Read phenomena (dirty reads, phantom reads) in SQL - Time & Space Complexity

Time Complexity: Read phenomena (dirty reads, phantom reads)

O(n)

Understanding Time Complexity

When databases read data during transactions, the way they handle changes affects how long queries take.

We want to understand how reading data that might be changing impacts the work done by the database.

Scenario Under Consideration

Analyze the time complexity of this transaction reading data with possible dirty or phantom reads.

BEGIN TRANSACTION;
SELECT * FROM Orders WHERE CustomerID = 123;
-- Another transaction may insert or update Orders here
SELECT COUNT(*) FROM Orders WHERE CustomerID = 123;
COMMIT;
    

This code reads orders for a customer, but other changes might happen during the transaction causing dirty or phantom reads.

Identify Repeating Operations

Look for repeated work that affects time.

• Primary operation: Scanning or searching the Orders table for matching CustomerID rows.
• How many times: Twice in this example, once for the SELECT * and once for the COUNT(*).

How Execution Grows With Input

As the number of orders grows, the database must check more rows each time it reads.

Input Size (n)	Approx. Operations
10	About 20 row checks (2 reads x 10 rows)
100	About 200 row checks
1000	About 2000 row checks

Pattern observation: The work roughly doubles with the number of rows because the query runs twice, each scanning the data.

Final Time Complexity

Time Complexity: O(n)

This means the time to read grows directly with the number of rows matching the query.

Common Mistake

[X] Wrong: "Reading data during a transaction always takes the same time regardless of data changes."

[OK] Correct: If other transactions add or change rows, the database may do extra work to handle these reads, making the time grow with data size and changes.

Interview Connect

Understanding how reading data during transactions affects performance shows you know how databases handle real-world data changes.

Self-Check

"What if we added an index on CustomerID? How would that change the time complexity of these reads?"

Practice

1. Which of the following best describes a dirty read in database transactions?

easy

A. Reading data that has been modified but not yet committed by another transaction.

B. Seeing new rows appear in a query result after re-running the same query.

C. Reading only committed data and never uncommitted changes.

D. Locking rows to prevent other transactions from reading them.

Solution

1. Step 1: Understand dirty read definition

   A dirty read happens when a transaction reads data that another transaction has changed but not committed yet.

2. Step 2: Compare options to definition

   Reading data that has been modified but not yet committed by another transaction. matches this exactly. Seeing new rows appear in a query result after re-running the same query. describes phantom reads, C describes a safe read, and D is about locking, not dirty reads.

3. Final Answer:

   Reading data that has been modified but not yet committed by another transaction. -> Option A

4. Quick Check:

   Dirty read = reading uncommitted data [OK]

Hint: Dirty read = reading uncommitted changes [OK]

Common Mistakes:

• Confusing dirty read with phantom read
• Thinking dirty read only reads committed data
• Mixing locking with read phenomena

2. Which SQL transaction isolation level allows dirty reads?

easy

A. SERIALIZABLE

B. REPEATABLE READ

C. READ COMMITTED

D. READ UNCOMMITTED

Solution

1. Step 1: Recall isolation levels and dirty reads

   Only the READ UNCOMMITTED isolation level allows dirty reads, meaning it can read uncommitted changes.

2. Step 2: Match options to isolation levels

   READ COMMITTED and higher levels prevent dirty reads. SERIALIZABLE is the strictest. So, READ UNCOMMITTED is correct.

3. Final Answer:

   READ UNCOMMITTED -> Option D

4. Quick Check:

   Dirty reads allowed only in READ UNCOMMITTED [OK]

Hint: Dirty reads only happen at READ UNCOMMITTED level [OK]

Common Mistakes:

• Choosing READ COMMITTED as allowing dirty reads
• Confusing phantom reads with dirty reads
• Not knowing isolation level hierarchy

3. Consider two transactions running concurrently on a table Orders. Transaction 1 reads all rows where status = 'pending'. Transaction 2 inserts a new row with status = 'pending' and commits. If Transaction 1 repeats the read, what phenomenon might it observe?

medium

A. Dirty read

B. Non-repeatable read

C. Phantom read

D. Lost update

Solution

1. Step 1: Analyze the scenario with inserted rows

   Transaction 1 reads rows with status 'pending'. Transaction 2 inserts a new 'pending' row and commits.

2. Step 2: Identify the phenomenon on repeated read

   When Transaction 1 reads again, it sees the new row that wasn't there before. This is a phantom read, where new rows appear between reads.

3. Final Answer:

   Phantom read -> Option C

4. Quick Check:

   New rows appearing = Phantom read [OK]

Hint: New rows between reads = phantom read [OK]

Common Mistakes:

• Confusing phantom read with dirty read
• Thinking non-repeatable read applies to new rows
• Mixing lost update with read phenomena

4. A developer wrote this SQL transaction code but observes inconsistent reads. Identify the error related to read phenomena:

BEGIN TRANSACTION;
SELECT * FROM Products WHERE price > 100;
-- Another transaction inserts a new product with price 150 and commits
SELECT * FROM Products WHERE price > 100;
COMMIT;

What is the likely cause?

medium

A. Using READ UNCOMMITTED isolation level causing dirty reads

B. Using READ COMMITTED isolation level causing phantom reads

C. Using SERIALIZABLE isolation level causing lost updates

D. Using REPEATABLE READ isolation level causing non-repeatable reads

Solution

1. Step 1: Understand the scenario with repeated SELECTs

   The transaction reads products with price > 100 twice. Between reads, another transaction inserts a new matching row and commits.

2. Step 2: Identify the read phenomenon

   Because the isolation level is likely READ COMMITTED, the second read sees the new row, causing a phantom read.

3. Final Answer:

   Using READ COMMITTED isolation level causing phantom reads -> Option B

4. Quick Check:

   Phantom reads occur at READ COMMITTED [OK]

Hint: Phantom reads happen at READ COMMITTED level [OK]

Common Mistakes:

• Assuming dirty reads cause this behavior
• Confusing lost updates with read phenomena
• Thinking REPEATABLE READ allows phantom reads

5. You want to prevent both dirty reads and phantom reads in your application. Which transaction isolation level should you choose?

hard

A. SERIALIZABLE

B. READ COMMITTED

C. REPEATABLE READ

D. READ UNCOMMITTED

Solution

1. Step 1: Review isolation levels and phenomena prevented

   READ UNCOMMITTED allows dirty reads. READ COMMITTED prevents dirty reads but allows phantom reads. REPEATABLE READ prevents dirty and non-repeatable reads but may allow phantom reads.

2. Step 2: Identify level preventing both dirty and phantom reads

   SERIALIZABLE is the strictest level and prevents dirty reads, non-repeatable reads, and phantom reads by fully isolating transactions.

3. Final Answer:

   SERIALIZABLE -> Option A

4. Quick Check:

   SERIALIZABLE prevents dirty and phantom reads [OK]

Hint: Use SERIALIZABLE to prevent dirty and phantom reads [OK]

Common Mistakes:

• Choosing REPEATABLE READ thinking it blocks phantom reads
• Confusing READ COMMITTED with preventing all read anomalies
• Ignoring performance impact of SERIALIZABLE