Choosing the Best Composite Index for A = ?, B IN (...), ORDER BY C

What the Question Asks

The interview question provides a table with three columns A, B, C that have equal selectivity. The typical query is WHERE A = ? AND B IN (...) ORDER BY C. The challenge is to design the most efficient composite index.

What Filesort Is

When MySQL executes ORDER BY, it can read rows in the required order directly from an index. If the index cannot provide that order, MySQL must retrieve the rows and sort them itself – an operation called filesort . Filesort may happen in memory, but if the data exceeds sort_buffer_size it spills to disk, incurring extra cost.

Composite Index Ordering Rules

In a composite index (A, B, C), the B‑tree is ordered first by A, then by B, then by C. Column C is globally ordered only when the values of A and B are fixed. MySQL’s rule for using an index to satisfy ORDER BY is that every column preceding the ordered column must appear as an equality condition in the WHERE clause.

Analyzing Index (A, B, C)

Using the sample data where A=10, the index entries are ordered as (A, B, C, PK). After locating the six rows with A=10, the engine skips the B=100 segment and keeps rows with B=200 and B=300. Their C values appear as 1, 4, 2, 6, which is not globally sorted, so MySQL triggers a filesort. The more values appear in the B IN list, the more segments are concatenated and the larger the filesort workload.

Analyzing Index (A, C, B)

With the same data, the index is ordered as (A, C, B, PK). After fixing A=10, the C column is already sorted (1 → 6). The engine scans the index, discarding rows whose B value is not in the IN list, but the remaining rows keep the original C order (1, 2, 4, 6). No filesort is needed, and B filtering happens at the index level, avoiding extra row lookups.

Other Index Options

(A, B) : C is not in the index, so ORDER BY C always requires a filesort and a table lookup for C.

(A, C) : C is ordered after A, so filesort is avoided, but B is not in the index; rows must be fetched from the table to evaluate the B IN condition, increasing the number of lookups.

Summary of Schemes

(A, B, C) : Filesort occurs; low index‑only filtering; performance degrades as the size of the B IN list grows.

(A, C, B) : No filesort; B filtered in the index; stable cost regardless of B IN size.

(A, C) : No filesort; high table‑lookup cost because B must be evaluated after the index scan.

(A, B) : Filesort required and additional lookup for C; overall worst performance.

Special Scenario

If the B IN clause ever contains only a single value, it becomes an equality condition. In that case, the index (A, B, C) can be superior because C follows a fully fixed prefix (A, B) and can use the index for ordering while B’s filter is highly selective.

Key Takeaway

The decisive rule is that the ordering column must immediately follow the equality columns in the index; any range column placed between them breaks the global order required for an index‑only sort. Therefore, for the given query pattern, the optimal composite index is (A, C, B), which guarantees zero filesort and stable performance even when the B IN list is large.