Re: PostgreSQL not ACID compliant? - Mailing list pgsql-hackers

Tom,

----- Original Message ----- 
From: "Tom Lane" <tgl@sss.pgh.pa.us>
To: "Heikki Tuuri" <Heikki.Tuuri@innodb.com>
Cc: <pgsql-hackers@postgresql.org>
Sent: Sunday, September 21, 2003 10:32 AM
Subject: Re: [HACKERS] PostgreSQL not ACID compliant?


> "Heikki Tuuri" <Heikki.Tuuri@innodb.com> writes:
> > 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.
>
> My understanding is that next-key locking only helps when all your
> predicates are point or range searches against an available b-tree
> index.

all SQL queries are performed through index searches. That is why next-key
locking enforces serializability. IBM researcher C. Mohan has written papers
about next-key locking. Next-key locking is an approximation of predicate
locking. We simply lock more to make sure the 'predicates' themselves are
locked.

> While that might cover many practical cases, it can hardly
> be called a complete solution to the problem of serializability.

It is a complete solution. Another approximation of predicate locking is
table level locking, a solution which Oracle used some 15 years ago, if you
switched it on the SERIALIZABLE isolation level.

> Another serious problem with predicate locking in general is that it's
> prone to creating deadlocks.  I gave an example here:
> http://archives.postgresql.org/pgsql-general/2003-01/msg01581.php
> Since next-key locking is just an approximate form of predicate locking
> (approximate in the sense that it may map many different predicates into
> the same lock), I'd expect it to generate even more deadlocks than true
> predicate locking would.
>
> In short, next-key is not a perfect solution either.

Of course, on the SERIALIZABLE isolation level we must lock more. Then
deadlocks happen more often.

...
> > 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.
>
> Should I read that as saying that you fail to take out the required
> next-key lock when inserting an autoincremented value?  Tsk tsk.
> The inserts may not conflict with each other, but I think you'll find
> that serializability is violated for concurrent selects looking at
> the table.

No, because if you set the transaction isolation level SERIALIZABLE, and use
a SELECT to read the MAX() of the auto-inc column, and try a concurrent
insert from another connection, that insert will block. In the counter
method, the auto-inc values assigned to newly inserted rows within the same
transaction are not guaranteed to be sequential. That is why we can avoid
the locking if we use the counter method.

> regards, tom lane

Best regards,

Heikki