ENH: merge_asof() has type specializations and can take multiple 'by' parameters (#13936)
State: closed

 - [x] closes #13936
 - [x] tests added / passed
 - [x] passes ``git diff upstream/master | flake8 --diff``
 - [x] whatsnew entry

Labels:
name: Reshaping
description: Concat, Merge/Join, Stack/Unstack, Explode
name: Dtype Conversions
description: Unexpected or buggy dtype conversions

Comments:
Hmm, AppVeyor failed with 

> Build execution time has reached the maximum allowed time for your plan (60 minutes).

I notice the same thing happened on #14771 and #14757.
@chrisaycock : Rebase onto `master` to re-trigger Appveyor.  Don't know exactly why Appveyor does this.
@gfyoung Thanks, re-running now.
pls update as @jorisvandenbossche changed the asv's a bit
## [Current coverage](https://codecov.io/gh/pandas-dev/pandas/pull/14783?src=pr) is 85.31% (diff: 100%)
> Merging [#14783](https://codecov.io/gh/pandas-dev/pandas/pull/14783?src=pr) into [master](https://codecov.io/gh/pandas-dev/pandas/branch/master?src=pr) will increase coverage by **<.01%**

```diff
@@             master     #14783   diff @@
==========================================
  Files           144        144          
  Lines         51004      51023    +19   
  Methods           0          0          
  Messages          0          0          
  Branches          0          0          
==========================================
+ Hits          43511      43532    +21   
+ Misses         7493       7491     -2   
  Partials          0          0          
```

> Powered by [Codecov](https://codecov.io?src=pr). Last update [a8cabb8...ffcf0c2](https://codecov.io/gh/pandas-dev/pandas/compare/a8cabb8ebb5875f2aa6e69c355e0ba2af06f7438...ffcf0c23fe20d58635ef577c4f82346084c4e4b1?src=pr)
@jreback I've update the benchmarks:

```
· Running 10 total benchmarks (2 commits * 1 environments * 5 benchmarks)
[  0.00%] · For pandas commit hash fafbb022:
[  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
[ 10.00%] ··· Running join_merge.MergeAsof.time_by_int                                                           21.26ms
[ 20.00%] ··· Running join_merge.MergeAsof.time_by_object                                                        25.12ms
[ 30.00%] ··· Running join_merge.MergeAsof.time_multiby                                                         471.15ms
[ 40.00%] ··· Running join_merge.MergeAsof.time_noby                                                              9.62ms
[ 50.00%] ··· Running join_merge.MergeAsof.time_on_int32                                                         12.68ms
[ 50.00%] · For pandas commit hash 14e48153:
[ 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
[ 60.00%] ··· Running join_merge.MergeAsof.time_by_int                                                           21.49ms
[ 70.00%] ··· Running join_merge.MergeAsof.time_by_object                                                        38.56ms
[ 80.00%] ··· Running join_merge.MergeAsof.time_multiby                                                           failed
[ 90.00%] ··· Running join_merge.MergeAsof.time_noby                                                              9.37ms
[100.00%] ··· Running join_merge.MergeAsof.time_on_int32                                                         15.42ms   
    before     after       ratio
  [14e48153] [fafbb022]
-   15.42ms    12.68ms      0.82  join_merge.MergeAsof.time_on_int32
-   38.56ms    25.12ms      0.65  join_merge.MergeAsof.time_by_object

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
```

Please advise on the `dict` vs `PyObjectHashTable`. Should I revert that change? The `dict` definitely  makes the code more complicated, but the benchmark improves significantly.

@chrisaycock this add significant complexity to the code and not in favor of this approach. That said, you might be able to use / create somethign like #14859 which does something very similar. IOW, you make a new hashtable type that has specialized properties (IIRC you are using tuples here?)
@jreback I'll just remove that change for now. The point of this PR is to get the "multi-by", so I'll focus on that. Thanks!
@chrisaycock absolutley.

and FYI, you should generally just categorize your object dtypes anyhow. (we could even do that under the hood for merging purposes).

pls make a new issue w.r.t. these points if you would like
AppVeyor is producing a very odd error. It keeps failing for `test_multiby_heterogeneous_types`, but computes a different resulting value each time!

The [first run](https://ci.appveyor.com/project/jreback/pandas-465/build/1.0.2521/job/1q42n5x5wb5pqt1m) computes:

```
[nan, 51.95, nan, nan, 720.5]
```

The [second run](https://ci.appveyor.com/project/jreback/pandas-465/build/1.0.2522/job/l86scoduxd7ckcu2) computes:

```
[nan, nan, nan, nan, 720.5]
```

The [third run](https://ci.appveyor.com/project/jreback/pandas-465/build/1.0.2524/job/6m61bb9ac934dog5) computes:

```
[nan, 51.95, nan, nan, nan]
```

There are no code differences between the second and third run! (I changed a line in the whatsnew to force a re-run in AppVeyor).

I have been unable to reproduce the error on my machine in either Py2 or Py3.

Given that the values change each run, I wonder if there is some element of randomness. The `test_multiby_heterogeneous_types` will invoke `stringify()` on a two-dimensional NumPy array where each array element contains a number and a string. But since I can't reproduce the error on my system (the results are always the same), I'm kind of at a loss for how to track this down.
@chrisaycock I can run your PR on windows tomorrow. but in any event, you should simply use the ``hash_array`` instead of stringifying things (IIUC what you are doing)
@jreback I'm trying to use the array as a key, like

```
In [19]: xs = np.arange(3)

In [20]: h = PyObjectHashTable()

In [21]: h.set_item(xs, 1)
...
TypeError: unhashable type: 'numpy.ndarray'
```

The NumPy array is not hashable, so both `PyObjectHashTable` and `dict` can't take it.

As for why I'm doing it this way, my [asof_join logic](https://github.com/pandas-dev/pandas/blob/master/pandas/src/joins_func_helper.pxi.in#L28) stores the last-seen index for the `by` parameter as the function linearly scans the array of timestamps. That's why the algo works in a single pass, which makes it extremely fast.

To handle an array in the `by` parameter, I need to hash multiple values at once. Since a NumPy array isn't hashable, I went with turning it into a string. (`.tostring()` returns the raw bytes, which is sufficient for what I need.)

This has worked reasonably well in testing, at least on my Mac.
```
In [9]: from pandas.tools.hashing import hash_array

In [10]: arr = np.arange(3)

In [11]: arr
Out[11]: array([0, 1, 2])

In [13]: np.bitwise_xor.reduce(hash_array(arr))
Out[13]: 10178186328804430191
```
I had a pr to make this a convenience function ,but its pretty trivial
@chrisaycock so this passed for me on windows (just noticed it failed on 3.4 on travis though).

so I suspect something is not stable in the multi-grouping......
@jreback Thanks for checking. I'll dig some more into this.
Just a note for posterity: After a lot of trial and error, I was able to get `.tostring()` to return different values for the same input:

```python
In [291]: np.array([0, 'QSDU'], dtype=object).tostring()
Out[291]: b'PH!\x00\x01\x00\x00\x00\x10qL\x0c\x01\x00\x00\x00'

In [292]: np.array([0, 'QSDU'], dtype=object).tostring()
Out[292]: b'PH!\x00\x01\x00\x00\x00\xe0%>\x0c\x01\x00\x00\x00'

In [293]: np.array([0, 'QSDU'], dtype=object).tostring()
Out[293]: b'PH!\x00\x01\x00\x00\x00\xf0!>\x0c\x01\x00\x00\x00'

In [294]: np.array([0, 'QSDU'], dtype=object).tostring()
Out[294]: b'PH!\x00\x01\x00\x00\x000Wq\x0c\x01\x00\x00\x00'

In [295]: np.array([0, 'QSDU'], dtype=object).tostring()
Out[295]: b'PH!\x00\x01\x00\x00\x00@Zq\x0c\x01\x00\x00\x00'
```

So the culprit is definitely this approach. I also tried the `Categorical`, which worked but was 20 times slower. Since multi-by is already 20 times slower than what I want, I abandoned this path.

I will continue digging.
@jreback Using a tuple representation solved the problem. (TravisCI failed an unrelated test with "Network is unreachable".) Any further thoughts on this PR?
just a couple of minor changes. ping when green.
@jreback It's all green!
thanks!
@chrisaycock very odd, some builds failed: https://travis-ci.org/pandas-dev/pandas/jobs/184684273

but these *did* clear up subsequently any ideas?
@jreback That's weird. The type specialization was the easy part; the "multi-by" logic was what caused all the grief on this PR.

I can't reproduce the error from the tip of the master branch in either 2.7 or 3.5 on my Mac. I will dig into this and see what I can find.
i suppose it's a cython caching problem 
@jreback Hmm, ok. Is there a way to prevent that in future tests? That `NoneType` error means that `_asof_by_function()` and `_asof_function()` can't find the Cython specialization for the desired data type. I should probably put a better error statement in there instead of relying on the `NoneType` message anyway.

By the way, did `test_on_specialized_type()` change in between the time I submitted the PR and now? 

I had used an `else` statement:

https://github.com/pandas-dev/pandas/pull/14783/files#diff-e00646757b932a2684fda4588f99009cR678

Now there's a `continue` statement:

https://github.com/chrisaycock/pandas/blob/master/pandas/tools/tests/test_merge_asof.py#L678

The effects are the same, so the nature of the test didn't change. I just think it's strange that I can't find anything in `git blame`.

i made a tiny change in he tests when committing

yeah i think this is a cache issue -
@jreback Alright, thanks. I'll add a better error statement for missing type specialization in a future commit.
i don't think that's necessary

it's compiled code so can't be missing