Add nbtree skip scan optimization.

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.

A skip array has "elements" that are generated procedurally and on
demand, but otherwise works just like a regular ScalarArrayOp array.
Preprocessing can freely add a skip array before or after any input
ScalarArrayOp arrays.  Index scans with a skip array decide when and
where to reposition the scan using the same approach as any other scan
with array keys.  This design builds on the design for array advancement
and primitive scan scheduling added to Postgres 17 by commit 5bf748b8.

Testing has shown that skip scans of an index with a low cardinality
skipped prefix column can be multiple orders of magnitude faster than an
equivalent full index scan (or sequential scan).  In general, the
cardinality of the scan's skipped column(s) limits the number of leaf
pages that can be skipped over.

The core B-Tree operator classes on most discrete types generate their
array elements with the help of their own custom skip support routine.
This infrastructure gives nbtree a way to generate the next required
array element by incrementing (or decrementing) the current array value.
It can reduce the number of index descents in cases where the next
possible indexable value frequently turns out to be the next value
stored in the index.  Opclasses that lack a skip support routine fall
back on having nbtree "increment" (or "decrement") a skip array's
current element by setting the NEXT (or PRIOR) scan key flag, without
directly changing the scan key's sk_argument.  These sentinel values
behave just like any other value from an array -- though they can never
locate equal index tuples (they can only locate the next group of index
tuples containing the next set of non-sentinel values that the scan's
arrays need to advance to).

A skip array's range is constrained by "contradictory" inequality keys.
For example, a skip array on "x" will only generate the values 1 and 2
given a qual such as "WHERE x BETWEEN 1 AND 2 AND y = 66".  Such a skip
array qual usually has near-identical performance characteristics to a
comparable SAOP qual "WHERE x = ANY('{1, 2}') AND y = 66".  However,
improved performance isn't guaranteed.  Much depends on physical index
characteristics.

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).
An upcoming commit will address the problems in this area by enhancing
_bt_readpage's approach to saving cycles on scan key evaluation, making
it work in a way that directly considers the needs of = array keys
(particularly = skip array keys).

Author: Peter Geoghegan <[email protected]>
Reviewed-By: Masahiro Ikeda <[email protected]>
Reviewed-By: Heikki Linnakangas <[email protected]>
Reviewed-By: Matthias van de Meent <[email protected]>
Reviewed-By: Tomas Vondra <[email protected]>
Reviewed-By: Aleksander Alekseev <[email protected]>
Reviewed-By: Alena Rybakina <[email protected]>
Discussion: https://postgr.es/m/CAH2-Wzmn1YsLzOGgjAQZdn1STSG_y8qP__vggTaPAYXJP+G4bw@mail.gmail.com

1 files changed, 556 insertions, 75 deletions

diff --git a/src/backend/access/nbtree/nbtpreprocesskeys.c b/src/backend/access/nbtree/nbtpreprocesskeys.c
index 38a87af1cc8..791aa4ece40 100644
--- a/src/backend/access/nbtree/nbtpreprocesskeys.c
+++ b/src/backend/access/nbtree/nbtpreprocesskeys.c
@@ -45,8 +45,15 @@ static bool _bt_compare_array_scankey_args(IndexScanDesc scan,
 										   ScanKey arraysk, ScanKey skey,
 										   FmgrInfo *orderproc, BTArrayKeyInfo *array,
 										   bool *qual_ok);
+static bool _bt_saoparray_shrink(IndexScanDesc scan, ScanKey arraysk,
+								 ScanKey skey, FmgrInfo *orderproc,
+								 BTArrayKeyInfo *array, bool *qual_ok);
+static bool _bt_skiparray_shrink(IndexScanDesc scan, ScanKey skey,
+								 BTArrayKeyInfo *array, bool *qual_ok);
 static ScanKey _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys);
 static void _bt_preprocess_array_keys_final(IndexScanDesc scan, int *keyDataMap);
+static int	_bt_num_array_keys(IndexScanDesc scan, Oid *skip_eq_ops_out,
+							   int *numSkipArrayKeys_out);
 static Datum _bt_find_extreme_element(IndexScanDesc scan, ScanKey skey,
 									  Oid elemtype, StrategyNumber strat,
 									  Datum *elems, int nelems);
@@ -89,6 +96,8 @@ static int	_bt_compare_array_elements(const void *a, const void *b, void *arg);
  * within each attribute may be done as a byproduct of the processing here.
  * That process must leave array scan keys (within an attribute) in the same
  * order as corresponding entries from the scan's BTArrayKeyInfo array info.
+ * We might also construct skip array scan keys that weren't present in the
+ * original input keys; these are also output in standard attribute order.
  *
  * The output keys are marked with flags SK_BT_REQFWD and/or SK_BT_REQBKWD
  * if they must be satisfied in order to continue the scan forward or backward
@@ -101,10 +110,16 @@ static int	_bt_compare_array_elements(const void *a, const void *b, void *arg);
  * attributes with "=" keys are marked both SK_BT_REQFWD and SK_BT_REQBKWD.
  * For the first attribute without an "=" key, any "<" and "<=" keys are
  * marked SK_BT_REQFWD while any ">" and ">=" keys are marked SK_BT_REQBKWD.
- * This can be seen to be correct by considering the above example.  Note
- * in particular that if there are no keys for a given attribute, the keys for
- * subsequent attributes can never be required; for instance "WHERE y = 4"
- * requires a full-index scan.
+ * This can be seen to be correct by considering the above example.
+ *
+ * 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).
  *
  * If possible, redundant keys are eliminated: we keep only the tightest
  * >/>= bound and the tightest </<= bound, and if there's an = key then
@@ -137,11 +152,20 @@ static int	_bt_compare_array_elements(const void *a, const void *b, void *arg);
  * Again, missing cross-type operators might cause us to fail to prove the
  * quals contradictory when they really are, but the scan will work correctly.
  *
- * Row comparison keys are currently also treated without any smarts:
- * we just transfer them into the preprocessed array without any
+ * 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[]).
+ *
+ * Row comparison keys currently have a couple of notable limitations.
+ * Right now we just transfer them into the preprocessed array without any
  * editorialization.  We can treat them the same as an ordinary inequality
  * comparison on the row's first index column, for the purposes of the logic
- * about required keys.
+ * about required keys.  Also, we are unable to merge a row comparison key
+ * into a skip array (only ordinary inequalities are merged).  A key that
+ * comes after a Row comparison key is therefore never marked as required.
  *
  * Note: the reason we have to copy the preprocessed scan keys into private
  * storage is that we are modifying the array based on comparisons of the
@@ -200,6 +224,14 @@ _bt_preprocess_keys(IndexScanDesc scan)
 		/* Also maintain keyDataMap for remapping so->orderProcs[] later */
 		keyDataMap = MemoryContextAlloc(so->arrayContext,
 										numberOfKeys * sizeof(int));
+
+		/*
+		 * Also enlarge output array when it might otherwise not have room for
+		 * a skip array's scan key
+		 */
+		if (numberOfKeys > scan->numberOfKeys)
+			so->keyData = repalloc(so->keyData,
+								   numberOfKeys * sizeof(ScanKeyData));
 	}
 	else
 		inkeys = scan->keyData;
@@ -229,6 +261,7 @@ _bt_preprocess_keys(IndexScanDesc scan)
 			Assert(so->keyData[0].sk_flags & SK_SEARCHARRAY);
 			Assert(so->keyData[0].sk_strategy != BTEqualStrategyNumber ||
 				   (so->arrayKeys[0].scan_key == 0 &&
+					!(so->keyData[0].sk_flags & SK_BT_SKIP) &&
 					OidIsValid(so->orderProcs[0].fn_oid)));
 		}
 
@@ -288,7 +321,8 @@ _bt_preprocess_keys(IndexScanDesc scan)
 			 * redundant.  Note that this is no less true if the = key is
 			 * SEARCHARRAY; the only real difference is that the inequality
 			 * key _becomes_ redundant by making _bt_compare_scankey_args
-			 * eliminate the subset of elements that won't need to be matched.
+			 * eliminate the subset of elements that won't need to be matched
+			 * (with SAOP arrays and skip arrays alike).
 			 *
 			 * If we have a case like "key = 1 AND key > 2", we set qual_ok to
 			 * false and abandon further processing.  We'll do the same thing
@@ -345,7 +379,6 @@ _bt_preprocess_keys(IndexScanDesc scan)
 							return;
 						}
 						/* else discard the redundant non-equality key */
-						Assert(!array || array->num_elems > 0);
 						xform[j].inkey = NULL;
 						xform[j].inkeyi = -1;
 					}
@@ -393,6 +426,11 @@ _bt_preprocess_keys(IndexScanDesc scan)
 			 * Emit the cleaned-up keys into the so->keyData[] array, and then
 			 * mark them if they are required.  They are required (possibly
 			 * only in one direction) if all attrs before this one had "=".
+			 *
+			 * In practice we'll rarely output non-required scan keys here;
+			 * typically, _bt_preprocess_array_keys has already added "=" keys
+			 * sufficient to form an unbroken series of "=" constraints on all
+			 * attrs prior to the attr from the final scan->keyData[] key.
 			 */
 			for (j = BTMaxStrategyNumber; --j >= 0;)
 			{
@@ -481,6 +519,7 @@ _bt_preprocess_keys(IndexScanDesc scan)
 
 					Assert(array->scan_key == i);
 					Assert(OidIsValid(orderproc->fn_oid));
+					Assert(!(inkey->sk_flags & SK_BT_SKIP));
 				}
 				else if (xform[j].inkey->sk_flags & SK_SEARCHARRAY)
 				{
@@ -489,6 +528,7 @@ _bt_preprocess_keys(IndexScanDesc scan)
 
 					Assert(array->scan_key == xform[j].inkeyi);
 					Assert(OidIsValid(orderproc->fn_oid));
+					Assert(!(xform[j].inkey->sk_flags & SK_BT_SKIP));
 				}
 
 				/*
@@ -508,8 +548,6 @@ _bt_preprocess_keys(IndexScanDesc scan)
 				/* Have all we need to determine redundancy */
 				if (test_result)
 				{
-					Assert(!array || array->num_elems > 0);
-
 					/*
 					 * New key is more restrictive, and so replaces old key...
 					 */
@@ -803,6 +841,9 @@ _bt_compare_scankey_args(IndexScanDesc scan, ScanKey op,
 				cmp_op;
 	StrategyNumber strat;
 
+	Assert(!((leftarg->sk_flags | rightarg->sk_flags) &
+			 (SK_ROW_HEADER | SK_ROW_MEMBER)));
+
 	/*
 	 * First, deal with cases where one or both args are NULL.  This should
 	 * only happen when the scankeys represent IS NULL/NOT NULL conditions.
@@ -812,6 +853,22 @@ _bt_compare_scankey_args(IndexScanDesc scan, ScanKey op,
 		bool		leftnull,
 					rightnull;
 
+		/* Handle skip array comparison with IS NOT NULL scan key */
+		if ((leftarg->sk_flags | rightarg->sk_flags) & SK_BT_SKIP)
+		{
+			/* Shouldn't generate skip array in presence of IS NULL key */
+			Assert(!((leftarg->sk_flags | rightarg->sk_flags) & SK_SEARCHNULL));
+			Assert((leftarg->sk_flags | rightarg->sk_flags) & SK_SEARCHNOTNULL);
+
+			/* Skip array will have no NULL element/IS NULL scan key */
+			Assert(array->num_elems == -1);
+			array->null_elem = false;
+
+			/* IS NOT NULL key (could be leftarg or rightarg) now redundant */
+			*result = true;
+			return true;
+		}
+
 		if (leftarg->sk_flags & SK_ISNULL)
 		{
 			Assert(leftarg->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL));
@@ -885,6 +942,7 @@ _bt_compare_scankey_args(IndexScanDesc scan, ScanKey op,
 		{
 			/* Can't make the comparison */
 			*result = false;	/* suppress compiler warnings */
+			Assert(!((leftarg->sk_flags | rightarg->sk_flags) & SK_BT_SKIP));
 			return false;
 		}
 
@@ -978,24 +1036,56 @@ _bt_compare_scankey_args(IndexScanDesc scan, ScanKey op,
  * Compare an array scan key to a scalar scan key, eliminating contradictory
  * array elements such that the scalar scan key becomes redundant.
  *
+ * If the opfamily is incomplete we may not be able to determine which
+ * elements are contradictory.  When we return true we'll have validly set
+ * *qual_ok, guaranteeing that at least the scalar scan key can be considered
+ * redundant.  We return false if the comparison could not be made (caller
+ * must keep both scan keys when this happens).
+ *
+ * Note: it's up to caller to deal with IS [NOT] NULL scan keys, as well as
+ * row comparison scan keys.  We only deal with scalar scan keys.
+ */
+static bool
+_bt_compare_array_scankey_args(IndexScanDesc scan, ScanKey arraysk, ScanKey skey,
+							   FmgrInfo *orderproc, BTArrayKeyInfo *array,
+							   bool *qual_ok)
+{
+	Assert(arraysk->sk_attno == skey->sk_attno);
+	Assert(!(arraysk->sk_flags & (SK_ISNULL | SK_ROW_HEADER | SK_ROW_MEMBER)));
+	Assert((arraysk->sk_flags & SK_SEARCHARRAY) &&
+		   arraysk->sk_strategy == BTEqualStrategyNumber);
+	/* don't expect to have to deal with NULLs/row comparison scan keys */
+	Assert(!(skey->sk_flags & (SK_ISNULL | SK_ROW_HEADER | SK_ROW_MEMBER)));
+	Assert(!(skey->sk_flags & SK_SEARCHARRAY) ||
+		   skey->sk_strategy != BTEqualStrategyNumber);
+
+	/*
+	 * Just call the appropriate helper function based on whether it's a SAOP
+	 * array or a skip array.  Both helpers will set *qual_ok in passing.
+	 */
+	if (array->num_elems != -1)
+		return _bt_saoparray_shrink(scan, arraysk, skey, orderproc, array,
+									qual_ok);
+	else
+		return _bt_skiparray_shrink(scan, skey, array, qual_ok);
+}
+
+/*
+ * Preprocessing of SAOP array scan key, used to determine which array
+ * elements are eliminated as contradictory by a non-array scalar key.
+ *
+ * _bt_compare_array_scankey_args helper function.
+ *
  * Array elements can be eliminated as contradictory when excluded by some
  * other operator on the same attribute.  For example, with an index scan qual
  * "WHERE a IN (1, 2, 3) AND a < 2", all array elements except the value "1"
  * are eliminated, and the < scan key is eliminated as redundant.  Cases where
  * every array element is eliminated by a redundant scalar scan key have an
  * unsatisfiable qual, which we handle by setting *qual_ok=false for caller.
- *
- * If the opfamily doesn't supply a complete set of cross-type ORDER procs we
- * may not be able to determine which elements are contradictory.  If we have
- * the required ORDER proc then we return true (and validly set *qual_ok),
- * guaranteeing that at least the scalar scan key can be considered redundant.
- * We return false if the comparison could not be made (caller must keep both
- * scan keys when this happens).
  */
 static bool
-_bt_compare_array_scankey_args(IndexScanDesc scan, ScanKey arraysk, ScanKey skey,
-							   FmgrInfo *orderproc, BTArrayKeyInfo *array,
-							   bool *qual_ok)
+_bt_saoparray_shrink(IndexScanDesc scan, ScanKey arraysk, ScanKey skey,
+					 FmgrInfo *orderproc, BTArrayKeyInfo *array, bool *qual_ok)
 {
 	Relation	rel = scan->indexRelation;
 	Oid			opcintype = rel->rd_opcintype[arraysk->sk_attno - 1];
@@ -1006,14 +1096,8 @@ _bt_compare_array_scankey_args(IndexScanDesc scan, ScanKey arraysk, ScanKey skey
 	FmgrInfo	crosstypeproc;
 	FmgrInfo   *orderprocp = orderproc;
 
-	Assert(arraysk->sk_attno == skey->sk_attno);
 	Assert(array->num_elems > 0);
-	Assert(!(arraysk->sk_flags & (SK_ISNULL | SK_ROW_HEADER | SK_ROW_MEMBER)));
-	Assert((arraysk->sk_flags & SK_SEARCHARRAY) &&
-		   arraysk->sk_strategy == BTEqualStrategyNumber);
-	Assert(!(skey->sk_flags & (SK_ISNULL | SK_ROW_HEADER | SK_ROW_MEMBER)));
-	Assert(!(skey->sk_flags & SK_SEARCHARRAY) ||
-		   skey->sk_strategy != BTEqualStrategyNumber);
+	Assert(!(arraysk->sk_flags & SK_BT_SKIP));
 
 	/*
 	 * _bt_binsrch_array_skey searches an array for the entry best matching a
@@ -1113,6 +1197,106 @@ _bt_compare_array_scankey_args(IndexScanDesc scan, ScanKey arraysk, ScanKey skey
 }
 
 /*
+ * Preprocessing of skip array scan key, used to determine redundancy against
+ * a non-array scalar scan key (must be an inequality).
+ *
+ * _bt_compare_array_scankey_args helper function.
+ *
+ * Skip arrays work by procedurally generating their elements as needed, so we
+ * just store the inequality as the skip array's low_compare or high_compare
+ * (except when there's already a more restrictive low_compare/high_compare).
+ * The array's final elements are the range of values that still satisfy the
+ * array's final low_compare and high_compare.
+ */
+static bool
+_bt_skiparray_shrink(IndexScanDesc scan, ScanKey skey, BTArrayKeyInfo *array,
+					 bool *qual_ok)
+{
+	bool		test_result;
+
+	Assert(array->num_elems == -1);
+
+	/*
+	 * Array's index attribute will be constrained by a strict operator/key.
+	 * Array must not "contain a NULL element" (i.e. the scan must not apply
+	 * "IS NULL" qual when it reaches the end of the index that stores NULLs).
+	 */
+	array->null_elem = false;
+	*qual_ok = true;
+
+	/*
+	 * Consider if we should treat caller's scalar scan key as the skip
+	 * array's high_compare or low_compare.
+	 *
+	 * In general the current array element must either be a copy of a value
+	 * taken from an index tuple, or a derivative value generated by opclass's
+	 * skip support function.  That way the scan can always safely assume that
+	 * it's okay to use the only-input-opclass-type proc from so->orderProcs[]
+	 * (they can be cross-type with SAOP arrays, but never with skip arrays).
+	 *
+	 * This approach is enabled by MINVAL/MAXVAL sentinel key markings, which
+	 * can be thought of as representing either the lowest or highest matching
+	 * array element (excluding the NULL element, where applicable, though as
+	 * just discussed it isn't applicable to this range skip array anyway).
+	 * Array keys marked MINVAL/MAXVAL never have a valid datum in their
+	 * sk_argument field.  The scan directly applies the array's low_compare
+	 * key when it encounters MINVAL in the array key proper (just as it
+	 * applies high_compare when it sees MAXVAL set in the array key proper).
+	 * The scan must never use the array's so->orderProcs[] proc against
+	 * low_compare's/high_compare's sk_argument, either (so->orderProcs[] is
+	 * only intended to be used with rhs datums from the array proper/index).
+	 */
+	switch (skey->sk_strategy)
+	{
+		case BTLessStrategyNumber:
+		case BTLessEqualStrategyNumber:
+			if (array->high_compare)
+			{
+				/* replace existing high_compare with caller's key? */
+				if (!_bt_compare_scankey_args(scan, array->high_compare, skey,
+											  array->high_compare, NULL, NULL,
+											  &test_result))
+					return false;	/* can't determine more restrictive key */
+
+				if (!test_result)
+					return true;	/* no, just discard caller's key */
+
+				/* yes, replace existing high_compare with caller's key */
+			}
+
+			/* caller's key becomes skip array's high_compare */
+			array->high_compare = skey;
+			break;
+		case BTGreaterEqualStrategyNumber:
+		case BTGreaterStrategyNumber:
+			if (array->low_compare)
+			{
+				/* replace existing low_compare with caller's key? */
+				if (!_bt_compare_scankey_args(scan, array->low_compare, skey,
+											  array->low_compare, NULL, NULL,
+											  &test_result))
+					return false;	/* can't determine more restrictive key */
+
+				if (!test_result)
+					return true;	/* no, just discard caller's key */
+
+				/* yes, replace existing low_compare with caller's key */
+			}
+
+			/* caller's key becomes skip array's low_compare */
+			array->low_compare = skey;
+			break;
+		case BTEqualStrategyNumber:
+		default:
+			elog(ERROR, "unrecognized StrategyNumber: %d",
+				 (int) skey->sk_strategy);
+			break;
+	}
+
+	return true;
+}
+
+/*
  *	_bt_preprocess_array_keys() -- Preprocess SK_SEARCHARRAY scan keys
  *
  * If there are any SK_SEARCHARRAY scan keys, deconstruct the array(s) and
@@ -1137,6 +1321,12 @@ _bt_compare_array_scankey_args(IndexScanDesc scan, ScanKey arraysk, ScanKey skey
  * one equality strategy array scan key per index attribute.  We'll always be
  * able to set things up that way when complete opfamilies are used.
  *
+ * We're also responsible for generating skip arrays (and their associated
+ * scan keys) here.  This enables skip scan.  We do this for index attributes
+ * that initially lacked an equality condition within scan->keyData[], iff
+ * doing so allows a later scan key (that was passed to us in scan->keyData[])
+ * to be marked required by our _bt_preprocess_keys caller.
+ *
  * We set the scan key references from the scan's BTArrayKeyInfo info array to
  * offsets into the temp modified input array returned to caller.  Scans that
  * have array keys should call _bt_preprocess_array_keys_final when standard
@@ -1144,50 +1334,46 @@ _bt_compare_array_scankey_args(IndexScanDesc scan, ScanKey arraysk, ScanKey skey
  * references into references to the scan's so->keyData[] output scan keys.
  *
  * Note: the reason we need to return a temp scan key array, rather than just
- * scribbling on scan->keyData, is that callers are permitted to call btrescan
- * without supplying a new set of scankey data.
+ * modifying scan->keyData[], is that callers are permitted to call btrescan
+ * without supplying a new set of scankey data.  Certain other preprocessing
+ * routines (e.g., _bt_fix_scankey_strategy) _can_ modify scan->keyData[], but
+ * we can't make that work here because our modifications are non-idempotent.
  */
 static ScanKey
 _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys)
 {
 	BTScanOpaque so = (BTScanOpaque) scan->opaque;
 	Relation	rel = scan->indexRelation;
-	int			numberOfKeys = scan->numberOfKeys;
 	int16	   *indoption = rel->rd_indoption;
+	Oid			skip_eq_ops[INDEX_MAX_KEYS];
 	int			numArrayKeys,
-				output_ikey = 0;
+				numSkipArrayKeys,
+				numArrayKeyData;
+	AttrNumber	attno_skip = 1;
 	int			origarrayatt = InvalidAttrNumber,
 				origarraykey = -1;
 	Oid			origelemtype = InvalidOid;
-	ScanKey		cur;
 	MemoryContext oldContext;
 	ScanKey		arrayKeyData;	/* modified copy of scan->keyData */
 
-	Assert(numberOfKeys);
-
-	/* Quick check to see if there are any array keys */
-	numArrayKeys = 0;
-	for (int i = 0; i < numberOfKeys; i++)
-	{
-		cur = &scan->keyData[i];
-		if (cur->sk_flags & SK_SEARCHARRAY)
-		{
-			numArrayKeys++;
-			Assert(!(cur->sk_flags & (SK_ROW_HEADER | SK_SEARCHNULL | SK_SEARCHNOTNULL)));
-			/* If any arrays are null as a whole, we can quit right now. */
-			if (cur->sk_flags & SK_ISNULL)
-			{
-				so->qual_ok = false;
-				return NULL;
-			}
-		}
-	}
+	/*
+	 * Check the number of input array keys within scan->keyData[] input keys
+	 * (also checks if we should add extra skip arrays based on input keys)
+	 */
+	numArrayKeys = _bt_num_array_keys(scan, skip_eq_ops, &numSkipArrayKeys);
 
 	/* Quit if nothing to do. */
 	if (numArrayKeys == 0)
 		return NULL;
 
 	/*
+	 * Estimated final size of arrayKeyData[] array we'll return to our caller
+	 * is the size of the original scan->keyData[] input array, plus space for
+	 * any additional skip array scan keys we'll need to generate below
+	 */
+	numArrayKeyData = scan->numberOfKeys + numSkipArrayKeys;
+
+	/*
 	 * Make a scan-lifespan context to hold array-associated data, or reset it
 	 * if we already have one from a previous rescan cycle.
 	 */
@@ -1201,18 +1387,20 @@ _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys)
 	oldContext = MemoryContextSwitchTo(so->arrayContext);
 
 	/* Create output scan keys in the workspace context */
-	arrayKeyData = (ScanKey) palloc(numberOfKeys * sizeof(ScanKeyData));
+	arrayKeyData = (ScanKey) palloc(numArrayKeyData * sizeof(ScanKeyData));
 
 	/* Allocate space for per-array data in the workspace context */
 	so->arrayKeys = (BTArrayKeyInfo *) palloc(numArrayKeys * sizeof(BTArrayKeyInfo));
 
 	/* Allocate space for ORDER procs used to help _bt_checkkeys */
-	so->orderProcs = (FmgrInfo *) palloc(numberOfKeys * sizeof(FmgrInfo));
+	so->orderProcs = (FmgrInfo *) palloc(numArrayKeyData * sizeof(FmgrInfo));
 
-	/* Now process each array key */
 	numArrayKeys = 0;
-	for (int input_ikey = 0; input_ikey < numberOfKeys; input_ikey++)
+	numArrayKeyData = 0;
+	for (int input_ikey = 0; input_ikey < scan->numberOfKeys; input_ikey++)
 	{
+		ScanKey		inkey = scan->keyData + input_ikey,
+					cur;
 		FmgrInfo	sortproc;
 		FmgrInfo   *sortprocp = &sortproc;
 		Oid			elemtype;
@@ -1225,22 +1413,114 @@ _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys)
 		Datum	   *elem_values;
 		bool	   *elem_nulls;
 		int			num_nonnulls;
-		int			j;
+
+		/* set up next output scan key */
+		cur = &arrayKeyData[numArrayKeyData];
+
+		/* Backfill skip arrays for attrs < or <= input key's attr? */
+		while (numSkipArrayKeys && attno_skip <= inkey->sk_attno)
+		{
+			Oid			opfamily = rel->rd_opfamily[attno_skip - 1];
+			Oid			opcintype = rel->rd_opcintype[attno_skip - 1];
+			Oid			collation = rel->rd_indcollation[attno_skip - 1];
+			Oid			eq_op = skip_eq_ops[attno_skip - 1];
+			CompactAttribute *attr;
+			RegProcedure cmp_proc;
+
+			if (!OidIsValid(eq_op))
+			{
+				/*
+				 * Attribute already has an = input key, so don't output a
+				 * skip array for attno_skip.  Just copy attribute's = input
+				 * key into arrayKeyData[] once outside this inner loop.
+				 *
+				 * Note: When we get here there must be a later attribute that
+				 * lacks an equality input key, and still needs a skip array
+				 * (if there wasn't then numSkipArrayKeys would be 0 by now).
+				 */
+				Assert(attno_skip == inkey->sk_attno);
+				/* inkey can't be last input key to be marked required: */
+				Assert(input_ikey < scan->numberOfKeys - 1);
+#if 0
+				/* Could be a redundant input scan key, so can't do this: */
+				Assert(inkey->sk_strategy == BTEqualStrategyNumber ||
+					   (inkey->sk_flags & SK_SEARCHNULL));
+#endif
+
+				attno_skip++;
+				break;
+			}
+
+			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 */
+
+			/*
+			 * We'll need a 3-way ORDER proc.  Set that up now.
+			 */
+			_bt_setup_array_cmp(scan, cur, opcintype,
+								&so->orderProcs[numArrayKeyData], NULL);
+
+			numArrayKeys++;
+			numArrayKeyData++;	/* keep this scan key/array */
+
+			/* set up next output scan key */
+			cur = &arrayKeyData[numArrayKeyData];
+
+			/* remember having output this skip array and scan key */
+			numSkipArrayKeys--;
+			attno_skip++;
+		}
 
 		/*
 		 * Provisionally copy scan key into arrayKeyData[] array we'll return
 		 * to _bt_preprocess_keys caller
 		 */
-		cur = &arrayKeyData[output_ikey];
-		*cur = scan->keyData[input_ikey];
+		*cur = *inkey;
 
 		if (!(cur->sk_flags & SK_SEARCHARRAY))
 		{
-			output_ikey++;		/* keep this non-array scan key */
+			numArrayKeyData++;	/* keep this non-array scan key */
 			continue;
 		}
 
 		/*
+		 * Process SAOP array scan key
+		 */
+		Assert(!(cur->sk_flags & (SK_ROW_HEADER | SK_SEARCHNULL | SK_SEARCHNOTNULL)));
+
+		/* If array is null as a whole, the scan qual is unsatisfiable */
+		if (cur->sk_flags & SK_ISNULL)
+		{
+			so->qual_ok = false;
+			break;
+		}
+
+		/*
 		 * Deconstruct the array into elements
 		 */
 		arrayval = DatumGetArrayTypeP(cur->sk_argument);
@@ -1257,7 +1537,7 @@ _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys)
 		 * all btree operators are strict.
 		 */
 		num_nonnulls = 0;
-		for (j = 0; j < num_elems; j++)
+		for (int j = 0; j < num_elems; j++)
 		{
 			if (!elem_nulls[j])
 				elem_values[num_nonnulls++] = elem_values[j];
@@ -1295,7 +1575,7 @@ _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys)
 					_bt_find_extreme_element(scan, cur, elemtype,
 											 BTGreaterStrategyNumber,
 											 elem_values, num_nonnulls);
-				output_ikey++;	/* keep this transformed scan key */
+				numArrayKeyData++;	/* keep this transformed scan key */
 				continue;
 			case BTEqualStrategyNumber:
 				/* proceed with rest of loop */
@@ -1306,7 +1586,7 @@ _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys)
 					_bt_find_extreme_element(scan, cur, elemtype,
 											 BTLessStrategyNumber,
 											 elem_values, num_nonnulls);
-				output_ikey++;	/* keep this transformed scan key */
+				numArrayKeyData++;	/* keep this transformed scan key */
 				continue;
 			default:
 				elog(ERROR, "unrecognized StrategyNumber: %d",
@@ -1323,7 +1603,7 @@ _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys)
 		 * sortproc just points to the same proc used during binary searches.
 		 */
 		_bt_setup_array_cmp(scan, cur, elemtype,
-							&so->orderProcs[output_ikey], &sortprocp);
+							&so->orderProcs[numArrayKeyData], &sortprocp);
 
 		/*
 		 * Sort the non-null elements and eliminate any duplicates.  We must
@@ -1392,23 +1672,24 @@ _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys)
 			origelemtype = elemtype;
 		}
 
-		/*
-		 * And set up the BTArrayKeyInfo data.
-		 *
-		 * Note: _bt_preprocess_array_keys_final will fix-up each array's
-		 * scan_key field later on, after so->keyData[] has been finalized.
-		 */
-		so->arrayKeys[numArrayKeys].scan_key = output_ikey;
+		/* Initialize generic BTArrayKeyInfo fields */
+		so->arrayKeys[numArrayKeys].scan_key = numArrayKeyData;
 		so->arrayKeys[numArrayKeys].num_elems = num_elems;
+
+		/* Initialize SAOP array specific BTArrayKeyInfo fields */
 		so->arrayKeys[numArrayKeys].elem_values = elem_values;
+		so->arrayKeys[numArrayKeys].cur_elem = -1;	/* i.e. invalid */
+
 		numArrayKeys++;
-		output_ikey++;			/* keep this scan key/array */
+		numArrayKeyData++;		/* keep this scan key/array */
 	}
 
+	Assert(numSkipArrayKeys == 0);
+
 	/* Set final number of equality-type array keys */
 	so->numArrayKeys = numArrayKeys;
-	/* Set number of scan keys remaining in arrayKeyData[] */
-	*new_numberOfKeys = output_ikey;
+	/* Set number of scan keys in arrayKeyData[] */
+	*new_numberOfKeys = numArrayKeyData;
 
 	MemoryContextSwitchTo(oldContext);
 
@@ -1514,7 +1795,14 @@ _bt_preprocess_array_keys_final(IndexScanDesc scan, int *keyDataMap)
 		{
 			BTArrayKeyInfo *array = &so->arrayKeys[arrayidx];
 
-			Assert(array->num_elems > 0);
+			/*
+			 * 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));
 
 			if (array->scan_key == input_ikey)
 			{
@@ -1576,6 +1864,199 @@ _bt_preprocess_array_keys_final(IndexScanDesc scan, int *keyDataMap)
 }
 
 /*
+ *	_bt_num_array_keys() -- determine # of BTArrayKeyInfo entries
+ *
+ * _bt_preprocess_array_keys helper function.  Returns the estimated size of
+ * the scan's BTArrayKeyInfo array, which is guaranteed to be large enough to
+ * fit every so->arrayKeys[] entry.
+ *
+ * Also sets *numSkipArrayKeys_out to the number of 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
+ */
+static int
+_bt_num_array_keys(IndexScanDesc scan, Oid *skip_eq_ops_out,
+				   int *numSkipArrayKeys_out)
+{
+	Relation	rel = scan->indexRelation;
+	AttrNumber	attno_skip = 1,
+				attno_inkey = 1;
+	bool		attno_has_equal = false,
+				attno_has_rowcompare = false;
+	int			numSAOPArrayKeys,
+				numSkipArrayKeys,
+				prev_numSkipArrayKeys;
+
+	Assert(scan->numberOfKeys);
+
+	/* Initial pass over input scan keys counts the number of SAOP arrays */
+	numSAOPArrayKeys = 0;
+	*numSkipArrayKeys_out = prev_numSkipArrayKeys = numSkipArrayKeys = 0;
+	for (int i = 0; i < scan->numberOfKeys; i++)
+	{
+		ScanKey		inkey = scan->keyData + i;
+
+		if (inkey->sk_flags & SK_SEARCHARRAY)
+			numSAOPArrayKeys++;
+	}
+
+#ifdef DEBUG_DISABLE_SKIP_SCAN
+	/* don't attempt to add skip arrays */
+	return numSAOPArrayKeys;
+#endif
+
+	for (int i = 0;; i++)
+	{
+		ScanKey		inkey = scan->keyData + i;
+
+		/*
+		 * 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++;
+		}
+
+		prev_numSkipArrayKeys = numSkipArrayKeys;
+
+		/*
+		 * Stop once past the final input scan key.  We deliberately never add
+		 * a skip array for the last input scan key's attribute -- even when
+		 * there are only inequality keys on that attribute.
+		 */
+		if (i == scan->numberOfKeys)
+			break;
+
+		/*
+		 * 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.
+		 * Alternative designs that can be used alongside skip arrays are
+		 * possible, but it's not clear that they're really worth pursuing.
+		 *
+		 * A RowCompare qual "(a, b, c) > (10, 'foo', 42)" is equivalent to
+		 * "(a=10 AND b='foo' AND c>42) OR (a=10 AND b>'foo') OR (a>10)".
+		 * Decomposing this RowCompare into these 3 disjuncts allows each
+		 * disjunct to be executed as a separate "single value" index scan.
+		 * That'll give all 3 scans the ability to add skip arrays in the
+		 * usual way (when there are any scalar keys after the RowCompare).
+		 * Under this scheme, a qual "(a, b, c) > (10, 'foo', 42) AND d = 99"
+		 * performs 3 separate scans, each of which can mark keys up to and
+		 * including its "d = 99" key as required to continue the scan.
+		 */
+		if (attno_has_rowcompare)
+			break;
+
+		/*
+		 * Now consider next attno_inkey (or keep going if this is an
+		 * additional scan key against the same attribute)
+		 */
+		if (attno_inkey < inkey->sk_attno)
+		{
+			/*
+			 * Now add skip array for previous scan key's attribute, though
+			 * only if the attribute has no equality strategy scan keys
+			 */
+			if (attno_has_equal)
+			{
+				/* Attributes with an = key must have InvalidOid eq_op set */
+				skip_eq_ops_out[attno_skip - 1] = InvalidOid;
+			}
+			else
+			{
+				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]))
+				{
+					/*
+					 * Input opclass lacks an equality strategy operator, so
+					 * don't generate a skip array that definitely won't work
+					 */
+					break;
+				}
+
+				/* plan on adding a backfill skip array for this attribute */
+				numSkipArrayKeys++;
+			}
+
+			/* Set things up for this new attribute */
+			attno_skip++;
+			attno_inkey = inkey->sk_attno;
+			attno_has_equal = false;
+		}
+
+		/*
+		 * Track if this attribute's scan keys include any equality strategy
+		 * scan keys (IS NULL keys count as equality keys here).  Also track
+		 * if it has any RowCompare keys.
+		 */
+		if (inkey->sk_strategy == BTEqualStrategyNumber ||
+			(inkey->sk_flags & SK_SEARCHNULL))
+			attno_has_equal = true;
+		if (inkey->sk_flags & SK_ROW_HEADER)
+			attno_has_rowcompare = true;
+	}
+
+	*numSkipArrayKeys_out = numSkipArrayKeys;
+	return numSAOPArrayKeys + numSkipArrayKeys;
+}
+
+/*
  * _bt_find_extreme_element() -- get least or greatest array element
  *
  * scan and skey identify the index column, whose opfamily determines the