Making a list endpoint cost O(page), not O(table)

A list endpoint has a property that makes it uniquely good at hiding its own cost: the response size is constant. Twenty rows on page one, twenty rows on page five hundred, twenty rows whether the table holds a thousand records or four million. Every signal the client can see stays flat while the work behind it grows without limit.

So these endpoints pass review, pass staging, pass the first year, and then become the slowest thing you own — not because anyone wrote bad code, but because four separate parts of a normal implementation are all O(table) and none of them announce it.

This post is the technique catalogue, not an incident report. Each section is a pattern with a decision rule and the shape of the code, in the order I would apply them to an endpoint that has started to drift. The examples are Postgres and Rails; the reasoning holds for MySQL, and for any ORM that gave you page and per_page and let you stop thinking about it.

Related reading in this series: a latency budget you can defend for deciding what any of this should cost, and Little's Law in one afternoon for what happens to the queue when it doesn't.

1. OFFSET does not skip rows

The first thing to fix, because it is the least ambiguous.

OFFSET 10000 does not tell the database to start at row 10,001. There is no such instruction. The executor produces rows from the start of the ordering, counts them, discards them, and begins returning once the count is satisfied. The work is proportional to how deep the page is.

The replacement is a seek, usually called keyset or cursor pagination: carry the last row's sort key forward and ask for what comes after it.

-- page N, cost grows with N
SELECT * FROM records
 WHERE tenant_id = $1
 ORDER BY id
 LIMIT 20 OFFSET $2;

-- any page, constant cost
SELECT * FROM records
 WHERE tenant_id = $1 AND id > $2   -- $2 = last id of the previous page
 ORDER BY id
 LIMIT 20;

Three practical notes that decide whether this works in production:

The cursor must be unique and in the sort order. Paginating by created_at alone breaks on ties — two rows with the same timestamp straddle a page boundary and one of them is never returned. Sort by (created_at, id) and carry both: WHERE (created_at, id) > ($1, $2). Row comparison is standard SQL and Postgres will use a composite index on (created_at, id) for it.

Your index must match the sort exactly, including direction. ORDER BY created_at DESC, id DESC wants an index declared DESC, DESC — or one the planner can read backwards, which it can only do when the directions are consistent with each other.

You lose random access, and that is usually fine. Keyset gives you next and previous, not "jump to page 47". Check who actually uses deep page numbers. Every time I have looked, the answer was a crawler and a script, and the product answer was a better filter rather than a deeper page.

Rule: if a list can exceed a few thousand rows, it is keyset. Offset is for bounded sets you can prove stay small.

2. The count is a second query, and nobody reads the number

Here is the cost people miss entirely. A paginated response typically renders "Showing 1–20 of 4,182", and that total is a separate aggregate over the whole filtered set, executed on every single request. It cannot use the LIMIT. It has no upper bound. It is frequently more expensive than fetching the page.

Then ask what the number is for. Users read it as an order of magnitude — "is this dozens or thousands?" — and to decide whether to narrow the filter. Nobody needs to know that it is 4,182 rather than 4,180. Past a few pages, the exact value is a scan you pay for to render a string nobody parses.

The technique is to push a LIMIT inside the count and report a floor:

SELECT COUNT(*) FROM (
  SELECT 1 FROM records
   WHERE tenant_id = $1 AND status = $2
   LIMIT 10001                     -- cap + 1
) counted;

The + 1 is the whole trick: it tells you whether you hit the cap without telling you how far past it you are, which is exactly the information the + in "10,000+" encodes. GitHub, Google and Jira all do a version of this. It is not a degradation, it is the correct interface for an unbounded set.

Two things to get right when you wire it up:

# The count must not inherit the page's LIMIT/OFFSET, and must not inherit
# its ORDER BY either — sorting a set you are only going to count is pure cost,
# and it can push the planner onto a completely different index.
scope = page.except(:limit, :offset).unscope(:order)
n = scope.limit(CAP + 1).count(:all)
capped = n > CAP

And check what your pagination library does with the total, because the derived fields go wrong quietly:

# total_pages is computed from total_count. Hand it a capped count and it
# reports a capped page count — which is correct and consistent, as long as
# your UI does not also promise a "last page" button that now lies.
total_pages = (total.to_f / per_page).ceil

Rule: exact counts are for sets with a natural ceiling — a user's API keys, a deal's line items. Anything that grows with the tenant gets a bounded count and a +.

3. A covering index is not a licence to skip the table

This is the one that surprises people who have already done the reading, because the plan says the optimisation is working and the timing says it isn't.

Postgres can answer a query from the index alone — an index-only scan — but only when it can prove the rows are visible to your transaction without looking. That proof comes from the visibility map, a bitmap that marks heap pages as all-visible, and it is maintained by VACUUM. For any page not marked, the scan must fetch from the heap to check row visibility. EXPLAIN (ANALYZE) reports those as Heap Fetches.

So an index-only scan is not a property of your index. It is a property of your index and your write pattern. A table that is fully rewritten on a schedule — an hourly rollup, a nightly upsert, a sync job — keeps dirtying pages faster than autovacuum marks them clean, and the scan degrades into doing both jobs at once. You will see a plan that reads like a win, with Heap Fetches in the tens of thousands and a runtime that says otherwise.

The related trap is the INCLUDE clause:

CREATE INDEX idx_records_agg
    ON records (tenant_id, status)
INCLUDE (score, updated_at);

INCLUDE columns are stored in the leaf pages and are readable but not searchable. They can satisfy a SELECT list; they cannot satisfy a WHERE clause or an ORDER BY. A filter on score will not use this index no matter how much the column looks present. Everything you filter, join or sort on belongs in the key columns — in selectivity order — and INCLUDE is only ever for payload you return.

Rule: before adding an index for an aggregate, check the write pattern of the table. If it is rewritten faster than it can be vacuumed, no index will fix the read — go to technique 4.

4. Stop deriving the number; store it

Once the table is too hot to index your way out of, the remaining move is to stop computing the figure per request and compute it per change instead. This is the read-model idea from CQRS, and you do not need the rest of CQRS to use it: one small table, one row per (scope, subject), a JSON payload of the figures, refreshed by the job that already writes the underlying data.

CREATE TABLE rollups (
  id           bigserial PRIMARY KEY,
  tenant_id    bigint      NOT NULL,
  subject_type varchar(32) NOT NULL,
  payload      jsonb       NOT NULL DEFAULT '{}',
  computed_at  timestamptz NOT NULL
);
CREATE UNIQUE INDEX idx_rollups_subject ON rollups (tenant_id, subject_type);

The economics are a read:write ratio and nothing else:

Two design rules keep this from rotting, and they matter more than the schema.

One definition per figure, shared by both paths. The moment the writer computes "open deals" one way and the live fallback computes it another, you have two answers to one question and a bug that only appears when the rollup is stale. Put each figure in exactly one place and have both the writer and the fallback call it:

class RollupWriter
  # The single definition. The writer stores this; the read path's fallback
  # calls the same method. There is no second implementation to drift.
  def self.score_tally(scope)
    scope.group(:segment).count
  end
end

Staleness is a policy, not an accident. Store computed_at, define what stale means, and decide what a stale read does — serve it and refresh in the background is usually right for a dashboard; fall through to the live query is right for anything a user is about to act on. Write it down in the model:

STALE_AFTER = 6.hours
def stale? = computed_at < STALE_AFTER.ago

Rule: precompute when reads outnumber writes and the aggregate is over a set the request does not narrow. That second clause is the whole of the next section.

5. The gate: when is a cached aggregate legal to serve?

This is the technique I see skipped most often, and it is the one that turns a cache into a correctness bug rather than a stale number.

A rollup answers a specific question: what is true across this whole scope? A request that adds any narrowing — an owner filter, a team-scoped permission, a "hide archived" toggle — is asking a different question. Serving the rollup to it is not a cache hit. It is a wrong number, rendered with total confidence, and it will be wrong in the direction of "too big", which is the direction people do not question.

SELECT … FROM "records" WHERE "records"."tenant_id" = 1

SELECT … FROM "records" WHERE "records"."tenant_id" = 1

The robust check is not a list of known-safe filters, because that list goes stale the moment someone adds a sixth one and forgets. Compare the generated SQL of the request's scope against the scope the rollup was built from:

# Admissible only when this request's visible set is exactly the set the
# rollup was computed over. String equality on generated SQL is crude and
# that is the point: anything that narrows the scope changes the string, so
# a filter added next year fails closed without anyone remembering this file.
def unrestricted?(type)
  subject_scope(type).to_sql == tenant_scope(type).to_sql
end

def rollup_for(type)
  return nil unless unrestricted?(type)
  fetch_rollup(type)
end

Fails closed is the property worth paying for. A new filter, a new policy, a new role — all of them make the strings differ, the gate returns nil, and the endpoint falls back to the live aggregate. The failure mode is "slower than it could be", not "confidently wrong". When you are choosing between two designs for a cache, choose the one whose unknown-unknowns land on the slow side.

For aggregates that span several subjects, every one of them has to clear the gate:

def insight_rollup
  return nil unless %w[Contact Company Deal].all? { |t| unrestricted?(t) }
  fetch_rollup("Insight")
end

Refactor order

Applying these to an endpoint already in production, cheapest and safest first:

Do not start at 4. A read model built over an endpoint that still sorts its count and offsets its pages is a second system maintaining a first system's waste.

What to measure

Numbers that tell you the endpoint is drifting, before a user does:

• Rows examined per row returned. The single best ratio. A healthy page reads tens of rows to return twenty. Anything in the thousands is technique 1 or 2 waiting to happen.
• Heap Fetches on any plan you believe is index-only. If it is not near zero, you do not have an index-only scan, whatever the node is called.
• Count-query time as a share of endpoint time. Above about 30% and the total is costing more than the data.
• Rollup hit rate, split by reason for a miss — stale versus scope-gated. A high scope-gated rate is not a bug, it is the gate telling you your users filter more than you assumed, which is a product finding.
• p95 by page depth, not just p95. The average page is page one. The complaint is always about page forty.

If you only instrument one of those, take the first. Rows examined per row returned is the number that separates an endpoint that will be fine at ten times the data from one that will not, and it is visible in a single EXPLAIN (ANALYZE, BUFFERS) long before it is visible in a dashboard.