Indexes

Why Queries Slow Down — And What Indexes Do About It

Imagine a physical library with one million books, completely unsorted. No catalogue, no shelves organised by topic, no numbering system. Just books piled randomly across thousands of shelves. Someone walks in and asks: "Do you have a book called Database System Concepts by Silberschatz?" The only way to find it is to walk through every single shelf and read every single book title until you either find it or exhaust every possibility. In the worst case — the book isn't there — you checked one million books for nothing.

This is exactly what a database does when you query a table with no index. It reads every single row from disk, evaluates your WHERE condition against each one, and keeps the matches. This operation is called a full table scan (or sequential scan), and at small data volumes it is perfectly acceptable. At millions of rows, it becomes the difference between a query taking 2 milliseconds and 8 seconds.

Now imagine the library installs a catalogue — a small organised book that tells you exactly which shelf and position every book is on, sorted alphabetically by title. Finding "Database System Concepts" takes two seconds: open the catalogue, flip to D, find the entry, walk directly to shelf 47 row 3. Done. You checked perhaps 20 entries in the catalogue instead of one million books on the shelves. That catalogue is a database index.

That is not a small difference. It is a 4000× speedup for one missing index on one query. At Swiggy's scale — tens of millions of orders, queries running thousands of times per second — a missing index can bring down an entire service. Adding the right index can fix a production incident in under a minute. This is why indexes are one of the most practically important topics in all of database engineering.

What an Index Actually Is

An index is a separate data structure stored alongside the table, maintained automatically by the DBMS. It contains a sorted copy of the values in the indexed column(s), along with pointers to the actual row locations on disk. When you query using an indexed column, the database uses the index to find the right disk location directly — without reading unrelated rows at all.

The key properties of an index: it speeds up reads dramatically, it costs storage space (an index can be as large as the table itself for wide tables), and it slows down writes slightly (every INSERT, UPDATE, and DELETE must also update every index on that table). This trade-off — faster reads, slower writes, more storage — is the central tension of index design.

-- CREATE an index (the most common operation)
CREATE INDEX idx_orders_customer ON orders(customer_id);
-- Index name convention: idx_{table}_{column(s)}
-- This creates a B+ tree index by default in PostgreSQL and MySQL

-- CREATE a UNIQUE index (also enforces uniqueness constraint)
CREATE UNIQUE INDEX idx_customers_email ON customers(email);
-- Equivalent to: ALTER TABLE customers ADD CONSTRAINT UNIQUE(email)

-- CREATE INDEX CONCURRENTLY (PostgreSQL — safe on live production tables)
CREATE INDEX CONCURRENTLY idx_orders_date ON orders(order_date);
-- Without CONCURRENTLY: locks the table during index creation (dangerous in production)
-- With CONCURRENTLY: builds the index without any table lock (takes longer but safe)

-- DROP an index
DROP INDEX idx_orders_customer;

-- View indexes on a table (PostgreSQL)
SELECT indexname, indexdef
FROM pg_indexes
WHERE tablename = 'orders';

-- View indexes on a table (MySQL)
SHOW INDEX FROM orders;

How Databases Store Data on Disk — Pages, Blocks, and Heap Files

To understand why indexes work the way they do, you need to understand how databases physically store data. This is the layer that index structures are specifically designed to navigate efficiently.

Pages — The Fundamental Unit of Disk Storage

Databases never read or write individual rows to disk. They operate in fixed-size units called pages (also called blocks). A page is typically 8KB in PostgreSQL (configurable), 16KB in MySQL InnoDB. Every read from disk retrieves at least one full page. Every write writes at least one full page.

A single page contains many rows. For a typical orders table where each row is about 200 bytes, an 8KB page holds roughly 40 rows. This means reading one order from disk also reads the 39 rows stored near it on the same page — whether you wanted those rows or not. This is why sequential scans are expensive: they read every page in the table, even if only a fraction of rows on each page match your query.

Heap Files — Unordered Row Storage

By default, database tables store rows in a heap file — an unordered collection of pages where rows are inserted wherever space is available. There is no particular order to the rows. A row inserted today might be on page 1. The next row might go to page 847 because that is where the last available space was. Heap files make inserts fast (just find free space and write) but make targeted lookups slow (no structure to navigate to a specific row without an index).

This is why a new table with no indexes behaves as we described: finding one row requires reading the entire heap file page by page. An index is a separately maintained structure that provides the navigation shortcut the heap file inherently lacks.

The Buffer Pool — How Databases Cache Pages in RAM

The database does not read from disk every time it needs a page. It maintains a buffer pool — a cache of recently accessed pages kept in RAM. When a query needs a page, the database checks the buffer pool first. If the page is there (a cache hit), it uses the RAM copy — microseconds. If not (a cache miss), it reads from disk — milliseconds.

This means query performance depends on the buffer pool hit rate. Frequently accessed index pages (especially the upper levels of a B+ tree) stay permanently in the buffer pool on a busy system — making index lookups even faster in practice than the raw numbers suggest. The root and upper levels of a B+ tree on a production system are almost always in RAM.

B+ Tree — The Data Structure Behind Every Standard Index

The vast majority of database indexes use a data structure called the B+ tree. Understanding why B+ trees specifically — and not binary search trees, red-black trees, or hash tables — requires understanding the constraints of disk-based storage.

Why Not Binary Search Trees?

A binary search tree (BST) gives O(log₂ n) search time and seems like a natural choice for an index. But BSTs have one fatal property for disk-based storage: each node has at most 2 children. For a table with 50 million rows, a balanced BST has a height of log₂(50,000,000) ≈ 26 levels. Each level potentially requires a separate disk read (if the node is not in the buffer pool). 26 disk reads × ~5 milliseconds per disk read = 130 milliseconds per query. At 10,000 queries per second, this is unacceptable.

The solution: make each node much wider. Instead of 2 children, allow thousands of children per node. This dramatically reduces the height of the tree. A B+ tree node with 1000 children on 50 million rows has height log₁₀₀₀(50,000,000) ≈ 3 levels. Three disk reads instead of 26. This is the core design insight of B+ trees.

B+ Tree Structure — Internal Nodes and Leaf Nodes

A B+ tree has two types of nodes with different purposes:

The Critical Property — All Leaf Nodes Are Linked

The defining feature that makes B+ trees superior to B-trees for databases: all leaf nodes are connected in a doubly-linked listfrom left to right. After finding the first matching key using the tree traversal, you can follow the linked list forward to retrieve all subsequent matching keys in sorted order — without going back up the tree.

This is what makes range queries (WHERE age BETWEEN 25 AND 35, WHERE order_date > '2024-01-01') fast. Find the first matching leaf node using tree traversal, then walk the linked list collecting all subsequent matches until the range condition is no longer satisfied. No re-traversal of the tree needed for each match.

B+ Tree Search — Step by Step

// QUERY: SELECT * FROM orders WHERE customer_id = 'C042'
// B+ tree index exists on customer_id

// STEP 1: Read the ROOT node (almost always in buffer pool — cached in RAM)
// Root contains: [C030 | C060 | C090]
// C042 > C030 AND C042 < C060 → follow pointer to SECOND child

// STEP 2: Read the INTERNAL NODE at level 2 (may be cached)
// Node contains: [C040 | C050 | C060]
// C042 > C040 AND C042 < C050 → follow pointer to FIRST child of this node

// STEP 3: Read the LEAF NODE
// Leaf contains: [C040→page12, C041→page18, C042→page7, C043→page22, C044→page9]
// C042 found! Pointer says: the row is on page 7

// STEP 4: Read DATA PAGE 7 from the heap file
// Retrieve the actual row data for customer C042

// TOTAL DISK READS: 4 (root + level2 + leaf + data page)
// For 50 million rows with branching factor 1000: 3 levels + 1 = 4 reads
// Compare: full table scan would read every page of the heap file
//          For 50M rows at 40 rows/page: 1,250,000 page reads

// RANGE QUERY: WHERE customer_id BETWEEN 'C040' AND 'C060'
// Step 1-3: same as above — navigate to leaf containing C040
// Step 4: read all matching rows from data pages for C040, C041... C060
// Step 5: follow leaf linked list forward to C041's leaf page (if different page)
// Continue until C060 is passed
// TOTAL: 3 tree reads + (number of matching leaf pages) + (number of matching data pages)
// Still dramatically fewer reads than full scan

B+ Tree Insertion — How the Tree Grows

Insertions are what make indexes cost something. Every time a row is inserted into the table, the database must also insert the new key into every index on that table. B+ tree insertion works as follows: navigate to the correct leaf node, insert the key in sorted position. If the leaf node is full (has reached maximum capacity), split it into two nodes and push the middle key up to the parent internal node. If the parent is also full, split it too. This splitting can cascade all the way to the root — when the root splits, a new root is created and the tree grows one level taller.

// ORDER: INSERT INTO orders VALUES ('C042', ...) — index on customer_id

// Before insertion — leaf node is full (max 4 keys in this example):
// Leaf: [C040 | C041 | C043 | C044]

// Insert C042 in sorted position → overflow:
// [C040 | C041 | C042 | C043 | C044] → exceeds capacity

// SPLIT: divide into two leaf nodes
// Left leaf:  [C040 | C041 | C042]
// Right leaf: [C043 | C044]
// Push middle key (C042) up to parent internal node

// Parent internal node before: [C030 | C060]
// After push-up: [C030 | C042 | C060] — with new pointer to right leaf
// Parent not full → no further splitting needed

// INSERT COST: O(log_B n) comparisons + potentially O(log_B n) page writes
// B = branching factor (typically 100-1000)
// At 50M rows: ~3 page reads + potentially 3 page writes for splits (rare)
// Most insertions do NOT cause splits — leaf nodes are often half-empty

B+ Tree Deletion

Deletion is the inverse of insertion. Navigate to the leaf node containing the key and remove it. If the leaf node falls below the minimum occupancy threshold (typically 50%), either borrow a key from a sibling node (redistribution) or merge with a sibling (underflow merge). Merging can cascade up the tree similarly to how splits cascade during insertion. In practice, databases often leave slightly underfull pages without immediate merging — merging is triggered periodically by maintenance operations (VACUUM in PostgreSQL).

Every Index Type — What It Is, When to Use It, When to Avoid It

-- MySQL InnoDB: PRIMARY KEY is always the clustered index
CREATE TABLE orders (
    order_id    INT PRIMARY KEY AUTO_INCREMENT,  -- clustered index automatically
    customer_id INT NOT NULL,
    order_date  DATETIME,
    total       DECIMAL(10,2)
);
-- Rows on disk: sorted by order_id (sequential integers = perfect clustering)

-- PostgreSQL: CLUSTER command (one-time reorganisation, not auto-maintained)
CREATE TABLE orders (order_id SERIAL PRIMARY KEY, ...);
CREATE INDEX idx_orders_date ON orders(order_date);
CLUSTER orders USING idx_orders_date;
-- Physically reorders table rows by order_date RIGHT NOW
-- Future inserts are NOT automatically in sorted order
-- Must run CLUSTER again periodically to maintain physical ordering

-- CHECKING: which columns benefit from clustered access?
-- Columns used in ORDER BY + LIMIT (pagination)
-- Columns used in range queries: BETWEEN, >, 
-- Primary key columns (always)

-- Table with multiple non-clustered indexes:
CREATE TABLE orders (
    order_id      SERIAL   PRIMARY KEY,     -- clustered (MySQL) or heap (PostgreSQL)
    customer_id   INT      NOT NULL,
    restaurant_id INT      NOT NULL,
    order_date    TIMESTAMP,
    status        VARCHAR(20),
    total_amount  DECIMAL(10,2)
);

-- Non-clustered index on customer_id (most common query: "orders for this customer")
CREATE INDEX idx_orders_customer ON orders(customer_id);

-- Non-clustered index on order_date (range queries: "orders in this month")
CREATE INDEX idx_orders_date ON orders(order_date);

-- Non-clustered index on status (filter: "all pending orders")
CREATE INDEX idx_orders_status ON orders(status);
-- ⚠ BUT: is a status index useful? See "when NOT to index" section below.

-- HOW NON-CLUSTERED LOOKUP WORKS:
-- Query: SELECT * FROM orders WHERE customer_id = 5
-- Step 1: B+ tree traversal in idx_orders_customer → finds leaf nodes for C_id=5
-- Step 2: Leaf node contains pointer: "row is at page 47, slot 3 in heap file"
-- Step 3: Read page 47 of the heap file → retrieve the row
-- Total: ~3 tree reads + 1 data page read per matching row
-- For customers with many orders: each order might be on a DIFFERENT data page
-- This is called "random I/O" — expensive if many rows match

-- Index on (customer_id, order_date)
CREATE INDEX idx_orders_customer_date ON orders(customer_id, order_date);

-- QUERIES THAT USE THIS INDEX:
-- 1. Filter on customer_id alone (uses first column of composite index):
SELECT * FROM orders WHERE customer_id = 5;
-- Uses index: scans all entries where first key = 5

-- 2. Filter on customer_id AND order_date (uses both columns):
SELECT * FROM orders WHERE customer_id = 5 AND order_date >= '2024-01-01';
-- Uses index optimally: navigates to customer_id=5 entries, then filters by date

-- 3. Filter + sort using index (no separate sort step needed):
SELECT * FROM orders WHERE customer_id = 5 ORDER BY order_date;
-- Perfect: results are already sorted by date within customer_id=5

-- QUERIES THAT DO NOT FULLY USE THIS INDEX:
-- 4. Filter on order_date alone:
SELECT * FROM orders WHERE order_date >= '2024-01-01';
-- Cannot use the index efficiently! order_date is the SECOND column.
-- The index sorts by customer_id first — within each customer, dates are sorted,
-- but across ALL customers, dates are not in order.
-- Result: full index scan or table scan depending on selectivity.
-- FIX: create a separate index on just order_date.

-- 5. Filter on order_date with different customer:
SELECT * FROM orders WHERE order_date >= '2024-01-01' AND customer_id = 5;
-- This DOES use the index — the query optimizer recognizes both columns are present
-- and can apply them in index order (customer_id first, then date).

-- COLUMN ORDER DECISION RULE:
-- Put the most selective column FIRST (the one that filters the most rows)
-- Put equality conditions BEFORE range conditions in the index definition
-- CREATE INDEX idx ON table(equality_col, range_col) -- correct ordering
-- CREATE INDEX idx ON table(range_col, equality_col) -- less optimal

-- Query we want to optimise (runs millions of times per day):
SELECT order_id, order_date, total_amount
FROM orders
WHERE customer_id = 5
ORDER BY order_date DESC
LIMIT 20;

-- Non-covering index (requires table access):
CREATE INDEX idx_orders_customer ON orders(customer_id);
-- Steps: B+ tree → leaf (has customer_id + row pointer) → follow 20 pointers to data pages
-- = 1 index lookup + up to 20 data page reads

-- COVERING index (no table access needed):
CREATE INDEX idx_orders_customer_covering
ON orders(customer_id, order_date DESC)
INCLUDE (order_id, total_amount);
-- Leaf node now contains: customer_id, order_date, order_id, total_amount
-- Steps: B+ tree → leaf → DONE (all needed columns are IN the leaf node)
-- = 1 index lookup + 0 data page reads
-- Dramatically faster — especially when data pages are not in buffer pool

-- PostgreSQL EXPLAIN output difference:
-- WITHOUT covering: Index Scan using idx_orders_customer (also reads heap)
-- WITH covering:    Index Only Scan using idx_orders_customer_covering
-- "Index Only Scan" = covering index hit — the holy grail of query optimization

-- DESIGN RULE FOR COVERING INDEXES:
-- Index columns: all WHERE and ORDER BY columns (determine sort order)
-- INCLUDE columns: all SELECT columns that are not in WHERE/ORDER BY
-- (INCLUDE columns don't affect index order — they just ride along for free)

-- Example:
CREATE INDEX idx_order_lookup ON orders
    (customer_id, status)        -- WHERE/ORDER BY columns
INCLUDE
    (order_id, total_amount, order_date);  -- SELECT columns

-- CREATE a hash index (PostgreSQL explicit syntax):
CREATE INDEX idx_sessions_token ON sessions USING HASH(session_token);
-- Perfect: session_token lookups are ALWAYS exact equality (never range)
-- WHERE session_token = 'abc123xyz...' ← hash index excels here

-- MySQL InnoDB: automatically uses hash-based "adaptive hash index" internally
-- You don't create hash indexes explicitly in MySQL — InnoDB manages them

-- USE HASH INDEX FOR:
SELECT * FROM sessions WHERE session_token = 'abc123xyz';   -- exact equality ✓
SELECT * FROM users   WHERE username = 'rahul_sharma';       -- exact equality ✓
SELECT * FROM cache   WHERE cache_key = 'product:P001';      -- exact equality ✓

-- DO NOT USE HASH INDEX FOR:
SELECT * FROM orders WHERE total_amount > 500;               -- range: USELESS
SELECT * FROM orders WHERE total_amount BETWEEN 200 AND 500; -- range: USELESS
SELECT * FROM customers ORDER BY age;                        -- ordering: USELESS
SELECT * FROM orders WHERE order_date LIKE '2024%';          -- pattern: USELESS

-- DECISION RULE: Use B+ tree indexes for almost everything.
-- Hash indexes are a micro-optimisation for columns that are ONLY ever
-- queried with exact equality and never with ranges or ordering.
-- In PostgreSQL, the B+ tree index on equality queries is almost as fast
-- as a hash index due to buffer pool caching of tree root nodes.
-- B+ tree is the safe default. Hash index is a very specific optimisation.

-- SCENARIO: 10 million orders. 99% are 'delivered'. Only 1% are 'pending'.
-- You only ever query pending orders in the operations dashboard.

-- Full index on status (wasteful):
CREATE INDEX idx_orders_status_full ON orders(status);
-- Index contains 10 million entries — 99% are 'delivered' which you never query this way

-- Partial index (only pending orders):
CREATE INDEX idx_orders_pending ON orders(order_id)
WHERE status = 'pending';
-- Index contains only 100,000 entries — 100x smaller, 100x faster to scan

-- Query that uses the partial index:
SELECT * FROM orders WHERE status = 'pending';
-- Optimizer sees the partial index covers exactly this query → uses it

-- More examples:
-- Index only active users (most users are inactive):
CREATE INDEX idx_users_active_email ON users(email)
WHERE is_active = true;

-- Index only large orders (most orders are small):
CREATE INDEX idx_large_orders ON orders(customer_id, total_amount)
WHERE total_amount > 1000;

-- Index only unprocessed events:
CREATE INDEX idx_events_unprocessed ON events(created_at)
WHERE processed_at IS NULL;

-- BENEFIT CALCULATION:
-- Table: 10M rows, 50KB per index entry
-- Full index: 500MB storage, updated on EVERY insert/update
-- Partial index (1% of rows): 5MB storage, updated only when pending rows change
-- For high-write systems: partial indexes can be 10-100x more efficient

-- PROBLEM: case-insensitive email search
-- Query: WHERE LOWER(email) = 'rahul@example.com'
-- Without functional index: LOWER() is computed on every row — cannot use regular index
SELECT * FROM users WHERE LOWER(email) = 'rahul@example.com';

-- SOLUTION: Index on LOWER(email)
CREATE INDEX idx_users_email_lower ON users(LOWER(email));
-- Now: WHERE LOWER(email) = 'rahul@example.com' uses the index ✓

-- Another example: date part extraction
-- Query: find all orders from 2024
-- Without functional index: full scan computing EXTRACT on every row
SELECT * FROM orders WHERE EXTRACT(YEAR FROM order_date) = 2024;

-- With functional index:
CREATE INDEX idx_orders_year ON orders(EXTRACT(YEAR FROM order_date));
-- Much better: still better to use range: WHERE order_date BETWEEN '2024-01-01' AND '2024-12-31'

-- JSON field indexing (PostgreSQL):
-- Index a specific field inside a JSONB column
CREATE INDEX idx_metadata_city ON customers((metadata->>'city'));
-- Query: WHERE metadata->>'city' = 'Bengaluru' now uses the index

When NOT to Add an Index — The Cases That Hurt More Than They Help

Every index has a cost. Storage space for the index structure itself. CPU and disk writes to maintain the index on every INSERT, UPDATE, and DELETE. Buffer pool space competing with actual data pages. More index options for the query optimiser to evaluate. Adding indexes blindly — indexing every column "just in case" — is a common mistake that makes write-heavy systems significantly slower without meaningful read improvement.

EXPLAIN and EXPLAIN ANALYZE — Reading the Database's Execution Plan

The EXPLAIN command shows you how the database plans to execute a query — which indexes it will use, which join algorithms it chooses, how many rows it estimates at each step. EXPLAIN ANALYZE actually executes the query and shows both the plan AND the actual measured runtime statistics. This is the primary diagnostic tool for query performance.

Key Scan Types — What They Mean

-- Run EXPLAIN ANALYZE on a slow query
EXPLAIN ANALYZE
SELECT o.order_id, c.name, o.total_amount
FROM orders o
JOIN customers c ON o.customer_id = c.customer_id
WHERE o.status = 'pending'
  AND o.total_amount > 500;

-- EXAMPLE OUTPUT:
-- Hash Join  (cost=1500.00..8400.00 rows=450 width=64)
--             (actual time=45.123..156.789 rows=423 loops=1)
--   Hash Cond: (o.customer_id = c.customer_id)
--   ->  Seq Scan on orders o
--         (cost=0.00..6500.00 rows=850 width=40)
--         (actual time=0.025..145.234 rows=847 loops=1)
--         Filter: ((status = 'pending') AND (total_amount > 500))
--         Rows Removed by Filter: 9153153
--   ->  Hash  (cost=600.00..600.00 rows=72000 width=28)
--         (actual time=32.456..32.456 rows=72000 loops=1)
--       ->  Seq Scan on customers c
--             (cost=0.00..600.00 rows=72000 width=28)
--             (actual time=0.012..18.234 rows=72000 loops=1)
-- Planning Time: 2.345 ms
-- Execution Time: 157.123 ms

-- READING THE OUTPUT:
-- "Seq Scan on orders" → full table scan on 10M row table → PROBLEM
-- "Rows Removed by Filter: 9153153" → reading 10M rows to find 847 → 99.99% waste
-- "Execution Time: 157ms" → acceptable? not for a user-facing API endpoint

-- DIAGNOSIS:
-- The Seq Scan on orders is the bottleneck
-- WHERE clause: status = 'pending' AND total_amount > 500
-- FIX: Add a partial index on pending orders with total_amount

CREATE INDEX idx_orders_pending_large
ON orders(total_amount)
WHERE status = 'pending';

-- AFTER INDEX:
-- Index Scan using idx_orders_pending_large on orders
--   (actual time=0.123..2.456 rows=847 loops=1)
--   Index Cond: (total_amount > 500)
-- Execution Time: 4.567 ms
-- 35x improvement from adding one targeted index

-- KEY NUMBERS TO LOOK FOR IN EXPLAIN ANALYZE:
-- "Rows Removed by Filter" large → index could help filter earlier
-- "actual rows" >> "estimated rows" → statistics are stale → run ANALYZE
-- "actual time" large for a node → that node is the bottleneck
-- "loops" > 1 → this node runs multiple times (e.g., inner side of nested loop join)
-- cost=X..Y → X=startup cost (first row), Y=total cost (all rows)

Common Query Optimisation Patterns

-- PATTERN 1: Leading wildcard LIKE cannot use B+ tree index
-- SLOW: leading % forces full scan
SELECT * FROM customers WHERE name LIKE '%Sharma%';
-- The B+ tree is sorted by name — we don't know where names containing "Sharma" start

-- BETTER: trailing wildcard CAN use index (scans from prefix)
SELECT * FROM customers WHERE name LIKE 'Sharma%';
-- Uses index: starts at "Sharma" in sorted order, reads forward

-- BEST for arbitrary substring search: Full-Text Search
CREATE INDEX idx_customers_name_fts ON customers USING GIN(to_tsvector('english', name));
SELECT * FROM customers WHERE to_tsvector('english', name) @@ to_tsquery('Sharma');

-- PATTERN 2: Function on indexed column disables the index
-- SLOW: applying function to column prevents index use
SELECT * FROM orders WHERE EXTRACT(YEAR FROM order_date) = 2024;
-- Function applied to order_date → cannot use B+ tree index on order_date

-- FAST: use range instead of function
SELECT * FROM orders WHERE order_date >= '2024-01-01' AND order_date < '2025-01-01';
-- Range query → B+ tree index on order_date used efficiently

-- PATTERN 3: Implicit type conversion disables index
-- SLOW: comparing VARCHAR column to integer causes implicit cast
SELECT * FROM customers WHERE customer_id = 42;  -- customer_id is VARCHAR
-- FAST: match types explicitly
SELECT * FROM customers WHERE customer_id = '42';  -- same type as column

-- PATTERN 4: OR conditions often prevent index use
-- SLOW: OR can force full scan (depends on optimizer sophistication)
SELECT * FROM orders WHERE status = 'pending' OR status = 'confirmed';
-- FAST: use IN (optimizer handles better)
SELECT * FROM orders WHERE status IN ('pending', 'confirmed');
-- OR BEST: UNION ALL if each condition benefits from different index
SELECT * FROM orders WHERE status = 'pending'
UNION ALL
SELECT * FROM orders WHERE status = 'confirmed';

-- PATTERN 5: ORDER BY + LIMIT uses index efficiently
-- If index matches ORDER BY column, no separate sort step is needed
CREATE INDEX idx_orders_date ON orders(order_date DESC);
-- This query is extremely fast:
SELECT * FROM orders ORDER BY order_date DESC LIMIT 20;
-- Uses index scan directly — no sort, reads exactly 20 leaf pages

Index Maintenance — Bloat, Fragmentation, and Keeping Indexes Healthy

Indexes degrade over time. Heavy insert and delete workloads leave partially empty pages (fragmentation). Deleted rows leave dead entries in index leaf nodes (bloat). Both conditions make the index slower than it should be — the database must read more pages to retrieve the same data, and the index takes more disk space than necessary. Regular maintenance is required.

Index Bloat and Fragmentation

When a row is deleted from a table, the corresponding entry in every index is marked as dead — but the space is not immediately reclaimed. Over time, especially in high-churn tables (many deletes and updates), indexes can become bloated with dead entries. The index size grows while the useful data shrinks. PostgreSQL's VACUUM process cleans dead tuples, but indexes may still become fragmented (many half-empty pages in a non-contiguous layout on disk).

-- POSTGRESQL: VACUUM cleans dead tuples from tables and indexes
VACUUM orders;             -- clean dead tuples, non-blocking
VACUUM ANALYZE orders;     -- clean + update statistics (optimizer uses statistics)
VACUUM FULL orders;        -- full rewrite, reclaim all space (BLOCKS table — use in maintenance window)

-- Check for index bloat (PostgreSQL):
SELECT
    schemaname,
    tablename,
    indexname,
    pg_size_pretty(pg_relation_size(indexrelid)) AS index_size,
    idx_scan    AS times_used,
    idx_tup_read,
    idx_tup_fetch
FROM pg_stat_user_indexes
ORDER BY pg_relation_size(indexrelid) DESC;

-- Find unused indexes (indexes never used since last stats reset):
SELECT schemaname, tablename, indexname, idx_scan
FROM pg_stat_user_indexes
WHERE idx_scan = 0
  AND indexname NOT LIKE '%_pkey'  -- exclude primary keys
ORDER BY schemaname, tablename;
-- Consider dropping indexes with idx_scan = 0 — they are pure overhead

-- REINDEX: rebuild an index from scratch (removes bloat, fixes fragmentation)
REINDEX INDEX idx_orders_customer;       -- specific index
REINDEX TABLE orders;                     -- all indexes on table
REINDEX INDEX CONCURRENTLY idx_orders_customer;  -- non-blocking (PostgreSQL 12+)

-- MYSQL: ANALYZE TABLE updates statistics
ANALYZE TABLE orders;

-- MYSQL: OPTIMIZE TABLE rebuilds table and indexes (equivalent to VACUUM FULL + REINDEX)
OPTIMIZE TABLE orders;  -- ⚠ locks table during operation — use in maintenance window

-- Statistics matter: the query optimizer uses row count estimates and
-- value distributions to choose execution plans. Stale statistics cause
-- the optimizer to make wrong decisions (wrong join order, wrong index).
-- Run ANALYZE regularly on frequently updated tables.

The 3am Alert — Diagnosing and Fixing a Missing Index in Production

This is the most realistic production scenario involving indexes. It happens at every company that operates at scale. Understanding this sequence — alert, diagnosis, fix — is what makes you a valuable engineer.

Index Interview Questions — With Complete Answers