【学习笔记】数据库系统原理 第九章 查询优化

以下内容为参考课件和《数据库系统概论》(第5版,王珊等著)的个人整理,若有错误欢迎指出

第九章 查询优化

文章目录

一、概述

1、目的

得到更好的查询性能。一般分为代数优化(基于关系代数的等价变换)和物理优化(存取路径等底层操作)。

2、查询处理基本步骤

语法分析和翻译,转化为内部表示形式(一般为查询树);然后进行优化;最后执行 执行计划。
【学习笔记】数据库系统原理 第九章 查询优化

3、操作实现方法

  • 选取操作的实现

    • 全表扫描方法,对于每一个元组都测试是否满足选择条件。

    • 折半扫描方法,如果文件按照某一属性排序,就可以折半扫描

    • 索引扫描方法,对属性建立索引表,根据索引项的指示去访问。

  • 连接操作的实现

    • 嵌套循环方法,即外层循环是一个表,内层循环是另一个表
    • 排序-合并方法,按照连接的属性排序,然后操作。一般用于等值连接,即以一个表为基准,在另一个表查找,找到第一个比基准大的,那就说明没有或者在此之前找到了,那么基准表就可以下一个元组了,然后另一个表继续往后找。
    • 索引连接方法,对一个表的连接属性建立索引,在另一个表中按照索引进行查找。
    • Hash Join方法,对元素较少的表建立Hash表,然后通过hash值查找。一般也是用于等值连接。

4、查询代价的度量

总代价 = IO代价(IO块数或次数)+CPU代价+通信开销(client、server的通信)+ 内存代价

  • 不会直接用时间算(不同设备有差异)

  • 主存中缓冲区的大小是一个重要影响因素

  • 减小中间结果的大小十分重要

二、代数优化

1、关系代数等价

结果有相同的属性集和元组集

2、常用的等价变换规则(关系代数)

  • 连接、笛卡尔积的交换律、结合律

  • 投影的串接定律: Π A 1 . . . . A n ( Π B 1 . . . B m ( E ) ) = Π A 1 . . . A n ( E ) \Pi_{A_1....A_n}(\Pi_{B_1...B_m}(E))=\Pi_{A_1...A_n}(E) ΠA1​....An​​(ΠB1​...Bm​​(E))=ΠA1​...An​​(E)

  • 选择的串接律(合并条件): σ F 1 ( σ F 2 ( E ) ) = σ F 1 ∧ F 2 ( E ) \sigma_{F_1}(\sigma_{F_2}(E))=\sigma_{F_1\wedge F_2}(E) σF1​​(σF2​​(E))=σF1​∧F2​​(E)

  • 选择与其他操作的交换律:

    假设相同属性同名

    • σ F ( E 1 × E 2 ) = σ F ( E 1 ) × σ F ( E 2 ) \sigma_F(E_1\times E_2) = \sigma_F(E_1)\times\sigma_F(E_2) σF​(E1​×E2​)=σF​(E1​)×σF​(E2​),这个是否含有相应属性而选择
    • σ F ( E 1 ∪ E 2 ) = σ F ( E 1 ) ∪ σ F ( E 2 ) \sigma_F(E_1\cup E_2) = \sigma_F(E_1)\cup \sigma_F(E_2) σF​(E1​∪E2​)=σF​(E1​)∪σF​(E2​)
    • σ F ( E 1 − E 2 ) = σ F ( E 1 ) − σ F ( E 2 ) \sigma_F(E_1 - E_2) = \sigma_F(E_1)- \sigma_F(E_2) σF​(E1​−E2​)=σF​(E1​)−σF​(E2​)
    • σ F ( E 1 ⋈ E 2 ) = σ F ( E 1 ) ⋈ σ F ( E 2 ) \sigma_F(E_1\Join E_2) = \sigma_F(E_1)\Join\sigma_F(E_2) σF​(E1​⋈E2​)=σF​(E1​)⋈σF​(E2​), F F F 只涉及公共属性
  • 投影和其他操作的交换律

    • Π A 1 . . . A n , B 1 . . . B m ( E 1 × E 2 ) = Π A 1 . . . A n ( E 1 ) × Π B 1 . . . B m ( E 2 ) \Pi_{A_1...A_n,B_1...B_m}(E_1\times E_2) = \Pi_{A_1...A_n}(E_1)\times \Pi_{B_1...B_m}(E_2) ΠA1​...An​,B1​...Bm​​(E1​×E2​)=ΠA1​...An​​(E1​)×ΠB1​...Bm​​(E2​)
    • Π A 1 . . . A n ( E 1 ∪ E 2 ) = Π A 1 . . . A n ( E 1 ) ∪ Π A 1 . . . A n ( E 2 ) \Pi_{A_1...A_n}(E_1\cup E_2) = \Pi_{A_1...A_n}(E_1)\cup \Pi_{A_1...A_n}(E_2) ΠA1​...An​​(E1​∪E2​)=ΠA1​...An​​(E1​)∪ΠA1​...An​​(E2​)​,假设相同属性 名字相同
    • 对于与选择的复合,若先投影,那么投影结果要包含所要的和选择涉及的属性

3、一般准则(启发式优化)

  • 选择运算尽可能先做——减小中间关系

  • 连接前适当预处理(排序、索引)

  • 投影和选择一起做——避免重复扫描

  • 投影还能与一些双目运算结合起来算——减少扫描次数

  • 一些选择(等值)+笛卡尔积操作 转为 连接操作

  • 公共子表达式只算一次,多次引用

  • 连接操作尽量生成小的结果,可以借助交换律、或先投影去掉没用的属性

4、查询树

关系代数表达式的树形表示:叶节点是输入的关系(表),内部节点是关系操作,自底向上执行。

先按照表达式画出树,再根据上述规则优化。

例子:
【学习笔记】数据库系统原理 第九章 查询优化
【学习笔记】数据库系统原理 第九章 查询优化
优化后(尽量早做选择,连接代替笛卡尔积,先连接产生较小的结果,用投影去除没用的属性):
【学习笔记】数据库系统原理 第九章 查询优化

上一篇:蓝桥杯 Huffman树 python实现


下一篇:java 蓝桥杯 Huffuman树