Query Processing
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.
Eg : Delete*from employee where id=’1’;
Basic Steps in Query Processing
1) Parsing and Translation
Translates the query into its internal form using relational algebra.
e.g. SELECT * FROM employee → π∗(employee)
This step has three sub-checks:
Syntax Check — Verifies the query is written correctly.
e.g. SELECT * FORM employee → error, because FORM should be FROM.
Semantic Check — Verifies the query makes logical sense.
Checks if tables/columns exist, data types are compatible, and operations are valid.
e.g. SELECT * FROM employee WHERE salary = 'hello' → error, because salary
is numeric, not a string.
Shared Pool Check — Checks if this query was executed before.
If yes → Soft Parse: reuses the existing execution plan (faster, skips optimization).
If no → Hard Parse: parses and optimizes from scratch, generates a new execution
plan.
2) Query Optimization
Among all equivalent evaluation plans chooses the one with lowest cost.
Cost is estimated using statistical information from the database catalog
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
Example
A ) Join first, then filter: σ dept='HR' (Employee ⋈ Department)
B ) Filter first, then join: σ dept='HR' (Employee) ⋈ Department
· Both queries return the same result, but the second one is cheaper because we
reduce the size of Employee before the join, so the join operates on fewer tuples.
· Project Early Drop columns you don't need early on before any join
· Always reduce your data as early as possible filter, trim, then join.
3) Evaluation
The query-execution engine takes a query-evaluation plan,
executes that plan, and returns the answers to the query.
Why Optimize Queries?
A query can often be written in multiple ways that return the same result, but with very
different performance. Without optimization, the database may execute an expensive
plan — like joining millions of rows before filtering — when a cheaper one exists.
Advantages of Query Optimization
Disk I/O is slow — reducing unnecessary reads directly speeds up execution
Large tables are common — even small inefficiencies scale badly with data size
Resources are shared — a poorly written query can slow down the entire database for
other users
The goal is to get the same answer, but with the least amount of work.
Evaluation of Query Processing Cost
Query cost is mainly based on disk I/O operations, since disk access is the slowest
part.
1. File Scan (Table Scan)
· Reads entire table row by row
Cost Formula:
𝐶𝑜𝑠𝑡 = 𝑁𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝐵𝑙𝑜𝑐𝑘𝑠 × (𝑡 𝑇 + 𝑡𝑆 )Cost=Number of Blocks×(tT+tS)
Where:
· 𝑡𝑇tT= time to transfer block
· 𝑡𝑆tS= time to search block
2. Index Scan
· Uses an index to directly locate required rows
Cost Formula:
𝐶𝑜𝑠𝑡 = (ℎ𝑖 + 1) × (𝑡𝑇 + 𝑡𝑆 )Cost=(hi+1)×(tT+tS)
Where:
· ℎ𝑖hi= height of index
· + 1+1 = access to actual data block
File Scan vs Table Scan
Aspect File Scan Table Scan
Scanning all data in a file stored on Scanning all rows of a database
Definition
disk table
Perspective File system / storage level Database / relational level
Terminology Used in lower-level storage Commonly used in DBMS and
Usage discussions SQL context
Data Data treated as rows and
Data treated as blocks in a file
Representation columns in a table
Meaning in
Reads entire file sequentially Reads entire table sequentially
Practice