Content-Type: text/plain;
	charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3826.700.81\))
Subject: Re: tuple radix sort
From: Chao Li <li.evan.chao@gmail.com>
In-Reply-To: 
 <CANWCAZYzx7a7E9AY16Jt_U3+GVKDADfgApZ-42SYNiig8dTnFA@mail.gmail.com>
Date: Wed, 29 Oct 2025 16:25:03 +0800
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>,
 Peter Geoghegan <pg@bowt.ie>
Content-Transfer-Encoding: quoted-printable
Message-Id: <DDA507E1-56DB-4D76-8B81-41660ED932B9@gmail.com>
References: 
 <CANWCAZYzx7a7E9AY16Jt_U3+GVKDADfgApZ-42SYNiig8dTnFA@mail.gmail.com>
To: John Naylor <johncnaylorls@gmail.com>
Archived-At: 
 <https://www.postgresql.org/message-id/DDA507E1-56DB-4D76-8B81-41660ED932B9%40gmail.com>
Precedence: bulk


> On Oct 29, 2025, at 14:28, John Naylor <johncnaylorls@gmail.com> =
wrote:
>=20
> I suspect the challenge
> will be multikey sorts when the first key has low cardinality.

As you predicted, when the first key has very low cardinality, radix is =
a little bit slower. I built a test that proves that:

```
evantest=3D# drop table if exists test_multi;
evantest=3D# create unlogged table test_multi (category int, name text);
=E2=80=94 first column has only 4 distinct values
evantest=3D# insert into test_multi select (random() * 4)::int as =
category, md5(random()::text) || md5(random()::text) as name from =
generate_series(1, 1000000);
evantest=3D# vacuum freeze test_multi;
evantest=3D# select count(*) from test_multi;
evantest=3D# set work_mem =3D '64MB=E2=80=99;

evantest-# \timing on
Timing is on.
evantest=3D# set wip_radix_sort =3D 'off';
Time: 0.403 ms
evantest=3D# \o /dev/null
evantest=3D# select * from test_multi order by category, name;
Time: 5607.336 ms (00:05.607)
evantest=3D# select * from test_multi order by category, name;
Time: 5703.555 ms (00:05.704)
evantest=3D# select * from test_multi order by category, name;
Time: 5692.644 ms (00:05.693)

evantest=3D# set wip_radix_sort =3D 'on';
Time: 0.859 ms
evantest=3D# select * from test_multi order by category, name;
Time: 5822.979 ms (00:05.823)
evantest=3D# select * from test_multi order by category, name;
Time: 5881.256 ms (00:05.881)
evantest=3D# select * from test_multi order by category, name;
Time: 5976.351 ms (00:05.976)
```

Roughly 5% slower for this corner case.

However, when I recreate the test table with high cardinality first =
column, wip_radix_sort seems still slower:

```
evantest=3D# \o
evantest=3D# drop table if exists test_multi;
DROP TABLE
evantest=3D# create unlogged table test_multi (category int, name text);
CREATE TABLE
evantest=3D# insert into test_multi
evantest-# select (random() * 1000000)::int as category,  =
md5(random()::text) || md5(random()::text) as name from =
generate_series(1, 1000000);
INSERT 0 1000000
evantest=3D# vacuum freeze test_multi;
VACUUM
evantest=3D# select count(*) from test_multi;
  count
---------
 1000000
(1 row)

evantest=3D# select * from test_multi limit 5;
 category |                               name
=
----------+---------------------------------------------------------------=
---
   607050 | =
c555126a5afea9f5ffe3880248c89944d211bc378f8c3b6d125b4360fe8619b7
   843579 | =
69b5a1dba76f52ff238566a3f88315a7425116d5d271fb54701b6e49d4afd8ce
   106298 | =
a96e8674db219e12463ecdbb405b99c631767972e489093045c97976c17c6561
   621860 | =
5e6739ea9f533f9cdb0b8db76e3d4ce63be6b2b612c8aff06c4b80451f8f2edc
   290110 | =
56944320e5abd3a854fffdd185b969727e8d414448d440725a392cda4c6355c4
(5 rows)

evantest=3D# \timing on
Timing is on.

evantest=3D# \o /dev/null
evantest=3D# set wip_radix_sort =3D 'off';
Time: 0.904 ms
evantest=3D# select * from test_multi limit 5;
Time: 0.983 ms
evantest=3D# select * from test_multi order by category, name;
Time: 593.578 ms
evantest=3D# select * from test_multi order by category, name;
Time: 597.329 ms
evantest=3D# select * from test_multi order by category, name;
Time: 600.050 ms

evantest=3D# set wip_radix_sort =3D 'on';
Time: 0.737 ms
evantest=3D# select * from test_multi order by category, name;
Time: 611.604 ms
evantest=3D# select * from test_multi order by category, name;
Time: 613.115 ms
evantest=3D# select * from test_multi order by category, name;
Time: 615.003 ms
```

This seems like a real regression.

Then I tried to only sort on the first column, yes, now radix is faster:

```
evantest=3D# set wip_radix_sort =3D 'off=E2=80=99;
evantest=3D# select * from test_multi order by category;
Time: 445.498 ms
evantest=3D# select * from test_multi order by category;
Time: 451.834 ms
evantest=3D# select * from test_multi order by category;
Time: 454.531 ms

evantest=3D# set wip_radix_sort =3D 'on';
Time: 0.329 ms
evantest=3D# select * from test_multi order by category;
Time: 402.829 ms
evantest=3D# select * from test_multi order by category;
Time: 408.014 ms
evantest=3D# select * from test_multi order by category;
Time: 415.340 ms
evantest=3D# select * from test_multi order by category;
Time: 413.969 ms
```

Hope the test helps. (The test was run a MacBook M4. )

Best regards,
--
Chao Li (Evan)
HighGo Software Co., Ltd.
https://www.highgo.com/