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

Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins

IP.com Disclosure Number: IPCOM000111065D
Original Publication Date: 1994-Feb-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 2 page(s) / 131K

Publishing Venue

IBM

Related People

Chen, MS: AUTHOR [+2]

Abstract

Disclosed is the concept of segmented right-deep trees to exploit inter-operator parallelism for the execution of pipelined hash joins in a multiprocessor-based database system. A query plan is usually compiled into a tree of operators, called query execution tree, where a leaf node represents an input relation and an internal node represents the resulting relation from joining the two relations associated with its two child nodes. Inter-operator parallelism means different joins are executed in parallel by different clusters of processors. For exploring inter-operator parallelism, there are three categories of query trees: left-deep trees, right-deep trees, and bushy trees. In the context of hash joins, the left and right child nodes of an internal node represent the inner and outer relations of the join, respectively.

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

Using Segmented Right-Deep Trees for the Execution of Pipelined Hash
Joins

      Disclosed is the concept of segmented right-deep trees to
exploit inter-operator parallelism for the execution of pipelined
hash joins in a multiprocessor-based database system.  A query plan
is usually compiled into a tree of operators, called query execution
tree, where a leaf node represents an input relation and an internal
node represents the resulting relation from joining the two relations
associated with its two child nodes.  Inter-operator parallelism
means different joins are executed in parallel by different clusters
of processors.  For exploring inter-operator parallelism, there are
three categories of query trees:  left-deep trees, right-deep trees,
and bushy trees.  In the context of hash joins, the left and right
child nodes of an internal node represent the inner and outer
relations of the join, respectively.  Hash joins provide the
feasibility of pipelining, which has the following three advantages.
First, most intermediate relations never need to be written back to
disks, or even exist as whole tables in the memory, hence
significantly reducing the I/O cost incurred.  Second, the first
tuples of the resulting relation can be produced earlier, which can
not only reduce the perceived response time by an end user, but also
enable an application program to start processing the result earlier.
Third, resources can be used more efficiently by adjusting the degree
of inter-operator parallelism exploited in the pipeline.

   Though right-deep trees and bushy trees allow the implementation
of pipelining, previous work on pipelining has focused on the use of
right-deep trees due to their simplicity in generation and
implementation.  Also, the improvement achievable by using the bushy
trees was not clearly understood.  The bushy tree, without being
restricted to a linear form, is of more flexibility on query plan
generation, and able to obtain a better query execution plan than a
right-deep tree can at the cost of searching in an ampler space.
However, as far as the hash join is concerned, the scheduling for an
execution plan of a bushy tree structure is much more complicated
than that of a right-deep tree structure.  Particularly, it is very
difficult, if not impossible, to achieve the synchronization required
for the execution of bushy trees such that the effect of pipelining
can be fully utilized.  As a result, to improve the parallel
execution of multi-join queries, we would naturally like to develop
schemes which can efficiently generate effective query plans that
fully exploit the advantage of pipelining while avoiding the above
mentioned deficiencies of the bushy and right-deep trees.

   A segmented right-deep tree is of the form of a bushy tree and
composed of a collection of right-deep subtrees, each of which is
associated with a pipeline segment.  The pipeline segments will be
executed one by one in a manner of bottom up with...