How do you approach SQL Optimization: Pick the Right Index from EXPLAIN?

Equality first, range second, ORDER BY last - and ORDER BY only helps if prior columns are equalities (otherwise the index can't both range-scan AND sort).

What are common mistakes on SQL Optimization: Pick the Right Index from EXPLAIN?

Filtering on an aggregate in WHERE rather than HAVING. An inner join where a left join is meant, which silently drops the rows the question was about - the customers with zero orders. COUNT(*) versus COUNT(column). The second skips nulls, and that difference is often the entire question.

gitGood.dev

← Back to problems

SQL Optimization: Pick the Right Index from EXPLAIN

HardDatabases

Description

This problem is paper-only - see explanation for the canonical SQL solution. The auto-grader checks your reasoning by asking you to return the recommended index column order for a given query.

You are given a query workload (a query string) and a set of available index hints. Return the best single composite index column order for the query as an array of column names.

Rule of thumb (Postgres / MySQL B-tree):

Equality columns first (WHERE col = ?), then
Range columns (WHERE col > ? / BETWEEN), then
ORDER BY columns (only useful as the last segment if the prior segments are equalities).
Selectivity matters: among equalities, put high-cardinality columns first.

For the auto-grader: parse the query into the structured { filters, ranges, orderBy } object passed in (already pre-parsed) and return an index column array.

Input shape: { equalities: string[], ranges: string[], orderBy: string[] }. Output: the column order.

Example 1

Input: parsed = { equalities:["tenant_id"], ranges:["created_at"], orderBy:["created_at"] }

Output: ["tenant_id","created_at"]

Explanation: Equality first, then range. The range column doubles as the ORDER BY column - a single composite index covers both filter and sort.

Example 2

Input: parsed = { equalities:["status","tenant_id"], ranges:[], orderBy:["created_at"] }

Output: ["status","tenant_id","created_at"]

Explanation: Both equalities first (order between them is fine - cardinality would tiebreak in real life). ORDER BY column last.

Constraints

- equalities, ranges, orderBy each have <= 5 columns - column names are lowercase strings

SQL Optimization: Pick the Right Index from EXPLAIN: approach, complexity and pitfalls

A hard sql problem, graded against 5 test cases (3 of them hidden).

The pattern: SQL

Query-writing problems - joins, aggregation, window functions, and query tuning.

Reach for it when you see: A schema and a question about the data rather than a function signature.

If you are stuck

Show the 3-step hint ladder

Equality first, range second, ORDER BY last - and ORDER BY only helps if prior columns are equalities (otherwise the index can't both range-scan AND sort).
If the range column equals the ORDER BY column, putting it once after the equalities serves both - don't append a duplicate.
If there's a range AND a separate ORDER BY column, the ORDER BY is unsorted by the index - drop it.

The optimal approach

Show the approach: The composite-index column-order rule:

A B-tree composite index `(a, b, c)` can serve a query if and only if:

- The leftmost columns are matched as equalities, and

- At most one trailing column is used as a range, and

- ORDER BY can ride along only if it's a continuation of the leading equality / range portion.

Algorithm:

1. Place all equality columns first (in any order; in practice, highest cardinality first for selectivity).

2. Append at most one range column.

3. If the range column is the same as the ORDER BY column, the index already supports the sort - done.

4. If there is no range column and the ORDER BY column is distinct, append the ORDER BY column.

5. If there is a range AND a distinct ORDER BY column, the ORDER BY can't be index-served - drop it from the index recommendation.

Why this matters in interviews: the difference between an indexed seek (O(log n + k)) and a full table scan + sort (O(n log n)) is many orders of magnitude. EXPLAIN ANALYZE reveals which one happened: look for "Index Scan using ..." vs "Seq Scan" + "Sort".

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common SQL mistakes

These apply to the pattern as a whole, not just this problem.

Filtering on an aggregate in `WHERE` rather than `HAVING`.
An inner join where a left join is meant, which silently drops the rows the question was about - the customers with zero orders.
`COUNT(*)` versus `COUNT(column)`. The second skips nulls, and that difference is often the entire question.