Bitmappsindex

Ett bitmappsindex är en speciell typ av databasindex som använder bitmappar .

Bitmappsindex har traditionellt ansetts fungera bra för kolumner med låg kardinalitet , som har ett blygsamt antal distinkta värden, antingen absolut eller i förhållande till antalet poster som innehåller data. Extremfallet med låg kardinalitet är boolesk data (t.ex. har en invånare i en stad tillgång till internet?), som har två värden, True och False. Bitmappsindex använder bitmatriser (vanligen kallade bitmappar) och svarar på frågor genom att utföra bitvis logiska operationer på dessa bitmappar. Bitmappsindex har en betydande utrymmes- och prestandafördel jämfört med andra strukturer för sökning av sådana data. Deras nackdel är att de är mindre effektiva än de traditionella B-tree- indexen för kolumner vars data uppdateras ofta: följaktligen används de oftare i skrivskyddade system som är specialiserade för snabba frågor - t.ex. datalager, och i allmänhet olämpliga för applikationer för onlinetransaktionsbearbetning .

Vissa forskare hävdar att bitmappsindex också är användbara för data med måttlig eller till och med hög kardinalitet (t.ex. data med unikt värde) som nås på ett skrivskyddat sätt, och frågor får åtkomst till flera bitmappsindexerade kolumner med hjälp av AND , OR eller XOR operatörer i stor utsträckning.

Bitmappsindex är också användbara i datalagringsapplikationer för att sammanfoga en stor faktatabell med mindre dimensionstabeller som de som är arrangerade i ett stjärnschema .

Exempel

Om du fortsätter med exemplet med internetåtkomst kan ett bitmappsindex ses logiskt enligt följande:

Identifierare Har Internet Bitmappar
Y N
1 Ja 1 0
2 Nej 0 1
3 Nej 0 1
4 Ospecificerad 0 0
5 Ja 1 0

Till vänster hänvisar Identifier till det unika numret som tilldelats varje invånare, HasInternet är data som ska indexeras, innehållet i bitmappsindexet visas som två kolumner under rubriken bitmappar . Varje kolumn i den vänstra illustrationen under rubriken Bitmaps är en bitmapp i bitmappsindexet. I det här fallet finns det två sådana bitmappar, en för "har internet" Ja och en för "har internet" Nej . Det är lätt att se att varje bit i bitmapp Y visar om en viss rad hänvisar till en person som har tillgång till internet. Detta är den enklaste formen av bitmappsindex. De flesta kolumner kommer att ha mer distinkta värden. Till exempel kommer försäljningsbeloppet sannolikt att ha ett mycket större antal distinkta värden. Variationer på bitmappsindexet kan också effektivt indexera dessa data. Vi går kort igenom tre sådana varianter.

Obs: Många av referenserna som citeras här är granskade på ( John Wu (2007)) . För de som kan vara intresserade av att experimentera med några av idéerna som nämns här, är många av dem implementerade i programvara med öppen källkod som FastBit, Lemur Bitmap Index C++ Library, Roaring Bitmap Java-biblioteket och Apache Hive Data Warehouse- systemet .

Kompression

Av historiska skäl utvecklades bitmappskomprimering och inverterad listkomprimering som separata forskningslinjer, och först senare erkändes de lösa i huvudsak samma problem.

Programvara kan komprimera varje bitmapp i ett bitmappsindex för att spara utrymme. Det har lagts ner mycket arbete på detta ämne. Även om det finns undantag som rytande bitmappar, använder bitmappskomprimeringsalgoritmer vanligtvis körlängdskodning , som den bytejusterade bitmappskoden, den ordjusterade hybridkoden, den partitionerade ordjusterade hybriden (PWAH) komprimeringen, positionslistans ord Aligned Hybrid, Compressed Adaptive Index (COMPAX), Enhanced Word-Aligned Hybrid (EWAH) och Compressed 'N' Composable Integer Set (CONCISE). Dessa komprimeringsmetoder kräver mycket liten ansträngning för att komprimera och dekomprimera. Ännu viktigare är att bitmappar komprimerade med BBC, WAH, COMPAX, PLWAH, EWAH och CONCISE kan delta direkt i bitvisa operationer utan dekompression. Detta ger dem avsevärda fördelar jämfört med generiska kompressionstekniker som LZ77 . BBC-komprimering och dess derivator används i ett kommersiellt databashanteringssystem . BBC är effektivt både för att minska indexstorlekar och bibehålla frågeprestanda . BBC kodar bitmapparna i byte , medan WAH kodar i ord, bättre matchar nuvarande CPU: er . "På både syntetisk data och verklig applikationsdata använder de nya ordjusterade scheman bara 50 % mer utrymme, men utför logiska operationer på komprimerad data 12 gånger snabbare än BBC." PLWAH-bitmappar rapporterades ta 50 % av lagringsutrymmet som konsumeras av WAH-bitmappar och ger upp till 20 % snabbare prestanda vid logiska operationer . Liknande överväganden kan göras för CONCISE och Enhanced Word-Aligned Hybrid.

Prestandan för scheman som BBC, WAH, PLWAH, EWAH, COMPAX och CONCISE är beroende av ordningen på raderna. En enkel lexikografisk sortering kan dela indexstorleken med 9 och göra index flera gånger snabbare. Ju större tabellen är, desto viktigare är det att sortera raderna. Omblandningstekniker har också föreslagits för att uppnå samma resultat av sortering vid indexering av strömmande data.

Kodning

Grundläggande bitmappsindex använder en bitmapp för varje distinkt värde. Det är möjligt att minska antalet bitmappar som används genom att använda en annan kodningsmetod . Till exempel är det möjligt att koda distinkta C-värden med log(C) bitmappar med binär kodning .

Detta minskar antalet bitmappar, vilket sparar ytterligare utrymme, men för att svara på alla frågor måste de flesta bitmappar nås. Detta gör det potentiellt inte lika effektivt som att skanna en vertikal projektion av basdata, även känd som en materialiserad vy eller projektionsindex. Att hitta den optimala kodningsmetoden som balanserar (godtycklig) frågeprestanda, indexstorlek och indexunderhåll är fortfarande en utmaning.

Utan att överväga komprimering, analyserade Chan och Ioannidis en klass av flerkomponentkodningsmetoder och kom till slutsatsen att tvåkomponentskodning sitter vid vinkeln på kurvan för prestanda kontra indexstorlek och därför representerar den bästa avvägningen mellan indexstorlek och indexstorlek. frågeprestanda.

Binning

För kolumner med hög kardinalitet är det användbart att lagra värdena, där varje fack täcker flera värden och bygga bitmapparna för att representera värdena i varje fack. Detta tillvägagångssätt minskar antalet bitmappar som används oavsett kodningsmetod. Men arkiverade index kan bara svara på vissa frågor utan att undersöka basdata. Till exempel, om en fack täcker intervallet från 0,1 till 0,2, när användaren frågar efter alla värden mindre än 0,15, är alla rader som faller i facket möjliga träffar och måste kontrolleras för att verifiera om de faktiskt är mindre än 0,15 . Processen att kontrollera basdata är känd som kandidatkontrollen. I de flesta fall är tiden som används av kandidatkontrollen betydligt längre än den tid som behövs för att arbeta med bitmappsindexet. Därför uppvisar arkiverade index oregelbundna prestanda. De kan vara mycket snabba för vissa frågor, men mycket långsammare om frågan inte exakt matchar en fack.

Historia

Begreppet bitmappsindex introducerades först av professor Israel Spiegler och Rafi Maayan i deras forskning "Storage and Retrieval Considerations of Binary Data Bases", publicerad 1985. Den första kommersiella databasprodukten som implementerade ett bitmappsindex var Computer Corporation of America's Model 204 . Patrick O'Neil publicerade en artikel om denna implementering 1987. Denna implementering är en hybrid mellan det grundläggande bitmappsindexet (utan komprimering) och listan över radidentifierare (RID-lista). Överlag är indexet organiserat som ett B+träd . När kolumnkardinaliteten är låg, skulle varje lövnod i B-trädet innehålla en lång lista med RID. I det här fallet kräver det mindre utrymme för att representera RID-listorna som bitmappar. Eftersom varje bitmapp representerar ett distinkt värde är detta det grundläggande bitmappsindexet. När kolumnkardinaliteten ökar blir varje bitmapp gles och det kan ta mer diskutrymme att lagra bitmapparna än att lagra samma innehåll som RID-listor. I detta fall byter den till att använda RID-listorna, vilket gör det till ett B+trädindex .

Bitmaps i minnet

En av de starkaste anledningarna till att använda bitmappsindex är att de mellanliggande resultaten som produceras från dem också är bitmappar och kan effektivt återanvändas i ytterligare operationer för att svara på mer komplexa frågor. Många programmeringsspråk stöder detta som en bitarray-datastruktur. Till exempel har Java klassen BitSet .

Vissa databassystem som inte erbjuder beständiga bitmappsindex använder bitmappar internt för att påskynda frågebehandlingen. Till exempel PostgreSQL version 8.1 och senare en "bitmap index scan"-optimering för att påskynda godtyckligt komplexa logiska operationer mellan tillgängliga index på en enda tabell.

För tabeller med många kolumner växer det totala antalet distinkta index för att tillfredsställa alla möjliga frågor (med likhetsfiltreringsvillkor på något av fälten) mycket snabbt, eftersom det definieras av denna formel:

.

En bitmappsindexskanning kombinerar uttryck på olika index, vilket kräver endast ett index per kolumn för att stödja alla möjliga frågor i en tabell.

Genom att tillämpa denna åtkomststrategi på B-trädindex kan du också kombinera intervallfrågor på flera kolumner. I detta tillvägagångssätt skapas en temporär bitmapp i minnet med en bit för varje rad i tabellen (1 MB kan alltså lagra över 8 miljoner poster). Därefter kombineras resultaten från varje index till bitmappen med hjälp av bitvisa operationer . Efter att alla villkor har utvärderats innehåller bitmappen en "1" för rader som matchade uttrycket. Slutligen korsas bitmappen och matchande rader hämtas. Förutom att effektivt kombinera index, förbättrar detta också referensplatsen för tabellåtkomster, eftersom alla rader hämtas sekventiellt från huvudtabellen. Den interna bitmappen kasseras efter frågan. Om det finns för många rader i tabellen för att använda 1 bit per rad, skapas istället en "förlustig" bitmapp med en enda bit per disksida. I det här fallet används bitmappen bara för att bestämma vilka sidor som ska hämtas; filterkriterierna tillämpas sedan på alla rader på matchande sidor.

Anteckningar
Bibliografi
Hämtad från " https://en.wikipedia.org/w/index.php?title=Bitmap_index&oldid=1105474840 "