X hits on this document

83 views

0 shares

0 downloads

0 comments

27 / 32

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.

Document info
Document views83
Page views83
Page last viewedFri Dec 09 17:41:04 UTC 2016
Pages32
Paragraphs351
Words1808

Comments