Browse Prior Art Database

Adaptive Path Selection for Query With Input Variables

IP.com Disclosure Number: IPCOM000036179D
Original Publication Date: 1989-Sep-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 3 page(s) / 15K

Publishing Venue

IBM

Related People

Gan, C: AUTHOR [+3]

Abstract

A technique is described wherby a new approach to access path selection for queries with input variables is provided. Rather than one pre- selected fixed access path, this proposed approach preselects a number of optimal access paths with one of these adopted for execution based on the run-time input variable values. Under the proposed approach, the selectivity of predicates where only constants are involved is estimated by query optimizer as the traditional approach. However, for a predicate where input variable is involved, we estimate the selectivity after the value of variable is determined instead of using default value.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 50% of the total text.

Page 1 of 3

Adaptive Path Selection for Query With Input Variables

A technique is described wherby a new approach to access path selection for queries with input variables is provided. Rather than one pre- selected fixed access path, this proposed approach preselects a number of optimal access paths with one of these adopted for execution based on the run-time input variable values. Under the proposed approach, the selectivity of predicates where only constants are involved is estimated by query optimizer as the traditional approach. However, for a predicate where input variable is involved, we estimate the selectivity after the value of variable is determined instead of using default value.

In prior art using a query compilation approach, query optimizer estimates the execution costs of all access paths available. Then, the access path with the minimum cost is selected and transformed into access structure for execution. To simplify the estimation of cost, the assumptions of uniformity and independence of attribute values are usually adopted. For instance, the attribute selectivity, which is used to determine the expected fraction of tuples taking on a specific attribute value, is commonly defined as the reciprocal of the number of distinct values taken by an attribute.

Consider the following query in which Screw#X is a variable to be determined by the executing program or input by a user. SELECT FROM < SP.name > WHERE < SP.Parts / Screw#X > The query otimizer has no knowledge about the value of Screw#X during compilation. To describe the selectivity of the above predicate, a default value must be used, e.g., 1/3 in DB2 and SQL/DS. Note that there is no significant meaning of this number other than the hypothesis that less than half of the tuples satisfies the predicate. In fact, the number of tuples selected during query execution can vary substantially for different values of Screw#X. The usage of a default selectivity, certainly, cannot lead to the optimal access path selection and often causes significant performance penalties, especially in a large database environment.

We consider a query with predicates which is of the form SELECT from R where P1,P2,...Pm where R is a relation. Predicate Pi is a Boolean function on an attribute of R, i.e. R.Ai, and is represented as R.Ai operator expression. The expression could be a constant, an input variable or mathematical expression. With no loss of generality, we assume that P1,P2,...,Pn involve either an input variable or mathematical expression, whereas Pn+1,...,Pm have only constants in their expressions. We also assume that an index on R.Ai exists and give no consideration of the predicate where no index is provided on the involved attribute.

Tuples of R can be retrieved through index scan or table scan. When an index on R.Ai is provided, the index scan leads to access tuples satisfying the predicate Pi . This scan, called selective index scan, could be very efficient if the selectivity of P...