数据库-实现篇 第十五讲

查询实现算法概述——关系代数操作

数据库查询基本思想： 数据库的核心操作 （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算法，“跳来跳去”