Indexes

What is a Database Index?

A database index is a data structure that improves the speed of data retrieval operations on a table. Think of it like the index at the back of a book — instead of reading every page to find a topic, you look up the page number in the index and jump directly to it.

Indexes work by creating a separate data structure (typically a B-tree) that stores a copy of the indexed column(s) along with a pointer to the full row. When you query with a WHERE clause that matches an indexed column, the database can use the index to find the relevant rows without scanning the entire table.

Without vs With Index

Without Index (Full Table Scan):
- Scans ALL 1,000,000 rows to find 10 matching rows
- Time complexity: O(n)

With Index (Index Scan):
- Uses B-tree to find 10 matching rows
- Time complexity: O(log n)

Simple Example

-- Table with 1 million rows
CREATE TABLE users (
    id INT PRIMARY KEY,
    email VARCHAR(255),
    name VARCHAR(100),
    created_at TIMESTAMP
);

-- This query scans ALL rows (slow)
SELECT * FROM users WHERE email = 'alice@example.com';

-- Create an index on email
CREATE INDEX idx_users_email ON users(email);

-- Now the query uses the index (fast)
SELECT * FROM users WHERE email = 'alice@example.com';

Types of Indexes

The B-tree index is by far the most commonly used index type in relational databases.

B-Tree Index: The Most Common Index

A B-tree (balanced tree) is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in O(log n) time. It is the default index type in most relational databases.

How B-Tree Works

B-Tree with column values [1, 3, 5, 7, 9, 11, 13, 15]:

              [7]
            /     \
        [3, 5]   [11, 13]
       /   |   \\    |   \
     [1] [3] [5]  [9] [15]

Leaf nodes are linked for range scans:
[1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> [15]

Key Properties

1. Balanced: All leaf nodes are at the same depth
2. Sorted: Values in each node are in order
3. Linked leaves: Leaf nodes form a linked list for efficient range scans
4. High fan-out: Each node can have many children, keeping the tree shallow

B-Tree Operations

-- Creating a B-tree index (default in most databases)
CREATE INDEX idx_orders_date ON orders(order_date);

-- The index stores values in sorted order:
-- Leaf Level: [2024-01-01] -> [2024-01-02] -> [2024-01-03] -> ...
-- Each entry points to the row(s) with that value

-- Range query uses leaf links efficiently:
SELECT * FROM orders 
WHERE order_date BETWEEN '2024-01-01' AND '2024-01-31';
-- Jumps to first matching leaf, scans linked list until end of range

B-Tree vs Other Structures

B-tree indexes are ideal for most query patterns because they support both equality and range operations.

Creating Indexes with SQL

The CREATE INDEX statement creates a new index on one or more columns of a table.

Basic Syntax

-- Create a simple index
CREATE INDEX idx_column_name ON table_name(column_name);

-- Example: Index on last_name
CREATE INDEX idx_employees_lastname ON employees(last_name);

-- Now queries using last_name benefit from the index:
SELECT * FROM employees WHERE last_name = 'Smith';
SELECT * FROM employees WHERE last_name LIKE 'Sm%';
SELECT * FROM employees ORDER BY last_name;

CREATE UNIQUE INDEX

A unique index ensures that the indexed column(s) contain no duplicate values. It also enforces uniqueness at the database level.

-- Unique index: no two rows can have the same email
CREATE UNIQUE INDEX idx_users_email ON users(email);

-- Attempting to insert duplicate fails:
INSERT INTO users (email, name) VALUES ('alice@example.com', 'Alice');
INSERT INTO users (email, name) VALUES ('alice@example.com', 'Bob');
-- ERROR: duplicate key value violates unique constraint

-- Unique index also acts as a regular index for queries:
SELECT * FROM users WHERE email = 'alice@example.com';

Naming Conventions

Follow a consistent naming convention for indexes:

-- Common patterns:
-- idx_table_column
CREATE INDEX idx_orders_customer_id ON orders(customer_id);

-- idx_table_column1_column2 (composite)
CREATE INDEX idx_orders_customer_date ON orders(customer_id, order_date);

-- pk_table (primary key)
-- Already created automatically: PRIMARY KEY (id)

-- fk_table_column (foreign key)
CREATE INDEX idx_orders_product_id ON orders(product_id);

Index Creation Considerations

• Online creation: Most modern databases support CREATE INDEX CONCURRENTLY (PostgreSQL) or ALTER TABLE ... ADD INDEX (MySQL) to avoid locking
• Storage: Indexes consume disk space and memory
• Write overhead: Every INSERT/UPDATE/DELETE must update the index
• Selective creation: Only index columns that are frequently queried

Composite Indexes: Multiple Columns

A composite index (multi-column index) is an index on two or more columns. It is created when queries frequently filter or sort by multiple columns together.

Creating Composite Indexes

-- Composite index on two columns
CREATE INDEX idx_orders_customer_date ON orders(customer_id, order_date);

-- This index helps queries that filter on customer_id AND order_date:
SELECT * FROM orders 
WHERE customer_id = 101 AND order_date = '2024-01-15';

-- It also helps queries that filter on customer_id alone (leftmost prefix):
SELECT * FROM orders WHERE customer_id = 101;

-- But it does NOT help queries that only filter on order_date:
SELECT * FROM orders WHERE order_date = '2024-01-15';

Leftmost Prefix Rule

A composite index on (A, B, C) can be used for:

-- Composite index on (department_id, salary, hire_date)
CREATE INDEX idx_emp_dept_salary_date 
ON employees(department_id, salary, hire_date);

-- All these queries use the index:
SELECT * FROM employees WHERE department_id = 5;
SELECT * FROM employees WHERE department_id = 5 AND salary > 70000;
SELECT * FROM employees WHERE department_id = 5 AND salary > 70000 AND hire_date > '2020-01-01';

-- This query does NOT use the index effectively:
SELECT * FROM employees WHERE salary > 70000;

Column Order Matters

The order of columns in a composite index should match your query patterns:

-- Bad: order_date first, but most queries start with customer_id
CREATE INDEX idx_bad ON orders(order_date, customer_id);

-- Good: customer_id first (more selective in WHERE clauses)
CREATE INDEX idx_good ON orders(customer_id, order_date);

-- For ORDER BY optimization:
SELECT * FROM orders 
WHERE customer_id = 101 
ORDER BY order_date DESC;
-- The composite index (customer_id, order_date) satisfies both filtering and sorting

Covering Index: Avoid Table Lookups

A covering index includes all the columns needed by a query, so the database can answer the query entirely from the index without reading the table data. This eliminates the need for a "key lookup" or "bookmark lookup" to the table.

How Covering Indexes Work

-- Without covering index:
SELECT customer_id, order_date, total 
FROM orders 
WHERE customer_id = 101;
-- 1. Use index on customer_id to find row pointers
-- 2. For each row, read the full row from the table (expensive!)

-- Create a covering index with ALL needed columns:
CREATE INDEX idx_orders_covering 
ON orders(customer_id, order_date, total);

-- Now the query is answered entirely from the index:
SELECT customer_id, order_date, total 
FROM orders 
WHERE customer_id = 101;
-- 1. Find matching entries in the index
-- 2. Return the values directly from index (no table access!)

Detecting Covering Indexes

Most databases show "Using index" in EXPLAIN output for covering index scans:

-- MySQL EXPLAIN
EXPLAIN SELECT customer_id, order_date, total 
FROM orders WHERE customer_id = 101;
+----+-------+---------------+-------------------+
| id | type  | possible_keys | Extra             |
+----+-------+---------------+-------------------+
|  1 | ref   | idx_covering  | Using index       |
+----+-------+---------------+-------------------+

-- PostgreSQL EXPLAIN ANALYZE
EXPLAIN ANALYZE 
SELECT customer_id, order_date, total 
FROM orders WHERE customer_id = 101;
-- Output: "Index Only Scan using idx_covering on orders"

Designing Covering Indexes

Include columns in this order:

1. WHERE columns (most selective first)
2. ORDER BY columns
3. SELECT columns (for covering)

-- Query: SELECT order_date, total FROM orders 
--        WHERE customer_id = 101 ORDER BY order_date;

CREATE INDEX idx_orders_covering 
ON orders(customer_id, order_date, total);
-- customer_id: WHERE clause
-- order_date: ORDER BY + SELECT
-- total: SELECT (for covering)

Trade-offs

• Pros: Dramatically faster reads, less I/O
• Cons: Larger index size, more storage, slower writes
• Best for: Read-heavy tables with specific query patterns

Index Selectivity: When an Index is Effective

Selectivity measures how many distinct values exist in a column relative to the total number of rows. High selectivity means the index can significantly narrow down the result set.

Calculating Selectivity

-- Selectivity = Number of Distinct Values / Total Rows
-- Range: 0 to 1 (higher = more selective = better index)

-- Example: gender column (low selectivity)
SELECT COUNT(DISTINCT gender) / COUNT(*) AS selectivity FROM users;
-- Result: ~0.000002 (2 values / 1,000,000 rows) - BAD index candidate

-- Example: email column (high selectivity)
SELECT COUNT(DISTINCT email) / COUNT(*) AS selectivity FROM users;
-- Result: ~1.0 (nearly unique) - GOOD index candidate

-- Example: status column (medium selectivity)
SELECT COUNT(DISTINCT status) / COUNT(*) AS selectivity FROM orders;
-- Result: ~0.00001 (5 statuses / 500,000 rows) - MARGINAL

Selectivity Guidelines

Low-Selectivity Index Gotchas

-- Index on 'is_active' (boolean, ~50% true/false) is usually useless:
CREATE INDEX idx_users_active ON users(is_active);

-- Query: SELECT * FROM users WHERE is_active = true;
-- Database optimizer will likely IGNORE the index and do a full scan
-- because scanning ~50% of rows via index is slower than sequential scan

-- EXCEPTION: When combined with other columns in composite index
CREATE INDEX idx_active_email ON users(is_active, email);
-- Query: SELECT * FROM users WHERE is_active = true AND email = '...';
-- Uses index to narrow down to active users, then finds specific email

Checking Index Usage

-- PostgreSQL: Check index usage statistics
SELECT indexrelname, idx_scan, idx_tup_read, idx_tup_fetch
FROM pg_stat_user_indexes
WHERE relname = 'users';

-- idx_scan = 0 means the index is never used (candidate for removal)

When Indexes Help Performance

Indexes are most beneficial for specific query patterns. Understanding when they help is crucial for database optimization.

Queries That Benefit from Indexes

-- 1. Equality searches (WHERE column = value)
SELECT * FROM users WHERE email = 'alice@example.com';
-- Index on email: O(log n) lookup

-- 2. Range queries (WHERE column BETWEEN a AND b)
SELECT * FROM orders WHERE order_date BETWEEN '2024-01-01' AND '2024-01-31';
-- Index on order_date: O(log n + k) where k is matching rows

-- 3. JOIN operations
SELECT o.*, c.name 
FROM orders o 
JOIN customers c ON o.customer_id = c.id;
-- Index on orders.customer_id: avoids full scan of orders

-- 4. ORDER BY / GROUP BY
SELECT department_id, COUNT(*) 
FROM employees 
GROUP BY department_id;
-- Index on department_id: avoids sorting

-- 5. LIKE with prefix pattern
SELECT * FROM users WHERE name LIKE 'John%';
-- Index on name: uses index (prefix match)

-- 6. EXISTS / IN with indexed subquery
SELECT * FROM orders o 
WHERE EXISTS (SELECT 1 FROM customers c WHERE c.id = o.customer_id);

Query Patterns That Use Indexes Efficiently

Real-World Example

-- Without index: 2.5 seconds (full scan of 10M rows)
SELECT * FROM orders 
WHERE customer_id = 12345 
AND order_date > '2024-01-01' 
ORDER BY order_date DESC;

-- Create composite index:
CREATE INDEX idx_orders_cust_date ON orders(customer_id, order_date DESC);

-- With index: 0.003 seconds (index seek + scan)
-- Same query now runs 800x faster

When Indexes Hurt Performance

Indexes are not always beneficial. They add overhead to write operations and consume storage. Understanding when NOT to index is equally important.

Write Operations Are Slower

-- Each INSERT must update every index on the table:
INSERT INTO orders (customer_id, order_date, total) VALUES (1, '2024-01-15', 100);
-- If orders has 5 indexes, the database must:
-- 1. Insert into primary key index
-- 2. Insert into idx_orders_customer_id
-- 3. Insert into idx_orders_date
-- 4. Insert into idx_orders_total
-- 5. Insert into idx_orders_status

-- UPDATE must also maintain all indexes:
UPDATE orders SET total = 150 WHERE id = 123;
-- Every index containing 'total' must be updated

-- DELETE must clean up index entries:
DELETE FROM orders WHERE id = 123;
-- All index entries for row 123 must be removed

Anti-Patterns: Bad Indexes

-- 1. Indexing every column (waste of resources)
CREATE INDEX idx_orders_id ON orders(id);          -- Already indexed (PK)
CREATE INDEX idx_orders_customer ON orders(customer_id);
CREATE INDEX idx_orders_date ON orders(order_date);
CREATE INDEX idx_orders_total ON orders(total);
CREATE INDEX idx_orders_status ON orders(status);
CREATE INDEX idx_orders_shipped ON orders(shipped_date);
-- 6 indexes = 6x write overhead!

-- 2. Low-selectivity indexes
CREATE INDEX idx_users_active ON users(is_active);  -- Boolean: 50/50
CREATE INDEX idx_products_category ON products(category_id); -- Only 20 categories

-- 3. Small tables (< 1000 rows)
-- Full table scan is often faster than index + lookup

-- 4. Duplicate/redundant indexes
CREATE INDEX idx1 ON orders(customer_id, order_date);
CREATE INDEX idx2 ON orders(customer_id);  -- Redundant: idx1 covers this

Index Maintenance Costs

When to Remove Indexes

-- Find unused indexes (PostgreSQL)
SELECT indexrelname, idx_scan
FROM pg_stat_user_indexes
WHERE idx_scan = 0 AND indexrelname NOT LIKE 'pg_%';

-- Drop unused index
DROP INDEX idx_unused;

-- Find duplicate indexes (MySQL)
SELECT * FROM sys.schema_redundant_indexes;