Composite Index

An index on more than one column

A composite index (also called a multi-column or compound index) indexes multiple columns together as a single structure, rather than indexing each column separately. For example:

sql
CREATE INDEX idx_dept_gpa ON students (department, gpa);

This builds a single B+ Tree where entries are sorted first by `department`, then by `gpa` within each department. Conceptually, it's like a phone book sorted by last name, then first name within each last name — not two separate indexes, but one combined ordering.

Column order is everything: the leftmost-prefix rule

This is the single most important fact about composite indexes: the order the columns are declared in matters critically. An index on (department, gpa) is sorted by department first. That means:

• WHERE department = 'CS' — can use this index efficiently (it's a prefix of the indexed columns).
• WHERE department = 'CS' AND gpa > 3.5 — can use this index efficiently (both columns, in order).
• WHERE gpa > 3.5 (alone, no department filter) — generally cannot efficiently use this index, because the index is sorted by department first; without knowing the department, GPA values for different departments are scattered throughout the structure, not grouped together.

This is known as the leftmost-prefix rule: a composite index on (A, B, C) can serve queries filtering on A, or (A, B), or (A, B, C), but generally cannot efficiently serve a query filtering on B alone, or C alone, or (B, C) without A.

Why order matters conceptually

Think of the phone-book analogy again: sorted by (last name, first name), you can easily find "everyone with last name Smith," or "Smith, John" specifically. But finding "everyone whose first name is John," regardless of last name, requires scanning the entire book, because first names are not grouped together independently of last name.

Edge cases

• If your application always filters by department alone, or by department AND gpa together, but never by gpa alone, then (department, gpa) is the right column order. If you sometimes need gpa alone, you may need a separate index on gpa, or reconsider the order.
• A composite index can also satisfy ORDER BY department, gpa for free (no extra sort step), because the leaf entries are already in that exact order.
• Composite indexes are a common way to build a covering index (20.8) — by adding extra "included" columns beyond the filter columns.

Interview-style Q&A

Q: What is the leftmost-prefix rule? A: A composite index on columns (A, B, C) can efficiently serve queries filtering on A, or A+B, or A+B+C, but generally not B alone, C alone, or B+C without A — because the index is physically sorted starting with A.

Q: Why can't `(department, gpa)` efficiently serve `WHERE gpa > 3.5` alone? A: Because the index is sorted by department first — gpa values are only sorted within each department group, so gpa values across different departments are scattered, not contiguous.

Key takeaway: composite index column order should match how your queries actually filter — put the most commonly filtered-alone (or leftmost-used) column first.