SQL Server关于predicate、density、selectivity、cardinality名词浅析

在SQL Server中，我们要看懂执行计划和统计信息，我们可能需要深刻理解一些关键词，例如密度（Density）、选择性（Selectivity）、谓词（predicate）、基数(Cardinality)。前阵子，对密度和选择性的概念模糊了，刚好看了 Query Tuning Fundamentals: Density, Predicates, Selectivity, and Cardinality 这篇文章， 遂结合自己的理解、以及相关案例、分析总结一下这些专业名称。

谓词（predicate）

什么是谓词呢？谓词是取值为 TRUE、FALSE 或 UNKNOWN 的表达式。   谓词用于WHERE子句和HAVING子句的搜索条件中，还用于FROM子句的联接条件以及需要布尔值的其他构造中。官方的解释为： A predicate is an expression that evaluates to True or False 。 在WHERE条里面的常见的谓词形式有：

    1： LIKE模糊查询。

    2： BETWEEN范围查询

    3： IS NULL、IS NOT NULL判断

    4： IN - OR

    5： EXIST

    6： 等值查询

    ..............................

我们先通过例子来看看一个谓词（predicates）吧。如下所示， h.SalesOrderID > 43669 这个范围查询就是一个过滤谓词。如下所示，在实际执行计划中，右键单击 “ Clustered Index Seek"查看细节。就会看到Seek Predicates。

USE AdventureWorks2014

GO

SELECT   h .*

FROM     Sales . SalesOrderHeader h

WHERE    h . SalesOrderID > 43669 ;

SQL Server中有两种谓词：过滤谓词和连接谓词 ，还有所谓的SARG谓词和非SARG谓词概念。如上所示，上面的谓词就属于过滤谓词，而位于LEFT/INNER/RIGHT JOIN的ON后面的为连接谓词。 另外在SQL Server中还有隐式谓词（implied predicates）的概念。使用跟踪标记2324可以禁用隐式谓词。 这里对这些概念不做展开介绍。

密度（Density）

密度（Density）这个指标是用来衡量一个（或一组）列中，有多少唯一值。 它是一个比率值。 实际应用中值越小越好。不过，首先我们要区分 DBCC SHOW_STATISTICS 输出的头部信息（STAT_HEADER）中的这个Density指标和DENSITY_VECTOR中的Density指标。这两者是有所区别的，其实一般我们所说的密度（Density）指DENSITY_VECTOR中密度，而不是STAT_HEADER中的Density。

在 DBCC SHOW_STATISTICS 输出的头部信息（STAT_HEADER），这个Density指标，官方文档的介绍如下，具体参考DBCC SHOW_STATISTICS (Transact-SQL)链接：

Density：密度计算公式为 1/统计信息对象第一个键列中的所有值（不包括直方图边界值）的非重复值。   查询优化器不使用此 Density 值，显示此值的目的是为了与   SQL Server 2008   之前的版本实现向后兼容

Calculated as 1 / distinct values for all values in the first key column of the statistics object, excluding the histogram boundary values.

This Density value is not used by the query optimizer and is displayed for backward compatibility with versions before SQL Server 2008.

但是这里发现头部信息（STAT_HEADER）中Density的值计算并不像官方文档介绍的那样（具体见上面所述，这也是我很困惑的地方，个人猜测是文档有错误，一直没人更正，毕竟官方文档也不能保证100%的准确性）：

STAT_HEADER的Density的的计算公式为 ~= count(disitnct column_name)/count(*)

0.607627522644 ~= 0.6162394

注意： 上面只能是约等于，不是等于关系 。后面找了很多资料，发现其实（STAT_HEADER）中的这个Density指标的计算公式是这样：

density =

  (select distinct (column_name)

    from table_name

    where column_name not in (histogram range_hi_key values))

  /   (select count(column_name)

    from table_name

    where column_name not in (histogram range_hi_key values))

具体到这个例子来说（对于复合索引，这个字段是符合索引第一个字段），如下所示：

SELECT  COUNT(DISTINCT CustomerID)*1.0/COUNT(*)
FROM    Sales.SalesOrderHeader
WHERE   CustomerID NOT IN ( 11000, 11019, 11091, 11142, 11185, 11223, 11262,
                            11300, 11331, 11417, 11439, 11498, 11519, 11566,
                            11631, 11677, 11711, 11769, 11892, 11935, 12008,
                            12054, 12127, 12196, 12291, 12321, 12363, 12489,
                            12559, 12616, 12760, 12880, 12969, 13038, 13096,
                            13175, 13231, 13270, 13474, 13575, 13608, 13652,
                            13756, 13823, 13944, 13988, 14096, 14162, 14265,
                            14341, 14612, 14860, 14943, 15048, 15114, 15177,
                            15521, 15625, 15687, 15932, 15974, 16237, 16513,
                            16583, 16641, 16758, 16855, 16959, 17026, 17103,
                            17181, 17260, 17335, 17551, 17619, 17715, 17788,
                            17832, 17930, 18047, 18125, 18223, 18294, 18390,
                            18452, 18620, 18712, 18749, 19031, 19289, 19339,
                            19420, 19499, 19585, 20051, 20159, 20245, 20576,
                            20779, 20862, 20960, 21046, 21248, 21470, 21574,
                            21807, 21916, 22122, 22344, 22826, 23136, 23267,
                            23578, 23725, 24159, 24257, 24466, 24754, 24887,
                            25114, 25400, 25555, 25819, 25916, 25995, 26127,
                            26276, 26564, 26686, 26841, 27197, 27361, 27672,
                            28050, 28389, 28749, 28919, 29105, 29270, 29448,
                            29508, 29603, 29669, 29698, 29723, 29795, 29857,
                            29927, 29990, 30023, 30096, 30117, 30118 )

由于查询优化器不使用此Density值，所以在此略过。我们下面来看看密度向量（ DENSITY_VECTOR ） 中的密度计算。

密度向量（ DENSITY_VECTOR ）

USE AdventureWorks2014;
 
GO
 
DBCC SHOW_STATISTICS('Sales.SalesOrderHeader', 'IX_SalesOrderHeader_CustomerID') WITH  DENSITY_VECTOR

密度向量中的密度 (density): 一个比率值 , 显示在一个 ( 组 ) 列中有多少唯一值 .( 实际应用中值越小越好 )   计算公式为 1/ 统计信息对象第一个键列中的所有值（不包括直方图边界值）的非重复值

Density = 1 / Number of distinct values for column(s)

下表对指定 DENSITY_VECTOR 时结果集中所返回的列进行了说明。

USE AdventureWorks2014;
GO
DBCC SHOW_STATISTICS('Sales.SalesOrderHeader', 'IX_SalesOrderHeader_CustomerID') WITH  DENSITY_VECTOR
 
--计算字段CustomerID的Density
SELECT  1.0 / COUNT(DISTINCT CustomerID)
FROM    Sales.SalesOrderHeader;
 
--计算字段CustomerID, SalesOrderID的Density
SELECT  1.0 / COUNT(*)
FROM    ( SELECT DISTINCT
                    CustomerID ,
                    SalesOrderID
          FROM      Sales.SalesOrderHeader
        ) T;
 
 

Density = 1 / Number of distinct values for column(s)

注意，如果有多个字段，那么就按上面方法依此类推。

其实，对于密度（ density ）值很大的字段，那么可以认为这个字段的唯一值很少。 . Density values range from 0 to 1.0 。如果这个值小于 0.1 ，一般讲这个索引的选择性比较高，如果大于 0.1 ，他的选择性就不高了。

选择性（Selectivity）

什么是选择性（Selectivity）呢，选择性也是一个比率值，它反应数据集里重复的数据量的比例（多少），或者反过来来说，值唯一的数据量有多少比例。如果一个字段的数据很少有重复值，那么它的选择性就很高，高选择性意味着高唯一性。它的取值范围为0~ 1。密度与选择性成反比，密度越小，选择性的值越大。当查询优化器（query optimizer）读取 SQL 时，选择性的高低程度决定了索引是否应该用来执行该操作。通过对索引的 Statistics进行处理分析，查询优化器可以作出决定。基本上，它会权衡使用索引来遍历选择所需的记录或者对表进行扫描这两种方式。

选择性(Selectivity) = 列唯一键(Distinct_Keys)/行数(Num_Rows)的比值。

如果选择率高也就是说，大量行都可以用索引键值来唯一标识 —— 那么该SQL Server评价索引就具有高选择性，即对优化器来说也是有用的。最佳的选择性是1，即每一行都有一个唯一的索引键值。低选择性意味着表中有许多重复的键值，这样的索引将很少有用。SQL Server优化器基于索引的选择性来决定对一个查询是否使用索引。越高的选择性，SQL Server检索结果集（Result set）就越快和越有效

选择性最常用于描述谓词，官方文档 “ Query Processing Architecture Guide ” 关于选择性的一段介绍如下：

SQL Server查询优化器在估计用于从表或索引中提取信息的不同方法所需的资源成本时，依赖于统计信息的分布。   为列和索引相关字段保留分布有关的统计信息，并保存有关基础数据的密度信息。   这些信息表明特定索引或列中的值的选择性。   例如，在一个代表汽车的表中，很多汽车出自同一制造商，但每辆车都有唯一的车牌号 (VIN)。   VIN 的密度比制造商低，所以 VIN 索引比制造商索引更具选择性。   如果索引统计信息不是当前的，则查询优化器可能无法对表的当前状态做出最佳选择。   有关密度的详细信息，请参阅统计信息。

密度定义数据中存在的唯一值的分布，或给定列的重复值平均数。   密度与选择性成反比，密度越小，值的选择性越大。

基数(Cardinality)  

基数（Cardinaltiy）简单一点来说，可以被认为是查询运算符（Index Seek、Nested Loop Join，Filter....）返回的行数。查询计划中的每个运算符都具有估计的基数（优化器猜测运算符将返回的行数）和实际基数（运算符实际返回的行数）。您可以通过运行 “ SET STATISTICS PROFILE ON ” 或查看实际执行计划查询来查看。如下截图所示： Actual Number of Rows 与 Esimated Number of Rows

优化器有很多方式估算基数的算法，我们这里列举几种简单的方式，如果你想了解更多基数估计的算法。可以参考 ” SQL Server中关于基数估计如何计算预估行数的一些探讨 “ 或官方文档Optimizing Your Query Plans with the SQL Server 2014 Cardinality Estimator

如果谓词很简单，如 “ CustomerID = 11142 ” ，并且搜索值恰好是直方图RANGE_HI_KEY（直方图梯级的上限列值端），则EQ_ROWS可用于非常准确的估计基数。如下所示：

USE AdventureWorks2014
GO
SELECT  *
FROM     Sales.SalesOrderHeader
WHERE  CustomerID   =11142;

如果查询条件的值恰好落在两个步骤RANGE_HI_KEY的端点之间，那么该特定直方图步骤中的EQ_ROWS用于估计谓词选择性和操作者基数。

USE AdventureWorks2014
GO
SELECT  *
FROM     Sales.SalesOrderHeader
WHERE  CustomerID   =11222;

如下所示，Esimated Number of Rows的取值就来源于AVG_RANGE_ROWS . 因为11222位于11185 与 11223之间。所以取RANGE_HI_KEY=11223这条记录对应的AVG_RANGE_ROWS（4.32432）。

3： 如果在查询条件中使用变量（编译时未知特定搜索值），则预估行数（Esimated Number of Rows）= 密度* 采样的行数：

  [Row Sampled ]* [ALL density ]

USE AdventureWorks2014
GO
DECLARE @CustomerID INT;
SET @CustomerID=11222
SELECT  *
FROM     Sales.SalesOrderHeader
WHERE  CustomerID   =@CustomerID;

有时，查询优化器无法准确预测相关运算符返回的行数， 这个会妨碍查询优化器准确的估计查询计划的成本，从而导致选择一个较差的执行计划。基数估计错误是SQL Server中查询计划速度缓慢的最常见原因之一，因此在调优过程中，了解如何在查询计划中识别基数估计问题非常重要。

参考资料：

https://blogs.msdn.microsoft.com/bartd/2011/01/25/query-tuning-fundamentals-density-predicates-selectivity-and-cardinality/

https://docs.microsoft.com/en-us/sql/relational-databases/query-processing-architecture-guide?view=sql-server-2017

https://docs.microsoft.com/zh-cn/sql/relational-databases/statistics/statistics?view=sql-server-2017#density