QUERY PROCESSING
1. Introduction to Query Processing
• Definition:
Query processing is the process of converting a high-level query (e.g., SQL) into a sequence
of low-level instructions that the database can execute efficiently.
• Importance:
o Ensures correctness of results.
o Optimizes resource usage (CPU, memory, and I/O).
o Reduces query execution time.
Example:
SELECT * FROM students WHERE age > 20;
ID Name Age Department
1 Alice 24 CSE
2 Bob 22 ECE
3 Charlie 25 MECH
4 Diana 20 CSE
5 Edward 23 EEE
2. Steps in Query Processing
Step 1: Query Parsing and Translation
• Purpose: Verify and transform the query into an internal form.
• Tasks:
o Syntax Analysis (Parsing): Ensures the query is grammatically correct (e.g., no typos).
Example: SELECT* frm students – frm spelling mistake, so error.
o Semantic Analysis: Checks for logical validity (e.g., table/column existence).
SELECT age FROM teachers – If teachers is not there, it shows error
o Output: An intermediate representation like a parse tree or query graph.
Step 2: Query Optimization
• Purpose: Improve the efficiency of query execution.
• Types of Optimization:
1. Logical Optimization: Focuses on refining the query structure:
▪ Simplifying conditions.
▪ Decomposing complex queries into smaller, manageable parts.
▪ Example: Redundant Filters
Query:
SELECT * FROM students WHERE age > 20 AND age > 18;
ID Name Age Department
1 Alice 24 CSE
2 Bob 22 ECE
3 Charlie 25 MECH
4 Diana 18 CSE
5 Edward 23 EEE
The condition age > 18 is already satisfied by age > 20.
The query can be simplified to:
SELECT * FROM students WHERE age > 20;
2. Physical Optimization: Selects the most efficient way to execute the query:
▪ Choosing the best join algorithms (e.g., Nested Loop, Hash Join).
▪ Deciding whether to use indexes or perform full table scans.
• Key Considerations:
o Cost estimation based on factors like disk I/O, CPU usage, and memory utilization.
Step 3: Query Execution Plan
• Purpose: Create a sequence of operations for query execution.
• Execution Plan: A step-by-step roadmap detailing:
o Which operations to perform (e.g., joins, filters).
o How to retrieve data (e.g., using indexes or scanning tables).
• Representation: Usually visualized as a tree, with nodes as operations and edges as data
flow.
Example:
SELECT name
FROM students
WHERE age > 20
AND dept_id = 101;
→ tree representation of query
π(name)
σ(age > 20 AND dept_id = 101)
Students
Step 4: Query Execution
• Purpose: Execute the steps in the query execution plan and produce results.
• Key Operations:
o Data Retrieval: Fetch data from storage (disk or memory).
o Processing: Apply operations like filtering, sorting, and joining.
• Result Delivery: Return the processed data to the user or application.
--------------------------------------------------------------------------------------------------------------------------------------
Example:
Query:
SELECT * FROM students WHERE age > 20;
1. Initial Table (students)
ID Name Age Department
1 Alice 19 CSE
2 Bob 22 ECE
3 Charlie 25 MECH
4 Diana 20 CSE
5 Edward 23 EEE
2. Step-by-Step Query Processing
Step 1: Parsing
• SQL query is checked for syntax and semantic errors.
• Example:
o Query: SELECT * FROM students WHERE age > 20;
▪ Syntax: Correct
▪ Semantic: Valid table and column names (students, age).
Step 2: Logical Optimization
• Logical changes are made to simplify or improve the query:
o Example: The condition age > 20 is kept as-is because it cannot be simplified further.
• Intermediate query remains:
SELECT * FROM students WHERE age > 20;
Step 3: Physical Optimization
• Decide the best method to fetch data:
o Index Use: If there’s an index on the age column, DBMS will use it to filter rows.
Syntax:
CREATE INDEX idx_columnname ON tablename(columnname);
Example: CREATE INDEX idx_age ON students(age);
o Full Table Scan: If no index exists, DBMS will scan the entire table.
Step 4: Query Execution
• Filter rows where age > 20.
• Retrieve all columns for the matching rows.
3. Final Output
After executing the query, the result is:
ID Name Age Department
2 Bob 22 ECE
3 Charlie 25 MECH
5 Edward 23 EEE
3. Key Components in Query Processing
1. Query Processor: Manages parsing, optimization, and execution.
2. Storage Manager: Retrieves and stores data during execution.
3. Execution Engine: Executes the query as per the execution plan.
4. Optimization Techniques
1. Use of Indexes:
o Avoid full table scans when possible.
2. Join Order Optimization:
o Reorder joins to minimize intermediate results.
3. Predicate Pushdown:
o Apply filters early to reduce unnecessary data.
4. Partition Pruning:
o Skip irrelevant partitions in partitioned tables.
5. Challenges in Query Processing
• Handling complex queries with multiple joins or subqueries.
• Balancing trade-offs between query speed and resource usage.
• Managing large-scale distributed or parallel queries efficiently.