E.: Scalable stream join processing with expensive predicates: Workload distribution and adaptation by time-slicing

Multi-way stream joins with expensive join predicates lead to great challenge for real-time (or close to real-time) stream processing. Given the memory- and CPU-intensive nature of such stream join queries, scalable processing on a cluster must be employed. This paper proposes a novel scheme for distributed processing of generic multi-way joins with win-dow constraints, called Pipelined State Partitioning (PSP). We target generic joins with arbitrarily join conditions, which are used in non-trivial stream applications such as image matching and biometric recognizing. The PSP scheme par-titions the states into disjoint slices in the time domain, and then distributes the fine-grained states in the cluster, form-ing a virtual computation ring. Compared to replication-based distribution of non-equi-joins, PSP scheme is supe-rior since: (1) zero state duplication and thus no repeated computations, (2) pipelined processing of every input tu-ple on multiple nodes to achieve low response time, and (3) cost-based adaptive workload distribution. We have implemented the proposed PSP schemes within the CAPE DSMS. Our experimental study demonstrates the significant performance improvements compared to the state-of-the-art generic distributed stream join algorithms. 1