Timestamp Ordering and MVCC: Concurrency Control Techniques in Databases

What is Timestamp Ordering (TO) Concurrency Control?

A protocol where each transaction is given a unique timestamp, and all reads/writes must follow the timestamp order.

Intuition: Transactions behave as if they run in the order they started.

Example: T1 has TS=5, T2 has TS=10 → all operations of T1 must logically precede T2's.

Why it matters: Guarantees serializability without locks — heavily tested.

What metadata does each data item maintain in TO?

Each item X keeps RTS(X) = largest timestamp of any transaction that read X and WTS(X) = largest timestamp of any transaction that wrote X.

Intuition: A timestamp "history" describing who touched this data last.

Example: After T5 reads X → RTS(X)=5.

Why it matters: Used in read/write validation; exam will give numerical timestamp problems.

When does a READ cause abort in TO?

T reading X aborts if TS(T) < WTS(X)

Intuition: T is "too old" — someone newer overwrote the value already.

Example: WTS(X)=20; T has TS=5 → T must abort.

Why it matters: Most common timestamp-ordering exam question.

When does a WRITE cause abort in TO?

T writing X aborts if TS(T) < RTS(X) OR TS(T) < WTS(X)

Intuition: T can't overwrite or "go back in time" relative to earlier operations.

Example: If a newer transaction already read X, T cannot write it.

Why it matters: Write validation is ALWAYS tested.

Why does timestamp ordering avoid deadlocks?

Because TO never waits — transactions abort instead of blocking

Intuition: "No waiting, no circles, no deadlocks."

Example: If T tries to write too late → abort and restart.

Why it matters: You must contrast TO vs 2PL on the exam.

What is MVCC (Multiversion Concurrency Control)?

Each write creates a new version of a data item; reads choose from existing versions

Intuition: Like Google Docs version history — everyone reads a version appropriate to them.

Example: X has versions: X1 (old), X2 (new). Older transactions read X1.

Why it matters: MVCC is used in PostgreSQL; heavily tested because reads never block.

How does a transaction choose a version in MVCC?

A transaction T with timestamp TS(T) reads the version with WTS ≤ TS(T) and largest possible WTS

Intuition: Read "the newest version that existed when you started."

Example: Versions at WTS 5, 8, 12; T's TS=9 → read version 8.

Why it matters: Timestamp-based version selection appears in exam problems.

Why do reads never block in MVCC?

Because each read selects an appropriate old version instead of waiting for writers.

Intuition: Readers don't wait on writers; they read older snapshots.

Example: T1 is writing X; T2 still reads X's previous version.

Why it matters: Shows MVCC advantage vs locking — common exam concept.

What problem does MVCC need to solve?

Garbage collecting obsolete versions that no active transaction can read.

Intuition: Old versions pile up over time.

Example: No transaction with TS<50 → delete versions older than WTS=50.

Why it matters: Exam may ask about overhead or cleanup.

What is Optimistic Concurrency Control (OCC)?

Transactions run without locks; at commit time, the system checks for conflicts.

Intuition: "Assume everything will be fine — check only at the end."

Example: T maintains readSet and writeSet → validation happens before commit.

Why it matters: OCC is great for low-conflict workloads; exam tests commit-time validation.

What are the 3 phases of OCC?

Read Phase: read data, compute locally; Validation Phase: check for conflicts; Write Phase: apply updates to DB.

Intuition: "Do work → check → publish."

Example: T reads R, writes changes to local buffer, validates, then commits.

Why it matters: Direct exam question: "List the phases of optimistic CC."

When does a transaction fail validation in OCC?

If its readSet overlaps with the writeSet of any committed or concurrently validating transaction

Intuition: "If someone else changed what you read, your work is invalid."

Example: T2 writes X; T1 read X → T1 fails validation.

Why it matters: OCC validation rules often appear in written problems.

Why is OCC good for low contention workloads?

Few writes → few conflicts → validation rarely fails.

Intuition: If nobody updates the same data, checking at commit is cheap.

Example: Analytics queries mostly reading.

Why it matters: Exam asks: "When to use OCC?"

Why is OCC bad for high contention workloads?

Many transactions access the same data → many validation failures → many aborts.

Intuition: Too much competition → wasteful restarts.

Example: Heavy updates to same bank account.

Why it matters: Contrast OCC vs 2PL, timestamp ordering.

What is the difference between MVCC and OCC?

MVCC creates multiple versions; OCC does optimistic validation at commit.

Intuition: MVCC: "Readers read old versions." OCC: "Everyone works freely, checked at the end."

Example: MVCC supports snapshot isolation; OCC does not.

Why it matters: Exam loves comparing concurrency methods.

Why does TO guarantee serializability?

Because transactions act as if processed in increasing timestamp order.

Intuition: They are forced to obey time.

Example: If T1 is older than T2, any attempt by T2 to read/write first aborts.

Why it matters: Proof reasoning for concurrency.

What is the biggest disadvantage of timestamp ordering?

You may get many aborts if old transactions try to access items rewritten by newer ones.

Intuition: Older transactions are fragile.

Example: Long-running T1 gets aborted many times.

Why it matters: Exam asks: When does TO fail?

What is the phantom anomaly in MVCC?

MVCC does NOT prevent phantoms unless predicate locking or SERIALIZABLE isolation is used.

Intuition: New rows matching a query may appear.

Example: T1: SELECT * WHERE age < 20 T2 inserts a new row age=18.

Why it matters: MVCC ≠ full serializability; exam trap question.

What is the key difference between Timestamp Ordering and 2PL?

TO aborts conflicting transactions; 2PL waits.

Intuition: TO = no waiting; 2PL = possible deadlocks.

Example: Write-write conflict: TO aborts one, 2PL might deadlock.

Why it matters: Exam comparison question.

Why does MVCC improve read performance?

Readers never wait for writers; writers never block readers.

Intuition: Concurrency skyrockets.

Example: Analytical workload with many SELECT queries.

Why it matters: MVCC is widely used in practice; exam concept.