{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T12:42:47Z","timestamp":1780058567282,"version":"3.54.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,8]]},"abstract":"<jats:p>Key-Value Stores (KVS) are becoming increasingly popular because they scale up and down elastically, sustain high throughputs for get\/put workloads and have low latencies. KVS owe these advantages to their simplicity. This simplicity, however, comes at a cost: It is expensive to process complex, analytical queries on top of a KVS because today's generation of KVS does not support an efficient way to scan the data. The problem is that there are conflicting goals when designing a KVS for analytical queries and for simple get\/put workloads: Analytical queries require high locality and a compact representation of data whereas elastic get\/put workloads require sparse indexes. This paper shows that it is possible to have it all, with reasonable compromises. We studied the KVS design space and built TellStore, a distributed KVS, that performs almost as well as state-of-the-art KVS for get\/put workloads and orders of magnitude better for analytical and mixed workloads. This paper presents the results of comprehensive experiments with an extended version of the YCSB benchmark and a workload from the telecommunication industry.<\/jats:p>","DOI":"10.14778\/3137628.3137659","type":"journal-article","created":{"date-parts":[[2017,9,7]],"date-time":"2017-09-07T13:35:53Z","timestamp":1504791353000},"page":"1526-1537","source":"Crossref","is-referenced-by-count":37,"title":["Fast scans on key-value stores"],"prefix":"10.14778","volume":"10","author":[{"given":"Markus","family":"Pilman","sequence":"first","affiliation":[{"name":"Snowflake Computing ETH Zurich"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kevin","family":"Bocksrocker","sequence":"additional","affiliation":[{"name":"Microsoft ETH Zurich"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lucas","family":"Braun","sequence":"additional","affiliation":[{"name":"Oracle Labs ETH Zurich"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Renato","family":"Marroqu\u00edn","sequence":"additional","affiliation":[{"name":"ETH Zurich"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Donald","family":"Kossmann","sequence":"additional","affiliation":[{"name":"Microsoft Research ETH Zurich"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Tellstore open-source project. https:\/\/github.com\/tellproject\/tellstore.  Tellstore open-source project. https:\/\/github.com\/tellproject\/tellstore."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687625"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376712"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367892"},{"key":"e_1_2_1_5_1","first-page":"169","volume-title":"VLDB","author":"Ailamaki A.","year":"2001"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/568271.223785"},{"key":"e_1_2_1_7_1","first-page":"9","volume-title":"CIDR'11","author":"Bernstein P.","year":"2011"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142527"},{"key":"e_1_2_1_9_1","first-page":"54","volume-title":"VLDB","volume":"99","author":"Boncz P. A.","year":"1999"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742783"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2903741"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463710"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815425"},{"key":"e_1_2_1_15_1","unstructured":"Facebook. Presto. http:\/\/prestodb.io. May. 02 2016.  Facebook. Presto. http:\/\/prestodb.io. May. 02 2016."},{"key":"e_1_2_1_16_1","unstructured":"Facebook. RocksDB. http:\/\/rocksdb.org. May. 02 2016.  Facebook. RocksDB. http:\/\/rocksdb.org. May. 02 2016."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2094114.2094126"},{"key":"e_1_2_1_18_1","unstructured":"F. F\u00e4rber etal The SAP HANA Database - An Architecture Overview. IEEE Data Eng. Bull. 35(1) 2012.  F. F\u00e4rber et al. The SAP HANA Database - An Architecture Overview. IEEE Data Eng. Bull. 35(1) 2012."},{"key":"e_1_2_1_19_1","unstructured":"A. Foundation. Kudu. http:\/\/getkudu.io. May. 02 2016.  A. Foundation. Kudu. http:\/\/getkudu.io. May. 02 2016."},{"key":"e_1_2_1_20_1","unstructured":"A. Foundation. HBase. http:\/\/hbase.apache.org\/. May. 27 2017.  A. Foundation. HBase. http:\/\/hbase.apache.org\/. May. 27 2017."},{"key":"e_1_2_1_21_1","unstructured":"FoundationDB. https:\/\/foundationdb.com\/. Feb. 07 2015.  FoundationDB. https:\/\/foundationdb.com\/. Feb. 07 2015."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168654"},{"key":"e_1_2_1_23_1","unstructured":"Google. LevelDB. http:\/\/leveldb.org. May. 02 2016.  Google. LevelDB. http:\/\/leveldb.org. May. 02 2016."},{"key":"e_1_2_1_24_1","volume-title":"Morgan Kauf\u00edann Publishers","author":"Gray J.","year":"1993"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767867"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732951.2732959"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1773912.1773922"},{"key":"e_1_2_1_29_1","volume-title":"CIDR","author":"Levandoski J. J.","year":"2015"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2751519"},{"key":"e_1_2_1_31_1","unstructured":"MemSQL. http:\/\/www.memsql.com\/. May. 02 2016.  MemSQL. http:\/\/www.memsql.com\/. May. 02 2016."},{"key":"e_1_2_1_32_1","unstructured":"MongoDB. http:\/\/mongodb.com\/. May. 27 2017.  MongoDB. http:\/\/mongodb.com\/. May. 27 2017."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002940"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1965724.1965751"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_1_36_1","volume-title":"ETH Z\u00fcrich","author":"Pilman M.","year":"2017"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561927_10"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453924"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536233"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/146941.146943"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/2591305.2591307"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824065"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2010.5496972"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/383059.383071"},{"key":"e_1_2_1_45_1","first-page":"553","volume-title":"Proceedings of the 31st international conference on Very large data bases","author":"Stonebraker M.","year":"2005"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687707"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687671"},{"key":"e_1_2_1_48_1","first-page":"10","volume-title":"Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing","author":"Zaharia M.","year":"2010"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564709"},{"key":"e_1_2_1_50_1","first-page":"723","volume-title":"Proceedings of the 33rd International Conference on Very Large Data Bases","author":"Zukowski M.","year":"2007"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3137628.3137659","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:58:45Z","timestamp":1672221525000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3137628.3137659"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8]]},"references-count":49,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["10.14778\/3137628.3137659"],"URL":"https:\/\/doi.org\/10.14778\/3137628.3137659","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,8]]}}}