This page describes Incremental View Maintenance (IVM) proposed in pgsql-hackers.

Overview

PostgreSQL has supported materialized views since 9.3. This feature is used to speed up query evaluation by storing the results of specified queries. One problem of materialized view is its maintenance. Materialized views have to be brought up to date when the underling base relations are updated.

Incremental View Maintenance (IVM) is a technique to maintain materialized views which computes and applies only the incremental changes to the materialized views rather than recomputing the contents as the current REFRESH command does. This feature is not implemented on PostgreSQL yet. Implementing this into PostgreSQL core was proposed firstly at PgCon 2013 Developer Meeting and [1][2]. There were also other discussions on IVM [3] [4]. The first patch was submitted in 2019[5].

Basic Theory of IVM

IVM computes and applies only the incremental changes to the materialized views. Suppose that view V is defined by query Q over a state of base relations D. When D changes D' = D + dD, we can get the new view state V' by calculating from D' and Q, and this is re-computation performed by REFRESH MATERIALIZED VIEW command. On the other hand, IVM calculates the delta for view (dV) from the base tables delta (dD) and view definition (Q), and applies this to get the new view state, V' = V + dV.

In theory, the view definition is described in a relational algebra (or bag algebra) form. For example, a (inner) join view of table R and S is defined as V = R ⨝ S.

When table R is changed in a transaction, this can be described as R ← R - ∇R + ΔR, where ∇R and ΔR denote tuples deleted from and inserted into R, respectively. (To be accurate, instead of - and +, ∸ and ⨄ are used by tradition in bag algebra.) In this condition, the deltas of the view are calculated as ∇V = ∇R ⨝ S and ΔV = ΔR ⨝ S, then the view can be updated as V ← V - ∇V + ΔV.

Multiple Tables Modification

For example, suppose that we have a view V joining table R,S and T, and new tuples are inserted to each table, dR, dS, and dT respectively.

V = R*S*T
R_new = R + dR
S_new = S + dS
T_new = T + dT

In this situation, we can calculate the new view state as below.

V_new 
 = R_new * S_new * T_new
 = (R + dR) * (S + dS) * (T + dT)
 = R*S*T + dR*(S + dS)*(T + dT) + R*dS*(T + dT) + R*S*dT
 = V + dR*(S + dS)*(T + dT) + R*dS*(T + dT) + R*S*dT
 = V + dV

So, the delta for view becomes

dV = dR*(S + dS)*(T + dT) + R*dS*(T + dT) + R*S*dT.

After we expand the right hand, the number of terms become 2^3-1 (= 7), so naively we have to perform seven joins in order to calculate the delta. However, if we can use both of pre-update state (R, S, and T) and post-update state (R_new, S_new, and T_new), we only need only three joins.

dV = dR*new_S*new_T + R*dS*T_new + R*S*dT

Self Join

When a base table is modified on self-join views, this is essentially the same as the case of multiple tables modification. Therefore, we can calculate the delta using pre- and post-state of the base table. For example,

V = R*R*R
R_new = R + dR

V_new = V + dV
dV = dR*new_R*new_R + R*dR*R_new + R*R*dR

How to extract changes on base tables

There are at least two approaches. One is using AFTER triggers and Transition Tables, which is a feature of AFTER trigger introduced from PostgreSQL 10. This was implemented originally aiming to support IVM, and in fact the proposed patch uses this. This enables collect row sets that include all of the rows inserted, deleted, or modified by the current SQL statement. These row sets can be referred as tables of specified name. OLD TABLE contains the before-images of all rows updated or deleted by the statement. Similarly, NEW TABLE contains the after-images of all rows updated or inserted by the statement. These two tables correspond ∇R and ΔR, respectively.

Another candidate is using logical decoding of WAL.

How to calculate the delta to be applied to materialized views

This is basically based on relational algebra or bag algebra. In theory, we can handle various view definition. Views can be defined using several operations: selection, projection, join, aggregate, union, difference, intersection, etc. If we can prepare a module for each operation, there is possibility of extensive implementation of IVM.

However, we started from a simple view definition. The proposed patch currently supports selection-projection-join and some aggregates.

When to maintain materialized views

There are two approaches, immediate maintenance and deferred maintenance.

Immediate View Maintenance

In immediate maintenance, views are updated in the same transaction where the base table is updated.

The proposed patch implements a kind of immediate maintenance, that is, materialized views are updated immediately in AFTER triggers when a base table is modified. SQL statement modify only one base table and the changes can be extracted by using Transition Tables mentioned above.

In addition, there could be another implementation of Immediate Maintenance, in which materialized views are updated at the end of a transaction that modified base table, rather than in AFTER trigger. Oracle supports this type of IVM. To implement this, we will need a mechanism to maintain change logs on base tables as well as Deferred maintenance as said bellow.

Deferred View Maintenance

In deferred maintenance, views are updated after the transaction is committed, for example, when the view is accessed, as a response to user command like REFRESH, or updated periodically, and so on.

In order to implement "deferred", it is need to implement a mechanism to maintain logs for recording changes of base tables. An algorithm to compute the delta to be applied to views are also to be considered because more than one tables could be modified a lot of times before a view is updated.

How to handle views with tuple duplicates or DISTINCT clause

We need some considerations to support materialized views including duplicate tuples or DISTINCT clause in its definition query.

For example, if there are two same tuples in a view and we would like to delete only one tuple rather than both of two. In this situation, we can not use DELETE statement simply, because this will delete both of tow tuples.

As another example, suppose a materialized view is defined with DISTINCT and there are duplicate tuples in its base table. The duplicates in the base table are eliminated due to DISTINCT. Then, when we would like to apply delta tables to this view, how we should update the view? When deleting tuples from the base table, a tuple in the view should be deleted if and only if the duplicity of the tuple becomes zero. Else, the tuple must remain in the view. Moreover, as for tuple insertion, we can insert a tuple into the view only if the same tuple doesn't exist in the view. If there is already the same one, additional tuple must not be inserted since duplicate is not allowed.

counting algorithm

Counting algorithm is an algorithm for handling tuple duplicates or DISTINCT clause in IVM. In this algorithm, the number of same tuples is counted and stored in the materialized views as duplicity of each tuple. When tuples are to be inserted into the view, the count is increased if there is already the same one. Otherwize, if the same tuple doesn't exist, a new tuple is inserted. Similarly, when tuples are to be deleted from the view, the count is decreased. If the count becomes zero, this tuple is deleted from the view.

How to identify rows to be modified in materialized views

When applying the delta to materialized views, we have to identify which tuple in materialized views is corresponding to a tuple in the delta. A naive method is matching by using all columns in a tuple, but clearly this is inefficient. If a materialized view has unique index, we can use this. Any way, for efficient IVM, appropriate index will be necessary on the materialized view. Maybe, REPLICA IDENTITY (or something similar) is useful.

Implementation details

This section describes details of the proposed patch's implementation

This patch implements a kind of Immediate Maintenance of materialized views. If a materialized view created with IVM option, the contents of this view is updated automatically and incrementally after base tables are updated.

Creating Materialized Views

Materialized view with IVM option created by CRATE INCREMENTAL MATERIALIZED VIEW command. Noted this syntax is just tentative, so it may be changed.

CREATE [INCREMANTAL] MATERIALIZED VIEW xxxxx AS SELECT ....;

For example, like this:

CREATE INCREMENTAL MATERIALIZED VIEW mv AS
   SELECT device_name, pid, price
   FROM devices d
   JOIN parts p
       ON d.pid = p.pid;

When a materialized view is created, AFTER triggers are automatically internally created on its all base tables. These are created for INSERT, DELETE, and UPDATE command as a statement level trigger, and with Transition Tables. When the base tables is modified (INSERT, DELETE, UPDATE), this view is updated incrementally in the trigger function. For example, like this:

   SELECT count(*) AS __ivm_count__, 
          device_name, pid, price
   FROM devices d
   JOIN parts p
       ON d.pid = p.pid
   GROUP BY device_name, pid, price;

Maintenance of Materialized View

When base tables are modified, the change set of the table can be referred as Ephemeral Named Relations (ENRs) thanks to Transition Table. We can calculate the diff set of the view by replacing the base table in the view definition query with the ENR (at least if it is Selection-Projection -Join view). As well as view definition time, GROUP BY and count(*) is added in order to count the duplicity of tuples in the diff set. As a result, two diff sets (one contains tuple to be deleted from and another contains tuples to be inserted into the view) are calculated, and the results are stored into temporary tables respectively. For example, when devices table is modified, the view delta can be calculated by the following query:

SELECT count(*) AS __ivm_count__, device_name, pid, price
FROM table_delta d
JOIN parts p
   ON d.pid = p.pid
GROUP BY device_name, pid, price;

The view is updated by applying these change sets.

Views without DISTINCT

When deleting tuples from the view, tuples to be deleted are identified by joining the delta table with the view, and the tuples are deleted as many as specified multiplicity by numbered using row_number() function, like this:

DELETE FROM mv WHERE ctid IN (
 SELECT tid FROM (
    SELECT row_number()
                OVER (PARTITION BY c1, c2, ...) 
                AS __ivm_row_number__,
           mv.ctid AS tid,
           diff.__ivm_count__
    FROM mv, old_delta AS diff
    WHERE mv.c1 = diff.c1 AND mv.c2 = diff.c2 AND ... ) v
WHERE v.__ivm_row_number__ <=  v.__ivm_count__;

When inserting tuples into the view, tuples are duplicated to the specified multiplicity using generate_series() function, like this.

INSERT INTO mv SELECT c1, c2, ... FROM (
  SELECT diff.*, generate_series(1, diff.__ivm_count__)
    FROM new_delta AS diff) AS v;

Views with DISTINCT

The values of __ivm_count__ column in the view is decreased or increased. When the values becomes zero, the corresponding tuple is deleted from the view.

Views with Aggregate

Currently, built-in count sum, avg, min, and max are supported.

As a restriction, expressions specified in GROUP BY must appear in the target list of views because tuples to be updated in materialized views are identified by using this group keys. However, in the case of aggregates without GROUP BY, there is only one tuple in the view, so keys are not uses to identify tuples.

When creating a materialized view, in addition to __ivm_count column, more than one hidden columns for each aggregate are added to the target list. For example, names of these hidden columns are ivm_count_avg and ivm_sum_avg for the average function.

In the case of views with DISTINCT, only the number of tuple duplicates (__ivm_count__) are updated at incremental maintenance. On the other hand, in the case of vies with aggregates, the aggregated values and related hidden columns are also updated. The way of update depends the kind of aggregate function.　Specifically, sum and count are updated by simply adding or subtracting delta value calculated from delta tables. avg is updated by using values of sum and count stored in views as hidden columns and deltas calculated from delta tables.

In min or max cases, it becomes more complicated. For an example of min, when tuples are inserted, the smaller value between the current min value in the view and the value calculated from the new delta table is used. When tuples are deleted, if the current min value in the view equals to the min in the old delta table, we need re-computation the latest min value from base tables. Otherwise, the current value in the view remains.

As to sum, avg, min, and max (any aggregate functions except to count), NULL in input values is ignored, and this returns a null value when no rows are selected. To support this specification, the number of not-NULL input values is counted and stored in views as a hidden column. In the case of count(), count(x) returns zero when no rows are selected, and count(*) doesn't ignore NULL input. These specification are also supported.

count(x) <-- count(x) +/- [count(x) from delta table]
sum(x) <-- sum(x) +/- [sum(x) from delta table]
   (However, this becomes NULL if count(x) results in 0.)
avg(x) <-- (sum(x) +/- [sum(x) from delta]) / (count(x) +/- [count(x) from delta])
   (NULL if count(x) results in 0.)
min/max:
 When tuples are inserted:
   min(x) <-- least (min(x), [min(x) from delta table])
   max(x) <-- greatest (max(x), [max(x) from delta table])
 When tuples are deleted:
   If the old min(x) or max(x) is deleted from the view, it needs recomputing the new value from base tables.

Self Joins and Multiple Tables Modification

Multiple tables can be modified when modifying CTEs, triggers, or foreign key constrains is used. For example,

WITH x AS (INSERT INTO r VALUES(1,10) RETURNING 1), 
     y AS (INSERT INTO s VALUES(1,100) RETURNING 1) 
SELECT 1;

Self-join is a essentially the same situation since same tables in a query can be regarded as different tables with the same contents, so we can handle these in the same algorithm. Similar way would be useful when we implement Deferred-maintenance in future.

AFTER triggers are used to collecting tuplestores containing transition table contents for each modified base table. So, when multiple tables are changed, multiple AFTER triggers are invoked, then the final AFTER trigger performs actual update of the matview. In addition AFTER trigger, also BEFORE trigger is used to handle global information for view maintenance.

To calculate view deltas, we need both pre-state and post-state of base tables. Post-update states are available in AFTER trigger. We calculate pre-update states by filtering inserted tuples using cmin/xmin system columns, and appending deleted tuples which are contained in a old transition table, for example, as bellow. pre_xid and pre_cid are TransactionID and CommandID before the table is changed, respectively. These are captured in BEFORE trigger.

SELECT t.* FROM mytbl t
  WHERE (age(t.xmin) - age(pre_xid::text::xid) > 0) OR
        (t.xmin = pre_xid AND t.cmin::text::int < pre_cid)
 UNION ALL
SELECT * FROM old_delta

Lifespan of Transition Tables

In the original PostgreSQL, tuplestores of transition tables are freed at the end of each nested query. However, their lifespan is prolonged to the end of the out-most query in our IVM implementation because transition tables generated in nested queries are used to calculate view deltas in the last AFTER trigger. For this purpose, SetTransitionTablePreserved is added in trigger.c.

Outer Join Support

In case of outer-joins, additionally to deltas which occur in inner-join case we need additional delete or insert of dangling tuples, that is, null-extended tuples generated when join-condition doesn't match.

This implementation basically based on the algorithm of Larson & Zhou (2007) [1]. Before view maintenances, jointree is analysed and "view maintenance graph" is generated, which represents which tuples in the views are affected when a table is modified. Tuples on which the modified table is not null-extended are directly affected by this change. Such affects are calculated similarly to inner-joins. On the other hand, dangling tuples generated by joining (directly) affected tuples can be indirectly affected. This means that we may need to delete dangling tuples when any tuples are inserted to a table, as well as to insert dangling tuples when tuples are deleted from a table.

[1] Efficient Maintenance of Materialized Outer-Join Views (Larson & Zhou, 2007)
https://ieeexplore.ieee.org/document/4221654

Currently, we have following restrictions:

outer join view's targetlist must contain attributes used in join conditions
outer join view's targetlist cannot contain non-strict functions
outer join supports only simple equijoin
outer join view's WHERE clause cannot contain non null-rejecting predicates
aggregate is not supported with outer join
subquery is not supported with outer join

Sub-queries Support

EXISTS in WHERE clause is supported.

The row number count of the EXISTS sub-query is stored in the view as a hidden column. For example,

SELECT t1.* FROM test1 AS t1
 WHERE EXISTS (SELECT 1 FROM test2 AS t2 WHERE t1.id = t2.id);

is rewritten to

SELECT t1.* , exist_query."__ivm_exists_count_0__" 
 FROM test1 AS t1 ,
      LATERAL(SELECT 1, COUNT(*) AS "__ivm_exists_count_0__"
          FROM test2 AS t2 WHERE t1.id = t2.id
          HAVING __ivm_exists_count_0__ > 0) AS exist_query;

When a table in the sub-query (test2) is modified, if the count __ivm_exists_count_0__ becomes zero, the tuple in the view should be deleted , otherwise the tuple remains.

Also, simple sub-queries and CTEs that include only selection, projection, or inner join, are also supported.

There are some restrictions:

aggregate functions are not supported together with EXISTS.
nested subqueries are not supported.
EXISTS condition can use only with AND Expr.

Other Things

Restrictions on view definition

The current implementation supports views including selection, projection, inner and outer join, DISTINCT, and some built-in aggregates (count, sum, min, max, agv) and GROUP BY (HAVING is not supported). Self-join, simple subqueries in FROM clause, simple CTEs, and EXIST subquery in WHERE clause are also supported. Other sub-queries and CTEs, window functions, or set operations is not supported.

Incremental maintainable materialized view (IMMV) including view, materialized view or IMMV in its definition is not supported, either.

Timing of view maintenance

This patch implements only a kind of Immediate Maintenance. For implementing Deferred Maintenance, we need a infrastructure to maintain these logs. For example, which logs are necessary and which logs can be discarded, etc.

Counting algorithm implementation

The proposed patch treats columns whose name start with "__ivm_", like __ivm_count__, as a special column name in a somewhat ad hoc way. This is used when maintaining views. When "SELECT * FROM ..." is issued to views, __ivm_count__ column is invisible for users. Note that users can not use this name as a user column in materialized views with IVM support. As for how to make internal columns invisible to SELECT *, there have been other discussions about doing that using a new flag in pg_attribute[6].

Concurrent Transactions

When a view is defined on two tables and each table is modified in different concurrent transactions respectively, if a change in one transaction was not considered in another transaction in READ COMMITTED level, an anormal update of the materialized view would be possible. To prevent this, a lock on the materialized view is taken in early stage of view maintenance to wait for concurrent transactions which are updating the same view to end. Also, the latest snapshot is taken before computing delta tables to make any changes which occurs in other transaction during lock waiting visible.

In REPEATABLE READ or SERIALIZABLE level, don't wait a lock, and raise an error immediately to prevent anormal update because table changes occurred in other transactions must not be visible, and views can not be maintained correctly in AFTER triggers.

These solutions might be ugly, but something to prevent anormal update is anyway necessary. There may be better way. One idea to resolve this is performing view maintenance in two phases. Firstly, views are updated using only table changes visible in this transaction. Then, just after this transaction is committed, views have to be updated additionally using changes happened in other transactions to keep consistency. This is a just idea, but to implement this idea, we will need keep to keep and maintain change logs.

Links

CommitFest

Incremental Materialized View Maintenance

Talks

Wiki

pgsql-hackers

pgsql-general

Incrementally refreshed materialized view

Some relevant papers

Maintaining View Incrementally -- describes the counting algorithm, and the DRed algorithm for recursive views
Maintenance of Materialized Views: Problems, Techniques, and Applications -- surveys all techniques known in the 90s

Incremental View Maintenance