In this section we derive the costs of stage 2 of the temporal join processing model. This stage is described in section 8.3.4. Here, each processor j performs computations , , ..., . Each computation RQk consists of performing the three subjoins
in exactly that order in order to exploit the opportunity to keep (a part of) R'k in main memory at the end of join (a), thus avoiding to reload it at the beginning of join (b). Alternatively, we could use the order (c), (b), (a) and exploit the same fact for the Q'k. In the remainder, however, we will assume the order (a), (b), (c); arguments and results can be easily transferred to the alternative case.
The subjoins are performed by using the nested-block join technique . This means that in joins (a) and (b) an R'k is cached either entirely or blockwise in main memory while being joined with Q''k and Q'k respectively. In join (c) we assume the same for the Q'k when being joined with R''k. The number of blocks in which an R'k has to be divided is referred to by . If is the amount of main memory at each node then each processor gets a share of
Thus can be computed by Similarly, refers to the number of blocks into which a Q'k is divided for computation in subjoin (c): We note that and are 1 if R'k and Q'k respectively fit in main memory.
The costs for each of the subjoins are computed in the same way: the
two sets of tuples have to be read from disk and are then joined using
a nested-blocked approach![[*]](foot_motif.gif)
. A minor difference appears for
join (b) that can exploit the fact that (a block of) R'k already
resides in main memory and therefore has not to be reloaded from disk.
There is no communication via the interconnect involved because the computations RQk are independent from each other. In the following paragraphs, we describe the cost components for join (a). The costs for joins (b) and (c) are derived accordingly with the marginal difference in the case of join (b) that has been mentioned above. All cost components are summarised in tables 8.5, 8.6 and 8.7.
First, we look at the I/O costs. These have to be considered on a node-wide level as disks are shared among all the processors of a node. For join (a), all tuples of R'k have to be read once from disk and those of Q''k once per block of R'k, i.e. times. Thus a node i has to load
tuples of sizes |r| and |q| respectively. This implies I/O costs of at node i. For the overall costs only the costs of the node with the heaviest load is relevant, i.e.| (57) |
| (58) |
| (59) |
| (60) |