Opensource internals

How PostgreSQL Skip Scans B-Tree Indexes

33 min read Jay Hubbert

With PostgreSQL 18's skip scan, an index on (a, b) can serve a query on b alone by procedurally generating the possible a values, which can be orders of magnitude faster than a full index scan.

A B-tree index on (a, b) is a sorted list of pairs. Sorting by a first means all the rows with a = 1 are contiguous, all the rows with a = 2 are contiguous, and so on — and within each of those groups, the rows are sorted by b.

Now consider the query SELECT * FROM t WHERE b = 5. There is exactly one row per a value that satisfies it, scattered all over the index, one per group. The index knows how to find a = 1, b = 5 in logarithmic time. It has no idea how to find b = 5 alone, because b is not the leading column.

This is the oldest limitation in multi-column B-tree indexing, and it is why people end up with four indexes. PostgreSQL 18 changed it. The feature is called skip scan, and it is one of the more interesting pieces of work in the nbtree access method — not because of the idea, which is obvious, but because of how carefully the implementation avoids making ordinary scans slower.

This is a walk through how it works, based on reading the PostgreSQL source (version 20devel, commit e75fcc9867f).

The idea, stated plainly

If you want to find b = 5 in an index on (a, b), and the number of distinct a values is small, you can just do:

text 
for each distinct value of a:
    look up (a, 5)

The commit that introduced the feature (92fe23d9, “Add nbtree skip scan optimization”) states it exactly:

Teach nbtree multi-column index scans to opportunistically skip over irrelevant sections of the index given a query with no “=” conditions on one or more prefix index columns. When nbtree is passed input scan keys derived from a predicate “WHERE b = 5”, new nbtree preprocessing steps output “WHERE a = ANY(<every possible ‘a’ value>) AND b = 5” scan keys. That is, preprocessing generates a “skip array” (and an output scan key) for the omitted prefix column “a”, which makes it safe to mark the scan key on “b” as required to continue the scan. The scan is therefore able to repeatedly reposition itself by applying both the “a” and “b” keys.

The critical phrase is “makes it safe to mark the scan key on b as required”. In a normal B-tree scan, a key is required if the scan can stop as soon as it is violated. With an unconstrained leading column, the b = 5 key cannot be required: the index is not sorted by b globally, so failing b = 5 tells you nothing about whether a later tuple might match. That is precisely why a scan with WHERE b = 5 on (a, b) has to read the whole index.

Add an artificial equality constraint on a — “a equals some value” — and the index is sorted by b within each a group. Now b = 5 is a required key, and the scan can stop as soon as it leaves the group.

The obstacle: nobody knows what “every possible a value” is, and there could be ten million of them. So the “array” is not materialized. It is generated on demand, one element at a time, as the scan runs. That is what a skip array is.

What the planner already did (and didn’t) do

It is worth being precise here, because “the planner falls back to a full index scan or a sequential scan” is only half true.

The planner does match a non-leading column’s qual to the index. match_clause_to_index() in src/backend/optimizer/path/indxpath.c tries every index column in turn:

c 
	/* OK, check each index key column for a match */
	for (indexcol = 0; indexcol < index->nkeycolumns; indexcol++)
	{
		IndexClause *iclause;
		ListCell   *lc;

		/* Ignore duplicates */
		foreach(lc, clauseset->indexclauses[indexcol])
		{
			iclause = (IndexClause *) lfirst(lc);

			if (iclause->rinfo == rinfo)
				return;
		}

		/* OK, try to match the clause to the index column */
		iclause = match_clause_to_indexcol(root,
										   rinfo,
										   indexcol,
										   index);

and build_index_paths() collects the matched clauses from every column into one list:

c 
	index_clauses = NIL;
	outer_relids = bms_copy(rel->lateral_relids);
	for (indexcol = 0; indexcol < index->nkeycolumns; indexcol++)
	{
		ListCell   *lc;

		foreach(lc, clauses->indexclauses[indexcol])
		{
			IndexClause *iclause = (IndexClause *) lfirst(lc);
			...
			/* OK to include this clause */
			index_clauses = lappend(index_clauses, iclause);

So the qual on b is passed to the index AM as an index qual. What the AM does with it is up to the AM. Before skip scan, nbtree would evaluate b = 5 against every tuple in the index and could not use it to stop early — a full index scan, but a scan that at least avoided the heap.

There is a real regression test in the tree that shows the modern behaviour. From src/test/regress/sql/btree_index.sql:

sql 
-- Test for skip scan with type that lacks skip support (text)
--
set enable_seqscan to false;
set enable_bitmapscan to false;

-- Forwards scan
SELECT id FROM btree_tall_tbl WHERE id = 55 ORDER BY t, id;

against an index on (t text, id int4). The expected plan (src/test/regress/expected/btree_index.out) is:

text 
                       QUERY PLAN
--------------------------------------------------------
 Index Only Scan using btree_tall_idx on btree_tall_tbl
   Index Cond: (id = 55)

Index Cond: (id = 55) on an index whose leading column is t. The planner does not label it as a skip scan, does not produce a second competing path, and does not change the plan shape depending on whether the scan actually manages to skip. It produces one index scan, and the AM decides at runtime how to execute it.

That design decision was deliberate, and it is the reason the feature could be merged without a lot of planner churn. As the follow-up commit 8a510275dd6 puts it:

Skip scan adds skip arrays during preprocessing using simple, static rules, and decides how best to navigate/apply the scan’s skip arrays dynamically, at runtime. The “startikey” optimization enables this approach. As a result of all this, the planner doesn’t need to generate distinct, competing index paths (one path for skip scan, another for an equivalent traditional full index scan). The overall effect is to make scan runtime close to optimal, even when the planner works off an incorrect cardinality estimate.

One path, runtime decisions. That is a much better design than two paths and a planner bet.

Generating the skip array

The skip array is created during scan key preprocessing, in src/backend/access/nbtree/nbtpreprocesskeys.c. This is the code that every B-tree index scan runs through before it touches the index.

The file’s header comment explains the whole scheme, including the part that motivates skip arrays in the first place:

If we never generated skip array scan keys, it would be possible for “gaps” to appear that make it unsafe to mark any subsequent input scan keys (copied from scan->keyData[]) as required to continue the scan. Prior to Postgres 18, a qual like “WHERE y = 4” always resulted in a full scan. This qual now becomes “WHERE x = ANY(’{every possible x value}’) and y = 4” on output. In other words, preprocessing now adds a skip array on “x”. This has the potential to be much more efficient than a full index scan (though it behaves like a full scan when there’s many distinct “x” values).

And it explains the cost of the feature, honestly:

Skip array = keys will even be generated in the presence of “contradictory” inequality quals when it’ll enable marking later input quals as required. We’ll merge any such inequalities into the generated skip array by setting its array.low_compare or array.high_compare key field. The resulting skip array will generate its array elements from a range that’s constrained by any merged input inequalities (which won’t get output in so->keyData[]).

Deciding which columns get skip arrays

_bt_num_array_keys() does the planning of which columns need a skip array. Its header comment is the clearest statement of the rules in the whole feature:

Also sets *numSkipArrayKeys_out to the number of skip arrays caller must add to the scan keys it’ll output. Caller must add this many skip arrays: one array for each of the most significant attributes that lack a = input key (IS NULL keys count as = input keys here). The specific attributes that need skip arrays are indicated by initializing skip_eq_ops_out[] arg 0-based attribute offset to a valid = op strategy Oid. We’ll only ever set skip_eq_ops_out[] entries to InvalidOid for attributes that already have an equality key in scan->keyData[] input keys – and only when there’s some later “attribute gap” for us to “fill-in” with a skip array.

We’re optimistic about skipping working out: we always add exactly the skip arrays needed to maximize the number of input scan keys that can ultimately be marked as required to continue the scan (but no more). Given a multi-column index on (a, b, c, d), we add skip arrays as follows:

Input keys Output keys (after all preprocessing)

a = 1 a = 1 (no skip arrays) b = 42 skip a AND b = 42 a = 1 AND b = 42 a = 1 AND b = 42 (no skip arrays) a >= 1 AND b = 42 range skip a AND b = 42 a = 1 AND b > 42 a = 1 AND b > 42 (no skip arrays) a >= 1 AND a <= 3 AND b = 42 range skip a AND b = 42 a = 1 AND c <= 27 a = 1 AND skip b AND c <= 27 a = 1 AND d >= 1 a = 1 AND skip b AND skip c AND d >= 1 a = 1 AND b >= 42 AND d > 1 a = 1 AND range skip b AND skip c AND d > 1

Read that table carefully; it is the specification. Two rules fall out:

  1. A skip array is added for a leading column only if a later column has a qual. If b = 42 is the last qual, a skip array on a is pointless — there is nothing after it that could become required. The last column never gets a skip array.
  2. A skip array’s range is constrained by inequality quals on the same column. a >= 1 AND b = 42 produces a range skip array on a that only generates values ≥ 1.

The implementation walks the input keys and back-fills:

c 
		/*
		 * Backfill skip arrays for any wholly omitted attributes prior to
		 * attno_inkey
		 */
		while (attno_skip < attno_inkey)
		{
			Oid			opfamily = rel->rd_opfamily[attno_skip - 1];
			Oid			opcintype = rel->rd_opcintype[attno_skip - 1];

			/* Look up input opclass's equality operator (might fail) */
			skip_eq_ops_out[attno_skip - 1] =
				get_opfamily_member(opfamily, opcintype, opcintype,
									BTEqualStrategyNumber);
			if (!OidIsValid(skip_eq_ops_out[attno_skip - 1]))
			{
				/*
				 * Cannot generate a skip array for this or later attributes
				 * (input opclass lacks an equality strategy operator)
				 */
				*numSkipArrayKeys_out = prev_numSkipArrayKeys;
				return numSAOPArrayKeys + prev_numSkipArrayKeys;
			}

			/* plan on adding a backfill skip array for this attribute */
			numSkipArrayKeys++;
			attno_skip++;
		}

Note the bail-out: if the opclass has no equality operator, no skip array is possible for that column or any later column. This is why skip scan does not work for every type.

The result is recorded on the scan:

c 
	numArrayKeys = _bt_num_array_keys(scan, skip_eq_ops, &numSkipArrayKeys);
	so->skipScan = (numSkipArrayKeys > 0);

so->skipScan is the flag the runtime uses to know it is dealing with a skip scan, and it is consulted in exactly one place in the read path (section on startikey below).

Building the scan key

The actual scan key is constructed in _bt_preprocess_array_keys():

c 
			cmp_proc = get_opcode(eq_op);
			if (!RegProcedureIsValid(cmp_proc))
				elog(ERROR, "missing oprcode for skipping equals operator %u", eq_op);

			ScanKeyEntryInitialize(cur,
								   SK_SEARCHARRAY | SK_BT_SKIP, /* flags */
								   attno_skip,	/* skipped att number */
								   BTEqualStrategyNumber,	/* equality strategy */
								   InvalidOid,	/* opclass input subtype */
								   collation,	/* index column's collation */
								   cmp_proc,	/* equality operator's proc */
								   (Datum) 0);	/* constant */

			/* Initialize generic BTArrayKeyInfo fields */
			so->arrayKeys[numArrayKeys].scan_key = numArrayKeyData;
			so->arrayKeys[numArrayKeys].num_elems = -1;

			/* Initialize skip array specific BTArrayKeyInfo fields */
			attr = TupleDescCompactAttr(RelationGetDescr(rel), attno_skip - 1);
			reverse = (indoption[attno_skip - 1] & INDOPTION_DESC) != 0;
			so->arrayKeys[numArrayKeys].attlen = attr->attlen;
			so->arrayKeys[numArrayKeys].attbyval = attr->attbyval;
			so->arrayKeys[numArrayKeys].null_elem = true;	/* for now */
			so->arrayKeys[numArrayKeys].sksup =
				PrepareSkipSupportFromOpclass(opfamily, opcintype, reverse);
			so->arrayKeys[numArrayKeys].low_compare = NULL; /* for now */
			so->arrayKeys[numArrayKeys].high_compare = NULL;	/* for now */

Three things to notice:

  • num_elems = -1 is the marker that distinguishes a skip array from an ordinary ScalarArrayOpExpr array. The BTArrayKeyInfo struct says so plainly:
c 
typedef struct BTArrayKeyInfo
{
	/* fields set for both kinds of array (SAOP arrays and skip arrays) */
	int			scan_key;		/* index of associated key in keyData */
	int			num_elems;		/* number of elems (-1 means skip array) */

	/* fields set for ScalarArrayOpExpr arrays only */
	Datum	   *elem_values;	/* array of num_elems Datums */
	int			cur_elem;		/* index of current element in elem_values */

	/* fields set for skip arrays only */
	int16		attlen;			/* attr's length, in bytes */
	bool		attbyval;		/* attr's FormData_pg_attribute.attbyval */
	bool		null_elem;		/* NULL is lowest/highest element? */
	SkipSupport sksup;			/* skip support (NULL if opclass lacks it) */
	ScanKey		low_compare;	/* array's > or >= lower bound */
	ScanKey		high_compare;	/* array's < or <= upper bound */
} BTArrayKeyInfo;
  • The scan key gets the SK_BT_SKIP flag, defined in src/include/access/nbtree.h alongside the other nbtree-specific scan key flags:
c 
#define SK_BT_REQFWD	0x00010000	/* required to continue forward scan */
#define SK_BT_REQBKWD	0x00020000	/* required to continue backward scan */
#define SK_BT_SKIP		0x00040000	/* skip array on column without input = */

/* SK_BT_SKIP-only flags (set and unset by array advancement) */
#define SK_BT_MINVAL	0x00080000	/* invalid sk_argument, use low_compare */
#define SK_BT_MAXVAL	0x00100000	/* invalid sk_argument, use high_compare */
#define SK_BT_NEXT		0x00200000	/* positions the scan > sk_argument */
#define SK_BT_PRIOR		0x00400000	/* positions the scan < sk_argument */
  • sksup is the opclass’s skip support, and it may be NULL.

Making the keys required

After preprocessing, the keys are marked required if they can be. The rule is in _bt_mark_scankey_required():

c 
	switch (skey->sk_strategy)
	{
		case BTLessStrategyNumber:
		case BTLessEqualStrategyNumber:
			addflags = SK_BT_REQFWD;
			break;
		case BTEqualStrategyNumber:
			addflags = SK_BT_REQFWD | SK_BT_REQBKWD;
			break;

An equality key is required in both directions — it is exactly the constraint that makes the scan able to stop. This is the payoff of the skip array: the b = 5 key becomes an equality key, and it becomes required, and the scan can terminate.

There is an invariant worth quoting, from _bt_preprocess_array_keys_final():

c 
			/*
			 * All skip arrays must be marked required, and final column can
			 * never have a skip array
			 */
			Assert(array->num_elems > 0 || array->num_elems == -1);
			Assert(array->num_elems != -1 || outkey->sk_flags & SK_BT_REQFWD);
			Assert(array->num_elems != -1 ||
				   outkey->sk_attno < IndexRelationGetNumberOfKeyAttributes(rel));

Every skip array is required; the last column never has one. Those two invariants are the whole specification, restated as assertions.

Skip support: generating the values

Now the interesting part: how does the scan produce “the next value of a”?

There are two mechanisms.

The generic one: sentinel flags

If the opclass has no skip support function, the scan cannot compute the next value of a. Instead, it sets a flag saying “position the scan somewhere after the current element” and lets the index itself find the next value that actually exists:

c 
	/*
	 * Opclasses without skip support "increment" the scan key's current
	 * element by setting the NEXT flag.  The true next value is determined by
	 * repositioning to the first index tuple > existing sk_argument/current
	 * array element.  Note that this works in the usual way when the scan key
	 * is already marked ISNULL (i.e. when the current element is NULL).
	 */
	if (!array->sksup)
	{
		/* Successfully "incremented" array */
		skey->sk_flags |= SK_BT_NEXT;
		return true;
	}

SK_BT_NEXT means “position strictly after the current element”; SK_BT_PRIOR is the backwards-scan equivalent; SK_BT_MINVAL and SK_BT_MAXVAL mean “the current element is the lowest/highest value in the array’s range, use low_compare/high_compare instead”.

This is the mechanism the text regression test above exercises, since text has no skip support.

The clever one: opclass support functions

For discrete types — integers, dates, oids, timestamps, uuids — the opclass can supply a function that knows how to step to the next value. The interface is in src/include/utils/skipsupport.h:

B-Tree operator classes for discrete types can optionally provide a support function for skipping. This is used during skip scans.

A B-tree operator class that implements skip support provides B-tree index scans with a way of enumerating and iterating through every possible value from the domain of indexable values. This gives scans a way to determine the next value in line for a given skip array/scan key/skipped attribute. Scans request the next (or previous) value whenever they run out of tuples matching the skip array’s current element value. The next (or previous) value can be used to relocate the scan; it is applied in combination with at least one additional lower-order non-skip key, taken from the query.

The structure is small:

c 
typedef struct SkipSupportData
{
	/*
	 * low_elem and high_elem must be set with the lowest and highest possible
	 * values from the domain of indexable values (assuming ascending order)
	 */
	Datum		low_elem;		/* lowest sorting/leftmost non-NULL value */
	Datum		high_elem;		/* highest sorting/rightmost non-NULL value */

	/*
	 * Decrement/increment functions.
	 * ...
	 */
	SkipSupportIncDec decrement;
	SkipSupportIncDec increment;
} SkipSupportData;

The int4 implementation is in src/backend/access/nbtree/nbtcompare.c:

c 
Datum
btint4skipsupport(PG_FUNCTION_ARGS)
{
	SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);

	sksup->decrement = int4_decrement;
	sksup->increment = int4_increment;
	sksup->low_elem = Int32GetDatum(PG_INT32_MIN);
	sksup->high_elem = Int32GetDatum(PG_INT32_MAX);

	PG_RETURN_VOID();
}

with the increment being:

c 
static Datum
int4_increment(Relation rel, Datum existing, bool *overflow)
{
	int32		iexisting = DatumGetInt32(existing);

	if (iexisting == PG_INT32_MAX)
	{
		/* return value is undefined */
		*overflow = true;
		return (Datum) 0;
	}

	*overflow = false;
	return Int32GetDatum(iexisting + 1);
}

The opclasses that provide this are registered as a sixth amproc, BTSKIPSUPPORT_PROC:

c 
/*
 *	To facilitate more efficient B-Tree skip scans, an operator class may
 *	choose to offer a sixth amproc procedure (BTSKIPSUPPORT_PROC).  For full
 *	details, see src/include/utils/skipsupport.h.
 */

#define BTORDER_PROC		1
#define BTSORTSUPPORT_PROC	2
#define BTINRANGE_PROC		3
#define BTEQUALIMAGE_PROC	4
#define BTOPTIONS_PROC		5
#define BTSKIPSUPPORT_PROC	6

The header comment on the whole idea is worth repeating, because it explains the performance model:

Indexes with an attribute whose input opclass is of one of these types tend to store adjacent values in adjoining groups of index tuples. Each time a skip scan with skip support successfully guesses that the next value in the index (for a given skipped column) is indeed the value that skip support just incremented its skip array to, it will have saved the scan some work. The scan will have avoided an index probe that directly finds the next value that appears in the index. (When skip support guesses wrong, then it won’t have saved any work, but it also won’t have added any useless work. The failed attempt to locate exactly-matching index tuples acts just like an explicit probe would; it’ll still find the index’s true next value.)

That is the whole trick in one sentence: guessing the next value is free, and being wrong costs nothing extra — because a failed guess degenerates into exactly the index probe you would have done anyway.

For a DESC column the support is flipped, so that “increment” still means “move forward in scan order”:

c 
	if (reverse)
	{
		/*
		 * DESC/reverse case: swap low_elem with high_elem, and swap decrement
		 * with increment
		 */
		Datum		low_elem = sksup->low_elem;
		SkipSupportIncDec decrement = sksup->decrement;

		sksup->low_elem = sksup->high_elem;
		sksup->decrement = sksup->increment;

		sksup->high_elem = low_elem;
		sksup->increment = decrement;
	}

Runtime: advancing the array

The scan advances its skip array when it runs out of tuples matching the current element. The core is _bt_array_increment() in src/backend/access/nbtree/nbtreadpage.c:

c 
	/*
	 * Opclasses with skip support directly increment sk_argument
	 */
	if (skey->sk_flags & SK_ISNULL)
	{
		Assert(skey->sk_flags & SK_BT_NULLS_FIRST);

		/*
		 * Existing sk_argument/array element is NULL (for an IS NULL qual).
		 *
		 * "Increment" from NULL to the low_elem value provided by opclass
		 * skip support routine.
		 */
		skey->sk_flags &= ~(SK_SEARCHNULL | SK_ISNULL);
		skey->sk_argument = datumCopy(array->sksup->low_elem,
									  array->attbyval, array->attlen);
		return true;
	}

	/*
	 * Ask opclass support routine to provide incremented copy of existing
	 * non-NULL sk_argument
	 */
	inc_sk_argument = array->sksup->increment(rel, skey->sk_argument, &oflow);
	if (unlikely(oflow))
	{
		/* inc_sk_argument has undefined value (so no pfree) */
		if (array->null_elem && !(skey->sk_flags & SK_BT_NULLS_FIRST))
		{
			_bt_skiparray_set_isnull(rel, skey, array);

			/* Successfully "incremented" array to NULL */
			return true;
		}

		/* Cannot increment past final array element */
		return false;
	}

and the range check that keeps a range skip array inside its bounds:

c 
	/*
	 * Successfully incremented sk_argument to a non-NULL value.  Make sure
	 * that the incremented value is still within the range of the array.
	 */
	if (array->high_compare &&
		!DatumGetBool(FunctionCall2Coll(&array->high_compare->sk_func,
										array->high_compare->sk_collation,
										inc_sk_argument,
										array->high_compare->sk_argument)))
	{
		/* Keep existing sk_argument after all */
		if (!array->attbyval)
			pfree(DatumGetPointer(inc_sk_argument));

		/* Cannot increment past final array element */
		return false;
	}

Snapping to values that exist

A subtlety: the skip array’s “current element” does not have to be a value that actually appears in the index. _bt_skiparray_set_element() sets the current element from whatever the scan just saw:

c 
static void
_bt_skiparray_set_element(Relation rel, ScanKey skey, BTArrayKeyInfo *array,
						  int32 set_elem_result, Datum tupdatum, bool tupnull)
{
	Assert(skey->sk_flags & SK_BT_SKIP);
	Assert(skey->sk_flags & SK_SEARCHARRAY);

	if (set_elem_result)
	{
		/* tupdatum/tupnull is out of the range of the skip array */
		Assert(!array->null_elem);

		_bt_array_set_low_or_high(rel, skey, array, set_elem_result < 0);
		return;
	}

	/* Advance skip array to tupdatum (or tupnull) value */
	if (unlikely(tupnull))
	{
		_bt_skiparray_set_isnull(rel, skey, array);
		return;
	}

	/* Free memory previously allocated for sk_argument if needed */
	if (!array->attbyval && skey->sk_argument)
		pfree(DatumGetPointer(skey->sk_argument));

	/* tupdatum becomes new sk_argument/new current element */
	skey->sk_flags &= ~(SK_SEARCHNULL | SK_ISNULL |
						SK_BT_MINVAL | SK_BT_MAXVAL |
						SK_BT_NEXT | SK_BT_PRIOR);
	skey->sk_argument = datumCopy(tupdatum, array->attbyval, array->attlen);
}

In other words: when the scan finds a tuple whose a value is 7, the skip array’s current element becomes 7 — not 6, not 8. The scan has discovered the real next value by reading it. This is why skip support can be a pure optimization: if the guess was wrong, the scan learns the truth from the index.

The whole advancement machinery is driven from _bt_advance_array_keys(), which is also where the scan decides whether to schedule another “primitive” index scan:

c 
	/*
	 * Advance the array keys incrementally whenever "beyond end of array
	 * element" array advancement happens, so that advancement will carry to
	 * higher-order arrays (might exhaust all the scan's arrays instead, which
	 * ends the top-level scan).
	 */
	if (beyond_end_advance &&
		!_bt_advance_array_keys_increment(scan, dir, &skip_array_advanced))
		goto end_toplevel_scan;

Positioning the scan

The first descent into the index has to work out where to start. That is _bt_first() in src/backend/access/nbtree/nbtsearch.c, and its comment describes the skip-array case in detail:

For example, a forward scan with a skip array on its leading attribute (with no low_compare/high_compare) will have at least two required scan keys, but we won’t use any of them as boundary keys during the scan’s initial call here. Our positioning key during the first call here can be thought of as representing “> -infinity”. Similarly, if such a skip array’s low_compare is “a > ‘foo’”, then we position using “a > ‘foo’” during the scan’s initial call here; a lower-order key such as “b = 42” can’t be used until the “a” array advances beyond MINVAL/low_compare.

On the other hand, if such a skip array’s low_compare was “a >= ‘foo’”, then we can use “a >= ‘foo’ AND b = 42” during the initial call here. A subsequent call here might have us use “a = ‘fop’ AND b = 42”.

The code that implements this picks between the skip array’s low_compare and high_compare depending on scan direction:

c 
				if (bkey != NULL &&
					(bkey->sk_flags & (SK_BT_MINVAL | SK_BT_MAXVAL)))
				{
					int			ikey = bkey - so->keyData;
					ScanKey		skipequalitykey = bkey;
					BTArrayKeyInfo *array = NULL;

					for (int arridx = 0; arridx < so->numArrayKeys; arridx++)
					{
						array = &so->arrayKeys[arridx];
						if (array->scan_key == ikey)
							break;
					}

					if (ScanDirectionIsForward(dir))
					{
						Assert(!(skipequalitykey->sk_flags & SK_BT_MAXVAL));
						bkey = array->low_compare;
					}
					else
					{
						Assert(!(skipequalitykey->sk_flags & SK_BT_MINVAL));
						bkey = array->high_compare;
					}

So the initial descent uses the best available boundary, and subsequent repositionings use the concrete current element of the skip array. That is the “repeated WHERE x = N AND y = 7700 searches” behaviour the documentation describes:

For example, given an index on (x, y), and a query condition WHERE y = 7700, a B-tree index scan might be able to apply the skip scan optimization. This generally happens when the query planner expects that repeated WHERE x = N AND y = 7700 searches for every possible value of N (or for every x value that is actually stored in the index) is the fastest possible approach, given the available indexes on the table.

The startikey optimization

Here is the part that makes the feature safe to enable by default.

Without any special handling, adding a skip array to every scan that has a “gap” in its leading columns would slow down every ordinary scan. The cost is real: a skip array has to be maintained — checked, advanced, possibly re-checked — for every tuple the scan visits. On a scan that cannot actually skip anything, that maintenance is pure overhead.

The fix, in commit 8a510275dd6 (“Further optimize nbtree search scan key comparisons”), is the startikey optimization. The idea: on a given leaf page, work out which scan keys are guaranteed to be satisfied by every tuple on that page, and skip the comparison entirely.

_bt_set_startikey() in src/backend/access/nbtree/nbtreadpage.c does the work:

c 
/*
 * Determines an offset to the first scan key (an so->keyData[]-wise offset)
 * that is _not_ guaranteed to be satisfied by every tuple from pstate.page,
 * which is set in pstate.startikey for _bt_checkkeys calls for the page.
 * This allows caller to save cycles on comparisons of a prefix of keys while
 * reading pstate.page.
 *
 * Also determines if later calls to _bt_checkkeys (for pstate.page) should be
 * forced to treat all required scan keys >= pstate.startikey as nonrequired
 * (that is, if they're to be treated as if any SK_BT_REQFWD/SK_BT_REQBKWD
 * markings that were set by preprocessing were not set at all, for the
 * duration of _bt_checkkeys calls prior to the call for pstate.finaltup).
 * This is indicated to caller by setting pstate.forcenonrequired.
 */

The implementation looks at the first and last non-pivot tuples on the page, finds the first attribute whose values differ between them (_bt_keep_natts_fast()), and then walks the scan keys deciding which ones are safe to skip.

For a scalar = key it is conservative:

c 
		if (!(key->sk_flags & SK_SEARCHARRAY))
		{
			/*
			 * Scalar = key (possibly an IS NULL key).
			 *
			 * It is unsafe to set pstate.startikey to an ikey beyond this
			 * key, unless the = key is satisfied by every possible tuple on
			 * the page (possible only when attribute has just one distinct
			 * value among all tuples on the page).
			 */
			if (key->sk_attno >= firstchangingattnum)
				break;			/* unsafe, multiple distinct attr values */

For a non-range skip array it is permissive, because such an array is “satisfied” by every tuple on the page by construction:

c 
		/*
		 * Skip array = key
		 */
		Assert(key->sk_flags & SK_BT_SKIP);
		if (array->null_elem)
		{
			/*
			 * Non-range skip array = key.
			 *
			 * Safe, non-range skip array "satisfied" by every tuple on page
			 * (safe even when "key->sk_attno > firstchangingattnum").
			 */
			continue;
		}

And the second half of the optimization — suppressing the “required” protocol for the duration of the page — is this one line:

c 
	pstate->forcenonrequired = (start_past_saop_eq || so->skipScan);
	pstate->startikey = startikey;

so->skipScan is the flag set during preprocessing. So for a skip scan, the scan always suppresses the required-key protocol while reading a page, which is exactly where the per-tuple array maintenance cost would otherwise be paid. The scan still has to maintain the array correctly, so the caller must re-synchronize at the end of the page:

c 
	/*
	 * _bt_readpage caller is required to call _bt_checkkeys against page's
	 * finaltup with forcenonrequired=false whenever we initially set
	 * forcenonrequired=true.  That way the scan's arrays will reliably track
	 * its progress through the index's key space.
	 *
	 * We don't expect this when _bt_readpage caller has no finaltup due to
	 * its page being the rightmost (or the leftmost, during backwards scans).
	 * When we see that _bt_readpage has no finaltup, back out of everything.
	 */
	Assert(!pstate->forcenonrequired || so->numArrayKeys);
	if (pstate->forcenonrequired && !pstate->finaltup)
	{
		pstate->forcenonrequired = false;
		pstate->startikey = 0;
	}

And _bt_checkkeys() uses the offset when it starts comparing:

c 
static bool
_bt_checkkeys(IndexScanDesc scan, BTReadPageState *pstate, bool arrayKeys,
			  IndexTuple tuple, int tupnatts)
{
	TupleDesc	tupdesc = RelationGetDescr(scan->indexRelation);
	BTScanOpaque so PG_USED_FOR_ASSERTS_ONLY = (BTScanOpaque) scan->opaque;
	ScanDirection dir = pstate->dir;
	int			ikey = pstate->startikey;
	bool		res;

Compare that with the naive version, which would start at ikey = 0 and evaluate every key against every tuple. With startikey, the prefix of keys that are guaranteed satisfied by every tuple on the page is skipped entirely.

The commit message explains the intent precisely:

Although this is independently useful work, its main goal is to avoid performance regressions with index scans that use skip arrays, but still never manage to skip over irrelevant leaf pages. We must avoid wasting CPU cycles on overly granular skip array maintenance in these cases. The new “startikey” optimization helps with this by selectively disabling array maintenance for the duration of a _bt_readpage call. This has no lasting consequences for the scan’s array keys (they’ll still reliably track the scan’s progress through the index’s key space whenever the scan is “between pages”).

And it ends with the sentence that is the best summary of the whole feature:

Many scans that cannot possibly skip will still benefit from the use of skip arrays, since they’ll allow the “startikey” optimization to be as effective as possible (by allowing preprocessing to mark all the scan’s keys as required). A scan that uses a skip array on “a” for a qual “WHERE a BETWEEN 0 AND 1_000_000 AND b = 42” is often much faster now, even when every tuple read by the scan has its own distinct “a” value.

The planner’s cost model

The planner does not generate a separate skip-scan path, but it does have to price the scan, and the price depends on how many descents the skip array will cause. That is btcostestimate() in src/backend/utils/adt/selfuncs.c, and it is the only place in the optimizer that knows about skip arrays.

The core variable is num_sa_scans — the estimated number of primitive index scans. When the planner encounters a gap between the index columns that have quals and the column that does, it multiplies in the skipped column’s ndistinct:

c 
			/*
			 * Skip scans use skip arrays, which are ScalarArrayOp style
			 * arrays that generate their elements procedurally and on demand.
			 * Given a multi-column index on "(a, b)", and an SQL WHERE clause
			 * "WHERE b = 42", a skip scan will effectively use an indexqual
			 * "WHERE a = ANY('{every col a value}') AND b = 42".  (Obviously,
			 * the array on "a" must also return "IS NULL" matches, since our
			 * WHERE clause used no strict operator on "a").
			 */
c 
				/*
				 * When there's no inequality quals, account for the need to
				 * find an initial value by counting -inf/+inf as a value.
				 ...
				 */
				if (indexSkipQuals == NIL)
					ndistinct += 1;

				/*
				 * Update num_sa_scans estimate by multiplying by ndistinct.
				 *
				 * We make the pessimistic assumption that there is no
				 * naturally occurring cross-column correlation.  This is
				 * often wrong, but it seems best to err on the side of not
				 * expecting skipping to be helpful...
				 */
				num_sa_scans *= ndistinct;

And then the discontinuity that keeps the estimate sane:

c 
				/*
				 * ...but back out of adding this latest group of 1 or more
				 * skip arrays when num_sa_scans exceeds the total number of
				 * index pages (revert to num_sa_scans from before indexcol).
				 * This causes a sharp discontinuity in cost (as a function of
				 * the indexcol's ndistinct), but that is representative of
				 * actual runtime costs.
				 *
				 * Note that skipping is helpful when each primitive index
				 * scan only manages to skip over 1 or 2 irrelevant leaf pages
				 * on average.  Skip arrays bring savings in CPU costs due to
				 * the scan not needing to evaluate indexquals against every
				 * tuple, which can greatly exceed any savings in I/O costs.
				 * This test is a test of whether num_sa_scans implies that
				 * we're past the point where the ability to skip ceases to
				 * lower the scan's costs (even qual evaluation CPU costs).
				 */
				if (index->pages < num_sa_scans)
				{
					num_sa_scans = num_sa_scans_prev_cols;
					break;		/* done building indexBoundQuals */
				}

So: if the skipped column has so many distinct values that you would need one index descent per page of the index, the planner stops pretending skipping will help. The cost function has a cliff in it, and the comment says so.

There is a second clamp, applied to everything:

c 
		/*
		 * btree automatically combines individual array element primitive
		 * index scans whenever the tuples covered by the next set of array
		 * keys are close to tuples covered by the current set.  That puts a
		 * natural ceiling on the worst case number of descents -- there
		 * cannot possibly be more than one descent per leaf page scanned.
		 *
		 * Clamp the number of descents to at most 1/3 the number of index
		 * pages. ...
		 */
		num_sa_scans = Min(num_sa_scans, ceil(index->pages * 0.3333333));
		num_sa_scans = Max(num_sa_scans, 1);

And the descent costs are charged per primitive scan, which is what makes a skip scan look expensive when it should not be used:

c 
	if (index->tuples > 1)		/* avoid computing log(0)
	{
		descentCost = ceil(log(index->tuples) / log(2.0)) * cpu_operator_cost;
		costs.indexStartupCost += descentCost;
		costs.indexTotalCost += costs.num_sa_scans * descentCost;
	}

Note the asymmetry in that code: the first descent is startup cost, the rest are total cost. Which is right, because the first descent is unavoidable — you have to find the first matching tuple somehow — while the rest are the cost of skipping.

Backwards scans

Skip scan works in both directions, and a separate optimization (1bd4bc85cac, “Optimize nbtree backwards scans”) makes backwards scans cheaper in general:

Make nbtree backwards scans optimistically access the next page to be read to the left by following a prevPage block number that’s now stashed in currPos when the leaf page is first read. This approach matches the one taken during forward scans, which follow a symmetric nextPage block number from currPos. We stash both a prevPage and a nextPage, since the scan direction might change (when fetching from a scrollable cursor).

Backwards scans will no longer need to lock the same page twice, except in rare cases where the scan detects a concurrent page split (or page deletion). Testing has shown this optimization to be particularly effective during parallel index-only backwards scans: ~12% reductions in query execution time are quite possible.

This matters for skip scan because a skip array in a backwards scan has to step down through the values of the skipped column, using the opclass’s decrement function and the SK_BT_PRIOR sentinel.

The regression test above covers exactly this: the same query with ORDER BY t DESC, id DESC produces:

text 
                           QUERY PLAN
-----------------------------------------------------------------
 Index Only Scan Backward using btree_tall_idx on btree_tall_tbl
   Index Cond: (id = 55)

The caveats

The author of the feature is refreshingly candid about what does not work. From the 8a510275dd6 commit message:

There are still some remaining regressions, affecting certain trickier cases.

Scans whose index quals have several range skip arrays, each on some high cardinality column, can still be slower than they were before the introduction of skip scan – even with the new “startikey” optimization. There are also known regressions affecting very selective index scans that use a skip array. The underlying issue with such selective scans is that they never get as far as reading a second leaf page, and so will never get a chance to consider applying the “startikey” optimization. In principle, all regressions could be avoided by teaching preprocessing to not add skip arrays whenever they aren’t expected to help, but it seems best to err on the side of robust performance.

So, in the author’s own list:

Regression caseWhy
Very selective scans that never reach a second leaf pageThe startikey optimization only kicks in from the second page onwards, so the array maintenance cost is paid without the benefit
Several range skip arrays on high-cardinality columnsEach range skip array has to be maintained and checked; the savings do not materialize

And the original commit 92fe23d9 is equally blunt about the preprocessing rules being optimistic:

B-Tree preprocessing is optimistic about skipping working out: it applies static, generic rules when determining where to generate skip arrays, which assumes that the runtime overhead of maintaining skip arrays will pay for itself – or lead to only a modest performance loss. As things stand, these assumptions are much too optimistic: skip array maintenance will lead to unacceptable regressions with unsympathetic queries (queries whose scan can’t skip over many irrelevant leaf pages).

Other limitations worth knowing:

  • Row comparisons stop the skip array machinery. From _bt_num_array_keys():
c 
		/*
		 * Later preprocessing steps cannot merge a RowCompare into a skip
		 * array, so stop adding skip arrays once we see one.  (Note that we
		 * can backfill skip arrays before a RowCompare, which will allow keys
		 * up to and including the RowCompare to be marked required.)
		 *
		 * Skip arrays work by maintaining a current array element value,
		 * which anchors lower-order keys via an implied equality constraint.
		 * This is incompatible with the current nbtree row comparison design,
		 * which compares all columns together, as an indivisible group.
		 */

  • The opclass needs an equality operator. If the leading column’s opclass has no = operator in its opfamily, no skip array can be generated for it, and none for any later column either.

  • Skip support is optional and type-dependent. Without it, the scan falls back on SK_BT_NEXT/SK_BT_PRIOR probes, which are more expensive but still correct.

  • The planner’s estimate is pessimistic about correlation. It assumes no natural cross-column correlation when multiplying in ndistinct, “but it seems best to err on the side of not expecting skipping to be helpful”.

  • A skip scan is not free even when it skips nothing. The startikey optimization keeps the CPU cost down, but it does not make it zero, and for a scan that reads one page and stops, the extra page does not arrive.

What it all means in practice

A few conclusions:

  • Skip scan changes what a multi-column index is worth. The traditional advice — “a composite index on (a, b) is useless for queries that only constrain b” — is now only true when b has high cardinality relative to the number of index pages. The PostgreSQL documentation puts the threshold bluntly:

if x has no more than several hundred distinct values, skip scan will make searches for specific y values execute reasonably efficiently.

  • The feature is opportunistic, not planner-driven. The planner produces an ordinary index scan; the AM decides at runtime whether it can skip. There is no Skip Scan node type in EXPLAIN, no competing path, and no plan flip depending on cardinality estimates at execution time.

  • The interesting engineering is in the cost avoidance, not the feature. startikey exists so that adding a skip array to a scan that cannot benefit does not make it slower. The feature’s value is bounded by how cheaply the “cannot benefit” case can be handled.

  • Discrete types get the good version. A text leading column falls back on sentinel probes; an int leading column can guess the next value exactly. If you are designing a schema, int, date, oid and timestamp leading columns are the ones that skip scan well.

  • It composes with the existing index machinery. Skip arrays are SK_SEARCHARRAY scan keys with num_elems = -1; they use the same array-advancement and primitive-scan scheduling that PostgreSQL 17 added for ScalarArrayOpExpr quals, and the same SK_BT_REQFWD / SK_BT_REQBKWD protocol. The feature is a preprocessing rule plus a new element source, not a new scan type.

Further reading

  • src/backend/access/nbtree/nbtpreprocesskeys.c — where skip arrays are generated. The header comment at the top of the file is the design document.
  • src/backend/access/nbtree/nbtreadpage.c — _bt_set_startikey(), _bt_checkkeys(), _bt_advance_array_keys(), _bt_array_increment().
  • src/backend/access/nbtree/nbtsearch.c — _bt_first()’s boundary-key logic for skip arrays.
  • src/include/utils/skipsupport.h — the skip support interface, and the comment explaining when guessing the next value is profitable.
  • src/backend/access/nbtree/nbtcompare.c — the int4 skip support implementation.
  • src/backend/utils/adt/selfuncs.c — btcostestimate(), the planner’s side of skip scan.
  • doc/src/sgml/indices.sgml — the “Indexes on Multiple Columns” section, which describes the optimization from a user’s perspective.
  • Commits 92fe23d9 (add skip scan), 8a510275dd6 (startikey optimization), 21a152b37f3 (primitive scan scheduling), 1bd4bc85cac (backwards scans).

PostgresPerformanceBtreeIndexInternals