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>
In-Reply-To: <tencent_0A6A072C7636A1238520B50E29D332627808@qq.com>
From: John Naylor <johncnaylorls@gmail.com>
Date: Sun, 15 Feb 2026 15:40:35 +0700
Message-ID: <CANWCAZaWV09=HdiF9mm7CBggFvxGkkHhhkSqyFoochQzW=RxAA@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="0000000000007523ba064ad8cb04"
Archived-At: <https://www.postgresql.org/message-id/CANWCAZaWV09%3DHdiF9mm7CBggFvxGkkHhhkSqyFoochQzW%3DRxAA%40mail.gmail.com>
Precedence: bulk

--0000000000007523ba064ad8cb04
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

I've committed v7-0001 with the above review and a couple more
cosmetic adjustments. Most notably, I've never really liked the name
sort_byvalue_datum(). It really is the entry point to radix sort, and
it only diverts to qsort if after the NULL partitioning phase there
aren't enough non-null tuples to justify the overhead of radix sort.
So for better symmetry with qsort_tuple, I've renamed
sort_byvalue_datum() to radix_sort_tuple(), which then calls out to
now-named radix_sort_recursive(), which will call itself until it
completes or diverts. Another change down below:

On Fri, Feb 13, 2026 at 10:25=E2=80=AFAM cca5507 <cca5507@qq.com> wrote:
> I think we need to add a comment to explain why we do the
> check. The cost of this check is not small.

(presorted check) The cost should only matter for pathological inputs,
and I haven't found it to matter much overall. I've left it
uncommented for now. However, while rebasing 0002 to deal with recent
review comments, I had an idea: In yesterday's commit, I moved the
presorted check down to just before invoking the actual radix sort.
That way, with the attached v8-0002 the common prefix detection is
done at the same time as the presorted check. That makes 0002 a
smaller patch and by doing both in the same for-loop it's easier to
read and can reduce the number of memory reads. We can consider more
commentary here, but the motivation do avoid unnecessary work should
be fairly obvious.

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

--
John Naylor
Amazon Web Services

--0000000000007523ba064ad8cb04
Content-Type: text/x-patch; charset="US-ASCII"; 
	name="v8-0004-WIP-Call-verify_memtuples_sorted-after-qsort-for-.patch"
Content-Disposition: attachment; 
	filename="v8-0004-WIP-Call-verify_memtuples_sorted-after-qsort-for-.patch"
Content-Transfer-Encoding: base64
Content-ID: <f_mlnhfzvi0>
X-Attachment-Id: f_mlnhfzvi0

RnJvbSAxNGRmNTg1NGRlNGI3M2RhODc5MmMwMTU4NTllOGQ3ZWNmMDlkNGQwIE1vbiBTZXAgMTcg
MDA6MDA6MDAgMjAwMQpGcm9tOiBKb2huIE5heWxvciA8am9obi5uYXlsb3JAcG9zdGdyZXNxbC5v
cmc+CkRhdGU6IFR1ZSwgMTAgRmViIDIwMjYgMTk6MTA6MjAgKzA3MDAKU3ViamVjdDogW1BBVENI
IHY4IDQvNF0gV0lQIENhbGwgdmVyaWZ5X21lbXR1cGxlc19zb3J0ZWQoKSBhZnRlciBxc29ydCBm
b3IKIGNvbnNpc3RlbmN5CgpUaGUgcmVncmVzc2lvbiB0ZXN0IGNoYW5nZXMgYXJlIGZyb20gYSB1
c2VyIGRlZmluZWQgZnVuY3Rpb24gdGhhdAppcyBub3cgY2FsbGVkIGEgY291cGxlIG1vcmUgdGlt
ZXMuCi0tLQogc3JjL2JhY2tlbmQvdXRpbHMvc29ydC90dXBsZXNvcnQuYyAgICAgIHwgMSArCiBz
cmMvdGVzdC9yZWdyZXNzL2V4cGVjdGVkL25hbWVzcGFjZS5vdXQgfCAyICsrCiAyIGZpbGVzIGNo
YW5nZWQsIDMgaW5zZXJ0aW9ucygrKQoKZGlmZiAtLWdpdCBhL3NyYy9iYWNrZW5kL3V0aWxzL3Nv
cnQvdHVwbGVzb3J0LmMgYi9zcmMvYmFja2VuZC91dGlscy9zb3J0L3R1cGxlc29ydC5jCmluZGV4
IDYyOWQ1OThkOGI3Li5kZWEzMzQ3NjY3ZiAxMDA2NDQKLS0tIGEvc3JjL2JhY2tlbmQvdXRpbHMv
c29ydC90dXBsZXNvcnQuYworKysgYi9zcmMvYmFja2VuZC91dGlscy9zb3J0L3R1cGxlc29ydC5j
CkBAIC0zMDMzLDYgKzMwMzMsNyBAQCB0dXBsZXNvcnRfc29ydF9tZW10dXBsZXMoVHVwbGVzb3J0
c3RhdGUgKnN0YXRlKQogCQkJCQkJc3RhdGUtPmJhc2UuY29tcGFyZXR1cCwKIAkJCQkJCXN0YXRl
KTsKIAkJfQorCQl2ZXJpZnlfbWVtdHVwbGVzX3NvcnRlZChzdGF0ZSk7CiAJfQogfQogCmRpZmYg
LS1naXQgYS9zcmMvdGVzdC9yZWdyZXNzL2V4cGVjdGVkL25hbWVzcGFjZS5vdXQgYi9zcmMvdGVz
dC9yZWdyZXNzL2V4cGVjdGVkL25hbWVzcGFjZS5vdXQKaW5kZXggZGJiZGE3MmQzOTUuLmI3OGFi
ZGYyMWVhIDEwMDY0NAotLS0gYS9zcmMvdGVzdC9yZWdyZXNzL2V4cGVjdGVkL25hbWVzcGFjZS5v
dXQKKysrIGIvc3JjL3Rlc3QvcmVncmVzcy9leHBlY3RlZC9uYW1lc3BhY2Uub3V0CkBAIC0xNDks
NiArMTQ5LDggQEAgTk9USUNFOiAgY3VycmVudCBzZWFyY2hfcGF0aDogcGdfY2F0YWxvZywgcGdf
dGVtcAogTk9USUNFOiAgY3VycmVudCBzZWFyY2hfcGF0aDogcGdfY2F0YWxvZywgcGdfdGVtcAog
Tk9USUNFOiAgY3VycmVudCBzZWFyY2hfcGF0aDogcGdfY2F0YWxvZywgcGdfdGVtcAogTk9USUNF
OiAgY3VycmVudCBzZWFyY2hfcGF0aDogcGdfY2F0YWxvZywgcGdfdGVtcAorTk9USUNFOiAgY3Vy
cmVudCBzZWFyY2hfcGF0aDogcGdfY2F0YWxvZywgcGdfdGVtcAorTk9USUNFOiAgY3VycmVudCBz
ZWFyY2hfcGF0aDogcGdfY2F0YWxvZywgcGdfdGVtcAogUkVGUkVTSCBNQVRFUklBTElaRUQgVklF
VyB0ZXN0X21haW50X3NlYXJjaF9wYXRoLnRlc3RfbWFpbnRfbXY7CiBOT1RJQ0U6ICBjdXJyZW50
IHNlYXJjaF9wYXRoOiBwZ19jYXRhbG9nLCBwZ190ZW1wCiBOT1RJQ0U6ICBjdXJyZW50IHNlYXJj
aF9wYXRoOiBwZ19jYXRhbG9nLCBwZ190ZW1wCi0tIAoyLjUzLjAKCg==
--0000000000007523ba064ad8cb04
Content-Type: text/x-patch; charset="US-ASCII"; 
	name="v8-0003-WIP-Add-possible-message-changes.patch"
Content-Disposition: attachment; 
	filename="v8-0003-WIP-Add-possible-message-changes.patch"
Content-Transfer-Encoding: base64
Content-ID: <f_mlnhfzwa1>
X-Attachment-Id: f_mlnhfzwa1

RnJvbSBhN2RmYzFjOWZhNTM1ZGZjZWFjNDhmOGU5MWFkMmNiNTE2ODcyODU1IE1vbiBTZXAgMTcg
MDA6MDA6MDAgMjAwMQpGcm9tOiBKb2huIE5heWxvciA8am9obi5uYXlsb3JAcG9zdGdyZXNxbC5v
cmc+CkRhdGU6IFR1ZSwgMTAgRmViIDIwMjYgMjA6MDI6MTkgKzA3MDAKU3ViamVjdDogW1BBVENI
IHY4IDMvNF0gV0lQIEFkZCBwb3NzaWJsZSBtZXNzYWdlIGNoYW5nZXMKCk5vdCBzdXJlIGlmIG5l
Y2Vzc2FyeSBzbyBrZXB0IG91dCBvZiBtYWluIGNvbW1pdAotLS0KIHNyYy9iYWNrZW5kL3V0aWxz
L3NvcnQvdHVwbGVzb3J0LmMgfCA0ICsrLS0KIDEgZmlsZSBjaGFuZ2VkLCAyIGluc2VydGlvbnMo
KyksIDIgZGVsZXRpb25zKC0pCgpkaWZmIC0tZ2l0IGEvc3JjL2JhY2tlbmQvdXRpbHMvc29ydC90
dXBsZXNvcnQuYyBiL3NyYy9iYWNrZW5kL3V0aWxzL3NvcnQvdHVwbGVzb3J0LmMKaW5kZXggMjIw
M2NmYjcyNWQuLjYyOWQ1OThkOGI3IDEwMDY0NAotLS0gYS9zcmMvYmFja2VuZC91dGlscy9zb3J0
L3R1cGxlc29ydC5jCisrKyBiL3NyYy9iYWNrZW5kL3V0aWxzL3NvcnQvdHVwbGVzb3J0LmMKQEAg
LTIyNDMsNyArMjI0Myw3IEBAIGR1bXB0dXBsZXMoVHVwbGVzb3J0c3RhdGUgKnN0YXRlLCBib29s
IGFsbHR1cGxlcykKIAlzdGF0ZS0+Y3VycmVudFJ1bisrOwogCiAJaWYgKHRyYWNlX3NvcnQpCi0J
CWVsb2coTE9HLCAid29ya2VyICVkIHN0YXJ0aW5nIHF1aWNrc29ydCBvZiBydW4gJWQ6ICVzIiwK
KwkJZWxvZyhMT0csICJ3b3JrZXIgJWQgc3RhcnRpbmcgaW50ZXJuYWwgc29ydCBvZiBydW4gJWQ6
ICVzIiwKIAkJCSBzdGF0ZS0+d29ya2VyLCBzdGF0ZS0+Y3VycmVudFJ1biwKIAkJCSBwZ19ydXNh
Z2Vfc2hvdygmc3RhdGUtPnJ1X3N0YXJ0KSk7CiAKQEAgLTIyNTQsNyArMjI1NCw3IEBAIGR1bXB0
dXBsZXMoVHVwbGVzb3J0c3RhdGUgKnN0YXRlLCBib29sIGFsbHR1cGxlcykKIAl0dXBsZXNvcnRf
c29ydF9tZW10dXBsZXMoc3RhdGUpOwogCiAJaWYgKHRyYWNlX3NvcnQpCi0JCWVsb2coTE9HLCAi
d29ya2VyICVkIGZpbmlzaGVkIHF1aWNrc29ydCBvZiBydW4gJWQ6ICVzIiwKKwkJZWxvZyhMT0cs
ICJ3b3JrZXIgJWQgZmluaXNoZWQgaW50ZXJuYWwgc29ydCBvZiBydW4gJWQ6ICVzIiwKIAkJCSBz
dGF0ZS0+d29ya2VyLCBzdGF0ZS0+Y3VycmVudFJ1biwKIAkJCSBwZ19ydXNhZ2Vfc2hvdygmc3Rh
dGUtPnJ1X3N0YXJ0KSk7CiAKLS0gCjIuNTMuMAoK
--0000000000007523ba064ad8cb04
Content-Type: text/x-patch; charset="US-ASCII"; 
	name="v8-0002-Detect-common-prefix-to-avoid-wasted-work-during-.patch"
Content-Disposition: attachment; 
	filename="v8-0002-Detect-common-prefix-to-avoid-wasted-work-during-.patch"
Content-Transfer-Encoding: base64
Content-ID: <f_mlnhfzwi2>
X-Attachment-Id: f_mlnhfzwi2

RnJvbSBhYjhiYTcxYjAxODQyMzc3OTI4OWM0NDJmMDVhMzY5ZTM3M2RjNDFkIE1vbiBTZXAgMTcg
MDA6MDA6MDAgMjAwMQpGcm9tOiBKb2huIE5heWxvciA8am9obi5uYXlsb3JAcG9zdGdyZXNxbC5v
cmc+CkRhdGU6IFNhdCwgMTQgRmViIDIwMjYgMTE6NDE6MzQgKzA3MDAKU3ViamVjdDogW1BBVENI
IHY4IDIvNF0gRGV0ZWN0IGNvbW1vbiBwcmVmaXggdG8gYXZvaWQgd2FzdGVkIHdvcmsgZHVyaW5n
IHJhZGl4CiBzb3J0CgpTdGFydCByYWRpeCBzb3J0IGF0IHRoZSBtb3N0IHNpZ25pZmljYW50IGJ5
dGUgcG9zaXRpb24gdGhhdCBoYXMgbW9yZQp0aGFuIG9uZSBkaXN0aW5jdCBieXRlIGluIHRoZSBp
bnB1dC4gVGhpcyBza2lwcyBwYXNzZXMgd2hlcmUgcmFkaXgKc29ydCB3b3VsZCBjb3VudCB0aGUg
ZGlzdGluY3QgYnl0ZXMganVzdCB0byBmaW5kIG9ubHkgYSBzaW5nbGUgb25lLAppbiB3aGljaCBj
YXNlIHRoZXJlIGlzIG5vdGhpbmcgZnVydGhlciB0byBkbyBmb3IgdGhhdCBwYXNzLiBUaGlzIGNh
bgpnaXZlIGEgZmV3IHBlcmNlbnQgc3BlZWR1cCBmb3IgaW50ZWdlcnMgdGhhdCBoYXZlIHNvbWUg
emVybyB1cHBlcgpieXRlcywgd2hpY2ggaXMgY29tbW9uIGZvciB0aG9zZSB0aGF0IGRpZG4ndCBh
cnJpdmUgdmlhIGFiYnJldmlhdGlvbi4KClJldmlld2VkLWJ5OiBDaGVuZ3BlbmcgWWFuIDxjaGVu
Z3BlbmdfeWFuQG91dGxvb2suY29tPgpEaXNjdXNzaW9uOiBodHRwczovL3Bvc3Rnci5lcy9tL0NB
TldDQVpZcEdNRFNTd0FhMThmT3hKR1hhUHpWZHlQc1dwT2tmQ1gzMkRXaDNRem56d0BtYWlsLmdt
YWlsLmNvbQotLS0KIHNyYy9iYWNrZW5kL3V0aWxzL3NvcnQvdHVwbGVzb3J0LmMgfCA0OCArKysr
KysrKysrKysrKysrKysrKysrKysrKy0tLS0KIDEgZmlsZSBjaGFuZ2VkLCA0MyBpbnNlcnRpb25z
KCspLCA1IGRlbGV0aW9ucygtKQoKZGlmZiAtLWdpdCBhL3NyYy9iYWNrZW5kL3V0aWxzL3NvcnQv
dHVwbGVzb3J0LmMgYi9zcmMvYmFja2VuZC91dGlscy9zb3J0L3R1cGxlc29ydC5jCmluZGV4IDFm
YzQ0MGVhNmNhLi4yMjAzY2ZiNzI1ZCAxMDA2NDQKLS0tIGEvc3JjL2JhY2tlbmQvdXRpbHMvc29y
dC90dXBsZXNvcnQuYworKysgYi9zcmMvYmFja2VuZC91dGlscy9zb3J0L3R1cGxlc29ydC5jCkBA
IC0xMDQsNiArMTA0LDcgQEAKICNpbmNsdWRlICJjb21tYW5kcy90YWJsZXNwYWNlLmgiCiAjaW5j
bHVkZSAibWlzY2FkbWluLmgiCiAjaW5jbHVkZSAicGdfdHJhY2UuaCIKKyNpbmNsdWRlICJwb3J0
L3BnX2JpdHV0aWxzLmgiCiAjaW5jbHVkZSAic3RvcmFnZS9zaG1lbS5oIgogI2luY2x1ZGUgInV0
aWxzL2d1Yy5oIgogI2luY2x1ZGUgInV0aWxzL21lbXV0aWxzLmgiCkBAIC0yOTA5LDI4ICsyOTEw
LDY1IEBAIHJhZGl4X3NvcnRfdHVwbGUoU29ydFR1cGxlICpkYXRhLCBzaXplX3QgbiwgVHVwbGVz
b3J0c3RhdGUgKnN0YXRlKQogCX0KIAllbHNlCiAJeworCQlpbnQJCQljb21tb25fcHJlZml4Owor
CQlEYXR1bQkJcmVmX2RhdHVtOworCQlEYXR1bQkJY29tbW9uX3VwcGVyX2JpdHMgPSAwOwogCQli
b29sCQlwcmVzb3J0ZWQgPSB0cnVlOwogCisJCUFzc2VydChub3RfbnVsbF9jb3VudCA+IDApOwor
CQlyZWZfZGF0dW0gPSBub3RfbnVsbF9zdGFydFswXS5kYXR1bTE7CisKKwkJLyogY29tcHV0ZSB0
aGUgY29tbW9uIHByZWZpeCBvZiBhbGwgZGF0dW1zICovCiAJCWZvciAoU29ydFR1cGxlICpzdCA9
IG5vdF9udWxsX3N0YXJ0ICsgMTsKIAkJCSBzdCA8IG5vdF9udWxsX3N0YXJ0ICsgbm90X251bGxf
Y291bnQ7CiAJCQkgc3QrKykKIAkJewotCQkJaWYgKENPTVBBUkVUVVAoc3RhdGUsIHN0IC0gMSwg
c3QpID4gMCkKLQkJCXsKKwkJCURhdHVtCQl0aGlzX2RhdHVtID0gc3QtPmRhdHVtMTsKKworCQkJ
LyoKKwkJCSAqIEFjY3VtdWxhdGUgYml0cyB0aGF0IHJlcHJlc2VudCBhIGRpZmZlcmVuY2UgZnJv
bSB0aGUgcmVmZXJlbmNlCisJCQkgKiBkYXR1bS4KKwkJCSAqLworCQkJY29tbW9uX3VwcGVyX2Jp
dHMgfD0gcmVmX2RhdHVtIF4gdGhpc19kYXR1bTsKKworCQkJLyogZG8gYSBwcmVzb3J0ZWQgY2hl
Y2sgd2hpbGUgd2UncmUgYXQgaXQgKi8KKwkJCWlmIChwcmVzb3J0ZWQgJiYgQ09NUEFSRVRVUChz
dGF0ZSwgc3QgLSAxLCBzdCkgPiAwKQogCQkJCXByZXNvcnRlZCA9IGZhbHNlOwotCQkJCWJyZWFr
OwotCQkJfQogCiAJCQlDSEVDS19GT1JfSU5URVJSVVBUUygpOwogCQl9CiAKIAkJaWYgKHByZXNv
cnRlZCkKIAkJCXJldHVybjsKKwkJZWxzZSBpZiAoY29tbW9uX3VwcGVyX2JpdHMgPT0gMCkKKwkJ
eworCQkJLyoKKwkJCSAqIEFsbCBOT1QgTlVMTCB0dXBsZXMgaGF2ZSB0aGUgc2FtZSBkYXR1bSwg
c28gd2UgY2FuIHNraXAgcmFkaXgKKwkJCSAqIHNvcnQuIFNvcnQgdXNpbmcgdGhlIHRpZWJyZWFr
IGNvbXBhcmF0b3IgaWYgbmVjZXNzYXJ5LgorCQkJICovCisJCQlpZiAoc3RhdGUtPmJhc2Uub25s
eUtleSA9PSBOVUxMKQorCQkJeworCQkJCXFzb3J0X3R1cGxlKG5vdF9udWxsX3N0YXJ0LAorCQkJ
CQkJCW5vdF9udWxsX2NvdW50LAorCQkJCQkJCXN0YXRlLT5iYXNlLmNvbXBhcmV0dXBfdGllYnJl
YWssCisJCQkJCQkJc3RhdGUpOworCQkJfQorCQl9CiAJCWVsc2UKIAkJeworCQkJaW50CQkJZGlm
ZnBvczsKKworCQkJLyoKKwkJCSAqIFRoZSB1cHBlciBiaXRzIG9mIGNvbW1vbl91cHBlcl9iaXRz
IGFyZSB6ZXJvIHdoZXJlIGFsbCBkYXR1bXMKKwkJCSAqIGhhdmUgdGhlIHNhbWUgYml0cy4gVGhl
IGJ5dGUgcG9zaXRpb24gb2YgdGhlIGxlZnRtb3N0IG9uZSBiaXQKKwkJCSAqIGlzIHRoZSBieXRl
IHdoZXJlIHJhZGl4IHNvcnQgc2hvdWxkIHN0YXJ0LgorCQkJICovCisJCQlkaWZmcG9zID0gcGdf
bGVmdG1vc3Rfb25lX3BvczY0KERhdHVtR2V0VUludDY0KGNvbW1vbl91cHBlcl9iaXRzKSk7CisJ
CQljb21tb25fcHJlZml4ID0gc2l6ZW9mKERhdHVtKSAtIDEgLSAoZGlmZnBvcyAvIEJJVFNfUEVS
X0JZVEUpOworCiAJCQlyYWRpeF9zb3J0X3JlY3Vyc2l2ZShub3RfbnVsbF9zdGFydCwKIAkJCQkJ
CQkJIG5vdF9udWxsX2NvdW50LAotCQkJCQkJCQkgMCwKKwkJCQkJCQkJIGNvbW1vbl9wcmVmaXgs
CiAJCQkJCQkJCSBzdGF0ZSk7CiAJCX0KIAl9Ci0tIAoyLjUzLjAKCg==
--0000000000007523ba064ad8cb04--