Write Skew anomaly in Oracle and PostgreSQL does not rollback transaction

Question

I noticed the following occurrence in both Oracle and PostgreSQL.

Considering we have the following database schema:

create table post (
    id int8 not null, 
    title varchar(255), 
    version int4 not null, 
    primary key (id));    

create table post_comment (
    id int8 not null, 
    review varchar(255), 
    version int4 not null, 
    post_id int8, 
    primary key (id));

alter table post_comment 
    add constraint FKna4y825fdc5hw8aow65ijexm0 
    foreign key (post_id) references post;  

With the following data:

insert into post (title, version, id) values ('Transactions', 0, 1);
insert into post_comment (post_id, review, version, id) 
    values (1, 'Post comment 1', 459, 0);
insert into post_comment (post_id, review, version, id) 
    values (1, 'Post comment 2', 537, 1);
insert into post_comment (post_id, review, version, id) 
    values (1, 'Post comment 3', 689, 2); 

If I open two separate SQL consoles and execute the following statements:

TX1: BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;

TX2: BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;

TX1: SELECT COUNT(*) FROM post_comment where post_id = 1;

TX1: > 3

TX1: UPDATE post_comment SET version = 100 WHERE post_id = 1;

TX2: INSERT INTO post_comment (post_id, review, version, id) VALUES (1, 'Phantom', 0, 1000);

TX2: COMMIT;

TX1: SELECT COUNT(*) FROM post_comment where post_id = 1;

TX1: > 3

TX1: COMMIT;

TX3: SELECT * from post_comment;

     > 0;"Post comment 0";100;1
       1;"Post comment 1";100;1
       2;"Post comment 2";100;1
       1000;"Phantom";0;1

As expected, the SERIALIZABLE isolation level has kept the snapshot data from the beginning of the TX1 transaction and TX1 only sees 3 post_comment records.

Because of the MVCC model in Oracle and PostgreSQL, TX2 is allowed to insert a new record and commit.

Why is TX1 allowed to commit? Because this is a Write Skew anomaly, I was expecting to see that TX1 would be rolled back with a "Serialization failure exception" or something similar.

Does the MVCC Serializable model in PostgreSQL and Oracle only offer a snapshot isolation guarantee but no Write Skew anomaly detection?

UPDATE

I even changed Tx1 to issue an UPDATE statement that changes the version column for all post_comment records belonging to the same post.

This way, Tx2 creates a new record and Tx1 is going to commit without knowing that a new record has been added that satisfied the UPDATE filtering criteria.

Actually, the only way to make it fail on PostgreSQL is if we execute the following COUNT query in Tx2, prior to inserting the phantom record:

Tx2: SELECT COUNT(*) FROM post_comment where post_id = 1 and version = 0

TX2: INSERT INTO post_comment (post_id, review, version, id) VALUES (1, 'Phantom', 0, 1000);

TX2: COMMIT;

Then Tx1 is going to be rolled back with:

org.postgresql.util.PSQLException: ERROR: could not serialize access due to read/write dependencies among transactions
  Detail: Reason code: Canceled on identification as a pivot, during conflict out checking.
  Hint: The transaction might succeed if retried.

Most likely that the write-skew anomaly prevention mechanism detected this change and rolled back the transaction.

Interesting that Oracle does not seem to be bothered by this anomaly and so Tx1 just commits successfully. Since Oracle does not prevent write-skew from happening, Tx1 commits juts fine.

By the way, you can run all these examples yourself since they are on GitHub.

Hampstead

TX2 commits, since it's the first to change data and commit. TX1 does not change the same data and therefore does not need to throw any exception, since it is possible to construct a serialized timeline of transactions including TX1. If TX1 would change the same data or data that depends on your data, it would throw an error. – Anticoagulant

I'm going to try with a read-write transaction then. – Hampstead

I added an UPDATE statement in TX1, and still Tx1 is able to commit. – Hampstead

@Vlad: The behaviour is entirely consistent with what you'd see if you ran TX1 and then ran TX2. In other words, the transactions have been successfully serialised; there is no serialisation failure. There are a lot of good examples on the Postgres wiki which might give you a feel for where/when/why you should expect serialisation errors to occur. – Potentiometer

That makes sense. If Tx1 and Tx2 would run completely one after the other, we would get the same outcome. – Hampstead

I managed to add a use case where Tx1 fails on PostgreSQL which validates your previous statement. Interesting that it works just fine in Oracle. – Hampstead

Answer 1

In the 1995 paper, A Critique of ANSI SQL Isolation Levels, Jim Gray and co, described Phantom Read as:

P3: r1[P]...w2[y in P]...(c1 or a1) (Phantom)

One important note is that ANSI SQL P3 only prohibits inserts (and updates, according to some interpretations) to a predicate whereas the definition of P3 above prohibits any write satisfying the predicate once the predicate has been read — the write could be an insert, update, or delete.

Therefore, a Phantom Read does not mean that you can simply return a snapshot as of the start of the currently running transaction and pretend that providing the same result for a query is going to protect you against the actual Phantom Read anomaly.

In the original SQL Server 2PL (Two-Phase Locking) implementation, returning the same result for a query implied Predicate Locks.

The MVCC (Multi-Version Concurrency Control) Snapshot Isolation (wrongly named Serializable in Oracle) does not actually prevent other transactions from inserting/deleting rows that match the same filtering criteria with a query that already executed and returned a result set in our current running transaction.

For this reason, we can imagine the following scenario in which we want to apply a raise to all employees:

1. Tx1: SELECT SUM(salary) FROM employee where company_id = 1;
2. Tx2: INSERT INTO employee (id, name, company_id, salary) VALUES (100, 'John Doe', 1, 100000);
3. Tx1: UPDATE employee SET salary = salary * 1.1;
4. Tx2: COMMIT;
5. Tx1: COMMIT:

In this scenario, the CEO runs the first transaction (Tx1), so:

1. She first checks the sum of all salaries in her company.
2. Meanwhile, the HR department runs the second transaction (Tx2) as they have just managed to hire John Doe and gave him a 100k $ salary.
3. The CEO decides that a 10% raise is feasible taking into account the total sum of salaries, being unaware that the salary sum has raised with 100k.
4. Meanwhile, the HR transaction Tx2 is committed.
5. Tx1 is committed.

Boom! The CEO has taken a decision on an old snapshot, giving a raise that might not be sustained by the current updated salary budget.

You can view a detailed explanation of this use case (with lots of diagrams) in the following post.

Is this a Phantom Read or a Write Skew?

According to Jim Gray and co, this is a Phantom Read since the Write Skew is defined as:

A5B Write Skew Suppose T1 reads x and y, which are consistent with C(), and then a T2 reads x and y, writes x, and commits. Then T1 writes y. If there were a constraint between x and y, it might be violated. In terms of histories:

A5B: r1[x]...r2[y]...w1[y]...w2[x]...(c1 and c2 occur)

In Oracle, the Transaction Manager might or might not detect the anomaly above because it does not use predicate locks or index range locks (next-key locks), like MySQL.

PostgreSQL manages to catch this anomaly only if Bob issues a read against the employee table, otherwise, the phenomenon is not prevented.

UPDATE

Initially, I was assuming that Serializability would imply a time ordering as well. However, as very well explained by Peter Bailis, wall-clock ordering or Linearizability is only assumed for Strict Serializability.

Therefore, my assumptions were made for a Strict Serializable system. But that's not what Serializable is supposed to offer. The Serializable isolation model makes no guarantees about time, and operations are allowed to be reordered as long as they are equivalent to a some serial execution.

Therefore, according to the Serializable definition, such a Phantom Read can occur if the second transaction does not issue any read. But, in a Strict Serializable model, the one offered by 2PL, the Phantom Read would be prevented even if the second transaction does not issue a read against the same entries which we are trying to guard against phantom reads.

Hampstead

Hey @Vlad, in your book at page 97, you mentioned in the summary table for REPEATABLE_READS that Postgres allows WRITE SKEW, but when you explain WRITE SKEW on page 91, both txs issue a read to both tables, Postgres wold be able to catch and forbid this. – Fideliafidelio

There are two types of write skews, actually: G1: Anti-dependency Cycles (write skew on disjoint read) and G2: Anti-Dependency Cycles (write skew on predicate read). The one in my book is G1, this one here is G2. PostgreSQL does not prevent any of them in RR. – Hampstead

yes indeed got it, just reviewed it, also took a look at some of you blog posts on the topic :). – Fideliafidelio

I'm glad I could help 😌 – Hampstead

Answer 2

I just wanted to point that Vlad Mihalcea's answer is plain wrong.

Is this a Phantom Read or a Write Skew?

Neither of those -- there is no anomaly here, transactions are serializable as Tx1 -> Tx2.

SQL standard states: "A serializable execution is defined to be an execution of the operations of concurrently executing SQL-transactions that produces the same effect as some serial execution of those same SQL-transactions."

PostgreSQL manages to catch this anomaly only if Bob issues a read against the employee table, otherwise the phenomenon is not prevented.

PostgreSQL's behavior here is 100% correct, it just "flips" apparent transactions order.

Depilatory

Then, how do you explain that you can get different outcomes if you run the same example in an MVCC-based database or a 2PL based one? Try to run in on Serializable isolation level on MySQL or SQL Server and you will see a different result. So, it means that the flavor of Concurrency Control allows for different ordering and different outcomes while still considering that both outcomes are correct, right? – Hampstead

What exact outcome do you mean here? E.g. in MS SQL the Tx2 is just blocked, so I can't commit Tx2 first. – Depilatory

Exactly. So, like any Concurrency control mechanism, a conflict is either prevented (2PL) or detected (MVCC). Here, 2PL prevents it, but MVCC allows it. – Hampstead

For more details, watch out my Transactions and Concurrency Control presentation from Voxxed Zurich. – Hampstead

No, SSI doesn't allow it. Again, you didn't demonstrate any anomaly. Look, any execution that produces the same result as either tx1->tx2 or tx2->tx1 (taking in account committed transactions only, of course) is, by definition, serializable. The difference here is that 2PL prevents one of serializable schedules, while SSI (correctly) does not. – Depilatory

Thanks for pointing it out. I now realized where I was wrong. My assumptions were valid for Strict Serializability, meaning that read and writes are Linearizable as well. However, the Serializable isolation level does not entail any wall-clock ordering semantics, hence you are absolutely right. I'll update my answer. Cheers! – Hampstead

"However, the Serializable isolation level does not entail any wall-clock ordering semantics." Yes, exactly. Thanks for fixing the answer (and for the link, BTW)! – Depilatory

Answer 3

What you observe is not a phantom read. That would be if a new row would show up when the query is issued the second time (phantoms appear unexpectedly).

You are protected from phantom reads in both Oracle and PostgreSQL with SERIALIZABLE isolation.

The difference between Oracle and PostgreSQL is that SERIALIZABLE isolation level in Oracle only offers snapshot isolation (which is good enough to keep phantoms from appearing), while in PostgreSQL it will guarantee true serializability (i.e., there always exists a serialization of the SQL statements that leads to the same results). If you want to get the same thing in Oracle and PostgreSQL, use REPEATABLE READ isolation in PostgreSQL.

Elastance

No, the outcome of count has not neen modified. Both times TX1 issued the query, it returned 3, even though TX2 had inserted a new value in the meantime. There is now way to see the new row in TX1. – Elastance

I don;t think it's as simple as that, or as simple as the SQL standard tries to picture how a phantom row is supposed to happen. It just depends on what the transaction executor considers to be an anomaly or not. Check out the updated section. If I add a select COUNT in Tx2, PostgreSQL will detect that Tx1 no longer holds true since Tx2 already took a decision based on a snapshot value that Tx1 is about to change. Oracle does not detect any anomaly, so it's just committing both transactions successfully. – Hampstead

I don't see where your problem is. The database presents each transaction with a consistent world-view, in this case that TX1 completed before TX2 even began. Nobody sees an inconsistency. Why do you want an error to be thrown? – Elastance

Consider that you selected all the employees in a company and want to give them a raise. After you run the query, the HR department decides to add a new employee. Your thread is resumed and you update the salary for the employees that you previously selected. In this scenario, the entry added by the HR department will not get any raise. There are two ways to overcome this issue: either you block Tx2 until Tx1 runs, or you rollback Tx1 because the view of the world has changed since Tx1 started. – Hampstead

No, because the new employee was added (logically) after all employees got a raise. Nobody guarantees you a certain transaction order. – Elastance

Right. But a Phantom Read should prevent a second transaction from modifying the view of what I have previously selected. That happens in SQL Server (2PL) and MySQL (because InnoDB takes locks for Serializable), but not for Oracle and PostgreSQL. That's exactly the point for having these anomalies prevented because transactions can be interleaved. – Hampstead

There is no phantom read. Oracle and PostgreSQL with MVCC just prevent phantom reads in a different way from databases that use locking. Read up on what a phantom read is - there is more than one way to skin the cat in this case. Most people prefer a solution where consistency is preserved without throwing an error. – Elastance

@Vlad: SERIALIZABLE only guarantees that things can be serialised. If you want to lock things, use locks. – Potentiometer

Then why does a lost update throws an exception then on MVCC. If you select the same record in Tx1 and Tx2, and both Tx1 and Tx2 modify it, then the first transaction can commit while the second one throws an exception. MVCC works through anomaly detection, while locks work by preventing anomalies. If you think that there is no Phantom Read here, then what is the purpose of serving an old snapshot value if you still allow it to be modified? That is not the case for lost updates, but it is here. – Hampstead

@Nick SERIALIZABLE guarantees that transactions have the same outcome if interleaved as if they have been executed one after another. Check out the updated section, the one that issues a select in Tx2. If I have a business logic that says to insert a new record if the select count is 3, then Tx2 runs fine in MVCC. However, if I execute Tx2 after Tx1, it will not issue the insert because the count value is 0 (the versions have changed to 100 in Tx1). That works on PostgreSQL, but not on Oracle in a SERIALZABLE transaction. – Hampstead

You can only update a row if you see its most recent version, that's why the scenario from your comment throws a serialization error -- if no error were thrown, no serialized order of these two transactions were possible. This has nothing to do with phantom reads. The purpose of serving an old snapshot value is to prevent phantom reads. – Elastance

A good description of this phenomena is in "Making Snapshot Isolation Serializable" by Fekete, Liarokapis, O'Neil, O'Neil, and Shasha. ACM Trans. Database Syst. 30(2): 492-528 (2005). Another good read is Serializable Executions with Snapshot Isolation: Modifying Application Code or Mixing Isolation Levels? DASFAA 2008: 267-281. – Koller

Answer 4

The Postgres documentation defines a phantom read as:

A transaction re-executes a query returning a set of rows that satisfy a search condition and finds that the set of rows satisfying the condition has changed due to another recently-committed transaction.

Because your select returns the same value both before and after the other transaction committed, it does not meet the criteria for a phantom read.

Humes

It returns the same value because SERIALIZABLE instructs the query executor to take the row versions as of the beginning of the TX1 transaction. But there's an anomaly because in reality, we have 4 records (Tx2 has been committed already) not 3 at the end of the Tx1 transaction. So, the assumptions are not held at the end of Tx1, that's why Tx1 should be rolled back. – Hampstead

In case you and the SQL standard disagree on what should be rolled back, I think Postgres is wise to follow the SQL standard ;) – Humes

I updated the question so that now Tx1 issues an UPDATE statement, and Tx1 is still able to commit. On MySQL and SQL Server, Tx2 is prevented to execute. On PostgreSQL and Oracle, Tx2 runs just fine, and Tx1 commits without any failure. Don't you think that Tx1 should be rolled back? Check out the outcome on Tx3. – Hampstead

Put the phantom insert BEFORE the UPDATE and you should get a serialization failure. You're confusing execution time with commit time; serialization checks take place as statements execute, taking into account what's happening in other uncommitted transactions, but only looking at other uncommitted statements that have already executed. – Chockablock