Re: GIN improvements part2: fast scan

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)