Bakgrund
I traditionellt radläge exekveringsplaner, kan SQL Server introducera en Bitmap-operatör som en del av att utföra tidig reduktion av halvanslutning före en parallell hash eller sammanfogning. Bitmappen är konstruerad från build-ingången och används för att filtrera rader på probe-ingången innan de når sammanfogningen. Jag har skrivit om row-mode bitmappar tidigare och de täcks också av dokumentationen.
Den här artikeln handlar om batchläge bitmappar, som har en helt annan implementering. Det har skett stora förbättringar sedan det första uppträdandet av batch-lägesexekveringsmotorn i SQL Server 2012. Detaljerna som ges här gäller SQL Server 2017 — den senast släppta versionen i skrivande stund. Funktioner som är specifika för tidigare versioner kommer att nämnas inline allt eftersom.
Frågeoptimeraren
Den enda join-operatören som kan köras i batch-läge är hash join. Frågeoptimeraren bestämmer om en hash-koppling i batchläge (seriell eller parallell) ska ha en bitmapp eller inte. Optimizern bedömer den potentiella användbarheten av en bitmapp genom att beräkna selektiviteten för en hypotetisk semi-join av hash-join-ingångarna på join-nycklarna.
En semi-join är meningsfull, eftersom funktionen med bitmappsfiltrering är att ta bort rader från sondsidan som inte finns på byggsidan. Om den uppskattade selektiviteten för halvanslutningen är 0,75 eller mindre anser optimeraren att det är värt att använda ett batchlägesbitmappsfilter. Med andra ord specificeras en bitmapp om semi-join-beräkningen indikerar att 25 % eller mer av raderna på probsidan skulle elimineras av bitmappen.
Den exakta semi-join-selektiviteten används bara för att avgöra om hash-join ska ha en bitmapp eller inte. Sondsidans selektivitetsuppskattning (synlig som en effekt på kardinalitetsuppskattningar) är modifierad för att återspegla det faktum att bitmappar i allmänhet inte är perfekta för att ta bort icke-kvalificerade rader. Detta är särskilt fallet när bitmappen är implementerad med hjälp av ett Bloom-filter, som kan generera falska positiva resultat (rader på sondsidan som passerar filtret, men som ändå inte förenas med byggsidan).
Selektivitetsavrundning
Optimeraren tar hänsyn till denna osäkerhet genom att avrunda semi-anslutningsselektiviteten till en potens av tio. Den gör detta genom att ta bas-10-logaritmen före avrundning. Till exempel ger en semi-join-selektivitet på 0,316 en log10 värde bråkdels under -0,5, vilket avrundas nedåt till -1. Den resulterande selektiviteten på probsidan är 10 =0,1. Däremot ger en semi-join-selektivitet på 0,317 en log10 värde strax över -0,5, vilket avrundas till noll. Selektiviteten på probsidan är därför 10 =1 (alla rader passerar). Möjliga bitmappselektiviteter på söksidan som härrör från denna serie av beräkningar är 1, 0,1, 0,01, 0,001 och så vidare. Observera att en bitmapp fortfarande kan användas när den uppskattade selektiviteten avrundas uppåt till 1 (alla rader passerar predikatet).
Operatorer och uppskattningar av kardinalitet
Det finns ingen separat bitmapp operatör för en hash-koppling i batchläge. Istället har hash join-operatören antingen en Bitmap Creator egenskap (inställd på true), eller så saknas egenskapen (inte inställd på false). Denna skillnad mellan exekvering av radläge och batchläge gör det mindre lätt att se om en bitmapp skapas, men den återspeglar mer exakt den underliggande processen:I radlägeskörning är bitmappen operatorn fyller i bitmappen när rader flödar genom den, en i taget, innan den når ingången för hash-join-build. Med andra ord byggs bitmappen och hashtabellen samtidigt under radlägesexekvering. I batch-läge är hashtabellen färdigbyggd innan bitmappen skapas (mer om detta inom kort).
Frågeoptimeraren gör inte kostnadsbaserade val om positionen för ett batchlägesbitmappsfilter på probesidan av hash-join. Den förutsätter helt enkelt att bitmappens selektivitet kommer att gälla för alla underordnade operatörer på sondsidan. I verkligheten skjuts bitmappen bara nedåt på probesidan när en enda slutlig exekveringsplan har valts av optimeraren. Om bitmappen inte kan tryckas hela vägen ner till en bladoperator kommer kardinalitetsuppskattningar att se lite konstiga ut. Detta är en avvägning som kan förbättras i framtiden.
The Execution Engine
Medan optimeraren bestämmer om en bitmapp för hash join batch mode ska användas eller inte, batch mode exekveringsmotorn bestämmer typen av bitmapp att använda vid körning. Detta beslut informeras av statistisk information som samlats in om kopplingsnycklarna på byggsidan under hashtabellbygget. Som tidigare nämnts, i motsats till exekvering i radläge, bygger batch-mode hash joins helt och hållet hashtabellen först, innan en separat passage över hashtabellen utförs för att bygga bitmappen.
Enkla bitmappar
Det finns två huvudtyper av batch-läges-bitmapp med hash-join. En enkel bitmapp innehåller en bit för var och en av ett sammanhängande intervall av värden på byggsidan. Till exempel kan en en-byte enkel bitmapp indikera om åtta sammanhängande värden på byggsidan finns eller inte. Värdena från 0 till 7 kan kodas in i bitmappen genom att ställa in motsvarande bit. Ett värde på 5 skulle sätta bit 5, som har positionsvärdet 2. Vi skulle kunna koda uppsättningen {1, 5, 7} som 2 + 2 + 2 =2 + 32 + 128 =162 =101000102 . Ett värdeintervall som inte börjar på noll kan kodas på samma sätt genom att förskjuta alla värden med det lägsta värde som finns i uppsättningen (vilket vi känner till från statistiken i hashtabellen).
En enkel bitmapp har fördelen att lagra exakt information om de faktiska värdena på byggsidan, till priset av att minnesbehovet är proportionellt mot intervallet av nuvarande värden.
Komplexa bitmappar
Den andra typen av bitmapp är ett Bloom-filter. Detta ställer in en eller flera bitar i bitmappsstrukturen i enlighet med resultatet av applicering av en eller flera hashfunktioner på varje build-side-värde. Vi testar för matchningar genom att tillämpa samma hash-funktioner på varje sondsidevärde. Om någon av hashfunktionerna identifierar en bit som inte är inställd kan vi vara säkra på att det aktuella sondvärdet inte visas på byggsidan.
Eftersom ett Bloom-filter är en probabilistisk struktur kanske vi inte filtrerar bort vissa sondvärden som inte har en matchning på byggsidan (falskt positivt), men vi kommer aldrig att filtrera bort ett värde som finns (falskt negativt). Med andra ord, ett Bloom-filter talar om för oss antingen "kanske en matchning" eller "definitivt inte en matchning". Frekvensen av falska positiva kan minskas antingen genom att använda fler bitar per nyckel (en större bitmapp) eller fler hash-funktioner. För att vara tydlig, kan ett Bloom-filter producera exakt filtrering, men det kanske inte heller.
Bloom-filter utgör ett utrymmes- och tidseffektivt alternativ när en enkel bitmapp är omöjligt på grund av utrymmesbehov. SQL Server-batchlägesimplementeringen av ett Bloom-filter är optimerad för moderna CPU-cachearkitekturer och är internt känd som en komplex bitmapp . Komplexa bitmappar har stöd för flera sammanfogningskolumner och alla datatyper i batchläge sedan SQL Server 2014.
Bitmappsval
Om SQL Server väljer en enkel eller komplex (Bloom filter) bitmapp beror på intervallet av build-side-värden (från hashtabellstatistik). Det finns en viktig varning för ordet "räckvidd" där, som kommer att förklaras i nästa avsnitt. Under tiden är det så här exekveringsmotorn väljer typ av bitmapp:
- En liten enkel bitmapp används när värdeintervallet är 2 (8 388 608) eller mindre. Detta är antalet bitar i 1MB.
- När värdeintervallet är mer än 2 men mindre än eller lika med 2 (8MB), väljer exekveringsmotorn mellan en stor enkel bitmapp och en komplex bitmapp genom att beräkna det nödvändiga minnet för varje alternativ och välja det mindre. En stor enkel bitmapp kan vara upp till 8 MB stor. Storleken på en komplex bitmapp beror på antalet bitar per nyckel som behövs för att representera data på ett adekvat sätt. Mer distinkta värden innebär normalt en större komplex bitmapp.
- Om värdeintervallet är längre än 2 bitar, en komplex bitmapp används.
Om värdeintervallet
intervallet av värden som hänvisas till ovan är baserad på den interna binära representation av uppgifterna. Till exempel, smallint värdena 128 och 255 kan representeras som 0x0080 och 0x00FF , vilket ger ett intervall på 0x7F (127) binära värden. Detta intervall skulle fungera bra med en liten enkel bitmapp.
Å andra sidan, datetime värdena "1900-01-01" och "1900-01-02" kan representeras i 8 byte som 0x0000000100000000 och 0x0000000200000000 (fyra byte för dagar och fyra byte för tick efter midnatt). Denna segmenterade representation ger ett binärt intervall på 0x0100000000 (4 294 967 296) för dessa två exempelvärden, som är alldeles för stora för att passa i en enkel bitmapp (även en stor). Datatyper med komplexa binära representationer (t.ex. byte-byte) fungerar vanligtvis inte bra med enkla bitmappar.
En ytterligare komplikation är att batchlägesdata normaliseras — konverterad till en binär layout som fungerar bra med vektoriserade instruktioner — och är alltid 64 bitar i storlek. Värden som inte får plats i 64 bitar lagras "off row", med en in-rad 64-bitars pekare. Denna binära layout är förresten inte densamma som rapporterats av en T-SQL-konvertering till en binär typ.
Ändå är den normaliserade layouten tillräckligt lika för heltalstyper (t.ex. integer och bigint ) att enkla bitmappar fortfarande är användbara för intervall av dessa datatyper. Andra typer med en heltalsliknande binär representation (t.ex. money och date ) är också lämpliga.
Ytterligare ett exempel:En uppsättning integer värden i intervallet 1 till 8 388 608 kommer bara får plats i en 1MB liten enkel bitmapp, med en bit per möjligt heltalsvärde i intervallet. Området kan ha en fast offset, så ett heltalsintervall på 10 000 000 till 18 388 607 skulle också passa (med en offset på tio miljoner). Observera att numret värdena som finns spelar ingen roll, bara intervallet. Två värden på 0 och 8 388 607 kommer att fylla det lilla enkla bitmappsintervallet lika bra som en uppsättning av alla möjliga värden mellan dessa två ytterligheter.
Räckviddstabeller
När körningsmotorn för batchläge bestämmer sig för att bygga en stor enkel bitmapp eller en komplex bitmapp för en hash-join, den bygger också en intervalltabell. Det gör det inte bygga en intervalltabell för små enkla bitmappar.
Områdestabellen är en struktur på 128 kB med fast storlek som består av 8 192 par av 8-byte-värden som specificerar ett (lågt, högt) område av värden som finns i hashtabellen. En intervalltabell kan byggas på vilken datatyp som helst som är kompatibel med batchlägeskörning. Under genomsökningen av den färdiga hashtabellen används varje batch data för att fylla i bitmappen och intervalltabellen.
För varje värde i batchen används en hash-funktion för att hitta en hink (par av intervallvärden) i intervalltabellen. Om hinken för närvarande inte används lagras värdet i både låga och höga 8-byte-värden. Om hinken redan används, fylls nästa hink istället (och så vidare, tills en tom hink hittas).
Om intervalltabellen blir en tredjedel full (2 730 av 8 192 hinkar används), kopieras de använda posterna ut, hinkintervallet fördubblas, sedan återinförs de sparade värdena på samma sätt som tidigare (även om hashfunktionen tar hänsyn till den nya skopstorleken). Eventuella överlappande skopor slås samman och fördubblingsprocessen fortsätter tills antalet använda skopor faller under 2 730. Till exempel kan två intervaller som initialt innehåller "intervallen" (1-1) och (2-2) slås samman till en enda intervallsektion på (1-2) efter den första intervallfördubblingen.
När alla partier av hashtabelldata har bearbetats till intervalltabellen, utförs en slutlig sammanslagning av hink, sedan placerar en snabbsortering på plats hinkarna i värdeordning. Detta möjliggör en binär sökning för att lokalisera en intervallhink med ett särskilt värde av intresse.
Nettoresultatet av all denna aktivitet är att producera en uppsättning av upp till 2 730 distinkta intervall som beskriver data i hashtabellen (utöver den stora enkla eller komplexa bitmappen).
Använda intervalltabellen
Områdestabellen används när ett bitmappsfilter för hash-join trycks ner i en avsökningsoperator för kolumnarkivet på probesidan. Varje columnstore-segment har katalogmetadata om de lägsta och högsta datavärdena som finns i segmentet. Exekveringsmotorn kan använda denna information för att binärt söka i bitmappstabellen för en matchning. Om ingen matchning hittas kan exekveringsmotorn hoppa över segmentet helt.
Denna körtidsoptimering sker även för framåtläsning, så motorn kan till och med undvika att läsa segment i minnet som den vet kommer att elimineras av intervalltabellfiltret. Alla segment som inte elimineras av intervalltabellen filtreras fortfarande med hjälp av bitmappen. Denna kombination resulterar i att det maximala antalet rader elimineras så tidigt som möjligt.
Även om en intervalltabell inte är byggd för en liten enkel bitmapp, kan den strukturen också användas för att uppnå segmenteliminering eftersom värdeintervallet är känt (inklusive eventuell offset). Den är tillräckligt liten för att göra det inte lönt att dela upp den i underområden med hjälp av en intervalltabell.
När bitmappen inte trycks ner i en kolumnbutiksskanning kan den fortfarande utvärderas som ett vanligt batchlägesfilter för att uppnå semi-join-reduktion innan hash-join. Detta är mycket mindre effektivt än segmenteliminering eller filtrering under kolumnbutiksskanningen, men det är fortfarande bättre än att filtrera vid själva hash-join.
Bitmappar och komprimerad data
Att tillämpa en bitmapp för hash join batch-läge på kolumnlagerdata som en del av skanningen kan ge mycket bra prestanda, men det kräver att oren segmentdata dekomprimeras innan bitmappen kan tillämpas. Denna dekompression kan utföras effektivt med SIMD-instruktioner, men det är fortfarande extraarbete.
SQL Server 2016 introducerade möjligheten att skapa en bitmapp för allmänna predikat på ordbokskodade segmentdata. Predikatet utvärderas mot ordboksposterna för att producera en ny liten bitmapp där varje uppsättning bit indikerar en ordbokspost som uppfyller predikatet. Att tillämpa denna bitmapp kan gå extremt snabbt, speciellt om bitmappen passar i ett enda SIMD-register. SQL Server kan fortfarande använda SIMD om bitmappen inte passar, men att samla in bitar från en bitmapp i minnet är lite mindre effektivt än fallet i registret.
Denna optimering för 2016 kan tillämpas på alla predikat skjuts in i en kolumnbutiksskanning, inklusive ett bitmapps "predikat" skapat av en uppströms hash-join. För att vara tydlig, tar SQL Server hash join-bitmappen och skapar en ny (mycket mindre) bitmapp med hjälp av ordboksposterna. Denna nya bitmapp tillämpas på segmentdata före dekomprimering. Optimeringen kan övervakas med den utökade händelsen column_store_expression_filter_bitmap_set . När en ordboksbitmapp används, händelsemedlemmen filter_on_compressed_data_type medlem kommer att fyllas i. Vanligtvis kommer detta att innehålla värdet RAWBITMAP . En ytterligare optimering existerar för att omvandla den komprimerade ordboksbitmappen till ett jämförelsefilter om ordboksbitmappen representerar ett enda sammanhängande värdeintervall. I så fall kommer du att se något annat än RAWBITMAP (t.ex. LTGT för en mindre än/större än jämförelse).
Utökade händelser och spårningsflaggor
Den allmänna möjligheten att kompilera nedtryckta filter (inklusive bitmappar som genereras av en hash-koppling i batchläge) på en kolumnbutiksskanning till en bitmapp kan inaktiveras med spårningsflagga 9361 på sessionsnivå. Den specifika bitmappsoptimeringen för komprimerad data kan inaktiveras med sessionsnivån. -nivå spårningsflagga 9362. Konvertering av en ordboksbitmapp med ett enda sammanhängande intervall till ett jämförelsefilter kan inaktiveras med spårningsflagga 9363. Det finns tyvärr inga spårningsflaggor från detaljhandeln som rapporterar informationsmeddelanden om batchlägesbitmappar eller nedtryckt filter sammanställning.
Det finns några utökade händelser som producerar information om bitmappar för hash join batch mode. De mest användbara är:
query_execution_column_store_segment_scan_startedquery_execution_column_store_segment_scan_finishedcolumn_store_expression_filter_bitmap_setcolumn_store_segment_eliminate
När en bitmapp för hash join batch-läge trycks ned i en kolumnbutiksskanning, rapporterar händelsen "startad" BITMAP_SIMPLE eller BITMAP_COMPLEX som filter_type . Den skiljer inte mellan små och stora enkla bitmappar och rapporterar inte heller något om intervalltabellen. Den utökade händelsemetadatan innehåller andra värden för column_store_filter_type som inkluderar BITMAP_SIMPLE_LARGE bland annat, men den utökade händelsen producerar för närvarande inte denna utdata när en stor enkel bitmapp används. Kanske kommer detta att rättas till i en framtida version.
Den globala spårningsflaggan 646 kan användas för att rapportera information om segmenteliminering aktiverad av intervalltabellen (eller en liten enkel bitmapp). Den rapporterar liknande information till segmentet eliminera utökad händelse. Alla spårningsflaggor som nämns i det här avsnittet är odokumenterade och stöds inte.
Slutliga tankar
Bitmaps i batchläge kan vara extremt effektiva när rätt datatyper är (max 64 bitar och heltalsliknande) används och bitmappen kan tryckas ner till en kolumnlagerskanning, speciellt om segmentdatan använder RLE-komprimering (ren lagring), eller om bitmappen kan kompileras till en annan bitmapp på ordboksdata.
Det kan vara trevligt om exekveringsplaner rapporterade mer detaljerad information om bitmappar för hash join - åtminstone för att säga vilken typ av bitmapp som skapades. Som det är har vi bara Bitmap Creator egendom och några utökade evenemang att arbeta med. Detta gör detaljerad plananalys lite svårare än det borde vara, med tanke på de enorma prestandavinster som kan uppnås genom att dra fördel av alla smarta optimeringar som är inbyggda i exekveringsmotorn för kolumnlagerdata och hash-kopplingar i batchläge.
Demos, illustrationer och ytterligare diskussioner om huvudpunkterna som diskuteras i den här artikeln finns tillgängliga på min personliga sida på Batch Mode Bitmap Demos.