From 37e9992214442ac485eee31d05506d430a89019f Mon Sep 17 00:00:00 2001
From: Tom Lane
Date: Tue, 24 Mar 2009 22:06:32 +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 | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

(limited to 'src/backend')

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;
-- 
cgit v1.2.3