Incremental computation

Fold is a datastream oriented approach to incremental computation (IC). Incremental computation roughly means doing as little work as possible to resolve an output when an input to a program changes. It’s a well established research domain in computer science that is used in many different domains from spreadsheets, to compilers, to various web rendering frameworks.

In the database field, IC is generally referred to as Incremental View Maintenance (IVM), and is less well established. The academic activity around IVM is rich, but has only started to permeate the database project and product world in the past few years. Even then, it’s really only been leveraged in systems oriented for big data workflows (Materialize) or caching portions of query sets (ReadySet). Generally this seems to be a result of the research being fairly complex and existing database runtimes being built with architectures that make integrating IVM concepts difficult (although some IVM postgres plugins are gaining traction).

Fold is a new architecture — while it inherits from projects like Differential Dataflow, it is a distinct approach with a much simpler surface area.