Khớp Cung với Cầu - Giải pháp, Phần 3

[Bước tới:Thử thách ban đầu | Giải pháp:Phần 1 | Phần 2 | Phần 3]

Trong bài viết này, tôi tiếp tục khám phá các giải pháp cho thách thức cung - cầu so khớp. Cảm ơn Luca, Kamil Kosno, Daniel Brown, Brian Walker, Joe Obbish, Rainer Hoffmann, Paul White, Charlie, Ian và Peter Larsson, vì đã gửi các giải pháp của bạn.

Tháng trước, tôi đã đề cập đến các giải pháp dựa trên phương pháp tiếp cận các nút giao cách quãng đã được sửa đổi so với phương pháp cổ điển. Giải pháp nhanh nhất trong số đó kết hợp ý tưởng từ Kamil, Luca và Daniel. Nó hợp nhất hai truy vấn với các vị từ sargable rời rạc. Giải pháp đã mất 1,34 giây để hoàn thành với đầu vào 400K hàng. Điều đó không quá tồi khi xem xét giải pháp dựa trên phương pháp tiếp cận các nút giao cách quãng cổ điển, mất 931 giây để hoàn thành với cùng một đầu vào. Cũng nhớ lại Joe đã đưa ra một giải pháp tuyệt vời dựa trên cách tiếp cận giao khoảng cổ điển nhưng tối ưu hóa logic đối sánh bằng cách bucketizing khoảng dựa trên độ dài khoảng lớn nhất. Với cùng một đầu vào 400K hàng, giải pháp của Joe mất 0,9 giây để hoàn thành. Phần khó khăn về giải pháp này là hiệu suất của nó giảm khi độ dài khoảng thời gian lớn nhất tăng lên.

Tháng này, tôi khám phá các giải pháp hấp dẫn nhanh hơn so với giải pháp Giao lộ sửa đổi Kamil / Luca / Daniel và trung hòa với độ dài khoảng cách. Các giải pháp trong bài viết này được tạo ra bởi Brian Walker, Ian, Peter Larsson, Paul White và tôi.

Tôi đã thử nghiệm tất cả các giải pháp trong bài viết này dựa trên bảng đầu vào Đấu giá với hàng 100 nghìn, 200 nghìn, 300 nghìn và 400 nghìn và với các chỉ mục sau:

 - Chỉ mục hỗ trợ giải pháp TẠO CHỈ SỐ KHÔNG CHỈ ĐỊNH DUY NHẤT idx_Code_ID_i_Quantity ON dbo.Auctions (Mã, ID) BAO GỒM (Số lượng); - Bật tính năng tổng hợp cửa sổ ở chế độ hàng loạt TẠO CHỈ SỐ KHÔNG ĐƯỢC ĐIỀU CHỈNH COLUMNSTORE idx_cs ON dbo.Auctions (ID) WHERE ID =-1 AND ID =-2;

Khi mô tả logic đằng sau các giải pháp, tôi sẽ giả sử bảng Đấu giá được điền với một tập hợp nhỏ dữ liệu mẫu sau:

 Mã ID Số lượng ----------- --------- 1 D 5.0000002 D 3.0000003 D 8.0000005 D 2.0000006 D 8.0000007 D 4.0000008 D 2.0000001000 S 8.0000002000 S 6.0000003000 S 2.0000004000 S 2.0000005000 S 4.0000006000 S 3.0000007000 S 2.000000

Sau đây là kết quả mong muốn cho dữ liệu mẫu này:

 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

Brian Walker’s Solution

Các phép nối bên ngoài được sử dụng khá phổ biến trong các giải pháp truy vấn SQL, nhưng cho đến nay khi bạn sử dụng chúng, bạn sử dụng các phép nối đơn phía. Khi giảng dạy về liên kết ngoài, tôi thường nhận được câu hỏi yêu cầu ví dụ cho các trường hợp sử dụng thực tế của liên kết ngoài đầy đủ và không có nhiều như vậy. Giải pháp của Brian là một ví dụ tuyệt vời về trường hợp sử dụng thực tế của các phép nối bên ngoài đầy đủ.

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

 DROP TABLE NẾU TỒN TẠI #MyPairings; TẠO BẢNG #MyPairings (DemandID INT NOT NULL, SupplyID INT NOT NULL, TradeQuantity DECIMAL (19,06) NOT NULL); VỚI D AS (CHỌN A.ID, SUM (A.Số lượng) HƠN (PHẦN THEO LỆNH A.Code BỞI A.ID ROWS UNBOUNDED PRECEDING) AS Chạy TỪ dbo.Auctions AS A WHERE A.Code ='D'), S AS (CHỌN A.ID, SUM (Số lượng) HẾT (PHẦN THEO LỆNH A.Code BỞI A.ID ROWS UNBOUNDED PRECEDING) AS Chạy TỪ dbo.Auctions AS A WHERE A.Code ='S'), W AS ( CHỌN 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 (CHỌN TRƯỜNG HỢP KHI W.DemandID LÀ KHÔNG ĐẦY ĐỦ THÌ W.DemandID ELSE MIN (W.DemandID) HẾT (ĐẶT HÀNG CỦA W.Running ROWS GIỮA ROW HIỆN TẠI VÀ UNBOUNDED SAU) KẾT THÚC LÀ DemandID, TRƯỜNG HỢP KHI W.SupplyID KHÔNG ĐẦY ĐỦ THÌ W.SupplyID ELSE MIN (W.SupplyID ) HẾT (ĐẶT HÀNG BẰNG W.Running ROWS GIỮA ROW HIỆN TẠI VÀ UNBOUNDED THEO DÕI) KẾT THÚC NHƯ SupplyID, W.Running FROM W) CHÈN #MyPair ings (DemandID, SupplyID, TradeQuantity) CHỌN Z.DemandID, Z.SupplyID, Z.Running - ISNULL (LAG (Z.Running) OVER (ORDER BY Z.Running), 0.0) NHƯ TradeQuantity TỪ Z TẠI ĐÂU Z.DemandID KHÔNG CÓ KHÔNG ĐỦ VÀ Z.SupplyID KHÔNG ĐỦ;

Tôi đã sửa lại cách sử dụng ban đầu của Brian đối với các bảng dẫn xuất với CTE để rõ ràng hơn.

CTE D tính tổng lượng cầu đang chạy trong cột kết quả được gọi là D.Running và CTE S tính tổng lượng cung đang chạy trong cột kết quả được gọi là S.Running. Sau đó, CTE W thực hiện một phép nối bên ngoài đầy đủ giữa D và S, khớp D.Running với S.Running, và trả về kết quả không phải NULL đầu tiên giữa D.Running và S.Running là W.Running. Đây là kết quả bạn nhận được nếu bạn truy vấn tất cả các hàng từ W được sắp xếp theo thứ tự Running:

 DemandID SupplyID đang chạy ------------- ---------------- 1 NULL 5.0000002 1000 8.000000NULL 2000 14.0000003 3000 16.0000005 4000 18.000000 NULL 5000 22.000000NULL 6000 25.0000006 NULL 26.000000NULL 7000 27.0000007 NULL 30.0000008 NULL 32.000000

Ý tưởng sử dụng một phép nối bên ngoài đầy đủ dựa trên một vị từ để so sánh tổng số cầu và cung đang chạy là một bước đột phá của thiên tài! Hầu hết các hàng trong kết quả này - 9 đầu tiên trong trường hợp của chúng tôi - đại diện cho các cặp kết quả mà thiếu một chút tính toán bổ sung. Các hàng có NULL ID theo sau thuộc một trong các loại đại diện cho các mục nhập không thể khớp với nhau. Trong trường hợp của chúng tôi, hai hàng cuối cùng đại diện cho các mục nhập cầu không thể khớp với các mục nhập cung. Vì vậy, những gì còn lại ở đây là tính toán DemandID, SupplyID và TradeQuantity của các cặp kết quả và lọc ra các mục không thể khớp.

Logic tính toán kết quả DemandID và SupplyID được thực hiện trong CTE Z như sau (giả sử sắp xếp theo thứ tự trong W by Running):

DemandID:nếu DemandID không phải là NULL thì DemandID, nếu không thì DemandID tối thiểu bắt đầu bằng hàng hiện tại
SupplyID:nếu SupplyID không phải là NULL thì SupplyID, nếu không thì SupplyID tối thiểu bắt đầu bằng hàng hiện tại

Đây là kết quả bạn nhận được nếu bạn truy vấn Z và sắp xếp các hàng bằng cách Chạy:

 DemandID SupplyID đang chạy ------------- ---------------- 1 1000 5.0000002 1000 8.0000003 2000 14.0000003 3000 16.0000005 4000 18.0000006 5000 22.0000006 6000 25.0000006 7000 26.0000007 7000 27.0000007 ĐẦY ĐỦ 30.0000008 ĐẦY ĐỦ 32.000000

Truy vấn bên ngoài lọc ra các hàng từ Z đại diện cho các mục nhập của một loại mà không thể khớp với các mục nhập khác bằng cách đảm bảo cả DemandID và SupplyID đều không NULL. Số lượng giao dịch của các cặp kết quả được tính bằng giá trị Đang chạy hiện tại trừ đi giá trị Đang chạy trước đó bằng cách sử dụng hàm LAG.

Đây là những gì được ghi vào bảng #MyPairings, là kết quả mong muốn:

 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

Kế hoạch cho giải pháp này được thể hiện trong Hình 1.

Hình 1:Kế hoạch truy vấn cho giải pháp của Brian

Hai nhánh trên cùng của kế hoạch tính toán tổng số cung và cầu bằng cách sử dụng toán tử Tổng hợp Cửa sổ ở chế độ hàng loạt, mỗi nhánh sau khi truy xuất các mục nhập tương ứng từ chỉ mục hỗ trợ. Giống như tôi đã giải thích trong các bài viết trước của loạt bài này, vì chỉ mục đã có các hàng được sắp xếp như các toán tử Tổng hợp Cửa sổ cần chúng, bạn sẽ nghĩ rằng các toán tử Sắp xếp rõ ràng không cần thiết. Nhưng SQL Server hiện không hỗ trợ kết hợp hiệu quả hoạt động chỉ mục bảo toàn thứ tự song song trước toán tử Tổng hợp cửa sổ chế độ hàng loạt song song, do đó, toán tử Sắp xếp song song rõ ràng đứng trước mỗi toán tử Tổng hợp cửa sổ song song.

Kế hoạch sử dụng một phép tham gia băm ở chế độ hàng loạt để xử lý kết nối bên ngoài đầy đủ. Kế hoạch cũng sử dụng hai toán tử Tổng hợp Cửa sổ chế độ hàng loạt bổ sung trước các toán tử Sắp xếp rõ ràng để tính toán các hàm cửa sổ MIN và LAG.

Đó là một kế hoạch khá hiệu quả!

Đây là thời gian chạy mà tôi nhận được cho giải pháp này so với kích thước đầu vào khác nhau, từ 100K đến 400K hàng, tính bằng giây:

 100 nghìn:0,368200 nghìn:0,845300 nghìn:1,255400 nghìn:1,315

Itzik’s Solution

Giải pháp tiếp theo cho thách thức là một trong những nỗ lực của tôi để giải quyết nó. Đây là mã giải pháp hoàn chỉnh:

 DROP TABLE NẾU TỒN TẠI #MyPairings; VỚI C1 AS (CHỌN *, SUM (Số lượng) HƠN (PHẦN THEO LỆNH Mã THEO ID ROWS CHƯA ĐƯỢC CẬP NHẬT CHÍNH XÁC) AS SumQty TỪ dbo.Auctions), C2 AS (CHỌN *, SUM (Số lượng * Mã trường hợp KHI 'D' THEN -1 KHI 'S' SAU 1 KẾT THÚC) HẾT (ĐẶT HÀNG THEO SumQty, Mã ROWS CHƯA ĐƯỢC BAO TRƯỚC CHÍNH XÁC) AS StockLevel, LAG (SumQty, 1, 0.0) OVER (ORDER BY SumQty, Code) AS PrevSumQty, MAX (CASE WHEN Code ='D' SAU ĐÓ ID KẾT THÚC) HẾT (ĐẶT HÀNG THEO SumQty, Mã ROWS UNBOUNDED PRECEDING) AS PrevDemandID, MAX (CASE WHEN Code ='S' THEN ID END) HẾT (ORDER BY SumQty, Code ROWS UNBOUNDED PRECEDING) AS PrevSupplyID, MIN (CASE WHEN Code ='D' THÌ ID END) HẾT (ĐẶT HÀNG THEO Tổng, CÁC TUYẾN Mã GIỮA ĐƯỜNG HIỆN TẠI VÀ ĐƯỜNG CHƯA ĐƯỢC TỔNG HỢP SAU) NHƯ NextDemandID, MIN (TRƯỜNG HỢP KHI Mã ='S' THEN ID END) HẾT (ĐẶT HÀNG THEO Tổng Số, CÁC TUYẾN Mã GIỮA HIỆN TẠI VÀ KHÔNG ĐƯỢC TỔ CHỨC THEO DÕI) AS NextSupplyID TỪ C1), C3 AS (CHỌN *, Mã trường hợp KHI 'D 'THEN ID WHEN' S 'THEN CASE WHEN StockLevel> 0 THEN NextDemandID ELSE PrevDemandID END END END AS DemandID, CASE Code KHI' S 'THEN ID WHEN' D 'THEN CASE WHEN StockLevel <=0 THEN NextSupplyID AS ELSE PrevSupplyID END END END SumQty - PrevSumQty AS TradeQuantity TỪ C2) CHỌN DemandID, SupplyID, TradeQuantityINTO #MyPairingsFROM C3WHERE TradeQuantity> 0.0 VÀ DemandID KHÔNG ĐẦY ĐỦ VÀ SupplyID KHÔNG ĐẦY ĐỦ;

CTE C1 truy vấn bảng Đấu giá và sử dụng hàm cửa sổ để tính toán tổng số lượng cung và cầu đang chạy, gọi cột kết quả là SumQty.

CTE C2 truy vấn C1 và tính toán một số thuộc tính bằng cách sử dụng các hàm cửa sổ dựa trên thứ tự SumQty và Code:

StockLevel:Mức tồn kho hiện tại sau khi xử lý mỗi mục nhập. Điều này được tính bằng cách gán một dấu âm cho số lượng cầu và một dấu dương cho số lượng cung cấp và tổng các số lượng đó lên đến và bao gồm cả mục nhập hiện tại.
PrevSumQty:Giá trị SumQty của hàng trước.
PrevDemandID:ID nhu cầu không NULL cuối cùng.
PrevSupplyID:ID nguồn cung cấp không phải NULL cuối cùng.
NextDemandID:ID nhu cầu tiếp theo không phải NULL.
NextSupplyID:ID nguồn cung cấp không phải NULL tiếp theo.

Đây là nội dung của C2 theo thứ tự của SumQty và Code:

 Mã ID Số lượng SumQty StockLevel PrevSumQty PrevDemandID PrevSupplyID NextDemandID NextSupplyID ----- ----------------- ---------------- - ----------- ------------ ------------ ------------ - ----------- 1 D 5.000000 5.000000 -5.000000 0.000000 1 NULL 1 10002 D 3.000000 8.000000 -8.000000 5.000000 2 NULL 2 10001000 S 8.000000 8.000000 0.000000 8.000000 2 1000 3 10002000 S 6.000000 14.000000 6.000000 8.000000 2 2000 3 20003 D 8.000000 16.000000 -2.000000 14.000000 3 2000 3 30003000 S 2.000000 16.000000 0.000000 16.000000 3 3000 5 30005 D 2.000000 18.000000 -2.000000 16.000000 5 3000 5 40004000 S 2.000000 18.000000 0.000000 18.000000 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.000000 26.000000 -1.000000 25.000000 6 6000 6 70007000 S 2.000000 27.000000 1.000000 26.000000 6 7000 7 7000 D 32.000000 -5.000000 30.000000 8 7000 8 NULL

CTE C3 truy vấn C2 và tính toán DemandID, SupplyID và TradeQuantity của các cặp kết quả, trước khi loại bỏ một số hàng thừa.

Kết quả cột C3.DemandID được tính như sau:

Nếu mục nhập hiện tại là mục nhập nhu cầu, hãy trả về DemandID.
Nếu mục nhập hiện tại là mục nhập cung ứng và lượng hàng hiện tại là dương, hãy trả về NextDemandID.
Nếu mục nhập hiện tại là mục nhập cung ứng và mức tồn kho hiện tại là không nhạy cảm, hãy trả về PrevDemandID.

Kết quả cột C3.SupplyID được tính như sau:

Nếu mục nhập hiện tại là mục nhập cung cấp, hãy trả lại SupplyID.
Nếu mục nhập hiện tại là mục nhập nhu cầu và mức tồn kho hiện tại là không nhạy cảm, hãy trả về NextSupplyID.
Nếu mục nhập hiện tại là mục nhập nhu cầu và lượng hàng hiện tại là dương, hãy trả lại PrevSupplyID.

Kết quả TradeQuantity được tính bằng SumQty của hàng hiện tại trừ đi PrevSumQty.

Dưới đây là nội dung của các cột liên quan đến kết quả từ C3:

 DemandID SupplyID TradeQ Số lượng ----------- ---------------- 1 1000 5.0000002 1000 3.0000002 1000 0.0000003 2000 6.0000003 3000 2.0000003 3000 0.0000005 4000 2.0000005 4000 0.0000006 5000 4.0000006 6000 3.0000006 7000 1.0000007 7.000 1.0000007 NULL 3.0000008 NULL 2.000000

Việc còn lại cho truy vấn bên ngoài phải làm là lọc ra các hàng thừa từ C3. Chúng bao gồm hai trường hợp:

Khi tổng số đang chạy của cả hai loại đều giống nhau, mục nhập cung cấp có số lượng giao dịch bằng không. Hãy nhớ thứ tự dựa trên SumQty và Code, vì vậy khi tổng số đang chạy giống nhau, mục nhập cầu sẽ xuất hiện trước mục nhập cung.
Các mục theo sau của một loại không thể khớp với các mục thuộc loại khác. Các mục nhập như vậy được đại diện bởi các hàng trong C3 trong đó DemandID là NULL hoặc SupplyID là NULL.

Kế hoạch cho giải pháp này được thể hiện trong Hình 2.

Hình 2:Kế hoạch truy vấn cho giải pháp của Itzik

Kế hoạch áp dụng một lần chuyển dữ liệu đầu vào và sử dụng bốn toán tử Tổng hợp Cửa sổ ở chế độ hàng loạt để xử lý các phép tính cửa sổ khác nhau. Tất cả các toán tử Tổng hợp Cửa sổ được đặt trước bởi các toán tử Sắp xếp rõ ràng, mặc dù chỉ có hai trong số đó là không thể tránh khỏi ở đây. Hai điều còn lại liên quan đến việc triển khai hiện tại của toán tử Tổng hợp Cửa sổ chế độ hàng loạt song song, không thể dựa vào đầu vào bảo toàn thứ tự song song. Một cách đơn giản để xem các toán tử Sắp xếp nào là do lý do này là buộc một kế hoạch nối tiếp và xem các toán tử Sắp xếp nào biến mất. Khi tôi buộc một kế hoạch nối tiếp với giải pháp này, các toán tử Sắp xếp thứ nhất và thứ ba sẽ biến mất.

Đây là thời gian chạy tính bằng giây mà tôi nhận được cho giải pháp này:

 100 nghìn:0,246200 nghìn:0,427300 nghìn:0,616400 nghìn:0,841>

Ian’s Solution

Giải pháp của Ian ngắn gọn và hiệu quả. Đây là mã giải pháp hoàn chỉnh:

 DROP TABLE NẾU TỒN TẠI #MyPairings; VỚI A AS (CHỌN *, SUM (Số lượng) HƠN (PHẦN THEO Mã ĐƠN ĐẶT HÀNG THEO ID ROWS CHƯA BAO GỒM CHÍNH XÁC) NHƯ CỘNG SỐ LƯỢNG TỪ dbo.Auctions), B AS (CHỌN Tích lũy Số lượng, Số lượng Tích lũy - LAG (Số lượng Tích lũy, 1, 0) HẾT (ĐƠN HÀNG THEO SỐ LƯỢNG TÍCH LŨY) NHƯ Số lượng giao dịch, MAX (TRƯỜNG HỢP KHI Mã ='D' THÌ ID END) NHƯ DemandID, MAX (TRƯỜNG HỢP KHI Mã ='S' THEN ID END) NHƯ Cung cấp từ một NHÓM THEO Tích lũy Số lượng, ID / ID - nhóm không có thật để cải thiện ước tính hàng - (số hàng trong Phiên đấu giá thay vì 2 hàng)), C AS (- điền vào NULL với cung / cầu tiếp theo - FIRST_VALUE (ID) BỎ QUA NULL ... - sẽ tốt hơn, nhưng điều này sẽ hoạt động bởi vì các ID theo thứ tự Số lượng tích lũy CHỌN MIN (DemandID) HƠN (ĐẶT HÀNG THEO LỆNH Tích lũy uantity ROWS GIỮA ROW HIỆN TẠI VÀ KHÔNG ĐƯỢC KẾT HỢP SAU ĐÂY) NHƯ SupplyID, TradeQuantity TỪ B) CHỌN DemandID, SupplyID, TradeQuantityINTO #MyPairingsFROM CWHERE SupplyID KHÔNG ĐẦY ĐỦ - cắt bớt nhu cầu chưa được đáp ứng và DemandID KHÔNG ĐẦY ĐỦ; - cắt bớt nguồn cung cấp không sử dụng

Mã trong CTE A truy vấn bảng Đấu giá và tính toán tổng số lượng cung và cầu đang chạy bằng cách sử dụng một hàm cửa sổ, đặt tên cho cột kết quả là Tích lũy Số lượng.

Mã trong CTE B truy vấn CTE A và nhóm các hàng theo Số lượng tích lũy. Việc nhóm này đạt được hiệu quả tương tự như cách tham gia bên ngoài của Brian dựa trên tổng số cung và cầu. Ian cũng đã thêm ID / ID biểu thức giả vào tập hợp nhóm để cải thiện số lượng ban đầu của nhóm theo ước tính. Trên máy của tôi, điều này cũng dẫn đến việc sử dụng gói song song thay vì gói nối tiếp.

Trong danh sách CHỌN, mã tính toán DemandID và SupplyID bằng cách truy xuất ID của loại mục nhập tương ứng trong nhóm bằng cách sử dụng tổng hợp MAX và biểu thức CASE. Nếu ID không có trong nhóm, kết quả là NULL. Mã cũng tính toán cột kết quả được gọi là TradeQuantity là số lượng tích lũy hiện tại trừ đi số trước đó, được truy xuất bằng cách sử dụng hàm cửa sổ LAG.

Đây là nội dung của B:

Tích lũy Số lượng Giao dịch Số lượng Nhu cầu Số lượng Cung cấp --------------------------------- - -------- 5.000000 5.000000 1 NULL 8.000000 3.000000 2 100014.000000 6.000000 NULL 200016.000000 2.000000 3 300018.000000 2.000000 5 400022.000000 4.000000 NULL 500025.000000 3.000000 NULL 600026.000000 1.000000 NULL 200016.000000 2.000000 3 300018.000000 2.000000 5 400022.000000 4.000000 NULL 500025.000000 3.000000 NULL 600026.000000 1.000000 6 NULL27.00000000 7 1.0000000000000000 trước 80003000>

Sau đó, mã trong CTE C sẽ truy vấn CTE B và điền vào NULL ID cung và cầu với ID cung và cầu không phải NULL tiếp theo, sử dụng chức năng cửa sổ MIN với khung GIỮA ĐƯỜNG HIỆN TẠI VÀ ĐƯỜNG DẪN SAU ĐÓ.

Đây là nội dung của C:

 DemandID SupplyID TradeQ Số lượng --------- ---------------- 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 7 NULL 3,000000 8 NULL 2,000000

Bước cuối cùng được xử lý bởi truy vấn bên ngoài đối với C là xóa các mục nhập của một loại mà không thể khớp với các mục nhập khác. Điều đó được thực hiện bằng cách lọc ra các hàng có SupplyID là NULL hoặc DemandID là NULL.

Kế hoạch cho giải pháp này được thể hiện trong Hình 3.

Hình 3:Kế hoạch truy vấn cho giải pháp Ian

Kế hoạch này thực hiện một lần quét dữ liệu đầu vào và sử dụng ba toán tử tổng hợp cửa sổ chế độ hàng loạt song song để tính toán các chức năng cửa sổ khác nhau, tất cả đều được đặt trước bởi toán tử Sắp xếp song song. Hai trong số đó là không thể tránh khỏi vì bạn có thể xác minh bằng cách bắt buộc một kế hoạch nối tiếp. Kế hoạch cũng sử dụng toán tử Hash Aggregate để xử lý việc nhóm và tổng hợp trong CTE B.

Đây là thời gian chạy tính bằng giây mà tôi nhận được cho giải pháp này:

 100K:0,214200K:0,363300K:0,546400K:0,701

Peter Larsson’s Solution

Giải pháp của Peter Larsson ngắn gọn, hấp dẫn và hiệu quả cao một cách đáng kinh ngạc. Đây là mã giải pháp hoàn chỉnh của Peter:

 DROP TABLE NẾU TỒN TẠI #MyPairings; WITH cteSource (ID, Code, RunningQuantity) AS (SELECT ID, Code, SUM (Quantity) OVER (PARTITION BY code ORDER BY ID) AS RunningQuantity FROM dbo.Auctions) CHỌN DemandID, SupplyID, TradeQuantityINTO #MyPairingsFROM (CHỌN MIN (CASE WHEN) Mã ='D' THÌ ID ELSE 2147483648 HẾT) HẾT (ĐẶT HÀNG THEO Số lượng đang chạy, Đường đi của mã GIỮA ĐƯỜNG HIỆN TẠI VÀ ĐƯỜNG DẪN SAU ĐÓ) NHƯ DemandID, MIN (TRƯỜNG HỢP KHI Mã ='S' THÌ ID ELSE 2147483648 HẾT) HẾT (ĐẶT HÀNG THEO Số lượng chạy, Mã ROWS GIỮA ROW HIỆN TẠI VÀ KHÔNG ĐƯỢC TỔNG HỢP SAU ĐÂY) NHƯ SupplyID, RunningQuantity - COALESCE (LAG (RunningQuantity) OVER (ORDER BY RunningQuantity, Code), 0.0) AS TradeQuantity from cteSource) AS dWHERE DemandID <2147483648 AND SupplyID <2147483648 AND SupplyID <2147483648 AND SupplyID <2147483648 AND SupplyID;

CTE cteSource truy vấn bảng Đấu giá và sử dụng hàm cửa sổ để tính tổng lượng cung và cầu đang chạy, gọi cột kết quả RunningQuantity.

Mã xác định bảng dẫn xuất d truy vấn cteSource và tính toán DemandID, SupplyID và TradeQuantity của các cặp kết quả, trước khi loại bỏ một số hàng thừa. Tất cả các hàm cửa sổ được sử dụng trong các tính toán đó đều dựa trên RunningQuantity và Code sắp xếp.

Cột kết quả d.DemandID được tính là ID nhu cầu tối thiểu bắt đầu bằng hiện tại hoặc 2147483648 nếu không tìm thấy.

Cột kết quả d.SupplyID được tính là ID nguồn cung cấp tối thiểu bắt đầu bằng hiện tại hoặc 2147483648 nếu không tìm thấy.

Kết quả TradeQuantity được tính bằng giá trị RunningQuantity của hàng hiện tại trừ đi giá trị RunningQuantity của hàng trước.

Đây là nội dung của d:

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

Điều còn lại cho truy vấn bên ngoài phải làm là lọc ra các hàng thừa từ d. Đó là những trường hợp số lượng giao dịch bằng 0 hoặc các mục nhập loại này không thể khớp với các mục nhập từ loại khác (có ID 2147483648).

Kế hoạch cho giải pháp này được thể hiện trong Hình 4.

Hình 4:Kế hoạch truy vấn cho giải pháp của Peter

Giống như kế hoạch của Ian, kế hoạch của Peter dựa trên một lần quét dữ liệu đầu vào và sử dụng ba toán tử tổng hợp cửa sổ chế độ hàng loạt song song để tính toán các chức năng cửa sổ khác nhau, tất cả đều có trước các toán tử Sắp xếp song song. Hai trong số đó là không thể tránh khỏi vì bạn có thể xác minh bằng cách bắt buộc một kế hoạch nối tiếp. Trong kế hoạch của Peter, không cần một nhà điều hành tổng hợp được nhóm lại như trong kế hoạch của Ian.

Cái nhìn sâu sắc của Peter đã cho phép một giải pháp ngắn gọn như vậy là nhận ra rằng đối với một mục nhập có liên quan của một trong hai loại, ID phù hợp của loại khác sẽ luôn xuất hiện sau này (dựa trên RunningQuantity và thứ tự mã). Sau khi xem giải pháp của Peter, chắc chắn tôi có cảm giác như tôi đã làm phức tạp hóa mọi thứ của mình lên quá mức!

Đây là thời gian chạy tính bằng giây mà tôi nhận được cho giải pháp này:

 100 nghìn:0,197200 nghìn:0,412300 nghìn:0,558400 nghìn:0,696

Paul White’s Solution

Giải pháp cuối cùng của chúng tôi được tạo ra bởi Paul White. Đây là mã giải pháp hoàn chỉnh:

 DROP TABLE NẾU TỒN TẠI #MyPairings; TẠO BẢNG #MyPairings (Số nguyên DemandID KHÔNG ĐỦ, Số nguyên SupplyID KHÔNG ĐỦ, Số thập phân TradeQuantity (19, 6) KHÔNG ĐỦ); ĐI CHÈN #MyPairings WITH (TABLOCK) (DemandID, SupplyID, TradeQuantity) CHỌN Q3.DemandID, Q3.SupplyID, Q3.TradeQuantityFROM (SELECT Q2.DemandID, Q2.SupplyID, TradeQuantity =- Chồng chéo khoảng thời gian CASE WHEN Q2.Code ='S' THEN CASE WHEN Q2.CumDemand> =Q2.IntEnd THEN Q2.IntLength WHEN Q2.CumDemand> Q2. IntStart THEN Q2.CumDemand - Q2.IntStart ELSE 0.0 KẾT THÚC KHI Q2.Code ='D' THEN CASE KHI Q2.CumSupply> =Q2.IntEnd THEN Q2.IntLength KHI Q2.CumSupply> Q2.IntStart SAU Q2.CumSupply - Q2. IntStart ELSE 0.0 END END FROM (CHỌN Q1.Code, Q1.IntStart, Q1.IntEnd, Q1.IntLength, DemandID =MAX (IIF (Q1.Code ='D', Q1.ID, 0)) OVER (ORDER BY Q1.IntStart, Q1.ID ROWS UNBOUNDED PRECEDING), SupplyID =MAX (IIF (Q1.Code ='S', Q1.ID, 0)) OVER (ORDER BY Q1.IntStart, Q1.ID ROWS UNBOUNDED PRECEDING), 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)) HẾT ( ORDER BY Q1.IntStart, Q1.ID ROWS UNBOUNDED PRECEDING) TỪ (- Khoảng thời gian nhu cầu CHỌN A.ID, A.Code, IntStart =SUM (A.Quantity) OVER (ORDER BY A.ID ROWS UNBOUNDED PRECEDING) - A. Định lượng, 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 - Khoảng cung cấp CHỌN 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 PRECEDING), IntLength =A.Số lượng TỪ dbo.Auctions AS A WHERE A.Code ='S') AS Q1) AS Q2) AS Q3WHERE Q3.TradeQ Số lượng> 0;

Mã xác định bảng dẫn xuất Q1 sử dụng hai truy vấn riêng biệt để tính toán khoảng cung và cầu dựa trên các tổng đang chạy và thống nhất hai truy vấn. Đối với mỗi khoảng thời gian, mã tính toán phần bắt đầu (IntStart), kết thúc (IntEnd) và độ dài (IntLength) của nó. Dưới đây là nội dung của Q1 theo thứ tự của IntStart và ID:

 Mã ID Bắt đầu IntEnd IntLength ----- ---------------- ---------- ---------- ---------- 1 D 0,000000 5.000000 5.0000001000 S 0.000000 8.000000 8.0000002 D 5.000000 8.000000 3.0000003 D 8.000000 16.000000 8.0000002000 S 8.000000 14.000000 6.0000003000 S 14.000000 16.000000 2.0000005 D 16.000000 18.000000 2.0000004000 S 16.000000 18.000000 2.0000006 D 18.000000 26.000000 8.0000005000 S 18.000000 22.000000 4.0000006000 S 22.000000 25.000000 3.0000007000 S 25.000000 27.000000 2.0000007 D 26.000000 30.000000 4.0000008 D 30.000000 32.000000 2.000000

Mã xác định bảng dẫn xuất Q2 truy vấn Q1 và tính toán các cột kết quả được gọi là DemandID, SupplyID, CumSupply và CumDemand. Tất cả các chức năng cửa sổ được sử dụng bởi mã này đều dựa trên IntStart và thứ tự ID và khung ROWS UNBOUNDED PRECEDING (tất cả các hàng cho đến hiện tại).

DemandID là ID nhu cầu tối đa cho đến hàng hiện tại hoặc 0 nếu không có.

SupplyID là ID nguồn cung cấp tối đa cho đến hàng hiện tại hoặc 0 nếu không có.

CumSupply là số lượng cung cấp tích lũy (độ dài khoảng cung cấp) cho đến hàng hiện tại.

CumDemand là số lượng nhu cầu tích lũy (độ dài khoảng nhu cầu) cho đến hàng hiện tại.

Đây là nội dung của Q2:

 Mã IntStart IntEnd IntEnd IntLength DemandID SupplyID CumSupply CumDemand ------------- ---------------- ---- ---------- ---------- ---------- D 0,000000 5,000000 5,000000 1 0 0,000000 5,000000S 0,000000 8,000000 8,000000 1 1000 8,000000 5,000000D 5,000000 8.000000 3,000000 2 1000 8.000000 8.000000D 8.000000 16.000000 8.000000 3 1000 8.000000 16.000000S 8.000000 14.000000 6.000000 3 2000 14.000000 16.000000S 14.000000 16.000000 2.000000 3. 8.000000 6 4000 18.000000 26.000000S 18.000000 22.000000 4.000000 6 5000 22.000000 26.000000S 22.000000 25.000000 3.000000 6 6000 25.000000 26.000000S 25.000000 27.000000 2.000000 6 7000 27.000000 26.000000D 26.000000 30.000000 4.000000 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.

Kết luận

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 ]