BUG: Fix edge cases in merge_asof() by comparing factorized keys (#13709)
State: closed

closes #13709 

Also removes unnecessary check_duplicates.


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

Comments:
this is have the same perf characteristics? (I was manually doing the perf comparisons).....prob should have some asv's for this....

## [Current coverage](https://codecov.io/gh/pydata/pandas/pull/13836?src=pr) is 85.23% (diff: 100%)

> Merging [#13836](https://codecov.io/gh/pydata/pandas/pull/13836?src=pr) into [master](https://codecov.io/gh/pydata/pandas/branch/master?src=pr) will decrease coverage by **0.01%**

``` diff
@@             master     #13836   diff @@
==========================================
  Files           140        140          
  Lines         50455      50449     -6   
  Methods           0          0          
  Messages          0          0          
  Branches          0          0          
==========================================
- Hits          43014      43001    -13   
- Misses         7441       7448     +7   
  Partials          0          0          
```

> Powered by [Codecov](https://codecov.io?src=pr). Last update [59f2557...c2e049c](https://codecov.io/gh/pydata/pandas/compare/59f25575f42e19f066dc3cd2245983071e2d7813...c2e049c43e254f68487d0e625ea80bf45f005808?src=pr)

@jreback I had thought about perf issues, but since the logic is a lot smaller (avoids the call to groupsort_indexer(), for example), it has to be faster.

actually I suspect it's much slower

the bottleneck never was the cython code
rather the grouping / indexing

that is why the check_duplicates helps

Can you show me the code you used for the perf tests? I'll run them manually and report back.

notebook is [here](http://nbviewer.jupyter.org/gist/jreback/5f089d308750c89b2a7d7446b790c056)

these used the original trades.csv, quotes.csv that you had sent me:

```
-rw-rw-r--@ 1 jreback  staff  17202707 Jun  2 18:19 trades.csv
-rw-rw-r--@ 1 jreback  staff  47853000 Jun  2 18:19 quotes.csv
```

they are not in the repo; we should prob generate some for test purposes

I've refreshed my data sample since that notebook, but my DataFrames are a similar size.

```
In [3]: trades.info()
<class 'pandas.core.frame.DataFrame'>
RangeIndex: 319018 entries, 0 to 319017
Data columns (total 4 columns):
time        319018 non-null datetime64[ns]
ticker      319018 non-null category
price       316669 non-null float64
quantity    319018 non-null int64
dtypes: category(1), datetime64[ns](1), float64(1), int64(1)
memory usage: 7.6 MB

In [4]: quotes.info()
<class 'pandas.core.frame.DataFrame'>
RangeIndex: 1032780 entries, 0 to 1032779
Data columns (total 4 columns):
time      1032780 non-null datetime64[ns]
ticker    1032780 non-null category
bid       1030431 non-null float64
ask       1030431 non-null float64
dtypes: category(1), datetime64[ns](1), float64(2)
memory usage: 24.6 MB
```

I ran the numbers with a fresh build both before and after my code change.

Before:

```
In [5]: %timeit -n 1 -r 1 pd.merge_asof(trades, quotes, on='time', by='ticker')
1 loop, best of 1: 970 ms per loop
```

After:

```
In [5]: %timeit -n 1 -r 1 pd.merge_asof(trades, quotes, on='time', by='ticker')
1 loop, best of 1: 835 ms per loop
```

So my code change is moderately faster, which is what I expect. The Python logic didn't really change since the `check_duplicates` is now gone (equivalent to the `False` case). And since the Cython logic was never much of a bottleneck, changes there provide only modest performance improvements.

try it with duplicates

Are you referring to duplicate timestamps and tickers? That's already in my sample data:

```
In [16]: quotes
Out[16]:
                           time ticker     bid     ask
0       2016-07-15 13:30:00.000   GOOG  724.24  725.73
1       2016-07-15 13:30:00.002   MSFT   53.83   53.95
2       2016-07-15 13:30:00.002   MSFT   53.83   53.95
3       2016-07-15 13:30:00.004   GOOG  722.75  725.73
4       2016-07-15 13:30:00.036   GOOG  725.48  725.73
5       2016-07-15 13:30:00.036   AAPL   98.92   99.05
6       2016-07-15 13:30:00.036   GOOG  722.75  725.73
7       2016-07-15 13:30:00.036   AAPL   98.92   99.05
8       2016-07-15 13:30:00.037   MSFT   53.84   53.95
9       2016-07-15 13:30:00.037   MSFT   53.84   53.95
...                         ...    ...     ...     ...
```

And of course the regression tests with duplicate data pass.

can u add an asv (prob need to generate data given a seed)

Will do.

I added a couple of simple benchmarks. The new version slightly outperforms, as I expected.

```
· Running 4 total benchmarks (2 commits * 1 environments * 2 benchmarks)
[  0.00%] · For pandas commit hash aab3e3cc:
[  0.00%] ·· Building for conda-py2.7-Cython-matplotlib-numexpr-numpy-openpyxl-pytables-scipy-sqlalchemy-xlrd-xlsxwriter-xlwt..............................
[  0.00%] ·· Benchmarking conda-py2.7-Cython-matplotlib-numexpr-numpy-openpyxl-pytables-scipy-sqlalchemy-xlrd-xlsxwriter-xlwt
[ 25.00%] ··· Running join_merge.merge_asof_by.time_merge_asof_by                                              539.69ms
[ 50.00%] ··· Running join_merge.merge_asof_noby.time_merge_asof_noby                                           77.95ms
[ 50.00%] · For pandas commit hash 2166ac13:
[ 50.00%] ·· Building for conda-py2.7-Cython-matplotlib-numexpr-numpy-openpyxl-pytables-scipy-sqlalchemy-xlrd-xlsxwriter-xlwt..
[ 50.00%] ·· Benchmarking conda-py2.7-Cython-matplotlib-numexpr-numpy-openpyxl-pytables-scipy-sqlalchemy-xlrd-xlsxwriter-xlwt
[ 75.00%] ··· Running join_merge.merge_asof_by.time_merge_asof_by                                              708.91ms
[100.00%] ··· Running join_merge.merge_asof_noby.time_merge_asof_noby                                           97.48ms
BENCHMARKS NOT SIGNIFICANTLY CHANGED.
```

@chrisaycock lgtm. just a very small change in asv. ping when green.

Updated as per your notes. Thanks.

@jreback It's green!

thank you sir!