next up previous contents index
Next: Cost Model Up: Temporal Join Processing Model Previous: Stage 1: Repartitioning

Stage 2: Joining

  

We now look at stage 2 of the algorithm. Here, each processor performs one or more computations RQk with $k=1,\dots,m$ in sequential order (see figure 8.10). In the remainder, we focus on one single computation RQk only and describe how it is done.

(8.1) defined an RQk to consist of the sequential computation of three individual subjoins 

Splitting the one `big' join $R \Join_{\scriptscriptstyle C}Q$ into several smaller partial joins $R_1 \Join_{\scriptscriptstyle C}Q_1$, ..., $R_m \Join_{\scriptscriptstyle C}Q_m$ and each of these partial joins into subjoins as in (8.1) was described in section 4.4.3. The two major advantages for this are:

1.
It is

but the join $R''_k \Join_{\scriptscriptstyle C}Q''_k$ is redundant as it is

Processing can therefore be reduced to the first three subjoins, thus avoiding a considerable amount of unnecessary computation.
2.
A second advantage arises from the fact that the size of the R'k  are easier to control than those of the Rk or R''k because every tuple appears only in one R'k but possibly in several Rk or R''k:

but

Actually, it is possible to guarantee that for all $k=1,\dots,m$ the R'k have a certain maximum number X of tuples (see chapter 5 and the oncoming chapter 9). Thus a partition can be chosen that guarantees that all R'k fit into a processor's local main memory. But this means that each R'k needs to be read from disk only once for the first subjoin and is then kept in main memory for the second subjoin . Alternatively one could do the same with Q'k, computing the subjoin first, keeping Q'k in main memory and then computing . Thus we are able to reduce the total number of disk accesses by |R|/2 and |Q|/2 respectively.

With respect to each subjoin, one can use any sequential temporal join algorithm. We adopt a nested-loops approach for the following reason: the selectivity factors  of the partial joins $R_k \Join_{\scriptscriptstyle C}Q_k$ - in the remainder we will refer to these factors as partial selectivities  - can be expected to be fairly high because the data has been partitioned according to the join predicate (i.e. temporal intersection in our case). We performed preliminary experiments in order to confirm this conclusion: two temporal relations U and V of 10000 tuples each were generated. U had a random profile with the majority of tuples being valid in the first half of the lifespan (1440 chronons) . V was periodic in the sense that there were several equal peak-to-peak distances for the function giving the number of tuples being valid at a time. The average length of a time interval was the same in both relations (120 chronons). The three temporal intersection joins (experiment 1), (experiment 2) and (experiment 3) were partitioned into m partial joins using (a) a uniform partition of the timeline and (b) an optimal partition using the algorithm IP-opt  of chapter 5. The resulting partial selectivities are shown in figure 8.12 and confirm our initial conclusion that partial selectivities are fairly high, beyond 70% in most cases. This justifies to use a nested-loops approach. Further partitioning through sorting (sort-merge join) or hashing (hash join) would not increase the performance by much but would introduce an overhead through sorting[*] and hashing respectively.


    
Figure: Partial selectivities as achieved in preliminary experiments.

After having clarified essential details we can now describe how a computation RQk is performed. We assume that the subjoins are computed in the order in which they appear in (8.1). Furthermore it is assumed that the respective outer relation is bigger than the corresponding inner relation for efficiency reasons (see section 3.4.1). If this is not the case one can easily swap. The join condition  C  consists of a temporal intersection and some boolean expression   over tuples $r \in R$ and $q \in Q$. The latter is supposed to be non-temporal and therefore amenable to the same optimisations that may be applied to non-temporal join evaluation. For performance modeling purposes we later assume that evaluates to true so that we can neglect any implications given by this part of the join condition and concentrate on the essential temporal aspects. Finally, a processor j is supposed to accumulate join results in an output buffer   which is flushed to disk when it is full. A join is then performed as shown in figure 8.13 which already assumes that evaluates to true. A computation RQk processes the three subjoins in sequential order:

(a)
intersection-join(R'k,Q''k)
(b)
intersection-join(R'k,Q'k)
(c)
intersection-join(R''k,Q'k)


  
Figure: The procedure intersection-join(R,Q).

The term time-concatenate   refers to the process of creating an appropriate timestamp  when concatenating a tuple $r \in R$ and a tuple $q \in Q$. This was described by (4.1) in section 4.1.

next up previous contents index
Next: Cost Model Up: Temporal Join Processing Model Previous: Stage 1: Repartitioning
Thomas Zurek