REF: Compute complete result_index upfront in groupby
State: closed

- [x] closes #55919
- [x] closes #52848
- [x] closes #36698
- [x] closes #43891
- [x] closes #49980
- [x] closes #56966
- [x] closes #56851 
- [x] [Tests added and passed](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#writing-tests) if fixing a bug or adding a new feature
- [x] All [code checks passed](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#pre-commit).
- [x] Added [type annotations](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#type-hints) to new arguments/methods/functions.
- [x] Added an entry in the latest `doc/source/whatsnew/vX.X.X.rst` file if fixing a bug or adding a new feature.

~Just a PoC at this point, need to try to move behavior changes out of here as much as possible.~

The main change this makes is it moves the computation of unobserved groups upfront. Currently, we only include unobserved groups upfront if there is a single grouping (e.g. `df.groupby('a')`) but not two or more (e.g. `df.groupby(['a', 'b'])`). When there are two or more, we go through the groupby computations with only observed groups, and then tack on the unobserved groups at the end. By always including unobserved groups upfront, we can simplify the logic in the groupby code. Having unobserved groups sometimes included and sometimes not included upfront is also a footgun.

In order to make this change, I found I needed to rework a bit of how NA values are handled in `Grouping._codes_and_uniques`. This in turn fixed some NA bugs.

This PR fixes a number of issues that stem from this (shown in the test changes)

 - Unobserved groups are not included in `groupby.apply` if there is more than one grouping
 - Unobserved groups do not appear in `groubpy.groups`
 - When there are multiple groupings, `len(df.groupby(..., dropna=True))` counts groups that have NA values
 - When there are multiple groupings, `df.groupby(..., dropna=True).groups` has groups that have NA values
 - The value of `.all` for empty groups was `np.nan` but should be `True`
 - The value of `.any` for empty groups was `np.nan` but should be `False`
 - The value of `.prod` for empty groups was `np.nan` but should be `1`

In addition, it allows us to remove various similar objects throughout groupby:

 - `BaseGrouper.group_keys_seq`
 - `BaseGrouper.reconstructed_codes`
 - `Grouping.group_index`
 - `Grouping.result_index`
 - `Grouping.group_arraylike`
 - `BinGrouper.reconstructed_codes`

and a few methods

 - `GroupBy._reindex_output`
 - `BaseGrouper._sort_idx`
 - `BaseGrouper._get_compressed_codes`

But it does add `BaseGrouper.result_index_and_codes`. This computes the (aggregated) result index that takes into account `dropna` and `observed`, along with the codes for the groups themselves.

ASVs; no performance regressions (with the standard 10% cutoff) other than groupby transform operations with multiple categorical groupings.

<details>

```
| Change   | Before [2b67593b] <test>   | After [e285742a] <gb_observed_pre>   |   Ratio | Benchmark (Parameter)                                                                                              |
|----------|----------------------------|--------------------------------------|---------|--------------------------------------------------------------------------------------------------------------------|
| +        | 308±4μs                    | 1.25±0ms                             |    4.08 | groupby.MultipleCategories.time_groupby_transform                                                                  |
| -        | 5.10±0.04ms                | 4.61±0.06ms                          |    0.91 | groupby.Apply.time_scalar_function_multi_col(5)                                                                    |
| -        | 239±4μs                    | 216±0.2μs                            |    0.9  | groupby.Categories.time_groupby_sort(False)                                                                        |
| -        | 60.1±2μs                   | 53.8±0.4μs                           |    0.9  | groupby.GroupByMethods.time_dtype_as_field('float', 'size', 'direct', 1, 'cython')                                 |
| -        | 241±5μs                    | 215±1μs                              |    0.89 | groupby.Categories.time_groupby_ordered_sort(False)                                                                |
| -        | 556±7μs                    | 488±60μs                             |    0.88 | arithmetic.IntFrameWithScalar.time_frame_op_with_scalar(<class 'numpy.int64'>, 5.0, <built-in function mul>)       |
| -        | 235±5μs                    | 205±2μs                              |    0.87 | groupby.Categories.time_groupby_extra_cat_sort(False)                                                              |
| -        | 419±8μs                    | 356±10μs                             |    0.85 | arithmetic.IntFrameWithScalar.time_frame_op_with_scalar(<class 'numpy.float64'>, 2, <built-in function le>)        |
| -        | 549±10μs                   | 461±50μs                             |    0.84 | arithmetic.IntFrameWithScalar.time_frame_op_with_scalar(<class 'numpy.float64'>, 3.0, <built-in function truediv>) |
| -        | 21.7±0.7μs                 | 18.1±0.06μs                          |    0.83 | groupby.GroupByMethods.time_dtype_as_field('uint', 'count', 'direct', 1, 'cython')                                 |
| -        | 22.5±0.3μs                 | 18.6±0.2μs                           |    0.83 | groupby.GroupByMethods.time_dtype_as_group('float', 'count', 'direct', 1, 'cython')                                |
| -        | 22.2±0.2μs                 | 18.4±0.8μs                           |    0.83 | groupby.GroupByMethods.time_dtype_as_group('uint', 'count', 'direct', 1, 'cython')                                 |
| -        | 22.3±0.8μs                 | 18.3±0.1μs                           |    0.82 | groupby.GroupByMethods.time_dtype_as_field('float', 'count', 'direct', 1, 'cython')                                |
| -        | 21.6±0.9μs                 | 17.8±0.3μs                           |    0.82 | groupby.GroupByMethods.time_dtype_as_field('int16', 'count', 'direct', 1, 'cython')                                |
| -        | 22.0±0.6μs                 | 18.1±0.3μs                           |    0.82 | groupby.GroupByMethods.time_dtype_as_group('int', 'count', 'direct', 1, 'cython')                                  |
| -        | 21.9±0.7μs                 | 17.8±0.3μs                           |    0.81 | groupby.GroupByMethods.time_dtype_as_field('int', 'count', 'direct', 1, 'cython')                                  |
| -        | 22.0±0.2μs                 | 17.9±0.07μs                          |    0.81 | groupby.GroupByMethods.time_dtype_as_group('int16', 'count', 'direct', 1, 'cython')                                |
| -        | 21.6±0.1μs                 | 17.0±0.06μs                          |    0.79 | groupby.GroupByMethods.time_dtype_as_group('object', 'count', 'direct', 1, 'cython')                               |
| -        | 520±50μs                   | 370±30μs                             |    0.71 | arithmetic.IntFrameWithScalar.time_frame_op_with_scalar(<class 'numpy.int64'>, 2, <built-in function sub>)         |
| -        | 13.7±1ms                   | 1.80±0ms                             |    0.13 | groupby.MultipleCategories.time_groupby_nosort                                                                     |
| -        | 15.8±2ms                   | 1.73±0ms                             |    0.11 | groupby.MultipleCategories.time_groupby_extra_cat_nosort                                                           |
| -        | 13.7±0.2ms                 | 1.57±0.01ms                          |    0.11 | groupby.MultipleCategories.time_groupby_ordered_nosort                                                             |
| -        | 33.6±0.4ms                 | 1.40±0ms                             |    0.04 | groupby.MultipleCategories.time_groupby_sort                                                                       |
| -        | 35.5±1ms                   | 1.23±0ms                             |    0.03 | groupby.MultipleCategories.time_groupby_extra_cat_sort                                                             |
| -        | 33.3±0.8ms                 | 1.15±0ms                             |    0.03 | groupby.MultipleCategories.time_groupby_ordered_sort                                                               |
```

</details>

I haven't verified this, but I believe this would also make #55261 trivial to implement just by changing a few lines of `result_index_and_ids`

Labels:
name: Bug
name: Refactor
description: Internal refactoring of code
name: Groupby
name: Categorical
description: Categorical Data Type

Comments:
@jbrockmendel @WillAyd @mroeschke - I think this is ready for review but not merging. If I can get a thumbs up that this is looking good enough, I will put up a PR to deprecate the attributes that are being removed here for 2.2. Then this will be mergeable for 3.0.
I think the approach makes sense overall 👍. Does this interact with `groupby.apply` given the resulting index could depend on the UDF?

Also this this happen to address https://github.com/pandas-dev/pandas/issues/35202 by any chance or is that a separate bug? IIRC it was related to how calculating the groupings via Categorical would see an NA value as missing instead of an actual factor
> Does this interact with `groupby.apply` given the resulting index could depend on the UDF?

Yes - when there are multiple groupings. Currently on main if there is a single grouping with unobserved groups and `observed=False`, the empty groups will be passed to the UDF. However when there are multiple groupings in this scenario, they will not be passed to the UDF but included in the result after (necessarily with the value nan). This PR resolves that inconsistency (and is tested for in `test_seriesgroupby_observed_false_or_none`)

<details>

```
df = pd.DataFrame(
    {
        'a1': pd.Categorical([1, 1, 2], categories=[1, 2, 3]),
        'a2': pd.Categorical([1, 1, 2], categories=[1, 2, 3]),
        'b': [4, 5, 6],
    }
)
gb = df.groupby(['a1', 'a2'], observed=False)
print(gb.apply(lambda x: x.sum()))

# main
#          b
# a1 a2
# 1  1   9.0
#    2   NaN
#    3   NaN
# 2  1   NaN
#    2   6.0
#    3   NaN
# 3  1   NaN
#    2   NaN
#    3   NaN

# PR
#        b
# a1 a2
# 1  1   9
#    2   0
#    3   0
# 2  1   0
#    2   6
#    3   0
# 3  1   0
#    2   0
#    3   0
```

</details>

> Also this this happen to address #35202 by any chance or is that a separate bug?

That's a separate bug. Early on the decision was made to have it so that categoricals only have NA values encoded as `-1` and to not allow them to appear in the categories with corresponding non-negative codes. While this is certainly reasonable, the groupby `dropna=False` implementation behaves a lot like the Categorical implementation but requires NA values to have non-negative codes. If we allow NA values in Categorical categories (which might not be a good idea - not sure), then likely we could use a lot more Categorical code in groupby. Doing this would also resolve this bug.

For this particular bug however, we can look into alternative implementations that don't go utilize Categorical code paths.
Its kind of hard to tell what is a refactor vs a bugfix vs an API change.  can any of this be split out into preliminaries?  in general im supportive of the approach here
> Its kind of hard to tell what is a refactor vs a bugfix vs an API change. can any of this be split out into preliminaries?

I intended for the only public API change to be the removal of deprecated attributes, but I see I missed the change to `grouper.group_info` (deprecating `grouper` itself would handle this). 

For this PR, I could leave objects like `group_keys_seq` and methods like `_reindex_output` in the code but remove all their usages, and then have a followup PR to remove their usage if this would be helpful. Because the deprecated attributes involve computation, I think this would involve a performance regression until they are removed. And this could be extended a bit further - I can leave usage of some of the deprecated attributes in place and replace their usage in a followup to reduce the diff as much as possible here. Again, this would involve performance regressions until it's all carried out.

I was hopeful the change to how `dropna` is handled with categoricals in `_codes_and_uniques` could be siphoned off into a precursor, but found it really depended on using `result_index_and_ids`. Thus for the bugfixes, they occurred naturally by moving the computation of unobserved groups up front. So they would require independent fixes and in most cases I don't see a feasible independent way. The only exception to this is `test_series_groupby_on_2_categoricals_unobserved_zeroes_or_nans` - we can have `any`, `all`, and `prod` produce the values `False`, `True`, and `1` on unobserved groups by essentially replicating the [not-so-great-pattern that sum uses](https://github.com/pandas-dev/pandas/blob/cbe1b321d928bb00ab9809f109ab483db2bb6b2d/pandas/core/groupby/groupby.py#L3129-L3132).


This pull request is stale because it has been open for thirty days with no activity. Please [update](https://pandas.pydata.org/pandas-docs/stable/development/contributing.html#updating-your-pull-request) and respond to this comment if you're still interested in working on this.
@jbrockmendel @mroeschke - this is now ready
Does this happen to fix https://github.com/pandas-dev/pandas/issues/35202
> Does this happen to fix #35202

No, see the bottom half of https://github.com/pandas-dev/pandas/pull/55738#issuecomment-1819790368.


Thanks @rhshadrach 
@rhshadrach is the following change in behaviour intentional?


```python
df = pd.DataFrame(
    {
        "key_cat": pd.Categorical(["a", "a", "b", "b"]),
        "key_noncat": [1, 1, 1, 2],
        "values": [1.0, 2.0, 3.0, 4.0],
    }
)
df.groupby(["key_cat", "key_noncat"], observed=False)["values"].agg(lambda x: x.sum())
```

Using released pandas, this injected NaNs for the unobserved values:

```python
# using pandas 2.2.0
>>> df.groupby(["key_cat", "key_noncat"], observed=False)["values"].agg(lambda x: x.sum())
key_cat  key_noncat
a        1             3.0
         2             NaN
b        1             3.0
         2             4.0
Name: values, dtype: float64
```

versus after (I assume) this PR on pandas main:

```python
# using pandas main
>>> df.groupby(["key_cat", "key_noncat"], observed=False)["values"].agg(lambda x: x.sum())
key_cat  key_noncat
a        1             3.0
         2             0.0
b        1             3.0
         2             4.0
Name: values, dtype: float64
```

The reason this now gives a 0 is because this actually calls the UDF on the empty group, and the sum of an empty Series is 0 (while before, the UDF was never called for the unobserved group).

I don't think I have a strong opinion on what the behaviour _should_ be, but if it is intentional, this probably warrants a whatsnew note (it was confusing to debug my failing tests).

Apart of the different result, this also means that your UDF _needs_ to be able to handle empty input (before, the UDF essentially never got empty input for those cases, I think?)

I also see that your top post has a long list of changes / fixes:

> This PR fixes a number of issues that stem from this (shown in the test changes)
>
>* ...

I think those are mostly added to the whatsnew, but it might be clearer to have a separate section explaining the general change (unobserved groups are now properly included through all APIs), and then list some of the consequence of it (instead of those bullet points that will become part of a large list of bullet points in the groupby section)

Thanks @jorisvandenbossche - indeed this is intentional; xref #36698. I'll ~add a whatsnew note~ try to make this a notable bug fix section in a followup.