数据库查询优化中的基数估算（Cardinality Estimation）原理解析 基数估算是数据库查询优化中代价估算（Cost Estimation）的核心环节，其目标是预测查询操作（如过滤、连接、分组等）产生的中间结果集的行数。准确的基数估算直接影响优化器选择最优执行计划的质量。 1. 基数估算的重要性 执行计划选择的基础 ：优化器通过比较不同执行计划的代价（CPU、I/O、内存等）来选择最优方案，而基数估算直接决定了这些代价计算的准确性。 示例说明 ：假设查询 SELECT * FROM users WHERE age > 30 AND city = 'Beijing' ，若优化器低估了符合条件的数据量，可能错误地选择全表扫描而非索引扫描，导致性能下降。 2. 基数估算的基本原理 2.1 统计信息收集 数据库通过定期收集统计信息来描述数据的分布特征，主要包括： 直方图（Histogram） ：将某一列的数值范围划分为多个桶（Bucket），记录每个桶内的数值频率、边界值等。例如，年龄列的直方图可能显示年龄在20-30岁的用户占比40%。 唯一值数量（Number of Distinct Values, NDV） ：估算列中不同值的个数，用于计算等值查询的选择性。 空值比例（Null Fraction） ：记录列中空值的占比。 相关性统计 ：分析多列之间的关联性（如年龄与收入的相关性），避免独立假设导致的估算偏差。 2.2 选择性（Selectivity）计算 选择性表示查询条件过滤后剩余数据占总数据的比例，是基数估算的关键： 等值查询 ： column = value 的选择性约为 1/NDV （假设数据均匀分布）。 范围查询 ： column > value 的选择性通过直方图估算。例如，若直方图显示年龄大于30的数据集中在30-40岁桶中，则根据桶内分布比例计算。 多条件组合 ： 独立假设 ：若条件独立，总选择性为各条件选择性的乘积。例如， age > 30 AND city = 'Beijing' 的选择性 ≈ Sel(age>30) × Sel(city='Beijing')。 相关性处理 ：若条件相关（如城市为北京的用户年龄普遍偏大），需通过多列统计信息或动态采样修正估算。 3. 基数估算的挑战与优化策略 3.1 数据偏斜（Data Skew） 问题 ：数据分布不均匀时，直方图可能无法准确捕捉异常值或密集区域。 解决方案 ： 使用更细粒度的直方图（如等高直方图或等宽直方图）。 对高频值（High-Frequency Values）单独记录，避免桶内平均化导致的误差。 3.2 多表连接估算 难点 ：连接操作的基数估算需考虑两表数据的关联性。例如， users JOIN orders ON users.id = orders.user_id ，若每个用户有多个订单，则结果集行数可能远大于单表行数。 方法 ： 假设引用完整性（如外键约束）：连接基数 ≈ 子表行数 × 父表匹配比例。 使用连接直方图或动态采样实时分析连接键的分布。 3.3 复杂查询的误差累积 问题 ：多条件、子查询、表达式等场景下，估算误差会逐级放大。 优化手段 ： 表达式预处理 ：先简化查询条件（如常量折叠），再估算选择性。 动态采样（Dynamic Sampling） ：对中间结果集进行小规模随机采样，校准估算值（如Oracle的动态采样机制）。 4. 实际案例：范围查询的基数估算 假设表 employees 有10000行，年龄列已收集直方图，分为5个桶： | 桶范围 | 频率 | |--------|------| | 20-30 | 20% | | 30-40 | 50% | | 40-50 | 20% | | 50-60 | 10% | 查询 WHERE age > 35 的基数估算过程： 定位年龄35所在的桶（30-40岁桶）。 假设桶内数据均匀分布，35-40岁占比为 (40-35)/(40-30) = 50% 。 该桶频率为50%，因此桶内满足条件的数据占比为 50% × 50% = 25% 。 更高年龄桶（40-50、50-60）的频率总和为30%。 总选择性 ≈ 25% + 30% = 55%，基数 ≈ 10000 × 55% = 5500行。 5. 总结 基数估算是查询优化器的“眼睛”，其准确性直接决定了执行计划的优劣。现代数据库通过结合统计信息、直方图、动态采样等技术，在效率与精度之间寻求平衡。然而，面对复杂数据分布或关联查询时，仍需依赖更高级的统计模型（如机器学习辅助估算）或人工干预（如提示语句）进一步优化。