sort-merge join #4538
Description
We are now using binary search algorithm when doing join/merge of two tables.
Despite binary search merge (call it bmerge) is a single threaded implementation now, as of now it is still 4 times faster than the next fastest solution, on a 5GB, 1e8 rows data (not taking GPU into account).
I am proposing to have an alternative join algorithm, sort-merge join (call it smerge), that could be used if tables are already sorted by join keys. In sort-merge join, sorting join keys is the most expensive part.
After looking at the timings in #4539 it make sense to use smerge instead of bmerge in many other cases, not just when tables are sorted. Although making bmerge parallel would reduce this timings differences, at least up to currently supported int32 row limit, #3957. I assume sort-merge join to scale little better. In the end it makes a linear scan over sorted integers, so the bigger the data (and chunk sizes), the better utilization of threads.