数据库查询优化器原理

可视化演示

展示查询优化器三大核心阶段：规则优化(RBO)、代价估算(CBO)和执行计划生成，逐步切换查看SQL到执行计划的全过程。

优化器概述

你打开导航输入“公司”，APP快速返回了几条推荐路线：走高速、走环线、走地面。每条路线的预计时间不同，导航不会随便挑一条，而是把所有可行路线放进一个“候选清单”，对比后选出最快的。数据库的查询优化器做着同样的事：当一条SQL到达数据库时，先由解析器检查语法、生成逻辑查询树，接着优化器把这棵树翻译成多个等价的执行计划——每个计划都有不同的连接顺序、不同的索引选择、不同的算子组合。这些计划就是候选路线，优化器接下来的任务是从中挑出一条“最便宜”的。

那“便宜”怎么定义？导航衡量的是时间，数据库衡量的是执行代价，通常包含磁盘IO、CPU计算量等资源消耗。优化器给每个候选计划估算一个总代价，然后选择代价最小的那个，这就是基于代价优化（CBO）的朴素思想。用公式表达就是：

候选计划的数量随表数量指数增长，全部评估代价极高，因此优化器用动态规划、贪心、剪枝等手段减少评估量。这就像导航不会列出4万条小路，而是先根据经验筛掉明显不行的路线，再对剩下几条精确计算。没学过优化器原理的人往往以为SQL执行是“直接翻译”，实际上每条SQL背后，数据库默默做了一场复杂的路线比拼。优化器选得好，查询飞一般快；选得差，一条小查询也能把数据库拖垮。这正是为什么看懂执行计划是数据库性能调优的第一课。

---

基于规则的优化

老司机开车有个习惯：看到前方是学校路段就提前减速绕行，知道晚高峰高架必堵就走地面。这些经验法则不依赖精确路况，却能在大多数场景下给出“还行”的方案。基于规则的优化器（RBO）就是这样一个老司机——它准备了一整套“交通规则”，只要SQL的形状匹配某条规则，就直接改写成另一个等价但更高效的SQL，完全不需要看数据长什么样。

最经典的规则是“谓词下推”：把WHERE里的过滤条件尽量往连接之前挪。这很好理解——拼装一台电脑，如果先装机再逐个零件检测故障，发现问题早就晚了；更聪明的做法是先把有问题的零件挑出来扔掉，再拿合格零件组装。对应到SQL：先对每张单独的表做过滤，再把过滤后的小结果集做连接，中间数据量能少好几个数量级。

另一个常见规则是“投影裁剪”：SELECT里没出现的列，干脆别从磁盘读出来。就像去超市只拿购物清单上的商品，不会每个货架都逛一遍。RBO的意义在于，它提供了一批成本极低的“本能反应”——规则匹配快、不依赖统计信息，现代数据库依然用它做第一轮改写，把SQL打磨成更适合CBO估价的形状。但你也能看出它的局限：老司机的经验再丰富，也猜不透突发的封路，RBO无法感知数据分布的变化，真正讲求“数据说话了算”的，是下一节的主角。

---

统计信息收集

导航APP为什么敢预测“走环线28分钟”？因为它手里有一份城市的实时路况数据：哪条路当前平均车速多少、哪段路正在堵车、哪个路口排队时长多少。优化器的“实时路况”就是统计信息——一张表有多少行、某列的值如何分布、某个值出现多少次。没有这些信息，优化器就变成了睁眼瞎，代价估算全凭瞎猜。

数据库怎么收集这些路况？三种典型手段。第一是“表级统计”：记录表的总行数、总页数，相当于知道全城道路总里程。第二是“列级统计”，最核心的是直方图：把某列的值域划分成若干个桶，统计每个桶内的记录数。这就像把一天24小时切成若干时段，统计每个时段的平均车流量——优化器看到“价格在0到100元的商品有5万条”，就能预判“WHERE price < 100“会返回多少行。第三是”唯一值计数“：记录某列有多少个不同的值，比如订单表有100万行，但”客户ID”去重后只有5万个，这对连接操作的选择率估算至关重要。

统计信息还有个绕不开的话题：新鲜度。路况是实时变化的，数据库里的数据也在不断增删改。如果统计信息一周没更新，直方图描述的是上周的路况，这周的数据可能早就变了样。所以数据库提供自动采样（如PostgreSQL的autovacuum）和手动命令（ANALYZE）刷新统计。可这里有个微妙平衡：统计太频繁浪费资源，统计太少又不准。经验法则是对大表按变更比例自动触发重统计，而不是每次DML都重算。“统计信息是整个优化器的地基”——地基歪了，上面盖的代价模型和执行计划统统会歪。

---

代价估算模型

导航评价一条路线，会综合距离、时间、费油量、过路费多个指标，最后折算成一个总分数：分越低越好。优化器的代价模型也是类似思路，它把执行一个算子的开销拆成两大类：IO代价和CPU代价。IO代价是“读磁盘一个数据页要多久”，CPU代价是“在内存里做一行比较、哈希、聚合要花多少时间”。磁盘读比内存计算慢几个数量级，所以IO往往是主导项——就像一段路的主干道是否通畅，比你在车里多算两分钟路线重要得多。

代价模型的输入是基数估算——也就是上一节说的“预计会有多少行”。基数估算准不准，直接决定代价模型算出来的数可信不可信。举个典型场景：优化器估算某次连接后只有100行，决定用内存哈希连接；可实际上因为统计信息过期，真实数据是10万行，哈希表爆内存，查询直接退化成慢速嵌套循环。代价模型如同导航的时间预测算法：路况（统计信息）失真，预测自然失准。这也是为什么很多DBA排查慢SQL时，第一件事不是加索引，而是先看统计信息是否过期——地基不牢，地动山摇。

---

连接顺序选择

去北京玩五个景点，先逛故宫还是先爬长城，总路途差别极大。如果第一天住在故宫旁边却先跑去长城，晚上又得折返，光路上就浪费半天。多表连接也是这个道理：A、B、C三张表连接，先连A和B还是先连B和C，产生的中间结果集大小完全不同，而中间结果越小，后续的连接和计算就越轻松。

那么可能的连接顺序有多少种？n张表全排列，就是n的阶乘：

面对爆炸的搜索空间，优化器用了两把手术刀。第一把是动态规划（DP）：把大问题拆成子问题，只保留每个子集的最优方案。比如要连接{A,B,C}，DP先算出{A,B}、{A,C}、{B,C}各自的最优连接方式和结果大小，再组合成三表连接的最优解，避免重复计算。只要基数估算准确，DP能找到全局最优解，代价是内存和时间开销随表数指数增长，一般超过12张表就会力不从心。第二把是贪心算法：每次只挑当前看起来最划算的两张表连接，不做全局搜索。它快，但可能错过全局最优——就像吃自助餐，一开始猛拿甜品的人，往往到后面吃不下主菜。实际数据库如PostgreSQL在表数量少时用动态规划，超过阈值自动切换成贪心（遗传算法），正是这种“先求准、再求快”的工程权衡。

---

执行计划生成

导航选定路线后，还需要告诉你每一步怎么走：先坐地铁、再骑共享单车、最后步行200米。执行计划生成就是这个“逐路指引”阶段——把优化器选中的逻辑方案，落实成一棵可执行的物理算子树。逻辑上“连接”这个动作，物理实现可以有多种：哈希连接（先把小表建哈希表，再拿大表逐行映射，适合等值连接、数据量大时），嵌套循环连接（外层表每取一行，就在内层表扫一遍，适合内层表极小或带索引时），归并连接（先对两边排序再归并，适合两个输入已有序）。同一种逻辑操作，物理算子不同，性能天差地别，就像同城搬家，用面包车、货车还是电动车，取决于货物体积和路程。

访问路径的选择同样关键：数据从哪儿读？全表扫描是一页页从头翻到尾，索引扫描就像查字典——通过B+树从根节点“跳”到目标页。对精确匹配的高选择性查询，索引扫描只要读几个块；但如果你要返回表中25%的行，优化器反而会选择全表扫描，因为大量随机IO块远慢于顺序扫描。这正是“索引不是银弹”的根本原因。执行计划生成的另一个重要机制是计划缓存：对于重复执行的SQL，数据库把已生成的执行计划缓存起来，下次直接复用，省掉整套优化开销。就像导航APP收藏了你的常用路线，下次一键导航，不再重新规划。

至此，一条SQL的完整旅程就串起来了：解析器把SQL变成语法树，优化器用RBO做规则化简，用统计信息喂给代价模型，用DP或贪心选连接顺序，最终生成一棵包含物理算子和访问路径的执行计划树。理解了这个流程，你就拿到了数据库性能调优的“全局地图”——任何一条慢SQL，你都能顺着这条链路，判断问题究竟出在统计信息过期、连接顺序失策，还是访问路径没走对。

---

AI 应用场景

Python 演示

"""Simplified query optimizer demo:CBO enumerates all join orders and picks the cheapest one."""import itertools  class Table:    """A table only cares about its row count in this demo."""     def __init__(self, name, rows):        self.name = name        self.rows = rows  def estimate_join_rows(left_rows, right_rows, selectivity):    """Estimate rows after join (cardinality estimation)."""    return left_rows * right_rows * selectivity  def join_cost(left_rows, right_rows):    """Simplified join cost: proportional to the input product."""    return left_rows * right_rows  def optimize_join_order(tables, selectivities):    """CBO core: enumerate all permutations, pick min total cost."""    best_order = None    best_cost = float("inf")    for perm in itertools.permutations(tables):        total_cost = 0        current_rows = perm[0].rows        for i in range(1, len(perm)):            cost = join_cost(current_rows, perm[i].rows)            total_cost += cost            current_rows = estimate_join_rows(                current_rows, perm[i].rows, selectivities[i - 1]            )        if total_cost < best_cost:            best_cost = total_cost            best_order = perm    return best_order, best_cost  if __name__ == "__main__":    users = Table("users", 100000)    orders = Table("orders", 1000000)    products = Table("products", 50000)    s_uo = 0.01    s_op = 0.05    best, cost = optimize_join_order(        [users, orders, products], [s_uo, s_op]    )    names = " -> ".join(t.name for t in best)    print("best join order:", names)    print("estimated cost:", cost)

1. class Table:定义一张表，只保留行数这个关键属性，因为在优化器眼里表格大小是第一位影响决策的因素。
2. def estimate_join_rows(...)基数估算函数：连接后的行数约等于两表行数相乘再乘以选择率。
3. def join_cost(left_rows, right_rows):简化连接代价：输入行数的乘积，行数越大连接操作越昂贵。
4. for perm in itertools.permutations(tables):枚举所有表的排列组合，这就是“候选执行计划集合”。
5. current_rows = estimate_join_rows(...)每连完一次就更新“中间结果行数”，作为下一次连接代价的输入。
6. if total_cost < best_cost:贪心式对比当前排列与历史最优，最终留下的就是CBO眼中的最优顺序。

常见误区

面试题