SQL Indexes — Avoid 90-Minute Foreign Key Lock

Indexes are the single most impactful optimization available in relational databases. A query that takes 30 seconds on a table with 10 million rows can return in 2 milliseconds after adding the right index. The difference is the gap between scanning every row on disk and jumping directly to the matching ones via a balanced tree structure.

However, indexes aren't free. The cost is write overhead and disk space. Every index you add slows down INSERT, UPDATE, and DELETE operations because the database must maintain the sorted order of the index in real-time. The 'Forge' philosophy is about precision: adding the exact indexes your critical queries need without bloating the table with redundant metadata.

Why SQL Indexes Are Not Optional

An SQL index is a separate data structure — typically a B-tree — that maps column values to row locations, enabling the database to find rows without scanning the entire table. Without an index, every query performs a sequential scan (O(n)), which becomes catastrophic beyond a few thousand rows. With a B-tree index, point lookups drop to O(log n), and range scans become efficient by traversing leaf nodes in order.

Indexes work by maintaining a sorted copy of the indexed column(s) along with pointers to the heap or clustered index. This imposes write overhead: each INSERT, UPDATE, or DELETE must update every relevant index, so adding indexes blindly can degrade write throughput by 2–5x. The database query planner chooses an index only when it estimates the index will reduce cost — typically when the query filters or sorts on leading columns of the index. Composite indexes follow a leftmost prefix rule: a query on (a, b, c) can use an index on (a, b, c) or (a, b) but not on (b, c) alone.

Use indexes on columns that appear in WHERE, JOIN, ORDER BY, or GROUP BY clauses, especially when those columns have high cardinality (many distinct values). In production systems, a missing index is the most common cause of sudden query degradation — a single unindexed foreign key can turn a 10ms JOIN into a 90-minute lock storm under load. Indexes are not free, but the cost of not having them is far higher.

How a B-Tree Index Works

Most relational databases (PostgreSQL, MySQL, SQL Server) use a B-tree (Balanced Tree) structure for indexing. A B-tree keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time.

When you query a column, the database starts at the root node and follows pointers down to the leaf nodes. Each leaf node contains the indexed value plus a 'Record Identifier' (RID) or a Primary Key value that points to the actual row data in the 'Heap' or Clustered Index.

-- io.thecodeforge.optimization
-- Scenario: Searching for a customer without an index
SELECT * FROM io_thecodeforge.orders WHERE customer_id = 1234;
-- Result: The database performs a 'Sequential Scan' (reads 100% of the table).

-- Optimization: Create a standard B-tree index
CREATE INDEX idx_orders_customer 
ON io_thecodeforge.orders(customer_id);

-- Now the query engine performs an 'Index Scan'
EXPLAIN ANALYZE 
SELECT * FROM io_thecodeforge.orders WHERE customer_id = 1234;

B-Tree Index Structure: Root, Branch, and Leaf Nodes

A B-tree index is a multi-level tree consisting of three types of pages (nodes): root, internal (branch), and leaf. The root node is the single entry point – it contains a small set of keys that divide the data into ranges. When you search for a value, the engine reads the root, follows a pointer to the appropriate branch node, which further narrows the range, and finally reaches the leaf node containing the actual index entry. The number of levels (the height of the tree) depends on the number of entries and the page size. For a B-tree of order k (each node can hold up to k keys), the height grows as log base k of (number of rows), so even with millions of rows the tree is rarely more than 3–5 levels deep.

Leaf nodes are the most important: they store the indexed column value along with a pointer to the actual row (either a page identifier and offset, or the clustered index key). In a non-clustered index, leaf nodes store only the indexed columns and the row locator. In a clustered index, leaf nodes contain all table columns (the data itself). Branch nodes contain routing information only – keys and pointers to lower-level nodes.

A B-tree remains balanced by design – all leaf nodes are at the same depth. When a node overflows, it splits into two nodes, and a new key is promoted upward. This automatic rebalancing ensures consistent O(log n) performance, but the split operations also contribute to write overhead and potential bloat over time.

Visualising the hierarchy makes debugging easier. When EXPLAIN ANALYZE reports 'Index Scan using idx_orders_customer_id' but with a high number of 'Heap Fetches', the issue often lies in leaf node page density (fragmentation) rather than the tree height.

Composite Indexes and the Leftmost Prefix Rule

A composite index (multi-column index) is sorted primarily by the first column, then the second, and so on. This leads to the Leftmost Prefix Rule: an index on $(A, B)$ can be used for queries filtering by $(A)$ or $(A, B)$, but it is completely useless for a query filtering only by $(B)$.

Choosing the right column order is vital. Generally, you put the column with the highest cardinality (most unique values) first, or the column most frequently used in WHERE clauses.

-- io.thecodeforge.optimization
-- Composite index on (last_name, first_name)
CREATE INDEX idx_user_full_name 
ON io_thecodeforge.users(last_name, first_name);

-- VALID: Uses index (leftmost prefix)
SELECT * FROM io_thecodeforge.users WHERE last_name = 'Jordan';

-- VALID: Uses index (exact match)
SELECT * FROM io_thecodeforge.users WHERE last_name = 'Jordan' AND first_name = 'Michael';

-- INVALID: Full Table Scan (skips the first column of the index)
SELECT * FROM io_thecodeforge.users WHERE first_name = 'Michael';

-- PRO TIP: Covering Index
-- This index contains ALL data needed, avoiding a 'Table Lookup' entirely
CREATE INDEX idx_covering_search 
ON io_thecodeforge.users(email) INCLUDE (user_id, status);

Specialized Indexes: GIN and GiST for JSON and Text Search

While B-tree indexes excel at equality and range queries on simple scalar columns, they cannot efficiently handle complex data types like JSONB, arrays, tsvectors, or geometric shapes. For such cases, PostgreSQL provides two generalized index methods: GIN (Generalized Inverted Index) and GiST (Generalized Search Tree).

GIN indexes are designed for composite types: JSONB, arrays, range types, and full-text search (tsvector). A GIN index stores a mapping from each possible key (e.g., each JSONB key/value pair, each array element, each lexeme in a tsvector) to a list of row locations. Queries using the @>, ?, ?|, ?& operators on JSONB become fast index scans instead of table-wide scans. GIN indexes are relatively expensive to build and maintain (each insert may touch many index entries), and they consume more storage than a B-tree on the same column. However, for read-heavy workloads that query JSONB with containment or existence operators, GIN is the only viable option.

GiST indexes are more versatile: they support range, point, polygon, and full-text search (though GIN is usually faster for text). GiST is also used for nearest-neighbor ordering and overlapping containment queries. When you need to find all rows that contain a point within a polygon or rows with a tsvector that matches a tsquery, a GiST index can accelerate those operations.

Picking the right one: For JSONB, prefer GIN with jsonb_path_ops operator class for smaller index and faster lookups on @> queries. For full-text search, GIN on a tsvector column is the standard. For geometric or range types, GiST is the natural choice. Both index types support concurrent creation just like B-trees.

-- io.thecodeforge.optimization
-- GIN index on JSONB
CREATE INDEX idx_documents_data_gin
ON documents USING GIN (data jsonb_path_ops);

-- Query that now uses the GIN index
SELECT id

When Indexes Hurt: Write Amplification and Bloat

Every time you INSERT a row into a table with 5 indexes, the database must perform 6 writes (1 to the table, 5 to the indexes). This is known as Write Amplification. Furthermore, indexes can become 'fragmented' over time as rows are deleted and updated, leading to bloated files and degraded performance.

-- io.thecodeforge.maintenance
-- 1. Identifying unused indexes (PostgreSQL example)
SELECT relname, indexrelname, idx_scan
FROM pg_stat_user_indexes
WHERE idx_scan = 0 AND idx_read = 0;
-- Action: Drop these to reclaim write performance.

-- 2. Avoiding 'Functional' index traps
-- This ignores a standard index on 'created_at'
SELECT * FROM io_thecodeforge.orders WHERE DATE(created_at) = '2024-01-01';

-- Correct approach: Use a range or a functional index
CREATE INDEX idx_functional_date ON io_thecodeforge.orders ((DATE(created_at)));

Index Maintenance: Fill Factor, Bloat, and Reindexing

Even well-chosen indexes degrade over time. Three key maintenance parameters and operations keep indexes healthy: fill factor, periodic reindexing, and bloat monitoring.

Fill Factor controls how much free space is left on each B-tree page when the index is built or rebuilt. The default in PostgreSQL is 90% for B-trees (10% free space). This space is reserved for future updates to existing rows that might cause the indexed value to change, or for inserts that fall into the same page range. Without that free space, every insert or update that targets a full page forces a page split — dividing the page into two half-full pages and promoting a key upward. Page splits increase index height slowly and cause fragmentation. Setting a fill factor of 70% for a table with frequent updates to indexed columns reduces splits but increases index size and storage cost.

Bloat occurs when page splits, dead tuples (after UPDATE/DELETE), and incomplete vacuum leave the index containing many empty or nearly empty pages. A bloated index is larger than necessary, uses more memory in shared buffers, and increases I/O for scans. You can measure bloat with the pgstattuple extension or by comparing the index size to the number of indexed values.

Reindexing rebuilds the entire index from scratch, creating a fresh copy with the correct fill factor and no bloat. In PostgreSQL, REINDEX INDEX or REINDEX TABLE locks the table. For production, use REINDEX INDEX CONCURRENTLY (available since PostgreSQL 12) to rebuild without blocking writes. Alternatively, use pg_repack or pg_squeeze for online reorganization. The frequency of reindexing depends on write volume — a table that sees 50% of its indexed columns updated monthly may benefit from quarterly reindexing.

A visual guide to fill factor and page splits: the diagram below shows two pages before and after an insert triggers a split with different fill factors.

Creating an Index: Three Patterns That Won't Bite You Later

You don't just CREATE INDEX and walk away. The wrong index is worse than no index — it burns CPU on writes and fools your optimizer into bad plans. Three patterns cover 90% of real cases. Single-column indexes for high-cardinality filters like customer IDs or timestamps. Multi-column (composite) indexes when you filter on multiple columns together — but respect the leftmost prefix rule or the index is dead weight. Unique indexes for enforcement, not performance. They prevent duplicates but add a uniqueness check on every write. Never index a boolean column with 50% true/50% false — the database will ignore it anyway. Always check selectivity before creating. If a column has fewer than 100 distinct values across a million rows, a full scan is cheaper.

-- io.thecodeforge
-- Product search is our most frequent query pattern
CREATE INDEX idx_orders_shipped_at ON orders (shipped_at);
-- Composite for multi-column filter: department + created date
CREATE INDEX idx_products_dept_created 
  ON products (department_id, created_at);
-- Enforce business rule: no duplicate invoice numbers
CREATE UNIQUE INDEX idx_invoices_number 
  ON invoices (invoice_number);
-- Show what PostgreSQL actually built
SELECT indexname, indexdef 
  FROM pg_indexes 
  WHERE tablename = 'products';

Confirming, Removing, and Altering Indexes Without Downtime

You need eyes on your indexes before you drop anything. Use SHOW INDEXES or system catalog views to see size, scan count, and last usage. In PostgreSQL, pg_stat_user_indexes tells you which indexes have zero scans — that's your drop list. Removing an index frees disk and speeds writes. But dropping the wrong one crateres query performance. Always check if any foreign key or unique constraint depends on it. Altering an index — renaming, rebuilding, or changing fill factor — often requires an exclusive lock. On large tables, do it in a maintenance window or use CONCURRENTLY variants. Renaming indexes follows a naming convention: idx_tablename_columnname. It saves hours of confusion during incident response. Never name an index 'idx_final_v3' — you will forget what it does by next quarter.

-- io.thecodeforge
-- Find unused indexes on our largest table
SELECT schemaname, tablename, indexname, idx_scan
  FROM pg_stat_user_indexes
  WHERE tablename = 'orders'
    AND idx_scan = 0;

-- Safe rename for clarity (PostgreSQL workaround)
ALTER INDEX idx_old_name RENAME TO idx_orders_shipped_at;

-- Drop unused index, no cascade needed
DROP INDEX IF EXISTS idx_orders_old_cache;

-- Rebuild with fill factor for write-heavy table
ALTER INDEX idx_orders_shipped_at 
  SET (fillfactor = 90);
REINDEX INDEX CONCURRENTLY idx_orders_shipped_at;

Partial, Expression, and Conditional Indexes

Partial indexes allow you to index only a subset of rows, reducing index size and maintenance overhead. They are defined with a WHERE clause. For example, to index only active orders: CREATE INDEX idx_active_orders ON orders (status) WHERE status = 'active';. Expression indexes index the result of a function or expression, enabling efficient queries on computed values. Example: CREATE INDEX idx_lower_email ON users (LOWER(email));. Conditional indexes are similar to partial indexes but often used for unique constraints on a subset. In PostgreSQL, you can combine both: CREATE UNIQUE INDEX idx_unique_active_user ON users (email) WHERE active = true;. These indexes are powerful for targeted performance gains without bloating the entire table index.

-- Partial index: only index active orders
CREATE INDEX idx_active_orders ON orders (status) WHERE status = 'active';

-- Expression index: index lowercased email
CREATE INDEX idx_lower_email ON users (LOWER(email));

-- Conditional unique index: enforce unique email only for active users
CREATE UNIQUE INDEX idx_unique_active_user ON users (email) WHERE active = true;

-- Query that benefits from expression index
SELECT * FROM users WHERE LOWER(email) = 'user@example.com';

BRIN, GiST, GIN, SP-GiST Index Types in PostgreSQL

PostgreSQL offers specialized index types beyond B-tree. BRIN (Block Range INdex) is excellent for large tables with naturally ordered data (e.g., timestamps). It stores min/max values per block range, making it very small. Example: CREATE INDEX idx_brin_created ON orders USING brin (created_at);. GiST (Generalized Search Tree) supports geometric and full-text search. For example, indexing a point column: CREATE INDEX idx_gist_location ON locations USING gist (coords);. GIN (Generalized Inverted Index) is for composite types like arrays, JSONB, and full-text search. Example: CREATE INDEX idx_gin_tags ON articles USING gin (tags);. SP-GiST (Space-Partitioned GiST) is for clustered data like quad-trees. Choose based on data type and query patterns: BRIN for sequential data, GiST for spatial, GIN for array/JSON, SP-GiST for partitioning.

-- BRIN index on timestamp column (large table)
CREATE INDEX idx_brin_created ON orders USING brin (created_at) WITH (pages_per_range = 32);

-- GiST index on geometric point
CREATE INDEX idx_gist_location ON locations USING gist (coords);

-- GIN index on array column
CREATE INDEX idx_gin_tags ON articles USING gin (tags);

-- GIN index on JSONB
CREATE INDEX idx_gin_data ON events USING gin (data jsonb_path_ops);

-- SP-GiST index for k-dimensional data
CREATE INDEX idx_spgist_point ON points USING spgist (p);

Index Maintenance: Reindexing, Bloat, Fill Factor

Over time, indexes can become bloated due to updates and deletes, degrading performance. Reindexing rebuilds the index to reclaim space and improve efficiency. Use REINDEX INDEX idx_name; or REINDEX TABLE table_name;. To minimize bloat, set an appropriate fill factor (default 90 for B-tree). Fill factor reserves space for future updates, reducing page splits. Example: CREATE INDEX idx_name ON table (col) WITH (fillfactor = 70);. Monitor bloat with pg_stat_user_indexes and pgstattuple extension. For large tables, use CONCURRENTLY to avoid locks: REINDEX INDEX CONCURRENTLY idx_name;. Regular maintenance (e.g., weekly reindexing of high-churn indexes) is crucial in production.

-- Check index bloat using pgstattuple
SELECT * FROM pgstattuple('idx_name');

-- Reindex with CONCURRENTLY to avoid locks
REINDEX INDEX CONCURRENTLY idx_name;

-- Create index with custom fill factor
CREATE INDEX idx_name ON table (col) WITH (fillfactor = 70);

-- Reindex table
REINDEX TABLE table_name;

-- Monitor index usage
SELECT schemaname, tablename, indexname, idx_scan, idx_tup_read, idx_tup_fetch
FROM pg_stat_user_indexes
WHERE idx_scan = 0;