Subject: [PATCH v4] Add sortsupport for range types and btree_gist

From: Christoph Heiss <[email-masked]>
Date: Wed, 31 Aug 2022 19:20:43 +0200

Incrementally building up a GiST index can result in a sub-optimal index
structure for range types.
By sorting the data before inserting it into the index will result in a
much better index.

This can provide sizeable improvements in query execution time, I/O read
time and shared block hits/reads.

Signed-off-by: Christoph Heiss <[email-masked]>
---
 src/include/catalog/pg_amproc.dat           |   3 +
 src/include/catalog/pg_proc.dat             |   3 +
 src/backend/utils/adt/rangetypes_gist.c     |  70 +++++++++++++
 contrib/btree_gist/Makefile                 |   3 +-
 contrib/btree_gist/btree_bit.c              |  19 ++++
 contrib/btree_gist/btree_bool.c             |  22 ++++
 contrib/btree_gist/btree_cash.c             |  22 ++++
 contrib/btree_gist/btree_enum.c             |  26 +++++
 contrib/btree_gist/btree_gist--1.7--1.8.sql | 110 ++++++++++++++++++++
 contrib/btree_gist/btree_gist.control       |   2 +-
 contrib/btree_gist/btree_inet.c             |  19 ++++
 contrib/btree_gist/btree_interval.c         |  19 ++++
 contrib/btree_gist/btree_macaddr8.c         |  19 ++++
 contrib/btree_gist/btree_time.c             |  19 ++++
 contrib/btree_gist/meson.build              |   1 +
 15 files changed, 355 insertions(+), 2 deletions(-)
 create mode 100644 contrib/btree_gist/btree_gist--1.7--1.8.sql

diff --git a/src/include/catalog/pg_amproc.dat b/src/include/catalog/pg_amproc.dat
index 4cc129bebd8..9318ad5fd84 100644
--- a/src/include/catalog/pg_amproc.dat
+++ b/src/include/catalog/pg_amproc.dat
@@ -600,6 +600,9 @@
 { amprocfamily => 'gist/range_ops', amproclefttype => 'anyrange',
   amprocrighttype => 'anyrange', amprocnum => '7',
   amproc => 'range_gist_same' },
+{ amprocfamily => 'gist/range_ops', amproclefttype => 'anyrange',
+  amprocrighttype => 'anyrange', amprocnum => '11',
+  amproc => 'range_gist_sortsupport' },
 { amprocfamily => 'gist/network_ops', amproclefttype => 'inet',
   amprocrighttype => 'inet', amprocnum => '1',
   amproc => 'inet_gist_consistent' },
diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat
index 68bb032d3ea..951d864f3bb 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -10313,6 +10313,9 @@
 { oid => '3881', descr => 'GiST support',
   proname => 'range_gist_same', prorettype => 'internal',
   proargtypes => 'anyrange anyrange internal', prosrc => 'range_gist_same' },
+{ oid => '8849', descr => 'GiST support',
+  proname => 'range_gist_sortsupport', prorettype => 'void',
+  proargtypes => 'internal', prosrc => 'range_gist_sortsupport' },
 { oid => '6154', descr => 'GiST support',
   proname => 'multirange_gist_consistent', prorettype => 'bool',
   proargtypes => 'internal anymultirange int2 oid internal',
diff --git a/src/backend/utils/adt/rangetypes_gist.c b/src/backend/utils/adt/rangetypes_gist.c
index 777fdf0e2e9..f77fc213f83 100644
--- a/src/backend/utils/adt/rangetypes_gist.c
+++ b/src/backend/utils/adt/rangetypes_gist.c
@@ -21,6 +21,7 @@
 #include "utils/fmgrprotos.h"
 #include "utils/multirangetypes.h"
 #include "utils/rangetypes.h"
+#include "utils/sortsupport.h"
 
 /*
  * Range class properties used to segregate different classes of ranges in
@@ -177,6 +178,7 @@ static void range_gist_double_sorting_split(TypeCacheEntry *typcache,
 static void range_gist_consider_split(ConsiderSplitContext *context,
 									  RangeBound *right_lower, int min_left_count,
 									  RangeBound *left_upper, int max_left_count);
+static int	range_gist_cmp(Datum a, Datum b, SortSupport ssup);
 static int	get_gist_range_class(RangeType *range);
 static int	single_bound_cmp(const void *a, const void *b, void *arg);
 static int	interval_cmp_lower(const void *a, const void *b, void *arg);
@@ -773,6 +775,20 @@ range_gist_picksplit(PG_FUNCTION_ARGS)
 	PG_RETURN_POINTER(v);
 }
 
+/*
+ * Sort support routine for fast GiST index build by sorting.
+ */
+Datum
+range_gist_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport	ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = range_gist_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}
+
 /* equality comparator for GiST */
 Datum
 range_gist_same(PG_FUNCTION_ARGS)
@@ -1693,6 +1709,60 @@ range_gist_consider_split(ConsiderSplitContext *context,
 	}
 }
 
+/*
+ * GiST sortsupport comparator for ranges.
+ *
+ * Operates solely on the lower bounds of the ranges, comparing them using
+ * range_cmp_bounds().
+ * Empty ranges are sorted before non-empty ones.
+ */
+static int
+range_gist_cmp(Datum a, Datum b, SortSupport ssup)
+{
+	RangeType *range_a = DatumGetRangeTypeP(a);
+	RangeType *range_b = DatumGetRangeTypeP(b);
+	TypeCacheEntry *typcache = ssup->ssup_extra;
+	RangeBound	lower1,
+				lower2;
+	RangeBound	upper1,
+				upper2;
+	bool		empty1,
+				empty2;
+	int			result;
+
+	if (typcache == NULL) {
+		Assert(RangeTypeGetOid(range_a) == RangeTypeGetOid(range_b));
+		typcache = lookup_type_cache(RangeTypeGetOid(range_a), TYPECACHE_RANGE_INFO);
+
+		/*
+		 * Cache the range info between calls to avoid having to call
+		 * lookup_type_cache() for each comparison.
+		 */
+		ssup->ssup_extra = typcache;
+	}
+
+	range_deserialize(typcache, range_a, &lower1, &upper1, &empty1);
+	range_deserialize(typcache, range_b, &lower2, &upper2, &empty2);
+
+	/* For b-tree use, empty ranges sort before all else */
+	if (empty1 && empty2)
+		result = 0;
+	else if (empty1)
+		result = -1;
+	else if (empty2)
+		result = 1;
+	else
+		result = range_cmp_bounds(typcache, &lower1, &lower2);
+
+	if ((Datum) range_a != a)
+		pfree(range_a);
+
+	if ((Datum) range_b != b)
+		pfree(range_b);
+
+	return result;
+}
+
 /*
  * Find class number for range.
  *
diff --git a/contrib/btree_gist/Makefile b/contrib/btree_gist/Makefile
index 48997c75f63..4096de73ea3 100644
--- a/contrib/btree_gist/Makefile
+++ b/contrib/btree_gist/Makefile
@@ -33,7 +33,8 @@ EXTENSION = btree_gist
 DATA = btree_gist--1.0--1.1.sql \
        btree_gist--1.1--1.2.sql btree_gist--1.2.sql btree_gist--1.2--1.3.sql \
        btree_gist--1.3--1.4.sql btree_gist--1.4--1.5.sql \
-       btree_gist--1.5--1.6.sql btree_gist--1.6--1.7.sql
+       btree_gist--1.5--1.6.sql btree_gist--1.6--1.7.sql \
+       btree_gist--1.7--1.8.sql
 PGFILEDESC = "btree_gist - B-tree equivalent GiST operator classes"
 
 REGRESS = init int2 int4 int8 float4 float8 cash oid timestamp timestamptz \
diff --git a/contrib/btree_gist/btree_bit.c b/contrib/btree_gist/btree_bit.c
index 5b246bcde4b..bf32bfd6280 100644
--- a/contrib/btree_gist/btree_bit.c
+++ b/contrib/btree_gist/btree_bit.c
@@ -7,6 +7,7 @@
 #include "btree_utils_var.h"
 #include "utils/builtins.h"
 #include "utils/bytea.h"
+#include "utils/sortsupport.h"
 #include "utils/varbit.h"

@@ -19,10 +20,17 @@ PG_FUNCTION_INFO_V1(gbt_bit_picksplit);
 PG_FUNCTION_INFO_V1(gbt_bit_consistent);
 PG_FUNCTION_INFO_V1(gbt_bit_penalty);
 PG_FUNCTION_INFO_V1(gbt_bit_same);
+PG_FUNCTION_INFO_V1(gbt_bit_sortsupport);

 /* define for comparison */
 
+static int
+bit_fast_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	return DatumGetInt32(DirectFunctionCall2(byteacmp, x, y));
+}
+
 static bool
 gbt_bitgt(const void *a, const void *b, Oid collation, FmgrInfo *flinfo)
 {
@@ -208,3 +216,14 @@ gbt_bit_penalty(PG_FUNCTION_ARGS)
 	PG_RETURN_POINTER(gbt_var_penalty(result, o, n, PG_GET_COLLATION(),
 									  &tinfo, fcinfo->flinfo));
 }
+
+Datum
+gbt_bit_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = bit_fast_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}
diff --git a/contrib/btree_gist/btree_bool.c b/contrib/btree_gist/btree_bool.c
index 8b2af129b52..3a9f230e680 100644
--- a/contrib/btree_gist/btree_bool.c
+++ b/contrib/btree_gist/btree_bool.c
@@ -6,6 +6,7 @@
 #include "btree_gist.h"
 #include "btree_utils_num.h"
 #include "common/int.h"
+#include "utils/sortsupport.h"
 
 typedef struct boolkey
 {
@@ -23,6 +24,16 @@ PG_FUNCTION_INFO_V1(gbt_bool_picksplit);
 PG_FUNCTION_INFO_V1(gbt_bool_consistent);
 PG_FUNCTION_INFO_V1(gbt_bool_penalty);
 PG_FUNCTION_INFO_V1(gbt_bool_same);
+PG_FUNCTION_INFO_V1(gbt_bool_sortsupport);
+
+static int
+bool_fast_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	bool	arg1 = DatumGetBool(x);
+	bool	arg2 = DatumGetBool(y);
+
+	return arg1 - arg2;
+}
 
 static bool
 gbt_boolgt(const void *a, const void *b, FmgrInfo *flinfo)
@@ -167,3 +178,14 @@ gbt_bool_same(PG_FUNCTION_ARGS)
 	*result = gbt_num_same((void *) b1, (void *) b2, &tinfo, fcinfo->flinfo);
 	PG_RETURN_POINTER(result);
 }
+
+Datum
+gbt_bool_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = bool_fast_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}
diff --git a/contrib/btree_gist/btree_cash.c b/contrib/btree_gist/btree_cash.c
index 6ac97e2b12a..389b7251309 100644
--- a/contrib/btree_gist/btree_cash.c
+++ b/contrib/btree_gist/btree_cash.c
@@ -7,6 +7,7 @@
 #include "btree_utils_num.h"
 #include "common/int.h"
 #include "utils/cash.h"
+#include "utils/sortsupport.h"
 
 typedef struct
 {
@@ -25,6 +26,16 @@ PG_FUNCTION_INFO_V1(gbt_cash_consistent);
 PG_FUNCTION_INFO_V1(gbt_cash_distance);
 PG_FUNCTION_INFO_V1(gbt_cash_penalty);
 PG_FUNCTION_INFO_V1(gbt_cash_same);
+PG_FUNCTION_INFO_V1(gbt_cash_sortsupport);
+
+static int
+cash_fast_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	bool	arg1 = DatumGetCash(x);
+	bool	arg2 = DatumGetCash(y);
+
+	return arg1 - arg2;
+}
 
 static bool
 gbt_cashgt(const void *a, const void *b, FmgrInfo *flinfo)
@@ -215,3 +226,14 @@ gbt_cash_same(PG_FUNCTION_ARGS)
 	*result = gbt_num_same((void *) b1, (void *) b2, &tinfo, fcinfo->flinfo);
 	PG_RETURN_POINTER(result);
 }
+
+Datum
+gbt_cash_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = cash_fast_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}
diff --git a/contrib/btree_gist/btree_enum.c b/contrib/btree_gist/btree_enum.c
index d4dc38a38e5..33b9a34235e 100644
--- a/contrib/btree_gist/btree_enum.c
+++ b/contrib/btree_gist/btree_enum.c
@@ -7,6 +7,7 @@
 #include "btree_utils_num.h"
 #include "fmgr.h"
 #include "utils/builtins.h"
+#include "utils/sortsupport.h"
 
 /* enums are really Oids, so we just use the same structure */
 
@@ -26,8 +27,16 @@ PG_FUNCTION_INFO_V1(gbt_enum_picksplit);
 PG_FUNCTION_INFO_V1(gbt_enum_consistent);
 PG_FUNCTION_INFO_V1(gbt_enum_penalty);
 PG_FUNCTION_INFO_V1(gbt_enum_same);
+PG_FUNCTION_INFO_V1(gbt_enum_sortsupport);

+static int
+enum_fast_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	return DatumGetInt32(CallerFInfoFunctionCall2(enum_cmp, ssup->ssup_extra,
+												  InvalidOid, x, y));
+}
+
 static bool
 gbt_enumgt(const void *a, const void *b, FmgrInfo *flinfo)
 {
@@ -183,3 +192,20 @@ gbt_enum_same(PG_FUNCTION_ARGS)
 	*result = gbt_num_same((void *) b1, (void *) b2, &tinfo, fcinfo->flinfo);
 	PG_RETURN_POINTER(result);
 }
+
+Datum
+gbt_enum_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = enum_fast_cmp;
+
+	/*
+	 * Since enum_fast_cmp() also uses enum_cmp() like the rest of the
+	 * comparsion functions, it also needs to pass on flinfo when calling
+	 * it. Thus save it in ->ssup_extra and later retrieve it in enum_fast_cmp().
+	 */
+	ssup->ssup_extra = fcinfo->flinfo;
+
+	PG_RETURN_VOID();
+}
diff --git a/contrib/btree_gist/btree_gist--1.7--1.8.sql b/contrib/btree_gist/btree_gist--1.7--1.8.sql
new file mode 100644
index 00000000000..a5ac9657ccc
--- /dev/null
+++ b/contrib/btree_gist/btree_gist--1.7--1.8.sql
@@ -0,0 +1,110 @@
+/* contrib/btree_gist/btree_gist--1.7--1.8.sql */
+
+-- complain if script is sourced in psql, rather than via CREATE EXTENSION
+\echo Use "ALTER EXTENSION btree_gist UPDATE TO '1.8'" to load this file. \quit
+
+CREATE FUNCTION gbt_bit_sortsupport(internal)
+RETURNS void
+AS 'MODULE_PATHNAME'
+LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_bool_sortsupport(internal)
+RETURNS void
+AS 'MODULE_PATHNAME'
+LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_cash_sortsupport(internal)
+RETURNS void
+AS 'MODULE_PATHNAME'
+LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_enum_sortsupport(internal)
+RETURNS void
+AS 'MODULE_PATHNAME'
+LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_inet_sortsupport(internal)
+RETURNS void
+AS 'MODULE_PATHNAME'
+LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_intv_sortsupport(internal)
+RETURNS void
+AS 'MODULE_PATHNAME'
+LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_macad8_sortsupport(internal)
+RETURNS void
+AS 'MODULE_PATHNAME'
+LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_time_sortsupport(internal)
+RETURNS void
+AS 'MODULE_PATHNAME'
+LANGUAGE C IMMUTABLE STRICT;
+
+ALTER OPERATOR FAMILY gist_bit_ops USING gist ADD
+    FUNCTION    11  (bit, bit) gbt_bit_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_bool_ops USING gist ADD
+    FUNCTION    11  (bool, bool) gbt_bool_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_bytea_ops USING gist ADD
+    FUNCTION    11  (bytea, bytea) bytea_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_cash_ops USING gist ADD
+    FUNCTION    11  (money, money) gbt_cash_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_date_ops USING gist ADD
+    FUNCTION    11  (date, date) date_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_enum_ops USING gist ADD
+    FUNCTION    11  (anyenum, anyenum) gbt_enum_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_float4_ops USING gist ADD
+    FUNCTION    11  (float4, float4) btfloat4sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_float8_ops USING gist ADD
+    FUNCTION    11  (float8, float8) btfloat8sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_inet_ops USING gist ADD
+    FUNCTION    11  (inet, inet) gbt_inet_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_int2_ops USING gist ADD
+    FUNCTION    11  (int2, int2) btint2sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_int4_ops USING gist ADD
+    FUNCTION    11  (int4, int4) btint4sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_int8_ops USING gist ADD
+    FUNCTION    11  (int8, int8) btint8sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_interval_ops USING gist ADD
+    FUNCTION    11  (interval, interval) gbt_intv_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_macaddr_ops USING gist ADD
+    FUNCTION    11  (macaddr, macaddr) macaddr_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_macaddr8_ops USING gist ADD
+    FUNCTION    11  (macaddr8, macaddr8) gbt_macad8_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_numeric_ops USING gist ADD
+    FUNCTION    11  (numeric, numeric) numeric_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_oid_ops USING gist ADD
+    FUNCTION    11  (oid, oid) btoidsortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_text_ops USING gist ADD
+    FUNCTION    11  (text, text) bttextsortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_bpchar_ops USING gist ADD
+    FUNCTION    11  (bpchar, bpchar) bpchar_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_time_ops USING gist ADD
+    FUNCTION    11  (time, time) gbt_time_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_timestamp_ops USING gist ADD
+    FUNCTION    11  (timestamp, timestamp) timestamp_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_uuid_ops USING gist ADD
+    FUNCTION    11  (uuid, uuid) uuid_sortsupport (internal) ;
diff --git a/contrib/btree_gist/btree_gist.control b/contrib/btree_gist/btree_gist.control
index fa9171a80a2..abf66538f32 100644
--- a/contrib/btree_gist/btree_gist.control
+++ b/contrib/btree_gist/btree_gist.control
@@ -1,6 +1,6 @@
 # btree_gist extension
 comment = 'support for indexing common datatypes in GiST'
-default_version = '1.7'
+default_version = '1.8'
 module_pathname = '$libdir/btree_gist'
 relocatable = true
 trusted = true
diff --git a/contrib/btree_gist/btree_inet.c b/contrib/btree_gist/btree_inet.c
index 2fb952dca83..1f519cfd611 100644
--- a/contrib/btree_gist/btree_inet.c
+++ b/contrib/btree_gist/btree_inet.c
@@ -8,6 +8,7 @@
 #include "catalog/pg_type.h"
 #include "utils/builtins.h"
 #include "utils/inet.h"
+#include "utils/sortsupport.h"
 
 typedef struct inetkey
 {
@@ -24,8 +25,15 @@ PG_FUNCTION_INFO_V1(gbt_inet_picksplit);
 PG_FUNCTION_INFO_V1(gbt_inet_consistent);
 PG_FUNCTION_INFO_V1(gbt_inet_penalty);
 PG_FUNCTION_INFO_V1(gbt_inet_same);
+PG_FUNCTION_INFO_V1(gbt_inet_sortsupport);

+static int
+inet_fast_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	return DatumGetInt32(DirectFunctionCall2(network_cmp, x, y));
+}
+
 static bool
 gbt_inetgt(const void *a, const void *b, FmgrInfo *flinfo)
 {
@@ -185,3 +193,14 @@ gbt_inet_same(PG_FUNCTION_ARGS)
 	*result = gbt_num_same((void *) b1, (void *) b2, &tinfo, fcinfo->flinfo);
 	PG_RETURN_POINTER(result);
 }
+
+Datum
+gbt_inet_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = inet_fast_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}
diff --git a/contrib/btree_gist/btree_interval.c b/contrib/btree_gist/btree_interval.c
index c2bf82086df..80179adc993 100644
--- a/contrib/btree_gist/btree_interval.c
+++ b/contrib/btree_gist/btree_interval.c
@@ -6,6 +6,7 @@
 #include "btree_gist.h"
 #include "btree_utils_num.h"
 #include "utils/builtins.h"
+#include "utils/sortsupport.h"
 #include "utils/timestamp.h"
 
 typedef struct
@@ -27,8 +28,15 @@ PG_FUNCTION_INFO_V1(gbt_intv_consistent);
 PG_FUNCTION_INFO_V1(gbt_intv_distance);
 PG_FUNCTION_INFO_V1(gbt_intv_penalty);
 PG_FUNCTION_INFO_V1(gbt_intv_same);
+PG_FUNCTION_INFO_V1(gbt_intv_sortsupport);

+static int
+intv_fast_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	return DatumGetInt32(DirectFunctionCall2(interval_cmp, x, y));
+}
+
 static bool
 gbt_intvgt(const void *a, const void *b, FmgrInfo *flinfo)
 {
@@ -295,3 +303,14 @@ gbt_intv_same(PG_FUNCTION_ARGS)
 	*result = gbt_num_same((void *) b1, (void *) b2, &tinfo, fcinfo->flinfo);
 	PG_RETURN_POINTER(result);
 }
+
+Datum
+gbt_intv_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = intv_fast_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}
diff --git a/contrib/btree_gist/btree_macaddr8.c b/contrib/btree_gist/btree_macaddr8.c
index 796cc4efee3..034e34bf908 100644
--- a/contrib/btree_gist/btree_macaddr8.c
+++ b/contrib/btree_gist/btree_macaddr8.c
@@ -7,6 +7,7 @@
 #include "btree_utils_num.h"
 #include "utils/builtins.h"
 #include "utils/inet.h"
+#include "utils/sortsupport.h"
 
 typedef struct
 {
@@ -25,8 +26,15 @@ PG_FUNCTION_INFO_V1(gbt_macad8_picksplit);
 PG_FUNCTION_INFO_V1(gbt_macad8_consistent);
 PG_FUNCTION_INFO_V1(gbt_macad8_penalty);
 PG_FUNCTION_INFO_V1(gbt_macad8_same);
+PG_FUNCTION_INFO_V1(gbt_macad8_sortsupport);

+static int
+macaddr8_fast_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	return DatumGetInt32(DirectFunctionCall2(macaddr8_cmp, x, y));
+}
+
 static bool
 gbt_macad8gt(const void *a, const void *b, FmgrInfo *flinfo)
 {
@@ -194,3 +202,14 @@ gbt_macad8_same(PG_FUNCTION_ARGS)
 	*result = gbt_num_same((void *) b1, (void *) b2, &tinfo, fcinfo->flinfo);
 	PG_RETURN_POINTER(result);
 }
+
+Datum
+gbt_macad8_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = macaddr8_fast_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}
diff --git a/contrib/btree_gist/btree_time.c b/contrib/btree_gist/btree_time.c
index fd8774a2f08..fb3454987be 100644
--- a/contrib/btree_gist/btree_time.c
+++ b/contrib/btree_gist/btree_time.c
@@ -7,6 +7,7 @@
 #include "btree_utils_num.h"
 #include "utils/builtins.h"
 #include "utils/date.h"
+#include "utils/sortsupport.h"
 #include "utils/timestamp.h"
 
 typedef struct
@@ -28,6 +29,7 @@ PG_FUNCTION_INFO_V1(gbt_time_distance);
 PG_FUNCTION_INFO_V1(gbt_timetz_consistent);
 PG_FUNCTION_INFO_V1(gbt_time_penalty);
 PG_FUNCTION_INFO_V1(gbt_time_same);
+PG_FUNCTION_INFO_V1(gbt_time_sortsupport);

 #ifdef USE_FLOAT8_BYVAL
@@ -37,6 +39,12 @@ PG_FUNCTION_INFO_V1(gbt_time_same);
 #endif

+static int
+time_fast_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	return DatumGetInt32(DirectFunctionCall2(time_cmp, x, y));
+}
+
 static bool
 gbt_timegt(const void *a, const void *b, FmgrInfo *flinfo)
 {
@@ -332,3 +340,14 @@ gbt_time_same(PG_FUNCTION_ARGS)
 	*result = gbt_num_same((void *) b1, (void *) b2, &tinfo, fcinfo->flinfo);
 	PG_RETURN_POINTER(result);
 }
+
+Datum
+gbt_time_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = time_fast_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}
diff --git a/contrib/btree_gist/meson.build b/contrib/btree_gist/meson.build
index c0a8d238540..6cb2cddbb45 100644
--- a/contrib/btree_gist/meson.build
+++ b/contrib/btree_gist/meson.build
@@ -41,6 +41,7 @@ install_data(
   'btree_gist--1.4--1.5.sql',
   'btree_gist--1.5--1.6.sql',
   'btree_gist--1.6--1.7.sql',
+  'btree_gist--1.7--1.8.sql',
   kwargs: contrib_data_args,
 )
 
-- 
2.37.3.542.gdd3f6c4cae

--fn5cgvpuomc627kp--

---

From: Bernd Helmle <[email-masked]>
Date: Tue, 11 Mar 2025 19:28:54 +0100

Hi,

Am Montag, dem 09.12.2024 um 18:10 +0100 schrieb Bernd Helmle:
> > I think we have two options:
> > 1. Just do not commit tests. We ran it manually, saw that paths are
> > taken, we are happy.
> 
> So here's a version with the original, unchanged regression tests and
> injection point removed (i hope i forgot nothing to revert).
> 
> This version also fixes cidr sortsupport (thanks again Andrey for
> spotting this), where i accidently used inet instead of the correct
> cidr datatype to pass down to the sortsupport function.

Please find a new rebased version of this patch. No changes to the
patch itself, but it didn't apply without conflicts anymore.

Thanks,
	Bernd

From 5cd326a29d5f6bb7ffb0c6328870cfd113ed1b42 Mon Sep 17 00:00:00 2001
From: Bernd Helmle <Bernd Helmle [email-masked]>
Date: Tue, 11 Mar 2025 19:15:13 +0100
Subject: [PATCH] Add support for sorted gist index builds to btree_gist

This enables sortsupport in the btree_gist extension for faster
builds of gist indexes. Additionally sortsupport is also added for range types
to the backend so that gist indexes on range types also benefit from the
speed up.

Sorted gist index build strategy is the new default now. Regression tests are
unchanged and are using the sorted build strategy instead.
---
 contrib/btree_gist/Makefile                 |   2 +-
 contrib/btree_gist/btree_bit.c              |  46 +++++
 contrib/btree_gist/btree_bool.c             |  22 +++
 contrib/btree_gist/btree_bytea.c            |  35 ++++
 contrib/btree_gist/btree_cash.c             |  27 +++
 contrib/btree_gist/btree_date.c             |  25 +++
 contrib/btree_gist/btree_enum.c             |  33 ++++
 contrib/btree_gist/btree_float4.c           |  28 +++
 contrib/btree_gist/btree_float8.c           |  27 +++
 contrib/btree_gist/btree_gist--1.8--1.9.sql | 192 ++++++++++++++++++++
 contrib/btree_gist/btree_gist.control       |   2 +-
 contrib/btree_gist/btree_inet.c             |  27 +++
 contrib/btree_gist/btree_int2.c             |  26 +++
 contrib/btree_gist/btree_int4.c             |  33 +++-
 contrib/btree_gist/btree_int8.c             |  26 +++
 contrib/btree_gist/btree_interval.c         |  25 +++
 contrib/btree_gist/btree_macaddr.c          |  29 +++
 contrib/btree_gist/btree_macaddr8.c         |  24 +++
 contrib/btree_gist/btree_numeric.c          |  33 ++++
 contrib/btree_gist/btree_oid.c              |  28 +++
 contrib/btree_gist/btree_text.c             |  34 ++++
 contrib/btree_gist/btree_time.c             |  26 +++
 contrib/btree_gist/btree_ts.c               |  25 +++
 contrib/btree_gist/btree_utils_var.h        |  12 +-
 contrib/btree_gist/btree_uuid.c             |  25 +++
 contrib/btree_gist/meson.build              |   1 +
 doc/src/sgml/btree-gist.sgml                |   7 +
 src/backend/utils/adt/rangetypes_gist.c     |  70 +++++++
 src/include/catalog/pg_amproc.dat           |   3 +
 src/include/catalog/pg_proc.dat             |   3 +
 30 files changed, 888 insertions(+), 8 deletions(-)
 create mode 100644 contrib/btree_gist/btree_gist--1.8--1.9.sql

diff --git a/contrib/btree_gist/Makefile b/contrib/btree_gist/Makefile
index 7ac2df26c10..68190ac5e46 100644
--- a/contrib/btree_gist/Makefile
+++ b/contrib/btree_gist/Makefile
@@ -34,7 +34,7 @@ DATA = btree_gist--1.0--1.1.sql \
        btree_gist--1.1--1.2.sql btree_gist--1.2.sql btree_gist--1.2--1.3.sql \
        btree_gist--1.3--1.4.sql btree_gist--1.4--1.5.sql \
        btree_gist--1.5--1.6.sql btree_gist--1.6--1.7.sql \
-       btree_gist--1.7--1.8.sql
+       btree_gist--1.7--1.8.sql btree_gist--1.8--1.9.sql
 PGFILEDESC = "btree_gist - B-tree equivalent GiST operator classes"
 
index f346b956fa9..35aa5578f83 100644

@@ -18,10 +19,33 @@ PG_FUNCTION_INFO_V1(gbt_bit_picksplit);
 PG_FUNCTION_INFO_V1(gbt_bit_consistent);
 PG_FUNCTION_INFO_V1(gbt_bit_penalty);
 PG_FUNCTION_INFO_V1(gbt_bit_same);
+PG_FUNCTION_INFO_V1(gbt_bit_sortsupport);
+PG_FUNCTION_INFO_V1(gbt_varbit_sortsupport);

+static int
+gbt_bit_ssup_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	GBT_VARKEY *key1 = PG_DETOAST_DATUM(x);
+	GBT_VARKEY *key2 = PG_DETOAST_DATUM(y);
+
+	GBT_VARKEY_R arg1 = gbt_var_key_readable(key1);
+	GBT_VARKEY_R arg2 = gbt_var_key_readable(key2);
+	Datum result;
+
+	/* lower is always equal to upper, so just compare those fields */
+	result = DirectFunctionCall2(byteacmp,
+								 PointerGetDatum(arg1.lower),
+								 PointerGetDatum(arg2.lower));
+
+	GBT_FREE_IF_COPY(key1, x);
+	GBT_FREE_IF_COPY(key2, y);
+
+	return DatumGetInt32(result);
+}
+
 static bool
 gbt_bitgt(const void *a, const void *b, Oid collation, FmgrInfo *flinfo)
 {
@@ -207,3 +231,25 @@ gbt_bit_penalty(PG_FUNCTION_ARGS)
 	PG_RETURN_POINTER(gbt_var_penalty(result, o, n, PG_GET_COLLATION(),
 									  &tinfo, fcinfo->flinfo));
 }
+
+Datum
+gbt_bit_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = gbt_bit_ssup_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}
+
+Datum
+gbt_varbit_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = gbt_bit_ssup_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}
\ No newline at end of file
diff --git a/contrib/btree_gist/btree_bool.c b/contrib/btree_gist/btree_bool.c
index adb724e16ac..e6b08f04e9d 100644
--- a/contrib/btree_gist/btree_bool.c
+++ b/contrib/btree_gist/btree_bool.c
@@ -5,6 +5,7 @@
 
 #include "btree_gist.h"
 
 typedef struct boolkey
 {
@@ -22,6 +23,16 @@ PG_FUNCTION_INFO_V1(gbt_bool_picksplit);
 PG_FUNCTION_INFO_V1(gbt_bool_consistent);
 PG_FUNCTION_INFO_V1(gbt_bool_penalty);
 PG_FUNCTION_INFO_V1(gbt_bool_same);
+PG_FUNCTION_INFO_V1(gbt_bool_sortsupport);
+
+static int
+gbt_bool_ssup_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	boolKEY	*arg1 = (boolKEY *) DatumGetPointer(x);
+	boolKEY *arg2 = (boolKEY *) DatumGetPointer(y);
+
+	return arg1->lower - arg2->lower;
+}
 
 static bool
 gbt_boolgt(const void *a, const void *b, FmgrInfo *flinfo)
@@ -166,3 +177,14 @@ gbt_bool_same(PG_FUNCTION_ARGS)
 	*result = gbt_num_same((void *) b1, (void *) b2, &tinfo, fcinfo->flinfo);
 	PG_RETURN_POINTER(result);
 }
+
+Datum
+gbt_bool_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = gbt_bool_ssup_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}
diff --git a/contrib/btree_gist/btree_bytea.c b/contrib/btree_gist/btree_bytea.c
index 5eacb8c59a0..87b83d162bb 100644
--- a/contrib/btree_gist/btree_bytea.c
+++ b/contrib/btree_gist/btree_bytea.c
@@ -6,6 +6,7 @@
 #include "btree_gist.h"
 #include "btree_utils_var.h"
 #include "utils/fmgrprotos.h"
+#include "utils/sortsupport.h"

 /*
@@ -17,7 +18,41 @@ PG_FUNCTION_INFO_V1(gbt_bytea_picksplit);
 PG_FUNCTION_INFO_V1(gbt_bytea_consistent);
 PG_FUNCTION_INFO_V1(gbt_bytea_penalty);
 PG_FUNCTION_INFO_V1(gbt_bytea_same);
+PG_FUNCTION_INFO_V1(gbt_bytea_sortsupport);
 
+/* sortsupport support */
+
+static int
+gbt_bytea_ssup_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	GBT_VARKEY *key1 = PG_DETOAST_DATUM(x);
+	GBT_VARKEY *key2 = PG_DETOAST_DATUM(y);
+
+	GBT_VARKEY_R xkey = gbt_var_key_readable(key1);
+	GBT_VARKEY_R ykey = gbt_var_key_readable(key2);
+	Datum result;
+
+	/* lower and upper are always the same, so it is enough to compare lower */
+	result = DirectFunctionCall2(byteacmp,
+								 PointerGetDatum(xkey.lower),
+								 PointerGetDatum(ykey.lower));
+
+	GBT_FREE_IF_COPY(key1, x);
+	GBT_FREE_IF_COPY(key2, y);
+
+	return DatumGetInt32(result);
+}
+
+Datum
+gbt_bytea_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = gbt_bytea_ssup_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}

index c18c34c8b83..4d50b0f0d9a 100644
 
 typedef struct
 {
@@ -25,6 +26,21 @@ PG_FUNCTION_INFO_V1(gbt_cash_consistent);
 PG_FUNCTION_INFO_V1(gbt_cash_distance);
 PG_FUNCTION_INFO_V1(gbt_cash_penalty);
 PG_FUNCTION_INFO_V1(gbt_cash_same);
+PG_FUNCTION_INFO_V1(gbt_cash_sortsupport);
+
+extern Datum cash_cmp(PG_FUNCTION_ARGS);
+
+static int
+gbt_cash_ssup_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	cashKEY	*arg1 = (cashKEY *) DatumGetPointer(x);
+	cashKEY	*arg2 = (cashKEY *) DatumGetPointer(y);
+
+	/* Since lower and upper are always equal, it is enough to compare lower */
+	return DatumGetInt32(DirectFunctionCall2(cash_cmp,
+											 CashGetDatum(arg1->lower),
+											 CashGetDatum(arg2->lower)));
+}
 
 static bool
 gbt_cashgt(const void *a, const void *b, FmgrInfo *flinfo)
@@ -215,3 +231,14 @@ gbt_cash_same(PG_FUNCTION_ARGS)
 	*result = gbt_num_same((void *) b1, (void *) b2, &tinfo, fcinfo->flinfo);
 	PG_RETURN_POINTER(result);
 }
+
+Datum
+gbt_cash_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = gbt_cash_ssup_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}
diff --git a/contrib/btree_gist/btree_date.c b/contrib/btree_gist/btree_date.c
index 7a4a9d7a853..ee2d96e6006 100644
--- a/contrib/btree_gist/btree_date.c
+++ b/contrib/btree_gist/btree_date.c
@@ -7,6 +7,7 @@
 #include "btree_utils_num.h"
 #include "utils/fmgrprotos.h"
 #include "utils/date.h"
+#include "utils/sortsupport.h"
 
 typedef struct
 {
@@ -25,6 +26,30 @@ PG_FUNCTION_INFO_V1(gbt_date_consistent);
 PG_FUNCTION_INFO_V1(gbt_date_distance);
 PG_FUNCTION_INFO_V1(gbt_date_penalty);
 PG_FUNCTION_INFO_V1(gbt_date_same);
+PG_FUNCTION_INFO_V1(gbt_date_sortsupport);
+
+/* sortsupport functions */
+
+static int gbt_date_ssup_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	dateKEY *akey = (dateKEY *) DatumGetPointer(x);
+	dateKEY *bkey = (dateKEY *) DatumGetPointer(y);
+
+	return DatumGetInt32(DirectFunctionCall2(date_cmp,
+											 DateADTGetDatum(akey->lower),
+											 DateADTGetDatum(bkey->lower)));
+}
+
+Datum
+gbt_date_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = gbt_date_ssup_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}
 
 static bool
 gbt_dategt(const void *a, const void *b, FmgrInfo *flinfo)
diff --git a/contrib/btree_gist/btree_enum.c b/contrib/btree_gist/btree_enum.c
index 05d02e704a0..9c4a7727102 100644
--- a/contrib/btree_gist/btree_enum.c
+++ b/contrib/btree_gist/btree_enum.c
@@ -7,6 +7,7 @@
 #include "btree_utils_num.h"
 #include "fmgr.h"
 #include "utils/fmgrprotos.h"
+#include "utils/sortsupport.h"

@@ -26,8 +27,23 @@ PG_FUNCTION_INFO_V1(gbt_enum_picksplit);

+static int
+gbt_enum_ssup_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	oidKEY *arg1 = (oidKEY *) DatumGetPointer(x);
+	oidKEY *arg2 = (oidKEY *) DatumGetPointer(y);
+
+	/* Since lower and upper oidKEY are always the same, just compare lower */
+	return DatumGetInt32(CallerFInfoFunctionCall2(enum_cmp,
+												  ssup->ssup_extra,
+												  InvalidOid,
+												  arg1->lower,
+												  arg2->lower));
+}
+
 static bool
 gbt_enumgt(const void *a, const void *b, FmgrInfo *flinfo)
 {
@@ -183,3 +199,20 @@ gbt_enum_same(PG_FUNCTION_ARGS)
 	*result = gbt_num_same((void *) b1, (void *) b2, &tinfo, fcinfo->flinfo);
 	PG_RETURN_POINTER(result);
 }
+
+Datum
+gbt_enum_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = gbt_enum_ssup_cmp;
+
+	/*
+	 * Since enum_fast_cmp() also uses enum_cmp() like the rest of the
+	 * comparison functions, it also needs to pass flinfo when calling
+	 * it. Thus save it in ssup_extra and retrieve it in enum_fast_cmp() later.
+	 */
+	ssup->ssup_extra = fcinfo->flinfo;
+
+	PG_RETURN_VOID();
+}
diff --git a/contrib/btree_gist/btree_float4.c b/contrib/btree_gist/btree_float4.c
index d138aa94bf2..c23f7886e09 100644
--- a/contrib/btree_gist/btree_float4.c
+++ b/contrib/btree_gist/btree_float4.c
@@ -5,6 +5,7 @@
 
 #include "btree_gist.h"
 #include "utils/float.h"
 
 typedef struct float4key
@@ -24,6 +25,33 @@ PG_FUNCTION_INFO_V1(gbt_float4_consistent);
 PG_FUNCTION_INFO_V1(gbt_float4_distance);
 PG_FUNCTION_INFO_V1(gbt_float4_penalty);
 PG_FUNCTION_INFO_V1(gbt_float4_same);
+PG_FUNCTION_INFO_V1(gbt_float4_sortsupport);
+
+extern Datum btfloat4cmp(PG_FUNCTION_ARGS);
+
+/* sortsupport functions */
+static int
+gbt_float4_ssup_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	float4KEY *arg1 = (float4KEY *) DatumGetPointer(x);
+	float4KEY *arg2 = (float4KEY *) DatumGetPointer(y);
+
+	/* Since lower and upper for float4KEYs here are always equal it is okay to compare them only */
+	return DatumGetInt32(DirectFunctionCall2(btfloat4cmp,
+											 Float4GetDatum(arg1->lower),
+											 Float4GetDatum(arg2->lower)));
+}
+
+Datum
+gbt_float4_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = gbt_float4_ssup_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}
 
 static bool
 gbt_float4gt(const void *a, const void *b, FmgrInfo *flinfo)
diff --git a/contrib/btree_gist/btree_float8.c b/contrib/btree_gist/btree_float8.c
index a74cd200529..129837f2a19 100644
--- a/contrib/btree_gist/btree_float8.c
+++ b/contrib/btree_gist/btree_float8.c
@@ -5,6 +5,7 @@
 
 #include "btree_gist.h"
 #include "utils/float.h"
 
 typedef struct float8key
@@ -24,7 +25,33 @@ PG_FUNCTION_INFO_V1(gbt_float8_consistent);
 PG_FUNCTION_INFO_V1(gbt_float8_distance);
 PG_FUNCTION_INFO_V1(gbt_float8_penalty);
 PG_FUNCTION_INFO_V1(gbt_float8_same);
+PG_FUNCTION_INFO_V1(gbt_float8_sortsupport);
 
+extern Datum btfloat8cmp(PG_FUNCTION_ARGS);
+
+/* sortsupport functions */
+static int
+gbt_float8_ssup_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	float8KEY *arg1 = (float8KEY *) DatumGetPointer(x);
+	float8KEY *arg2 = (float8KEY *) DatumGetPointer(y);
+
+	/* upper and lower for input keys are equal here */
+	return DatumGetInt32(DirectFunctionCall2(btfloat8cmp,
+											 Float8GetDatum(arg1->lower),
+											 Float8GetDatum(arg2->lower)));
+}
+
+Datum
+gbt_float8_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = gbt_float8_ssup_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}
 
 static bool
 gbt_float8gt(const void *a, const void *b, FmgrInfo *flinfo)
diff --git a/contrib/btree_gist/btree_gist--1.8--1.9.sql b/contrib/btree_gist/btree_gist--1.8--1.9.sql
new file mode 100644
index 00000000000..401e9965cf6
--- /dev/null
+++ b/contrib/btree_gist/btree_gist--1.8--1.9.sql
@@ -0,0 +1,192 @@
+/* contrib/btree_gist/btree_gist--1.7--1.8.sql */
+
+-- complain if script is sourced in psql, rather than via CREATE EXTENSION
+\echo Use "ALTER EXTENSION btree_gist UPDATE TO '1.9'" to load this file. \quit
+
+CREATE FUNCTION gbt_bit_sortsupport(internal)
+RETURNS void
+AS 'MODULE_PATHNAME'
+LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_varbit_sortsupport(internal)
+RETURNS void
+AS 'MODULE_PATHNAME'
+LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_bool_sortsupport(internal)
+RETURNS void
+AS 'MODULE_PATHNAME'
+LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_cash_sortsupport(internal)
+RETURNS void
+AS 'MODULE_PATHNAME'
+LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_enum_sortsupport(internal)
+RETURNS void
+AS 'MODULE_PATHNAME'
+LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_inet_sortsupport(internal)
+RETURNS void
+AS 'MODULE_PATHNAME'
+LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_intv_sortsupport(internal)
+RETURNS void
+AS 'MODULE_PATHNAME'
+LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_macad8_sortsupport(internal)
+RETURNS void
+AS 'MODULE_PATHNAME'
+LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_time_sortsupport(internal)
+RETURNS void
+AS 'MODULE_PATHNAME'
+LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_int2_sortsupport(internal)
+    RETURNS void
+AS 'MODULE_PATHNAME'
+    LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_int4_sortsupport(internal)
+    RETURNS void
+AS 'MODULE_PATHNAME'
+LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_int8_sortsupport(internal)
+    RETURNS void
+AS 'MODULE_PATHNAME'
+    LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_bytea_sortsupport(internal)
+    RETURNS void
+AS 'MODULE_PATHNAME'
+    LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_date_sortsupport(internal)
+    RETURNS void
+AS 'MODULE_PATHNAME'
+    LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_float4_sortsupport(internal)
+    RETURNS void
+AS 'MODULE_PATHNAME'
+    LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_float8_sortsupport(internal)
+    RETURNS void
+AS 'MODULE_PATHNAME'
+    LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_macaddr_sortsupport(internal)
+    RETURNS void
+AS 'MODULE_PATHNAME'
+    LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_numeric_sortsupport(internal)
+    RETURNS void
+AS 'MODULE_PATHNAME'
+    LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_oid_sortsupport(internal)
+    RETURNS void
+AS 'MODULE_PATHNAME'
+    LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_text_sortsupport(internal)
+    RETURNS void
+AS 'MODULE_PATHNAME'
+    LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_ts_sortsupport(internal)
+    RETURNS void
+AS 'MODULE_PATHNAME'
+    LANGUAGE C IMMUTABLE STRICT;
+
+CREATE FUNCTION gbt_uuid_sortsupport(internal)
+    RETURNS void
+AS 'MODULE_PATHNAME'
+    LANGUAGE C IMMUTABLE STRICT;
+
+ALTER OPERATOR FAMILY gist_vbit_ops USING gist ADD
+    FUNCTION    11  (varbit, varbit) gbt_varbit_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_bit_ops USING gist ADD
+    FUNCTION    11  (bit, bit) gbt_bit_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_bool_ops USING gist ADD
+    FUNCTION    11  (bool, bool) gbt_bool_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_bytea_ops USING gist ADD
+    FUNCTION    11  (bytea, bytea) gbt_bytea_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_cash_ops USING gist ADD
+    FUNCTION    11  (money, money) gbt_cash_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_date_ops USING gist ADD
+    FUNCTION    11  (date, date) gbt_date_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_enum_ops USING gist ADD
+    FUNCTION    11  (anyenum, anyenum) gbt_enum_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_float4_ops USING gist ADD
+    FUNCTION    11  (float4, float4) gbt_float4_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_float8_ops USING gist ADD
+    FUNCTION    11  (float8, float8) gbt_float8_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_inet_ops USING gist ADD
+    FUNCTION    11  (inet, inet) gbt_inet_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_cidr_ops USING gist ADD
+    FUNCTION    11  (cidr, cidr) gbt_inet_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_int2_ops USING gist ADD
+    FUNCTION    11  (int2, int2) gbt_int2_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_int4_ops USING gist ADD
+    FUNCTION    11  (int4, int4) gbt_int4_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_int8_ops USING gist ADD
+    FUNCTION    11  (int8, int8) gbt_int8_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_interval_ops USING gist ADD
+    FUNCTION    11  (interval, interval) gbt_intv_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_macaddr_ops USING gist ADD
+    FUNCTION    11  (macaddr, macaddr) gbt_macaddr_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_macaddr8_ops USING gist ADD
+    FUNCTION    11  (macaddr8, macaddr8) gbt_macad8_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_numeric_ops USING gist ADD
+    FUNCTION    11  (numeric, numeric) gbt_numeric_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_oid_ops USING gist ADD
+    FUNCTION    11  (oid, oid) gbt_oid_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_text_ops USING gist ADD
+    FUNCTION    11  (text, text) gbt_text_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_bpchar_ops USING gist ADD
+    FUNCTION    11  (bpchar, bpchar) bpchar_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_time_ops USING gist ADD
+    FUNCTION    11  (time, time) gbt_time_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_timestamp_ops USING gist ADD
+    FUNCTION    11  (timestamp, timestamp) gbt_ts_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_timestamptz_ops USING gist ADD
+    FUNCTION    11  (timestamptz, timestamptz) gbt_ts_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_timetz_ops USING gist ADD
+    FUNCTION    11  (timetz, timetz) gbt_time_sortsupport (internal) ;
+
+ALTER OPERATOR FAMILY gist_uuid_ops USING gist ADD
+    FUNCTION    11  (uuid, uuid) gbt_uuid_sortsupport (internal) ;
diff --git a/contrib/btree_gist/btree_gist.control b/contrib/btree_gist/btree_gist.control
index abf66538f32..69d9341a0ad 100644
--- a/contrib/btree_gist/btree_gist.control
+++ b/contrib/btree_gist/btree_gist.control
@@ -1,6 +1,6 @@
 # btree_gist extension
 comment = 'support for indexing common datatypes in GiST'
-default_version = '1.8'
+default_version = '1.9'
 module_pathname = '$libdir/btree_gist'
 relocatable = true
 trusted = true
diff --git a/contrib/btree_gist/btree_inet.c b/contrib/btree_gist/btree_inet.c
index 4cffd349091..cf94cd0f300 100644
--- a/contrib/btree_gist/btree_inet.c
+++ b/contrib/btree_gist/btree_inet.c
@@ -7,6 +7,7 @@
 #include "btree_utils_num.h"
 #include "catalog/pg_type.h"
 #include "utils/builtins.h"
+#include "utils/sortsupport.h"
 
 typedef struct inetkey
 {
@@ -23,8 +24,23 @@ PG_FUNCTION_INFO_V1(gbt_inet_picksplit);

+static int
+gbt_inet_ssup_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	inetKEY *arg1 = (inetKEY *) DatumGetPointer(x);
+	inetKEY *arg2 = (inetKEY *) DatumGetPointer(y);
+
+	if (arg1->lower == arg2->lower)
+		return 0;
+	else if (arg1->lower > arg2->lower)
+		return 1;
+	else
+		return -1;
+}
+
 static bool
 gbt_inetgt(const void *a, const void *b, FmgrInfo *flinfo)
 {
@@ -184,3 +200,14 @@ gbt_inet_same(PG_FUNCTION_ARGS)
 	*result = gbt_num_same((void *) b1, (void *) b2, &tinfo, fcinfo->flinfo);
 	PG_RETURN_POINTER(result);
 }
+
+Datum
+gbt_inet_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = gbt_inet_ssup_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}
diff --git a/contrib/btree_gist/btree_int2.c b/contrib/btree_gist/btree_int2.c
index 1751a6c055d..02df5813231 100644
--- a/contrib/btree_gist/btree_int2.c
+++ b/contrib/btree_gist/btree_int2.c
@@ -5,6 +5,7 @@
 
 #include "btree_gist.h"
 
 typedef struct int16key
@@ -24,6 +25,31 @@ PG_FUNCTION_INFO_V1(gbt_int2_consistent);
 PG_FUNCTION_INFO_V1(gbt_int2_distance);
 PG_FUNCTION_INFO_V1(gbt_int2_penalty);
 PG_FUNCTION_INFO_V1(gbt_int2_same);
+PG_FUNCTION_INFO_V1(gbt_int2_sortsupport);
+
+/* sortsupport functions */
+static int
+gbt_int2_ssup_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	int16KEY *arg1 = (int16KEY *) DatumGetPointer(x);
+	int16KEY *arg2 = (int16KEY *) DatumGetPointer(y);
+
+	if (arg1->lower < arg2->lower)
+		return -1;
+	else if (arg1->lower > arg2->lower)
+		return 1;
+	else
+		return 0;
+}
+
+Datum
+gbt_int2_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = gbt_int2_ssup_cmp;
+	PG_RETURN_VOID();
+}
 
 static bool
 gbt_int2gt(const void *a, const void *b, FmgrInfo *flinfo)
diff --git a/contrib/btree_gist/btree_int4.c b/contrib/btree_gist/btree_int4.c
index 90d183be6e8..1cef35aace0 100644
--- a/contrib/btree_gist/btree_int4.c
+++ b/contrib/btree_gist/btree_int4.c
@@ -2,15 +2,15 @@
  * contrib/btree_gist/btree_int4.c
  */
 #include "postgres.h"
-
+#include "common/int.h"
+#include "utils/sortsupport.h"
 #include "btree_gist.h"
 #include "btree_utils_num.h"
-#include "common/int.h"
 
 typedef struct int32key
 {
-	int32		lower;
-	int32		upper;
+  int32		lower;
+  int32		upper;
 } int32KEY;
 
 /*
@@ -24,7 +24,7 @@ PG_FUNCTION_INFO_V1(gbt_int4_consistent);
 PG_FUNCTION_INFO_V1(gbt_int4_distance);
 PG_FUNCTION_INFO_V1(gbt_int4_penalty);
 PG_FUNCTION_INFO_V1(gbt_int4_same);
-
+PG_FUNCTION_INFO_V1(gbt_int4_sortsupport);
 
 static bool
 gbt_int4gt(const void *a, const void *b, FmgrInfo *flinfo)
@@ -90,6 +90,29 @@ static const gbtree_ninfo tinfo =
 	gbt_int4_dist
 };
 
+static int
+gbt_int4_ssup_cmp(Datum a, Datum b, SortSupport ssup)
+{
+	int32KEY   *ia = (int32KEY *) DatumGetPointer(a);
+	int32KEY   *ib = (int32KEY *) DatumGetPointer(b);
+
+	/* int4KEY upper and lower are always the same for input keys here. */
+	if (ia->lower < ib->lower)
+		return -1;
+	else if (ia->lower > ib->lower)
+		return 1;
+	else
+		return 0;
+}
+
+Datum
+gbt_int4_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = gbt_int4_ssup_cmp;
+	PG_RETURN_VOID();
+}
 
 PG_FUNCTION_INFO_V1(int4_dist);
 Datum
diff --git a/contrib/btree_gist/btree_int8.c b/contrib/btree_gist/btree_int8.c
index 661cf8189fc..f61a4da6801 100644
--- a/contrib/btree_gist/btree_int8.c
+++ b/contrib/btree_gist/btree_int8.c
@@ -6,6 +6,7 @@
 #include "btree_gist.h"
 #include "btree_utils_num.h"
 #include "common/int.h"
+#include "utils/sortsupport.h"
 
 typedef struct int64key
 {
@@ -24,7 +25,32 @@ PG_FUNCTION_INFO_V1(gbt_int8_consistent);
 PG_FUNCTION_INFO_V1(gbt_int8_distance);
 PG_FUNCTION_INFO_V1(gbt_int8_penalty);
 PG_FUNCTION_INFO_V1(gbt_int8_same);
+PG_FUNCTION_INFO_V1(gbt_int8_sortsupport);
 
+/* sortsupport functions */
+static int
+gbt_int8_ssup_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	int64KEY *arg1 = (int64KEY *) DatumGetPointer(x);
+	int64KEY *arg2 = (int64KEY *) DatumGetPointer(y);
+
+	if (arg1->lower < arg2->lower)
+		return -1;
+	else if (arg1->lower > arg2->lower)
+		return 1;
+	else
+		return 0;
+
+}
+
+Datum
+gbt_int8_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = gbt_int8_ssup_cmp;
+	PG_RETURN_VOID();
+}
 
 static bool
 gbt_int8gt(const void *a, const void *b, FmgrInfo *flinfo)
diff --git a/contrib/btree_gist/btree_interval.c b/contrib/btree_gist/btree_interval.c
index 8f99a416965..25b4ecce192 100644
--- a/contrib/btree_gist/btree_interval.c
+++ b/contrib/btree_gist/btree_interval.c
@@ -6,6 +6,7 @@
 #include "btree_gist.h"
 #include "btree_utils_num.h"
 #include "utils/fmgrprotos.h"
+#include "utils/sortsupport.h"
 #include "utils/timestamp.h"
 
 typedef struct
@@ -27,8 +28,21 @@ PG_FUNCTION_INFO_V1(gbt_intv_consistent);

+static int
+gbt_intv_ssup_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	intvKEY *arg1 = (intvKEY *) DatumGetPointer(x);
+	intvKEY *arg2 = (intvKEY *) DatumGetPointer(y);
+
+	/* intvKEY lower and upper are always equal here, so compare just lower members is enough */
+	return DatumGetInt32(DirectFunctionCall2(interval_cmp,
+											 IntervalPGetDatum(&arg1->lower),
+											 IntervalPGetDatum(&arg2->lower)));
+}
+
 static bool
 gbt_intvgt(const void *a, const void *b, FmgrInfo *flinfo)
 {
@@ -295,3 +309,14 @@ gbt_intv_same(PG_FUNCTION_ARGS)
 	*result = gbt_num_same((void *) b1, (void *) b2, &tinfo, fcinfo->flinfo);
 	PG_RETURN_POINTER(result);
 }
+
+Datum
+gbt_intv_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = gbt_intv_ssup_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}
diff --git a/contrib/btree_gist/btree_macaddr.c b/contrib/btree_gist/btree_macaddr.c
index 558cfa2172f..7df85e5db3b 100644
--- a/contrib/btree_gist/btree_macaddr.c
+++ b/contrib/btree_gist/btree_macaddr.c
@@ -7,6 +7,7 @@
 #include "btree_utils_num.h"
 #include "utils/fmgrprotos.h"
 #include "utils/inet.h"
+#include "utils/sortsupport.h"
 
 typedef struct
 {
@@ -25,6 +26,34 @@ PG_FUNCTION_INFO_V1(gbt_macad_picksplit);
 PG_FUNCTION_INFO_V1(gbt_macad_consistent);
 PG_FUNCTION_INFO_V1(gbt_macad_penalty);
 PG_FUNCTION_INFO_V1(gbt_macad_same);
+PG_FUNCTION_INFO_V1(gbt_macaddr_sortsupport);
+
+/* sortsupport functions */
+static int
+gbt_macaddr_ssup_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	macKEY *arg1 = (macKEY *) DatumGetPointer(x);
+	macKEY *arg2 = (macKEY *) DatumGetPointer(y);
+
+	/* macKEY lower and upper members are always equal here,
+	 * so its enough to compare just lower.
+	 */
+	return DatumGetInt32(DirectFunctionCall2(macaddr_cmp,
+											 MacaddrPGetDatum(&arg1->lower),
+											 MacaddrPGetDatum(&arg2->lower)));
+
+}
+
+Datum
+gbt_macaddr_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = gbt_macaddr_ssup_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}

 static bool
index 5d0c5509f51..e659168b1e2 100644
 
 typedef struct
 {
@@ -25,8 +26,20 @@ PG_FUNCTION_INFO_V1(gbt_macad8_picksplit);

+static int
+gbt_macaddr8_ssup_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	mac8KEY *arg1 = (mac8KEY *) DatumGetPointer(x);
+	mac8KEY *arg2 = (mac8KEY *) DatumGetPointer(y);
+
+	return DatumGetInt32(DirectFunctionCall2(macaddr8_cmp,
+											 Macaddr8PGetDatum(&arg1->lower),
+											 Macaddr8PGetDatum(&arg2->lower)));
+}
+
 static bool
 gbt_macad8gt(const void *a, const void *b, FmgrInfo *flinfo)
 {
@@ -194,3 +207,14 @@ gbt_macad8_same(PG_FUNCTION_ARGS)
 	*result = gbt_num_same((void *) b1, (void *) b2, &tinfo, fcinfo->flinfo);
 	PG_RETURN_POINTER(result);
 }
+
+Datum
+gbt_macad8_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = gbt_macaddr8_ssup_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}
diff --git a/contrib/btree_gist/btree_numeric.c b/contrib/btree_gist/btree_numeric.c
index d533648a295..fe6a5a48dd5 100644
--- a/contrib/btree_gist/btree_numeric.c
+++ b/contrib/btree_gist/btree_numeric.c
@@ -11,6 +11,7 @@
 #include "utils/builtins.h"
 #include "utils/numeric.h"
 #include "utils/rel.h"
+#include "utils/sortsupport.h"
 
 /*
 ** Bytea ops
@@ -21,7 +22,39 @@ PG_FUNCTION_INFO_V1(gbt_numeric_picksplit);
 PG_FUNCTION_INFO_V1(gbt_numeric_consistent);
 PG_FUNCTION_INFO_V1(gbt_numeric_penalty);
 PG_FUNCTION_INFO_V1(gbt_numeric_same);
+PG_FUNCTION_INFO_V1(gbt_numeric_sortsupport);
 
+/* Sortsupport functions */
+static int
+gbt_numeric_ssup_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	GBT_VARKEY *key1 = PG_DETOAST_DATUM(x);
+	GBT_VARKEY *key2 = PG_DETOAST_DATUM(y);
+
+	GBT_VARKEY_R arg1 = gbt_var_key_readable(key1);
+	GBT_VARKEY_R arg2 = gbt_var_key_readable(key2);
+	Datum result;
+
+	result = DirectFunctionCall2(numeric_cmp,
+								 PointerGetDatum(arg1.lower),
+								 PointerGetDatum(arg2.lower));
+
+	GBT_FREE_IF_COPY(key1, x);
+	GBT_FREE_IF_COPY(key2, y);
+
+	return DatumGetInt32(result);
+}
+
+Datum
+gbt_numeric_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = gbt_numeric_ssup_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}

diff --git a/contrib/btree_gist/btree_oid.c b/contrib/btree_gist/btree_oid.c
index d1976f4f091..e3bd78658d0 100644
--- a/contrib/btree_gist/btree_oid.c
+++ b/contrib/btree_gist/btree_oid.c
@@ -5,6 +5,7 @@
 
 #include "btree_gist.h"
 
 typedef struct
 {
@@ -23,7 +24,34 @@ PG_FUNCTION_INFO_V1(gbt_oid_consistent);
 PG_FUNCTION_INFO_V1(gbt_oid_distance);
 PG_FUNCTION_INFO_V1(gbt_oid_penalty);
 PG_FUNCTION_INFO_V1(gbt_oid_same);
+PG_FUNCTION_INFO_V1(gbt_oid_sortsupport);
 
+/* Sortsupport functions */
+static int
+gbt_oid_ssup_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	oidKEY *arg1 = (oidKEY *) DatumGetPointer(x);
+	oidKEY *arg2 = (oidKEY *) DatumGetPointer(y);
+
+	/* upper and lower fields are equal for each oidKEY, so just compare lower */
+	if (arg1->lower > arg2->lower)
+		return 1;
+	else if (arg1->lower < arg2->lower)
+		return -1;
+	else
+		return 0;
+}
+
+Datum
+gbt_oid_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = gbt_oid_ssup_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}
 
 static bool
 gbt_oidgt(const void *a, const void *b, FmgrInfo *flinfo)
diff --git a/contrib/btree_gist/btree_text.c b/contrib/btree_gist/btree_text.c
index 8f80f54240f..4c6dfa9a4e7 100644
--- a/contrib/btree_gist/btree_text.c
+++ b/contrib/btree_gist/btree_text.c
@@ -7,6 +7,7 @@
 #include "btree_utils_var.h"
 #include "mb/pg_wchar.h"
 #include "utils/fmgrprotos.h"
+#include "utils/sortsupport.h"
 
 /*
 ** Text ops
@@ -19,7 +20,40 @@ PG_FUNCTION_INFO_V1(gbt_text_consistent);
 PG_FUNCTION_INFO_V1(gbt_bpchar_consistent);
 PG_FUNCTION_INFO_V1(gbt_text_penalty);
 PG_FUNCTION_INFO_V1(gbt_text_same);
+PG_FUNCTION_INFO_V1(gbt_text_sortsupport);
 
+/* Sortsupport functions */
+static int
+gbt_text_ssup_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	GBT_VARKEY *key1 = PG_DETOAST_DATUM(x);
+	GBT_VARKEY *key2 = PG_DETOAST_DATUM(y);
+
+	GBT_VARKEY_R arg1 = gbt_var_key_readable(key1);
+	GBT_VARKEY_R arg2 = gbt_var_key_readable(key2);
+	Datum result;
+
+	result = DirectFunctionCall2Coll(bttextcmp,
+									 ssup->ssup_collation,
+									 PointerGetDatum(arg1.lower),
+									 PointerGetDatum(arg2.lower));
+
+	GBT_FREE_IF_COPY(key1, x);
+	GBT_FREE_IF_COPY(key2, y);
+
+	return DatumGetInt32(result);
+}
+
+Datum
+gbt_text_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = gbt_text_ssup_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}

index 2f7859340f6..28d4447ff59 100644
 
 typedef struct
@@ -28,6 +29,8 @@ PG_FUNCTION_INFO_V1(gbt_time_distance);
 PG_FUNCTION_INFO_V1(gbt_timetz_consistent);
 PG_FUNCTION_INFO_V1(gbt_time_penalty);
 PG_FUNCTION_INFO_V1(gbt_time_same);
+PG_FUNCTION_INFO_V1(gbt_time_sortsupport);
+PG_FUNCTION_INFO_V1(gbt_timetz_sortsupport);

 #ifdef USE_FLOAT8_BYVAL
@@ -37,6 +40,18 @@ PG_FUNCTION_INFO_V1(gbt_time_same);
 #endif

+static int
+gbt_timekey_ssup_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	timeKEY *arg1 = (timeKEY *) DatumGetPointer(x);
+	timeKEY *arg2 = (timeKEY *) DatumGetPointer(y);
+
+	/* lower and upper are equal during sortsupport comparison */
+	return DatumGetInt32(DirectFunctionCall2(time_cmp,
+											 TimeADTGetDatumFast(arg1->lower),
+											 TimeADTGetDatumFast(arg2->lower)));
+}
+
 static bool
 gbt_timegt(const void *a, const void *b, FmgrInfo *flinfo)
 {
@@ -332,3 +347,14 @@ gbt_time_same(PG_FUNCTION_ARGS)
 	*result = gbt_num_same((void *) b1, (void *) b2, &tinfo, fcinfo->flinfo);
 	PG_RETURN_POINTER(result);
 }
+
+Datum
+gbt_time_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = gbt_timekey_ssup_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}
diff --git a/contrib/btree_gist/btree_ts.c b/contrib/btree_gist/btree_ts.c
index 9e0d979dda9..5ec739b4813 100644
--- a/contrib/btree_gist/btree_ts.c
+++ b/contrib/btree_gist/btree_ts.c
@@ -10,6 +10,7 @@
 #include "utils/fmgrprotos.h"
 #include "utils/timestamp.h"
 #include "utils/float.h"
+#include "utils/sortsupport.h"
 
 typedef struct
 {
@@ -31,6 +32,7 @@ PG_FUNCTION_INFO_V1(gbt_tstz_consistent);
 PG_FUNCTION_INFO_V1(gbt_tstz_distance);
 PG_FUNCTION_INFO_V1(gbt_ts_penalty);
 PG_FUNCTION_INFO_V1(gbt_ts_same);
+PG_FUNCTION_INFO_V1(gbt_ts_sortsupport);

 #ifdef USE_FLOAT8_BYVAL
@@ -39,6 +41,29 @@ PG_FUNCTION_INFO_V1(gbt_ts_same);
 #define TimestampGetDatumFast(X) PointerGetDatum(&(X))
 #endif
 
+/* Sortsupport functions */
+static int
+gbt_ts_ssup_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	tsKEY *arg1 = (tsKEY *) DatumGetPointer(x);
+	tsKEY *arg2 = (tsKEY *) DatumGetPointer(y);
+
+	/* Sortsupport always gets the same lower and upper value for input keys */
+	return DatumGetInt32(DirectFunctionCall2(timestamp_cmp,
+											 TimestampGetDatumFast(arg1->lower),
+											 TimestampGetDatumFast(arg2->lower)));
+}
+
+Datum
+gbt_ts_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = gbt_ts_ssup_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}
 
 static bool
 gbt_tsgt(const void *a, const void *b, FmgrInfo *flinfo)
diff --git a/contrib/btree_gist/btree_utils_var.h b/contrib/btree_gist/btree_utils_var.h
index 9302d41ced6..f79b553a1e1 100644
--- a/contrib/btree_gist/btree_utils_var.h
+++ b/contrib/btree_gist/btree_utils_var.h
@@ -41,7 +41,17 @@ typedef struct
 	GBT_VARKEY *(*f_l2n) (GBT_VARKEY *, FmgrInfo *flinfo);	/* convert leaf to node */
 } gbtree_vinfo;
 
-
+/*
+ * Free ptr1 in case its a copy of ptr2.
+ *
+ * This is adapted from varlena's PG_FREE_IF_COPY, though
+ * doesn't require fcinfo access.
+ */
+#define GBT_FREE_IF_COPY(ptr1, ptr2) \
+	do { \
+		if ((Pointer) (ptr1) != DatumGetPointer(ptr2)) \
+			pfree(ptr1); \
+	} while (0)
 
 extern GBT_VARKEY_R gbt_var_key_readable(const GBT_VARKEY *k);
 
diff --git a/contrib/btree_gist/btree_uuid.c b/contrib/btree_gist/btree_uuid.c
index f4c5c6e5892..85e57d52151 100644
--- a/contrib/btree_gist/btree_uuid.c
+++ b/contrib/btree_gist/btree_uuid.c
@@ -6,6 +6,7 @@
 #include "btree_gist.h"
 #include "btree_utils_num.h"
 #include "port/pg_bswap.h"
+#include "utils/sortsupport.h"
 #include "utils/uuid.h"
 
 typedef struct
@@ -25,7 +26,31 @@ PG_FUNCTION_INFO_V1(gbt_uuid_picksplit);
 PG_FUNCTION_INFO_V1(gbt_uuid_consistent);
 PG_FUNCTION_INFO_V1(gbt_uuid_penalty);
 PG_FUNCTION_INFO_V1(gbt_uuid_same);
+PG_FUNCTION_INFO_V1(gbt_uuid_sortsupport);
 
+static int uuid_internal_cmp(const pg_uuid_t *arg1, const pg_uuid_t *arg2);
+
+/* Sortsupport functions */
+static int
+gbt_uuid_ssup_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	uuidKEY *arg1 = (uuidKEY *) DatumGetPointer(x);
+	uuidKEY *arg2 = (uuidKEY *) DatumGetPointer(y);
+
+	/* Sortsupport gets equal upper and lower values for each key to compare */
+	return uuid_internal_cmp(&arg1->lower, &arg2->lower);
+}
+
+Datum
+gbt_uuid_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = gbt_uuid_ssup_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}
 
 static int
 uuid_internal_cmp(const pg_uuid_t *arg1, const pg_uuid_t *arg2)
diff --git a/contrib/btree_gist/meson.build b/contrib/btree_gist/meson.build
index f4fa9574f1f..89932dd3844 100644
--- a/contrib/btree_gist/meson.build
+++ b/contrib/btree_gist/meson.build
@@ -51,6 +51,7 @@ install_data(
   'btree_gist--1.5--1.6.sql',
   'btree_gist--1.6--1.7.sql',
   'btree_gist--1.7--1.8.sql',
+  'btree_gist--1.8--1.9.sql',
   kwargs: contrib_data_args,
 )
 
diff --git a/doc/src/sgml/btree-gist.sgml b/doc/src/sgml/btree-gist.sgml
index 31e7c78aaef..a4c1b99be1f 100644
--- a/doc/src/sgml/btree-gist.sgml
+++ b/doc/src/sgml/btree-gist.sgml
@@ -52,6 +52,13 @@
   <type>oid</type>, and <type>money</type>.
  </para>
 
+ <para>
+  By default <filename>btree_gist</filename> builds <acronym>GiST</acronym> index with
+  <function>sortsupport</function> in <firstterm>sorted</firstterm> mode. This usually results in
+  much faster index built speed. It is still possible to revert to buffered built strategy
+  by using the <literal>buffering</literal> parameter when creating the index.
+ </para>
+
  <para>
   This module is considered <quote>trusted</quote>, that is, it can be
   installed by non-superusers who have <literal>CREATE</literal> privilege
diff --git a/src/backend/utils/adt/rangetypes_gist.c b/src/backend/utils/adt/rangetypes_gist.c
index a60ee985e74..fa7543be9de 100644
--- a/src/backend/utils/adt/rangetypes_gist.c
+++ b/src/backend/utils/adt/rangetypes_gist.c
@@ -21,6 +21,7 @@
 #include "utils/fmgrprotos.h"
 #include "utils/multirangetypes.h"
 #include "utils/rangetypes.h"
+#include "utils/sortsupport.h"
 
 /*
 
+/*
 
+/*
+ * similar to range_cmp, but range typcache is cached.
+	if (typcache == NULL)
+	{
+	{
+		if (result == 0)
+			result = range_cmp_bounds(typcache, &upper1, &upper2);
index 19100482ba4..4b812b680d4 100644
@@ -606,6 +606,9 @@
 { amprocfamily => 'gist/range_ops', amproclefttype => 'any',
   amprocrighttype => 'any', amprocnum => '12',
   amproc => 'gist_stratnum_common' },
index 42e427f8fe8..9e423d9d970 100644
@@ -10854,6 +10854,9 @@
2.48.1