Skip to content
Rindle
Contents

ZVM

Rindle's incremental query engine

ZVM (Zero View Maintenance) is the query engine at the heart of Rindle. It started as the engine behind Zero, where it has run in production for two years, and Rindle is a Rust port of it.

What It Does

A normal database answers a query once. The moment anything changes, the answer is stale, and the application has to ask again.

ZVM answers once and then keeps the answer current. For every write to the tables a query reads, it works out what changed in the result: this row entered, that one left, this field is different, a comment appeared under this issue. It does this by precisely calculating the changes needed to the previous result. It doesn’t re-run queries and diff.

ZVM is inspired by incremental query engines like Differential Dataflow, DBSP, and Noria, but blends in features from traditional query engines to better balance hydrate and update performance.

Why We Built It

Previous incremental query engines are built to provide maximum update speed and throughput, but trade-off time to first result. They are designed for OLAP style applications where there are a small number of very-long running queries over huge datasets.

When we were working on Zero, we needed efficient live queries but for an OLTP use case — large numbers of dynamic, small queries over moderate datasets.

How It Works

Differential dataflow and DBSP work by creating a dataflow pipeline of operators. Data flows through these operators unidirectionally, from top down.

A dataflow pipeline Two tables feed a join, which feeds a limit, which feeds the result. Data only flows downward. The join keeps a copy of both inputs, and the limit keeps every row that could enter the top 10. ISSUE table COMMENT table JOIN issue → comments LIMIT 10 RESULT holds a copy of both inputs holds every row that could enter the top 10
Every row flows down.

This has a few immediate challenges for OLTP applications:

  1. The entire input dataset needs to flow through the pipeline to compute the first result.
  2. Join and limit operators require a huge amount of state to be able to lookup data needed for their work, since there is no other place they could get it.

ZVM also builds a pipeline, but in ZVM data can flow both ways. Clients can pull data from the bottom-up to hydrate initial results. The system can also push data from top-down when data sources change.

A ZVM pipeline The same tables, join and limit. Changes are pushed down from the tables. Rows are pulled up from the tables when a result is needed, so the join keeps no copy and the limit stops after about ten rows. ISSUE table COMMENT table JOIN issue → comments LIMIT 10 RESULT no copy: fetches rows from the tables stops after about 10 rows
Push ↓ changes when a table changes. Pull ↑ rows when a result is needed.

This means that just like in a normal database, ZVM can stop early on limited queries. If you request 10 rows, ZVM will usually read some small constant factor more than 10 rows.

Also, since ZVM inherently includes the ability to fetch, it can use this in the join and limit operators to avoid storing state. Instead that data can be looked up from the database itself when needed.

Stopping early means that Rindle can support short-lived, dynamic live queries. And using very small amounts of memory in the operators means that Rindle can support many such queries.