CMU 15-445/645-笔记-15-Query Plan 和优化-part2
## 课程目标
1. 如何通过 Cost Model 来对查询计划进行成本预估
2. 如何根据 Logical Plan 枚举 执行 Plan
3. 内嵌子查询，通过规则对它们进行重写，并使其变得更为高效
## Cost Estimation
这种成本可能是由一堆不同的基础硬件性能的参数所组成的
但无论如何，都要将要访问的 tuple 数量作为成本的参考，也就是说，要确定数据从一个 operator 传递到下一个 operator 时，这个传递的数据量大小是多少
## Statistics
在 DBMS 中，用来预估成本时所使用的基础组件就是 DBMS 内部的 Statistics Catalog
所有主流的数据库系统都会通过某种命令来强制收集新的统计信息
某些系统会设置定时任务，定期更新这些统计信息
某些系统在执行查询时，顺带更新这些统计信息
某些系统会通过触发器来更新这些统计信息，比如设置一个触发限制，如果表中有 10% 或者 20% 的数据发生了改变，就执行 RUNSTATS 命令来做更新
需要注意的是，更新统计信息的成本会很高，因为它需要对整个表进行扫描
有上面的信息，就要想办法计算或者维护这个信息，以此来获得每个属性中不同的值的数量
通过这个基本信息，可以获得一个新的数据信息，也就是选择基数(Selection Cardinality)，定义一个 SC 函数，然后通过 tuple 数量除属性 A 下面的去重后的值的数量来计算出这个选择基数
当然，这里有一个非常重要的假设，那就是 **数据分布均匀**
那么通过这个选择基数，还能做哪些事情呢?
如果能弄清楚每个 operator 传给下一个 operator 的 tuple 的数量，那么就可以知道这个传递实际的工作量有多少，要使用的磁盘空间有多少，以及内存量有多少
即通过选择基数来计算 子 operator 要提供的数据量有多少
例子，在一个 unique key 上使用等价判断(equality predicate)
上图中，要查找 id = 123 的 tuple，这是很容易的，因为它的基数是 1，不管表中有多少个 tuple，总有一个 tuple 符合条件。因为这里用的是主键(Primary Key)，是唯一的
难点在于，假如判断条件变得复杂了，那么这个就不太好做，因为现在就需要将不同判断条件对应的 选择基数 以一种特别的方式结合起来
那么对于复杂的 Predicates 应该怎么算呢
就是上图这些。简单来讲，选择率就是一个函数。对于针对该表的一个给定条件来说，这个函数会计算出该表中有多少符合该条件的 tuple
而这个计算的方式，也取决于实际执行的操作类型
例子
在上图中的例子中 age = 2 的选择率是这么计算的
通过查看上图中出现的直方图，就能准确的知道它(age = 2)的出现次数，而其结果就是 1/5(假设数据分布均匀)
如果来计算 Range Predicate 的选择率呢?
结果就是 1/2
但实际上这个结果是有问题的，正确答案是 3/5，但根据公式得到的是 1/2
所以公式计算出的结果也不一定正确，也正是因为如此，当对包含一堆不同条件和 operator 的复杂查询进行这样的预估的时候，就会出现很多问题
最后的例子就是 negation
而 age = 2 的选择基数是 1
所以 age != 2 的范围就是 [0, 1] 和 [3, 4]
所以正确答案就是 4/5
在这里，预估的条件选择率和概率是一回事(Selectivity ~= Probility)
## 一些更复杂的统计
假设现在要得到一个交集，那么这个时候，就应该去计算第一个条件(age = 2)的选择率，然后再去计算第二个条件(name LIKE 'A%') 的选择率，然后将这俩概率进行相乘(因为假设对这俩条件的预估都是相互独立的)
于是这样就能得到它们的交集
假设现在要得到一个并集，并集的计算公式如上，并且假设对这俩条件的选择率都是独立的
于是这样就能得到它们的并集
## Selection Cardinality
除了之前提到过的 Uniform Data 以及 Indipendent Predicates 假设外，还有一种假设叫做 Inclusion Principle
在计算条件选择率时有很多假设前题，而这会使得计算变得简单，但这容易得出错误的预测结果
Uniform Data 假设的时所有数据的出现概率都是相同的
> Heavy-Hitter: 如果有一些 Skewed(倾斜) Data，它出现的频率非常高，此时可以通过维护一个单独的 hash table 或者直方图来跟踪这些 data(但是只可能会去保存每列中前 10 或者前 20 个不同的值)，对于其他数据来说，可以假设它们出现的频率是统一的，可以根据这个来预测 Cardinality (基数)。这是用来解决这种均匀数据问题的标准手段
Indipendent Predicates 假设俩预测的条件是独立的，如果要取交集，就将其计算出的概率进行相乘来生成组合基数
Inclusion Principle 是这样一个假设，比如要对 2 个表进行 Join 操作，然后对于 Inner Table 中的每个 tuple 来说，在 Outer Table 中都会有一个与之对应的 tuple
## Correlated Attributes
但是 Uniform Data 以及 Indipendent Predicates 假设往往回导致估算的不准确
比如在下面的例子中，对于选择率的计算
上图的公式和最终实际的结果差了一个数量级(因为从现实角度来讲，Makes 和 Models 这俩条件是相关的)
那么解决办法是什么呢
可以声明 makes 和 models 这些列是相关的，那么数据库系统就可以将它们当作特殊案例来进行处理，以此规避掉这些问题
## Cost Estimations
数据库系统会在内部维护这些直方图来跟踪这些信息
纵坐标是值的出现频率，横坐标是属性的值
但是真实数据不长这样
真实数据更具备倾向性
那么这样的数据怎么追踪呢
就是将这些数据划分到不同的 bucket 中，一个 bucket 只保存一个值，不会为一个 bucket 中的每个元素都去保存一个值
比如
这个就被称之为等宽直方图(Equi-Width Histogram)，下面的值是这个 bucket 中每个值出现的次数的总和
那么新的直方图中显示的就是这些聚合后的值
当然这种方式虽然节省空间，但是问题也存在，就是不知道这些值中哪个值得出现次数是比较高的
那么怎么解决这个问题呢? 用分位数(Quantiles)
## Histograms with Quantiles
主要是通过调整 bucket 的宽度，使每个 bucket 的 count 总和都大致相等
就像上图中表示的这样
那么结果就是
## Sampling
本质上就是，通过维护一个样本表，然后根据该样本来衍生出统计信息
直方图就像是数据库中的表的数据的一种低解析度副本，它是对其他内容的一种近似缩略表达
那么在不通过用直方图来衍生统计信息的情况下，该如何拿到基于该表本身的一个更小的副本呢?
先从表中进行取样，拿到一个 tuple，然后将它们复制到一个样本表(table sample)中
这个时候计算 age > 50 的选择率
计算出来的结果就是 1/3，那么此时可以假设，在完整的表中，不同值的选择率会与之相符
在查询时，就可以对这个表进行维护，或者当表中有很大一部分数据发生改变，比如批量加载表中数据，或者批量删除表中数据，此时就可以触发更新这些数据了
## Observation
通过粗略的估计这些条件的条件的选择率，我们还能做到什么呢?
当然是可以通过成本模型或者 Cost-based search 来进行查询优化
## Single-Relation Query Planning
对于 single-relation query 这种情况而言，最难的就是选择对应的 access method
而另一件事情就是预估条件时的顺序
如何去选择最优的 access method 呢? 在查询优化器中使用一些简单的启发式规则就好了。这对于那些 OLTP 类的查询来说是最简单的，因为这种查询本身访问的数据量并不多
## OLTP Query Planning
对于 OLTP 查询来说，首先要做的就是试着鉴定这个查询是否是 Search Argumentable 的。即在执行查询时，可以使用一个索引来帮助查询，而对于这个查询来说，使用这个索引是一个最佳选择
例子
SQL 语句如上图所示
这里有一个启发式规则: `id INT PRIMARY KEY`，表示 id 是一个主键
如果这里有一个索引，用它就完事了(可以使用这个索引来做索引扫描)
## Multi-Relation Query Planning
随着要 Join 的表的数量增加，Join 操作时产生的备选方案的数量也会增加。所以这里就需要对这些方案做一个剪枝处理
System R 一个基础假设是，只考虑左连接树的情况(left-deep join tree)
那么什么是 left-deep join tree?
它实际上长这样
join 操作会沿着这棵树的左边进行(左一就是 left-deep join tree)
左二像是大杂烩(有些在左边 Join，有些在右边 Join)
左三为 bushy tree
IBM 的 System R 不会考虑左二和左三
这样做有什么好处呢?
使用 left-deep join tree，就像一个 pipeline，在过程中不需要延后生成某个 Join operator 的输出结果，因为它始终是下一个 Join operator 的输入，就不用中间产生一些临时数据写到磁盘中，那么就可以最小化写入磁盘的数据量
即
那么如何枚举查询计划呢
首先要做的就是，从逻辑层面来枚举所有可能的不同的执行 Join 操作的顺序
但是有可能这个顺序会非常之多
在 1970 年代，IBM 那帮人就提出了一种叫动态编程的技术，即通过将一个大问题分解为一些较小的小问题，然后让问题变得更容易解决
例子
首先要做的就是计算出，在使用不同的 Join 算法的情况下，第一步的成本是多少(可以使用 Hash Join 或者 SortMerge Join)
然后通过之前讲的那些公式来计算出这些 Join 操作的执行成本
成本比较之后，选择执行成本最低的那个 Join 算法
下一步继续 Join 之前，执行类似的操作
同样的，只保留执行成本最低的那个 Join 算法
那么最终这个查询计划要使用的执行方案，就是下面这个
以上就是 动态编程 基本思想的体现
## Candidate Plan Example
在对 R S T 这 3 个表进行 Join 时，列出可能会使用的 Join 顺序
过滤掉一些不需要的，然后查看每个查询计划树
然后对于某个查询计划树，列出所有可以使用的不同的 Join 算法
> NLJ: Nest-Loop Join
HJ: Hash Join
然后再选择一个 Join 算法
然后列出所有可以使用的 access method
## Postgres Optimizer
pg 除了有之前提到的那个动态编程算法之外，它还有一个自己的遗传查询优化器，它这个遗传查询优化能应对更大的搜索范围
例子
首先列出查询计划相关的一堆不同的随机配置(Join 顺序、索引/循序扫描、要使用的 Join 算法等)
然后计算出这些配置的执行成本
选出一个最低成本的，然后将最高成本的丢弃，保留中间的方案，并且基于除了最高成本的那些方案进行随机处理，以此生成新的查询计划
接下来做一些类似的操作
然后生成下一个方案
这有点像模拟退火遗传算法?
## Nested Sub-Queries
对每一个在外部查询中看到的 tuple 放到内部查询去做评估，MySQL 以前是这样做的
如何做嵌套的子查询?
1. 通过重写查询来去掉彼此关联性，做扁平化处理
2. 将内部查询提取出来，作为一个单独的查询来执行，然后将这个查询的结果传入外层查询
例子
### Rewrite
在这个例子中，外部查询 S 和内部查询 R 是相关联的，所以需要将他重写为 Join
### Decompose
当在画橘色圈的位置进行查找时，对于 Outer Table(sailor 表) 上的每个 tuple 来说，就需要不断反复执行这段逻辑，但是这个很操蛋
所以这个时候需要将它提取出来，这样就无需每次都执行一遍了
那么怎么做呢? 就是把这个内嵌的语句拿出来，保存为某个变量
然后用这个变量去做一个对应的替换
## 结论
