文档
计算机科学
数据库
关系查询优化

关系查询优化

  • 代数优化
    • 规则
      • 交换律
        • E1×E2=E2×E1E_1 \times E_2 = E_2 \times E_1
        • E1⋈E2=E2⋈E1E_1 \Join E_2 = E_2 \Join E_1
        • E1⋈FE2=E2⋈FE1E_1 \underset{F}{\Join} E_2 = E_2 \underset{F}{\Join} E_1
        • σF(ΠA1,…,An(E))=ΠA1,…,An(σF(E))\sigma_F(\Pi_{A_1, \dots, A_n}(E)) = \Pi_{A_1, \dots, A_n}(\sigma_F(E))，其中 FF 只使用 A1,…,AnA_1, \dots, A_n 中的属性。
        • σF(E1×E2)=σF(E1)×E2\sigma_F(E_1 \times E_2) = \sigma_F(E_1) \times E_2，其中 FF 只使用 E1E_1 中的属性。
        • σF1∧F2(E1×E2)=σF1(E1)×σF2(E2)\sigma_{F_1 \land F_2}(E_1 \times E_2) = \sigma_{F_1}(E_1) \times \sigma_{F_2}(E_2)，其中 F1,F2F_1, F_2 只分别使用 E1,E2E_1, E_2 中的属性。
        • σF1∧F2(E1×E2)=σF2(σF1(E1)×E2)\sigma_{F_1 \land F_2}(E_1 \times E_2) = \sigma_{F_2}(\sigma_{F_1}(E_1) \times E_2)，其中 F1F_1 只使用 E1E_1 中的属性。
      • 结合律
        • (E1×E2)×E3=E1×(E2×E3)(E_1 \times E_2) \times E_3 = E_1 \times (E_2 \times E_3)
        • (E1⋈E2)⋈E3=E1⋈(E2⋈E3)(E_1 \Join E_2) \Join E_3 = E_1 \Join (E_2 \Join E_3)
        • (E1⋈F1E2)⋈F2E3=E1⋈F1(E2⋈F2E3)(E_1 \underset{F_1}{\Join} E_2) \underset{F_2}{\Join} E_3 = E_1 \underset{F_1}{\Join} (E_2 \underset{F_2}{\Join} E_3)
      • 分配律
        • σF(E1∪E2)=σF(E1)∪σF(E2)\sigma_F(E_1 \cup E_2) = \sigma_F(E_1) \cup \sigma_F(E_2)
        • σF(E1∩E2)=σF(E1)∩σF(E2)\sigma_F(E_1 \cap E_2) = \sigma_F(E_1) \cap \sigma_F(E_2)
        • σF(E1−E2)=σF(E1)−σF(E2)\sigma_F(E_1 - E_2) = \sigma_F(E_1) - \sigma_F(E_2)
        • σF(E1⋈E2)=σF(E1)⋈σF(E2)\sigma_F(E_1 \Join E_2) = \sigma_F(E_1) \Join \sigma_F(E_2)，其中 FF 只使用 E1,E2E_1, E_2 中的公共属性。
        • ΠA1,…,An(E1∪E2)=ΠA1,…,An(E1)∪ΠA1,…,An(E2)\Pi_{A_1, \dots, A_n}(E_1 \cup E_2) = \Pi_{A_1, \dots, A_n}(E_1) \cup \Pi_{A_1, \dots, A_n}(E_2)
        • ΠA1,…,An(E1∩E2)=ΠA1,…,An(E1)∩ΠA1,…,An(E2)\Pi_{A_1, \dots, A_n}(E_1 \cap E_2) = \Pi_{A_1, \dots, A_n}(E_1) \cap \Pi_{A_1, \dots, A_n}(E_2)
        • ΠA1,…,An(E1−E2)=ΠA1,…,An(E1)−ΠA1,…,An(E2)\Pi_{A_1, \dots, A_n}(E_1 - E_2) = \Pi_{A_1, \dots, A_n}(E_1) - \Pi_{A_1, \dots, A_n}(E_2)
        • ΠA1,…,An,B1,…,Bm(E1×E2)=ΠA1,…,An(E1)×ΠB1,…,Bm(E2)\Pi_{A_1, \dots, A_n, B_1, \dots, B_m}(E_1 \times E_2) = \Pi_{A_1, \dots, A_n}(E_1) \times \Pi_{B_1, \dots, B_m}(E_2)，其中 A1,…,AnA_1, \dots, A_n 是 E1E_1 的属性，B1,…,BmB_1, \dots, B_m 是 E2E_2 的属性。
      • 串接律
        • ΠA1,…,An(ΠB1,…,Bm(E))=ΠA1,…,An(E)\Pi_{A_1, \dots, A_n}(\Pi_{B_1, \dots, B_m}(E)) = \Pi_{A_1, \dots, A_n}(E)，其中 {A1,…,An}⊆{B1,…,Bm}\{A_1, \dots, A_n\} \subseteq \{B_1, \dots, B_m\}。
        • σF1(σF2(E))=σF1∧F2(E)\sigma_{F_1}(\sigma_{F_2}(E)) = \sigma_{F_1 \land F_2}(E)
    • 策略
      • 尽量早进行选择运算：减小中间关系的大小。
      • 投影和选择同时进行：避免重复扫描。
      • 投影和双目运算结合：减少关系的大小，进而减少重复扫描。
      • 尽量把笛卡尔积转换为连接。
      • 缓存公共子表达式。
    • 算法
      • 输入：查询的关系表达式树。
      • 优化步骤：
        • 拆分选择条件。
        • 将选择运算向叶结点移动。
        • 将投影运算向叶结点移动。
        • 把多个选择和投影的串接合并为一次选择和一次投影串接。
        • 对结点分组，一元运算和部分二元运算的结点的连通块组成一个组，一个组内操作一起完成。
          • 符合条件的二元运算包括并、交、差、等值连接、笛卡尔积结合等值选择。
          • 其他笛卡尔积的组不能包括其子结点。
      • 数据库的查询执行按照优化的表达式树，以组为单位进行计算。
  • 基于存取路径的优化
    • 选择
      • 如果是小关系：优先全表扫描。
      • 如果是大关系：
        • 如果选择条件是主键相等性：使用主键索引。
        • 如果选择条件是单个非主属性且有索引：
          • 如果估计结果比例较小：使用索引。
          • 否则使用全表扫描。
        • 如果选择条件是合取条件：
          • 如果有组合索引：使用组合索引
          • 如果部分属性有索引：用部分索引筛选再判断其他条件
          • 否则用全表扫描。
        • 如果选择条件是析取条件：使用全表扫描。
    • 连接
      • 如果两个表都按连接属性排序：用排序合并法。
      • 如果一个表的连接属性有索引：用索引连接法。
      • 如果其中一个表较小：用哈希连接法。
      • 否则使用嵌套循环法，并选择占用内存储存块更小的表为外表。
  • 基于代价估算的优化
关系查询处理数据库安全