Event-Reduce: updating live query results without re-running the query

The problem is the second read after every write

Live queries, also called reactive or realtime queries, sit between an application and a database that can report changes. The scenario the documentation describes is short. You run a query that returns a result in 100 milliseconds. A write event changes some data. Now you need the new version of the result set, and you have three options.

The first is to run the query over the database again, which takes another 100 milliseconds. The second is to write complex code that somehow merges the incoming event with the old state. The third is to use EventReduce to calculate the new results on the CPU without disk IO, nearly instant.

That middle option is the one most teams end up choosing by accident, and it is where the bugs live. Merging an event into a result set by hand means re-implementing the query semantics in application code, and query semantics include sort order, limit, and the interaction between them.

EventReduce takes the third option and makes it mechanical. When a document is inserted, updated or deleted, it takes the old query results and the change event and computes the new results in memory, without querying the database again. It is described as a lightweight form of incremental view maintenance for a single query over a single table or collection.

Three functions, a query description, and a change event

The JavaScript implementation is published to npm as event-reduce-js and the usage is compact. You describe the query as a parameter object, hold the current results, and pass a change event to the library:

import { calculateActionName, runAction } from 'event-reduce-js';

// describe your query: SELECT * FROM users WHERE age > 18 ORDER BY age, id LIMIT 10
const queryParams = {
    primaryKey: 'id',
    sortFields: ['age', 'id'],
    limit: 10,
    queryMatcher: doc => doc.age > 18,
    sortComparator: (a, b) => (a.age - b.age || (a.id < b.id ? -1 : 1)) < 0 ? -1 : 1
};

let results = [{ id: 'a', age: 20 }, { id: 'b', age: 30 }];

The change event from the database is then handed to the algorithm, and the action it returns is applied, with a fallback to a full query when the event cannot be optimized:

// a change event from your database's change stream
const changeEvent = { operation: 'INSERT', id: 'c', doc: { id: 'c', age: 25 }, previous: null };

const action = calculateActionName({ queryParams, changeEvent, previousResults: results });
if (action === 'runFullQueryAgain') {
    results = await runQueryOnDatabase(); // EventReduce could not optimize this event
} else {
    results = runAction(action, queryParams, changeEvent, results);
    // -> [{ id: 'a', age: 20 }, { id: 'c', age: 25 }, { id: 'b', age: 30 }]
}

The three functions are calculateActionName, runAction and, in the fallback branch, your own runQueryOnDatabase. The library does not know how to query your database, it only knows how to update a result set it is given.

Look closely at the sortComparator, because it encodes the ordering. It compares on age, breaks ties on id, and returns -1 or 1. That comparator is the contract with the database, and the correctness of every result depends on it agreeing with what the database would have returned.

Eighteen state functions and sixteen action functions

The mechanism underneath is combinatorial, and the documentation describes it precisely.

EventReduce uses 18 different state functions to describe an event plus previousResults combination. A state function returns a boolean value, and the examples given are isInsert(), wasResultsEmpty() and sortParamsChanged().

There are also 16 different action functions. An action function takes the event and previousResults and modifies the results array in a given way, with the examples insertFirst(), replaceExisting(), insertAtSortPosition() and doNothing().

With 18 boolean state functions there are 2^18 possible state combinations, and the documentation says that for each of these 2^19 state combinations the library calculates which action function gives the same results the database would return when the full query is executed again. The slight difference in the two counts is in the source text as written, and it is worth noting only because it signals that the tables were generated by enumeration rather than written by hand.

The result of that enumeration is a big truth table, and from the truth table a binary decision diagram is created. The BDD is then optimized so that as few state functions as possible have to be evaluated to determine the correct action for an incoming event and results combination.

The final artifact, the optimized BDD, is what ships as the algorithm, and it is language agnostic. The programmer is not supposed to know about any of this optimisation and instead calls three simple functions.

The predictable sort order requirement

This is the constraint that decides whether you can use the library at all, and it is listed first under limitations.

EventReduce only works with queries that have a predictable sort-order for any given documents. The documentation adds the practical fix in parentheses: you can make any query predictable by adding the primary key as the last sort parameter. That is why the example query sorts by age, id rather than by age alone, with id being the primary key.

The reason is structural. To insert a new document into a sorted result set without re-querying, the algorithm has to know exactly where the document belongs, and that requires a total order with no ties. Without a tiebreaker, two documents that compare equal could come back from the database in either order, and the sorted position of a new document would be ambiguous.

A second limitation is stated but truncated in the documentation: it begins with the statement that EventReduce can be used with, and the sentence is not finished in the source text. That gap is worth knowing about before you rely on the limitations list being complete, particularly if your change stream carries events with fields the library does not model, such as a document that moves in and out of the matched set in a single operation.

Where the speed claims come from

The performance figures in the project are specific and worth reading in context.

In the browser demo, for randomly generated events, about 94% of them could be optimized by EventReduce, so roughly 94% of write events in the demo are handled without re-running the query. The documentation says that in real world usage, with non-random events, this can be even higher.

The other figure is delivery speed. For the different implementations in common browser databases, the project reports up to 12 times faster displaying of new query results after a write occurred.

Both are claims about the project's own demo and about browser databases, not about your database, and the 12 times figure is an upper bound on a favourable comparison rather than a typical result. The 94% figure is more informative, because it is the fraction of writes for which the algorithm even applies, and it is a property of the workload rather than of the hardware.

The claim that does carry weight is the one about production use. EventReduce is described as proven in production as the query engine behind the live queries of RxDB.

RxDB replaced handwritten change detection with it

The reference implementation gives a concrete before and after, which is the clearest evidence that the approach works at scale.

RxDB, the local-first JavaScript database, has used EventReduce for its live queries since version 9.0.0, where it is enabled by default. When an app subscribes to a query, RxDB keeps the results up to date by running each write event of the collection through EventReduce, and only when EventReduce returns runFullQueryAgain does RxDB query the storage again. So most writes update the observed results without an extra read from the storage, whichever storage RxDB runs on.

Before that, RxDB used its own QueryChangeDetection, which was made of many handwritten if-else comparisons. The contrast is the real argument for the approach. A handwritten comparator has to be extended every time a new case appears, and each extension is a place for an ordering bug to hide. A precomputed decision diagram is fixed and complete at the point it was generated.

The fallback branch is designed rather than exceptional. runFullQueryAgain is a normal, expected outcome that the caller must handle, which is a healthier design than a library that silently returns a wrong result when it meets a case it does not understand.

Where the project fits, and what to check before adopting

The documentation lists the situations it is meant for: observing query results that need to stay up to date, for example reactive user interfaces, realtime dashboards, live queries in local-first apps, or server-push subscriptions. The stated benefits are reducing the latency until a database change updates the application, making observing query results more scalable by doing less disk IO, reducing the bandwidth when streaming realtime query results from the backend to the client, and creating a better form of caching where instead of invalidating the cache on write you update its content.

The last of those is the conceptual shift worth taking seriously. Invalidation is a blunt instrument: any write to a collection invalidates every query that touches it. Updating the content of a result set in place is precise, and it is the reason the approach composes with a change stream rather than merely avoiding a read.

There are three things to verify before you integrate. First, that every query you want to optimize has a total order, and that you append the primary key as the last sort parameter where it is missing. Second, that the sortComparator you supply matches your database's ordering, including collation, because a mismatch produces incorrect results rather than an error, and the library has no way to detect it. Third, that your change stream gives you what the algorithm needs. The event shape shown carries an operation of INSERT, an id, a doc and a previous value, and for updates and deletes the previous document is what lets the algorithm remove the old entry from the result set.

The project is MIT licensed, and the algorithm is published as event-reduce-js on npm with a JavaScript implementation in the repository.

Editorial conclusion

Adopt EventReduce if you are running live or reactive queries where a write currently forces a full re-query, since the algorithm takes the previous results and the change event and returns updated results without touching the database, and it works with any database that exposes a change stream. Do not adopt it if your query has no deterministic sort order, because that requirement is not optional, and do not adopt it as a general cache invalidation strategy when a full re-query is cheap. Before you integrate, append the primary key as the last sort parameter of every query you intend to optimize, since that is the documented way to make an arbitrary query predictable, and check the sortComparator you supply against the ordering your database would produce, because a mismatch there produces wrong results rather than an error.

Frequently asked questions

Official sources

1. License: MIT
2. Project website
3. pubkey/event-reduce on GitHub
4. README
5. Releases