-
查询处理的过程
(1) 查询分析
检查语法错误
(2) 查询检查
语义检查、用户权限检查、完整性约束检查
(3) 建立查询的内部表示
生成语法树
(4) 查询优化
代数优化：关系代数表达式的等价变换
物理优化：结合索引、数据值的分布特征改善查询
代价估算：评估若干查询计划的效率
(5) 查询执行
分为 解释 和 编译两种
解释执行：对于每一条查询语句，DBMS都不保留可执行代码，每次都重新解释执行查询语句；
编译执行：运行前先编译，生成可执行代码
-
执行选择操作的算法 SELECT XXX FROM XX <条件>;
(1) 顺序扫描：按照元组的物理顺序逐个扫描
适用于元组少，被选中的元组比例高的情况
(2) 二分查找：如果物理文件有序，则用二分查找算法
(3) 索引（或散列）: 如果选择条件涉及的列上有索引，则通过索引查找满足条件的元组指针，然后通过该指针继续检索满足查询条件的元组
-
执行复合选择操作的算法： 由合取(AND), 析取(OR)连接而成的复合选择条件
(1) 合取AND
1° 组合索引
适用于合取的几个列恰好组成了组合索引
2° 单独索引
如果某一个属性上具有索引，则通过索引找到复合与该属性有关的查询条件的元组指针，通过元组指针得到符合该条件的元组，并对得到的元组检查其余的查询条件是否满足
3° 多个索引
如果合取条件涉及的属性都存在索引，那么可以分别检索满足单个条件的元组指针集再求交集；如果只有部分属性存在索引，那么求交集后还要进行验证是否满足其他条件
选择性：满足条件的记录数占记录总数的比例。最大为1，最小为0. 在DBMS数据字典中常常会记录选择性的估计值，这一值越小，越有必要有限使用这个条件来检索元组.
(2) 析取OR
只要任意一个条件没有索引，就只能用顺序扫描的方式
-
连接操作的算法
(1) 嵌套循环法
把一个关系作为外循环，另一个关系作为内循环。顺序扫描外循环中的每一条记录，对于每一条记录，检索内循环的每条元组是否满足连接条件。
一般地，使用记录较少的关系作为外循环。
(2) 索引嵌套循环法
嵌套循环法中，如果两个连接属性的一个属性存在索引或散列，则使用索引扫描代替顺序扫描
(3) 排序合并法
适用于自然连接和等值连接。如果两个关系按照连接属性，元组按照排序连续存放，那么可以同时对两个关系进行扫描，连接等值的元组。
排序合并法只需要分别对两个关系扫描一次。
(4) 散列连接法
思路：以连接属性作为散列键，先对两个关系的连接属性分别使用同一个散列函数划分为几个hash桶，再进行桶内部的匹配检测。
过程：
1° 划分阶段： 将记录数少的关系R的用于连接的属性值进行散列，将各个元组划分为不同的hash桶
2° 试探阶段： 将另一个关系S的用于连接的属性值进行散列，然后与已经在桶中的R的元组进行匹配。
散列连接法只需要分别对两个关系扫描一次。
散列连接法的前提是较小的表可以在划分阶段完全放入内存中。
-
投影操作的算法
(1) 如果要投影的列中包含了主键，则可以直接操作；
(2) 如果要投影的列中不包含主键，但是没有加DISTINCT，则也可以直接操作；
(3) 如果要投影的列中不包含主键，且加了DISTINCT，那么可以先对结果进行排序；或用散列法消除重复元组（检查每条记录是否与桶中的记录重复），消除重复元组
-
集合运算的算法
(1) 并、差、交
分别对两个关系按照主键属性进行排序，然后分别对两个关系进行一次扫描
(2) 笛卡尔积
嵌套循环法
chapter05_查询处理和查询优化_1_关系数据库系统的查询处理过程与算法
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 查询优化技术(1) 代数优化(2) 基于存储路径的优化(3) 基于代价估算的优化整体过程：将查询转换成语法树；根据...
