Lecture 7:

Concurrency control

Rasmus Pagh

Database Tuning, Spring 2007 1

 Today’s lecture

• Concurrency control basics

• Conflicts and serializability
• Locking
• Isolation levels in SQL
• Optimistic concurrency control
• Transaction tuning
• Transaction chopping

Database Tuning, Spring 2007 2

 Problem session

• Come up with examples of undesired

behaviour that could occur if several
transactions run in parallel such that
the actions interleave. Consider e.g.:
– Transferring money and adding interest in
a bank’s database.
– Booking plane tickets.

Database Tuning, Spring 2007 3

ACID properties of transactions

• Atomicity: A transaction is executed

either completely or not at all.
• Consistency: Database constraints
must be kept.
• Isolation: Transactions must appear to
execute one by one in isolation.
• Durability: The effect of a committed
transaction must never be lost.

Database Tuning, Spring 2007 4

 Today: Atomicity and isolation

• This lecture is concerned with atomicity

and isolation.
• Durability: Read RG 18, or SB 2.3
• Consistency is a consequence of
atomicity and isolation + maintaining
any declared DB constraint (not
discussed in this course).

Database Tuning, Spring 2007 5

 Isolation and serializability

• We would like the DBMS to make

transactions satisfy serializability:
– The state of the database should always
look as if the committed transactions were
performed one by one in isolation (i.e., in a
serial schedule).
• The scheduler of the DBMS is allowed
to choose the order of transactions:
– It is not necessarily the transaction that is
started first, which is first in the serial
schedule.
– The order may even look different from the
viewpoint of different users.

Database Tuning, Spring 2007 6

 A simple scheduler

• A simple scheduler would maintain a

queue of transactions, and carry them
out in order.
• Problems:
– Transactions have to wait for each other,
even if unrelated (e.g. requesting data on
different disks).
– Smaller throughput. (Why?)
– Some transactions may take very long, e.g.
when external input or remote data is
needed during the transaction.

Database Tuning, Spring 2007 7

 Interleaving schedulers

• Good DBMSs have schedulers that

allow the actions of transactions to
interleave.
• However, the result should be as if
some serial schedule was used.
• Such schedules are called serializable.
• In practice schedulers do not recognize
all serializable schedules, but allow just
some.
Next: Conflict serializable schedules.

Database Tuning, Spring 2007 8

 Simple view on transactions

• We regard a transaction as a sequence

of reads and writes of DB elements,
that may interleave with sequences of
other transactions.
• DB elements could be e.g. a value in a
tuple, an entire tuple, or a disk block.
• rT(X), shorthand for ”transaction T
reads database element X”.
• wT(X), shorthand for ”transaction T
writes database element X”.

Database Tuning, Spring 2007 9

 Conflicts

• The order of some operations is of no

importance for the final result of
executing the transactions.
• Example: We may interchange the
order of any two read operations
without changing the behaviour of the
transaction(s) doing the reads.
• In other cases, changing the order may
give a different result - there is a
conflict.

Database Tuning, Spring 2007 10

 What operations conflict?

• By considering all cases, it can be seen

that two operations can conflict only if:
– They involve the same DB element, and
– At least one of them is a write operation.
• Note that this is a conservative (but
safe) rule.

rT1(A) wT1(A)
rT2(A) rT2(A)

Database Tuning, Spring 2007 11

 Conflict serializability

• Suppose we have a schedule for the

operations of several transactions.
• We can obtain conflict-equivalent
schedules by swapping adjacent
operations that do not conflict.
• If a schedule is conflict-equivalent to a
serial schedule, it is serializable.
• The converse is not true (ex. in RG).

Database Tuning, Spring 2007 12

 Testing conflict serializability

• Suppose we have a schedule for the

operations of current transactions.
• If there is a conflict between operations
of two transactions, T1 and T2, we
know which of them must be first in a
conflict-equivalent serial schedule.
• This can be represented as a directed
edge in a graph with transactions as
vertices.

Database Tuning, Spring 2007 13

 Problem session
• Find a criterion on the precedence graph
which is equivalent to conflict-serializability:
– If the graph meets the criterion the schedule is
conflict-serializable, and
– If the schedule is conflict-serializable, the graph
meets the criterion.

Database Tuning, Spring 2007 14

 Enforcing serializability

• Knowing how to recognize conflict-

serializability is not enough.
• We will now study mechanisms that
enforce serializability:
– Locking (pessimistic concurrency control).
– Time stamping (optimistic concurrency
control).

Database Tuning, Spring 2007 15

 Locks

• In its simplest form, a lock is a right to

perform operations on a database
element.
• Only one transaction may hold a lock
on an element at any time.
• Locks must be requested by
transactions and granted by the locking
scheduler.

Database Tuning, Spring 2007 16

 Two-phase locking

• Commercial DBMSs widely use two-

phase locking, satisfying the condition:
– In a transaction, all requests for locks
precede all unlock requests.
• If two-phase locking is used, the
schedule is conflict-equivalent to a
serial schedule in which transactions
are ordered according to the time of
their first unlock request. (Why?)

Database Tuning, Spring 2007 17

 Strict two-phase locking

• In strict 2PL all locks are released

when the transaction completes.
• This is commonly implemented in
commercial systems, since:
– it makes transaction rollback easier to
implement, and
– avoids so-called cascading aborts (this
happens if another transaction reads a
value by a transaction that is later rolled
back)

Database Tuning, Spring 2007 18

 Lock modes

• The simple locking scheme we saw is

too restrictive, e.g., it does not allow
different transactions to read the same
DB element concurrently.
• Idea: Have several kinds of locks,
depending on what you want to do.
Several locks on the same DB element
may be ok (e.g. two read locks).

Database Tuning, Spring 2007 19

 Shared and exclusive locks

• Locks for reading can be shared (S).

• Locks needed for writing must be
exclusive (X).
• Compatibility matrix says which locks
are granted:
Lock requested
S X
Lock held S Yes No
X No No

Database Tuning, Spring 2007 20

 Update locks

• A transaction that will eventually write

to a DB element, may allow other DB
elements to keep read locks until it is
ready to write.
• This can be achieved by a special
update lock (U) which can be upgraded
to an exclusive lock.

Database Tuning, Spring 2007 21

 Compatibility for update locks

Lock requested
S X U
S Yes No Yes
Lock held
X No No No
U No (!) No No

• Question: Why not upgrade shared

locks?

Database Tuning, Spring 2007 22

 The locking scheduler

• The locking scheduler is responsible for

granting locks to transactions.
• It keeps lists of all currents locks, and
of all current lock requests.
• Locks are not necessarily granted in
sequence, e.g., a request may have to
wait until another transaction releases
its lock.
• Efficient implementation not discussed
in this lecture.

Database Tuning, Spring 2007 23

 Problem session

• So far we did not discuss what DB

elements to lock: Atomic values, tuples,
blocks, relations?
• What are the advantages and
disadvantages of fine-grained locks
(such as locks on tuples) and coarse-
grained locks (such as locks on
relations)?
• Explain the following advice from SB:
”Long transactions should use table
locks, short transactions should use
record locks”.

Database Tuning, Spring 2007 24

 Granularity of locks

• Fine-grained locks allow a lot of

concurrency, but may cause problems
with deadlocks.
• Coarse-grained locks require fewer
resources by the locking scheduler.
• We want to allow fine-grained locks,
but use (or switch to) coarser locks
when needed.
• Some DBMSs switch automatically -
this is called lock escalation. The
downside is that this easily leads to
deadlocks.
Database Tuning, Spring 2007 25
 Multiple-granularity locking

• An exclusive lock on a tuple should

prevent an exclusive lock on the whole
relation.
• To implement this, all locks must be
accompanied by intention locks at
higher levels of the hierarchy of
database elements.
• We denote shared/exclusive intention
locks by IS/IX, where I stands for the
intention to shared/exclusively lock
database elements at a lower level.
Database Tuning, Spring 2007 26
 Compatibility of intention locks

Lock requested
IS IX S X
IS Yes Yes Yes No

Lock held IX Yes Yes No No

S Yes No Yes No
X No No No No

Database Tuning, Spring 2007 27

 Locks on indexes

• When updating a relation, any indexes

on the table also need to be updated.
• Again, we must use locks to ensure
serializability.
• B-trees have a particular challenge:
The root may be changed by any
update, so it seems concurrent updates
can’t be done using locks.

Database Tuning, Spring 2007 28

 Locks in B-trees

• First idea:
– Put an exclusive lock on a B-tree node if
there is a chance it may have to change.
– Lock from top to bottom along the path.
– Unlock from bottom to top as soon as
nodes have been updated.
• Refinement:
– Get IX locks top-down on the search path.
– Convert these to X locks top-down, as
needed.

Database Tuning, Spring 2007 29

 Phantom tuples

• Suppose we lock tuples where A=42 in

a relation, and subsequently another
tuple with A=42 is inserted.
• For some transactions this may result
in unserializable behaviour, i.e., it will
be clear that the tuple was inserted
during the course of a transaction.
• Such tuples are called phantoms.

Database Tuning, Spring 2007 30

 Avoiding phantoms

• Phantoms can be avoided by putting an

exclusive lock on a relation before
adding tuples. (However, this gives
poor concurrency.)
• A technique called index locking may
prevent other transactions from
inserting phantom tuples, but allow
most non-phantom insertions.
• In SQL, the programmer may choose to
either allow phantoms in a transaction
or insist they should not occur.
Database Tuning, Spring 2007 31
Exercise (ADBT exam 2005)

Database Tuning, Spring 2007 32

 SQL isolation levels

• A transaction in SQL may be chosen to

have one of four isolation levels:
– READ UNCOMMITTED:
”No locks are obtained.”
– READ COMMITTED:
”Read locks are immediately released -
read values may change during the
transaction.”
– REPEATABLE READ:
”2PL but no lock when adding new tuples.”
– SERIALIZABLE:
”2PL with lock when adding new tuples.”

Database Tuning, Spring 2007 33

 SQL isolation levels

Isolation Level Dirty Unrepeatable Phantoms

Read read

Read uncommitted Maybe Maybe Maybe

Read committed No Maybe Maybe

Repeatable read No No Maybe

Serializable No No No

Database Tuning, Spring 2007 34

 SQL implementation

• Note that implementation is not part of

the SQL standards - they specify only
semantics.
• A DBMS designer may choose another
implementation than the mentioned
locking schemes, as long as the
semantics conforms to the standard.

Database Tuning, Spring 2007 35

 Cursor stability

• Most DBMSs extend the guarantee of

READ COMMITTED with cursor stability:
– “Read locks are held for the duration
of a single SQL statement.”
– Still, values seen may change from
one statement to the next.

Database Tuning, Spring 2007 36

 Snapshot isolation

• Some DBMSs implement snapshot

isolation, an isolation level that gives
a stronger guarantee than READ
COMMITTED.
• Each transaction T executes against
the version of the data items that was
committed “when the T started”.
• Possible implementation:
– No locks for read, locks for writes.
– Store old versions of data (costs
space).

Database Tuning, Spring 2007 37

 Locks and deadlocks

• The DBMS sometimes must make a

transaction wait for another transaction
to release a lock.
• This can lead to deadlock if e.g. A waits
for B, and B waits for A.
• In general, we have a deadlock exactly
when there is a cycle in the waits-for
graph.
• Deadlocks are resolved by aborting
some transaction involved in the cycle.

Database Tuning, Spring 2007 38

 Dealing with deadlocks

• Possibilities:
– Examine the waits-for graph periodically to
find any deadlock.
– If a transaction lived for too long it may be
involved in a deadlock - roll back.
– Use timestamps, unique numbers
associated with every transaction to
prevent deadlocks.
• Deadlocks are less likely if we lock
entire relations - but this decreases
throughput.

Database Tuning, Spring 2007 39

Avoiding deadlocks by timestamp

• Two possible policies when T waits for U:

– Wait-die.
If T is youngest it is rolled back.
– Wound-wait.
If U is youngest it is rolled back.

• In both cases there can be no waits-for

cycles, because transactions only wait
for younger (resp. older) transactions.
• Why always roll back the youngest?

Database Tuning, Spring 2007 40

 Summary of locking

• Locking can prevent transactions from

engaging in non-serializable behaviour.
• However, it is sometimes a bit too strict
and pessimistic, not allowing as much
concurrency as we would like.
• Next we will consider optimistic
concurrency control that works well
when transactions don’t conflict much.

Database Tuning, Spring 2007 41

 Optimistic concurrency control

• Basic idea: Let transactions go ahead,

and only at the end make sure that the
behavior is serializable.
• Several ways of realizing:
– Validation
– Optimistic 2PL (private workspace)
– Timestamping (next)

Database Tuning, Spring 2007 42

 Timestamps

• Idea: Associate a unique number, the

timestamp, with each transaction.
• Transactions should behave as if they
were executed in order of their
timestamps.
• For each database element, record:
• The highest timestamp of a transaction that read
it.
• The highest timestamp of a transaction that
wrote it.
• Whether the writing transaction has committed.

Database Tuning, Spring 2007 43

 Timestamp based scheduling

• If transaction T requests to:

– Read a DB element written by an
uncommitted transaction, it must wait for it
to commit or abort.
– Read a DB element with a higher write
timestamp, T must be rolled back.
– Write a DB element with a higher read
timestamp, T must be rolled back.

• Rolling back means undoing all actions,

getting a new timestamp, and
restarting.

Database Tuning, Spring 2007 44

 Problem session

• What should the scheduler do if a

transaction requests to write a DB
element with a higher write timestamp?

Database Tuning, Spring 2007 45

 Multiversion timestamps

• In principle, all previous versions of DB

elements could be saved.
• This would allow any read operation to
be consistent with the timestamp of the
transaction.
• Used in many systems for scheduling
read only transactions. (In practice,
only recent versions are saved.)

Database Tuning, Spring 2007 46

 Optimism vs pessimism

• Pessimistic concurrency is best in high-

conflict situations:
– Smallest number of aborts.
– No wasted processing (if no deadlocks).
• Optimistic concurrency control is best if
conflicts are rare, e.g., if there are
many read-only transactions.
– Highest level of concurrency.
– Time stamp methods used in some
distributed databases.

Database Tuning, Spring 2007 47

 Lock tuning

• SB offers this advice on locking:

– Use special facilities for long reads.
– Eliminate locking when unnecessary.
– Use the weakest isolation guarantee the
application allows.
– Change the database schema only during
”quiet periods” (catalog bottleneck).
– Think about partitioning.
– Select the appropriate granularity of
locking. (Next)
– If possible, chop transactions into smaller
pieces. (Later)
Database Tuning, Spring 2007 48
 Locking in Oracle
• ”Oracle Database always performs necessary locking to
ensure data concurrency, integrity, and statement-level
read consistency. You can override these default locking
mechanisms. For example, you might want to override the
default locking of Oracle Database if:
– You want transaction-level read consistency or "repeatable reads"
- where transactions query a consistent set of data for the duration
of the transaction, knowing that the data has not been changed by
any other transactions. This level of consistency can be achieved
by using explicit locking, read-only transactions, serializable
transactions, or overriding default locking for the system.
– A transaction requires exclusive access to a resource. To proceed
with its statements, the transaction with exclusive access to a
resource does not have to wait for other transactions to complete.”

Database Tuning, Spring 2007 49

 Locking in Oracle, cont.

• Locking a table T:

LOCK TABLE T IN EXCLUSIVE MODE;

• Unlocking all locked tables:

commit;

• Other lock modes are also available.

Database Tuning, Spring 2007 50

 Transaction tuning example
(slide (c) Shasha and Bonnet, 2001)

Simple purchases:
• Purchase item I for price P
– 1. If cash < P then roll back transaction
(constraint)
– 2. Inventory(I) := inventory(I)+P
– 3. Cash := Cash – P
• Two purchase transactions P1 and P2
– P1 has item I for price 50
– P2 has item I for price 75
– Cash is 100

Database Tuning, Spring 2007 51

 Example: Simple Purchases
(slide (c) Shasha and Bonnet, 2001)

• If 1-2-3 as one transaction then one of

P1, P2 rolls back.
• If 1, 2, 3 as three distinct transactions:
– P1 checks that cash > 50. It is.
– P2 checks that cash > 75. It is.
– P1 completes. Cash = 50.
– P2 completes. Cash = - 25.

Database Tuning, Spring 2007 52

 Example: Simple Purchases
(slide (c) Shasha and Bonnet, 2001)

• Orthodox solution
– Make whole program a single transaction
• Cash becomes a bottleneck!
• Chopping solution
– Find a way to rearrange and then chop up
the transactions without violating
serializable isolation level.

Database Tuning, Spring 2007 53

 Example: Simple Purchases
(slide (c) Shasha and Bonnet, 2001)

• Chopping solution:
– 1. If Cash < P then roll back.
Cash := Cash – P.
– 2. Inventory(I) := inventory(I) + P
• Chopping execution:
– P11: 100 > 50. Cash := 50.
– P21: 75 > 50. Rollback.
– P12: inventory := inventory + 50.

Database Tuning, Spring 2007 54

 Transaction Chopping
(slide (c) Shasha and Bonnet, 2001)

• Execution rules:
– When pieces execute, they follow the
partial order defined by the transactions.
– If a piece is aborted because of a conflict, it
will be resubmitted until it commits
– If a piece is aborted because of an abort,
no other pieces for that transaction will
execute.

Database Tuning, Spring 2007 55

 Transaction Chopping
(slide (c) Shasha and Bonnet, 2001)

• Let T1, T2, …, Tn be a set of

transactions. A chopping partitions
each Ti into pieces ci1, ci2, …, cik.
• A chopping of T is rollback-safe if
– (a) T does not contain any abort commands
or
– (b) if the abort commands are in the first
piece.

Database Tuning, Spring 2007 56

 Summary

• Concurrency control is crucial in a

DBMS.
• Handling CC problems requires an
understanding of the involved
mechanisms.
• Mostly, the schedule of operations of
transactions should be serializable.
• The scheduler may use locks or
timestamps.
– Locks allow less concurrency, and may
cause deadlocks.
– Timestamps may cause more aborts.

Database Tuning, Spring 2007 57

 Exercise

ADBT exam 2006, problem 4

Database Tuning, Spring 2007 58