[FEA]Add merge_asof to cudf

[xhkong]

Please add merge_asof to cudf to match pandas merge_asof capabilities. Thanks!

[kkraus14]

For reference: https://pandas.pydata.org/pandas-docs/stable/reference/api/pandas.merge_asof.html

I can only see this working with a sort based join FYI.

[beckernick]

@vyasr might the recent conditional join / AST work perhaps be relevant for this issue? Copying the summary from the pandas docs linked above.

Perform an asof merge.

This is similar to a left-join except that we match on nearest key rather than equal keys. Both DataFrames must be sorted by the key.

For each row in the left DataFrame:

• A “backward” search selects the last row in the right DataFrame whose ‘on’ key is less than or equal to the left’s key.
• A “forward” search selects the first row in the right DataFrame whose ‘on’ key is greater than or equal to the left’s key.
• A “nearest” search selects the row in the right DataFrame whose ‘on’ key is closest in absolute distance to the left’s key.

The default is “backward” and is compatible in versions below 0.20.0. The direction parameter was added in version 0.20.0 and introduces “forward” and “nearest”.

Optionally match on equivalent keys with ‘by’ before searching with ‘on’.

[jrhemstad]

This could not be implemented with the AST as it requires storing state (i.e., the "closest so far" value). I'm not sure how you would implement this in a way that is not terrible.

[vyasr]

The kernel computing conditional joins currently uses a 1D grid to parallelize only over the rows of the left table. We probably want to retain the flexibility to change the grid layout in the future if we find a more performant approach for conditional joins, but a slightly modified version of the current kernel that stores the "closest so far" value in a kernel-local variable should work for this use case, right? Note that the pandas API specifically requires that both DataFrames are sorted to begin with. I'm imagining something like the following (in very rough pseudocode):

join_index = SENTINEL
finished = false
for row in right:
    if not finished and condition(row):
        join_index = index(row)
    else:
        finished = true

if join_index == SENTINEL:
    handle_no_join()
else:
    add_pair_to_cache(left_row, join_index)

with condition = ast_operator::GREATER for backwards and condition = ast_operator::LESS for forwards. nearest would require a little extra logic using ast_operator::GREATER but then doing a comparison of two values the first time the condition is False.

[GregoryKimball]

Quick update: my interest in this issue has grown since I started researching sort-based join algorithms such as the "inequality_join" in DuckDB, "asof join" in polars, and "merge_asof" in pandas.