FIT5202 · Data Processing for Big Data
Parallel Sort & Parallel Group-By
Week 4 closes the Volume theme of Monash FIT5202 with parallel external sorting and parallel aggregation. It builds from serial external sort-merge (counting passes with a limited buffer) to the five parallel sort algorithms — merge-all, binary-merge, the two redistribution variants and partitioned sort — and the three parallel group-by methods (traditional, two-phase, and redistribution). Counting external-sort passes and choosing a group-by method are recurring calculation and reasoning items in the exam.
What this chapter covers
- 01Serial external sort-merge: Pass 0 sort phase, then (B−1)-way merge passes with a B-page buffer
- 02Counting passes: #runs = ⌈file pages / buffer pages⌉, then repeatedly merge (B−1) at a time
- 03Parallel Merge-All Sort (local sort + one final K-way merge — the merge is a bottleneck)
- 04Parallel Binary-Merge Sort (pairwise pipelined merge)
- 05Parallel Redistribution Binary-Merge and Redistribution Merge-All (redistribute to spread the merge)
- 06Parallel Partitioned Sort (range-redistribute, then independent local sort — no merge needed; skew risk)
- 07Parallel Group-By: traditional (local then global), two-phase, and redistribution methods
- 08Cost and skew considerations across sort and aggregation
Counting passes in an external sort-merge
- +1Pass 0 (sort phase): read the file in chunks of 8 pages, sort each chunk in memory, write it back. Number of runs = ⌈150 / 8⌉ = ⌈18.75⌉ = 19 sorted runs (the last run is 150 − 18×8 = 6 pages).
- +1Merge fan-in: with B = 8 buffer pages, reserve 1 for output, leaving B − 1 = 7 input buffers, so each merge pass is a 7-way merge.
- +1Pass 1: 7-way merge the 19 runs → ⌈19 / 7⌉ = 3 runs.
- +1Pass 2: 7-way merge the 3 runs → ⌈3 / 7⌉ = 1 sorted file. Total = Pass 0 (sort) + Pass 1 + Pass 2 = 3 passes.
Key terms
- External sort-merge
- A sort for data that does not fit in memory: Pass 0 sorts buffer-sized runs, then repeated (B−1)-way merges combine runs until one sorted file remains.
- (B−1)-way merge
- With a B-page buffer, one page is the output buffer and B−1 are input buffers, so each merge pass combines up to B−1 runs at once.
- Parallel Merge-All Sort
- Each processor sorts locally, then a single processor performs one final K-way merge of all runs. Simple, but the final merge overloads one processor and the network.
- Parallel Partitioned Sort
- Range-redistribute records so each processor owns a value range, then each sorts independently. No merge is needed, but partitioning can introduce skew.
- Two-phase group-by
- Phase 1: each processor aggregates its local records by the group-by attribute. Phase 2: redistribute the partial results by that attribute and do a final aggregation per processor.
- Redistribution group-by
- Redistribute the RAW records to processors by the group-by attribute first, then each processor aggregates locally in one step. Moves more data than the two-phase method.
Parallel Sort & Parallel Group-By FAQ
How do I count external-sort passes quickly?
Start with the Pass-0 run count ⌈file pages / buffer pages⌉. Then repeatedly divide by the merge fan-in (B−1), rounding up, counting one pass each time until you reach a single run. Add the Pass-0 sort as one pass. Reserving a buffer page for output is the detail people forget.
What makes the redistribution sort algorithms better than merge-all?
Parallel Merge-All Sort funnels every run into one final K-way merge, so one processor and the network become the bottleneck. The redistribution variants spread the merging work across the whole pool of processors, giving genuine parallelism in the merge phase — at the cost of a redistribution step and possible skew.
When should I use the two-phase group-by instead of redistribution?
Use two-phase when local aggregation shrinks the data a lot (for example many records per group): you aggregate locally first, so only small partial results are shuffled. Use redistribution when groups are few or aggregation does not reduce much, so shuffling raw records is acceptable. The choice is again a network-cost trade-off.
Can AI help me with parallel sort and group-by?
Yes. Sia can count external-sort passes with you, compare the five parallel sort algorithms, and explain when two-phase beats redistribution for a group-by — step by step, checking your reasoning. It does not complete your graded work, and Monash academic-integrity rules apply.
Exam move
Make external-sort pass-counting automatic: ⌈file/buffer⌉ runs, then divide by (B−1) each pass, remembering to reserve one output buffer. Learn the five parallel sort algorithms as two families — without redistribution (merge-all, binary-merge) and with redistribution (the two redistribution variants and partitioned sort) — and be ready to say why redistribution spreads the merge. For group-by, be able to justify two-phase versus redistribution by data movement. Keep the Week-4 quiz warm on Moodle; it closes the Volume block that Test-style questions revisit.
Working through Parallel Sort & Parallel Group-By in FIT5202? Sia is AskSia’s AI Information Technology tutor — ask any FIT5202 Parallel Sort & Parallel Group-By question and get a clear, step-by-step explanation grounded in how FIT5202 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
