Date: 2025-05-14
Time: 14:00–14:50
Room: Breakout Room 2
Level: Advanced
Composite B-Tree indexes can be seen as multidimensional indexes where each index column represents a distinct dimension. The "skip scan" optimization exploits this dimensionality to enable far more efficient scans of standard composite B-Tree indexes. With skip scan, certain queries that would have traditionally required a large and expensive full index scan (or a sequential scan) are executed as a series of small index scans instead.
Given a composite index on "(a, b)", a skip scan plan can be used for queries whose predicate completely omits "a", and has a selective predicate on "b". This is likely to be the fastest plan when there is no index on "b" alone — provided that many index leaf pages can be skipped over by iteratively repositioning the scan to the next leaf page that might contain a matching tuple.
The skip scan optimization takes a query like this:
SELECT * FROM tab WHERE b = 5000;
and executes the query using a scan of our "(a, b)" index, which works as if the query had been written:
SELECT * FROM tab WHERE a = ANY('{every possible value in column a}') AND b = 5000;
This can be much more efficient when "a" is a very low cardinality column. Skip scan only needs to read leaf pages that might have tuples that satisfy "b = 5000" — typically one leaf page per distinct "a" value. Any leaf pages that couldn't possibly contain a matching tuple can be skipped over entirely.
The talk will present work targeting Postgres 18 (authored by the speaker) that adds the skip scan optimization to the standard nbtree index access method. It covers the design and implementation of nbtree skip scan, and relates that design to possible future improvements.
The skip scan technique was first described in the 1995 paper "Efficient Search of Multidimensional B-Trees". Skip scan is one of several techniques described by the paper. MDAM also provides a framework for general OR optimization. The general OR optimization technique could conceivably create plans that are competitive with traditional BitmapOr + Bitmap index alternatives — particularly when the alternatives fail to preserve index sort order.