Systolic arrays for rapid processing of simple database transactions
Philip L. Lehman · 1984
This dissertation is an exploration of a method of using the computational power available from Very Large Scale Integration (VLSI) to solve an important database management problem. In many of the largest commercial database systems, most types of transactions have two characteristics in common: simplicity (for example, cashing a check in a banking database requires very few database operations) and high frequency of execution (a bank may need to execute thousands of similar simple transactions per second.) A systolic array design is proposed for rapid execution of simple relational database transactions. The simple query array is intended for use as a component of a high-performance relational database machine. Transaction fragments from a batch of similar transactions are executed simultaneously by passing a database relation through the array. This scheme produces a substantial reduction in the amount of input-output necessary to process the transactions. Several simple query arrays are arranged as stages of a pipeline to allow concurrent processing of several multi-relation transaction batches. Consistency problems may arise from concurrent transaction execution. The problem of finding the optimal consistent schedule for the simple query pipeline is NP-complete. However, several fast heuristics produce near-optimal schedules, and exhibit a tradeoff between work performed (by the scheduler) and resulting schedule quality (throughput). Variations on the basic architecture are also explored; these include relations of different sizes, asynchronous stages, and buffered stages. These enhancements produce a slight improvement over the initial design. A basic architecture is proposed that employs the simple query pipeline. A projection of the performance of this design shows a large improvement over the best currently-available conventional systems for this task. The scheme described uses tremendous parallelism and reduced input-output requirements to achieve high throughput for programmable simple database transactions, while maintaining database consistency. From a database perspective, this is the first use of special purpose hardware to tackle the specific problems of many commercial databases. From a systolic perspective, this is one of the first designs used for simultaneous execution of a large number of small (but useful) tasks--instead of one large, computation-intensive problem--resulting in far more parallelism than is obtainable from a conventional multiprocessor.