Indexes

A database index is a separate data structure maintained alongside a table that maps column values to the physical locations of rows containing those values. Without an index, finding rows that satisfy a WHERE condition requires reading every row in the table — a sequential scan that is O(n) in cost. With a B-tree index, the database traverses a sorted tree structure in O(log n) time to find the matching rows, then fetches only those rows from the table. For a table with 10 million rows, this is the difference between examining 10 million rows versus 3-4 tree nodes.

The most common index type is the B-tree (balanced tree). The tree is kept sorted by the indexed column values. Each internal node points to child nodes whose values fall in a specific range. Each leaf node points to the actual table rows. The balance property ensures every lookup takes the same number of steps — typically 3-4 for tables with millions of rows — regardless of which value is being searched.

Indexes also benefit ORDER BY (the index is already sorted, so no sort step is needed), MIN and MAX (first and last leaf of the index), and JOIN conditions (the FK column is looked up in the index instead of scanned). The cost of indexes is write overhead — every INSERT, UPDATE, and DELETE must also update all indexes on the table. A table with 10 indexes pays 10 index maintenance operations per write. This is why indexes must be chosen deliberately: create the indexes the query workload needs, and periodically audit and remove unused ones.

A clustered index determines the physical order in which rows are stored on disk — the table's rows are physically sorted by the clustered index column. Because the data is stored in index order, range scans on the clustered column are extremely efficient (rows in a date range are adjacent on disk and read in one sequential sweep). Each table can have only one clustered index because the rows can only be physically ordered one way.

SQL Server and MySQL InnoDB have explicit clustered index syntax. In SQL Server, CREATE CLUSTERED INDEX is a DDL operation. In MySQL InnoDB, the PRIMARY KEY is automatically the clustered index — the table is stored in primary key order. If no primary key exists, InnoDB selects a hidden row ID column. In PostgreSQL, there is no persistent clustered index — CLUSTER table_name USING index_name physically reorders the table once, but the order is not maintained as new rows are inserted.

A non-clustered index (the standard type in most databases) is a separate structure from the table data. Leaf nodes contain the indexed column values plus a pointer (row ID or primary key) to the actual table row. Range scans on a non-clustered index may require many random disk accesses to fetch matching rows from the heap — this is efficient for highly selective queries (few matching rows) but slower than a clustered index for large range scans. For most OLTP workloads: use the primary key as the clustered index (usually the auto-increment or UUID ID), and create non-clustered indexes on FK columns and frequently filtered columns.

A composite index covers multiple columns, defined in a specific order: CREATE INDEX ON orders(store_id, order_date). The B-tree sorts entries first by store_id, then by order_date within each store_id group. This means the index is useful for queries that filter on store_id (the leading column) — the database can go directly to the store_id section of the index. It is also useful for queries that filter on both store_id and order_date — the index delivers both lookups in one traversal.

Column order matters because the index can only be entered from the left. A query filtering only on order_date (without store_id) cannot use this composite index — it would have to scan the entire index because order_date values are interleaved across all store_id groups, not sorted globally. The database treats the composite index as a phone book sorted by last name then first name — you can look up "all Sharma entries" or "Sharma, Priya" efficiently, but you cannot look up "all Priya entries across all last names" without scanning the whole book.

Two practical rules for composite index column order: first, put equality-filter columns before range-filter columns — equality filters use one specific section of the index, while range filters use a contiguous span; combining both in the right order allows the index to navigate to the equality section and then range-scan within it. Second, put the most selective column first when both are equality filters — this reduces the number of rows the database must examine after the initial lookup. For a query with WHERE store_id = 'ST001' AND order_status = 'Delivered': if order_status has only 4 distinct values but store_id has 10 distinct values, store_id is more selective per value and should come first.

A partial index adds a WHERE clause to the index definition, indexing only rows that satisfy the condition. This makes the index smaller (fewer rows to index), faster to build and search (smaller tree), and cheaper to maintain (fewer index entries to update on writes). Use a partial index whenever queries consistently filter on a known, stable subset of rows and that subset is significantly smaller than the full table.

The classic use cases: indexing only active/live rows (WHERE is_deleted = false or WHERE status = 'Active') — if 90% of rows are deleted, a partial index on active rows is 10% the size of a full index and much faster to search. Indexing only a specific status value (WHERE order_status = 'Pending') for a queue-processing system where workers always query pending items. Indexing only non-NULL values (WHERE email IS NOT NULL) when the column is nullable and NULL rows are never queried. Indexing only recent data (WHERE created_at >= '2024-01-01') for a time-series table where queries never touch old data.

The constraint: the partial index is only used when the query's WHERE clause implies the index's WHERE condition. A query WHERE order_status = 'Pending' AND order_date = '2024-01-15' can use a partial index WHERE order_status = 'Pending' on order_date — the query's status filter implies the index's partial condition. A query WHERE order_date = '2024-01-15' without any status filter cannot use this partial index — the planner cannot be certain the partial condition is satisfied. Design partial indexes around the most common, high-frequency query patterns in the workload.

Finding slow queries: PostgreSQL's pg_stat_statements extension tracks query execution statistics across all sessions — total execution time, call count, mean time, and the query text. SELECT query, calls, mean_exec_time FROM pg_stat_statements ORDER BY mean_exec_time DESC LIMIT 20 reveals the 20 slowest queries by average execution time. The slow query log (log_min_duration_statement in postgresql.conf) logs any query exceeding a threshold. Application performance monitoring (APM) tools like Datadog or New Relic capture slow database queries from the application layer.

Diagnosing with EXPLAIN ANALYZE: prepend EXPLAIN ANALYZE to the slow query and examine the output. Look for: Seq Scan on large tables (check if rows processed >> rows returned — high filter ratio suggests a missing index), estimated rows dramatically different from actual rows (stale statistics — run ANALYZE table_name to refresh), and Sort nodes processing millions of rows (add an index on the ORDER BY column or LIMIT the result set). Also look at the total Planning Time and Execution Time at the bottom — high planning time on a simple query suggests overly complex statistics or too many indexes for the planner to evaluate.

The fix workflow: identify the Seq Scan node and its filter condition — that filter condition is the candidate for an index. Verify the index would be selective (low percentage of rows returned relative to total rows — a WHERE on status with 2 distinct values for a 50% match rate may not benefit from an index). Create the index with CONCURRENTLY to avoid locking. Run EXPLAIN ANALYZE again to confirm the plan changed from Seq Scan to Index Scan. Measure actual query time before and after. If the index is not used, check for the function-on-column anti-pattern, implicit type casting, or low selectivity causing the planner to prefer a sequential scan. Use pg_stat_user_indexes after a week to verify the new index is actually being used in production traffic.

Cause: Four possible causes: (1) The index is not being used because a function is applied to the indexed column in WHERE — WHERE LOWER(city) = 'bangalore' defeats an index on city. (2) The query returns too many rows — if >15-20% of the table matches the condition, the planner may prefer a sequential scan (reading the table sequentially is faster than many random index lookups for large result sets). (3) Statistics are stale — the planner's row count estimates are wrong, causing it to choose a bad plan. (4) The index was created after the planner's statistics snapshot — run ANALYZE on the table.

Fix: Check EXPLAIN ANALYZE carefully — look for 'Filter:' lines that show a condition being applied after the index scan (index used but extra filtering). For function-on-column: create a functional index matching the expression. For low selectivity: accept the sequential scan (it may genuinely be faster for large result sets) or use a partial index to make the subset smaller. For stale statistics: run ANALYZE table_name to refresh planner statistics. To force index use for testing: SET enable_seqscan = off — this forces the planner to use indexes even when it thinks a seq scan is faster. Never leave this setting off in production.

Cause: Attempting to create a UNIQUE index on a column that already contains duplicate values. UNIQUE indexes enforce uniqueness at creation time — if duplicates exist in the current data, the index creation fails. This is data quality feedback: the column you thought was unique is not.

Fix: Find the duplicates first: SELECT column, COUNT(*) FROM table GROUP BY column HAVING COUNT(*) > 1. Decide which duplicate rows to keep and remove the others. After deduplication, retry CREATE UNIQUE INDEX. If the column genuinely should not be unique, use CREATE INDEX (without UNIQUE). For future data quality, add a UNIQUE constraint to the column to enforce uniqueness at the application layer and prevent duplicates from being inserted.

Cause: CREATE INDEX without CONCURRENTLY takes an exclusive lock on the table for the entire duration of index creation. On a large table (millions of rows), this can take minutes. During this time, all reads and writes to the table are blocked and queue up. On a production database with live traffic, this is an outage.

Fix: Always use CREATE INDEX CONCURRENTLY for production tables: CREATE INDEX CONCURRENTLY idx_name ON table(column). CONCURRENTLY builds the index in two passes — the first pass scans the table without a lock, the second pass validates and catches any changes during the first pass. Total time is longer than a direct CREATE INDEX but no exclusive lock is held. Restriction: CREATE INDEX CONCURRENTLY cannot run inside a transaction block (cannot be used inside BEGIN/COMMIT). Run it as a standalone statement. If a CONCURRENT index creation fails midway, it leaves an INVALID index — drop it with DROP INDEX CONCURRENTLY and retry.

Cause: A composite index on (col_a, col_b) cannot be entered without specifying col_a (the leading column). A query WHERE col_b = value cannot navigate the index because col_b values are sorted within each col_a group — scanning all col_a groups to find col_b matches would be slower than a sequential table scan. The index is unusable for queries that skip the leading column.

Fix: Create a separate index on col_b alone: CREATE INDEX idx_table_col_b ON table(col_b). Now queries filtering only on col_b use this single-column index. Keep the composite index on (col_a, col_b) for queries that filter on both. The result: two indexes, each optimal for its query pattern. Review query patterns before creating composite indexes — the leading column should be the one most frequently filtered on in isolation. If queries always filter on both columns together, the composite index is sufficient and no separate index is needed.

Cause: An index marked INVALID was created with CONCURRENTLY but the creation failed partway through (due to a constraint violation, a crash, or cancellation). The invalid index entry remains in the schema but is not usable by the query planner — it is ignored. The table effectively has no index for that column.

Fix: Drop the invalid index: DROP INDEX CONCURRENTLY idx_name (check first: SELECT indexname, indisvalid FROM pg_indexes JOIN pg_index ON indexrelid = pg_class.oid WHERE indisvalid = false). After dropping, retry the CREATE INDEX CONCURRENTLY. If the failure was due to a unique constraint violation, resolve the duplicate data first. If the failure was due to a timeout or cancellation, simply retry — CONCURRENTLY can be interrupted safely, but the partial index must be dropped before retrying.

Design an indexing strategy for FreshCart's most critical queries. Write the CREATE INDEX statements (with appropriate types — partial, composite, functional, covering) for each scenario, and explain your choice. Scenarios: (1) The orders table is queried thousands of times per day with WHERE order_status = 'Delivered' AND order_date >= some_date — this is the most common query pattern. (2) Customer login authenticates by looking up LOWER(email) — case-insensitive email search happens on every login. (3) The analytics team runs store performance reports that GROUP BY store_id and aggregate total_amount — they always filter WHERE order_status = 'Delivered'. (4) Product search uses WHERE product_name ILIKE 'amul%' (prefix match, case-insensitive). (5) The order_items table is joined to orders via order_id on every order detail query. Then write a diagnostic query that shows all indexes on the orders and order_items tables.