使用 WHERE IN 删除操作期间的意外扫描

Question

我有一个类似如下的查询：

DELETE FROM tblFEStatsBrowsers WHERE BrowserID NOT IN (
    SELECT DISTINCT BrowserID FROM tblFEStatsPaperHits WITH (NOLOCK) WHERE BrowserID IS NOT NULL
)

tblFEStatsBrowsers 有 553 行。
tblFEStatsPaperHits 有 47.974.301 行。

tblFEStatsBrowsers:

CREATE TABLE [dbo].[tblFEStatsBrowsers](
    [BrowserID] [smallint] IDENTITY(1,1) NOT NULL,
    [Browser] [varchar](50) NOT NULL,
    [Name] [varchar](40) NOT NULL,
    [Version] [varchar](10) NOT NULL,
    CONSTRAINT [PK_tblFEStatsBrowsers] PRIMARY KEY CLUSTERED ([BrowserID] ASC)
)

tblFEStatsPaperHits：

CREATE TABLE [dbo].[tblFEStatsPaperHits](
    [PaperID] [int] NOT NULL,
    [Created] [smalldatetime] NOT NULL,
    [IP] [binary](4) NULL,
    [PlatformID] [tinyint] NULL,
    [BrowserID] [smallint] NULL,
    [ReferrerID] [int] NULL,
    [UserLanguage] [char](2) NULL
)

tblFEStatsPaperHits 上有一个不包含 BrowserID 的聚集索引。因此，执行内部查询将需要对 tblFEStatsPaperHits 进行全表扫描 - 这完全没问题。

目前，对 tblFEStatsBrowsers 中的每一行执行一次完整扫描，这意味着我有 553 次 tblFEStatsPaperHits 的全表扫描。

重写为 WHERE EXISTS 不会改变计划：

DELETE FROM tblFEStatsBrowsers WHERE NOT EXISTS (
    SELECT * FROM tblFEStatsPaperHits WITH (NOLOCK) WHERE BrowserID = tblFEStatsBrowsers.BrowserID
)

但是，正如 Adam Machanic 所建议的，添加 HASH JOIN 选项确实会产生最佳执行计划（只需扫描 tblFEStatsPaperHits）：

DELETE FROM tblFEStatsBrowsers WHERE NOT EXISTS (
    SELECT * FROM tblFEStatsPaperHits WITH (NOLOCK) WHERE BrowserID = tblFEStatsBrowsers.BrowserID
) OPTION (HASH JOIN)

现在这不是如何解决这个问题的问题 - 我可以使用 OPTION (HASH JOIN) 或手动创建临时表。我更想知道为什么查询优化器会使用它当前所做的计划。

由于 QO 在 BrowserID 列上没有任何统计信息，我猜它假设了最坏的情况 - 5000 万个不同的值，因此需要相当大的内存/tempdb 工作表。因此，最安全的方法是对 tblFEStatsBrowsers 中的每一行执行扫描。两个表中的 BrowserID 列之间没有外键关系，因此 QO 无法从 tblFEStatsBrowsers 中扣除任何信息。

原因就这么简单吗？

更新 1
给出几个统计数据： OPTION (HASH JOIN)：
208.711 次逻辑读取（12 次扫描）

选项（LOOP JOIN，HASH GROUP）：
11.008.698 逻辑读取（~scan per BrowserID (339)）

无选项：
11.008.775 次逻辑读取（~scan per BrowserID (339)）

更新 2
优秀的答案，你们所有人 - 谢谢！很难只选一个。虽然 Martin 是第一个，而 Remus 提供了一个很好的解决方案，但我必须把它交给新西兰人，因为他们在细节上有精神:)

Answer 1

“我更想知道为什么查询优化器会使用它目前所做的计划。”

换句话说，问题是为什么与替代方案（其中有很多）相比，以下计划对优化器来说看起来最便宜。

联接的内侧本质上是为 的每个相关值运行以下形式的查询BrowserID：

DECLARE @BrowserID smallint;

SELECT 
    tfsph.BrowserID 
FROM dbo.tblFEStatsPaperHits AS tfsph 
WHERE 
    tfsph.BrowserID = @BrowserID 
OPTION (MAXDOP 1);

请注意，估计的行数是185,220（不是289,013），因为相等比较隐式排除NULL（除非ANSI_NULLS是OFF）。上述计划的估计成本为206.8台。

现在让我们添加一个TOP (1)子句：

DECLARE @BrowserID smallint;

SELECT TOP (1)
    tfsph.BrowserID 
FROM dbo.tblFEStatsPaperHits AS tfsph 
WHERE 
    tfsph.BrowserID = @BrowserID 
OPTION (MAXDOP 1);

估计成本现在是0.00452 个单位。Top 物理运算符的添加在 Top 运算符处设置了1 行的行目标。那么问题就变成了如何为聚集索引扫描得出一个“行目标”；也就是说，在一行与BrowserID谓词匹配之前，扫描应该处理多少行？

可用的统计信息显示166 个不同的BrowserID值（1/[所有密度] = 1/0.006024096 = 166）。Costing 假设不同的值均匀分布在物理行上，因此聚集索引扫描的行目标设置为166.302（考虑到自收集采样统计信息以来表基数的变化）。

扫描预期的 166 行的估计成本不是很大（甚至执行 339 次，每次更改一次BrowserID） - Clustered Index Scan 显示估计成本为1.3219 个单位，显示了行目标的缩放效果。I/O 和 CPU 的未缩放运算符成本分别显示为153.931和52.8698：

在实践中，这是非常不可能的从索引扫描的第166行（可以以任意顺序发生，他们将返回）将包含每个可能的一个BrowserID值。尽管如此，该DELETE计划的总成本为1.40921 个单位，因此由优化器选择。巴特·邓肯 (Bart Duncan) 在最近的一篇题为“行目标变得无赖”的帖子中展示了这种类型的另一个例子。

这也是有趣的是，在执行计划中的顶级运营商是不与反相关的半加入（特别是“短路”马丁提到）。我们可以通过首先禁用名为GbAggToConstScanOrTop的探索规则来开始查看 Top 的来源：

DBCC RULEOFF ('GbAggToConstScanOrTop');
GO
DELETE FROM tblFEStatsBrowsers 
WHERE BrowserID NOT IN 
(
    SELECT DISTINCT BrowserID 
    FROM tblFEStatsPaperHits WITH (NOLOCK) 
    WHERE BrowserID IS NOT NULL
) OPTION (MAXDOP 1, LOOP JOIN, RECOMPILE);
GO
DBCC RULEON ('GbAggToConstScanOrTop');

该计划的估计成本为364.912，并显示 Top 替换了 Group By Aggregate（按相关列分组BrowserID）。聚合不是由于DISTINCT查询文本中的冗余：它是可以通过两个探索规则LASJNtoLASJNonDist和LASJOnLclDist引入的优化。禁用这两个也会产生这个计划：

DBCC RULEOFF ('LASJNtoLASJNonDist');
DBCC RULEOFF ('LASJOnLclDist');
DBCC RULEOFF ('GbAggToConstScanOrTop');
GO
DELETE FROM tblFEStatsBrowsers 
WHERE BrowserID NOT IN 
(
    SELECT DISTINCT BrowserID 
    FROM tblFEStatsPaperHits WITH (NOLOCK) 
    WHERE BrowserID IS NOT NULL
) OPTION (MAXDOP 1, LOOP JOIN, RECOMPILE);
GO
DBCC RULEON ('LASJNtoLASJNonDist');
DBCC RULEON ('LASJOnLclDist');
DBCC RULEON ('GbAggToConstScanOrTop');

该计划的估计成本为40729.3 个单位。

如果没有从 Group By 到 Top 的转换，优化器“自然地”BrowserID在反半连接之前选择一个带有聚合的散列连接计划：

DBCC RULEOFF ('GbAggToConstScanOrTop');
GO
DELETE FROM tblFEStatsBrowsers 
WHERE BrowserID NOT IN 
(
    SELECT DISTINCT BrowserID 
    FROM tblFEStatsPaperHits WITH (NOLOCK) 
    WHERE BrowserID IS NOT NULL
) OPTION (MAXDOP 1, RECOMPILE);
GO
DBCC RULEON ('GbAggToConstScanOrTop');

没有 MAXDOP 1 限制，一个并行计划：

“修复”原始查询的另一种方法BrowserID是在执行计划报告的基础上创建缺失的索引。当内侧被索引时，嵌套循环效果最好。在最好的时候，估计半连接的基数是具有挑战性的。没有正确的索引（大表甚至没有唯一键！）根本没有帮助。

我在行目标，第 4 部分：反联接反模式中写了更多关于此的内容。

Answer 2

当我运行您的脚本以创建仅统计数据库和问题中的查询时，我得到以下计划。

计划中显示的表基数是

• tblFEStatsPaperHits： 48063400
• tblFEStatsBrowsers ： 339

所以它估计需要执行tblFEStatsPaperHits339 次扫描。每个扫描都有相关的谓词tblFEStatsBrowsers.BrowserID=tblFEStatsPaperHits.BrowserID AND tblFEStatsPaperHits.BrowserID IS NOT NULL，该谓词被下推到扫描运算符中。

然而，该计划并不意味着会有 339 次完整扫描。由于它在反半连接运算符下，一旦找到每次扫描的第一个匹配行，它就会短路其余部分。此节点的估计子树成本为1.32603，整个计划的成本为1.41337。

对于哈希连接，它给出了以下计划

整个计划的成本为418.415（大约比嵌套循环计划贵 300 倍），而单独的单个完整聚集索引扫描的tblFEStatsPaperHits成本为 at 206.8。将此与1.32603之前给出的 339 次局部扫描的估计值进行比较（平均局部扫描估计成本 = 0.003911592）。

因此，这表明每次部分扫描的成本比完全扫描的成本低 53,000 倍。如果成本计算与行数成线性比例，那么这意味着它假设在每次迭代中平均只需要处理 900 行，然后才能找到匹配的行并且可以短路。

然而，我认为成本计算并不会以这种线性方式进行扩展。我认为它们还包含了一些固定启动成本的元素。TOP在以下查询中尝试各种值

SELECT TOP 147 BrowserID 
FROM [dbo].[tblFEStatsPaperHits] 

147给出与0.003911592at最接近的估计子树成本0.0039113。无论哪种方式，很明显，它是基于这样的假设，即每次扫描只需要处理表的一小部分，按数百行而不是数百万行的顺序计算。

我不确定它基于这个假设的确切数学，它并没有真正与计划其余部分中的行数估计相加（来自嵌套循环连接的 236 个估计行意味着有 236根本找不到匹配行并且需要完整扫描的情况）。我认为这只是建模假设有所下降并使嵌套循环计划显着低于成本的情况。

Answer 3

在我的书甚至一个50M的行扫描是不可接受的......我惯用的伎俩就是将这种独特价值，并保持它最新的委托发动机：

create view [dbo].[vwFEStatsPaperHitsBrowserID]
with schemabinding
as
select BrowserID, COUNT_BIG(*) as big_count
from [dbo].[tblFEStatsPaperHits]
group by [BrowserID];
go

create unique clustered index [cdxVwFEStatsPaperHitsBrowserID] 
  on [vwFEStatsPaperHitsBrowserID]([BrowserID]);
go

这为您提供了每个 BrowserID 一行的物化索引，无需扫描 50M 行。引擎将为您维护它，QO 将在您发布的语句中“按原样”使用它（没有任何提示或查询重写）。

缺点当然是争用。任何插入或删除操作tblFEStatsPaperHits（我猜是一个带有大量插入的日志表）都必须序列化对给定 BrowserID 的访问。如果您愿意购买它，有一些方法可以使其可行（延迟更新、2 阶段日志记录等）。