数据库查询优化中的代价模型（Cost Model）与基数估算（Cardinality Estimation） 描述 在数据库查询优化器中，代价模型与基数估算是决定最优执行计划的核心技术。代价模型用于量化不同执行策略的资源消耗（如CPU、I/O、内存），而基数估算负责预测查询操作中间结果的元组数量。优化器通过结合二者选择总代价最小的计划。若基数估算偏差过大，可能导致优化器选择次优计划，引发性能问题。 知识点分步讲解 基数估算的基础作用 定义 ：基数估算是预测查询中每个操作符（如扫描、连接、聚合）输出行数的过程。例如，对条件 WHERE age > 30 ，需估算满足条件的行数占总行数的比例。 重要性 ：基数估算的准确性直接影响连接顺序选择、访问路径（索引扫描 vs. 全表扫描）等决策。若低估行数，可能错误选择嵌套循环连接而非哈希连接；高估则可能导致不必要的磁盘I/O。 基数估算的常用方法 统计信息依赖 ：数据库通过统计信息（如直方图、最常值MCV、不同值数量NDV）进行估算。 直方图 ：将数据按值域分桶，记录每个桶的频率分布。例如，对 age 字段的等宽直方图，若 age 取值0-100，分10个桶，则每个桶范围10岁，优化器可快速估算 age > 30 的占比。 假设独立性局限 ：当查询涉及多列条件（如 WHERE age > 30 AND city = 'Beijing' ），若缺乏多列统计信息，优化器可能简单假设列独立，导致误差累积。 采样估算 ：对大规模数据随机采样，通过样本分布推断整体基数，平衡精度与计算开销。 代价模型的组成与计算 代价因子 ：将操作成本量化为数值，通常基于I/O代价（读取页数）和CPU代价（处理元组数）。例如，一次顺序I/O代价设为1单位，一次随机I/O代价设为10单位（因磁头寻道耗时更高）。 操作符代价计算 ： 顺序扫描 ：代价 ≈ 表页数 × 顺序I/O代价 + 元组数 × CPU处理单行代价。 索引扫描 ：代价 ≈ 索引高度 × 随机I/O代价 + 满足条件的索引项数 × （随机I/O代价 + 回表CPU代价）。 连接代价示例 ： 嵌套循环连接代价 ≈ 外表扫描代价 + 外表行数 × 内表扫描代价。 哈希连接代价 ≈ 外表扫描代价 + 内表构建哈希表代价 + 连接处理代价。 代价模型与基数估算的协同流程 步骤1 ：解析查询，生成逻辑计划树（如先过滤再连接）。 步骤2 ：自底向上估算每个操作符的基数（如先估算过滤条件的输出行数，再作为连接的输入）。 步骤3 ：结合基数结果与代价模型，计算每个物理操作符（如索引扫描 vs. 全表扫描）的代价。 步骤4 ：通过动态规划或贪心算法比较不同连接顺序、操作符实现的组合代价，选择总代价最小的计划。 实际挑战与优化方向 数据倾斜处理 ：当数据分布不均时（如90%用户集中在少数城市），直方图需使用等高直方图或MCV列表精准捕捉倾斜。 关联列修正 ：若 age 与 city 存在强关联（如年轻用户多在北京），可通过扩展统计信息（Extended Statistics）记录列间相关性，减少独立性假设误差。 自适应优化 ：现代数据库（如Oracle、SQL Server）支持执行时重优化（Re-optimization），当基数估算偏差超过阈值时，动态调整后续操作计划。 总结 代价模型与基数估算是优化器的“大脑”，其精度决定了查询效率。通过结合统计信息、代价公式与优化算法，数据库能在毫秒级内从亿万级计划中选出最优解。实际应用中，需定期更新统计信息并监控执行计划，避免因数据变化导致估算失效。