[Sokolov Yura <funny.falcon@postgrespro.ru>]

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
>>> simple
>>> key-value table. I've noticed amount of cpu spent in a 
>>> compactify_tuples
>>> (called by PageRepareFragmentaion). Most of time were spent in qsort 
>>> of
>>> itemidbase items.
>> 
>> Ah, I played with this too a couple of years ago, see
>> https://www.postgresql.org/message-id/546B89DE.7030906%40vmware.com,
>> but got distracted by other things and never got around to commit
>> that.
>> 
>>> itemidbase array is bounded by number of tuples in a page, and
>>> itemIdSortData
>>> structure is simple, so specialized version could be a better choice.
>>> 
>>> Attached patch adds combination of one pass of prefix sort with
>>> insertion
>>> sort for larger array and shell sort for smaller array.
>>> Insertion sort and shell sort are implemented as macros and could be
>>> reused.
>> 
>> 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.
>> 
>> - Heikki
> 
> 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
> count[i+1]++.
> 
> 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
> cpu time.

In a sequel, I propose to simplify PageRepairFragmentation in attached
patch.

-- 
Sokolov Yura aka funny.falcon
Postgres Professional: https://postgrespro.ru
The Russian Postgres Company

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Attachments:

  [text/x-diff] 0002-bufpage.c-simplify-PageRepairFragmentation.patch (3.3K, ../e49befcc6f1d7099834c6fdf5c675a60@postgrespro.ru/2-0002-bufpage.c-simplify-PageRepairFragmentation.patch)
  download | inline diff:
From 2cde4cb6b0c4c5868d99e13789b0ac33364d7315 Mon Sep 17 00:00:00 2001
From: Sokolov Yura <funny.falcon@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
items).
---
 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
--- a/src/backend/storage/page/bufpage.c
+++ b/src/backend/storage/page/bufpage.c
@@ -555,10 +555,11 @@ PageRepairFragmentation(Page page)
 	Offset		pd_special = ((PageHeader) page)->pd_special;
 	ItemId		lp;
 	int			nline,
-				nstorage,
 				nunused;
 	int			i;
 	Size		totallen;
+	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);
 		if (ItemIdIsUsed(lp))
 		{
 			if (ItemIdHasStorage(lp))
-				nstorage++;
+			{
+				itemidptr->offsetindex = i - 1;
+				itemidptr->itemoff = ItemIdGetOffset(lp);
+				if (unlikely(itemidptr->itemoff < (int) pd_upper ||
+							 itemidptr->itemoff >= (int) pd_special))
+					ereport(ERROR,
+							(errcode(ERRCODE_DATA_CORRUPTED),
+							 errmsg("corrupted item pointer: %u",
+									itemidptr->itemoff)));
+				itemidptr->alignedlen = MAXALIGN(ItemIdGetLength(lp));
+				totallen += itemidptr->alignedlen;
+				itemidptr++;
+			}
 		}
 		else
 		{
@@ -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)
 	else
 	{
 		/* 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)
-					ereport(ERROR,
-							(errcode(ERRCODE_DATA_CORRUPTED),
-							 errmsg("corrupted item pointer: %u",
-									itemidptr->itemoff)));
-				itemidptr->alignedlen = MAXALIGN(ItemIdGetLength(lp));
-				totallen += itemidptr->alignedlen;
-				itemidptr++;
-			}
-		}
-
 		if (totallen > (Size) (pd_special - pd_lower))
 			ereport(ERROR,
 					(errcode(ERRCODE_DATA_CORRUPTED),
 			   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 */
-- 
2.11.0