Skip to content

Composite Index

1. What is it? (2-3 lines)

A Composite Index (also called a Multi-Column Index) is an index built on two or more columns of a database table ((colA, colB, colC)). Data inside the index leaf pages is sorted lexicographically according to the specified left-to-right column order.

2. Why does it exist?

Queries frequently filter or sort by multiple conditions (WHERE tenant_id = 5 AND status = 'ACTIVE' ORDER BY created_at DESC). Creating single-column indexes on tenant_id, status, and created_at forces the query optimizer to pick one index or attempt expensive Index Intersections. A Composite Index evaluates all conditions in a single \(O(\log N)\) B+ Tree seek.

3. Where is it used?

  • Multi-tenant enterprise SaaS applications (tenant_id, user_id).
  • E-commerce order lookups (user_id, status, created_at).
  • Time-series cursor pagination (created_at, id).

4. How does it work? (simple flow)

  1. Lexicographical B+ Tree Sorting: Index keys are stored as composite tuples (colA, colB, colC). Rows are sorted by colA first; if colA values are identical, sorted by colB; if colB identical, sorted by colC.
  2. Leftmost Prefix Rule: The B+ Tree can ONLY be searched if the query filters include the leftmost column (colA).
  3. Valid: WHERE colA = 1, WHERE colA = 1 AND colB = 2, WHERE colA = 1 AND colB = 2 AND colC = 3.
  4. Invalid (Skipped Index): WHERE colB = 2, WHERE colC = 3 (Bypass index, triggers Full Table Scan).
  5. Range Truncation: A range filter (<, >, LIKE 'abc%') on an earlier column (colB) stops index usage for subsequent columns (colC).

5. Advantages

  • Combines multiple column predicates into a single B+ Tree traversal.
  • Eliminates secondary sorting operations (ORDER BY filesort) if index column order matches ORDER BY.
  • Acts as a Covering Index if query selects only a subset of composite index columns.

6. Limitations

  • Leftmost Prefix Constraint: Queries that omit the leading column cannot utilize the index.
  • Range Truncation Boundary: Once a range condition (>) is applied to colB, colC cannot be filtered via index seek.
  • Larger index size on disk and RAM compared to single-column indexes.

7. Common interview questions (10)

  1. What is the Leftmost Prefix Rule in Composite Indexes?
  2. Given index (A, B, C), will query WHERE B = 2 AND C = 3 use the index? Why or why not?
  3. How does column order in (A, B) affect index efficiency based on column selectivity/cardinality?
  4. What happens to composite index usage in query WHERE A = 1 AND B > 10 AND C = 5?
  5. How does Index Skip Scan (MySQL 8.0+) bypass the Leftmost Prefix Rule under low cardinality?
  6. How should you order columns in a Composite Index to satisfy both WHERE and ORDER BY clauses?
  7. Why is (tenant_id, created_at) better than (created_at, tenant_id) for multi-tenant range queries?
  8. What is the maximum number of columns allowed in a MySQL or PostgreSQL composite index?
  9. How does Index Condition Pushdown (ICP) optimize composite index range queries?
  10. How do composite indexes support Cursor-Based Pagination on non-unique columns?

8. Common misconceptions

  • Misconception: Order of columns in WHERE clause must match index column order. Fact: Query optimizer automatically reorders equality predicates in WHERE clauses to match index column order!
  • Misconception: Creating separate indexes on A and B is identical to composite index (A, B). Fact: Two single-column indexes require index intersection/merge, which is far slower than a single composite index seek.

10. 30-second cheat sheet

  • Rule 1: Leftmost Prefix Rule — Query MUST filter by leading column A to use index (A, B, C).
  • Rule 2: Column Ordering — Put high-cardinality equality columns first (tenant_id), then range columns (created_at).
  • Rule 3: Range Truncation — WHERE A = 1 AND B > 5 AND C = 10 \(\implies\) Index filters A & B, but scans C.
  • Benefit: Replaces filesort and index merges with a single \(O(\log N)\) B+ Tree seek.