Query Processing, Optimization, and Transaction Processing

Syllabus tag: Paper-II, Section-B, Topics IV.9–IV.11 — Query Processing & Evaluation · Query Optimization · Transaction Processing

This page covers three separate syllabus subtopics; each has its own heading below so nothing is merged away.

A. Query Processing & Evaluation

Definition

Query processing is the sequence of steps a DBMS takes to transform a high-level query (SQL) into an efficient low-level execution strategy and produce the result.

Steps

1. Parsing & Translation: check syntax/semantics, translate SQL into an internal representation (a relational algebra expression / query tree)
2. Optimization: generate alternative equivalent execution plans and choose the (estimated) cheapest one — see Section B
3. Evaluation: the query-evaluation engine executes the chosen plan and produces the result

Query Evaluation Plan

• An evaluation plan annotates each operator in the query tree with the specific algorithm to use (e.g., which join algorithm, which index) and the order of execution — different plans for the same query can have vastly different costs.
• Evaluated using the iterator model: each operator supports open(), next(), close(), allowing results to be pipelined between operators without materializing every intermediate result to disk.

B. Query Optimization

Definition

Query optimization is the process of choosing, among all logically equivalent execution plans for a query, the one with the lowest estimated cost (I/O, CPU, memory).

Heuristic (Rule-Based) Optimization

Apply transformation rules to the query tree before cost estimation, to shrink intermediate results early:

• Push Selection (σ) operations down the tree as early as possible (filter rows before joining)
• Push Projection (π) operations down as early as possible (drop unneeded columns early)
• Combine a Selection and a Cartesian Product into a Join where possible
• Choose the join order that produces the smallest intermediate relations first

Cost-Based Optimization & Join Algorithms

Numerical — Nested-Loop Join I/O Cost

Given relations R (1,000 blocks) and S (200 blocks), simple nested-loop join, R as outer:

• Cost = b_R + (b_R × b_S) block transfers = 1000 + (1000 × 200) = 201,000 block accesses
• If S (smaller relation) is used as the outer relation instead: 200 + (200 × 1000) = 200,200 block accesses — cheaper, illustrating why the optimizer picks the smaller relation as the outer loop.
• If enough memory exists to hold all of S in memory (block nested-loop with S fully buffered): cost drops to b_R + b_S = 1000 + 200 = 1,200 block accesses — a dramatic reduction, showing why memory-aware plans matter.

C. Transaction Processing

Definition

A transaction is a logical unit of database work — a sequence of one or more operations (reads/writes) that must execute as an indivisible whole.

ACID Properties

• Atomicity: all-or-nothing — either every operation in the transaction commits, or none do (rolled back on failure)
• Consistency: a transaction moves the database from one valid (constraint-satisfying) state to another
• Isolation: concurrently executing transactions must not interfere with each other's intermediate (uncommitted) state
• Durability: once a transaction commits, its effects survive any subsequent system failure (via logs/checkpoints)

Schedules & Serializability

• A schedule is the chronological order in which operations from multiple transactions execute.
• Serial schedule: transactions execute one completely after another (no interleaving) — always consistent, but no concurrency.
• Non-serial (interleaved) schedule: operations from different transactions interleave — needed for performance, but risks conflicts.
• Conflict-serializable schedule: a non-serial schedule that can be transformed into some serial schedule by swapping non-conflicting adjacent operations — the practical target for concurrency control.

Concurrency Control Techniques

• Lock-Based (Two-Phase Locking, 2PL): every transaction has a growing phase (acquires locks, never releases) followed by a shrinking phase (releases locks, never acquires) — guarantees conflict-serializability.
  • Strict 2PL: all locks held until COMMIT/ROLLBACK (not just until the shrinking phase starts) — prevents cascading rollbacks; the variant almost universally used in practice.
• Timestamp Ordering: each transaction gets a unique timestamp at start; conflicting operations are ordered by timestamp rather than by locks — no waiting, but may cause more rollbacks.
• Optimistic (Validation-Based) Concurrency Control: transactions execute freely and are validated only at commit time — efficient when conflicts are rare (read-heavy workloads).

Deadlock

• A deadlock occurs when two or more transactions each hold a lock the other needs, and each waits indefinitely for the other.
• Prevention: Wait-Die and Wound-Wait schemes (using transaction timestamps to decide who waits vs who is aborted)
• Detection: build a wait-for graph; a cycle indicates deadlock — one transaction is chosen as the victim and rolled back

Recovery

• Log-based recovery: every update is first written to a log (write-ahead logging, WAL) before the actual database page — allows REDO (reapply committed changes) and UNDO (reverse uncommitted changes) after a crash
• Checkpoints: periodic snapshots that bound how far back the recovery process must scan the log
• Shadow paging: maintains two page tables (current + shadow); commit atomically switches the shadow table to become current — avoids the need for UNDO logging, but complicates concurrent transactions

MCQ Trap

• ACID = Atomicity, Consistency, Isolation, Durability — a very common MCQ fill-in.
• Strict 2PL is what's used in real systems, not plain 2PL — plain 2PL guarantees serializability but not recoverability (can still need cascading rollback).
• On system shutdown before COMMIT, the DBMS automatically rolls back (UNDOes) the incomplete transaction on recovery — this exact scenario appeared as an FPSC 2025 MCQ.

CSS Exam Angle

• High-yield across nearly every year (2016, 2020, 2023, 2024): ACID properties and 2PL concurrency control are near-guaranteed short questions.
• FPSC 2024 explicitly asked to "discuss potential pitfalls and optimizations related to complex SQL queries" — connect SQL-writing questions to this optimization section (join order, index usage) rather than treating them as unrelated topics.

Likely Questions

1. Explain the ACID properties of a transaction with a real-world example.
2. Explain Two-Phase Locking (2PL) as a concurrency control mechanism; distinguish it from Strict 2PL.
3. What is a conflict-serializable schedule? Why does the DBMS care about serializability?
4. Explain the steps of query processing from SQL text to result.
5. Compare nested-loop, sort-merge, and hash join algorithms by when each is preferable.
6. Given block counts for two relations, compute the I/O cost of a nested-loop join under different outer-relation choices.
7. Explain deadlock detection using a wait-for graph, and contrast it with deadlock prevention (Wait-Die/Wound-Wait).
8. Differentiate log-based recovery and shadow paging.

---

📘 Enrichment — Worked Examples for All Three Sections

A+. Query Processing Pipeline

flowchart LR
    Q["SQL query"] --> P["Parser & Translator"]
    P --> RA["Relational algebra / query tree"]
    RA --> O["Optimizer"]
    CAT[("Catalog statistics")] --> O
    O --> EP["Execution plan"]
    EP --> E["Evaluation engine"]
    DATA[("Data + indexes")] --> E
    E --> R["Result"]

A+. Cost of a Selection (numerical)

Employee: 10,000 records in 1,000 blocks; condition EmpId = 5000.

• Linear scan: 1,000 block accesses worst case (500 average for a key).
• Binary search on a file sorted by EmpId: ⌈log₂ 1000⌉ = 10.
• B+-tree index of height 3: 3 + 1 = 4 block accesses.
• For a non-key condition (DeptId = 10, 500 matching rows) a secondary index may cost up to 500 extra accesses — the optimizer may then prefer a full scan. This is why "use an index" is not always the right answer.

B+. Heuristic Optimization — Worked Query Tree

SELECT E.Name
FROM Employee E, Department D
WHERE E.DeptId = D.DeptId AND D.Location = 'Lahore';

Assume Employee = 10,000 rows, Department = 50 rows (5 in Lahore), ~200 employees per department.

• Canonical (naive) tree: π Name ( σ E.DeptId = D.DeptId ∧ Location='Lahore' ( Employee × Department ) ) → the Cartesian product materialises 10,000 × 50 = 500,000 tuples.
• Step 1 — push selection down: σ Location='Lahore' (Department) → only 5 rows.
• Step 2 — replace σ + × by a join: Employee ⋈ (5 Lahore departments) → about 1,000 rows.
• Step 3 — push projection down: carry only DeptId and Name into the join.
• Optimized: π Name ( π DeptId, Name (Employee) ⋈ π DeptId ( σ Location='Lahore' (Department) ) ) — intermediate result shrinks from 500,000 to about 1,000 tuples (≈ 500× less work).

flowchart BT
    E["Employee"] --> PE["π DeptId, Name"]
    D["Department"] --> SD["σ Location='Lahore'"]
    SD --> PD["π DeptId"]
    PE --> J["⋈ DeptId"]
    PD --> J
    J --> P["π Name"]

B+. Equivalence Rules Used by Optimizers (memorise 5)

1. Cascade of σ: σ c1 ∧ c2 (R) = σ c1 (σ c2 (R))
2. Commutativity of σ: order of selections does not matter.
3. σ distributes over ⋈ when the condition involves only one relation's attributes (push-down).
4. Joins are commutative and associative → join reordering (smallest intermediate first).
5. π can be pushed below ⋈ if the join attributes are kept.

C+. Why Concurrency Control Is Needed — The Four Problems

C+. SQL Isolation Levels

C+. Transaction States

stateDiagram-v2
    [*] --> Active
    Active --> PartiallyCommitted: last statement executed
    Active --> Failed: error / abort
    PartiallyCommitted --> Committed: log forced to disk
    PartiallyCommitted --> Failed: failure before commit
    Failed --> Aborted: rollback done
    Committed --> [*]
    Aborted --> [*]

C+. Numerical — Testing Conflict Serializability with a Precedence Graph

Conflicting operations: two operations from different transactions on the same item where at least one is a write (R-W, W-R, W-W).

Schedule S1: r1(X), r2(X), w1(X), w2(X)

• r1(X) before w2(X) → edge T1 → T2
• r2(X) before w1(X) → edge T2 → T1
• Cycle T1 ⇄ T2 → not conflict-serializable (this is exactly the lost-update pattern).

Schedule S2: r1(A), w1(A), r2(A), w2(A), r1(B), w1(B), r2(B), w2(B)

• All conflicts on A and on B go T1 before T2 → only edge T1 → T2
• No cycle → conflict-serializable, equivalent to serial order T1, T2 (topological sort of the graph).

Schedule S3 (three transactions): r1(X), r2(Y), w3(X), r2(X), w1(Y)

• r1(X) before w3(X) → T1 → T3
• w3(X) before r2(X) → T3 → T2
• r2(Y) before w1(Y) → T2 → T1
• Cycle T1 → T3 → T2 → T1 → not serializable.

C+. 2PL Illustrated

T1: lock-X(A)  read(A)  A=A-100  write(A)  lock-X(B)  |  unlock(A)  read(B) B=B+100 write(B) unlock(B)
    <----------------- growing phase ----------------> | <----------- shrinking phase ------------>
                                                  lock point

• Lock compatibility: Shared (S) is compatible with S; Exclusive (X) is compatible with nothing.
• Basic 2PL: releasing A early (as above) lets T2 read A before T1 commits → if T1 aborts, T2 must also abort (cascading rollback).
• Strict 2PL: hold all X locks until COMMIT → no cascading rollbacks. Rigorous 2PL: hold all locks (S and X) until commit.
• 2PL does not prevent deadlock.

C+. Deadlock Example with Wait-for Graph

• T1 locks A, T2 locks B; T1 requests B (waits for T2); T2 requests A (waits for T1) → wait-for graph T1 → T2 → T1 → cycle → deadlock → abort the younger/cheaper transaction.
• Wait-Die (non-preemptive): older requester waits; younger requester dies (restarts with same timestamp).
• Wound-Wait (preemptive): older requester wounds (aborts) the younger holder; younger requester waits.

C+. Numerical — Log-Based Recovery After a Crash

<T1 start>
<T1, A, 1000, 950>
<T2 start>
<T1, B, 2000, 2050>
<T1 commit>
<T2, C, 700, 600>
<T3 start>
<T3, D, 500, 400>
--- CRASH ---

(Log record format: transaction, item, old value, new value.)

• Immediate update scheme: T1 has start + commit → REDO T1 (A = 950, B = 2050). T2 and T3 have no commit → UNDO in reverse order: D = 500, C = 700.
• Deferred update scheme: uncommitted changes never reached the database → only REDO T1; T2, T3 simply ignored (no UNDO needed).
• Checkpoint twist: if a <checkpoint> record had been written after <T1 commit>, T1's changes would already be on disk → no REDO needed for T1; recovery only scans back to the last checkpoint.
• Write-Ahead Logging rule: the log record must reach stable storage before the data page it describes, and all log records of a transaction before its commit.

---

✍️ Model Answers — Likely Questions

Q1. Explain the ACID properties with a real-world example.

Example: transfer Rs 5,000 from Ali's account to Sara's via Raast/online banking: T = read(Ali); Ali −= 5000; write(Ali); read(Sara); Sara += 5000; write(Sara).

• Atomicity — if the system fails after debiting Ali, the debit is undone (log-based UNDO). Responsible: recovery manager.
• Consistency — the total Ali + Sara is the same before and after; constraints like balance ≥ 0 hold. Responsible: programmer + integrity constraints.
• Isolation — a concurrent balance enquiry never sees money "in flight". Responsible: concurrency control (Strict 2PL).
• Durability — once the app shows "successful", the transfer survives a power failure. Responsible: recovery manager (WAL, forced log).

Conclusion: ACID is what makes a DBMS trustworthy for banking, NADRA records and e-commerce; NoSQL systems often relax it (BASE) for scale.

Q2. Explain Two-Phase Locking; distinguish it from Strict 2PL.

2PL: each transaction acquires all locks in a growing phase and releases in a shrinking phase; after its first unlock it can never lock again. The point of the last lock is the lock point; ordering transactions by lock point gives an equivalent serial schedule → guarantees conflict serializability.

Problems of basic 2PL: cascading rollbacks (other transactions read data released before commit) and deadlocks.

Strict 2PL: holds exclusive locks until commit/abort → schedules are also strict/recoverable, no cascading rollback. Rigorous 2PL: holds all locks until commit → serial order = commit order.

Draw the growing/shrinking diagram above and conclude that commercial DBMSs use Strict 2PL (plus MVCC for reads).

Q3. What is a conflict-serializable schedule and why does it matter?

A schedule is conflict-serializable if it can be transformed into a serial schedule by swapping adjacent non-conflicting operations — equivalently, its precedence graph is acyclic.

It matters because serial execution is always correct but slow; serializability lets the DBMS interleave for performance while guaranteeing the same result as some serial order.

Demonstrate with S1 (cycle → not serializable) and S2 (acyclic → equivalent to T1, T2) above.

Q4. Explain the steps of query processing.

1. Parsing & translation: syntax check, validate names against the catalog, produce a relational-algebra query tree.
2. Optimization: apply equivalence rules (push σ and π down, reorder joins) and cost estimates from catalog statistics (row counts, index availability, selectivity) to choose the cheapest plan.
3. Evaluation: the engine executes the plan using chosen algorithms (index scan, hash join), pipelining results where possible.

Include the pipeline diagram and the Lahore-employees worked optimization (500,000 → 1,000 intermediate tuples).

Q5. Compare nested-loop, sort-merge and hash joins.

Use the join-algorithm table in the notes and give costs for R (1,000 blocks) and S (200 blocks): nested-loop 200,200 (S outer); block nested-loop with S fully in memory 1,200; sort-merge ≈ sorting cost + 1,200 (cheap if already sorted); hash join ≈ 3 × (1,000 + 200) = 3,600 with partitioning (1,200 if S fits in memory). Conclude: hash join for large unsorted equijoins, sort-merge when inputs are sorted or output must be sorted, index nested-loop when the inner relation has an index on the join key.

Q6. Compute nested-loop join I/O cost for different outer relations.

Formula: cost = b_outer + (n_outer × b_inner) for tuple-at-a-time, or b_outer + (b_outer × b_inner) for block-at-a-time.

Block-at-a-time with R = 1,000 and S = 200 blocks: R outer = 1,000 + 1,000 × 200 = 201,000; S outer = 200 + 200 × 1,000 = 200,200 → choose the smaller relation as outer. With S fully buffered in memory: 1,000 + 200 = 1,200.

Q7. Explain deadlock detection with a wait-for graph; contrast with prevention.

Detection: nodes = transactions, edge Ti → Tj when Ti waits for a lock held by Tj; the system periodically searches for cycles; on a cycle it picks a victim (least work done, fewest locks, youngest) and rolls it back, avoiding starvation by limiting repeated selection.

Prevention: ensure a cycle can never form — Wait-Die and Wound-Wait using timestamps (older transactions get priority), or acquire all locks up front, or lock items in a fixed order.

Timeout: abort any transaction waiting longer than a limit — simple but imprecise.

Trade-off: detection allows more concurrency but costs graph maintenance; prevention may abort transactions unnecessarily.

Q8. Differentiate log-based recovery and shadow paging.

Illustrate with the crash log numerical above.

---

⚡ 60-Second Revision

• Query processing: Parse → Optimize → Evaluate. Push σ and π down; smallest relation as outer.
• ACID: Atomicity & Durability → recovery manager; Isolation → concurrency control; Consistency → constraints + programmer.
• Conflict = same item, different transactions, at least one write. Acyclic precedence graph ⇒ serializable.
• 2PL ⇒ serializable, not deadlock-free. Strict 2PL ⇒ no cascading rollback.
• Recovery: REDO committed, UNDO uncommitted; WAL before data.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2016 · Paper-II · Q6(a) and 2023 · Paper-II · Q6(b) · 8 and 4 marks

Q. A transaction is a unit of program execution that accesses and possibly updates data items. Explain the ACID properties of transaction processing.

Ans.

• Atomicity ("all or nothing"): either all operations of the transaction are done or none are. If it fails midway, all its changes are rolled back (recovery manager, logs). Example: a transfer that debits account A must also credit B, or neither happens.
• Consistency: a transaction takes the database from one valid state to another, preserving all rules (constraints, balances). Example: the total money before and after a transfer is the same.
• Isolation: concurrent transactions do not see each other's partial results, as if they ran one at a time (concurrency control such as locking).
• Durability: once committed, the changes survive crashes and power failures (write-ahead log, stable storage).

2020 · Paper-II · Q6(c) · 5 marks

Q. Explain Two-Phase Locking (2PL) as a concurrency control mechanism in database systems.

Ans.

• 2PL guarantees serialisable schedules by dividing each transaction into two phases:
  • Growing phase: the transaction may acquire locks (shared for reading, exclusive for writing) but cannot release any.
  • Shrinking phase: once it releases its first lock, it may only release locks and cannot acquire new ones.
• The lock point (when the last lock is obtained) gives the serial order of transactions.
• Variants: strict 2PL (hold exclusive locks until commit, which also avoids cascading rollbacks) and rigorous 2PL (hold all locks until commit).
• Drawbacks: can cause deadlocks (handled by timeouts or detection) and reduces concurrency.

MCQs

2025 P-II · Q10. In case of any shutdown during a transaction before commit, which of the following is done automatically?

• (A) View
• (B) Commit
• (C) Rollback ✅
• (D) Flashback
• Answer: (C) Rollback.
• Why: atomicity says an incomplete transaction must leave no effect. On restart the DBMS uses the log to undo (roll back) its uncommitted changes. It does not commit, because the user never issued the commit.