Query Processing

Query processing is the set of activities involved in retrieving data from a database in response to a SQL query. It translates a high-level SQL statement...

What is Query Processing?

Query processing is the set of activities involved in retrieving data from a database in response to a SQL query. It translates a high-level SQL statement into a sequence of low-level operations that can be executed on the stored data.

Step 1 — Parsing and Translation

The parser:

Checks SQL syntax
Verifies table/column names exist (in system catalog)
Checks data types and permissions
Produces a parse tree

SQL

SELECT name, salary FROM Employee WHERE dept_id = 1;

Parse Tree

SELECT

/ \

name, salary WHERE

/ \

Employee dept_id = 1

Relational Algebra

π_{name, salary}(σ_{dept_id=1}(Employee))

Step 2 — Relational Algebra Expression

The query is converted into a relational algebra expression or query tree (expression tree):

Query Tree for:

SELECT e.name, d.dept_name

FROM Employee e JOIN Department d ON e.dept_id = d.dept_id

WHERE e.salary > 70000;

π_{name, dept_name}

│

σ_{salary > 70000}

│

⋈_{dept_id}

/ \

Employee Department

Step 3 — Query Optimization

The optimizer generates multiple equivalent execution plans and picks the cheapest one based on cost estimates.

Algebraic Optimizations (Heuristics):

Rule 1	Push selections DOWN (apply early to reduce rows)
Rule 2	Push projections DOWN (reduce columns early)
Rule 3	Perform MOST SELECTIVE operations first
Rule 4	Join order matters for intermediate result sizes

Step 4 — Physical Query Plan (Execution Plan)

For each relational algebra operation, the optimizer chooses a physical algorithm:

Logical Operation	Physical Algorithms
Selection (σ)	Linear scan, Index scan, B+ tree traversal
Projection (π)	Sequential scan + column elimination
Join (⋈)	Nested loop join, Sort-merge join, Hash join
Sorting	External merge sort
Grouping	Hashing, Sorting

Physical Join Algorithms

1. Nested Loop Join

If r.key = s.key	output (r, s)
Cost	\|R\| × \|S\| tuple comparisons
Best when	one of the relations fits in memory

2. Block Nested Loop Join

Example

For each BLOCK of R: For each BLOCK of S: Join all tuples in the block pair Cost: |B_R| + (|B_R| × |B_S|) block I/Os Much better than tuple-level nesting

3. Index Nested Loop Join

Example

For each tuple r in R: Use INDEX on S to find matching tuples → much faster than scanning all of S Cost: |B_R| + |R| × (index traversal cost) Best when: S has an index on the join attribute

4. Sort-Merge Join

Example

1. Sort R by join attribute 2. Sort S by join attribute 3. Merge the two sorted files (like merge sort) Cost: Sort R + Sort S + Merge pass Best when: Both relations are large; sorted output needed

5. Hash Join

Example

Phase 1 (Build): Hash all tuples of R into hash buckets (in memory) Phase 2 (Probe): For each tuple s in S: Hash s, probe the bucket for matches Output matching pairs Cost: 3 × (|B_R| + |B_S|) block I/Os Best when: both relations are large; equality join

EXPLAIN — Viewing Query Plans

Most DBMS allow you to inspect the chosen execution plan:

sql example

-- MySQL / MariaDB
EXPLAIN SELECT e.name, d.dept_name
FROM Employee e
JOIN Department d ON e.dept_id = d.dept_id
WHERE e.salary > 70000;

-- PostgreSQL
EXPLAIN ANALYZE SELECT ...;

-- Output shows:
-- Join method used (nested loop / hash join / merge join)
-- Whether indexes were used
-- Estimated rows, cost, actual time

Query Execution Engine

The execution engine

1. Reads the chosen physical plan

2. Calls operators in pipeline fashion:

- Each operator reads from its inputs

- Produces output tuples one at a time (pipelining)

- No need to materialize intermediate results in memory

3. Returns final result set to the client

Pipelining

Scan → Select → Project → Join → Sort

Each operator passes tuples directly to the next

→ Reduces memory usage and disk I/O

What is Query Processing?

Step 1 — Parsing and Translation

The parser:

Checks SQL syntax
Verifies table/column names exist (in system catalog)
Checks data types and permissions
Produces a parse tree

SQL

SELECT name, salary FROM Employee WHERE dept_id = 1;

Parse Tree

SELECT

/ \

name, salary WHERE

/ \

Employee dept_id = 1

Relational Algebra

π_{name, salary}(σ_{dept_id=1}(Employee))

Step 2 — Relational Algebra Expression

The query is converted into a relational algebra expression or query tree (expression tree):

Query Tree for:

SELECT e.name, d.dept_name

FROM Employee e JOIN Department d ON e.dept_id = d.dept_id

WHERE e.salary > 70000;

π_{name, dept_name}

│

σ_{salary > 70000}

│

⋈_{dept_id}

/ \

Employee Department

Step 3 — Query Optimization

The optimizer generates multiple equivalent execution plans and picks the cheapest one based on cost estimates.

Algebraic Optimizations (Heuristics):

Rule 1	Push selections DOWN (apply early to reduce rows)
Rule 2	Push projections DOWN (reduce columns early)
Rule 3	Perform MOST SELECTIVE operations first
Rule 4	Join order matters for intermediate result sizes

Step 4 — Physical Query Plan (Execution Plan)

For each relational algebra operation, the optimizer chooses a physical algorithm:

Logical Operation	Physical Algorithms
Selection (σ)	Linear scan, Index scan, B+ tree traversal
Projection (π)	Sequential scan + column elimination
Join (⋈)	Nested loop join, Sort-merge join, Hash join
Sorting	External merge sort
Grouping	Hashing, Sorting

Physical Join Algorithms

1. Nested Loop Join

If r.key = s.key	output (r, s)
Cost	\|R\| × \|S\| tuple comparisons
Best when	one of the relations fits in memory

2. Block Nested Loop Join

Example

For each BLOCK of R: For each BLOCK of S: Join all tuples in the block pair Cost: |B_R| + (|B_R| × |B_S|) block I/Os Much better than tuple-level nesting

3. Index Nested Loop Join

Example

For each tuple r in R: Use INDEX on S to find matching tuples → much faster than scanning all of S Cost: |B_R| + |R| × (index traversal cost) Best when: S has an index on the join attribute

4. Sort-Merge Join

Example

1. Sort R by join attribute 2. Sort S by join attribute 3. Merge the two sorted files (like merge sort) Cost: Sort R + Sort S + Merge pass Best when: Both relations are large; sorted output needed

5. Hash Join

Example

EXPLAIN — Viewing Query Plans

Most DBMS allow you to inspect the chosen execution plan:

sql example

-- MySQL / MariaDB
EXPLAIN SELECT e.name, d.dept_name
FROM Employee e
JOIN Department d ON e.dept_id = d.dept_id
WHERE e.salary > 70000;

-- PostgreSQL
EXPLAIN ANALYZE SELECT ...;

-- Output shows:
-- Join method used (nested loop / hash join / merge join)
-- Whether indexes were used
-- Estimated rows, cost, actual time

Query Execution Engine

The execution engine

1. Reads the chosen physical plan

2. Calls operators in pipeline fashion:

- Each operator reads from its inputs

- Produces output tuples one at a time (pipelining)

- No need to materialize intermediate results in memory

3. Returns final result set to the client

Pipelining

Scan → Select → Project → Join → Sort

Each operator passes tuples directly to the next

→ Reduces memory usage and disk I/O

Query Processing

What is Query Processing?

Step 1 — Parsing and Translation

SQL

Parse Tree

Relational Algebra

Step 2 — Relational Algebra Expression

Step 3 — Query Optimization

Step 4 — Physical Query Plan (Execution Plan)

Physical Join Algorithms

1. Nested Loop Join

2. Block Nested Loop Join

3. Index Nested Loop Join

4. Sort-Merge Join

5. Hash Join

EXPLAIN — Viewing Query Plans

Query Execution Engine

The execution engine

Pipelining

Study next in this module

Query Processing

What is Query Processing?

Step 1 — Parsing and Translation

SQL

Parse Tree

Relational Algebra

Step 2 — Relational Algebra Expression

Step 3 — Query Optimization

Step 4 — Physical Query Plan (Execution Plan)

Physical Join Algorithms

1. Nested Loop Join

2. Block Nested Loop Join

3. Index Nested Loop Join

4. Sort-Merge Join

5. Hash Join

EXPLAIN — Viewing Query Plans

Query Execution Engine

The execution engine

Pipelining

Study next in this module