Clustered Index

Introduction

Clustered index: physically orders table rows by index key. Rows stored contiguously in index key order on disk. Only one clustered index per table (defines physical sort order). Typically primary key.

Core benefit: range queries extremely fast (sequential disk reads). Sorting free (rows already sorted). No separate lookup needed (leaf nodes contain all data). Dominant index for most queries.

Trade-off: expensive to maintain (reorganization on inserts/updates). Can only have one (physical constraint). Choice critical: wrong clustered index slows workload.

"Clustered indexes define physical table layout. Critical optimization: rows organized by key, range queries scanned sequentially. Choose carefully: wrong choice impacts all queries." -- Index design

Clustered Index Concept

Physical Sorting

Rows physically ordered by clustered key on disk. Read pages sequentially: get consecutive rows in key order. No random access needed. Example: employee table clustered by employee_id -> employees 1-100 on page 1, 101-200 on page 2.

B-Tree Structure

Clustered index: B-Tree on key. Leaf nodes: actual data pages (contain full rows). Internal nodes: guides traversal. Lowest level: all data.

Leaf Node Contents

Non-clustered index leaf: (key, row_id). Clustered index leaf: (key, full_row_data). No additional lookup needed. Read leaf node = get complete row.

Unique Ordering

Each key position unique: determines row slot. Duplicates: handled by adding uniquifier (invisible column). Ensures every row distinct position.

Index Key Definition

Clustering key: column(s) defining order. Usually primary key (immutable, unique). Can be non-key columns. Choice: impacts query performance significantly.

Physical Organization

Heap Table (No Clustered Index)

Rows stored without order. New rows: appended to end (free space chain). Searches: table scan required. No inherent sorting. Older systems sometimes use (uncommon now).

Clustered Organization

Rows stored in clustered key order. Example: customer_id clustered index -> rows sorted by customer_id. Sequential reads: customers in order (1-1000, 1001-2000, etc.).

Page Organization

Disk page: multiple rows (16KB typical). Rows packed: minimize gaps. Insert into middle: shifts rows (or splits page). Goal: maintain sort order, minimize fragmentation.

Page Splits

Insert row: find position in sorted order. Page full: split into two. Left page: smaller keys. Right page: larger keys. Parent updated. Causes fragmentation.

Fragmentation Management

Over time: inserts/deletes cause gaps. Rebuilding: reorganize pages, remove gaps. Maintenance: periodic rebuild. Cost: downtime (typically offline). Trade-off: performance vs. maintenance cost.

Primary Key and Clustering

Primary Key as Clustered Key

Default: primary key becomes clustered index. Makes sense: primary key immutable, unique, frequently queried. Natural choice. Explicit clustering possible (rare).

Immutability Benefit

Primary key immutable: no reorganization needed. Rows stay in same position. Clustered key updates: expensive (move rows). Immutability critical for performance.

Choosing Clustering Column

Criteria: (1) Immutable (rarely changes), (2) Unique or nearly unique, (3) Used in range queries, (4) Frequently sorted. Example: order_id (good) vs. status (bad, low cardinality).

Surrogate Keys

Identity/auto-increment column: often clustered. Sequential: inserts append (no reorganization). But: queries by ID rare (just lookups). Better: cluster by natural key if range queries important.

Composite Clustered Keys

Multiple columns: department_id, employee_id. Rows: grouped by department, sorted by employee within. Efficient for: WHERE department=X queries (range within department).

Index Leaf Nodes

Clustered Leaf Node Structure

Contains: clustering key + all row data (columns). No separate row lookup. Single disk read: get complete row. Very efficient.

Example Leaf Node

Clustered Index on employee_id
Leaf Node:
[emp_id=101, name='Alice', salary=50000, dept='Sales']
[emp_id=102, name='Bob', salary=55000, dept='IT']
[emp_id=103, name='Charlie', salary=60000, dept='Sales']

Query: WHERE employee_id=102
Read leaf node, find row, get complete data (one disk access)

Non-Clustered Leaf Nodes

Non-clustered leaf: (index_key, row_id). Row_id: pointer to clustered leaf. Lookup: navigate non-clustered index, get row_id, then access clustered index. Extra hop.

Leaf Node Linking

Leaf nodes linked (sibling pointers): sequential traversal. Clustered index leaves: contain data, linked. Enabling range scans: sequential read of pages.

Data Storage Cost

Clustered leaf: entire row stored. Non-clustered: only index columns + row_id. Clustered: larger pages (fewer rows per page). Trade-off: size vs. access speed.

Range Queries and Sorting

Range Query Optimization

WHERE employee_id BETWEEN 100 AND 200. Clustered: find leaf with key=100, scan sequentially to key=200. Sequential disk reads: very fast. No sorting needed.

Sequential Access Pattern

Clustered index: naturally sequential. Disk controller: prefetch next pages. Cache hits: likely (consecutive reads). Throughput: limited by disk bandwidth.

ORDER BY Efficiency

If clustered key matches ORDER BY: no sorting needed. Example: SELECT * FROM employees ORDER BY employee_id. Already sorted! Cost: just sequential scan.

Complex Range Queries

Multiple conditions: WHERE department=10 AND salary>50000. Clustered by department+salary: efficient (scan relevant range). Wrong clustering: table scan needed.

Index Intersection

Query matches clustered range partially: use other indexes to narrow. Example: clustered by customer_id, secondary by status. WHERE customer_id BETWEEN 100-200 AND status='active'. Clustered finds range, secondary filter narrows.

Insertion, Deletion, and Reorganization

Insertion Cost

Find position: binary search (log n cost). Page found: insert row, maintain sort. Page full: split (expensive). Cost: O(log n) for search + O(page_size) for split.

Random Inserts

Insert random keys: frequent page splits. Fragmentation: pages scattered, not filled. Reorganization needed: compact, remove gaps. Cost: significant.

Sequential Inserts

Insert in clustering order (e.g., increasing IDs): append to end. No splits. Efficient. Common pattern: logs, events (time-ordered).

Deletion Impact

Delete row: remove, shift others (or mark deleted). Page becomes less full. Accumulates: many deletes -> many gaps. Reorganization: reclaim space.

Index Maintenance

Rebuild: expensive (sort all rows, recreate index). Typical: offline operation. Cost: downtime, resource intensive. Frequency: depends on workload.

Fragmentation Monitoring

Track: percentage empty space, page splits/sec. Rebuild threshold: >10-20% fragmentation (depends on system). Proactive: rebuild before severe fragmentation.

Performance Characteristics

Search Performance

Clustered key search: O(log n) tree traversal. Worst case: one disk access per level (typically 3-4 levels). Plus leaf access = 4-5 disk accesses typical. Very fast.

Range Query Performance

Find start: O(log n). Scan range: sequential (k rows = k/rows_per_page disk accesses). Excellent: minimize random I/O.

Insert/Delete Performance

O(log n) search + O(size) reorganization (page split). Amortized: acceptable. Burst inserts: problematic (many splits).

Full Table Scan

Clustered index: scan all leaves sequentially. Efficient: disk prefetch, cache hits. Non-clustered: random access pattern, slower.

Performance Comparison

Limitations and Trade-offs

Only One per Table

Physical constraint: can only order rows one way. Multiple clustered indexes: impossible. Must choose primary one. Limits optimization options.

Expensive Maintenance

Fragmentation: inserts cause page splits, scattered pages. Rebuild: offline, resource-intensive. Frequency: depends on workload. Cost: significant for OLTP systems.

Insert Performance Hit

Random inserts: page splits. Cost: O(page_size) per split. High-volume inserts: problematic. Sequential inserts: efficient (append). Workload-dependent.

Wrong Choice Impact

Poor clustering key: all queries suffer. Queries access random rows: expensive. No range queries benefit. Difficult to change (requires rebuild). Planning critical.

Table-Specific Optimization

Each table: one clustering decision. Cannot optimize for all query types. Compromise: choose best overall. Accept some queries less optimal.

Key Updates Problematic

If clustering key updateable: expensive. Row moves: physical reorganization. Immutability preferred. Avoid updatable clustered keys.

Clustered vs. Non-Clustered Indexes

Physical vs. Logical

Clustered: physical ordering (table layout). Non-clustered: logical ordering (separate structure). Clustered: affects all queries. Non-clustered: specific queries.

Leaf Node Difference

Clustered leaf: full row. Non-clustered leaf: index columns + row_id. Clustered: larger but no extra access. Non-clustered: smaller but extra lookup.

Number Allowed

Clustered: exactly one. Non-clustered: many (typically 999 limit in SQL Server). Multiple strategies possible with non-clustered. Flexibility advantage.

Maintenance Cost

Clustered: page splits expensive. Non-clustered: updates easier (separate index). Overhead: non-clustered. Trade-off: multiple indexes for flexibility.

Query Performance

Clustered: natural for primary workload. Non-clustered: excellent for specific queries. Combination: optimal (clustered for default, non-clustered for special queries).

Selection Strategy

Clustered: most common queries, range queries, sorting. Non-clustered: additional query patterns, low-cardinality columns. Both: comprehensive coverage.

Practical Design Considerations

Choose Primary Clustering Key

Criteria: (1) Used in range queries frequently, (2) Immutable or rarely changing, (3) Not NULL (all rows must participate), (4) Minimizes fragmentation (sequential inserts preferred).

Natural vs. Surrogate Keys

Natural key: business meaning, often ideal (ORDER BY). Surrogate key: identity column, simple but may not match queries. Consider: domain semantics.

Cardinality Consideration

High cardinality: good (minimal duplicates). Low cardinality: bad (many rows per value, grouping inefficient). Avoid: clustering by status or gender (poor distribution).

Insert Pattern Analysis

Sequential inserts: excellent (append, no splits). Random inserts: problematic (frequent splits). Design: prefer sequential keys if volume high.

Workload Analysis

OLTP: multiple query types, compromise clustering. OLAP: known query patterns, optimize clustering. Time-series: cluster by timestamp (sequential inserts, efficient range).

Monitoring and Tuning

Track fragmentation: plan rebuilds. Monitor query plans: verify index usage. Adjust: if clustered key poor, rebuild (expensive but sometimes necessary).

Database Implementations

SQL Server

Clustered index: mandatory (table structure). Every table has clustered index (on primary key by default). Can specify explicit clustering. Rebuild: REBUILD command (offline/online).

Oracle Database

Index-Organized Table (IOT): rows stored in B-Tree (clustered-like). Efficient for range queries. Can specify clustering key. Standard practice.

MySQL/InnoDB

Clustered on primary key: automatic. Full row in leaf. Very efficient. Recommended: always define primary key. Optimization: critical for performance.

PostgreSQL

CLUSTER command: reorganize table by index. One-time operation (not persistent). Table reverts as inserts occur. Manual clustering possible but not automatic.

Vertica

Column-oriented: different storage model. Segmentation: physical projection. Similar benefits to clustering (sequential access, compression). Modern approach.

References

• Ramakrishnan, R., and Gehrke, J. "Database Management Systems." McGraw-Hill, 3rd edition, 2003.
• Garcia-Molina, H., Ullman, J. D., and Widom, J. "Database Systems: The Complete Book." Pearson, 2nd edition, 2008.
• Silberschatz, A., Korth, H. F., and Sudarshan, S. "Database System Concepts." McGraw-Hill, 6th edition, 2010.
• DeWitt, D. J., and Gray, J. "An Architecture for High Performance Database Systems." Proceedings of ICDE, 1992.
• Microsoft SQL Server Documentation. "Clustered and Nonclustered Indexes." 2023.