Query Processing & Optimization: Trees, Plans & Costs

TAKEAWAYS:

• Query processing converts SQL into relational algebra → query trees → execution plans to minimize cost (CPU, I/O, time).
• Heuristic optimization uses rules-of-thumb (e.g., "select early"), while cost-based optimization picks the cheapest plan via statistics.
• The CAP theorem forces trade-offs: CA (eSewa), CP (NEPSE), or AP (Pathao) in distributed databases.
• Query trees (e.g., AND/OR trees) help visualize operator order; execution plans show physical steps (e.g., nested loops vs. hash joins).
• Index selection (B-trees, bitmaps) and partitioning (range/hash) drastically reduce I/O costs.
• Real-world systems (e.g., Khalti’s fraud detection) use cost-based optimization to prioritize low-latency queries.

---

1. Query Processing: From SQL to Execution

1.1 How Queries Are Processed

When you run a SQL query (e.g., SELECT * FROM Orders WHERE customer_id = 101), the database follows these 5 stages:

Key Steps Explained

1. Parsing & Validation

   • Checks syntax (e.g., WHERE without FROM fails).
   • Example: SELECT name FROM Customers WHERE age > 30 → Valid.
   • Invalid: SELECT * FROM (missing table).

2. Query Rewriting

   • Converts SQL to relational algebra (e.g., σ_age>30(π_name(Customers))).
   • Simplifies expressions (e.g., WHERE a > 5 AND a < 10 → WHERE a BETWEEN 5 AND 10).

3. Query Optimization

   • Chooses the fastest execution path (discussed in Section 3).

4. Execution Plan Generation

   • Creates a query tree (logical) → execution plan (physical).
   • Example plan for SELECT * FROM Orders JOIN Customers:

     Seq Scan on Orders (Cost: 10.00)
       → Nested Loop Join (Cost: 100.00)
         → Index Scan on Customers (Cost: 50.00)
     

5. Execution & Result Return

   • Fetches data from disk/buffer, applies joins/filters, and returns rows.

---

1.2 Why Convert SQL to Relational Algebra?

• Formal foundation: Algebra is unambiguous (SQL has dialects).
• Optimization basis: Algebra expressions can be rewritten for efficiency.
• Example: SQL: SELECT name FROM Customers WHERE city = 'Kathmandu' Algebra: π_name(σ_city='Kathmandu'(Customers))

---

2. Query Trees: Visualizing Operator Order

2.1 What Is a Query Tree?

A query tree is a hierarchical representation of operations in a query. It shows:

• Logical operators (e.g., σ, π, ⋈).
• Order of execution (top-down or bottom-up).

Example: For SELECT name FROM Orders JOIN Customers WHERE Orders.customer_id = Customers.id AND Customers.city = 'Kathmandu'

2.2 Why Use Query Trees?

• Optimization: Helps rearrange operations (e.g., push σ down).
• Debugging: Shows why a query is slow (e.g., full table scan before filter).
• Example: In eSewa’s transaction logs, queries like SELECT * FROM Transactions WHERE user_id = X are optimized by moving σ_user_id to the start.

---

3. Query Optimization Techniques

3.1 Heuristic vs. Cost-Based Optimization

Heuristic Rules (Examples)

1. Select Early: Apply WHERE filters before joins.
   • Bad: FROM A JOIN B WHERE A.id = B.id AND A.value > 100
   • Good: FROM A WHERE A.value > 100 JOIN B WHERE A.id = B.id
2. Project Early: Remove columns early to reduce I/O.
   • Bad: SELECT * FROM A JOIN B (fetches all columns)
   • Good: SELECT A.id, B.name FROM A JOIN B (only needed columns)
3. Join Order: Join smaller tables first.
   • Example: Customers (100K rows) vs. Orders (1M rows) → Join Customers first.

3.2 Cost-Based Optimization (CBO)

CBO uses statistics (e.g., ANALYZE in PostgreSQL) to estimate:

• I/O cost: Cost = (rows scanned) × (block size)
• CPU cost: Complex operations (e.g., sorts, joins).
• Example: For SELECT * FROM Orders WHERE order_date > '2023-01-01', CBO might choose:
  • A B-tree index scan (if order_date is indexed) over a seq scan.

How CBO Works (Step-by-Step)

1. Gather Statistics:
   • ANALYZE command updates metadata (e.g., pg_statistic in PostgreSQL).
2. Generate Plans:
   • Enumerates all possible execution paths (e.g., nested loops, hash joins).
3. Estimate Costs:
   • Uses formulas like: $$\text{Cost}=\text{Seq Scan Cost}+\text{Join Cost}+\text{Sort Cost}$$
4. Pick the Cheapest Plan:
   • Example: For JOIN A ON B, CBO might choose:
     • Nested Loop Join (if A is small).
     • Hash Join (if B is large).

---

4. Execution Plans: Physical Operations

4.1 Common Join Strategies

Example: Pathao’s ride-matching system uses hash joins to match drivers and riders in real-time.

4.2 Indexes and Their Impact

Indexes speed up queries but slow down writes. Common types:

• B-tree: Default for =, >, < (e.g., WHERE customer_id = 101).
• Bitmap: Good for low-cardinality columns (e.g., WHERE status = 'active').
• Hash: Exact-match only (e.g., WHERE email = 'user@example.com').

---

5. Distributed Databases & the CAP Theorem

5.1 CAP Theorem Trade-offs

In distributed systems (e.g., Khalti’s payment network), you must choose:

• Consistency (C): All nodes see the same data (e.g., NEPSE’s trade ledger).
• Availability (A): System works even if some nodes fail (e.g., Pathao’s ride requests).
• Partition Tolerance (P): Works during network splits (always true in real systems).

---

6. Real-World Applications

6.1 eSewa: Query Optimization for Bill Payments

• Problem: Millions of SELECT balance FROM Users WHERE user_id = X queries.
• Solution:
  • Heuristic: Cache frequent queries (e.g., user_id lookups).
  • CBO: Use B-tree indexes on user_id and transaction_date.
  • Result: Reduced query time from 50ms → 2ms.

6.2 NEPSE: Cost-Based Optimization for Stock Data

• Problem: SELECT price FROM Trades WHERE symbol = 'NEPSE' AND date = '2023-01-01' must run in <10ms.
• Solution:
  • Partitioning: Store trades by date (range partitioning).
  • Indexing: Composite index on (symbol, date).
  • Execution Plan: Uses index-only scan (avoids table access).

6.3 Daraz: Handling High Traffic with Query Trees

• Problem: SELECT product FROM Inventory WHERE stock > 0 during sales.
• Solution:
  • Query Tree: Pushes σ_stock>0 before joins with Orders.
  • Optimization: Uses materialized views for top products.

---

7. Worked Example: Optimizing a Bank Loan Query

Scenario: A bank runs:

SELECT customer_name, loan_amount
FROM Customers JOIN Loans
WHERE Customers.id = Loans.customer_id
AND loan_status = 'approved'
AND loan_amount > 1000000;

Step 1: Relational Algebra

π_customer_name,loan_amount(
  σ_loan_status='approved' AND loan_amount>1000000(
    Customers ⋈ Loans
  )
)

Step 2: Heuristic Optimization

1. Push σ down:

   π_customer_name,loan_amount(
     σ_loan_status='approved' AND loan_amount>1000000(
       Customers ⋈ σ_customer_id=Customers.id(Loans)
     )
   )
   

2. Project early: Remove unused columns from Customers (e.g., address).

Step 3: Cost-Based Optimization

• Statistics:
  • Customers: 10M rows, id is indexed.
  • Loans: 50M rows, customer_id and loan_status are indexed.
• Best Plan:
  • Nested Loop Join (since Customers is smaller).
  • Index Scan on Loans(loan_status, loan_amount).

Execution Plan:

Index Scan on Loans (Cost: 10.00)  -- Filters approved loans >1M
→ Nested Loop Join (Cost: 50.00)   -- Joins with Customers
  → Index Scan on Customers (Cost: 20.00) -- Fetches customer_name

---

Exam Tip

1. For short answers:

   • Define query tree as "a hierarchical representation of relational algebra operations."
   • CAP theorem: "No distributed system can guarantee all three: Consistency, Availability, and Partition Tolerance."
   • Heuristic optimization: "Rule-based techniques like 'select early' or 'project early' to improve query speed without statistics."

2. For long answers (10+ marks):

   • Structure: Use the 5-step query processing pipeline (Section 1.1).
   • Examples: Always tie to real systems (e.g., "In Khalti, CBO ensures low-latency payment queries").
   • Diagrams: Draw query trees or execution plans to explain optimization steps.
   • CAP Theorem: Compare eSewa (CA) vs. Pathao (AP) in 3 bullet points.

3. Common Pitfalls:

   • Forgetting to explain both heuristic and cost-based optimization.
   • Not showing how indexes reduce I/O (always mention Cost = rows × block size).
   • Ignoring real-world examples (examiners love eSewa/Khalti/NEPSE cases).

---