Perform radix sort on SortTuples with pass-by-value Datums Radix sort can be much faster than quicksort, but for our purposes it is limited to sequences of unsigned bytes. To make tuples with other types amenable to this technique, several features of tuple comparison must be accounted for, i.e. the sort key must be "normalized":
1. Signedness -- It's possible to modify a signed integer such that it can be compared as unsigned. For example, a signed char has range -128 to 127. If we cast that to unsigned char and add 128, the range of values becomes 0 to 255 while preserving order. 2. Direction -- SQL allows specification of ASC or DESC. The descending case is easily handled by taking the complement of the unsigned representation. 3. NULL values -- NULLS FIRST and NULLS LAST must work correctly. This commmit only handles the case where datum1 is pass-by-value Datum (possibly abbreviated) that compares like an ordinary integer. (Abbreviations of values of type "numeric" are a convenient counterexample.) First, tuples are partitioned by nullness in the correct NULL ordering. Then the NOT NULL tuples are sorted with radix sort on datum1. For tiebreaks on subsequent sortkeys (including the first sort key if abbreviated), we divert to the usual qsort. ORDER BY queries on pre-warmed buffers are up to 2x faster on high cardinality inputs with radix sort than the sort specializations added by commit 697492434, so get rid of them. It's sufficient to fall back to qsort_tuple() for small arrays. Moderately low cardinality inputs show more modest improvents. Our qsort is strongly optimized for very low cardinality inputs, but radix sort is usually equal or very close in those cases. The changes to the regression tests are caused by under-specified sort orders, e.g. "SELECT a, b from mytable order by a;". For unstable sorts, such as our qsort and this in-place radix sort, there is no guarantee of the order of "b" within each group of "a". The implementation is taken from ska_byte_sort() (Boost licensed), which is similar to American flag sort (an in-place radix sort) with modifications to make it better suited for modern pipelined CPUs. The technique of normalization described above can also be extended to the case of multiple keys. That is left for future work (Thanks to Peter Geoghegan for the suggestion to look into this area). Reviewed-by: Chengpeng Yan <[email protected]> Reviewed-by: zengman <[email protected]> Reviewed-by: ChangAo Chen <[email protected]> Reviewed-by: Álvaro Herrera <[email protected]> Reviewed-by: Chao Li <[email protected]> (earlier version) Discussion: https://postgr.es/m/canwcazyzx7a7e9ay16jt_u3+gvkdadfgapz-42syniig8dt...@mail.gmail.com Branch ------ master Details ------- https://git.postgresql.org/pg/commitdiff/ef3c3cf6d021ff9884c513afd850a9fe85cad736 Modified Files -------------- src/backend/utils/sort/tuplesort.c | 561 ++++++++++++++++++++++++-------- src/include/utils/sortsupport.h | 101 ------ src/include/utils/tuplesort.h | 1 + src/test/regress/expected/tuplesort.out | 6 +- src/tools/pgindent/typedefs.list | 1 + 5 files changed, 430 insertions(+), 240 deletions(-)
