Composite & Covering Indexes

In simple words

Sometimes you search on two columns together — for example one user's orders that have a certain status. A composite index is one index built on several columns, sorted by the first column and then by the second within it, like a phone book sorted by last name and then first name. Because of that order, it only helps when your search starts from the first column. A covering index goes one step further: it holds every column the query needs, so the database can answer from the index alone without opening the table at all.

Composite Index — What and Why

A composite index (also called a multi-column index) is an index built on two or more columns together.

-- Single column index on user_id only
CREATE INDEX idx_user_id ON orders(user_id);

-- Single column index on status only
CREATE INDEX idx_status ON orders(status);

-- Composite index on (user_id, status) together
CREATE INDEX idx_user_status ON orders(user_id, status);

Why composite indexes exist:

-- This query needs BOTH user_id AND status filtered
SELECT * FROM orders
WHERE user_id = 123
  AND status = 'DELIVERED';

-- With two separate indexes:
  Option A: use idx_user_id → find all orders for user 123 (maybe 200 orders) →
            then filter status in memory
  Option B: use idx_status  → find all DELIVERED orders (maybe 5M rows) →
            then filter user_id in memory
  Both are suboptimal.

-- With composite index on (user_id, status):
  → directly find rows where user_id=123 AND status='DELIVERED'
  → maybe 5 rows → fetch exactly those
  → far more efficient

How Composite Index is Stored Internally

A composite index sorts data by the first column, then by the second column within each group of the first, and so on.

Composite index on orders(user_id, status):

Sorted first by user_id, then by status within each user_id group:

user_id | status      | row_pointer
────────┼─────────────┼────────────
1       | CANCELLED   | → row A
1       | CONFIRMED   | → row B
1       | DELIVERED   | → row C
1       | DELIVERED   | → row D
1       | SHIPPED     | → row E
2       | CONFIRMED   | → row F
2       | DELIVERED   | → row G
3       | PENDING     | → row H
...

This physical ordering determines exactly which queries can use the index.

The Left-Prefix Rule — The Most Important Rule

A composite index on (A, B, C) can be used for queries that filter on:

• A alone
• A + B
• A + B + C

It CANNOT be used efficiently for:

• B alone
• C alone
• B + C (without A)

Index: (user_id, status, created_at)

Queries that USE the index:
  WHERE user_id = 123                           ✅ prefix: (user_id)
  WHERE user_id = 123 AND status = 'DELIVERED'  ✅ prefix: (user_id, status)
  WHERE user_id = 123 AND status = 'DELIVERED'
    AND created_at > '2024-01-01'               ✅ prefix: (user_id, status, created_at)

Queries that DO NOT use the index:
  WHERE status = 'DELIVERED'                    ❌ no left prefix
  WHERE created_at > '2024-01-01'               ❌ no left prefix
  WHERE status = 'DELIVERED'
    AND created_at > '2024-01-01'               ❌ skips user_id (left prefix)

Why This Rule Exists

The index is physically sorted by (user_id, then status, then created_at).

To find status='DELIVERED' without knowing user_id:
  → The index isn't sorted by status globally
  → Every user_id group has its own status ordering
  → DB cannot use the index — must scan everything
  → Same as no index at all

It's like looking for a word in a phone book sorted by LastName, FirstName:
  → Finding by LastName: easy (left prefix)
  → Finding by FirstName only: impossible without scanning everything

Column Order in Composite Indexes — Matters Enormously

The order of columns in a composite index is a critical design decision.

Rule: Most Selective + Most Frequently Filtered Column First

-- Scenario: query on orders table
SELECT * FROM orders
WHERE user_id = 123
  AND status = 'DELIVERED'
ORDER BY created_at DESC;

-- Option 1: Index on (status, user_id, created_at)
CREATE INDEX idx_a ON orders(status, user_id, created_at);

-- Option 2: Index on (user_id, status, created_at)
CREATE INDEX idx_b ON orders(user_id, status, created_at);

Analysis:
  status has ~5 distinct values (PENDING, CONFIRMED, SHIPPED, DELIVERED, CANCELLED)
  → Low selectivity: 'DELIVERED' matches ~20% of all orders (2M of 10M rows)

  user_id has 10M distinct values
  → High selectivity: user_id=123 matches ~50 rows

Option 1 (status first):
  Step 1: find all DELIVERED orders → 2M rows
  Step 2: filter user_id=123 from 2M → 50 rows
  Still processing 2M entries in the index

Option 2 (user_id first): ✅ BETTER
  Step 1: find user_id=123 → 50 rows
  Step 2: filter status=DELIVERED from 50 → maybe 20 rows
  Only processed 50 entries in the index

→ user_id first is dramatically more efficient
→ High selectivity column goes first

Rule: Equality Columns Before Range Columns

-- Query:
SELECT * FROM orders
WHERE user_id = 123           -- equality
  AND created_at > '2024-01-01'  -- range
ORDER BY created_at DESC;

-- ❌ Wrong order: (created_at, user_id)
CREATE INDEX idx_bad ON orders(created_at, user_id);
-- After range on created_at, the index cannot filter user_id efficiently
-- The sorted order within the range is by created_at, not user_id

-- ✅ Correct order: (user_id, created_at)
CREATE INDEX idx_good ON orders(user_id, created_at);
-- Equality on user_id → narrows to user's orders
-- Then range on created_at → sorted within that user's rows → efficient

Rule: Equality (=) columns BEFORE range (<, >, BETWEEN, LIKE) columns

Reason: Once a range condition is applied, the index cannot continue
        efficiently filtering subsequent columns because the ordering
        of those columns is interleaved within the range.

Covering Index — The Performance Superpower

A covering index is an index that contains all the columns a query needs, so the database can answer the query entirely from the index without ever touching the actual table rows.

Normal index lookup (Secondary Index):
  Query → Index B-Tree → (value, PK) → Table B-Tree → actual row data
  Two lookups: index + table

Covering index lookup (Index-Only Scan):
  Query → Index B-Tree → all needed column values are RIGHT HERE
  One lookup: index only → done
  Never touches the actual table

Example

-- Table: orders (user_id, status, amount, created_at, shipping_address, notes, ...)
-- Query:
SELECT user_id, status, amount
FROM orders
WHERE user_id = 123;

Without covering index:
  Index on (user_id) → find row pointers for user_id=123
  → Follow EACH pointer back to the table to get status and amount
  → 50 random I/O operations to fetch 50 rows from the table

With covering index on (user_id, status, amount):
  → Index leaf nodes CONTAIN user_id, status, amount
  → All data needed is in the index itself
  → Zero table lookups → index-only scan → much faster

-- Create the covering index
CREATE INDEX idx_covering ON orders(user_id, status, amount);

-- EXPLAIN will show: "Using index" in Extra column
-- This means it's an index-only scan (covering index used)
EXPLAIN SELECT user_id, status, amount FROM orders WHERE user_id = 123;
-- Extra: Using index   ← covering index hit

How to Identify if You Need a Covering Index

Ask: "Does my query SELECT only a few columns from a large table
      where the rest of the columns are never needed?"

Signs you need a covering index:
  - EXPLAIN shows "Using index condition" or many random I/O
  - Query fetches only 3-4 columns but table has 30+ columns
  - Same query runs millions of times per day
  - The query is on the hot read path (product page, feed, dashboard)

Composite Index vs Multiple Single Indexes

-- Option A: Two separate indexes
CREATE INDEX idx_user_id ON orders(user_id);
CREATE INDEX idx_status   ON orders(status);

-- Option B: One composite index
CREATE INDEX idx_user_status ON orders(user_id, status);

When both columns are filtered together (WHERE user_id=? AND status=?):
  Option A: DB picks ONE index (usually more selective one)
            → filter second condition in memory → less efficient
            MySQL can do "index merge" but it's expensive
  Option B: Single composite index handles both together → efficient

When only one column is filtered:
  WHERE user_id = 123       → idx_user_status works (left prefix) ✅
  WHERE status = 'DELIVERED' → idx_user_status does NOT work ❌
                               separate idx_status would be needed

Decision:
  If queries mostly use both columns together → composite
  If queries frequently use each column alone → separate indexes (or both)
  For user_id + status pattern: composite is almost always better

Index Design Walkthrough — Real Scenario

System: E-commerce order service

-- Frequent queries on the orders table:

-- Q1: Get all orders for a user (order history page) — millions of calls/day
SELECT order_id, status, amount, created_at
FROM orders
WHERE user_id = ?
ORDER BY created_at DESC
LIMIT 20;

-- Q2: Get all pending orders for ops dashboard — runs every minute
SELECT order_id, user_id, amount
FROM orders
WHERE status = 'PENDING'
  AND created_at < NOW() - INTERVAL 2 HOUR;

-- Q3: Get delivered orders for a user in last 30 days (returns page)
SELECT order_id, amount, created_at
FROM orders
WHERE user_id = ?
  AND status = 'DELIVERED'
  AND created_at >= NOW() - INTERVAL 30 DAY;

Index design:

For Q1:
  Needs: user_id (equality), created_at (range + sort)
  Index: (user_id, created_at)
  SELECT columns: order_id, status, amount, created_at
  → Add to index for covering: (user_id, created_at, status, amount, order_id)
  → Now it's an index-only scan for Q1

For Q2:
  Needs: status (equality), created_at (range)
  Selectivity: status is low, but filtering only 'PENDING' + time range is selective
  Index: (status, created_at)
  → Equality on status, then range on created_at — correct order

For Q3:
  Needs: user_id (equality), status (equality), created_at (range)
  Index: (user_id, status, created_at)
  → Two equalities first, then range — correct order
  → Also covers Q1 partially (user_id is left prefix) but Q1 needs sort
     → keep both indexes or choose based on query frequency

Final index set:
  CREATE INDEX idx_user_date ON orders(user_id, created_at, status, amount);
  CREATE INDEX idx_status_date ON orders(status, created_at, user_id, amount);
  CREATE INDEX idx_user_status_date ON orders(user_id, status, created_at);

Common Mistakes to Avoid

❌ Wrong column order — range column before equality column
   (created_at, user_id) for WHERE user_id=? AND created_at>?
   → Fix: (user_id, created_at) — equality first

❌ Over-indexing — creating 10+ indexes on a write-heavy table
   → Every insert/update pays the cost of updating all 10 indexes
   → Audit and drop unused indexes regularly

❌ Indexing low-cardinality columns first
   (is_active, user_id) → is_active has 2 values, useless as prefix
   → Fix: (user_id, is_active)

❌ Not including SELECT columns in covering index
   Index on (user_id) but query selects amount, status too
   → Results in double lookup
   → Fix: Include frequently selected columns in the index

❌ Using functions on indexed columns
   WHERE LOWER(email) = 'alice@email.com' → breaks index
   → Fix: Store email lowercased, or create functional index:
   CREATE INDEX ON users (LOWER(email));   -- PostgreSQL

❌ Too many included columns in covering index
   Adding 15 columns "just in case" → index becomes huge
   → defeats the purpose (large index = more I/O)
   → Only include columns actually needed by the hot query

EXPLAIN Output — Reading Index Usage

EXPLAIN SELECT user_id, status, amount
FROM orders
WHERE user_id = 123 AND status = 'DELIVERED';

-- With composite covering index on (user_id, status, amount):
┌──────┬──────────────────────┬──────────┬──────────────┬──────┬─────────────────────┐
│ type │ possible_keys        │ key      │ key_len      │ rows │ Extra               │
├──────┼──────────────────────┼──────────┼──────────────┼──────┼─────────────────────┤
│ ref  │ idx_user_status_amt  │ idx_u_s_a│ 8            │ 5    │ Using index         │
└──────┴──────────────────────┴──────────┴──────────────┴──────┴─────────────────────┘

type = 'ref'         → B-Tree index used for equality lookup ✅
key  = idx_u_s_a     → this specific index was chosen ✅
rows = 5             → estimated 5 rows scanned ✅ (vs millions without)
Extra = 'Using index' → COVERING INDEX! No table lookup needed ✅

-- Red flags in EXPLAIN:
type = 'ALL'                     → full table scan, no index used ❌
Extra = 'Using filesort'         → sort not served by index ❌
Extra = 'Using temporary'        → temp table created (expensive) ❌
Extra = 'Using index condition'  → index used but not covering (table lookup needed)

System Design Context

High-Frequency Read Paths Need Covering Indexes

Twitter-like feed service:
  Query: "Get 20 most recent tweets by users I follow"
  This runs for every feed refresh, billions of times/day

  tweets table: tweet_id, user_id, content, created_at, likes, retweets, ...

  Without covering index:
    → Index lookup finds tweet IDs → fetch each row from table
    → 20 random I/O operations × billions of requests = massive I/O load

  With covering index on (user_id, created_at, tweet_id, content, likes):
    → Everything needed is in the index
    → Index-only scan → 10x less I/O

Lesson: Every millisecond on a query that runs billions of times/day
        translates to real infrastructure cost.
        Covering indexes are the first optimization to reach for.

Composite Index Strategy in Microservices

OrderService: most queries filter by user_id first → user_id as first column
InventoryService: most queries filter by product_id first → product_id first
NotificationService: most queries filter by user_id + status → (user_id, status)
AnalyticsService: mostly range queries on created_at → (created_at, event_type)

Each service has different query patterns → different index strategies.
Design indexes per service's specific hot queries, not generically.

How This Connects

• Indexing - B-Tree & Hash Indexes — the prerequisite: how a single-column B-Tree works, clustered vs secondary, the bookmark lookup this note eliminates.
• Query Optimization & EXPLAIN Plans — Using index (covering / index-only scan) vs Using index condition vs Using filesort in EXPLAIN tell you whether your column order and covering columns landed.
• SQL - Joins, Aggregations, Subqueries — a GROUP BY a ORDER BY a or a join can be served straight from a composite index in sorted order, skipping the sort step entirely.
• Module 4 — Data Architecture / Sharding — the shard key is effectively the mandatory left-most prefix of every query; picking it is the same reasoning at cluster scale.
• Time Series Data — modeling & storage — (entity_id, timestamp) is the canonical composite: equality on the series, range on time.

In the Interview

When to say it. Any "will this index be used?" question, any "the query filters on A and B but the index isn't helping" debugging prompt, and any hot-read-path design where you want an index-only scan.

The ~20-second version:

"A composite index on (A, B, C) is a single B-Tree sorted by A, then B, then C. The left-prefix rule says it only helps queries that filter from the left — A, or A+B, or A+B+C — never B or C alone, because within the index B is only sorted inside each A group. Column order follows two rules: equality predicates before the range predicate, and put the range/sort column last so the index can return rows already ordered. A covering index goes further — if the index also contains every column the query SELECTs, the database never touches the table; EXPLAIN shows 'Using index'. On a path that runs billions of times a day, turning a double lookup into an index-only scan is a real infrastructure saving."

Follow-ups to expect:

1. "Index (user_id, status, created_at). Query: WHERE status = 'X' AND created_at > ?. Used?" — No: user_id is the missing left prefix. You'd need (status, created_at) or a query that also constrains user_id.
2. "Index (user_id, created_at). Query: WHERE user_id = ? AND created_at > ? ORDER BY created_at. Used, and is the sort free?" — Yes and yes: equality seeks the user's slice, the range walks created_at in order, so ORDER BY created_at needs no filesort.
3. "Why does the range column have to be last?" — After a range condition, the next column's values are interleaved across the range, so the index can't keep filtering/ordering on it.
4. "Composite vs two single-column indexes?" — Composite wins when the columns are queried together. Two singles let each be used alone (index merge is possible but costlier). Sometimes you keep both.
5. "Downside of a wide covering index?" — It's a bigger structure: more disk, slower writes, more of the buffer pool consumed. Only cover the genuinely hot query, and don't add "just in case" columns.

Mistake to avoid: putting a low-cardinality column first "because it's filtered a lot" — e.g. (is_active, user_id). is_active has two values, so it barely narrows anything as a prefix. Lead with the selective equality column: (user_id, is_active).

Quick Revision — 7 Lines

1. Composite index = index on multiple columns, sorted by first column then second etc.
2. Left-prefix rule: index (A, B, C) can only be used if query filters start from A
3. Column order: equality columns first, then range columns; high-selectivity columns first
4. Covering index = all SELECT columns are in the index → index-only scan, no table lookup
5. EXPLAIN shows 'Using index' for covering index, 'ALL' for full scan
6. Composite beats multiple single-column indexes when both columns are always filtered together
7. Over-indexing slows writes — audit and drop unused indexes regularly