Re: GIN improvements part 3: ordering in index

On Mon, Jun 17, 2013 at 10:27 PM, Heikki Linnakangas <
hlinnakangas(at)vmware(dot)com> wrote:

> On 17.06.2013 15:56, Alexander Korotkov wrote:
>
>> On Sat, Jun 15, 2013 at 3:02 AM, Alexander Korotkov<aekorotkov(at)gmail(dot)com>
>> **wrote:
>>
>> This patch introduces new interface method of GIN which takes same
>>> arguments as consistent but returns float8.
>>> float8 gin_ordering(bool check[], StrategyNumber n, Datum query, int32
>>> nkeys, Pointer extra_data[], bool *recheck, Datum queryKeys[], bool
>>> nullFlags[], Datum addInfo[], bool addInfoIsNull[])
>>> This patch implements gingettuple method which can return ordering data
>>> using KNN infrastructure. Also it introduces>< operator for fts which
>>> support ordering in GIN index. Some example:
>>>
>>> postgres=# explain analyze select * from dblp_titles2 where tsvector @@
>>> to_tsquery('english', 'statistics') order by tsvector><
>>> to_tsquery('english', 'statistics') limit 10;
>>> QUERY
>>> PLAN
>>>
>>> ------------------------------**------------------------------**
>>> ------------------------------**------------------------------**
>>> -------------------------
>>> Limit (cost=12.00..48.22 rows=10 width=136) (actual time=6.999..7.120
>>> rows=10 loops=1)
>>> -> Index Scan using dblp_titles2_idx on dblp_titles2
>>> (cost=12.00..43003.03 rows=11868 width=136) (actual time=6.996..7.115
>>> rows=10 loops=1)
>>> Index Cond: (tsvector @@ '''statist'''::tsquery)
>>> Order By: (tsvector>< '''statist'''::tsquery)
>>> Total runtime: 7.556 ms
>>> (5 rows)
>>>
>>>
>> Attached version of patch has some refactoring and bug fixes.
>>
>
> Thanks. There are no docs changes and not many comments, that needs to be
> fixed, but I think I understand how it works:
>
> On the first call to gingettuple, the index is first scanned for all the
> matches, which are collected in an array in memory. Then, the array is
> sorted with qsort(), and the matches are returned one by one from the
> sorted array.
>

Right.

That has some obvious limitations. First of all, you can run out of memory.

Yes, it is so. qsort should be replaced with tuplesort.

Secondly, is that really any faster than the plan you get without this
> patch? Ie. scan all the matches with a bitmap index scan, and sort the
> results on the rank function. If it is faster, why?
>

At, first it's obviously much faster when not both heap and index fit into
cache, because of IO. With patch you need only posting trees and posting
lists of requested entries. If query matching significant part of documents
then without patch you will need almost all the heap.
Also it's faster when both heap and index are in the cache. There are some
examples on DBLP paper titles (2.5M titles of 47 average length).

Without patch:
postgres=# explain analyze select id, s from dblp_titles2 where ts @@
to_tsquery('english', 'system') order by ts_rank(ts, to_tsquery('english',
'system')) desc limit 10;
QUERY
PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=60634.15..60634.17 rows=10 width=134) (actual
time=200.204..200.205 rows=10 loops=1)
-> Sort (cost=60634.15..61041.28 rows=162854 width=134) (actual
time=200.202..200.203 rows=10 loops=1)
Sort Key: (ts_rank(ts, '''system'''::tsquery))
Sort Method: top-N heapsort Memory: 28kB
-> Bitmap Heap Scan on dblp_titles2 (cost=1758.12..57114.93
rows=162854 width=134) (actual time=33.592..158.006 rows=168308 loops=1)
Recheck Cond: (ts @@ '''system'''::tsquery)
-> Bitmap Index Scan on dblp_titles2_idx
(cost=0.00..1717.41 rows=162854 width=0) (actual time=27.327..27.327
rows=168308 loops=1)
Index Cond: (ts @@ '''system'''::tsquery)
Total runtime: 200.610 ms
(9 rows)

With patch:
postgres=# explain analyze select id, s from dblp_titles2 where ts @@
to_tsquery('english', 'system') order by ts >< to_tsquery('english',
'system') limit 10;
QUERY
PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=12.00..43.05 rows=10 width=136) (actual time=39.585..39.597
rows=10 loops=1)
-> Index Scan using dblp_titles2_idx on dblp_titles2
(cost=12.00..493681.61 rows=159005 width=136) (actual time=39.584..39.593
rows=10 loops=1)
Index Cond: (ts @@ '''system'''::tsquery)
Order By: (ts >< '''system'''::tsquery)
Total runtime: 40.115 ms
(5 rows)

Without patch:
postgres=# explain analyze select id, s, ts_rank(ts, to_tsquery('english',
'statistics')) from dblp_titles2 where ts @@ to_tsquery('english',
'statistics') order by ts_rank(ts, to_tsquery('english', 'statistics'))
desc limit 10;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=26029.65..26029.67 rows=10 width=134) (actual
time=19.938..19.939 rows=10 loops=1)
-> Sort (cost=26029.65..26055.17 rows=10210 width=134) (actual
time=19.936..19.937 rows=10 loops=1)
Sort Key: (ts_rank(ts, '''statist'''::tsquery))
Sort Method: top-N heapsort Memory: 27kB
-> Bitmap Heap Scan on dblp_titles2 (cost=127.13..25809.01
rows=10210 width=134) (actual time=4.262..16.854 rows=10298 loops=1)
Recheck Cond: (ts @@ '''statist'''::tsquery)
-> Bitmap Index Scan on dblp_titles2_idx
(cost=0.00..124.58 rows=10210 width=0) (actual time=2.887..2.887
rows=10298 loops=1)
Index Cond: (ts @@ '''statist'''::tsquery)
Total runtime: 20.037 ms
(9 rows)

With patch:
postgres=# explain analyze select id, s from dblp_titles2 where ts @@
to_tsquery('english', 'statistics') order by ts >< to_tsquery('english',
'statistics') limit 10;
QUERY
PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=12.00..48.60 rows=10 width=134) (actual time=3.469..3.485
rows=10 loops=1)
-> Index Scan using dblp_titles2_idx on dblp_titles2
(cost=12.00..38919.15 rows=10629 width=134) (actual time=3.469..3.483
rows=10 loops=1)
Index Cond: (ts @@ '''statist'''::tsquery)
Order By: (ts >< '''statist'''::tsquery)
Total runtime: 3.575 ms
(5 rows)

I didn't do detailed profile to know exactly, but I can suppose following
reasons of why performance gain:
1) Don't do bsearch if tsvector, immediately get required word positions
2) Don't check visibility (check only for resulting tuples). However with a
lot of invisible tuples we have to calculate more relevance.
3) Less switching between planner nodes
4) More sequential access to RAM
Actually, I'm not sure about that reasons and probably there is another
reason. But there is no magic, with patch it still honestly get word
positions and calculates relevance. Replacing qsort with tuplesort will add
some overhead, but I doubt that it will change the situation dramatically.

What parts of the previous two patches does this rely on?

It could be possible to implement similar patch completely independently of
other patches. But without additional information you wouldn't be able to
calculate something useful to sort. So, logically it rely on part 1:
additional information.
"Physically" patches I posted are applying only sequentially: part 1 =>
part 2 => part 3.

BTW, patch with more bug fixes is attached.

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