Tháng trước, tôi đã trình bày câu đố của Peter Larsson về việc khớp cung với cầu. Tôi đã chỉ ra giải pháp dựa trên con trỏ đơn giản của Peter và giải thích rằng nó có tính năng mở rộng tuyến tính. Thách thức mà tôi để lại cho bạn là thử và đưa ra một giải pháp dựa trên cơ sở cho nhiệm vụ, và cậu bé, mọi người đã vượt qua thử thách chưa! Cảm ơn Luca, Kamil Kosno, Daniel Brown, Brian Walker, Joe Obbish, Rainer Hoffmann, Paul White, Charlie, và tất nhiên, Peter Larsson, vì đã gửi các giải pháp của bạn. Một số ý tưởng rất tuyệt vời và hoàn toàn sáng suốt.
Trong tháng này, tôi sẽ bắt đầu khám phá các giải pháp đã gửi, đại khái là đi từ những giải pháp hoạt động kém hơn đến những giải pháp hoạt động tốt nhất. Tại sao thậm chí phải bận tâm với những người hoạt động kém? Vì bạn vẫn có thể học hỏi được nhiều điều từ họ; ví dụ, bằng cách xác định các mẫu chống. Thật vậy, nỗ lực đầu tiên để giải quyết thách thức này đối với nhiều người, bao gồm cả tôi và Peter, dựa trên khái niệm giao nhau giữa các quãng. Điều đó xảy ra là kỹ thuật dựa trên vị từ cổ điển để xác định giao điểm khoảng cách có hiệu suất kém vì không có sơ đồ lập chỉ mục tốt để hỗ trợ nó. Bài viết này dành riêng cho cách tiếp cận kém hiệu quả này. Mặc dù hiệu suất kém, việc tìm ra giải pháp là một bài tập thú vị. Nó đòi hỏi thực hành kỹ năng mô hình hóa vấn đề theo cách cho phép xử lý dựa trên cơ sở. Điều thú vị là xác định được lý do dẫn đến hiệu suất không tốt, giúp bạn dễ dàng tránh được mô hình chống đối trong tương lai. Hãy nhớ rằng giải pháp này chỉ là điểm khởi đầu.
DDL và một tập nhỏ dữ liệu mẫu
Xin nhắc lại, nhiệm vụ liên quan đến việc truy vấn bảng có tên "Đấu giá". "Sử dụng mã sau để tạo bảng và điền vào bảng đó với một tập hợp nhỏ dữ liệu mẫu:
DROP TABLE NẾU TỒN TẠI 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'), SỐ LƯỢNG KHAI THÁC (19 , 6) KHÔNG ĐẦY ĐỦ CONSTRAINT ck_Auctions_Q Số lượng KIỂM TRA (Số lượng> 0)); ĐẶ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;
Nhiệm vụ của bạn là tạo các cặp khớp cung với mục cầu dựa trên thứ tự ID, ghi chúng vào một bảng tạm thời. Sau đây là kết quả mong muốn cho tập dữ liệu mẫu nhỏ:
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
Tháng trước, tôi cũng đã cung cấp mã mà bạn có thể sử dụng để điền vào bảng Đấu giá một tập hợp lớn dữ liệu mẫu, kiểm soát số lượng mục nhập cung và cầu cũng như phạm vi số lượng của chúng. Đảm bảo rằng bạn sử dụng mã từ bài viết tháng trước để kiểm tra hiệu suất của các giải pháp.
Lập mô hình dữ liệu dưới dạng các khoảng thời gian
Một ý tưởng hấp dẫn có lợi cho việc hỗ trợ các giải pháp dựa trên tập hợp là lập mô hình dữ liệu dưới dạng các khoảng thời gian. Nói cách khác, đại diện cho mỗi mục nhập cung và cầu dưới dạng một khoảng bắt đầu với tổng số lượng đang chạy của cùng một loại (cầu hoặc cung) cho đến nhưng không bao gồm hiện tại và kết thúc bằng tổng đang chạy bao gồm cả hiện tại, tất nhiên là dựa trên ID đặt hàng. Ví dụ:nhìn vào tập dữ liệu mẫu nhỏ, mục nhập nhu cầu đầu tiên (ID 1) dành cho số lượng là 5,0 và mục thứ hai (ID 2) dành cho số lượng là 3.0. Mục nhập nhu cầu đầu tiên có thể được biểu thị bằng khoảng thời gian bắt đầu:0,0, kết thúc:5,0 và mục thứ hai với khoảng thời gian bắt đầu:5,0, kết thúc:8,0, v.v. Tương tự, mục nhập cung đầu tiên (ID 1000) dành cho số lượng 8.0 và thứ hai (ID 2000) dành cho số lượng 6.0. Mục nhập cung cấp đầu tiên có thể được biểu thị với khoảng bắt đầu:0.0, kết thúc:8.0 và mục thứ hai với khoảng bắt đầu:8.0, kết thúc:14.0, v.v.
Các cặp cung cầu mà bạn cần tạo sau đó là các phân đoạn chồng chéo của các khoảng giao nhau giữa hai loại.
Điều này có lẽ được hiểu rõ nhất bằng cách mô tả trực quan mô hình dữ liệu dựa trên khoảng thời gian và kết quả mong muốn, như thể hiện trong Hình 1.
Hình 1:Lập mô hình Dữ liệu dưới dạng Khoảng
Mô tả trực quan trong Hình 1 khá dễ hiểu nhưng nói tóm lại…
Các hình chữ nhật màu xanh đại diện cho các mục nhập nhu cầu dưới dạng khoảng thời gian, hiển thị tổng số lượng đang chạy riêng khi bắt đầu khoảng thời gian và tổng số chạy bao gồm khi kết thúc khoảng thời gian. Các hình chữ nhật màu vàng cũng làm tương tự đối với các mục cung cấp. Sau đó, hãy chú ý xem các đoạn chồng chéo của các khoảng giao nhau của hai loại, được mô tả bằng các hình chữ nhật màu xanh lá cây, là các cặp cung - cầu mà bạn cần tạo ra như thế nào. Ví dụ:ghép nối kết quả đầu tiên là với ID nhu cầu 1, ID cung cấp 1000, số lượng 5. Kết quả ghép nối thứ hai là với ID nhu cầu 2, ID cung cấp 1000, số lượng 3. Và cứ tiếp tục như vậy.
Giao điểm ngắt quãng sử dụng CTE
Trước khi bạn bắt đầu viết mã T-SQL với các giải pháp dựa trên ý tưởng mô hình hóa khoảng thời gian, bạn nên có một cảm nhận trực quan về những chỉ mục nào có thể hữu ích ở đây. Vì bạn có khả năng sử dụng các hàm cửa sổ để tính tổng số đang chạy, bạn có thể hưởng lợi từ chỉ mục bao gồm khóa dựa trên các cột Mã, ID và bao gồm cả cột Số lượng. Đây là mã để tạo một chỉ mục như vậy:
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);
Đó cũng là chỉ mục mà tôi đã đề xuất cho giải pháp dựa trên con trỏ mà tôi đã đề cập vào tháng trước.
Ngoài ra, có tiềm năng ở đây để hưởng lợi từ xử lý hàng loạt. Bạn có thể cho phép xem xét nó mà không cần yêu cầu của chế độ hàng loạt trên cửa hàng, ví dụ:sử dụng SQL Server 2019 Enterprise trở lên, bằng cách tạo chỉ mục cột lưu trữ giả sau:
TẠO CHỈ SỐ KHÔNG CHỈNH SỬA CỘT KHÔNG CHỈNH SỬA idx_cs TRÊN dbo.Auctions (ID) WHERE ID =-1 AND ID =-2;
Bây giờ bạn có thể bắt đầu làm việc với mã T-SQL của giải pháp.
Đoạn mã sau tạo các khoảng thời gian biểu thị các mục nhập nhu cầu:
WITH D0 AS-- D0 tính toán nhu cầu đang chạy dưới dạng EndDemand (CHỌN ID, Số lượng, SUM (Số lượng) HƠN (ĐẶT HÀNG THEO ID ROWS CHƯA BAO GỒM CHÍNH XÁC) AS EndDemand TỪ dbo.Auctions WHERE Code ='D'), - D trích xuất trước EndDemand dưới dạng StartDemand, thể hiện nhu cầu đầu cuối dưới dạng khoảng D AS (SELECT ID, Quantity, EndDemand - Quantity AS StartDemand, EndDemand FROM D0) SELECT * FROM D;
Truy vấn xác định CTE D0 lọc các mục nhu cầu từ bảng Đấu giá và tính tổng số lượng đang chạy làm dấu phân cách cuối của các khoảng nhu cầu. Sau đó, truy vấn xác định CTE thứ hai được gọi là D truy vấn D0 và tính toán dấu phân cách bắt đầu của các khoảng nhu cầu bằng cách lấy dấu phân cách cuối trừ đi số lượng hiện tại.
Mã này tạo ra kết quả sau:
ID Số lượng StartDemand EndDemand ------------- ---------------- ---------- 1 5.000000 0.000000 5.0000002 3.000000 5.000000 8.0000003 8.000000 8.000000 16.0000005 2.000000 16.000000 18.0000006 8.000000 18.000000 26.0000007 4.000000 26.000000 30.0000008 2.000000 30.000000 32.000000
Các khoảng cung cấp được tạo ra rất giống nhau bằng cách áp dụng cùng một logic cho các mục cung cấp, sử dụng mã sau:
WITH S0 AS-- S0 tính toán nguồn cung đang chạy dưới dạng EndSupply (CHỌN ID, Số lượng, SUM (Số lượng) HƠN (ĐẶT HÀNG THEO ID ROWS UNBOUNDED PRECEDING) AS EndSupply FROM dbo.Auctions WHERE Code ='S'), - S trích xuất trước EndSupply dưới dạng StartSupply, thể hiện nguồn cung đầu cuối dưới dạng khoảngS AS (SELECT ID, Quantity, EndSupply - Quantity AS StartSupply, EndSupply FROM S0) SELECT * FROM S;
Mã này tạo ra kết quả sau:
ID Số lượng StartSupply EndSupply ----- ---------------- ------------ 1000 8.000000 0.000000 8.0000002000 6.000000 8.000000 14.0000003000 2.000000 14.000000 16.0000004000 2.000000 16.000000 18.0000005000 4.000000 18.000000 22.0000006000 3.000000 22.000000 25.0000007000 2.000000 25.000000 27.000000
Những gì còn lại sau đó là xác định các khoảng cung và cầu giao nhau từ CTE D và S, đồng thời tính toán các phân đoạn chồng chéo của các khoảng giao nhau đó. Hãy nhớ rằng các cặp kết quả nên được ghi vào một bảng tạm thời. Điều này có thể được thực hiện bằng cách sử dụng mã sau:
- Thả bảng tạm thời nếu tồn tại BẢNG XỬ LÝ NẾU TỒN TẠI #MyPairings; VỚI D0 AS-- D0 tính toán nhu cầu đang chạy dưới dạng EndDemand (CHỌN ID, Số lượng, SUM (Số lượng) OVER (ĐẶT HÀNG THEO ID ROWS UNBOUNDED PRECEDING) AS EndDemand TỪ dbo. Đấu giá WHERE Code ='D'), - D trích xuất EndDemand trước dưới dạng StartDemand, thể hiện nhu cầu đầu cuối dưới dạng khoảng D AS (SELECT ID, Quantity, EndDemand - Quantity AS StartDemand, EndDemand FROM D0), S0 AS-- S0 tính toán nguồn cung đang chạy dưới dạng EndSupply (SELECT ID, Quantity, SUM (Quantity) OVER (ORDER BY ID ROWS UNBOUNDED PRECEDING) AS EndSupply FROM dbo.Auctions WHERE Code ='S'), - S trích xuất trước EndSupply dưới dạng StartSupply, thể hiện nguồn cung đầu cuối như một khoảng thời gianS AS (CHỌN ID, Số lượng, EndSupply - Số lượng AS StartSupply, EndSupply FROM S0) - Truy vấn bên ngoài xác định các giao dịch là các phân đoạn chồng chéo của các khoảng giao nhau - Khi đó, trong các khoảng cung và cầu giao nhau, số lượng giao dịch là - ÍT NHẤT (EndDemand, EndSupply) - LỚN NHẤT (StartDemsnad, StartSupply) CHỌN D.ID AS DemandID, S.ID AS SupplyID, TRƯỜNG hợp WH EN EndDemandStartSupply THEN StartDemand ELSE StartSupply END AS TradeQuantityINTO #MyPairingsFROM D INNER JOIN S ON D.StartDemand Bên cạnh mã tạo khoảng cung và cầu mà bạn đã thấy trước đó, phần bổ sung chính ở đây là truy vấn bên ngoài, xác định các khoảng giao nhau giữa D và S và tính toán các phân đoạn chồng chéo. Để xác định các khoảng giao nhau, truy vấn bên ngoài kết hợp D và S bằng cách sử dụng vị từ nối sau: D.StartDemandS.StartSupply Đó là vị từ cổ điển để xác định giao điểm giữa các khoảng. Đó cũng là nguyên nhân chính dẫn đến hiệu suất kém của giải pháp, như tôi sẽ giải thích ngay sau đây.
Truy vấn bên ngoài cũng tính toán số lượng giao dịch trong danh sách CHỌN như:
ÍT NHẤT (EndDemand, EndSupply) - TUYỆT VỜI NHẤT (StartDemand, StartSupply)Nếu bạn đang sử dụng Azure SQL, bạn có thể sử dụng biểu thức này. Nếu bạn đang sử dụng SQL Server 2019 trở xuống, bạn có thể sử dụng giải pháp thay thế tương đương về mặt logic sau:
TRƯỜNG HỢP KHI EndDemandStartSupply THEN StartDemand ELSE StartSupply END Vì yêu cầu là ghi kết quả vào một bảng tạm thời, nên truy vấn bên ngoài sử dụng câu lệnh SELECT INTO để đạt được điều này.
Ý tưởng lập mô hình dữ liệu dưới dạng khoảng thời gian rõ ràng là rất hấp dẫn và tao nhã. Nhưng về hiệu suất thì sao? Thật không may, giải pháp cụ thể này có một vấn đề lớn liên quan đến cách xác định giao điểm. Kiểm tra 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 các nút giao thông sử dụng giải pháp CTEs
Hãy bắt đầu với những phần không tốn kém của kế hoạch.
Đầu vào bên ngoài của phép nối Vòng lặp lồng nhau tính toán các khoảng nhu cầu. Nó sử dụng toán tử Tìm kiếm chỉ mục để truy xuất các mục nhập nhu cầu và toán tử Tổng hợp cửa sổ chế độ hàng loạt để tính toán dấu phân cách cuối khoảng nhu cầu (được gọi là Expr1005 trong kế hoạch này). Dấu phân cách bắt đầu khoảng nhu cầu sau đó là Expr1005 - Số lượng (từ D).
Lưu ý thêm, bạn có thể thấy việc sử dụng toán tử Sắp xếp rõ ràng trước toán tử Tổng hợp Cửa sổ chế độ hàng loạt đáng ngạc nhiên ở đây, vì các mục nhập nhu cầu được truy xuất từ Tìm kiếm Chỉ mục đã được sắp xếp theo ID giống như hàm cửa sổ cần chúng. Điều này liên quan đến thực tế là hiện tại, SQL Server 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 một toán tử Window Aggregate ở chế độ hàng loạt song song. Nếu bạn buộc một kế hoạch nối tiếp chỉ cho mục đích thử nghiệm, bạn sẽ thấy toán tử Sắp xếp biến mất. SQL Server quyết định tổng thể, việc sử dụng song song ở đây được ưu tiên hơn, mặc dù nó dẫn đến việc sắp xếp rõ ràng được bổ sung. Nhưng một lần nữa, phần kế hoạch này đại diện cho một phần nhỏ công việc trong kế hoạch tổng thể của mọi thứ.
Tương tự, đầu vào bên trong của phép nối Vòng lặp lồng nhau bắt đầu bằng cách tính toán các khoảng cung cấp. Thật kỳ lạ, SQL Server đã chọn sử dụng các toán tử chế độ hàng để xử lý phần này. Mặt khác, các toán tử chế độ hàng được sử dụng để tính toán tổng số đang chạy liên quan đến chi phí cao hơn so với thay thế Chế độ hàng loạt Window Aggregate; mặt khác, SQL Server có triển khai song song hiệu quả hoạt động chỉ mục bảo toàn thứ tự theo sau bởi tính toán của hàm cửa sổ, tránh Sắp xếp rõ ràng cho phần này. Thật kỳ lạ khi trình tối ưu hóa đã chọn một chiến lược cho các khoảng nhu cầu và một chiến lược khác cho các khoảng cung. Ở bất kỳ tốc độ nào, toán tử Tìm kiếm chỉ mục truy xuất các mục cung cấp và chuỗi toán tử tiếp theo cho đến toán tử Vô hướng tính toán tính toán dấu phân cách cuối khoảng cung cấp (được gọi là Expr1009 trong kế hoạch này). Dấu phân cách bắt đầu khoảng cung cấp sau đó là Expr1009 - Số lượng (từ S).
Mặc dù tôi đã sử dụng nhiều văn bản để mô tả hai phần này, nhưng phần thực sự đắt giá của công việc trong kế hoạch là phần tiếp theo.
Phần tiếp theo cần nối các khoảng cầu và khoảng cung bằng cách sử dụng vị từ sau:
D.StartDemandS.StartSupply Không có chỉ số hỗ trợ, giả sử khoảng cầu DI và khoảng cung SI, điều này sẽ liên quan đến việc xử lý hàng DI * SI. Kế hoạch trong Hình 2 được tạo sau khi điền vào bảng Đấu giá 400.000 hàng (200.000 mục nhập cầu và 200.000 mục nhập cung). Vì vậy, không có chỉ mục hỗ trợ, kế hoạch sẽ cần phải xử lý 200.000 * 200.000 =40.000.000.000 hàng. Để giảm thiểu chi phí này, trình tối ưu hóa đã chọn tạo chỉ mục tạm thời (xem toán tử Bộ chỉ mục) với dấu phân cách cuối khoảng cung cấp (Expr1009) làm khóa. Đó là khá nhiều điều tốt nhất nó có thể làm. Tuy nhiên, điều này chỉ giải quyết một phần của vấn đề. Với hai vị từ phạm vi, chỉ một vị từ tìm kiếm chỉ mục có thể được hỗ trợ. Còn lại phải được xử lý bằng cách sử dụng một vị từ dư. Thật vậy, bạn có thể thấy trong kế hoạch rằng tìm kiếm trong chỉ mục tạm thời sử dụng vị từ tìm kiếm Expr1009> Expr1005 - D.Quantity, theo sau là toán tử Bộ lọc xử lý vị từ còn lại Expr1005> Expr1009 - S.Quantity.
Giả sử trung bình, vị từ tìm kiếm tách biệt một nửa số hàng cung khỏi chỉ mục trên mỗi hàng nhu cầu, tổng số hàng được phát ra từ toán tử Bộ chỉ mục và được xử lý bởi toán tử Bộ lọc khi đó là DI * SI / 2. Trong trường hợp của chúng tôi, với 200.000 hàng cầu và hàng 200.000 hàng cung, điều này có nghĩa là 20.000.000.000. Thật vậy, mũi tên đi từ toán tử Bộ đệm chỉ mục đến toán tử Bộ lọc báo cáo một số hàng gần với giá trị này.
Kế hoạch này có tỷ lệ mở rộng bậc hai, so với tỷ lệ tuyến tính của giải pháp dựa trên con trỏ từ tháng trước. Bạn có thể xem kết quả của một bài kiểm tra hiệu suất so sánh hai giải pháp trong Hình 3. Bạn có thể thấy rõ hình parabol có hình dạng độc đáo cho giải pháp dựa trên tập hợp.
Hình 3:Hiệu suất các nút giao thông sử dụng giải pháp CTEs so với giải pháp dựa trên con trỏ
Giao lộ ngắt quãng sử dụng bảng tạm thời
Bạn có thể cải thiện phần nào mọi thứ bằng cách thay thế việc sử dụng CTE cho các khoảng cung và cầu bằng các bảng tạm thời và để tránh cuộn chỉ mục, hãy tạo chỉ mục của riêng bạn trên bảng tạm thời giữ các khoảng cung với dấu phân cách cuối làm chìa khóa. Đây là mã của giải pháp hoàn chỉnh:
- Bỏ bảng tạm thời nếu tồn tại BẢNG THẢM NẾU TỒN TẠI #MyPairings, #Demand, #Supply; VỚI D0 AS-- D0 tính toán nhu cầu đang chạy dưới dạng EndDemand (CHỌN ID, Số lượng, SUM (Số lượng) OVER (ĐẶT HÀNG THEO ID ROWS UNBOUNDED PRECEDING) AS EndDemand TỪ dbo. Đấu giá WHERE Code ='D'), - D trích xuất EndDemand trước dưới dạng StartDemand, thể hiện nhu cầu đầu cuối dưới dạng khoảng D AS (SELECT ID, Quantity, EndDemand - Quantity AS StartDemand, EndDemand FROM D0) SELECT ID, Quantity, CAST (ISNULL (StartDemand, 0.0) AS DECIMAL (19, 6)) AS StartDemand, CAST (ISNULL (EndDemand, 0.0) AS DECIMAL (19, 6)) AS EndDemandINTO #DemandFROM D; WITH S0 AS-- S0 tính toán nguồn cung cấp đang chạy dưới dạng EndSupply (CHỌN ID, Số lượng, SUM (Số lượng) HƠN (ĐẶT HÀNG THEO ID ROWS UNBOUNDED PRECEDING) AS EndSupply FROM dbo.Auctions WHERE Code ='S'), - S trích xuất trước EndSupply dưới dạng StartSupply, biểu thị nguồn cung đầu cuối như một khoảng thời gianS AS (SELECT ID, Quantity, EndSupply - Số lượng AS StartSupply, EndSupply FROM S0) CHỌN ID, Số lượng, CAST (ISNULL (StartSupply, 0.0) AS DECIMAL (19, 6)) AS StartSupply, CAST (ISNULL (EndSupply, 0.0) AS DECIMAL (19, 6)) AS EndSupplyINTO #SupplyFROM S; TẠO CHỈ SỐ ĐƯỢC ĐIỀU CHỈNH DUY NHẤT idx_cl_ES_ID TRÊN #Supply (EndSupply, ID); - Truy vấn bên ngoài xác định các giao dịch là các phân đoạn chồng chéo của các khoảng giao nhau - Trong các khoảng cung và cầu giao nhau, số lượng giao dịch khi đó là - ÍT NHẤT (EndDemand, EndSupply) - LỚN NHẤT (StartDemsnad, StartSupply) CHỌN D.ID AS DemandID, S.ID AS SupplyID, CASE WHEN EndDemandStartSupply THEN StartDemand ELSE StartSupply END AS TradeQuantityINTO #MyPairingsFROM #Demand AS D INNEREEK #Supply S.EndSupply VÀ D.EndDemand> S.StartSupply; Các 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 các nút giao thông sử dụng giải pháp bảng tạm
Hai kế hoạch đầu tiên sử dụng sự kết hợp của các toán tử Tổng hợp chỉ mục theo chế độ Tìm kiếm + Sắp xếp + Cửa sổ để tính toán các khoảng cung và cầu và ghi chúng vào các bảng tạm thời. Kế hoạch thứ ba xử lý việc tạo chỉ mục trên bảng #Supply với dấu phân tách EndSupply làm khóa hàng đầu.
Kế hoạch thứ tư đại diện cho phần lớn công việc, với toán tử tham gia Vòng lặp lồng nhau khớp với từng khoảng từ #Demand, các khoảng giao nhau từ #Supply. Cũng quan sát điều đó ở đây, toán tử Tìm kiếm chỉ mục dựa vào vị từ # Supply.EndSupply> # Demand.StartDemand làm vị từ tìm kiếm và # Demand.EndDemand> # Supply.StartSupply làm vị từ còn lại. Vì vậy, về độ phức tạp / tỷ lệ, bạn sẽ có được độ phức tạp bậc hai giống như đối với giải pháp trước đó. Bạn chỉ phải trả ít hơn cho mỗi hàng vì bạn đang sử dụng chỉ mục của riêng mình thay vì ống chỉ mục được sử dụng bởi gói trước đó. Bạn có thể thấy hiệu suất của giải pháp này so với hai giải pháp trước trong Hình 5.
Hình 5:Hiệu suất của các nút giao thông sử dụng bảng tạm thời so với hai giải pháp khác
Như bạn có thể thấy, giải pháp với bảng tạm hoạt động tốt hơn giải pháp với CTE, nhưng nó vẫn có tỷ lệ bậc hai và hoạt động rất kém so với con trỏ.
Tiếp theo là gì?
Bài viết này đề cập đến nỗ lực đầu tiên trong việc xử lý nhiệm vụ khớp cung với cầu cổ điển bằng cách sử dụng một giải pháp dựa trên tập hợp. Ý tưởng là lập mô hình dữ liệu dưới dạng các khoảng thời gian, khớp cung với các mục cầu bằng cách xác định các khoảng cung và cầu giao nhau, sau đó tính toán số lượng giao dịch dựa trên quy mô của các phân đoạn chồng chéo. Chắc chắn là một ý tưởng hấp dẫn. Vấn đề chính của nó cũng là vấn đề kinh điển của việc xác định giao điểm khoảng bằng cách sử dụng hai vị từ phạm vi. Ngay cả với chỉ mục tốt nhất tại chỗ, bạn chỉ có thể hỗ trợ một vị từ phạm vi với một tìm kiếm chỉ mục; vị từ phạm vi khác phải được xử lý bằng cách sử dụng một vị từ còn lại. Điều này dẫn đến một kế hoạch có độ phức tạp bậc hai.
Vậy bạn có thể làm gì để vượt qua trở ngại này? Có một số ý tưởng khác nhau. Một ý tưởng tuyệt vời thuộc về Joe Obbish, bạn có thể đọc chi tiết trong bài đăng trên blog của anh ấy. Tôi sẽ trình bày các ý tưởng khác trong các bài viết sắp tới của loạt bài này.
[Bước tới:Thử thách ban đầu | Giải pháp:Phần 1 | Phần 2 | Phần 3]
