Re: GIN improvements part2: fast scan

On 17.06.2013 15:55, Alexander Korotkov wrote:
> On Sat, Jun 15, 2013 at 2:55 AM, Alexander Korotkov<aekorotkov(at)gmail(dot)com>wrote:
>
>> attached patch implementing "fast scan" technique for GIN. This is second
>> patch of GIN improvements, see the 1st one here:
>>
>> http://www.postgresql.org/message-id/CAPpHfduxv-iL7aedwPW0W5fXrWGAKfxijWM63_hZujaCRxnmFQ@mail.gmail.com
>> This patch allow to skip parts of posting trees when their scan is not
>> necessary. In particular, it solves "frequent_term& rare_term" problem of
>> FTS.
>> It introduces new interface method pre_consistent which behaves like
>> consistent, but:
>> 1) allows false positives on input (check[])
>> 2) allowed to return false positives
>>
>> Some example: "frequent_term& rare_term" becomes pretty fast.
>>
>> create table test as (select to_tsvector('english', 'bbb') as v from
>> generate_series(1,1000000));
>> insert into test (select to_tsvector('english', 'ddd') from
>> generate_series(1,10));
>> create index test_idx on test using gin (v);
>>
>> postgres=# explain analyze select * from test where v @@
>> to_tsquery('english', 'bbb& ddd');
>> QUERY PLAN
>>
>> -----------------------------------------------------------------------------------------------------------------------
>> Bitmap Heap Scan on test (cost=942.75..7280.63 rows=5000 width=17)
>> (actual time=0.458..0.461 rows=10 loops=1)
>> Recheck Cond: (v @@ '''bbb''& ''ddd'''::tsquery)
>> -> Bitmap Index Scan on test_idx (cost=0.00..941.50 rows=5000
>> width=0) (actual time=0.449..0.449 rows=10 loops=1)
>> Index Cond: (v @@ '''bbb''& ''ddd'''::tsquery)
>> Total runtime: 0.516 ms
>> (5 rows)
>>
>
> Attached version of patch has some refactoring and bug fixes.

Good timing, I just started looking at this.

I think you'll need to explain how this works. There are no docs, and
almost no comments.

(and this shows how poorly I understand this, but) Why does this require
the "additional information" patch? What extra information do you store
on-disk, in the additional information?

The pre-consistent method is like the consistent method, but it allows
false positives. I think that's because during the scan, before having
scanned for all the keys, the gin AM doesn't yet know if the tuple
contains all of the keys. So it passes the keys it doesn't yet know
about as 'true' to pre-consistent. Could that be generalized, to pass a
tri-state instead of a boolean for each key to the pre-consistent
method? For each key, you would pass "true", "false", or "don't know". I
think you could then also speed up queries like "!english & bbb".

- Heikki