Composite indexes: column order and selectivity

Capsule description

The previous capsule taught you when a single-column B-tree index is used or not. Now we raise the stakes: queries with several simultaneous filters.

SELECT * FROM orders
WHERE customer_id = 42
  AND status = 'pending'
  AND created_at >= '2026-01-01';

Here you have three possible paths:

1. Create three separate indexes, one per column. PostgreSQL combines them with BitmapAnd.
2. Create a single composite index on (customer_id, status, created_at).
3. Create a composite with a different order, for example (status, customer_id, created_at).

All three options work in the sense that the query returns the correct results. But only one is optimal. And the difference between the best and the worst can be 20-50x in latency.

This capsule teaches you to choose. You'll learn the leftmost prefix rule (the most misunderstood rule of indexing), how to decide the column order based on selectivity and query patterns, and to always validate with EXPLAIN that the composite you designed is the one the planner uses.

Concrete objective: you'll be able to look at an endpoint with 2-4 filters and propose the right composite index, justifying the order by an analysis of selectivity and usage patterns.

The leftmost prefix rule: the heart of the composite

A composite index (a, b, c) is a B-tree where the keys are ordered tuples, first by a, then by b within each a, then by c within each (a, b).

Visualize it as a phone book ordered by (last name, first name, middle name):

García, Ana, María
García, Ana, Sofía
García, Carlos, Luis
García, Pedro, José
López, Ana, María
López, Beatriz, Elena
...

Which lookups are fast with that ordering?

The leftmost prefix rule: a composite (a, b, c) works for queries with WHERE a, WHERE a AND b, WHERE a AND b AND c. It does NOT work (or works poorly) for WHERE b, WHERE c, or WHERE b AND c.

The "leftmost prefix" means: the leftmost columns of the index are the ones that matter. You can "skip" columns on the right, but you can't skip columns on the left.

Subtle cases

Case 1: a range on the first column stops the prefix from being used

(a, b) with the query WHERE a > 10 AND b = 5:

• The index searches for all the rows with a > 10 (a range).
• Within each a, the bs are ordered, but the different a ranges are separated.
• The index can narrow by a > 10, but b = 5 is applied as a Filter after reading from the index. Not as efficient as if a were an equality.

Derived rule: put equalities before ranges in the composite. (status, created_at) is better than (created_at, status) for WHERE status = 'pending' AND created_at > X.

Case 2: order matters for ORDER BY

(a, b) orders by a and within each a by b. If your query is:

WHERE a = 5 ORDER BY b DESC LIMIT 10

The index already has the rows with a = 5 ordered by b. PostgreSQL can read the first 10 in reverse, without a separate Sort.

But if your query is:

WHERE a = 5 ORDER BY c DESC LIMIT 10

— the index doesn't help the ORDER BY (it doesn't include c in the order). You need (a, c) or a composite (a, b, c) where b isn't in the middle breaking the order.

Composite vs separate indexes: when each one wins

You have the query:

SELECT * FROM orders WHERE customer_id = 42 AND status = 'pending';

Option A: two separate indexes

CREATE INDEX idx_customer ON orders(customer_id);
CREATE INDEX idx_status ON orders(status);

PostgreSQL can combine them with Bitmap And:

Bitmap Heap Scan on orders
  Recheck Cond: ((customer_id = 42) AND (status = 'pending'::text))
  ->  BitmapAnd
        ->  Bitmap Index Scan on idx_customer
              Index Cond: (customer_id = 42)
        ->  Bitmap Index Scan on idx_status
              Index Cond: (status = 'pending'::text)

How it works: it reads from each index a bitmap with the rows that match each condition, does a logical AND of the bitmaps, goes to the heap to fetch only those that pass both.

Advantage: flexible. Each index also works for queries with a single filter (WHERE customer_id = X or WHERE status = Y).

Disadvantage: more operations. It reads two indexes, combines, goes to the heap. More buffers than a single composite that already knows the answer.

Option B: composite (customer_id, status)

CREATE INDEX idx_customer_status ON orders(customer_id, status);

Index Scan using idx_customer_status on orders
  Index Cond: ((customer_id = 42) AND (status = 'pending'::text))

How it works: it goes down the tree with customer_id = 42, within that range it goes down to status = 'pending', returns rows directly.

Advantage: faster for this exact query. A single pass through the index.

Disadvantage: it works for WHERE customer_id, it works for WHERE customer_id AND status, but it does NOT work for WHERE status alone (leftmost prefix rule).

Decision heuristic

Practical rule: if you have a query with N filters, start with a composite with those N filters. If you later see that you also need queries with subsets, evaluate: does the composite itself cover the subset via leftmost prefix? If yes, done. If not, evaluate adding a separate index.

How to choose the column order

Three criteria, in order of priority:

Criterion 1: equality before range

Columns with = (exact equality) should go before columns with <, >, BETWEEN, LIKE 'foo%'.

-- Query
WHERE status = 'pending' AND created_at > '2026-01-01'

-- ✅ Good: equality first
CREATE INDEX ON orders(status, created_at);

-- ❌ Bad: range first
CREATE INDEX ON orders(created_at, status);

Reason: the index narrows perfectly with the equality of status, and within that subset the range of created_at is consecutive.

Criterion 2: high selectivity before low selectivity

When both are equality, the more selective column (with more cardinality relative to the filter) usually goes first.

-- Query
WHERE customer_id = 42 AND status = 'pending'

-- customer_id: 50,000 distinct values in 5M rows → each value covers ~100 rows
-- status: 4 distinct values, 'pending' covers 5% → covers 250,000 rows

-- ✅ Good: customer_id (more selective) first
CREATE INDEX ON orders(customer_id, status);

Reason: going down the tree with customer_id = 42 leaves ~100 rows. Within that, filtering status = 'pending' is trivial. The other way around, going down with status = 'pending' leaves 250k rows, and within that, filtering by customer_id still narrows a lot — but the tree already traversed much more.

Exception: if one column is used always and the other sometimes, put the "always" one first, even if it's less selective. The composite will still be useful for the queries that only filter by the first one.

Criterion 3: order of ORDER BY and GROUP BY

If your query ends with ORDER BY column_X, consider including column_X in the composite in the same direction as the order, after the equality columns.

-- Query
WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 20

-- ✅ Good: the composite includes created_at in the expected order
CREATE INDEX ON orders(customer_id, created_at DESC);

Result: an Index Scan that already returns rows in DESC order. No additional Sort. LIMIT 20 cuts immediately.

(In PostgreSQL, the default order is ASC. Specify DESC if your ORDER BY requires it — a B-tree can be read in either direction, but sometimes the direction matters for complex combinations.)

Worked example: three queries, three indexes, decisions explained

You'll set up the dataset, see three problematic queries, design the right composite for each, and validate the plans.

Setup

Reuse the demo_orders from the previous capsule, or create it from scratch:

DROP TABLE IF EXISTS demo_orders;
CREATE TABLE demo_orders (
    id          BIGSERIAL PRIMARY KEY,
    customer_id INTEGER NOT NULL,
    status      TEXT NOT NULL,
    total       NUMERIC(10, 2) NOT NULL,
    created_at  TIMESTAMPTZ NOT NULL DEFAULT NOW()
);

INSERT INTO demo_orders (customer_id, status, total, created_at)
SELECT
    (random() * 50000)::INTEGER + 1,
    CASE
        WHEN random() < 0.95 THEN 'completed'
        WHEN random() < 0.99 THEN 'pending'
        ELSE 'cancelled'
    END,
    (random() * 1000)::NUMERIC(10, 2),
    NOW() - (random() * INTERVAL '365 days')
FROM generate_series(1, 500000);

ANALYZE demo_orders;

Query 1: filters by customer + status

SELECT * FROM demo_orders
WHERE customer_id = 42 AND status = 'pending';

Analysis:

• customer_id: high cardinality (50,000 values). customer_id = 42 covers ~10 rows.
• status: low cardinality (3 values). status = 'pending' covers ~20,000 rows.
• Both are equality. The more selective column in this case is customer_id.

Design: composite (customer_id, status).

CREATE INDEX idx_customer_status ON demo_orders(customer_id, status);

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM demo_orders WHERE customer_id = 42 AND status = 'pending';

Expected plan:

Index Scan using idx_customer_status on demo_orders
  Index Cond: ((customer_id = 42) AND (status = 'pending'::text))
  Buffers: shared hit=4
Planning Time: 0.345 ms
Execution Time: 0.123 ms

A single operation, 4 buffers, sub-millisecond. Ideal.

Query 2: filter by status + date range

SELECT * FROM demo_orders
WHERE status = 'pending' AND created_at >= '2026-01-01';

Analysis:

• status = 'pending' is equality. Covers ~20,000 rows (5%).
• created_at >= '2026-01-01' is a range. Covers a fraction of the year, say ~30%.
• Equality before range (criterion 1).

Design: composite (status, created_at).

CREATE INDEX idx_status_created ON demo_orders(status, created_at);

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM demo_orders
WHERE status = 'pending' AND created_at >= '2026-01-01';

Expected plan:

Index Scan using idx_status_created on demo_orders
  Index Cond: ((status = 'pending'::text) AND (created_at >= '2026-01-01 00:00:00+00'::timestamp with time zone))
  Buffers: shared hit=...

The index leverages the equality of status and within that subset traverses the date range consecutively.

Comparison with the wrong order: if you had created (created_at, status), the plan would do the range on created_at first (covers 30%) and then Filter: status = 'pending'. More buffers read, more rows discarded.

Query 3: filter + ordering + limit

SELECT * FROM demo_orders
WHERE customer_id = 42
ORDER BY created_at DESC
LIMIT 20;

Analysis:

• customer_id = 42 is equality on high cardinality. Returns ~10 rows.
• ORDER BY created_at DESC LIMIT 20 needs the rows ordered.

Design: composite (customer_id, created_at DESC). The order column goes after the equality, in the direction of the order.

CREATE INDEX idx_customer_created_desc ON demo_orders(customer_id, created_at DESC);

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM demo_orders
WHERE customer_id = 42
ORDER BY created_at DESC
LIMIT 20;

Expected plan:

Limit
  ->  Index Scan using idx_customer_created_desc on demo_orders
        Index Cond: (customer_id = 42)
  Buffers: shared hit=...

No separate Sort. The index is already ordered, it reads the first 20 and finishes.

Without the right index (say only (customer_id) with no order): the plan would have an extra Sort between the Index Scan and the Limit. Tolerable for 10 rows, a serious problem if in another query the customer_id covered 50k rows that have to be sorted.

Why does this matter in real work?

1. A poorly ordered composite = an index that isn't used.

The most common mistake: adding columns to the composite in the order they appear in the query (or alphabetical) without thinking about selectivity. The index exists but the planner ignores it because another plan is cheaper. Wasted tablespace, slowed-down writes, zero benefit.

2. The conversation with the team becomes technical.

In a PR review, "I added a composite because the query needed it" is a junior answer. "I added (customer_id, status) because customer_id has cardinality 50k and status covers 5% for pending; the composite favors equality-before-low-selectivity, and I validated with EXPLAIN that it now does a direct Index Scan instead of a Bitmap And" is a senior answer.

3. You reduce the total number of indexes.

A well-designed composite replaces two or three separate indexes. Fewer indexes = faster writes, less disk, less to maintain in REINDEX.

4. You improve ORDER BY without a Sort.

Endpoints with pagination + filter (WHERE customer_id = X ORDER BY created_at DESC LIMIT 20) are ubiquitous. The composite that respects the order eliminates the Sort and dramatically reduces p99.

Traps and common mistakes

Mistake 1 (conceptual): assuming a composite (a, b) works for WHERE b

Symptom: "I have idx_orders_customer_status and the query WHERE status = 'pending' is still slow."

Why it happens: the leftmost prefix rule. (customer_id, status) is ordered first by customer_id. To search only by status, PostgreSQL would have to scan the whole index, which generally doesn't help over Seq Scan. (There's a pattern called "skip scan" in other databases that helps this case, but PostgreSQL doesn't implement it to date.)

How to detect: EXPLAIN shows Seq Scan or uses another index.

How to fix it: if you need to filter only by status frequently, add a separate index or reverse the composite. But first evaluate: is it really useful to index status alone? If it covers 5%, yes (partial index, capsule 05); if it covers 95%, no.

Mistake 2 (practical): putting columns in the composite in the order of the query

Symptom: the query is WHERE status = 'pending' AND customer_id = 42, so you create (status, customer_id).

Why it's sometimes sub-optimal: the order of columns in the WHERE doesn't matter for the result, but it matters a lot for the composite's order. What matters is selectivity.

How to fix it: decide the order by an analysis of selectivity and usage patterns, not by the textual order of the query. PostgreSQL applies WHERE a AND b the same as WHERE b AND a.

Mistake 3 (conceptual): huge composites "just in case"

Symptom: CREATE INDEX ON orders(customer_id, status, created_at, total, currency, region); to "cover everything".

Why it's wrong: the index becomes huge. Each added column increases its size on disk. More importantly: the leftmost prefix rule means the columns on the right only help if the ones on the left are in the WHERE. If nobody filters by (customer_id, status, created_at, total, currency) but only by the first three, the last two are dead weight.

How to fix it: keep composites to 2-4 columns maximum. If you need to return extra columns without filtering by them, consider covering indexes with INCLUDE (capsule 04).

Mistake 4 (conceptual): ignoring that a range "breaks" the prefix

Symptom: you create (created_at, status) for WHERE created_at >= X AND status = 'pending', thinking the composite covers both.

Why it's sub-optimal: the range on created_at covers many rows. Within each distinct created_at, the statuses are ordered, but the planner can't jump between created_at ranges and apply the status equality efficiently. The status is applied as a post-index Filter.

How to detect: EXPLAIN shows Index Cond: (created_at >= ...) and Filter: (status = 'pending') separately.

How to fix it: reverse the order: (status, created_at). The status equality narrows first, and within that the created_at range is efficient.

Mistake 5 (practical): not validating that the composite is used

Symptom: you create the composite, assume it's set, and months later discover that the plan still shows Bitmap And with old indexes.

Why it happens: the planner may prefer another combination if the statistics or costs don't fit. Or the composite became invalid after a pg_upgrade.

How to fix it: capture EXPLAIN (ANALYZE, BUFFERS) after creating the index. Confirm that the plan mentions the composite by name. If it doesn't use it, investigate (capsule 02 trap #2).

Mistake 6 (conceptual): a composite for every possible permutation

Symptom: three columns, you create (a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a). Six indexes.

Why it's wrong: you're multiplying write and disk overhead by six. The leftmost prefix rule already gives you several prefixes for free with a single composite.

How to fix it: decide which is the optimal order for your main query pattern. Accept that some secondary combinations will be less optimal. If a specific combination is critical and doesn't fit the main composite, add one extra index. Not six.

Exercises

Exercise 1: leftmost prefix rule, prediction

You have the composite (country, city, postal_code) on an addresses table. For each query, predict whether the composite is used efficiently.

1. WHERE country = 'AR'
2. WHERE country = 'AR' AND city = 'Córdoba'
3. WHERE country = 'AR' AND city = 'Córdoba' AND postal_code = '5000'
4. WHERE city = 'Córdoba' (without country)
5. WHERE country = 'AR' AND postal_code = '5000' (without city)
6. WHERE postal_code = '5000' (only postal)
7. WHERE country LIKE 'A%'

Exercise 2: design a composite for a catalog query

You have this query from a product catalog endpoint:

SELECT id, name, price
FROM products
WHERE category_id = 5
  AND in_stock = true
ORDER BY price ASC
LIMIT 24;

Data:

• products: 800,000 rows.
• category_id: 50 categories, relatively uniform distribution (~16,000 products per category).
• in_stock: boolean, ~70% in stock.
• price: float, high cardinality, queries order by it frequently.

Design the composite and justify the column order.

CREATE INDEX idx_products_cat_stock_price
ON products(category_id, in_stock, price);

Limit
  ->  Index Scan using idx_products_cat_stock_price on products
        Index Cond: ((category_id = 5) AND (in_stock = true))

Exercise 3: evaluate composite vs separate indexes

An events table has three common queries:

• Query A: WHERE user_id = X (95% of the time)
• Query B: WHERE event_type = 'login' (rare, almost never)
• Query C: WHERE user_id = X AND event_type = 'login' (occasional)

How many indexes would you create and of what type?

Exercise 4: detect a poorly ordered index in a plan

You have the query:

SELECT * FROM logs
WHERE created_at >= '2026-05-01' AND severity = 'ERROR';

The current plan:

Bitmap Heap Scan on logs
  Recheck Cond: ((created_at >= '2026-05-01'::date) AND (severity = 'ERROR'::text))
  ->  Bitmap Index Scan on idx_logs_created_severity
        Index Cond: ((created_at >= '2026-05-01'::date) AND (severity = 'ERROR'::text))
  Buffers: shared hit=15000
Execution Time: 450ms

severity = 'ERROR' covers 2% of the logs. created_at >= '2026-05-01' covers 30%.

What problem do you detect? What would you change?

CREATE INDEX idx_logs_severity_created ON logs(severity, created_at);
DROP INDEX idx_logs_created_severity;

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM logs
WHERE created_at >= '2026-05-01' AND severity = 'ERROR';

Index Scan using idx_logs_severity_created on logs
  Index Cond: ((severity = 'ERROR'::text) AND (created_at >= '2026-05-01'::date))
  Buffers: shared hit=...  ← significantly less
Execution Time: ...ms      ← much faster

Exercise 5: composite with ORDER BY

You have:

SELECT * FROM messages
WHERE channel_id = 42
ORDER BY sent_at DESC
LIMIT 50;

Design the composite. Then answer: what would happen if the query were ORDER BY sent_at ASC with the same index?

Limit
  ->  Index Scan using idx_messages_channel_sent on messages
        Index Cond: (channel_id = 42)

Limit
  ->  Index Scan Backward using idx_messages_channel_sent on messages
        Index Cond: (channel_id = 42)

Exercise 6: apply it to your own case

Take a real query from your project (or from the module 1 bookstore) that has 2-3 filters and/or an ORDER BY. Follow these steps:

1. Capture the current plan with EXPLAIN (ANALYZE, BUFFERS).
2. Note the cardinality and estimated selectivity of each WHERE column.
3. Design the composite following the criteria.
4. Create the index and capture the plan afterward.
5. Compare Execution Time and Buffers.

## Index design: [endpoint name/description]

**Query:**
```sql
SELECT ... FROM ... WHERE col_a = X AND col_b > Y ORDER BY col_c LIMIT N;

Seq Scan on table
  Filter: ...
  Rows Removed by Filter: ...
  Buffers: shared hit=A read=B
Execution Time: X ms

CREATE INDEX idx_... ON table(col_a, col_b, col_c);
-- Reasons: equality-range-order, leftmost prefix covers Q1 and Q2 too.

Index Scan using idx_... on table
  Index Cond: ...
  Buffers: shared hit=...
Execution Time: ... ms

If your improvement is <2x, consider whether the index was worth it (remember: it costs writes and disk). If your improvement is 10x+, a clear winner.

</details>

---

## Summary and next step

In this capsule you learned:

- A **composite index** `(a, b, c)` is ordered first by `a`, then by `b` within `a`, etc.
- **Leftmost prefix rule:** it works for `WHERE a`, `WHERE a AND b`, `WHERE a AND b AND c`. It does NOT work efficiently for `WHERE b` or `WHERE c` alone.
- **Criterion 1 — equality before range:** `(status, created_at)` for `WHERE status = X AND created_at > Y`.
- **Criterion 2 — high selectivity before low:** the column that narrows the most goes first.
- **Criterion 3 — order of `ORDER BY`:** the order column goes at the end of the composite (equalities first, order after).
- **Composite vs separate indexes:** composite wins when the filters almost always go together. Separate ones win when they're used independently most of the time.
- **Keep composites small** (2-4 columns). To return extra columns without filtering by them, use covering indexes with `INCLUDE` (next capsule).

Before moving on, you should be able to:

- Apply the leftmost prefix rule to predict which queries a composite leverages.
- Decide the column order using the three criteria.
- Validate with `EXPLAIN` that the composite you designed is the one the planner is using.
- Differentiate when a composite vs separate indexes is preferable.

**Next capsule — Covering indexes with `INCLUDE`.** Your composite covers the `WHERE`, perfect. But PostgreSQL still has to go to the heap to return the columns the query projects (`SELECT col_x, col_y, ...`). That's extra overhead. Capsule 04 teaches you how to add non-key columns to the index with `INCLUDE`, enabling an `Index Only Scan` that doesn't even touch the heap. The difference: going from an `Index Scan` with 5,000 buffers read to an `Index Only Scan` with 50.

---

## Resources

1. [Markus Winand — Use The Index, Luke! — "The Equality Operator"](https://use-the-index-luke.com/sql/where-clause/the-equals-operator/concatenated-keys) — the canonical explanation of composite indexes with excellent visualizations.
2. [Markus Winand — Use The Index, Luke! — "Slow Indexes Part I"](https://use-the-index-luke.com/sql/anatomy/slow-indexes) — why an index that "exists but isn't used" isn't an index.
3. [PostgreSQL Documentation — Multicolumn Indexes](https://www.postgresql.org/docs/16/indexes-multicolumn.html) — the official chapter on composites in PostgreSQL 16.
4. [PostgreSQL Documentation — Combining Multiple Indexes](https://www.postgresql.org/docs/16/indexes-bitmap-scans.html) — how PostgreSQL combines several indexes with `BitmapAnd` / `BitmapOr`.
5. [Hubert "depesz" Lubaczewski — "Picking the right composite index"](https://www.depesz.com/2018/11/12/picking-the-right-composite-index/) — a real case of deciding column order with before/after plans.
6. [Bruce Momjian — "Indexing Mistakes"](https://momjian.us/main/writings/pgsql/index_mistakes.pdf) — indexing anti-patterns from the core team, an entire section on composites.
7. [Tom Lane on multicolumn index usage](https://www.postgresql.org/message-id/15704.1352746906@sss.pgh.pa.us) — the canonical explanation of when PostgreSQL chooses a composite vs a combination of simple indexes.

---

*Module 3 — Database Performance & Query Tuning Guide*