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: 
 <CANWCAZYUsV1no_JejqD6na-6adj6e2SD2-aQEWzRgV=LtpsR5g@mail.gmail.com>
Date: Thu, 30 Oct 2025 09:56:06 +0800
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>,
 Peter Geoghegan <pg@bowt.ie>
Content-Transfer-Encoding: quoted-printable
Message-Id: <72B9451B-0121-491E-A702-BE8AAEFDB80E@gmail.com>
References: 
 <CANWCAZYzx7a7E9AY16Jt_U3+GVKDADfgApZ-42SYNiig8dTnFA@mail.gmail.com>
 <DDA507E1-56DB-4D76-8B81-41660ED932B9@gmail.com>
 <CANWCAZYUsV1no_JejqD6na-6adj6e2SD2-aQEWzRgV=LtpsR5g@mail.gmail.com>
To: John Naylor <johncnaylorls@gmail.com>
Archived-At: 
 <https://www.postgresql.org/message-id/72B9451B-0121-491E-A702-BE8AAEFDB80E%40gmail.com>
Precedence: bulk


> On Oct 29, 2025, at 19:29, John Naylor <johncnaylorls@gmail.com> =
wrote:
>=20
> On Wed, Oct 29, 2025 at 3:25=E2=80=AFPM Chao Li =
<li.evan.chao@gmail.com> wrote:
>>> 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.
>>=20
>> As you predicted, when the first key has very low cardinality, radix =
is a little bit slower. I built a test that proves that:
>>=20
>> ```
>> 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
>=20
> Thanks for testing. Note it's actually 5 because of rounding.

Yes, 0-4, totally 5.

> Your
> text also seems to have em-dashes and unicode apostrophes where it
> should have dashes / single quotes. That's not great if you expect
> others to try to reproduce.

I just copied the content from psql (running in iTerm). I did a Google =
search, and found that was because of Mac Mail=E2=80=99s =E2=80=9Csmart =
quotes=E2=80=9D substitution. Looks like even I manually type in a pair =
of single quotes, it still does the substitution. I will try to see how =
to disable that, but I don=E2=80=99t want to switch to another mail app.

> I'm also not thrilled about having to
> remove your psql prompt.
>=20

I just wanted to show my entire test process, so I simply copied all =
contents from psql. In future, I will remove psql prompts from reproduce =
procedure.

> drop table if exists test_multi;
> create unlogged table test_multi (category int, name text);
> insert into test_multi select (random() * 4)::int as category,
> md5(random()::text) || md5(random()::text) as name from
> generate_series(1, 1000000);
> vacuum freeze test_multi;
>=20
> Anyway, because this table is larger than my first example, the input
> no longer fits into 64MB of work_mem and it switches to an external
> merge sort. Normally I set work_mem to 1GB for testing sorts so I
> don't have to think about it, but neglected to in my first email.=20

I changed work_men to 1GB and reran the test. As the high cardinality =
data are still there, so I first reran with data:

```
evantest=3D# set work_mem =3D '1GB';
Time: 0.301 ms
evantest=3D#
evantest=3D# select * from test_multi order by category, name;
Time: 575.247 ms
evantest=3D# select * from test_multi order by category, name;
Time: 554.351 ms
evantest=3D# select * from test_multi order by category, name;
Time: 565.100 ms
evantest=3D#
evantest=3D# set wip_radix_sort =3D 'on';
Time: 0.752 ms
evantest=3D# select * from test_multi order by category, name;
Time: 558.057 ms
evantest=3D# select * from test_multi order by category, name;
Time: 565.542 ms
evantest=3D# select * from test_multi order by category, name;
Time: 559.973 ms
```

With radix_sort on and off, execution time are almost the same.

Then I restore the data to low cardinality, off is still faster than on:
```
evantest=3D# set wip_radix_sort =3D =E2=80=98off';
Time: 0.549 ms
evantest=3D# select * from test_multi order by category, name;
Time: 5509.075 ms (00:05.509)
evantest=3D# select * from test_multi order by category, name;
Time: 5553.566 ms (00:05.554)
evantest=3D# select * from test_multi order by category, name;
Time: 5598.595 ms (00:05.599)
evantest=3D# set wip_radix_sort =3D =E2=80=98on';
Time: 0.786 ms
evantest=3D#
evantest=3D# select * from test_multi order by category, name;
Time: 5770.964 ms (00:05.771)
evantest=3D# select * from test_multi order by category, name;
Time: 5779.755 ms (00:05.780)
evantest=3D# select * from test_multi order by category, name;
Time: 5851.134 ms (00:05.851)
evantest=3D#
evantest=3D# set work_mem =3D '2GB=E2=80=99; # increasing work_mem to =
2GB doesn=E2=80=99t help
Time: 0.404 ms
evantest=3D#
evantest=3D# select * from test_multi order by category, name;
Time: 5781.005 ms (00:05.781)
evantest=3D# select * from test_multi order by category, name;
Time: 5826.025 ms (00:05.826)
evantest=3D# select * from test_multi order by category, name;
Time: 5937.919 ms (00:05.938)
```

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