Determining serialization order for serializable snapshot isolation

• Determination of serialization order for Serializable Snapshot Isolation (SSI).
• Time-travel queries on consistent database state for SSI.
• Sharpness of results: what can happen in non-SSI executions.
• A parametrized version of SSI that bounds the settle-time in serialization order.

Snapshot Isolation (SI) is in wide use by database systems but does not guarantee serializability. Serializable snapshot isolation (SSI) was defined in 2008 by Cahill, Röhm, and Fekete in Ref. [1] and an enhanced version that we call ESSI was defined in 2009 by the same authors [2]. Both guarantee serializable execution by aborting transactions that might be involved in anomalies, but occasional transactions are aborted unnecessarily. The resulting commit order is often different from the serialization order and this can confuse bank auditors, for example. In this paper we show how to determine the proper serialization order of these transactions and store this information for later access. With this known serialization order the database system can perform time-travel queries to capture snapshots of consistent database states in the past. Our algorithm assigns to each SSI or ESSI transaction at its commit time an appropriate serialization order timestamp that falls within the transaction lifetime, i.e., between its start-time and commit-time. The algorithm uses only information already gathered by the algorithm implementing ESSI in [2].