{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T03:29:39Z","timestamp":1762918179807},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:p>Incremental processing is widely-adopted in many applications, ranging from incremental view maintenance, stream computing, to recently emerging progressive data warehouse and intermittent query processing. Despite many algorithms developed on this topic, none of them can produce an incremental plan that always achieves the best performance, since the optimal plan is data dependent. In this paper, we develop a novel cost-based optimizer framework, called Tempura, for optimizing incremental data processing. We propose an incremental query planning model called TIP based on the concept of time-varying relations, which can formally model incremental processing in its most general form. We give a full specification of Tempura, which can not only unify various existing techniques to generate an optimal incremental plan, but also allow the developer to add their rewrite rules. We study how to explore the plan space and search for an optimal incremental plan. We evaluate Tempura in various incremental processing scenarios to show its effectiveness and efficiency.<\/jats:p>","DOI":"10.14778\/3421424.3421427","type":"journal-article","created":{"date-parts":[[2020,10,28]],"date-time":"2020-10-28T01:15:11Z","timestamp":1603847711000},"page":"14-27","source":"Crossref","is-referenced-by-count":9,"title":["Tempura"],"prefix":"10.14778","volume":"14","author":[{"given":"Zuozhi","family":"Wang","sequence":"first","affiliation":[{"name":"University of California"}]},{"given":"Kai","family":"Zeng","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"given":"Botong","family":"Huang","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"given":"Wei","family":"Chen","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"given":"Xiaozong","family":"Cui","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"given":"Bo","family":"Wang","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"given":"Ji","family":"Liu","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"given":"Liya","family":"Fan","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"given":"Dachuan","family":"Qu","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"given":"Zhenyu","family":"Hou","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"given":"Tao","family":"Guan","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"given":"Chen","family":"Li","sequence":"additional","affiliation":[{"name":"University of California"}]},{"given":"Jingren","family":"Zhou","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]}],"member":"320","published-online":{"date-parts":[[2020,10,27]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"277","article-title":"The design of the borealis stream processing engine","volume":"5","author":"Abadi Daniel J","year":"2005","unstructured":"Daniel J Abadi , Yanif Ahmad , Magdalena Balazinska , Ugur Cetintemel , Mitch Cherniack , Jeong-Hyon Hwang , Wolfgang Lindner , Anurag Maskey , Alex Rasin , Esther Ryvkina , 2005 . The design of the borealis stream processing engine .. In Cidr , Vol. 5. 277 -- 289 . Daniel J Abadi, Yanif Ahmad, Magdalena Balazinska, Ugur Cetintemel, Mitch Cherniack, Jeong-Hyon Hwang, Wolfgang Lindner, Anurag Maskey, Alex Rasin, Esther Ryvkina, et al. 2005. The design of the borealis stream processing engine.. In Cidr, Vol. 5. 277--289.","journal-title":"Cidr"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304581"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2336664.2336670"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/202106.202107"},{"key":"e_1_2_1_5_1","unstructured":"Alibaba Cloud MaxCompute [n.d.]. https:\/\/www.alibabacloud.com\/product\/maxcompute.  Alibaba Cloud MaxCompute [n.d.]. https:\/\/www.alibabacloud.com\/product\/maxcompute."},{"key":"e_1_2_1_6_1","unstructured":"Apache Calcite [n.d.]. https:\/\/calcite.apache.org.  Apache Calcite [n.d.]. https:\/\/calcite.apache.org."},{"key":"e_1_2_1_7_1","unstructured":"Apache Flink [n.d.]. https:\/\/flink.apache.org.  Apache Flink [n.d.]. https:\/\/flink.apache.org."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0147-z"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872822"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066171"},{"key":"e_1_2_1_11_1","volume-title":"One SQL to Rule Them All. CoRR abs\/1905.12133","author":"Begoli Edmon","year":"2019","unstructured":"Edmon Begoli , Tyler Akidau , Fabian Hueske , Julian Hyde , Kathryn Knight , and Kenneth Knowles . 2019. One SQL to Rule Them All. CoRR abs\/1905.12133 ( 2019 ). arXiv:1905.12133 http:\/\/arxiv.org\/abs\/1905.12133 Edmon Begoli, Tyler Akidau, Fabian Hueske, Julian Hyde, Kathryn Knight, and Kenneth Knowles. 2019. One SQL to Rule Them All. CoRR abs\/1905.12133 (2019). arXiv:1905.12133 http:\/\/arxiv.org\/abs\/1905.12133"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190662"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/16894.16861"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308560.3320099"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247542"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556557"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242524.1242526"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/645480.655434"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1670243.1670244"},{"key":"e_1_2_1_20_1","volume-title":"The Cascades Framework for Query Optimization. Data Engineering Bulletin 18","author":"Graefe Goetz","year":"1995","unstructured":"Goetz Graefe . 1995. The Cascades Framework for Query Optimization. Data Engineering Bulletin 18 ( 1995 ). Goetz Graefe. 1995. The Cascades Framework for Query Optimization. Data Engineering Bulletin 18 (1995)."},{"key":"e_1_2_1_21_1","volume-title":"Dagstuhl Reports","volume":"2","author":"Graefe Goetz","year":"2012","unstructured":"Goetz Graefe , Wey Guy , Harumi Anne Kuno , and Glenn Paullley . 2012 . Robust query processing (dagstuhl seminar 12321) . In Dagstuhl Reports , Vol. 2 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Goetz Graefe, Wey Guy, Harumi Anne Kuno, and Glenn Paullley. 2012. Robust query processing (dagstuhl seminar 12321). In Dagstuhl Reports, Vol. 2. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/645478.757691"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/290593.290597"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/568271.223849"},{"key":"e_1_2_1_25_1","unstructured":"Introducing Stream-Stream Joins in Apache Spark 2.3 [n.d.]. https:\/\/databricks.com\/blog\/2018\/03\/13\/introducing-stream-stream-joins-in-apache-spark-2-3.html.  Introducing Stream-Stream Joins in Apache Spark 2.3 [n.d.]. https:\/\/databricks.com\/blog\/2018\/03\/13\/introducing-stream-stream-joins-in-apache-spark-2-3.html."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2017.8257979"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034792"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807100"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612176"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367851"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316733"},{"key":"e_1_2_1_32_1","unstructured":"Mavis K Lee. 1988. Implementing an Interpreter for Functional Rules in a Query Optimizer.  Mavis K Lee. 1988. Implementing an Interpreter for Functional Rules in a Query Optimizer."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30570-5_3"},{"key":"e_1_2_1_34_1","unstructured":"Rajeev Motwani Jennifer Widom Arvind Arasu Brian Babcock Shivnath Babu Mayur Datar Gurmeet Manku Chris Olston Justin Rosenstein and Rohit Varma. 2003. Query processing resource management and approximation in a data stream management system. CIDR.  Rajeev Motwani Jennifer Widom Arvind Arasu Brian Babcock Shivnath Babu Mayur Datar Gurmeet Manku Chris Olston Justin Rosenstein and Rohit Varma. 2003. Query processing resource management and approximation in a data stream management system. CIDR."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915246"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564723"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3242153.3242155"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2595637"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342278"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/141484.130333"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767879"},{"key":"e_1_2_1_43_1","unstructured":"The TPC-DS Benchmark [n.d.]. http:\/\/www.tpc.org\/tpcds\/.  The TPC-DS Benchmark [n.d.]. http:\/\/www.tpc.org\/tpcds\/."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564697"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3384708"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421427"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183742"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2854006.2854012"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629600"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915240"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367862"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3421424.3421427","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:18:48Z","timestamp":1672226328000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3421424.3421427"}},"subtitle":["a general cost-based optimizer framework for incremental data processing"],"short-title":[],"issued":{"date-parts":[[2020,9]]},"references-count":51,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["10.14778\/3421424.3421427"],"URL":"https:\/\/doi.org\/10.14778\/3421424.3421427","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,9]]}}}