09.关系查询处理和查询优化

查询处理

查询处理步骤

• 查询分析

  • 对查询语句进行扫描
  • 词法分析和语法分析

• 查询检查

  • 合法性检查
  • 视图转换
  • 安全性和完整性初步检查

• 查询优化

  • 查询优化分类
    • 代数优化/逻辑优化
    • 物理优化
  • 查询优化的选择依据
    • 基于规则
    • 基于代价
    • 基于语义

• 查询执行

实现查询操作的算法示例

• 选择操作的典型实现

  • 全表扫描方法
  • 索引扫描方法

• 连接操作的实现

  • 嵌套循环算法
  • 排序-合并算法
  • 索引连接算法
  • Hash Join算法

查询优化

查询优化概述

• 关系系统的查询优化 : 只要提出"干什么", 不必指出"怎么干"

• 关系数据库管理系统通过某种代价模型计算出各种查询执行策略的执行代价, 然后选取代价最小的执行方案

• 查询优化的总目标是选择有效的策略, 求得给定关系表达式的值, 使得查询代价最小

一个实例

见ppt ch59

• 第一种情况

  • 计算广义笛卡尔积
  • 作选择操作
  • 作投影操作

• 第二种情况

  • 计算自然连接
  • 读取中间文件块, 执行选择运算
  • 把第2步结果投影输出

• 第三种情况

• 有索引更优

代数优化

关系代数表达式等价变换规则

• 代数优化策略是通过对关系代数表达式的等价变换来提高查询效率

• 连接, 笛卡尔积交换律

  

• 连接, 笛卡尔积的结合律

  

• 投影的串接定律

  

• 选择的串接定律

  

• 选择与投影操作的交换律

  

• 选择与笛卡尔积的交换律

  

• 选择与并的分配律

  

• 选择与差运算的分配律

  

• 选择对自然连接的分配律

  

• 投影与笛卡尔积的分配律

  

• 投影与并的分配律

  

查询树的启发式优化

• 选择运算应尽可能先做

• 把投影运算和选择运算同时进行

• 把投影同其前或其后的双目运算结合起来, 没有必要为了去掉某些字段而扫描一遍

• 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算

• 找出公共子表达式

优化查询树

物理优化

选择高效合理的操作算法或存取路径

基于启发式规则的存取路径选择优化

• 选择操作的启发式规则

  • 五种策略

• 连接操作的启发式规则

  • 四条规则

基于代价的优化

• 统计信息

  • 对每个基本表
  • 对基表的每个列
  • 对索引

• 代价估算

  • 全表扫描算法的代价估算公式
  • 索引扫描算法的代价估算公式
  • 嵌套循环连接算法的代价估算公式
  • 排序-合并连接算法的代价估算公式