pg.ddx.io pgsql-performance@postgresql.org mailing list archive
help / color / mirror / Atom feedWhy creating GIN table index is so slow than inserting data into empty table with the same index?
4+ messages / 3 participants
[nested] [flat]
* Why creating GIN table index is so slow than inserting data into empty table with the same index?
@ 2009-03-24 00:59 Sergey Burladyan <eshkinkot@gmail.com>
2009-03-24 03:35 ` Re: Why creating GIN table index is so slow than inserting data into empty table with the same index? Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 4+ messages in thread
From: Sergey Burladyan @ 2009-03-24 00:59 UTC (permalink / raw)
To: pgsql-performance
example:
select version();
version
--------------------------------------------------------------------------------------------
PostgreSQL 8.3.6 on i486-pc-linux-gnu, compiled by GCC gcc-4.3.real (Debian 4.3.3-3) 4.3.3
show maintenance_work_mem ;
maintenance_work_mem
----------------------
128MB
create table a (i1 int, i2 int, i3 int, i4 int, i5 int, i6 int);
insert into a select n, n, n, n, n, n from generate_series(1, 100000) as n;
INSERT 0 100000
Время: 570,110 мс
create index arr_gin on a using gin ( (array[i1, i2, i3, i4, i5, i6]) );
CREATE INDEX
Время: 203068,314 мс
truncate a;
drop index arr_gin ;
create index arr_gin on a using gin ( (array[i1, i2, i3, i4, i5, i6]) );
CREATE INDEX
Время: 3,246 мс
insert into a select n, n, n, n, n, n from generate_series(1, 100000) as n;
INSERT 0 100000
Время: 2405,481 мс
select pg_size_pretty(pg_total_relation_size('a')) as total,
pg_size_pretty(pg_relation_size('a')) as table;
total | table
---------+---------
9792 kB | 5096 kB
203068.314 ms VS 2405.481 ms, is this behaviour normal ?
Thanks !
--
Sergey Burladyan
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: Why creating GIN table index is so slow than inserting data into empty table with the same index?
2009-03-24 00:59 Why creating GIN table index is so slow than inserting data into empty table with the same index? Sergey Burladyan <eshkinkot@gmail.com>
@ 2009-03-24 03:35 ` Tom Lane <tgl@sss.pgh.pa.us>
2009-03-24 11:07 ` Re: Why creating GIN table index is so slow than inserting data into empty table with the same index? Heikki Linnakangas <heikki.linnakangas@enterprisedb.com>
0 siblings, 1 reply; 4+ messages in thread
From: Tom Lane @ 2009-03-24 03:35 UTC (permalink / raw)
To: Sergey Burladyan <eshkinkot@gmail.com>; +Cc: Oleg Bartunov <oleg@sai.msu.su>; Teodor Sigaev <teodor@sigaev.ru>; pgsql-performance
Sergey Burladyan <eshkinkot@gmail.com> writes:
> show maintenance_work_mem ;
> maintenance_work_mem
> ----------------------
> 128MB
> create table a (i1 int, i2 int, i3 int, i4 int, i5 int, i6 int);
> insert into a select n, n, n, n, n, n from generate_series(1, 100000) as n;
> create index arr_gin on a using gin ( (array[i1, i2, i3, i4, i5, i6]) );
[ takes forever ]
Seems the reason this is so awful is that the incoming data is exactly
presorted, meaning that the tree structure that ginInsertEntry() is
trying to build degenerates to a linear list (ie, every new element
becomes the right child of the prior one). So the processing becomes
O(N^2) up till you reach maintenance_work_mem and flush the tree. With
a large setting for maintenance_work_mem it gets spectacularly slow.
I think a reasonable solution for this might be to keep an eye on
maxdepth and force a flush if that gets too large (more than a few
hundred, perhaps?). Something like this:
/* If we've maxed out our available memory, dump everything to the index */
+ /* Also dump if the tree seems to be getting too unbalanced */
- if (buildstate->accum.allocatedMemory >= maintenance_work_mem * 1024L)
+ if (buildstate->accum.allocatedMemory >= maintenance_work_mem * 1024L ||
+ buildstate->accum.maxdepth > DEPTH_LIMIT)
{
The new fast-insert code likely will need a similar defense.
Comments?
regards, tom lane
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: Why creating GIN table index is so slow than inserting data into empty table with the same index?
2009-03-24 00:59 Why creating GIN table index is so slow than inserting data into empty table with the same index? Sergey Burladyan <eshkinkot@gmail.com>
2009-03-24 03:35 ` Re: Why creating GIN table index is so slow than inserting data into empty table with the same index? Tom Lane <tgl@sss.pgh.pa.us>
@ 2009-03-24 11:07 ` Heikki Linnakangas <heikki.linnakangas@enterprisedb.com>
2009-03-24 13:45 ` Re: Why creating GIN table index is so slow than inserting data into empty table with the same index? Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 4+ messages in thread
From: Heikki Linnakangas @ 2009-03-24 11:07 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Sergey Burladyan <eshkinkot@gmail.com>; Oleg Bartunov <oleg@sai.msu.su>; Teodor Sigaev <teodor@sigaev.ru>; pgsql-performance
Tom Lane wrote:
> Sergey Burladyan <eshkinkot@gmail.com> writes:
>> show maintenance_work_mem ;
>> maintenance_work_mem
>> ----------------------
>> 128MB
>
>> create table a (i1 int, i2 int, i3 int, i4 int, i5 int, i6 int);
>> insert into a select n, n, n, n, n, n from generate_series(1, 100000) as n;
>> create index arr_gin on a using gin ( (array[i1, i2, i3, i4, i5, i6]) );
>
> [ takes forever ]
>
> Seems the reason this is so awful is that the incoming data is exactly
> presorted, meaning that the tree structure that ginInsertEntry() is
> trying to build degenerates to a linear list (ie, every new element
> becomes the right child of the prior one). So the processing becomes
> O(N^2) up till you reach maintenance_work_mem and flush the tree. With
> a large setting for maintenance_work_mem it gets spectacularly slow.
Yes, this is probably the same issue I bumped into a while ago:
http://archives.postgresql.org/message-id/49350A13.3020105@enterprisedb.com
> I think a reasonable solution for this might be to keep an eye on
> maxdepth and force a flush if that gets too large (more than a few
> hundred, perhaps?). Something like this:
>
> /* If we've maxed out our available memory, dump everything to the index */
> + /* Also dump if the tree seems to be getting too unbalanced */
> - if (buildstate->accum.allocatedMemory >= maintenance_work_mem * 1024L)
> + if (buildstate->accum.allocatedMemory >= maintenance_work_mem * 1024L ||
> + buildstate->accum.maxdepth > DEPTH_LIMIT)
> {
>
> The new fast-insert code likely will need a similar defense.
I fooled around with a balanced tree, which solved the problem but
unfortunately made the unsorted case slower. Limiting the depth like
that should avoid that so it's worth trying.
--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: Why creating GIN table index is so slow than inserting data into empty table with the same index?
2009-03-24 00:59 Why creating GIN table index is so slow than inserting data into empty table with the same index? Sergey Burladyan <eshkinkot@gmail.com>
2009-03-24 03:35 ` Re: Why creating GIN table index is so slow than inserting data into empty table with the same index? Tom Lane <tgl@sss.pgh.pa.us>
2009-03-24 11:07 ` Re: Why creating GIN table index is so slow than inserting data into empty table with the same index? Heikki Linnakangas <heikki.linnakangas@enterprisedb.com>
@ 2009-03-24 13:45 ` Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 0 replies; 4+ messages in thread
From: Tom Lane @ 2009-03-24 13:45 UTC (permalink / raw)
To: Heikki Linnakangas <heikki.linnakangas@enterprisedb.com>; +Cc: Sergey Burladyan <eshkinkot@gmail.com>; Oleg Bartunov <oleg@sai.msu.su>; Teodor Sigaev <teodor@sigaev.ru>; pgsql-performance
Heikki Linnakangas <heikki.linnakangas@enterprisedb.com> writes:
> Tom Lane wrote:
>> I think a reasonable solution for this might be to keep an eye on
>> maxdepth and force a flush if that gets too large (more than a few
>> hundred, perhaps?). Something like this:
> I fooled around with a balanced tree, which solved the problem but
> unfortunately made the unsorted case slower.
Yeah, rebalancing the search tree would fix that, but every balanced
tree algorithm I know about is complicated, slow, and needs extra
memory. It's really unclear that it'd be worth the trouble for a
transient data structure like this one.
regards, tom lane
^ permalink raw reply [nested|flat] 4+ messages in thread
end of thread, other threads:[~2009-03-24 13:45 UTC | newest]
Thread overview: 4+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2009-03-24 00:59 Why creating GIN table index is so slow than inserting data into empty table with the same index? Sergey Burladyan <eshkinkot@gmail.com>
2009-03-24 03:35 ` Tom Lane <tgl@sss.pgh.pa.us>
2009-03-24 11:07 ` Heikki Linnakangas <heikki.linnakangas@enterprisedb.com>
2009-03-24 13:45 ` Tom Lane <tgl@sss.pgh.pa.us>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox