{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T10:00:50Z","timestamp":1791194450202,"version":"4.1.0"},"reference-count":33,"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>Many systems for big data analytics employ a data flow abstraction to define parallel data processing tasks. In this setting, custom operations expressed as user-defined functions are very common. We address the problem of performing data flow optimization at this level of abstraction, where the semantics of operators are not known. Traditionally, query optimization is applied to queries with known algebraic semantics. In this work, we find that a handful of properties, rather than a full algebraic specification, suffice to establish reordering conditions for data processing operators. We show that these properties can be accurately estimated for black box operators by statically analyzing the general-purpose code of their user-defined functions.<\/jats:p>\n          <jats:p>We design and implement an optimizer for parallel data flows that does not assume knowledge of semantics or algebraic properties of operators. Our evaluation confirms that the optimizer can apply common rewritings such as selection reordering, bushy join-order enumeration, and limited forms of aggregation push-down, hence yielding similar rewriting power as modern relational DBMS optimizers. Moreover, it can optimize the operator order of nonrelational data flows, a unique feature among today's systems.<\/jats:p>","DOI":"10.14778\/2350229.2350244","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1256-1267","source":"Crossref","is-referenced-by-count":83,"title":["Opening the black boxes in data flow optimization"],"prefix":"10.14778","volume":"5","author":[{"given":"Fabian","family":"Hueske","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mathias","family":"Peters","sequence":"additional","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matthias J.","family":"Sax","sequence":"additional","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Astrid","family":"Rheinl\u00e4nder","sequence":"additional","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rico","family":"Bergmann","sequence":"additional","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aljoscha","family":"Krettek","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kostas","family":"Tzoumas","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"http:\/\/public.web.cern.ch\/public\/en\/LHC\/Computing-en.html.  http:\/\/public.web.cern.ch\/public\/en\/LHC\/Computing-en.html."},{"key":"e_1_2_1_2_1","unstructured":"http:\/\/www.greenplum.com\/technology\/mapreduce.  http:\/\/www.greenplum.com\/technology\/mapreduce."},{"key":"e_1_2_1_3_1","unstructured":"http:\/\/www.sable.mcgill.ca\/soot\/.  http:\/\/www.sable.mcgill.ca\/soot\/."},{"key":"e_1_2_1_4_1","unstructured":"http:\/\/stratosphere.eu.  http:\/\/stratosphere.eu."},{"key":"e_1_2_1_5_1","volume-title":"Techniques and Tools. Pearson","author":"Aho A. V.","year":"2006","unstructured":"A. V. Aho , M. S. Lam , R. Sethi , and J. D. Ullman . Compilers: Principles , Techniques and Tools. Pearson , 2006 . A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques and Tools. Pearson, 2006."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1038\/nmeth0710-495"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807148"},{"key":"e_1_2_1_8_1","volume-title":"Designing a multi-petabyte database for LSST. CoRR, abs\/cs\/0604112","author":"Becla J.","year":"2006","unstructured":"J. Becla , A. Hanushevsky , S. Nikolaev , G. Abdulla , A. S. Szalay , M. A. Nieto-Santisteban , A. Thakar , and J. Gray . Designing a multi-petabyte database for LSST. CoRR, abs\/cs\/0604112 , 2006 . J. Becla, A. Hanushevsky, S. Nikolaev, G. Abdulla, A. S. Szalay, M. A. Nieto-Santisteban, A. Thakar, and J. Gray. Designing a multi-petabyte database for LSST. CoRR, abs\/cs\/0604112, 2006."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-011-7082-y"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402755.3402761"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767921"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454166"},{"key":"e_1_2_1_13_1","first-page":"354","volume-title":"VLDB","author":"Chaudhuri S.","year":"1994","unstructured":"S. Chaudhuri and K. Shim . Including group-by in query optimization . In VLDB , pp. 354 -- 366 , 1994 . S. Chaudhuri and K. Shim. Including group-by in query optimization. In VLDB, pp. 354--366, 1994."},{"issue":"3","key":"e_1_2_1_14_1","first-page":"3","article-title":"An overview of cost-based optimization of queries with aggregates","volume":"18","author":"Chaudhuri S.","year":"1995","unstructured":"S. Chaudhuri and K. Shim . An overview of cost-based optimization of queries with aggregates . IEEE Data Eng. Bull. , 18 ( 3 ): 3 -- 9 , 1995 . S. Chaudhuri and K. Shim. An overview of cost-based optimization of queries with aggregates. IEEE Data Eng. Bull., 18(3):3--9, 1995.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/320248.320249"},{"issue":"12","key":"e_1_2_1_16_1","first-page":"1318","volume":"4","author":"Chattopadhyay B.","year":"2011","unstructured":"B. Chattopadhyay , L. Lin , W. Liu , S. Mittal , P. Aragonda , V. Lychagina , Y. Kwon , and M. Wong . Tenzing A SQL Implementation On The MapReduce Framework. PVLDB , 4 ( 12 ): 1318 -- 1327 , 2011 . B. Chattopadhyay, L. Lin, W. Liu, S. Mittal, P. Aragonda, V. Lychagina, Y. Kwon, and M. Wong. Tenzing A SQL Implementation On The MapReduce Framework. PVLDB, 4(12):1318--1327, 2011.","journal-title":"Tenzing A SQL Implementation On The MapReduce Framework. PVLDB"},{"key":"e_1_2_1_17_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 , pp. 137 -- 150 , 2004 . J. Dean and S. Ghemawat. MapReduce: Simplified data processing on large clusters. In OSDI, pp. 137--150, 2004."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767901"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687567"},{"issue":"3","key":"e_1_2_1_21_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_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559982"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/292481.277627"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402746"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272996.1273005"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/1978665.1978670"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376672"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376726"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_30_1","first-page":"173","volume-title":"CIDR","author":"Stonebraker M.","year":"2007","unstructured":"M. Stonebraker , C. Bear , U. \u00c7etintemel , M. Cherniack , T. Ge , N. Hachem , S. Harizopoulos , J. Lifter , J. Rogers , and S. B. Zdonik . One size fits all? Part 2: Benchmarking studies . In CIDR , pp. 173 -- 184 , 2007 . M. Stonebraker, C. Bear, U. \u00c7etintemel, M. Cherniack, T. Ge, N. Hachem, S. Harizopoulos, J. Lifter, J. Rogers, and S. B. Zdonik. One size fits all? Part 2: Benchmarking studies. In CIDR, pp. 173--184, 2007."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687609"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1646468.1646476"},{"key":"e_1_2_1_33_1","first-page":"1","volume-title":"OSDI","author":"Yu Y.","year":"2008","unstructured":"Y. Yu , M. Isard , D. Fetterly , M. Budiu , \u00da. Erlingsson, P. K. Gunda , and J. Currey . DryadLINQ: A system for general-purpose distributed data-parallel computing using a high-level language . In OSDI , pp. 1 -- 14 , 2008 . Y. Yu, M. Isard, D. Fetterly, M. Budiu, \u00da. Erlingsson, P. K. Gunda, and J. Currey. DryadLINQ: A system for general-purpose distributed data-parallel computing using a high-level language. In OSDI, pp. 1--14, 2008."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2350229.2350244","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:26:59Z","timestamp":1672226819000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2350229.2350244"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":33,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.14778\/2350229.2350244"],"URL":"https:\/\/doi.org\/10.14778\/2350229.2350244","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}