SPARQL Query Optimizations for GPU RDF Stores
Article Sidebar
Main Article Content
Abstract
The SPARQL query time optimization is one of the challenges for the Resource Description Framework (RDF) data store. Even though Graphic Processing Units (GPU) can be used to accelerate query processing, it has weaknesses from the GPU memory transfer overhead. In this work, we propose optimization techniques for the GPU RDF store. In particular, we present the query optimization technique, which results in a reduction in the memory transfer time. In particular, the first approach is to use an empty interval filter that considers the empty data range to eliminate unneeded data during the uploading process. Secondly, we provide the heuristic query execution planner for generating an execution plan which suits our GPU RDF store and the filter technique. Our experiments on the WatDiv benchmark show that the proposed methods perform well on benchmark queries. The total query processing time on GPU is improved on average by 30% compared to the random plan generators.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
References
P. Makpaisit and C. Chantrapornchai, “VEDAS: an efficient GPU alternative for store and query of large RDF data sets,” J. Big Data, vol. 8, no. 1, p. 125, 2021. [Online]. Available: https: //doi.org/10.1186/s40537-021-00513-y
Y. Kim, Y. Lee, and J. Lee, “An efficient approach to triple search and join of hdt processing using gpu,” in Proc. 7th Int. Conf. Adv. Databases Knowl. Data Appl, pp. 70–74, 2015.
C. Chantrapornchai and C. Choksuchat, “TripleID-Q: RDF Query Processing Framework Using GPU,” in IEEE Transactions on Parallel and Distributed Systems, vol. 29, no. 9, pp. 2121-2135, 1 Sept. 2018
F. Jamour, I. Abdelaziz, and P. Kalnis, “A demonstration of MAGiQ: matrix algebra approach for solving RDF graph queries,” Proceedings of the VLDB Endowment, vol. 11, pp. 1978–1981, 08 2018.
T. Ren, G. Rao, X. Zhang, and Z. Feng, “Srspg: A plugin-based spark framework for large-scale rdf streams processing on gpu,” in ISWC (Satellites), pp. 89–92, 2019.
X. Zhang, M. Zhang, P. Peng, J. Song, Z. Feng, and L. Zou, “gsmat: A scalable sparse matrixbased join for sparql query processing,” 2018.
Hendarmawan, M. Kuga, and M. Iida, “Streaming Accelerator Design for Regular Expression on CPU+FPGA Embedded System,” ECTI-CIT Transactions, vol. 16, no. 4, pp. 448–459, Oct. 2022.
T. Neumann and G. Moerkotte, “Characteristic sets: Accurate cardinality estimation for RDF queries with multiple joins,” 2011 IEEE 27th International Conference on Data Engineering, Hannover, Germany, pp. 984-994, 2011.
M. Meimaris, G. Papastefanatos, N. Mamoulis and I. Anagnostopoulos, “Extended Characteristic Sets: Graph Indexing for SPARQL Query Optimization,” 2017 IEEE 33rd International Conference on Data Engineering (ICDE), San Diego, CA, USA, pp. 497-508, 2017.
G. Selvaraj, C. Lutteroth and G. Weber, “Traveling Light — A Low-Overhead Approach for SPARQLQueryOptimization,”2021IEEE15th International Conference on Semantic Computing (ICSC), Laguna Hills, CA, USA, pp. 56-61, 2021.
P. Tsialiamanis, L. Sidirourgos, I. Fundulaki, V. Christophides, and P. Boncz, “Heuristics-based query optimisation for sparql,” in Proceedings of the 15th International Conference on Extending Database Technology, pp. 324–335, 2012.
M. Meimaris and G. Papastefanatos, “DistanceBased Triple Reordering for SPARQL Query Optimization,” 2017 IEEE 33rd International Conference on Data Engineering (ICDE), San Diego, CA, USA, pp. 1559-1562, 2017.
M. Stocker, A. Seaborne, A. Bernstein, C. Kiefer, and D. Reynolds, “Sparql basic graph pattern optimization using selectivity estimation,” in Proceedings of the 17th international conference on World Wide Web, pp. 595–604, 2008.
A. Abbas, P. Genev‘es, C. Roisin, and N. Laya ̈ıda,“Selectivityestimationforsparqltriple patterns with shape expressions,” in Web Engineering: 18th International Conference, ICWE 2018, C ́aceres, Spain, June 5-8, 2018, Proceedings 18. Springer, 2018, pp. 195–209.
K. Rabbani, M. Lissandrini, and K. Hose, “Optimizing sparql queries using shape statistics,” in Advances in Database Technology-24th International Conference on Extending Database Technology, EDBT 2021. OpenProceedings. org, 2021, pp. 505–510.
G.Aluc ̧,O.Hartig,M.T.O ̈zsu,andK.Daudjee, “Diversified stress testing of rdf data management systems,” in The Semantic Web–ISWC 2014: 13th International Semantic Web Conference, Riva del Garda, Italy, October 19-23, 2014. Proceedings, Part I 13. Springer, 2014, pp. 197–212.