Do Small Tables Need Indexes? How a 114-Row Table Read 166 Billion Tuples

TL;DR — The usual answer to “do small tables need indexes?” is no, a sequential scan of a few pages is cheaper than an index probe, and the planner knows it. That answer is right per execution and wrong in aggregate. During the diagnosis of a database overload, pg_stat_user_tables showed a 114-row table with 1.6 billion sequential scans and 166 billion tuples read — because it sat inside a correlated subquery that ran once per row of every order query on the platform. Per-scan cost is irrelevant when the multiplier is the outer row count. The fix was not really the index; it was stopping the loop.

Key takeaways

• The planner is correct to seq-scan a tiny table. It is optimising one execution, and it does not know that execution is inside a loop of ten thousand.
• Correlated subqueries in PL/pgSQL and per-row resource embeds each run the inner query once per outer row. That is one scan per outer row, by design.
• seq_scan and seq_tup_read in pg_stat_user_tables find these in one query: sort by seq_tup_read and look for tables whose n_live_tup is tiny.
• Billions of cheap scans still cost CPU per tuple and churn shared_buffers. On a 2 GB instance this showed up as 483 MB of swap.
• Indexing the tiny table is a hedge. Removing the repetition — inlining the function so the planner sees one query — is the fix.

The number

The overload postmortem needed to know which tables the database was spending its time on, and pg_stat_user_tables answers that in one query:

-- Which tables are scanned most, and how much do the scans read?
SELECT relname,
       n_live_tup                       AS rows,
       seq_scan,
       seq_tup_read,
       round(seq_tup_read::numeric / GREATEST(seq_scan, 1)) AS tuples_per_scan
  FROM pg_stat_user_tables
 ORDER BY seq_tup_read DESC
 LIMIT 10;

Illustrative table names, real magnitudes:

Two different problems are in this table, and the “tuples per scan” column separates them.

The bottom rows — meal_reviews, transactions — are the textbook case: tens of thousands of rows, tens of thousands of tuples read per scan, a filter column with no index. Every scaling post covers this, including mine, and the fix is an index on the column in the WHERE clause. Not interesting.

The top rows are the interesting ones. order_subsidies has 114 rows, so a scan reads about 114 tuples — that is a handful of heap pages, and the whole table lives permanently in shared_buffers. Any single scan of it costs microseconds. There were 1.6 billion of them.

Why the planner is right, and it does not matter

Ask Postgres to find one row in a 114-row table and it will scan the table. Reading two heap pages sequentially and comparing 114 tuples is cheaper than descending a B-tree and then fetching the heap page anyway. If you add an index and run EXPLAIN, the planner will very often still choose the sequential scan, and it will be correct to.

The planner’s cost model is per execution. It has no concept of this query is the inner side of a loop, because at the level it operates the loop is somebody else’s plan. That is the whole story of this post: the decision was right at the granularity it was made at, and wrong at the granularity that mattered.

Where the repetition came from

Two constructs, both of which run the inner query once per outer row.

A correlated subquery inside a PL/pgSQL function. The platform’s main order-listing function was written in PL/pgSQL and, for each order it returned, computed the subsidy applied to it by querying the ledger:

-- Illustrative. Shape of the original function, reduced.
CREATE FUNCTION orders_for_outlet(p_outlet uuid)
RETURNS TABLE (order_id uuid, total numeric, subsidy numeric)
LANGUAGE plpgsql STABLE AS $$
BEGIN
  RETURN QUERY
    SELECT o.id,
           o.total,
           -- runs once per order row: one scan of order_subsidies per order
           (SELECT coalesce(sum(l.amount), 0)
              FROM order_subsidies l
             WHERE l.order_id = o.id)
      FROM orders o
     WHERE o.outlet_id = p_outlet;
END $$;

For an outlet with 10,000 lifetime orders, one call scans order_subsidies 10,000 times. This function had 14 call sites, some of them inside real-time handlers that re-ran it per connected client per order update. The scan count is not surprising once you multiply.

A per-row resource embed. The API layer (PostgREST, though the same is true of any ORM that resolves relations lazily) compiles a request like “orders, with their subsidy rows” into a LATERAL subquery that executes once per outer row. Same shape, same multiplier, without any function in the way.

  one API request for an outlet's orders
    └─ 1 scan of orders (indexed, fine)              →  N rows
         └─ per row: 1 scan of order_subsidies        →  N scans
              └─ per row: 1 scan of meal_timings     →  N scans
                                                        ─────────
                                                        2N + 1 scans per request
  × 8,000 requests/day  × 14 call sites  × weeks since stats reset  = 10⁹

Why cheap × billions still hurts

A sequential scan of a cached two-page table does no I/O. It still does work:

• CPU per tuple. Every scan visits every tuple, tests the filter, and discards most of them. 166 billion tuple visits is on the order of hours of CPU, spent finding rows that an index would have found in a few comparisons — or that a single join would have found once.
• Buffer churn. Hot pages stay in shared_buffers, which sounds good until you remember that the buffer pool is shared. Re-touching the same pages billions of times keeps them pinned at the top of the eviction order and pushes out the pages that a paginated order query actually needed. The postmortem’s diagnosis line was that this kept a 2 GB instance in constant memory pressure, with 483 MB swapped at the moment we looked.
• Lock and snapshot overhead. Each scan is small, but each one takes a snapshot, pins and unpins buffers, and reports statistics. At 10⁹ that overhead is a real fraction of the work.

None of this shows up in a slow-query log, because no individual query is slow. It shows up as a database that is busy all the time with nothing obviously to blame.

The fix, in the order it mattered

1. Inline the function, and shrink the loop. Converting the PL/pgSQL function to LANGUAGE sql STABLE lets the planner inline it into the calling query, so the filters and limits the API layer adds (WHERE outlet_id = …, LIMIT 20) are pushed into the plan instead of being applied after the function has materialised an outlet’s entire history. The correlated subquery still runs per row — Postgres does not decorrelate a scalar subquery for you — but it now runs 20 times per request instead of 10,000. One change; 14 call sites fixed. This is what removed most of the 10⁹.

To make the small table scan once, the subquery has to move into the FROM clause as a grouped join, which is the rewrite I would do next:

-- Illustrative. Aggregate the ledger once, then join; order_subsidies is scanned one time.
SELECT o.id, o.total, coalesce(s.subsidy, 0) AS subsidy
  FROM orders o
  LEFT JOIN (SELECT order_id, sum(amount) AS subsidy
               FROM order_subsidies GROUP BY order_id) s ON s.order_id = o.id
 WHERE o.outlet_id = $1
 ORDER BY o.created_at DESC
 LIMIT 20;

2. Add the indexes anyway. CREATE INDEX CONCURRENTLY on the filter column of each table in the list. For the large tables this was the fix outright. For the tiny ones it is a hedge: if some future query does hit order_subsidies in a loop again, the planner may pick the index once the table is a few pages wide, and the cost of carrying an index on 114 rows is nothing. I am not going to claim the index changed the plan on the smallest tables, because I did not verify that it did.

3. Remember the foreign-key rule. Postgres does not create an index for a foreign key column; it creates one for the referenced primary key. order_subsidies.order_id referenced orders.id and had no index of its own. Every “join the child table to the parent” query scans the child unless you add that index yourself.

What CREATE INDEX CONCURRENTLY does and doesn’t promise

The migration ran during service, so it used CONCURRENTLY. Two things to know before you do the same:

• It cannot run inside a transaction block. Most migration runners wrap each file in a transaction; this statement has to be in a file that opts out of that, or it errors immediately. The docs explain the two-scan build and why it needs to see other transactions commit in between.
• If it fails, it leaves an invalid index behind. A concurrent build that hits a deadlock or a unique violation leaves the index in place, marked invalid, still maintained on every write, never used for reads. Check for these after any concurrent build:

SELECT indexrelid::regclass
  FROM pg_index
 WHERE NOT indisvalid;

Drop and rebuild anything that comes back. An invalid index is the worst of both worlds — write cost, no read benefit — and it is silent.

What actually broke in production

The numbers in the table are cumulative since the last statistics reset, which on this instance was months earlier. That means I cannot tell you the rate — whether 1.6 billion scans was a steady drip or mostly the last two weeks — and the honest reading of the postmortem is that the base load had been building for a long time before anyone queried pg_stat_user_tables at all. The query at the top of this post takes a second to run. It should have been run monthly.

The other thing that broke is a habit. When I checked this function’s performance, I ran it once, for one outlet, and read the plan. The plan looked fine, and for one call it was fine. Nothing in EXPLAIN output invites you to multiply by the number of call sites or by the largest outlet’s order count, and I did not.

FAQ

Do small tables need indexes in PostgreSQL? Usually not for a single query — the planner will scan a table of a few pages faster than it can probe an index. They need one when they are the inner side of a per-row loop: a correlated subquery, a lateral join, or an ORM relation resolved per parent row. Even then the better fix is to restructure the query so the small table is scanned once, and add the index as a hedge.

How do I find which tables Postgres is scanning most? Query pg_stat_user_tables and sort by seq_tup_read. Divide by seq_scan to get tuples per scan: a high count with a large table means a missing index on a filter column; a huge seq_scan count with a tiny table means something is scanning it in a loop.

Why does a correlated subquery cause repeated sequential scans? Because it references a column from the outer query, so it must be re-evaluated for every outer row. If the inner table is small the planner chooses a sequential scan for each evaluation, giving one full scan per outer row. Rewriting as a join or a GROUP BY subquery in the FROM clause lets the planner scan the inner table once.

Why is a PL/pgSQL function slower than a SQL function for queries? A PL/pgSQL function is opaque to the planner: it runs its body as separate statements and returns the full result before any outer filter applies. A LANGUAGE sql function marked STABLE or IMMUTABLE can be inlined into the caller’s plan, so filters and limits from the outer query push down and correlated pieces can be turned into joins.

Does Postgres automatically index foreign key columns? No. Declaring a foreign key creates no index on the referencing column; only the referenced side (a primary key or unique constraint) is indexed. Any query that joins from the child table to the parent, or deletes a parent row and must check children, scans the child table unless you add the index yourself.

Is CREATE INDEX CONCURRENTLY safe to run in production? It avoids the write-blocking lock a normal CREATE INDEX takes, so writes continue during the build. It cannot run inside a transaction, takes longer, and if it fails it leaves an invalid index that must be dropped by hand. Check pg_index.indisvalid after every concurrent build.

What I’d still improve

• Reset table statistics and re-measure for a week, so the rate is known rather than the cumulative total since a forgotten date.
• Alert on seq_tup_read growth per table, not just on slow queries. A slow-query log cannot see a million fast queries.
• Enable pg_stat_statements and sort by total time rather than mean time, which is the view that finds this class of problem — cheap statements with enormous call counts. Turn on track_planning while you are there: a trigger that re-planned on every call was invisible without it.
• Multiply in review. Any EXPLAIN on a function or embed gets a second line: how many times per request, and how many requests per day?

The one idea to take away

Per-scan cost is irrelevant when the multiplier is the outer row count.

The planner optimises one execution and it is usually right. The thing it cannot see is the loop you wrapped around it — a correlated subquery, a per-row embed, a function called from fourteen places — and that loop is where the cost lives. So when a tiny table shows up at the top of pg_stat_user_tables, do not reach for an index first. Ask what is scanning it in a loop, and make that scan happen once.

I write about backend reliability, Postgres data modelling and production failure modes from work on food-tech and healthcare platforms. More on what I build and how I work, the overload this diagnosis came out of, and the broader indexing and RPC techniques. The pg_stat_user_tables query above takes a second to run; run it on something today.