TimelyDataflow / TimelyDataflow/differential-dataflow

Interactive: Support recursive queries

Open
#140 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Rust
Stars
3k
Forks
211
Avg merge
10h 42m
Merged PRs (30d)
34

Description

A query is a list of rule definitions, binding a plan to a name. Each of these plans can invoke other sources of data by name. If the sequence of rules only reference previously bound names, then we do not need any recursion, and can just implement each rule in order. That is how the code currently works.

More generally, we can have some non-standard behavior if:

  1. A rule references itself,
  2. A rule references a name bound later in the query.
  3. A rule references a bound name that is rebound later in the query.

In these cases, and perhaps others I haven't thought of, we might prefer the semantics of a query to be the fixed point of repeated application of its rules, in order. This is a strict generalization of just requiring an acyclic "depends on" relation among the rules.

It seems natural to construct the "depends on" relation and find the strongly connected components. Each of these can be independently rendered as an iterative scope, with iterate::Variable types used for collections that must develop recursively. For re-bound names, the initial value of the variable should be the initial collection, and the recursive definition then overwrites this.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

The issue names no files or tests. Start by locating the Interactive query rule evaluation and its handling of rule dependencies, then determine how strongly connected components and iterative scopes fit the existing implementation. Done means recursive, forward-reference, and rebound-name queries use fixed-point semantics while acyclic queries retain current behavior, with coverage for these cases.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data-engineering, distributed-systems
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.