第 15 章 - 查询优化 (Query Optimization)

第 10 章的基本规划器使用一种简单算法创建查询计划。遗憾的是，这些计划往往会产生远多于必要数量的块访问，基本原因有两个：操作执行顺序并不理想，并且它们没有利用第 12 到 14 章中的索引化、物化或多缓冲实现。

本章考察规划器如何解决这些问题并生成高效计划。这项任务称为查询优化 (query optimization)。一个查询的最高效计划可能比朴素计划快几个数量级，这正是数据库引擎能在合理时间内响应查询，还是完全不可用之间的差别。因此，良好的查询优化策略是每个商业数据库系统的重要组成部分。

15.1 等价查询树 (Equivalent Query Trees)

如果一个 SQL 查询无法区分两张表，那么这两张表就是等价的。也就是说，两张等价表包含完全相同的记录，虽然记录顺序不一定相同。如果两个查询的输出表总是等价的，不管数据库内容如何，那么这两个查询就是等价的。本节考察关系代数查询之间的等价性。由于这些查询可以表示成树，两个查询之间的等价性通常可以看作它们的树之间的一种转换。下面几小节考察这些转换。

15.1.1 重排乘积 (Rearranging Products)

令 T1 和 T2 为两张表。回忆一下，T1 与 T2 的乘积是一张包含 T1 与 T2 中所有记录组合的表。也就是说，只要 T1 中有记录 r1，T2 中有记录 r2，那么组合记录 (r1, r2) 就在输出表中。注意，这条组合记录本质上与 (r2, r1) 相同，因为记录中字段出现的顺序并不重要。而 (r2, r1) 正是 T2 与 T1 的乘积产生的记录，因此 product 操作符必须是可交换的。也就是说：

product(T1, T2) == product(T2, T1)

类似的论证（见练习 15.1）可以说明 product 操作符也是可结合的。也就是说：

product(product(T1, T2), T3) == product(T1, product(T2, T3))

从查询树角度看，第一个等价性会交换 product 节点的左右子节点。第二个等价性适用于两个 product 节点相邻的情况。此时，内部 product 节点从外部 product 节点的左子节点移动为其右子节点；其他子节点的顺序保持不变。图 15.1 展示了这些等价性。

这两个等价性可以反复用于转换由 product 节点组成的树。例如，考虑图 15.2，它由对应如下查询的两棵树组成：

select SName
from STUDENT, ENROLL, SECTION, COURSE, DEPT

图 15.2a 中的树由基本规划器创建。把这棵树转换成图 15.2b 中的树需要两步。第一步把交换律应用到 SECTION 之上的 product 节点；第二步把结合律应用到 DEPT 之上的 product 节点。

事实上，可以证明（见练习 15.2），可以使用这两条规则把任意 product 节点树转换为具有相同节点的任意其他树。也就是说，乘积操作可以按任意顺序执行。

图 15.1 与 product 操作符有关的等价性 (Equivalences involving the product operator)

(a) product 操作符是可交换的；(b) product 操作符是可结合的。

图 15.2 重排 product 节点以产生等价查询树 (Rearranging product nodes to produce an equivalent query tree)

(a) 基本规划器产生的树；(b) 应用结合律和交换律转换后的结果。

15.1.2 拆分选择 (Splitting Selections)

假设选择谓词 p 是两个谓词 p1 和 p2 的合取。可以分两步找到满足 p 的记录：首先找到满足 p1 的记录，然后从这个集合中找到满足 p2 的记录。换句话说，以下等价性成立：

select(T, p1 and p2) == select(select(T, p1), p2)

从查询树角度看，这个等价性用一对 select 节点替换单个 select 节点；见图 15.3。

反复应用这个等价性，可以把查询树中的单个 select 节点替换为多个 select 节点，谓词中的每个合取项对应一个节点。此外，由于谓词的合取项可以任意重排，这些 select 节点可以以任意顺序出现。

拆分 select 节点的能力对查询优化极其有用，因为每个“更小的” select 节点都可以独立放置在查询树中的最优位置。因此，查询优化器会努力把谓词拆分成尽可能多的合取项。它通过把每个谓词转换为合取范式 (conjunctive normal form, CNF) 来做到这一点。如果一个谓词是若干子谓词的合取，并且这些子谓词都不包含 AND 操作符，那么该谓词就是 CNF。

CNF 谓词中的 AND 操作符总是位于最外层。例如，考虑如下 SQL 查询：

select SName from STUDENT
where (MajorId=10 and SId=3) or (GradYear=2018)

按上述写法，where 子句谓词不是 CNF，因为 AND 操作符位于 OR 操作符内部。不过，总是可以使用德摩根律把 AND 操作符移动到最外层。在这个例子中，得到如下等价查询：

select SName from STUDENT
where (MajorId=10 or GradYear=2018) and (SId=3 or GradYear=2018)

这个查询的谓词有两个合取项，现在可以拆分。

图 15.3 拆分 select 节点 (Splitting a select node)

15.1.3 在树中移动选择 (Moving Selections Within a Tree)

下面的查询检索所有主修数学的学生姓名：

select SName from STUDENT, DEPT
where DName = 'math' and MajorId = DId

它的 where 子句谓词是 CNF，并且包含两个合取项。图 15.4a 展示基本规划器创建的查询树，这里修改为包含两个 select 节点。先考虑 DName 上的选择。它下面的 product 节点输出 STUDENT 和 DEPT 记录的所有组合；随后 select 节点只保留那些 DName 值为 "math" 的组合。如果先从 DEPT 中选出数学系记录，再返回所有 STUDENT 记录与该记录的组合，会得到完全相同的记录集合。换句话说，由于这个选择只应用于 DEPT 表，因此可以把该选择“下推”到乘积内部，得到图 15.4b 中的等价树。

现在考虑连接谓词 MajorId = DId。无法把这个选择下推到乘积内部，因为该谓词提到来自 STUDENT 和 DEPT 的字段。例如，把选择推到 STUDENT 之上会产生无意义查询，因为选择会引用 STUDENT 中不存在的字段。

下面的等价性概括了上述讨论。当谓词 p 只引用 T1 的字段时，该等价性成立：

select(product(T1, T2), p) == product(select(T1, p), T2)

图 15.5 展示了这个等价性。

这个等价性可以反复应用于一个 select 节点，把它尽可能向查询树下方推。例如，考虑图 15.6。图 (a) 中的查询返回 2018 年某门数学课不及格的学生姓名。图 (b) 和图 (c) 展示该查询的两棵等价树。图 15.6b 展示基本规划器创建的查询树。图 15.6c 展示拆分 select 节点并把较小的 select 节点向树下方推之后得到的查询树。

图 15.5 的等价性也可以反向应用，把 select 节点向树上方移动，越过一个或多个 product 节点。此外，很容易证明，一个 select 节点总是可以在任意方向上越过另一个 select 节点，并且只要语义上有意义，select 节点也可以越过 project 或 groupby 节点（见练习 15.4）。因此，只要 select 节点的谓词只提到底层子树的字段，就可以把该节点放在查询树中的任何位置。

图 15.4 把 select 节点向查询树下方推 (Pushing a select node down the query tree)

图 15.5 把 select 节点推入 product 内部 (Pushing a select node inside a product)

图 15.6 把多个选择向查询树下方推 (Pushing several selections down a query tree)

(a) SQL 查询；(b) 基本规划器创建的查询树；(c) 下推 select 节点后得到的查询树。

15.1.4 识别连接操作符 (Identifying Join Operators)

回忆一下，join 操作符是通过 select 和 product 操作符定义的：

join(T1, T2, p) == select(product(T1, T2), p)

这个等价性断言，可以把一对 select-product 节点转换为单个 join 节点。例如，图 15.7 展示了对图 15.6c 中的树执行这种转换后的结果。

图 15.7 用 join 节点替换图 15.6c 中的 select-product 节点 (Replacing the select-product nodes in Figure 15.6c with join nodes)

15.1.5 添加投影 (Adding Projections)

可以在查询树中任意节点之上添加一个 project 节点，只要其投影列表包含该节点祖先所提到的所有字段。这个转换通常用于在执行物化时减小查询树中节点输入的大小。

例如，图 15.8 展示了图 15.7 的查询树，其中添加了额外的 project 节点，以尽早消除字段。

图 15.8 向图 15.7 的查询树添加投影 (Adding projections to the query tree of Figure 15.7)

15.2 查询优化的必要性 (The Need for Query Optimization)

给定一个 SQL 查询，规划器必须为它选择合适的计划。这个计划生成活动包含两个步骤：

• 规划器选择与该查询对应的关系代数查询树。
• 规划器为查询树中的每个节点选择一种实现。

一般来说，一个 SQL 查询可以有许多等价查询树，而树中的每个节点又可以用几种方式实现。因此，规划器可能有许多候选计划可供选择。如果规划器能选择最高效的计划当然很好，但这是否必要？毕竟，寻找最佳计划可能需要大量工作。在同意做这些工作之前，你应该确信它确实值得。使用第 10 章中的基本规划算法到底有什么问题？

事实证明，同一个查询的不同计划可能具有极其不同的块访问次数。举例来说，考虑图 15.9 中的两棵查询树。图 (a) 是一个 SQL 查询，用于检索 Joe 在 2020 年获得的成绩。图 (b) 展示基本规划器创建的查询树，图 (c) 展示一棵等价树。

考虑图 (b) 中的计划。使用图 7.8 中的统计数据，可以如下计算该计划的成本：STUDENT 和 SECTION 之间的乘积有 45,000 * 25,000 = 1,125,000,000 条记录，并且需要 4500 + (45,000 * 2500) = 112,504,500 次块访问。随后与 ENROLL 的乘积需要 112,504,500 + (1,125,000,000 * 50,000) = 56,250,112,504,500 次块访问。select 和 project 节点不需要额外块访问。因此，这个计划需要超过 56 万亿次块访问！如果假设每次块访问只需 1 ms，数据库引擎也要约 1780 年才能回答这个查询。

现在考虑图 (c) 中的查询树。假设名为 "joe" 的学生只有一名。在这种情况下，STUDENT 上的选择需要 4500 次块访问，并输出 1 条记录。与 ENROLL 的连接需要 4500 + (1 * 50,000) = 54,500 次块访问，并输出 34 条记录。与 SECTION 的连接需要 54,500 + (34 * 2500) = 139,500 次块访问。按每次块访问 1 ms 计算，执行这个计划大约需要 2.3 分钟。

成本从 1780 年降到 2.3 分钟，这非常惊人，也说明基本规划算法完全没有价值。没有客户端能等上千年才得到查询答案。如果数据库引擎要有用，其规划器就必须足够精巧，能够构造合理的查询树。

虽然 2.3 分钟并不是完全无法接受的执行时间，但规划器还可以通过为查询树中的节点使用其他实现来做得更好。再次考虑图 (c) 中的查询树，并假设 ENROLL 在 StudentId 上有索引。那么图 15.10 中的计划就是可能的。

该图中的大多数计划都使用第 10 章中的基本计划类。例外是 p4 和 p7。计划 p4 执行索引连接。对每条选中的 STUDENT 记录，它会搜索 StudentId 上的索引，以找到匹配的 ENROLL 记录。计划 p7 使用多缓冲乘积执行连接。它物化右侧表（即 2020 年的课程节次），把这些记录分成 chunk，并执行 p4 与这些 chunk 的乘积。

计算一下该计划需要的块访问。计划 p2 需要 4500 次块访问，并输出 1 条记录。索引连接对匹配 Joe 的 STUDENT 记录的 34 条记录，各访问一次 ENROLL；也就是说，该连接需要额外 34 次块访问，并输出 34 条记录。计划 p6（找到 2020 年的节次）需要 2500 次块访问，并输出 500 条记录。多缓冲乘积物化这些记录，需要额外 50 个块来创建一个 50 块的临时表。假设至少有 50 个缓冲区可用，这张临时表可以放入单个 chunk，因此乘积还需要 50 次块访问来扫描临时表，外加计算左侧记录的成本。其余计划不需要额外块访问。因此，该计划总共需要 7134 次块访问，耗时略多于 7 秒。

换句话说，在使用同一棵查询树的情况下，仔细选择节点实现把查询执行时间降低了近 20 倍。这个降低幅度可能不如使用不同查询树带来的差异那么夸张，但依然相当大，也很重要。一个商业数据库系统如果比竞争对手慢 20 倍，很难在市场中长期存在。

图 15.9 哪棵查询树会得到更好的计划？(Which query tree results in the better plan?)

(a) SQL 查询；(b) 基本规划器产生的查询树；(c) 一棵等价查询树。

select Grade from STUDENT, SECTION, ENROLL
where SId=StudentId and SectId=SectionId
and SName='joe' and YearOffered=2020

图 15.10 图 15.9c 中树的一个高效计划 (An efficient plan for the tree of Figure 15.9c)

SimpleDB db = new SimpleDB("studentdb");
MetadataMgr mdm = db.mdMgr();
Transaction tx = db.newTx();

// STUDENT 节点的计划
Plan p1 = new TablePlan(tx, "student", mdm);

// STUDENT 之上 select 节点的计划
Predicate joepred = new Predicate(...); // sname='joe'
Plan p2 = new SelectPlan(p1, joepred);

// ENROLL 节点的计划
Plan p3 = new TablePlan(tx, "enroll", mdm);

// STUDENT 和 ENROLL 之间的 indexjoin 计划
Map<String,IndexInfo> indexes = mdm.getIndexInfo("enroll", tx);
IndexInfo ii = indexes.get("studentid");
Plan p4 = new IndexJoinPlan(p2, p3, ii, "sid");

// SECTION 节点的计划
Plan p5 = new TablePlan(tx, "section", mdm);

// SECTION 之上 select 节点的计划
Predicate sectpred = new Predicate(...); // yearoffered=2020
Plan p6 = new SelectPlan(p5, sectpred);

// indexjoin 和 SECTION 之间的多缓冲乘积计划
Plan p7 = new MultiBufferProductPlan(tx, p4, p6);

// 多缓冲乘积之上 select 节点的计划
Predicate sectpred = new Predicate(...); // sectid=sectionid
Plan p8 = new SelectPlan(p7, sectpred);

// project 节点的计划
List<String> fields = Arrays.asList("grade");
Plan p9 = new ProjectPlan(p8, fields);

15.3 查询优化器结构 (The Structure of a Query Optimizer)

给定一个 SQL 查询，规划器必须尝试找到该查询中需要最少块访问的计划。这个过程称为查询优化。

但是规划器如何确定这个计划？穷举所有可能计划会令人望而生畏：如果一个查询有 n 个乘积操作，那么它们有 (2n)!/n! 种排列方式，这意味着等价计划数量随查询规模超指数增长。这还没有考虑放置其他操作符节点的不同方式，以及为每个节点分配实现的不同方式。

查询规划器处理这种复杂性的一种方式，是把优化分为两个独立阶段：

• 阶段 1：寻找该查询最有希望的树，也就是看起来最可能产生最高效计划的查询树。
• 阶段 2：为该树中的每个节点选择最佳实现。

通过独立执行这两个阶段，规划器减少了每个阶段需要做出的选择，使每个阶段更简单、更聚焦。

在这两个优化阶段中，规划器还可以使用启发式规则限制它考虑的树和计划集合，从而进一步降低复杂度。例如，查询规划器通常使用“尽早执行选择”的启发式规则。经验表明，在一个查询的最优计划中，select 节点总是（或几乎总是）被尽可能早地放置。因此，遵循这个启发式规则后，查询规划器就不需要考虑候选查询树中 select 节点的任何其他放置方式。

接下来的两节考察查询优化的两个阶段及其相关启发式规则。

15.4 寻找最有希望的查询树 (Finding the Most Promising Query Tree)

15.4.1 树的成本 (The Cost of a Tree)

查询优化的第一阶段是寻找“最有希望”的查询树，也就是规划器认为会具有最低成本计划的树。规划器无法实际确定最佳树，原因是第一阶段无法获得成本信息。块访问与计划相关，而计划直到第二阶段才会被考虑。因此，规划器需要一种方法，在不实际计算块访问的情况下比较查询树。关键观察是：

• 一个查询中的几乎所有块访问都来自乘积和连接操作。
• 这些操作所需的块访问次数与其输入大小有关。一个例外是索引连接，其成本基本上与被索引表的大小无关；规划器在这个阶段会忽略该例外。

因此，规划器把查询树的成本定义为树中每个 product/join 节点输入大小之和。

例如，计算图 15.9 中两棵查询树的成本。这些树有两个 product 节点，所以应当把每个节点输入的大小相加。结果见图 15.11，并表明第二棵查询树远好于第一棵。

可以把查询树成本看作对其执行时间的一种“粗略快速”近似。该成本不能帮助估算块访问，但能帮助确定两棵树的相对价值。特别是，给定两棵查询树，可以预期最高效计划来自成本较低的树。这个预期并不总是正确（见练习 15.8）。不过，经验表明它大多数时候都是正确的；即使不正确，较低成本树的最便宜计划通常也足够好。

图 15.11 计算两棵查询树的成本 (Calculating the cost of two query trees)

查询树	底部乘积节点输入大小	顶部乘积节点输入大小	树的总成本
图 15.9(b)	45,000 + 25,000	1,125,000,000 + 1,500,000	1,126,570,000
图 15.9(c)	1 + 1,500,000	34 + 25,000	1,525,035

15.4.2 把 Select 节点向树下方推 (Pushing Select Nodes Down the Tree)

规划器使用启发式规则寻找最有希望的查询树。第一个启发式规则涉及树中 select 节点的位置。选择谓词来自 SQL 查询的 where 子句。回忆第 15.1.2 节中的等价性允许规划器把 select 节点放在树中任意位置，只要该谓词在该位置有意义。

哪种 select 节点放置方式会得到最低成本树？select 节点的输出记录数不会多于其输入。因此，如果把 select 节点放在 product 或 join 内部，这些节点的输入很可能更小，树的成本也会降低。这引出了如下启发式规则。

• 启发式规则 1：规划器只需要考虑那些选择被尽可能下推的查询树。

假设完全下推选择之后，查询树中有两个选择相邻。启发式规则 1 并不指定这些选择应该以什么顺序出现。不过，这个顺序不会影响树的成本，因此规划器可以自由选择任意顺序，或把它们组合成单个 select 节点。

启发式规则 1 减轻了规划器的任务，使它无需担心 select 节点放在哪里。给定其他操作符的查询计划后，这些节点的位置就有了明确规定。

15.4.3 用 Join 替换 Select-Product 节点 (Replacing Select-Product Nodes by Join)

考虑一个涉及表 T1 和 T2 字段的连接谓词。当包含该谓词的 select 节点被向树下方推时，它会停在树中的某个特定位置，也就是这样一个 product 节点：T1 出现在其一棵子树中，而 T2 出现在另一棵子树中。这一对 select-product 节点可以替换为单个 join 节点。

• 启发式规则 2：规划器应当把查询树中每一对 select-product 节点替换为单个 join 节点。

虽然这个启发式规则不会改变查询树成本，但它是寻找最佳计划的重要一步。本书已经考察了几种高效的 join 操作符实现。通过识别查询树中的连接，规划器允许这些实现方式在第二阶段优化期间被考虑。

15.4.4 使用左深查询树 (Using Left-Deep Query Trees)

规划器必须选择乘积/连接操作的执行顺序。作为例子，考虑图 15.12。图 (a) 中的 SQL 查询检索 2018 年毕业学生的姓名以及他们修读的数学课程标题。图 (b) 到图 (f) 展示该查询的五棵等价树。

这些树具有不同骨架。图 (b) 到图 (d) 中的树称为左深 (left-deep)，因为每个 product/join 节点的右侧都不包含其他 product/join 节点。类似地，图 (e) 中的树称为右深 (right-deep)。图 (f) 中的树称为浓密树 (bushy)，因为它既不是左深，也不是右深。许多查询规划器采用如下启发式规则：

• 启发式规则 3：规划器只需要考虑左深查询树。

这个启发式规则背后的理由并不明显。例如，考虑图 15.13，它使用图 7.8 的统计数据计算每棵树的成本。图 15.12 中成本最低的树是 bushy 树。而且，那棵树实际上是最有希望的树（见练习 15.9）。那么为什么规划器会故意忽略一大批可能包含最有希望树的树呢？原因有两个。

第一个原因是，即使左深树没有最低成本，它们也倾向于拥有最高效的计划。回想已经见过的连接算法；它们都在连接右侧是存储表时工作得最好。例如，多缓冲乘积需要物化其右侧表，因此当这张表已经是存储表时就不需要额外物化。索引连接也只有在其右侧是存储表时才可能。因此，使用左深树会增加规划器在生成最终计划时能够使用更高效实现的可能性。经验表明，一个查询的最佳左深计划通常要么是最优的，要么已经足够接近最优。

第二个原因是方便。如果一个查询有 n 个 product/join 节点，那么只有 n! 棵左深树，远少于 (2n)!/n! 棵可能树。因此，启发式规则 3 让规划器能够快得多地工作（这很重要），同时陷入坏计划的风险很小。

一棵左深树可以通过按顺序列出其表来指定。第一张表是最底层 product/join 节点左侧出现的表，后续表来自向树上方移动时每个 product/join 节点的右侧。这个顺序称为左深树的连接顺序 (join order)。

例如，图 15.12b 的左深树具有连接顺序 (STUDENT, ENROLL, SECTION, COURSE)，图 15.12c 的树具有连接顺序 (STUDENT, COURSE, SECTION, ENROLL)。因此，启发式规则 3 简化了查询规划器的工作：规划器只需要确定最佳连接顺序。随后，启发式规则 1 到 3 完全确定对应的查询树。

图 15.12 具有不同骨架的等价查询树 (Equivalent query trees having different skeletons)

(a) SQL 查询；(b) 左深查询树；(c) 另一棵左深查询树；(d) 又一棵左深查询树；(e) 右深查询树；(f) bushy 查询树。

select SName, Title
from STUDENT, ENROLL, SECTION, COURSE
where SId=StudentId and SectId=SectionId
and CId=CourseId and GradYear=2018 and DeptId=10

图 15.13 图 15.12 中树的成本 (The cost of the trees in Figure 15.12)

树	较低连接的成本	中间连接的成本	较高连接的成本	总成本
(b)	1,500,900	55,000	30,013	1,585,913
(c)	913	36,700	3,750,000	3,787,613
(d)	25,013	1,500,625	38,400	1,564,038
(e)	25,013	1,500,625	38,400	1,564,038
(f)	1,500,900（左侧连接）	25,013（右侧连接）	30,625	1,556,538

15.4.5 用启发式规则选择连接顺序 (Choosing a Join Order Heuristically)

为给定查询寻找最佳连接顺序，是查询优化过程中最关键的部分。这里的“关键”有两层含义：

• 连接顺序的选择会极大影响所得查询树的成本。图 15.12 中树 (b) 远好于树 (c)，就是一个例子。
• 可能的连接顺序太多，通常不可行逐一检查。特别是，一个提到 n 张表的查询可以有 n! 种连接顺序。

因此，规划器必须非常聪明地选择要考虑哪些连接顺序，避免陷入坏顺序。为确定好的连接顺序，人们发展出两类一般方法：使用启发式规则的方法，以及考虑所有可能顺序的方法。本节考察启发式方法；下一节考虑穷举搜索。

启发式方法以增量方式构造连接顺序。也就是说，规划器首先选择某张表作为连接顺序中的第一张表。然后，它选择另一张表作为连接顺序中的下一张表，并重复此过程，直到连接顺序完整。

下面的启发式规则帮助规划器筛除“显然很差”的连接顺序：

• 启发式规则 4：只要可能，连接顺序中的每张表都应该与先前已经选择的表连接。

换句话说，这个启发式规则指出，查询树中的唯一 product 节点应当对应连接。图 15.12c 中的查询树违反了这个启发式规则，因为它一开始就对 STUDENT 和 COURSE 表取乘积。

为什么违反启发式规则 4 的连接顺序如此糟糕？回忆一下，连接谓词的作用是过滤掉由乘积操作生成的无意义输出记录。因此，当查询树包含非连接乘积节点时，其中间表会继续传播这些无意义记录，直到遇到连接谓词。例如，再次考虑图 15.12c 的查询树。STUDENT 和 COURSE 之间的乘积会产生 11,700 条输出记录，因为数学系的 13 条 COURSE 记录各自重复 900 次（2018 年毕业的每名学生各一次）。当这张输出表与 SECTION 连接时，每条 COURSE 记录都会与它的 SECTION 记录匹配；然而，这些匹配被重复了 900 次。因此，该连接的输出比它本应有的大小大了 900 倍。只有当 ENROLL 被加入连接顺序后，与 STUDENT 的连接谓词才终于发挥作用，消除这种重复。

这个例子说明，涉及乘积节点的查询树输出一开始可能很小，但最终由乘积导致的重复会产生非常高成本的树。因此，启发式规则 4 断言，应尽可能避免乘积操作。当然，如果用户指定的查询没有把所有表完全连接起来，那么乘积节点不可避免。在这种情况下，该启发式规则会确保这个节点尽可能位于树的高处，使重复造成的影响尽可能小。

启发式规则 4 是常用启发式规则。确实可以找到一些查询，其最有希望的查询树违反这个启发式规则（见练习 15.11），但这样的查询在实践中很少出现。

现在需要处理两个问题：应当先选择哪张表，以及应当从可连接表中选择哪张表作为下一张表。这些问题很难。数据库社区提出过许多启发式规则，但对于哪一个最合适并没有太多共识。这里考虑两种合乎逻辑的可能性，称为启发式规则 5a 和 5b：

• 启发式规则 5a：选择产生最小输出的表。

这个启发式规则是最直接、最朴素的方法。它的意图是：由于查询树的成本与其中间输出表大小之和有关，最小化这个和的一种好方法是最小化其中每张表。

在图 15.12a 的查询上使用这个启发式规则。连接顺序中的第一张表会是 COURSE，因为它的选择谓词把它减少到 13 条记录。剩余表由启发式规则 4 决定。也就是说，SECTION 是唯一与 COURSE 连接的表，随后 ENROLL 是唯一与 SECTION 连接的表，最后剩下 STUDENT。得到的查询树见图 15.12d。

另一个启发式规则如下：

• 启发式规则 5b：选择具有最严格选择谓词的表。

启发式规则 5b 来自这样一个观察：选择谓词越位于查询树下方，对成本的影响越大。例如，考虑图 15.12b 的查询树及其 STUDENT 上的选择谓词。该选择谓词显然会减少 STUDENT 记录数量，从而降低其正上方连接节点的成本。但它还有一个更重要的好处：该谓词还把该连接的输出从 1,500,000 条记录减少到仅 30,000 条记录，从而降低树中随后每个连接节点的成本。换句话说，select 节点带来的成本节省会沿树一路向上复合。相比之下，树顶端 COURSE 上的选择谓词影响要小得多。

由于查询树下方的选择谓词对成本影响最大，优化器选择具有最大缩减因子的谓词所在表是合理的。这正是启发式规则 5b 所做的。例如，图 15.12b 的查询树满足这个启发式规则。其连接顺序中的第一张表是 STUDENT，因为它的选择谓词把表缩小 50 倍，而 COURSE 的选择谓词只把它缩小 40 倍。和之前一样，连接顺序中的剩余表由启发式规则 4 决定。

在这个例子中，使用启发式规则 5b 得到的查询树成本低于启发式规则 5a。这很典型。研究（例如 Swami [1989]）表明，尽管启发式规则 5a 很符合直觉并能产生合理查询树，但这些树的成本往往高于启发式规则 5b 产生的树。

15.4.6 通过穷举枚举选择连接顺序 (Choosing a Join Order by Exhaustive Enumeration)

启发式规则 4 和 5 往往能产生好的连接顺序，但并不保证产生最佳连接顺序。如果厂商希望确保其规划器找到最优连接顺序，唯一选择就是枚举所有连接顺序。本节考察这种策略。

一个提到 n 张表的查询最多可以有 n! 种连接顺序。一种著名的算法技术，称为动态规划 (dynamic programming)，可以把寻找最有希望连接顺序所需的时间降低到 O(2^n)。如果 n 合理地小（比如不超过 15 或 20 张表），那么该算法足够高效，可以实际使用。

为了说明这种技术如何节省时间，考虑一个连接大学数据库中全部五张表的查询。其 120 种可能连接顺序中的四种是：

(STUDENT, ENROLL, SECTION, COURSE, DEPT)
(STUDENT, SECTION, ENROLL, COURSE, DEPT)
(STUDENT, ENROLL, SECTION, DEPT, COURSE)
(STUDENT, SECTION, ENROLL, DEPT, COURSE)

前两个连接顺序只在第二张和第三张表上不同。假设我们确定部分连接顺序 (STUDENT, ENROLL, SECTION) 的成本低于 (STUDENT, SECTION, ENROLL)。那么无需进一步计算，就可以推出第一个连接顺序的成本一定低于第二个连接顺序。此外，还能知道第三个连接顺序所需的块访问少于第四个连接顺序。一般来说，任何以 (STUDENT, SECTION, ENROLL) 开头的连接顺序都不值得考虑。

动态规划算法使用一个名为 lowest 的数组变量，它对每个可能的表集合都有一个条目。如果 S 是一个表集合，那么 lowest[S] 包含三个值：

• 涉及 S 中表的最低成本连接顺序。
• 对应该连接顺序的查询树成本。
• 该查询树输出的记录数。

该算法首先计算每个两表集合的 lowest[S]，然后计算每个三表集合，持续下去，直到到达查询中的全部表集合。当 S 是全部表集合时，lowest[S] 的值就是最优连接顺序。

计算两张表的集合 (Computing Sets of Two Tables)

考虑一个两表集合，比如 {T1, T2}。lowest[{T1, T2}] 的值通过计算这样一棵查询树的成本来确定：该树对两张表及其选择谓词执行连接（如果没有连接谓词则执行乘积）。查询树成本是 product/join 节点两个输入大小之和。注意，无论哪张表在前，成本都相同。因此，规划器必须使用其他标准来确定第一张表。一个合理选择是使用启发式规则 5a 或 5b。

计算三张表的集合 (Computing Sets of Three Tables)

考虑一个三表集合，比如 {T1, T2, T3}。可以通过考虑如下连接顺序来计算它们的最低成本连接顺序：

lowest[{T2, T3}] 与 T1 连接
lowest[{T1, T3}] 与 T2 连接
lowest[{T1, T2}] 与 T3 连接

成本最低的连接顺序会保存为 lowest[{T1, T2, T3}] 的值。

计算 n 张表的集合 (Computing Sets of n Tables)

现在假设变量 lowest 已经为每个 n - 1 张表的集合计算完成。给定集合 {T1, T2, ..., Tn}，算法会考虑如下连接顺序：

lowest[{T2, T3, ..., Tn}] 与 T1 连接
lowest[{T1, T3, ..., Tn}] 与 T2 连接
...
lowest[{T1, T2, ..., Tn-1}] 与 Tn 连接

成本最低的连接顺序就是该查询的最佳连接顺序。

作为例子，在图 15.12 的查询上使用动态规划算法。该算法首先考虑所有六个两表集合，如图 15.14a 所示。

每个两表集合都有两个部分连接顺序，列在该集合对应的行中。每个集合的连接顺序按照期望程度列出。在这个例子中，它们具有相同成本，所以按照启发式规则 5a 列出。每个集合中的第一个部分连接顺序被选作后续计算中该集合的代表。

随后，算法考虑所有四个三表集合。图 15.14b 列出了这些集合的部分连接顺序及其成本。每个集合有三个可能连接顺序。连接顺序中的前两张表是图 15.14a 中该集合的最低成本代表。成本按从低到高列出，因此每个集合中的第一个部分连接顺序被选作该集合的代表。

图 15.14c 考虑四表集合。这里有四个连接顺序需要考虑。每个连接顺序中的前三张表代表图 15.14b 中的最低成本连接顺序；第四张表是缺失的那张表。该表说明，连接顺序 (STUDENT, ENROLL, SECTION, COURSE) 是最优的。

注意，在每个阶段，算法必须为每个可能的前缀表集合计算 lowest 的值，因为无法预先知道成本在后续阶段会如何变化。某个阶段成本最高的前缀，可能由于剩余表与它连接的方式，最终产生最低成本的整体连接顺序。

图 15.14 计算图 15.12 的最佳连接顺序 (Calculating the best join order for Figure 15.12)

(a) 所有两表集合：

S	部分连接顺序	成本	记录数
{ENROLL, STUDENT}	(STUDENT, ENROLL) / (ENROLL, STUDENT)	1,500,900 / 1,500,900	30,000
{ENROLL, SECTION}	(SECTION, ENROLL) / (ENROLL, SECTION)	1,525,000 / 1,525,000	1,500,000
{COURSE, SECTION}	(COURSE, SECTION) / (SECTION, COURSE)	25,500 / 25,500	25,000
{SECTION, STUDENT}	(STUDENT, SECTION) / (SECTION, STUDENT)	25,900 / 25,900	22,500,000
{COURSE, STUDENT}	(COURSE, STUDENT) / (STUDENT, COURSE)	1,400 / 1,400	450,000
{COURSE, ENROLL}	(COURSE, ENROLL) / (ENROLL, COURSE)	1,500,500 / 1,500,500	450,000,000

(b) 所有三表集合：

S	部分连接顺序	成本	记录数
{ENROLL, SECTION, STUDENT}	(STUDENT, ENROLL, SECTION) / (SECTION, ENROLL, STUDENT) / (STUDENT, SECTION, ENROLL)	1,555,900 / 3,025,900 / 24,025,900	30,000
{COURSE, ENROLL, STUDENT}	(STUDENT, ENROLL, COURSE) / (COURSE, STUDENT, ENROLL) / (COURSE, ENROLL, STUDENT)	1,531,400 / 1,951,400 / 451,501,400	15,000,000
{COURSE, ENROLL, SECTION}	(SECTION, ENROLL, COURSE) / (COURSE, SECTION, ENROLL) / (COURSE, ENROLL, SECTION)	1,500,500 / 1,550,500 / 450,025,000	1,500,000
{COURSE, SECTION, STUDENT}	(COURSE, SECTION, STUDENT) / (COURSE, STUDENT, SECTION) / (STUDENT, SECTION, COURSE)	25,900 / 475,000 / 22,500,500	22,500,000

(c) 所有四表集合：

连接顺序	成本
(STUDENT, ENROLL, SECTION, COURSE)	1,586,400
(COURSE, SECTION, ENROLL, STUDENT)	3,051,400
(STUDENT, ENROLL, COURSE, SECTION)	16,556,400
(COURSE, SECTION, STUDENT, ENROLL)	24,051,400

15.5 寻找最高效执行计划 (Finding the Most Efficient Plan)

查询优化的第一阶段是寻找最有希望的查询树。第二阶段是把该查询树转换为高效计划。规划器通过为查询树中的每个节点选择一种实现来构造计划。它自底向上选择这些实现，从叶节点开始。自底向上的优点是，当考虑某个给定节点时，规划器已经为它的每棵子树选择了最低成本计划。因此，规划器可以考虑该节点的每种可能实现，使用实现的 blocksAccessed 方法计算该实现的成本，并选择成本最低的实现。

注意，规划器独立于其他节点的实现来选择每个节点的实现。特别是，它不关心某个节点的子树如何实现，只需要知道该实现的成本。节点之间缺乏交互显著降低了计划生成的计算复杂度。如果查询树有 n 个节点，并且每个节点最多有 k 种实现，那么规划器最多需要检查 k * n 个计划，这当然是合理的。

不过，规划器也可以利用启发式规则加速计划生成。这些启发式规则往往与操作有关。例如：

• 启发式规则 6：如果可能，使用 indexselect 实现 select 节点。
• 启发式规则 7：按如下优先级实现 join 节点：
  • 如果可能，使用 indexjoin。
  • 如果某个输入表很小，使用 hashjoin。
  • 否则使用 mergejoin。

还有一个问题需要考虑。每当规划器选择使用物化计划实现某个节点时，它还应当如下向查询树插入 project 节点：

• 启发式规则 8：规划器应当在每个物化节点的子节点处添加 project 节点，以移除不再需要的字段。

启发式规则 8 确保物化实现创建的临时表尽可能小。这很重要，有两个原因：较大的表需要更多块访问来创建，也需要更多块访问来扫描。因此，规划器应当确定物化节点及其祖先会需要哪些字段，并插入 project 节点，从其输入中移除其他字段。

例如，考虑图 15.15 的查询树。这棵树返回 Joe 在 2020 年获得的成绩，并等价于图 15.9 中的树。

图 15.10 的计划选择使用多缓冲乘积实现上方的 join 节点，这是物化实现。启发式规则 8 断言，需要把 project 节点作为该 join 节点的子节点添加到查询树中；这些节点见图 15.15。右侧的 project 节点尤其重要，因为它把临时表大小减少约 75%，从而使算法能使用更少 chunk 运行。

图 15.15 图 15.9 查询的一棵查询树，其中添加了 project 节点 (A query tree for the query of Figure 15.9, with added project nodes)

15.6 结合优化的两个阶段 (Combining the Two Stages of Optimization)

理解查询优化最简单的方式是把它看成两个分离阶段：第一阶段从 SQL 查询构造查询树，第二阶段从查询树构造计划。然而在实践中，这两个阶段常常被结合起来。支持结合优化阶段有两个好理由：

• 方便性：可以直接创建计划，而不必创建显式查询树。
• 准确性：由于计划与查询树同时创建，可能可以用实际块访问来计算树的成本。

本节考察两个结合式优化示例：基于启发式规则的 SimpleDB 优化器，以及基于枚举的“Selinger 风格”优化器。

15.6.1 基于启发式规则的 SimpleDB 优化器 (The Heuristic-Based SimpleDB Optimizer)

SimpleDB 查询优化器由 simpledb.opt 包中的两个类实现：HeuristicQueryPlanner 和 TablePlanner。要在 SimpleDB 中使用这个优化器，必须修改 simpledb.server 包中的 SimpleDB.planner 方法，使其创建 HeuristicQueryPlanner 实例，而不是 BasicQueryPlanner。

HeuristicQueryPlanner 类 (The Class HeuristicQueryPlanner)

HeuristicQueryPlanner 类使用启发式规则 5a 来确定连接顺序。每张表都有一个 TablePlanner 对象。当某张表被加入连接顺序时，它的 TablePlanner 对象会创建对应计划，添加适当的选择和连接谓词，并在可能时使用索引。这样，计划就与连接顺序同时构建。

HeuristicQueryPlanner 的代码见图 15.16。集合 tableinfo 为查询中的每张表包含一个 TablePlanner 对象。规划器首先从该集合中选择（并移除）与最小表对应的对象，并把它的选择计划作为当前计划。然后，它反复从集合中选择（并移除）具有最低成本连接的表。规划器把当前计划发送给该表的 TablePlanner 对象，后者创建并返回连接计划。这个连接计划随后成为当前计划。这个过程持续到集合为空，此时当前计划就是最终计划。

图 15.16 SimpleDB HeuristicQueryPlanner 类的代码 (The code for the SimpleDB class HeuristicQueryPlanner)

public class HeuristicQueryPlanner implements QueryPlanner {
    private Collection<TablePlanner> tableplanners = new ArrayList<>();
    private MetadataMgr mdm;

    public HeuristicQueryPlanner(MetadataMgr mdm) {
        this.mdm = mdm;
    }

    public Plan createPlan(QueryData data, Transaction tx) {
        // 第 1 步，为每张提到的表创建 TablePlanner 对象
        for (String tblname : data.tables()) {
            TablePlanner tp = new TablePlanner(tblname, data.pred(),
                                               tx, mdm);
            tableplanners.add(tp);
        }

        // 第 2 步，选择大小最低的计划作为连接顺序起点
        Plan currentplan = getLowestSelectPlan();

        // 第 3 步，反复向连接顺序添加计划
        while (!tableplanners.isEmpty()) {
            Plan p = getLowestJoinPlan(currentplan);
            if (p != null)
                currentplan = p;
            else // 没有适用的连接
                currentplan = getLowestProductPlan(currentplan);
        }

        // 第 4 步，按字段名投影并返回
        return new ProjectPlan(currentplan, data.fields());
    }

    private Plan getLowestSelectPlan() {
        TablePlanner besttp = null;
        Plan bestplan = null;
        for (TablePlanner tp : tableplanners) {
            Plan plan = tp.makeSelectPlan();
            if (bestplan == null ||
                plan.recordsOutput() < bestplan.recordsOutput()) {
                besttp = tp;
                bestplan = plan;
            }
        }
        tableplanners.remove(besttp);
        return bestplan;
    }

    private Plan getLowestJoinPlan(Plan current) {
        TablePlanner besttp = null;
        Plan bestplan = null;
        for (TablePlanner tp : tableplanners) {
            Plan plan = tp.makeJoinPlan(current);
            if (plan != null && (bestplan == null ||
                plan.recordsOutput() < bestplan.recordsOutput())) {
                besttp = tp;
                bestplan = plan;
            }
        }
        if (bestplan != null)
            tableplanners.remove(besttp);
        return bestplan;
    }

    private Plan getLowestProductPlan(Plan current) {
        TablePlanner besttp = null;
        Plan bestplan = null;
        for (TablePlanner tp : tableplanners) {
            Plan plan = tp.makeProductPlan(current);
            if (bestplan == null ||
                plan.recordsOutput() < bestplan.recordsOutput()) {
                besttp = tp;
                bestplan = plan;
            }
        }
        tableplanners.remove(besttp);
        return bestplan;
    }

    public void setPlanner(Planner p) {
        // 用于规划视图；为简单起见，这段代码没有处理。
    }
}

TablePlanner 类 (The Class TablePlanner)

TablePlanner 类的对象负责为单张表创建计划；其代码见图 15.17。TablePlanner 构造函数为指定表创建一张表，获取该表的索引信息，并保存查询谓词。该类具有公有方法 makeSelectPlan、makeProductPlan 和 makeJoinPlan。

makeSelectPlan 方法为其表创建选择计划。该方法首先调用 makeIndexSelect 来确定能否使用索引；如果可以，则创建一个 IndexSelect 计划。随后该方法调用 addSelectPred，确定适用于该表的谓词部分，并为其创建选择计划。

makeProductPlan 方法向表计划添加选择计划，然后创建 MultiBufferProductPlan，实现指定计划与该计划的乘积。理想情况下，该方法应创建 hashjoin 计划，但 SimpleDB 不支持哈希连接；见练习 15.17。

makeJoinPlan 方法首先调用谓词的 joinPred 方法，以确定指定计划与该计划之间是否存在连接。如果不存在连接谓词，该方法返回 null。如果存在连接谓词，该方法会检查能否创建 IndexJoinScan。如果不能，则通过创建多缓冲乘积并随后执行选择来实现连接。

图 15.17 SimpleDB TablePlanner 类的代码 (The code for the SimpleDB class TablePlanner)

class TablePlanner {
    private TablePlan myplan;
    private Predicate mypred;
    private Schema myschema;
    private Map<String,IndexInfo> indexes;
    private Transaction tx;

    public TablePlanner(String tblname, Predicate mypred,
                        Transaction tx, MetadataMgr mdm) {
        this.mypred = mypred;
        this.tx = tx;
        myplan = new TablePlan(tx, tblname, mdm);
        myschema = myplan.schema();
        indexes = mdm.getIndexInfo(tblname, tx);
    }

    public Plan makeSelectPlan() {
        Plan p = makeIndexSelect();
        if (p == null)
            p = myplan;
        return addSelectPred(p);
    }

    public Plan makeJoinPlan(Plan current) {
        Schema currsch = current.schema();
        Predicate joinpred = mypred.joinSubPred(myschema, currsch);
        if (joinpred == null)
            return null;
        Plan p = makeIndexJoin(current, currsch);
        if (p == null)
            p = makeProductJoin(current, currsch);
        return p;
    }

    public Plan makeProductPlan(Plan current) {
        Plan p = addSelectPred(myplan);
        return new MultiBufferProductPlan(current, p, tx);
    }

    private Plan makeIndexSelect() {
        for (String fldname : indexes.keySet()) {
            Constant val = mypred.equatesWithConstant(fldname);
            if (val != null) {
                IndexInfo ii = indexes.get(fldname);
                return new IndexSelectPlan(myplan, ii, val, tx);
            }
        }
        return null;
    }

    private Plan makeIndexJoin(Plan current, Schema currsch) {
        for (String fldname : indexes.keySet()) {
            String outerfield = mypred.equatesWithField(fldname);
            if (outerfield != null && currsch.hasField(outerfield)) {
                IndexInfo ii = indexes.get(fldname);
                Plan p = new IndexJoinPlan(current, myplan, ii,
                                           outerfield, tx);
                p = addSelectPred(p);
                return addJoinPred(p, currsch);
            }
        }
        return null;
    }

    private Plan makeProductJoin(Plan current, Schema currsch) {
        Plan p = makeProductPlan(current);
        return addJoinPred(p, currsch);
    }

    private Plan addSelectPred(Plan p) {
        Predicate selectpred = mypred.selectSubPred(myschema);
        if (selectpred != null)
            return new SelectPlan(p, selectpred);
        else
            return p;
    }

    private Plan addJoinPred(Plan p, Schema currsch) {
        Predicate joinpred = mypred.joinSubPred(currsch, myschema);
        if (joinpred != null)
            return new SelectPlan(p, joinpred);
        else
            return p;
    }
}

输出记录数与块访问 (Records Output Versus Blocks Accessed)

HeuristicQueryPlanner 代码使用 recordsOutput 方法计算最低成本计划。也就是说，它试图找到需要最少块访问的计划，却从不检查其子计划的块需求。这种情况值得解释。

如你所见，使用启发式优化的问题在于，开头看起来很便宜的部分连接顺序最终可能变得非常昂贵，而最佳连接顺序可能有一个非常昂贵的开头。因此，优化器不要被看似比实际更好的连接带偏非常重要。图 15.18 展示了这个问题。

图 15.18a 的查询返回 Einstein 教授所授每门课程给出的成绩及课程标题。假设使用图 7.8 的统计数据，并假设 ENROLL 在 SectionId 上有索引。SimpleDB 优化器会选择 SECTION 作为连接顺序中的第一张表，因为它最小（也最具选择性）。问题是它接下来应该选择哪张表。如果标准是最小化输出记录数，那么应该选择 COURSE。但如果标准是最小化块访问，那么应该选择 ENROLL，因为索引连接会更高效。然而，ENROLL 最终是错误选择，因为大量输出记录会使后续与 COURSE 的连接昂贵得多。

这个例子说明，匹配的 ENROLL 记录数量很大，会显著影响后续连接的成本；因此，ENROLL 应尽可能晚地出现在连接顺序中。通过最小化输出记录数，优化器确保 ENROLL 最终位于末尾。与 ENROLL 的连接具有快速实现这一事实具有误导性，并且无关紧要。

图 15.18 连接顺序中的第二张表应该是哪张？(Which table should be second in the join order?)

(a) SQL 查询；(b) 在连接顺序中第二个选择 ENROLL；(c) 在连接顺序中第二个选择 COURSE。

select Title, Grade
from ENROLL, SECTION, COURSE
where SectId=SectionId and CId=CourseId and Prof='einstein'

15.6.2 Selinger 风格优化 (Selinger-Style Optimization)

SimpleDB 优化器使用启发式规则选择连接顺序。20 世纪 70 年代早期，IBM 的研究人员为 System-R 原型数据库系统编写了一个影响深远的优化器；这个优化器使用动态规划选择连接顺序。由于 Pat Selinger 领导了该优化器团队，这种优化策略通常被称为“Selinger 风格”。

Selinger 风格优化把动态规划与计划生成结合起来。特别是，该算法为每个表集合 S 计算 lowest[S]。不过，它不在 lowest[S] 中保存连接顺序，而是保存最低成本计划。

算法从计算每对表的最低成本计划开始。然后，它使用这些计划计算每组三张表的最低成本计划，依此类推，直到计算出整体最低成本计划。

在这个算法中，最低成本计划是块访问次数最少的计划，而不是输出记录数最少的计划。这意味着该算法是本书中唯一一个在选择连接顺序时真正考虑块访问的算法；因此，它的估算可能比其他算法更准确。

为什么 Selinger 风格优化能够使用块访问？原因是，与启发式优化不同，它会考虑所有左深树，并且在确定某个部分连接顺序无用之前，不会丢弃它。回看图 15.18 的例子。Selinger 风格算法会计算并存储 {SECTION, ENROLL} 和 {SECTION, COURSE} 的最低计划，即使 {SECTION, ENROLL} 的计划更便宜。它在计算 {ENROLL, SECTION, COURSE} 的最低计划时会同时考虑这两个计划。当它发现把 COURSE 连接到 (ENROLL, SECTION) 过于昂贵时，就能够使用替代计划。

使用块访问来比较计划还有另一个优点：可以进行更详细的成本分析。例如，优化器可以把排序成本纳入考虑。考虑图 15.19 的查询树。

假设规划器使用 hashjoin 连接 ENROLL 和 STUDENT。当它随后执行分组时，规划器需要物化输出，并按 StudentId 对其排序。反过来，假设规划器使用 mergejoin 连接这两张表。在这种情况下，它不需要预处理输出，因为输出已经按 StudentId 排序。换句话说，即使 mergejoin 本身不如 hashjoin 高效，它仍可能产生最佳最终计划！

这个例子的要点是，如果规划器想生成最佳计划，还需要跟踪排序顺序。Selinger 风格优化器可以通过在 lowest[S] 中保存每种排序顺序的最低成本计划来做到这一点。在上述例子中，lowest[{ENROLL, STUDENT}] 的值会同时包含 mergejoin 和 hashjoin 计划，因为二者具有不同排序顺序。

图 15.19 连接 ENROLL 与 STUDENT 的最佳方式是什么？(What is the best way to join ENROLL with STUDENT?)

15.7 查询块合并 (Merging Query Blocks)

本节考察提到视图的查询优化。例如，考虑图 15.20a 的查询，它使用一个视图来检索在 Einstein 教授所授课程中获得 “A” 的学生姓名。第 10 章中的基本查询规划器通过分别规划视图定义和查询，然后把视图计划接入查询计划，来为这种查询创建计划。该计划见图 15.20b。

与每个查询和视图定义关联的计划称为查询块 (query block)。图 15.20b 的计划说明了优化器处理视图查询的最简单方式：它可以先分别优化每个查询块，再把它们组合起来形成最终计划。虽然分别优化实现起来简单，但创建出的计划不一定很好。图 15.20 的计划就是例子。最佳连接顺序是 (SECTION, ENROLL, STUDENT)，但在这些查询块给定的情况下，这个连接顺序不可能实现。

解决这个问题的方法是合并查询块，并把它们的内容作为一个查询来规划。例如，在图 15.20 中，规划器可以忽略视图定义块中的 project 节点，并把它的 select 和表节点加入主查询。如果视图定义足够简单，这种策略就是可能的。当视图定义包含分组或重复消除时，情况会复杂得多，并且合并可能不可行。

图 15.20 规划一个视图查询 (Planning a view query)

(a) 视图定义和使用它的查询；(b) 分别规划每个查询块。

create view EINSTEIN as
select SectId from SECTION
where Prof = 'einstein'

select SName from STUDENT, ENROLL, EINSTEIN
where SId = StudentId and SectionId = SectId
and Grade = 'A'

15.8 本章小结 (Chapter Summary)

• 如果两个查询的输出表包含完全相同的记录（虽然顺序不一定相同），并且这一点不依赖数据库内容，那么这两个查询就是等价的。
• 一个 SQL 查询可能有许多等价查询树。这些等价性从关系代数操作符的性质推导而来。
  • product 操作符是可交换且可结合的。这些性质意味着查询树中的 product 节点可以按任意顺序计算。
  • 谓词 p 的 select 节点可以拆分成多个 select 节点，p 的每个合取项对应一个节点。把 p 写成合取范式（CNF）可以把它拆分成最小片段。每个合取项对应的节点可以放在查询树中的任何位置，只要其选择谓词在该位置有意义。
  • 一对 select-product 节点可以替换为单个 join 节点。
  • 可以在查询树中任意节点之上插入 project 节点，只要其投影列表包含该节点祖先提到的所有字段。
• 两棵等价树的计划可能有截然不同的执行时间。因此，规划器会尝试寻找需要最少块访问的计划。这个过程称为查询优化。
• 查询优化很困难，因为一个 SQL 查询的计划数量可能远远超过规划器可行枚举的范围。规划器可以通过把优化分成两个独立阶段来处理这种复杂性：
  • 阶段 1：寻找该查询最有希望的树，也就是看起来最可能产生最高效计划的查询树。
  • 阶段 2：为该查询树选择最佳计划。
• 在阶段 1 中，规划器无法估算块访问，因为它不知道会使用哪些计划。相反，它把查询树的成本定义为树中每个 product/join 节点输入大小之和。直观上，低成本查询树会最小化中间连接的大小。其想法是，每个连接的输出会成为后续连接的输入，因此中间输出越大，执行查询就越昂贵。
• 规划器还采用启发式规则来限制它考虑的树和计划集合。常见启发式规则包括：
  • 把 select 节点尽可能深地放入查询树。
  • 把每一对 select-product 节点替换为 join 节点。
  • 在每个物化计划的输入之上放置 project 节点。
  • 只考虑左深树。
  • 只要可能，就避免不是连接的乘积操作。
• 每棵左深树都有一个关联的连接顺序。寻找好的连接顺序是查询优化中最困难的部分。
• 选择连接顺序的一种方式是使用启发式规则。两个合理（但相互冲突）的启发式规则是：
  • 选择产生最小输出的表。
  • 选择具有最严格谓词的表。
• 第二个启发式规则努力创建一种查询树，其中最严格的 select 节点尽可能深；其直觉是这类树往往具有最低成本。
• 选择连接顺序的另一种方式是使用动态规划穷举检查所有可能连接顺序。动态规划算法会计算每个表集合的最低连接顺序，从两表集合开始，然后是三表集合，持续下去，直到到达全部表集合。
• 在第二个优化阶段中，规划器通过为查询树中的每个节点选择一种实现来构造计划。它独立于其他节点的实现来选择每个实现，并以块访问为单位计算其成本。规划器可以通过检查每个节点的所有可能实现，或遵循如下启发式规则，来确定最低成本计划：
  • 只要可能就使用索引。
  • 如果连接不能使用索引，那么当某个输入表很小时使用 hashjoin；否则使用 mergejoin。
• 查询优化器的实现可以结合两个阶段，在构造查询树的同时构造计划。SimpleDB 优化器使用启发式规则确定连接顺序，并在每张表被选择时增量构造计划。Selinger 风格优化器使用动态规划：它不为每个表集合保存最低成本连接顺序，而是保存最低成本计划。Selinger 风格优化器的优点是，不同于其他任何技术，它可以使用估算块访问来计算最佳连接顺序。
• 使用视图的查询会有由多个查询块组成的计划。处理多个查询块最直接的方式是分别优化每个查询块，然后把它们组合起来。不过，如果查询块可以一起优化，就可能得到更高效的计划。当视图定义足够简单时，这种策略是可能的。

15.9 建议阅读 (Suggested Reading)

本章对查询优化做了基本介绍；Graefe（1993）和 Chaudhuri（1998）的文章给出了更多细节。Swami（1989）的论文包含对各种连接顺序启发式规则的实验比较。Selinger 等人（1979）描述了 System-R 优化器。

传统查询规划器的一个困难是，其启发式规则和优化策略被硬编码到方法中。因此，如果要改变启发式规则或添加新的关系操作符，唯一办法就是重写代码。另一种方法是把操作符及其转换表达为重写规则，并让规划器反复使用这些规则把初始查询转换为最优查询。这样，要改变规划器，只需改变规则集合。Pirahesh（1992）描述了这种策略。

本章中的优化策略在查询规划和查询执行之间有明显分界：一旦计划被打开并执行，就没有回头路。如果规划器错误地选择了低效计划，就无能为力了。Kabra 和 DeWitt（1998）的文章描述了数据库系统如何监控计划执行，收集关于其行为的统计信息。如果系统认为执行效率低于预期，就可以使用这些统计信息创建更好的计划，并把旧计划与新计划“热交换”。

• Chaudhuri, S. (1998). An overview of query optimization in relational systems. Proceedings of the ACM Principles of Database Systems Conference, pp. 34-43.
• Graefe, G. (1993). Query evaluation techniques for large databases. ACM Computing Surveys, 25(2), pp. 73-170.
• Kabra, N., & DeWitt, D. (1998). Efficient mid-query re-optimization of sub-optimal query execution plans. Proceedings of the ACM SIGMOD Conference, pp. 106-117.
• Pirahesh, H., Hellerstein, J., & Hasan, W. (1992). Extendable/rule based query rewrite in starburst. Proceedings of the ACM SIGMOD Conference, pp. 39-48.
• Selinger, P., Astrahan, M., Chamberlin, D., Lorie, R., & Price, T. (1979). Access-path selection in a relational database management system. Proceedings of the ACM SIGMOD Conference, pp. 23-34.
• Swami, A. (1989). Optimization of large join queries: Combining heuristics and combinatorial techniques. ACM SIGMOD Record, 18(2), 367-376.

15.10 习题 (Exercises)

概念性练习 (Conceptual Exercises)

15.1. 证明 product 操作符是可结合的。

15.2. 考虑一个对多张表取乘积的查询，以及该查询的任意两棵等价查询树。证明可以使用第 15.1.1 节的等价性把一棵树转换为另一棵树。

15.3. 考虑图 15.2a 的查询树。

(a) 给出一个转换序列，用于创建下面这棵树。

(b) 给出一个转换序列，用于创建一棵连接顺序为 (COURSE, SECTION, ENROLL, STUDENT, DEPT) 的左深树。

15.4. 考虑一棵包含 select 节点的查询树。

(a) 证明把 select 节点移动越过另一个 select 节点会得到等价查询树。

(b) 什么时候可以把 select 节点移动到 project 节点之上？

(c) 证明只要语义上有意义，就可以把 select 节点移动到 groupby 节点之上或之下。

15.5. 考虑练习 8.16 中的 union 关系代数操作符。

(a) 证明该操作符是可结合且可交换的，并给出这些等价性的转换。

(b) 给出一种允许把选择推入 union 内部的转换。

15.6. 考虑练习 8.17 中的 antijoin 和 semijoin 关系代数操作符。

(a) 这些操作符是否可结合？是否可交换？给出任何适用的转换。

(b) 给出允许把选择推入 antijoin 或 semijoin 内部的转换。

15.7. 考虑把图 15.6b 的选择谓词加入图 15.2b 的查询树。给出把选择尽可能下推之后得到的查询树。

15.8. 给出两棵等价查询树，使最低成本计划来自成本较高的那棵树。

15.9. 证明图 15.12e 中的 bushy 树是其 SQL 查询最有希望的树。

15.10. 图 15.6c 的查询树具有连接顺序 (STUDENT, ENROLL, SECTION, COURSE, DEPT)。还有 15 种不需要乘积操作的连接顺序。枚举它们。

15.11. 给出一个查询，使启发式规则 4 不会产生最低成本查询树。

15.12. 考虑图 15.6。

(a) 计算两棵树各自的成本。

(b) 分别使用启发式规则 5a 和 5b，利用启发式算法计算最有希望的查询树。

(c) 使用动态规划算法计算最有希望的查询树。

(d) 计算最有希望查询树的最低成本计划。

15.13. 考虑如下查询：

select Grade
from ENROLL, STUDENT, SECTION
where SId=StudentId and SectId=SectionId and SId=1 and SectId=53

(a) 证明连接顺序 (ENROLL, STUDENT, SECTION) 的树成本低于 (ENROLL, SECTION, STUDENT)。

(b) 分别使用启发式规则 5a 和 5b，利用启发式算法计算最有希望的查询树。

(c) 使用动态规划算法计算最有希望的查询树。

(d) 计算最有希望查询树的最低成本计划。

15.14. 第 15.4 节给出的动态规划算法只考虑左深树。扩展它，使其考虑所有可能的连接树。

编程练习 (Programming Exercises)

15.15. 修改 SimpleDB 启发式规划器，使其使用启发式规则 5b 来选择连接顺序中的表。

15.16. 为 SimpleDB 实现一个 Selinger 风格查询规划器。

15.17. 练习 14.15 要求你在 SimpleDB 中实现 hashjoin 算法。现在修改 TablePlanner 类，使其在可能时创建 hashjoin 计划，而不是多缓冲乘积。