SPECIAL IMPLEMENTATION CONSIDERATIONS - Database Design and Development: An Essential Guide for IT Professionals - page 405

How does the optimizer proceed to refine the query tree and make it more and
more efficient? In the heuristic approach, the optimizer applies heuristic rules to
convert the initial tree into a more efficient tree in each step. Therefore, this
approach is also known as rule-based optimization.
Here are a few examples of good heuristic practices for making an initial
relational algebraic expression or query tree more efficient:

• Perform selection operations first. This means moving selection operations
down the query tree. Again, apply the most restrictive selection operation
earliest.
• Combine a Cartesian product operation and a subsequent selection operation
and replace them with a join operation.
• Perform projection operation as early as possible. This means moving projec-
tion operation down the query tree.
• Compute repeating expressions once, store the result, and reuse the result.

Now, let us see how rules such as these are applied in the heuristic approach. Use
Figure 13-11 to consider the following query:

SELECT PatientName
FROM PATIENT P, TREATMENT T, DOCTOR D

WHERE DoctorName = “Ruby Ross”

AND D.DoctorID = T.DoctorID
AND P.PatientNo = T.PatientNo
AND DOB > 12DEC1952

Figures 13-17 and 13-18 illustrate the consecutive steps in the transformation
process of the query trees for this query using the heuristic approach.
Follow optimization steps 1 through 5. Note how, in step 1, the initial query tree
will produce a large result set from the PRODUCT operations on the PATIENT,
DOCTOR, and TREATMENT relations. Therefore, this initial query tree is very
inefficient. Note, however, that the query needs only one row from the DOCTOR
relation and only those PATIENT relation rows where the date of birth is after Dec.
31, 1952. So the next version of the query tree, in step 2, moves the SELECT
operations down to be executed first. A further improvement, in step 3, is achieved
by switching the order of these two SELECT operations because the SELECT
operation on DOCTOR relation will retrieve only one record. Proceed further and
examine the improvements in steps 4 and 5.

Cost-Based Optimization

In the heuristic approach, the optimizer applies a number for rules to arrive at the
optimal query tree for execution. The optimizer selects the appropriate rules for a
particular query and applies the rules in the proper sequence as the process of query
tree transformation continues. At the end of each step when a more efficient query
tree emerges, you do not know exactly how much better the newer version of the