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

Commitba1cc65

Browse files
committed
Add some randomness to the choice of which GiST page to insert to.
When descending the tree for an insert, and there are multiple equally goodpages we could insert to, make the choice in random. Previously, we wouldalways choose the tuple with lowest offset number. That meant that when twonon-leaf pages overlap - in the extreme case they might have exactly the samekey - all but the first such page went unused. That wasn't optimal for spaceusage; if you deleted some tuples from the non-first pages, the space wouldnever be reused.With this patch, the other pages are sometimes chosen too, although there'sstill a heavy bias towards low-offset tuples, so that we don't lose cachelocality when doing a lot of inserts with similar keys.Original idea by Alexander Korotkov, although this patch version was writtenby me and copy-edited by Tom Lane.
1 parentbe92647 commitba1cc65

File tree

1 file changed

+62
-4
lines changed

1 file changed

+62
-4
lines changed

‎src/backend/access/gist/gistutil.c

Lines changed: 62 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -379,6 +379,7 @@ gistchoose(Relation r, Page p, IndexTuple it,/* it has compressed entry */
379379
GISTENTRYentry,
380380
identry[INDEX_MAX_KEYS];
381381
boolisnull[INDEX_MAX_KEYS];
382+
intkeep_current_best;
382383

383384
Assert(!GistPageIsLeaf(p));
384385

@@ -401,6 +402,31 @@ gistchoose(Relation r, Page p, IndexTuple it,/* it has compressed entry */
401402
*/
402403
best_penalty[0]=-1;
403404

405+
/*
406+
* If we find a tuple that's exactly as good as the currently best one, we
407+
* could use either one. When inserting a lot of tuples with the same or
408+
* similar keys, it's preferable to descend down the same path when
409+
* possible, as that's more cache-friendly. On the other hand, if all
410+
* inserts land on the same leaf page after a split, we're never going to
411+
* insert anything to the other half of the split, and will end up using
412+
* only 50% of the available space. Distributing the inserts evenly would
413+
* lead to better space usage, but that hurts cache-locality during
414+
* insertion. To get the best of both worlds, when we find a tuple that's
415+
* exactly as good as the previous best, choose randomly whether to stick
416+
* to the old best, or use the new one. Once we decide to stick to the
417+
* old best, we keep sticking to it for any subsequent equally good tuples
418+
* we might find. This favors tuples with low offsets, but still allows
419+
* some inserts to go to other equally-good subtrees.
420+
*
421+
* keep_current_best is -1 if we haven't yet had to make a random choice
422+
* whether to keep the current best tuple. If we have done so, and
423+
* decided to keep it, keep_current_best is 1; if we've decided to
424+
* replace, keep_current_best is 0. (This state will be reset to -1 as
425+
* soon as we've made the replacement, but sometimes we make the choice in
426+
* advance of actually finding a replacement best tuple.)
427+
*/
428+
keep_current_best=-1;
429+
404430
/*
405431
* Loop over tuples on page.
406432
*/
@@ -446,6 +472,9 @@ gistchoose(Relation r, Page p, IndexTuple it,/* it has compressed entry */
446472

447473
if (j<r->rd_att->natts-1)
448474
best_penalty[j+1]=-1;
475+
476+
/* we have new best, so reset keep-it decision */
477+
keep_current_best=-1;
449478
}
450479
elseif (best_penalty[j]==usize)
451480
{
@@ -468,12 +497,41 @@ gistchoose(Relation r, Page p, IndexTuple it,/* it has compressed entry */
468497
}
469498

470499
/*
471-
* If we find a tuple with zero penalty for all columns, there's no
472-
* need to examine remaining tuples; just break out of the loop and
473-
* return it.
500+
* If we looped past the last column, and did not update "result",
501+
* then this tuple is exactly as good as the prior best tuple.
502+
*/
503+
if (j==r->rd_att->natts&&result!=i)
504+
{
505+
if (keep_current_best==-1)
506+
{
507+
/* we didn't make the random choice yet for this old best */
508+
keep_current_best= (random() <= (MAX_RANDOM_VALUE /2)) ?1 :0;
509+
}
510+
if (keep_current_best==0)
511+
{
512+
/* we choose to use the new tuple */
513+
result=i;
514+
/* choose again if there are even more exactly-as-good ones */
515+
keep_current_best=-1;
516+
}
517+
}
518+
519+
/*
520+
* If we find a tuple with zero penalty for all columns, and we've
521+
* decided we don't want to search for another tuple with equal
522+
* penalty, there's no need to examine remaining tuples; just break
523+
* out of the loop and return it.
474524
*/
475525
if (zero_penalty)
476-
break;
526+
{
527+
if (keep_current_best==-1)
528+
{
529+
/* we didn't make the random choice yet for this old best */
530+
keep_current_best= (random() <= (MAX_RANDOM_VALUE /2)) ?1 :0;
531+
}
532+
if (keep_current_best==1)
533+
break;
534+
}
477535
}
478536

479537
returnresult;

0 commit comments

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