{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,30]],"date-time":"2023-08-30T12:52:09Z","timestamp":1693399929852},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,3]]},"abstract":"<jats:p>\n            Enabling interactive data exploration at cloud scale requires minimizing end-to-end query execution latency, while guaranteeing fault tolerance, and query execution under resource-constraints. Typically, such a query execution involves orchestrating the execution of hundreds or thousands of related tasks on cloud scale clusters. Without any resource constraints, all query tasks can be scheduled to execute simultaneously (gang scheduling) while connected tasks stream data between them. When the data size referenced by a query increases, gang scheduling may be resource-wasteful or un-satisfiable with a limited, per-query resource budget. This paper introduces B\n            <jats:sc>ubble<\/jats:sc>\n            E\n            <jats:sc>xecution<\/jats:sc>\n            , a new query processing framework for interactive workloads at cloud scale, that balances cost-based query optimization, fault tolerance, optimal resource management, and execution orchestration. Bubble execution involves dividing a query execution graph into a collection of query sub-graphs (bubbles), and scheduling them within a per-query resource budget. The query operators (tasks) inside a bubble stream data between them while fault tolerance is handled by persisting temporary results at bubble boundaries. Our implementation enhances our JetScope service, for interactive workloads, deployed in production clusters at Microsoft. Experiments with TPC-H queries show that bubble execution can reduce resource usage significantly in the presence of failures while maintaining performance competitive with gang execution.\n          <\/jats:p>","DOI":"10.14778\/3192965.3192967","type":"journal-article","created":{"date-parts":[[2018,5,22]],"date-time":"2018-05-22T19:56:10Z","timestamp":1527018970000},"page":"746-758","source":"Crossref","is-referenced-by-count":6,"title":["Bubble execution"],"prefix":"10.14778","volume":"11","author":[{"given":"Zhicheng","family":"Yint","sequence":"first","affiliation":[{"name":"Microsoft Corporation"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jin","family":"Sun","sequence":"additional","affiliation":[{"name":"Microsoft Corporation"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ming","family":"Li","sequence":"additional","affiliation":[{"name":"Microsoft Corporation"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jaliya","family":"Ekanayake","sequence":"additional","affiliation":[{"name":"Microsoft Corporation"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haibo","family":"Lin","sequence":"additional","affiliation":[{"name":"Microsoft Corporation"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Friedman","sequence":"additional","affiliation":[{"name":"Microsoft Corporation"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9 A.","family":"Blakeley","sequence":"additional","affiliation":[{"name":"Microsoft Corporation"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Clemens","family":"Szyperski","sequence":"additional","affiliation":[{"name":"Microsoft Corporation"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikhil R.","family":"Devanur","sequence":"additional","affiliation":[{"name":"Microsoft Research"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742797"},{"key":"e_1_2_1_2_1","first-page":"54","volume-title":"VLDB","author":"Boncz P. A.","year":"1999","unstructured":"P. A. Boncz , S. Manegold , and M. L. Kersten . Database architecture optimized for the new bottleneck: Memory access . In VLDB , pages 54 -- 65 , 1999 . P. A. Boncz, S. Manegold, and M. L. Kersten. Database architecture optimized for the new bottleneck: Memory access. In VLDB, pages 54--65, 1999."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824066"},{"key":"e_1_2_1_4_1","first-page":"285","volume-title":"OSDI","author":"Boutin E.","year":"2014","unstructured":"E. Boutin , J. Ekanayake , W. Lin , B. Shi , J. Zhou , Z. Qian , M. Wu , and L. Zhou . Apollo: Scalable and coordinated scheduling for cloud-scale computing . In OSDI , pages 285 -- 300 , 2014 . E. Boutin, J. Ekanayake, W. Lin, B. Shi, J. Zhou, Z. Qian, M. Wu, and L. Zhou. Apollo: Scalable and coordinated scheduling for cloud-scale computing. In OSDI, pages 285--300, 2014."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536223"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454166"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402755.3402765"},{"key":"e_1_2_1_8_1","first-page":"313","volume-title":"NSDI","author":"Condie T.","year":"2010","unstructured":"T. Condie , N. Conway , P. Alvaro , J. M. Hellerstein , K. Elmeleegy , and R. Sears . Mapreduce online . In NSDI , pages 313 -- 328 , 2010 . T. Condie, N. Conway, P. Alvaro, J. M. Hellerstein, K. Elmeleegy, and R. Sears. Mapreduce online. In NSDI, pages 313--328, 2010."},{"key":"e_1_2_1_9_1","first-page":"137","volume-title":"OSDI","author":"Dean J.","year":"2004","unstructured":"J. Dean and S. Ghemawat . Mapreduce: Simplified data processing on large clusters . In OSDI , pages 137 -- 150 , 2004 . J. Dean and S. Ghemawat. Mapreduce: Simplified data processing on large clusters. In OSDI, pages 137--150, 2004."},{"key":"e_1_2_1_10_1","unstructured":"E. Demaine. Algorithmic lower bounds: Fun with hardness proofs. https: \/\/ocw.mit.edu\/courses\/electrical-engineering-and-computer-science\/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014\/lecture-notes\/MIT6_890F14_Lec13.pdf 2014.  E. Demaine. Algorithmic lower bounds: Fun with hardness proofs. https: \/\/ocw.mit.edu\/courses\/electrical-engineering-and-computer-science\/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014\/lecture-notes\/MIT6_890F14_Lec13.pdf 2014."},{"key":"e_1_2_1_11_1","unstructured":"Facebook. Presto. https:\/\/2.zoppoz.workers.dev:443\/https\/prestodb.io\/.  Facebook. Presto. https:\/\/2.zoppoz.workers.dev:443\/https\/prestodb.io\/."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(92)90014-E"},{"key":"e_1_2_1_13_1","unstructured":"A. S. Foundation. Apache Kafka. https:\/\/2.zoppoz.workers.dev:443\/http\/kafka. apache.org\/.  A. S. Foundation. Apache Kafka. https:\/\/2.zoppoz.workers.dev:443\/http\/kafka. apache.org\/."},{"key":"e_1_2_1_14_1","unstructured":"A. S. Foundation. Apache Storm. https:\/\/2.zoppoz.workers.dev:443\/https\/storm.apache.org\/.  A. S. Foundation. Apache Storm. https:\/\/2.zoppoz.workers.dev:443\/https\/storm.apache.org\/."},{"key":"e_1_2_1_15_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson . Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman , 1979 . M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979."},{"issue":"3","key":"e_1_2_1_16_1","first-page":"19","article-title":"The cascades framework for query optimization","volume":"18","author":"Graefe G.","year":"1995","unstructured":"G. Graefe . The cascades framework for query optimization . IEEE Data Eng. Bull. , 18 ( 3 ): 19 -- 29 , 1995 . G. Graefe. The cascades framework for query optimization. IEEE Data Eng. Bull., 18(3):19--29, 1995.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/66926.66960"},{"key":"e_1_2_1_18_1","volume-title":"NSDI","author":"Hindman B.","year":"2011","unstructured":"B. Hindman , A. Konwinski , M. Zaharia , A. Ghodsi , A. D. Joseph , R. H. Katz , S. Shenker , and I. Stoica . Mesos: A platform for fine-grained resource sharing in the data center . In NSDI , 2011 . B. Hindman, A. Konwinski, M. Zaharia, A. Ghodsi, A. D. Joseph, R. H. Katz, S. Shenker, and I. Stoica. Mesos: A platform for fine-grained resource sharing in the data center. In NSDI, 2011."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272998.1273005"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_21_1","volume-title":"CIDR","author":"Kornacker M.","year":"2015","unstructured":"M. Kornacker , A. Behm , V. Bittorf , T. Bobrovytsky , C. Ching , A. Choi , J. Erickson , M. Grund , D. Hecht , M. Jacobs , I. Joshi , L. Kuff , D. Kumar , A. Leblang , N. Li , I. Pandis , H. Robinson , D. Rorke , S. Rus , J. Russell , D. Tsirogiannis , S. Wanderman-Milne , and M. Yoder . Impala: A modern, open-source SQL engine for hadoop . In CIDR , 2015 . M. Kornacker, A. Behm, V. Bittorf, T. Bobrovytsky, C. Ching, A. Choi, J. Erickson, M. Grund, D. Hecht, M. Jacobs, I. Joshi, L. Kuff, D. Kumar, A. Leblang, N. Li, I. Pandis, H. Robinson, D. Rorke, S. Rus, J. Russell, D. Tsirogiannis, S. Wanderman-Milne, and M. Yoder. Impala: A modern, open-source SQL engine for hadoop. In CIDR, 2015."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989448"},{"key":"e_1_2_1_23_1","first-page":"439","volume-title":"NSDI","author":"Lin W.","year":"2016","unstructured":"W. Lin , H. Fan , Z. Qian , J. Xu , S. Yang , J. Zhou , and L. Zhou . Streamscope: Continuous reliable distributed processing of big data streams . In NSDI , pages 439 -- 453 , 2016 . W. Lin, H. Fan, Z. Qian, J. Xu, S. Yang, J. Zhou, and L. Zhou. Streamscope: Continuous reliable distributed processing of big data streams. In NSDI, pages 439--453, 2016."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920886"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185443"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2523616.2523633"},{"key":"e_1_2_1_27_1","unstructured":"Wikipedia. Minimum k-cut. https:\/\/2.zoppoz.workers.dev:443\/https\/en.wikipedia.org\/wiki\/Minimum_k-cut.  Wikipedia. Minimum k-cut. https:\/\/2.zoppoz.workers.dev:443\/https\/en.wikipedia.org\/wiki\/Minimum_k-cut."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465288"},{"key":"e_1_2_1_29_1","volume-title":"HotCloud","author":"Zaharia M.","year":"2010","unstructured":"M. Zaharia , M. Chowdhury , M. J. Franklin , S. Shenker , and I. Stoica . Spark: Cluster computing with working sets . In HotCloud , 2010 . M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica. Spark: Cluster computing with working sets. In HotCloud, 2010."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0280-z"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/pdf\/10.14778\/3192965.3192967","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:13:34Z","timestamp":1672226014000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/10.14778\/3192965.3192967"}},"subtitle":["resource-aware reliable analytics at cloud scale"],"short-title":[],"issued":{"date-parts":[[2018,3]]},"references-count":30,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2018,3]]}},"alternative-id":["10.14778\/3192965.3192967"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.14778\/3192965.3192967","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,3]]}}}