数据库查询优化中的索引选择与代价估算原理解析
字数 3458 2025-12-09 03:14:51

数据库查询优化中的索引选择与代价估算原理解析

这是一个数据库查询优化中的核心问题：当查询涉及多个索引时，优化器如何选择“最优”的索引来执行查询？其决策过程紧密依赖于代价估算模型。

一、 问题描述与背景

当你执行一条SQL查询，比如 SELECT * FROM orders WHERE customer_id = 100 AND order_date > '2023-01-01'，并且表 orders 在 customer_id 和 order_date 列上都有单列索引时，数据库优化器面临几个选择：

  1. 使用 customer_id 索引。
  2. 使用 order_date 索引。
  3. 同时使用两个索引进行“索引合并”（如果支持）。
  4. 不使用任何索引，进行全表扫描。

核心问题：优化器如何做出这个选择？答案是：它需要估算每种执行计划的执行代价，然后选择代价最小的一个。而估算代价的基础，就是关于数据分布的统计信息。

二、 核心概念：统计信息

优化器进行代价估算的依据并不是实时扫描整个表，而是依赖于预先收集并维护的统计信息。对于表和索引，关键统计信息包括：

  1. 表的基数：表中的总行数（num_rows）。
  2. 列的基数：该列上不同值的数量（num_distinct）。这直接影响选择率估算。例如，customer_id 如果唯一值很多，那么 customer_id = 100 筛选出的行数预期就很少。
  3. 直方图：对于数据分布不均匀的列（如 order_date，新订单远多于旧订单），仅有基数不够。直方图将列值范围划分为多个“桶”，记录每个桶中的最小值、最大值、行数以及不同值数量，用于更精确地估算范围查询（>， <， BETWEEN）的选择率。
  4. 索引统计信息：包括索引的层级数（height）、叶子块数量（leaf_blocks）等，用于估算索引扫描的I/O成本。

三、 代价估算的循序渐进过程

我们以查询 SELECT * FROM orders WHERE customer_id = 100 AND order_date > '2023-01-01' 为例，假设两个列都有单列索引，且不采用索引合并。

步骤1：计算每个过滤条件的选择率

选择率（selectivity）是指一个条件能筛选出表中多大比例的行。它是一个介于0和1之间的小数。

  • 对于等值条件 customer_id = 100：

    • 如果 customer_id 列是唯一的，那么选择率 = 1 / num_distinct(customer_id)。
    • 如果非唯一，但统计信息收集了该值频次，则用频次/总行数。否则，常用简化模型：1 / num_distinct(customer_id)。
    • 举例：假设 num_distinct(customer_id) = 10000，则 sel_customer = 1 / 10000 = 0.0001。

  • 对于范围条件 order_date > '2023-01-01'：

    • 需要借助直方图。优化器会查找直方图，确定 '2023-01-01' 这个值落在哪个桶里，并估算出大于该值的行数比例。
    • 简化估算：如果没有直方图，优化器可能使用一个经验值（如1/3或1/2），但这很不精确。
    • 举例：假设通过直方图估算出 sel_date = 0.05（即5%的数据符合条件）。

步骤2：估算组合条件的选择率与结果集行数

当条件用 AND 连接时，优化器通常假设它们是独立的（这是一个关键假设，有时不符合现实）。

  • 组合选择率 sel_combined = sel_customer * sel_date = 0.0001 * 0.05 = 0.000005。
  • 预计结果集行数 cardinality = num_rows * sel_combined。假设 num_rows = 1,000,000，则 cardinality = 1,000,000 * 0.000005 = 5 行。

步骤3：估算不同访问路径的代价

代价模型通常考虑 I/O成本（从磁盘读取数据块）和 CPU成本（处理行、比较数据）。为简化，我们聚焦于I/O。

  • 路径A：使用 customer_id 索引

    1. 索引范围扫描：从B+树索引根节点走到叶子节点，找到 customer_id = 100 的所有条目。假设 customer_id 索引高度为3，需要读3个索引块。
    2. 回表：索引条目包含对应数据行的物理地址（ROWID）。每找到一条索引条目，就需要根据ROWID去读取对应的表数据块。我们预计有 num_rows * sel_customer = 1,000,000 * 0.0001 = 100 行符合 customer_id = 100。
    3. 过滤：从表中读出这100行后，需要在内存中应用第二个条件 order_date > '2023-01-01' 进行过滤，最终得到约5行。
    4. 总代价估算：假设每次回表读一个数据块（最理想情况，且不重复读同一块），代价 ≈ 索引高度(3) + 回表次数(100) = 103次I/O。

  • 路径B：使用 order_date 索引

    1. 索引范围扫描：在 order_date 索引上找到所有 > '2023-01-01' 的条目。假设索引高度为3，且范围扫描需要读取多个叶子块。估算符合 order_date 条件的行数为 1,000,000 * 0.05 = 50,000。
    2. 回表：需要对这5万行进行回表读取。
    3. 过滤：回表后，在内存中用 customer_id = 100 过滤，得到最终5行。
    4. 总代价估算：远高于路径A，因为回表次数高达5万次。

  • 路径C：全表扫描

    1. 顺序读取：需要读取整个表的所有数据块。假设表有10,000个数据块。
    2. 过滤：在内存中同时用两个条件过滤所有100万行。
    3. 总代价估算：10,000次I/O。

步骤4：比较并选择

对比三种路径的估算代价：

  • 路径A（customer_id 索引）：~103次I/O
  • 路径B（order_date 索引）：~50,000次I/O
  • 路径C（全表扫描）：10,000次I/O

优化器会认为 路径A的代价最低，因此很可能选择使用 customer_id 索引的执行计划。

四、 进阶考量与复杂性

  1. 相关性误区：我们假设 customer_id 和 order_date 独立。但如果老客户（特定ID）总是在最近日期下单，二者强相关，那么实际符合条件的行数可能远多于5行（可能接近100行）。这会导致优化器严重低估代价（基数估计错误），从而可能选择错误的计划。
  2. 复合索引：如果存在 (customer_id， order_date) 复合索引，优化器会评估这个选项。对于查询 WHERE customer_id = 100 AND order_date > ...，该复合索引可以直接在索引内部完成两个条件的过滤（customer_id 用于精确查找，order_date 用于范围过滤），无需回表过滤，且回表次数就是最终结果行数（约5次），代价可能低至 索引高度(3) + 回表(5) = 8次I/O，成为最优选择。
  3. 代价模型参数：数据库允许配置一些成本常量，如一次随机I/O（如回表）与一次顺序I/O（如全表扫描）的成本比值。调整这些参数会影响优化器的决策。
  4. 动态采样与实时统计：对于某些复杂查询或临时表，优化器可能在解析时动态读取一小部分数据块来获得更准确的即时统计信息，以校正估算。

总结

索引选择的本质是一个基于代价估算的决策过程。优化器通过：

  1. 收集统计信息：了解数据分布。
  2. 估算选择率：预测每个条件能过滤多少数据。
  3. 估算基数：预测中间结果和最终结果的大小。
  4. 计算不同访问路径的I/O与CPU成本。
  5. 选择估算代价最低的路径作为执行计划。

理解这个过程，对于解读复杂查询的执行计划、诊断“为什么没用上我建的索引”这类性能问题至关重要。当优化器选择错误时，通常是因为统计信息过时、数据相关性未被捕捉或代价模型参数不合理，这为我们提供了明确的调优方向。

数据库查询优化中的索引选择与代价估算原理解析 这是一个数据库查询优化中的核心问题：当查询涉及多个索引时，优化器如何选择“最优”的索引来执行查询？其决策过程紧密依赖于代价估算模型。 一、 问题描述与背景 当你执行一条SQL查询，比如 SELECT * FROM orders WHERE customer_id = 100 AND order_date > '2023-01-01' ，并且表 orders 在 customer_id 和 order_date 列上都有单列索引时，数据库优化器面临几个选择： 使用 customer_id 索引。 使用 order_date 索引。 同时使用两个索引进行“索引合并”（如果支持）。 不使用任何索引，进行全表扫描。 核心问题 ：优化器如何做出这个选择？答案是：它需要估算每种执行计划的 执行代价 ，然后选择代价最小的一个。而估算代价的基础，就是关于数据分布的 统计信息 。 二、 核心概念：统计信息 优化器进行代价估算的依据并不是实时扫描整个表，而是依赖于预先收集并维护的 统计信息 。对于表和索引，关键统计信息包括： 表的基数 ：表中的总行数（ num_rows ）。 列的基数 ：该列上不同值的数量（ num_distinct ）。这直接影响选择率估算。例如， customer_id 如果唯一值很多，那么 customer_id = 100 筛选出的行数预期就很少。 直方图 ：对于数据分布不均匀的列（如 order_date ，新订单远多于旧订单），仅有基数不够。直方图将列值范围划分为多个“桶”，记录每个桶中的最小值、最大值、行数以及不同值数量，用于更精确地估算范围查询（ > ， < ， BETWEEN ）的选择率。 索引统计信息 ：包括索引的层级数（ height ）、叶子块数量（ leaf_blocks ）等，用于估算索引扫描的I/O成本。 三、 代价估算的循序渐进过程 我们以查询 SELECT * FROM orders WHERE customer_id = 100 AND order_date > '2023-01-01' 为例，假设两个列都有单列索引，且不采用索引合并。 步骤1：计算每个过滤条件的选择率 选择率（ selectivity ）是指一个条件能筛选出表中多大比例的行。它是一个介于0和1之间的小数。 对于等值条件 customer_id = 100 ： 如果 customer_id 列是唯一的，那么选择率 = 1 / num_distinct(customer_id) 。 如果非唯一，但统计信息收集了该值频次，则用频次/总行数。否则，常用简化模型： 1 / num_distinct(customer_id) 。 举例 ：假设 num_distinct(customer_id) = 10000 ，则 sel_customer = 1 / 10000 = 0.0001 。 对于范围条件 order_date > '2023-01-01' ： 需要借助 直方图 。优化器会查找直方图，确定 '2023-01-01' 这个值落在哪个桶里，并估算出大于该值的行数比例。 简化估算 ：如果没有直方图，优化器可能使用一个经验值（如1/3或1/2），但这很不精确。 举例 ：假设通过直方图估算出 sel_date = 0.05 （即5%的数据符合条件）。 步骤2：估算组合条件的选择率与结果集行数 当条件用 AND 连接时，优化器通常假设它们是 独立的 （这是一个关键假设，有时不符合现实）。 组合选择率 sel_combined = sel_customer * sel_date = 0.0001 * 0.05 = 0.000005 。 预计结果集行数 cardinality = num_rows * sel_combined 。假设 num_rows = 1,000,000 ，则 cardinality = 1,000,000 * 0.000005 = 5 行。 步骤3：估算不同访问路径的代价 代价模型通常考虑 I/O成本 （从磁盘读取数据块）和 CPU成本 （处理行、比较数据）。为简化，我们聚焦于I/O。 路径A：使用 customer_id 索引 索引范围扫描 ：从B+树索引根节点走到叶子节点，找到 customer_id = 100 的所有条目。假设 customer_id 索引高度为3，需要读3个索引块。 回表 ：索引条目包含对应数据行的物理地址（ROWID）。每找到一条索引条目，就需要根据ROWID去读取对应的 表数据块 。我们预计有 num_rows * sel_customer = 1,000,000 * 0.0001 = 100 行符合 customer_id = 100 。 过滤 ：从表中读出这100行后，需要在内存中应用第二个条件 order_date > '2023-01-01' 进行过滤，最终得到约5行。 总代价估算 ：假设每次回表读一个数据块（最理想情况，且不重复读同一块），代价 ≈ 索引高度(3) + 回表次数(100) = 103次I/O 。 路径B：使用 order_date 索引 索引范围扫描 ：在 order_date 索引上找到所有 > '2023-01-01' 的条目。假设索引高度为3，且范围扫描需要读取多个叶子块。估算符合 order_date 条件的行数为 1,000,000 * 0.05 = 50,000 。 回表 ：需要对这5万行进行回表读取。 过滤 ：回表后，在内存中用 customer_id = 100 过滤，得到最终5行。 总代价估算 ：远高于路径A，因为回表次数高达5万次。 路径C：全表扫描 顺序读取 ：需要读取整个表的所有数据块。假设表有10,000个数据块。 过滤 ：在内存中同时用两个条件过滤所有100万行。 总代价估算 ： 10,000次I/O 。 步骤4：比较并选择 对比三种路径的估算代价： 路径A（ customer_id 索引）：~103次I/O 路径B（ order_date 索引）：~50,000次I/O 路径C（全表扫描）：10,000次I/O 优化器会认为 路径A的代价最低 ，因此很可能选择使用 customer_id 索引的执行计划。 四、 进阶考量与复杂性 相关性误区 ：我们假设 customer_id 和 order_date 独立。但如果老客户（特定ID）总是在最近日期下单，二者强相关，那么实际符合条件的行数可能远多于5行（可能接近100行）。这会导致优化器严重低估代价（ 基数估计错误 ），从而可能选择错误的计划。 复合索引 ：如果存在 (customer_id， order_date) 复合索引，优化器会评估这个选项。对于查询 WHERE customer_id = 100 AND order_date > ... ，该复合索引可以直接在索引内部完成两个条件的过滤（ customer_id 用于精确查找， order_date 用于范围过滤），无需回表过滤，且回表次数就是最终结果行数（约5次），代价可能低至 索引高度(3) + 回表(5) = 8次I/O ，成为最优选择。 代价模型参数 ：数据库允许配置一些成本常量，如一次随机I/O（如回表）与一次顺序I/O（如全表扫描）的成本比值。调整这些参数会影响优化器的决策。 动态采样与实时统计 ：对于某些复杂查询或临时表，优化器可能在解析时动态读取一小部分数据块来获得更准确的即时统计信息，以校正估算。 总结 索引选择的本质是一个基于代价估算的决策过程 。优化器通过： 收集统计信息 ：了解数据分布。 估算选择率 ：预测每个条件能过滤多少数据。 估算基数 ：预测中间结果和最终结果的大小。 计算不同访问路径的I/O与CPU成本 。 选择估算代价最低的路径 作为执行计划。 理解这个过程，对于解读复杂查询的执行计划、诊断“为什么没用上我建的索引”这类性能问题至关重要。当优化器选择错误时，通常是因为统计信息过时、数据相关性未被捕捉或代价模型参数不合理，这为我们提供了明确的调优方向。