Improvements of GIN indexes were presented on PGCon 2008. Presentation:
http://www.sigaev.ru/gin/fastinsert_...column_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/

--
Sent via pgsql-patches mailing list (pgsql-patches@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-patches

> 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/

--
Sent via pgsql-patches mailing list (pgsql-patches@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-patches

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

--
Sent via pgsql-patches mailing list (pgsql-patches@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-patches

> 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/

--
Sent via pgsql-patches mailing list (pgsql-patches@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-patches

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.

--
Sent via pgsql-patches mailing list (pgsql-patches@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-patches

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.

--
Sent via pgsql-patches mailing list (pgsql-patches@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-patches

> 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/

--
Sent via pgsql-patches mailing list (pgsql-patches@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-patches

> 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/

--
Sent via pgsql-patches mailing list (pgsql-patches@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-patches

> 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/

--
Sent via pgsql-patches mailing list (pgsql-patches@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-patches

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

--
Sent via pgsql-patches mailing list (pgsql-patches@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-patches