{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:54:14Z","timestamp":1775638454379,"version":"3.50.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,11]]},"abstract":"<jats:p>\n            The cost of big-data analytics is dominated by shuffle operations that induce multiple disk reads, writes and network transfers. This paper proposes a new class of optimization rules that are specifically aimed at eliminating shuffles where possible. The rules substitute multiple shuffle inducing operators (\n            <jats:italic>Join, UnionAll, Spool, GroupBy<\/jats:italic>\n            ) with a single streaming operator which implements an entire sub-query. We call such operators\n            <jats:italic>super-operators.<\/jats:italic>\n          <\/jats:p>\n          <jats:p>A key challenge with adding new rules that substitute sub-queries with super-operators is that there are many variants of the same sub-query that can be implemented via minor modifications to the same super-operator. Adding each as a separate rule leads to a search space explosion. We propose several extensions to the query optimizer to address this challenge. We propose a new abstract representation for operator trees that captures all possible sub-queries that a super-operator implements. We propose a new rule matching algorithm that can efficiently search for abstract operator trees. Finally we extend the physical operator interface to introduce new parametric super-operators.<\/jats:p>\n          <jats:p>We implement our changes in SCOPE, a state-of-the-art production big-data optimizer used extensively at Microsoft. We demonstrate that the proposed optimizations provide significant reduction in both resource cost (average 1.7x) and latency (average 1.5x) on several production queries, and do so without increasing optimization time.<\/jats:p>","DOI":"10.14778\/3368289.3368299","type":"journal-article","created":{"date-parts":[[2020,9,11]],"date-time":"2020-09-11T03:17:35Z","timestamp":1599794255000},"page":"348-361","source":"Crossref","is-referenced-by-count":12,"title":["Incorporating super-operators in big-data query optimizers"],"prefix":"10.14778","volume":"13","author":[{"given":"Jyoti","family":"Leeka","sequence":"first","affiliation":[{"name":"Microsoft"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kaushik","family":"Rajan","sequence":"additional","affiliation":[{"name":"Microsoft"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,11]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Code Generation and T4 Text Templates. https:\/\/docs.microsoft.com\/en-us\/visualstudio\/modeling\/code-generation-and-t4--text-templates 2019.  Code Generation and T4 Text Templates. https:\/\/docs.microsoft.com\/en-us\/visualstudio\/modeling\/code-generation-and-t4--text-templates 2019."},{"key":"e_1_2_1_2_1","unstructured":"Expression evaluation and lambdaCalculus. https:\/\/en.wikipedia.org\/wiki\/Lambda_calculus 2019.  Expression evaluation and lambdaCalculus. https:\/\/en.wikipedia.org\/wiki\/Lambda_calculus 2019."},{"key":"e_1_2_1_3_1","unstructured":"SQL Server https:\/\/www.microsoft.com\/en-us\/sql-server\/sql-server-2019 2019.  SQL Server https:\/\/www.microsoft.com\/en-us\/sql-server\/sql-server-2019 2019."},{"key":"e_1_2_1_4_1","first-page":"1383","volume-title":"SIGMOD","author":"Armbrust Michael","year":"2015"},{"key":"e_1_2_1_5_1","volume-title":"Hadoop Apache Project","author":"Dhruba","year":"2008"},{"key":"e_1_2_1_6_1","first-page":"476","volume-title":"VLDB","author":"Chatziantoniou Damianos","year":"1997"},{"key":"e_1_2_1_7_1","first-page":"177","volume-title":"NSDI","author":"Curino Carlo","year":"2019"},{"key":"e_1_2_1_8_1","first-page":"799","volume-title":"OSDI","author":"Essertel Gregory","year":"2018"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375748"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/945445.945450"},{"key":"e_1_2_1_11_1","first-page":"18","article-title":"The cascades framework for query optimization","author":"Graefe Goetz","year":"1995","journal-title":"Data Engineering Bulletin"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1993.344061"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-51085-0_43"},{"key":"e_1_2_1_14_1","first-page":"121","volume-title":"OSDI","author":"Guo Zhenyu","year":"2012"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742795"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Yannis Klonatos Christoph Koch Tiark Rompf and Hassan Chafi. Building efficient query engines in a high-level language. PVLDB 7(10) 2014.  Yannis Klonatos Christoph Koch Tiark Rompf and Hassan Chafi. Building efficient query engines in a high-level language. PVLDB 7(10) 2014.","DOI":"10.14778\/2732951.2732959"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447892"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2011.26"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993513"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Thomas Neumann. Efficiently compiling efficient query plans for modern hardware. PVLDB 4(9) 2011.  Thomas Neumann. Efficiently compiling efficient query plans for modern hardware. PVLDB 4(9) 2011.","DOI":"10.14778\/2002938.2002940"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339495"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056100"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815418"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132773"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3324961"},{"key":"e_1_2_1_26_1","first-page":"1626","volume-title":"PVLDB","author":"Thusoo Ashish","year":"2009"},{"key":"e_1_2_1_27_1","volume-title":"ACM SIGMOD Record","author":"Florian","year":"2000"},{"key":"e_1_2_1_28_1","volume-title":"Portland State University","author":"Xu Yongwen","year":"1998"},{"key":"e_1_2_1_29_1","volume-title":"HotCloud","author":"Zaharia Matei","year":"2010"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3190508.3190534"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447802"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0280-z"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872840"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3368289.3368299","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:44:43Z","timestamp":1672220683000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3368289.3368299"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,11]]}},"alternative-id":["10.14778\/3368289.3368299"],"URL":"https:\/\/doi.org\/10.14778\/3368289.3368299","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,11]]}}}