时间：2022-12-27 20:30:01 | 来源：信息时代
时间：2022-12-27 20:30:01 来源：信息时代
基于右线性树查询优化方法 : 采用右线性树的模型来表示查询执行计划的一种优化方法。
1.基于右线性树(RDT)的优化查询
n+1级右线性树(right-deep tree)是一个满足下列条件的查询树:
(1)具有2n+1个结点。
(2)每个内结点有且仅有两个子结点。
(3)每个内结点(n-1级内结点除外)的右子结点是一个连接操作,左子结点是一个关系。
(4) n-1级内结点的两个子结点皆为关系。简称右线性树为RDT树。
设Q是一个具有n个连接操作的多连接查询。可以从Q构造出n!个等价的右线性树。如果可以使用m种算法实现一个连接操作,则对于每个右线性树存在mn种执行Q的策略或计划。于是,得到mnn!种按照右线性树方式执行Q的查询执行计划。这些查询执行计划构成了Q的基于右线性树的查询执行计划空间。基于右线性树的查询优化方法就是要从这个查询执行计划空间中选择具有最小或较小时间复杂性的计划,完成Q的执行。
给定一个多连接查询的一棵右线性树,它的数据操作相关图确定了多连接查询的唯一一个具有最高并行性的执行计划(简称查询执行计划)。
2.右线性树查询执行计划的复杂性模型。
通常,右线性树查询采用复杂性模型实现,该模型是选择优化右线性树查询执行计划的关键。RDT树复杂性模型包括两部分。第一部分是build、probe和scan操作的复杂性(与左线性树相同);第二部分是整个查询执行计划的复杂性(由build、probe和scan操作的复杂性计算而得到,其中包括工作量和并行执行时间)。后者是整个右线性树查询执行计划的复杂性的测度。设给定一个多连接查询Q,则以下为基于右线性树的查询优化算法的主要实现步骤:
(1)使用枚举方法搜索Q的RDT树空间,选择具有最小响应时间的优化RDT树。
(2)从选定的优化RDT树产生数据操作相关图。
(3) 由数据操作相关图产生具有最高数据操作间并行性的RDT树查询执行计划。
(4)按照优化RDT树各结点的工作量的比例为每个结点分配处理机。
(5)调度处理机执行查询执行计划。
3.存储空间限制问题的解决方法
基于右线性树查询优化算法也存在主存储器空间的限制问题。其解决方法有:
(1)静态右线性树调度方法: 这种方法把右线性树分成多个不相交的可执行片段,使得每个片段的存储要求不超过可用的存储空间。使用右线性树和数据操作相关图方法为每个片段确定具有最高数据操作间并行性的执行计划。然后顺序地执行各个片段。这种方法需要把每个片段的执行结果暂存到磁盘上,作为下一个片段执行的一个输入关系。
(2)HYBRID调度方法:该方法的基本思想是在build阶段,每个连接关系被分成两部分,一部分进入内存,建立Hash表,另一部分以后处理;在probe阶段,每个连接操作的结果也被分成两部分,一部分直接用来进行下一个连接操作的probe处理,另一部分以后处理。
(3) 自底向上的动态调度方法: 与LDT树解决方法类似。
关键词：方法,数据
在线咨询
