Transaction Scheduling & Reordering Rules

Two simple rules unlock significant performance gains while maintaining correctness.

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

The Correctness Challenge: Isolation for ACID

TM's Guarantee

Transactions are Isolated from each other

They never see partial changes from other transactions—ensuring correctness. Each transaction operates as if it's the only task in the database.

Key Definitions

Serial Schedule

Transactions execute completely one after another with no overlap

Example: T₁ finishes entirely before T₂ begins (or vice versa)

Interleaved Schedule

The TM interleaves operations from different transactions

Example: Operations are executed in a different order.

The Performance vs Safety Trade-off

The Central Challenge

Maximum Safety

Serial execution: One transaction at a time

  • Perfect correctness
  • Easy to understand
  • Terrible performance

The Sweet Spot

Maximum Performance

No coordination: Zero isolation

  • Maximum parallelism
  • Race conditions
  • Data corruption

The Solution

Smart concurrency control following Rules 1 and 2 below lets us approach maximum performance while maintaining safety guarantees.

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

Serial vs Interleaved: Banking Examples

Let's see serial and interleaved schedules in action:

Scenario: Two things happen at month-end:

Banking transaction schedules showing serial and interleaved execution

Understanding the Three Schedules

The image demonstrates the difference between serial and interleaved execution:

Key Insight: S1 and S2 are both correct (though different). S6 is incorrect because it doesn't match ANY serial schedule—it violates isolation!

The Bridge to Concurrency Control

Why We Need Locking Mechanisms

Connecting the Dots

1

Rule 1 creates opportunity

Transaction-level reordering enables massive parallelism

→
2

Rule 2 creates challenge

Must carefully control R/W operation ordering

→
3

Solution: Concurrency Control

Locks, timestamps, and isolation protocols