Serializable isolation level

Continuing with the previous posts(1,2,3,4), Although repeatable read isolation
level can guarantee that dirty reads don't happen and that data read multiple
times in a transaction doesn't change within the transaction, repeatable read
isolation level still allows for a relation to change via something called as
"Phantom Tuples".

Phantom reads
A phantom read is said to have occurred when, during a transaction, two
identical queries are executed, and the number of rows returned by the second
query is different from the first. The phantom reads is a special case of
Non-repeatable reads when Transaction t1 repeats a range SELECT query and,
between both operations, Transaction t2 creates, by INSERT command, new rows
(in the table) which fulfill that SELECT clause.

Consider the items table again :

            items
    + -- + --------- + ----- +
    | id | item      | price |
    + -- + --------- + ----- +
    | 1  | Colgate   | 5.23  |
    + -- + --------- + ----- +
    | 2  | Pepsodent | 4.33  |
    + -- + --------- + ----- +
    | 3  | Sensodyne | 12.33 |
    + -- + --------- + ----- +

Consider the following transactions:

 ------------------------- + ------------------------- +
| transaction t1 statements | transaction t2 statements |
+ ------------------------- + ------------------------- +
| SELECT * FROM items       |                           |
| WHERE price < 12.33       |                           |
| //selects Colgate         |                           |
| //and pepsodent           |                           |
+ ------------------------- + ------------------------- +
|                           | INSERT INTO items VALUES  |
|                           | (4, Close-Up, 3.33        |
|                           |                           |
|                           | Commit;                   |
+ ------------------------- + ------------------------- +
| SELECT * FROM items       |                           |
| WHERE price < 12.33       |                           |
| //now 3 rows are found    |                           |
| Commit;                   |                           |
+ ------------------------- + ------------------------- +

Note that Transaction t1 executed the same query twice. But still number of rows
returned during the two select queries is different. This might seem wrong, but
it is justified as per the definition of repeatable read isolation level, as the
same values are read both the times, but only that extra rows are also read.
The records that originated in the second select query which were not present in
the result of first statement of transaction t1 are called phantom tuples. They
seem to have emerged from nowhere as far as transaction t1 is concerned(Hence
phantom).

Note however if we replace the statement in the transaction t2 with :

    DELETE FROM items WHERE price = 12.33;

The deletion will either happen before entire transaction t1 or after
transaction t1. This is because of how repeatable read is implemented using
locks. This means values read in first statement of t1 are locked. In this case
DELETE cannot go through in between the two statements of transaction t1.
However, in the case of INSERT, the new values being inserted are not locked. If
a range based lock is also held apart from read-write lock, then the situation
of inserting phantom tuples will not occur.


Locks vs isolation levels
In the case of a read uncommitted isolation level, no locks are held. In the
case of read committed, a write lock is held until the end of transaction, so
that no other transaction can write concurrently. In repeatable read, both read
and write locks are held till the end of transaction, so already read rows
cannot be changed. However, change in the range of rows is possible.

If both read and write locks are held and range change is also not allowed by
holding range locks, then the isolation level is called "Serializable".


Isolation Levels vs Read Phenomena
+ ------------ + ----------- + -------------- + --------- +
| Isolation    | Dirty reads | Non-repeatable | Phantoms  |
| level        |             | reads          |           |
+ ------------ + ----------- + -------------- + --------- +
| Read         | may occur   | may occur      | may occur |
| Uncommitted  |             |                |           |
+ ------------ + ----------- + -------------- + --------- +
| Read         | -           | may occur      | may occur |
| Committed    |             |                |           |
+ ------------ + ----------- + -------------- + --------- +
| Repeatable   | -           | -              | may occur |
| Read         |             |                |           |
+ ------------ + ----------- + -------------- + --------- +
| Serializable |             |                | -         |
+ ------------ + ----------- + -------------- + --------- +