XII. Query Optimization

Introduction

• 基于成本的查询优化(cost-based query optimization) 具体步骤：

  • 使用 等价规则(equivalence rule) 生成逻辑等价的表达式．

  • 以不同方式标注结果表达式以获得不同的 查询计划(query plan)．

  • 选择 估计成本(estimation cost) 最低的查询计划．

Equivalence Rules

• R1：合取选择可分解：$\sigma_{\theta_{1} \land \theta_{2}}(E) = \sigma_{\theta_{1}}\left( \sigma_{\theta_{2}}(E) \right)$．

• R2：选择可交换：$\sigma_{\theta_{1}}\left( \sigma_{\theta_{2}}(E) \right) = \sigma_{\theta_{2}}\left( \sigma_{\theta_{1}}(E) \right)$．

• R3：连续多次投影只需要最后一个：$\Pi_{L_{1}}\left( \Pi_{L_{2}}(E) \right) = \Pi_{L_{1}}(E)$．

• R4：选择操作可以与笛卡尔积和 $\theta$ 连接相结合：$\sigma_{\theta}\left( E_{1} \times E_{2} \right) = E_{1}\Join_{\theta}E_{2}$；$\sigma_{\theta_{1}}\left( E_{1}\Join_{\theta_{2}}E_{2} \right) = E_{1}\Join_{\theta_{1} \land \theta_{2}}E_{2}$．

• R5：$\theta$ 连接/自然连接可交换：$E_{1}\Join_{\theta}E_{2} = E_{2}\Join_{\theta}E_{1}$；$E_{1}\Join E_{2} = E_{2}\Join E_{1}$．

• R6a：自然连接可结合：$\left( E_{1}\Join E_{2} \right)\Join E_{3} = E_{1}\Join\left( E_{2}\Join E_{3} \right)$．

• R6b：设 $\theta_{2}$ 只涉及到 $E_{2}$ 和 $E_{3}$ 的属性，则有 $\left( E_{1}\Join_{\theta_{1}}E_{2} \right)\Join_{\theta_{2} \land \theta_{3}}E_{3} = E_{1}\Join_{\theta_{1} \land \theta_{3}}\left( E_{2}\Join_{\theta_{2}}E_{3} \right)$．

TBD：后面的会用到吗？

Cost Estimation

• 成本估计时不仅需考虑每个 运算符(operator) 的成本，还要考虑到中间结果的规模带来的影响．

• 符号约定：对于关系 $r$，

  • $n_{r}$ 表示 $r$ 中的元组数量．

  • $l_{r}$ 表示 $r$ 中单个元组的大小．

  • $f_{r}$ 表示一个块中可以容纳的 $r$ 的元组数量．

  • $b_{r}$ 表示 $r$ 中的块的数量，$b_{r} = \left\lceil {n_{r}\text{ / }f_{r}} \right\rceil$．

  • $V(A,r)$ 表示 $r$ 中属性 $A$ 的不同取值数量．

• 直方图(histogram) 可用来表示关系中每个属性的取值分布情况．

  • 在一些规模估计中，可以通过直方图改进．否则一般按照均匀分布进行估计．

Estimation of Size

Size Estimation of Selections

• $\sigma_{A = V}(r)$：

  • 一般情况：$\widetilde{\mathrm{\text{size}}} = \frac{n}{V(A,r)}$．

  • 当 $V$ 是 $r$ 的主键时 $\mathrm{\text{size}} = 1$．

• $\sigma_{A \leq V}(r)$（和 $\sigma_{A \geq V}$ 是对称的）

  • 如果可从 catalog 中获取 $\min(A,r)$ 和 $\max(A,r)$，则 $\widetilde{\mathrm{\text{size}}} = {n_{r} \cdot \frac{v - \min(A,r)}{\max(A,r) - \min(A,r)}}$（假设均匀分布）．

  • 如果缺乏统计信息，可估计为 $\widetilde{\mathrm{\text{size}}} = \frac{n_{r}}{2}$．

Size Estimation of Complex Selections

• 用 中选率(selectivity) $\frac{s_{i}}{n_{r}}$ 来表示关系 $r$ 中的单个元组满足 $\theta_{i}$ 的概率．

• 合取 $\sigma_{\theta_{1} \land \theta_{2} \land \ldots \land \theta_{n}}(r)$：$\widetilde{\mathrm{\text{size}}} = {n_{r} \times \frac{s_{1} \times s_{2} \times \ldots \times s_{n}}{n_{r}^{n}}}$．

• 析取 $\sigma_{\theta_{1} \vee \theta_{2} \vee \ldots \vee \theta_{n}}(r)$：$\widetilde{\mathrm{\text{size}}} = n_{r} \times \left( 1 - \left( 1 - \frac{s_{1}}{n_{r}} \right) \times \left( 1 - \frac{s_{2}}{n_{r}} \right) \times \ldots \times \left( 1 - \frac{s_{n}}{n_{r}} \right) \right)$．

• 否定 $\sigma_{\neg\theta}(r)$：$\widetilde{\mathrm{\text{size}}} = n_{r} - \widetilde{\mathrm{\text{size}}}(\sigma_{\theta(r)})$．

Size Estimation of Joins

• 如果 $R \cap S = \varnothing$，则自然连接退化为笛卡尔积．$\mathrm{\text{size}}(r\Join s) = \mathrm{\text{size}}(r \times s) = n_{r} \times n_{s}$，且每个元组的大小为 $l_{r} + l_{s}$．

• 如果 $R \cap S$ 是 $R$ 的键（$R \cap S \subseteq R$），则 $\mathrm{\text{size}}(R\Join S) \leq n_{s}$，因为对于 $s$ 中的每个元组都可以找到 $r$ 中的至多一个元组与之匹配．

• 如果 $R \cap S$ 是 $S$ 中引用 $R$ 的外键，则 $\mathrm{\text{size}}(R\Join S) = n_{s}$，因为 $s$ 中的每个元组都能外键的完整性保证能恰好找到一个元组与之匹配．

• 如果 $R \cap S = \left\{ A \right\}$ 不是 $R$ 或 $S$ 的键，则 $\widetilde{\mathrm{\text{size}}} = {\min(\frac{n_{r} \times n_{s}}{V(A,r)},\frac{n_{r} \times n_{s}}{V(A,s)})}$．两种估计分别是假设 $r$（或 $s$）中的每个元组都能在另一个中找到若干个元组 与之匹配．

select * from instructor natural join teaches on ID
where dept_name='CS' and salary >=70000;

(*) Size Estimation of Other Operations

• 投影：$\widetilde{\mathrm{\text{size}}}(\Pi_{A}(r)) = V(A,r)$

• 聚合：$\widetilde{\mathrm{\text{size}}}({{}_{A}\mathbf{g}_{F}}(r)) = V(A,r)$

• 集合操作：一般设为其上限 $\widetilde{\mathrm{\text{size}}}(r \cup s) = \mathrm{\text{size}}(r) + \mathrm{\text{size}}(s)$，$\widetilde{\mathrm{\text{size}}}(r \cap s) = \min(\mathrm{\text{size}}(r),\mathrm{\text{size}}(s))$，$\widetilde{\mathrm{\text{size}}}(r - s) = \mathrm{\text{size}}(r)$．

• 外连接：预留未找到匹配的元组的大小 $\widetilde{\mathrm{\text{size}}}(r\mathrm{⟕}s) = \mathrm{\text{size}}(r\Join s) + n_{r}$，$\widetilde{\mathrm{\text{size}}}(r\mathrm{⟗}s) = \mathrm{\text{size}}(r\Join s) + n_{r} + n_{s}$．

Estimation of Number of Distinct Values

TBD：有点没看懂

• $V(A,)$

Choice of Evaluation Plans

Cost-Based Join-Order Selection

• 如果暴力计算，则需要考虑 $\frac{\left( 2(n - 1) \right)!}{(n - 1)!}$ 种可能，情况太多．

• 可以考虑使用动态规划，$\left\{ r_{1},r_{2},\ldots,r_{n} \right\}$ 的每个子集的”基于成本的最优连接顺序选择”是确定的，只需要计算一次．

• 左深连接树(left-deep join tree)：要求每个连接的右操作数都是一个关系而非中间连接的结果．

  • 许多优化器只考虑左深连接树顺序，以简化情况．

Additional Optimization Techniques

Nested Subqueries

TBD

Materialized Views

• 物化视图(materialized view)：每次重新计算 视图(view) 的代价很高，可以将视图的计算结果存储在磁盘上．

• 推荐使用 增量视图维护(incremental view maintenance) 的策略，每次更新后只更新变化的部分．

• 增量维护连接操作：$v = r\Join s$．

  • 插入：$r^{\text{new }} = r^{\text{old }} \cup i_{r} \Longrightarrow v^{\text{new }} = \left( r^{\text{old }} \cup i_{r} \right)\Join s = \left( r^{\text{old }}\Join s \right) + i_{r}\Join s = v^{\text{old }} + i_{r}\Join s$．

  • 删除：$r^{\text{new }} = r^{\text{old }} - d_{r} \Longrightarrow v^{\text{new }} = \left( r^{\text{old }} - d_{r} \right)\Join s = \left( r^{\text{old }}\Join s \right) - d_{r}\Join s = v^{\text{old }} - d_{r}\Join s$．

• 增量维护选择操作：$v = \sigma_{\theta}(r)$．

  • 插入：$r^{\text{new }} = r^{\text{old }} \cup i_{r} \Longrightarrow v^{\text{new }} = \sigma_{\theta}\left( r^{\text{old }} \cup i_{r} \right) = \sigma_{\theta}\left( r^{\text{old}} \right) \cup \sigma_{\theta}\left( i_{r} \right) = v^{\text{old }} \cup \sigma_{\theta}\left( i_{r} \right)$．

  • 删除：$r^{\text{new }} = r^{\text{old }} - d_{r} \Longrightarrow v^{\text{new }} = \sigma_{\theta}\left( r^{\text{old }} - d_{r} \right) = \sigma_{\theta}\left( r^{\text{old}} \right) - \sigma_{\theta}\left( d_{r} \right) = v^{\text{old }} - \sigma_{\theta}\left( d_{r} \right)$．

• 增量维护投影操作：需要对投影的结果进行一个计数，以确保正确的增量更新，参考下面的例子．