权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Research on Optimizatiion for Complex Query in Parallel Databases

并行数据库中复杂查询的优化研究

基本信息

批准号：
07680336
负责人：
NAKANO Miyuki
金额：
$ 1.54万
依托单位：
University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
1995
资助国家：
日本
起止时间：
1995 至 1996
项目状态：
已结题

项目摘要

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

最近，无共享架构正在成为商用高度并行机器（如SP-2、AP-1000、PARAGON等）的标准。因此，在这些并行机器或并行环境上实现了许多商业并行数据库系统。为了利用操作间的并行性，在为并行数据库系统开发高效的多路连接处理调度器方面已经付出了相当大的努力。从目前无共享系统上的大型数据库系统来看，多路连接的流水线处理对于保证大量数据在网络上的顺利传输具有重要意义。因此，无共享架构下的并行数据库处理在查询编译时必须考虑网络带宽，而目前的研究大多采用无共享架构，忽略了网络通信成本。因此，对于无共享环境下的多路连接，有必要开发一种考虑I/O访问和网络传输重叠的优化算法。本文研究了无共享环境下的并行多路连接处理，并给出了在有限网络带宽下，如何有效地构造给定资源环境下的多路连接调度。虽然现在通信带宽显著增加，但磁盘阵列的出现也增加了I/O数据流的带宽。这意味着当连接操作的数量不是很小时，网络很容易饱和。该算法首先生成子树种子，在流水线处理中充分消耗网络带宽。然后，将这些子树种子相互组合，最终生成最优查询树。详细描述了生成平衡I/O访问和网络传输、占用较少内存的短树的限制条件。利用引入的代价公式，对所提出的多路连接计划生成算法进行了评价。从评价结果来看，本文方法的质量不仅优于先前提出的左深树、右深树和分割右深树等算法，而且算法的质量也没有相对下降。少