Pipelined hash-join on multithreaded architectures

ABSTRACT

Multi-core and multithreaded processors present both opportunities and challenges in the design of database query processing algorithms. Previous work has shown the potential for performance gains, but also that, in adverse circumstances, multithreading can actually reduce performance. This paper examines the performance of a pipeline of hash-join operations when executing on multithreaded and multicore processors. We examine the optimal number of threads to execute and the partitioning of the workload across those threads. We then describe a buffer-management scheme that minimizes cache conflicts among the threads. Additionally we compare the performance of full materialization of the output at each stage in the pipeline versus passing pointers between stages.

REFERENCES

• 1: Intel multi-core processor architecture development backgrounder. Intel White Paper, 2005.
• 2: Multi-core processors -- the next evolution in computing. AMD White Paper, 2005.
• 3: Throughput computing: Changing the economics and ecology of the data center with innovative SPARC® technology. Sun Microsystems White Paper, November 2005.
• 4: Anastassia Ailamaki , David J. DeWitt , Mark D. Hill , David A. Wood, DBMSs on a Modern Processor: Where Does Time Go?, Proceedings of the 25th International Conference on Very Large Data Bases, p.266-277, September 07-10, 1999
• 5: Doug Burger , James R. Goodman, Billion-Transistor Architectures: There and Back Again, Computer, v.37 n.3, p.22-28, March 2004 [doi>10.1109/MC.2004.1273999]
• 6: D. Carmean. Data management challenges on new computer architectures. In First Int'l Workshop on Data Management on New Hardware (DaMoN), June 2005. Oral Presentation.
• 7: Shimin Chen , Anastassia Ailamaki , Phillip B. Gibbons , Todd C. Mowry, Improving Hash Join Performance through Prefetching, Proceedings of the 20th International Conference on Data Engineering, p.116, March 30-April 02, 2004
• 8: Susan J. Eggers , Joel S. Emer , Henry M. Levy , Jack L. Lo , Rebecca L. Stamm , Dean M. Tullsen, Simultaneous Multithreading: A Platform for Next-Generation Processors, IEEE Micro, v.17 n.5, p.12-19, September 1997 [doi>10.1109/40.621209]
• 9: Philip Garcia , Henry F. Korth, Database hash-join algorithms on multithreaded computer architectures, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy [doi>10.1145/1128022.1128055]
• 10: P. C. Garcia. Optimizing database algorithms for modern computer architectures. Master's thesis, August 2005. http://www.cse.lehigh.edu/~pcg2/thesis.pdf.
• 11: Naga Govindaraju , Jim Gray , Ritesh Kumar , Dinesh Manocha, GPUTeraSort: high performance graphics co-processor sorting for large database management, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142511]
• 12: Goetz Graefe, Encapsulation of parallelism in the Volcano query processing system, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.102-111, May 23-26, 1990, Atlantic City, New Jersey, United States
• 13: W. Daniel Hillis , Guy L. Steele, Jr., Data parallel algorithms, Communications of the ACM, v.29 n.12, p.1170-1183, Dec. 1986 [doi>10.1145/7902.7903]
• 14: R. Kalla, B. Sinharoy, and J. M. Tendler. IBM Power5 chip: A dual-core multithreaded processor. 2004.
• 15: M. Kitsuregawa, H. Tanaka, and T. Moto-Oka. Application of hash to data base machine and its architecture. In New Generation Computing, volume 1, pages 63--74, 1983.
• 16: D. T. Marr, F. Binns, D. L. Hill, G. Hinton, D. A. Koufaty, J. A. Miller, and M. Upton. Hyper-threading technology architecture and microarchitecture. Intel Technology Journal, (Q1):4--15, 2002.
• 17: F. Mueller. Pthreads library interface, 1993.
• 18: S. Oks. Be aware: To hyper or not to hyper. Slava Oks Weblog http://blogs.msdn.com/slavao/archive/-2005/11/12/492119.aspx, Nov 2005.
• 19: P. S. Otellini. Multi-core enables performance without power penalties. In Intel Developer Forum Keynote, http://www.embedded-controleurope.com/pdf/-ecedec05p26.pdf, 2005.
• 20: 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
• 21: D. Towner and D. May. The 'uniform heterogeneous multi-threaded' processor architecture. In A. Chalmers, M. Mirmehdi, and H. Muller, editors, Communicating Process Architectures - 2001, pages 103--116. IOS Press, September 2001.
• 22: Dean M. Tullsen , Susan J. Eggers , Joel S. Emer , Henry M. Levy , Jack L. Lo , Rebecca L. Stamm, Exploiting choice: instruction fetch and issue on an implementable simultaneous multithreading processor, Proceedings of the 23rd annual international symposium on Computer architecture, p.191-202, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 23: Dean M. Tullsen , Susan J. Eggers , Henry M. Levy, Simultaneous multithreading: maximizing on-chip parallelism, Proceedings of the 22nd annual international symposium on Computer architecture, p.392-403, June 22-24, 1995, S. Margherita Ligure, Italy
• 24: Jingren Zhou , John Cieslewicz , Kenneth A. Ross , Mihir Shah, Improving database performance on simultaneous multithreading processors, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway