SQL Server的优化器如何估计连接表中的行数？

Question

我正在AdventureWorks2012数据库中运行此查询：

SELECT 
    s.SalesOrderID,
    d.CarrierTrackingNumber,
    d.ProductID,
    d.OrderQty
FROM Sales.SalesOrderHeader s 
JOIN Sales.SalesOrderDetail d 
    ON s.SalesOrderID = d.SalesOrderID
WHERE s.CustomerID = 11077

如果我查看估计的执行计划，我会看到以下内容：

初始的索引搜索（右上方）使用了IX_SalesOrderHeader_CustomerID索引，并在字面值11077上进行搜索。它估计有2.6192行。

如果我使用DBCC SHOW_STATISTICS ('Sales.SalesOrderHeader', 'IX_SalesOrderHeader_CustomerID') WITH HISTOGRAM，它会显示值11077位于两个样本键11019和11091之间。

在11019和11091之间的不同行的平均数量为2.619718，或者四舍五入为2.61972，这是索引搜索显示的估计行数的值。

我不理解的部分是针对SalesOrderDetail表的聚集索引搜索的估计行数。

如果我运行DBCC SHOW_STATISTICS ('Sales.SalesOrderDetail', 'PK_SalesOrderDetail_SalesOrderID_SalesOrderDetailID')：

所以我要连接的SalesOrderID的密度是3.178134E-05。这意味着1/3.178134E-05（31465）等于SalesOrderDetail表中唯一的SalesOrderID值的数量。

如果SalesOrderDetail中有31465个唯一的SalesOrderID，那么在均匀分布的情况下，每个SalesOrderID的平均行数是121317（总行数）除以31465。平均值为3.85561。

所以如果要循环遍历的估计行数是2.61972，并且平均返回值为3.85561，那么我认为估计行数应该是2.61972 * 3.85561 = 10.10062。

但是估计行数是11.4867。

我觉得我对第二个估计的理解是错误的，而且不同的数字似乎表明了这一点。我错过了什么？

- 8kb

Answer 1

我觉得我对第二个估计的理解是错误的，不同的数字似乎表明了这一点。我错过了什么？

使用SQL Server 2012的基数估计器，连接的选择性驱动了嵌套循环连接内部一侧的预估行数，而不是反过来。

11.4867这个数字是通过将连接输出的计算估计基数（30.0919）除以迭代次数（2.61972）得到的，用于在showplan中显示。使用单精度浮点运算，结果为11.4867。

事实就是如此简单。请注意，（逻辑上的）连接选择性与物理连接操作符的选择无关。无论最终使用嵌套循环连接、哈希连接还是合并连接物理操作符执行连接，它的选择性都保持不变。

在SQL Server 2012及更早版本中，联接选择性（作为整体）使用每个表的SalesOrderID直方图进行估算（在步长边界对齐后，根据需要使用线性插值进行调整）。与SalesOrderHeader表相关联的SalesOrderID直方图还根据独立的CustomerID过滤器的缩放效应进行了调整。

这并不意味着问题中提出的备选计算方式在根本上有什么“错误”；它只是基于一组不同的假设进行计算。对于给定的逻辑操作序列，始终会有不同的计算或合并估计的方法。不能保证应用于相同数据的不同统计方法将产生相同的答案，也不能保证其中一种方法始终优于另一种方法。由于应用不同统计方法而导致的不一致性甚至可能在单个最终执行计划中出现，尽管它们很少被注意到。

作为一个附注，SQL Server 2014的基数估算器在合并独立过滤器调整的直方图信息（粗略对齐）方面采取了不同的方法，这导致了对于此查询的不同最终估计结果为10.1006行。

Plan for computation:

  CSelCalcExpressionComparedToExpression
  (QCOL: [s].SalesOrderID x_cmpEq QCOL: [d].SalesOrderID)

Loaded histogram for column QCOL: [s].SalesOrderID from stats with id 1
Loaded histogram for column QCOL: [d].SalesOrderID from stats with id 1

Stats collection generated: 

  CStCollJoin(ID=4, **CARD=10.1006** x_jtInner)
      CStCollFilter(ID=3, CARD=2.61972)
          CStCollBaseTable(ID=1, CARD=31465 TBL: Sales.SalesOrderHeader AS TBL: s)
      CStCollBaseTable(ID=2, CARD=121317 TBL: Sales.SalesOrderDetail AS TBL: d)

这恰好是与问题中的计算结果相同，尽管详细的推理方式不同（即它不是基于假设的嵌套循环实现）。

- Paul White