Tìm "Thời gian chờ" theo Tổng hợp thay vì Kết hợp
Tôi muốn chia sẻ một truy vấn thực sự hoang dã mà chỉ cần 1 lần quét bảng với 1 lần đọc logic. Để so sánh, câu trả lời khác tốt nhất trên trang, truy vấn của Simon Kingston, thực hiện 2 lần quét.
Trên một tập dữ liệu rất lớn (17.408 hàng đầu vào, tạo ra 8.193 hàng kết quả), cần CPU 574 và thời gian 2645, trong khi truy vấn của Simon Kingston lấy CPU 63.820 và thời gian là 37.108.
Có thể với các chỉ mục, các truy vấn khác trên trang có thể hoạt động tốt hơn nhiều lần, nhưng tôi thấy thú vị khi đạt được cải thiện 111x CPU và cải thiện tốc độ 14x chỉ bằng cách viết lại truy vấn.
(Xin lưu ý:Ý tôi là không có sự thiếu tôn trọng nào đối với Simon Kingston hay bất kỳ ai khác; tôi chỉ đơn giản là vui mừng về ý tưởng của tôi cho truy vấn này rất tốt. Truy vấn của anh ấy tốt hơn của tôi vì hiệu suất của nó rất nhiều và nó thực sự dễ hiểu và có thể duy trì , không giống như của tôi.)
Đây là truy vấn bất khả thi. Thật là khó hiểu. Thật khó để viết. Nhưng nó là tuyệt vời. :)
WITH Ranks AS (
SELECT
T = Dense_Rank() OVER (ORDER BY Time, Num),
N = Dense_Rank() OVER (PARTITION BY Name ORDER BY Time, Num),
*
FROM
#Data D
CROSS JOIN (
VALUES (1), (2)
) X (Num)
), Items AS (
SELECT
FromTime = Min(Time),
ToTime = Max(Time),
Name = IsNull(Min(CASE WHEN Num = 2 THEN Name END), Min(Name)),
I = IsNull(Min(CASE WHEN Num = 2 THEN T - N END), Min(T - N)),
MinNum = Min(Num)
FROM
Ranks
GROUP BY
T / 2
)
SELECT
FromTime = Min(FromTime),
ToTime = CASE WHEN MinNum = 2 THEN NULL ELSE Max(ToTime) END,
Name
FROM Items
GROUP BY
I, Name, MinNum
ORDER BY
FromTime
Lưu ý:Điều này yêu cầu SQL 2008 trở lên. Để làm cho nó hoạt động trong SQL 2005, hãy thay đổi mệnh đề VALUES thành SELECT 1 UNION ALL SELECT 2 .
Truy vấn được cập nhật
Sau khi suy nghĩ về điều này một chút, tôi nhận ra rằng tôi đang hoàn thành hai nhiệm vụ logic riêng biệt cùng một lúc và điều này làm cho truy vấn trở nên phức tạp một cách không cần thiết:1) loại bỏ các hàng trung gian không liên quan đến giải pháp cuối cùng (các hàng không bắt đầu một nhiệm vụ mới) và 2) kéo giá trị "Thời gian chờ" từ hàng tiếp theo. Bằng cách thực hiện # 1 trước # 2, truy vấn đơn giản hơn và thực hiện với khoảng một nửa CPU!
Vì vậy, đây là truy vấn được đơn giản hóa mà trước tiên, hãy cắt bỏ các hàng mà chúng tôi không quan tâm, sau đó nhận giá trị ToTime bằng cách sử dụng tổng hợp chứ không phải là JOIN. Đúng, nó có 3 chức năng tạo cửa sổ thay vì 2, nhưng cuối cùng do có ít hàng hơn (sau khi cắt bớt những hàng mà chúng tôi không quan tâm) nên nó có ít công việc hơn để thực hiện:
WITH Ranks AS (
SELECT
Grp =
Row_Number() OVER (ORDER BY Time)
- Row_Number() OVER (PARTITION BY Name ORDER BY Time),
[Time], Name
FROM #Data D
), Ranges AS (
SELECT
Result = Row_Number() OVER (ORDER BY Min(R.[Time]), X.Num) / 2,
[Time] = Min(R.[Time]),
R.Name, X.Num
FROM
Ranks R
CROSS JOIN (VALUES (1), (2)) X (Num)
GROUP BY
R.Name, R.Grp, X.Num
)
SELECT
FromTime = Min([Time]),
ToTime = CASE WHEN Count(*) = 1 THEN NULL ELSE Max([Time]) END,
Name = IsNull(Min(CASE WHEN Num = 2 THEN Name ELSE NULL END), Min(Name))
FROM Ranges R
WHERE Result > 0
GROUP BY Result
ORDER BY FromTime;
Truy vấn cập nhật này có tất cả các vấn đề giống như tôi đã trình bày trong phần giải thích của mình, tuy nhiên, chúng dễ giải quyết hơn vì tôi không xử lý thêm các hàng không cần thiết. Tôi cũng thấy rằng Row_Number() / 2 giá trị của 0 tôi đã phải loại trừ và tôi không chắc tại sao tôi không loại trừ nó khỏi truy vấn trước đó, nhưng trong mọi trường hợp, điều này hoạt động hoàn hảo và nhanh đáng kinh ngạc!
Áp dụng bên ngoài Tidies Mọi thứ
Cuối cùng, đây là một phiên bản về cơ bản giống với truy vấn của Simon Kingston mà tôi nghĩ là một cú pháp dễ hiểu hơn.
SELECT
FromTime = Min(D.Time),
X.ToTime,
D.Name
FROM
#Data D
OUTER APPLY (
SELECT TOP 1 ToTime = D2.[Time]
FROM #Data D2
WHERE
D.[Time] < D2.[Time]
AND D.[Name] <> D2.[Name]
ORDER BY D2.[Time]
) X
GROUP BY
X.ToTime,
D.Name
ORDER BY
FromTime;
Đây là tập lệnh thiết lập nếu bạn muốn so sánh hiệu suất trên tập dữ liệu lớn hơn:
CREATE TABLE #Data (
RecordId int,
[Time] int,
Name varchar(10)
);
INSERT #Data VALUES
(1, 10, 'Running'),
(2, 18, 'Running'),
(3, 21, 'Running'),
(4, 29, 'Walking'),
(5, 33, 'Walking'),
(6, 57, 'Running'),
(7, 66, 'Running'),
(8, 77, 'Running'),
(9, 81, 'Walking'),
(10, 89, 'Running'),
(11, 93, 'Walking'),
(12, 99, 'Running'),
(13, 107, 'Running'),
(14, 113, 'Walking'),
(15, 124, 'Walking'),
(16, 155, 'Walking'),
(17, 178, 'Running');
GO
insert #data select recordid + (select max(recordid) from #data), time + (select max(time) +25 from #data), name from #data
GO 10
Giải thích
Đây là ý tưởng cơ bản đằng sau truy vấn của tôi.
-
Thời gian đại diện cho một công tắc phải xuất hiện trong hai hàng liền kề, một để kết thúc hoạt động trước đó và một để bắt đầu hoạt động tiếp theo. Giải pháp tự nhiên cho điều này là một phép nối để một hàng đầu ra có thể kéo từ hàng của chính nó (cho thời gian bắt đầu) và thay đổi tiếp theo hàng (cho thời gian kết thúc).
-
Tuy nhiên, truy vấn của tôi đáp ứng yêu cầu làm cho thời gian kết thúc xuất hiện ở hai hàng khác nhau bằng cách lặp lại hàng hai lần, với
CROSS JOIN (VALUES (1), (2)). Bây giờ chúng tôi có tất cả các hàng của chúng tôi được sao chép. Ý tưởng là thay vì sử dụng JOIN để tính toán trên các cột, chúng tôi sẽ sử dụng một số hình thức tổng hợp để thu gọn từng cặp hàng mong muốn thành một. -
Nhiệm vụ tiếp theo là làm cho mỗi hàng trùng lặp được phân chia đúng cách để một thể hiện đi với cặp trước và một với cặp tiếp theo. Điều này được thực hiện với cột T, một
ROW_NUMBER()đặt hàng theoTime, và sau đó chia cho 2 (mặc dù tôi đã thay đổi nó thành DENSE_RANK () để đối xứng vì trong trường hợp này, nó trả về cùng một giá trị là ROW_NUMBER). Để có hiệu quả, tôi đã thực hiện phép chia trong bước tiếp theo để số hàng có thể được sử dụng lại trong một phép tính khác (tiếp tục đọc). Vì số hàng bắt đầu từ 1 và chia cho 2 hoàn toàn chuyển đổi thành int, điều này có tác dụng tạo ra chuỗi0 1 1 2 2 3 3 4 4 ...có kết quả mong muốn:bằng cách nhóm theo giá trị được tính toán này, vì chúng tôi cũng đã sắp xếp theoNumở số hàng, giờ đây chúng ta đã hoàn thành rằng tất cả các bộ sau bộ đầu tiên đều bao gồm Num =2 từ hàng "trước" và Num =1 từ hàng "tiếp theo". -
Nhiệm vụ khó khăn tiếp theo là tìm ra cách để loại bỏ các hàng mà chúng ta không quan tâm và bằng cách nào đó thu gọn thời gian bắt đầu của một khối thành cùng một hàng với thời gian kết thúc của một khối. Những gì chúng tôi muốn là một cách để mỗi tập hợp Chạy hoặc Đi bộ rời rạc được cung cấp một số riêng để chúng tôi có thể nhóm theo nó.
DENSE_RANK()là một giải pháp tự nhiên, nhưng một vấn đề là nó chú ý đến từng giá trị trongORDER BYmệnh đề - chúng tôi không có cú pháp để thực hiệnDENSE_RANK() OVER (PREORDER BY Time ORDER BY Name)sao choTimekhông gây raRANKtính toán để thay đổi ngoại trừ mỗi thay đổi trongName. Sau một số suy nghĩ, tôi nhận ra rằng mình có thể hiểu được một chút logic đằng sau giải pháp các hòn đảo được nhóm lại của Itzik Ben-Gan và tôi đã phát hiện ra rằng thứ hạng của các hàng được sắp xếp theoTime, được trừ khỏi thứ hạng của các hàng được phân vùng bằngNamevà đặt hàng theoTime, sẽ mang lại một giá trị giống nhau cho mỗi hàng trong cùng một nhóm nhưng khác với các nhóm khác. Kỹ thuật đảo nhóm được nhóm chung là tạo hai giá trị được tính toán mà cả hai đều tăng lên trong bước khóa với các hàng như4 5 6và1 2 3, giá trị đó khi bị trừ đi sẽ mang lại cùng một giá trị (trong trường hợp ví dụ này là3 3 3là kết quả của4 - 1,5 - 2và6 - 3). Lưu ý:Ban đầu tôi bắt đầu vớiROW_NUMBER()choNcủa tôi tính toán nhưng nó không hoạt động. Câu trả lời đúng làDENSE_RANK()mặc dù tôi rất tiếc phải nói rằng tôi không nhớ tại sao tôi lại kết luận điều này vào thời điểm đó, và tôi sẽ phải đi sâu vào tìm hiểu lại. Nhưng dù sao, đó là những gìT-Ntính toán:một số có thể được nhóm lại để tách biệt từng "đảo" của một trạng thái (Chạy hoặc Đi bộ). -
Nhưng đây không phải là kết thúc vì có một số nếp nhăn. Trước hết, hàng "tiếp theo" trong mỗi nhóm chứa các giá trị không chính xác cho
Name,NvàT. Chúng tôi giải quyết vấn đề này bằng cách chọn, từ mỗi nhóm, giá trị từNum = 2hàng khi nó tồn tại (nhưng nếu nó không tồn tại, thì chúng tôi sử dụng giá trị còn lại). Điều này tạo ra các biểu thức nhưCASE WHEN NUM = 2 THEN x END:điều này sẽ loại bỏ đúng cách các giá trị hàng "tiếp theo" không chính xác. -
Sau một số thử nghiệm, tôi nhận ra rằng không đủ để nhóm theo
T - Nbởi vì cả nhóm Đi bộ và nhóm Chạy đều có thể có cùng giá trị được tính toán (trong trường hợp dữ liệu mẫu của tôi được cung cấp lên đến 17, có haiT - Ngiá trị của 6). Nhưng chỉ cần nhóm theoNamecũng như giải quyết vấn đề này. Không có nhóm nào thuộc "Chạy" hoặc "Đi bộ" sẽ có cùng số lượng giá trị can thiệp từ loại đối diện. Nghĩa là, vì nhóm đầu tiên bắt đầu bằng "Đang chạy" và có hai hàng "Đi bộ" xen vào trước nhóm "Đang chạy" tiếp theo, khi đó giá trị của N sẽ nhỏ hơn 2 so với giá trị củaTtrong nhóm "Đang chạy" tiếp theo đó. Tôi chỉ nhận ra rằng một cách để nghĩ về điều này làT - Nphép tính đếm số hàng trước hàng hiện tại KHÔNG thuộc cùng một giá trị "Đang chạy" hoặc "Đi bộ". Một số suy nghĩ sẽ cho thấy điều này là đúng:nếu chúng ta chuyển sang nhóm "Đang chạy" thứ ba, đó chỉ là nhóm thứ ba do có một nhóm "Đi bộ" tách họ ra, vì vậy nó có một số hàng xen kẽ khác nhau. trước nó và do nó bắt đầu ở vị trí cao hơn, nó đủ cao để các giá trị không thể bị trùng lặp. -
Cuối cùng, vì nhóm cuối cùng của chúng tôi chỉ bao gồm một hàng (không có thời gian kết thúc và chúng tôi cần hiển thị
NULLthay vào đó) tôi đã phải thực hiện một phép tính có thể được sử dụng để xác định xem liệu chúng tôi có thời gian kết thúc hay không. Điều này được thực hiện vớiMin(Num)và sau đó cuối cùng phát hiện rằng khi Min (Num) là 2 (nghĩa là chúng ta không có hàng "tiếp theo") thì hiển thịNULLthay vìMax(ToTime)giá trị.
Tôi hy vọng lời giải thích này có ích cho mọi người. Tôi không biết liệu kỹ thuật "nhân hàng" của mình có hữu ích và áp dụng được cho hầu hết người viết truy vấn SQL trong môi trường sản xuất hay không vì khó hiểu nó và khó bảo trì, nó chắc chắn sẽ xuất hiện cho người tiếp theo truy cập mã (phản ứng có thể là "Nó đang làm cái quái gì vậy !?", sau đó là "Đã đến lúc viết lại!").
Nếu bạn đã làm được điều đó đến nay thì tôi cảm ơn bạn đã dành thời gian và dành thời gian cho tôi trong chuyến du ngoạn nhỏ đến vùng đất-giải-đố-vui-vẻ-cực-kỳ-thú-vị.
Tự mình xem
A.k.a. mô phỏng "PREORDER BY":
Một lưu ý cuối cùng. Để xem cách làm T - N thực hiện công việc - và lưu ý rằng việc sử dụng phần này của phương pháp của tôi có thể không áp dụng chung cho cộng đồng SQL - hãy chạy truy vấn sau đối với 17 hàng đầu tiên của dữ liệu mẫu:
WITH Ranks AS (
SELECT
T = Dense_Rank() OVER (ORDER BY Time),
N = Dense_Rank() OVER (PARTITION BY Name ORDER BY Time),
*
FROM
#Data D
)
SELECT
*,
T - N
FROM Ranks
ORDER BY
[Time];
Điều này dẫn đến:
RecordId Time Name T N T - N
----------- ---- ---------- ---- ---- -----
1 10 Running 1 1 0
2 18 Running 2 2 0
3 21 Running 3 3 0
4 29 Walking 4 1 3
5 33 Walking 5 2 3
6 57 Running 6 4 2
7 66 Running 7 5 2
8 77 Running 8 6 2
9 81 Walking 9 3 6
10 89 Running 10 7 3
11 93 Walking 11 4 7
12 99 Running 12 8 4
13 107 Running 13 9 4
14 113 Walking 14 5 9
15 124 Walking 15 6 9
16 155 Walking 16 7 9
17 178 Running 17 10 7
Phần quan trọng là mỗi nhóm "Đi bộ" hoặc "Chạy" có cùng giá trị cho T - N khác biệt với bất kỳ nhóm nào khác có cùng tên.
Hiệu suất
Tôi không muốn xác nhận quan điểm về việc truy vấn của tôi nhanh hơn của người khác. Tuy nhiên, với sự khác biệt ấn tượng như thế nào (khi không có chỉ mục), tôi muốn hiển thị các số ở định dạng bảng. Đây là một kỹ thuật tốt khi cần hiệu suất cao của loại tương quan hàng này với hàng khác.
Trước khi mỗi truy vấn chạy, tôi đã sử dụng DBCC FREEPROCCACHE; DBCC DROPCLEANBUFFERS; . Tôi đặt MAXDOP thành 1 cho mỗi truy vấn để loại bỏ tác động thu hẹp thời gian của tính song song. Tôi đã chọn từng tập hợp kết quả thành các biến thay vì trả lại chúng cho máy khách để chỉ đo lường hiệu suất chứ không phải việc truyền dữ liệu máy khách. Tất cả các truy vấn được đưa ra cùng một mệnh đề ORDER BY. Tất cả các thử nghiệm đã sử dụng 17.408 hàng đầu vào cho ra 8.193 hàng kết quả.
Không có kết quả nào được hiển thị vì những người / lý do sau:
RichardTheKiwi *Could not test--query needs updating*
ypercube *No SQL 2012 environment yet :)*
Tim S *Did not complete tests within 5 minutes*
Không có chỉ mục:
CPU Duration Reads Writes
----------- ----------- ----------- -----------
ErikE 344 344 99 0
Simon Kingston 68672 69582 549203 49
Với chỉ mục CREATE UNIQUE CLUSTERED INDEX CI_#Data ON #Data (Time); :
CPU Duration Reads Writes
----------- ----------- ----------- -----------
ErikE 328 336 99 0
Simon Kingston 70391 71291 549203 49 * basically not worse
Với chỉ mục CREATE UNIQUE CLUSTERED INDEX CI_#Data ON #Data (Time, Name); :
CPU Duration Reads Writes
----------- ----------- ----------- -----------
ErikE 375 414 359 0 * IO WINNER
Simon Kingston 172 189 38273 0 * CPU WINNER
Vì vậy, luân lý của câu chuyện là:
Chỉ mục thích hợp quan trọng hơn thuật sĩ truy vấn
Với chỉ số thích hợp, phiên bản của Simon Kingston tổng thể chiến thắng, đặc biệt là khi bao gồm độ phức tạp / khả năng bảo trì của truy vấn.
Chú ý bài học này tốt! 38k lượt đọc không thực sự nhiều và phiên bản của Simon Kingston chạy bằng một nửa thời gian của tôi. Việc tăng tốc độ truy vấn của tôi hoàn toàn là do không có chỉ mục nào trên bảng và chi phí cực kỳ nghiêm trọng mà điều này gây ra cho bất kỳ truy vấn nào cần tham gia (điều của tôi thì không):quét toàn bộ bảng Hash Match giết chết hiệu suất của nó. Với một chỉ mục, truy vấn của anh ấy có thể thực hiện Vòng lặp lồng nhau với tìm kiếm chỉ mục được phân nhóm (còn gọi là tra cứu dấu trang), điều này khiến mọi thứ thực sự nhanh chóng.
Điều thú vị là một chỉ số nhóm về Thời gian thôi là không đủ. Mặc dù Thời gian là duy nhất, nghĩa là chỉ có một Tên xuất hiện mỗi lần, nhưng vẫn cần Tên là một phần của chỉ mục để sử dụng nó đúng cách.
Việc thêm chỉ mục theo nhóm vào bảng khi đầy dữ liệu mất chưa đến 1 giây! Đừng bỏ qua các chỉ mục của bạn.
