db_8 查询处理与查询优化

查询处理概述

关系查询处理的四个阶段

  • 查询分析
  • 查询检查
    • 静态
  • 查询优化
  • 查询执行
    • 代码生成器

image-20241230192325318

查询时间开销

  • 磁盘 I/O代价
    • tT–传输一个块的平均时间
    • tS– 一次磁盘寻道时间加上旋转延迟
    • 传输b块加上S次寻道旋转的时间开销
    • $b t_T+ S t_S$
  • CPU代价
  • 内存代价
  • 通信代价

查询操作的实现

选择操作

（1）全表扫描

  • 按照物理顺序读表的M块到内存
  • 检查内存的每个元组t
  • 如果满足条件则输出t，直到表所有块都经过上述检查

（2）索引扫描

  • 如果在选择条件的属性上有索引
  • 先通过索引找到目标索引项
  • 再通过索引项找到元组

当选择率较低时，基于索引的选择算法要优于全表扫描算法

选择率较高，或者要查找的元组均匀地分布在查找的表中，基于索引的选择算法的性能不如全表扫描算法

排序操作

  • 快速排序法
    • 内存中完全容纳的关系
  • 外排序-归并算法
    • 建立多个排好序的归并段（run），每个段仅包含关系的部分记录
    • 对归并段进行归并
    • 内存中无法容纳的关系

连接操作

最耗时的操作

（1）嵌套循环法

  • 外循环表和内循环表

  • 选择小表作为外循环

    • 如果连接操作使用的缓冲区块数为k

      分配（k-1） 块给外表r

      1块给内表s,

      br为表r的块数，bs为表s的块数

    • 存取块数为$b_r+\frac{b_r}{k-1}*b_s$

  • 适用于任何连接条件

  • 代价高

（2）索引连接法

  • 内层关系s的连接属性上有索引，
  • 对于外层关系r中的每一个元组tr，用索引查找s中与tr 满足连接条件的元组
  • 选择索引作为内循环
  • 都有索引 选择小表作为外循环

（3）排序-合并法

  • 只能用于等值连接或自然连接！！！！

  • 将两个关系在连接属性上排序

  • 为每个关系分配一个指针，分别为pr和ps

    对于pr指向r 的一个连接属性值，移动ps找到s中与该值相等的元组， 与pr指向的元组做连接

  • 两个关系的每个块都只需要读一次

    • 存取块数为$b_r+b_s$

（4） Hash join法

  • 只能用于等值连接或自然连接！！！！

  • 哈希函数h用于划分两个关系

    h将连接属性值映射到{0, 1, …, n} 集合上

    将r的元组划分为r0, r1, . . ., rn 个部分，如果 h(tr [JoinAttrs])=i, 则元组tr 将被放入ri ，同理将s也划分成s0,, s1. . ., sn 个部分

  • 对于某个连接属性值，若被哈希为i，则s中相应的元组必定在si 中，而r中的元组必定在ri 中，因此只需将si和ri中的元组相比

    （还要比较是因为可能发生了碰撞）

其他运算

  • 去重：

    使重复数据相邻，保留一个数据删除其它

    • 排序
    • Hash

  • 投影

    • 每个元组投影，然后去重

  • 集合运算—并，差，交

    • 排序-合并连接：排序然后对每个已排序的关系扫描一次
    • hash-join：将两个关系分区，在两个关系对应区中执行运算

  • 库函数

    • 基于分组属性进行排序或Hash以聚集同组的元组，再执行库函数

查询表达式的执行

  • 物化方法
    • 按次序每次只执行一个运算，运算结果被物化到一个临时关系中，这 些临时关系一般需要写到磁盘上
    • 方法适用性广泛，但临时表的写和读代价大
  • 流水线方法
    • 执行多个运算，将结果传递给下一个运算
    • 不需要在磁盘上存储临时关系，代价小 ，但对有些运算不适用，如排序等

查询优化

查询优化目标

总代价=I/O代价+ CPU代价+ 内存代价+通信代价（分布式数据库）

选择一个高效执行的查询处理策略，使得查询代价最小

即访问磁盘的块数最少

查询优化结构

查询计划：定义了每个操作的算法以及这些操作执行的顺序

image-20241230200833387

按照优化的层次分类

  • 代数优化：关系代数表达式的优化，即按照一定的规则，改变代数表达式中操作的次序和组合
  • 物理优化：存取路径和底层操作算法的选择。

代数优化

基本概念

通过对关系代数表达式的等价变换来提高查询效率

  • 关系代数表达式的等价
    • 指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的

等价变换规则

image-20241230201848964

image-20241230201925414

image-20241230201933829

总结

  • 选择

    • 分配并、差、自然连接
    • 分配笛卡尔积 看条件里有谁的属性
    • 交换投影

  • 投影

    • 分配笛卡尔积、并
    • 交换选择

查询树

关系代数表达式的树形表示

操作的关系位于叶节点

关系运算位于内部节点

执行方式：自底向上执行，当一个内部节点的操作分量可用时，该节点的操作启动执行，执行结束后用结果关系代替该节点

  • SELECT -> 投影
  • FROM -> 笛卡尔积
  • WHERE -> 选择

查询树的启发式优化

  • 选择运算尽早执行（减少元组）
  • 投影运算尽早执行（减少属性）
  • 把投影运算和选择运算同时进行（减少扫描关系的次数）
  • 把笛卡尔积与选择转换为连接
  • 公共表达式的中间结果复用

image-20241230205509224

  • 对每个叶节点加必要的投影操作，以去掉对查询无用的属性
  • 如果笛卡尔积后还需按连接条件进行选择操作， 可将两者组合成连接操作

物理优化

选择高效合理的操作算法或存取路径，得到优化的查询计划

  • 基于规则的启发式优化方法
  • 基于代价估算的优化方法
  • 两者结合的优化方法

基于规则的启发式优化方法

  • 选择
    • 对于小关系，使用全表顺序扫描
    • 对于大关系：可以采用索引扫描法（如结果的元组数目较小），全表顺序扫描
  • 连接
    • 排序-合并法：两个表都已经按照连接属性排序
    • 索引连接法：一个表在连接属性上有索引
    • Hash join：连接属性上未排序且未建索引，且其中一个表较小
    • 嵌套循环法：选择较小的表为外循环表

基于代价估算的优化方法

利用数据库的统计信息计算各种操作算法的执行代价，选出具有最小代价的执行计划

数据库统计信息主要包括：

  • 每个基本表的规模，包括元组数、元组长度、占用块数以及溢出块数等
  • 基本表每个列的信息，包括不同值个数、最大与最小值，是否有索引以及索引类型等
  • 索引的具体信息，例如B+树索引的层数、不同索引值个数等