Title: Incremental View Maintenance for (Recursive) Queries
Speaker: Frank McSherry (Materialize.IO)
Abstract
Declarative query languages provide systems with the ability to reason about how best to perform the necessary work for the query. They also provide the systems enough information to cleverly *maintain* the query, as the data change, often by doing substantially less work than is required to perform the query in the first place. This act goes by the name "Incremental View Maintenance" or "IVM".
Incremental view maintenance is common is most databases, especially for relatively easy queries (selection, projection, filtering, relational joins, and simple aggregations). Things become substantially more complicated when the queries are "harder", in particular when there are non-monotonic aggregations and recursion.
In this lecture, we'll talk through the principles underlying one approach to IVM for general data-parallel computation, including unrestricted aggregations and recursion. The basis is [differential dataflow](https://github.com/TimelyDataflow/differential-dataflow), a new approach to incremental computation that generalizes the "increments" from a *sequence* of changes to more expressive structures of re-use.
Slides
Bio
Frank McSherry is Chief Scientist at Materialize, Inc. Prior to that, Frank did a fair bit of relatively public work on dataflow systems, first at MSR Silicon Valley (RIP) and most recently ETH Zurich, with a bit of pro bono work in between. He also did some work on differential privacy back in the day, and has one of the more confrontational laptops in the business.