## 4 Techniques of In-Network Join Processing
### Techniques without Filtering of Non-Joinable Tuples
In the second query model, to perform a sliding window join, both \(\widehat{\w}_{R}\) and \(\widehat{\w}_{S}\) are maintained in the join region \(P\). A difference from the static join case is that not only \(R\) but \(S\) is shipped and distributed in \(P\) in the unit of a sliding window. \(\widehat{\w}_{R}\) (\(\widehat{\w}_{S}\)) is supposed to be partitioned among the nodes of \(P\) such that each node of \(P\) stores a partition of \(\widehat{\w}_{R}\) as well as a partition of \(\widehat{\w}_{S}\). Each tuple \(t\) of \(R\)_(S)_ is sent to \(P\) when it is produced. \(t\) is broadcast to every node of \(P\) such that it is joined with \(\widehat{\w}_{S}\) (\(\widehat{\w}_{R}\)). In this process, \(t\) is stored at the first encountered node of \(P\) with available memory. The join result tuples are sent to the query sink. The stream version of _Distributed-Broadcast Join_ is a _symmetric_ nested-loop join. The set of newly produced tuples of \(R\) (\(S\)) is the outer relation while \(\widehat{\w}_{S}\) (\(\widehat{\w}_{R}\)) plays the role of the inner relation. In computing the location of the optimal join region \(\mathcal{P}\), the size of \(\mathcal{P}\) needs to be set so that both \(\widehat{\w}_{R}\) and \(\widehat{\w}_{S}\) could be stored in \(\mathcal{P}\). _Distribute-Broadcast Join_ can be effective for a long-running continuous join. Reliable statistics required in computing the optimal join region such as the sizes of \(R\), \(S\), and \(R\Join S\) can be collected when the query is long-running. It is especially so when data rates of \(R\) and \(S\) and join selectivity vary during the lifetime of the query. _Distributed-Broadcast Join_ can adapt to node failures in traversing the join region because GPSR and TBF protocols can adapt to node failures, guaranteeing data delivery as long as a route exists. _Mediated Join_. In [4], [PERSON] _et al_. proposed _Mediated Join_ to answer an inter-region join \(R\Join S\) to be executed as a one-shot query submitted at the query sink \(Q\). It collects \(R\) and \(S\) at a join region \(P\), performs the join, and sends the result to \(Q\). \(P\) consists of one or more nodes, and its location is other than that of region \(R\) or \(S\). A detailed description of a distributed join algorithm in WSNs with which _Mediated Join_ can be implemented is well presented in [3]. \(R\Join S\) is implemented in nested-loop join. First, \(R\) is distributed in \(P\), and then \(S\) is broadcast to \(P\) for join. \(R\) and \(S\) respectively play the role of the inner and the outer relation. In [3], [PERSON] and [PERSON] investigated a problem of optimal selection of \(R\) or \(S\) as the _outer_ relation (with the remaining one being the inner relation). The choice would make a difference in communication cost of executing the same join. Depending on the choice, the size of the join region would be different. The size of the join region affects the cost for distributing the inner relation as well as the cost for broadcasting the outer relation. In [3], the cost formula that estimates the total communication cost \(E\) in processing \(R\Join S\) given the sizes of \(R_{i}\) (inner relation) and \(R_{o}\) (outer relation) is derived. Using this formula, it was shown that the total cost would vary considerably depending on which of \(R\) or \(S\) is selected as the outer relation. With \(E(R_{i}=R)\) denoting the total cost where \(R\) is the inner relation, and \(\|R\|\) the size of \(R\), it was shown that the ratio \(E(R_{i}=S)/E(R_{i}=R)\) non-monotonically varies from 0.6 to around 1.6 when the ratio \(\|S\|/\|R\|\) falls in the range [1, 7]. If \(E(R_{i}=S)/E(R_{i}=R)\) is greater than 1, \(S\) is chosen as the outer relation. Otherwise, \(R\) is chosen as the outer relation. Once the routing tree of region \(R\) (\(S\)) is constructed, the size of \(R\) (\(S\)) can be collected at the root. Therefore, it is possible to pick a better nested-loop join strategy at the join region where the join is to be conducted. _Distributed Index-Join_.