关系查询处理

• 处理过程
  • 步骤
    • 查询分析：词法分析、语法分析、语义分析。
    • 查询检查：安全性检查、完整性检查、有效性检查。
    • 构建内部表示语法树。
    • 查询优化。
    • 查询计划执行。
  • 方式
    • 解释处理、编译处理。
• 查询处理算法实现
  • 选择
    • 顺序扫描：逐个扫描每个元组，收集所有满足条件的元组。
      • 适用于尺寸小或选择率大的表。
      • 代价估算：平均 $\left\lceil \dfrac{B}{2} \right\rceil$，$B$ 为数据块个数。
    • 二分扫描：条件为属性相等性、元组储存有序时，用二分法查找。
      • 代价估算：$\left\lceil \log_2 B \right\rceil$。
    • 索引扫描：当查询条件与索引匹配时，通过索引找到所有满足条件的元组。
      • 代价估算（B+ 树索引）
        • 唯一属性相等比较：$L + 1$，$L$ 为层数，根节点为 $0$ 层。
        • 可重属性相等比较：最坏 $L + S$，$S$ 为满足条件的元组个数。
        • 偏序比较：
  • 合取选择
    • 组合索引：如果多个相等性条件对应属性的组合存在索引，就直接使用索引。
    • 单个索引：用一个属性的索引筛选属性，再进一步检查其他条件。
    • 多个索引：用每个条件的索引分别筛选，再取交集。
    • 使用索引时，应当优先使用选择率低的属性的索引。
  • 析取选择
    • 多个索引：每个条件都有索引时，使用每个索引筛选再合并。
    • 其他情况下，基本无法优化。
  • 连接
    • 嵌套循环法：顺序扫描外循环表，对其中每个元组再顺序扫描内循环表，检查连接条件。
      • 使用块数少的表作为外循环，代价更小。
      • 适用于任何连接条件。
    • 索引嵌套循环法：基于嵌套循环法，用索引扫描代替顺序扫描。
    • 排序合并法：将两个表排序，再同时顺序扫描检查连接条件。
      • 需要额外的排序时间。
    • 哈希连接：将一个表按哈希划分到桶，另外一个表的元组与哈希相同的桶中的元组连接。
      • 前一步称为划分阶段，后一步称为试探阶段/连接阶段。
      • 划分到桶的表需要较小、可以放入内存。
  • 投影
    • 被选择属性包含主键或唯一属性时，无论是否指定去重都无需去重。
    • 其他情况下且指定需要去重时，用排序去重或哈希去重。
  • 集合运算
    • 交、并、差通常使用排序合并法。
    • 笛卡尔积通常使用嵌套循环法。