Access paths and selectivity

Before a database can join tables, it must find each table's candidate rows. It has two broad options. It can read every page of the table, which is a sequential scan. Or it can use an index to jump to the matching rows, which is an index scan. Each option is called an access path. The planner picks one by comparing estimated costs.

The big idea: sequential reads vs random reads

Reading a table in order is fast, because the disk or memory reads pages one after another. Following an index is often random. Each matching row may point to a different page, and each page fetch is a separate trip.

So an index is not automatically faster. It wins only when it avoids reading most of the table. The key number is selectivity: the fraction of rows that a condition keeps.

Walking through a scan decision

Take orders with 10 million rows, stored in 8 KB pages with about 100 rows per page. That is about 100,000 pages.

pages in table                = 10,000,000 / 100 = 100,000
index lookup returns          = 50,000 rows
if rows are scattered         ≈ 50,000 separate page reads
sequential scan reads         = 100,000 pages, in order

The index touches half as many pages, but each read is random and costs more. Reading the table once in order can be cheaper. When the planner ignores your index in a case like this, it is protecting you from random I/O. It is not being careless.

The main access paths

The index-only scan needs a covering index. You can add extra columns with INCLUDE so the query never has to visit the table.

Why the planner skips an index

Common reasons:

• The predicate wraps the column. WHERE lower(email) = 'x' cannot use a plain index on email. It needs an index on lower(email).
• Mismatched types. WHERE indexed_bigint = '42' may not match the index, depending on the types involved.
• The statistics say the condition is not selective. The planner expects many rows, so a scan is cheaper. See statistics and cardinality.
• An ordering helps. An index that returns rows already sorted can beat a scan followed by a sort, especially with ORDER BY … LIMIT.

Common mistakes

• Adding an index for a low-selectivity column. A boolean or a status with 3 values rarely helps on its own.
• Wrapping an indexed column in a function. Rewrite the condition as a range, or index the expression.
• Expecting an index to fix a query that returns most of the table. A scan is often the right answer there.

Check yourself

1. Why can an index lookup that returns 50,000 rows be slower than a scan of 100,000 pages? Each matching row may sit on a different page, so the index causes many random reads. The scan reads pages in order.
2. Why does WHERE date_trunc('day', created_at) = … ignore an index on created_at? The index stores the raw values. Wrapping the column in a function hides them from the index. Use a range condition instead.

Key takeaways

• An access path is how the database finds a table's rows: a scan or an index.
• Index scans can be random and expensive, so they win only when the condition is selective.
• Selectivity is the fraction of rows kept. Low selectivity favors scans.
• Write conditions so the index can be used, such as ranges instead of functions on the column.

Further learning

Next, read join algorithms to see how the database combines the rows from two access paths.

Use The Index, LukeSQL indexing and tuning tutorial for developers. No unnecessary database details—just what developers need to know. Covers all major SQL databases.use-the-index-luke.com