System issues in parallel sorting for database systems

Abstract

An external parallel merge-sort and sort-merge join on tightly coupled processors is considered. The issue of whether significant speedup can be achieved with good CPU efficiency is addressed . A pure sort query and a five-relation join query using a sort-merge-join algorithm are examined. It is found that the external sort is readily parallelizable. In the absence of skew, a speedup linear in the number of tightly coupled processors can be obtained. However, it is shown that skew can reduce the speedup significantly. An examination is made of how important types of skew can be handled to yield close to linear speedup. The effect on the speedup and CPU efficiency of the database size, memory constraints, CPU MIPS, query selectivity, I/O striping, and skew is shown.