Оценка на кардиналност за предикат върху израз COUNT

Тази статия разглежда оценката на селективността и мощността за предикати на COUNT(*) изрази, както може да се види в HAVING клаузи. Да се ​​надяваме, че детайлите са интересни сами по себе си. Те също така дават представа за някои от общите подходи и алгоритми, използвани от оценителя на мощността.

Прост пример за използване на примерната база данни на AdventureWorks:

ИЗБЕРЕТЕ A.City ОТ Личност.[Адрес] КАТО ГРУПА ПО A.City С COUNT_BIG(*) =1;

Интересуваме се да видим как SQL Server извлича оценка за предиката на израза за броене в HAVING клауза.

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

-- Извлечена таблицаSELECT SQ1.CityFROM( SELECT A.City, Expr1001 =COUNT_BIG(*) ОТ Лице.[Адрес] КАТО ГРУПА ПО A.City) КАТО SQ1WHERE SQ1.Expr1001 =1; -- CTEWITH Групиран КАТО(ИЗБЕРЕТЕ A.City, Expr1001 =COUNT_BIG(*) ОТ Лице.[Адрес] КАТО ГРУПА ПО A.City)ИЗБЕРЕТЕ G.CityFROM Групиран КАТО GWHERE G.Expr1001 =1;

И трите формуляра на заявка произвеждат един и същ план за изпълнение, с идентични хеш стойности на плана на заявката.

Планът след изпълнение (фактически) показва перфектна оценка за агрегата; обаче оценката за HAVING филтърът за клауза (или еквивалент, в другите форми на заявка) е лош:

Статистика за City колона предоставя точна информация за броя на отделните градски стойности:

DBCC SHOW_STATISTICS ([Person.Address], City) WITH DENSITY_VECTOR;

Плялата плътност цифрата е реципрочната стойност на броя уникални стойности. Просто изчисляване (1 / 0,00173913) =575 дава оценката за мощността на агрегата. Групирането по град очевидно произвежда един ред за всяка отделна стойност.

Имайте предвид, че всичката плътност идва от вектора на плътността. Внимавайте да не използвате случайно вплътноста стойност от изхода на заглавката на статистиката на DBCC SHOW_STATISTICS . Плътността на заглавката се поддържа само за обратна съвместимост; не се използва от оптимизатора по време на оценка на мощността в наши дни.

Проблемът

Агрегатът въвежда нова изчислена колона в работния поток, с етикет Expr1001 в плана за изпълнение. Той съдържа стойността на COUNT(*) във всеки групиран изходен ред:

Очевидно няма статистическа информация в базата данни за тази нова изчислена колона. Въпреки че оптимизаторът знае, че ще има 575 реда, той не знае нищо за разпределението на стойностите на броене в тези редове.

Е, не съвсем нищо:Оптимизаторът е наясно, че стойностите на броене ще бъдат цели положителни числа (1, 2, 3…). И все пак, разпределението на тези целочислени стойности на броя между 575-те реда ще е необходимо, за да се оцени точно селективността на COUNT(*) = 1 предикат.

Някой може да си помисли, че някаква информация за разпространението може да бъде извлечена от хистограмата, но хистограмата предоставя само конкретна информация за броя (в EQ_ROWS ) за стойности на стъпката на хистограмата. Между стъпките на хистограмата, всичко, което имаме, е обобщение:RANGE_ROWS редовете имат DISTINCT_RANGE_ROWS отделни стойности. За таблици, които са достатъчно големи, за да ни е грижа за качеството на оценката на селективността, е много вероятно по-голямата част от таблицата да е представена от тези обобщения в рамките на стъпките.

Например първите два реда на City колонната хистограма са:

DBCC SHOW_STATISTICS ([Person.Address], City) С ХИСТОГРАМА;

Това ни казва, че има точно един ред за „Abingdon“ и 29 други реда след „Abingdon“, но преди „Ballard“, с 19 различни стойности в този диапазон от 29 реда. Следната заявка показва действителното разпределение на редовете между уникални стойности в този 29-редов интервал между стъпки:

ИЗБЕРЕТЕ A.City, NumRows =COUNT_BIG(*)FROM Person.[Адрес] КАТО КЪДЕ A.City> N'Abingdon' И A.City  

 
 

 Има 29 реда с 19 различни стойности, точно както казва хистограмата. Все пак е ясно, че нямаме основа да оценяваме селективността на предикат в колоната за броене в тази заявка. Например, HAVING COUNT_BIG(*) = 2 ще върне 5 реда (за Александрия, Алтадена, Атланта, Аугсбург и Остин), но нямаме начин да определим това от хистограмата.
 
Образовано предположение
 

 Подходът, който използва SQL Server, е да приеме, че всяка група е най-вероятно да съдържа общия среден (среден) брой редове. Това е просто кардиналността, разделена на броя на уникалните стойности. Например, за 1000 реда с 20 уникални стойности, SQL Server ще приеме, че (1000 / 20) =50 реда на група е най-вероятната стойност.
 

 Връщайки се към нашия оригинален пример, това означава, че колоната за изчислено броене е „най-вероятно“ да съдържа стойност около (19614 / 575) ~=34.1113 . Тъй като плътност е реципрочна на броя на уникалните стойности, можем също да изразим това като кардиналност * плътност =(19614 * 0,00173913), което дава много подобен резултат.
 
Разпространение
 

 Казвайки, че средната стойност най-вероятно е само ни отвежда дотук. Също така трябва да установим колко точно е вероятно това; и как се променя вероятността, когато се отдалечим от средната стойност. Ако приемем, че всички групи имат точно 34.113 реда в нашия пример, не би било много „образовано“ предположение!
 

 SQL Server се справя с това, като приема нормално разпределение. Това има характерната форма на камбана, с която може би вече сте запознати (изображение от свързания запис в Wikipedia):
 

 
 

 Точната форма на нормалното разпределение зависи отдва параметъра :средната стойност (µ ) и стандартното отклонение (σ ). Средната стойност определя местоположението на върха. Стандартното отклонение определя колко "сплескана" е кривата на звънеца. Колкото по-плоска е кривата, толкова по-нисък е пикът и толкова повече плътността на вероятността се разпределя върху други стойности.
 

 SQL Server може да извлече средната стойност от статистическа информация, както вече беше отбелязано. Стандартното отклонение от стойностите на колоната с изчислен брой е неизвестна. SQL Server го оценява като квадратен корен от средната стойност (с лека корекция, подробно описана по-късно). В нашия пример това означава, че двата параметъра на нормалното разпределение са приблизително 34,1113 и 5,84 (корен квадратен).
 

 Стандартът нормалното разпределение (червената крива на диаграмата по-горе) е забележителен специален случай. Това се случва, когато средната стойност е нула, а стандартното отклонение е 1. Всяко нормално разпределение може да се трансформира в стандартното нормално разпределение чрез изваждане на средната стойност и разделяне на стандартното отклонение.
 
Области и интервали
 

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

 За нормалното разпределение със средно 34,1113 и стандартно отклонение 5,84, площта под кривата вляво от x =30 е около 0,2406:
 

 
 

 Това съответства на вероятността изчислената колона за броене да е по-малка или равна на 30 за нашата примерна заявка.
 

 Това води добре до идеята, че като цяло не търсим вероятността за конкретна стойност, а за интервал . За да се намери вероятното, че броятравно целочислена стойност, трябва да отчетем факта, че целите числа обхващат интервал с размер 1. Как преобразуваме цяло число в интервал е донякъде произволно. SQL Server се справя с това чрез добавяне и изваждане на 0,5 за да дадете долната и горната граница на интервала.
 

 Например, за да намерим вероятността изчислената стойност на броене да е равна на 30, трябва да извадим площта под кривата на нормалното разпределение за (x =29,5) от площта за (x =30,5). Резултатът съответства на среза за (29,5  

 
 

 Площта на червения резен е около0,0533 . В добро първо приближение това е селективността на предикат count =30 в нашата тестова заявка.
 
Функция за кумулативно разпределение
 

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

 Тъй като всички нормални разпределения могат лесно да бъдат трансформирани към стандартното нормално разпределение (средно =0, стандартно отклонение =1), всички приближения работят за оценка на стандартната норма. Това означава, че трябва да се трансформираме нашите интервални граници от конкретното нормално разпределение, подходящо за заявката, до стандартното нормално разпределение. Това се прави, както бе споменато по-рано, като се извади средната стойност и се раздели на стандартното отклонение.
 

 Ако сте запознати с Excel, може да сте наясно с функциите NORM.DIST и NORM.S.DIST, които могат да изчисляват CDF (използвайки методи за числови апроксимации) за определено нормално разпределение или стандартно нормално разпределение.
 

 Няма CDF калкулатор, вграден в SQL Server, но можем лесно да го направим. Като се има предвид, че CDF за стандартното нормално разпределение е:
 

 
 

 …където erf е функцията за грешка:
 

 
 

 По-долу е показана T-SQL реализация за получаване на CDF за стандартното нормално разпределение. Той използва числово приближение за функцията за грешка това е много близко до този, който SQL Server използва вътрешно:
 
СЪЗДАВАНЕ НА ПРОЦЕДУРА dbo.GetStandardNormalCDF( @x float, @cdf float ИЗХОД) ASBEGIN SET NOCOUNT, XACT_ABORT ON; ДЕКЛАРИРАНЕ @sign float, @erf float; SET @sign =SIGN(@x); SET @x =ABS(@x) / SQRT(2); SET @erf =1; SET @erf =@erf + (0,0705230784 * @x); SET @erf =@erf + (0,0422820123 * POWER(@x, 2)); SET @erf =@erf + (0,0092705272 * POWER(@x, 3)); SET @erf =@erf + (0,0001520143 * POWER(@x, 4)); SET @erf =@erf + (0,0002765672 * POWER(@x, 5)); SET @erf =@erf + (0,0000430638 * POWER(@x, 6)); SET @erf =POWER(@erf, -16); SET @erf =1 - @erf; SET @erf =@erf * @sign; SET @cdf =0,5 * (1 + @erf);END;
 

 Пример, за да изчислим CDF за x =30, използвайки нормалното разпределение за нашата тестова заявка:
 
DECLARE @cdf float;DECLARE @x float;-- ИМАТЕ COUNT_BIG(*) =xSET @x =30;-- Нормализиране на 30 чрез изваждане на средната стойност-- и разделяне на стандартното отклонениеSET @x =(@x - 34.1113) / 5.84;ИЗПЪЛНЕТЕ dbo.GetStandardNormalCDF @x =@x, @cdf =@cdf ИЗХОД;ИЗБЕРЕТЕ CDF =@cdf;
 

 Обърнете внимание на стъпката на нормализиране, за да преобразувате към стандартното нормално разпределение. Процедурата връща стойността 0,2407196…, която съответства на съответния резултат от Excel до седем знака след десетичната запетая.
 
Окончателни подробности и примери
 

 Следният код модифицира нашата примерна заявка, за да произведе по-голяма оценка за филтъра (сравнението сега е със стойността 32, което е много по-близо до средната стойност от преди):
 
ИЗБЕРЕТЕ A.CityFROM лице.[адрес] КАТО ГРУПА ОТ A.CityHAVING COUNT_BIG(*) =32;
 

 
 

 Прогнозата от оптимизатора сега е 36,7807 .
 

 За да изчислим ръчно прогнозата, първо трябва да разгледаме няколко последни подробности:
 
 
Средната стойност, използвана за извличане на стандартното отклонение (чрез квадратен корен), се мащабира с коефициент от ((отличителни стойности – 1) / (отличителни стойности) . В примера броят на отделните стойности е 575, така че коефициентът на мащабиране е (574 / 575) ~=0,99826. 
Ако долната граница на интервала (цело число) е 1, SQL Server третира интервала като неограничен от долната страна. Селективността е равна на CDF само на горната граница на интервала (1.5). Долната граница (която би била 0,5) не се използва. 
Наследеният оценител на мощността (CE) има сложна логика за COUNT(*) = 1 , което не е описано тук. 
Освен COUNT(*) = 1 В случай, наследеният CE използва същата логика като новия CE (достъпен в SQL Server 2014 нататък).
 
 

 Следващата процедура включва всички подробности в тази статия. Изисква CDF процедурата, дадена по-рано:
 
СЪЗДАВАНЕ НА ПРОЦЕДУРА dbo.GetCountPredicateEstimate( @From integer, @To integer, @Cardinality float, @Desity float, @Selectivity float OUTPUT, @Estimate float OUTPUT)ASBEGIN SET NOCOUNT, XACT_ABORT ON; ЗАПОЧНЕТЕ ОПИТАЙТЕ ДЕКЛАРИРАНЕ @Start float, @End float, @Distinct float, @Mean float, @MeanAdj float, @Stdev float, @NormStart float, @NormEnd float, @CDFStart float, @CDFEnd float; -- Проверете въвеждането и приложете настройките по подразбиране IF ISNULL(@From, 0) =0 SET @From =1; АКО @From <1 RAISERROR ('@From трябва да бъде>=1', 16, 1); IF ISNULL(@Cardinality, -1) <=0 RAISERROR('@Cardinality трябва да е положителен', 16, 1); IF ISNULL(@Desity, -1) <=0 RAISERROR('@Desity трябва да е положителна', 16, 1); IF ISNULL(@To, 0) =0 SET @To =CEILING(1 / @Desity); АКО @To <@From RAISERROR('@To трябва да бъде>=@From', 16, 1); -- Преобразуване на целочислен диапазон в интервал SET @Start =@From - 0.5; SET @End =@To + 0,5; -- Получаване на брой различни стойности SET @Distinct =1 / @Desity; -- Изчислете средната стойност SET @Mean =@Cardinality * @Desity; -- Регулиране на средната стойност; SET @MeanAdj =@Mean * ((@Distinct - 1) / @Distinct); -- Получаване на стандартно отклонение (предположение) SET @Stdev =SQRT(@MeanAdj); -- Нормализиране на интервала SET @NormStart =(@Start - @Mean) / @Stdev; SET @NormEnd =(@End - @Mean) / @Stdev; -- Изчислете CDF-ове ИЗПЪЛНЯВАТЕ dbo.GetStandardNormalCDF @x =@NormStart, @cdf =@CDFStart ИЗХОД; ИЗПЪЛНЕТЕ dbo.GetStandardNormalCDF @x =@NormEnd, @cdf =@CDFEnd ИЗХОД; -- Селективност SET @Selectivity =CASE -- Неограничено начало WHEN @From =1 THEN @CDFEnd -- Неограничен край WHEN @To>=@Distinct THEN 1 - @CDFStart -- Нормален интервал ELSE @CDFEnd - @CDFStart END; -- Оценка на връщане на ред SET @Estimate =@Селективност * @Distinct; END TRY BEGIN CATCH DECLARE @EM nvarchar(4000) =ERROR_MESSAGE(); АКО @@TRANCOUNT> 0 ТРАНЗАКЦИЯ ОТМЕНА; RAISERROR (@EM, 16, 1); ВРЪЩАНЕ; END CATCH;END;
 

 Вече можем да използваме тази процедура, за да генерираме прогноза за новата ни тестова заявка:
 
DECLARE @Selectivity float, @Estimate float;EXECUTE dbo.GetCountPredicateEstimate @From =32, @To =32, @Cardinality =19614, @Desity =0.00173913, @Selectivity =0.00173913, @Selectivity =OUTEsti =PUTma, @PUTma ИЗБЕРЕТЕ Селективност =@Селективност, оценка =@оценка, закръглено =КРЪГЛО(@оценка, 4);
 

 Резултатът е:
 

 
 

 Това се сравнява много добре с приблизителната оценка на оптимизатора от 36,7807. 
 
Примери за интервал на неравенство
 

 Процедурата може да се използва за други интервали на броене освен тестовете за равенство. Всичко, което се изисква, е да зададете @From и @To параметри към границите на целочисления интервал. За да посочите неограничено, предайте нула или NULL както предпочитате.
 
ИЗБЕРЕТЕ A.CityFROM лице.[Адрес] КАТО ГРУПА ОТ A.CityHAVING COUNT_BIG(*) <50;
 

 
 

 За да използваме това с нашата процедура, ние задаваме @From = NULL и @To = 49 (защото 50 е изключено с по-малко от):
 
DECLARE @Selectivity float, @Estimate float;EXECUTE dbo.GetCountPredicateEstimate @From =NULL, @To =49, @Cardinality =19614, @Desity =0.00173913, @Selectivity =0.00173913, @Selectivity =OUTEsti =PUTma, @PUtelect ИЗБЕРЕТЕ Селективност =@Селективност, оценка =@оценка, закръглено =КРЪГЛО(@оценка, 4);
 

 Резултатът е 572,5964:
 

 
 

 Един последен пример за използване на BETWEEN :
 
ИЗБЕРЕТЕ A.CityFROM лице.[Адрес] КАТО ГРУПА ОТ A.City ИМА COUNT_BIG(*) МЕЖДУ 25 И 30;
 

 Оценката на оптимизатора е 
 

 
 

 Тъй като BETWEEN включва, преминаваме процедурата @From = 25 и @To = 30 . Резултатът е:
 

 
 

 Отново, това е в съответствие с оценката на оптимизатора.