TimelyDataflow / TimelyDataflow/differential-dataflow

Implement `JoinGe` / `JoinLe`

Open
#80 0 comments 0 reactions 0 assignees View on GitHub

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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.