Special Edition on Databases

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: 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), and has long been a central problem of database theory and practice.

We describe a set of simple ideas which combined solve completely the IVM problem for arbitrary queries (including recursive queries and essentially all queries that can be written in SQL):

• representing changes as a first-class object
• treating all computations as (stateful) stream computations
• a trivial algorithm for converting any standard stream computation into an incremental computation

This work has received the 2023 VLDB best paper award, and the 2024 ACM SIGMOD research highlights award.

Takeaways

These ideas are not just a pretty theory: they are very practical. Feldera is a start-up which has built an incremental query engine which maintains incrementally arbitrary collections of views described in SQL; the incremental maintenance produces many orders of magnitude reduction in query latency and computational resource usage compared with traditional batch SQL query engines.

Who is this for?

Any person interested in databases, including theoreticians and practitioners. Only basic knowledge of data structures is required for understading this presentation.

About the presenter

Mihai Budiu is chief scientist at Feldera, 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. Four of his papers have received “test of time” awards. He is the acting PMC chair for the Apache Calcite project.