Next: Brute Force Nested-Loops Joins Up: Join Processing Previous: Types of Joins

Sequential Join Algorithms

As previously stated, a lot of effort has been spent on finding efficient ways of joining two or more relations. As a result, many different join algorithms have evolved, many of them being variations of others. Essentially, there are four basic techniques:

brute force nested-loops,
sort-merge,
hash,
data-structure-assisted (index-based).

In the following subsections, we look at these techniques for performing the join

$\begin{displaymath} R \;\Join_{\scriptscriptstyle C}\; Q\end{displaymath}$

The purpose is to give sufficient details to understand the implications for temporal joins. A more detailed summary of join algorithms can be found in [Mishra and Eich, 1992].

Finally, in section 3.6, two features are presented that allow us to classify the various algorithms, namely:

the way in which data is partitioned into data fragments, and
the degree of overlap of fragments during the joining phase.

These characteristics will allow us to analyse the algorithms with respect to their suitability for temporal join processing.

Thomas Zurek