SQL Server中关于基数估计如何计算预估行数的一些探讨

huiselele

　　   关于SQL Server 2014中的基数估计，官方文档Optimizing Your Query Plans with the SQL Server 2014 Cardinality Estimator里有大量细节介绍，但是全部是英文，估计也没有几个人仔细阅读。那么SQL Server 2014中基数估计的预估行数到底是怎么计算的呢？ 有哪一些规律呢？我们下面通过一些例子来初略了解一下，下面测试案例仅供参考，如有不足或肤浅的地方，敬请指教！
　　　　下面实验测试的环境主要为SQL Server 2014 SP2 （Standard Edition (64-bit)） 具体版本号为12.0.5000.0 ，如有在其它版本测试，后面会做具体说明。如下所示，我们先创建一个测试表并插入一些测试数据后，方便后面的测试工作。


IF EXISTS(SELECT 1 FROM sys.objects WHERE type='U' AND name='TEST_ESTIMATED_ROW')BEGIN    DROP TABLE TEST_ESTIMATED_ROW;END IF NOT EXISTS(SELECT 1 FROM sys.objects WHERE type='U' AND name='TEST_ESTIMATED_ROW')BEGIN        CREATE TABLE TEST_ESTIMATED_ROW        (            ID        INT,            NAME    VARCHAR(24)        )ENDGO DECLARE @Index INT =1; WHILE @Index <= 100BEGIN     INSERT INTO TEST_ESTIMATED_ROW    VALUES(10, 'id is 10');     SET @Index+=1;ENDGO DECLARE @Index INT =1; WHILE @Index <= 200BEGIN     INSERT INTO TEST_ESTIMATED_ROW    VALUES(20, 'id is 20');     SET @Index+=1;ENDGO DECLARE @Index INT =1; WHILE @Index <= 300BEGIN     INSERT INTO TEST_ESTIMATED_ROW    VALUES(30, 'id is 30');     SET @Index+=1;ENDGO  DECLARE @Index INT =1; WHILE @Index <= 400BEGIN     INSERT INTO TEST_ESTIMATED_ROW    VALUES(40, 'id is 40');     SET @Index+=1;ENDGO  DECLARE @Index INT =1; WHILE @Index <= 500BEGIN     INSERT INTO TEST_ESTIMATED_ROW    VALUES(50, 'id is 50');     SET @Index+=1;ENDGO  CREATE INDEX IX_TEST_ESTIMATED_ROW_N1 ON TEST_ESTIMATED_ROW(ID);GO
　　　　我们来看看这个表的统计信息以及直方图内容。




DBCC SHOW_STATISTICS ('dbo.TEST_ESTIMATED_ROW','IX_TEST_ESTIMATED_ROW_N1'); GO
　　
　　　　SQL Server中有两种谓词：过滤谓词和连接谓词 。 我们先来看看过滤谓词的基数估计（预估行数），测试过程，如果要保持测试的公正性或不被其他因素影响，你可以使用下面的DBCC命令来排除干扰，如下例子所示：




DBCC FREEPROCCACHE;       --从执行计划缓冲区删除所有缓存的执行计划GODBCC DROPCLEANBUFFERS;     --从缓冲池中删除所有缓存，清除缓冲区GO SELECT * FROM dbo.TEST_ESTIMATED_ROW WHERE ID = 10;GO
　　
　　　　（注意，执行时请勾选包含实际执行计划按钮）如上所示，预估行数（Estimated Number of Rows）为100,跟实际行数一致。当然你换其他值，例如20， 30， 40 ，50，其预估行数（Estimated Number of Rows）跟实际行数都是正确的（SQL SERVER 2012中测试结果也相同）。那么如果我换一个不存在的值呢？预估行数会是多少呢？




SELECT * FROM dbo.TEST_ESTIMATED_ROW WHERE ID = 4;GO
　　
　　
　　如上所示，预估行数（Estimated Number of Rows）为1. 你换其他任何不存在的值，预估行数（Estimated Number of Rows）都为1。这个跟沿用了老的基数评估：超出统计信息范围，那么老的基数评估就认为不存在，评估行数为1。很显然，对于没有超出统计信息范畴的，但是确实不存在的记录，其预估行数（Estimated Number of Rows）也是1，这个基数估计确实是合理，也是正确的。那么如果我使用变量呢？这个预估行数（Estimated Number of Rows）又会是什么值呢？　　




DECLARE @SID INT = 11;  --换任何值都可以SELECT * FROM dbo.TEST_ESTIMATED_ROW WHERE ID = @SID;GO
　　
　　
　　如上截图所示，实际执行计划的预估行数（Estimated Number of Rows）是300， 那么如何计算来的呢？ 其实你可以根据公式来计算， 如果不相信，你可以构造各种案例测试验证一下就能得到答案了.
　　
　　  [Row Sampled ]* [ALL density ] = 1500 * 0.2 = 300 也就是统计信息中抽样总行数*All Density（统计信息对象中各列的每个前缀的密度）
　　　　如果你加上OPTION(RECOMPILE)， 那么预估行数（Estimated Number of Rows）又会变成1




DECLARE @SID INT = 11;  SELECT * FROM dbo.TEST_ESTIMATED_ROW WHERE ID = @SID OPTION(RECOMPILE)GO
　　
　　
　　如果你赋予@SID值为20，并加上OPTION(RECOMPILE)时，那么预估行数（Estimated Number of Rows）就会变成EQ_ROWS的值了　　



DECLARE @SID INT = 20;  SELECT * FROM dbo.TEST_ESTIMATED_ROW WHERE ID = @SID OPTION(RECOMPILE)GO


　　　　接下来，我们修改一下SQL语句，将查询条件从等于符号改为大于符号，如下所示：




DECLARE @SID INT = 11;SELECT * FROM dbo.TEST_ESTIMATED_ROW WHERE ID > @SID;GO
　　
　　
　　如上所示，预估行数（Estimated Number of Rows）变为了450，那么这个值是怎么计算得来的呢？
　　计算公式是： [Row Sampled ] * 0.3（30%）
　　1500 *0.3= 450　　肯定会有人问，你怎么知道是 [Row Sampled ] * 0.3 呢？ 不会是你逆推的吧。 不错，这里是一个推测（网上也有不少资料都确认是0.3，权且当做计算公式中的一个常量），而且也做了不少测试，确实就是30%。例如你将@SID赋值为41，预估行数（Estimated Number of Rows）依然为450，如果你怀疑是缓存的执行计划缘故，你可以先清空缓存的执行计划，结果依然如此。根据我的测试，不管你给@SID赋予任何值，预估行数（Estimated Number of Rows）全部为450




DBCC FREEPROCCACHE;GODBCC DROPCLEANBUFFERS;GODECLARE @SID INT = 41;SELECT * FROM dbo.TEST_ESTIMATED_ROW WHERE ID > @SID;GO
　　
　　　　如果SQL加上 OPTION(RECOMPILE) ，然后@SID赋予RANGE_HI_KEY里的值，那么预估行数（Estimated Number of Rows）又是如何计算的呢？




DECLARE @SID INT = 20;SELECT * FROM dbo.TEST_ESTIMATED_ROW WHERE ID > @SID OPTION(RECOMPILE);GO
　　
　　
　　这个1200 是这样计算的，如下所示，大于20的RANGE_HI_KEY有30 ， 40， 50 ，他们对应的EQ_ROWS值相加 300+ 400 + 500 =1200， 不信你可以测试一下，将@SID赋予30，那么预估行数（Estimated Number of Rows）就会变成900.
　　
　　
　　　　那么我们再修改一下SQL查询语句，例如，我们要做一个区间查询，预估行数（Estimated Number of Rows）又会有什么变化呢？




DBCC FREEPROCCACHE;GODBCC DROPCLEANBUFFERS;GODECLARE @Min_Value INT = 20;DECLARE @Max_Value INT = 50;SELECT * FROM dbo.TEST_ESTIMATED_ROW WHERE ID > @Min_Value AND ID < @Max_ValueGO
　　
　　
　　如上所示，预估行数（Estimated Number of Rows）为246.475 这个值怎么来的呢？其实它是这样计算的:
　　
　　Selectivity of most selective predicate * Square root of (selectivity of second most selective predicate) * Total number of rows
　　SELECT 0.3*SQRT(0.3)*1500 --246.475150877325 --0.3是计算规则里面的一个常量
　　　　那么如果我在SQL Server 2012中执行该SQL语句或者使用查询跟踪标记9481来关闭新的基数评估，数据库优化器使用老的基数评估，你会发现预估行数（Estimated Number of Rows）为135了。如下所示：




DBCC FREEPROCCACHE;GO DBCC DROPCLEANBUFFERS;GO DECLARE @Min_Value INT = 20;DECLARE @Max_Value INT = 50;SELECT * FROM dbo.TEST_ESTIMATED_ROW WHERE ID > @Min_Value AND ID < @Max_ValueOPTION (QUERYTRACEON 9481);GO
　　
　　
　　这里的计算公式是
　　((Estimated number of rows for first predicate) *(Estimated number of rows for second predicate)) /Total number of rows
　　(0.3*1500)*(0.3*1500)/1500 = 0.09*1500 = 135
　　　　那么现在我们往表TEST_ESTIMATED_ROW里面插入50条记录，此时这个数据量是不会触发统计信息更新的，而此时ID=55的值超出了直方图中的RANG_HI_KY的最大值50，也就是说直方图中没有统计这些新插入的数据，那这种情形称作升序键问题（ascending key problem）。在更统计信息新前就对这些数据运行查询，就会发生此类问题。




DECLARE @Index INT =1; WHILE @Index <= 50BEGIN     INSERT INTO TEST_ESTIMATED_ROW    VALUES(55, 'id is 50');     SET @Index+=1;ENDGO　　
　　那么再来看看下面SQL的预估行数（Estimated Number of Rows），如下所示：




DBCC FREEPROCCACHE;GODBCC DROPCLEANBUFFERS;GOSELECT * FROM dbo.TEST_ESTIMATED_ROW WHERE ID = 55;GO
　　
　　　　那么预估行数（Estimated Number of Rows）为39.37 是怎么计算来的呢？其实这个问题就是http://www.cnblogs.com/wy123/p/6770258.html这篇博客里面提出的问题，先前++C++他在群里面讨论了一下。Optimizing Your Query Plans with the SQL Server 2014 Cardinality Estimator里面介绍，这种是基数估计的计算公式为 [All density] * [Rows Sampled] 。但是实际测试发现这个例子并不是如此，那么我们先来亲自测试一下白皮书文档里面的例子（注意，数据库实例是SQL Server 2014，AdventureWorks2012的兼容级别为120）,看看文档里面的例子是否正确。




SELECT [SalesOrderID], [OrderDate] FROM Sales.[SalesOrderHeader]WHERE [OrderDate] = '2005-07-01 00:00:00.000'; SELECT  .[object_id],        .[name],        .[auto_created]FROM    sys.[stats] AS sINNER JOIN sys.[stats_columns] AS [sc]        ON .[stats_id] = [sc].[stats_id] AND           .[object_id] = [sc].[object_id]WHERE   .[object_id] = OBJECT_ID('Sales.SalesOrderHeader') AND        COL_NAME(.[object_id], [sc].[column_id]) = 'OrderDate';
　　
　　可以看到OrderDate的统计信息为_WA_Sys_00000003_4B7734FF
　　　　




DBCC SHOW_STATISTICS('Sales.SalesOrderHeader', _WA_Sys_00000003_4B7734FF);　　

　　　　从上可以看到最后统计信息更新时，采集的RANGE_HI_KEY的最大值为2008-07-31 00:00:00，那么我们插入50条记录，此时这个数据量并不会触发统计信息更新。




INSERT  INTO Sales.[SalesOrderHeader] ( [RevisionNumber], [OrderDate],                                          [DueDate], [ShipDate], [Status],                                          [OnlineOrderFlag],                                          [PurchaseOrderNumber],                                          [AccountNumber], [CustomerID],                                          [SalesPersonID], [TerritoryID],                                          [BillToAddressID], [ShipToAddressID],                                          [ShipMethodID], [CreditCardID],                                          [CreditCardApprovalCode],                                          [CurrencyRateID], [SubTotal],                                          [TaxAmt], [Freight], [Comment] )VALUES  ( 3, '2014-02-02 00:00:00.000', '5/1/2014', '4/1/2014', 5, 0, 'SO43659', 'PO522145787',29825, 279, 5, 985, 985, 5, 21, 'Vi84182', NULL, 250.00,25.00, 10.00, '' );GO 50 -- INSERT 50 rows, representing very recent data, with a current OrderDate value
　　
　　然后我们开启SQL跟踪标志9481,你会发现下面SQL的预估行数为1。因为此时优化器采用老的基数估计。　　




SELECT [SalesOrderID], [OrderDate] FROM Sales.[SalesOrderHeader]WHERE [OrderDate] = '2014-02-02 00:00:00.000'OPTION (QUERYTRACEON 9481);  -- CardinalityEstimationModelVersion 70
　　 　　取消SQL跟踪标志时，数据库使用新的基数估计时，预估函数变为了27.9938




DBCC FREEPROCCACHE;GODBCC DROPCLEANBUFFERS;GOSELECT [SalesOrderID], [OrderDate] FROM Sales.[SalesOrderHeader]WHERE [OrderDate] = '2014-02-02 00:00:00.000'
　　
　　
　　
　　31465 *0.0008896797 ~=27.9937717605 ~= 27.9938 （四舍五入）
　　　　白皮书里的例子确实是如此，但是最上面那个例子，不清楚预估行数是如何计算的，尽管做了一些推测，但是在其它例子中始终不能验证。不知是这个白皮书有误还是SQL Server的基数估计做了调整， 还是说基数估计（CE)的算法远远不止这么简单？我在这个问题上纠结了两天，依然没有搞清楚！在测试、推测过程中，我发现一个新的问题：当表里面新增了数据，那么之前的测试列子结果是否还是一样呢？答案是不一样了。如下所示：




SELECT * FROM dbo.TEST_ESTIMATED_ROW WHERE ID = 10; GO
　　
　　预估函数从100变为了103.333， 这个是怎么计算来的呢？ 个人推测是这样得来的（如下所示）。
　　SELECT 1550*(100.0/1500) --~= 103.332300
　　　　也就是说升序键问题（ascending key problem）也会影响预估函数。上面都是简单SQL的预估行数（Estimated Number of Rows）的推演、实际情况中，SQL要比这个复杂得多，那么在复杂情况下，例如多个过滤谓词的情况下，基数估计又是怎样预估行数的呢？由于前面例子构造的比较简单，不适合后面的演示，那么我们就用Optimizing Your Query Plans with the SQL Server 2014 Cardinality Estimator里的例子来简单演示一下：




USE [AdventureWorks2012];GO SELECT    [AddressID],    [AddressLine1],    [AddressLine2]FROM Person.[Address]WHERE [StateProvinceID] = 9 AND      [City] = N'Burbank' AND      [PostalCode] = N'91502'OPTION (QUERYTRACEON 9481); -- CardinalityEstimationModelVersion 70GO
　　 　　如下所示，过滤谓词[StateProvinceID]、[City]、 [PostalCode]对应的统计信息分别为IX_Address_StateProvinceID、_WA_Sys_00000004_164452B1、_WA_Sys_00000006_164452B1。




SELECT  .[object_id],        .[name],        .[auto_created],        COL_NAME(.[object_id], [sc].[column_id]) AS [col_name]FROM    sys.[stats] AS sINNER JOIN sys.[stats_columns] AS [sc]        ON .[stats_id] = [sc].[stats_id] AND           .[object_id] = [sc].[object_id]WHERE   .[object_id] = OBJECT_ID('Person.Address');
　　



DBCC SHOW_STATISTICS ('Person.Address', _WA_Sys_00000004_164452B1); -- City
　　
　　
　　SELECT 196.0/19614 ~= 0.0099928
　　
　　　　




DBCC SHOW_STATISTICS ('Person.Address', IX_Address_StateProvinceID); -- StateProvinceID
　　
　　
　　SELECT 4564.0/19614 ~= 0.2326909
　　　　




DBCC SHOW_STATISTICS ('Person.Address', _WA_Sys_00000006_164452B1); -- PostalCode
　　
　　
　　SELECT 194.0/19614 ~= 0.0098908 --记录
　　
　　
　　从SQL Server 7 ~ SQL Server 2012， 如果查询条件中，两个或多个谓词使用AND联结，那么各个谓词的选择率Si的乘积将作为查询预估函数的选择率
　　(S1 * S2 * S3....*Sn)
　　(S1 * S2 * S3....*Sn) *（Rows Sampled）　　




SELECT  0.0098908 * -- PostalCode predicate selectivity        0.0099928 * -- City predicate selectivity        0.2326909 * -- StateProvinceID predicate selectivity        19614;      -- Table cardinality　　其计算结果为0.451091024458953138624 ，它低于1行。所以查询优化器使用估计的最小行数 (1)。下面看看SQL Server 2014中新的基数估计是如何计算预估行数的。




SELECT    [AddressID],    [AddressLine1],    [AddressLine2]FROM Person.[Address]WHERE [StateProvinceID] = 9 AND      [City] = N'Burbank' AND      [PostalCode] = N'91502' GO
　　
　　
　　那么新的基数估计（SQL Server 2014）的预估行数（Estimated Number of Rows）13.4692是怎么计算来的呢？ 其实它们是选择率使用下面这样一个公式，其中p0 < p1 < p2 < p3 < p4　　




SELECT  0.0098908                * -- PostalCode predicate selectivity        SQRT(0.0099928)          * -- City predicate selectivity        SQRT(SQRT(0.2326909))    * -- StateProvinceID predicate selectivity        19614; -- Table cardinality
　　
　　计算结果为13.4690212669225 ~= 13.4692 是否还是有一些差别呢？你使用下面SQL对比，就会发现，其实原因是小数点后精确位数和四舍五入导致的。具体我也不知道计算估计精确位数。
　　
　　　　那么OR Selectivity又是如何计算的，我们先来看看老的基数估计是是如何计算的，如下例子所示：




USE [AdventureWorks2012];GO SELECT    [AddressID],          [AddressLine1],          [AddressLine2]FROM Person.[Address]WHERE ([StateProvinceID] = 9 OR      [City] = N'Burbank' )AND      [PostalCode] = N'91502'OPTION (QUERYTRACEON 9481); -- CardinalityEstimationModelVersion 70
　　
　　0.0098908 -- PostalCode predicate selectivity
　　0.0099928 -- City predicate selectivity
　　0.2326909 -- StateProvinceID predicate selectivity
　　
　　计算公式：(S1 + S2) – (S1 * S2) ，那么(S1 + S2) – (S1 * S2) 计算的值为
　　(0.0099928 + 0.2326909) - (0.0099928 * 0.2326909) ~= 0.24035846637448
　　
　　然后和AND操作，我们执行SQL Server 2014以前的AND的选择性是这样计算的S1 * S2
　　0.0098908 * ((0.0099928 + 0.2326909) - (0.0099928 * 0.2326909)) ~= 0.002377337519216706784
　　最后的计算结果如下：
　　0.002377337519216706784 *19614 ~= 46.629098101916486861376 ~= 46.6296 （注意这个误差是因为精确小数位数和四舍五入造成的）
　　　　那么我们再来看看SQL Server 2014下OR Selectivity的计算公式




USE [AdventureWorks2012];GO SELECT    [AddressID],          [AddressLine1],          [AddressLine2]FROM Person.[Address]WHERE ([StateProvinceID] = 9 OR      [City] = N'Burbank' )AND      [PostalCode] = N'91502'
　　
　　
　　那么这个预估行数（Estimated Number of Rows）是怎么算出来的呢？ Paul White 的博客介绍，是通过下面这样计算来的。
　　0.0098908 -- PostalCode predicate selectivity
　　0.0099928 -- City predicate selectivity
　　0.2326909 -- StateProvinceID predicate selectivity
　　
　　A OR B = NOT （( NOT A) AND (NOT B)) 就是说A OR B 和 NOT （( NOT A) AND (NOT B)) 是等价的。
　　
　　那么就可以这么推算，最后的预估行数（Estimated Number of Rows）计算结果为94.3525， 跟结果94.3515有细微差别（这个是因为浮点数精度和四舍五入造成的）
　　SELECT 1- (1- 0.2326909)*SQRT(( 1-0.0099928)) ~= 0.236534308898679
　　SELECT 0.009891 *SQRT(1- (1- 0.2326909)*SQRT(( 1-0.0099928)) )*19614 ~= 94.3525070823501 ~= 94.3515
　　
　　上面是关于SQL Server中的基数估计（CE)如何计算预估行数的一些初步的探讨和认识，纠结我的问题到目前还没有弄清楚。虽然有点遗憾，但是在测试过程，发现去探究这些规律是一件非常有意思的事情.
　　
　　参考资料：
　　http://sqlblog.com/blogs/paul_white/archive/tags/Cardinality/default.aspx
　　http://sqlblog.com/blogs/paul_white/archive/2014/04/15/cardinality-estimation-for-disjunctive-predicates-in-2014.aspx
　　https://blogs.msdn.microsoft.com/psssql/2014/04/01/sql-server-2014s-new-cardinality-estimator-part-1/
　　https://dbafromthecold.wordpress.com/2014/11/04/cardinality-estimation-in-sql-server/
　　https://blogs.technet.microsoft.com/dataplatforminsider/2014/03/17/the-new-and-improved-cardinality-estimator-in-sql-server-2014/