Module 7 closed with a change of question. For seven modules the question has been does this return what I want?; from here on it's how long does it take?. And the answer almost always runs through the same object: the index, an auxiliary data structure the engine maintains alongside the table and that turns "look at every row until you find it" into "go straight to where it is".

In this lesson you won't create a single index yet. First you have to understand what problem they solve and how they work inside, because almost every mistake made with indexes —creating the useless ones, not creating the necessary ones, being surprised that the engine ignores them— comes from not having the right mental model. By the end you'll know why searching among 20 million rows can cost four disk accesses, why LIKE '%organic%' can't take advantage of any of them, and —what will surprise you most— which indexes GreenStore already has without anybody creating them and which ones it's missing.

1. The book-index analogy, and where it breaks down
2. How the engine reads a table with no index
3. The B-tree structure
4. What an index really stores: the key and the pointer
5. Index Scan, Index Only Scan and covering indexes
6. What a B-tree speeds up and what it doesn't
7. The indexes GreenStore already has
8. The hole: PostgreSQL doesn't index foreign keys
9. The price of an index
10. Common Mistakes and Tips
11. Exercises
12. Conclusion

You have an 800-page manual and you want to know where HAVING is discussed. There are two ways:

• Leaf through the whole book until you find it. It always works, and it costs 800 pages.
• Go to the alphabetical index at the back, look up "HAVING" —which is sorted, so you locate it in seconds— and read "p. 412".

A book's index is exactly a database index: a sorted copy of part of the information (the terms) together with a pointer to where the rest is (the page). It doesn't contain the book; it contains just enough to jump into it.

The analogy is a good one, but it's worth marking where it breaks down, because that's precisely where the interesting decisions begin:

Those five differences are, in fact, the script of the whole module. The fourth is the hardest to accept: creating an index doesn't guarantee it gets used. You'll see it demonstrated over GreenStore in lesson 08-05.

With no index there's only one possible strategy: the sequential scan (Seq Scan in PostgreSQL jargon). The engine reads the table block by block from the start, checks the WHERE on each row and discards the ones that don't qualify.

Seven rows out of twenty. To hand them to you, the engine has read all twenty. With 20 rows that's free. The key is how it scales:

(Intuition figures, not laboratory ones: the exact number depends on row width, on the cache and on the disk. What matters is the shape of the two columns.)

The Seq Scan column grows linearly: twice the rows, twice the time. The index column grows logarithmically: multiplying the rows by a thousand adds one access. That difference between O(n) and O(log n) is the whole module in one line, and it explains why a query that runs perfectly with development data can bring production down six months later.

A Seq Scan isn't a mistake. It's the right strategy when the table is small or when you're going to return a good part of it. You'll see it in detail in 08-03 and demonstrated in 08-05.

The default index in PostgreSQL —and in every relational engine— is the B-tree (balanced tree). It's a sorted tree with three kinds of node:

• Root: a single node, the entry point of every search.
• Internal nodes: they contain separator values and pointers to nodes on the level below. They say "the values lower than 5.50 are over here".
• Leaves: they contain the key's actual values, each with the pointer to the table row. On top of that, the leaves are linked to each other in order, which makes it possible to walk a range without climbing back up the tree.

This is what a B-tree index over products.price would look like, with the catalogue's 20 prices spread across five leaves of four entries each:

Look for the €12.50 product: you come in through the root, you see that 12.50 sits between 9.90 and 14.25, you go down to leaf 4 and there it is. Two accesses, not twenty. And for WHERE price BETWEEN 9 AND 15 you come in once at 9.00 and then follow the dotted arrows between leaves until you go past 15: that's what makes a B-tree just as good for ranges as for equalities.

In PostgreSQL each node of the tree is an 8 kB page. A lot of entries fit on that page: for a 4-byte integer key, on the order of 250 usable entries once the headers and the free margin the engine leaves are discounted. That number is called the branching factor (fanout), and it's what makes the tree wide and short instead of narrow and tall.

Read it slowly, because it's the figure worth memorising from the module: a table of fifteen million rows is traversed in three accesses. And of those three, the upper levels are almost always in cache because every query goes through them, so in practice the real cost is usually one disk access, or none.

The fanout depends on the width of the key: indexing an INTEGER gives very wide trees; indexing a VARCHAR(150) with long names gives entries five times as big, fewer entries per page and, with the same rows, one extra level of height. It's the first reason why indexing narrow columns comes cheaper.

The "balanced" in the name means that all the leaves sit at the same depth, and the engine keeps it that way by splitting and merging pages on insert and delete. That's why there are no "unbalanced indexes" that need rebuilding by hand: the cost of keeping them balanced is paid on every write, and that's where a good part of the price section 9 talks about comes from.

A leaf entry doesn't contain the row. It contains two things:

1. The key's value (12.50).
2. A physical pointer to the row, which in PostgreSQL is called the ctid and is a pair (block, position within the block).

The ctid is a system column you can query:

All twenty products are in block 0: they fit comfortably in a single 8 kB page. That apparently incidental detail is the reason no index is any use at all on this table, and it'll come back in section 7 and in 08-05.

Careful: the ctid isn't a stable identifier. It changes when the row is updated, because PostgreSQL writes a new version somewhere else. Never store it in a column or use it as a key: that's what id is for. Here we're only using it to look at the machinery from the inside.

The consequence of the index storing a pointer and not the row is important: an index lookup involves two steps. First you go down the tree to the leaf and get the ctid; then you have to go to the table (the heap) to read the row and pick up the columns you asked for. That second step is called a heap fetch, and if your query returns a thousand rows, that's a thousand jumps to possibly scattered positions on disk.

Two of the plan nodes you'll see constantly in 08-05 come out of that:

The second is the jackpot: the whole heap fetch is saved. And it's achieved with what's called a covering index: an index that covers every column the query needs, both for filtering and for displaying.

In lesson 08-02 you'll see how to build covering indexes on purpose with the INCLUDE clause, which adds columns to the index just to be read, without using them for sorting.

An honest nuance: in PostgreSQL an Index Only Scan doesn't always avoid 100 % of the table accesses. The index doesn't know whether a row is visible to your session, so it consults an auxiliary map (the visibility map) and, for the blocks marked as not entirely clean, it does go to the heap. That shows up in the plan as Heap Fetches: N. If that number is high, the table needs maintenance (VACUUM), and that's covered in 08-05.

A B-tree is sorted. Anything that can be expressed as "go to a point in the order and move forward" it solves; everything else, it doesn't. This table closes three promises the course has been carrying since modules 2, 4 and 6:

The four red rows at the end all have the same cause: to use an index, the column has to appear bare on one side of the comparison. The moment you wrap it in a function, in a calculation or in a leading wildcard, the engine can no longer translate your condition into "a point in the order and move forward".

Two practical consequences you'll resolve in the coming lessons, not now:

• The conditions in the red rows can almost always be rewritten. EXTRACT(YEAR FROM order_date) = 2025 is identical to order_date >= '2025-01-01' AND order_date < '2026-01-01', and this second version does use the index: they're the same 16 orders from 2025. That rewrite has a name —sargability— and it's the heart of lesson 08-04.
• When they can't be rewritten, there are specific tools: an index on the expression for LOWER(email) (08-02) and the pg_trgm extension with a GIN index for the LIKE '%organic%' that 04-01 left pending (08-03).

Here comes the surprise: you've never written a CREATE INDEX and GreenStore already has eleven indexes. In 05-01 it was mentioned in passing that PRIMARY KEY and UNIQUE "are implemented by creating an index underneath, and the structures are covered in module 8". The moment has come.

A single index, products_pkey, with btree written out explicitly: it's section 3's structure. To see them all at once, the pg_indexes catalog view:

Eleven indexes: nine from the primary keys and two from the UNIQUE constraints on categories.name and customers.email. They're all UNIQUE INDEX ... USING btree, and they all exist because a constraint needs them: the only reasonable way of checking "this value isn't repeated" before accepting an INSERT is to have the values sorted. That's why in PostgreSQL the constraint and the index are the same physical object, and that's why an INSERT into customers with a duplicate email fails in microseconds rather than by reading the 15 rows.

This also explains why WHERE c.id = 7 or WHERE c.email = 'lucia.martinez@example.com' have always been fast in the course, even though nobody had mentioned indexes.

And now the most valuable point of the lesson. Look at the list again: products.category_id doesn't appear. Nor does orders.customer_id. Nor order_lines.order_id.

PostgreSQL creates an index automatically for PRIMARY KEY and for UNIQUE, but NOT for foreign keys. The index exists on the referenced side (the parent's PK), never on the referencing side (the child column).

These are GreenStore's eleven foreign keys, all of them unindexed:

Why it hurts, on two fronts.

First, the JOINs. The course's canonical query joins order_lines with orders, customers and products. Each ON ol.order_id = o.id can be resolved in two directions: looking up orders by id (indexed, fast) or looking up order_lines by order_id (unindexed, full scan). With 47 lines it makes no difference; with 20 million, "the lines of order 8,412,006" with no index means reading all 20 million.

Second, and less well known: deletes on the parent. When you run DELETE FROM orders WHERE id = 5, PostgreSQL is obliged to check every table referencing orders —order_lines and returns— to apply the CASCADE. If those columns have no index, every order deletion triggers a full scan of the child tables. It's one of the classic causes of "deleting a row takes 40 seconds" in large databases, and the engine doesn't warn you: the slow query isn't the one you wrote.

Dialect note: this isn't the case in every engine. MySQL with InnoDB creates an index automatically over every foreign-key column if a suitable one doesn't already exist, and in fact it requires one. Oracle and SQL Server behave like PostgreSQL: they don't create it, and their official documentation recommends creating it by hand. If you're coming from MySQL, this is probably the performance difference that will bite you hardest when migrating.

The practical rule you take away —and that you'll apply in the next lesson— is a short one: almost every foreign-key column wants its index. "Almost", because there are exceptions (a tiny child table, or an FK you never filter or delete by), and those exceptions are 08-03's subject.

If indexes were free, the answer would be to index everything. They aren't, and it's worth keeping the cost in mind from the first minute:

The consequence is that an index is a bet: you speed up the reads that use it in exchange for making every write on the table more expensive. On a table read a thousand times per write, the bet is excellent. On an event-log table written to constantly and queried once a month, it's a bad deal. Quantifying that bet —and the list of cases in which you should not index— is all of lesson 08-03.

• Believing that creating an index guarantees it gets used. The planner decides. With small tables, with poorly selective filters or with stale statistics, it'll choose the Seq Scan and it'll be right.
• Thinking the index contains the row. It contains the key and a pointer. Hence the second access to the table, the Index Scan against the Index Only Scan and the very existence of covering indexes.
• Assuming foreign keys are indexed. In PostgreSQL they aren't. It's the most profitable discovery in this lesson.
• Indexing a column and going on filtering with a function on top of it. LOWER(email) doesn't use the index on email. Either you rewrite the query, or you create an index on the expression (08-02).
• Expecting miracles from LIKE '%text%'. No B-tree can help you without a prefix. The solution exists, but it's another family of indexes (08-03).
• Confusing the ctid with an identifier. It changes with every UPDATE. To identify a row there's its primary key.
• Tip: think in terms of "a point in the order and move forward". If your condition can be translated into that, the index is useful. If not, it isn't. It's the best mental filter there is for predicting a plan without running it.
• Tip: always look at \d table before creating an index. It's the quickest way of discovering an equivalent one already exists.
• Tip: memorise the height table. Knowing that 15 million rows are 3 accesses saves you whole arguments about whether "the table is too big to search".

For each condition, say whether a B-tree index on the column involved could be used, and justify it in one sentence.

Without running anything, answer:

1. How many indexes does the order_lines table have today and on which columns?
2. Which of its columns are foreign keys and which of those are indexed?
3. DELETE FROM orders WHERE id = 5 cascaded and deleted three lines in lesson 01-06. Describe what the engine has to do in order_lines to locate them, and how it would change with 20 million lines.

A colleague proposes: "Since indexes speed up queries, let's create one on every column of orders: customer_id, employee_id, order_date, status, payment_method and shipping_cost."

1. Give two technical arguments against, using what you saw in sections 6 and 9.
2. Which of those six columns strike you as reasonable candidates and which don't? Justify it with the nature of GreenStore's data.

Solution 1

Solution 2

1. Just one: order_lines_pkey, a unique B-tree index on id, created by the PRIMARY KEY.

2. It has two foreign keys, order_id (→ orders, ON DELETE CASCADE) and product_id (→ products, ON DELETE RESTRICT), and neither of them is indexed. It's the highest-volume table in the schema and the one that appears in practically every JOIN in the course: it's the first index candidate in all of GreenStore.

3. To apply the CASCADE, the engine has to find every row with order_id = 5. With no index on order_id, the only way is a full sequential scan of order_lines: read the 47 rows, keep the 3 and delete them. With 20 million lines, that same DELETE of one row in orders would force 20 million rows to be read —and as many again in returns, which also references orders with CASCADE. The slow query wouldn't be the one you wrote, but the integrity check it triggers: that's why this case is so hard to diagnose without EXPLAIN (08-05).

Solution 3

1. Two arguments:

• Every index makes all the table's writes more expensive. With six indexes, an INSERT into orders goes from updating one structure (the PK) to updating seven. A Christmas peak in orders turns into a write problem that didn't exist before.
• Several of those indexes would never be used. An index is only useful if the planner chooses it, and for that the filter has to be selective. status has 5 values across 20 orders and payment_method has 4: filtering by one of them returns a huge fraction of the table, and reading it all sequentially is cheaper than going to the index and back to the table row by row.

2. How they split:

Notice the criterion peeking through: you don't index a column because it exists, but because there are real queries filtering, joining or sorting by it and returning few rows. That criterion is the thread running through the next three lessons.

You now have the complete mental model:

• An index is a sorted copy of a column plus a pointer to the row, like a book's alphabetical index, except that there can be many, they have to be kept alive and the planner uses them, not you.
• With no index there's only the Seq Scan, whose cost grows linearly. A B-tree grows logarithmically: with a fanout of around 250 entries per page, 15 million rows fit in 3 levels, and the upper levels live in cache.
• The index stores the key and the ctid, so normally a second access to the table is needed: that separates the Index Scan from the Index Only Scan, and from there the concept of a covering index is born.
• A B-tree is good for equalities, ranges, IN, LIKE 'abc%' prefixes, ORDER BY, MIN and MAX; it's no good for LIKE '%abc', for functions or calculations on the filtered column, or for <>. The column has to appear bare in the condition.
• GreenStore already has eleven indexes nobody created —nine from the PKs and two from the UNIQUE constraints— and it's missing the ones for its eleven foreign keys, because PostgreSQL doesn't index them automatically (MySQL/InnoDB does). That penalises the JOINs and, very particularly, the cascading deletes.
• An index is paid for in space and in slower writes, so it's a bet you have to win.

In lesson 08-02, Creating and Managing Indexes, you move into action: the full syntax of CREATE INDEX, the CONCURRENTLY variant that doesn't lock the table, composite indexes and the leftmost-prefix rule that decides what order to put the columns in, partial indexes that only index the rows you care about, indexes on expressions that close the LOWER(email) problem, and how to list them, measure their size and spot the ones nobody uses. Starting, of course, with the eleven foreign keys you've just discovered uncovered.