Indexes for Performance — Recognize when filters and joins benefit from indexes (conceptual) - SQL

SECTION 1

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.

1970 • Codd's Relational Model

Edgar F. Codd published his landmark paper describing the relational model. The model separated logical structure from physical storage, but the question of efficient access paths remained open.

1972 • B-Tree Invention

Rudolf Bayer and Edward McCreight introduced the B-tree, a self-balancing tree structure designed for block-oriented storage media. It became the backbone of database indexing.

1979 • Oracle & System R

The first commercial SQL databases—IBM's System R and Oracle V2—shipped with B-tree indexes and cost-based query optimizers, proving that indexes could make relational queries practical at scale.

1990s • Hash & Bitmap Indexes

As data warehousing grew, alternative index types—hash indexes for equality lookups and bitmap indexes for low-cardinality columns—expanded the optimizer's toolbox beyond B-trees.

2010s+ • Modern Adaptive Indexing

Columnar stores, learned indexes using machine learning models, and adaptive indexing techniques (e.g., database cracking) continue to push the boundary, but the fundamental conceptual question persists: which columns benefit from an index?

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.

SECTION 2

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

Indexes dramatically accelerate WHERE clauses that are highly selective—meaning they eliminate most rows. An index on a column with millions of distinct values allows the engine to jump directly to matching entries.

Join Acceleration

When two tables are joined, indexes on the join key columns allow the engine to use index-nested-loop or merge-join strategies instead of expensive Cartesian-product-style nested loops over raw data.

Sorted Access

B-tree indexes maintain key order, so ORDER BY and range queries (BETWEEN, <, >) can walk the index leaf pages sequentially rather than sorting the entire result set in memory.

Write-Side Trade-off

Every INSERT, UPDATE, or DELETE must also update every affected index. Indexes speed reads at the cost of slower writes and additional storage, so indexing every column is counterproductive.

Covering Indexes

When an index contains all columns a query references, the engine satisfies the query entirely from the index without touching the base table—an index-only scan that eliminates random I/O to the heap.

✦

KEY TAKEAWAY

Think of a database index like a library's card catalog. Without it, finding a specific book means walking every aisle and scanning every shelf—a full table scan. With the catalog (index), you look up the Dewey Decimal number and proceed directly to the shelf. The catalog takes space and must be updated whenever books are added or removed, but for a library of millions of books, the time savings on lookups far outweigh the maintenance cost. The key insight is that indexes are most valuable when your query targets a small fraction of the total collection.

SECTION 3

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.

Left: a full table scan reads every data page sequentially. Right: a B-tree index traverses from root to leaf (typically 3–4 levels for millions of rows) and follows a single pointer to the exact data page. The ✓ marks the matching row; ✗ marks non-matching rows that the scan must still examine.

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.

SECTION 4

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.

SELECTIVITY

S = |σ(P)| / |R|

Where 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.

INDEX LOOKUP COST (SIMPLIFIED)

C_index ≈ ⌈log_f(N)⌉ + ⌈S × N / R_pp⌉

Where 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.

FULL SCAN COST

C_scan = ⌈|R| / R_pp⌉

The scan cost is simply the total number of data pages, since every page is read once sequentially. The optimizer chooses the index plan when C_index < C_scan.

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.

ℹ

Cardinality vs. Selectivity

The optimizer uses statistics (histograms, distinct-value counts) to estimate selectivity. Cardinality refers to the number of distinct values in a column. A column with high cardinality (e.g., a primary key with 1 million distinct values) produces highly selective equality predicates (S ≈ 1/1,000,000). A column with low cardinality (e.g., a boolean flag with 2 distinct values) produces unselective predicates (S ≈ 0.5), making an index on that column rarely useful for equality filters.

SECTION 5

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.

The decision map partitions common filter and join patterns into three zones: green (✓) indicates that an index will almost certainly be used, amber (⚠) means the optimizer may or may not choose the index depending on statistics, and red (✗) means the index is unusable or a scan is cheaper. Notice that functions applied to indexed columns and leading wildcards both prevent B-tree usage.

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.

SECTION 6

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.

📝

Query Under Analysis

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';

Index Selection Analysis

1
Step 1 — Identify Filter Predicates

The WHERE clause contains two predicates on the orders table: a range filter order_date >= '2024-06-01' and an equality filter status = 'shipped'. We need to assess the selectivity of each.

Two filter predicates identified on orders table.
2
Step 2 — Assess Selectivity of Each Predicate

Assume order_date spans 5 years, so the last ~7 months covers roughly 12% of rows (S ≈ 0.12)—moderately selective. The status column has 4 distinct values (pending, processing, shipped, cancelled), so 'shipped' has S ≈ 0.25—poor selectivity alone. However, the combined selectivity is approximately S₁ × S₂ ≈ 0.12 × 0.25 = 0.03, meaning about 3% of rows match both predicates.

Combined selectivity ≈ 3% — highly selective, strong index candidate.
3
Step 3 — Choose Index Columns for Filters

A composite index on (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.

Recommended: CREATE INDEX idx_orders_status_date ON orders(status, order_date);
4
Step 4 — Identify Join Predicate and Index Need

The join condition is 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.

Join is covered by the existing PK index on customers.id. Optionally add index on orders(customer_id) if reverse join order is possible.
5
Step 5 — Consider a Covering Index

If we extend the composite index to include all columns the query reads from orders, we can achieve an index-only scan: 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.

Covering index eliminates heap lookups for matched rows, giving maximum read performance at the cost of additional storage and write overhead.

SECTION 7

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.

Index benefit/cost analysis across common operations

✦

KEY TAKEAWAY

Indexes in database systems are analogous to caches in computer architecture: they trade space and maintenance overhead for dramatically faster reads on predictable access patterns. Just as a CPU cache is most effective when the program exhibits strong locality of reference, a database index is most effective when queries consistently target a small, predictable subset of rows. Over-indexing is like over-provisioning cache lines for data that will never be reused—it wastes resources and slows down the write path. The art is in indexing precisely the columns that your actual query workload filters and joins on.

SECTION 8

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

From conceptual foundations to advanced indexing strategies

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.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain why an index on a boolean column (e.g., 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?

Show answer

A boolean column has only two distinct values, giving each value a selectivity of roughly 50%. At that selectivity, an index-assisted lookup would touch approximately half of all data pages via random I/O, which is far more expensive than a single sequential full-table scan. The optimizer will therefore choose the scan. However, if the data is heavily skewed—say 99% of users are active and only 1% are inactive—then filtering for is_active = FALSE achieves roughly 1% selectivity, and the index could be useful for that specific predicate value. Some databases also support partial indexes (e.g., CREATE INDEX ON users(id) WHERE is_active = FALSE) which index only the rare case, keeping the structure small and efficient.

Question 2: BASIC CALCULATION

A table has 2,000,000 rows stored across 250,000 data pages (8 rows per page). A B-tree index on a unique column has a fanout of 200. How many page reads are required for (a) a full table scan to find one specific row, and (b) an index lookup for that same row? Assume the B-tree height is ⌈log₂₀₀(2,000,000)⌉.

Show answer

For the full table scan, the engine must read all 250,000 data pages sequentially, so the cost is 250,000 page reads. For the index lookup, the B-tree height is ⌈log₂₀₀(2,000,000)⌉. Since 200² = 40,000 and 200³ = 8,000,000, we get ⌈log₂₀₀(2,000,000)⌉ = 3 levels. Traversing root → branch → leaf requires 3 index page reads, plus 1 data page read to fetch the actual row, giving a total of 4 page reads. The index lookup is approximately 62,500 times more efficient than the full scan for this point query—a dramatic demonstration of why indexes matter on large tables with selective predicates.

Question 3: INTERMEDIATE

Consider the query: 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.

Show answer

The optimizer can use the first column of the composite index (category_id = 7) because it is an equality predicate on the leading column. However, the second predicate applies the YEAR() function to release_date, which transforms the column value and prevents the B-tree from using the sorted order on release_date. So the index is only partially used—the engine navigates to category_id = 7 entries but must scan all of them to evaluate the YEAR() function. To enable full index utilization, rewrite the predicate as a range: WHERE category_id = 7 AND release_date >= '2024-01-01' AND release_date < '2025-01-01'. This allows the optimizer to use both columns of the composite index: it navigates to category_id = 7, then performs a tight range scan on release_date within that partition. This is a practical example of why sargable (Search ARGument ABLE) predicates are essential for index utilization.

Question 4: APPLIED

You are tuning a reporting query on a production system:

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.

Show answer

First, consider the filter: hire_date >= '2020-01-01' on the employees table. If this selects about 40% of rows (the last ~5 of 12 years), it is marginally selective. However, combining the filter with the join will narrow results significantly. The key index to create is a composite index on employees: CREATE INDEX idx_emp_hiredate_dept ON employees(hire_date, dept_id, salary). This enables a range scan starting at '2020-01-01', and because dept_id and salary are included, it becomes a covering index—no heap access needed. The departments.id primary key index already supports the join lookup when the optimizer probes from the filtered employees to departments. Since departments is tiny (200 rows), the optimizer may hash it into memory regardless. Finally, adding CREATE INDEX idx_emp_dept_hire ON employees(dept_id, hire_date, salary) could help if the optimizer prefers to drive from departments: for each of the 200 departments, it would range-scan the employees index to find hires after 2020. This alternative composite index with dept_id leading could enable a more efficient group-by strategy. The choice between these depends on actual data distribution, which EXPLAIN ANALYZE would reveal.

Question 5: CRITICAL THINKING

A colleague argues: "We should index every column that ever appears in a WHERE clause or JOIN condition to maximize query performance." Construct a rigorous counter-argument. Address at least three distinct reasons why this blanket strategy is suboptimal, and propose a principled methodology for deciding which indexes to create.

Show answer

While the intention is understandable, indexing every filtered/joined column is counterproductive for several reasons. First, write amplification: each INSERT must update every index on the table, and each UPDATE to an indexed column triggers an index modification. On write-heavy tables (e.g., logging, event tracking), the cumulative overhead of maintaining dozens of indexes can degrade INSERT throughput by orders of magnitude. Second, storage cost: indexes consume disk space proportional to the number of indexed columns and rows. Over-indexing can double or triple the storage footprint of a table, impacting backups, replication lag, and memory pressure in the buffer pool—since index pages compete with data pages for cache residency. Third, optimizer confusion: while modern optimizers are sophisticated, an abundance of overlapping indexes increases plan search space and can occasionally lead to suboptimal plan selection, especially when statistics are stale. A principled methodology involves: (1) analyzing the actual query workload using slow-query logs or pg_stat_statements to identify the most frequently executed and slowest queries, (2) running EXPLAIN on those queries to determine whether they perform full scans on large tables, (3) evaluating the selectivity of each predicate and the cardinality of each join to prioritize index candidates, (4) preferring composite indexes that serve multiple queries over single-column indexes, and (5) monitoring index usage statistics (e.g., pg_stat_user_indexes in PostgreSQL) to drop indexes that are never used. This evidence-driven approach indexes what matters and avoids the maintenance tax on the write path.

SUMMARY

Lesson Summary

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.