高级数据库系统知识点总结（Part 3）

查询优化、连接算法

查询优化

• 重点内容：整个查询的工作过程（逻辑优化、物理优化）；中间结果的大小估计；查询计划的IO代价计算

工作流程

1. 初始逻辑查询计划生成：将语法分析树转换为关系代数表达式树——逻辑查询计划（使用关系代数）
2. 查询重写：将初始逻辑查询计划转换为优化的逻辑查询计划
   1. 基于代数转换规则
3. 估计中间结果大小结果大小

查询代价估计

1. 中间关系大小估计
2. IO代价估计
3. 物理查询计划生成
   其中1和2要在内存里完成（磁盘IO代价太高）

中间结果的大小估计

需要用到的一些统计量，也即估计目标：

1. T(R)：R的元组数
2. S(R)：R中每个元组的大小（Bytes）
3. V(R,A)：R的属性A上的不同值数
4. B(R): 容纳R所有元组所需的块数

• 例子：R=

A	B	C	D
cat	1	10	a
cat	1	20	b
dog	1	30	a
dog	1	40	c
bat	1	50	d

A: 20 byte string; B: 4 byte integer; C: 8 byte date; D: 5 byte string

• 则 T(R)=5, S(R)=37, V(R,A)=3, V(R,B)=1, V(R,C)=5, V(R,D)=4

1. W = R1 R2 的大小估计
   1. T(W) = T(R1) * T(R2)
   2. S(W) = S(R1) + S(R2)
2. W = (R) 的大小估计
   1. S(W) = S(R)
   2. T(W) = s * T(R). （分类讨论：=，，） $$s=\left\{ \begin{aligned} &\frac{1}{V(R,z)}&, p为\text{“}z=val\text{”}比较时\\ &1-\frac{1}{V(R,z)}&, p为\text{“}z\neq val\text{”}比较时\\ &\left. \begin{aligned} &1/2 或\\ &1/3 或\\ &范围命中率f \end{aligned}\right\}&, p为\text{“}\leq,\geq,<,>\text{”}比较时 \end{aligned} \right.$$
3. W = R1 R2 的大小估计. 令为R1的属性集合，为R2的属性集合
   1. 若 ，则与R1R2相同
   2. 若 ，且 R1.A上的值都在R2中, 则 $$T(W)=\frac{T(R2)}{V(R2,A)}\times T(R1)$$
   3. 一般地： $$T(W)=\frac{T(R1)\cdot T(R2)}{\max\{V(R1,A),V(R2,A)\}}$$
   4. S(W) = S(R1) + S(R2) - S(A) （容斥原理）
   5. V(W,A) = min{V(R1, A), V(R2, A)}（假设满足值集的包含）

IO代价估计

• 估计目标：指型查询计划所必须读（写）的磁盘块数目
• 影响查询计划IO代价的因素：
  1. 实现查询计划的逻辑操作符
  2. 中间结果的大小
  3. 实现逻辑操作符的物理操作. e.g., 连接操作是用索引连接还是散列连接？
  4. 相似操作的顺序. e.g., 多关系的连接顺序
  5. 物理操作符之家你的参数传递方式（流水线还是物化？）

1. 流水线：多个操作同时执行，一个操作产生的元组直接通过共享内存传递给其他操作
   1. 节省IO
   2. 占用主存，若缓冲区出现“颠簸”则IO增加
2. 物化：操作依次执行，并且每个操作的结果（中间关系）都写到磁盘上共其他操作存取
   1. 通过磁盘物理进行数据传递
   2. 节省主存空间

• 需要的一些参数：
  1. B(R)：R所需的块数
  2. f(R)：每块可容纳的R的最大元组数
  3. M：可用的内存块数
  4. HT(i)：索引i的层数
  5. LB(i)：索引i的叶节点所需的块数

连接算法

• 重点内容：每个连接算法的IO代价估计和内存开销

1. 连接操作的实现算法 （）：
   1. 嵌套循环连接
   2. 归并连接
   3. 索引连接
   4. 散列连接

连接算法的代价分析

1. 影响连接算法代价（I/O）的因素：
   1. 关系的元组是否在磁盘块中连续存放？
   2. 关系是否按连接属性有序？
   3. 连接属性上是否存在索引？

嵌套循环连接代价分析

100个block用来放置R1, 1个block用来放置R2

1. 不连续存放，每个元组都需要一次单独的IO： R1 R2 IO代价=T(R1) * (1 + T(R2)) = 50,010,000
2. 改进的方法（略）
3. 连续存放，设R1和R2被连续存放在块中，则 R1 R2 IO代价=B(R1) / (M - 1) * (M - 1 + B(R2)) = B(R2)

归并连接代价分析

• 沿用嵌套循环连接的例子

1. 连续存放且有序，总IO代价=读R1代价+读R2代价=B(R1) + B(R2)=1,000+500=1,500
2. 连续存放但无序：需要排序但内存有限. 一种排序方法：两阶段多路归并排序
   
   1. 每个元组在两个阶段各有一次读和写，共有4次IO. 故排序IO代价=4 * (B(R1) + B(R2))=6,000
   2. 考虑连续存放且有序时，需要一次读。故整个流程每个元组经历五次IO，总IO代价=5 * (B(R1) + B(R2)) = 7,500
3. Buffer block数的平方必须大于等于排序关系R的块数B(R)
4. 归并算法的改进：将第二阶段的排序和join合并进行，省去一次读一次写，总IO代价=3 * (B(R1) + B(R2))
   1. 要求：R1的chunk数+R2的chunk数M

索引连接代价分析

• R1(A,C) R2(C,D)

  假设R1.C存在索引
  假设R1.C的索引存储在内存中
  假设R2连续存放且无序

raed R2: B(R2) IOs
probe index: no IOs
Read matching R1 tuples: ?

• 关键问题：matching tuples 选中率p的估计

1. 若R1.C是主键，R2.C是外键，则每个R2tuple在R1中，选中率p = 1
2. 若 V(R1,C) < T(R1)，则每个R2 Tuple在R1中的选中率p = T(R1)/V(R1,C) = 2
3. 总而言之，总代价估计 = B(R2) + T(R2) * p
4. 如果R1.C上的Index不能全部放在内存（假设R1.C的一级索引占200块）:
   
   1. 总Io代价=B(R2) + T(R2) * (Probe index cost + p)

散列连接代价分析

假设R1，R2连续存放但无序
假设共有100个哈希桶

1. 第（1）步，内存块数为M，故划分为M-1个桶，每一块对应一个同。最后一块用于读入R1(R2)的一块，计算其中每个元组的h，并将元组复制到对应的块中，共产生2 * (B(R1) + B(R2))次读写
2. 第（2）步，按块读取后归并，共产生(B(R1) + B(R2))次读写
3. 总而言之，总IO代价=3 * (B(R1) + B(R2))
4. 内存要求：min(B(R1), B(R2)) M^2

连接算法的对比总结

R1 R2，连续存放且无序. C是公共属性

假设

对于索引连接，假设索引存于内存中

算法	时间代价	内存要求	适用场景
嵌套循环连接（R2 R1）			相对于内存较小的关系
归并连接			记录有序
归并连接（改进后）			记录有序且R1.C>R2.C
索引连接			索引存在且有用(太大了不行)
散列连接			记录无序且无索引且V(R1.C)V(R2.C)

连接的左右变元选择

• 嵌套循环连接：较小的关系作为左变元
• 归并连接：排序之后较小的关系作为左变元首先读入内存
• 索引连接：有索引的关系作为右变元
• 散列连接：较小的关系作为左变元，散列后读入内存