GIN improvements part2: fast scan

From: Alexander Korotkov <aekorotkov(at)gmail(dot)com>
To: pgsql-hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: GIN improvements part2: fast scan
Date: 2013-06-14 22:55:17
Message-ID: CAPpHfdvftaJq7www381naLw1=4u0h+qpXgWvNhcEB9HMVywbGg@mail.gmail.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

Hackes,

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)

------
With best regards,
Alexander Korotkov.

Attachment Content-Type Size
gin_fast_scan.1.patch.gz application/x-gzip 6.2 KB

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Tom Lane 2013-06-14 22:58:05 Re: stray SIGALRM
Previous Message Andres Freund 2013-06-14 22:51:47 Re: changeset generation v5-01 - Patches & git tree