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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
