查询处理概述
关系数据库管理系统查询处理可以分为4个阶段：查询分析、查询检查、查询优化和查询执行。
1.查询分析 ：对用户提交的查询语句进行扫描、词法分析和语法分析，判断是否符合SQL语法规则，若没有语法错误，就会生成一棵语法树。
2.查询检查 ：对语法树进行查询检查，首先根据数据字典中的模式信息检查语句中的数据对象，如关系名、属性名是否存在和有效；还要根据数据字典中的用户权限和完整性约束信息对用户的存取权限进行检查。若通过检查，则将数据库对象的外部名称转换成内部表示。这个过程实际上是对语法树进行语义解析的过程，最后语法树被解析为一个具有特定语义的关系代数表达式，其表示形式仍然是一棵树，称为查询树。
3.查询优化 ：每个查询都会有多种可供选择的执行策略和操作算法，查询优化就是选择一个能高效执行的查询处理策略。一般将查询优化分为代数优化和物理优化。代数优化指对关系代数表达式进行等价变换，改变代数表达式中操作的次序和组合，使查询执行更高效；物理优化则是指存取路径和底层操作算法的选择，选择依据可以是基于规则、代价、语义的。查询优化之后，形成查询计划。
4.查询执行 ：查询计划由一系列操作符构成，每一个操作符实现计划中的一步。查询执行阶段，系统将按照查询计划逐步执行相应的操作序列，得到最终的查询结果。
选择运算
选择操作的典型实现方法有全表扫描法和索引扫描法。
1.全表扫描
对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出。
假设可以使用的内存为M块，全表扫描的算法思想如下：
1.按物理次序读表T的M块到内存；
2.检查内存的每个元组t，如果t满足选择条件，则输出t；
如果表T还有其他块未被处理，重复(1)和(2)。
这种方法适合小表，对规模大的表要进行顺序扫描，当选择率（即满足条件的元组数占全表比例）较低时，此算法效率很低。
2.索引扫描法
当选择条件中的属性上有索引（例如B+树索引或Hash索引）时，通过索引先找到满足条件的元组指针，再通过元组指针直接在要查询的表中找到元组。
［例1 ］ 等值查询：select * from t1 where col＝常量，并且col上有索引（B+树索引或Hash索引均可） ，则使用索引得到col为该常量元组的指针，通过元组指针在表t1中检索到结果。
［例2 ］ 范围查询： select * from t1 where col > 常量，并且col上有B+树索引，使用B+树索引找到col＝常量的索引项，以此为入口点在B+树的顺序集上得到col > 常量的所有元组指针， 通过这些元组指针到t1表中检索满足条件的元组。
［例 3 ］ 合取条件查询：select * from t1 where col1＝常量a AND col2 >常量b，如果 col1和 col1上有组合索引（col1,col2），则利用此组合索引进行查询筛选；否则，如果 col1和 col2上分别有索引，则：
方法一：分别利用各自索引查找到满足部分条件的一组元组指针，求这2组指针的交集，再到t1表中检索得到结果。
方法二：只利用索引查找到满足该部分条件的一组元组指针，通过这些元组指针到t1表中检索，对得到的元组检查另一些选择条件是否满足，把满足条件的元组作为结果输出。
一般情况下，当选择率较低时，基于索引的选择算法要优于全表扫描。但在某些情况下，如选择率较高、或者要查找的元组均匀分散在表中，这时索引扫描法的性能可能还不如全表扫描法，因为还需要考虑扫描索引带来的额外开销。
排序运算
排序是数据库中的一个基本功能，用户通过Order by子句即能达到将指定的结果集排序的目的，而且不仅仅是Order by子句，Group by、Distinct等子句都会隐含使用排序操作。
- 利用索引避免排序
为了优化查询语句的排序性能，最好的情况是避免排序，合理利用索引是一个不错的方法。因为一些索引本身也是有序的，如B+树，如果在需要排序的字段上面建立了合适的索引，那么就可以跳过排序过程，提高查询速度。
例如：假设t1表存在B+树索引key1(key_part1, key_part2)，则以下查询可以利用索引来避免排序：
SELECT * FROM t1 ORDER BY key_part1, key_part2;
SELECT * FROM t1 WHERE key_part1 = constant ORDER BY key_part2;
SELECT * FROM t1 WHERE key_part1 > constant ORDER BY key_part1;
SELECT * FROM t1 WHERE key_part1 = constant1 AND key_part2 > constant2 ORDER BY key_part2;
如果排序字段不在索引中，或者分别存在于多个索引中，或者排序键的字段顺序与组合索引中的字段顺序不一致，则无法利用索引来避免排序。
2. 对于不能利用索引来避免排序的查询，DBMS必须自己实现排序功能以满足用户需求。实现排序的算法可以是文件排序，也可以是内存排序，具体要由排序缓冲区（sort buffer）的大小和结果集的大小来确定。
数据库内部排序的实现主要涉及3种经典排序算法：快速排序、归并排序和堆排序。对于不能全部放在内存中的关系，需要引入外排序，最常用的就是外部归并排序。外部归并排序分为两个阶段：Phase1 – Sorting，对主存中的数据块进行排序，然后将排序后的数据块写回磁盘；Phase2 – Merging，将已排序的子文件合并成一个较大的文件。
标签：查询,查询处理,t1,索引,key,排序,元组 From： https://www.cnblogs.com/lygin/p/16735030.html