opt: reorder GroupBy and Join operators

[andy-kimball]

Implement the GroupBy reordering rules in sections 3.1 and 3.2 of this paper. These sections show how to reorder GroupBy with respect to inner and outer joins.

We should consider two sets of rules:

Normalization: the normal form should either always pull GroupBy operators above joins, or else push them down. I suspect pulling them up would result in fewer transformations. The reason to do this normalization is to try and group together joins with one another. This makes it more likely that the optimizer can remove unnecessary joins. Also, when we do more sophisticated join ordering analysis, we want joins grouped together.

Exploration: from an execution speed point of view, sometimes it's better to join and then group, and sometimes it's better to group and then join. We need the coster to examine both options, and select the option with the lower estimated cost.

Jira issue: CRDB-4417

[RaduBerinde]

See https://github.com/cockroachdb/cockroach/issues/54597 for a concrete case.

[jrote1]

@RaduBerinde is there any timeline to when this issue will be fixed?

[RaduBerinde]

It is not on our roadmap for the next major release, so I would say the release in fall 2021 at the earliest..

[jrote1]

I would be keen to look into this, not sure how much help I will be though. Is there any pointers that you could give me? Similar historical PRs etc?

[RaduBerinde]

I'd say the places to start are:

• the paper linked in the description, to understand the details of the transformations
• the general overview of how the optimizer works https://github.com/cockroachdb/cockroach/blob/master/pkg/sql/opt/doc.go
• understanding how some existing exploration rules work: https://github.com/cockroachdb/cockroach/blob/master/pkg/sql/opt/xform/rules/join.opt and https://github.com/cockroachdb/cockroach/blob/master/pkg/sql/opt/xform/custom_funcs.go

Thank you!

[nehageorge]

The requirements of this issue have changed. See https://github.com/cockroachdb/cockroach/pull/70988#issuecomment-932344330.

[remysucre]

We have encountered similar issues in nearly all projects using equality saturation, because almost all languages contain arithmetics and have rules for associativity, commutativity, and distributivity. Applying the rules until fix point (equivalent to growing the memo until it stops changing) will suffer from exponential explosion. Our solution is to timeout after a number of rule applications, while scheduling each rule so that no one dominates. SQL Server takes a similar approach, using timeouts and stages. So to implement this issue, one solution is to do timeout and scheduling for the rewrite rules, then run the DP join reordering at the end. This does not require implementing the new "groupjoin" operator described in the paper linked from the comment above.

Theoretically, the optimal way to solve this is Functional Aggregate Queries (paper, slides). The paper looks scary but the main ideas are rather simple (variable elimination, indicator projection). Still, it would require major effort by a highly experienced team to implement. Hung and Mahmoud are the people behind relationalAI. It's possible that FAQ is related to the paper on groupjoins.

[nehageorge]

Removing my assignment as I will no longer be working on this.

[github-actions[bot]]

We have marked this issue as stale because it has been inactive for 18 months. If this issue is still relevant, removing the stale label or adding a comment will keep it active. Otherwise, we'll close it in 10 days to keep the issue queue tidy. Thank you for your contribution to CockroachDB!

[andy-kimball]

Still relevant.