A Read-Only Transaction Anomaly Under Snapshot Isolation
By Alan Fekete, Elizabeth O'Neil, and Patrick O'Neilfekete@it.usyd.edu.au,{eoneil,poneil}@cs.umb.edu

Research of all authors was supported by NSF Grant IRI 97-11374.

Abstract. Snapshot Isolation (SI),is a multi-version concurrency control
algorithm introduced in [BBGMOO95] andlater implemented by Oracle. SI avoids
many concurrency errors, and it neverdelays read-only transactions. However
it does not guarantee serializability.
It has been widely assumed that, underSI, read-only transactions always execute serializably provided the concurrent update transactions are serializable. The reason for this is that all
SI reads return values from a single
instant of time when all committed
transactions have completed theirwrites and no writes of non-committed
transactions are visible. This seems
to imply that read-only transactions
will not read anomalous results solong as the update transactions withwhich they execute do not write such
results. In the current note, however,
we exhibit an example contradicting
these assumptions: it is possible for
an SI history to be non-serializable
while the sub-history containing all
update transactions is serializable.

1. Definition of Snapshot Isolation
In what follows, we assume time ismeasured by a counter that advances
whenever any transaction starts orcommits, and we designate the time
when transaction Ti starts asstart(Ti) and the time when Ti commits
as commit(Ti).
Definition 1.1: Snapshot Isolation (SI). A transaction Ti executing under SI conceptually reads
data from the committed state of thedatabase as of time start(Ti) (thesnapshot), and holds the results of
its own writes in local memory store,
so if it reads data it has written it
will read its own output. Predicatesevaluated by Ti are also based on rows
and index entry versions from the committed state of the database at timestart(Ti), adjusted to take Ti's own
writes into account. Snapshot Isolation also must obey a "First Committer(Updater) Wins" rule, explained below•-1-The interval in time from the start
to the commit of a transaction, represented [Start(Ti), Commit(Ti)], iscalled its transactional lifetime. Wesay two transactions T1 and T2 areconcurrent if their transactional
lifetimes overlap, i.e., [start(T1),commit(T1)] ∩ [start(T2), commit(T2)]≠ Φ. Writes by transactions active
after Ti starts, i.e., writes byconcurrent transactions, are not visible to Ti. When Ti is ready to commit,
it obeys the First Committer Wins
rule, as follows: Ti will successfullycommit if and only if no concurrent
transaction Tk has already committed
writes (updates) of rows or index
entries that Ti intends to write. See
also the discussion of the variant
First Updater Wins rule below.
The First Committer Wins rule isreminiscent of certification in optimistic concurrency control, but only
items written by Ti are checked forconcurrent modification, not items
read.
In the Oracle implementation ofSnapshot Isolation (referred to as theSERIALIZABLE Isolation Level in Oracle[JAC95]), an attempt by Ti to read arow that has changed since start(Ti)will cause the system to read an appropriate older version in the rollback segment. Indexes are also accessed in the appropriate snapshot
state, so that predicate evaluation
retrieves row versions current as ofthe snapshot. The First Committer Wins
rule is enforced, not by a commit-timevalidation, but by checks done at thetime of updating. If Ti and Tk areconcurrent, and Ti updates the data
item X, then it will take a Write lockon X; if Tk subsequently attempts toupdate X while Ti is still active, Tk
will be prevented by the lock on Xfrom making further progress. If Ti
then commits, Tk will abort; Tk will
only be able to continue if Ti drops
its lock on X by aborting. If, on theother hand, Ti and Tk are concurrent,and Ti updates X but then commits before Tk attempts to update X, therewill be no delay due to locking, butTk will abort immediately when it attempts to update X (the abort does notwait until Tk attempts to commit). For
Oracle we rename the First Committer
Wins rule to First Updater Wins; theultimate effect is the same – one of
the concurrent transactions updating adata item aborts. Aborts by a transaction for this reason are known as serialization errors, ORA-08177 (OracleRelease 9.2).
Snapshot Isolation is an attractive
isolation level. Reading from a snapshot means that a transaction neversees the partial results of othertransactions: T sees all the changes
made by transactions that commit before start(T), and it sees no changes
made by transactions that commit afterstart(T). Also, the First Committer
Wins rule allows SI to avoid the mostcommon type of lost update error, as
shown in Example 1.1.
2. Anomaly Behavior in SI
Most of the anomalies that occur inlower Locking Isolation Levels such as
READ COMMITTED are absent in SI.
Example 1.1 gives an example.
Example 1.1. Lost Update. If
transaction T1 tries to modify a data
item X while a concurrent T2 also
tries to modify X, then SI's First
Committer Wins rule will cause one of
the transactions to abort, so thefirst update will not be lost. E.g.,
in example history H1 below, we display the values read and written in a
versioned notation we use to specify
SI histories; when Ti writes a versionof X, the version is named Xi.
H1: R1(X0,50) R2(X0,50) W2(X2,70) C2
W1(X1,60) A1
This history leaves X with the value
70 (version X2), since only T2, attempting to add an increment of 20 toX, was able to complete. T1 can now
retry and hopefully add its incrementof 10 to X without interference. Notethat many database system productswith locking-based concurrency default-2-

to the READ COMMITTED isolation level,
which takes long-term write-locks but
no long-term read locks (it only tests
reads to make sure they do not read
write-locked data); in that case, thehistory above without the versioned
data items would succeed in both its
writes, causing a Lost Update. •Despite its attractions, SI does not
ensure that all executed histories areserializable, as defined in classicaltransactional theory (e.g., in [BHG87,PAPA86, GR93]). Indeed it is possible
for a set of transactions, each ofwhich in isolation respects an integrity constraint, to execute under SI
in such a way as to leave the databasein a corrupted state. One such problem
is called "Write Skew".
Example 1.2. Write Skew. Suppose X
and Y are data items in different rows
representing checking account balancesof a married couple at a bank, with aconstraint that X+Y > 0 (the bank permits either account to be overdrawn,
as long as the sum of the account balances remains positive). Assume that
initially X0 = 70 and Y0 = 80. UnderSI, transaction T1 reads X0 and Y0,
then subtracts 100 from X, assuming it
is safe because the two data items
added up to 150. Transaction T2 concurrently reads X0 and Y0, then subtracts 100 from Y, assuming it is safefor the same reason. Each update issafe by itself, but SI will result in
the following history:
H2: R1(X0,70) R2(X0,70) R1(Y0,80)
R2(Y0,80) W1(X1,-30) C1 W2(Y2,-20) C2
Here the final committed state (X1 andY2) violates the constraint X+Y > 0.
This problem was not detected by First
Committer Wins because two different
data items were updated, each under
the assumption that the other remained
stable. Hence the name "Write Skew". •While Example 1.2 displays one of anumber of anomalous situations that
can arise in SI, the occurrence ofsuch situations is actually rather
rare in real-world applications. TheTPC-C benchmark application [TPC-C],
consisting of seven transactional pro-grams, displays no such anomalies, and
it is reasonably representative. We
also point out that it is quite easy
to modify application or database design to avoid the anomaly of Example
1.2. One way is to require in thetransactional program that each Readof X and Y to update Y give the impression of a Write of X (this is possible in Oracle using the Select ForUpdate statement). Now it seems thatboth X and Y are updated in H2 andcollision will occur. Another approachrequires that each constraint on thesum of two accounts X and Y be materialized in another row Z and insist
that all updates of X and Y must keep
Z up to date. Then the anomaly of history H will not arise, since collisionon updates of Z will occur whenever Xand Y are updated by two different
transactions.
3. A Read-Only
Anomaly in SITransaction

Another type of anomaly can occur resulting from read-only transaction
participation. As we explained in theAbstract, this is surprising. Startingwith [BBGMOO95], it was assumed that
read-only transactions always execute
serializably, without ever needing towait or abort because of concurrentupdate transactions. This seemed selfevident because all reads take placeat an instant of time, when all committed transactions have completed
their writes and no writes of non-committed transactions are visible. The
implied guarantee is that read-onlytransactions will not read anomalous
results so long as the update transactions do not write such results. But
Example 1.3 shows this isn't true.
Example 1.3. Read-Only Transaction Anomaly. Suppose X and Y aredata items in different rows representing a checking account balance anda savings account balance, and that
initially X0 = 0 and Y0 = 0. In history H3 below, transaction T1 deposits
20 to the savings account Y, T2 subtracts 10 from the checking account X,
considering the withdrawal covered aslong as X+Y > 0, but accepting anoverdraft with a penalty charge of 1-3-

if X+Y goes negative; finally, T3 is aread-only transaction that retrieves
the values of X and Y and prints themout for the customer. For one sequenceof operations, this can result in thefollowing history under SI:
H3: R2(X0,0) R2(Y0,0) R1(Y0,0)
W1(Y1,20) C1 R3(X0,0) R3(Y1,20) C3
W2(X2,-11) C2
The anomaly that arises in this transaction is that read-only transaction
T3 prints out X = 0 and Y = 20, while
final values are Y = 20 and X = -11.
This can’t happen in any serializable
execution since if 20 was added to Y
before 10 was subtracted from X, nocharge of 1 would ever occur, and thefinal balance should be 10, not 9. A
customer, knowing a deposit of 20 was
due and worried that his check for 10
might have caused a penalty, would
conclude he was safe based on the dataread by T3. Indeed, such a print-out
by T3 would be embarrassing for a bankshould the SEC ask how the charge occurred. We also note that any execution of T1 and T2 (with arbitrary parameter values) without T3 present
will always act serializably. •Intuitive Explanation of Example
1.3. In H3, T2 reads X0 = 0 and Y0 =0, then writes X2 = -11, while T1 concurrently updates Y1 to hold 20, which
would change the behavior of T2 if T2started after T1 committed. The onlyequivalent serial history ending with
X = -11 and Y = 20 must have T2 followed by T1. But since concurrent
transactions don't see each other's
results in SI, T1 can commit first(out of serial order). Now the readonly transaction T3 can see the committed state of T1 only: Y = 20, and X= 0, and conclude that the deposit
came in before the charge, implying
there would be no penalty charge whenT2 executes. The fact that SI allows
commit order different than serial
order is what causes the anomaly.
Conclusion There is great practicalvalue in understanding the propertiesof database histories under weak isolation (that is, with concurrencycontrol that does not automaticallyguarantee serializable behavior). It
is especially important to understandwhat can and can’t happen when runningunder SI, in view of the wide commercial penetration of the Oracle DBMS,
which implements SI. Several papers
have identified sufficient conditions
that can be checked for application
programs to guarantee serializable behavior for those applications [F99,BLL00]. We are in the process of attempting to develop a broad theory
which covers the anomalies of Example
1.2 and 1.3, along with numerous others. We hope our theory will guide theapplication designer to adjust theprograms without changing their functionality, so that serializability isguaranteed.

References[BBGMOO95] H. Berenson, P. Bernstein, J. Gray, J.
Melton, E. O’Neil, and P. O’Neil. A Critique of ANSISQL Isolation Levels. Proc. of the ACM SIGMODInternational Conference on Management of Data, 1995.
Pages 1-10.
[BHG87] P. A. Bernstein, V. Hadzilacos, and N.
Goodman. Concurrency Control and Recovery inDatabase Systems. Addison Wesley, 1987. (This text is
now out of print but can be downloaded fromhttp://research.microsoft.com/pubs/ccontrol/default.htm)[BLL00] A. Bernstein, P. Lewis and S. Lu. Semantic
Conditions for Correctness at Different Isolation Levels.
In Proceedings of IEEE International Conference on DataEngineering, 2000. Pages 57-66.
[F99] A. Fekete. Serializability and Snapshot Isolation.
Proceedings of the Australian Database Conference,Auckland, New Zealand, January 1999. Pages 201-210.
[GR93] J. N. Gray and A. Reuter. Transaction
Processing: Concepts and Techniques. MorganKaufmann Publishers Inc., 1993.
[JAC95] K. Jacobs, with contributors: R. Bamford, G.
Doherty, K. Haas, M. Holt, F. Putzolu, B. Quigley.
Concurrency Control: Transaction Isolation andSerializability in SQL92 and Oracle7. Oracle White
Paper, Part No. A33745, July, 1995.
[PAPA86] C. Papadimitriou. The Theory of Database
Concurrency Control. Computer Science Press, 1986.

-4-[TPC-C] TPC-C Benchmark Specification, available at
http://www.tpc.org/