Lecture#14 Query Planning & Optimization-JZTXT

SQL是声明性的，这意味着用户告诉 DBMS 他们想要什么答案，而不是如何得到答案。因此，DBMS 需要将 SQL 语句转换为可执行的查询计划。但不同的查询计划的效率可能出现多个数量级的差别，如 Join Algorithms 一节中的 Simple Nested Loop Join 与 Hash Join 的时间对比 (1.3 hours vs. 0.45 seconds)。因此，DBMS 需要一种方法来为给定查询选择“最佳”计划。这是 Query Optimizer 的工作。

Query Optimizer 第一次出现在 IBM System R，那时人们认为 DBMS 指定的查询计划永远无法比人类指定的更好。System R 的 optimizer 中的一些理念至今仍在使用。

我们先来看下一条 sql 语句在 BusTub 中的运行流程：

一条 sql 语句会经过 Parser -> Binder -> Planner -> Optimizer -> Executors 几个阶段。SQL 语句 parse 后，通过 binder 绑定 identifier 到各个实体，使用 planner 生成查询计划，而后使用 optimizer 优化成最终的查询计划，最终通过 executor 生成一颗算子执行树。

SQL 在被 parse 前，可经由 SQL Rewriter 通过某种转换规则来对 SQL 进行重写 (比如用一些额外的信息对数据库里面某些表进行标记，表示可以在这个节点或者磁盘上找到这些表)，这个是可选的。

1️⃣ Parser：根据 sql 语句生成一颗抽象语法树 (Abstract Syntax Tree)

具体如何生成，请参考编译原理。Parser 不是数据库的核心部分，也不是性能瓶颈，因此除非热爱编译原理，或者想通过实现一个 sql Parser 对编译原理进行实践，否则一般都会采用第三方库。Bustub 中采用了 libpg_query 库将 sql 语句 parse 为 AST。

2️⃣ Binder：结合数据库的元信息，将抽象语法树转成一个具有库表信息的语义语法树

得到 AST 后，Binder 将遍历这棵树，将所有 identifier 解析成没有歧义的实体。实体是 Bustub 可以理解的各种 c++ 类。绑定完成后，得到的结果是一棵 Bustub 可以直接理解的树。这里把它叫做 Binder AST。

? 下面这条 sql 语句中 SELECT 和 FROM 是关键字，* 和 __mock_table_1 是标识符。

Binder 会在 catalog 中查 __mock_table_1 的信息，将 __mock_table_1 绑定到具体的实体表上 (table_oid=0)。与此同时，将 * 展开成可以查到的所有列。

bustub> explain (binder) select * from __mock_table_1;
=== BINDER ===
BoundSelect {
  table=BoundBaseTableRef { table=__mock_table_1, oid=0 },
  columns=[__mock_table_1.colA, __mock_table_1.colB],
  groupBy=[],
  having=,
  where=,
  limit=,
  offset=,
  order_by=[],
  is_distinct=false,
}

3️⃣ Planner：根据语义语法树生成逻辑执行计划树，也叫查询计划

得到 Binder AST 后，Planner 将遍历这棵树，生成初步的查询计划。

有很多种子查询计划 (Scan、Join、Projection......)，每个子查询计划 plan node 都是这棵树上的一个节点。查询计划规定了数据的流向。数据从树叶流向树根，自底向上地流动，在根节点输出结果。

? 下面这条 sql 语句对应的原始查询计划

SELECT t1.y, t2.x FROM t1 INNER JOIN t2 ON t1.x = t2.y;

4️⃣ Optimizer：优化查询计划，生成最终的物理执行计划

由 Planner 得到初步的查询计划后，再将查询计划交给 Optimizer 进行修改优化，生成优化过后的最终查询计划。Optimizer 主要有两种实现方式：

基于规则 (Rule-based)：Optimizer 遍历初步查询计划，仅按硬编码在数据库中的一系列规则优化 Plan。例如：将 Limit + Sort 合并为 TopN、谓词下推 (Predicate Pushdown)、投影下推 (Projection Pushdown)、列裁剪等。
- 这种 Optimizer 不需要知道数据的具体内容，仅是根据预先定义好的规则修改 Plan Node。
基于代价 (Cost-based)：估计并比较多个查询计划的代价，最终选择代价最小的为最终查询计划。
- 这种 Optimizer 首先需要读取数据，利用统计学模型来预测不同形式但结果等价的查询计划的 cost。

BusTub optimizer 是一个 Rule-based 优化器。我们将不同的规则按顺序应用到当前的查询计划上，产生最终的查询计划。

❗️一般来说，Planner 生成的是 Logical Plan Node，代表抽象的 Plan。Optimizer 则生成 Physical Plan Node，代表具体执行的 Plan。一个比较典型的例子是 Join：在 Planner 生成的查询计划中，Join 就是 Join。在 Optimizer 生成的查询计划中，Join 会被优化成具体的 HashJoin 或 NestedIndexJoin 等等。

5️⃣ Executor：根据查询计划，生成具体的算子执行树

Optimizer 生成的具体的查询计划后，就可以生成真正执行查询计划的一系列算子。生成算子的步骤：遍历查询计划树，将树上的 PlanNode 替换成对应的 Executor。

总结，查询优化是个 NP-Hard 问题，有两种查询优化策略：

基于规则 (Rule-based)：通过 rewrite query 来消除不高效的部分，不需要成本模型。
基于代价 (Cost-based)：使用成本模型来评估多种等价计划然后选择成本最小的。

1 Query Rewriting

如果两个关系代数表达式 (Relational Algebra Expressions) 如果能产生相同的 tuple 集合，我们就称二者等价。DBMS 可以通过一些 Heuristics/Rules 来将关系几何表达式转化为成本更低的等价表达式，从而达到查询优化的目的。这些规则通常试用于所有查询，如：

谓词下推 (Predicate Pushdown)
投影下推 (Projection Pushdown)

1.1 谓词下推

Predicate 通常有很高的选择性，可以过滤掉许多无用的数据。将 Predicate 推到查询计划的底部，可以在查询开始时就更多地过滤数据，Predicate 通常有很高的选择性，可以过滤掉许多无用的数据。

核心思想：

越早过滤越多数据越好
重排 predicates，使得选择性大的排前面
将复杂的 predicate 拆分，然后往下压，如 X=Y AND Y=3 可以修改成 X=3 AND Y=3

1.2 投影下推

投影下推方案对列存储数据库不适用。在行存储数据库中，越早过滤掉不用的字段越好，因此将 Projections 操作往查询计划底部推也能够缩小中间结果占用的空间大小。

1.3 优化 sub-queries

DBMS将where子句中的嵌套子查询 (nested sub-queries) 视为接受参数并返回单个值或一组值的函数。

对于嵌套子查询，有两种优化方法：

1️⃣ 通过去相关性/扁平化嵌套子查询，来重写查询。

2️⃣ 对于较难的查询，将查询分解为块，然后每次集中处理一个块。将子查询写入临时表，在查询完成后丢弃。

1.3 其他规则

1️⃣ 分割连接谓词、用 join 替代笛卡尔积。

2️⃣ 删除不可能 or 不必要的谓词。

3️⃣ 合并谓词。

4️⃣ 去除不必要的 Join：

Join 操作的顺序是决定查询性能的一个关键因素。对所有可能的连接顺序进行穷举是低效的，所以连接顺序的优化需要一个 cost model。然而，我们仍然可以用启发式的优化方法来消除不必要的 join。

优化规则总结：

删除不可能 or 不必要的谓词

合并谓词

越早过滤数据越好（谓词下推）

分解一个复杂的谓词，并进行谓词下推（分割连接谓词）

对谓词进行重新排序，使得选择性大的排前面

用 join 替代笛卡尔积

尽可能早地进行投影，以创建更小的 tuples 来减少中间结果（投影下推）

对嵌套子查询：通过去相关性/扁平化嵌套子查询，来重写查询；分解嵌套子查询，将结果存储在一个临时表中

去除不必要的 Join

2 Cost-based Search

许多操作没有通用的规则，如 Join：Join 操作既符合交换律又符合结合律，等价关系代数表达式数量庞大，这时候就需要一些成本估算技术，将过滤性大的表作为 Outer Table，小的作为 Inner Table，从而达到查询优化的目的。

2.1 Cost Estimation

一个查询需要花费多长时间，取决于许多因素：

CPU: Small cost; tough to estimate
Disk: #block transfers
Memory: Amount of DRAM used
Network: #messages

但本质上取决于：整个查询过程需要读入和写出多少 tuples

因此 DBMS 需要保存每个 table 的一些统计信息，如 attributes、indexes 等信息，有助于估计查询成本。值得一提的是，不同的 DBMS 的搜集、更新统计信息的策略不同，获取到这些元信息的语法也不同：

Postgres/SQLite: ANALYZE
Oracle/MySQL: ANALYZE TABLE
SQL Server: UPDATE STATISTICS
DB2: RUNSTATS

2.2 Selection Statistics

以下 selection 都建立在以下假设上：

数据均匀分布

谓词相互独立

Join 的域相重叠，因此内表中的每个 key 也存在于外表中 (除了内外表的 primary key)

通常，DBMS 对任意的 table R，都保存着以下信息：

\(N_R\)：R 中 tuples 的数量
\(V(A, R)\)：R 中 A 属性的不同取值 (distinct values) 个数
\(A_{max}, A_{min}\)：A 属性取值的最大和最小值

由此可得 选择基数 (selection cardinality)，即 R 中 A 属性下每个值的平均记录个数：

\[SC(A, R) = N_R / V(A, R) \]

需要注意的是，这种估计建立在假设：R 中所有数据在 A 属性下均匀分布 (data uniformity)。

谓词 P 的 选择率 (selectivity) 是指符合条件的 tuple 的百分比。

利用以上信息和假设，DBMS 可以估不同谓词的 sel：

Equality
Range
Negation
Conjunction
Disjunction

Equality Predicate

SELECT * FROM people WHERE age = 2;

设 people 表中有 5 条个人信息，即 \(N_R = 5\) 所有信息中的 age 有 5 个取值，即 \(V(age, people) = 5\)：

\[sel(A=constant) = SC(P) / V(A, R) = \frac{1}{5} \]

Range Predicate

SELECT * FROM people WHERE age >= 2;

可以利用 \(A_{max}, A_{min}\) 来估计：

\[sel(A ≥ a) = (A_{max} - a)/ (A_{max} - A_{min}) \]

Negation Query

SELECT * FROM people WHERE age != 2;

利用 equality query 可以反向推导出 negation query 的情况：

\[sel(not \ P) = 1 - sel(P) = 1 - SC(age=2) = \frac{4}{5} \]

实际上这里所谓的选择率 (Selectivity) 就是基于均匀分布假设下的可能性 (Probability)。

Conjunction Query

SELECT * FROM people
 WHERE age = 2
   AND name LIKE 'A%';

若假设两个 predicates 之间相互独立，则可以推导出：

\[sel(P1 \wedge P2) = sel(P1)\bullet sel(P2) \]

其韦恩图如下所示：

Disjunction Query

SELECT * FROM people
 WHERE age = 2
    OR name LIKE 'A%';

若假设两个 predicates 之间相互独立，则可以推导出：

\[sel(P1 \vee P2) = sel(P1) + sel(P2) - sel(P1 \wedge P2) = sel(P1) + sel(P2) - sel(P1)\bullet sel(P2) \]

其韦恩图如下所示：

Join

对 Join 的结果大小估计，考虑最通用的情况：假设 \(R_{cols} \cap S_{cols} = \{A\}\)，其中 A 不是 R 或 S 的 primary key，可以从两个方向思考：

对 R 中的每个 tuple，找到 S 中相应的 tuples：\(estSize \approx N_{R} \bullet N_{S} / V(A, S)\)
对 S 中的每个 tuple，找到 R 中相应的 tuples：\(estSize \approx N_{R} \bullet N_{S} / V(A, R)\)

综合两个方向，取小的：

\[estSize \approx N_R \bullet N_S / max(\{V(A, S), V(A, R)\}) \]

若两个表 join 后的 selectivity 非常不准确，可能是这两个表的相关性太高，因此可要求 DBMS 对二者 join 后的表进行 selectivity

2.3 Other Statistics

选择率计算中，做出的三个假设往往不被真实数据所满足。例如，相关的属性打破了谓词独立性的假设。

现代 DBMSs 也会使用?三种方式来降低成本估计本身的成本：

Histograms：保持一个 column 中每个值 (或值的范围) 的出现次数。
Sketches：概率数据结构，给出一个给定值的近似计数。
Sampling：DBMS维护每个表的一个小子集，然后用它来评估表达式以计算 selectivity。

Histograms

真实数据往往是倾斜的 (Skewed)，有些数据出现频率很高，此时可以通过维护一个单独的哈希表或直方图来跟踪这些 data (但是只可能会去保存每列中前 10 或者前 20 个不同的值)，对于其他数据来说，可以假设它们出现的频率是统一的，可以根据这个来预测 Cardinality (基数)。这是用来解决这种均匀数据问题的标准手段。

直方图中，纵坐标是值的出现频率，横坐标是属性的值。真实数据往往更具倾向性，而不是均匀分布。

等宽直方图：我们将这些数据划分到不同的 bucket 中，每个 bucket 对应的 value 范围相同，一个 bucket 值保存一个值，表示该 bucket 对应各 value 出现的次数的总和。新的直方图中显示的就是这些聚合后的值。

等宽直方图虽然节省空间，但存在问题：不知道这些 value 中那些 value 出现次数是比较高的。这时就可采用等深直方图(分数图)。

等深直方图：通过调整 bucket 的宽度，使每个 bucket 的 count 总和都大致相等。

Sketchs

作为直方图的替代，一些系统使用 Sketchs 来生成数据集的近似统计数据，它是一种概率数据结构。

? Count-Min Sketch (2003)：近似估计一个集合中元素的数目

? HyperLogLog (2007)：近似计算一个集合中不同元素的数目

Sampling

直方图就像是数据库中的表的数据的一种低解析度副本，它是对其他内容的一种近似缩略表达。那么在不通过用直方图来衍生统计信息的情况下，该如何拿到基于该表本身的一个更小的副本呢? —— 采样

采样本质上，是通过维护一个样本表，然后根据该样本来衍生出统计信息。

? 可以等间隔在表中对数据采样，然后再估计。

为了避免重复采样，DMBS 会保存一份采样表，待 table 的变动较大时，再更新采样表。

3 Query Optimization

通过粗略的估计这些条件的选择率后，我们可以通过 Cost-based search 来进行查询优化。

在执行基于规则的重写之后，DBMS 将列举查询的不同计划并估计它们的成本。在耗尽所有计划或超时后，它为查询选择它所看到的最佳计划。

单一关系查询 (Single relation)
多关系查询 (Multiple relations)
嵌套子查询 (Nested sub-queries)

3.1 Single-Relation Query Plans

对于 single-relation query 而言，最重要的是：

选择最好的 access method：Sequential Scan、Binary Search (clustered indexes)、Index Scan
评估谓词顺序

这些采用一些简单的启发式规则就可以了。OLTP 类的查询计划是相对简单的，因为他们通常是 Search Argumentable 的：

通常只要推选最好的 index
Join 大多只发生在基数很小的外键关系上
可用简单的启发式优化实现

? 下面 sql 语句中有一个启发式规则 id INT PRIMARY KEY，表示 id 是个主键。若这里有一个索引，用它做索引扫描就可以了。

3.2 Multi-Relation Query Plans

对于多关系查询计划，随着 Join 的表数目增加，Join 操作产生的备选计划的数量也迅速增长。因此，必须限制搜索空间，以便能够在合理的时间内找到最佳计划。有两种方法可以解决这个搜索问题：

Bottom-up：从头开始，建立计划以达到你想要的结果。? IBM System R, DB2, MySQL, Postgres, 大多数开源 DBMS
Top-down：从想要的结果开始，然后顺着树的方向找到让你达到这个目标的最佳计划。? MSSQL, Greenplum, CockroachDB, Volcano

Bottom-up optimization example - System R

使用静态规则来进行初始优化。然后使用动态编程，用分而治之的搜索方法确定表的最佳连接顺序。

将查询分解成块，为每个块生成逻辑运算符 (枚举关系排序)
对于每个逻辑运算符，生成一组实现它的物理运算符 (枚举 Join 算法选择，枚举访问方法选择)
然后，迭代构建一个“左深”树，使执行该计划的估计工作量最小化

? 先列举 join 的顺序，列举每个 operator 的plan (实现 join 的算法)，列举每个表的获取方式 (index、sql Scan)，再使用 动态编程 来减少成本估计得数量：通过之前讲的那些公式计算在使用不同的 Join 算法的情况下，第一步的成本是多少(可以使用 Hash Join 或者 SortMerge Join)，选择执行成本最低的那个 Join 算法：