-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I apologize if this post is inappropriate.

Doing some development work, me and my co-worker discussed some 
optimizations strategies. One of the ideas that came up was materialized 
views. Trading disk space to summarize queries, and paying for a trigger 
waterfall on certain kinds of updates seems like a small price to pay right 
now in our situation.

I searched through the archives and I couldn't seem to find anything 
relevant.

As I've no familiarity with the internals, but I do know the front-end 
pretty well, what can I do to help implement materialized views? Is such an 
idea feasible? Is there some reason why it just isn't a good idea? (And if 
not, what is a better idea?)

If someone is willing to guide me, I can probably contribute a fair amount 
of C code. I do have experience with C.

The bird's eye view of the project would probably be turning a statement (is 
there such a statement in SQL92?) in the creation of a table, the initial 
population of the table, and the creation of several triggers strategically 
placed so that the data in the materialized view table is always in sync. 
Direct inserts or updates on the materialized view should be illegal, 
except by the triggers. However, perhaps like views work today, we can 
allow rules to be added to the table.

Certain restrictions on the materialized views should be enforced: No 
mutables, in particular.

- -- 
Jonathan Gardner
jgardner@jonathangardner.net
Live Free, Use Linux!
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)

iD8DBQE/xNzcWgwF3QvpWNwRAkbiAJ4m1zRPe+y3Tha0649QXH30y9eITwCfTjsv
ow9Nwnnwrc6x9QaAB1AfHWQ=
=Ofb5
-----END PGP SIGNATURE-----


Wed, 26 Nov 2003 09:03:24 -0800
Jonathan Gardner <jgardner@jonathangardner.net>
Materialized views proposal
Jonathan Gardner kirjutas K, 26.11.2003 kell 19:03:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> I apologize if this post is inappropriate.
> 
> Doing some development work, me and my co-worker discussed some 
> optimizations strategies. One of the ideas that came up was materialized 
> views. Trading disk space to summarize queries, and paying for a trigger 
> waterfall on certain kinds of updates seems like a small price to pay right 
> now in our situation.
> 
> I searched through the archives and I couldn't seem to find anything 
> relevant.
> 
> As I've no familiarity with the internals, but I do know the front-end 
> pretty well, what can I do to help implement materialized views? 

First, You could start by implementing materialized views manually,
using tables and triggers, to get the feel of what should be generated.

Next, still working from frontend, try to make some code (probably in
some RAD/scripring language) which does the transform from CREATE VIEW
(or whatever) syntax (or manually constructed syntax tree) into create
table + create trigger statements.

If you have the above working well, talk about moving this to backend.

> Is such an 
> idea feasible? Is there some reason why it just isn't a good idea? (And if 
> not, what is a better idea?)
> 
> If someone is willing to guide me, I can probably contribute a fair amount 
> of C code. I do have experience with C.

What is needed is good algorithms. Writing C code is secondary to that.

Similar problem has kept us from implementing updatable views for quite
some time.

--------------------
Hannu


Wed, 26 Nov 2003 19:19:34 +0200
Hannu Krosing <hannu@tm.ee>
Re: Materialized views proposal
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Wednesday 26 November 2003 09:19, Hannu Krosing wrote:
>
> First, You could start by implementing materialized views manually,
> using tables and triggers, to get the feel of what should be generated.
>
> Next, still working from frontend, try to make some code (probably in
> some RAD/scripring language) which does the transform from CREATE VIEW
> (or whatever) syntax (or manually constructed syntax tree) into create
> table + create trigger statements.
>
> If you have the above working well, talk about moving this to backend.
>

Thanks for the suggestion. I will definitely do that.


> What is needed is good algorithms. Writing C code is secondary to that.
>
> Similar problem has kept us from implementing updatable views for quite
> some time.
>

You are definitely correct.

- -- 
Jonathan M. Gardner
Web Developer, Amazon.com
jonagard@amazon.com - (206) 266-2906
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)

iD8DBQE/xPfOBFeYcclU5Q0RAhgfAKDAYmm67Jc5n7WwyUDtn5IJOhhrXwCfcRud
EAR9U63FEqlHbGrdzKxGmdw=
=a6RK
-----END PGP SIGNATURE-----


Wed, 26 Nov 2003 10:58:22 -0800
Jonathan Gardner <jonagard@amazon.com>
Re: Materialized views proposal
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Wednesday 26 November 2003 10:58 am, Jonathan Gardner wrote:
> On Wednesday 26 November 2003 09:19, Hannu Krosing wrote:
> > What is needed is good algorithms. Writing C code is secondary to that.
> >
> > Similar problem has kept us from implementing updatable views for quite
> > some time.
>
> You are definitely correct.

Preliminary research has shown that:
1) We would put triggers on each table that contributes to a view.

2) We would only be interested in those inserts and deletes (counting an 
update as a delete and then an insert) that satisfy the "WHERE" clause of 
the view.

3) We would implement some sort of differential view update scheme based on 
the paper "Efficiently Updating Materialized Views"[1]. They classify all 
select queries into one of four categories and describe how to go about 
producing a differential update. I couldn't understand this part at all.

- ---

I am already too deep in database theory. While I enjoy reading a good 
paper, I just don't have the background in DB science like I do in Physics. 
For instance, my set theory is very weak (I can't tell if U is a union or 
an intersection, for instanct).

At this point, I have a choice. Drop a couple hundred dollars on database 
theory textbooks and spend the next three months learning it, or hoping one 
of you database theorists out there take pity on me and pick this up or 
coach me through it. Any takers on the second one?

- ---

I have a proposal. Let me hear what you think. There will be two kinds of 
materialized view in PostgreSQL:

The first is the "snapshot" approach. Provide a materialized view, but don't 
provide automatic updating. The user can call a refresh statement to 
repopulate the entire view from time to time as appropriate. The benefit of 
this is that you can use queries that have functions that are immutable or 
stable. (You could probably use volatile as well but I wouldn't recommend 
it). This is so easy to implement, it isn't even funny.

Optimizing this would involve collecting all the inserted / updated /deleted 
rows since the last snapshot. We can have a logging table that accumulates 
all the changes since the last refresh for this purpose. (This kind of 
table may exist anyway for replication or other purposes.)

Finally, we could examine the changed rows, ignore the irrelevant ones, 
ignore the redundant ones (IE, rows that have been inserted and then 
deleted during that time), and decide whether doing a complete refresh 
would be quicker than doing several differential updates to the 
materialized view.


The second is the automatically updated materialized view. Each insert, 
update, or delete executed against the table that are queried for the view 
will trigger a function call using the algorithms proposed in [1]. Every 
function in the query must be stable.


We could provide a mechanism to alter the materialized view between snapshot 
to auto-updated. It would be as simple as refreshing the snapshot and then 
enabling the triggers, or as simple as disabling the triggers.


I already have written a set of scripts in perl that provides the first 
proposal without the optimization idea. I will put them up at GBorg.


Footnotes:
[1] ftp://ftp.research.microsoft.com/users/palarson/sigmod86.ps

- -- 
Jonathan Gardner
jgardner@jonathangardner.net
Live Free, Use Linux!
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)

iD8DBQE/yQjZWgwF3QvpWNwRAnqkAKCasoODeV2+KcP52DMXiEyq7pfhmACcCFBV
X28Nd5PvlhR8Xta/G4w2qBQ=
=OLa8
-----END PGP SIGNATURE-----


Sat, 29 Nov 2003 13:00:06 -0800
Jonathan Gardner <jgardner@jonathangardner.net>
Re: Materialized views proposal
Jonathan Gardner <jgardner@jonathangardner.net> writes:
> 3) We would implement some sort of differential view update scheme
>    based on the paper "Efficiently Updating Materialized Views"[1].

One resource on this topic that appears to be quite authoritative is
"Materialized Views: Techniques, Implementations, and Applications" by
A. Gupta and I. Mumick (MIT Press, 1999). That might present the
material in a manner that is easier to grok than the original papers
themselves.

I didn't realize that it was possible to spend 600 pages only
discussing materialized views, but it apparently it is :-)

-Neil


Sat, 29 Nov 2003 19:18:10 -0500
Neil Conway <neilc@samurai.com>
Re: Materialized views proposal
Neil Conway kirjutas P, 30.11.2003 kell 02:18:
> Jonathan Gardner <jgardner@jonathangardner.net> writes:
> > 3) We would implement some sort of differential view update scheme
> >    based on the paper "Efficiently Updating Materialized Views"[1].

Maybe the TelegraphCQ engine can give some ideas

http://telegraph.cs.berkeley.edu/

from brief reading, it seems that all they do is kind of materialized
views ;) - they call it Continuous Dataflow Processing, i.e. queries
that run continuously over incoming data.

----------------
Hannu


Sun, 30 Nov 2003 14:57:44 +0200
Hannu Krosing <hannu@tm.ee>
Re: Materialized views proposal
>>>>> "Hannu" == Hannu Krosing <hannu@tm.ee> writes:

    Hannu> Neil Conway kirjutas P, 30.11.2003 kell 02:18:
    >> Jonathan Gardner <jgardner@jonathangardner.net> writes: > 3) We
    >> would implement some sort of differential view update scheme >
    >> based on the paper "Efficiently Updating Materialized
    >> Views"[1].

    Hannu> Maybe the TelegraphCQ engine can give some ideas

    Hannu> http://telegraph.cs.berkeley.edu/

    Hannu> from brief reading, it seems that all they do is kind of
    Hannu> materialized views ;) - they call it Continuous Dataflow
    Hannu> Processing, i.e. queries that run continuously over
    Hannu> incoming data.


A fair portion of the community argues that everything that we do is
merely materialized views :-)

While materialized views are certainly related, there are however,
things that are quite different in processing continuous queries over
data streams. The first ideas on stream processing did come from work
on scalable triggers which is intimately related to materialized
views. Work on mviews isn't really concerned with things like windowed
joins and aggregate processing.

My advice is to take a very incremental approach to materialized view
implementation. There are essentially 2 pieces - one the maintenance
of the views and second the routing of queries to automagically use
the materialized views. The former is done by something like triggers
and the latter is through either a query-rewrite mechanism or
something like an optimizer choosing a different access method. 

As for the former, there are again two subdivisions - what changes you
propagate and when you apply 'em. What you propagate are the
deltas. So you have the following choices:

IPIA - Immediate Propagate, Immediate Apply 
IPDA - Immediate Propagate, Deferred Apply
DPDA - Deferred Propagate, Deferred Apply

DPIA - makes no sense ..

The easiest is DPDA .. in this model you essentially recompute the
view on demand. The next is IPIA.. with IPIA, you can choose to either
recompute the entire view or only figure out how to translate a delta
into appropriate changes in the mview. After that there is IPDA
.. this involves creating a delta table that is populated based on the
triggers. Every so often you process a set of deltas and recompute the
view (either in its entirety or in parts>

Another way to slice the problem is to limit the scope of queries that
can be used to define views. 

I suggest that first we don't consider joins .. and only consider
grouped aggregates over a single table. Joins are more hairy with
changes in one table potentially requiring a wholesale recomputation
of the join. 

Note that all this discussion is only about the first part of the
problem .. maintenance of the views. The other part, routing is almost
equally complicated .. there you have to solve the query subsumption
problem without also eliminating choices in your access plan. 

As people have said there are plenty of papers on this in the
literature. While I am no theorist I can certainly help with reading
the papers .. not every bit of a paper is very useful. 

-- 
Pip-pip
Sailesh
http://www.cs.berkeley.edu/~sailesh



Sun, 30 Nov 2003 14:46:46 -0800
Sailesh Krishnamurthy <sailesh@cs.berkeley.edu>
Re: Materialized views proposal