Thread

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

Change PointerGetDatum() back to a macro
- d65995cbc6e1 19 (unreleased) landed
Replace deprecated StaticAssertStmt() with StaticAssertDecl()
- 66ad764c8d51 19 (unreleased) landed
Optimize sorting and deduplicating trigrams
- 9f3755ea07aa 19 (unreleased) landed
Optimize sort and deduplication in ginExtractEntries()
- 6f5ad00ab763 19 (unreleased) landed
Inline ginCompareAttEntries for speed
- bba81f9d3d4f 19 (unreleased) landed

Reduce build times of pg_trgm GIN indexes

David Geier <geidav.pg@gmail.com> — 2026-01-05T15:01:44Z

Hi hackers,

Attached is a series of patches which gradually reduce the time it takes
to create GIN indexes. Most of the gains come from optimizing the
trigram extraction code in pg_trgm. A few small optimizations apply to
any GIN index operator class.

The changes are motivated by the time it takes to create GIN indexes on
large production tables, especially, on columns with long strings. Even
with multiple parallel maintenance workers I've seen this taking hours.

For testing purposes I've used two different data sets:

1. The l_comment column of the TPC-H SF 10 lineitem table. l_comment
contains relatively short strings with a minimum of 10, a maximum of 43
and an average of ~27 characters.

2. The plots from a collection of movies from Wikipedia. The plots are
much longer than l_comment, with a minimum of 15, a maximum of 36,773
and an average of ~2,165 characters. The CSV file can be downloaded here
[1].

Testing both cases is important because a big part of the trigram
extraction is spent on removing duplicates. The longer the string, the
more duplicates are usually encountered.

The script I used for testing is attached. I ran CREATE INDEX three
times and took the fastest run. I'm getting the following results on my
i9-13950HX dev laptop in release build:

Data set | Patched (ms) | Master (ms) | Speedup
--------------------|--------------|--------------|----------
movies(plot) | 3,409 | 10,311 | 3.02x
lineitem(l_comment) | 161,569 | 256,986 | 1.59x

The attached patches do the following:

- v1-0001-Inline-ginCompareAttEntries.patch: Inline
ginCompareAttEntries() which is very frequently called by the GIN code.

- v1-0002-Optimized-comparison-functions.patch: Use FunctionCallInvoke()
instead of FunctionCall2Coll(). This saves a bunch of per-comparison
setup code, such as calling InitFunctionCallInfoData().

- v1-0003-Use-sort_template.h.patch: Use sort_template.h instead of
qsort(), to inline calls to the sort comparator. This is an interim step
that is further improved on by patch 0006.

- v1-0004-Avoid-dedup-and-sort-in-ginExtractEntries.patch
ginExtractEntries() deduplicates and sorts the entries returned from the
extract value function. In case of pg_trgm, that is completely redundant
because the trigrams are already deduplicated and sorted. The current
version of this patch is just to demonstrate the potential. We need to
think about what we want here. Ideally, we would require the extraction
function to provide the entries deduplicated and sorted. Alternatively,
we could indicate to ginExtractEntries() if the entries are already
deduplicated and sorted. If we don't want to alter the signature of the
extract value function, we could e.g. use the MSB of the nentries argument.

- v1-0005-Make-btint4cmp-branchless.patch: Removes branches from
btint4cmp(), which is heavily called from the GIN code. This might as
well have benefit in other parts of the code base.

v1-0006-Use-radix-sort.patch: Replace the sort_template.h-based qsort()
with radix sort. For the purpose of demonstrating the possible gains,
I've only replaced the signed variant for now. I've also tried using
simplehash.h for deduplicating followed by a sort_template.h-based sort.
But that was slower.

v1-0007-Faster-qunique-comparator.patch: qunique() doesn't require a
full sort comparator (-1 = less, 0 = equal, 1 = greater) but only a
equal/unequal comparator (e.g. 0 = equal and 1 = unequal). The same
optimization can be done in plenty of other places in our code base.
Likely, in most of them the gains are insignificant.

v1-0008-Add-ASCII-fastpath-to-generate_trgm_only.patch: Typically lots
of text is actually ASCII. Hence, we provide a fast path for this case
which is exercised if the MSB of the current character is unset.

With above changes, the majority of the runtime is now spent on
inserting the trigrams into the GIN index via ginInsertBAEntry(). The
code in master uses a red-black for further deduplication and sorting.
Traversing the red-black tree and updating it is pretty slow. I haven't
looked through all the code yet, but it seems to me that we would be
better off replacing the red-black tree with a sort and/or a hash map.
But I'll leave this as future work for now.

[1]
https://github.com/kiq005/movie-recommendation/raw/refs/heads/master/src/dataset/wiki_movie_plots_deduped.csv

--
David Geier

Re: Reduce build times of pg_trgm GIN indexes

Heikki Linnakangas <hlinnaka@iki.fi> — 2026-01-06T17:00:23Z

On 05/01/2026 17:01, David Geier wrote:
> The script I used for testing is attached. I ran CREATE INDEX three
> times and took the fastest run. I'm getting the following results on my
> i9-13950HX dev laptop in release build:
> 
> Data set            | Patched (ms) | Master (ms)  | Speedup
> --------------------|--------------|--------------|----------
> movies(plot)        |   3,409      |  10,311      | 3.02x
> lineitem(l_comment) | 161,569      | 256,986      | 1.59x
> 

Impressive speedup!

> The attached patches do the following:
> 
> - v1-0001-Inline-ginCompareAttEntries.patch: Inline
> ginCompareAttEntries() which is very frequently called by the GIN code.

Looks good.

> - v1-0002-Optimized-comparison-functions.patch: Use FunctionCallInvoke()
> instead of FunctionCall2Coll(). This saves a bunch of per-comparison
> setup code, such as calling InitFunctionCallInfoData().

You lose the check for NULL result with this. That's probably still 
worth checking.

> - v1-0003-Use-sort_template.h.patch: Use sort_template.h instead of
> qsort(), to inline calls to the sort comparator. This is an interim step
> that is further improved on by patch 0006.

ok

> - v1-0004-Avoid-dedup-and-sort-in-ginExtractEntries.patch
> ginExtractEntries() deduplicates and sorts the entries returned from the
> extract value function. In case of pg_trgm, that is completely redundant
> because the trigrams are already deduplicated and sorted. The current
> version of this patch is just to demonstrate the potential. We need to
> think about what we want here. Ideally, we would require the extraction
> function to provide the entries deduplicated and sorted. Alternatively,
> we could indicate to ginExtractEntries() if the entries are already
> deduplicated and sorted. If we don't want to alter the signature of the
> extract value function, we could e.g. use the MSB of the nentries argument.

Yeah, this seems wrong as it is. You're assuming that if the extract 
function returns nullFlags == NULL, the array is already sorted and deduped.

> - v1-0005-Make-btint4cmp-branchless.patch: Removes branches from
> btint4cmp(), which is heavily called from the GIN code. This might as
> well have benefit in other parts of the code base.

Seems reasonable.

> v1-0006-Use-radix-sort.patch: Replace the sort_template.h-based qsort()
> with radix sort. For the purpose of demonstrating the possible gains,
> I've only replaced the signed variant for now. I've also tried using
> simplehash.h for deduplicating followed by a sort_template.h-based sort.
> But that was slower.

Ok.

> v1-0007-Faster-qunique-comparator.patch: qunique() doesn't require a
> full sort comparator (-1 = less, 0 = equal, 1 = greater) but only a
> equal/unequal comparator (e.g. 0 = equal and 1 = unequal). The same
> optimization can be done in plenty of other places in our code base.
> Likely, in most of them the gains are insignificant.

Makes sense. I'm a little disappointed the compiler won't do that 
optimization for us..

Perhaps we should introduce a new qunique_eq() function with a different 
callback signature:

/* like qunique(), but the callback function returns true/false rather 
than int */
static inline size_t
qunique_eq(void *array, size_t elements, size_t width,
		bool (*equal) (const void *, const void *))

> v1-0008-Add-ASCII-fastpath-to-generate_trgm_only.patch: Typically lots
> of text is actually ASCII. Hence, we provide a fast path for this case
> which is exercised if the MSB of the current character is unset.

This uses pg_ascii_tolower() when for ASCII characters when built with 
the IGNORECASE. I don't think that's correct, if the proper collation 
would do something more complicated for than what pg_ascii_tolower() does.

Did you measure how big is the impact from each individual patch? 
Patches 1 and 2 seem pretty much ready to be committed, but I wonder if 
they make any difference on their own.

- Heikki

Re: Reduce build times of pg_trgm GIN indexes

Kirill Reshke <reshkekirill@gmail.com> — 2026-01-06T20:05:45Z

On Tue, 6 Jan 2026 at 22:00, Heikki Linnakangas <hlinnaka@iki.fi> wrote:
>
> On 05/01/2026 17:01, David Geier wrote:
> > The script I used for testing is attached. I ran CREATE INDEX three
> > times and took the fastest run. I'm getting the following results on my
> > i9-13950HX dev laptop in release build:
> >
> > Data set            | Patched (ms) | Master (ms)  | Speedup
> > --------------------|--------------|--------------|----------
> > movies(plot)        |   3,409      |  10,311      | 3.02x
> > lineitem(l_comment) | 161,569      | 256,986      | 1.59x
> >
>
> Impressive speedup!
>
> > The attached patches do the following:
> >
> > - v1-0001-Inline-ginCompareAttEntries.patch: Inline
> > ginCompareAttEntries() which is very frequently called by the GIN code.
>
> Looks good.
>
> > - v1-0002-Optimized-comparison-functions.patch: Use FunctionCallInvoke()
> > instead of FunctionCall2Coll(). This saves a bunch of per-comparison
> > setup code, such as calling InitFunctionCallInfoData().
>
> You lose the check for NULL result with this. That's probably still
> worth checking.
>
> > - v1-0003-Use-sort_template.h.patch: Use sort_template.h instead of
> > qsort(), to inline calls to the sort comparator. This is an interim step
> > that is further improved on by patch 0006.
>
> ok
>
> > - v1-0004-Avoid-dedup-and-sort-in-ginExtractEntries.patch
> > ginExtractEntries() deduplicates and sorts the entries returned from the
> > extract value function. In case of pg_trgm, that is completely redundant
> > because the trigrams are already deduplicated and sorted. The current
> > version of this patch is just to demonstrate the potential. We need to
> > think about what we want here. Ideally, we would require the extraction
> > function to provide the entries deduplicated and sorted. Alternatively,
> > we could indicate to ginExtractEntries() if the entries are already
> > deduplicated and sorted. If we don't want to alter the signature of the
> > extract value function, we could e.g. use the MSB of the nentries argument.
>
> Yeah, this seems wrong as it is. You're assuming that if the extract
> function returns nullFlags == NULL, the array is already sorted and deduped.
>
> > - v1-0005-Make-btint4cmp-branchless.patch: Removes branches from
> > btint4cmp(), which is heavily called from the GIN code. This might as
> > well have benefit in other parts of the code base.
>
> Seems reasonable.
>
> > v1-0006-Use-radix-sort.patch: Replace the sort_template.h-based qsort()
> > with radix sort. For the purpose of demonstrating the possible gains,
> > I've only replaced the signed variant for now. I've also tried using
> > simplehash.h for deduplicating followed by a sort_template.h-based sort.
> > But that was slower.
>
> Ok.
>
> > v1-0007-Faster-qunique-comparator.patch: qunique() doesn't require a
> > full sort comparator (-1 = less, 0 = equal, 1 = greater) but only a
> > equal/unequal comparator (e.g. 0 = equal and 1 = unequal). The same
> > optimization can be done in plenty of other places in our code base.
> > Likely, in most of them the gains are insignificant.
>
> Makes sense. I'm a little disappointed the compiler won't do that
> optimization for us..
>
> Perhaps we should introduce a new qunique_eq() function with a different
> callback signature:
>
> /* like qunique(), but the callback function returns true/false rather
> than int */
> static inline size_t
> qunique_eq(void *array, size_t elements, size_t width,
>                 bool (*equal) (const void *, const void *))
>
> > v1-0008-Add-ASCII-fastpath-to-generate_trgm_only.patch: Typically lots
> > of text is actually ASCII. Hence, we provide a fast path for this case
> > which is exercised if the MSB of the current character is unset.
>
> This uses pg_ascii_tolower() when for ASCII characters when built with
> the IGNORECASE. I don't think that's correct, if the proper collation
> would do something more complicated for than what pg_ascii_tolower() does.
>
> Did you measure how big is the impact from each individual patch?
> Patches 1 and 2 seem pretty much ready to be committed, but I wonder if
> they make any difference on their own.
>
> - Heikki
>
>
>


Hi!
patches 0003, 0004 & 0008 applies with whitespace errors.


reshke@yezzey-cbdb-bench:~/pgpure$ git am v1-0003-Use-sort_template.h.patch
Applying: Use sort_template.h
.git/rebase-apply/patch:66: trailing whitespace.

warning: 1 line adds whitespace errors.
reshke@yezzey-cbdb-bench:~/pgpure$ git am
v1-0004-Avoid-dedup-and-sort-in-ginExtractEntries.patch
Applying: Avoid dedup and sort in ginExtractEntries
.git/rebase-apply/patch:30: trailing whitespace.
{
warning: 1 line adds whitespace errors.
reshke@yezzey-cbdb-bench:~/pgpure$ git am
v1-0008-Add-ASCII-fastpath-to-generate_trgm_only.patch
Applying: Add ASCII fastpath to generate_trgm_only()
.git/rebase-apply/patch:101: trailing whitespace.
else
warning: 1 line adds whitespace errors.


I did run benchmarks of my VM using your data. v1-0001 solely improves
runtime by 4-5%. v2-0002 does not show runtime improvement for me.
With parallel GIN build, performance gains are 2-3 % for 2 workers and
not noticeable after that.

I will try to run some more benchmarks on this.

-- 
Best regards,
Kirill Reshke

Re: Reduce build times of pg_trgm GIN indexes

David Geier <geidav.pg@gmail.com> — 2026-01-09T12:06:42Z

Hi Heikki!

Thanks for looking at the patch set.

On 06.01.2026 18:00, Heikki Linnakangas wrote:
> On 05/01/2026 17:01, David Geier wrote:
>> - v1-0002-Optimized-comparison-functions.patch: Use FunctionCallInvoke()
>> instead of FunctionCall2Coll(). This saves a bunch of per-comparison
>> setup code, such as calling InitFunctionCallInfoData().
> 
> You lose the check for NULL result with this. That's probably still
> worth checking.

It seems like existing code where all args are not null, has that safety
check. Added it for consistency.

>> - v1-0004-Avoid-dedup-and-sort-in-ginExtractEntries.patch
>> ginExtractEntries() deduplicates and sorts the entries returned from the
>> extract value function. In case of pg_trgm, that is completely redundant
>> because the trigrams are already deduplicated and sorted. The current
>> version of this patch is just to demonstrate the potential. We need to
>> think about what we want here. Ideally, we would require the extraction
>> function to provide the entries deduplicated and sorted. Alternatively,
>> we could indicate to ginExtractEntries() if the entries are already
>> deduplicated and sorted. If we don't want to alter the signature of the
>> extract value function, we could e.g. use the MSB of the nentries
>> argument.
> 
> Yeah, this seems wrong as it is. You're assuming that if the extract
> function returns nullFlags == NULL, the array is already sorted and
> deduped.

As said, that was just for demonstration purposes of the possible gains.
I've changed the code now such that the extractValue function of the GIN
index can indicate via the third argument uniqueAndSorted, if the
returned keys are already unique and sorted.

Unfortunately, it seems like this patch regresses performance. See
measurements below. I haven't had the time to investigate why that is.
It's pretty counter intuitive, given that this patch effectively only
removes code. Maybe you could re-test patch 0004 and share your runtimes?

>> v1-0007-Faster-qunique-comparator.patch: qunique() doesn't require a
>> full sort comparator (-1 = less, 0 = equal, 1 = greater) but only a
>> equal/unequal comparator (e.g. 0 = equal and 1 = unequal). The same
>> optimization can be done in plenty of other places in our code base.
>> Likely, in most of them the gains are insignificant.
> 
> Makes sense. I'm a little disappointed the compiler won't do that
> optimization for us..

I thought the same.

> 
> Perhaps we should introduce a new qunique_eq() function with a different
> callback signature:
> 
> /* like qunique(), but the callback function returns true/false rather
> than int */
> static inline size_t
> qunique_eq(void *array, size_t elements, size_t width,
>         bool (*equal) (const void *, const void *))
> 

I would prefer to change qunique() instead. That would enforce using an
adequate comparison function from the get go. There are only ~15 calls
to qunique(). So refactoring this should also be a fairly small patch. I
can do that if there's agreement for that approach.

>> v1-0008-Add-ASCII-fastpath-to-generate_trgm_only.patch: Typically lots
>> of text is actually ASCII. Hence, we provide a fast path for this case
>> which is exercised if the MSB of the current character is unset.
> 
> This uses pg_ascii_tolower() when for ASCII characters when built with
> the IGNORECASE. I don't think that's correct, if the proper collation
> would do something more complicated for than what pg_ascii_tolower() does.

Oh, that's evil. I had tested that specifically. But it only worked
because the code in master uses str_tolower() with
DEFAULT_COLLATION_OID. So using a different locale like in the following
example does something different than when creating a database with the
same locale.

postgres=# select lower('III' COLLATE "tr_TR");
 lower
-------
 ııı

postgres=# select show_trgm('III' COLLATE "tr_TR");
        show_trgm
-------------------------
 {"  i"," ii","ii ",iii}
(1 row)

But when using tr_TR as default locale of the database the following
happens:

postgres=# select lower('III' COLLATE "tr_TR");
 lower
-------
 ııı

postgres=# select show_trgm('III');sü
               show_trgm
---------------------------------------
 {0xbbd8dd,0xf26fab,0xf31e1a,0x2af4f1}

I'm wondering if that's intentional to begin with. Shouldn't the code
instead pass PG_GET_COLLATION() to str_tolower()? Might require some
research to see how other index types handle locales.

Coming back to the original problem: the lengthy comment at the top of
pg_locale_libc.c, suggests that in some cases ASCII characters are
handled the pg_ascii_tolower() way for the default locale. See for
example tolower_libc_mb(). So a character by character conversion using
that function will yield a different result than strlower_libc_mb(). I'm
wondering why that is.

Anyways, we could limit the optimization to only kick in when the used
locale follows the same rules as pg_ascii_tolower(). We could test that
when creating the locale and store that info in pg_locale_struct.

Thoughts?

> Did you measure how big is the impact from each individual patch?
> Patches 1 and 2 seem pretty much ready to be committed, but I wonder if
> they make any difference on their own.

Here is the impact of each patch. I ran again CREATE INDEX three times
and took the fastest run. The run of each patch includes all previous
patches as well. For example, the timings for patch 0003 were measured
with a binary that also had patch 0002 and 0001 applied. To get the
impact of each patch in isolation, the delta to the previous run was taken.

Code                                | movies |delta  | lineitem | delta
------------------------------------|--------|-------|------------------
master                              | 10,311 | 0     | 256,986  | 0
v1-0001-Inline-ginCompareAttEntries |  9,694 | 617   | 239,778  | 17,208
v1-0002-Optimized-comparison-func   |  9,510 | 184   | 238,094  |  1,684
v1-0003-Use-sort_template.h         |  8,661 | 849   | 231,190  |  6,904
v1-0004-Avoid-dedup-and-sort-in     |  9,305 | -644  | 232,472  | -1,282
v1-0005-Make-btint4cmp-branchless   |  8,240 | 1,065 | 228,387  |  4,085
v1-0006-Use-radix-sort              |  6,976 | 1,264 | 207,687  | 20,700
v1-0007-Faster-qunique-comparator   |  5,911 | 1,065 | 203,744  |  3,943
v1-0008-Add-ASCII-fastpath          |  3,409 | 2,502 | 161,469  | 42,275

Attached is v2 of the patch set with the aforementioned changes. I've
also fixed the white space errors in 0003, 0004 and 0008, as reported by
Kirill.

--
David Geier

Re: Reduce build times of pg_trgm GIN indexes

David Geier <geidav.pg@gmail.com> — 2026-01-09T12:10:38Z

Hi!

> Hi!
> patches 0003, 0004 & 0008 applies with whitespace errors.
> 
I've fixed the white space errors. See v2 of the patch set in [1].

> I did run benchmarks of my VM using your data. v1-0001 solely improves
> runtime by 4-5%. v2-0002 does not show runtime improvement for me.
> With parallel GIN build, performance gains are 2-3 % for 2 workers and
> not noticeable after that.
> 
> I will try to run some more benchmarks on this.

Thanks. I've also included the delta for each patch in [1]. I would be
curious what you measure, especially for patch 0004, where I curiously
measured a regression.

[1]
https://www.postgresql.org/message-id/e5dd01c6-c469-405d-aea2-feca0b2dc34d%40gmail.com

--
David Geier

Re: Reduce build times of pg_trgm GIN indexes

Heikki Linnakangas <hlinnaka@iki.fi> — 2026-01-09T18:36:26Z

On 09/01/2026 14:06, David Geier wrote:
> On 06.01.2026 18:00, Heikki Linnakangas wrote:
>> On 05/01/2026 17:01, David Geier wrote:
>>> - v1-0002-Optimized-comparison-functions.patch: Use FunctionCallInvoke()
>>> instead of FunctionCall2Coll(). This saves a bunch of per-comparison
>>> setup code, such as calling InitFunctionCallInfoData().
>>
>> You lose the check for NULL result with this. That's probably still
>> worth checking.
> 
> It seems like existing code where all args are not null, has that safety
> check. Added it for consistency.
> 
>>> - v1-0004-Avoid-dedup-and-sort-in-ginExtractEntries.patch
>>> ginExtractEntries() deduplicates and sorts the entries returned from the
>>> extract value function. In case of pg_trgm, that is completely redundant
>>> because the trigrams are already deduplicated and sorted. The current
>>> version of this patch is just to demonstrate the potential. We need to
>>> think about what we want here. Ideally, we would require the extraction
>>> function to provide the entries deduplicated and sorted. Alternatively,
>>> we could indicate to ginExtractEntries() if the entries are already
>>> deduplicated and sorted. If we don't want to alter the signature of the
>>> extract value function, we could e.g. use the MSB of the nentries
>>> argument.
>>
>> Yeah, this seems wrong as it is. You're assuming that if the extract
>> function returns nullFlags == NULL, the array is already sorted and
>> deduped.
> 
> As said, that was just for demonstration purposes of the possible gains.
> I've changed the code now such that the extractValue function of the GIN
> index can indicate via the third argument uniqueAndSorted, if the
> returned keys are already unique and sorted.
> 
> Unfortunately, it seems like this patch regresses performance. See
> measurements below. I haven't had the time to investigate why that is.
> It's pretty counter intuitive, given that this patch effectively only
> removes code. Maybe you could re-test patch 0004 and share your runtimes?

Looking at 0001 and 0004 patches and ginExtractEntries(), the way 
ginExtractEntries() handles NULLs looks a little inefficient. It treats 
NULLs as proper entries, passing them through qsort() for deduplication 
and comparing them with cmpEntries(). But the end result is always that 
if the opclass's extractValueFn() function returned any NULLs, then 
there's exctly one GIN_CAT_NULL_KEY as the last entry of the result 
array. Surely we could be smarter about how we accomplish that. Your 
0004 patch eliminates the deduplication overhead altogether, which is 
great of course, but the point remains for when we still need the 
deduplication.

Attached is an attempt at that. It avoids the null-checks in 
cmpEntries(), saving a few cycles. That's drowned in noise with your 
test cases, but with the attached test case with int arrays, I'm seeing 
a 1-2 % gain. That's not much, but I think it's still worth doing 
because it makes the code a little simpler too, IMHO. (I didn't test it 
together with the rest of your patches.)

>> Perhaps we should introduce a new qunique_eq() function with a different
>> callback signature:
>>
>> /* like qunique(), but the callback function returns true/false rather
>> than int */
>> static inline size_t
>> qunique_eq(void *array, size_t elements, size_t width,
>>          bool (*equal) (const void *, const void *))
>>
> 
> I would prefer to change qunique() instead. That would enforce using an
> adequate comparison function from the get go. There are only ~15 calls
> to qunique(). So refactoring this should also be a fairly small patch. I
> can do that if there's agreement for that approach.

Works for me.

At quick glance, most if not all of the qunique() calls call qsort() 
just before qunique(). I wonder if we should have a single "sort and 
deduplicate" function, instead. It could perhaps do some deduplication 
"on the go", or other optimizations.

>> Did you measure how big is the impact from each individual patch?
>> Patches 1 and 2 seem pretty much ready to be committed, but I wonder if
>> they make any difference on their own.
> 
> Here is the impact of each patch. I ran again CREATE INDEX three times
> and took the fastest run. The run of each patch includes all previous
> patches as well. For example, the timings for patch 0003 were measured
> with a binary that also had patch 0002 and 0001 applied. To get the
> impact of each patch in isolation, the delta to the previous run was taken.
> 
> Code                                | movies |delta  | lineitem | delta
> ------------------------------------|--------|-------|------------------
> master                              | 10,311 | 0     | 256,986  | 0
> v1-0001-Inline-ginCompareAttEntries |  9,694 | 617   | 239,778  | 17,208
> v1-0002-Optimized-comparison-func   |  9,510 | 184   | 238,094  |  1,684
> v1-0003-Use-sort_template.h         |  8,661 | 849   | 231,190  |  6,904
> v1-0004-Avoid-dedup-and-sort-in     |  9,305 | -644  | 232,472  | -1,282
> v1-0005-Make-btint4cmp-branchless   |  8,240 | 1,065 | 228,387  |  4,085
> v1-0006-Use-radix-sort              |  6,976 | 1,264 | 207,687  | 20,700
> v1-0007-Faster-qunique-comparator   |  5,911 | 1,065 | 203,744  |  3,943
> v1-0008-Add-ASCII-fastpath          |  3,409 | 2,502 | 161,469  | 42,275
> 
> Attached is v2 of the patch set with the aforementioned changes. I've
> also fixed the white space errors in 0003, 0004 and 0008, as reported by
> Kirill.

Thanks, I pushed patch 0001 now, that's a simple and clear win.

- Heikki

Re: Reduce build times of pg_trgm GIN indexes

David Geier <geidav.pg@gmail.com> — 2026-01-09T21:02:01Z

On 09.01.2026 19:36, Heikki Linnakangas wrote:
>>>> - v1-0004-Avoid-dedup-and-sort-in-ginExtractEntries.patch
>>>> ginExtractEntries() deduplicates and sorts the entries returned from
>>>> the
>>>> extract value function. In case of pg_trgm, that is completely
>>>> redundant
>>>> because the trigrams are already deduplicated and sorted. The current
>>>> version of this patch is just to demonstrate the potential. We need to
>>>> think about what we want here. Ideally, we would require the extraction
>>>> function to provide the entries deduplicated and sorted. Alternatively,
>>>> we could indicate to ginExtractEntries() if the entries are already
>>>> deduplicated and sorted. If we don't want to alter the signature of the
>>>> extract value function, we could e.g. use the MSB of the nentries
>>>> argument.
>>>
>>> Yeah, this seems wrong as it is. You're assuming that if the extract
>>> function returns nullFlags == NULL, the array is already sorted and
>>> deduped.
>>
>> As said, that was just for demonstration purposes of the possible gains.
>> I've changed the code now such that the extractValue function of the GIN
>> index can indicate via the third argument uniqueAndSorted, if the
>> returned keys are already unique and sorted.
>>
>> Unfortunately, it seems like this patch regresses performance. See
>> measurements below. I haven't had the time to investigate why that is.
>> It's pretty counter intuitive, given that this patch effectively only
>> removes code. Maybe you could re-test patch 0004 and share your runtimes?
> 
> Looking at 0001 and 0004 patches and ginExtractEntries(), the way
> ginExtractEntries() handles NULLs looks a little inefficient. It treats
> NULLs as proper entries, passing them through qsort() for deduplication
> and comparing them with cmpEntries(). But the end result is always that
> if the opclass's extractValueFn() function returned any NULLs, then
> there's exctly one GIN_CAT_NULL_KEY as the last entry of the result
> array. Surely we could be smarter about how we accomplish that. Your
> 0004 patch eliminates the deduplication overhead altogether, which is
> great of course, but the point remains for when we still need the
> deduplication.
Good observation. I like this idea. I've focused on pg_trgm but making
this code faster is certainly useful.

Given that doing the sort on pre-sorted input apparently doesn't add
measurable overhead, according to my benchmark results, we can apply
your patch and leave mine out for the moment being.

That's btw. also the reason for why 0002 doesn't show much gain: when
the data is pre-sorted, cmpEntries() is not called as much.
> 
> Attached is an attempt at that. It avoids the null-checks in
> cmpEntries(), saving a few cycles. That's drowned in noise with your
> test cases, but with the attached test case with int arrays, I'm seeing
> a 1-2 % gain. That's not much, but I think it's still worth doing
> because it makes the code a little simpler too, IMHO. (I didn't test it
> together with the rest of your patches.)

Performance is death by a thousand cuts and that's definitely the case
for the GIN index code. I'm all for putting in these small improvements
because they'll add up and what's now 2% can be 10% once other
optimization are in.

I took a look at your patch. Overall looks good to me. Just a few comments:

1) You should be able to create the categories array without the need
for the subsequent for loop as follows:

StaticAssertStmt(GIN_CAT_NORM_KEY == 0, "Assuming GIN_CAT_NORM_KEY=0");
*categories = palloc0_array(GinNullCategory, (nentries + (hasNull ? 1 : 0));

2) Your test case seems sub-optimal to show the gains. The arrays don't
contain any NULL values and are also already sorted. Or I'm missing
something.

3) Could you try your patch in conjunction with 0002 on data that is not
pre-sorted and then check if 0002 has more impact? That way cmpEntries()
should be called much more often.

4) Have you checked if there are regression tests that exercise this
code? If not, how about adding some?

>>> Perhaps we should introduce a new qunique_eq() function with a different
>>> callback signature:
>>>
>>> /* like qunique(), but the callback function returns true/false rather
>>> than int */
>>> static inline size_t
>>> qunique_eq(void *array, size_t elements, size_t width,
>>>          bool (*equal) (const void *, const void *))
>>>
>>
>> I would prefer to change qunique() instead. That would enforce using an
>> adequate comparison function from the get go. There are only ~15 calls
>> to qunique(). So refactoring this should also be a fairly small patch. I
>> can do that if there's agreement for that approach.
> 
> Works for me.
> 
> At quick glance, most if not all of the qunique() calls call qsort()
> just before qunique(). I wonder if we should have a single "sort and
> deduplicate" function, instead. It could perhaps do some deduplication
> "on the go", or other optimizations.

If it's just for deduplication purposes and the data doesn't have to end
up sorted, something based on a hash map should be even faster. How
about we start with changing the qunique() comparator signature and as a
2nd step take a closer look at how to go about providing a function that
does it in one go?

If you agree, I'll share a patch here next week.

>>> Did you measure how big is the impact from each individual patch?
>>> Patches 1 and 2 seem pretty much ready to be committed, but I wonder if
>>> they make any difference on their own.
>>
>> Here is the impact of each patch. I ran again CREATE INDEX three times
>> and took the fastest run. The run of each patch includes all previous
>> patches as well. For example, the timings for patch 0003 were measured
>> with a binary that also had patch 0002 and 0001 applied. To get the
>> impact of each patch in isolation, the delta to the previous run was
>> taken.
>>
>> Code                                | movies |delta  | lineitem | delta
>> ------------------------------------|--------|-------|------------------
>> master                              | 10,311 | 0     | 256,986  | 0
>> v1-0001-Inline-ginCompareAttEntries |  9,694 | 617   | 239,778  | 17,208
>> v1-0002-Optimized-comparison-func   |  9,510 | 184   | 238,094  |  1,684
>> v1-0003-Use-sort_template.h         |  8,661 | 849   | 231,190  |  6,904
>> v1-0004-Avoid-dedup-and-sort-in     |  9,305 | -644  | 232,472  | -1,282
>> v1-0005-Make-btint4cmp-branchless   |  8,240 | 1,065 | 228,387  |  4,085
>> v1-0006-Use-radix-sort              |  6,976 | 1,264 | 207,687  | 20,700
>> v1-0007-Faster-qunique-comparator   |  5,911 | 1,065 | 203,744  |  3,943
>> v1-0008-Add-ASCII-fastpath          |  3,409 | 2,502 | 161,469  | 42,275
>>
>> Attached is v2 of the patch set with the aforementioned changes. I've
>> also fixed the white space errors in 0003, 0004 and 0008, as reported by
>> Kirill.
> 
> Thanks, I pushed patch 0001 now, that's a simple and clear win.
Great. Thanks.

What about the other patches? 0003 and 0007 are also pretty simple and
IMHO uncontroversial while giving decent savings.

For 0006 I would make the code also work for char being unsigned. That's
still missing.

Any thoughts about 0008 and my findings regarding the to lower-case
conversion for ASCII? Adding to pg_locale_struct if it's save to use
ASCII-style tolower should be straight forward and then the code should
be correct.

--
David Geier

Re: Reduce build times of pg_trgm GIN indexes

Heikki Linnakangas <hlinnaka@iki.fi> — 2026-01-12T22:10:03Z

On 09/01/2026 14:06, David Geier wrote:
> On 06.01.2026 18:00, Heikki Linnakangas wrote:
>> On 05/01/2026 17:01, David Geier wrote:
>>> v1-0008-Add-ASCII-fastpath-to-generate_trgm_only.patch: Typically lots
>>> of text is actually ASCII. Hence, we provide a fast path for this case
>>> which is exercised if the MSB of the current character is unset.
>>
>> This uses pg_ascii_tolower() when for ASCII characters when built with
>> the IGNORECASE. I don't think that's correct, if the proper collation
>> would do something more complicated for than what pg_ascii_tolower() does.
> 
> Oh, that's evil. I had tested that specifically. But it only worked
> because the code in master uses str_tolower() with
> DEFAULT_COLLATION_OID. So using a different locale like in the following
> example does something different than when creating a database with the
> same locale.
> 
> postgres=# select lower('III' COLLATE "tr_TR");
>   lower
> -------
>   ııı
> 
> postgres=# select show_trgm('III' COLLATE "tr_TR");
>          show_trgm
> -------------------------
>   {"  i"," ii","ii ",iii}
> (1 row)
> 
> But when using tr_TR as default locale of the database the following
> happens:
> 
> postgres=# select lower('III' COLLATE "tr_TR");
>   lower
> -------
>   ııı
> 
> postgres=# select show_trgm('III');sü
>                 show_trgm
> ---------------------------------------
>   {0xbbd8dd,0xf26fab,0xf31e1a,0x2af4f1}
> 
> I'm wondering if that's intentional to begin with. Shouldn't the code
> instead pass PG_GET_COLLATION() to str_tolower()? Might require some
> research to see how other index types handle locales.
> 
> Coming back to the original problem: the lengthy comment at the top of
> pg_locale_libc.c, suggests that in some cases ASCII characters are
> handled the pg_ascii_tolower() way for the default locale. See for
> example tolower_libc_mb(). So a character by character conversion using
> that function will yield a different result than strlower_libc_mb(). I'm
> wondering why that is.

Hmm, yeah, that feels funny. The trigram code predates per-column 
collation support, so I guess we never really thought through how it 
should interact with COLLATE clauses.

> Anyways, we could limit the optimization to only kick in when the used
> locale follows the same rules as pg_ascii_tolower(). We could test that
> when creating the locale and store that info in pg_locale_struct.

I think that's only possible for libc locales, which operate one 
character at a time. In ICU locales, lower-casing a character can depend 
on the surrounding characters, so you cannot just test the conversion of 
every ascii character individually. It would make sense for libc locales 
though, and I hope the ICU functions are a little faster anyway.

Although, we probably should be using case-folding rather than 
lower-casing with ICU locales anyway. Case-folding is designed for 
string matching. It'd be a backwards-compatibility breaking change, though.

- Heikki

Re: Reduce build times of pg_trgm GIN indexes

David Geier <geidav.pg@gmail.com> — 2026-01-14T12:27:05Z

Hi Heikki!

On 09.01.2026 22:02, David Geier wrote:
> Given that doing the sort on pre-sorted input apparently doesn't add
> measurable overhead, according to my benchmark results, we can apply
> your patch and leave mine out for the moment being.

I've removed my patch from the patch set in favor of your patch. I've
adapted your patch slightly as follows:

- I replaced the custom for-loop by qunique()
- I switched to sort_template.h which gives a nice speedup as it can do
some things more efficiently now where the entries are simple Datums.
- I use palloc0_array() to initialize the array to GIN_CAT_NORM_KEY in
one go.

Your patch together with my changes gives a 20% speedup on a table with
arrays of 1000 elements and 10% NULLs. See attached test script.

> That's btw. also the reason for why 0002 doesn't show much gain: when
> the data is pre-sorted, cmpEntries() is not called as much.

This turned out to be not the case. I tested 0002 with the attached
script but that neither showed any significant improvements. It's still
curious to me because cmpEntries() is called hundreds of millions of
times and the disassembly shows that the optimized function indeed
directly calls the operator rather than having the indirection via
FunctionCall2Coll().

Anyways, I've removed the patch from the patch set for the moment being.

>>> I would prefer to change qunique() instead. That would enforce using an
>>> adequate comparison function from the get go. There are only ~15 calls
>>> to qunique(). So refactoring this should also be a fairly small patch. I
>>> can do that if there's agreement for that approach.
>>
>> Works for me.
>>
>> At quick glance, most if not all of the qunique() calls call qsort()
>> just before qunique(). I wonder if we should have a single "sort and
>> deduplicate" function, instead. It could perhaps do some deduplication
>> "on the go", or other optimizations.
> 
> If it's just for deduplication purposes and the data doesn't have to end
> up sorted, something based on a hash map should be even faster. How
> about we start with changing the qunique() comparator signature and as a
> 2nd step take a closer look at how to go about providing a function that
> does it in one go?

Thinking about this some more: ideally we have two functions: something
like deduplicateArray() and sortAndDeduplicateArray(). We could
initially implement deduplicateArray() on top of
sortAndDeduplicateArray(). If we ever find a case that needs
optimization, and doesn't require the data to actually end up sorted, we
can implement deduplicateArray() e.g. on top of simplehash.h.

I'll draft a patch and submit it in a separate thread.

> What about the other patches? 0003 and 0007 are also pretty simple and
> IMHO uncontroversial while giving decent savings.

I've reordered the patches such that the ones that I think are
uncontroversial, small and ready to be committed are at the beginning
(patches 0001 - 0004). The radix sort and ASCII fast-path patches come
last (0005 and 0006). I would like to first concentrate on getting 0001
- 0004 in and then get back to 0005 and 0006.

I remeasured the savings of 0001 - 0004, which comes on top of the
already committed patch that inlined the comparison function, which gave
another ~5%:

Data set            | Patched (ms) | Master (ms)  | Speedup
--------------------|--------------|--------------|----------
movies(plot)        |   8,058      |  10,311      | 1.27x
lineitem(l_comment) | 223,233      | 256,986      | 1.19x

--
David Geier

Re: Reduce build times of pg_trgm GIN indexes

David Geier <geidav.pg@gmail.com> — 2026-01-21T15:45:06Z

>> Oh, that's evil. I had tested that specifically. But it only worked
>> because the code in master uses str_tolower() with
>> DEFAULT_COLLATION_OID. So using a different locale like in the following
>> example does something different than when creating a database with the
>> same locale.
>>
>> postgres=# select lower('III' COLLATE "tr_TR");
>>   lower
>> -------
>>   ııı
>>
>> postgres=# select show_trgm('III' COLLATE "tr_TR");
>>          show_trgm
>> -------------------------
>>   {"  i"," ii","ii ",iii}
>> (1 row)
>>
>> But when using tr_TR as default locale of the database the following
>> happens:
>>
>> postgres=# select lower('III' COLLATE "tr_TR");
>>   lower
>> -------
>>   ııı
>>
>> postgres=# select show_trgm('III');sü
>>                 show_trgm
>> ---------------------------------------
>>   {0xbbd8dd,0xf26fab,0xf31e1a,0x2af4f1}
>>
>> I'm wondering if that's intentional to begin with. Shouldn't the code
>> instead pass PG_GET_COLLATION() to str_tolower()? Might require some
>> research to see how other index types handle locales.
>>
>> Coming back to the original problem: the lengthy comment at the top of
>> pg_locale_libc.c, suggests that in some cases ASCII characters are
>> handled the pg_ascii_tolower() way for the default locale. See for
>> example tolower_libc_mb(). So a character by character conversion using
>> that function will yield a different result than strlower_libc_mb(). I'm
>> wondering why that is.
> 
> Hmm, yeah, that feels funny. The trigram code predates per-column
> collation support, so I guess we never really thought through how it
> should interact with COLLATE clauses.

I've written a patch to fix that. See [1].

>> Anyways, we could limit the optimization to only kick in when the used
>> locale follows the same rules as pg_ascii_tolower(). We could test that
>> when creating the locale and store that info in pg_locale_struct.
> 
> I think that's only possible for libc locales, which operate one
> character at a time. In ICU locales, lower-casing a character can depend
> on the surrounding characters, so you cannot just test the conversion of
> every ascii character individually. It would make sense for libc locales
> though, and I hope the ICU functions are a little faster anyway.
> 
> Although, we probably should be using case-folding rather than lower-
> casing with ICU locales anyway. Case-folding is designed for string
> matching. It'd be a backwards-compatibility breaking change, though.

Oh, I wasn't ware of that. Doing it only for libc locales seems still
useful.

Good point with the casefolding. I'll look into that.

How do we usually go about such backwards-compatibility breaking
changes? Could we have pg_upgrade reindex all GIN indexes? Would that be
acceptable?

[1]
https://www.postgresql.org/message-id/flat/db087c3e-230e-4119-8a03-8b5d74956bc2%40gmail.com

--
David Geier

Re: Reduce build times of pg_trgm GIN indexes

Matthias van de Meent <boekewurm+postgres@gmail.com> — 2026-01-21T20:50:54Z

On Wed, 21 Jan 2026 at 16:45, David Geier <geidav.pg@gmail.com> wrote:
>
> How do we usually go about such backwards-compatibility breaking
> changes?

When it concerns a bug, we mention the change in the release notes
with a warning to reindex affected indexes to be sure no known
corruption remains. See e.g. the final entry in the PG18 release
notes' migration section here:
https://www.postgresql.org/docs/18/release-18.html#RELEASE-18-MIGRATION.

> Could we have pg_upgrade reindex all GIN indexes? Would that be
> acceptable?

No. We'd handle this like any other collation/opclass fixes; we ask
users to reindex their indexes in their own time after they've
upgraded their cluster. Note that in this case it concerns an issue
with just one GIN opclass, not all GIN indexes; so even if we were to
address this in pg_upgrade it wouldn't be a correct choice to reindex
every GIN index, as only a subset of those would be affected by this
issue.

Generally speaking, pg_upgrade doesn't concern itself with the
validity of the data structures that are described by the catalogs
that it upgrades, it only concerns itself with that it correctly
transcribes the catalogs from one version to another, and that the
data files of the old cluster are transfered correctly without
changes.

Kind regards,

Matthias van de Meent
Databricks (https://www.databricks.com)

Re: Reduce build times of pg_trgm GIN indexes

David Geier <geidav.pg@gmail.com> — 2026-01-23T10:18:56Z

Hi Matthias,

On 21.01.2026 21:50, Matthias van de Meent wrote:
> On Wed, 21 Jan 2026 at 16:45, David Geier <geidav.pg@gmail.com> wrote:
>>
>> How do we usually go about such backwards-compatibility breaking
>> changes?
> 
> When it concerns a bug, we mention the change in the release notes
> with a warning to reindex affected indexes to be sure no known
> corruption remains. See e.g. the final entry in the PG18 release
> notes' migration section here:
> https://www.postgresql.org/docs/18/release-18.html#RELEASE-18-MIGRATION.
> 
>> Could we have pg_upgrade reindex all GIN indexes? Would that be
>> acceptable?
> 
> No. We'd handle this like any other collation/opclass fixes; we ask
> users to reindex their indexes in their own time after they've
> upgraded their cluster. Note that in this case it concerns an issue
> with just one GIN opclass, not all GIN indexes; so even if we were to
> address this in pg_upgrade it wouldn't be a correct choice to reindex
> every GIN index, as only a subset of those would be affected by this
> issue.
> 
> Generally speaking, pg_upgrade doesn't concern itself with the
> validity of the data structures that are described by the catalogs
> that it upgrades, it only concerns itself with that it correctly
> transcribes the catalogs from one version to another, and that the
> data files of the old cluster are transfered correctly without
> changes.

Thanks for the clarifications and the link to the release notes. That's
very helpful. Then I know how to move on and will update the patch
accordingly.

--
David Geier

Re: Reduce build times of pg_trgm GIN indexes

David Geier <geidav.pg@gmail.com> — 2026-03-02T12:17:56Z

On 23.01.2026 11:18, David Geier wrote:
> Hi Matthias,
> 
> On 21.01.2026 21:50, Matthias van de Meent wrote:
>> On Wed, 21 Jan 2026 at 16:45, David Geier <geidav.pg@gmail.com> wrote:
>>>
>>> How do we usually go about such backwards-compatibility breaking
>>> changes?
>>
>> When it concerns a bug, we mention the change in the release notes
>> with a warning to reindex affected indexes to be sure no known
>> corruption remains. See e.g. the final entry in the PG18 release
>> notes' migration section here:
>> https://www.postgresql.org/docs/18/release-18.html#RELEASE-18-MIGRATION.
>>
>>> Could we have pg_upgrade reindex all GIN indexes? Would that be
>>> acceptable?
>>
>> No. We'd handle this like any other collation/opclass fixes; we ask
>> users to reindex their indexes in their own time after they've
>> upgraded their cluster. Note that in this case it concerns an issue
>> with just one GIN opclass, not all GIN indexes; so even if we were to
>> address this in pg_upgrade it wouldn't be a correct choice to reindex
>> every GIN index, as only a subset of those would be affected by this
>> issue.
>>
>> Generally speaking, pg_upgrade doesn't concern itself with the
>> validity of the data structures that are described by the catalogs
>> that it upgrades, it only concerns itself with that it correctly
>> transcribes the catalogs from one version to another, and that the
>> data files of the old cluster are transfered correctly without
>> changes.
> 
> Thanks for the clarifications and the link to the release notes. That's
> very helpful. Then I know how to move on and will update the patch
> accordingly.

Attached are the patches rebased on latest master.

I've removed the ASCII fast-path patch 0006 as it turned out to be more
complicated to make work than expected.

I kept the radix sort patch because it gives a decent speedup but I
would like to focus for now on getting patches 0001 - 0004 merged.
They're all simple and, the way I see it, uncontroversial.

I remeasured the savings of 0001 - 0004, which comes on top of the
already committed patch that inlined the comparison function, which gave
another ~5%:

Data set            | Patched (ms) | Master (ms)  | Speedup
--------------------|--------------|--------------|----------
movies(plot)        |   8,058      |  10,311      | 1.27x
lineitem(l_comment) | 223,233      | 256,986      | 1.19x

I've also registered the change at the commit fest, see
https://commitfest.postgresql.org/patch/6418/.

--
David Geier

Re: Reduce build times of pg_trgm GIN indexes

David Geier <geidav.pg@gmail.com> — 2026-03-03T17:31:51Z

> Attached are the patches rebased on latest master.
> 
> I've removed the ASCII fast-path patch 0006 as it turned out to be more
> complicated to make work than expected.
> 
> I kept the radix sort patch because it gives a decent speedup but I
> would like to focus for now on getting patches 0001 - 0004 merged.
> They're all simple and, the way I see it, uncontroversial.
> 
> I remeasured the savings of 0001 - 0004, which comes on top of the
> already committed patch that inlined the comparison function, which gave
> another ~5%:
> 
> Data set            | Patched (ms) | Master (ms)  | Speedup
> --------------------|--------------|--------------|----------
> movies(plot)        |   8,058      |  10,311      | 1.27x
> lineitem(l_comment) | 223,233      | 256,986      | 1.19x
> 
> I've also registered the change at the commit fest, see
> https://commitfest.postgresql.org/patch/6418/.

Attached is v5 that removes an incorrect assertion from the radix sort code.

--
David Geier

Re: Reduce build times of pg_trgm GIN indexes

Heikki Linnakangas <hlinnaka@iki.fi> — 2026-04-07T11:27:40Z

On 03/03/2026 19:31, David Geier wrote:
>> Attached are the patches rebased on latest master.
>>
>> I've removed the ASCII fast-path patch 0006 as it turned out to be more
>> complicated to make work than expected.
>>
>> I kept the radix sort patch because it gives a decent speedup but I
>> would like to focus for now on getting patches 0001 - 0004 merged.
>> They're all simple and, the way I see it, uncontroversial.
>>
>> I remeasured the savings of 0001 - 0004, which comes on top of the
>> already committed patch that inlined the comparison function, which gave
>> another ~5%:
>>
>> Data set            | Patched (ms) | Master (ms)  | Speedup
>> --------------------|--------------|--------------|----------
>> movies(plot)        |   8,058      |  10,311      | 1.27x
>> lineitem(l_comment) | 223,233      | 256,986      | 1.19x
>>
>> I've also registered the change at the commit fest, see
>> https://commitfest.postgresql.org/patch/6418/.
> 
> Attached is v5 that removes an incorrect assertion from the radix sort code.
>
> v5-0001-Optimize-sort-and-deduplication-in-ginExtractEntr.patch
> v5-0002-Optimize-generate_trgm-with-sort_template.h.patch
> v5-0003-Make-btint4cmp-branchless.patch
> v5-0004-Faster-qunique-comparator-in-generate_trgm.patch
> v5-0005-Optimize-generate_trgm-with-radix-sort.patch

Pushed 0001 as commit 6f5ad00ab7.

I squashed 0002 and 0004 into one commit, and did some more refactoring: 
I created a trigram_qsort() helper function that calls the signed or 
unsigned variant, so that that logic doesn't need to be duplicated in 
the callers. For symmetry, I also added a trigram_qunique() helper 
function which just calls qunique() with the new, faster CMPTRGM_EQ 
comparator. Pushed these as commit 9f3755ea07.

Patch 0003 gives me pause. It's a tiny patch:

> @@ -203,12 +204,7 @@ btint4cmp(PG_FUNCTION_ARGS)
>  	int32		a = PG_GETARG_INT32(0);
>  	int32		b = PG_GETARG_INT32(1);
>  
> -	if (a > b)
> -		PG_RETURN_INT32(A_GREATER_THAN_B);
> -	else if (a == b)
> -		PG_RETURN_INT32(0);
> -	else
> -		PG_RETURN_INT32(A_LESS_THAN_B);
> +	PG_RETURN_INT32(pg_cmp_s32(a, b));
>  }

But the comments on the pg_cmp functions say:

>  * NB: If the comparator function is inlined, some compilers may produce
>  * worse code with these helper functions than with code with the
>  * following form:
>  *
>  *     if (a < b)
>  *         return -1;
>  *     if (a > b)
>  *         return 1;
>  *     return 0;
>  *

So, uh, is that really a universal improvement? Is that comment about 
producing worse code outdated?

- Heikki

Re: Reduce build times of pg_trgm GIN indexes

John Naylor <johncnaylorls@gmail.com> — 2026-04-08T02:15:38Z

On Tue, Apr 7, 2026 at 6:27 PM Heikki Linnakangas <hlinnaka@iki.fi> wrote:
> But the comments on the pg_cmp functions say:
>
> >  * NB: If the comparator function is inlined, some compilers may produce
> >  * worse code with these helper functions than with code with the
> >  * following form:
> >  *
> >  *     if (a < b)
> >  *         return -1;
> >  *     if (a > b)
> >  *         return 1;
> >  *     return 0;
> >  *
>
> So, uh, is that really a universal improvement? Is that comment about
> producing worse code outdated?

No, it's quite recent:

https://www.postgresql.org/message-id/20240212230423.GA3519%40nathanxps13

--
John Naylor
Amazon Web Services

Re: Reduce build times of pg_trgm GIN indexes

Bertrand Drouvot <bertranddrouvot.pg@gmail.com> — 2026-04-09T11:28:24Z

Hi,

On Tue, Apr 07, 2026 at 02:27:40PM +0300, Heikki Linnakangas wrote:
> On 03/03/2026 19:31, David Geier wrote:
> > > Attached are the patches rebased on latest master.
> > > 
> > > I've removed the ASCII fast-path patch 0006 as it turned out to be more
> > > complicated to make work than expected.
> > > 
> > > I kept the radix sort patch because it gives a decent speedup but I
> > > would like to focus for now on getting patches 0001 - 0004 merged.
> > > They're all simple and, the way I see it, uncontroversial.
> > > 
> > > I remeasured the savings of 0001 - 0004, which comes on top of the
> > > already committed patch that inlined the comparison function, which gave
> > > another ~5%:
> > > 
> > > Data set            | Patched (ms) | Master (ms)  | Speedup
> > > --------------------|--------------|--------------|----------
> > > movies(plot)        |   8,058      |  10,311      | 1.27x
> > > lineitem(l_comment) | 223,233      | 256,986      | 1.19x
> > > 
> > > I've also registered the change at the commit fest, see
> > > https://commitfest.postgresql.org/patch/6418/.
> > 
> > Attached is v5 that removes an incorrect assertion from the radix sort code.
> > 
> > v5-0001-Optimize-sort-and-deduplication-in-ginExtractEntr.patch
> > v5-0002-Optimize-generate_trgm-with-sort_template.h.patch
> > v5-0003-Make-btint4cmp-branchless.patch
> > v5-0004-Faster-qunique-comparator-in-generate_trgm.patch
> > v5-0005-Optimize-generate_trgm-with-radix-sort.patch
> 
> Pushed 0001 as commit 6f5ad00ab7.

This commit makes use of StaticAssertStmt() that has been deprecated in 
d50c86e74375. The attached, fixes it.

Regards,

-- 
Bertrand Drouvot
PostgreSQL Contributors Team
RDS Open Source Databases
Amazon Web Services: https://aws.amazon.com

Re: Reduce build times of pg_trgm GIN indexes

Tom Lane <tgl@sss.pgh.pa.us> — 2026-04-12T18:05:02Z

Heikki Linnakangas <hlinnaka@iki.fi> writes:
> Pushed 0001 as commit 6f5ad00ab7.

This commit has caused Coverity to start complaining that
most of ginExtractEntries() is unreachable:

*** CID 1691468:         Control flow issues  (DEADCODE)
/srv/coverity/git/pgsql-git/postgresql/src/backend/access/gin/ginutil.c: 495             in ginExtractEntries()
489     	/*
490     	 * Scan the items for any NULLs.  All NULLs are considered equal, so we
491     	 * just need to check and remember if there are any.  We remove them from
492     	 * the array here, and after deduplication, put back one NULL entry to
493     	 * represent them all.
494     	 */
>>>     CID 1691468:         Control flow issues  (DEADCODE)
>>>     Execution cannot reach this statement: "hasNull = false;".
495     	hasNull = false;
496     	if (nullFlags)
497     	{
498     		int32		numNonNulls = 0;
499     
500     		for (int32 i = 0; i < nentries; i++)

Evidently, it does not realize that the extractValueFn() can change
nentries from its initial value of zero.  I wouldn't be too surprised
if that's related to our casting of the pointer to uintptr_t --- that
may cause it to not see the passed pointer as a potential reference
mechanism.

I would just write that off as Coverity not being smart enough, except
that I'm worried that some compiler might make a similar deduction and
break the function completely.  Was the switch to a local variable
for nentries really a useful win performance-wise?

			regards, tom lane

Re: Reduce build times of pg_trgm GIN indexes

Peter Eisentraut <peter@eisentraut.org> — 2026-04-13T09:41:02Z

On 09.04.26 13:28, Bertrand Drouvot wrote:
> Hi,
> 
> On Tue, Apr 07, 2026 at 02:27:40PM +0300, Heikki Linnakangas wrote:
>> On 03/03/2026 19:31, David Geier wrote:
>>>> Attached are the patches rebased on latest master.
>>>>
>>>> I've removed the ASCII fast-path patch 0006 as it turned out to be more
>>>> complicated to make work than expected.
>>>>
>>>> I kept the radix sort patch because it gives a decent speedup but I
>>>> would like to focus for now on getting patches 0001 - 0004 merged.
>>>> They're all simple and, the way I see it, uncontroversial.
>>>>
>>>> I remeasured the savings of 0001 - 0004, which comes on top of the
>>>> already committed patch that inlined the comparison function, which gave
>>>> another ~5%:
>>>>
>>>> Data set            | Patched (ms) | Master (ms)  | Speedup
>>>> --------------------|--------------|--------------|----------
>>>> movies(plot)        |   8,058      |  10,311      | 1.27x
>>>> lineitem(l_comment) | 223,233      | 256,986      | 1.19x
>>>>
>>>> I've also registered the change at the commit fest, see
>>>> https://commitfest.postgresql.org/patch/6418/.
>>>
>>> Attached is v5 that removes an incorrect assertion from the radix sort code.
>>>
>>> v5-0001-Optimize-sort-and-deduplication-in-ginExtractEntr.patch
>>> v5-0002-Optimize-generate_trgm-with-sort_template.h.patch
>>> v5-0003-Make-btint4cmp-branchless.patch
>>> v5-0004-Faster-qunique-comparator-in-generate_trgm.patch
>>> v5-0005-Optimize-generate_trgm-with-radix-sort.patch
>>
>> Pushed 0001 as commit 6f5ad00ab7.
> 
> This commit makes use of StaticAssertStmt() that has been deprecated in
> d50c86e74375. The attached, fixes it.

I think the position of the static assertion is correct, because it 
refers to the palloc0_array() that follows.  Maybe the comment could be 
a bit clearer, like "using palloc0_array requires GIN_CAT_NORM_KEY==0"?

Re: Reduce build times of pg_trgm GIN indexes

Bertrand Drouvot <bertranddrouvot.pg@gmail.com> — 2026-04-13T11:04:09Z

Hi,

On Mon, Apr 13, 2026 at 11:41:02AM +0200, Peter Eisentraut wrote:
> On 09.04.26 13:28, Bertrand Drouvot wrote:
> > 
> > This commit makes use of StaticAssertStmt() that has been deprecated in
> > d50c86e74375. The attached, fixes it.
> 
> I think the position of the static assertion is correct, because it refers
> to the palloc0_array() that follows.  Maybe the comment could be a bit
> clearer, like "using palloc0_array requires GIN_CAT_NORM_KEY==0"?

Yeah that looks better to not lose the connection with palloc0_array() here.
Done that way in the attached and adding new braces to avoid warning from
-Wdeclaration-after-statement.

Regards,

-- 
Bertrand Drouvot
PostgreSQL Contributors Team
RDS Open Source Databases
Amazon Web Services: https://aws.amazon.com

Re: Reduce build times of pg_trgm GIN indexes

David Geier <geidav.pg@gmail.com> — 2026-04-13T15:03:11Z

Hi!

On 13.04.2026 13:04, Bertrand Drouvot wrote:
> Hi,
> 
> On Mon, Apr 13, 2026 at 11:41:02AM +0200, Peter Eisentraut wrote:
>> On 09.04.26 13:28, Bertrand Drouvot wrote:
>>>
>>> This commit makes use of StaticAssertStmt() that has been deprecated in
>>> d50c86e74375. The attached, fixes it.

I cannot find a comment close to StaticAssertStmt() that says it got
deprecated. Is the goal to completely get rid of StaticAssertStmt()?

>> I think the position of the static assertion is correct, because it refers
>> to the palloc0_array() that follows.  Maybe the comment could be a bit
>> clearer, like "using palloc0_array requires GIN_CAT_NORM_KEY==0"?
> 
> Yeah that looks better to not lose the connection with palloc0_array() here.
> Done that way in the attached and adding new braces to avoid warning from
> -Wdeclaration-after-statement.

Looks good to me.

--
David Geier

Re: Reduce build times of pg_trgm GIN indexes

David Geier <geidav.pg@gmail.com> — 2026-04-13T15:05:30Z

On 08.04.2026 04:15, John Naylor wrote:
> On Tue, Apr 7, 2026 at 6:27 PM Heikki Linnakangas <hlinnaka@iki.fi> wrote:
>> But the comments on the pg_cmp functions say:
>>
>>>  * NB: If the comparator function is inlined, some compilers may produce
>>>  * worse code with these helper functions than with code with the
>>>  * following form:
>>>  *
>>>  *     if (a < b)
>>>  *         return -1;
>>>  *     if (a > b)
>>>  *         return 1;
>>>  *     return 0;
>>>  *
>>
>> So, uh, is that really a universal improvement? Is that comment about
>> producing worse code outdated?

Well spotted. Thanks!

> 
> No, it's quite recent:
> 
> https://www.postgresql.org/message-id/20240212230423.GA3519%40nathanxps13

In my original benchmarks it was faster. I'll rebase the remaining
commits and do some more analysis.

--
David Geier

Re: Reduce build times of pg_trgm GIN indexes

David Geier <geidav.pg@gmail.com> — 2026-04-13T15:06:40Z

Hi Heikki!

> Pushed 0001 as commit 6f5ad00ab7.
> 
> I squashed 0002 and 0004 into one commit, and did some more refactoring:
> I created a trigram_qsort() helper function that calls the signed or
> unsigned variant, so that that logic doesn't need to be duplicated in
> the callers. For symmetry, I also added a trigram_qunique() helper
> function which just calls qunique() with the new, faster CMPTRGM_EQ
> comparator. Pushed these as commit 9f3755ea07.

Thanks for committing these patches.

--
David Geier

Re: Reduce build times of pg_trgm GIN indexes

David Geier <geidav.pg@gmail.com> — 2026-04-13T15:22:10Z

On 12.04.2026 20:05, Tom Lane wrote:
> Heikki Linnakangas <hlinnaka@iki.fi> writes:
>> Pushed 0001 as commit 6f5ad00ab7.
> 
> This commit has caused Coverity to start complaining that
> most of ginExtractEntries() is unreachable:
> 
> *** CID 1691468:         Control flow issues  (DEADCODE)
> /srv/coverity/git/pgsql-git/postgresql/src/backend/access/gin/ginutil.c: 495             in ginExtractEntries()
> 489     	/*
> 490     	 * Scan the items for any NULLs.  All NULLs are considered equal, so we
> 491     	 * just need to check and remember if there are any.  We remove them from
> 492     	 * the array here, and after deduplication, put back one NULL entry to
> 493     	 * represent them all.
> 494     	 */
>>>>     CID 1691468:         Control flow issues  (DEADCODE)
>>>>     Execution cannot reach this statement: "hasNull = false;".
> 495     	hasNull = false;
> 496     	if (nullFlags)
> 497     	{
> 498     		int32		numNonNulls = 0;
> 499     
> 500     		for (int32 i = 0; i < nentries; i++)
> 
> Evidently, it does not realize that the extractValueFn() can change
> nentries from its initial value of zero.  I wouldn't be too surprised
> if that's related to our casting of the pointer to uintptr_t --- that
> may cause it to not see the passed pointer as a potential reference
> mechanism.

Curious that we don't see that more frequently for other functions that
have output arguments. But maybe there are just too few?

> I would just write that off as Coverity not being smart enough, except
> that I'm worried that some compiler might make a similar deduction and
> break the function completely.  Was the switch to a local variable
> for nentries really a useful win performance-wise?

I haven't benchmarked the variant with using the pointer directly. I can
do that.

--
David Geier

Re: Reduce build times of pg_trgm GIN indexes

Heikki Linnakangas <hlinnaka@iki.fi> — 2026-04-13T16:14:23Z

On 12/04/2026 21:05, Tom Lane wrote:
> Heikki Linnakangas <hlinnaka@iki.fi> writes:
>> Pushed 0001 as commit 6f5ad00ab7.
> 
> This commit has caused Coverity to start complaining that
> most of ginExtractEntries() is unreachable:
> 
> *** CID 1691468:         Control flow issues  (DEADCODE)
> /srv/coverity/git/pgsql-git/postgresql/src/backend/access/gin/ginutil.c: 495             in ginExtractEntries()
> 489     	/*
> 490     	 * Scan the items for any NULLs.  All NULLs are considered equal, so we
> 491     	 * just need to check and remember if there are any.  We remove them from
> 492     	 * the array here, and after deduplication, put back one NULL entry to
> 493     	 * represent them all.
> 494     	 */
>>>>      CID 1691468:         Control flow issues  (DEADCODE)
>>>>      Execution cannot reach this statement: "hasNull = false;".
> 495     	hasNull = false;
> 496     	if (nullFlags)
> 497     	{
> 498     		int32		numNonNulls = 0;
> 499
> 500     		for (int32 i = 0; i < nentries; i++)
> 
> Evidently, it does not realize that the extractValueFn() can change
> nentries from its initial value of zero.  I wouldn't be too surprised
> if that's related to our casting of the pointer to uintptr_t --- that
> may cause it to not see the passed pointer as a potential reference
> mechanism.
> 
> I would just write that off as Coverity not being smart enough, except
> that I'm worried that some compiler might make a similar deduction and
> break the function completely.  Was the switch to a local variable
> for nentries really a useful win performance-wise?

I didn't do it for performance, but because I find the function easier 
to read that way. We could change it back.

It's a pretty scary thought that a compiler might misoptimize that 
though. In the same function we have 'nullFlags', too, as a local 
variable, even before this commit. Not sure why Coverity doesn't 
complain about that.

> /*
>  * PointerGetDatum
>  *		Returns datum representation for a pointer.
>  */
> static inline Datum
> PointerGetDatum(const void *X)
> {
> 	return (Datum) (uintptr_t) X;
> }

Hmm, is that 'const' incorrect? This function doesn't modify *X, but the 
resulting address will be used to modify it. Maybe changing it to 
non-const "void *X" would give Coverity a hint.

- Heikki

Re: Reduce build times of pg_trgm GIN indexes

Bertrand Drouvot <bertranddrouvot.pg@gmail.com> — 2026-04-13T17:15:52Z

Hi,

On Mon, Apr 13, 2026 at 05:03:11PM +0200, David Geier wrote:
> Hi!
> 
> On 13.04.2026 13:04, Bertrand Drouvot wrote:
> > Hi,
> > 
> > On Mon, Apr 13, 2026 at 11:41:02AM +0200, Peter Eisentraut wrote:
> >> On 09.04.26 13:28, Bertrand Drouvot wrote:
> >>>
> >>> This commit makes use of StaticAssertStmt() that has been deprecated in
> >>> d50c86e74375. The attached, fixes it.
> 
> I cannot find a comment close to StaticAssertStmt() that says it got
> deprecated.

The comment on top of it's definition is:

"
/*
 * StaticAssertStmt() was previously used to make static assertions work as a
 * statement, but its use is now deprecated.
 */
"

> Is the goal to completely get rid of StaticAssertStmt()?

According to its comment, I'd say so.

> > Yeah that looks better to not lose the connection with palloc0_array() here.
> > Done that way in the attached and adding new braces to avoid warning from
> > -Wdeclaration-after-statement.
> 
> Looks good to me.

Thanks for looking at it!

Regards,

-- 
Bertrand Drouvot
PostgreSQL Contributors Team
RDS Open Source Databases
Amazon Web Services: https://aws.amazon.com

Re: Reduce build times of pg_trgm GIN indexes

David Geier <geidav.pg@gmail.com> — 2026-04-14T07:02:10Z

> I didn't do it for performance, but because I find the function easier
> to read that way. We could change it back.
> 
> It's a pretty scary thought that a compiler might misoptimize that
> though. In the same function we have 'nullFlags', too, as a local
> variable, even before this commit. Not sure why Coverity doesn't
> complain about that.
> 
>> /*
>>  * PointerGetDatum
>>  *        Returns datum representation for a pointer.
>>  */
>> static inline Datum
>> PointerGetDatum(const void *X)
>> {
>>     return (Datum) (uintptr_t) X;
>> }
> 
> Hmm, is that 'const' incorrect? This function doesn't modify *X, but the
> resulting address will be used to modify it. Maybe changing it to non-
> const "void *X" would give Coverity a hint.

Ah, that could be it.
Is there a way for me to run Coverity on a patch to test that out?

Which Coverity CI do we actually use? Is it this one here [1]?

[1] https://scan.coverity.com/projects/209?

--
David Geier

Re: Reduce build times of pg_trgm GIN indexes

Heikki Linnakangas <hlinnaka@iki.fi> — 2026-04-14T09:22:27Z

On 13/04/2026 20:15, Bertrand Drouvot wrote:
> On Mon, Apr 13, 2026 at 05:03:11PM +0200, David Geier wrote:
>> On 13.04.2026 13:04, Bertrand Drouvot wrote:
>>> On Mon, Apr 13, 2026 at 11:41:02AM +0200, Peter Eisentraut wrote:
>>>> On 09.04.26 13:28, Bertrand Drouvot wrote:
>>>>>
>>>>> This commit makes use of StaticAssertStmt() that has been deprecated in
>>>>> d50c86e74375. The attached, fixes it.
>>
>> I cannot find a comment close to StaticAssertStmt() that says it got
>> deprecated.
> 
> The comment on top of it's definition is:
> 
> "
> /*
>   * StaticAssertStmt() was previously used to make static assertions work as a
>   * statement, but its use is now deprecated.
>   */
> "
> 
>> Is the goal to completely get rid of StaticAssertStmt()?
> 
> According to its comment, I'd say so.
> 
>>> Yeah that looks better to not lose the connection with palloc0_array() here.
>>> Done that way in the attached and adding new braces to avoid warning from
>>> -Wdeclaration-after-statement.
>>
>> Looks good to me.
> 
> Thanks for looking at it!

Committed this StaticAssertStmt/Decl() fix, thanks

- Heikki

Re: Reduce build times of pg_trgm GIN indexes

David Geier <geidav.pg@gmail.com> — 2026-04-14T13:05:51Z

On 13.04.2026 17:05, David Geier wrote:
> On 08.04.2026 04:15, John Naylor wrote:
>> On Tue, Apr 7, 2026 at 6:27 PM Heikki Linnakangas <hlinnaka@iki.fi> wrote:
>>> But the comments on the pg_cmp functions say:
>>>
>>>>  * NB: If the comparator function is inlined, some compilers may produce
>>>>  * worse code with these helper functions than with code with the
>>>>  * following form:
>>>>  *
>>>>  *     if (a < b)
>>>>  *         return -1;
>>>>  *     if (a > b)
>>>>  *         return 1;
>>>>  *     return 0;
>>>>  *
>>>
>>> So, uh, is that really a universal improvement? Is that comment about
>>> producing worse code outdated?
> 
> Well spotted. Thanks!
> 
>>
>> No, it's quite recent:
>>
>> https://www.postgresql.org/message-id/20240212230423.GA3519%40nathanxps13

FWICS, this would only matter if btint4cmp() would get inlined
somewhere, where the compiler could actually make use of understanding
that parts of the if-cascade are not needed. Andres' example was

return DO_COMPARE(a, b) < 0 ?
	(DO_COMPARE(b, c) < 0 ? b : (DO_COMPARE(a, c) < 0 ? c : a))
	: (DO_COMPARE(b, c) > 0 ? b : (DO_COMPARE(a, c) < 0 ? a : c));

In the case of btint4cmp(), it's only ever invoked from the function
manager, where it cannot be inlined.

Or are there ways to invoke btint4cmp() that can be inlined, which I'm
unaware of?

> In my original benchmarks it was faster. I'll rebase the remaining
> commits and do some more analysis.

Here is the disassembly and the perf top output of master vs patched. I
compiled with GCC 15.2.0.

The unpatched version of btint4cmp() contains a conditional jump, which
is mispredicted frequently in the sort. The patched version is
completely branchless.

master
======

Dump of assembler code for function btint4cmp:
   0x00005aa9e33ccdb0 <+0>:	endbr64
   0x00005aa9e33ccdb4 <+4>:	mov    0x20(%rdi),%edx
   0x00005aa9e33ccdb7 <+7>:	mov    $0x1,%eax
   0x00005aa9e33ccdbc <+12>:	cmp    %edx,0x30(%rdi)
   0x00005aa9e33ccdbf <+15>:	jl     0x5aa9e33ccdca <btint4cmp+26>
   0x00005aa9e33ccdc1 <+17>:	setne  %al
   0x00005aa9e33ccdc4 <+20>:	movzbl %al,%eax
   0x00005aa9e33ccdc7 <+23>:	neg    %rax
   0x00005aa9e33ccdca <+26>:	ret

  37.22%  pg_trgm.so  [.] trigram_qsort_signed.constprop.0
   7.99%  postgres    [.] cmpEntryAccumulator
   6.60%  postgres    [.] ginCombineData
   6.03%  postgres    [.] FunctionCall2Coll
   3.19%  postgres    [.] btint4cmp
   2.30%  postgres    [.] rbt_insert
   2.29%  pg_trgm.so  [.] generate_trgm
   2.24%  postgres    [.] pg_mblen_range
   1.77%  libc.so.6   [.] __towlower_l
   1.73%  pg_trgm.so  [.] trigram_qsort_signed_med3
   1.56%  postgres    [.] pg_utf2wchar_with_len

Patched
=======

Dump of assembler code for function btint4cmp:
   0x000055a69e87bdb0 <+0>:	endbr64
   0x000055a69e87bdb4 <+4>:	mov    0x20(%rdi),%eax
   0x000055a69e87bdb7 <+7>:	cmp    %eax,0x30(%rdi)
   0x000055a69e87bdba <+10>:	setl   %al
   0x000055a69e87bdbd <+13>:	setg   %dl
   0x000055a69e87bdc0 <+16>:	movzbl %dl,%edx
   0x000055a69e87bdc3 <+19>:	movzbl %al,%eax
   0x000055a69e87bdc6 <+22>:	sub    %edx,%eax
   0x000055a69e87bdc8 <+24>:	cltq
   0x000055a69e87bdca <+26>:	ret

  38.07%  pg_trgm.so        [.] trigram_qsort_signed.constprop.0
   7.69%  postgres          [.] cmpEntryAccumulator
   6.96%  postgres          [.] ginCombineData
   3.90%  postgres          [.] FunctionCall2Coll
   2.54%  postgres          [.] pg_mblen_range
   2.40%  postgres          [.] btint4cmp
   2.38%  pg_trgm.so        [.] generate_trgm
   1.86%  postgres          [.] rbt_insert
   1.80%  libc.so.6         [.] __towlower_l
   1.73%  pg_trgm.so        [.] trigram_qsort_signed_med3
   1.66%  postgres          [.] pg_utf2wchar_with_len

--
David Geier

Re: Reduce build times of pg_trgm GIN indexes

David Geier <geidav.pg@gmail.com> — 2026-04-14T14:24:10Z

On 13.04.2026 17:06, David Geier wrote:
>> I squashed 0002 and 0004 into one commit, and did some more refactoring:
>> I created a trigram_qsort() helper function that calls the signed or
>> unsigned variant, so that that logic doesn't need to be duplicated in
>> the callers. For symmetry, I also added a trigram_qunique() helper
>> function which just calls qunique() with the new, faster CMPTRGM_EQ
>> comparator. Pushed these as commit 9f3755ea07.
> 
> Thanks for committing these patches.

Attached are the remaining patches (previously 0003 and 0005) rebased on
latest master. Currently, there's no radix sort variant for the unsigned
char case. Do we care about this case or is it fine if that case runs
slower?

The following perf profiles show that trigram_qsort() goes from ~34%
down to ~7% with the radix sort optimization. The optimized run also
includes the btint4cmp() optimization. Without that the result would be
even better.

With that change we could move on and tackle optimizing

1. 41.52% generate_trgm_only() by e.g. using an ASCII fast-patch
2. 32.72% ginInsertBAEntries() by no longer using the RB-tree but
   e.g. also the radix sort

master




   - heapam_index_build_range_scan



      - 99.40% ginBuildCallback



         - ginHeapTupleBulkInsert



            - 66.55% ginExtractEntries



               - 65.29% FunctionCall3Coll



                  - gin_extract_value_trgm



                     - 62.80% generate_trgm



                        + 34.33% trigram_qsort (inlined)



                        + 26.20% generate_trgm_only



                        + 2.23% trigram_qunique (inlined)



                     + 1.74% detoast_attr



               + 1.19% qsort_arg_entries



            + 32.72% ginInsertBAEntries




patched




   - heapam_index_build_range_scan



      - 99.42% ginBuildCallback



         - 95.95% ginHeapTupleBulkInsert



            - 59.11% ginExtractEntries



               - 56.93% FunctionCall3Coll



                  - gin_extract_value_trgm



                     - 52.19% generate_trgm



                        + 41.52% generate_trgm_only



                        + 7.14% trigram_qsort (inlined)



                        + 3.53% trigram_qunique (inlined)



                     + 4.08% detoast_attr



               + 2.13% qsort_arg_entries



            + 36.78% ginInsertBAEntries

--
David Geier

Re: Reduce build times of pg_trgm GIN indexes

Heikki Linnakangas <hlinnaka@iki.fi> — 2026-04-15T11:06:14Z

On 14/04/2026 10:02, David Geier wrote:
>> I didn't do it for performance, but because I find the function easier
>> to read that way. We could change it back.
>>
>> It's a pretty scary thought that a compiler might misoptimize that
>> though. In the same function we have 'nullFlags', too, as a local
>> variable, even before this commit. Not sure why Coverity doesn't
>> complain about that.
>>
>>> /*
>>>   * PointerGetDatum
>>>   *        Returns datum representation for a pointer.
>>>   */
>>> static inline Datum
>>> PointerGetDatum(const void *X)
>>> {
>>>      return (Datum) (uintptr_t) X;
>>> }
>>
>> Hmm, is that 'const' incorrect? This function doesn't modify *X, but the
>> resulting address will be used to modify it. Maybe changing it to non-
>> const "void *X" would give Coverity a hint.

This was briefly discussed when PointerGetDatum() was changed from a 
macro to a static inline function [1]. On that email, Peter pointed out 
that the compiler was doing the same deduction that Coverity did now, 
i.e. that if you pass the Datum returned by PointerGetDatum(&foo) to a 
function, it cannot change *foo. I'm surprised we dismissed that worry 
so quickly. If the compiler optimizes based on that assumption, you can 
get incorrect code.

Three alternative fixes were discussed on that thread. Here's a fourth 
one that I think is better;

#define PointerGetDatum(X) \
	((Datum) (uintptr_t) (true ? (X) : NULL))

I found this trick with the dummy conditional expression at [2]. It 
always evaluates to just (X), but it has the effect that you get a 
compiler error if (X) is not a pointer.

[1] 
https://www.postgresql.org/message-id/812568f2-ff1d-ebd9-aee6-e00d8f2e0fb6%40enterprisedb.com

[2] See "TO_VOID_PTR_EXPR()" at 
https://medium.com/@pauljlucas/generic-in-c-d7ab47e3b5ab

> Ah, that could be it.
> Is there a way for me to run Coverity on a patch to test that out?

Not really I'm afraid. I can commit a fix and we'll see if it helps the 
next time that Coverity runs (= Sunday).

> Which Coverity CI do we actually use? Is it this one here [1]?
> 
> [1] https://scan.coverity.com/projects/209?

Yeah, that's the one, but only the security team has access.

- Heikki

Re: Reduce build times of pg_trgm GIN indexes

Peter Eisentraut <peter@eisentraut.org> — 2026-04-15T19:12:51Z

On 15.04.26 13:06, Heikki Linnakangas wrote:
> On 14/04/2026 10:02, David Geier wrote:
>>> I didn't do it for performance, but because I find the function easier
>>> to read that way. We could change it back.
>>>
>>> It's a pretty scary thought that a compiler might misoptimize that
>>> though. In the same function we have 'nullFlags', too, as a local
>>> variable, even before this commit. Not sure why Coverity doesn't
>>> complain about that.
>>>
>>>> /*
>>>>   * PointerGetDatum
>>>>   *        Returns datum representation for a pointer.
>>>>   */
>>>> static inline Datum
>>>> PointerGetDatum(const void *X)
>>>> {
>>>>      return (Datum) (uintptr_t) X;
>>>> }
>>>
>>> Hmm, is that 'const' incorrect? This function doesn't modify *X, but the
>>> resulting address will be used to modify it. Maybe changing it to non-
>>> const "void *X" would give Coverity a hint.
> 
> This was briefly discussed when PointerGetDatum() was changed from a 
> macro to a static inline function [1]. On that email, Peter pointed out 
> that the compiler was doing the same deduction that Coverity did now, 
> i.e. that if you pass the Datum returned by PointerGetDatum(&foo) to a 
> function, it cannot change *foo. I'm surprised we dismissed that worry 
> so quickly. If the compiler optimizes based on that assumption, you can 
> get incorrect code.

I don't think this is in evidence.  AFAICT, it's just Coverity that is 
complaining here, which is its right, but the code is not incorrect.

Re: Reduce build times of pg_trgm GIN indexes

Tom Lane <tgl@sss.pgh.pa.us> — 2026-04-15T21:25:24Z

Peter Eisentraut <peter@eisentraut.org> writes:
> On 15.04.26 13:06, Heikki Linnakangas wrote:
>> This was briefly discussed when PointerGetDatum() was changed from a 
>> macro to a static inline function [1]. On that email, Peter pointed out 
>> that the compiler was doing the same deduction that Coverity did now, 
>> i.e. that if you pass the Datum returned by PointerGetDatum(&foo) to a 
>> function, it cannot change *foo. I'm surprised we dismissed that worry 
>> so quickly. If the compiler optimizes based on that assumption, you can 
>> get incorrect code.

> I don't think this is in evidence.  AFAICT, it's just Coverity that is 
> complaining here, which is its right, but the code is not incorrect.

Are you sure?  This seems like the sort of thing that will bite us on
the rear sometime in the future, as the compiler geeks put in more and
more aggressive optimizations.

I think we should at least test the theory that changing
PointerGetDatum to remove the const cast would silence Coverity's
complaint.  If it does not then we're attributing too much
intelligence to Coverity.  But if it does, then we've correctly
identified why it's complaining, and we should take seriously the
idea that they aren't the only ones making this sort of deduction
(or won't be for long).

			regards, tom lane

Re: Reduce build times of pg_trgm GIN indexes

Peter Eisentraut <peter@eisentraut.org> — 2026-04-16T08:45:55Z

On 15.04.26 23:25, Tom Lane wrote:
> Peter Eisentraut <peter@eisentraut.org> writes:
>> On 15.04.26 13:06, Heikki Linnakangas wrote:
>>> This was briefly discussed when PointerGetDatum() was changed from a
>>> macro to a static inline function [1]. On that email, Peter pointed out
>>> that the compiler was doing the same deduction that Coverity did now,
>>> i.e. that if you pass the Datum returned by PointerGetDatum(&foo) to a
>>> function, it cannot change *foo. I'm surprised we dismissed that worry
>>> so quickly. If the compiler optimizes based on that assumption, you can
>>> get incorrect code.
> 
>> I don't think this is in evidence.  AFAICT, it's just Coverity that is
>> complaining here, which is its right, but the code is not incorrect.
> 
> Are you sure?  This seems like the sort of thing that will bite us on
> the rear sometime in the future, as the compiler geeks put in more and
> more aggressive optimizations.
> 
> I think we should at least test the theory that changing
> PointerGetDatum to remove the const cast would silence Coverity's
> complaint.  If it does not then we're attributing too much
> intelligence to Coverity.  But if it does, then we've correctly
> identified why it's complaining, and we should take seriously the
> idea that they aren't the only ones making this sort of deduction
> (or won't be for long).

I think it's quite clear to me that Coverity is complaining about this 
correctly, in its view of the world.  Compilers sometimes complain about 
this, too, although in this case they apparently don't look quite as 
deeply to do this analysis.

What I'm missing here is, essentially where the previous thread stopped: 
What is the overall message that we want to communicate with the API?

If the default assumption is that what pointers converted to Datums 
point to should not be modified on the other side (where the Datum is 
converted back to a pointer), then the current declaration of 
PointerGetDatum() is suitable, and the GIN code can be considered an 
exception and we make a special API for that.  The previous thread 
proposed NonconstPointerGetDatum().

(If this is the resolution, I also have half a patch somewhere that 
makes the string input argument for the InputFunctionCall family of 
functions const, which also seems intuitively sensible.)

If, on the other hand, the decision is that there is in fact no such 
guarantee, that consumers of Datums are free to modify whatever they 
seem fit, then we should drop the const of PointerGetDatum and fix the 
fallout up the call stack.

The macro proposed by Heikki, I don't know, still doesn't actually 
answer this question, just (possibly) makes these warnings go away in a 
slightly mysterious way.

Re: Reduce build times of pg_trgm GIN indexes

Heikki Linnakangas <hlinnaka@iki.fi> — 2026-04-16T09:49:38Z

On 16/04/2026 11:45, Peter Eisentraut wrote:
> On 15.04.26 23:25, Tom Lane wrote:
>> Peter Eisentraut <peter@eisentraut.org> writes:
>>> On 15.04.26 13:06, Heikki Linnakangas wrote:
>>>> This was briefly discussed when PointerGetDatum() was changed from a
>>>> macro to a static inline function [1]. On that email, Peter pointed out
>>>> that the compiler was doing the same deduction that Coverity did now,
>>>> i.e. that if you pass the Datum returned by PointerGetDatum(&foo) to a
>>>> function, it cannot change *foo. I'm surprised we dismissed that worry
>>>> so quickly. If the compiler optimizes based on that assumption, you can
>>>> get incorrect code.
>>
>>> I don't think this is in evidence.  AFAICT, it's just Coverity that is
>>> complaining here, which is its right, but the code is not incorrect.
>>
>> Are you sure?  This seems like the sort of thing that will bite us on
>> the rear sometime in the future, as the compiler geeks put in more and
>> more aggressive optimizations.
>>
>> I think we should at least test the theory that changing
>> PointerGetDatum to remove the const cast would silence Coverity's
>> complaint.  If it does not then we're attributing too much
>> intelligence to Coverity.  But if it does, then we've correctly
>> identified why it's complaining, and we should take seriously the
>> idea that they aren't the only ones making this sort of deduction
>> (or won't be for long).
> 
> I think it's quite clear to me that Coverity is complaining about this 
> correctly, in its view of the world.  Compilers sometimes complain about 
> this, too, although in this case they apparently don't look quite as 
> deeply to do this analysis.
> 
> What I'm missing here is, essentially where the previous thread stopped: 
> What is the overall message that we want to communicate with the API?
> 
> If the default assumption is that what pointers converted to Datums 
> point to should not be modified on the other side (where the Datum is 
> converted back to a pointer), then the current declaration of 
> PointerGetDatum() is suitable, and the GIN code can be considered an 
> exception and we make a special API for that.  The previous thread 
> proposed NonconstPointerGetDatum().
> 
> (If this is the resolution, I also have half a patch somewhere that 
> makes the string input argument for the InputFunctionCall family of 
> functions const, which also seems intuitively sensible.)
> 
> If, on the other hand, the decision is that there is in fact no such 
> guarantee, that consumers of Datums are free to modify whatever they 
> seem fit, then we should drop the const of PointerGetDatum and fix the 
> fallout up the call stack.
> 
> The macro proposed by Heikki, I don't know, still doesn't actually 
> answer this question, just (possibly) makes these warnings go away in a 
> slightly mysterious way.

My intention was that if you do:

     const foo *ptr;
     ...
     datum = PointerGetDatum(ptr);

Then you're not allowed to modify the contents of *ptr through the 
'datum'. But if you do:

     foo *ptr;
     ...
     datum = PointerGetDatum(ptr);

Then it is allowed.

I don't know how to tell the compiler exactly that. I tried various 
hacks with _Generic(), but couldn't make it work. The macro casts away 
the 'const' in the first case, which might disable some optimizations 
that the compiler could otherwise do.

We could have all three:

ConstPointerGetDatum(const void *): Promises that the returned Datum is 
not used to modify

NonConstPointerGetDatum(void *): No such promise.

PointerGetDatum(): Macro as I proposed. Like NonConstPointerGetDatum(), 
but for backwards-compatibility it doesn't emit a warning if you pass a 
const pointer to it.

- Heikki

Re: Reduce build times of pg_trgm GIN indexes

Tom Lane <tgl@sss.pgh.pa.us> — 2026-04-16T14:37:51Z

Heikki Linnakangas <hlinnaka@iki.fi> writes:
> On 16/04/2026 11:45, Peter Eisentraut wrote:
>> What I'm missing here is, essentially where the previous thread stopped: 
>> What is the overall message that we want to communicate with the API?

Good point.

>> If the default assumption is that what pointers converted to Datums 
>> point to should not be modified on the other side (where the Datum is 
>> converted back to a pointer), then the current declaration of 
>> PointerGetDatum() is suitable, and the GIN code can be considered an 
>> exception and we make a special API for that.  The previous thread 
>> proposed NonconstPointerGetDatum().

I think there can be no doubt that most functions receiving a
pass-by-ref Datum are not supposed to scribble on the pointed-to
data.  So it makes sense to me that PointerGetDatum should carry
an implication of const-ness, and then we need to invent a new
notation to use in the small number of places where that's not
appropriate.  I'd capitalize it as NonConstPointerGetDatum,
but other than that nit that naming suggestion seems fine to me.

Of course, then the *real* question is why DatumGetPointer
doesn't deliver a const pointer.  But I don't see how to get
there without extremely invasive changes.

> We could have all three:

Not excited about making massive changes for this.

I remain far less certain than Peter is that this discussion has
anything to do with why Coverity is complaining about
ginExtractEntries.  I still think we should make some minimum-effort
change to see if the complaint goes away before expending a lot of
brain cells on choosing a final fix.

			regards, tom lane

Re: Reduce build times of pg_trgm GIN indexes

Andres Freund <andres@anarazel.de> — 2026-04-16T14:43:04Z

Hi, 

On April 16, 2026 4:45:55 AM EDT, Peter Eisentraut <peter@eisentraut.org> wrote:
>On 15.04.26 23:25, Tom Lane wrote:
>> Peter Eisentraut <peter@eisentraut.org> writes:
>>> On 15.04.26 13:06, Heikki Linnakangas wrote:
>>>> This was briefly discussed when PointerGetDatum() was changed from a
>>>> macro to a static inline function [1]. On that email, Peter pointed out
>>>> that the compiler was doing the same deduction that Coverity did now,
>>>> i.e. that if you pass the Datum returned by PointerGetDatum(&foo) to a
>>>> function, it cannot change *foo. I'm surprised we dismissed that worry
>>>> so quickly. If the compiler optimizes based on that assumption, you can
>>>> get incorrect code.
>> 
>>> I don't think this is in evidence.  AFAICT, it's just Coverity that is
>>> complaining here, which is its right, but the code is not incorrect.
>> 
>> Are you sure?  This seems like the sort of thing that will bite us on
>> the rear sometime in the future, as the compiler geeks put in more and
>> more aggressive optimizations.
>> 
>> I think we should at least test the theory that changing
>> PointerGetDatum to remove the const cast would silence Coverity's
>> complaint.  If it does not then we're attributing too much
>> intelligence to Coverity.  But if it does, then we've correctly
>> identified why it's complaining, and we should take seriously the
>> idea that they aren't the only ones making this sort of deduction
>> (or won't be for long).
>
>I think it's quite clear to me that Coverity is complaining about this correctly, in its view of the world.  Compilers sometimes complain about this, too, although in this case they apparently don't look quite as deeply to do this analysis.
>
>What I'm missing here is, essentially where the previous thread stopped: What is the overall message that we want to communicate with the API?
>
>If the default assumption is that what pointers converted to Datums point to should not be modified on the other side (where the Datum is converted back to a pointer), then the current declaration of PointerGetDatum() is suitable, and the GIN code can be considered an exception and we make a special API for that.  The previous thread proposed NonconstPointerGetDatum().

To me it seems way way way to dangerous to just redefine what PointerGetDatum() means for all existing callers, without doing an exhaustive verification of all the callers.

Separately from that, it doesn't seem defensible to take a const pointer and return a non const one. Why is that sane? 

Greetings, 

Andres
-- 
Sent from my Android device with K-9 Mail. Please excuse my brevity.

Re: Reduce build times of pg_trgm GIN indexes

Heikki Linnakangas <hlinnaka@iki.fi> — 2026-04-16T17:30:51Z

On 16/04/2026 17:37, Tom Lane wrote:
> Heikki Linnakangas <hlinnaka@iki.fi> writes:
>> On 16/04/2026 11:45, Peter Eisentraut wrote:
>>> What I'm missing here is, essentially where the previous thread stopped:
>>> What is the overall message that we want to communicate with the API?
> 
> Good point.
> 
>>> If the default assumption is that what pointers converted to Datums
>>> point to should not be modified on the other side (where the Datum is
>>> converted back to a pointer), then the current declaration of
>>> PointerGetDatum() is suitable, and the GIN code can be considered an
>>> exception and we make a special API for that.  The previous thread
>>> proposed NonconstPointerGetDatum().
> 
> I think there can be no doubt that most functions receiving a
> pass-by-ref Datum are not supposed to scribble on the pointed-to
> data.  So it makes sense to me that PointerGetDatum should carry
> an implication of const-ness, and then we need to invent a new
> notation to use in the small number of places where that's not
> appropriate.  I'd capitalize it as NonConstPointerGetDatum,
> but other than that nit that naming suggestion seems fine to me.

That makes sense. My worry is that we're changing the rules in a very 
subtle way: It used to be OK to use PointerGetDatum(), pass the 
resulting datum to something that modifies it. Now we say it's not OK, 
and you must use NonConstPointerGetDatum(). You don't get any compiler 
warnings if you use it wrong, except for this one coverity warning 
apparently, but it doesn't catch this reliably either.

> Of course, then the *real* question is why DatumGetPointer
> doesn't deliver a const pointer.  But I don't see how to get
> there without extremely invasive changes.

Good point.

>> We could have all three:
> 
> Not excited about making massive changes for this.

Having all three would be a very localized change in postgres.h.

> I remain far less certain than Peter is that this discussion has
> anything to do with why Coverity is complaining about
> ginExtractEntries.  I still think we should make some minimum-effort
> change to see if the complaint goes away before expending a lot of
> brain cells on choosing a final fix.

I think I'm going to commit my proposal to turn PointerGetDatum() back 
into a macro, and see if that makes Coverity happy. Then we'll know, and 
we can decide on the next steps. Any objections?

One open question is whether we should backpatch any of this. I guess 
compilers don't misoptimize this in practice, or we would've gotten more 
reports, but I really can't rationalize why not and a new compiler 
version might well start hitting this.

- Heikki

Re: Reduce build times of pg_trgm GIN indexes

Tom Lane <tgl@sss.pgh.pa.us> — 2026-04-16T17:47:05Z

Heikki Linnakangas <hlinnaka@iki.fi> writes:
> On 16/04/2026 17:37, Tom Lane wrote:
>> Not excited about making massive changes for this.

> Having all three would be a very localized change in postgres.h.

Sure, but *using* them in a consistent way would be invasive.

>> I remain far less certain than Peter is that this discussion has
>> anything to do with why Coverity is complaining about
>> ginExtractEntries.  I still think we should make some minimum-effort
>> change to see if the complaint goes away before expending a lot of
>> brain cells on choosing a final fix.

> I think I'm going to commit my proposal to turn PointerGetDatum() back 
> into a macro, and see if that makes Coverity happy. Then we'll know, and 
> we can decide on the next steps. Any objections?

WFM.

			regards, tom lane

Re: Reduce build times of pg_trgm GIN indexes

Heikki Linnakangas <hlinnaka@iki.fi> — 2026-04-17T19:21:41Z

On 16/04/2026 20:47, Tom Lane wrote:
> Heikki Linnakangas <hlinnaka@iki.fi> writes:
>> On 16/04/2026 17:37, Tom Lane wrote:
>>> Not excited about making massive changes for this.
> 
>> Having all three would be a very localized change in postgres.h.
> 
> Sure, but *using* them in a consistent way would be invasive.
> 
>>> I remain far less certain than Peter is that this discussion has
>>> anything to do with why Coverity is complaining about
>>> ginExtractEntries.  I still think we should make some minimum-effort
>>> change to see if the complaint goes away before expending a lot of
>>> brain cells on choosing a final fix.
> 
>> I think I'm going to commit my proposal to turn PointerGetDatum() back
>> into a macro, and see if that makes Coverity happy. Then we'll know, and
>> we can decide on the next steps. Any objections?
> 
> WFM.

Grepping for PointerGetDatum(), there are a bunch of wrappers of it for 
specific types, like:

static inline Datum CStringGetDatum(const char *X)
static inline Datum NumericGetDatum(Numeric X)

Most are marked "const". These all potentially have the same problem, 
but I think for these it is a good assumption that resulting Datum will 
not be used to modify *X, so we can leave them alone. I guess we didn't 
do that for NumericGetDatum just because the Numeric typedef doesn't 
allow that.

There's also:

static inline Datum fetch_att(const void *T, bool attbyval, int attlen)

The "const" seems reasonable on that too.

This is an interesting case:

static inline Datum
EOHPGetRWDatum(const struct ExpandedObjectHeader *eohptr)
{
	return PointerGetDatum(eohptr->eoh_rw_ptr);
}

That RW stands for read/write, which sounds alarming. But the returned 
datum points to eohptr->eoh_rw_ptr rather than *eohptr itself, so I 
think the 'const' is correct here after all.

So, pushed a commit that changes just PointerGetDatum() itself, leaving 
all those others alone.

- Heikki

Re: Reduce build times of pg_trgm GIN indexes

Heikki Linnakangas <hlinnaka@iki.fi> — 2026-04-22T21:11:51Z

On 17/04/2026 22:21, Heikki Linnakangas wrote:
> On 16/04/2026 20:47, Tom Lane wrote:
>> Heikki Linnakangas <hlinnaka@iki.fi> writes:
>>> On 16/04/2026 17:37, Tom Lane wrote:
>>>> Not excited about making massive changes for this.
>>
>>> Having all three would be a very localized change in postgres.h.
>>
>> Sure, but *using* them in a consistent way would be invasive.
>>
>>>> I remain far less certain than Peter is that this discussion has
>>>> anything to do with why Coverity is complaining about
>>>> ginExtractEntries.  I still think we should make some minimum-effort
>>>> change to see if the complaint goes away before expending a lot of
>>>> brain cells on choosing a final fix.
>>
>>> I think I'm going to commit my proposal to turn PointerGetDatum() back
>>> into a macro, and see if that makes Coverity happy. Then we'll know, and
>>> we can decide on the next steps. Any objections?
>>
>> WFM.
> 
> ...
> 
> So, pushed a commit that changes just PointerGetDatum() itself, leaving 
> all those others alone.

As we thought, this made the Coverity warning go away.

I'm happy with the status quo in master, but if we want to introduce new 
ConstPointerGetDatum() or NonConstPointerGetDatum() variants instead of 
the macro, now is the time to do it.

For backbranches, IMHO we should go with the macro. It's a little scary 
to replace such a widely used function as PointerGetDatum() in 
back-branches, but I do think this should be fixed. Introducing new 
variants doesn't seems even less backpatchable.

- Heikki

Re: Reduce build times of pg_trgm GIN indexes

David Geier <geidav.pg@gmail.com> — 2026-04-22T21:26:56Z

On 14.04.2026 16:24, David Geier wrote:
> Attached are the remaining patches (previously 0003 and 0005) rebased on
> latest master. Currently, there's no radix sort variant for the unsigned
> char case. Do we care about this case or is it fine if that case runs
> slower?
> 
> The following perf profiles show that trigram_qsort() goes from ~34%
> down to ~7% with the radix sort optimization. The optimized run also
> includes the btint4cmp() optimization. Without that the result would be
> even better.
> 
> With that change we could move on and tackle optimizing
> 
> 1. 41.52% generate_trgm_only() by e.g. using an ASCII fast-patch
> 2. 32.72% ginInsertBAEntries() by no longer using the RB-tree but
>    e.g. also the radix sort

Attached is the rebased patch set as well as a new patch that optimizes
ginInsertBAEntries(). Performance improvements are as follows, measured
with the same benchmark I used in the first mail of this thread.
Runtimes and deltas are in milliseconds.

Code                               | movies | delta  | lineitem | delta
-----------------------------------|--------|--------|------------------
master                             | 11,160 | -      | 248,146  | -
v7-0001-Make-btint4cmp-branchless  |  9,509 | 1,651  | 236,760  | 11,386
v7-0002-Use-radix-sort             |  6,123 | 3,386  | 214,632  | 22,128
v7-0003-Replace-RB-tree            |  4,755 | 1,368  | 144,252  | 70,380

I optimized ginInsertBAEntries() by replacing the red-black tree by a
hash map (simplehash.h) on the keys (e.g. trigrams), where each hash map
entry contains an item pointer list with the row TIDs the key occurs in.
This is in the spirit of the original red-black tree implementation but
this way the deduplication of each key is handled in O(1), instead of
O(log(num_unique_keys)). This reduces the overall runtime complexity from

O(num_total_keys * log(num_unique_keys))
  ->
O(num_total_keys + num_unique_keys * log(num_unique_keys))

As there are normally a lot less keys than rows, this is complexity-wise
preferable. And even if all keys are unique, the rebalancing operations
are pretty expensive and in reality outweigh the slightly better
complexity in the worst-case.

- The sorting of the item pointer lists for each key stays as is, except
  for that I switched to sort_template.h.

- The red-black tree code in rbtree.c/.h is now completely unused and
  could be removed. Thoughts?

- The size on disk changed very slightly. I think this is because the
  memory accounting is slightly different and with that slightly more or
  less keys / item pointers can be processed in one go.

- FWICS, we can use datumIsEqual() and datum_image_hash() in the hash
  map because as of today, the GIN index code doesn't work properly with
  non-deterministic collations / non-image-equal types, e.g. see [1].

- I also simplified ginInsertBAEntries(). Previously, it used an
  insertion order that minimizes the number of RB-tree rebalancing
  operations for sorted inputs. With the hash map approach, it's better
  to insert in sort order as this increases the likelihood of hitting
  the same hash map entry again for equal keys.

- This patch set also improves parallel GIN index builds as the parallel
  code builds on top of ginInsertBAEntries().

- Regression tests pass and gin_index_check() from amcheck couldn't find
  an error in the data structures.

To be fair: 0001 is less interesting after removing the RB-tree because
a lot less key comparisons are being performed. I still think it makes
sense to merge it as it should also accelerate e.g. B-tree traversals.

With these changes the number one bottleneck becomes the trigram
generation in generate_trgm_only(). The following perf profile nicely
shows that:

-   99.89%     0.00%  postgres  postgres           [.] ginbuild
     ginbuild
     table_index_build_scan (inlined)
   - heapam_index_build_range_scan
      - 94.05% ginBuildCallback
         - 86.48% ginHeapTupleBulkInsert
            - 68.57% ginExtractEntries
               - 64.69% FunctionCall3Coll
                  - gin_extract_value_trgm
                     - 62.75% generate_trgm
                        - 39.57% generate_trgm_only
                           + 18.53% str_tolower
                           + 16.91% find_word (inlined)
                           + 1.36% make_trigrams (inlined)
                             0.66% __strlen_avx2
                        + 18.49% trigram_qsort (inlined)
                        + 4.17% trigram_qunique (inlined)
                       0.79% trgm2int
               + 3.33% qsort_arg_entries
            - 17.28% ginInsertBAEntries
               - ginInsertBAEntry (inlined)
                  - 8.04% ginbuild_insert (inlined)
                     - 4.89% ginbuild_insert_hash_internal (inlined)
                          1.25% gin_equal_key (inlined)
                          0.68% ginbuild_initial_bucket (inlined)
                     + 3.14% gin_hash_key (inlined)
                  + 2.45% AllocSetRealloc
                  + 0.85% asm_exc_page_fault
                    0.52% getDatumCopy (inlined)
         + 6.00% ginEntryInsert
         + 1.19% ginBeginBAScan
      + 2.99% heap_getnext

[1]
https://www.postgresql.org/message-id/flat/8ef4899c4acfebca45cc6c042a6dc611d25ffab1.camel%40cybertec.at

--
David Geier