Re: BUG #19031: pg_trgm infinite loop on certain cases

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);
     }

     /*