Batch-modus Bitmaps in SQL Server

Achtergrond

In traditionele rij-modus uitvoeringsplannen, kan SQL Server een Bitmap-operator introduceren als onderdeel van het uitvoeren van vroege semi-join-reductie vóór een parallelle hash- of merge-join. De bitmap is opgebouwd uit de build-invoer en wordt gebruikt om rijen op de probe-invoer te filteren voordat ze de join bereiken. Ik heb geschreven over row-mode bitmaps eerder en ze worden ook behandeld in de documentatie.

Dit artikel gaat over batchmodus bitmaps, die een heel andere implementatie hebben. Er zijn grote verbeteringen aangebracht sinds de eerste verschijning van de batchmodusuitvoeringsengine in SQL Server 2012. De details die hier worden gegeven, zijn van toepassing op SQL Server 2017 - de meest recent uitgebrachte versie op het moment van schrijven. Functies die specifiek zijn voor eerdere versies zullen inline worden vermeld terwijl we verder gaan.

De Query Optimizer

De enige join-operator die in batchmodus kan worden uitgevoerd, is hash-join. De query-optimizer beslist of een hash-join in batchmodus (serieel of parallel) een bitmap moet hebben of niet. De optimizer beoordeelt het potentiële nut van een bitmap door de selectiviteit van een hypothetische semi-join te berekenen van de hash join-invoer op de join-sleutel(s).

Een semi-join is logisch, omdat de functie van bitmapfiltering is om rijen van de probe-zijde te verwijderen die niet bestaan ​​aan de build-zijde. Als de geschatte selectiviteit van de semi-join 0,75 . is of minder, de optimizer acht het de moeite waard om een ​​bitmapfilter in batchmodus te gebruiken. Met andere woorden, een bitmap wordt gespecificeerd als de berekening van de semi-join aangeeft dat 25% of meer van de rijen aan de tasterzijde door de bitmap zouden worden geëlimineerd.

De exacte selectiviteit van semi-join wordt alleen gebruikt om te bepalen of de hash-join een bitmap moet hebben of niet. De schatting van de selectiviteit aan de sondezijde (zichtbaar als een effect op schattingen van de kardinaliteit) is aangepast om het feit weer te geven dat bitmaps over het algemeen niet perfect zijn in het verwijderen van niet-gekwalificeerde rijen. Dit is met name het geval wanneer de bitmap is geïmplementeerd met behulp van een Bloom-filter, dat valse positieven kan genereren (rijen aan de sondezijde die het filter passeren, maar niettemin niet aansluiten op de build-zijde).

Selectiviteitsafronding

De optimizer houdt rekening met deze onzekerheid door de semi-join selectiviteit af te ronden op een macht van tien. Het doet dit door de logaritme met grondtal 10 te nemen voordat wordt afgerond. Een semi-joinselectiviteit van 0,316 geeft bijvoorbeeld een log₁₀ waarde fractioneel onder -0,5, die naar beneden wordt afgerond op -1. De resulterende selectiviteit aan de sondezijde is 10 =0,1. Daarentegen geeft een semi-join selectiviteit van 0,317 een log₁₀ waarde net boven -0,5, die wordt afgerond op nul. De selectiviteit aan de sondezijde is daarom 10 =1 (alle rijen passeren). Mogelijke probe-side bitmap-selectiviteiten die resulteren uit deze reeks berekeningen zijn 1, 0,1, 0,01, 0,001 enzovoort. Houd er rekening mee dat een bitmap nog steeds kan worden gebruikt wanneer de geschatte selectiviteit naar boven wordt afgerond op 1 (alle rijen passeren het predikaat).

Operators en kardinaliteitsschattingen

Er is geen aparte Bitmap operator voor een hash-join in batchmodus. In plaats daarvan heeft de hash-join-operator een Bitmap Creator eigenschap (ingesteld op waar), of de eigenschap ontbreekt (niet ingesteld op onwaar). Dit verschil tussen uitvoering in rijmodus en batchmodus maakt het minder gemakkelijk om te zien of een bitmap wordt gemaakt, maar geeft wel nauwkeuriger het onderliggende proces weer:bij uitvoering in rijmodus wordt de Bitmap operator vult de bitmap terwijl rijen er één voor één doorheen stromen voordat de hash join build-invoer wordt bereikt. Met andere woorden, de bitmap en hashtabel worden gelijktijdig gebouwd onder uitvoering in rijmodus. In batchmodus is de hashtabel volledig gebouwd voordat de bitmap wordt gemaakt (hierover binnenkort meer).

De query-optimizer maakt geen op kosten gebaseerde keuzes over de positie van een bitmapfilter in batchmodus aan de testzijde van de hash-join. Er wordt eenvoudigweg vanuit gegaan dat de selectiviteit van de bitmap van toepassing is op alle onderliggende operatoren aan de sondezijde. In werkelijkheid wordt de bitmap pas naar beneden gedrukt als een enkel definitief uitvoeringsplan door de optimizer is geselecteerd. Als de bitmap niet helemaal naar een leaf-operator kan worden gepusht, zien kardinaliteitsschattingen er een beetje vreemd uit. Dit is een afweging die in de toekomst kan worden verbeterd.

De Execution Engine

Terwijl de optimizer beslist of een hash-join batchmodusbitmap moet worden gebruikt of niet, de batchmodusuitvoeringsengine bepaalt het type van bitmap te gebruiken tijdens runtime. Deze beslissing wordt gebaseerd op statistische informatie die is verzameld over de join-sleutels aan de buildzijde tijdens het bouwen van de hashtabel. Zoals eerder vermeld, bouwen batch-modus hash-joins, in tegenstelling tot uitvoering in rijmodus, eerst de hashtabel volledig op, voordat een afzonderlijke passage over de hashtabel wordt uitgevoerd om de bitmap te bouwen.

Eenvoudige bitmaps

Er zijn twee hoofdtypen hash-joinbitmap in batchmodus. Een eenvoudige bitmap bevat één bit voor elk van een aaneengesloten reeks waarden aan de buildzijde. Een eenvoudige bitmap van één byte kan bijvoorbeeld aangeven of acht aaneengesloten waarden aan de buildzijde aanwezig zijn of niet. De waarden 0 tot en met 7 kunnen in de bitmap worden gecodeerd door de bijbehorende bit in te stellen. Een waarde van 5 zou bit 5 instellen, wat de positionele waarde van 2 heeft. We zouden de set {1, 5, 7} kunnen coderen als 2 + 2 + 2 =2 + 32 + 128 =162 =10100010₂ . Een reeks waarden die niet bij nul begint, kan op dezelfde manier worden gecodeerd door alle waarden te compenseren met de minimumwaarde die in de set aanwezig is (die we kennen uit de hashtabelstatistieken).

Een eenvoudige bitmap heeft het voordeel dat exacte informatie over de daadwerkelijk aanwezige build-side waarden, ten koste van geheugen dat evenredig is aan het bereik aantal waarden aanwezig.

Complexe bitmaps

Het tweede type bitmap is een Bloom-filter. Dit stelt een of meer bits in de bitmapstructuur in op basis van het resultaat van het toepassen van een of meer hashfuncties op elke waarde aan de buildzijde. We testen op overeenkomsten door dezelfde hashfuncties toe te passen op elke waarde aan de sondezijde. Als een van de hash-functies een bit identificeert dat niet is ingesteld, kunnen we er zeker van zijn dat de huidige probe-waarde niet aan de build-kant verschijnt.

Aangezien een Bloom-filter een probabilistische structuur is, filteren we sommige probe-waarden die geen match hebben aan de build-side (fout-positief) misschien niet weg, maar we zullen nooit een waarde uitfilteren die aanwezig is (fout-negatief). Met andere woorden, een Bloom-filter vertelt ons ofwel "misschien een match" of "absoluut geen match". Het aantal valse positieven kan worden verminderd door ofwel meer bits per sleutel (een grotere bitmap) te gebruiken of door meer hash-functies te gebruiken. Voor alle duidelijkheid:een Bloom-filter mag produceren exacte filtering, maar het kan ook niet.

Bloom-filters bieden een ruimte- en tijdbesparend alternatief wanneer een eenvoudige bitmap wegens ruimtegebrek niet mogelijk. De implementatie in batchmodus van SQL Server van een Bloom-filter is geoptimaliseerd voor moderne CPU-cache-architecturen en staat intern bekend als een complexe bitmap . Complexe bitmaps ondersteunen sinds SQL Server 2014 meerdere samenvoegkolommen en alle gegevenstypen in batchmodus.

Bitmapkeuze

Of SQL Server kiest voor een eenvoudige of complex (Bloom-filter) bitmap hangt af van het bereik van build-side-waarden (van hash-tabelstatistieken). Er is een belangrijk voorbehoud bij het woord "bereik", dat in de volgende sectie zal worden uitgelegd. Ondertussen kiest de uitvoeringsengine het type bitmap als volgt:

1. Een kleine eenvoudige bitmap wordt gebruikt wanneer het waardenbereik 2 (8.388.608) of minder is. Dit is het aantal bits in 1 MB.
2. Als het waardenbereik groter is dan 2 maar kleiner dan of gelijk aan 2 (8 MB), kiest de uitvoeringsengine tussen een grote eenvoudige bitmap en een complexe bitmap door voor elke optie het benodigde geheugen te berekenen en de kleinere te kiezen. Een grote eenvoudige bitmap kan tot 8 MB groot zijn. De grootte van een complexe bitmap hangt af van het aantal bits per sleutel dat nodig is om de gegevens adequaat weer te geven. Meer verschillende waarden betekent normaal gesproken een grotere complexe bitmap.
3. Als het waardenbereik groter is dan 2 bits, een complexe bitmap wordt gebruikt.

Over het waardenbereik

Het bereik van waarden waarnaar hierboven wordt verwezen, is gebaseerd op de interne binaire weergave van de gegevens. Bijvoorbeeld de smallint waarden 128 en 255 kunnen worden weergegeven als 0x0080 en 0x00FF , met een bereik van 0x7F (127) binaire waarden. Dit bereik zou goed werken met een kleine, eenvoudige bitmap.

Aan de andere kant, de datetime waarden "1900-01-01" en "1900-01-02" kunnen in 8 bytes worden weergegeven als 0x0000000100000000 en 0x0000000200000000 (vier bytes voor dagen en vier bytes voor tikken na middernacht). Deze gesegmenteerde weergave geeft een binair bereik van 0x0100000000 (4.294.967.296) voor die twee voorbeeldwaarden, wat veel te groot is om in een eenvoudige bitmap (zelfs een grote) te passen. Gegevenstypen met complexe binaire representaties (bijv. byte-swapping) werken doorgaans niet goed met eenvoudige bitmaps.

Een andere complicatie is dat gegevens in batchmodus worden genormaliseerd — geconverteerd naar een binaire lay-out die goed werkt met gevectoriseerde instructies — en altijd 64 bits groot is. Waarden die niet in 64 bits passen, worden "off row" opgeslagen met een 64-bits pointer in de rij. Deze binaire lay-out is trouwens niet hetzelfde als gerapporteerd door een T-SQL-conversie naar een binair type.

Desalniettemin is de genormaliseerde lay-out vergelijkbaar genoeg voor typen integers (bijv. integer en bigint ) dat eenvoudige bitmaps nog steeds nuttig zijn voor reeksen van deze gegevenstypen. Andere typen met een geheel getal-achtige binaire representatie (bijv. money en date ) zijn ook geschikt.

Nog een voorbeeld:een set van integer waarden in het bereik van 1 tot 8.388.608 zullen slechts passen in een kleine eenvoudige bitmap van 1 MB, met één bit per mogelijke integerwaarde in het bereik. Het bereik kan een vaste offset hebben, dus een geheel getal van 10.000.000 tot 18.388.607 zou ook passen (met een offset van tien miljoen). Merk op dat het nummer van de aanwezige waarden doet er niet toe, alleen het bereik. Twee waarden van 0 en 8.388.607 vullen het kleine, eenvoudige bitmapbereik net zo goed als een set van alle mogelijke waarden tussen die twee uitersten.

Bereiktabellen

Wanneer de batchmodusuitvoeringsengine besluit een grote eenvoudige . te bouwen bitmap of een complex bitmap voor een hash-join, het bouwt ook een bereiktabel. Het doet niet bouw een bereiktabel voor klein eenvoudige bitmaps.

De bereiktabel is een 128KB-structuur met een vaste grootte die bestaat uit 8.192 paren van 8-bytewaarden die een (laag, hoog) bereik van waarden specificeren die aanwezig zijn in de hashtabel. Een bereiktabel kan worden gebouwd op elk gegevenstype dat compatibel is met uitvoering in batchmodus. Tijdens het scannen van de voltooide hash-tabel wordt elke batch gegevens gebruikt om de bitmap en te vullen de bereiktabel.

Voor elke waarde in de batch wordt een hash-functie gebruikt om een ​​bucket (paar bereikwaarden) in de bereiktabel te vinden. Als de bucket momenteel niet wordt gebruikt, wordt de waarde opgeslagen in zowel lage als hoge 8-bytewaarden. Als de emmer al in gebruik is, wordt de volgende emmer gevuld (en zo verder, totdat er een lege emmer is gevonden).

Als de bereiktabel voor een derde vol raakt (2.730 van 8.192 gebruikte buckets), worden de gebruikte items gekopieerd, wordt het bucketbereik verdubbeld en worden de opgeslagen waarden op dezelfde manier opnieuw ingevoegd als voorheen (hoewel de hash-functie rekening houdt met de nieuwe bakmaat). Overlappende buckets worden samengevoegd en het proces van verdubbeling gaat door totdat het aantal gebruikte buckets onder de 2.730 daalt. Twee buckets die aanvankelijk de 'bereiken' (1-1) en (2-2) bevatten, kunnen bijvoorbeeld worden samengevoegd tot een enkele bereikbucket van (1-2) na de eerste bereikverdubbeling.

Zodra alle batches hashtabelgegevens zijn verwerkt in de bereiktabel, wordt een laatste bucket merge uitgevoerd, waarna een in-place quicksort de buckets in waardevolgorde plaatst. Dit maakt een binaire zoekopdracht mogelijk om een ​​bereik-bucket te lokaliseren met een bepaalde waarde van belang.

Het nettoresultaat van al deze activiteiten is het produceren van een set van maximaal 2730 verschillende bereiken die de gegevens in de hashtabel beschrijven (naast de grote eenvoudige of complexe bitmap).

De bereiktabel gebruiken

De bereiktabel wordt gebruikt wanneer een hash-join-bitmapfilter naar beneden wordt geduwd in een kolomopslag-scanoperator aan de sondezijde. Elk columnstore-segment heeft catalogusmetagegevens over de minimale en maximale gegevenswaarden die in het segment aanwezig zijn. De uitvoeringsengine kan deze informatie gebruiken om binair in de bitmapbereiktabel te zoeken naar een overeenkomst. Als er geen overeenkomst wordt gevonden, kan de uitvoeringsengine het segment volledig overslaan.

Deze runtime-optimalisatie vindt ook plaats voor read-ahead, zodat de engine zelfs kan voorkomen dat segmenten in het geheugen worden gelezen waarvan hij weet dat deze door het bereiktabelfilter worden geëlimineerd. Alle segmenten die niet door de bereiktabel zijn geëlimineerd, worden nog steeds gefilterd met behulp van de bitmap. Deze combinatie zorgt ervoor dat het maximale aantal rijen zo vroeg mogelijk wordt geëlimineerd.

Hoewel een bereiktabel niet is gemaakt voor een kleine, eenvoudige bitmap, kan die structuur ook worden gebruikt om segmentverwijdering te bereiken, omdat het waardenbereik bekend is (inclusief eventuele verschuivingen). Het is klein genoeg om het niet de moeite waard te maken om het in subbereiken te verdelen met behulp van een bereiktabel.

Wanneer de bitmap niet naar beneden in een columnstore-scan wordt geduwd, kan deze nog steeds worden geëvalueerd als een normale batchmodusfilter om semi-joinreductie te bereiken vóór de hash-join. Dit is veel minder efficiënt dan segmentverwijdering of filtering tijdens de columnstore-scan, maar het is nog steeds beter dan filteren op de hash-join zelf.

Bitmaps en gecomprimeerde gegevens

Het toepassen van een hash-join batch-modusbitmap op columnstore-gegevens als onderdeel van de scan kan zeer goede prestaties opleveren, maar het vereist wel dat onzuivere segmentgegevens worden gedecomprimeerd voordat de bitmap kan worden toegepast. Deze decompressie kan efficiënt worden uitgevoerd met behulp van SIMD-instructies, maar het is nog steeds extra werk.

SQL Server 2016 introduceerde de mogelijkheid om een ​​bitmap te maken voor algemene predikaten op in woordenboeken gecodeerde segmentgegevens. Het predikaat wordt geëvalueerd aan de hand van de woordenboekitems om een ​​nieuwe . te produceren kleine bitmap waarbij elk ingesteld bit een woordenboekinvoer aangeeft die aan het predikaat voldoet. Het toepassen van deze bitmap kan extreem snel gaan, zeker als de bitmap in één SIMD-register past. SQL Server kan SIMD nog steeds gebruiken als de bitmap niet past, maar het verzamelen van bits uit een in-memory bitmap is iets minder efficiënt dan het geval in het register.

Deze optimalisatie voor 2016 kan worden toegepast op elke predikaat geduwd in een columnstore-scan, inclusief een bitmap-predikaat dat is gemaakt door een upstream-hash-join. Voor alle duidelijkheid:SQL Server neemt de hash-join-bitmap en maakt een nieuwe (veel kleinere) bitmap met behulp van de woordenlijstvermeldingen. Deze nieuwe bitmap wordt toegepast op de segmentgegevens vóór decompressie. De optimalisatie kan worden gecontroleerd met de uitgebreide gebeurtenis column_store_expression_filter_bitmap_set . Wanneer een woordenboekbitmap wordt gebruikt, wordt het gebeurtenislid filter_on_compressed_data_type lid zal worden ingevuld. Meestal bevat dit de waarde RAWBITMAP . Een verdere optimalisatie bestaat om de gecomprimeerde woordenboekbitmap om te zetten in een vergelijkingsfilter als de woordenboekbitmap een enkel aaneengesloten bereik van waarden vertegenwoordigt. In dat geval zie je iets anders dan RAWBITMAP (bijv. LTGT voor een minder dan/groter dan vergelijking).

Uitgebreide gebeurtenissen en traceervlaggen

De algemene mogelijkheid om gepushte filters (inclusief bitmaps gegenereerd door een batchmodus hash-join) op een columnstore-scan in een bitmap te compileren, kan worden uitgeschakeld met traceringsvlag 9361 op sessieniveau. De specifieke bitmapoptimalisatie met gecomprimeerde gegevens kan worden uitgeschakeld met sessie -niveau traceringsvlag 9362. Conversie van een woordenboekbitmap met een enkel aaneengesloten bereik naar een vergelijkingsfilter kan worden uitgeschakeld met traceringsvlag 9363. Helaas zijn er geen traceervlaggen voor de detailhandel die informatieve berichten rapporteren over batchmodus-bitmaps of een ingedrukt filter compilatie.

Er zijn een paar uitgebreide gebeurtenissen die informatie produceren over hash-join batch-modus bitmaps. De handigste zijn:

• query_execution_column_store_segment_scan_started
• query_execution_column_store_segment_scan_finished
• column_store_expression_filter_bitmap_set
• column_store_segment_eliminate

Wanneer een hash-join-batchmodusbitmap naar beneden wordt gedrukt in een columnstore-scan, meldt de gebeurtenis "gestart" BITMAP_SIMPLE of BITMAP_COMPLEX als het filter_type . Het maakt geen onderscheid tussen kleine en grote eenvoudige bitmaps, en rapporteert ook niets over de bereiktabel. De uitgebreide gebeurtenismetagegevens bevatten andere waarden voor column_store_filter_type die BITMAP_SIMPLE_LARGE . bevatten onder andere, maar de uitgebreide gebeurtenis produceert momenteel deze uitvoer niet wanneer een grote eenvoudige bitmap wordt gebruikt. Misschien wordt dit in een toekomstige release gecorrigeerd.

Globale traceervlag 646 kan worden gebruikt om informatie te rapporteren over segmenteliminatie mogelijk gemaakt door de bereiktabel (of een kleine eenvoudige bitmap). Het rapporteert gelijkaardige informatie aan het segment elimineert uitgebreide gebeurtenis. Alle traceervlaggen die in deze sectie worden genoemd, zijn niet gedocumenteerd en worden niet ondersteund.

Laatste gedachten

Bitmaps in batchmodus kunnen uiterst effectief zijn wanneer de juiste gegevenstypen (max. 64 bits en integer-achtig) worden gebruikt en de bitmap kan naar een columnstore-scan worden geduwd, vooral als de segmentgegevens RLE-compressie gebruiken (pure opslag), of als de bitmap kan worden gecompileerd in een andere bitmap op woordenboekgegevens.

Het zou leuk zijn als uitvoeringsplannen meer gedetailleerde informatie over hash-join-bitmaps zouden rapporteren - in ieder geval om te zeggen welk type bitmap is gemaakt. Zoals het is, hebben we alleen de Bitmap Creator eigendom, en enkele uitgebreide evenementen om mee te werken. Dit maakt gedetailleerde plananalyse een beetje moeilijker dan het zou moeten zijn, gezien de enorme prestatieverbeteringen die kunnen worden gerealiseerd door gebruik te maken van alle slimme optimalisaties die in de uitvoeringsengine zijn ingebouwd voor columnstore-gegevens en hash-joins in batchmodus.

Demo's, illustraties en verdere bespreking van de belangrijkste punten die in dit artikel worden besproken, zijn beschikbaar op mijn persoonlijke site op Batch Mode Bitmap-demo's.