04/25/2005

Yan Huang - CSCI5330 Database Implementation – Parallel Database

# Parallel Sort (Cont.)

Parallel External Sort-Merge

Assume the relation has already been partitioned among disks D0, ..., Dn-1 (in whatever manner).

Each processor Pi locally sorts the data on disk Di.

The sorted runs on each processor are then merged to get the final sorted output.

Parallelize the merging of sorted runs as follows:

The sorted partitions at each processor Pi are range-partitioned across the processors P0, ..., Pm-1.

Each processor Pi performs a merge on the streams as they are received, to get a single sorted run.

The sorted runs on processors P0,..., Pm-1 are concatenated to get the final result.