course database

第九章 查询优化

Posted by fzy on January 23, 2024

查询优化

查询处理的阶段 (记背)

image-20230615141428564

查询优化：选择一个高效的执行查询处理策略

查询优化分类：

  • 代数优化：指关系代数表达式的优化
  • 物理优化：指存取路径和底层操作算法的选择

查询优化的方法：

https://www.cnblogs.com/LyndonYoung/articles/11063788.html

  • 基于规则

    基于规则的优化就是当数据库执行一条query语句的时候必须遵循预先定义好的一系列规则来确定执行过程

  • 基于代价

    让执行引擎依据预先存储到数据库中表的一些实时更新的统计信息来选择出最优代价最小的执行计划来执行query语句，表的统计信息一般会有表大小，行数，单行长度，单列数据分布情况，索引情况等等

  • 基于语义

    从语义的角度对SQL进行优化，不是一种形式上的优化，所以其优化的范围，可能覆盖其他类型的优化范围。

选择操作的实现

  • 全表扫描
  • 索引扫描（B+树索引或者Hash索引）

连接操作的实现

连接操作是最耗时的操作之一，连接操作主要有以下的实现方法

https://developer.aliyun.com/article/283798

  • 嵌套循环：对外层的每一个元组，检索内层循环中的每一个元组，检查两个元组 是否在连接属性上相等。（最耗时）

  • 排序-合并：先对两个表按照链接属性排序，然后合并输出（）

    排序合并连接是嵌套循环连接的变种。排序合并连接（Sort Merge Join）是一种两个表在做表连接时用排序操作（Sort）和合并操作（Merge）来得到连接结果集的表连接方法。

  • 索引连接：通过连接属性将两张表的值连接起来。

  • Hash连接：将连接属性作为Hash码，用同一个hash函数将两个表元组散列到同一个hash文件中。

代数优化：构建语法树

查询优化一般准则：（记背）

  • 选择运算应该尽可能先做（减少中间关系）

  • 再执行连接操作之前对关系适当进行预处理
    • 按照连接属性排序
    • 在连接属性上建立索引

  • 投影运算和选择运算同时做（避免重复扫描）

  • 将投影运算与其前面或者后面的双目运算结合（减少扫描遍数）

  • 某些选择运算+在其前面的笛卡尔积连接运算

    先选择、排序索引预处理、选择投影同时开、

关系代数等价变换规则

等价变化就是用相同的关系代替原本的关系，得到的结果是相同的。

image-20230615141846199

image-20230615141922151

image-20230615142010998

image-20230615142221169

image-20230615142309223

image-20230615142347990

image-20230615142357235

1.连接、笛卡尔积交换律

2.连接、笛卡尔积结合律

3.投影串接

4.选择串接

5.选择和投影的交换律

6.选择与笛卡尔积的交换律

7.选择和并的交换

8.选择和差的交换

9.投影和笛卡尔积的交换

10.投影和并的交换

关系代数表达式的优化算法

先构造查询树查询树是一种表示关系代数表达式的树形结构。在一个查询树中，叶子结点表示关系，内结点表示关系代数操作。查询树以自底向上的方式执行

  • 分解选择运算

    规则4，把形如бF1 ∧F2 ∧ … ∧ Fn (E)变换为бF1 (бF2(… (бFn(E))… ))

  • 通过交换选择，将其尽可能移到叶子端。

    规则4，5~8，选择的交换律

  • 通过交换投影，将其尽可能移到叶子端。

    规则3，5，9~10，投影的交换律

  • 合并串接的选择和投影运算，放在一起执行。

  • 对内节点分组。

  • 生成程序

    分解选择、交换选择、交换投影、合并串接、内节点分组

物理优化

物理优化就是要选择合理高效的操作算法或者存取路径。

基于启发式规则

选择操作的启发式规则

小关系，就全表顺序索引，大关系就看选择条件是不是主码，如果是的话可以采用主码索引。如果是非主属性的查询，要估算查询的比例占表的多少，较少（<10%)的时候用索引，否则还是全表扫。

连接操作的启发式规则

如果两个表都已经按照属性排序了，就用排序合并方法。如果有表在连接属性上建立了索引，就用索引连接方法。如果其中一个表比较小，就用Hash连接。一定要用嵌套循环的时候将表小的放在外层循环。

基于代价估算的优化

简单来讲就是数据字典中已经有了表的一些统计信息，你就可以用类似估计复杂度的方法来估算代价。选择估计代价最小的方法来执行。

优化步骤

  1. 将查询转换成某种内部表示
  2. 进行代数优化，将语法树转换成标准形式
  3. 物理优化，选择底层的存取路径
  4. 生成查询计划，选择代价最小的

SQL优化

这一部分大纲里面没有写，暂时不整理，后面复习看情况有必要的时候再整理。

第9章 关系查询处理和查询优化

1.试述查询优化在关系数据库系统中的重要性

答：关系数据库系统的查询优化既是 RDBMS 实现的关键技术又是关系数据库系统的优点所在。它减轻了用户选择存取路径的负担。用户只要提出“干什么”，不必指出“怎么干”。查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化”做得更好。

2.试述查询优化的一般准则。

答：下面的优化策略一般能提高查询效率： ( l ）选择运算应尽可能先做； ( 2 ）把投影运算和选择运算同时进行； ( 3 ）把投影同其前或其后的双目运算结合起来执行； ( 4 ）把某些选择同在它前面要执行的笛卡儿积结合起来成为一个连接运算； ( 5 ）找出公共子表达式； ( 6 ）选取合适的连接算法。

3.试述查询优化的一般步骤。

答：各个关系系统的优化方法不尽相同，大致的步骤可以归纳如下： ( l ）把查询转换成某种内部表示，通常用的内部表示是语法树。 ( 2 ）把语法树转换成标准（优化）形式。即利用优化算法，把原始的语法树转换成优化的形式。 ( 3 ）选择低层的存取路径。 ( 4 ）生成查询计划，选择代价最小的。

CATALOG
    FEATURED TAGS
    course database csdiy software engineer os blog cpp project math 计算方法 ML