Re: GIN improvements part2: fast scan - Mailing list pgsql-hackers

On 02/05/2014 12:42 PM, Alexander Korotkov wrote:

Attached patch is "light" version of fast scan. It does extra consistent
function calls only on startScanKey, no extra calls during scan of the
index.
It finds subset of rarest entries absence of which guarantee false
consistent function result.

Sounds good. Since the extra consistent calls are only performed at startup, it's unlikely to cause any noticeable performance regression, even when it's not helping.

I've run real-life tests based of postgresql.org logs (33318 queries). Here
is a table with summary time of running whole test case.

=# select method, sum(time) from test_result group by method order by
method;
        method        |       sum
---------------------+------------------
  fast-scan-11        | 126916.111999999
  fast-scan-light     |       137321.211
  heikki              |       466751.693
  heikki-true-ternary | 454113.623999997
  master              |       446976.288
(6 rows)

where 'heikki' is gin-ternary-logic binary-heap
preconsistent-only-on-new-page.patch and 'heikki-true-ternary' is version
with my catalog changes promoting ternary consistent function to opclass.

Looks good.

We can see fast-scan-light gives almost same performance benefit on "&"
queries. However, I test only CPU effect, not IO effect.
Any thoughts?

This test doesn't handle lossy-pages correctly:

                /*
                 * Check if all items marked as scanEntryUseForSkip is not present in
                 * minItem. If so, we can correct advancePast.
                 */
                if (ginCompareItemPointers(&minItem, &minItemSkip) < 0)
                {
                        advancePast = minItemSkip;
                        advancePast.ip_posid--;
                        continue;
                }

If minItemSkip is a lossy page, we skip all exact items on the same page. That's wrong, here's a test case to demonstrate:

CREATE TABLE foo (ts tsvector);
INSERT INTO foo SELECT to_tsvector('foo bar'||g) from generate_series(1, 1000000) g;
CREATE INDEX i_foo ON foo USING gin (ts);

set work_mem='64'; -- to force lossy pages
-- should return 111111
select count(*) from foo where ts @@ to_tsquery('foo & bar4:*');

After some fiddling (including fixing the above), I ended up with the attached version of your patch. I still left out the catalog changes, again not because I don't think we should have them, but to split this into smaller patches that can be reviewed separately. I extended the "both ways" shim function to work with more than one "maybe" input. Of course, that is O(n^2), where n is the number of "maybe" arguments, so that won't scale, but it's OK for testing purposes. And many if not most real world queries, too.

I had a very hard time understanding what it really means for an entry to be in the scanEntryUseForSkip array. What does it mean to "use" an entry for skipping?

So I refactored that logic, to hopefully make it more clear. In essence, the entries are divided into two groups, required and other items. If none of the entries in the required set are true, then we know that the overall qual cannot match. See the comments for a more detailed explanation. I'm not wedded to the term "required" here; one might think that *all* the entries in the required set must be TRUE for a match, while it's actually that at least one of them must be TRUE.

In keyGetItem, we fetch the minimum item among all the entries in the requiredEntries set. That's the next item we're going to return, regardless of any items in otherEntries set. But before calling the consistent function, we advance the other entries up to that point, so that we know whether to pass TRUE or FALSE to the consistent function. IOW, otherEntries only provide extra information for the consistent function to decide if we have a match or not - they don't affect which items we return to the caller.

I think this is pretty close to committable state now. I'm slightly disappointed that we can't do the skipping in more scenarios. For example, in "foo & bar", we can currently skip "bar" entry up to the next "foo", but we cannot skip "foo" up to the next "bar". But this is fairly simple, and since we sort the entries by estimated frequency, should already cover all the pathological "rare & frequent" type queries. So that's OK.