diff options
| author | Tom Lane | 2009-03-24 22:06:32 +0000 |
|---|---|---|
| committer | Tom Lane | 2009-03-24 22:06:32 +0000 |
| commit | 37e9992214442ac485eee31d05506d430a89019f (patch) | |
| tree | 727b7977da2f69c838f02386bb19932fd3a5fcb5 /src/backend | |
| parent | 98686e1ea142d88cc29eaea012047bb73f1ae5cd (diff) | |
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.
Diffstat (limited to 'src/backend')
| -rw-r--r-- | src/backend/access/gin/gininsert.c | 5 |
1 files changed, 3 insertions, 2 deletions
diff --git a/src/backend/access/gin/gininsert.c b/src/backend/access/gin/gininsert.c index ed79a8f3de7..e511f8ca1ca 100644 --- a/src/backend/access/gin/gininsert.c +++ b/src/backend/access/gin/gininsert.c @@ -8,7 +8,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/access/gin/gininsert.c,v 1.5.2.1 2007/06/05 12:48:21 teodor Exp $ + * $PostgreSQL: pgsql/src/backend/access/gin/gininsert.c,v 1.5.2.2 2009/03/24 22:06:32 tgl Exp $ *------------------------------------------------------------------------- */ @@ -241,7 +241,8 @@ ginBuildCallback(Relation index, HeapTuple htup, Datum *values, * we use only half maintenance_work_mem, because there is some leaks * during insertion and extract values */ - if (buildstate->accum.allocatedMemory >= maintenance_work_mem * 1024L / 2L) + if (buildstate->accum.allocatedMemory >= maintenance_work_mem * 1024L / 2L || + buildstate->accum.maxdepth > GIN_MAX_TREE_DEPTH) { ItemPointerData *list; Datum entry; |