Query Processing in DBMS
Query Processing is the activity performed in extracting data from the database. In
query processing, it takes various steps for fetching the data from the database.
The steps involved are:
1. Parsing and translation
2. Optimization
3. Evaluation
The steps involved in query processing in dbms are summarised below :
Thus, we can understand the working of a query processing in the below-
described diagram:
Suppose a user executes a query. As we have learned that there are various
methods of extracting the data from the database. In SQL, a user wants to fetch the
records of the employees whose salary is greater than or equal to 10000. For doing
this, the following query is undertaken:
select emp_name from Employee where salary>10000;
Thus, to make the system understand the user query, it needs to be translated in
the form of relational algebra. We can bring this query in the relational algebra
form as:
o σsalary>10000 (πsalary (Employee))
o πsalary (σsalary>10000 (Employee))
After translating the given query, we can execute each relational algebra operation
by using different algorithms. So, in this way, a query processing begins its working.
Evaluation
For this, with addition to the relational algebra translation, it is required to
annotate the translated relational algebra expression with the instructions used for
specifying and evaluating each operation. Thus, after translating the user query,
the system executes a query evaluation plan.
Query Evaluation Plan
o In order to fully evaluate a query, the system needs to construct a query
evaluation plan.
o The annotations in the evaluation plan may refer to the algorithms to be used
for the particular index or the specific operations.
o Such relational algebra with annotations is referred to as Evaluation
Primitives. The evaluation primitives carry the instructions needed for the
evaluation of the operation.
o Thus, a query evaluation plan defines a sequence of primitive operations
used for evaluating a query. The query evaluation plan is also referred to
as the query execution plan.
o A query execution engine is responsible for generating the output of the
given query. It takes the query execution plan, executes it, and finally makes
the output for the user query.
Optimization
o The cost of the query evaluation can vary for different types of queries.
Although the system is responsible for constructing the evaluation plan, the
user does need not to write their query efficiently.
o Usually, a database system generates an efficient query evaluation plan,
which minimizes its cost. This type of task performed by the database system
and is known as Query Optimization.
o For optimizing a query, the query optimizer should have an estimated cost
analysis of each operation. It is because the overall operation cost depends
on the memory allocations to several operations, execution costs, and so on.
Finally, after selecting an evaluation plan, the system evaluates the query and
produces the output of the query.
Measures of Query Cost in DBMS
In the previous section, we understood about Query processing steps and
evaluation plan. Though a system can create multiple plans for a query, the chosen
method should be the best of all. It can be done by comparing each possible plan
in terms of their estimated cost. For calculating the net estimated cost of any plan,
the cost of each operation within a plan should be determined and combined to
get the net estimated cost of the query evaluation plan.
The cost estimation of a query evaluation plan is calculated in terms of various
resources that include:
o Number of disk accesses cost
o Execution time taken by the CPU to execute a query
o Communication costs in distributed or parallel database systems.
CPU Cycle
CPU cost is difficult to calculate.
Normally CPU speed is faster than disk speed.
CPU cost is relatively lower than disk cost.
Distributed or Parallel database systems
Primarily it’s considered with Distributed or Parallel database systems.
Disk Accesses Cost
Basic measures of disk access cost :-
Number of seek
Number of block read
Number of block write
To get the final result, these numbers to be multiplied by the average time required to
complete the task. Hence, it can be written as follows;
Query cost =
(number of seek operations X average seek time)
+(number of blocks read X average transfer time for reading a block)
+(number of blocks written X average transfer time for writing a block)
tT – time to transfer one block
tS – time for one seek
Cost for b block transfers plus S seeks
o b * tT + S * tS
The Formula of query cost = b * tT + S * tS
We ignore CPU costs for simplicity
o Real systems do take CPU cost into account
