Scalable stream join processing with expensive predicates: workload distribution and adaptation by time-slicing

ABSTRACT

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 window 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 partitions the states into disjoint slices in the time domain, and then distributes the fine-grained states in the cluster, forming a virtual computation ring. Compared to replication-based distribution of non-equi-joins, PSP scheme is superior since: (1) zero state duplication and thus no repeated computations, (2) pipelined processing of every input tuple 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.

REFERENCES

• 1: Yanif Ahmad , Bradley Berg , Uǧur Cetintemel , Mark Humphrey , Jeong-Hyon Hwang , Anjali Jhingran , Anurag Maskey , Olga Papaemmanouil , Alexander Rasin , Nesime Tatbul , Wenjuan Xing , Ying Xing , Stan Zdonik, Distributed operation in the Borealis stream processing engine, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066274]
• 2: Yanif Ahmad , Uğur Çetintemel, Network-aware query processing for stream-based applications, Proceedings of the Thirtieth international conference on Very large data bases, p.456-467, August 31-September 03, 2004, Toronto, Canada
• 3: M. H. Ali , W. G. Aref , R. Bose , A. K. Elmagarmid , A. Helal , I. Kamel , M. F. Mokbel, Nile-PDT: a phenomenon detection and tracking framework for data stream management systems, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 4: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 5: Shivnath Babu , Rajeev Motwani , Kamesh Munagala , Itaru Nishizawa , Jennifer Widom, Adaptive ordering of pipelined stream filters, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007615]
• 6: Shivnath Babu , Kamesh Munagala , Jennifer Widom , Rajeev Motwani, Adaptive Caching for Continuous Queries, Proceedings of the 21st International Conference on Data Engineering, p.118-129, April 05-08, 2005 [doi>10.1109/ICDE.2005.15]
• 7: David DeWitt , Jim Gray, Parallel database systems: the future of high performance database systems, Communications of the ACM, v.35 n.6, p.85-98, June 1992 [doi>10.1145/129888.129894]
• 8: Sumit Ganguly , Waqar Hasan , Ravi Krishnamurthy, Query optimization for parallel execution, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.9-18, June 02-05, 1992, San Diego, California, United States
• 9: X. Gu, P. S. Yu, and H. Wang. Adaptive load diffusion for multiway windowed stream joins. In ICDE, pages 146--155, 2007.
• 10: Navendu Jain , Lisa Amini , Henrique Andrade , Richard King , Yoonho Park , Philippe Selo , Chitra Venkatramani, Design, implementation, and evaluation of the linear road bnchmark on the stream processing core, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142522]
• 11: Donald Kossmann, The state of the art in distributed query processing, ACM Computing Surveys (CSUR), v.32 n.4, p.422-469, Dec. 2000 [doi>10.1145/371578.371598]
• 12: Sailesh Krishnamurthy , Chung Wu , Michael Franklin, On-the-fly sharing for streamed aggregation, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142543]
• 13: Sailesh Kumar , Sarang Dharmapurikar , Fang Yu , Patrick Crowley , Jonathan Turner, Algorithms to accelerate multiple regular expressions matching for deep packet inspection, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 14: Bin Liu , Yali Zhu , Mariana Jbantova , Bradley Momberger , Elke A. Rundensteiner, A dynamically adaptive distributed system for processing complex continuous queries, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 15: V. Raghavan, E. A. Rundensteiner, J. P. Woycheese, and A. Mukherji. Firestream: Sensor stream processing for monitoring fire. In ICDE, 2007.
• 16: M. A. Shah, J. M. Hellerstein, S. Chandrasekaran, and M. J. Franklin. Flux: An adaptive partitioning operator for continuous query systmes. In Proceedings of ICDE, pages 25--36, 2003.
• 17: Utkarsh Srivastava , Jennifer Widom, Memory-limited execution of windowed stream joins, Proceedings of the Thirtieth international conference on Very large data bases, p.324-335, August 31-September 03, 2004, Toronto, Canada
• 18: Nesime Tatbul , Uğur Çetintemel , Stan Zdonik , Mitch Cherniack , Michael Stonebraker, Load shedding in a data stream manager, Proceedings of the 29th international conference on Very large data bases, p.309-320, September 09-12, 2003, Berlin, Germany
• 19: Feng Tian , David J. DeWitt, Tuple routing strategies for distributed eddies, Proceedings of the 29th international conference on Very large data bases, p.333-344, September 09-12, 2003, Berlin, Germany
• 20: T. Urhan and M. Franklin. XJoin: A reactively scheduled pipelined join operator. IEEE Data Engineering Bulletin, 23(2):27--33, 2000.
• 21: Patrick Valduriez, Parallel database systems: open problems and new issues, Distributed and Parallel Databases, v.1 n.2, p.137-165, April 1993 [doi>10.1007/BF01264049]
• 22: Stratis D. Viglas , Jeffrey F. Naughton , Josef Burger, Maximizing the output rate of multi-way join queries over streaming information sources, Proceedings of the 29th international conference on Very large data bases, p.285-296, September 09-12, 2003, Berlin, Germany
• 23: Song Wang , Elke Rundensteiner , Samrat Ganguly , Sudeept Bhatnagar, State-slice: new paradigm of multi-query optimization of window-based stream queries, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea