ENH: Faster merge_asof() performs a single pass when joining tables (#13902)
State: closed

This version passes existing regression tests but is ultimately wrong
because it requires the "by" column to be a single object. A proper version
would handle int (and possily float) columns through type differentiation.


Labels:
name: Datetime
description: Datetime data dtype
name: Missing-data
description: np.nan, pd.NaT, pd.NA, dropna, isnull, interpolate
name: Performance
description: Memory or execution speed performance

Comments:
lint failed with

```
'pandas.types.common._ensure_platform_int' imported but unused
```

I will fix this in a subsequent update.

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

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

``` diff
@@             master     #13903   diff @@
==========================================
  Files           139        139          
  Lines         50143      50154    +11   
  Methods           0          0          
  Messages          0          0          
  Branches          0          0          
==========================================
+ Hits          42776      42780     +4   
- Misses         7367       7374     +7   
  Partials          0          0          
```

> Powered by [Codecov](https://codecov.io?src=pr). Last update [142c796...f0d0165](https://codecov.io/gh/pydata/pandas/compare/142c7968a1918fd56b7ad40ea7c013a48b0c25fc...f0d0165072f6e76421f60c672b75071b677e85f0?src=pr)

First attempt at Tempita. More work needed still -- not ready for merge yet.

While Travis is running, here are the latest benchmarks:

```
$ asv continuous master -b "join_merge.merge_asof_*"
· Creating environments
· Discovering benchmarks
·· Uninstalling from conda-py2.7-Cython-matplotlib-numexpr-numpy-openpyxl-pytables-scipy-sqlalchemy-xlrd-xlsxwriter-xlwt.
·· Installing into conda-py2.7-Cython-matplotlib-numexpr-numpy-openpyxl-pytables-scipy-sqlalchemy-xlrd-xlsxwriter-xlwt.
· Running 6 total benchmarks (2 commits * 1 environments * 3 benchmarks)
[  0.00%] · For pandas commit hash 2a01e11a:
[  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
[ 16.67%] ··· Running join_merge.merge_asof_by_int.time_merge_asof_by_int                                       24.79ms
[ 33.33%] ··· Running join_merge.merge_asof_by_object.time_merge_asof_by_object                                 41.29ms
[ 50.00%] ··· Running join_merge.merge_asof_noby.time_merge_asof_noby                                           12.63ms
[ 50.00%] · For pandas commit hash e5ee5d2e:
[ 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
[ 66.67%] ··· Running join_merge.merge_asof_by_int.time_merge_asof_by_int                                      447.26ms
[ 83.33%] ··· Running join_merge.merge_asof_by_object.time_merge_asof_by_object                                533.65ms
[100.00%] ··· Running join_merge.merge_asof_noby.time_merge_asof_noby                                           78.02ms
   before     after       ratio
  [e5ee5d2e] [2a01e11a]
-   78.02ms    12.63ms      0.16  join_merge.merge_asof_noby.time_merge_asof_noby
-  533.65ms    41.29ms      0.08  join_merge.merge_asof_by_object.time_merge_asof_by_object
-  447.26ms    24.79ms      0.06  join_merge.merge_asof_by_int.time_merge_asof_by_int

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
```

This can handle `on` as {`int64_t`, `double`} and `by` as {`int64_t`, `object`}. But it only allows one column in the `by` parameter. So either I'll have to change how I'm doing things, or change the spec of the function such that only one column is permitted.

it's fine to limit this for now
we can always expand / fix that later

@jreback Alright, I've made it explicit now, both in the documentation and in the validation.

just merged https://github.com/pydata/pandas/pull/13925

pls rebase and can merge this

@jreback Everything has been rebased and pushed. Thanks!

thanks @chrisaycock 

very nice!

2 things for future:

1) can you raise an issue about limitations in using `on` (e.g. need to expand the dtypes accepted). and show an example
2) releasing GIL on this is very easy (though not sure it would help very much, but prob won't hurt).