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

第九章 关系查询处理和查询优化：v查询处理是关系数据库管理系统的核心，查询优化技术是查询处理的关键技术

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

• 关系数据库系统的查询处理
  • 查询处理步骤
  • 实现查询操作的算法示例
    • 选择操作的实现
      • 全表扫描方法 (Table Scan)
        • 对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出
        • 适合小表，不适合大表
      • 索引扫描方法 (Index Scan)
        • 适合于选择条件中的属性上有索引(例如B+树索引或Hash索引)
        • 通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组
    • 连接操作的实现
      • （1）嵌套循环算法(nested loop join)
      • （2）排序-合并算法(sort-merge join 或merge join)
      • （3）索引连接(index join)算法
      • （4）Hash Join算法
• 关系数据库系统的查询优化
  • 查询优化概述
    • 关系系统
      • 是关系数据库管理系统实现的关键技术又是关系系统的优点所在
      • 减轻了用户选择存取路径的负担
    • 非关系系统
      • 用户使用过程化的语言表达查询要求，执行何种记录级的操作，以及操作的序列是由用户来决定的
      • 用户必须了解存取路径，系统要提供用户选择存取路径的手段，查询效率由用户的存取策略决定
      • 如果用户做了不当的选择，系统是无法对此加以改进的
    • 优点
      • 用户不必考虑如何最好地表达查询以获得较好的效率
      • 系统可以比用户程序的“优化”做得更好
    • 总目标
      • 选择有效的策略
      • 求得给定关系表达式的值
      • 使得查询代价最小(实际上是较小)
• 物理优化
  • 基于启发式规则的存取路径选择优化
    • 选择操作的启发式规则
      • 对于选择条件是“非主属性＝值”的查询，并且选择列上有索引
      • 对于选择条件是属性上的非等值查询或者范围查询，并且选择列上有索引
      • 对于用AND连接的合取选择条件
      • 对于用OR连接的析取选择条件，一般使用全表顺序扫描
    • 连接操作的启发式规则
      • 如果2个表都已经按照连接属性排序
      • 如果一个表在连接属性上有索引
      • 如果上面2个规则都不适用，其中一个表较小
      • 可以选用嵌套循环方法，并选择其中较小的表，确切地讲是占用的块数(b)较少的表，作为外表(外循环的表)
  • 基于代价的优化
    • 1.统计信息
      • 对每个基本表
      • 对基表的每个列
      • 对索引
    • 2.代价估算示例
      • 全表扫描算法的代价估算公式
      • 索引扫描算法的代价估算公式
      • 嵌套循环连接算法的代价估算公式
      • 排序-合并连接算法的代价估算公式
    • 3.优化方法
• 代数优化
  • 关系代数表达式等价变换规则
    • 代数优化策略：通过对关系代数表达式的等价变换来提高查询效率
    • 关系代数表达式的等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的
    • 两个关系表达式E1和E2是等价的，可记为E1≡E2
    • 常用的等价变换规则
      • 连接、笛卡尔积交换律
      • 连接、笛卡尔积的结合律
      • 投影的串接定律
      • 选择的串接定律
      • 选择与投影操作的交换律
      • 选择与笛卡尔积的交换律
      • 选择与并的分配律
      • 选择与差运算的分配律
      • 选择对自然连接的分配律
      • 投影与笛卡尔积的分配律
      • 投影与并的分配律
  • 查询树的启发式优化
    • 典型的启发式规则
      • 选择运算应尽可能先做
      • 把投影运算和选择运算同时进行
      • 把投影同其前或其后的双目运算结合起来，没有必要为了去掉某些字段而扫描一遍关系。
      • 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算，连接特别是等值连接运算要比同样关系上的笛卡尔积省很多时间。
      • 找出公共子表达式