Abstract: We describe DBSP, a framework for incremental computation. Incremental computations repeatedly evaluate a function on some input values that are "changing". The goal of an efficient implementation is to "reuse" previously computed results. Ideally, when presented with a new change to the input, an incremental computation should only perform work proportional to the size of the changes of the input, rather than to the size of the entire dataset. In databases "incremental computation" is known as Incremental View Maintenance (IVM); IVM has long been a central problem of database theory and practice.
We define incremental computations as computations on data streams, i.e., sequences of data values, by borrowing ideas from Digital Signal Processing. We then give a general solution to the incremental computation problem, including an algorithm for converting any DBSP program into an incremental program. Feldera is an early-stage start-up that has built a full-fledged incremental SQL query engine based on a DBSP Rust runtime.
This work has received the 2023 VLDB best paper award, and the 2024 ACM SIGMOD research highlights award.
Bio: Mihai Budiu is chief scientist at Feldera.com, an early-stage startup. He has a Ph.D. in computer science from Carnegie Mellon University. He was previously employed at VMware Research, Barefoot Networks, and Microsoft Research. Mihai has published papers on reconfigurable hardware, computer architecture, compilers, security, distributed systems, big data platforms, large-scale machine learning, programmable networks and P4, data visualization, and databases; five of his papers have received "test of time" awards. He has also received two technology transfer awards. He is a member of the Apache Calcite Project Management Committee (PMC).