基于左线性树查询优化方法(数据库)

时间：2022-12-28 02:30:01 | 来源：信息时代

时间：2022-12-28 02:30:01 来源：信息时代

    基于左线性树查询优化方法 : 采用左线性树模型表示查询执行计划的一种优化方法。
1.左线性树查询优化算法
一个多连接查询的查询树是一棵树T=(V,E),其中,V是结点集合,每个内结点表示一个连接操作,同时也对应于该连接操作的结果关系;每个叶结点表示一个操作关系,同时也表示这个关系上的scan操作,scan操作是直接作用在关系上的投影和选择操作的组合; E是边集合,如V表示的连接操作的输入关系是结点V₁和V₂所对应的关系,则(V₁,V)、(V₂,V)∈E。在查询树T中,如果根到结点V的路径长为k,则称V为T的k级结点,如果从根到叶结点的最长路径的长度为n,则称这个查询树为n+1级查询树。
给定一棵查询树T,可得到查询树的数据相关图,用来描述查询树中各操作之间的固有数据依赖性,规定查询树的并行执行方式。
n+1级左线性树(left-deep-tree)是一个满足下列条件的查询树:
(1)具有2n+1个结点。
(2)每个内结点有且仅有两个子结点。
(3)每个内结点(n-1级内结点除外)的左子结点是一连接操作,右子结点是一关系。
(4)n-1级内结点的两个子结点皆为关系。
以下简称左线性树为LDT树。
设Q是一个具有n个连接操作的多连接查询。可以从Q构造出n!个等价的左线性树。如果使用m种算法实现一个连接操作,则对于每个左线性树存在mⁿ种执行Q的策略或计划。于是,得到mⁿn!种按照左线性树方式执行Q的查询执行计划。这些查询执行计划构成了基于左线性树的查询执行计划空间。基于左线性树的查询优化方法就是要从这个查询执行计划空间中选择具有最小或较小时间复杂性的计划,完成Q的执行。
2.基于并行Hash连接算法的LDT树优化查询实例
以下以并行Hash连接算法为例,说明LDT树与优化查询执行计划的关系和LDT树的复杂性模型。在Hash连接算法中,连接关系分为内关系和外关系。内关系用来建立Hash表。外关系用来搜索匹配由内关系建立的Hash表。Hash连接算法可以视为两个独立操作的组合。一个操作用来建立Hash表,简记作build。另一个操作用来搜索匹配Hash表,实现两个关系的连接,简记作probe。Hash连接算法可以分为两个顺序执行阶段:
(1) build阶段: 使用build操作,扫描内关系,建立Hash表。
(2) probe阶段:使用probe操作,扫描外关系,搜索匹配Hash表,完成连接处理。
给定一个多连接查询的一棵左线性树,它的数据操作相关图就确定了这个多连接查询的唯一的一个具有最高数据操作间并行性的查询执行计划。
3.存储空间限制问题的解决方法
基于左线性树查询优化方法存在存储空间限制问题。在build阶段,除了第一个Hash表以外,所有其他Hash表都是由中间结果关系建立的。这些中间结果关系的大小很难预测。即使能够预测这些中间结果的大小,在多用户环境下优化处理程序也很难预知查询执行计划执行时可用存储空间的大小。如果我们有足够的存储空间,问题很简单,只需为Hash表分配充分大的空间。如果我们只有有限的存储空间,Hash表大小的确定则成为影响并行查询执行计划性能的大问题。常用的解决方法有两种:
第一种方法由Graefe和Ward提出。这种方法的基本思想是在优化处理阶段产生多个查询执行计划,在运行阶段由运行系统根据当时的存储空间大小选择合适的查询执行计划执行。
第二种方法是运行系统根据可用存储空间大小的改变,动态地调整连接操作的Hash表的大小。通常,可以在每个连接操作的Hash表中记录连接操作中间结果的大小,并使用这个信息动态改变该操作的下一个连接操作Hash表的大小。