BUG: Index.get_indexer_non_unique misbehaves with multiple nan
State: closed

- [x] closes #35392
- [x] tests added / passed
- [x] passes `black pandas`
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [x] whatsnew entry

Looking at the implementation in index.pyx, I notice that when `[np.nan]` is passed to `get_indexer_non_unique`, the code was not able to get passed the `__contains__` method for stargets (line 314).

Further testing (python=3.7.7, numpy=1.18.5):

```
import numpy as np

# Case 1: Does not work -> prints nothing
# nan dtype: np.float64, ndarray dtype: np.float64
targets = np.array([np.nan])

# Case 2: Works -> prints 0, 1, 2
# nan dtype: U3, ndarray dtype: <U32
targets = np.array([np.nan, 'var1'])

values = np.array([np.nan, 'var1', np.nan])

stargets = set(targets)

for i, v in enumerate(values):
    if v in stargets:
        print(i)
```

Case 1 and 2 results differ because of the dtype of nan (U3 vs float64).

Upon further research, I figured out that np.nan != np.nan as per IEEE (when it is a float) and creating a set from a np.array could lead to some bizarre results (https://github.com/numpy/numpy/issues/9358). Also, since a dictionary is the main data structure in this method to keep track of the targets indices, I don't think it is ideal to use nans as keys (https://stackoverflow.com/questions/6441857/nans-as-key-in-dictionaries).

I thought it would be appropriate to replace nans (with 0s) in the targets and values arrays in order to avoid the problems stated above. When considering where to replace the nans, I thought of two places where it could potentially happen:

1. In `get_indexer_non_unique` (/pandas/core/indexes/base.py)
2. In `get_indexer_non_unique` (/pandas/_libs/index.pyx)

Including the changes in 1. would mean overwriting the the Index object's properties, so I decided to include the changes in 2.

FYI -- I wasn't sure if the test I included was in the correct file. Please let me know if you would like this test to be in another file.


Labels:
name: Indexing
description: Related to indexing on series/frames, not to indexes themselves
name: Missing-data
description: np.nan, pd.NaT, pd.NA, dropna, isnull, interpolate

Comments:
Thanks for the comments, @arw2019! I just committed the changes.
@WillAyd I added a check to disambiguate between 0 and np.nan. I believe the CI failure is unrelated (`test_s3_roundtrip_for_dir`). Let me know what you think!
Is it only/mainly object-dtype Index that is getting this wrong?
@jbrockmendel tested this on master and it looks like even when using Float64Index, it is incorrect:
```
>>> import pandas as pd
>>> import numpy as np
>>> axis = pd.Index([np.nan, 1.0, np.nan], dtype=np.float64)
>>> axis.get_indexer_for([np.nan])
array([-1])
>>> axis
Float64Index([nan, 1.0, nan], dtype='float64')
```

but this PR should solve the issue no matter if pd.Index is float64 or object dtype:
```
>>> import pandas as pd
>>> import numpy as np
>>> axis = pd.Index([np.nan, "1.0", np.nan], dtype=object)
>>> axis
Index([nan, '1.0', nan], dtype='object')
>>> axis.get_indexer_for([np.nan])
array([0, 2])
>>> axis = pd.Index([np.nan, 1.0, np.nan], dtype=np.float64)
>>> axis
Float64Index([nan, 1.0, nan], dtype='float64')
>>> axis.get_indexer_for([np.nan])
array([0, 2])
```
@jbrockmendel - my PR caused your test to fail:

In pandas/tests/indexing/test_loc.py (test_loc_getitem_listlike_unused_category_raises_keyerro) are raising the following errors:
```
KeyError: "Passing list-likes to .loc or [] with any missing labels is no longer supported. The following labels were missing: Index([-1], dtype='object'). See https://pandas.pydata.org/pandas-docs/stable/user_guide/indexing.html#deprecate-loc-reindex-listlike"
```

```
AssertionError: Regex pattern 'Passing list-likes to .loc or \\[\\] with any missing labels is no longer supported. The following labels were missing: (Categorical)?Index\\(\\[nan\\], .*\\). See https' does not match '"Passing list-likes to .loc or [] with any missing labels is no longer supported. The following labels were missing: Index([-1], dtype=\'object\'). See https://pandas.pydata.org/pandas-docs/stable/user_guide/indexing.html#deprecate-loc-reindex-listlike"'.
```

Since I am setting the NaN values in the Index to -1, it is causing `_validate_read_indexer` to trigger its assertion statement. I'm unsure how to resolve this. Is my implementation not supportable due to this error?
> Since I am setting the NaN values in the Index to -1, it is causing _validate_read_indexer to trigger its assertion statement. I'm unsure how to resolve this. Is my implementation not supportable due to this error?

The user-facing exception message should reflect the key the user actually passed.  So IIUC you need to sort of undo the np.nan->0 replacement
> > Since I am setting the NaN values in the Index to -1, it is causing _validate_read_indexer to trigger its assertion statement. I'm unsure how to resolve this. Is my implementation not supportable due to this error?
> 
> The user-facing exception message should reflect the key the user actually passed. So IIUC you need to sort of undo the np.nan->0 replacement

agreed. my new implementation does not mutate the original target/values, and instead handles within the for loop (as suggested by your comment earlier)
lgtm. @WillAyd or @jbrockmendel if any other comments.
@alexhlim can you merge master to resolve conflicts.
@simonjayhawkins just merged with master!
@alexhlim ok i think @jbrockmendel has a question. Are all the cases in the OP covered by tests? (meaning the user facing cases). can you merge master, ping when ready.
@jreback all cases in OP are in included in the tests. once I resolve issue above, I will merge master and ping.
@jbrockmendel I separated sections of `get_indexer_non_unique` so I could override in IndexEngine's subclasses (ObjectEngine, Float32Engine, Float64Engine). let me know what you think!
@alexhlim can you also run the indexing perf asv's for this.
Is the issue multiple NaNs, or would this also fix `pd.Index(["a", "b", "a", np.nan]).get_indexer_non_unique([np.nan])`?
@jbrockmendel I noticed you submitted a PR that will close the original issue. if that's the case, would you like me to close this PR? or are there some changes that I have incorporated in this PR that you would like merged?
>  I noticed you submitted a PR that will close the original issue. if that's the case, would you like me to close this PR? or are there some changes that I have incorporated in this PR that you would like merged?

I was hoping you'd port whatever parts of my PR are useful and then I'll close mine.  You did most of the work here.
> > I noticed you submitted a PR that will close the original issue. if that's the case, would you like me to close this PR? or are there some changes that I have incorporated in this PR that you would like merged?
> 
> I was hoping you'd port whatever parts of my PR are useful and then I'll close mine. You did most of the work here.

Thanks for the guidance, I will definitely port your work into this PR!
@jbrockmendel I liked the simplicity of your implementation better, so I decided to use it instead of what I currently have. I added a test case for the matching-but-not-identical nans. also, I rebased this PR so there's a cleaner commit history.
@jreback ran the index asv: some performance decreased:

```
asv continuous -f 1.1 upstream/master HEAD -b ^indexing

       before           after         ratio
     [5675cd8a]       [85dd25ce]
     <master>         <nui-regression>
+        81.5±2ms          107±2ms     1.31  indexing.NumericSeriesIndexing.time_getitem_lists(<class 'pandas.core.indexes.numeric.UInt64Index'>, 'nonunique_monotonic_inc')
+        80.4±1ms          105±3ms     1.31  indexing.NumericSeriesIndexing.time_getitem_array(<class 'pandas.core.indexes.numeric.Int64Index'>, 'nonunique_monotonic_inc')
+        81.8±2ms          106±1ms     1.29  indexing.NumericSeriesIndexing.time_getitem_lists(<class 'pandas.core.indexes.numeric.Int64Index'>, 'nonunique_monotonic_inc')
+      83.3±0.9ms        105±0.9ms     1.26  indexing.NumericSeriesIndexing.time_getitem_array(<class 'pandas.core.indexes.numeric.UInt64Index'>, 'nonunique_monotonic_inc')
+        81.9±2ms          101±2ms     1.24  indexing.NumericSeriesIndexing.time_loc_array(<class 'pandas.core.indexes.numeric.Int64Index'>, 'nonunique_monotonic_inc')
+      8.14±0.3ms       10.0±0.2ms     1.23  indexing.NumericSeriesIndexing.time_loc_scalar(<class 'pandas.core.indexes.numeric.UInt64Index'>, 'nonunique_monotonic_inc')
+        88.4±2ms          106±2ms     1.19  indexing.NumericSeriesIndexing.time_getitem_array(<class 'pandas.core.indexes.numeric.Float64Index'>, 'nonunique_monotonic_inc')
+        88.5±1ms          106±1ms     1.19  indexing.NumericSeriesIndexing.time_getitem_lists(<class 'pandas.core.indexes.numeric.Float64Index'>, 'nonunique_monotonic_inc')
+         128±2μs          143±3μs     1.12  indexing.NumericSeriesIndexing.time_getitem_slice(<class 'pandas.core.indexes.numeric.Float64Index'>, 'nonunique_monotonic_inc')

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
PERFORMANCE DECREASED.

```
LGTM @alexhlim can you merge master
LGTM pending green cc @jreback
@jbrockmendel noticed that CI / Checks is failing:

1. [doctest] pandas.core.generic.NDFrame.to_xarray
2. Typing validation

Are these errors something that my PR caused?  If not, should I wait until these errors are resolved on master and re-merge?
Looks like those are unrelated, #42716
@jbrockmendel @jreback pinging b/c green
thanks @alexhlim very nice, will merge on green.
thanks @alexhlim 
Thank you everyone, especially @jbrockmendel and @jreback for guiding me through this PR. I definitely learned a lot!