思维导图

  • 关系查询处理和查询优化
    • 关系查询优化
      • 查询优化概述
        • 由DBMS进行查询优化的好处
        • 查询优化目标
        • 代价模型
      • 查询优化的一般准则
      • 关系代数等价变换规则
        • 连接、笛卡尔积交换律
        • 连接、笛卡尔积的结合律
        • 投影的串接定律
        • 选择的串接定律
        • 选择与投影的交换律
        • 选择与笛卡尔积的交换律
        • 选择与并的交换
        • 选择与差运算的交换
        • 投影与笛卡尔积的交换
        • 投影与并的交换
      • 关系代数表达式的优化算法
        • 详细流程
      • 优化的一般步骤
        • 把查询转换成某种内部表示
        • 代数优化
        • 物理优化
        • 生成查询计划

关系查询优化

查询优化概述

  • 查询优化的必要性
    • 查询优化极大地影响RDBMS的性能。
  • 查询优化的可能性
    • 关系数据语言的级别很高，使DBMS可以从关系表达式中分析查询语义。
    • 级别越高，越接近自然语言。

由DBMS进行查询优化的好处

用户不必考虑如何最好地表达查询以获得较好的效率，
系统可以比用户程序的优化做得更好。

  1. 优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息
  2. 如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。
  3. 优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。
  4. 优化器中包括了很多复杂的优化技术

查询优化目标

  • 查询优化的总目标
    • 选择有效策略，求得给定关系表达式的值
  • 实际系统的查询优化步骤
    1. 将查询转换成某种内部表示，通常是语法树
    2. 根据一定的等价变换规则把语法树转换成标准（优化）形式
    3. 选择低层的操作算法
      • 对于语法树中的每一个操作
        • 计算各种执行算法的执行代价
        • 选择代价小的执行算法
    4. 生成查询计划(查询执行方案)
      • 查询计划是由一系列内部操作组成的。

代价模型

  • 集中式数据库
    • 单用户系统
      • 总代价 = I/O代价 + CPU代价
    • 多用户系统
      • 总代价 = I/O代价 + CPU代价 + 内存代价
  • 分布式数据库
    • 总代价 = I/O代价 + CPU代价[+ 内存代价] + 通信代价

查询优化的一般准则

  • 选择运算应尽可能先做
    • 目的：减小中间关系
  • 在执行连接操作前对关系适当进行预处理
    • 按连接属性排序
    • 在连接属性上建立索引
  • 投影运算和选择运算同时做
    • 目的：避免重复扫描关系
  • 将投影运算与其前面或后面的双目运算结合
    • 目的：减少扫描关系的遍数
  • 某些选择运算＋在其前面执行的笛卡尔积
  • 提取公共子表达式

关系代数等价变换规则

  • 关系代数表达式等价
    • 指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的
    • 上面的优化策略大部分都涉及到代数表达式的变换

设E1、E2等是关系代数表达式，F是条件表达式

连接、笛卡尔积交换律

E1×E2≡E2×E1E_1 \times E_2 \equiv E_2 \times E_1
E1⋈E2≡E2⋈E1E_1 \bowtie E_2 \equiv E_2 \bowtie E_1
E1⋈FE2≡E2⋈FE1E_1 \mathop{\bowtie}\limits_{F} E_2 \equiv E_2 \mathop{\bowtie}\limits_{F} E_1

连接、笛卡尔积的结合律

(E1×E2)×E3≡E1×(E2×E3)(E_1 \times E_2) \times E_3\equiv E_1 \times (E_2 \times E_3)
(E1⋈E2)⋈E3≡E1⋈(E2⋈E3)(E_1 \bowtie E_2) \bowtie E_3\equiv E_1 \bowtie (E_2 \bowtie E_3)
(E1⋈FE2)⋈FE3≡E1⋈F(E2⋈FE3)(E_1 \mathop{\bowtie}\limits_{F} E_2) \mathop{\bowtie}\limits_{F} E_3\equiv E_1 \mathop{\bowtie}\limits_{F} (E_2 \mathop{\bowtie}\limits_{F} E_3)

投影的串接定律

ΠA1,A2,⋯ ,An(ΠB1,B2,⋯ ,Bn(E))≡ΠA1,A2,⋯ ,An(E)\mathop{\Pi}_{A_1,A_2,\cdots ,A_n}(\mathop{\Pi}_{B_1,B_2,\cdots,B_n}(E))\equiv\mathop{\Pi}_{A_1,A_2,\cdots,A_n}(E)

  • 假设：
  • E是关系代数表达式
  • Ai(i=1,2,…,n),Bj(j=1,2,…,m)A_i(i=1,2,…,n), B_j(j=1,2,…,m)是属性名
  • {A1,A2,⋯ ,An}\{A_1, A_2, \cdots, A_n\}构成{B1,B2,⋯ ,Bm}\{B_1,B_2,\cdots,B_m\}的子集

选择的串接定律

σF1(σF2(E))≡σF1∧F2(E)\sigma_{F_1}(\sigma_{F_2}(E))\equiv \sigma_{F_1\wedge F_2(E)}

  • 选择的串接律说明选择条件可以合并
  • 这样一次就可检查全部条件。

选择与投影的交换律

  • 假设: 选择条件F只涉及属性A1,A2,⋯ ,AnA_1,A_2,\cdots ,A_n
    σF(ΠA1,A2,⋯ ,An(E))≡ΠA1,A2,⋯ ,An(σF(E))\sigma_{F}(\mathop{\Pi}_{A_1,A_2,\cdots ,A_n}(E))\equiv \mathop{\Pi}_{A_1,A_2,\cdots ,A_n}(\sigma_{F}(E))
  • 假设: F中有不属于A1,A2,⋯ ,AnA_1,A_2,\cdots ,A_n的属性B1,B2,⋯ ,BmB_1,B_2,\cdots,B_m
    ΠA1,A2,⋯ ,An(σF(E))≡ΠA1,A2,⋯ ,An(σF(ΠA1,A2,⋯ ,An,B1,B2,⋯ ,Bm(E)))\mathop{\Pi}_{A_1,A_2,\cdots ,A_n}(\sigma_{F}(E)) \equiv \mathop{\Pi}_{A_1,A_2,\cdots ,A_n}(\sigma_{F}(\mathop{\Pi}_{A_1,A_2,\cdots ,A_n,B_1,B_2,\cdots,B_m}(E)))

选择与笛卡尔积的交换律

  • 假设：F中涉及的属性都是E1中的属性
    σF(E1×E2)≡σF(E1)×E2\sigma_F(E_1 \times E_2)\equiv \sigma_F(E_1)\times E_2
  • 假设：F=F1∧F2F=F_1 \wedge F_2，并且F1只涉及E1中的属性，F2只涉及E2中的属性，则由上面的等价变换规则1,4,6可推出：
    σF(E1×E2)≡σF1(E1)×σF2(E2)\sigma_F(E_1 \times E_2)\equiv \sigma_{F_1}(E_1)\times \sigma_{F_2}(E_2)
  • 假设： F=F1∧F2F=F_1 \wedge F_2， F1只涉及E1中的属性，F2涉及E1和E2两者的属性
    σF(E1×E2)≡σF2(σF1(E1)×E2)\sigma_F(E_1 \times E_2)\equiv \sigma_{F_2}(\sigma_{F_1}(E_1)\times E_2)
    • 它使部分选择在笛卡尔积前先做

选择与并的交换

  • 假设：E=E1∪E2E=E_1 \cup E_2，E1，E2有相同的属性名
    σF(E1∪E2)≡σF(E1)∪σF(E2)\sigma_F(E_1 \cup E_2) \equiv \sigma_F(E_1) \cup \sigma_F(E_2)

选择与差运算的交换

  • 假设：E1与E2有相同的属性名
    σF(E1−E2)≡σF(E1)−σF(E2)\sigma_F(E_1 - E_2) \equiv \sigma_F(E_1) - \sigma_F(E_2)

投影与笛卡尔积的交换

  • 假设：E1和E2是两个关系表达式，A1,A2,⋯ ,AnA_1,A_2,\cdots ,A_n是E1的属性，B1,B2,⋯ ,BmB_1,B_2,\cdots,B_m是E2的属性
    ΠA1,A2,⋯ ,An,B1,B2,⋯ ,Bm(E1×E2)≡ΠA1,A2,⋯ ,An(E1)×ΠB1,B2,⋯ ,Bm(E2)\mathop{\Pi}_{A_1,A_2,\cdots ,A_n,B_1,B_2,\cdots,B_m}(E_1 \times E_2)\equiv \mathop{\Pi}_{A_1,A_2,\cdots ,A_n}(E_1) \times \mathop{\Pi}_{B_1,B_2,\cdots,B_m}(E_2)

投影与并的交换

  • 假设：E1和E2 有相同的属性名
    ΠA1,A2,⋯ ,An(E1∪E2)≡ΠA1,A2,⋯ ,An(E1)∪ΠA1,A2,⋯ ,An(E2)\mathop{\Pi}_{A_1,A_2,\cdots ,A_n}(E_1 \cup E_2)\equiv \mathop{\Pi}_{A_1,A_2,\cdots ,A_n}(E_1) \cup \mathop{\Pi}_{A_1,A_2,\cdots ,A_n}(E_2)
序号 内容
1-2 连接、笛卡尔积的交换律、结合律
3 合并或分解投影运算
4 合并或分解选择运算
5-8 选择运算与其他运算交换
5,9,10 投影运算与其他运算交换

关系代数表达式的优化算法

  • 算法：关系表达式的优化
  • 输入：一个关系表达式的语法树。
  • 输出：计算该表达式的程序。

详细流程

  • 分解选择运算
  • 交换选择运算，将其尽可能移到叶端
    • 对每一个选择，利用规则4～8尽可能把它移到树的叶端。
  • 交换投影运算，将其尽可能移到叶端
    • 对每一个投影利用规则3，9，10，5中的一般形式尽可能把它移向树的叶端。
  • 合并串接的选择和投影，以便能同时执行或在一次扫描中完成
    • 利用规则3～5把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。
    • 使多个选择或投影能同时执行，或在一次扫描中全部完成
    • 尽管这种变换似乎违背“投影尽可能早做”的原则，但这样做效率更高。
  • 对内结点分组
    • 把上述得到的语法树的内节点分组。
    • 每一双目运算和它所有的直接祖先为一组(这些直接祖先是σ,Π\sigma,\Pi运算)。
    • 如果其后代直到叶子全是单目运算，则也将它们并入该组，但当双目运算是笛卡尔积(×)，而且其后的选择不能与它结合为等值连接时除外。把这些单目运算单独分为一组。
  • 生成程序
    • 生成一个程序，每组结点的计算是程序中的一步。
    • 各步的顺序是任意的，只要保证任何一组的计算不会在它的后代组之前计算。

优化的一般步骤

  1. 把查询转换成某种内部表示
  2. 代数优化：把语法树转换成标准（优化）形式
  3. 物理优化：选择低层的存取路径
  4. 生成查询计划，选择代价最小的

把查询转换成某种内部表示

例：求选修了课程C2的学生姓名

1
2
3
4
SELECT  Student.Sname
FROM    Student, SC
WHERE  Student.Sno=SC.Sno
AND     SC.Cno='2';


代数优化

利用优化算法把语法树转换成标准（优化）形式。

物理优化

  • 优化器查找数据字典获得当前数据库状态信息
    • 选择字段上是否有索引
    • 连接的两个表是否有序
    • 连接字段上是否有索引
  • 然后根据一定的优化规则选择存取路径
    • 如本例中若SC表上建有Cno的索引，则应该利用这个索引，而不必顺序扫描SC表。

生成查询计划

  • 在作连接运算时，若两个表(设为R1，R2)均无序，连接属性上也没有索引，则可以有下面几种查询计划：
    • 对两个表作排序预处理
    • 对R1在连接属性上建索引
    • 对R2在连接属性上建索引
    • 在R1，R2的连接属性上均建索引
  • 对不同的查询计划计算代价，选择代价最小的一个。
  • 在计算代价时主要考虑磁盘读写的I/O数，内存CPU处理时间在粗略计算时可不考虑。