Optimization of Queries with Conjunction of Predicates

Abstract

A method to optimize the access at the objects of a relational database is through the optimization of the queries. This article presents an approach of the cost model used in optimization of Select-Project-Join (SPJ) queries with conjunction of predicates and proposes a join optimization algorithm named System RO-H (System Rank Ordering Heuristic). The System RO-H algorithm for optimizing SPJ queries with conjunction of predicates is a System R Dynamic Programming algorithm that extends optimal linear join subplans using a rank-ordering heuristic method as follows: choosing a predicate in ascending order according to the h-metric, where the h-metric depends on the selectivity and the cost per tuple of the predicate, using an expression with heuristic constants.
The System Rank-Ordering Heuristic algorithm finds an optimal plan in the space of linear left deep join trees. The System RO-H algorithm saves not a single plan, but multiple optimal plans for every subset, one for each distinct such order, termed interesting order. In order to build an optimal execution plan for a set S of i relations, the optimal plan for each subset of S, consisting of i-1 relations is extended, using the Lemma based on a h-metric for predicates. Optimal plans for subsets are stored and reused. The optimization algorithm chooses a plan of least cost from the execution space.