The gap between asymptotic analysis and real execution

Big-O tells you how a cost grows as input grows, in the limit, with constants thrown away. That’s the right tool for comparing two sorting algorithms in a CS class. It’s the wrong tool, on its own, for predicting how a database executes a query. A query planner isn’t picking between abstract algorithms on an idealized machine. It’s picking between concrete physical operations, sequential reads, random reads, hash builds, sort buffers, running against a measured data distribution, with cost denominated in estimated page fetches and CPU cycles, not big-O classes.
A B-tree lookup is O(log n). A full table scan is O(n). If you stopped there you’d expect the planner to grab the index every time n gets large. Real planners routinely do the opposite, and they’re right to.
Index scan vs. sequential scan: what’s actually being compared
An index scan traverses the B-tree, which is cheap, a handful of comparisons, then for each matching entry fetches the corresponding heap page to get the actual row. That’s a heap fetch, and unless the index is covering, you pay for one per match. Each heap fetch is potentially a random I/O: a different disk page, no locality guarantee, unless the table happens to be physically clustered on that column.
A sequential scan reads the table page by page in physical order. On spinning disks, and even on SSDs behind a page cache, that order benefits from read-ahead and prefetching, which makes it dramatically cheaper per page than scattered random access.
So the real comparison isn’t O(log n) vs O(n) in the abstract. It’s:
index_scan_cost ≈ log(n) [tree traversal]
+ selectivity * n * random_page_cost [heap fetches]
seq_scan_cost ≈ n * seq_page_cost
Postgres defaults random_page_cost to 4.0 against a seq_page_cost of 1.0 (people tune it down to around 1.1–1.5 on SSD-backed systems, but it’s still at or above sequential cost). Selectivity is the fraction of rows the predicate is expected to match. Once that fraction gets large enough, the selectivity * n * random_page_cost term outgrows the cost of just reading the whole table in one pass. The crossover usually shows up in the single-digit percentages of the table, not some rare edge case. That’s why an index that’s fantastic for a highly selective predicate turns actively harmful for a low-selectivity one, and the planner refusing to use it is the correct call, not a bug.
The planner doesn’t know Big-O. It knows statistics.
Postgres’s planner is cost-based. It never reasons “index lookup is logarithmic.” It pulls numbers from pg_statistic, populated by ANALYZE: table row count (reltuples), most-common values and their frequencies, histogram bounds for everything else, and correlation between physical row order and column value. From that it computes an estimated selectivity for your predicate, feeds it into the cost formulas above (plus startup cost, CPU tuple cost, CPU operator cost), and picks whichever plan comes out cheapest.
Big-O describes a trend as n approaches infinity. The planner cares about one specific n, one specific selectivity, and specific hardware cost ratios, and it has to estimate all of that. When stats are stale or a predicate correlates with something the optimizer doesn’t model, those estimates can be badly wrong.
An illustrative example (not captured live, representative of real behavior)
Table: orders, 12 million rows, B-tree index on status.
CREATE INDEX idx_orders_status ON orders(status);
ANALYZE orders;
Querying a common status:
EXPLAIN ANALYZE
SELECT * FROM orders WHERE status = 'pending';
Seq Scan on orders (cost=0.00..305412.00 rows=4812000 width=96)
(actual time=0.019..1847.332 rows=4798213 loops=1)
Filter: (status = 'pending'::text)
Rows Removed by Filter: 7201787
Planning Time: 0.112 ms
Execution Time: 1958.410 ms
‘pending’ covers roughly 40% of the table. Even with idx_orders_status sitting right there, the planner skips it and does a full scan. That’s correct: fetching 4.8M heap pages randomly through the index would cost far more than one sequential pass, even though the index path is “O(log n) + k” and the seq scan is “O(n).” The constant on the random-access term swamps the asymptotic advantage.
Now a selective status:
EXPLAIN ANALYZE
SELECT * FROM orders WHERE status = 'chargeback_disputed';
Index Scan using idx_orders_status on orders
(cost=0.43..892.17 rows=214 width=96)
(actual time=0.038..0.291 rows=211 loops=1)
Index Cond: (status = 'chargeback_disputed'::text)
Planning Time: 0.098 ms
Execution Time: 0.324 ms
Selectivity here is about 0.0018%. The heap-fetch term is negligible, and the index wins by roughly four orders of magnitude in wall-clock time, matching the intuitive big-O expectation, because at this selectivity the random-access constant never gets a chance to dominate.
Same table, same index, same schema. The only thing that changed is the data distribution behind the predicate, and that’s exactly what you can’t see by analyzing the index structure in isolation.
Why this matters practically
None of this means indexes are unreliable or seq scans are secretly fast. It means complexity class is necessary but not sufficient for predicting real execution cost. A few things follow from that directly.
Run EXPLAIN (ANALYZE, BUFFERS) before arguing about a plan from intuition. ANALYZE without BUFFERS only shows estimated vs. actual rows and time. BUFFERS shows actual page hits and reads, which is where you’ll catch cases where estimated and actual plans diverge because the stats are stale.
Keep ANALYZE current. Autovacuum handles this most of the time, but bulk loads and fast-churning tables can outrun it, and a bad selectivity estimate produces a bad plan no matter how well you designed the index.
Don’t assume “it has an index, so it’ll use it.” If a predicate commonly matches a large chunk of the table, a partial index (WHERE status != 'pending') or a different approach entirely, covering index, BRIN for correlated columns, partitioning by status, is usually the real fix. Forcing index usage with planner hints is treating the symptom.
When you’re comparing two query shapes, compare their actual costs on your actual data, not their theoretical complexity class. A nested loop join, asymptotically worse at O(n*m), can still beat a hash join on small, highly selective inner relations, because the hash build’s fixed overhead dominates at small n.
Big-O tells you how a cost scales. The planner’s job, and yours when you’re staring at its output, is figuring out what that cost actually is: for this table, this data, this hardware, right now. Trust the EXPLAIN output over your asymptotic intuition. The planner is optimizing a cost function you don’t have memorized, using statistics you’ve probably never looked at.




