Pozadí
V tradičním řádkovém režimu provádění plánů, může SQL Server zavést bitmapový operátor jako součást provádění časného snížení polovičního spojení před paralelním hashem nebo sloučením. Bitmapa je vytvořena ze vstupu sestavení a používá se k filtrování řádků na vstupu sondy, než dosáhnou spojení. Psal jsem o řádkovém režimu bitmapy dříve a jsou také zahrnuty v dokumentaci.
Tento článek je o dávkovém režimu bitmapy, které mají velmi odlišnou implementaci. Od prvního výskytu spouštěcího modulu v dávkovém režimu v SQL Server 2012 došlo k významným vylepšením. Zde uvedené podrobnosti platí pro SQL Server 2017 – poslední vydanou verzi v době psaní tohoto článku. Funkce specifické pro dřívější verze budou zmíněny v textu.
Optimalizátor dotazů
Jediný operátor spojení, který lze spustit v dávkovém režimu, je hash join. Optimalizátor dotazů rozhodne, zda by spojení hash v dávkovém režimu (sériové nebo paralelní) mělo mít bitmapu nebo ne. Optimalizátor vyhodnotí potenciální užitečnost bitmapy výpočtem selektivity hypotetického semi spojení z hash spojovacích vstupů na spojovacích klíčích.
Semi spojení dává smysl, protože funkcí filtrování bitmap je odstranit ze strany sondy řádky, které na straně sestavení neexistují. Pokud je odhadovaná selektivita semi spojení 0,75 nebo méně, optimalizátor považuje za užitečné použít bitmapový filtr v dávkovém režimu. Jinými slovy, bitmapa je specifikována, pokud výpočet semi spojení ukazuje, že 25 % nebo více řádků na straně sondy by bitmapa odstranila.
Přesná selektivita semi spojení se používá pouze k určení, zda má hash spojení mít bitmapu nebo ne. Odhad selektivity na straně sondy (viditelný jako vliv na odhady mohutnosti) je upraven tak, aby odrážel skutečnost, že bitmapy nejsou obecně dokonalé při odstraňování nekvalifikovaných řádků. To je zejména případ, kdy je bitmapa implementována pomocí Bloomova filtru, který může generovat falešné poplachy (řádky na straně sondy, které projdou filtrem, ale přesto se nespojí se stranou sestavení).
Zaokrouhlování selektivity
Optimalizátor bere v úvahu tuto nejistotu zaokrouhlením selektivity polospojení na desetinu. Dělá to tak, že před zaokrouhlením vezme logaritmus se základem 10. Například selektivita semi spojení 0,316 dává log10 hodnota nepatrně pod -0,5, která je zaokrouhlena dolů na -1. Výsledná selektivita na straně sondy je 10 =0,1. Naproti tomu polořadovka spojení selektivita 0,317 dává log10 hodnota těsně nad -0,5, která je zaokrouhlena na nulu. Selektivita na straně sondy je tedy 10 =1 (projdou všechny řady). Možné selektivity bitmapy na straně sondy vyplývající z této řady výpočtů jsou 1, 0,1, 0,01, 0,001 a tak dále. Všimněte si, že bitmapa může být stále používána, když je odhadovaná selektivita zaokrouhlena nahoru na 1 (všechny řádky procházejí predikátem).
Operátoři a odhady mohutnosti
Neexistuje žádná samostatná Bitmapa operátor pro spojení hash v dávkovém režimu. Místo toho má operátor spojení hash buď Bitmap Creator vlastnost (nastavena na true), nebo vlastnost chybí (není nastavena na false). Tento rozdíl mezi prováděním v režimu řádků a v dávkovém režimu usnadňuje sledování, zda se vytváří bitmapa, ale přesněji odráží základní proces:Při provádění v režimu řádků je Bitmapa operátor naplní bitmapu tak, jak přes ni procházejí řádky, jeden po druhém, než dosáhne vstupu sestavení hash join. Jinými slovy, bitmapa a tabulka hash jsou vytvářeny souběžně v režimu řádků. V dávkovém režimu je hašovací tabulka plně sestavena před vytvořením bitmapy (více o tom brzy).
Optimalizátor dotazů neprovádí volby na základě nákladů ohledně pozice bitmapového filtru v dávkovém režimu na straně sondy hash spojení. Jednoduše předpokládá, že selektivita bitmapy bude platit pro všechny podřízené operátory na straně sondy. Ve skutečnosti je bitmapa posunuta dolů na stranu sondy, jakmile optimalizátor vybere jediný konečný plán provádění. Pokud bitmapu nelze posunout úplně dolů k operátoru listu, budou odhady mohutnosti vypadat trochu divně. Toto je kompromis, který by se mohl v budoucnu zlepšit.
Prováděcí modul
Zatímco optimalizátor rozhodne, zda bitmapa v dávkovém režimu hašování by měla být použita nebo ne, o typu rozhoduje spouštěcí modul v dávkovém režimu bitmapy k použití za běhu. Toto rozhodnutí je založeno na statistických informacích shromážděných o klíčích spojení na straně sestavení během sestavení hashovací tabulky. Jak již bylo zmíněno, na rozdíl od provádění v režimu řádků, spojení hašování v dávkovém režimu nejprve kompletně vytvoří hašovací tabulku, než se provede samostatný průchod přes hašovací tabulku za účelem vytvoření bitmapy.
Jednoduché bitmapy
Existují dva hlavní typy bitmapy spojení hash v dávkovém režimu. Jednoduché bitmapa obsahuje jeden bit pro každou ze souvislého rozsahu hodnot na straně sestavení. Jednobajtová jednoduchá bitmapa je například schopna indikovat, zda je přítomno osm souvislých hodnot na straně sestavení či nikoli. Hodnoty 0 až 7 včetně lze do bitmapy zakódovat nastavením odpovídajícího bitu. Hodnota 5 by nastavila bit 5, který má poziční hodnotu 2. Množinu {1, 5, 7} bychom mohli zakódovat jako 2 + 2 + 2 =2 + 32 + 128 =162 =101000102 . Rozsah hodnot, který nezačíná na nule, lze zakódovat stejným způsobem, a to tak, že všechny hodnoty odsadíme o minimální hodnotu přítomnou v sadě (kterou známe ze statistik hashovací tabulky).
Jednoduchá bitmapa má výhodu uložení přesného informace o skutečně přítomných hodnotách na straně sestavení, za cenu potřeby paměti úměrné rozsahu přítomných hodnot.
Složité bitmapy
Druhým typem bitmapy je Bloomův filtr. Tím se nastaví jeden nebo více bitů ve struktuře bitmapy podle výsledku aplikace jedné nebo více hashovacích funkcí na každou hodnotu na straně sestavení. Testujeme shodu použitím stejných hashovacích funkcí na každou hodnotu na straně sondy. Pokud některá z hašovacích funkcí identifikuje bit, který není nastaven, můžeme si být jisti, že se aktuální hodnota sondy neobjeví na straně sestavení.
Protože Bloomův filtr je pravděpodobnostní struktura, nemusíme odfiltrovat některé hodnoty sondy, které nemají shodu na straně sestavení (falešně pozitivní), ale nikdy nevyfiltrujeme hodnotu, která je přítomna (falešně negativní). Jinými slovy, Bloomův filtr nám říká buď „možná se shoduje“ nebo „rozhodně neodpovídá“. Míru falešně pozitivních výsledků lze snížit buď použitím více bitů na klíč (větší bitmapa) nebo více hashovacích funkcí. Aby bylo jasno, filtr Bloom může produkovat přesné filtrování, ale také nemusí.
Bloomovy filtry představují prostorově a časově efektivní alternativu jednoduché bitmapy je z důvodu prostorových nároků neproveditelné. Implementace dávkového režimu SQL Server filtru Bloom je optimalizována pro moderní architektury mezipaměti CPU a je interně známá jako složitá bitmapa . Složité bitmapy podporují více sloupců spojení a všechny datové typy dávkového režimu od SQL Server 2014.
Volba bitmap
Zda SQL Server zvolí jednoduché nebo složité Bitmapa (filtr květu) závisí na rozsahu hodnot na straně sestavení (ze statistik hashovací tabulky). Ke slovu „rozsah“ je zde důležité upozornění, které bude vysvětleno v další části. Mezitím si prováděcí stroj vybírá typ bitmapy takto:
- Malá jednoduchá bitmapa se používá, když je rozsah hodnot 2 (8 388 608) nebo méně. Toto je počet bitů v 1 MB.
- Pokud je rozsah hodnot větší než 2, ale menší nebo roven 2 (8 MB), prováděcí modul zvolí mezi velkou jednoduchou bitmapou a složitá bitmapa výpočtem požadované paměti pro každou možnost a výběrem té menší. Velká jednoduchá bitmapa může mít velikost až 8 MB. Velikost komplexní bitmapy závisí na počtu bitů na klíč potřebných k adekvátní reprezentaci dat. Odlišnější hodnoty obvykle znamenají větší komplexní bitmapu.
- Pokud je rozsah hodnot větší než 2 bity, jedná se o složitou bitmapu se používá.
O rozsahu hodnot
rozsah výše uvedených hodnot je založen na interní binárně reprezentace dat. Například smallint hodnoty 128 a 255 mohou být reprezentovány jako 0x0080 a 0x00FF s rozsahem 0x7F (127) binární hodnoty. Tento rozsah by dobře fungoval s malou jednoduchou bitmapou.
Na druhé straně datetime hodnoty „1900-01-01“ a „1900-01-02“ mohou být reprezentovány v 8 bajtech jako 0x0000000100000000 a 0x0000000200000000 (čtyři bajty pro dny a čtyři bajty pro tikání po půlnoci). Tato segmentovaná reprezentace poskytuje binární rozsah 0x0100000000 (4 294 967 296) pro tyto dvě vzorové hodnoty, což je příliš velké na to, aby se vešlo do jednoduché bitmapy (i velké). Datové typy se složitými binárními reprezentacemi (např. byte-swapping) obvykle nebudou dobře fungovat s jednoduchými bitmapami.
Další komplikací je, že data v dávkovém režimu jsou normalizována — převedeno na binární rozložení, které dobře funguje s vektorizovanými instrukcemi — a má vždy 64 bitů. Hodnoty, které se nevejdou do 64 bitů, jsou uloženy „mimo řádek“ s 64bitovým ukazatelem v řádku. Mimochodem, toto binární rozložení není stejné, jak uvádí převod T-SQL na binární typ.
Nicméně normalizované rozvržení je dostatečně podobné pro celočíselné typy (např. integer a bigint ), že jednoduché bitmapy jsou stále užitečné pro rozsahy těchto datových typů. Jiné typy s binární reprezentací podobnou celému číslu (např. money a date ) jsou také vhodné.
Ještě jeden příklad:Sada integer hodnoty v rozsahu 1 až 8 388 608 budou jen vejde se do 1 MB malé jednoduché bitmapy s použitím jednoho bitu na možnou celočíselnou hodnotu v rozsahu. Rozsah může mít pevný posun, takže by se vešel i rozsah celých čísel od 10 000 000 do 18 388 607 (s posunem deset milionů). Všimněte si, že číslo na přítomných hodnotách nezáleží, jen na rozsahu. Dvě hodnoty 0 a 8 388 607 vyplní malý jednoduchý bitmapový rozsah stejně dobře jako sadu všech možných hodnot mezi těmito dvěma extrémy.
Tabulky rozsahů
Když se modul spouštění v dávkovém režimu rozhodne vytvořit velký jednoduchý bitmapa nebo komplex bitmap pro hash spojení, také vytvoří tabulku rozsahů. Není vytvořit tabulku rozsahů pro malé jednoduché bitmapy.
Tabulka rozsahů je pevná struktura o velikosti 128 kB tvořená 8 192 páry 8bajtových hodnot určujících (nízký, vysoký) rozsah hodnot přítomných v tabulce hash. Tabulku rozsahů lze sestavit na jakémkoli datovém typu kompatibilním s prováděním v dávkovém režimu. Během skenování hotové hash tabulky se každá dávka dat použije k naplnění bitmapy a tabulku rozsahů.
Pro každou hodnotu v dávce se k vyhledání segmentu (dvojice hodnot rozsahu) v tabulce rozsahů používá hašovací funkce. Pokud není segment aktuálně používán, je hodnota uložena v nízké i vysoké 8bajtové hodnotě. Pokud se kbelík již používá, naplní se místo něj další kbelík (a tak dále, dokud se nenajde prázdný kbelík).
Pokud se tabulka rozsahů zaplní z jedné třetiny (2 730 z 8 192 použitých segmentů), použité záznamy se zkopírují, rozsah segmentu se zdvojnásobí a uložené hodnoty se znovu vloží stejným způsobem jako dříve (ačkoli funkce hash bere v úvahu nová velikost kbelíku). Všechny překrývající se segmenty jsou sloučeny a proces zdvojování pokračuje, dokud počet použitých segmentů neklesne pod 2 730. Například dva segmenty, které zpočátku obsahují „rozsahy“ (1-1) a (2-2), se mohou po prvním zdvojnásobení rozsahu sloučit do jednoho segmentu rozsahu (1-2).
Jakmile jsou všechny dávky dat hashovací tabulky zpracovány do tabulky rozsahů, provede se závěrečné sloučení segmentů a poté rychlé třídění na místě seřadí segmenty do hodnotového pořadí. To umožňuje binárním vyhledáváním najít segment rozsahu podle konkrétní hodnoty, která vás zajímá.
Čistým výsledkem celé této činnosti je vytvoření sady až 2 730 různých rozsahů popisujících data v hashovací tabulce (kromě velké jednoduché nebo složité bitmapy).
Použití tabulky rozsahů
Tabulka rozsahů se používá, když je bitmapový filtr spojení hash posunut dolů do operátoru skenování sloupců na straně sondy. Každý segment columnstore má katalogová metadata o minimálních a maximálních hodnotách dat přítomných v segmentu. Prováděcí stroj může tyto informace použít k binárnímu hledání shody v tabulce rozsahu bitmap. Pokud není nalezena žádná shoda, prováděcí modul může segment úplně přeskočit.
Tato optimalizace za běhu se vyskytuje i pro čtení napřed, takže engine se může dokonce vyhnout čtení segmentů do paměti, o kterých ví, že budou eliminovány filtrem tabulky rozsahů. Všechny segmenty, které nejsou eliminovány tabulkou rozsahů, jsou stále filtrovány pomocí bitmapy. Tato kombinace má za následek odstranění maximálního počtu řádků co nejdříve.
Ačkoli tabulka rozsahů není vytvořena pro malou jednoduchou bitmapu, lze tuto strukturu také použít k dosažení eliminace segmentu, protože je znám rozsah hodnot (včetně jakéhokoli offsetu). Je dostatečně malý, aby se nevyplatilo jej rozdělovat do podrozsahů pomocí tabulky rozsahů.
Když bitmapa není posunuta dolů do prohledávání columnstore, může být stále vyhodnocena jako běžný filtr dávkového režimu, aby se dosáhlo snížení semi spojení před spojením hash. To je mnohem méně efektivní než eliminace segmentů nebo filtrování během skenování columnstore, ale stále je to lepší než filtrování na samotném spojení hash.
Bitmapy a komprimovaná data
Použití bitmapy v dávkovém režimu hašovacího spojení na data columnstore jako součást skenování může poskytnout velmi dobrý výkon, ale před použitím bitmapy vyžaduje dekomprimaci nečistých segmentových dat. Tuto dekompresi lze efektivně provést pomocí instrukcí SIMD, ale stále je to práce navíc.
SQL Server 2016 zavedl možnost vytvořit bitmapu pro obecné predikáty na datech segmentů kódovaných ve slovníku. Predikát je vyhodnocen oproti záznamům ve slovníku, aby se vytvořil nový malá bitová mapa s každým nastaveným bitem označujícím položku slovníku, která splňuje predikát. Použití této bitmapy může být extrémně rychlé, zvláště pokud se bitmapa vejde do jednoho registru SIMD. SQL Server může stále používat SIMD, pokud se bitmapa nevejde, ale shromažďování bitů z bitmapy v paměti je o něco méně efektivní než případ v registru.
Tuto optimalizaci pro rok 2016 lze použít na libovolnou predikát vložen do prohledávání columnstore, včetně bitmapového ‚predikátu‘ vytvořeného spojením hash upstream. Aby bylo jasno, SQL Server vezme bitmapu spojení hash a vytvoří novou (mnohem menší) bitmapu pomocí položek slovníku. Tato nová bitmapa se aplikuje na data segmentu před dekompresí. Optimalizaci lze sledovat pomocí rozšířené události column_store_expression_filter_bitmap_set . Když se použije bitmapa slovníku, člen události filter_on_compressed_data_type člen bude vyplněn. Obvykle to bude obsahovat hodnotu RAWBITMAP . Existuje další optimalizace pro převod komprimované slovníkové bitmapy na srovnávací filtr, pokud slovníková bitmapa představuje jediný souvislý rozsah hodnot. V tom případě uvidíte něco jiného než RAWBITMAP (např. LTGT pro srovnání menší/větší než).
Rozšířené události a příznaky trasování
Obecnou schopnost kompilovat posunuté filtry (včetně bitmap generovaných spojením hash v dávkovém režimu) při skenování columnstore do bitmapy lze deaktivovat příznakem trasování na úrovni relace 9361. Specifickou optimalizaci bitmapy komprimovaných dat lze deaktivovat pomocí relace -úroveň příznak trasování 9362. Převod bitmapy slovníku s jedním souvislým rozsahem na srovnávací filtr lze zakázat příznakem trasování 9363. Bohužel neexistují žádné příznaky trasování maloobchodního sestavení, které by hlásily informační zprávy o bitmapách v dávkovém režimu nebo posunutém filtru kompilace.
Existuje několik rozšířených událostí, které vytvářejí informace o bitmapách v dávkovém režimu hašovacího spojení. Nejužitečnější jsou:
query_execution_column_store_segment_scan_startedquery_execution_column_store_segment_scan_finishedcolumn_store_expression_filter_bitmap_setcolumn_store_segment_eliminate
Když je bitmapa v dávkovém režimu hašovacího spojení posunuta dolů do skenování columnstore, událost „started“ hlásí BITMAP_SIMPLE nebo BITMAP_COMPLEX jako filter_type . Nerozlišuje mezi malými a velkými jednoduchými bitmapami ani nehlásí nic o tabulce rozsahů. Rozšířená metadata události obsahují další hodnoty pro column_store_filter_type které zahrnují BITMAP_SIMPLE_LARGE mimo jiné, ale rozšířená událost aktuálně nevytváří tento výstup, když je použita velká jednoduchá bitmapa. Možná to bude opraveno v budoucí verzi.
Globální příznak trasování 646 lze použít k hlášení informací o eliminaci segmentu umožněné tabulkou rozsahů (nebo malou jednoduchou bitmapou). Hlásí podobné informace jako segment eliminující rozšířenou událost. Všechny příznaky trasování uvedené v této části jsou nezdokumentované a nepodporované.
Závěrečné myšlenky
Bitmapy v dávkovém režimu mohou být extrémně účinné, když jsou správné datové typy (maximálně 64 bitů a podobné celému číslu) a bitmapa může být posunuta dolů na skenování columnstore, zejména pokud data segmentu používají kompresi RLE (čisté úložiště), nebo pokud lze bitmapu zkompilovat do jiné bitmapy na datech slovníku.
Mohlo by být hezké, kdyby prováděcí plány uváděly podrobnější informace o bitmapách hash join – alespoň aby bylo řečeno, jaký typ bitmapy byl vytvořen. V současné době máme pouze Tvůrce bitmap majetku a některých rozšířených akcí, se kterými lze pracovat. Díky tomu je podrobná analýza plánu o něco těžší, než by měla být, vzhledem k obrovskému nárůstu výkonu, kterého lze dosáhnout využitím všech chytrých optimalizací zabudovaných do prováděcího enginu pro data columnstore a spojení hash v dávkovém režimu.
Ukázky, ilustrace a další diskuse o hlavních bodech probíraných v tomto článku jsou k dispozici na mém osobním webu na stránce Ukázky bitmap v dávkovém režimu.