为什么这个连接基数估计这么大？

Question

对于以下查询，我遇到了我认为不可能高的基数估计：

SELECT dm.PRIMARY_ID
FROM
(
    SELECT COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID) PRIMARY_ID
    FROM X_DRIVING_TABLE dt
    LEFT OUTER JOIN X_DETAIL_1 d1 ON dt.ID = d1.ID
    LEFT OUTER JOIN X_DETAIL_LINK lnk ON d1.LINK_ID = lnk.LINK_ID
    LEFT OUTER JOIN X_DETAIL_2 d2 ON dt.ID = d2.ID
    LEFT OUTER JOIN X_DETAIL_3 d3 ON dt.ID = d3.ID
) dm
INNER JOIN X_LAST_TABLE lst ON dm.PRIMARY_ID = lst.JOIN_ID;

估计的计划在这里。我正在处理表格的统计副本，因此无法包含实际计划。但是，我不认为它与这个问题非常相关。

SQL Server 估计将从“dm”派生表返回 481577 行。然后估计在连接到 X_LAST_TABLE 后将返回 4528030000 行，但 JOIN_ID 是 X_LAST_TIME 的主键。我希望连接基数估计在 0 到 481577 行之间。相反，当交叉连接外部表和内部表时，行估计值似乎是我得到的行数的 10%。计算结果为四舍五入：481577*94025*0.1 = 45280277425，四舍五入为 4528030000。

我主要是在寻找这种行为的根本原因。我也对简单的解决方法感兴趣，但请不要建议更改数据模型或使用临时表。此查询是视图中逻辑的简化。我知道在几列上做 COALESCE 并加入它们并不是一个好习惯。这个问题的部分目标是弄清楚我是否需​​要建议重新设计数据模型。

我正在 Microsoft SQL Server 2014 上进行测试，并启用了旧基数估算器。TF 4199 和其他人都在。如果最终相关，我可以提供完整的跟踪标志列表。

这是最相关的表定义：

CREATE TABLE X_LAST_TABLE (
JOIN_ID NUMERIC(18, 0) NOT NULL
    CONSTRAINT PK_X_LAST_TABLE PRIMARY KEY CLUSTERED (JOIN_ID ASC)
);

如果有人想在他们的一台服务器上重现该问题，我还编写了所有表创建脚本及其统计信息。

添加一些我的观察结果，使用 TF 2312 修复了估计值，但这对我来说不是一个选择。TF 2301 不修正估计。删除其中一个表可修复估计值。奇怪的是，更改 X_DETAIL_LINK 的连接顺序也修复了估计值。通过更改连接顺序，我的意思是重写查询而不是用提示强制连接顺序。这是仅更改连接顺序时的估计查询计划。

Answer 1

我知道COALESCE在几个专栏上做并加入它们并不是一个好习惯。

当模式是 3NF+（带有键和约束）并且查询是关系型的并且主要是 SPJG（选择-投影-连接-分组）时，生成良好的基数和分布估计已经足够困难了。CE 模型建立在这些原则之上。更不寻常的或者非关系的特点有一个查询时，愈接近什么样的基数和选择性框架可以处理边界。走得太远，CE 会放弃猜测。

大多数 MCVE 示例都是简单的 SPJ（无 G），尽管主要是外等连接（建模为内连接加反半连接）而不是更简单的内等连接（或半连接）。所有关系都有键，但没有外键或其他约束。除了一个连接之外，所有连接都是一对多的，这很好。

例外是和之间的多对多外连接。此连接在 MCVE 中的唯一功能是潜在地复制. 这是一种不寻常的事情。X_DETAIL_1X_DETAIL_LINKX_DETAIL_1

简单的相等谓词（选择）和标量运算符也更好。例如，attribute compare-equal 属性/常量通常在模型中运行良好。修改直方图和频率统计以反映此类谓词的应用相对“容易”。

COALESCE建立在 上CASE，而后者又在内部实现为IIF（这IIF在 Transact-SQL 语言中出现之前确实如此）。CE 模型IIF为UNION具有两个互斥子项的 a，每个子项都包含一个基于输入关系选择的项目。列出的每个组件都具有模型支持，因此将它们组合起来相对简单。即便如此，抽象层越多，最终结果往往越不准确——这也是较大的执行计划往往不太稳定和可靠的原因。

ISNULL另一方面，是引擎固有的。它不是使用任何更基本的组件构建的。ISNULL例如，将 的效果应用于直方图就像替换NULL值的步骤一样简单（并根据需要进行压缩）。它仍然相对不透明，就像标量运算符一样，因此最好尽可能避免。尽管如此，与CASE基于 - 的替代方案相比，它通常对优化器更友好（对优化器不友好）。

CE（70 和 120+）非常复杂，即使按照 SQL Server 标准也是如此。这不是将简单的逻辑（带有秘密公式）应用于每个运算符的情况。CE 知道密钥和函数依赖；它知道如何使用频率、多元统计和直方图进行估计；并且绝对有大量的特殊情况、改进、制衡和支持结构。它通常以多种方式（频率、直方图）估计，例如连接，并根据两者之间的差异决定结果或调整。

最后要介绍的基本内容是：从下往上对查询树中的每个操作运行初始基数估计。首先为叶运算符（基本关系）导出选择性和基数。为父运算符导出修改后的直方图和密度/频率信息。我们走得越远，估计的质量就越低，因为错误往往会累积。

这个单一的初始综合估计提供了一个起点，并且发生在对最终执行计划进行任何考虑之前（它甚至发生在微不足道的计划编译阶段之前）。此时的查询树倾向于相当接近地反映查询的书面形式（尽管删除了子查询，并应用了简化等）

在初始估计之后，SQL Server 立即执行启发式连接重新排序，松散地尝试重新排序树以首先放置较小的表和高选择性连接。它还尝试在外连接和交叉产品之前定位内连接。它的功能并不广泛；它的努力并非详尽无遗；并且它不考虑物理成本（因为它们还不存在——只有统计信息和元数据信息存在）。启发式重新排序在简单的内部 equijoin 树上最成功。它的存在是为了为基于成本的优化提供一个“更好”的起点。

为什么这个连接基数估计这么大？

MCVE 有一个“不寻常的”主要是冗余的多对多连接，以及COALESCE谓词中的等连接。运算符树也有一个内部连接last，启发式连接重新排序无法将树向上移动到更喜欢的位置。撇开所有的标量和投影，连接树是：

LogOp_Join [ Card=4.52803e+009 ]
    LogOp_LeftOuterJoin [ Card=481577 ]
        LogOp_LeftOuterJoin [ Card=481577 ]
            LogOp_LeftOuterJoin [ Card=481577 ]
                LogOp_LeftOuterJoin [ Card=481577 ]
                LogOp_Get TBL: X_DRIVING_TABLE(alias TBL: dt) [ Card=481577 ]
                LogOp_Get TBL: X_DETAIL_1(alias TBL: d1) [ Card=70 ]
                LogOp_Get TBL: X_DETAIL_LINK(alias TBL: lnk) [ Card=47 ]
            LogOp_Get TBL: X_DETAIL_2(alias TBL: d2) X_DETAIL_2 [ Card=119 ]
        LogOp_Get TBL: X_DETAIL_3(alias TBL: d3) X_DETAIL_3 [ Card=281 ]
    LogOp_Get TBL: X_LAST_TABLE(alias TBL: lst) X_LAST_TABLE [ Card=94025 ]

请注意，错误的最终估计已经到位。它Card=4.52803e+009以双精度浮点值 4.5280277425e+9（十进制为 4528027742.5）的形式打印并在内部存储。

原始查询中的派生表已被删除，并且投影标准化。执行初始基数和选择性估计的树的 SQL 表示是：

SELECT 
    PRIMARY_ID = COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID)
FROM X_DRIVING_TABLE dt
LEFT OUTER JOIN X_DETAIL_1 d1
    ON dt.ID = d1.ID
LEFT OUTER JOIN X_DETAIL_LINK lnk 
    ON d1.LINK_ID = lnk.LINK_ID
LEFT OUTER JOIN X_DETAIL_2 d2 
    ON dt.ID = d2.ID
LEFT OUTER JOIN X_DETAIL_3 d3 
    ON dt.ID = d3.ID
INNER JOIN X_LAST_TABLE lst 
    ON lst.JOIN_ID = COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID)

（顺便说一句，重复COALESCE也出现在最终计划中 - 一次在最终的计算标量中，一次在内部联接的内侧）。

注意最后的连接。这个内部连接（根据定义）是X_LAST_TABLE和前面的连接输出的笛卡尔积，应用了一个选择（连接谓词）lst.JOIN_ID = COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID)。笛卡尔积的基数就是 481577 * 94025 = 45280277425。

为此，我们需要确定并应用谓词的选择性。不透明扩展COALESCE树（就UNION和IIF，记住）的组合以及对关键信息的影响、派生的直方图和早期“不寻常”的多对多外连接的频率组合意味着 CE 无法以任何正常方式得出可接受的估计。

结果，它进入了猜测逻辑。猜测逻辑中等复杂，尝试了“受过教育的”猜测和“不那么受过教育”的猜测算法层。如果找不到更好的猜测基础，模型将使用最后手段的猜测，对于等式比较，它是：sqllang!x_Selectivity_Equal= 固定 0.1 选择性（10% 猜测）：

-- the moment of doom
movsd xmm0,mmword ptr [sqllang!x_Selectivity_Equal

结果是笛卡尔积的 0.1 选择性：481577 * 94025 * 0.1 = 4528027742.5 (~4.52803e+009) 如前所述。

重写

当有问题的连接被注释掉时，会产生更好的估计，因为避免了固定选择性“最后的猜测”（关键信息由 1-M 连接保留）。估计的质量仍然是低置信度的，因为COALESCE连接谓词根本不是 CE 友好的。我想，修正后的估计至少对人类来说看起来更合理。

当查询是使用X_DETAIL_LINK 放置在最后的外部连接写入时，启发式重新排序能够将其与最终内部连接交换X_LAST_TABLE。将内连接放在问题旁边，使有限的早期重新排序能力有机会改善最终估计，因为大部分冗余的“不寻常”多对多外连接的影响出现在棘手的选择性估计之后为COALESCE。同样，估计值比固定猜测好不了多少，并且可能经不起法庭上确定的盘问。

重新排序内连接和外连接的混合既困难又耗时（即使是第 2 阶段的完全优化也只尝试有限的理论移动子集）。

ISNULLMax Vernon 的答案中建议的嵌套设法避免了救助固定猜测，但最终估计是不可能的零行（为了体面而提升到一行）。对于计算具有的所有统计基础，这也可能是 1 行的固定猜测。

我希望连接基数估计在 0 到 481577 行之间。

这是一个合理的期望，即使人们接受基数估计可以在不同时间（在基于成本的优化期间）在物理上不同但逻辑和语义相同的子树上发生 - 最终计划是一种缝合在一起的最佳计划最好（每个备忘录组）。缺乏计划范围的一致性保证并不意味着个人加入应该能够蔑视尊重，我明白这一点。

另一方面，如果我们最后只能猜测到最后，希望已经落空，何必呢。我们尝试了所有我们知道的技巧，然后放弃了。如果不出意外，疯狂的最终估计是一个很好的警告信号，表明在此查询的编译和优化期间，CE 内并非一切顺利。

当我尝试 MCVE 时，120+ CEISNULL为原始查询生成了零 (= 1) 行最终估计值（如嵌套），这与我的思维方式一样不可接受。

真正的解决方案可能涉及设计更改，以允许简单的 equi-joins 没有COALESCEor ISNULL，以及理想的外键和其他对查询编译有用的约束。

Answer 2

我相信因加入而Compute Scalar产生的运营商是问题的根本原因。从历史上看，计算标量很难准确地计算成本^1、2。COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID)X_LAST_TABLE.JOIN_ID

由于您提供了一个具有准确统计信息的最低限度完整的可验证示例（谢谢！），我能够重写查询，以便连接不再需要扩展到的CASE功能COALESCE，从而导致更准确的行估计，并且显然更多准确的总体成本计算^{见最后的附录。}：

SELECT COALESCE(dm.d1ID, dm.d2ID, dm.d3ID)
FROM
(
    SELECT d1ID = d1.JOIN_ID
        , d2ID = d2.JOIN_ID
        , d3ID = d3.JOIN_ID
    FROM X_DRIVING_TABLE dt
    LEFT OUTER JOIN X_DETAIL_1 d1 ON dt.ID = d1.ID
    LEFT OUTER JOIN X_DETAIL_LINK lnk ON d1.LINK_ID = lnk.LINK_ID
    LEFT OUTER JOIN X_DETAIL_2 d2 ON dt.ID = d2.ID
    LEFT OUTER JOIN X_DETAIL_3 d3 ON dt.ID = d3.ID
) dm
INNER JOIN X_LAST_TABLE lst 
    ON (dm.d1ID IS NOT NULL AND dm.d1ID = lst.JOIN_ID)
    OR (dm.d1ID IS NULL AND dm.d2ID IS NOT NULL AND dm.d2ID = lst.JOIN_ID)
    OR (dm.d1ID IS NULL AND dm.d2ID IS NULL AND dm.d3ID IS NOT NULL AND dm.d3ID = lst.JOIN_ID);

虽然xID IS NOT NULL技术上不需要 ，因为ID = JOIN_ID不会加入空值，我将它们包括在内，因为它更清楚地描绘了意图。

计划 1和计划 2

方案一：

方案二：

新查询从并行化中受益（？）。另外值得注意的是，新查询的估计输出行数为 1，实际上在一天结束时可能比原始查询的估计值 4528030000 更差。新查询中选择运算符的子树成本为 243210，而原始时钟为 536.535，显然更低。话虽如此，我不相信第一个估计接近现实。

附录 1。

在与@Lamak 的讨论激发下，在The Heap™上与不同的人进一步协商后，似乎我上面的观察查询执行得非常糟糕，即使有并行性也是如此。允许既有良好性能的解决方案和良好的基数估计包括更换的COALESCE(x,y,z)有ISNULL(ISNULL(x, y), z)，如：

SELECT dm.PRIMARY_ID
FROM
(
    SELECT ISNULL(ISNULL(d1.JOIN_ID, d2.JOIN_ID), d3.JOIN_ID) PRIMARY_ID
    FROM X_DRIVING_TABLE dt
    LEFT OUTER JOIN X_DETAIL_1 d1 ON dt.ID = d1.ID
    LEFT OUTER JOIN X_DETAIL_LINK lnk ON d1.LINK_ID = lnk.LINK_ID
    LEFT OUTER JOIN X_DETAIL_2 d2 ON dt.ID = d2.ID
    LEFT OUTER JOIN X_DETAIL_3 d3 ON dt.ID = d3.ID
) dm
INNER JOIN X_LAST_TABLE lst ON dm.PRIMARY_ID = lst.JOIN_ID;

COALESCE被CASE查询优化器转换为“在幕后”的语句。因此，基数估计器很难发现埋在里面的列的可靠统计数据COALESCE。 ISNULL作为一个内在函数对于基数估计器来说更加“开放”。ISNULL如果已知目标不可为空，那么可以优化掉也没有任何价值。

该ISNULL变体的计划如下所示：

（在此处粘贴计划版本）。

仅供参考，哨兵一号为他们伟大的计划资源管理器提供了道具，我用它来制作上面的图形计划。