本文共 1314 字，大约阅读时间需要 4 分钟。

在 TiDB 中，物理优化阶段需要对逻辑查询计划中的算子进行代价估算并选择代价最低的路径。统计信息是这一过程的核心模块，本文将从基础概念、收集机制以及代价估算方面进行详细介绍。

表态统计信息的核心作用

统计信息的主要任务是通过概括实际数据的特征，为查询代价估算提供依据。优化器并不需要确切的代价值，只需一个可靠的估算值即可。因此，数据库通常维护一系列简化的数据特征，如总行数、列的等深直方图、Count-Min Sketch 等。

等深直方图与Count-Min Sketch

1. 等深直方图

等深直方图是数据分布描述的有效工具，通过将数据分为若干区间（桶），并记录每个桶内的记录数。TiDB采用等深直方图，确保每个桶内的记录数尽可能接近，从而在最坏情况下也能保证较低的误差。例如，对于数据集 {1.6, 1.9, 1.9, 2.0, 2.4, 2.6, 2.7, 2.7, 2.8, 2.9, 3.4, 3.5}，分为4个桶：[1.6, 1.9]、[2.0, 2.6]、[2.7, 2.8] 和 [2.9, 3.5]，每个桶内的记录数均为3。

2. Count-Min Sketch

Count-Min Sketch 是一种高效处理等值查询和 Join 大小估计的数据结构，通过 hash 函数将数据映射到若干列中，计数数组记录每个值的出现次数。在查询时，利用 d 行的最小值作为估计值。Count-Min Sketch 在等值查询、Join 估算等方面具有强大的准确性。

统计信息的创建

列直方图

在 TiDB 中，直方图的创建采用抽样算法。通过抽样后排序，建立直方图。样本池抽样至一定大小，确保样本代表性。排序后遍历值，按桶规则将其归类，计算桶深。

索引直方图

索引直方图的创建依赖于数据有序性。确定桶数后，依次插入数据，如桶深不够时扩大桶深并合并相邻桶。合并时处理边界问题，确保各值只在一个桶中。

统计信息的维护

动态更新机制

在 TiDB 2.1 中，引入动态更新机制。通过查询反馈调整统计信息，如桶高、边界和 Count-Min Sketch。方法包括误差假设和精确计算，确保统计信息适应查询需求。

桶高与边界调整

桶高更新基于误差分布，合并或分裂桶以优化误差。分裂时根据查询点密度选择边界，合并时处理误差贡献。Count-Min Sketch 更新简单地根据估计误差进行调整。

统计信息的使用

范围查询估算

等深直方图用于范围查询，如区间 [1.7, 2.8] 蝉后落入两个完全覆盖桶以及部分覆盖桶。通过连续均匀假设估算部分覆盖桶内的记录数。这一数学方法也可用于非数值字段。

等值查询

Count-Min Sketch 提供精确估算，文献提出的 Count-Mean-Min 检索方法通过中位数估计值出现次数，降低估算误差。这种方法兼顾快速查询和准确性。

多列查询

selectivity.go 函数处理多列查询，将查询条件分组，独立估算后相乘，如使用贪心算法选择覆盖最大过滤条件的列或索引，确保最优过滤效率。

这些优化步骤共同确保 TiDB在高度并发环境下的高效运行，为优化器选择最佳查询路径提供可靠统计基础。