Thread: 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.gz > > Changes: > - 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 flushing > > I'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.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. 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. > > http://www.sigaev.ru/misc/multicolumn_gin-0.3.gz 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
Neil, > 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. I have plenty of other stuff I could assign you if you're not needed on GIN. -- --Josh Josh Berkus PostgreSQL @ Sun San Francisco
Teodor Sigaev <teodor@sigaev.ru> writes: > http://www.sigaev.ru/misc/fast_insert_gin-0.7.gz > http://www.sigaev.ru/misc/multicolumn_gin-0.3.gz I've committed the multicolumn one with minor revisions (fix some poor English in docs and comments, add regression-test coverage). Do you need more review of fast_insert yet? It looked like a number of people commented on it already. regards, tom lane
> I've committed the multicolumn one with minor revisions (fix some poor
> English in docs and comments, add regression-test coverage). Do you
Thank you very much.
> need more review of fast_insert yet? It looked like a number of people
> commented on it already.
I should modify it to support/synchronize with multicolumn GIN - both patches
touch the same pieces of code, and I didn't make a single patch to simplify review.
--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/
Updated: http://www.sigaev.ru/misc/fast_insert_gin-0.9.gz > need more review of fast_insert yet? It looked like a number of people > commented on it already. I still havn't clearness of acceptability for suggested aminsertcleanup calling. -- Teodor Sigaev E-mail: teodor@sigaev.ru WWW: http://www.sigaev.ru/