Startup Cost vs Total Cost Under LIMIT #

SELECT … WHERE status = 'failed' ORDER BY created_at DESC LIMIT 20 returns in 2 ms on most days and in 40 seconds on the day nothing has failed recently. The plan is the same both days: walk the created_at index backwards and stop after 20 matches. When the matches are recent, that is a short walk. When they are rare or old, it is a walk through the whole table.

Every node in a plan carries two costs, startup and total, and LIMIT is where the difference between them decides the plan. The general cost arithmetic is in cost estimation models; this page covers the specific trap it creates for top-N queries.

The Cost-Model Condition #

cost=S..T means: S is the estimated cost before the first row is returned, T is the estimated cost to return all rows. A sort has a high startup cost, because it must consume its entire input before emitting anything. An index scan that already returns rows in the requested order has a startup cost near zero.

A Limit node does not know how many rows it will really need to read; it assumes the rows it wants are spread uniformly through its input. If the input is estimated to produce N rows and the limit is k, the planner charges:

startup + (total − startup) × k / N

For the index walk: the index scan returns all created_at order rows, the filter status = 'failed' is estimated to keep 0.5% of them, so N is 0.5% of the table and 20 matches are expected after reading about 4,000 rows. That fraction of the total cost is tiny, so the index walk wins easily against “find all failed rows, then sort, then take 20”, whose high startup cost is paid in full.

The assumption fails when matching rows are not uniformly distributed along the index order: failed rows clustered in the past, a tenant whose rows are all old, a status that is rare in recent data. The walk then reads far more than k / N of its input before finding enough matches. The same trap affects EXISTS subqueries (effectively LIMIT 1), cursors (which plan for cursor_tuple_fraction, default 0.1, of the result) and merge joins chosen because a sorted path has low startup cost.

Two plans for ORDER BY created_at DESC LIMIT 20 Left, the index walk: startup cost near zero, and the Limit charges only the fraction needed to find 20 matches assuming they are spread evenly, so it looks cheap. Right, filter then sort: the bitmap scan and sort must finish before the first row, so the full startup cost is charged and it looks expensive, even though its cost does not depend on where matches sit. index walk on created_at startup ≈ 0 charged: total × 20 / estimated matches assumes matches spread evenly real cost depends on where matches are bitmap scan on status → sort startup = find all + sort them charged in full before row 1 estimate looks expensive real cost independent of match position the Limit discount is only as good as the uniformity assumption

Annotated EXPLAIN Evidence #

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, created_at FROM jobs
WHERE status = 'failed'
ORDER BY created_at DESC
LIMIT 20;
Limit  (cost=0.44..812.30 rows=20 width=16) (actual time=40204.1..40215.9 rows=20 loops=1)
  ->  Index Scan Backward using jobs_created_at_idx on jobs
        (cost=0.44..8120114.00 rows=200011 width=16)
        (actual time=40204.1..40215.8 rows=20 loops=1)
        Filter: (status = 'failed'::text)
        Rows Removed by Filter: 39811204
        Buffers: shared hit=1022 read=384910
Execution Time: 40216.3 ms
-- Limit cost 812 ≈ 8.1M × 20 / 200011 : the uniform-spread discount
-- Rows Removed by Filter 39.8M: the failed rows were all old, far down the index

The plan the planner rejected:

Limit  (cost=182214.10..182214.15 rows=20 width=16) (actual time=96.2..96.2 rows=20 loops=1)
  ->  Sort  (cost=182214.10..182714.13 rows=200011 width=16)
        Sort Key: created_at DESC
        Sort Method: top-N heapsort  Memory: 26kB
        ->  Bitmap Heap Scan on jobs  (actual rows=198422 loops=1)
              Recheck Cond: (status = 'failed'::text)
Execution Time: 96.8 ms
-- startup cost 182K charged in full: looked 224× more expensive, ran 415× faster
The three numbers that reveal the trap Three fields are annotated. The Limit's total cost is a small fraction of the child's total. Rows Removed by Filter is enormous compared with the limit of 20. Actual startup time equals total time, meaning nothing was returned until the very end of the walk. Limit (cost=0.44..812.30) over 8.1M child fraction charged, not the walk Rows Removed by Filter: 39811204 matches were far down the index actual time=40204.1..40215.9 first row arrived at the end first-row time close to total time under LIMIT is the tell

Step-by-Step Resolution #

  1. Confirm the pattern: a Limit over an ordered scan with a Filter, huge Rows Removed by Filter, and actual startup time close to total time.

  2. Check how matches are distributed along the ordering column:

    SELECT date_trunc('month', created_at) AS m, count(*)
FROM jobs WHERE status = 'failed' GROUP BY 1 ORDER BY 1 DESC LIMIT 6;

  3. Give the filter and the order one index. The cleanest fix makes the walk read only matching rows:

    CREATE INDEX CONCURRENTLY jobs_status_created_idx ON jobs (status, created_at DESC);

    With equality on status first, the index returns only failed jobs, already in order, and the Limit stops after exactly 20 entries — the pattern in partial indexes for job queue polling when the status is fixed.

  4. If an index is not possible, remove the ordered path from consideration for that statement by making the sort key an expression:

    SELECT id, created_at FROM jobs
WHERE status = 'failed'
ORDER BY created_at + interval '0' DESC
LIMIT 20;

    The expression no longer matches the index, so the planner must filter first and sort — which is correct when matches are rare. Comment the reason next to the query.

  5. Review cursor-driven queries separately. A client that opens a cursor and fetches everything makes the 10% assumption wrong in the other direction; raising cursor_tuple_fraction to 1.0 for that session plans for the full result.

Where the matches sit decides the real cost Three bars for the backward index walk. Matches spread evenly: about 4 thousand rows read. Matches mostly last week: about 90 thousand rows read. Matches all older than a year: 39.8 million rows read. The planner assumes the first case in every situation. spread evenly (assumed) ~4,000 rows read mostly last week ~90,000 rows read all older than a year 39.8M rows read the estimate is identical in all three cases

Before and After #

-- BEFORE: backward walk on created_at, filter on status
Limit → Index Scan Backward using jobs_created_at_idx   Rows Removed by Filter: 39811204   Execution Time: 40216.3 ms

-- AFTER: index on (status, created_at DESC)
Limit → Index Scan using jobs_status_created_idx   Index Cond: (status = 'failed')     Execution Time: 0.09 ms

Why statistics cannot fix this #

It is tempting to treat this as an estimate problem and reach for statistics tuning. But the row estimate for status = 'failed' was accurate: about 200,000 failed jobs existed. What the planner lacks is information about where those rows fall in created_at order, and no per-column statistic records that relationship between two columns’ orderings. Extended statistics describe how column values co-occur, not how one column’s values are positioned along another column’s sort order. The only reliable remedies are structural: an index that makes the ordered path read only qualifying rows, or a rewrite that removes the ordered path as an option.

Common Pitfalls #

Adding a single-column index on the filter column. An index on status alone gives the planner a cheap way to find failed rows but not in order; the uniform assumption can still make the backward walk look cheaper. Diagnostic signal: the new index unused. Fix: a composite index with the filter first and the sort column second.

Using OFFSET for pagination. LIMIT 20 OFFSET 10000 charges for 10,020 rows and suffers the same distribution effect. Diagnostic signal: pages slowing linearly with depth. Fix: keyset pagination on the ordering column.

Fixing one parameter value. The trap is data-dependent; a rare tenant or status triggers it while common ones do not. Diagnostic signal: fast for most values, catastrophic for a few. Fix: test the rarest values, not the typical ones.

Disabling index scans for the session. enable_indexscan = off also removes the good bitmap and index plans elsewhere in the query. Diagnostic signal: other nodes regress after the change. Fix: the expression rewrite or composite index scoped to this statement.

Frequently Asked Questions #

What is the difference between startup cost and total cost in EXPLAIN? #

Startup cost is the estimated cost before the node can return its first row; total cost is the estimate to return all rows. A sort has high startup cost because it reads all input first, while an index scan in the right order can return its first row almost immediately.

Why does adding LIMIT make PostgreSQL choose a slower plan? #

The Limit node assumes the rows it needs are spread evenly through its input, so a plan with near-zero startup cost is charged only a small fraction of its total. When matching rows are clustered far from the start of that order, the plan reads much more than assumed.

How do I stop ORDER BY LIMIT from walking the wrong index? #

Create a composite index with the equality filter columns first and the ORDER BY column last, so the ordered scan reads only matching rows. Where that is impossible, make the sort key an expression such as created_at + interval '0' so the ordered index path is no longer available.

Up: Cost Estimation Models