Ambang Pengoptimalan – Pengelompokan dan Penggabungan Data, Bagian 3

Artikel ini adalah yang ketiga dari seri tentang ambang pengoptimalan untuk mengelompokkan dan menggabungkan data. Di Bagian 1 saya membahas algoritma Stream Aggregate yang telah dipesan sebelumnya. Di Bagian 2 saya membahas algoritma Sort + Stream Aggregate yang tidak dipesan sebelumnya. Di bagian ini saya membahas algoritma Hash Match (Aggregate), yang akan saya sebut sebagai Hash Aggregate. Saya juga memberikan ringkasan dan perbandingan antara algoritma yang saya bahas di Bagian 1, Bagian 2, dan Bagian 3.

Saya akan menggunakan database sampel yang sama yang disebut PerformanceV3, yang saya gunakan di artikel sebelumnya dalam seri ini. Pastikan bahwa sebelum Anda menjalankan contoh di artikel, Anda terlebih dahulu menjalankan kode berikut untuk menghapus beberapa indeks yang tidak diperlukan:

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

Hanya dua indeks yang harus ditinggalkan pada tabel ini adalah idx_cl_od (dikelompokkan dengan orderdate sebagai kuncinya) dan PK_Orders (tidak dikelompokkan dengan orderid sebagai kuncinya).

Hash Agregat

Algoritma Hash Aggregate mengatur grup dalam tabel hash berdasarkan beberapa fungsi hash yang dipilih secara internal. Tidak seperti algoritma Stream Aggregate, tidak perlu menggunakan baris dalam urutan grup. Pertimbangkan kueri berikut (kami akan menyebutnya Kueri 1) sebagai contoh (memaksa agregat hash dan paket serial):

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

Gambar 1 menunjukkan rencana untuk Query 1.

Gambar 1:Rencana untuk Kueri 1

Paket memindai baris dari indeks berkerumun menggunakan properti Dipesan:Salah (pemindaian tidak diperlukan untuk mengirimkan baris yang diurutkan oleh kunci indeks). Biasanya, pengoptimal akan lebih memilih untuk memindai indeks penutup tersempit, yang dalam kasus kami adalah indeks berkerumun. Rencananya membuat tabel hash dengan kolom dan agregat yang dikelompokkan. Kueri kami meminta agregat COUNT bertipe INT. Rencana tersebut sebenarnya menghitungnya sebagai nilai yang diketik BIGINT, oleh karena itu operator Hitung Skalar, menerapkan konversi implisit ke INT.

Microsoft tidak secara publik membagikan algoritme hash yang mereka gunakan. Ini adalah teknologi yang sangat eksklusif. Namun, untuk mengilustrasikan konsep tersebut, anggaplah SQL Server menggunakan fungsi hash % 250 (modulo 250) untuk kueri kita di atas. Sebelum memproses baris apa pun, tabel hash kami memiliki 250 ember yang mewakili 250 kemungkinan hasil dari fungsi hash (0 hingga 249). Saat SQL Server memproses setiap baris, SQL Server menerapkan fungsi hash % 250. Hasilnya adalah penunjuk ke salah satu ember di tabel hash kami. Jika daftar tertaut ember belum menyertakan grup baris saat ini, SQL Server menambahkan grup baru ke daftar tertaut dengan kolom grup (empid dalam kasus kami) dan nilai agregat awal (hitung 1 dalam kasus kami). Jika grup sudah ada, SQL Server memperbarui agregat (menambahkan 1 ke hitungan dalam kasus kami). Sebagai contoh, anggaplah SQL Server memproses 10 baris berikut terlebih dahulu:

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

Gambar 2 menunjukkan tiga status tabel hash:sebelum setiap baris diproses, setelah 5 baris pertama diproses, dan setelah 10 baris pertama diproses. Setiap item dalam daftar tertaut menyimpan tuple (empid, COUNT(*)).

Gambar 2:Status tabel hash

Setelah operator Hash Aggregate selesai menggunakan semua baris input, tabel hash memiliki semua grup dengan status akhir agregat.

Seperti operator Sortir, operator Hash Aggregate membutuhkan hibah memori, dan jika kehabisan memori, perlu tumpah ke tempdb; namun, sementara pengurutan membutuhkan pemberian memori yang sebanding dengan jumlah baris yang akan diurutkan, hashing membutuhkan pemberian memori yang sebanding dengan jumlah grup. Jadi, terutama ketika kumpulan pengelompokan memiliki kepadatan tinggi (jumlah grup kecil), algoritme ini membutuhkan memori yang jauh lebih sedikit daripada saat pengurutan eksplisit diperlukan.

Pertimbangkan dua kueri berikut (sebut saja Kueri 1 dan Kueri 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);

Gambar 3 membandingkan pemberian memori untuk kueri ini.

Gambar 3:Rencana untuk Kueri 1 dan Kueri 2

Perhatikan perbedaan besar antara pemberian memori dalam dua kasus.

Untuk biaya operator Hash Aggregate, kembali ke Gambar 1, perhatikan bahwa tidak ada biaya I/O, melainkan hanya biaya CPU. Selanjutnya, cobalah untuk merekayasa balik rumus penetapan biaya CPU menggunakan teknik serupa dengan yang saya bahas di bagian sebelumnya dalam seri ini. Faktor-faktor yang berpotensi mempengaruhi biaya operator adalah jumlah baris input, jumlah grup keluaran, fungsi agregat yang digunakan, dan apa yang Anda kelompokkan (kardinalitas kumpulan pengelompokan, tipe data yang digunakan).

Anda mengharapkan operator ini memiliki biaya awal dalam persiapan untuk membangun tabel hash. Anda juga mengharapkannya untuk menskalakan secara linier sehubungan dengan jumlah baris dan grup. Itu memang yang saya temukan. Namun, sementara biaya operator Stream Agregat dan Sortir tidak dipengaruhi oleh apa yang Anda kelompokkan, tampaknya biaya operator Hash Aggregate adalah—baik dalam hal kardinalitas kumpulan pengelompokan dan tipe data yang digunakan.

Untuk mengamati bahwa kardinalitas kumpulan pengelompokan memengaruhi biaya operator, periksa biaya CPU operator Hash Aggregate dalam paket untuk kueri berikut (sebut saja Kueri 3 dan Kueri 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);

Tentu saja, Anda ingin memastikan bahwa perkiraan jumlah baris input dan grup output sama dalam kedua kasus. Perkiraan rencana untuk kueri ini ditunjukkan pada Gambar 4.

Gambar 4:Rencana untuk Kueri 3 dan Kueri 4

Seperti yang Anda lihat, biaya CPU dari operator Hash Aggregate adalah 0,16903 saat mengelompokkan menurut satu kolom bilangan bulat, dan 0,174016 saat mengelompokkan dengan dua kolom bilangan bulat, dengan yang lainnya sama. Artinya, kardinalitas himpunan pengelompokan memang mempengaruhi biaya.

Mengenai apakah tipe data dari elemen yang dikelompokkan memengaruhi biaya, saya menggunakan kueri berikut untuk memeriksanya (sebut saja Kueri 5, Kueri 6, dan Kueri 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);

Paket untuk ketiga kueri memiliki perkiraan jumlah baris input dan grup keluaran yang sama, namun semuanya mendapatkan perkiraan biaya CPU yang berbeda (0,121766, 0,16903, dan 0,171716), oleh karena itu jenis data yang digunakan memang memengaruhi biaya.

Jenis fungsi agregat juga tampaknya berdampak pada biaya. Misalnya, pertimbangkan dua kueri berikut (sebut saja Kueri 8 dan Kueri 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);

Perkiraan biaya CPU untuk Agregat Hash dalam paket untuk Kueri 8 adalah 0,166344, dan di Kueri 9 adalah 0,16903.

Ini bisa menjadi latihan yang menarik untuk mencoba dan mencari tahu dengan tepat bagaimana kardinalitas himpunan pengelompokan, tipe data, dan fungsi agregat yang digunakan mempengaruhi biaya; Saya hanya tidak mengejar aspek penetapan biaya ini. Jadi, setelah membuat pilihan kumpulan pengelompokan dan fungsi agregat untuk kueri Anda, Anda dapat merekayasa balik rumus penetapan biaya. Misalnya, mari kita rekayasa balik rumus biaya CPU untuk operator Hash Aggregate saat mengelompokkan berdasarkan satu kolom integer dan mengembalikan agregat MAX(orderdate). Rumusnya harus:

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;