Understanding SQL Indexes and Query Performance

Part 2 of 16 · ~2 min

What Problem Indexes Actually Solve

Strip the pay-band screen down to its simplest possible version — no salary range, no sorting, just "show me everyone in this department":

SELECT * FROM Employees WHERE dept = 'Facilities';

Six thousand rows come back. It takes four seconds.

That number should bother you, because 6,200 rows is nothing. The database is not slow at returning 6,200 rows. It is slow because of how it found them: with no index on dept, the only strategy available is to read all 2.4 million rows and check each one's dept value against 'Facilities'. That is a full table scan, and its defining property is that its cost has nothing whatsoever to do with how many rows match. Ask for a department with six thousand people or a department with one, and the database does the identical 2.4 million units of work either way. It is O(n) in the size of the table, not the answer.

An index is how you buy your way out of that.

CREATE INDEX idx_emp_dept ON Employees (dept);

What that statement builds is a second structure, separate from the table, holding every dept value in sorted order, each one paired with a pointer back to the row it came from. Because it is sorted, the database can find 'Facilities' in it by narrowing — check the middle, go left or right, repeat — rather than by looking at everything. A handful of steps instead of 2.4 million.

Run the query again and it comes back in about eight milliseconds.

That is the entire pitch for indexes, and it is worth stating plainly before we complicate it for the next fourteen chapters: an index trades storage and write speed for the ability to find rows without inspecting all of them. Everything that follows is detail about when that trade is worth making.

Now, two things to carry forward.

First, a promise: we are going to add four more indexes to this table over the next five chapters, and in chapter 12 we are going to add up what they cost. They are not free, the bill is real, and it arrives in a specific place.

Second, something you should try, because it will not do what you expect. Run that same query for the department we actually care about:

SELECT * FROM Employees WHERE dept = 'Sales';

The index exists. The column is indexed. And the timing barely moves — it is still seconds, not milliseconds. Nothing is broken, nothing is misconfigured, and the database is making the correct decision. Chapter 7 is where that gets explained. Hold onto it; it is the most useful surprise in this reference.