扫码获取 VIP 码
添加管理员微信获取 VIP 码
数据库系统工程师的上午题里，有一类题目表面考的是关系代数，实际考的却是查询优化。很多考生把关系代数的并、差、笛卡尔积、选择、投影、连接背得滚瓜烂熟，可一旦题目问"下列关系代数表达式的查询优化中，错误的说法是哪一项"，立刻陷入混乱。原因在于，关系代数解决的是"用什么运算表达查询"，而查询优化解决的是"同一查询的多种等价写法，哪种执行代价更小"。这是两个层次的问题，命题人恰恰喜欢在两者的交界处挖坑。本文从查询优化的概念本质讲起，深挖启发式优化规则与选择、投影下推的底层逻辑，再逐条拆解历年真题的命题思路，帮助读者把这一类高频考点彻底吃透。
在数据库系统中，用户提交的一条查询语句，绝大多数情况下并不是被原封不动地执行的。数据库管理系统（DBMS）收到查询后，要经历语法分析、语义检查、查询转换、查询优化、执行计划生成、执行这样一个完整的流水线。其中，查询优化是整个流程中最能体现数据库系统技术含量的环节。它要回答的问题只有一个：给定一个查询请求，如何在众多等价的执行方案中，挑选出代价最小、执行效率最高的那一个。
所谓"等价"，是指不同的关系代数表达式或不同的执行路径，最终返回的结果集完全相同。以查询"选修了课程号等于C1的学生的姓名"为例，可以先做学生关系与选课关系的笛卡尔积，再从结果中做选择，最后投影出姓名；也可以先对选课关系做"课程号等于C1"的选择，再与学生关系做连接，最后投影。两种写法的结果相同，但前者的笛卡尔积会先生成一张巨大的中间表，再从中筛选；后者则先缩小了选课关系的规模，再连接。执行代价的差异可能达到几个数量级。查询优化的任务，就是在不改变查询语义的前提下，把这个"先做选择再连接"的合理顺序自动找出来。
需要强调的是，查询优化是对数据库系统的性能优化，而不是对SQL语句书写风格的简单建议。有些教材把"SELECT子句中只写需要的列""避免使用通配符"这类经验也归入查询优化，但严格意义上的查询优化发生在DBMS内部，由优化器自动完成，用户感知不到中间过程。考生需要区分两个层面：一是用户层面的人工SQL调优，二是系统层面的自动查询优化。软考考察的重点是后者，尤其是关系代数表达式的代数优化。
查询优化从方法上可以分为两大类，即代数优化和物理优化。代数优化又称逻辑优化或规则优化，它把查询表示成关系代数表达式，再依据一组等价变换规则，把表达式改写成执行代价更小的等价形式。代数优化的输入和输出都是关系代数表达式，它不关心数据具体存在哪个磁盘块、用什么索引存取，只关心运算的种类和运算的先后顺序。例如，把选择运算尽量推向叶节点、把投影运算尽量提前、把笛卡尔积和其后的选择合并为连接，这些都属于代数优化的范畴。
物理优化则更进一步，它在代数优化给出的逻辑执行计划基础上，为每一个运算选择具体的物理实现算法，并估算执行代价，从而确定最终的执行计划。物理优化关心的是底层细节：连接是用嵌套循环、排序归并还是哈希连接；存取是用全表扫描还是走某个索引；缓冲区的页面如何分配。物理优化通常基于代价估算模型，根据关系的元组数、属性值分布、索引的统计信息，估算各种候选方案的代价，选出代价最小者。
这两层优化的关系是：代数优化先对逻辑结构进行等价改写，物理优化再对改写后的结构做具体算法的选择和代价评估。软考上午题主要考察代数优化，也就是等价变换规则和启发式规则的运用；而物理优化的考察通常停留在概念层面，要求考生知道它基于代价估算、依赖统计信息即可。把握住这个分层，就不会把两类题目的考点混淆。
从执行流程看，查询优化发生在查询解析之后、执行计划生成之前，是查询处理流水线中最具技术含量的一环。用户提交的SQL经过词法分析和语法分析，被转换成一棵语法树，语法树再映射为初始的关系代数表达式，这棵表达式通常直接对应SQL的书写顺序，执行代价往往很高。查询优化器要做的，就是把这张初级的、代价高的表达式，逐步改写为代价低的等价表达式。整个过程要保证两点：一是改写前后语义等价，结果集不能有任何差异；二是优化自身的开销要控制在合理范围内，不能为了优化一个简单查询而耗费比直接执行还长的时间。
代数优化的合法性，建立在一组关系代数等价变换规则之上。这些规则保证变换前后的表达式在语义上完全一致，即对任意合法数据库状态，两个表达式产生的结果关系完全相同。理解这些规则，不能靠死记硬背，而要看透每条规则背后的集合论语义。
最基础的一条规则是选择的串接律与交换律：对同一关系施加多个选择条件，可以分解为依次施加，也可以交换先后顺序，结果不变。其集合论依据在于，选择运算本质上是按谓词筛选元组，多个谓词之间是合取关系，交集运算满足交换律和结合律。因此，条件"成绩大于等于90且课程号为C1"的选择，无论先按哪个条件筛，最终留下的元组集合都一样。
第二条关键规则是选择运算对笛卡尔积的分配律。这条规则是查询优化中"选择下推"的理论根基。设有表达式"选择(关系R 笛卡尔积 关系S)"，当选择条件只涉及R的属性时，可以把它改写为"选择(R) 笛卡尔积 S"。其道理在于：选择条件只筛R的元组，与S无关，那么先在R上做选择，只缩小R的规模，不会影响最终结果，却能显著减少笛卡尔积要处理的元组对数量。当选择条件同时涉及R和S的属性时，不能把整个选择直接下推到单一关系上，但可以部分下推：把只涉及R属性的那一部分条件下推到R上，只涉及S属性的部分下推到S上，再把涉及两者属性的连接条件留在连接运算处。
第三条是投影运算对笛卡尔积的分配律。投影只保留若干属性列，如果某些中间关系的属性在最终结果中根本用不到，那么在连接之前先投影掉这些无用属性，可以缩减中间关系的宽度，从而降低后续运算处理的数据量。投影下推的依据是：未被投影保留的属性，对后续只依赖保留属性的运算不产生任何影响，提前消除是安全的。
此外还有连接运算的交换律与结合律。自然连接和等值连接满足交换律，即R连接S与S连接R结果等价；也满足结合律，即(R连接S)连接T与R连接(S连接T)结果等价。这两条规则为连接顺序的重排提供了理论依据：优化器可以把代价小的连接安排在前，把中间结果大的连接安排在后，从而控制中间关系规模的膨胀。但需要注意的是，连接顺序重排只改变运算的先后，不改变最终的连接语义，这是它区别于普通算数运算结合律的地方。
代数优化的启发式规则，可以概括成一条总纲：尽可能先做选择运算，再做投影运算，把笛卡尔积尽量与选择结合成连接，同时避免重复计算公共子表达式。这条总纲背后的成本直觉是：选择运算的过滤性最强，能大幅减少中间结果的行数；投影运算能减少中间结果的列数；而笛卡尔积是最昂贵的运算，其代价与两个输入关系元组数的乘积成正比，必须尽量避免或尽早缩小其输入规模。
具体拆解开来，启发式优化通常包含以下几条规则。第一，选择运算优先：把选择运算尽量下推到查询树的叶节点附近，尽早过滤掉不满足条件的元组。第二，投影运算次之：在保证语义不变的前提下，把投影运算尽量提前，消除对后续运算无用的属性列。第三，合并选择：把针对同一关系的多个选择条件合并为一个，减少扫描次数。第四，把笛卡尔积与选择结合成连接：当选择条件恰好是笛卡尔积两边关系属性的等值条件时，这个"选择加笛卡尔积"的组合在语义上等价于连接，而连接的实现算法远比笛卡尔积高效。第五，提取公共子表达式：当同一子表达式在查询中重复出现时，只计算一次并复用其结果，避免重复扫描。
这五条规则中，选择下推是最核心、最常考的一条。命题人经常给出一个关系代数表达式，让考生判断哪一种等价改写符合启发式优化原则，或者指出某个改写违反了规则。要答对这类题，必须能在表达式和查询树两种表示之间自由转换，并准确判断选择条件下推的安全条件。
把启发式规则落到具体操作上，可以得到一组可机械执行的变换手法。手法之一是选择下推与选择合并。对于表达式"选择p1(选择p2(R))"，可以合并为"选择(p1且p2)(R)"，只扫描一次R。对于"选择p(R 连接 S)"，当p只涉及R属性时，改写为"选择p(R) 连接 S"；当p拆分为p_R和p_S且p_C时，改写为"选择p_R(R) 连接(条件p_C) 选择p_S(S)"。