BUG: Fix reindexing with multi-indexed DataFrames
- [x] closes https://github.com/pandas-dev/pandas/issues/29896
- [x] tests added / passed
- [x] passes `black pandas`
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [x] whatsnew entry

Addresses an issue which appears to have existed since 0.23.0 where bugs in the `get_indexer()` method for the `MultiIndex` class cause incorrect reindexing behavior for multi-indexed DataFrames.

motivating, example, from (the issue)
```python
>>> 
>>> df = pd.DataFrame({
...     'a': [0, 0, 0, 0],
...     'b': [0, 2, 3, 4],
...     'c': ['A', 'B', 'C', 'D']
... }).set_index(['a', 'b'])
>>> 
>>> df
     c
a b   
0 0  A
  2  B
  3  C
  4  D
>>> df.index
MultiIndex([(0, 0),
            (0, 2),
            (0, 3),
            (0, 4)],
           names=['a', 'b'])
>>> mi_2 = pd.MultiIndex.from_product([[0], [-1, 0, 1, 3, 4, 5]])
>>> mi_2
MultiIndex([(0, -1),
            (0,  0),
            (0,  1),
            (0,  3),
            (0,  4),
            (0,  5)],
           )
```

as expected, without a `method` value:
```python
>>> df.reindex(mi_2)
        c
0 -1  NaN
   0    A
   1  NaN
   3    C
   4    D
   5  NaN
```

using `method="backfill"`, it is:
```python
>>> 
>>> df.reindex(mi_2, method="backfill")
      c
0 -1  A
   0  A
   1  D
   3  A
   4  A
   5  C
>>>
```
but should (IMHO) be:
```python
>>> df.reindex(mi_2, method="backfill")
        c
0 -1    A
   0    A
   1    B
   3    C
   4    D
   5  NaN
>>>
```

similarly, using `method="pad"`, it is:
```python
>>> df.reindex(mi_2, method="pad")
        c
0 -1  NaN
   0  NaN
   1    D
   3  NaN
   4    A
   5    C
```
but should (IMHO) be:
```python
>>> df.reindex(mi_2, method="pad")
        c
0 -1  NaN
   0    A
   1    A
   3    C
   4    D
   5    D
```
Hello @ChrisRobo! 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 2020-04-08 05:17:02 UTC > Hello @ChrisRobo! 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:
> 
> * In the file [`pandas/tests/frame/indexing/test_indexing.py`](https://github.com/pandas-dev/pandas/blob/26c8ac3e150a8559ee5f372b0b66db44c9d2f3c2/pandas/tests/frame/indexing/test_indexing.py):
> 
> > [Line 1591:68](https://github.com/pandas-dev/pandas/blob/26c8ac3e150a8559ee5f372b0b66db44c9d2f3c2/pandas/tests/frame/indexing/test_indexing.py#L1591): [E231](https://duckduckgo.com/?q=pep8%20E231) missing whitespace after ','
> > [Line 1597:75](https://github.com/pandas-dev/pandas/blob/26c8ac3e150a8559ee5f372b0b66db44c9d2f3c2/pandas/tests/frame/indexing/test_indexing.py#L1597): [E231](https://duckduckgo.com/?q=pep8%20E231) missing whitespace after ','
> > [Line 1600:61](https://github.com/pandas-dev/pandas/blob/26c8ac3e150a8559ee5f372b0b66db44c9d2f3c2/pandas/tests/frame/indexing/test_indexing.py#L1600): [E231](https://duckduckgo.com/?q=pep8%20E231) missing whitespace after ','
> > [Line 1603:61](https://github.com/pandas-dev/pandas/blob/26c8ac3e150a8559ee5f372b0b66db44c9d2f3c2/pandas/tests/frame/indexing/test_indexing.py#L1603): [E231](https://duckduckgo.com/?q=pep8%20E231) missing whitespace after ','
> 
> * In the file [`pandas/tests/indexes/multi/test_indexing.py`](https://github.com/pandas-dev/pandas/blob/26c8ac3e150a8559ee5f372b0b66db44c9d2f3c2/pandas/tests/indexes/multi/test_indexing.py):
> 
> > [Line 279:64](https://github.com/pandas-dev/pandas/blob/26c8ac3e150a8559ee5f372b0b66db44c9d2f3c2/pandas/tests/indexes/multi/test_indexing.py#L279): [E231](https://duckduckgo.com/?q=pep8%20E231) missing whitespace after ','
> > [Line 283:53](https://github.com/pandas-dev/pandas/blob/26c8ac3e150a8559ee5f372b0b66db44c9d2f3c2/pandas/tests/indexes/multi/test_indexing.py#L283): [E231](https://duckduckgo.com/?q=pep8%20E231) missing whitespace after ','
> > [Line 287:53](https://github.com/pandas-dev/pandas/blob/26c8ac3e150a8559ee5f372b0b66db44c9d2f3c2/pandas/tests/indexes/multi/test_indexing.py#L287): [E231](https://duckduckgo.com/?q=pep8%20E231) missing whitespace after ','
> 
> ##### Comment last updated at 2020-01-06 23:44:11 UTC

the formatting decisions on these lines are auto-generated output of `black pandas`.  I defer to the reviewers here re: the preferred style decisions > i don’t think the reindeximg result is valid here
> 
> pls show your original example at the top of the PR
> include the case of reindex without pad/backfill
> 
> show the same example with an Index (factorize the tuples);
> 
> convince us why these should be different as that is what you are proposing (i think)

thanks for the quick feedback here!

I included the original example from the issue (with both what I saw and what I expected to see) and also added the case of no filling (not included in the issue because I don't view that as a bug).

Apologies for the ignorance (this is my first PR here), but what specifically are you looking for with tuple factorization?  I'm having trouble constructing an index of tuples which is not itself a MultiIndex.

My argument for why this is a bug is that backfilling/padding should respect python tuple ordering properties (which it appears to have done until version 0.23.0), e.g. `(0, 0) < (0, 1) < (0, 2)`, and so, using the case of the example
- when backfilling, the row with index value (0, 1) should have `B` (not `D`) as its `c` value, since this should be backfilled to the row with index value (0, 2) in `df` (whose `c` value is `B`)
- when padding, the row with index value (0, 1) should have `A` (not `D`) as its `c` value, since this should be padded to the row with index value (0, 0) in `df` (whose `c` value is `A`)
- moreover, in both cases, the rows with index values (0, 3) and (0, 4) should have `c` values `C` and `D` respectively (they are `A` and `A` with backfilling and `NaN` and `A` with padding), since (0, 3) and (0, 4) are both in `df.index` to begin with

Happy to add more examples or any kind of additional explanation or validation that you'd like to help make this clearer.  Thanks again for the responsiveness here's a more concise version of the example from the GH issue which still illustrates the problem, I think.  I believe that since (0, 0) < (0, 1) < (0, 2) under python tuple ordering rules, that reindexing with (0, 1) with `backfill` should give you the value of (0, 2) and reindexing with `pad` should give you the value of (0, 0)

setup:
```python
>>> df = pd.DataFrame({'a': [0, 0], 'b': [0, 2], 'c': ['A', 'B']}).set_index(['a', 'b'])
>>> df
     c
a b   
0 0  A
  2  B
>>> 
>>> mi_2 = pd.MultiIndex.from_product([[0], [1]])
>>> mi_2
MultiIndex([(0, 1)],
           )
```

in both cases, without a `method` value:
```python
>>> df.reindex(mi_2)
       c
0 1  NaN
```

filling with `backfill`, as is (which I argue is a bug):
```python
>>> df.reindex(mi_2, method='bfill')
     c
0 1  A
```
I believe it should be:
```python
>>> df.reindex(mi_2, method='bfill')
     c
0 1  B
```
similarly, as is, with `pad` (I also believe this is a bug):
```python
>>> df.reindex(mi_2, method='pad')
       c
0 1  NaN
```
whereas I believe it should be
```python
>>> df.reindex(mi_2, method='pad')
     c
0 1  A
```

hopefully this is easier to read @ChrisRobo can you update your example to show a few values, instead of a single one. some should *have* values even in the reindex and some should not so as to see the effect of the reindex. > @ChrisRobo can you update your example to show a few values, instead of a single one. some should _have_ values even in the reindex and some should not so as to see the effect of the reindex.

sure (making a new comment in the interest of preserving the history of this thread)

here's an example which I think is a bit more comprehensive.

setup:
```python
>>> df = pd.DataFrame({
...     'a': [1, 1, 1, 4, 4, 4],
...     'b': [1, 5, 9, 1, 5, 9],
...     'c': ['A', 'B', 'C', 'D', 'E', 'F'],
... })
>>> df = df.set_index(['a', 'b'])
>>> df
     c
a b   
1 1  A
  5  B
  9  C
4 1  D
  5  E
  9  F
>>> 
>>> mi_2 = pd.MultiIndex.from_tuples([
...     (1, 0),
...     (1, 5),
...     (1, 7),
...     (3, 2),
...     (4, 9),
...     (4, 11),
...     (5, 2),
... ])
>>> mi_2
MultiIndex([(1,  0),
            (1,  5),
            (1,  7),
            (3,  2),
            (4,  9),
            (4, 11),
            (5,  2)],
           )
>>> 
```
current behavior w/o a filling method (no proposed change):
```python
>>> df.reindex(mi_2)
        c
1 0   NaN
  5     B
  7   NaN
3 2   NaN
4 9     F
  11  NaN
5 2   NaN
```
current behavior w/`backfill` and `pad`:
```python
>>> df.reindex(mi_2, method='backfill')
      c
1 0   A
  5   F
  7   A
3 2   A
4 9   A
  11  D
5 2   B
>>> 
>>> 
>>> df.reindex(mi_2, method='pad')
        c
1 0   NaN
  5     F
  7   NaN
3 2   NaN
4 9   NaN
  11    C
5 2     B
```
whereas I think this is correct:
```python
>>> df.reindex(mi_2, method='backfill')
        c
1 0     A
  5     B
  7     C
3 2     D
4 9     F
  11  NaN
5 2   NaN
>>> 
>>> df.reindex(mi_2, method='pad')
        c
1 0   NaN
  5     B
  7     B
3 2     C
4 9     F
  11    F
```

this covers the case of values which are too large/too small (for backfilling/padding, respectively), cases which exist in the original and new index (i.e. (1, 5) and (4, 11)), values in the new index to which nothing is filled (i.e. (4, 5, E)), and backfilling/padding cases (i.e. those which are `NaN` without a `method` value but are not afterward).

Let me know if there's a case which this is missing but which you think it should cover! @jreback  @jbrockmendel when you get a chance, would one or both of you mind taking another look at this?

I'm happy to add more examples or test coverage if you'd like will look. thought this was going to conflict with a recently merged refactor of MI indexing. pls merge master anyhow. > will look. thought this was going to conflict with a recently merged refactor of MI indexing. pls merge master anyhow.

thanks! :).  just rebased on top of master @jreback  @jbrockmendel thanks for the suggestions, sorry for the late reply here.

I basically re-wrote this using what (I think is) a much simpler implementation, i.e. using something like an updated factorization of the MultiIndexes' tuples and passing that to the relevant filling method.  I also added types wherever I could in cython code and made additions to the tests as requested. @jreback I ran the MultiIndex asvs (exact invocation was: `asv continuous -f 1.1 -E virtualenv upstream/master HEAD -b ^multiindex`) and the result was
```
BENCHMARKS NOT SIGNIFICANTLY CHANGED.
```
I can upload (or paste a subset of) the full multiindex benchmarks if you like as well # [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/30766?src=pr&el=h1) Report
> Merging [#30766](https://codecov.io/gh/pandas-dev/pandas/pull/30766?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/ed7adcd51a9c1c44f57bcc6f6241956ce1bd047c?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/30766/graphs/tree.svg?width=650&token=eZ4WkYLtcO&height=150&src=pr)](https://codecov.io/gh/pandas-dev/pandas/pull/30766?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master   #30766      +/-   ##
==========================================
- Coverage   93.63%   93.63%   -0.01%     
==========================================
  Files         199      199              
  Lines       49472    49470       -2     
==========================================
- Hits        46325    46319       -6     
- Misses       3147     3151       +4
```


| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/30766?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/indexes/multi.py](https://codecov.io/gh/pandas-dev/pandas/pull/30766/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9tdWx0aS5weQ==) | `98.11% <100%> (ø)` | :arrow_up: |
| [pandas/io/gbq.py](https://codecov.io/gh/pandas-dev/pandas/pull/30766/diff?src=pr&el=tree#diff-cGFuZGFzL2lvL2dicS5weQ==) | `84.21% <0%> (-10.53%)` | :arrow_down: |
| [pandas/core/frame.py](https://codecov.io/gh/pandas-dev/pandas/pull/30766/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `97.13% <0%> (-0.13%)` | :arrow_down: |
| [pandas/core/indexing.py](https://codecov.io/gh/pandas-dev/pandas/pull/30766/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhpbmcucHk=) | `96.62% <0%> (-0.03%)` | :arrow_down: |
| [pandas/core/base.py](https://codecov.io/gh/pandas-dev/pandas/pull/30766/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYmFzZS5weQ==) | `97.1% <0%> (ø)` | :arrow_up: |
| [pandas/core/generic.py](https://codecov.io/gh/pandas-dev/pandas/pull/30766/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZ2VuZXJpYy5weQ==) | `96.75% <0%> (ø)` | :arrow_up: |
| [pandas/core/tools/datetimes.py](https://codecov.io/gh/pandas-dev/pandas/pull/30766/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvdG9vbHMvZGF0ZXRpbWVzLnB5) | `86.73% <0%> (ø)` | :arrow_up: |
| [pandas/core/indexes/base.py](https://codecov.io/gh/pandas-dev/pandas/pull/30766/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9iYXNlLnB5) | `98.15% <0%> (ø)` | :arrow_up: |
| [pandas/core/internals/managers.py](https://codecov.io/gh/pandas-dev/pandas/pull/30766/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW50ZXJuYWxzL21hbmFnZXJzLnB5) | `96.47% <0%> (ø)` | :arrow_up: |
| [pandas/core/arrays/sparse/scipy\_sparse.py](https://codecov.io/gh/pandas-dev/pandas/pull/30766/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL3NwYXJzZS9zY2lweV9zcGFyc2UucHk=) | `89.23% <0%> (ø)` | :arrow_up: |
| ... and [3 more](https://codecov.io/gh/pandas-dev/pandas/pull/30766/diff?src=pr&el=tree-more) | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/30766?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/30766?src=pr&el=footer). Last update [ed7adcd...ee9e7c2](https://codecov.io/gh/pandas-dev/pandas/pull/30766?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).
 @jreback @jbrockmendel I think I've addressed all comments here, would one or both of you mind taking another look whenever you get a chance? ping on this @jreback @jbrockmendel -- does it look OK?  I think I've made all the desired updates, but happy to tweak more as is necessary. @jreback per your request, I added some ASV benchmarks for these cases.

In summary, for the new benchmarks I added:
- this improves performance (> 10%) over 0.22.0, i.e. the last version where this feature worked
```
       before           after         ratio
     [a00154dc]       [0c3c0cbd]
     <v0.22.0^0>       <crobo/fix-multi-index-reindex>
...
-         552±6ms          477±3ms     0.86  multiindex_object.Integer.time_get_indexer_and_backfill
-         626±4ms          482±4ms     0.77  multiindex_object.Integer.time_get_indexer_and_pad
```
- performance with the current version of this PR is much worse than the (currently buggy) master (as expected, there were no significant changes on any of the existing ASVs)
```
       before           after         ratio
     [ed7adcd5]       [0c3c0cbd]
     <master>         <crobo/fix-multi-index-reindex>
+         124±2ms          481±6ms     3.87  multiindex_object.Integer.time_get_indexer_and_backfill
+         127±5ms          477±7ms     3.76  multiindex_object.Integer.time_get_indexer_and_pad
```
- ***however***, performance with the pre-rewrite version of this PR (i.e. more complicated) code was not significantly different from master
master:
```
[ 75.00%] · For pandas commit ed7adcd5 <master> (round 2/2):
...
[ 90.00%] ··· multiindex_object.Integer.time_get_indexer_and_backfill      123±6ms
[ 91.25%] ··· multiindex_object.Integer.time_get_indexer_and_pad            121±3ms
```
this PR, pre-simplifying re-write:
```
[ 50.00%] · For pandas commit 6c8f50a1 <crobo/fix-multi-index-reindex~19> (round 2/2):
...
[ 65.00%] ··· multiindex_object.Integer.time_get_indexer_and_backfill      122±5ms
[ 66.25%] ··· multiindex_object.Integer.time_get_indexer_and_pad           124±7ms
```

conceptually it is much simpler, IMO w/o a doubt, to implement it like this.  It definitely is slower, though.  I can take a crack at simplifying my initial implementation and making the algorithm clearer but I defer to you re: the tradeoff of performance vs. simplicity here. @jreback build is green, pinging as requested.  see info in my previous comment re: ASV performance at various commits; happy to make adjustments as desired. @ChrisRobo is the current code reflecting the above comment `this PR, pre-simplifying re-write:` ?
e.g. where we are now > @ChrisRobo is the current code reflecting the above comment `this PR, pre-simplifying re-write:` ?
> e.g. where we are now

the code in the PR right now is reflected by the second ASV snippet there.   The "pre-simplifying rewrite" commend referred to the PR as of [this review](https://github.com/pandas-dev/pandas/pull/30766#pullrequestreview-355635473), which was commit `6c8f50a1` in this branch. @ChrisRobo caffeine is still kicking in so bear with me as I make sure i understand the current status.  A previous draft of this PR maintained performance but with more complex code, while the current state of the PR is simpler but takes a performance hit? > @ChrisRobo caffeine is still kicking in so bear with me as I make sure i understand the current status. A previous draft of this PR maintained performance but with more complex code, while the current state of the PR is simpler but takes a performance hit?

hahah re: caffeine and yes precisely.  FWIW though, even the simpler but less performant code is a > 10% performance improvement over the last version (0.22.0) when this feature behaved correctly. CI currently failing on a parquet test (see failure log [here](https://dev.azure.com/pandas-dev/pandas/_build/results?buildId=31737&view=logs&j=a3a13ea8-7cf0-5bdb-71bb-6ac8830ae35c&t=add65f64-6c25-5783-8fd6-d9aa1b63d9d4)).  Not exactly sure how it's related to this change but I'll work on debugging ok, thanks to @jbrockmendel the CI issue seems to be fixed and the build is green.  Do you and @jreback have a sense of how you'd like to proceed here?  I've made all of @jreback's desired changes to the docs, I believe, but not sure how you want to proceed re: the performance/clarity questions > looks fine, can you merge master and just confirm the performance of what you have here.
> 
> sorry this took a long time to review, we have _many_ PRs. thanks

rebased on top of master, perf (in terms of times) for relevant ASV benchmarks seems the same as before

against master:
```
       before           after         ratio
     [e0dd81a5]       [7836cc90]
     <crobo/fix-multi-index-reindex~49>       <crobo/fix-multi-index-reindex>
+         120±7ms          484±9ms     4.05  multiindex_object.Integer.time_get_indexer_and_backfill
+         120±6ms          474±9ms     3.96  multiindex_object.Integer.time_get_indexer_and_pad
-        711±10μs          610±5μs     0.86  multiindex_object.Values.time_datetime_level_values_sliced
```

against 0.22.0 (last version where the correct functionality was in place):
```
       before           after         ratio
     [a00154dc]       [7836cc90]
     <v0.22.0^0>       <list>    
...
-        556±10ms          485±9ms     0.87  multiindex_object.Integer.time_get_indexer_and_backfill
-        626±10ms          482±5ms     0.77  multiindex_object.Integer.time_get_indexer_and_pad
```

and no problem re: reviews, thanks for taking the time to look at this! thanks @ChrisRobo great effort! and thanks for sticking with it. we are getting lots of PRs now-a-days and hard to give good review on them all. my pleasure, and thanks @jreback and @jbrockmendel for the time reviewing! 