Tło
W tradycyjnym trybie wiersza planów wykonania, SQL Server może wprowadzić operator Bitmap w ramach wykonywania wczesnej redukcji częściowych sprzężeń przed równoległym połączeniem mieszającym lub scalającym. Mapa bitowa jest tworzona na podstawie danych wejściowych kompilacji i służy do filtrowania wierszy w danych wejściowych sondy, zanim dotrą do sprzężenia. Pisałem o trybie wierszowym bitmapy wcześniej i są one również omówione w dokumentacji.
Ten artykuł dotyczy trybu wsadowego bitmapy, które mają bardzo różną implementację. Od czasu pierwszego pojawienia się silnika wykonywania w trybie wsadowym w SQL Server 2012 wprowadzono znaczne ulepszenia. Podane tutaj szczegóły dotyczą SQL Server 2017 — najnowszej wersji wydanej w momencie pisania tego tekstu. Funkcje specyficzne dla wcześniejszych wersji będą wymienione w tekście w miarę postępów.
Optymalizator zapytań
Jedynym operatorem łączenia, który może działać w trybie wsadowym, jest łączenie mieszające. Optymalizator zapytań decyduje, czy łączenie mieszające w trybie wsadowym (szeregowe lub równoległe) powinno mieć mapę bitową, czy nie. Optymalizator ocenia potencjalną przydatność mapy bitowej, obliczając selektywność hipotetycznego połączenia częściowego wejść hash join na kluczach łączenia.
Semi join ma sens, ponieważ funkcją filtrowania bitmap jest usuwanie wierszy ze strony sondy, które nie istnieją po stronie kompilacji. Jeśli szacowana selektywność częściowego sprzężenia wynosi 0,75 lub mniej, optymalizator uważa, że warto użyć filtru bitmapowego trybu wsadowego. Innymi słowy, bitmapa jest określona, jeśli obliczenia sprzężenia częściowego wskazują, że 25% lub więcej wierszy po stronie sondy zostałoby wyeliminowanych przez bitmapę.
Dokładna selektywność sprzężenia semi jest używana tylko do określenia, czy sprzężenie mieszające powinno mieć mapę bitową, czy nie. Oszacowanie selektywności po stronie sondy (widoczne jako wpływ na oszacowania kardynalności) jest modyfikowane w celu odzwierciedlenia faktu, że mapy bitowe nie są generalnie doskonałe w usuwaniu niekwalifikowanych wierszy. Dzieje się tak szczególnie w przypadku, gdy bitmapa jest implementowana przy użyciu filtra Bloom, który może generować fałszywe alarmy (wiersze po stronie sondy, które przechodzą przez filtr, ale mimo to nie łączą się ze stroną kompilacji).
Zaokrąglanie selektywności
Optymalizator uwzględnia tę niepewność, zaokrąglając selektywność sprzężenia semi do potęgi dziesiątej. Robi to, biorąc logarytm dziesiętny przed zaokrągleniem. Na przykład selektywność semi-join wynosząca 0,316 daje log10 wartość ułamkowo poniżej -0,5, co jest zaokrąglane w dół do -1. Otrzymana selektywność po stronie sondy wynosi 10 =0,1. Natomiast selektywność semi-join wynosząca 0,317 daje log10 wartość nieco powyżej -0,5, która jest zaokrąglana do zera. Selektywność po stronie sondy wynosi zatem 10 =1 (wszystkie rzędy pasują). Możliwe selektywności bitmapy po stronie sondy wynikające z tej serii obliczeń to 1, 0,1, 0,01, 0,001 i tak dalej. Zauważ, że bitmapa może być nadal używana, gdy szacowana selektywność jest zaokrąglana do 1 (wszystkie wiersze przechodzą przez predykat).
Oszacowania operatorów i liczności
Nie ma oddzielnej bitmapy operator dla łączenia mieszającego w trybie wsadowym. Zamiast tego operator łączenia mieszającego ma albo Twórcę bitmap właściwość (ustawiona na true) lub brak właściwości (nie jest ustawiona na false). Ta różnica między wykonywaniem w trybie wiersza a trybem wsadowym sprawia, że trudniej jest sprawdzić, czy bitmapa jest tworzona, ale dokładniej odzwierciedla proces leżący u podstaw:W przypadku wykonywania w trybie wiersza Bitmapa operator wypełnia mapę bitową, gdy przepływają przez nią wiersze, po jednym na raz, przed osiągnięciem danych wejściowych kompilacji łączenia mieszającego. Innymi słowy, bitmapa i tablica mieszająca są budowane jednocześnie w trybie wykonywania w trybie wierszowym. W trybie wsadowym tablica mieszająca jest w pełni budowana przed utworzeniem mapy bitowej (więcej o tym wkrótce).
Optymalizator zapytań nie dokonuje wyborów opartych na kosztach dotyczących pozycji filtru mapy bitowej trybu wsadowego po stronie sondy sprzężenia mieszającego. Po prostu zakłada, że selektywność mapy bitowej będzie miała zastosowanie do wszystkich operatorów podrzędnych po stronie sondy. W rzeczywistości mapa bitowa jest przesuwana po stronie sondy dopiero po wybraniu przez optymalizator jednego ostatecznego planu wykonania. Jeśli bitmapy nie można przesunąć do samego operatora liścia, oszacowania kardynalności będą wyglądać nieco dziwnie. Jest to kompromis, który może zostać poprawiony w przyszłości.
Silnik wykonawczy
Podczas gdy optymalizator decyduje, czy powinna być używana mapa bitowa trybu wsadowego łączenia haszującego, mechanizm wykonywania w trybie wsadowym decyduje o typie bitmapy do użycia w czasie wykonywania. Ta decyzja jest podejmowana na podstawie informacji statystycznych zebranych na temat kluczy łączenia po stronie kompilacji podczas budowania tabeli mieszającej. Jak wspomniano wcześniej, w przeciwieństwie do wykonywania w trybie wierszowym, sprzężenia mieszające w trybie wsadowym najpierw całkowicie budują tablicę mieszającą, zanim zostanie wykonane oddzielne przejście nad tablicą mieszającą w celu zbudowania mapy bitowej.
Proste mapy bitowe
Istnieją dwa główne typy bitmap łączenia mieszającego w trybie wsadowym. Prosty bitmapa zawiera jeden bit dla każdego z ciągłego zakresu wartości po stronie kompilacji. Na przykład prosta jednobajtowa mapa bitowa może wskazywać, czy istnieje osiem ciągłych wartości po stronie kompilacji, czy nie. Wartości od 0 do 7 włącznie można zakodować w mapie bitowej przez ustawienie odpowiedniego bitu. Wartość 5 ustawi bit 5, który ma wartość pozycyjną równą 2. Możemy zakodować zbiór {1, 5, 7} jako 2 + 2 + 2 =2 + 32 + 128 =162 =101000102 . Zakres wartości, który nie zaczyna się od zera, można zakodować w ten sam sposób, odsuwając wszystkie wartości o minimalną wartość obecną w zestawie (którą znamy ze statystyk tablicy mieszającej).
Prosta mapa bitowa ma tę zaletę, że przechowuje dokładne informacje o faktycznie obecnych wartościach po stronie kompilacji, kosztem wymagania pamięci proporcjonalnej do zakresu obecnych wartości.
Złożone mapy bitowe
Drugim rodzajem bitmapy jest filtr Bloom. Ustawia to jeden lub więcej bitów w strukturze bitmapy zgodnie z wynikiem zastosowania jednej lub więcej funkcji skrótu do każdej wartości po stronie kompilacji. Testujemy dopasowania, stosując te same funkcje skrótu do każdej wartości po stronie sondy. Jeśli którakolwiek z funkcji mieszających zidentyfikuje bit, który nie jest ustawiony, możemy być pewni, że bieżąca wartość sondy nie pojawi się po stronie kompilacji.
Ponieważ filtr Blooma jest strukturą probabilistyczną, możemy nie odfiltrować niektórych wartości sondy, które nie mają dopasowania po stronie kompilacji (fałszywie dodatnie), ale nigdy nie odfiltrujemy wartości, która jest obecna (fałszywie ujemne). Innymi słowy, filtr Bloom mówi nam albo „może pasuje” albo „zdecydowanie nie pasuje”. Częstość fałszywych alarmów można zmniejszyć, używając większej liczby bitów na klucz (większa mapa bitowa) lub większej liczby funkcji mieszających. Aby było jasne, filtr Bloom może zapewnia dokładne filtrowanie, ale może też nie.
Filtry Bloom stanowią alternatywę efektywną pod względem przestrzeni i czasu, gdy prosta mapa bitowa jest niewykonalne ze względu na wymagania przestrzenne. Implementacja filtra Bloom w trybie wsadowym SQL Server jest zoptymalizowana pod kątem nowoczesnych architektur pamięci podręcznej procesora i jest znana wewnętrznie jako złożona mapa bitowa . Złożone mapy bitowe obsługują wiele kolumn sprzężeń i wszystkie typy danych w trybie wsadowym od SQL Server 2014.
Wybór bitmapy
Czy SQL Server wybiera prosty lub złożony (Filtr rozkwitu) bitmapa zależy od zakresu wartości po stronie kompilacji (ze statystyk tablic mieszających). Istnieje ważne zastrzeżenie dotyczące słowa „zakres”, które zostanie wyjaśnione w następnej sekcji. Tymczasem tak silnik wykonawczy wybiera typ bitmapy:
- Mała prosta bitmapa jest używany, gdy zakres wartości wynosi 2 (8 388 608) lub mniej. To jest liczba bitów w 1MB.
- Gdy zakres wartości jest większy niż 2, ale mniejszy lub równy 2 (8 MB), silnik wykonawczy wybiera między dużą prostą mapą bitową i złożoną bitmapę obliczając wymaganą pamięć dla każdej opcji i wybierając mniejszą. Duża prosta bitmapa może mieć rozmiar do 8 MB. Rozmiar złożonej mapy bitowej zależy od liczby bitów na klucz potrzebnych do odpowiedniego przedstawienia danych. Bardziej wyraźne wartości zwykle oznaczają większą złożoną bitmapę.
- Jeśli zakres wartości przekracza 2 bity, złożona mapa bitowa jest używany.
O zakresie wartości
zakres wartości, o których mowa powyżej, opiera się na wewnętrznym pliku binarnym reprezentacja danych. Na przykład smallint wartości 128 i 255 mogą być reprezentowane jako 0x0080 i 0x00FF , dając zakres 0x7F (127) wartości binarne. Ten zakres działałby dobrze z małą prostą mapą bitową.
Z drugiej strony datetime wartości „1900-01-01” i „1900-01-02” mogą być reprezentowane w 8 bajtach jako 0x0000000100000000 i 0x0000000200000000 (cztery bajty dla dni i cztery bajty dla tików po północy). Ta podzielona na segmenty reprezentacja daje binarny zakres 0x0100000000 (4 294 967 296) dla tych dwóch przykładowych wartości, co jest zbyt duże, aby zmieścić się w prostej bitmapie (nawet dużej). Typy danych ze złożonymi reprezentacjami binarnymi (np. zamiana bajtów) zazwyczaj nie będą działać dobrze z prostymi mapami bitowymi.
Kolejną komplikacją jest to, że dane w trybie wsadowym są normalizowane — przekonwertowany na układ binarny, który działa dobrze z instrukcjami wektorowymi — i zawsze ma rozmiar 64 bity. Wartości, które nie mieszczą się w 64 bitach, są przechowywane „poza wierszem” z 64-bitowym wskaźnikiem w wierszu. Nawiasem mówiąc, ten układ binarny nie jest taki sam, jak raportowany przez konwersję T-SQL na typ binarny.
Niemniej jednak znormalizowany układ jest wystarczająco podobny dla typów całkowitych (np. integer i bigint ), że proste mapy bitowe są nadal przydatne dla zakresów tych typów danych. Inne typy z reprezentacją binarną zbliżoną do liczb całkowitych (np. money i date ) są również odpowiednie.
Jeszcze jeden przykład:zbiór integer wartości z zakresu od 1 do 8 388 608 będą tylko zmieścić w małej, prostej bitmapie o wielkości 1 MB, używając jednego bitu na możliwą wartość całkowitą w zakresie. Zakres może mieć stałe przesunięcie, więc pasowałby również zakres liczb całkowitych od 10 000 000 do 18 388 607 (z przesunięciem wynoszącym dziesięć milionów). Zwróć uwagę, że liczba obecnych wartości nie ma znaczenia, tylko zakres. Dwie wartości 0 i 8 388 607 wypełnią mały prosty zakres bitmap, a także zestaw wszystkich możliwych wartości pomiędzy tymi dwoma ekstremami.
Tabele zakresów
Gdy silnik wykonawczy w trybie wsadowym zdecyduje się zbudować duży, prosty bitmapa lub złożony bitmapa dla sprzężenia haszującego, buduje również tablicę zakresów. To nie zbuduj tabelę zasięgu dla małych proste mapy bitowe.
Tablica zakresów jest strukturą o stałym rozmiarze 128 KB, składającą się z 8192 par 8-bajtowych wartości określających (dolny, wysoki) zakres wartości obecnych w tablicy mieszającej. Tabelę zakresów można zbudować na dowolnym typie danych zgodnym z wykonywaniem w trybie wsadowym. Podczas skanowania gotowej tablicy mieszającej każda partia danych jest używana do wypełnienia mapy bitowej i tabela zasięgu.
Dla każdej wartości w partii funkcja mieszająca jest używana do zlokalizowania segmentu (pary wartości zakresu) w tabeli zakresów. Jeśli zasobnik jest obecnie nieużywany, wartość jest przechowywana zarówno w niskich, jak i wysokich 8-bajtowych wartościach. Jeśli wiadro jest już w użyciu, zamiast tego napełniane jest następne wiadro (i tak dalej, aż do znalezienia pustego wiadra).
Jeśli tabela zakresu zapełni się w jednej trzeciej (2730 z 8192 użytych segmentów), użyte wpisy zostaną skopiowane, zakres segmentu zostanie podwojony, a następnie zapisane wartości zostaną ponownie wstawione w taki sam sposób jak poprzednio (chociaż funkcja skrótu uwzględnia nowy rozmiar łyżki). Wszelkie nakładające się zasobniki są scalane, a proces podwajania trwa do momentu, gdy liczba używanych zasobników spadnie poniżej 2730. Na przykład dwa zasobniki, które początkowo zawierają „zakresy” (1-1) i (2-2) mogą zostać połączone w jeden zasobnik zakresu (1-2) po podwojeniu pierwszego zakresu.
Po przetworzeniu wszystkich partii danych tabeli mieszającej do tabeli zakresów wykonywane jest końcowe scalanie segmentów, a następnie szybkie sortowanie w miejscu ustawia segmenty w kolejności wartości. Pozwala to na wyszukiwanie binarne w celu zlokalizowania przedziału zakresu o określonej wartości będącej przedmiotem zainteresowania.
Wynikiem wszystkich tych działań jest utworzenie zestawu do 2730 odrębnych zakresów opisujących dane w tablicy mieszającej (oprócz dużej prostej lub złożonej mapy bitowej).
Korzystanie z tabeli zakresów
Tabela zakresów jest używana, gdy filtr bitmapy łączenia mieszającego jest wpychany do operatora skanowania magazynu kolumn po stronie sondy. Każdy segment magazynu kolumn zawiera metadane katalogu dotyczące minimalnej i maksymalnej wartości danych obecnych w segmencie. Silnik wykonawczy może użyć tych informacji do przeszukiwania binarnego tabeli zakresu bitmap w poszukiwaniu dopasowania. Jeśli nie zostanie znalezione żadne dopasowanie, silnik wykonawczy może całkowicie pominąć segment.
Ta optymalizacja środowiska wykonawczego dotyczy również odczytu z wyprzedzeniem, dzięki czemu silnik może nawet uniknąć wczytywania do pamięci segmentów, o których wie, że zostaną wyeliminowane przez filtr tabeli zakresów. Wszelkie segmenty, które nie zostały wyeliminowane przez tabelę zakresów, są nadal filtrowane przy użyciu mapy bitowej. Ta kombinacja powoduje, że maksymalna liczba wierszy jest eliminowana tak szybko, jak to możliwe.
Chociaż tabela zakresów nie jest tworzona dla małej prostej mapy bitowej, ta struktura może być również używana do eliminacji segmentów, ponieważ zakres wartości jest znany (w tym wszelkie przesunięcia). Jest na tyle mały, że nie warto dzielić go na podzakresy za pomocą tabeli zakresów.
Gdy mapa bitowa nie zostanie wypchnięta do skanowania magazynu kolumn, nadal można ją ocenić jako zwykły filtr w trybie wsadowym, aby osiągnąć redukcję sprzężenia częściowego przed sprzężeniem mieszającym. Jest to znacznie mniej wydajne niż eliminacja segmentów lub filtrowanie podczas skanowania magazynu kolumn, ale nadal jest lepsze niż filtrowanie przy samym łączeniu mieszającym.
Mapy bitowe i skompresowane dane
Zastosowanie mapy bitowej w trybie wsadowym łączenia mieszającego do danych magazynu kolumn w ramach skanowania może zapewnić bardzo dobrą wydajność, ale wymaga zdekompresowania nieczystych danych segmentu przed zastosowaniem mapy bitowej. Ta dekompresja może być wykonana wydajnie za pomocą instrukcji SIMD, ale nadal jest to dodatkowa praca.
W SQL Server 2016 wprowadzono możliwość tworzenia mapy bitowej dla ogólnych predykatów na danych segmentów zakodowanych w słowniku. Predykat jest oceniany na podstawie wpisów w słowniku w celu utworzenia nowego mała mapa bitowa z każdym ustawionym bitem wskazującym wpis w słowniku, który spełnia predykat. Zastosowanie tej bitmapy może być niezwykle szybkie, zwłaszcza jeśli bitmapa mieści się w jednym rejestrze SIMD. SQL Server może nadal używać SIMD, jeśli mapa bitowa nie pasuje, ale zbieranie bitów z mapy bitowej w pamięci jest nieco mniej wydajne niż w przypadku w rejestrze.
Optymalizację na rok 2016 można zastosować do dowolnego predykat wypchnięty do skanowania magazynu kolumn, w tym „predykat” mapy bitowej utworzony przez sprzężenie haszujące. Aby było jasne, SQL Server pobiera bitmapę sprzężenia mieszającego i tworzy nową (znacznie mniejszą) bitmapę przy użyciu wpisów słownika. Ta nowa bitmapa jest stosowana do danych segmentu przed dekompresją. Optymalizacja może być monitorowana za pomocą rozszerzonego zdarzenia column_store_expression_filter_bitmap_set . Gdy używana jest mapa bitowa słownika, element zdarzenia filter_on_compressed_data_type członek zostanie wypełniony. Zwykle zawiera wartość RAWBITMAP . Istnieje dalsza optymalizacja w celu przekształcenia skompresowanej mapy bitowej słownika na filtr porównania, jeśli mapa bitowa słownika reprezentuje pojedynczy ciągły zakres wartości. W takim przypadku zobaczysz coś innego niż RAWBITMAP (np. LTGT dla porównania mniejsze niż/większe niż).
Zdarzenia rozszerzone i flagi śledzenia
Ogólną możliwość kompilowania filtrów wypychanych (w tym map bitowych generowanych przez sprzężenie haszujące w trybie wsadowym) podczas skanowania magazynu kolumn do mapy bitowej można wyłączyć za pomocą flagi śledzenia na poziomie sesji 9361. Konkretną optymalizację mapy bitowej skompresowanych danych można wyłączyć za pomocą sesji -poziom flagi śledzenia 9362. Konwersję mapy bitowej słownika z pojedynczym ciągłym zakresem na filtr porównania można wyłączyć za pomocą flagi śledzenia 9363. Niestety nie ma flag śledzenia kompilacji detalicznej, które zgłaszają komunikaty informacyjne o mapach bitowych w trybie wsadowym lub filtrze wypychanym kompilacja.
Istnieje kilka rozszerzonych zdarzeń, które generują informacje o mapach bitowych trybu wsadowego łączenia mieszającego. Najbardziej przydatne to:
query_execution_column_store_segment_scan_startedquery_execution_column_store_segment_scan_finishedcolumn_store_expression_filter_bitmap_setcolumn_store_segment_eliminate
Gdy mapa bitowa trybu wsadowego łączenia mieszającego jest przekazywana w dół do skanowania magazynu kolumn, „rozpoczęte” zdarzenie zgłasza BITMAP_SIMPLE lub BITMAP_COMPLEX jako filter_type . Nie rozróżnia małych i dużych prostych bitmap, ani nie zgłasza żadnych informacji o tabeli zakresów. Rozszerzone metadane zdarzenia zawierają inne wartości dla column_store_filter_type zawierające BITMAP_SIMPLE_LARGE między innymi, ale zdarzenie rozszerzone obecnie nie generuje tych danych wyjściowych, gdy używana jest duża prosta bitmapa. Być może zostanie to poprawione w przyszłej wersji.
Globalna flaga śledzenia 646 może być użyta do raportowania informacji o eliminacji segmentu włączonej przez tabelę zakresów (lub małą prostą mapę bitową). Raportuje podobne informacje do segmentu eliminując rozszerzone zdarzenie. Wszystkie flagi śledzenia wymienione w tej sekcji są nieudokumentowane i nieobsługiwane.
Końcowe myśli
Mapy bitowe w trybie wsadowym mogą być niezwykle skuteczne, gdy właściwe typy danych (maksymalnie 64 bity i liczby całkowite), a bitmapę można przesunąć do skanowania magazynu kolumn, zwłaszcza jeśli dane segmentu wykorzystują kompresję RLE (czysta pamięć masowa) lub jeśli bitmapę można skompilować do innej bitmapy na danych słownikowych.
Byłoby fajnie, gdyby plany wykonania podawały bardziej szczegółowe informacje o bitmapach łączenia skrótów — przynajmniej po to, by powiedzieć, jaki typ bitmapy został utworzony. Obecnie mamy tylko Twórcę bitmap nieruchomość i niektóre rozszerzone zdarzenia do pracy. To sprawia, że szczegółowa analiza planu jest nieco trudniejsza niż powinna, biorąc pod uwagę ogromny wzrost wydajności, który można osiągnąć, wykorzystując wszystkie sprytne optymalizacje wbudowane w silnik wykonawczy dla danych magazynu kolumn i łączeń mieszających w trybie wsadowym.
Prezentacje, ilustracje i dalsze omówienie głównych punktów omówionych w tym artykule są dostępne na mojej osobistej stronie w trybie Batch Mode Bitmap Demos.
