Re: GiST intarray build speedup: two-arg fast path

Hi Kirill,

> While profiling index builds for different AMs, I noticed that GiST
> index for inarray
> speds much time in in g_int_union and qsort inside inner_int_union for
> some of benchmark cases.This simple diff gives 1.2-1.5x speedup:
>
>
> diff --git a/contrib/intarray/_int_gist.c b/contrib/intarray/_int_gist.c
> index 98711ac54e2..966409e9582 100644
> --- a/contrib/intarray/_int_gist.c
> +++ b/contrib/intarray/_int_gist.c
> @@ -130,6 +130,14 @@ g_int_union(PG_FUNCTION_ARGS)
> ArrayType *res;
> int totlen = 0;
>
> + if (entryvec->n == 2)
> + {
> + res = inner_int_union(GETENTRY(entryvec, 0),
> +
> GETENTRY(entryvec, 1));
> + *size = VARSIZE(res);
> + PG_RETURN_POINTER(res);
> + }
> +
> for (i = 0; i < entryvec->n; i++)
> {
> ArrayType *ent = GETENTRY(entryvec, i);
>
> Simple case where this helps (SQL was generated by my fuzzer)
>
> CREATE EXTENSION IF NOT EXISTS intarray;
> CREATE TABLE t AS
> SELECT i id,
> ARRAY(SELECT DISTINCT ((hashint4(i*43+j)::bigint)%10000)::int
> FROM generate_series(1,30) j) a
> FROM generate_series(1,5000) i;
>
> CREATE INDEX ON t USING gist(a gist__int_ops);
>
> index create time 46s->26s.
> I did run some other benchmarks and it didn't show any regressions.

Is this because of the specific data ingested or does that hold for all
ingest patterns? Seems like gistMakeUnionKey() always calls
g_int_union() with just two input arrays. Is this where the speedup
comes from?

> Off-list Andrey x4m proposed to try this for n = 3 4 5 etc, which also
> shows some speedup (i. don't have full bench result yet).
The current complexity of g_int_union() is O(N * log N) where N is the
total number of elements across all K input arrays. Your optimization
seems to be a special case of a min-heap based algorithm for K = 2,
where the general complexity is O(N * log K).

Have you thought about implementing a proper min-heap based algorithm?
That would then naturally also work for K > 2.

--
David Geier