Query co-planning for shared execution in Key-Value Stores

• Josue Joel Ttito Universidad Católica San Pablo
• Renato Marroquin Oracle Labs
• Sergio Lifschitz Pontifícia Universidade Católica do Rio de Janeiro https://orcid.org/0000-0003-3073-3734

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

Resumo

Key-value stores propose a very simple yet powerful data model. Data is modeled using key-value pairs where values can be arbitrary objects and can be written/read using the key associated with it. In addition to their simple interface, such data stores also provide read operations such as full and range scans. However, due to the simplicity of its interface, trying to optimize data accesses becomes challenging. This work aims to enable the shared execution of concurrent range and point queries on key-value stores. Thus, reducing the overall data movement when executing a complete workload. To accomplish this, we analyze different possible data structures and propose our variation of a segment tree, Updatable Interval Tree. This data structure helps us co-planning and co-executing multiple range queries together, as we show in our evaluation.

Palavras-chave: Databases, Key-Value Stores, Query co-planning

Referências

Bast, H., Buchhold, B., Haussmann, E. Semantic search on text and knowledge bases. Found. and Trends® in Info. Retr., 10(1), (2016), 119-271. DOI: 10.1561/1500000032

Bergamaschi, S., Guerra, F., Interlandi, M., Trillo-Lado, R., Velegrakis, Y. Combining user and database perspective for solving keyword queries over relational databases. Inf. Syst. 55, C (Jan. 2016), 1-19. DOI: 10.1016/j.is.2015.07.005

García, G.M., Izquierdo, Y.T., Menendez, E., Dartayre, F., Casanova, M.A. RDF Keyword-based Query Technology Meets a Real-World Dataset. In: Proc. 20th Int’l. Conf. on Extending Database Technology (EDBT 2017), pp. 656-667.

García, G.M. A Keyword-based Query Processing Method for Datasets with Schemas. Thesis presented to the Graduate Program in Informatics, PUC-Rio (March 2020). DOI: https://doi.org/10.17771/PUCRio.acad.48728

Han, S., Zou, L., Yu, X., Zhao, D. Keyword Search on RDF Graphs - A Query Graph Assembly Approach. In: Proc. 2017 ACM Conf. on Information and Knowledge Management (CIKM 2017), pp. 227-236. DOI: 10.1145/3132847.3132957

Izquierdo, Y.T., García, G.M., Menendez, E.S., Casanova, M.A., Dartayre, F., Levy, C.H., QUIOW: A Keyword-Based Query Processing Tool for RDF Datasets and Relational Databases. In: DEXA 2018, LNCS 11030 (2018), pp. 259-269. DOI: 10.1007/978-3-319-98812-2_22

Izquierdo, Y.T., Casanova, M.A., García, G.M., Dartayre, F., Levy, C.H. Keyword Search over Federated RDF Datasets. In: Proc. ER Forum 2017 and ER Demo track co-located with the 36th Int’l. Conf. on Conceptual Modelling (ER 2017), CEUR Workshop Proc., Vol. 1979, CEUR-WS.org

Mello, L.E. et al. Opening Brazilian COVID-19 patient data to support world research on pandemics (July 30, 2020). DOI: 10.5281/zenodo.3966427

Oliveira, P., Silva, A., Moura, E. Ranking Candidate Networks of relations to improve keyword search over relational databases. In: Proc. IEEE 31st Int’l. Conf. on Data Engineering (ICDE 2015), pp. 399-410. DOI: 10.1109/ICDE.2015.7113301

Tran, T., Wang, H., Rudolph, S., Cimiano, P. Top-k exploration of query candidates for efficient keyword search on graph-shaped (rdf) data. In: Proc. 2009 IEEE Int’l. Conf. on Data Engineering (ICDE 2009), pp. 405-416. DOI: 10.1109/ICDE.2009.119