pingcap / pingcap/tidb

pkg/expression/grouping_sets.go — repeated subset construction in grouping-set merge

Open
#68,522 0 comments 0 reactions 1 assignee Claimed by @hawkingrei View on GitHub
type/enhancement
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.