Thread: Incrementally refreshed materialized view

Does PG support INCREMENTAL MV ? Looks like not (until 9.5)

On Mon, Sep 26, 2016 at 1:22 PM, Melvin Davidson <melvin6925@gmail.com> wrote:
> On Mon, Sep 26, 2016 at 1:56 PM, Adam Brusselback <adambrusselback@gmail.com> wrote:
>>
>> I am working on a plan to implement incrementally refreshed
>> materialized "views" with the existing functionality in
>> Postgres.
>>
>> Below is the plan for doing that:

>> [design from scratch, incomplete]

>> I am however stuck on: How do we know what to refresh?

>> Pretty much, I need to figure out how to follow the joins in the
>> view back to whatever key was defined as the "refresh key" for
>> each dependent table.  I know about the
>> information_schema.view_column_usage, but I don't think that'll
>> get me everything I need.
>>
>> I'd really appreciate any help with this, as i'd love a better
>> way to get eagerly refreshed materialized views in Postgres
>> rather than doing everything manually as I have to now.
>>
>> If I can provide any more info please let me know.

> I am a bit curious. Why are you reinventing the wheel?
> What is wrong with:
>
> REFRESH MATERIALIZED VIEW [ CONCURRENTLY ] name
>     [ WITH [ NO ] DATA ]
>
> https://www.postgresql.org/docs/9.4/static/sql-refreshmaterializedview.html
>
> Can't you do that in a cron job?

Well, that is not *incremental* maintenance -- the entire query is
executed, with the resulting relation either replacing the previous
contents of the matview or "diffed" against the previous contents
(so that the difference can be applied with transactional
semantics), depending on whether CONCURRENTLY was specified.

The OP is still reinventing the wheel though.  A summary of
available techniques as of the mid-90s can be found here:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.40.2254&rep=rep1&type=pdf

With some detail for what to me look like the two most promising
techniques here:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31.3208&rep=rep1&type=pdf

The first step in using either of those techniques (counting or
DRed) is to capture a delta relation to feed into the relational
algebra used by these techniques.  As a first step in that
direction I have been floating a patch to implement the
SQL-standard "transition tables" feature for AFTER triggers.

https://commitfest.postgresql.org/10/778/

If you want to help that effort, reading the thread and reviewing
the patch would be good.

--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Mon, Sep 26, 2016 at 2:04 PM, Rakesh Kumar
<rakeshkumar464@outlook.com> wrote:

> Does PG have a concept of MV log, from where it can detect the
> delta changes and apply  incremental changes quickly.

That is what I am trying to work toward with the patch I cited in
an earlier post.  Once some variation of that is in, the actual
incremental maintenance can be build on top of it.  To see an
example of what would be done with such a delta relation for a
simple MV, using the count algorithm, see below:


--------------------------------------------------------------------------
--
-- This file demonstrates how incremental maintenance of materialized views
-- is intended to work using the counting algorithm.  TEMP tables are used
-- to mock up both snapshots of relations and delta relations which will
-- be created automatically "behind the scenes" as part of the algorithm.
--
-- Delta relations for both base tables and materialized views will need a
-- "count(t)" column to track the number of alternative derivations of the
-- tuple.  The column is actually named that in this example.  Where the
-- count is needed by the algorithm and a relation doesn't have it
-- (because, for example, it is a base table), 1 is used.  This is kept in
-- the example for purposes of illustration.  While it is explicitly added
-- to the materialized views for this example, the idea would be that
-- specifying these materialized views using DISTINCT would implicitly add
-- the "count(t)" column when incremental maintenance was specified.
--
-- The logic for a JOIN is that the resulting row should have the product
-- of multiplying the two input row counts.  Calculating a delta for that
-- requires two such joins which are then processed by a UNION with special
-- semantics.  Those semantics are achieved in this example by feeding
-- UNION ALL results to an outer SELECT which uses GROUP BY and HAVING
-- clauses.
--
-- This example dodges some complex and performance-sapping problems that
-- occur when duplicate rows may be present.  It does so with a combination
-- of a PRIMARY KEY declaration in the base table and GROUP BY clauses in
-- the materialized views.
--
-- The temporary relation names in the example are chosen for clarity of
-- the example.  If temporary relation names are actually needed in the
-- implementation, they would need to be different, probably based on the
-- related permanent relation OID, for length.
--
--------------------------------------------------------------------------

-- Set up the base table used for these materialized views.
CREATE TABLE link
(
  src  text not null,
  dst  text not null,
  primary key (src, dst)
);
INSERT INTO link
  VALUES ('a','b'),('b','c'),('b','e'),('a','d'),('d','c');

-- Display and capture "before" image.
SELECT * FROM link ORDER BY 1, 2;
CREATE TEMP TABLE link1 AS SELECT * FROM link;

-- Create and display the initial state of the "hop" MV.
CREATE MATERIALIZED VIEW hop AS
  SELECT t1.src, t2.dst, count(*) AS "count(t)"
    FROM link t1
    JOIN link t2 ON (t2.src = t1.dst)
    GROUP BY t1.src, t2.dst;
SELECT * FROM hop;

-- Execute a transaction that modifies the base table.
-- The assumption is that the changes will be applied shortly after commit.
BEGIN;
DELETE FROM link WHERE src = 'b' AND dst = 'e';
INSERT INTO link VALUES ('c','h'),('f','g');
COMMIT;

-- Display and capture "after" image.
SELECT * FROM link ORDER BY 1, 2;
CREATE TEMP TABLE link2 AS SELECT * FROM link;

-- Mock up the delta(link) table which will get created "behind the scenes".
CREATE TEMP TABLE "Δ(link)" (src text NOT NULL, dst text NOT NULL,
"count(t)" int NOT NULL);
INSERT INTO "Δ(link)" VALUES ('b','e',-1),('c','h',1),('f','g',1);
SELECT * FROM "Δ(link)" ORDER BY 1, 2;

-- Given link before and after images, and delta(link), calculate delta(hop).
-- This must happen while the "before" and "after" snapshots are still
registered,
-- but not necessarily in the same transaction as the modifications to
the base table.
CREATE TEMP TABLE "Δ(hop)"
  (src text NOT NULL, dst text NOT NULL, "count(t)" int NOT NULL);
INSERT INTO "Δ(hop)"
  SELECT src, dst, sum("count(t)") AS "count(t)"
    FROM (
           SELECT delta.src, before.dst, delta."count(t)" * 1
             FROM "Δ(link)" delta
             JOIN link1 before ON (before.src = delta.dst)
           UNION ALL
           SELECT after.src, delta.dst, 1 * delta."count(t)"
             FROM link2 after
             JOIN "Δ(link)" delta ON (delta.src = after.dst)
         ) x(src, dst, "count(t)")
    GROUP BY src, dst
    HAVING sum("count(t)") <> 0;
SELECT * FROM "Δ(hop)" ORDER BY 1, 2;

-- Once the MV delta has been generated, the snapshots can be released.
-- We're using temp tables for demonstration purposes, so drop those,
-- and the base table's delta.
DROP TABLE link1, link2, "Δ(link)";

-- At some later time the MV delta is processed "behind the scenes".
-- We can't do the demonstration maintenance against the MV, so copy it.
CREATE TEMP TABLE hop2 AS SELECT * FROM hop;
BEGIN;
DELETE FROM hop2 t1
  USING "Δ(hop)" t2
  WHERE t1.src = t2.src
    AND t1.dst = t2.dst
    AND t1."count(t)" + t2."count(t)" = 0;
UPDATE hop2 t1
  SET "count(t)" = t1."count(t)" + t2."count(t)"
  FROM "Δ(hop)" t2
  WHERE t1.src = t2.src
    AND t1.dst = t2.dst;
INSERT INTO hop2
  SELECT * FROM "Δ(hop)" t1
    WHERE "count(t)" > 0
      AND NOT EXISTS (SELECT * FROM hop2 t2 WHERE t2.src = t1.src AND
t2.dst = t1.dst);
COMMIT;

-- Show that we got to the same result with incremental maintenance as
with REFRESH.
REFRESH MATERIALIZED VIEW hop;
SELECT * FROM hop ORDER BY 1, 2;
SELECT * FROM hop2 ORDER BY 1, 2;

-- Now we're done with the MV delta.
DROP TABLE hop2, "Δ(hop)";

--------------------------------------------------------------------------

-- Let's show how it works when an MV uses another MV.
-- Create the 2nd-level MV.
CREATE MATERIALIZED VIEW tri_hop AS
  SELECT t1.src, t2.dst, sum(t1."count(t)" * 1) AS "count(t)"
    FROM hop t1
    JOIN link t2 ON (t2.src = t1.dst)
    GROUP BY t1.src, t2.dst;
SELECT * FROM tri_hop ORDER BY 1, 2;

-- Display and capture "before" image.
-- Include hop now, because it is referenced by tri_hop.
SELECT * FROM link ORDER BY 1, 2;
CREATE TEMP TABLE link1 AS SELECT * FROM link;
SELECT * FROM hop ORDER BY 1, 2;
CREATE TEMP TABLE hop1 AS SELECT * FROM hop;

-- Execute a transaction that modifies the base table.
-- The assumption is that the changes will be applied shortly after commit.
BEGIN;
DELETE FROM link WHERE src = 'a' AND dst = 'b';
INSERT INTO link VALUES ('d','f'),('b','h');
COMMIT;

-- Display and capture "after" image.
SELECT * FROM link ORDER BY 1, 2;
CREATE TEMP TABLE link2 AS SELECT * FROM link;

-- Mock up the delta(link) table which will get created "behind the scenes".
CREATE TEMP TABLE "Δ(link)" (src text NOT NULL, dst text NOT NULL,
"count(t)" int NOT NULL);
INSERT INTO "Δ(link)" VALUES ('a','b',-1),('d','f',1),('b','h',1);
SELECT * FROM "Δ(link)" ORDER BY 1, 2;

-- Given link before and after images, and delta(link), calculate delta(hop).
-- This must happen while the "before" and "after" snapshots are still
registered,
-- but not necessarily in the same transaction as the modifications to
the base table.
-- For a "first level" MV, this is calculated just the same as before,
but it will be used
-- to calculate the 2nd level MV before we discard the snapshots.
CREATE TEMP TABLE "Δ(hop)"
  (src text NOT NULL, dst text NOT NULL, "count(t)" int NOT NULL);
INSERT INTO "Δ(hop)"
  SELECT src, dst, sum("count(t)") AS "count(t)"
    FROM (
           SELECT delta.src, before.dst, delta."count(t)" * 1
             FROM "Δ(link)" delta
             JOIN link1 before ON (before.src = delta.dst)
           UNION ALL
           SELECT after.src, delta.dst, 1 * delta."count(t)"
             FROM link2 after
             JOIN "Δ(link)" delta ON (delta.src = after.dst)
         ) x(src, dst, "count(t)")
    GROUP BY src, dst
    HAVING sum("count(t)") <> 0;
SELECT * FROM "Δ(hop)" ORDER BY 1, 2;

-- Since the counting algorithm requires the link table "before"
image, as well as
-- the hop MV "after" image and delta(hop) to calculate delta(tri_hop), we must
-- maintain hop before releasing the snapshots used to update link.
CREATE TEMP TABLE hop2 AS SELECT * FROM hop;
BEGIN;
DELETE FROM hop2 t1
  USING "Δ(hop)" t2
  WHERE t1.src = t2.src
    AND t1.dst = t2.dst
    AND t1."count(t)" + t2."count(t)" = 0;
UPDATE hop2 t1
  SET "count(t)" = t1."count(t)" + t2."count(t)"
  FROM "Δ(hop)" t2
  WHERE t1.src = t2.src
    AND t1.dst = t2.dst;
INSERT INTO hop2
  SELECT * FROM "Δ(hop)" t1
    WHERE "count(t)" > 0
      AND NOT EXISTS (SELECT * FROM hop2 t2 WHERE t2.src = t1.src AND
t2.dst = t1.dst);
COMMIT;

-- Show that we got to the same result with incremental maintenance as
with REFRESH.
REFRESH MATERIALIZED VIEW hop;
SELECT * FROM hop ORDER BY 1, 2;
SELECT * FROM hop2 ORDER BY 1, 2;

-- After the 1st level MV is run, we can calculate the delta for the 2nd level.
CREATE TEMP TABLE "Δ(tri_hop)"
  (src text NOT NULL, dst text NOT NULL, "count(t)" int NOT NULL);
INSERT INTO "Δ(tri_hop)"
  SELECT src, dst, sum("count(t)") AS "count(t)"
    FROM (
           SELECT delta.src, before.dst, delta."count(t)" * 1
             FROM "Δ(hop)" delta
             JOIN link1 before ON (before.src = delta.dst)
           UNION ALL
           SELECT after.src, delta.dst, 1 * delta."count(t)"
             FROM hop2 after
             JOIN "Δ(link)" delta ON (delta.src = after.dst)
         ) x(src, dst, "count(t)")
    GROUP BY src, dst
    HAVING sum("count(t)") <> 0;
SELECT * FROM "Δ(tri_hop)" ORDER BY 1, 2;

-- Now we're done with snapshots and all but the highest-level delta.
DROP TABLE link1, link2, "Δ(link)";
DROP TABLE hop1, hop2, "Δ(hop)";

-- At some later time the MV delta is processed "behind the scenes".
-- We can't do the demonstration maintenance against the MV, so copy it.
CREATE TEMP TABLE tri_hop2 AS SELECT * FROM tri_hop;
BEGIN;
DELETE FROM tri_hop2 t1
  USING "Δ(tri_hop)" t2
  WHERE t1.src = t2.src
    AND t1.dst = t2.dst
    AND t1."count(t)" + t2."count(t)" = 0;
UPDATE tri_hop2 t1
  SET "count(t)" = t1."count(t)" + t2."count(t)"
  FROM "Δ(tri_hop)" t2
  WHERE t1.src = t2.src
    AND t1.dst = t2.dst;
INSERT INTO tri_hop2
  SELECT * FROM "Δ(tri_hop)" t1
    WHERE "count(t)" > 0
      AND NOT EXISTS (SELECT * FROM tri_hop2 t2 WHERE t2.src = t1.src
AND t2.dst = t1.dst);
COMMIT;

-- Show that we got to the same result with incremental maintenance as
with REFRESH.
REFRESH MATERIALIZED VIEW tri_hop;
SELECT * FROM tri_hop ORDER BY 1, 2;
SELECT * FROM tri_hop2 ORDER BY 1, 2;

-- Now we're done with the MV delta.
DROP TABLE tri_hop2, "Δ(tri_hop)";


--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Mon, Sep 26, 2016 at 3:16 PM, Adam Brusselback
<adambrusselback@gmail.com> wrote:

> Well I feel like I've learned a ton already reading through the links you
> provided earlier and that example above.

Yeah, I know that example can really help show what will happen
"under the covers", and make it more concrete.  The theory that
it's based on seems brilliant to me.  That fact that it's based on
relational algebra (RA) means that it is much more likely to be
implemented in a complete and correct manner than something ad hoc.
 I know I started at this with a try (similar to yours) at
analyzing from scratch, then went and searched the literature.
When I came back to my ad hoc notes, the RA pointed out some holes
in the logic where corner cases would have been wrong because of
missed details.  RA is well thought out and solid; it seems to me
to be the perfect thing to underlie a solution to this problem.

> I'm very interested in getting this into core. I'll look into what I need to
> do to review. Not crazy familiar with C, as I mainly do Java development.
> I'll see if I can help in any way though.

Just testing it and reviewing the documentation for errors,
omissions, or just plain hard-to-follow language would be a big
help.  Please post back about any problems getting things patched
and build.

> The main reason I was working on an alternative is because I need something
> now rather than in a couple years, but I've been dealing with manually
> creating the few I do need for my database. What I proposed above was just
> me thinking about what could be done with things as they are. Obviously it's
> junk compared to a real solution in-core.  Would you consider my approach
> even worth trying, or should I just suck it up and do things manually for
> now and put that effort into getting incremental refresh into core?

Oh, I've used plain tables and triggers many times myself.  If you
need something now, you kind of have to go that route.  The
algorithms I cited do provide an interesting potential alternative
for how to go about that, although operating a row at a time you
probably won't approach the speed of statement-level set logic for
statements that affect very many rows.  :-(

--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company