Vector Referencing Oriented Platform-Oblivious In-Memory Join Optimization Technique
Author:
Affiliation:

Clc Number:

TP311

Fund Project:

National Natural Science Foundation of China (61732014, 61772533);National High Technology Research and Development Program of China (863) (2015AA015307);the Basic Research Funds in Renmin University of China from the Central Government (16XNLQ02)

  • Article
  • | |
  • Metrics
  • |
  • Reference [27]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    Graph analysis database such as MapD employs the emerging manycore architecture GPU and Phi processors to support high performance analytical processing, where the join operation is still the performance bottleneck when facing complex data schemas. In recent years, as heterogeneous processors come to be main-stream high performance computing platforms, the researches of in-memory join performance extend the focuses from multicore to the emerging manycore platforms. However those efforts have not uncover the inner relationships among join algorithm performance, join dataset size and hardware architectures, and cannot provide sufficient join selection strategies for databases under the future heterogeneous processor platforms. This paper targets in-memory join optimization techniques on multicore, Xeon Phi and GPU processor platforms. By optimizing hash table design, this work uses vector mapping instead of hash mapping to eliminate the hashing overhead effects for performance, so that the in-memory join performance characteristics influenced can be measured by hardware factors such as multicore cache size, Xeon Phi cache size, Xeon Phi simultaneous multi-threading mechanism, and GPU SIMT (single instruction multiple threads) mechanism. The experimental results show that caching and simultaneous massive-threading mechanism are key factors to improve in-memory join algorithm performance. Caching mechanism performs well for cache fit join operations, the simultaneous massive-threading mechanism of GPU does well for big table joins, and Xeon Phi achieves the highest performance for L2 cache fit joins. The experimental results also exploit the relationship between in-memory join performance and heterogeneous processor hardware features, and provide optimization policy for in-memory database query optimizer on future heterogeneous processor platforms.

    Reference
    [1] https://www.mapd.com/
    [2] Root C, Mostak T. MapD:A GPU-powered big data analytics and visualization platform. In:Proc. of the SIGGRAPH. Anaheim, 2016. 73:1-73:2.[doi:10.1145/2897839.2927468]
    [3] https://www.top500.org/lists/2016/11/
    [4] https://www.top500.org/green500/lists/2016/11/
    [5] Schuh S, Chen X, Dittrich J. An experimental comparison of thirteen relational equi-joins in main memory. In:Proc. of the SIGMOD. New York:ACM Press, 2016. 1961-1976.[doi:10.1145/2882903.2882917]
    [6] Richter S, Alvarez V, Dittrich J. A seven-dimensional analysis of Hashing methods and its implications on query processing. Proc. of the VLDB Endowment, 2015,9(3):96-107.[doi:10.14778/2850583.2850585]
    [7] Blanas S, Li Y, Patel JM. Design and evaluation of main memory Hash join algorithms for multi-core CPUs. In:Proc. of the SIGMOD. New York:ACM Press, 2011. 37-48.[doi:10.1145/1989323.1989328]
    [8] Balkesen C, Teubner J, Alonso G, OzsuT. Main-Memory Hash joins on multi-core CPUs:Tuning to the underlying hardware. In:Proc. of ICDE. Washington:IEEE Computer Society, 2013. 362-373.[doi:10.1109/ICDE.2013.6544839]
    [9] Albutiu MC, Kemper A, Neumann T. Massively parallel sort-merge joins in main memory multi-core data-base systems. Proc. of the VLDB Endowment, 2012,5(10):1064-1075.[doi:10.14778/2336664.2336678]
    [10] Lang H, Leis V, AlbutiuMC, Neumann T, Kemper A. Massively parallel NUMA-aware Hash joins. In:Proc. of the IMDM@VLDB. 2013. 3-14.[doi:10.1007/978-3-319-13960-9_1]
    [11] Pagh R, Wei Z, Yi K, Zhang Q. Cache-Oblivious Hashing. In:Proc. of the PODS. Indianapolis. 2010. 297-304.[doi:10.1145/1807085.1807124]
    [12] Mitzenmacher M. A new approach to analyzing robin hood Hashing. In:Proc. of the ANALCO. 2016. 10-24.[doi:10.1137/1.9781611974324.2]
    [13] Pagh R. Cuckoo Hashing. In:Proc. of the Encyclopedia of Algorithms. 2016. 478-481.[doi:10.1007/3-540-44676-1_10]
    [14] Barber R, Lohman GM, Pandis I, Raman V, Sidle R, Attaluri GK, Chainani N, Lightstone S, Sharpe D. Memory-Efficient Hash joins. Proc. of the VLDB Endowment, 2014,8(4):353-364.[doi:10.14778/2735496.2735499]
    [15] Zhang Y, Zhou X, Zhang Y, Zhang Y, Su M, Wang S. Virtual denormalization via array index reference for main memory OLAP. IEEE Trans. on Knowledge and Data Engineering, 2016,28(4):1061-1074.[doi:10.1109/TKDE.2015.2499199]
    [16] He BS, Yang K, Fang R, Lu M, Govindaraju NK, Luo Q, Sander PV. Relational joins on graphics processors. In:Proc. of the SIGMOD. New York:ACM Press, 2008. 511-524.[doi:10.1145/1376616.1376670]
    [17] Yuan Y, Lee R, Zhang X. The Yin and Yang of processing data warehousing queries on GPU devices. Proc. of the VLDB Edowment, 2013,6(10):817-828.[doi:10.14778/2536206.2536210]
    [18] Pirk H, Manegold S, Kersten M. Accelerating foreign-key joins using asymmetric memory channels. In:Bordawekar R, Lang CA, eds. Proc. of the Int'l Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures (ADMS). 2011. 27-35.
    [19] He J, Lu M, He B. Revisiting co-processing for Hash joins on the coupled CPU-GPU architecture. Proc. of the VLDB Endowment, 2013,6(10):889-900.[doi:10.14778/2536206.2536216]
    [20] Jha S, He BS, Lu M, Cheng XT, Huynh HP. Improving main memory Hash joins on intel Xeon Phi processors:An experimental approach. Proc. of the VLDB Endowment, 2015,8(6):642-653.[doi:10.14778/2735703.2735704]
    [21] Polychroniou O, Raghavan A, Ross KA. Rethinking SIMD vectorization for in-memory databases. In:Proc. of the SIGMOD. New York:ACM Press, 2015. 1493-1508.[doi:10.1145/2723372.2747645]
    [22] Halstead RJ, Absalyamov I, Najjar WA, Tsotras VJ. FPGA-Based multithreading for in-memory Hash joins. In:Proc. of CIDR. 2015.
    [23] Zukowski M, Boncz PA. Vectorwise:Beyond column stores. IEEE Data Engineering Bulletin, 2012,35(1):21-27.
    [24] Zhang Y, Zhang YS, Chen H, Wang S. OLAP Foreign Join Algorithm for MIC Coprocessor. Ruan Jian Xue Bao/Journal of Software, 2017,28(3):490-501(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5156.htm[doi:10.13328/j. cnki.jos.005156]
    [25] Lee JG, Attaluri GK, Barber R. Joins on encoded and partitioned data. Proc. of the VLDB Endowment, 2014,7(13):1355-1366.
    附中文参考文献:
    [24] 张宇,张延松,陈红,王珊.一种基于众核架构Phi协处理器的内存OLAP外键连接算法.软件学报,2017,28(3):490-501. http://www.jos.org.cn/1000-9825/5156.htm[doi:10.13328/j. cnki.jos.005156]
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

张延松,张宇,王珊.基于向量引用Platform-Oblivious内存连接优化技术.软件学报,2018,29(3):883-895

Copy
Share
Article Metrics
  • Abstract:3779
  • PDF: 5696
  • HTML: 3010
  • Cited by: 0
History
  • Received:July 31,2017
  • Revised:September 05,2017
  • Online: December 05,2017
You are the first2044900Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063