Indexing and Query Optimization

Before you add Redis or shard the database, ask whether the right index would fix the slow query. Indexing is how you turn full table scans into millisecond lookups — and how you accidentally slow down every write.

An index is a sorted lookup structure — design columns to match the WHERE and ORDER BY clauses you actually run:

Indexes are how we turn full table scans into point lookups — but every index taxes writes. We frame the discussion around three lenses:

Walk the query path as interview steps. Step 1 — Parse: SQL arrives at the optimizer. Step 2 — Plan: optimizer chooses index seek vs sequential scan based on selectivity and stats. Step 3 — Index seek: B-tree traversal to matching rows — O(log n) instead of O(n). Step 4 — Covering index: if all SELECT columns live in the index, skip the heap fetch. Step 5 — Write path: every INSERT/UPDATE maintains index pages — name the write amplification.

These index types and optimizer behaviors are what we cite when sizing read vs write cost:

• Clustered Index: Organizes the raw table rows on disk physically sorted by the primary key (maximum one per table).
• Non-Clustered Index: A separate tree storing secondary keys pointing to primary key addresses.
• Partial Index: Indexes only rows matching a predicate (e.g. WHERE status = 'ACTIVE') — smaller and faster for filtered hot paths.
• Covering Index: Includes all columns in the SELECT clause so the engine never touches the heap — enables index-only scans.
• Leftmost Prefix Rule: A composite index on (A, B, C) only helps queries that filter on column A first.
• Index type matrix — match structure to query pattern:

Indexes accelerate reads but slow writes — we articulate the trade-off:

Missing indexes and over-indexing both kill production systems — we name the failure modes:

These patterns show where indexing changes the architecture conversation:

Reach for index discussion when point lookups or sort-heavy queries dominate the hot path:

Indexing pairs with sharding (local indexes per shard) and SQL vs NoSQL access-pattern design:

• LSM-Tree vs B+Tree (comparing append-heavy storage vs read-optimized databases)
• Database Partitioning & Sharding (routing queries across multi-node databases)
• Query Execution Plans (compiling, optimizing, and execution maps of SQL engines)
• Full-Text Inverted Indexing (tokenization and search indexing internals)
• Geospatial S2 & H3 Hierarchies (geospatial coordinates representation)

In interviews, propose indexes on columns that appear in frequent WHERE, JOIN, and ORDER BY clauses — email for login, user_id on child tables, composite keys for timeline queries. For search beyond SQL, mention Elasticsearch or PostGIS synced via CDC with acceptable lag.

Clustered vs Non-Clustered Storage Mechanics

In clustered indexes (e.g., MySQL's InnoDB primary key), leaf nodes store the actual physical data row on disk. In secondary non-clustered indexes, the leaf nodes store the secondary search key and the primary key as a row pointer. To retrieve non-indexed columns, the database must traverse the secondary index tree, find the primary key, and then traverse the primary clustered index tree (double lookup or key lookup).

Composite Index Rule Mathematics

When planning multi-column composite indexes, you must adhere to the Equality-first, Sort-next, Range-last optimization math:

-- For Query: 
WHERE status = 'ACTIVE' AND user_id = 100 AND created_at > '2024-01-01' 
ORDER BY created_at DESC;

-- Best Composite Index columns:
(user_id, status, created_at)

• Columns filtered with exact match (=) must come first.
• Columns utilized in sorting (ORDER BY) come second.
• Columns queried with range comparisons (>, <, BETWEEN) must come last. Range columns break B+Tree index traversal chain for subsequent columns.

Covering Indexes & Index-Only Scans

A covering index contains all columns requested in the query. For example, if you index (user_id, status) and query: SELECT status FROM users WHERE user_id = 10, the database reads the index leaf node directly and returns the response. It completely skips accessing raw table data on disk, reducing I/O operations to near zero.

Query Execution Analysis (EXPLAIN)

To verify database optimizer decisions, prefix queries with EXPLAIN or EXPLAIN ANALYZE. High-performing queries will list:

• type: ref or eq_ref (using index lookup).
• Extra: Using index (confirming covering index).
• Low rows scanned ratio (ideally close to returned count).
• Avoid Extra: Using filesort or Extra: Using temporary (indicates slow non-indexed in-memory sorting).

LSM-Tree Write Path (Cassandra, RocksDB, LevelDB)

B+Tree indexes optimize for read latency — every INSERT updates random pages on disk, which hurts write-heavy workloads. Log-Structured Merge (LSM) trees flip the model: writes append sequentially to an in-memory memtable and a write-ahead log; when the memtable fills, it flushes to immutable SST files on disk. Reads check memtable → bloom filter → SST layers (newest to oldest).

• Write amplification: Background compaction merges SST files — disk I/O continues after writes "complete."
• Read amplification: A key may exist in multiple SST layers until compaction runs; bloom filters skip absent keys cheaply.
• Interview fit: Choose LSM-backed stores for append-heavy telemetry, messaging metadata, and write-heavy KV — choose B+Tree OLTP when complex indexed reads dominate.