Adding a column to 22 million rows without melting the database

This summer I needed to add a categories ltree[] column to Nominatim’s placex table as part of my GSoC project, on a planet-scale PostgreSQL database that serves search and ingests OSM replication updates the whole time. The column itself takes one ALTER TABLE. Filling it is the actual problem.

The obvious move is a batch update: walk the table, compute categories from existing tags, UPDATE everything. I started roughly there, and the version that got merged (PR #4106) looks very different. The pattern we ended up with is one I’d now reach for on any large live table, so here it is.

what a full-table UPDATE actually costs

Postgres doesn’t update rows in place. Every UPDATE writes a new row version and leaves the old one behind as a dead tuple for vacuum to clean up later. Update the whole table and you’ve effectively rewritten it once, plus every index on it. On a planet database that’s hours of sustained I/O, serious WAL volume, and a table temporarily far bigger than it needs to be until autovacuum catches up.

And placex is not a table you can quietly take offline. Search reads from it, the replication stream writes to it, constantly. A long-running migration is either holding locks that fight replication or getting killed by it.

Also, not everyone migrates on the same hardware. Nominatim installs range from full planet servers to country extracts on a laptop. A migration that’s fine for the laptop can be a multi-hour outage for the planet server. You design for the worst case.

the pattern: backfill only what’s read, default the rest

The question that changed the design (credit to my mentor sarah) was: who actually reads this column right now? Not “which rows should have data eventually”, but which rows does the code need to read today.

For us the answer was small. The update trigger reads the categories of other rows only when linking places and waterways, and those link targets all sit at rank_address < 26. So the migration eagerly backfills exactly that subset and nothing else. The rest of the strategy:

1. A lazy trigger fills the column on write. At the top of placex_update, if categories is empty, derive it from class/type right there. Rows get their value whenever they’re touched anyway, at a moment the write cost is already being paid. One catch: the trigger must produce byte-identical output to the import pipeline (ours is Lua), sanitization quirks and all, or you end up with rows that disagree depending on which code path wrote them.
2. Batch the remainder later, on your schedule. Before the search side started depending on the column, follow-up migrations filled the remaining ranks in batches. Nobody ever queried a half-empty column, and nobody sat through a full-table rewrite either.

The trade-off is honest: for a while some rows have data and some have NULL, and everything reading the column has to tolerate that during the transition. If your feature can’t handle partial data even briefly, this isn’t your pattern. For us, the search side wasn’t querying the categories column yet, so this wasn’t an issue. That let us reduce what was projected to be a multi-hour migration into about ~40 minutes of eager backfilling, while search behaved identically before and after the migration.

Two smaller things that made the eager part fast: disable the table’s triggers during the bulk UPDATE (otherwise ours would have fired 22 million times marking rows for reindex), and create your new indexes after the backfill, not before. Building an index once over final data is far cheaper than maintaining it through millions of updates.

end your migration with ANALYZE. i mean it

This one I learned the unpleasant way. After migrating, I ran our geocoder test suite and it took 4 hours 43 minutes. The slowest queries in the log showed 269 seconds. I ran the same queries manually: 0.7 seconds. Same server, same data.

Stale planner statistics. A bulk UPDATE leaves the planner’s picture of the table badly out of date, and the shiny new partial indexes are invisible to a planner that still believes the column is all NULL. So it plans on fiction and picks garbage. Autovacuum does eventually run an automatic ANALYZE after enough row changes, which is why my manual queries were fast by the time I tried them. But “eventually” is not a word you want anywhere near a migration.

So the merged migration ends with:

conn.execute(“ANALYZE placex”)

One line. Statistics are fresh the moment the migration returns, instead of at whatever unpredictable point autovacuum wakes up. If your migration bulk-updates a table, put an explicit ANALYZE on that table as the last step, every time. Mine hit during a benchmark run. Yours might hit during production traffic.

things i’d tell past me

The eager-everything backfill feels more “complete”, and I resisted the lazy design for about a week because of that. But complete-but-hostile loses to partial-but-safe when a live planet database is involved. Also: take your performance baseline before migrating. I only thought of it after, and spent a genuinely bad day believing I’d regressed search by 10x.

Full code and the whole discussion is in osm-search/nominatim#4106.