Re: counting algorithm for incremental matview maintenance

Nicolas Barbier <nicolas(dot)barbier(at)gmail(dot)com> wrote:
> 2013/5/17 Kevin Grittner <kgrittn(at)ymail(dot)com>:
>
>> During calculation of the deltas to apply to the matviews, it must
>> be possible to query the referenced tables from the perspective of
>> both the "before" and "after" versions of the data.
>
> [..]
>
>> I don't think the process applying the deltas needs to do
>> anything unusual or special about acquiring snapshots as it
>> processes the delta from each transaction, unless we see some way
>> to optimize things once we're hip-deep in the details.
>
> Note that the basic count algorithm assumes real-serializable
> transactions for correctness. Example:
>
> * The example matview’s defining query is a simple join: SELECT * FROM
> A JOIN B ON A.a = B.b.
> * For simplicity, assume that the matview is initially empty.
> * Assume a non real-serializable isolation mode, e.g., REPEATABLE READ.
> * Assume that there are two transactions T1 and T2 running in
> parallel, that don’t see each other’s changes.
> * Both T1 and T2 insert a row in A and B, respectively, in such a way
> that the combination of the rows is matched by the join condition
> (i.e., the row inserted by T1 has A.a equal to the B.b of the row
> inserted by T2).
> * The count algorithm will not add anything to the matview as part of
> the execution of T1 (because the new row in A doesn’t join with any
> rows in B that T1 observes).
> * Idem for T2 (nothing will be added).
> * After T1 and T2 completed, a new transaction will see an
> inconsistency: A and B contain rows that are supposed to result in a
> row in the matview, but it doesn’t contain any.

Good point.

It might be hard to detect when this type of race condition exists,
since it could be hidden inside a function.  Any thoughts on that?

> Each of the following would fix this problem:
>
> (1) Real-serializability must be required for all transactions that
> update any base table of a matview’s that is maintained using the
> count algorithm.

Agreed.  I wonder whether we should have an option to constraint
DML on a table to serializable transactions, and an option for a
matview to flag that its incremental update depends on that.  This
strategy would automatically detect problems hidden in functions,
whether or not they were explicitly recognized issues with the
matview definition.

It is clear, however, that this cannot be the only supported
approach.

> (2) The matview’s defining query and the corresponding base tables
> must adhere to certain (very commonly satisfied) conditions (for
> example, if there is an FK between A.a and B.b, the example cannot be
> made to fail; The FK must not be deferred in the case of
> right-after-each-statement matview maintenance).

Agreed.  That would cover a high percentage of cases regardless of
transaction isolation level.  Knowing when you needed such a
constraint to make incremental maintenance safe would be hard,
though.

> (3) The count algorithm must be implemented in a way that understands
> MVCC internals: Reading the base tables must be done using a technique
> that reads all rows (i.e., also the ones not visible to the current
> transaction), and the xmin/xmax/etc of the updated rows in the matview
> must be set in a smart way, so as to yield visibility results that
> correspond to the visibility of the “originating” rows in the base
> tables. Calculation of the matview deltas (especially the part where
> the base tables are inspected for joining rows) must in this case
> probably be done in a serialized manner.

I will look at this option some more, but on the face of it, I'm
not quite following how it would work; and it sounds invasive and
fragile. If you know of any paper on this approach you could point
me to, or if you could sketch it out in a little more detail, I
would appreciate that.  While (1) and (2) are straightforward
approaches, either of which would clearly address the race
conditions, I fear that there are those who would not be happy with
a requirement that one or the other of those are required in order
to use incremental maintenance -- so it would be nice to have a
fall-back strategy.

There will, at least for the next several releases, be matviews
defined with queries for which we cannot support incremental
maintenance -- REFRESH will continue to be the only way to deal
with these until we enhance incremental maintenance to support them.
For example, in 9.4 I don't intend to support incremental
maintenance of matviews defined with recursive queries.  To me it
makes sense to prohibit incremental maintenance of a matview for
which there is no strategy to deal with concurrency problems.

Thoughts?

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