Reactivity / Live Queries / Subscriptions / Database Observation

[tantaman]

A follow up to: expo/expo#23728 (comment)

Update Hook

The sqlite_update_hook has a number of problems:

1. It does not call you back if changes are made by other connections to the DB
2. It calls you back before transaction commit so the change that the update hook notifies you about could get rolled back. I didn't find docs stating this but experimentation shows it to be true.
3. Only one update hook callback can be registered per connection so if the app developer adds their own callback, yours will get removed.

   Any callback set by a previous call to this function for the same database connection is overridden.

4. sqlite3_update_hook does not notify when changes are made to WITHOUT ROWID tables

   sqlite3_update_hook ... to be invoked whenever a row is updated, inserted or deleted in a rowid table

We can work around most of these:

1. Only support observability if the developer uses a single write connection. This is a reasonable expectation given that SQLite does not support concurrent writers anyway and trying to have many concurrent write connections to the same DB won't buy users much, if anything. This is the approach taken by grdb as well.
2. For 2, we can collect all updates in the SQLite binding layer and not release those updates until we receive a commit callback
3. We can solve this in the binding layer by having the bindings keep track of many callback registrations to update/commit/rollback hooks.
4. We'll need to caveat that users may not observe without rowid tables. Unless @groue knows some magic to deal with this.

Fine Grained Observation

Given we have ways to make do with the update_hook, that brings us to "fine grained" reactivity.

The SQLite bindings I currently provide to React re-run a query if/when any table that the query used changes. This is regardless of what columns the query happened to use. This works pretty well until there are > 50 live queries.

@groue was gracious enough to spend some time answering questions about how GRDB handles observability and it looks like we can do better. We can:

1. Not re-run a query unless the columns used by that query were impacted by a write
2. In some circumstances, update query results in-place without re-running it

The high level about how GRDB accomplishes this --

1. It makes use of the authorizer callbacks -- https://www.sqlite.org/c3ref/set_authorizer.html. These callbacks let us discover the tables and columns used by a query rather than just the tables
2. It makes use of the pre-update hook -- https://sqlite.org/c3ref/preupdate_count.html. This callback tells us the values that individual columns will be set to on a write. To support this in a transactional manner, we'd need to pair this hook with the commit and rollback hooks such that we only update query results in-place after commit.

@groue also brought up some points I hadn't considered when thinking through other reactive query approaches.

• What if users have triggers on their tables?
• How about the effects of foreign keys and cascade delete?

The GRDB approach seems to avoid these pitfalls.

For the reactive components of Vulcan I think following the same path as GRDB, maybe even porting their implementation of observability to Rust so we can compile to WASM for use in the browser, is the right medium term path.

1. It is proven
2. It buys us quite a bit of performance gains. How much is unknown but, in theory, it should be quite a bit.
3. It doesn't require a massive amount of research since an implementation exists
4. My guess is it'll be 1/10th the effort of the original plans

[tantaman]

Just as an update -- I've found an alternative approach that allows full incremental view maintenance of any sql query. The only drawback is it requires pre-compiling the queries ahead of time so the queries which need to be "live" have to be known ahead of time. Bind params are still supported allowed, however.

We could get around compilation by creating a byte code interpreter (similar to how SQLite compiles and runs prepared statements) but that'll take a long while 😅

[fractaledmind]

Out of curiosity and for my edification, how is "full incremental view maintenance of any sql query" similar to and different from a "partial materialization engine" (a la PlanetScale Boost or Noria)? I'd love to more deeply understand how you are are weaving together the different hooks/callbacks that SQLite provides to provide a "full incremental view maintenance of any sql query". This is a topic of deep fascination to me, and I'd love to explore being able to bring some of these concepts to the Ruby world.

[tantaman]

I think you could weave together the update hook with the commit hook and get what you need.

The basic idea would be to compile a set of incremental views whose inputs are the tables that it queries. When something is being written to the tables used by the view (e.g., you get an update callback for the table), you pass the full contents of the row to the view.

I think the fastest way to get a proof of concept, although one that requires a compilation step, is to use Feldera's SQL -> DBSP compiler: https://github.com/feldera/feldera/tree/main/crates/dbsp & https://github.com/feldera/feldera/tree/main/sql-to-dbsp-compiler

Then wire the various SQLite hooks to feed that.

Basic idea:

1. Create the SQL string for the view
2. Compile that string to DBSP using their compiler. This emits the source for a Rust library.
3. Feed data from the SQLite update hook, by querying for the row that changed by rowid, to that library
4. Add some API surface area for users to get results from the pre-compiled incremental view

There are a few downsides to Feldera's compiler:

1. It is based on Apache Calcite so would require a Java toolchain installed on the thing doing the compilation. Not a huge problem but would probably require compilation of queries to be done at app build time.
2. Their compiler emits Rust code rather than byte code. This lands you in the same place as 1.
3. Their views require having all data in-memory from the source tables. So... if your dataset doesn't fit into memory your're out of luck.

Someone could fix (3) to read data from SQLite itself if rows are missing from the view. I think storage is on their roadmap but you'd want to check exactly how they're going to do it. Reading from the underlying DB? Creating separate storage? The latter seems like it would be hard to keep consistent with the main data store. Maybe there are some hints as to their direction here: feldera/feldera#982

There are a number of ports of the SQLite query parser out there so (1) should be tractable to move off of Calcite and to something lighter and maybe even something you can deliver with your end user's application. The benefit of being able to deliver the compiler with the app is that you can support dynamically crafted queries at runtime.

I believe (2) is also being fixed by the Feldera team. I don't know the details other than there will be a JIT to compile SQL strings to DBSP and it will be based on https://cranelift.dev. Maybe you can scour for more details in related issues to this one: feldera/feldera#678

While Feldera may not be ready for an embedded use case like SQLite, the core DBSP algorithm seems like a great fit. It is general (can express all of SQL) and doesn't seem too bad to implement.

[tantaman]

This is a topic of deep fascination to me, and I'd love to explore being able to bring some of these concepts to the Ruby world.

Do you want to bring it to SQLite for Ruby? Or just some sort of incremental computation to Ruby without any of the SQL baggage? E.g., something analogous to what I'm doing for JavaScript: https://github.com/vlcn-io/materialite

[tantaman]

I've been doing quite a bit of testing with Materialite and a fully in-memory SQLite DB.

Fully in-memory SQLite given that is the absolute fastest setup for SQLite in the browser.

The findings so far have been interesting in that Materialite dominates SQLite by an order of magnitude even for queries that can't be incrementally maintained.

My hunch is that the cost of going from JS -> WASM is just incredibly high. + the extra work of going from raw string -> parsed string -> sql query plan when fresh queries are created.

Materialite is also nice in that it doesn't matter if the developer does dumb things like returning 100,000 rows. Its still fast.

the "dev doing dumb things" example:

Materialite - Updating an issue in a list of 100,000 issues

diff.mov

In-Memory SQLite - Updating an issue in a list of 100,000 issues

livestore100k.mov

And an example of JS -> WASM cost just being incredibly high. Both Materialite and SQLite should be doing the exact same amount of work on query change since creating a brand new query has no incremental starting point.

Non-Incremental Queriers

Materialite - new queries, no incrementalism

filter-mat.mov

SQLite - new queries, y so slow?

filter-livesetore.mov