Yan Huang - CSCI5330 Database Implementation – Parallel Database
Choose processors P0, ..., Pm, where m n -1 to do sorting.
Create range-partition vector with m entries, on the sorting attributes
Redistribute the relation using range partitioning
all tuples that lie in the ith range are sent to processor Pi
Pi stores the tuples it received temporarily on disk Di.
This step requires I/O and communication overhead.
Each processor Pi sorts its partition of the relation locally.
Each processors executes same operation (sort) in parallel with other processors, without any interaction with the others (data parallelism).
Final merge operation is trivial