{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T22:16:04Z","timestamp":1765232164178},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>There is a growing trend of performing analysis on large datasets using workflows composed of MapReduce jobs connected through producer-consumer relationships based on data. This trend has spurred the development of a number of interfaces---ranging from program-based to query-based interfaces---for generating MapReduce workflows. Studies have shown that the gap in performance can be quite large between optimized and unoptimized workflows. However, automatic cost-based optimization of MapReduce workflows remains a challenge due to the multitude of interfaces, large size of the execution plan space, and the frequent unavailability of all types of information needed for optimization.<\/jats:p>\n          <jats:p>\n            We introduce a comprehensive plan space for MapReduce workflows generated by popular workflow generators. We then propose\n            <jats:italic>Stubby<\/jats:italic>\n            , a cost-based optimizer that searches selectively through the subspace of the full plan space that can be enumerated correctly and costed based on the information available in any given setting. Stubby enumerates the plan space based on plan-to-plan transformations and an efficient search algorithm. Stubby is designed to be extensible to new interfaces and new types of optimizations, which is a desirable feature given how rapidly MapReduce systems are evolving. Stubby's efficiency and effectiveness have been evaluated using representative workflows from many domains.\n          <\/jats:p>","DOI":"10.14778\/2350229.2350239","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1196-1207","source":"Crossref","is-referenced-by-count":47,"title":["Stubby"],"prefix":"10.14778","volume":"5","author":[{"given":"Harold","family":"Lim","sequence":"first","affiliation":[{"name":"Duke University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Herodotos","family":"Herodotou","sequence":"additional","affiliation":[{"name":"Duke University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shivnath","family":"Babu","sequence":"additional","affiliation":[{"name":"Duke University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806596.1806638"},{"key":"e_1_2_1_2_1","first-page":"295","volume-title":"VLDB","author":"Chatziantoniou D.","year":"1996","unstructured":"D. Chatziantoniou and K. A. Ross . Querying Multiple Features of Groups in Relational Databases . In VLDB , pages 295 -- 306 , 1996 . D. Chatziantoniou and K. A. Ross. Querying Multiple Features of Groups in Relational Databases. In VLDB, pages 295--306, 1996."},{"key":"e_1_2_1_3_1","unstructured":"Cloudera: 7 Tips for Improving MapReduce Performance. cloudera. com\/blog\/2009\/12\/7-tips-for-improving-mapreduce-performance.  Cloudera: 7 Tips for Improving MapReduce Performance. cloudera. com\/blog\/2009\/12\/7-tips-for-improving-mapreduce-performance."},{"key":"e_1_2_1_4_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_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687568"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/38713.38734"},{"key":"e_1_2_1_7_1","unstructured":"Apache Hadoop. http:\/\/hadoop.apache.org\/. Apache Hadoop . http:\/\/hadoop.apache.org\/."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402746"},{"key":"e_1_2_1_9_1","unstructured":"Apache Hive. http:\/\/hive.apache.org\/.  Apache Hive. http:\/\/hive.apache.org\/."},{"issue":"6","key":"e_1_2_1_10_1","first-page":"385","article-title":"Automatic Optimization for MapReduce Programs","volume":"4","author":"Jahani E.","year":"2011","unstructured":"E. Jahani , M. J. Cafarella , and C. R\u00e9 . Automatic Optimization for MapReduce Programs . PVLDB , 4 ( 6 ): 385 -- 396 , 2011 . E. Jahani, M. J. Cafarella, and C. R\u00e9. Automatic Optimization for MapReduce Programs. PVLDB, 4(6):385--396, 2011.","journal-title":"PVLDB"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2011.26"},{"key":"e_1_2_1_12_1","volume-title":"Duke Computer Science","author":"Lim H.","year":"2012","unstructured":"H. Lim , H. Herodotou , and S. Babu . Stubby: A Transformation-based Optimizer for MapReduce Workflows. Technical report , Duke Computer Science , 2012 . http:\/\/www.cs.duke.edu\/starfish\/files\/stubby-technical-report.pdf. H. Lim, H. Herodotou, and S. Babu. Stubby: A Transformation-based Optimizer for MapReduce Workflows. Technical report, Duke Computer Science, 2012. http:\/\/www.cs.duke.edu\/starfish\/files\/stubby-technical-report.pdf."},{"issue":"1","key":"e_1_2_1_13_1","first-page":"494","volume":"3","author":"Nykiel T.","year":"2010","unstructured":"T. Nykiel , M. Potamias , C. Mishra , G. Kollios , and N. Koudas . MRShare: Sharing Across Multiple Queries in MapReduce. PVLDB , 3 ( 1 ): 494 -- 505 , 2010 . T. Nykiel, M. Potamias, C. Mishra, G. Kollios, and N. Koudas. MRShare: Sharing Across Multiple Queries in MapReduce. PVLDB, 3(1):494--505, 2010.","journal-title":"MRShare: Sharing Across Multiple Queries in MapReduce. PVLDB"},{"key":"e_1_2_1_14_1","first-page":"267","volume-title":"Automatic Optimization of Parallel Dataflow Programs. In USENIX Annual Technical Conference","author":"Olston C.","year":"2008","unstructured":"C. Olston , B. Reed , A. Silberstein , and U. Srivastava . Automatic Optimization of Parallel Dataflow Programs. In USENIX Annual Technical Conference , pages 267 -- 273 , 2008 . C. Olston, B. Reed, A. Silberstein, and U. Srivastava. Automatic Optimization of Parallel Dataflow Programs. In USENIX Annual Technical Conference, pages 267--273, 2008."},{"key":"e_1_2_1_15_1","unstructured":"Oozie: Workflow Engine for Hadoop. http:\/\/yahoo.github.com\/oozie\/.  Oozie: Workflow Engine for Hadoop. http:\/\/yahoo.github.com\/oozie\/."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559865"},{"key":"e_1_2_1_18_1","unstructured":"Apache Pig. http:\/\/pig.apache.org\/.  Apache Pig. http:\/\/pig.apache.org\/."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.103"},{"key":"e_1_2_1_20_1","unstructured":"TPC-H Benchmark Specification. http:\/\/www.tpc.org\/tpch\/.  TPC-H Benchmark Specification. http:\/\/www.tpc.org\/tpch\/."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989350"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2038916.2038927"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2038916.2038928"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/781027.781052"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629600"},{"key":"e_1_2_1_26_1","first-page":"1","volume-title":"OSDI","author":"Yu Y.","year":"2008","unstructured":"Y. Yu , M. Isard , D. Fetterly , M. Budiu , U. Erlingsson , P. K. Gunda , and J. Currey . DryadLINQ: A System for General-Purpose Distributed Data-Parallel Computing Using a High-Level Language . In OSDI , pages 1 -- 14 , 2008 . Y. Yu, M. Isard, D. Fetterly, M. Budiu, U. Erlingsson, P. K. Gunda, and J. Currey. DryadLINQ: A System for General-Purpose Distributed Data-Parallel Computing Using a High-Level Language. In OSDI, pages 1--14, 2008."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447802"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2350229.2350239","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:26:16Z","timestamp":1672226776000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2350229.2350239"}},"subtitle":["a transformation-based optimizer for MapReduce workflows"],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":26,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.14778\/2350229.2350239"],"URL":"https:\/\/doi.org\/10.14778\/2350229.2350239","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}