External-Memory Algorithms

External-memory algorithms organize work so data movement between memory and storage remains manageable. When data exceeds the available working memory, a method with attractive CPU complexity can still spend most of its time making inefficient accesses or repeatedly moving the same records.

Start by counting the data representation and the memory actually available to the operation. Then choose an access pattern that moves useful blocks and bounds intermediate state. Streaming input is helpful only if the rest of the program does not quietly accumulate the entire result.

TL;DR

Quick Example

This complete Python illustration creates three sorted temporary runs of at most four integers and merges their file streams. It uses only its own temporary directory.

The program preserves duplicates and negative values. Input and final output both fit RAM; list(heapq.merge(...)) intentionally materializes the tiny result for its assertion. This is not a larger-than-RAM test, a bounded production sorter, a block-I/O measurement, or a durable recovery implementation.

Core Concepts

I/O cost model

External-memory analysis separates internal memory from storage and counts block transfers. State the modeled memory M, block size B, data size N, and whether those quantities count records or bytes. Vitter’s source explains the model and locality motivation. External-memory introduction

Run generation and merging

External merge sorting forms memory-sized sorted runs and merges bounded groups through input/output buffers. Fan-in and pass count depend on the available memory and buffering assumptions. Vitter, external sorting chapter

Operating environment

The abstract I/O model is an analysis tool. Filesystem buffering, device behavior, shared load, compression, and record representation can change observed performance. Treat those as measured conditions rather than hiding them inside a theoretical bound.

Walk through a bounded merge plan

Imagine a fictional input of 64 equal-sized records, a run-generation capacity of 16 records, and a merge fan-in of three. Run generation produces four initial runs. One merge pass can reduce them to two runs, and another can produce one ordered result. This is illustrative planning arithmetic, not a device benchmark.

The fan-in needs memory for useful input buffers, an output buffer, merge bookkeeping, and runtime overhead. Do not set it equal to every available file descriptor or every nominal memory block without reserving the rest of the process’s needs.

Each full materialized merge pass reads and writes the participating records. If the next stage can consume the final merge as a stream, a design may avoid writing a final intermediate file. State whether that changes durability, recovery, or downstream replay requirements.

For variable-length records, a count of 16 records is not a safe memory budget. Bound bytes, account for the in-memory representation and sorting overhead, and define how to handle a single record larger than the intended buffer.

The example opens all three runs because the fixture is tiny. A large run set needs multiple bounded passes and a manifest describing the participating files. Opening every run at once simply moves the capacity failure from RAM to descriptors or buffering.

Match operations to access patterns

This matrix is a starting point, not a cost model: scans and indexed lookups vary widely in cost. The shape of the data and the storage system determine whether locality actually helps the workload.

Inspect skew. A partitioning design can fit the average partition in memory while one popular key creates a much larger partition. Define fallback spilling or repartitioning instead of assuming uniform input.

Keep comparison semantics stable across runs. Collation, numeric parsing, null ordering, and tie behavior must agree when records are sorted and merged. If output needs stable ordering among equal keys, carry an appropriate original sequence or deterministic tie key.

Distinguish compression’s storage savings from its CPU and access effects. A smaller file can reduce bytes moved while making random access or restart more complicated. Measure the combined operation under the actual format.

Plan scratch space, interruption, and acceptance

Estimate the peak simultaneous input, run, merge, output, and recovery artifacts before running on a large dataset. A sorter can be logically correct and still fail after exhausting scratch space halfway through a pass.

Use an owned working location and a manifest or equivalent recovery record for production jobs. Associate intermediate files with a job identity and input revision. Do not discover runs by loosely globbing a shared directory containing unrelated or stale files.

Decide which intermediate result is complete and reusable after interruption. Close and validate outputs under the appropriate durability procedure before treating them as accepted input to the next pass. Atomic naming alone does not establish that data reached durable storage.

Verify ordering, count, and content preservation with a suitable method. For a bounded fixture, compare with an in-memory reference. For large production data, choose checks that fit the required integrity and performance model, and review their limitations.

Report measured resident memory, scratch use, records/bytes, storage path, cache conditions, and elapsed time when making performance claims. A tiny temporary-file example proves a mechanism; it does not prove that the implementation remains bounded at scale.

Best Practices

Budget actual bytes

Account for record expansion, sort workspace, buffers, and runtime overhead. Test oversized records and skew.

Bound every stage

Keep fan-in, open files, queued output, and intermediate state within declared limits. Verify downstream backpressure.

Verify recovery and preservation

Test interruption and restart in an approved environment. Accept output only after the required ordering and content checks.

Common Mistakes

Bad: Reading through an iterator makes the whole program streaming.

Correct: Check sorting, buffering, downstream queues, and result materialization as well.

Bad: Merge every run at once for fewer passes.

Correct: Choose bounded fan-in from memory, buffers, descriptors, and operating overhead.

Bad: The theoretical I/O bound predicts elapsed time exactly.

Correct: Use it to compare designs, then measure the actual workload and storage environment.

FAQ

Did the example process data larger than RAM?

No. It demonstrates real run files and merging with deliberately tiny data and a materialized result.

Why keep an output buffer?

The merge needs a controlled output path as well as input streams. Its exact buffering and durability policy depend on the implementation.

Is external sorting always the right approach?

No. Match scanning, indexing, partitioning, or sorting to the operation and measured constraints.

Related Topics

References