]> git.ipfire.org Git - thirdparty/postgresql.git/commit
Install a search tree depth limit in GIN bulk-insert operations, to prevent
authorTom Lane <tgl@sss.pgh.pa.us>
Tue, 24 Mar 2009 22:06:24 +0000 (22:06 +0000)
committerTom Lane <tgl@sss.pgh.pa.us>
Tue, 24 Mar 2009 22:06:24 +0000 (22:06 +0000)
commite760463c7779f5021e6b8d81ca96b3edc40704ba
tree53f6fe81196f8db34358400d06cf0fb85f2ebb43
parente1cf329061aed52e1948bb9bff870db68975c33d
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.
src/backend/access/gin/gininsert.c
src/include/access/gin.h