v19-0003-Add-skipskip-nbtree-skip-scan-optimization.patch

From a2fc33978acfb6bd440685d855e50ee28466e3cf Mon Sep 17 00:00:00 2001
From: Peter Geoghegan <pg@bowt.ie>
Date: Sat, 16 Nov 2024 15:58:41 -0500
Subject: [PATCH v19 3/3] Add "skipskip" nbtree skip scan optimization.

Fix regressions in cases that are nominally eligible to use skip scan
but can never actually benefit from skipping.  These are cases where the
leading skipped prefix column contains many distinct values -- often as
many distinct values are there are total index tuples.

For example, the test case posted here is fixed by the work from this
commit:

https://postgr.es/m/51d00219180323d121572e1f83ccde2a@oss.nttdata.com

Note that this commit doesn't actually change anything about when or how
skip scan decides when or how to skip.  It just avoids wasting CPU
cycles on uselessly maintaining a skip array at the tuple granularity,
preferring to maintain the skip arrays at something closer to the page
granularity when that makes sense.  See:

https://www.postgresql.org/message-id/flat/CAH2-Wz%3DE7XrkvscBN0U6V81NK3Q-dQOmivvbEsjG-zwEfDdFpg%40mail.gmail.com#7d34e8aa875d7a718043834c5ef4c167

Doing well on cases like this is important because we can't expect the
optimizer to never choose an affected plan -- we prefer to solve these
problems in the executor, which has access to the most reliable and
current information about the index.  The optimizer can afford to be
very optimistic about skipping if actual runtime scan behavior is very
similar to a traditional full index scan in the worst case.  See
"optimizer" section from the original intro mail for more information:

https://postgr.es/m/CAH2-Wzmn1YsLzOGgjAQZdn1STSG_y8qP__vggTaPAYXJP%2BG4bw%40mail.gmail.com

Author: Peter Geoghegan <pg@bowt.ie>
Reviewed-By: Masahiro Ikeda <ikedamsh@oss.nttdata.com>
Discussion: https://postgr.es/m/CAH2-Wz=Y93jf5WjoOsN=xvqpMjRy-bxCE037bVFi-EasrpeUJA@mail.gmail.com
---
 src/include/access/nbtree.h           |   9 ++
 src/backend/access/nbtree/nbtree.c    |   1 +
 src/backend/access/nbtree/nbtsearch.c |  51 ++++++-
 src/backend/access/nbtree/nbtutils.c  | 206 +++++++++++++++++++++++---
 4 files changed, 238 insertions(+), 29 deletions(-)

diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h
index d841e85bc..e3b6f200d 100644
--- a/src/include/access/nbtree.h
+++ b/src/include/access/nbtree.h
@@ -1051,6 +1051,7 @@ typedef struct BTScanOpaqueData
 
 	/* workspace for SK_SEARCHARRAY support */
 	int			numArrayKeys;	/* number of equality-type array keys */
+	bool		skipScan;		/* At least one skip array in arrayKeys[]? */
 	bool		needPrimScan;	/* New prim scan to continue in current dir? */
 	bool		scanBehind;		/* Last array advancement matched -inf attr? */
 	bool		oppositeDirCheck;	/* explicit scanBehind recheck needed? */
@@ -1111,6 +1112,14 @@ typedef struct BTReadPageState
 	bool		prechecked;		/* precheck set continuescan to 'true'? */
 	bool		firstmatch;		/* at least one match so far?  */
 
+	/*
+	 * Input and output parameters, set and unset by both _bt_readpage and
+	 * _bt_checkkeys to manage "skipskip" optimization during skip scans
+	 */
+	bool		skipskip;
+	bool		noskipskip;
+	bool		advanced;
+
 	/*
 	 * Private _bt_checkkeys state used to manage "look ahead" optimization
 	 * (only used during scans with array keys)
diff --git a/src/backend/access/nbtree/nbtree.c b/src/backend/access/nbtree/nbtree.c
index 294eb1eb4..c96d7a446 100644
--- a/src/backend/access/nbtree/nbtree.c
+++ b/src/backend/access/nbtree/nbtree.c
@@ -423,6 +423,7 @@ btrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
 		memcpy(scan->keyData, scankey, scan->numberOfKeys * sizeof(ScanKeyData));
 	so->numberOfKeys = 0;		/* until _bt_preprocess_keys sets it */
 	so->numArrayKeys = 0;		/* ditto */
+	so->skipScan = false;		/* ditto */
 }
 
 /*
diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c
index 43e321896..b88db6afe 100644
--- a/src/backend/access/nbtree/nbtsearch.c
+++ b/src/backend/access/nbtree/nbtsearch.c
@@ -1644,6 +1644,27 @@ _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum,
 	pstate.continuescan = true; /* default assumption */
 	pstate.prechecked = false;
 	pstate.firstmatch = false;
+
+	/*
+	 * Initialize "skipskip" optimization state (used only during scans with
+	 * skip arrays).
+	 *
+	 * Skip scans use this to manage the overhead of maintaining skip arrays
+	 * on columns with many distinct values.  It also works as a substitute
+	 * for the pstate.prechecked optimization, which skip scan never uses.
+	 *
+	 * We never do this for the first page read by each primitive scan.  This
+	 * avoids slowing down queries with skip arrays that have relatively few
+	 * distinct values -- the "look ahead" optimization is preferred there.
+	 */
+	pstate.skipskip = false;
+	pstate.noskipskip = firstPage;
+	pstate.advanced = false;
+
+	/*
+	 * Initialize "look ahead" optimization state (used only during scans with
+	 * arrays, including those that just use skip arrays)
+	 */
 	pstate.rechecks = 0;
 	pstate.targetdistance = 0;
 
@@ -1660,10 +1681,10 @@ _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum,
 	 * corresponding value from the last item on the page.  So checking with
 	 * the last item on the page would give a more precise answer.
 	 *
-	 * We skip this for the first page read by each (primitive) scan, to avoid
-	 * slowing down point queries.  They typically don't stand to gain much
-	 * when the optimization can be applied, and are more likely to notice the
-	 * overhead of the precheck.
+	 * We don't do this for the first page read by each (primitive) scan, to
+	 * avoid slowing down point queries.  They typically don't stand to gain
+	 * much when the optimization can be applied, and are more likely to
+	 * notice the overhead of the precheck.  Also avoid it during skip scans.
 	 *
 	 * The optimization is unsafe and must be avoided whenever _bt_checkkeys
 	 * just set a low-order required array's key to the best available match
@@ -1687,7 +1708,7 @@ _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum,
 	 * required < or <= strategy scan keys) during the precheck, we can safely
 	 * assume that this must also be true of all earlier tuples from the page.
 	 */
-	if (!firstPage && !so->scanBehind && minoff < maxoff)
+	if (!firstPage && !so->skipScan && !so->scanBehind && minoff < maxoff)
 	{
 		ItemId		iid;
 		IndexTuple	itup;
@@ -1837,6 +1858,16 @@ _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum,
 
 			truncatt = BTreeTupleGetNAtts(itup, rel);
 			pstate.prechecked = false;	/* precheck didn't cover HIKEY */
+			if (pstate.skipskip)
+			{
+				/*
+				 * reset array keys for finaltup call, since skipskip
+				 * optimization prevented ordinary array maintenance
+				 */
+				Assert(so->skipScan);
+				_bt_start_array_keys(scan, dir);
+				pstate.skipskip = false;
+			}
 			_bt_checkkeys(scan, &pstate, arrayKeys, itup, truncatt);
 		}
 
@@ -1897,6 +1928,16 @@ _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum,
 			Assert(!BTreeTupleIsPivot(itup));
 
 			pstate.offnum = offnum;
+			if (offnum == minoff && pstate.skipskip)
+			{
+				/*
+				 * reset array keys for finaltup call, since skipskip
+				 * optimization prevented ordinary array maintenance
+				 */
+				Assert(so->skipScan);
+				_bt_start_array_keys(scan, dir);
+				pstate.skipskip = false;
+			}
 			passes_quals = _bt_checkkeys(scan, &pstate, arrayKeys,
 										 itup, indnatts);
 
diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c
index a40635998..a1089e5e4 100644
--- a/src/backend/access/nbtree/nbtutils.c
+++ b/src/backend/access/nbtree/nbtutils.c
@@ -151,13 +151,16 @@ static bool _bt_fix_scankey_strategy(ScanKey skey, int16 *indoption);
 static void _bt_mark_scankey_required(ScanKey skey);
 static bool _bt_check_compare(IndexScanDesc scan, ScanDirection dir,
 							  IndexTuple tuple, int tupnatts, TupleDesc tupdesc,
-							  bool advancenonrequired, bool prechecked, bool firstmatch,
+							  bool advancenonrequired, bool skipskip,
+							  bool prechecked, bool firstmatch,
 							  bool *continuescan, int *ikey);
 static bool _bt_check_rowcompare(ScanKey skey,
 								 IndexTuple tuple, int tupnatts, TupleDesc tupdesc,
 								 ScanDirection dir, bool *continuescan);
 static void _bt_checkkeys_look_ahead(IndexScanDesc scan, BTReadPageState *pstate,
-									 int tupnatts, TupleDesc tupdesc);
+									 IndexTuple tuple, int tupnatts, TupleDesc tupdesc);
+static bool _bt_checkkeys_skipskip(IndexScanDesc scan, BTReadPageState *pstate,
+								   IndexTuple tuple, TupleDesc tupdesc);
 static int	_bt_keep_natts(Relation rel, IndexTuple lastleft,
 						   IndexTuple firstright, BTScanInsert itup_key);
 
@@ -354,6 +357,7 @@ _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys)
 	 */
 	numArrayKeys = _bt_preprocess_num_array_keys(scan, skipatts,
 												 &numSkipArrayKeys);
+	so->skipScan = (numSkipArrayKeys > 0);
 
 	/* Quit if nothing to do. */
 	if (numArrayKeys == 0)
@@ -3205,8 +3209,6 @@ _bt_advance_array_keys(IndexScanDesc scan, BTReadPageState *pstate,
 
 		if (cur->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD))
 		{
-			Assert(sktrig_required);
-
 			required = true;
 
 			if (cur->sk_attno > tupnatts)
@@ -3353,7 +3355,7 @@ _bt_advance_array_keys(IndexScanDesc scan, BTReadPageState *pstate,
 		}
 		else
 		{
-			Assert(sktrig_required && required);
+			Assert(required);
 
 			/*
 			 * This is a required non-array equality strategy scan key, which
@@ -3395,7 +3397,7 @@ _bt_advance_array_keys(IndexScanDesc scan, BTReadPageState *pstate,
 		 * be eliminated by _bt_preprocess_keys.  It won't matter if some of
 		 * our "true" array scan keys (or even all of them) are non-required.
 		 */
-		if (required &&
+		if (sktrig_required && required &&
 			((ScanDirectionIsForward(dir) && result > 0) ||
 			 (ScanDirectionIsBackward(dir) && result < 0)))
 			beyond_end_advance = true;
@@ -3410,7 +3412,7 @@ _bt_advance_array_keys(IndexScanDesc scan, BTReadPageState *pstate,
 			 * array scan keys are considered interesting.)
 			 */
 			all_satisfied = false;
-			if (required)
+			if (sktrig_required && required)
 				all_required_satisfied = false;
 			else
 			{
@@ -3522,7 +3524,7 @@ _bt_advance_array_keys(IndexScanDesc scan, BTReadPageState *pstate,
 
 		/* Recheck _bt_check_compare on behalf of caller */
 		if (_bt_check_compare(scan, dir, tuple, tupnatts, tupdesc,
-							  false, false, false,
+							  false, !sktrig_required, false, false,
 							  &continuescan, &nsktrig) &&
 			!so->scanBehind)
 		{
@@ -3591,6 +3593,9 @@ _bt_advance_array_keys(IndexScanDesc scan, BTReadPageState *pstate,
 		return false;
 	}
 
+	/* _bt_readpage must have unset skipskip flag (for finaltup call) */
+	Assert(!pstate->skipskip);
+
 	/*
 	 * Postcondition array state assertion (for still-unsatisfied tuples).
 	 *
@@ -3760,6 +3765,23 @@ _bt_advance_array_keys(IndexScanDesc scan, BTReadPageState *pstate,
 		pstate->skip = pstate->maxoff + 1;
 	}
 
+	/*
+	 * Optimization: if a scan with a skip array doesn't satisfy every
+	 * required key (in practice this is almost always all the scan's keys),
+	 * we assume that this page isn't likely to skip "within" a page using
+	 * _bt_checkkeys_look_ahead.  We'll apply the 'skipskip' optimization.
+	 *
+	 * The 'skipskip' optimization allows _bt_checkkeys/_bt_check_compare to
+	 * stop maintaining the scan's skip arrays until we've reached finaltup.
+	 */
+	else if (so->skipScan && !pstate->noskipskip && pstate->advanced &&
+			 _bt_checkkeys_skipskip(scan, pstate, tuple, tupdesc))
+	{
+		pstate->skipskip = true;
+	}
+
+	pstate->advanced = true;	/* remember arrays advanced on page */
+
 	/* Caller's tuple doesn't match the new qual */
 	return false;
 
@@ -3861,7 +3883,8 @@ end_toplevel_scan:
  * make the scan much more efficient: if there are few distinct values in "x",
  * we'll be able to skip over many irrelevant leaf pages.  (If on the other
  * hand there are many distinct values in "x" then the scan will degenerate
- * into a full index scan at run time.)
+ * into a full index scan at run time, but we'll be no worse off overall.
+ * _bt_checkkeys's 'skipskip' optimization keeps the runtime overhead low.)
  *
  * If possible, redundant keys are eliminated: we keep only the tightest
  * >/>= bound and the tightest </<= bound, and if there's an = key then
@@ -4903,7 +4926,8 @@ _bt_checkkeys(IndexScanDesc scan, BTReadPageState *pstate, bool arrayKeys,
 	Assert(BTreeTupleGetNAtts(tuple, scan->indexRelation) == tupnatts);
 
 	res = _bt_check_compare(scan, dir, tuple, tupnatts, tupdesc,
-							arrayKeys, pstate->prechecked, pstate->firstmatch,
+							arrayKeys, pstate->skipskip,
+							pstate->prechecked, pstate->firstmatch,
 							&pstate->continuescan, &ikey);
 
 #ifdef USE_ASSERT_CHECKING
@@ -4915,7 +4939,8 @@ _bt_checkkeys(IndexScanDesc scan, BTReadPageState *pstate, bool arrayKeys,
 		 * Assert that the scan isn't in danger of becoming confused.
 		 */
 		Assert(!so->scanBehind && !so->oppositeDirCheck);
-		Assert(!pstate->prechecked && !pstate->firstmatch);
+		Assert(!pstate->skipskip && !pstate->prechecked &&
+			   !pstate->firstmatch);
 		Assert(!_bt_tuple_before_array_skeys(scan, dir, tuple, tupdesc,
 											 tupnatts, false, 0, NULL));
 	}
@@ -4929,7 +4954,7 @@ _bt_checkkeys(IndexScanDesc scan, BTReadPageState *pstate, bool arrayKeys,
 		 * get the same answer without those optimizations
 		 */
 		Assert(res == _bt_check_compare(scan, dir, tuple, tupnatts, tupdesc,
-										false, false, false,
+										false, pstate->skipskip, false, false,
 										&dcontinuescan, &dikey));
 		Assert(pstate->continuescan == dcontinuescan);
 	}
@@ -5002,7 +5027,8 @@ _bt_checkkeys(IndexScanDesc scan, BTReadPageState *pstate, bool arrayKeys,
 			if (pstate->rechecks >= LOOK_AHEAD_REQUIRED_RECHECKS)
 			{
 				/* See if we should skip ahead within the current leaf page */
-				_bt_checkkeys_look_ahead(scan, pstate, tupnatts, tupdesc);
+				_bt_checkkeys_look_ahead(scan, pstate, tuple, tupnatts,
+										 tupdesc);
 
 				/*
 				 * Might have set pstate.skip to a later page offset.  When
@@ -5060,7 +5086,7 @@ _bt_oppodir_checkkeys(IndexScanDesc scan, ScanDirection dir,
 	Assert(so->numArrayKeys);
 
 	_bt_check_compare(scan, flipped, finaltup, nfinaltupatts, tupdesc,
-					  false, false, false, &continuescan, &ikey);
+					  false, false, false, false, &continuescan, &ikey);
 
 	if (!continuescan && so->keyData[ikey].sk_strategy != BTEqualStrategyNumber)
 		return false;
@@ -5099,17 +5125,24 @@ _bt_oppodir_checkkeys(IndexScanDesc scan, ScanDirection dir,
  *
  * Though we advance non-required array keys on our own, that shouldn't have
  * any lasting consequences for the scan.  By definition, non-required arrays
- * have no fixed relationship with the scan's progress.  (There are delicate
- * considerations for non-required arrays when the arrays need to be advanced
- * following our setting continuescan to false, but that doesn't concern us.)
+ * have no fixed relationship with the scan's progress.  (skipskip=true makes
+ * us treat required scan keys as non-required, though.  That's safe because
+ * _bt_readpage will account for our failure to fully maintain the scan's
+ * arrays later on, right before its finaltup call to _bt_checkkeys.)
  *
  * Pass advancenonrequired=false to avoid all array related side effects.
  * This allows _bt_advance_array_keys caller to avoid infinite recursion.
+ *
+ * Pass skipskip=true to instruct us to skip all of the scan's skip arrays.
+ * This provides the scan with a way of keeping the cost of maintaining its
+ * skip arrays under control, given skip arrays on high cardinality columns
+ * (i.e. given a skip array on a column which isn't a good fit for skip scan).
  */
 static bool
 _bt_check_compare(IndexScanDesc scan, ScanDirection dir,
 				  IndexTuple tuple, int tupnatts, TupleDesc tupdesc,
-				  bool advancenonrequired, bool prechecked, bool firstmatch,
+				  bool advancenonrequired, bool skipskip,
+				  bool prechecked, bool firstmatch,
 				  bool *continuescan, int *ikey)
 {
 	BTScanOpaque so = (BTScanOpaque) scan->opaque;
@@ -5126,10 +5159,18 @@ _bt_check_compare(IndexScanDesc scan, ScanDirection dir,
 
 		/*
 		 * Check if the key is required in the current scan direction, in the
-		 * opposite scan direction _only_, or in neither direction
+		 * opposite scan direction _only_, or in neither direction (except
+		 * when reading a page that's now using the "skipskip" optimization)
 		 */
-		if (((key->sk_flags & SK_BT_REQFWD) && ScanDirectionIsForward(dir)) ||
-			((key->sk_flags & SK_BT_REQBKWD) && ScanDirectionIsBackward(dir)))
+		if (skipskip)
+		{
+			Assert(!prechecked);
+
+			if (key->sk_flags & SK_BT_SKIP)
+				continue;
+		}
+		else if (((key->sk_flags & SK_BT_REQFWD) && ScanDirectionIsForward(dir)) ||
+				 ((key->sk_flags & SK_BT_REQBKWD) && ScanDirectionIsBackward(dir)))
 			requiredSameDir = true;
 		else if (((key->sk_flags & SK_BT_REQFWD) && ScanDirectionIsBackward(dir)) ||
 				 ((key->sk_flags & SK_BT_REQBKWD) && ScanDirectionIsForward(dir)))
@@ -5241,7 +5282,7 @@ _bt_check_compare(IndexScanDesc scan, ScanDirection dir,
 				 * (_bt_advance_array_keys also relies on this behavior during
 				 * forward scans.)
 				 */
-				if ((key->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) &&
+				if ((requiredSameDir || requiredOppositeDirOnly) &&
 					ScanDirectionIsBackward(dir))
 					*continuescan = false;
 			}
@@ -5259,7 +5300,7 @@ _bt_check_compare(IndexScanDesc scan, ScanDirection dir,
 				 * (_bt_advance_array_keys also relies on this behavior during
 				 * backward scans.)
 				 */
-				if ((key->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) &&
+				if ((requiredSameDir || requiredOppositeDirOnly) &&
 					ScanDirectionIsForward(dir))
 					*continuescan = false;
 			}
@@ -5511,13 +5552,19 @@ _bt_check_rowcompare(ScanKey skey, IndexTuple tuple, int tupnatts,
  */
 static void
 _bt_checkkeys_look_ahead(IndexScanDesc scan, BTReadPageState *pstate,
-						 int tupnatts, TupleDesc tupdesc)
+						 IndexTuple tuple, int tupnatts, TupleDesc tupdesc)
 {
 	BTScanOpaque so = (BTScanOpaque) scan->opaque;
 	ScanDirection dir = so->currPos.dir;
 	OffsetNumber aheadoffnum;
 	IndexTuple	ahead;
 
+	/*
+	 * The "look ahead" skipping mechanism cannot be used at the same time as
+	 * skip scan's similar "skipskip" mechanism
+	 */
+	Assert(!pstate->skipskip);
+
 	/* Avoid looking ahead when comparing the page high key */
 	if (pstate->offnum < pstate->minoff)
 		return;
@@ -5563,6 +5610,9 @@ _bt_checkkeys_look_ahead(IndexScanDesc scan, BTReadPageState *pstate,
 			pstate->skip = aheadoffnum + 1;
 		else
 			pstate->skip = aheadoffnum - 1;
+
+		/* Don't attempt skipskip optimization on this page from here on */
+		pstate->noskipskip = true;
 	}
 	else
 	{
@@ -5575,9 +5625,117 @@ _bt_checkkeys_look_ahead(IndexScanDesc scan, BTReadPageState *pstate,
 		 */
 		pstate->rechecks = 0;
 		pstate->targetdistance = Max(pstate->targetdistance / 8, 1);
+
+		/*
+		 * During skip scan (when skip arrays are in use), pages containing
+		 * tuple where an omitted prefix column (a column corresponding to a
+		 * skip array) has many distinct values are a challenge.
+		 *
+		 * The 'skipskip' optimization allows _bt_checkkeys/_bt_check_compare
+		 * to stop maintaining the scan's skip arrays until we've reached
+		 * finaltup.
+		 */
+		if (so->skipScan && !pstate->noskipskip)
+		{
+			if (_bt_checkkeys_skipskip(scan, pstate, tuple, tupdesc))
+				pstate->skipskip = true;
+		}
 	}
 }
 
+/*
+ * Can _bt_checkkeys/_bt_check_compare apply the 'skipskip' optimization?
+ *
+ * Return value indicates if the optimization is safe for the tuples on the
+ * page after caller's tuple, but before its page's finaltup.
+ */
+static bool
+_bt_checkkeys_skipskip(IndexScanDesc scan, BTReadPageState *pstate,
+					   IndexTuple tuple, TupleDesc tupdesc)
+{
+	BTScanOpaque so = (BTScanOpaque) scan->opaque;
+	Relation	rel = scan->indexRelation;
+	ScanDirection dir = so->currPos.dir;
+	IndexTuple	finaltup = pstate->finaltup;
+	int			arrayidx = 0,
+				nfinaltupatts = 0;
+	bool		rangearrayseen = false;
+
+	Assert(!BTreeTupleIsPivot(tuple));
+	Assert(tuple != finaltup);
+
+	if (finaltup)
+		nfinaltupatts = BTreeTupleGetNAtts(finaltup, rel);
+	for (int ikey = 0; ikey < so->numberOfKeys; ikey++)
+	{
+		ScanKey		cur = so->keyData + ikey;
+		BTArrayKeyInfo *array = NULL;
+		Datum		tupdatum;
+		bool		tupnull;
+		int32		result;
+
+		/*
+		 * Only need to check range skip arrays within this loop.
+		 *
+		 * A SAOP array can always be treated as a non-required array within
+		 * _bt_check_compare.  A skip array without a lower or upper bound is
+		 * always safe to skip within _bt_check_compare, since it is satisfied
+		 * by every possible value.
+		 */
+		if (cur->sk_strategy != BTEqualStrategyNumber)
+			continue;
+		if (!(cur->sk_flags & SK_SEARCHARRAY))
+			continue;
+		array = &so->arrayKeys[arrayidx++];
+		Assert(array->scan_key == ikey);
+		if (array->num_elems != -1 || array->null_elem)
+			continue;
+
+		/*
+		 * Found a range skip array to test.
+		 *
+		 * Scans with more than one range skip array are not eligible to use
+		 * the optimization.  Note that we support the skipskip optimization
+		 * for a qual like "WHERE a BETWEEN 1 AND 10 AND b BETWEEN 1 AND 3",
+		 * since there the qual actually requires only a single skip array.
+		 * However, if such a qual ended with "... AND C > 42", then it will
+		 * prevent use of the skipskip optimization.
+		 */
+		if (rangearrayseen)
+			return false;
+
+		/*
+		 * Don't attempt the optimization when we have a skip array and are
+		 * reading the rightmost leaf page (or the leftmost leaf page, when
+		 * scanning backwards)
+		 */
+		if (!finaltup)
+			return false;
+		rangearrayseen = true;
+
+		/* test the tuple that just advanced arrays within our caller */
+		Assert(cur->sk_flags & SK_BT_SKIP);
+		Assert(cur->sk_flags & SK_BT_REQFWD);
+		tupdatum = index_getattr(tuple, cur->sk_attno, tupdesc, &tupnull);
+		_bt_binsrch_skiparray_skey(&so->orderProcs[ikey], false, dir,
+								   tupdatum, tupnull, array, cur, &result);
+		if (result != 0)
+			return false;
+
+		/* test the page's finaltup iff relevant attribute isn't truncated */
+		if (cur->sk_attno > nfinaltupatts)
+			continue;
+
+		tupdatum = index_getattr(finaltup, cur->sk_attno, tupdesc, &tupnull);
+		_bt_binsrch_skiparray_skey(&so->orderProcs[ikey], false, dir,
+								   tupdatum, tupnull, array, cur, &result);
+		if (result != 0)
+			return false;
+	}
+
+	return true;
+}
+
 /*
  * _bt_killitems - set LP_DEAD state for items an indexscan caller has
  * told us were killed
-- 
2.45.2