查询实现算法概述——关系代数操作
-
数据库查询基本思想：
数据库的核心操作
（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