X hits on this document

111 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 views111
Page views111
Page last viewedMon Jan 23 19:13:25 UTC 2017
Pages32
Paragraphs351
Words1808

Comments