Knowing that an index exists is the easy half; designing the right one is what interviewers actually test. Which columns, in what order, whether the index alone can answer the query, and why the optimizer sometimes ignores the index you just built. For a Backend or AI engineer this is the daily work behind "this endpoint got slow at 5 million rows": one well-shaped composite or covering index usually beats three separate single-column ones, and a badly shaped one costs write throughput for nothing.
CREATE INDEX idx_city_age ON users(city, age);
The B+Tree is sorted by city FIRST, then by age within each city:
(city1, 18) (city1, 19) ... (city1, 77)
(city2, 18) (city2, 19) ... (city2, 77)
(city3, 18) ...
Usable:
WHERE city = 'city7' -- prefix (city)
WHERE city = 'city7' AND age > 30 -- prefix, then a range on the next column
WHERE city = 'city7' ORDER BY age -- already sorted, no sort step needed
Generally NOT usable as a seek:
WHERE age = 30 -- the matching entries are scattered
-- across every city's blockA composite index is one B+Tree whose key is the tuple of columns, sorted lexicographically like a phone book sorted by last name then first name. You can find "Smith" quickly, or "Smith, John" quickly, but you cannot find every "John" without reading the whole book, because the Johns are spread under every last name. That is the leftmost-prefix rule: the index can be used for a seek when the query constrains the leading column(s) with equality, plus optionally one more column. Some engines can work around a low-cardinality leading column with a "skip scan" (SQLite after ANALYZE, as shown below; recent MySQL 8.0 and PostgreSQL 18 versions have variants), but treat that as a bonus rather than a design assumption.
Query: WHERE city = 'city7' AND age > 30
Index (city, age): Index (age, city):
seek to (city7, 31), read forward seek to age > 30, read ALL ages 31..77
until city changes across every city, filter city = 'city7'
-> reads only matching entries -> reads ~ (fraction of table with age > 30)
and discards most of it
Rule of thumb for the column order:
1. equality-filtered columns first (city =)
2. then the range / sort column (age >, ORDER BY age)
3. columns after a range column cannot narrow the seek any furtherWithin one contiguous run of the tree, entries are sorted only by the columns before the first range condition. Once the index reaches a range predicate on age, everything after it in the key is no longer in a single sorted run, so it can be used to filter entries but not to skip pages. That is why equality columns go first, then the range column. Selectivity is a secondary consideration: putting the "most selective column first" is folklore that breaks as soon as a query does not filter on it. Design the order from the queries you run: which columns are always equality-filtered, which is ranged or sorted.
SELECT city, age FROM users WHERE city = 'city7' AND age > 30;
Index (city, age) contains every column the query needs:
descend index -> read matching leaf entries -> return them.
No row lookup: no heap fetch (PostgreSQL) / no PK-tree descent (InnoDB secondary).
SELECT * FROM users WHERE city = 'city7' AND age > 30;
index gives the row pointers, then EACH matching row needs an extra fetch
(random I/O per row) to get the remaining columns.
PostgreSQL 11+ lets you carry extra payload columns that are not part of the key:
CREATE INDEX idx_orders_cust ON orders (customer_id, created_at) INCLUDE (total);A covering index is not a special kind of index. It is any index that contains all the columns a particular query reads, so the table is never touched. This removes the per-row random lookup, which is usually the dominant cost of a non-covering index scan. In PostgreSQL an "index-only scan" additionally depends on the visibility map (pages recently modified may still require a heap check), so vacuuming affects it. INCLUDE columns are stored in the leaf entries but not in the search key, so they add width without affecting ordering or uniqueness; in MySQL/InnoDB you get the same effect by appending the columns to the key (secondary indexes already carry the primary key). The price is a wider index: more pages, more memory, more write work.
cardinality = number of DISTINCT values in the column
selectivity = distinct values / total rows (closer to 1 = more selective)
20,000-row test table (from the run below):
user_id / id : 20,000 distinct -> selectivity 1.0 (WHERE id = 5 matches 1 row)
city : 50 distinct -> ~400 rows per value
gender : 2 distinct -> 10,000 rows per value (50% of the table)
Partial index: index only the rows you query
CREATE INDEX idx_pending ON users(status) WHERE status = 'pending';
200 of 20,000 rows are 'pending': tiny index, cheap to maintain, and only
queries whose WHERE implies status = 'pending' can use it.
Expression index: index the computed value
CREATE INDEX idx_email_lower ON users(lower(email));
WHERE lower(email) = '[email protected]' -> can use it
WHERE email = '[email protected]' -> cannot (different expression)Selectivity is about how much a predicate narrows the table, and it is what decides whether an index pays for itself. An index on gender splits the table in half, so either value matches 10,000 rows; following 10,000 pointers into the table is random I/O that a sequential scan may beat, so in PostgreSQL and similar engines the optimizer often prefers the scan (SQLite, as the run below shows, still picks the index; behaviour is engine specific). A partial index attacks the problem from the other side: index only the small, interesting slice (pending jobs, soft-deleted flags, unprocessed messages) and the index stays small and cheap. An expression index lets a function-wrapped predicate be indexed, because the stored key is the computed value.
Index on email exists, yet these scan (sqlite, real output):
WHERE lower(email) = 'x' -- function on the column: stored keys are raw emails
WHERE id + 0 = 5 -- arithmetic on the column
WHERE email LIKE '%[email protected]' -- leading wildcard: no known starting key
(PostgreSQL adds: WHERE varchar_col = 123 -- implicit cast can defeat the index)
Fixes:
WHERE email = 'x' (compare the raw column, move the function to the constant)
CREATE INDEX ... (lower(email)) -- expression index
prefix search: LIKE 'abc%' or a range email >= 'abc' AND email < 'abd'
suffix / infix search: a different structure (trigram index, full-text)
Other reasons the optimizer skips an index:
- predicate matches a large fraction of rows (seq scan cheaper than many random fetches)
- the table is tiny (one page: scanning is cheaper than a descent)
- stale or missing statistics -> wrong row estimates
- leading column of the composite index is not constrained
- OR conditions or a mismatched collation / data typeAn index is keyed on the stored value. If the query applies a function or cast to the column, the database cannot know where in the sorted order the transformed values land, so it must compute the expression for every row: that is a scan. "Sargable" predicates (Search ARGument ABLE) keep the bare column on one side of the comparison. Beyond correctness, indexes hurt by adding write amplification (each insert, update or delete touches every index), by consuming memory that could cache table data, and by cluttering the optimizer's choices. The optimizer ignoring an index is not a bug: it is cost-based and, when it estimates that using the index would touch more pages than a scan, or its statistics say so, it will scan.
INCLUDE, or extra key columns in MySQL).lower(email)) keep indexes small or make function-based predicates indexable.INCLUDE in PostgreSQL), weighing the extra width and write cost.(city) is redundant if (city, age) exists) and indexes that the workload no longer uses.-- Runs in sqlite3. Plans below are real output from SQLite 3.51.
CREATE TABLE users (id INTEGER PRIMARY KEY, email TEXT, city TEXT, age INTEGER,
gender TEXT, status TEXT, name TEXT);
WITH RECURSIVE n(i) AS (SELECT 1 UNION ALL SELECT i+1 FROM n WHERE i<20000)
INSERT INTO users SELECT i, 'User'||i||'@Example.com', 'city'||(i%50), 18+(i%60),
CASE WHEN i%2=0 THEN 'M' ELSE 'F' END,
CASE WHEN i%100=0 THEN 'pending' ELSE 'done' END, 'name'||i FROM n;
SELECT count(DISTINCT city), count(DISTINCT gender), count(DISTINCT id) FROM users;
-- 50 | 2 | 20000
CREATE INDEX idx_city_age ON users(city, age);
EXPLAIN QUERY PLAN SELECT * FROM users WHERE city='city7' AND age>30;
-- SEARCH users USING INDEX idx_city_age (city=? AND age>?)
EXPLAIN QUERY PLAN SELECT * FROM users WHERE city='city7';
-- SEARCH users USING INDEX idx_city_age (city=?)
EXPLAIN QUERY PLAN SELECT * FROM users WHERE age=30; -- skips the leading column
-- SCAN users
EXPLAIN QUERY PLAN SELECT * FROM users WHERE city='city7' ORDER BY age;
-- SEARCH users USING INDEX idx_city_age (city=?) (no sort step: index order reused)
EXPLAIN QUERY PLAN SELECT city, age FROM users WHERE city='city7' AND age>30;
-- SEARCH users USING COVERING INDEX idx_city_age (city=? AND age>?)
-- Reverse the column order: the range column now leads
DROP INDEX idx_city_age;
CREATE INDEX idx_age_city ON users(age, city);
EXPLAIN QUERY PLAN SELECT * FROM users WHERE city='city7' AND age>30;
-- SEARCH users USING INDEX idx_age_city (age>?) (city is only a filter, not a seek)
EXPLAIN QUERY PLAN SELECT * FROM users WHERE city='city7' AND age=30;
-- SEARCH users USING INDEX idx_age_city (age=? AND city=?) (both equality: either order works)
DROP INDEX idx_age_city;
-- Functions on the column
CREATE INDEX idx_email ON users(email);
EXPLAIN QUERY PLAN SELECT * FROM users WHERE lower(email)='[email protected]';
-- SCAN users
CREATE INDEX idx_email_lower ON users(lower(email));
EXPLAIN QUERY PLAN SELECT * FROM users WHERE lower(email)='[email protected]';
-- SEARCH users USING INDEX idx_email_lower (<expr>=?)
EXPLAIN QUERY PLAN SELECT * FROM users WHERE email LIKE '%[email protected]';
-- SCAN users
EXPLAIN QUERY PLAN SELECT * FROM users WHERE id + 0 = 5;
-- SCAN users
-- Partial index
CREATE INDEX idx_pending ON users(status) WHERE status='pending';
EXPLAIN QUERY PLAN SELECT * FROM users WHERE status='pending';
-- SEARCH users USING INDEX idx_pending (status=?)
EXPLAIN QUERY PLAN SELECT * FROM users WHERE status='done';
-- SCAN users
-- Low selectivity: SQLite still uses the index on a 50/50 column
CREATE INDEX idx_gender ON users(gender);
EXPLAIN QUERY PLAN SELECT * FROM users WHERE gender='M';
-- SEARCH users USING INDEX idx_gender (gender=?)
-- Skip scan after statistics exist (SQLite-specific behaviour)
CREATE INDEX idx_city_age ON users(city, age);
ANALYZE;
EXPLAIN QUERY PLAN SELECT * FROM users WHERE age=30;
-- SEARCH users USING INDEX idx_city_age (ANY(city) AND age=?)
-- PostgreSQL (not run here; no output shown): covering + partial + expression
-- CREATE INDEX idx_orders_cust ON orders (customer_id, created_at) INCLUDE (total);
-- CREATE INDEX idx_pending ON users (id) WHERE status = 'pending';
-- CREATE INDEX idx_email_lower ON users (lower(email));
-- EXPLAIN SELECT total FROM orders WHERE customer_id = 42 AND created_at > now() - interval '7 days';
-- expect an "Index Only Scan", provided the visibility map is reasonably up to date.Q: What is a composite index?
A: A single index built over more than one column, stored as a B+Tree sorted by the first column, then the second within it, and so on. It serves queries that filter on a leftmost prefix of those columns and can also serve ORDER BY on the next column, replacing several single-column indexes with one that the optimizer can seek in one pass. The trade-off is that it is wider, costs more per write, and helps only queries that match its column order.
Q: Why does column order matter?
A: The index is sorted by the leading column first, so matching entries form one contiguous run only when the leading columns are constrained. (city, age) answers city = 'X' AND age > 30 by seeking to one spot and reading forward, while (age, city) must read every entry with age over 30 across all cities and filter afterwards. In general, equality columns go first, then the range or sort column; and queries that omit the leading column generally cannot use the index for a seek.
Q: What is a covering index?
A: An index that contains every column a query needs, so the engine answers from the index alone and skips the table lookup (an index-only scan in PostgreSQL, "Using index" in MySQL). That removes the random row fetch per match, which is often the real cost of a non-covering index scan. The cost is a bigger index with more write overhead, and in PostgreSQL index-only scans still depend on the visibility map being reasonably fresh.
Q: What is index selectivity?
A: Selectivity describes how much a predicate narrows the table, often expressed as distinct values divided by total rows (cardinality over row count). An index on user_id is highly selective: one value maps to one row. An index on gender is not: each value matches half the table, so the index barely reduces the work and still costs writes. Selectivity is judged per predicate and value, since a skewed column can be selective for a rare value and useless for a common one.
Q: When would the optimizer ignore an index?
A: When its cost estimate says the index path is more expensive or when the index cannot be used at all. The first case includes predicates that match a large fraction of rows (a sequential scan beats many random fetches), tiny tables, and stale statistics that misestimate row counts. The second includes functions or casts on the indexed column, leading-wildcard LIKE, and a query that skips the leading column of a composite index. Checking EXPLAIN tells you which case applies.
Follow-up: You have an index on (city) and another on (city, age). Do you need both?
A: Usually not: any query the single-column index serves can be served by the composite index through its leftmost prefix, so the smaller one is redundant and only adds write cost and storage. The exception is when the narrower index is measurably faster for a very hot query (smaller, better cached), or when the narrower one enforces different uniqueness. Confirm with EXPLAIN and index-usage statistics before dropping.
Follow-up: A query filters WHERE created_at > X ORDER BY id LIMIT 20 and is still slow with an index on created_at. Why?
A: The engine has two options: use the created_at index and then sort the matches by id, or walk the id index in order and filter until 20 rows pass. If many rows satisfy the range, the first option sorts a large set and the second may read far more entries than 20 when matches are rare. A composite index cannot serve both a range on one column and an ordering on a different column, so the fix depends on the data distribution; measure with EXPLAIN ANALYZE rather than guessing.
Follow-up: Does putting the most selective column first always give the best composite index?
A: No. That advice only helps when queries filter on the leading column by equality. If most queries filter on (status, created_at) but seldom on a high-cardinality user_id, leading with user_id makes the index unusable for them. Order by how queries constrain columns: equality first, then range or sort, and use selectivity mainly to break ties between equality columns and to decide whether the index is worth having at all.
Most read paths in a design can be traced to a composite index whose column order mirrors the API. "Orders for a customer in the last 7 days, newest first" is (customer_id, created_at); "inbox for a user sorted by time" is (user_id, received_at); a multi-tenant SaaS table almost always leads with tenant_id so every query is a prefix seek within one tenant. Partial indexes suit job queues and outbox tables, where a tiny "unprocessed" slice is polled constantly while millions of finished rows sit untouched. Covering indexes matter for hot list endpoints, since they avoid per-row lookups entirely. At scale every extra index is also a write-throughput and replication-lag cost, which is why an interview answer that names the exact index and admits what it costs on writes reads as senior. For AI retrieval pipelines the same reasoning applies to the metadata filters that surround a vector search: index tenant, document type and timestamps so that filters narrow the candidates before or alongside the vector step.
The decision is to shape one index around a specific query pattern instead of adding generic single-column indexes. The benefit is a seek plus a sorted, possibly index-only read; the cost is that the index serves mainly the queries that match its column order, grows wider with each added column, and adds work to every write on the table. It is the wrong choice when the access pattern is unstable or ad hoc (analytics that filter on arbitrary column combinations are better served by a columnar or search engine), when the leading column has low selectivity and no query uses a prefix, or when the table is write-heavy enough that maintenance dominates. Covering indexes and INCLUDE columns trade a larger index for fewer table lookups, and can quietly grow into a second copy of the table. Partial and expression indexes are powerful but brittle: a query must state its predicate in a form the planner can match to the index, so a small rewrite in application code can silently lose the index.