## 3 Overview of Join Processing in WSNs
### Components of Join Implementation
The same principle could be exploited for joins in WSNs. Such techniques conduct in-network filtering of non-joinable attribute values and/or of non-joinable tuples using semijoins or its variants [2, 4, 5, 6, 7, 12, 21]. An alternative approach is a stochastic one using and maintaining a join filter in every sensor node [24]. This technique called _Continuous Join Filtering (CJF)_ is described in Section 4.3. Given a 2-way join \(R\bowtie S\) in WSNs, the techniques proposed in the literature fall into the following three categories based on the reduction of the join operand relations:  
* Full reduction of both operand relations [2, 4, 21]
* Full reduction of one operand relation [6]
* Partial reduction of both operand relations [5, 7, 12, 24]  
**Involvement of base station. ** In all the techniques surveyed, after non-joinable tuples are filtered out if such a step exists, those tuples that have survived are sent either to the base station or to the query sink inside the network or to the designated join region of the network for the final join. Excluding this final join phase, all the techniques except those of [6, 7, 24] conduct in-network processing of join _without_ any form of involvement of the base station. In the techniques of [6, 7, 24], the base station is not just involved but plays a coordinating and core role. **Adapted join implementation**. Most of the proposed techniques can be regarded as having some components that are variations or extensions of the join or semijoin implementations in the conventional centralized/distributed databases. They are adapted to the WSN environments. The techniques in [3, 4, 8, 11] adapt nested-loop join or indexed nested-loop join. Those of [2, 5, 8] adapt hash join, partitioning relations into buckets which are replaced inside the network. Even the sort-merge join is logically adapted in the techniques of [5, 12] though no physical sorting is carried out in the network. The techniques of [2, 4, 5, 6, 7, 12, 21] conduct in-network filtering of non-joinable tuples with the semijoin or its variations adapted to WSNs. **Cost-based optimization. ** Assuming that the statistics on the sensor readings are given a priori or collected for a long-running continuous join, cost-based join optimization is carried out. The list includes:  
* computation of the optimal join region for an inter-region join [4, 11, 20]
* selection of the optimal inner/outer relation in an adapted nested-loop join implementation [3]
* selection of the optimal join path in the network and the optimal join node on the path for a pair of nodes that participate in a join [22, 23]* adaptive re-optimization for the join path and the join node for a pair of nodes that participate in a join [22]
* adaptive re-optimization for multiple pairs of nodes that participate in a join [22]
* selection of the optimal in-network semijoin strategy for a routing tree based inter-region join [21]
* maintenance of the optimal join filters [24]  
All of the aforementioned cost-based optimizations except that in [3] are suitable for a long-running continuous join query. One reason is that they require the statistics on the sensor readings for cost analysis and their meaningful values could not be collected soon. Another reason is that the cost incurred for such an optimization might be so high that it needs to be amortized during the lifetime of the query. **Collection of statistics. ** To conduct cost-based optimizations, the statistics on sensor relations and join result are required. They include the size of join operand relations, the size of join result (or join selectivity), semijoin selectivities, and selectivity of each selection predicate on sensor attributes, and so on. The collection of the statistics is a part of join implementation. In [11], for a periodic continuous join, the initial execution is assumed to be carried out at the query sink to sample the statistics. In [21], the external join is employed in the learning phases to collect the statistics.