Baggrund
I traditionel rækketilstand eksekveringsplaner, kan SQL Server introducere en Bitmap-operatør som en del af at udføre tidlig semi join-reduktion før en parallel hash eller merge join. Bitmap'et er konstrueret ud fra build-inputtet og bruges til at filtrere rækker på sonde-inputtet, før de når sammenføjningen. Jeg har skrevet om row-mode bitmaps før, og de er også dækket af dokumentationen.
Denne artikel handler om batch-tilstand bitmaps, som har en meget anderledes implementering. Der er sket store forbedringer siden den første optræden af batch-mode-udførelsesmotoren i SQL Server 2012. De detaljer, der gives her, gælder for SQL Server 2017 - den senest udgivne version i skrivende stund. Funktioner, der er specifikke for tidligere versioner, vil blive nævnt inline, efterhånden som vi går videre.
Forespørgselsoptimeringsværktøjet
Den eneste join-operatør, der kan køre i batch-tilstand, er hash join. Forespørgselsoptimeringsværktøjet bestemmer, om en batch-mode hash join (seriel eller parallel) skal have en bitmap eller ej. Optimeringsværktøjet vurderer den potentielle nytte af en bitmap ved at beregne selektiviteten af en hypotetisk semi join af hash join-indgangene på join-nøglen(e).
En semi-join giver mening, fordi bitmapfiltreringens funktion er at fjerne rækker fra probesiden, som ikke findes på buildsiden. Hvis den estimerede selektivitet af semi-sammenføjningen er 0,75 eller mindre, anser optimeringsværktøjet det for umagen værd at bruge et batch-tilstand bitmapfilter. Med andre ord angives en bitmap, hvis semi-sammenføjningsberegningen indikerer, at 25 % eller flere af rækkerne på sondesiden ville blive elimineret af bitmappet.
Den nøjagtige semi-join-selektivitet bruges kun til at bestemme, om hash-joinet skal have en bitmap eller ej. Probesideselektivitetsestimatet (synligt som en effekt på kardinalitetsestimater) er modificeret for at afspejle det faktum, at bitmaps generelt ikke er perfekte til at fjerne ikke-kvalificerede rækker. Dette er især tilfældet, når bitmap'et er implementeret ved hjælp af et Bloom-filter, som kan generere falske positiver (rækker på sondesiden, der passerer filteret, men ikke desto mindre ikke forbinder med build-siden).
Selektivitetsafrunding
Optimizeren tager højde for denne usikkerhed ved at afrunde semi join-selektiviteten til en potens på ti. Det gør den ved at tage base-10-logaritmen før afrunding. For eksempel giver en semi join-selektivitet på 0,316 en log10 værdi brøkdele under -0,5, hvilket rundes ned til -1. Den resulterende probesideselektivitet er 10 =0,1. Derimod giver en semi join-selektivitet på 0,317 en log10 værdi lige over -0,5, som er afrundet til nul. Selektiviteten på probesiden er derfor 10 =1 (alle rækker passerer). Mulige bitmapselektiviteter på probesiden, der er et resultat af denne serie af beregninger, er 1, 0,1, 0,01, 0,001 og så videre. Bemærk, at en bitmap stadig kan bruges, når den estimerede selektivitet er rundet op til 1 (alle rækker passerer prædikatet).
Operatører og kardinalitetsestimater
Der er ingen separat Bitmap operatør for en batch mode hash join. I stedet har hash join-operatøren enten en Bitmap Creator egenskab (sat til sand), eller egenskaben mangler (ikke sat til falsk). Denne forskel mellem rækketilstand og udførelse af batchtilstand gør det mindre let at se, om der oprettes en bitmap, men den afspejler mere præcist den underliggende proces:I rækketilstandsudførelse er Bitmap operatoren udfylder bitmap'et, efterhånden som rækker flyder gennem det, én ad gangen, før den når hash join build-inputtet. Med andre ord bygges bitmap- og hashtabellen samtidigt under udførelse af rækketilstand. I batch-tilstand er hash-tabellen fuldt bygget, før bitmap'et oprettes (mere om dette snart).
Forespørgselsoptimeringsværktøjet foretager ikke omkostningsbaserede valg om placeringen af et batch-tilstand bitmapfilter på probesiden af hash-joinet. Det antager simpelthen, at selektiviteten af bitmap'et vil gælde for alle underordnede operatører på sondesiden. I virkeligheden skubbes bitmappet kun ned ad sondesiden, når en enkelt endelig udførelsesplan er blevet valgt af optimeringsværktøjet. Hvis bitmap'et ikke kan skubbes helt ned til en bladoperator, vil kardinalitetsestimater se lidt mærkelige ud. Dette er en afvejning, der kan blive forbedret i fremtiden.
Execution Engine
Mens optimeringsværktøjet bestemmer om en hash join batch mode bitmap skal bruges eller ej, batch mode eksekveringsmotoren bestemmer typen af bitmap til brug under kørsel. Denne beslutning er informeret af statistisk information indsamlet om build-side join-nøglerne under hash-tabellen build. Som tidligere nævnt, i modsætning til rækketilstandsudførelse, bygger batch-mode hash joins fuldstændigt opbygge hash-tabellen først, før en separat passage over hash-tabellen udføres for at bygge bitmap.
Simple bitmaps
Der er to hovedtyper af batch mode hash join bitmap. En simpel bitmap indeholder en bit for hver af et sammenhængende område af build-side værdier. For eksempel er en simpel bitmap på én byte i stand til at angive, om otte sammenhængende build-side-værdier er til stede eller ej. Værdierne 0 til 7 inklusive kan indkodes i bitmap ved at indstille den tilsvarende bit. En værdi på 5 ville sætte bit 5, som har positionsværdien 2. Vi kunne kode sættet {1, 5, 7} som 2 + 2 + 2 =2 + 32 + 128 =162 =101000102 . En række værdier, der ikke starter ved nul, kan kodes på samme måde ved at forskyde alle værdier med minimumsværdien i sættet (som vi kender fra hash-tabellens statistik).
En simpel bitmap har den fordel, at den gemmer nøjagtig oplysninger om de faktisk tilstedeværende værdier på byggesiden, på bekostning af at kræve hukommelse proportional med området af tilstedeværende værdier.
Komplekse bitmaps
Den anden type bitmap er et Bloom-filter. Dette indstiller en eller flere bits i bitmapstrukturen i overensstemmelse med resultatet af at anvende en eller flere hash-funktioner til hver build-side-værdi. Vi tester for matches ved at anvende de samme hash-funktioner på hver probe-sideværdi. Hvis nogen af hash-funktionerne identificerer en bit, der ikke er indstillet, kan vi være sikre på, at den aktuelle probeværdi ikke vises på byggesiden.
Da et Bloom-filter er en sandsynlighedsstruktur, vil vi muligvis ikke bortfiltrere nogle probeværdier, der ikke har en build-side-match (falsk positiv), men vi vil aldrig bortfiltrere en værdi, der er til stede (falsk negativ). Med andre ord fortæller et Bloom-filter os enten "måske et match" eller "bestemt ikke et match". Raten af falske positiver kan reduceres enten ved at bruge flere bits pr. nøgle (en større bitmap) eller flere hash-funktioner. For at være klar, kan et Bloom-filter producere nøjagtig filtrering, men det er måske heller ikke.
Bloom-filtre præsenterer et plads- og tidseffektivt alternativ, når en simpel bitmap er umuligt på grund af pladsbehov. SQL Server-batchtilstandsimplementeringen af et Bloom-filter er optimeret til moderne CPU-cache-arkitekturer og er internt kendt som en kompleks bitmap . Komplekse bitmaps har understøttet flere joinkolonner og alle batch-tilstandsdatatyper siden SQL Server 2014.
Bitmapvalg
Om SQL Server vælger en simpel eller kompleks (Bloom-filter) bitmap afhænger af området af build-side værdier (fra hash tabel statistik). Der er en vigtig advarsel til ordet "rækkevidde", som vil blive forklaret i næste afsnit. I mellemtiden er det sådan, udførelsesmotoren vælger typen af bitmap:
- En lille simpel bitmap bruges, når værdiintervallet er 2 (8.388.608) eller mindre. Dette er antallet af bits i 1 MB.
- Når værdiintervallet er mere end 2, men mindre end eller lig med 2 (8MB), vælger udførelsesmotoren mellem en stor simpel bitmap og en kompleks bitmap ved at beregne den nødvendige hukommelse for hver mulighed og vælge den mindste. En stor simpel bitmap kan være op til 8MB i størrelse. Størrelsen af en kompleks bitmap afhænger af antallet af bits pr. nøgle, der er nødvendige for at repræsentere dataene korrekt. Mere distinkte værdier betyder normalt en større kompleks bitmap.
- Hvis værdiintervallet er ud over 2 bit, er en kompleks bitmap bruges.
Om intervallet af værdier
udvalget af værdier nævnt ovenfor er baseret på den interne binære repræsentation af data. For eksempel smallint værdierne 128 og 255 kan være repræsenteret som 0x0080 og 0x00FF , hvilket giver et interval på 0x7F (127) binære værdier. Dette interval ville fungere godt med en lille simpel bitmap.
På den anden side er datetime værdierne "1900-01-01" og "1900-01-02" kan være repræsenteret i 8 bytes som 0x0000000100000000 og 0x0000000200000000 (fire bytes for dage og fire bytes for kryds efter midnat). Denne segmenterede repræsentation giver et binært interval på 0x0100000000 (4.294.967.296) for disse to eksempelværdier, som er alt for store til at passe ind i en simpel bitmap (selv en stor). Datatyper med komplekse binære repræsentationer (f.eks. byte-swapping) vil typisk ikke fungere godt med simple bitmaps.
En yderligere komplikation er, at batchtilstandsdata normaliseres — konverteret til et binært layout, der fungerer godt med vektoriserede instruktioner — og altid er 64 bit i størrelse. Værdier, der ikke kan passe i 64 bit, gemmes "off row", med en in-row 64-bit pointer. Dette binære layout er i øvrigt ikke det samme som rapporteret ved en T-SQL-konvertering til en binær type.
Ikke desto mindre er det normaliserede layout ens nok til heltalstyper (f.eks. integer og bigint ), at simple bitmaps stadig er nyttige til områder af disse datatyper. Andre typer med en heltalslignende binær repræsentation (f.eks. money og date ) er også egnede.
Endnu et eksempel:Et sæt integer værdier i området 1 til 8.388.608 vil bare passer ind i en 1MB lille simpel bitmap, der bruger en bit pr. mulig heltalsværdi i området. Området kan have en fast offset, så et heltalsområde på 10.000.000 til 18.388.607 ville også passe (med en offset på ti millioner). Bemærk, at nummeret af tilstedeværende værdier er ligegyldigt, kun rækkevidden. To værdier på 0 og 8.388.607 vil fylde det lille simple bitmapområde lige så godt som et sæt af alle mulige værdier mellem disse to yderpunkter.
Rangetabeller
Når batch-mode-udførelsesmotoren beslutter at bygge en stor enkel bitmap eller et kompleks bitmap for en hash-join, den bygger også en rækkeviddetabel. Det gør ikke opbyg en intervaltabel til lille simple bitmaps.
Områdetabellen er en struktur på 128 KB i fast størrelse, der består af 8.192 par 8-byte værdier, der specificerer et (lavt, højt) område af værdier, der findes i hashtabellen. En intervaltabel kan bygges på enhver datatype, der er kompatibel med batch-mode-udførelse. Under scanningen af den færdige hash-tabel bruges hver batch af data til at udfylde bitmap'et og rækkeviddetabellen.
For hver værdi i batchen bruges en hash-funktion til at finde en bucket (par af intervalværdier) i intervaltabellen. Hvis bøtten er ubrugt i øjeblikket, gemmes værdien i både lave og høje 8-byte værdier. Hvis spanden allerede er i brug, fyldes den næste spand i stedet (og så videre, indtil en tom spand findes).
Hvis rækkeviddetabellen bliver en tredjedel fuld (2.730 af 8.192 brugte buckets), kopieres de brugte poster ud, bucket-området fordobles, derefter genindsættes de gemte værdier på samme måde som før (selvom hash-funktionen tager højde for den nye spandstørrelse). Eventuelle overlappende skovle slås sammen, og fordoblingsprocessen fortsætter, indtil antallet af brugte skovle falder til under 2.730. For eksempel kan to buckets, der oprindeligt indeholder "intervallerne" (1-1) og (2-2), smelte sammen til en enkelt interval-bucket på (1-2) efter den første intervalfordobling.
Når alle batches af hash-tabeldata er blevet behandlet i intervaltabellen, udføres en endelig bucket-fletning, hvorefter en in-place quicksort placerer buckets i værdirækkefølge. Dette giver mulighed for en binær søgning for at lokalisere en rækkevidde med en bestemt værdi af interesse.
Nettoresultatet af al denne aktivitet er at producere et sæt på op til 2.730 forskellige områder, der beskriver dataene i hash-tabellen (ud over den store simple eller komplekse bitmap).
Brug af rækkeviddetabellen
Områdetabellen bruges, når et hash join-bitmapfilter skubbes ned i en scanningsoperator for kolonnelager på probesiden. Hvert kolonnelagersegment har katalogmetadata om minimums- og maksimumsdataværdierne i segmentet. Eksekveringsmotoren kan bruge denne information til at binært søge i bitmapområdets tabel for et match. Hvis der ikke findes noget match, kan eksekveringsmotoren springe segmentet helt over.
Denne kørselstidsoptimering forekommer også for read-ahead, så motoren kan endda undgå at læse segmenter ind i hukommelsen, som den ved vil blive elimineret af range-tabelfilteret. Alle segmenter, der ikke er elimineret af rækketabellen, filtreres stadig ved hjælp af bitmap. Denne kombination resulterer i, at det maksimale antal rækker elimineres så tidligt som muligt.
Selvom en intervaltabel ikke er bygget til en lille simpel bitmap, kan den struktur også bruges til at opnå segmenteliminering, fordi rækkevidden af værdier er kendt (inklusive enhver offset). Den er lille nok til at gøre det ikke umagen værd at opdele det i underområder ved hjælp af en områdetabel.
Når bitmap'et ikke er skubbet ned i en columnstore-scanning, kan det stadig evalueres som et almindeligt batch-mode-filter for at opnå semi-join-reduktion før hash-join. Dette er meget mindre effektivt end segmenteliminering eller filtrering under columnstore-scanningen, men det er stadig bedre end at filtrere ved selve hash-sammenføjningen.
Bitmaps og komprimerede data
Anvendelse af en hash join-batch-tilstand bitmap til kolonnelagerdata som en del af scanningen kan give meget god ydeevne, men det kræver, at urene segmentdata dekomprimeres, før bitmap'en kan anvendes. Denne dekompression kan udføres effektivt ved hjælp af SIMD-instruktioner, men det er stadig ekstra arbejde.
SQL Server 2016 introducerede muligheden for at oprette en bitmap for generelle prædikater på ordbogskodede segmentdata. Prædikatet evalueres i forhold til ordbogsposterne for at producere en ny lille bitmap, hvor hver sæt bit angiver en ordbogsindgang, der opfylder prædikatet. Det kan være ekstremt hurtigt at anvende denne bitmap, især hvis bitmap'et passer i et enkelt SIMD-register. SQL Server kan stadig bruge SIMD, hvis bitmap'et ikke passer, men at samle bits fra en bitmap i hukommelsen er en smule mindre effektiv end tilfældet i registeret.
Denne 2016-optimering kan anvendes på enhver prædikat skubbet ind i en columnstore-scanning, inklusive et bitmap "prædikat" oprettet af en upstream hash join. For at være klar, tager SQL Server hash join-bitmap og opretter en ny (meget mindre) bitmap ved hjælp af ordbogsposterne. Denne nye bitmap anvendes på segmentdataene før dekomprimering. Optimeringen kan overvåges med den udvidede hændelse column_store_expression_filter_bitmap_set . Når en ordbog bitmap bruges, hændelsesmedlemmet filter_on_compressed_data_type medlem vil blive udfyldt. Normalt vil dette indeholde værdien RAWBITMAP . En yderligere optimering eksisterer for at konvertere den komprimerede ordbogs bitmap til et sammenligningsfilter, hvis ordbogens bitmap repræsenterer et enkelt sammenhængende område af værdier. I så fald vil du se noget andet end RAWBITMAP (f.eks. LTGT for en mindre end/større end sammenligning).
Udvidede begivenheder og sporingsflag
Den generelle evne til at kompilere push-down filtre (inklusive bitmaps genereret af en batch mode hash join) på en columnstore scanning til en bitmap kan deaktiveres med sporingsflag 9361 på sessionsniveau. Den specifikke bitmapoptimering af komprimerede data kan deaktiveres med session -niveau sporingsflag 9362. Konvertering af en ordbogs bitmap med et enkelt sammenhængende område til et sammenligningsfilter kan deaktiveres med sporingsflag 9363. Der er desværre ingen detail-build sporingsflag, der rapporterer informationsmeddelelser om batch mode bitmaps eller push-down filter kompilering.
Der er et par udvidede begivenheder, der producerer information om hash join batch mode bitmaps. De mest nyttige er:
query_execution_column_store_segment_scan_startedquery_execution_column_store_segment_scan_finishedcolumn_store_expression_filter_bitmap_setcolumn_store_segment_eliminate
Når en hash join batch mode bitmap skubbes ned i en columnstore scanning, rapporterer "started" begivenheden BITMAP_SIMPLE eller BITMAP_COMPLEX som filter_type . Den skelner ikke mellem små og store simple bitmaps, og den rapporterer heller ikke noget om rækkeviddetabellen. De udvidede hændelsesmetadata indeholder andre værdier for column_store_filter_type der inkluderer BITMAP_SIMPLE_LARGE blandt andet, men den udvidede hændelse producerer i øjeblikket ikke dette output, når der bruges en stor simpel bitmap. Måske vil dette blive rettet i en fremtidig udgivelse.
Globalt sporingsflag 646 kan bruges til at rapportere information om segmenteliminering aktiveret af intervaltabellen (eller en lille simpel bitmap). Den rapporterer lignende oplysninger til segmentet eliminere udvidet hændelse. Alle sporingsflag nævnt i dette afsnit er udokumenterede og ikke understøttede.
Sidste tanker
Batch-tilstand bitmaps kan være ekstremt effektive, når de rigtige datatyper (max 64 bit og heltalslignende) bruges og bitmap kan skubbes ned til en columnstore scanning, især hvis segmentdata anvender RLE komprimering (ren lagring), eller hvis bitmap kan kompileres til en anden bitmap på ordbogsdata.
Det kunne være rart, hvis udførelsesplaner rapporterede mere detaljerede oplysninger om hash join bitmaps - i det mindste for at sige, hvilken type bitmap der blev oprettet. Som det er, har vi kun Bitmap Creator ejendom og nogle udvidede arrangementer at arbejde med. Dette gør detaljeret plananalyse en smule sværere, end det burde være, i betragtning af de enorme præstationsgevinster, der kan opnås ved at udnytte alle de smarte optimeringer, der er indbygget i udførelsesmotoren til kolonnelagerdata og batch-mode hash joins.
Demoer, illustrationer og yderligere diskussion af de vigtigste punkter, der diskuteres i denne artikel, er tilgængelige på min personlige side på Batch Mode Bitmap Demoer.