sql-server – 为什么我的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只需扫描表的第一个数据页就可以找到两个不同的值,但它是scans all of the data instead.为什么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,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;

以下查询 scans all 10 million rows from the table.如何获取不扫描整个表的内容？我正在使用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);

Msg 8622,Level 16,State 1,Line 1

Query processor could not produce a query plan because of the hints defined in this query. Resubmit the query without specifying any hints and without using SET FORCEPLAN.

GbAggToSort将group-by聚合(distinct)实现为不同的排序.这是一个阻塞运算符,它将在生成任何行之前读取输入中的所有数据. GbAggToStrm将group-by聚合实现为流聚合(在此实例中也需要输入排序).这也是一个阻塞运算符. GbAggToHS实现为哈希匹配,这是我们在问题的错误计划中看到的,但它可以实现为哈希匹配(聚合)或哈希匹配(流不同).

哈希匹配(flow distinct)运算符是解决此问题的一种方法,因为它不会阻塞.一旦找到足够的不同值,sql Server应该能够停止扫描.

The Flow Distinct logical operator scans the input,removing duplicates. Whereas the Distinct operator consumes all input before producing any output,the Flow Distinct operator returns each row as it is obtained from the input (unless that row is a duplicate,in which case it is discarded).

为什么问题中的查询使用哈希匹配(聚合)而不是哈希匹配(流不同)？随着表中不同值的变化,我预计散列匹配(流不同)查询的成本会降低,因为它需要扫描到表的行数估计应该减少.我预计哈希匹配(聚合)计划的成本会增加,因为它需要构建的哈希表会变得更大.调查此问题的一种方法是在creating a plan guide之前.如果我创建了两个数据副本但是对其中一个应用了计划指南,我应该能够将哈希匹配(聚合)与哈希匹配(不同)并排比较相同的数据.请注意,我无法通过禁用查询优化器规则来执行此操作,因为同一规则适用于两个计划(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)

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

计划指南仅适用于确切的查询文本,因此我们将其从计划指南中复制回来：


重置数据：


获取适用于计划指南的查询的query plan：


这有我们想要的哈希匹配(flow distinct)运算符和我们的测试数据.请注意,sql Server希望读取表中的所有行,并且估计的开销与具有散列匹配(聚合)的计划完全相同.我做的测试表明,当计划的行目标大于或等于sql Server从表中预期的不同值的数量时,两个计划的成本是相同的,在这种情况下可以简单地从统计.不幸的是(对于我们的查询),当成本相同时,优化器会选择哈希匹配(聚合)而不是哈希匹配(流不同).所以我们距离我们想要的计划是0.0000001魔术优化器单位.
解决此问题的一种方法是减少行目标.如果从视图点开始的行目标是优化器小于不同的行数,我们可能会得到哈希匹配(流不同).这可以通过OPTIMIZE FOR查询提示来完成：


对于此查询,优化程序创建计划,就好像查询只需要第一行,但执行查询时,它会返回前10行.在我的机器上,此查询从X_10_DISTINCT_HEAP扫描892800行,并在299 ms内完成,具有250 ms的cpu时间和2537次逻辑读取.
请注意,如果统计信息仅报告一个不同的值,则此技术将不起作用,这可能会针对偏斜数据的采样统计信息发生.但是,在这种情况下,您的数据不可能被密集地打包,以证明使用这样的技术是合理的.通过扫描表中的所有数据,您可能不会损失太多,特别是如果可以并行完成.
解决此问题的另一种方法是通过膨胀sql Server期望从基表获取的估计的不同值的数量.这比预期的要难.应用确定性函数不可能增加结果的独特计数.如果查询优化器知道该数学事实(某些测试表明它至少是出于我们的目的),那么应用确定性函数(includes all string functions)将不会增加不同行的估计数量.
许多非确定性函数也不起作用,包括NEWID()和RAND()的明显选择.但是,LAG()为此查询提供了技巧.查询优化器期望针对LAG表达式提供1000万个不同的值,这将鼓励hash match (flow distinct) plan：


在我的机器上,并在1165 ms内完成,cpu时间为1109 ms,逻辑读取为2537,因此LAG()会增加相当多的相对开销. @Paul White建议为此查询尝试批处理模式处理.在sql Server 2016上,我们甚至可以使用MAXDOP 1进行批处理模式处理.获取行存储表的批处理模式处理的一种方法是加入空CCI,如下所示：


该代码导致this query plan.
Paul指出我必须更改查询以使用LAG(…,因为LAG(…,0)似乎没有资格进行Window Aggregate优化.此更改将已用时间减少到520毫秒,cpu时间减少到454毫秒.
请注意,LAG()方法不是最稳定的方法.如果Microsoft更改了针对该功能的唯一性假设,则它可能不再起作用.它与传统的CE有不同的估计.此类对堆的优化也不是一个好主意.如果重建表,最终可能会在最糟糕的情况下结束,其中几乎所有行都需要从表中读取.
对于具有唯一列的表(例如问题中的聚集索引示例),我们有更好的选择.例如,我们可以通过使用始终返回空字符串的SUBSTRING表达式来欺骗优化器. sql Server认为SUBSTRING不会更改不同值的数量,因此如果我们将其应用于唯一列(例如PK),则估计的不同行数为1000万.以下query获取哈希匹配(flow distinct)运算符：


在我的机器上,此查询从X_10_DISTINCT_CI扫描900000行,并在333 ms内完成,cpu时间为297 ms,逻辑读取为3011.
总之,当N> =表中估计的不同行数时,查询优化器似乎假设将从表中读取SELECT DISTINCT TOP N查询的所有行.散列匹配(聚合)运算符可能具有与散列匹配(流不同)运算符相同的开销,但优化器始终选择聚合运算符.当在表扫描开始附近有足够的不同值时,这可能导致不必要的逻辑读取.欺骗优化器使用散列匹配(flow distinct)运算符的两种方法是使用OPTIMIZE FOR提示降低行目标,或者使用唯一列上的LAG()或SUBSTRING增加不同行的估计数.
-- plan handle is 0xSELECT DISTINCT TOP 10 ID
FROM X_10_DISTINCT_HEAP
OPTION (MAXDOP 1,QUERYRULEOFF GbAggToStrm);

7009014BC025097E88F6C01000001000000000000000000000000000000000000000000000000000000
 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',
 0x
SELECT DISTINCT TOP 10 ID
FROM X_10_DISTINCT_HEAP
OPTION (MAXDOP 1,QUERYRULEOFF GbAggToStrm);
SELECT DISTINCT TOP 10 ID
FROM X_10_DISTINCT_HEAP
OPTION (MAXDOP 1,QUERYRULEOFF GbAggToStrm);SELECT DISTINCT TOP 10 ID
FROM X_10_DISTINCT_HEAP
OPTION (MAXDOP 1,QUERYRULEOFF GbAggToStrm);7009014BC025097E88F6C01000001000000000000000000000000000000000000000000000000000000;
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)DECLARE @j INT = 10;

SELECT DISTINCT TOP (@j) VAL
FROM X_10_DISTINCT_HEAP
OPTION (MAXDOP 1,OPTIMIZE FOR (@j = 1));SELECT DISTINCT TOP 10 LAG(VAL,0) OVER (ORDER BY (SELECT NULL)) AS ID
FROM X_10_DISTINCT_HEAP
OPTION (MAXDOP 1);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);SELECT DISTINCT TOP 10 VAL + SUBSTRING(CAST(PK AS VARCHAR(10)),11,1)
FROM X_10_DISTINCT_CI
OPTION (MAXDOP 1);

sql-server – 为什么我的SELECT DISTINCT TOP N查询扫描整个表？

解决方法

相关文章