Using Intel Xeon Phi coprocessors for execution of natural join on compressed data

Authors

DOI:

https://doi.org/10.26089/NumMet.v16r450

Keywords:

columnar data representation, columnar indexes, database coprocessor, interval fragmentation, parallel database system, cluster computing systems with many-core accelerators, Intel Xeon Phi

Abstract

A database coprocessor for high-performance cluster computing systems with many-core accelerators is described. This coprocessor uses distributed columnar indexes with interval fragmentation. The operation of the coprocessor engine is considered by an example of natural join processing. The parallel decomposition of natural join operator is performed using distributed columnar indexes. The proposed approach allow one to perform relational operators on computing clusters without massive data exchange. The results of computational experiments on Intel Xeon Phi confirm the efficiency of the developed methods and algorithms.

Author Biographies

E.V. Ivanova

L.B. Sokolinsky

South Ural State University
• Vice-Rector for Informatization

References

  1. L. B. Sokolinsky, Parallel Data Base Systems (Mosk. Gos. Univ., Moscow, 2013) [in Russian].
  2. L. B. Sokolinsky, “Design and Evaluation of Database Multiprocessor Architecture with High Data Availability,” in Proc. 12th Int. Workshop on Database and Expert Systems Applications, Munich, Germany, September 3-7, 2001 (IEEE Press, Washington, 2001), pp. 115-120.
  3. L. B. Sokolinsky, “Operating System Support for a Parallel DBMS with an Hierarchical Shared-Nothing Architecture,” in Proc. 3-rd East European Conf. on Advances in Databases and Information Systems, Maribor, Slovenia, September 13-16, 1999 (Institute of Informatics, Maribor, 1999), pp. 38-45.
  4. L. B. Sokolinsky and M. L. Tsymbler, “Principles of a File Management System in the Parallel Omega DBMS for MVS-100,” Vestn. Chelyabinskii Gos. Univ., No. 2, 78-96 (1999).
  5. J. Fang, A. L. Varbanescu, and H. Sips, “Sesame: A User-Transparent Optimizing Framework for Many-Core Processors,” in Proc. 13th IEEE/ACM Int. Symp. on Cluster, Cloud and Grid Computing, Delft, Netherlands, May 13-16, 2013 (IEEE Press, New York, 2013), pp. 70-73.
  6. M. Scherger, “Design of an In-Memory Database Engine Using Intel Xeon Phi Coprocessors,” in Proc. Int. Conf. on Parallel and Distributed Processing Techniques and Applications, Las Vegas, USA, July 21-24, 2014 (CSREA Press, Las Vegas, 2014), pp. 21-27.
  7. S. Breß, F. Beier, H. Rauhe, et al., “Efficient Co-Processor Utilization in Database Query Processing,” Information Systems 38 (8), 1084-1096 (2013).
  8. K. Yu. Besedin and P. S. Kostenetskiy, “Application of Multicore Coprocessors in Parallel Database Systems,” in Proc. Int. Conf. on Parallel Computational Technologies, Chelyabinsk, Russia, April 1-5, 2013 (South Ural State Univ., Chelyabinsk, 2013), p. 583.
  9. S. Khoshafian, G. P. Copeland, T. Jagodis, et al., “A Query Processing Strategy for the Decomposed Storage Model,” in Proc. 3rd Int. Conf. on Data Engineering, Los Angeles, USA, February 3-5, 1987 (IEEE Press, Washington, 1987), pp. 636-643.
  10. M. Stonebraker, D. J. Abadi, A. Batkin, et al., “C-Store: A Column-Oriented DBMS,” in Proc. 31st Int. Conf. on Very Large Data Bases, Trondheim, Norway, August 30-September 2, 2005 (ACM Press, New York, 2005), pp. 553-564.
  11. P. Boncz, M. Zukowski, and N. Nes, “MonetDB/X100: Hyper-Pipelining Query Execution,” in Electronic Proc. 2nd Biennial Conf. on Innovative Data Systems Research, Asilomar, USA, January 4-7, 2005 , pp. 225-237.
    http://www.cidrdb.org/cidr2005/call.html . Cited October 27, 2015.
  12. E. V. Ivanova and L. B. Sokolinsky, “Using Distributed Columnar Indexes for Implementing Queries to Very Large Data Bases,” in Proc. Int. Conf. on Parallel Computational Technologies, Rostov-on-Don, Russia, March 31-April 4, 2014 (South Ural State Univ., Chelyabinsk, 2014), pp. 270-275.
  13. E. V. Ivanova, “Using Distributed Columnar Hash Indexes for Implementing Queries to Very Large Data Bases,” in Proc. Int. Conf. on Scientific Services and Internet, Abrau-Dyurso, Russia, September 22-27, 2014 (Mosk. Gos. Univ., Moscow, 2014), pp. 102-104.
  14. E. V. Ivanova and L. B. Sokolinsky, “Decomposition of Intersection and Join Operations Based on the Domain-Interval Fragmented Column Indices,” Vestn. South Ural State Univ. Ser. Vychisl. Mat. Inf. 4 (1), 44-56 (2015).
  15. H. Garcia-Molina, J. D. Ullman, and J. Widom, Database Systems: The Complete Book (Prentice Hall, Upper Saddle River, 2002; Vil’yams, Moscow, 2004).
  16. A Prototype of the DBMS Coprocessor System Using Column Indices Based on Domain-Interval Fragmentation.
    https://github.com/elena-ivanova/colomnindices . Cited October 29, 2015.
  17. J. Gray, P. Sundaresan, S. Englert, et al., “Quickly Generating Billion-Record Synthetic Databases,” in Proc. ACM SIGMOD Int. Conf. Management of Data, Minneapolis, USA, May 24-27, 1994 (ACM Press, New York, 1994), pp. 243-252.
  18. G. Roelofs, J. Gailly, and M. Adler, “Zlib Home Page,”
    http://www.zlib.net . Cited October 29, 2015.

Published

16-09-2015

How to Cite

Иванова Е.В., Соколинский Л.Б. Using Intel Xeon Phi Coprocessors for Execution of Natural Join on Compressed Data // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2015. 16. 534-542. doi 10.26089/NumMet.v16r450

Issue

Section

Section 1. Numerical methods and applications