[PERF] Get rid of MultiIndex conversion in IntervalIndex.intersection 
State: closed

-  xref #24813 
-  passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
-  whatsnew entry

```
       before           after         ratio
     [64104ec3]       [e9ddf02b]
     <master>         <GH24813-inter>
-     1.76±0.01ms        233±0.5μs     0.13  index_object.IntervalIndexMethod.time_intersection(1000)
-      58.0±0.4ms       3.94±0.2ms     0.07  index_object.IntervalIndexMethod.time_intersection(100000)
```

Labels:
name: Performance
description: Memory or execution speed performance
name: Interval
description: Interval data type

Comments:
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/26225?src=pr&el=h1) Report
> Merging [#26225](https://codecov.io/gh/pandas-dev/pandas/pull/26225?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/64104ec343f0770afa88f02da47b34fbe62c8281?src=pr&el=desc) will **decrease** coverage by `0.01%`.
> The diff coverage is `85%`.

[![Impacted file tree graph](https://codecov.io/gh/pandas-dev/pandas/pull/26225/graphs/tree.svg?width=650&token=eZ4WkYLtcO&height=150&src=pr)](https://codecov.io/gh/pandas-dev/pandas/pull/26225?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master   #26225      +/-   ##
==========================================
- Coverage   91.97%   91.96%   -0.02%     
==========================================
  Files         175      175              
  Lines       52379    52398      +19     
==========================================
+ Hits        48178    48190      +12     
- Misses       4201     4208       +7
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.52% <85%> (-0.01%)` | :arrow_down: |
| #single | `40.69% <10%> (-0.16%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/26225?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/indexes/interval.py](https://codecov.io/gh/pandas-dev/pandas/pull/26225/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9pbnRlcnZhbC5weQ==) | `94.87% <85%> (-0.36%)` | :arrow_down: |
| [pandas/io/gbq.py](https://codecov.io/gh/pandas-dev/pandas/pull/26225/diff?src=pr&el=tree#diff-cGFuZGFzL2lvL2dicS5weQ==) | `78.94% <0%> (-10.53%)` | :arrow_down: |
| [pandas/core/frame.py](https://codecov.io/gh/pandas-dev/pandas/pull/26225/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `96.9% <0%> (-0.12%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/26225?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/26225?src=pr&el=footer). Last update [64104ec...e9ddf02](https://codecov.io/gh/pandas-dev/pandas/pull/26225?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/26225?src=pr&el=h1) Report
> Merging [#26225](https://codecov.io/gh/pandas-dev/pandas/pull/26225?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/891a419a5155e6b42c0696a81cf853b6f3febbf7?src=pr&el=desc) will **decrease** coverage by `<.01%`.
> The diff coverage is `100%`.

[![Impacted file tree graph](https://codecov.io/gh/pandas-dev/pandas/pull/26225/graphs/tree.svg?width=650&token=eZ4WkYLtcO&height=150&src=pr)](https://codecov.io/gh/pandas-dev/pandas/pull/26225?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master   #26225      +/-   ##
==========================================
- Coverage   91.87%   91.87%   -0.01%     
==========================================
  Files         174      174              
  Lines       50661    50700      +39     
==========================================
+ Hits        46547    46582      +35     
- Misses       4114     4118       +4
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.41% <100%> (ø)` | :arrow_up: |
| #single | `41.77% <29.31%> (-0.1%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/26225?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/indexes/interval.py](https://codecov.io/gh/pandas-dev/pandas/pull/26225/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9pbnRlcnZhbC5weQ==) | `96.42% <100%> (+0.22%)` | :arrow_up: |
| [pandas/core/indexes/base.py](https://codecov.io/gh/pandas-dev/pandas/pull/26225/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9iYXNlLnB5) | `96.72% <100%> (ø)` | :arrow_up: |
| [pandas/io/gbq.py](https://codecov.io/gh/pandas-dev/pandas/pull/26225/diff?src=pr&el=tree#diff-cGFuZGFzL2lvL2dicS5weQ==) | `78.94% <0%> (-10.53%)` | :arrow_down: |
| [pandas/core/frame.py](https://codecov.io/gh/pandas-dev/pandas/pull/26225/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `97% <0%> (-0.12%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/26225?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/26225?src=pr&el=footer). Last update [891a419...ea2550a](https://codecov.io/gh/pandas-dev/pandas/pull/26225?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

Thanks, will look at this in the next day or so.
pls merge master
@jreback Please tell me if you have anything to implement.
@makbigc apologies, some git conflicts have come up in the meantime. Do you have time to resolve them?
Hello @makbigc! 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 2019-06-06 08:09:48 UTC
@TomAugspurger conflict resolved
Did you intend to close this?
Yes, the present approach doesn't work. And I work in another approach which compares the left hand side and the corresponding right hand side. But the order is `n**2`. The performance is worsen.  

Thanks all for the review. I will come back when I have a better idea.
The function `get_indexer_non_unique` is used to screen out avoiding the worst case of order `n**2`. 

```
All benchmarks:

       before           after         ratio
     [ae409049]       [402b09cf]
     <master>         <GH24813-inter>
-     1.76±0.02ms          234±3μs     0.13  index_object.IntervalIndexMethod.time_intersection(1000)
-        58.7±2ms      3.82±0.05ms     0.07  index_object.IntervalIndexMethod.time_intersection(100000)
-     1.61±0.01ms          504±2μs     0.31  index_object.IntervalIndexMethod.time_intersection_duplicate(1000)
-        61.4±2ms       34.5±0.7ms     0.56  index_object.IntervalIndexMethod.time_intersection_duplicate(100000)
```
Can you merge master? Looks like merging the `IntervalIndex.is_unique` PR caused a conflict.

Looks good overall! Just one small corner case when duplicate NA values are present:
```python
In [1]: import pandas as pd; import numpy as np

In [2]: ii = pd.IntervalIndex([np.nan, np.nan])

In [3]: ii
Out[3]: 
IntervalIndex([nan, nan],
              closed='right',
              dtype='interval[float64]')

In [4]: ii.intersection(ii)
Out[4]: 
IntervalIndex([],
              closed='right',
              dtype='interval[float64]')
```
It seems the failure of test_constructor_list_frames isn't due to our change in this PR.
That's fixed on master, if you merge master and repush.

On Tue, May 28, 2019 at 2:01 AM Mak Sze Chun <notifications@github.com>
wrote:

> It seems the failure of test_constructor_list_frames isn't due to our
> change in this PR.
>
> —
> You are receiving this because you were mentioned.
> Reply to this email directly, view it on GitHub
> <https://github.com/pandas-dev/pandas/pull/26225?email_source=notifications&email_token=AAKAOIV5E2CZHTBQVZDKYGDPXTKDXA5CNFSM4HI4KVK2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODWLFBOI#issuecomment-496390329>,
> or mute the thread
> <https://github.com/notifications/unsubscribe-auth/AAKAOIXDETYIIC7LKHWE2WLPXTKDXANCNFSM4HI4KVKQ>
> .
>

@jschendel 
@jschendel  comments here
@jreback all tests passed.
thanks @makbigc very nice.

> LGTM aside from the behavior with dupes, which is inconsistent across all implementations of intersection. I'm fine merging this as-is and then resolving the dupe behavior globally at a later point in time once the expected behavior is determined.

yeah can we create an issue to resolve this, might involve some work.
not sure why the CI didin't fail here, but I think this PR made the benchmarks fail, see #26703: https://dev.azure.com/pandas-dev/pandas/_build/results?buildId=12407&view=logs

@makbigc can you take a look please?