做数据库作业做到第九章很多人的体验是从“写SQL很爽”突然变成“看执行计划很懵”。关系查询处理和查询优化这一章既要理解数据库内部怎么执行一条查询又要会用手工方式估算代价和改写查询树作业题往往看起来不复杂真正动手却到处是坑选择下推该推几个关系、投影到底能不能动、代价公式里哪些因子要算、两个表做连接到底用哪种算法一步错后面全错。这篇文章不按某个特定教材的题号去讲答案而是把这章课后习题里高频出现的几类题型拆开关系代数优化、代价估算、连接策略选择、综合执行计划推导每一类都给一套可以直接照着做的判断流程和计算口径。无论你是正在赶作业还是在准备考试都可以拿这篇文章当复习提纲。1. 这章习题到底在考什么先建立一条知识主线1.1 第九章在整本数据库教材里的位置前面章节讲的是怎么设计表、怎么写SQL、怎么用视图和索引也就是“用户视角”的数据库。到了第九章视角切换到数据库系统内部一条SQL语句交进去之后系统到底经历了什么才把结果返回给你。这一过程通常被拆成四个阶段语法分析与翻译检查SQL语法、语义合法性把SQL转换成关系代数表达式或等价的分析树逻辑优化也叫代数优化利用关系代数的等价变换规则把执行起来很笨的表达式改成更聪明的形式物理优化为每一个操作选择具体的算法比如全表扫描还是索引扫描、嵌套循环连接还是哈希连接同时确定操作之间的执行顺序执行按照选好的执行计划真正读写数据返回结果。课后习题的命题逻辑很简单你既然学了这条主线就得能在这条主线上的任何一环做手工推演。所以题目类型基本可以归纳成下面这张表。题型考察点常见问法SQL转关系代数是否理解SQL的声明式语义与过程化表达之间的差异“把下列SQL写成关系代数表达式”查询树构造与启发式优化是否掌握等价变换规则和优化原则“画出查询树并优化”代价估算是否会用IO代价模型比较访问路径“全表扫描、索引扫描哪个代价低”连接算法与顺序是否理解物理优化中的算法取舍“用嵌套循环连接还是哈希连接连接顺序怎么定”综合执行计划推导能否串联前面所有知识“给出该查询的最优执行计划并计算代价”1.2 为什么这章作业容易出现“背会了但不会做”一个很普遍的现象是不少同学把等价变换规则倒背如流结果做题时先把所有选择一股脑下推再把投影也全部下推最后发现优化完的查询树反而不能执行。原因在于规则本身是“允许做什么”而不是“应该做什么”。课后题真正想训练的是判断力哪一步变换能减少中间数据量哪一步变换只是形式好看但没有任何实际收益哪一步变换甚至会把连接条件拆坏。后面所有内容都会围绕这个判断力展开。先记住结论优化不是套公式而是在每一步都估算一遍“这条路径要碰多少块数据”。有了这个意识再看下面的题型就有方向了。2. 关系代数优化题把SQL翻译成查询树再按规则“瘦身”2.1 为什么一定先要会画查询树关系代数优化的标准操作对象是查询树也叫关系代数语法树。树的结构并不复杂叶子节点是参与查询的基本关系内部节点是关系代数操作从叶子到根的方向就是数据流动的方向。画查询树最大的好处是强迫你显式表达操作顺序。SQL是声明式的你告诉数据库“要什么”但不告诉它“先干什么后干什么”。而关系代数是过程式的任何一棵查询树都对应一个具体的执行次序。课后题让你画查询树本质就是让你把SQL里面隐含的操作顺序摊开来看。举个例子很多人第一次画树时会犯错把WHERE子句里的条件全部放在一个选择节点里然后挂到所有表的笛卡尔积之上。这样做并没有语法错误但它把许多本来可以先过滤的小关系硬生生拖到了大连接之后逻辑上可行性能上很糟。查询树优化的目标就是在不改变语义的前提下把这些过滤操作尽量往叶子方向推。2.2 两类最核心的等价变换规则课后习题里真正高频用到的规则基本可以压缩成两条主线。第一是选择下推。选择操作是最“便宜”的过滤手段它能直接减少一个关系中的元组数。能往下推的选择就往下推这就是“选择尽早执行”原则。但要注意两点一是选择条件只能下推到它用到的那些属性所在的关系上二是如果选择条件涉及的属性分属多个关系通常要用“选择分裂”把它拆成多个选择再分别下推。比如 A1 AND B2 如果A属于R、B属于S就得拆成两个选择分别推到R和S上。这也是课后题最爱埋的坑之一。第二是投影下推。投影能够去掉不需要的列让中间结果是“瘦表”后续连接、排序、扫描都能少读数据。但投影下推比选择下推更讲究下推投影时除了最终要输出的属性还必须保留后续操作需要用到的属性最典型的就是连接属性。如果某个投影把连接键给剪掉了那这棵树语义就错了。所以实际做题时投影下推往往跟“补全属性集”一起做。除了这两条连接操作满足交换律和结合律、选择与笛卡尔积可以合并成连接也是经常用的规则。但理解了选择、投影的取舍逻辑其他规则基本都可以按同样的思路推理。2.3 一道典型优化题的手工推导示例假设有这样一道课后题SELECT Sname FROM Students S, SC, Courses C WHERE S.Sno SC.Sno AND SC.Cno C.Cno AND S.Sage 20 AND C.Credit 2;第一步把它直接翻译成查询树。初始状态往往很朴素三个关系先做笛卡尔积再统一做选择和投影。用文本近似表示初始查询树大概是投影(Sname) └─ 选择(S.Sage20 AND C.Credit2 AND 连接条件) └─ 笛卡尔积 ├─ 笛卡尔积 │ ├─ Students │ └─ SC └─ Courses第二步开始优化。先把选择条件拆开S.Sage20 只涉及 Students可以下推到 Students 叶子上C.Credit2 只涉及 Courses可以下推到 Courses 叶子上两个等值连接条件留在连接节点上分别变成 S.SnoSC.Sno 和 SC.CnoC.Cno。第三步处理投影。最终需要 Sname但连接过程必须保留 S.Sno、SC.Sno、SC.Cno、C.Cno。所以把投影下推到连接之上的同时在三个叶子节点上方分别加上“只保留必要属性”的投影。优化后的查询树结构变成投影(Sname) └─ 连接(SC.CnoC.Cno) ├─ 投影(S.Cno) │ └─ 连接(SC.SnoS.Sno) │ ├─ 投影(Sno,Sname)后选择(Sage20) │ │ └─ Students │ └─ 投影(Sno,Cno) │ └─ SC └─ 投影(Cno)后选择(Credit2) └─ Courses这棵树的执行路径比初始树清晰得多先过滤出年轻学生和学分较高的课程这两个小集合再做两次连接中间数据量小了一个数量级。像这种题阅卷时重点看的是你能否把选择正确拆分并下推到对应叶子以及投影属性集合是否保留连接键。2.4 下推时容易翻车的几种情况第一外连接不能随便下推。选择下推到外连接的“保留侧”时语义会变。例如 LEFT OUTER JOIN 右表上的过滤条件下推可能把不匹配的右表元组过滤掉导致左表保留行数变化。遇到外连接老老实实在连接结果之上再做选择。第二含有聚合、GROUP BY、DISTINCT 时投影下推要格外小心。去重和分组依赖完整属性集合在不知道分组键之前投影不能把排序或分组属性剪掉。第三子查询和外连接有时会改变规则适用范围。很多教材在讲规则时会注明“给定关系集合不相交且结果不依赖元组顺序”。作业题一般不会故意出这种极端情况但面试和考试中喜欢用这类边界条件来区分学生是背规则还是懂语义。3. 代价估算题IO是主角别被“看起来快”带偏3.1 代价模型的基本盘为什么只看IO次数优化器选物理计划时的代价一般由三部分构成IO代价、CPU代价、通信代价。在单机数据库场景下磁盘IO通常是最大瓶颈所以绝大多数教材和课后题都默认“按磁盘访问的块数比较不同方案的优劣”。这里的逻辑和普通程序不一样。普通程序里一次运算的成本是“算了几次CPU指令”但数据库里一条查询如果涉及全表扫描可能要把几百万行数据从磁盘搬到内存。磁盘随机读一次要十毫秒级别的寻道时间哪怕是顺序读吞吐量也远低于内存运算。所以课余题设一个极端简化模型内存无限大、磁盘块大小固定、每次IO读一个块。在这个模型下谁的块数少谁就快。我建议做题时保留这个口径不要自己去加“CPU运算还要考虑hash函数耗时”之类的细节那是论文级讨论课后题不会考。先把块数算对再谈精细化。3.2 频度最高的几个代价参数不同教材记号略有差异但核心参数就那么几个记号含义怎么得到n_R关系R的元组数题目给出或由统计信息得出f_R每块能容纳的R元组数元组长度除以块大小题目常直接给出b_R关系R占用的数据块数b_R ceil(n_R / f_R)hB树索引的高度题目给出或按层数推算s选择率满足条件的元组占总元组数的比例还有一个容易忽略的概念是聚簇索引和非聚簇索引的区别。聚簇索引的索引顺序与表数据物理顺序一致所以按聚簇索引取一批连续键值时命中的数据集中在一块块连续的数据块上非聚簇索引的叶子节点只存指向数据行的指针命中多少个元组就要去抓多少次数据块。这个差异直接导致两种索引在范围查询下的代价天差地别。3.3 一道完整的访问路径比较题来看一道非常典型的课后题目几乎每本教材第九章后面都有类似变体。关系R有 n_R20000 个元组每块容纳 f_R20 个元组则 b_R20000/201000 块。查询为SELECT * FROM R WHERE a 10已知满足条件的元组占 10%即 2000 个元组。方案A全表扫描。顺序读一遍R的全部1000个块代价为1000块IO。方案B在属性a上建聚簇索引索引高度 h3。先用索引定位到第一个满足条件的键值再从聚簇表中读取命中的元组。10%的元组是2000行2000除以每块20行得到100块。总代价约 h100103块IO。方案C在属性a上建非聚簇索引同样 h3。索引定位后2000个满足条件的元组各自散落在各个数据块中理论上每次取一个指针再去读一个块极端情况下要读取 2000 次数据块。总代价约 320002003块IO。比较结果很有意思看起来“用索引”总是比全表扫描快在聚簇索引下确实如此但非聚簇索引在10%的选择率下反而比全表扫描慢一倍。原因很简单非聚簇索引的命中元组在物理块上不连续2000次随机单块IO的开销远大于全表1000块的顺序IO。3.4 选择率变化时结论会反转如果把这个题改一下把选择率从10%提高到50%也就是10000个元组满足条件聚簇索引代价310000/20503块IO非聚簇索引代价310000≈10003块IO全表扫描仍为1000块IO。这时聚簇索引依然比全表扫描好一点而非聚簇索引已经完全不可用。但若选择率到80%全表扫描就会反超聚簇索引。这就是优化器为什么依赖统计信息同一个索引在不同数据分布下可能从“最佳方案”变成“最差方案”。课后题让你算两到三个方案不是比谁背公式熟而是让你建立“索引不是万能”的直觉。3.5 代价计算题最常见的三个翻车点其一是混淆“元组数”和“块数”。很多同学把20000个元组当作20000块IO去算结果算出天文数字。务必先除以每块容纳的元组数再参与代价计算。其二是非聚簇索引的随机访问次数。非聚簇索引扫描1000个满足条件元组代价基本就是1000次数据块访问不是说“读索引叶节点1000块钱读数据1000块钱”那是双重计数。索引叶节点的IO只需要算一次定位开销。其三是忘记题目给定条件。如果题目明说“内存可容纳全部数据”或“假设数据已按查询属性排序”那么全表扫描很可能只需要读一遍数据块甚至零IO顺序和随机的问题就不存在了。做题前先圈出题目假设再动手套公式。4. 连接策略题嵌套循环、排序合并、哈希到底选哪个4.1 连接顺序为什么是优化的核心命题多表查询里连接顺序直接决定中间结果规模。考虑三个关系R、S、T先做 R⋈S 还是先做 S⋈T两种顺序产生的中间关系大小可能差好几个数量级。连接操作满足交换律和结合律所以理论上所有连接顺序都是合法的优化器要做的就是在巨大的候选集里找一个代价小的。课后题会把这个过程简化成给你两个表的大小、连接键的分布、内存可用块数让你比较几种连接算法或者让你判断“哪个表应该做外层”。判断的核心原则只有一个尽量让中间结果小而精。有一个工程上常用的经验法则是先连接小关系尤其是通过条件过滤之后的小关系另一个更严格的做法是估算中间结果大小两个关系在连接键上的选择率越低即重复值越少结果越小。4.2 三种主流连接算法的代价口径先做约定R有n_R10000个元组、b_R100块S有n_S5000个元组、b_S50块每块100个元组内存缓冲区只留少量块给结果不考虑中间结果写回。简单嵌套循环连接外层R的每个元组都要扫一遍内层S的全部块。代价为 n_R×b_Sb_R10000×50100约500100块IO。这个数字说明为什么真实数据库几乎不用这种原始算法。它只在外层极小、内层可以整体放进内存时才勉强能用。块嵌套循环连接不是按外层元组循环而是按外层块循环。把R的一个块读入内存再让S的每一块与之匹配。代价为 b_R×b_Sb_R100×501005100块IO。这个数量级比简单嵌套循环好了近两个数量级原因是减少了内层重复扫描的次数。排序合并连接如果R和S已经按连接键有序代价就是两边各扫描一遍b_Rb_S150块IO。如果无序还要加上两个关系各自排序的代价。外部排序的IO量大约是关系本身的2到3倍所以无序时排序合并并不便宜。这个算法最适合“两侧数据量差不多且连接键本身有序”的场景。哈希连接先把较小的关系S读出来构建哈希表代价是读一遍S共50块再读一遍R去探测哈希表共100块。理想情况下总代价约150块IO。若内存不够需要把哈希桶写回磁盘再读取课后题常用 3×(b_Rb_S) 来估算即约450块IO。哈希连接的优势是无需预先排序对等值连接非常友好也是很多数据库引擎里的默认连接算法。三种算法放在一起对比算法本示例IO代价适用场景简单嵌套循环约500100块外层极小内层可入内存块嵌套循环约5100块通用后备方案排序合并约150块到数百块两侧有序或连接键需排序哈希连接约150到450块等值连接数据量大单看这个例子哈希连接和排序合并明显优于嵌套循环如果S和R已经有序排序合并甚至可以和哈希打个平手。课后题让你“为每个连接选算法”时答案不是说哈希一定最好而是要根据给定条件判断数据有序没有、内存够不够大、连接是不是等值。4.3 什么时候嵌套循环反而更合适很多人学完哈希连接后容易形成“哈希无敌”的印象。但在真实系统里嵌套循环连接依然大量存在。原因有几个一是嵌套循环不要求等值条件非等值连接如 R.a S.b 只能用嵌套循环二是当外层关系经过过滤后非常小比如只有几个元组时嵌套循环的 IO 代价是“几个元组 × 内表块数”可能比先把两个大表都哈希一遍更划算三是哈希连接对数据分布敏感如果连接键严重偏斜哈希桶可能溢出而嵌套循环的行为反而稳定。所以做题时不要只背一个最优算法要会描述“在什么条件下哪个方案好”。比如外层只有10个元组、内层有500块时简单嵌套循环的代价大约 10×50015001块这时它未必比哈希差太多。考试或作业里这类情景题考察的就是这种条件化判断。4.4 连接树的形状左深树为什么是工程默认除了连接算法连接顺序还包括连接树的形状。三张表连接时树形可能为左深树、右深树或总线型树。左深树的意思是每次连接都用一个已经得到的中间结果去连接一个新的关系形状上像向左倾斜。工程上优化器格外偏爱左深树原因是它方便流水线执行每次只生成一个中间结果内存占用容易控制而且可以沿用前一次连接的输出直接做下一次连接不需要物化多个中间表。课后题如果出现“请画出多表连接的执行计划”推荐优先给出左深树方案并在括号里说明理由候选方案少、能利用前一次连接结果、便于索引嵌套循环。这比随手画一棵随意形状的树要严谨得多。5. 综合题实战一道作业题从SQL到最终执行计划的完整推导5.1 题目与初始语义综合题的价值在于把前面所有知识串成流水线。下面这道题是课后综合题的常见模板里面杂糅了选择下推、投影裁剪、连接顺序和物理算法选择。查询需求SELECT Sname, Cname FROM Student, SC, Course WHERE Student.Sno SC.Sno AND SC.Cno Course.Cno AND Student.Sdept CS AND Course.Credit 2;给定统计信息Student10000个元组每块100行共100块CS系学生占5%即500人SC50000个元组每块100行共500块Course200个元组每块50行共4块Credit2的课程占20%即40门。5.2 第一步逻辑层面的手工优化先写初始查询树再逐步优化。这一步可以把第2节的规则重新走一遍把 SdeptCS 下推到 Student 叶子节点Student 先变成500行的临时结果约5块把 Credit2 下推到 Course 叶子节点Course 变成40行的临时结果不到1块投影下推最终只需要 Sname、Cname但连接过程要保留 Sno 和 Cno所以三个子树上的投影属性集合分别为StudentSno, SnameSCSno, CnoCourseCno, Cname。优化后的关系代数表达式大致是π(Sname,Cname)( (σ(SdeptCS)(Student)) ⋈(Sno) (SC ⋈(Cno) σ(Credit2)(Course)) )5.3 第二步确定中间结果大小决定连接顺序这里要先估算中间结果不能盲目选择“先连接Student和Course”因为两者之间没有直接连接条件强行连接会生成笛卡尔积。课后题出现这个坑的概率非常高。所以连接顺序第一步就是看图找边Student和SC通过Sno连接SC和Course通过Cno连接得到一条链 Student→SC→Course。再估算中间结果大小。CS系有500个学生每个CS学生平均选若干门课假设选课记录分散在SC中。SC有50000行学生总数10000人平均每人5门课CS学生的选课记录大致按比例估算为500×52500行这里按中间结果约2500行估算约25块。这个数量远小于两张大表直接连接的规模。因此连接顺序应该是先连接Student和SC得到CS学生选课记录再与Course中的低学分课程连接。左深树天然符合这个顺序。5.4 第三步为每个操作选物理算法开始选择执行策略Student 上执行 σ(SdeptCS)。全表扫描100块可以得到500行CS学生代价100块IO如果Sdept上有聚簇索引且CS系比例5%索引定位加读取命中数据约358块IO。考虑说明优化器会倾向后者。为保守起见综合题里可以写“假设Sdept无索引则全表扫描100块”。SC 与 CS学生连接。CS学生500人为每个学生到SC中查找选课记录。如果SC.Sno上有索引用索引嵌套循环连接内层按索引查找约几十次IO如果SC.Sno上没有索引就只能顺序扫描SC全部500块构建哈希或做块嵌套循环。两种方案都合理但要能写清楚为什么选它。我这里选择“无索引时全表扫描SC再建哈希”总代价500块扫描加连接输出约25块远低于嵌套循环下对50000行逐一遍历。与 Course 连接。Credit2的课程只有40门可以把40门课程先建成哈希表放在内存然后流式读取中间结果2500行逐个探测Course的4块扫描成本几乎可以忽略。整个执行计划的读盘量约为Student扫描100块 SC扫描500块 中间结果写读约50块 Course扫描4块合计650块上下。对比不做任何优化时“三个关系先做笛卡尔积再过滤”的方案读盘量少了两三个数量级优化意义一目了然。5.5 综合题的标准答题结构这种题阅卷最看重的是过程不是最终答案。推荐的答题结构是四段式写SQL对应的关系代数或查询树说明你理解查询语义做逻辑优化标出每一条选择下推和投影裁剪的依据估算各阶段中间结果大小说明连接顺序为什么这么排为每个操作选算法并给出IO代价汇总。按照这套结构写即使某一步估算不准阅卷人也能看出你的思维链路是完整的。最怕的是只扔一个“最终执行计划”上去中间过程全空那既无法验证你是否真的会做也拿不到步骤分。6. 课后习题的常见失分点与自查清单6.1 阅卷视角下最典型的失分点把前面几章内容放在一起我总结出六个高频错误覆盖作业和考试。选择下推的顺序错了。先下推投影、后下推选择或者把所有选择合并成一个再推这两种做法不能说必然错但很容易在中间某一步丢掉必要属性或把连接条件弄碎。推荐固定顺序先拆选择并下推再处理投影。投影集合漏了连接键。投影下推后只保留输出列没有保留连接属性查询树语义已经错误。这条几乎是投影类题目失分率最高的一项。把选择条件误当成连接条件。连接条件必须连接两个关系中的属性选择条件是单关系上的过滤。如果连接节点上挂了单表属性条件要么没下推干净要么把连接做成了先连接再过滤都有问题。代价估算的单位混乱。有的同学算全表扫描用块数算索引扫描却用元组数最后数字相加物理意义不明。做题时统一用“块IO次数”作为单位所有中间量先换算成块。忽略题目中的前提假设。明明说“关系已按连接键有序”排序合并代价就是一遍扫描用哈希反而多算一遍构建代价。读题时先圈出排序、内存、索引这类前提词。连接顺序没有理由。很多同学连接顺序靠直觉题目问“为什么”只写“因为这样快”没有任何估算支撑。至少要写一句“先连接后中间结果约X块而另一种顺序的中间结果是Y块所以选前者”这比抽象的理由有力得多。6.2 交作业前用这张清单自查我建议每做完一道综合题都按下面的顺序过一遍检查项是否通过关系代数表达式中的所有属性都属于对应关系是 / 否每个选择条件下推到能直接判断真假的关系上是 / 否投影下推后仍保留连接键和输出属性是 / 否连接顺序的中间结果大小有估算依据是 / 否代价计算统一用“块IO次数”且不遗漏基础扫描是 / 否外连接、聚合、子查询没有滥用下推规则是 / 否如果哪一项没通过不要急着改数字先回到查询树重新画一遍。绝大多数综合题的错误都写在树里树对了后续的代价计算和算法选择才可能对。6.3 从作业到实践这些技巧的真实用途别以为这章作业只是在应付考试。数据库优化器的核心逻辑和你在作业里手工做的事是一样的。比如一条慢查询让你头疼你先看执行计划里有没有全表扫描再检查WHERE条件里的列有没有索引这本质上就是“把选择下推”加“选对访问路径”。再比如多表连接时发现中间结果爆炸你想办法调整JOIN顺序或者改成小表驱动大表这就是左深树与连接顺序的实际体现。唯一的不同是优化器能枚举的计划数量是你的几千倍还能基于统计信息自动选而你能做的是在SQL层面理解系统为什么会选一个糟糕的计划然后通过重写查询、加索引或调整表结构让它走对路。这章作业培养的恰恰就是这种“读执行计划”的能力。最后说一个个人习惯每做完一道优化综合题我会把优化前后的查询树并排抄一遍在每一层节点旁边标注“这里减少了多少块IO”。坚持做几道之后你会明显感觉到自己看执行计划不再发怵写多表SQL时也会不自觉地想“哪张小表应该先驱动”。这个过程比背任何公式都管用。