数据库-实现篇 第十五讲
查询实现算法概述——关系代数操作
-
数据库查询基本思想:
数据库的核心操作
(1)基本动作:
并、差、积、选择、投影
(2)基于关系代数提出的SQL语句,转化为关系代数的组合操作
(3)程序执行机构进行解释、拆解 -
查询实现和查询优化:
(1)将SQL语句转化为关系代数表达式
转化后,若先执行连接操作,则会造成爆炸,故DBMS不能按照该顺序进行执行
尽量把选择、投影操作移到乘积的前面去执行
(2)改变操作次序
(3)为每一个操作选择一个优化的程序进行执行——物理查询优化
(4)执行
- 物理查询优化:实现关系代数操作的成熟的组合,求代价最少
- 数据库三大类操作:
(1)一次单一元组的一元操作:选择、投影
——迭代器算法
(2)整个关系的一元操作:DISTINCT、GROUP BY、SORTING
(3)整个关系的二元操作:并、交、差、连接、积
——一趟扫描、两趟扫描、多趟扫描:内存使用情况
基于排序、散列、索引的算法
连接操作的实现算法
迭代器
对于一次单一元组操作
物化策略扫描三遍数据库,流水线策略扫描一遍数据库
-
迭代器:迭代地读取一个集合中的每一个元素,而封装其读取细节
-
并运算迭代器构造
-
选择运算迭代器:
-
投影运算迭代器:
-
R和S的连接迭代器:
趟扫描算法——去重复操作
-
关系 / 数据表的读取
(1)聚簇关系——关系的元组集中存放
TableScan(R) —— 表空间扫描算法,扫描结果未排序
B(R):R的存储块数目
SortTableScan(R) —— 排序扫描算法
IndexScan(R)
SortIndecScan(R)
(2)非聚簇关系
T(R):R的元组数目 -
去重复操作 DISTINCT
(1)在内存中保存已处理过的元组,当新元组到达时与之前的元组做比较
重点:设计内存部分的数据结构,便于元组比较时的快速查找
(2)算法复杂性:B(R)
(3)应用条件:B(R)<=M -
分组聚集计算
(1)分组聚集:在内存当中保留所有的分组,保存每个分组上的聚集信息
(2)算法复杂性:B(R)
(3)应用条件:B(R)<=M
(4)实例:基于散列的一趟扫描算法:
分组的桶若有溢出桶,则降低了查询速率。
(5)集合操作需要去重复,包操作需要计数统计每一个元组出现的次数
(6)连接操作优化 R和S连接
在S读入时直接按照某种散列关系排序,读R时对已散列内容进行比较
散列函数可取连接条件中的相应属性
基于索引的算法
广泛用于选择操作、连接操作等
- 基于索引的选择算法
(1)辅助快速索引
(2)索引应用示例分析
- 基于有序索引的连接算法
基于B+树的Zig-Zag算法,“跳来跳去”
本文地址:https://blog.csdn.net/qq_40301196/article/details/107131652