## 4 Techniques of In-Network Join Processing
### Techniques without Filtering of Non-Joinable Tuples
Figure 5: **(a)** An initiator node \(N_{i}\) and its target node \(N_{t}\). A join between \(N_{i}\) and \(N_{t}\) is called a _pair-wise join_. **(b)** Two target nodes \(N_{t}^{\,1}\) and \(N_{t}^{\,2}\) for one initiator node \(N_{i}\). Each of the (\(N_{i}\), \(N_{t}^{\,1}\)) and (\(N_{i}\), \(N_{t}^{\,2}\)) pairs represents a pair-wise join. In [23], _multiple routing trees_ are considered to provide several alternative paths between an initiator node and a target node. Using only one routing tree, the number of hops between two nodes physically near each other may be large. This problem can be handled by employing multiple trees. They can also reduce hot spots and congestion. Since multiple routing trees are employed, a target node may hear from the initiator node through multiple paths. The two nodes choose one of these paths and one node on the chosen path as the _join node_. Figure 6 shows an example where two routing trees are employed. Here, a cost-based selection of the optimal join node is carried out, assuming that selectivity of each predicate \(\psi\) is known and that the number of hops from a node to the base station is known [22]. In [22], the techniques of _multiple_ join pair optimization were also proposed. One is network-level resource sharing. An example is a _path collapse_ feature shown in Figure 7(a,b). For two pair-wise joins,  
Figure 6: **(a)** A routing tree where a dark circle denotes the root, and the _join path_ between two triangular nodes; **(b)** Alternative routing tree for the same set of nodes and a different join path; **(c)** The two routing trees are in use together, and there are two join paths searched; **(d)** Every node on the two join paths are candidate _join nodes_. Figure 7: Multiple join pair optimization. (a) Before path collapse: there are two pair-wise joins (\(i\), \(t_{1}\)) and (\(i\), \(t_{2}\)). The two join paths are node-disjoint except \(i\). There is a link between \(n_{1}\) and \(n_{2}\); (b) After path collapse: the link between \(n_{1}\) and \(n_{2}\) is in use to make the join path of (\(i\), \(t_{2}\)) shorter; (c) Before group-based optimization for \(R\bowtie S\), where \(\mathbb{R}=\{r_{1}\), \(r_{2}\}\) and \(\mathbb{S}=\{s_{1},s_{2},s_{3}\}\); (d) After group-based optimization: \(R\bowtie S\) is executed as an external join. if some part of their join paths could be shared to make one of the current join paths shorter, that path is updated. Another is a _group-based optimization_ shown in Figure 7(c,d). For a join \(R\bowtie S\), if a complete bipartite graph is formed between the two node sets \(\mathbb{R}\) and \(\mathbb{S}\) (_i.e._, there are \(|\mathbb{R}|\cdot|\mathbb{S}|\) pair-wise joins running), the external join in which all the nodes in \(\mathbb{R}\cup\ \mathbb{S}\) participate is considered as an alternative strategy. Cost analysis is carried out to check if the external join is cheaper than a group of \(|\mathbb{R}|\cdot|\mathbb{S}|\) pair-wise joins. In _Pair-Wise Join_, node failures are handled as follows: If a node on the join path fails after the path is established, the node of data source cannot reach the join node. Recovery is carried out by searching an alternative path. If such a recovery fails, a pair-wise join is switched to the external join. If the base station is unreachable from a node, it will wait for the routing trees to be rebuilt. _Pair-wise Join_ would be effective for the applications where each node that participates in the join query is expected to be paired with a small number of nodes due mainly to the spatial join predicates. It can be employed for a long-running continuous join. The statistics required in cost analysis for the optimal join initiation and in multiple join pair optimization are assumed to be collectable because the query is long-running. The optimal join initiation for a pair-wise join may be very costly, incurring high communication overhead. It could be amortized later if the query is a long-running one.