强迫流不同

Question

我有一张这样的表：

CREATE TABLE Updates
(
    UpdateId INT NOT NULL IDENTITY(1,1) PRIMARY KEY,
    ObjectId INT NOT NULL
)

本质上是跟踪 ID 增加的对象的更新。

该表的使用者将选择一个由 100 个不同对象 ID 组成的块，按UpdateId特定的UpdateId. 本质上，跟踪它停止的位置，然后查询任何更新。

我发现这是一个有趣的优化问题，因为我只能通过编写由于索引而碰巧做我想要的查询来生成最大优化的查询计划，但不保证我想要什么：

SELECT DISTINCT TOP 100 ObjectId
FROM Updates
WHERE UpdateId > @fromUpdateId

@fromUpdateId存储过程参数在哪里。

有以下计划：

SELECT <- TOP <- Hash match (flow distinct, 100 rows touched) <- Index seek

由于UpdateId正在使用索引上的搜索，结果已经很好，并且按照我想要的从最低到最高的更新 ID 排序。这会生成一个流程不同的计划，这就是我想要的。但是排序显然不能保证行为，所以我不想使用它。

这个技巧也会产生相同的查询计划（尽管有一个冗余的 TOP）：

WITH ids AS
(
    SELECT ObjectId
    FROM Updates
    WHERE UpdateId > @fromUpdateId
    ORDER BY UpdateId OFFSET 0 ROWS
)
SELECT DISTINCT TOP 100 ObjectId FROM ids

不过，我不确定（也不怀疑）这是否真的能保证订购。

我希望 SQL Server 足够智能以简化的一个查询是这样的，但它最终生成了一个非常糟糕的查询计划：

SELECT TOP 100 ObjectId
FROM Updates
WHERE UpdateId > @fromUpdateId
GROUP BY ObjectId
ORDER BY MIN(UpdateId)

有以下计划：

SELECT <- Top N Sort <- Hash Match aggregate (50,000+ rows touched) <- Index Seek

我正在尝试找到一种方法来生成具有索引查找UpdateId和不同流以删除重复ObjectIds的最佳计划。有任何想法吗？

如果需要，请提供示例数据。对象很少有多个更新，并且在一组 100 行中几乎不应该有多个更新，这就是为什么我要使用不同的流，除非有我不知道的更好的东西？但是，不能保证单个ObjectId表中的行数不会超过 100。该表有超过 1,000,000 行，预计会快速增长。

假设用户 this 有另一种方式找到合适的 next @fromUpdateId。无需在此查询中返回它。

Answer 1

SQL Server 优化器无法生成您所追求的执行计划并保证您需要，因为Hash Match Flow Distinct运算符不是顺序保留的。

不过，我不确定（也不怀疑）这是否真的能保证订购。

在许多情况下，您可能会观察到顺序保留，但这是一个实现细节；没有保证，所以你不能依赖它。与往常一样，呈现顺序只能由顶级ORDER BY子句来保证。

例子

下面的脚本显示 Hash Match Flow Distinct 不保留顺序。它设置了有问题的表格，两列中的匹配数字为 1-50,000：

IF OBJECT_ID(N'dbo.Updates', N'U') IS NOT NULL
    DROP TABLE dbo.Updates;
GO
CREATE TABLE Updates
(
    UpdateId INT NOT NULL IDENTITY(1,1),
    ObjectId INT NOT NULL,

    CONSTRAINT PK_Updates_UpdateId PRIMARY KEY (UpdateId)
);
GO
INSERT dbo.Updates (ObjectId)
SELECT TOP (50000)
    ObjectId =
        ROW_NUMBER() OVER (
            ORDER BY C1.[object_id]) 
FROM sys.columns AS C1
CROSS JOIN sys.columns AS C2
ORDER BY
    ObjectId;

测试查询是：

DECLARE @Rows bigint = 50000;

-- Optimized for 1 row, but will be 50,000 when executed
SELECT DISTINCT TOP (@Rows)
    U.ObjectId 
FROM dbo.Updates AS U
WHERE 
    U.UpdateId > 0
OPTION (OPTIMIZE FOR (@Rows = 1));

估计的计划显示了一个不同的索引查找和流程：

输出似乎是按顺序开始的：

...但进一步下降的价值开始“缺失”：

...最终：

在这种特殊情况下的解释是散列运算符溢出：

一旦一个分区溢出，所有散列到同一分区的行也会溢出。溢出的分区稍后处理，打破了遇到的不同值将按照接收到的顺序立即发出的期望。

有很多方法可以编写高效的查询来生成您想要的有序结果，例如递归或使用游标。但是，它不能使用Hash Match Flow Distinct来完成。

Answer 2

我对这个答案不满意，因为我无法获得一个流程不同的运算符以及保证正确的结果。但是，我有一个替代方案，它应该能够获得良好的性能和正确的结果。不幸的是，它需要在表上创建一个非聚集索引。

我通过尝试考虑我可以使用的列组合ORDER BY并在应用DISTINCT它们后获得正确结果来解决这个问题。UpdateIdper ObjectIdwith的最小值ObjectId就是一个这样的组合。但是，直接要求最小值UpdateId似乎会导致从表中读取所有行。相反，我们可以间接地要求UpdateId与另一个表连接的最小值。这个想法是Updates按顺序扫描表，丢弃UpdateId不是该行的最小值的任何行ObjectId，并保留前 100 行。根据您对数据分布的描述，我们不需要丢弃很多行。

对于数据准备，我将 100 万行放入一个表中，每个不同的 ObjectId 有 2 行：

INSERT INTO Updates WITH (TABLOCK)
SELECT t.RN / 2
FROM 
(
    SELECT TOP 1000000 -1 + ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) RN
    FROM master..spt_values t1
    CROSS JOIN master..spt_values t2
) t;

CREATE INDEX IX On Updates (Objectid, UpdateId);

在非聚集索引Objectid和UpdateId是很重要的。它允许我们有效地丢弃没有最小UpdateIdper 的行Objectid。有很多方法可以编写与上述描述相匹配的查询。这是使用的一种方式NOT EXISTS：

DECLARE @fromUpdateId INT = 9999;
SELECT ObjectId
FROM (
    SELECT DISTINCT TOP 100 u1.UpdateId, u1.ObjectId
    FROM Updates u1
    WHERE UpdateId > @fromUpdateId
    AND NOT EXISTS (
        SELECT 1
        FROM Updates u2
        WHERE u2.UpdateId > @fromUpdateId
        AND u1.ObjectId = u2.ObjectId
        AND u2.UpdateId < u1.UpdateId
    )
    ORDER BY u1.UpdateId, u1.ObjectId
) t;

这是查询计划的图片：

在最好的情况下，SQL Server 只会对非聚集索引执行 100 次索引查找。为了模拟变得非常不幸，我更改了查询以将前 5000 行返回给客户端。这导致了 9999 次索引搜索，因此就像每个不同的 平均获得 100 行ObjectId。这是来自的输出SET STATISTICS IO, TIME ON：

表“更新”。扫描计数 10000，逻辑读取 31900，物理读取 0

SQL Server 执行时间：CPU 时间 = 31 毫秒，已用时间 = 42 毫秒。

Answer 3

我喜欢这个问题 - Flow Distinct 是我最喜欢的运算符之一。

现在，保证是问题。当您考虑 FD 运算符以有序的方式从 Seek 运算符中提取行时，生成每一行，因为它确定它是唯一的，这将为您提供正确顺序的行。但是很难知道是否可能存在某些 FD 一次不处理一行的情况。

理论上，FD 可以从 Seek 请求 100 行，并按照它需要的任何顺序生成它们。

查询提示OPTION (FAST 1, MAXDOP 1)可能会有所帮助，因为它会避免从 Seek 操作符获得比它需要的更多的行。不过有保证吗？不完全的。它仍然可以决定一次拉一页行，或者类似的东西。

我认为OPTION (FAST 1, MAXDOP 1)，您的OFFSET版本会让您对订单充满信心，但这并不能保证。