数据库理论之查询处理和查询优化

关系数据库的查询处理和查询优化

查询处理

查询处理是 是 RDBMS 执行查询语句的过程,其任务是把用户提交给 RDBMS 的查询语句转换为高效的查询执行计划。

查询处理步骤

查询处理分为4个阶段:查询分析、查询检查、查询优化和查询执行。

  1. 查询分析(语法)
    对查询语句进行扫描、词法分析、语法分析
  2. 查询检查(语义)
    对合法的查询语句进行语义检查,即根据数据字典中有关的模式定义检查语句中的数据库对象,如关系名、属性名等是否存在和有效。 然后进行安全性、完整性检查。检查通过后把SQL语句转换成等价的关系代数表达式。RDBMS 一般采用查询树(语法树)来表示拓展的关系代数表达式。
  3. 查询优化
    查询优化就是选择一个高效执行的查询处理策略。
    分为代数优化物理优化
    1. 代数优化是指关系代数表达式的优化,即按照一定的规则,通过对关系代数表达式进行等价变换,改变代数表达式中操作的次序和组合,使查询执行更高效。
    2. 物理优化是指通过存取路径和底层操作算法的选择进行的优化。
      选择的依据可以是基于规则的、基于代价的、基于语义的。
  4. 查询执行
    依据优化器得到的执行策略生成查询执行计划,由代码生成器生成执行这个查询计划的代码,然后 加以执行,回送查询结果。

查询操作算法

(1) 全表扫描方法 (Table Scan)
对查询的基本表顺序扫描,逐一检查每个元组是否满足选择条件,把满足条件的元组作为结果输出
适合小表,不适合大表

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

当选择率较低时,基于索引的选择算法要优于全表扫描算法 。但在某些情况下,例如选择率较高,或者要查找的元组均匀地分布在查找的表中,这时基于索引的选择算法性能不如全表扫描算法。因此除了对表的扫描操作,还要加上对B+树索引的扫描操作,对每一个检索码,从 B+树根节点到叶子结点路径上的每个结点都要进行一次 IO 操作。

Hash树和B+树也有优劣,等下次写有关索引的时候再讲。

连接操作算法

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

本节只讨论等值连接(或自然连接)最常用的实现算法,例:

SELECT * FROM Student, SC WHERE Student.Sno=SC.Sno;

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

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

可见就是O(N2)的时间复杂度,十分耗时。

(2) 排序——合并算法(sort-merge join 或 merge join)
+ 如果连接的表没有排好序,先对 Student 表和 SC 表按连接属性 Sno 排序
+ 取 Student 表中第一个 Sno ,依次扫描 SC 表中具有相同 Sno 的元组
+ 当扫描到 Sno 不相同的第一个 SC 元组时 ,返回 Student 表扫描它的下一个元组,再扫描 SC 表中具有相同 Sno 的元组,把它们连接起来
+ 重复上述步骤直到 Student 表扫描完

这种算法具有动态规划的思想,Student表和SC表都只要扫描一遍,而且如果连接的属性有注册索引,并且索引是有序的,可以省去排序的时间。

对于大表,先排序后使用排序-合并连接算法执行连接,总的时间一般仍会减少。

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

步骤:

(前提)在 SC 表上已经建立属性 Sno 的索引。
1. 对 Student 中每一个元组,由 Sno 值通过 SC 的索引查找相应的 SC 元组。
2. 把这些 SC 元组和 Student 元组连接起来

循环执行1、2,直到Student表中的元组处理完为止  

只有一个表需要索引

(4) Hash Join 算法

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

将小表转为哈希表,用表1 的 匹配字段用哈希函数映射到哈希表

上面 hash join 算法前提:假设两个表中较小的表在第一阶段后可以完全放入内存的 hash 桶中。

查询优化

查询优化在关系数据库系统中有着非常重要的地位

关系查询优化是影响关系数据库管理系统性能的关键因素

由于关系表达式的语义级别很高,使关系系统可以从关系表达式中分析查询语义,提供了执行查询优化的可能性

概述

关系系统的查询优化

是关系数据库管理系统实现的关键技术又是关系系统的优点所在
减轻了用户选择存取路径的负担

非关系系统

用户使用过程化的语言表达查询要求,执行何种记录级的操作,以及操作的序列是由用户来决定的
用户必须了解存取路径,系统要提供用户选择存取路径的手段,查询效率由用户的存取策略决定
如果用户做了不当的选择,系统是无法对此加以改进的

查询优化的优点

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

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

数据库理论之查询处理和查询优化

查询优化的总目标

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

一个实例

一个关系查询可以对应不同的执行方案,其效率可能相差非常大。

例:求选修了2号课程的学生姓名。

SELECT Student.Sname FROM Student, SC
    WHERE Student.Sno=SC.Sno AND SC.Cno='2'

假定学生-课程数据库中有 1000 个学生记录,10000 个选课记录
选修 2 号课程的选课记录为 50 个

数据库理论之查询处理和查询优化

第一种情况:

  1. 计算笛卡尔积

    算法:

    1. 在内存中尽可能多地装入某个表(如 Student 表) 的若干块 ,留出一块存放另一个表(如 SC 表) 的元组。
    2. 把 SC 中的每个元组和 Student 中每个元组连接 , 连接后的元组装满一块后就写到中间文件上
    3. 从 SC 中读入一块和内存中的 Student 元组连接,直到 SC 表处理完。
    4. 再读入若干块 Student 元组,读入一块 SC 元组
    5. 重复上述处理过程,直到把 Student 表处理完

数据库理论之查询处理和查询优化
  1. 作选择操作

    依次读入连接后的元组,按照选择条件选取满足要求的记录
    假定内存处理时间忽略。读取中间文件花费的时间 (同写中间文件一样) 需读入106块。
    若满足条件的元组假设仅 50 个,均可放在内存。

  2. 作投影操作
    把第 2 步的结果在 Sname 上作投影输出,得到最终结果
    第一种情况下执行查询的总读写数据块 2100+106+106

第二种情况:

  1. 计算自然连接
    1. 执行自然连接,读取 Student 和 和 SC 表的策略不变,总的读取块数仍为 2100 块
    2. 自然连接的结果比第一种情况大大减少,为 104 个元组
    3. 写出数据块= 103 块
  2. 读取中间文件块,执行选择运算,读取的数据块= 103 块
  3. 把第 2 步结果投影输出。
    第二种情况下执行查询的总读写数据块=2100+103+103
    其执行代价大约是第一种情况的 488 分之一

第三种情况:

  1. 先对 SC 表作选择运算 ,只需读一遍 SC 表,存取100 块,因为满足条件的元组仅50个,不必使用中间文件。
  2. 读取 Student 表,把读入的 Student 元组和内存中的 SC 元组作连接。也只需读一遍Student 表共 100 块。
  3. 把连接结果投影输出
    第三种情况总的读写数据块=100+100
    其执行代价大约是第一种情况的万分之一,是第二种情况的 20 分之一

注:
假如 SC 表的 Cno 字段上有索引
+ 第一步就不必读取所有的 SC 元组而只需读取 Cno=‘2’ 的那些元组(50 个)
+ 存取的索引块和 SC 中满足条件的数据块大约总共 3 ~4 块

若 Student 表在 Sno 上也有索引
+ 不必读取所有的 Student 元组
+ 因为满足条件的 SC 记录仅 50 个,涉及最多 50 个 个 Student 记录
+ 读取 Student 表的块数也可大大减少

总结

有选择和连接操作时,先做选择操作,这样参加连接的元组就可以大大减少,这是代数优化。

在 Q3 中 SC 表的选择操作算法有全表扫描或索引扫描,经过初步估算,索引扫描方法较优。

对于 Student 和 SC 表的连接,利用 Student 表上的索引,采用索引连接代价也较小,这就是物理优化。

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e6%95%b0%e6%8d%ae%e5%ba%93%e7%90%86%e8%ae%ba%e4%b9%8b%e6%9f%a5%e8%af%a2%e5%a4%84%e7%90%86%e5%92%8c%e6%9f%a5%e8%af%a2%e4%bc%98%e5%8c%96/