Clarification regarding compaction in DD

Hi!

I have a question on how DD decides which batches to compact? Specifically, when using the UnorderedInput interface to insert data into DD, consider the following pseudo code and 2 scenarios, both using the Pair timestamp:

for i in 0..m {
    if (i+1) != m { let edge_cap_next = edge_cap.delayed((i+1, 0)); }        (i)
    for j in 0..n {
        edge_input.session(edge_cap.clone()).give(edge, (i, j), diff)
        edge_cap.downgrade((i, j+1));
    }
    if (i+1) != m { edge_cap = edge_cap_next;  }                            (ii)
}

• When there are only one dimensional timestamps: [(0,0), (0,1), (0,2), ...(0,25)] (m=1 and n=25), there will no call to edge_cap.delayed(Pair(1,0)) in (i) above. Does that mean DD assumes there will be no data coming in at (1,*) or higher timestamps and starts compacting the batches as the timestamps move forward? Specifically, when computing at (0,25), will DD compact all data from (0,0) to (0,24) into a single batch, which would mean the computation at (0,25) will only be accessing diffs at one earlier timestamps (0,24) instead of all 24 earlier timestamps separately?

Experimentally, by adding the if condition at lines (i) and (ii) above (which then prevents creating the capability at (1,0)), runtime for wcc for 90 1D timestamps (m=1 and n=90) get better by 2.4X.

• Now consider the case when data is inserted at timestamps that can be organized in a 5x5 2D grid (m=5 and n=5). My question is, after statement (ii) above executes, does DD reason that there will be no more inputs at (i, *) (because we drop that capability) and hence can start compacting earlier rows?

Consider the computation at timestamp (3, 3), does DD compact the rows from 0 to 2 in any way? For example, DD can potentially compact all data from (0,0) to (2,3), which would mean the computation at (3,3) will only need to compute earlier diffs from 4 earlier batches: (2,3), (3,0), (3,1) and (3,2). Or does DD keep the diff data separate at all timestamps from (0,0) to (3,3)? In that case, the computation at (3,3) will need to sum the earlier diffs at each of the 16 batches with timestamps less than (3,3)? Or maybe DD does some compaction in between?

Start with the UnorderedInput interface and the delayed and downgrade capability calls shown in the issue, then trace how differential dataflow handles compaction. Determine the behavior for the one-dimensional and 5x5 timestamp cases, and document a definitive explanation of which batches remain accessible and when compaction occurs.