关于 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 ,如有在其它版本测试,后面会做具体说明。如下所示,我们先创建一个测试表并插入一些测试数据后,方便后面的测试工作。
- IFEXISTS(SELECT1FROMsys.objectsWHEREtype='U'ANDname='TEST_ESTIMATED_ROW')
- BEGIN
- DROPTABLETEST_ESTIMATED_ROW;
- END
- IFNOTEXISTS(SELECT1FROMsys.objectsWHEREtype='U'ANDname='TEST_ESTIMATED_ROW')
- BEGIN
- CREATETABLETEST_ESTIMATED_ROW
- (
- ID INT,
- NAME VARCHAR(24)
- )
- END
- GO
- DECLARE@IndexINT=1;
- WHILE@Index<= 100
- BEGIN
- INSERTINTOTEST_ESTIMATED_ROW
- VALUES(10,'id is 10');
- SET@Index+=1;
- END
- GO
- DECLARE@IndexINT=1;
- WHILE@Index<= 200
- BEGIN
- INSERTINTOTEST_ESTIMATED_ROW
- VALUES(20,'id is 20');
- SET@Index+=1;
- END
- GO
- DECLARE@IndexINT=1;
- WHILE@Index<= 300
- BEGIN
- INSERTINTOTEST_ESTIMATED_ROW
- VALUES(30,'id is 30');
- SET@Index+=1;
- END
- GO
- DECLARE@IndexINT=1;
- WHILE@Index<= 400
- BEGIN
- INSERTINTOTEST_ESTIMATED_ROW
- VALUES(40,'id is 40');
- SET@Index+=1;
- END
- GO
- DECLARE@IndexINT=1;
- WHILE@Index<= 500
- BEGIN
- INSERTINTOTEST_ESTIMATED_ROW
- VALUES(50,'id is 50');
- SET@Index+=1;
- END
- GO
- CREATEINDEXIX_TEST_ESTIMATED_ROW_N1ONTEST_ESTIMATED_ROW(ID);
- GO
我们来看看这个表的统计信息以及直方图内容。
- DBCCSHOW_STATISTICS ('dbo.TEST_ESTIMATED_ROW','IX_TEST_ESTIMATED_ROW_N1');
- GO
SQL Server 中有两种谓词:过滤谓词和连接谓词 。 我们先来看看过滤谓词的基数估计(预估行数),测试过程,如果要保持测试的公正性或不被其他因素影响,你可以使用下面的 DBCC 命令来排除干扰,如下例子所示:
- DBCCFREEPROCCACHE; --从执行计划缓冲区删除所有缓存的执行计划
- GO
- DBCCDROPCLEANBUFFERS; --从缓冲池中删除所有缓存,清除缓冲区
- GO
- SELECT*FROMdbo.TEST_ESTIMATED_ROWWHEREID = 10;
- GO
(注意,执行时请勾选包含实际执行计划按钮)如上所示,预估行数(Estimated Number of Rows)为 100, 跟实际行数一致。当然你换其他值,例如 20, 30, 40 ,50,其预估行数(Estimated Number of Rows)跟实际行数都是正确的(SQL SERVER 2012 中测试结果也相同)。那么如果我换一个不存在的值呢?预估行数会是多少呢?
- SELECT*FROMdbo.TEST_ESTIMATED_ROWWHEREID = 4;
- GO
如上所示,预估行数(Estimated Number of Rows)为 1. 你换其他任何不存在的值,预估行数(Estimated Number of Rows)都为 1。这个跟沿用了老的基数评估:超出统计信息范围,那么老的基数评估就认为不存在,评估行数为 1。很显然,对于没有超出统计信息范畴的,但是确实不存在的记录,其预估行数(Estimated Number of Rows)也是 1,这个基数估计确实是合理,也是正确的。那么如果我使用变量呢?这个预估行数(Estimated Number of Rows)又会是什么值呢?
- DECLARE@SIDINT= 11; --换任何值都可以
- SELECT*FROMdbo.TEST_ESTIMATED_ROWWHEREID = @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@SIDINT= 11;
- SELECT*FROMdbo.TEST_ESTIMATED_ROWWHEREID = @SIDOPTION(RECOMPILE)
- GO
如果你赋予 @SID 值为 20,并加上 OPTION(RECOMPILE) 时,那么预估行数(Estimated Number of Rows)就会变成 EQ_ROWS 的值了
- DECLARE@SIDINT= 20;
- SELECT*FROMdbo.TEST_ESTIMATED_ROWWHEREID = @SIDOPTION(RECOMPILE)
- GO
接下来,我们修改一下 SQL 语句,将查询条件从等于符号改为大于符号,如下所示:
- DECLARE@SIDINT= 11;
- SELECT*FROMdbo.TEST_ESTIMATED_ROWWHEREID > @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
- DBCCFREEPROCCACHE;
- GO
- DBCCDROPCLEANBUFFERS;
- GO
- DECLARE@SIDINT= 41;
- SELECT*FROMdbo.TEST_ESTIMATED_ROWWHEREID > @SID;
- GO
如果 SQL 加上 OPTION(RECOMPILE) ,然后 @SID 赋予 RANGE_HI_KEY 里的值,那么预估行数(Estimated Number of Rows)又是如何计算的呢?
- DECLARE@SIDINT= 20;
- SELECT*FROMdbo.TEST_ESTIMATED_ROWWHEREID > @SIDOPTION(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)又会有什么变化呢?
- DBCCFREEPROCCACHE;
- GO
- DBCCDROPCLEANBUFFERS;
- GO
- DECLARE@Min_ValueINT= 20;
- DECLARE@Max_ValueINT= 50;
- SELECT*FROMdbo.TEST_ESTIMATED_ROWWHEREID > @Min_ValueANDID < @Max_Value
- GO
如上所示,预估行数(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 了。如下所示:
- DBCCFREEPROCCACHE;
- GO
- DBCCDROPCLEANBUFFERS;
- GO
- DECLARE@Min_ValueINT= 20;
- DECLARE@Max_ValueINT= 50;
- SELECT*FROMdbo.TEST_ESTIMATED_ROWWHEREID > @Min_ValueANDID < @Max_Value
- OPTION(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@IndexINT=1;
- WHILE@Index<= 50
- BEGIN
- INSERTINTOTEST_ESTIMATED_ROW
- VALUES(55,'id is 50');
- SET@Index+=1;
- END
- GO
那么再来看看下面 SQL 的预估行数(Estimated Number of Rows),如下所示:
- DBCCFREEPROCCACHE;
- GO
- DBCCDROPCLEANBUFFERS;
- GO
- SELECT*FROMdbo.TEST_ESTIMATED_ROWWHEREID = 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]
- FROMSales.[SalesOrderHeader]
- WHERE[OrderDate] ='2005-07-01 00:00:00.000';
- SELECT [s]. [object_id],
- [s]. [name],
- [s].[auto_created]
- FROMsys.[stats]ASs
- INNERJOINsys.[stats_columns]AS[sc]
- ON[s].[stats_id] = [sc].[stats_id]AND
- [s].[object_id] = [sc].[object_id]
- WHERE[s].[object_id] = OBJECT_ID('Sales.SalesOrderHeader')AND
- COL_NAME([s].[object_id], [sc].[column_id]) ='OrderDate';
可以看到 OrderDate 的统计信息为_WA_Sys_00000003_4B7734FF
- DBCCSHOW_STATISTICS('Sales.SalesOrderHeader', _WA_Sys_00000003_4B7734FF);
从上可以看到最后统计信息更新时,采集的 RANGE_HI_KEY 的最大值为 2008-07-31 00:00:00,那么我们插入 50 条记录,此时这个数据量并不会触发统计信息更新。
- INSERT INTOSales.[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]
- FROMSales.[SalesOrderHeader]
- WHERE[OrderDate] ='2014-02-02 00:00:00.000'
- OPTION(QUERYTRACEON 9481); -- CardinalityEstimationModelVersion 70
取消 SQL 跟踪标志时,数据库使用新的基数估计时,预估函数变为了 27.9938
- DBCCFREEPROCCACHE;
- GO
- DBCCDROPCLEANBUFFERS;
- GO
- SELECT[SalesOrderID],
- [OrderDate]
- FROMSales.[SalesOrderHeader]
- WHERE[OrderDate] ='2014-02-02 00:00:00.000'
31465 *0.0008896797 ~=27.9937717605 ~= 27.9938 (四舍五入)
白皮书里的例子确实是如此,但是最上面那个例子,不清楚预估行数是如何计算的,尽管做了一些推测,但是在其它例子中始终不能验证。不知是这个白皮书有误还是 SQL Server 的基数估计做了调整, 还是说基数估计(CE) 的算法远远不止这么简单?我在这个问题上纠结了两天,依然没有搞清楚!在测试、推测过程中,我发现一个新的问题:当表里面新增了数据,那么之前的测试列子结果是否还是一样呢?答案是不一样了。如下所示:
- SELECT*FROMdbo.TEST_ESTIMATED_ROWWHEREID = 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]
- FROMPerson.[Address]
- WHERE[StateProvinceID] = 9AND
- [City] = N'Burbank'AND
- [PostalCode] = N'91502'
- OPTION(QUERYTRACEON 9481); -- CardinalityEstimationModelVersion 70
- GO
如下所示,过滤谓词 [StateProvinceID]、[City]、 [PostalCode] 对应的统计信息分别为 IX_Address_StateProvinceID、_WA_Sys_00000004_164452B1、_WA_Sys_00000006_164452B1。
- SELECT [s]. [object_id],
- [s]. [name],
- [s]. [auto_created],
- COL_NAME([s].[object_id], [sc].[column_id])AS[col_name]
- FROMsys.[stats]ASs
- INNERJOINsys.[stats_columns]AS[sc]
- ON[s].[stats_id] = [sc].[stats_id]AND
- [s].[object_id] = [sc].[object_id]
- WHERE[s].[object_id] = OBJECT_ID('Person.Address');
- DBCCSHOW_STATISTICS ('Person.Address', _WA_Sys_00000004_164452B1); -- City
SELECT 196.0/19614 ~= 0.0099928
- DBCCSHOW_STATISTICS ('Person.Address', IX_Address_StateProvinceID); -- StateProvinceID
SELECT 4564.0/19614 ~= 0.2326909
- DBCCSHOW_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)
- SELECT0.0098908 * -- PostalCode predicate selectivity
- 0.0099928 * -- City predicate selectivity
- 0.2326909 * -- StateProvinceID predicate selectivity
- 19614; --Tablecardinality
其计算结果为 0.451091024458953138624 ,它低于 1 行。所以查询优化器使用估计的最小行数 (1)。下面看看 SQL Server 2014 中新的基数估计是如何计算预估行数的。
- SELECT [AddressID],
- [AddressLine1],
- [AddressLine2]
- FROMPerson.[Address]
- WHERE[StateProvinceID] = 9AND
- [City] = N'Burbank'AND
- [PostalCode] = N'91502'
- GO
那么新的基数估计(SQL Server 2014)的预估行数(Estimated Number of Rows)13.4692 是怎么计算来的呢? 其实它们是选择率使用下面这样一个公式,其中 p0 < p1 < p2 < p3 < p4
- SELECT0.0098908 * -- PostalCode predicate selectivity
- SQRT(0.0099928) * -- City predicate selectivity
- SQRT(SQRT(0.2326909)) * -- StateProvinceID predicate selectivity
- 19614; --Tablecardinality
计算结果为 13.4690212669225 ~= 13.4692 是否还是有一些差别呢?你使用下面 SQL 对比,就会发现,其实原因是小数点后精确位数和四舍五入导致的。具体我也不知道计算估计精确位数。
那么 OR Selectivity 又是如何计算的,我们先来看看老的基数估计是是如何计算的,如下例子所示:
- USE[AdventureWorks2012];
- GO
- SELECT [AddressID],
- [AddressLine1],
- [AddressLine2]
- FROMPerson.[Address]
- WHERE([StateProvinceID] = 9OR
- [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]
- FROMPerson.[Address]
- WHERE([StateProvinceID] = 9OR
- [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/
来源: http://www.cnblogs.com/kerrycode/p/6794534.html