Toward Implementing
Incremental View Maintenanceon PostgreSQL

Yugo Nagata @ SRA OSS, Inc. Japan.
PGCon 2019
- May 31, 2019

Who am I●

Yugo Nagata– Engineer at SRA OSS, Inc. Japan●

PostgreSQL experiences– Technical support– consulting– Education– R&D

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

2

Outline●●●

Introduction–

Views and materialize views–

Incremental View Maintenance (IVM)

Implementing IVM on PostgreSQL–

What to be considered to implement IVM–

Work-in-Progress patch–

How it works

Examples–●Performance Evaluation

Discussions
Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

3

What is Incremental View
Maintenance (IVM)

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

4Views
CREATE VIEW V AS
SELECT device_name, pid, price
FROM devices dJOIN parts p
ON d.pid = p.pid;

V
name
G1
G2
G3

pid
P1
P1
P2

*
●

A view is a virtual relation
defined by a query on basetables.
–●device
name
G1
G2
G3

pid
P1
P1
P2

price
10
10
20

JOIN

parts
pid
P1
P2

price
10
20

Only the definition query is
stored.

The result is computed whena query is issued to a view.

Table data

Table data

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

5

Materialized Views
CREATE MATERIALIZED VIEW V AS
SELECT device_name, pid, price
FROM devices dJOIN parts p
ON d.pid = p.pid;

V
name
G1
G2
G3

Materialized view
data
pid
P1
P1
P2

*
●

●

Materialized views persist theresults in a table-like form.
No need to compute the result
when a query is issued.

device
name
G1
G2
G3

pid
P1
P1
P2

price
10
10
20

JOIN

parts
pid
P1
P2

price
10
20

– Enables faster access to data.
●

The data is not always up to date.
– Need maintenance.

Table data

Table data

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

6

Creating Materialized Views
CREATE MATERIALIZED VIEW V AS
SELECT device_name, pid, price
FROM devices dJOIN parts p
ON d.pid = p.pid;

●

●

V
name
G1
G2
G3

Materialized view
data
pid
P1
P1
P2

*

The data of a materialized view iscomputed at definition time.
–

This is similar to “CREATE TABLE
AS” statement.

–

The result of the definition query isinserted into the materialized view.

Need maintenance to keep
consistency between thematerialized data and base tables.

device
name
G1
G2
G3

pid
P1
P1
P2

Table data

price
10
10
20

insert

JOIN

parts
pid
P1
P2

price
10
20

Table data

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

7

Refreshing Materialized Views
V
name
G1
G2
G3

REFRESH MATERIALIZED VIEW V;

Materialized view
data
pid
P1
P1
P2

price
10
10
20

insertreplace●●

Need to re-compute theresult of the definition
query.
Replacing the thecontents of a materialized
view with the result.

*device
name
G1
G2
G3

pid
P1
P1
P2

Table data

JOIN

parts
pid
P1
P2

temporary table
price
10
20

Table data

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

8

Refreshing Materialized Views
V
name
G1
G2
G3

REFRESH MATERIALIZED VIEW CONCURRENTLY V;

Materialized view
data
pid
P1
P1
P2

price
10
10
20

insert

merge
diff

●

●

With CONCURRENTLY
option, the materialized viewis refreshed without locking
out concurrent selects on the
view.

*

device
name
G1
G2
G3

pid
P1
P1
P2

JOIN

parts
pid
P1
P2

temporary table
price
10
20

Need to re-compute the resultof the definition query, too.
Table data

Table data

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

9

Incremental View Maintenance●

Incremental View Maintenance (IVM)–

Compute and apply only the incremental changes to thematerialized views
Changes of

V =Q v ( D)u

δ (V )

materialized view

Incremental maintenanceMaterialized view

View
definition

Base
Baserelations
relations

Qv

D

Changes ofbase tablesδ u ( D)u

recomputation

IVM

V new =Qv ( D ')UpdatedUpdatedmaterializedbase relations
View

Qv
Refreshing

D '=u ( D )UpdatedBaserelations
relationsbase

Update query
Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

10Basic Theory of IVM●

View definition–●

SELECT * FROM R NATURAL JOIN S;

Ex.) Natural join view
V≝R⋈S

Change on a base tableR ← (R − ∇R ∪ ∆R)

●

R, S
∇R
∆R

base tables
deleted tuples
inserted tuples

Calculation of change on view
∇V = ∇R ⋈ S∆V = ∆R ⋈ S●

Apply the change to the viewV ← (V − ∇V ∪ ∆V)
Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

11

Basic Theory of IVM: Example (1)RS
numbernumberenglish

roman

1

one

1

I

2

two

2

II

3

three

3

III

naturaljoin

V≝R⋈S
numberroman

english

1

one

I

2

two

II

3

three

III

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

12Basic Theory of IVM: Example (2)Table R is changedR ← (R − ∇R ∪ ∆R)
numberS
numberenglishroman

1

one → ONE

1

I

2

two

2

II

3

three

3

III
Calculate changes on view V∇Rnumber1

englishnatural
join

one

1

number1∆R
number∇V = ∇R ⋈ S

englishONE

naturaljoin

english
one

roman
I

∆V = ∆R ⋈ S
number1

roman

englishONE

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

I
13

Basic Theory of IVM: Example (3)∇V∆Vnumberroman

englishone

1

numberI

1
deleteONE

I

insertV ← (V − ∇V ∪ ∆V)
englishnumberroman

englishroman

1

one → ONE

I

2

two

II

3

three

III

View V is update by applying
the calculated changes

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

14

Implementing IVM on PostgreSQL

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

15

Considerations implementing IVM (1)●●How to extract changes on base tables–

AFTER trigger and Transition Tables–

Logical decoding of WAL is another idea.

How to compute the delta to be applied to materialized views–

Basically, based on relational algebra (or bag algebra).

–

Starting from a simple view definition:●

Selection-Projection-Join views

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

16

Considerations implementing IVM (2)●When to maintain materialized views–

Immediate maintenance:

The materialized view is updated in the same transaction where thebase table is updated.
– Deferred maintenance:●●

The materialized view is updated after the transaction is committed– When view is accessed– As a response to user command (like REFRESH)– periodically– etc.

●How to handle views with tuple duplicates or DISTINCT clause
Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

17Views with Tuple Duplicates
SELECT english, roman
FROM R JOIN S USING (id);Venglish

∇V

roman

one

I

two

II

two

II

three

III

deleteenglish
two

roman
II

●

Only one tuple of duplicated two must be deleted.

●

DELETE statement can not be used because this delete two tuples.
Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

18Views with DISTINCT clause
SELECT DISTINCT english, greek
FROM R JOIN S USING (id);V∇Venglish

roman

one

I

two

II

three

III

II

two
insert?

roman

englishdelete?

∆Vromanenglish
three

III

●

A tuple is deleted if and only if duplicity of the tuple becomes zero.

●

Additional tuple can not be inserted if there is already the same one.
Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

19

IVM Implementation using OIDs
(PGConf.EU 2018)●

PoC (Proof of Concept) implementation–

Using row OIDs as “primary keys” of tuples in a materialized
view–

This can handle views with tuple duplicates correctly.
●–●

DISTINCT is not supported.

Materialized views can be incrementally updated using
REFRESH command. (a kind of Deferred Maintenance)

Problems:–

OID system column is removed since PostgreSQL 12.

–

Needs many changes in executor nodes.

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

20

New IVM Implementation●

Working-in-Progress patch has been submitted●

Provides a kind of Immediate Maintenance–●Materialized views can be updated automatically andincrementally after base tables are updated.

Supports views including duplicate tuples or
DISTINCT clause in the view definition–"counting algorithm" is used
Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

21

Counting algorithm (1)●Algorithm for handling tuple duplicate or DISTINCT in IVM– The numbers of tuples are counted and this information isstored in materialized views.

When tuples are to be inserted into the view, the count increases.
When tuples are to be deleted from the view, the count decreases.
If the count becomes zero, this tuple is deleted.

V
roman

english

count

one

I

1

two

II

2

three

III

1
Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

22

Counting algorithm (2)●Algorithm for handling tuple duplicate or DISTINCT in IVM– The numbers of tuples are counted and this information isstored in materialized views.

When tuples are to be inserted into the view, the count increases.
●
When tuples are to be deleted from the view, the count decreases.
●
If the count becomes zero, this tuple is deleted.
●

∇V

V

deleteroman

english

count

one

I

1

two

II

2→1

three

III

1→2

englishtwoinsert

count

roman
II

1

∆V
englishthree

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

count

roman
III

1
23

How it works

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

24

Creating materialized views (1)●CREATE INCREMENTAL MATERIALIZED VIEW–

Creates matrialized views which is updated
automatically and incrementally after base tables arechanged–This syntax is just tentative, so it may be changed.
CREATE INCREMENTAL MATERIALIZED VIEW MV AS
SELECT device_name, pid, price
FROM devices dJOIN parts p
ON d.pid = p.pid;

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

25

Creating materialized views (2)●When populating the matrialized view:–

The number of tuples are counted by adding count(*)
and GROUP BY to the query.

–

The result of count is stored in the matview as a special
column named "__ivm_count__".
CREATE INCREMENTAL MATERIALIZED VIEW MV AS
SELECT count(*) AS __ivm_count__,
device_name, pid, price
FROM devices dJOIN parts p
ON d.pid = p.pid
GROUP BY device_name, pid, price;

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

26

Creating materialized views (3)●●AFTER triggers are created on the all base tables.
–

For INSERT, DELETE, and UPDATE–Statement level trigger–

With Transition Tables

Triggers are Created automatically and internally rather thanissuing CREATE TRIGGER statement.
–

Similar to the implementation of foreign key constrains

Example of an equivalent query:
CREATE TRIGGER IVM_trigger_upd_16598
AFTER UPDATE ON devises
REFERENCING NEW TABLE AS ivm_newtable OLD TABLE AS ivm_oldtable
FOR EACH STATEMENTEXECUTE FUNCTION IVM_immediate_maintenance(‘public.mv’);
Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

27

Transition Tables
CREATE TRIGGER IVM_trigger_upd_16598
AFTER UPDATE ON devises
REFERENCING NEW TABLE AS ivm_newtable OLD TABLE AS ivm_oldtable
FOR EACH STATEMENTEXECUTE FUNCTION IVM_immediate_maintenance(‘public.mv’);●●This is a feature of AFTER trigger since PostgreSQL 10.
Changes on tables can be referred in the trigger function using
table names specified by REFERENCING clause.
–

ivm_oldtable contains tuples deleted from the table in a statement.

–

ivm_newtable contains tuples newly inserted into the table.

–

In theory, corresponding ∇R and ∆R respectively.

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

28

Calculating Changes on Views●●

Calculate the changes on the materialized view by:–

Replacing the base table in the view definition query with thetransition table.

–

Using count(*) and GROUP BY to count the duplicity of tuples.

The results are stored into temporary tables. (as ∇V and ∆V)
CREATE TEMPORARY TABLE tempname_old AS
SELECT count(*) AS __ivm_count__, device_name, pid, price
FROM ivm_oldtable dJOIN parts p
ON d.pid = p.pid
GROUP BY device_name, pid, price;
CREATE TEMPORARY TABLE tempname_new AS
SELECT count(*) AS __ivm_count__, device_name, pid, price
FROM ivm_newtable dJOIN parts p
ON d.pid = p.pid
GROUP BY device_name, pid, price;
Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

29

Applying Changes to View (1)●The materialized view is updated by merging the
calculated changes.
–

For each tuple in the change:

If the the corresponding tuple already exists, the value of__ivm_count__ column in the view is updated●
Rather than executing DELETE or INSERT simply– When the values becomes zero, the corresponding tuple isdeleted.
●–Using modifying CTE (WITH clause)

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

30

Applying Changes to View (2)●Decrease __ivm_count__, or delete an old tuple
WITH t AS (SELECT diff.__ivm_count__,(diff.__ivm_count__ = mv.__ivm_count__) AS for_dlt,
mv.ctid
FROM matview_name AS mv, tempname_old AS diff
WHERE (mv.device_name, mv.pid, mv.price)= (diff.device_name, diff.pid, diff.price)),
updt AS (UPDATE mateview_name AS mv
SET __ivm_count__ = mv.__ivm_count__ - t.__ivm_count__
FROM t
WHERE mv.ctid = t.ctid AND NOT for_dlt)
DELETE FROM matview_name AS mv
USING t
WHERE mv.ctid = t.ctid AND for_dlt;
Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

31

Applying Changes to View (3)●Increase __ivm_count__, or Insert a new tuple
WITH updt AS (UPDATE matview_name AS mv
SET __ivm_count__ = mv.__ivm_count__ + diff.__ivm_count__
FROM temptable_new AS diff
WHERE (mv.device_name, mv.pid, mv.price)= (diff.device_name, diff.pid, diff.price)
RETURNING diff.device_name, diff.pid, diff.price)
INSERT INTO matview_name(SELECT * FROM temptable_new AS diff
WHERE (diff.device_name, diff.pid, diff.pric)
NOT IN (SELECT * FROM updt));

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

32

Access to materialized views●

When SELECT is issued for materialized views with IVM:
– case 1: Defined with DISTINCT:All columns (except to __ivm_count__) of each tuple are
returned.
●
Duplicity of tuples are already eliminated by GROUP BY.
●– case 2: DISTINCT is not used:

Returns each tuple __ivm_count__ times.
●
By rewriting the SELECT query to replace the view with a
sub-query which joins the view and generate_series
function.
●

SELECT mv.* FROM mv, generate_series(1, mv.__ivm_count__);Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

33

Examples

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

34

Example 1
postgres=# CREATE INCREMENTAL MATERIALIZED VIEW m AS SELECT * FROM t0;
SELECT 3
Creating a materialized view with IVM option
postgres=# SELECT * FROM m;
i
--3
2
1
(3 rows)
postgres=# INSERT INTO t0 VALUES (4);INSERT 0 1
postgres=# SELECt * FROM m;
i
--3
2
1
The view is automatically updated.
4(4 rows)

Insert a tuple into the base table.

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

35

Example 2-1
postgres=# SELECT * FROM t1;
id | t----+--1 | A
2 | B
3 | C
4 | A
(4 rows)
postgres=# CREATE INCREMENTAL MATERIALIZED VIEW m1 AS SELECT t FROM t1;
SELECT 3
postgres=# SELECT * FROM m1;t--A
Creating a materialized view with tuple duplicatesAC
B(4 rows)
Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

36

Example 2-2
postgres=# INSERT INTO t1 VALUES (5, 'B');
INSERT 0 1
Inserting (5,B) into
postgres=# DELETE FROM t1 WHERE id IN (1,3);
and deleting (1, A), (3, C) fromDELETE 2
the base table.
postgres=# SELECT * FROM m1;
t--The view with tuple duplicates is correctly updated.
B
Before:B
At(3 rows)--A
A
C
B(4 rows)

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

37

Example 3
postgres=# SELECT *, __ivm_count__ FROM m1;
t | __ivm_count__---+--------------__ivm_count__ column is invisible for users
B |2
when "SELECT * FROM ..." is issued,
B |
2
A |
1
but users can see this by specifying it explicitly.
(3 rows)
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)

The internal usage of generate_series
function is visible in the EXPLAIN result.
Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

38

Simple Performance Evaluation (1)●Materialized views of a simple join using pgbench tables:
Scale factor of pgbench: 100
CREATE MATERIALIZED VIEW mv_normal AS
SELECT aid, bid, abalance, bbalance
FROM pgbench_accounts JOIN pgbench_branches
USING (bid)
WHERE abalance > 0 OR bbalance > 0;
CREATE INCREMENTAL MATERIALIZED VIEW mv_ivm AS
SELECT aid, bid, abalance, bbalance
FROM pgbench_accounts JOIN pgbench_branches
USING (bid)
WHERE abalance > 0 OR bbalance > 0;

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

39

Simple Performance Evaluation (2)test=# REFRESH MATERIALIZED VIEW mv_normal ;REFRESH MATERIALIZED VIEW
Time: 11210.563 ms (00:11.211)
test=# CREATE INDEX on mv_ivm (aid,bid);
CREATE INDEX
test=# SELECT * FROM mv_ivm WHERE aid = 1;
aid | bid | abalance | bbalance-----+-----+----------+---------1 |
1 |
10 |
10
(1 row)

The standard REFRESH of mv_normal
took more than 10 seconds.

Creating an index on mv_ivm

Time: 2.498 ms
test=# UPDATE pgbench_accounts SET abalance = 1000 WHERE aid = 1;
UPDATE 1
Updating a tuple in pgbench_accounts took 18ms.
Time: 18.634 ms
test=# SELECT * FROM mv_ivm WHERE aid = 1;
aid | bid | abalance | bbalance-----+-----+----------+---------mv_ivm was updated automatically and correctly.
1 |1 |1000 |
10(1 row)
Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

40

Simple Performance Evaluation (3)test=# DROP INDEX mv_ivm__aid_bid_idx ;DROP INDEX
Time: 10.613 ms
test=# UPDATE pgbench_accounts SET abalance = 2000 WHERE aid = 1;
UPDATE 1
Time: 3931.274 ms (00:03.931)

However, if there are not indexes on mv_ivm, it
took about 4 sec.
Although this is faster than normal REFRESH,
appropriate indexes are needed onmaterialized views for efficient IVM.

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

41

Current Restrictions●

Supported:–●●

selection, projection, inner join, DISTINCT

Not supported:–

Aggregation and GROUP BY–

Self-join, sub-queries, OUTER JOIN, CTE, windowfunctions–Set operations (UNION, EXCEPT, INTERSECT)I plan to deal with some aggregations by the first release.

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

42

Timing of View Maintenance●

Currently, only Immediate Maintenance is supported:–●●

Materialized views are updated immediately when a base table is modified.

Deferred Maintenance:–

Materialized views are updated after the transaction, for example, by theuser command like REFRESH.

–

Need to implement a mechanism to maintain “logs” for recording changesof base tables and another algorithm to update materialized views.

There could be another implementation of Immediate Maintenance–Materialized views are updated at the end of a transaction that modified
base tables, rather than in AFTER trigger.

–

Needs “logs” mechanism as well as Deferred.
Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

43

About counting algorithm●●"__ivm_count__" is treated as a special column name.
–Maybe this name has to be inhibited in user tables.

–

Is it acceptable to use such columns for IVM,
or is there other better way?

generate_series function is used when materialized views with tuple
duplicates is accessed:–

We can make a new set returning function instead of generate_series.

–

Performance issues:
Planner’s estimation of rows number is wrong.
●
The cost of join with this function could be high.
●→ We might have to add a new plan node for IVM matrialized views
rather than using a set returning function.
Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

44

Other issues●●

Concurrent transactions–

When concurrent transactions modify base tables under the samematerialized view, lock waiting and race condition could occur.

–

Need more investigation

Optimization–“counting” is unnecessary if a view doesn’t have DISTINCT or
duplicates.

–

When overhead of IVM is higher than normal REFRESH, weshould use the latter.
●

Using cost estimated by optimizer
Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

45

Summary●

Our implementation of IVM on PostgreSQL–

Immediate View Maintenance using AFTER trigger–

Views with tuple duplicates or DISTINCT●●●

counting algorithm

To do:–

Aggregation and GROUP BY (for the first release of IVM)–

Deferred Maintenance–

Concurrent transaction issues–

Optimizations

Working-in-Progress patch has been submitted to pgsql-hackers–

Subject: Implementing Incremental View Maintenance
Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

46

Thank you

Copyright © 2019 SRA OSS, Inc. Japan All rights reserved.

47