Odhad mohutnosti predikátu na výrazu COUNT

Tento článek se zabývá odhadem selektivity a mohutnosti predikátů na COUNT(*) výrazy, jak je vidět v HAVING doložky. Podrobnosti jsou snad samy o sobě zajímavé. Poskytují také vhled do některých obecných přístupů a algoritmů používaných estimátorem mohutnosti.

Jednoduchý příklad pomocí vzorové databáze AdventureWorks:

VYBERTE A.City FROM Person.[Address] JAKO SKUPINU PODLE A.City HAVING COUNT_BIG(*) =1;

Zajímá nás, jak SQL Server odvozuje odhad predikátu na výraz počtu v HAVING doložka.

Samozřejmě HAVING klauzule je jen syntaktický cukr. Stejně tak jsme mohli napsat dotaz pomocí odvozené tabulky nebo běžného tabulkového výrazu:

-- Odvozená tabulkaSELECT SQ1.CityFROM( SELECT A.City, Expr1001 =COUNT_BIG(*) FROM Osoba.[Adresa] AS A GROUP BY A.City) AS SQ1WHERE SQ1.Expr1001 =1; -- CTEWITH Grouped AS( SELECT A.City, Expr1001 =COUNT_BIG(*) FROM Person.[Address] AS A GROUP BY A.City)SELECT G.CityFROM Grouped AS GWHERE G.Expr1001 =1;

Všechny tři formuláře dotazů vytvářejí stejný plán provádění s identickými hodnotami hash plánu dotazů.

Plán po provedení (skutečný) ukazuje dokonalý odhad pro agregát; nicméně odhad pro HAVING filtr klauzule (nebo ekvivalentní v jiných formulářích dotazu) je špatný:

Statistiky pro City poskytuje přesné informace o počtu různých hodnot měst:

DBCC SHOW_STATISTICS ([Person.Address], Město) S DENSITY_VECTOR;

Veškerá hustota číslo je převrácená hodnota počtu jedinečných hodnot. Jednoduchý výpočet (1 / 0,00173913) =575 udává odhad mohutnosti pro agregát. Seskupení podle města samozřejmě vytváří jeden řádek pro každou odlišnou hodnotu.

Všimněte si, že veškerá hustota pochází z vektoru hustoty. Dejte pozor, abyste omylem nepoužili hustotu hodnotu z výstupu záhlaví statistik DBCC SHOW_STATISTICS . Hustota záhlaví je zachována pouze pro zpětnou kompatibilitu; v dnešní době ji optimalizátor při odhadu mohutnosti nepoužívá.

Problém

Agregát zavádí do pracovního postupu nový vypočítaný sloupec s označením Expr1001 v prováděcím plánu. Obsahuje hodnotu COUNT(*) v každém seskupeném řádku výstupu:

V databázi evidentně nejsou žádné statistické informace o tomto novém vypočítaném sloupci. Zatímco optimalizátor ví, že bude 575 řádků, neví nic o distribuci hodnot počtu v těchto řádcích.

Tedy ne tak docela nic:Optimalizátor si je vědom, že hodnoty počtu budou kladná celá čísla (1, 2, 3…). K přesnému odhadu selektivity COUNT(*) = 1 by však bylo zapotřebí rozdělení těchto celočíselných hodnot počtu mezi 575 řádky. predikát.

Někdo by si mohl myslet, že z histogramu lze odvodit nějaký druh informací o distribuci, ale histogram poskytuje pouze konkrétní informace o počtu (v EQ_ROWS ) pro hodnoty kroku histogramu. Mezi kroky histogramu máme pouze shrnutí:RANGE_ROWS řádky mají DISTINCT_RANGE_ROWS odlišné hodnoty. U tabulek, které jsou dostatečně velké, aby nám záleželo na kvalitě odhadu selektivity, je velmi pravděpodobné, že většinu tabulky představují tyto souhrny v rámci jednotlivých kroků.

Například první dva řádky City sloupcový histogram jsou:

DBCC SHOW_STATISTICS ([Person.Address], Město) S HISTOGRAMEM;

To nám říká, že existuje přesně jeden řádek pro „Abingdon“ a 29 dalších řádků za „Abingdon“, ale před „Ballard“, s 19 odlišnými hodnotami v tomto rozsahu 29 řádků. Následující dotaz ukazuje skutečné rozložení řádků mezi jedinečné hodnoty v tomto 29řádkovém rozsahu v rámci kroku:

SELECT A.City, NumRows =COUNT_BIG(*)FROM Person.[Address] AS A WHERE A.City> N'Abingdon' AND A.City  

 
 

 Existuje 29 řádků s 19 odlišnými hodnotami, jak je uvedeno v histogramu. Přesto je jasné, že nemáme žádný základ pro hodnocení selektivity predikátu na sloupec počtu v tomto dotazu. Například HAVING COUNT_BIG(*) = 2 vrátí 5 řádků (pro Alexandrii, Altadenu, Atlantu, Augsburg a Austin), ale z histogramu to nemůžeme nijak určit.
 
Vzdělaný odhad
 

 Přístup SQL Serveru je předpokládat, že každá skupina je nejpravděpodobnější obsahovat celkový průměrný (průměrný) počet řádků. Toto je jednoduše mohutnost dělená počtem jedinečných hodnot. Například pro 1000 řádků s 20 jedinečnými hodnotami by SQL Server předpokládal, že (1000 / 20) =50 řádků na skupinu je nejpravděpodobnější hodnotou.
 

 Vrátíme-li se zpět k našemu původnímu příkladu, znamená to, že sloupec vypočítaného počtu „s největší pravděpodobností“ obsahuje hodnotu kolem (19614 / 575) ~=34,1113 . Od hustoty je převrácená hodnota počtu jedinečných hodnot, můžeme to také vyjádřit jako kardinalita * hustota =(19614 * 0,00173913), což dává velmi podobný výsledek.
 
Distribuce
 

 Tvrzení, že střední hodnota je s největší pravděpodobností trvá jen tak daleko. Musíme také přesně určit, jak je to pravděpodobné; a jak se pravděpodobnost mění, když se vzdalujeme od střední hodnoty. Za předpokladu, že všechny skupiny mají v našem příkladu přesně 34 113 řádků, by nebyl příliš „vzdělaný“ odhad!
 

 SQL Server to řeší za předpokladu normální distribuce. Toto má charakteristický tvar zvonu, který již možná znáte (obrázek z odkazovaného záznamu na Wikipedii):
 

 
 

 Přesný tvar normálního rozdělení závisí na dvou parametrech :střední hodnota (µ ) a směrodatná odchylka (σ ). Průměr určuje umístění vrcholu. Směrodatná odchylka udává, jak „zploštělá“ je zvonová křivka. Čím plošší je křivka, tím nižší je vrchol a tím více je hustota pravděpodobnosti rozložena na jiné hodnoty.
 

 SQL Server může odvodit průměr ze statistických informací, jak již bylo uvedeno. Směrodatná odchylka z vypočteného počtu hodnot sloupce není znám. SQL Server to odhaduje jako druhou odmocninu průměru (s mírnou úpravou podrobně popsaným později). V našem příkladu to znamená, že dva parametry normálního rozdělení jsou zhruba 34,1113 a 5,84 (druhá odmocnina).
 

 Standard normální rozdělení (červená křivka v diagramu výše) je pozoruhodný speciální případ. K tomu dochází, když je průměr nula a směrodatná odchylka je 1. Jakékoli normální rozdělení lze převést na standardní normální rozdělení odečtením průměru a dělením směrodatnou odchylkou.
 
Oblasti a intervaly
 

 Zajímá nás odhad selektivity, proto hledáme pravděpodobnost, že počítaný sloupec má určitou hodnotu (x). Tato pravděpodobnost není dána hodnotou na ose y výše, ale plochou pod křivkou nalevo od x.
 

 Pro normální rozdělení s průměrem 34,1113 a směrodatnou odchylkou 5,84 je plocha pod křivkou nalevo od x =30 přibližně 0,2406:
 

 
 

 To odpovídá pravděpodobnosti, že vypočítaný sloupec počtu je menší nebo roven 30 pro náš příklad dotazu.
 

 To pěkně vede k myšlence, že obecně nehledáme pravděpodobnost konkrétní hodnoty, ale interval . Chcete-li zjistit pravděpodobnost, že se počet rovná celočíselnou hodnotu, musíme vzít v úvahu skutečnost, že celá čísla zabírají interval o velikosti 1. Jak převedeme celé číslo na interval, je poněkud libovolné. SQL Server to řeší přidáním a odečtením 0,5 k zadání dolní a horní hranice intervalu.
 

 Abychom například našli pravděpodobnost, že se vypočítaná hodnota počtu rovná 30, musíme odečíst plocha pod křivkou normálního rozdělení pro (x =29,5) od plochy pro (x =30,5). Výsledek odpovídá řezu pro (29,5  

 
 

 Oblast červeného řezu je přibližně 0,0533 . Pro dobrou první aproximaci je to selektivita predikátu počet =30 v našem testovacím dotazu.
 
Funkce kumulativního rozdělení
 

 Výpočet plochy pod normálním rozdělením nalevo od dané hodnoty není přímočarý. Obecný vzorec je dán kumulativní distribuční funkcí (CDF). Problém je v tom, že CDF nelze vyjádřit pomocí elementárních matematických funkcí, takže je třeba místo toho použít metody numerické aproximace.
 

 Protože všechna normální rozdělení lze snadno převést na standardní normální rozdělení (průměr =0, směrodatná odchylka =1), všechny aproximace slouží k odhadu standardního normálu. To znamená, že se musíme transformovat naše hranice intervalu od konkrétního normálního rozdělení vhodného pro dotaz ke standardnímu normálnímu rozdělení. To se provádí, jak již bylo zmíněno dříve, odečtením průměru a dělením směrodatnou odchylkou.
 

 Pokud znáte Excel, možná znáte funkce NORM.DIST a NORM.S.DIST, které dokážou vypočítat CDF (pomocí metod numerické aproximace) pro konkrétní normální rozdělení nebo standardní normální rozdělení.
 

 SQL Server nemá vestavěnou kalkulačku CDF, ale můžeme ji snadno vytvořit. Vzhledem k tomu, že CDF pro standardní normální rozdělení je:
 

 
 

 …kde erf je chybová funkce:
 

 
 

 Implementace T-SQL pro získání CDF pro standardní normální rozdělení je uvedena níže. Pro chybovou funkci používá číselnou aproximaci který je velmi blízký tomu, který SQL Server používá interně:
 
CREATE PROCEDURE dbo.GetStandardNormalCDF( @x float, @cdf float OUTPUT)ASBEGIN SET NOCOUNT, XACT_ABORT ON; DECLARE @sign float, @erf float; SET @znak =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;
 

 Příklad pro výpočet CDF pro x =30 pomocí normálního rozdělení pro náš testovací dotaz:
 
DECLARE @cdf float;DECLARE @x float;-- HAVING COUNT_BIG(*) =xSET @x =30;-- Normalizujte 30 odečtením střední hodnoty-- a dělením směrodatnou odchylkouSET @x =(@x - 34.1113) / 5.84;EXECUTE dbo.GetStandardNormalCDF @x =@x, @cdf =@cdf OUTPUT;SELECT CDF =@cdf;
 

 Všimněte si kroku normalizace pro převod na standardní normální rozdělení. Procedura vrátí hodnotu 0,2407196…, která odpovídá odpovídajícímu výsledku Excelu na sedm desetinných míst.
 
Konečné podrobnosti a příklady
 

 Následující kód upravuje náš vzorový dotaz tak, aby vytvořil větší odhad pro filtr (srovnání je nyní s hodnotou 32, která je mnohem blíže průměru než dříve):
 
SELECT A.CityFROM Person.[Address] AS AGROUP BY A.CityHAVING COUNT_BIG(*) =32;
 

 
 

 Odhad z optimalizátoru je nyní 36,7807 .
 

 Abychom odhad vypočítali ručně, musíme nejprve vyřešit několik posledních podrobností:
 
 
Průměr použitý k odvození směrodatné odchylky (přes odmocninu) je škálován faktorem ((odlišné hodnoty – 1) / (odlišné hodnoty) . V příkladu je počet odlišných hodnot 575, takže faktor měřítka je (574 / 575) ~=0,99826. 
Pokud je dolní mez (celého čísla) intervalu 1, SQL Server považuje interval za neohraničený na spodní straně. Selektivita se rovná CDF samotné horní hranice intervalu (1,5). Dolní mez (která by byla 0,5) se nepoužívá. 
Starší nástroj pro odhad mohutnosti (CE) má složitou logiku pro COUNT(*) = 1 , která zde není podrobně popsána. 
Kromě COUNT(*) = 1 V případě starší verze CE používá stejnou logiku jako nová CE (dostupná od SQL Serveru 2014 a novější).
 
 

 Následující postup zahrnuje všechny podrobnosti v tomto článku. Vyžaduje to dříve uvedený postup CDF:
 
CREATE PROCEDURE dbo.GetCountPredicateEstimate( @From integer, @To integer, @Cardinality float, @Density float, @Selectivity float OUTPUT, @Estimate float OUTPUT)ASBEGIN SET NOCOUNT, XACT_ABORT ON; ZAČNĚTE ZKUSTE DECLARE @Start float, @End float, @Distinct float, @Mean float, @MeanAdj float, @Stdev float, @NormStart float, @NormEnd float, @CDFStart float, @CDFEend float; -- Ověřte vstup a použijte výchozí hodnoty IF ISNULL(@Od, 0) =0 SET @Od =1; IF @Od <1 RAISERROR ('@Od musí být>=1', 16, 1); IF ISNULL(@Kardinalita, -1) <=0 RAISERROR('@Kardinalita musí být kladná', 16, 1); IF ISNULL(@Hustota, -1) <=0 RAISERROR('@Hustota musí být kladná', 16, 1); IF ISNULL(@To, 0) =0 SET @To =CEILING(1 / @Hustota); IF @To <@From RAISERROR('@To musí být>=@Od', 16, 1); -- Převést rozsah celého čísla na interval SET @Začátek =@Od - 0,5; SET @End =@To + 0,5; -- Získejte počet odlišných hodnot SET @Distinct =1 / @Density; -- Vypočítejte střední hodnotu SET @Průměr =@Kardinalita * @Hustota; -- Upravte střední hodnotu; SET @MeanAdj =@Mean * ((@Distinct - 1) / @Distinct); -- Získejte standardní odchylku (hádejte) SET @Stdev =SQRT(@MeanAdj); -- Normalizovat interval SET @NormStart =(@Start - @Mean) / @Stdev; SET @NormEnd =(@End - @Mean) / @Stdev; -- Vypočítat CDF EXECUTE dbo.GetStandardNormalCDF @x =@NormStart, @cdf =@CDFStart OUTPUT; EXECUTE dbo.GetStandardNormalCDF @x =@NormEnd, @cdf =@CDFEnd VÝSTUP; -- Selektivita SET @Selectivity =CASE -- Neohraničený začátek WHEN @From =1 THEN @CDFEnd -- Neohraničený konec WHEN @To>=@Distinct THEN 1 - @CDFStart -- Normální interval ELSE @CDFEnd - @CDFStart KONEC; -- Odhad řádku návratu SET @Estimate =@Selectivity * @Distinct; KONEC ZKUSTE ZAČÁTEK CATCH DECLARE @EM nvarchar(4000) =ERROR_MESSAGE(); POKUD @@TRANCOUNT> 0 ROLLBACK TRANSACTION; RAISERROR (@EM, 16, 1); VRÁTIT SE; END CATCH;END;
 

 Nyní můžeme tento postup použít ke generování odhadu pro náš nový testovací dotaz:
 
DECLARE @Selectivity float, @Estimate float;EXECUTE dbo.GetCountPredicateEstimate @From =32, @To =32, @Kardinality =19614, @Density =0,00173913, @Selectivity =@Selectivity OUTPUT, @EstimateP OUT, @EstimateP OUT SELECT Selektivita =@Selektivita, Odhad =@Odhad, Zaokrouhleno =ROUND(@Odhad, 4);
 

 Výstup je:
 

 
 

 To je velmi dobře srovnatelné s odhadem mohutnosti optimalizátoru 36,7807. 
 
Příklady intervalů nerovností
 

 Postup lze použít pro jiné intervaly počítání kromě testů rovnosti. Vše, co je potřeba, je nastavit @From a @To parametry k hranicím celočíselného intervalu. Chcete-li zadat neomezené, předejte nulu nebo NULL jak chcete.
 
SELECT A.CityFROM Person.[Address] AS AGROUP BY A.CityHAVING COUNT_BIG(*) <50;
 

 
 

 Abychom to mohli použít v našem postupu, nastavíme @From = NULL a @To = 49 (protože 50 je vyloučeno o méně než):
 
DECLARE @Selectivity float, @Estimate float;EXECUTE dbo.GetCountPredicateEstimate @From =NULL, @To =49, @Cardinality =19614, @Density =0,00173913, @Selectivity =@Selectivity OUTPUT, @EstimateP OUT, @EstimateP OUT SELECT Selektivita =@Selektivita, Odhad =@Odhad, Zaokrouhleno =ROUND(@Odhad, 4);
 

 Výsledek je 572,5964:
 

 
 

 Poslední příklad použití BETWEEN :
 
SELECT A.CityFROM Person.[Address] AS GROUP BY A.CityHAVING COUNT_BIG(*) MEZI 25 A 30;
 

 Odhad optimalizátoru je 
 

 
 

 Od BETWEEN je včetně, předáme proceduru @From = 25 a @To = 30 . Výsledek je:
 

 
 

 Opět to souhlasí s odhadem optimalizátoru.