search

TimelyDataflow / differential-dataflow

An implementation of differential dataflow using timely dataflow on Rust.
MIT License
2.53k stars 182 forks source link

dogs^3 compaction improvement #457

Closed frankmcsherry closed 7 months ago

frankmcsherry commented 7 months ago

The half_join operator and its ilk take a frontier_func: FF argument that is meant to act on times and "rewind" them enough that logical compaction using their output will keep their input from being consolidated with the past (primarily to allow "strict inequality" with the timestamp, which would not be correct if the past were consolidated up to it).

This function was previous from a time to a time, but this is insufficiently expressive. For example, with a partial order one needs to take times (x, y, z) to (x - 1, y - 1, z - 1), where it would be sufficient to use the frontier { (x - 1, y, z), (x, y - 1, z), (x, y, z - 1) }.

This PR modifies the function to allow it to modify an Antichain argument, rather than needing to return a new single timestamp.

frankmcsherry commented 7 months ago

It also includes a commit that cleans up some dependencies, because these were lingering.