Re: Serializable Isolation without blocking

[ Reviving this old thread because a recent one referred to it. ]

2009/5/7 Albe Laurenz <laurenz(dot)albe(at)wien(dot)gv(dot)at>:

> Kevin Grittner wrote:
>
>> > maybe I misunderstood something.
>> >
>> > Consider a function
>> > "makehighlander(personid integer) RETURNS void"
>> > defined like this:
>> >
>> >    SELECT ishighlander INTO b FROM scots WHERE id=personid;
>> >    IF b THEN
>> >       RETURN; /* no need to do anything */
>> >    END IF;
>> >    UPDATE scots SET ishighlander=TRUE WHERE id=personid;
>> >    SELECT count(*) INTO n FROM scots WHERE ishighlander;
>> >    IF (n > 1) THEN
>> >       RAISE EXCEPTION 'There can be only one';
>> >    END IF;
>> >
>> > If we assume that "ishighlander" is false for all records in
>> > the beginning, and there are two calls to the function with
>> > two personid's of records *in different pages*, then there cannot be
>> > any conflicts since all (write and intention) locks taken by each of
>> > these calls should only affect the one page that contains the one
>> > record that is updated and then found in the subsequent SELECT.
>> >
>> > Yet if the two execute concurrently and the two first SELECTs are
>> > executed before the two UPDATEs, then both functions have a snapshot
>> > so that the final SELECT statements will return 1 and both functions
>> > will succeed, leaving the table with two highlanders.
>>
>> I do think you misunderstood.  If there are two concurrent executions
>> and each reads one row, there will be an SIREAD lock for each of those
>> rows.  As an example, let's say that one of them (T0) updates its row
>> and does its count, finds everything looks fine, and commits.  In
>> reading the row the other transaction (T1) modified it sets the
>> T0.outConflict flag to true and the T1.inConflict flag to true.
>
> Where does T0 read the row that T1 modified?

* Typically, concurrency theory doesn't care about the specifics of
relational databases: it works on a (possibly countably infinite)
number of data items (sometimes called "variables").
* If a certain concurrency control technique works for such data items
(i.e., can only result in serializable executions or whatever), then
it must necessarily also work for relational databases which map their
data in "pages", if those pages are treated the same way the data
items are. Indexes and any other structures that can be used to *find
out* which other pages to read/write must then also be treated this
way.
* To answer your specific question: T0 might not read that specific
row, but the COUNT(..) definitely must read *something* that must be
modified by T1 when it updates the ishighlander field: either the row
itself (which I would expect if no index on ishighlander exists), or
some page in an index that it used to find out that it didn't need to
inspect the row itself. Otherwise, the update wasn't effective because
re-executing the COUNT(..) later on would not result in any change in
the result (which leads to a contradiction: changing the ishighlander
field of one row must result in a change in the number of
highlanders).

Nicolas