Venryx
commented
3 years ago Desired optimizations:
1) Cache subscription-query results, and apply row-changes to its results directly (ie. mutating the cache)
Rather than re-running the full query for a collection each time a row changes, instead read the change-data within the replication-stream entry, find the subscription-queries that are affected by the change, and directly apply those changes in memory.
Of course, this is not possible for every query (eg. if the query depends on computed-values from functions), but it is possible for a large portion of queries, and -- at least in my project -- that subset is worth the effort to support. (in fact, for my current codebase, 100% of the live-queries should be supportable in this way, due to the much less expressive querying that Firestore supports)
Some posts/repos that are relevant:
Granted, this caching system is expected to add complications with regard to permissions; you have to make sure that the cache is invalidated when the user's permissions change, otherwise it may result in unauthorized data leakage/persistence. The InvaliDB papers discuss this issue, and the solution it uses. (two of the papers: short version, long version)
The permission issue is likely an area where the solution settled on will not work universally (due to the flexibility of the Postgres RLS system). However, if the solution found can handle the use-cases of 80+% of projects/queries (for example, by declaring certain rules the developer has to follow for reliable usage), it can still be useful.
Admittedly, this non-universality will likely keep the advanced live-query system in the domain of a third-party addition, rather than something in the core; this thread is still relevant, however, in that it can guide discussion on what "primitives" are necessary within the subscription-lds and lds packages in order to support a third-party solution.
2) Batch equivalent subscriptions from multiple users
Given the above caching system, it's expected that there will be many concurrent queries amassed, for systems with many users. This implies significant overhead, as each user (and for each subscribed collection) will require their own "query match" check, when a row is changed.
To help reduce this query-matching overhead, it is important to be able to merge equivalent subscriptions wherever possible. For example, if there are 1000 users and each subscribes to a shared list of events for the month, we want only one subscription made instead of 1000.
Again, this functionality requires that the permission system be constrained enough that the system can meaningfully batch subscriptions without breaking security rules. This means that the solution will not work for every project (at least not without certain restrictions or hints being added). While this makes it problematic to include within Postgraphile proper, the optimization can be very beneficial for projects (or portions of them) where maximum performance is more important than RLS's full flexibility, and the developers are willing to use a third-party solution for it.
3) Add partitioning system, so the query-matching itself doesn't overload the live-query servers
As a project scales, the number of concurrent users will make it infeasible for a single server to manage the subscriptions for every client (assuming that they access different parts of the database, and/or that the user count is so high that merely pushing out the deltas of shared tables to everyone is too much). Thus, it will be necessary to support having multiple live-query servers running, each handling a subset of the subscriptions.
That's not enough though; you have to also partition the notifications of changes to each live-query server, so that the query-matching itself does not create a bottleneck.
The fully horizontally-scalable solution (with multiple servers, partitioned by both query and object-id) is briefly described and visualized here.
4) When a subscription-query's result changes, send only the delta to the client, rather than the whole list
This may require holding a buffer of recent changes, to reliably send it to all of the subscribed clients. This would have some overhead; but, one way or another, Firestore and InvaliDB have proven that the delta-sending approach is workable. (I've confirmed with chrome's dev-tools that Firestore only sends the deltas, and I know the same is true for InvaliDB.)
It also requires a change on the client side, to be able to receive the "delta" and apply it to its own in-browser cache. (it's possible there exists an Apollo library for this sort of thing that could be utilized)
That said, this optimization still seems to be the easiest of the four to implement, as it doesn't require special permission checks, nor does it require communication between the database server and "live query" servers.
It's also arguably the most relevant for early usage, as you're going to see immediate reductions in network bandwidth/costs (eg. by 99%, for single-row changes to a 100 item collection that has live-query subscriptions), versus performance limits you'd merely hit later down the road (relating to query-matching and such within your servers, as optimized by entries 1-3).
All in all, there's quite a lot of work required to get the performance of Postgraphile's live-queries on par with that of Firestore or InvaliDB. Realistically, I will probably give up before I implement all four. 😅 That said, even if only one or two are managed to be implemented, they should still provide some meaningful performance benefits -- perhaps enough to make live-queries more generally usable.
Anyway, if anyone's interested in taking on one or more or these tasks, let me know and I'll focus on the others.
In the meantime, I'll look into what steps are required for implementing optimization 4. (since it seems the most straightforward)
benjie
Feature description
The live-query feature is impressive, but it appears to be lacking a number of optimizations needed for high scalability.
I know that most functionality that's achieved through live-queries can be approximated through use of the more efficient TRIGGER/NOTIFY subscriptions; however, the live-query approach is much more "elegant" in my view, and it requires less "wiring" to set up each time.
Because live-queries are not a high-priority feature for most developers, I expect that I will need to develop most of the optimizations myself. This will probably be a lot of work, but I'd like to give a try at it, as if I manage it, I can then benefit from the optimizations in all my future projects. (as well as the ~half dozen projects I currently have on Firestore that I plan to migrate)
This thread is my attempt to list those potential optimizations, discuss them, and eventually attempt to develop support for them. (either by enhancing the existing subscription-lds plugin, or creating a new plugin that sits on top of it)
Motivating example
What motivated this feature request for me, is that I am attempting to transition a project from Google Firestore to Postgraphile + Postgres, and its codebase is heavily reliant on the live-query functionality that Firestore supports.
I'm not in a rush to complete the transition (the current site works fine for now), but I would like to gradually extend Postgraphile until its live-query support can scale to a level comparable to Firestore. (granted, it will likely be more expensive and require horizontal-scaling/dedicated-live-query-servers, but that's acceptable)
Like mentioned, most developers seem to get by with the simpler TRIGGER/NOTIFY subscriptions. However, I think if the live-query functionality were optimized enough that you could use it on larger production sites, a lot more developers would be interested in using it.
From what I understand, Firebase/Firestore and Baqend/InvaliDB are the only two database solutions which have thoroughly scalable live-queries at the moment. And as Firestore and InvaliDB are both proprietary, this makes scalable live-query support in Postgraphile particularly desirable.
The Medium article above, written by Wolfram Wingerath (the developer of InvaliDB's live-query solution), explains what some of those necessary optimizations are. (beyond the Medium article, he's also written papers on the subject, which describe the challenges and solutions in greater depth)
Breaking changes
It depends on the implementation details. The optimizations will likely require some architectural extensions (eg. the concept of "partitioned live-query servers"), but most of these changes should be able to be implemented in external packages, rather than the subscription-lds and lds packages themselves. (For now, I'll just maintain an independent fork with the changes needed.)
Supporting development
I [tick all that apply]:
My next post will attempt to describe what some of the desired optimizations are.