From: John Naylor <john.naylor@postgresql.org>
To: pgsql-committers@lists.postgresql.org
Subject: pgsql: Skip common prefixes during radix sort
Date: Wed, 01 Apr 2026 07:19:16 +0000
Message-ID: <E1w7pr9-002QQU-2J@gemulon.postgresql.org> (raw)
Skip common prefixes during radix sort
During the counting step, keep track of the bits that are the same
for the entire input. If we counted only a single distinct byte,
the next recursion will start at the next byte position that has
more than one distinct byte in the input. This allows us to skip over
multiple passes where the byte is the same for the entire input.
This provides a significant speedup for integers that have some upper
bytes with all-zeros or all-ones, which is common.
Reviewed-by: Chengpeng Yan <chengpeng_yan@outlook.com>
Reviewed-by: ChangAo Chen <cca5507@qq.com>
Discussion: https://postgr.es/m/CANWCAZYpGMDSSwAa18fOxJGXaPzVdyPsWpOkfCX32DWh3Qznzw@mail.gmail.com
Branch
------
master
Details
-------
https://git.postgresql.org/pg/commitdiff/f6bd9f0fe25a3cea06e26204cc75cc6e954c4577
Modified Files
--------------
src/backend/utils/sort/tuplesort.c | 44 ++++++++++++++++++++++++++++++++++----
1 file changed, 40 insertions(+), 4 deletions(-)
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-committers@postgresql.org
Cc: john.naylor@postgresql.org, pgsql-committers@lists.postgresql.org
Subject: Re: pgsql: Skip common prefixes during radix sort
In-Reply-To: <E1w7pr9-002QQU-2J@gemulon.postgresql.org>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox