GIN improvements
Improvements of GIN indexes were presented on PGCon 2008. Presentation:
http://www.sigaev.ru/gin/fastinsert_and_multicolumn_GIN.pdf
1) multicolumn GIN
This patch ( http://www.sigaev.ru/misc/multicolumn_gin-0.2.gz ) adds multicolumn
support to GIN. The basic idea is: keys (entries in GIN terminology) extracted
from values are stored in separated tuples along with their column number. In
that case, multicolumn clause is just AND of column's clauses. Unlike other
indexes, the performance of search doesn't depends on what column of index
(first, last, any subset) is used in search clause. This property can be used in
gincostestimate, but I haven't looked on it yet.
2) fast insert into GIN
This patch ( http://www.sigaev.ru/misc/fast_insert_gin-0.4.gz ) implements an
idea of using bulk insert technique, which used at index creation time. Inserted
rows are stored in the linked list of pending pages and inserted to the regular
structure of GIN at vacuum time. The algorithm is shown in presentation, but
insert completion process (vacuum) was significantly reworkes to improve
concurrency. Now, the list of pending page is locked much lesser time - only
during deletion of pages from the list.
Open item:
what is a right time to call insert completion? Currently, it is called by
ginbulkdelete and ginvacuumcleanup, ginvacuumcleanup will call completion if
ginbulkdelete wasn't called. That's not good, but works. Completion process
should started before ginbulkdelete because ginbulkdelete doesn't look on
pending pages at all.
Since insert completion (of any index if that method will exists, I think) runs
fast if number of inserted tuples is a small because it doesn't go through the
whole index, so, IMHO, the existing statistic's fields should not be changed.
That idea, discussed at PGCon, is to have trigger in vacuum which will be fired
if number of inserted tuples becomes big. Now I don't think that the idea is
useful for two reason: for small number of tuples completion is a cheap and it
should be called before ginbulkdelete. IMHO, it's enough to add an optional
method to pg_am (aminsertcleanup, per Tom's suggestion). This method will be
called before ambulkdelete and amvacuumcleanup. Opinions, objections, suggestions?
On presentation some people were interested on how our changes affect the
search speed after rows insert. The tests are below: We use the same tables as
in presentation and measure search times ( after insertion of some rows ) before
and after vacuum. All times are in ms. Test tables contain 100000 rows, in the
first table the number of elements in array is 100 with cardinality = 500,
second - 100 and 500000, last - 1000 and 500.
Insert 10000 into table with 100000 rows (10%)
| v && '{v1}' |
-----------------+---------+--------+ found
| novac-d | vac-d | rows
-----------------+---------+--------+-------
n:100, c:500 | 118 | 35 | 19909
n:100, c:500000 | 95 | 0.7 | 25
n:1000, c:500 | 380 | 79 | 95211
Insert 1000 into table with 100000 rows (1%)
| v && '{v1}' |
-----------------+---------+--------+ found
| novac-d | vac-d | rows
-----------------+---------+--------+-------
n:100, c:500 | 40 | 31 | 18327
n:100, c:500000 | 13 | 0.5 | 26
n:1000, c:500 | 102 | 71 | 87499
Insert 100 into table with 100000 rows (0.1%)
| v && '{v1}' |
-----------------+---------+--------+ found
| novac-d | vac-d | rows
-----------------+---------+--------+-------
n:100, c:500 | 32 | 31 | 18171
n:100, c:500000 | 1.7 | 0.5 | 20
n:1000, c:500 | 74 | 71 | 87499
Looking at result it's easy to conclude that:
- time of search pending list is O(number of inserted rows), i.e., search time
is equal to (time of search in GIN) + K1 * (number of inserted rows after the
last vacuum).
- search time is O(average length of indexed columns). Observations made above
is also applicable here.
- significant performance gap starts around 5-10% of inserts or near 500-1000
inserts. This is very depends on specific dataset.
Notice, that insert performance to GIN was increased up to 10 times. See
exact results in presentation.
Do we need to add option to control this (fast insertion) feature?
If so, what is a default value? It's not clear to me.
Note: These patches are mutually exclusive because they touch the same pieces
of code and I'm too lazy to manage several depending patches. I don't see any
problem to join patches to one, but IMHO it will be difficult to review.
--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/
2) fast insert into GIN
New version:
http://www.sigaev.ru/misc/fast_insert_gin-0.6.gz
Changes:
- added option FASTUPDATE=(1|t|true|on|enable|0|f|false|disable) for
CREATE/ALTER command for GIN indexes
- Since there wasn't any comments on first email, pg_am.aminsertcleanup optional
method was introduced.
- added documentation
Suppose, patch is ready to review/commit...
--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/
Teodor Sigaev wrote:
2) fast insert into GIN
New version:
http://www.sigaev.ru/misc/fast_insert_gin-0.6.gzChanges:
- added option FASTUPDATE=(1|t|true|on|enable|0|f|false|disable) for
CREATE/ALTER command for GIN indexes
I think we should try to make it automatic. I'm not sure how.
How about having a constant sized "fastupdate" buffer, of say 100 rows
or a fixed number of pages, and when that becomes full, the next
inserter will have to pay the price of updating the index and flushing
the buffer. To keep that overhead out of the main codepath, we could
make autovacuum to flush the buffers periodically.
--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com
How about having a constant sized "fastupdate" buffer, of say 100 rows
or a fixed number of pages, and when that becomes full, the next
inserter will have to pay the price of updating the index and flushing
I'm not sure that is acceptable because flushing pending list may take several
seconds in unpredictable moment.
the buffer. To keep that overhead out of the main codepath, we could
make autovacuum to flush the buffers periodically.
Do you mean that GIN sends a "smoke signal" to the autovacuum launcher process
to ask about vacuum?
--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/
Teodor Sigaev wrote:
How about having a constant sized "fastupdate" buffer, of say 100 rows
or a fixed number of pages, and when that becomes full, the next
inserter will have to pay the price of updating the index and flushingI'm not sure that is acceptable because flushing pending list may take
several seconds in unpredictable moment.
Perhaps we could make the fixed-size buffer be of size X, and trigger
autovac on X/3 or some such, to give it enough slack so that it would be
very unlikely to be processed by user processes.
the buffer. To keep that overhead out of the main codepath, we could
make autovacuum to flush the buffers periodically.Do you mean that GIN sends a "smoke signal" to the autovacuum launcher
process to ask about vacuum?
Something like that, yes.
Currently, autovac only uses pgstats as trigger for actions. Maybe we
could use something else (say, a flag in shared memory?), or just stash
the info that the index needs to be processed in pgstats and have
autovac examine it.
--
Alvaro Herrera http://www.CommandPrompt.com/
The PostgreSQL Company - Command Prompt, Inc.
Teodor Sigaev wrote:
2) fast insert into GIN
New version:
http://www.sigaev.ru/misc/fast_insert_gin-0.6.gzChanges:
- added option FASTUPDATE=(1|t|true|on|enable|0|f|false|disable) for
CREATE/ALTER command for GIN indexes
- Since there wasn't any comments on first email, pg_am.aminsertcleanup optional
method was introduced.
Hmm, this alters the semantics of amvacuumcleanup a bit. Currently in
btvacuumcleanup we invoke btvacuumscan only if btbulkdelete was not
called. This is noticed by observing whether the "stats" pointer is
NULL. However, the patch changes this a bit because
index_vacuum_cleanup is called with the results of index_insert_cleanup,
instead of a plain NULL.
Right now this is not a problem because there is no insert_cleanup
function for btree, but I wonder if we should clean it up.
FWIW there's a typo in catalogs.sgml (finction -> function)
What's the use of the FASTUPDATE parameter? Is there a case when a user
is interested in turning it off?
--
Alvaro Herrera http://www.CommandPrompt.com/
The PostgreSQL Company - Command Prompt, Inc.
Perhaps we could make the fixed-size buffer be of size X, and trigger
autovac on X/3 or some such, to give it enough slack so that it would be
very unlikely to be processed by user processes.Do you mean that GIN sends a "smoke signal" to the autovacuum launcher
process to ask about vacuum?Currently, autovac only uses pgstats as trigger for actions. Maybe we
could use something else (say, a flag in shared memory?), or just stash
the info that the index needs to be processed in pgstats and have
autovac examine it.
Flag in pgstats or shared memory is most reasonable solution. Using size of
buffers is not very good because other indexes might use another technics for
delayed insert and use another trigger criteria.
Suppose, the best technic for GIN will be a setting flag by search procedure -
if time of scanning pending pages is eqial to time of search in regular
structure then it's time to call insert cleanup.
--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/
Right now this is not a problem because there is no insert_cleanup
function for btree, but I wonder if we should clean it up.
Look at gistbulkdelete and gistvacuumcleanup, first function wants to send a
bool flag to second one and they use GiSTBulkDelete structure instead of usual
IndexBulkDeleteResult. When it will be needed btree may use the same method.
FWIW there's a typo in catalogs.sgml (finction -> function)
Thank you, will fix.
What's the use of the FASTUPDATE parameter? Is there a case when a user
is interested in turning it off?
Yeah - when time of search is much-much more important (or crucial) than
insertion time. Or table stores read-only values.
--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/
1) multicolumn GIN
Unlike other indexes, the performance of search
doesn't depends on what column of index (first, last, any subset) is
used in search clause. This property can be used in gincostestimate, but
I haven't looked on it yet.
After some playing I didn't find any mentions in *costestimate function about
difference of cost estimation between first and any other columns in clauses,
so, IMHO, issue above isn't an issue. :)
So, I didn't see any comments/objections and I intend to commit this patch for
next two days and synchronize 'fast insert into GIN' patch with CVS.
Objections?
--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/
Teodor Sigaev <teodor@sigaev.ru> writes:
So, I didn't see any comments/objections and I intend to commit this patch for
next two days and synchronize 'fast insert into GIN' patch with CVS.
Objections?
I think it hasn't really gotten reviewed at all (certainly not by me).
If you want other people to look it over you should wait for next
month's commit fest.
regards, tom lane
Sync with current CVS HEAD and post in hackers- too because patches- close to
the closing.
http://www.sigaev.ru/misc/fast_insert_gin-0.7.gz
http://www.sigaev.ru/misc/multicolumn_gin-0.3.gz
--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/
Dumb question:
What's the benefit of a multi-column GIN index over multiple
single-column GIN indexes?
--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com
What's the benefit of a multi-column GIN index over multiple
single-column GIN indexes?
Page 12 from presentation on PgCon
(http://www.sigaev.ru/gin/fastinsert_and_multicolumn_GIN.pdf):
Multicolumn index vs. 2 single column indexes
Size: 539 Mb 538 Mb
Speed: *1.885* ms 4.994 ms
Index: ~340 s ~200 s
Insert: 72 s/10000 66 s/10000--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/
On Fri, 4 Jul 2008, Teodor Sigaev wrote:
What's the benefit of a multi-column GIN index over multiple
single-column GIN indexes?Page 12 from presentation on PgCon
(http://www.sigaev.ru/gin/fastinsert_and_multicolumn_GIN.pdf):Multicolumn index vs. 2 single column indexes
Size: 539 Mb 538 Mb Speed: *1.885* ms 4.994 ms Index: ~340 s ~200 s Insert: 72 s/10000 66 s/10000
Well, another reason is a index feature-completeness
Regards,
Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83
Teodor Sigaev wrote:
Sync with current CVS HEAD and post in hackers- too because patches-
close to the closing.
I looked this over and it looks good in general. I was only wondering
about for single-column indexes -- we're storing attribute numbers too,
right? Would it be too difficult to strip them out in that case?
--
Alvaro Herrera http://www.CommandPrompt.com/
The PostgreSQL Company - Command Prompt, Inc.
I looked this over and it looks good in general. I was only wondering
about for single-column indexes -- we're storing attribute numbers too,
right?
No, GinState->oneCol field signals to GinFormTuple and
gin_index_getattr/gintuple_get_attrnum about actual storage.
Single column index is binary compatible with current index :)
--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/
Teodor Sigaev wrote:
I looked this over and it looks good in general. I was only wondering
about for single-column indexes -- we're storing attribute numbers too,
right?No, GinState->oneCol field signals to GinFormTuple and
gin_index_getattr/gintuple_get_attrnum about actual storage.Single column index is binary compatible with current index :)
Ah, neat!
--
Alvaro Herrera http://www.CommandPrompt.com/
PostgreSQL Replication, Consulting, Custom Development, 24x7 support
I looked this over and it looks good in general.
May I think that patch passed review and commit it?
--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/
Teodor Sigaev <teodor@sigaev.ru> writes:
I looked this over and it looks good in general.
May I think that patch passed review and commit it?
I'd still like to take a look.
regards, tom lane
On Tue, 2008-07-08 at 14:51 -0400, Tom Lane wrote:
I'd still like to take a look.
I was tasked with reviewing this for the current commit fest, although
so far I've just been working on grokking the rest of the GIN code. But
if you'd like to review it instead, that's fine with me.
-Neil
