Optimalizační prahy – seskupování a agregace dat, část 3

Tento článek je třetí ze série o prahových hodnotách optimalizace pro seskupování a agregaci dat. V části 1 jsem pokryl předobjednaný algoritmus Stream Aggregate. V části 2 jsem pokryl nepředobjednaný algoritmus Sort + Stream Aggregate. V této části se zabývám algoritmem Hash Match (Aggregate), který budu označovat jednoduše jako Hash Aggregate. Poskytuji také shrnutí a srovnání mezi algoritmy, kterými se zabývám v části 1, části 2 a části 3.

Použiji stejnou ukázkovou databázi s názvem PerformanceV3, kterou jsem použil v předchozích článcích série. Jen se ujistěte, že před spuštěním příkladů v článku nejprve spustíte následující kód, abyste odstranili několik nepotřebných indexů:

DROP INDEX idx_nc_sid_od_cid ON dbo.Orders;
DROP INDEX idx_unc_od_oid_i_cid_eid ON dbo.Orders;

Jediné dva indexy, které by v této tabulce měly zůstat, jsou idx_cl_od (seskupený s datem objednávky jako klíčem) a PK_Orders (nesdružený s orderid jako klíčem).

Hash Aggregate

Algoritmus Hash Aggregate organizuje skupiny do hashovací tabulky na základě nějaké interně zvolené hashovací funkce. Na rozdíl od algoritmu Stream Aggregate nemusí spotřebovávat řádky ve skupinovém pořadí. Zvažte následující dotaz (budeme ho nazývat Dotaz 1) jako příklad (vynucení agregace hash a sériového plánu):

SELECT empid, COUNT(*) AS numorders
  FROM dbo.Orders
  GROUP BY empid
  OPTION (HASH GROUP, MAXDOP 1);

Obrázek 1 ukazuje plán pro Dotaz 1.

Obrázek 1:Plán pro dotaz 1

Plán skenuje řádky z seskupeného indexu pomocí vlastnosti Ordered:False (skenování není nutné k dodání řádků uspořádaných podle klíče indexu). Optimalizátor obvykle upřednostňuje skenování nejužšího krycího indexu, což je v našem případě seskupený index. Plán vytvoří hašovací tabulku se seskupenými sloupci a agregacemi. Náš dotaz vyžaduje agregaci COUNT typu INT. Plán to ve skutečnosti vypočítá jako hodnotu typu BIGINT, tedy operátor Compute Scalar, který aplikuje implicitní převod na INT.

Microsoft veřejně nesdílí hashovací algoritmy, které používá. Jedná se o velmi proprietární technologii. Abychom tento koncept ilustrovali, předpokládejme, že SQL Server používá pro náš dotaz výše hashovací funkci % 250 (modulo 250). Před zpracováním jakýchkoli řádků má naše hašovací tabulka 250 segmentů představujících 250 možných výsledků hašovací funkce (0 až 249). Jak SQL Server zpracovává každý řádek, aplikuje hashovací funkci % 250. Výsledkem je ukazatel na jeden z bucketů v naší hashovací tabulce. Pokud propojený seznam kbelíku ještě nezahrnuje skupinu aktuálního řádku, SQL Server přidá do propojeného seznamu novou skupinu se sloupci skupiny (v našem případě prázdné) a počáteční agregovanou hodnotou (v našem případě počet 1). Pokud skupina již existuje, SQL Server aktualizuje agregaci (v našem případě přidá k počtu 1). Předpokládejme například, že SQL Server nejprve zpracuje následujících 10 řádků:

orderid empid 
------- ----- 
320     3
30      5
660     253
820     3
850     1
1000    255
700     3
1240    253
350     4
400     255

Obrázek 2 ukazuje tři stavy hašovací tabulky:před zpracováním jakýchkoli řádků, po zpracování prvních 5 řádků a po zpracování prvních 10 řádků. Každá položka v propojeném seznamu obsahuje n-tici (empid, COUNT(*)).

Obrázek 2:Stavy hashovací tabulky

Jakmile operátor hash Aggregate dokončí spotřebu všech vstupních řádků, hash tabulka bude mít všechny skupiny s konečným stavem agregace.

Stejně jako operátor Sort vyžaduje operátor Hash Aggregate přidělení paměti, a pokud mu dojde paměť, musí se přelít do tempdb; zatímco řazení vyžaduje přidělení paměti, které je úměrné počtu řádků, které mají být seřazeny, hašování vyžaduje přidělení paměti, které je úměrné počtu skupin. Takže zvláště když má seskupovací sada vysokou hustotu (malý počet skupin), tento algoritmus vyžaduje podstatně méně paměti, než když je vyžadováno explicitní třídění.

Zvažte následující dva dotazy (nazývejte je Dotaz 1 a Dotaz 2):

SELECT empid, COUNT(*) AS numorders
  FROM dbo.Orders
  GROUP BY empid
  OPTION (HASH GROUP, MAXDOP 1);
 
SELECT empid, COUNT(*) AS numorders
  FROM dbo.Orders
  GROUP BY empid
  OPTION (ORDER GROUP, MAXDOP 1);

Obrázek 3 porovnává přidělení paměti pro tyto dotazy.

Obrázek 3:Plány pro Dotaz 1 a Dotaz 2

Všimněte si velkého rozdílu mezi přidělením paměti v těchto dvou případech.

Pokud jde o náklady operátora Hash Aggregate, vraťme se k obrázku 1, všimněte si, že neexistují žádné I/O náklady, ale pouze náklady na CPU. Dále se pokuste zpětně analyzovat vzorec výpočtu nákladů na CPU pomocí podobných technik, jaké jsem popsal v předchozích dílech série. Faktory, které mohou potenciálně ovlivnit náklady operátora, jsou počet vstupních řádků, počet výstupních skupin, použitá agregační funkce a to, podle čeho seskupujete (kardinalita seskupovací sady, použité datové typy).

Očekávali byste, že tento operátor bude mít počáteční náklady na přípravu na vytvoření hashovací tabulky. Také byste očekávali, že se bude škálovat lineárně s ohledem na počet řádků a skupin. To je skutečně to, co jsem našel. I když však náklady operátorů Stream Aggregate a Sort nejsou ovlivněny tím, podle čeho seskupujete, zdá se, že náklady operátora Hash Aggregate jsou – jak z hlediska mohutnosti sady seskupení, tak použitých datových typů.

Chcete-li pozorovat, že mohutnost skupiny seskupení ovlivňuje náklady operátora, zkontrolujte náklady na CPU operátorů Hash Aggregate v plánech pro následující dotazy (nazývejte je Dotaz 3 a Dotaz 4):

SELECT orderid % 1000 AS grp, MAX(orderdate) AS maxod
  FROM (SELECT TOP (20000) * FROM dbo.Orders) AS D
  GROUP BY orderid % 1000
  OPTION(HASH GROUP, MAXDOP 1);
 
SELECT orderid % 50 AS grp1, orderid % 20 AS grp2, MAX(orderdate) AS maxod
  FROM (SELECT TOP (20000) * FROM dbo.Orders) AS D
  GROUP BY orderid % 50, orderid % 20 
  OPTION(HASH GROUP, MAXDOP 1);

Samozřejmě se chcete ujistit, že odhadovaný počet vstupních řádků a výstupních skupin je v obou případech stejný. Odhadované plány pro tyto dotazy jsou zobrazeny na obrázku 4.

Obrázek 4:Plány pro Dotaz 3 a Dotaz 4

Jak vidíte, náklady na CPU operátoru Hash Aggregate jsou 0,16903 při seskupování podle jednoho celočíselného sloupce a 0,174016 při seskupování podle dvou celých sloupců, přičemž všechny ostatní jsou stejné. To znamená, že mohutnost seskupení skutečně ovlivňuje náklady.

Pokud jde o to, zda datový typ seskupeného prvku ovlivňuje cenu, použil jsem ke kontrole následující dotazy (nazývejte je Dotaz 5, Dotaz 6 a Dotaz 7):

SELECT CAST(orderid AS SMALLINT) % CAST(1000 AS SMALLINT) AS grp,
    MAX(orderdate) AS maxod
  FROM (SELECT TOP (20000) * FROM dbo.Orders) AS D
  GROUP BY CAST(orderid AS SMALLINT) % CAST(1000 AS SMALLINT)
  OPTION(HASH GROUP, MAXDOP 1);
 
SELECT orderid % 1000 AS grp, MAX(orderdate) AS maxod
  FROM (SELECT TOP (20000) * FROM dbo.Orders) AS D
  GROUP BY orderid % 1000
  OPTION(HASH GROUP, MAXDOP 1);
 
SELECT CAST(orderid AS BIGINT) % CAST(1000 AS BIGINT) AS grp,
    MAX(orderdate) AS maxod
  FROM (SELECT TOP (20000) * FROM dbo.Orders) AS D
  GROUP BY CAST(orderid AS BIGINT) % CAST(1000 AS BIGINT)
  OPTION(HASH GROUP, MAXDOP 1);

Plány pro všechny tři dotazy mají stejný odhadovaný počet vstupních řádků a výstupních skupin, přesto mají všechny různé odhadované náklady na CPU (0,121766, 0,16903 a 0,171716), a proto použitý datový typ ovlivňuje náklady.

Zdá se, že typ agregační funkce má také vliv na náklady. Zvažte například následující dva dotazy (nazývejte je Dotaz 8 a Dotaz 9):

SELECT orderid % 1000 AS grp, COUNT(*) AS numorders
  FROM (SELECT TOP (20000) * FROM dbo.Orders) AS D
  GROUP BY orderid % 1000
  OPTION(HASH GROUP, MAXDOP 1);
 
SELECT orderid % 1000 AS grp, MAX(orderdate) AS maxod
  FROM (SELECT TOP (20000) * FROM dbo.Orders) AS D
  GROUP BY orderid % 1000
  OPTION(HASH GROUP, MAXDOP 1);

Odhadovaná cena CPU pro Hash Aggregate v plánu pro Query 8 je 0,166344 a v Query 9 je 0,16903.

Mohlo by to být zajímavé cvičení pokusit se přesně zjistit, jakým způsobem mohutnost skupiny seskupení, datové typy a použitá agregační funkce ovlivňují náklady; Jen jsem nesledoval tento aspekt nákladů. Po výběru sady seskupení a agregační funkce pro váš dotaz tedy můžete provést zpětnou analýzu kalkulačního vzorce. Pojďme například zpětně analyzovat vzorec výpočtu nákladů na CPU pro operátor Hash Aggregate při seskupování podle jednoho sloupce celého čísla a vrácení agregace MAX (datum objednávky). Vzorec by měl být:

SELECT orderid % 1000 AS grp, MAX(orderdate) AS maxod
  FROM (SELECT TOP (100000) * FROM dbo.Orders) AS D
  GROUP BY orderid % 1000
  OPTION(HASH GROUP, MAXDOP 1);
 
SELECT orderid % 2000 AS grp, MAX(orderdate) AS maxod
  FROM (SELECT TOP (100000) * FROM dbo.Orders) AS D
  GROUP BY orderid % 2000
  OPTION(HASH GROUP, MAXDOP 1);
 
SELECT orderid % 3000 AS grp, MAX(orderdate) AS maxod
  FROM (SELECT TOP (200000) * FROM dbo.Orders) AS D
  GROUP BY orderid % 3000
  OPTION(HASH GROUP, MAXDOP 1);
 
SELECT orderid % 6000 AS grp, MAX(orderdate) AS maxod
  FROM (SELECT TOP (200000) * FROM dbo.Orders) AS D
  GROUP BY orderid % 6000
  OPTION(HASH GROUP, MAXDOP 1);
 
SELECT orderid % 5000 AS grp, MAX(orderdate) AS maxod
  FROM (SELECT TOP (500000) * FROM dbo.Orders) AS D
  GROUP BY orderid % 5000
  OPTION(HASH GROUP, MAXDOP 1);
 
SELECT orderid % 10000 AS grp, MAX(orderdate) AS maxod
  FROM (SELECT TOP (500000) * FROM dbo.Orders) AS D
  GROUP BY orderid % 10000
  OPTION(HASH GROUP, MAXDOP 1);

numrows     numgroups   predictedcost  estimatedcost
----------- ----------- -------------- --------------
100000      1000        0.703315       0.703316
100000      2000        0.721023       0.721024
200000      3000        1.40659        1.40659
200000      6000        1.45972        1.45972
500000      5000        3.44558        3.44558
500000      10000       3.53412        3.53412

CREATE INDEX idx_eid_od ON dbo.Orders(empid, orderdate);

SELECT empid, MAX(orderdate) AS maxod
  FROM (SELECT TOP (10000) * FROM dbo.Orders) AS D
  GROUP BY empid;
 
SELECT empid, MAX(orderdate) AS maxod
  FROM (SELECT TOP (20000) * FROM dbo.Orders) AS D
  GROUP BY empid;
 
SELECT empid, MAX(orderdate) AS maxod
  FROM (SELECT TOP (30000) * FROM dbo.Orders) AS D
  GROUP BY empid;
 
SELECT empid, MAX(orderdate) AS maxod
  FROM (SELECT TOP (40000) * FROM dbo.Orders) AS D
  GROUP BY empid;
 
SELECT empid, MAX(orderdate) AS maxod
  FROM (SELECT TOP (50000) * FROM dbo.Orders) AS D
  GROUP BY empid;

DROP INDEX idx_eid_od ON dbo.Orders;

SELECT orderid % 500 AS grp, MAX(orderdate) AS maxod
  FROM (SELECT TOP (1454) * FROM dbo.Orders) AS D
  GROUP BY orderid % 500;
 
SELECT orderid % 500 AS grp, MAX(orderdate) AS maxod
  FROM (SELECT TOP (1455) * FROM dbo.Orders) AS D
  GROUP BY orderid % 500;

CREATE OR ALTER PROC dbo.EmpOrders
  @initialorderid AS INT
AS
  SELECT empid, COUNT(*) AS numorders
  FROM dbo.Orders
  WHERE orderid >= @initialorderid
  GROUP BY empid;
GO

CREATE INDEX idx_oid_i_eid ON dbo.Orders(orderid) INCLUDE(empid);

EXEC dbo.EmpOrders @initialorderid = 999991;

EXEC dbo.EmpOrders @initialorderid = 990001;

DROP INDEX idx_oid_i_eid ON dbo.Orders;