Database Indexing: How Indexes Actually Work, With Real Measured Numbers

Running the same lookup query against a 200,000-row table, once with no index and once after adding a single index on the searched column, produces a real, measured difference of roughly 268 times faster, not a marketing number, an actual timed result from SQLite’s own query planner. That gap is the entire reason indexing exists as a topic worth understanding properly rather than treating as a box to check once and forget about.

What’s less commonly understood, and what causes most of the real-world confusion around indexes, is that having an index doesn’t guarantee it actually gets used. A composite index built in the wrong column order, or a perfectly good index sitting unused because a query wraps the indexed column in a function, both produce a database quietly falling back to scanning every row anyway, with no error, no warning, just a slow query that looks identical on the surface to one that’s actually using its index correctly. This piece demonstrates both failure modes with real, measured numbers rather than asking you to take the theory on faith.

How an Index Actually Works

Most relational database indexes are built on a B-tree, a balanced tree structure that keeps values sorted and lets the database find a specific value, or a range of values, in a small, predictable number of steps rather than checking every row one by one. Instead of scanning a table’s full million rows to find the one matching a given email address, a B-tree index lets the database navigate down a small number of tree levels, typically no more than three or four even for a very large table, landing directly on the matching row’s location.

Without an index, the database has exactly one option for most queries: a full table scan, reading every single row in the table and checking each one against the query’s condition. This is the SCAN operation that shows up in a query plan when no usable index exists, and it’s precisely what an index exists to avoid, replacing it with a SEARCH operation that jumps directly to the relevant rows instead.

The Basic Case, Measured

Running a lookup by email against a 200,000-row users table with no index produces a query plan showing SCAN users, and a measured execution time of roughly 8.4 milliseconds. Adding a single index on the email column changes the query plan to SEARCH users USING INDEX idx_email (email=?), and the same exact query drops to roughly 0.03 milliseconds, a measured 268 times faster, for the identical query against the identical data, with the only change being the presence of one index.

-- Before: SCAN users (8.4ms)
SELECT * FROM users WHERE email = 'user150000@example.com';

-- After: CREATE INDEX idx_email ON users(email);
-- SEARCH users USING INDEX idx_email (email=?)  (0.03ms)

This gap widens, not narrows, as table size grows, since a full table scan’s cost grows linearly with the number of rows, while a B-tree index lookup’s cost grows only logarithmically, meaning the difference between a scan and a search becomes more dramatic, not less, on a table with millions of rows compared to the 200,000-row example measured here.

Composite Indexes and the Leftmost Prefix Rule

A composite index spans multiple columns together, and how the database can use it depends entirely on which columns a query actually filters by, and in what order those columns appear in the index definition. This is best shown directly: building an index on (customer_id, status) and running three different queries against the same 300,000-row orders table produces three genuinely different outcomes.

The third row is the one that surprises people who haven’t seen this demonstrated directly: the index on (customer_id, status) exists, and it’s completely ignored when the query only filters by status, the second column, falling all the way back to a full table scan despite an index technically covering that column. This is the leftmost prefix rule in action: a composite index can only be used efficiently for queries that filter on a contiguous prefix of its columns starting from the left, the first column alone, or the first and second together, but not the second column in isolation.

Choosing Column Order in a Composite Index

A reasonable general guideline is placing equality-filtered columns before range-filtered columns in a composite index, since a B-tree can use an equality match on a leading column and then efficiently narrow a range within that match on a following column, but a range condition on a leading column limits how effectively subsequent columns can be used within the index at all.

Selectivity, how much a given column narrows down the result set, matters too. A column like status with only four possible values narrows a large table down to roughly a quarter of its rows at best, while a column like customer_id with thousands of distinct values narrows things down far more precisely. Leading a composite index with the more selective column generally produces a more effective index, though the actual query patterns your application runs matter more than a general rule, since an index should ultimately be built around the specific filters your real queries actually use, not a selectivity calculation in isolation.

Why Wrapping a Column in a Function Defeats an Index

Running WHERE email = 'value' against an indexed email column uses the index directly, measured at roughly 0.025 milliseconds against a 200,000-row table. Running the logically similar WHERE LOWER(email) = 'value' against the exact same indexed column produces a full table scan instead, measured at roughly 24.2 milliseconds, nearly a thousand times slower for what looks like a nearly identical query.

-- Uses the index (0.025ms)
SELECT * FROM users WHERE email = 'user150000@example.com';

-- Ignores the index entirely (24.2ms, ~966x slower)
SELECT * FROM users WHERE LOWER(email) = 'user150000@example.com';

The index stores the column’s actual, unmodified values in sorted order. Once a query wraps that column in a function, LOWER(), a date extraction, string concatenation, the database can no longer directly compare the index’s stored values against the query’s condition, since the condition is now evaluating a computed result rather than the raw column value the index was built on. Some databases support function-based or expression indexes specifically to solve this, an index built directly on LOWER(email) rather than on email itself, which restores index usability for queries using that exact expression, but this requires deliberately creating that specific expression index, not something a database does automatically.

The practical takeaway: if a query needs case-insensitive matching regularly, either store data in a normalized, consistent case to begin with, or create an expression index matching the exact transformation the query applies, rather than relying on a plain column index to somehow cover a wrapped, transformed version of that column.

Covering Indexes

The earlier email lookup example’s query plan actually read SEARCH users USING COVERING INDEX idx_email, and that word “covering” is worth understanding specifically. A covering index contains every column a query needs, both the filter condition and anything being selected, meaning the database can answer the query directly from the index itself without ever needing to look up the corresponding full row in the table. This is faster still than a normal index search, which typically requires one additional step after finding a match in the index: fetching the actual full row from the table to retrieve any columns not present in the index.

Designing an index to cover a specific frequent query, by including the actual selected columns alongside the filtered ones, is a genuine, worthwhile optimization for a query that runs often enough to justify the extra index size, though it’s not something to apply reflexively to every index, since a wider covering index costs more to store and maintain than a narrower one built purely for filtering.

Reading EXPLAIN Output Across Databases

The examples in this piece use SQLite’s EXPLAIN QUERY PLAN syntax, which reports whether a query results in a SCAN or a SEARCH and which index, if any, is being used. PostgreSQL’s EXPLAIN ANALYZE provides considerably more detail, including actual execution time, estimated versus actual row counts, and whether a step is a Seq Scan (sequential scan, PostgreSQL’s equivalent of SQLite’s table scan) or an Index Scan or Index Only Scan (PostgreSQL’s term for a covering index lookup). MySQL’s EXPLAIN shows a similar structure, with a type column indicating ALL for a full table scan versus ref, range, or const for various levels of index usage, each database using its own terminology for fundamentally the same underlying distinction: is this query resolving via a targeted index lookup, or reading through rows one by one.

Running EXPLAIN against a slow query, in whichever specific syntax your database uses, is the direct, reliable way to confirm whether an index is actually being used, rather than assuming it is simply because the index exists in the schema. This is worth doing as a standard diagnostic step any time a query feels slower than expected, precisely because, as shown above, an index’s mere presence doesn’t guarantee any specific query is actually taking advantage of it.

When Not to Add an Index

Every index adds real, ongoing write cost, since an insert, update, or delete affecting an indexed column has to update that index’s structure in addition to the table’s own data, and a table with many indexes pays this cost on every single write, not just occasionally. A table that’s written to constantly but read from rarely can genuinely suffer from having too many indexes, where the cumulative write overhead outweighs the read benefit any individual index provides.

Indexing a column with very low selectivity, a boolean flag with only two possible values, or a status column with only a handful of distinct values spread evenly across a large table, often provides little real benefit, since the database may reasonably decide a full scan is still cheaper than an index lookup that would still need to examine a large fraction of the table’s rows regardless. This connects directly to the design decisions covered in this site’s database table and relationship planner, since thinking through which columns actually need indexing is part of the same schema design process, not an afterthought applied once performance problems already show up.

A table small enough that a full scan is already fast in absolute terms, a lookup table with a few hundred rows, rarely benefits meaningfully from an index at all, and adding one purely out of habit adds write overhead and schema complexity for a performance problem that doesn’t actually exist at that scale.

Beyond B-Trees: Other Index Types Worth Knowing

Hash indexes support exact-match equality lookups extremely efficiently but don’t support range queries or sorting at all, unlike a B-tree, which handles both equality and range conditions well. They’re a reasonable, narrower-purpose choice specifically for columns queried only by exact match and never by range or ordering.

GIN and GiST indexes in PostgreSQL support efficient querying inside more complex data types, specifically including JSONB columns and full-text search, which matters directly for the flexible-schema approach covered in this site’s SQL vs NoSQL comparison. A JSONB column without a GIN index still supports querying, but it falls back to scanning and parsing the JSON content of every row, while a properly configured GIN index lets PostgreSQL query specific keys inside that JSON structure with genuine index-backed efficiency, closing much of the performance gap that historically pushed people toward a dedicated document database for this kind of flexible data.

Real Scenarios

Common Mistakes

Adding an index and assuming the problem is solved without ever confirming via EXPLAIN that the specific slow query actually uses it is one of the most common gaps, and as demonstrated directly above, an index existing is genuinely no guarantee a given query benefits from it at all.

Building a composite index in an order that doesn’t match how the application actually queries the data, without checking the leftmost prefix rule against real query patterns, silently produces exactly the non-leading-column scenario measured earlier, a real index sitting unused for a real, common query.

Wrapping indexed columns in functions inside WHERE clauses, case-insensitive comparisons, date truncation, string manipulation, without either normalizing the underlying data or creating a matching expression index, reproduces the near-thousand-times slowdown measured directly above, often without anyone noticing until the table grows large enough for the scan to become genuinely painful.

And over-indexing a write-heavy table defensively, adding an index for every column that might someday be filtered on rather than the ones actually queried in practice, trades real, ongoing write performance for hypothetical future read convenience that may never materialize.

FAQ