| From: | tgl(at)postgresql(dot)org (Tom Lane) |
|---|---|
| To: | pgsql-committers(at)postgresql(dot)org |
| Subject: | pgsql: Install a search tree depth limit in GIN bulk-insert operations, |
| Date: | 2009-03-24 22:06:04 |
| Message-ID: | 20090324220604.04783754ADE@cvs.postgresql.org |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Thread: | |
| Lists: | pgsql-committers |
Log Message:
-----------
Install a search tree depth limit in GIN bulk-insert operations, to prevent
them from degrading badly when the input is sorted or nearly so. In this
scenario the tree is unbalanced to the point of becoming a mere linked list,
so insertions become O(N^2). The easiest and most safely back-patchable
solution is to stop growing the tree sooner, ie limit the growth of N. We
might later consider a rebalancing tree algorithm, but it's not clear that
the benefit would be worth the cost and complexity. Per report from Sergey
Burladyan and an earlier complaint from Heikki.
Back-patch to 8.2; older versions didn't have GIN indexes.
Modified Files:
--------------
pgsql/src/backend/access/gin:
ginfast.c (r1.1 -> r1.2)
(http://anoncvs.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/gin/ginfast.c?r1=1.1&r2=1.2)
gininsert.c (r1.19 -> r1.20)
(http://anoncvs.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/gin/gininsert.c?r1=1.19&r2=1.20)
pgsql/src/include/access:
gin.h (r1.29 -> r1.30)
(http://anoncvs.postgresql.org/cvsweb.cgi/pgsql/src/include/access/gin.h?r1=1.29&r2=1.30)
| From | Date | Subject | |
|---|---|---|---|
| Next Message | Tom Lane | 2009-03-24 22:06:24 | pgsql: Install a search tree depth limit in GIN bulk-insert operations, |
| Previous Message | User Hinoue | 2009-03-24 21:38:46 | psqlodbc - psqlodbc: Add a textbox to setup dialog to change the |