Development of Parallel Relational Database Machine Using Hash and Sort

本研究的目的是开发一种并行关系数据库机器，即使在大型数据库访问拥塞的情况下也能保持高性能。机器设计基于数据流模型，该模型使我们能够沿着数据流执行操作。结合以下结果，我们相信我们的目标完全实现了。结果可以从数据流处理、生成和控制的角度来总结：1.(数据流处理)为了实现数据流模型，我们需要为每一次关系代数运算提供线性时间算法。我们的方法是基于数据的散列和线性时间排序的聚类效应，后者是由硬件排序器实现的。原型分类器(第二版)可以以3MB/秒的速率对数据进行分类，并且对记录长度、记录数量和要分类的数据流数量没有限制。(数据流生成)在我们的设计中，性能由最初从磁盘生成的数据流决定。我们开发了自适应多维聚类技术，并对其详细性能进行了评估。实验结果表明，该技术可以大大减少页面的平均访问次数，从而高效地生成初始数据流。(数据流控制)在我们的机器中，数据流是自治的，因此它们可以在没有任何集中控制的情况下流经机器。因此，机器的控制器比其他控制器的负担要小得多：只有在数据流要开始或结束时才会调用它。我们的设计利用数据流控制来确定操作执行的顺序。性能评估表明，该算法控制开销小，易于实现。

The objective of this research was to develop a parallel relational database machine which can keep the high performance even for congested accesses to the large database. The machine design is based on the data stream model which enables us to execute operations along the stream of data. Together with the following results, we believe that our objective was fully achieved. The results can be summarized from the view point of data stream processing, generation, and control:1. (data stream processing) To implement the data stream model, we need the linear time algorithms for every relational algebra operation. Our approach is based on the clustering effect of hash and linear time sorting of data, the latter of which is realized by the hardware sorter. The prototype sorter (the second version) can sort data at the rate of 3MB/sec, and exposes no limitation on the length of record, the number of records, and the number of data streams to be sorted.2. (data stream generation) In our design, the performance is dominated by the initial generation of data streams from disks. We developed the adaptive multidimensional clustering technique and evaluated its detailed performance. It was shown that the technique can reduce the average number of page accesses largely, hence can generate the initial data streams quite efficiently.3. (data stream control) In our machine, the data streams are made so autonomous that they can flow through the machine without any centralized control. As a result, the controller of the machine is much less burdened than others: it is invoked only when the data streaming is to start or end. Our design utilizes the data flow control to determine the order of operation executions. Its performance evaluation shows that the control overhead is very little and that it is easy to implement.