Re: tuple radix sort

From: Chao Li <li(dot)evan(dot)chao(at)gmail(dot)com>
To: John Naylor <johncnaylorls(at)gmail(dot)com>
Cc: Chengpeng Yan <chengpeng_yan(at)outlook(dot)com>, "pgsql-hackers(at)lists(dot)postgresql(dot)org" <pgsql-hackers(at)lists(dot)postgresql(dot)org>, Peter Geoghegan <pg(at)bowt(dot)ie>
Subject: Re: tuple radix sort
Date: 2025-12-03 08:22:13
Message-ID: 606C775A-4C1A-482B-BE7D-2E7A46AE14B9@gmail.com
Views: Whole Thread | Raw Message | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

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] = {0};
+ uint8_t remaining_partitions[256] = {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=# select * from test_multi order by category, name;
Time: 299.912 ms
evantest=# select * from test_multi order by category, name;
Time: 298.793 ms
evantest=# select * from test_multi order by category, name;
Time: 300.306 ms
evantest=# select * from test_multi order by category, name;
Time: 302.140 ms
```

v5 + my change:
```
evantest=# select * from test_multi order by category, name;
Time: 152.572 ms
evantest=# select * from test_multi order by category, name;
Time: 143.296 ms
evantest=# 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 = ‘on;
set work_mem = ‘2GB’;
select * from test_multi order by category, name;
```

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

Attachment Content-Type Size
tuplesort_chaoli.diff application/octet-stream 1.9 KB
unknown_filename text/plain 4 bytes

In response to

Browse pgsql-hackers by date

  From Date Subject
Previous Message Bertrand Drouvot 2025-12-03 08:14:41 Re: Remove useless pointer advance in StatsShmemInit()