为什么我的 SELECT DISTINCT TOP N 查询会扫描整个表？

Question

我遇到了一些SELECT DISTINCT TOP N查询，这些查询似乎被 SQL Server 查询优化器优化得很差。让我们从一个简单的例子开始：具有两个交替值的百万行表。我将使用GetNums函数来生成数据：

DROP TABLE IF EXISTS X_2_DISTINCT_VALUES;

CREATE TABLE X_2_DISTINCT_VALUES (PK INT IDENTITY (1, 1), VAL INT NOT NULL);

INSERT INTO X_2_DISTINCT_VALUES WITH (TABLOCK) (VAL)
SELECT N % 2
FROM dbo.GetNums(1000000);

UPDATE STATISTICS X_2_DISTINCT_VALUES WITH FULLSCAN;

对于以下查询：

SELECT DISTINCT TOP 2 VAL
FROM X_2_DISTINCT_VALUES
OPTION (MAXDOP 1);

SQL Server 可以通过扫描表的第一个数据页找到两个不同的值，但它会扫描所有数据。为什么 SQL Server 不进行扫描，直到找到所需数量的不同值？

对于这个问题，请使用以下测试数据，其中包含 1000 万行，并在块中生成 10 个不同的值：

DROP TABLE IF EXISTS X_10_DISTINCT_HEAP;

CREATE TABLE X_10_DISTINCT_HEAP (VAL VARCHAR(10) NOT NULL);

INSERT INTO X_10_DISTINCT_HEAP WITH (TABLOCK)
SELECT REPLICATE(CHAR(65 + (N / 100000 ) % 10 ), 10)
FROM dbo.GetNums(10000000);

UPDATE STATISTICS X_10_DISTINCT_HEAP WITH FULLSCAN;

带有聚集索引的表的答案也是可以接受的：

DROP TABLE IF EXISTS X_10_DISTINCT_CI;

CREATE TABLE X_10_DISTINCT_CI (PK INT IDENTITY (1, 1), VAL VARCHAR(10) NOT NULL, PRIMARY KEY (PK));

INSERT INTO X_10_DISTINCT_CI WITH (TABLOCK) (VAL)
SELECT REPLICATE(CHAR(65 + (N / 100000 ) % 10 ), 10)
FROM dbo.GetNums(10000000);

UPDATE STATISTICS X_10_DISTINCT_CI WITH FULLSCAN;

以下查询扫描表中的所有 1000 万行。我怎样才能得到不扫描整个表格的东西？我正在使用 SQL Server 2016 SP1。

SELECT DISTINCT TOP 10 VAL
FROM X_10_DISTINCT_HEAP
OPTION (MAXDOP 1);

Answer 1

看起来有三种不同的优化器规则可以执行DISTINCT上述查询中的操作。以下查询抛出一个错误，表明该列表是详尽无遗的：

SELECT DISTINCT TOP 10 ID
FROM X_10_DISTINCT_HEAP
OPTION (MAXDOP 1, QUERYRULEOFF GbAggToSort, QUERYRULEOFF GbAggToHS, QUERYRULEOFF GbAggToStrm);

消息 8622，级别 16，状态 1，第 1 行

由于此查询中定义的提示，查询处理器无法生成查询计划。在不指定任何提示且不使用 SET FORCEPLAN 的情况下重新提交查询。

GbAggToSort将 group-by 聚合 (distinct) 实现为不同的排序。这是一个阻塞运算符，它将在生成任何行之前从输入中读取所有数据。GbAggToStrm将 group-by 聚合实现为流聚合（在这种情况下也需要输入排序）。这也是一个阻塞运算符。GbAggToHS实现为散列匹配，这是我们在问题的错误计划中看到的，但它可以实现为散列匹配（聚合）或散列匹配（流不同）。

哈希匹配（流不同）运算符是解决此问题的一种方法，因为它不会阻塞。SQL Server 应该能够在找到足够多的不同值后停止扫描。

Flow Distinct 逻辑运算符扫描输入，删除重复项。Distinct 运算符在产生任何输出之前消耗所有输入，而 Flow Distinct 运算符返回从输入中获得的每一行（除非该行是重复的，在这种情况下它被丢弃）。

为什么问题中的查询使用哈希匹配（聚合）而不是哈希匹配（流不同）？随着表中不同值的数量发生变化，我预计哈希匹配（流不同）查询的成本会降低，因为它需要扫描到表的行数的估计应该会减少。我预计哈希匹配（聚合）计划的成本会增加，因为它需要构建的哈希表会变得更大。对此进行调查的一种方法是创建计划指南。如果我创建了数据的两个副本，但对其中一个应用了计划指南，我应该能够将哈希匹配（聚合）与哈希匹配（不同）与相同的数据并排比较。请注意，我无法通过禁用查询优化器规则来做到这一点，因为相同的规则适用于两个计划 ( GbAggToHS)。

这是获取我所追求的计划指南的一种方法：

DROP TABLE IF EXISTS X_PLAN_GUIDE_TARGET;

CREATE TABLE X_PLAN_GUIDE_TARGET (VAL VARCHAR(10) NOT NULL);

INSERT INTO X_PLAN_GUIDE_TARGET WITH (TABLOCK)
SELECT CAST(N % 10000 AS VARCHAR(10))
FROM dbo.GetNums(10000000);

UPDATE STATISTICS X_PLAN_GUIDE_TARGET WITH FULLSCAN;

-- run this query
SELECT DISTINCT TOP 10 VAL  FROM X_PLAN_GUIDE_TARGET  OPTION (MAXDOP 1)

获取计划句柄并使用它来创建计划指南：

-- plan handle is 0x060007009014BC025097E88F6C01000001000000000000000000000000000000000000000000000000000000
SELECT qs.plan_handle, st.text FROM 
sys.dm_exec_query_stats AS qs   
CROSS APPLY sys.dm_exec_sql_text(qs.sql_handle) AS st  
WHERE st.text LIKE '%X[_]PLAN[_]GUIDE[_]TARGET%'
ORDER BY last_execution_time DESC;

EXEC sp_create_plan_guide_from_handle 
'EVIL_PLAN_GUIDE', 
0x060007009014BC025097E88F6C01000001000000000000000000000000000000000000000000000000000000;

计划指南仅适用于确切的查询文本，因此让我们从计划指南中复制它：

SELECT query_text
FROM sys.plan_guides
WHERE name = 'EVIL_PLAN_GUIDE';

重置数据：

TRUNCATE TABLE X_PLAN_GUIDE_TARGET;

INSERT INTO X_PLAN_GUIDE_TARGET WITH (TABLOCK)
SELECT REPLICATE(CHAR(65 + (N / 100000 ) % 10 ), 10)
FROM dbo.GetNums(10000000);

获取应用了计划指南的查询的查询计划：

SELECT DISTINCT TOP 10 VAL  FROM X_PLAN_GUIDE_TARGET  OPTION (MAXDOP 1)

这具有我们想要的测试数据的哈希匹配（流不同）运算符。请注意，SQL Server 期望从表中读取所有行，并且估计成本与具有哈希匹配（聚合）的计划完全相同。我所做的测试表明，当计划的行目标大于或等于 SQL Server 期望从表中获得的不同值的数量时，这两个计划的成本是相同的，在这种情况下，可以简单地从统计数据。不幸的是（对于我们的查询）优化器在成本相同时选择散列匹配（聚合）而不是散列匹配（流不同）。所以我们离我们想要的计划还有 0.0000001 个魔法优化器单位。

解决此问题的一种方法是减少行目标。如果从优化器的角度来看行目标小于不同的行数，我们可能会得到哈希匹配（流不同）。这可以通过OPTIMIZE FOR查询提示来完成：

DECLARE @j INT = 10;

SELECT DISTINCT TOP (@j) VAL
FROM X_10_DISTINCT_HEAP
OPTION (MAXDOP 1, OPTIMIZE FOR (@j = 1));

对于这个查询，优化器创建一个计划，就好像查询只需要第一行，但是当执行查询时，它会返回前 10 行。在我的机器上，此查询扫描 892800 行X_10_DISTINCT_HEAP并在 299 毫秒内完成，CPU 时间为 250 毫秒，逻辑读取为 2537。

请注意，如果统计数据仅报告一个不同的值，则此技术将不起作用，这可能发生在针对偏斜数据的抽样统计数据中。但是，在这种情况下，您的数据不太可能密集到足以证明使用此类技术的合理性。通过扫描表中的所有数据，您可能不会损失太多，特别是如果可以并行完成。

解决此问题的另一种方法是夸大 SQL Server 期望从基表中获得的不同估计值的数量。这比预期的要难。应用确定性函数不可能增加结果的不同计数。如果查询优化器知道这个数学事实（一些测试表明它至少是为了我们的目的），那么应用确定性函数（包括所有字符串函数）将不会增加不同行的估计数量。

许多不确定的功能没有任何工作，包括明显的选择NEWID()和RAND()。但是，LAG()此查询的技巧。查询优化器期望针对LAG表达式有1000 万个不同的值，这将鼓励哈希匹配（流不同）计划：

SELECT DISTINCT TOP 10 LAG(VAL, 0) OVER (ORDER BY (SELECT NULL)) AS ID
FROM X_10_DISTINCT_HEAP
OPTION (MAXDOP 1);

在我的机器上，此查询扫描 892800 行X_10_DISTINCT_HEAP并在 1165 毫秒内完成，CPU 时间为 1109 毫秒，逻辑读取为 2537，因此LAG()增加了相当多的相对开销。@Paul White 建议尝试对此查询进行批处理模式处理。在 SQL Server 2016 上，即使使用MAXDOP 1. 获得行存储表的批处理模式处理的一种方法是连接到一个空的 CCI，如下所示：

CREATE TABLE #X_DUMMY_CCI (ID INT NOT NULL);

CREATE CLUSTERED COLUMNSTORE INDEX X_DUMMY_CCI ON #X_DUMMY_CCI;

SELECT DISTINCT TOP 10 VAL
FROM
(
    SELECT LAG(VAL, 1) OVER (ORDER BY (SELECT NULL)) AS VAL
    FROM X_10_DISTINCT_HEAP
    LEFT OUTER JOIN #X_DUMMY_CCI ON 1 = 0
) t
WHERE t.VAL IS NOT NULL
OPTION (MAXDOP 1);

该代码生成此查询计划。

Paul 指出我必须更改要使用的查询，LAG(..., 1)因为LAG(..., 0)它似乎不符合 Window Aggregate 优化的条件。此更改将经过时间减少到 520 毫秒，将 CPU 时间减少到 454 毫秒。

请注意，该LAG()方法不是最稳定的方法。如果 Microsoft 更改针对该函数的唯一性假设，则它可能不再起作用。它与旧版 CE 有不同的估计。此外，这种针对堆的优化也不是一个好主意。如果重建表，则可能会出现最坏的情况，即几乎所有行都需要从表中读取。

对于具有唯一列的表（例如问题中的聚集索引示例），我们有更好的选择。例如，我们可以通过使用SUBSTRING始终返回空字符串的表达式来欺骗优化器。SQL Server 不认为这SUBSTRING会改变不同值的数量，因此如果我们将其应用于唯一列，例如 PK，那么估计的不同行数为 1000 万。以下查询获取哈希匹配（流不同）运算符：

SELECT DISTINCT TOP 10 VAL + SUBSTRING(CAST(PK AS VARCHAR(10)), 11, 1)
FROM X_10_DISTINCT_CI
OPTION (MAXDOP 1);

在我的机器上，此查询扫描 900000 行X_10_DISTINCT_CI并在 333 毫秒内完成，CPU 时间为 297 毫秒，逻辑读取为 3011。

总之，查询优化器似乎假定SELECT DISTINCT TOP N当N>=表中估计的不同行数时，将从表中读取所有行以进行查询。哈希匹配（聚合）运算符可能与哈希匹配（流不同）运算符具有相同的成本，但优化器始终选择聚合运算符。当足够的不同值位于表扫描开始附近时，这会导致不必要的逻辑读取。诱使优化器使用哈希匹配（流不同）运算符的两种方法是使用OPTIMIZE FOR提示降低行目标或使用LAG()或SUBSTRING在唯一列上增加估计的不同行数。

Answer 2

您已经正确回答了自己的问题。

我只想补充一点，最有效的方法实际上是扫描整个表 - 如果它可以组织为列存储“堆”：

CREATE CLUSTERED COLUMNSTORE INDEX CCSI 
ON dbo.X_10_DISTINCT_HEAP;

简单查询：

SELECT DISTINCT TOP (10)
    XDH.VAL 
FROM dbo.X_10_DISTINCT_HEAP AS XDH
OPTION (MAXDOP 1);

然后给出：

表'X_10_DISTINCT_HEAP'。扫描次数 1,
 逻辑读 0，物理读 0，预读 0， 
 lob 逻辑读取 66，lob 物理读取 0，lob 预读读取 0。
表'X_10_DISTINCT_HEAP'。段读取 13，段跳过 0。

 SQL Server 执行时间：
   CPU 时间 = 0 毫秒，经过时间 = 11 毫秒。

Hash Match (Flow Distinct) 当前无法在批处理模式下执行。由于从批处理到行处理的（不可见的）昂贵的转换，使用它的方法要慢得多。例如：

SET ROWCOUNT 10;

SELECT DISTINCT 
    XDH.VAL
FROM dbo.X_10_DISTINCT_HEAP AS XDH
OPTION (FAST 1);

SET ROWCOUNT 0;

给出：

表'X_10_DISTINCT_HEAP'。扫描次数 1,
 逻辑读 0，物理读 0，预读 0， 
 lob 逻辑读取 20，lob 物理读取 0，lob 预读读取 0。
表'X_10_DISTINCT_HEAP'。段读取 4，段跳过 0。

 SQL Server 执行时间：
   CPU 时间 = 640 毫秒，经过时间 = 680 毫秒。

这比将表组织为行存储堆时要慢。

Answer 3

这里尝试使用递归 CTE 模拟重复的部分扫描（类似于但与跳过扫描不同）。目的 - 因为我们没有索引(id)- 是避免对表进行排序和多次扫描。

它有一些技巧可以绕过一些递归 CTE 限制：

• 没有TOP允许递归部分。我们使用子查询，ROW_NUMBER()而不是。
• 我们不能对常量部分有多个引用，LEFT JOIN也不NOT IN (SELECT id FROM cte)能从递归部分使用或使用。为了绕过，我们构建了一个VARCHAR累积所有id值的字符串，类似于STRING_AGG或 到hierarchyID，然后与 进行比较LIKE。

对于rextester.com 上的堆（假设列名为id）test-1。

这 - 如测试所示 - 不会避免多次扫描，但在前几页中找到不同的值时执行正常。然而，如果这些值分布不均，它可能会对表的大部分进行多次扫描——这当然会导致性能不佳。

WITH ct (id, found, list) AS
  ( SELECT TOP (1) id, 1, CAST('/' + id + '/' AS VARCHAR(MAX))
    FROM x_large_table_2
  UNION ALL
    SELECT y.ID, ct.found + 1, CAST(ct.list + y.id + '/' AS VARCHAR(MAX))
    FROM ct
      CROSS APPLY 
      ( SELECT x.id, 
               rn = ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
        FROM x_large_table_2 AS x
        WHERE ct.list NOT LIKE '%/' + id + '/%'
      ) AS y
    WHERE ct.found < 3         -- the TOP (n) parameter here
      AND y.rn = 1
  )
SELECT id FROM ct ;

当表被聚类时（CI on unique_key），在 reextester.com 上进行 test-2。

这使用聚集索引 ( WHERE x.unique_key > ct.unique_key) 来避免多次扫描：

WITH ct (unique_key, id, found, list) AS
  ( SELECT TOP (1) unique_key, id, 1, CAST(CONCAT('/',id, '/') AS VARCHAR(MAX))
    FROM x_large_table_2
  UNION ALL
    SELECT y.unique_key, y.ID, ct.found + 1, 
        CAST(CONCAT(ct.list, y.id, '/') AS VARCHAR(MAX))
    FROM ct
      CROSS APPLY 
      ( SELECT x.unique_key, x.id, 
               rn = ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
        FROM x_large_table_2 AS x
        WHERE x.unique_key > ct.unique_key
          AND ct.list NOT LIKE '%/' + id + '/%'
      ) AS y
    WHERE ct.found < 5       -- the TOP (n) parameter here
      AND y.rn = 1
  )
-- SELECT * FROM ct ;        -- for debugging
SELECT id FROM ct ;