『database-7』optimization

查询处理与优化

一、关系查询处理步骤

• 查询分析：SQL 词法分析 + 语法分析

• 查询检查：语义检查 + 存取权限检查 + SQL \(\Rightarrow\) 关系代数

• 查询优化：选择高效执行的查询处理策略

• 查询执行：生成查询计划代码

  ---

• 查询代价度量：

  • 驻留在磁盘上的大型数据库：I/O代价
  • 取一个块就访问一次磁盘：访盘块数

---

二、查询操作的实现

• 选择操作：

  • 全表扫描法：按物理顺序读取表的 M 块到内存，将 M 块中满足条件的元组 t 输出
  • 索引扫描法：若在选择条件的属性上建有索引，先根据索引域找到目标索引项，再通过索引项找到元组t

• 连接操作：

  • 嵌套-循环法：将较小表 s 作为外表，r 作为内表，缓冲区 k-1 块分配给外表 r，1 块分配给内表 s
    则总 I/O 次数 = \(\text{b}_r + \dfrac{\text{b}_r}{k-1} * \text{b}_s\)，前项表示内表的总 I/O 次数、后项表示外表的总 I/O 次数
  • 索引连接法：若关系s的连接属性上有索引，对于每个元组\(\text{t}_r\)，可根据索引查找s中满足连接条件的\(\text{t}_s\)
  • 排序合并法：分为两步
    1. 将关系r和s分别根据连接属性排序
    2. 设两个动指针 \(\text{p}_r\) 和 \(\text{p}_s\)，对于 \(\text{p}_r\) 指向的连接属性值，移动 \(\text{p}_s\) 找到 s 中与 r 值相等的元组
  • Hash-Join 法：设哈希函数为hash
    1. hash 将连接属性映射到{0, ..., n}，根据连接属性将关系 r 划分为 \(\text{r}_0, ..., \text{r}_n\)，将 s 划分为 \(\text{s}_0, ..., \text{s}_n\)
    2. 将 \(\text{r}_i\) 和 \(\text{s}_i\) 中的元组相比较进行连接运算；这种方法仅适用于等值（or 自然）连接

• 排序：分两种情况

  • 内存中可完全容纳的关系：直接快速排序
  • 内存中不可完全容纳关系：外排序 - 归并法，即先建立多个内部有序的归并段，再对各归并段排序

• 去重：先使重复数据相邻，再保留其中一个

• 投影：在每个元组上执行投影，之后去重

• 集合运算：类似 排序合并法 or Hash-Join 法

  ---

• 表达式的执行：分为 物化 or 流水线方法

  • 物化：运算结果被物化到一个临时关系中，临时关系一般需要写回磁盘（适用范围广，但读写开销大）
  • 流水线：直接将运算结果传递给下一个运算，不存储临时关系

---

三、查询优化

• 查询优化目标：选择高效执行的查询处理策略，使查询代价最小，即访问磁盘块数最少

• 关系代数表达式等价变换规则：

  • 连接（×）和 笛卡尔积（\(\Join\)）遵循交换律、结合律
  • 投影 和 选择 遵循串接律（两步压缩成一步运算）
  • 选择 和 投影 遵循交换律（先选择，后投影）
  • 选择 与 笛卡尔积 遵循交换律（可将“选择F”拆分作用在内层仅含 \(\text{F}_i\) 中属性的关系上，达到先选择后求积）
  • 选择 与 并、差、自然连接 遵循分配律（可将“选择F”直接作用在内层关系上，再做并、差、自然连接运算，达到先选择后运算）
  • 投影 与 笛卡尔积 遵循分配律（可将投影属性按关系拆成两部分，先分别投影再连接，达到先投影后求积）
  • 投影 与 并 遵循分配律（可将投影直接作用在内层关系上，再取并集，达到先投影后求并）

• 查询树的启发式优化：

  • 选择运算尽早执行（减少元组数目）
  • 投影运算尽早执行（减少属性数目）
  • 笛卡尔积 + 选择 \(\Rightarrow\) 条件连接（笛卡尔积得到的中间结果往往很大）
  • 找出公共子表达式，把公共子表达式的结果写入中间文件，复用运算结果

  ---

• 物理优化：

  • 基于启发式规则的操作算法选择：
    • 选择操作：小关系直接全表扫描；大关系可采用索引扫描
    • 连接操作：
      • 两表均按连接属性排序使用：排序-合并法
      • 一个表上的连接属性有索引：索引连接法
      • 连接属性上未建索引 且 未排序：Hash-Join法
      • 最后使用嵌套循环法，并选择小表作为外循环表
  • 基于代价估算的优化：基于数据库统计信息计算各种操作的执行代价，选择具有最小代价的执行计划