复杂查询的执行设涉及多次存取磁盘的操作, 要选择最小化磁盘存取的方法
关系表达式的转换
[1] 查询处理策略第一步: 找到一个关系代数表达式, 使它与所给表达式等价且有更小执行代价
每个关系代数表达式都表示某个特定的操作序列
[2] 等价表达式的枚举:
- 子表达式e上使用等价规则把表达式E转化为E’, 则除了e及其转换, E与E’有相同的子表达式
e及其转换通常也有许多相同的 子表达式, 可以采用一些表达式表示技术, 使两个表达式指向共享的子表达式, 减少对空间的需求 - 优化器可以避免检查用等价规则所有可以产生的表达式
表达式结果集统计大小的估计
[1] 数据库为每一个关系r存储统计信息: 元组数n, 磁盘块数b, 元组字节数l, 块因子(一个磁盘块能容纳关系中元组的个数)f, 特定属性A中出现不同取值的数目V(A, r); 索引的高度和叶节点的页数
V(A, r)也可以针对属性集
如果r的元组在物理上存储在一个文件中, 则b=n/f
[2] 使用直方图存储——依赖这些信息选择合适的策略, 如查询过程有多个索引用于辅助时
[3] 近似的统计数据是可以接受的
统计数据可以基于基础数据随机抽样的样本
[4] 有些数据库是管理员定期运行一条命令更新统计数据
有些数据库可以在某些时间点自动更新统计数据, 如当元组数量显著变化; 或者例如一个关系扫描估计的基数和执行一个查询时真正的基数差异显著时, 启动统计数据更新
[5] 选择、连接、其他运算结果集大小估计 336-339页, 不同取值个数的估计 339-340页
执行计划的选择
基于代价的连接顺序选择
[1] 动态规划算法:
- 尽早访问单个关系时就使用选择, 将计算出的执行计划存储在(一个以关系集做索引的关联数组)bestplan中, 每个项包含两部分: S的最佳计划的代价 + 该计划本身
- 检查是否已经算出给定关系集S计算连接的最佳执行计划, 是则返回
- 如果S只包含一个关系, 访问S的最佳方法记录在bestplan中, 涉及用一个索引定位元组并取出或者扫描整个关系表(索引扫描或关系表扫描)
如果除了通过索引扫描的选择条件, S上还有其他选择条件, 则添加一个选择运算到计划中保证S上的所有选择 - 如果S包含多个关系, 将S分成两个不相交的子集, 对每个子集递归找出最佳执行计划
[2] 仅仅为有n个给定关系的关系集合每个子集找出最佳连接顺序是不够的
要为每个子集连接结果的每个感兴趣的排序顺序找出最佳连接顺序
(如果某个具体的元组排序顺序对后面运算可能有用, 该特定顺序为感兴趣的排序顺序)
采用等价规则的基于代价的优化器
[1] 物理等价规则: 允许将例如连接这样的逻辑操作转换成像散列连接或嵌套循环连接这样的物理操作, 添加到原来的等价规则中
[2] 使等价规则优化高效的技术:
- 避免应用等价规则创建相同子表达式的多个副本, 来节约空间
- 检测相同表达式重复推导
- 基于缓存的动态规划形式, 第一次优化子表达式时, 缓存存储最优的查询执行计划
后续优化相同子表达式的请求通过返回已缓存的计划进行处理 - 维护(到任何时刻为止为任何子表达式产生的)代价最低的计划, 并且对(其他任何比当前该子表达式代价最低计划)代价高的计划剪枝, 避免产生所有可能的执行计划
启发式优化
[1] 尽早执行选择操作, 尽早执行投影操作, 避免笛卡尔积操作
选择运算优先于投影运算
[2] 左深连接顺序: 只对特殊类型的连接次序进行搜索
用于流水线计算特别方便, 右操作对象是一个已存储的关系, 每个连接只有一个输入来自流水线
[3] 优化成本预算: 超过预算时停止搜索最有计划, 返回当前找到的最优计划
预算本身可能动态设置: 找到低开销计划则降低预算; 找到的最优计划比较昂贵, 则需要更多时间优化, 带来执行时间明显减少
[4] 计划缓存: 同样的查询常数值不同, 可以使用缓存的查询执行计划
物化视图和其他查询优化
[1] 物化视图用来加速查询处理, 原关系发生修改时, 需要用增量的视图维护来高效的更新物化视图
利用包含一个操作的输入的变化量的代数表达式, 能够完成对该操作的变化量的计算
如何借助物化视图进行查询优化, 如何选择需要待物化的视图[2] top-K优化, 连接极小化, 更新优化, 多查询优化, 参数化查询优化