Menyesuaikan Pasokan Dengan Permintaan — Solusi, Bagian 3

Dalam artikel ini, saya terus mengeksplorasi solusi untuk mencocokkan penawaran dengan tantangan permintaan. Terima kasih kepada Luca, Kamil Kosno, Daniel Brown, Brian Walker, Joe Obbish, Rainer Hoffmann, Paul White, Charlie, Ian, dan Peter Larsson, yang telah mengirimkan solusi Anda.

Bulan lalu saya membahas solusi berdasarkan pendekatan persimpangan interval yang direvisi dibandingkan dengan yang klasik. Yang tercepat dari solusi tersebut menggabungkan ide dari Kamil, Luca, dan Daniel. Ini menyatukan dua pertanyaan dengan predikat sargable yang terputus-putus. Solusinya membutuhkan waktu 1,34 detik untuk menyelesaikan input 400K-baris. Itu tidak terlalu buruk mengingat solusi berdasarkan pendekatan persimpangan interval klasik membutuhkan waktu 931 detik untuk diselesaikan dengan input yang sama. Ingat juga Joe datang dengan solusi brilian yang mengandalkan pendekatan persimpangan interval klasik tetapi mengoptimalkan logika pencocokan dengan mengelompokkan interval berdasarkan panjang interval terbesar. Dengan input 400K-baris yang sama, solusi Joe membutuhkan waktu 0,9 detik untuk menyelesaikannya. Bagian yang sulit dari solusi ini adalah kinerjanya menurun seiring dengan bertambahnya panjang interval terbesar.

Bulan ini saya mengeksplorasi solusi menarik yang lebih cepat daripada solusi Persimpangan Revisi Kamil/Luca/Daniel dan netral terhadap panjang interval. Solusi dalam artikel ini dibuat oleh Brian Walker, Ian, Peter Larsson, Paul White, dan saya.

Saya menguji semua solusi dalam artikel ini terhadap tabel input Lelang dengan baris 100K, 200K, 300K, dan 400K, dan dengan indeks berikut:

-- Indeks untuk mendukung solusi BUAT INDEKS NONCLUSTERED UNIK idx_Code_ID_i_Quantity ON dbo.Auctions(Code, ID) INCLUDE(Quantity); -- Aktifkan mode batch Jendela Agregat CREATE NONCLUSTERED COLUMNSTORE INDEX idx_cs ON dbo.Auctions(ID) WHERE ID =-1 AND ID =-2;

Saat menjelaskan logika di balik solusi, saya akan menganggap tabel Lelang diisi dengan kumpulan kecil data sampel berikut:

Jumlah Kode ID----------- ---- ---------1 D 5.0000002 D 3.000.0003 D 8.000.0005 D 2.0000006 D 8.000007 D 4.0000008 D 2.0000001000 S 8.000.0002000 S 6.0000003000 S 2.0000004000 S 2.0000005000 S 4.0000006000 S 3.000.0007000 S 2.000000

Berikut adalah hasil yang diinginkan untuk data sampel ini:

DemandID SupplyID TradeQuantity----------- ----------- --------------1 1000 5.0000002 1000 3.000.0003 2000 6.000003 3000 2.0000005 4000 2.0000006 5000 4.0000006 6000 3.000.0006 7000 1.000.0007 7000 1.000.000

Solusi Brian Walker

Gabungan luar cukup umum digunakan dalam solusi kueri SQL, tetapi sejauh ini ketika Anda menggunakannya, Anda menggunakan yang satu sisi. Saat mengajar tentang outer join, saya sering mendapat pertanyaan yang menanyakan contoh kasus penggunaan praktis full outer join, dan jumlahnya tidak banyak. Solusi Brian adalah contoh yang bagus dari kasus penggunaan praktis dari gabungan luar penuh.

Berikut kode solusi lengkap Brian:

DROP TABLE JIKA ADA #MyPairings; BUAT TABEL #MyPairings( DemandID INT NOT NULL, SupplyID INT NOT NULL, TradeQuantity DECIMAL(19,06) NOT NULL); DENGAN D AS( SELECT A.ID, SUM(A.Quantity) OVER (PARTITION BY A.Code ORDER BY A.ID ROWS UNBOUNDED PRECEDING) AS Running FROM dbo.Auctions AS A WHERE A.Code ='D'),S AS( SELECT A.ID, SUM(A.Quantity) OVER (PARTITION BY A.Code ORDER BY A.ID ROWS UNBOUNDED PRECEDING) AS Running FROM dbo.Auctions AS A WHERE A.Code ='S'),W AS( SELECT D.ID AS DemandID, S.ID AS SupplyID, ISNULL(D.Running, S.Running) AS Running FROM D FULL JOIN S ON D.Running =S.Running),Z AS( SELECT CASE WHEN W.DemandID IS NOT NULL MAKA W.DemandID ELSE MIN(W.DemandID) OVER (PESAN OLEH W.Running ROW ANTARA ROW SAAT INI DAN UNBOUNDED FOLLOWING) BERAKHIR SEBAGAI DemandID, KASUS KETIKA W.SupplyID TIDAK NULL MAKA W.SupplyID ELSEID MIN(W. ) LEBIH (PESAN MENURUT W.Running BARIS ANTARA BARIS SAAT INI DAN UNBOUNDED BERIKUT) BERAKHIR SEBAGAI SupplyID, W.Running FROM W)INSERT #MyPair ings( DemandID, SupplyID, TradeQuantity ) PILIH Z.DemandID, Z.SupplyID, Z.Running - ISNULL(LAG(Z.Running) OVER (ORDER BY Z.Running), 0.0) SEBAGAI TradeQuantity DARI Z MANA Z.DemandID TIDAK NULL DAN Z.SupplyID BUKAN NULL;

Saya merevisi penggunaan asli tabel turunan Brian dengan CTE untuk kejelasan.

CTE D menghitung jumlah total permintaan yang berjalan di kolom hasil yang disebut D.Running, dan CTE S menghitung jumlah total pasokan yang berjalan di kolom hasil yang disebut S.Running. CTE W kemudian melakukan gabungan luar penuh antara D dan S, mencocokkan D.Running dengan S.Running, dan mengembalikan non-NULL pertama di antara D.Running dan S.Running sebagai W.Running. Inilah hasil yang Anda dapatkan jika Anda menanyakan semua baris dari W yang dipesan dengan Menjalankan:

DemandID SupplyID Berjalan----------- ----------- ----------1 NULL 5.0000002 1000 8.000.000NULL 2000 14.000003 3000 16.0000005 4000 18.000.000 NULL 5000 22.000000NULL 6000 25.0000006 NULL 26.000000NULL 7000 27.0000007 NULL 30.0000008 NULL 32.000000 

Ide untuk menggunakan full outer join berdasarkan predikat yang membandingkan total permintaan dan penawaran yang berjalan adalah ide yang jenius! Sebagian besar baris dalam hasil ini—9 pertama dalam kasus kami—mewakili pasangan hasil dengan sedikit perhitungan tambahan yang hilang. Baris dengan ID NULL trailing dari salah satu jenis mewakili entri yang tidak dapat dicocokkan. Dalam kasus kami, dua baris terakhir mewakili entri permintaan yang tidak dapat dicocokkan dengan entri penawaran. Jadi, yang tersisa di sini adalah menghitung DemandID, SupplyID, dan TradeQuantity dari pasangan hasil, dan untuk memfilter entri yang tidak dapat dicocokkan.

Logika yang menghitung hasil DemandID dan SupplyID dilakukan di CTE Z sebagai berikut (dengan asumsi memesan di W dengan Menjalankan):

• DemandID:jika DemandID bukan NULL maka DemandID, jika tidak, DemandID minimum dimulai dengan baris saat ini
• SupplyID:jika SupplyID bukan NULL maka SupplyID, jika tidak, SupplyID minimum dimulai dengan baris saat ini

Inilah hasil yang Anda dapatkan jika Anda meminta Z dan memesan baris dengan Menjalankan:

DemandID SupplyID Berjalan----------- ----------- ----------1 1000 5.0000002 1000 8.000.0003 2000 14.000003 3000 16.0000005 4000 18.000006 5000 22.0000006 6000 25.0000006 7000 26.0000007 7000 27.0000007 NULL 30.0000008 NULL 32.000000

Kueri luar menyaring baris dari Z yang mewakili entri dari satu jenis yang tidak dapat dicocokkan dengan entri jenis lain dengan memastikan DemandID dan SupplyID tidak NULL. Kuantitas perdagangan pasangan hasil dihitung sebagai nilai Berjalan saat ini dikurangi nilai Berjalan sebelumnya menggunakan fungsi LAG.

Inilah yang ditulis ke tabel #MyPairings, yang merupakan hasil yang diinginkan:

DemandID SupplyID TradeQuantity----------- ----------- --------------1 1000 5.0000002 1000 3.000.0003 2000 6.000003 3000 2.0000005 4000 2.0000006 5000 4.0000006 6000 3.000.0006 7000 1.000.0007 7000 1.000.000

Rencana untuk solusi ini ditunjukkan pada Gambar 1.

Gambar 1:Rencana kueri untuk solusi Brian

Dua cabang teratas dari rencana menghitung total permintaan dan pasokan yang berjalan menggunakan operator Agregat Jendela mode batch, masing-masing setelah mengambil entri masing-masing dari indeks pendukung. Seperti yang saya jelaskan di artikel sebelumnya dalam seri ini, karena indeks sudah memiliki baris yang diurutkan seperti yang dibutuhkan oleh operator Agregat Jendela, Anda akan berpikir operator Sortir eksplisit tidak diperlukan. Tetapi SQL Server saat ini tidak mendukung kombinasi efisien dari operasi indeks pelestarian urutan paralel sebelum operator Agregat Jendela mode batch paralel, sehingga sebagai hasilnya, operator Sortir paralel eksplisit mendahului setiap operator Agregat Jendela paralel.

Paket menggunakan gabungan hash mode batch untuk menangani gabungan luar penuh. Paket ini juga menggunakan dua operator Agregat Jendela mode batch tambahan yang didahului oleh operator Sortir eksplisit untuk menghitung fungsi jendela MIN dan LAG.

Itu rencana yang cukup efisien!

Berikut adalah waktu berjalan yang saya dapatkan untuk solusi ini terhadap ukuran input mulai dari 100K hingga 400K baris, dalam hitungan detik:

100K:0.368200K:0.845300K:1.255400K:1.315

Solusi Itzik

Solusi berikutnya untuk tantangan ini adalah salah satu upaya saya untuk menyelesaikannya. Berikut kode solusi lengkapnya:

DROP TABLE JIKA ADA #MyPairings; DENGAN C1 AS( SELECT *, SUM(Quantity) OVER(PARTITION BY Code ORDER BY ID ROWS UNBOUNDED PRECEDING) AS SumQty FROM dbo.Auctions),C2 AS( SELECT *, SUM(Quantity * CASE Code WHEN 'D' THEN -1 WHEN 'S' THEN 1 END) OVER(ORDER BY SumQty, Code ROWS UNBOUNDED PRECEDING) AS StockLevel, LAG(SumQty, 1, 0.0) OVER(ORDER BY SumQty, Code) AS PrevSumQty, MAX(CASE WHEN Code ='D' THEN ID END) OVER(ORDER BY SumQty, Code ROWS UNBOUNDED PRECEDING) AS PrevDemandID, MAX(CASE WHEN Code ='S' THEN ID END) OVER(ORDER BY SumQty, Code ROWS UNBOUNDED PRECEDING) AS PrevSupplyID, MIN(CASE EN Code ='D' THEN ID END) OVER(ORDER BY SumQty, Code ROWS ANTARA CURRENT ROW DAN UNBOUNDED FOLLOWING) AS NextDemandID, MIN(CASE WHEN Code ='S' THEN THEN ID END) OVER(ORDER BY SumQty, Kode BARIS ANTARA CURRENT ROW DAN UNBOUNDED FOLLOWING) SEBAGAI NextSupplyID DARI C1),C3 AS( SELECT *, CASE Code WHEN 'D ' KEMUDIAN ID KETIKA 'S' KASUS KETIKA StockLevel> 0 THEN NextDemandID ELSE PrevDemandID AKHIR SEBAGAI DemandID, KASUS KODE KETIKA 'S' MAKA ID KETIKA 'D' KASUS KETIKA StockLevel <=0 THEN NextSupplyID ELSE ID Pasokan AKHIR SEBAGAI SumQty - PrevSumQty SEBAGAI TradeQuantity DARI C2)PILIH DemandID, SupplyID, TradeQuantityINTO #MyPairingsFROM C3WHERE TradeQuantity> 0,0 DAN DemandID TIDAK NULL DAN SupplyID BUKAN NULL;

CTE C1 mengkueri tabel Lelang dan menggunakan fungsi jendela untuk menghitung jumlah permintaan dan pasokan total yang berjalan, dengan memanggil kolom hasil SumQty.

CTE C2 mengkueri C1, dan menghitung sejumlah atribut menggunakan fungsi jendela berdasarkan urutan SumQty dan Kode:

• Level Stok:Level stok saat ini setelah memproses setiap entri. Ini dihitung dengan memberikan tanda negatif untuk jumlah permintaan dan tanda positif untuk jumlah penawaran dan menjumlahkan jumlah tersebut hingga dan termasuk entri saat ini.
• PrevSumQty:Nilai SumQty baris sebelumnya.
• PrevDemandID:ID permintaan non-NULL terakhir.
• PrevSupplyID:ID persediaan non-NULL terakhir.
• NextDemandID:ID permintaan non-NULL berikutnya.
• NextSupplyID:ID persediaan non-NULL berikutnya.

Berikut isi C2 yang dipesan oleh SumQty dan Kode:

Kode ID Kuantitas SumQty StockLevel SebelumnyaJumlahQty SebelumnyaDemandID SebelumnyaSupplyID BerikutnyaDemandID NextSupplyID----- ---- --------- ---------- --------- ------------ ------------ ------------ ------------ - -----------1 D 5.000.000 5.000.000 -5.000000 0.000000 1 NULL 1 10002 D 3.000.000 8.000.000 -8.000.000 5.000.000 2 NULL 2 10001000 S 8.000.000 8.000.000 0.000000 8.000.000 2 1000 3 10002000 S 6.000000 14.000.000 6.000.000 8.000.000 2 2000 3 20003 D 8.000.000 16.000.000 -2.000000 14.00000 3 2000 3 30003000 S 2.000000 16.000000 0.000000 16.000000 3 3000 5 30005 D 2.000000 18.000.000 -2.000000 16.000000 5 3000 5 40004000 S 2.000000 18.000.000 0.000000 18.00000 5 4000 6 40005000 S 4,000000 22,000000 4,000000 18,000000 5 5000 6 50006000 S 3,000000 25.000000 7.000000 22.000000 5 6000 6 60006 D 8.000.000 26.000000 -1.000000 25.000000 6 6000 6 70007000 S 2.000000 27.000000 1.000.000 26.000000 6 7000 7 70007 D 4.00000 30.000000 -3.000.000 27.000000 NULL 7 7000 32.000000 -5.000000 30.000000 8 7000 8 NULL

CTE C3 mengkueri C2 dan menghitung DemandID, SupplyID, dan TradeQuantity pasangan hasil, sebelum menghapus beberapa baris yang berlebihan.

Kolom C3.DemandID hasil dihitung seperti ini:

• Jika entri saat ini adalah entri permintaan, kembalikan DemandID.
• Jika entri saat ini adalah entri persediaan dan tingkat stok saat ini positif, kembalikan NextDemandID.
• Jika entri saat ini adalah entri persediaan dan tingkat stok saat ini tidak positif, kembalikan PrevDemandID.

Hasil kolom C3.SupplyID dihitung seperti ini:

• Jika entri saat ini adalah entri persediaan, kembalikan SupplyID.
• Jika entri saat ini adalah entri permintaan dan tingkat stok saat ini tidak positif, kembalikan NextSupplyID.
• Jika entri saat ini adalah entri permintaan dan tingkat stok saat ini positif, kembalikan PrevSupplyID.

Hasil TradeQuantity dihitung sebagai SumQty baris saat ini dikurangi PrevSumQty.

Berikut adalah isi kolom yang relevan dengan hasil dari C3:

DemandID SupplyID TradeQuantity----------- ----------- --------------1 1000 5.0000002 1000 3.000.0002 1000 0.0000003 2000 6.0000003 3000 2.0000003 3000 0.0000005 4000 2.0000005 4000 0.0000006 5000 4.000.0006 6000 3.000.0006 7000 1.000007 7000 1.000007 NULL 3.0000008 NULL 2.000000

Apa yang tersisa untuk dilakukan kueri luar adalah memfilter baris yang berlebihan dari C3. Itu termasuk dua kasus:

• Ketika total berjalan dari kedua jenis adalah sama, entri pasokan memiliki kuantitas perdagangan nol. Ingat pemesanan didasarkan pada SumQty dan Kode, jadi ketika total berjalan sama, entri permintaan muncul sebelum entri pasokan.
• Entri trailing dari satu jenis yang tidak dapat dicocokkan dengan entri dari jenis lainnya. Entri tersebut diwakili oleh baris di C3 di mana DemandID adalah NULL atau SupplyID adalah NULL.

Rencana untuk solusi ini ditunjukkan pada Gambar 2.

Gambar 2:Rencana kueri untuk solusi Itzik

Rencana tersebut menerapkan satu lintasan data masukan dan menggunakan empat operator Agregat Jendela mode batch untuk menangani berbagai komputasi berjendela. Semua operator Agregat Jendela didahului oleh operator Sortir eksplisit, meskipun hanya dua di antaranya yang tidak dapat dihindari di sini. Dua lainnya berkaitan dengan implementasi saat ini dari operator Agregat Jendela mode batch paralel, yang tidak dapat mengandalkan input pelestarian pesanan paralel. Cara sederhana untuk melihat operator Urutkan mana yang disebabkan oleh alasan ini adalah dengan memaksakan rencana serial dan melihat operator Urutkan mana yang hilang. Saat saya memaksakan paket serial dengan solusi ini, operator Urutkan pertama dan ketiga menghilang.

Berikut adalah waktu berjalan dalam hitungan detik yang saya dapatkan untuk solusi ini:

100K:0.246200K:0.427300K:0.616400K:0.841>

Solusi Ian

Solusi Ian singkat dan efisien. Berikut kode solusi lengkapnya:

DROP TABLE JIKA ADA #MyPairings; DENGAN A AS ( SELECT *, SUM(Quantity) OVER (PARTITION BY Code ORDER BY ID ROWS UNBOUNDED PRECEDING) AS CumulativeQuantity FROM dbo.Auctions), B AS ( SELECT CumulativeQuantity, CumulativeQuantity - LAG(CumulativeQuantity, 1, 0) OVER (ORDER OLEH CumulativeQuantity) AS TradeQuantity, MAX(CASE WHEN Code ='D' THEN THEN ID END) AS DemandID, MAX(CASE WHEN Code ='S' THEN ID END) AS SupplyID DARI GROUP BY CumulativeQuantity, ID/ID -- pengelompokan palsu untuk meningkatkan perkiraan baris -- (jumlah baris Lelang bukannya 2 baris)), C AS ( -- isi NULL dengan penawaran/permintaan berikutnya -- FIRST_VALUE(ID) IGNORE NULLS OVER ... -- akan lebih baik, tetapi ini akan berfungsi karena ID berada dalam urutan KumulatifQuantity SELECT MIN(DemandID) OVER (ORDER BY CumulativeQuantity ROWS ANTARA CURRENT ROW DAN UNBOUNDED FOLLOWING) SEBAGAI DemandID, MIN(SupplyID) OVER (ORDER BY CumulativeQ jumlah BARIS ANTARA BARIS LANCAR DAN UNBOUNDED BERIKUT) SEBAGAI SupplyID, TradeQuantity DARI B)PILIH DemandID, SupplyID, TradeQuantityINTO #MyPairingsFROM CWHERE SupplyID TIDAK NULL -- potong permintaan yang tidak terpenuhi DAN DemandID TIDAK NULL; -- rapikan persediaan yang tidak terpakai

Kode di CTE A mengkueri tabel Lelang dan menghitung jumlah permintaan dan penawaran total yang berjalan menggunakan fungsi jendela, menamai kolom hasil KumulatifKuantitas.

Kode di CTE B mengkueri CTE A, dan mengelompokkan baris menurut Kumulatif Kuantitas. Pengelompokan ini mencapai efek yang mirip dengan gabungan luar Brian berdasarkan total permintaan dan penawaran yang berjalan. Ian juga menambahkan ID/ID ekspresi dummy ke set pengelompokan untuk meningkatkan kardinalitas asli pengelompokan yang diperkirakan. Di komputer saya, ini juga mengakibatkan penggunaan paket paralel alih-alih paket serial.

Dalam daftar SELECT, kode menghitung DemandID dan SupplyID dengan mengambil ID dari masing-masing tipe entri dalam grup menggunakan agregat MAX dan ekspresi CASE. Jika ID tidak ada di grup, hasilnya NULL. Kode juga menghitung kolom hasil yang disebut TradeQuantity sebagai kuantitas kumulatif saat ini dikurangi yang sebelumnya, diambil menggunakan fungsi jendela LAG.

Berikut adalah isi dari B:

KumulatifKuantitas PerdaganganKuantitas PermintaanId PasokanId-------------------- -------------- --------- - -------- 5.000.000 5.000.000 1 NULL 8.000.000 3.000.000 2 100014.000000 6.000000 NULL 200016.000000 2.000000 3 300018.000000 2.000000 5 400022.000000 4.00000 NULL 500025.000000 3.000.000 NULL 600026.000000 1.000.000 6 NULL27.000000 1.000.000 NULL 700030.000000 3.000.000 7 NULL3 2.000000> 

 Kode dalam CTE C kemudian menanyakan CTE B dan mengisi ID permintaan dan penawaran NULL dengan ID permintaan dan suplai non-NULL berikutnya, menggunakan fungsi jendela MIN dengan bingkai BARIS ANTARA CURRENT ROW DAN UNBOUNDED FOLLOWING.
 

 Berikut isi dari C:
 
DemandID SupplyID TradeQuantity --------- --------- --------------1 1000 5.000000 2 1000 3.000.000 3 2000 6.000.000 3 3000 2.000.000 5 4000 2.000000 6 5000 4.000.000 6 6000 3.000.000 6 7000 1.000.000 7 7000 1.000.000 7 NULL 3.000.000 8 NULL 2.000000
 

 Langkah terakhir yang ditangani oleh kueri luar terhadap C adalah menghapus entri dari satu jenis yang tidak dapat dicocokkan dengan entri dari jenis lainnya. Itu dilakukan dengan memfilter baris di mana SupplyID adalah NULL atau DemandID adalah NULL.
 

 Rencana untuk solusi ini ditunjukkan pada Gambar 3.
 

 Gambar 3:Rencana kueri untuk solusi Ian 
 

 Rencana ini melakukan satu pemindaian data input dan menggunakan tiga operator agregat jendela mode batch paralel untuk menghitung berbagai fungsi jendela, semuanya didahului oleh operator Sortir paralel. Dua di antaranya tidak dapat dihindari karena Anda dapat memverifikasi dengan memaksakan rencana serial. Rencana tersebut juga menggunakan operator Hash Aggregate untuk menangani pengelompokan dan agregasi di CTE B.
 

 Berikut adalah waktu berjalan dalam hitungan detik yang saya dapatkan untuk solusi ini:
 
100K:0,214200K:0,363300K:0,546400K:0,701
 

 
 
Solusi Peter Larsson
 

 Solusi Peter Larsson sangat singkat, manis, dan sangat efisien. Berikut kode solusi lengkap Peter:
 
DROP TABLE JIKA ADA #MyPairings; DENGAN cteSource(ID, Code, RunningQuantity)AS( SELECT ID, Code, SUM(Quantity) OVER (PARTITION BY Code ORDER BY ID) AS RunningQuantity FROM dbo.Auctions)SELECT DemandID, SupplyID, TradeQuantityINTO #MyPairingsFROM ( SELECT MIN(CASE WHEN Kode ='D' THEN ID ELSE 2147483648 AKHIR) OVER (PESAN MENURUT RunningQuantity, Kode BARIS ANTARA LAIN LANCAR DAN UNBOUNDED FOLLOWING) SEBAGAI DemandID, MIN(CASE WHEN Code ='S' THEN ID ELSE 2147483648 END) OVER (PESAN, OLEH RunningQuantity Kode BARIS ANTARA BARIS LANCAR DAN UNBOUNDED BERIKUT) SEBAGAI SupplyID, RunningQuantity - COALESCE(LAG(RunningQuantity) OVER (ORDER BY RunningQuantity, Code), 0.0) SEBAGAI TradeQuantity DARI cteSource ) SEBAGAI dWHERE DemandID <2147483648 AND SupplyID <2147483648 AND SupplyID <2147483648 AND SupplyID <2147483648 
 

 CTE cteSource mengkueri tabel Auctions dan menggunakan fungsi jendela untuk menghitung jumlah total permintaan dan pasokan yang berjalan, dengan memanggil kolom hasil RunningQuantity.
 

 Kode yang mendefinisikan tabel turunan d mengkueri cteSource dan menghitung pasangan hasil DemandID, SupplyID, dan TradeQuantity, sebelum menghapus beberapa baris yang berlebihan. Semua fungsi jendela yang digunakan dalam perhitungan tersebut didasarkan pada RunningQuantity dan urutan Kode.
 

 Kolom hasil d.DemandID dihitung sebagai ID permintaan minimum yang dimulai dengan saat ini atau 2147483648 jika tidak ada yang ditemukan.
 

 Kolom hasil d.SupplyID dihitung sebagai ID persediaan minimum yang dimulai dengan saat ini atau 2147483648 jika tidak ada yang ditemukan.
 

 Hasil TradeQuantity dihitung sebagai nilai RunningQuantity baris saat ini dikurangi nilai RunningQuantity baris sebelumnya.
 

 Berikut isi dari d:
 
DemandID SupplyID TradeQuantity--------- ----------- --------------1 1000 5.0000002 1000 3.000.0003 1000 0,0000003 2000 60000003 3000 2.0000005 3000 0.0000005 4000 2.0000006 4000 0.0000006 5000 4.000.0006 6000 3.000.0006 7000 1.0000007 7000 1.000007 2147483648 3.000.0008 2147483648 2.000000
 

 Apa yang tersisa untuk dilakukan kueri luar adalah memfilter baris yang berlebihan dari d. Itu adalah kasus di mana kuantitas perdagangan adalah nol, atau entri dari satu jenis yang tidak dapat dicocokkan dengan entri dari jenis lain (dengan ID 2147483648).
 

 Rencana untuk solusi ini ditunjukkan pada Gambar 4.
 

 Gambar 4:Rencana kueri untuk solusi Peter 
 

 Seperti rencana Ian, rencana Peter bergantung pada satu pemindaian data input dan menggunakan tiga operator agregat jendela mode batch paralel untuk menghitung berbagai fungsi jendela, semuanya didahului oleh operator Sortir paralel. Dua di antaranya tidak dapat dihindari karena Anda dapat memverifikasi dengan memaksakan rencana serial. Dalam paket Peter, tidak diperlukan operator agregat yang dikelompokkan seperti dalam paket Ian.
 

 Wawasan kritis Peter yang memungkinkan solusi singkat seperti itu adalah kesadaran bahwa untuk entri yang relevan dari salah satu jenis, ID yang cocok dari jenis lain akan selalu muncul kemudian (berdasarkan RunningQuantity dan pemesanan Kode). Setelah melihat solusi Peter, sepertinya saya terlalu memperumit masalah saya!
 

 Berikut adalah waktu berjalan dalam hitungan detik yang saya dapatkan untuk solusi ini:
 
100K:0.197200K:0.412300K:0.558400K:0.696
 

 
 
Solusi Paul White
 

 Solusi terakhir kami dibuat oleh Paul White. Berikut kode solusi lengkapnya:
 
DROP TABLE JIKA ADA #MyPairings; BUAT TABEL #MyPairings(Integer ID Permintaan NOT NULL, bilangan bulat SupplyID NOT NULL, desimal TradeQuantity(19, 6) NOT NULL);GO INSERT #MyPairings WITH (TABLOCK)( DemandID, SupplyID, TradeQuantity)PILIH Q3.DemandID, Q3.SupplyID, Q3.TradeQuantityFROM ( SELECT Q2.DemandID, Q2.SupplyID, TradeQuantity =-- Interval tumpang tindih CASE WHEN Q2.Code ='S' THEN CASE WHEN Q2.CumDemand>=Q2.IntEnd THEN Q2.IntLength WHEN Q2.CumDemand> Q2.CumDemand IntStart THEN Q2.CumDemand - Q2.IntStart ELSE 0.0 END WHEN Q2.Code ='D' THE N CASE WHEN Q2.CumSupply>=Q2.IntEnd THEN Q2.IntLength WHEN Q2.CumSupply> Q2.IntStart THEN IntStart ELSE 0.0 AKHIR AKHIR DARI ( PILIH Q1.Code, Q1.IntStart, Q1.IntEnd, Q1.IntLength, DemandID =MAX(IIF(Q1.Code ='D', Q1.ID, 0)) OVER ( ORDER BY Q1.IntStart, Q1.ID BARIS TIDAK TERBATAS SEBELUMNYA), SupplyID =MAX(IIF(Q1.Code ='S', Q1.ID, 0)) OVER ( ORDER BY Q1.IntStart, Q1.ID BARIS UNBOUNDED SEBELUMNYA), CumSupply =SUM(IIF(Q1.Code ='S', Q1.IntLength, 0)) OVER ( ORDER BY Q1.IntStart, Q1.ID ROWS UNBOUNDED PRECEDING), CumDemand =SUM(IIF(Q1.Code ='D', Q1.IntLength, 0)) OVER ( ORDER OLEH Q1.IntStart, Q1.ID ROWS UNBOUNDED PRECEDING) DARI ( -- Demand intervals SELECT A.ID, A.Code, IntStart =SUM(A.Quantity) OVER ( ORDER BY A.ID ROWS UNBOUNDED PRECEDING) - A. Kuantitas, IntEnd =SUM(A.Quantity) OVER ( ORDER BY A.ID ROWS UNBOUNDED PRECEDING), IntLength =A.Quantity FROM dbo.Auctions AS A WHERE A.Code ='D' UNION ALL -- Supply interval SELECT A.ID, A.Code, IntStart =SUM(A.Quantity) OVER ( ORDER BY A.ID ROWS UNBOUNDED PRECEDING) - A.Quantity, IntEnd =SUM(A.Quantity) OVER ( ORDER BY A.ID ROWS UNBOUNDED SEBELUMNYA), IntLength =A.Kuantitas DARI dbo.Auctions SEBAGAI MANA A.Code ='S' ) SEBAGAI Q1 ) SEBAGAI Q2) SEBAGAI Q3WHERE Q3.TradeQuantity> 0;
 

 Kode yang mendefinisikan tabel turunan Q1 menggunakan dua kueri terpisah untuk menghitung interval permintaan dan pasokan berdasarkan total berjalan dan menyatukan keduanya. Untuk setiap interval, kode menghitung awal (IntStart), akhir (IntEnd), dan panjangnya (IntLength). Berikut adalah isi Q1 yang dipesan oleh IntStart dan ID:
 
Kode ID IntStart IntEnd IntLength----- ---- ---------- ---------- ----------1 D 0,000000 27.000000 5.000.0001000 S 0.000000 8.000.000 8.000.0002 D 5.000.000 8.000.000 3.000.0003 D 8.000.000 16.000.000 8.000.0002000 S 8.00000 14.00000 6.0000003000 S 14.00000 16.000000 2.000000 D 16.000000 18.000000 2.0000004000 S 16.0000000 18.000.000 2.0000006 D 18.000000 26.000000 8.0000005000 S 14.000.000 2.000.000 D 30,000000 32,000000 2,000000
 

 Kode yang mendefinisikan tabel turunan Q2 kueri Q1 dan menghitung kolom hasil yang disebut DemandID, SupplyID, CumSupply, dan CumDemand. Semua fungsi jendela yang digunakan oleh kode ini didasarkan pada pemesanan IntStart dan ID dan frame ROWS UNBOUNDED PRECEDING (semua baris hingga saat ini).
 

 DemandID adalah ID permintaan maksimum hingga baris saat ini, atau 0 jika tidak ada.
 

 SupplyID adalah ID persediaan maksimum hingga baris saat ini, atau 0 jika tidak ada.
 

 CumSupply adalah jumlah pasokan kumulatif (panjang interval pasokan) hingga baris saat ini.
 

 CumDemand adalah jumlah permintaan kumulatif (panjang interval permintaan) hingga baris saat ini.
 

 Berikut adalah isi dari Q2:
 
Code IntStart IntEnd IntLength DemandID SupplyID CumSupply CumDemand---- ---------- ---------- ---------- ----- ---- --------- ---------- ----------D 0,000000 5.000000 5.000.000 1 0 0.000000 5.000.000S 0.000000 8.000.000 8.000.000 1 1000 8.000.000 5.000.000D 5.000.000 8.000.000 3.000.000 2 1000 8.000.000 8.000.000D 8.000.000 16.000000 8.000.000 3 1000 8.000.000 16.000000S 8.000.000 14.000.000 6.000.000 3 2000 14.00000 16.000000S 14.00000 16.000000 2.000000 3 3000 16.000000 16.000000D 16.000.000 18.000.000 2.000.000 5 3000 16.000000 18.000.000S 16.000.000 18.000.000 16.000.000 8.000.000 6 4000 18.000.000 26.000000S 18.000.000 22.000000 4.000.000 6 5000 22.000000 26.000000S 22.000000 25.000000 3.000.000 6 6000 25.000000 26.000000S 25.000000 27.000000 2.000000 6 7000 27.000000 26.000000D 26.000000 30.000000 4.000.000 7 7000 27.000000 30.000000D 30.000000 32.000000 2.000000 8 7000 27.000000 32.000000
 

 Q2 already has the final result pairings’ correct DemandID and SupplyID values. The code defining the derived table Q3 queries Q2 and computes the result pairings’ TradeQuantity values as the overlapping segments of the demand and supply intervals. Finally, the outer query against Q3 filters only the relevant pairings where TradeQuantity is positive. 
 

 The plan for this solution is shown in Figure 5.
 

 Figure 5:Query plan for Paul’s solution 
 

 The top two branches of the plan are responsible for computing the demand and supply intervals. Both rely on Index Seek operators to get the relevant rows based on index order, and then use parallel batch-mode Window Aggregate operators, preceded by Sort operators that theoretically could have been avoided. The plan concatenates the two inputs, sorts the rows by IntStart and ID to support the subsequent remaining Window Aggregate operator. Only this Sort operator is unavoidable in this plan. The rest of the plan handles the needed scalar computations and the final filter. That’s a very efficient plan!
 

 Here are the run times in seconds I got for this solution:
 
100K:0.187200K:0.331300K:0.369400K:0.425
 

 These numbers are pretty impressive! 
 
Performance Comparison
 

 Figure 6 has a performance comparison between all solutions covered in this article.
 

 Figure 6:Performance comparison 
 

 At this point, we can add the fastest solutions I covered in previous articles. Those are Joe’s and Kamil/Luca/Daniel’s solutions. The complete comparison is shown in Figure 7. 
 

 Figure 7:Performance comparison including earlier solutions 
 

 These are all impressively fast solutions, with the fastest being Paul’s and Peter’s.
 
Kesimpulan
 

 When I originally introduced Peter’s puzzle, I showed a straightforward cursor-based solution that took 11.81 seconds to complete against a 400K-row input. The challenge was to come up with an efficient set-based solution. It’s so inspiring to see all the solutions people sent. I always learn so much from such puzzles both from my own attempts and by analyzing others’ solutions. It’s impressive to see several sub-second solutions, with Paul’s being less than half a second!
 

 It's great to have multiple efficient techniques to handle such a classic need of matching supply with demand. Well done everyone!
 [ Jump to:Original challenge | Solutions:Part 1 | Part 2 | Part 3 ]