MIME-Version: 1.0
Content-Type: multipart/mixed;
 boundary="=_6f8b884a037a71985bc64cf63238b3ed"
Date: Sun, 14 May 2017 21:47:11 +0300
From: Sokolov Yura <funny.falcon@postgrespro.ru>
To: pgsql-hackers@postgresql.org
Subject: Small improvement to compactify_tuples
Organization: Postgres Professional
Message-ID: <3c6ff1d3a2ff429ee80d0031e6c69cb7@postgrespro.ru>
User-Agent: Roundcube Webmail/1.2.4
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org

--=_6f8b884a037a71985bc64cf63238b3ed
Content-Transfer-Encoding: 7bit
Content-Type: text/plain; charset=US-ASCII;
 format=flowed

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
--=_6f8b884a037a71985bc64cf63238b3ed
Content-Transfer-Encoding: base64
Content-Type: text/x-diff;
 name=0001-storage-page-bufpage.c-improve-compactify_tuples.patch
Content-Disposition: attachment;
 filename=0001-storage-page-bufpage.c-improve-compactify_tuples.patch;
 size=5059

RnJvbSBmOGVkMjM1ZGJiNjBhNzliNGY1OWRjOGE0YWYwMTRiMmNhNjk4Nzcy
IE1vbiBTZXAgMTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBTb2tvbG92IFl1cmEg
YWthIGZ1bm55X2ZhbGNvbiA8ZnVubnkuZmFsY29uQGdtYWlsLmNvbT4KRGF0
ZTogU3VuLCAxNCBNYXkgMjAxNyAyMDo1NzowMCArMDMwMApTdWJqZWN0OiBb
UEFUQ0hdIHN0b3JhZ2UvcGFnZS9idWZwYWdlLmM6IGltcHJvdmUgY29tcGFj
dGlmeV90dXBsZXMKCkl0ZW1zIHBhc3NlZCB0byBjb21wYWN0aWZ5X3R1cGxl
cyBhcmUgYWxtb3N0IHNvcnRlZC4gU28gY2FsbCB0byBnZW5lcmFsCnFzb3J0
IG1ha2VzIHVubmVjZXNzYXJ5IG92ZXJoZWFkIG9uIGZ1bmN0aW9uIGNhbGxz
IChzd2FwZnVuYywgbWVkLAppdGVtb2ZmY29tcGFyZSkuCgpUaGlzIHBhdGNo
IGFkZCBvbmUgcGFzcyBvZiBwcmVmaXggc29ydCArIGluc2VydGlvbiBzb3J0
IGZvciBsYXJnZSBhcnJheQpvZiBpdGVtcywgYW5kIHNoZWxsIHNvcnQgZm9y
IHNtYWxsZXIgYXJyYXlzLgoKSW5zZXJ0aW9uIGFuZCBTaGVsbCBzb3J0IGFy
ZSBpbXBsZW1lbnRlZCB1c2luZyBtYWNyb3Nlcy4KClRoaXMgYXBwcm9hY2gg
YWxsb3dzIHRvIHNhdmUgMyUgb2YgY3B1IGluIGRlZ2VuZXJhdGUgY2FzZQoo
aGlnaGx5IGludGVuc2l2ZSBIT1QgcmFuZG9tIHVwZGF0ZXMgb24gdW5sb2dn
ZWQgdGFibGUgd2l0aAogc3luY2hyb25pemVkX2NvbW1pdD1vZmYpLgotLS0K
IHNyYy9iYWNrZW5kL3N0b3JhZ2UvcGFnZS9idWZwYWdlLmMgfCA0MiArKysr
KysrKysrKysrKysrKysrKysrKysrLS0KIHNyYy9pbmNsdWRlL2MuaCAgICAg
ICAgICAgICAgICAgICAgfCA1OSArKysrKysrKysrKysrKysrKysrKysrKysr
KysrKysrKysrKysrKwogMiBmaWxlcyBjaGFuZ2VkLCA5OCBpbnNlcnRpb25z
KCspLCAzIGRlbGV0aW9ucygtKQoKZGlmZiAtLWdpdCBhL3NyYy9iYWNrZW5k
L3N0b3JhZ2UvcGFnZS9idWZwYWdlLmMgYi9zcmMvYmFja2VuZC9zdG9yYWdl
L3BhZ2UvYnVmcGFnZS5jCmluZGV4IGZkZjA0NWEuLmI3YzYzOTIgMTAwNjQ0
Ci0tLSBhL3NyYy9iYWNrZW5kL3N0b3JhZ2UvcGFnZS9idWZwYWdlLmMKKysr
IGIvc3JjL2JhY2tlbmQvc3RvcmFnZS9wYWdlL2J1ZnBhZ2UuYwpAQCAtNDMz
LDYgKzQzMywzNiBAQCBpdGVtb2ZmY29tcGFyZShjb25zdCB2b2lkICppdGVt
aWRwMSwgY29uc3Qgdm9pZCAqaXRlbWlkcDIpCiAJCSgoaXRlbUlkU29ydCkg
aXRlbWlkcDEpLT5pdGVtb2ZmOwogfQogCisjZGVmaW5lIE5TUExJVCAyNTYK
KyNkZWZpbmUgUFJFRkRJViAoQkxDS1NaIC8gTlNQTElUKQorLyogb25lIHBh
c3Mgb2YgcHJlZml4IHNvcnQgZm9yIGhpZ2ggOCBiaXRzIG9mIGl0ZW1vZmYu
Ki8KK3N0YXRpYyB2b2lkCitwcmVmaXhfcHJlc29ydChpdGVtSWRTb3J0IGl0
ZW1pZGJhc2UsIGludCBuaXRlbXMpCit7CisJaXRlbUlkU29ydERhdGEgY29w
eVtNYXhJbmRleFR1cGxlc1BlclBhZ2VdOworCWludAljb3VudFtOU1BMSVQr
MV0gPSB7IDAgfTsKKwlpbnQgaSwgcG9zLCBoaWdoYml0czsKKworCUFzc2Vy
dChuaXRlbXMgPD0gTWF4SW5kZXhUdXBsZXNQZXJQYWdlKTsKKwlmb3IgKGkg
PSAwOyBpIDwgbml0ZW1zOyBpKyspCisJeworCQloaWdoYml0cyA9IGl0ZW1p
ZGJhc2VbaV0uaXRlbW9mZiAvIFBSRUZESVY7CisJCWNvdW50W2hpZ2hiaXRz
XSsrOworCX0KKwkvKiBzb3J0IGluIGRlY3JlYXNpbmcgb3JkZXIgKi8KKwlm
b3IgKGkgPSBOU1BMSVQtMTsgaSAhPSAwOyBpLS0pCisJCWNvdW50W2ktMV0g
Kz0gY291bnRbaV07CisJQXNzZXJ0KGNvdW50WzBdID09IG5pdGVtcyk7CisJ
Zm9yIChpID0gMDsgaSA8IG5pdGVtczsgaSsrKQorCXsKKwkJaGlnaGJpdHMg
PSBpdGVtaWRiYXNlW2ldLml0ZW1vZmYgLyBQUkVGRElWOworCQlwb3MgPSBj
b3VudFtoaWdoYml0cysxXSsrOworCQljb3B5W3Bvc10gPSBpdGVtaWRiYXNl
W2ldOworCX0KKwlBc3NlcnQoY291bnRbMV0gPT0gbml0ZW1zKTsKKwltZW1j
cHkoaXRlbWlkYmFzZSwgY29weSwgc2l6ZW9mKGl0ZW1JZFNvcnREYXRhKSAq
IG5pdGVtcyk7Cit9CisKIC8qCiAgKiBBZnRlciByZW1vdmluZyBvciBtYXJr
aW5nIHNvbWUgbGluZSBwb2ludGVycyB1bnVzZWQsIG1vdmUgdGhlIHR1cGxl
cyB0bwogICogcmVtb3ZlIHRoZSBnYXBzIGNhdXNlZCBieSB0aGUgcmVtb3Zl
ZCBpdGVtcy4KQEAgLTQ0NCw5ICs0NzQsMTUgQEAgY29tcGFjdGlmeV90dXBs
ZXMoaXRlbUlkU29ydCBpdGVtaWRiYXNlLCBpbnQgbml0ZW1zLCBQYWdlIHBh
Z2UpCiAJT2Zmc2V0CQl1cHBlcjsKIAlpbnQJCQlpOwogCi0JLyogc29ydCBp
dGVtSWRTb3J0RGF0YSBhcnJheSBpbnRvIGRlY3JlYXNpbmcgaXRlbW9mZiBv
cmRlciAqLwotCXFzb3J0KChjaGFyICopIGl0ZW1pZGJhc2UsIG5pdGVtcywg
c2l6ZW9mKGl0ZW1JZFNvcnREYXRhKSwKLQkJICBpdGVtb2ZmY29tcGFyZSk7
CisJaWYgKG5pdGVtcyA+IDQ4KQorCXsKKwkJcHJlZml4X3ByZXNvcnQoaXRl
bWlkYmFzZSwgbml0ZW1zKTsKKwkJcGdfaW5zZXJ0aW9uX3NvcnQoaXRlbUlk
U29ydERhdGEsIGl0ZW1pZGJhc2UsIG5pdGVtcywgaXRlbW9mZmNvbXBhcmUp
OworCX0KKwllbHNlCisJeworCQlwZ19zaGVsbF9zb3J0KGl0ZW1JZFNvcnRE
YXRhLCBpdGVtaWRiYXNlLCBuaXRlbXMsIGl0ZW1vZmZjb21wYXJlKTsKKwl9
CiAKIAl1cHBlciA9IHBoZHItPnBkX3NwZWNpYWw7CiAJZm9yIChpID0gMDsg
aSA8IG5pdGVtczsgaSsrKQpkaWZmIC0tZ2l0IGEvc3JjL2luY2x1ZGUvYy5o
IGIvc3JjL2luY2x1ZGUvYy5oCmluZGV4IGZiYTA3YzYuLjgzNzk0MGQgMTAw
NjQ0Ci0tLSBhL3NyYy9pbmNsdWRlL2MuaAorKysgYi9zcmMvaW5jbHVkZS9j
LmgKQEAgLTk2Miw2ICs5NjIsNjUgQEAgdHlwZWRlZiBOYW1lRGF0YSAqTmFt
ZTsKICNkZWZpbmUgdW5saWtlbHkoeCkgKCh4KSAhPSAwKQogI2VuZGlmCiAK
Ky8qCisgKiBwZ19zaGVsbF9zb3J0IC0gc29ydCBmb3Igc21hbGwgYXJyYXlz
IHdpdGggaW5saW5hYmxlIGNvbXBhcmF0b3IuCisgKiBTaW5jZSBpdCBpcyBp
bXBsZW1lbnRlZCBhcyBhIG1hY3JvcyBpdCBjb3VsZCBiZSBvcHRpbWl6ZWQg
dG9nZXRoZXIgd2l0aAorICogY29tcGFyaXNvbiBmdW5jdGlvbi4KKyAqIEdh
cHMgYXJlICJnYXAoaSkgPSBzbWFsbGVzdCBwcmltZSBudW1iZXIgYmVsb3cg
ZV5pIi4gVGhleSBhcmUgY2xvc2UgdG8KKyAqIEluY2VycGkgJiBTZWR3aWNr
IGdhcHMsIGJ1dCBsb29rcyB0byBiZSBiZXR0ZXIgaW4gYXZlcmFnZS4KKyAq
IEl0IGlzIGJlc3QgdXNlZCB3aXRoIGFycmF5IHNtYWxsZXIgdGhhbiAyMDAg
ZWxlbWVudHMsIGFuZCBjb3VsZCBiZSBzYWZlbHkKKyAqIHVzZWQgdXB0byAx
MDAwIGVsZW1lbnRzLiBCdXQgaXQgZGVncmFkZXMgZmFzdCBhZnRlciB0aGF0
LCBhbmQgaXQgaXMKKyAqIGJldHRlciB0byB1c2UgcXNvcnQuCisgKgorICog
QXJndW1lbnRzOgorICoJIGVsZW1fdCAtIHR5cGUgb2YgYXJyYXkgZWxlbWVu
dCAoZm9yIGRlY2xhcmluZyB0ZW1wb3JhcnkgdmFyaWFibGVzKQorICoJIGFy
cmF5CS0gcG9pbnRlciB0byBlbGVtZW50cyB0byBiZSBzb3J0ZWQKKyAqCSBu
aXRlbXMgLSBhbW91bnQgb2YgZWxlbWVudHMgdG8gYmUgc29ydGVkCisgKgkg
Y21wCS0gY29tcGFyaXNvbiBmdW5jdGlvbiB0aGF0IGFjY2VwdHMgYWRkcmVz
cyBvZiBlbGVtZW50cworICoJCQkgIChpdCBpcyBjb21wYXRpYmxlIHdpdGgg
cXNvcnQgY29tcGFyaXNvbiBmdW5jdGlvbikuCisgKgkgTm90ZTogYGNtcGAg
YXJndW1lbnQgZXZhbHVhdGVzIG1hbnkgdGltZXMuCisgKgkgT3RoZXIgYXJn
dW1lbnRzIGV2YWx1YXRlcyBvbmNlCisgKi8KKyNkZWZpbmUgcGdfc2hlbGxf
c29ydF9wYXNzKGVsZW1fdCwgY21wLCBvZmYpIFwKKwlkbyB7IFwKKwkJaW50
IF9pLCBfajsgXAorCQllbGVtX3QgX3RlbXA7IFwKKwkJZm9yIChfaSA9IG9m
ZjsgX2kgPCBfbjsgX2kgKz0gb2ZmKSBcCisJCXsgXAorCQkJaWYgKChjbXAp
KF9hcnIrX2ksIF9hcnIrX2ktb2ZmKSA+PSAwKSBcCisJCQkJY29udGludWU7
IFwKKwkJCV90ZW1wID0gX2FycltfaV07IFwKKwkJCV9qID0gX2k7IFwKKwkJ
CWRvIHsgXAorCQkJCV9hcnJbX2pdID0gX2FycltfaiAtIG9mZl07IFwKKwkJ
CQlfaiAtPSBvZmY7IFwKKwkJCX0gd2hpbGUgKF9qID49IG9mZiAmJiAoY21w
KShfYXJyK19qLW9mZiwgJl90ZW1wKSA+IDApOyBcCisJCQlfYXJyW19qXSA9
IF90ZW1wOyBcCisJCX0gXAorCX0gd2hpbGUgKDApCisjZGVmaW5lIHBnX3No
ZWxsX3NvcnQoZWxlbV90LCBhcnJheSwgbml0ZW1zLCBjbXApIFwKKwlkbyB7
IFwKKwkJaW50IF9uID0gKG5pdGVtcyk7IFwKKwkJZWxlbV90KiBfYXJyID0g
KGFycmF5KTsgXAorCQlzdGF0aWMgY29uc3QgaW50IF9vZmZzZXRzW10gPSB7
NDAxLCAxMzksIDUzLCAxOSwgNywgM307IFwKKwkJaW50IF9ub2ZmLCBfb2Zm
OyBcCisJCWZvciAoX25vZmYgPSAwOyBfbm9mZiA8IGxlbmd0aG9mKF9vZmZz
ZXRzKTsgX25vZmYrKykgeyBcCisJCQlfb2ZmID0gX29mZnNldHNbX25vZmZd
OyBcCisJCQlwZ19zaGVsbF9zb3J0X3Bhc3MoZWxlbV90LCAoY21wKSwgX29m
Zik7IFwKKwkJfSBcCisJCXBnX3NoZWxsX3NvcnRfcGFzcyhlbGVtX3QsIChj
bXApLCAxKTsgXAorCX0gd2hpbGUoMCkKKy8qCisgKiBwZ19pbnNlcnRpb25f
c29ydCAtIGp1c3QgaW5zZXJ0aW9uIHNvcnQgZm9yIHNtYWxsZXN0IGFycmF5
LCBvciBpZgorICogYXJyYXkgd2FzIGFsbW9zdCBzb3J0ZWQgYWxyZWFkeS4g
VXNlcyBzYW1lIGFyZ3VtZW50cyBhcyBwZ19zaGVsbF9zb3J0LgorICovCisj
ZGVmaW5lIHBnX2luc2VydGlvbl9zb3J0KGVsZW1fdCwgYXJyYXksIG5pdGVt
cywgY21wKSBcCisJZG8geyBcCisJCWludCBfbiA9IChuaXRlbXMpOyBcCisJ
CWVsZW1fdCogX2FyciA9IChhcnJheSk7IFwKKwkJcGdfc2hlbGxfc29ydF9w
YXNzKGVsZW1fdCwgKGNtcCksIDEpOyBcCisJfSB3aGlsZSAoMCkKKwogCiAv
KiAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t
LS0tLS0tLS0tLS0tLS0tLS0tLS0tCiAgKgkJCQlTZWN0aW9uIDg6CXJhbmRv
bSBzdHVmZgotLSAKMi45LjMKCg==

--=_6f8b884a037a71985bc64cf63238b3ed
Content-Type: text/plain
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
MIME-Version: 1.0


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

--=_6f8b884a037a71985bc64cf63238b3ed--