TimelyDataflow / TimelyDataflow/differential-dataflow

Implement a JoinTotal trait and operators

Open
#77 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

Issue #74 calls for specialized implementations for totally ordered timestamps. The join operator variants may be good candidates, as they are pervasive even with totally ordered timestamps, and the core join logic is somewhat complicated by partial orders.

This may be a relatively minor copy / paste job, but this interpretation may be optimistic. I believe the main point at which the JoinCore trait must be careful due to partial orders is in the "complicated" case for the JoinThinker type: when our keys have "long" histories on both inputs we dare not risk a Cartesian product, and instead play back the histories in time order. As with GroupCore, this tracks the meet of times and compacts updates using advance_by with this meet; this should all be unnecessary with totally ordered times, and we can instead just update the collection of values in-place.

It would be excellent if we only specialized the implementation of the JoinThinker type, as this may be the only logic that needs to change. This might mean some horrible mess where JoinCore becomes parametric in the type of the thinker, in which case we should not do this, but should specialization ever land we could imagine expecting Rust to pick up the specialized implementation, perhaps?

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

Start by reading the JoinCore and JoinThinker logic described in the issue, then compare it with GroupCore and the specialized implementations requested by issue #74. Determine whether only JoinThinker needs specialization without making JoinCore unnecessarily parametric; done means implementing JoinTotal and its operators with the intended totally ordered behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
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.