查询处理和优化

技术探索
🗨️字数统计=2.1k字 ⏳阅读时长≈7分钟

一、查询处理

查询处理是数据库管理系统把用户提交上来的查询语句转换成高效的查询执行计划。

关系数据库管理系统查询处理可以分为4个阶段：

  • 查询分析
  • 查询检查
  • 查询优化
  • 查询执行

1. 查询分析

首先对查询语句进行扫描、语法分析和词法分析。从查询语句中识别出语言符号，如SQL关键字、属性名和关系名等，进行语法检查和语法分析，判断查询语句是否符合SQL语法规则

2. 查询检查

对合法的查询语句进行语义检查，即检查数据库对象，如关系名、属性名是否存在和有效。

还要根据用户权限和完整性约束定义对用户的存取权限进行检查。如果用户没有相应权限或者违反了完整性约束，就拒绝执行该查询。

检查过后将SQL查询语句转成内部表示即等价的关系代数表达式，一般用 查询树 / 语法分析树 来表示扩展的关系代数表达式

3. 查询优化

查询优化就是优化器选择一个高效执行的查询处理策略，以获得最好的查询优化效果

按照优化的层次分为代数优化和物理优化

4. 查询执行

根据优化器得到的执行策略生成查询执行计划，由代码生成器生成执行这个查询计划的代码，然后加以执行，并返回查询结果


二、实现查询操作的算法

1. 选择操作的实现

① 全表扫描算法 table scan

适用于规模较小的表。

对于大规模的表，当选择率较低时，这个算法的效率很低

② 索引扫描算法 index scan

如果选择条件中的属性上有索引，可以用索引扫描算法，通过索引先找到满足条件的元组指针，再通过元组指针在查询的基本表中找到元组

2. 连接操作的实现 / 多表连接

以下面这条 SQL 语句为例：

1
select * from Student,SC where Student.Sno = SC.Sno;

① 嵌套循环算法 nested loop

最简单可行的算法。

  • 取 Student 表的一个元组，与 SC 表的所有元组进行比较，凡满足连接条件的元组就进行连接并且作为结果输出。
  • 然后再取 Student 表的下一个元组，与 S 的所有元组比较，直至 Student 表的所有元组与 SC 表的所有元组比较完毕为止。

② 排序-归并算法 sort-merge

等值连接常用的算法，如果 Student 表和 SC 表已经按连接属性排好序了，则可按序比较两个表的连接属性，找出匹配的所有元组。

核心思想：分别从两个表中取出一行元组进行比较，如果匹配就连接起来放入结果集；如果不匹配，将较小的那个元组丢弃，继续匹配这个表的下一行，依次处理直到将两表的数据取完。

如果 Student 表 和 SC 表在做连接操作之前没有按连接属性进行排序，则我们需要事先为之排序，由于排序是开销很大的操作，在此情况下是否值得使用排序归并法，那就需要权衡了。

③ 索引连接算法 index join

  • 在 SC 表上已经建立了 Sno 的索引
  • 对 Student 中的每一个元组，在 SC 表中通过 Sno 的索引查找对应的 SC 元组，把相匹配的两个表中的元组连接起来。循环执行，直到 Student 表扫描结束

④ 散列连接算法 hash join

🚨 Oracle 支持 hash join，MySQL 不支持

用来处理等值连接。把连接属性作为 hash 的 value，用同一个 hash 函数把 Student 表和 SC 表中的元组散列到 hash 表中。

  • 创建阶段：创建 hash 表。对包含较少元组的表进行处理，把他的元组按 hash 函数分散到 hahs 桶中（采用拉链法）
  • 连接阶段：对另一个表进行 hash。并把这个表中元组和上一个表中相匹配的元组（同义词）连接起来。如果一个桶中只有 Student 或者 SC 的元组，则不进行连接。

三、查询优化

每个查询都会有许多可供选择的执行策略和操作算法，查询优化就是选择一个高效执行的查询处理策略。

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

1. 代数优化

代数优化就是通过对关系代数式的等价变换来提高查询效率

代数优化改变的是查询语句中操作的次序和组合，但不涉及底层的存取路径


最常用的优化原则是尽量缩减查询过程中的中间结果。由于选择、投影等一元操作分别从水平或垂直方向减少关系的大小，而连接、并等二元操作不但操作本身的开销较大，而且很可能产生大的中间结果。因此，再做查询优化时，总是让选择和投影先做，再做连接等二元操作。在连接时，也是先做小关系之间的连接，再做大关系之间的连接。


常见的对关系表达式进行查询优化的方法有：

  • 选择运算尽可能先做
  • 若投影运算和选择运算都是对同一个关系进行操作，则将投影运算和选择运算同时进行
  • 把投影同其前或后的双目运算符结合起来
  • 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个来连接运算（连接，特别是等值连接，要比同样关系上的笛卡尔积省很多时间）
  • 找出公共子表达式（比如查询视图的时候，定义视图的表达式就是公共子表达式）

2. 物理优化

物理优化就是选择高效合理的操作算法或者存取路径来达到查询优化的目标

选择的方法如下：

  • 基于规则的启发式优化
  • 基于代价估算的优化：选择代价最小的执行计划
  • 两者结合的优化方法

① 基于规则的启发式优化

🚩 启发式优化：指的是在大部分情况下使用，但不是在所有情况下都是最好的规则

1）对于选择操作的启发式规则：

  • 对于小关系，使用全表顺序扫描，即使选择列上有索引
  • 对于大关系，启发式规则有：
    • 选择条件是 主键 = 值，采用主键索引
    • 选择条件是 非主属性 = 值，并且选择列上有索引，估算查询结果的元组数目，如果比例较小，可以使用索引，否则仍然使用全表顺序扫描
    • 选择条件是 非等值查询或范围查询，并且选择列上有索引，估算查询结果的元组数目，如果比例较小，可以使用索引，否则仍然使用全表顺序扫描
    • 使用 AND 连接的合取选择条件，如果有涉及这些属性的组合索引，则优先使用索引，否则使用全表顺序扫描
    • 对于 OR 连接的析取选择条件，一般使用全表顺序扫描

2）对于连接操作的启发式规则：

  • 如果两个表都已经按照连接属性排序，则使用排序-合并算法
  • 如果一个表在连接属性上有索引，则使用索引连接算法
  • 如果上面两个规则不适用，且其中一个表较小，则使用 hash join 算法
  • 最后可以使用嵌套循环算法

② 基于代价估算的优化

基于代价的优化方法要计算各种操作算法的执行代价，它与数据库的状态密切相关。为此在数据字典中存储了优化器需要的统计信息，主要包括以下几个方面：

分享到