数据库查询优化器：SQL 是如何被执行的

SQL 是一种声明式语言：使用者只需描述"想要什么数据"，而不需要说明"如何获取这些数据"。一条连接多张表、带有过滤和聚合条件的查询语句，并没有规定先读哪张表、使用哪个索引、用什么算法连接、按什么顺序执行。

这些决定由数据库中的查询优化器（Query Optimizer）做出。对于同一条 SQL 语句，往往存在成百上千种在逻辑上等价的执行方式，它们的执行时间可能相差几个数量级：一种方式只需几毫秒，另一种方式可能需要数小时。查询优化器的任务，就是从众多可能的执行方案中，找出代价最低的那一个。

查询优化器被认为是数据库系统中最复杂的组件之一。本文介绍一条 SQL 语句从文本到执行的完整过程、基于规则的查询重写、执行算子的实现方式、基于代价的优化与连接顺序选择、统计信息与基数估计，以及优化器的常见问题和调优方法。

一、查询处理的流程

一条 SQL 查询在数据库中通常经过以下几个阶段：

1. 解析（Parsing）：将 SQL 文本进行词法和语法分析，生成语法树。这一阶段检查语句是否符合 SQL 的语法规则；
2. 语义分析（Binding）：将语法树中的名称与数据库的元数据进行绑定：确认表和列是否存在、解析列属于哪张表、检查数据类型是否匹配、验证用户是否有相应的权限。结果是一棵带有完整语义信息的树；
3. 逻辑优化（Logical Optimization）：将查询转换为逻辑计划，并应用一系列与具体执行方式无关的等价变换规则，对查询进行重写和简化；
4. 物理优化（Physical Optimization）：为逻辑计划中的每个操作选择具体的执行算法和访问路径，并决定连接的顺序，生成物理执行计划。这一阶段通常基于代价估计进行选择；
5. 执行（Execution）：执行引擎按照物理计划，从存储中读取数据，经过各个算子的处理，最终产生结果。

其中，逻辑优化和物理优化共同构成了查询优化器的核心工作。

二、关系代数与逻辑计划

关系代数

查询优化的理论基础是关系代数。SQL 查询可以被表示为一组关系代数运算的组合，常见的运算包括：

• 选择（Selection，σ）：从关系中筛选出满足条件的元组，对应 SQL 中的 WHERE 子句；
• 投影（Projection，π）：从关系中选取特定的列，对应 SELECT 列表；
• 连接（Join，⋈）：根据连接条件，将两个关系中匹配的元组组合在一起；
• 聚合（Aggregation，γ）：按照分组键对元组进行分组，并计算聚合函数，对应 GROUP BY 和聚合函数；
• 并、交、差：集合运算；
• 排序：对应 ORDER BY。

逻辑计划树

一条查询被转换为一棵由关系代数运算构成的树，称为逻辑计划。树的叶子节点是表的扫描，内部节点是各种运算，数据从叶子向根流动，根节点产生最终结果。

例如，以下查询：

SELECT c.name, SUM(o.amount)
FROM customers c JOIN orders o ON c.id = o.customer_id
WHERE c.city = '上海' AND o.order_date >= '2026-01-01'
GROUP BY c.name;

一个直接从语句结构转换而来的逻辑计划可能是：

聚合（按 c.name 分组，计算 SUM(o.amount)）
  └─ 选择（c.city = '上海' AND o.order_date >= '2026-01-01'）
       └─ 连接（c.id = o.customer_id）
            ├─ 扫描 customers
            └─ 扫描 orders

这个计划在逻辑上是正确的，但效率很低：它先将两张表的全部数据进行连接，再进行过滤。如果 orders 表有上亿条记录，而满足条件的只有很少一部分，大量的连接工作都是白费的。

三、基于规则的查询重写

逻辑优化阶段应用一系列等价变换规则，将查询改写为在逻辑上等价但更容易高效执行的形式。这些规则通常被认为在绝大多数情况下都是有益的，因此可以无条件地应用。

谓词下推

谓词下推（Predicate Pushdown）是最重要的重写规则之一：将过滤条件尽可能地移到靠近数据源的位置，尽早减少需要处理的数据量。

在上面的例子中，c.city = '上海' 只涉及 customers 表，o.order_date >= '2026-01-01' 只涉及 orders 表，它们都可以被下推到连接之前：

聚合
  └─ 连接（c.id = o.customer_id）
       ├─ 选择（c.city = '上海'）
       │    └─ 扫描 customers
       └─ 选择（o.order_date >= '2026-01-01'）
            └─ 扫描 orders

这样，参与连接的数据量大幅减少。更进一步，谓词还可以被下推到存储层，例如在扫描时直接利用索引，或者在列式存储中跳过不满足条件的数据块。

需要注意的是，谓词下推在某些情况下是不合法的。例如，对于外连接，将作用于可能被补充为空值一侧的条件下推到连接之前，可能会改变查询的结果。

投影下推

投影下推（Projection Pushdown）将列的裁剪尽可能地提前：只读取查询实际需要的列，在每个算子中只保留后续需要使用的列。这减少了内存占用和数据传输量，在列式存储中效果尤为显著，因为未被引用的列根本不需要从磁盘读取。

常量折叠与表达式简化

与编译器类似，查询优化器也会对表达式进行简化：

• 计算常量表达式，例如将 price > 100 * 2 改写为 price > 200；
• 消除恒真或恒假的条件，例如 1 = 1 可以删除，1 = 0 意味着查询结果为空，无需执行；
• 根据已知的条件推导出新的条件。例如，如果有 a = b 且 b = 5，可以推导出 a = 5，并将这个新条件下推到 a 所在的表；
• 简化逻辑表达式，例如合并重复的条件、消除矛盾的条件。

子查询展开

SQL 允许在查询中嵌套子查询。如果按照字面含义执行，对外层查询的每一行都重新执行一次子查询，效率往往极低。

SELECT * FROM orders o
WHERE o.customer_id IN (SELECT id FROM customers WHERE city = '上海');

优化器可以将这类子查询展开为连接：

SELECT o.* FROM orders o
SEMI JOIN customers c ON o.customer_id = c.id
WHERE c.city = '上海';

这里的半连接（Semi Join）表示：对于外层的每一行，只要在子查询中存在至少一个匹配，就保留该行，且只保留一次，不会因为有多个匹配而重复。类似地，NOT IN 和 NOT EXISTS 子查询可以转换为反连接（Anti Join）。

对于相关子查询，即子查询中引用了外层查询的列，例如在 WHERE 子句中对每个客户计算其订单总额并与某个值比较，优化器可以通过去相关化，将其转换为先对内层表进行分组聚合，再与外层表连接的形式，避免逐行执行子查询。

子查询展开之后，连接的顺序和算法就可以由后续的基于代价的优化统一决定，获得更大的优化空间。

外连接化简

外连接比内连接的约束更多，限制了连接顺序的调整。如果查询中有一个作用于外连接可空一侧的条件，并且该条件会过滤掉空值，那么外连接实际上可以转换为内连接。

例如，在左外连接之后，WHERE 子句中有 o.amount > 100。对于在 orders 表中没有匹配的客户，外连接会为 o.amount 填充空值，而空值与任何值比较的结果都不为真，这些行会被过滤掉。因此，这个左外连接与内连接的结果完全相同，可以直接改写为内连接。

其他重写

• 视图展开：将查询中引用的视图替换为视图的定义，与外层查询合并后统一优化；
• 公共表达式消除：识别查询中多次出现的相同子表达式，只计算一次；
• 聚合下推：在某些条件下，将聚合操作移到连接之前，先对数据进行预聚合，减少参与连接的数据量；
• 连接消除：如果一个连接对查询结果没有影响，可以将其删除。例如，查询只使用了 orders 表的列，而与 customers 表的连接是基于外键的内连接，且 customers 表的主键保证了每个订单恰好匹配一个客户，那么这个连接可以被消除；
• 利用约束：利用主键、唯一约束、外键约束、非空约束等，推导出更多的优化机会。例如，对主键列进行 DISTINCT 是多余的；
• 分区裁剪：对于分区表，根据过滤条件确定只需要访问哪些分区，跳过其余的分区。

四、物理算子

逻辑计划描述了"做什么"，物理计划则进一步决定"怎么做"。每一个逻辑运算，都可能有多种物理实现方式，称为物理算子。

访问路径

读取一张表的数据，有多种不同的方式：

全表扫描（Sequential Scan）：按顺序读取表的全部数据。顺序读取的效率很高，适合需要读取表中大部分数据的情况。

索引扫描（Index Scan）：利用索引，例如 B+ 树，找到满足条件的记录的位置，再根据位置到表中读取完整的记录，这一步称为回表。索引扫描适合只需要读取少量数据的情况。但回表是随机读取，当需要读取的数据较多时，大量的随机读取可能比全表扫描还要慢。

仅索引扫描（Index-Only Scan）：如果查询所需的所有列都包含在索引中，就无需回表，直接从索引中读取数据，这种索引称为覆盖索引。

位图扫描（Bitmap Scan）：先通过一个或多个索引找出所有满足条件的记录位置，将它们按照在表中的物理位置排序，标记在一个位图中，然后按顺序读取表中对应的数据页。这将随机读取转化为接近顺序的读取，适合需要读取中等数量记录的情况。位图扫描还可以方便地组合多个索引的结果，对多个条件分别使用不同的索引，然后对位图求交集或并集。

选择哪种访问路径，取决于条件的选择率，即满足条件的记录占全表的比例。选择率很低时，索引扫描更优；选择率很高时，全表扫描更优；介于两者之间时，位图扫描可能是最好的选择。

连接算法

连接是查询中最耗时的操作之一，主要有三种基本算法。

嵌套循环连接（Nested Loop Join）：

对外表的每一行 r：
    对内表的每一行 s：
        如果 r 与 s 满足连接条件，输出 (r, s)

最简单的嵌套循环连接需要比较两张表的所有组合，代价与两表大小的乘积成正比，在两张表都很大时非常慢。

但如果内表的连接列上有索引，就可以对外表的每一行，通过索引直接找到内表中匹配的行，而不必扫描整个内表，这称为索引嵌套循环连接。当外表较小、内表有合适的索引时，这种方式非常高效。

嵌套循环连接还有一个优点：它可以支持任意的连接条件，包括不等值条件和复杂的表达式。

哈希连接（Hash Join）：

1. 构建阶段：选择两张表中较小的一张作为构建表，读取其全部数据，以连接列为键，在内存中建立一个哈希表；
2. 探测阶段：读取另一张表，即探测表的每一行，用其连接列的值在哈希表中查找匹配的行，输出匹配结果。

哈希连接只需要对两张表各扫描一次，代价与两表大小之和成正比，在两张大表进行等值连接时，通常是最高效的选择。

哈希连接的限制在于：只能用于等值连接；需要足够的内存来存放构建表的哈希表。当构建表太大、内存无法容纳时，需要将两张表都按照连接列的哈希值分成多个分区，写入磁盘，然后对每一对对应的分区分别进行哈希连接，称为分区哈希连接或Grace 哈希连接。这会带来额外的磁盘读写开销。

排序归并连接（Sort-Merge Join）：

1. 将两张表分别按照连接列排序；
2. 同时遍历两张排好序的表，类似于归并排序中的合并过程，找出连接列相等的行并输出。

如果两张表已经按照连接列有序，例如从连接列上的索引中读取，或者是上一个操作的输出恰好有序，排序的步骤就可以省略，排序归并连接会非常高效。此外，它的输出结果也是有序的，如果后续的操作需要按照连接列排序或分组，就可以复用这一顺序。

排序归并连接可以处理等值连接，也能较好地处理某些范围连接条件。

聚合算法

哈希聚合：建立一个以分组键为键的哈希表，遍历数据，将每一行累加到对应分组的聚合结果中。适合分组数量不太多、能够放入内存的情况。

排序聚合：先按照分组键对数据排序，然后顺序遍历，相同分组键的行是相邻的，逐组计算聚合结果。如果输入数据已经按分组键有序，排序聚合不需要额外的内存，并且输出也是有序的。

排序

当数据量能够放入内存时，使用内存排序算法；数据量太大时，使用外部排序：将数据分成多个能够放入内存的块，分别排序后写入磁盘，然后对这些有序的块进行多路归并。

对于带有 LIMIT 的排序，例如只需要前 10 条记录，可以使用堆排序，只维护一个大小为 10 的堆，避免对全部数据进行排序。

如果数据可以从一个有序的索引中按顺序读出，排序操作就可以完全避免。

五、基于代价的优化

搜索空间

在确定了可用的物理算子后，优化器需要决定：

• 每张表使用哪种访问路径；
• 多张表以什么顺序进行连接；
• 每个连接使用哪种连接算法；
• 每个聚合、排序使用哪种算法。

这些选择的组合构成了一个庞大的搜索空间。优化器需要在这个空间中搜索代价最低的执行计划。

代价模型

为了比较不同执行计划的优劣，优化器需要一个代价模型来估计每个计划的执行代价。代价通常综合考虑以下几个方面：

• I/O 代价：需要从磁盘读取多少个数据页，以及这些读取是顺序的还是随机的。在传统的基于磁盘的数据库中，I/O 往往是最主要的代价；
• CPU 代价：需要处理多少行数据、执行多少次比较和计算；
• 内存使用：算子需要多少内存，内存不足时是否需要将数据溢出到磁盘；
• 网络代价：在分布式数据库中，数据在节点之间传输的代价。

代价模型为每个物理算子定义了计算代价的公式，这些公式的关键输入是每个算子需要处理的数据量，即基数（Cardinality）。例如，一个全表扫描的代价取决于表的页数；一个索引扫描的代价取决于满足条件的行数；一个哈希连接的代价取决于两个输入的行数。

代价模型中的各项参数，例如顺序读取一个页面与随机读取一个页面的相对代价、处理一行数据的 CPU 代价，通常可以配置。在使用固态硬盘的系统中，随机读取的相对代价远低于机械硬盘，适当地调整这些参数，可以让优化器做出更符合实际硬件情况的选择。

需要强调的是，代价模型计算出的代价是一个相对的估计值，用于在不同计划之间进行比较，而不是对实际执行时间的准确预测。

连接顺序的重要性

在所有的优化决策中，连接顺序的选择往往对性能影响最大。

考虑三张表的连接：A 有 100 万行，B 有 100 万行，C 有 100 行。假设 A 与 B 连接后产生 1000 万行结果，而 A 与 C 连接后只产生 1000 行结果，再与 B 连接得到最终结果。

• 如果先连接 A 和 B，会产生一个 1000 万行的中间结果，再与 C 连接；
• 如果先连接 A 和 C，只产生 1000 行的中间结果，再与 B 连接，代价要小得多。

两种顺序的最终结果完全相同，但执行代价可能相差上千倍。好的连接顺序的核心原则是：尽早进行能够大幅减少数据量的连接，让中间结果保持尽可能小。

搜索空间的爆炸

连接顺序的可能性随着表的数量急剧增长。对于 n 张表的连接：

• 如果只考虑左深树，即每次连接都是将一张新表连接到之前的中间结果上，可能的顺序有 n! 种；
• 如果考虑浓密树，即允许两个中间结果之间进行连接，可能的连接树的数量更是远大于 n!。

5 张表的左深树有 120 种，10 张表有 360 多万种，而 15 张表则超过一万亿种。再乘以每个连接可选的算法和每张表可选的访问路径，搜索空间极其庞大，不可能逐一枚举。

动态规划

经典的连接顺序优化方法是动态规划，由早期的关系数据库研究原型系统提出，至今仍是许多数据库优化器的基础。

其基本思路是：

1. 对于每一张单独的表，找出访问它的最优方式；
2. 对于每两张表的组合，基于第一步的结果，找出连接这两张表的最优方式；
3. 对于每三张表的组合，基于前面的结果，考虑所有可能的拆分方式，即先连接其中两张表，再与第三张表连接，找出最优方式；
4. 依此类推，直到包含所有表的组合。

动态规划之所以有效，依赖于一个关键的性质：最优计划的子计划也是最优的。对于一组表的最优连接计划，其中任何一个子集的连接方式，也应该是该子集最优的连接方式。因此，可以自底向上地逐步构建，每个子集只需保留最优的计划。

但这个性质有一个例外：有时一个代价稍高的子计划，其输出结果恰好按照某个列有序，这种有趣的顺序（Interesting Order）可能让后续的排序归并连接、排序聚合或 ORDER BY 无需再进行排序，从而使整体代价更低。因此，动态规划不仅为每个子集保留代价最低的计划，还要为每种可能对后续操作有用的输出顺序，分别保留一个最优计划。

动态规划的时间复杂度仍然是指数级的，但远低于穷举。对于十几张表以内的连接，通常能够在可接受的时间内找到最优解。

启发式与随机搜索

当连接的表数量很多时，动态规划也会变得过于耗时。优化器通常会采用以下策略：

• 限制搜索空间：只考虑左深树，或者不考虑会产生笛卡尔积的连接顺序，即两张表之间没有连接条件就不直接连接；
• 贪心算法：每次选择当前代价最低的连接，逐步构建计划。速度快，但可能错过全局最优解；
• 随机化搜索：使用遗传算法、模拟退火等方法，在搜索空间中随机探索，在有限的时间内找到一个较好的计划。一些数据库在连接的表数量超过一定阈值时，会自动切换到遗传算法。

自顶向下的优化框架

除了自底向上的动态规划，另一类重要的优化器框架采用自顶向下的方式：

• 从整个查询的逻辑表达式出发，应用各种变换规则，生成大量等价的逻辑表达式和物理实现；
• 使用一种称为备忘录的数据结构，将等价的表达式归为同一个组，避免重复探索相同的子问题；
• 在搜索过程中，利用已知的代价上界进行剪枝：如果某个分支的代价已经超过了当前找到的最好计划，就不再继续探索；
• 在搜索时，可以将父节点对输出属性的要求，例如需要按某列排序，传递给子节点，子节点据此选择满足要求的实现方式。

这种框架以规则为中心，易于扩展：添加新的优化只需添加新的变换规则。许多商业数据库和开源的大数据查询引擎都采用了这一类框架。

六、统计信息与基数估计

基数估计的核心地位

代价模型的计算依赖于对每个算子输出行数的估计。基数估计（Cardinality Estimation）的准确性，直接决定了优化器能否选出好的执行计划。

研究表明，在导致优化器选出糟糕执行计划的各种原因中，基数估计的错误是最主要的一个，其影响往往远大于代价模型本身的不准确。一个数量级的基数估计错误，就可能导致优化器选择了错误的连接顺序或连接算法，使查询的执行时间相差成百上千倍。

统计信息

为了进行基数估计，数据库会收集和维护关于数据的统计信息，通常包括：

• 表级统计：表的总行数、占用的数据页数；
• 列级统计：
  • 不同值的数量（Number of Distinct Values，NDV）；
  • 空值的比例；
  • 最小值和最大值；
  • 最常见值列表及其出现频率；
  • 直方图，描述数据在取值范围上的分布；
  • 列的平均宽度；
  • 列值的物理顺序与逻辑顺序的相关性，用于估计索引扫描时回表的随机读取程度。

统计信息通常通过对表进行采样来收集，而不是扫描全表，以降低收集的开销。数据库会在数据发生较大变化后自动重新收集统计信息，也可以由管理员手动触发。

直方图

直方图是描述数据分布的主要工具。它将列的取值范围划分为若干个桶，记录每个桶中的数据情况。常见的直方图类型有：

• 等宽直方图：每个桶覆盖相同宽度的取值范围，记录落入每个桶的行数。在数据分布不均匀时，大部分数据可能集中在少数几个桶中，精度较差；
• 等深直方图：每个桶包含大致相同数量的行，记录每个桶的边界值。在数据密集的区域，桶的范围较窄，精度更高。这是数据库中更常用的形式。

结合最常见值列表，可以对高频值进行精确的估计，而直方图则用于估计其余值的分布。

选择率估计

利用统计信息，优化器可以估计各种条件的选择率：

• 等值条件 col = 常量：如果该常量在最常见值列表中，直接使用其记录的频率；否则，假设剩余的值是均匀分布的，选择率约为剩余比例除以剩余的不同值数量；
• 范围条件 col > 常量：利用直方图，估计常量在分布中所处的位置，计算大于该值的数据比例；
• 空值判断：直接使用空值的比例；
• 复杂表达式：对于优化器无法分析的条件，例如对列应用了函数，往往只能使用一个固定的默认选择率。

连接基数估计

对于等值连接 R.a = S.b，一个常用的估计公式是：

|R ⋈ S| ≈ |R| × |S| / max(NDV(R.a), NDV(S.b))

这个公式基于一个假设：较小的那个取值集合中的每个值，都能在另一个集合中找到匹配，即包含假设；并且每个值出现的频率是均匀的。对于基于外键与主键的连接，这一估计通常比较准确。但在数据分布偏斜，或者两个列的取值范围只有部分重叠时，估计可能会有很大的偏差。

独立性假设与相关性问题

当一个查询包含多个过滤条件时，例如 city = '上海' AND district = '浦东新区'，最简单的做法是假设各个条件相互独立，将它们的选择率相乘。

但现实数据中，列与列之间常常存在相关性。在上面的例子中，"浦东新区"这个区只存在于上海，满足第二个条件的行一定满足第一个条件。如果"上海"的选择率是 10%，"浦东新区"的选择率是 2%，按照独立性假设，估计的选择率是 0.2%，而实际的选择率是 2%，低估了 10 倍。

当查询包含更多相关的条件，或者经过多次连接时，这种估计误差会逐级累积和放大。在多表连接的复杂查询中，经过几层连接后，估计值与实际值相差几个数量级的情况并不罕见。

基数被严重低估时，优化器可能选择嵌套循环连接，认为外表只有很少几行；实际执行时，外表却有上百万行，嵌套循环连接需要执行上百万次内表查找，查询变得极其缓慢。

为了应对相关性问题，一些数据库支持扩展统计信息，可以针对多个列的组合收集联合的统计数据，例如多列的不同值数量、多列之间的函数依赖关系、多列组合的最常见值。管理员可以为经常一起出现在查询条件中的相关列创建这类统计信息。

其他估计方法

除了基于统计摘要的方法，还有一些其他的基数估计方法：

• 采样估计：在优化时，从表中抽取一小部分样本，直接在样本上执行过滤条件，计算实际的选择率。这种方法能够自然地处理列之间的相关性和复杂的条件，但会增加优化的时间，并且对于选择率很低的条件，样本中可能一个匹配都没有；
• 基于机器学习的估计：利用历史查询的执行反馈或数据本身训练模型，学习数据的分布和条件之间的相关性，预测查询的基数。这是近年来的一个研究热点，部分方法已经开始在实际系统中尝试应用。

七、执行模型

优化器生成执行计划后，执行引擎负责实际地运行它。执行引擎的设计也会深刻影响查询的性能。

火山模型

火山模型（Volcano Model），也称迭代器模型，是最经典的执行模型。

在这个模型中，每个物理算子都实现一个统一的接口，其中最主要的方法是"获取下一行"。执行时，从计划树的根节点开始，不断调用其"获取下一行"方法；每个算子在需要输入数据时，调用其子算子的"获取下一行"方法。数据就这样一行一行地从叶子节点被"拉"到根节点。

火山模型的优点是设计简洁、易于实现和扩展，每个算子都可以独立开发，自由组合。并且它天然支持流水线执行：数据一行一行地流过算子，不需要将中间结果全部物化。

其缺点在于性能：每处理一行数据，都需要多次虚函数调用，在处理大量数据时，这些调用的开销相当可观；同时，逐行处理的方式难以充分利用现代处理器的缓存和向量指令。

向量化执行

向量化执行是对火山模型的改进：每次调用不再返回一行数据，而是返回一批数据，通常包含数百到数千行，并且常以列式的格式组织。

每个算子以批为单位处理数据，在一个紧凑的循环中对一整列数据执行相同的操作。这带来了几方面的好处：

• 函数调用的开销被分摊到一批数据上；
• 紧凑循环中的代码和数据都有很好的缓存局部性；
• 编译器可以对这样的循环进行自动向量化，使用 SIMD 指令同时处理多个数据；
• 处理器的分支预测和流水线也能更好地工作。

向量化执行在分析型查询中能够带来数倍乃至一个数量级的性能提升，已经被广泛应用于分析型数据库和数据处理引擎中。

编译执行

另一种思路是编译执行：为每个查询的执行计划即时生成专门的代码，并将其编译为机器码执行。

生成的代码将多个算子的逻辑融合在一起，例如将扫描、过滤和聚合合并到一个紧凑的循环中，数据可以一直保存在寄存器中，在多个算子之间传递时无需物化。这消除了解释执行带来的所有额外开销，使查询的执行效率接近手写的专门代码。

编译执行的代价是编译本身需要时间。对于执行时间很短的查询，编译的开销可能超过它节省的时间。一些系统采用分层的策略：先以解释的方式开始执行，同时在后台编译，编译完成后切换到编译后的代码。

向量化执行和编译执行是现代分析型数据库提升执行效率的两条主要路线，各有优劣，也有系统尝试将两者结合。

八、自适应查询执行

无论统计信息多么完善，基数估计都不可能完全准确。当优化器基于错误的估计选择了一个糟糕的计划时，查询可能会运行得极其缓慢。自适应查询执行试图在查询执行的过程中，根据实际观察到的数据情况，动态地调整执行计划。

常见的自适应技术包括：

• 自适应连接：在执行时根据实际的输入行数，在嵌套循环连接和哈希连接之间切换。例如，先开始收集外表的数据，如果行数少于阈值，就使用索引嵌套循环连接；如果超过阈值，就切换为哈希连接；
• 运行时重新优化：在某些中间结果被完全计算出来后，根据其实际的行数和数据分布，对计划的剩余部分重新进行优化；
• 动态分区合并与倾斜处理：在分布式查询引擎中，根据中间结果各分区的实际大小，合并过小的分区以减少调度开销，或者拆分过大的分区以缓解数据倾斜；
• 运行时过滤：在哈希连接的构建阶段完成后，根据构建表中实际出现的连接键，生成一个过滤器，例如布隆过滤器或取值范围，并将其下推到探测表的扫描中，提前过滤掉不可能匹配的数据。这在星型模型的分析查询中效果尤其显著：一张小的维度表经过过滤后，可以生成一个过滤器，大幅减少需要从巨大的事实表中读取的数据量。

九、优化器的常见问题与调优

统计信息过时

当表中的数据发生了大量变化，而统计信息没有及时更新时，优化器会基于过时的信息做出错误的判断。典型的场景是：一张表在批量导入大量数据后立即被查询，此时统计信息仍然认为它是一张很小的表。

应对方法是在大批量数据变更后，手动触发统计信息的收集，并确认自动收集的机制正常工作。

参数敏感的查询

对于使用参数的预编译语句，数据库可能会缓存执行计划，以避免每次执行都重新优化。但同一个查询，在不同的参数值下，最优的计划可能完全不同。

例如，按状态查询订单，查询"已取消"的订单只返回很少的行，应该使用索引；查询"已完成"的订单返回大部分行，应该使用全表扫描。如果缓存的计划是针对某一个参数值优化的，用于其他参数值时可能效率极差。

不同的数据库对此有不同的处理方式：一些数据库在前几次执行时使用针对具体参数值的计划，如果发现通用计划的代价与之接近，才切换为通用计划；一些数据库会为不同的参数值范围缓存不同的计划；也可以通过查询提示，强制每次执行都重新优化。

优化器无法利用索引的情况

以下一些常见的写法会导致优化器无法使用索引：

• 对索引列应用函数或表达式：例如对日期列取年份后进行比较，或者对字符串列转换大小写后进行比较。索引中存储的是原始值，而不是函数计算后的值。解决方法是改写条件，使索引列保持原样，例如将取年份的条件改为一个日期范围；或者创建函数索引；
• 隐式类型转换：例如字符串类型的列与数字进行比较，数据库可能需要对每一行的列值进行转换，导致无法使用索引；
• 前导通配符的模糊匹配：以通配符开头的模式无法利用 B+ 树索引的有序性；
• 对多个列的 OR 条件：如果多个条件分别作用于不同的列，单个索引无法同时满足，优化器可能选择全表扫描。在支持位图扫描或索引合并的数据库中，可以分别使用多个索引后合并结果；也可以将查询改写为多个查询的 UNION。

查看执行计划

诊断查询性能问题的第一步，是查看优化器选择的执行计划。几乎所有的数据库都提供了相应的命令，显示计划树的结构、每个算子的类型、估计的行数和代价。

更有价值的是带有实际执行信息的执行计划：数据库实际执行查询，并在计划中同时显示每个算子估计的行数和实际的行数、实际的执行时间、读取的数据页数、内存使用情况等。

分析执行计划时，最重要的线索是：找出估计行数与实际行数相差悬殊的地方。这往往就是优化器做出错误决策的根源。沿着计划树从下往上，找到第一个出现较大估计偏差的算子，分析其原因：是统计信息过时、列之间存在相关性、条件过于复杂无法估计，还是数据分布存在严重的倾斜。

干预优化器

当优化器无法自行选出好的计划时，可以通过一些方式进行干预：

• 更新统计信息：这是最基本、最应该首先尝试的方法；
• 创建扩展统计信息：针对相关的列组合，帮助优化器更准确地估计；
• 改写查询：用更清晰、更易于优化器理解的方式表达相同的逻辑；
• 调整索引：创建合适的索引、覆盖索引或函数索引；
• 调整代价参数：使代价模型更符合实际的硬件特性；
• 使用查询提示：许多数据库允许在查询中加入提示，强制使用特定的索引、连接顺序或连接算法；
• 计划固定：一些数据库支持将一个已知良好的执行计划固定下来，防止优化器在统计信息或数据变化后选择其他计划。

查询提示和计划固定是最后的手段。它们绕过了优化器的判断，在数据分布发生变化后，原本的最优计划可能不再适合，而被固定的计划无法随之调整。使用这些手段时，需要定期复核其效果。

十、分布式查询优化

在分布式数据库和大数据查询引擎中，数据分布在多个节点上，查询优化面临额外的挑战。

数据传输的代价。 在分布式环境中，网络传输通常是最主要的代价之一。优化器需要考虑数据的分布方式，尽量减少节点之间的数据移动。

分布式连接策略。 对于两张分布在多个节点上的表进行连接，有几种常见的策略：

• 广播连接：将较小的那张表的全部数据复制到每一个节点上，与较大表在各节点的本地数据进行连接。适合一张表很小的情况；
• 重分区连接：将两张表都按照连接键的哈希值重新分布，使相同连接键的数据位于同一个节点上，然后在各节点本地进行连接。适合两张表都很大的情况，但需要大量的网络传输；
• 本地连接：如果两张表已经按照连接键以相同的方式分布，就可以直接在各节点本地进行连接，无需任何数据移动。这要求在设计表的分布方式时，就考虑到常见的连接模式。

数据倾斜。 如果某些连接键的值特别频繁，按照哈希值重新分布后，这些值对应的数据会集中在少数几个节点上，这些节点的处理时间远远超过其他节点，成为整个查询的瓶颈。应对数据倾斜的方法包括：识别出高频的倾斜值，对其采用广播等特殊的处理方式；或者将倾斜值的数据进一步拆分到多个节点上处理。

聚合下推。 在数据重新分布之前，先在各个节点本地进行部分聚合，大幅减少需要传输的数据量，再将部分聚合的结果汇总，完成最终的聚合。

结语

查询优化器是数据库声明式查询能力背后的引擎。它将一条只描述"要什么"的 SQL 语句，转化为一个精确描述"怎么做"的执行计划，并在数量庞大的可能方案中，努力选出代价最低的那一个。

这一过程融合了多个领域的技术：关系代数提供了等价变换的理论基础；基于规则的重写消除了显而易见的低效；访问路径和连接算法提供了丰富的执行手段；代价模型和动态规划在庞大的搜索空间中寻找最优解；统计信息和基数估计为所有决策提供依据；向量化和编译执行则让选定的计划尽可能高效地运行。

然而，查询优化器并非无所不能。基数估计的误差、列之间的相关性、过时的统计信息、复杂的查询结构，都可能使优化器做出错误的选择。理解优化器的工作原理，能够帮助我们读懂执行计划，找出性能问题的根源，写出更易于优化的查询，在必要时进行恰当的干预。在使用数据库时，了解优化器能做什么、不能做什么，是从会写 SQL 到写好 SQL 的重要一步。