Continuous multi-way joins over distributed hash tables

ABSTRACT

This paper studies the problem of evaluating continuous multi-way joins on top of Distributed Hash Tables (DHTs). We present a novel algorithm, called recursive join (RJoin), that takes into account various parameters crucial in a distributed setting i.e., network traffic, query processing load distribution, storage load distribution etc. The key idea of RJoin is incremental evaluation: as relevant tuples arrive continuously, a given multi-way join is rewritten continuously into a join with fewer join operators, and is assigned continuously to different nodes of the network. In this way, RJoin distributes the responsibility of evaluating a continuous multi-way join to many network nodes by assigning parts of the evaluation of each binary join to a different node depending on the values of the join attributes. The actual nodes to be involved are decided by RJoin dynamically after taking into account the rate of incoming tuples with values equal to the values of the joined attributes. RJoin also supports sliding window joins which is a crucial feature, especially for long join paths, since it provides a mechanism to reduce the query processing state and thus keep the cost of handling incoming tuples stable. In addition, RJoin is able to handle message delays due to heavy network traffic. We present a detailed mathematical and experimental analysis of RJoin and study the performance tradeoffs that occur.

REFERENCES

• 1: Arvind Arasu , Shivnath Babu , Jennifer Widom, The CQL continuous query language: semantic foundations and query execution, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.2, p.121-142, June 2006 [doi>10.1007/s00778-004-0147-z]
• 2: D. Abadi et al. The Design of the Borealis Stream Processing Engine. CIDR '05.
• 3: Karl Aberer , Luc Onana Alima , Ali Ghodsi , Sarunas Girdzijauskas , Seif Haridi , Manfred Hauswirth, The Essence of P2P: A Reference Architecture for Overlay Networks, Proceedings of the Fifth IEEE International Conference on Peer-to-Peer Computing, p.11-20, August 31-September 02, 2005 [doi>10.1109/P2P.2005.38]
• 4: 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
• 5: Y. Ahmad et al. Locality-Aware Networked Join Evaluation. NETDB '05.
• 6: Mayank Bawa , Aristides Gionis , Hector Garcia-Molina , Rajeev Motwani, The price of validity in dynamic networks, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007627]
• 7: Don Carney , Uǧur Çetintemel , Mitch Cherniack , Christian Convey , Sangdon Lee , Greg Seidman , Michael Stonebraker , Nesime Tatbul , Stan Zdonik, Monitoring streams: a new class of data management applications, Proceedings of the 28th international conference on Very Large Data Bases, p.215-226, August 20-23, 2002, Hong Kong, China
• 8: Sirish Chandrasekaran , Michael J. Franklin, PSoup: a system for streaming queries over streaming data, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.2, p.140-156, August 2003 [doi>10.1007/s00778-003-0096-y]
• 9: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, ACM SIGMOD Record, v.29 n.2, p.379-390, June 2000
• 10: M. Cherniack et al. Scalable Distributed Stream Processing. CIDR '03.
• 11: Bugra Gedik , Ling Liu, PeerCQ: A Decentralized and Self-Configuring Peer-to-Peer Information Monitoring System, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.490, May 19-22, 2003
• 12: Lukasz Golab , M Tamer Özsu, Processing sliding window multi-joins in continuous queries over data streams, Proceedings of the 29th international conference on Very large data bases, p.500-511, September 09-12, 2003, Berlin, Germany
• 13: J. M. Hellerstein et al. A Wakeup Call for Internet Monitoring Systems: The Case for Distributed Triggers. HotNets-III '04.
• 14: Keren Horowitz , Dahlia Malkhi, Estimating network size from local information, Information Processing Letters, v.88 n.5, p.237-243, 16 December 2003 [doi>10.1016/j.ipl.2003.08.011]
• 15: Ryan Huebsch , Joseph M. Hellerstein , Nick Lanham , Boon Thau Loo , Scott Shenker , Ion Stoica, Querying the internet with PIER, Proceedings of the 29th international conference on Very large data bases, p.321-332, September 09-12, 2003, Berlin, Germany
• 16: R. Huebsch et al. The Architecture of PIER: an Internet-Scale Query Processor. CIDR '05.
• 17: S. Idreos. Distributed Evaluation of Continuous Equi-join Queries over Large Structured Overlay Networks. Master thesis. Technical University of Crete. September, 2005.
• 18: Stratos Idreos , Christos Tryfonopoulos , Manolis Koubarakis, Distributed Evaluation of Continuous Equi-join Queries over Large Structured Overlay Networks, Proceedings of the 22nd International Conference on Data Engineering, p.43, April 03-07, 2006 [doi>10.1109/ICDE.2006.50]
• 19: David R. Karger , Matthias Ruhl, Simple efficient load balancing algorithms for peer-to-peer systems, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007919]
• 20: 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]
• 21: Ling Liu , Calton Pu , Wei Tang, Continual Queries for Internet Scale Event-Driven Information Delivery, IEEE Transactions on Knowledge and Data Engineering, v.11 n.4, p.610-628, July 1999 [doi>10.1109/69.790816]
• 22: Samuel Madden , Mehul Shah , Joseph M. Hellerstein , Vijayshankar Raman, Continuously adaptive continuous queries over streams, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564698]
• 23: S. Chandrasekharan et al. TelegraphCQ: Continuous dataflow processing for an uncertain world. CIDR '03.
• 24: J. Shneidman et al. A Cost-Space Approach to Distributed Query Optimization in Stream Based Overlays. NETDB '05.
• 25: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, ACM SIGCOMM Computer Communication Review, v.31 n.4, p.149-160, October 2001
• 26: Douglas Terry , David Goldberg , David Nichols , Brian Oki, Continuous queries over append-only databases, ACM SIGMOD Record, v.21 n.2, p.321-330, June 1, 1992
• 27: B.-Y. Zhao et al. Tapestry: A Resilient Global-scale Overlay for Service Deployment. IEEE Journal on Selected Areas in Communications, 22(1), 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations