Trong Trận đấu gần nhất, Phần 1, tôi đã đề cập đến một thử thách T-SQL được cung cấp cho tôi bởi Karen Ly, Nhà phân tích thu nhập cố định của Jr. tại RBC. Thử thách liên quan đến hai bảng - T1 và T2, mỗi bảng có một cột khóa (keycol), một giá trị (val) và một số cột khác (được đại diện bằng một cột được gọi là các cột khác). Nhiệm vụ là đối sánh với từng hàng từ T1 với hàng từ T2 trong đó T2.val gần nhất với T1.val (chênh lệch tuyệt đối là thấp nhất thấp nhất), sử dụng giá trị T2.keycol thấp nhất làm dấu ngắt. Tôi đã cung cấp một số giải pháp quan hệ và thảo luận về đặc điểm hoạt động của chúng. Tôi cũng đã thách thức bạn thử và tìm một giải pháp hoạt động hợp lý trong trường hợp bạn không được phép / không thể tạo chỉ mục hỗ trợ. Trong Phần 2, tôi đã trình bày cách có thể đạt được điều này bằng cách sử dụng các giải pháp lặp lại. Tôi đã nhận được một số giải pháp dành cho người đọc rất thú vị từ Kamil Konsno, Alejandro Mesa và Radek Celuch và những giải pháp đó là trọng tâm của bài viết tháng này.
Dữ liệu mẫu
Xin nhắc lại, tôi đã cung cấp cả bộ dữ liệu mẫu lớn và nhỏ để bạn làm việc. Bộ nhỏ để kiểm tra tính hợp lệ của giải pháp của bạn và bộ lớn để kiểm tra hiệu suất của nó. Sử dụng mã sau để tạo cơ sở dữ liệu mẫu testdb và trong đó có các bảng mẫu T1 và T2:
- BẬT TÀI KHOẢN DbSET mẫu; IF DB_ID ('testdb') LÀ KHÔNG TẠO CƠ SỞ DỮ LIỆU testdb; ĐI SỬ DỤNG testdb; ĐI - Bảng mẫu T1 và BẢNG T2DROP NẾU TỒN TẠI dbo.T1, dbo.T2; TẠO BẢNG dbo.T1 (keycol INT NOT NULL IDENTITY CONSTRAINT PK_T1 PRIMARY KEY, val INT NOT NULL, othercols BINARY (100) NOT NULL CONSTRAINT DFT_T1_col1 DEFAULT (0xAA)); TẠO BẢNG dbo.T2 (keycol INT NOT NULL IDENTITY CONSTRAINT PK_T2 PRIMARY KEY, val INT NOT NULL, othercols BINARY (100) NOT NULL CONSTRAINT DFT_T2_col1 DEFAULT (0xBB)); Sử dụng mã sau để điền vào các bảng với tập hợp nhỏ dữ liệu mẫu:
- Điền vào T1 và T2 với các tập dữ liệu mẫu nhỏ BẢNG TRUNCATE dbo.T1; BẢNG TRUNCATE dbo.T2; CHÈN VÀO CÁC GIÁ TRỊ dbo.T1 (val) (1), (1), (3), (3), (5), (8), (13), (16), (18), (20), ( 21); CHÈN VÀO CÁC GIÁ TRỊ dbo.T2 (val) (2), (2), (7), (3), (3), (11), (11), (13), (17), (19);
Tôi sẽ sử dụng các bộ dữ liệu mẫu nhỏ khi mô tả logic của các giải pháp khác nhau và cung cấp các bộ kết quả trung gian cho các bước của giải pháp.
Sử dụng mã sau để tạo hàm trợ giúp GetNums và để điền vào các bảng với bộ dữ liệu mẫu lớn:
- Hàm trợ giúp để tạo chuỗi các số nguyên CHỨC NĂNG DROP NẾU TỒN TẠI dbo.GetNums; ĐI TẠO HOẶC CHỨC NĂNG ALTER dbo.GetNums (@low AS BIGINT, @high AS BIGINT) BẢNG TRẢ LẠI VỚI L0 AS (SELECT c FROM (SELECT 1 UNION TẤT CẢ CHỌN 1) AS 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 AS A CROSS JOIN L2 AS B), L4 AS (CHỌN 1 AS c TỪ L3 AS A CROSS JOIN L3 AS B), L5 AS (CHỌN 1 AS c TỪ L4 AS A CROSS JOIN L4 AS B), Số hạng NHƯ (CHỌN ROW_NUMBER () HẾT (ĐẶT HÀNG BẰNG (CHỌN ĐẦY ĐỦ)) NHƯ rownum TỪ L5) CHỌN ĐẦU (@high - @low + 1) @low + rownum - 1 NHƯ n TỪ CÁC SỐ LỆNH THEO rownum; ĐI - Điền vào T1 và T2 với các tập dữ liệu mẫu lớnDECLARE @ numrowsT1 AS INT =1000000, @ maxvalT1 AS INT =10000000, @ numrowsT2 AS INT =1000000, @ maxvalT2 AS INT =10000000; BẢNG TRUNCATE dbo.T1; BẢNG TRUNCATE dbo.T2; CHÈN VÀO dbo.T1 VỚI (TABLOCK) (val) CHỌN ABS (CHECKSUM (NEWID ()))% @ maxvalT1 + 1 AS val FROM dbo.GetNums (1, @ numrowsT1) AS Nums; CHÈN VÀO dbo.T2 VỚI (TABLOCK) (val) CHỌN ABS (CHECKSUM (NEWID ()))% @ maxvalT2 + 1 AS val FROM dbo.GetNums (1, @ numrowsT2) AS Nums;
Khi bạn muốn kiểm tra giải pháp của mình với các chỉ mục hỗ trợ, hãy sử dụng mã sau để tạo các chỉ mục đó:
TẠO CHỈ SỐ idx_val_key TRÊN dbo.T1 (val, keycol) BAO GỒM (othercols); TẠO CHỈ SỐ idx_val_key TRÊN dbo.T2 (val, keycol) BAO GỒM (othercols); TẠO CHỈ SỐ idx_valD_key TRÊN dbo.T2 (val DESC, keycol) BAO GỒM (sôcôla khác);
Khi bạn muốn kiểm tra giải pháp của mình mà không có chỉ mục hỗ trợ, hãy sử dụng mã sau để xóa các chỉ mục đó:
DROP INDEX NẾU CÓ idx_val_key TRÊN dbo.T1; DROP INDEX NẾU CÓ idx_val_key ON dbo.T2; DROP INDEX NẾU CÓ idx_valD_key ON dbo.T2;
Giải pháp 1 của Kamil Kosno - Sử dụng bảng tạm thời
Kamil Kosno đã gửi một vài - hai ý tưởng ban đầu của anh ấy và hai biến thể về các giải pháp của Alejandro và Radek. Giải pháp đầu tiên của Kamil sử dụng bảng tạm thời được lập chỉ mục. Thông thường, ngay cả khi bạn không được phép tạo chỉ mục hỗ trợ trên các bảng gốc, bạn vẫn được phép làm việc với các bảng tạm thời và với các bảng tạm thời, bạn luôn có thể tạo chỉ mục của riêng mình.
Đây là mã hoàn chỉnh của giải pháp:
DROP TABLE NẾU TỒN TẠI # T2; CHỌN MIN (keycol) AS keycol, valINTO # T2FROM dbo.T2GROUP BY val; TẠO CHỈ SỐ DUY NHẤT idx_nc_val_key ON # T2 (val, keycol); VỚI các lựa chọn tốt nhất NHƯ (CHỌN keycol NHƯ keycol1, val NHƯ val1, các loại sôcôla khác NHƯ các loại sôcôla khác1, TRƯỜNG HỢP KHI ĐẾN THÌ THÌ COALESCE (trước, nxt) KHI ABS (val - trước)Ở Bước 1 của giải pháp, bạn lưu trữ keycol tối thiểu cho mỗi val duy nhất trong một bảng tạm thời được gọi là # T2 và tạo chỉ mục hỗ trợ trên (val, keycol). Đây là mã triển khai bước này:
DROP TABLE NẾU TỒN TẠI # T2; CHỌN MIN (keycol) AS keycol, valINTO # T2FROM dbo.T2GROUP BY val; TẠO CHỈ SỐ DUY NHẤT idx_nc_val_key ON # T2 (val, keycol); CHỌN * TỪ # T2;Bảng tạm thời được điền với dữ liệu sau:
keycol val ------------- 1 24 33 76 118 139 1710 19Ở Bước 2 của giải pháp, bạn áp dụng như sau:
Đối với mỗi hàng trong T1, tính toán các giá trị trước và nxt từ # T2. Tính trước giá trị lớn nhất trong # T2 nhỏ hơn hoặc bằng giá trị trong T1. Tính nxt làm giá trị nhỏ nhất trong # T2 lớn hơn hoặc bằng giá trị trong T1.
Sử dụng biểu thức CASE để tính val2 dựa trên logic sau:
- Khi trước hoặc nxt là null, trả về giá trị khác không đầu tiên trong hai hoặc NULL nếu cả hai đều NULL.
- Khi chênh lệch tuyệt đối giữa val và trước nhỏ hơn chênh lệch tuyệt đối giữa val và nxt, trả về trước.
- Khi nếu chênh lệch tuyệt đối giữa val và nxt nhỏ hơn chênh lệch tuyệt đối giữa val và prv, hãy trả về nxt.
- Ngược lại, nếu nxt nhỏ hơn trước thì trả về nxt, nếu không thì trả về trước.
Đây là mã triển khai bước này:
CHỌN keycol AS keycol1, val AS val1, othercols AS othercols1, TRƯỜNG HỢP KHI (trước + nxt LÀ KHÔNG ĐỦ) THÌ COALESCE (trước, nxt) KHI ABS (val - trước)Mã này tạo ra kết quả sau:
keycol1 val1 othercols1 val2 ------------- ---------------- 1 1 0xAA 22 1 0xAA 23 3 0xAA 34 3 0xAA 35 5 0xAA 36 8 0xAA 77 13 0xAA 138 16 0xAA 179 18 0xAA 1710 20 0xAA 1911 21 0xAA 19Trong Bước 3 của giải pháp, bạn xác định một CTE được gọi là tốt nhất dựa trên truy vấn từ Bước 2. Sau đó, bạn kết hợp các kết quả tốt nhất với # T2 để nhận khóa và kết hợp kết quả với T2 để nhận phần còn lại của dữ liệu (các loại khác).
Đây là mã triển khai bước này:
SELECT keycol1, val1, SUBSTRING (othercols1, 1, 1) AS othercols1, tempT2.keycol AS keycol2, val2, SUBSTRING (T2.othercols, 1, 1) AS othercols2FROM tốt nhất AS B INNER JOIN # T2 AS tempT2 ON tempT2 .val =B.val2 INNER THAM GIA dbo.T2 TRÊN T2.keycol =tempT2.keycol;Kế hoạch cho giải pháp 1 của Kamil với các chỉ số hỗ trợ được thể hiện trong Hình 1.
Hình 1:Kế hoạch cho giải pháp 1 của Kamil với các chỉ mục
Nhánh đầu tiên của kế hoạch nhóm và tổng hợp dữ liệu từ T2 và ghi kết quả vào bảng tạm thời # T2. Lưu ý rằng nhánh này sử dụng thuật toán Tổng hợp luồng được sắp xếp trước dựa trên việc quét chỉ mục idx_valD_key theo thứ tự trên T2.
Dưới đây là số liệu thống kê về hiệu suất cho gói này:
thời gian chạy (giây):5,55, CPU (giây):16,6, đọc logic:6,687,172Kế hoạch cho giải pháp 1 của Kamil mà không có các chỉ mục hỗ trợ được thể hiện trong Hình 2.
Hình 2:Kế hoạch cho giải pháp 1 của Kamil không có chỉ mục
Sự khác biệt chính giữa kế hoạch này và kế hoạch trước đó là nhánh đầu tiên của kế hoạch, xử lý phần nhóm và tổng hợp ở Bước 1, lần này không thể kéo dữ liệu được sắp xếp trước từ chỉ mục hỗ trợ, vì vậy nó kéo dữ liệu không có thứ tự từ nhóm được phân nhóm. lập chỉ mục trên T2 và sau đó sử dụng thuật toán Hash Aggregate.
Dưới đây là số liệu thống kê về hiệu suất cho gói này:
thời gian chạy:6.44, CPU:19.3, đọc logic:6.688.277Giải pháp của Alejandro Mesa - Sử dụng kỹ thuật nonnull cuối cùng
Giải pháp của Alejandro sử dụng kỹ thuật không rỗng cuối cùng được mô tả ở đây.
Đây là mã hoàn chỉnh của giải pháp (được cung cấp ở đây mà không cần trả lại các loại sôcôla khác):
WITH R1 AS (SELECT keycol, val, tid, MAX (CASE WHEN tid =0 THEN CAST (val AS binary (4)) + CAST (keycol AS binary (4)) END) OVER (ORDER BY val, tid , keycol ĐƯỜNG LỐI GIỮA ĐOẠN CHÍNH XÁC CHƯA ĐƯỢC BAO GỒM VÀ 1 ĐOẠN CHÍNH XÁC) NHƯ dưới đây_binstr, MIN (TRƯỜNG HỢP KHI tid =0 THÌ ĐÚC (val AS binary (4)) + CAST (keycol AS binary (4)) KẾT THÚC) HẾT (ĐẶT HÀNG THEO val, tid, keycol ĐƯỜNG LỐI GIỮA 1 ĐƯỜNG SAU VÀ KHÔNG ĐƯỢC TỔNG HỢP SAU ĐÂY) NHƯ above_binstr FROM (CHỌN keycol, val, 1 NHƯ tid TỪ dbo.T1 ĐOÀN KẾT TẤT CẢ CHỌN MIN (keycol) NHƯ keycol, val, 0 NHƯ TRÊN TỪ NHÓM dbo.T2 THEO val) NHƯ T ), R2 AS (SELECT keycol, val, CAST (SUBSTRING (under_binstr, 1, 4) AS int) AS dưới đây_T2_val, CAST (SUBSTRING (dưới_binstr, 5, 4) AS int) AS dưới đây_T2_keycol, CAST (SUBSTRING (trên_binstr, 1, 4) AS int) AS above_T2_val, CAST (SUBSTRING (above_binstr, 5, 4) AS int) AS above_T2_keycol FROM R1 WHERE tid =1), R3 AS (CHỌN keycol, val, COALESCE (dưới_T2_val, trên_T2 _val) NHƯ bên dưới_T2_val, COALESCE (bên dưới_T2_keycol, bên trên_T2_keycol) NH bên dưới_T2_keycol, COALESCE (bên trên_T2_val, bên dưới_T2_val) NH bên trên_T2_val, COALESCE (bên trên_T2_keycol, bên dưới_T2_keycol) NHƯ bên trên_TEN2_keycol, valycol từ phía dưới. ) <=ABS (trên_T2_val - val) THÌ bên dưới_T2_keycol ELSE ở trên_T2_keycol HẾT NHƯ keycol2, TRƯỜNG HỢP KHI ABS (val - dưới_T2_val) <=ABS (trên_T2_val - val) THÌ bên dưới_T2_val ELSE ở trên_T2_val HẾT NHƯ val2FROM R3;Trong Bước 1 của giải pháp, bạn thống nhất các hàng từ T1 (gán cột kết quả được gọi là tid cho 1) với các hàng từ T2 (gán tid =0) và xác định một bảng dẫn xuất được gọi là T dựa trên kết quả. Sử dụng kỹ thuật nonull cuối cùng, dựa trên thứ tự của val, tid, keycol, đối với mỗi hàng hiện tại, bạn truy xuất giá trị của hàng tid =0 cuối cùng được nối thành một cột nhị phân được gọi là dưới đây_binstr. Tương tự, bạn truy xuất các giá trị của hàng tid =0 tiếp theo được nối vào một cột nhị phân có tên là trên_binstr.
Đây là mã triển khai bước này:
SELECT keycol, val, tid, MAX (CASE WHEN tid =0 THEN CAST (val AS binary (4)) + CAST (keycol AS binary (4)) END) HẾT (ĐẶT HÀNG THEO val, tid, keycol GIỮA CHƯA BAO GỒM CHÍNH XÁC VÀ 1 CHÍNH XÁC) NHƯ dưới đây_binstr, MIN (TRƯỜNG HỢP KHI tid =0 THEN CAST (val AS binary (4)) + CAST (keycol AS binary (4)) END) HẾT (ĐẶT HÀNG THEO val, tid, keycol CÁC CON GIAO TIẾP GIỮA 1 ĐANG THEO DÕI VÀ KHÔNG ĐƯỢC TỔ CHỨC THEO DÕI) AS above_binstrFROM (CHỌN keycol, val, 1 AS tid FROM dbo.T1 UNION ALL CHỌN MIN (keycol) AS keycol, val, 0 AS tid FROM dbo.T2 GROUP BY val) AS T;Mã này tạo ra kết quả sau:
keycol val tid dưới đây_binstr trên_binstr ----------- ----------- ----------- --------- ------------------ 1 1 1 NULL 0x00000002000000012 1 1 NULL 0x00000002000000011 2 0 NULL 0x00000003000000044 3 0 0x0000000200000001 0x00000007000000033 3 1 0x0000000300000004 0x00000007000000034 3 1 Các 08 0x00000011000000098 16 1 0x0000000D00000008 0x00000011000000099 17 0x0000000D00000008 0x000000130000000A9 18 1 0x0000001100000009 0x000000130000000A10 19 0 0x0000000D00000008 0x000000130000000A9 18 1 0x0000001100000009 0x000000130000000A10 19 0 0x0000000001Trong Bước 2 của giải pháp, bạn xác định CTE có tên là R1 dựa trên truy vấn từ Bước 1. Bạn truy vấn R1, chỉ lọc các hàng có tid =1 và trích xuất các giá trị riêng lẻ từ các chuỗi nhị phân được nối.
Đây là mã triển khai bước này:
CHỌN keycol, val, CAST (SUBSTRING (under_binstr, 1, 4) AS int) AS dưới đây_T2_val, CAST (SUBSTRING (dưới_binstr, 5, 4) AS int) AS dưới đây_T2_keycol, CAST (SUBSTRING (trên_binstr, 1, 4) AS int) AS above_T2_val, CAST (SUBSTRING (above_binstr, 5, 4) AS int) AS above_T2_keycolFROM R1WHERE tid =1;Mã này tạo ra kết quả sau:
keycol val dưới đây_T2_val dưới_T2_keycol ở trên_T2_val trên_T2_keycol ----------- ----------- ---------------- -------- ------------ --------------- 1 1 NULL NULL 2 12 1 NULL NULL 2 13 3 3 4 7 34 3 3 4 7 35 5 3 4 7 36 8 7 3 11 67 13 13 8 17 98 16 13 8 17 99 18 17 9 19 1010 20 19 10 NULL NULL11 21 19 10 NULL NULLTrong Bước 3 của giải pháp, bạn xác định CTE được gọi là R2 dựa trên truy vấn từ Bước 2. Sau đó, bạn tính toán các cột kết quả sau:
- dưới đây_T2_val:giá trị khác không đầu tiên giữa dưới_T2_val và trên_T2_val
- dưới đây_T2_keycol:giá trị khác không đầu tiên giữa dưới_T2_keycol và trên_T2_keycol
- above_T2_val:giá trị khác không đầu tiên giữa trên_T2_val và dưới_T2_val
- above_T2_keycol:giá trị khác không đầu tiên giữa trên_T2_keycol và dưới_T2_keycol
Đây là mã triển khai bước này:
SELECT keycol, val, COALESCE (dưới_T2_val, trên_T2_val) AS dưới_T2_val, COALESCE (dưới_T2_keycol, trên_T2_keycol) NHƯ dưới_T2_keycol, COALESCE (trên_T2_val, dưới_T2_val) AS trên_T2_val, COALESCE_Trom2 trên, COALES_Trom2 trên, COALESCE_TROM_RROM> R2Mã này tạo ra kết quả sau:
keycol val dưới đây_T2_val dưới_T2_keycol ở trên_T2_val trên_T2_keycol ----------- ----------- ---------------- -------- ------------ --------------- 1 1 2 1 2 12 1 2 1 2 13 3 3 4 7 34 3 3 4 7 35 5 3 4 7 36 8 7 3 11 67 13 13 8 17 98 16 13 8 17 99 18 17 9 19 1010 20 19 10 19 1011 21 19 10 19 10Trong Bước 4 của giải pháp, bạn xác định một CTE được gọi là R3 dựa trên truy vấn từ Bước 3. Bạn trả về bí danh keycol là T1_keycol và bí danh val là T1_val. Tính cột kết quả T2_keycol như sau:nếu chênh lệch tuyệt đối giữa val và dưới_T2_val nhỏ hơn hoặc bằng chênh lệch tuyệt đối giữa trên_T2_val và val, hãy trả về dưới_T2_keycol, nếu không thì trên_T2_keycol. Tính cột kết quả T2_val như sau:nếu chênh lệch tuyệt đối giữa val và dưới_T2_val nhỏ hơn hoặc bằng chênh lệch tuyệt đối giữa trên_T2_val và val, hãy trả về dưới_T2_val, nếu không thì ở trên_T2_val.
Đây là mã triển khai bước này:
CHỌN móc khóa AS keycol1, val AS val1, TRƯỜNG HỢP KHI ABS (val - dưới_T2_val) <=ABS (trên_T2_val - val) THÌ bên dưới_T2_keycol ELSE ở trên_T2_keycol KẾT THÚC NHƯ keycol2, TRƯỜNG HỢP KHI CÓ ABS (val - dưới_T2_val) <=ABS (trên_T2_val - val) THEN dưới đây_T2_val ELSE ở trên_T2_val END AS val2FROM R3;Kế hoạch cho giải pháp của Alejandro với các chỉ mục hỗ trợ được thể hiện trong Hình 3.
Hình 3:Kế hoạch cho giải pháp của Alejandro với các chỉ mục
Dưới đây là số liệu thống kê về hiệu suất cho gói này:
thời gian chạy:7.8, CPU:12.6, đọc logic:35.886Kế hoạch cho giải pháp của Alejandro mà không có chỉ mục hỗ trợ được thể hiện trong Hình 4.
Hình 4:Phương án cho giải pháp của Alejandro không có chỉ mục
Dưới đây là số liệu thống kê về hiệu suất cho gói này:
thời gian chạy:8.19, CPU:14.8, đọc logic:37.091Lưu ý rằng trong hai nhánh đầu tiên của kế hoạch trong Hình 4, có hai loại trước toán tử Kết hợp Hợp nhất (Concatenation) do thiếu các chỉ mục hỗ trợ. Những cách sắp xếp đó không cần thiết trong sơ đồ trong Hình 3 vì dữ liệu được truy xuất theo thứ tự trước từ các chỉ mục hỗ trợ.
Sự thay đổi của Kamil đối với giải pháp của Alejandro
Trong giải pháp này, Kamil cũng dựa vào tuyệt chiêu cuối cùng. Đây là mã hoàn chỉnh của giải pháp:
WITH all_vals AS (CHỌN keycol, val FROM dbo.T1 UNION TẤT CẢ CHỌN DISTINCT NULL, val FROM dbo.T2), phạm vi AS (CHỌN keycol, val, MAX (TRƯỜNG HỢP KHI keycol KHÔNG ĐỦ THÌ val END) HẾT (ĐƠN HÀNG BẰNG val, keycol ĐƯỜNG LỐI GIỮA ĐƯỜNG KÉO DÀI VÀ 1 ĐƯỜNG CHÍNH XÁC) NHƯ TRƯỚC, TỐI THIỂU (TRƯỜNG HỢP KHI keycol ĐẦY ĐỦ THÌ val KẾT THÚC) HẾT (ĐẶT HÀNG THEO val, CÁC ĐƯỜNG KÉO GIỮA 1 ĐƯỜNG DẪN SAU VÀ CÒN LẠI SAU ĐÂY) NHƯ nxt so với tất cả các khoảng thời gian () CHỌN keycol NHƯ keycol1, val NHƯ val1, TRƯỜNG HỢP KHI ABS (val - trước) <=ISNULL (ABS (val - nxt), trước) THÌ TRƯỚC HẾT Nxt KẾT THÚC NHƯ val2 TỪ các phạm vi ĐÓ keycol KHÔNG ĐẦY ĐỦ) CHỌN keycol1, val1, SUBSTRING (T1.othercols, 1, 1) AS othercols1, val2, T2.keycol AS keycol2, SUBSTRING (T2.othercols, 1, 1) AS othercols2 FROM match_vals AS M INNER JOIN (CHỌN *, ROW_NUMBER () HẾT (PHẦN BỞI val LỆNH BẰNG keycol) NHƯ rn TỪ dbo.T2) NHƯ T2 TRÊN T2.val =M.val2 VÀ rn =1 THAM GIA INNER dbo.T1 TRÊN T1.keycol =keycol1;Trong Bước 1 của giải pháp, bạn xác định CTE được gọi là tất cả các khoảng và phạm vi, trong đó bạn sử dụng kỹ thuật không rỗng cuối cùng để xác định cho từng giá trị trong T1 (trong đó keycol không phải là NULL) các phạm vi giá trị dưới (trước) và trên (nxt) từ T2 ( trong đó keycol là rỗng).
Đây là mã triển khai bước này:
WITH all_vals AS (CHỌN keycol, val FROM dbo.T1 UNION TẤT CẢ CHỌN DISTINCT NULL, val FROM dbo.T2), phạm vi AS (CHỌN keycol, val, MAX (TRƯỜNG HỢP KHI keycol KHÔNG ĐỦ THÌ val END) HẾT (ĐƠN HÀNG THEO val, keycol ĐƯỜNG LỐI GIỮA DÒNG CHƯA BAO GỒM VÀ 1 ĐƯỜNG CHÍNH XÁC) NHƯ TRƯỚC, MIN (TRƯỜNG HỢP KHI keycol ĐẦY ĐỦ THÌ val KẾT THÚC) HẾT (ĐẶT HÀNG THEO val, CÁC ĐƯỜNG KÉO GIỮA 1 ĐƯỜNG DẪN SAU VÀ CHƯA BẮT ĐẦU SAU) NHƯ nxt * TỪ tất cả các khoảng);Mã này tạo ra kết quả sau:
keycol val prev nxt ----------- ----------- ----------- -1 1 NULL 22 1 NULL 2NULL 2 NULL 3NULL 3 2 73 3 3 74 3 3 75 5 3 7NULL 7 3 116 8 7 11NULL 11 7 13NULL 13 11 177 13 13 178 16 13 17NULL 17 13 199 18 17 19NULL 19 17 NULL10 20 19 NULL11 21 19 NULLTrong Bước 2 của giải pháp, bạn truy vấn phạm vi CTE và chỉ lọc các hàng có keycol không rỗng. Bạn trả về cột keycol và val từ T1 tương ứng là keycol1 và val1. Sau đó, giữa giá trị trước và nxt, bạn trả về giá trị gần nhất với val1 là val2.
Đây là mã triển khai bước này:
CHỌN keycol NHƯ keycol1, val NHƯ val1, TRƯỜNG HỢP KHI ABS (val - trước) <=ISNULL (ABS (val - nxt), trước) THÌ trước đó ELSE nxt KẾT THÚC NHƯ dải val2FROM VÌ ĐÂU KÉO KHÔNG ĐỦ;Mã này tạo ra kết quả sau:
keycol1 val1 val2 ----------- ----------- ----------- 1 1 22 1 23 3 34 3 35 5 36 8 77 13 138 16 179 18 1710 20 1911 21 19Trong Bước 3 của giải pháp, bạn xác định một CTE được gọi là Match_vals dựa trên truy vấn từ Bước 2. Bạn cũng xác định một bảng dẫn xuất có tên là T2 trong đó sử dụng số hàng được phân vùng mà bạn xử lý logic tiebreak cho các hàng từ dbo.T2. Sau đó, bạn kết hợp các đợt khớp lệnh, CTE T2 và bảng T1 để xử lý lôgic đối sánh cuối cùng.
Đây là mã triển khai bước này:
SELECT keycol1, val1, SUBSTRING (T1.othercols, 1, 1) AS othercols1, val2, T2.keycol AS keycol2, SUBSTRING (T2.othercols, 1, 1) AS othercols2 FROM match_vals AS M INNER JOIN (CHỌN * , ROW_NUMBER () HẾT (PHẦN THEO LỆNH CỦA val BẰNG keycol) NHƯ rn TỪ dbo.T2) NHƯ T2 TRÊN T2.val =M.val2 VÀ rn =1 THAM GIA BÊN TRONG dbo.T1 TRÊN T1.keycol =keycol1;Kế hoạch về sự thay đổi của Kamil đối với giải pháp của Alejandro với các chỉ số hỗ trợ được thể hiện trong Hình 5.
Hình 5:Kế hoạch cho sự thay đổi của Kamil trên giải pháp của Alejandro với các chỉ mục
Dưới đây là số liệu thống kê về hiệu suất cho gói này:
thời gian chạy:11,5, CPU:18,3, đọc logic:59,218Kế hoạch về sự thay đổi của Kamil đối với giải pháp của Alejandro mà không có các chỉ mục hỗ trợ được thể hiện trong Hình 6.
Hình 6:Kế hoạch cho sự thay đổi của Kamil đối với giải pháp của Alejandro không có chỉ mục
Dưới đây là số liệu thống kê về hiệu suất cho gói này:
thời gian chạy:12,6, CPU:23,5, đọc logic:61,432Tương tự như các kế hoạch cho giải pháp của Alejandro, cũng trong trường hợp này, kế hoạch trong Hình 5 không yêu cầu sắp xếp rõ ràng trước khi áp dụng toán tử Merge Join (nối) vì dữ liệu được truy xuất được sắp xếp trước từ các chỉ mục hỗ trợ và kế hoạch trong Hình 6 không yêu cầu sắp xếp rõ ràng vì không có chỉ mục hỗ trợ.
Giải pháp của Radek Celuch - Sử dụng các khoảng thời gian
Radek đã nảy ra một ý tưởng đơn giản và đẹp mắt. Đối với mỗi giá trị khác biệt trong T2.val, bạn tính một khoảng thời gian biểu thị phạm vi giá trị từ T1.val sẽ khớp với T2.val hiện tại.
Đây là mã hoàn chỉnh của giải pháp:
WITH Pre1 AS (SELECT keycol, val, othercols, ROW_NUMBER () OVER (PARTITION BY val ORDER BY keycol) AS rn FROM dbo.T2), Pre2 AS (SELECT keycol, val, othercols, LAG (val) OVER ( ĐẶT HÀNG THEO val) NHƯ trước, DẪN (val) HẾT (ĐẶT HÀNG BẰNG val) NHƯ tiếp theo TỪ TRƯỚC 1 TẠI ĐÂU rn =1), T2 NHƯ (CHỌN keycol, val, sôcôla khác, ISNULL (val - (val - trước) / 2 + ( 1 - (val - trước)% 2), 0) AS thấp, ISNULL (val + (next - val) / 2, 2147483647) AS cao TỪ Pre2) CHỌN T1.keycol AS keycol1, T1.val AS val1, SUBSTRING ( T1.othercols, 1, 1) AS othercols1, T2.keycol AS keycol2, T2.val AS val2, SUBSTRING (T2.othercols, 1, 1) AS othercols2FROM dbo.T1 INNER JOIN T2 TRÊN T1.val GIỮA T2.low VÀ T2.high;Trong Bước 1 của giải pháp, bạn truy vấn T2 và tính số hàng (gọi cột rn), được phân vùng theo val và thứ tự theo keycol. Bạn xác định một CTE được gọi là Pre1 dựa trên truy vấn này. Sau đó, bạn truy vấn Pre1 và chỉ lọc các hàng có rn =1. Trong cùng một truy vấn, sử dụng LAG và LEAD, bạn trả về cho mỗi hàng giá trị của cột val từ hàng trước (gọi là trước) và từ hàng tiếp theo ( gọi nó tiếp theo).
Đây là mã triển khai bước này:
WITH Pre1 AS (SELECT keycol, val, othercols, ROW_NUMBER () OVER (PARTITION BY val ORDER BY keycol) AS rn FROM dbo.T2) SELECT keycol, val, othercols, LAG (val) OVER (ORDER BY val) AS trước, LEAD (val) OVER (ORDER BY val) AS nextFROM Pre1WHERE rn =1;Mã này tạo ra kết quả sau:
keycol val othercols trước đây ------- ------------- ---------------- -1 2 0xBB NULL 34 3 0xBB 2 73 7 0xBB 3 116 11 0xBB 7 138 13 0xBB 11 179 17 0xBB 13 1910 19 0xBB 17 NULLTrong Bước 2 của giải pháp, bạn xác định CTE được gọi là Pre2 dựa trên truy vấn từ Bước 1. Bạn truy vấn Pre2 và tính toán cho mỗi hàng một khoảng [thấp, cao] trong đó val từ T1 sẽ rơi vào. Dưới đây là các tính toán cho giá trị thấp và cao:
- thấp =ISNULL (val - (val - trước) / 2 + (1 - (val - trước)% 2), 0)
- cao =ISNULL (val + (tiếp theo - val) / 2, 2147483647)
Kiểm tra mod 2 về tính toán ranh giới thấp được sử dụng để đáp ứng yêu cầu T2.val thấp hơn và bộ lọc số hàng được sử dụng để đáp ứng yêu cầu T2.keycol thấp hơn. Các giá trị 0 và 2147483647 được sử dụng làm giới hạn cực thấp và trên.
Đây là mã triển khai bước này:
CHỌN keycol, val, sô cô la khác, ISNULL (val - (val - trước) / 2 + (1 - (val - trước)% 2), 0) Ở mức thấp, ISNULL (val + (tiếp theo - val) / 2 , 2147483647) AS highFROM Pre2;Mã này tạo ra kết quả sau:
keycol val othercols thấp cao ------- ----------- ----------- ----------- 1 2 0xBB 0 24 3 0xBB 3 53 7 0xBB 6 96 11 0xBB 10 128 13 0xBB 13 159 17 0xBB 16 1810 19 0xBB 19 2147483647Trong Bước 3 của giải pháp, bạn xác định một CTE được gọi là T2 dựa trên truy vấn từ Bước 2. Sau đó, bạn tham gia bảng T1 với các hàng khớp CTE T2 dựa trên val từ T1 nằm trong khoảng [thấp, cao] trong T2.
Đây là mã triển khai bước này:
CHỌN T1.keycol AS keycol1, T1.val AS val1, SUBSTRING (T1.othercols, 1, 1) AS othercols1, T2.keycol AS keycol2, T2.val AS val2, SUBSTRING (T2.othercols, 1, 1 ) AS othercols2FROM dbo.T1 INNER JOIN T2 TRÊN T1.val GIỮA T2.low VÀ T2.high;Kế hoạch cho giải pháp của Radek với các chỉ mục hỗ trợ được thể hiện trong Hình 7.
Hình 7:Kế hoạch cho giải pháp của Radek với các chỉ mục
Dưới đây là số liệu thống kê về hiệu suất cho gói này:
thời gian chạy:10.6, CPU:7.63, đọc logic:3.193.125Kế hoạch cho giải pháp của Radek mà không có chỉ mục hỗ trợ được thể hiện trong Hình 8.
Hình 8:Kế hoạch cho giải pháp của Radek không có chỉ mục
Dưới đây là số liệu thống kê về hiệu suất cho gói này:
thời gian chạy:18.1, CPU:27.4, đọc logic:5.827.360Ở đây, sự khác biệt về hiệu suất giữa hai kế hoạch là khá đáng kể. Kế hoạch trong Hình 8 yêu cầu sắp xếp sơ bộ trước khi tính toán các số hàng, kế hoạch trong Hình 7 thì không. Quan trọng hơn, để khớp từng khoảng thời gian với các hàng tương ứng từ T1, kế hoạch trong Hình 8 tạo ra một Chỉ mục Spool về cơ bản như một sự thay thế cho chỉ mục bị thiếu, trong khi kế hoạch trong Hình 7 chỉ đơn giản sử dụng chỉ mục hiện có idx_val_key trên T1. Đó là lý do chính dẫn đến sự khác biệt lớn giữa tất cả các thước đo hiệu suất. Tuy nhiên, hiệu suất mà không có chỉ mục hỗ trợ là hợp lý.
Sự thay đổi của Kamil đối với giải pháp của Radek
Kamil đã đưa ra một biến thể về giải pháp của Radek. Đây là mã hoàn chỉnh của giải pháp:
WITH T2_collapsed AS (SELECT keycol AS keycol2, val AS val2, ROW_NUMBER () OVER (PARTITION BY val ORDER BY keycol) AS rn FROM dbo.T2), phạm vi AS (SELECT keycol2 AS trước, val2 AS trước, LEAD ( keycol2) HẾT (ORDER BY val2) AS nxtkey, LEAD (val2) OVER (ORDER BY val2) AS nxtval FROM T2_collapsed WHERE rn =1), các đối sánh tốt nhất AS (CHỌN T1.keycol AS keycol1, T1.val AS val1, SUBSTRING (T1 .othercols, 1, 1) NHƯ các loại sôcôla khác1, TRƯỜNG HỢP KHI ABS (T1.val - trước) <=ABS (T1.val - nxtval) THÌ trước đó khóa ELSE nxtkey KẾT THÚC NHƯ keycol2, TRƯỜNG HỢP KHI ABS (T1.val - trước) <=ABS (T1.val - nxtval) THÌ thịnh hành ELSE nxtval KẾT THÚC NHƯ val2 TỪ các phạm vi INNER JOIN dbo.T1 ON trước đó <=T1.val VÀ T1.valĐây là mô tả riêng của Kamil về giải pháp này:
This solution is close to Radek's idea of checking against low and high range, although the ranges are based purely on actual T2 values. We get each row and the lead values only for each row in collapsed T2 (first step always gets rid of duplicate keys if found, by using row number or min(keycol) grouped by val on t2). The key concepts are how to check low and high range not to get duplicates – lower range inclusive, higher range exclusive, as well as handling the outliers (if present) by creating a separate set looking at the lowest and max values in T2 (UNION ALL bit). The check against the max value is done with inclusive range to complement the case of T1 vals being equal to the top T2 vals.
The plan for Kamil’s variation on Radek’s solution with supporting indexes is shown in Figure 9.
Figure 9:Plan for Kamil’s variation on Radek’s solution with indexes
Here are the performance stats for this plan:
run time:8.59, CPU:8.5, logical reads:3,206,849The plan for Kamil’s variation on Radek’s solution without supporting indexes is shown in Figure 10.
Figure 10:Plan for Kamil’s variation on Radek’s solution without indexes
Here are the performance stats for this plan:
run time:14, CPU:24.5, logical reads:5,870,596The plan in Figure 9 is serial and most of the calculations are done based on preordered data obtained from the supporting indexes. The plan in Figure 10 is parallel, plus there are a few sorts, and even an index spool activity. The performance measures of the latter plan are substantially higher than the former plan, but the performance in both cases is reasonable.
Solution 2 by Kamil Kosno – Using ranking, offset and aggregate window functions
Kamil came up with another original approach that is based on a combination of ranking, offset and aggregate window functions. Đây là mã hoàn chỉnh của giải pháp:
WITH A AS( SELECT 1 AS t, keycol,val, DENSE_RANK() OVER(ORDER BY val) AS rnk FROM dbo.T1 UNION ALL SELECT NULL, MIN(keycol), val, 0 FROM dbo.T2 GROUP BY val),B AS( SELECT t, keycol, val, CASE WHEN t =1 THEN DENSE_RANK() OVER (ORDER BY val, t) - rnk ELSE 0 END AS grp, LAG(CASE WHEN t IS NULL THEN val END) OVER(ORDER BY val, t) AS prev, LAG(CASE WHEN t IS NULL THEN keycol END) OVER(ORDER BY val, t) AS prevkey, LEAD(CASE WHEN t IS NULL THEN val END) OVER(ORDER BY val, t) AS nxt, LEAD(CASE WHEN t IS NULL THEN keycol END) OVER(ORDER BY val, t) AS nxtkey FROM A),C AS( SELECT keycol AS keycol1, val AS val1, MAX (prev) OVER(PARTITION BY grp ORDER BY prev DESC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS mxprev, MAX (prevkey) OVER(PARTITION BY grp ORDER BY prev DESC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS mxprevkey, MAX (nxt) OVER(PARTITION BY grp ORDER BY nxt ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) AS mxnxt, MAX (nxtkey) OVER(PARTITION BY grp ORDER BY nxt ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) AS mxnxtkey FROM B WHERE t =1),D AS( SELECT keycol1, val1, CASE WHEN ABS(val1 - mxprev) <=ISNULL(ABS(val1 - mxnxt), mxprev) THEN mxprevkey ELSE mxnxtkey END AS keycol2, CASE WHEN ABS(val1 - mxprev) <=ISNULL(ABS(val1 - mxnxt), mxprev) THEN mxprev ELSE mxnxt END AS val2 FROM C)SELECT D.keycol1, D.val1, D.keycol2, D.val2, SUBSTRING(T1.othercols, 1, 1) AS othercols1, SUBSTRING(T2.othercols, 1, 1) AS othercols2FROM D INNER JOIN dbo.T1 ON T1.keycol =D.keycol1 INNER JOIN dbo.T2 ON T2.keycol =D.keycol2;In Step 1 of the solution you unify the following result sets:
- Rows from T1 with a result column called t assigned with the constant 1 and column rnk representing dense rank values ordered by val
- Group rows from T2 by val and return val and min keycol for each group, with the result column t assigned with NULL and rnk with 0
Đây là mã triển khai bước này:
SELECT 1 AS t, keycol,val, DENSE_RANK() OVER(ORDER BY val) AS rnkFROM dbo.T1UNION ALLSELECT NULL, MIN(keycol), val, 0FROM dbo.T2GROUP BY val;Mã này tạo ra kết quả sau:
t keycol val rnk----------- ----------- ----------- --------------------1 1 1 11 2 1 11 3 3 21 4 3 21 5 5 31 6 8 41 7 13 51 8 16 61 9 18 71 10 20 81 11 21 9NULL 1 2 0NULL 4 3 0NULL 3 7 0NULL 6 11 0NULL 8 13 0NULL 9 17 0NULL 10 19 0In Step 2 of the solution you define a CTE called A based on the query from Step 1. You query A and compute group identifiers (grp) for T1 values that fall between ranges of distinct T2 values. This is done using an islands technique where you subtract rnk (dense ranks for only T1 values) from rnk2 (dense ranks for unified T1 values and distinct T2 values).
Using the LAG and LEAD functions, you compute for each T1 row the prev/next val and keycol values from T2, if present, and NULL otherwise. These calculations return values for the first and last rows in each group, if present, but NULLs for intermediate rows in groups.
Đây là mã triển khai bước này:
SELECT t, keycol, val, rnk, DENSE_RANK() OVER (ORDER BY val) AS rnk2, CASE WHEN t =1 THEN DENSE_RANK() OVER (ORDER BY val, t) - rnk ELSE 0 END AS grp, LAG(CASE WHEN t IS NULL THEN val END) OVER(ORDER BY val, t) AS prev, LAG(CASE WHEN t IS NULL THEN keycol END) OVER(ORDER BY val, t) AS prevkey, LEAD(CASE WHEN t IS NULL THEN val END) OVER(ORDER BY val, t) AS nxt, LEAD(CASE WHEN t IS NULL THEN keycol END) OVER(ORDER BY val, t) AS nxtkeyFROM A;Mã này tạo ra kết quả sau:
t keycol val rnk rnk2 grp prev prevkey nxt nxtkey----- ------ --- --- ---- --- ----- ------- ----- -------1 1 1 1 1 0 NULL NULL NULL NULL1 2 1 1 1 0 NULL NULL 2 1NULL 1 2 0 2 0 NULL NULL 3 4NULL 4 3 0 3 0 2 1 NULL NULL1 3 3 2 3 2 3 4 NULL NULL1 4 3 2 3 2 NULL NULL NULL NULL1 5 5 3 4 2 NULL NULL 7 3NULL 3 7 0 5 0 NULL NULL NULL NULL1 6 8 4 6 3 7 3 11 6NULL 6 11 0 7 0 NULL NULL 13 8NULL 8 13 0 8 0 11 6 NULL NULL1 7 13 5 8 5 13 8 NULL NULL1 8 16 6 9 5 NULL NULL 17 9NULL 9 17 0 10 0 NULL NULL NULL NULL1 9 18 7 11 6 17 9 19 10NULL 10 19 0 12 0 NULL NULL NULL NULL1 10 20 8 13 7 19 10 NULL NULL1 11 21 9 14 7 NULL NULL NULL NULLIn Step 3 you define a CTE called B based on the query from Step 2. You Query B and filter only original T1 rows (where t =1). In each group, you return the first row's prev and prevkey values, and last row's nxt and nxtkey values. Instead of just using a window partition clause, a window frame specification is used to define the minimal frame with the desired row to reduce I/O against the spool.
Đây là mã triển khai bước này:
SELECT keycol AS keycol1, val AS val1, MAX (prev) OVER(PARTITION BY grp ORDER BY prev DESC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS mxprev, MAX (prevkey) OVER(PARTITION BY grp ORDER BY prev DESC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS mxprevkey, MAX (nxt) OVER(PARTITION BY grp ORDER BY nxt ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) AS mxnxt, MAX (nxtkey) OVER(PARTITION BY grp ORDER BY nxt ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) AS mxnxtkeyFROM BWHERE t =1;Mã này tạo ra kết quả sau:
keycol1 val1 mxprev mxprevkey mxnxt mxnxtkey----------- ----------- ----------- ----------- ----------- -----------2 1 NULL NULL 2 11 1 NULL NULL 2 15 5 3 4 7 33 3 3 4 7 34 3 3 4 7 36 8 7 3 11 68 16 13 8 17 97 13 13 8 17 99 18 17 9 19 1010 20 19 10 NULL NULL11 21 19 10 NULL NULLIn Step 4 you define a CTE called C based on the query from Step 3. You query C to compute keycol2 and val2 based on the closest match.
Đây là mã triển khai bước này:
SELECT keycol1, val1, CASE WHEN ABS(val1 - mxprev) <=ISNULL(ABS(val1 - mxnxt), mxprev) THEN mxprevkey ELSE mxnxtkey END AS keycol2, CASE WHEN ABS(val1 - mxprev) <=ISNULL(ABS(val1 - mxnxt), mxprev) THEN mxprev ELSE mxnxt END AS val2FROM C;Mã này tạo ra kết quả sau:
keycol1 val1 keycol2 val2----------- ----------- ----------- -----------2 1 1 21 1 1 25 5 4 33 3 4 34 3 4 36 8 3 78 16 9 177 13 8 139 18 9 1710 20 10 1911 21 10 19In Step 5 you define a CTE called D based on the query from Step 4. You then join D with T1 and T2 to get the other needed columns.
Đây là mã triển khai bước này:
SELECT D.keycol1, D.val1, D.keycol2, D.val2, SUBSTRING(T1.othercols, 1, 1) AS othercols1, SUBSTRING(T2.othercols, 1, 1) AS othercols2FROM D INNER JOIN dbo.T1 ON T1.keycol =D.keycol1 INNER JOIN dbo.T2 ON T2.keycol =D.keycol2;The plan for solution 2 by Kamil with supporting indexes is shown in Figure 11.
Figure 11:Plan for solution 2 by Kamil with indexes
Here are the performance stats for this plan:
run time:18.1, CPU:34.4, logical reads:56,736The plan for solution 2 by Kamil without supporting indexes is shown in Figure 12.
Figure 12:Plan for solution 2 by Kamil without indexes
Here are the performance stats for this plan:
run time:20.3, CPU:38.9, logical reads:59,012As you can see, the Plan in Figure 12 involves a couple of extra sorts compared to the plan in Figure 1 to order the data for the two queries in the CTE A—one to support the dense rank calculation and the other to support the grouped query. Other than that, the rest of the work is similar in both. In the grand scheme of things, there’s a bit of extra CPU work and consequentially time penalty, but still both queries perform fairly reasonably.
Kết luận
This article concludes the series on the closest match challenge. It’s great to see the different creative ideas that Kamil, Alejandro and Radek came up with. Thanks to all of you for sending your solutions!
