Blokbereikindex - Block Range Index
Een Block Range Index of BRIN is een techniek voor het indexeren van databases . Ze zijn bedoeld om de prestaties bij extreem grote tafels te verbeteren.
BRIN-indexen bieden vergelijkbare voordelen als horizontale partitionering of sharding, maar zonder dat partities expliciet hoeven te worden gedeclareerd .
Een BRIN is van toepassing op een index op een tabel die groot is en waar de indexsleutelwaarde eenvoudig kan worden gesorteerd en geëvalueerd met een MinMax-functie .
BRIN werd oorspronkelijk voorgesteld door Alvaro Herrera van 2ndQuadrant in 2013 als 'Minmax-indexen'. Implementaties zijn tot dusver nauw gekoppeld aan interne implementatie- en opslagtechnieken voor de databasetabellen. Dit maakt ze efficiënt, maar beperkt ze tot bepaalde leveranciers. Tot nu toe is PostgreSQL de enige leverancier die een live-product met deze specifieke functie heeft aangekondigd in PostgreSQL 9.5. Andere leveranciers hebben een aantal vergelijkbare functies beschreven, waaronder Oracle , Netezza ' zonekaarten ' , Infobright 'datapakketten', MonetDB en Apache Hive met ORC / Parquet.
Ontwerp
BRIN werkt door grote blokken gegevens in een compacte vorm te "samenvatten", die efficiënt kan worden getest om veel van hen al vroeg uit te sluiten van een databasequery. Deze tests sluiten voor elke vergelijking een groot gegevensblok uit. Door het datavolume zo vroeg te verkleinen, zowel door grote blokken als kleine tuples weer te geven, als door veel blokken te elimineren, vermindert BRIN de hoeveelheid gedetailleerde gegevens die door het databaseknooppunt rij voor rij moeten worden onderzocht aanzienlijk.
Gegevensopslag in grote databases is gelaagd en opgedeeld, waarbij de tabelopslag in 'blokken' is gerangschikt. Elk blok bevat misschien 1 MB in elk blok en ze worden opgehaald door specifieke blokken van een schijfgebaseerde opslaglaag aan te vragen. BRIN is een lichtgewicht samenvattingslaag in het geheugen daarboven: elke tupel in de index vat één blok samen met betrekking tot het bereik van de gegevens die erin zijn opgenomen: de minimum- en maximumwaarden, en of het blok niet-nulgegevens bevat voor de kolom ( s) van belang.
In tegenstelling tot een traditionele index die de gebieden van de tabel lokaliseert die waarden bevatten die van belang zijn, fungeert BRIN als "negatieve indexen", die de blokken tonen die beslist niet van belang zijn en dus niet verder verwerkt hoeven te worden.
Enkele eenvoudige benchmarks suggereren een vijfvoudige verbetering van de zoekprestaties met een indexscan, vergeleken met de niet-geïndexeerde tabel. In vergelijking met B-trees vermijden ze hun overheadkosten voor onderhoud.
Omdat BRIN zo licht is, kunnen ze volledig in het geheugen worden bewaard, waardoor schijfoverhead tijdens het scannen wordt vermeden. Hetzelfde geldt misschien niet voor B-tree: B-tree vereist een boomknooppunt voor elke ongeveer N rijen in de tabel, waarbij N de capaciteit is van een enkel knooppunt, dus de indexgrootte is groot. Omdat BRIN slechts een tuple nodig heeft voor elk blok (van vele rijen), wordt de index voldoende klein om het verschil te maken tussen schijf en geheugen. Voor een 'smalle' tafel benadert het B-tree indexvolume dat van de tafel zelf; de BRIN is er misschien maar 5-15% van.
Voordelen
Zoeken en indexeren
Een grote database-index zou typisch B-tree- algoritmen gebruiken. BRIN is niet altijd een substituut voor B-tree, het is een verbetering ten opzichte van het sequentieel scannen van een index, met bijzondere (en potentieel grote) voordelen wanneer de index voldoet aan bepaalde voorwaarden om te worden besteld en het zoekdoel een beperkte set van deze waarden. In het algemene geval kan met willekeurige gegevens de B-tree nog steeds superieur zijn.
Een bijzonder voordeel van de BRIN-techniek, gedeeld met Oracle Exadata's Smart Scanning, is het gebruik van dit type index met Big Data- of datawarehousing- toepassingen, waarvan bekend is dat bijna de hele tabel niet relevant is voor het interessegebied. Met BRIN kan de tabel in dergelijke gevallen worden opgevraagd door alleen blokken op te halen die mogelijk interessante gegevens bevatten en die uit te sluiten die duidelijk buiten het bereik liggen of geen gegevens voor deze kolom bevatten.
Invoegen
Een regelmatig probleem bij de verwerking van grote tabellen is dat het ophalen van een index vereist is, maar het bijhouden van deze index vertraagt het toevoegen van nieuwe records. Typische praktijken zijn geweest om toevoegingen te groeperen en ze als een enkele bulktransactie toe te voegen, of om de index te verwijderen, de batch nieuwe records toe te voegen en vervolgens de index opnieuw te maken. Beide zijn storend voor gelijktijdige lees- / schrijfbewerkingen en zijn wellicht niet mogelijk in sommige continu werkende bedrijven.
Met BRIN wordt de vertraging door het handhaven van de index veel verminderd in vergelijking met B-tree. Wong meldt dat B-tree toevoegingen aan een niet-geïndexeerde 10GB-tabel met 85% vertraagde, maar een vergelijkbare BRIN had slechts een overhead van 11%.
Index maken
BRIN kan worden gemaakt voor extreem grote gegevens waarbij B-tree horizontale partitionering zou vereisen.
Het aanmaken van de BRIN gaat ook veel sneller dan voor een B-tree, namelijk met 80%. Dit zou een nuttige verbetering zijn voor het herstructureren van bestaande databasetoepassingen die de drop-add-reindex-benadering gebruiken, zonder dat de code moet worden gewijzigd.
Implementatie
Afhankelijkheid van tafelbestelling
Er kunnen meerdere BRIN worden gedefinieerd voor verschillende kolommen in een enkele tabel. Er zijn echter beperkingen.
BRIN is alleen efficiënt als de ordening van de sleutelwaarden de organisatie van blokken in de opslaglaag volgt. In het eenvoudigste geval kan dit de fysieke ordening van de tabel vereisen, wat vaak de aanmaakvolgorde is van de rijen erin, om overeen te komen met de volgorde van de sleutel. Als deze sleutel een aanmaakdatum is, kan dat een triviale vereiste zijn.
Als de gegevens echt willekeurig zijn, of als er veel verloop is van de sleutelwaarden in een 'hot' database, kunnen de aannames die aan BRIN ten grondslag liggen, mislukken. Alle blokken bevatten vermeldingen "van belang" en zo weinig kunnen in het begin worden uitgesloten door het BRIN-bereikfilter.
In de meeste gevallen is BRIN beperkt tot één index per tabel. Er kunnen meerdere BRIN's worden gedefinieerd, maar waarschijnlijk heeft slechts één de juiste volgorde. Als twee (of meer) indexen een soortgelijk ordeningsgedrag hebben, kan het mogelijk en nuttig zijn om meerdere BRIN's op dezelfde tafel te definiëren. Een voor de hand liggend voorbeeld is waar zowel een aanmaakdatum als een record_id-kolom beide monotoon toenemen met de volgorde van het maken van records. In andere gevallen is de sleutelwaarde misschien niet monotoon, maar op voorwaarde dat er nog steeds een sterke groepering is binnen de fysieke volgorde van de plaat, is BRIN effectief.
Exadata-opslagindexen
BRIN heeft enkele overeenkomsten met Oracle Exadata " Storage Indexes ". Exadata heeft het sterke concept van een 'opslaglaag' in zijn architectuurstack. Tabelgegevens worden in blokken of 'opslagcellen' op de opslagservers bewaard. Deze opslagcellen zijn ondoorzichtig voor de opslagserver en worden op verzoek teruggestuurd naar de database-engine met hun identificator. Voorheen moesten de databaseknooppunten alle opslagcellen opvragen om ze te scannen.
Storage Indexes zorgt voor het snoeien van gegevens op deze laag: efficiënt aangeven van secties die verder niet interessant zijn. De opslagindex wordt in het geheugen op de opslagserver geladen, zodat wanneer een verzoek om cellen wordt verzonden, deze kan worden voorspeld met zoekwaarden. Deze worden vergeleken met de Storage Index en dan hoeven alleen de relevante cellen terug te worden gestuurd naar het databankknooppunt.
Prestatievoordelen met een opslagindex zijn het duidelijkst wanneer de geïndexeerde kolom veel nullen bevat . Er worden enorme prestatievoordelen behaald bij het scannen van schaarse gegevens .
Ontwikkeling
Ontwikkeling voor PostgreSQL werd uitgevoerd als onderdeel van het AXLE-project (Advanced Analytics for Extremely Large European Databases). Dit werk werd gedeeltelijk gefinancierd door het zevende kaderprogramma van de Europese Unie (FP7 / 2007-2013).
PostgreSQL
Implementatie voor PostgreSQL was voor het eerst zichtbaar in 2013. BRIN verscheen begin 2016 in release 9.5 van PostgreSQL .
