Skip common prefixes during radix sort
John Naylor <john.naylor@postgresql.org>
Author:
John Naylor <john.naylor@postgresql.org>
Date: 2026-04-01T07:18:57Z
Releases:
19 (unreleased)
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
Files
| Path | Change | +/− |
|---|---|---|
| src/backend/utils/sort/tuplesort.c | modified | +40 −4 |
Discussion
- tuple radix sort 47 messages · 2025-10-29 → 2026-04-29