Composite Index

In the real world of database design, queries rarely filter on just one column. Consider an e-commerce application: customers search for products by category AND price range, orders are retrieved by customer_id AND order_date, and shipping records are filtered by warehouse_id AND status AND shipment_date. Single-column indexes, while valuable, often fall short when facing these multi-predicate queries.

Composite indexes—also known as multi-column indexes, concatenated indexes, or compound indexes—solve this fundamental problem by indexing multiple columns together as a single, unified structure. Understanding how to design and leverage these indexes effectively separates routine database administrators from true database performance engineers.

A composite index (or multi-column index) is an index built on two or more columns of a table. Unlike single-column indexes that organize data by the values of one attribute, composite indexes create a hierarchical ordering based on the combined values of multiple columns.

Formal Definition:

Given a table T with columns (C₁, C₂, ..., Cₙ), a composite index I on columns (C₁, C₂, ..., Cₖ) where k ≥ 2 creates an ordering where:

• Records are first sorted by C₁
• Within each C₁ value, records are sorted by C₂
• Within each (C₁, C₂) combination, records are sorted by C₃
• And so on, through all k columns

This creates a lexicographic ordering—similar to how words are ordered in a dictionary, where the first letter is primary, the second is secondary, and so forth.

Most database systems implement composite indexes using B+-trees, the dominant index structure in modern RDBMS. Understanding how multi-column keys are stored in a B+-tree is crucial for designing effective composite indexes.

Key Composition in B+-Trees:

In a B+-tree for a composite index on columns (A, B, C), each index entry contains:

• Composite Key: The concatenated values (A, B, C) stored as a single searchable unit
• Pointer: Either a record pointer (in clustered indexes) or a row identifier (in non-clustered indexes)

The tree maintains its sorted invariant based on the composite key comparison, which works lexicographically:

Physical Layout in Leaf Nodes:

The leaf nodes of a composite index B+-tree contain entries sorted by the composite key:

Leaf Node 1: [(1,A,100), (1,A,200), (1,B,100), (1,B,150), (1,C,100)] -> next
Leaf Node 2: [(2,A,50), (2,A,100), (2,B,75), (2,C,200)] -> next
Leaf Node 3: [(3,A,25), (3,B,150), (3,C,100), (3,C,200)] -> null

Notice how entries are sorted first by the first column (1, 2, 3), then by the second column (A, B, C within each first-column value), and finally by the third column (numeric values within each two-column combination).

Internal Node Keys:

Internal nodes contain separator keys that guide searches down the tree. These separator keys are also composite, containing enough columns to correctly route queries:

The fundamental motivation for composite indexes arises from the limitations of combining multiple single-column indexes. Consider a query with two predicates:

SELECT * FROM employees
WHERE department_id = 50 AND hire_date = '2023-01-15';

With two separate single-column indexes:

1. Index on department_id finds all employees in department 50 (say, 500 rows)
2. Index on hire_date finds all employees hired on 2023-01-15 (say, 20 rows)
3. The database must intersect these result sets to find matching rows

This intersection operation has overhead, and neither index alone can efficiently pinpoint the exact rows.

With a composite index on (department_id, hire_date):

1. The index directly navigates to entries where department_id = 50 AND hire_date = '2023-01-15'
2. The query finds the exact rows in a single index traversal
3. No post-processing intersection needed

Selectivity measures how effectively an index narrows down the search space. For a single column, selectivity is the reciprocal of the number of distinct values (assuming uniform distribution):

Selectivity(column) = 1 / NDV(column)

Where NDV is the Number of Distinct Values.

For composite indexes, selectivity combines across columns:

Selectivity(A, B) ≈ Selectivity(A) × Selectivity(B)
             = 1 / (NDV(A) × NDV(B))

This multiplicative effect is why composite indexes can be dramatically more selective than single-column indexes.

The Independence Assumption:

The multiplicative selectivity formula assumes column values are statistically independent. In practice, columns are often correlated:

• Job titles may cluster by department (all 'Developer' titles in Engineering)
• Certain product categories may dominate specific warehouses
• Geographic regions may correlate with customer demographics

When columns are correlated, the composite selectivity is worse than the formula predicts because the combinations are not uniformly distributed. Database query optimizers use histograms and multi-column statistics to account for these correlations.

The SQL syntax for creating composite indexes is straightforward—list multiple columns in the CREATE INDEX statement. However, the order of columns in the definition is critically important and determines which queries the index can serve effectively.

Standard SQL Syntax:

CREATE INDEX index_name ON table_name (column1, column2, column3, ...);

The column order directly maps to the lexicographic ordering in the B+-tree: column1 is the primary sort key, column2 is secondary, and so on.

Composite indexes excel in specific query patterns. Understanding these patterns helps identify opportunities to improve performance through strategic multi-column indexing.

Composite indexes come with measurable costs that must be weighed against their query performance benefits.

Storage Requirements:

The storage size of a composite index depends on:

• Number of rows in the table
• Combined size of all indexed columns
• Index structure overhead (B+-tree internal nodes, pointers)
• Fill factor settings

Approximate formula:

Index Size ≈ Rows × (Sum of column sizes + Pointer size) × (1 / Fill factor) × Overhead factor

Maintenance Overhead:

Every INSERT, UPDATE (on indexed columns), and DELETE operation must update the composite index:

1. INSERT: New entry must be added at the correct sorted position, potentially causing page splits
2. UPDATE: If any indexed column changes, the entry must be repositioned (effectively delete + insert)
3. DELETE: Entry must be removed, potentially causing page merges

The maintenance cost increases with:

• Number of composite indexes on the table
• Number of columns in each composite index
• Frequency of DML operations
• Amount of data being modified