关系查询处理和查询优化

关系数据库系统的查询处理

查询处理时关系数据库管理系统执行查询语句的过程，其任务是把用户提交给关系数据库管理系统的查询语句转换为高效的查询执行计划。

查询处理步骤

关系数据库管理系统查询处理阶段：查询分析、查询检查、查询优化和查询执行。

实现查询操作的算法示例

选择操作的实现 选择操作典型实现方法：

• 全表扫描方法 (Table Scan)

  • 对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出

  • 适合小表，不适合大表

• 索引扫描方法 (Index Scan)

  • 适合于选择条件中的属性上有索引(例如B+树索引或Hash索引)

  • 通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组

连接操作的实现

• 连接操作是查询处理中最耗时的操作之一

• 等值连接(或自然连接)最常用的实现算法

  • 嵌套循环算法(nested loop join)

  • 排序-合并算法(sort-merge join 或merge join)

  • 索引连接(index join)算法

  • Hash Join算法

关系数据库系统的查询优化

查询优化在关系数据库系统中有着非常重要的地位。关系数据库系统和非过程化的SQL之所以能够取得巨大成功，关键是得益于查询优化技术的发展。关系查询优化是影响关系数据库管理系统性能的关键因素。

查询优化概述

查询优化分类

• 代数优化

• 物理优化

查询优化的优点

• 用户不必考虑如何最好地表达查询以获得较好的效率

• 系统可以比用户程序的“优化”做得更好

  • 优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息。

  • 如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。

  • 优化器可以考虑数百种不同的执行计划，程序员一般只能考虑有限的几种可能性。

  • 优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。

关系数据库管理系统通过某种代价模型计算出各种查询执行策略的执行代价，然后选取代价最小的执行方案。

查询优化的总目标

• 选择有效的策略

• 求得给定关系表达式的值

• 使得查询代价最小(实际上是较小)

代数优化

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

代数优化策略：通过对关系代数表达式的等价变换来提高查询效率

关系代数表达式的等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的

常用的等价变换规则：

1. 连接、笛卡尔积交换律 设E1和E2是关系代数表达式，F是连接运算的条件，则有

• $E_1\times E_2\equiv E_2\times E_1$

• $E_1\bowtie E_2\equiv E_2\bowtie E_1$

• $E_1\underset F{\bowtie}E_2\equiv E_2\underset F{\bowtie}E_1$

1. 连接、笛卡尔积的结合律 设E1，E2，E3是关系代数表达式，F1和F2是连接运算的条件，则有

• $(E_1\times E_2)\times E_3\equiv E_1\times(E_2\times E_3)$

• $(E_1\bowtie E_2)\bowtie E_3\equiv E_1\bowtie (E_2\bowtie E_3)$

• $(E_1\underset {F_1}{\bowtie}E_2)\underset{F_2}{\bowtie}E_3\equiv E_1\underset {F_1}{\bowtie}(E_2\underset{F_2}{\bowtie}E_3)$

1. 投影的串接定律 ${\Pi}\_{A\_1,A\_2,...,A\_n}({\Pi}\_{B\_1,B\_2,...,B\_m}(E))\equiv{\Pi}\_{A\_1,A\_2,...,A\_n}(E)$ 这里，E是关系代数表达式，$A_i(i=1,2,...,n)$、$B_j(j=1,2,...,m)$是属性名，且$\lbrace A_1,A_2,...,A_n\rbrace$构成$\lbrace B_1,B_2,...,B_m\rbrace$的子集。

2. 选择的串接定律 ${\sigma}\_{F\_1}({\sigma}\_{F\_2}(E))\equiv{\sigma}\_{F\_1\wedge F\_2}(E)$ 这里，E是关系代数表达式，F1、F2是选择条件。

3. 选择与投影操作的交换律 ${\sigma}\_F({\Pi}\_{A\_1,A\_2,...,A\_n}(E))\equiv{\Pi}\_{A\_1,A\_2,...,A\_n}({\sigma}\_F(E))$ 这里，选择条件F只涉及属性A1,A2,...,An。

4. 选择与笛卡尔积的交换律

• 如果F中涉及的属性都是E1中的属性，则${\sigma}_F(E_1\times E_2)\equiv{\sigma}_F(E_1)\times E_2$

• 如果$F=F_1\wedge F_2$，并且F1只涉及E1中的属性，F2只涉及E2中的属性，则有上面的等价变换规则1、4、6可推出${\sigma}_F(E_1\times E_2)\equiv{\sigma}_{F_1}(E_1)\times{\sigma}_{F_2}(E_2)$

• 如果F1只涉及E1中的属性，F2涉及E1和E2两者的属性，则仍有${\sigma}_F(E_1\times E_2)\equiv{\sigma}_{F_2}({\sigma}_{F_1}(E_1)\times E_2)$

1. 选择与并的分配律 设$E=E_1\cup E_2$，E1、E2有相同的属性名，则 ${\sigma}\_F(E\_1\cup E\_2)\equiv {\sigma}\_F(E\_1)\cup {\sigma}\_F(E\_2)$

2. 选择与差运算的分配律 若E1与E2有相同的属性名，则 ${\sigma}\_F(E\_1-E\_2)\equiv{\sigma}\_F(E\_1)-{\sigma}\_F(E\_2)$

3. 选择对自然连接的分配律 ${\sigma}\_F(E\_1\bowtie E\_2)\equiv {\sigma}\_F(E\_1)\bowtie{\sigma}\_F(E\_2)$ F只涉及E1与E2的公共属性。

4. 投影与笛卡尔积的分配律 设E1和E2是两个关系表达式，$A_1,A_2,...,A_n$是E1的属性，$B_1,B_2,...,B_m$是E2的属性，则 ${\Pi}\_{A\_1,A\_2,...,A\_n,B\_1,B\_2,...,B\_m}(E\_1\times E\_2)\equiv{\Pi}\_{A\_1,A\_2,...,A\_n}(E\_1)\times{\Pi}\_{B\_1,B\_2,...,B\_m}(E\_2)$

5. 投影与并的分配律 设E1和E2有相同的属性名，则 ${\Pi}\_{A\_1,A\_2,...,A\_n}(E\_1\cup E\_2)\equiv{\Pi}\_{A\_1,A\_2,...,A\_n}(E\_1)\cup{\Pi}\_{A\_1,A\_2,...,A\_n}(E\_2)$

查询树的启发式优化

典型的启发式规则

• 选择运算应尽可能先做

• 把投影运算和选择运算同时进行

• 把投影同其前或其后的双目运算结合起来，没有必要为了去掉某些字段而扫描一遍关系。

• 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算，连接特别是等值连接运算要比同样关系上的笛卡尔积省很多时间。

• 找出公共子表达式

物理优化

物理优化就是要选择高效合理的操作算法或存取路径，求得优化的查询计划，达到查询优化的目标。

物理优化方法

• 基于规则的启发式优化

• 基于代价估算的优化

• 两者结合的优化方法

基于启发式规则的存取路径选择优化

选择操作的启发式规则

• 对于小关系，使用全表顺序扫描，即使选择列上有索引

• 对于大关系，启发式规则有：

  • 对于选择条件是“主码＝值”的查询

  • 查询结果最多是一个元组，可以选择主码索引

  • 一般的关系数据库管理系统会自动建立主码索引

  • 对于选择条件是“非主属性＝值”的查询，并且选择列上有索引

    • 要估算查询结果的元组数目

    • 如果比例较小(<10%)可以使用索引扫描方法

    • 否则还是使用全表顺序扫描

  • 对于选择条件是属性上的非等值查询或者范围查询，并且选择列上有索引

    • 要估算查询结果的元组数目 如果比例较小(<10%)可以使用索引扫描方法 否则还是使用全表顺序扫描

  • 对于用AND连接的合取选择条件

    • 如果有涉及这些属性的组合索引 优先采用组合索引扫描方法

    • 如果某些属性上有一般的索引，可以用索引扫描方法 通过分别查找满足每个条件的指针，求指针的交集 通过索引查找满足部分条件的元组，然后在扫描这些元组时判断是否满足剩余条件

    • 其他情况：使用全表顺序扫描

  • 对于用OR连接的析取选择条件，一般使用全表顺序扫描

连接操作的启发式规则

• 如果2个表都已经按照连接属性排序

  • 选用排序-合并算法

• 如果一个表在连接属性上有索引

  • 选用索引连接算法

• 如果上面2个规则都不适用，其中一个表较小

  • 选用Hash join算法

• 可以选用嵌套循环方法，并选择其中较小的表，确切地讲是占用的块数(b)较少的表，作为外表(外循环的表)

基于代价的优化

统计信息

• 基于代价的优化方法要计算查询的各种不同执行方案的执行代价，它与数据库的状态密切相关

• 优化器需要的统计信息

  • 对每个基本表

    • 该表的元组总数(N)

    • 元组长度(l)

    • 占用的块数(B)

    • 占用的溢出块数(BO)

  • 对基表的每个列

    • 该列不同值的个数(m)

    • 列最大值

    • 最小值

    • 列上是否已经建立了索引

    • 哪种索引(B+树索引、Hash索引、聚集索引)

    • 可以计算选择率(f)

  • 对索引

    • 索引的层数(L)

    • 不同索引值的个数

    • 索引的选择基数S(有S个元组具有某个索引值)

    • 索引的叶结点数(Y)

代价估算示例

• 全表扫描算法的代价估算公式

  • 如果基本表大小为B块，全表扫描算法的代价 cost＝B

  • 如果选择条件是“码＝值”，那么平均搜索代价 cost＝B/2

• 索引扫描算法的代价估算公式

  • 如果选择条件是“码＝值”

    • 则采用该表的主索引

    • 若为B+树，层数为L，需要存取B+树中从根结点到叶结点L块，再加上基本表中该元组所在的那一块，所以cost=L+1

  • 如果选择条件涉及非码属性

    • 若为B+树索引，选择条件是相等比较，S是索引的选择基数(有S个元组满足条件)

    • 满足条件的元组可能会保存在不同的块上，所以(最坏的情况)cost=L+S

  • 如果比较条件是＞，＞＝，＜，＜＝操作

    • 假设有一半的元组满足条件

    • 就要存取一半的叶结点

    • 通过索引访问一半的表存储块

    • cost=L+Y/2+B/2

    • 如果可以获得更准确的选择基数，可以进一步修正Y/2与B/2

• 嵌套循环连接算法的代价估算公式

  • 嵌套循环连接算法的代价 cost＝Br+BrBs/(K-1)

  • 如果需要把连接结果写回磁盘 cost＝Br+Br Bs/(K-1)+(FrsNrNs)/Mrs

    • 其中Frs为连接选择性(join selectivity)，表示连接结果元组数的比例

    • Mrs是存放连接结果的块因子，表示每块中可以存放的结果元组数目

• 排序-合并连接算法的代价估算公式

  • 如果连接表已经按照连接属性排好序，则 cost＝Br+Bs+(FrsNrNs)/Mrs

  • 如果必须对文件排序

    • 还需要在代价函数中加上排序的代价

    • 对于包含B个块的文件排序的代价大约是(2B)+(2B*${\log}_2 B$)

《数据库系统概论（第5版）》王珊 萨师煊 著