TimelyDataflow / TimelyDataflow/differential-dataflow
Relax requirements of `Diff`
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 3k
- Forks
- 211
- Avg merge
- 10h 42m
- Merged PRs (30d)
- 34
Description
The Diff trait constraints the types "differences" that differential dataflow updates can use. It currently corresponds to an Abelian group, which is something that can be added, has an inverse, and satisfies associativity and commutativity.
This property is great in that operators consuming such differences as inputs can produce such differences as outputs. In general, operators like group need the flexibility to subtract, and we have not great information about the order of accumulation (we could try harder here, but there are some semantic issues iirc).
At the same time, some operators do not need to negate records, for example join. As well as operators like map, filter, concat, and such. It would seem such operators could use a less restrictive requirement, in particular they may not require inversion.
Removing the requirement of inversion would allow differential dataflow to express monotonic computations more clearly, in their type: if a record may only be added and never removed, this can be reflected in the type () which simply doesn't have an inverse (nor a zero, perhaps?). If a maximization or minimization can only move in one direction, we need not support full retractions, and combined with the type information the consumer can know that it should never expect such.
Both inputs and outputs can reflect this type information, and we could know that a collection at any point is monotonic or not, and if appropriate specialize the implementation.
It seems that many of the internal accumulation strategies could still apply even without inverses, as the rules of accumulation merge the results without negation (reflecting an opportunity we are ignoring). We may want to understand whether we require a Zero associated value, which is what allows us to discard fully ineffective updates, but for many monotonic quantities you simply can't achieve this anyhow (i.e. no retraction).
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by locating the Diff trait and its constraints, then inspect the group, join, map, filter, and concat operators discussed in the issue. Determine which operators require inversion or Zero and whether their inputs and outputs can express monotonicity. Done requires a settled type and API design, plus agreement on the affected accumulation strategies.
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