查询优化：让同一条查询走更短的路

一条 SQL 只说明“想要什么”，通常没有规定“先读哪张表、用哪个索引、按什么顺序连接”。这给数据库留下了优化空间，也带来一个难题：同一个结果往往对应成千上万条执行路径，而这些路径的开销可能相差几个数量级。

我们用“星河零售”的订单分析贯穿全文。业务人员要查询最近 30 天华东地区、已支付、电子商品类目的高金额订单，涉及 customer、orders、order_item、product 和 category 五张表。数据规模并不对称：订单有数亿行，订单明细更多，类目表却只有几百行。优化器要在真正执行前回答一连串问题：条件能否提前过滤？五张表先连哪两张？顺序扫描还是索引扫描？哈希连接、归并连接还是索引嵌套循环？中间结果要流水传递，还是落盘物化？

图：优化器把 SQL 转成逻辑表达式，再联合统计信息、代价模型和搜索算法选出可执行的物理计划。

优化器接收什么，又交付什么

从逻辑意图到物理动作

解析器先完成名称绑定、类型检查和权限检查，并把 SQL 转成逻辑算子树。逻辑树描述选择、投影、连接、分组等关系运算，却不决定这些运算怎样落到存储层。优化器的输入至少包括四类信息：

优化器的输出是执行计划。它不仅标出算子顺序，还要给每个逻辑算子指定物理实现。例如，orders 可以用全表顺序扫描，也可以按 (region, status, paid_at) 做范围索引扫描；连接可以用哈希连接、归并连接或嵌套循环连接；算子之间可以流水传递，也可以先把结果写成临时数据再交给下一步。

逻辑等价不代表执行代价相同

假设先把 orders 与 order_item 全量连接，再过滤地区与时间，中间结果可能接近订单明细总量。若先从订单表取出“华东、已支付、最近 30 天”的小集合，再连接明细，后续算子读取和比较的行数都会下降。两条表达式返回相同结果，处理的数据量却不同。

计划的优劣也不能只看最终行数。一个能立即吐出前几行的流水计划，首行延迟可能很低；另一个计划需要先排序或建立哈希表，虽然总成本较低，却有更高的启动成本。交互式查询、报表导出和批处理可能因此偏好不同的计划。

生成、标注、估价是交织进行的

优化过程可以概括为三类动作：生成逻辑等价表达式，为表达式标注物理算法，估算并比较计划代价。实际实现不会先生成全部表达式再统一估价，因为候选数量很快就会失控。优化器通常边生成边估价，把重复子问题放进备忘录，并尽早剪掉已经不可能胜出的候选。

等价变换怎样扩展候选计划

等价的严格含义

若两个关系代数表达式在每个满足模式约束的合法数据库实例上都产生相同的元组集合，就可以在集合语义下认为它们等价。SQL 通常保留重复行，因此真正做 SQL 重写时还要检查重复项的数量是否一致。一个在集合语义下成立的改写，不一定能原样用于多重集语义。

等价规则是双向的语义规则。它说的是“左右两种写法结果相同”，不直接承诺右边更快。优化器可以用规则打开新的计划机会，再由统计信息和代价模型判断哪种形式值得保留。

常用关系代数规则

合取选择可以拆成级联选择，多个选择也可以交换顺序：

连续投影中，如果外层属性集合包含关系满足所需条件，中间冗余投影可以消除：

选择与笛卡尔积可以组合成 θ 连接；连接本身也可以吸收额外条件：

内连接具有交换性，自然连接还具有结合性。它们让优化器能够重新安排多表连接：

集合并与交满足交换律、结合律，选择可以分配到并、交、差两侧，投影可以分配到模式相同的并运算两侧。若选择谓词只引用分组键，它还可以越过聚合下推；若谓词引用聚合结果，就不能这样做。

规则集还要控制重复推导。若一条规则可以由其他规则组合得到，把它保留在热路径中会让同一表达式通过更多路线反复出现。优化器倾向使用足够表达所需变换的精简规则集，并用规范化表示识别已经见过的表达式。概念上，规则不断匹配子树、生成新形态，直到没有新表达式；工程实现则会在到达这个固定点之前利用成本界停止扩展无望分支。

图：等价规则改变表达式的形状，为提前过滤、缩窄列和调整连接次序创造条件。

外连接的边界

外连接会补出空值，因此不能直接套用内连接的全部规则。比如把右表条件从左外连接上方下推到右表，可能使原本应被上方选择淘汰的左侧行重新以“右侧全空”形式出现，结果就变了。

如果上方谓词对右侧补出的空值具有“空值拒绝”性质，也就是右侧相关属性为空时谓词只能得到假或未知，那么左外连接可以在该语境下收紧为内连接。像 product.price > 1000 就会拒绝右侧 price 为空的补行。

先减行、再减列、再安排连接

谓词下推

星河零售的条件可以按属性归属拆开：customer.region = '华东' 下推到客户表，orders.status = '已支付' 与时间范围下推到订单表，category.name = '电子商品' 下推到类目表。这样做的直观收益是让连接尽早面对小输入。

若谓词 $\theta_1$ 只引用 $E_1$ 的属性，则有：

若两组谓词分别只引用两侧，还可以分别下推。可是真实代价要结合访问路径判断：当小表通过连接键索引访问一张极大的表，而过滤列没有索引时，先对大表做完整过滤扫描可能比“先连接、顺手检查谓词”更贵。下推是一条很强的经验规则，不是脱离代价的定律。

投影下推

投影下推减少的是元组宽度。最终结果若只需要订单号、支付时间、商品名和金额，就不该让客户手机号、商品详情、订单备注等大字段一路穿过连接和排序。

投影不能丢掉后续仍要使用的属性。连接前的两侧除了最终输出列，还必须保留连接键；后续有分组、排序或过滤时，也要保留相应属性。设 $L_1,L_2$ 是最终需要的两侧属性，$L_3,L_4$ 是各自额外需要的连接属性，则可写成：

连接次序决定中间结果

五表连接不应机械地按 SQL 中出现的次序执行。先连接 category 与筛选后的 product，可以快速得到电子商品集合；先过滤 orders 再连接 customer，可以快速得到目标区域订单。之后再与 order_item 相遇，通常比一开始把整张明细表与整张商品表连接更稳妥。

优化器还要避免无连接谓词的笛卡尔积。如果先连接 customer 与 product，两者没有共同业务键，会生成两边行数乘积的中间结果。即使后面连接能够过滤，前面的膨胀也已经支付了代价。

图：下推选择减少中间行数，下推投影减少每行宽度，合理连接次序避免无谓的笛卡尔积。

统计信息让优化器能够提前估量

表、页、元组与不同值数

优化器不能先把每个候选计划跑一遍，只能用目录中的统计信息预测。对关系 $r$，常见统计量包括：

若元组成片存放，可以粗略写成：

目录还会保存索引层高、叶页数、聚簇程度、空值比例、最小值和最大值。若 $A$ 是键，则 $V(A,r)=n_r$。多列不同值数 $V((A,B),r)$ 能表达列组合的分布，通常比把两列独立估算更可靠。

直方图与高频值

只有最小值、最大值和不同值数时，估算器往往默认均匀分布。但零售数据很少均匀：订单状态可能大量集中在“已支付”，区域可能集中在少数大区，热门商品的明细行数远高于长尾商品。

等宽直方图把值域切成宽度相同的桶，每个桶记录行数；等深直方图调整桶边界，让每桶包含近似相同数量的行。数据倾斜时，等深桶会在密集区间变窄，从而保留更多细节。直方图还可以记录桶内不同值数。

图：相同桶数下，等深直方图会把更多边界分配给数据密集区，高频值则适合单独保存精确频次。

若某些值远比其他值常见，可以把最常见值及其精确频次单独保存，直方图只描述剩余部分。这样估算 status = '已支付' 时就不必假设每种状态平均分配。

统计信息为什么允许近似

每次插入、删除都同步更新全部统计信息，会给写事务带来很大负担。实际系统通常通过随机采样生成统计信息，并在数据变化达到阈值、低负载窗口或管理员触发时重新分析。执行过程中还可以比较“估算行数”和“实际行数”，偏差很大时触发统计刷新。

随机性很重要。如果样本只来自最近写入的分区，或者只覆盖某些门店，直方图会带入系统偏差。优化器不要求每个数字完全准确，但需要它们足以正确比较候选计划的相对大小。

选择率与基数怎样逐层传播

单条件选择

如果没有高频值或直方图，并假设属性值均匀分布，等值谓词的输出行数可估为：

若订单表有 2 亿行，status 有 5 个不同值，均匀假设会估成 4000 万行。但若高频值统计说明“已支付”占 68%，就应直接估为 1.36 亿行。这个差异足以改变索引扫描与顺序扫描的选择。

对范围谓词 $A\le v$，只知道最小值和最大值时，可用分段估算：

直方图存在时，应对谓词覆盖的完整桶与边界桶分别累计。参数值在优化时未知，估算器只能使用默认选择率、参数统计或生成多套参数计划。

复合谓词

设简单谓词 $\theta_i$ 的选择率为 $s_i$。若暂时假设条件独立，合取选择率是乘积：

析取选择率可以从“所有条件都不满足”的概率反推：

独立性是假设，不是事实。“华东”和“高金额订单”可能相关，“电子商品”和“高单价”也可能相关。把相关条件直接相乘会系统性低估或高估输出行数。多列统计、依赖信息和执行期反馈用于修正这种误差。

连接基数

笛卡尔积的行数是 $n_rn_s$。若共同属性是被引用表的主键，并且另一侧外键非空且每个值都能匹配，连接输出行数就等于外键侧行数。

当连接属性 $A$ 在两侧都不是键，且假设均匀、值域大体重叠时，常用估算为：

分母取较大的不同值数，等价于选择从两侧推导出的两个估算中的较小者。若两侧连接键直方图采用相同桶边界，还可以在每个桶内独立估算匹配数，再把各桶结果相加。值域重叠很少时，单纯的均匀公式仍会高估。

图：每个算子的输出行数和不同值数会继续成为父算子的输入，早期误差可能沿计划树逐层放大。

其他算子与不同值数

集合投影 $\Pi_A(r)$ 去重后的行数是 $V(A,r)$；按 $G$ 分组的聚合输出行数是 $V(G,r)$。并、交、差在缺乏重叠统计时，只能使用偏保守的上界估算。外连接还要考虑无法匹配后补空的行。

选择后不同值数也要传播。若谓词固定 $A=3$，则结果中 $V(A)=1$；若限定在三个明确值中，则不同值数至多为 3；一般情况下可先使用：

这个信息会继续影响下一次选择或连接估算。

代价模型把行数翻译成资源开销

代价不是墙上时钟时间

优化器显示的 cost 往往是内部单位，不等同于毫秒。一个常见抽象是把页读取、随机寻道、CPU 比较、内存占用和网络传输加权：

权重会随硬件、缓存和并行度变化。顺序读很多页可能比随机读较少页更快；数据已在缓冲池时，CPU 比较会变得更显眼；分布式执行还要考虑数据重分区和跨节点网络。

总成本也不是简单把所有输入读取重复相加。流水边会把生产者输出直接交给消费者，父算子不必再次从磁盘完整读取；物化边会把中间结果写出并重读。排序、哈希建表等阻塞算子还会带来启动成本和内存不足后的外部归并或分区写盘。

访问路径的选择

选择率很低、索引聚簇良好时，索引扫描通常只触碰少量索引页和数据页。若条件命中表中大多数行，非聚簇索引会导致大量随机回表，顺序扫描可能更便宜。覆盖索引能直接给出查询所需列，避免回表，是另一条物理路径。

连接算法的选择

图：基数、索引、顺序、可用内存与后续排序需求共同决定物理算法，不能只凭表大小选连接。

有趣顺序是一种可复用的物理性质

某个子计划可能不是当前最便宜的，却输出后续算子需要的排序顺序。例如先用归并连接得到按 customer_id 有序的结果，后面若还要按该键连接或分组，就能省掉一次排序。优化器因此不能只为每个关系子集保留一个最低成本计划，而要为每个有用的输出顺序分别保留最佳计划。

动态规划同时挑选连接顺序与物理算子

为什么不能枚举完整连接树

对 $n$ 个关系，若把左右输入次序也视为不同，二叉连接次序数量可写成：

五表已有 1680 种，七表达到 665280 种，十表超过 176 亿种。再乘上每张表的访问路径、每个连接的物理算法、构建侧选择和物化方式，穷举很快不可行。

最优子结构与备忘录

动态规划的关键是：若全局最优计划先算出关系子集 $S_1$，那么该位置使用的 $S_1$ 子计划必须是满足相同输出物理性质时的最低成本计划。否则把它替换成更便宜的同性质子计划，就能得到更便宜的全局计划，和“全局最优”矛盾。

用 Best[S, o] 表示计算关系子集 $S$ 且输出物理性质 $o$ 的最佳计划。单表状态枚举顺序扫描、索引扫描和覆盖索引等访问路径；多表状态把 $S$ 划分成两个非空子集，再尝试所有可用连接算法：

索引嵌套循环需要单独处理：内侧若是带连接键索引的基础表，就不必先执行完整内侧扫描，索引探测成本直接计入连接算法。哈希连接也要分别尝试把两侧设为构建输入。

图：每个子集只保留满足特定输出性质的最佳候选，更大的子集直接复用这些结果。

复杂度与剪枝

考虑所有浓密连接树的动态规划约为 $O(3^n)$，需要保存约 $2^n$ 个关系子集及少量有趣顺序。只考虑左深树时，每次连接的右侧都是基础关系，搜索时间可以降到约 $O(n2^n)$，也更适合流水执行。

连接图还能进一步剪枝。若两个子集之间没有连接谓词，把它们合并会生成笛卡尔积，通常可以跳过。对称划分只需考察一次。备忘录中已有更便宜的同性质候选时，更贵候选也可直接淘汰。

搜索空间必须有边界

通用规则优化器的备忘录

只优化内连接次序还不够。外连接、聚合、集合运算和 Top-K 都需要更一般的等价规则框架。实现时可以把逻辑规则用于生成等价表达式，再用物理规则把逻辑连接转换成哈希连接、归并连接等具体算子。

高效实现需要共享相同子表达式，避免复制整棵树；检测重复推导，避免不同规则路径反复得到同一表达式；第一次优化子表达式时记录结果；维护当前上界，用成本界剪掉不可能胜出的候选。这样的备忘录不是简单的“计划列表”，而是一张表达式组、物理性质和最佳实现之间的图。

启发式规则的价值与风险

常见启发式包括尽早选择、尽早投影、避免笛卡尔积、优先连接能产生较小中间结果的输入。它们计算便宜，常用于快速找到一个可用计划，给后续成本搜索提供上界。

启发式也会失误。大表过滤列没有索引，而连接键有索引时，先完整扫描大表过滤可能比用小外表做索引嵌套循环更贵。投影过早若引入去重、阻断索引覆盖或丢失有趣顺序，也可能增加代价。

限制树形与优化预算

左深树让每次连接的右输入保持为基础表，方便流水执行，也把搜索从全部浓密树缩小到更少候选。更激进的策略会从每个可能的起始表出发，用访问路径排名贪心选择下一张表。

优化器还可以设置时间或成本预算。先用便宜规则得到基线计划；如果基线已经很便宜，减少搜索时间；如果基线昂贵，允许更长的优化时间。预算耗尽时返回目前最好的计划，而不是让编译时间无限增长。

计划缓存与参数敏感

应用常把同一条参数化 SQL 反复执行。计划缓存能省去重复优化，但第一次参数对应的最佳计划未必适合后续参数。小门店一天只有几十笔订单，索引扫描很好；全国活动日的范围返回数千万行，顺序扫描或并行计划可能更合适。参数敏感问题的本质是同一个语句模板对应多种数据规模。

嵌套子查询需要去相关化

相关执行为什么昂贵

考虑“找出最近 30 天至少有一笔已支付订单的客户”：

select c.customer_id, c.name
from customer as c
where exists (
  select 1
  from orders as o
  where o.customer_id = c.customer_id
    and o.status = '已支付'
    and o.paid_at >= :start_time
);

概念上，内层查询像一个以 c.customer_id 为参数的函数。若对外层每个客户重新执行一次内层查询，会产生大量重复工作和随机 I/O。优化器会尝试把相关子查询转换为连接形式，让成熟的连接算法一次处理整批数据。

半连接保持 EXISTS 的重复语义

直接改成普通连接可能重复客户行：一个客户有十笔订单，就会连接出十行。EXISTS 只关心是否至少存在一行。半连接 $r\ltimes_{\theta}s$ 只保留左侧能找到匹配的元组，并保持左侧自身的重复次数，正好表达这种语义：

NOT EXISTS 可以转换为反半连接：只保留左侧找不到匹配的元组。IN 在空值与重复语义允许时也可使用相应半连接重写。

聚合相关子查询更复杂

如果内层计算每个客户的订单数，去相关化通常要把相关键移入分组键，然后把标量比较变成半连接或连接谓词。标量子查询还要求返回至多一行；某些改写会掩盖原本应该抛出的“多行结果”异常，因此不能只看性能。

去相关化不是永远更便宜，也不是对所有复杂子查询都可行。一般规则优化器会把半连接、反半连接和聚合改写放入候选空间，再由成本模型决定。

物化视图既参与重写，也需要维护

用预计算换取读取速度

普通视图只保存定义，查询时再执行；物化视图把结果实际存下来。星河零售每天反复查看“门店、日期、类目”的销售额和订单数，可以物化这组聚合，查询时从数十亿条明细计算变为读取少量汇总行。

物化数据是冗余副本，收益来自读查询，成本来自存储和更新维护。立即维护让视图与基础表在同一事务中保持一致，会增加写入延迟；延迟维护把变更积累后批量刷新，降低前台写入压力，但查询可能看到有时效差的数据。

差分与增量维护

把更新拆成删除旧元组和插入新元组，只需处理插入差分 $i_r$ 与删除差分 $d_r$。若 $v=r\bowtie s$，在 $$ 侧插入时：

删除时：

选择的差分可以直接通过原谓词过滤：

投影去重后，同一个结果元组可能由多条基础元组产生。删除其中一条时不能立即删除投影结果，需要为每个投影元组维护派生计数，计数降到零才真正删除。

聚合也需要辅助状态。count 增减计数；sum 增减数值并保留组计数；avg 应维护 sum 与 count 再相除；min、max 删除当前极值时要寻找次优值，适合在 (分组键, 聚合列) 上准备有序索引。

集合交的增量维护需要检查新插入元组是否也存在于另一侧；并与差还要跟踪同一结果元组由哪一侧贡献。外连接更麻烦：某侧插入第一条匹配时，要撤掉原来的补空行；删除最后一条匹配时，又要补回空值行。完整表达式按自底向上的方式传播差分：先算最小子表达式的变化，再把这批变化送入父算子，直到得到物化结果的最终增量。

图：差分沿表达式树传播，只更新受影响的连接、投影或聚合结果，不必每次全量重算。

重写有两个方向

若已物化 $v=r\bowtie s$，查询 $r\bowtie s\bowtie t$ 可以改写成 $v\bowtie t$。优化器要识别查询子表达式能否由物化结果覆盖，还要补上缺失的选择、投影或聚合。

反方向也可能更便宜。若查询 σ_{A=10}(v)，而物化视图没有 A 上的索引，直接扫描整个 $v$ 很贵；把 $v$ 展开回 $r\bowtie s$，利用 r.A 与连接键索引，可能得到更低成本计划。物化并不意味着查询必须读取物化结果。

选择哪些视图与索引

物化视图和索引都是派生数据：加速一部分查询，同时增加存储与写维护。选择问题应基于真实工作负载，把查询延迟、更新代价、刷新时效和存储预算放在一起评估。只统计“被引用次数”会漏掉维护成本，也会忽视少数高优先级查询的响应要求。

高级优化处理运行时与工作负载问题

Top-K 不必先算完再丢掉

只取金额最高的 20 笔订单时，先生成全部结果、完整排序再截断会浪费大量工作。若索引或流水计划能按目标顺序产生元组，执行器可以在收集到足够结果后提前停止。另一种思路是估计第 $K$ 名的阈值，先加范围条件缩小候选；结果不足时放宽阈值重试，过多时只保留前 $K$。

连接消除依赖约束

视图可能连接了 orders 与 store，但某次查询只用订单列。若 orders.store_id 是非空外键，引用 store 的唯一键，连接既不会过滤订单，也不会复制订单，就可以移除。没有非空、外键或唯一约束时，删除连接可能改变行数，不能仅凭“没输出右表列”判断。

更新查询要防止重复命中

若用薪资索引扫描 salary >= 10000 并同时把薪资提高，更新后的索引项可能被重新插到扫描尚未经过的位置，同一行就可能再次被看到。这类“更新改变自身扫描结果”的风险称为 Halloween 问题。解决办法是先物化受影响行标识，再统一更新；如果能证明更新不会让元组重新进入剩余扫描范围，则可省掉这次物化。大量索引更新还可以按各索引键排序后批量应用，减少随机 I/O。

多查询共享不等于各自最优之和

一批报表都扫描同一张大订单事实表时，可以把一次扫描的数据流水发送给多个查询。更一般的多查询优化会寻找公共子表达式，只算一次并复用。有时每个查询单独的最低成本计划共享性很差，换成各自稍贵、但能共享大量工作的一组计划，总成本反而更低。

参数化与自适应

参数化优化可以预先产生多套计划，并记录各自适用的参数范围。真正执行时只需按参数挑选，不必完整重优化。自适应执行则把选择推迟到运行期：例如观察外侧输入实际大小后，在嵌套循环与哈希连接之间切换。

若早期实际基数与估算相差太大，系统还可以用新观测重新规划剩余部分，甚至终止并重启计划。自适应机制必须控制重启次数和已支付成本，否则“纠错”本身会比继续执行更贵。