Does ordering by auto-incrementing PK ensure chronological order?

Question

Is it safe to assume that ordering by an auto-incrementing PK in Postgres will order the records chronologically, from a creation standpoint? I have a many to many relationship, from which I don't need to track anything else except the relationship itself and some form of order of creation. I am trying to decide whether I need to incorporate a timestamp column for this, or whether I can reutilize the existing auto-incrementing PK column for that same purpose.

Answer 1

Assuming by "auto-incrementing" you mean the Postgres SERIAL pseudo-type, the short answer is "not always".

SERIAL columns are implemented using standard SQL sequences, which might generate out-of-order values when used by multiple concurrent sessions if the CACHE parameter is set to something more than 1. The manual states this:

[A]lthough multiple sessions are guaranteed to allocate distinct sequence values, the values might be generated out of sequence when all the sessions are considered. For example, with a cache setting of 10, session A might reserve values 1..10 and return nextval=1, then session B might reserve values 11..20 and return nextval=11 before session A has generated nextval=2. Thus, with a cache setting of one it is safe to assume that nextval values are generated sequentially; with a cache setting greater than one you should only assume that the nextval values are all distinct, not that they are generated purely sequentially.

Leaving CACHE value at 1 might hurt performance in an environment with high concurrency, so you will have to choose what is more important to you.

In my view, trying to repurpose SERIAL for tracking order of creation of records is not a good idea, because it potentially creates a maintenance problem: since the sequence's only promise is to provide some unique incrementing value to each nextval request, relying on its behaviour under one circumstance might cause your application to behave unpredictably when the situation changes, e.g. the sequence implementation details are modified in a future Postgres version, or changes in your workload require you to increase the CACHE setting. Using a proper timestamp for orderging is both safer and semantically clearer.

Answer 2

What do you mean by the chronological order?

If there's a transaction 1 that begins before transaction 2, but ends after transaction 2, is the first transaction transaction 1 or transaction 2?

If you're using the SERIALIZABLE transaction isolation level, it guarantees that there is a total order for transactions: that is, there is some serial (non-parallel) order for the transactions that would give the same result as the transactions running in your real life parallel system.

Most likely, PostgreSQL sequences will not give the exact same ordering for values than the serializable total order. You could fix this by creating your own sequence: create a table with one row having one integer column, and update that row. However, if doing that, the parallelizability of your transactions suffers. It can even suffer in a manner that causes some of the transactions to fail.

One solution, as proposed by a comment, is timestamps. However, the timestamp order is not necessarily the same as the serial order that would give the same results.

(As a side note, you should be prepared for failed transactions in all cases. Deadlocks cause failed transactions. The SERIALIZABLE isolation level causes even more failed transactions. The proper way is to have exponential back-off and retry.)