Mencocokkan Pasokan Dengan Permintaan Tantangan

[ Langsung ke solusi:Bagian 1 | Bagian 2 | Bagian 3]

Teman saya Peter Larsson mengirimi saya tantangan T-SQL yang melibatkan pencocokan pasokan dengan permintaan. Sejauh tantangan pergi, itu salah satu yang tangguh. Ini adalah kebutuhan yang cukup umum dalam kehidupan nyata; sederhana untuk dijelaskan, dan cukup mudah untuk diselesaikan dengan kinerja yang wajar menggunakan solusi berbasis kursor. Bagian yang sulit adalah menyelesaikannya menggunakan solusi berbasis himpunan yang efisien.

Ketika Peter mengirimi saya teka-teki, saya biasanya merespons dengan solusi yang disarankan, dan dia biasanya memberikan solusi yang berkinerja lebih baik dan brilian. Kadang-kadang saya curiga dia mengirimi saya teka-teki untuk memotivasi dirinya menemukan solusi yang bagus.

Karena tugas tersebut mewakili kebutuhan bersama dan sangat menarik, saya bertanya kepada Peter apakah dia keberatan jika saya membagikannya dan solusinya dengan pembaca sqlperformance.com, dan dia dengan senang hati mengizinkan saya.

Bulan ini, saya akan menyajikan tantangan dan solusi klasik berbasis kursor. Dalam artikel berikutnya, saya akan menyajikan solusi berbasis himpunan—termasuk solusi yang saya dan Peter kerjakan.

Tantangan

Tantangannya melibatkan kueri tabel bernama Auctions, yang Anda buat menggunakan kode berikut:

DROP TABLE IF EXISTS dbo.Auctions;
 
CREATE TABLE dbo.Auctions
(
  ID INT NOT NULL IDENTITY(1, 1)
    CONSTRAINT pk_Auctions PRIMARY KEY CLUSTERED,
  Code CHAR(1) NOT NULL
    CONSTRAINT ck_Auctions_Code CHECK (Code = 'D' OR Code = 'S'),
  Quantity DECIMAL(19, 6) NOT NULL
    CONSTRAINT ck_Auctions_Quantity CHECK (Quantity > 0)
);

Tabel ini menyimpan entri permintaan dan penawaran. Entri permintaan ditandai dengan kode D dan entri penawaran dengan S. Tugas Anda adalah mencocokkan jumlah penawaran dan permintaan berdasarkan pemesanan ID, menuliskan hasilnya ke dalam tabel sementara. Entri dapat mewakili pesanan beli dan jual mata uang kripto seperti BTC/USD, pesanan beli dan jual saham seperti MSFT/USD, atau barang atau barang lainnya di mana Anda perlu mencocokkan penawaran dengan permintaan. Perhatikan bahwa entri Lelang tidak memiliki atribut harga. Seperti yang disebutkan, Anda harus mencocokkan jumlah penawaran dan permintaan berdasarkan pemesanan ID. Pemesanan ini dapat diturunkan dari harga (naik untuk entri pasokan dan turun untuk entri permintaan) atau kriteria lain yang relevan. Dalam tantangan ini, idenya adalah untuk menjaga hal-hal sederhana dan menganggap ID sudah mewakili urutan yang relevan untuk pencocokan.

Sebagai contoh, gunakan kode berikut untuk mengisi tabel Lelang dengan sekumpulan kecil contoh data:

SET NOCOUNT ON;
 
DELETE FROM dbo.Auctions;
 
SET IDENTITY_INSERT dbo.Auctions ON;
 
INSERT INTO dbo.Auctions(ID, Code, Quantity) VALUES
  (1,    'D', 5.0),
  (2,    'D', 3.0),
  (3,    'D', 8.0),
  (5,    'D', 2.0),
  (6,    'D', 8.0),
  (7,    'D', 4.0),
  (8,    'D', 2.0),
  (1000, 'S', 8.0),
  (2000, 'S', 6.0),
  (3000, 'S', 2.0),
  (4000, 'S', 2.0),
  (5000, 'S', 4.0),
  (6000, 'S', 3.0),
  (7000, 'S', 2.0);
 
SET IDENTITY_INSERT dbo.Auctions OFF;

Anda harus mencocokkan jumlah penawaran dan permintaan seperti ini:

Jumlah 5.0 dicocokkan untuk Permintaan 1 dan Penawaran 1000, menghabiskan Permintaan 1 dan meninggalkan 3.0 dari Penawaran 1000
Kuantitas 3,0 dicocokkan untuk Permintaan 2 dan Penawaran 1000, menghabiskan Permintaan 2 dan Penawaran 1000
Kuantitas 6,0 dicocokkan untuk Permintaan 3 dan Penawaran 2000, menyisakan 2.0 dari Permintaan 3 dan menipiskan persediaan 2000
Kuantitas 2,0 dicocokkan untuk Permintaan 3 dan Penawaran 3000, menghabiskan Permintaan 3 dan Penawaran 3000
Kuantitas 2,0 dicocokkan untuk Permintaan 5 dan Penawaran 4000, menghabiskan Permintaan 5 dan Penawaran 4000
Kuantitas 4,0 dicocokkan untuk Permintaan 6 dan Pasokan 5000, meninggalkan 4.0 dari Permintaan 6 dan menghabiskan Pasokan 5000
Kuantitas 3,0 dicocokkan untuk Permintaan 6 dan Penawaran 6000, meninggalkan 1,0 dari Permintaan 6 dan menghabiskan Penawaran 6000
Kuantitas 1,0 dicocokkan untuk Permintaan 6 dan Penawaran 7000, menghabiskan Permintaan 6 dan menyisakan 1,0 dari Pasokan 7000
Kuantitas 1,0 dicocokkan untuk Permintaan 7 dan Pasokan 7000, meninggalkan 3.0 dari Permintaan 7 dan menghabiskan Pasokan 7000; Permintaan 8 tidak cocok dengan entri Pasokan apa pun dan karena itu dibiarkan dengan jumlah penuh 2.0

Solusi Anda seharusnya menulis data berikut ke dalam tabel sementara yang dihasilkan:

DemandID    SupplyID    TradeQuantity
----------- ----------- --------------
1           1000        5.000000
2           1000        3.000000
3           2000        6.000000
3           3000        2.000000
5           4000        2.000000
6           5000        4.000000
6           6000        3.000000
6           7000        1.000000
7           7000        1.000000

Set Besar Data Sampel

Untuk menguji kinerja solusi, Anda memerlukan kumpulan data sampel yang lebih besar. Untuk membantu ini, Anda dapat menggunakan fungsi GetNums, yang Anda buat dengan menjalankan kode berikut:

CREATE FUNCTION dbo.GetNums(@low AS BIGINT = 1, @high AS BIGINT)
  RETURNS TABLE
AS
RETURN
  WITH
    L0 AS ( SELECT 1 AS c 
            FROM (VALUES(1),(1),(1),(1),(1),(1),(1),(1),
                        (1),(1),(1),(1),(1),(1),(1),(1)) AS D(c) ),
    L1 AS ( SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B ),
    L2 AS ( SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B ),
    L3 AS ( SELECT 1 AS c FROM L2 AS A CROSS JOIN L2 AS B ),
    Nums AS ( SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS rownum
              FROM L3 )
  SELECT TOP(@high - @low + 1)
     rownum AS rn,
     @high + 1 - rownum AS op,
     @low - 1 + rownum AS n
  FROM Nums
  ORDER BY rownum;
GO

Fungsi ini mengembalikan urutan bilangan bulat dalam rentang yang diminta.

Dengan fungsi ini, Anda dapat menggunakan kode berikut yang disediakan oleh Peter untuk mengisi tabel Lelang dengan data sampel, menyesuaikan input sesuai kebutuhan:

DECLARE
  -- test with 50K, 100K, 150K, 200K in each of variables @Buyers and @Sellers
  -- so total rowcount is double (100K, 200K, 300K, 400K)
  @Buyers            AS INT            = 200000,
  @Sellers           AS INT            = 200000,
  @BuyerMinQuantity  AS DECIMAL(19, 6) = 0.000001,
  @BuyerMaxQuantity  AS DECIMAL(19, 6) = 99.999999,
  @SellerMinQuantity AS DECIMAL(19, 6) = 0.000001,
  @SellerMaxQuantity AS DECIMAL(19, 6) = 99.999999;
 
DELETE FROM dbo.Auctions;
 
INSERT INTO dbo.Auctions(Code, Quantity)
  SELECT Code, Quantity
  FROM ( SELECT 'D' AS Code,
           (ABS(CHECKSUM(NEWID())) % (1000000 * (@BuyerMaxQuantity - @BuyerMinQuantity)))
             / 1000000E + @BuyerMinQuantity AS Quantity
         FROM dbo.GetNums(1, @Buyers)
         UNION ALL
         SELECT 'S' AS Code,
           (ABS(CHECKSUM(NEWID())) % (1000000 * (@SellerMaxQuantity - @SellerMinQuantity)))
             / 1000000E + @SellerMinQuantity AS Quantity
         FROM dbo.GetNums(1, @Sellers) ) AS X
  ORDER BY NEWID();
 
SELECT Code, COUNT(*) AS Items
FROM dbo.Auctions
GROUP BY Code;

Seperti yang Anda lihat, Anda dapat menyesuaikan jumlah pembeli dan penjual serta jumlah pembeli dan penjual minimum dan maksimum. Kode di atas menentukan 200.000 pembeli dan 200.000 penjual, menghasilkan total 400.000 baris dalam tabel Lelang. Kueri terakhir memberi tahu Anda berapa banyak entri permintaan (D) dan penawaran (S) yang ditulis ke tabel. Ini mengembalikan output berikut untuk input yang disebutkan di atas:

Code Items
---- -----------
D    200000
S    200000

Saya akan menguji kinerja berbagai solusi menggunakan kode di atas, menetapkan jumlah pembeli dan penjual masing-masing sebagai berikut:50.000, 100.000, 150.000, dan 200.000. Ini berarti saya akan mendapatkan jumlah baris berikut dalam tabel:100.000, 200.000, 300.000, dan 400.000. Tentu saja, Anda dapat menyesuaikan input sesuai keinginan untuk menguji kinerja solusi Anda.

Solusi Berbasis Kursor

Peter menyediakan solusi berbasis kursor. Ini cukup mendasar, yang merupakan salah satu keuntungan penting. Ini akan digunakan sebagai patokan.

Solusinya menggunakan dua kursor:satu untuk entri permintaan yang dipesan oleh ID dan yang lainnya untuk entri pasokan yang dipesan oleh ID. Untuk menghindari pemindaian penuh dan pengurutan per kursor, buat indeks berikut:

CREATE UNIQUE NONCLUSTERED INDEX idx_Code_ID_i_Quantity
  ON dbo.Auctions(Code, ID)
  INCLUDE(Quantity);

Berikut kode solusi lengkapnya:

SET NOCOUNT ON;
 
DROP TABLE IF EXISTS #PairingsCursor;
 
CREATE TABLE #PairingsCursor
(
  DemandID INT NOT NULL,
  SupplyID INT NOT NULL,
  TradeQuantity DECIMAL(19, 6) NOT NULL
);
 
DECLARE curDemand CURSOR LOCAL FORWARD_ONLY READ_ONLY FOR
  SELECT ID AS DemandID, Quantity FROM dbo.Auctions WHERE Code = 'D' ORDER BY ID;
 
DECLARE curSupply CURSOR LOCAL FORWARD_ONLY READ_ONLY FOR
  SELECT ID AS SupplyID, Quantity FROM dbo.Auctions WHERE Code = 'S' ORDER BY ID;
 
DECLARE @DemandID AS INT, @DemandQuantity AS DECIMAL(19, 6),
        @SupplyID AS INT, @SupplyQuantity AS DECIMAL(19, 6);
 
OPEN curDemand;
FETCH NEXT FROM curDemand INTO @DemandID, @DemandQuantity;
 
OPEN curSupply;
FETCH NEXT FROM curSupply INTO @SupplyID, @SupplyQuantity;
 
WHILE @@FETCH_STATUS = 0
BEGIN
 
  IF @DemandQuantity <= @SupplyQuantity
  BEGIN
    INSERT #PairingsCursor(DemandID, SupplyID, TradeQuantity)
      VALUES(@DemandID, @SupplyID, @DemandQuantity);
 
    SET @SupplyQuantity -= @DemandQuantity;
 
    FETCH NEXT FROM curDemand INTO @DemandID, @DemandQuantity;
  END;
  ELSE
  BEGIN
    IF @SupplyQuantity > 0
    BEGIN
      INSERT #PairingsCursor(DemandID, SupplyID, TradeQuantity)
        VALUES(@DemandID, @SupplyID, @SupplyQuantity);
 
      SET @DemandQuantity -= @SupplyQuantity;
    END;
 
    FETCH NEXT FROM curSupply INTO @SupplyID, @SupplyQuantity;
  END;
END;
 
CLOSE curDemand;
DEALLOCATE curDemand;
 
CLOSE curSupply;
DEALLOCATE curSupply;

Seperti yang Anda lihat, kode dimulai dengan membuat tabel sementara. Ini kemudian mendeklarasikan dua kursor dan mengambil baris dari masing-masing, menulis kuantitas permintaan saat ini ke variabel @DemandQuantity dan kuantitas pasokan saat ini ke @SupplyQuantity. Kemudian proses entri dalam satu lingkaran selama pengambilan terakhir berhasil. Kode menerapkan logika berikut di badan loop:

Jika jumlah permintaan saat ini kurang dari atau sama dengan jumlah penawaran saat ini, kode akan melakukan hal berikut:

Menulis baris ke tabel temp dengan pasangan saat ini, dengan kuantitas permintaan (@DemandQuantity) sebagai kuantitas yang cocok
Kurangi kuantitas permintaan saat ini dari kuantitas pasokan saat ini (@SupplyQuantity)
Mengambil baris berikutnya dari kursor permintaan

Jika tidak, kode akan melakukan hal berikut:

Memeriksa apakah kuantitas suplai saat ini lebih besar dari nol, dan jika ya, akan melakukan hal berikut:
- Menulis baris ke tabel temp dengan pasangan saat ini, dengan kuantitas suplai sebagai kuantitas yang cocok
- Kurangi jumlah penawaran saat ini dari jumlah permintaan saat ini
Mengambil baris berikutnya dari kursor suplai

Setelah loop selesai, tidak ada lagi pasangan yang cocok, jadi kode hanya membersihkan sumber kursor.

Dari sudut pandang kinerja, Anda mendapatkan overhead yang khas dari pengambilan dan pengulangan kursor. Kemudian lagi, solusi ini melakukan satu lintasan terurut atas data permintaan dan satu lintasan terurut atas data pasokan, masing-masing menggunakan pemindaian pencarian dan jangkauan dalam indeks yang Anda buat sebelumnya. Rencana untuk kueri kursor ditunjukkan pada Gambar 1.

Gambar 1:Rencana Kueri Kursor

Karena rencana tersebut melakukan pemindaian jangkauan pencarian dan pemesanan dari masing-masing bagian (permintaan dan penawaran) tanpa melibatkan penyortiran, ia memiliki penskalaan linier. Ini dikonfirmasi oleh angka kinerja yang saya dapatkan saat mengujinya, seperti yang ditunjukkan pada Gambar 2.

Gambar 2:Kinerja Solusi Berbasis Kursor

Jika Anda tertarik dengan waktu lari yang lebih tepat, ini dia:

100.000 baris (50.000 permintaan dan 50.000 persediaan):2,93 detik
200.000 baris:5,89 detik
300.000 baris:8,75 detik
400.000 baris:11,81 detik

Mengingat solusinya memiliki penskalaan linier, Anda dapat dengan mudah memprediksi waktu berjalan dengan skala lain. Misalnya, dengan satu juta baris (katakanlah, 500.000 permintaan dan 500.000 persediaan), dibutuhkan sekitar 29,5 detik untuk dijalankan.

Tantangannya Ada

Solusi berbasis kursor memiliki penskalaan linier dan, dengan demikian, tidak buruk. Tapi itu memang menimbulkan pengambilan kursor biasa dan overhead perulangan. Jelas, Anda dapat mengurangi overhead ini dengan menerapkan algoritme yang sama menggunakan solusi berbasis CLR. Pertanyaannya adalah, dapatkah Anda menemukan solusi berbasis himpunan yang berkinerja baik untuk tugas ini?

Seperti yang disebutkan, saya akan mengeksplorasi solusi berbasis set—berperforma buruk dan berkinerja baik—mulai bulan depan. Sementara itu, jika Anda siap menghadapi tantangan, lihat apakah Anda dapat menemukan solusi berbasis himpunan sendiri.

Untuk memverifikasi kebenaran solusi Anda, pertama-tama bandingkan hasilnya dengan yang ditunjukkan di sini untuk kumpulan kecil data sampel. Anda juga dapat memeriksa validitas hasil solusi Anda dengan sekumpulan besar data sampel dengan memverifikasi perbedaan simetris antara hasil solusi kursor dan Anda kosong. Dengan asumsi hasil kursor disimpan dalam tabel temp bernama #PairingsCursor dan milik Anda di tabel temp bernama #MyPairings, Anda dapat menggunakan kode berikut untuk mencapai ini:

(SELECT * FROM #PairingsCursor EXCEPT SELECT * FROM #MyPairings)
UNION ALL
(SELECT * FROM #MyPairings EXCEPT SELECT * FROM #PairingsCursor);

Hasilnya harus kosong.

Semoga berhasil!

[ Langsung ke solusi:Bagian 1 | Bagian 2 | Bagian 3]