时间：2022-10-31 14:30:01 | 来源：信息时代
时间：2022-10-31 14:30:01 来源：信息时代
两段式并行查询优化方法 : 一种高效率的并行算法,该算法分两阶段执行:第一阶段使用传统的查询优化方法产生高效率的顺序查询执行计划。第二阶段则再将其并行化。第一阶段产生的顺序查询执行计划,产生一个高效率的并行查询执行计划。两阶段算法的主要问题是: 第一阶段产生的顺序查询执行计划可能具有很高的固有顺序性,但会使第二阶段产生的并行查询执行计划的并行性降低。
1.最小执行时间方法
该方法是以最小化查询执行时间为目标的一种两段式并行查询优化方法。以多连接查询为例,假定每个连接操作都由merge_sort连接算法实现。设R和S是两个关系。使用merge_sort连接算法在单处理机系统中完成R和S的连接操作所需时间开销定义为cost(R,S)=|R|+|S|+|R⋈S|, 其中,R⋈S表示R和S的连接,|R|、|S|和|R⋈S|分别表示关系R、S和R⋈S结果的大小。 两个阶段分述如下:
(1)顺序查询执行计划的产生算法: 有两个高效率顺序查询执行计划的产生算法:
①贪心算法SG:设ψ是多连接查询Q中所有关系的集合。SG算法的基本思想是: 首先从ψ中选择两个关系R和S,使得Cost(R,S)最小; 然后,令ψ={R⋈S}∪(ψ-{R,S}), 即用关系R⋈S替代R和S; 再从ψ中选择R’≠R⋈S, 使得Cost(R⋈S,R′)最小; 这个过程循环反复进行直至ψ为空。
②启发式算法SH:SG算法只能产生线性树查询执行计划。SH能够产生更一般的浓密树查询执行计划。SH算法的思想来自于计算n个数的huffman算法。设ψ是多连接查询Q中所有关系的集合。SH算法的基本思想是:首先从ψ中选择两个关系R和S, 使得cost(R,S)最小; 然后令ψ={R⋈S}∪(ψ-{R, S}), 即用关系R⋈S替代R和S; 再从ψ中选择R′和S″,使得Cost(R′,S′)最小; 这个过程循环反复,直至ψ为空。
(2)顺序查询执行计划的并行化: 顺序查询执行计划并行化的一种方法是为执行计划中每个连接操作分配多个处理机,既实现单个连接操作的并行执行,也实现多个连接操作的并行执行。有两类为连接操作分配处理机的方法。
① 自底向上的分配方法:在一定的处理机数量范围内,一个连接操作的执行时间随着执行这个操作的处理机个数的增加而减少。当执行这个连接操作的处理机个数达到某个值后,由于该连接操作可开发的并行性的限制和通信开销的迅速增长,继续增加执行该操作的处理机数将增加这个操作的执行时间。这个值被称为连接操作的最小时间点。在进行处理机分配时,必须充分考虑最小时间点的影响。以下是四种处理机分配策略:
顺序执行策略(SE): 逐个顺序地执行查询执行计划中的每个连接操作,每个连接操作由所有处理机并行执行。这种方法完全丢弃了多连接操作间的并行性。
固定分配方法(FS): 为查询执行计划中的每个连接操作分配固定数量的处理机,发挥多连接操作间的并行性。
最小时间点方法(MT): 按照最小时间点Pm为每个连接操作分配处理机。由于数据相关性和处理机空闲的影响,这种方法仅能最小化单个连接操作的执行时间,不一定能最优化整个查询的有效性。
时间与有效性折中方法(TE): 为查询执行计划中每个连接操作分配x个处理机,其中,x∈(0,Pm]。
把任一个处理机分配策略与任一顺序查询执行计划生成算法结合,可得到完整的多连接查询的启发式优化并行执行算法。
② 自顶向下的处理机分配方法:该方法的核心是一个“同步执行规则”。同步执行规则定义为:处理机的分配要保证任一个连接操作的两个操作关系必须在近似相等的时间点被同时产生。
设并行计算系统的处理机个数为P。由于顺序查询执行计划树的根结点r对应于最后执行的连接操作,自顶向下的处理机分配方法首先把所有P个处理机全部分配给r。然后,把根结点r分得的P个处理机划分为两组L和R。L分配给r的左子结点,R分配给r的右子结点。L和R中的处理机数需要根据r的两个子树的工作量来确定,使得r的两个子树在近似相等的时间点产生r的两个操作关系。上述过程自顶向下反复进行,直至查询执行计划树的所有内结点(即所有连接操作)都被分配了处理机。算法TD与任何一个产生顺序查询执行计划的算法相结合即可得到一个完整的多连接查询的优化处理算法。
在线咨询
