← 输入框|github.com|刷新
Skip to content

[SQL] Improvements related to CSE - #7864

Merged
mihaibudiu merged 5 commits into
mainfrom
issue7596
Nov 6, 2026
Merged

mihaibudiu merged 5 commits into
mainfrom
issue7596

Conversation

@mihaibudiu

Copy link
Copy Markdown
Contributor

Linked Issue

Fixes #7596

Describe Manual Test Plan

There are 5 commits; the main one is the one related to ValueNumbering (inner CSE), which fixes some potential bugs. The other commits are small code quality improvements and tests

Checklist

  • Unit tests added/updated

Signed-off-by: Mihai Budiu <mbudiu@feldera.com>
@mythical-fred-oss

Copy link
Copy Markdown
Contributor

What I ran

Command Result
./build.sh ✅
mvn test -Dtest=EquivalenceTests (the PR's tests + 3 of mine) ✅ 19/19
mvn test -Dtest=PersistentIdTests,FuseExpensiveMapsTests,MetadataTests (these compile and run Rust) ✅ 93/93

I found no correctness problems. The value-numbering, closure-scoping, assignment-placement and static-replacement logic all hold up for the cases I traced. The gates pass: the PR adds unit tests, it has no user-visible or breaking change, and it adds no dependencies.

missing (medium): cases the PR's tests do not cover. I wrote tests for all three and they pass:

  1. Nested blocks. |t| { let a = t.0; { let c = t.1; Tup((a+c)*(a+c), f(a+1), g(a+1)) } }: the variable for a+c must go after let c in the inner block, and the variable for a+1 must go to the outer block. This is the scoping case the lastDependency rewrite exists for, and testCSEAfterLastLet only uses a flat block.
  2. A mutable borrow of a field, g(&mut acc.0). The PR only tests a borrow of the whole variable, &mut acc, so it never exercises the field-stripping in baseDeclaration.
  3. The DBSPLetStatement cell path in ImplementStatics (see the inline comment).
@Test
public void testCSENestedBlocks() {
    DBSPCompiler compiler = new DBSPCompiler(new CompilerOptions());
    DBSPVariablePath t = b.refVar(b.tup(b.i32n(), b.i32n()));
    DBSPLetStatement a = new DBSPLetStatement("a", b.field(t, 0));
    DBSPLetStatement c = new DBSPLetStatement("c", b.field(t, 1));
    DBSPExpression prod = b.binary(b.i32n(), DBSPOpcode.MUL,
            b.add(a.getVarReference(), c.getVarReference()),
            b.add(a.getVarReference(), c.getVarReference()));
    DBSPExpression inner = new DBSPBlockExpression(Linq.list(c), b.tuple(prod,
            b.call("f", b.add(a.getVarReference(), b.lit(1, true))),
            b.call("g", b.add(a.getVarReference(), b.lit(1, true)))));
    IDBSPInnerNode result = cse(compiler, new DBSPBlockExpression(Linq.list(a), inner).closure(t));
    assertCseVariables(compiler, result, 2);
    assertResolves(compiler, result);
}

@Test
public void testCSEMutableFieldBorrow() {
    DBSPCompiler compiler = new DBSPCompiler(new CompilerOptions());
    DBSPVariablePath acc = b.tup(b.i32n()).var();
    DBSPClosureExpression closure = b.tuple(
            b.call("f", acc.field(0)),
            b.call("g", acc.field(0).borrow(true)),
            b.call("f", acc.field(0))).closure(acc);
    assertCseVariables(compiler, cse(compiler, closure), 0);
}

Otherwise LGTM.

- Insert each CSE variable after the last let statement that it depends on.
- Copy a subtree that two closures share, so that each closure gets its own translation.
- Include the result type in the representation of unary expressions and tuples.
- Put delimiters around expression ids in value numbering representations.
- Count each user that has no value number as a separate user.
- Include the generic arguments in the representation of paths.
- Give no value number to an expression that reads a mutable variable.

Fixes #7596

Signed-off-by: Mihai Budiu <mbudiu@feldera.com>
Signed-off-by: Mihai Budiu <mbudiu@feldera.com>
Signed-off-by: Mihai Budiu <mbudiu@feldera.com>
Signed-off-by: Mihai Budiu <mbudiu@feldera.com>
@mihaibudiu
mihaibudiu added this pull request to the merge queue Nov 6, 2026
Merged via the queue into main with commit 8b7e6e9 Nov 6, 2026
1 check passed
@mihaibudiu
mihaibudiu deleted the issue7596 branch November 6, 2026 06:17
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] Audit the value numbering pass

2 participants