Re: Serializable Isolation without blocking

"Albe Laurenz" <laurenz.albe@wien.gv.at> wrote: 
> As far as I know, only the table rows that are found in the index
> scan are examined for visibility. Which would be only one in my
> example.
S2PL locking schemes routinely use index range locks.
> But in your attempt to sketch a way how true serializability could
> be implemented, you went beyond the scope of the original paper,
> which does not claim to tackle "phantoms".
It doesn't put forward techniques to tackle that, apparently
considering the issues to be so well-known and obvious as to not
require more than a brief mention.  They have a section titled
"Phantoms":
>> Throughout the discussion so far, we have followed typi-
>> cal concurrency control theory and assumed that a transac-
>> tion is a sequence of reads and writes on named data items.
>> In general, a relational database engine must also deal with
>> predicate operations (such as SQL *where* clauses). These
>> mean that a concurrency control algorithm must also con-
>> sider phantoms, where an item created or deleted in one
>> transaction would change the result of a predicate operation
>> in a concurrent transaction if the two transactions executed
>> serially. The solution used in traditional two-phase locking
>> is multigranularity locking, where a predicate operation
>> takes intention locks on larger units, such as pages or ta-
>> bles, to prevent insertion of records that might match the
>> predicate.
> As you mentioned in your first post, there will not be a free lunch.
> What hurts concurrency in an implementation with blocking read locks
> might also hurt concurrency in an implementation where transactions
> are frequently aborted and have to be retried.
Possibly; although the benchmarks published in the paper show much
better throughput than traditional blocking techniques with long and
high-conflict transactions.  Eyeballing the graph (based on 20
concurrent sessions), blocking techniques got a 2% deadlock rate in
this benchmark, snapshot isolation got a 2.6% update conflict rate,
and the technique published in the paper got a 0.1% update conflict
rate plus another 7.2% snapshot unsafe rate.  Oddly, in spite of a
serialization failure rate of 7.3% versus snapshot isolation's 2.6%,
the performance of the new technique edged out snapshot isolation when
the number of connections was 35 or higher.  I assume that is because
the rollbacks and restarts somehow reduced thrashing.  The traditional
serializable techniques started to drop below the non-blocking
techniques at about 10 concurrent sessions, and performance kept
dropping from that point while the non-blocking performance continued
to rise all the way to 50.
-Kevin