Parallel sort and join for high speed database machine operations
Mamoru Maekawa · 1981
This paper proposes a parallel joining and sorting algorithm that completes in about log N steps for N records. The algorithm is intended for large database systems. The algorithm and its required processor interconnection are simple and realistic. Thus, a performance improvement of three to four orders of magnitude can be realistically expected by applying this algorithm to database machines. Analysis is primarily made by simulations.