Incremental View Maintenance

From PostgreSQL wiki

Jump to: navigation, search

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

Contents

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 bellow.

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.

When a materialized view is created, AFTER triggers are internally created on its all base tables. When the base tables is modified (INSERT, DELETE, UPDATE), this view is updated incrementally in the trigger function.

Before populating the materialized view, GROUP BY and count(*) are added to the view definition query for counting duplicity of tuples in the view. The result of count is stored in the view as a special column named "__ivm_count__".

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 (to be deleted from and to be inserted into the view) are calculated, and the results are stored into temporary tables respectively.

The view is updated by merging these change sets. Instead of executing DELETE or INSERT simply, 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.

Self Joins and Multiple Tables Modification

Supporting self-join views and multiple tables modification are essentially the same problem, 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

Life Span of Transition Tables

In the original core implementation, tuplestores of transition tables were freed for each query depth. However, we want to prolong their life plan because we have to preserve these for a whole query assuming some base tables are changed in other trigger functions, so I added a hack to trigger.c.

Aggregate support

Currently, count sum, min, max and avg 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 without aggregate functions, 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.

Access to Materialized Views

When SELECT is issued for materialized views with IVM support defined with DISTINCT, all columns except to __ivm_count__ of each tuple are returned. This is correct because duplicity of tuples are eliminated by GROUP BY.

When DISTINCT is not used, the query returns each tuple __ivm_count__ times. Currently, this is implemented by rewriting the SELECT query to replace the view RTE with a subquery which joins the view and generate_series function as bellow.

SELECT mv.* FROM mv, generate_series(1, mv.__ivm_count__);

__ivm_count__ column is invisible for users when "SELECT * FROM ..." is issued, but users can see the value by specifying in target list explicitly.


Restrictions on view definition

The current implementation supports views including selection, projection, inner join with or without DISTINCT, and some aggregates (count, sum, min, max, agv) and GROUP BY (HAVING is not supported). Self-join is also supported. Subquery support and outer join support are on our plan. CTE and window functions are not supported.

Incremental materialized view on view, materialized view or incremental materialized view are not supported.

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 "__ivm_count__" as a special column name in a somewhat ad hoc way. This is used when maintaining and accessing materialized 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].

When a materialized view with duplicate tuples is accessed, this is replaced with a subquery which uses generate_series function. It does not have to be generate_series, and we can make a new set returning function for this. Anyway, this internal behaviour is visible in EXPLAIN results as below.

postgres=# EXPLAIN SELECT * FROM m1;
                                  QUERY PLAN                                  
------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..61.03 rows=3000 width=2)
   ->  Seq Scan on m1 mv  (cost=0.00..1.03 rows=3 width=10)
   ->  Function Scan on generate_series  (cost=0.00..10.00 rows=1000 width=0)
(3 rows)

Also, there would be performance impact because estimated rows number by optimizer is wrong, and what is worse, the cost of join is not small when the size of view is large. Therefore, we might have to add a new plan node for selecting from materialized views with IVM support rather than using a special set returning function.

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

Talks

Wiki

pgsql-hackers

pgsql-general

Personal tools