Integration into a Query Optimiser

  Let us now consider the question where the optimisation process, as presented in the previous section, would be integrated into a query optimiser. To that end, we have to look at the tasks that are performed by a query optimiser. As a starting point we have to imagine that a query has been translated into an algebraic expression which itself corresponds to a operation tree or query tree. This query tree describes the order in which the individual operations are processed and on which inputs. See figure 6.2 for an example of such a tree. A query optimiser then tries to transform an initial query tree into an equivalent one, i.e. one that yields the same result, but one that implies less costs. There are various possibilities at various levels to do this. Essentially, there are three stages of optimisation [Graefe, 1993]:

1.

Semantic query optimisation
At this stage, an optimiser derives, for example, implied predicates using transitivity and other algebraic properties or integrity constraint. From selection conditions, such as , it can, for example, derive that r.A = s.A which could possibly help to simplify the original algebraic expression and therefore also the corresponding tree. Another example of semantic query optimisation is to use the implicit fact that an interval's startpoint ts cannot lie beyond its endpoint te, i.e. ,for simplifying an algebraic expression.

2.

Logical query optimisation
At the logical level, the optimiser considers transformations of the query expressions to other, equivalent expressions. The join operation, for example, is commutative and associative [Ryan and Smith, 1995]. Therefore it is  

(22)

Logical query optimisation also considers statistical profiles of the relation, selectivities of selection conditions and estimates sizes of intermediate results from that. In general, it is beneficial to avoid huge intermediate results. This is an important criterion, for example, in order to decide whether the left or the right expression in (6.1) imposes less costs.

3.

Physical query optimisation
Finally, at the physical level, an optimiser maps a query tree to the optimal (or at least a near optimal) combination of execution algorithms. Typically, there is a variety of algorithms for each operation on offer. In order to select the most appropriate algorithm, an optimiser considers whether it can use indices, exploit sort-orders, optimise resource allocation etc. In chapters 3 and 4, we have already noted that the selectivity factor is an important characteristic for deciding on the most appropriate join algorithm. At this stage, the optimiser also employs cost models and performs cost calculations.

We now want to look at the integration of the optimisation process of figure 6.1 into an optimiser as it has been described above. From the discussion it becomes obvious that it can form an integral part of the physical optimisation level. The optimisation that we propose can answer two questions in that context:

• Should a temporal join (as it appears in some query) be processed by partitioning over the interval timestamps? Does it achieve less costs than a sort-merge or any other join technique? This could be answered by comparing the cost predictions for partitioned join processing with those of the other techniques. This would require cost models for these other techniques that are based on the same assumptions as those made in chapter 8. It is not our intention to provide these additional cost models in this thesis. But we nevertheless do want to point to this possibility which could be elaborated in future research.
• If the temporal join is to be processed by partitioning over the interval attribute, our optimisation also provides a decision on a suitable, near-optimal partition.