MIME-Version: 1.0
References: 
 <CANWCAZYzx7a7E9AY16Jt_U3+GVKDADfgApZ-42SYNiig8dTnFA@mail.gmail.com>
 <DDA507E1-56DB-4D76-8B81-41660ED932B9@gmail.com>
In-Reply-To: <DDA507E1-56DB-4D76-8B81-41660ED932B9@gmail.com>
From: John Naylor <johncnaylorls@gmail.com>
Date: Wed, 29 Oct 2025 18:29:35 +0700
Message-ID: 
 <CANWCAZYUsV1no_JejqD6na-6adj6e2SD2-aQEWzRgV=LtpsR5g@mail.gmail.com>
Subject: Re: tuple radix sort
To: Chao Li <li.evan.chao@gmail.com>
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>,
 Peter Geoghegan <pg@bowt.ie>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: 
 <https://www.postgresql.org/message-id/CANWCAZYUsV1no_JejqD6na-6adj6e2SD2-aQEWzRgV%3DLtpsR5g%40mail.gmail.com>
Precedence: bulk

On Wed, Oct 29, 2025 at 3:25=E2=80=AFPM Chao Li <li.evan.chao@gmail.com> wr=
ote:
> > On Oct 29, 2025, at 14:28, John Naylor <johncnaylorls@gmail.com> wrote:
> >
> > 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

Thanks for testing. Note it's actually 5 because of rounding. 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'm also not thrilled about having to
remove your psql prompt.

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;

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. I
don't know if that explains the disparity, but I've made that change
for my quick tests below.

> evantest=3D# \o /dev/null
> evantest=3D# select * from test_multi order by category, name;
[...]
> Roughly 5% slower for this corner case.

Seems fine for me on this old Intel laptop (min of 5 runs):

set wip_radix_sort =3D 'off';
2368.369

set wip_radix_sort =3D 'on';
2290.654

It's close enough that I'll want to test more closely at a range of
low-cardinality inputs. I haven't done any rigorous scripted testing
yet, so take this with a grain of salt.

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

drop table if exists test_multi;
create unlogged table test_multi (category int, name text);
insert into test_multi select (random() * 1000000)::int as category,
md5(random()::text) || md5(random()::text) as name from
generate_series(1, 1000000);
vacuum freeze test_multi;

> evantest=3D# set wip_radix_sort =3D 'off';
> Time: 0.904 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.

It's better for me here (min of 5 again), although the time scanning
the table probably dominates:

off:
536.257

on:
471.345

--
John Naylor
Amazon Web Services