[FEA] Sort-merge join: Improve pre-processed table class design and merge implementation
- Dominant language
- C++
- Stars
- 9.8k
- Forks
- 1.1k
- Avg merge
- 3d 6m
- Merged PRs (30d)
- 278
Description
**Is your feature request related to a problem? Please describe.**
1. Row iterators for pre-processed table: The order in which the pre-processed table is iterated depends on whether it is pre-sorted or not. That is, for pre-sorted input tables, we can directly pass counting iterators to go over the table. If we need to sort the table, then we have to pass iterators to the ordering column returned by `cudf::sorted_order()`. Instead of having four if-conditions in `sort_merge_join::inner_join()`, a more elegant solution would be to have `preprocessed_table` struct have `begin` and `end` functions that return the appropriate iterator depending on the value of `std::optional sorted_order`. For example:
```cpp
template
class preprocessed_table {
It1 s1;
It2 s2;
auto begin() const {
if constexpr(b)
return s1;
return s2;
}
};
```
2. Merge implementation: The parallel merge algorithm has several thrust calls which results in multiple passes over the pre-processed tables. We can reduce the number of passes, as well as the thrust kernel launch overhead with kernel fusion. For instance, we have three thrust calls (lower bound + inclusive scan + transform) to populate the smaller indices array which can be fused into a single kernel.
Contributor guide
Assessment
This issue has not been assessed yet.