Skip to content

[SQL] Optimization to share expensive expressions across sibling map operators - #6831

Merged
mihaibudiu merged 3 commits into
feldera:mainfrom
mihaibudiu:issue6817
Aug 11, 2026
Merged

[SQL] Optimization to share expensive expressions across sibling map operators#6831
mihaibudiu merged 3 commits into
feldera:mainfrom
mihaibudiu:issue6817

Conversation

@mihaibudiu

Copy link
Copy Markdown
Contributor

Fixes #6817

Checklist

  • Unit tests added/updated

There are 3 commits, two of which do some janitorial stuff.
The third one implements an optimization that works when you have multiple views that may invoke the same expensive function in a map operator. Something like:

CREATE VIEW V1 AS SELECT f(expensive(x)) FROM T;
CREATE VIEW V2 AS SELECT g(expensive(x)) FROM T;

This will be compiled into something equivalent to:

CREATE LOCAL VIEW L AS SELECT expensive(x) AS e FROM T;
CREATE VIEW V1 AS SELECT f(e) FROM L;
CREATE VIEW V2 AS SELECT g(e) FROM L;

For some customer programs this can produce significant savings in computation cost, even thought the optimized operators are all linear.

@mythical-fred mythical-fred left a comment

Copy link
Copy Markdown

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

APPROVE.

New FuseExpensiveMaps pass hoists shared expensive subexpressions across sibling DBSPMapOperators that share an input port. Groups by input, collects minimal expensive subexpressions per closure body (Expensive predicate + closed-over-parameter check), fingerprints via CanonicalForm for fast fingerprint-equality union-find, and rewrites each cluster into one fused map (union of distinct columns) followed by one projection per original member. Single-map "clusters" are still fused when the map itself duplicates an expensive expression (hasDuplicatedExpensiveField) — that path is exactly what testWithinSingleMap exercises.

Correctness sanity that I walked through:

  • equivalent(left, newLeft, right, newRight) compares newLeft.closure(left.param()) vs newRight.closure(right.param()), which normalises via EquivalenceContext alpha-equivalence. Since maps in a group share their input port and therefore their row type, using first.param().getType().var() as the fresh variable in Fuse.fuse and calling member.function().call(var).reduce() is type-safe.
  • ContainsNow(compiler, /*perExpression*/ true) resets found on each startVisit, so reusing one instance across all map operators in FindFusableMaps.postorder is fine — good detail, easy to get wrong.
  • CollectExpensiveExpressions.closed() correctly refuses expressions that reference variables declared outside the expression and not equal to the closure parameter — necessary because expensive expressions get hoisted to the fused map's body. The ResolveReferences fix to preorder(DBSPLetExpression) (declaring the let variable) is a prerequisite and is included in this PR.
  • The postorder handshake in Fuse.postorder (skip if already in remap, else fuse the whole cluster on first sight and register projections for every member) means members visited later in the traversal find themselves already mapped — clean.
  • shouldInlineComposition guard on DBSPClosureExpression prevents a later projection-fusion pass from re-inlining a duplicated-expensive-field projection and undoing this work. Nice.

ConstantViews warning pass and the frontend.calciteCompiler.optimizer logger scope are unrelated janitorial additions and look harmless.

Test coverage is thorough: cross-view sharing, UNION ALL with expensive-inside-larger-expensive, within-single-map dedup (with CountLazy == 0 assertion catching that CSE didn't have to step in), and VARIANT-column sharing. CountCalls asserting exactly 1 call is a strong, easy-to-read invariant.

Non-blocking nit: FuseExpensiveMapsTests.testVariantSharing opens with showFinalVerbose(4);. That's a global Logger.INSTANCE.setLoggingLevel(DBSPCompiler.class, 4) side-effect that persists for the rest of the JVM/test-class run — same debug-leftover pattern I flagged on #6824 (showFinal() in AntiJoinDistinctTests.testSegment). Drop the line before merging.

Style micro-nit (not blocking): FindFusableMaps.find is a plain iterative walk with no path compression / union-by-rank. Groups per input port are typically tiny so it doesn't matter — just noting it in case a future pathological case shows up.

Commits are signed-off, no AI-attribution trailers.

@lalithsuresh

Copy link
Copy Markdown
Contributor

@mihaibudiu this could be done for filters too right?

@mihaibudiu

Copy link
Copy Markdown
Contributor Author

@mihaibudiu this could be done for filters too right?

that was done in #6815

@mythical-fred mythical-fred left a comment

Copy link
Copy Markdown

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Rebased tip ab855bbc95 over 42639f04. Delta vs prior approved tip is a straight rebase — same 8 files, same semantics (FuseExpensiveMaps + ConstantViews passes, ResolveReferences let-var declaration, shouldInlineComposition guard, ContainsNow(perExpression=true)). Prior nits still stand (showFinalVerbose(4) debug leftover in testVariantSharing; no path-compression in the tiny union-find — both non-blocking). Re-approving on the current base.

@mihaibudiu
mihaibudiu added this pull request to the merge queue Aug 10, 2026
@github-merge-queue
github-merge-queue Bot removed this pull request from the merge queue due to failed status checks Aug 10, 2026
Signed-off-by: Mihai Budiu <mbudiu@feldera.com>
Signed-off-by: Mihai Budiu <mbudiu@feldera.com>
…operators

Signed-off-by: Mihai Budiu <mbudiu@feldera.com>
@mihaibudiu
mihaibudiu enabled auto-merge August 10, 2026 21:22
@mihaibudiu
mihaibudiu added this pull request to the merge queue Aug 10, 2026
@github-merge-queue
github-merge-queue Bot removed this pull request from the merge queue due to failed status checks Aug 10, 2026
@mihaibudiu
mihaibudiu added this pull request to the merge queue Aug 10, 2026
@github-merge-queue
github-merge-queue Bot removed this pull request from the merge queue due to failed status checks Aug 10, 2026
@mihaibudiu
mihaibudiu added this pull request to the merge queue Aug 10, 2026
Merged via the queue into feldera:main with commit 9f62637 Aug 11, 2026
1 check passed
@mihaibudiu
mihaibudiu deleted the issue6817 branch August 11, 2026 02:12
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

[SQL] Optimize multiple map operators applied to the same source by finding common sub-expressions

3 participants