Index Selection - Learning Module

Loading content...

0/252

Index Maintenance Cost

The Hidden Tax of Indexing

Every index you create imposes a tax on your database system—a tax that is paid not just in storage space, but in CPU cycles, I/O operations, memory pressure, and lock contention. Understanding these costs is essential because they are often invisible until they accumulate to a crisis point.

The Four Categories of Index Cost:

Index maintenance costs fall into four distinct categories, each with different characteristics and implications:

Per-Operation Costs — The immediate overhead added to each INSERT, UPDATE, or DELETE
Storage Costs — The disk space consumed by index data structures
Memory Costs — The buffer pool space required for efficient index access
Periodic Maintenance Costs — The background operations needed to keep indexes healthy

In this page, we will dissect each category with the rigor required to make informed indexing decisions.

What You Will Learn

By the end of this page, you will understand exactly what happens when you modify data in an indexed table, how to calculate storage and memory requirements, the impact of index fragmentation, and the maintenance operations required to keep indexes performing optimally.

Per-Operation Write Costs

Every write operation must maintain every index on the affected table. This fundamental fact has profound implications for system design.

The Anatomy of an INSERT with Indexes:

When you execute INSERT INTO orders VALUES (...) on a table with 6 indexes, here is the complete sequence of operations:

INSERT Operation Breakdown

•Write row to table/heap — Insert the actual data row into the base table or clustered index
•Write transaction log entry (table) — Record the table modification for recovery
•Locate insertion point in Index 1 — Traverse B+-tree to find correct leaf page
•Acquire page lock on Index 1 leaf — Obtain exclusive lock for modification
•Insert key into Index 1 leaf — Add the key-pointer pair to the leaf page
•Possibly split page in Index 1 — If leaf is full, allocate new page and redistribute keys
•Possibly update Index 1 parent nodes — If split occurred, propagate changes upward
•Write transaction log entry (Index 1) — Record the index modification
•Repeat steps 3-8 for Indexes 2-6 — Full sequence for each additional index
•Write all dirty pages to disk — Flush modifications (batched by checkpoint)

Quantifying the Cost:

The time complexity of a single INSERT scales linearly with the number of indexes:

$$T_{INSERT} = T_{base} + \sum_{i=1}^{n} T_{index_i}$$

Where:

$T_{base}$ = Time to insert row into base table
$T_{index_i}$ = Time to update index $i$
$n$ = Number of indexes

Each $T_{index_i}$ includes:

B+-tree traversal: O(log n) comparisons and page accesses
Page lock acquisition: Variable, depends on contention
Page modification: O(1) if no split, O(log n) if cascading splits
Log writing: O(1) per log entry

Empirical Write Overhead by Index Count (Representative Benchmarks)
Indexes	INSERT Latency	UPDATE Latency	DELETE Latency	Bulk INSERT (10K rows/sec)
0 (heap only)	0.08 ms	0.10 ms	0.09 ms	125,000 rows/sec
2	0.15 ms	0.22 ms	0.18 ms	67,000 rows/sec
5	0.31 ms	0.45 ms	0.38 ms	32,000 rows/sec
10	0.58 ms	0.92 ms	0.71 ms	17,000 rows/sec
15	0.89 ms	1.48 ms	1.12 ms	11,200 rows/sec
20	1.24 ms	2.15 ms	1.58 ms	8,000 rows/sec

UPDATE Operations Are Particularly Expensive

Notice that UPDATE latency increases faster than INSERT or DELETE. This is because updating an indexed column requires both removing the old key and inserting the new key—effectively two index operations per affected index. An UPDATE that modifies all indexed columns on a 15-index table performs 30 index key operations.

UPDATE and DELETE: The Complete Picture

While INSERT is straightforward (add keys to all indexes), UPDATE and DELETE have additional complexity that affects their cost profile.

UPDATE Operation Analysis:

UPDATE only modifies indexes for columns that are actually changed:

-- Only updates indexes containing 'status' or 'updated_at'
UPDATE orders SET status = 'shipped', updated_at = NOW() WHERE id = 12345;

-- Updates ALL indexes containing any of these columns
UPDATE orders
SET customer_id = 999, status = 'cancelled', total = 0, notes = 'Refunded'
WHERE id = 12345;

This creates an important optimization opportunity: design UPDATEs to modify as few indexed columns as possible.

UPDATE Operation Steps

•Read phase — Locate row and current values
•For each affected index:
•→ Find old key in B+-tree
•→ Remove old key from leaf page
•→ Handle potential underflow/merge
•→ Find insertion point for new key
•→ Insert new key
•→ Handle potential overflow/split
•Apply row modifications — Update heap/clustered index
•Write log entries — For all changes

DELETE Operation Steps

•Read phase — Locate row to delete
•For each index on table:
•→ Find key in B+-tree
•→ Remove key from leaf page
•→ Handle potential underflow
•→ Possibly merge with sibling page
•→ Update parent if merge occurred
•Remove row — Delete from heap/clustered index
•Write log entries — For all changes

The Deferred Delete Optimization:

Many modern databases use ghost records or delete markers instead of immediately removing index entries:

DELETE marks the record as 'deleted' but doesn't physically remove it
Index entries remain in place but are marked invalid
Background processes later perform physical cleanup

This optimizes DELETE latency but creates storage bloat and cleanup overhead. The trade-off is worthwhile for most workloads because:

User-facing DELETE operations complete faster
Cleanup can be batched and scheduled during low-activity periods
MVCC (Multi-Version Concurrency Control) benefits from retaining old versions temporarily

Soft Deletes Exacerbate Index Costs

If your application uses soft deletes (SET is_deleted = 1 instead of DELETE), remember that these are UPDATEs, not DELETEs. The row remains in all indexes forever. Consider partial indexes that exclude deleted records, or periodic archival to separate tables.

Storage Costs: More Than Just Disk Space

Index storage costs are often underestimated. A naive assumption is that an index on a small column uses minimal space. In reality, index storage can exceed the base table size.

Anatomy of Index Storage:

Each index consists of:

Leaf pages — Containing keys and pointers (row locators)
Internal (branch) pages — Containing separator keys and child pointers
Root page — Entry point for traversal
Overflow pages — For handling long keys or page splits
Free space — Reserved for future insertions (fill factor)

Index Size Estimation Formula
Component	Calculation	Notes
Key Size	Sum of indexed column sizes + overhead	VARCHAR uses actual length + 2 bytes. NULLs may add bitmap overhead.
Row Locator	4-8 bytes (heap RID) or clustered key size	Non-clustered indexes in clustered tables store the clustering key.
Entry Size	Key Size + Row Locator + per-entry overhead	Overhead: 4-8 bytes for slot directory, status bits.
Entries per Page	(Page Size × Fill Factor) / Entry Size	Typical page: 8KB. Fill factor: 80-90%.
Leaf Pages	Row Count / Entries per Page	The dominant storage component.
Non-leaf Pages	Leaf Pages / (Page Size / (Key + Pointer))	Much smaller; typically adds 1-5% to total.
Total Size	Leaf Pages × Page Size × (1 + Overhead%)	Add 10-20% for fragmentation and free space.

Index Size Calculation Example
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
-- Table: orders (50 million rows)
-- Columns: order_id BIGINT (8 bytes), customer_id INT (4 bytes),
--          order_date DATE (4 bytes), status VARCHAR(20) (avg 10 bytes)
 
-- Index: (customer_id, order_date)
-- Key size: 4 + 4 = 8 bytes
-- Row locator (assuming clustered on order_id): 8 bytes
-- Entry size: 8 + 8 + 6 (overhead) = 22 bytes
 
-- With 8KB pages and 85% fill factor:
-- Usable space per page: 8192 × 0.85 = 6,963 bytes
-- Entries per page: 6,963 / 22 ≈ 316 entries
 
-- Leaf pages needed: 50,000,000 / 316 ≈ 158,228 pages
-- Leaf storage: 158,228 × 8 KB ≈ 1.24 GB
 
-- Non-leaf pages: 158,228 / 400 ≈ 396 + 1 root ≈ 400 pages
-- Non-leaf storage: 400 × 8 KB ≈ 3 MB
 
-- Total index size: ~1.25 GB
 
-- Verification in PostgreSQL:
SELECT pg_size_pretty(pg_relation_size('idx_orders_customer_date'));
-- Result: 1.29 GB (close to estimate, extra from fragmentation)

Storage Cost Multipliers:

Several factors can significantly increase actual storage beyond theoretical calculations:

Storage Multipliers

•Fill Factor — Leaving 20% free space for inserts increases storage by 25% (1/0.8 = 1.25)
•Fragmentation — Random inserts cause page splits, creating half-empty pages. Can add 50%+ overhead.
•Row Versioning — MVCC systems may store multiple versions in indexes. Active transactions can bloat indexes.
•Ghost Records — Deleted entries awaiting cleanup consume space until vacuumed.
•Alignment Padding — Columns may be padded to word boundaries, increasing effective size.
•Compression Trade-offs — Compressed indexes use less disk but may expand in memory.

Case Study: Index Larger Than Table

A production system had a 10 GB table with 12 indexes totaling 45 GB. The indexes consumed 4.5× the base table storage. Each index addition seemed small, but the cumulative effect was dramatic. Storage costs, backup times, and restore durations all increased proportionally.

Memory Pressure and Buffer Pool Competition

For indexes to deliver their promised performance benefits, they must be cached in the buffer pool. This creates competition with other data structures for limited memory resources.

The Buffer Pool Reality:

Modern database systems cache frequently accessed pages in a buffer pool (also called buffer cache or shared buffers). When an index page is needed:

If in buffer pool: Memory access (~100 nanoseconds)
If on SSD: SSD read (~100 microseconds) — 1,000× slower
If on HDD: Disk read (~10 milliseconds) — 100,000× slower

An index that doesn't fit in the buffer pool loses most of its performance advantage.

Index Cacheability Analysis
Index Size	Buffer Pool Fit	Effective Performance
< 10% of buffer pool	Fully cached, high locality	Excellent: 3-4 I/Os for any lookup, usually from cache
10-50% of buffer pool	Partially cached, root/upper levels reliable	Good: Upper levels cached, leaf pages may require I/O
50-100% of buffer pool	Competitive caching, frequent eviction	Degraded: High cache miss rate during peak load
100% of buffer pool	Cannot fully cache, trashes other data	Poor: Index competes with table for cache, net negative
buffer pool	Minimal caching possible	Very Poor: Almost every access requires I/O

Working Set Analysis:

Not all pages in an index are accessed equally. The working set is the subset of pages accessed during normal operation:

Hot pages: Root and upper-level internal nodes (accessed constantly)
Warm pages: Frequently-accessed leaf segments (recent data, popular keys)
Cold pages: Rarely-accessed leaves (old data, uncommon keys)

A well-designed index has a small working set relative to total size. An index on a monotonically increasing key (like auto-increment ID or timestamp) has excellent locality—new inserts always go to the same few pages, keeping the working set small.

Conversely, an index on randomly distributed keys (like UUIDs) has poor locality—inserts scatter across the entire index, requiring the whole index to be cached for good performance.

Good Locality Patterns

•Sequential IDs (auto-increment)
•Timestamp columns (recent data hot)
•Date-based partitioning
•Range queries on sorted data
•Customer ID with uneven access (80/20 rule)

Poor Locality Patterns

•Random UUIDs as primary key
•Hash-based distribution
•Evenly distributed lookups
•Full index scans
•Index on low-cardinality column

The Cascading Effect

Memory pressure from over-indexing doesn't just hurt index performance—it evicts table data pages from the buffer pool, degrading ALL queries including those that don't use indexes. The system becomes I/O bound on operations that should be memory-speed.

Lock Contention and Concurrency Overhead

Index maintenance requires locks, and locks create contention. In high-concurrency systems, this contention can become the limiting factor on throughput.

Index Page Locking:

When modifying an index, the database must acquire locks to prevent concurrent operations from creating inconsistencies:

Shared locks (S): For read operations on index pages
Exclusive locks (X): For write operations (insert, delete, modify)
Update locks (U): Intermediate state to prevent deadlocks

Most databases use fine-grained locking at the page or key level, but contention still occurs when multiple transactions target the same page.

Hot Spots in Indexes:

Certain index patterns create severe lock contention:

1. Sequential Key Insertion (The Right Edge Problem)

When inserting into an index on an auto-increment or timestamp column:

All inserts target the rightmost leaf page
All concurrent inserters compete for the same page lock
Throughput is limited by single-page write speed

2. Popular Key Updates

If many transactions update the same indexed value:

All updates request exclusive lock on the same leaf page
Transactions queue behind each other
Response time degrades linearly with concurrency

3. Index Splits During High Load

When a page split occurs:

Parent pages must also be modified
Lock escalation may occur
Concurrent operations on the same subtree are blocked

Detecting Lock Contention
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
-- Identify lock contention on indexes
SELECT
    relname AS index_name,
    pg_stat_user_indexes.idx_scan AS index_scans,
    pg_stat_user_indexes.idx_tup_read AS tuples_read,
    pg_statio_user_indexes.idx_blks_read AS blocks_read,
    pg_statio_user_indexes.idx_blks_hit AS blocks_hit,
    ROUND(
        pg_statio_user_indexes.idx_blks_hit * 100.0 /
        NULLIF(pg_statio_user_indexes.idx_blks_read + pg_statio_user_indexes.idx_blks_hit, 0),
        2
    ) AS cache_hit_ratio
FROM pg_stat_user_indexes
JOIN pg_statio_user_indexes USING (schemaname, relname, indexrelname)
WHERE schemaname = 'public'
ORDER BY idx_scan DESC;
 
-- Check for lock waits (real-time)
SELECT
    blocked_locks.relation::regclass AS blocked_table,
    blocked_activity.query AS blocked_query,
    blocking_locks.relation::regclass AS blocking_table,
    blocking_activity.query AS blocking_query,
    blocked_activity.wait_event_type,
    blocked_activity.wait_event
FROM pg_catalog.pg_locks blocked_locks
JOIN pg_catalog.pg_stat_activity blocked_activity
    ON blocked_activity.pid = blocked_locks.pid
JOIN pg_catalog.pg_locks blocking_locks
    ON blocking_locks.locktype = blocked_locks.locktype
    AND blocking_locks.database IS NOT DISTINCT FROM blocked_locks.database
    AND blocking_locks.relation IS NOT DISTINCT FROM blocked_locks.relation
    AND blocking_locks.page IS NOT DISTINCT FROM blocked_locks.page
    AND blocking_locks.tuple IS NOT DISTINCT FROM blocked_locks.tuple
    AND blocking_locks.transactionid IS NOT DISTINCT FROM blocked_locks.transactionid
    AND blocking_locks.pid != blocked_locks.pid
JOIN pg_catalog.pg_stat_activity blocking_activity
    ON blocking_activity.pid = blocking_locks.pid
WHERE NOT blocked_locks.granted;

Mitigating Lock Contention

To reduce index lock contention: (1) Use higher fill factors to delay page splits, (2) Consider GUID/UUID alternatives that distribute inserts across pages, (3) Partition indexes on hot columns, (4) Use database-specific features like SQL Server's OPTIMIZE_FOR_SEQUENTIAL_KEY option.

Index Fragmentation: The Silent Performance Killer

Fragmentation is the gradual degradation of index structure over time due to insert, update, and delete operations. There are two types of fragmentation, each with different symptoms and remedies.

Internal fragmentation occurs when pages are not fully utilized—they contain free space that could hold more entries.

Causes:

Page splits: When a page overflows, it splits into two half-full pages
Deletions: Removed entries leave gaps that may not be reused
Variable-length keys: Entries vary in size, making perfect packing impossible

Impact:

Storage waste: Paying for disk space that holds nothing
Memory waste: Cached pages are half-empty
Increased I/O: Range scans read more pages than necessary

Measurement:

Internal fragmentation is typically expressed as average page fullness:

90%+ fullness: Healthy
75-90%: Acceptable for active indexes
50-75%: Degraded, consider rebuilding
<50%: Severely fragmented, rebuild urgently

Check Internal Fragmentation (PostgreSQL)
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
-- Install pgstattuple extension
CREATE EXTENSION IF NOT EXISTS pgstattuple;
 
-- Analyze index fragmentation
SELECT
    schemaname || '.' || indexname AS index,
    pg_size_pretty(pg_relation_size(indexname::regclass)) AS size,
    avg_leaf_density AS page_fullness_pct,
    leaf_fragmentation AS fragmentation_pct
FROM pgstattuple_all('idx_orders_customer_id');
 
-- For all indexes on a table
SELECT
    indexrelname,
    pg_size_pretty(pg_relation_size(indexrelid)) AS size,
    idx.avg_leaf_density,
    idx.leaf_fragmentation
FROM pg_stat_user_indexes psu
CROSS JOIN LATERAL pgstattuple(indexrelid) idx
WHERE relname = 'orders';

Periodic Maintenance Operations

Beyond per-operation costs, indexes require periodic maintenance to remain healthy. These maintenance operations consume resources and must be scheduled carefully to avoid impacting production workloads.

Essential Index Maintenance Tasks

•Statistics Updates — Query optimizer relies on accurate statistics about key distribution. Stale statistics lead to poor plan choices. Update frequency depends on data change rate—daily for volatile tables, weekly for stable ones.
•Index Reorganization — Defragments pages without rebuilding. Lower impact than rebuild but less effective for severe fragmentation. Can run online in most databases. Suitable for 5-30% fragmentation.
•Index Rebuild — Completely reconstructs the index from scratch. Eliminates all fragmentation and resets structure. Higher resource usage but most effective. Required for >30% fragmentation.
•Vacuum/Cleanup — Reclaims space from dead tuples (PostgreSQL VACUUM, SQL Server Ghost Cleanup). Essential for tables with high delete/update activity. Delay causes bloat and performance degradation.
•Integrity Verification — Periodic consistency checks (DBCC CHECKDB, pg_amcheck). Detects corruption before it causes data loss. CPU and I/O intensive; schedule during low-activity windows.

Maintenance Impact and Scheduling
Operation	Resource Usage	Blocking?	Recommended Frequency	Best Scheduled
Statistics Update	Low-Medium	No	Daily / On threshold	Any time
Reorganize	Medium	Minimal	Weekly / As-needed	Low-activity period
Rebuild (Online)	High	Minimal	Monthly / As-needed	Maintenance window
Rebuild (Offline)	Very High	Yes	When necessary	Extended downtime
Vacuum/Cleanup	Medium	Minimal	Continuous / Daily	Any time (auto-vacuum)
Integrity Check	Very High	Read-only	Weekly / Monthly	Weekends / Off-hours

Automated Maintenance Scripts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
-- Reindex with minimal locking (PostgreSQL 12+)
REINDEX TABLE CONCURRENTLY orders;
 
-- Update statistics
ANALYZE orders;
 
-- Check and vacuum
VACUUM (VERBOSE, ANALYZE) orders;
 
-- Automated maintenance query
SELECT
    schemaname,
    tablename,
    n_live_tup,
    n_dead_tup,
    ROUND(n_dead_tup * 100.0 / NULLIF(n_live_tup + n_dead_tup, 0), 2) AS dead_ratio,
    last_vacuum,
    last_autovacuum,
    last_analyze
FROM pg_stat_user_tables
WHERE n_dead_tup > 1000
ORDER BY n_dead_tup DESC;

Maintenance Debt Compounds

Skipping or delaying maintenance doesn't eliminate the work—it defers and compounds it. A week of missed vacuums might take minutes to catch up. A month might take hours. A year might require extended downtime. Build maintenance into your operational rhythm from day one.

Summary: The True Cost of Indexes

We have dissected the comprehensive costs of index maintenance. This knowledge enables informed decision-making about when the read benefits of an index justify its maintenance costs.

Key Takeaways

•Per-operation costs scale linearly with index count — Each index adds measurable latency to every write operation.
•UPDATE operations are especially expensive — Modifying indexed columns requires both key removal and insertion.
•Storage costs often exceed expectations — Overhead from structure, fragmentation, and fill factor can double theoretical size.
•Memory pressure affects entire system — Oversized indexes evict valuable data from buffer pool, degrading all queries.
•Lock contention limits concurrency — Hot spots in indexes become throughput bottlenecks under load.
•Fragmentation degrades over time — Without maintenance, index performance silently deteriorates.
•Maintenance requires resources and scheduling — Plan for ongoing operational overhead, not just creation cost.

Page Complete

You now understand the complete picture of index maintenance costs. This knowledge is essential for making ROI-based indexing decisions. Next, we'll examine how to analyze query patterns to identify which queries actually need—and would benefit from—index support.