Thread: [PATCH] Fix for slow GIN index queries when "gin_fuzzy_search_limit"setting is relatively small for large tables

=?UTF-8?B?QWTDqQ==?= <ade.hey@gmail.com> writes:
> Like the title says, using "gin_fuzzy_search_limit" degrades speed when it
> has a relatively low setting.
> ...
> Attached is SQL to test and observe this issue and also attached is a patch
> I want to eventually submit to a commitfest.

I took a brief look at this.  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.  Okay,
I can see why that'd be a big win, but why are you tying it to the
dropItem behavior?  It should apply any time we're iterating this loop
more than once.  IOW, it seems to me like the logic about when to step
right is just kinda broken, and this is a band-aid rather than a full fix.
The performance hit is worse for fuzzy-search mode because it will
iterate the loop more (relative to the amount of work done elsewhere),
but there's still a potential for wasted work.

Actually, a look at the code coverage report shows that the
not-step-right path is never taken at all in our standard regression
tests.  Maybe that just says bad things about the tests' coverage, but
now I'm wondering whether we could just flush that code path altogether,
and assume that we should always step right at this point.

[ cc'ing heikki and alexander, who seem to have originated that code
at 626a120656a75bf4fe64b1d0d83c23cb38d3771a.  The commit message says
it saves a lot of I/O, but I'm wondering if this report disproves that.
In any case the lack of test coverage is pretty damning. ]

While we're here, what do you think about the comment in the other
code branch just above:

        /* XXX: shouldn't we apply the fuzzy search limit here? */

I'm personally inclined to suspect that the fuzzy-search business has
got lots of bugs, which haven't been noticed because (a) it's so squishily
defined that one can hardly tell whether a given result is buggy or not,
and (b) nearly nobody uses it anyway (possibly not unrelated to (a)).
As somebody who evidently is using it, you're probably more motivated
to track down bugs than the rest of us.

            regards, tom lane

=?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);

I wrote:
> 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.

And done.  Thanks for the bug report and patch!

            regards, tom lane