Optimalisatiedrempels - Gegevens groeperen en aggregeren, deel 3

Dit artikel is het derde in een reeks over optimalisatiedrempels voor het groeperen en aggregeren van gegevens. In deel 1 heb ik het vooraf bestelde Stream Aggregate-algoritme behandeld. In deel 2 heb ik het niet-vooraf bestelde Sort + Stream Aggregate-algoritme behandeld. In dit deel behandel ik het Hash Match (Aggregate) algoritme, dat ik simpelweg Hash Aggregate zal noemen. Ik geef ook een samenvatting en een vergelijking tussen de algoritmen die ik behandel in Deel 1, Deel 2 en Deel 3.

Ik gebruik dezelfde voorbeelddatabase genaamd PerformanceV3, die ik in de vorige artikelen in de serie heb gebruikt. Zorg ervoor dat u, voordat u de voorbeelden in het artikel uitvoert, eerst de volgende code uitvoert om een ​​aantal onnodige indexen te verwijderen:

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

De enige twee indexen die in deze tabel moeten worden achtergelaten, zijn idx_cl_od (geclusterd met orderdatum als sleutel) en PK_Orders (niet-geclusterd met orderid als sleutel).

Hash-aggregaat

Het Hash Aggregate-algoritme organiseert de groepen in een hashtabel op basis van een intern gekozen hashfunctie. In tegenstelling tot het Stream Aggregate-algoritme, hoeft het de rijen niet in groepsvolgorde te consumeren. Beschouw de volgende query (we noemen deze Query 1) als voorbeeld (waardoor een hash-aggregatie en een serieel plan wordt geforceerd):

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

Afbeelding 1 toont het plan voor Query 1.

Figuur 1:Plan voor Query 1

Het plan scant de rijen uit de geclusterde index met behulp van een Ordered:False-eigenschap (scan is niet vereist om de rijen te leveren die zijn besteld door de indexsleutel). Doorgaans zal de optimizer de voorkeur geven aan het scannen van de smalste dekkende index, wat in ons geval de geclusterde index is. Het plan bouwt een hashtabel op met de gegroepeerde kolommen en de aggregaten. Onze zoekopdracht vraagt ​​om een ​​INT-getypeerd COUNT-aggregaat. Het plan berekent het eigenlijk als een BIGINT-getypte waarde, vandaar de Compute Scalar-operator, die impliciete conversie toepast op INT.

Microsoft deelt de hash-algoritmen die ze gebruiken niet publiekelijk. Dit is zeer gepatenteerde technologie. Laten we echter, om het concept te illustreren, aannemen dat SQL Server de % 250 (modulo 250) hash-functie gebruikt voor onze bovenstaande query. Voordat we rijen verwerken, heeft onze hashtabel 250 buckets die de 250 mogelijke uitkomsten van de hashfunctie vertegenwoordigen (0 tot en met 249). Terwijl SQL Server elke rij verwerkt, past het de hashfunctie % 250 toe. Het resultaat is een verwijzing naar een van de buckets in onze hashtabel. Als de gekoppelde lijst van de bucket nog niet de groep van de huidige rij bevat, voegt SQL Server een nieuwe groep toe aan de gekoppelde lijst met de groepskolommen (empid in ons geval) en de initiële totale waarde (tel 1 in ons geval). Als de groep al bestaat, werkt SQL Server het aggregaat bij (voegt in ons geval 1 toe aan het aantal). Stel bijvoorbeeld dat SQL Server de volgende 10 rijen eerst verwerkt:

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

Afbeelding 2 toont drie toestanden van de hashtabel:voordat er rijen zijn verwerkt, nadat de eerste 5 rijen zijn verwerkt en nadat de eerste 10 rijen zijn verwerkt. Elk item in de gekoppelde lijst bevat de tuple (empid, COUNT(*)).

Figuur 2:Hashtabelstatussen

Zodra de Hash Aggregate-operator alle invoerrijen heeft verbruikt, bevat de hashtabel alle groepen met de uiteindelijke status van het aggregaat.

Net als de Sort-operator, vereist de Hash Aggregate-operator een geheugentoekenning, en als het geheugen opraakt, moet het naar tempdb worden gemorst; echter, terwijl sorteren een geheugentoekenning vereist die evenredig is met het aantal rijen dat moet worden gesorteerd, vereist hashing een geheugentoekenning die evenredig is met het aantal groepen. Dus vooral wanneer de groeperingsset een hoge dichtheid heeft (klein aantal groepen), vereist dit algoritme aanzienlijk minder geheugen dan wanneer expliciete sortering vereist is.

Overweeg de volgende twee zoekopdrachten (noem ze Query 1 en Query 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);

Afbeelding 3 vergelijkt de geheugentoekenningen voor deze zoekopdrachten.

Figuur 3:Plannen voor Query 1 en Query 2

Let op het grote verschil tussen de geheugentoekenningen in de twee gevallen.

Wat betreft de kosten van de Hash Aggregate-operator, teruggaand naar figuur 1, merk op dat er geen I/O-kosten zijn, maar alleen CPU-kosten. Probeer vervolgens de CPU-kostenformule te reverse-engineeren met behulp van vergelijkbare technieken als degene die ik in de vorige delen van de serie heb behandeld. De factoren die mogelijk van invloed kunnen zijn op de kosten van de operator, zijn het aantal invoerrijen, het aantal uitvoergroepen, de gebruikte aggregatiefunctie en waarop u groepeert (kardinaliteit van de groeperingsset, gebruikte gegevenstypen).

Je zou verwachten dat deze operator opstartkosten heeft ter voorbereiding op het bouwen van de hashtabel. Je zou ook verwachten dat het lineair zou schalen met betrekking tot het aantal rijen en groepen. Dat is inderdaad wat ik heb gevonden. Hoewel de kosten van zowel de Stream Aggregate- als de Sort-operatoren niet worden beïnvloed door waarop u groepeert, lijkt het erop dat de kosten van de Hash Aggregate-operator dat wel zijn, zowel in termen van de kardinaliteit van de groeperingsset als de gebruikte gegevenstypen.

Om te zien dat de kardinaliteit van de groeperingsset van invloed is op de kosten van de operator, controleert u de CPU-kosten van de Hash Aggregate-operators in de plannen voor de volgende query's (noem ze Query 3 en Query 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);

Natuurlijk wilt u ervoor zorgen dat het geschatte aantal invoerrijen en uitvoergroepen in beide gevallen hetzelfde is. De geschatte plannen voor deze zoekopdrachten worden weergegeven in figuur 4.

Figuur 4:Plannen voor Query 3 en Query 4

Zoals u kunt zien, bedragen de CPU-kosten van de Hash Aggregate-operator 0,16903 bij groepering op één geheeltallige kolom en 0,174016 bij groepering op twee gehele gehele kolommen, waarbij al het andere gelijk is. Dit betekent dat de kardinaliteit van de groeperingsset inderdaad van invloed is op de kosten.

Wat betreft de vraag of het gegevenstype van het gegroepeerde element de kosten beïnvloedt, heb ik de volgende query's gebruikt om dit te controleren (noem ze Query 5, Query 6 en Query 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);

De plannen voor alle drie de query's hebben hetzelfde geschatte aantal invoerrijen en uitvoergroepen, maar ze krijgen allemaal verschillende geschatte CPU-kosten (0.121766, 0.16903 en 0.171716), vandaar dat het gebruikte gegevenstype wel van invloed is op de kosten.

Het type aggregatiefunctie lijkt ook een impact te hebben op de kosten. Beschouw bijvoorbeeld de volgende twee zoekopdrachten (noem ze Query 8 en Query 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);

De geschatte CPU-kosten voor de Hash Aggregate in het plan voor Query 8 zijn 0,166344 en in Query 9 0,16903.

Het zou een interessante oefening kunnen zijn om uit te zoeken op welke manier de kardinaliteit van de groeperingsset, de gebruikte gegevenstypen en de gebruikte aggregatiefunctie de kosten precies beïnvloeden; Ik heb dit aspect van de kosten gewoon niet nagestreefd. Dus nadat u een keuze hebt gemaakt voor de groeperingsset en de aggregatiefunctie voor uw query, kunt u de kostprijsberekeningsformule reverse-engineeren. Laten we bijvoorbeeld de CPU-kostenformule voor de Hash Aggregate-operator reverse-engineeren bij het groeperen op een enkele integerkolom en het retourneren van het MAX(orderdate)-aggregaat. De formule zou moeten zijn:

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;