Memaksa Perbedaan Aliran

19

Saya punya tabel seperti ini:

CREATE TABLE Updates
(
    UpdateId INT NOT NULL IDENTITY(1,1) PRIMARY KEY,
    ObjectId INT NOT NULL
)

Pada dasarnya pelacakan pembaruan ke objek dengan ID yang meningkat.

Konsumen tabel ini akan memilih sepotong 100 objek ID yang berbeda, dipesan oleh UpdateId dan mulai dari yang spesifik UpdateId. Pada dasarnya, catat di mana ia tinggalkan dan kemudian minta pembaruan.

Saya menemukan ini sebagai masalah optimisasi yang menarik karena saya hanya dapat menghasilkan rencana kueri yang optimal dengan menulis kueri yang kebetulan melakukan apa yang saya inginkan karena indeks, tetapi tidak menjamin apa yang saya inginkan:

SELECT DISTINCT TOP 100 ObjectId
FROM Updates
WHERE UpdateId > @fromUpdateId

Dimana @fromUpdateId parameter prosedur tersimpan.

Dengan rencana:

SELECT <- TOP <- Hash match (flow distinct, 100 rows touched) <- Index seek

Karena pencarian pada UpdateIdindeks yang digunakan, hasilnya sudah bagus dan dipesan dari ID pembaruan terendah ke tertinggi seperti yang saya inginkan. Dan ini menghasilkan rencana aliran yang berbeda , yang saya inginkan. Tapi pemesanan jelas bukan perilaku terjamin, jadi saya tidak ingin menggunakannya.

Trik ini juga menghasilkan rencana kueri yang sama (meskipun dengan TOP yang berlebihan):

WITH ids AS
(
    SELECT ObjectId
    FROM Updates
    WHERE UpdateId > @fromUpdateId
    ORDER BY UpdateId OFFSET 0 ROWS
)
SELECT DISTINCT TOP 100 ObjectId FROM ids

Padahal, saya tidak yakin (dan curiga tidak) apakah ini benar-benar menjamin pemesanan.

Satu pertanyaan yang saya harap SQL Server akan cukup pintar untuk disederhanakan adalah ini, tetapi akhirnya menghasilkan rencana permintaan yang sangat buruk:

SELECT TOP 100 ObjectId
FROM Updates
WHERE UpdateId > @fromUpdateId
GROUP BY ObjectId
ORDER BY MIN(UpdateId)

Dengan rencana:

SELECT <- Top N Sort <- Hash Match aggregate (50,000+ rows touched) <- Index Seek

Saya mencoba menemukan cara untuk menghasilkan rencana optimal dengan pencarian indeks UpdateIddan aliran yang berbeda untuk menghapus duplikat ObjectId. Ada ide?

Sampel data jika Anda menginginkannya. Objek jarang akan memiliki lebih dari satu pembaruan, dan seharusnya hampir tidak pernah memiliki lebih dari satu pembaruan dalam satu set 100 baris, itulah sebabnya saya mencari alur yang berbeda , kecuali ada sesuatu yang lebih baik yang tidak saya ketahui? Namun, tidak ada jaminan bahwa satu ObjectIdtidak akan memiliki lebih dari 100 baris dalam tabel. Tabel ini memiliki lebih dari 1.000.000 baris dan diperkirakan akan tumbuh dengan cepat.

Asumsikan pengguna ini memiliki cara lain untuk menemukan yang sesuai selanjutnya @fromUpdateId. Tidak perlu mengembalikannya dalam permintaan ini.

Cory Nelson
sumber

Jawaban:

15

Pengoptimal SQL Server tidak dapat menghasilkan rencana eksekusi yang Anda kejar dengan jaminan yang Anda butuhkan, karena operator Hash Match Flow Distinct tidak mempertahankan pesanan.

Padahal, saya tidak yakin (dan curiga tidak) apakah ini benar-benar menjamin pemesanan.

Anda dapat mengamati pelestarian pesanan dalam banyak kasus, tetapi ini adalah detail implementasi; tidak ada jaminan, jadi Anda tidak bisa mengandalkannya. Seperti biasa, urutan presentasi hanya dapat dijamin oleh tingkat atasORDER BY klausa .

Contoh

Script di bawah ini menunjukkan bahwa Hash Match Flow Distinct tidak menjaga ketertiban. Itu mengatur tabel yang dimaksud dengan angka yang cocok 1-50.000 di kedua kolom:

IF OBJECT_ID(N'dbo.Updates', N'U') IS NOT NULL
    DROP TABLE dbo.Updates;
GO
CREATE TABLE Updates
(
    UpdateId INT NOT NULL IDENTITY(1,1),
    ObjectId INT NOT NULL,

    CONSTRAINT PK_Updates_UpdateId PRIMARY KEY (UpdateId)
);
GO
INSERT dbo.Updates (ObjectId)
SELECT TOP (50000)
    ObjectId =
        ROW_NUMBER() OVER (
            ORDER BY C1.[object_id]) 
FROM sys.columns AS C1
CROSS JOIN sys.columns AS C2
ORDER BY
    ObjectId;

Permintaan tes adalah:

DECLARE @Rows bigint = 50000;

-- Optimized for 1 row, but will be 50,000 when executed
SELECT DISTINCT TOP (@Rows)
    U.ObjectId 
FROM dbo.Updates AS U
WHERE 
    U.UpdateId > 0
OPTION (OPTIMIZE FOR (@Rows = 1));

Perkiraan rencana menunjukkan indeks pencarian dan aliran berbeda:

Perkiraan rencana

Outputnya tentu saja diperintahkan untuk memulai dengan:

Mulai dari hasil

... tetapi semakin jauh nilai mulai hilang ':

Pola mogok

...dan akhirnya:

Kekacauan pecah

Penjelasan dalam kasus khusus ini, adalah bahwa operator hash menumpahkan:

Rencana pasca-eksekusi

Setelah partisi tumpah, semua baris yang hash ke partisi yang sama juga tumpah. Partisi yang tumpah diproses nanti, melanggar harapan bahwa nilai-nilai berbeda yang ditemui akan dipancarkan segera dalam urutan mereka diterima.


Ada banyak cara untuk menulis kueri yang efisien untuk menghasilkan hasil yang Anda inginkan, seperti rekursi atau menggunakan kursor. Namun, itu tidak dapat dilakukan dengan menggunakan Hash Match Flow Distinct .

Paul White mengatakan GoFundMonica
sumber
11

Saya tidak puas dengan jawaban ini karena saya tidak bisa mendapatkan aliran operator yang berbeda bersama dengan hasil yang dijamin benar. Namun, saya punya alternatif yang harus mendapatkan kinerja yang baik bersama dengan hasil yang benar. Sayangnya itu mengharuskan indeks nonclustered dibuat di atas meja.

Saya mendekati masalah ini dengan mencoba memikirkan kombinasi kolom yang saya bisa ORDER BYdan mendapatkan hasil yang benar setelah menerapkannya DISTINCT. Nilai minimum UpdateIdper ObjectIdbersama dengan ObjectIdsalah satu kombinasi tersebut. Namun, secara langsung meminta minimum UpdateIdtampaknya menghasilkan membaca semua baris dari tabel. Sebagai gantinya, kami secara tidak langsung dapat meminta nilai minimum dari UpdateIdgabungan lainnya ke tabel. Idenya adalah untuk memindai Updatestabel secara berurutan, membuang setiap baris yang UpdateIdbukan nilai minimum untuk baris itu ObjectId, dan mempertahankan 100 baris pertama. Berdasarkan uraian Anda tentang distribusi data, kami tidak perlu membuang banyak baris.

Untuk persiapan data, saya menempatkan 1 juta baris ke tabel dengan 2 baris untuk setiap ObjectId yang berbeda:

INSERT INTO Updates WITH (TABLOCK)
SELECT t.RN / 2
FROM 
(
    SELECT TOP 1000000 -1 + ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) RN
    FROM master..spt_values t1
    CROSS JOIN master..spt_values t2
) t;

CREATE INDEX IX On Updates (Objectid, UpdateId);

Indeks nonclustered aktif Objectiddan UpdateIdpenting. Hal ini memungkinkan kami untuk secara efisien membuang baris yang tidak memiliki minimum UpdateIdper Objectid. Ada banyak cara untuk menulis kueri yang cocok dengan deskripsi di atas. Berikut ini salah satu cara menggunakan NOT EXISTS:

DECLARE @fromUpdateId INT = 9999;
SELECT ObjectId
FROM (
    SELECT DISTINCT TOP 100 u1.UpdateId, u1.ObjectId
    FROM Updates u1
    WHERE UpdateId > @fromUpdateId
    AND NOT EXISTS (
        SELECT 1
        FROM Updates u2
        WHERE u2.UpdateId > @fromUpdateId
        AND u1.ObjectId = u2.ObjectId
        AND u2.UpdateId < u1.UpdateId
    )
    ORDER BY u1.UpdateId, u1.ObjectId
) t;

Ini gambar rencana kueri :

rencana permintaan

Dalam kasus terbaik SQL Server hanya akan melakukan 100 indeks berusaha terhadap indeks nonclustered. Untuk mensimulasikan menjadi sangat sial, saya mengubah kueri untuk mengembalikan 5.000 baris pertama ke klien. Itu menghasilkan indeks pencarian 9999, jadi itu seperti mendapatkan rata-rata 100 baris per berbeda ObjectId. Ini adalah output dari SET STATISTICS IO, TIME ON:

Tabel 'Pembaruan'. Pindai hitung 10.000, bacaan logis 31900, bacaan fisik 0

Waktu Eksekusi SQL Server: Waktu CPU = 31 ms, waktu yang berlalu = 42 ms.

Joe Obbish
sumber
9

Saya suka pertanyaan - Flow Distinct adalah salah satu operator favorit saya.

Sekarang, jaminan adalah masalahnya. Ketika Anda berpikir tentang operator FD yang menarik baris dari operator Seek dengan cara yang teratur, menghasilkan setiap baris karena menentukannya unik, ini akan memberi Anda baris dalam urutan yang benar. Tetapi sulit untuk mengetahui apakah mungkin ada beberapa skenario di mana FD tidak menangani satu baris pada satu waktu.

Secara teoritis, FD dapat meminta 100 baris dari Seek, dan memproduksinya dalam urutan apa pun yang mereka butuhkan.

Petunjuk kueri OPTION (FAST 1, MAXDOP 1)bisa membantu, karena itu akan menghindari mendapatkan lebih banyak baris daripada yang dibutuhkan dari operator Seek. Apakah itu jaminan ? Tidak terlalu. Itu masih bisa memutuskan untuk menarik satu halaman baris pada satu waktu, atau sesuatu seperti itu.

Saya pikir dengan OPTION (FAST 1, MAXDOP 1), OFFSETversi Anda akan memberi Anda banyak kepercayaan tentang pesanan, tetapi itu bukan jaminan.

Rob Farley
sumber
Seperti yang saya mengerti, masalahnya adalah bahwa operator Flow Distinct menggunakan tabel hash yang dapat tumpah ke disk. Ketika ada tumpahan, baris yang dapat diproses menggunakan bagian yang masih dalam RAM diproses segera, tetapi baris lainnya tidak diproses sampai data yang tumpah dibaca kembali dari disk. Dari apa yang bisa saya katakan, operator mana pun yang menggunakan tabel hash (seperti Hash Join) tidak dijamin untuk menjaga ketertiban karena perilaku tumpahnya.
sam.bishop
Benar. Lihat jawabannya oleh Paul White.
Rob Farley