Phù hợp cung với thách thức nhu cầu

[Chuyển đến các giải pháp:Phần 1 | Phần 2 | Phần 3]

Bạn tôi Peter Larsson đã gửi cho tôi một thử thách T-SQL liên quan đến việc kết hợp cung với cầu. Đối với những thách thức, nó là một thách thức đáng gờm. Đó là một nhu cầu khá phổ biến trong cuộc sống thực; nó đơn giản để mô tả và nó khá dễ giải quyết với hiệu suất hợp lý bằng cách sử dụng giải pháp dựa trên con trỏ. Phần khó là giải quyết nó bằng cách sử dụng một giải pháp dựa trên tập hợp hiệu quả.

Khi Peter gửi cho tôi một câu đố, tôi thường trả lời bằng một giải pháp được đề xuất và anh ấy thường đưa ra một giải pháp hiệu quả hơn, tuyệt vời hơn. Đôi khi tôi nghi ngờ anh ấy gửi cho tôi những câu đố để thúc đẩy bản thân đưa ra một giải pháp tuyệt vời.

Vì nhiệm vụ đại diện cho một nhu cầu chung và rất thú vị, tôi đã hỏi Peter liệu anh ấy có phiền không nếu tôi chia sẻ nó và các giải pháp của anh ấy với độc giả của sqlperformance.com và anh ấy rất vui khi cho phép tôi.

Tháng này, tôi sẽ trình bày thách thức và giải pháp dựa trên con trỏ cổ điển. Trong các bài viết tiếp theo, tôi sẽ trình bày các giải pháp dựa trên cơ sở - bao gồm cả những giải pháp mà Peter và tôi đã làm việc.

Thử thách

Thử thách liên quan đến việc truy vấn một bảng có tên là Đấu giá mà bạn tạo bằng mã sau:

 DROP TABLE NẾU TỒN TẠI dbo.Auctions; TẠO BẢNG BẢNG. , 6) KHÔNG ĐẦY ĐỦ CONSTRAINT ck_Auctions_Quantity KIỂM TRA (Số lượng> 0));

Bảng này chứa các mục nhập cung và cầu. Các mục nhu cầu được đánh dấu bằng mã D và các mục cung bằng S. Nhiệm vụ của bạn là khớp số lượng cung và cầu dựa trên thứ tự ID, ghi kết quả vào một bảng tạm thời. Các mục nhập có thể đại diện cho các lệnh mua và bán tiền điện tử như BTC / USD, lệnh mua và bán chứng khoán như MSFT / USD hoặc bất kỳ mặt hàng nào khác hoặc hàng hóa mà bạn cần để khớp cung với cầu. Lưu ý rằng các mục Đấu giá thiếu thuộc tính giá. Như đã đề cập, bạn nên khớp số lượng cung và cầu dựa trên thứ tự ID. Thứ tự này có thể bắt nguồn từ giá cả (tăng dần cho các mục cung và giảm dần cho các mục cầu) hoặc bất kỳ tiêu chí liên quan nào khác. Trong thử thách này, ý tưởng là giữ cho mọi thứ đơn giản và giả sử rằng ID đã đại diện cho thứ tự phù hợp để khớp.

Ví dụ:sử dụng mã sau để điền vào bảng Đấu giá với một tập hợp nhỏ dữ liệu mẫu:

 ĐẶT SỐ TÀI KHOẢN BẬT; XÓA khỏi dbo.Auctions; SET IDENTITY_INSERT dbo.Auctions ON; CHÈN VÀO Dbo.Auctions (ID, Mã, Số lượng) GIÁ TRỊ (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;

Bạn phải khớp số lượng cung và cầu như vậy:

Số lượng 5,0 được so khớp cho Nhu cầu 1 và Cung 1000, làm cạn kiệt Nhu cầu 1 và để lại 3,0 so với Cung 1000
Số lượng 3.0 phù hợp với Cầu 2 và Cung 1000, làm cạn kiệt cả Cầu 2 và Cung 1000
Số lượng 6,0 được so khớp cho Nhu cầu 3 và Cung 2000, để lại 2,0 cho Nhu cầu 3 và cạn kiệt nguồn cung 2000
Số lượng 2,0 được so khớp cho Nhu cầu 3 và Nguồn cung 3000, làm cạn kiệt cả Nhu cầu 3 và Nguồn cung 3000
Số lượng 2,0 được so khớp cho Nhu cầu 5 và Nguồn cung 4000, làm cạn kiệt cả Nhu cầu 5 và Nguồn cung 4000
Số lượng 4,0 được khớp với Nhu cầu 6 và Nguồn cung 5000, để lại 4,0 của Nhu cầu 6 và cạn kiệt Nguồn cung 5000
Số lượng 3.0 được khớp với Nhu cầu 6 và Cung cấp 6000, còn lại 1.0 của Nhu cầu 6 và làm cạn kiệt Nguồn cung cấp 6000
Số lượng 1,0 được khớp với Cầu 6 và Cung 7000, làm cạn kiệt Cầu 6 và để lại 1,0 của Cung 7000
Một lượng 1,0 khớp với Cầu 7 và Cung 7000, để lại 3,0 cho Cầu 7 và làm cạn kiệt Cung 7000; Cầu 8 không khớp với bất kỳ mục Cung nào và do đó chỉ còn lại với số lượng đầy đủ là 2.0

Giải pháp của bạn phải ghi dữ liệu sau vào bảng tạm thời kết quả:

 DemandID SupplyID TradeQ Số lượng ----------- ---------------- 1 1000 5.0000002 1000 3.0000003 2000 6.0000003 3000 2,0000005 4000 2,0000006 5000 4,0000006 6000 3,0000006 7000 1,0000007 7000 1,000000

Bộ dữ liệu mẫu lớn

Để kiểm tra hiệu suất của các giải pháp, bạn sẽ cần một bộ dữ liệu mẫu lớn hơn. Để trợ giúp việc này, bạn có thể sử dụng hàm GetNums mà bạn tạo bằng cách chạy mã sau:

 TẠO CHỨC NĂNG dbo.GetNums (@low AS BIGINT =1, @high AS BIGINT) BẢNG TRỞ LẠI CÓ L0 AS (CHỌN 1 NHƯ c TỪ (VALUES (1), (1), (1), (1), (1), (1), (1), (1), (1), (1), (1), (1), (1), (1), (1), (1)) NHƯ D (c)), L1 AS (CHỌN 1 AS c TỪ L0 AS A CROSS JOIN L0 AS B), L2 AS (CHỌN 1 AS c TỪ L1 AS A CROSS JOIN L1 AS B), L3 AS (CHỌN 1 AS c TỪ L2 NHƯ CHÉO THAM GIA L2 NHƯ B), Nums NHƯ (CHỌN ROW_NUMBER () HẾT (ĐẶT HÀNG BẰNG (CHỌN NULL)) NHƯ rownum TỪ L3) CHỌN ĐẦU (@high - @low + 1) rownum AS rn, @high + 1 - rownum AS op, @low - 1 + rownum AS n TỪ Nums ĐẶT HÀNG BỞI rownum; ĐI

Hàm này trả về một chuỗi các số nguyên trong phạm vi được yêu cầu.

Với chức năng này, bạn có thể sử dụng mã sau do Peter cung cấp để điền dữ liệu mẫu vào bảng Đấu giá, tùy chỉnh các đầu vào nếu cần:

DECLARE - kiểm tra với 50K, 100K, 150K, 200K trong mỗi biến @Buyers và @Sellers - vì vậy tổng số hàng là gấp đôi (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; XÓA khỏi dbo.Auctions; CHÈN VÀO dbo.Auctions (Mã, Số lượng) CHỌN Mã, Số lượng TỪ (CHỌN 'D' AS Mã, (ABS (CHECKSUM (NEWID ()))% (1000000 * (@BuyerMaxQuantity - @BuyerMinQuantity))) / 1000000E + @ BuyerMinQuantity AS Number AS Số lượng TỪ dbo.GetNums (1, @Sellers)) AS X ORDER BY NEWID (); CHỌN mã, COUNT (*) AS mục

Như bạn thấy, bạn có thể tùy chỉnh số lượng người mua và người bán cũng như số lượng người mua và người bán tối thiểu và tối đa. Đoạn mã trên chỉ định 200.000 người mua và 200.000 người bán, dẫn đến tổng số 400.000 hàng trong bảng Đấu giá. Truy vấn cuối cùng cho bạn biết có bao nhiêu mục nhập cầu (D) và cung (S) đã được ghi vào bảng. Nó trả về đầu ra sau cho các đầu vào nói trên:

 Mã mục ---- ----------- D 200000S 200000

Tôi sẽ kiểm tra hiệu suất của các giải pháp khác nhau bằng cách sử dụng đoạn mã trên, đặt số lượng người mua và người bán mỗi người như sau:50.000, 100.000, 150.000 và 200.000. Điều này có nghĩa là tôi sẽ nhận được tổng số hàng sau đây trong bảng:100.000, 200.000, 300.000 và 400.000. Tất nhiên, bạn có thể tùy chỉnh các đầu vào theo ý muốn để kiểm tra hiệu suất của các giải pháp của mình.

Giải pháp dựa trên con trỏ

Peter đã cung cấp giải pháp dựa trên con trỏ. Nó khá cơ bản, đó là một trong những lợi thế quan trọng của nó. Nó sẽ được sử dụng làm điểm chuẩn.

Giải pháp sử dụng hai con trỏ:một cho các mục nhu cầu được sắp xếp theo ID và một cho các mục cung cấp được sắp xếp theo ID. Để tránh quét toàn bộ và sắp xếp trên mỗi con trỏ, hãy tạo chỉ mục sau:

 TẠO CHỈ SỐ DUY NHẤT KHÔNG CHỈNH SỬA idx_Code_ID_i_Quantity ON dbo.Auctions (Mã, ID) BAO GỒM (Số lượng);

Đây là mã của giải pháp hoàn chỉnh:

 ĐẶT SỐ TÀI KHOẢN BẬT; DROP TABLE NẾU TỒN TẠI #PairingsCursor; TẠO BẢNG #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, Số lượng TỪ dbo.Auctions WHERE Mã ='D' ĐẶT HÀNG THEO ID; DECLARE curSupply CURSOR LOCAL FORWARD_ONLY READ_ONLY FOR SELECT ID AS SupplyID, Số lượng TỪ dbo.Auctions WHERE Code ='S' ĐẶT HÀNG THEO ID; DECLARE @DemandID AS INT, @DemandQuantity AS DECIMAL (19, 6), @SupplyID AS INT, @SupplyQuantity AS DECIMAL (19, 6); MỞ curDemand; TÌM KIẾM TIẾP THEO TỪ curDemand VÀO @DemandID, @DemandQuantity; MỞ curSupply; TÌM HIỂU TIẾP THEO TỪ curSupply VÀO @SupplyID, @SupplyQuantity; WHILE @@ FETCH_STATUS =0BEGIN IF @DemandQuantity <=@SupplyQuantity BEGIN INSERT #PairingsCursor (DemandID, SupplyID, TradeQuantity) GIÁ TRỊ (@DemandID, @SupplyID, @DemandQuantity); SET @SupplyQuantity - =@DemandQuantity; TÌM KIẾM TIẾP THEO TỪ curDemand VÀO @DemandID, @DemandQuantity; CHẤM DỨT; ELSE BẮT ĐẦU NẾU @SupplyQuantity> 0 BẮT ĐẦU CHÈN #PairingsCursor (DemandID, SupplyID, TradeQuantity) GIÁ TRỊ (@DemandID, @SupplyID, @SupplyQuantity); SET @DemandQuantity - =@SupplyQuantity; CHẤM DỨT; TÌM KIẾM TIẾP THEO TỪ curSupply VÀO @SupplyID, @SupplyQuantity; HẾT; KẾT THÚC; CLOSE curDemand; DEALLOCATE curDemand; CLOSE curSupply; DEALLOCATE curSupply;

Như bạn có thể thấy, mã bắt đầu bằng cách tạo một bảng tạm thời. Sau đó, nó khai báo hai con trỏ và lấy một hàng từ mỗi con trỏ, ghi lượng cầu hiện tại vào biến @DemandQuantity và lượng cung hiện tại vào @SupplyQuantity. Sau đó, nó xử lý các mục nhập trong một vòng lặp miễn là lần tìm nạp cuối cùng thành công. Mã áp dụng logic sau trong phần thân của vòng lặp:

Nếu lượng cầu hiện tại nhỏ hơn hoặc bằng lượng cung hiện tại, mã thực hiện như sau:

Ghi một hàng vào bảng tạm thời với ghép nối hiện tại, với số lượng nhu cầu (@DemandQuantity) là số lượng đã khớp
Trừ lượng cầu hiện tại cho số lượng cung hiện tại (@SupplyQuantity)
Tìm nạp hàng tiếp theo từ con trỏ yêu cầu

Nếu không, mã sẽ thực hiện như sau:

Kiểm tra xem số lượng cung cấp hiện tại có lớn hơn 0 không và nếu có, nó sẽ thực hiện như sau:
- Ghi một hàng vào bảng tạm thời với ghép nối hiện tại, với số lượng cung cấp là số lượng đã khớp
- Trừ lượng cung hiện tại cho lượng cầu hiện tại
Tìm nạp hàng tiếp theo từ con trỏ cung cấp

Sau khi hoàn tất vòng lặp, không còn cặp nào để khớp nữa, vì vậy mã chỉ xóa tài nguyên con trỏ.

Từ quan điểm hiệu suất, bạn có được chi phí điển hình của việc tìm nạp và lặp lại con trỏ. Sau đó, một lần nữa, giải pháp này thực hiện một lần chuyển theo thứ tự qua dữ liệu nhu cầu và một lần chuyển theo thứ tự qua dữ liệu cung, mỗi lần sử dụng tìm kiếm và quét phạm vi trong chỉ mục bạn đã tạo trước đó. Các kế hoạch cho các truy vấn con trỏ được thể hiện trong Hình 1.

Hình 1:Kế hoạch cho truy vấn con trỏ

Vì kế hoạch thực hiện tìm kiếm và quét phạm vi theo thứ tự của từng bộ phận (nhu cầu và cung) mà không liên quan đến phân loại, nó có quy mô tuyến tính. Điều này đã được xác nhận bởi các con số hiệu suất mà tôi nhận được khi kiểm tra nó, như thể hiện trong Hình 2.

Hình 2:Hiệu suất của Giải pháp dựa trên con trỏ

Nếu bạn quan tâm đến thời gian chạy chính xác hơn, thì đây là:

100.000 hàng (50.000 nhu cầu và 50.000 nguồn cung cấp):2,93 giây
200.000 hàng:5,89 giây
300.000 hàng:8,75 giây
400.000 hàng:11,81 giây

Với giải pháp có tỷ lệ tuyến tính, bạn có thể dễ dàng dự đoán thời gian chạy với các tỷ lệ khác. Ví dụ:với một triệu hàng (giả sử 500.000 nhu cầu và 500.000 nguồn cung cấp), sẽ mất khoảng 29,5 giây để chạy.

Thử thách đang diễn ra

Giải pháp dựa trên con trỏ có tỷ lệ tuyến tính và như vậy, nó không tệ. Nhưng nó phải chịu phí tìm nạp và lặp lại con trỏ điển hình. Rõ ràng, bạn có thể giảm chi phí này bằng cách triển khai cùng một thuật toán sử dụng giải pháp dựa trên CLR. Câu hỏi đặt ra là bạn có thể đưa ra một giải pháp dựa trên bộ hoạt động hiệu quả cho nhiệm vụ này không?

Như đã đề cập, tôi sẽ khám phá các giải pháp dựa trên thiết lập — cả hoạt động kém và hoạt động tốt — bắt đầu từ tháng tới. Trong khi đó, nếu bạn muốn thử thách, hãy xem liệu bạn có thể đưa ra các giải pháp dựa trên thiết lập của riêng mình hay không.

Để xác minh tính đúng đắn của giải pháp của bạn, trước tiên hãy so sánh kết quả của nó với kết quả được hiển thị ở đây cho một tập hợp nhỏ dữ liệu mẫu. Bạn cũng có thể kiểm tra tính hợp lệ của kết quả giải pháp của mình bằng một tập hợp lớn dữ liệu mẫu bằng cách xác minh sự khác biệt đối xứng giữa kết quả của giải pháp con trỏ và kết quả của bạn là trống. Giả sử kết quả của con trỏ được lưu trữ trong bảng tạm gọi là #PairingsCursor và của bạn trong bảng tạm gọi là #MyPairings, bạn có thể sử dụng đoạn mã sau để đạt được điều này:

 (CHỌN * TỪ #PairingsCursor NGOẠI TRỪ CHỌN * TỪ #MyPairings) ĐOÀN KẾT TẤT CẢ (CHỌN * TỪ #MyPairings TRỪ CHỌN * TỪ #PairingsCursor);

Kết quả phải để trống.

Chúc bạn thành công!

[Chuyển đến các giải pháp:Phần 1 | Phần 2 | Phần 3]