Thread: [PATCH] Add sortsupport for range types and btree_gist

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

Hi Christoph!

> On 15 Jun 2022, at 15:45, Christoph Heiss <christoph.heiss@cybertec.at> wrote:
>
> By sorting the data before inserting it into the index results in a much better index structure, leading to
significantperformance improvements. 

Here's my version of the very similar idea [0]. It lacks range types support.
On a quick glance your version lacks support of abbreviated sort, so I think benchmarks can be pushed event further :)
Let's merge our efforts and create combined patch?

Please, create a new entry for the patch on Commitfest.

Thank you!

Best regards, Andrey Borodin.

[0] https://commitfest.postgresql.org/37/2824/

On Wed, Jun 15, 2022 at 3:45 AM Christoph Heiss
<christoph.heiss@cybertec.at> wrote:
> `make check-world` reports no regressions.

cfbot is reporting a crash in contrib/btree_gist:

    https://cirrus-ci.com/github/postgresql-cfbot/postgresql/commitfest/38/3686

Thanks,
--Jacob

This entry has been waiting on author input for a while (our current
threshold is roughly two weeks), so I've marked it Returned with
Feedback.

Once you think the patchset is ready for review again, you (or any
interested party) can resurrect the patch entry by visiting

    https://commitfest.postgresql.org/38/3686/

and changing the status to "Needs Review", and then changing the
status again to "Move to next CF". (Don't forget the second step;
hopefully we will have streamlined this in the near future!)

Thanks,
--Jacob

Hi!

Sorry for the long delay.

This fixes the crashes, now all tests run fine w/ and w/o debug 
configuration. That shouldn't even have slipped through as such.

Notable changes from v1:
- gbt_enum_sortsupport() now passes on fcinfo->flinfo
   enum_cmp_internal() needs a place to cache the typcache entry.
- inet sortsupport now uses network_cmp() directly

Thanks,
Christoph Heiss

Hi,

On 2022-08-31 21:15:40 +0200, Christoph Heiss wrote:
> Notable changes from v1:
> - gbt_enum_sortsupport() now passes on fcinfo->flinfo
>   enum_cmp_internal() needs a place to cache the typcache entry.
> - inet sortsupport now uses network_cmp() directly

Updated the patch to add the minimal change for meson compat.

Greetings,

Andres Freund

On 2022-10-02 00:23:32 -0700, Andres Freund wrote:
> Updated the patch to add the minimal change for meson compat.

Now I made the same mistake of not adding the change... Clearly I need to stop
for tonight. Either way, here's the hopefully correct change.

Hi,

No deep code review yet, but CF is approaching its end and i didn't
have time to look at this earlier :/ 

Below are some things i've tested so far.

Am Mittwoch, dem 15.06.2022 um 12:45 +0200 schrieb Christoph Heiss:


> 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.
>

Here are my results with repeating this:

HEAD:
-- token index (buffering=auto)
CREATE INDEX Time: 700213,110 ms (11:40,213)

HEAD patched:

-- token index (buffering=auto)
CREATE INDEX Time: 136229,400 ms (02:16,229)

So index creation speed on the test set (table filled with the tokens
and then creating the index afterwards) gets a lot of speedup with this
patch and default buffering strategy.

> 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

I've changed this a little and did the following:

    CREATE EXTENSION btree_gist;
    CREATE TABLE t (id uuid, block_range int4range);
    COPY t FROM '..' DELIMITER ',' CSV HEADER;
    CREATE INDEX ON before USING GIST (id, block_range);

So creating the index _after_ having loaded the tokens.
My configuration was:

shared_buffers = 4G
max_wal_size = 6G
effective_cache_size = 4g # (default, index fits)
maintenance_work_mem = 1G


Here are my numbers from the attached benchmark script 

HEAD -> HEAD patched:

Shared Hit Blocks (avg) : 76.81 -> 9.17
Shared Read Blocks (avg): 0.43 -> 0.11
Execution Time (avg)    : 0.40 -> 0.05
IO Read Time (avg)      : 0.001 -> 0.0007

So with these settings i see an improvement with the provided test set.
Since this patches adds sortsupport for all other existing opclasses, i
thought to give it a try with another test set. What i did was to adapt
the benchmark script (see attached) to use the "pgbench_accounts" table
which i changed to instead using the primary key to have a btree_gist
index on column "aid".

I let pgbench fill its tables with scale = 1000, dropped the primary
key, create the btree_gist on "aid" with default buffering strategy:

pgbench -s 1000 -i bernd

ALTER TABLE pgbench_accounts DROP CONSTRAINT pgbench_accounts_pkey ;
CREATE INDEX ON pgbench_accounts USING gist(aid);

Ran the benchmark script bench-gist-pgbench_accounts.py:

The numbers are:

HEAD -> HEAD patched

Shared Hit Blocks (avg) : 4.85 -> 8.75
Shared Read Blocks (avg): 0.14 -> 0.17
Execution Time (avg)    : 0.01 -> 0.05
IO Read Time (avg)      : 0.0003 -> 0.0009

So numbers got worse here. You can uncover this when using pgbench
against that modified table in a much more worse outcome.

Running

pgbench -s 1000 -c 16 -j 16 -S -Mprepared -T 300

on my workstation at least 3 times gives me the following numbers:

HEAD:

tps = 215338.784398 (without initial connection time)
tps = 212826.513727 (without initial connection time)
tps = 212102.857891 (without initial connection time)

HEAD patched:

tps = 126487.796716 (without initial connection time)
tps = 125076.391528 (without initial connection time)
tps = 124538.946388 (without initial connection time)


So this doesn't look good. While this patch gets a real improvement for
the provided tokens, it makes performance for at least int4 on this
test worse. Though the picture changes again if you build the index
buffered:

tps = 198409.248911 (without initial connection time)
tps = 194431.827394 (without initial connection time)
tps = 195657.532281 (without initial connection time)

which is again close to current HEAD (i have no idea why it is even
*that* slower, since "buffered=on" shouldn't employ sortsupport, no?).
Of course, built time for the index in this case is much slower again:

-- pgbench_accounts index (buffered)
CREATE INDEX Time: 900912,924 ms (15:00,913)

So while providing a huge improvement on index creation speed it's
sometimes still required to carefully check the index quality.

[...]


> 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.

Hmm i'd say we leave them in the contrib module until they are required
somewhere else, too or make a separate patch for them? Do we have plans
to have such requirement in the backend already?

Attached is a rebased patch against current HEAD.


Thanks

    Bernd

On Thu, Dec 1, 2022 at 1:27 AM Bernd Helmle <mailings@oopsware.de> wrote:
>
> Hi,
>
> No deep code review yet, but CF is approaching its end and i didn't
> have time to look at this earlier :/
>
> Below are some things i've tested so far.
>
> Am Mittwoch, dem 15.06.2022 um 12:45 +0200 schrieb Christoph Heiss:
>
>
> > 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.
> >
>
> Here are my results with repeating this:
>
> HEAD:
> -- token index (buffering=auto)
> CREATE INDEX Time: 700213,110 ms (11:40,213)
>
> HEAD patched:
>
> -- token index (buffering=auto)
> CREATE INDEX Time: 136229,400 ms (02:16,229)
>
> So index creation speed on the test set (table filled with the tokens
> and then creating the index afterwards) gets a lot of speedup with this
> patch and default buffering strategy.
>
> > 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
>
> I've changed this a little and did the following:
>
>     CREATE EXTENSION btree_gist;
>     CREATE TABLE t (id uuid, block_range int4range);
>     COPY t FROM '..' DELIMITER ',' CSV HEADER;
>     CREATE INDEX ON before USING GIST (id, block_range);
>
> So creating the index _after_ having loaded the tokens.
> My configuration was:
>
> shared_buffers = 4G
> max_wal_size = 6G
> effective_cache_size = 4g # (default, index fits)
> maintenance_work_mem = 1G
>
>
> Here are my numbers from the attached benchmark script
>
> HEAD -> HEAD patched:
>
> Shared Hit Blocks (avg) : 76.81 -> 9.17
> Shared Read Blocks (avg): 0.43 -> 0.11
> Execution Time (avg)    : 0.40 -> 0.05
> IO Read Time (avg)      : 0.001 -> 0.0007
>
> So with these settings i see an improvement with the provided test set.
> Since this patches adds sortsupport for all other existing opclasses, i
> thought to give it a try with another test set. What i did was to adapt
> the benchmark script (see attached) to use the "pgbench_accounts" table
> which i changed to instead using the primary key to have a btree_gist
> index on column "aid".
>
> I let pgbench fill its tables with scale = 1000, dropped the primary
> key, create the btree_gist on "aid" with default buffering strategy:
>
> pgbench -s 1000 -i bernd
>
> ALTER TABLE pgbench_accounts DROP CONSTRAINT pgbench_accounts_pkey ;
> CREATE INDEX ON pgbench_accounts USING gist(aid);
>
> Ran the benchmark script bench-gist-pgbench_accounts.py:
>

 \d pgbench_accounts
              Table "public.pgbench_accounts"
  Column  |     Type      | Collation | Nullable | Default
----------+---------------+-----------+----------+---------
 aid      | integer       |           | not null |
 bid      | integer       |           |          |
 abalance | integer       |           |          |
 filler   | character(84) |           |          |
Indexes:
    "pgbench_accounts_pkey" PRIMARY KEY, btree (aid)

you do  `CREATE INDEX ON pgbench_accounts USING gist(aid);`
but the original patch didn't change contrib/btree_gist/btree_int4.c
So I doubt your benchmark is related to the original patch.
or maybe I missed something.

also per doc:
`
sortsupport
Returns a comparator function to sort data in a way that preserves
locality. It is used by CREATE INDEX and REINDEX commands. The quality
of the created index depends on how well the sort order determined by
the comparator function preserves locality of the inputs.
`
from the doc, add sortsupport function will only influence index build time?

+/*
+ * 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;
+}

per https://www.postgresql.org/docs/current/gist-extensibility.html
QUOTE:
All the GiST support methods are normally called in short-lived memory
contexts; that is, CurrentMemoryContext will get reset after each
tuple is processed. It is therefore not very important to worry about
pfree'ing everything you palloc. However, in some cases it's useful
for a support method to
ENDOF_QUOTE

so removing the following part should be OK.
+ if ((Datum) range_a != a)
+ pfree(range_a);
+
+ if ((Datum) range_b != b)
+ pfree(range_b);

comparison solely on the lower bounds looks strange to me.
if lower bound is the same, then compare upper bound, so the
range_gist_cmp function is consistent with function range_compare.
so following change:

+ else
+ result = range_cmp_bounds(typcache, &lower1, &lower2);
to
`
else
{
result = range_cmp_bounds(typcache, &lower1, &lower2);
if (result == 0)
result = range_cmp_bounds(typcache, &upper1, &upper2);
}
`

does contrib/btree_gist/btree_gist--1.7--1.8.sql function be declared
as strict ? (I am not sure)
other than that, the whole patch looks good.

On Wed, Jan 10, 2024 at 8:00 AM jian he <jian.universality@gmail.com> wrote:
>
> `
> from the doc, add sortsupport function will only influence index build time?
>
> +/*
> + * 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;
> +}
>
> per https://www.postgresql.org/docs/current/gist-extensibility.html
> QUOTE:
> All the GiST support methods are normally called in short-lived memory
> contexts; that is, CurrentMemoryContext will get reset after each
> tuple is processed. It is therefore not very important to worry about
> pfree'ing everything you palloc. However, in some cases it's useful
> for a support method to
> ENDOF_QUOTE
>
> so removing the following part should be OK.
> + if ((Datum) range_a != a)
> + pfree(range_a);
> +
> + if ((Datum) range_b != b)
> + pfree(range_b);
>
> comparison solely on the lower bounds looks strange to me.
> if lower bound is the same, then compare upper bound, so the
> range_gist_cmp function is consistent with function range_compare.
> so following change:
>
> + else
> + result = range_cmp_bounds(typcache, &lower1, &lower2);
> to
> `
> else
> {
> result = range_cmp_bounds(typcache, &lower1, &lower2);
> if (result == 0)
> result = range_cmp_bounds(typcache, &upper1, &upper2);
> }
> `
>
> does contrib/btree_gist/btree_gist--1.7--1.8.sql function be declared
> as strict ? (I am not sure)
> other than that, the whole patch looks good.

the original author email address (christoph.heiss@cybertec.at)
Address not found.
so I don't include it.

I split the original author's patch into 2.
1. Add GiST sortsupport function for all the btree-gist module data
types except anyrange data type (which actually does not in this
module)
2. Add GiST sortsupport function for anyrange data type.

What changed compared to the original patch:
1. The original patch missed some operator class for all the data
types in btree-gist modules. So I added them.
now add sortsupport function for all the following data types in btree-gist:

int2,int4,int8,float4,float8,numeric
timestamp with time zone,
timestamp without time zone, time with time zone, time without time zone, date
interval, oid, money, char
varchar, text, bytea, bit, varbit
macaddr, macaddr8, inet, cidr, uuid, bool, enum

2. range_gist_cmp: the gist range sortsupport function, it looks like
range_cmp, but the range typcache is cached,
so we don't need to repeatedly call lookup_type_cache.
refactor: As mentioned above, if the range lower bound is the same
then compare the upper bound.
I aslo refactored the comment.

what I am confused:
In fmgr.h

/*
 * Support for cleaning up detoasted copies of inputs.  This must only
 * be used for pass-by-ref datatypes, and normally would only be used
 * for toastable types.  If the given pointer is different from the
 * original argument, assume it's a palloc'd detoasted copy, and pfree it.
 * NOTE: most functions on toastable types do not have to worry about this,
 * but we currently require that support functions for indexes not leak
 * memory.
 */
#define PG_FREE_IF_COPY(ptr,n) \
do { \
if ((Pointer) (ptr) != PG_GETARG_POINTER(n)) \
pfree(ptr); \
} while (0)

but the doc (https://www.postgresql.org/docs/current/gist-extensibility.html)
 says:
All the GiST support methods are normally called in short-lived memory
contexts; that is, CurrentMemoryContext will get reset after each
tuple is processed. It is therefore not very important to worry about
pfree'ing everything you palloc.
ENDOF_QUOTE

so I am not sure in range_gist_cmp, we need the following:
`
if ((Datum) range_a != a)
pfree(range_a);
if ((Datum) range_b != b)
pfree(range_b);
`

> On 10 Jan 2024, at 19:18, jian he <jian.universality@gmail.com> wrote:
>
> what I am confused:
> In fmgr.h
>
> /*
> * Support for cleaning up detoasted copies of inputs.  This must only
> * be used for pass-by-ref datatypes, and normally would only be used
> * for toastable types.  If the given pointer is different from the
> * original argument, assume it's a palloc'd detoasted copy, and pfree it.
> * NOTE: most functions on toastable types do not have to worry about this,
> * but we currently require that support functions for indexes not leak
> * memory.
> */
> #define PG_FREE_IF_COPY(ptr,n) \
> do { \
> if ((Pointer) (ptr) != PG_GETARG_POINTER(n)) \
> pfree(ptr); \
> } while (0)
>
> but the doc (https://www.postgresql.org/docs/current/gist-extensibility.html)
> says:
> All the GiST support methods are normally called in short-lived memory
> contexts; that is, CurrentMemoryContext will get reset after each
> tuple is processed. It is therefore not very important to worry about
> pfree'ing everything you palloc.
> ENDOF_QUOTE
>
> so I am not sure in range_gist_cmp, we need the following:
> `
> if ((Datum) range_a != a)
> pfree(range_a);
> if ((Datum) range_b != b)
> pfree(range_b);
> `

I think GiST sortsupport comments are more relevant, so there's no need for this pfree()s.

Also, please check other thread, maybe you will find some useful code there [0,1]. It was committed[2] once, but
reverted.Please make sure that corrections made there are taken into account in your patch. 

Thanks for working on this!


Best regards, Andrey Borodin.

[0] https://commitfest.postgresql.org/31/2824/
[1]
https://www.postgresql.org/message-id/flat/285041639646332%40sas1-bf93f9015d57.qloud-c.yandex.net#0e5b4ed57d861d38a3d836c9ec09c0c5
[2] https://github.com/postgres/postgres/commit/9f984ba6d23dc6eecebf479ab1d3f2e550a4e9be

Am Mittwoch, dem 10.01.2024 um 08:00 +0800 schrieb jian he:


> you do  `CREATE INDEX ON pgbench_accounts USING gist(aid);`
> but the original patch didn't change contrib/btree_gist/btree_int4.c
> So I doubt your benchmark is related to the original patch.
> or maybe I missed something.
>

The patch originally does this:

+ALTER OPERATOR FAMILY gist_int4_ops USING gist ADD
+    FUNCTION    11  (int4, int4) btint4sortsupport (internal) ;

This adds sortsupport function to int4 as well. We reuse existing
btint4sortsupport() function, so no need to change btree_int4.c.

> also per doc:
> `
> sortsupport
> Returns a comparator function to sort data in a way that preserves
> locality. It is used by CREATE INDEX and REINDEX commands. The
> quality
> of the created index depends on how well the sort order determined by
> the comparator function preserves locality of the inputs.
> `
> from the doc, add sortsupport function will only influence index
> build time?
>

Thats the point of this patch. Though it influences the index quality
in a way which seems to cause the measured performance regression
upthread.

>
> per https://www.postgresql.org/docs/current/gist-extensibility.html
> QUOTE:
> All the GiST support methods are normally called in short-lived
> memory
> contexts; that is, CurrentMemoryContext will get reset after each
> tuple is processed. It is therefore not very important to worry about
> pfree'ing everything you palloc. However, in some cases it's useful
> for a support method to
> ENDOF_QUOTE
>
> so removing the following part should be OK.
> + if ((Datum) range_a != a)
> + pfree(range_a);
> +
> + if ((Datum) range_b != b)
> + pfree(range_b);
>

Probably, i think we get a different range objects in case of
detoasting in this case.

> comparison solely on the lower bounds looks strange to me.
> if lower bound is the same, then compare upper bound, so the
> range_gist_cmp function is consistent with function range_compare.
> so following change:
>
> + else
> + result = range_cmp_bounds(typcache, &lower1, &lower2);
> to
> `
> else
> {
> result = range_cmp_bounds(typcache, &lower1, &lower2);
> if (result == 0)
> result = range_cmp_bounds(typcache, &upper1, &upper2);
> }
> `
>
> does contrib/btree_gist/btree_gist--1.7--1.8.sql function be declared
> as strict ? (I am not sure)
> other than that, the whole patch looks good.
>
>

That's something surely to consider.

Am Mittwoch, dem 10.01.2024 um 20:13 +0500 schrieb Andrey M. Borodin:
> I think GiST sortsupport comments are more relevant, so there's no
> need for this pfree()s.
>
> Also, please check other thread, maybe you will find some useful code
> there [0,1]. It was committed[2] once, but reverted. Please make sure
> that corrections made there are taken into account in your patch.
>

At least, i believe we have the same problem described here (many
thanks Andrey for the links, i wasn't aware about this discussion):

https://www.postgresql.org/message-id/98b34b51-a6db-acc4-1bcf-a29caf69bbc7%40iki.fi

> Thanks for working on this!

Absolutely. This patch needs input ...

On Wed, 10 Jan 2024 at 19:49, jian he <jian.universality@gmail.com> wrote:
>
> On Wed, Jan 10, 2024 at 8:00 AM jian he <jian.universality@gmail.com> wrote:
> >
> > `
> > from the doc, add sortsupport function will only influence index build time?
> >
> > +/*
> > + * 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;
> > +}
> >
> > per https://www.postgresql.org/docs/current/gist-extensibility.html
> > QUOTE:
> > All the GiST support methods are normally called in short-lived memory
> > contexts; that is, CurrentMemoryContext will get reset after each
> > tuple is processed. It is therefore not very important to worry about
> > pfree'ing everything you palloc. However, in some cases it's useful
> > for a support method to
> > ENDOF_QUOTE
> >
> > so removing the following part should be OK.
> > + if ((Datum) range_a != a)
> > + pfree(range_a);
> > +
> > + if ((Datum) range_b != b)
> > + pfree(range_b);
> >
> > comparison solely on the lower bounds looks strange to me.
> > if lower bound is the same, then compare upper bound, so the
> > range_gist_cmp function is consistent with function range_compare.
> > so following change:
> >
> > + else
> > + result = range_cmp_bounds(typcache, &lower1, &lower2);
> > to
> > `
> > else
> > {
> > result = range_cmp_bounds(typcache, &lower1, &lower2);
> > if (result == 0)
> > result = range_cmp_bounds(typcache, &upper1, &upper2);
> > }
> > `
> >
> > does contrib/btree_gist/btree_gist--1.7--1.8.sql function be declared
> > as strict ? (I am not sure)
> > other than that, the whole patch looks good.
>
> the original author email address (christoph.heiss@cybertec.at)
> Address not found.
> so I don't include it.
>
> I split the original author's patch into 2.
> 1. Add GiST sortsupport function for all the btree-gist module data
> types except anyrange data type (which actually does not in this
> module)
> 2. Add GiST sortsupport function for anyrange data type.

CFBot shows that the patch does not apply anymore as in [1]:
=== Applying patches on top of PostgreSQL commit ID
7014c9a4bba2d1b67d60687afb5b2091c1d07f73 ===
=== applying patch
./v5-0001-Add-GIST-sortsupport-function-for-all-the-btree-g.patch
patching file contrib/btree_gist/Makefile
Hunk #1 FAILED at 33.
1 out of 1 hunk FAILED -- saving rejects to file contrib/btree_gist/Makefile.rej
...
The next patch would create the file
contrib/btree_gist/btree_gist--1.7--1.8.sql,
which already exists!  Applying it anyway.
patching file contrib/btree_gist/btree_gist--1.7--1.8.sql
Hunk #1 FAILED at 1.
1 out of 1 hunk FAILED -- saving rejects to file
contrib/btree_gist/btree_gist--1.7--1.8.sql.rej
patching file contrib/btree_gist/btree_gist.control
Hunk #1 FAILED at 1.
1 out of 1 hunk FAILED -- saving rejects to file
contrib/btree_gist/btree_gist.control.rej
...
patching file contrib/btree_gist/meson.build
Hunk #1 FAILED at 50.
1 out of 1 hunk FAILED -- saving rejects to file
contrib/btree_gist/meson.build.rej

Please post an updated version for the same.

[1] - http://cfbot.cputube.org/patch_46_3686.log

Regards,
Vignesh

Am Freitag, dem 26.01.2024 um 18:31 +0530 schrieb vignesh C:
> CFBot shows that the patch does not apply anymore as in [1]:
> === Applying patches on top of PostgreSQL commit ID

I've started working on it and planning to submit a polished patch for
the upcoming CF.

Am Mittwoch, dem 10.01.2024 um 22:18 +0800 schrieb jian he:
>
> I split the original author's patch into 2.
> 1. Add GiST sortsupport function for all the btree-gist module data
> types except anyrange data type (which actually does not in this
> module)
> 2. Add GiST sortsupport function for anyrange data type.
>

Please find attached a new version of this patch set with the following
changes/adjustments:

- Rebased to current master
- Heavily reworked *_cmp() functions to properly
decode GPT_VARKEY and GBT_KEY input.

For some datatypes the btree comparison functions were reused and the
input arguments not properly handled. This patch adds dedicated
btree_gist sortsupport comparison methods for all datatypes.

There was another patch from Andrey Borodin (thanks again for the hint)
and a deeper review done by Heikki in [1]. I've incorporated Heikkis
findings in this patch, too.

[...]

I've also updated the btree_gist documentation to reflect the default
sorted built strategy this patch introduces now.


Additionally i did some benchmarks again on this new version on the
patch. Still, index build speed improvement is quite impressive on the
dataset originally provided by Christoph Heiss (since its not available
anymore i've uploaded it here [2] again):

HEAD
(Index was built with default buffering setting)
---------------------
REINDEX (s)      4809
CREATE INDEX (s) 4920

btree_gist sortsupport
----------------------
REINDEX (s)       573
CREATE INDEX (s)   578

I created another pgbench based custom script to measure the single
core speed of the lookup query of the bench-gist.py script. This looks
like this:

init.sql
--------
BEGIN;

DROP TABLE IF EXISTS test_dataset;
CREATE TABLE test_dataset(keyid integer not null, id text not null,
block_range int4range);
CREATE TEMP SEQUENCE testset_seq;
INSERT INTO test_dataset SELECT nextval('testset_seq'), id, block_range
FROM test ORDER BY random() LIMIT 10000;
CREATE UNIQUE INDEX ON test_dataset(keyid);

COMMIT;

bench.pgbench
-------------

\set keyid random(1, 10000)
SELECT id, block_range FROM test_dataset WHERE keyid = :keyid \gset
SELECT id, block_range FROM test WHERE id = ':id' AND block_range &&
':block_range';

Run by

for in in `seq 1 3`; do psql -qXf init.pgbench && pgbench -n -r -c 1 -T
60 -f bench.pgbench; done

With this i get the following (on prewarmed index and table):

HEAD 
-------------------------------------
pgbench single core tps=248,67

btree_gist sortsupport
----------------------------
pgbench single core tps=1830,33

This is an average over 3 runs each (complete results attached). So
this looks really impressive and i hope i didn't do something entirely
wrong (still learning about this GiST stuff).

> what I am confused:
> In fmgr.h
>
> /*
>  * Support for cleaning up detoasted copies of inputs.  This must
> only
>  * be used for pass-by-ref datatypes, and normally would only be used
>  * for toastable types.  If the given pointer is different from the
>  * original argument, assume it's a palloc'd detoasted copy, and
> pfree it.
>  * NOTE: most functions on toastable types do not have to worry about
> this,
>  * but we currently require that support functions for indexes not
> leak
>  * memory.
>  */
> #define PG_FREE_IF_COPY(ptr,n) \
> do { \
> if ((Pointer) (ptr) != PG_GETARG_POINTER(n)) \
> pfree(ptr); \
> } while (0)
>
> but the doc
> (https://www.postgresql.org/docs/current/gist-extensibility.html)
>  says:
> All the GiST support methods are normally called in short-lived
> memory
> contexts; that is, CurrentMemoryContext will get reset after each
> tuple is processed. It is therefore not very important to worry about
> pfree'ing everything you palloc.
> ENDOF_QUOTE
>
> so I am not sure in range_gist_cmp, we need the following:
> `
> if ((Datum) range_a != a)
> pfree(range_a);
> if ((Datum) range_b != b)
> pfree(range_b);
> `

Turns out this is not true for sortsupport: the comparison function is
called for each tuple during sorting, which will leak the detoasted
(and probably copied datum) in the sort memory context. See the same
for e.g. numeric and text, which i needed to change to pass the key
values correctly to the text_cmp() or numeric_cmp() function in these
cases.

I've adapted the PG_FREE_IF_COPY() macro for these functions and
introduced GBT_FREE_IF_COPY() in btree_utils_var.h, since the former
relies on fcinfo.

I'll add the patch again to the upcoming CF for another review round.

[1]
https://www.postgresql.org/message-id/c0846e34-8b3a-e1bf-c88e-021eb241a481%40iki.fi

[2] https://drive.google.com/file/d/1CPNFGR53-FUto1zjXPMM2Yrn0GaGfGFz/view?usp=drive_link

On Fri, Feb 9, 2024 at 2:14 AM Bernd Helmle <mailings@oopsware.de> wrote:
>
> Am Mittwoch, dem 10.01.2024 um 22:18 +0800 schrieb jian he:
> >
> > I split the original author's patch into 2.
> > 1. Add GiST sortsupport function for all the btree-gist module data
> > types except anyrange data type (which actually does not in this
> > module)
> > 2. Add GiST sortsupport function for anyrange data type.
> >
>
> > what I am confused:
> > In fmgr.h
> >
> > /*
> >  * Support for cleaning up detoasted copies of inputs.  This must
> > only
> >  * be used for pass-by-ref datatypes, and normally would only be used
> >  * for toastable types.  If the given pointer is different from the
> >  * original argument, assume it's a palloc'd detoasted copy, and
> > pfree it.
> >  * NOTE: most functions on toastable types do not have to worry about
> > this,
> >  * but we currently require that support functions for indexes not
> > leak
> >  * memory.
> >  */
> > #define PG_FREE_IF_COPY(ptr,n) \
> > do { \
> > if ((Pointer) (ptr) != PG_GETARG_POINTER(n)) \
> > pfree(ptr); \
> > } while (0)
> >
> > but the doc
> > (https://www.postgresql.org/docs/current/gist-extensibility.html)
> >  says:
> > All the GiST support methods are normally called in short-lived
> > memory
> > contexts; that is, CurrentMemoryContext will get reset after each
> > tuple is processed. It is therefore not very important to worry about
> > pfree'ing everything you palloc.
> > ENDOF_QUOTE
> >
> > so I am not sure in range_gist_cmp, we need the following:
> > `
> > if ((Datum) range_a != a)
> > pfree(range_a);
> > if ((Datum) range_b != b)
> > pfree(range_b);
> > `
>
> Turns out this is not true for sortsupport: the comparison function is
> called for each tuple during sorting, which will leak the detoasted
> (and probably copied datum) in the sort memory context. See the same
> for e.g. numeric and text, which i needed to change to pass the key
> values correctly to the text_cmp() or numeric_cmp() function in these
> cases.
>

+ <para>
+  Per default <filename>btree_gist</filename> builts
<acronym>GiST</acronym> indexe with
+  <function>sortsupport</function> in <firstterm>sorted</firstterm>
mode. This usually results in a
+  much better index quality and smaller index sizes by 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>
+
I believe `built` |`builts` should be `build`.
Also
maybe we can simply copy some texts from
https://www.postgresql.org/docs/current/gist-implementation.html.
how about the following:
  <para>
   The sorted method is only available if each of the opclasses used by the
   index provides a <function>sortsupport</function> function, as described
   in <xref linkend="gist-extensibility"/>.  If they do, this method is
   usually the best, so it is used by default.
  It is still possible to change to a buffered build strategy by using
the <literal>buffering</literal> parameter
  to the CREATE INDEX command.
  </para>

you've changed contrib/btree_gist/meson.build, seems we also need to
change contrib/btree_gist/Makefile

gist_point_sortsupport have `if (ssup->abbreviate)`,  does
range_gist_sortsupport also this part?
I think the `if(ssup->abbreviate)` part is optional?
Can we add some comments on it?

Am Montag, dem 12.02.2024 um 21:00 +0800 schrieb jian he:
> + <para>
> +  Per default <filename>btree_gist</filename> builts
> <acronym>GiST</acronym> indexe with
> +  <function>sortsupport</function> in <firstterm>sorted</firstterm>
> mode. This usually results in a
> +  much better index quality and smaller index sizes by 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>
> +
> I believe `built` |`builts` should be `build`.

Right, Fixed.

> Also
> maybe we can simply copy some texts from
> https://www.postgresql.org/docs/current/gist-implementation.html.
> how about the following:
>   <para>
>    The sorted method is only available if each of the opclasses used
> by the
>    index provides a <function>sortsupport</function> function, as
> described
>    in <xref linkend="gist-extensibility"/>.  If they do, this method
> is
>    usually the best, so it is used by default.
>   It is still possible to change to a buffered build strategy by
> using
> the <literal>buffering</literal> parameter
>   to the CREATE INDEX command.
>   </para>

Hmm not sure what you are trying to achieve with this? The opclasses in
btree_gist provides sortsupport, but by reading the above i would get
the impression they're still optional.

>
> you've changed contrib/btree_gist/meson.build, seems we also need to
> change contrib/btree_gist/Makefile
>

Oh, good catch. I'm so focused on meson already that i totally forgot
the good old Makefile. Fixed.

> gist_point_sortsupport have `if (ssup->abbreviate)`,  does
> range_gist_sortsupport also this part?
> I think the `if(ssup->abbreviate)` part is optional?
> Can we add some comments on it?

I've thought about abbreviated keys support but put that aside for
later. I wanted to focus on general sortsupport first before getting my
hands on it and so postponed it for another round.

If we agree that this patch needs support for abbreviated keys now, i
certainly can work on it.

Thanks for your review,

    Bernd

Hi,

Here is a rebased version of the patch. Since i don't have anything to
add at the moment and the numbers looks promising and to move on, i've
marked this patch "Ready For Committer".


Thanks,

    Bernd

> On 22 Mar 2024, at 18:20, Bernd Helmle <mailings@oopsware.de> wrote:
>
> Here is a rebased version of the patch.

FWIW it would be nice at least port tests from commit that I referenced upthread.
Nowadays we have injection points, so these tests can be much more stable.

Sorry for bringing up this so late.


Best regards, Andrey Borodin.

Hi Andrey,

Am Freitag, dem 22.03.2024 um 18:27 +0500 schrieb Andrey M. Borodin:
> > Here is a rebased version of the patch.
>
> FWIW it would be nice at least port tests from commit that I
> referenced upthread.
> Nowadays we have injection points, so these tests can be much more
> stable.

Alright, that's a reasonable point. I will look into this. Did you see
other important things missing?

Changed status back to "Waiting On Author".

Thanks,

    Bernd

> On 25 Oct 2024, at 19:41, Bernd Helmle <mailings@oopsware.de> wrote:
>
> So this is a new rebased version of the patches including regression
> tests with default (sortsupport) and buffering behavior. I split up the
> tests for buffering vs. non-buffering but kept them basically the same
> for testing the index builts.

Hi Bernde!
Thanks for the patch!

I have some notes.

First patch:
0. We have PG_FREE_IF_COPY(), does it suits your needs?
1. Tests do not check what actual build method is used. You can add INJECTION_POINT("gist-sort-build") and expect a
noticethere or something like that. 
2. "Per default" -> "By default", "indexe" -> "index", "index quality" -> NULL (in 14 quality was bad, since 15 same
"quality")

Second patch:
0. PG_FREE_IF_COPY in range_gist_cmp? :)
1. Some test of this new functionality?

Thanks!


Best regards, Andrey Borodin.

Am Samstag, dem 26.10.2024 um 11:40 +0300 schrieb Andrey M. Borodin:
> First patch:
> 0. We have PG_FREE_IF_COPY(), does it suits your needs?

PG_FREE_IF_COPY() requires FunctionCallInfo (the macro uses
PG_GETARG_POINTER() to reference the pointer value to compare), which
is not usable in the context we need it.

> 1. Tests do not check what actual build method is used. You can add
> INJECTION_POINT("gist-sort-build") and expect a notice there or
> something like that.

Hmm good idea, i give it a try.

> 2. "Per default" -> "By default", "indexe" -> "index", "index
> quality" -> NULL (in 14 quality was bad, since 15 same "quality")
>
> Second patch:
> 0. PG_FREE_IF_COPY in range_gist_cmp? :)

See above.

> 1. Some test of this new functionality?

Right, but i am unsure where this belongs to. Perhaps to
src/test/regress/sql/rangetypes.sql ? We can extend the gist tests
there.

> On 11 Nov 2024, at 21:41, Bernd Helmle <mailings@oopsware.de> wrote:
>
> Updated and rebased patches attached.

Hi Bernd!

Some nitpicking:
0. postgres % git apply ~/Downloads/v7.3-Add-GIST-sortsupport-*
/Users/x4mmm/Downloads/v7.3-Add-GIST-sortsupport-btree-gist.patch:19: space before tab in indent.
    oid oid_buffering timestamp timestamp_buffering timestamptz \
/Users/x4mmm/Downloads/v7.3-Add-GIST-sortsupport-btree-gist.patch:20: space before tab in indent.
    timestamptz_buffering time time_buffering timetz timetz_buffering date \
/Users/x4mmm/Downloads/v7.3-Add-GIST-sortsupport-btree-gist.patch:21: space before tab in indent.
    date_buffering interval interval_buffering macaddr macaddr_buffering \
/Users/x4mmm/Downloads/v7.3-Add-GIST-sortsupport-btree-gist.patch:22: space before tab in indent.
    macaddr8 macaddr8_buffering inet inet_buffering cidr cidr_buffering text \
/Users/x4mmm/Downloads/v7.3-Add-GIST-sortsupport-btree-gist.patch:23: space before tab in indent.
    text_buffering varchar varchar_buffering char char_buffering \
warning: 5 lines add whitespace errors.

1. I'm mostly seening patches formatted with `git patch-format` rather than diffs as patches...

2. Changes in contrib/btree_gist/btree_gist.c seem unnecessary.

3. Why do you move "typedef struct int32key" to btree_gist.h, but do not need to move all other keys?

4. These ifdedfs are not needed, just do INJECTION_POINT()
#ifdef USE_INJECTION_POINTS
INJECTION_POINT("btree-gist-sorted-build");
#endif

Also, there are 61 occurance of this code. Why not just 1 in gist_indexsortbuild() ?

Thanks!


Best regards, Andrey Borodin.

Am Montag, dem 11.11.2024 um 23:03 +0500 schrieb Andrey M. Borodin:
> Some nitpicking:
> 0. postgres % git apply ~/Downloads/v7.3-Add-GIST-sortsupport-*
> /Users/x4mmm/Downloads/v7.3-Add-GIST-sortsupport-btree-gist.patch:19:
> space before tab in indent.

I obviously shouldn't do patches after a long work day....


[...]

>
> 1. I'm mostly seening patches formatted with `git patch-format`
> rather than diffs as patches...
>

Will do.

> 2. Changes in contrib/btree_gist/btree_gist.c seem unnecessary.
>

Agreed. Will fix

> 3. Why do you move "typedef struct int32key" to btree_gist.h, but do
> not need to move all other keys?
>

Hmm, afair i did this back in an earlier stage of the patch and forgot
about it. It needs to be moved back to btree_int4.c, will fix.

> 4. These ifdedfs are not needed, just do INJECTION_POINT()
> #ifdef USE_INJECTION_POINTS
> INJECTION_POINT("btree-gist-sorted-build");
> #endif
>

I never worked with injection points before, i copied that pattern from
the docs somewhere, where those #ifdef's are used. Will fix.

> Also, there are 61 occurance of this code. Why not just 1 in
> gist_indexsortbuild() ?
>
>

Right, but after thinking about this i'd even go further: naming the
injection points for the sortsupport according to their datatype
they're called on. That would connect the regression test with the
specific datatype/sortsupport function and this would make sure the
correct sortsupport function for the specific test case is called.
Though that means that each test needs to attach/detach the injection
point itself...

What do you think?

Thanks,
    Bernd