Re: [PATCH] Fix for slow GIN index queries when "gin_fuzzy_search_limit" setting is relatively small for large tables - Mailing list pgsql-hackers

=?UTF-8?B?QWTDqQ==?= <ade.hey@gmail.com> writes:
>> It seems like what you're actually trying
>> to accomplish is to ensure that entryLoadMoreItems's "stepright" path
>> is taken, instead of re-descending the index from the root.

> What I was primarily trying to do is make sure that when entryLoadMoreItems
> is called, it loads new items that it didn't load previously, which would
> occur in special cases. But the solution to that goal does result in the
> "stepright" path being used.

Oh, hm, now I see what you mean: as things stand, it's likely to
repeatedly (and very expensively) reload the same page we were
already on, until the random dropItem() test finally accepts some
item from that page.  Ick.

I think though that the fix can be a bit less messy than you have here,
because advancePast is just a local variable in entryGetItem, so we
can overwrite it without any problem.  So what I want to do is just
update it to equal entry->curItem before looping around.  But shoving
that assignment into the while-condition was too ugly for my taste
(and no, I didn't like your assignment there either).  So I ended up
refactoring the do-loop into a for-loop with internal break conditions,
as attached.

I also made the posting-list case handle reduction in the same way,
and for good measure changed the bitmap-result case to look similar,
which caused me to notice that it had a bug too: the "continue" case
within that loop failed to reset gotitem = false as it should,
if we'd looped around after rejecting an item due to reduceResult.
As far as I can see, that would lead to returning the previously-
rejected curItem value, which isn't fatal but it's still wrong.
So I just got rid of the gotitem variable altogether; it really
wasn't helping with either clarity or correctness.

This patch also adds a couple of test cases so that we have more
code coverage in this area.  The overall coverage of ginget.c
is still mighty lame, but at least we're going through some of
these lines that we weren't before.

I'm inclined to back-patch this.  Given how fuzzy the definition
of gin_fuzzy_search_limit is, it seems unlikely that anyone would
be depending on the current buggy behavior.

            regards, tom lane

diff --git a/src/backend/access/gin/ginget.c b/src/backend/access/gin/ginget.c
index 50fe38b..c18ba87 100644
--- a/src/backend/access/gin/ginget.c
+++ b/src/backend/access/gin/ginget.c
@@ -813,9 +813,8 @@ entryGetItem(GinState *ginstate, GinScanEntry entry,
         /* A bitmap result */
         BlockNumber advancePastBlk = GinItemPointerGetBlockNumber(&advancePast);
         OffsetNumber advancePastOff = GinItemPointerGetOffsetNumber(&advancePast);
-        bool        gotitem = false;

-        do
+        for (;;)
         {
             /*
              * If we've exhausted all items on this block, move to next block
@@ -864,7 +863,6 @@ entryGetItem(GinState *ginstate, GinScanEntry entry,
                  * estimate number of results on this page to support correct
                  * reducing of result even if it's enabled.
                  */
-                gotitem = true;
                 break;
             }

@@ -877,7 +875,7 @@ entryGetItem(GinState *ginstate, GinScanEntry entry,
                 /*
                  * First, do a quick check against the last offset on the
                  * page. If that's > advancePast, so are all the other
-                 * offsets.
+                 * offsets, so just go back to the top to get the next page.
                  */
                 if (entry->matchResult->offsets[entry->matchResult->ntuples - 1] <= advancePastOff)
                 {
@@ -894,8 +892,11 @@ entryGetItem(GinState *ginstate, GinScanEntry entry,
                            entry->matchResult->blockno,
                            entry->matchResult->offsets[entry->offset]);
             entry->offset++;
-            gotitem = true;
-        } while (!gotitem || (entry->reduceResult == true && dropItem(entry)));
+
+            /* Done unless we need to reduce the result */
+            if (!entry->reduceResult || !dropItem(entry))
+                break;
+        }
     }
     else if (!BufferIsValid(entry->buffer))
     {
@@ -903,7 +904,7 @@ entryGetItem(GinState *ginstate, GinScanEntry entry,
          * A posting list from an entry tuple, or the last page of a posting
          * tree.
          */
-        do
+        for (;;)
         {
             if (entry->offset >= entry->nlist)
             {
@@ -913,13 +914,20 @@ entryGetItem(GinState *ginstate, GinScanEntry entry,
             }

             entry->curItem = entry->list[entry->offset++];
-        } while (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0);
-        /* XXX: shouldn't we apply the fuzzy search limit here? */
+
+            /* If we're not past advancePast, keep scanning */
+            if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
+                continue;
+
+            /* Done unless we need to reduce the result */
+            if (!entry->reduceResult || !dropItem(entry))
+                break;
+        }
     }
     else
     {
         /* A posting tree */
-        do
+        for (;;)
         {
             /* If we've processed the current batch, load more items */
             while (entry->offset >= entry->nlist)
@@ -935,8 +943,20 @@ entryGetItem(GinState *ginstate, GinScanEntry entry,

             entry->curItem = entry->list[entry->offset++];

-        } while (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0 ||
-                 (entry->reduceResult == true && dropItem(entry)));
+            /* If we're not past advancePast, keep scanning */
+            if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
+                continue;
+
+            /* Done unless we need to reduce the result */
+            if (!entry->reduceResult || !dropItem(entry))
+                break;
+
+            /*
+             * Advance advancePast (critical for good performance of
+             * entryLoadMoreItems), and keep scanning
+             */
+            advancePast = entry->curItem;
+        }
     }
 }

diff --git a/src/test/regress/expected/gin.out b/src/test/regress/expected/gin.out
index e3c4805..83de522 100644
--- a/src/test/regress/expected/gin.out
+++ b/src/test/regress/expected/gin.out
@@ -35,6 +35,44 @@ insert into gin_test_tbl select array[1, 2, g] from generate_series(1, 1000) g;
 insert into gin_test_tbl select array[1, 3, g] from generate_series(1, 1000) g;
 delete from gin_test_tbl where i @> array[2];
 vacuum gin_test_tbl;
+-- Test for "rare && frequent" searches
+explain (costs off)
+select count(*) from gin_test_tbl where i @> array[1, 999];
+                      QUERY PLAN
+-------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on gin_test_tbl
+         Recheck Cond: (i @> '{1,999}'::integer[])
+         ->  Bitmap Index Scan on gin_test_idx
+               Index Cond: (i @> '{1,999}'::integer[])
+(5 rows)
+
+select count(*) from gin_test_tbl where i @> array[1, 999];
+ count
+-------
+     3
+(1 row)
+
+-- Very weak test for gin_fuzzy_search_limit
+set gin_fuzzy_search_limit = 1000;
+explain (costs off)
+select count(*) > 0 as ok from gin_test_tbl where i @> array[1];
+                    QUERY PLAN
+---------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on gin_test_tbl
+         Recheck Cond: (i @> '{1}'::integer[])
+         ->  Bitmap Index Scan on gin_test_idx
+               Index Cond: (i @> '{1}'::integer[])
+(5 rows)
+
+select count(*) > 0 as ok from gin_test_tbl where i @> array[1];
+ ok
+----
+ t
+(1 row)
+
+reset gin_fuzzy_search_limit;
 -- Test optimization of empty queries
 create temp table t_gin_test_tbl(i int4[], j int4[]);
 create index on t_gin_test_tbl using gin (i, j);
diff --git a/src/test/regress/sql/gin.sql b/src/test/regress/sql/gin.sql
index 836717c..abe3575 100644
--- a/src/test/regress/sql/gin.sql
+++ b/src/test/regress/sql/gin.sql
@@ -35,6 +35,22 @@ insert into gin_test_tbl select array[1, 3, g] from generate_series(1, 1000) g;
 delete from gin_test_tbl where i @> array[2];
 vacuum gin_test_tbl;

+-- Test for "rare && frequent" searches
+explain (costs off)
+select count(*) from gin_test_tbl where i @> array[1, 999];
+
+select count(*) from gin_test_tbl where i @> array[1, 999];
+
+-- Very weak test for gin_fuzzy_search_limit
+set gin_fuzzy_search_limit = 1000;
+
+explain (costs off)
+select count(*) > 0 as ok from gin_test_tbl where i @> array[1];
+
+select count(*) > 0 as ok from gin_test_tbl where i @> array[1];
+
+reset gin_fuzzy_search_limit;
+
 -- Test optimization of empty queries
 create temp table t_gin_test_tbl(i int4[], j int4[]);
 create index on t_gin_test_tbl using gin (i, j);