Partitioned Temporal Join for Sequential Processing

Next: Spatially Partitioned Temporal Join Up: Explicit-Partitioning Join Algorithms Previous: Improved Temporal Hash Join

Partitioned Temporal Join for Sequential Processing

The separation of primary and replicated tuples within an R_k can be exploited for sequential processing too. Soo et al. proposed the following strategy in [Soo et al., 1994]:

The partial joins $R_1 \Join_{\scriptscriptstyle C}Q_1$ , ..., $R_m \Join_{\scriptscriptstyle C}Q_m$ are processed either from `left to right' (i.e. 1 to m) or `right to left' (i.e. m to 1).
Assuming that the partial joins are processed in the order from 1 to m, we can avoid the replication of tuples which, for example, takes place within a partitioning stage that precedes that joining stage. This can be done in the following way: after a partial join $R_k \Join_{\scriptscriptstyle C}Q_k$ has been processed the tuples $R''_{k+1} \,\subseteq\, R_k$ and $Q''_{k+1} \,\subseteq\, Q_k$ are kept in a cache memory. Thus, only R'_k+1 and Q'_k+1 need to be accessed on disk.

Figure 4.12 summarises this strategy. Again, if the partial joins are evaluated by nested loops we get a search strategy as in figure 4.8. Please note that the difference lies in the fact that, here, partial joins are not independent from each other and require sequential processing in order to save disk access costs. Soo et al.'s technique can also be improved by decomposing the partial joins as described in section 4.4.3. The resulting search strategy then corresponds to figure 4.11.

**Figure:** Sequential processing of a partitioned temporal intersection join.
$\begin{figure} \begin{center} \fbox { \begin{minipage} {9cm} \begin{flushleft} ... ...\scriptscriptstyle C}Q_m$\end{flushleft}\end{minipage}} \end{center}\end{figure}$

Next: Spatially Partitioned Temporal Join Up: Explicit-Partitioning Join Algorithms Previous: Improved Temporal Hash Join

Thomas Zurek