基于段式右线性树查询优化方法(数据库)
时间：2022-12-28 04:30:01 | 来源：信息时代
时间：2022-12-28 04:30:01 来源：信息时代
基于段式右线性树查询优化方法 : 采用片段式右线性树的模型表示查询执行计划的一种优化方法。
1.片段式右线性树(SRD树)
片段式右线性树,简称为SRD树,由一组右线性树连接而成,每个右线性树称为一个片段,每个片段中的一个连接操作称为一个阶段。片段式右线性树可递归地定义如下:
(1)右线性树是一个片段式右线性树。
(2)如果T是一个片段式右线性树,则用一个片段式右线性树替代T的任何一个叶结点所得到的树仍然是片段式右线性树。
在基于片段式右线性树的查询优化方法中,优化算法仅考虑由片段式右线性树表示的查询执行计划,查询执行计划空间由片段式右线性树查询执行计划组成。片段式右线性树查询执行计划空间远大于右线性树和左线性树的查询执行计划空间。因此,不能使用枚举方法,而需要采用更新颖、高效的启发式查询优化方法。
2.片段式右线性树(SRD)的构造过程
给定一个查询Q,Q的基于SRD树的查询优化问题是构造Q的优化SRD树的问题。Q的优化SRD树的构造过程如下:①确定SRD树的片段数m;②确定每个片段中的关系数的上界; ③以k和m为输入,调用启发式算法为每个片段选择一组连接关系,生成SRD树。以上三步的实现算法如下:
(1)确定SRD树的片段数和每个片段中的关系数:在确定SRD树的片段数时,必须考虑所有关系的大小和可用存储器空间的大小。在可用存储器空间的限制下,选择尽量小的片段数。如果片段数过多,由于建立Hash表、流水线处理、片段的结果关系写回磁盘等方面的开销,可能会引起查询处理时间的延长,影响系统的性能。片段数计算的规则为:在保证每个片段中的所有关系的大小不超过所有处理结点的累计存储器容量的前提下,选择最小的片段数,则一个SRD树的片段数应该是
其中,q是查询中的关系数,N是处理机数,|R
i|是R
i的字节数,M是每个处理机的存储器容量(字节数)。
(2)确定出SRD树的片段数以后,可以很容易地估算出每个片段中关系数的上界:
(3) 为各片段选择关系生成SRD树: 为每个片段选择一组连接关系是基于SRD树的查询优化算法的最复杂而且最关键的步骤。通常,有两种启发式算法可供采用:
最小开销算法(MW算法): 给定一组关系和整数k,MW算法的功能是确定一个由k个内关系R
1,…,R
k和一个外关系S组成的右线性树,形成SRD树的一个片段,使得如下的目标函数最小化:
对于i=1,…,k,W是|S|、|R
i|和|I
i|的线性组合。MW算法在选择内外关系时使用了贪心法,即从给定的关系集合中选择关系R使得W中项(C
1+C
2)|R|+(C
3+C
4)|I|最小,其中,I是由于选择R而产生的中间连接结果。MW算法首先从给定关系集合中选择一个关系作为R
1,然后选择另一个关系作为外关系S,次之再选择一个关系作为R
2,如此下去,最后选择一个关系作为R
k。确定R
1时,还不能计算与R
1有关的中间结果I
1,所以只需选择R
1使得(C
1+C
2)|R
1|最小。由于(C
1+C
2)是常数,只需选择R
1使得|R
1|最小。从选择外关系S开始,就可以计算出与所选择关系相关的中间连接结果。于是,从选择外关系S开始,每当选择一个关系R,必须保证(C
1+C
2)|R|+(C
3+C
4)|I|最小。设RS是给定的关系集合,MW算法如下:①从RS选择关系R作为R
1,使|R
1|最小,RS=RS-{R}; ②从RS选择关系R′作为S,使(C
1+C
3)|S|+(C
3+C
4)|I
1|最小,RS=RS-{R′};③对于2≤i≤k-1,从RS选择关系R′
i作为R
i,使(C
1+C
2)|R
i|+(C
3+C
4)|I
i|最小,RS=RS-{R′
i};④从RS选择关系R′
k作为R
k,使(C
1+C
2)|R
k|+C
5|I
k|最小,RS=RS-{R’
k}。
DB算法: MW方法总是为较早的片段分配较小的关系。这种策略可能引起两个问题。一是越后边的片段所含的关系越大,可能会使总的可用存储空间容纳不了整个片段内的所有内关系,导致增加更多片段,降低执行效率; 二是由于较早生成的片段包含小关系,存储空间得不到充分利用。DB算法可以避免这两个问题。
DB使用了惩罚和获利两个概念。惩罚定义为P=WP+WB,获利定义为B=(|S|+|R
1|+…+|R
k|)-|I
k|。DB算法的目的是为每个片段分配关系R
1,S,R
2,…,R
k,使得Y=P-wB最小,w是加权因子。设RS是给定的关系集合。展开Y式,可以得到如下的DB算法: ①从RS选择关系R作为R1,使得|R
1|最小,RS=RS-{R};②从RS选择关系R′作为S,使得|S|最小,RS=RS-{R′}:③对于2≤i≤k-1,从RS选择关系R′
i作为R
i,使得(C
2-C
3)|R
i|+(C
3-C
4)|I
i|最小,RS=RS-{(R′
i};④从RS选择关系R′
k作为R
k,使得(C
2-C
3)|R
k|+C
5|I
k|最小,RS=RS-{R′
k}。
3. SRD树的生成算法
算法输入为:查询中的关系集合RS,查询中关系个数q,系统中处理机个数N和每个处理机可用的存储器容量M。算法输出为查询的SRD树执行计划。算法的主要执行过程如下:
首先计算片段数
然后估算每个片段中关系数的上界
最后使用MW或DB算法由RS逐个构造片段S
i。
在线咨询
