Skip site navigation (1) Skip section navigation (2)

pgsql: Install a search tree depth limit in GIN bulk-insert operations,

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:32
Message-ID: 20090324220632.4BEB7754ADE@cvs.postgresql.org (view raw or flat)
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.

Tags:
----
REL8_2_STABLE

Modified Files:
--------------
    pgsql/src/backend/access/gin:
        gininsert.c (r1.5.2.1 -> r1.5.2.2)
        (http://anoncvs.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/gin/gininsert.c?r1=1.5.2.1&r2=1.5.2.2)
    pgsql/src/include/access:
        gin.h (r1.9.2.2 -> r1.9.2.3)
        (http://anoncvs.postgresql.org/cvsweb.cgi/pgsql/src/include/access/gin.h?r1=1.9.2.2&r2=1.9.2.3)

pgsql-committers by date

Next:From: Peter EisentrautDate: 2009-03-25 13:07:26
Subject: pgsql: No period if it's not a sentence
Previous:From: Tom LaneDate: 2009-03-24 22:06:24
Subject: pgsql: Install a search tree depth limit in GIN bulk-insert operations,

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group