数据库_数据库是怎样炼成的：查询处理优化篇

本文主要介绍关系型数据库的查询处理和查询优化技术，查询优化主要分为代数优化和物理优化，代数优化指关系代数表达式的优化，物理优化指存取路径和底层操作算法的优化

01

—

    查询处理的任务是把用户提交给RDBMS的查询语句转化为高效的执行计划，查询处理可以分为四个阶段：查询分析、查询检查、查询优化和查询执行。

1、查询分析

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

2、查询检查

    对合法的查询语句进行语义检查，检查语句中的数据库对象、属性、关系是否存在和有效，还要根据数据字典中的用户权限和完整性约束定义的用户的存取权限进行检查，检查过后便把SQL转换为等价的关系代数表达式，一般使用查询树（语法分析树），来表示扩展的关系代数表达式。（这部分主要是安全性检查和完整性检查）

3、查询优化

    每个查询都会有许多可供选择的执行策略和操作算法，查询优化就是选择一个高效的处理策略，按照操作的层次一般可以分为代数优化和物理优化，代数优化指按照一定的规则改变代数表达式中的操作次序和组合（关系表达式等价变换规则）；物理优化则是存取路径和底层操作算法的选择。其依据可以是基于规则、代价、语义等。

4、 查询执行

    依据优化器得到的执行策略生成执行计划，由代码生成器生成执行这个查询计划的代码。   

查询操作的算法实例

    本节简单举例几种选择和连接操作的实现算法思想，每一种都有多种具体实现。

一、选择操作的实现

1、简单的全表扫描

    对查询的基本表顺序扫描，逐一检查每个元组是否满足。

2、索引扫描方法

    如果选择的属性上有索引（b树或hash），可以用索引扫描，用过先找到满足条件的元组主码，直接在查询的基本表中找到元组。

    如果是大于小于的范围操作，先找到阈值处的索引，以此为入口点在B+树的顺序集上找到所有元组指针，之后在回表。

    如果是多个条件，一是先找到这些条件的元组交集，然后回表，二是先找到一个条件的元组，回表，再继续在得到的元组中判断下一组条件。

二、连接操作的实现（只说了自然连接）

1、嵌套循环方法

    对外层循环的每一个元组，检索内存循环的每一个元组，并检查两个元组在连接属性上是否相等，直到外层的处理完。

2、排序-合并方法

    先对两个表的连接属性进行排序，然后循环外层循环表做处理，两个表都只要扫描一遍。

3、索引连接 Index Join 方法

    首先在内层循环表的连接属性上建立索引，然后循环外层表通过索引找到对应的内层表并连接起来，循环处理直到外层的元组处理完成

4、Hash Join方法

    把连接属性作为Hash码，用同一个Hash函数将两个元组集散列到同一个文件中。第一步划分阶段，对包含较少元组的表分散到Hash表的桶中。第二步试探阶段，把另一个表处理一遍，把桶中另一张表的元组连过来。

03

—

04

—