Indexing & Query
Reasoning, making it fast

Across the first five modules you learned to produce the right answer: select and filter, join tables, group and aggregate, and slide window functions over ordered rows. On a toy schema with six employees, every one of those queries returns instantly. That is the trap. The same query against millions of rows can take milliseconds or minutes depending on a single decision: whether the database can use an index or has to read the entire table.

This module is the one that makes you sound senior. Anyone can memorize JOIN syntax. The line that separates L3 from L1 is being able to look at a slow query, say "let me check the plan," read an EXPLAIN ANALYZE output, and explain precisely why it is slow and what you would change. Meet Maya, a new analyst at our small company (the same departments, employees, and orders schema you have used all along). Her toy queries always returned instantly, until the orders table grew into tens of millions of rows. That is where every idea below earns its keep, and where we will follow her.

Maya's first slow query is simple: she wants one employee's orders.

SELECT * FROM orders WHERE emp_id = 42;

How does the database actually find those rows? Without help, it does the only thing it can: it starts at the first row and reads every single row in the table, testing emp_id = 42 on each one and keeping the matches. This is a sequential scan (Postgres calls it a Seq Scan). If the table has 20 million rows, the database inspects all 20 million to find maybe a dozen matching orders.

The cost of a sequential scan grows linearly with table size: this is O(n) work. For a small table that is completely fine and often the fastest option, since reading a few hundred rows straight off disk beats any cleverness. That is why Maya never noticed it before. But as the row count climbs into the millions, "look at everything" becomes catastrophic, and it gets worse every time the table grows.

Think of the index at the back of a physical textbook. To find every page that mentions "deadlock," you do not read the whole book. You flip to the alphabetical index, jump straight to D, and it hands you the page numbers. The index is a sorted structure that maps a value to where the real content lives. A database index is exactly this idea, made out of a tree.

The default index type in PostgreSQL is a B-tree: a sorted, balanced tree. Each node holds indexed values in sorted order plus pointers. Internal nodes point to child nodes, and leaf nodes point to the actual table rows. Because it stays balanced, every leaf sits at the same depth, so any lookup touches the same small number of nodes from root to leaf.

The payoff is the depth. A balanced tree finding a value is O(log n), not O(n). For a table of 20 million rows, that is roughly four hops from root to leaf instead of 20 million comparisons. That is the entire reason indexes exist: they convert "read everything" into "navigate a sorted tree." Because the tree is sorted, the same structure also serves range scans (>, BETWEEN) and ordered reads, not just exact matches.

Creating one is a single statement. You name the table and the column(s) to index:

-- speed up lookups and joins on emp_id
CREATE INDEX idx_orders_emp ON orders(emp_id);

-- a naming convention helps: idx_<table>_<column(s)>
CREATE INDEX idx_orders_date ON orders(order_date);

Once idx_orders_emp exists, the database can use it for any query whose work matches the sorted shape of the index. A single-column B-tree on emp_id can accelerate all of these:

Notice the pattern: an index helps when your query needs the data in the order the index stores it, whether to find a value, a range of values, or to return them sorted. That single observation drives everything in the rest of this module.

If indexes only made queries faster, you would index every column and be done. The reason you do not is the central trade-off of this entire module.

Walk through it concretely. Say orders has five indexes. Inserting one new order is no longer a single write. The database appends the row to the table and inserts the new key into all five B-trees, each of which may need to rebalance. A write-heavy table drowning in indexes can become slower to write than it ever gained in read speed.

This reframes the question. "Should I add an index?" is really a cost-benefit decision: how often is this column queried (the benefit) versus how often is this table written, and how much disk can I spend (the cost). An index on a column nobody filters by is pure overhead, since it slows every write and helps no read. Unused indexes are a real, common problem, not a hypothetical.

Maya never has to guess whether a query uses an index. She can ask the database to show her its plan. This is the single most practical performance skill in the whole course.

EXPLAIN shows the query plan the planner intends to run, with cost estimates, without executing it. EXPLAIN ANALYZE goes further: it actually runs the query and reports the real row counts and timing alongside the estimates. When you are debugging slowness, you almost always want ANALYZE.

EXPLAIN ANALYZE SELECT * FROM orders WHERE emp_id = 42;

Seq Scan on orders  (cost=0.00..358000.00 rows=11 width=64)
                    (actual time=0.41..842.6 rows=12 loops=1)
  Filter: (emp_id = 42)
  Rows Removed by Filter: 19999988
Planning Time: 0.12 ms
Execution Time: 843.1 ms

Maya reads that plan top-down. Seq Scan means it read the whole table. cost=0.00..358000.00 is the planner's estimate (startup cost..total cost, in arbitrary units); rows=11 is its estimate of matches; actual time and rows=12 are what really happened. The damning line is Rows Removed by Filter: 19999988: the database inspected 20 million rows to return 12. So she adds the index and looks again.

EXPLAIN ANALYZE SELECT * FROM orders WHERE emp_id = 42;

Index Scan using idx_orders_emp on orders
        (cost=0.43..39.7 rows=11 width=64)
        (actual time=0.03..0.06 rows=12 loops=1)
  Index Cond: (emp_id = 42)
Planning Time: 0.20 ms
Execution Time: 0.09 ms

Same query, same result, but 843 ms became 0.09 ms, roughly ten-thousand-fold. The plan now says Index Scan, the estimated total cost collapsed from 358000 to 39.7, and there is no "Rows Removed by Filter" line because the index went straight to the matching rows. Maya's hang is gone.

The three scan types you will see

Here is the trap that catches even people who have indexed correctly. A week later Maya adds an index, writes a WHERE on that exact column, and the query still does a Seq Scan. The cause is almost always sargability (a contraction of "Search ARGument ABLE"): whether your condition is written in a form the index can actually use.

The rule is simple and follows directly from the B-tree model. The index stores the raw column value. The moment you wrap the column in a function or arithmetic, the index no longer holds the value you are asking about, so it cannot help, and the planner falls back to a full scan.

-- NON-sargable: function on the column → Seq Scan
SELECT * FROM employees WHERE LOWER(name) = 'alice';

-- NON-sargable: arithmetic moves the column out of reach
SELECT * FROM employees WHERE salary + 1000 > 50000;

-- SARGABLE rewrite: move the math to the constant side
SELECT * FROM employees WHERE salary > 49000;

-- SARGABLE fix for LOWER(): build an expression index
CREATE INDEX idx_emp_lname ON employees(LOWER(name));
-- now WHERE LOWER(name) = 'alice' CAN use the index

Two ways out. Rewrite the condition so the raw column stands alone (move the arithmetic to the constant side, as with salary > 49000). Or, when you genuinely need the transformation, build an expression index on the transformed value itself. CREATE INDEX ... ON employees(LOWER(name)) stores the lowercased strings, so the matching query becomes sargable again. Maya picks the rewrite, and the Seq Scan flips back to an Index Scan.

An index can cover more than one column, and the order of those columns is not cosmetic. It determines which queries the index can serve. A composite index is sorted by the first column, then by the second within each value of the first, exactly like a phone book sorted by last name, then first name.

CREATE INDEX idx_orders_status_date
  ON orders(status, order_date);

Because it is sorted by status first, this index follows the left-prefix rule: it can serve any query that filters on a leading prefix of its columns, but not on a later column alone.

The phone-book intuition makes the "No" obvious: a book sorted by last-name-then-first is useless for finding everyone named "James" regardless of surname, since the Jameses are scattered across every letter. Filtering on order_date alone is the same problem.

Normally an Index Scan is two steps: navigate the B-tree to find where the rows are, then go to the table (the "heap") to fetch them. But if the index already contains every column the query needs, the second step is pointless, since Postgres can answer entirely from the index. This is an index-only scan, and the index is called a covering index.

-- query only needs emp_id and amount
SELECT amount FROM orders WHERE emp_id = 42;

-- index that covers it: emp_id to search, amount carried along
CREATE INDEX idx_orders_emp_amt
  ON orders(emp_id) INCLUDE (amount);
-- plan now shows: Index Only Scan, no heap fetch

The INCLUDE clause carries extra columns in the index's leaf nodes without making them part of the sort key, so amount rides along just to be returned, without bloating the searchable part of the tree. The plan changes from Index Scan to Index Only Scan, skipping the heap visit entirely. It is a real win for hot, read-heavy queries, but keep it in proportion: every extra column makes the index larger and slower to maintain.

Knowing when an index will not help is as senior a skill as knowing when it will. Three cases where adding one is the wrong move:

Selectivity is the idea under all of this. An index pays off when it lets the database skip most of the table. If a filter matches a tiny fraction of rows (high selectivity), an index is a huge win. If it matches a large fraction (low selectivity, like a boolean or a 2-value status), the planner correctly decides scanning is cheaper than bouncing between the index and the table thousands of times, and it will ignore your index even if you build it.

A repeatable workflow for any slow query

When someone hands you a slow query, do not guess. Run this loop:

The first and last steps matter most. People skip straight to "add an index" without measuring, add the wrong one, and never check whether it helped. Measure, change one thing, measure again. That discipline, not memorized syntax, is what turned Maya from someone who filed a ticket into someone who closes them, and it is what makes you trustworthy with a production database.

To see a Seq Scan beat into an Index Scan, you need a table big enough to matter. Generate one, then run each task and read the plan before and after every change. Reading about indexes does nothing; watching 843 ms become 0.09 ms in your own terminal is what makes it stick.

-- 2 million synthetic orders to make scans hurt
INSERT INTO orders (order_id, emp_id, customer, amount, order_date, status)
SELECT g,
       (random() * 1000)::int,
       'cust_' || g,
       (random() * 500)::numeric(10,2),
       DATE '2020-01-01' + (random() * 1500)::int,
       (ARRAY['paid','pending','cancelled'])[ceil(random()*3)]
FROM generate_series(1, 2000000) AS g;

ANALYZE orders;  -- refresh planner statistics

• Run EXPLAIN ANALYZE SELECT * FROM orders WHERE emp_id = 42; before any index. Note the scan type, the execution time, and the "Rows Removed by Filter" line.
• Create idx_orders_emp on emp_id, run the same EXPLAIN ANALYZE again, and compare. Confirm it flipped to an Index Scan and the time dropped sharply.
• Write a non-sargable query: WHERE emp_id + 0 = 42. Confirm the plan reverts to a Seq Scan even though the index exists. Then rewrite it sargably and watch the index return.
• Build a composite index on (status, order_date). Show it is used for WHERE status='paid' AND order_date > '2023-01-01'.
• Now query WHERE order_date > '2023-01-01' alone. Prove the composite index is not used (left-prefix rule); it should Seq Scan or use a different index.
• Create an expression index on LOWER(customer), then confirm WHERE LOWER(customer) = 'cust_500' uses it.
• Run EXPLAIN (no ANALYZE) on a query and then EXPLAIN ANALYZE. Spot the difference: estimated vs. actual rows and the presence of real timing.
• Build a covering index with INCLUDE (amount) and confirm a query selecting only amount shows an Index Only Scan.