Transaction Scheduling & Reordering Rules

Concept. Transaction scheduling reorders independent operations from concurrent transactions to maximize throughput while preserving serializability. Two operations can swap order if and only if they don't conflict (don't both touch the same row, with at least one being a write).

Intuition. When Mickey's read of Song 42 and Minnie's write of Song 99 are queued back-to-back, the scheduler can swap them. They touch different rows, so the swap is invisible to both transactions and lets Minnie's slow disk write run in parallel with Mickey's quick read.

Here, we'll refer to the Transaction Manager (TM) or Database (DB) as the decision-maker in our data operations.

The Performance vs Safety Trade-off

Maximum Safety

Serial execution: one transaction at a time.

  • Perfect correctness
  • Easy to understand
    − Terrible performance

The Sweet Spot

Smart concurrency control: approach maximum performance while keeping safety guarantees.

How: Rules 1 & 2 (below) let the database interleave transactions safely.

Maximum Performance

No coordination: zero isolation.

  • Maximum parallelism
    − Race conditions
    − Data corruption

Rule 1: DB Does Not Care About Transaction Order

The Rule: Database systems can execute transactions in any order they choose.

Why Rule 1 Exists: Performance!

Key Insight

Databases exploit this reordering flexibility to optimize around IO costs and achieve massive parallelism. If transactions T1 and T2 touch different data, they can run completely in parallel!

Parallel Execution

Run independent transactions simultaneously across multiple CPU cores

IO Optimization

Batch disk operations and minimize expensive random access

Better Throughput

Process thousands of transactions per second instead of hundreds

Developer Control

When You Need Specific Ordering

If your application requires T1 to happen before T2, create a single transaction T42 that includes both T1 and T2 logic in the desired order:

BEGIN TRANSACTION T42
-- T1 logic here
-- T2 logic here  
COMMIT

Rule 2: DB Cares About Order of R/W Actions

The Rule: Within and across transactions, the order of individual read/write operations determines correctness.

Why Rule 2 Matters: Data Integrity

Critical Insight

Databases must ensure that transactions see consistent snapshots of data. No transaction should see the intermediate states of another transaction.

Read Consistency

All reads within a transaction see the same consistent view of the database

Write Isolation

Writes from one transaction are not visible to others until commit

Serializable Result

Final result matches some serial execution order

The Bridge to Concurrency Control

Why We Need Locking Mechanisms

Connecting the Dots

Rule 1 creates opportunity

Transaction-level reordering enables massive parallelism.

→

Rule 2 creates challenge

Must carefully control R/W operation ordering.

→

Solution: Concurrency Control

Locks, timestamps, and isolation protocols.