Florian,

if you set the transaction isolation level SERIALIZABLE in MySQL/InnoDB,
then InnoDB uses next-key locking in every SELECT, and transactions really
are serializable in the mathematical sense. I think the same holds for DB2
and MS SQL Server.

PostgreSQL and Oracle use a loophole of SQL-1992 in defining
serializability. In SQL-1992 serializability is defined as 'no phantom rows
can appear if a read is repeated'. Oracle and PostgreSQL conform to this
SQL-1992 definition, but their execution is really not serializable in the
mathematical sense, like your example with COUNT(*) shows. Peter Gulutzan
notes this in his paper: http://www.dbazine.com/gulutzan6.html. Another
example of the flaw in the Oracle and PostgreSQL model is shown if you try
to code a UNIQUE check manually. If your SELECT returns no conflicting rows,
that does not guarantee there are none at the serialization point of the
INSERT.

...

Another note: Joshua Drake claimed that InnoDB deadlocks if you try to do
inserts concurrently to a table with a primary key. I guess he refers to
some old version, where InnoDB still used

SELECT MAX(auto_inc_column) FROM table FOR UPDATE;

to determine the next auto-inc key value. Because the execution has to be
serializable :), it is not that easy to make this algorithm to avoid
deadlocks if inserts are made to the end of the index.

But the InnoDB algorithm was changed a long time ago. Nowadays innoDB uses
an internal counter. I ran Joshua's test with MySQL-4.0.15 with the default
my.cnf settings, and no deadlocks were generated.

Best regards,

Heikki

..................
List:     postgresql-general
Subject:  Re: [HACKERS] PostgreSQL not ACID compliant?
From:     Florian Weimer <fw () deneb ! enyo ! de>
Date:     2003-09-20 20:33:11
[Download message RAW]

"scott.marlowe" <scott.marlowe@ihs.com> writes:

> Postgresql supports Serializable transactions, which are 100% ACID
> compliant.

How can I activate it? 8-)

Yes, I know about SET TRANSACTION ISOLATION LEVEL SERIALIZABLE, please
read on.

Given the two tables:

CREATE TABLE items (item INTEGER);
CREATE TABLE counts (count INTEGER);

And transactions following this pattern:

  number := <some number>;
  INSERT INTO items VALUES (number);
  nr := SELECT COUNT(*) FROM items;
  INSERT INTO counts VALUES (nr);
  COMMIT;

If these transactions are executed serially, the following condition
always holds once the tables are non-empty:

(*)  (SELECT COUNT(*) FROM items) = (SELECT MAX(count) FROM counts)

Now look at the following history:

Session 1                           Session 2

number := <some number>;
                                    number := <some number>;
INSERT INTO items VALUES (number);
                                    INSERT INTO items VALUES (number);
nr := SELECT COUNT(*) FROM items;
                                    nr := SELECT COUNT(*) FROM items;
INSERT INTO counts VALUES (nr);
                                    INSERT INTO counts VALUES (nr);
COMMIT;
                                    COMMIT;

If you enter these commands in two parallel psql sessions, in the
order indicated, condition (*) no longer holds once both transactions
are completed.  Therefore, PostgreSQL must have generated a
non-serializable history.

Is this a bug, or is SQLxx serializability defined in different terms?



Sun, 21 Sep 2003 09:33:01 +0300
"Heikki Tuuri" <Heikki.Tuuri@innodb.com>
Re: PostgreSQL not ACID compliant?