Spinning relations: high-speed networks for distributed join processing

ABSTRACT

By leveraging modern networking hardware (RDMA-enabled network cards), we can shift priorities in distributed database processing significantly. Complex and sophisticated mechanisms to avoid network traffic can be replaced by a scheme that takes advantage of the bandwidth and low latency offered by such interconnects.

We illustrate this phenomenon with cyclo-join, an efficient join algorithm based on continuously pumping data through a ring-structured network. Our approach is capable of exploiting the resources of all CPUs and distributed main-memory available in the network for processing queries of arbitrary shape and datasets of arbitrary size.

REFERENCES

• 1: Swarup Acharya , Rafael Alonso , Michael Franklin , Stanley Zdonik, Broadcast disks: data management for asymmetric communication environments, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.199-210, May 22-25, 1995, San Jose, California, United States
• 2: Philip A. Bernstein , Dah-Ming W. Chiu, Using Semi-Joins to Solve Relational Queries, Journal of the ACM (JACM), v.28 n.1, p.25-40, Jan. 1981 [doi>10.1145/322234.322238]
• 3: T. F. Bowen , G. Gopal , G. Herman , T. Hickey , K. C. Lee , W. H. Mansfield , J. Raitz , A. Weinrib, The Datacycle architecture, Communications of the ACM, v.35 n.12, p.71-81, Dec. 1992 [doi>10.1145/138859.138868]
• 4: David D. Clark, Van Jacobson, John Romkey, and Howard Salwen. An Analysis of TCP Processing Overhead. IEEE Communications Magazine, 27:23--29, 1989.
• 5: A. P. Foong , T. R. Huff , H. H. Hum , J. R. Patwardhan , G. J. Regnier, TCP performance re-visited, Proceedings of the 2003 IEEE International Symposium on Performance Analysis of Systems and Software, p.70-79, March 06-08, 2003
• 6: Philip Werner Frey , Gustavo Alonso, Minimizing the Hidden Cost of RDMA, Proceedings of the 2009 29th IEEE International Conference on Distributed Computing Systems, p.553-560, June 22-26, 2009 [doi>10.1109/ICDCS.2009.32]
• 7: InfiniBand Trade Association. InfiniBand Architecture Specification. http://www.infinibandta.org.
• 8: S. Ioannidis, E. Markatos, and J. Sevaslidou. Using Network Memory to Improve the Performance of Transaction-Based Systems. In Proc. of the 4th ACM LCR, Pittsburgh, PA, USA, May 1998.
• 9: H. T. Kung and Charles E. Leiserson. Systolic Arrays (for VLSI). In Sparse Matrix Proceedings, pages 256--282, Knoxville, TN, USA, November 1978.
• 10: Lothar F. Mackert , Guy M. Lohman, R* Optimizer Validation and Performance Evaluation for Distributed Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.149-159, August 25-28, 1986
• 11: Stefan Manegold , Peter Boncz , Martin Kersten, Optimizing Main-Memory Join on Modern Hardware, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.709-730, July 2002 [doi>10.1109/TKDE.2002.1019210]
• 12: A. Romanow, J. Mogul, T. Talpey, and S. Bailey. Remote Direct Memory Access (RDMA) over IP Problem Statement, 2005.
• 13: Ambuj Shatdal , Chander Kant , Jeffrey F. Naughton, Cache Conscious Algorithms for Relational Query Processing, Proceedings of the 20th International Conference on Very Large Data Bases, p.510-521, September 12-15, 1994
• 14: Z. Smith. Bandwidth: a Memory Bandwidth Benchmark. http://home.comcast.net/~fbui/bandwidth.html.
• 15: Patrick Valduriez , Georges Gardarin, Join and Semijoin Algorithms for a Multiprocessor Database Machine, ACM Transactions on Database Systems (TODS), v.9 n.1, p.133-161, March 1984 [doi>10.1145/348.318590]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Design, Management