是否有可能為 distinct/group by 獲得基於搜尋的並行計劃？

September 7, 2015

這個問題的一個例子表明，SQL Server 將選擇一個完整的索引掃描來解決這樣的查詢：
select distinct [typeName] from [types]
在哪裡
$$ typeName $$有一個非聚集的、非唯一的升序索引。他的範例有 200M 行，但只有 76 個唯一值。在這種密度下（約 76 次二分搜尋），搜尋計劃似乎是一個更好的選擇？他的情況可以正常化，但問題的原因是我真的想解決這樣的問題：
select TransactionId, max(CreatedUtc) 
from TxLog 
group by TransactionId
上有一個索引(TransactionId, MaxCreatedUtc)。
使用標準化源 (dt) 重寫不會改變計劃。
select dt.TransactionId, MaxCreatedUtc
from [Transaction] dt -- distinct transactions
cross apply
  (
       select Max(CreatedUtc) as MaxCreatedUtc 
         from TxLog tl
        where tl.TransactionId = dt.TransactionId         
  ) ca
僅將 CA 子查詢作為標量 UDF 執行確實顯示了 1 次搜尋的計劃。
select max(CreatedUtc) as MaxCreatedUtc
from Pub.TransactionLog 
where TransactionID = @TxId;
在原始查詢中使用該標量 UDF 似乎可行，但會失去並行性（UDF 的已知問題）：
select t.typeName, 
      Pub.ufn_TransactionMaxCreatedUtc(t.TransactionId) as MaxCreatedUtc
 from Pub.[Transaction] t
使用內聯 TVF 重寫會將其恢復為基於掃描的計劃。
來自答案/評論@ypercube：
select TransactionId, MaxCreatedUtc        
from Pub.[Transaction]  t
 cross apply
  (
       select top (1) CreatedUtc as MaxCreatedUtc 
       from Pub.TransactionLog l
       where l.TransactionID = t.TransactionId
       order by CreatedUtc desc                     
  ) ca
計劃看起來不錯。沒有並行性但沒有意義，因為這麼快。有時將不得不嘗試解決更大的問題。謝謝。

我的設置完全相同，並且我經歷了重寫查詢的相同階段。
在我的情況下，表名和含義有點不同，但整體結構是相同的。你的表Transactions對應我下面的表PortalElevators。它有大約 2000 行。你的表TxLog對應我的表PlaybackStats。它有大約 1.5 億行。它有索引(ElevatorID, DataSourceRowID)，和你一樣。
我將對真實數據執行幾種查詢變體，並比較執行計劃、IO 和時間統計資訊。我正在使用 SQL Server 2008 標準版。
用 MAX 分組
SELECT [ElevatorID], MAX([DataSourceRowID]) AS LastItemID
FROM [dbo].[PlaybackStats]
GROUP BY [ElevatorID]
與您的優化器一樣掃描索引並聚合結果。慢。
單行
讓我們看看如果我MAX隻請求一行優化器會做什麼：
SELECT MAX([dbo].[PlaybackStats].[DataSourceRowID]) AS LastItemID
FROM [dbo].[PlaybackStats]
WHERE [dbo].[PlaybackStats].ElevatorID = 1
優化器足夠聰明，可以使用索引並且它會進行一次搜尋。順便說一句，我們可以看到優化器使用TOP運算符，即使查詢沒有它。這是一個明顯的跡象，表明引擎的優化路徑MAX和TOP引擎中有一些共同點，但它們是不同的，我們將在下面看到。
與 MAX 交叉應用
SELECT
   [dbo].[PortalElevators].elevatorsId
   ,LastItemID
FROM
   [dbo].[PortalElevators]
   CROSS APPLY
   (
       SELECT MAX([dbo].[PlaybackStats].[DataSourceRowID]) AS LastItemID
       FROM [dbo].[PlaybackStats]
       WHERE [dbo].[PlaybackStats].ElevatorID = [dbo].[PortalElevators].elevatorsId
   ) AS CA
;
優化器仍然掃描索引。MAX在這裡轉換成TOP並掃描成 seek是不夠聰明的。慢。我最初沒有想到這個變體，我的下一個嘗試是標量 UDF。
標量 UDF
我看到獲取MAX單個行的計劃有索引搜尋，所以我把這個簡單的查詢放在一個標量 UDF 中。
CREATE FUNCTION [dbo].[GetElevatorLastID]
(
   @ParamElevatorID int
)
RETURNS bigint
AS
BEGIN
   DECLARE @Result bigint;
   SELECT @Result = MAX([dbo].[PlaybackStats].[DataSourceRowID])
   FROM [dbo].[PlaybackStats]
   WHERE [dbo].[PlaybackStats].ElevatorID = @ParamElevatorID;
   RETURN @Result;
END

SELECT
   [dbo].[PortalElevators].elevatorsId
   ,[dbo].[GetElevatorLastID]([dbo].[PortalElevators].elevatorsId) AS LastItemID
FROM
   [dbo].[PortalElevators]
;
它執行得很快。至少，比Group by. 不幸的是，執行計劃沒有顯示 UDF 的詳細資訊，更糟糕的是，它沒有顯示真實的 IO 統計資訊（它不包括 UDF 生成的 IO）。您需要執行 Profiler 來查看函式的所有呼叫及其統計資訊。該計劃僅顯示 6 個讀數。單個行的計劃有 4 次讀取，因此實數將接近：6 + 2779 * 4 = 6 + 11,116 = 11,122.
與 TOP 交叉申請
最終，我發現了CROSS APPLY它以及如何應用它;-) 在這種情況下。
SELECT
   [dbo].[PortalElevators].elevatorsId
   ,LastItemID
FROM
   [dbo].[PortalElevators]
   CROSS APPLY
   (
       SELECT TOP(1) [dbo].[PlaybackStats].[DataSourceRowID] AS LastItemID
       FROM [dbo].[PlaybackStats]
       WHERE [dbo].[PlaybackStats].ElevatorID = [dbo].[PortalElevators].elevatorsId
       ORDER BY [dbo].[PlaybackStats].[DataSourceRowID] DESC
   ) AS CA
;
這裡優化器足夠聰明，可以進行約 2000 次搜尋。您可以看到讀取次數遠低於 for group by。快速地。
有趣的是，這裡的讀取次數 (11,850) 比我使用 UDF 估計的讀取次數 (11,122) 多一點。表 IO 統計數據CROSS APPLY具有 11,844 次讀取和 2,779 次大表掃描計數，這給出了11,844 / 2,779 ~= 4.26每次索引查找的讀取次數。最有可能的是，尋找某些值使用 4 次讀取，而某些 5 次，平均為 4.26。有 2,779 次搜尋，但只有 2,130 行的值。正如我所說，如果沒有分析器，使用 UDF 很難獲得真正的讀取次數。
遞歸 CTE
正如評論中所指出的，Paul White 描述了一種遞歸索引跳過掃描方法，可以在不執行完整索引掃描的情況下在大表中查找不同的值，而是遞歸地進行索引搜尋。要開始遞歸，我們需要找到錨點的MINorMAX值，然後遞歸的每一步都會一個接一個地添加下一個值。該文章詳細解釋了它。
WITH RecursiveCTE
AS
(
   -- Anchor
   SELECT TOP (1) [ElevatorID], [DataSourceRowID]
   FROM [dbo].[PlaybackStats]
   ORDER BY [ElevatorID] DESC, [DataSourceRowID] DESC

   UNION ALL

   -- Recursive
   SELECT R.[ElevatorID], R.[DataSourceRowID]
   FROM
   (
       -- Number the rows
       SELECT
           T.[ElevatorID], T.[DataSourceRowID]
           ,ROW_NUMBER() OVER (ORDER BY T.[ElevatorID] DESC, T.[DataSourceRowID] DESC) AS rn
       FROM
           [dbo].[PlaybackStats] AS T
           INNER JOIN RecursiveCTE AS R ON R.[ElevatorID] &gt; T.[ElevatorID]
   ) AS R
   WHERE
       -- Only the row that sorts lowest
       R.rn = 1
)
SELECT [ElevatorID], [DataSourceRowID]
FROM RecursiveCTE
OPTION (MAXRECURSION 0);
它非常快，儘管它執行的讀取量幾乎是CROSS APPLY. 它讀取 12,781 次，讀取Worktable8,524 次PlaybackStats。另一方面，它執行與大表中不同值一樣多的查找。CROSS APPLYwithTOP執行與小表中的行一樣多的搜尋。在我的例子中，小表有 2,779 行，但大表只有 2,130 個不同的值。
概括
                        Logical Reads       Duration
CROSS APPLY with MAX           482,121          6,604
GROUP BY with MAX              482,123          6,581
Scalar UDF                    ~ 11,122            728
Recursive                       21,305             30
CROSS APPLY with TOP            11,850              9 (nine!)
我將每個查詢執行了 3 次並選擇了最佳時間。沒有物理讀取。
結論
在這個特殊的greatest-n-per-group問題案例中，我們有：
n=1;
組數遠小於表中的行數；
有適當的索引；
兩種最好的方法是：
如果我們有一個包含組列表的小表，最好的方法是CROSS APPLY使用TOP.
如果我們只有大表，最好的方法是Recursive Index Skip Scan.