Use ideas from Incremental View Maintenance to know what has changed

[mitar]

Instead of doing a full refresh when any of the sources changes, we could based on what changes in the source compute how does (and if) this influence current results. There is some work for materialized views on how to do that, known as Incremental View Maintenance.

There are two main questions:

• How to know/store what exactly changed.
• How to map that to how results change.

Then we can update both our temporary cache table and send those changes to the client. Instead of doing a full refresh. And only if we do not know how to map new inputs to new results, we do a full refresh.

There are some related projects which could help here:

• https://github.com/ntqvinh/PgMvIncrementalUpdate
• https://github.com/twosigma/postgresql-contrib
• https://www.postgresql.org/message-id/flat/20181227215726.4d166b4874f8983a641123f5%40sraoss.co.jp

It might be necessary to parse and rewrite the query, for which this could help.

[mitar]

Attaching the paper describing above code.

QuocVinh2016_Article_SynchronousIncrementalUpdateOf.pdf

Also see:

• Provide a way to compute updates to a set of results when sources change ntqvinh/PgMvIncrementalUpdate#4
• Provide a version for Linux ntqvinh/PgMvIncrementalUpdate#3
• Please improve documentation ntqvinh/PgMvIncrementalUpdate#2

[ntqvinh]

Dear all,

Unfortunately i don't understand node.js. Anyway i think a MS-notification-service-like service for PostgreSQL will be very useful. If there is similar service, you can implement ASYNchronous programming to dramatically improve the performance of the system. We have naive thing like that for C# here: http://it.ued.udn.vn/chuyen-giao-cong-nghe/498-2015-08-03-17-51-21 (http://it.ued.udn.vn/myprojects/pgNotiServ/postgresql-notification-2014.rar).

[mitar]

Interesting. It really looks like we have similar interests. :-) Yes, node.js is chosen because it is great at asynchronous programming. So I would love to implement something like this in node.

[mitar]

An interesting read is how they do this in Hasura. Some notes:

• They also see this similar to materialized view maintenance.
• They currently re-run queries and do not do do incremental updates (same as this package currently).
• They do not use triggers (like this package can do) but use regular refresh interval.
• They do some additional things to batch queries together. Like merge same query with different parameters (like user ID) together. This package does not do any such optimizations.

So a takeaway could be that if you optimize query ru-running enough, maybe incremental updates are not really necessary?

[mitar]

Some other related projects:

• https://www.graphile.org/postgraphile/live-queries/ (one of many projects using replication stream of changes, this one re-runs queries based on changes detected from replication change stream)
• https://github.com/supabase/realtime (using replication stream of changes to broadcast them to clients)
• https://rxdb.info/query-change-detection.html (uses replication stream of changes but knows how to map that to updates to queries)

[mitar]

Noria is a caching layer where the main design is in fact incremental and efficient updating of materialized views. Very similar to what this issue is about.

[mitar]

event-reduce optimizes repeating queries.

[mitar]

Also related is InvaliDB.

[Venryx]

I've read (parts of some of) the papers on the InvaliDB solution (eg. http://www.vldb.org/pvldb/vol13/p3032-wingerath.pdf), and so far it's the most complete solution I've seen for the problem so far.

Unfortunately, it is closed-source, so is not directly usable outside of the Baqend service; that said, the papers go into a good amount of detail on the design of the system, so it's still a helpful resource for those attempting to build an equivalent open-source solution.