Hi all!
The motivation behind this is that incrementally building up a GiST
index for certain input data can create a terrible tree structure.
Furthermore, exclusion constraints are commonly implemented using GiST
indices and for that use case, data is mostly orderable.
By sorting the data before inserting it into the index results in a much
better index structure, leading to significant performance improvements.
Testing was done using following setup, with about 50 million rows:
CREATE EXTENSION btree_gist;
CREATE TABLE t (id uuid, block_range int4range);
CREATE INDEX ON before USING GIST (id, block_range);
COPY t FROM '..' DELIMITER ',' CSV HEADER;
using
SELECT * FROM t WHERE id = '..' AND block_range && '..'
as test query, using a unpatched instance and one with the patch applied.
Some stats for fetching 10,000 random rows using the query above,
100 iterations to get good averages.
The benchmarking was done on a unpatched instance compiled using the
exact same options as with the patch applied.
[ Results are noted in a unpatched -> patched fashion. ]
First set of results are after the initial CREATE TABLE, CREATE INDEX
and a COPY to the table, thereby incrementally building the index.
Shared Hit Blocks (average): 110.97 -> 78.58
Shared Read Blocks (average): 58.90 -> 47.42
Execution Time (average): 1.10 -> 0.83 ms
I/O Read Time (average): 0.19 -> 0.15 ms
After a REINDEX on the table, the results improve even more:
Shared Hit Blocks (average): 84.24 -> 8.54
Shared Read Blocks (average): 49.89 -> 0.74
Execution Time (average): 0.84 -> 0.065 ms
I/O Read Time (average): 0.16 -> 0.004 ms
Additionally, the time a REINDEX takes also improves significantly:
672407.584 ms (11:12.408) -> 130670.232 ms (02:10.670)
Most of the sortsupport for btree_gist was implemented by re-using
already existing infrastructure. For the few remaining types (bit, bool,
cash, enum, interval, macaddress8 and time) I manually implemented them
directly in btree_gist.
It might make sense to move them into the backend for uniformity, but I
wanted to get other opinions on that first.
`make check-world` reports no regressions.
Attached below, besides the patch, are also two scripts for benchmarking.
`bench-gist.py` to benchmark the actual patch, example usage of this
would be e.g. `./bench-gist.py -o results.csv public.table`. This
expects a local instance with no authentication and default `postgres`
user. The port can be set using the `--port` option.
`plot.py` prints average values (as used above) and creates boxplots for
each statistic from the result files produced with `bench-gist.py`.
Depends on matplotlib and pandas.
Additionally, if needed, the sample dataset used to benchmark this is
available to independently verify the results [1].
Thanks,
Christoph Heiss
---
[1] https://drive.google.com/file/d/1SKRiUYd78_zl7CeD8pLDoggzCCh0wj39
From 22e1b60929c39309e06c2477d8d027e60ad49b9d Mon Sep 17 00:00:00 2001
From: Christoph Heiss <christoph.he...@cybertec.at>
Date: Thu, 9 Jun 2022 17:07:46 +0200
Subject: [PATCH 1/1] Add sortsupport for range types and btree_gist
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 <christoph.he...@cybertec.at>
---
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 | 19 ++++
contrib/btree_gist/btree_gist--1.7--1.8.sql | 105 ++++++++++++++++++++
contrib/btree_gist/btree_gist.control | 2 +-
contrib/btree_gist/btree_interval.c | 19 ++++
contrib/btree_gist/btree_macaddr8.c | 19 ++++
contrib/btree_gist/btree_time.c | 19 ++++
src/backend/utils/adt/rangetypes_gist.c | 70 +++++++++++++
src/include/catalog/pg_amproc.dat | 3 +
src/include/catalog/pg_proc.dat | 3 +
13 files changed, 323 insertions(+), 2 deletions(-)
create mode 100644 contrib/btree_gist/btree_gist--1.7--1.8.sql
diff --git a/contrib/btree_gist/Makefile b/contrib/btree_gist/Makefile
index 48997c75f6..4096de73ea 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 5b246bcde4..bf32bfd628 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 8b2af129b5..3a9f230e68 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 6ac97e2b12..389b725130 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 d4dc38a38e..2ab0ae9bc8 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,15 @@ 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(DirectFunctionCall2(enum_cmp, x, y));
+}
+
static bool
gbt_enumgt(const void *a, const void *b, FmgrInfo *flinfo)
{
@@ -183,3 +191,14 @@ 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;
+ ssup->ssup_extra = NULL;
+
+ 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 0000000000..01bd8f9f64
--- /dev/null
+++ b/contrib/btree_gist/btree_gist--1.7--1.8.sql
@@ -0,0 +1,105 @@
+/* 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_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) network_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 fa9171a80a..abf66538f3 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_interval.c b/contrib/btree_gist/btree_interval.c
index c2bf82086d..80179adc99 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 796cc4efee..034e34bf90 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 fd8774a2f0..fb3454987b 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/src/backend/utils/adt/rangetypes_gist.c b/src/backend/utils/adt/rangetypes_gist.c
index fbf39dbf30..2ded365dc2 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)
@@ -1692,6 +1708,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/src/include/catalog/pg_amproc.dat b/src/include/catalog/pg_amproc.dat
index 4cc129bebd..9318ad5fd8 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 87aa571a33..47676fb53e 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -10376,6 +10376,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',
--
2.36.1
#!/usr/bin/env python3
import sys
import matplotlib.pyplot as plt
import pandas as pd
df = pd.concat(pd.read_csv(f) for f in sys.argv[1:])
print(df)
grp = df.groupby('tbl')
print(grp['hit'].mean())
print(grp['time'].mean())
print(grp['read'].mean())
print(grp['iotime'].mean())
fig, axs = plt.subplots(1, 4, figsize=(16, 6))
stats = {
'hit': 'Shared block hits',
'time':'Execution time in ms',
'read': 'Shared block reads',
'iotime': 'I/O read time in ms'
}
for index, (name, desc) in enumerate(stats.items()):
df.boxplot(by='tbl', ax=axs[index], column=name, rot=45, showfliers=False)
axs[index].set_xlabel('')
axs[index].set_ylabel(desc)
plt.tight_layout(w_pad=4)
plt.suptitle('Sortsupport for range types and btree_gist')
plt.show()
#!/usr/bin/env python3
import csv
import psycopg2
import logging
import argparse
logging.basicConfig(level=logging.INFO, format="%(asctime)s %(levelname)s %(message)s")
parser = argparse.ArgumentParser()
parser.add_argument("--output", "-o")
parser.add_argument("--iters", "-n", default=10, type=int)
parser.add_argument("--points", "-p", default=10000, type=int)
parser.add_argument("--port", default=5432, type=int)
parser.add_argument("inputs", nargs="*")
args = parser.parse_args()
conn = psycopg2.connect(f'host=/tmp user=postgres dbname=postgres port={args.port}')
cur = conn.cursor()
output = open(args.output, 'w')
out = csv.writer(output)
out.writerow(['schema', 'tbl', 'i', 'point', 'time', 'hit', 'read', 'iotime'])
for schema, tbl in [i.split(".") for i in args.inputs]:
logging.info(f"Fetching points for {schema}.{tbl}")
cur.execute(f"SELECT id, block_range FROM {schema}.{tbl} ORDER BY RANDOM() LIMIT {args.points}")
datapoints = cur.fetchall()
logging.info(f"Benching {schema}.{tbl}")
for iteration in range(args.iters):
logging.info(f" iter {iteration}")
for pointid, point in enumerate(datapoints):
cur.execute(f"EXPLAIN (BUFFERS, ANALYZE, FORMAT 'json') SELECT * FROM {schema}.{tbl} WHERE id = %s AND block_range && %s", point)
explain = cur.fetchone()[0][0]
plan = explain['Plan']
exec_time = explain['Execution Time']
hit = plan['Shared Hit Blocks']
read = plan['Shared Read Blocks']
readtime = plan['I/O Read Time']
out.writerow(list(map(str, [schema, tbl, iteration+1, pointid+1, exec_time, hit, read, readtime])))
