CMU 15-445/645-笔记-14-Query Plan 和优化-part1

## 课程前沿

### Query 优化

第一个查询优化器的实现可以追溯到 1970 年代，也就是 IBM 的 System R

当时 Ted Codd 写了第一篇关于关系模型的 paper，然后有俩波人，一波是 IBM ，另一波是 UC Berkeley 的，构建出了史上最著名的关系型数据库系统，UC Berkeley 那波人开发出来的叫 Ingres(Postgres 是 Ingres 的后续产品)，IBM 那群人开发出来的叫 System R

Ted Codd 在第一次提出关系模型时，并没有提出相关的类似 SQL 的语言，SQL 是后来才出现的

UC Berkeley 那波人使用的是一种叫 Quel 的语言，看起来像 SQL，但语法不一样

查询优化有 2 个方面可以进行讨论

1. 使用静态规则/条件触发(比如在 SQL 中定义了 `1 = 0` 这样的玩意儿，那就可以通过一条规则将它去除掉，以及，在不用直接看数据库表的情况下，可以通过数据库的 system catalog 文件这种类似的规则就可以知道这个数据库里面的 tuple 实际包含的头信息)

2. Cost-based Search(枚举 SQL 中所有可能的查询方案，通过某种方式去掉那些多余、愚蠢、耗费成本的方案，至于如何判断这个成本，就是用某种成本模型来做预估)

一个查询优化的 Pipeline 长这样

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

2. 再通过一个 SQL Parser，将 SQL 解析成 ast

3. 将 ast 传入 Binder 中，Binder 负责将 SQL 查询中引用的那些命名对象 转换 成某种内部标识符，而它是通过 System Catalog 来做到这一点的(比如 SQL 为 `SELECT * FROM foo`，如果不想让查询计划中的剩下部分对 foo 表 进行处理，那就需要在 System Catalog 里面去查有没有一个叫做 foo 的表，如果存在，那么就从 System Catalog 里面拿到 foo 表对应的内部标识符，使得后面能够找到这个 foo 表；如果 foo 表不存在，System Catalog 就会直接表明 foo 表不存在，并抛出一个错误)

4. Binder 要输出 Logical Plan(Logical Plan 指的是，从一个高级层面来讲，这个查询想干的事情是什么，比如要查表数据，或者对表进行 Join 操作，但并不会表明在实际中该怎么去执行这个查询，具体如何执行这个查询是 Physical Plan 所需要干的事情)，然后传入一个 Tree Rewriter (这个也是可选的)。然后为了对 ast 进行重写，需要从 System Catalog 处拿到 Schema Info，表的一些属性都在这个里面

5. Tree Rewriter 会输出和 Binder 输出的一样的 Logical Plan，然后将 Logical Plan 传入查询优化器。然后在这个查询优化器中，使用 Cost Model 来找出最佳查询方案。查询优化器会使用 System Catalog 提供的 Schema Info 以及 Cost Model 来对这些方案进行成本预估

6. 成本预估完成后，查询优化器就可以生成一个 Physical Plan(Physical Plan 就是数据库系统实际执行查询语句的方式)

### Logical Plan 和 Physical Plan

Logical Plan 是包含 SELECT/FILTER/PROJECTION/JOIN 等操作的，使用这些的时候不代表要使用哪种算法实现

Physical Plan 定义如何去执行查询方案，即在一个查询计划中要怎么使用这些不同的 operator

### Query 优化是一个 NP 问题级别的问题

对于查询优化来说，机器学习确实是一种潜在的改善手段，但它并不是哪种能够解决一切问题的黑科技

## 课程目标

## Relational Algebra Equivalences

可以对关系代数或者查询计划进行转换，让它们变成相同效果的不同关系代数语句

只要查询的结果是相同的，比如一组 tuple 的集合，虽然表达式不同，但只要结果一样，这俩表达式就是等同的

> 注意这里 tuple 的顺序可以不一致，只要内容相同就行

可以使用关系代数中的传递性的特性，通过不同的方式改变表达式的标准逻辑，通过移动 operator 来生成更为高效的计划

这种高级的技术，就叫做查询重写(Query Rewriting)

例子

上面的 SQL 语句可以写出下面的这种关系代数语句

那么对于这条语句能做哪些简单的优化呢?

可以将 filter 这一步放在 enrolled 里面做

将 filter 操作放在 Join 操作之前，可以减少很多 Join 的操作

操作更少 -> 成本更低 -> 执行速度更快 -> 所用硬件资源也更少

可以在不查看数据的情况下，通过比较 filter 函数和 Join 函数的成本，就可以做到这种 push down

关系代数转换和等同如上图

通过选择和比较这些不同的 operator，来对查询计划做相关的优化

对于上图中的例子来说，可以将这个复杂的判断条件进行拆分，使其变得易于计算

因为这比起从 tuple 中拿到 Y 属性的值，然后将它复制到某个寄存器或者变量中再进行比较，这种做法成本更低

对于 Projection 操作来说，也可以将它们尽早 push down

思路是，当将数据从一个 operator 传递到下一个 operator 时，要最小化需要复制的数据

例子

在数据传给 Join operator 之前，引入一个 Projection 操作，这样就可以去掉那些不需要的列信息，只传递需要的几列数据给 Join operator

更多例子

首先移除掉愚蠢的和不必要的条件，比如 SQL 语句 `SELECT * FROM  A WHERE 1 = 0;`

这个语句意味着什么呢? 意味着，对于在 A 表中扫描到的每个 tuple 来说，会对 `1 = 0` 这个条件进行检查，而因为这个条件的结果永远不可能为 true，所以没有任何一个 tuple 能匹配上这个条件。那么优化就是，直接跳过扫描，返回一个空结果给用户

对于 `SELECT * FROM A WHERE 1 = 1;` 那么就可以重写为 `SELECT * FROM A;`

同样的，也可以在 Join 操作中使用类似的优化，比如上图中的条件就是无用的，所以可以直接优化成

那么还能继续做哪些优化呢?

可以将那些不必要的 Projection 操作给忽略掉

还有一个就是条件合并

可以把上图优化成

那么最后讨论下如何进行估算

对于一个查询来说，如果要对 n 个表进行 Join，那么可以使用不同的 Join 顺序的数量就是 4^n

要枚举的数量一大，这也是一个问题，所以就需要减少枚举出来的 Join 顺序的数量

## Cost Estimation

成本模型能够预估在数据库系统化中执行操作时所需要的成本

然后通过牺牲预测的正确性来获得效率

> mongoDB 貌似没有成本模型和查询优化器

## Statistics

预估执行查询的成本是通过在内部维护表相关的信息来做的，这些信息大多都是索引、表以及 tuple 中的值相关的元数据

不同数据库系统，获取到这些元信息的语法也不同

然后将数据带入公式来预估这些值