Browse Prior Art Database

Full Exploitation of Query Selection Via Range Manipultion

IP.com Disclosure Number: IPCOM000114989D
Original Publication Date: 1995-Feb-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 6 page(s) / 212K

Publishing Venue

IBM

Related People

Bestgen, RJ: AUTHOR [+10]

Abstract

Methods to fully exploit selection criteria to improve query performance are disclosed. Selection operands and predicates are organized and analyzed to eliminate redundant criteria, completely utilize one or more indices, improve transitive closure, make query cost estimation more accurate, and improve join implementation.

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

Full Exploitation of Query Selection Via Range Manipultion

      Methods to fully exploit selection criteria to improve query
performance are disclosed.  Selection operands and predicates are
organized and analyzed to eliminate redundant criteria, completely
utilize one or more indices, improve transitive closure, make query
cost estimation more accurate, and improve join implementation.

      By decomposing database query selection (e.g., WHERE clause in
SQL) into ranges based on selection operands (e.g., columns), complex
selection can reduced to simple, readily usable selection.  The
solution is to transform the query selection into a series of ranges
based on predicates.

      The first step is to build a list of potential ranges within
the query selection.  For example, WHERE (COL1=10 AND COL2=20) OR
(COL1=30 AND COL2=40) would have two potential ranges:
                   Element(s)   Lo Bound(s)  Hi Bound(s)
  range 1  ===>    COL1 COL2     10 20        10 20
  range 2  ===>    COL1 COL2     30 40        30 40

      A range consists of elements and element bounds.  A bound is
further defined as a low bound and a high bound and is the lower
and/or upper limit, respectively, of the value(s) contained in the
element that will satisfy that part of the query selection.  For
predicates where the operands are both columns, a range is generated
with two elements, the first where the first column is the element
and the second is the bound and the second where the second column is
the element and the first is the bound.  Once the ranges are
generated, two things become apparent:
  o  Each range is ORed with each other range(s)
  o  Each element (column/bound combination) in a particular range
      is ANDed with every other element in that range.

      Using the following rules, these ranges can be used to build
multiple combinations of isolatable ranges:
  1.  At least one element must be chosen from each and every range
  2.  More than one element may be chosen from each range

      Using these two rules, the following combinations of isolatable
ranges can be implied.  Each entry that makes up a particular
combination is a range and is, therefore, logically ORed with the
other range in the combination.  Each combination may be used by
itself or in conjunction with other combinations to end up with the
best possible result.
  Combination  element(s)      low bound(s)     high bound(s)
      1          COL1             10                10
        (or)     COL1             30                30
      2          COL1             10                10
        (or)     COL2             40                40
      3          COL2             20        ...