Performance comparison of join on hypercube and mesh

ABSTRACT

In this paper, we compare the performance of two join algorithms on a cube and on a multidimensional mesh architectures. The algorithms are nested-loop and sort-merge joins. The study confirms that a higher connectivity architecture is faster and has a wider performance bandwidth. The sort-merge join algorithm is better for a small number of nodes, but it becomes worse than the nested-loop join algorithm as the number of nodes gets larger and the join selectivity gets large, especially for the simpler mesh architecture. The study also shows that the 3-dimensional mesh architecture has performance comparable to the more complicated cube architecture for the medium number of nodes in a system.

REFERENCES

• 1: C K Baru , S Y W Su, The architecture of SM3: A dynamically partitionable multicomputer system, IEEE Transactions on Computers, v.35 n.9, p.790-802, Sept. 1986 [doi>10.1109/TC.1986.1676839]
• 2: Boral, H., DeWitt, D. J., Friedland, D., Jarrell, N. F., and Wilkinson, W. K., "The Implementation of the Database Machine DIRECT," IEEE Transactions on Software Engineering, vol. SE-8, no. 6, pp. 533- 543, November 1982.
• 3: Britton Lee Inc., "IDM 500: Intelligent Database Machine Product Description," Britton Lee, Inc., 1981.
• 4: R. H. Canaday , R. D. Harrison , E. L. Ivie , J. L. Ryder , L. A. Wehr, A back-end computer for data base management, Communications of the ACM, v.17 n.10, p.575-582, Oct. 1974 [doi>10.1145/355620.361172]
• 5: Cesarini, F., De Luca Cardillo, D., and Soda, G., "An Assessment of the Query-Processing Capability of DBMAC," Advanced Database Machine Architecture, David K. Hsiao, (ed.), Prentice-Hall, Englewood Cliffs, NJ., pp. 109-129, 1983.
• 6: Alvin M. Despain , David A. Patterson, X-Tree: A tree structured multi-processor computer architecture, Proceedings of the 5th annual symposium on Computer architecture, p.144-151, April 03-05, 1978 [doi>10.1145/800094.803041]
• 7: David J. DeWitt , Robert H. Gerber , Goetz Graefe , Michael L. Heytens , Krishna B. Kumar , M. Muralikrishna, GAMMA - A High Performance Dataflow Database Machine, Proceedings of the 12th International Conference on Very Large Data Bases, p.228-237, August 25-28, 1986
• 8: O. Frieder, Database processing on a cube-connected multicomputer, University of Michigan, Ann Arbor, MI, 1987
• 9: Hsiao, D. K., et al, Whe Implementation of a Multi-backend Database System (MDBS): Part I - An Exercise in Database Software Engineering," Advance, d Database Machine Architecture, D. K. Hsiao (ed.), Prentice-Hall, Englewood Cliffs, N.J., 1983, pp. :300- 326.
• 10: Intel Corporation, "Guild to iDBP," Order Number: 222104, Intel Corporation, 1982.
• 11: Kitsuregawa, M., Tanaka, H., and Moto-Oka, T., "Memory Management Algorithms in Pipeline Merge Sorter," Proceedings of the Fourth International Workshop on Database Machines, DeWitt, D. J., and Boral, H. (ed.), Springer-Verlag, N.Y., 1985, pp. 21)8-232.
• 12: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 13: Missikoff, M., and Terranova, M., "The Architecture of a Relational Database Computer Known as DBMAC," Advanced Database Machine Architecture, D. K. Hsiao, (ed.), Prentice-Hail, Englewood Cliffs, N.H., 1983, pp. 87-108.
• 14: Sekino, A., Takeuchi, K., Makino, T., Doi, T., Goto, T., Hakozaki, K., "Design Considerations for an Information Query Computer," Proceedings of the international Workshop on Database Machines, San Diego, Calif., September 1982.
• 15: Roger K. Shultz , Roy J. Zingg, Response Time Analysis of Multiprocessor Computers for Database Support, ACM Transactions on Database Systems (TODS), v.9 n.1, p.100-132, March 1984 [doi>10.1145/348.318589]
• 16: Su, S. Y. W., Lupkiewicz, S., lx~, C., Lo, D. H., and Doty, K. L., "MICRONET: A Microcomputer Network System for Managing Distributed Relational Databases," Proceedings of the Fourth International Conference on Very Large Data Bases, Berlin, West Germy, 1978, pp. 288-298.
• 17: Teradata Corporation, "DBC/1012 Data Base Computer Concepts and Fadlities," Release 1.1, OY2~1-91, Los Angeles, Calif., 1984.
• 18: Uemura, S, Yuba, T., Kokubu, A., Ooomote, R., and Sugawara, Y., "The Design and Implementation of a Magnetic-bubble Database Machine," information Processing 80, S. H. Lavington (ed.) North-Holland Publishing Co., Amsterdam, Netherlands, 1980, pp. 433-438.
• 19: 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:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.6 Database Machines

General Terms:
Algorithms, Design, Measurement, Performance, Theory