[SQL] Compiler analysis to detect potentially "unbounded" state - #6714
Conversation
| @@ -0,0 +1,58 @@ | |||
| package org.dbsp.sqlCompiler.compiler.visitors.outer; | |||
There was a problem hiding this comment.
This class used to be nested inside another one, it is unchanged otherwise.
mythical-fred
left a comment
There was a problem hiding this comment.
Analysis is currently dormant (log-only via -TFindUnboundedState=1) and the classifier looks generally sound. A few observations inline; nothing blocking.
| super.postorder(node); | ||
| } | ||
|
|
||
| @Override |
There was a problem hiding this comment.
A DBSPWindowOperator with lowerUnbounded == true but whose inputs happen to be bounded currently falls through super.postorder(node) → postorder(DBSPOperator), which computes an empty unbounded list (no inputs are unbounded) and therefore marks nothing. If a (-inf, upper] window is meant to be flagged unconditionally when it's outside a recursive block — as the comment on lowerUnbounded suggests — this override probably needs to markUnbounded(node, <all inputs>) explicitly rather than delegate to the generic path. As-is, this is a potential false negative.
| unbounded.add(input); | ||
| } | ||
| if (node.inputs.isEmpty()) | ||
| // Stateful non-GCed input operator | ||
| this.markUnbounded(node, unbounded); | ||
| if (!unbounded.isEmpty()) | ||
| this.markUnbounded(node, unbounded); |
There was a problem hiding this comment.
Semantically this is fine (the two branches are disjoint), but the shape is a bit surprising: two ifs in a row where the second is an unrelated condition, and the first calls markUnbounded(node, unbounded) with a guaranteed-empty list (since inputs.isEmpty()). Consider else if for clarity, and passing a more informative marker for the "stateful zero-input source" case — the empty unboundedInputs list currently makes that record indistinguishable from a stateful operator whose inputs all happen to be bounded.
| this.add(findBounded); | ||
| // Second run for recursive circuits | ||
| this.add(findBounded); |
There was a problem hiding this comment.
Adding the same findBounded instance twice as a fixed-point substitute works for shallow recursion but is not guaranteed to reach a fixed point for arbitrarily nested DBSPNestedOperators — each NestedOperator layer effectively needs one extra pass to propagate boundedness through the view-declaration → nested-output plumbing. Consider iterating until bounded.size() stops changing (bounded by circuit size), or documenting the assumption that recursion depth is 1.
| this.unbounded.clear(); | ||
| return super.apply(circuit); | ||
| } | ||
|
|
There was a problem hiding this comment.
Linear scan over gcedStreams per operator; on large circuits this becomes O(#ops × #gced). A Set<DBSPOperator> populated in FindGCedStreams, or a precomputed operator → hasGCedOutput map, would make this O(1).
| * | ||
| * <p>The analysis computes two properties: | ||
| * <ul> | ||
| * <li>"bounded", a property of streams: the integral of |
There was a problem hiding this comment.
Since the analysis has no consumer yet and doesn't affect codegen, no end-to-end test is needed — but a small unit test that pins the current set of UnboundedOperators for a few representative SQL programs (a plain aggregate, a windowed aggregate, a recursive view, a temporal filter) would make future refinements safer to land. The commit message itself flags "may need to be refined", which is exactly when a golden set of expectations pays off.
|
PR-description nit (not code): "Most operators produce finite outputs it all inputs are finite" — should be "if all inputs are finite". |
|
The test which motivated this work can be paired up nicely with the "soft-deletes" feature #6702 |
|
|
||
| public FindSourcePositions(DBSPCompiler compiler, boolean reset) { | ||
| super(compiler); | ||
| this.positions = new HashSet<>(); |
There was a problem hiding this comment.
This has been unchanged in Java for at least 20 years. It means "compiler should infer the type arguments".
It's used thousands of times in this codebase.
Signed-off-by: Mihai Budiu <mbudiu@feldera.com>
Signed-off-by: Mihai Budiu <mbudiu@feldera.com>
Signed-off-by: Mihai Budiu <mbudiu@feldera.com>
…ggregates Signed-off-by: Mihai Budiu <mbudiu@feldera.com>
There are 3 commits, only the last one is the analysis about unbounded state. It may need to be refined.
Fixes #4990
The analysis identifies streams which are GC-ed and assumes they are "finite"; outputs of window operators with a non-trivial lower bound are also assumed to be finite. Most operators produce finite outputs it all inputs are finite. Otherwise the state of a stateful operator is assumed to be unbounded.