What is a composite index

A composite index (also referred to as a compound, multi-column, or concatenated index) is an index created across two or more columns of a single database table simultaneously.

🟢 Junior Level

A composite index (also referred to as a compound, multi-column, or concatenated index) is an index created across two or more columns of a single database table simultaneously.

Why Use Composite Indexes?

A single well-designed composite index can satisfy queries that filter or sort by multiple columns together, often replacing several single-column indexes. This saves disk storage, reduces RAM cache requirements, and dramatically minimizes write amplification during INSERT, UPDATE, and DELETE operations.

Simple Analogy

Think of a physical telephone directory sorted first by Last Name, and second by First Name:

You can locate "Smith, John" instantly because the directory is ordered by last name, then first name.
You can locate all "Smith" entries with a fast contiguous range scan.
But if you only know the first name "John", the directory order is useless — you would have to scan the entire book from beginning to end.

The Leftmost Prefix Rule

The single most important principle of composite B-trees is the Leftmost Prefix Rule:

A composite index on columns (A, B, C) can only be used by queries that filter on the leading columns in strict sequential order from left to right.

-- Create a composite index on (city, age)
CREATE INDEX idx_users_city_age ON users(city, age);

-- ✅ Uses index: leading column 'city' is provided
SELECT * FROM users WHERE city = 'Chicago';

-- ✅ Uses index: both leading columns 'city' and 'age' are provided
SELECT * FROM users WHERE city = 'Chicago' AND age = 30;

-- ❌ CANNOT effectively use index: leading column 'city' is missing
SELECT * FROM users WHERE age = 30;

🟡 Middle Level

How It Works Internally: Lexicographical Ordering

In a composite B-tree, keys are stored in a strict hierarchical (lexicographical) sort order:

All rows are sorted primarily by the 1st column.
For identical values of the 1st column, rows are sorted by the 2nd column.
For identical values of the 1st and 2nd columns, rows are sorted by the 3rd column, and so on.

Composite B-Tree Leaf Page Layout:
┌──────────────────┬──────────────────┬────────────────────────┐
│ Column 1: city   │ Column 2: age    │ TID Pointer (Heap Row) │
├──────────────────┼──────────────────┼────────────────────────┤
│ 'Berlin'         │ 22               │ (Block 4, Offset 1)    │
│ 'Berlin'         │ 28               │ (Block 4, Offset 2)    │
│ 'Berlin'         │ 35               │ (Block 5, Offset 1)    │
│ 'London'         │ 19               │ (Block 5, Offset 2)    │
│ 'London'         │ 40               │ (Block 6, Offset 1)    │
│ 'Madrid'         │ 31               │ (Block 6, Offset 2)    │
└──────────────────┴──────────────────┴────────────────────────┘

Notice that the values of age are only sorted within each individual city. Globally, age values (22, 28, 35, 19, 40, 31) are scattered and unordered.

The Golden Rule of Column Ordering

When designing a composite index, structure column positions according to the universal access pattern:

\[\text{Equality Columns } (=) \longrightarrow \text{Range Columns } (<, >, \text{BETWEEN}) \longrightarrow \text{Sort / Payload Columns } (\text{ORDER BY} / \text{INCLUDE})\]

1. Equality Columns Before Range Columns

-- Target Query:
SELECT * FROM users WHERE city = 'Berlin' AND age >= 25;

-- ✅ CORRECT: Equality column 'city' first, Range column 'age' second
CREATE INDEX idx_users_city_age ON users(city, age);

-- ❌ SUBOPTIMAL: Range column first
CREATE INDEX idx_users_age_city ON users(age, city);

Why? When the query engine navigates idx_users_age_city, the condition age >= 25 matches a broad range of leaf pages. Because city is nested under each different age, the value 'Berlin' is scattered across multiple disjoint locations in the index, preventing contiguous B-tree seeking.

2. Filtering Combined with Sorting (`ORDER BY`)

-- Target Query:
SELECT order_id, total_amount 
FROM orders 
WHERE customer_id = 42 
ORDER BY created_at DESC 
LIMIT 10;

-- ✅ Ideal Index: Filters customer_id and directly returns rows in pre-sorted order
CREATE INDEX idx_orders_customer_date 
ON orders(customer_id, created_at DESC);

Composite Index vs. Multiple Single-Column Indexes

Scenario	Separate Single Indexes: `idx(A)` + `idx(B)`	Single Composite Index: `idx(A, B)`
`WHERE A = 1`	✅ Fast Index Scan on `idx(A)`	✅ Fast Index Scan on `idx(A, B)`
`WHERE B = 2`	✅ Fast Index Scan on `idx(B)`	❌ Cannot use `idx(A, B)` (Leftmost prefix violated)
`WHERE A = 1 AND B = 2`	⚠️ Bitmap Index Scan (reads two indexes, builds two bitmaps, performs bitwise AND, then reads heap)	✅ Instant, single-pass direct Index Scan
Write Overhead	🔴 2 index updates on every `INSERT`/`DELETE`	🟢 1 index update on every `INSERT`/`DELETE`
Storage Footprint	🔴 2 distinct B-trees (high page overhead)	🟢 1 consolidated B-tree

🔴 Senior Level

Architectural Trade-offs: Composite Index vs. Covering Index (`INCLUDE`)

Introduced in PostgreSQL 11, the INCLUDE clause allows storing non-key payload attributes directly in B-tree leaf pages without including them in navigation keys:

-- Scenario: High-frequency customer lookup projecting status and amount
-- 1. Standard Composite Index:
CREATE INDEX idx_orders_composite ON orders(customer_id, status, amount);

-- 2. Covering Index with INCLUDE:
CREATE INDEX idx_orders_covering ON orders(customer_id) INCLUDE (status, amount);

Detailed Comparison:

Feature	Composite Index `(a, b)`	Covering Index `(a) INCLUDE (b)`
B-tree Depth	Deeper (wide keys on root/internal nodes reduce fan-out)	Shallower (internal nodes contain only column `a`)
Usable in `WHERE b = 42`	✅ Yes, when `a` is also in `WHERE`	❌ No, `b` cannot be used to navigate the index tree
Usable in `ORDER BY a, b`	✅ Yes, pre-sorted by `(a, b)`	❌ No, `b` is unordered in the leaf pages
Index-Only Scans	✅ Yes	✅ Yes (payload `b` retrieved from leaf page)
Unique Constraints	Enforces uniqueness across `(a, b)`	Enforces uniqueness only on column `a`

Emulating Index Skip Scan via Recursive CTE

Unlike Oracle or MySQL 8.0+, PostgreSQL currently lacks a native Index Skip Scan. If a composite index exists on (status, user_id) where status has very low cardinality ('ACTIVE', 'INACTIVE', 'PENDING'), querying solely by WHERE user_id = 999 normally causes PostgreSQL to fall back to a full table Seq Scan.

You can emulate an ultra-fast Skip Scan using a Recursive CTE:

-- Emulates native Skip Scan across a low-cardinality leading prefix column
WITH RECURSIVE skip_scan AS (
    -- Anchor member: Find the lowest status
    (SELECT MIN(status) AS status FROM orders)
    UNION ALL
    -- Recursive member: Find the next distinct status
    SELECT (
        SELECT MIN(status) 
        FROM orders 
        WHERE status > s.status
    )
    FROM skip_scan s 
    WHERE s.status IS NOT NULL
)
SELECT o.*
FROM skip_scan s
JOIN LATERAL (
    -- Performs a fast point-lookup for each distinct status
    SELECT * 
    FROM orders 
    WHERE status = s.status AND user_id = 999
) o ON true;
-- Turns a 25-second sequential scan on a 50M-row table into a ~1.5 ms index seek!

Multi-Column Sort Directionality (Mixed Sorting)

PostgreSQL B-trees are bidirectional: an index on (a ASC, b ASC) can seamlessly execute ORDER BY a DESC, b DESC by reading leaf pages backwards via P_PREV.
However, it CANNOT satisfy mixed sort directions without an expensive in-memory sort:

-- Query requiring mixed sorting:
SELECT * FROM leaderboard ORDER BY score DESC, created_at ASC;

-- ❌ CANNOT avoid in-memory Sort node with standard index:
CREATE INDEX idx_bad ON leaderboard(score, created_at);

-- ✅ Avoids sorting completely:
CREATE INDEX idx_good ON leaderboard(score DESC, created_at ASC);

4 Tricky Questions

1. In a query `WHERE a = 10 AND b > 100 AND c = 'ACTIVE'`, how does a composite index on `(a, b, c)` utilize column `c`?

Answer:
Column c is NOT used for B-tree index navigation (range narrowing).

Column a and column b are evaluated as Index Cond (index seek predicates). They determine the start and stop boundaries of the B-tree leaf page traversal.
Because b is an inequality range (> 100), values of c are no longer contiguous across the search range.
However, column c is evaluated on the index leaf page as an Index Filter predicate before accessing the table heap. While it cannot reduce the number of index pages read, it saves substantial heap I/O by discarding non-matching tuples before touching the table.

2. If you already have a composite index on `(a, b)`, is there any reason to keep an index on `(a)` alone? What about an index on `(b)` alone?

Answer:

Index on (a) alone: Almost always completely redundant! The composite index (a, b) can satisfy all equality, range, and sorting queries on a via the Leftmost Prefix Rule. You should drop idx(a) to save write I/O, unless (a, b) is exceptionally wide and (a) is queried millions of times per second with strict in-memory cache constraints.
Index on (b) alone: Must be kept! The composite index (a, b) cannot be used by queries that filter solely on b without a.

3. Can a composite index enforce a uniqueness constraint while including unindexed payload columns?

Answer:
Yes, using the UNIQUE ... INCLUDE syntax:

CREATE UNIQUE INDEX idx_users_email_include_profile 
ON users(email) INCLUDE (display_name, avatar_url);

This guarantees that email remains globally unique, while allowing queries like SELECT display_name, avatar_url FROM users WHERE email = ? to execute as an Index Only Scan. Storing payload columns under INCLUDE prevents them from participating in the uniqueness constraint.

4. What is the impact of column order in `(a, b)` if both columns are always filtered using exact equality (`WHERE a = ? AND b = ?`)?

Answer:
If both columns are always queried together with equality (=), the query planner executes with identical performance regardless of whether the index is (a, b) or (b, a).
However, the tie-breaker should be chosen based on secondary query patterns:

Partial queries: Place the column that is more frequently queried alone as the leading column.
Cardinality / Selectivity: If both are queried alone equally often, placing the column with higher cardinality first can marginally improve compression and deduplication in modern PostgreSQL B-trees.

🎯 Interview Cheat Sheet

Core Rules

Leftmost Prefix Rule: A composite index (A, B, C) can serve queries on A, (A, B), and (A, B, C). It cannot directly serve queries on B, C, or (B, C).
Optimal Column Order: Equality (=) columns first $\rightarrow$ Range (<, >, BETWEEN) columns second $\rightarrow$ Sort (ORDER BY) columns third $\rightarrow$ Payload (INCLUDE) columns last.
Redundancy Cleanup: If you have CREATE INDEX (a, b), drop CREATE INDEX (a).
Directionality: B-trees can scan backwards for identical direction (DESC, DESC matches ASC, ASC), but mixed direction (ASC, DESC) requires an explicit matching index definition.

Advanced Architectural Concepts

INCLUDE Clause: Keeps root and internal nodes narrow by storing non-search payload columns solely in leaf pages, boosting cache hit ratios for Index Only Scans.
Skip Scan Emulation: PostgreSQL lacks native B-tree Skip Scan; emulate it for low-cardinality prefixes via a Recursive CTE.
Max Recommended Columns: Keep composite indexes to 2–4 columns. Exceeding 5 columns causes leaf page bloat and harms buffer cache hit ratios.

Red Flags (What NOT to Say)

❌ “The database optimizer can rearrange the composite index to match any WHERE clause.” (The optimizer cannot alter the physical layout of the B-tree).
❌ “It’s better to create separate single-column indexes on every column and let PostgreSQL bitmap-join them.” (A composite index is significantly faster, executes in a single pass, and avoids bitmap creation overhead).
❌ “Range columns should go first because they eliminate the most rows.” (Range columns placed first break B-tree navigation for all subsequent columns).

What are indexes and why are they needed — Index fundamentals and scan types
How does B-tree index work — Internal multi-way search tree mechanics
What is index cardinality — Selectivity and B-tree column ordering
What are the disadvantages of indexes — Write amplification trade-offs