Query Processing & Optimization: Execution Plans, Indexes, Joins, Cost Models

TAKEAWAYS:

• Query execution follows a three-phase process: parsing → optimization → execution, with each phase transforming the query into an efficient plan.
• Indexing (B-trees, hash, bitmap) speeds up searches but adds storage and write overhead; choose based on query patterns.
• Join algorithms (nested loops, hash join, merge join) differ in cost and suitability for sorted/unsorted data.
• Cost-based optimization uses statistical metadata (e.g., table sizes, selectivity) to pick the cheapest execution plan.
• Query rewriting (e.g., predicate pushdown, view merging) can drastically reduce I/O and computation.
• Real-world systems like NEPSE (stock market) and Daraz (e-commerce) rely on optimized queries to handle millions of transactions per second.

---

1. Query Processing Overview

Databases don’t run SQL queries directly—they process them in stages to generate an efficient execution plan. Think of it like a chef preparing a dish:

1. Parsing: Checks syntax and converts SQL into an abstract syntax tree (AST).
2. Optimization: Rewrites the query (e.g., simplifies joins, pushes filters down) and selects the best plan.
3. Execution: Runs the plan step-by-step, accessing data via indexes or full scans.

Why it matters: Without optimization, even simple queries (e.g., "Find all Daraz orders shipped to Kathmandu in 2023") could scan millions of rows inefficiently.

---

2. The Optimization Phase: How Databases Choose the Best Plan

The optimizer compares multiple execution plans (e.g., two joins in different orders) and picks the cheapest one based on:

• Statistics: Table sizes, column distributions (e.g., 80% of NEPSE trades are under ₹500).
• Cost models: Estimates I/O, CPU, and memory usage (e.g., a hash join might be faster for unsorted data).

Key Techniques

Visual: Cost comparison of two plans for SELECT * FROM orders JOIN customers ON orders.customer_id = customers.id:

Worked Example: NEPSE’s Trade Query Suppose NEPSE runs:

SELECT t.symbol, SUM(t.quantity)
FROM trades t
WHERE t.timestamp > '2023-01-01'
GROUP BY t.symbol;

• Bad plan: Scans all trades (millions of rows) → groups → filters.
• Optimized plan:
  1. Predicate pushdown: Filters timestamp early (reduces rows by 90%).
  2. Index scan: Uses a B-tree on timestamp (if indexed).
  3. Hash aggregation: Groups remaining rows in memory.

---

3. Indexes: The Secret Weapon for Fast Queries

Indexes are data structures (B-trees, hash, bitmap) that speed up searches but slow down writes. Choose wisely!

Index Types

How indexes work:

1. B-tree: Balanced tree where leaves hold sorted keys (like a phone book).

2. Hash: Direct mapping (e.g., user_id → password_hash).
3. Bitmap: Bit arrays for categorical data (e.g., status = "active" or "inactive").

Worked Example: Pathao’s Ride Search Pathao’s app uses a composite index on (pickup_location, dropoff_location, timestamp) to:

• Quickly find rides near you (B-tree on pickup_location).
• Filter by time (range scan on timestamp).
• Avoid full table scans during peak hours (e.g., 6–9 PM).

When NOT to index:

• Tables with frequent updates (indexes slow INSERT/UPDATE).
• Columns used in sorts/joins (unless selective).

---

4. Join Algorithms: How Databases Combine Tables

Joins are expensive—databases use different strategies based on data size and sort status.

Visual: Hash join steps for orders JOIN products:

Worked Example: Bank Loan Approval A bank runs:

SELECT c.name, SUM(l.amount)
FROM customers c
JOIN loans l ON c.id = l.customer_id
WHERE l.status = 'approved';

• Optimized plan:
  1. Hash join: Builds a hash table on customer_id (from loans).
  2. Probe: Joins with customers (faster than nested loops if loans is large).

---

5. Cost-Based Optimization: The Math Behind "Cheapest Plan"

Databases use statistics (e.g., table sizes, column distributions) to estimate costs. For example:

Worked Example: Khalti’s Transaction Query Khalti optimizes:

SELECT u.name, COUNT(t.id)
FROM users u
JOIN transactions t ON u.id = t.user_id
WHERE t.amount > 1000;

• Cost model:
  • transactions has 10M rows, 80% are >₹1000 → selectivity = 0.8.
  • Nested loop cost: users (1M) × transactions (10M) × 0.8 = 8B ops.
  • Hash join cost: users (1M) + transactions (10M) × 0.8 = 9M ops → cheaper.

---

6. Query Rewriting: Tricks to Save Resources

Databases rewrite queries to avoid redundant work. Examples:

• Predicate pushdown: Move WHERE clauses to earlier stages.

  -- Before: Scan all orders, then filter.
  SELECT * FROM orders WHERE status = 'shipped';
  
  -- After: Filter first (if index exists).
  SELECT * FROM orders WHERE status = 'shipped';
  

• View merging: Replace views with their base tables.

  -- Before: Scan `high_value_customers` (view) → scan `orders` again.
  SELECT * FROM high_value_customers;
  
  -- After: Direct join with `orders`.
  SELECT * FROM customers c JOIN orders o ON c.id = o.customer_id
  WHERE o.amount > 10000;
  

• Common table expressions (CTEs): Break complex queries into steps.

  WITH top_customers AS (
      SELECT customer_id, SUM(amount) as total
      FROM orders
      GROUP BY customer_id
      ORDER BY total DESC
      LIMIT 100
  )
  SELECT * FROM top_customers;
  

---

In the Real World

1. NEPSE (Nepal Stock Exchange)

   • Idea: Indexed range scans on timestamp and symbol columns.
   • How: Trades are stored in a B-tree indexed by timestamp to quickly fetch daily summaries (e.g., "Top 10 stocks by volume on 2023-10-01").
   • Worked example: A query like SELECT * FROM trades WHERE timestamp BETWEEN '2023-10-01' AND '2023-10-31' uses a range scan on the index instead of scanning all 50M trades.

2. Daraz (E-commerce)

   • Idea: Hash joins for product-customer relationships.
   • How: When a user searches for "laptops," Daraz joins products (1M rows) with customer_reviews (5M rows) using a hash table on product_id. Without optimization, this would take hours.
   • Real query:

     SELECT p.name, AVG(r.rating)
     FROM products p
     JOIN reviews r ON p.id = r.product_id
     WHERE p.category = 'electronics'
     GROUP BY p.id;
     

3. Ncell (Telecom)

   • Idea: Predicate pushdown in bill generation.
   • How: When generating monthly bills, Ncell filters inactive users early (using a bitmap index on status) before joining with call logs (100M rows). This reduces the join size by 95%.

---

Exam Tip

1. Focus on trade-offs:

   • Indexes speed up reads but slow down writes. Example: "Why doesn’t NEPSE index trades.timestamp for all queries?" → "Because frequent updates (new trades) would degrade performance."
   • Joins: Nested loops are simple but slow for large tables. Example: "How would you optimize SELECT * FROM orders JOIN customers if orders is 100x larger than customers?" → "Use a hash join with customers as the build table."

2. Draw execution plans:

   • Always sketch the before/after optimization for a query. Example:

     Before: Full scan (orders) → Full scan (customers) → Join
     After:  Index scan (orders.customer_id) → Hash join
     

3. Cost-based questions:

   • Given table sizes and selectivity, calculate which join is cheaper. Example:
     • Table A: 10K rows, Table B: 1M rows, join on id.
     • Nested loop cost: 10K × 1M = 10B ops.
     • Hash join cost: 1M (build) + 10K (probe) = 1.01M ops → hash join wins.

4. Real-world mapping:

   • Link concepts to Nepalese apps. Example:
     • "How does Pathao use indexes?" → "Composite index on (pickup_location, dropoff_location, timestamp) for fast ride searches."
     • "Why does Khalti use hash joins?" → "Transactions are unsorted, but hash joins are efficient for exact-match lookups."

5. Common pitfalls:

   • Ignoring statistics: Always assume the optimizer has up-to-date stats (e.g., table sizes, column distributions).
   • Over-indexing: Don’t index every column—focus on selective columns (e.g., email is better than last_name for lookups).
   • Forgetting join order: A JOIN B JOIN C is not always the same as B JOIN C JOIN A—cost depends on table sizes.

---

Final Visual: Query optimization pipeline (recap)