Index scan

On this page 7

An index scan is a query execution method in which the database engine traverses an index structure to find the rows that satisfy a predicate, then fetches those rows from the table, rather than reading every row in the table. In databases, the index scan is one of the basic access paths that the query planner chooses between, and it is the main reason indexing exists at all.

The value of an index scan depends on how many rows it returns. When a predicate matches a small fraction of a table, an index scan reduces the work from millions of row reads to a handful of page visits. When the predicate matches a large fraction, the same scan can be slower than a full table scan because it replaces sequential reads with scattered random reads.

How an index scan locates rows

An index scan works by descending the index tree to the first matching key and then reading index entries in key order until the predicate no longer holds. In a typical B-tree index, the engine starts at the root page, follows separator keys through internal pages, and reaches a leaf page in three to four page reads even for tables with hundreds of millions of rows.

Each leaf entry stores the indexed key together with a row locator, such as a physical tuple identifier in PostgreSQL or the clustering key in SQL Server and MySQL InnoDB. For every qualifying entry, the engine performs a table lookup (often called a heap fetch, key lookup or bookmark lookup) to read the remaining columns that the query needs.

The scan proceeds through the following phases, each of which contributes its own cost to the execution plan.

PhaseWhat the engine doesTypical cost driver
SeekDescends from root to the first qualifying leafTree height, usually 3-4 pages
Range walkReads consecutive leaf entries in key orderNumber of matching keys
Row lookupFetches each referenced row from the tableRandom I/O per row
FilterApplies predicates the index could not evaluateRows fetched but discarded
TerminationStops when keys exceed the range boundNegligible
Phases of a typical B-tree index scan

The ordering of the leaf level is a useful by-product. Because entries are already sorted, an index scan can satisfy ORDER BY clauses and merge joins without a separate sort step, which is often the deciding factor when the planner prefers it over a cheaper-looking alternative.

Variants of the index scan

Database engines implement several distinct index scan variants, and the names differ between products even when the mechanics match. Reading an execution plan correctly requires knowing which variant appears and what it implies about table access.

VariantHow it reads dataTypical engine naming
Index seek or range scanSeeks to a key, reads a bounded range, fetches rowsIndex Seek (SQL Server), Index Scan (PostgreSQL)
Full index scanReads every leaf entry in key orderIndex Scan (SQL Server), INDEX FULL SCAN (Oracle)
Index-only scanAnswers the query from the index without table accessIndex Only Scan (PostgreSQL), covering index use
Bitmap index scanCollects row locators into a bitmap, then reads pages in physical orderBitmap Index Scan plus Bitmap Heap Scan (PostgreSQL)
Skip scanJumps across distinct leading-column values of a composite indexINDEX SKIP SCAN (Oracle), skip scan (MySQL 8.0)
Common index access variants and their behavior

The terminology trap is real: in SQL Server, an Index Scan reads the whole index, whereas an Index Seek uses the tree to jump to a range. In PostgreSQL, the operator called Index Scan performs a seek followed by a range walk. Practitioners comparing plans across products should therefore read the operator details rather than its label.

The index-only scan deserves special attention. When every column the query references is present in the index, the engine skips the table lookup entirely. PostgreSQL additionally consults the visibility map to confirm that a page contains only rows visible to all transactions, so tables that are not vacuumed regularly lose much of this benefit.

Index scan compared with other access paths

The query planner chooses an index scan only when its estimated cost is lower than the cost of the competing access paths. The comparison rests on the estimated number of qualifying rows, the physical ordering of the table and the relative cost of random versus sequential I/O.

Access pathBest suited toI/O patternMain weakness
Sequential table scanLarge fractions of the tableSequential, read-ahead friendlyReads every page regardless of need
Index scanHighly selective predicatesRandom page reads per rowDegrades sharply as matches grow
Bitmap scanModerate selectivity, several predicatesSorted page readsLoses ordering, needs memory
Index-only scanQueries fully covered by the indexIndex pages onlyRequires wider indexes
Access paths compared by selectivity and I/O pattern

The crossover point between an index scan and a sequential scan is commonly cited as somewhere between 1% and 20% of the table, but no fixed threshold exists. It depends on row width, cache hit ratio, storage type and the correlation between index order and physical row order. On solid-state storage with a warm cache, index scans remain competitive at much higher fractions than on spinning disks.

PostgreSQL expresses this trade-off through the random_page_cost and seq_page_cost parameters, with defaults of 4.0 and 1.0. Lowering random_page_cost toward 1.1 on SSD-backed systems makes the planner choose index scans more readily, which is often appropriate but should be validated against real workloads.

Conditions that make an index scan possible

An index scan is available only when the predicate matches the index definition in a form the engine can use. Many slow queries have a perfectly good index that the planner cannot apply because of how the condition is written.

  • Leftmost prefix rule: a composite index on (customer_id, order_date) supports filters on customer_id alone or on both columns, but generally not on order_date alone unless the engine supports skip scans.
  • Sargable predicates: wrapping the indexed column in a function, as in WHERE LOWER(email) = 'x', prevents an index scan unless an expression index exists.
  • Matching data types: implicit type conversion, such as comparing a text column with a numeric literal, can disable index use silently.
  • Leading wildcards: LIKE '%term' cannot use a B-tree index, whereas LIKE 'term%' usually can.
  • Operator support: hash indexes serve only equality, while B-tree indexes serve equality, ranges and sorting.

Index selectivity decides the remaining cases. Even a perfectly sargable predicate on an indexed column will trigger a sequential scan when the planner estimates that most rows qualify, so accurate statistics from ANALYZE or UPDATE STATISTICS are a precondition for good index scan decisions.

Diagnosing problems with index scans

Most index scan problems appear as a gap between estimated and actual rows in the execution plan. Tools such as EXPLAIN ANALYZE in PostgreSQL, actual execution plans in SQL Server and EXPLAIN FORMAT=TREE in MySQL show both numbers, and a mismatch of an order of magnitude or more usually explains the slowdown.

SymptomLikely causeTypical remedy
Index scan returns far more rows than estimatedStale or skewed statisticsRefresh statistics, add extended statistics
Many rows fetched, then filtered outIndex covers only part of the predicateExtend the index or create a composite index
High random I/O despite few matchesLow correlation between index and table orderCluster the table or use a bitmap scan
Index-only scan still visits the heapVisibility map not up to dateRun VACUUM more frequently
Planner ignores an existing indexNon-sargable predicate or type mismatchRewrite the condition or add an expression index
Index scan symptoms, causes and remedies

A common misconception is that forcing an index scan always helps. Index hints and disabled sequential scans can fix one query while degrading others when data grows, so the durable fix is usually better statistics, a better index or a rewritten predicate rather than a planner override.

In everyday language

Picture a thick reference book with an alphabetical index at the back. To find every page that mentions one rare topic, you look it up in the index and turn straight to those pages. That is an index scan: the database checks its sorted list first and then visits only the rows it needs.

The shortcut stops paying off when the topic appears on almost every page. Jumping back and forth between index and text becomes slower than reading the book from start to finish. The fewer rows you need, the more an index scan helps, and the database decides which approach is cheaper each time it runs a query.

Seen in the real world

An online retailer keeps an orders table with about 80 million rows in PostgreSQL. A customer service screen runs a query that lists one customer’s orders from the last 90 days, sorted by date. Without a suitable index, the planner performs a sequential scan that reads the whole table and takes around 40 seconds.

The database team creates a composite B-tree index on (customer_id, order_date) and includes the order status and total as extra columns. The planner now chooses an index-only scan: it seeks to the customer, walks a few dozen leaf entries in date order and returns results without touching the table. The query finishes in under 5 milliseconds, and no separate sort step appears in the plan.

The team also notices that a monthly report filtering on order status alone still uses a sequential scan. That choice is correct, because the status predicate matches roughly 70% of the table, where an index scan would cost more than reading the table sequentially.