Обсуждение: BUG #19031: pg_trgm infinite loop on certain cases
The following bug has been logged on the website:
Bug reference: 19031
Logged by: Tim Wood
Email address: washwithcare@gmail.com
PostgreSQL version: 17.6
Operating system: MacOS
Description:
When querying against a column with a gin_trgm_ops index, using <% with a
string without any trigrams followed by a string with trigrams causes what
appears to be an infinite loop, and the query cannot be canceled, and the
process must be restarted in order to kill the long running query.
Simplified use case:
```
create extension if not exists pg_trgm with schema public;
create temp table simple_case (name text);
create index simple_case_name_index on simple_case using gin (name
gin_trgm_ops);
-- generate enough records for the optimizer to choose the index
insert into simple_case (name) select 'two and' || i::text from
generate_series(1, 1000000) as t(i);
select * from simple_case; -- returns normally
explain select * from simple_case where (',' <% name);
select * from simple_case where (',' <% name); -- returns normally
explain select * from simple_case where ('a' <% name) and (',' <% name);
select * from simple_case where ('a' <% name) and (',' <% name); -- returns
normally
explain select * from simple_case where ('a' <% name) and (',' <% name) and
('a' <% name);
select * from simple_case where ('a' <% name) and (',' <% name) and ('a' <%
name); -- returns normally
explain select * from simple_case where (',' <% name) and ('a' <% name);
select * from simple_case where (',' <% name) and ('a' <% name); -- infinite
loop
select * from simple_case where ('' <% name) and ('a' <% name); -- infinite
loop
```
PG Bug reporting form <noreply@postgresql.org> writes:
> When querying against a column with a gin_trgm_ops index, using <% with a
> string without any trigrams followed by a string with trigrams causes what
> appears to be an infinite loop, and the query cannot be canceled, and the
> process must be restarted in order to kill the long running query.
Thanks for the test case! AFAICT this is a bug in 4b754d6c1
which introduced "excludeOnly" GIN scan keys. There is a comment
in scanGetItem that says
/*
* ginNewScanKey() should never mark the first key as
* excludeOnly.
*/
However, if you look at ginNewScanKey, it's totally not concerned
about avoiding that. In this test case, the first scan key is marked
excludeOnly, and that sends scanGetItem into what seems an infinite
loop.
After reading the comments in that commit, I think what we actually
want is to require excludeOnly scan keys to appear last. The 0002
patch attached modifies ginNewScanKey to re-order the scan keys to
guarantee that, and it fixes this test case.
However, I don't totally understand *why* it fixes the test case.
Especially not after I noted that there's already a test case in
pg_trgm that exercises exactly this situation:
select count(*) from test_trgm where t like '%99%' and t like '%qwerty%';
If you put an Assert into ginNewScanKey that the first scan key
isn't excludeOnly (instead of the re-sort), it fails on that query.
So why do we not see an infinite loop for that test case? I don't
really understand the GIN code well enough to figure out what is
the difference.
In the meantime, the 0001 patch attached moves the
CHECK_FOR_INTERRUPTS() call in gingetbitmap to be inside the loop in
scanGetItem, so that it's able to respond to a query cancel request in
this situation. I think we'd better do that even after fixing the
present bug.
regards, tom lane
diff --git a/src/backend/access/gin/ginget.c b/src/backend/access/gin/ginget.c
index f29ccd3c2d1..656299b1b52 100644
--- a/src/backend/access/gin/ginget.c
+++ b/src/backend/access/gin/ginget.c
@@ -1327,6 +1327,8 @@ scanGetItem(IndexScanDesc scan, ItemPointerData advancePast,
*/
do
{
+ CHECK_FOR_INTERRUPTS();
+
ItemPointerSetMin(item);
match = true;
for (i = 0; i < so->nkeys && match; i++)
@@ -1966,8 +1968,6 @@ gingetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
for (;;)
{
- CHECK_FOR_INTERRUPTS();
-
if (!scanGetItem(scan, iptr, &iptr, &recheck))
break;
diff --git a/src/backend/access/gin/ginscan.c b/src/backend/access/gin/ginscan.c
index c2d1771bd77..26081693383 100644
--- a/src/backend/access/gin/ginscan.c
+++ b/src/backend/access/gin/ginscan.c
@@ -271,6 +271,7 @@ ginNewScanKey(IndexScanDesc scan)
ScanKey scankey = scan->keyData;
GinScanOpaque so = (GinScanOpaque) scan->opaque;
int i;
+ int numExcludeOnly;
bool hasNullQuery = false;
bool attrHasNormalScan[INDEX_MAX_KEYS] = {false};
MemoryContext oldCtx;
@@ -393,6 +394,7 @@ ginNewScanKey(IndexScanDesc scan)
* excludeOnly scan key must receive a GIN_CAT_EMPTY_QUERY hidden entry
* and be set to normal (excludeOnly = false).
*/
+ numExcludeOnly = 0;
for (i = 0; i < so->nkeys; i++)
{
GinScanKey key = &so->keys[i];
@@ -406,6 +408,47 @@ ginNewScanKey(IndexScanDesc scan)
ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_QUERY);
attrHasNormalScan[key->attnum - 1] = true;
}
+ else
+ numExcludeOnly++;
+ }
+
+ /*
+ * If we left any excludeOnly scan keys as-is, move them to the end of the
+ * scan key array: they must appear after normal key(s).
+ */
+ if (numExcludeOnly > 0)
+ {
+ GinScanKey tmpkeys;
+ int iNormalKey;
+ int iExcludeOnly;
+
+ /* We'd better have made at least one normal key */
+ Assert(numExcludeOnly < so->nkeys);
+ /* Make a temporary array to hold the re-ordered scan keys */
+ tmpkeys = (GinScanKey) palloc(so->nkeys * sizeof(GinScanKeyData));
+ /* Re-order the keys ... */
+ iNormalKey = 0;
+ iExcludeOnly = so->nkeys - numExcludeOnly;
+ for (i = 0; i < so->nkeys; i++)
+ {
+ GinScanKey key = &so->keys[i];
+
+ if (key->excludeOnly)
+ {
+ memcpy(tmpkeys + iExcludeOnly, key, sizeof(GinScanKeyData));
+ iExcludeOnly++;
+ }
+ else
+ {
+ memcpy(tmpkeys + iNormalKey, key, sizeof(GinScanKeyData));
+ iNormalKey++;
+ }
+ }
+ Assert(iNormalKey == so->nkeys - numExcludeOnly);
+ Assert(iExcludeOnly == so->nkeys);
+ /* ... and copy them back to so->keys[] */
+ memcpy(so->keys, tmpkeys, so->nkeys * sizeof(GinScanKeyData));
+ pfree(tmpkeys);
}
/*
Hi,
On Tue, Aug 26, 2025 at 3:54 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> ...
> However, I don't totally understand *why* it fixes the test case.
> Especially not after I noted that there's already a test case in
> pg_trgm that exercises exactly this situation:
>
> select count(*) from test_trgm where t like '%99%' and t like '%qwerty%';
>
> If you put an Assert into ginNewScanKey that the first scan key
> isn't excludeOnly (instead of the re-sort), it fails on that query.
> So why do we not see an infinite loop for that test case? I don't
> really understand the GIN code well enough to figure out what is
> the difference.
>
I debug a little bit and it looks like the reason there's no infinite
loop in your example is because it returns MAYBE for the first
'excludeOnly' key in:
keyGetItem()
...
res = key->triConsistentFn(key);
so we set key->curItemMatches = true for the first key and move on to
the second normal key, allowing the scan to proceed and eventually
finish. In the bug repro, the first 'excludeOnly' key returns FALSE in
triConsistentFn, so we get stuck on the 'excludeOnly' key which never
finishes. I don't have an opinion on whether it's good or not to move
all the 'excludeOnly' keys to the end, but it seems that simply not
having an "excludeOnly" key as the first key is enough to fix the bug.
Maybe it's enough to just swap any normal key with the first one, if
it's "excludeOnly"?
> In the meantime, the 0001 patch attached moves the
> CHECK_FOR_INTERRUPTS() call in gingetbitmap to be inside the loop in
> scanGetItem, so that it's able to respond to a query cancel request in
> this situation. I think we'd better do that even after fixing the
> present bug.
+1
Best regards,
Arseniy Mukhin
Arseniy Mukhin <arseniy.mukhin.dev@gmail.com> writes:
> On Tue, Aug 26, 2025 at 3:54 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> However, I don't totally understand *why* it fixes the test case.
>> Especially not after I noted that there's already a test case in
>> pg_trgm that exercises exactly this situation:
>>
>> select count(*) from test_trgm where t like '%99%' and t like '%qwerty%';
>>
>> If you put an Assert into ginNewScanKey that the first scan key
>> isn't excludeOnly (instead of the re-sort), it fails on that query.
>> So why do we not see an infinite loop for that test case? I don't
>> really understand the GIN code well enough to figure out what is
>> the difference.
> I debug a little bit and it looks like the reason there's no infinite
> loop in your example is because it returns MAYBE for the first
> 'excludeOnly' key in:
> keyGetItem()
> ...
> res = key->triConsistentFn(key);
Ah-hah! The thing I'd overlooked is that that regression test query
uses a different operator: LIKE not %>. So even though the
GinScanKey looks pretty similar, the strategy is different, leading
gin_trgm_triconsistent to return GIN_MAYBE not GIN_FALSE when nkeys=0.
So now I can reproduce the failure with the regression tests' table:
select count(*) from test_trgm where t %> '' and t %> '%qwerty%';
> I don't have an opinion on whether it's good or not to move
> all the 'excludeOnly' keys to the end, but it seems that simply not
> having an "excludeOnly" key as the first key is enough to fix the bug.
> Maybe it's enough to just swap any normal key with the first one, if
> it's "excludeOnly"?
Yeah, that would be enough to get us out of this particular example.
But I think the lesson here is that there are under-documented
dependencies on the ordering of GinScanKeys, and I want the fix to
make that ordering more predictable not less so. For example, after
seeing this I have little confidence that GIN wouldn't have issues
with an excludeOnly key that precedes the first normal key for its
index attribute, even when there are other keys for other attributes
appearing ahead of them in the scankey array. So I'd rather that the
fix be based on a consistent pattern like "put excludeOnly keys after
not-excludeOnly keys", not "let's swap the first key with some
randomly-chosen other key".
regards, tom lane
On Tue, Aug 26, 2025 at 6:16 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> Arseniy Mukhin <arseniy.mukhin.dev@gmail.com> writes:
> > On Tue, Aug 26, 2025 at 3:54 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> >> However, I don't totally understand *why* it fixes the test case.
> >> Especially not after I noted that there's already a test case in
> >> pg_trgm that exercises exactly this situation:
> >>
> >> select count(*) from test_trgm where t like '%99%' and t like '%qwerty%';
> >>
> >> If you put an Assert into ginNewScanKey that the first scan key
> >> isn't excludeOnly (instead of the re-sort), it fails on that query.
> >> So why do we not see an infinite loop for that test case? I don't
> >> really understand the GIN code well enough to figure out what is
> >> the difference.
>
> > I debug a little bit and it looks like the reason there's no infinite
> > loop in your example is because it returns MAYBE for the first
> > 'excludeOnly' key in:
> > keyGetItem()
> > ...
> > res = key->triConsistentFn(key);
>
> Ah-hah! The thing I'd overlooked is that that regression test query
> uses a different operator: LIKE not %>. So even though the
> GinScanKey looks pretty similar, the strategy is different, leading
> gin_trgm_triconsistent to return GIN_MAYBE not GIN_FALSE when nkeys=0.
> So now I can reproduce the failure with the regression tests' table:
>
> select count(*) from test_trgm where t %> '' and t %> '%qwerty%';
>
Great!
> > I don't have an opinion on whether it's good or not to move
> > all the 'excludeOnly' keys to the end, but it seems that simply not
> > having an "excludeOnly" key as the first key is enough to fix the bug.
> > Maybe it's enough to just swap any normal key with the first one, if
> > it's "excludeOnly"?
>
> Yeah, that would be enough to get us out of this particular example.
> But I think the lesson here is that there are under-documented
> dependencies on the ordering of GinScanKeys, and I want the fix to
> make that ordering more predictable not less so. For example, after
> seeing this I have little confidence that GIN wouldn't have issues
> with an excludeOnly key that precedes the first normal key for its
> index attribute, even when there are other keys for other attributes
> appearing ahead of them in the scankey array. So I'd rather that the
> fix be based on a consistent pattern like "put excludeOnly keys after
> not-excludeOnly keys", not "let's swap the first key with some
> randomly-chosen other key".
>
Good point, thanks for the explanation. I forgot that there can be
many attributes. And I agree, the more determinism in the system, the
easier it is to work with it and the less room for bugs. OTOH it seems
from the performance POV we want to have the stricter keys to be the
first so we do less work and fail fast on the first keys. It looks
like these two rules (excludeOnly keys LAST and more restrictive keys
FIRST) are kind of in conflict with each other. I tried to do some
experiments and it's seems GIN quite sensitive to it, at least in this
artificial example:
(bug repro table is used here)
-- excludeOnly key is the middle
explain analyse
select *
from simple_case
where ('two' <% name)
and (',' <% name)
and ('and' <% name);
-- Execution Time: 406.718 ms
-- excludeOnly key in the end
explain analyse
select *
from simple_case
where ('two' <% name)
and ('and' <% name)
and (',' <% name);
-- Execution Time: 706.655 ms
With applying patch both queries show the same time (second one). So
currently the user can tune the query by defining more restrictive
keys first. With the proposed fix it looks like users will have less
freedom here. But it's only about excludeOnly keys. Don't know if we
need to worry about it?
Best regards,
Arseniy Mukhin
Arseniy Mukhin <arseniy.mukhin.dev@gmail.com> writes:
> Good point, thanks for the explanation. I forgot that there can be
> many attributes. And I agree, the more determinism in the system, the
> easier it is to work with it and the less room for bugs. OTOH it seems
> from the performance POV we want to have the stricter keys to be the
> first so we do less work and fail fast on the first keys. It looks
> like these two rules (excludeOnly keys LAST and more restrictive keys
> FIRST) are kind of in conflict with each other. I tried to do some
> experiments and it's seems GIN quite sensitive to it, at least in this
> artificial example:
Yeah, it is. I recall seeing some comments to the effect that
optimizing the order of scan keys would be a good thing, but if there
is any code in there that tries to do so, I'm not seeing where.
Seems like a fertile area for future research.
> With applying patch both queries show the same time (second one). So
> currently the user can tune the query by defining more restrictive
> keys first. With the proposed fix it looks like users will have less
> freedom here.
I think most people would consider it a bug if they have to tune the
order of the WHERE clauses manually. The original statement of the
current bug was basically that: it worked in one order and not the
other.
regards, tom lane
On Wed, Aug 27, 2025 at 5:32 PM Tom Lane <tgl@sss.pgh.pa.us> wrote: > > Arseniy Mukhin <arseniy.mukhin.dev@gmail.com> writes: > > Good point, thanks for the explanation. I forgot that there can be > > many attributes. And I agree, the more determinism in the system, the > > easier it is to work with it and the less room for bugs. OTOH it seems > > from the performance POV we want to have the stricter keys to be the > > first so we do less work and fail fast on the first keys. It looks > > like these two rules (excludeOnly keys LAST and more restrictive keys > > FIRST) are kind of in conflict with each other. I tried to do some > > experiments and it's seems GIN quite sensitive to it, at least in this > > artificial example: > > Yeah, it is. I recall seeing some comments to the effect that > optimizing the order of scan keys would be a good thing, but if there > is any code in there that tries to do so, I'm not seeing where. > Seems like a fertile area for future research. > > > With applying patch both queries show the same time (second one). So > > currently the user can tune the query by defining more restrictive > > keys first. With the proposed fix it looks like users will have less > > freedom here. > > I think most people would consider it a bug if they have to tune the > order of the WHERE clauses manually. The original statement of the > current bug was basically that: it worked in one order and not the > other. > Ok. I checked the patches. The bug is gone. Everything looks correct. Thank you! Best regards, Arseniy Mukhin
On Wed, Aug 27, 2025 at 10:17 PM Arseniy Mukhin <arseniy.mukhin.dev@gmail.com> wrote: > On Wed, Aug 27, 2025 at 5:32 PM Tom Lane <tgl@sss.pgh.pa.us> wrote: > > > > Arseniy Mukhin <arseniy.mukhin.dev@gmail.com> writes: > > > Good point, thanks for the explanation. I forgot that there can be > > > many attributes. And I agree, the more determinism in the system, the > > > easier it is to work with it and the less room for bugs. OTOH it seems > > > from the performance POV we want to have the stricter keys to be the > > > first so we do less work and fail fast on the first keys. It looks > > > like these two rules (excludeOnly keys LAST and more restrictive keys > > > FIRST) are kind of in conflict with each other. I tried to do some > > > experiments and it's seems GIN quite sensitive to it, at least in this > > > artificial example: > > > > Yeah, it is. I recall seeing some comments to the effect that > > optimizing the order of scan keys would be a good thing, but if there > > is any code in there that tries to do so, I'm not seeing where. > > Seems like a fertile area for future research. > > > > > With applying patch both queries show the same time (second one). So > > > currently the user can tune the query by defining more restrictive > > > keys first. With the proposed fix it looks like users will have less > > > freedom here. > > > > I think most people would consider it a bug if they have to tune the > > order of the WHERE clauses manually. The original statement of the > > current bug was basically that: it worked in one order and not the > > other. > > > > Ok. I checked the patches. The bug is gone. Everything looks correct. +1 Sorry for being late to the party. I skim through the thread and read the patches. Looks correct for me. ------ Regards, Alexander Korotkov Supabase