Re: BUG #18831: Particular queries using gin-indexes are not interruptible, resulting is resource usage concerns. - Mailing list pgsql-bugs

PG Bug reporting form <noreply@postgresql.org> writes:
> As part of checking why some of the queries were not interruptible (even
> though statement_timeout was set), I was able to reduce it to something
> generic, as the usage of a gin index and the ?| operator. 

Thanks for the report.  It looks like the issue boils down to trying
to do a GIN index search with a very large array on the RHS of the
?| operator.  extractQuery extracts all the array elements as search
keys, and then we spend O(N^2) time in a very stupid de-duplication
loop in ginFillScanEntry.  Also, if we get past that, there's O(N^2)
work in startScanKey.

It's not hard to remove the O(N^2) behavior in ginFillScanEntry:
the de-duplication is just an optimization AFAICS, and we can stop
doing it once there are too many keys.  A more principled approach
would be to sort the keys and then just compare adjacent ones to
de-dup, but I seriously doubt it's worth the extra code that
would be needed.

Half of the problem in startScanKey is just wasted work: it
re-initializes the entire entryRes[] array for each required-key
probe, when it actually would take less code to incrementally
update the array.  However, the other half is that we are doing
up to nentries calls of the triConsistentFn, which may be doing
O(nentries) work itself per call --- and indeed is doing so in
this specific case.  I don't see any solution for that that
doesn't involve changes in the API spec for GIN opclasses.
It does seem like a pretty bad way to be doing things for
operators that have simple AND or OR semantics, where we could
know the answer in constant time if we only had an API for it.
So maybe it's worth trying to do something about that, but don't
hold your breath.

For now I propose the attached, which bounds ginFillScanEntry's
de-dup efforts at 1000 keys, fixes the silly coding in startScanKey,
and adds a CHECK_FOR_INTERRUPTS in the startScanKey loop to cover
the fact that it's still O(N^2) in the worst case.  With this
I don't notice any objectionable delay in response to cancel
interrupts.  Also, while it's still O(N^2) in the end,
there's a pretty nice speedup for mid-size problems:
NOTICE:  Query for 10000/ 200000 took      6.957140 s
vs
NOTICE:  Query for 10000/ 200000 took    649.409895 s

            regards, tom lane

diff --git a/src/backend/access/gin/ginget.c b/src/backend/access/gin/ginget.c
index f3b19d280c3..4a56f19390d 100644
--- a/src/backend/access/gin/ginget.c
+++ b/src/backend/access/gin/ginget.c
@@ -558,16 +558,18 @@ startScanKey(GinState *ginstate, GinScanOpaque so, GinScanKey key)
         qsort_arg(entryIndexes, key->nentries, sizeof(int),
                   entryIndexByFrequencyCmp, key);

+        for (i = 1; i < key->nentries; i++)
+            key->entryRes[entryIndexes[i]] = GIN_MAYBE;
         for (i = 0; i < key->nentries - 1; i++)
         {
             /* Pass all entries <= i as FALSE, and the rest as MAYBE */
-            for (j = 0; j <= i; j++)
-                key->entryRes[entryIndexes[j]] = GIN_FALSE;
-            for (j = i + 1; j < key->nentries; j++)
-                key->entryRes[entryIndexes[j]] = GIN_MAYBE;
+            key->entryRes[entryIndexes[i]] = GIN_FALSE;

             if (key->triConsistentFn(key) == GIN_FALSE)
                 break;
+
+            /* Make this loop interruptible in case there are many keys */
+            CHECK_FOR_INTERRUPTS();
         }
         /* i is now the last required entry. */

diff --git a/src/backend/access/gin/ginscan.c b/src/backend/access/gin/ginscan.c
index 63ded6301e2..a50694f6776 100644
--- a/src/backend/access/gin/ginscan.c
+++ b/src/backend/access/gin/ginscan.c
@@ -68,8 +68,12 @@ ginFillScanEntry(GinScanOpaque so, OffsetNumber attnum,
      *
      * Entries with non-null extra_data are never considered identical, since
      * we can't know exactly what the opclass might be doing with that.
+     *
+     * Also, give up de-duplication once we have 1000 entries.  That avoids
+     * spending O(N^2) time on probably-fruitless de-duplication of large
+     * search-key sets.
      */
-    if (extra_data == NULL)
+    if (extra_data == NULL && so->totalentries < 1000)
     {
         for (i = 0; i < so->totalentries; i++)
         {