Re: GIN improvements part 3: ordering in index
| От | Alexander Korotkov |
|---|---|
| Тема | Re: GIN improvements part 3: ordering in index |
| Дата | |
| Msg-id | CAPpHfdvJ5Z=wRGVGmeOkkmbkjRo9U0s8sKfkSLQAoWnC-gcxTw@mail.gmail.com обсуждение исходный текст |
| Ответ на | Re: GIN improvements part 3: ordering in index (Heikki Linnakangas <hlinnakangas@vmware.com>) |
| Ответы |
Re: GIN improvements part 3: ordering in index
(Alexander Korotkov <aekorotkov@gmail.com>)
|
| Список | pgsql-hackers |
On Mon, Jun 17, 2013 at 10:27 PM, Heikki Linnakangas <hlinnakangas@vmware.com> wrote:
------
With best regards,
Alexander Korotkov.
On 17.06.2013 15:56, Alexander Korotkov 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.
Вложения
В списке pgsql-hackers по дате отправления: