数据库系统实现 查询执行与优化

查询

• 顺序扫描文件表并按关键字排序
• 性能参数估计
  • B(R)：包含关系R的全部记录的磁盘块数
  • T(R)：关系R中记录个数
  • v(R,a)： 关系R中属性a 的取值个数
• 一趟算法
  • 一次单个元组操作的一趟算法：每次读入R关系的一个盘块，处理一条记录即可
  • 整个关系的一元操作的一趟算法：
    • 消除重复：
      • 将已经遇到的元组缓存在内存中（散列或者平衡二叉树）
      • B(δ(R))<= M(内存缓冲块数)
  • 二元操作的一趟算法（并，交差，积）
    
• 基于元组的嵌套循环连接
  
• 基于块的嵌套循环连接
  
  
• 基于排序的两趟算法B((R))<= M^2
  • 排序：子排序 + 多路归并
  • 去重：字排序 + 多路归并（去重）
    
• 基于散列的两趟算法
  • 散列
    
  • 去重：同一个桶内部去重即可
  • 分组：散列函数依赖于分组属性，保证每个桶内为一个分组即可
• 缓冲区管理： 最近最少使用（LRU）,先进先出（FIFO）,时钟算法顺时针查找
• 多趟排序
  • 多路归并排序子表
  • 一元操作根据选择条件筛选元组，放入输出
  • 二元操作子表归并时，比对两个关系中的元组
  • 多趟排序性能
    
• 散列多趟
  • 算法
    

查询改进

• 不改变表达式结果的情况下，选择操作尽量在语法树上下移
  • 并操作：选择下推到两个参数
  • 差操作：选择下推到第一个参数
  • 其它运算，选择下推至第一个参数
• 投影下推，但是原位置仍保留投影

故障恢复