[vlovich123]

Is there any trick to implement live updates in a scaleable way? In the limit for a naive implementation, every mutation would have to check every subscriber to see if the change is relevant which seems like it would cause large bottlenecks for writes.

[jitl]

One of the guys behind Convex explained the rough idea; I hope I do it justice.

The strategy is to break the subscription up into listens based on the read-set ranges of the query. Then you put the individual read-set ranges into a system table that you index. Finally when writes happen, you notify all queries who's read-set intersects with the write-set.

For example, say I have a query `SELECT * from block WHERE parent_id = X AND last_modified_at > Y`.

This query might create two subscriptions for its read sets:

    { query_id: Q, table: block, column: parent_id, min: X, max: X }
    { query_id: Q, table: block, column: last_modified_at, min: Y, max: Infinity }

Now a write happens: `INSERT INTO block { id: Z, parent_id: X, last_modified_at: Y + 10, title: "hi" }`

We can find our subscriptions to notify by doing queries like these:

    SELECT query_id FROM subscription WHERE
      table = block
      AND (
        (column = id
        AND min <= new_block.id
        AND max >= new_block.id
        )
        OR
        (column = parent_id
        AND min <= new_block.parent_id
        AND max >= new_block.parent_id)
        OR
        (column = last_modified_at
        AND min <= new_block.last_modified_at
        AND max >= new_block.last_modified_at)
      )

Then you notify all those query_ids.

I'm sure there's a lot of details and optimizations you can do on top of this; finding the right read sets seems pretty tricky for complex queries. Plus stuff like batching/debouncing, etc.

[vlovich123]

Is there a talk you can point me to?

There’s several challenges with this approach that come up for me (which unless I’m mistaken is the naive approach of checking each write against a notification set).

The first is that maintaining the read set seems very expensive since it scales with the number of live queries installed. In a multi tenant DB, that seems tricky to manage in terms of memory used.

The second is that the computation of intersection with a read range seems potentially very expensive. Imagine you have a string column. You now have to do a string comparison for every insertion that might hypothetically match the query.

Finally, computing that read set correctly seems challenging (as you mention) and it’s not immediately clear to me it’s always tractable (eg could you do this with arbitrary complicated joins?).

Additionally, in your description, each write has an implicit table scan to do the select to find the intersection. That will tank write throughput even for small total intersection sets (eg there’s a reason LSM databases do deletes by inserting a tombstone instead of checking whether the data exists first, same with the merge operator in RocksDB - a db read in the write path significantly kills performance)

[jitl]

See https://news.ycombinator.com/item?id=31836545

To the specifics of my solution, you’re going to visit many less than O(subscriptions) rows using a btree index on min & max as I suggested, and I’m sure there’s use case specific data structures that could do an even better job.

You also don’t need to stall the write transaction until subscriptions are notified; you can batch up that work into big chunks and process it on a background queue after the transaction commits.

Finally, you don’t need to have subscribe to read sets that exactly match the query. You can simplify them a lot for those kinds of complex cases because you can tolerate over-subscription, re-running the query even if it hasn’t changed, checking the new result, and then deciding to deliver it to the external subscriber or not.

[mpercival531]

Listener callout does not have to be part of the synchronous writes. Say if you keep a changelog, listeners can be asynchronously notified. These checks can be batched and throttled as well to minimize call-outs.

I would suspect this is what Google does with Cloud Firestore.

[vlovich123]

If you’re throttling, then your database can’t actually keep up with broadcasting changes. Throttling only helps ensure the system keeps working even when there’s a sudden spike.

Batching only helps if you’re able to amortize the cost of notifications by doing that, but it’s not immediately clear to me that that there’s an opportunity to amortize since by definition all the book keeping to keep track of the writes would have to happen (roughly) in the synchronous write path (+ require a fair amount of RAM when scaling). The sibling poster made mention of taking read / write sets and doing intersections, but I don’t think that answers the question for several reasons I listed (ie it seems to me like you’d be taking a substantial performance hit on the order of O(num listeners) for all writes even if the write doesn’t match any listener). You could maybe shrink that to log(N) if you sort the set of listeners first, but that’s still an insertion speed of m log(n) for m items and n listeners or O(mn) if you can’t shrink it). That seems pretty expensive to me because it impacts all tenants of the DB, not just those using this feature…