Skip to content
StealThis.dev

How the Database Executes Your Query — Fundamentals

What it is and why it affects you

When you run SELECT * FROM orders WHERE user_id = 42, the database has exactly two fundamental ways to find those rows:

  1. Sequential scan — read the whole table, keep matching rows. Cost: O(n) in rows, and worse, O(n) in disk pages read.
  2. Index scan — walk a B-tree (a sorted tree structure maintained alongside the table) down to the matching entries, then fetch just those rows. Cost: O(log n + k) for k matches.

With 10M orders, that’s the difference between reading ~10M rows and reading ~3–4 tree levels plus your handful of rows: hundreds of ms (or seconds) vs sub-millisecond. Every “my endpoint got slow as the table grew” story is some version of this table.

The database chooses between these with a query planner: it estimates costs using statistics about your data and picks the cheapest plan. Your job is rarely to outsmart it — it’s to (a) give it the indexes it needs, and (b) check what it actually chose with EXPLAIN.

The mental model

A B-tree index is a sorted, balanced tree over the values of one or more columns:

                        [ 500 | 2000 ]
                       /       |       \
              [100|300]   [800|1500]   [3000|5000]
              /   |   \    …                 …
        leaf pages: sorted values → pointers to table rows
  • Lookup (WHERE user_id = 42): walk root → leaf. ~3–4 page reads even at millions of rows — that’s O(log n) with a huge branching factor.
  • Range (WHERE created_at > '2026-01-01'): find the start leaf, then read leaves left-to-right — the leaves are linked and sorted.
  • Order (ORDER BY created_at DESC LIMIT 10): the index is already sorted — read the last 10 entries, done. No sort at all.

What indexes cost: every INSERT/UPDATE also updates each index (write amplification), and each index takes disk/cache space. That’s why you index the columns your queries filter/join/sort by — not everything.

Watch both access paths hunt the same row:

Two multiplication traps sit on top of this model:

  • N+1 queries: one query for the list, then one query per row for its relations. 100 rows = 101 round trips. Each may be fast; the sum (and the latency per round trip) is your slow endpoint.
  • OFFSET pagination: OFFSET 100000 LIMIT 20 walks and discards 100,000 rows first — O(offset) per page. Keyset pagination (WHERE id > $last LIMIT 20) uses the index and stays O(log n) on any page.

Reference table

Access methods (Postgres names; every serious DB has equivalents):

Plan nodeWhat it doesCost shapeYou want it when
Seq Scanreads the whole tableO(n)small tables, or queries matching most rows
Index ScanB-tree walk → fetch rowsO(log n + k)selective filters, sorts, joins
Index Only Scananswer entirely from the indexO(log n + k), no table visitsthe index covers all selected columns
Bitmap Index Scanindex → bitmap of pages → bulk fetchbetween the twomedium-selectivity filters
Nested Loop / Hash Join / Merge Joinjoin strategiesn·m / n+m / sorted mergethe planner picks — verify with EXPLAIN

What a B-tree index can accelerate:

Query shapeIndex helps?
WHERE col = x, IN, range (<, >, BETWEEN)Yes
WHERE col LIKE 'abc%'Yes (prefix)
WHERE col LIKE '%abc' / ILIKE '%abc%'No — needs trigram/full-text index
WHERE fn(col) = xNo — unless you index fn(col) (expression index)
ORDER BY col LIMIT kYes — reads k entries, no sort
Composite (a, b): filter on a or a AND bYes; filter on b alone: no (column order matters)

How this connects to the cases

Primary sources