Database Indexing: When It Helps and When It Hurts
How an index turns a full table scan into a short lookup, shown with real query plans before and after. Covers composite indexes, covering indexes, and the write cost people forget.
A database index is a separate sorted structure, usually a B-tree, that lets the engine find rows by a column in O(log n) instead of scanning the whole table in O(n). Interviewers expect the trade-off: indexes speed up reads that filter, join or sort on indexed columns, but every insert, update and delete must also update every index.
A database index is a separate sorted structure, usually a B-tree, that lets the engine find rows by a column without scanning the whole table. It speeds up reads that filter, join or sort on the indexed columns, and it slows down writes and uses disk space.
- Without an index, a lookup by column is a full table scan costing O(n); a B-tree index finds matches in O(log n) with a handful of page reads.
- In SQLite, adding an index on customer_id changed the query plan for 100,000 rows from SCAN orders to SEARCH orders USING INDEX idx_cust.
- A composite index on (a, b, c) serves queries filtering on a, on a and b, or on a, b and c, but not on b or c alone: the leftmost prefix rule.
- A covering index holds every column a query needs, so the engine answers from the index alone and never fetches the table row.
- An index cannot be used when the query applies a function to the column, uses a leading wildcard such as LIKE '%son', or compares mismatched types.
- Every INSERT adds an entry to every index on a table, so a table with ten indexes does eleven writes per insert.
01What an index is
Without an index, finding customer_id = 42 means reading every row and checking it. That is a full table scan, and it costs O(n). With 100 million rows, that is slow.
An index is like the index at the back of a book. It stores the values of the indexed column in sorted order, each with a pointer to its row. Because it is sorted, the database can binary-search it, or more exactly walk down a B-tree in a handful of page reads, and find the matches in O(log n).
The default index type in nearly every relational database (PostgreSQL, MySQL, SQLite, SQL Server, Oracle) is a B-tree or a close variant. Hash indexes exist too, and are only good for equality lookups.
02Seeing it work
import sqlite3
e = sqlite3.connect(':memory:')
e.execute("create table orders(id integer primary key, customer_id int, amount int)")
e.executemany("insert into orders(customer_id, amount) values (?, ?)",
[(i % 1000, i % 97) for i in range(100000)])
q = "select * from orders where customer_id = 42"
print(e.execute('explain query plan ' + q).fetchall())
e.execute("create index idx_cust on orders(customer_id)")
print(e.execute('explain query plan ' + q).fetchall())The first plan says SCAN orders, which is the full scan over 100,000 rows. After creating the index it says SEARCH orders USING INDEX idx_cust (customer_id=?). The query returns the same 100 rows, but it now reads only those.
In PostgreSQL and MySQL the command is EXPLAIN (or EXPLAIN ANALYZE to actually run the query and report timings). Learning to read a plan is the single most useful database skill for performance work.
03Composite indexes and the leftmost prefix
An index can cover several columns. It is sorted by the first column, then by the second within equal first values, like a phone book sorted by last name and then first name.
That means it helps when you filter on the first column, or on the first and second. It does not help a query on only the second column, just as a phone book does not help you find everyone named Priya.
e.execute("create index idx_ca on orders(customer_id, amount)")
print(e.execute("explain query plan select * from orders where amount = 5").fetchall())
# SCAN orders - the index starts with customer_id, so it cannot help hereColumn order matters. Put columns tested with equality first, and a column used for a range (>, <, BETWEEN) last. If you query by customer_id alone sometimes and by customer_id, amount other times, one composite index covers both, and a separate customer_id index is redundant.
04Covering indexes
print(e.execute("explain query plan select amount from orders "
"where customer_id = 42 and amount > 50").fetchall())
# SEARCH orders USING COVERING INDEX idx_ca (customer_id=? AND amount>?)The word COVERING means the answer came entirely from the index, since both customer_id and amount live there. The engine never goes back to fetch the full row. That saves a random read per match and can make a query several times faster.
The trade-off is a wider index. Some databases let you add non-key columns just to cover queries (INCLUDE in PostgreSQL and SQL Server).
05What stops an index being used
An index works on the stored value. If you change the value in the query, the engine cannot use the sorted order.
print(e.execute("explain query plan select * from orders where amount + 1 = 10").fetchall())
# SCAN ordersRewriting it as amount = 9 allows an index on amount to be used. The same happens with WHERE lower(email) = 'a@b.com' (fix: an index on the expression, which PostgreSQL supports), and WHERE name LIKE '%son' (a leading wildcard cannot use a B-tree, though LIKE 'son%' can).
A type mismatch, such as comparing a text column to a number, can force a conversion on every row and disable the index. And on tiny tables, or when a query returns a large fraction of the rows, the planner correctly prefers a scan, since jumping around via an index is slower than reading everything in order.
06The cost: writes and space
An index is not free. Each INSERT adds an entry to every index on the table. Each UPDATE of an indexed column moves entries. Each DELETE removes them. A table with ten indexes does eleven writes per insert.
Indexes also take disk space and memory, sometimes as much as the table itself.
So you index for the queries you actually run. Look at slow queries and their plans, add an index to fix one, and check the plan again. Drop indexes nothing uses. Columns with very few distinct values, like a boolean is_active, are usually poor candidates alone, because the index narrows the search very little.
07Common interview questions
Q: What data structure do indexes use?
A: Usually a B-tree (or B+ tree), which stays balanced and has high fan-out, so lookups touch very few disk pages.
Q: Clustered versus non-clustered index?
A: A clustered index defines the physical order of the table rows, so there is one per table (the primary key in InnoDB). A non-clustered index is a separate structure pointing to rows.
Q: Why would the database ignore my index?
A: A function on the column, a leading wildcard, a type mismatch, low selectivity, or stale statistics making a scan look cheaper.
Q: What is the leftmost prefix rule?
A: A composite index on (a, b, c) can serve queries filtering on a, on a and b, or on a, b and c, but not on b or c alone.
Q: Downside of too many indexes?
A: Slower writes, more storage, and more work for the planner.