Browse Prior Art Database

Extensible Design for Generating Alternative Join Sequences In a Relational Query Optimizer

IP.com Disclosure Number: IPCOM000100452D
Original Publication Date: 1990-Apr-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 2 page(s) / 91K

Publishing Venue

IBM

Related People

Lohman, GM: AUTHOR [+2]

Abstract

This article relates to a flexible method for developing an optimal plan to execute a relational query. Specifically, the method enumerates different orders in which the tables in a query may be joined and eliminates those orders that are unlikely to provide optimal execution plans. (Image Omitted)

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

Extensible Design for Generating Alternative Join Sequences In a Relational Query Optimizer

       This article relates to a flexible method for developing
an optimal plan to execute a relational query.  Specifically, the
method enumerates different orders in which the tables in a query may
be joined and eliminates those orders that are unlikely to provide
optimal execution plans.

                            (Image Omitted)

      Potential join orders are generated by the enumeration
generator.  It begins with single-table sets and, for set_size = 2,
3, ..., num_tables, inductively generates pairs of sets of tables
having part_size and set_size - part_size tables, where part_size &
min (comp_limit, floor(set_size/2)).

      The criteria by which certain orders are eliminated can be
extended or altered:
      a.   when building the optimizer, by adding or replacing the
modules which generate or filter potential join orders, or
      b.   when optimizing a particular query, by adjusting
user-provided parameters.  For example, the method includes default
criteria that:  (1) eliminate joins called "Cartesian products"
between any two sets of tables not having a "join predicate" that
references tables in both sets of tables, and (2) limit joins called
"composite inners" in which both operands to be joined are the result
of an earlier join, through the parameter comp_limit. These criteria
eliminate join orders that rarely produce optimal plans, thus
minimizing the number of potential execution plans to evaluate.
However, the method permits a user willing to pay for more thorough
optimization to adjust these criteria -- and thus the number of
potential execution plans -- through parameters specifying the degree
of optimization desired by the user for a given query.

      Note that in the above, a "join predicate" is generalized to
mean any predicate referencing columns from more than one table and
may involve any relational operator (not just "*") and any arithmetic
expressions.  It also includes predicates that may be deduced from
other equality predicates (*), even if not specified by the user.

      Specific examples of filters on two potentially joinable table
sets ts1 and ts2, include:
      1.   Disjointness (mandatory):  ts1  ts2 = d.
      2.   Dependenc...