Re: [HACKERS] GIN improvements

От:

Neil Conway <neilc@samurai.com>

Дата:

9 июля 2008 г. в 15:32:46

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

Re: [HACKERS] GIN improvements

От:

Tom Lane <tgl@sss.pgh.pa.us>

Дата:

8 июля 2008 г. в 15:51:59

Teodor Sigaev  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

Re: GIN improvements

От:

Alvaro Herrera <alvherre@commandprompt.com>

Дата:

8 июня 2008 г. в 19:26:41

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.

Re: GIN improvements

От:

Alvaro Herrera <alvherre@commandprompt.com>

Дата:

8 июня 2008 г. в 19:47:00

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.

Re: GIN improvements

От:

Alvaro Herrera <alvherre@commandprompt.com>

Дата:

7 июля 2008 г. в 10:45:48

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.

Re: GIN improvements

От:

Alvaro Herrera <alvherre@commandprompt.com>

Дата:

7 июля 2008 г. в 11:03:52

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

Re: [HACKERS] GIN improvements

От:

Josh Berkus <josh@agliodbs.com>

Дата:

9 июля 2008 г. в 15:49:38

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

Re: GIN improvements

От:

Tom Lane <tgl@sss.pgh.pa.us>

Дата:

11 июля 2008 г. в 18:09:42

Teodor Sigaev  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

Re: GIN improvements

От:

Tom Lane <tgl@sss.pgh.pa.us>

Дата:

17 июня 2008 г. в 15:36:39

Teodor Sigaev  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

GIN improvements

От:

Teodor Sigaev <teodor@sigaev.ru>

Дата:

31 мая 2008 г. в 00:56:00


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/

Re: GIN improvements

От:

Teodor Sigaev <teodor@sigaev.ru>

Дата:

6 июня 2008 г. в 10:54:35


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

Re: GIN improvements

От:

"Heikki Linnakangas" <heikki@enterprisedb.com>

Дата:

6 июня 2008 г. в 11:02:33

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

Re: GIN improvements

От:

Teodor Sigaev <teodor@sigaev.ru>

Дата:

6 июня 2008 г. в 11:16:55

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

Re: GIN improvements

От:

Teodor Sigaev <teodor@sigaev.ru>

Дата:

10 июня 2008 г. в 08:23:25

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

Re: GIN improvements

От:

Teodor Sigaev <teodor@sigaev.ru>

Дата:

10 июня 2008 г. в 08:38:45

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

Re: GIN improvements

От:

Teodor Sigaev <teodor@sigaev.ru>

Дата:

17 июня 2008 г. в 15:31:09


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

Re: GIN improvements

От:

Teodor Sigaev <teodor@sigaev.ru>

Дата:

2 июля 2008 г. в 15:13:31

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/

Multi-column GIN

От:

"Heikki Linnakangas" <heikki@enterprisedb.com>

Дата:

4 июля 2008 г. в 05:26:11

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

Re: Multi-column GIN

От:

Teodor Sigaev <teodor@sigaev.ru>

Дата:

4 июля 2008 г. в 05:41:48

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

Re: GIN improvements

От:

Teodor Sigaev <teodor@sigaev.ru>

Дата:

7 июля 2008 г. в 10:58:36

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

Re: [HACKERS] GIN improvements

От:

Teodor Sigaev <teodor@sigaev.ru>

Дата:

8 июля 2008 г. в 15:43:32

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

Re: [HACKERS] GIN improvements

От:

Teodor Sigaev <teodor@sigaev.ru>

Дата:

11 июля 2008 г. в 19:59:17

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

Re: [HACKERS] GIN improvements

От:

Teodor Sigaev <teodor@sigaev.ru>

Дата:

13 июля 2008 г. в 18:05:30

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/

Re: Multi-column GIN

От:

Oleg Bartunov <oleg@sai.msu.su>

Дата:

4 июля 2008 г. в 06:13:28

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