Exploiting Internal Parallelism of SSD for Hash Join

YANG Lianghuai; ZHANG Ting; FAN Yulei; GONG Weihua; YU Jian

doi:10.1049/cje.2019.06.009

Volume 28 Issue 5

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2019 > 28(5): 889-898

YANG Lianghuai, ZHANG Ting, FAN Yulei, et al., “Exploiting Internal Parallelism of SSD for Hash Join,” Chinese Journal of Electronics, vol. 28, no. 5, pp. 889-898, 2019, doi: 10.1049/cje.2019.06.009

Citation:

YANG Lianghuai, ZHANG Ting, FAN Yulei, et al., “Exploiting Internal Parallelism of SSD for Hash Join,” Chinese Journal of Electronics, vol. 28, no. 5, pp. 889-898, 2019, doi: 10.1049/cje.2019.06.009

Citation:

PDF( 5148 KB)

Exploiting Internal Parallelism of SSD for Hash Join

doi: 10.1049/cje.2019.06.009

1.
School of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China;
2.
School of Computing and Mathematical Sciences, Auckland University of Technology, Auckland, New Zealand

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

Abstract

Abstract

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.
- Hash join,
- Internal parallelism,
- I/O granularity,
- Queue depth,
- Solid state drive

FullText(HTML)

References(21)

References

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.

Relative Articles

Supplements(0)

Cited By

Proportional views