Multi-Column WHERE — Index Selection

Real queries often have multiple conditions. The query planner must decide which index to use (if any) and how to handle the remaining conditions.

Access Predicates vs Filter Predicates

SELECT * FROM users WHERE name = 'Alice' AND age > 25

If we have an index on name:

• Access predicate: name = 'Alice' — used to search the index (O(log n))
• Filter predicate: age > 25 — checked against each row returned by the index

Step 1: Index lookup → name='Alice' → rowids [1, 7, 23]
Step 2: Fetch rows 1, 7, 23 from table
Step 3: Filter → keep only those with age > 25

The index eliminates most rows; the filter handles the rest.

Choosing Which Index to Use

If multiple indexes exist, the planner picks the most selective one:

-- Indexes exist on both 'name' and 'city'
SELECT * FROM users WHERE name = 'Alice' AND city = 'NYC'

If 'Alice' matches 5 rows and 'NYC' matches 50,000 rows, use the name index (more selective).

The .explain Output

.explain SELECT * FROM users WHERE age > 20 AND name = 'Alice'
→ SEARCH TABLE users USING INDEX idx_name (name='Alice') FILTER (age>20)

This shows:

• SEARCH: using an index (not a full scan)
• USING INDEX idx_name: which index
• FILTER (age>20): applied after the index lookup

No Useful Index

If no index matches any WHERE column:

.explain SELECT * FROM users WHERE age > 20 AND height < 180
-- No index on age or height
→ SCAN TABLE users

Falls back to a full table scan, checking both conditions against every row.

Composite Indexes

A single index on multiple columns is called a composite (or compound) index:

CREATE INDEX idx_name_age ON users (name, age)

This index supports:

• WHERE name = 'Alice' (uses first column)
• WHERE name = 'Alice' AND age > 25 (uses both columns)
• WHERE age > 25 alone? No! (leftmost prefix rule)

The leftmost prefix rule: a composite index can only be used if the query includes the leftmost column(s) of the index.

How PostgreSQL Selects Indexes

PostgreSQL's planner (costsize.c) calculates a cost for each available index and compares with the table scan cost. It considers:

• Index selectivity (estimated from pg_stats)
• Correlation between physical row order and index order
• Whether an index-only scan is possible

How SQLite Selects Indexes

SQLite's NGQP (Next Generation Query Planner) tries different combinations of indexes and picks the lowest estimated cost. The ANALYZE command populates sqlite_stat1 with histograms for better selectivity estimates.

Your Task

When WHERE has multiple conditions, use the best available index for the most selective condition and apply remaining conditions as filters. Show this in .explain.