Fair intersection of seekable iterators
summary
Proposes a compositional join implementation based on a seekable iterator interface that bounds work by interleaving calls, introducing a later constructor to avoid blocking and a found flag that returns either a result or a lower bound. Shows worst-case pathological ordering (evens ∩ odds ping‑ponging through a million elements) and demonstrates practical throughput: a triangle query over 10M edges runs in ~6s, a transitive closure on 240k edges in ~9s, implemented in Rust over sorted arrays/LSM-style storage.
AI-written summary · about
chapters (15)
- 0:00Fair intersection intro
- 1:23Disjunctive to conjunctive search
- 3:12Depth-first union fails completeness
- 5:01Later for fair disjunctive search
- 7:09Seeking in sorted arrays
- 9:39Seekable iterator interface
- 12:51Compositional intersection performance
- 13:33Fair intersection with lower bounds
- 17:55Exhausting seekable iterators
- 19:19Relational algebra and joins
- 21:08Datalog engine in Rust
- 23:18Triangle query benchmark
- 24:45Transitive closure and LSM
- 25:51Takeaways and future work
- 27:15Q&A
related talks
16mA Compiler for Fused Relational Operations on Multisets
55mSort vs Hash A Duality
01h 05mQuery Optimization and Evaluation 2: Worst-Case Optimal Join Algorithms
14mVerifying Concurrent Multicopy Search Structures
26mIncremental View Maintenance: Beyond Worst-Case Analysis II
01h 09mAccessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: I
29mDirect Access for Conjunctive Queries with Aggregation
57mQuery Optimization and Evaluation 1: Output Size Bounds and Information Theory