Re: GIN improvements part2: fast scan

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.

- Heikki