[FEA] have cudf::merge or similar API be stable, with the order of the tables passed in
- 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.**
Spark's sort is a stable sort. Most of the time that does not mater much, but there are a few cases where it does make a difference in the output (some window functions in a single process).
`cudf::merge` currently provides no way to ensure that if batch 1 came before batch 2 in read order that the output would be preserved.
**Describe the solution you'd like**
It would be great in the case of ties in cudf::merge if the order of the rows could match the order of the tables passed in. If this is going to cause a performance difference with the existing merge then a separate API is fine too.
**Describe alternatives you've considered**
Add in a separate row of longs with all of the data that is a sequence to get a total ordering of the data read in so I can then use it as the final key in the sort, but that adds a lot of extra memory for something that is a really rare use case.
**Additional context**
This is not super critical, as I said it is for a few corner cases. But from looking at the code it looks like it is simple enough that I could do it. The underlying `trust::merge` says that it is stable for what we want in the docs. That just leaves the order in which the tables are merged. It looks like right now there is a priority queue used to try and reduce the amount of data transferred and merges done by merging the two smallest tables at a time. I think if we instead merged them in waves, we could still reduce the amount of intermediate data transferred and maintain stable ordering. Not as clean as the existing code but the following pseudo code would probably do what we want.
```
queue input(all the input tables)
queue output()
while (input.size > 1) {
while (input.size > 1) {
left = input.pop
right = input.pop
output.add(merge(left, right))
}
if (input.size == 1) {
output.add(input.pop)
}
input = output
output.reset()
}
return input.pop
```
Contributor guide
Assessment
This issue has not been assessed yet.