Apa algoritma di belakang operator KECUALI?

Apa algoritma internal tentang bagaimana operator Kecuali bekerja di bawah selimut di SQL Server? Apakah secara internal mengambil hash dari setiap baris dan membandingkan?

David Lozinksi menjalankan penelitian, SQL: Cara tercepat untuk menyisipkan catatan baru di mana orang belum ada. Dia menunjukkan Kecuali pernyataan adalah yang tercepat untuk baris jumlah besar; terikat erat dengan hasil kami di bawah ini.

Asumsi: Saya pikir Left join akan menjadi yang tercepat, karena hanya membandingkan 1 kolom, Kecuali akan memakan waktu paling lama, karena harus membandingkan Semua kolom.
Dengan hasil ini, sekarang pemikiran kita adalah Kecuali secara otomatis dan internal mengambil hash dari setiap baris? Saya melihat Kecuali rencana eksekusi dan tidak menggunakan beberapa hash.

Latar belakang: Tim kami membandingkan dua tabel tumpukan. Tabel A Baris tidak pada Tabel B, dimasukkan ke dalam Tabel B.

Heap tables (dari filesystem teks lama) tidak memiliki kunci utama / pengarah / pengidentifikasi. Beberapa tabel memiliki baris duplikat, jadi kami menemukan Hash setiap baris, dan menghapus duplikat, dan membuat pengidentifikasi kunci utama.

1) Pertama kami menjalankan pernyataan kecuali, tidak termasuk (kolom hash)

select * from TableA
Except
Select * from TableB,

2) Kemudian kami menjalankan perbandingan gabungan kiri antara dua tabel pada HashRowId

select * 
FROM dbo.TableA A
left join dbo.TableB B
    on A.RowHash =  B.RowHash
where B.Hash is null

secara mengejutkan Sisipan Pernyataan Kecuali adalah yang tercepat.

Hasil sebenarnya memetakan dekat dengan hasil pengujian dari David Lozinksi

Apa algoritma internal tentang bagaimana operator Kecuali bekerja di bawah selimut di SQL Server?

Saya tidak akan mengatakan bahwa ada algoritma internal khusus untuk EXCEPT. Sebab A EXCEPT B, mesin mengambil tupel berbeda (jika perlu) dari A dan mengurangi baris yang cocok dengan B. Tidak ada operator rencana kueri khusus. Perbedaan dan pengurangan diterapkan melalui operator biasa yang akan Anda lihat dengan pengurutan atau dengan gabungan. Gabung bersarang loop, gabung gabung, dan gabung hash semua didukung. Untuk menunjukkan ini, saya akan membuang 15 juta baris ke dalam tumpukan:

DROP TABLE IF EXISTS dbo.TABLE_1;

CREATE TABLE dbo.TABLE_1 (
    COL1 BIGINT NULL,
    COL2 BIGINT NULL
);

INSERT INTO dbo.TABLE_1 WITH (TABLOCK)
SELECT TOP (15000000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)), NULL
FROM master..spt_values t1
CROSS JOIN master..spt_values t2
OPTION (MAXDOP 1);


DROP TABLE IF EXISTS dbo.TABLE_2;

CREATE TABLE dbo.TABLE_2 (
    COL1 BIGINT NULL,
    COL2 BIGINT NULL
);

INSERT INTO dbo.TABLE_2 WITH (TABLOCK)
SELECT TOP (15000000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)), NULL
FROM master..spt_values t1
CROSS JOIN master..spt_values t2
OPTION (MAXDOP 1);

Pengoptimal menjadikannya keputusan berbasis biaya biasa tentang bagaimana menerapkan pengurutan dan bergabung. Dengan dua tumpukan saya mendapatkan hash bergabung seperti yang diharapkan. Anda bisa melihat tipe gabungan lainnya secara alami dengan menambahkan indeks atau dengan mengubah data di salah satu tabel. Di bawah ini saya memaksa gabungan dan loop bergabung dengan petunjuk hanya untuk tujuan ilustrasi:

Apakah secara internal mengambil hash dari setiap baris dan membandingkan?

Tidak. Ini diterapkan seperti yang lainnya. Salah satu perbedaannya adalah bahwa NULL diperlakukan sama. Ini adalah jenis khusus dari perbandingan yang dapat Anda lihat dalam rencana eksekusi: <Compare CompareOp="IS">. Namun, Anda bisa mendapatkan paket yang sama dengan T-SQL yang tidak menyertakan EXCEPTkata kunci. Misalnya, berikut ini memiliki rencana kueri yang sama persis dengan EXCEPTkueri yang menggunakan hash bergabung:

SELECT t1.*
FROM
(
    SELECT DISTINCT COL1, COL2
    FROM dbo.TABLE_1
) t1
WHERE NOT EXISTS (
    SELECT 1
    FROM dbo.TABLE_2 t2
    WHERE (t1.COL1 = t2.COL1 OR (t1.COL1 IS NULL AND t2.COL1 IS NULL))
    AND (t1.COL2 = t2.COL2 OR (t1.COL2 IS NULL AND t2.COL2 IS NULL))
);

Diffing XML dari rencana eksekusi hanya mengungkapkan perbedaan dangkal di sekitar alias dan hal-hal seperti itu. Sisa probe untuk hash bergabung melakukan perbandingan baris. Mereka sama untuk kedua pertanyaan:

Jika Anda masih ragu, saya menjalankan PerfView dengan laju sampel tertinggi yang tersedia untuk mendapatkan tumpukan panggilan untuk kueri dengan EXCEPTdan kueri tanpa itu. Berikut adalah hasilnya secara berdampingan:

Tidak ada perbedaan nyata. Tumpukan panggilan ada hashing referensi hadir karena cocok hash dalam rencana. Jika saya menambahkan indeks untuk menggabungkan gabungan alami, Anda tidak akan melihat referensi apa pun untuk hashing di tumpukan panggilan:

Setiap hashing yang terjadi adalah karena implementasi operator hash match. Tidak ada sesuatu yang istimewa tentang EXCEPTyang mengarah ke perbandingan hashing internal khusus.