Feature request: asofjoin

[natemcintosh]

This is a request for an asof join type, as seen in pandas, kdb+, QuestDB, and probably a few others.

This is a rather niche join, but extremely useful for time series work. I think the pandas' description sums it up pretty well:

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’.

[bkamins]

OK - request noted. Let us wait for others to comment. Currently most of development is focused on other areas (performance), but we can get back to it in the future.

[skanskan]

Is it related with this ?
https://discourse.julialang.org/t/merge-dataframes-where-one-value-is-between-two-others/34738

[natemcintosh]

It is very similar, but I believe there is one key difference: the "right" dataframe only has one timestamp, not a start timestamp and an end timestamp.

A super simple example (without a groupby option) is

left = DataFrame(time=[1,5,10], left_val=["a","b","c"])
right = DataFrame(time=[1,2,3,6,7], right_val=[1,2,3,6,7])

# for each time in `left`, find the time (if any) in `right` that 
# is equal to or before it
right_inds = [searchsortedlast(right.time, t) for t in left.time]
# returns right_inds = [1,3,5]

# concatenate the dataframes
df = hcat(left, right[right_inds, :], makeunique=true)

The pandas version of this function also does forward and nearest selection, but backward selection is probably used most often

[junder873]

I agree this function would be very useful. It is definitely a niche to financial data, though I am sure some other fields use it. After asking that question and writing an initial function, I modified it to include a minimize component (which works for asof if the ranges are correct): https://gist.github.com/junder873/ae1ec240f2fd6d4cbdb2ec19bc2b5f9c

I am sure my code is sloppy, so I would love a more formal solution to these types of problems.

[robsmith11]

For reference, here are the kdb docs for asof and window joins:
https://code.kx.com/q/ref/aj/
https://code.kx.com/q/ref/wj/

kdb is very well designed and optimized for filtering, joining, and basic data operations on financial market data. It's definitely worth a look for inspiration for any dataframes library. I still strongly prefer its syntax vs pandas or Julia's dataframes.

[natemcintosh]

I agree this function would be very useful. It is definitely a niche to financial data, though I am sure some other fields use it. After asking that question and writing an initial function, I modified it to include a minimize component (which works for asof if the ranges are correct): https://gist.github.com/junder873/ae1ec240f2fd6d4cbdb2ec19bc2b5f9c

I am sure my code is sloppy, so I would love a more formal solution to these types of problems.

I understand how range_join performs the join by putting between two other times, but how does it work for an asof join, where you only want a row before or equal to a certain time?

[junder873]

It would be using two different components of the function I posted, the conditions component and the minimize component:

df1 = DataFrame(
    id=1:2,
    date_left=[Date(2020, 1, 5), Date(2020, 5, 3)]
)
df2 = DataFrame(
    id=[1, 1, 1, 2, 2],
    date_right=[Date(2020, 1, 1), Date(2020, 1, 4), Date(2020, 1, 6), Date(2019, 1, 1), Date(2020, 5, 1)],
    val=1:5
)



range_join(
    df1,
    df2,
    [:id],
    Tuple{Function, Symbol, Symbol}[
        (>, :date_left, :date_right)
    ],
    minimize=[:date_left => :date_right]
)

[bkamins]

So I would propose the following (we would need to think about the best name though; technically we could add this extension to leftjoin as it is not breaking, but I was not sure if it is not better to add a new name as the functionality is more complex, although leftjoin is a special case of it; potentially we could add this API to all joins but I am not sure if it is worth it - let us discuss):

rulejoin(df1, df2; on, condition=(x...) -> all(t -> isequal(t[1], t[2]), x), makeunique=false, source=nothing, validate=(false, false), renamecols=(identity => identity), window=nothing, keep=:all)

This would behave like leftjoin except that new condition, window and keep kwargs are added.

• condition: a function taking as many positional arguments as are on columns, each positional argument is a tuple of values from left and right table; by default it checks if values from left and right table are equal (so this is the default leftjoin); we could add predefined functions for some standard conditions (like maximum absolute distance, greater than etc.)
• keep: which matching rows from the right table to keep. By default :all to keep all rows. Other options are :first - keep first matching row, :last - keep last matching row, or a function, in this case it is taking as many positional arguments as are on columns, each positional argument is a tuple of values from left and right table and it should return values that are comparable and have total order; the returned value is the first row that is a minimal element of the set of matching rows;
• window:
  • if nothing then the operation is O(n*m) - just all combinations of left and right table are checked; the result is produced in the order of rows from df1
  • if :ascending then df1 and df2 are sorted before operation and it is guaranteed by the user that condition is a "window function" (i.e. as you move along the condition after data frames are sorted the matching rows are a continuous block and both begin and end of the block are increasing); in this case, after sorting the cost of matching is O(n+m). Sorting is done only if needed in particular (so
  • if :descending then the behavior is the same as for :ascending, but with rev=true when sorting

Adding this feature will cover all kinds of joins on arbitrary condition, with all kinds of "as of" and similar joins being a special case and fast.

What I am not sure about if it is not overly general (and thus not needed in practice). Maybe it is enough to ensure such matching only on a single column and just allow other on columns to be standard equijoin conditions?

CC @nalimilan