Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Adaptive Join Algorithm

IP.com Disclosure Number: IPCOM000101031D
Original Publication Date: 1990-Jun-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 5 page(s) / 189K

Publishing Venue

IBM

Related People

Lee, Y: AUTHOR [+2]

Abstract

An adaptive join algorithm is described to reduce the cost of join operation. First, the values of the joining attributes and the number of tuples of each joining relation involved in the resultant relation are identified by joining the indices. Then, proper join method and access method are selected. The proposed algorithm provides significant performance improvement over conventional approaches.

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

Adaptive Join Algorithm

       An adaptive join algorithm is described to reduce the
cost of join operation.  First, the values of the joining attributes
and the number of tuples of each joining relation involved in the
resultant relation are identified by joining the indices.  Then,
proper join method and access method are selected.  The proposed
algorithm provides significant performance improvement over
conventional approaches.

      Here we construct an adaptive access plan for the two-way join
operation to illustrate the concept of progressively making query
evaluation decisions as more information is unveiled during the
process of executing the access plan.  It is assumed that indexes
exist on the join attribute for both relations.  The join plan is
based on an evaluation principle and starts with joining the indexes
without actually retrieving the matching tuples. Information, such as
the indexes of matching tuples, the cardinality of resultant relation
and the number of tuples in each joining relation, satisfying the
join predicate, is first  obtained.  Then, a proper join algorithm
and access path can be chosen to get the join result.  We shall
present the evaluation principle of the approach first followed by
the details of the algorithm.

      A 2-way equi-join operation on relations R1 and R2 is
considered.  The equi-join operation on attributes A of R1 and B of
R2 is denoted as R1 -A = B-R2 .  It is assumed that both indexes,
either clustering or

                            (Image Omitted)

 nonclustering, on R1 .A and R2 .B exist.  Also, we let
fA(Ri) and sA=a(Ri) denote the projection of relation Ri onto
attribute A and the set of tuples in Ri satisfying predicate A = a,
respectively.  For each relation Ri and its attribute A, denoted as
Ri .A, we define SiA = {(a,k) ¯ a   fA(Ri), k=šsA=a(Ri )š} where
šsA=a (Ri )š is the number of occurrences of value "a" in Ri .A.  Si
Acan be viewed as a relation consisting of two attributes: attribute
A and a count attribute, i.e., each tuple provides a distinct value
appeared in attribute A of Ri and the number of times it occurred.
As in the B-tree implementation of index, the information required to
construct Si A is embedded in the leaf nodes of the index on Ri .A.
Define the relation T12  AB = S1 A -A = B-S2 B . T12 AB
identifies the tuples from R1 (R2) which have at least one matching
tuple in R2 (R1 ) in the join operation.  The attribute B of T12  AB
can be ignored as it is identical to T12  AB .A.  To distinguish the
count attributes of T12  AB , we use K1 and K2 for count attributes
obtained from S1 A and S2 B , respectively.  Based on T12  AB , we
can partition Ri into two relations: Ri ' and Ri ", where Ri ' =
{t-t Ri , t.A (or t.B)    fA (T12  AB )} and Ri " = Ri
- Ri '.  In addition, we define an integer di as the summation of
t.Ki for all t     T12  AB .  It is easy to show that Ri '-A
= B-R2 ' =...