Databases Reference
In-Depth Information
= read TEMP5
= 13.
In summary, the total cost of answering the query using this approach is as follows:
Number of block accesses for the query (option 2A)
= 2 + 261 + 2 + 97 + 23 + 13
= 398.
We now compa re the two approaches:
Block Accesses
Option 1A
6,240 executing joins first
Option 1B
398 executing joins last
It is clearly seen that the use of table reduction techniques (early selections and pro-
jections) has the potential of greatly reducing the I/O time cost of executing a query.
Although in this example indexes were not required, in general they can be very useful
to reduce I/O time further.
3.4
Query Execution Plan Development
A query execution plan is a data structure that represents each database operation (selec-
tions, projections, and joins) as a distinct node. The sequence of operations in a query
execution plan can be represented as top down or bottom up. We use the bottom-up
approach, and Figures 3.1 and 3.2 are classic examples of the use of query execution
plans to denote possible sequences of operations needed to complete SQL queries. An
SQL query may have many possible execution sequences, depending on the complexity
of the query, and each sequence can be represented by a query execution plan. Our goal
is to find the query execution plan that finds the correct answer to the query in the least
amount of time. Since the optimal solution to this problem is often too difficult and
time consuming to determine relative to the time restrictions imposed on database que-
ries by customers, query optimization is really a process of finding a “good” solution
that is reasonably close to the optimal solution, but can be quickly computed.
A popular heuristic for many query optimization algorithms in database systems
today involves the simple observation from Section 3.3 that selections and projections
should be done before joins because joins tend to be by far the most time-costly opera-
tions. Joins should be done with the smallest segments of tables possible, that is, those
segments that have only the critical data needed to satisfy the query. For instance in
Example Query 3.1, the supplier records are requested for suppliers in New York, which
