---

⭐ QUERY EXECUTION

When you write a query in SQL (e.g., SELECT * FROM EMP WHERE SALARY > 50000), the DBMS does NOT execute it directly.
Instead, it goes through a complex internal pipeline involving:

1. Parsing
2. Query Rewriting (Relational Algebra Transformation)
3. Optimization (Logical + Physical)
4. Plan Generation
5. Execution by the Query Engine
6. Accessing storage (Buffer Manager, Index Manager)
7. Returning results

This entire process is known as Query Execution.

---

⭐ 1. Query Compilation Phases

Phase 1: Parsing & Syntax Checking

• SQL query is checked for syntax errors.
• Verifies table names, column names.
• Converts SQL into a Parse Tree (equivalent to a structured AST).

Example

SQL:

SELECT Name FROM EMP WHERE Salary > 50000;

Parse Tree (simplified):

SELECT
   ├── Columns: Name
   └── FROM EMP
          └── WHERE Salary > 50000

---

⭐ 2. Query Rewriting (Logical Rewrite)

The query is transformed into relational algebra (RA).

SQL → Relational Algebra:

π Name ( σ Salary > 50000 (EMP) )

Rewrite rules applied:

• Push selections down
• Combine projections
• Remove redundant conditions
• Flatten subqueries
• Apply view expansion

This generates an improved Logical Query Plan.

---

⭐ 3. Query Optimization

The most critical phase in query execution.

The Query Optimizer selects the best, most efficient execution plan.

Types of Optimization:

1. Logical Optimization
   • Rule-based simplification
   • Predicate pushdown
   • Join reordering
2. Physical Optimization
   • Determines physical operations like
     • index scan
     • sequential scan
     • hash join
     • merge join
     • nested-loop join

Optimizer uses:

✔ Cost model
✔ Table statistics (row count, histograms)
✔ Index availability
✔ CPU & I/O cost models

---

⭐ 4. Execution Plan (Physical Plan Generation)

After optimization, the DBMS produces a physical execution plan, which is a tree of physical operators.

Example Execution Plan:

Nested Loop Join
  ├── Index Scan on EMP (Salary > 50000)
  └── Table Scan on DEPT

You can see an execution plan in SQL using:

EXPLAIN SELECT ... ;

---

⭐ 5. Query Execution Engine

The final plan is handed over to the Execution Engine, which uses:

• Executor
• Access methods
• Buffer manager
• Lock manager
• Transaction manager

It runs the plan operator-by-operator.

---

⭐ 6. Access Methods: Index Scan, Table Scan

To fetch data, DBMS chooses one of:

✔ Table Scan

Reads the whole table → slow but necessary when:

• No index
• Query needs most rows

✔ Index Scan

Uses B-Tree or Hash indexes → fast.

Example:
WHERE Salary > 50000 uses Salary index.

---

⭐ 7. Buffer Manager Interaction

Fetched pages (disk blocks) are brought from disk into buffer pool.

Buffer manager handles:

• Page replacement (LRU / CLOCK)
• Prefetching
• Caching

Reduces costly disk I/O.

---

⭐ 8. Join Algorithms in Query Execution

Join operations are costliest in query execution. DBMS may choose:

✔ Nested Loop Join

Simple but slow (O(n*m))
Useful when inner table is small or indexed.

✔ Merge Join

Requires sorted inputs; very efficient for large datasets.

✔ Hash Join

Creates hash table on one relation → fast for large, unsorted relations.

---

⭐ 9. Output Generation

After executing all RA operators, DBMS:

• Forms result tuples
• Eliminates duplicates (if required)
• Sorts (if required)
• Returns output to client

---

⭐ Complete Query Execution Pipeline (Diagram)

      SQL Query
          |
          v
+------------------+
| 1. Parser        |
| Syntax + Semantics |
+------------------+
          |
          v
+------------------+
| 2. Query Rewriter|
| RA Transformation |
+------------------+
          |
          v
+------------------+
| 3. Optimizer      |
| Cost-based Plan   |
+------------------+
          |
          v
+------------------+
| 4. Execution Plan |
+------------------+
          |
          v
+------------------------+
| 5. Execution Engine    |
|  - Access Methods      |
|  - Buffer Manager      |
+------------------------+
          |
          v
       Output

---

⭐ Example: Step-by-Step Query Execution

SQL Query:

SELECT Name FROM EMP WHERE DeptID = 10 AND Salary > 50000;

Step 1: Parse

No syntax errors.

Step 2: Convert to RA

π Name ( σ DeptID=10 ∧ Salary>50000 (EMP) )

Step 3: Optimization

• Push down selections early
• Use index on DeptID and Salary if available
• Choose index-scan instead of table scan

Step 4: Execution Plan

Index Scan on EMP using idx_dept_salary
  Filter: DeptID=10 AND Salary>50000
Project: Name

Step 5: Execute

→ Fetch matching rows
→ Output Name column

---

⭐ Query Execution vs Query Processing

Query Processing	Query Execution
Entire pipeline from parsing → optimization → execution	Final stage of actually running the physical plan
Includes RA rewriting, plan generation	Uses buffer manager, joins, access methods
Logical + physical	Physical only

---

⭐ Perfect 5-Mark Short Answer

Query execution is the final phase of query processing where a physical query plan is executed by the DBMS. Steps include accessing base tables using table scans or index scans, applying selection and projection, performing join algorithms like nested loop or hash join, and retrieving data from storage via the buffer manager. The execution engine follows the optimized physical plan to produce the final result set.

---