Skip to content

[DBSP] Potential new API for Recursive Streams #6666

Description

@lstwn

Potential new API for Recursive Streams

The current API for RecursiveStreams has some limitations:

  1. Have a setting that limits the recursion depth for recursive SQL queries #3318 There is no possibility to specify a maximum recursion depth to prevent non-termination for ill-specified fixed point computations.
  2. [SQL][DBSP] Using more than 14 mutually-recursive views generates Rust compilation errors #5193 The SQL-to-DBSP compiler is currently limited to at most 14 recursive streams.
  3. The RecursiveStreams API always does an implicit distinct, i.e., computing the fixedpoint $y = \mathit{distinct}(f(i+Δi, y))$ to ensure convergence in more cases. Yet, sometimes this is overkill: If you happen to know that your data is, e.g., an acyclic graph or a (per-definition cycle-free) abstract syntax tree, you should not have to pay for the implicit deduplication operation and simply compute the fixedpoint $y = f(i+Δi, y)$.

Motivation

SQL's recursive common table expressions (CTEs) expose this trade-off: Either you use UNION ALL and have no implicit deduplication step (at the expense of non-termination for cyclic data) or you use UNION and get to enjoy the reverse properties. Why not have this for DBSP's recursion API, too? The updated tutorials 10 and 11 of this PR show this for the example of a transitive closure over an acyclic and cyclic graph, respectively.

Regarding (1) and (2): By now there exist approaches to fix this with DBSP natively (see #6653 and #6577, respectively).

Hence, I think there is the opportunity to create a new API for recursive computations that fixes all three limitations in a principled way.

Reference-level explanation

The SQL-to-DBSP compiler would need adjustments to make use of DBSP's new API. TBD; I don't know the compiler well enough.

Drawbacks

This would either be a breaking change if adjusting the RecursiveStreams API or it would cause a depreciation notice and introduce a new API.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions