Query Optimization: Techniques, Execution Plans, Indexing & Cost-Based Analysis

Key Concepts and Techniques

What is Query Optimization?

Query optimization is the process of improving the efficiency of SQL queries by reducing execution time, minimizing resource consumption (CPU, I/O, memory), and ensuring optimal use of database indexes and structures. The database optimizer evaluates different query execution plans and selects the most efficient one based on cost estimation.

How the Database Optimizer Works

The database optimizer follows these steps:

1. Parsing: Checks syntax and converts SQL into an internal representation.
2. Semantic Analysis: Validates object references (tables, columns).
3. Query Transformation: Rewrites the query into an equivalent but optimized form (e.g., converting WHERE clauses into JOIN conditions).
4. Cost Estimation: Evaluates multiple execution plans and assigns a cost (based on I/O, CPU, and memory usage).
5. Plan Selection: Chooses the plan with the lowest estimated cost.

stateDiagram-v2
    [*] --> Parsing: Checks syntax
    Parsing --> Semantic: Validates objects
    Semantic --> Transformation: Rewrites query
    Transformation --> CostEstimation: Evaluates plans
    CostEstimation --> PlanSelection: Chooses best plan
    PlanSelection --> [*]

Execution Plans

An execution plan is a roadmap that the database follows to execute a query. It shows the sequence of operations (e.g., TABLE ACCESS, INDEX RANGE SCAN, HASH JOIN) and their order. Execution plans can be visualized using tools like Oracle’s EXPLAIN PLAN, SQL Server’s Execution Plan, or MySQL’s EXPLAIN.

graph TD
    A["Query Execution"] --> B["Scan Table"]
    B --> C["Apply Filters"]
    C --> D["Join Tables"]
    D --> E["Sort Results"]
    E --> F["Return to User"]

Types of Execution Plans:

1. Estimated Execution Plan: Shows the optimizer’s predicted cost and steps (useful for tuning).
2. Actual Execution Plan: Displays real-time statistics (e.g., rows processed, I/O, CPU time).

Example (Oracle):

EXPLAIN PLAN FOR
SELECT * FROM employees WHERE salary > 50000;
SELECT * FROM TABLE(DBMS_XPLAN.DISPLAY);

Output:

--------------------------------------------------
| Id  | Operation          | Name      | Rows  | Bytes |
--------------------------------------------------
|   0 | SELECT STATEMENT   |           | 1000  | 45000 |
|   1 |  TABLE ACCESS FULL | EMPLOYEES | 1000  | 45000 |
--------------------------------------------------

Here, TABLE ACCESS FULL means a full table scan, which is inefficient for large tables.

Indexing Strategies for Optimization

Indexes speed up data retrieval by providing direct access paths to rows. However, they add overhead during INSERT, UPDATE, and DELETE operations.

Types of Indexes

When to Use Indexes

• High-selectivity columns: Columns with many unique values (e.g., email, SSN).
• Frequently queried columns: Columns used in WHERE, JOIN, or ORDER BY.
• Avoid over-indexing: Each index slows down INSERT/UPDATE operations.

Example:

-- Create an index on the 'email' column for faster lookups
CREATE INDEX idx_employee_email ON employees(email);

Query Rewriting Techniques

Rewriting queries can significantly improve performance by leveraging indexes, reducing joins, or simplifying logic.

Common Techniques:

1. Avoid SELECT *: Fetch only required columns.

   -- Bad: Retrieves all columns
   SELECT * FROM orders;
   -- Good: Retrieves only needed columns
   SELECT order_id, customer_id, order_date FROM orders;
   

2. Use EXISTS instead of IN for subqueries:

   -- Slower (creates a temporary table)
   SELECT * FROM employees WHERE department_id IN (SELECT dept_id FROM departments WHERE location = 'Kathmandu');
   -- Faster (stops at first match)
   SELECT * FROM employees e WHERE EXISTS (SELECT 1 FROM departments d WHERE d.dept_id = e.department_id AND d.location = 'Kathmandu');
   

3. Replace OR with UNION ALL:

   -- Inefficient (can't use indexes)
   SELECT * FROM products WHERE category = 'Electronics' OR category = 'Clothing';
   -- Efficient (uses indexes separately)
   SELECT * FROM products WHERE category = 'Electronics'
   UNION ALL
   SELECT * FROM products WHERE category = 'Clothing';
   

4. Use JOIN instead of subqueries:

   -- Inefficient (nested loop)
   SELECT e.name FROM employees e WHERE e.department_id = (SELECT dept_id FROM departments WHERE name = 'IT');
   -- Efficient (join)
   SELECT e.name FROM employees e JOIN departments d ON e.department_id = d.dept_id WHERE d.name = 'IT';
   

Cost-Based Optimization

The database optimizer uses cost-based optimization (CBO) to estimate the most efficient execution plan. Cost is calculated based on:

• I/O Cost: Time to read data from disk (slowest operation).
• CPU Cost: Time to process data in memory.
• Memory Usage: Buffer cache hits vs. disk reads.

Factors Affecting Cost:

1. Statistics: The optimizer relies on table statistics (e.g., number of rows, column values distribution).

   -- Update statistics in Oracle
   EXEC DBMS_STATS.GATHER_TABLE_STATS('HR', 'EMPLOYEES');
   

2. Index Selectivity: Higher selectivity (more unique values) reduces I/O.
3. Join Methods:
   • Nested Loop Join: Fast for small tables but slow for large ones.
   • Hash Join: Efficient for large tables in memory.
   • Sort-Merge Join: Uses sorting (good for ordered data).

Example (Join Cost Comparison):

graph LR
    A["Small Table"] -->|"Nested Loop"| B["Fast"]
    C["Large Table"] -->|"Hash Join"| D["Fast in Memory"]
    E["Ordered Data"] -->|"Sort-Merge"| F["Efficient"]

Real-World Applications

1. eSewa (Nepal)

• Use Case: Query optimization for transaction processing.
• How: eSewa’s database uses indexed tables for user_id and transaction_id to ensure fast retrieval during payments. Composite indexes on (user_id, transaction_date) speed up reports for fraud detection.

2. Khalti (Nepal)

• Use Case: Real-time balance checks.
• How: Khalti’s backend uses hash indexes on account_number for O(1) lookup during fund transfers. Cost-based optimization ensures that high-frequency queries (e.g., balance inquiries) execute in milliseconds.

3. Nepal Stock Exchange (NEPSE)

• Use Case: Stock price updates.
• How: NEPSE’s database uses materialized views and partitioned tables (by date) to optimize queries for real-time stock price feeds. Execution plans are tuned to minimize I/O during peak trading hours.

4. Pathao (Ride-Hailing App)

• Use Case: Driver location queries.
• How: Pathao’s database uses geospatial indexes (e.g., PostgreSQL’s GiST) to quickly find nearby drivers. A poorly optimized query could cause delays in matching riders to drivers, increasing wait times.

Worked Example: Daraz Order Processing

Scenario: Daraz needs to optimize queries for order status updates during Black Friday sales (high traffic). Problem: A query to fetch orders with status = 'Processing' takes 5 seconds due to a full table scan. Solution:

1. Add an index:

   CREATE INDEX idx_order_status ON orders(status);
   

2. Rewrite the query:

   -- Before (slow)
   SELECT * FROM orders WHERE status = 'Processing';
   -- After (fast, uses index)
   SELECT order_id, customer_id FROM orders WHERE status = 'Processing';
   

3. Result: Query time reduces to 200ms, handling 10x more requests during peak hours.

Performance Tuning Tools

Example (MySQL EXPLAIN):

EXPLAIN SELECT * FROM customers WHERE country = 'Nepal';

Output:

+----+-------------+-----------+------------+-------+---------------+---------+---------+------+------+----------+----------------+
| id | select_type | table     | partitions | type  | possible_keys | key     | key_len | ref  | rows | filtered | Extra          |
+----+-------------+-----------+------------+-------+---------------+---------+---------+------+------+----------+----------------+
|  1 | SIMPLE      | customers | NULL       | ref   | idx_country   | idx_country | 101    | const|    5 |   100.00 | NULL           |
+----+-------------+-----------+------------+-------+---------------+---------+---------+------+------+----------+----------------+

• type = ref: Uses the index (idx_country) for fast lookup.
• rows = 5: Only 5 rows are scanned.

Common Pitfalls and Mistakes

1. Missing Indexes: Queries on unindexed columns perform full table scans.
   • Fix: Add indexes to frequently queried columns.
2. Over-Indexing: Too many indexes slow down INSERT/UPDATE.
   • Fix: Monitor index usage and drop unused ones.
3. Cartesian Products: Unintended joins without ON clauses.
   • Fix: Always specify join conditions.
4. Implicit Conversions: Comparing VARCHAR and INT forces full scans.
   • Fix: Use explicit casting or matching data types.
5. Long-Running Transactions: Locks tables and blocks other queries.
   • Fix: Commit transactions frequently.

Exam Tip

For the Database Administration (IT276) exam, focus on:

1. Execution Plans: Be able to read and interpret EXPLAIN output for SQL queries.
2. Indexing: Know when to use B-tree, hash, or composite indexes and their trade-offs.
3. Query Rewriting: Practice converting inefficient queries (e.g., OR to UNION ALL, IN to EXISTS).
4. Cost-Based Optimization: Understand how statistics and join methods affect query cost.
5. Real-World Scenarios: Relate optimization techniques to Nepali companies (e.g., eSewa, Khalti) or global platforms (e.g., YouTube’s video search indexing).

Common Exam Questions:

• Explain how a database optimizer selects the best execution plan.
• Compare Nested Loop Join and Hash Join with examples.
• Write SQL to optimize a slow-running query (e.g., add an index, rewrite OR).
• Describe the impact of indexing on INSERT performance.