comnik / comnik/declarative-dataflow

CardinalityOne not correct for partially-ordered times

Open
#76 0 comments 0 reactions 0 assignees View on GitHub
bug
Dominant language
Rust
Stars
326
Forks
27
PR merge metrics
No merged PRs in 30d

Description

The state machine powering the `CardinalityOne` operator currently assumes totally ordered input timestamps, s.t. when processed in time order (i.e. in the order that `consolidate` will reveal them), all keys end up in the correct state.

In fact, the current implementation is a bit stronger, in that it should still produce correct results on bitemporal inputs, as long as event times increase monotonically per key. This is due to an [additional sort by event time after consolidation](https://github.com/comnik/declarative-dataflow/blob/master/src/operators/mod.rs#L56).
For [general partially-ordered inputs](https://github.com/comnik/declarative-dataflow/blob/master/tests/cardinality_one.rs#L362) this is not safe any longer.

A solution might be to re-implement `CardinalityOne` as a special kind of `arrange`. This way we could use the trace handle to lookup the correct last value as of the input time, without having to maintain two traces per attribute.

The existing implementation should get rid of the additional sort and live on as `CardinalityOneTotal`, or something like that.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.