Оценка на присъединяване на SQL Server с помощта на грубо подравняване на хистограма

Основните промени, направени в оценката на кардиналността, започвайки с издаването на SQL Server 2014, са описани в Бялата книга на Microsoft Оптимизиране на вашите планове за заявка с оценката на мощността на SQL Server 2014 от Джо Сак, И Фанг и Василис Пападимос.

Една от тези промени се отнася до оценката на простите присъединявания с единичен предикат за равенство или неравенство, използвайки статистически хистограми. В раздела, озаглавен „Присъединете се към промените в алгоритъма за оценка“, документът въвежда концепцията за „грубо подравняване“, използвайки минимални и максимални граници на хистограмата:

Въпреки че е потенциално по-малко последователен, наследеният CE може да даде малко по-добри оценки за условието за просто присъединяване поради подравняването на хистограмата стъпка по стъпка. Новият CE използва грубо подравняване. Въпреки това, разликата в оценките може да е достатъчно малка, за да е по-малко вероятно да предизвика проблем с качеството на плана.

Като един от техническите рецензенти на статията смятах, че малко повече подробности около тази промяна биха били полезни, но това не влезе в окончателната версия. Тази статия добавя някои от тези подробности.

Пример за грубо подравняване на хистограма

Грубо подравняване Примерът в Бялата книга използва версията Data Warehouse на примерната база данни на AdventureWorks. Въпреки името, базата данни е доста малка; резервното копие е само 22.3MB и се разширява до около 200MB. Може да бъде изтеглен чрез връзки на страницата с документация за инсталиране и конфигуриране на AdventureWorks.

Заявката, която ни интересува, се присъединява към FactResellerSales и FactCurrencyRate таблици.

SELECT
    FRS.ProductKey,
    FRS.OrderDateKey,
    FRS.DueDateKey,
    FRS.ShipDateKey,
    FCR.DateKey,
    FCR.AverageRate,
    FCR.EndOfDayRate,
    FCR.[Date]
FROM dbo.FactResellerSales AS FRS
JOIN dbo.FactCurrencyRate AS FCR
    ON FCR.CurrencyKey = FRS.CurrencyKey;

Това е просто равносъединяване на една колона така че отговаря на изискванията за мощност на присъединяване и оценка на селективността с помощта на грубо подравняване на хистограмата.

Хистограми

Хистограмите, от които се нуждаем, са свързани с CurrencyKey колона на всяка съединена маса. В ново копие на базата данни AdventureWorksDW, съществуващите статистически данни за по-големите FactResellerSales таблицата са базирани на извадка. За да увеличим максимално възпроизводимостта и да направим подробните изчисления възможно най-прости за следване (избягвайки мащабиране), първото нещо, което ще направим, е да обновим статистиката с помощта на пълно сканиране:

UPDATE STATISTICS dbo.FactCurrencyRate WITH FULLSCAN;
UPDATE STATISTICS dbo.FactResellerSales WITH FULLSCAN;

Тези таблици имат удобната за демонстрация полза от създаването на малък и прост maxdiff хистограми:

DBCC SHOW_STATISTICS
    (FactResellerSales, CurrencyKey)
WITH HISTOGRAM;
 
DBCC SHOW_STATISTICS
    (FactCurrencyRate, [PK_FactCurrencyRate_CurrencyKey_DateKey])
WITH HISTOGRAM;

Комбиниране на минимални съвпадащи хистограма стъпки

Първата стъпка в грубото подравняване изчислението е да се намери приносът към мощността на присъединяването, осигурена от най-ниската стъпка на съвпадение на хистограмата. За нашите примерни хистограми минималната стойност на съответстващата стъпка е на RANGE_HI_KEY = 6 :

Приблизителната мощност на равносъединяване само за тази подчертана стъпка е 1 713 * 1 158 =1 983 654 реда .

Оставащи съвпадащи стъпки

След това трябва да идентифицираме обхвата на хистограмата RANGE_HI_KEY стъпки до максимума за възможни съвпадения на равносъединяване. Това включва придвижване напред от по-рано намерения минимум, докато един от входните данни на хистограмата изчерпи редовете. Съвпадащите диапазони на равносъединяване за текущия пример са подчертани по-долу:

Тези два диапазона представляват останалите редове, за които може да се очаква да допринесат за кардиналността на равносъединяването.

Груба честотно-базирана оценка

Въпросът сега е как да се извърши груб оценка на кардиналността на еквисъединяването на подчертаните стъпки, като се използва наличната информация.

Първоначалният оценител на мощността щеше да извърши фино подравняване стъпка по стъпка на хистограмата, използвайки линейна интерполация, да оцени приноса на присъединяване на всяка стъпка (точно както направихме за минималната стойност на стъпката преди) и да сумира приноса на всяка стъпка, за да получи пълна оценка за присъединяване. Въпреки че тази процедура има много интуитивен смисъл, практическият опит показва, че този фин подход добавя допълнителни изчислителни разходи и може да даде резултати с променливо качество.

Първоначалният оценител имаше друг начин за оценка на мощността на присъединяване, когато информацията за хистограмата или не беше налична, или евристично оценена като по-ниска. Това е известно като оценка, базирана на честота, и използва следните дефиниции:

• C – мощността (брой редове)
• D – броят на отделните стойности
• F – честотата (брой редове) за всяка отделна стойност
• Забележка C =D * F по дефиниция

Ефектът от равносвързаност на отношения R1 и R2 върху всяко от тези свойства е както е показано по-долу:

• F' =F1 * F2
• D' =MIN(D1; D2) – предполагайки задържане
• C' =D' * F' (отново по дефиниция)

Ние сме след C', мощността на равнопоставеното. Заместване на D' и F' във формулата и разширяване:

• C' =D' * F'
• C' =MIN(D1; D2) * F1 * F2
• C' =MIN(D1 * F1 * F2; D2 * F1 * F2)
• сега, тъй като C1 =D1 * F1 и C2 =D2 * F2:
• C' =MIN(C1 * F2, C2 * F1)
• най-накрая, тъй като F =C/D (също по дефиниция):
• C' =MIN(C1 * C2 / D2; C2 * C1 / D1)

Отбелязвайки, че C1 * C2 е продукт на двете входни мощности (декартово присъединяване), е ясно, че минимумът от тези изрази ще бъде този с по-голям брой различни стойности:

• C' =(C1 * C2) / MAX(D1; D2)

В случай, че всичко това изглежда малко абстрактно, интуитивен начин да се мисли за базирана на честота оценка на еквисъединяване е да се вземе предвид, че всяка отделна стойност от една релация ще се присъедини към определен брой редове (средната честота) в другата връзка. Ако имаме 5 различни стойности от едната страна и всяка отделна стойност от другата страна се появява средно 3 пъти, разумната (но груба) оценка за равносъединяване е 5 * 3 =15.

Това не е толкова широка четка, колкото изглежда. Не забравяйте, че числата за кардиналност и различни стойности по-горе не идват от цялата връзка, а само от съответстващите стъпки над минимума. Оттук и груба оценка между минимални и максимални стойности.

Изчисляване на честотата

Можем да получим всеки от тези параметри от подчертаните стъпки на хистограмата.

• Кардиналността C е сумата от EQ_ROWS и RANGE_ROWS .
• Броят на отделните стойности D е сумата от DISTINCT_RANGE_ROWS плюс едно за всяка стъпка.

Кардиналността C1 на съвпадението на FactResellerSales стъпки е сборът от маркираните клетки:

Това дава C1 =59 142 редове.

Няма отделни редове за диапазон, така че единствените различни стойности идват от самите четири граници на стъпки, което дава D1 =4 .

За втората таблица:

Това дава C2 =9,632 . Отново няма отделни редове на диапазона, така че отделните стойности идват от границите на десетте стъпки, D2 =10.

Попълване на Equijoin оценка

Вече имаме всички числа, от които се нуждаем за формулата за равенство:

• C' =(C1 * C2) / MAX(D1; D2)
• C' =(59142 * 9632) / MAX(4; 10)
• C' =569655744 / 10
• C' =56 965 574,4

Не забравяйте, че това е приносът на стъпките на хистограмата над минималната съвпадаща граница. За да завършим оценката на мощността на присъединяването, трябва да добавим приноса от минималните стойности на съвпадащи стъпки, които бяха 1713 * 1158 =1 983 654 реда.

Следователно крайната оценка за равносъединение е 56 965 574,4 + 1 983 654 =58 949 228,4 реда или 58 949 200 до шест значими цифри.

Този резултат се потвърждава в прогнозния план за изпълнение на заявката източник:

Както е отбелязано в Бялата книга, това не е голяма оценка. Действителният брой редове, върнати от тази заявка, е 70 470 090 . Оценката, направена от оригиналния („наследен“) оценител на мощността – използвайки подравняване на хистограма стъпка по стъпка – е 70 470 100 реда.

По-добри резултати често са възможни с по-финия метод, но само ако статистическите данни са много добро представяне на основното разпределение на данните. Това не е просто въпрос на актуализиране на статистиката или използване на популация от пълно сканиране. Алгоритъмът, използван за пакетиране на информация в максимум 201 стъпки на хистограмата, не е перфектен и във всеки случай много разпределения на данни в реалния свят просто не са способни на такава прецизност на хистограмата. Средно хората трябва да открият, че по-грубият метод осигурява напълно адекватни оценки и по-голяма стабилност с новата CE.

Втори пример

Това надгражда малко върху предишния пример и не изисква изтегляне на примерна база данни.

DROP TABLE IF EXISTS
    dbo.R1,
    dbo.R2;
 
CREATE TABLE dbo.R1 (n integer NOT NULL);
CREATE TABLE dbo.R2 (n integer NOT NULL);
 
INSERT dbo.R1
    (n)
VALUES
    (1), (2), (3), (4), (5), (6), (7), (8), (9), (10),
    (6), (6), (6), (6), (6), (6), (6), (6), (6), (6), 
    (6), (6), (6), (6), (6), (6), (6), (6), (6);
 
INSERT dbo.R2
    (n)
VALUES
    (5), (6), (7), (8), (9), (10), (11), (12), (13), (14), (15),
    (10), (10);
 
CREATE STATISTICS stats_n ON dbo.R1 (n) WITH FULLSCAN;
CREATE STATISTICS stats_n ON dbo.R2 (n) WITH FULLSCAN;

Хистограмите, показващи съвпадащи минимални стъпки, са:

Най-ниският RANGE_HI_KEY който съвпада е 5. Стойността на EQ_ROWS е 1 и в двете, така че приблизителната мощност на равносъединяване е 1 * 1 =1 ред .

Най-високото съвпадение на RANGE_HI_KEY е 10. Открояване на редовете на хистограмата R1 за груба честотна оценка:

Сумиране на EQ_ROWS и RANGE_ROWS дава C1 =24 . Броят на отделните редове е 2 DISTINCT_RANGE_ROWS (отличителни стойности между стъпките) плюс 3 за отделните стойности, свързани с границата на всяка стъпка, което дава D1 =5 .

За R2, сумиране на EQ_ROWS и RANGE_ROWS дава C2 =7 . Броят на отделните редове е 2 DISTINCT_RANGE_ROWS (отличителни стойности между стъпките) плюс 3 за отделните стойности, свързани с границата на всяка стъпка, което дава D2 =5 .

Приблизителната оценка C' е:

• C' =(C1 * C2) / MAX(D1; D2)
• C' =(24 * 7) / 5
• C' =33,6

Добавяне в 1 ред от минималната стъпка съвпадението дава обща оценка от 34,6 реда за равносъединяване:

SELECT
    R1.n,
    R2.n
FROM dbo.R1 AS R1
JOIN dbo.R2 AS R2
    ON R2.n = R1.n;

Прогнозният план за изпълнение показва оценка, съответстваща на нашето изчисление:

Това не е точно правилно, но "наследеният" оценител на мощността не се справя по-добре, оценявайки 15,25 реда срещу 27 действителни:

За цялостно третиране ще трябва също да добавим окончателен принос от съвпадение на нулеви стъпки на хистограмата, но това е необичайно за equijoins (които обикновено се пишат за отхвърляне на нули) и сравнително просто разширение за заинтересования читател.

Последни мисли

Надяваме се, че подробностите в статията ще запълнят няколко пропуски за всеки, който някога се е чудил за „грубо подравняване“. Имайте предвид, че това е само един малък компонент в оценката на мощността. Има няколко други важни концепции и алгоритми, използвани за оценка на присъединяването, по-специално начинът, по който се оценяват предикатите, които не са присъединени, и как се обработват по-сложните съединения. Много от наистина важните части са доста добре обхванати в Бялата книга.