Query Processing & Optimization: Steps, Costs, Trees & Techniques

TAKEAWAYS:

• Query processing follows 4 phases: parsing → optimization → execution → result delivery, with each phase adding metadata (query tree, cost estimates).
• Cost models (I/O, CPU, memory) determine the cheapest execution plan, measured in disk reads, CPU cycles, and buffer hits.
• Optimization techniques include rewriting (joins → subqueries), materialized views (precomputed results), and pipelined evaluation (streaming intermediate results).
• Indexing (B-trees, hash) and partitioning reduce I/O costs for large tables, while query hints override the optimizer’s choices.
• Real-world impact: NEPSE’s stock queries use materialized views for fast historical data, while eSewa’s transaction logs rely on pipelined evaluation to handle 10,000+ concurrent payments.
• Exam focus: Be ready to draw query trees, compare cost models, and write optimized SQL for given scenarios (e.g., Daraz’s order fulfillment queries).

1. What is Query Processing?

Query processing is the end-to-end journey of a SQL query from submission to result delivery. It involves:

1. Parsing: Checking syntax, resolving references (e.g., table/column names).
2. Semantic Analysis: Validating constraints (e.g., foreign keys, NULLs).
3. Optimization: Choosing the fastest execution plan.
4. Execution: Running the plan (e.g., scanning tables, joining rows).
5. Result Delivery: Returning data to the client.

Why optimize? Without optimization, a query like SELECT * FROM Orders WHERE CustomerID = 100 might scan every row in a 10M-row table, wasting CPU and I/O. Optimization rewrites it to use an index on CustomerID, reducing scans to ~100 rows.

flowchart TD
    A["User Submits Query"] --> B["Parser: Syntax Check"]
    B --> C["Semantic Analyzer: Validate Constraints"]
    C --> D["Optimizer: Choose Best Plan"]
    D --> E["Executor: Run Plan"]
    E --> F["Result Delivery"]
    D -->|"Alternate Plans"| G["Query Tree"]
    G --> H["Cost Estimator"]
    H -->|"Cheapest Path"| D

2. Steps in Query Processing

A. Parsing and Semantic Analysis

• Parser: Breaks SQL into tokens (e.g., SELECT, FROM, WHERE). Example: SELECT Name FROM Employees WHERE Salary > 50000 → Tokens: SELECT, Name, FROM, Employees, WHERE, Salary, >, 50000.
• Semantic Analyzer: Checks if tables/columns exist and constraints are met.
  • Error: SELECT NonExistentColumn FROM Employees → Fails here.
  • Success: SELECT Name FROM Employees → Proceeds to optimization.

B. Query Optimization

The optimizer’s goal: Find the cheapest execution plan using:

1. Query Rewriting: Convert one query form to another with lower cost.
   • Example: Rewrite JOIN as a SUBQUERY if indexes exist.
   • Before: SELECT * FROM Orders JOIN Customers ON Orders.CustomerID = Customers.ID
   • After: SELECT * FROM Orders WHERE CustomerID IN (SELECT ID FROM Customers)
2. Query Tree Construction: Represent the query as a tree of operations.
   • Example for SELECT Name FROM Employees WHERE Department = 'IT':

     flowchart TD
         A["Scan Employees"] --> B["Filter: Department = 'IT'"] --> C["Project: Name"]

3. Cost Estimation: Assign costs to each operation (see Section 3).

C. Execution

• The executor follows the optimized plan, using:
  • Buffers: Cache frequently accessed data in memory.
  • Indexes: Skip full table scans (e.g., B-tree indexes for WHERE clauses).
  • Parallelism: Split work across CPU cores (e.g., CREATE INDEX CONCURRENTLY in PostgreSQL).

D. Result Delivery

• Streaming: Send results row-by-row (e.g., SELECT * FROM LargeTable).
• Materialized Results: Store intermediate results (e.g., WITH clauses in PostgreSQL).

3. How Cost is Measured

Cost models predict the time/resources needed for each operation. Common metrics:

Example: For SELECT * FROM Orders WHERE OrderDate > '2023-01-01':

• Without Index: Scan all 1M rows → I/O Cost = 100 * 1000 = 100,000.
• With Index: Scan only 100 matching rows → I/O Cost = 100 * 1 = 100.

4. Query Optimization Techniques

A. Materialized Views

• Definition: Precomputed query results stored as tables.
• Use Case: NEPSE’s stock price history is stored as a materialized view to avoid recalculating daily.
• SQL Example:

  CREATE MATERIALIZED VIEW DailyStockPrices AS
  SELECT Date, Symbol, ClosePrice
  FROM StockData
  WHERE Date >= CURRENT_DATE - 30;
  

• Pros/Cons:

  Pros	Cons
  Faster reads (no computation)	Storage overhead
  Reduces CPU load	Requires refreshes (e.g., REFRESH MATERIALIZED VIEW)

B. Pipelined Evaluation

• Definition: Process query results as they arrive, without waiting for full completion.
• Use Case: Pathao’s ride allocation system streams driver locations to match riders in real-time.
• Example:

  -- Traditional: Load all data first
  SELECT * FROM LargeTable WHERE Condition;
  
  -- Pipelined: Stream results
  SELECT * FROM LargeTable WHERE Condition FETCH FIRST 100 ROWS ONLY;
  

• Advantages:
  • Lower memory usage (no full result set in RAM).
  • Faster response for partial results (e.g., paginated searches).

C. Query Rewriting

• Techniques:
  1. Push Predicates: Apply WHERE filters early to reduce rows.
     • Bad: SELECT * FROM A JOIN B ON A.id = B.id WHERE A.value > 100
     • Good: SELECT * FROM A WHERE A.value > 100 JOIN B ON A.id = B.id
  2. Join Order Optimization: Choose the smallest table first.
     • Example: For Orders (1M rows) and Customers (100 rows), join Customers first.
  3. Subquery Unnesting: Convert correlated subqueries to joins.
     • Before: SELECT * FROM Orders WHERE CustomerID IN (SELECT ID FROM Customers WHERE Region = 'Kathmandu')
     • After: SELECT O.* FROM Orders O JOIN Customers C ON O.CustomerID = C.ID WHERE C.Region = 'Kathmandu'

D. Indexing Strategies

• B-tree Indexes: Best for =, >, < queries (e.g., WHERE Salary > 50000).
• Hash Indexes: Fast for exact matches (e.g., WHERE CustomerID = 100).
• Composite Indexes: Combine columns (e.g., (LastName, FirstName)).
  • Example: For SELECT * FROM Employees WHERE Department = 'IT' AND Salary > 50000, use:

    CREATE INDEX idx_dept_salary ON Employees(Department, Salary);
    

5. Real-World Applications

A. eSewa’s Payment Processing

• Problem: Handles 10,000+ transactions/sec during festivals.
• Solution:
  • Materialized Views: Precompute daily transaction summaries.
  • Pipelined Evaluation: Stream payment confirmations to users without waiting for batch processing.
  • Indexing: Hash indexes on TransactionID for O(1) lookups.

B. NEPSE’s Stock Data

• Problem: Analysts need historical stock prices for 1000+ companies.
• Solution:
  • Materialized Views: Store daily closing prices to avoid recalculating from raw trades.
  • Partitioning: Split data by Year to reduce scan size (e.g., PARTITION BY RANGE (TradeDate)).

C. Daraz’s Order Fulfillment

• Problem: High latency in SELECT * FROM Orders WHERE Status = 'Processing' during sales.
• Solution:
  • Query Rewriting: Replace SELECT * with SELECT OrderID, CustomerID to fetch only needed columns.
  • Indexing: B-tree on (Status, OrderDate) for fast status checks.

6. Worked Example: Optimizing a Bank Loan Query

Scenario: A bank’s Loans table (10M rows) needs to find all high-risk loans (CreditScore < 600 and LatePayments > 3). Tables:

Loans(LoanID, CustomerID, Amount, CreditScore, LatePayments)
Customers(CustomerID, Name, Address)

Step 1: Naive Query (Slow)

SELECT L.LoanID, C.Name
FROM Loans L JOIN Customers C ON L.CustomerID = C.CustomerID
WHERE L.CreditScore < 600 AND L.LatePayments > 3;

• Cost: Scans all 10M rows → High I/O.

Step 2: Optimized Query (Fast)

-- Step 1: Filter first (push predicates)
SELECT L.LoanID, C.Name
FROM Loans L JOIN Customers C ON L.CustomerID = C.CustomerID
WHERE L.CreditScore < 600 AND L.LatePayments > 3;

• With Indexes:

  CREATE INDEX idx_credit_late ON Loans(CreditScore, LatePayments);
  

• Query Tree:

  flowchart TD
      A["Scan Loans (using index)"] --> B["Filter: CreditScore < 600 AND LatePayments > 3"] --> C["Join Customers"] --> D["Project: LoanID, Name"]

• Cost: Scans only ~1000 high-risk rows → 90% faster.

7. Common Pitfalls and How to Avoid Them

8. Exam Tip: How to Score Full Marks

1. For "Define query processing" (1+4 marks):

   • 1 mark: "Query processing is the series of steps to execute a SQL query efficiently."
   • 4 marks: Describe all 4 phases (parsing, optimization, execution, delivery) with one example each (e.g., parsing checks syntax, optimization picks the cheapest plan).

2. For "Draw a query tree" (4 marks):

   • Use Mermaid syntax (as shown above) or a textual tree.
   • Label nodes (e.g., "Scan", "Filter", "Join") and edges (e.g., "→ Project").
   • Example: For SELECT Name FROM Employees WHERE Salary > 50000, show:

     Scan Employees → Filter (Salary > 50000) → Project (Name)
     

3. For "Optimize this SQL" (6 marks):

   • Step 1: Identify bottlenecks (e.g., full scan, missing index).
   • Step 2: Rewrite using predicate pushdown or join order.
   • Step 3: Add indexes or materialized views.
   • Example: For SELECT * FROM Orders WHERE CustomerID IN (SELECT ID FROM Customers WHERE Region = 'Kathmandu'), rewrite as:

     SELECT O.* FROM Orders O JOIN Customers C ON O.CustomerID = C.ID WHERE C.Region = 'Kathmandu';
     

     • Bonus: Mention "This avoids the correlated subquery overhead."

4. For "Compare materialized views vs. pipelined evaluation" (5 marks):

   • Use a table like this:

     Feature	Materialized Views	Pipelined Evaluation
     Use Case	Precomputed aggregations	Streaming intermediate results
     Storage	High (stores results)	Low (streams data)
     Refresh Overhead	Yes (periodic refreshes)	No (real-time)
     Example	NEPSE’s stock summaries	Pathao’s live ride matching

9. Practice Questions (Exam-Style)

1. Draw the query tree for:

   SELECT DISTINCT Department
   FROM Employees
   WHERE Salary > 50000
   ORDER BY Department;
   

2. Optimize the following query for a Products table (10M rows):

   SELECT P.Name, S.Supplier
   FROM Products P JOIN Suppliers S ON P.SupplierID = S.ID
   WHERE P.Price > 1000 AND S.Country = 'USA';
   

3. Explain how a bank uses indexing and materialized views to speed up loan approval queries. Give one SQL example for each.