Damn it, now we're going to have to make hashing faster
Conversation
Replying to
hash_mem_multiplier's default was increased to 2.0 in 15, so that's something! Though it's equally relevant to hashing and sorting.
1
Maybe the cost model of sorting should be adjusted now that it has become more efficient. The constant factor should depend on the sort input type (compare cost) and row size (swap cost).
1
That's probably a good idea. IIRC the other problem with cost_sort() is that the CPU cost of external sorts is too pessimistic.
1
Agreed. Btw, regarding sort templating and specialisations: Why not try radix sort for integers or even for strings. One could even take into account the column statistics to choose between quicksort and radix sort and use a costing model behind that. What‘s your opinion on that?
1
The difficulty often comes from real world data having lots of variability. The worst case matters a lot. Alphasort paper uses a car analogy for this: "street-legal versus formula one". The fastest cars cannot be driven on public roads. That might be relevant to radix sort ideas.
1
Now that SSE2 intrinsics are available, would it maybe make sense to integrate a vectorization path in the sort_template.h code along the lines of this? arxiv.org/pdf/2205.05982
2
1
My early concern about "street legal sort" apply. The paper's authors make clear that they focussed on "non-tuple keys". Whereas Postgres sorts tuples with nullable columns using user-defined extensible comparators.
1
I could be wrong, of course. If I am wrong then the details are likely to be interesting. Maybe somebody can replace the SortTuple struct with something amenable to vectorization, but still just as flexible. Domain-specific (rel database) techniques often play a big role here.
I was thinking about non-tuple sort or single datum tuple sort that could benefit. One idea for general tuple sort could be to optimize that by extracting out the sort key from the whole tuple and putting it into a dense array with an offset into the tuplestore appended /1
2
1
that dense sort would better utilize the CPU cache and could be SIMD more easily. With many tables using surrogate keys sort-merge joins or index builds could benefit greatly. To save on memory one could limit this to the insertion sort and vectorize only that code path. /2