Фон
В традиционен редов режим планове за изпълнение, SQL Server може да въведе Bitmap оператор като част от извършването на ранно намаляване на полу присъединяване преди паралелно хеширане или присъединяване при сливане. Растерната карта се изгражда от входа за изграждане и се използва за филтриране на редове на входа на сондата, преди да достигнат до присъединяването. Писах за редов режим растерни изображения преди и те също са обхванати в документацията.
Тази статия е за партиден режим растерни изображения, които имат много различна реализация. Имаше значителни подобрения от първото появяване на машината за изпълнение на пакетен режим в SQL Server 2012. Данните тук се отнасят за SQL Server 2017 — най-новата пусната версия към момента на писане. Характеристиките, специфични за по-ранните версии, ще бъдат споменати на линия, докато вървим напред.
Оптимизаторът на заявки
Единственият оператор за присъединяване, който може да работи в пакетен режим, е хеш присъединяването. Оптимизаторът на заявки решава дали хеш присъединяването в пакетен режим (серийно или паралелно) трябва да има растерно изображение или не. Оптимизаторът оценява потенциалната полезност на растерното изображение чрез изчисляване на селективността на хипотетично полусъединяване на входовете за хеш обединяване на ключа(ите) за свързване.
Полусъединяването има смисъл, тъй като функцията на филтрирането на растерни изображения е да премахва редове от страната на пробата, които не съществуват от страната на изграждане. Ако изчислената селективност на полусъединяването е 0,75 или по-малко, оптимизаторът смята, че си струва да използва филтър за растерни изображения в пакетен режим. С други думи, растерното изображение се посочва, ако изчислението на полусъединяване показва, че 25% или повече от редовете от страната на сондата ще бъдат елиминирани от растерното изображение.
Точната селективност на полу присъединяване се използва само за определяне дали хеш присъединяването трябва да има растерно изображение или не. Оценката за селективност от страна на сондата (видима като ефект върху оценките за мощността) е модифицирана, за да отрази факта, че растерните изображения обикновено не са перфектни при премахването на неквалифицирани редове. Това е особено случаят, когато растерното изображение се реализира с помощта на филтър Bloom, който може да генерира фалшиви положителни резултати (редове от страната на сондата, които преминават филтъра, но въпреки това не се присъединяват към страната за изграждане).
Селективно закръгляване
Оптимизаторът взема предвид тази несигурност, като закръгля селективността на полусъединяване до степен десет. Прави това, като взема логаритъма на база 10 преди закръгляне. Например, селективност на полусъединяване от 0,316 дава log10 стойност дробно под -0,5, която се закръгля надолу до -1. Получената селективност от страна на сондата е 10 =0,1. За разлика от това, селективността на полусъединяване от 0,317 дава log10 стойност малко над -0,5, която е закръглена до нула. Следователно селективността от страна на сондата е 10 =1 (всички редове преминават). Възможната селективност на растерното изображение от страна на сондата, произтичаща от тази серия от изчисления, е 1, 0,1, 0,01, 0,001 и т.н. Имайте предвид, че все още може да се използва растерна карта, когато изчислената селективност се закръгли до 1 (всички редове преминават предиката).
Оператори и оценки за мощността
Няма отделно Растрово изображение оператор за хеш присъединяване в пакетен режим. Вместо това операторът за свързване на хеш има Създател на растерни изображения свойство (определено на true) или свойството липсва (не е зададено на false). Тази разлика между режима на ред и изпълнението на пакетния режим прави по-малко лесно да се види дали се създава растерна карта, но тя отразява по-точно основния процес:При изпълнение в режим на ред, Растровата карта операторът попълва растерната карта, докато редовете преминават през нея, един по един, преди да достигнат входа за изграждане на хеш присъединяване. С други думи, растерната и хеш таблицата се изграждат едновременно при изпълнение на режим на ред. В пакетен режим хеш-таблицата е напълно изградена преди да бъде създадено растерното изображение (повече за това скоро).
Оптимизаторът на заявки не прави базирани на разходите избори относно позицията на филтър за растерни изображения в пакетен режим от страна на пробната страна на хеш присъединяването. Той просто предполага, че селективността на растерното изображение ще се прилага за всички дъщерни оператори от страната на сондата. В действителност, растерното изображение се избутва надолу от страната на сондата само след като един-единствен окончателен план за изпълнение е избран от оптимизатора. Ако растерното изображение не може да бъде избутано чак до листов оператор, оценките за мощност ще изглеждат малко странни. Това е компромис, който може да бъде подобрен в бъдеще.
Механизмът за изпълнение
Докато оптимизаторът решава дали трябва да се използва растерна карта в пакетен режим на хеш присъединяване или не, машината за изпълнение на пакетен режим решава типа на растерна карта, която да се използва по време на изпълнение. Това решение се основава на статистическа информация, събрана за ключовете за присъединяване от страна на изграждане по време на изграждането на хеш таблицата. Както беше споменато по-горе, за разлика от изпълнението в редов режим, хеш-съединяванията в пакетен режим първо изграждат изцяло хеш таблицата, преди да се извърши отделно преминаване през хеш таблицата за изграждане на растерното изображение.
Прости растерни изображения
Има два основни типа растерна карта на хеш присъединяване в пакетен режим. Прост растерната карта съдържа един бит за всяка от непрекъснат диапазон от стойности от страна на изграждане. Например, еднобайтова проста растерна карта е в състояние да покаже дали са налице осем последователни стойности от страна на изграждане или не. Стойностите от 0 до 7 включително могат да бъдат кодирани в растерната карта чрез задаване на съответния бит. Стойност от 5 би задала бит 5, който има позиционна стойност 2. Бихме могли да кодираме набора {1, 5, 7} като 2 + 2 + 2 =2 + 32 + 128 =162 =101000102под> . Диапазон от стойности, който не започва от нула, може да бъде кодиран по същия начин, като се компенсират всички стойности с минималната стойност, присъстваща в набора (която знаем от статистиката на хеш таблицата).
Простото растерно изображение има предимството да съхранява точно информация за действително наличните стойности от страна на изграждане, с цената на изискване на памет, пропорционална на диапазон на наличните стойности.
Сложни растерни изображения
Вторият тип растерни изображения е филтър на Bloom. Това задава един или повече битове в структурата на растерната карта в зависимост от резултата от прилагането на една или повече хеш функции към всяка стойност от страна на изграждане. Тестваме за съвпадения, като прилагаме едни и същи хеш функции към всяка стойност от страна на сондата. Ако някоя от хеш функциите идентифицира бит, който не е зададен, можем да сме сигурни, че текущата стойност на сондата не се показва от страната на компилирането.
Тъй като филтърът Bloom е вероятностна структура, може да не филтрираме някои стойности на сондата, които нямат съвпадение от страна на изграждане (фалшиво положително), но никога няма да филтрираме стойност, която присъства (фалшиво отрицателна). С други думи, филтърът на Bloom ни казва или „може би съвпадение“, или „определено не съвпадение“. Процентът на фалшивите положителни резултати може да бъде намален чрез използване на повече битове на ключ (по-голямо растерно изображение) или повече хеш функции. За да бъде ясно, може филтър на Bloom произвежда точно филтриране, но също така може и да не.
Филтрите Bloom представляват ефективно пространство и време алтернатива, когато просто растерно изображение е невъзможно поради необходимостта от пространство. Внедряването на пакетния режим на SQL Server на филтър Bloom е оптимизирано за съвременни архитектури на кеша на процесора и е известно вътрешно като сложно растерно изображение . Сложните растерни изображения поддържат множество колони за свързване и всички типове данни в пакетен режим от SQL Server 2014.
Избор на растерно изображение
Дали SQL Server избира просто или сложни (Bloom филтър) растерното изображение зависи от обхвата на стойности от страна на изграждане (от статистика на хеш таблицата). Има важно предупреждение към думата „обхват“ там, което ще бъде обяснено в следващия раздел. Междувременно ето как машината за изпълнение избира вида на растерното изображение:
- Малка проста растерна карта се използва, когато диапазонът от стойности е 2 (8,388,608) или по-малко. Това е броят на битовете в 1MB.
- Когато диапазонът от стойности е повече от 2, но по-малък или равен на 2 (8MB), машината за изпълнение избира между голямо просто растерно изображение и сложно растерно изображение като се изчисли необходимата памет за всяка опция и се избере по-малката. Голямо просто растерно изображение може да бъде с размер до 8MB. Размерът на сложното растерно изображение зависи от броя битове на ключ, необходими за адекватно представяне на данните. По-отличителните стойности обикновено означават по-голямо сложно растерно изображение.
- Ако диапазонът от стойности е над 2 бита, сложно растерно изображение се използва.
Относно диапазона от стойности
Обхват на посочените по-горе стойности се базира на вътрешния двоичен представяне на данните. Например smallint
стойности 128 и 255 могат да бъдат представени като 0x0080
и 0x00FF
, давайки диапазон от 0x7F
(127) двоични стойности. Този диапазон би работил добре с малка проста растерна карта.
От друга страна, datetime
стойностите “1900-01-01” и “1900-01-02” могат да бъдат представени в 8 байта като 0x0000000100000000
и 0x0000000200000000
(четири байта за дни и четири байта за кърлежи след полунощ). Това сегментирано представяне дава двоичен диапазон от 0x0100000000
(4,294,967,296) за тези две примерни стойности, което е твърде голямо, за да се побере в обикновена растерна карта (дори и голяма). Типовете данни със сложни двоични представяния (напр. смяна на байтове) обикновено няма да работят добре с прости растерни изображения.
Допълнително усложнение е, че данните в пакетния режим са нормализирани — преобразува се в двоично оформление, което работи добре с векторизирани инструкции — и винаги е с размер 64 бита. Стойности, които не могат да се поберат в 64 бита, се съхраняват „извън реда“ с 64-битов указател в ред. Между другото, това двоично оформление не е същото като отчетеното от T-SQL преобразуване в двоичен тип.
Независимо от това, нормализираното оформление е достатъчно подобно за целочислените типове (напр. integer
и bigint
), че простите растерни изображения все още са полезни за диапазони от тези типове данни. Други типове с целочислено двоично представяне (напр. money
и date
) също са подходящи.
Още един пример:Набор от integer
стойности в диапазона от 1 до 8,388,608 ще просто се вписват в 1MB малка проста растерна карта, като се използва един бит за възможна целочислена стойност в диапазона. Диапазонът може да има фиксирано отместване, така че целочислен диапазон от 10 000 000 до 18 388 607 също ще се побере (с отместване от десет милиона). Обърнете внимание, че числото на наличните стойности няма значение, само диапазонът. Две стойности от 0 и 8,388,607 ще запълнят малкия диапазон на прости растерни изображения, както и набор от всички възможни стойности между тези две крайности.
Таблици с диапазони
Когато машината за изпълнение на пакетен режим реши да изгради голям просто растерно изображение или комплекс растерна карта за хеш присъединяване, тя също така изгражда таблица с диапазон. Тоне изградете таблица с диапазони замалки прости растерни изображения.
Таблицата с диапазони е структура с фиксиран размер от 128 KB, съставена от 8 192 двойки 8-байтови стойности, определящи (нисък, висок) диапазон от стойности, присъстващи в хеш таблицата. Таблица с диапазони може да бъде изградена върху всеки тип данни, съвместим с изпълнение в пакетен режим. По време на сканирането на готовата хеш таблица всяка партида данни се използва за попълване на растерното изображение и таблицата с обхвата.
За всяка стойност в пакета се използва хеш функция за намиране на кофа (двойка стойности на диапазона) в таблицата с диапазони. Ако кофата в момента не се използва, стойността се съхранява както в ниски, така и в високи 8-байтови стойности. Ако кофата вече се използва, вместо нея се пълни следващата (и така нататък, докато се намери празна кофа).
Ако таблицата с диапазони стане пълна с една трета (2730 от 8192 използвани кофи), използваните записи се копират, диапазонът на кофата се удвоява, след което запазените стойности се вмъкват отново по същия начин, както преди (въпреки че хеш функцията отчита новия размер на кофата). Всички припокриващи се кофи се обединяват и процесът на удвояване продължава, докато броят на използваните кофи падне под 2730. Например две групи, които първоначално съдържат „диапазони“ (1-1) и (2-2), могат да се слеят в един диапазон от (1-2) след първото удвояване на диапазона.
След като всички партиди данни от хеш таблицата бъдат обработени в таблицата с диапазони, се извършва окончателно сливане на сегменти, след което бързото сортиране на място поставя сегментите в ред на стойност. Това дава възможност за двоично търсене, за да се намери сегмент с диапазон, като се има предвид конкретна стойност, представляваща интерес.
Нетният резултат от цялата тази дейност е да се създаде набор от до 2730 различни диапазона, описващи данните в хеш таблицата (в допълнение към голямата проста или сложна растерна карта).
Използване на таблицата с диапазони
Таблицата на диапазона се използва, когато филтърът за растерни изображения на хеш присъединяване се изтласква надолу в оператор за сканиране на columnstore от страна на сондата. Всеки сегмент на columnstore има каталожни метаданни за минималните и максималните стойности на данни, присъстващи в сегмента. Изпълнителната машина може да използва тази информация за двоично търсене в таблицата с диапазон на растерни изображения за съвпадение. Ако не бъде намерено съвпадение, машината за изпълнение може да пропусне сегмента напълно.
Тази оптимизация по време на изпълнение се извършва и за четене напред, така че машината може дори да избегне четене на сегменти в паметта, за които знае, че ще бъдат елиминирани от филтъра на таблицата с диапазони. Всички сегменти, които не са елиминирани от таблицата с диапазони, все още се филтрират с помощта на растерното изображение. Тази комбинация води до елиминиране на максималния брой редове възможно най-рано.
Въпреки че таблицата с диапазони не е изградена за малка проста растерна карта, тази структура може да се използва и за постигане на елиминиране на сегмента, тъй като диапазонът от стойности е известен (включително всяко отместване). Той е достатъчно малък, за да не си струва да го разделяте на поддиапазони с помощта на таблица с диапазони.
Когато растерната карта не се избутва надолу в сканиране на columnstore, тя все още може да бъде оценена като обикновен филтър за пакетен режим, за да се постигне намаление на полу присъединяване преди хеш присъединяването. Това е много по-малко ефективно от елиминирането на сегменти или филтрирането по време на сканирането на columnstore, но все пак е по-добре от филтрирането при самото хеш присъединяване.
Растрови изображения и компресирани данни
Прилагането на растерна карта в пакетен режим на хеш присъединяване към данните от columnstore като част от сканирането може да доведе до много добра производителност, но изисква декомпресиране на нечистите сегментни данни, преди да може да се приложи растерното изображение. Тази декомпресия може да се извърши ефективно с помощта на SIMD инструкции, но все още е допълнителна работа.
SQL Server 2016 въведе възможността за създаване на растерна карта за общи предикати върху кодирани в речник сегментни данни. Предикатът се оценява спрямо записите в речника, за да се създаде нов малка растерна карта с всеки зададен бит, указващ запис в речника, който удовлетворява предиката. Прилагането на това растерно изображение може да бъде изключително бързо, особено ако растерното изображение се побира в един SIMD регистър. SQL Server все още може да използва SIMD, ако растерното изображение не пасва, но събирането на битове от растерна карта в паметта е малко по-малко ефективно от случая в регистъра.
Тази оптимизация за 2016 г. може да се приложи към всякак предикат, изтласкан в сканиране на columnstore, включително „предикат“ на растерна карта, създаден от възходящо хеш присъединяване. За да бъде ясно, SQL Server взема растерната карта на хеш присъединяването и създава нова (много по-малка) растерна карта, използвайки записите в речника. Това ново растерно изображение се прилага към сегментните данни преди декомпресията. Оптимизацията може да се наблюдава с разширеното събитие column_store_expression_filter_bitmap_set
. Когато се използва речниково растерно изображение, членът на събитието filter_on_compressed_data_type
член ще бъде попълнен. Обикновено това ще съдържа стойността RAWBITMAP
. Съществува допълнителна оптимизация за преобразуване на компресираната речникова растерна карта във филтър за сравнение, ако речниковата растерна карта представлява единичен непрекъснат диапазон от стойности. В този случай ще видите нещо различно от RAWBITMAP
(напр. LTGT
за по-малко от/по-голямо от сравнение).
Разширени събития и флагове за проследяване
Общата способност за компилиране на натиснати филтри (включително растерни изображения, генерирани от хеш обединяване в пакетен режим) при сканиране на columnstore в растерна карта може да бъде деактивирана с флаг за проследяване на ниво сесия 9361. Специфичната оптимизация на растерни изображения с компресирани данни може да бъде деактивирана със сесия -level trace flag 9362. Преобразуването на речниково растерно изображение с единичен непрекъснат диапазон в филтър за сравнение може да бъде деактивирано с флаг за проследяване 9363. За съжаление няма флагове за трасиране на дребно, които отчитат информационни съобщения относно растерни карти в пакетен режим или натиснат филтър компилация.
Има няколко разширени събития, които произвеждат информация за растерните карти в пакетния режим на хеш присъединяване. Най-полезните са:
query_execution_column_store_segment_scan_started
query_execution_column_store_segment_scan_finished
column_store_expression_filter_bitmap_set
column_store_segment_eliminate
Когато битова карта в пакетен режим на хеш присъединяване се избута надолу в сканиране на columnstore, събитието „started“ отчита BITMAP_SIMPLE
или BITMAP_COMPLEX
като filter_type
. Той не прави разлика между малки и големи прости растерни изображения, нито отчита нищо за таблицата на диапазона. Разширените метаданни за събитие съдържат други стойности за column_store_filter_type
които включват BITMAP_SIMPLE_LARGE
наред с други неща, но разширеното събитие в момента не произвежда този изход, когато се използва голямо просто растерно изображение. Може би това ще бъде коригирано в бъдеща версия.
Глобалният флаг за проследяване 646 може да се използва за докладване на информация за елиминирането на сегмента, разрешено от таблицата на диапазона (или малка проста растерна карта). Той отчита подобна информация на сегмента за премахване на разширено събитие. Всички флагове за проследяване, споменати в този раздел, са недокументирани и не се поддържат.
Последни мисли
Растерните карти в пакетния режим могат да бъдат изключително ефективни, когато правилните типове данни (максимум 64 бита и целочислени) се използват и растерното изображение може да бъде преместено надолу до сканиране на columnstore, особено ако сегментните данни използват компресия на RLE (чисто съхранение) или ако растерното изображение може да бъде компилирано в друго растерно изображение върху данни от речник.
Може да е хубаво, ако плановете за изпълнение съобщават по-подробна информация за растерните изображения на хеш присъединяване - поне да се каже какъв тип растерна карта е създадена. Както е, имаме само Bitmap Creator собственост и някои разширени събития за работа. Това прави подробния анализ на плана малко по-труден, отколкото би трябвало да бъде, като се има предвид огромните печалби в производителността, които могат да бъдат реализирани, като се възползвате от всички интелигентни оптимизации, вградени в механизма за изпълнение за данни в columnstore и хеш обединения в пакетен режим.
Демонстрации, илюстрации и по-нататъшно обсъждане на основните моменти, обсъждани в тази статия, са достъпни на моя личен сайт в пакетни демонстрации на растерни изображения.