启发式优化(数据库)
时间：2022-11-06 14:30:01 | 来源：信息时代
时间：2022-11-06 14:30:01 来源：信息时代
启发式优化 : 启发式优化是指查询优化器利用启发式规则来选取查询计划,这种方法可以有效缩减查询计划的搜索空间,提高查询优化的效率。
基于代价的查询优化的一个缺点是,寻找优化的查询方案的搜索空间过于庞大,使得优化本身的代价过高。查询计划树中所有操作符的可能组合形式构成了查询计划树的空间,随着操作符数目的增长,这个空间扩张的速度非常快。以一个四表连接的查询为例,其可能的树形状有5种,如图1所示。对于每一种树形状,四个关系又可以有4!即24种排列次序,于是,四表连接的查询树共有5×24即120种形式。
图1 四表连接的五种连接树形状
n个关系的连接操作,其树形状的数目T(n)可以如下递归计算出来:
T(1)=1,
例如T(1)=1,T(2)=1,T(3)=2,T(4)=5,T(5)=14,T(6)=42,等等。对于n个关系,每种树形可以有n!种方法来分配关系。因此当允许所有树型时,查询计划树的可能数目为T(n)×n!。对于每个操作符结点,又可能有m种算法可供选择,因此可以得到n
m×T(n)×n! 种查询执行计划。为每一种查询执行计划计算其代价,并从中选出最小代价的计划,当n比较大时,其代价将是非常大的。
启发式优化就是查询优化器利用启发式规则来减少优化本身的代价,即查询优化过程中,运用启发式规则选取若干较优的候选方案,只计算这些候选方案的执行代价,而不必比较全部可能的方案,从而缩减了查询优化的搜索空间,减少了生成备选方案的开销和估算代价的工作量,较快地选出最终的优化方案。当然这样做的前提是可能丢失最佳执行计划,因为这些启发式规则只是在通常情况下的经验规则,但并不能适用于所有情况。
启发式优化的策略可以分为两大类,第一类是限制查询计划树形状的规则,第二类是选取操作算法的启发式规则。
限制查询计划树形状的规则,就是将查询计划树限制为某一类固定形状,例如对于连接树,DBMS通常只考虑左深连接树,即图1(a)形状的树。这样,对于n个关系,如果只有一种左深连接树的形状,当每个操作符m种算法时,搜索空间由n
m×T(n)×n! 种可能的查询执行计划降低为n
mn! 种可能的计划。
选取操作算法常用的启发式规则包括:
(1)对于逻辑计划中的σ
A=c(R),如果R在属性A上有索引,则执行一个索引扫描以获得R中A属性值等于c的元组。
(2)对于逻辑计划中的σ
A=cand…(R),如果R在属性A上有索引,则先执行一个索引扫描以获得R中A值等于c的元组,然后再对其作进一步筛选(用物理操作符Filter表示)。
(3)如果参与连接的一个关系在连接属性上有索引,则采用索引连接,且该关系作内表。
(4)如果参与连接的一个关系是按连接属性排好序的,则采用排序-合并连接比用散列连接好,但不一定比索引连接好。
(5)计算三个或更多的关系的并或交时,先对最小关系进行组合。
显然,使用了限制查询计划树形状的规则和选取操作算法的启发式规则后,查询优化器的代价可以明显降低。这就是启发式优化的价值所在。
在线咨询
