Browse Prior Art Database

Adaptive Access Plan for Select Queries With Multiple Predicates

IP.com Disclosure Number: IPCOM000099329D
Original Publication Date: 1990-Jan-01
Included in the Prior Art Database: 2005-Mar-14
Document File: 5 page(s) / 206K

Publishing Venue

IBM

Related People

Lee, YH: AUTHOR [+2]

Abstract

A technique is described whereby an adaptive access plan algorithm is implemented for a relational query with multiple selection predicates. The plan uses indexes involved to measure the number of tuples qualifying each predicate. Then, an access path is chosen to minimize I/O cost and predicate evaluations are ordered to reduce CPU computation. The decisions are made progressively such that the overhead is minimized.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 30% of the total text.

Adaptive Access Plan for Select Queries With Multiple Predicates

       A technique is described whereby an adaptive access plan
algorithm is implemented for a relational query with multiple
selection predicates.  The plan uses indexes involved to measure the
number of tuples qualifying each predicate.  Then, an access path is
chosen to minimize I/O cost and predicate evaluations are ordered to
reduce CPU computation.  The decisions are made progressively such
that the overhead is minimized.

      In prior art, a query optimizer during compilation selects the
access plan with the minimum projected cost based on estimated
measures on relations.  Since estimates can deviate substantially
from their true values, the access plan chosen may be far from
optimal.  Under the proposed implementation, the compiler generates
an adaptive access plan that can progressively make access path
selection decisions based on information available at run time.  The
approach postpones the necessity to estimate unknown information
during compilation until run time when the information becomes
available or can be better estimated. This leads to the optimal
selection of an access plan.

      We now consider how to design an adaptive access plan for
selection of tuples from a relation R.  The query has a multiple
predicate of the form "R.Ai comparison-operator expression".  Assume
that an index exists on attribute Ai . The choices on access path is
to either sequentially scan through the whole relation and select the
qualified tuple or to use one or a combination of indexes on R.Ai to
make tuple selection and retrieval directly.

      Assume the data structure for the index model is a balanced
tree (B-tree).  Non-leaf nodes of the tree consist of pointers to
their direct descendants and the high key values of their
descendants.  Leaf nodes contain sets of (key,np(key), list of TIDs)
where TID links to the tuple with the key value key.  The field,
np(key), indicates the length of the TID list.  This field is
necessary to associate with each key since the TID list can have
variable length.  In addition, the leaf pages are linked together to
support sequential access of leaf nodes.  To search for tuples with a
particular key, an index scan is started from the root, ending with
the leaf node containing the key. Then, the corresponding tuples are
located using the associated TIDs.

      Assume a non-clustering index.  The performance of
non-clustering index scan depends on the number of tuples to be
retrieved.  It will be appropriate to measure that number and then
use it for decision making.  The progressive access plan described
below concentrates on how to make the selection between table scan
and non-clustering index scan during run time.  The predicate
expressions are first evaluated and are represented by either values
or ranges. The plan first starts with scanning the indexes to
calculate the number of qualified tuples.  ...