System issues in parallel sorting for database systems

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