PARALLEL EQUI-JOIN ALGORITHM for LARGE RELATIONAL DATA BASE Operations
Original Publication Date: 1987-Oct-01
Included in the Prior Art Database: 2005-Feb-02
A technique is described whereby an algorithm minimizes the processing time of large relational data base operations in multiprocessing computer systems. The algorithm follows straightforward hash-table base techniques for equi-join, by providing virtually unbounded parallelism. The algorithm assumes implementation on highly parallel processors which rely on three characteristics: 1. The input/output (I/O) operations are performed concurrently with the computations. 2. There is a large main memory which is accessible by all processors equally. 3. There is an adequate implementation of the synchronization primitive fetch-and-add. As in similar equi-join algorithms the performance of this concept assumes that the output relations are approximately the same size as the input relations.