Non-Clustered Index

Introduction

Non-clustered index: secondary index structure enabling fast lookups on columns other than clustering key. Multiple allowed (up to 999 in SQL Server). Flexible: add indexes for specific query patterns without reorganizing table.

Core mechanism: B-Tree with indexed columns in leaf, row identifier (row_id or clustered key) for data access. Enables query optimization: filtered search fast, data retrieval via row_id. Multiple strategies possible.

Usage: common in production databases. Each significant query pattern: dedicated non-clustered index. Strategy: minimize I/O, optimize specific queries. Essential for OLTP performance.

"Non-clustered indexes provide flexibility: multiple optimization strategies without table reorganization. Secondary access paths enable fast lookups on non-primary columns. Foundation of query performance tuning." -- Index design

Non-Clustered Index Concept

Logical Structure

Separate B-Tree: index columns ordered in leaf, row identifier for access. Clustered key or row_id: enables finding actual data. Multiple indexes: multiple trees, independent maintenance.

Index Independence

Non-clustered: doesn't affect table layout. Table: remains in clustered order (or heap). Multiple indexes: each independent. Changes: reflected in all indexes (transactional).

Flexibility Advantage

Query optimizations: add indexes for problem queries. No table reorganization. Maintenance: separate from data. Cost: storage and update overhead. Benefit: query speed improvement.

Selection and Use

Query planner: chooses best index for each query. Clustered: default (always available). Non-clustered: optional (used if beneficial). Multiple options: optimizer picks best.

Number of Indexes

Practical limit: 10-20 per table (index explosion). More indexes: slower inserts/updates (maintain all). Balance: query speed vs. write speed. Typical: 3-5 non-clustered indexes per table.

Index Structure and Leaf Nodes

B-Tree Organization

Non-clustered: standard B-Tree. Root-internal nodes guide traversal (same as clustered). Leaf nodes: contain index key(s) and row identifier. Distinct from clustered (no full row data).

Leaf Node Contents

SQL Server: (index_key, clustered_key) or (index_key, row_id). MySQL/InnoDB: (index_key, clustered_key). PostgreSQL: (index_key, row_id). Enables finding actual row in table.

Example Leaf Structure

Table clustered by employee_id
Non-clustered index on department

Leaf Node (Non-Clustered Index):
[dept='IT', emp_id=101]
[dept='IT', emp_id=103]
[dept='Sales', emp_id=102]
[dept='Sales', emp_id=104]

Lookup flow: find 'IT' -> get emp_ids [101, 103] -> access clustered index for full rows

Index Size Comparison

Non-clustered: smaller than clustered (index columns + row_id). Clustered: larger (full row). Difference: depends on row size. Typical: 10-20% of data size for small index.

Linked Leaf Nodes

Leaves linked (sibling pointers): enable range scans. Walk forward/backward through leaves. Enables: sequential access on index key. Supports: BETWEEN queries, sorted results.

Row Identifier and Lookup

Row Identifier Types

Clustered system: clustered key stored in non-clustered leaf. Data retrieval: navigate clustered index (known key). Heap-based: row_id (physical location). Data retrieval: direct access (faster but physical).

Key Lookup Mechanism

Find row: (1) Search non-clustered index (find index key), (2) Get clustered key/row_id, (3) Access clustered index/heap to get full row. Multiple disk accesses typical (2-3 more than direct clustered access).

Clustered Key Advantage

Clustered key: immutable, identifies row uniquely. Non-clustered: stored in all indexes. Change clustered key: propagates to all. Cost: expensive (all indexes updated). Immutability critical.

Key Lookup Cost

Navigation: tree traversal (log n disk accesses). Leaf node: get clustered key (1 access). Clustered index: find row (log n accesses). Total: 2*log n + 1 typical. Expensive for large result sets.

Covering Index Optimization

If non-clustered contains all needed columns: no key lookup required. Query satisfied entirely from index. Saves disk accesses. Strategic optimization.

Key Lookup Operations

Simple Equality Lookup

WHERE department='IT'. Non-clustered index on department: find 'IT' (binary search). Get all employee_ids. For each: lookup clustered index (key lookup). Cost: 5-10 disk accesses typical (depends on result size).

Lookup Join Pattern

Nested loop join: outer table provides department values. Inner: lookup clustered for each. Many lookups: expensive. Batch: group by department, reduce redundant lookups.

Range Query Lookups

WHERE department IN ('IT', 'HR'). Non-clustered: find ranges, get keys. Multiple key lookups: one per row. Cost: linear in result size (manageable for small ranges).

Lookup Optimization

Query planner: decisions on lookup strategy. Clustered index scan: alternative (if result large, scan faster than lookups). Cost threshold: break-even point.

Batch Lookups

Prefetch: multiple rows before accessing. Reduce latency: parallel I/O. Implementation: depends on system. SQL Server: row goal optimization (stop early for TOP N).

Covering Indexes

Concept

Covering index: contains all columns needed for query. No key lookup required. Query satisfied entirely from index leaves. Major optimization: avoid disk access to clustered index.

Example Covering Index

Query: SELECT name, salary FROM employees WHERE department='IT'

Index on (department, name, salary):
Leaf: [dept, name, salary, clustered_key]

Search 'IT' -> all needed columns in index leaves
Result: no key lookup required

Non-covering index (salary missing):
Leaf: [dept, name, clustered_key]
Need salary: must lookup clustered index (extra cost)

Benefits

Eliminates key lookup: single index scan. Fast: sequential leaf reads. Cost: reduced disk I/O dramatically. Index scan only: no table access.

Index Size Trade-off

Covering: larger index (more columns). Extra storage: worth if query frequent. Design: balance index size vs. query benefit. Sweet spot: 2-4 extra columns.

Composite Indexes

Multi-column covering: (filter_col, output_col1, output_col2, ...). Order matters: filter first (filters efficiently), outputs after. Design: crucial for efficiency.

Included Columns

Concept

Included columns: added to index leaf without being part of key. Search: doesn't use included columns. But: reduces key lookup. Compromise between index size and benefit.

Syntax Example

CREATE INDEX idx_dept ON employees(department) INCLUDE (salary, name);

Index key: department (used for search)
Included: salary, name (in leaf but not key)

Query: SELECT salary WHERE department='IT'
Finds 'IT' -> gets salary from index leaf (no lookup)

Advantages vs. Covering

Included: smaller key size (faster searches). Covering: key contains all (must include in search). Included: flexibility (search on limited columns, include extra data). Modern optimization.

B-Tree Navigation

Included columns: not in internal nodes (key only). Faster navigation (smaller key). Full columns: in leaf only. Reduces overhead.

Database Support

SQL Server: INCLUDE clause (standard). MySQL: not supported (include in key). PostgreSQL: INCLUDE clause (recent). Oracle: similar but different syntax. Feature: modern systems.

Multi-Column Indexes

Composite Index Design

Multiple key columns: order critical. First column: most filtering (selection). Second: range or second filter. Example: (department, salary). Search department fast, range within department.

Index Order Principle

Equality columns first: department='IT'. Range columns next: salary>50000. Sort columns last: ORDER BY. Order: impacts efficiency. Wrong order: index underutilized.

Example Multi-Column Query

Index: (department, salary, hire_date)

Query: WHERE department='IT' AND salary>50000 ORDER BY hire_date
Execution:
1. Find department='IT' in index
2. Scan for salary>50000 within IT
3. Results already sorted by hire_date
4. Very efficient (full index usage)

Partial Index Utilization

Query: WHERE salary>50000. Index (department, salary): utilizes only if department filtered. Without department: scan all. Suboptimal. Design for common queries.

Index Explosion

Multiple queries: multiple multi-column indexes needed. Too many: maintenance overhead. Strategy: identify key queries, optimize for those. Balance: coverage vs. cost.

Performance Characteristics

Search Performance

Non-clustered search: O(log n) index traversal. Find index key: binary search. Comparable to clustered. Key difference: leaf contains row_id (not full row).

Result Retrieval

Small result set: key lookup acceptable (few extra accesses). Large result set: many lookups (expensive). Decision threshold: estimate result size before committing to lookup.

Key Lookup Cost

Per row: 1-2 disk accesses (find row in clustered). 100 rows: 100-200 accesses typical. Compare: clustered index scan (sequential). Tipping point: break-even at 10-20% result set.

Covering Benefits

Covering index: eliminates lookups. Single scan: all data. Cost: index size. Benefit: query speed dramatic improvement. ROI: excellent if query frequent.

Benchmark Table

Comparison with Clustered Indexes

Physical vs. Logical

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

Data Access

Clustered: leaf contains full row. Non-clustered: leaf contains key only. Access pattern: clustered direct, non-clustered requires lookup.

Number Allowed

Clustered: exactly one. Non-clustered: many (typically up to 999). Flexibility: multiple strategies. Trade-off: maintenance cost.

Maintenance Cost

Clustered: expensive (table reorganization). Non-clustered: updates to index only. Non-clustered: easier to add/drop. Practical: non-clustered preferred when possible.

Query Optimization

Clustered: forces table order. Non-clustered: flexible (can add/remove). Multiple strategies: combine clustering + non-clustered for comprehensive optimization.

Combined Strategy

Clustered: primary access path (choose carefully). Non-clustered: secondary paths (add as needed). Together: comprehensive performance optimization. Both: essential.

Design Strategies

Workload Analysis

Identify key queries: frequency, selectivity, result size. Profile: find slow queries. Analyze: determine index benefit. Create: only beneficial indexes. Avoid: random index creation.

Index Column Selection

Choose columns: used in WHERE, JOIN, GROUP BY, ORDER BY. Frequency: indexes for most frequent. Balance: index size vs. benefit. Sweet spot: 2-4 columns.

Column Order

Equality columns first: department='IT'. Range columns next: salary>50000. Sort columns last: ORDER BY. Order: critical for efficiency. Test: verify expected column ordering.

Index Covering Strategy

Identify covering candidates: queries accessing specific columns. Add INCLUDE or composite: cover common queries. Trade-off: index size for query speed. Selective: cover high-benefit queries.

Incremental Approach

Start: clustered index only. Monitor: identify slow queries. Add: non-clustered for each bottleneck. Measure: verify improvement. Avoid: pre-creating random indexes. Iterative refinement.

Monitoring and Maintenance

Unused indexes: consume resources, slow writes. Monitor: usage statistics. Remove: unused indexes. Fragmentation: rebuild/reorganize periodically. Proactive: maintain index health.

Practical Examples

E-Commerce Example

Table: Orders (order_id, customer_id, order_date, status, total)
Clustered: order_id (natural ordering)

Queries:
1. "GET orders by customer" -> Non-clustered(customer_id)
2. "GET recent high-value orders" -> Non-clustered(order_date DESC, total)
3. "FILTER by status" -> Non-clustered(status) INCLUDE (customer_id, total)

Strategy: 3 non-clustered indexes for key queries

User Profile Example

Table: Users (user_id, email, phone, created_date, status)
Clustered: user_id

Queries:
1. "FIND by email" (login) -> Non-clustered(email) INCLUDE (status)
2. "FIND by phone" (recovery) -> Non-clustered(phone)
3. "RECENT users" -> Non-clustered(created_date DESC)

Covering: email index includes status (avoids lookup for auth check)

Event Log Example

Table: Events (event_id, timestamp, user_id, event_type, data)
Clustered: timestamp (sequential inserts optimal)

Queries:
1. "EVENTS by user" -> Non-clustered(user_id, timestamp)
2. "FILTER by type" -> Non-clustered(event_type, timestamp)
3. "COVERAGE" -> Composite (user_id, event_type, timestamp)

Strategy: composite index covers multiple query patterns

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.
• Microsoft SQL Server Documentation. "Clustered and Nonclustered Indexes Designed." 2023.
• MySQL InnoDB Storage Engine Documentation. "Indexing Strategy." 2023.