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

On Thu, Dec 1, 2022 at 1:27 AM Bernd Helmle <mailings(at)oopsware(dot)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.