transactions - Does MySQL/InnoDB implement true serializable isolation?

Question

It is not entirely clear from MySQL documentation whether the InnoDB engine implements true serializable isolation¹ or snapshot isolation, which is often confusingly called "serializable" too. Which one is it?

If MySQL InnoDB doesn't, are there any completely free, production-quality RDBMS which do?

¹ where "true serializable isolation" means the absence of not only read anomalies as per the SQL standard, but also the write skew anomaly, explained in further detail here.

Answer 1

UPDATE:

See comments, this seems to be fixed in MySQL 5.5, with these examples we still have a table lock and the index next-key lock cannot be fooled, AFAIK.

Original:

Found your question yesterday and I was wondering about the MVCC seriability model of InnoDb as well.

So I made some tests. MySQL 5.1.37. A good test for the serializability problem is the one provided in postgrESQL 9.0 MVCC documentation, on this chapter Serializable Isolation versus True Serializability we can see the limit of the MVCC model on serializability if no predicate locking is performed.

So let's test it on MySQL:

CREATE TABLE t1 (
 class integer,
 value integer
) ENGINE=InnoDB;

INSERT INTO t1 (`class`,`value`) VALUES
  (1,10),
  (1,20),
  (2,100),
  (2,200);

Now we will open two different connections to have two parallel transactions (T1 and T2):

T1:

SET TRANSACTIOn ISOLATION LEVEL SERIALIZABLE;
BEGIN;
SELECT SUM(value) FROM t1 WHERE class = 1;

Result is 30.

T2:

 SET TRANSACTIOn ISOLATION LEVEL SERIALIZABLE;
 BEGIN;
 SELECT SUM(value) FROM t1 WHERE class = 2;

Result is 300.

Now comes the serializability problem. If T1 inserts a row rendering the select from T2 invalid (here T2 does the same).

T1:

INSERT INTO t1 (`class`,`value`) VALUES (2,30);

==> waiting (a lock is in place)

T2:

INSERT INTO t1 (`class`,`value`) VALUES (1,300);

==> ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction

T1 now succeeds in his insert, t2 had a ROLLBACK, good serializability.

This would fail on PostgreSQL 9.0 (things are changing on 9.1, but it's another problem). In fact only one of the transactions can perform an insert on the table. Even if we try to insert on class=3 with.

INSERT INTO t1 (`class`,`value`) VALUES (3,30);

We would see a waiting lock, and deadlocks in case of problems. Looks like we have a predicate locking in MySQL... But in fact it's a next-key locking implementation in InnoDB.

Innodb performs row locks with some gaps locked as well on indexes. Here we have no indexes on the table, looks like MySQL decided to lock the table.

So let's try to test the next-key locking to see if this enforce serializability. First Rollback the running transaction (T1). Then create an index.

CREATE index t1class ON t1 (class);

Now redo the test. Success, serializability is still enforced. Good news.

But with the index in place I think the next-key locking and the row locks are made on the index. This mean we should be able to perform insert if it does not impact a parallel transaction... and here comes the big problem.

T1:

SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;
BEGIN;
SELECT SUM(value) FROM t1 WHERE class = 1;

Result is 30.

T2:

 SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;
 BEGIN;
 SELECT SUM(value) FROM t1 WHERE class = 2;

Result is 300.

Here we gonna make an unrelated insert on T1, now that we have an index this will succeed:

T1:

INSERT INTO t1 (`class`,`value`) VALUES (3,30);

Both can perform the insert (here I made only one), that's normal. The predictive locking isn't applied, no SELECT queries has been made on class=3. Looks like the next-key locking performs better if we give it good indexes (no Table lock on inserts).

Now we try to insert on the next-key lock, On a row matching selection of T2 (class=2):

T1:

INSERT INTO t1 (`class`,`value`) VALUES (2,30);

Ouch. It succeeds!

T2:

INSERT INTO t1 (`class`,`value`) VALUES (1,300);

==> waiting. There is still a lock there. Hopefully.

T1:

COMMIT;

T2: (where the lock has gone, the insert is made)

SELECT SUM(value) FROM t1 WHERE class = 2;
COMMIT;

Still having 300 here. Seems the serializability has gone.

select * from t1;
+-------+-------+
| class | value |
+-------+-------+
|     1 |    10 | 
|     1 |    20 | 
|     2 |   100 | 
|     2 |   200 | 
|     3 |    30 | <-- test
|     2 |    30 | <-- from trans1
|     1 |   300 | <-- from trans2 ERROR!
+-------+-------+

Result: By inserting a new unrelated row before inserting a row impacting a parallel transaction query we have spoofed the next-key locking mechanism. Or at least this is what I understand from my tests. So I would say, do not trust the engine for true serializability. When you have aggregates functions in a transaction the best thing is to manually lock the table, transform your serializability problem in a real only-one-guy situation, no surprises! Other serializability problems in examples are constraint verifications (check that the amount is still positive after your operation), do you own locks on these cases as well.