Data & Databases

Indexes and Execution Plans: Making the Optimizer Work for You

Advanced9 min readUpdated

An index is a data structure with rules, and an execution plan is the optimizer telling you which rules it could use. This guide covers how B-trees answer queries, how to order the columns of a composite index, when specialised index types beat a B-tree, how statistics drive cost estimates, and how to read EXPLAIN ANALYZE closely enough to find the node where an estimate went wrong.

What you will learn

  • Explain how a B-tree index answers equality, range and ordering requests
  • Order the columns of a composite index and decide when to add included columns
  • Choose between B-tree, hash, GIN, BRIN, bitmap, partial and expression indexes
  • Read EXPLAIN ANALYZE output and locate the node whose estimate diverged from reality
  • Diagnose why the planner chose a bad plan and fix the cause rather than the symptom

Every relational engine ships an optimizer that decides how to execute your query, and every optimizer is a cost model fed by statistics. When a query is slow, the interesting question is not "which index should I add" but "what did the optimizer believe, and where was it wrong". The execution plan is the only place that answer lives.

This guide assumes you already write predicates the optimizer can use — functions off the indexed column, no implicit conversions, the habits covered in SQL best practices. What follows is the layer underneath: what an index physically is, what makes it usable, and how to read a plan closely enough to act on it. Examples use PostgreSQL 17 syntax with Oracle equivalents noted.

What a B-tree can and cannot do

Nearly every index you create is a balanced tree of sorted keys. Internal pages hold separator keys that route a search; leaf pages hold the keys in order, each with a pointer to the row (a heap tuple identifier in PostgreSQL, a ROWID in Oracle). Leaf pages are linked, so once a search lands, the engine can walk forwards or backwards without returning to the root.

That structure supports exactly four things, and understanding them explains almost every index question:

  1. Equality lookup. Descend to the first matching key. Cost is logarithmic in the row count — three or four page reads on a large table.
  2. Range scan. Descend once, then walk the leaves while the key still satisfies the bound. >, <, BETWEEN and prefix LIKE 'abc%' all reduce to this.
  3. Ordering. Leaves are already sorted, so an index can supply ORDER BY without a sort step, which matters enormously when combined with LIMIT.
  4. Uniqueness. A unique index is how the engine enforces primary keys and unique constraints.

What it cannot do is answer anything that does not start at a known point in the key order. LIKE '%invoice%' has no starting prefix. Neither does a predicate on the second column of a composite index when the first is unconstrained — although PostgreSQL 18 softened this with skip scan, which probes each distinct leading value when that column has few distinct values. Treat that as a safety net, not a design principle.

Composite indexes: column order is the design

An index on (a, b, c) sorts rows by a, then by b within equal a, then by c. The consequence: the index is usable for a query that constrains a leading prefix of those columns. WHERE a = ? uses it, WHERE a = ? AND b = ? uses it better, WHERE b = ? alone essentially cannot.

The rule that follows is worth memorising: equality columns first, then the column you range-scan or sort by. Once the scan hits a range predicate, everything after it in the index is no longer usable for further seeking — only for filtering the rows the range returns.

-- Query: recent unpaid invoices for one customer
SELECT id, issued_at, amount
FROM   invoice
WHERE  customer_id = $1 AND status = 'UNPAID' AND issued_at >= $2
ORDER  BY issued_at DESC
LIMIT  50;

-- Equalities first, range/sort column last
CREATE INDEX invoice_cust_status_issued
  ON invoice (customer_id, status, issued_at DESC);

This index answers the whole query with one range scan and no sort. Swap the columns to (issued_at, customer_id, status) and the engine must scan every invoice since $2 and filter, which is fine on a small table and disastrous on a large one.

A covering index goes one step further: if the index contains every column the query touches, the engine never visits the table at all. PostgreSQL reports this as an Index Only Scan, and it is only possible when the visibility map says the relevant pages are all-visible — which is another reason autovacuum matters, as discussed in the Oracle and PostgreSQL comparison. Columns needed only for output, never for filtering or ordering, belong in INCLUDE rather than in the key, which keeps the tree narrower:

CREATE INDEX invoice_cust_issued_covering
  ON invoice (customer_id, issued_at DESC) INCLUDE (amount, status);

Selectivity and statistics

The optimizer chooses between an index scan and a sequential scan on estimated selectivity: the fraction of rows a predicate keeps. An index is worth using when that fraction is small, because each matching row may cost a random page read. Once the fraction rises past a few percent of a large table, reading everything sequentially is cheaper. This is why a status column with two values almost never benefits from a plain B-tree, and why nobody should be surprised when an index on it goes unused.

Selectivity estimates come from statistics gathered by ANALYZE (PostgreSQL, run automatically by autovacuum) or DBMS_STATS (Oracle): the number of distinct values per column, the fraction of nulls, a list of most common values with their frequencies, and a histogram of the rest. Three situations break them:

  • Stale statistics after a bulk load or a mass update. The fix is to run ANALYZE as the last step of any ETL job.
  • Correlated columns. The planner assumes independence, so WHERE city = 'Lyon' AND country = 'FR' is estimated by multiplying two selectivities even though the first implies the second, producing an estimate that is wildly too low. PostgreSQL's answer is extended statistics: CREATE STATISTICS city_country (dependencies, ndistinct) ON city, country FROM address;
  • Skew. A column where one value covers 90% of rows needs a histogram and, in Oracle, benefits from adaptive cursor sharing so that different bind values can get different plans.

Raising default_statistics_target (or the per-column equivalent) makes histograms finer at the cost of slower analysis. Do it for the few columns with genuinely awkward distributions, not globally.

Index types beyond the B-tree

TypeGood forNotes
B-treeEquality, ranges, ordering, uniquenessThe default; the only type that supports ORDER BY cheaply
Hash (PostgreSQL)Simple equality on large keysCrash-safe and WAL-logged since 10, but no ranges, no ordering
GINMulti-valued columns: jsonb, arrays, full textInverted structure; slow to update, fast to search
GiST / SP-GiSTGeometric, range and nearest-neighbour queriesExtensible framework, used by PostGIS
BRINVery large tables where a column correlates with physical orderTiny; stores min/max per block range, ideal for append-only timestamps
Bitmap (Oracle)Low-cardinality columns in read-mostly warehousesCombines cheaply with AND/OR; locks whole bitmap segments, so unsuitable for OLTP

Two modifiers apply to any of them. A partial index stores only rows matching a predicate, which is perfect when queries always target a small subset: CREATE INDEX ON job (created_at) WHERE status = 'PENDING'; gives you a tiny index over a queue table regardless of how much completed history piles up. An expression index stores the result of a function, restoring index usability for a predicate that would otherwise be non-sargable: CREATE INDEX ON person (lower(email)); is used by WHERE lower(email) = $1, provided the query repeats the expression exactly.

PostgreSQL also builds bitmap heap scans on the fly: it collects matching tuple identifiers from one or more indexes into an in-memory bitmap, sorts them by physical location, then reads the heap in order. That is how two separate single-column indexes can cooperate on an AND or OR — usefully, but never as well as one well-ordered composite index.

Reading EXPLAIN ANALYZE

Ask for the measured version, with buffers, and read it as a tree that executes from the innermost node outwards:

EXPLAIN (ANALYZE, BUFFERS, VERBOSE)
SELECT c.name, sum(i.amount)
FROM   customer c
JOIN   invoice i ON i.customer_id = c.id
WHERE  i.issued_at >= date '2026-01-01'
GROUP  BY c.name;
HashAggregate  (cost=18422.10..18560.42 rows=11066 width=40)
               (actual time=214.883..218.014 rows=10871 loops=1)
  Group Key: c.name
  ->  Hash Join  (cost=612.00..17250.44 rows=234332 width=36)
                 (actual time=6.201..168.442 rows=233980 loops=1)
        Hash Cond: (i.customer_id = c.id)
        ->  Index Scan using invoice_issued_at_idx on invoice i
              (cost=0.43..14887.02 rows=234332 width=12)
              (actual time=0.038..92.117 rows=233980 loops=1)
              Index Cond: (issued_at >= '2026-01-01'::date)
              Buffers: shared hit=4210 read=8891
        ->  Hash  (cost=474.00..474.00 rows=11040 width=32)
                  (actual time=6.104..6.105 rows=11040 loops=1)
              ->  Seq Scan on customer c  (cost=0.00..474.00 rows=11040 width=32)
Planning Time: 0.412 ms
Execution Time: 219.774 ms

Read it in this order:

  1. Compare rows= estimated with rows= actual on every node. A factor of ten or more is the signal you are looking for, and the lowest node where it appears is the cause; everything above it inherits the error. Here the estimates are excellent, so the plan shape is trustworthy.
  2. Multiply by loops. Actual row counts and times inside a nested loop are per iteration. A node reporting 3 rows and 0.2 ms with loops=50000 consumed ten seconds.
  3. Look at Buffers. shared hit came from cache, read came from the operating system, and temp read/written means an operation spilled to disk — usually a sort or hash that exceeded work_mem.
  4. Distinguish Index Cond from Filter. An index condition narrows the scan; a filter is applied to rows the scan already returned. Rows Removed by Filter: 480000 means you fetched half a million rows to throw them away.
  5. Check timing at the top. A large planning time relative to execution suggests too many partitions or an over-indexed table.

The join operators tell their own story. Nested Loop probes the inner relation once per outer row, which is optimal when the outer side is tiny and the inner probe is indexed, and catastrophic when the outer estimate was wrong. Hash Join builds a hash table of the smaller input and streams the larger past it — the usual choice for large equijoins. Merge Join consumes both sides in sorted order, which is cheap when indexes already supply the order and expensive when it forces two sorts. Oracle's plan output names the same three shapes and adds HASH JOIN distribution methods in parallel execution.

When the planner gets it wrong

Bad plans nearly always trace back to a bad estimate, and there is a short list of causes:

  • A wrong row estimate, from stale statistics, correlated columns, or a predicate the optimizer cannot see through — a function call, a value hidden behind an opaque bind, or a join on an expression.
  • Parameter sensitivity. A prepared statement's generic plan may be built for an average value and then be reused for a highly skewed one. PostgreSQL replans custom plans for the first executions and can fall back to a generic one; setting plan_cache_mode = force_custom_plan on the session diagnoses this. Oracle calls the same phenomenon bind peeking and mitigates it with adaptive cursor sharing.
  • A missing index, or an index whose column order does not fit the predicate.
  • Cost-model mismatch. Default random_page_cost of 4.0 assumes spinning disks. On SSDs, lowering it to 1.1 legitimately shifts the balance towards index scans.
  • Insufficient work_mem, forcing a hash or sort to spill; the plan is right but the execution is not.

An ORM adds a layer of indirection but changes none of this: the generated SQL still has a plan, and lazy loading still turns one query into a thousand — see Spring Data JPA for how to fetch in sets instead.

The cost of an index

Indexes are not free, and the invoice arrives on the write path. Every insert and delete updates every index on the table; an update touches the indexes whose columns it changes, plus all of them if the row cannot stay on its page. Indexes also occupy cache that data pages would otherwise use, and they bloat: a heavily updated index accumulates dead entries until it is rebuilt. PostgreSQL's REINDEX INDEX CONCURRENTLY rebuilds without taking a disruptive lock, and CREATE INDEX CONCURRENTLY adds one to a live table at the cost of two table passes.

Before adding an index, check whether an existing one can be extended instead — an index on (customer_id) is redundant once (customer_id, issued_at) exists. Before keeping one, check whether anything uses it:

SELECT relname, indexrelname, idx_scan, pg_size_pretty(pg_relation_size(indexrelid))
FROM   pg_stat_user_indexes
WHERE  idx_scan = 0
ORDER  BY pg_relation_size(indexrelid) DESC;

Zero scans since the last statistics reset, on a table that is queried, means the index is pure overhead — unless it backs a constraint. Design the schema well first, as covered in database design and normalization; indexes correct for access patterns, they do not rescue a broken model.

Key takeaways

  • A B-tree serves equality, ranges, ordering and uniqueness from a sorted structure, and can only start a scan from a known prefix of its key.
  • In a composite index, put equality columns first and the range or sort column last; add non-filtered output columns with INCLUDE to enable index-only scans.
  • The optimizer chooses on estimated selectivity, so wrong statistics — stale, correlated or skewed — are the usual root cause of a bad plan.
  • Beyond B-trees, use GIN for multi-valued data, BRIN for huge correlated tables, bitmap indexes for read-mostly warehouses, and partial or expression indexes to make a small subset cheap.
  • Read EXPLAIN ANALYZE from the innermost node out, compare estimated with actual rows, multiply by loops, and watch for rows removed by filter and spills to temp files.
  • Every index taxes writes and consumes cache: extend an existing index rather than adding a near-duplicate, and drop what pg_stat_user_indexes shows nothing uses.

Sources and further reading

Frequently asked questions

Why is the database ignoring my index?
Usually because using it would be slower. If a predicate matches a large share of the table, reading the index and then fetching each matching row from the heap costs more random I/O than one sequential pass. Check the estimated versus actual row counts in EXPLAIN ANALYZE first: when they differ by an order of magnitude, the problem is stale or insufficient statistics, not the index.
How many indexes is too many?
There is no fixed number, but every index is written on every insert and delete, and on updates that touch its columns, so write throughput falls as the count grows. A practical audit is to list indexes with no scans recorded in pg_stat_user_indexes since the last reset, check for duplicates whose columns are a prefix of another index, and drop what nothing uses.
What is the difference between EXPLAIN and EXPLAIN ANALYZE?
EXPLAIN shows the plan the optimizer chose along with its cost and row estimates, without running the query. EXPLAIN ANALYZE actually executes it and adds measured timings, real row counts and loop counts, which is what lets you compare estimate against reality. Because it runs the statement, wrap data-modifying queries in a transaction you roll back.
Should I use optimizer hints to force a plan?
Only as a temporary measure with a note explaining why. A hint freezes a decision that was correct for one data distribution and one release, and it hides the underlying cause — usually a missing index, a stale statistic or a predicate the planner cannot estimate. Fix the cause, then remove the hint and confirm the plan stayed good.