Query Processing

Query Processing includes translations on high level Queries into low level
expressions that can be used at physical level of file system, query optimization
and actual execution of query to get the actual result.
Block Diagram of Query Processing is as:

Detailed Diagram is drawn as:

It is done in the following steps:
 Step-1:
Parser: During parse call, the database performs the following checks-
Syntax check, Semantic check and Shared pool check, after converting
the query into relational algebra.
Parser performs the following checks as (refer detailed diagram):
1. Syntax check – concludes SQL syntactic validity. Example:
SELECT * FORM employee
Here error of wrong spelling of FROM is given by this check.
2. Semantic check – determines whether the statement is
meaningful or not. Example: query contains a tablename which
does not exist is checked by this check.
3. Shared Pool check – Every query possess a hash code
during its execution. So, this check determines existence of
written hash code in shared pool if code exists in shared pool
then database will not take additional steps for optimization
and execution.
Hard Parse and Soft Parse –
If there is a fresh query and its hash code does not exist in shared pool
then that query has to pass through from the additional steps known as
hard parsing otherwise if hash code exists then query does not pass
through additional steps. It just passes directly to execution engine (refer
detailed diagram). This is known as soft parsing.
Hard Parse includes following steps – Optimizer and Row source
generation.
 Step-2:
Optimizer: During optimization stage, database must perform a hard
parse atleast for one unique DML statement and perform optimization
during this parse. This database never optimizes DDL unless it includes
a DML component such as subquery that require optimization.
It is a process in which multiple query execution plan for satisfying a
query are examined and most efficient query plan is satisfied for
execution.
Database catalog stores the execution plans and then optimizer passes
the lowest cost plan for execution.
Row Source Generation –
The Row Source Generation is a software that receives a optimal
execution plan from the optimizer and produces an iterative execution
plan that is usable by the rest of the database. the iterative plan is the
binary program that when executes by the sql engine produces the result
set.
 Step-3:
Execution Engine: Finally runs the query and display the required
result.
 Relational Algebra Operations

Relational Algebra is a procedural query language. Relational algebra mainly

provides a theoretical foundation for relational databases and SQL. The main
purpose of using Relational Algebra is to define operators that transform one or
more input relations into an output relation. Given that these operators accept
relations as input and produce relations as output, they can be combined and used
to express potentially complex queries that transform potentially many input
relations (whose data are stored in the database) into a single output relation (the
query results). As it is pure mathematics, there is no use of English Keywords in
Relational Algebra and operators are represented using symbols.
Fundamental Operators
These are the basic/fundamental operators used in Relational Algebra.
1. Selection(σ)
2. Projection(π)
3. Union(U)
4. Set Difference(-)
5. Set Intersection(∩)
6. Rename(ρ)
7. Cartesian Product(X)
1. Selection(σ): It is used to select required tuples of the relations.
Example:
A B C

1 2 4

2 2 3

3 2 3

4 3 4

For the above relation, σ(c>3)R will select the tuples which have c more than 3.
A B C

1 2 4

4 3 4

Note: The selection operator only selects the required tuples but does not display
them. For display, the data projection operator is used.
2. Projection(π): It is used to project required column data from a relation.
Example: Consider Table 1. Suppose we want columns B and C from Relation R.
π(B,C)R will show following columns.
B C

2 4

2 3

3 4

Note: By Default, projection removes duplicate data.

3. Union(U): Union operation in relational algebra is the same as union operation
in set theory.
Example:

FRENCH
Student_Name Roll_Number

Ram 01

Mohan 02

Vivek 13

Geeta 17

GERMAN
Student_Name Roll_Number

Vivek 13

Geeta 17

Shyam 21

Rohan 25

Consider the following table of Students having different optional subjects in their
course.
π(Student_Name)FRENCH U π(Student_Name)GERMAN
Student_Name

Ram

Mohan

Vivek

Geeta

Shyam

Rohan

Note: The only constraint in the union of two relations is that both relations must
have the same set of Attributes.
4. Set Difference(-): Set Difference in relational algebra is the same set difference
operation as in set theory.
Example: From the above table of FRENCH and GERMAN, Set Difference is used
as follows
π(Student_Name)FRENCH - π(Student_Name)GERMAN

Student_Name

Ram

Mohan

Note: The only constraint in the Set Difference between two relations is that both
relations must have the same set of Attributes.
5. Set Intersection(∩): Set Intersection in relational algebra is the same set
intersection operation in set theory.
Example: From the above table of FRENCH and GERMAN, the Set Intersection is
used as follows
π(Student_Name)FRENCH ∩ π(Student_Name)GERMAN

Student_Name

Vivek

Geeta

Note: The only constraint in the Set Difference between two relations is that both
relations must have the same set of Attributes.
6. Rename(ρ): Rename is a unary operation used for renaming attributes of a
relation.
ρ(a/b)R will rename the attribute 'b' of the relation by 'a'.

7. Cross Product(X): Cross-product between two relations. Let’s say A and B, so

the cross product between A X B will result in all the attributes of A followed by
each attribute of B. Each record of A will pair with every record of B.
Example:

A
Name Age Gender

Ram 14 M

Sona 15 F

Kim 20 M

B
ID Course

1 DS

2 DBMS

AXB
Name Age Gender ID Course

Ram 14 M 1 DS

Ram 14 M 2 DBMS

Sona 15 F 1 DS

Sona 15 F 2 DBMS

Kim 20 M 1 DS

Kim 20 M 2 DBMS

Note: If A has ‘n’ tuples and B has ‘m’ tuples then A X B will have ‘ n*m ‘ tuples.
Layers of Query Processing
Query processing has 4 layers:
• Query Decomposition
• Data Localization
• Global Query Optimization
• Distribution Query Execution

Query Decomposition
The first layer decomposes the calculus query into an algebraic query on global
relations. The information needed for this transformation is found in the global
conceptual schema describing the global relations.
• Query decomposition can be viewed as four successive steps.
• Normalization
• Analysis
• Simplification
• Restructure
• First, the calculus query is rewritten in a normalized form that is suitable for
subsequent manipulation. Normalization of a query generally involves the
manipulation of the query quantifiers and of the query qualification by applying
logical operator priority.
• Second, the normalized query is analyzed semantically so that incorrect queries
are detected and rejected as early as possible. Techniques to detect incorrect
queries exist only for a subset of relational calculus. Typically, they use some sort of
graph that captures the semantics of the query.
•Third, the correct query (still expressed in relational calculus) is simplified.
One way to simplify a query is to eliminate redundant predicates. Note that
redundant queries are likely to arise when a query is the result of system
transformations applied to the user query. such transformations are used for
performing semantic data control (views, protection, and semantic integrity control).
•Fourth, an algebraic the calculus query is restructured as query. The traditional
way to do this transformation toward a "“better" algebraic specification is to start with
an initial algebraic query and transform it in order to find a "go

Query Processing Example

Query:

select salary
from instructor
where salary < 75000;

This query can be translated into either of the following relational-algebra

expressions:

 σsalary <75000(Πsalary (salary <75000(Πsalary ( instructor ))))

 Πsalary (σsalary <75000(Πsalary (salary <75000( instructor ))))

Data Localization
The input to the second layer is an algebraic query on global relations. The main
role of the second layer is to localize the query's data using data distribution
information in the fragment schema.
• This layer determines which fragments are involved in the query and transforms
the distributed query into a query on fragments.
• A global relation can be reconstructed by applying the fragmentation rules, and
then deriving a program, called a localization program, of relational algebra
operators, which then act on fragments.
Generating a query on fragments is done in two steps
• First, the query is mapped into a fragment query by substituting each relation by
its reconstruction program (also called materialization program).
• Second, the fragment query is simplified and restructured to produce another
"good" query.

Global Query Optimization

• The input to the third layer is an algebraic query on fragments. The goal of query
optimization is to find an execution strategy for the query which is close to optimal.
• The previous layers have already optimized the query, for example, by eliminating
redundant expressions. However, this optimization is independent of fragment
characteristics such as fragment allocation and cardinalities.
• Query optimization consists of finding the "best" ordering of operators in the query,
including communication operators that minimize a cost function.
• The output of the query optimization layer is a optimized algebraic query with
communication operators included on fragments. It is typically represented and
saved (for future executions) as a distributed query execution plan.

Distribution Query Execution

• The last layer is performed by all the sites having fragments involved in the query.
• Each sub query executing at one site, called a local query, is then optimized using
the local schema of the site and executed.

Query processing problem

Here are some common query processing problems:

 Parsing and Syntax Errors: One of the first problems in query processing is
parsing the user's query to ensure it has proper syntax. If there are syntax
errors, the query cannot be executed until they are fixed.

 Semantic Errors: Even if a query is syntactically correct, it may have

semantic errors. These errors involve issues like referencing non-existent
tables or columns, which can lead to incorrect results.
 Query Optimization: ADBMSs aim to optimize query performance by
choosing the best execution plan. The problem here is to find an efficient plan
from various alternatives, which is often an NP-hard problem.

 Cost Estimation: The query optimizer must estimate the cost of different
execution plans, including I/O, CPU, and memory costs. Inaccurate cost
estimates can lead to suboptimal query plans.

 Join Order and Join Algorithms: Deciding the order in which to join tables in
a multi-table query and choosing the right join algorithms (e.g., nested loop,
hash join, merge join) can be challenging. Poor choices can lead to slow
query execution.

 Index Selection: ADBMSs use indexes to speed up query processing.

Selecting the right indexes for a query is crucial, and choosing the wrong ones
can result in performance problems.

 Parallel Query Execution: ADBMSs often support parallel processing to

speed up query execution. Coordinating parallel tasks and ensuring load
balancing can be complex.

 Query Deadlocks: When multiple queries are accessing the same data
concurrently, deadlocks can occur if they block each other from completing.
Managing and resolving deadlocks is a challenge in query processing.

 Query Caching: Caching query results to improve performance can lead to

cache consistency and invalidation problems if not managed properly.

 Concurrency Control: Handling concurrent queries and ensuring data

consistency is another challenge. ADBMSs use various concurrency control
mechanisms, such as locking and timestamp-based protocols.

 Resource Management: Allocating system resources (e.g., memory, CPU)

efficiently among multiple queries is crucial to prevent resource contention
and bottlenecks.
  Query Performance Tuning: After execution, monitoring query performance
and optimizing poorly performing queries is an ongoing problem in ADBMS.

Characterization of query processors

Query Parsing:
Syntax Analysis: Query processors perform syntax analysis to check the query's
grammatical correctness. They ensure that the SQL query follows the proper syntax
rules.
Semantic Analysis: Beyond syntax, they also perform semantic analysis to validate
that tables, columns, and expressions in the query exist and are correctly
referenced.

Query Optimization:
Cost-Based Optimization: Many modern query processors use cost-based
optimization. They estimate the cost of different query execution plans and choose
the plan with the lowest cost. This involves estimating I/O, CPU, and memory usage
for various execution strategies.
Rule-Based Optimization: Some query processors use a rule-based approach,
applying a set of predefined rules to transform the query into a more efficient form.

Query Rewriting:
Transformations: Query processors can apply various query transformations, such
as predicate pushdown, join reordering, and subquery unnesting, to enhance query
performance.
Query Execution:
Physical Plan Generation: After optimization, query processors generate a physical
execution plan. This plan specifies how the query will be executed, including the
order of operations, join methods, and access methods.
Parallel Execution: In many DBMSs, query processors can execute parts of the
query in parallel to leverage multi-core and multi-processor systems, improving
query performance.

Index Selection:
Identifying Indexes: Query processors determine which indexes to use to access
data efficiently. They consider the query's filter conditions and join predicates.
Index Scan vs. Full Table Scan: Query processors decide whether to perform index
scans or full table scans based on cost estimates and data distribution.

Join Algorithms:

Join Type Selection: The choice of join algorithms (e.g., nested loop, hash join,
merge join) can significantly impact query performance. Query processors select
appropriate join methods based on data characteristics and cost estimates.
Query Caching:
Query Result Caching: Some query processors support caching of query results to
reduce the load on the system and improve response times for frequently
executed queries.
Concurrency Control:
Locking and Isolation: Query processors manage concurrency by implementing
locking mechanisms to ensure data consistency and isolation levels. They
coordinate access to shared resources when multiple queries run concurrently.
Query Execution Monitoring:
Resource Consumption: Query processors monitor resource consumption (CPU,
memory, I/O) and provide feedback for resource management and performance
optimization.
Query Performance Tuning:
Profiling and Optimization: DBAs and developers often use query processors to
analyze and optimize query performance, making adjustments as needed based on
execution statistics.
Error Handling:
Query Error Handling: Query processors detect and handle errors, providing
feedback and diagnostics to users when issues arise during query execution.
Query Compilation and Reuse:
Compilation: In some DBMSs, query processors compile queries into executable
code for faster execution.
Query Plan Cache:
Caching: Query processors maintain a cache of execution plans to reuse plans for
similar queries, reducing query processing overhead.
Query processing objectives
The primary objectives of query processing are as follows:

1. Correctness: The most fundamental objective of query processing is to

produce correct results. Queries should return data that accurately reflects the
current state of the database.

2. Efficiency: Query processing aims to execute queries in the most efficient

manner possible. This includes minimizing response time, reducing system
resource consumption (e.g., CPU and memory), and optimizing the execution
plan.

3. Optimization: Query optimization seeks to generate an execution plan that

minimizes the cost of executing the query. This involves selecting the best
access paths, join strategies, and other query processing techniques to
improve overall performance.

4. Transparency: Users should interact with the DBMS in a straightforward and

intuitive way. The query processor should handle complexities such as query
optimization behind the scenes, making it easy for users to write queries
without needing to understand the system's internal workings.

5. Flexibility: Query processing should support a wide range of query types and
operations. It should be capable of handling simple SELECT queries as well
as complex queries with multiple joins, subqueries, and aggregations.

6. Concurrency Control: In multi-user environments, query processing must

manage concurrent access to the database to ensure that transactions do not
interfere with each other. This includes implementing mechanisms like locking
and isolation levels.

7. Security: Query processing must enforce data access permissions and

security policies to prevent unauthorized access to sensitive information and
maintain data integrity.

8. Error Handling: Effective query processing includes robust error detection

and handling mechanisms. It should provide meaningful error messages to
 users and recover gracefully from errors without compromising data
consistency.

9. Resource Management: Query processing should efficiently allocate system

resources (e.g., CPU, memory, disk I/O) among competing queries to avoid
resource contention and bottlenecks.

10. Scalability: The query processor should be able to scale with the database
system's growth. It should be capable of handling an increasing number of
concurrent queries and data volumes without significantly degrading
performance.

11. Plan Reusability: Reusing execution plans can help improve performance
and reduce processing overhead. Query processing should support the
caching and reuse of query execution plans for frequently executed queries.

12. Adaptability: In dynamic environments, the query processor should adapt to

changing workloads and data distributions. It should continually reevaluate
query plans to accommodate evolving requirements.

13. Index and Data Structure Selection: Efficient query processing involves
selecting appropriate indexes and data structures to access and manipulate
data. The query processor should make intelligent choices based on query
requirements and data distribution.