YANG Lianghuai, ZHANG Ting, FAN Yulei, GONG Weihua, YU Jian. Exploiting Internal Parallelism of SSD for Hash Join[J]. Chinese Journal of Electronics, 2019, 28(5): 889-898. doi: 10.1049/cje.2019.06.009
Citation: YANG Lianghuai, ZHANG Ting, FAN Yulei, GONG Weihua, YU Jian. Exploiting Internal Parallelism of SSD for Hash Join[J]. Chinese Journal of Electronics, 2019, 28(5): 889-898. doi: 10.1049/cje.2019.06.009

Exploiting Internal Parallelism of SSD for Hash Join

doi: 10.1049/cje.2019.06.009
Funds:  This work is supported by the Zhejiang Provincial Natural Science Foundation (No.LY14F020017, No.LQ15F020007) and the National Natural Science Foundation of China (No.61070042).
More Information
  • Corresponding author: FAN Yulei (corresponding author) received the Ph.D.degree in computer science from Renmin University of China in 2014,and currently is a lecturer at School of Computer Science and Technology in Zhejiang University of Technology.His research interests include database systems,data stream and data mining.(Email:fyl815@zjut.edu.cn)
  • Received Date: 2017-01-12
  • Rev Recd Date: 2017-04-22
  • Publish Date: 2019-09-10
  • By regarding a Solid-state drive(SSD) as a black box and observing its external behavior instead of peeping into its internal details, we investigate how the factors of I/O granularity and I/O queue depth influence the throughput of an SSD through a series of experiments and relate to the internal parallelism of an SSD, and then propose the concept of Combination equivalence class (CEC) as the set of combination pairs of these two factors. A novel buffer allocation scheme for hash join over SSDs is invented by taking both factors into account. Extensive experiments demonstrate the effectiveness of our scheme.
  • loading
  • R. F. Freitasand and W. W. Wilcke, "Storage-class memory:The next storage system technology", IBM Journal of Research and Development, Vol.52, No.4, pp.439-448, 2008.
    N. Agrawal, V. Prabhakaran, T. Wobber, et al., "Design tradeoffs for SSD performance", Proc. of USENIX Technical Conference, pp.57-70, 2008.
    S. W. Lee and B. Moon, "Design of flash-based DBMS:An in-page logging approach", Proc. of SIGMOD Conference, pp.55-66, 2007.
    S. Lee, B. Moon, C. Park, et al., "A case for flash memory SSD in enterprise database applications", Proc. of SIGMOD Conference, pp.1075-1086, 2008.
    H. Kim and S. Ahn, "BPLRU:A buffer management scheme for improving random writes in flash storage", Proc. of USENIX Conference on File and Storage Technologies, pp. 1-14, 2008.
    G. J. Kim, S. C. Baek, H. S. Lee, et al., "LGeDBMS:A small DBMS for embedded system with flash memory", Proc. of Int'l Conf. on Very Large Data Bases, pp.1255-1258, 2006.
    M. Athanassoulis, A. Ailamaki, S. Chen, et al., "Flash in a DBMS:Where and how?", IEEE Data Eng. Bull., Vol.33, No.4, pp.28-34, 2011.
    I. Koltsidas and S. Viglas, "Data management over flash memory", Proc. of SIGMOD Conference, pp.1209-1212, 2011.
    F. Chen, R. Lee, X. Zhang, "Essential roles of exploiting internal parallelism of flash memory based solid state drives in high-speed data processing", Proc. of High Performance Computing Architecture, pp.266-277, 2011.
    F. Chen, D. A. Koufaty, X. Zhang, "Understanding intrinsic characteristics and system implications of flash memory based solid state drives", Proc. of SIGMETRICS/Performance, pp.181-192, 2009.
    M. Bjrling, P. Bonnet, L. Bouganim, et al.,"The necessary death of the block device interface", Proc. of Conference on Innovative Data Systems Research, 2013.
    S.-Y. Park, E. Seo, J.-Y. Shin, et al., "Exploiting internal parallelism of flash-based SSDs", Computer Architecture Letters, Vol.9, No.1, pp.9-12, 2010.
    W. Lai, Y. Fan, X. Meng, "Scan and join optimization by exploiting internal parallelism of flash-based solid state drives", Proc. of WAIM Conference, pp.381-392, 2013.
    C. Kim, E. Sedlar, J. Chhugani, et al., "Sort vs. hash revisited:Fast join implementation on modern multicore CPUs", Proc. of Int'l Conf. on Very Large Data Bases, pp.1378-1389, 2009.
    C. Balkesen, G. Alonso, J. Teubner, et al., "Multi-core, mainmemory joins:Sort vs. hash revisited", Proc. of Int'l Conf. on Very Large Data Bases, pp.85-96, 2014.
    D. Tsirogiannis, S. Harizopoulos, M. A. Shah, et al., "Query processing techniques for solid state drives", Proc. of SIGMOD Conference, pp.59-72, 2009.
    M. Shah, S. Harizopoulos, J. Wiener, et al., "Fast scans and joins using flash drives", Proc. of DaMoN Conference, pp.17-24, 2008.
    S. W. Lee, B. Moon and C. Park, "Advances in flash memory SSD technology for enterprise database applications", Proc. of SIGMOD Conference, pp.863-870, 2009.
    J. Kim, S. Seo, D. Jung, et al., "Parameter-aware I/O management for solid state disks", IEEE Transactions on Computers, Vol.61, No.5, pp.636-649, 2012.
    H. Roh, S. Park, S. Kim, et al., "B+ tree index optimization by exploiting internal parallelism of flash-based solid state drives", Proc. of Int'l Conf. on Very Large Data Bases, pp.286-297, 2012.
    D. DeWitt and R. Gerber, "Multiprocessor hash-based join algorithms", Proc. of Int'l Conf. on Very Large Data Bases, pp.151-164, 1985.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (152) PDF downloads(368) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return