Block Range Index - Block Range Index
Et Block Range Index eller BRIN er en databaseindekseringsteknik . De er beregnet til at forbedre ydeevnen med ekstremt store borde.
BRIN-indekser giver lignende fordele som vandret partitionering eller sharding, men uden eksplicit at skulle erklære partitioner.
En BRIN kan anvendes på et indeks på en tabel, der er stor, og hvor indeksnøgleværdien let sorteres og evalueres med en MinMax-funktion .
BRIN blev oprindeligt foreslået af Alvaro Herrera fra 2ndQuadrant i 2013 som 'Minmax-indekser'. Implementeringer hidtil er tæt knyttet til intern implementering og lagringsteknikker til databasetabellerne. Dette gør dem effektive, men begrænser dem til bestemte leverandører. Indtil videre er PostgreSQL den eneste leverandør, der har annonceret et live produkt med denne specifikke funktion i PostgreSQL 9.5. Andre leverandører har beskrevet nogle lignende funktioner, herunder Oracle , Netezza 'zone maps', Infobright 'data packs', MonetDB og Apache Hive with ORC / Parquet.
Design
BRIN fungerer ved at "opsummere" store blokke af data til en kompakt form, som kan testes effektivt for at udelukke mange af dem fra en databaseforespørgsel tidligt. Disse tests udelukker en stor datablok til hver sammenligning. Ved at reducere datavolumenet så tidligt, både ved at repræsentere store blokke som små tupler, og ved at eliminere mange blokke, reducerer BRIN væsentligt mængden af detaljerede data, der skal undersøges af databaseknudepunktet række for række.
Datalagring i store databaser er lagdelt og klumpet, med bordlagring arrangeret i 'blokke'. Hver blok indeholder måske 1 MB i hvert stykke, og de hentes ved at anmode om specifikke blokke fra et diskbaseret lagerlag. BRIN er et let resumélag i hukommelsen over dette: hver tuple i indekset opsummerer en blok med hensyn til rækkevidden af data deri: dens minimums- og maksimumværdier, og hvis blokken indeholder data, der ikke er nul til kolonnen ( s) af interesse.
I modsætning til et traditionelt indeks, der lokaliserer regionerne i tabellen, der indeholder værdier af interesse, fungerer BRIN som "negative indekser", der viser de blokke, der bestemt ikke er af interesse og derfor ikke behøver at blive behandlet yderligere.
Nogle enkle benchmarks antyder en femdoblet forbedring af søgeeffekten med en indeksscanning sammenlignet med den ikke-indekserede tabel. Sammenlignet med B-træer undgår de deres vedligeholdelsesomkostninger.
Da BRIN er så lette, kan de muligvis holdes helt i hukommelsen og dermed undgå diskoverhead under scanningen. Det samme er muligvis ikke tilfældet med B-træ: B-træ kræver en træknude for hver cirka N række i tabellen, hvor N er kapaciteten for en enkelt node, og dermed er indeksstørrelsen stor. Da BRIN kun kræver en tuple for hver blok (med mange rækker), bliver indekset tilstrækkeligt lille til at gøre forskellen mellem disk og hukommelse. For en 'smal' tabel nærmer B-træindeksvolumen sig til selve tabellen; BRIN er muligvis kun 5-15% af det.
Fordele
Søg og indeks scan
Et stort databaseindeks bruger typisk B- træalgoritmer. BRIN er ikke altid en erstatning for B-tree, det er en forbedring af sekventiel scanning af et indeks med særlige (og potentielt store) fordele, når indekset opfylder bestemte betingelser for at blive bestilt, og at søgemålet skal være et snævert sæt af disse værdier. I almindelighed, med tilfældige data, kan B-tree stadig være overlegen.
En særlig fordel ved BRIN-teknikken, der deles med Oracle Exadatas Smart Scanning, er brugen af denne type indeks med Big Data- eller datalagringsapplikationer , hvor det vides, at næsten hele tabellen er irrelevant for interessen. BRIN gør det muligt at spørge tabellen i sådanne tilfælde ved kun at hente blokke, der kan indeholde data af interesse, og ekskludere dem, der klart er uden for området, eller som ikke indeholder nogen data til denne kolonne.
Indsæt
Et regelmæssigt problem med behandlingen af store tabeller er, at hentning kræver brug af et indeks, men vedligeholdelse af dette indeks bremser tilføjelsen af nye poster. Typisk praksis har været at gruppere tilføjelser sammen og tilføje dem som en enkelt bulk-transaktion eller at droppe indekset, tilføje batchen af nye poster og derefter genskabe indekset. Begge disse er forstyrrende for samtidige læse / skrive-operationer og er muligvis ikke mulige i nogle kontinuerligt fungerende virksomheder.
Med BRIN er afmatningen fra opretholdelse af indekset meget reduceret sammenlignet med B-træ. Wong rapporterer, at B-tree bremsede tilføjelser til en uindekseret 10 GB-tabel med 85%, men en sammenlignelig BRIN havde kun en generalomkostning på 11%.
Indeks oprettelse
BRIN kan oprettes til ekstremt store data, hvor B-træet kræver vandret opdeling.
Oprettelse af BRIN er også meget hurtigere end for et B-træ, med 80%. Dette ville være en nyttig forbedring af refactoring af eksisterende databaseapplikationer, der bruger drop-add-reindex-tilgangen uden at kræve kodeændringer.
Implementering
Afhængighed af bordbestilling
Flere BRIN kan defineres for forskellige kolonner på en enkelt tabel. Der er dog begrænsninger.
BRIN er kun effektive, hvis rækkefølgen af nøgleværdier følger organisationen af blokke i lagringslaget. I det enkleste tilfælde kan dette kræve den fysiske rækkefølge af tabellen, som ofte er oprettelsesrækkefølgen for rækkerne inden i den, for at matche nøglens rækkefølge. Hvor denne nøgle er en oprettelsesdato, kan det være et trivielt krav.
Hvis dataene virkelig er tilfældige, eller hvis der er meget churn af nøgleværdierne i en 'hot' database, kan antagelserne bag BRIN muligvis bryde sammen. Alle blokke indeholder poster "af interesse", og så få kan ekskluderes tidligt af BRIN-rækkefilteret.
I de fleste tilfælde er BRIN begrænset til et enkelt indeks pr. Tabel. Flere BRIN kan defineres, men kun en har sandsynligvis passende ordre. Hvis to (eller flere) indekser har samme rækkefølge, kan det være muligt og nyttigt at definere flere BRIN på samme tabel. Et indlysende eksempel er, hvor både en oprettelsesdato og en record_id-kolonne begge øges monotont med sekvensen for oprettelse af poster. I andre tilfælde kan nøgleværdien muligvis ikke være monoton, men forudsat at der stadig er en stærk gruppering inden for postens fysiske rækkefølge, er BRIN effektiv.
Exadata Storage Indexes
BRIN har nogle ligheder med Oracle Exadata " Storage Indexes ". Exadata har det stærke koncept med et 'lagringslag' i sin arkitekturstak. Tabeldata holdes i blokke eller 'lagringsceller' på lagerserverne. Disse lagringsceller er uigennemsigtige for lagringsserveren og returneres til databasemotoren efter anmodning ved hjælp af deres identifikator. Tidligere skal databaseknuderne anmode om alle lagringscellerne for at scanne dem.
Storage Indexes giver data beskæring på dette lag: indikerer effektivt sektioner, der ikke er yderligere interesserede. Lagerindekset indlæses i hukommelsen på lagerserveren, så når en anmodning om celler udstedes, kan det være baseret på søgningsværdier. Disse sammenlignes med lagerindekset, og kun de relevante celler skal derefter returneres til databasenoden.
Ydelsesfordele med et lagerindeks er tydeligst, når den indekserede kolonne indeholder mange nuller . Der opnås store ydelsesfordele ved scanning på tværs af sparsomme data .
Udvikling
Udvikling af PostgreSQL blev udført som en del af AXLE-projektet (Advanced Analytics for Extremely Large European Databases). Dette arbejde blev delvist finansieret af Den Europæiske Unions syvende rammeprogram (FP7 / 2007-2013).
PostgreSQL
Implementering af PostgreSQL var først tydelig i 2013. BRIN dukkede op i frigivelse 9.5 af PostgreSQL i starten af 2016.
