GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — [SQL] Dataflow analysis to compute for each stream whether it's a (multi)set by mihaibudiu · Pull Request #7725 · feldera/feldera

Conversation

@mihaibudiu

@mihaibudiu mihaibudiu commented Oct 29, 2026

Copy link
Copy Markdown
Contributor

Linked Issue

Fixes #7023
Fixes #7706

Previously each operator used to carry a bit indicating whether it expects the output (or the integrated output for an incremental circuit) to be a set or a multiset. This is used to remove some unneeded DISTINCT calls. This PR removes the bit from the operator and adds a dataflow analysis which recomputes the value of the bit. This is better because the bit cannot become stale by mistake: it is only valid immediately after the analysis has run.

The analysis is a bit more precise now too: it tries to prove that some functions are injective, if they can preserve sets, and recursive circuits insert DISTINCT calls automatically; now we use this information (although I think the compiler should insert the distincts, not the circuit builder).

Checklist

  • Unit tests added/updated

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
@mihaibudiu
mihaibudiu force-pushed the issue7023 branch from f0559d8 to be7aeed Compare October 29, 2026 23:21
@mihaibudiu
mihaibudiu requested a review from ryzhyk October 29, 2026 23:21
ryzhyk
ryzhyk approved these changes Oct 29, 2026
View reviewed changes
@mihaibudiu
[SQL] Dataflow analysis to compute for each stream whether it's a (mu…
d29940c
…lti)set

Signed-off-by: Mihai Budiu <[email protected]>
@mihaibudiu
mihaibudiu force-pushed the issue7023 branch from be7aeed to d29940c Compare October 30, 2026 00:01
mythical-fred-oss[bot]
mythical-fred-oss Bot reviewed Oct 30, 2026
View reviewed changes
Comment thread ...-compiler/src/main/java/org/dbsp/sqlCompiler/compiler/visitors/outer/merkle/MerkleOuter.java
// That code calls mark_distinct() when the output is a set.
// The local hash does not include the inputs, so two operators with
// equal functions and input types can differ only in this flag.
this.property("isMultiset");

@mythical-fred-oss mythical-fred-oss Bot Oct 30, 2026

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

pitfall (medium): persistent ids change on upgrade. This bit is part of the global hash. The more precise analysis flips it for some operators, and the change carries into every downstream id. metadataTests-generateDF.json shows it: a map (s4) becomes a set, so the stateful integrate (s5), the atomic_sum and the sink all get new persistent_ids. So an existing pipeline whose program has this shape (e.g. a projection over a GROUP BY) will see those operators as changed after a compiler upgrade, and has to bootstrap them or fail to resume from its checkpoint. Please say this in the PR or release notes. If the upgrade should be transparent, gate it behind a state-version bump.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
mythical-fred-oss[bot]
mythical-fred-oss Bot reviewed Oct 30, 2026
View reviewed changes
Comment thread ...mpiler/src/main/java/org/dbsp/sqlCompiler/compiler/visitors/outer/keys/MultisetAnalysis.java
}

@Override
public void postorder(DBSPNestedOperator operator) {

@mythical-fred-oss mythical-fred-oss Bot Oct 30, 2026

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

bug (medium): outputs with a null internalOutputs entry are never stored. The operator is still added to analyzed, so a later isMultiset(nested.getOutput(i)) on such a port won't re-analyze it. Instead Utilities.getExists throws an internal error. Store a conservative true for those ports, or assert that nothing ever reads them.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
@mythical-fred-oss

mythical-fred-oss Bot commented Oct 30, 2026

Copy link
Copy Markdown
Contributor

What I ran: ./build.sh, then mvn test -pl SQL-compiler for MultisetAnalysisTests, OtherTests, MetadataTests, EquivalenceTests, ShareIndexesTests, TopKUnusedFieldsTests and DBSPWindowOperatorTests. All 159 tests passed (1 skipped).

QA tests I added locally (all pass, including the Rust run):

Case Result
SELECT DISTINCT a FROM (SELECT DISTINCT a,b ...) with rows (1,1),(1,2) 1 with weight 1 ✅
LEFT JOIN of sets whose projection drops columns, right-side NULL padding weights all 1 ✅
Analysis results: column swap → set; projection, a+1 → multiset (conservative) ✅ CAST(a AS BIGINT) widening → multiset (the lossless-cast path did not prove it injective here; a missed optimization, not a bug)

missing (medium): test coverage. MultisetAnalysis has about 60 operator rules, but the PR tests only 4 of them directly: index over a keyed table, deindex with an empty key, SAFE_CAST, and recursion. There are no direct tests for the rules that now drive mark_distinct() in generated code:

  • join / left join / star join with map
  • Lag, Rank, RowNumber, IndexedTopK
  • Hop / Window
  • ChainOperator
  • unsafe narrowing integer casts, which are treated as injective because they raise an error on overflow

If one of these rules is wrong, mark_distinct() lands on a multiset, and the runtime can silently return wrong results. That is worth an end-to-end stepWeightOne test for each rule. The two QA tests above can serve as templates:

@Test
public void qaProjectionOverSet() {
    var ccs = this.getCCS("""
            CREATE TABLE t (a INT, b INT);
            CREATE VIEW v AS SELECT DISTINCT a FROM (SELECT DISTINCT a, b FROM t);""");
    ccs.stepWeightOne("INSERT INTO t VALUES (1, 1), (1, 2);", """
             a
            ---
             1""");
}

missing (medium): breaking change not called out. Persistent ids change for existing programs; details are in the inline comment. The PR description doesn't mention it, nor does it describe any manual testing.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@mihaibudiu
mihaibudiu added this pull request to the merge queue Oct 30, 2026
Merged via the queue into main with commit 7bfc610 Oct 30, 2026
1 check passed

Uh oh!

There was an error while loading. Please reload this page.

@mihaibudiu
mihaibudiu deleted the issue7023 branch October 30, 2026 09:09
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@mythical-fred-oss mythical-fred-oss[bot] mythical-fred-oss[bot] left review comments
@ryzhyk ryzhyk ryzhyk approved these changes

Uh oh!

There was an error while loading. Please reload this page.

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

[SQL] map_index that drops a table's primary key is marked distinct [SQL] Make the "is multiset" flag the result of a dynamic analysis

Uh oh!

There was an error while loading. Please reload this page.

2 participants

@mihaibudiu @ryzhyk
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.