Re: Update on true serializable techniques in MVCC

2009/12/16 Albe Laurenz <laurenz(dot)albe(at)wien(dot)gv(dot)at>:

> Quote:
>   The problem [of phantom reads] was identified in (Eswaran et al., 1976),
>   but the general purpose "predicate locking" solution suggested there
>   has not been widely adopted because of the difficulty in testing mutual
>   satisfiability of predicates.
>
>   Instead, locking DBMS implementations commonly use algorithms based on
>   "next-key locking". In these, a range of key space is protected against
>   concurrent insertion or deletion by acquiring a shared lock on the next
>   row in order, as a scan is made to check whether rows match a predicate.
>   The scan might be through the data records or through an index.
>
>   Inserts and deletes follow the same protocol, obtaining an exclusive
>   lock on the row after the one being inserted or deleted. The result
>   of this locking protocol is that a range scan prevents concurrent
>   inserts or delete within the range of the scan, and vice versa.
>
> That sounds like it should actually work.

That boils down to 2PL, using a granularity that is somewhere between
table locks and single-row locks (note that the latter doesn't
correctly enforce serializability, hence something more coarse which
also locks not-yet-existing rows is needed).

Disadvantages:

1. Unstable latency: Depending on whether indexes or table scans are
used (i.e., the plan), other transactions may be blocked for long
durations or not.
2. Unstable susceptibility to deadlocks: Idem; it is possible that
once the planner starts to use another kind of scans, that your
transactions start to deadlock.

It seems that the proposed SIREAD method fixes at least (1), because
there is no additional blocking involved. I am not sure whether the
serialization failures that it may cause are dependent on the plan
used. If so, that would be very similar to (2).

Nicolas