From e5efda442cfcfa20a0cf6166952c671a0f39689b Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Tue, 24 Mar 2009 22:06:03 +0000 Subject: 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 | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) (limited to 'src/backend/access/gin/gininsert.c') diff --git a/src/backend/access/gin/gininsert.c b/src/backend/access/gin/gininsert.c index d05882cdb94..f6a348eb85d 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.19 2009/03/24 20:17:11 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/access/gin/gininsert.c,v 1.20 2009/03/24 22:06:03 tgl Exp $ *------------------------------------------------------------------------- */ @@ -245,7 +245,9 @@ ginBuildCallback(Relation index, HeapTuple htup, Datum *values, &htup->t_self); /* If we've maxed out our available memory, dump everything to the index */ - if (buildstate->accum.allocatedMemory >= maintenance_work_mem * 1024L) + /* Also dump if the tree seems to be getting too unbalanced */ + if (buildstate->accum.allocatedMemory >= maintenance_work_mem * 1024L || + buildstate->accum.maxdepth > GIN_MAX_TREE_DEPTH) { ItemPointerData *list; Datum entry; -- cgit v1.2.3