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:38:53 +0300
"Heikki Tuuri" <Heikki.Tuuri@innodb.com>
Re: 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.  While that might cover many practical cases, it can hardly
be called a complete solution to the problem of serializability.

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.

> 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.

Yup, pretty much the same point I made above.  Inserting at the end of
the index requires a next-key lock on a (notional) infinite key.
So all those inserts need the same exclusive lock.

> 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.

			regards, tom lane

Sun, 21 Sep 2003 03:32:10 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: PostgreSQL not ACID compliant? 
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



Sun, 21 Sep 2003 12:51:10 +0300
"Heikki Tuuri" <Heikki.Tuuri@innodb.com>
Re: PostgreSQL not ACID compliant? 
Heikki Tuuri kirjutas P, 21.09.2003 kell 12:51:
> 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.

Does that mean that an index is allways needed for predicate column, or
is this an abstract "index" in some realational algebra sense ?

>  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.

Is this solution complete only for MAX() case, or is this a general
solution woking for things line AVG or STDDEV and perhaps all
user-defined aggregates as well ?

> 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.

Table level locking seems to be a complete solution indeed, just not
concurrent at all. It may be that we have to forget concurrency to get
complete and general concurrency ;( 

Or is "next key locking" something more than a solution for getting
continuous nextval() 's ?

------------------
Hannu

Mon, 22 Sep 2003 22:00:43 +0300
Hannu Krosing <hannu@tm.ee>
Re: PostgreSQL not ACID compliant?
Hannu,

----- Original Message ----- 
From: "Hannu Krosing" <hannu@tm.ee>
To: "Heikki Tuuri" <Heikki.Tuuri@innodb.com>
Cc: <pgsql-hackers@postgresql.org>
Sent: Monday, September 22, 2003 10:00 PM
Subject: Re: [HACKERS] PostgreSQL not ACID compliant?


> Heikki Tuuri kirjutas P, 21.09.2003 kell 12:51:
> > 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.
>
> Does that mean that an index is allways needed for predicate column, or
> is this an abstract "index" in some realational algebra sense ?

in InnoDB, all tables have a clustered index, where rows are stored.
Normally, it is the primary key of the table. All searches to the table go
through indexes, even table scans.

> >  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.
>
> Is this solution complete only for MAX() case, or is this a general
> solution woking for things line AVG or STDDEV and perhaps all
> user-defined aggregates as well ?

It works for all queries. An AVG(), for example, does a table scan through
the clustered index, and consequently locks the whole table, if you use the
SERIALIZABLE isolation level.

> > 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.
>
> Table level locking seems to be a complete solution indeed, just not
> concurrent at all. It may be that we have to forget concurrency to get
> complete and general concurrency ;(

No, not at all. If you want SERIALIZABLE execution, you can do the
following:

1) Report transactions, like AVG(), are often read-only, and you can use the
default multiversioning concurrency control method of InnoDB to perform them
without setting any locks. The database simply reads a snapshot of the
database, and that snapshot is the serialization point of the read-only
transaction.

2) Update transactions are usually smaller, they will not scan whole tables.
For them you can use the SERIALIZABLE isolation level and next key locks.
The serialization point of the transaction is the COMMIT time of the
transaction.

> Or is "next key locking" something more than a solution for getting
> continuous nextval() 's ?

Yes.

> ------------------
> Hannu

Best regards,

Heikki



Thu, 25 Sep 2003 09:37:11 +0300
"Heikki Tuuri" <Heikki.Tuuri@innodb.com>
Re: PostgreSQL not ACID compliant?
I'm afraid I'm confused about something very simple... but anyway

I need to run a query on a varchar field containing a backslash.
My first attempt looked like this:
  SELECT smth. FROM  tbl WHERE situation LIKE '%\\%';
This did not returned any rows.

I looked up for a reference, confirmed that
"... double-backslash is required to represent a literal backslash."
http://www.postgresql.org/docs/aw_pgsql_book/node139.html#copy_backslash_han
dling

But when I doubled the number of backslashes:
  SELECT smth. FROM  tbl WHERE situation LIKE '%\\\\%';
- it actually worked fine.

Same thing happens with using regex: situation ~ '\\';

Could someone shed some light on this, please.

Mike.




Fri, 03 Oct 2003 09:40:50 -0400
Michael Brusser <michael@synchronicity.com>
Using backslash in query
Michael Brusser <michael@synchronicity.com> writes:
> But when I doubled the number of backslashes:
>   SELECT smth. FROM  tbl WHERE situation LIKE '%\\\\%';
> - it actually worked fine.

Backslash is special to both the string-literal parser and the LIKE code.
So when you write the above, the pattern value that arrives at the LIKE
processor has one less level of backslashing:
	%\\%
and the LIKE processor interprets this as percent, a literal backslash,
and another percent.

			regards, tom lane

Fri, 03 Oct 2003 11:34:04 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: Using backslash in query 
Tom Lane kirjutas R, 03.10.2003 kell 18:34:
> Michael Brusser <michael@synchronicity.com> writes:
> > But when I doubled the number of backslashes:
> >   SELECT smth. FROM  tbl WHERE situation LIKE '%\\\\%';
> > - it actually worked fine.
> 
> Backslash is special to both the string-literal parser and the LIKE code.
> So when you write the above, the pattern value that arrives at the LIKE
> processor has one less level of backslashing:
> 	%\\%
> and the LIKE processor interprets this as percent, a literal backslash,
> and another percent.

Regarding the dollar-quoting discussions -

Will we be able to write the above query as 

SELECT smth. FROM  tbl WHERE WHERE situation LIKE $$%\\%$$;

in 7.4 or is \ still special there ?

if it is then one \ in regex in plpython still needs to be entered as
\\\\\\\\ which has some geek coolness but would not be what I'd prefer
to do on a regular basis.

----------------
Hannu


Sat, 04 Oct 2003 11:20:09 +0300
Hannu Krosing <hannu@tm.ee>
Re: Using backslash in query

----- Original Message ----- 
From: "Hannu Krosing" <hannu@tm.ee>
>
> Regarding the dollar-quoting discussions -
>
> Will we be able to write the above query as
>
> SELECT smth. FROM  tbl WHERE WHERE situation LIKE $$%\\%$$;
>

Yes, as I understand it (as long as you remove the one of the WHEREs :-) ).
If not we need some rethinking.  Think of this as our equivalent of XML's
CDATA quoting - you don't need to escape & or < or > inside a CDATA node.


> in 7.4 or is \ still special there ?

I don't believe so.


cheers

andrew


Sat, 4 Oct 2003 07:31:21 -0400
"Andrew Dunstan" <andrew@dunslane.net>
Re: Using backslash in query

but this will be in 7.5, not 7.4, won't it?

Andrew Dunstan wrote:

>----- Original Message ----- 
>From: "Hannu Krosing" <hannu@tm.ee>
>  
>
>>Regarding the dollar-quoting discussions -
>>
>>Will we be able to write the above query as
>>
>>SELECT smth. FROM  tbl WHERE WHERE situation LIKE $$%\\%$$;
>>
>>    
>>
>
>Yes, as I understand it (as long as you remove the one of the WHEREs :-) ).
>If not we need some rethinking.  Think of this as our equivalent of XML's
>CDATA quoting - you don't need to escape & or < or > inside a CDATA node.
>
>
>  
>
>>in 7.4 or is \ still special there ?
>>    
>>
>
>I don't believe so.
>
>
>  
>


Sat, 04 Oct 2003 08:09:03 -0400
Andrew Dunstan <andrew@dunslane.net>
Re: Using backslash in query
Hannu Krosing <hannu@tm.ee> writes:
> Regarding the dollar-quoting discussions -

> Will we be able to write the above query as 
> SELECT smth. FROM  tbl WHERE WHERE situation LIKE $$%\\%$$;
> in 7.4 or is \ still special there ?

We were discussing that for 7.5 not 7.4.  But yeah, it would work that
way because \ won't be treated specially in dollar-quoted literals.

			regards, tom lane

Sat, 04 Oct 2003 11:45:28 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: Using backslash in query 