Advanced Programming I Lecture Notes

8 February 2007 • External Sorting

Outline

• Background

• Basic external sorting.

  • Balanced n-way sort merge.

• Balance vs. unbalance.

• Initial block distributions.

  • Polyphase sort merge.

Massive Sorting

• How would you sort lots of data?

  Using a pair of 5-year-old computers, two home DSL connections, 42 hours of computer time, and 5 man hours, I now had documents describing the reading preferences of 260,000 U.S. citizens.

  I downloaded all the files to an external 120 GB Firewire drive in UFS format. The raw data occupied little more than 5 GB.

  --- Data Mining 101: Finding Subversives with Amazon Wishlists
  Boing Boing, 5 January 2006

External Sorting

• How do you sort gigabytes of data?

  • This much data won't fit in physical store, and maybe not in virtual memory either.

• Most of the data's going to be stored on external devices.

  • Disk, tapes, perhaps the network.

• Sorting in such cases is called external sorting.

Is Sorting Necessary?

• Sorting makes practical massive data storage and retrieval applications.

  • Sorting improves indexing and access to data.

  • Sorting simplifies and speeds data maintenance.

• Without sorting, databases themselves would not be possible.

External Devices

• External devices have several complicating characteristics.

  • Read-write access to external devices is slow (at least x10 slower than RAM).

  • Access patterns may be restricted (sequential tape access).

• Successful external sorting algorithms must accommodate device characteristics.

  • Effective external sorts are device dependent.

Objectives

• Stick to general external sorting principles.

• Fast sorting by minimizing I-O.

• Assume devices are disk- and tape-like.

  • Faster random access from disks than from tapes.

  • Sustained sequential access is fastest in either case.

• Assume a primary-secondary virtual-memory hierarchy.

General Approach.

• Minimize device I-O by reading and writing big blocks.

  • Big blocks in the system can be manipulated by the sort.

• The data sloshes back and forth between input and output devices.

  • The sort works on data as it sluices through the system.

General Approach..

The complete data transfer from input to output is called a pass. External sort costs can be measured in passes. As well devices and the usual time and space measures.

Basic Idea

• Group data into blocks; data within a block is sorted.

• Merge two or more sorted blocks into a single sorted block.

• One pass through the data halves the number of blocks while doubling their size.

• Eventually you're left with a single, sorted block.

• This is known as the sort-merge strategy.

Basic Idea Illustrated

Implementation Details

• Assume 2n > 2 devices.

• The initial block size is determined by available primary storage.

• The initial block sort is an internal sort.

  • The initial data ordering makes the choice of an internal sort tricky.

• The remaining passes combine and sort blocks with a merge (as in merge sort).

Balanced n-way Sort Merge

• A sort-merge algorithm is

  • balanced if it uses n input and n output devices.

  • n-way if it merges n blocks into one block.

• The result is a balanced, n-way sort merge.

Analysis

• Assume a balanced, n-way sort merge.

• A file of R records can be split into S = R/B blocks, with each block holding (at most) B records.

  • B determined by primary-storage availability.

• Each n-way merge reduces M blocks to M/n blocks.

• Data are sorted in O(log_n S) passes.

The Initial Distribution

• The initial distribution pass blocks, sorts, and distributes the data.

• A simple initial distribution pass has problems:

  • The block size is limited by available storage.

    • Larger block sizes mean fewer passes.

  • It ignores any sorting that exists in the data.

    • Long ordered runs are broken up into blocks.

Exploiting Initial Order

• Use ordered-run length to determine block size.

  

• Buffer out-of-order data to maintain ordered runs.

  

Replacement Selection

• Respecting order when building runs is called replacement selection.

• The primary-storage sort buffer becomes a cache for out-of-order data.

  • The cache is flushed (a new block is started) when it's full of out-of-order data.

• Merging is tricker given the unequal block sizes.

Balance Problems

An n-way balanced sort merge wastes devices. n - 1 output devices are unused during a pass.

• More devices in motion means faster sorting.

Unbalancing The Sort

An unbalanced sort merge can use all but one device during a merge. But requires a distribute pass after each merge pass.

Improved Unbalancing

• Combine the merging and distribution passes.

  1. Merge the blocks until one of the input devices empties.

  2. Switch the output device to an input device.

  3. Switch the empty input device to the output device.

  4. Continue the merge.

• This strategy is called polyphase merging.

Polyphase Merge Illustrated

Properties

• For best results, polyphase merging requires

  • Nonuniform block sizes.

  • Nonuniform block distribution.

• Without nonuniformity, polyphase merging degenerates to merge-distributed passes.

• Replacement selection produces nonuniform block sizes.

Nonuniform Block Distribution

• Work backwards through a polyphase merge sort to determine initial block distributions.

  D1 D2 D3 D4 0 13 11 7 7 6 4 0 3 2 0 4 1 0 2 2 0 1 1 1 1 0 0 0

  A four device example. These numbers are known as generalized Fibonacci numbers. Dummy blocks make the numbers come out right.

Analysis

• Analyzing polyphase merge sort is complicated.

• In general, polyphase merging is better than balanced n-way merging when there's a small (> 8) number of devices.

  • But an external sort is written for a specific system and task, not "in general".

Points to Remember

• Changing position might change view points.

  • Mergesort isn't bad compared to disk I-O.

• Exploit all the data.

  • Replacement selection exploits sorted data.

• Performance and generality conflict.

  • Favor generality; high performance is hard and fragile.

References

• External Sorting, Chapter 13 in Algorithms by Robert Sedgewick, Addison-Wesley, 1983.

• Polyphase Merge Sorting by Tom Nelson in C/C++ Users Journal, July, 1997.

• External Sorting, Section 5.4 in The Art of Computer Programming, Vol. 3: Sorting and Searching by Donald Knuth, Addison-Wesley, 1973.