Query co-planning for shared execution in key-value stores
DOI:
https://doi.org/10.5753/jidm.2021.1946Keywords:
range queries, database, key-value stores, embedded data stores, shared executionAbstract
Key-value stores propose a straightforward yet powerful data model. Data is modeled using key-value pairs where values can be arbitrary objects and 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. Our data structure helps us co-planning and co-executing multiple range queries together and reduces redundant work. This results in executing workloads more efficiently and overall increased throughput, as we show in our evaluation.
Downloads
References
Chandramouli, B., Prasaad, G., Kossmann, D., Levandoski, J., Hunter, J., and Barnett, M. Faster: A concurrent key-value store with in-place updates. In 2018 ACM SIGMOD International Conference on Management of Data (SIGMOD ’18), Houston, TX, USA, 2018 ACM SIGMOD International Conference on Management of Data (SIGMOD ’18), Houston, TX, USA ed. ACM, 2018.
Dayan, N., Athanassoulis, M., and Idreos, S. Monkey: Optimal navigable key-value store. In Proceedings of the 2017 ACM International Conference on Management of Data. SIGMOD ’17. Association for Computing Machinery, New York, NY, USA, 2017.
Dayan, N. and Idreos, S. Dostoevsky: Better space-time trade-offs for lsm-tree based key-value stores via adaptive removal of superfluous merging. In Proceedings of the 2018 International Conference on Management of Data. SIGMOD ’18. Association for Computing Machinery, New York, NY, USA, 2018.
Escriva, R., Wong, B., and Sirer, E. G. Hyperdex: A distributed, searchable key-value store. SIGCOMM Comput. Commun. Rev. 42 (4), Aug., 2012.
Finkelstein, S. J. Common subexpression analysis in database applications. In Proceedings of the 1982 ACM SIGMOD, M. Schkolnick (Ed.), 1982.
Giannikis, G., Alonso, G., and Kossmann, D. Shareddb: Killing one thousand queries with one stone. Proc. VLDB Endow. 5 (6), 2012.
Giannikis, G., Makreshanski, D., Alonso, G., and Kossmann, D. Shared workload optimization. Proc. VLDB ndow. 7 (6), 2014.
Giannikis, G., Unterbrunner, P., Meyer, J., Alonso, G., Fauser, D., and Kossmann, D. Crescando. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data. SIGMOD ’10.
Inc., F. rocksdb, 2020.
Informatica, C. W. duckdb, 2020.
Li, B., Ruan, Z., Xiao, W., Lu, Y., Xiong, Y., Putnam, A., Chen, E., and Zhang, L. Kv-direct: High-performance in-memory key-value store with programmable nic. In Proceedings of the 26th Symposium on Operating Systems Principles, Proceedings of the 26th Symposium on Operating Systems Principles ed. ACM, 2017.
Marroquin, R., Müller, I., Makreshanski, D., and Alonso, G. Pay one, get hundreds for free: Reducing cloud costs through shared query execution. In ACM SoCC 2018, 2018.
Pilman, M., Bocksrocker, K., Braun, L., Marroquín, R., and Kossmann, D. Fast scans on key-value stores. Proc. VLDB Endow. 10 (11), Aug., 2017.
Sellis, T. K. Multiple-query optimization. ACM Trans. Database Syst. 13 (1), 1988.
Sivasubramanian, S. Amazon dynamodb: A seamlessly scalable non-relational database service. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. SIGMOD ’12. Association for Computing Machinery, New York, NY, USA, 2012.
Unterbrunner, P., Giannikis, G., Alonso, G., Fauser, D., and Kossmann, D. Predictable performance for unpredictable workloads. Proc. VLDB Endow. 2 (1), 2009.
Wang, X., Olston, C., Sarma, A. D., and Burns, R. Coscan: Cooperative scan sharing in the cloud. In Proceedings of the 2nd ACM Symposium on Cloud Computing. SOCC ’11. New York, NY, USA.
