Repository: pandas-dev/pandas
Pull request: BUG: pivot/unstack leading to too many items should raise exception

- [x] closes #20601
- [x] tests added / passed
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [x] whatsnew entry

Problem statement:
ERR: pivot_table when number of levels larger than int32 range
#### Code Sample, a copy-pastable example if possible

```
import pandas as pd
dat = pd.DataFrame({'ind1':list(range(1337600))*2,'ind2':list(range(3040))*2*440,'count':[1]*2*1337600})
dat.pivot_table(index='ind1',columns='ind2',values='count',aggfunc='count')
```

#### Problem description

Above code raises the following error:

```
  File "..\pandas\core\reshape\reshape.py", line 144, in _make_selectors
    mask = np.zeros(np.prod(self.full_shape), dtype=bool)

ValueError: negative dimensions are not allowed
```

np.prod(self.full_shape) appears to be returning a negative value because the number of unique index combinations is larger than the largest int32 value.

If line 144 were changed to the following, the issue could be fixed:
```
mask = np.zeros(np.prod(self.full_shape,dtype=np.int64), dtype=bool)
```

#### Expected Output
1337600 x 3040 dataframe.

#### Output of ``pd.show_versions()``

<details>

INSTALLED VERSIONS
------------------
commit: None
python: 3.6.4.final.0
python-bits: 64
OS: Windows
OS-release: 7
machine: AMD64
processor: Intel64 Family 6 Model 37 Stepping 1, GenuineIntel
byteorder: little
LC_ALL: None
LANG: en
LOCALE: None.None

pandas: 0.22.0
pytest: 3.3.2
pip: 9.0.1
setuptools: 38.4.0
Cython: 0.27.3
numpy: 1.12.1
scipy: 1.0.0
pyarrow: None
xarray: None
IPython: 6.2.1
sphinx: 1.6.6
patsy: 0.5.0
dateutil: 2.6.1
pytz: 2017.3
blosc: None
bottleneck: 1.2.1
tables: 3.4.2
numexpr: 2.6.4
feather: None
matplotlib: 2.1.2
openpyxl: 2.4.10
xlrd: 1.1.0
xlwt: 1.3.0
xlsxwriter: 1.0.2
lxml: 4.1.1
bs4: 4.6.0
html5lib: 1.0.1
sqlalchemy: 1.2.1
pymysql: None
psycopg2: None
jinja2: 2.10
s3fs: None
fastparquet: None
pandas_gbq: None
pandas_datareader: None

</details>

Hints from issue discussion:
you are creating a frame with 4B entries? what are you going to do with that?
I have a dataset with over a million samples and a few thousand features which I'm preprocessing. The raw data is in stacked form at the moment which is what I'm attempting to pivot_table.
~~~python
mask = np.zeros(np.prod(self.full_shape,dtype=np.int64), dtype=bool)
~~~

I suppose we could do this, but this also has a noticeable memory impact (1 byte vs 8 bytes).  Does this patch actually fix your problem?
It does fix the problem, but I do understand the memory impact it could cause.

If this patch has too much of a negative impact on memory usage, I think throwing an error indicting that np.prod will lead to integer overflow when the pivot table is too large would be enough. That would inform the user that they need to reduce the size of the data to resolve the problem since the ValueError that actually got raised made it hard to track down the problem.

Thanks!
I'm more inclined to do error message, as this use case almost rarely shows up.  Feel free to do a PR!
@mklwong I think showing an error message is reasonable here. Note you can actually catch this in the _Unstacker constructor (or possibly earlier)

Commit message: ENH: Raise and catch FloatingPointException due to overflow

* Modify tests to only cover windows platforms

Patch to review:
diff --git a/pandas/core/reshape/pivot.py b/pandas/core/reshape/pivot.py
index 22e591e776a22..611cd350a3e53 100644
--- a/pandas/core/reshape/pivot.py
+++ b/pandas/core/reshape/pivot.py
@@ -81,9 +81,7 @@ def pivot_table(data, values=None, index=None, columns=None, aggfunc='mean',
                 pass
         values = list(values)
 
-    # group by the cartesian product of the grouper
-    # if we have a categorical
-    grouped = data.groupby(keys, observed=False)
+    grouped = data.groupby(keys)
     agged = grouped.agg(aggfunc)
     if dropna and isinstance(agged, ABCDataFrame) and len(agged.columns):
         agged = agged.dropna(how='all')
diff --git a/pandas/core/reshape/reshape.py b/pandas/core/reshape/reshape.py
index 03b77f0e787f0..700440ec4aeef 100644
--- a/pandas/core/reshape/reshape.py
+++ b/pandas/core/reshape/reshape.py
@@ -127,6 +127,16 @@ def __init__(self, values, index, level=-1, value_columns=None,
         self.removed_level = self.new_index_levels.pop(self.level)
         self.removed_level_full = index.levels[self.level]
 
+        num_rows = np.max([index_level.size for index_level
+                           in self.new_index_levels])
+        num_columns = self.removed_level.size
+        with np.errstate(all='raise'):
+            try:
+                num_columns * num_rows
+            except FloatingPointError:
+                raise ValueError('Unstacked DataFrame is too big, '
+                                 'causing int32 overflow')
+
         self._make_sorted_values_labels()
         self._make_selectors()
 
diff --git a/pandas/tests/reshape/test_pivot.py b/pandas/tests/reshape/test_pivot.py
index 1cb036dccf23c..9aa4800597ca7 100644
--- a/pandas/tests/reshape/test_pivot.py
+++ b/pandas/tests/reshape/test_pivot.py
@@ -1,6 +1,7 @@
 # -*- coding: utf-8 -*-
 
 from datetime import datetime, date, timedelta
+import sys
 
 import pytest
 
@@ -1276,6 +1277,18 @@ def test_pivot_string_func_vs_func(self, f, f_numpy):
                                aggfunc=f_numpy)
         tm.assert_frame_equal(result, expected)
 
+    @pytest.mark.slow
+    def test_pivot_number_of_levels_larger_than_int32(self):
+        # GH 20601
+        if sys.platform == 'win32':
+            df = DataFrame({'ind1': np.arange(2 ** 16),
+                            'ind2': np.arange(2 ** 16),
+                            'count': 0})
+
+            with tm.assert_raises_regex(ValueError, 'int32 overflow'):
+                df.pivot_table(index='ind1', columns='ind2',
+                               values='count', aggfunc='count')
+
 
 class TestCrosstab(object):
 
diff --git a/pandas/tests/test_multilevel.py b/pandas/tests/test_multilevel.py
index 2022340926cca..68fa3643e4f18 100644
--- a/pandas/tests/test_multilevel.py
+++ b/pandas/tests/test_multilevel.py
@@ -3,6 +3,8 @@
 from warnings import catch_warnings, simplefilter
 import datetime
 import itertools
+import sys
+
 import pytest
 import pytz
 
@@ -1212,6 +1214,15 @@ def test_unstack_unobserved_keys(self):
         recons = result.stack()
         tm.assert_frame_equal(recons, df)
 
+    @pytest.mark.slow
+    def test_unstack_number_of_levels_larger_than_int32(self):
+        if sys.platform == 'win32':
+            # GH 20601
+            df = DataFrame(np.random.randn(2 ** 16, 2),
+                           index=[np.arange(2 ** 16), np.arange(2 ** 16)])
+            with tm.assert_raises_regex(ValueError, 'int32 overflow'):
+                df.unstack()
+
     def test_stack_order_with_unsorted_levels(self):
         # GH 16323
 


Code review comments:
diff_hunk: @@ -1276,6 +1277,18 @@ def test_pivot_string_func_vs_func(self, f, f_numpy):
                                aggfunc=f_numpy)
         tm.assert_frame_equal(result, expected)
 
+    @pytest.mark.slow
+    def test_pivot_number_of_levels_larger_than_int32(self):
+        # GH 20601
+        if sys.platform == 'win32':
+            df = DataFrame({'ind1': np.arange(2 ** 16),
+                            'ind2': np.arange(2 ** 16),
path: pandas/tests/reshape/test_pivot.py
text: @user1:
it doesn't need to be this big, just something that exceeds int32 (2B) is needed

@author:
Can you explain this further? If I decrease the value to `2 ** 15` I do not get an overflow.

diff_hunk: @@ -127,6 +127,16 @@ def __init__(self, values, index, level=-1, value_columns=None,
         self.removed_level = self.new_index_levels.pop(self.level)
         self.removed_level_full = index.levels[self.level]
 
+        num_rows = np.max([index_level.size for index_level
+                           in self.new_index_levels])
+        num_columns = self.removed_level.size
+        with np.errstate(all='raise'):
path: pandas/core/reshape/reshape.py
text: @user1:
can't you just compare vs np.iinfo('int32').max?

diff_hunk: @@ -1276,6 +1277,18 @@ def test_pivot_string_func_vs_func(self, f, f_numpy):
                                aggfunc=f_numpy)
         tm.assert_frame_equal(result, expected)
 
+    @pytest.mark.slow
+    def test_pivot_number_of_levels_larger_than_int32(self):
+        # GH 20601
+        if sys.platform == 'win32':
path: pandas/tests/reshape/test_pivot.py
text: @user1:
use ``is_platform_windows`` (import from ``pandas.compat``

@user1:
why is this on windows only?

@author:
I don't know 100% percent, but numpy appears to treat int32 differently on Windows than on Unix:
https://stackoverflow.com/questions/36278590/numpy-array-dtype-is-coming-as-int32-by-default-in-a-windows-10-64-bit-machine/36279549

https://github.com/numpy/numpy/issues/8433

On my MacOs environment, the code from the issue works - takes some time but pandas (0.23.4) computes the expected result while my Windows environment encounters the described error. I therefore think, that this is a Windows only issue and we probably should not limit other OS versions by always checking against the int32 upper limit.