Analyzing the Performance of Spatial Indices on Flash Memories using a Flash Simulator

• Anderson Chaves Carniel Universidade de São Paulo http://orcid.org/0000-0002-8297-9894
• Tamires Brito da Silva Universidade de São Paulo
• Kairo Luiz dos Santos Bonicenha Universidade de São Paulo
• Ricardo Rodrigues Ciferri Universidade Federal de São Carlos
• Cristina Dutra de Aguiar Ciferri Universidade de São Paulo

DOI: https://doi.org/10.5753/sbbd.2017.171434

Resumo

Spatial databases improve the spatial query processing by employing spatial indices. Due to the advantages of flash memories over magnetic disks like faster reads and writes, there is a special interest in managing spatial indices in these memories. However, many flash memories employ a Flash Translation Layer that does not provide open access to many important statistics, restricting the performance analysis of spatial indices. Flash simulators are promising tools to improve the performance analysis of spatial indices. In this paper, we analyze the performance of several distinct configurations of spatial indices by using a flash simulator and a real flash-based solid state drive. As a result, we provide correlations between these results to check the accuracy of a flash simulator in the spatial indexing context. In addition, we discuss the possibility of using a flash simulator as a first step for benchmarking spatial indices. That is, we check if the results provided by a flash simulator can be used to decrease the number of configurations to be evaluated in real flash memories, reducing the required time of an empirical analysis.

Palavras-chave: Spatial Indices, Flash Memories, Flash Simulator

Referências

Brayner, A. and Monteiro Filho, J. M. (2016). Hardware-aware database systems: A new era for database technology is coming - vision paper. In Brazilian Symp. on Databases, pages 187–192.

Carniel, A. C., Ciferri, R. R., and Ciferri, C. D. A. (2016a). Experimental evaluation of spatial indices with FESTIval. In Brazilian Symp. on Databases - Demos, pages 123–128.

Carniel, A. C., Ciferri, R. R., and Ciferri, C. D. A. (2016b). The performance relation of spatial indexing on hard disk drives and solid state drives. In Brazilian Symp. on GeoInformatics, pages 263–274.

Carniel, A. C., Ciferri, R. R., and Ciferri, C. D. A. (2017). A generic and efficient framework for spatial indexing on flash-based solid state drives. In European Conference on Advances in Databases and Information Systems.

Chung, T.-S., Park, D.-J., Park, S., Lee, D.-H., Lee, S.-W., and Song, H.-J. (2009). A survey of flash translation layer. Journal of Systems Architecture: the EUROMICRO Journal, 55(5-6):332–343.

Dong, X., Xu, C., Xie, Y., and Jouppi, N. (2012). NVSim: A circuit-level performance, energy, and area model for emerging nonvolatile memory. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 31(7):994–1007.

Emrich, T., Graf, F., Kriegel, H.-P., Schubert, M., and Thoma, M. (2010). On the impact of flash SSDs on spatial indexing. In Int. Workshop on Data Management on New Hardware, pages 3–8.

Gaede, V. and Günther, O. (1998). Multidimensional access methods. ACM Computing Surveys, 30(2):170–231.

Güting, R. H. (1994). An introduction to spatial database systems. The VLDB Journal, 3(4):357–399.

Jin, P., Xie, X., Wang, N., and Yue, L. (2015). Optimizing R-tree for flash memory. Expert Systems with Applications, 42(10):4676–4686.

Jung, M. and Kandemir, M. (2013). Revisiting widely held SSD expectations and rethinking system-level implications. In ACM SIGMETRICS Int. Conf. on Measurement and Modeling of Computer Systems, pages 203–216.

Kim, Y., Tauras, B., Gupta, A., and Urgaonkar, B. (2009). FlashSim: A simulator for NAND flash-based solid-state drives. In Int. Conf. on Advances in System Simulation, pages 125–131.

Lv, Y., Li, J., Cui, B., and Chen, X. (2011). Log-Compact R-tree: An efficient spatial index for SSD. In Int. Conf. on Database Systems for Advanced Applications, pages 202–213.

Mittal, S. and Vetter, J. S. (2016). A survey of software techniques for using non-volatile memories for storage and main memory systems. IEEE Trans. on Parallel and Distributed Systems, 27(5):1537–1550.

Sarwat, M., Mokbel, M. F., Zhou, X., and Nath, S. (2013). Generic and efficient framework for search trees on flash memory storage systems. GeoInformatica, 17(3):417–448.

Su, X., Jin, P., Xiang, X., Cui, K., and Yue, L. (2009). Flash-DBSim: A simulation tool for evaluating flash-based database algorithms. In IEEE Int. Conf. on Computer Science and Information Technology, pages 185–189.

Wu, C.-H., Chang, L.-P., and Kuo, T.-W. (2003). An efficient R-tree implementation over flash-memory storage systems. In ACM SIGSPATIAL Int. Conf. on Advances in Geographic Information Systems, pages 17–24.