Add GiST and btree sortsupport routines for range types

For GiST, having a sortsupport function allows building the index
using the "sorted build" method, which is much faster.

For b-tree, the sortsupport routine doesn't give any new
functionality, but speeds up sorting a tiny bit. The difference is not
very significant, about 2% in cursory testing on my laptop, because
the range type comparison function has quite a lot of overhead from
detoasting. In any case, since we have the function for GiST anyway,
we might as well register it for the btree opfamily too.

Author: Bernd Helmle <mailings@oopsware.de>
Discussion: https://www.postgresql.org/message-id/64d324ce2a6d535d3f0f3baeeea7b25beff82ce4.camel@oopsware.de

1 files changed, 64 insertions, 0 deletions

diff --git a/src/backend/utils/adt/rangetypes.c b/src/backend/utils/adt/rangetypes.c
index 5f9fb23871a..66cc0acf4a7 100644
--- a/src/backend/utils/adt/rangetypes.c
+++ b/src/backend/utils/adt/rangetypes.c
@@ -43,6 +43,7 @@
 #include "utils/date.h"
 #include "utils/lsyscache.h"
 #include "utils/rangetypes.h"
+#include "utils/sortsupport.h"
 #include "utils/timestamp.h"
 
 
@@ -57,6 +58,7 @@ typedef struct RangeIOData
 
 static RangeIOData *get_range_io_data(FunctionCallInfo fcinfo, Oid rngtypid,
 									  IOFuncSelector func);
+static int	range_fast_cmp(Datum a, Datum b, SortSupport ssup);
 static char range_parse_flags(const char *flags_str);
 static bool range_parse(const char *string, char *flags, char **lbound_str,
 						char **ubound_str, Node *escontext);
@@ -1290,6 +1292,68 @@ range_cmp(PG_FUNCTION_ARGS)
 	PG_RETURN_INT32(cmp);
 }
 
+/* Sort support strategy routine */
+Datum
+range_sortsupport(PG_FUNCTION_ARGS)
+{
+	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+	ssup->comparator = range_fast_cmp;
+	ssup->ssup_extra = NULL;
+
+	PG_RETURN_VOID();
+}
+
+/* like range_cmp, but uses the new sortsupport interface */
+static int
+range_fast_cmp(Datum a, Datum b, SortSupport ssup)
+{
+	RangeType  *range_a = DatumGetRangeTypeP(a);
+	RangeType  *range_b = DatumGetRangeTypeP(b);
+	TypeCacheEntry *typcache;
+	RangeBound	lower1,
+				lower2;
+	RangeBound	upper1,
+				upper2;
+	bool		empty1,
+				empty2;
+	int			cmp;
+
+	/* cache the range info between calls */
+	if (ssup->ssup_extra == NULL)
+	{
+		Assert(RangeTypeGetOid(range_a) == RangeTypeGetOid(range_b));
+		ssup->ssup_extra =
+			lookup_type_cache(RangeTypeGetOid(range_a), TYPECACHE_RANGE_INFO);
+	}
+	typcache = ssup->ssup_extra;
+
+	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)
+		cmp = 0;
+	else if (empty1)
+		cmp = -1;
+	else if (empty2)
+		cmp = 1;
+	else
+	{
+		cmp = range_cmp_bounds(typcache, &lower1, &lower2);
+		if (cmp == 0)
+			cmp = range_cmp_bounds(typcache, &upper1, &upper2);
+	}
+
+	if ((Datum) range_a != a)
+		pfree(range_a);
+	if ((Datum) range_b != b)
+		pfree(range_b);
+
+	return cmp;
+}
+
+
 /* inequality operators using the range_cmp function */
 Datum
 range_lt(PG_FUNCTION_ARGS)