SQL Indexing

SQL indexing is the practice of creating auxiliary data structures that allow the database engine to locate rows matching a query condition without scanning the entire table. An index on a column is analogous to a book's index: instead of reading every page to find a topic, you look up the index entry and jump directly to the right page.

Why indexing is important:

Without an index, a query like SELECT * FROM orders WHERE customer_id = 42 requires a full table scan — reading every row. On a table with 50 million rows, this is slow. With an index on customer_id, the engine performs a B-tree lookup in O(log n) time.

What indexes improve:

• WHERE clause filtering
• JOIN conditions (especially the join columns)
• ORDER BY sorting (index may already be ordered)
• GROUP BY operations
• Covering queries (index-only scans when all needed columns are in the index)

The trade-off:

• Indexes speed up reads but slow down writes (INSERT, UPDATE, DELETE must update the index too)
• Indexes consume disk space
• Too many indexes on a write-heavy table can hurt overall throughput

Types of indexes:

• B-tree (default in most databases) — suited for equality and range queries
• Hash — fast equality lookups; does not support range queries
• Full-text — searches within text content
• GIN / GiST (PostgreSQL) — for JSON, arrays, geometric data
• Clustered — determines physical row order (one per table in SQL Server/MySQL InnoDB)
• Non-clustered — separate structure with pointers to heap rows
• Composite — covers multiple columns
• Partial / filtered — only indexes rows matching a condition

Most SQL databases use a B-tree (balanced tree) as the underlying data structure for indexes. Understanding the mechanics explains when an index helps and when it doesn't.

B-tree structure:

• The index stores key values (the indexed column values) in sorted order in a tree structure
• The tree has a root node, internal nodes (for navigation), and leaf nodes (which hold the actual key values and pointers to the table rows)
• Because the tree is balanced, every lookup takes O(log n) time regardless of which key is searched

How a query uses an index:

For SELECT * FROM employees WHERE employee_id = 500:

1. Database starts at the B-tree root
2. Follows branch pointers (left = smaller, right = larger) down the tree
3. Reaches the leaf node containing employee_id = 500
4. Retrieves the row pointer (a page number + row offset, called a "row ID" or "heap pointer")
5. Jumps directly to that page in the table to fetch the full row

Index-only scans (covering indexes): If the SELECT only needs columns that are all in the index, the database never touches the main table — the index itself contains all the data needed.

CREATE INDEX idx_emp_dept_salary ON employees(department_id, salary);
-- This index covers: SELECT salary FROM employees WHERE department_id = 10

When indexes are NOT used:

• The optimizer estimates a full scan is cheaper (e.g., query returns >15–20% of rows)
• A function is applied to the indexed column: WHERE YEAR(hire_date) = 2024 (use WHERE hire_date >= '2024-01-01' AND hire_date < '2025-01-01' instead)
• Implicit type conversion prevents index use
• LIKE '%value%' (leading wildcard)

A clustered index determines the physical storage order of rows in a table. The table data itself is stored sorted according to the clustered index key. Because of this, there can only be one clustered index per table.

Key characteristics:

• The leaf nodes of the B-tree are the actual table rows (not pointers to rows)
• Lookups by the clustered index key are extremely fast — no extra row pointer lookup needed
• Range queries on the clustered index key are especially efficient because data is physically contiguous on disk

Default behavior by database:

• MySQL (InnoDB): The primary key is always the clustered index. If no primary key is defined, InnoDB uses the first UNIQUE NOT NULL column, or generates a hidden 6-byte row ID.
• SQL Server: A primary key creates a clustered index by default (you can override this)
• PostgreSQL: PostgreSQL does not have a true clustered index; it uses heap storage. The CLUSTER command physically reorders the table once, but it is not maintained automatically.

Example:

-- SQL Server: primary key = clustered index by default
CREATE TABLE orders (
    order_id   INT PRIMARY KEY,         -- clustered index on order_id
    order_date DATE,
    total      DECIMAL(10,2)
);

-- Explicit clustered index on SQL Server
CREATE CLUSTERED INDEX idx_order_date ON orders(order_date);

Choosing the clustered index key: Ideal characteristics:

• Narrow — shorter keys mean more entries fit per B-tree page
• Static — key value should not change (changing it requires physically moving the row)
• Monotonically increasing — sequential inserts (e.g., auto-increment IDs) avoid page splits; random values (e.g., UUID v4) cause fragmentation

A non-clustered index is a separate data structure from the table's row data. It stores a copy of the indexed column values in sorted order, with each entry containing a pointer back to the actual row in the table (a row ID or primary key reference).

Key characteristics:

• Multiple non-clustered indexes can exist on one table (SQL Server allows up to 999)
• The leaf nodes contain the indexed key values + a row locator (not the full row data)
• Lookups require two steps: find the key in the index, then follow the pointer to the table row (called a key lookup or bookmark lookup)
• The extra pointer lookup adds overhead — index-only scans (covering indexes) avoid this

Structure:

Non-clustered index B-tree
└── Leaf: (email value, row pointer → heap/clustered index)

Separate table heap or clustered index
└── Full row data

Creating a non-clustered index:

CREATE INDEX idx_employees_email ON employees(email);
CREATE NONCLUSTERED INDEX idx_emp_dept ON employees(department_id);  -- SQL Server explicit syntax

Covering index (important optimization): Include additional columns in the index so queries can be satisfied without touching the main table:

CREATE INDEX idx_emp_dept_covering
ON employees(department_id)
INCLUDE (first_name, salary);
-- SELECT first_name, salary FROM employees WHERE department_id = 5
-- can be answered entirely from the index

Non-clustered vs clustered:

A composite index (also called a multi-column index or compound index) is an index built on two or more columns of a table. The index entries are sorted first by the first column, then by the second within each first-column value, and so on.

CREATE INDEX idx_emp_dept_salary ON employees(department_id, salary);
CREATE INDEX idx_name_composite ON customers(last_name, first_name, city);

The left-prefix rule — the most important concept:

A composite index on (A, B, C) supports queries filtering on:

• A alone ✓
• A, B ✓
• A, B, C ✓
• B alone ✗ (cannot use the index without the leftmost column)
• B, C alone ✗

-- index on (department_id, salary):
WHERE department_id = 5                          -- uses index ✓
WHERE department_id = 5 AND salary > 80000       -- uses index fully ✓
WHERE salary > 80000                             -- cannot use this index ✗

When composite indexes beat separate single-column indexes:

A single composite index can serve multiple columns in a single B-tree traversal. Two separate single-column indexes would require a merge or only one would be used.

Covering queries: A composite index covering all columns in a SELECT enables an index-only scan — the database never reads the main table:

CREATE INDEX idx_covering ON orders(customer_id, order_date, total);
SELECT order_date, total FROM orders WHERE customer_id = 42;
-- answered entirely from the index

Column order matters: Put the most selective column first for equality filters; put range-queried columns last (range stops the index from being used for subsequent columns).

A covering index is an index that contains all the columns a query needs to satisfy — so the database engine can answer the query entirely from the index without reading the main table (called an index-only scan).

-- Query:
SELECT first_name, salary FROM employees WHERE department_id = 5;

-- Covering index includes all three columns touched by the query:
CREATE INDEX idx_emp_covering ON employees(department_id, first_name, salary);
-- department_id is the filter; first_name and salary are the SELECT columns

Without a covering index, the engine must: (1) look up matching rows in the index, then (2) fetch the full row from the table heap for each match. With a covering index, step 2 is eliminated.

How to create one: In PostgreSQL and SQL Server, use INCLUDE to add non-key columns to the index leaf:

CREATE INDEX idx_emp_dept ON employees(department_id) INCLUDE (first_name, salary);

When to use: High-frequency queries on large tables where the select list and filter columns are known and stable. Covering indexes use more disk space and slow down writes — use them selectively.

Window functions perform calculations across a set of rows related to the current row, without collapsing the rows into a single group (unlike GROUP BY aggregates). They use an OVER() clause.

SELECT
    name,
    department,
    salary,
    AVG(salary)  OVER (PARTITION BY department) AS dept_avg,
    RANK()       OVER (PARTITION BY department ORDER BY salary DESC) AS dept_rank,
    LAG(salary)  OVER (ORDER BY hire_date) AS prev_hire_salary
FROM employees;

Key window function categories:

• Ranking: ROW_NUMBER(), RANK(), DENSE_RANK(), NTILE(n)
• Offset: LAG(col, n), LEAD(col, n), FIRST_VALUE(), LAST_VALUE()
• Aggregate: SUM(), AVG(), COUNT(), MIN(), MAX() — used with OVER()

RANK() vs ROW_NUMBER() vs DENSE_RANK(): With scores 100, 100, 90:

• ROW_NUMBER(): 1, 2, 3 (always unique)
• RANK(): 1, 1, 3 (ties share rank, gap after)
• DENSE_RANK(): 1, 1, 2 (ties share rank, no gap)

Common interview use: "Find the top 3 earners per department":

WITH ranked AS (
    SELECT name, department, salary,
           ROW_NUMBER() OVER (PARTITION BY department ORDER BY salary DESC) AS rn
    FROM employees
)
SELECT * FROM ranked WHERE rn <= 3;

Supported in: PostgreSQL, MySQL 8.0+, SQL Server, Oracle, SQLite 3.25+.