Open AccessQuery co-planning for shared execution in key-value stores
Author(s) -
Josué Joel Ttito,
Renato Marroquín,
Sérgio Lifschitz,
L. J. McGibbney,
José Talavera
Publication year - 2021
Publication title -
journal of information and data management
Language(s) - English
Resource type - Journals
ISSN - 2178-7107
DOI - 10.5753/jidm.2021.1946
Subject(s) - computer science , key (lock) , workload , interface (matter) , tree (set theory) , data structure , associative array , interval (graph theory) , distributed computing , operating system , programming language , mathematical analysis , mathematics , bubble , maximum bubble pressure method , combinatorics
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.