Data Structures & Algorithms for Data

Big-O notation in plain language

Big-O is not about how fast something is in seconds. It's about how the amount of work grows as your data grows. That distinction is the whole game. A clever algorithm on a slow laptop will crush a sloppy one on a supercomputer the moment the data gets big enough — and in data work, the data always gets big enough.

Say you have n rows. We ask: if I double n, what happens to the work?

• O(n) — double the rows, double the work. Looking at every row once. Fine.
• O(n²) — double the rows, quadruple the work. Comparing every row to every other row. Catastrophic.

That gap sounds abstract until you put real numbers on it. At a thousand rows, an O(n²) algorithm does a million operations — instant, you'd never notice. At a million rows, it does a trillion operations — your job hangs for hours or dies. The O(n) version, meanwhile, did a million operations: a blink. Same task, same machine; one scales and one doesn't.

Keep this table in your head. When a query is mysteriously slow, the first question a senior engineer asks is: "what's the Big-O of what it's actually doing?" Usually something accidentally became O(n²).

Arrays/lists and hash tables

Two structures cover most of your day. An array (Python list) is a row of boxes in order. Reading box #5 is instant — O(1) — but finding a value means checking boxes one by one until you hit it: O(n).

A hash table (Python dict and set) is the single most important structure in data engineering. It computes a value's "hash" — a number derived from the data itself — and uses that number to jump straight to where the value lives. No scanning. Membership tests and key lookups are O(1), no matter how big the table gets.

Let's feel the difference. We'll search for a value the slow way (scanning a list) and the fast way (testing a set), on a big input, and time both.

import time

N = 2_000_000
data = list(range(N))          # a list 0 .. N-1
data_set = set(data)           # the same values in a hash table (set)

target = N - 1                 # worst case: the last value (or a missing one)

# --- Slow way: scan the list, checking each element (O(n)) ---
start = time.perf_counter()
found = target in data         # 'in' on a LIST scans element by element
list_time = time.perf_counter() - start

# --- Fast way: hash lookup in a set (O(1)) ---
start = time.perf_counter()
found = target in data_set     # 'in' on a SET hashes and jumps straight there
set_time = time.perf_counter() - start

print(f"list scan : {list_time*1000:8.3f} ms")
print(f"set lookup: {set_time*1000:8.3f} ms")
print(f"set is ~{list_time/set_time:,.0f}x faster")

Trees and sorted structures

Hash tables are unbeatable for "is this exact key present?" But they're useless for ranges — "give me all users who signed up between March and June" — because hashing scatters values randomly, destroying any order. For ranges and sorting you want data kept sorted.

The payoff of sorted data is binary search. To find a value in a sorted array, look at the middle: too high? Throw away the top half. Too low? Throw away the bottom half. Each step halves what's left, so finding anything among a million rows takes about 20 steps — that's O(log n).

A tree generalizes this idea so the structure can be updated cheaply as rows are inserted and deleted, while staying balanced enough that lookups remain O(log n). The version databases actually use is the B-tree — a wide, shallow tree tuned for reading from disk in big chunks. It's how a database index turns a WHERE user_id = 42 from an O(n) full scan into an O(log n) seek, and how it answers range queries (WHERE date BETWEEN …) by walking the sorted leaves. We unpack B-trees in Chapter 03; for now, just hold onto this: "kept sorted" is what buys you fast range queries and O(log n) lookups.

Sorting — and what happens when data won't fit

Sorting shows up everywhere: ORDER BY, deduplication, and one of the join algorithms below. The best general-purpose sorts (the kind behind Python's sorted()) run in O(n log n). The intuition: there are n items to place, and pinning down each one's position takes about log n comparisons (the same "halving" we just saw). You can't do better than O(n log n) with comparison-based sorting — it's a proven floor.

rows = [("eu", 95), ("us", 200), ("eu", 80), ("us", 120)]

# sort by amount (the 2nd field), descending — O(n log n)
by_amount = sorted(rows, key=lambda r: r[1], reverse=True)
print(by_amount)
# [('us', 200), ('us', 120), ('eu', 95), ('eu', 80)]

That works while everything fits in memory. But data engineering routinely sorts files bigger than RAM — a 500 GB dataset on a 16 GB machine. You can't hold it all at once, so you use an external sort:

1. Split & sort chunks. Read as much as fits in memory, sort that chunk, write it back to disk as a sorted "run." Repeat until the whole file is a pile of sorted runs.
2. Merge the runs. Open all the sorted runs at once and repeatedly take the smallest current value across them — like merging sorted decks of cards. This streams through the data using little memory and produces one fully sorted output.

The payoff: how a JOIN actually executes

You write SELECT … FROM orders JOIN customers ON orders.customer_id = customers.id and rows come back matched up. But how? The database picks one of three algorithms, and the choice is the difference between milliseconds and a job that never finishes. Say orders has n rows and customers has m rows.

Nested-loop join is the naive way: for each of the n orders, scan all m customers looking for a match. That's n × m comparisons — O(n·m), the quadratic monster from the Big-O table. Fine for tiny tables; ruinous for big ones (unless one side has an index, which turns the inner scan into an O(log m) seek).

Hash join is the workhorse, and it's our hash table again. Build phase: load the smaller table into a hash table keyed on the join column. Probe phase: stream the bigger table through, and for each row do an O(1) lookup to find its matches. Total work is just O(n + m) — you touch each row about once. This is why hash joins are fast.

Sort-merge join sorts both tables on the join key (O(n log n + m log m)), then walks them together in one pass like the merge step of external sort. It shines when the data is already sorted (or indexed in order), or is too big for a hash table to fit in memory — because sorting can spill to disk.

You rarely choose the algorithm directly — the query planner does (Chapter 04). But now, when EXPLAIN says Hash Join or Nested Loop, you'll know exactly what it means and whether to worry.

GROUP BY and DISTINCT — the same hash table, again

Once the hash table clicks, aggregation is almost obvious. GROUP BY region works by hashing on region: keep a dict whose keys are regions and whose values are running totals. Stream through the rows once, hashing each region to its bucket and updating the total. One pass, O(n), memory proportional to the number of groups (not rows).

DISTINCT and deduplication are even simpler: drop everything into a set. The set's O(1) membership test silently discards repeats, leaving only unique values.

rows = [("us", 120), ("eu", 80), ("us", 200), ("eu", 95)]

# GROUP BY region, SUM(amount) — a hash aggregation by hand
totals = {}
for region, amount in rows:
    totals[region] = totals.get(region, 0) + amount   # O(1) per row
print(totals)                 # {'us': 320, 'eu': 175}

# SELECT DISTINCT region — dedup via a set
print(set(r[0] for r in rows))   # {'us', 'eu'}

✓ Check yourself

• Can you explain why O(n²) is "fine" at a thousand rows but catastrophic at a million?
• Why is a set lookup O(1) while a list scan is O(n) — what is the hash doing?
• What does a hash join do in its build phase, and why can that phase run out of memory?
• What is fan-out, and how can it make a join's output bigger than both inputs?

a = list(range(0, 100_000))
b = list(range(50_000, 150_000))   # overlap is 50_000 .. 99_999

# --- Slow way: nested loop — O(n·m) ---
def common_slow(xs, ys):
    result = []
    for x in xs:              # n iterations
        if x in ys:           # each 'in' on a LIST is O(m) → n*m total
            result.append(x)
    return result

# --- Fast way: build a set, then probe — O(n + m) ---
def common_fast(xs, ys):
    ys_set = set(ys)          # build: O(m)
    return [x for x in xs if x in ys_set]   # probe: n * O(1) = O(n)

# common_slow(a, b)  # works, but ~10 BILLION comparisons — don't wait up
print(len(common_fast(a, b)))   # 50000, returns almost instantly

Next

We've seen the algorithms that make data operations fast; now let's see where the data physically lives and how indexes turn those algorithms loose on disk. → Inside a Database — Storage & Indexes