Why can MySQL handle multiple updates concurrently and PostgreSQL can't?

Question

Let's imagine you have a table with this definition:

CREATE TABLE public.positions
(
   id serial,
   latitude numeric(18,12),
   longitude numeric(18,12),
   updated_at timestamp without time zone
)

And you have 50,000 rows in this table. Now for testing purposes you will run an update like this:

update positions
set  updated_at = now()
where latitude between 234.12 and 235.00;

That statement will update 1,000 rows from the 50,000 (in this specific dataset).

If you run such a query in 30 different threads*, MySQL innodb will succeed and PostgreSQL will fail with lots of deadlocks.

Why?

---

_{* I'm comparing the latest version of MySQL innodb vs Postgres, this is a concurrent update case. Production cases: imagine 5000 stocks being updated with the latest price available constantly.}

Answer 1

Rolando already more or less described the reason why the deadlocks happen. Let me add that PostgreSQL has to take locks on the rows to be updated, in order to maintain consistency. (now() is fixed to the beginning of the transaction, meaning that two concurrent updates will want to update a given row to a different timestamp, which has to be resolved somehow - taking locks on the rows is the PostgreSQL solution.)

The locks are assigned to the transaction on a first come - first served basis. Deadlocks occur when two transactions try to obtain locks on the same rows in different order. The way to do this is - now not surprisingly - requesting the locks in a predictable order. This is done by

SELECT id -- could be any column, even a constant
FROM position 
WHERE latitude between 234.12 and 235.00
ORDER BY id 
FOR UPDATE;

Here the crucial part is ORDER BY id and FOR UPDATE. The latter takes the necessary locks of the same type the subsequent UPDATE needs.

The SELECT ... FOR UPDATE statement might looks superfluous otherwise (especially when you don't need the selected data), and it also means disk writes even before actually changing the data. This has to be considered when using it.

Answer 2

HISTORY LESSON

On Mar 13, 2013, Uber had switched from MySQL to PostgrsSQL.

Surprisingly, that love affair did not last very long.

On Jun 26, 2016, Uber had switched from PostgreSQL to MySQL.

Why the about face ???

YOUR ACTUAL QUESTION

Running an UPDATE is surprisingly micromanaged in PostgreSQL.

There are two DDL System Identifiers in PostgreSQL that must be properly understood

• ctid : The physical location of the row version within its table. Note that although the ctid can be used to locate the row version very quickly, a row's ctid will change if it is updated or moved by VACUUM FULL. Therefore ctid is useless as a long-term row identifier. The OID, or even better a user-defined serial number, should be used to identify logical rows.
• oid : The object identifier (object ID) of a row. This column is only present if the table was created using WITH OIDS, or if the default_with_oids configuration variable was set at the time. This column is of typeoid (same name as the column); see PostgreSQL Documentation on Object Identifier Types for more information about the type.

With regard to ctids, please note that performing and UPDATE (DELETE/INSERT from a physical standpoint) or VACUUM FULL will change a row's ctid. This does not bode well for tables with many indexes. Why ? This fact was recently discovered (July 26, 2016) by the Data Engineers at Uber.

Please note the following diagram (courtesy of Uber Engineering)

PostgreSQL does not cohesively couple a PRIMARY KEY with non-unique indexes. Since an index references a row by ctid, a simple UPDATE (even on a non-indexed column) will change the ctid, resulting in the need to rewrite the ctid in every index in the table that references that changed row. This is not something new. PostgreSQL has always done this by design.

Therefore, doing an UPDATE on 1000 rows will perform 1000 DELETEs and 1000 INSERTs. As already mentioned, every index attached to the table must have their new row ctid values written in the BTREE index entries, replacing the old row ctid value. Since you have no indexes on the table, you are just experiencing the DELETEs and INSERTs generating the deadlocks you see.

SUPPLEMENTAL INFO

Someone once posted a discussion about this and how to get around it. Others take advantage of the exposure of the Systems Identifiers available to their WHERE clauses:

• Jun 04, 2002 : ctid & updates (or speedy updates/deletes)
• Jul 05, 2011 : Delete completely duplicate rows in PostgreSQL (and keep only 1)
• Nov 26, 2012 : Detecting Table Rewrites with the ctid Column
• May 27, 2014 : How do I decompose ctid into page and row numbers?

The default transaction isolation level is READ COMMITTED. Having indexes that move would provided better consistency of data under this isolation level, but it comes at the cost of the constant rewriting of ctid values in the indexes and well as the MongoDB-like behavior of deleting and inserting a whole new row just for a simple UPDATE. While other transaction isolation levels are possible (REPEATABLE READ, READ UNCOMMITTED, SERIALIZABLE), it may require some specialized SQL against ctid and oid values to maintain needed views of the data in any given transaction. Such specialized queries may be helpful for SELECTs but would be rather untrustworthy for UPDATEs and DELETEs since there is also a VACUUM daemon running and the possibility of ctid going obsolete would be huge. In that case, it would be wise to reference rows in queries by the oid rather that citd.

WHAT ABOUT INNODB ???

InnoDB does not jump through hoops like PostgreSQL to perform an UPDATE. InnoDB does not compel you to write specialized SQL commands that harness rowid-type info to juice up an UPDATE.

InnoDB's default isolation is level is REPEATABLE READ. This is much easier to maintain than READ COMMITTED along with the fact that InnoDB rowids never change.

In order for InnoDB to have this same bad behavior, you would have to run the REPLACE command (which is a mechanical DELETE and INSERT). PostgreSQL performs this operation automatically and there is nothing you can do about it (unless you are brave enough to get the source code and fix or improve the UPDATE process).

Answer 3

I don't think this has anything to do with how UPDATEs are handled by Postgres or MySQL (or Uber's somewhat moot reasons to switch back)

Additionally, with the given setup, Postgres will not create a new row version for every update because no index values are being changed. This case is known as a HOT (Heap-Only Tupple) update. See e.g. here, here or here (plus: as a reaction on Uber's critic an optimization for this is currently being worked on)

The culprit of a deadlock is always acquiring locks in different order from different threads - and that is independent on how the lock is acquired or how the change is physically done in the background.

The big difference between MySQL/InnoDB and Postgres is that MySQL always uses what is called an "index organized table" in Oracle (or a "clustered index" in SQL Server). So the rows of a table are actually stored in an index structure (which isn't always a good choice).

This in turn means that the rows are physically "sorted" by the primary key (if there is no primary key, MySQL will add an invisible column for that) and an update on a table without an index will simply scan the whole table until all rows matching the where clause are found.

The "sorted" storage imposed by an index organized table means the rows are (most probably) always scanned in the same order for each thread - which in turn means the locks are acquired in the same order for each thread - thus avoiding the deadlock.

Postgres does not have index organized tables (clustered indexes) and thus the order in which the locks are obtained is not determined by some implicit order and hence the deadlocks can occur.

Given the nature of regular tables in Oracle (or in SQL Server for tables without a clustered index) I wouldn't be surprised if Oracle or SQL Server showed the same behavior as Postgres.

---

I tried to reproduce this and created a little (Java) test program.

The table was created like this:

create table positions
(
   id integer,
   value_1 numeric(18,12), 
   value_2 numeric(18,12),
   updated_at timestamp
);

insert into positions (id, value_1, value_2)
select i, random() * 50000  + 1, random() * 50000  + 1
from generate_series(1, 50000) i;

So I have 50.000 rows in the table with the value_1 and value_2 columns ranging from 1 to 50.000

The Java program created 50 threads, connected each one to the database and once all were connected the actual updates were started in parallel - this was done to avoid that the first thread was already finished before the last one connected).

update positions 
  set updated_at = current_timestamp
where value_1 between 5000 and 30000;

So it's updating roughly 25.000 rows (half of the table).

Neither in Postgres 9.5, nor in 9.6 did I get a deadlock. After lowering the deadlock timeout from 1 second to 25ms I still did not get a deadlock. Although I do get a lot of lock warnings like the following (if I enable log_lock_waits)

2016-10-12 08:19:53 CEST postgres LOG:  process 6252 still waiting for ExclusiveLock on tuple (9384,1) of relation 1828790 of database 12401 after 31.197 ms
2016-10-12 08:19:53 CEST postgres DETAIL:  Process holding the lock: 11036. Wait queue: 1892, 6252, 9836.

Even after making every thread sleep for 25milliseconds after the update, but before the commit, I did not get any deadlocks.

I also increased the number of rows to 500.000 and the number of updated rows to 250.000, still no deadlock.

You can see the test program here: http://hastebin.com/usuruqolez.java