pgsql: Skip common prefixes during radix sort

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(at)outlook(dot)com>
Reviewed-by: ChangAo Chen <cca5507(at)qq(dot)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(-)