『数据库』数据库的查询可不是只知道 Select 就可以的-关系数据库系统的查询处理

数据库从入门到精通：戳我

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

一、关系数据库系统的查询处理
1.查询处理步骤
关系数据库管理系统查询处理阶段 ：
1）查询分析 ：对查询语句进行扫描、词法分 析和语法分析

• 词法分析：从查询语句中识别出正确的语言符号
• 语法分析：进行语法检查

2）查询检查

• 查询检查的任务
  合法权检查
  视图转换
  安全性检查
  完整性初步检查
• 根据数据字典中有关的模式定义检查语句中的数据库对象，如关系名、属性名是否存在和有效
• 如果是对视图的操作，则要用视图消解方法把对视图的操作转换成对基本表的操作
• 根据数据字典中的用户权限和完整性约束定义对 用户的存取权限进行检查
• 检查通过后把 SQL 查询语句转换成内部表示，即等价的==关系代数表达式==。
• 关系数据库管理系统一般都用查询树，也称为==语法分析树==来表示扩展的关系代数表达式。

3）查询优化：选择一个高效执行的查询处理策略
查询优化分类：

• 代数优化/逻辑优化：指关系代数表达式的优化
• 物理优化：指存取路径和底层操作算法的选择

查询优化的选择依据：

• 基于规则(rule based)
• 基于代价(cost based)
• 基于语义(semantic based)

4）查询执行：

• 依据优化器得到的执行策略生成查询执行计划
• 代码生成器(code generator)生成执行查询计划 的代码
• 两种执行方法：自顶向下；自底向上。

2.实现查询操作的算法示例
1）选择操作的实现
==全表扫描方法 (Table Scan)==

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

==索引扫描方法 (Index Scan)==

• 适合于选择条件中的属性上有索引(例如 B+树索引或 Hash 索引)。
• 通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组。

2）连接操作的实现
连接操作是查询处理中最耗时的操作之一。

[例]
SELECT *
FROM Student, SC
WHERE Student.Sno=SC.Sno;

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

• 对外层循环(Student 表)的每一个元组(s)，检索内层循 环(SC 表)中的每一个元组(sc)
• 检查这两个元组在连接属性(Sno)上是否相等
• 如果满足连接条件，则串接后作为结果输出，直到外 层循环表中的元组处理完为止。

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

• 如果连接的表没有排好序，先对 Student 表和 SC 表按 连接属性 Sno 排序
• 取 Student 表中第一个 Sno，依次扫描 SC 表中具有相 同 Sno 的元组
• 当扫描到 Sno 不相同的第一个 SC 元组时，返回 Student 表扫描它的下一个元组，再扫描 SC 表中具有 相同 Sno 的元组，把它们连接起来
• 重复上述步骤直到 Student 表扫描完

注意：

• Student 表和 SC 表都只要扫描一遍
• 如果两个表原来无序，执行时间要加上对两个表的排序时间
• 对于大表，先排序后使用排序-合并连接算法执行连接，总的时间一般仍会减少

==索引连接(index join)算法==

• 在 SC 表上已经建立属性 Sno 的索引。
• 对 Student 中每一个元组，由 Sno 值通过 SC 的索引查 找相应的 SC 元组。
• 把这些 SC 元组和 Student 元组连接起来 循环执行前两步，直到 Student 表中的元组处理完为止

==Hash Join 算法==
前提：假设两个表中较小的表 在第一阶段后可以完全放入内存的 hash 桶中。

• 把连接属性作为 hash 码，用同一个 hash 函数把 Student 表和 SC 表 中的元组散列到 hash 表中。
• 划分阶段(building phase, 也称为 partitioning phase)
  对包含较少元组的表(如 Student 表)进行一遍处理
  把它的元组按 hash 函数分散到 hash 表的桶中
• 试探阶段(probing phase,也称为连接阶段 join phase)
  对另一个表(SC 表)进行一遍处理
  把 SC 表的元组也按同一个 hash 函数（hash 码是连接属性）进 行散列
  把 SC 元组与桶中来自 Student 表并与之相匹配的元组连接起来

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

• 查询优化在关系数据库系统中有着非常重要的地位
• 关系查询优化是影响关系数据库管理系统性能的关键因素
• 由于关系表达式的语义级别很高，使关系系统可以从关系表达式中分析查询语义，提供了执行查询优化的可能性

一、概述

• 1.关系系统的查询优化
  是关系数据库管理系统实现的关键技术又是关系系统的优点所在。
  减轻了用户选择存取路径的负担。
• 2.非关系系统
  用户使用过程化的语言表达查询要求，执行何种记录级的操作，以及操作的序列是由用户来决定的。
  用户必须了解存取路径，系统要提供用户选择存取路径的手段，查询效率由用户的存取策略决定。
  如果用户做了不当的选择，系统是无法对此加以改进的。

3.查询优化的优点

• 用户不必考虑如何最好地表达查询以获得较好的效率
• 系统可以比用户程序的“优化”做得更好
  (1)优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息。
  (2)如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。
  (3)优化器可以考虑数百种不同的执行计划，程序员一 般只能考虑有限的几种可能性。
  (4)优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术

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

• 集中式数据库
  执行开销主要包括：磁盘存取块数(I/O 代价)；处理机时间(CPU 代价)；查询的内存开销
  I/O 代价是最主要的
• 分布式数据库
  总代价=I/O 代价+CPU 代价+内存代价＋通信代价

5.查询优化的总目标

• 选择有效的策略
• 求得给定关系表达式的值
• 使得查询代价最小(实际上是较小)

代数优化

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

• 代数优化策略：通过对关系代数表达式的等价变换来提高查询效率。
• 关系代数表达式的等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的。
• 两个关系表达式 E1 和 E2 是等价的，可记为 E1≡E。

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

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

3.投影的串接定律

• E 是关系代数表达式
• Ai(i=1，2，…，n)，Bj(j=1，2，…，m)是属性名
• {A1，A2，…，An}构成{B1，B2，…，Bm}的子集

4.选择的串接定律

• E 是关系代数表达式，F1、F2 是选择条件
• 选择的串接律说明选择条件可以合并,这样一次就可检查全部条件

5.选择与投影操作的交换律

• 选择条件 F 只涉及属性 A1，…，An。
• 若 F 中有不属于 A1，…，An 的属性 B1，…，Bm 有更一般规则：
  
  6. 选择与笛卡尔积的交换律
• 如果 F 中涉及的属性都是 E1 中的属性，则
  
• 如果 F=F1∧F2，并且 F1 只涉及 E1 中的属性，F2 只涉及 E2 中的属性，则由上面的等价变换规则 1，4，6 可推出：
  
• 若 F1 只涉及 E1 中的属性，F2 涉及 E1 和 E2 两者的属性，则仍有
  
  它使部分选择在笛卡尔积前先做。

7. 选择与并的分配律
设 E=E1∪E2，E1，E2 有相同的属性名，则

8. 选择与差运算的分配律
若 E1 与 E2 有相同的属性名，则

9. 选择对自然连接的分配律

F 只涉及 E1 与 E2 的公共属性

10. 投影与笛卡尔积的分配律
设 E1 和 E2 是两个关系表达式，A1，…，An 是 E1 的属性，B1，…，Bm 是 E2 的属性，则

11. 投影与并的分配律
设 E1 和 E2 有相同的属性名，则

二、查询树的启发式优化
典型的启发式规则
（1）选择运算应尽可能先做
在优化策略中这是最重要、最基本的一条。
（2）把投影运算和选择运算同时进行
如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系。
（3） 把投影同其前或其后的双目运算结合起来，没有必要为了去掉某些字段而扫描一遍关系。
（4） 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算，连接特别是等值连接运算要比同样关系上的笛卡尔积省很多时间。
（5） 找出公共子表达式

• 如果这种重复出现的子表达式的结果不是很大的关系
• 并且从外存中读入这个关系比计算该子表达式的时间少得多
• 则先计算一次公共子表达式并把结果写入中间文件是合算的。
• 当查询的是视图时，定义视图的表达式就是公共子表达式的情况

物理优化

• 代数优化改变查询语句中操作的次序和组合，不涉及底层的存取路径
• 对于一个查询语句有许多存取方案，它们的执行效率不同， 仅仅进行代数优化是不够的
• 物理优化就是要==选择高效合理的操作算法或存取路径==，求得优化的查询计划

物理优化方法

• 基于规则的启发式优化
  启发式规则是指那些在大多数情况下都适用，但不是在每种情况下都是适用的规则。
• 基于代价估算的优化
  优化器估算不同执行策略的代价，并选出具有最小代价的执行计划。
• 两者结合的优化方法
  常常先使用启发式规则，选取若干较优的候选方案，减少代价估算的工作量
  然后分别计算这些候选方案的执行代价，较快地选出最终的优化方案

一、基于启发式规则的存取路径选择优化
1.选择操作的启发式规则
对于小关系，使用全表顺序扫描，即使选择列上有索引
对于大关系，启发式规则有：
（1）对于选择条件是“==主码＝值==”的查询

• 查询结果最多是一个元组，可以选择主码索引
• 一般的关系数据库管理系统会自动建立主码索引

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

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

（3）对于选择条件是属性上的非等值查询或者范围查询，并且选择列上有索引
要估算查询结果的元组数目：

• 如果比例较小(<10%)可以使用索引扫描方法
• 否则还是使用全表顺序扫描

（4）对于用 AND 连接的合取选择条件

• 如果有涉及这些属性的组合索引
  优先采用组合索引扫描方法
• 如果某些属性上有一般的索引，可以用索引扫描方法
  通过分别查找满足每个条件的指针，求指针的交集
  通过索引查找满足部分条件的元组，然后在扫描这些元组时判断是否满足剩余条件
• 其他情况：使用全表顺序扫描

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

2.连接操作的启发式规则
（1）如果 2 个表都已经按照连接属性排序

• 选用排序-合并算法

（2）如果一个表在连接属性上有索引

• 选用索引连接算法

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

• 选用 Hash join 算法

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

• 设连接表 R 与 S 分别占用的块数为 Br 与 Bs
• 连接操作使用的内存缓冲区块数为 K
• 分配 K-1 块给外表
• 如果 R 为外表，则嵌套循环法存取的块数为 Br+BrBs/(K-1)
• 显然应该选块数小的表作为外表

二、基于代价的优化

• 启发式规则优化是定性的选择，适合解释执行的系统
  解释执行的系统，优化开销包含在查询总开销之中
• 编译执行的系统中查询优化和查询执行是分开的
  可以采用精细复杂一些的基于代价的优化方法

1.统计信息

基于代价的优化方法要计算查询的各种不同执行方案的执行代价，它与数据库的状态密切相关
优化器需要的统计信息
（1）对每个基本表

• 该表的元组总数(N)
• 元组长度(l)
• 占用的块数(B)
• 占用的溢出块数(BO)

（2）对基表的每个列

• 该列不同值的个数(m)
• 列最大值
• 最小值
• 列上是否已经建立了索引
• 哪种索引(B+树索引、Hash 索引、聚集索引)
• 可以计算选择率(f)
  如果不同值的分布是均匀的，f ＝ 1/m。
  如果不同值的分布不均匀，则要计算每个值的选择率，f ＝具有该值的元组数/N。

（3）对索引

• 索引的层数(L)
• 不同索引值的个数
• 索引的选择基数 S(有 S 个元组具有某个索引值)
• 索引的叶结点数(Y)

2.代价估算示例
（1）全表扫描算法的代价估算公式

• 如果基本表大小为 B 块，全表扫描算法的代价 cost ＝ B
• 如果选择条件是“码＝值”，那么平均搜索代价 cost ＝ B/2

（2）索引扫描算法的代价估算公式

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

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

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

• 若为 B+树索引，选择条件是相等比较，S 是索引的选择基数(有 S 个元组满足条件)
• 满足条件的元组可能会保存在不同的块上，所以(最坏的情况)cost=L+S

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

• 假设有一半的元组满足条件
• 就要存取一半的叶结点
• 通过索引访问一半的表存储块
• cost=L+Y/2+B/2
• 如果可以获得更准确的选择基数，可以进一步修正 Y/2 与 B/2

（3）嵌套循环连接算法的代价估算公式

嵌套循环连接算法的代价
cost＝Br+BrBs/(K-1)
如果需要把连接结果写回磁盘
cost＝Br+Br Bs/(K-1)+(Frs*Nr*Ns)/Mrs

• 其中 Frs 为连接选择性(join selectivity)，表示连接结果元组数的比例
• Mrs 是存放连接结果的块因子，表示每块中可以存放的结果元组数目

（4）排序-合并连接算法的代价估算公式

• 如果连接表已经按照连接属性排好序，则
  cost＝Br+Bs+(Frs*Nr*Ns)/Mrs
• 如果必须对文件排序
  还需要在代价函数中加上排序的代价
  对于包含 B 个块的文件排序的代价大约是
  (2*B)+(2*B*log2B)

==查询处理是关系数据库管理系统的核心，查询优化技术是查询处理的关键技术 ==