TimelyDataflow / TimelyDataflow/differential-dataflow
Implement `JoinGe` / `JoinLe`
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 3k
- Forks
- 211
- Avg merge
- 10h 42m
- Merged PRs (30d)
- 34
Description
Several TPCH queries (e.g. q11, q17, q20, q22) have inequality joins, where (key, value) pairs are joined against (key, threshold), and should result in (key, value) for each value greater than the corresponding threshold.
Using differential dataflow's JoinCore, this might look like
let values: Collection<_, (K, V)> = ...;
let threshes: Collection<_, (K, V)> = ...;
values.join_core(&threshes, |k,v,t| if v > t { Some((k,v)) } else { None });
This implementation can have pretty miserable performance: each time a threshold changes we reconsider all values. Even if the threshold changed only slightly.
However, we don't need to have miserable performance. The Cursor types backing the values collection have efficient (logarithmic) seek_val functionality, and given a threshold change (note: same time and negated diff):
(thresh_old, time, diff)
(thresh_new, time, -diff)
We can load only the subrange of values between thresh_min and thresh_max, whichever they happen to be.
I propose we consider a join variant implementing
values.join_core(&threshes, |k,v,t| if v > t { Some((k,v)) } else { None });
with the above observations as a performance optimization. There are probably further optimizations, but just doing this should be relatively easy and would dramatically improve some cases.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by locating the differential dataflow JoinCore implementation and the Cursor code supporting seek_val. Compare the proposed JoinGe/JoinLe behavior with TPCH queries q11, q17, q20, and q22, then verify that threshold changes load only the values between the old and new thresholds while preserving the stated (key, value) results.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- data-engineering, distributed-systems
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 38/100