Development of Parallel Relational Database Machine Using Hash and Sort

本文的研究目标是开发一种能够在大型数据库访问拥塞的情况下保持高性能的并行关系数据库机器。机器设计基于数据流模型，使我们能够沿着数据流执行操作。加上下列结果，我们认为我们的目标已完全实现。结果可以从数据流处理、生成和控制的角度进行总结：（数据流处理）为了实现数据流模型，我们需要对每个关系代数运算使用线性时间算法。我们的方法是基于哈希的聚类效应和数据的线性时间排序，后者由硬件排序器实现。原型排序器（第二个版本）可以以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.