数据库原理——第九章:关系查询处理和查询优化

参考书目《数据库系统概论(第5版)》

关系数据库系统的查询处理

关系数据库管理系统查询处理分为4个阶段:查询分析查询检查查询优化查询执行

  1. 查询分析:对SQL语句进行语法分析词法分析,报告语句中可能的语法错误
  2. 查询检查:对合法的查询语句进行语义检查,即根据数据字典中有关的模式定义检查语句中的数据库对象,如关系名、属性名是否存在和合法
    • 可能涉及视图消解用户存取权限完整性约束检查,这时的完整性检查是初步的、静态的检查
    • 关系数据库管理系统一般都用查询树(也即语法分析树)来表示扩展的关系代数表达式
  3. 查询优化:选择一个高效执行的查询处理策略;按照优化的层次一般可分为代数优化物理优化
    • 代数优化是指关系代数表达式的优化
    • 物理优化是指存取路径和底层操作算法的选择
  4. 查询执行:依据优化器得到的执行策略生成查询执行计划,由代码生成器生成执行这个查询计划的代码。然后执行并回送查询结果

关系数据库系统的查询优化

查询优化在关系数据库系统中有着非常重要的地位,关系数据库系统取得巨大成功的原因关键是得益于查询优化技术的发展
查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较高的效率,而且在于系统可以比用户程序做的更好,原因如下:

  1. 优化器可以从数据字典中获取许多统计信息,而用户程序则难以获得这些信息
  2. 如果数据库的物理统计信息变了,系统可以自动对查询进行重新优化而不必重写程序
  3. 优化器可以考虑数百种不同的执行方案,而程序员一般只能考虑有限的几种
  4. 优化器中实现包含了很多复杂的优化技术,这些技术的实现降低了编写人员的门槛

在集中式数据库中,查询执行开销主要包括磁盘存取块数(I/O代价)、处理机时间(CPU代价)以及查询的内存开销,在分布式数据库中还要加上通信代价
查询执行的总代价 = I/O代价 + CPU代价 + 内存代价 + (通信代价)


代数优化

查询树的启发式优化:

  1. 选择运算应尽可能先做
  2. 把投影运算和选择运算同时进行
  3. 把投影同其前或后的双目运算结合起来
  4. 把某些选择同它前面要执行的笛卡尔积结合起来成为一个连接运算
  5. 找出公共子表达式

物理优化

物理优化的目的是为了选择高效合理的操作算法存取路径,方法有

  1. 基于规则的启发式优化
  2. 基于代价估算的优化
  3. 二者结合的优化方法