# Database Indexing and Query Optimization Interview Guide

Source: https://www.techinterview.org/post/3233463536/database-indexing-query-optimization/
Updated: 2026-04-17 · techinterview.org

## Database Indexing and Query Optimization for Interviews

Database indexing questions appear frequently in system design interviews and sometimes as standalone deep-dives. Understanding B-trees, index types, and query optimization is essential for senior engineering roles and is commonly tested at companies like Amazon, Google, Meta, and Databricks.

## Why Indexes Matter

Without an index, a query scans every row (O(n)). With a B-tree index, lookup is O(log n). For a table with 100 million rows: full scan = 100M reads, B-tree index lookup = ~27 comparisons (log₂(100M) ≈ 27).


```
-- Without index: full table scan (100M row reads)
SELECT * FROM orders WHERE user_id = 12345;

-- With index on user_id: B-tree lookup then row fetch
-- ~27 comparisons to find the index entry, then row fetch
CREATE INDEX idx_orders_user_id ON orders(user_id);
```


## B-Tree Index Structure

PostgreSQL, MySQL (InnoDB), and most RDBMS use B+ trees (a variant where all data lives in leaf nodes):

- **Root node**: Starting point, contains key ranges pointing to child nodes

- **Internal nodes**: Key ranges pointing to child nodes (no data)

- **Leaf nodes**: Actual index entries (key + row pointer/clustered data)

- **Linked leaf nodes**: Leaves form a doubly-linked list for range scans


```
B+ Tree visualization (order 3):
          [10 | 20]
         /    |    
      [5|8] [15|18] [25|30]
      ↓↓↓    ↓↓↓     ↓↓↓
   row ptrs row ptrs row ptrs  (leaf nodes linked: →→→)
```


**Height**: For n rows and branching factor b (typically 100-1000 for disk pages), height = log_b(n). A billion rows with b=1000: height = 3. Only 3 disk I/Os to find any row!

## Types of Indexes

### 1. B-Tree Index (default)


```
CREATE INDEX idx_name ON table(column);
-- Supports: =, , =, BETWEEN, LIKE 'prefix%'
-- Does NOT support: LIKE '%suffix', functions on column
```


### 2. Composite (Multi-Column) Index


```
CREATE INDEX idx_user_date ON orders(user_id, created_at);
-- This index can serve:
-- WHERE user_id = 5                          ✓ (leftmost prefix)
-- WHERE user_id = 5 AND created_at > '2024' ✓ (full use)
-- WHERE created_at > '2024'                  ✗ (not leftmost — index not used)
-- Rule: Leftmost prefix rule — must include leading columns
```


### 3. Hash Index


```
-- Only supports equality (=), NOT range queries
-- Memory engine in MySQL, Redis, Hash indexes in PostgreSQL
-- O(1) lookup vs O(log n) for B-tree
-- Use case: exact-match lookups (session cache, user lookup by email)
CREATE INDEX idx_email_hash ON users USING HASH (email);
```


### 4. Covering Index


```
-- Index contains ALL columns needed by query — no table lookup needed
CREATE INDEX idx_covering ON orders(user_id, total_amount, status);

-- This query is served entirely from the index (no heap fetch):
SELECT user_id, total_amount, status
FROM orders WHERE user_id = 5;
-- "Index only scan" in EXPLAIN — fastest possible
```


### 5. Partial Index


```
-- Index only rows matching a condition — smaller, faster
CREATE INDEX idx_active_users ON users(email) WHERE is_active = true;

-- Only indexes ~10% of users (active ones)
-- Much smaller than full-table index
-- Use case: soft-deleted records, status flags
```


### 6. GIN/GiST Indexes (PostgreSQL)


```
-- GIN (Generalized Inverted Index): for full-text search, JSONB, arrays
CREATE INDEX idx_tags ON posts USING GIN (tags);
SELECT * FROM posts WHERE tags @> ARRAY['python'];

-- GiST (Generalized Search Tree): for geometric/spatial data
CREATE INDEX idx_location ON stores USING GIST (location);
SELECT * FROM stores WHERE location <-> POINT(40.7, -74.0) < 10;
```


## Clustered vs Non-Clustered Indexes

| Property | Clustered | Non-Clustered |
| --- | --- | --- |
| Data storage | Rows stored in index order | Separate from row data |
| Per table | Only one allowed | Multiple allowed |
| Range scans | Extremely fast (rows adjacent) | Random I/O for each row |
| MySQL InnoDB | Primary key is clustered | Secondary indexes store PK |
| PostgreSQL | CLUSTER command (one-time) | All heap indexes |

**InnoDB secondary index overhead**: Secondary indexes store the primary key value. Lookup on secondary index → get PK → lookup clustered index (double lookup). This is why wide primary keys (UUIDs) are expensive in MySQL InnoDB — every secondary index carries the UUID overhead.

## EXPLAIN and Query Planning


```
-- EXPLAIN shows query plan without executing
EXPLAIN SELECT * FROM orders WHERE user_id = 5 AND total > 100;

-- EXPLAIN ANALYZE actually runs query and shows real timing
EXPLAIN ANALYZE SELECT * FROM orders WHERE user_id = 5 AND total > 100;

-- Key things to look for:
-- Seq Scan: full table scan — missing index
-- Index Scan: using B-tree index
-- Index Only Scan: covering index — no heap fetch
-- Bitmap Heap Scan: multiple index conditions combined
-- Nested Loop / Hash Join / Merge Join: join strategies

-- Rows estimate vs actual: large difference = stale statistics
-- Run ANALYZE to update: ANALYZE orders;
```


## Common Index Pitfalls

### Functions on Indexed Columns


```
-- BAD: index on created_at is NOT used (function applied first)
SELECT * FROM orders WHERE YEAR(created_at) = 2024;
SELECT * FROM orders WHERE LOWER(email) = 'user@example.com';

-- GOOD: rewrite to allow index use
SELECT * FROM orders WHERE created_at BETWEEN '2024-01-01' AND '2024-12-31';

-- GOOD: functional index (PostgreSQL)
CREATE INDEX idx_lower_email ON users (LOWER(email));
SELECT * FROM users WHERE LOWER(email) = 'user@example.com';
```


### Leading Wildcard


```
-- BAD: leading wildcard forces full scan
SELECT * FROM products WHERE name LIKE '%phone%';

-- GOOD: trailing wildcard uses index
SELECT * FROM products WHERE name LIKE 'phone%';

-- GOOD: for full-text search use GIN/tsvector
CREATE INDEX idx_fts ON products USING GIN(to_tsvector('english', name));
SELECT * FROM products WHERE to_tsvector('english', name) @@ 'phone';
```


### NULL Values


```
-- B-tree indexes DO include NULL values in PostgreSQL
-- IS NULL / IS NOT NULL CAN use B-tree index in PostgreSQL

-- Partial index trick for sparse non-null columns:
CREATE INDEX idx_premium ON users(premium_expires) WHERE premium_expires IS NOT NULL;
```


## Index Selectivity and Cardinality

**Selectivity** = unique values / total rows. High selectivity (close to 1.0) → index is valuable. Low selectivity → index scan may be slower than full table scan.


```
-- Check cardinality
SELECT COUNT(DISTINCT status) / COUNT(*) AS selectivity FROM orders;
-- status has values: pending/processing/completed/cancelled
-- selectivity ≈ 4/1,000,000 = 0.000004 — BAD candidate for B-tree index
-- user_id: unique per user → selectivity ≈ 1.0 — GREAT candidate

-- Rule of thumb: index is efficient when it eliminates >80% of rows
-- For status column: use partial index or bitmap index
```


## Write Overhead of Indexes

Every index slows down INSERT/UPDATE/DELETE because the index must be maintained. Each index = one additional B-tree write per DML operation. Guidelines:

- OLTP tables: 3-5 indexes max per table

- Data warehouse (OLAP): more indexes acceptable (fewer writes)

- Bulk insert: drop indexes, insert, rebuild — much faster than online maintenance

- PostgreSQL: CREATE INDEX CONCURRENTLY to build index without locking table

## Interview Questions and Answers

- **Why choose a composite index over two separate indexes?** Composite index can serve multi-column WHERE clauses with one lookup. Two separate indexes require a bitmap AND operation or optimizer must choose one. Composite is faster when both columns commonly appear together in queries.

- **When does the optimizer ignore an index?** When estimated cost of index scan + row fetch exceeds sequential scan (e.g., query returns >10-20% of table). Stale statistics cause wrong estimates — run ANALYZE.

- **How do you find slow queries in production?** PostgreSQL: pg_stat_statements extension, pg_stat_user_tables for sequential scan counts. MySQL: slow query log, performance_schema. Then EXPLAIN ANALYZE the top offenders.