Re: Implementing Incremental View Maintenance

From: Tatsuo Ishii <ishii(at)sraoss(dot)co(dot)jp>
To: nagata(at)sraoss(dot)co(dot)jp
Cc: pgsql-hackers(at)postgresql(dot)org, ishii(at)sraoss(dot)co(dot)jp, hoshiai(at)sraoss(dot)co(dot)jp, alvherre(at)2ndquadrant(dot)com, thomas(dot)munro(at)gmail(dot)com, kgrittn(at)gmail(dot)com
Subject: Re: Implementing Incremental View Maintenance
Date: 2019-11-26 07:14:21
Message-ID: 20191126.161421.2149283545283229665.t-ishii@sraoss.co.jp
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

Note that this is the last patch in the series of IVM patches: now we
would like focus on blushing up the patches, rather than adding new
SQL support to IVM, so that the patch is merged into PostgreSQL 13
(hopefully). We are very welcome reviews, comments on the patch.

BTW, the SGML docs in the patch is very poor at this point. I am going
to add more descriptions to the doc.

> Hi,
>
> Attached is the latest patch (v8) to add support for Incremental View
> Maintenance (IVM). This patch adds OUTER join support in addition
> to the patch (v7) submitted last week in the following post.
>
> On Fri, 22 Nov 2019 15:29:45 +0900 (JST)
> Tatsuo Ishii <ishii(at)sraoss(dot)co(dot)jp> wrote:
>> Up to now, IVM supports materialized views using:
>>
>> - Inner joins
>> - Some aggregate functions (count, sum, min, max, avg)
>> - GROUP BY
>> - Self joins
>>
>> With the latest patch now IVM supports subqueries in addition to
>> above.
>>
>> Known limitations are listed here:
>>
>> https://github.com/sraoss/pgsql-ivm/issues
>>
>> See more details at:
>> https://wiki.postgresql.org/wiki/Incremental_View_Maintenance
>
> * About outer join support:
>
> In case of outer-join, when a table is modified, in addition to deltas
> which occur in inner-join case, we also need to deletion or insertion of
> dangling tuples, that is, null-extended tuples generated when a join
> condition isn't met.
>
> [Example]
> ---------------------------------------------
> -- Create base tables and an outer join view
> CREATE TABLE r(i int);
> CREATE TABLE s(j int);
> INSERT INTO r VALUES (1);
> CREATE INCREMENTAL MATERIALIZED VIEW mv
> AS SELECT * FROM r LEFT JOIN s ON r.i=s.j;
> SELECT * FROM mv;
> i | j
> ---+---
> (1 row)
>
> -- After an insertion to a base table ...
> INSERT INTO s VALUES (1);
> -- (1,1) is inserted and (1,null) is deleted from the view.
> SELECT * FROM mv;
> i | j
> ---+---
> 1 | 1
> (1 row)
> ---------------------------------------------
>
> Our implementation is basically based on the algorithm of Larson & Zhou
> (2007) [1]. Before view maintenances, the view definition query's jointree
> is analysed to make "view maintenance graph". This graph represents
> which tuples in the views are affected when a base table is modified.
> Specifically, tuples which are not null-extended on the modified table
> (that is, tuples generated by joins with the modiifed table) are directly
> affected. The delta of such effects are calculated similarly to inner-joins.
>
> On the other hand, dangling tuples generated by anti-joins with 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
>
> Although the original paper assumes that every base table and view have a
> unique key and tuple duplicates is disallowed, we allow this. If a view has
> tuple duplicates, we have to determine the number of each dangling tuple to
> be inserted into the view when tuples in a table are deleted. For this purpose,
> we count the number of each tuples which constitute a deleted tuple. These
> counts are stored as JSONB object in the delta table, and we use this
> information to maintain outer-join views. Also, we support outer self-joins
> that is not assumed in the original paper.
>
> * Restrictions
>
> 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 (including EXSITS) is not supported with outer join
>
>
> Regression tests for all patterns of 3-way outer join and are added.
>
> Moreover, I reordered IVM related functions in matview.c so that ones
> which have relationship will be located closely. Moreover, I added more
> comments.
>
> Regards,
> Yugo Nagata
>
>
> --
> Yugo Nagata <nagata(at)sraoss(dot)co(dot)jp>

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Phil Florent 2019-11-26 08:29:26 RE: GROUPING SETS and SQL standard
Previous Message Yugo Nagata 2019-11-26 07:02:25 Re: Implementing Incremental View Maintenance