B+trees and not reading the whole table

Every operator so far starts with a Scan that reads every row. An index lets you jump to the rows you want. This part covers how a B+tree does that, what an index scan and an index nested-loop join look like as operators, and when an index makes things worse.

Take SELECT * FROM orders WHERE customer_id = 7 against the generated dataset: 5,000 orders, 126 of which belong to customer 7. Part 2's plan is Filter(customer_id = 7, Scan(orders)). It reads all 5,000 rows and evaluates the predicate 5,000 times to keep 126. The filter can't do better, because it only sees one row at a time and has no idea where the next match is.

To skip the other 4,874 rows, we need a second structure that is sorted by customer_id and points back at rows. That structure is an index. The question is what shape it should have.

Why a tree

Three candidates, all of them reasonable:

• A sorted array of (key, row id). Binary search finds a key in log₂(n) steps, and a range is a contiguous slice. But inserting a key shifts on average half the array, so every insert is O(n).
• A hash table from key to row ids. Lookups are O(1) and inserts are cheap. But it has no order, so customer_id BETWEEN 5 AND 9 or ORDER BY customer_id get no help at all.
• A balanced search tree. It has the sorted array's ordering and supports cheap inserts. The question is the fanout.

A binary tree over a million keys is 20 levels deep, and every level is a pointer chase, meaning a cache miss in memory or a page read on disk. A B+tree fixes that by making nodes wide. Each node holds up to order − 1 keys and order children. With order 200, which is typical for 8 KB pages and small keys, a million keys fit in three levels and a billion fit in four. The root and the second level stay hot in cache, so a lookup costs one or two real reads.

The "+" adds two rules on top of a plain B-tree:

1. All keys live in the leaves. Inner nodes only hold separator keys that route a search, copied up from the leaves. A separator k means "keys ≥ k go right".
2. Leaves are linked left to right. Once you find where a range starts, you walk sideways along the leaves instead of going back up the tree.

function search(tree, key)
  node = tree.root
  while not node.leaf
    i = count of separators s in node.keys where key >= s
    node = node.children[i]                -- one node per level: height visits total
  return entries in node with entry.key == key

function rangeScan(tree, lo, hi)
  leaf = descend to the leaf where lo would be      -- same loop as search
  loop
    for each entry in leaf
      if entry.key > hi then return
      if entry.key >= lo then yield entry.rowId
    leaf = leaf.next                       -- the "+" in B+tree
    if leaf is null then return

Inserting is where the balance comes from. You descend to the right leaf and insert in sorted position. If the leaf now holds too many keys, you split it in half and push the first key of the right half up into the parent as a new separator. If that overflows the parent, it splits too, pushing its middle key up. If the root splits, a new root is created above it. That's the only way the tree grows taller, which is why every leaf is always at the same depth.

function insert(node, key, rowId) -> split or null
  if node.leaf
    insert (key, rowId) into node.keys in sorted position
    if len(node.keys) <= order - 1 then return null
    right = new leaf with the upper half of node.keys
    right.next = node.next;  node.next = right
    return (right.keys[0], right)          -- separator is COPIED up; it stays in the leaf
  i = childIndex(node, key)
  split = insert(node.children[i], key, rowId)
  if split is null then return null
  add split.key and split.right to node at position i
  if len(node.keys) <= order - 1 then return null
  mid = len(node.keys) / 2
  right = new inner node with keys after mid and their children
  return (node.keys[mid], right)           -- inner split: middle key MOVES up

Try it. Order 3 makes splits happen constantly, which is the easiest way to see the mechanism. Insert keys one at a time and watch which leaf overflows. Search lights up the root-to-leaf path. Range scan descends once, then follows the dashed leaf links.

Two things to notice in the figure. First, a search visits exactly height nodes, whether the key exists or not. Second, the range scan's cost is height + leaves touched: one descent, then a sideways walk proportional to the size of the answer, not the size of the table.

Indexes as operators

An index on its own only produces row ids. To use it in a query, we need it to be an operator with the same Open / Next / Close shape as everything since part 2. There are two useful ones.

IndexScan

An IndexScan(table, index, lo, hi) replaces Filter(pred, Scan(table)) when the predicate is an equality or range on the indexed column:

IndexScan.Open()
  cursor = rangeScan(index, lo, hi)        -- a lazy iterator over row ids

IndexScan.Next()
  rowId = cursor.next()
  if rowId is none then return (null, false)
  return (table.rows[rowId], true)         -- the "fetch": index entry -> actual row

The last line is easy to skip over, and it's the one that decides whether the index helps. Our index is secondary: it's a separate structure, and its leaves hold row ids. Each match costs a lookup into the table. In memory that's an array index. On disk it's a random page read, because rows matching customer_id = 7 are scattered through the table in whatever order they were inserted.

A clustered index (SQLite's rowid tables, InnoDB's primary key, a Postgres table right after CLUSTER) stores the rows themselves in key order, so matching rows sit next to each other and the fetch is free or sequential. A covering index includes every column the query needs, so the fetch disappears entirely.

Index nested-loop join

The more important use is inside a join. Part 3's nested loop join rescans the entire inner input once per outer row, costing |outer| × |inner|. If the inner side is a base table with an index on the join column, you can replace that rescan with a seek:

IndexNLJoin.Next()
  loop
    if matches has more
      return (outerRow ++ table.rows[matches.next()], true)
    (outerRow, ok) = outer.Next()
    if not ok then return (null, false)
    key = eval(outerKey, outerRow)
    if key is null then continue           -- NULL never joins
    matches = search(index, key)           -- height node visits, not |inner| rows

The cost becomes |outer| × (height + matches per key). Compared with part 3's hash join, there's no build phase and no hash table in memory. The index is the hash table, built ahead of time and kept up to date on every insert. That makes the index NL join the best plan when the outer side is small, as in "these 20 customers and their orders". The hash join wins when both sides are large and you'd do millions of seeks. Choosing between them requires knowing how big the outer side will be, which is what part 6 is about.

When an index makes it worse

Indexes aren't free speed. A full scan reads pages in order, which disks and prefetchers are very good at. An index scan through a secondary index does a few node visits, then one random fetch per matching row. With 1% of a million-row table matching, that's 10,000 random reads, and if 100 rows fit on a page the full scan was only 10,000 sequential reads to begin with.

The figure plots both, plus a clustered index, as the fraction of matching rows changes. Random page cost is the ratio of a random read to a sequential one. Postgres defaults random_page_cost to 4. In memory it's closer to 1–2 (a cache miss versus a prefetched line).

The crossover is surprisingly low. At the default ratio, a secondary index is only worth using below roughly a quarter of a percent of the table. Above that, the planner should ignore the index and scan. That's why planners need selectivity estimates: the same query with customer_id = 7 (126 rows, 2.5% of orders in our skewed data) and customer_id = 150 (11 rows) can deserve different plans.

A clustered index changes the picture completely, because the fetch is sequential. That's why the choice of clustering key matters so much in InnoDB and SQL Server, and why Postgres has bitmap heap scans: they collect row ids from the index, sort them by page, and fetch each page once, turning random reads back into something closer to sequential ones.

cd go && go test ./exercises/lesson05/
cd clojure && clojure -M:ex -d ex -n exercises.lesson05.indexes-test