MIME-Version: 1.0
References: 
 <CANWCAZYzx7a7E9AY16Jt_U3+GVKDADfgApZ-42SYNiig8dTnFA@mail.gmail.com>
 <CANWCAZbsx5VY-F5RVvZ5H1abBWcinMY90gNra6EbdGS1CTx=7g@mail.gmail.com>
 <CANWCAZaN8kW6o7Ymc_jzPO_Z5SqekQTTNra3xTGYTH+cjrVp8g@mail.gmail.com>
 <269A8FB9-6D43-43CF-A6FE-52D28CBDB8A9@Outlook.com>
 <CANWCAZZiMGj6QuHfyBPv9at7xn23NPAz4nit=G6fr26V+h8MKg@mail.gmail.com>
 <F7935986-4E3D-477C-B45C-878420B45C0D@gmail.com>
 <CANWCAZaKRzsYPn9YWRR8g5dkX-ep_jgyUb4r3KFekK5ZTNo7ew@mail.gmail.com>
 <606C775A-4C1A-482B-BE7D-2E7A46AE14B9@gmail.com>
 <CANWCAZaBeDPfF0sCdSssRXv6nBZeRP8Z=OO1731zsoUC58U5_Q@mail.gmail.com>
 <F7D64692-F979-4661-B91C-8A1FF09F69BD@gmail.com>
 <9D3D4647-868B-4562-B382-D201478AD67B@gmail.com>
 <CANWCAZZo5rgE4+NYYES1hLN9PvonXMH=K3Z7b0TKcCBNOAjaag@mail.gmail.com>
 <54659731-2232-4E74-9533-D136D01B153F@gmail.com>
 <CANWCAZYur4VDbx9zkpFM3mM4-Hj4_Vt1t=Z4TPhK7+3=T6BMOA@mail.gmail.com>
 <tencent_6EB1CE2270AFA3DD4164A5D2@qq.com>
 <CANWCAZYBgHCpS-w5E8+wJpfhwLK88Kys-5ukSta2gj4BRPiTSg@mail.gmail.com>
 <tencent_1565D02652E0DC26675AABE2@qq.com>
 <tencent_D9FB41A25D4A685F6176ED4A4A804C06DE06@qq.com>
 <CANWCAZZA_AqWy7xw20O=jWG+t0Cy4rUnvs1RaAABvSp3iLnGhg@mail.gmail.com>
 <tencent_0A6A072C7636A1238520B50E29D332627808@qq.com>
 <CANWCAZaWV09=HdiF9mm7CBggFvxGkkHhhkSqyFoochQzW=RxAA@mail.gmail.com>
In-Reply-To: 
 <CANWCAZaWV09=HdiF9mm7CBggFvxGkkHhhkSqyFoochQzW=RxAA@mail.gmail.com>
From: John Naylor <johncnaylorls@gmail.com>
Date: Mon, 30 Mar 2026 12:57:52 +0700
Message-ID: 
 <CANWCAZZuQPMAPoCUQo7E2v2Zk5z9T=8bE=VGpC8_TYG3aomGyQ@mail.gmail.com>
Subject: Re: tuple radix sort
To: cca5507 <cca5507@qq.com>
Cc: zengman <zengman@halodbtech.com>,
	pgsql-hackers <pgsql-hackers@lists.postgresql.org>
Content-Type: multipart/mixed; boundary="000000000000b74ddf064e37883e"
Archived-At: 
 <https://www.postgresql.org/message-id/CANWCAZZuQPMAPoCUQo7E2v2Zk5z9T%3D8bE%3DVGpC8_TYG3aomGyQ%40mail.gmail.com>
Precedence: bulk

--000000000000b74ddf064e37883e
Content-Type: text/plain; charset="UTF-8"

I wrote:
> Next step : Test whether it's worth it for the common prefix detection
> to use the normalized datum.

This turned out to be a loser, but in the course of trying it a better
idea occurred to me. v8's prefix detection was really a special-case
optimization where the sort key is all non-negative integers (or all
negative, but that's not common). It's wasted work when the input is
mixed in sign, and for abbreviated keys. It's not much of a waste, but
we can do better.

v9 computes the common prefix during every recursion at the same time
we populate the SortTuple's current byte. That should be practically
free given a modest amount of instruction-level parallelism.

As a demo, I slightly modified the "p5" test (an adversarial case for
radix sort) from

https://www.postgresql.org/message-id/CANWCAZb0STJRAnn8fcVccQmektizNkgqBD_cg%2B0cs1%3Db4WWajQ%40mail.gmail.com

...so that all bytes differ only in the least significant byte or in
the sign bit.

select setseed(0.935349);
with r (rand, i) as (select random(-100, 100), i
from generate_series(1,1_000_000,1) i )
insert into tsort
select case
 when r.rand < -95 or r.rand > 95
 then r.rand
 else 0 end
 from r;

vacuum freeze tsort ;

cat bench.sql
select * from tsort order by i offset 100000000;

pgbench -n -t 500 -f bench.sql | grep latency
(on pre-warmed buffers with work_mem 64MB)

master:
latency average = 99.663 ms
v8:
latency average = 102.040 ms
v9:
latency average = 84.856 ms

Here we can see that common prefix detection is useless in v8. It adds
work, but it's not worse than noise in this benchmark, so could be
disregarded. In v9 we proceed directly to performing a radix sort pass
on the most significant byte, which effectively partitions into signed
and unsigned. The next recursion step detects that all bytes are the
same and simultaneously calculates how far to skip so that the next
recursion is productive.

For the case of all non-negative integers:

select setseed(0.935349);
insert into tsort
select random(0, 100)
from generate_series(1,1_000_000,1) i;
vacuum freeze tsort ;

...in v9 the first pass computes the current byte from the normalized
datum and stores it, but this pass is unproductive. There was a risk
that this is more expensive than v8's up-front common prefix detection
because of memory writes. I only see noise-level differences:

master:
latency average = 98.725 ms
v8:
latency average = 75.572 ms
v9:
latency average = 76.635 ms

I intend to commit v9-0001 this week.

I've decided not to commit v8-0003 (message changes) from my last
message since it doesn't really add any value IMO. That can always be
revisited. I'm on the fence about v8-0004 (assert the correct order
also for qsort), but it seems good for consistency. I'd like to at
least continue asserting this for radix sort since it's new this
cycle. To save CI cycles etc, maybe we can eventually hide the check
behind a debug symbol.

-- 
John Naylor
Amazon Web Services

--000000000000b74ddf064e37883e
Content-Type: text/x-patch; charset="US-ASCII";
	name="v9-0001-Detect-common-prefixes-during-radix-sort.patch"
Content-Disposition: attachment;
	filename="v9-0001-Detect-common-prefixes-during-radix-sort.patch"
Content-Transfer-Encoding: base64
Content-ID: <f_mncreb760>
X-Attachment-Id: f_mncreb760

RnJvbSA2ZTk0YjBhMjYwYmM4MTI0ODM3NWM3ZDQ1NTY4YTUyZjE3Mjc0YmY5IE1vbiBTZXAgMTcg
MDA6MDA6MDAgMjAwMQpGcm9tOiBKb2huIE5heWxvciA8am9obi5uYXlsb3JAcG9zdGdyZXNxbC5v
cmc+CkRhdGU6IE1vbiwgMzAgTWFyIDIwMjYgMTI6MjY6NTggKzA3MDAKU3ViamVjdDogW1BBVENI
IHY5XSBEZXRlY3QgY29tbW9uIHByZWZpeGVzIGR1cmluZyByYWRpeCBzb3J0CgpEdXJpbmcgdGhl
IGNvdW50aW5nIHN0ZXAsIGtlZXAgdHJhY2sgb2YgdGhlIGJpdHMgdGhhdCBhcmUgdGhlIHNhbWUK
Zm9yIHRoZSBlbnRpcmUgaW5wdXQuICBJZiB3ZSBjb3VudGVkIG9ubHkgYSBzaW5nbGUgZGlzdGlu
Y3QgYnl0ZSwKdGhlIG5leHQgcmVjdXJzaW9uIHdpbGwgc3RhcnQgYXQgdGhlIG5leHQgYnl0ZSBw
b3NpdGlvbiB0aGF0IGhhcwptb3JlIHRoYW4gb25lIGRpc3RpbmN0IGJ5dGUgaW4gdGhlIGlucHV0
LiBUaGlzIGFsbG93cyB1cyB0byBza2lwIG92ZXIKbXVsdGlwbGUgcGFzc2VzIHdoZXJlIHRoZSBi
eXRlIGlzIHRoZSBzYW1lIGZvciB0aGUgZW50aXJlIGlucHV0LgoKVGhpcyBwcm92aWRlcyBhIHNp
Z25pZmljYW50IHNwZWVkdXAgZm9yIGludGVnZXJzIHRoYXQgaGF2ZSBzb21lIHVwcGVyCmJ5dGVz
IHdpdGggYWxsLXplcm9zIG9yIGFsbC1vbmVzLCB3aGljaCBpcyBjb21tb24uCgpSZXZpZXdlZC1i
eTogQ2hlbmdwZW5nIFlhbiA8Y2hlbmdwZW5nX3lhbkBvdXRsb29rLmNvbT4KRGlzY3Vzc2lvbjog
aHR0cHM6Ly9wb3N0Z3IuZXMvbS9DQU5XQ0FaWXBHTURTU3dBYTE4Zk94SkdYYVB6VmR5UHNXcE9r
ZkNYMzJEV2gzUXpuendAbWFpbC5nbWFpbC5jb20KLS0tCiBzcmMvYmFja2VuZC91dGlscy9zb3J0
L3R1cGxlc29ydC5jIHwgNDQgKysrKysrKysrKysrKysrKysrKysrKysrKysrLS0tCiAxIGZpbGUg
Y2hhbmdlZCwgNDAgaW5zZXJ0aW9ucygrKSwgNCBkZWxldGlvbnMoLSkKCmRpZmYgLS1naXQgYS9z
cmMvYmFja2VuZC91dGlscy9zb3J0L3R1cGxlc29ydC5jIGIvc3JjL2JhY2tlbmQvdXRpbHMvc29y
dC90dXBsZXNvcnQuYwppbmRleCAxZmM0NDBlYTZjYS4uNzJjMmMyOTk1ZDggMTAwNjQ0Ci0tLSBh
L3NyYy9iYWNrZW5kL3V0aWxzL3NvcnQvdHVwbGVzb3J0LmMKKysrIGIvc3JjL2JhY2tlbmQvdXRp
bHMvc29ydC90dXBsZXNvcnQuYwpAQCAtMTA0LDYgKzEwNCw3IEBACiAjaW5jbHVkZSAiY29tbWFu
ZHMvdGFibGVzcGFjZS5oIgogI2luY2x1ZGUgIm1pc2NhZG1pbi5oIgogI2luY2x1ZGUgInBnX3Ry
YWNlLmgiCisjaW5jbHVkZSAicG9ydC9wZ19iaXR1dGlscy5oIgogI2luY2x1ZGUgInN0b3JhZ2Uv
c2htZW0uaCIKICNpbmNsdWRlICJ1dGlscy9ndWMuaCIKICNpbmNsdWRlICJ1dGlscy9tZW11dGls
cy5oIgpAQCAtMjY1OSwxNyArMjY2MCwyNSBAQCByYWRpeF9zb3J0X3JlY3Vyc2l2ZShTb3J0VHVw
bGUgKmJlZ2luLCBzaXplX3Qgbl9lbGVtcywgaW50IGxldmVsLCBUdXBsZXNvcnRzdGF0ZQogCWlu
dAkJCW51bV9wYXJ0aXRpb25zID0gMDsKIAlpbnQJCQludW1fcmVtYWluaW5nOwogCVNvcnRTdXBw
b3J0IHNzdXAgPSAmc3RhdGUtPmJhc2Uuc29ydEtleXNbMF07CisJRGF0dW0JCXJlZl9kYXR1bTsK
KwlEYXR1bQkJY29tbW9uX3VwcGVyX2JpdHMgPSAwOwogCXNpemVfdAkJc3RhcnRfb2Zmc2V0ID0g
MDsKIAlTb3J0VHVwbGUgICpwYXJ0aXRpb25fYmVnaW4gPSBiZWdpbjsKKwlpbnQJCQluZXh0X2xl
dmVsOwogCiAJLyogY291bnQgbnVtYmVyIG9mIG9jY3VycmVuY2VzIG9mIGVhY2ggYnl0ZSAqLwor
CXJlZl9kYXR1bSA9IG5vcm1hbGl6ZV9kYXR1bShiZWdpblswXS5kYXR1bTEsIHNzdXApOwogCWZv
ciAoU29ydFR1cGxlICpzdCA9IGJlZ2luOyBzdCA8IGJlZ2luICsgbl9lbGVtczsgc3QrKykKIAl7
CisJCURhdHVtCQl0aGlzX2RhdHVtOwogCQl1aW50OAkJdGhpc19wYXJ0aXRpb247CiAKKwkJdGhp
c19kYXR1bSA9IG5vcm1hbGl6ZV9kYXR1bShzdC0+ZGF0dW0xLCBzc3VwKTsKKwkJLyogYWNjdW11
bGF0ZSBiaXRzIGRpZmZlcmVudCBmcm9tIHRoZSByZWZlcmVuY2UgZGF0dW0gKi8KKwkJY29tbW9u
X3VwcGVyX2JpdHMgfD0gcmVmX2RhdHVtIF4gdGhpc19kYXR1bTsKKwogCQkvKiBleHRyYWN0IHRo
ZSBieXRlIGZvciB0aGlzIGxldmVsIGZyb20gdGhlIG5vcm1hbGl6ZWQgZGF0dW0gKi8KLQkJdGhp
c19wYXJ0aXRpb24gPSBjdXJyZW50X2J5dGUobm9ybWFsaXplX2RhdHVtKHN0LT5kYXR1bTEsIHNz
dXApLAotCQkJCQkJCQkJICBsZXZlbCk7CisJCXRoaXNfcGFydGl0aW9uID0gY3VycmVudF9ieXRl
KHRoaXNfZGF0dW0sIGxldmVsKTsKIAogCQkvKiBzYXZlIGl0IGZvciB0aGUgcGVybXV0YXRpb24g
c3RlcCAqLwogCQlzdC0+Y3VyYnl0ZSA9IHRoaXNfcGFydGl0aW9uOwpAQCAtMjc0Nyw2ICsyNzU2
LDMzIEBAIHJhZGl4X3NvcnRfcmVjdXJzaXZlKFNvcnRUdXBsZSAqYmVnaW4sIHNpemVfdCBuX2Vs
ZW1zLCBpbnQgbGV2ZWwsIFR1cGxlc29ydHN0YXRlCiAJfQogCiAJLyogcmVjdXJzZSAqLworCisJ
aWYgKG51bV9wYXJ0aXRpb25zID09IDEpCisJeworCQkvKgorCQkgKiBUaGVyZSBpcyBvbmx5IG9u
ZSBkaXN0aW5jdCBieXRlIGF0IHRoZSBjdXJyZW50IGxldmVsLiBJdCBjYW4gaGFwcGVuCisJCSAq
IHRoYXQgc29tZSBzdWJzZXF1ZW50IGJ5dGVzIGFyZSBhbHNvIHRoZSBzYW1lIGZvciBhbGwgaW5w
dXQgdmFsdWVzLAorCQkgKiBzdWNoIGFzIHRoZSB1cHBlciBieXRlcyBvZiBzbWFsbCBpbnRlZ2Vy
cy4gVG8gc2tpcCB1bnByb2R1Y3RpdmUKKwkJICogcGFzc2VzIGZvciB0aGF0IGNhc2UsIHdlIGNv
bXB1dGUgdGhlIGxldmVsIHdoZXJlIHRoZSBpbnB1dCBoYXMgbW9yZQorCQkgKiB0aGFuIG9uZSBk
aXN0aW5jdCBieXRlLCBzbyB0aGF0IHRoZSBuZXh0IHJlY3Vyc2lvbiBjYW4gc3RhcnQgdGhlcmUu
CisJCSAqLworCQlpZiAoY29tbW9uX3VwcGVyX2JpdHMgPT0gMCkKKwkJCW5leHRfbGV2ZWwgPSBz
aXplb2YoRGF0dW0pOworCQllbHNlCisJCXsKKwkJCWludAkJCWRpZmZwb3M7CisKKwkJCS8qCisJ
CQkgKiBUaGUgdXBwZXIgYml0cyBvZiBjb21tb25fdXBwZXJfYml0cyBhcmUgemVybyB3aGVyZSBh
bGwgZGF0dW1zCisJCQkgKiBoYXZlIHRoZSBzYW1lIGJpdHMuCisJCQkgKi8KKwkJCWRpZmZwb3Mg
PSBwZ19sZWZ0bW9zdF9vbmVfcG9zNjQoRGF0dW1HZXRVSW50NjQoY29tbW9uX3VwcGVyX2JpdHMp
KTsKKwkJCW5leHRfbGV2ZWwgPSBzaXplb2YoRGF0dW0pIC0gMSAtIChkaWZmcG9zIC8gQklUU19Q
RVJfQllURSk7CisJCX0KKwl9CisJZWxzZQorCQluZXh0X2xldmVsID0gbGV2ZWwgKyAxOworCiAJ
Zm9yICh1aW50OCAqcnAgPSByZW1haW5pbmdfcGFydGl0aW9uczsKIAkJIHJwIDwgcmVtYWluaW5n
X3BhcnRpdGlvbnMgKyBudW1fcGFydGl0aW9uczsKIAkJIHJwKyspCkBAIC0yNzU3LDcgKzI3OTMs
NyBAQCByYWRpeF9zb3J0X3JlY3Vyc2l2ZShTb3J0VHVwbGUgKmJlZ2luLCBzaXplX3Qgbl9lbGVt
cywgaW50IGxldmVsLCBUdXBsZXNvcnRzdGF0ZQogCiAJCWlmIChudW1fZWxlbWVudHMgPiAxKQog
CQl7Ci0JCQlpZiAobGV2ZWwgPCBzaXplb2YoRGF0dW0pIC0gMSkKKwkJCWlmIChuZXh0X2xldmVs
IDwgc2l6ZW9mKERhdHVtKSkKIAkJCXsKIAkJCQlpZiAobnVtX2VsZW1lbnRzIDwgUVNPUlRfVEhS
RVNIT0xEKQogCQkJCXsKQEAgLTI3NzAsNyArMjgwNiw3IEBAIHJhZGl4X3NvcnRfcmVjdXJzaXZl
KFNvcnRUdXBsZSAqYmVnaW4sIHNpemVfdCBuX2VsZW1zLCBpbnQgbGV2ZWwsIFR1cGxlc29ydHN0
YXRlCiAJCQkJewogCQkJCQlyYWRpeF9zb3J0X3JlY3Vyc2l2ZShwYXJ0aXRpb25fYmVnaW4sCiAJ
CQkJCQkJCQkJIG51bV9lbGVtZW50cywKLQkJCQkJCQkJCQkgbGV2ZWwgKyAxLAorCQkJCQkJCQkJ
CSBuZXh0X2xldmVsLAogCQkJCQkJCQkJCSBzdGF0ZSk7CiAJCQkJfQogCQkJfQotLSAKMi41My4w
Cgo=
--000000000000b74ddf064e37883e--