Sokolov Yura писал 2017-05-15 15:08:
Heikki Linnakangas писал 2017-05-15 12:06:
On 05/14/2017 09:47 PM, Sokolov Yura wrote:
Good day, everyone.
I've been playing a bit with unlogged tables - just random updates on
key-value table. I've noticed amount of cpu spent in a
(called by PageRepareFragmentaion). Most of time were spent in qsort
Ah, I played with this too a couple of years ago, see
but got distracted by other things and never got around to commit
itemidbase array is bounded by number of tuples in a page, and
structure is simple, so specialized version could be a better choice.
Attached patch adds combination of one pass of prefix sort with
sort for larger array and shell sort for smaller array.
Insertion sort and shell sort are implemented as macros and could be
Cool! Could you compare that against the bucket sort I posted in the
above thread, please?
At a quick glance, your "prefix sort" seems to be the the same
algorithm as the bucket sort that I implemented. You chose 256
buckets, where I picked 32. And you're adding a shell sort
implementation, for small arrays, while I used a straight insertion
sort. Not sure what these differences mean in practice.
Thank you for attention.
My first version of big page sort was almost exactly same to yours.
I had a bug in my insertion sort, so I had to refactor it.
(bug were fixed)
I found that items in itemidbase are almost sorted, so it is important
to try keep its order in prefix sort. So I've changed --count[i] to
And it looks like it is better to have more buckets:
- with 256 buckets, size of single bucket is almost always less than 2,
so array is almost always sorted after prefix sort pass.
But it looks like it is better to sort each bucket separately, as you
did, and as it was in my early version.
Also I used your names for functions and some comments.
I attached new version of the patch.
I left memcpy intact cause it looks like it doesn't take noticable
In a sequel, I propose to simplify PageRepairFragmentation in attached
Sokolov Yura aka funny.falcon
Postgres Professional: https://postgrespro.ru
The Russian Postgres Company
From 2cde4cb6b0c4c5868d99e13789b0ac33364d7315 Mon Sep 17 00:00:00 2001
From: Sokolov Yura <funny.fal...@postgrespro.ru>
Date: Mon, 15 May 2017 16:04:14 +0300
Subject: [PATCH 2/2] bufpage.c: simplify PageRepairFragmentation
In assumption that page usually doesn't become empty, merge second loop
body (collecting items with storage) into first (counting kinds of
src/backend/storage/page/bufpage.c | 46 +++++++++++++++-----------------------
1 file changed, 18 insertions(+), 28 deletions(-)
diff --git a/src/backend/storage/page/bufpage.c b/src/backend/storage/page/bufpage.c
index c5630e808b..61738f241f 100644
@@ -555,10 +555,11 @@ PageRepairFragmentation(Page page)
Offset pd_special = ((PageHeader) page)->pd_special;
+ itemIdSortData itemidbase[MaxHeapTuplesPerPage];
+ itemIdSort itemidptr = itemidbase;
* It's worth the trouble to be more paranoid here than in most places,
@@ -578,14 +579,26 @@ PageRepairFragmentation(Page page)
pd_lower, pd_upper, pd_special)));
nline = PageGetMaxOffsetNumber(page);
- nunused = nstorage = 0;
+ nunused = totallen = 0;
for (i = FirstOffsetNumber; i <= nline; i++)
lp = PageGetItemId(page, i);
+ itemidptr->offsetindex = i - 1;
+ itemidptr->itemoff = ItemIdGetOffset(lp);
+ if (unlikely(itemidptr->itemoff < (int) pd_upper ||
+ itemidptr->itemoff >= (int) pd_special))
+ errmsg("corrupted item pointer: %u",
+ itemidptr->alignedlen = MAXALIGN(ItemIdGetLength(lp));
+ totallen += itemidptr->alignedlen;
@@ -595,7 +608,7 @@ PageRepairFragmentation(Page page)
- if (nstorage == 0)
+ if (itemidptr == itemidbase)
/* Page is completely empty, so just reset it quickly */
((PageHeader) page)->pd_upper = pd_special;
@@ -603,36 +616,13 @@ PageRepairFragmentation(Page page)
/* Need to compact the page the hard way */
- itemIdSortData itemidbase[MaxHeapTuplesPerPage];
- itemIdSort itemidptr = itemidbase;
- totallen = 0;
- for (i = 0; i < nline; i++)
- lp = PageGetItemId(page, i + 1);
- if (ItemIdHasStorage(lp))
- itemidptr->offsetindex = i;
- itemidptr->itemoff = ItemIdGetOffset(lp);
- if (itemidptr->itemoff < (int) pd_upper ||
- itemidptr->itemoff >= (int) pd_special)
- errmsg("corrupted item pointer: %u",
- itemidptr->alignedlen = MAXALIGN(ItemIdGetLength(lp));
- totallen += itemidptr->alignedlen;
if (totallen > (Size) (pd_special - pd_lower))
errmsg("corrupted item lengths: total %u, available space %u",
(unsigned int) totallen, pd_special - pd_lower)));
- compactify_tuples(itemidbase, nstorage, page);
+ compactify_tuples(itemidbase, (int) (itemidptr - itemidbase), page);
/* Set hint bit for PageAddItem */
Sent via pgsql-hackers mailing list (email@example.com)
To make changes to your subscription: