Research on Optimizatiion for Complex Query in Parallel Databases

近年来，无共享体系结构正在成为商业高度并行机的标准，如SP-2、AP-1000、Paragon等。因此，已经有许多商业并行数据库系统在这些并行机或并行环境上实现。为了利用操作间的并行性，已经有相当多的工作集中于为并行数据库系统开发高效的多路连接处理调度器。从当今大型数据库系统在无共享系统上的观点来看，多路连接的流水线处理对于通过网络平稳地传输大量数据是很重要的。因此，无共享体系结构上的并行数据库处理在查询编译时必须考虑网络带宽，而目前已有的研究大多假设共享一切体系结构，其中忽略了网络通信成本。因此，在无共享环境…中进行多路连接是必要的在这项研究中，我们考虑了无共享环境下的并行多路连接处理，并展示了如何在有限的网络带宽下针对给定的资源环境高效地构造多路连接调度。虽然如今通信带宽大幅增加，但磁盘阵列的出现也增加了I/O数据流的带宽。这意味着当加入操作的数量不是那么少时，网络很容易饱和。我们的算法首先生成子树种子，在流水线处理中完全消耗网络带宽。然后，将这些子树种子相互组合，最终生成一棵最优查询树。详细描述了生成平衡I/O访问和网络传输且占用较少内存的短树的约束条件。利用引入的代价公式对所提出的多路连接计划生成算法进行了评估，并与以往的工作进行了比较。从评价结果来看，该方法不仅比已有的左深树、右深树和分割右深树等算法的质量要好，而且我们的算法的质量并没有相对恶化。较少

Recently, shared-nothing architecture is becoming the standard for commercial highly parallel machines such a SP-2, AP-1000, PARAGON etc. Thus, there have been a number of commercial parallel database systems implemented on these parallel machines or parallel environment. In order to exploit an inter-operation parallelism, there has been considerable effort focused on developing efficient multi-way join processing schedulers for parallel database systems. From the point of view of large database systems on a shared-nothing system these days, it is important for pipeline processing of multi-way join to transfer large amount of data through the network smoothly. So, parallel database processing on a shared-nothing architecture has to take the network bandwidth into account for query compilation, while most the researches so far done assumed shared everything architecture where network communication cost is neglected. Thus, it is necessary for multi-way joins in shared-nothing environment … More to exploit a new optimization algorithm considering the overlap of the I/O accesses and the network transfers.In this research, we consider parallel multi-way join processing in a shared-nothing environment and show how multi-way join scheduling can be constructed efficiently for a given resource environment under finite network bandwidth. Although the communication bandwidth increases significantly these days, the advent of the disk array also increases the bandwidth of I/O data stream. This means the network could easily saturate when the number of join operation is not so small. Our algorithm first generates sub-tree seeds which fully consumes the network bandwidth in a pipeline processing. Then, these sub-tree seeds are combined each other to finally produce an optimal query tree. The restriction conditions for generating a short-tree which balances the I/O accesses and the network transfers and uses less memory are described in detail. The proposed algorithm for generating the multi-way join plan is evaluated in comparison with former work by using the introduced cost formula. From the evaluation results, not only is the quality of the proposed method better than previously presented algorithms such as left-deep, right-deep and segmented right-deep trees, but the quality of our algorithm does not deteriorate comparatively. Less