乘风原创程序

  • 数据库-实现篇 第十五讲
  • 2020/7/7 10:27:42
  • 查询实现算法概述——关系代数操作

    1. 数据库查询基本思想:
      数据库的核心操作
      (1)基本动作:
      并、差、积、选择、投影
      (2)基于关系代数提出的SQL语句,转化为关系代数的组合操作
      (3)程序执行机构进行解释、拆解

    2. 查询实现和查询优化:
      (1)将SQL语句转化为关系代数表达式
      在这里插入图片描述
      转化后,若先执行连接操作,则会造成爆炸,故DBMS不能按照该顺序进行执行
      尽量把选择、投影操作移到乘积的前面去执行

    (2)改变操作次序
    (3)为每一个操作选择一个优化的程序进行执行——物理查询优化
    (4)执行

    1. 物理查询优化:实现关系代数操作的成熟的组合,求代价最少
      在这里插入图片描述
    2. 数据库三大类操作:
      (1)一次单一元组的一元操作:选择、投影
      ——迭代器算法
      (2)整个关系的一元操作:DISTINCT、GROUP BY、SORTING
      (3)整个关系的二元操作:并、交、差、连接、积
      ——一趟扫描、两趟扫描、多趟扫描:内存使用情况
      基于排序、散列、索引的算法

    连接操作的实现算法

    在这里插入图片描述

    迭代器

    对于一次单一元组操作

    在这里插入图片描述
    物化策略扫描三遍数据库,流水线策略扫描一遍数据库

    1. 迭代器:迭代地读取一个集合中的每一个元素,而封装其读取细节
      在这里插入图片描述

    2. 并运算迭代器构造
      在这里插入图片描述

    3. 选择运算迭代器:
      在这里插入图片描述

    4. 投影运算迭代器:
      在这里插入图片描述

    5. R和S的连接迭代器:
      在这里插入图片描述

    趟扫描算法——去重复操作

    1. 关系 / 数据表的读取
      (1)聚簇关系——关系的元组集中存放
      TableScan(R) —— 表空间扫描算法,扫描结果未排序
      B(R):R的存储块数目
      SortTableScan(R) —— 排序扫描算法
      IndexScan(R)
      SortIndecScan(R)
      (2)非聚簇关系
      T(R):R的元组数目

    2. 去重复操作 DISTINCT
      (1)在内存中保存已处理过的元组,当新元组到达时与之前的元组做比较
      在这里插入图片描述
      重点:设计内存部分的数据结构,便于元组比较时的快速查找
      (2)算法复杂性:B(R)
      (3)应用条件:B(R)<=M

    3. 分组聚集计算
      (1)分组聚集:在内存当中保留所有的分组,保存每个分组上的聚集信息
      在这里插入图片描述
      (2)算法复杂性:B(R)
      (3)应用条件:B(R)<=M
      (4)实例:基于散列的一趟扫描算法:
      在这里插入图片描述
      分组的桶若有溢出桶,则降低了查询速率。

    (5)集合操作需要去重复,包操作需要计数统计每一个元组出现的次数
    在这里插入图片描述
    (6)连接操作优化 R和S连接
    在S读入时直接按照某种散列关系排序,读R时对已散列内容进行比较
    散列函数可取连接条件中的相应属性
    在这里插入图片描述

    基于索引的算法

    广泛用于选择操作、连接操作等

    1. 基于索引的选择算法
      (1)辅助快速索引
      (2)索引应用示例分析
      在这里插入图片描述
      在这里插入图片描述
    2. 基于有序索引的连接算法
      基于B+树的Zig-Zag算法,“跳来跳去”

    在这里插入图片描述

    本文地址:https://blog.csdn.net/qq_40301196/article/details/107131652