Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commite5efda4

Browse files
committed
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 thisscenario 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-patchablesolution is to stop growing the tree sooner, ie limit the growth of N. Wemight later consider a rebalancing tree algorithm, but it's not clear thatthe benefit would be worth the cost and complexity. Per report from SergeyBurladyan and an earlier complaint from Heikki.Back-patch to 8.2; older versions didn't have GIN indexes.
1 parentfc022d7 commite5efda4

File tree

3 files changed

+20
-12
lines changed

3 files changed

+20
-12
lines changed

‎src/backend/access/gin/ginfast.c‎

Lines changed: 5 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@
1111
* Portions Copyright (c) 1994, Regents of the University of California
1212
*
1313
* IDENTIFICATION
14-
*$PostgreSQL: pgsql/src/backend/access/gin/ginfast.c,v 1.1 2009/03/2420:17:10 tgl Exp $
14+
*$PostgreSQL: pgsql/src/backend/access/gin/ginfast.c,v 1.2 2009/03/2422:06:03 tgl Exp $
1515
*
1616
*-------------------------------------------------------------------------
1717
*/
@@ -749,9 +749,10 @@ ginInsertCleanup(Relation index, GinState *ginstate,
749749
* XXX using up maintenance_work_mem here is probably unreasonably
750750
* much, since vacuum might already be using that much.
751751
*/
752-
if (GinPageGetOpaque(page)->rightlink==InvalidBlockNumber||
753-
(GinPageHasFullRow(page)&&
754-
accum.allocatedMemory>maintenance_work_mem*1024L ) )
752+
if (GinPageGetOpaque(page)->rightlink==InvalidBlockNumber||
753+
(GinPageHasFullRow(page)&&
754+
(accum.allocatedMemory >=maintenance_work_mem*1024L||
755+
accum.maxdepth>GIN_MAX_TREE_DEPTH)))
755756
{
756757
ItemPointerData*list;
757758
uint32nlist;

‎src/backend/access/gin/gininsert.c‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
* Portions Copyright (c) 1994, Regents of the University of California
99
*
1010
* IDENTIFICATION
11-
*$PostgreSQL: pgsql/src/backend/access/gin/gininsert.c,v 1.19 2009/03/2420:17:11 tgl Exp $
11+
*$PostgreSQL: pgsql/src/backend/access/gin/gininsert.c,v 1.20 2009/03/2422:06:03 tgl Exp $
1212
*-------------------------------------------------------------------------
1313
*/
1414

@@ -245,7 +245,9 @@ ginBuildCallback(Relation index, HeapTuple htup, Datum *values,
245245
&htup->t_self);
246246

247247
/* If we've maxed out our available memory, dump everything to the index */
248-
if (buildstate->accum.allocatedMemory >=maintenance_work_mem*1024L)
248+
/* Also dump if the tree seems to be getting too unbalanced */
249+
if (buildstate->accum.allocatedMemory >=maintenance_work_mem*1024L||
250+
buildstate->accum.maxdepth>GIN_MAX_TREE_DEPTH)
249251
{
250252
ItemPointerData*list;
251253
Datumentry;

‎src/include/access/gin.h‎

Lines changed: 11 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,7 @@
44
*
55
*Copyright (c) 2006-2009, PostgreSQL Global Development Group
66
*
7-
*$PostgreSQL: pgsql/src/include/access/gin.h,v 1.29 2009/03/2420:17:14 tgl Exp $
7+
*$PostgreSQL: pgsql/src/include/access/gin.h,v 1.30 2009/03/2422:06:03 tgl Exp $
88
*--------------------------------------------------------------------------
99
*/
1010
#ifndefGIN_H
@@ -26,6 +26,14 @@
2626
#defineGIN_COMPARE_PARTIAL_PROC 5
2727
#defineGINNProcs 5
2828

29+
/*
30+
* Max depth allowed in search tree during bulk inserts. This is to keep from
31+
* degenerating to O(N^2) behavior when the tree is unbalanced due to sorted
32+
* or nearly-sorted input. (Perhaps it would be better to use a balanced-tree
33+
* algorithm, but in common cases that would only add useless overhead.)
34+
*/
35+
#defineGIN_MAX_TREE_DEPTH 100
36+
2937
/*
3038
* Page opaque data in a inverted index page.
3139
*
@@ -434,12 +442,9 @@ extern IndexTuple ginPageGetLinkItup(Buffer buf);
434442

435443
/* gindatapage.c */
436444
externintcompareItemPointers(ItemPointera,ItemPointerb);
437-
externvoid
438-
MergeItemPointers(
439-
ItemPointerData*dst,
445+
externvoidMergeItemPointers(ItemPointerData*dst,
440446
ItemPointerData*a,uint32na,
441-
ItemPointerData*b,uint32nb
442-
);
447+
ItemPointerData*b,uint32nb);
443448

444449
externvoidGinDataPageAddItem(Pagepage,void*data,OffsetNumberoffset);
445450
externvoidPageDeletePostingItem(Pagepage,OffsetNumberoffset);

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp