Historical Context & Motivation
The challenge of efficiently retrieving data from large collections is as old as computing itself. When early relational database management systems emerged in the 1970s, researchers quickly recognized that the elegant declarative nature of SQL—specifying what data you want, not how to get it—created a fundamental performance problem. Without auxiliary data structures to guide lookups, the database engine had no choice but to perform a full table scan, reading every single row from disk to evaluate a query. As datasets grew from thousands to millions and then billions of rows, this linear-time approach became untenable, driving the development of database indexes—persistent, sorted data structures that let the engine locate rows in logarithmic or even constant time.
Despite decades of progress, the core question facing every database developer remains remarkably consistent: given a query with WHERE filters and JOIN conditions, which columns should be indexed, and why? This lesson develops the conceptual framework to answer that question.
Core Principles of Database Indexes
An index in a relational database is a separate data structure—maintained alongside the table—that maps column values to the physical locations (row IDs or page addresses) of the corresponding rows. Conceptually, it serves the same purpose as the index at the back of a textbook: instead of scanning every page, you consult a sorted lookup that directs you to the exact page you need. The database engine's query optimizer decides whether to use an index for a given query by estimating the cost of an index-assisted path versus a sequential scan and choosing the cheaper plan.
Selective Filtering
Join Acceleration
Sorted Access
Write-Side Trade-off
Covering Indexes
Visualizing Index Lookup vs. Full Scan
The following diagram contrasts the two fundamental access strategies a database engine can employ when evaluating a WHERE clause. On the left, a full table scan reads every page in the table sequentially, checking each row against the predicate. On the right, a B-tree index lookup traverses the tree from root to leaf in O(log n) steps, then follows a pointer directly to the matching data page. The visual contrast makes clear why indexes matter for selective queries.
The diagram illustrates the central insight: a full scan's cost grows linearly with table size, while an indexed lookup grows logarithmically. For a table with one million rows stored across roughly 125,000 data pages, a point query without an index reads all 125,000 pages; the same query with a B-tree index on the search column reads approximately 3–4 index pages plus 1 data page—a reduction of over four orders of magnitude. This difference only widens as the table grows, which is why understanding selectivity—the fraction of rows a predicate matches—is essential to deciding whether an index will help a particular query.
How the Optimizer Decides: Selectivity & Cost Estimation
The query optimizer does not blindly use every available index. It estimates the cost of alternative access plans and chooses the cheapest one. The key metric driving this decision is selectivity, defined as the fraction of rows satisfying a predicate. Low selectivity values (close to 0) indicate that the predicate is highly selective—few rows match—and indexes are beneficial. High selectivity values (close to 1) indicate that most rows match, making a sequential scan cheaper because index-assisted random I/O would touch nearly every data page anyway.
S is the selectivity of predicate P, |σ(P)| is the number of rows satisfying P, and |R| is the total number of rows in relation R. A selectivity of 0.001 means 0.1% of rows match—an excellent candidate for an index.f is the B-tree fanout (typically 100–500), N is the number of index entries, S is selectivity, and R_pp is rows per data page. The first term represents the tree traversal; the second represents the data-page fetches for matching rows.A critical threshold emerges from these formulas. When selectivity exceeds roughly 5–15% of the table (the exact threshold depends on clustering and buffer pool state), the optimizer typically switches to a full scan because the random I/O pattern of index lookups becomes more expensive than sequential reads. This is why indexes help selective queries and can actually hurt when the predicate matches a large fraction of the table. For joins, the analysis extends similarly: the join key index on the inner table is beneficial when each probe from the outer table matches only a small number of rows in the inner table.
When Filters and Joins Benefit from Indexes
Not all WHERE clauses and JOIN conditions benefit equally from indexes. The decision depends on predicate type, column cardinality, query access pattern, and the join algorithm the optimizer selects. The diagram below maps out these decision factors for both filter predicates and join conditions, showing when an index is likely helpful versus when it is likely ignored.
Filters: Key Patterns
Equality predicates (WHERE user_id = 42) on columns with high cardinality are the canonical index beneficiaries—the B-tree locates the single matching leaf entry in O(log n) time. Range predicates (WHERE created_at > '2024-01-01') also benefit, but only when the range is selective. If the range covers 30% or more of the data, the optimizer may determine that sequential I/O through a full scan is cheaper than the random I/O of index-assisted lookups. Two common pitfalls destroy index usability: applying a function to the indexed column (e.g., UPPER(email)) and using a leading wildcard in LIKE patterns ('%son'). In both cases, the engine cannot use the B-tree's sorted order because the search key has been transformed.
Joins: Key Patterns
For join operations, the optimizer's primary strategy is the index nested-loop join: for each row in the outer table, it uses an index on the inner table's join key to find matching rows. This works beautifully when the inner table has an index on the join column and each probe returns a small number of matches. In typical foreign-key relationships—such as orders.user_id → users.id—the primary key index on users.id makes each lookup a single B-tree traversal. When both sides are indexed, the engine may choose a merge join that walks both sorted indexes simultaneously. However, for large many-to-many joins or joins on computed expressions, a hash join that builds an in-memory hash table may outperform any index-based approach.
Worked Example: Choosing Indexes for a Query
Consider the following query on an e-commerce database. The orders table has 5 million rows and the customers table has 500,000 rows. We want to determine which indexes would make this query efficient.
SELECT c.name, o.total FROM customers c JOIN orders o ON c.id = o.customer_id WHERE o.order_date >= '2024-06-01' AND o.status = 'shipped';orders table: a range filter order_date >= '2024-06-01' and an equality filter status = 'shipped'. We need to assess the selectivity of each.(status, order_date) places the equality column first, allowing the B-tree to narrow to the 'shipped' entries, then range-scan within that subset by order_date. This column order is critical: the equality column first produces a tight range scan on the second column. Reversing the order ((order_date, status)) would work but less efficiently because the range predicate on the leading column prevents a tight bound on the second column.c.id = o.customer_id. The column customers.id is the primary key, so it is already indexed. The optimizer will likely scan the filtered orders (the smaller set after applying the WHERE clause) and use the PK index on customers to look up each customer's name. If orders.customer_id were not already indexed, an index there would help if the optimizer chose customers as the outer table.CREATE INDEX idx_orders_covering ON orders(status, order_date, customer_id, total); This eliminates the random I/O back to the heap for each matched row, since the index leaf pages contain all needed columns. The trade-off is a wider (and larger) index that is more expensive to maintain on writes.Index Strengths, Limitations, and Trade-offs
| Factor | Index Benefit | Index Cost / Limitation |
|---|---|---|
| Point lookups (equality) | O(log n) traversal to a single leaf entry; typically 3–4 I/O operations regardless of table size. | If the column has very low cardinality, index lookup returns too many rows and a scan is cheaper. |
| Range scans | B-tree leaf pages are linked, enabling efficient sequential traversal within a range. | Wide ranges (low selectivity) cause excessive random I/O to fetch scattered data pages. |
| Join acceleration | Index nested-loop join: each outer-row probe is O(log n). Merge join avoids sort when both sides are indexed. | Hash join may be faster for large, non-selective joins. Index NL join degrades when inner-table result per probe is large. |
| Write operations | Minimal impact with few indexes. Well-chosen indexes keep write amplification manageable. | Every INSERT/UPDATE/DELETE must maintain each affected index. Write-heavy workloads suffer from excessive indexing. |
| Storage overhead | Indexes are typically 10–30% of the table size, a modest cost for the read-speed benefits. | Many indexes on a large table can double or triple total storage. Wide covering indexes exacerbate this. |
| ORDER BY / GROUP BY | Index provides pre-sorted data, eliminating expensive sort operations in memory or on disk. | Only beneficial if the index order matches the query's ORDER BY clause exactly. |
Connection to Advanced Indexing Strategies
The conceptual framework of recognizing when filters and joins benefit from indexes extends naturally to more sophisticated indexing strategies encountered in advanced database courses and production systems. Understanding the basics prepares you to reason about these deeper topics.
| Concept (This Lesson) | Advanced Extension |
|---|---|
| Single-column B-tree index for equality/range filters | Composite indexes — multi-column indexes that obey the leftmost-prefix rule, enabling index access for compound WHERE clauses |
| Functions on columns prevent index use | Expression indexes (PostgreSQL) or functional indexes — index the result of a function, e.g., CREATE INDEX ON users (LOWER(email)) |
| Selectivity-based cost estimation | Adaptive query execution — runtime re-optimization when estimated cardinalities diverge from actual cardinalities (e.g., Spark AQE, Oracle adaptive plans) |
| B-tree for ordered data | LSM-trees and learned indexes — write-optimized structures (RocksDB, LevelDB) and ML-based indexes that predict key positions using regression models |
| Covering indexes to avoid heap access | Clustered indexes / IOT — the table data itself is stored in index order (SQL Server clustered index, Oracle Index-Organized Table), eliminating the heap entirely for the primary access path |
As you move into database internals courses, query optimization seminars, or real-world performance tuning roles, you will use execution plan analysis (the EXPLAIN or EXPLAIN ANALYZE command) to empirically verify whether the optimizer chose an index scan or a sequential scan, and to validate whether the selectivity estimates driving that choice are accurate. The conceptual reasoning covered here—evaluating predicate selectivity, column cardinality, and join-key index availability—is exactly the mental model that professional database engineers apply every day.
Practice Problems
is_active with values TRUE and FALSE) is generally not useful for a query like SELECT * FROM users WHERE is_active = TRUE. Under what special circumstance might it still help?SELECT * FROM products WHERE YEAR(release_date) = 2024 AND category_id = 7; The products table has an index on (category_id, release_date). Will the optimizer use this composite index fully, partially, or not at all? Explain your reasoning and suggest a rewrite that would allow full index utilization.SELECT d.name, COUNT(*) AS emp_count, AVG(e.salary) FROM departments d JOIN employees e ON d.id = e.dept_id WHERE e.hire_date >= '2020-01-01' GROUP BY d.name ORDER BY emp_count DESC; The employees table has 10 million rows; departments has 200 rows. Currently, the only indexes are the primary keys on each table. Propose a set of indexes and explain how each one helps the optimizer execute this query efficiently.Lesson Summary
Database indexes are auxiliary data structures—most commonly B-trees—that map column values to row locations, transforming O(N) full table scans into O(log N) index lookups. The query optimizer uses selectivity—the fraction of rows matching a predicate—to decide whether an index scan or a sequential scan is cheaper. Indexes are most beneficial for highly selective equality and range predicates on columns with high cardinality.
For join operations, indexes on the join key of the inner (probed) table enable efficient index nested-loop joins and merge joins. Common pitfalls include applying functions to indexed columns (breaking sargability), using leading wildcards in LIKE patterns, and indexing low-cardinality columns where selectivity is poor. The overarching principle is to index based on actual workload analysis, balancing read performance gains against write-side maintenance costs and storage overhead.