pkg/expression/grouping_sets.go — repeated subset construction in grouping-set merge
- Dominant language
- Go
- Stars
- 40.5k
- Forks
- 6.2k
- PR merge metrics
- PR metrics pending
Description
## Enhancement
Locations:
- pkg/expression/grouping_sets.go
Current pattern:
- GroupingSets.Merge() iterates all grouping expressions and calls MergeOne().
- MergeOne() scans existing grouping sets and entries.
- Each SubSetOf() call rebuilds two intset.FastIntSets from expression slices.
Estimated current complexity:
- Roughly O(G * S * E * C) plus repeated allocations.
- G = grouping expressions inserted
- S = existing grouping-set chains scanned
- E = expressions per chain
- C = columns per grouping expression
- In bad cases, this becomes quadratic/cubic-ish planning work with avoidable allocation churn.
Recommended change:
- Cache GroupingExprs.IDSet() once during merge, or introduce an internal merge representation carrying {exprs, idSet}.
- Replace repeated SubSetOf() conversions with set subset checks on precomputed sets.
Estimated after:
- Same merge/search shape, but subset checks become mostly allocation-free.
- Practical cost becomes closer to O(G * S * E) with much lower constants.
Risk:
- Medium. Need to preserve ordering and prefix-merging semantics.
Tests/benchmarks needed:
- Add/extend tests for rollup/cube/grouping-set merge equivalence.
- Add microbenchmark around large grouping sets / repeated columns.
TODO
- The repeated calls to SubSetOf() within Merge()/MergeOne() (pkg/expression/grouping_sets.go:48, pkg/expression/grouping_sets.go:86, pkg/expression/grouping_sets.go:361) rebuild FastIntSet each time, resulting in explicit redundant overhead.
- Cache GroupingExprs.IDSet() within the lifecycle of this merge is reasonable, as the semantics remain unchanged (the set inclusion is still based on UniqueID).
- This is mainly triggered in multiple distinct aggregation candidate paths (pkg/planner/core/task.go:1695), which is a planning-phase optimization, not an execution-phase hotspot; therefore, it is "feasible and correct," but the overall benefit is usually not as significant as executor hotspot optimization. - If you want to implement it locally, prioritize using SubSetOf caching, and then use NeedCloneColumn in a single pass.
Contributor guide
Assessment
This issue has not been assessed yet.