[dbsp, compiler] GC for the right-hand side of ASOF joins. #5370

ryzhyk · 2026-01-04T22:51:41Z

Fixes #2010

mihaibudiu

I will add a commit with the compiler support

mihaibudiu · 2026-01-05T17:16:54Z

crates/dbsp/src/trace/spine_async/list_merger.rs

 }

 /// Merger that merges up to 64 batches at a time.
+// FIXME: can we apply GC to the output of the merger instead of individual cursors?


If N is not large, this is not a big issue.
And I suspect in practice it is never large.

mihaibudiu · 2026-01-05T17:18:52Z

crates/dbsp/src/trace/spine_async/push_merger.rs

+                    return Ok(true);
+                }
+            } else {
+                // TODO: We currently don't handle the case when value_filter is a LastN filter.


how do we make sure we don't forget this? should an issue be filed?

I'll file an issue

crates/dbsp/src/trace/filter.rs

crates/dbsp/src/operator/dynamic/trace.rs

crates/dbsp/src/operator/dynamic/upsert.rs

mihaibudiu · 2026-01-05T18:27:13Z

crates/dbsp/src/trace/cursor.rs

+
+                // Find n'th value below the waterline.
+                let mut count = 1;
+                while count < *n && cursor.val_valid() {


what is the amortized cost of this? this looks expensive.

mihaibudiu · 2026-01-06T01:33:03Z

Partially fixes #1975
(I think)

ryzhyk · 2026-01-06T01:42:48Z

Fixes #1975 (I think)

Not until we actually apply it to top-k operators.

FilteredMergeCursor was implemented as a wrapper around a MergeCursor. In order to enable more flexible implementations that can do reverse search and lookahead we modify it to take a full-featured `Cursor` as an argument. Signed-off-by: Leonid Ryzhyk <[email protected]>

Add support for a new form of GC described in #1975 that preserves the last N values before the waterline. This can be used to GC the right-hand side of ASOF joins and top-k operators. Limitations: - The new GC mechanism doesn't yet work for PushMerger's. It's not hard to add, but since we only use PushMerger's via devtweaks, this doesn't seem like a priority - The current implementation can postpone discarding unused values quite a bit, potentially keeping several times more state than necessary (even though the state should be bounded): Specifically, it discards up to last the N values in each cursor when merging. The resulting batch may end up with more than N values below the waterline, which won't be discarded until the next merge operation. Moreover, the entire spine can have many more values before the waterline stored in other batches that were not part of the merge. Signed-off-by: Leonid Ryzhyk <[email protected]>

Signed-off-by: Mihai Budiu <[email protected]>

Copilot

Pull request overview

This PR adds garbage collection support for the right-hand side of ASOF JOIN operations. It introduces a new DBSPIntegrateTraceRetainValuesLastNOperator that retains the last N values below a waterline threshold, which is necessary for ASOF joins where we need to preserve a fixed number of recent values regardless of how far in the past they are.

Key changes:

Added DBSPIntegrateTraceRetainValuesLastNOperator for retaining the last N values per key
Implemented GroupFilter enum to support both simple and LastN filtering strategies
Updated ASOF join implementation to apply GC to both sides of the join
Added comprehensive test coverage for the new functionality

Reviewed changes

Copilot reviewed 40 out of 40 changed files in this pull request and generated 1 comment.

Show a summary per file

File	Description
`sql-to-dbsp-compiler/SQL-compiler/src/main/java/org/dbsp/sqlCompiler/circuit/operator/DBSPIntegrateTraceRetainValuesLastNOperator.java`	New operator for retaining last N values with GC
`sql-to-dbsp-compiler/SQL-compiler/src/main/java/org/dbsp/sqlCompiler/circuit/operator/GCOperator.java`	Added `asOperator()` method to interface
`sql-to-dbsp-compiler/SQL-compiler/src/main/java/org/dbsp/sqlCompiler/compiler/visitors/outer/monotonicity/InsertLimiters.java`	Updated ASOF join to create GC operators for both sides
`sql-to-dbsp-compiler/SQL-compiler/src/main/java/org/dbsp/sqlCompiler/compiler/visitors/outer/LowerAsof.java`	Extended to handle LastN operators in ASOF join lowering
`crates/dbsp/src/trace/filter.rs`	New file defining `GroupFilter` enum for filtering strategies
`crates/dbsp/src/trace/cursor.rs`	Implemented `GroupFilterCursor` state machine for LastN filtering
`crates/dbsp/src/operator/dynamic/trace.rs`	Added test coverage for `integrate_trace_retain_values_last_n`

Comments suppressed due to low confidence (2)

sql-to-dbsp-compiler/SQL-compiler/src/main/java/org/dbsp/sqlCompiler/compiler/visitors/outer/LowerAsof.java:1

Missing closing parenthesis in comment. The comment should end with )).
sql-to-dbsp-compiler/SQL-compiler/src/main/java/org/dbsp/sqlCompiler/compiler/visitors/outer/LowerAsof.java:1
Missing closing parenthesis in comment. The comment should end with )).

Copilot · 2026-01-06T18:31:17Z

crates/dbsp/src/trace/filter.rs

+///   Assumes that the predicate is monotonic: once it is satisfied for a value,
+///   it is also satisfied for all subsequent values for the same key.
+///   Also assumed that the values are ordered in some way, so that the last N
+///   values under the cursor ate the ones that need to be preserved.


Corrected spelling of 'ate' to 'are'.

Suggested change

/// values under the cursor ate the ones that need to be preserved.

/// values under the cursor are the ones that need to be preserved.

ryzhyk requested a review from mihaibudiu January 4, 2026 22:51

ryzhyk added SQL compiler Related to the SQL compiler DBSP core Related to the core DBSP library labels Jan 4, 2026

ryzhyk mentioned this pull request Jan 5, 2026

[dbsp] Transaction support for asof joins. #5372

Merged

mihaibudiu approved these changes Jan 5, 2026

View reviewed changes

ryzhyk and others added 3 commits January 6, 2026 10:10

[SQL] Compiler support for ASOF JOIN right input GC

4636e8b

Signed-off-by: Mihai Budiu <[email protected]>

ryzhyk changed the title ~~[WIP] GC for the right-hand side of ASOF joins.~~ [dbsp, compiler] GC for the right-hand side of ASOF joins. Jan 6, 2026

ryzhyk force-pushed the issue-2010 branch from 839fc01 to 4636e8b Compare January 6, 2026 18:14

ryzhyk marked this pull request as ready for review January 6, 2026 18:29

Copilot AI review requested due to automatic review settings January 6, 2026 18:29

Copilot AI reviewed Jan 6, 2026

View reviewed changes

ryzhyk added this pull request to the merge queue Jan 6, 2026

Merged via the queue into main with commit bc7c2b7 Jan 6, 2026
5 of 7 checks passed

ryzhyk deleted the issue-2010 branch January 6, 2026 19:38

	/// values under the cursor ate the ones that need to be preserved.
	/// values under the cursor are the ones that need to be preserved.

[dbsp, compiler] GC for the right-hand side of ASOF joins. #5370

[dbsp, compiler] GC for the right-hand side of ASOF joins. #5370

Uh oh!

Conversation

ryzhyk commented Jan 4, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

mihaibudiu left a comment

Choose a reason for hiding this comment

Uh oh!

mihaibudiu Jan 5, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

mihaibudiu Jan 5, 2026

Choose a reason for hiding this comment

Uh oh!

ryzhyk Jan 6, 2026

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

mihaibudiu Jan 5, 2026

Choose a reason for hiding this comment

Uh oh!

mihaibudiu commented Jan 6, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ryzhyk commented Jan 6, 2026

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Pull request overview

Reviewed changes

Uh oh!

Copilot AI Jan 6, 2026

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

ryzhyk commented Jan 4, 2026 •

edited

Loading

mihaibudiu Jan 5, 2026 •

edited

Loading

mihaibudiu commented Jan 6, 2026 •

edited

Loading