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):** 1. Equality columns first (WHERE col = ?), then 2. Range columns (WHERE col > ? / BETWEEN), then 3. ORDER BY columns (only useful as the last segment if the prior segments are equalities). 4. 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

Loading editor...