企业官网建设流程全解析

做数据库作业做到第九章，很多人的体验是从“写SQL很爽”突然变成“看执行计划很懵”。关系查询处理和查询优化这一章，既要理解数据库内部怎么执行一条查询，又要会用手工方式估算代价和改写查询树，作业题往往看起来不复杂，真正动手却到处是坑：选择下推该推几个关系、投影到底能不能动、代价公式里哪些因子要算、两个表做连接到底用哪种算法，一步错后面全错。

这篇文章不按某个特定教材的题号去讲答案，而是把这章课后习题里高频出现的几类题型拆开：关系代数优化、代价估算、连接策略选择、综合执行计划推导，每一类都给一套可以直接照着做的判断流程和计算口径。无论你是正在赶作业，还是在准备考试，都可以拿这篇文章当复习提纲。

1. 这章习题到底在考什么：先建立一条知识主线

1.1 第九章在整本数据库教材里的位置

前面章节讲的是怎么设计表、怎么写SQL、怎么用视图和索引，也就是“用户视角”的数据库。到了第九章，视角切换到数据库系统内部：一条SQL语句交进去之后，系统到底经历了什么才把结果返回给你。

这一过程通常被拆成四个阶段：

1. 语法分析与翻译：检查SQL语法、语义合法性，把SQL转换成关系代数表达式或等价的分析树；
2. 逻辑优化：也叫代数优化，利用关系代数的等价变换规则，把执行起来很笨的表达式改成更聪明的形式；
3. 物理优化：为每一个操作选择具体的算法，比如全表扫描还是索引扫描、嵌套循环连接还是哈希连接，同时确定操作之间的执行顺序；
4. 执行：按照选好的执行计划真正读写数据，返回结果。

课后习题的命题逻辑很简单：你既然学了这条主线，就得能在这条主线上的任何一环做手工推演。所以题目类型基本可以归纳成下面这张表。

1.2 为什么这章作业容易出现“背会了但不会做”

一个很普遍的现象是：不少同学把等价变换规则倒背如流，结果做题时先把所有选择一股脑下推，再把投影也全部下推，最后发现优化完的查询树反而不能执行。原因在于，规则本身是“允许做什么”，而不是“应该做什么”。课后题真正想训练的是判断力：哪一步变换能减少中间数据量，哪一步变换只是形式好看但没有任何实际收益，哪一步变换甚至会把连接条件拆坏。

后面所有内容都会围绕这个判断力展开。先记住结论：优化不是套公式，而是在每一步都估算一遍“这条路径要碰多少块数据”。有了这个意识，再看下面的题型就有方向了。

2. 关系代数优化题：把SQL翻译成查询树，再按规则“瘦身”

2.1 为什么一定先要会画查询树

关系代数优化的标准操作对象是查询树，也叫关系代数语法树。树的结构并不复杂：叶子节点是参与查询的基本关系，内部节点是关系代数操作，从叶子到根的方向就是数据流动的方向。

画查询树最大的好处是强迫你显式表达操作顺序。SQL是声明式的，你告诉数据库“要什么”，但不告诉它“先干什么后干什么”。而关系代数是过程式的，任何一棵查询树都对应一个具体的执行次序。课后题让你画查询树，本质就是让你把SQL里面隐含的操作顺序摊开来看。

举个例子，很多人第一次画树时会犯错，把WHERE子句里的条件全部放在一个选择节点里，然后挂到所有表的笛卡尔积之上。这样做并没有语法错误，但它把许多本来可以先过滤的小关系硬生生拖到了大连接之后，逻辑上可行，性能上很糟。查询树优化的目标，就是在不改变语义的前提下，把这些过滤操作尽量往叶子方向推。

2.2 两类最核心的等价变换规则

课后习题里真正高频用到的规则，基本可以压缩成两条主线。

第一是选择下推。选择操作是最“便宜”的过滤手段，它能直接减少一个关系中的元组数。能往下推的选择就往下推，这就是“选择尽早执行”原则。但要注意两点：一是选择条件只能下推到它用到的那些属性所在的关系上，二是如果选择条件涉及的属性分属多个关系，通常要用“选择分裂”把它拆成多个选择再分别下推。比如 A=1 AND B>2 如果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.Sage<20 AND C.Credit>2 AND 连接条件) └─ 笛卡尔积 ├─ 笛卡尔积 │ ├─ Students │ └─ SC └─ Courses

第二步，开始优化。先把选择条件拆开：

• S.Sage<20 只涉及 Students，可以下推到 Students 叶子上；
• C.Credit>2 只涉及 Courses，可以下推到 Courses 叶子上；
• 两个等值连接条件留在连接节点上，分别变成 S.Sno=SC.Sno 和 SC.Cno=C.Cno。

第三步，处理投影。最终需要 Sname，但连接过程必须保留 S.Sno、SC.Sno、SC.Cno、C.Cno。所以把投影下推到连接之上的同时，在三个叶子节点上方分别加上“只保留必要属性”的投影。

优化后的查询树结构变成：

投影(Sname) └─ 连接(SC.Cno=C.Cno) ├─ 投影(S.Cno) │ └─ 连接(SC.Sno=S.Sno) │ ├─ 投影(Sno,Sname)后选择(Sage<20) │ │ └─ Students │ └─ 投影(Sno,Cno) │ └─ SC └─ 投影(Cno)后选择(Credit>2) └─ Courses

这棵树的执行路径比初始树清晰得多：先过滤出年轻学生和学分较高的课程这两个小集合，再做两次连接，中间数据量小了一个数量级。像这种题，阅卷时重点看的是你能否把选择正确拆分并下推到对应叶子，以及投影属性集合是否保留连接键。

2.4 下推时容易翻车的几种情况

第一，外连接不能随便下推。选择下推到外连接的“保留侧”时语义会变。例如 LEFT OUTER JOIN 右表上的过滤条件下推，可能把不匹配的右表元组过滤掉，导致左表保留行数变化。遇到外连接，老老实实在连接结果之上再做选择。

第二，含有聚合、GROUP BY、DISTINCT 时，投影下推要格外小心。去重和分组依赖完整属性集合，在不知道分组键之前，投影不能把排序或分组属性剪掉。

第三，子查询和外连接有时会改变规则适用范围。很多教材在讲规则时会注明“给定关系集合不相交，且结果不依赖元组顺序”。作业题一般不会故意出这种极端情况，但面试和考试中喜欢用这类边界条件来区分学生是背规则还是懂语义。

3. 代价估算题：IO是主角，别被“看起来快”带偏

3.1 代价模型的基本盘：为什么只看IO次数

优化器选物理计划时的代价一般由三部分构成：IO代价、CPU代价、通信代价。在单机数据库场景下，磁盘IO通常是最大瓶颈，所以绝大多数教材和课后题都默认“按磁盘访问的块数比较不同方案的优劣”。

这里的逻辑和普通程序不一样。普通程序里一次运算的成本是“算了几次CPU指令”，但数据库里一条查询如果涉及全表扫描，可能要把几百万行数据从磁盘搬到内存。磁盘随机读一次要十毫秒级别的寻道时间，哪怕是顺序读，吞吐量也远低于内存运算。所以课余题设一个极端简化模型：内存无限大、磁盘块大小固定、每次IO读一个块。在这个模型下，谁的块数少谁就快。

我建议做题时保留这个口径，不要自己去加“CPU运算还要考虑hash函数耗时”之类的细节，那是论文级讨论，课后题不会考。先把块数算对，再谈精细化。

3.2 频度最高的几个代价参数

不同教材记号略有差异，但核心参数就那么几个：

还有一个容易忽略的概念是聚簇索引和非聚簇索引的区别。聚簇索引的索引顺序与表数据物理顺序一致，所以按聚簇索引取一批连续键值时，命中的数据集中在一块块连续的数据块上；非聚簇索引的叶子节点只存指向数据行的指针，命中多少个元组就要去抓多少次数据块。这个差异直接导致两种索引在范围查询下的代价天差地别。

3.3 一道完整的访问路径比较题

来看一道非常典型的课后题目，几乎每本教材第九章后面都有类似变体。

关系R有 n_R=20000 个元组，每块容纳 f_R=20 个元组，则 b_R=20000/20=1000 块。查询为SELECT * FROM R WHERE a < 10，已知满足条件的元组占 10%，即 2000 个元组。

方案A：全表扫描。顺序读一遍R的全部1000个块，代价为1000块IO。

方案B：在属性a上建聚簇索引，索引高度 h=3。先用索引定位到第一个满足条件的键值，再从聚簇表中读取命中的元组。10%的元组是2000行，2000除以每块20行，得到100块。总代价约 h+100=103块IO。

方案C：在属性a上建非聚簇索引，同样 h=3。索引定位后，2000个满足条件的元组各自散落在各个数据块中，理论上每次取一个指针再去读一个块，极端情况下要读取 2000 次数据块。总代价约 3+2000=2003块IO。

比较结果很有意思：看起来“用索引”总是比全表扫描快，在聚簇索引下确实如此，但非聚簇索引在10%的选择率下反而比全表扫描慢一倍。原因很简单，非聚簇索引的命中元组在物理块上不连续，2000次随机单块IO的开销远大于全表1000块的顺序IO。

3.4 选择率变化时结论会反转

如果把这个题改一下，把选择率从10%提高到50%，也就是10000个元组满足条件：

• 聚簇索引代价：3+10000/20=503块IO；
• 非聚簇索引代价：3+10000≈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_R=10000个元组、b_R=100块，S有n_S=5000个元组、b_S=50块，每块100个元组，内存缓冲区只留少量块给结果，不考虑中间结果写回。

简单嵌套循环连接：外层R的每个元组都要扫一遍内层S的全部块。代价为 n_R×b_S+b_R=10000×50+100，约500100块IO。这个数字说明为什么真实数据库几乎不用这种原始算法。它只在外层极小、内层可以整体放进内存时才勉强能用。

块嵌套循环连接：不是按外层元组循环，而是按外层块循环。把R的一个块读入内存，再让S的每一块与之匹配。代价为 b_R×b_S+b_R=100×50+100=5100块IO。这个数量级比简单嵌套循环好了近两个数量级，原因是减少了内层重复扫描的次数。

排序合并连接：如果R和S已经按连接键有序，代价就是两边各扫描一遍，b_R+b_S=150块IO。如果无序，还要加上两个关系各自排序的代价。外部排序的IO量大约是关系本身的2到3倍，所以无序时排序合并并不便宜。这个算法最适合“两侧数据量差不多，且连接键本身有序”的场景。

哈希连接：先把较小的关系S读出来构建哈希表，代价是读一遍S共50块；再读一遍R去探测哈希表，共100块。理想情况下总代价约150块IO。若内存不够需要把哈希桶写回磁盘再读取，课后题常用 3×(b_R+b_S) 来估算，即约450块IO。哈希连接的优势是无需预先排序，对等值连接非常友好，也是很多数据库引擎里的默认连接算法。

三种算法放在一起对比：

单看这个例子，哈希连接和排序合并明显优于嵌套循环；如果S和R已经有序，排序合并甚至可以和哈希打个平手。课后题让你“为每个连接选算法”时，答案不是说哈希一定最好，而是要根据给定条件判断：数据有序没有、内存够不够大、连接是不是等值。

4.3 什么时候嵌套循环反而更合适

很多人学完哈希连接后，容易形成“哈希无敌”的印象。但在真实系统里，嵌套循环连接依然大量存在。原因有几个：一是嵌套循环不要求等值条件，非等值连接如 R.a > S.b 只能用嵌套循环；二是当外层关系经过过滤后非常小，比如只有几个元组时，嵌套循环的 IO 代价是“几个元组 × 内表块数”，可能比先把两个大表都哈希一遍更划算；三是哈希连接对数据分布敏感，如果连接键严重偏斜，哈希桶可能溢出，而嵌套循环的行为反而稳定。

所以做题时，不要只背一个最优算法，要会描述“在什么条件下哪个方案好”。比如外层只有10个元组、内层有500块时，简单嵌套循环的代价大约 10×500+1=5001块，这时它未必比哈希差太多。考试或作业里这类情景题，考察的就是这种条件化判断。

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;

给定统计信息：

• Student：10000个元组，每块100行，共100块；CS系学生占5%，即500人；
• SC：50000个元组，每块100行，共500块；
• Course：200个元组，每块50行，共4块；Credit=2的课程占20%，即40门。

5.2 第一步：逻辑层面的手工优化

先写初始查询树，再逐步优化。这一步可以把第2节的规则重新走一遍：

• 把 Sdept='CS' 下推到 Student 叶子节点，Student 先变成500行的临时结果，约5块；
• 把 Credit=2 下推到 Course 叶子节点，Course 变成40行的临时结果，不到1块；
• 投影下推：最终只需要 Sname、Cname，但连接过程要保留 Sno 和 Cno，所以三个子树上的投影属性集合分别为：
  • Student：Sno, Sname；
  • SC：Sno, Cno；
  • Course：Cno, Cname。

优化后的关系代数表达式大致是：

π(Sname,Cname)( (σ(Sdept='CS')(Student)) ⋈(Sno) (SC ⋈(Cno) σ(Credit=2)(Course)) )

5.3 第二步：确定中间结果大小，决定连接顺序

这里要先估算中间结果，不能盲目选择“先连接Student和Course”，因为两者之间没有直接连接条件，强行连接会生成笛卡尔积。课后题出现这个坑的概率非常高。所以连接顺序第一步就是看图找边：Student和SC通过Sno连接，SC和Course通过Cno连接，得到一条链 Student→SC→Course。

再估算中间结果大小。CS系有500个学生，每个CS学生平均选若干门课，假设选课记录分散在SC中。SC有50000行，学生总数10000人，平均每人5门课；CS学生的选课记录大致按比例估算为500×5=2500行，这里按中间结果约2500行估算，约25块。这个数量远小于两张大表直接连接的规模。

因此连接顺序应该是：先连接Student和SC得到CS学生选课记录，再与Course中的低学分课程连接。左深树天然符合这个顺序。

5.4 第三步：为每个操作选物理算法

开始选择执行策略：

• Student 上执行 σ(Sdept='CS')。全表扫描100块可以得到500行CS学生，代价100块IO；如果Sdept上有聚簇索引且CS系比例5%，索引定位加读取命中数据约3+5=8块IO。考虑说明优化器会倾向后者。为保守起见，综合题里可以写“假设Sdept无索引，则全表扫描100块”。

• SC 与 CS学生连接。CS学生500人，为每个学生到SC中查找选课记录。如果SC.Sno上有索引，用索引嵌套循环连接，内层按索引查找约几十次IO；如果SC.Sno上没有索引，就只能顺序扫描SC全部500块，构建哈希或做块嵌套循环。两种方案都合理，但要能写清楚为什么选它。我这里选择“无索引时全表扫描SC再建哈希”，总代价500块扫描加连接输出约25块，远低于嵌套循环下对50000行逐一遍历。

• 与 Course 连接。Credit=2的课程只有40门，可以把40门课程先建成哈希表放在内存，然后流式读取中间结果2500行逐个探测，Course的4块扫描成本几乎可以忽略。

整个执行计划的读盘量约为：Student扫描100块 + SC扫描500块 + 中间结果写读约50块 + Course扫描4块，合计650块上下。对比不做任何优化时“三个关系先做笛卡尔积再过滤”的方案，读盘量少了两三个数量级，优化意义一目了然。

5.5 综合题的标准答题结构

这种题阅卷最看重的是过程，不是最终答案。推荐的答题结构是四段式：

1. 写SQL对应的关系代数或查询树，说明你理解查询语义；
2. 做逻辑优化，标出每一条选择下推和投影裁剪的依据；
3. 估算各阶段中间结果大小，说明连接顺序为什么这么排；
4. 为每个操作选算法并给出IO代价汇总。

按照这套结构写，即使某一步估算不准，阅卷人也能看出你的思维链路是完整的。最怕的是只扔一个“最终执行计划”上去，中间过程全空，那既无法验证你是否真的会做，也拿不到步骤分。

6. 课后习题的常见失分点与自查清单

6.1 阅卷视角下最典型的失分点

把前面几章内容放在一起，我总结出六个高频错误，覆盖作业和考试。

1. 选择下推的顺序错了。先下推投影、后下推选择，或者把所有选择合并成一个再推，这两种做法不能说必然错，但很容易在中间某一步丢掉必要属性或把连接条件弄碎。推荐固定顺序：先拆选择并下推，再处理投影。

2. 投影集合漏了连接键。投影下推后只保留输出列，没有保留连接属性，查询树语义已经错误。这条几乎是投影类题目失分率最高的一项。

3. 把选择条件误当成连接条件。连接条件必须连接两个关系中的属性，选择条件是单关系上的过滤。如果连接节点上挂了单表属性条件，要么没下推干净，要么把连接做成了先连接再过滤，都有问题。

4. 代价估算的单位混乱。有的同学算全表扫描用块数，算索引扫描却用元组数，最后数字相加，物理意义不明。做题时统一用“块IO次数”作为单位，所有中间量先换算成块。

5. 忽略题目中的前提假设。明明说“关系已按连接键有序”，排序合并代价就是一遍扫描，用哈希反而多算一遍构建代价。读题时先圈出排序、内存、索引这类前提词。

6. 连接顺序没有理由。很多同学连接顺序靠直觉，题目问“为什么”，只写“因为这样快”，没有任何估算支撑。至少要写一句“先连接后中间结果约X块，而另一种顺序的中间结果是Y块，所以选前者”，这比抽象的理由有力得多。

6.2 交作业前用这张清单自查

我建议每做完一道综合题，都按下面的顺序过一遍：

如果哪一项没通过，不要急着改数字，先回到查询树重新画一遍。绝大多数综合题的错误都写在树里，树对了，后续的代价计算和算法选择才可能对。

6.3 从作业到实践：这些技巧的真实用途

别以为这章作业只是在应付考试。数据库优化器的核心逻辑，和你在作业里手工做的事是一样的。比如一条慢查询让你头疼，你先看执行计划里有没有全表扫描，再检查WHERE条件里的列有没有索引，这本质上就是“把选择下推”加“选对访问路径”。再比如多表连接时发现中间结果爆炸，你想办法调整JOIN顺序或者改成小表驱动大表，这就是左深树与连接顺序的实际体现。

唯一的不同是，优化器能枚举的计划数量是你的几千倍，还能基于统计信息自动选；而你能做的是在SQL层面理解系统为什么会选一个糟糕的计划，然后通过重写查询、加索引或调整表结构让它走对路。这章作业培养的，恰恰就是这种“读执行计划”的能力。

最后说一个个人习惯：每做完一道优化综合题，我会把优化前后的查询树并排抄一遍，在每一层节点旁边标注“这里减少了多少块IO”。坚持做几道之后，你会明显感觉到自己看执行计划不再发怵，写多表SQL时也会不自觉地想“哪张小表应该先驱动”。这个过程比背任何公式都管用。