the join implementation in futhark/join.fut does redudant sorting.
Ideally we would sort once when we combine the tables. In this implementation we would simply need to first sort by the column value being merged on and than by table.
Currently we use partition in the generate_pair function. This would not be neccesary if the lists were pre sorted. However this extra work may be insignificant. (need to test this).
the join implementation in futhark/join.fut does redudant sorting.
Ideally we would sort once when we combine the tables. In this implementation we would simply need to first sort by the column value being merged on and than by table.
Currently we use partition in the generate_pair function. This would not be neccesary if the lists were pre sorted. However this extra work may be insignificant. (need to test this).