ch16 查询优化

概述

• 选择一个给定查询的执行方法，一个表达式有多个等价表达式，每个运算又有不同的算法
• 执行计划：准确的定义了每个运算应使用的算法，以及运算之间的执行应该如何协调
• 一个查询的不同执行计划的代价差异天差地别
• 基于代价的优化步骤：
  1. 使用等价规则产生逻辑等价表达式
  2. 注解结果表达式来得到替代查询计划
  3. 基于代价估计选择代价最小的计划
• 计划代价估计基于
  • 关系统计信息
  • 用于中间结果的统计估计
  • 算法的代价估计，使用统计来计算

关系表达式转换

• 如果两个关系代数表达式在所有有效数据库实例中都会产生相同的元组集合，则等价（顺序无关紧要）
• 在SQL中，输入输出都是元组的多重集合
• 等价规则指出两种不同形式的表达式是等价的

等价规则

1. 合取选择运算可分解

$${\sigma }_{{\theta }_1\wedge {\theta }_2}(E)={\sigma }_{{\theta }_1}({\sigma }_{{\theta }_2}(E))$$

2. 选择运算交换律

$${\sigma }_{{\theta }_1}({\sigma }_{{\theta }_2}(E))={\sigma }_{{\theta }_2}({\sigma }_{{\theta }_1}(E))$$

3. 一系列投影运算只有最后一个有用

$${\mathrm{\Pi }}_{L_1}({\mathrm{\Pi }}_{L_2}(\dots ({\mathrm{\Pi }}_{L_n}(E))\dots ))={\mathrm{\Pi }}_{L_1}(E)$$

4. 选择操作和笛卡尔积以及 $\theta$ 连接结合

$${\sigma }_{\theta }(E_1\times E_2)=E_1{\bowtie }_{\theta }{E}_2$$$${\sigma }_{{\theta }_1}(E_1{\bowtie }_{{\theta }_2}{E}_2)=E_1{\bowtie }_{{\theta }_1\wedge {\theta }_2}{E}_2$$

5. $\theta$ 连接满足交换律

$$E_1{\bowtie }_{\theta }{E}_2=E_2{\bowtie }_{\theta }{E}_1$$

6. 连接运算在满足以下条件情况下有结合律
   • 自然连接满足结合律
   $$(E_1\bowtie E_2)\bowtie E_3=E_1\bowtie (E_2\bowtie E_3)$$
   • $\theta$ 连接具有以下方式的结合律（其中 ${\theta }_2$ 只涉及到 $E_2$ 和 $E_3$ 的属性）
   $$\begin{array}{r}(E_1{\bowtie }_{{\theta }_1}{E}_2){\bowtie }_{{\theta }_2\wedge {\theta }_3}{E}_3=\\ E_1{\bowtie }_{{\theta }_1\wedge {\theta }_3}(E_2{\bowtie }_{{\theta }_2}{E}_3)\end{array}$$
7. 选择运算在以下两个条件下对 $\theta$ 连接具有分配律
   • 当选择条件 ${\theta }_0$ 的所有属性只涉及到参与连接运算的表达式之一（比如 $E_1$）时，满足分配律
   $${\sigma }_{{\theta }_0}(E_1{\bowtie }_{\theta }{E}_2)=({\sigma }_{{\theta }_0}(E_1)){\bowtie }_{\theta }{E}_2$$
   • 当选择条件 ${\theta }_1$ 只涉及到 $E_1$ 的属性，当选择条件 ${\theta }_2$ 只涉及到 $E_2$ 的属性，满足分配律：
   $${\sigma }_{{\theta }_1\wedge {\theta }_2}(E_1{\bowtie }_{\theta }{E}_2)=$$$$({\sigma }_{{\theta }_1}(E_1)){\bowtie }_{\theta }({\sigma }_{{\theta }_2}(E_2))$$
8. 投影运算在下列条件下对 $\theta$ 连接具有分配律
   • 假设连接条件 $\theta$ 只涉及到 $L_1\cup L_2$ 中的属性
   $${\mathrm{\Pi }}_{L_1\cup L_2}(E_1{\bowtie }_{\theta }{E}_2)=$$$$({\mathrm{\Pi }}_{L_1}(E_1)){\bowtie }_{\theta }({\mathrm{\Pi }}_{L_2}(E_2))$$
   • 考虑连接 $E_1{\bowtie }_{\theta }{E}_2$:
     • 令 $L_1$ 和 $L_2$ 分别代表 $E_1$ 和 $E_2$ 的属性集合
     • 令 $L_3$ 是 $E_1$ 中出现在连接条件 $\theta$ 中但不在 $L_1\cup L_2$ 中的属性
     • 令 $L_4$ 是 $E_2$ 中出现在连接条件 $\theta$ 中但不在 $L_1\cup L_2$ 中的属性
   $${\mathrm{\Pi }}_{L_1\cup L_2}(E_1{\bowtie }_{\theta }{E}_2)=$$$${\mathrm{\Pi }}_{L_1\cup L_2}(({\mathrm{\Pi }}_{L_1\cup L_3}(E_1)){\bowtie }_{\theta }({\mathrm{\Pi }}_{L_2\cup L_4}(E_2)))$$
9. 集合的交和并满足交换律，但是差集不满足

$$E_1\cup E_2=E_2\cup E_1$$$$E_1\cap E_2=E_2\cap E_1$$

10. 集合的并和交满足结合律

$$(E_1\cup E_2)\cup E_3=E_1\cup (E_2\cup E_3)$$$$(E_1\cap E_2)\cap E_3=E_1\cap (E_2\cap E_3)$$

11. 选择运算对并交差有分配律

$${\sigma }_{\theta }(E_1\cup E_2)={\sigma }_{\theta }(E_1)\cup {\sigma }_{\theta }(E_2)$$$${\sigma }_{\theta }(E_1\cap E_2)={\sigma }_{\theta }(E_1)\cap {\sigma }_{\theta }(E_2)$$$${\sigma }_{\theta }(E_1-E_2)={\sigma }_{\theta }(E_1)-{\sigma }_{\theta }(E_2)$$

注意：以下两条对并不成立

$${\sigma }_{\theta }(E_1-E_2)={\sigma }_{\theta }(E_1)-E_2$$$${\sigma }_{\theta }(E_1\cap E_2)={\sigma }_{\theta }(E_1)\cap E_2$$

12. 投影运算对并有分配律

$${\mathrm{\Pi }}_L(E_1\cup E_2)=({\mathrm{\Pi }}_L(E_1))\cup ({\mathrm{\Pi }}_L(E_2))$$

转换实例

• 查询所有音乐系老师的名字以及他们所教课程的名称

• 尽可能早的执行选择操作能减小被链接关系的大小
• 通过投影下推，尽早的执行投影能减小被连接的关系的大小
• 尽可能选择较小的两个表先做连接，对于所有的关系 $r_1,r_2,r_3$ ，他们之间互相连接有结合律成立。如果 $r_2\bowtie r_3$ 较大，$r_1\bowtie r_2$ 较小，选择先对 $r_1\bowtie r_2$ 进行运算

$$(r_1\bowtie r_2)\bowtie r_3$$

表达式结果集统计大小的估计

• 目录信息
  • $n_r$：关系 $r$ 的元组数
  • $b_r$：包含关系 $r$ 中元组的磁盘块数
  • $f_r$：关系 $r$ 的块因子，指的是一个磁盘块能容纳关系 $r$ 中的元组个数
  • $l_r$：关系 $r$ 中每个元组的字节数
  • $V(A,r)$：关系 $r$ 中属性 $A$ 中出现的非重复值的个数，该值与 ${\mathrm{\Pi }}_A(r)$ 相同

$$b_r=\lceil \frac{n_r}{f_r}\rceil$$

直方图

略（你让我$\mathrm{L}\mathrm{A}\mathrm{T}\mathrm{E}\mathrm{X}$给你搓一个直方图出来？我哪有这个功能）

选择运算结果的大小估计

• ${\sigma }_{A=v}(r)$
  • 满足选择记录数：$n_r/V(A,r)$ （认为分布均匀）
  • 码上的等值比较规模估计为 $1$
• ${\sigma }_{A\le v}(r)$ （${\sigma }_{A\ge v}(r)$ 的例子是对称的）
  • $c$ 表示满足条件元组的估计数
  • 如果 $min(A,r)$ 和 $max(A,r)$ 可储存到目录上
  • 若 $v<min(A,r)$ 则 $c=0$
  • $c=n_r\cdot \frac{v-min(A,r)}{max(A,r)-min(A,r)}$ （假定平均）
  • 如果有直方图可以得到更精准的估计
  • 不存在统计信息的时候假定 $c=n_r/2$

复杂选择运算结果的大小估计

• 条件 ${\theta }_i$ 的选中率是关系 $r$ 上一个元组满足 ${\theta }_i$ 的概率
  • 如果 $s_i$ 是关系 $r$ 中满足条件的元组数，则选中率 ${\theta }_i=s_i/n_r$
  • 对于合取：${\sigma }_{{\theta }_1\wedge {\theta }_2\wedge ...\wedge {\theta }_n}(r)$，选中率为
  $$\theta =n_r\ast \prod _{i=1}^n{\theta }_i=n_r\ast \frac{\prod _{i=1}^n{s}_i}{n_r^n}$$
  • 对于析取：${\sigma }_{{\theta }_1\vee {\theta }_2\vee ...\vee {\theta }_n}(r)$
  $$\theta =n_r\ast (1-\prod _{i=1}^n(1-\frac{s_i}{n_r}))$$
  • 对于否定：${\sigma }_{\mathrm{\neg }\theta }(r)$
  $$\theta =n_r-size({\sigma }_{\theta }(r))$$
• 笛卡尔积 $r\times s$ 包含 $n_r{n}_s$ 个元组，每个元组占用 $S_r+S_s$ 个字节
• 若 $R\cap S=\varnothing$ ，则 $r\bowtie s$ 与 $r\times s$ 结果一样
• 若 $R\cap S$ 是 $R$ 的码，则可知 $s$ 的一个元组至多与 $r$ 的一个元组相连接，因此，$r\bowtie s$ 的元组数不会超过 $s$ 中元组的数目
• 若 $R\cap S$ 是 $S$ 中参照 $R$ 的外码，$r\bowtie s$ 中的元组数正好与 $s$ 的元组数相等，$R\cap S$ 是参照 $S$ 的外码的例子，与之对称
• 若 $R\cap S=\{A\}$ 既不是 $R$ 的码也不是 $S$ 的码
  • 假设 $R$ 中的所有元组在 r \bowtie s$ 中产生的元组个数估计为 $\frac{n_r{n}_s}{V(A,s)}$
  • 如果情况正好相反，则元组数估计为 $\frac{n_s{n}_r}{V(A,r)}$
  • 这两个值中的较小者可能比较准确
  • 有直方图可以更准确

执行计划选择

• 当选择执行计划时，必须要考虑执行技术的相互作用
  • 为每个操作独立选择代价最小的算法可能不会产生整体最佳的算法
• 实际的查询优化器优化器合并了以下两大方法中的元素

基于代价的优化

• 考虑为表达式 $r_1\bowtie r_2\bowtie \dots \bowtie r_n$ 寻找最佳链接顺序
• 不必产生所有的连接顺序
  • 使用动态规划，任意子集的最小代价的连接顺序只计算一次并储存起来

左深连接树

略

代价优化

• 使用动态规划算法产生最佳连接顺序的时间复杂度是 $O(3^n)$ ，空间复杂度是 $O(2^n)$
• 如果只考虑左深树，找到最佳连接顺序的时间复杂度是 $O(n{2}^n)$，空间复杂度是 $O(2^n)$
• 基于代价的优化是昂贵的，但是对于大型数据库上的查询是值得的（典型的查询 $n$ 很小，通常 $n<10$）

启发式优化

• 基于代价的优化的缺点是优化本身的代价，即使动态规划也如此
• 查询优化器使用启发式方法来减小优化代价
• 启发式优化通过使用一系列规则转化查询树来改善执行性能（尽可能早的执行投影和选择）