[HACKERS] Small improvement to compactify_tuples

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.

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.

I've tested following table:

     create unlogged table test3 (
         id integer PRIMARY KEY with (fillfactor=85),
         val text
     ) WITH (fillfactor=85);
     insert into test3 select i, '!'||i from generate_series(1, 10000000) 
as i;

With pgbench script:

     \set id1 RANDOM(1, :scale)
     \set id2 RANDOM(1, :scale)

     select * from test3 where id = :id1;
     update test3 set val = '!'|| :id2 where id = :id1;

And command:

     pgbench -M prepared -c 3 -s 10000000 -T 1000 -P 3 -n -f test3.sql 
testdb

Using 1GB shared_buffers and synchronous_commit=off.

On my notebook improvement is:

before patch:

     progress: 63.0 s, 15880.1 tps, lat 0.189 ms stddev 0.127
     progress: 66.0 s, 15975.8 tps, lat 0.188 ms stddev 0.122
     progress: 69.0 s, 15904.1 tps, lat 0.189 ms stddev 0.152
     progress: 72.0 s, 15000.9 tps, lat 0.200 ms stddev 0.213
     progress: 75.0 s, 15101.7 tps, lat 0.199 ms stddev 0.192
     progress: 78.0 s, 15854.2 tps, lat 0.189 ms stddev 0.158
     progress: 81.0 s, 15803.3 tps, lat 0.190 ms stddev 0.158
     progress: 84.0 s, 15242.9 tps, lat 0.197 ms stddev 0.203
     progress: 87.0 s, 15184.1 tps, lat 0.198 ms stddev 0.215

after patch:

     progress: 63.0 s, 17108.5 tps, lat 0.175 ms stddev 0.140
     progress: 66.0 s, 17271.9 tps, lat 0.174 ms stddev 0.155
     progress: 69.0 s, 17243.5 tps, lat 0.174 ms stddev 0.143
     progress: 72.0 s, 16675.3 tps, lat 0.180 ms stddev 0.206
     progress: 75.0 s, 17187.4 tps, lat 0.175 ms stddev 0.157
     progress: 78.0 s, 17293.0 tps, lat 0.173 ms stddev 0.159
     progress: 81.0 s, 16289.8 tps, lat 0.184 ms stddev 0.180
     progress: 84.0 s, 16131.2 tps, lat 0.186 ms stddev 0.170
     progress: 87.0 s, 16741.1 tps, lat 0.179 ms stddev 0.165

I understand that it is quite degenerate test case.
But probably this improvement still has sense.

With regards,
-- 
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