基数估计

定义

基数估计(Cardinality Estimation)指查询优化器在不实际执行查询的前提下,估算每个算子(过滤、连接、聚合)输出行数的过程。行数估计是代价模型的输入,直接决定索引选择、连接算法与连接顺序。

方法

传统方法基于统计信息:利用列的非重复值数(NDV)、直方图估算选择率,再依据独立性假设(多个谓词相乘)与均匀分布假设推算结果。连接基数通常按包含性假设由两侧 NDV 推导。

难点

真实数据普遍存在列间相关性(如城市与邮编)与倾斜分布,使独立性与均匀性假设失效;多表连接时误差逐级放大,可达数量级级别,导致优化器选出灾难性计划。这被公认为查询优化中最困难的问题,论文 How Good Are Query Optimizers, Really? 对此有系统评测。

改进方向

工程上的缓解手段包括多列扩展统计、动态采样、执行反馈(根据实际行数修正);研究方向包括基于草图(sketch)的估计与机器学习基数估计(学习型优化器),后者是近年数据库学术界的热点。