v10-0002-Add-skip-scan-to-nbtree.patch

From bc36c046ee40532f17d3419abea9dbac15ba836d Mon Sep 17 00:00:00 2001
From: Peter Geoghegan <pg@bowt.ie>
Date: Tue, 16 Apr 2024 13:21:36 -0400
Subject: [PATCH v10 2/2] Add skip scan to nbtree.

Skip scan allows nbtree index scans to efficiently use a composite index
on the columns (a, b) for queries with a qual "WHERE b = 5".  This is
useful in cases where the total number of distinct values in the column
'a' is reasonably small (think hundreds, possibly thousands).  In
effect, a skip scan treats the composite index on (a, b) as if it was a
series of disjunct subindexes -- one subindex per distinct 'a' value.

The scan exhaustively "searches every subindex" by using a qual that
behaves like "WHERE a = ANY(<every possible 'a' value>) AND b = 5".
This works by extending the design for arrays established by commit
5bf748b8.  "Skip arrays" generate their array values procedurally and
on-demand, but otherwise work just like conventional SAOP arrays.

The core B-Tree operator classes on most discrete types generate their
array elements with help from 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 very next
indexable value frequently turns out to be the next indexed value.  In
practice, this is likely whenever the scan skips with an input opclass
where "dense" indexed values occur naturally, such as btree/date_ops.

The design of skip arrays allows array advancement to work without
concern for which specific array types are involved; only the lowest
level code needs to treat skip arrays and SAOP arrays differently.
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 are conceptually just like any
other value that might appear in either kind of array.  A call made to
_bt_first to reposition the scan based on a NEXT/PRIOR sentinel usually
won't locate a leaf page containing tuples that must be returned to the
scan, but that's normal during any skip scan that happens to involve
"sparse" indexed values (skip support can only help with "dense" indexed
values, which isn't meaningfully possible when the skipped column is of
a continuous type, where skip support typically can't be implemented).

The optimizer doesn't use distinct new index paths to represent index
skip scans; whether and to what extent a scan actually skips is always
determined dynamically, at runtime.  Skipping is possible during
eligible bitmap index scans, index scans, and index-only scans.  It's
also possible during eligible parallel scans.  An eligible scan is any
scan that nbtree preprocessing generates a skip array for, which happens
whenever doing so will enable later preprocessing to mark original input
scan keys (passed by the executor) as required to continue the scan.

There are hardly any limitations around where skip arrays/scan keys may
appear relative to conventional/input scan keys.  This is no less true
in the presence of conventional SAOP array scan keys, which may both
roll over and be rolled over by skip arrays.  For example, a skip array
on the column "b" is generated for "WHERE a = 42 AND c IN (5, 6, 7, 8)".
As always (since commit 5bf748b8), whether or not nbtree actually skips
depends in large part on physical index characteristics at runtime.
Preprocessing is optimistic about skipping working out: it applies
simple static rules to decide where to place skip arrays.  It's up to
array-related scan code to keep the overhead of maintaining the scan's
skip arrays under control when it turns out that skipping isn't helpful.

Preprocessing will never cons up a skip array for an index column that
has an equality strategy scan key on input, but will do so for indexed
columns that are only constrained by inequality strategy scan keys.
This allows the scan to skip using a range skip array.  These are just
like conventional skip arrays, but only generate values from within a
given range.  The range is constrained by input inequality scan keys.
For example, a skip array on "a" can only ever use array element values
1 and 2 when generated for a qual "WHERE a BETWEEN 1 AND 2 AND b = 66".
Such a skip array works very much like the conventional SAOP array that
would be generated given the qual "WHERE a = ANY('{1, 2}') AND b = 66".

Author: Peter Geoghegan <pg@bowt.ie>
Reviewed-By: Tomas Vondra <tomas@vondra.me>
Reviewed-By: Masahiro Ikeda <masahiro.ikeda@nttdata.com>
Reviewed-By: Aleksander Alekseev <aleksander@timescale.com>
Discussion: https://postgr.es/m/CAH2-Wzmn1YsLzOGgjAQZdn1STSG_y8qP__vggTaPAYXJP+G4bw@mail.gmail.com
---
 src/include/access/amapi.h                    |    3 +-
 src/include/access/nbtree.h                   |   28 +-
 src/include/catalog/pg_amproc.dat             |   16 +
 src/include/catalog/pg_proc.dat               |   24 +
 src/include/storage/lwlock.h                  |    1 +
 src/include/utils/skipsupport.h               |  109 ++
 src/backend/access/index/indexam.c            |    3 +-
 src/backend/access/nbtree/nbtcompare.c        |  273 +++
 src/backend/access/nbtree/nbtree.c            |  208 ++-
 src/backend/access/nbtree/nbtsearch.c         |   84 +-
 src/backend/access/nbtree/nbtutils.c          | 1468 +++++++++++++++--
 src/backend/access/nbtree/nbtvalidate.c       |    4 +
 src/backend/commands/opclasscmds.c            |   25 +
 src/backend/storage/lmgr/lwlock.c             |    1 +
 .../utils/activity/wait_event_names.txt       |    1 +
 src/backend/utils/adt/Makefile                |    1 +
 src/backend/utils/adt/date.c                  |   46 +
 src/backend/utils/adt/meson.build             |    1 +
 src/backend/utils/adt/selfuncs.c              |  380 +++--
 src/backend/utils/adt/skipsupport.c           |   60 +
 src/backend/utils/adt/uuid.c                  |   71 +
 src/backend/utils/misc/guc_tables.c           |   23 +
 doc/src/sgml/btree.sgml                       |   32 +
 doc/src/sgml/indexam.sgml                     |    3 +-
 doc/src/sgml/indices.sgml                     |   49 +-
 doc/src/sgml/xindex.sgml                      |   16 +-
 src/test/regress/expected/alter_generic.out   |   10 +-
 src/test/regress/expected/create_index.out    |    4 +-
 src/test/regress/expected/join.out            |   61 +-
 src/test/regress/expected/psql.out            |    3 +-
 src/test/regress/expected/union.out           |   15 +-
 src/test/regress/sql/alter_generic.sql        |    5 +-
 src/test/regress/sql/create_index.sql         |    4 +-
 src/tools/pgindent/typedefs.list              |    3 +
 34 files changed, 2717 insertions(+), 318 deletions(-)
 create mode 100644 src/include/utils/skipsupport.h
 create mode 100644 src/backend/utils/adt/skipsupport.c

diff --git a/src/include/access/amapi.h b/src/include/access/amapi.h
index c51de742e..0826c124f 100644
--- a/src/include/access/amapi.h
+++ b/src/include/access/amapi.h
@@ -202,7 +202,8 @@ typedef void (*amrestrpos_function) (IndexScanDesc scan);
  */
 
 /* estimate size of parallel scan descriptor */
-typedef Size (*amestimateparallelscan_function) (int nkeys, int norderbys);
+typedef Size (*amestimateparallelscan_function) (Relation indexRelation,
+												 int nkeys, int norderbys);
 
 /* prepare for parallel index scan */
 typedef void (*aminitparallelscan_function) (void *target);
diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h
index 90a68375a..6372d2aee 100644
--- a/src/include/access/nbtree.h
+++ b/src/include/access/nbtree.h
@@ -24,6 +24,7 @@
 #include "lib/stringinfo.h"
 #include "storage/bufmgr.h"
 #include "storage/shm_toc.h"
+#include "utils/skipsupport.h"
 
 /* There's room for a 16-bit vacuum cycle ID in BTPageOpaqueData */
 typedef uint16 BTCycleId;
@@ -709,7 +710,8 @@ BTreeTupleGetMaxHeapTID(IndexTuple itup)
 #define BTINRANGE_PROC		3
 #define BTEQUALIMAGE_PROC	4
 #define BTOPTIONS_PROC		5
-#define BTNProcs			5
+#define BTSKIPSUPPORT_PROC	6
+#define BTNProcs			6
 
 /*
  *	We need to be able to tell the difference between read and write
@@ -1031,10 +1033,22 @@ typedef BTScanPosData *BTScanPos;
 /* We need one of these for each equality-type SK_SEARCHARRAY scan key */
 typedef struct BTArrayKeyInfo
 {
+	/* fields used by both kinds of array (standard arrays and skip arrays) */
 	int			scan_key;		/* index of associated key in keyData */
+	int			num_elems;		/* number of elems (-1 for skip array) */
+
+	/* fields for standard ScalarArrayOpExpr arrays */
 	int			cur_elem;		/* index of current element in elem_values */
-	int			num_elems;		/* number of elems in current array value */
 	Datum	   *elem_values;	/* array of num_elems Datums */
+
+	/* fields for skip arrays, which generate their elements procedurally */
+	bool		use_sksup;		/* sksup initialized/skip support in use? */
+	bool		null_elem;		/* lowest/highest element actually NULL? */
+	SkipSupportData sksup;		/* skip scan support (unless !use_sksup) */
+	ScanKey		low_compare;	/* array's > or >= lower bound */
+	ScanKey		high_compare;	/* array's < or <= upper bound */
+	FmgrInfo   *low_order;		/* low_compare's ORDER proc */
+	FmgrInfo   *high_order;		/* high_compare's ORDER proc */
 } BTArrayKeyInfo;
 
 typedef struct BTScanOpaqueData
@@ -1124,6 +1138,10 @@ typedef struct BTReadPageState
  */
 #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 omitted prefix column */
+#define SK_BT_NEGPOSINF	0x00080000	/* -inf/+inf key (invalid sk_argument) */
+#define SK_BT_NEXT		0x00100000	/* positions scan > sk_argument */
+#define SK_BT_PRIOR		0x00200000	/* positions scan < sk_argument */
 #define SK_BT_INDOPTION_SHIFT  24	/* must clear the above bits */
 #define SK_BT_DESC			(INDOPTION_DESC << SK_BT_INDOPTION_SHIFT)
 #define SK_BT_NULLS_FIRST	(INDOPTION_NULLS_FIRST << SK_BT_INDOPTION_SHIFT)
@@ -1160,6 +1178,10 @@ typedef struct BTOptions
 #define PROGRESS_BTREE_PHASE_PERFORMSORT_2				4
 #define PROGRESS_BTREE_PHASE_LEAF_LOAD					5
 
+/* GUC parameters (just a temporary convenience for reviewers) */
+extern PGDLLIMPORT int skipscan_prefix_cols;
+extern PGDLLIMPORT bool skipscan_skipsupport_enabled;
+
 /*
  * external entry points for btree, in nbtree.c
  */
@@ -1170,7 +1192,7 @@ extern bool btinsert(Relation rel, Datum *values, bool *isnull,
 					 bool indexUnchanged,
 					 struct IndexInfo *indexInfo);
 extern IndexScanDesc btbeginscan(Relation rel, int nkeys, int norderbys);
-extern Size btestimateparallelscan(int nkeys, int norderbys);
+extern Size btestimateparallelscan(Relation rel, int nkeys, int norderbys);
 extern void btinitparallelscan(void *target);
 extern bool btgettuple(IndexScanDesc scan, ScanDirection dir);
 extern int64 btgetbitmap(IndexScanDesc scan, TIDBitmap *tbm);
diff --git a/src/include/catalog/pg_amproc.dat b/src/include/catalog/pg_amproc.dat
index 5d7fe292b..c0ccdfdfb 100644
--- a/src/include/catalog/pg_amproc.dat
+++ b/src/include/catalog/pg_amproc.dat
@@ -21,6 +21,8 @@
   amprocrighttype => 'bit', amprocnum => '4', amproc => 'btequalimage' },
 { amprocfamily => 'btree/bool_ops', amproclefttype => 'bool',
   amprocrighttype => 'bool', amprocnum => '1', amproc => 'btboolcmp' },
+{ amprocfamily => 'btree/bool_ops', amproclefttype => 'bool',
+  amprocrighttype => 'bool', amprocnum => '6', amproc => 'btboolskipsupport' },
 { amprocfamily => 'btree/bool_ops', amproclefttype => 'bool',
   amprocrighttype => 'bool', amprocnum => '4', amproc => 'btequalimage' },
 { amprocfamily => 'btree/bpchar_ops', amproclefttype => 'bpchar',
@@ -41,12 +43,16 @@
   amprocrighttype => 'char', amprocnum => '1', amproc => 'btcharcmp' },
 { amprocfamily => 'btree/char_ops', amproclefttype => 'char',
   amprocrighttype => 'char', amprocnum => '4', amproc => 'btequalimage' },
+{ amprocfamily => 'btree/char_ops', amproclefttype => 'char',
+  amprocrighttype => 'char', amprocnum => '6', amproc => 'btcharskipsupport' },
 { amprocfamily => 'btree/datetime_ops', amproclefttype => 'date',
   amprocrighttype => 'date', amprocnum => '1', amproc => 'date_cmp' },
 { amprocfamily => 'btree/datetime_ops', amproclefttype => 'date',
   amprocrighttype => 'date', amprocnum => '2', amproc => 'date_sortsupport' },
 { amprocfamily => 'btree/datetime_ops', amproclefttype => 'date',
   amprocrighttype => 'date', amprocnum => '4', amproc => 'btequalimage' },
+{ amprocfamily => 'btree/datetime_ops', amproclefttype => 'date',
+  amprocrighttype => 'date', amprocnum => '6', amproc => 'date_skipsupport' },
 { amprocfamily => 'btree/datetime_ops', amproclefttype => 'date',
   amprocrighttype => 'timestamp', amprocnum => '1',
   amproc => 'date_cmp_timestamp' },
@@ -122,6 +128,8 @@
   amprocrighttype => 'int2', amprocnum => '2', amproc => 'btint2sortsupport' },
 { amprocfamily => 'btree/integer_ops', amproclefttype => 'int2',
   amprocrighttype => 'int2', amprocnum => '4', amproc => 'btequalimage' },
+{ amprocfamily => 'btree/integer_ops', amproclefttype => 'int2',
+  amprocrighttype => 'int2', amprocnum => '6', amproc => 'btint2skipsupport' },
 { amprocfamily => 'btree/integer_ops', amproclefttype => 'int2',
   amprocrighttype => 'int4', amprocnum => '1', amproc => 'btint24cmp' },
 { amprocfamily => 'btree/integer_ops', amproclefttype => 'int2',
@@ -141,6 +149,8 @@
   amprocrighttype => 'int4', amprocnum => '2', amproc => 'btint4sortsupport' },
 { amprocfamily => 'btree/integer_ops', amproclefttype => 'int4',
   amprocrighttype => 'int4', amprocnum => '4', amproc => 'btequalimage' },
+{ amprocfamily => 'btree/integer_ops', amproclefttype => 'int4',
+  amprocrighttype => 'int4', amprocnum => '6', amproc => 'btint4skipsupport' },
 { amprocfamily => 'btree/integer_ops', amproclefttype => 'int4',
   amprocrighttype => 'int8', amprocnum => '1', amproc => 'btint48cmp' },
 { amprocfamily => 'btree/integer_ops', amproclefttype => 'int4',
@@ -160,6 +170,8 @@
   amprocrighttype => 'int8', amprocnum => '2', amproc => 'btint8sortsupport' },
 { amprocfamily => 'btree/integer_ops', amproclefttype => 'int8',
   amprocrighttype => 'int8', amprocnum => '4', amproc => 'btequalimage' },
+{ amprocfamily => 'btree/integer_ops', amproclefttype => 'int8',
+  amprocrighttype => 'int8', amprocnum => '6', amproc => 'btint8skipsupport' },
 { amprocfamily => 'btree/integer_ops', amproclefttype => 'int8',
   amprocrighttype => 'int4', amprocnum => '1', amproc => 'btint84cmp' },
 { amprocfamily => 'btree/integer_ops', amproclefttype => 'int8',
@@ -193,6 +205,8 @@
   amprocrighttype => 'oid', amprocnum => '2', amproc => 'btoidsortsupport' },
 { amprocfamily => 'btree/oid_ops', amproclefttype => 'oid',
   amprocrighttype => 'oid', amprocnum => '4', amproc => 'btequalimage' },
+{ amprocfamily => 'btree/oid_ops', amproclefttype => 'oid',
+  amprocrighttype => 'oid', amprocnum => '6', amproc => 'btoidskipsupport' },
 { amprocfamily => 'btree/oidvector_ops', amproclefttype => 'oidvector',
   amprocrighttype => 'oidvector', amprocnum => '1',
   amproc => 'btoidvectorcmp' },
@@ -261,6 +275,8 @@
   amprocrighttype => 'uuid', amprocnum => '2', amproc => 'uuid_sortsupport' },
 { amprocfamily => 'btree/uuid_ops', amproclefttype => 'uuid',
   amprocrighttype => 'uuid', amprocnum => '4', amproc => 'btequalimage' },
+{ amprocfamily => 'btree/uuid_ops', amproclefttype => 'uuid',
+  amprocrighttype => 'uuid', amprocnum => '6', amproc => 'uuid_skipsupport' },
 { amprocfamily => 'btree/record_ops', amproclefttype => 'record',
   amprocrighttype => 'record', amprocnum => '1', amproc => 'btrecordcmp' },
 { amprocfamily => 'btree/record_image_ops', amproclefttype => 'record',
diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat
index 7c0b74fe0..f04a26622 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -1004,18 +1004,27 @@
 { oid => '3129', descr => 'sort support',
   proname => 'btint2sortsupport', prorettype => 'void',
   proargtypes => 'internal', prosrc => 'btint2sortsupport' },
+{ oid => '9290', descr => 'skip support',
+  proname => 'btint2skipsupport', prorettype => 'void',
+  proargtypes => 'internal', prosrc => 'btint2skipsupport' },
 { oid => '351', descr => 'less-equal-greater',
   proname => 'btint4cmp', proleakproof => 't', prorettype => 'int4',
   proargtypes => 'int4 int4', prosrc => 'btint4cmp' },
 { oid => '3130', descr => 'sort support',
   proname => 'btint4sortsupport', prorettype => 'void',
   proargtypes => 'internal', prosrc => 'btint4sortsupport' },
+{ oid => '9291', descr => 'skip support',
+  proname => 'btint4skipsupport', prorettype => 'void',
+  proargtypes => 'internal', prosrc => 'btint4skipsupport' },
 { oid => '842', descr => 'less-equal-greater',
   proname => 'btint8cmp', proleakproof => 't', prorettype => 'int4',
   proargtypes => 'int8 int8', prosrc => 'btint8cmp' },
 { oid => '3131', descr => 'sort support',
   proname => 'btint8sortsupport', prorettype => 'void',
   proargtypes => 'internal', prosrc => 'btint8sortsupport' },
+{ oid => '9292', descr => 'skip support',
+  proname => 'btint8skipsupport', prorettype => 'void',
+  proargtypes => 'internal', prosrc => 'btint8skipsupport' },
 { oid => '354', descr => 'less-equal-greater',
   proname => 'btfloat4cmp', proleakproof => 't', prorettype => 'int4',
   proargtypes => 'float4 float4', prosrc => 'btfloat4cmp' },
@@ -1034,12 +1043,18 @@
 { oid => '3134', descr => 'sort support',
   proname => 'btoidsortsupport', prorettype => 'void',
   proargtypes => 'internal', prosrc => 'btoidsortsupport' },
+{ oid => '9293', descr => 'skip support',
+  proname => 'btoidskipsupport', prorettype => 'void',
+  proargtypes => 'internal', prosrc => 'btoidskipsupport' },
 { oid => '404', descr => 'less-equal-greater',
   proname => 'btoidvectorcmp', proleakproof => 't', prorettype => 'int4',
   proargtypes => 'oidvector oidvector', prosrc => 'btoidvectorcmp' },
 { oid => '358', descr => 'less-equal-greater',
   proname => 'btcharcmp', proleakproof => 't', prorettype => 'int4',
   proargtypes => 'char char', prosrc => 'btcharcmp' },
+{ oid => '9294', descr => 'skip support',
+  proname => 'btcharskipsupport', prorettype => 'void',
+  proargtypes => 'internal', prosrc => 'btcharskipsupport' },
 { oid => '359', descr => 'less-equal-greater',
   proname => 'btnamecmp', proleakproof => 't', prorettype => 'int4',
   proargtypes => 'name name', prosrc => 'btnamecmp' },
@@ -2257,6 +2272,9 @@
 { oid => '3136', descr => 'sort support',
   proname => 'date_sortsupport', prorettype => 'void',
   proargtypes => 'internal', prosrc => 'date_sortsupport' },
+{ oid => '9295', descr => 'skip support',
+  proname => 'date_skipsupport', prorettype => 'void',
+  proargtypes => 'internal', prosrc => 'date_skipsupport' },
 { oid => '4133', descr => 'window RANGE support',
   proname => 'in_range', prorettype => 'bool',
   proargtypes => 'date date interval bool bool',
@@ -4444,6 +4462,9 @@
 { oid => '1693', descr => 'less-equal-greater',
   proname => 'btboolcmp', proleakproof => 't', prorettype => 'int4',
   proargtypes => 'bool bool', prosrc => 'btboolcmp' },
+{ oid => '9296', descr => 'skip support',
+  proname => 'btboolskipsupport', prorettype => 'void',
+  proargtypes => 'internal', prosrc => 'btboolskipsupport' },
 
 { oid => '1688', descr => 'hash',
   proname => 'time_hash', prorettype => 'int4', proargtypes => 'time',
@@ -9320,6 +9341,9 @@
 { oid => '3300', descr => 'sort support',
   proname => 'uuid_sortsupport', prorettype => 'void',
   proargtypes => 'internal', prosrc => 'uuid_sortsupport' },
+{ oid => '9297', descr => 'skip support',
+  proname => 'uuid_skipsupport', prorettype => 'void',
+  proargtypes => 'internal', prosrc => 'uuid_skipsupport' },
 { oid => '2961', descr => 'I/O',
   proname => 'uuid_recv', prorettype => 'uuid', proargtypes => 'internal',
   prosrc => 'uuid_recv' },
diff --git a/src/include/storage/lwlock.h b/src/include/storage/lwlock.h
index d70e6d37e..5b58739ad 100644
--- a/src/include/storage/lwlock.h
+++ b/src/include/storage/lwlock.h
@@ -192,6 +192,7 @@ typedef enum BuiltinTrancheIds
 	LWTRANCHE_LOCK_MANAGER,
 	LWTRANCHE_PREDICATE_LOCK_MANAGER,
 	LWTRANCHE_PARALLEL_HASH_JOIN,
+	LWTRANCHE_PARALLEL_BTREE_SCAN,
 	LWTRANCHE_PARALLEL_QUERY_DSA,
 	LWTRANCHE_PER_SESSION_DSA,
 	LWTRANCHE_PER_SESSION_RECORD_TYPE,
diff --git a/src/include/utils/skipsupport.h b/src/include/utils/skipsupport.h
new file mode 100644
index 000000000..bd1fb599a
--- /dev/null
+++ b/src/include/utils/skipsupport.h
@@ -0,0 +1,109 @@
+/*-------------------------------------------------------------------------
+ *
+ * skipsupport.h
+ *	  Support routines for B-Tree skip scan.
+ *
+ * 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.
+ *
+ * Skip support is used by discrete type (e.g., integer and date) opclasses.
+ * Indexes with an attribute whose input opclass is of one of these types tend
+ * to store adjacent values in adjoining pairs 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.)
+ *
+ * The B-Tree code can fall back on next-key sentinel values for any opclass
+ * that doesn't provide its own skip support function.  There is no point in
+ * providing skip support unless the next indexed key value is often the next
+ * indexable value (at least with some workloads).  Opclasses where that never
+ * works out in practice should just rely on the B-Tree AM's generic next-key
+ * fallback strategy.  Opclasses where adding skip support is infeasible or
+ * hard (e.g., an opclass for a continuous type) can also use the fallback.
+ *
+ *
+ * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * src/include/utils/skipsupport.h
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef SKIPSUPPORT_H
+#define SKIPSUPPORT_H
+
+#include "utils/relcache.h"
+
+typedef struct SkipSupportData *SkipSupport;
+typedef Datum (*SkipSupportIncDec) (Relation rel,
+									Datum existing,
+									bool *overflow);
+
+/*
+ * State/callbacks used by skip arrays to procedurally generate elements.
+ *
+ * A BTSKIPSUPPORT_PROC function must set each and every field when called
+ * (there are no optional fields).
+ */
+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).
+	 * This gives the B-Tree code a useful value to start from, before any
+	 * data has been read from the index.
+	 *
+	 * low_elem and high_elem are also used by skip scans to determine when
+	 * they've reached the final possible value (in the current direction).
+	 * It's typical for the scan to run out of leaf pages before it runs out
+	 * of unscanned indexable values, but it's still useful for the scan to
+	 * have a way to recognize when it has reached the last possible value
+	 * (it'll sometimes save a useless probe for a lesser/greater value).
+	 */
+	Datum		low_elem;		/* lowest sorting/leftmost non-NULL value */
+	Datum		high_elem;		/* highest sorting/rightmost non-NULL value */
+
+	/*
+	 * Decrement/increment functions.
+	 *
+	 * Returns a decremented/incremented copy of caller's existing datum,
+	 * allocated in caller's memory context (in the case of pass-by-reference
+	 * types).  It's not okay for these functions to leak any memory.
+	 *
+	 * Both decrement and increment callbacks are guaranteed to never be
+	 * called with a NULL "existing" arg.
+	 *
+	 * When the decrement function (or increment function) is called with a
+	 * value that already matches low_elem (or high_elem), function must set
+	 * the *overflow argument.  The return value is treated as undefined by
+	 * the B-Tree code; it shouldn't need to be (and won't be) pfree'd.
+	 *
+	 * The B-Tree skip scan caller's "existing" datum is often just a straight
+	 * copy of a value from an index tuple.  Operator classes must accept
+	 * every possible representational variation within the underlying type.
+	 * On the other hand, opclasses are _not_ required to preserve information
+	 * that doesn't affect how datums are sorted (e.g., skip support for a
+	 * fixed precision numeric type needn't preserve datum display scale).
+	 */
+	SkipSupportIncDec decrement;
+	SkipSupportIncDec increment;
+} SkipSupportData;
+
+extern bool PrepareSkipSupportFromOpclass(Oid opfamily, Oid opcintype,
+										  bool reverse, SkipSupport sksup);
+
+#endif							/* SKIPSUPPORT_H */
diff --git a/src/backend/access/index/indexam.c b/src/backend/access/index/indexam.c
index 1859be614..b4f1466d4 100644
--- a/src/backend/access/index/indexam.c
+++ b/src/backend/access/index/indexam.c
@@ -470,7 +470,8 @@ index_parallelscan_estimate(Relation indexRelation, int nkeys, int norderbys,
 	 */
 	if (indexRelation->rd_indam->amestimateparallelscan != NULL)
 		nbytes = add_size(nbytes,
-						  indexRelation->rd_indam->amestimateparallelscan(nkeys,
+						  indexRelation->rd_indam->amestimateparallelscan(indexRelation,
+																		  nkeys,
 																		  norderbys));
 
 	return nbytes;
diff --git a/src/backend/access/nbtree/nbtcompare.c b/src/backend/access/nbtree/nbtcompare.c
index 1c72867c8..26ebbf776 100644
--- a/src/backend/access/nbtree/nbtcompare.c
+++ b/src/backend/access/nbtree/nbtcompare.c
@@ -58,6 +58,7 @@
 #include <limits.h>
 
 #include "utils/fmgrprotos.h"
+#include "utils/skipsupport.h"
 #include "utils/sortsupport.h"
 
 #ifdef STRESS_SORT_INT_MIN
@@ -78,6 +79,51 @@ btboolcmp(PG_FUNCTION_ARGS)
 	PG_RETURN_INT32((int32) a - (int32) b);
 }
 
+static Datum
+bool_decrement(Relation rel, Datum existing, bool *underflow)
+{
+	bool		bexisting = DatumGetBool(existing);
+
+	if (bexisting == false)
+	{
+		/* return value is undefined */
+		*underflow = true;
+		return (Datum) 0;
+	}
+
+	*underflow = false;
+	return BoolGetDatum(bexisting - 1);
+}
+
+static Datum
+bool_increment(Relation rel, Datum existing, bool *overflow)
+{
+	bool		bexisting = DatumGetBool(existing);
+
+	if (bexisting == true)
+	{
+		/* return value is undefined */
+		*overflow = true;
+		return (Datum) 0;
+	}
+
+	*overflow = false;
+	return BoolGetDatum(bexisting + 1);
+}
+
+Datum
+btboolskipsupport(PG_FUNCTION_ARGS)
+{
+	SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
+
+	sksup->decrement = bool_decrement;
+	sksup->increment = bool_increment;
+	sksup->low_elem = BoolGetDatum(false);
+	sksup->high_elem = BoolGetDatum(true);
+
+	PG_RETURN_VOID();
+}
+
 Datum
 btint2cmp(PG_FUNCTION_ARGS)
 {
@@ -105,6 +151,51 @@ btint2sortsupport(PG_FUNCTION_ARGS)
 	PG_RETURN_VOID();
 }
 
+static Datum
+int2_decrement(Relation rel, Datum existing, bool *underflow)
+{
+	int16		iexisting = DatumGetInt16(existing);
+
+	if (iexisting == PG_INT16_MIN)
+	{
+		/* return value is undefined */
+		*underflow = true;
+		return (Datum) 0;
+	}
+
+	*underflow = false;
+	return Int16GetDatum(iexisting - 1);
+}
+
+static Datum
+int2_increment(Relation rel, Datum existing, bool *overflow)
+{
+	int16		iexisting = DatumGetInt16(existing);
+
+	if (iexisting == PG_INT16_MAX)
+	{
+		/* return value is undefined */
+		*overflow = true;
+		return (Datum) 0;
+	}
+
+	*overflow = false;
+	return Int16GetDatum(iexisting + 1);
+}
+
+Datum
+btint2skipsupport(PG_FUNCTION_ARGS)
+{
+	SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
+
+	sksup->decrement = int2_decrement;
+	sksup->increment = int2_increment;
+	sksup->low_elem = Int16GetDatum(PG_INT16_MIN);
+	sksup->high_elem = Int16GetDatum(PG_INT16_MAX);
+
+	PG_RETURN_VOID();
+}
+
 Datum
 btint4cmp(PG_FUNCTION_ARGS)
 {
@@ -128,6 +219,51 @@ btint4sortsupport(PG_FUNCTION_ARGS)
 	PG_RETURN_VOID();
 }
 
+static Datum
+int4_decrement(Relation rel, Datum existing, bool *underflow)
+{
+	int32		iexisting = DatumGetInt32(existing);
+
+	if (iexisting == PG_INT32_MIN)
+	{
+		/* return value is undefined */
+		*underflow = true;
+		return (Datum) 0;
+	}
+
+	*underflow = false;
+	return Int32GetDatum(iexisting - 1);
+}
+
+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);
+}
+
+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();
+}
+
 Datum
 btint8cmp(PG_FUNCTION_ARGS)
 {
@@ -171,6 +307,51 @@ btint8sortsupport(PG_FUNCTION_ARGS)
 	PG_RETURN_VOID();
 }
 
+static Datum
+int8_decrement(Relation rel, Datum existing, bool *underflow)
+{
+	int64		iexisting = DatumGetInt64(existing);
+
+	if (iexisting == PG_INT64_MIN)
+	{
+		/* return value is undefined */
+		*underflow = true;
+		return (Datum) 0;
+	}
+
+	*underflow = false;
+	return Int64GetDatum(iexisting - 1);
+}
+
+static Datum
+int8_increment(Relation rel, Datum existing, bool *overflow)
+{
+	int64		iexisting = DatumGetInt64(existing);
+
+	if (iexisting == PG_INT64_MAX)
+	{
+		/* return value is undefined */
+		*overflow = true;
+		return (Datum) 0;
+	}
+
+	*overflow = false;
+	return Int64GetDatum(iexisting + 1);
+}
+
+Datum
+btint8skipsupport(PG_FUNCTION_ARGS)
+{
+	SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
+
+	sksup->decrement = int8_decrement;
+	sksup->increment = int8_increment;
+	sksup->low_elem = Int64GetDatum(PG_INT64_MIN);
+	sksup->high_elem = Int64GetDatum(PG_INT64_MAX);
+
+	PG_RETURN_VOID();
+}
+
 Datum
 btint48cmp(PG_FUNCTION_ARGS)
 {
@@ -292,6 +473,51 @@ btoidsortsupport(PG_FUNCTION_ARGS)
 	PG_RETURN_VOID();
 }
 
+static Datum
+oid_decrement(Relation rel, Datum existing, bool *underflow)
+{
+	Oid			oexisting = DatumGetObjectId(existing);
+
+	if (oexisting == InvalidOid)
+	{
+		/* return value is undefined */
+		*underflow = true;
+		return (Datum) 0;
+	}
+
+	*underflow = false;
+	return ObjectIdGetDatum(oexisting - 1);
+}
+
+static Datum
+oid_increment(Relation rel, Datum existing, bool *overflow)
+{
+	Oid			oexisting = DatumGetObjectId(existing);
+
+	if (oexisting == OID_MAX)
+	{
+		/* return value is undefined */
+		*overflow = true;
+		return (Datum) 0;
+	}
+
+	*overflow = false;
+	return ObjectIdGetDatum(oexisting + 1);
+}
+
+Datum
+btoidskipsupport(PG_FUNCTION_ARGS)
+{
+	SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
+
+	sksup->decrement = oid_decrement;
+	sksup->increment = oid_increment;
+	sksup->low_elem = ObjectIdGetDatum(InvalidOid);
+	sksup->high_elem = ObjectIdGetDatum(OID_MAX);
+
+	PG_RETURN_VOID();
+}
+
 Datum
 btoidvectorcmp(PG_FUNCTION_ARGS)
 {
@@ -325,3 +551,50 @@ btcharcmp(PG_FUNCTION_ARGS)
 	/* Be careful to compare chars as unsigned */
 	PG_RETURN_INT32((int32) ((uint8) a) - (int32) ((uint8) b));
 }
+
+static Datum
+char_decrement(Relation rel, Datum existing, bool *underflow)
+{
+	uint8		cexisting = UInt8GetDatum(existing);
+
+	if (cexisting == 0)
+	{
+		/* return value is undefined */
+		*underflow = true;
+		return (Datum) 0;
+	}
+
+	*underflow = false;
+	return CharGetDatum((uint8) cexisting - 1);
+}
+
+static Datum
+char_increment(Relation rel, Datum existing, bool *overflow)
+{
+	uint8		cexisting = UInt8GetDatum(existing);
+
+	if (cexisting == UCHAR_MAX)
+	{
+		/* return value is undefined */
+		*overflow = true;
+		return (Datum) 0;
+	}
+
+	*overflow = false;
+	return CharGetDatum((uint8) cexisting + 1);
+}
+
+Datum
+btcharskipsupport(PG_FUNCTION_ARGS)
+{
+	SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
+
+	sksup->decrement = char_decrement;
+	sksup->increment = char_increment;
+
+	/* btcharcmp compares chars as unsigned */
+	sksup->low_elem = UInt8GetDatum(0);
+	sksup->high_elem = UInt8GetDatum(UCHAR_MAX);
+
+	PG_RETURN_VOID();
+}
diff --git a/src/backend/access/nbtree/nbtree.c b/src/backend/access/nbtree/nbtree.c
index ddc6e1f7a..abf168acd 100644
--- a/src/backend/access/nbtree/nbtree.c
+++ b/src/backend/access/nbtree/nbtree.c
@@ -32,6 +32,7 @@
 #include "storage/ipc.h"
 #include "storage/lmgr.h"
 #include "storage/smgr.h"
+#include "utils/datum.h"
 #include "utils/fmgrprotos.h"
 #include "utils/index_selfuncs.h"
 #include "utils/memutils.h"
@@ -71,7 +72,7 @@ typedef struct BTParallelScanDescData
 									 * available for scan. see above for
 									 * possible states of parallel scan. */
 	uint64		btps_nsearches; /* counts index searches for EXPLAIN ANALYZE */
-	slock_t		btps_mutex;		/* protects above variables, btps_arrElems */
+	LWLock		btps_lock;		/* protects above variables, btps_arrElems */
 	ConditionVariable btps_cv;	/* used to synchronize parallel scan */
 
 	/*
@@ -79,11 +80,23 @@ typedef struct BTParallelScanDescData
 	 * index scan.  Holds BTArrayKeyInfo.cur_elem offsets for scan keys.
 	 */
 	int			btps_arrElems[FLEXIBLE_ARRAY_MEMBER];
+
+	/*
+	 * The remainder of the space allocated in shared memory is used by scans
+	 * that need to schedule another primitive index scan with skip arrays.
+	 * Space holds a flattened representation of each skip array's current
+	 * array element, in datum format.  We don't store BTArrayKeyInfo.cur_elem
+	 * offsets for skip arrays; their elements are determined dynamically.
+	 */
 }			BTParallelScanDescData;
 
 typedef struct BTParallelScanDescData *BTParallelScanDesc;
 
 
+static void _bt_parallel_serialize_arrays(Relation rel, BTParallelScanDesc btscan,
+										  BTScanOpaque so);
+static void _bt_parallel_restore_arrays(Relation rel, BTParallelScanDesc btscan,
+										BTScanOpaque so);
 static void btvacuumscan(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
 						 IndexBulkDeleteCallback callback, void *callback_state,
 						 BTCycleId cycleid);
@@ -536,10 +549,156 @@ btrestrpos(IndexScanDesc scan)
  * btestimateparallelscan -- estimate storage for BTParallelScanDescData
  */
 Size
-btestimateparallelscan(int nkeys, int norderbys)
+btestimateparallelscan(Relation rel, int nkeys, int norderbys)
 {
+	int16		nkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
+	Size		estnbtreeshared,
+				genericattrspace;
+
 	/* Pessimistically assume all input scankeys will be output with arrays */
-	return offsetof(BTParallelScanDescData, btps_arrElems) + sizeof(int) * nkeys;
+	estnbtreeshared = offsetof(BTParallelScanDescData, btps_arrElems) +
+		sizeof(int) * nkeys;
+
+	/*
+	 * Assume every index attribute might require that we generate a skip scan
+	 * key
+	 */
+	genericattrspace = datumEstimateSpace((Datum) 0, false, true,
+										  sizeof(Datum));
+	for (int attnum = 1; attnum <= nkeyatts; attnum++)
+	{
+		Form_pg_attribute attr;
+
+		/* Every skip array needs a space for storing sk_flags */
+		estnbtreeshared = add_size(estnbtreeshared, sizeof(int));
+
+		attr = TupleDescAttr(rel->rd_att, attnum - 1);
+		if (attr->attlen > 0)
+		{
+			/* Fixed length datum */
+			Size		estfixed = datumEstimateSpace((Datum) 0, false,
+													  attr->attbyval,
+													  attr->attlen);
+
+			estnbtreeshared = add_size(estnbtreeshared, estfixed);
+			continue;
+		}
+
+		/*
+		 * Varlena (or other variable-length) datum.
+		 *
+		 * Assume that serializing the arrays will use just as much space as a
+		 * pass-by-value datum, in addition to a full third of a page of
+		 * space.
+		 */
+		estnbtreeshared = add_size(estnbtreeshared, genericattrspace);
+		estnbtreeshared = add_size(estnbtreeshared, BLCKSZ / 3);
+	}
+
+	return estnbtreeshared;
+}
+
+/*
+ * _bt_parallel_serialize_arrays() -- Serialize parallel array state.
+ *
+ * Caller must have exclusively locked btscan->btps_lock when called.
+ */
+static void
+_bt_parallel_serialize_arrays(Relation rel, BTParallelScanDesc btscan,
+							  BTScanOpaque so)
+{
+	char	   *datumshared;
+
+	/* Space for serialized datums begins immediately after btps_arrElems[] */
+	datumshared = ((char *) &btscan->btps_arrElems[so->numArrayKeys]);
+	for (int i = 0; i < so->numArrayKeys; i++)
+	{
+		BTArrayKeyInfo *array = &so->arrayKeys[i];
+		ScanKey		skey = &so->keyData[array->scan_key];
+		Form_pg_attribute attr;
+
+		if (array->num_elems != -1)
+		{
+			/* Serialize regular (non-skip) array using cur_elem */
+			Assert(!(skey->sk_flags & SK_BT_SKIP));
+			btscan->btps_arrElems[i] = array->cur_elem;
+			continue;
+		}
+
+		/* Serialize skip array/skip scan key */
+		Assert(skey->sk_flags & SK_BT_SKIP);
+		memcpy(datumshared, &skey->sk_flags, sizeof(int));
+		datumshared += sizeof(int);
+
+		if (skey->sk_flags & SK_BT_NEGPOSINF)
+		{
+			/* No sk_argument datum to serialize */
+			Assert(skey->sk_argument == 0);
+			continue;
+		}
+
+		attr = TupleDescAttr(RelationGetDescr(rel), skey->sk_attno - 1);
+		datumSerialize(skey->sk_argument, (skey->sk_flags & SK_ISNULL) != 0,
+					   attr->attbyval, attr->attlen, &datumshared);
+	}
+}
+
+/*
+ * _bt_parallel_restore_arrays() -- Restore serialized parallel array state.
+ *
+ * Caller must have exclusively locked btscan->btps_lock when called.
+ */
+static void
+_bt_parallel_restore_arrays(Relation rel, BTParallelScanDesc btscan,
+							BTScanOpaque so)
+{
+	char	   *datumshared;
+
+	/* Space for serialized datums begins immediately after btps_arrElems[] */
+	datumshared = ((char *) &btscan->btps_arrElems[so->numArrayKeys]);
+	for (int i = 0; i < so->numArrayKeys; i++)
+	{
+		BTArrayKeyInfo *array = &so->arrayKeys[i];
+		ScanKey		skey = &so->keyData[array->scan_key];
+		bool		isnull;
+		Form_pg_attribute attr;
+
+		if (array->num_elems != -1)
+		{
+			/* Restore regular (non-skip) array's cur_elem */
+			Assert(!(skey->sk_flags & SK_BT_SKIP));
+			array->cur_elem = btscan->btps_arrElems[i];
+			skey->sk_argument = array->elem_values[array->cur_elem];
+			continue;
+		}
+
+		/*
+		 * Restore skip array/skip scan key, while freeing memory allocated
+		 * for old sk_argument where required
+		 */
+		attr = TupleDescAttr(RelationGetDescr(rel), skey->sk_attno - 1);
+		if (!attr->attbyval && skey->sk_argument)
+			pfree(DatumGetPointer(skey->sk_argument));
+		skey->sk_argument = (Datum) 0;
+		memcpy(&skey->sk_flags, datumshared, sizeof(int));
+		datumshared += sizeof(int);
+
+		Assert(skey->sk_flags & SK_BT_SKIP);
+
+		if (skey->sk_flags & SK_BT_NEGPOSINF)
+		{
+			/* No sk_argument datum to restore */
+			continue;
+		}
+
+		skey->sk_argument = datumRestore(&datumshared, &isnull);
+		if (isnull)
+		{
+			Assert(skey->sk_argument == 0);
+			Assert(skey->sk_flags & SK_SEARCHNULL);
+			Assert(skey->sk_flags & SK_ISNULL);
+		}
+	}
 }
 
 /*
@@ -550,7 +709,8 @@ btinitparallelscan(void *target)
 {
 	BTParallelScanDesc bt_target = (BTParallelScanDesc) target;
 
-	SpinLockInit(&bt_target->btps_mutex);
+	LWLockInitialize(&bt_target->btps_lock,
+					 LWTRANCHE_PARALLEL_BTREE_SCAN);
 	bt_target->btps_scanPage = InvalidBlockNumber;
 	bt_target->btps_pageStatus = BTPARALLEL_NOT_INITIALIZED;
 	bt_target->btps_nsearches = 0;
@@ -572,15 +732,15 @@ btparallelrescan(IndexScanDesc scan)
 												  parallel_scan->ps_offset);
 
 	/*
-	 * In theory, we don't need to acquire the spinlock here, because there
+	 * In theory, we don't need to acquire the LWLock here, because there
 	 * shouldn't be any other workers running at this point, but we do so for
 	 * consistency.
 	 */
-	SpinLockAcquire(&btscan->btps_mutex);
+	LWLockAcquire(&btscan->btps_lock, LW_EXCLUSIVE);
 	btscan->btps_scanPage = InvalidBlockNumber;
 	btscan->btps_pageStatus = BTPARALLEL_NOT_INITIALIZED;
 	/* deliberately don't reset btps_nsearches (matches index_rescan) */
-	SpinLockRelease(&btscan->btps_mutex);
+	LWLockRelease(&btscan->btps_lock);
 }
 
 /*
@@ -607,6 +767,7 @@ btparallelrescan(IndexScanDesc scan)
 bool
 _bt_parallel_seize(IndexScanDesc scan, BlockNumber *pageno, bool first)
 {
+	Relation	rel = scan->indexRelation;
 	BTScanOpaque so = (BTScanOpaque) scan->opaque;
 	bool		exit_loop = false;
 	bool		status = true;
@@ -640,7 +801,7 @@ _bt_parallel_seize(IndexScanDesc scan, BlockNumber *pageno, bool first)
 
 	while (1)
 	{
-		SpinLockAcquire(&btscan->btps_mutex);
+		LWLockAcquire(&btscan->btps_lock, LW_EXCLUSIVE);
 
 		if (btscan->btps_pageStatus == BTPARALLEL_DONE)
 		{
@@ -655,14 +816,9 @@ _bt_parallel_seize(IndexScanDesc scan, BlockNumber *pageno, bool first)
 			{
 				/* Can start scheduled primitive scan right away, so do so */
 				btscan->btps_pageStatus = BTPARALLEL_ADVANCING;
-				for (int i = 0; i < so->numArrayKeys; i++)
-				{
-					BTArrayKeyInfo *array = &so->arrayKeys[i];
-					ScanKey		skey = &so->keyData[array->scan_key];
 
-					array->cur_elem = btscan->btps_arrElems[i];
-					skey->sk_argument = array->elem_values[array->cur_elem];
-				}
+				/* Restore scan's array keys from serialized values */
+				_bt_parallel_restore_arrays(rel, btscan, so);
 				*pageno = InvalidBlockNumber;
 				exit_loop = true;
 			}
@@ -699,7 +855,7 @@ _bt_parallel_seize(IndexScanDesc scan, BlockNumber *pageno, bool first)
 			*pageno = btscan->btps_scanPage;
 			exit_loop = true;
 		}
-		SpinLockRelease(&btscan->btps_mutex);
+		LWLockRelease(&btscan->btps_lock);
 		if (exit_loop || !status)
 			break;
 		ConditionVariableSleep(&btscan->btps_cv, WAIT_EVENT_BTREE_PAGE);
@@ -729,10 +885,10 @@ _bt_parallel_release(IndexScanDesc scan, BlockNumber scan_page)
 	btscan = (BTParallelScanDesc) OffsetToPointer((void *) parallel_scan,
 												  parallel_scan->ps_offset);
 
-	SpinLockAcquire(&btscan->btps_mutex);
+	LWLockAcquire(&btscan->btps_lock, LW_EXCLUSIVE);
 	btscan->btps_scanPage = scan_page;
 	btscan->btps_pageStatus = BTPARALLEL_IDLE;
-	SpinLockRelease(&btscan->btps_mutex);
+	LWLockRelease(&btscan->btps_lock);
 	ConditionVariableSignal(&btscan->btps_cv);
 }
 
@@ -769,7 +925,7 @@ _bt_parallel_done(IndexScanDesc scan)
 	 * Mark the parallel scan as done, unless some other process did so
 	 * already
 	 */
-	SpinLockAcquire(&btscan->btps_mutex);
+	LWLockAcquire(&btscan->btps_lock, LW_EXCLUSIVE);
 	Assert(btscan->btps_pageStatus != BTPARALLEL_NEED_PRIMSCAN);
 	if (btscan->btps_pageStatus != BTPARALLEL_DONE)
 	{
@@ -778,7 +934,7 @@ _bt_parallel_done(IndexScanDesc scan)
 	}
 	/* Copy the authoritative shared primitive scan counter to local field */
 	scan->nsearches = btscan->btps_nsearches;
-	SpinLockRelease(&btscan->btps_mutex);
+	LWLockRelease(&btscan->btps_lock);
 
 	/* wake up all the workers associated with this parallel scan */
 	if (status_changed)
@@ -796,6 +952,7 @@ _bt_parallel_done(IndexScanDesc scan)
 void
 _bt_parallel_primscan_schedule(IndexScanDesc scan, BlockNumber prev_scan_page)
 {
+	Relation	rel = scan->indexRelation;
 	BTScanOpaque so = (BTScanOpaque) scan->opaque;
 	ParallelIndexScanDesc parallel_scan = scan->parallel_scan;
 	BTParallelScanDesc btscan;
@@ -805,7 +962,7 @@ _bt_parallel_primscan_schedule(IndexScanDesc scan, BlockNumber prev_scan_page)
 	btscan = (BTParallelScanDesc) OffsetToPointer((void *) parallel_scan,
 												  parallel_scan->ps_offset);
 
-	SpinLockAcquire(&btscan->btps_mutex);
+	LWLockAcquire(&btscan->btps_lock, LW_EXCLUSIVE);
 	if (btscan->btps_scanPage == prev_scan_page &&
 		btscan->btps_pageStatus == BTPARALLEL_IDLE)
 	{
@@ -814,14 +971,9 @@ _bt_parallel_primscan_schedule(IndexScanDesc scan, BlockNumber prev_scan_page)
 		btscan->btps_nsearches++;
 
 		/* Serialize scan's current array keys */
-		for (int i = 0; i < so->numArrayKeys; i++)
-		{
-			BTArrayKeyInfo *array = &so->arrayKeys[i];
-
-			btscan->btps_arrElems[i] = array->cur_elem;
-		}
+		_bt_parallel_serialize_arrays(rel, btscan, so);
 	}
-	SpinLockRelease(&btscan->btps_mutex);
+	LWLockRelease(&btscan->btps_lock);
 }
 
 /*
diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c
index 1bc21eb50..7bc148e4c 100644
--- a/src/backend/access/nbtree/nbtsearch.c
+++ b/src/backend/access/nbtree/nbtsearch.c
@@ -883,7 +883,6 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
 	Buffer		buf;
 	BTStack		stack;
 	OffsetNumber offnum;
-	StrategyNumber strat;
 	BTScanInsertData inskey;
 	ScanKey		startKeys[INDEX_MAX_KEYS];
 	ScanKeyData notnullkeys[INDEX_MAX_KEYS];
@@ -975,7 +974,17 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
 	 * a > or < boundary or find an attribute with no boundary (which can be
 	 * thought of as the same as "> -infinity"), we can't use keys for any
 	 * attributes to its right, because it would break our simplistic notion
-	 * of what initial positioning strategy to use.
+	 * of what initial positioning strategy to use.  In practice skip scan
+	 * typically enables us to use all scan keys here, even with a set of
+	 * input keys that leave a "gap" between two index attributes (cases with
+	 * multiple gaps will even manage this without any special restrictions).
+	 *
+	 * Skip scan works by having _bt_preprocess_keys cons up = boundary keys
+	 * for any index columns that were missing a = key in scan->keyData[], the
+	 * input scan keys passed to us by the executor.  This happens for index
+	 * attributes prior to the attribute of our final input scan key.  The
+	 * underlying = keys use skip arrays.  A skip array key on the column x
+	 * can be thought of as "x = ANY('{every possible x value}')".
 	 *
 	 * When the scan keys include cross-type operators, _bt_preprocess_keys
 	 * may not be able to eliminate redundant keys; in such cases we will
@@ -1050,6 +1059,35 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
 		{
 			if (i >= so->numberOfKeys || cur->sk_attno != curattr)
 			{
+				if (chosen && (chosen->sk_flags & SK_BT_NEGPOSINF))
+				{
+					/* -inf/+inf element from a skip array's scan key */
+					ScanKey		skiparraysk = chosen;
+					BTArrayKeyInfo *array = NULL;
+
+					for (int arridx = 0; arridx < so->numArrayKeys; arridx++)
+					{
+						array = &so->arrayKeys[arridx];
+						if (array->scan_key == skiparraysk - so->keyData)
+							break;
+					}
+
+					/* use array's inequality key in startKeys[] */
+					if (ScanDirectionIsForward(dir))
+						chosen = array->low_compare;
+					else
+						chosen = array->high_compare;
+
+					/*
+					 * If the skip array doesn't include a NULL element, it
+					 * implies a NOT NULL constraint
+					 */
+					if (!array->null_elem)
+						impliesNN = skiparraysk;
+					else
+						Assert(chosen == NULL && impliesNN == NULL);
+				}
+
 				/*
 				 * Done looking at keys for curattr.  If we didn't find a
 				 * usable boundary key, see if we can deduce a NOT NULL key.
@@ -1083,16 +1121,48 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
 					break;
 				startKeys[keysz++] = chosen;
 
+				if (chosen->sk_flags & (SK_BT_NEXT | SK_BT_PRIOR))
+				{
+					/*
+					 * Next/prior key element from a skip array's scan key.
+					 * Adjust strat_total, so that our = key gets treated like
+					 * a > key (or like a < key) within _bt_search.
+					 *
+					 * Note: 'chosen' could be marked SK_ISNULL, in which case
+					 * startKeys[] will position us at first tuple ">" NULL
+					 * (for backwards scans it'll position us at _last_ tuple
+					 * "<" NULL instead).
+					 */
+					Assert(strat_total == BTEqualStrategyNumber);
+					Assert(!(chosen->sk_flags & SK_SEARCHNOTNULL));
+					if (ScanDirectionIsForward(dir))
+					{
+						Assert(!(chosen->sk_flags & SK_BT_PRIOR));
+						strat_total = BTGreaterStrategyNumber;
+					}
+					else
+					{
+						Assert(!(chosen->sk_flags & SK_BT_NEXT));
+						strat_total = BTLessStrategyNumber;
+					}
+
+					/*
+					 * We'll never find an exact = match for a NEXT or PRIOR
+					 * sentinel sk_argument value, so there's no reason to
+					 * save any later would-be boundary keys in startKeys[]
+					 */
+					break;
+				}
+
 				/*
 				 * Adjust strat_total, and quit if we have stored a > or <
 				 * key.
 				 */
-				strat = chosen->sk_strategy;
-				if (strat != BTEqualStrategyNumber)
+				if (chosen->sk_strategy != BTEqualStrategyNumber)
 				{
-					strat_total = strat;
-					if (strat == BTGreaterStrategyNumber ||
-						strat == BTLessStrategyNumber)
+					strat_total = chosen->sk_strategy;
+					if (chosen->sk_strategy == BTGreaterStrategyNumber ||
+						chosen->sk_strategy == BTLessStrategyNumber)
 						break;
 				}
 
diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c
index 61ded00ca..972ccc90f 100644
--- a/src/backend/access/nbtree/nbtutils.c
+++ b/src/backend/access/nbtree/nbtutils.c
@@ -29,9 +29,37 @@
 #include "utils/memutils.h"
 #include "utils/rel.h"
 
+/*
+ * GUC parameters (temporary convenience for reviewers).
+ *
+ * To disable all skipping, set skipscan_prefix_cols=0.  Otherwise set it to
+ * the attribute number that you wish to make the last attribute number that
+ * we can add a skip scan key for.  For example, skipscan_prefix_cols=1 makes
+ * an index scan with qual "WHERE b = 1 AND d = 42" generate a skip scan key
+ * on the column 'a' (which is attnum 1) only, preventing us from adding one
+ * for the column 'c'.  And so only the scan key on 'b' (not the one on 'd')
+ * gets marked required within _bt_preprocess_keys -- there is no 'c' skip
+ * array to "anchor the required-ness" of 'b' through 'c' into 'd'.
+ */
+int			skipscan_prefix_cols = INDEX_MAX_KEYS;
+
+/*
+ * skipscan_skipsupport_enabled can be used to avoid using skip support.  Used
+ * to quantify the performance benefit that comes from having dedicated skip
+ * support, with a given opclass and test query.
+ */
+bool		skipscan_skipsupport_enabled = true;
+
 #define LOOK_AHEAD_REQUIRED_RECHECKS 	3
 #define LOOK_AHEAD_DEFAULT_DISTANCE 	5
 
+typedef struct BTSkipPreproc
+{
+	SkipSupportData sksup;		/* opclass skip scan support (optional) */
+	bool		use_sksup;		/* sksup initialized/skip support in use? */
+	Oid			eq_op;			/* = op to be used to add array, if any */
+} BTSkipPreproc;
+
 typedef struct BTSortArrayContext
 {
 	FmgrInfo   *sortproc;
@@ -64,15 +92,37 @@ static bool _bt_compare_array_scankey_args(IndexScanDesc scan,
 										   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_decide_skipatts(IndexScanDesc scan, BTSkipPreproc *skipatts);
+static bool _bt_skipsupport(Relation rel, int add_skip_attno,
+							BTSkipPreproc *skipatts);
 static int	_bt_compare_array_elements(const void *a, const void *b, void *arg);
 static inline int32 _bt_compare_array_skey(FmgrInfo *orderproc,
 										   Datum tupdatum, bool tupnull,
 										   Datum arrdatum, ScanKey cur);
+static void _bt_array_preproc_shrink(ScanKey arraysk, ScanKey skey,
+									 FmgrInfo *orderprocp,
+									 BTArrayKeyInfo *array, bool *qual_ok);
+static bool _bt_skip_preproc_shrink(IndexScanDesc scan, ScanKey arraysk,
+									ScanKey skey, FmgrInfo *orderprocp,
+									BTArrayKeyInfo *array, bool *qual_ok);
 static int	_bt_binsrch_array_skey(FmgrInfo *orderproc,
 								   bool cur_elem_trig, ScanDirection dir,
 								   Datum tupdatum, bool tupnull,
 								   BTArrayKeyInfo *array, ScanKey cur,
 								   int32 *set_elem_result);
+static void _bt_binsrch_skiparray_skey(FmgrInfo *orderproc,
+									   bool cur_elem_trig, ScanDirection dir,
+									   Datum tupdatum, bool tupnull,
+									   BTArrayKeyInfo *array, ScanKey cur,
+									   int32 *set_elem_result);
+static void _bt_scankey_set_low_or_high(Relation rel, ScanKey skey,
+										BTArrayKeyInfo *array, bool low_not_high);
+static void _bt_scankey_set_element(Relation rel, ScanKey skey, BTArrayKeyInfo *array,
+									Datum tupdatum, bool tupnull);
+static void _bt_scankey_unset_isnull(Relation rel, ScanKey skey, BTArrayKeyInfo *array);
+static void _bt_scankey_set_isnull(Relation rel, ScanKey skey, BTArrayKeyInfo *array);
+static bool _bt_scankey_decrement(Relation rel, ScanKey skey, BTArrayKeyInfo *array);
+static bool _bt_scankey_increment(Relation rel, ScanKey skey, BTArrayKeyInfo *array);
 static bool _bt_advance_array_keys_increment(IndexScanDesc scan, ScanDirection dir);
 static void _bt_rewind_nonrequired_arrays(IndexScanDesc scan, ScanDirection dir);
 static bool _bt_tuple_before_array_skeys(IndexScanDesc scan, ScanDirection dir,
@@ -256,6 +306,12 @@ _bt_freestack(BTStack stack)
  * 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
@@ -271,10 +327,12 @@ _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;
+	BTSkipPreproc skipatts[INDEX_MAX_KEYS];
 	int			numArrayKeys,
-				output_ikey = 0;
+				numArrayKeyData,
+				numSkipArrayKeys;
+	AttrNumber	attno_skip = 1;
 	int			origarrayatt = InvalidAttrNumber,
 				origarraykey = -1;
 	Oid			origelemtype = InvalidOid;
@@ -282,11 +340,15 @@ _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys)
 	MemoryContext oldContext;
 	ScanKey		arrayKeyData;	/* modified copy of scan->keyData */
 
-	Assert(numberOfKeys);
+	Assert(scan->numberOfKeys);
 
-	/* Quick check to see if there are any array keys */
+	/*
+	 * Quick check to see if there are any array keys, or any missing keys we
+	 * can generate a "skip scan" array key for ourselves
+	 */
 	numArrayKeys = 0;
-	for (int i = 0; i < numberOfKeys; i++)
+	numArrayKeyData = scan->numberOfKeys;	/* Initial arrayKeyData[] size */
+	for (int i = 0; i < scan->numberOfKeys; i++)
 	{
 		cur = &scan->keyData[i];
 		if (cur->sk_flags & SK_SEARCHARRAY)
@@ -302,6 +364,15 @@ _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys)
 		}
 	}
 
+	numSkipArrayKeys = _bt_decide_skipatts(scan, skipatts);
+	if (numSkipArrayKeys)
+	{
+		/* At least one skip array must be added to so->arrayKeys[] */
+		numArrayKeys += numSkipArrayKeys;
+		/* Associated scan keys must be added to arrayKeyData[], too */
+		numArrayKeyData += numSkipArrayKeys;
+	}
+
 	/* Quit if nothing to do. */
 	if (numArrayKeys == 0)
 		return NULL;
@@ -320,17 +391,23 @@ _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 */
+	/*
+	 * Process each array key, and generate skip arrays as needed.  Also copy
+	 * every scan->keyData[] input scan key (whether it's an array or not)
+	 * into the arrayKeyData array we'll return to our caller (barring any
+	 * array scan keys that we could eliminate early through array merging).
+	 */
 	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++)
 	{
 		FmgrInfo	sortproc;
 		FmgrInfo   *sortprocp = &sortproc;
@@ -346,16 +423,82 @@ _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys)
 		int			num_nonnulls;
 		int			j;
 
+		/* Create a skip array and scan key where indicated by skipatts */
+		while (numSkipArrayKeys &&
+			   attno_skip <= scan->keyData[input_ikey].sk_attno)
+		{
+			Oid			opcintype = rel->rd_opcintype[attno_skip - 1];
+			Oid			collation = rel->rd_indcollation[attno_skip - 1];
+			Oid			eq_op = skipatts[attno_skip - 1].eq_op;
+			RegProcedure cmp_proc;
+
+			if (!OidIsValid(eq_op))
+			{
+				/* won't skip using this attribute */
+				attno_skip++;
+				continue;
+			}
+
+			cmp_proc = get_opcode(eq_op);
+			if (!RegProcedureIsValid(cmp_proc))
+				elog(ERROR, "missing oprcode for skipping equals operator %u", eq_op);
+
+			cur = &arrayKeyData[numArrayKeyData];
+			Assert(attno_skip <= scan->keyData[input_ikey].sk_attno);
+			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 array fields */
+			so->arrayKeys[numArrayKeys].scan_key = numArrayKeyData;
+			so->arrayKeys[numArrayKeys].num_elems = -1;
+			so->arrayKeys[numArrayKeys].cur_elem = 0;
+			so->arrayKeys[numArrayKeys].elem_values = NULL; /* unusued */
+			so->arrayKeys[numArrayKeys].use_sksup = skipatts[attno_skip - 1].use_sksup;
+			so->arrayKeys[numArrayKeys].null_elem = true;	/* for now */
+			so->arrayKeys[numArrayKeys].sksup = skipatts[attno_skip - 1].sksup;
+			so->arrayKeys[numArrayKeys].low_compare = NULL; /* for now */
+			so->arrayKeys[numArrayKeys].high_compare = NULL;	/* for now */
+			so->arrayKeys[numArrayKeys].low_order = NULL;	/* for now */
+			so->arrayKeys[numArrayKeys].high_order = NULL;	/* for now */
+
+			/* Temporary testing GUC can disable the use of skip support */
+			if (!skipscan_skipsupport_enabled)
+				so->arrayKeys[numArrayKeys].use_sksup = false;
+
+			/*
+			 * We'll need a 3-way ORDER proc to determine when and how the
+			 * consed-up "array" will advance inside _bt_advance_array_keys.
+			 * Set one up now.
+			 */
+			_bt_setup_array_cmp(scan, cur, opcintype,
+								&so->orderProcs[numArrayKeyData], NULL);
+
+			/*
+			 * Prepare to output next scan key (might be another skip scan
+			 * key, or it could be an input scan key from scan->keyData[])
+			 */
+			numSkipArrayKeys--;
+			numArrayKeys++;
+			attno_skip++;
+			numArrayKeyData++;	/* keep this scan key/array */
+		}
+
 		/*
 		 * Provisionally copy scan key into arrayKeyData[] array we'll return
 		 * to _bt_preprocess_keys caller
 		 */
-		cur = &arrayKeyData[output_ikey];
+		cur = &arrayKeyData[numArrayKeyData];
 		*cur = scan->keyData[input_ikey];
 
 		if (!(cur->sk_flags & SK_SEARCHARRAY))
 		{
-			output_ikey++;		/* keep this non-array scan key */
+			numArrayKeyData++;	/* keep this non-array scan key */
 			continue;
 		}
 
@@ -414,7 +557,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 */
@@ -425,7 +568,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",
@@ -442,7 +585,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
@@ -517,17 +660,23 @@ _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys)
 		 * 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;
+		so->arrayKeys[numArrayKeys].scan_key = numArrayKeyData;
 		so->arrayKeys[numArrayKeys].num_elems = num_elems;
 		so->arrayKeys[numArrayKeys].elem_values = elem_values;
+		so->arrayKeys[numArrayKeys].null_elem = false;	/* unused */
+		so->arrayKeys[numArrayKeys].use_sksup = false;	/* redundant */
+		so->arrayKeys[numArrayKeys].low_compare = NULL; /* unused */
+		so->arrayKeys[numArrayKeys].high_compare = NULL;	/* unused */
+		so->arrayKeys[numArrayKeys].low_order = NULL;	/* unused */
+		so->arrayKeys[numArrayKeys].high_order = NULL;	/* unused */
 		numArrayKeys++;
-		output_ikey++;			/* keep this scan key/array */
+		numArrayKeyData++;		/* keep this scan key/array */
 	}
 
 	/* Set final number of equality-type array keys */
 	so->numArrayKeys = numArrayKeys;
-	/* Set number of scan keys remaining in arrayKeyData[] */
-	*new_numberOfKeys = output_ikey;
+	/* Set final number of scan keys in arrayKeyData[] */
+	*new_numberOfKeys = numArrayKeyData;
 
 	MemoryContextSwitchTo(oldContext);
 
@@ -633,7 +782,8 @@ _bt_preprocess_array_keys_final(IndexScanDesc scan, int *keyDataMap)
 		{
 			BTArrayKeyInfo *array = &so->arrayKeys[arrayidx];
 
-			Assert(array->num_elems > 0);
+			Assert(array->num_elems > 0 || array->num_elems == -1);
+			Assert(array->num_elems != -1 || outkey->sk_flags & SK_BT_REQFWD);
 
 			if (array->scan_key == input_ikey)
 			{
@@ -684,7 +834,7 @@ _bt_preprocess_array_keys_final(IndexScanDesc scan, int *keyDataMap)
 	 * Parallel index scans require space in shared memory to store the
 	 * current array elements (for arrays kept by preprocessing) to schedule
 	 * the next primitive index scan.  The underlying structure is protected
-	 * using a spinlock, so defensively limit its size.  In practice this can
+	 * using an LWLock, so defensively limit its size.  In practice this can
 	 * only affect parallel scans that use an incomplete opfamily.
 	 */
 	if (scan->parallel_scan && so->numArrayKeys > INDEX_MAX_KEYS)
@@ -694,6 +844,191 @@ _bt_preprocess_array_keys_final(IndexScanDesc scan, int *keyDataMap)
 								 so->numArrayKeys, INDEX_MAX_KEYS)));
 }
 
+/*
+ *	_bt_decide_skipatts() -- set index attributes requiring skip arrays
+ *
+ * _bt_preprocess_array_keys helper function.  Determines which attributes
+ * will require skip arrays/scan keys.  Also sets up skip support callbacks
+ * for attributes whose input opclass have skip support (opclasses without
+ * skip support will fall back on using next-key sentinel values when
+ * advancing the skip array to its next array element).
+ *
+ * Return value is the total number of scan keys to add as "input" scan keys
+ * for further processing within _bt_preprocess_keys.
+ */
+static int
+_bt_decide_skipatts(IndexScanDesc scan, BTSkipPreproc *skipatts)
+{
+	Relation	rel = scan->indexRelation;
+	AttrNumber	attno_inkey = 1,
+				attno_skip = 1;
+	bool		attno_has_equal = false,
+				attno_has_rowcompare = false;
+	int			numSkipArrayKeys = 0;
+
+	Assert(scan->numberOfKeys);
+
+	/*
+	 * Only add skip arrays (and associated scan keys) when doing so will
+	 * enable _bt_preprocess_keys to mark one or more lower-order input scan
+	 * keys (user-visible scan keys taken from scan->keyData[] input array) as
+	 * required to continue the scan
+	 */
+	for (int i = 0;; i++)
+	{
+		ScanKey		inkey = scan->keyData + i;
+		int			prev_numSkipArrayKeys = numSkipArrayKeys;
+
+		/*
+		 * Backfill skip arrays for any wholly omitted attributes prior to
+		 * attno_inkey
+		 */
+		while (attno_skip < attno_inkey)
+		{
+			if (!_bt_skipsupport(rel, attno_skip, &skipatts[attno_skip - 1]))
+			{
+				/*
+				 * Cannot generate a skip array for this or later attributes
+				 * (input opclass lacks an equality strategy operator)
+				 */
+				return prev_numSkipArrayKeys;
+			}
+
+			/* plan on adding a backfill skip array for this attribute */
+			numSkipArrayKeys++;
+			attno_skip++;
+		}
+
+		/*
+		 * Stop once past the final input scan key.  We deliberately never add
+		 * a skip attribute for the attribute of the last input scan key.
+		 *
+		 * If the last input scan key(s) use equality strategy, then a skip
+		 * attribute is superfluous at best.  If the last input scan key uses
+		 * an inequality strategy, then adding a skip scan array/scan key is a
+		 * valid though suboptimal transformation.  It is better to arrange
+		 * for preprocessing to allow such an input inequality scan key to
+		 * remain an inequality on output.  That way _bt_checkkeys will be
+		 * able to make best use of both of its precheck optimizations, but
+		 * _bt_first will be no less capable of efficiently finding the
+		 * starting position for each primitive index scan.
+		 */
+		if (i == scan->numberOfKeys)
+			break;
+
+		/*
+		 * Cannot keep adding skip arrays after a RowCompare
+		 */
+		if (attno_has_rowcompare)
+			break;
+
+		/*
+		 * Apply temporary testing GUC that can be used to disable skipping
+		 */
+		if (attno_inkey > skipscan_prefix_cols)
+			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.
+			 *
+			 * Adding skip arrays to an attribute that has one or more
+			 * inequality scan keys will cause preprocessing to output a range
+			 * skip array.  This will happen when preprocessing proper deals
+			 * with the redundancy between the array and its inequalities.
+			 */
+			skipatts[attno_skip - 1].eq_op = InvalidOid;
+			if (attno_has_equal)
+			{
+				/* Don't skip, attribute already has an input equality key */
+			}
+			else if (_bt_skipsupport(rel, attno_skip, &skipatts[attno_skip - 1]))
+			{
+				/*
+				 * Saw no equalities for the prior attribute, so add a range
+				 * skip array for this attribute
+				 */
+				numSkipArrayKeys++;
+			}
+			else
+			{
+				/*
+				 * Cannot generate a skip array for this or later attributes
+				 * (input opclass lacks an equality strategy operator)
+				 */
+				return 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 have any equality strategy scan
+		 * keys (while counting IS NULL scan keys as equality scan keys)
+		 */
+		if (inkey->sk_strategy == BTEqualStrategyNumber ||
+			(inkey->sk_flags & SK_SEARCHNULL))
+			attno_has_equal = true;
+
+		/*
+		 * We don't support RowCompare transformation.  Remember that we saw a
+		 * RowCompare, so that we don't keep adding skip attributes.  (We may
+		 * still backfill skip attributes before the RowCompare, so that it
+		 * will be marked required.)
+		 */
+		if (inkey->sk_flags & SK_ROW_HEADER)
+			attno_has_rowcompare = true;
+	}
+
+	return numSkipArrayKeys;
+}
+
+/*
+ *	_bt_skipsupport() -- set up skip support function in *skipatts
+ *
+ * Returns true on success, indicating that we set *skipatts with input
+ * opclass's equality operator.  Otherwise returns false (only possible for an
+ * index attribute whose input opclass comes from an incomplete opfamily).
+ */
+static bool
+_bt_skipsupport(Relation rel, int add_skip_attno, BTSkipPreproc *skipatts)
+{
+	int16	   *indoption = rel->rd_indoption;
+	Oid			opfamily = rel->rd_opfamily[add_skip_attno - 1];
+	Oid			opcintype = rel->rd_opcintype[add_skip_attno - 1];
+	bool		reverse;
+
+	/* Look up input opclass's equality operator (might fail) */
+	skipatts->eq_op = get_opfamily_member(opfamily, opcintype, opcintype,
+										  BTEqualStrategyNumber);
+
+	/*
+	 * We don't really expect opclasses that lack even an equality strategy
+	 * operator, but they're supported.  We cope by making caller not use a
+	 * skip array for this index column (nor for any lower-order columns).
+	 */
+	if (!OidIsValid(skipatts->eq_op))
+		return false;
+
+	/* Have skip support infrastructure set all SkipSupport fields */
+	reverse = (indoption[add_skip_attno - 1] & INDOPTION_DESC) != 0;
+	skipatts->use_sksup = PrepareSkipSupportFromOpclass(opfamily, opcintype,
+														reverse,
+														&skipatts->sksup);
+
+	/* might not have set up skip support, but can skip either way */
+	return true;
+}
+
 /*
  * _bt_setup_array_cmp() -- Set up array comparison functions
  *
@@ -980,26 +1315,28 @@ _bt_merge_arrays(IndexScanDesc scan, ScanKey skey, FmgrInfo *sortproc,
  * 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 inequality scan keys.
  */
 static bool
 _bt_compare_array_scankey_args(IndexScanDesc scan, ScanKey arraysk, ScanKey skey,
 							   FmgrInfo *orderproc, BTArrayKeyInfo *array,
 							   bool *qual_ok)
 {
+	BTScanOpaque so = (BTScanOpaque) scan->opaque;
 	Relation	rel = scan->indexRelation;
 	Oid			opcintype = rel->rd_opcintype[arraysk->sk_attno - 1];
-	int			cmpresult = 0,
-				cmpexact = 0,
-				matchelem,
-				new_nelems = 0;
 	FmgrInfo	crosstypeproc;
 	FmgrInfo   *orderprocp = orderproc;
+	MemoryContext oldContext;
+	bool		eliminated;
 
 	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);
+	/* 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);
@@ -1009,8 +1346,8 @@ _bt_compare_array_scankey_args(IndexScanDesc scan, ScanKey arraysk, ScanKey skey
 	 * datum of opclass input type for the index's attribute (on-disk type).
 	 * We can reuse the array's ORDER proc whenever the non-array scan key's
 	 * type is a match for the corresponding attribute's input opclass type.
-	 * Otherwise, we have to do another ORDER proc lookup so that our call to
-	 * _bt_binsrch_array_skey applies the correct comparator.
+	 * Otherwise, we have to do another ORDER proc lookup.  We have to be sure
+	 * that _bt_compare_array_skey/_bt_binsrch_array_skey use the right proc.
 	 *
 	 * Note: we have to support the convention that sk_subtype == InvalidOid
 	 * means the opclass input type; this is a hack to simplify life for
@@ -1041,11 +1378,65 @@ _bt_compare_array_scankey_args(IndexScanDesc scan, ScanKey arraysk, ScanKey skey
 			return false;
 		}
 
-		/* We have all we need to determine redundancy/contradictoriness */
+		/* We successfully looked up the required cross-type ORDER proc */
 		orderprocp = &crosstypeproc;
 		fmgr_info(cmp_proc, orderprocp);
 	}
 
+	oldContext = MemoryContextSwitchTo(so->arrayContext);
+
+	/*
+	 * Perform preprocessing of the array based on whether it's a conventional
+	 * array, or a skip array.  Sets *qual_ok correctly in passing.
+	 */
+	if (array->num_elems != -1)
+	{
+		/*
+		 * We successfully looked up the required cross-type ORDER proc, which
+		 * ensures that the scalar scan key can be eliminated as redundant
+		 */
+		eliminated = true;
+
+		_bt_array_preproc_shrink(arraysk, skey, orderprocp, array, qual_ok);
+	}
+	else
+	{
+		/*
+		 * With a skip array, it's possible that we won't be able to eliminate
+		 * the scalar scan key, despite looking up the required ORDER proc.
+		 * This happens when there's a lack of suitable cross-type support for
+		 * comparing skey to an existing inequality associated with the array.
+		 */
+		eliminated = _bt_skip_preproc_shrink(scan, arraysk, skey, orderprocp,
+											 array, qual_ok);
+	}
+
+	MemoryContextSwitchTo(oldContext);
+
+	return eliminated;
+}
+
+/*
+ * Finish off preprocessing of conventional (non-skip) array scan key when it
+ * is redundant with (or contradicted by) a non-array scalar scan key.
+ * _bt_compare_array_scankey_args helper function, called after the relevant
+ * (potentially cross-type) ORDER proc has been looked up successfully.
+ *
+ * Rewrites caller's array in-place as needed to eliminate redundant array
+ * elements.  Calling here always renders caller's scalar scan key redundant.
+ */
+static void
+_bt_array_preproc_shrink(ScanKey arraysk, ScanKey skey, FmgrInfo *orderprocp,
+						 BTArrayKeyInfo *array, bool *qual_ok)
+{
+	int			cmpresult = 0,
+				cmpexact = 0,
+				matchelem,
+				new_nelems = 0;
+
+	Assert(array->num_elems > 0);
+	Assert(!(arraysk->sk_flags & SK_BT_SKIP));
+
 	matchelem = _bt_binsrch_array_skey(orderprocp, false,
 									   NoMovementScanDirection,
 									   skey->sk_argument, false, array,
@@ -1097,6 +1488,121 @@ _bt_compare_array_scankey_args(IndexScanDesc scan, ScanKey arraysk, ScanKey skey
 
 	array->num_elems = new_nelems;
 	*qual_ok = new_nelems > 0;
+}
+
+/*
+ * Finish off preprocessing of skip array scan key when it is "redundant with"
+ * a non-array scalar scan key.  The scalar scan key must be an inequality.
+ * _bt_compare_array_scankey_args helper function, called after the relevant
+ * (potentially cross-type) ORDER proc has been looked up successfully.
+ *
+ * Unlike _bt_array_preproc_shrink, we cannot really modify caller's array
+ * in-place.  Skip arrays work by procedurally generating their elements as
+ * needed, so our approach is to store a copy of the inequality in the skip
+ * array, forcing its elements to be generated within the limits of a range.
+ *
+ * Return value indicates if the scalar scan key could be "eliminated".  We
+ * return true in the common case where caller's scan key was successfully
+ * rolled into the skip array.  We return false when we can't do that due to
+ * the presence of an existing, conflicting inequality that cannot be compared
+ * to caller's inequality due to a lack of suitable cross-type support.
+ */
+static bool
+_bt_skip_preproc_shrink(IndexScanDesc scan, ScanKey arraysk, ScanKey skey,
+						FmgrInfo *orderprocp, BTArrayKeyInfo *array,
+						bool *qual_ok)
+{
+	bool		test_result;
+
+	Assert(array->num_elems == -1);
+	Assert(arraysk->sk_flags & SK_BT_SKIP);
+
+	/*
+	 * Array must not generate a NULL array element (for "IS NULL" qual).  Its
+	 * index attribute is constrained by a strict operator, so NULL elements
+	 * must not be returned by the scan (it would be wrong to allow it).
+	 */
+	array->null_elem = false;
+	*qual_ok = true;
+
+	/*
+	 * Store a copy of caller's scalar scan key, plus a copy of the operator's
+	 * corresponding 3-way ORDER proc.
+	 *
+	 * 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 scan code can assume that it'll always
+	 * be safe to use the same-type ORDER procs stored in so->orderProcs[],
+	 * provided the array's scan key isn't marked NEGPOSINF.  When the array's
+	 * scan key is marked NEGPOSINF, then it'll lack a valid sk_argument, and
+	 * it'll be necessary to apply low_compare and/or high_compare separately.
+	 *
+	 * Under this scheme, there isn't any danger of anybody becoming confused
+	 * about which type is used where, even in cross-type scenarios; each scan
+	 * key consistently uses the same underlying type.  While NEGPOSINF is a
+	 * distinct array element, it is only used to force low_compare and/or
+	 * high_compare to find the real first (or final) element in the index.
+	 * You can think of NEGPOSINF as representing an imaginary point in the
+	 * key space immediately before the start (or immediately after the end)
+	 * of the true first (or true final) matching value.
+	 */
+	switch (skey->sk_strategy)
+	{
+		case BTLessStrategyNumber:
+		case BTLessEqualStrategyNumber:
+			if (array->high_compare)
+			{
+				/* try to keep only one high_compare inequality */
+				if (!_bt_compare_scankey_args(scan, array->high_compare, skey,
+											  array->high_compare, NULL, NULL,
+											  &test_result))
+					return false;	/* can't make new high_compare redundant  */
+
+				if (!test_result)
+					return true;	/* discard new high_compare */
+
+				/* replace old high_compare with new one */
+			}
+			else
+			{
+				/* Allocate scan key/ORDER proc buffers in so->arrayContext */
+				array->high_compare = palloc(sizeof(ScanKeyData));
+				array->high_order = palloc(sizeof(FmgrInfo));
+			}
+
+			*array->high_compare = *skey;
+			*array->high_order = *orderprocp;
+			break;
+		case BTGreaterEqualStrategyNumber:
+		case BTGreaterStrategyNumber:
+			if (array->low_compare)
+			{
+				/* try to keep only one low_compare inequality */
+				if (!_bt_compare_scankey_args(scan, array->low_compare, skey,
+											  array->low_compare, NULL, NULL,
+											  &test_result))
+					return false;	/* can't make new low_compare redundant  */
+
+				if (!test_result)
+					return true;	/* discard new low_compare */
+
+				/* replace old low_compare with new one */
+			}
+			else
+			{
+				/* Allocate scan key/ORDER proc buffers in so->arrayContext */
+				array->low_compare = palloc(sizeof(ScanKeyData));
+				array->low_order = palloc(sizeof(FmgrInfo));
+			}
+
+			*array->low_compare = *skey;
+			*array->low_order = *orderprocp;
+			break;
+		default:
+			elog(ERROR, "unrecognized StrategyNumber: %d",
+				 (int) skey->sk_strategy);
+			break;
+	}
 
 	return true;
 }
@@ -1220,6 +1726,8 @@ _bt_binsrch_array_skey(FmgrInfo *orderproc,
 	Datum		arrdatum;
 
 	Assert(cur->sk_flags & SK_SEARCHARRAY);
+	Assert(!(cur->sk_flags & SK_BT_SKIP));
+	Assert(!(cur->sk_flags & SK_ISNULL));	/* plain arrays can't do this */
 	Assert(cur->sk_strategy == BTEqualStrategyNumber);
 
 	if (cur_elem_trig)
@@ -1342,6 +1850,98 @@ _bt_binsrch_array_skey(FmgrInfo *orderproc,
 	return low_elem;
 }
 
+/*
+ * _bt_binsrch_skiparray_skey() -- "Binary search" within a skip array
+ *
+ * Does not return an index into the array, because the array doesn't really
+ * have any elements (it generates its array elements procedurally instead).
+ * Note that this may include a NULL value/an IS NULL qual.
+ *
+ * Sets *set_elem_result just like _bt_binsrch_array_skey would with a true
+ * array.  The value 0 indicates that tupdatum/tupnull is within the range of
+ * the skip array.  Other values indicate what _bt_compare_array_skey returned
+ * for the best available match to tupdatum/tupnull (in practice this means
+ * either the lowest item or the highest item in the range of the array).
+ *
+ * cur_elem_trig indicates if array advancement was triggered by this array's
+ * scan key.  We use this to optimize-away comparisons that are known by our
+ * caller to be unnecessary from context, just like _bt_binsrch_array_skey.
+ *
+ * Note: This function doesn't actually binary search.  It uses an interface
+ * that's as similar to _bt_binsrch_array_skey as possible for consistency.
+ * "Binary searching a skip array" just means determining if tupdatum/tupnull
+ * are before, within, or beyond the range of caller's skip array.
+ */
+static void
+_bt_binsrch_skiparray_skey(FmgrInfo *orderproc,
+						   bool cur_elem_trig, ScanDirection dir,
+						   Datum tupdatum, bool tupnull,
+						   BTArrayKeyInfo *array, ScanKey cur,
+						   int32 *set_elem_result)
+{
+	Assert(cur->sk_flags & SK_BT_SKIP);
+	Assert(cur->sk_flags & SK_SEARCHARRAY);
+	Assert(cur->sk_flags & SK_BT_REQFWD);
+	Assert(array->num_elems == -1);
+	Assert(!ScanDirectionIsNoMovement(dir));
+
+	if (tupnull)				/* NULL tupdatum */
+	{
+		if (array->null_elem)
+			*set_elem_result = 0;	/* NULL "=" NULL */
+		else if (cur->sk_flags & SK_BT_NULLS_FIRST)
+			*set_elem_result = -1;	/* NULL "<" NOT_NULL */
+		else
+			*set_elem_result = 1;	/* NULL ">" NOT_NULL */
+
+		return;
+	}
+
+	/*
+	 * Array inequalities determine whether tupdatum is within the range of
+	 * caller's skip array
+	 */
+	*set_elem_result = 0;
+	if (ScanDirectionIsForward(dir))
+	{
+		/*
+		 * Evaluate low_compare first (unless cur_elem_trig tells us that it
+		 * cannot possibly fail to be satisfied), then evaluate high_compare
+		 */
+		if (!cur_elem_trig && array->low_compare &&
+			!DatumGetBool(FunctionCall2Coll(&array->low_compare->sk_func,
+											array->low_compare->sk_collation,
+											tupdatum,
+											array->low_compare->sk_argument)))
+			*set_elem_result = -1;
+		else if (array->high_compare &&
+				 !DatumGetBool(FunctionCall2Coll(&array->high_compare->sk_func,
+												 array->high_compare->sk_collation,
+												 tupdatum,
+												 array->high_compare->sk_argument)))
+			*set_elem_result = 1;
+	}
+	else
+	{
+		/*
+		 * Evaluate high_compare first (unless cur_elem_trig tells us that it
+		 * cannot possibly fail to be satisfied), then evaluate low_compare
+		 */
+		if (!cur_elem_trig && array->high_compare &&
+			!DatumGetBool(FunctionCall2Coll(&array->high_compare->sk_func,
+											array->high_compare->sk_collation,
+											tupdatum,
+											array->high_compare->sk_argument)))
+			*set_elem_result = 1;
+		else if (array->low_compare &&
+				 !DatumGetBool(FunctionCall2Coll(&array->low_compare->sk_func,
+												 array->low_compare->sk_collation,
+												 tupdatum,
+												 array->low_compare->sk_argument)))
+			*set_elem_result = -1;
+	}
+}
+
 /*
  * _bt_start_array_keys() -- Initialize array keys at start of a scan
  *
@@ -1351,29 +1951,486 @@ _bt_binsrch_array_skey(FmgrInfo *orderproc,
 void
 _bt_start_array_keys(IndexScanDesc scan, ScanDirection dir)
 {
+	Relation	rel = scan->indexRelation;
 	BTScanOpaque so = (BTScanOpaque) scan->opaque;
-	int			i;
 
 	Assert(so->numArrayKeys);
 	Assert(so->qual_ok);
 
-	for (i = 0; i < so->numArrayKeys; i++)
+	for (int i = 0; i < so->numArrayKeys; i++)
 	{
-		BTArrayKeyInfo *curArrayKey = &so->arrayKeys[i];
-		ScanKey		skey = &so->keyData[curArrayKey->scan_key];
+		BTArrayKeyInfo *array = &so->arrayKeys[i];
+		ScanKey		skey = &so->keyData[array->scan_key];
 
-		Assert(curArrayKey->num_elems > 0);
 		Assert(skey->sk_flags & SK_SEARCHARRAY);
 
-		if (ScanDirectionIsBackward(dir))
-			curArrayKey->cur_elem = curArrayKey->num_elems - 1;
-		else
-			curArrayKey->cur_elem = 0;
-		skey->sk_argument = curArrayKey->elem_values[curArrayKey->cur_elem];
+		_bt_scankey_set_low_or_high(rel, skey, array,
+									ScanDirectionIsForward(dir));
 	}
 	so->scanBehind = so->oppositeDirCheck = false;	/* reset */
 }
 
+/*
+ * _bt_scankey_set_low_or_high() -- Set array scan key to lowest/highest element
+ *
+ * Caller also passes associated scan key, which will have its argument set to
+ * the lowest/highest array value in passing.
+ */
+static void
+_bt_scankey_set_low_or_high(Relation rel, ScanKey skey, BTArrayKeyInfo *array,
+							bool low_not_high)
+{
+	Form_pg_attribute attr;
+
+	Assert(skey->sk_flags & SK_SEARCHARRAY);
+
+	if (array->num_elems != -1)
+	{
+		/* set low or high element for conventional array */
+		int			set_elem = 0;
+
+		Assert(!(skey->sk_flags & SK_BT_SKIP));
+
+		if (!low_not_high)
+			set_elem = array->num_elems - 1;
+
+		/*
+		 * Just copy over array datum (only skip arrays require freeing and
+		 * allocating memory for sk_argument)
+		 */
+		array->cur_elem = set_elem;
+		skey->sk_argument = array->elem_values[set_elem];
+
+		return;
+	}
+
+	/* set low or high element for skip array */
+	Assert(skey->sk_flags & SK_BT_SKIP);
+	Assert(array->num_elems == -1);
+
+	/* Free memory previously allocated for sk_argument if needed */
+	attr = TupleDescAttr(RelationGetDescr(rel), skey->sk_attno - 1);
+	if (!attr->attbyval && skey->sk_argument)
+		pfree(DatumGetPointer(skey->sk_argument));
+
+	/* Reset flags */
+	skey->sk_argument = (Datum) 0;
+	skey->sk_flags &= ~(SK_SEARCHNULL | SK_ISNULL |
+						SK_BT_NEGPOSINF | SK_BT_NEXT | SK_BT_PRIOR);
+
+	if (array->null_elem &&
+		(low_not_high == ((skey->sk_flags & SK_BT_NULLS_FIRST) != 0)))
+	{
+		/* Requested element (either lowest or highest) has the value NULL */
+		skey->sk_flags |= (SK_SEARCHNULL | SK_ISNULL);
+	}
+	else if (low_not_high)
+	{
+		/* Setting skip array to lowest element, which isn't just NULL */
+		if (array->use_sksup && !array->low_compare)
+			skey->sk_argument = datumCopy(array->sksup.low_elem,
+										  attr->attbyval, attr->attlen);
+		else
+			skey->sk_flags |= SK_BT_NEGPOSINF;
+	}
+	else
+	{
+		/* Setting skip array to highest element, which isn't just NULL */
+		if (array->use_sksup && !array->high_compare)
+			skey->sk_argument = datumCopy(array->sksup.high_elem,
+										  attr->attbyval, attr->attlen);
+		else
+			skey->sk_flags |= SK_BT_NEGPOSINF;
+	}
+}
+
+/*
+ * _bt_scankey_set_element() -- Set skip array scan key's sk_argument
+ *
+ * Sets scan key to "IS NULL" when required, and handles memory management for
+ * pass-by-reference types.
+ */
+static void
+_bt_scankey_set_element(Relation rel, ScanKey skey, BTArrayKeyInfo *array,
+						Datum tupdatum, bool tupnull)
+{
+	/* tupdatum within the range of low_value/high_value */
+	Form_pg_attribute attr;
+
+	Assert(skey->sk_flags & SK_BT_SKIP);
+	Assert(skey->sk_flags & SK_SEARCHARRAY);
+	Assert(!(tupnull && !array->null_elem));
+
+	/* Free memory previously allocated for sk_argument if needed */
+	attr = TupleDescAttr(RelationGetDescr(rel), skey->sk_attno - 1);
+	if (!attr->attbyval && skey->sk_argument)
+		pfree(DatumGetPointer(skey->sk_argument));
+	skey->sk_argument = (Datum) 0;
+	skey->sk_flags &= ~(SK_SEARCHNULL | SK_ISNULL |
+						SK_BT_NEGPOSINF | SK_BT_NEXT | SK_BT_PRIOR);
+	if (!tupnull)
+		skey->sk_argument = datumCopy(tupdatum, attr->attbyval, attr->attlen);
+	else
+		skey->sk_flags |= (SK_SEARCHNULL | SK_ISNULL);
+}
+
+/*
+ * _bt_scankey_unset_isnull() -- increment/decrement scan key from NULL
+ *
+ * Unsets scan key's "IS NULL" marking, and sets the non-NULL value from the
+ * array immediately before (or immediate after) NULL in the key space.
+ */
+static void
+_bt_scankey_unset_isnull(Relation rel, ScanKey skey, BTArrayKeyInfo *array)
+{
+	Form_pg_attribute attr;
+
+	Assert(skey->sk_flags & SK_BT_SKIP);
+	Assert(skey->sk_flags & SK_SEARCHARRAY);
+	Assert(skey->sk_flags & SK_SEARCHNULL);
+	Assert(skey->sk_flags & SK_ISNULL);
+	Assert(!(skey->sk_flags & (SK_BT_NEGPOSINF | SK_BT_NEXT | SK_BT_PRIOR)));
+	Assert(skey->sk_argument == 0);
+	Assert(array->use_sksup && array->null_elem &&
+		   !array->low_compare && !array->high_compare);
+
+	/*
+	 * sk_argument must be set to whatever non-NULL value comes immediately
+	 * before or after NULL
+	 */
+	attr = TupleDescAttr(RelationGetDescr(rel), skey->sk_attno - 1);
+	skey->sk_flags &= ~(SK_SEARCHNULL | SK_ISNULL);
+	if (skey->sk_flags & SK_BT_NULLS_FIRST)
+		skey->sk_argument = datumCopy(array->sksup.low_elem,
+									  attr->attbyval, attr->attlen);
+	else
+		skey->sk_argument = datumCopy(array->sksup.high_elem,
+									  attr->attbyval, attr->attlen);
+}
+
+/*
+ * _bt_scankey_set_isnull() -- decrement/increment scan key to NULL
+ */
+static void
+_bt_scankey_set_isnull(Relation rel, ScanKey skey, BTArrayKeyInfo *array)
+{
+	Form_pg_attribute attr;
+
+	Assert(skey->sk_flags & SK_BT_SKIP);
+	Assert(skey->sk_flags & SK_SEARCHARRAY);
+	Assert(!(skey->sk_flags & (SK_SEARCHNULL | SK_ISNULL |
+							   SK_BT_NEGPOSINF | SK_BT_NEXT | SK_BT_PRIOR)));
+	Assert(array->null_elem);
+	Assert(!array->low_compare && !array->high_compare);
+
+	/* Free memory previously allocated for sk_argument if needed */
+	attr = TupleDescAttr(RelationGetDescr(rel), skey->sk_attno - 1);
+	if (!attr->attbyval && skey->sk_argument)
+		pfree(DatumGetPointer(skey->sk_argument));
+
+	/* Set sk_argument to NULL */
+	skey->sk_argument = (Datum) 0;
+	skey->sk_flags |= (SK_SEARCHNULL | SK_ISNULL);
+}
+
+/*
+ * _bt_scankey_decrement() -- decrement array scan key's sk_argument
+ *
+ * Return value indicates whether caller's array was successfully decremented.
+ * Cannot decrement an array whose current element is already the first one.
+ */
+static bool
+_bt_scankey_decrement(Relation rel, ScanKey skey, BTArrayKeyInfo *array)
+{
+	bool		underflow = false;
+	Datum		dec_sk_argument;
+	Form_pg_attribute attr;
+
+	Assert(skey->sk_flags & SK_SEARCHARRAY);
+	Assert(!(skey->sk_flags & (SK_BT_NEXT | SK_BT_PRIOR)));
+
+	/* Regular (non-skip) array? */
+	if (array->num_elems != -1)
+	{
+		Assert(!(skey->sk_flags & SK_BT_SKIP));
+		Assert(!(skey->sk_flags & SK_BT_NEGPOSINF));
+		if (array->cur_elem > 0)
+		{
+			/*
+			 * Just copy over array datum (only skip arrays require freeing
+			 * and allocating memory for sk_argument)
+			 */
+			array->cur_elem--;
+			skey->sk_argument = array->elem_values[array->cur_elem];
+
+			/* Successfully decremented array */
+			return true;
+		}
+
+		/* Cannot decrement to before first array element */
+		return false;
+	}
+
+	/* Nope, this is a skip array */
+	Assert(skey->sk_flags & SK_BT_SKIP);
+
+	/* The sentinel value -inf is never decrementable */
+	if (skey->sk_flags & SK_BT_NEGPOSINF)
+		return false;
+
+	/*
+	 * When the current array element is NULL, and the lowest sorting value in
+	 * the index is also NULL, we cannot decrement before first array element
+	 */
+	if ((skey->sk_flags & SK_ISNULL) && (skey->sk_flags & SK_BT_NULLS_FIRST))
+		return false;
+
+	/*
+	 * Opclasses without skip support "decrement" the scan key's current
+	 * element by setting the PRIOR flag.  The true prior value can only be
+	 * determined when the scan reads lower sorting tuples.
+	 *
+	 * When the current array element is NULL, and the highest sorting value
+	 * in the index is also NULL, _bt_first can find the highest non-NULL.
+	 */
+	if (!array->use_sksup)
+	{
+		/*
+		 * Determine as best we can (given the lack of skip support) whether
+		 * the prior element will turn out to be out of bounds for the skip
+		 * array.
+		 *
+		 * Skip arrays (that lack skip support) can only do this when their
+		 * low_compare is for an >= inequality; if the current array element
+		 * is == the inequality's sk_argument, then the true prior value
+		 * cannot possibly satisfy low_compare.  We can give up right away.
+		 */
+		if (array->low_compare &&
+			array->low_compare->sk_strategy == BTGreaterEqualStrategyNumber &&
+			_bt_compare_array_skey(array->low_order,
+								   array->low_compare->sk_argument, false,
+								   skey->sk_argument, skey) == 0)
+			return false;
+
+		/* else the scan must figure out the true prior value */
+		skey->sk_flags |= SK_BT_PRIOR;
+		return true;
+	}
+
+	/*
+	 * Opclasses with skip support decrement the scan key's current element
+	 * using a callback
+	 */
+	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).
+		 *
+		 * Decrement current array element to the high_elem value provided by
+		 * opclass skip support routine.
+		 */
+		_bt_scankey_unset_isnull(rel, skey, array);
+		return true;
+	}
+
+	/*
+	 * Ask opclass support routine to provide decremented copy of existing
+	 * non-NULL sk_argument
+	 */
+	dec_sk_argument = array->sksup.decrement(rel, skey->sk_argument, &underflow);
+
+	if (underflow)
+	{
+		/* dec_sk_argument has undefined value (so no pfree) */
+		if (array->null_elem && (skey->sk_flags & SK_BT_NULLS_FIRST))
+		{
+			/* "Decrement" sk_argument to NULL */
+			_bt_scankey_set_isnull(rel, skey, array);
+			return true;
+		}
+
+		/* Cannot decrement before first array element */
+		return false;
+	}
+
+	/*
+	 * Successfully decremented sk_argument to a non-NULL value.  Make sure
+	 * that the decremented value is still within the range of the skip array.
+	 */
+	attr = TupleDescAttr(RelationGetDescr(rel), skey->sk_attno - 1);
+	if (array->low_compare &&
+		!DatumGetBool(FunctionCall2Coll(&array->low_compare->sk_func,
+										array->low_compare->sk_collation,
+										dec_sk_argument,
+										array->low_compare->sk_argument)))
+	{
+		/* Keep existing sk_argument after all */
+		if (!attr->attbyval)
+			pfree(DatumGetPointer(dec_sk_argument));
+
+		/* Cannot decrement before first array element */
+		return false;
+	}
+
+	/* Accept non-NULL datum value from opclass decrement callback */
+	if (!attr->attbyval && skey->sk_argument)
+		pfree(DatumGetPointer(skey->sk_argument));
+	skey->sk_argument = dec_sk_argument;
+
+	return true;
+}
+
+/*
+ * _bt_scankey_increment() -- increment array scan key's sk_argument
+ *
+ * Return value indicates whether caller's array was successfully incremented.
+ * Cannot increment an array whose current element is already the final one.
+ */
+static bool
+_bt_scankey_increment(Relation rel, ScanKey skey, BTArrayKeyInfo *array)
+{
+	bool		overflow = false;
+	Datum		inc_sk_argument;
+	Form_pg_attribute attr;
+
+	Assert(skey->sk_flags & SK_SEARCHARRAY);
+	Assert(!(skey->sk_flags & (SK_BT_NEXT | SK_BT_PRIOR)));
+
+	/* Regular (non-skip) array? */
+	if (array->num_elems != -1)
+	{
+		Assert(!(skey->sk_flags & SK_BT_SKIP));
+		Assert(!(skey->sk_flags & SK_BT_NEGPOSINF));
+		if (array->cur_elem < array->num_elems - 1)
+		{
+			/*
+			 * Just copy over array datum (only skip arrays require freeing
+			 * and allocating memory for sk_argument)
+			 */
+			array->cur_elem++;
+			skey->sk_argument = array->elem_values[array->cur_elem];
+
+			/* Successfully incremented array */
+			return true;
+		}
+
+		/* Cannot increment past final array element */
+		return false;
+	}
+
+	/* Nope, this is a skip array */
+	Assert(skey->sk_flags & SK_BT_SKIP);
+
+	/* The sentinel value +inf is never incrementable */
+	if (skey->sk_flags & SK_BT_NEGPOSINF)
+		return false;
+
+	/*
+	 * When the current array element is NULL, and the highest sorting value
+	 * in the index is also NULL, we cannot increment past the final element
+	 */
+	if ((skey->sk_flags & SK_ISNULL) && !(skey->sk_flags & SK_BT_NULLS_FIRST))
+		return false;
+
+	/*
+	 * Opclasses without skip support "increment" the scan key's current
+	 * element by setting the NEXT flag.  The true next value can only be
+	 * determined when the scan reads higher sorting tuples.
+	 *
+	 * When the current array element is NULL, and the lowest sorting value in
+	 * the index is also NULL, _bt_first can find the lowest non-NULL.
+	 */
+	if (!array->use_sksup)
+	{
+		/*
+		 * Determine as best we can (given the lack of skip support) whether
+		 * the next element will turn out to be out of bounds for the skip
+		 * array.
+		 *
+		 * Skip arrays (that lack skip support) can only do this when their
+		 * high_compare is for an <= inequality; if the current array element
+		 * is == the inequality's sk_argument, then the true next value cannot
+		 * possibly satisfy high_compare.  We can give up right away.
+		 */
+		if (array->high_compare &&
+			array->high_compare->sk_strategy == BTLessEqualStrategyNumber &&
+			_bt_compare_array_skey(array->high_order,
+								   array->high_compare->sk_argument, false,
+								   skey->sk_argument, skey) == 0)
+			return false;
+
+		/* else the scan must figure out the true next value */
+		skey->sk_flags |= SK_BT_NEXT;
+		return true;
+	}
+
+	/*
+	 * Opclasses with skip support increment the scan key's current element
+	 * using a callback
+	 */
+	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 current array element to the low_elem value provided by
+		 * opclass skip support routine.
+		 */
+		_bt_scankey_unset_isnull(rel, skey, array);
+		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, &overflow);
+
+	if (overflow)
+	{
+		/* inc_sk_argument has undefined value (so no pfree) */
+		if (array->null_elem && !(skey->sk_flags & SK_BT_NULLS_FIRST))
+		{
+			/* "Increment" sk_argument to NULL */
+			_bt_scankey_set_isnull(rel, skey, array);
+			return true;
+		}
+
+		/* Cannot increment past final array element */
+		return false;
+	}
+
+	/*
+	 * Successfully incremented sk_argument to a non-NULL value.  Make sure
+	 * that the incremented value is still within the range of the skip array.
+	 */
+	attr = TupleDescAttr(RelationGetDescr(rel), skey->sk_attno - 1);
+	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 (!attr->attbyval)
+			pfree(DatumGetPointer(inc_sk_argument));
+
+		/* Cannot increment past final array element */
+		return false;
+	}
+
+	/* Accept non-NULL datum value from opclass increment callback */
+	if (!attr->attbyval && skey->sk_argument)
+		pfree(DatumGetPointer(skey->sk_argument));
+	skey->sk_argument = inc_sk_argument;
+
+	return true;
+}
+
 /*
  * _bt_advance_array_keys_increment() -- Advance to next set of array elements
  *
@@ -1389,6 +2446,7 @@ _bt_start_array_keys(IndexScanDesc scan, ScanDirection dir)
 static bool
 _bt_advance_array_keys_increment(IndexScanDesc scan, ScanDirection dir)
 {
+	Relation	rel = scan->indexRelation;
 	BTScanOpaque so = (BTScanOpaque) scan->opaque;
 
 	/*
@@ -1398,29 +2456,30 @@ _bt_advance_array_keys_increment(IndexScanDesc scan, ScanDirection dir)
 	 */
 	for (int i = so->numArrayKeys - 1; i >= 0; i--)
 	{
-		BTArrayKeyInfo *curArrayKey = &so->arrayKeys[i];
-		ScanKey		skey = &so->keyData[curArrayKey->scan_key];
-		int			cur_elem = curArrayKey->cur_elem;
-		int			num_elems = curArrayKey->num_elems;
-		bool		rolled = false;
+		BTArrayKeyInfo *array = &so->arrayKeys[i];
+		ScanKey		skey = &so->keyData[array->scan_key];
 
-		if (ScanDirectionIsForward(dir) && ++cur_elem >= num_elems)
+		if (ScanDirectionIsForward(dir))
 		{
-			cur_elem = 0;
-			rolled = true;
+			if (_bt_scankey_increment(rel, skey, array))
+				return true;
 		}
-		else if (ScanDirectionIsBackward(dir) && --cur_elem < 0)
+		else
 		{
-			cur_elem = num_elems - 1;
-			rolled = true;
+			if (_bt_scankey_decrement(rel, skey, array))
+				return true;
 		}
 
-		curArrayKey->cur_elem = cur_elem;
-		skey->sk_argument = curArrayKey->elem_values[cur_elem];
-		if (!rolled)
-			return true;
+		/*
+		 * Couldn't increment (or decrement) array.  Handle array roll over.
+		 *
+		 * Start over at the array's lowest sorting value (or its highest
+		 * value, for backward scans)...
+		 */
+		_bt_scankey_set_low_or_high(rel, skey, array,
+									ScanDirectionIsForward(dir));
 
-		/* Need to advance next array key, if any */
+		/* ...then increment (or decrement) next most significant array */
 	}
 
 	/*
@@ -1475,6 +2534,7 @@ _bt_advance_array_keys_increment(IndexScanDesc scan, ScanDirection dir)
 static void
 _bt_rewind_nonrequired_arrays(IndexScanDesc scan, ScanDirection dir)
 {
+	Relation	rel = scan->indexRelation;
 	BTScanOpaque so = (BTScanOpaque) scan->opaque;
 	int			arrayidx = 0;
 
@@ -1482,7 +2542,6 @@ _bt_rewind_nonrequired_arrays(IndexScanDesc scan, ScanDirection dir)
 	{
 		ScanKey		cur = so->keyData + ikey;
 		BTArrayKeyInfo *array = NULL;
-		int			first_elem_dir;
 
 		if (!(cur->sk_flags & SK_SEARCHARRAY) ||
 			cur->sk_strategy != BTEqualStrategyNumber)
@@ -1494,16 +2553,10 @@ _bt_rewind_nonrequired_arrays(IndexScanDesc scan, ScanDirection dir)
 		if ((cur->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)))
 			continue;
 
-		if (ScanDirectionIsForward(dir))
-			first_elem_dir = 0;
-		else
-			first_elem_dir = array->num_elems - 1;
+		Assert(array->num_elems != -1); /* No non-required skip arrays */
 
-		if (array->cur_elem != first_elem_dir)
-		{
-			array->cur_elem = first_elem_dir;
-			cur->sk_argument = array->elem_values[first_elem_dir];
-		}
+		_bt_scankey_set_low_or_high(rel, cur, array,
+									ScanDirectionIsForward(dir));
 	}
 }
 
@@ -1628,9 +2681,94 @@ _bt_tuple_before_array_skeys(IndexScanDesc scan, ScanDirection dir,
 
 		tupdatum = index_getattr(tuple, cur->sk_attno, tupdesc, &tupnull);
 
-		result = _bt_compare_array_skey(&so->orderProcs[ikey],
-										tupdatum, tupnull,
-										cur->sk_argument, cur);
+		if (!(cur->sk_flags & SK_BT_NEGPOSINF))
+		{
+			/* Scankey has a valid/comparable sk_argument value (not -inf) */
+			result = _bt_compare_array_skey(&so->orderProcs[ikey],
+											tupdatum, tupnull,
+											cur->sk_argument, cur);
+
+			if (result == 0 && (cur->sk_flags & SK_BT_NEXT))
+			{
+				/*
+				 * tupdatum is == sk_argument, but true current array element
+				 * is actually "sk_argument + infinitesimal"
+				 */
+				if (ScanDirectionIsForward(dir))
+				{
+					/* tupdatum is still < "sk_argument + infinitesimal" */
+					return true;
+				}
+
+				/*
+				 * Scan direction was forward during the scan's last call to
+				 * _bt_advance_array_keys, but has since changed to backward.
+				 * It's time for caller to advance the scan's array keys.
+				 * Array goes back to having tupdatum be its current element.
+				 */
+				return false;
+			}
+			else if (result == 0 && (cur->sk_flags & SK_BT_PRIOR))
+			{
+				/*
+				 * tupdatum is == sk_argument, but true current array element
+				 * is actually "sk_argument - infinitesimal"
+				 */
+				if (ScanDirectionIsBackward(dir))
+				{
+					/* tupdatum is still > "sk_argument - infinitesimal" */
+					return true;
+				}
+
+				/*
+				 * Scan direction was backward during the scan's last call to
+				 * _bt_advance_array_keys, but has since changed to forward.
+				 * It's time for caller to advance the scan's array keys.
+				 * Array goes back to having tupdatum be its current element.
+				 */
+				return false;
+			}
+		}
+		else
+		{
+			/*
+			 * Scankey searches for the sentinel value -inf (or +inf).
+			 *
+			 * Note: -inf could mean "absolute" -inf, or it could represent an
+			 * imaginary point in the key space that comes immediately before
+			 * the first real value that satisfies the array's low_compare.
+			 * +inf and high_compare work similarly.
+			 */
+			BTArrayKeyInfo *array = NULL;
+
+			for (int arrayidx = 0; arrayidx < so->numArrayKeys; arrayidx++)
+			{
+				array = &so->arrayKeys[arrayidx];
+				if (array->scan_key == ikey)
+					break;
+			}
+
+			/*
+			 * Compare tupdatum against -inf using array's low_compare, if any
+			 * (or compare it against +inf using array's high_compare).
+			 *
+			 * Optimization: avoid uselessly evaluating array's high_compare
+			 * (or uselessly evaluating array's low_compare) by passing
+			 * cur_elem_trig=true, along with an inverted scan direction.
+			 */
+			_bt_binsrch_skiparray_skey(&so->orderProcs[ikey], true, -dir,
+									   tupdatum, tupnull, array, cur,
+									   &result);
+
+			if (result == 0)
+			{
+				/*
+				 * tupdatum is > -inf sk_argument (or < +inf sk_argument).
+				 * It's time for caller to advance the scan's array keys.
+				 */
+				return false;
+			}
+		}
 
 		/*
 		 * Does this comparison indicate that caller must _not_ advance the
@@ -1962,18 +3100,9 @@ _bt_advance_array_keys(IndexScanDesc scan, BTReadPageState *pstate,
 		 */
 		if (beyond_end_advance)
 		{
-			int			final_elem_dir;
-
-			if (ScanDirectionIsBackward(dir) || !array)
-				final_elem_dir = 0;
-			else
-				final_elem_dir = array->num_elems - 1;
-
-			if (array && array->cur_elem != final_elem_dir)
-			{
-				array->cur_elem = final_elem_dir;
-				cur->sk_argument = array->elem_values[final_elem_dir];
-			}
+			if (array)
+				_bt_scankey_set_low_or_high(rel, cur, array,
+											ScanDirectionIsBackward(dir));
 
 			continue;
 		}
@@ -1998,18 +3127,9 @@ _bt_advance_array_keys(IndexScanDesc scan, BTReadPageState *pstate,
 		 */
 		if (!all_required_satisfied || cur->sk_attno > tupnatts)
 		{
-			int			first_elem_dir;
-
-			if (ScanDirectionIsForward(dir) || !array)
-				first_elem_dir = 0;
-			else
-				first_elem_dir = array->num_elems - 1;
-
-			if (array && array->cur_elem != first_elem_dir)
-			{
-				array->cur_elem = first_elem_dir;
-				cur->sk_argument = array->elem_values[first_elem_dir];
-			}
+			if (array)
+				_bt_scankey_set_low_or_high(rel, cur, array,
+											ScanDirectionIsForward(dir));
 
 			continue;
 		}
@@ -2027,12 +3147,21 @@ _bt_advance_array_keys(IndexScanDesc scan, BTReadPageState *pstate,
 			/*
 			 * Binary search for closest match that's available from the array
 			 */
-			set_elem = _bt_binsrch_array_skey(&so->orderProcs[ikey],
-											  cur_elem_trig, dir,
-											  tupdatum, tupnull, array, cur,
-											  &result);
+			if (array->num_elems != -1)
+				set_elem = _bt_binsrch_array_skey(&so->orderProcs[ikey],
+												  cur_elem_trig, dir,
+												  tupdatum, tupnull, array, cur,
+												  &result);
 
-			Assert(set_elem >= 0 && set_elem < array->num_elems);
+			/*
+			 * "Binary search" by checking if tupdatum/tupnull are within the
+			 * range of the skip array
+			 */
+			else
+				_bt_binsrch_skiparray_skey(&so->orderProcs[ikey],
+										   cur_elem_trig, dir,
+										   tupdatum, tupnull, array, cur,
+										   &result);
 		}
 		else
 		{
@@ -2108,11 +3237,62 @@ _bt_advance_array_keys(IndexScanDesc scan, BTReadPageState *pstate,
 			}
 		}
 
-		/* Advance array keys, even when set_elem isn't an exact match */
-		if (array && array->cur_elem != set_elem)
+		if (!array)
+			continue;			/* cannot advance a non-array */
+
+		/* Advance array keys, even when we don't have an exact match */
+		if (array->num_elems != -1)
 		{
-			array->cur_elem = set_elem;
-			cur->sk_argument = array->elem_values[set_elem];
+			/* Conventional array, use set_elem... */
+			if (array->cur_elem != set_elem)
+			{
+				array->cur_elem = set_elem;
+				cur->sk_argument = array->elem_values[set_elem];
+			}
+
+			continue;
+		}
+
+		/*
+		 * ...or skip array, which doesn't advance using a set_elem offset.
+		 *
+		 * Array "contains" elements for every possible datum from a given
+		 * range of values.  This is often the range -inf through to +inf.
+		 * "Binary searching" only determined whether tupdatum is beyond,
+		 * before, or within the range of the skip array.
+		 *
+		 * As always, we set the array element to its closest available match.
+		 * But unlike with a conventional array, a skip array's new element
+		 * might be NEGPOSINF, a special sentinel value.
+		 */
+		if (beyond_end_advance)
+		{
+			/*
+			 * tupdatum/tupnull is > the skip array's "final element"
+			 * (tupdatum/tupnull is < the "first element" for backwards scans)
+			 */
+			_bt_scankey_set_low_or_high(rel, cur, array,
+										ScanDirectionIsBackward(dir));
+		}
+		else if (!all_required_satisfied)
+		{
+			/*
+			 * tupdatum/tupnull is < the skip array's "first element"
+			 * (tupdatum/tupnull is > the "final element" for backwards scans)
+			 */
+			Assert(sktrig < ikey);	/* check on _bt_tuple_before_array_skeys */
+			_bt_scankey_set_low_or_high(rel, cur, array,
+										ScanDirectionIsForward(dir));
+		}
+		else
+		{
+			/*
+			 * tupdatum/tupnull is == "some array element".
+			 *
+			 * Set scan key's sk_argument to tupdatum.  If tupdatum is null,
+			 * we'll set IS NULL flags in scan key's sk_flags instead.
+			 */
+			_bt_scankey_set_element(rel, cur, array, tupdatum, tupnull);
 		}
 	}
 
@@ -2458,6 +3638,8 @@ end_toplevel_scan:
  * 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 cons up 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
@@ -2470,10 +3652,16 @@ end_toplevel_scan:
  * 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 consed up skip array scan keys, it would be possible for "gaps"
+ * to appear that made it unsafe to mark any subsequent input scan keys (taken
+ * from scan->keyData[]) as required to continue the scan.  If there are no
+ * keys for a given attribute, the keys for subsequent attributes can never be
+ * required.  For instance, "WHERE y = 4" always required a full-index scan on
+ * version prior to Postgres 18.  Now preprocessing rewrites such a qual into
+ * "WHERE x = ANY('{every possible x value}') and y = 4", thereby enabling
+ * marking the key on y (and the key on x) required to continue te scan.
  *
  * If possible, redundant keys are eliminated: we keep only the tightest
  * >/>= bound and the tightest </<= bound, and if there's an = key then
@@ -2510,7 +3698,12 @@ end_toplevel_scan:
  * 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.  Note, however, that we are not able to replace a row
+ * comparison with a skip array due to the design of _bt_check_rowcompare.
+ * Row comparisons are treated like a comparison of the first/leftmost column
+ * from the row argument, but actually compare multiple columns internally.
+ * That won't work with skip arrays, which work by making a value into the
+ * current array element, which anchors later scan keys via "=" comparisons.
  *
  * 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
@@ -2574,6 +3767,14 @@ _bt_preprocess_keys(IndexScanDesc scan)
 		/* Also maintain keyDataMap for remapping so->orderProc[] later */
 		keyDataMap = MemoryContextAlloc(so->arrayContext,
 										numberOfKeys * sizeof(int));
+
+		/*
+		 * Also enlarge output array when it might otherwise not have room for
+		 * a skip scan key
+		 */
+		if (numberOfKeys > scan->numberOfKeys)
+			so->keyData = repalloc(so->keyData,
+								   numberOfKeys * sizeof(ScanKeyData));
 	}
 	else
 		inkeys = scan->keyData;
@@ -2713,7 +3914,8 @@ _bt_preprocess_keys(IndexScanDesc scan)
 							return;
 						}
 						/* else discard the redundant non-equality key */
-						Assert(!array || array->num_elems > 0);
+						Assert(!array || array->num_elems > 0 ||
+							   array->num_elems == -1);
 						xform[j].inkey = NULL;
 						xform[j].inkeyi = -1;
 					}
@@ -2761,6 +3963,16 @@ _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 "=".
+			 *
+			 * Our call to _bt_preprocess_array_keys is generally expected to
+			 * have already added "=" scan keys with skip arrays as required
+			 * to form an unbroken series of "=" constraints on all attrs
+			 * prior to the attr from the last scan key that came from our
+			 * original set of scan->keyData[] input scan keys.  Despite all
+			 * this, we cannot assume _bt_preprocess_array_keys will always
+			 * make it safe for us to mark all scan keys required.  Certain
+			 * corner cases might have prevented it from adding a skip array
+			 * (e.g., opclasses without an "=" operator can't use "=" arrays).
 			 */
 			for (j = BTMaxStrategyNumber; --j >= 0;)
 			{
@@ -2849,6 +4061,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)
 				{
@@ -2857,6 +4070,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));
 				}
 
 				/*
@@ -2876,7 +4090,8 @@ _bt_preprocess_keys(IndexScanDesc scan)
 				/* Have all we need to determine redundancy */
 				if (test_result)
 				{
-					Assert(!array || array->num_elems > 0);
+					Assert(!array || array->num_elems > 0 ||
+						   array->num_elems == -1);
 
 					/*
 					 * New key is more restrictive, and so replaces old key...
@@ -3018,10 +4233,11 @@ _bt_verify_keys_with_arraykeys(IndexScanDesc scan)
 		if (array->scan_key != ikey)
 			return false;
 
-		if (array->num_elems <= 0)
+		if (array->num_elems == 0 || array->num_elems < -1)
 			return false;
 
-		if (cur->sk_argument != array->elem_values[array->cur_elem])
+		if (array->num_elems != -1 &&
+			cur->sk_argument != array->elem_values[array->cur_elem])
 			return false;
 		if (last_sk_attno > cur->sk_attno)
 			return false;
@@ -3087,6 +4303,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.
@@ -3096,6 +4315,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));
@@ -3169,6 +4404,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;
 		}
 
@@ -3730,6 +4966,20 @@ _bt_check_compare(IndexScanDesc scan, ScanDirection dir,
 			continue;
 		}
 
+		/*
+		 * A skip array scan key might be negative/positive infinity.  Might
+		 * also be next key/prior key sentinel, which we don't deal with.
+		 */
+		if (key->sk_flags & (SK_BT_NEGPOSINF | SK_BT_NEXT | SK_BT_PRIOR))
+		{
+			Assert(key->sk_flags & SK_SEARCHARRAY);
+			Assert(key->sk_flags & SK_BT_SKIP);
+			Assert(requiredSameDir);
+
+			*continuescan = false;
+			return false;
+		}
+
 		/* row-comparison keys need special processing */
 		if (key->sk_flags & SK_ROW_HEADER)
 		{
diff --git a/src/backend/access/nbtree/nbtvalidate.c b/src/backend/access/nbtree/nbtvalidate.c
index e9d4cd60d..96d0d9185 100644
--- a/src/backend/access/nbtree/nbtvalidate.c
+++ b/src/backend/access/nbtree/nbtvalidate.c
@@ -114,6 +114,10 @@ btvalidate(Oid opclassoid)
 			case BTOPTIONS_PROC:
 				ok = check_amoptsproc_signature(procform->amproc);
 				break;
+			case BTSKIPSUPPORT_PROC:
+				ok = check_amproc_signature(procform->amproc, VOIDOID, true,
+											1, 1, INTERNALOID);
+				break;
 			default:
 				ereport(INFO,
 						(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
diff --git a/src/backend/commands/opclasscmds.c b/src/backend/commands/opclasscmds.c
index b8b5c147c..a86dbf71b 100644
--- a/src/backend/commands/opclasscmds.c
+++ b/src/backend/commands/opclasscmds.c
@@ -1330,6 +1330,31 @@ assignProcTypes(OpFamilyMember *member, Oid amoid, Oid typeoid,
 						(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
 						 errmsg("btree equal image functions must not be cross-type")));
 		}
+		else if (member->number == BTSKIPSUPPORT_PROC)
+		{
+			if (procform->pronargs != 1 ||
+				procform->proargtypes.values[0] != INTERNALOID)
+				ereport(ERROR,
+						(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
+						 errmsg("btree skip support functions must accept type \"internal\"")));
+			if (procform->prorettype != VOIDOID)
+				ereport(ERROR,
+						(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
+						 errmsg("btree skip support functions must return void")));
+
+			/*
+			 * pg_amproc functions are indexed by (lefttype, righttype), but a
+			 * skip support function doesn't make sense in cross-type
+			 * scenarios.  The same opclass opcintype OID is always used for
+			 * lefttype and righttype.  Providing a cross-type routine isn't
+			 * sensible.  Reject cross-type ALTER OPERATOR FAMILY ...  ADD
+			 * FUNCTION 6 statements here.
+			 */
+			if (member->lefttype != member->righttype)
+				ereport(ERROR,
+						(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
+						 errmsg("btree skip support functions must not be cross-type")));
+		}
 	}
 	else if (amoid == HASH_AM_OID)
 	{
diff --git a/src/backend/storage/lmgr/lwlock.c b/src/backend/storage/lmgr/lwlock.c
index db6ed784a..86a5de8f4 100644
--- a/src/backend/storage/lmgr/lwlock.c
+++ b/src/backend/storage/lmgr/lwlock.c
@@ -143,6 +143,7 @@ static const char *const BuiltinTrancheNames[] = {
 	[LWTRANCHE_LOCK_MANAGER] = "LockManager",
 	[LWTRANCHE_PREDICATE_LOCK_MANAGER] = "PredicateLockManager",
 	[LWTRANCHE_PARALLEL_HASH_JOIN] = "ParallelHashJoin",
+	[LWTRANCHE_PARALLEL_BTREE_SCAN] = "ParallelBtreeScan",
 	[LWTRANCHE_PARALLEL_QUERY_DSA] = "ParallelQueryDSA",
 	[LWTRANCHE_PER_SESSION_DSA] = "PerSessionDSA",
 	[LWTRANCHE_PER_SESSION_RECORD_TYPE] = "PerSessionRecordType",
diff --git a/src/backend/utils/activity/wait_event_names.txt b/src/backend/utils/activity/wait_event_names.txt
index 8efb4044d..6efa3e353 100644
--- a/src/backend/utils/activity/wait_event_names.txt
+++ b/src/backend/utils/activity/wait_event_names.txt
@@ -372,6 +372,7 @@ BufferMapping	"Waiting to associate a data block with a buffer in the buffer poo
 LockManager	"Waiting to read or update information about <quote>heavyweight</quote> locks."
 PredicateLockManager	"Waiting to access predicate lock information used by serializable transactions."
 ParallelHashJoin	"Waiting to synchronize workers during Parallel Hash Join plan execution."
+ParallelBtreeScan	"Waiting to synchronize workers during a parallel B-tree scan."
 ParallelQueryDSA	"Waiting for parallel query dynamic shared memory allocation."
 PerSessionDSA	"Waiting for parallel query dynamic shared memory allocation."
 PerSessionRecordType	"Waiting to access a parallel query's information about composite types."
diff --git a/src/backend/utils/adt/Makefile b/src/backend/utils/adt/Makefile
index 85e5eaf32..88c929a0a 100644
--- a/src/backend/utils/adt/Makefile
+++ b/src/backend/utils/adt/Makefile
@@ -98,6 +98,7 @@ OBJS = \
 	rowtypes.o \
 	ruleutils.o \
 	selfuncs.o \
+	skipsupport.o \
 	tid.o \
 	timestamp.o \
 	trigfuncs.o \
diff --git a/src/backend/utils/adt/date.c b/src/backend/utils/adt/date.c
index 8130f3e8a..256350007 100644
--- a/src/backend/utils/adt/date.c
+++ b/src/backend/utils/adt/date.c
@@ -34,6 +34,7 @@
 #include "utils/date.h"
 #include "utils/datetime.h"
 #include "utils/numeric.h"
+#include "utils/skipsupport.h"
 #include "utils/sortsupport.h"
 
 /*
@@ -455,6 +456,51 @@ date_sortsupport(PG_FUNCTION_ARGS)
 	PG_RETURN_VOID();
 }
 
+static Datum
+date_decrement(Relation rel, Datum existing, bool *underflow)
+{
+	DateADT		dexisting = DatumGetDateADT(existing);
+
+	if (dexisting == DATEVAL_NOBEGIN)
+	{
+		/* return value is undefined */
+		*underflow = true;
+		return (Datum) 0;
+	}
+
+	*underflow = false;
+	return DateADTGetDatum(dexisting - 1);
+}
+
+static Datum
+date_increment(Relation rel, Datum existing, bool *overflow)
+{
+	DateADT		dexisting = DatumGetDateADT(existing);
+
+	if (dexisting == DATEVAL_NOEND)
+	{
+		/* return value is undefined */
+		*overflow = true;
+		return (Datum) 0;
+	}
+
+	*overflow = false;
+	return DateADTGetDatum(dexisting + 1);
+}
+
+Datum
+date_skipsupport(PG_FUNCTION_ARGS)
+{
+	SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
+
+	sksup->decrement = date_decrement;
+	sksup->increment = date_increment;
+	sksup->low_elem = DateADTGetDatum(DATEVAL_NOBEGIN);
+	sksup->high_elem = DateADTGetDatum(DATEVAL_NOEND);
+
+	PG_RETURN_VOID();
+}
+
 Datum
 hashdate(PG_FUNCTION_ARGS)
 {
diff --git a/src/backend/utils/adt/meson.build b/src/backend/utils/adt/meson.build
index f73f294b8..cb8470324 100644
--- a/src/backend/utils/adt/meson.build
+++ b/src/backend/utils/adt/meson.build
@@ -85,6 +85,7 @@ backend_sources += files(
   'rowtypes.c',
   'ruleutils.c',
   'selfuncs.c',
+  'skipsupport.c',
   'tid.c',
   'timestamp.c',
   'trigfuncs.c',
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index 08fa6774d..d04bd379d 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -192,6 +192,8 @@ static double convert_timevalue_to_scalar(Datum value, Oid typid,
 										  bool *failure);
 static void examine_simple_variable(PlannerInfo *root, Var *var,
 									VariableStatData *vardata);
+static void examine_indexcol_variable(PlannerInfo *root, IndexOptInfo *index,
+									  int indexcol, VariableStatData *vardata);
 static bool get_variable_range(PlannerInfo *root, VariableStatData *vardata,
 							   Oid sortop, Oid collation,
 							   Datum *min, Datum *max);
@@ -213,6 +215,8 @@ static bool get_actual_variable_endpoint(Relation heapRel,
 										 MemoryContext outercontext,
 										 Datum *endpointDatum);
 static RelOptInfo *find_join_input_rel(PlannerInfo *root, Relids relids);
+static double btcost_correlation(IndexOptInfo *index,
+								 VariableStatData *vardata);
 
 
 /*
@@ -5736,6 +5740,92 @@ examine_simple_variable(PlannerInfo *root, Var *var,
 	}
 }
 
+/*
+ * examine_indexcol_variable
+ *		Try to look up statistical data about an index column/expression.
+ *		Fill in a VariableStatData struct to describe the column.
+ *
+ * Inputs:
+ *	root: the planner info
+ *	index: the index whose column we're interested in
+ *	indexcol: 0-based index column number (subscripts index->indexkeys[])
+ *
+ * Outputs: *vardata is filled as follows:
+ *	var: the input expression (with any binary relabeling stripped, if
+ *		it is or contains a variable; but otherwise the type is preserved)
+ *	rel: RelOptInfo for table relation containing variable.
+ *	statsTuple: the pg_statistic entry for the variable, if one exists;
+ *		otherwise NULL.
+ *	freefunc: pointer to a function to release statsTuple with.
+ *
+ * Caller is responsible for doing ReleaseVariableStats() before exiting.
+ */
+static void
+examine_indexcol_variable(PlannerInfo *root, IndexOptInfo *index,
+						  int indexcol, VariableStatData *vardata)
+{
+	AttrNumber	colnum;
+	Oid			relid;
+
+	if (index->indexkeys[indexcol] != 0)
+	{
+		/* Simple variable --- look to stats for the underlying table */
+		RangeTblEntry *rte = planner_rt_fetch(index->rel->relid, root);
+
+		Assert(rte->rtekind == RTE_RELATION);
+		relid = rte->relid;
+		Assert(relid != InvalidOid);
+		colnum = index->indexkeys[indexcol];
+		vardata->rel = index->rel;
+
+		if (get_relation_stats_hook &&
+			(*get_relation_stats_hook) (root, rte, colnum, vardata))
+		{
+			/*
+			 * The hook took control of acquiring a stats tuple.  If it did
+			 * supply a tuple, it'd better have supplied a freefunc.
+			 */
+			if (HeapTupleIsValid(vardata->statsTuple) &&
+				!vardata->freefunc)
+				elog(ERROR, "no function provided to release variable stats with");
+		}
+		else
+		{
+			vardata->statsTuple = SearchSysCache3(STATRELATTINH,
+												  ObjectIdGetDatum(relid),
+												  Int16GetDatum(colnum),
+												  BoolGetDatum(rte->inh));
+			vardata->freefunc = ReleaseSysCache;
+		}
+	}
+	else
+	{
+		/* Expression --- maybe there are stats for the index itself */
+		relid = index->indexoid;
+		colnum = indexcol + 1;
+
+		if (get_index_stats_hook &&
+			(*get_index_stats_hook) (root, relid, colnum, vardata))
+		{
+			/*
+			 * The hook took control of acquiring a stats tuple.  If it did
+			 * supply a tuple, it'd better have supplied a freefunc.
+			 */
+			if (HeapTupleIsValid(vardata->statsTuple) &&
+				!vardata->freefunc)
+				elog(ERROR, "no function provided to release variable stats with");
+		}
+		else
+		{
+			vardata->statsTuple = SearchSysCache3(STATRELATTINH,
+												  ObjectIdGetDatum(relid),
+												  Int16GetDatum(colnum),
+												  BoolGetDatum(false));
+			vardata->freefunc = ReleaseSysCache;
+		}
+	}
+}
+
 /*
  * Check whether it is permitted to call func_oid passing some of the
  * pg_statistic data in vardata.  We allow this either if the user has SELECT
@@ -6794,6 +6884,54 @@ add_predicate_to_index_quals(IndexOptInfo *index, List *indexQuals)
 	return list_concat(predExtraQuals, indexQuals);
 }
 
+/*
+ * Estimate correlation of btree index's first column.
+ *
+ * If we can get an estimate of the first column's ordering correlation C
+ * from pg_statistic, estimate the index correlation as C for a
+ * single-column index, or C * 0.75 for multiple columns. (The idea here
+ * is that multiple columns dilute the importance of the first column's
+ * ordering, but don't negate it entirely.  Before 8.0 we divided the
+ * correlation by the number of columns, but that seems too strong.)
+ *
+ * We already filled in the stats tuple for *vardata when called.
+ */
+static double
+btcost_correlation(IndexOptInfo *index, VariableStatData *vardata)
+{
+	Oid			sortop;
+	AttStatsSlot sslot;
+	double		indexCorrelation = 0;
+
+	Assert(HeapTupleIsValid(vardata->statsTuple));
+
+	sortop = get_opfamily_member(index->opfamily[0],
+								 index->opcintype[0],
+								 index->opcintype[0],
+								 BTLessStrategyNumber);
+	if (OidIsValid(sortop) &&
+		get_attstatsslot(&sslot, vardata->statsTuple,
+						 STATISTIC_KIND_CORRELATION, sortop,
+						 ATTSTATSSLOT_NUMBERS))
+	{
+		double		varCorrelation;
+
+		Assert(sslot.nnumbers == 1);
+		varCorrelation = sslot.numbers[0];
+
+		if (index->reverse_sort[0])
+			varCorrelation = -varCorrelation;
+
+		if (index->nkeycolumns > 1)
+			indexCorrelation = varCorrelation * 0.75;
+		else
+			indexCorrelation = varCorrelation;
+
+		free_attstatsslot(&sslot);
+	}
+
+	return indexCorrelation;
+}
 
 void
 btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
@@ -6803,17 +6941,22 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
 {
 	IndexOptInfo *index = path->indexinfo;
 	GenericCosts costs = {0};
-	Oid			relid;
-	AttrNumber	colnum;
 	VariableStatData vardata = {0};
 	double		numIndexTuples;
 	Cost		descentCost;
 	List	   *indexBoundQuals;
 	int			indexcol;
 	bool		eqQualHere;
+	bool		upperInequalHere;
+	bool		lowerInequalHere;
+	bool		have_correlation = false;
+	bool		found_skip;
 	bool		found_saop;
+	bool		found_rowcompare;
 	bool		found_is_null_op;
+	double		inequalselectivity = 1.0;
 	double		num_sa_scans;
+	double		correlation = 0;
 	ListCell   *lc;
 
 	/*
@@ -6829,14 +6972,19 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
 	 * For a RowCompareExpr, we consider only the first column, just as
 	 * rowcomparesel() does.
 	 *
-	 * If there's a ScalarArrayOpExpr in the quals, we'll actually perform up
-	 * to N index descents (not just one), but the ScalarArrayOpExpr's
-	 * operator can be considered to act the same as it normally does.
+	 * If there's a ScalarArrayOpExpr in the quals, or if we expect to
+	 * generate a skip scan array, then we'll actually perform up to N index
+	 * descents (not just one), but the underlying operator can be considered
+	 * to act the same as it normally does.
 	 */
 	indexBoundQuals = NIL;
 	indexcol = 0;
 	eqQualHere = false;
+	upperInequalHere = false;
+	lowerInequalHere = false;
+	found_skip = false;
 	found_saop = false;
+	found_rowcompare = false;
 	found_is_null_op = false;
 	num_sa_scans = 1;
 	foreach(lc, path->indexclauses)
@@ -6846,13 +6994,90 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
 
 		if (indexcol != iclause->indexcol)
 		{
+			bool		first = true;
+
 			/* Beginning of a new column's quals */
-			if (!eqQualHere)
-				break;			/* done if no '=' qual for indexcol */
+			if (eqQualHere)
+				indexcol++;		/* don't skip the previous '=' qual's column */
+			else if (found_rowcompare)
+				break;			/* Skip arrays can't absord a RowCompare */
+
+			/*
+			 * Now estimate number of "array elements" using ndistinct.
+			 *
+			 * Internally, nbtree treats skip scans as scans with SAOP style
+			 * arrays that generate elements procedurally.  We effectively
+			 * assume a "col = ANY('{every possible col value}')" qual.
+			 */
+			while (indexcol < iclause->indexcol)
+			{
+				double		ndistinct = DEFAULT_NUM_DISTINCT;
+				bool		isdefault = true;
+
+				/* Attain ndistinct for index column/indexed expression */
+				examine_indexcol_variable(root, index, indexcol, &vardata);
+				if (HeapTupleIsValid(vardata.statsTuple))
+				{
+					ndistinct = get_variable_numdistinct(&vardata, &isdefault);
+
+					if (indexcol == 0)
+					{
+						/*
+						 * Get an estimate of the leading column's correlation
+						 * in passing (avoids rereading variable stats below)
+						 */
+						correlation = btcost_correlation(index, &vardata);
+						have_correlation = true;
+					}
+				}
+
+				ReleaseVariableStats(vardata);
+
+				if (first)
+				{
+					first = false;
+
+					/*
+					 * Apply the selectivities of any inequalities to
+					 * ndistinct (unless ndistinct is only a default estimate)
+					 */
+					if (!isdefault)
+						ndistinct *= inequalselectivity;
+
+					/*
+					 * Skip scan will likely require an initial index descent
+					 * to find out what the real first element is..
+					 */
+					if (!upperInequalHere)
+						ndistinct += 1;
+
+					/*
+					 * ...and another extra descent to confirm no further
+					 * groupings/matches
+					 */
+					if (!lowerInequalHere)
+						ndistinct += 1;
+				}
+
+				/*
+				 * Multiply our running estimate by ndistinct to update it.
+				 * Here 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
+				 * relying on skipping.
+				 */
+				num_sa_scans *= ndistinct;
+
+				/* Done costing skipping for this index column */
+				indexcol++;
+				found_skip = true;
+			}
+
+			/* new index column resets tracking variables */
 			eqQualHere = false;
-			indexcol++;
-			if (indexcol != iclause->indexcol)
-				break;			/* no quals at all for indexcol */
+			upperInequalHere = false;
+			lowerInequalHere = false;
+			inequalselectivity = 1.0;
 		}
 
 		/* Examine each indexqual associated with this index clause */
@@ -6874,6 +7099,7 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
 				RowCompareExpr *rc = (RowCompareExpr *) clause;
 
 				clause_op = linitial_oid(rc->opnos);
+				found_rowcompare = true;
 			}
 			else if (IsA(clause, ScalarArrayOpExpr))
 			{
@@ -6894,7 +7120,7 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
 				if (nt->nulltesttype == IS_NULL)
 				{
 					found_is_null_op = true;
-					/* IS NULL is like = for selectivity purposes */
+					/* IS NULL is like = for selectivity/skipping purposes */
 					eqQualHere = true;
 				}
 			}
@@ -6910,6 +7136,38 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
 				Assert(op_strategy != 0);	/* not a member of opfamily?? */
 				if (op_strategy == BTEqualStrategyNumber)
 					eqQualHere = true;
+				else if (rinfo->norm_selec >= 0)
+				{
+					bool		useinequal = true;
+
+					/*
+					 * Skip scan requires tracking inequality selectivities to
+					 * compute an adjusted whole-column ndistinct
+					 */
+					if (op_strategy < BTEqualStrategyNumber)
+					{
+						if (upperInequalHere)
+							useinequal = false;
+						upperInequalHere = true;
+					}
+					else
+					{
+						if (lowerInequalHere)
+							useinequal = false;
+						lowerInequalHere = true;
+					}
+
+					/*
+					 * Assume inequality selectivities are _not_ independent,
+					 * but only track up to one upper bound inequality and up
+					 * to one lower bound inequality.  This avoids wildly
+					 * wrong estimates given redundant operators.
+					 */
+					if (useinequal)
+						inequalselectivity =
+							Max(inequalselectivity - (1.0 - rinfo->norm_selec),
+								DEFAULT_RANGE_INEQ_SEL);
+				}
 			}
 
 			indexBoundQuals = lappend(indexBoundQuals, rinfo);
@@ -6925,6 +7183,7 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
 	if (index->unique &&
 		indexcol == index->nkeycolumns - 1 &&
 		eqQualHere &&
+		!found_skip &&
 		!found_saop &&
 		!found_is_null_op)
 		numIndexTuples = 1.0;
@@ -7033,104 +7292,19 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
 	costs.indexStartupCost += descentCost;
 	costs.indexTotalCost += costs.num_sa_scans * descentCost;
 
-	/*
-	 * If we can get an estimate of the first column's ordering correlation C
-	 * from pg_statistic, estimate the index correlation as C for a
-	 * single-column index, or C * 0.75 for multiple columns. (The idea here
-	 * is that multiple columns dilute the importance of the first column's
-	 * ordering, but don't negate it entirely.  Before 8.0 we divided the
-	 * correlation by the number of columns, but that seems too strong.)
-	 */
-	if (index->indexkeys[0] != 0)
+	if (!have_correlation)
 	{
-		/* Simple variable --- look to stats for the underlying table */
-		RangeTblEntry *rte = planner_rt_fetch(index->rel->relid, root);
-
-		Assert(rte->rtekind == RTE_RELATION);
-		relid = rte->relid;
-		Assert(relid != InvalidOid);
-		colnum = index->indexkeys[0];
-
-		if (get_relation_stats_hook &&
-			(*get_relation_stats_hook) (root, rte, colnum, &vardata))
-		{
-			/*
-			 * The hook took control of acquiring a stats tuple.  If it did
-			 * supply a tuple, it'd better have supplied a freefunc.
-			 */
-			if (HeapTupleIsValid(vardata.statsTuple) &&
-				!vardata.freefunc)
-				elog(ERROR, "no function provided to release variable stats with");
-		}
-		else
-		{
-			vardata.statsTuple = SearchSysCache3(STATRELATTINH,
-												 ObjectIdGetDatum(relid),
-												 Int16GetDatum(colnum),
-												 BoolGetDatum(rte->inh));
-			vardata.freefunc = ReleaseSysCache;
-		}
+		examine_indexcol_variable(root, index, 0, &vardata);
+		if (HeapTupleIsValid(vardata.statsTuple))
+			costs.indexCorrelation = btcost_correlation(index, &vardata);
+		ReleaseVariableStats(vardata);
 	}
 	else
 	{
-		/* Expression --- maybe there are stats for the index itself */
-		relid = index->indexoid;
-		colnum = 1;
-
-		if (get_index_stats_hook &&
-			(*get_index_stats_hook) (root, relid, colnum, &vardata))
-		{
-			/*
-			 * The hook took control of acquiring a stats tuple.  If it did
-			 * supply a tuple, it'd better have supplied a freefunc.
-			 */
-			if (HeapTupleIsValid(vardata.statsTuple) &&
-				!vardata.freefunc)
-				elog(ERROR, "no function provided to release variable stats with");
-		}
-		else
-		{
-			vardata.statsTuple = SearchSysCache3(STATRELATTINH,
-												 ObjectIdGetDatum(relid),
-												 Int16GetDatum(colnum),
-												 BoolGetDatum(false));
-			vardata.freefunc = ReleaseSysCache;
-		}
+		/* get_variable_index_correlation called earlier */
+		costs.indexCorrelation = correlation;
 	}
 
-	if (HeapTupleIsValid(vardata.statsTuple))
-	{
-		Oid			sortop;
-		AttStatsSlot sslot;
-
-		sortop = get_opfamily_member(index->opfamily[0],
-									 index->opcintype[0],
-									 index->opcintype[0],
-									 BTLessStrategyNumber);
-		if (OidIsValid(sortop) &&
-			get_attstatsslot(&sslot, vardata.statsTuple,
-							 STATISTIC_KIND_CORRELATION, sortop,
-							 ATTSTATSSLOT_NUMBERS))
-		{
-			double		varCorrelation;
-
-			Assert(sslot.nnumbers == 1);
-			varCorrelation = sslot.numbers[0];
-
-			if (index->reverse_sort[0])
-				varCorrelation = -varCorrelation;
-
-			if (index->nkeycolumns > 1)
-				costs.indexCorrelation = varCorrelation * 0.75;
-			else
-				costs.indexCorrelation = varCorrelation;
-
-			free_attstatsslot(&sslot);
-		}
-	}
-
-	ReleaseVariableStats(vardata);
-
 	*indexStartupCost = costs.indexStartupCost;
 	*indexTotalCost = costs.indexTotalCost;
 	*indexSelectivity = costs.indexSelectivity;
diff --git a/src/backend/utils/adt/skipsupport.c b/src/backend/utils/adt/skipsupport.c
new file mode 100644
index 000000000..d91471e26
--- /dev/null
+++ b/src/backend/utils/adt/skipsupport.c
@@ -0,0 +1,60 @@
+/*-------------------------------------------------------------------------
+ *
+ * skipsupport.c
+ *	  Support routines for B-Tree skip scan.
+ *
+ *
+ * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * IDENTIFICATION
+ *	  src/backend/utils/adt/skipsupport.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#include "postgres.h"
+
+#include "access/nbtree.h"
+#include "utils/lsyscache.h"
+#include "utils/skipsupport.h"
+
+/*
+ * Fill in SkipSupport given an operator class (opfamily + opcintype).
+ *
+ * On success, returns true, and initializes all SkipSupport fields for
+ * caller.  Otherwise returns false, indicating that operator class has no
+ * skip support function.
+ */
+bool
+PrepareSkipSupportFromOpclass(Oid opfamily, Oid opcintype, bool reverse,
+							  SkipSupport sksup)
+{
+	Oid			skipSupportFunction;
+
+	/* Look for a skip support function */
+	skipSupportFunction = get_opfamily_proc(opfamily, opcintype, opcintype,
+											BTSKIPSUPPORT_PROC);
+	if (!OidIsValid(skipSupportFunction))
+		return false;
+
+	OidFunctionCall1(skipSupportFunction, PointerGetDatum(sksup));
+
+	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;
+	}
+
+	return true;
+}
diff --git a/src/backend/utils/adt/uuid.c b/src/backend/utils/adt/uuid.c
index 5284d23dc..654bda638 100644
--- a/src/backend/utils/adt/uuid.c
+++ b/src/backend/utils/adt/uuid.c
@@ -13,12 +13,15 @@
 
 #include "postgres.h"
 
+#include <limits.h>
+
 #include "common/hashfn.h"
 #include "lib/hyperloglog.h"
 #include "libpq/pqformat.h"
 #include "port/pg_bswap.h"
 #include "utils/fmgrprotos.h"
 #include "utils/guc.h"
+#include "utils/skipsupport.h"
 #include "utils/sortsupport.h"
 #include "utils/timestamp.h"
 #include "utils/uuid.h"
@@ -384,6 +387,74 @@ uuid_abbrev_convert(Datum original, SortSupport ssup)
 	return res;
 }
 
+static Datum
+uuid_decrement(Relation rel, Datum existing, bool *underflow)
+{
+	pg_uuid_t  *uuid;
+
+	uuid = (pg_uuid_t *) palloc(UUID_LEN);
+	memcpy(uuid, DatumGetUUIDP(existing), UUID_LEN);
+	for (int i = UUID_LEN - 1; i >= 0; i--)
+	{
+		if (uuid->data[i] > 0)
+		{
+			uuid->data[i]--;
+			*underflow = false;
+			return UUIDPGetDatum(uuid);
+		}
+		uuid->data[i] = UCHAR_MAX;
+	}
+
+	pfree(uuid);				/* cannot leak memory */
+
+	/* return value is undefined */
+	*underflow = true;
+	return (Datum) 0;
+}
+
+static Datum
+uuid_increment(Relation rel, Datum existing, bool *overflow)
+{
+	pg_uuid_t  *uuid;
+
+	uuid = (pg_uuid_t *) palloc(UUID_LEN);
+	memcpy(uuid, DatumGetUUIDP(existing), UUID_LEN);
+	for (int i = UUID_LEN - 1; i >= 0; i--)
+	{
+		if (uuid->data[i] < UCHAR_MAX)
+		{
+			uuid->data[i]++;
+			*overflow = false;
+			return UUIDPGetDatum(uuid);
+		}
+		uuid->data[i] = 0;
+	}
+
+	pfree(uuid);				/* cannot leak memory */
+
+	/* return value is undefined */
+	*overflow = true;
+	return (Datum) 0;
+}
+
+Datum
+uuid_skipsupport(PG_FUNCTION_ARGS)
+{
+	SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
+	pg_uuid_t  *uuid_min = palloc(UUID_LEN);
+	pg_uuid_t  *uuid_max = palloc(UUID_LEN);
+
+	memset(uuid_min->data, 0x00, UUID_LEN);
+	memset(uuid_max->data, 0xFF, UUID_LEN);
+
+	sksup->decrement = uuid_decrement;
+	sksup->increment = uuid_increment;
+	sksup->low_elem = UUIDPGetDatum(uuid_min);
+	sksup->high_elem = UUIDPGetDatum(uuid_max);
+
+	PG_RETURN_VOID();
+}
+
 /* hash index support */
 Datum
 uuid_hash(PG_FUNCTION_ARGS)
diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c
index 2c4cc8cd4..90de15c4b 100644
--- a/src/backend/utils/misc/guc_tables.c
+++ b/src/backend/utils/misc/guc_tables.c
@@ -28,6 +28,7 @@
 
 #include "access/commit_ts.h"
 #include "access/gin.h"
+#include "access/nbtree.h"
 #include "access/slru.h"
 #include "access/toast_compression.h"
 #include "access/twophase.h"
@@ -1751,6 +1752,17 @@ struct config_bool ConfigureNamesBool[] =
 	},
 #endif
 
+	/* XXX Remove before commit */
+	{
+		{"skipscan_skipsupport_enabled", PGC_SUSET, DEVELOPER_OPTIONS,
+			NULL, NULL,
+			GUC_NOT_IN_SAMPLE
+		},
+		&skipscan_skipsupport_enabled,
+		true,
+		NULL, NULL, NULL
+	},
+
 	{
 		{"integer_datetimes", PGC_INTERNAL, PRESET_OPTIONS,
 			gettext_noop("Shows whether datetimes are integer based."),
@@ -3590,6 +3602,17 @@ struct config_int ConfigureNamesInt[] =
 		NULL, NULL, NULL
 	},
 
+	/* XXX Remove before commit */
+	{
+		{"skipscan_prefix_cols", PGC_SUSET, DEVELOPER_OPTIONS,
+			NULL, NULL,
+			GUC_NOT_IN_SAMPLE
+		},
+		&skipscan_prefix_cols,
+		INDEX_MAX_KEYS, 0, INDEX_MAX_KEYS,
+		NULL, NULL, NULL
+	},
+
 	{
 		/* Can't be set in postgresql.conf */
 		{"server_version_num", PGC_INTERNAL, PRESET_OPTIONS,
diff --git a/doc/src/sgml/btree.sgml b/doc/src/sgml/btree.sgml
index 2b3997988..d256e091f 100644
--- a/doc/src/sgml/btree.sgml
+++ b/doc/src/sgml/btree.sgml
@@ -583,6 +583,38 @@ options(<replaceable>relopts</replaceable> <type>local_relopts *</type>) returns
     </para>
    </listitem>
   </varlistentry>
+  <varlistentry>
+   <term><function>skipsupport</function></term>
+   <listitem>
+    <para>
+     Optionally, a btree operator family may provide a <firstterm>skip
+      support</firstterm> function, registered under support function
+     number 6.  These functions allow the B-tree code to more efficiently
+     navigate the index structure during an index skip scan.  Operator classes
+     that implement skip support provide the core B-Tree code with a way of
+     enumerating and iterating through every possible value from the domain of
+     indexable values.   The APIs involved in this are defined in
+     <filename>src/include/utils/skipsupport.h</filename>.
+    </para>
+    <para>
+     Operator classes that do not provide a skip support function are still
+     eligible to use skip scan.  The core code can still use a fallback
+     strategy, though it might be somewhat less efficient with discrete types.
+     It usually doesn't make sense (and may not even be feasible) for operator
+     classes on continuous types to provide a skip support function.
+    </para>
+    <para>
+     It is not sensible for an operator family to register a cross-type
+     <function>skipsupport</function> function, and attempting to do so will
+     result in an error.  This is because determining the next indexable value
+     from some earlier value does not just depend on sorting/equality
+     semantics, which are more or less defined at the operator family level.
+     Skip scan works by exhaustively considering every possible value stored
+     in an index, so the domain of the particular data type stored within the
+     index must also be considered.
+    </para>
+   </listitem>
+  </varlistentry>
  </variablelist>
 
 </sect2>
diff --git a/doc/src/sgml/indexam.sgml b/doc/src/sgml/indexam.sgml
index dc7d14b60..3116c6350 100644
--- a/doc/src/sgml/indexam.sgml
+++ b/doc/src/sgml/indexam.sgml
@@ -825,7 +825,8 @@ amrestrpos (IndexScanDesc scan);
   <para>
 <programlisting>
 Size
-amestimateparallelscan (int nkeys,
+amestimateparallelscan (Relation indexRelation,
+                        int nkeys,
                         int norderbys);
 </programlisting>
    Estimate and return the number of bytes of dynamic shared memory which
diff --git a/doc/src/sgml/indices.sgml b/doc/src/sgml/indices.sgml
index 6d731e070..b0cb09eb7 100644
--- a/doc/src/sgml/indices.sgml
+++ b/doc/src/sgml/indices.sgml
@@ -457,23 +457,26 @@ CREATE INDEX test2_mm_idx ON test2 (major, minor);
   <para>
    A multicolumn B-tree index can be used with query conditions that
    involve any subset of the index's columns, but the index is most
-   efficient when there are constraints on the leading (leftmost) columns.
-   The exact rule is that equality constraints on leading columns, plus
-   any inequality constraints on the first column that does not have an
-   equality constraint, will be used to limit the portion of the index
-   that is scanned.  Constraints on columns to the right of these columns
-   are checked in the index, so they save visits to the table proper, but
-   they do not reduce the portion of the index that has to be scanned.
+   efficient when there are equality constraints on the leading (leftmost) columns.
+   B-Tree index scans can use the index skip scan strategy to generate
+   equality constraints on prefix columns that were wholly omitted from the
+   query predicate, as well as prefix columns whose values were constrained by
+   inequality conditions.
    For example, given an index on <literal>(a, b, c)</literal> and a
    query condition <literal>WHERE a = 5 AND b &gt;= 42 AND c &lt; 77</literal>,
    the index would have to be scanned from the first entry with
    <literal>a</literal> = 5 and <literal>b</literal> = 42 up through the last entry with
-   <literal>a</literal> = 5.  Index entries with <literal>c</literal> &gt;= 77 would be
-   skipped, but they'd still have to be scanned through.
+   <literal>a</literal> = 5.  Intervening groups of index entries with
+   <literal>c</literal> &gt;= 77 would not need to be returned by the scan,
+   and can be skipped over entirely by applying the skip scan strategy.
    This index could in principle be used for queries that have constraints
    on <literal>b</literal> and/or <literal>c</literal> with no constraint on <literal>a</literal>
-   &mdash; but the entire index would have to be scanned, so in most cases
-   the planner would prefer a sequential table scan over using the index.
+   &mdash; but that approach is generally only taken when there are so few
+   distinct <literal>a</literal> values that the planner expects the skip scan
+   strategy to allow the scan to skip over most individual index leaf pages.
+   If there are many distinct <literal>a</literal> values, then the entire
+   index will have to be scanned, so in most cases the planner will prefer a
+   sequential table scan over using the index.
   </para>
 
   <para>
@@ -508,11 +511,15 @@ CREATE INDEX test2_mm_idx ON test2 (major, minor);
   </para>
 
   <para>
-   Multicolumn indexes should be used sparingly.  In most situations,
-   an index on a single column is sufficient and saves space and time.
-   Indexes with more than three columns are unlikely to be helpful
-   unless the usage of the table is extremely stylized.  See also
-   <xref linkend="indexes-bitmap-scans"/> and
+   Multicolumn indexes should only be used when testing shows that they'll
+   offer a clear advantage over simply using multiple single column indexes.
+   Indexes with more than three columns can make sense, but only when most
+   queries that make use of later columns also make use of earlier prefix
+   columns.  It's possible for B-Tree index scans to make use of <quote>skip
+    scan</quote> optimizations with queries that omit a low cardinality
+   leading prefix column, but this is usually much less efficient than a scan
+   of an index without the extra prefix column.  See <xref
+    linkend="indexes-bitmap-scans"/> and
    <xref linkend="indexes-index-only-scans"/> for some discussion of the
    merits of different index configurations.
   </para>
@@ -669,9 +676,13 @@ CREATE INDEX test3_desc_index ON test3 (id DESC NULLS LAST);
    multicolumn index on <literal>(x, y)</literal>.  This index would typically be
    more efficient than index combination for queries involving both
    columns, but as discussed in <xref linkend="indexes-multicolumn"/>, it
-   would be almost useless for queries involving only <literal>y</literal>, so it
-   should not be the only index.  A combination of the multicolumn index
-   and a separate index on <literal>y</literal> would serve reasonably well.  For
+   would be less useful for queries involving only <literal>y</literal>.  Just
+   how useful might depend on how effective the B-Tree index skip scan
+   optimization is; if <literal>x</literal> has no more than several hundred
+   distinct values, skip scan will make searches for specific
+   <literal>y</literal> values execute reasonably efficiently.  A combination
+   of a multicolumn index on <literal>(x, y)</literal> and a separate index on
+   <literal>y</literal> might also serve reasonably well.  For
    queries involving only <literal>x</literal>, the multicolumn index could be
    used, though it would be larger and hence slower than an index on
    <literal>x</literal> alone.  The last alternative is to create all three
diff --git a/doc/src/sgml/xindex.sgml b/doc/src/sgml/xindex.sgml
index 3a19dab15..ee26dbecc 100644
--- a/doc/src/sgml/xindex.sgml
+++ b/doc/src/sgml/xindex.sgml
@@ -461,6 +461,13 @@
        </entry>
        <entry>5</entry>
       </row>
+      <row>
+       <entry>
+        Return the addresses of C-callable skip support function(s)
+        (optional)
+       </entry>
+       <entry>6</entry>
+      </row>
      </tbody>
     </tgroup>
    </table>
@@ -1062,7 +1069,8 @@ DEFAULT FOR TYPE int8 USING btree FAMILY integer_ops AS
   FUNCTION 1 btint8cmp(int8, int8) ,
   FUNCTION 2 btint8sortsupport(internal) ,
   FUNCTION 3 in_range(int8, int8, int8, boolean, boolean) ,
-  FUNCTION 4 btequalimage(oid) ;
+  FUNCTION 4 btequalimage(oid) ,
+  FUNCTION 6 btint8skipsupport(internal) ;
 
 CREATE OPERATOR CLASS int4_ops
 DEFAULT FOR TYPE int4 USING btree FAMILY integer_ops AS
@@ -1075,7 +1083,8 @@ DEFAULT FOR TYPE int4 USING btree FAMILY integer_ops AS
   FUNCTION 1 btint4cmp(int4, int4) ,
   FUNCTION 2 btint4sortsupport(internal) ,
   FUNCTION 3 in_range(int4, int4, int4, boolean, boolean) ,
-  FUNCTION 4 btequalimage(oid) ;
+  FUNCTION 4 btequalimage(oid) ,
+  FUNCTION 6 btint4skipsupport(internal) ;
 
 CREATE OPERATOR CLASS int2_ops
 DEFAULT FOR TYPE int2 USING btree FAMILY integer_ops AS
@@ -1088,7 +1097,8 @@ DEFAULT FOR TYPE int2 USING btree FAMILY integer_ops AS
   FUNCTION 1 btint2cmp(int2, int2) ,
   FUNCTION 2 btint2sortsupport(internal) ,
   FUNCTION 3 in_range(int2, int2, int2, boolean, boolean) ,
-  FUNCTION 4 btequalimage(oid) ;
+  FUNCTION 4 btequalimage(oid) ,
+  FUNCTION 6 btint2skipsupport(internal) ;
 
 ALTER OPERATOR FAMILY integer_ops USING btree ADD
   -- cross-type comparisons int8 vs int2
diff --git a/src/test/regress/expected/alter_generic.out b/src/test/regress/expected/alter_generic.out
index ae54cb254..f5aa73ac7 100644
--- a/src/test/regress/expected/alter_generic.out
+++ b/src/test/regress/expected/alter_generic.out
@@ -362,9 +362,9 @@ ERROR:  invalid operator number 0, must be between 1 and 5
 ALTER OPERATOR FAMILY alt_opf4 USING btree ADD OPERATOR 1 < ; -- operator without argument types
 ERROR:  operator argument types must be specified in ALTER OPERATOR FAMILY
 ALTER OPERATOR FAMILY alt_opf4 USING btree ADD FUNCTION 0 btint42cmp(int4, int2); -- invalid options parsing function
-ERROR:  invalid function number 0, must be between 1 and 5
-ALTER OPERATOR FAMILY alt_opf4 USING btree ADD FUNCTION 6 btint42cmp(int4, int2); -- function number should be between 1 and 5
-ERROR:  invalid function number 6, must be between 1 and 5
+ERROR:  invalid function number 0, must be between 1 and 6
+ALTER OPERATOR FAMILY alt_opf4 USING btree ADD FUNCTION 7 btint42cmp(int4, int2); -- function number should be between 1 and 6
+ERROR:  invalid function number 7, must be between 1 and 6
 ALTER OPERATOR FAMILY alt_opf4 USING btree ADD STORAGE invalid_storage; -- Ensure STORAGE is not a part of ALTER OPERATOR FAMILY
 ERROR:  STORAGE cannot be specified in ALTER OPERATOR FAMILY
 DROP OPERATOR FAMILY alt_opf4 USING btree;
@@ -505,6 +505,10 @@ ALTER OPERATOR FAMILY alt_opf18 USING btree ADD
 ALTER OPERATOR FAMILY alt_opf18 USING btree
   ADD FUNCTION 4 (int4, int2) btequalimage(oid);
 ERROR:  btree equal image functions must not be cross-type
+-- Should fail. Not allowed to have cross-type skip support function.
+ALTER OPERATOR FAMILY alt_opf18 USING btree
+  ADD FUNCTION 6 (int4, int2) btint4skipsupport(internal);
+ERROR:  btree skip support functions must not be cross-type
 ALTER OPERATOR FAMILY alt_opf18 USING btree DROP FUNCTION 2 (int4, int4);
 ERROR:  function 2(integer,integer) does not exist in operator family "alt_opf18"
 DROP OPERATOR FAMILY alt_opf18 USING btree;
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index d3358dfc3..fa6f27e6d 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1938,7 +1938,7 @@ ORDER BY unique1;
       42
 (3 rows)
 
--- Non-required array scan key on "tenthous":
+-- Skip array on "thousand", SAOP array on "tenthous":
 explain (costs off)
 SELECT thousand, tenthous FROM tenk1
 WHERE thousand < 2 AND tenthous IN (1001,3000)
@@ -1958,7 +1958,7 @@ ORDER BY thousand;
         1 |     1001
 (2 rows)
 
--- Non-required array scan key on "tenthous", backward scan:
+-- Skip array on "thousand", SAOP array on "tenthous", backward scan:
 explain (costs off)
 SELECT thousand, tenthous FROM tenk1
 WHERE thousand < 2 AND tenthous IN (1001,3000)
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 756c2e249..564c1fe4b 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4370,24 +4370,25 @@ select b.unique1 from
   join int4_tbl i1 on b.thousand = f1
   right join int4_tbl i2 on i2.f1 = b.tenthous
   order by 1;
-                                       QUERY PLAN                                        
------------------------------------------------------------------------------------------
+                                   QUERY PLAN                                   
+--------------------------------------------------------------------------------
  Sort
    Sort Key: b.unique1
    ->  Nested Loop Left Join
          ->  Seq Scan on int4_tbl i2
-         ->  Nested Loop Left Join
-               Join Filter: (b.unique1 = 42)
-               ->  Nested Loop
+         ->  Nested Loop
+               Join Filter: (b.thousand = i1.f1)
+               ->  Nested Loop Left Join
+                     Join Filter: (b.unique1 = 42)
                      ->  Nested Loop
-                           ->  Seq Scan on int4_tbl i1
                            ->  Index Scan using tenk1_thous_tenthous on tenk1 b
-                                 Index Cond: ((thousand = i1.f1) AND (tenthous = i2.f1))
-                     ->  Index Scan using tenk1_unique1 on tenk1 a
-                           Index Cond: (unique1 = b.unique2)
-               ->  Index Only Scan using tenk1_thous_tenthous on tenk1 c
-                     Index Cond: (thousand = a.thousand)
-(15 rows)
+                                 Index Cond: (tenthous = i2.f1)
+                           ->  Index Scan using tenk1_unique1 on tenk1 a
+                                 Index Cond: (unique1 = b.unique2)
+                     ->  Index Only Scan using tenk1_thous_tenthous on tenk1 c
+                           Index Cond: (thousand = a.thousand)
+               ->  Seq Scan on int4_tbl i1
+(16 rows)
 
 select b.unique1 from
   tenk1 a join tenk1 b on a.unique1 = b.unique2
@@ -7492,19 +7493,23 @@ select * from fkest f1
   join fkest f2 on (f1.x = f2.x and f1.x10 = f2.x10b and f1.x100 = f2.x100)
   join fkest f3 on f1.x = f3.x
   where f1.x100 = 2;
-                        QUERY PLAN                         
------------------------------------------------------------
+                            QUERY PLAN                             
+-------------------------------------------------------------------
  Nested Loop
    ->  Hash Join
          Hash Cond: ((f2.x = f1.x) AND (f2.x10b = f1.x10))
-         ->  Seq Scan on fkest f2
-               Filter: (x100 = 2)
+         ->  Bitmap Heap Scan on fkest f2
+               Recheck Cond: (x100 = 2)
+               ->  Bitmap Index Scan on fkest_x_x10_x100_idx
+                     Index Cond: (x100 = 2)
          ->  Hash
-               ->  Seq Scan on fkest f1
-                     Filter: (x100 = 2)
+               ->  Bitmap Heap Scan on fkest f1
+                     Recheck Cond: (x100 = 2)
+                     ->  Bitmap Index Scan on fkest_x_x10_x100_idx
+                           Index Cond: (x100 = 2)
    ->  Index Scan using fkest_x_x10_x100_idx on fkest f3
          Index Cond: (x = f1.x)
-(10 rows)
+(14 rows)
 
 alter table fkest add constraint fk
   foreign key (x, x10b, x100) references fkest (x, x10, x100);
@@ -7513,20 +7518,24 @@ select * from fkest f1
   join fkest f2 on (f1.x = f2.x and f1.x10 = f2.x10b and f1.x100 = f2.x100)
   join fkest f3 on f1.x = f3.x
   where f1.x100 = 2;
-                     QUERY PLAN                      
------------------------------------------------------
+                            QUERY PLAN                             
+-------------------------------------------------------------------
  Hash Join
    Hash Cond: ((f2.x = f1.x) AND (f2.x10b = f1.x10))
    ->  Hash Join
          Hash Cond: (f3.x = f2.x)
          ->  Seq Scan on fkest f3
          ->  Hash
-               ->  Seq Scan on fkest f2
-                     Filter: (x100 = 2)
+               ->  Bitmap Heap Scan on fkest f2
+                     Recheck Cond: (x100 = 2)
+                     ->  Bitmap Index Scan on fkest_x_x10_x100_idx
+                           Index Cond: (x100 = 2)
    ->  Hash
-         ->  Seq Scan on fkest f1
-               Filter: (x100 = 2)
-(11 rows)
+         ->  Bitmap Heap Scan on fkest f1
+               Recheck Cond: (x100 = 2)
+               ->  Bitmap Index Scan on fkest_x_x10_x100_idx
+                     Index Cond: (x100 = 2)
+(15 rows)
 
 rollback;
 --
diff --git a/src/test/regress/expected/psql.out b/src/test/regress/expected/psql.out
index 3819bf5e2..58c2d013a 100644
--- a/src/test/regress/expected/psql.out
+++ b/src/test/regress/expected/psql.out
@@ -5240,9 +5240,10 @@ List of access methods
  btree | uuid_ops        | uuid                 | uuid                  |      1 | uuid_cmp
  btree | uuid_ops        | uuid                 | uuid                  |      2 | uuid_sortsupport
  btree | uuid_ops        | uuid                 | uuid                  |      4 | btequalimage
+ btree | uuid_ops        | uuid                 | uuid                  |      6 | uuid_skipsupport
  hash  | uuid_ops        | uuid                 | uuid                  |      1 | uuid_hash
  hash  | uuid_ops        | uuid                 | uuid                  |      2 | uuid_hash_extended
-(5 rows)
+(6 rows)
 
 -- check \dconfig
 set work_mem = 10240;
diff --git a/src/test/regress/expected/union.out b/src/test/regress/expected/union.out
index c73631a9a..62eb4239a 100644
--- a/src/test/regress/expected/union.out
+++ b/src/test/regress/expected/union.out
@@ -1461,18 +1461,17 @@ select t1.unique1 from tenk1 t1
 inner join tenk2 t2 on t1.tenthous = t2.tenthous and t2.thousand = 0
    union all
 (values(1)) limit 1;
-                       QUERY PLAN                       
---------------------------------------------------------
+                             QUERY PLAN                              
+---------------------------------------------------------------------
  Limit
    ->  Append
          ->  Nested Loop
-               Join Filter: (t1.tenthous = t2.tenthous)
-               ->  Seq Scan on tenk1 t1
-               ->  Materialize
-                     ->  Seq Scan on tenk2 t2
-                           Filter: (thousand = 0)
+               ->  Seq Scan on tenk2 t2
+                     Filter: (thousand = 0)
+               ->  Index Scan using tenk1_thous_tenthous on tenk1 t1
+                     Index Cond: (tenthous = t2.tenthous)
          ->  Result
-(9 rows)
+(8 rows)
 
 -- Ensure there is no problem if cheapest_startup_path is NULL
 explain (costs off)
diff --git a/src/test/regress/sql/alter_generic.sql b/src/test/regress/sql/alter_generic.sql
index de58d268d..5e20dc633 100644
--- a/src/test/regress/sql/alter_generic.sql
+++ b/src/test/regress/sql/alter_generic.sql
@@ -310,7 +310,7 @@ ALTER OPERATOR FAMILY alt_opf4 USING btree ADD OPERATOR 6 < (int4, int2); -- ope
 ALTER OPERATOR FAMILY alt_opf4 USING btree ADD OPERATOR 0 < (int4, int2); -- operator number should be between 1 and 5
 ALTER OPERATOR FAMILY alt_opf4 USING btree ADD OPERATOR 1 < ; -- operator without argument types
 ALTER OPERATOR FAMILY alt_opf4 USING btree ADD FUNCTION 0 btint42cmp(int4, int2); -- invalid options parsing function
-ALTER OPERATOR FAMILY alt_opf4 USING btree ADD FUNCTION 6 btint42cmp(int4, int2); -- function number should be between 1 and 5
+ALTER OPERATOR FAMILY alt_opf4 USING btree ADD FUNCTION 7 btint42cmp(int4, int2); -- function number should be between 1 and 6
 ALTER OPERATOR FAMILY alt_opf4 USING btree ADD STORAGE invalid_storage; -- Ensure STORAGE is not a part of ALTER OPERATOR FAMILY
 DROP OPERATOR FAMILY alt_opf4 USING btree;
 
@@ -444,6 +444,9 @@ ALTER OPERATOR FAMILY alt_opf18 USING btree ADD
 -- Should fail. Not allowed to have cross-type equalimage function.
 ALTER OPERATOR FAMILY alt_opf18 USING btree
   ADD FUNCTION 4 (int4, int2) btequalimage(oid);
+-- Should fail. Not allowed to have cross-type skip support function.
+ALTER OPERATOR FAMILY alt_opf18 USING btree
+  ADD FUNCTION 6 (int4, int2) btint4skipsupport(internal);
 ALTER OPERATOR FAMILY alt_opf18 USING btree DROP FUNCTION 2 (int4, int4);
 DROP OPERATOR FAMILY alt_opf18 USING btree;
 
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index fe162cc7c..dea40e013 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -766,7 +766,7 @@ SELECT unique1 FROM tenk1
 WHERE unique1 IN (1,42,7)
 ORDER BY unique1;
 
--- Non-required array scan key on "tenthous":
+-- Skip array on "thousand", SAOP array on "tenthous":
 explain (costs off)
 SELECT thousand, tenthous FROM tenk1
 WHERE thousand < 2 AND tenthous IN (1001,3000)
@@ -776,7 +776,7 @@ SELECT thousand, tenthous FROM tenk1
 WHERE thousand < 2 AND tenthous IN (1001,3000)
 ORDER BY thousand;
 
--- Non-required array scan key on "tenthous", backward scan:
+-- Skip array on "thousand", SAOP array on "tenthous", backward scan:
 explain (costs off)
 SELECT thousand, tenthous FROM tenk1
 WHERE thousand < 2 AND tenthous IN (1001,3000)
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 57de1acff..c0b621f40 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -218,6 +218,7 @@ BTScanPos
 BTScanPosData
 BTScanPosItem
 BTShared
+BTSkipPreproc
 BTSortArrayContext
 BTSpool
 BTStack
@@ -2662,6 +2663,8 @@ SimpleStringListCell
 SingleBoundSortItem
 Size
 SkipPages
+SkipSupport
+SkipSupportData
 SlabBlock
 SlabContext
 SlabSlot
-- 
2.45.2