From: Chao Li <li.evan.chao@gmail.com>
Message-Id: <606C775A-4C1A-482B-BE7D-2E7A46AE14B9@gmail.com>
Content-Type: multipart/mixed;
	boundary="Apple-Mail=_A7A6D6D3-1EAE-40E7-AD01-5BBEC88DC6FC"
Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3826.700.81\))
Subject: Re: tuple radix sort
Date: Wed, 3 Dec 2025 16:22:13 +0800
In-Reply-To: 
 <CANWCAZaKRzsYPn9YWRR8g5dkX-ep_jgyUb4r3KFekK5ZTNo7ew@mail.gmail.com>
Cc: Chengpeng Yan <chengpeng_yan@outlook.com>,
 "pgsql-hackers@lists.postgresql.org" <pgsql-hackers@lists.postgresql.org>,
 Peter Geoghegan <pg@bowt.ie>
To: John Naylor <johncnaylorls@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>
 <F7935986-4E3D-477C-B45C-878420B45C0D@gmail.com>
 <CANWCAZaKRzsYPn9YWRR8g5dkX-ep_jgyUb4r3KFekK5ZTNo7ew@mail.gmail.com>
Archived-At: 
 <https://www.postgresql.org/message-id/606C775A-4C1A-482B-BE7D-2E7A46AE14B9%40gmail.com>
Precedence: bulk


--Apple-Mail=_A7A6D6D3-1EAE-40E7-AD01-5BBEC88DC6FC
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=utf-8

Hi John,

I played with this again today and found an optimization that seems to =
dramatically improve the performance:

```
+static void
+radix_sort_tuple(SortTuple *begin, size_t n_elems, int level, =
Tuplesortstate *state)
+{
+	RadixPartitionInfo partitions[256] =3D {0};
+	uint8_t		remaining_partitions[256] =3D {0};
```

Here partitions and remaining_partitions are just temporary buffers, =
allocating memory from stack and initialize them seems slow. By passing =
them as function parameters are much faster. See attached diff for my =
change.

V5 patch: by the way, v5 is very faster than v1.
```
evantest=3D# select * from test_multi order by category, name;
Time: 299.912 ms
evantest=3D# select * from test_multi order by category, name;
Time: 298.793 ms
evantest=3D# select * from test_multi order by category, name;
Time: 300.306 ms
evantest=3D# select * from test_multi order by category, name;
Time: 302.140 ms
```

v5 + my change:
```
evantest=3D# select * from test_multi order by category, name;
Time: 152.572 ms
evantest=3D# select * from test_multi order by category, name;
Time: 143.296 ms
evantest=3D# select * from test_multi order by category, name;
Time: 151.606 ms
```

The test I did today is just the high cardinality first column test I =
had done before:
```
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;
\timing on
\o /dev/null
set wip_radix_sort =3D =E2=80=98on;
set work_mem =3D =E2=80=982GB=E2=80=99;
select * from test_multi order by category, name;
```

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


--Apple-Mail=_A7A6D6D3-1EAE-40E7-AD01-5BBEC88DC6FC
Content-Disposition: attachment;
	filename=tuplesort_chaoli.diff
Content-Type: application/octet-stream;
	x-unix-mode=0644;
	name="tuplesort_chaoli.diff"
Content-Transfer-Encoding: 7bit

diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
index 028c5b71c27..2bf2785f5ec 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -2760,10 +2760,11 @@ normalize_datum(Datum orig, SortSupport ssup)
  * DEALINGS IN THE SOFTWARE.
  */
 static void
-radix_sort_tuple(SortTuple *begin, size_t n_elems, int level, Tuplesortstate *state)
+radix_sort_tuple(SortTuple *begin, size_t n_elems, int level, Tuplesortstate *state,
+				 RadixPartitionInfo * partitions, uint8_t *remaining_partitions)
 {
-	RadixPartitionInfo partitions[256] = {0};
-	uint8_t		remaining_partitions[256] = {0};
+	/* RadixPartitionInfo partitions[256] = {0}; */
+	/* uint8_t		remaining_partitions[256] = {0}; */
 	size_t		total = 0;
 	int			num_partitions = 0;
 	int			num_remaining;
@@ -2771,6 +2772,9 @@ radix_sort_tuple(SortTuple *begin, size_t n_elems, int level, Tuplesortstate *st
 	size_t		start_offset = 0;
 	SortTuple  *partition_begin = begin;
 
+	memset(partitions, 0, sizeof(RadixPartitionInfo) * 256);
+	memset(remaining_partitions, 0, sizeof(uint8_t) * 256);
+
 	/* count number of occurrences of each byte */
 	for (SortTuple *tup = begin; tup < begin + n_elems; tup++)
 	{
@@ -2881,7 +2885,9 @@ radix_sort_tuple(SortTuple *begin, size_t n_elems, int level, Tuplesortstate *st
 					radix_sort_tuple(partition_begin,
 									 num_elements,
 									 level + 1,
-									 state);
+									 state,
+									 partitions,
+									 remaining_partitions);
 				}
 			}
 			else if (state->base.onlyKey == NULL)
@@ -3019,10 +3025,15 @@ sort_byvalue_datum(Tuplesortstate *state)
 		}
 		else
 		{
+			RadixPartitionInfo partitions[256];
+			uint8_t		remaining_partitions[256];
+
 			radix_sort_tuple(not_null_start,
 							 not_null_count,
 							 0,
-							 state);
+							 state,
+							 partitions,
+							 remaining_partitions);
 		}
 	}
 }

--Apple-Mail=_A7A6D6D3-1EAE-40E7-AD01-5BBEC88DC6FC
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=us-ascii


--Apple-Mail=_A7A6D6D3-1EAE-40E7-AD01-5BBEC88DC6FC--