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: 
 <CANWCAZZiMGj6QuHfyBPv9at7xn23NPAz4nit=G6fr26V+h8MKg@mail.gmail.com>
Date: Thu, 27 Nov 2025 15:48:58 +0800
Cc: Chengpeng Yan <chengpeng_yan@outlook.com>,
 "pgsql-hackers@lists.postgresql.org" <pgsql-hackers@lists.postgresql.org>,
 Peter Geoghegan <pg@bowt.ie>
Content-Transfer-Encoding: quoted-printable
Message-Id: <F7935986-4E3D-477C-B45C-878420B45C0D@gmail.com>
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>
To: John Naylor <johncnaylorls@gmail.com>
Archived-At: 
 <https://www.postgresql.org/message-id/F7935986-4E3D-477C-B45C-878420B45C0D%40gmail.com>
Precedence: bulk

Hi John,

I did an initial test before, but I didn=E2=80=99t read the code at the =
time. Today, I spent time reviewing 0001. Overall, I believe the =
implementation is solid. I just got a few comments/suggestions.

> On Nov 26, 2025, at 21:11, John Naylor <johncnaylorls@gmail.com> =
wrote:
>=20
>=20
> For v5 I've also added CHECK_FOR_INTERRUPTS and rewrote some comments.
>=20
>=20
> --
> John Naylor
> Amazon Web Services
> =
<v5-0001-Use-radix-sort-when-SortTuple-contains-a-pass-by-.patch><v5-0004-=
Detect-common-prefix-to-avoid-wasted-work-during-.patch><v5-0003-WIP-make-=
some-regression-tests-sort-order-more-de.patch><v5-0002-WIP-Adjust-regress=
ion-tests.patch>


1 - 0001
```
+		/* extract the byte for this level from the normalized =
datum */
+		current_byte =3D =
extract_byte(normalize_datum(tup->datum1, ssup),
+									=
level);
+
+		/* save it for the permutation step */
+		tup->current_byte =3D current_byte;
```

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 current_byte in SortTuple, it shouldn=E2=80=99t be a big deal to =
add one more field to it.

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.

3 - 0001

In sort_byvalue_datum, we can add a fast-path for all NULL and all NOT =
NULL cases, so that they won=E2=80=99t need to run the branchless cyclic =
permutation and the two =E2=80=9Cfor=E2=80=9D loops of assertions. =
Something like:

```
while (d1 < state->memtupcount && data[d1].isnull1 =3D=3D nulls_first)
    d1++;

null_count =3D d1;
not_null_count =3D state->memtupcount - d1;

/* fast paths: all on one side */
if (null_count =3D=3D 0 || not_null_count =3D=3D 0)
{
    if (nulls_first)
    {
        null_start =3D data;
        not_null_start =3D data + null_count;
    }
    else
    {
        not_null_start =3D data;
        null_start =3D data + not_null_count;
    }

    /* only one partition is non-empty; sort it and return */
    if (not_null_count > 1)
    {
        if (not_null_count < QSORT_THRESHOLD)
            qsort_tuple(not_null_start, not_null_count, =
state->base.comparetup, state);
        else
            radix_sort_tuple(not_null_start, not_null_count, 0, state);
    }
    else if (null_count > 1 && state->base.onlyKey =3D=3D NULL)
    {
        qsort_tuple(null_start, null_count, =
state->base.comparetup_tiebreak, state);
    }
    return;
}

/* ... existing branchless cyclic permutation ... */

```

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