TimelyDataflow / TimelyDataflow/differential-dataflow

Wrong check?

Open
#246 1 comment 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

https://github.com/TimelyDataflow/differential-dataflow/blob/fbea6a8ec599c6173642bf5b40a19ea3024d537d/src/trace/implementations/spine_fueled.rs#L410

I think this is wrong: it should be the other way around.

Consider the case in which:

  • through_frontier (TF) = {(1,1)}
  • pending[0].upper() (UP) = {(0,2), (1,0)}

We should not move pending[0] to merging because its frontier is not dominated by TF,
and as such we should not allow it to be merged with other batches.
However, the expression evaluates to true, since (1,0) <= (1,1).

Moreover, we should also enter the loop in the case of empty TF (as it dominates every other frontier).

I think the correct check should be

(self.through_frontier.is_empty()  
  || self.pending[0].upper().iter().all(|t1| self.through_frontier.iter().any(|t2| t1.less_equal(t2))))

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 at src/trace/implementations/spine_fueled.rs:410 and read the surrounding pending-to-merging logic. Check the frontier cases described in the issue, including an empty through_frontier, and verify that the condition matches the intended dominance behavior before running the relevant test suite.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data-engineering, distributed-systems
Issue type
Bug
Difficulty
2/5
Estimated time
1-3 hours
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
42/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.