是否可以为不同/分组获得基于搜索的并行计划？

Question

这个问题的一个例子表明，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

计划看起来不错。由于如此之快，没有并行性但毫无意义。某个时候将不得不在更大的问题上尝试这个。谢谢。

Answer 1

我有完全相同的设置，并且我已经经历了重写查询的相同阶段。

在我的例子中，表名和含义有点不同，但整体结构是相同的。你的表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和扫描成搜索不够聪明。减缓。我最初没有想到这个变体，我的下一次尝试是标量 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] > 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;
• 组数远小于表中的行数；
• 有合适的索引；

两种最好的方法是：

1. 如果我们有一个包含组列表的小表，最好的方法是CROSS APPLY使用TOP。

2. 如果我们只有大表，最好的方法是Recursive Index Skip Scan.