Incremental Computation
summary
Claims a practical, general solution to incremental view maintenance for arbitrary SQL (including recursive queries) by representing updates as Z-sets, treating queries as stateful stream computations and mechanically transforming standard stream plans into incremental ones using a delay (Z^-1) / integrate/differentiate pattern. Implementation (open source, used in Feldera) turns a 250 GB job on Spark (60 nodes, 20 minutes) into one machine with 15 GB RAM and ~200 ms refresh — roughly 5000x less work; paper won VLDB 2023 Best Paper and SIGMOD 2024 highlight.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 1:03Core ideas behind incremental computation
- 3:30Why incremental computation matters for databases
- 7:20Incremental view maintenance explained
- 10:51Understanding changes with Z-sets
- 20:59Streams in incremental systems
- 30:29Databases as streaming systems
- 33:16Decomposing queries for incremental computation
- 37:22Building incremental operators
- 41:57Time-space trade-offs in incremental systems
- 43:02Q&A
related talks
38mIncremental View Maintenance: Beyond Worst-Case Analysis I
01h 05mIncremental View Maintenance 2
21mRecent Advances in Incremental View Maintenance
01h 08mIncremental View Maintenance 1
33mA (Semi)Ring-Based Query Algebra for Incremental View Maintenance and Query Compilation
29mScalable Spreadsheet-driven End-User Applications with Incremental Computation
26mIncremental View Maintenance: Beyond Worst-Case Analysis II
18mDBSP: A unified (practical) theory of databases, streams, and incremental computation