Indexes and transactions

An index is an ordered structure of column values and row pointers that speeds up search. A transaction is a group of commands that run in full or not at all.

Why a query can be slow

When you ask the database for all the services of category 7, by default it does the simplest thing: it reads the table row by row and checks each one. This is called a full scan (in a query plan it’s called Seq Scan, short for sequential scan). On a hundred rows you won’t notice it. On a million rows you will: the database reads a million rows to find ten.

The index: the pointer at the back of a book

A good book has an alphabetical index at the back: “contract: 14, 87, 203”. You don’t leaf through the whole book for the word “contract”, you look it up in the index and go to the right pages. A database index works the same way: it’s a separate ordered structure of column values and pointers to rows.

Most often it’s a tree: on each level the values are laid out in order, and one step discards almost everything. A tree that branches hundreds of ways finds one row among millions in three or four steps. That’s why a search through an index barely slows down when the table grows a thousand times.

Play with the diagram. The table-size slider and the “how many rows match” choice show how many pages the database reads with an index and without one. Try the smallest tables and the most common values.

Index Transaction

Query: SELECT * FROM items WHERE category_id = 7. This is a model, not a measurement: a page holds 100 rows, and the index tree branches 200 ways.

Rows in the table: 100,000 How many rows match: one row0.1% of the rowsevery tenth row (10%)half of them (50%) Extra indexes: 0

• No index: read everything in order 1,000
• With an index: the tree (3) + the pages of the rows (100) 103

The planner will use the index. Few rows match and the table is large: walking the tree is faster than reading all 1,000 pages. That is 10 times less work.

The price of a write: inserting one row writes to the table, to the primary key index and to the extra indexes, of which there are 0 now. Writes in all: 2. Extra indexes slow writing down and take up space.

Text alternative: on a large table with a rare value, an index reads tens or hundreds of times fewer pages than scanning the whole table. On a small table, or with a common value, an index does not help, and the database reads the whole table. Every extra index makes writing more expensive.

What you should have noticed.

• The gain grows with the table. On a table of a hundred rows there’s no difference. On a million rows with a rare value, the index reads hundreds of times less.
• An index isn’t always needed. If half the table matches (gender, yes/no, “active”), it’s simpler to read it all: a trip through the index for every row costs more. The planner (the part of the database that chooses how to run a query) decides this itself.
• Every index costs something. An insert or an update has to change the table and every index. Five indexes mean five extra writes with every inquiry. They also take up space.

The rules that follow:

1. Build an index for a specific, frequent query that is slow, not “just in case” on every column.
2. A primary key and columns marked UNIQUE get an index automatically. But on foreign keys (category_id) PostgreSQL doesn’t create an index by itself, and joins on them often get faster after you add one by hand.
3. An index can be composite: ON items (category_id, day) helps queries that filter by category (and by date as well). The order of the columns matters: such an index serves queries on category_id and on the pair, but not queries on day alone.

Check yourself: is an index on a yes/no column worth building?

Almost never. The condition “active = true” matches about half the table, and it’s simpler to read the table straight through than to make a trip through the index for every row.

How to see what the database does: EXPLAIN

You don’t have to guess: before any query you can write the word EXPLAIN, and the database shows the plan, how it intends to run it.

EXPLAIN SELECT * FROM items WHERE category_id = 7;

In the plan of real PostgreSQL you’ll see Seq Scan on items (reads everything) or Index Scan using … on items (goes through the index), and also an estimate of the cost in arbitrary units. The EXPLAIN ANALYZE version also runs the query and measures the real time. In the practice below the sandbox prints a simplified model of a plan: how many rows it read. It’s a teaching interpreter, not real PostgreSQL, and the numbers in its plan are different, but you can see the same difference between scanning the whole table and using an index.

A transaction: all or nothing

Now the second topic, about crashes. Buying a ticket is two writes: take the seat off and record the order. If the server falls over between them, we get a seat taken with no order. The ticket is lost, and nobody will know. The two writes need to go through together or not at all.

That’s what a transaction does: a group of commands that the database treats as one indivisible action.

BEGIN;
UPDATE seats SET free = free - 1;
INSERT INTO orders (name, phone) VALUES ('…', '…');
COMMIT;   -- everything is final now

BEGIN opens the transaction, COMMIT confirms all the changes at once, and ROLLBACK cancels them all. If the server falls over in the middle, everything before COMMIT is rolled back on its own. Look at the “Transaction” tab of the diagram: the mode without a transaction leaves the data in a broken state, and the mode with a transaction doesn’t.

The properties of transactions are gathered into the word ACID:

• Atomicity: all or nothing.
• Consistency: after a transaction the rules of the data hold, foreign keys lead where they should, and no constraint is broken.
• Isolation: two simultaneous transactions don’t see each other’s unfinished changes. This is what kept two editors from overwriting each other in the first lesson.
• Durability: what was confirmed with COMMIT won’t vanish, even if the power goes off right afterwards.

Isolation has levels: the stricter it is, the safer, and the more often transactions have to wait for each other. By default PostgreSQL chooses a moderate one (READ COMMITTED), and the strictest is called SERIALIZABLE. On your site the moderate one is almost always enough.

One last detail, but it saves you in shops and in booking appointments. Two buyers press “buy” for the last seat at the same moment. You can’t first read the number of seats and then write “that number minus one”: between those steps the second buyer reads the same number. It’s safer in one statement: UPDATE seats SET free = free - 1 WHERE free > 0, and then check whether a row was changed. The condition and the change run indivisibly, and the second buyer is refused.

Practice

You’re in the era of 2022: sites now live on cloud databases, and designers think about load in advance. Take a table of two thousand services and speed up the query by category, then record an inquiry so that a crash can’t spoil it.

The page has three ready tables and five boxes. In the first, ask for the plan before the index; in the second, create an index and ask again (how many rows were read, write the numbers on the line under the box). Then in the third write a transaction of two inserts, in the fourth imitate a crash (no COMMIT), and in the fifth roll back and make sure there are no new inquiries.

What was wrong with MySQL: no transactions

For many years the most popular table engine in MySQL was MyISAM: fast, simple, and with no transactions and no foreign keys. Thousands of PHP sites ran on it, and a crash between two writes left half-assembled orders in the database. The InnoDB engine, which has all of this, became the default only in MySQL 5.5, at the end of 2010. Today a database that can do transactions is taken for granted, and nobody wants to explain to a customer where their ticket went.