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

Поиск
Список
Период
Сортировка
От tgl@postgresql.org (Tom Lane)
Тема pgsql: Install a search tree depth limit in GIN bulk-insert operations,
Дата
Msg-id 20090324220604.04783754ADE@cvs.postgresql.org
обсуждение исходный текст
Список 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.

Modified Files:
--------------
    pgsql/src/backend/access/gin:
        ginfast.c (r1.1 -> r1.2)
        (http://anoncvs.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/gin/ginfast.c?r1=1.1&r2=1.2)
        gininsert.c (r1.19 -> r1.20)
        (http://anoncvs.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/gin/gininsert.c?r1=1.19&r2=1.20)
    pgsql/src/include/access:
        gin.h (r1.29 -> r1.30)
        (http://anoncvs.postgresql.org/cvsweb.cgi/pgsql/src/include/access/gin.h?r1=1.29&r2=1.30)

В списке pgsql-committers по дате отправления:

Предыдущее
От: hinoue@pgfoundry.org (User Hinoue)
Дата:
Сообщение: psqlodbc - psqlodbc: Add a textbox to setup dialog to change the
Следующее
От: tgl@postgresql.org (Tom Lane)
Дата:
Сообщение: pgsql: Install a search tree depth limit in GIN bulk-insert operations,