基于浓密树查询优化方法(数据库)

时间：2022-12-29 04:30:02 | 来源：信息时代

时间：2022-12-29 04:30:02 来源：信息时代

    基于浓密树查询优化方法 : 采用浓密树模型表示查询执行计划的一种优化方法。浓密树查询执行计划是一种更一般的查询执行计划表示模型。
浓密树是一个满足下列条件的树:
(1)叶结点表示关系。
(2)每个内结点既表示一个数据操作,也表示操作的结果关系,其子结点所对应的关系是该内结点的操作关系。
作为一种更一般的查询执行计划表示模型,浓密树在线性树查询执行计划中,多个连接操作被逐个地完成,即第一个第二个关系首先连接成为一个关系,其结果再与第三个关系连接成为一个关系,如此下去,直至最后一个关系被连接。在浓密树查询执行计划中,可以有多个关系对同时进行连接操作。
设Q是一个多连接查询。Q的所有浓密树查询执行计划构成了Q的浓密树查询执行计划空间。如果Q包括n个连接操作,可以从Q构造出[]×n!个浓密树。如果使用m种算法实现一个连接操作,则对于每个浓密树存在n^m种执行Q的策略或计划。于是,得到n^m[]×n!种按照浓密树方式执行Q的查询执行计划。显然,浓密树查询执行计划空间远比其他几种查询执行计划空间大。如果考虑到处理器和存储器的分配,浓密树的查询执行计划空间将会更大。
1.并行查询优化算法GP
GP算法是一种循环算法,每个循环产生浓密树查询执行计划的一个顺序执行段。GP算法也是一个贪心算法。在每次循环中,它都把尽可能多的连接操作放进一个顺序执行段,以获得最大的局部并行性。GP算法的输入是一个连接查询图G=(V,E),其中,V是结点集,每个结点对应一个关系,E是边集合,每条边表示一个连接操作,用关系对(R₁,R₂₎表示。输出为查询执行计划S。算法的主要思想如下: 先令S为空集合。如果参与连接的关系数目大于3(即结点数V>3),则调用函数select_rel_pairs(G)来选择一组并行执行的连接操作 Ψ并将其并入S中。然后算法根据Ψ中的操作对图G进行修改。对Ψ中每个连接操作(R₁,R₂₎,设R₁表示R₁与R₂的连接结果关系。算法从G中删除结点R₂并从E中删除满足条件{(R₁, R₂₎}∪ {(r,R₁)|∃(r,R₂₎∈E}的边。最后算法确定G中余下的3个关系的优化连接序列并将其并入S中。
算法GP中的select-rel-pairs(G)函数为一个顺序执行段选择尽可能多的可并行执行的连接操作。它的输入是一个连接查询图G,输出是可并行执行的一组连接操作。该函数循环调用minimum_cost(G,k,Ψ_k,C_k)函数,若Ψ_k不包含G中所有连接关系对,则执行minimum_cost(G,k+1,Ψ_k+1,C_k+1),直至(C_k+1>C_k)∨(Ψ_k+1包含所有G中的连接关系对)。上述循环从k=0开始,逐次递增直至满足循环结束条件。当循环结束后,若(C_k+1>C_k)则返回Ψ_k,否则返回Ψ_k+1。
函数minimum_cost(G,i,Ψ_i,C_k)是select_rel_pairs函数的核心部分。它以连接查询图G和需要并行运行的连接操作数i为输入,计算所有首先并行执行i个连接操作的查询执行计划的开销,以连接关系对集合的形式确定具有最小开销的查询执行计划并返回到Ψ_i,其开销返回到C_i,并为确定的查询执行计划的每个连接操作确定实现算法。
为了减少minimum cost函数的开销,进而减少优化算法的开销,将两个启发式规则,分别加入GP算法,得到启发式贪心算法GPT。
2. GPT算法
GPT是启发式贪心算法。一个浓密树查询执行计划的开销是其所有顺序执行段的开销的总和。考虑到每个多连接查询的所有可能的顺序执行段数和每个阶段内所有可能并行执行的连接操作数,浓密树查询执行计划空间是相当大的,搜索具有最小开销的浓密树查询执行计划的时间复杂性相当大。为了减少查询执行计划空间,算法GPT的启发式规则规定只在满足下列条件的浓密树查询执行计划中寻找优化查询执行计划: ①第一顺序执行段具有多个连接操作并行执行; ②其余顺序执行段仅包含一个连接操作。
这样,算法GPT搜索的查询执行计划空间(简称GPT查询执行计划空间)就小了很多。对于GPT查询执行计划空间中的每个查询执行计划P,如果P的第一顺序执行段有k个并行执行的连接操作,其余的顺序执行段仅执行一个连接操作,则其开销定义为:totalk(P)=par_join_cost(P_k)+seq_join_cost((P-R(P_k))∪join_result(P_k))。其中,P_k是P的第一顺序执行段,R(P_k)是查询执行计划P_k的关系集合,par_join_cost(P_k)是并行执行P_k中k个连接操作所需的开销,join_result(P_k)是P_k的结果关系,seq_join_cost(X)是逐个执行X中所有连接操作(每个连接操作可以由多个处理机并行执行)所需开销。GPT算法与GP算法的不同仅在于minimum_cost(G,k,Ψ_k,C_k)的不同。给定k,GPT算法的minimum_cost函数,首先枚举所有“第一顺序执行段包括k个连接操作、其余顺序执行段皆包括一个连接操作”的浓密树查询执行计划,计算每个计划的开销Totalk;然后选择具有最小Totalk的计划送Ψ_k,其开销送C_k。只需要用函数minimum_costT(G,k,Ψ_k,C_k)替代GP算法中的函数minimum_cost(G,k,Ψ_k,C_k)即可得到GPT。