[FEA] Implement argument-order stable option for `cudf::merge::merge`
- 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.**
In implementing the cudf-polars interpreter, I would like to use `cudf::merge::merge` to implement the polars `merge_sorted` functionality. Where polars guarantees that for equal keys in the left and right dataframes, `merge_sorted` is stable (that is, equal keys, and hence carrier columns, from the left dataframe appear in the result before those in the right frame), libcudf makes no such guarantee. Note that this is only a binary merge.
`cudf::merge::merge` is n-ary, rather than binary, and uses a priority queue, based on the length of the input (and intermediate) dataframes that are produced. Hence, we can't guarantee that the result is stable wrt the original input (in the sense described above) without some gymnastics.
**Describe the solution you'd like**
I'd like a stable version of `merge` for the binary case. In this case there's no real advantage to be gained by picking the smaller dataframe as the left one (because there's only one round of merges), and so the implementation is cheap.
For stable n-ary merge, I think there's no way around adding an additional disambiguating key column to each table that becomes part of the comparator.
**Describe alternatives you've considered**
Always adding the disambiguating key column.
Contributor guide
Assessment
This issue has not been assessed yet.