Query Processing:
Overview
By Nivedh Krishna
What is a query
In SQL, a query is a request for information or an action to
be performed on data stored in a database. It is typically
written in Structured Query Language (SQL) and can be used to
retrieve, insert, update, or delete data
Example
Insert into employee values(1,’Nivedh’,’it’,’35000’);
Update employee set salary = ‘40000’ where id =’1’;
Delete*from employee where id=’1’;
Basic Steps in Query Processing
1. Parsing and translation
2. Optimization
3. Evaluation
Parsing and translation
• Translate the query into its internal form. This is then
translated into relational [Link] checks syntax, verifies
relations
e.g. SELECT * FORM employee
• Here, the error of the wrong spelling of FROM is given by this
check.
• Semantic check and Shared pool check comes afterwards
Semantic Check
This is a core part of parsing. It ensures the query is logically
valid—like checking if tables or columns exist, permissions are
correct, and operations are meaningful. It’s about understanding the
meaning of the query before moving forward.
Shared Pool Check
This is more about efficiency and optimization. After the query is
parsed (syntax and semantics are verified), the database checks the
shared pool to see if the query has been executed before. If it has,
the database can skip re-optimizing and reuse the existing execution
plan. This step bridges parsing and optimization, as it decides
whether to proceed with a full optimization (hard parse) or reuse a
plan (soft parse).
• Hard Parse: When a query is parsed, optimized, and a new execution
plan is generated from scratch—happens when the query isn’t found in
the shared pool.
• Soft Parse: When the query’s execution plan is reused from the shared
pool, skipping optimization—faster and more efficient.
Query Optimization
• Among all equivalent evaluation plans choose
the one with lowest cost.
• Cost is estimated using statistical information from the database
catalog
e.g.. number of tuples in each relation, size of tuples, etc.
Evaluation
• The query-execution engine takes a query-evaluation plan,
• executes that plan, and returns the answers to the query.
Relational algebra symbols
• Selection (σ)
• Projection (π)
• Union (∪)
• Set Difference (−)
• Cartesian Product (×)
• Rename (ρ)
• Intersection (∩)
• SELECT name, salary FROM employees WHERE department = 'HR';
• π(name, salary)(σ(department = 'HR')(employees))
Query Optimization
A single query can be executed in many ways. Query optimization helps
choose the most efficient plan by comparing different execution methods
to find the one with the lowest cost.
Importance: The goal of query optimization is to reduce the system
resources required to fulfill a query, and ultimately provide the user
with the correct result set faster.
First, it provides the user with faster results, which makes the
application seem faster to the user.
Secondly, it allows the system to service more queries in the same
amount of time, because each request takes less time than
unoptimized queries.
Thirdly, query optimization ultimately reduces the amount of wear on
the hardware (e.g. disk drives), and allows the server to run more
efficiently (e.g. lower power consumption and memory usage).
Equivalence Rules in Query Optimization
• Rules that let the optimizer rewrite a query differently — same
result, but faster.
Select Early Filter rows before joining tables
• Join first, then filter: σ dept='HR' (Employee ⋈ Department)
• Filter first, then join: σ dept='HR' (Employee) ⋈ Department
• Project Early Drop columns you don't need early on π name,
salary (Employee) before any join
• Join Reordering Join smaller tables first If Department is
smaller than Employee, join it first
Always reduce your data as early as possible filter, trim, then
join.
Approaches To Access Data
File Scan (Table Scan)
A file scan, also called a sequential scan or table scan, means the
database reads every row in a table to find the data you’re looking for.
It’s like reading every page of a book to find a single sentence.
it happens When there’s no index on the column used in the WHERE
[Link] the query needs to scan a large portion of the table (e.g.,
retrieving most rows).
Pros:
Simple and [Link] be efficient for small tables or when
retrieving a large fraction of rows.
Cons:
Very slow for large tables, as it reads every [Link]-intensive,
especially for tables with millions of rows.
Example:
SELECT * FROM customers WHERE name like %Z;
Index Scan
An index scan uses an index (like a book’s index) to quickly locate the
rows that match your query. Instead of reading every row, the database
jumps directly to the relevant data.
it happens: When there’s an index on the column used in the WHERE, JOIN,
or ORDER BY clause.
When the query retrieves a small fraction of rows.
Pros:
Much faster than a file scan for large tables. Efficient for queries that
filter or sort data.
Cons:
Indexes consume additional storage [Link], updates, and deletes
can slow down slightly because indexes need to be updated.
Example:
SELECT * FROM customers WHERE customer_id = 1001
File Scan Cost
A file scan reads every block of the table sequentially.
Cost Formula:
Total Cost = (Number of Blocks in Table) × (t_T + t_S)
t_T: Time to transfer a block from disk to memory.
t_S: Time to search a block in memory.
Index Scan Cost
An index scan uses an index to locate the relevant rows, avoiding a
full table scan.
Total Cost = (h_i + 1) × (t_T + t_S)
h_i: Height of the index (number of levels from root to leaf).
t_T: Time to transfer a block from disk to memory.
t_S: Time to search a block in memory.
The +1 accounts for accessing the actual data block after reaching the
leaf node.
Design better indexes: Create indexes on columns frequently used in WHERE,
JOIN, or ORDER BY clauses.
Write efficient queries: Avoid full table scans by ensuring your queries
can use indexes.
Analyze execution plans: Recognize when a query is performing a file scan
and optimize it by adding indexes or rewriting the query.
Optimized Query
SELECT * FROM employees WHERE employee_id = 1001;
Non optimized Query
SELECT * FROM employees WHERE name = 'John Doe';
More access methods or search strategies for querying data.
A3: Hash Index Scan A4: Clustered Index Scan
Uses a hash index for exact-match lookups (e.g., WHERE Scans a clustered index (where data is physically ordered
id = 101). by the index key).
Example: Primary key lookups in SQL Server.
A5: Covering Index Scan A6: Multi-Column Index Scan
Retrieves all required columns from the index itself, Uses composite indexes (indexes on multiple columns).
avoiding table access. Example: WHERE (col1, col2) = (value1,
Example: SELECT indexed_col1, value2).
indexed_col2 FROM table WHERE
indexed_col1 = value.
A7: Bitmap Index Scan A8: Nested Loop Join
Uses bitmap indexes for low-cardinality columns (e.g., Joins tables by looping through rows of one table and
gender, status). matching them with another.
Example: WHERE status = 'active'.
A9: Merge Join A10: Hash Join
Joins sorted tables by merging them (efficient for large, Joins tables using a hash table (great for large, unsorted
sorted datasets). datasets).
So finally Your SQL Query
↓
1. Parsing (Syntax Check)
↓
2. Query Rewriting (Relational Algebra)
↓
3. Query Optimization (Equivalence Rules + Cost-Based)
↓
4. Execution Plan Generation
↓
5. Execution (Fetch and Return Results)