Parallel Temporal Nested-Loop Joins
| Author:
| Thomas Zurek
|
| Date:
| January 1996
|
| Type:
| Technical Report, ECS-CSG-20-95
|
| Institution:
| Department of Computer Science, Edinburgh University
|
Abstract
In this report we present a framework for parallel temporal joins. We
focus on temporal intersection as the most general temporal join
condition. A basic algorithm is given that consists of a partition and
a joining stage. In the partition stage tuples have to be replicated
if they intersect with more than one partition range. This causes a
significant overhead -- around 70% in the case of our modest workload.
The joining stage can employ any sequential join technique. The basic
algorithm is enhanced through two possible optimisations that reduce
the overhead imposed by replication.
The algorithm and its optimisations are evaluated on top of a
performance model. We describe the model and give details in the
appendix. The evaluation shows that both optimisations together
decrease the basic costs significantly. Furthermore we can give an
idea of the quantitative impact of replication overhead in parallel
temporal join processing. Our (modest) workload caused a share of
around 70% of the total costs; higher values can be expected in
reality.
Thomas Zurek,
<tz@dcs.ed.ac.uk>