ENH: conditional merge - initial concept
State: closed

- [ ] closes #8962
- [ ] tests added / passed
- [ ] Ensure all linting tests pass, see [here](https://pandas.pydata.org/pandas-docs/dev/development/contributing.html#code-standards) for how to run them
- [ ] whatsnew entry

This is an initial implementation of a conditional join proposed here: https://github.com/pandas-dev/pandas/issues/8962#issuecomment-871958622

This is by no means meant to be a final solution, but just meant to get some momentum behind the feature. 

The following issue provides the proposed initial implementation and examples for the usefulness an optimized version of this feature could provide: https://github.com/pandas-dev/pandas/issues/41150

Example Usage:

```
Merge dataframes df1 and df2, where column df1.timestep falls within the range
of df2.timestart to df2.timeend, using `condition`.

>>> df1 = pd.DataFrame({'timestep': range(5)})
>>> df2 = pd.DataFrame({'mood': ['happy', 'jolly', 'joy', 'cloud9'],
                        'timestart': [0, 2, 2, 3],
                        'timeend': [1, 3, 4, 4]})
>>> df1
   timestep
0         0
1         1
2         2
3         3
4         4
>>> df2
     mood  timestart  timeend
0   happy          0        1
1   jolly          2        3
2     joy          2        4
3  cloud9          3        4
>>> df1.merge(
...     df2,
...     condition=lambda dfx: (dfx.timestart <= dfx.timestep)
...                           & (dfx.timestep <= dfx.timeend)
... ).pivot_table(index='timestep', values='mood', aggfunc=', '.join)
                        mood
timestep                    
0                      happy
1                      happy
2                 jolly, joy
3         jolly, joy, cloud9
4                joy, cloud9
```

Labels:
name: Enhancement
name: Reshaping
description: Concat, Merge/Join, Stack/Unstack, Explode

Comments:
@jreback @mroeschke - Any thoughts on this conditional join concept. @jreback you mentioned [here](https://github.com/pandas-dev/pandas/issues/41150#issuecomment-846508901) that you would consider a solution similar to this for conditional merging, do you still think this is a reasonable initial solution?

(re-pinged after opening the PR)
@jreback was waiting until we decided how/if we actually wanted to move forward with this feature before adding tests. I'll go ahead and add them soon though.
@jreback added a couple tests, also did some initial benchmarks on some contrived examples.

```
left = pd.DataFrame(range(10000), columns=['t'])
right = pd.DataFrame([['x', 1, 5]] * 10000, columns=['a', 's', 'e'])

# existing generic merge approach - ~50sec ~3GB peak
right.merge(left, how='cross').loc[lambda dfx: (dfx.t >= dfx.s) & (dfx.t <= dfx.e)]

# new conditional merge approach - ~16sec ~187MB peak
right.merge(left, condition=lambda dfx: (dfx.t >= dfx.s) & (dfx.t <= dfx.e))
```

Keep in mind this is the most naive/least performant possible approach to conditional merging (chunked and fixed chunk size), so plenty of room for optimization I would think.
@jreback - any thoughts on latest changes?
@jreback - Sorry for the incoming wall of text. I am moving the goal posts a bit, and I'm not sure if some of the stuff I'm introducing below has been considered and subsequently dismissed in the past, also if this is out of scope for the library, please let me know as well.

cc @mroeschke as well since you were involved in some of the conditional join discussions

First, I think there's 2 things to address here:

1) should we modify the default
2) should we allow other types of joins with condition besides cross

My thoughts are:

1) You are right we should leave it as inner.
2) Actually I thought about this more and I had mistakenly attributed the functionality of how=cross with custom condition to what really should have been how=inner with custom condition (this was because my initial proposal was an explictily lazy cross join with deferred filter, and that generally speaking for merges how=cross + filter=condition provides equivalent results to how=inner + on=condition).
So, actually I think for the time being we should only support how=inner with a custom condition (and leave how=cross as is, strictly cartesian product, no conditions). The reason I think we should only support how=inner for now is because only it can preserve the same behavior from initial naive implementation to final desired implementation (will expand on this below along with some other things).

Before I continue on why I think other join types wouldn't stay consistent, I thought about the API a bit more, and I think that actually it makes more sense for the condition to be provided through the `on` keyword (this is relevant to my point about preserving behavior). This is more consistent with how joins work in general. The fact that in the current api we provide e.g. `on=[A, B]` (ignoring the other left/right_on/index args for now) is really just a shorthand for `on=left.A == right.A and left.B == right.B`. The current interface is a specialization of the more general conditions of what constitutes a match in a join. So I think it would make sense to provide your callable condition in the `on` argument (as an addition to what is allowed in `on`, all the existing functionality would remain).

I actually wouldn't recommend anymore a separate `condition` argument (especially not in tandem with `on`) because essentially with the way `on` works right now it will act as an `AND col==col` addition to your condition which is overly restricting. 

Getting to why other join types won't stay consistent with the final approach now. As it stands right now the fact that we are considering a chunked approach to start with, this will also enforce some limitation on what we can do. With a simple naive chunked approach, you can't recreate a left, right or outer join by joining the cartesian product pairs of chunks. This will introduce duplicate record artifacts into your result (I guess you could introduce some logic to clean up in these cases). Even if you could cleanly do the left/right/outer joins in the chunked manner you'd need to satisfy the SLA of "preserving the left or right's key order", which will not be trivial/performant after aggregating the chunked results.

With inner joins we can provide an initial chunked implementation that will satisfy the api of and generalizable nature of a final solution. As of today we could very easily setup the interface to work like so, without interfering with any existing functionality (same mechanism as current PR, just allow `on` to be callable and remove `condition`):

```
left.merge(right, how='inner', on=lambda left, right: left.A == right.A)
```

For inner join with `on=callable`, none of the existing merging mechanisms would be used, it would actually be identical to how I had proposed cross join with condition=callable.

All this said the desired final state would require quite a bit of additions to the cython joining code: `pandas/_libs/join.pyx`. All the existing implementations would still exist for when you use merge with the classic `on=<some column names>`. Since it looks like the existing cython join code uses factorized column values and is optimized for equality,  we'd need to write new (separate/additional) versions of those functions that can compare the actual values to determine when a join condition is met.
@jreback @mroeschke - any thoughts on the proposal above? To summarize, for the initial implementation I am suggesting the following:

1) No `condition` argument, custom callable conditions would be provided through `on` argument (all changes to existing api/args would be additive, no breaking changes)
2) For now, restrict on=callable to how=inner, while feature is implemented through chunked merging
3) on=callable would take 2 parameters `(left, right)`
4) Resulting frames (in all existing/future on=callable cases) would include all columns from both left/right, conflicting columns will be suffixed with suffixes provided, even if columns are used in the condition (since left/right column of same name could have different values)
5) For future development, add optimized join functions to `pandas/_libs/join.pyx` after which we can implement how=[outer, left, right]
> @jreback @mroeschke - any thoughts on the proposal above? To summarize, for the initial implementation I am suggesting the following:
> 
> 1. No `condition` argument, custom callable conditions would be provided through `on` argument (all changes to existing api/args would be additive, no breaking changes)
> 2. For now, restrict on=callable to how=inner, while feature is implemented through chunked merging
> 3. on=callable would take 2 parameters `(left, right)`
> 4. Resulting frames (in all existing/future on=callable cases) would include all columns from both left/right, conflicting columns will be suffixed with suffixes provided, even if columns are used in the condition (since left/right column of same name could have different values)
> 5. For future development, add optimized join functions to `pandas/_libs/join.pyx` after which we can implement how=[outer, left, right]

i am fine with allowing `on` as a 2-arg callable, makes it very simple to handle here (and restricting to `how='inner'` is fine as well as that's the default.

I wouldn't touch cython at this point, just write a python impl for correctness.
@aa1371 It's great to see work on this feature in pandas! I'm working on implementing conditional joins in [cudf](https://github.com/rapidsai/cudf/). We have a working C++ implementation based on constructing and evaluating an expression via an abstract syntax tree. At the moment, the most natural Python API to translate to that is something closer to pandas `query` API, namely accepting an expression (as a string) for the `on` parameter and then translating it into a suitable expression for evaluation. Accepting an arbitrary callable is quite a bit trickier for us given the need for GPU evaluation. Would you be open to expanding your API to accept either a string _or_ a callable for the `on` parameter? That would allow us to maintain at least partial compatibility, accepting that pandas would support the more general case of an arbitrary callable that `cudf` has no plans to handle at the moment. 

Taking your last comment, my suggestion would translate your example
```
left.merge(right, how='inner', on=lambda left, right: left.A == right.A)
```
to
```
left.merge(right, how='inner', on="left.A == right.A")
```

Converting a string to a callable is straightforward via [`compile`](https://docs.python.org/3/library/functions.html#compile) at which point it could be treated identically to a user-provided callable: 
```
on = eval(compile('lambda left, right: ' + on, '<string>', mode='eval')) if isinstance(on, str) else on
```
@vyasr - I’ll defer that decision to @jreback. I will say though that there’s still some decisions to be made on how the callable condition would work (see this comment: https://github.com/pandas-dev/pandas/pull/42964#discussion_r706663412).
This pull request is stale because it has been open for thirty days with no activity. Please update or respond to this comment if you're still interested in working on this.
@jreback - thoughts on this comment?
https://github.com/pandas-dev/pandas/pull/42964#discussion_r706663412
@aa1371 not objecting to the api

the implementation needs to fit into the current patterns 
looking forward to this ! 
Hello @aa1371! Thanks for updating this PR. We checked the lines you've touched for [PEP 8](https://www.python.org/dev/peps/pep-0008) issues, and found:









There are currently no PEP 8 issues detected in this Pull Request. Cheers! :beers: 

##### Comment last updated at 2022-01-05 23:37:03 UTC
@jreback - regarding this point (https://github.com/pandas-dev/pandas/pull/42964#discussion_r706663412), for now I've decided to not add too many custom restrictions. Thus the left/right arg in the callable `on` conditions will remain as plain dfs. However I've added this note in the `on` param section in the merge docstring to raise awareness to the fact that this might change in the future.

```
    ** note: Currently, for callables, the 2 arguments are represented by
             DataFrame objects. This is subject to change in the future. For
             the highest chance of forward compatibility treat the args passed
             into the callable as if they are a simple datastructure
             (e.g. dictionary or dataclass) holding just a single row of the
             merge operation, such that accessing any element in the
             datastructure would provide a scalar value, rather than a
             column/Series.
```
Let me know what you think about this decision.
> I need you to move this in line with the current implementation in order to proceed.

@jreback can you expand on what you mean by this? what needs to be addressed to be "in line" with the current implementation?
@jreback - can you please expand on what’s needed above, in order to proceed.
> @jreback - can you please expand on what’s needed above, in order to proceed.

looks where you put this code and where ALL the rest of the code is. you need to move it. 
I see, understood. 

I think there is value in keeping this distinct from the standard merge operation **for now**, and would like to refrain from modifying any of the `_MergeOperation` code as it is now, since in its current form this feature depends on internally calling `pd.merge` and since it will make an eventual optimized refactor of this feature trivial, in terms of cleaning up any implementation details included in this first iteration. 

Also because `_OrderedMerge`  inherits from `_MergeOperation`, and I don't think that in this first iteration that OrderedMerges will be supported, and thus don't think that `_OrderedMerge` should inherit any of the implementation, even if it is not exposed to users.

I think there are 2 good ways we can do this. One is the way it is currently implemented. The other is doing something along these lines.

1. leave `_MergeOperation` untouched
2. subclass it with something like `_CustomEnabledMergeOperation`, which will implement all the custom merge logic
3. in `pd.merge` use `_CustomEnabledMergeOperation` in instead of `_MergeOperation`.

With this newly proposed way, (1) any future  reimplementation of this feature will not need to untangle the current implementation from `_MergeOperation` (however simple the untangling may be), (2) all other subclasses of `_MergeOperation` will not inherit any of the custom merge logic that is currently irrelevant to them. (3) Any merging changes unrelated to custom merging can continue being made to `_MergeOperation` without having to worry about accounting for the custom merge logic (i.e. `_MergeOperation` can remain the defacto main merging operation class). And (4) `pd.merge` will remain a simple instantiation/method call of a `_MergeOperation` object. 

If you agree with the proposal above, I can go ahead any implement that. 
Thoughts?
@jreback - I updated the PR with the suggestion here: https://github.com/pandas-dev/pandas/pull/42964#issuecomment-1001712098

Let me know if you think this is a good path to move forward with.
Could you also add a doc example  & test of the feature request in https://github.com/pandas-dev/pandas/issues/10309
this still needs a lot of work. its slightly better than before.
@jreback - got it, what else needs to be considered to move forward?
> @aa1371 It's great to see work on this feature in pandas! I'm working on implementing conditional joins in [cudf](https://github.com/rapidsai/cudf/). We have a working C++ implementation based on constructing and evaluating an expression via an abstract syntax tree. At the moment, the most natural Python API to translate to that is something closer to pandas `query` API, namely accepting an expression (as a string) for the `on` parameter and then translating it into a suitable expression for evaluation. Accepting an arbitrary callable is quite a bit trickier for us given the need for GPU evaluation. Would you be open to expanding your API to accept either a string _or_ a callable for the `on` parameter? That would allow us to maintain at least partial compatibility, accepting that pandas would support the more general case of an arbitrary callable that `cudf` has no plans to handle at the moment.
> 
> Taking your last comment, my suggestion would translate your example
> 
> ```
> left.merge(right, how='inner', on=lambda left, right: left.A == right.A)
> ```
> 
> to
> 
> ```
> left.merge(right, how='inner', on="left.A == right.A")
> ```
> 
> Converting a string to a callable is straightforward via [`compile`](https://docs.python.org/3/library/functions.html#compile) at which point it could be treated identically to a user-provided callable:
> 
> ```
> on = eval(compile('lambda left, right: ' + on, '<string>', mode='eval')) if isinstance(on, str) else on
> ```

Following up here, @jreback @mroeschke any thoughts on the above? Let me know if I can provide any extra info that might help you evaluate the feasibility of the proposed modification.
> > @aa1371 It's great to see work on this feature in pandas! I'm working on implementing conditional joins in [cudf](https://github.com/rapidsai/cudf/). We have a working C++ implementation based on constructing and evaluating an expression via an abstract syntax tree. At the moment, the most natural Python API to translate to that is something closer to pandas `query` API, namely accepting an expression (as a string) for the `on` parameter and then translating it into a suitable expression for evaluation. Accepting an arbitrary callable is quite a bit trickier for us given the need for GPU evaluation. Would you be open to expanding your API to accept either a string _or_ a callable for the `on` parameter? That would allow us to maintain at least partial compatibility, accepting that pandas would support the more general case of an arbitrary callable that `cudf` has no plans to handle at the moment.
> > Taking your last comment, my suggestion would translate your example
> > ```
> > left.merge(right, how='inner', on=lambda left, right: left.A == right.A)
> > ```
> > 
> > 
> >     
> >       
> >     
> > 
> >       
> >     
> > 
> >     
> >   
> > to
> > ```
> > left.merge(right, how='inner', on="left.A == right.A")
> > ```
> > 
> > 
> >     
> >       
> >     
> > 
> >       
> >     
> > 
> >     
> >   
> > Converting a string to a callable is straightforward via [`compile`](https://docs.python.org/3/library/functions.html#compile) at which point it could be treated identically to a user-provided callable:
> > ```
> > on = eval(compile('lambda left, right: ' + on, '<string>', mode='eval')) if isinstance(on, str) else on
> > ```
> 
> Following up here, @jreback @mroeschke any thoughts on the above? Let me know if I can provide any extra info that might help you evaluate the feasibility of the proposed modification.

I am not particularly partial towards string evaluation APIs ,and pandas hasn't proliferated it's query/eval API to other methods so I'd be -1 to add it here, especially for an initial pass at this functionality.
-1 as well for strings
Thanks for letting me know. I'm not particularly a fan of string-based APIs either, so I understand wanting to avoid them. We'll see what we can do with the function approach for now.
A possibility would be to transition to `Column` objects like in PySpark.
This would also enable Pandas to perform e.g. query optimization and lazy execution.
> this still needs a lot of work

@jreback - understood. What else do we want to consider to move this forward?
@mroeschke - any additional thoughts as well?
i left comments above

simple as possible