The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Search and Sorting on Large Data Volumes

Next ►
►

Third case study. In 06-01 the challenge was chaining algorithms; in 06-02, modeling a new domain; here the challenge is size: Rutalia has been operating for years and has accumulated 200 million historical delivery records (~40 GB) that management wants to consolidate and analyze. The search and sorting algorithms from module 4 are still the foundation, but a silent assumption breaks: that the data fits in RAM and that accessing one element costs the same as any other. When that stops being true, the variable that governs the design is no longer the number of comparisons but the number of disk accesses, and from that change of currency come external sorting, B-trees, MapReduce and the probabilistic structures we will see here.

Contents

  1. When the data does not fit in RAM: the memory hierarchy
  2. External sorting: sorted runs + k-way merge
  3. Indexes: why databases do not do binary search
  4. MapReduce: the divide-group-combine paradigm
  5. Probabilistic structures: the Bloom filter and its cousins
  6. Top-K in streaming: the 10 postal codes with the most deliveries
  7. The full case: the plan for the 200 million records

When the data does not fit in RAM: the memory hierarchy

All the complexity analysis in this course (01-01, 01-02) counted operations assuming a uniform memory access cost. The reality of hardware is a hierarchy with jumps of several orders of magnitude:

Level Approximate latency On a human scale (1 ns = 1 s)
L1 cache ~1 ns 1 second
RAM ~100 ns ~2 minutes
SSD (random read) ~100 µs ~28 hours
Magnetic disk (seek) ~10 ms ~4 months
Network between data centers ~50-150 ms years

Two design consequences that explain everything that follows:

  • One disk access is worth ~1,000-100,000 RAM accesses. An algorithm with more comparisons but fewer disk reads wins. The relevant complexity is now measured in I/O operations (the external memory model).
  • Sequential disk access is enormously cheaper than random access (the disk/SSD serves contiguous blocks at high speed). Good external algorithms read and write in sequential streams of large blocks, never hopping from record to record.

With this new currency, let us revisit the two operations from module 4.

External sorting: sorted runs + k-way merge

How do you sort 40 GB with 1 GB of RAM? The classic algorithm, external merge sort, is mergesort (04-02) rethought to minimize I/O, and it reuses two pieces you already have:

  1. Phase 1 — generate runs: read the file in chunks that fit in RAM, sort each chunk in memory (Timsort, 04-02) and write it out as an already-sorted temporary file (a run). With 1 GB of RAM and 40 GB of data: 40 runs.
  2. Phase 2 — k-way merge: merge the 40 runs in a single pass with a heap (01-04), exactly the k-way merge you did with heapq.merge in 04-02: at any moment you only need the "front" of each run in RAM.

Each phase reads and writes the data once: 2 full passes ≈ 4·N/B I/O operations (N data, B block size), versus the ~N·log₂N random reads of a naive quicksort over disk, which would be thousands of times slower. Let us simulate it with real files at small scale:

import heapq
import os
import random
import tempfile

random.seed(3)
workdir = tempfile.mkdtemp()

# --- Data: 100,000 "delivery records" (num_id;minutes), unsorted ---
raw_file = os.path.join(workdir, "deliveries.txt")
with open(raw_file, "w") as f:
    for i in random.sample(range(100_000), 100_000):
        f.write(f"{i};{random.randint(5, 120)}\n")

MEMORY = 10_000   # records that "fit in RAM" (simulated)

# --- Phase 1: generate sorted runs ---
def generate_runs(filename, memory):
    runs = []
    with open(filename) as f:
        while True:
            chunk = [line for _, line in zip(range(memory), f)]
            if not chunk:
                break
            chunk.sort(key=lambda l: int(l.split(";")[0]))   # Timsort, in RAM
            path = os.path.join(workdir, f"run_{len(runs)}.txt")
            with open(path, "w") as out:
                out.writelines(chunk)
            runs.append(path)
    return runs

# --- Phase 2: k-way merge with a heap ---
def merge_runs(runs, output):
    files = [open(r) for r in runs]
    # Each run is wrapped in a GENERATOR of (key, line):
    # only one line per run lives in RAM at a time (the front of the heap)
    def keyed(f):
        for line in f:
            yield (int(line.split(";")[0]), line)
    with open(output, "w") as out:
        for _, line in heapq.merge(*(keyed(f) for f in files)):
            out.write(line)
    for f in files:
        f.close()

runs = generate_runs(raw_file, MEMORY)
print(f"Generated {len(runs)} runs of <= {MEMORY} records")
sorted_file = os.path.join(workdir, "deliveries_sorted.txt")
merge_runs(runs, sorted_file)

# Verification: the final file is sorted
with open(sorted_file) as f:
    keys = [int(l.split(";")[0]) for l in f]
print("Sorted?", all(keys[i] <= keys[i+1] for i in range(len(keys)-1)))

Note that keyed(f) is a generator, not a list: if you materialized each run with list(f) you would put all the data back into RAM and the algorithm would lose its reason for existing. The "everything as streams" discipline is half the job in external algorithms.

Fine points of the real algorithm:

  • What if there are too many runs? With RAM for k run fronts, the merge admits k streams. If more than k runs come out, you merge in several rounds (merges of k at a time): the number of passes is ⌈log_k(number of runs)⌉ — logarithmic with a huge base (k is usually hundreds or thousands), so in practice 2-3 passes are enough for almost any size.
  • This is, literally, the algorithm databases run for an ORDER BY that does not fit in memory, and the centerpiece of the shuffle phase of MapReduce (next section).

Indexes: why databases do not do binary search

You now have the data sorted on disk. Look up a record with binary search (04-01)? Correct in comparisons (log₂ of 200 million ≈ 28), disastrous in I/O: 28 random disk reads, each at an unpredictable position. And worse: keeping a sorted array on disk under daily insertions is unworkable (shifting millions of records per insertion, as you saw when analyzing array insertion in 01-02).

The database solution is the B-tree (and its B+ variant): the on-disk generalization of the binary search tree you met in 01-04.

  • Each node occupies one disk block (4-16 KB) and holds hundreds of sorted keys, not one.
  • A node with m keys has m+1 children: the tree is extremely shallow. With a branching factor of ~500, 200 million keys fit in height 3-4.
  • Searching = reading 3-4 blocks (and the root and second level live cached in RAM: often 1-2 actual reads). Inside each block you do run binary search (04-01) — but that is CPU, which is free compared with the I/O.
  • The tree stays balanced by construction (nodes split when they fill up), with insertions and deletions in O(log n) blocks.
flowchart TD
    R["root: [P-08M | P-95M]<br>1 block, in RAM"] --> A["[P-01M ... P-07M]"]
    R --> B["[P-09M ... P-90M]"]
    R --> C["[P-96M ... P-200M]"]
    B --> H1["leaf: records<br>P-42,000,000 ..."]
    B --> H2["leaf: ..."]
    B --> H3["leaf: ..."]

The full comparison, connecting with 01-04 and 04-01:

Structure Exact search Range search Insertions I/O cost (search)
Sorted array + binary search (04-01) O(log n) excellent O(n) — unworkable ~28 random reads
Balanced binary tree (01-04) O(log n) good O(log n) ~28 (one node per wasted block)
B/B+ tree O(log n) excellent (linked leaves) O(log n) 3-4 reads, 1-2 in practice
Hash index (01-04) O(1) no range support O(1) amortized 1-2 reads

Decision rule: pure equality lookups at maximum speed → hash; ranges, sorting, prefixes (WHERE delivery_date BETWEEN ...) → B-tree. That is why the default index in almost every relational database is a B+; hash indexes exist but are the special case. It is the same hash-vs-tree dilemma from 01-04, now settled by the I/O currency and the query pattern.

MapReduce: the divide-group-combine paradigm

When not even one disk is enough — or one machine takes too long — the work is spread across many. MapReduce (Google, 2004) imposed a simple discipline: if you express your computation as two pure functions, the framework takes care of distributing, retrying failures and moving data.

  • map(record) → list of (key, value): applied to each record in parallel, on the machine where the data already lives.
  • shuffle (done by the framework): groups all the values of the same key — internally, a distributed external sort like the one in section 2.
  • reduce(key, values) → result: combines the values of each key, in parallel per key.

The "hello world" is counting words; our case is identical with a different key: total deliveries and average delay per zone over the history. We simulate the paradigm in Python to see the data flow (the real value shows up with hundreds of machines, but the contract is this one):

from collections import defaultdict

# Fictional historical records: (order_id, zone, delivery_minutes)
records = [
    ("P-001", "ALM", 22), ("P-002", "CEN", 35), ("P-003", "ALM", 41),
    ("P-004", "UNI", 18), ("P-005", "CEN", 52), ("P-006", "ALM", 30),
]   # ... imagine 200 million of these

def map_fn(record):
    _, zone, minutes = record
    return [(zone, minutes)]                 # key = zone

def reduce_fn(zone, values):
    return {"zone": zone, "deliveries": len(values),
            "avg_min": sum(values) / len(values)}

# --- What the framework would do ---
# 1) map in parallel over chunks of the file
intermediate = [pair for r in records for pair in map_fn(r)]
# 2) shuffle: group by key (= distributed external sort)
groups = defaultdict(list)
for key, value in intermediate:
    groups[key].append(value)
# 3) reduce in parallel per key
result = [reduce_fn(z, vs) for z, vs in groups.items()]
print(result)

Why this scales and what it demands in return:

  • It scales because map and reduce are independent per record/key: adding machines divides the time almost linearly, and the only point of contact (the shuffle) is an external sort — a problem already solved.
  • It demands that the functions be pure and the reduce operations associative in practice (able to combine partials). Counting, summing, max, means (as sum+count): perfect. Algorithms with tightly coupled global state: a bad fit.
  • The modern heir is Apache Spark, which generalizes the model (chains of map/filter/reduce/join keeping data in RAM between steps) — but the divide-group-combine mental model is the same, and knowing how to recognize when your computation admits it is the transferable skill.

As always in this course: divide and conquer (01-03, 04-02) was never just a recursion trick; at this scale it is an architecture.

Probabilistic structures: the Bloom filter and its cousins

Sometimes the question does not demand exactness. "Have I already seen this order id?" over 200 million ids demands a set of several GB… unless you accept a small, controlled probability of a false positive. The Bloom filter offers exactly that deal: ~10 bits of memory per element (independent of the size of the ids!) in exchange for "yes, I have seen it" occasionally being a lie — "no, I have not seen it" is always the truth.

Mechanics: an array of m bits and k hash functions (the tool from 01-04). Insert x: set the k bits hash_i(x) % m to 1. Query x: if any of its k bits is 0, it is definitely not there; if all k are 1, it is probably there (other elements may have set them — that is the false positive).

import hashlib

class BloomFilter:
    def __init__(self, m_bits, k_hashes):
        self.m, self.k = m_bits, k_hashes
        self.bits = bytearray(m_bits // 8 + 1)

    def _positions(self, item):
        # k hashes from a single digest (the double-hashing technique)
        d = hashlib.sha256(item.encode()).digest()
        h1 = int.from_bytes(d[:8], "big")
        h2 = int.from_bytes(d[8:16], "big") | 1
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def add(self, item):
        for p in self._positions(item):
            self.bits[p // 8] |= 1 << (p % 8)

    def contains(self, item):
        return all(self.bits[p // 8] >> (p % 8) & 1
                   for p in self._positions(item))

# Have we already processed this order? (deduplication at ingestion)
bloom = BloomFilter(m_bits=1_000_000, k_hashes=7)   # ~122 KB for 100k items
for i in range(100_000):
    bloom.add(f"P-{i:09d}")

print(bloom.contains("P-000000042"))    # True (it is there)
false_pos = sum(bloom.contains(f"X-{i:09d}") for i in range(100_000))
print(f"False positives: {false_pos / 100_000:.4%}")   # typically < 1%

With m/n = 10 bits per element and k ≈ 7, the theoretical false-positive rate is ≈ (1 − e^(−kn/m))^k ≈ 0.8% — and the experiment confirms it. Canonical use: a cheap filter in front of an expensive resource (should I query the database for this id? only if the Bloom filter says "maybe"), wiping out at a stroke the vast majority of lookups for nonexistent elements.

The full family, so you can recognize them when they show up:

Structure Question it answers Error Typical memory
Bloom filter does x belong to the set? false positives (never negatives) ~10 bits/element
HyperLogLog how many distinct elements have I seen? (unique customers this year) ±2% in the count ~1.5 KB total, for billions
Count-min sketch how many times has x appeared? (approximate frequencies) overestimates, never underestimates KBs, fixed

The common pattern: trading exactness for memory, with the error mathematically bounded. It is the same philosophy as the heuristics of module 2 — giving up the optimum deliberately — now applied to space instead of time.

Top-K in streaming: the 10 postal codes with the most deliveries

Last piece: "the 10 postal codes with the most deliveries in the history". The reflex of sorting the ~10,000 postal codes by count works, but it is a special case of a pattern that deserves a name, because it comes up constantly with streams: for a top-K you do not need to sort everything — keep a min-heap of size K (01-04, and the same move as the k-way merge from 04-02):

import heapq
from collections import Counter

# Phase 1 (one pass, O(1) per record): count by key
counts = Counter()
def process(record):
    _, postal_code = record
    counts[postal_code] += 1

# ... after processing the full stream ...
counts = Counter({f"CP-{i:05d}": random.randint(1, 1_000_000)
                  for i in range(10_000)})   # simulation

# Phase 2: top-10 with a size-10 min-heap — O(n log K), not O(n log n)
top10 = heapq.nlargest(10, counts.items(), key=lambda kv: kv[1])
for postal_code, c in top10:
    print(postal_code, c)

heapq.nlargest does internally what you would do by hand: it scans the n counts keeping a min-heap with the K best seen so far; if the newcomer beats the heap's minimum, it replaces it. Cost O(n log K) with O(K) memory — with K=10 and n=10,000, about 15 times fewer comparisons than sorting, and the gap widens with n. And if not even the exact counts fit (keys of brutal cardinality, like one key per customer), you combine it with the count-min sketch from the previous table: approximate counts + an exact top-K heap on top of them.

The full case: the plan for the 200 million records

Let us close Rutalia's case with the engineering plan, piece by piece:

Business need Solution Section / lesson
Consolidate the historical files by date External merge sort (runs + k-way merge) §2, 04-02, 01-04
Deduplicate orders at ingestion Bloom filter in front of the exact check §5
Look up any order by id or by date range B+ tree (id) — or hash if there were only equality lookups §3, 01-04, 04-01
Deliveries and average delay per zone Divide-group-combine aggregation (Spark in real life) §4
Unique customers per quarter HyperLogLog §5
The 10 postal codes with the most deliveries Counter + top-K min-heap §6

Nothing in this table is a new algorithm: it is module 1 and module 4 repriced in the I/O currency. And the outputs of this pipeline are not an end in themselves: the per-zone aggregate table is exactly the kind of dataset the demand profiles of 05-05 and the cost matrices of 06-01 came from — today's big data feeds tomorrow's optimization and ML.

Common Mistakes and Tips

  • Counting comparisons when the currency is I/O. An algorithm that is "optimal" in RAM can be thousands of times slower on disk than a "worse" sequential one. Always ask: how many passes over the data am I making, and how much random access?
  • Materializing generators. list(file) over 40 GB kills the process. In data pipelines, everything that can be a generator/iterator must be one — the k-way merge works precisely because only the front of each run lives in RAM.
  • Using a Bloom filter where false positives are unacceptable. "I have probably seen it" is fine for skipping an expensive query; it is wrong for deciding that a payment is a duplicate and rejecting it. The Bloom filter filters; the exact check decides.
  • Sizing the Bloom filter by eye. The error rate depends on m/n and k; if you insert 10 times more elements than planned, the filter saturates and says "yes" to almost everything. Compute m for the maximum expected n.
  • Sorting everything for a top-K. O(n log n) time and O(n) memory where O(n log K) and O(K) sufficed. With streams, moreover, sorting is outright impossible: the heap is the tool.
  • Tip: before going distributed (Spark, cluster), exhaust the single machine — a good external sort and a good index on one machine handle surprisingly large volumes with a fraction of the operational complexity.

Exercises

  1. Merge passes. You have 25,000 runs after phase 1 and RAM to merge k = 50 streams at a time. How many merge rounds do you need, and how many full read/write passes over the data does that mean (counting phase 1)? What if you double the RAM (k = 100)?
  2. Size a Bloom filter for 200 million order ids with a target false-positive rate of 1%. Use the approximations m ≈ −n·ln(p)/(ln 2)² and k ≈ (m/n)·ln 2. How much memory is that in MB and how many hashes k do you use? Compare it with a Python set of those 200 million strings (estimate ~100 bytes per entry).
  3. Approximate median in one pass. The 200 million delivery_minutes values (integers 0-300) do not fit in RAM, but you want the exact median. Design a single-pass method with O(1) memory with respect to n. Hint: the key is in the range of the values, and you already saw the idea in counting sort (04-02).

Solutions

  1. Each round divides the number of runs by k: 25,000 → 500 → 10 → 1, that is, 3 rounds (⌈log₅₀ 25,000⌉ = 3). Full passes: 1 (phase 1) + 3 (merges) = 4 read+write passes. With k = 100: 25,000 → 250 → 3 → 1, still 3 rounds (⌈log₁₀₀ 25,000⌉ = 3, though only just: with 10,000 runs, 2 would have been enough). Moral: a large k flattens the logarithm extremely fast; RAM invested in merge width pays for itself in full.
  2. m ≈ −2·10⁸ · ln(0.01) / (ln 2)² ≈ 2·10⁸ · 4.605 / 0.4805 ≈ 1.92·10⁹ bits ≈ 229 MB, with k ≈ (m/n)·ln 2 ≈ 9.6·0.693 ≈ 7 hashes. The exact set: 200 M × ~100 B ≈ 20 GB. The Bloom filter uses ~85 times less memory in exchange for a 1% "maybe" that you resolve by querying the exact store only in those cases.
  3. Since the values live in a small, discrete range (0-300), keep a histogram of 301 counters (the counting sort table from 04-02) and update it in one pass: O(1) memory with respect to n. At the end, scan while accumulating until you exceed n/2: that value is the exact median (and you get any percentile as a bonus). The lesson: "it doesn't fit in RAM" refers to the records; sometimes the sufficient summary of the data is tiny — recognizing that saves you from deploying a cluster for a problem of 301 integers.

Conclusion

You have seen what happens to the algorithms of module 4 when the data overflows RAM: the currency changes from comparisons to I/O operations, and out of that change come external merge sort (Timsort + k-way merge with a heap, 04-02 and 01-04, applied to files), B-trees (the search tree from 01-04 fattened up to the size of a disk block), the divide-group-combine paradigm of MapReduce/Spark (divide and conquer as an architecture), and the probabilistic structures — with the Bloom filter implemented — that buy memory in exchange for a bounded error, plus top-K in streaming with a heap. Rutalia's 200-million-record case was solved with a decision table, not with brute force. And those aggregates are not the end of the road: they are the raw material of the models from module 5. That is exactly where the last lesson of the module goes: what happens when those machine learning models leave the notebook and enter production — drift, monitoring, famous failures, and the ethical obligations of deciding about people.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved