Year: 1987

Authors: R Agrawal, MJ Carey, M Livny

Note: I referenced the morning paper’s post for this topic.


There are many performance studies each showing advantages of their system. How could this be? The primary controversy was over which one of blocking, immediate-restart, optimistic was better. The authors provide a framework for when which option is better. It could be viewed as a taxonomy of assumptions made for each system.

Summary of Concurrency Control Paradigms

For blocking and immediate restart, “Transactions set read locks on objects that they read, and these locks are later upgraded to write locks for objects that they also write.” They differ when lock requests are denied

  • Blocking: the requesting transaction is blocked.
  • Immediate-restart (IR): obtain read lock then write lock, but if lock request is denied then abort, try again after some amount of time to allow for the competing transaction to complete.
  • Optimistic (OCC): execute unhindered until commit point, when they are validated, if the read of the transaction has now changed and the change is committed, abort transaction and restart.

Performance Model

  • Database system model: CPU, disk, granularity, concurrency control alg
  • User model: nature of the transaction: batch or interactive
  • Transaction model: number of objects that it reads and writes

There is a lot to keep track of, and the smart thing the authors here did is to simplify the model to (1) size of relation (2) number of transactions allowed to happen (multiprogramming level) (3) blocking ratio: average number of times that a transaction has to block per commit (3) restart ratio: # of times restart needed before commit.

Taxonomy of Assumptions and Impact on Paradigm

  • Infinite resource: this would affect OCC and IR more because they use up resource. As seen in Fig 8 — because immediate restart has a delay time so when contention is really high IR actually does best.
  • Restarted transactions are replaced by independent transaction: I think that this never happens in real life, but it makes the analysis more tractable. As shown in Fig 31, with infinite resources fake restarts almost make no difference on OCC (because the situation is gurarnteed to be different since the conflicting transaction has already committed and is visible, so the restart being modeled as the same or different makes no real difference), whereas for blocking and immediate-restart the real restarts would have a lower throughput due to contention.
  • Lock upgrades: most systems do lock upgrade from reader to writer lock, but what happens if this is not the case? In general when resource is constrained having upgrades is better mostly because lock updates reduces deadlocks and less aborts.


It all depends!!

  • if utilizations are sufficiently low, a restart-oriented algorithm becomes a better choice.