Skip to content

distinct (any reduce) misses a correction at the join of incomparable times when history advances past upper #1108

Open

Description

@creatifcoding

With a partially ordered timestamp, reduce can leave out a correction. distinct then holds a record twice at the join of two incomparable times at which the record was introduced. Observed on differential-dataflow 0.26.0 (crates.io) with timely 0.32.0, and on master at e7c2470. The cursor tactic used by reduce/distinct and the int_proxy ProxyReduceTactic are both affected [observed].

Conditions

  • The timestamp has at least three incomparable dimensions. The case below uses Product<u64, Product<u64, u64>>; a downstream randomized test first hit it inside iterate, where the iteration counter adds a dimension [observed].
  • A record is already in the history at a time p, before the interval being retired.
  • The interval's new times n1, n2 are such that p ∨ (n1 ∧ n2) is at or beyond the interval's upper, while p ∨ n1 is a time at which the output must change [inferred].

Repro

Cargo.toml:

[package]
name = "dd-repro"
version = "0.1.0"
edition = "2021"

[dependencies]
differential-dataflow = "=0.26.0"
timely = "=0.32.0"

src/main.rs:

use differential_dataflow::AsCollection;
use timely::PartialOrder;
use timely::dataflow::operators::vec::unordered_input::UnorderedInput;
use timely::order::Product;

type Time3 = Product<u64, Product<u64, u64>>;
fn t(a: u64, b: u64, c: u64) -> Time3 { Product::new(a, Product::new(b, c)) }

fn main() {
    // Each round: updates at their times, then the input frontier.
    let rounds = vec![
        (vec![(0u64, t(0, 1, 0), 1isize)], t(0, 0, 1)),
        (vec![(0, t(0, 0, 2), 1), (0, t(1, 0, 1), 1)], t(0, 1, 1)),
    ];
    let (send, recv) = std::sync::mpsc::channel();
    timely::execute_directly(move |worker| {
        let (mut input, root, probe) = worker.dataflow::<u64, _, _>(|outer| {
            outer.scoped::<Time3, _, _>("Product", |scope| {
                let ((input, root), stream) = scope.new_unordered_input::<(u64, Time3, isize)>();
                let (probe, _) = stream.as_collection().distinct()
                    .inspect(move |update| send.send(update.clone()).unwrap())
                    .probe();
                (input, root, probe)
            })
        });
        let mut cap = root.delayed(&t(0, 0, 0));
        drop(root);
        for (updates, frontier) in rounds {
            for update in updates {
                input.activate().session(&cap).give(update);
            }
            cap = cap.delayed(&frontier);
            // Run until the output frontier reaches the input frontier.
            worker.step_while(|| probe.with_frontier(|f| f.iter().any(|p| !cap.time().less_equal(p))));
        }
    });
    let output: Vec<_> = recv.try_iter().collect();
    println!("distinct output: {output:?}");
    // `distinct` must hold `0` exactly once wherever some copy is present.
    let at = t(0, 1, 2);
    let count: isize = output.iter().filter(|(_, time, _)| time.less_equal(&at)).map(|(_, _, d)| d).sum();
    println!("multiplicity of 0 at {at:?}: {count}");
    assert_eq!(count, 1);
}

Output on 0.26.0 [observed]:

distinct output: [(0, (0, (1, 0)), 1), (0, (0, (0, 2)), 1), (0, (1, (0, 1)), 1), (0, (1, (0, 2)), -1), (0, (1, (1, 1)), -1)]
multiplicity of 0 at (0, (1, 2)): 2
thread 'main' panicked at src/main.rs:43:5:
assertion `left == right` failed
  left: 2
 right: 1

The expected output also has (0, (0, (1, 2)), -1) and (0, (1, (1, 2)), 1). Those two corrections are what the proposed fix produces [observed, with the patch applied via [patch.crates-io]].

Cause

In round 2 the reduce advances the history by the meet of the new times, (0,0,2) ∧ (1,0,1) = (0,0,1). That moves the history time (0,1,0) to (0,1,1), which is the interval's upper.

(0,1,1) is not interesting, since no batch or pending time lies below it. But its join with the batch time (0,0,2), at (0,1,2), is interesting, and that is where distinct must retract the second copy.

In src/operators/cursor/reduce.rs (HistoryReplayer::compute), joins with batch times and times_current are formed only inside if !upper_limit.less_equal(&next_time) (l. 415 at e7c2470). The only other branch is else if interesting. An uninteresting time beyond upper_limit takes neither branch, so the join is neither evaluated nor deferred. In the next interval both (0,1,0) and (0,0,2) are history, which does not seed interesting times, so (0,1,2) is never visited [inferred, confirmed by instrumentation].

ProxyReduceTactic has the same shape: Sweep::tick returns Tick::Passed for an unreached time beyond upper without closing it against the reached times (src/operators/int_proxy/reduce.rs, ll. 602-608) [observed in code; retire-level test fails].

The coverage set in formal/Differential/RoundCoverage.lean (round_coverage, cl_inter_above_eq_novelJoins) contains (0,1,2) = (0,1,0) ∨ (0,0,2), a join that includes a novel time [inferred].

A fix and regression tests are in #1109.

This analysis and patch were prepared with AI assistance and reviewed before submission.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

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