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>
In-Reply-To: <F7935986-4E3D-477C-B45C-878420B45C0D@gmail.com>
From: John Naylor <johncnaylorls@gmail.com>
Date: Thu, 27 Nov 2025 18:45:32 +0700
Message-ID: 
 <CANWCAZaKRzsYPn9YWRR8g5dkX-ep_jgyUb4r3KFekK5ZTNo7ew@mail.gmail.com>
Subject: Re: tuple radix sort
To: Chao Li <li.evan.chao@gmail.com>
Cc: Chengpeng Yan <chengpeng_yan@outlook.com>,
	"pgsql-hackers@lists.postgresql.org" <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/CANWCAZaKRzsYPn9YWRR8g5dkX-ep_jgyUb4r3KFekK5ZTNo7ew%40mail.gmail.com>
Precedence: bulk

On Thu, Nov 27, 2025 at 2:49=E2=80=AFPM Chao Li <li.evan.chao@gmail.com> wr=
ote:
> I did an initial test before, but I didn=E2=80=99t read the code at the t=
ime. Today, I spent time reviewing 0001. Overall, I believe the implementat=
ion is solid. I just got a few comments/suggestions.

Thanks for looking!

> > On Nov 26, 2025, at 21:11, John Naylor <johncnaylorls@gmail.com> wrote:

> > <v5-0001-Use-radix-sort-when-SortTuple-contains-a-pass-by-.patch><v5-00=
04-Detect-common-prefix-to-avoid-wasted-work-during-.patch><v5-0003-WIP-mak=
e-some-regression-tests-sort-order-more-de.patch><v5-0002-WIP-Adjust-regres=
sion-tests.patch>

> We recompute normalize_datum(tup->datum1, ssup) for every tuple in every =
level, why don=E2=80=99t cache the result in SortTuple. As we have cached c=
urrent_byte in SortTuple, it shouldn=E2=80=99t be a big deal to add one mor=
e field to it.

Actually it is a big deal, because the memtuples array counts against work_=
mem.

I saw two ways to store the full normalized without increasing the
size, and I've already rejected them:
- share space with isnull1/srctape -- v3 did this, and I already
explained the reason for changing when I shared v4.
- share space with datum1 -- that would require additional code to
restore the original datum and makes it more difficult to verify
correctness

There is also a proposal upthread to not store anything, and that's
still up in the air.

> 2 - 0001
> ```
> +       while (num_remaining > 1)
> +       {
> +               /* start the count over */
> +               num_remaining =3D num_partitions;
> ```
>
> The swap loop always start the count over, so that sorted partitions are =
re-scanned as well. I think we can do an optimization like:
>
> ```
> num_active =3D num_partitions;
> while (num_active > 1)
> {
>     for (int i =3D 0; i < num_active; )
>     {
>         uint8 idx =3D remaining_partitions[i];
>         // do the swaps for the partition =E2=80=A6
>
>         if (partitions[idx].offset =3D=3D partitions[idx].next_offset)
>         {
>             remaining_partitions[i] =3D remaining_partitions[num_active -=
 1];
>             num_active--;
>         }
>         else
>             i++;
>     }
> }
> ```
>
> This way we move out sorted partitions, so they will not be re-scanned.

I don't think that's going to work without additional bookkeeping, so
I'm not sure it's worth it. See the recursion step.

> 3 - 0001
>
> In sort_byvalue_datum, we can add a fast-path for all NULL and all NOT NU=
LL cases, so that they won=E2=80=99t need to run the branchless cyclic perm=
utation and the two =E2=80=9Cfor=E2=80=9D loops of assertions. Something li=
ke:

This is too clever and yet doesn't go far enough.

There is already one fast path, which happens to cover the common ASC
+ all NOT NULL case. The right way to skip the permutation step would
be to add a second loop that starts from the end and stops at the
first tuple that needs to swap. That should work not just for all NULL
and all NOT NULL, but also where there is a mix of the two and some
(or all) are already in place. All these cases can be treated the same
and they will continue to the exact same paths.

I haven't yet bothered to try harder, but it may be necessary in order
to avoid introducing regressions, so I'll look into it.

--
John Naylor
Amazon Web Services