{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T06:51:37Z","timestamp":1777013497694,"version":"3.51.4"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:p>\n            Systems performing large data-parallel computations, including online analytical processing (OLAP) systems like Druid and search engines like Elasticsearch, are increasingly being used for business-critical real-time applications where providing low query latency is paramount. In this paper, we investigate an underexplored factor in the performance of data-parallel queries: their\n            <jats:italic>parallelism.<\/jats:italic>\n            We find that to minimize the tail latency of data-parallel queries, it is critical to place data such that the data items accessed by each individual query are spread across as many machines as possible so that each query can leverage the computational resources of as many machines as possible. To optimize parallelism and minimize tail latency in real systems, we develop a novel parallelism-optimizing data placement algorithm that defines a linearly-computable measure of query parallelism, uses it to frame data placement as an optimization problem, and leverages a new optimization problem partitioning technique to scale to large cluster sizes. We apply this algorithm to popular systems such as Solr and MongoDB and show that it reduces p99 latency by 7-64% on data-parallel workloads.\n          <\/jats:p>","DOI":"10.14778\/3574245.3574260","type":"journal-article","created":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T23:14:12Z","timestamp":1677021252000},"page":"760-771","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Parallelism-Optimizing Data Placement for Faster Data-Parallel Computations"],"prefix":"10.14778","volume":"16","author":[{"given":"Nirvik","family":"Baruah","sequence":"first","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Kraft","sequence":"additional","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fiodar","family":"Kazhamiaka","sequence":"additional","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Bailis","sequence":"additional","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matei","family":"Zaharia","sequence":"additional","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,2,21]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2016. Distributing data in druid at scale. https:\/\/metamarkets.com\/2016\/distributing-data-in-druid-at-petabyte-scale.  2016. Distributing data in druid at scale. https:\/\/metamarkets.com\/2016\/distributing-data-in-druid-at-petabyte-scale."},{"key":"e_1_2_1_2_1","unstructured":"2018. Why Architecting for Disaster Recovery is Important for Your Time Series Data. https:\/\/www.influxdata.com\/customer\/capital-one\/.  2018. Why Architecting for Disaster Recovery is Important for Your Time Series Data. https:\/\/www.influxdata.com\/customer\/capital-one\/."},{"key":"e_1_2_1_3_1","unstructured":"2019. How Walmart is Combating Fraud and Saving Consumers Millions. https:\/\/www.elastic.co\/elasticon\/tour\/2019\/dallas\/.  2019. How Walmart is Combating Fraud and Saving Consumers Millions. https:\/\/www.elastic.co\/elasticon\/tour\/2019\/dallas\/."},{"key":"e_1_2_1_4_1","unstructured":"2020. Enterprise Scale Analytics Platform Powered by Druid at Target. https:\/\/imply.io\/virtual-druid-summit.  2020. Enterprise Scale Analytics Platform Powered by Druid at Target. https:\/\/imply.io\/virtual-druid-summit."},{"key":"e_1_2_1_5_1","unstructured":"2021. MongoDB. https:\/\/www.mongodb.com\/.  2021. MongoDB. https:\/\/www.mongodb.com\/."},{"key":"e_1_2_1_6_1","unstructured":"2022. Apache Solr. https:\/\/lucene.apache.org\/solr\/.  2022. Apache Solr. https:\/\/lucene.apache.org\/solr\/."},{"key":"e_1_2_1_7_1","unstructured":"2022. ClickHouse. https:\/\/clickhouse.tech\/.  2022. ClickHouse. https:\/\/clickhouse.tech\/."},{"key":"e_1_2_1_8_1","unstructured":"2022. CPLEX. https:\/\/www.ibm.com\/analytics\/cplex-optimizer.  2022. CPLEX. https:\/\/www.ibm.com\/analytics\/cplex-optimizer."},{"key":"e_1_2_1_9_1","unstructured":"2022. Elasticsearch. www.elastic.co.  2022. Elasticsearch. www.elastic.co."},{"key":"e_1_2_1_10_1","volume-title":"Slicer: Auto-Sharding for Datacenter Applications. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16)","author":"Adya Atul","year":"2016","unstructured":"Atul Adya , Daniel Myers , Jon Howell , Jeremy Elson , Colin Meek , Vishesh Khemani , Stefan Fulger , Pan Gu , Lakshminath Bhuvanagiri , Jason Hunter , Roberto Peon , Larry Kai , Alexander Shraer , Arif Merchant , and Kfir Lev-Ari . 2016 . Slicer: Auto-Sharding for Datacenter Applications. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16) . USENIX Association, Savannah, GA, 739--753. https:\/\/www.usenix.org\/conference\/osdi16\/technical-sessions\/presentation\/adya Atul Adya, Daniel Myers, Jon Howell, Jeremy Elson, Colin Meek, Vishesh Khemani, Stefan Fulger, Pan Gu, Lakshminath Bhuvanagiri, Jason Hunter, Roberto Peon, Larry Kai, Alexander Shraer, Arif Merchant, and Kfir Lev-Ari. 2016. Slicer: Auto-Sharding for Datacenter Applications. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16). USENIX Association, Savannah, GA, 739--753. https:\/\/www.usenix.org\/conference\/osdi16\/technical-sessions\/presentation\/adya"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2150976.2150984"},{"key":"e_1_2_1_12_1","volume-title":"PACMan: Coordinated Memory Caching for Parallel Jobs. In 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 12)","author":"Ananthanarayanan Ganesh","year":"2012","unstructured":"Ganesh Ananthanarayanan , Ali Ghodsi , Andrew Warfield , Dhruba Borthakur , Srikanth Kandula , Scott Shenker , and Ion Stoica . 2012 . PACMan: Coordinated Memory Caching for Parallel Jobs. In 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 12) . USENIX Association, San Jose, CA, 267--280. https:\/\/www.usenix.org\/conference\/nsdi12\/technical-sessions\/presentation\/ananthanarayanan Ganesh Ananthanarayanan, Ali Ghodsi, Andrew Warfield, Dhruba Borthakur, Srikanth Kandula, Scott Shenker, and Ion Stoica. 2012. PACMan: Coordinated Memory Caching for Parallel Jobs. In 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 12). USENIX Association, San Jose, CA, 267--280. https:\/\/www.usenix.org\/conference\/nsdi12\/technical-sessions\/presentation\/ananthanarayanan"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1924943.1924962"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920853"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2408776.2408794"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3190508.3190542"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/080736491"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-006-8497-6"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2911451.2914689"},{"key":"e_1_2_1_22_1","volume-title":"Data-Parallel Actors: A Programming Model for Scalable Query Serving Systems. In 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22)","author":"Kraft Peter","year":"2022","unstructured":"Peter Kraft , Fiodar Kazhamiaka , Peter Bailis , and Matei Zaharia . 2022 . Data-Parallel Actors: A Programming Model for Scalable Query Serving Systems. In 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22) . USENIX Association, Renton, WA. https:\/\/www.usenix.org\/conference\/nsdi22\/presentation\/kraft Peter Kraft, Fiodar Kazhamiaka, Peter Bailis, and Matei Zaharia. 2022. Data-Parallel Actors: A Programming Model for Scalable Query Serving Systems. In 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22). USENIX Association, Renton, WA. https:\/\/www.usenix.org\/conference\/nsdi22\/presentation\/kraft"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477132.3483546"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196935"},{"key":"e_1_2_1_25_1","unstructured":"Michael McCandless. 2020. Lucene nightly benchmarks. (2020).  Michael McCandless. 2020. Lucene nightly benchmarks. (2020)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148170.1148232"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477132.3483588"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732979"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3025111.3025125"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2010.5496972"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735508.2735514"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2595631"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-007-9125-x"},{"key":"e_1_2_1_34_1","volume-title":"Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing. In 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 12)","author":"Zaharia Matei","year":"2012","unstructured":"Matei Zaharia , Mosharaf Chowdhury , Tathagata Das , Ankur Dave , Justin Ma , Murphy McCauly , Michael J. Franklin , Scott Shenker , and Ion Stoica . 2012 . Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing. In 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 12) . USENIX Association, San Jose, CA, 15--28. https:\/\/www.usenix.org\/conference\/nsdi12\/technical-sessions\/presentation\/zaharia Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauly, Michael J. Franklin, Scott Shenker, and Ion Stoica. 2012. Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing. In 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 12). USENIX Association, San Jose, CA, 15--28. https:\/\/www.usenix.org\/conference\/nsdi12\/technical-sessions\/presentation\/zaharia"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855741.1855744"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3574245.3574260","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T23:14:47Z","timestamp":1677021287000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3574245.3574260"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["10.14778\/3574245.3574260"],"URL":"https:\/\/doi.org\/10.14778\/3574245.3574260","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,12]]},"assertion":[{"value":"2023-02-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}