Why Your Query Optimizer Doesn’t Know Your Database Is Getting Old

The blind spot at the center of every data platform

Every modern data platform — whether it’s a Postgres instance backing a SaaS product or a lakehouse chewing through terabytes on Spark — leans on the same quiet assumption: that the query optimizer knows what it’s talking about. You write a query, the planner picks a join order, an index, a scan strategy, and it estimates a cost. Cheaper plan wins. This is cost-based optimization, and it has been the backbone of relational systems since System R in the 1970s.

But cost estimates are only as good as the model behind them, and that model is built on a simplification most engineers never think to question: that reading a page from storage costs roughly the same, no matter where that page happens to sit.

That assumption breaks down in ways that matter — and a strand of research out of the University of Tokyo, led by database systems researcher Kazuo Goda, has spent years documenting exactly how.

The problem nobody optimizes for: aging

Databases don’t stay tidy. Every insert, update, and delete gradually erodes the structural efficiency of storage — rows get split across pages, indexes fragment, free space scatters unpredictably. This phenomenon has a name in the database literature: aging, and it’s been studied since at least the early 1980s, when researchers like Heyman formalized mathematical models of database degradation and Sockut and Goldberg cataloged reorganization strategies to fight it.

The conventional fix has always been operational: run a VACUUM, rebuild an index, reorganize a table, and move on. What's largely been treated as a maintenance problem, though, is actually an optimization problem — and that's the reframing at the heart of Goda's work.

Aging isn’t uniform — and that’s the part optimizers miss

In Aging Locality Awareness in Cost Estimation for Database Query Optimization (Kato, Hayamizu, Goda, and Kitsuregawa, DEXA 2016), the authors make a sharp observation: aging doesn’t degrade a database evenly. Because real-world data access is inherently skewed — some tables, some ranges, some partitions get hammered far more than others — the resulting fragmentation clusters in specific regions of the storage space. I/O cost, in other words, has locality: it’s cheap in some places and expensive in others, and that expensive-vs-cheap map keeps shifting as the workload evolves.

Query optimizers, however, don’t see any of this. Classical cost models treat I/O cost as roughly uniform across the storage space, so a plan that looks cheapest on paper can turn out to be the slowest one to actually execute — not because the optimizer chose badly, but because it was reasoning about a storage layout that no longer exists. The authors’ proposed method instead builds a cost estimator that tracks where aging has concentrated and folds that locality directly into the cost calculation. Tested against PostgreSQL running TPC-H workloads, it produced meaningfully more accurate cost estimates than the standard, aging-blind model — precisely in the scenarios where conventional optimizers were quietly wrong.

It’s a small-sounding fix with a large implication: the optimizer’s map of the world needs to include the physical scars of the workload’s own history.

Why this matters beyond one database engine

It would be easy to file this away as a niche PostgreSQL result, but the underlying idea shows up everywhere in modern data infrastructure, just wearing different clothes:

• Lakehouse compaction. Delta Lake, Iceberg, and Hudi tables accumulate small files and stale versions with every write, and query engines pay an I/O tax for it until compaction or OPTIMIZE jobs run. That's aging with a different name.
• LSM-tree storage engines. Systems built on log-structured merge trees (Cassandra, RocksDB-backed stores, ClickHouse) degrade read performance as unmerged SSTables pile up, and their read-path cost is directly a function of how skewed and stale that pile-up is.
• Cloud warehouse statistics drift. Snowflake, BigQuery, and Fabric-style engines all rely on metadata and micro-partition statistics that go stale as data mutates — and stale statistics produce exactly the same failure mode Goda’s team measured: a cost model reasoning about a storage reality that has already moved on.

This connects to a broader thread in Goda’s research: the conviction that cost and performance models are only trustworthy when they reflect the true physical state of storage, not an idealized one. His later work — including a 2012 Proceedings of the IEEE retrospective on the history of storage systems, and more recent work modeling I/O interference in distributed, GPU-accelerated analytical engines — keeps returning to the same throughline: as storage hardware and access patterns get more complex, the abstractions optimizers reason over have to get more honest, or the numbers they produce stop meaning anything.

What this means if you build or operate data platforms

A few practical takeaways fall out of this line of research, regardless of which engine you run:

1. Don’t treat query plans as static truths. A plan that was optimal last month may be pessimal today if the underlying storage has aged unevenly since then. Re-planning and statistics refresh aren’t just hygiene — they’re load-bearing for correctness of cost, not just correctness of results.
2. Instrument physical layout, not just query latency. Fragmentation, small-file counts, tombstone density, and version skew are leading indicators of exactly the kind of locality-driven cost blindness this research describes. If you can see it, you can compact or reorganize before the optimizer starts guessing wrong.
3. Treat maintenance jobs as part of the optimization loop, not outside it. Vacuuming, compaction, and reorganization aren’t just cleanup — they’re how you keep the optimizer’s mental model of storage cost close to reality.
4. Workload skew is a feature of your system, not noise to average away. Because aging locality is a direct consequence of access skew, any cost model — or any dashboard — that assumes uniform access across your dataset is quietly wrong for exactly the hot paths that matter most.

The takeaway

Query optimization is often taught as a pure algorithms problem — join ordering, cardinality estimation, cost formulas on a whiteboard. Goda’s work on aging locality is a good reminder that it’s really a systems problem: the optimizer is only as good as its picture of the physical world underneath it, and that picture decays continuously as the system is used. Building data infrastructure that stays fast isn’t just about picking the right engine — it’s about making sure the engine’s model of its own storage keeps up with reality.

Reference

Kato, C., Hayamizu, Y., Goda, K., Kitsuregawa, M. (2016). Aging Locality Awareness in Cost Estimation for Database Query Optimization. In: Hartmann, S., Ma, H. (eds) Database and Expert Systems Applications (DEXA 2016). Lecture Notes in Computer Science, vol. 9828, pp. 389–396. Springer, Cham.

Further reading: Heyman, D.P. (1982), Mathematical Models of Database Degradation, ACM TODS 7(4); Sockut, G.H. & Goldberg, R.P. (1979), Database Reorganization — Principles and Practice, ACM Computing Surveys 11(4); Goda, K. & Kitsuregawa, M. (2012), The History of Storage Systems, Proceedings of the IEEE 100 (Centennial Issue).