{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T00:06:11Z","timestamp":1756512371647,"version":"3.44.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,2]]},"abstract":"<jats:p>Incremental query processing is widely used in data warehouses and streaming systems. While many optimization techniques are developed to generate incremental query plans, the scheduling support for incremental processing remains preliminary. Typically, execution is triggered with fixed frequencies specified by the user. In this paper, we propose a novel scheduling problem for incremental query execution under a deadline, assuming the resource has a fluctuating and unforeseen price. We propose two naive solutions as well as a prophet scheduler that foresees the future. We present an end-to-end system Agamotto that models future probabilities offline with a Markov Decision Process (MDP) and makes cost-based and dynamic scheduling decisions online. We show how Agamotto can be extended to handle a workflow of dependent queries, so that they can all incrementally execute in an asynchronous fashion. Experiments show that Agamotto consistently outperforms the naive solutions, and the achieved cost is on average 10x closer to the theoretical lower bound provided by the prophet scheduler.<\/jats:p>","DOI":"10.14778\/3725688.3725711","type":"journal-article","created":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T14:19:21Z","timestamp":1756477161000},"page":"1852-1864","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Agamotto: Scheduling of Deadline-Oriented Incremental Query Execution under Uncertain Resource Price"],"prefix":"10.14778","volume":"18","author":[{"given":"Botong","family":"Huang","sequence":"first","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lianggui","family":"Weng","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Chen","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kai","family":"Zeng","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yihui","family":"Feng","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bolin","family":"Ding","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingren","family":"Zhou","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zuozhi","family":"Wang","sequence":"additional","affiliation":[{"name":"University of California, Irvine, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chen","family":"Li","sequence":"additional","affiliation":[{"name":"University of California, Irvine, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,8,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2021.3070785"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589776"},{"key":"e_1_2_1_3_1","unstructured":"Alibaba Cloud ECS Spot Instances n.a.. https:\/\/www.alibabacloud.com\/help\/zh\/batch-compute\/latest\/bidding-resources"},{"key":"e_1_2_1_4_1","unstructured":"Alibaba MaxCompute n.a.. https:\/\/www.alibabacloud.com\/product\/maxcompute"},{"key":"e_1_2_1_5_1","unstructured":"Amazon EC2 Spot Instances n.a.. https:\/\/aws.amazon.com\/ec2\/spot\/"},{"key":"e_1_2_1_6_1","unstructured":"Apache Hudi n.a.. https:\/\/hudi.apache.org\/."},{"key":"e_1_2_1_7_1","unstructured":"Apache Spark n.a.. https:\/\/spark.apache.org\/."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190664"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190662"},{"key":"e_1_2_1_10_1","first-page":"28","article-title":"Apache Flink\u2122: Stream and Batch Processing in a Single Engine","volume":"38","author":"Carbone Paris","year":"2015","unstructured":"Paris Carbone, Asterios Katsifodimos, Stephan Ewen, Volker Markl, Seif Haridi, and Kostas Tzoumas. 2015. Apache Flink\u2122: Stream and Batch Processing in a Single Engine. IEEE Data Eng. Bull. 38, 4 (2015), 28\u201338. http:\/\/sites.computer.org\/debull\/A15dec\/p28.pdf","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2018.2846234"},{"key":"e_1_2_1_12_1","volume-title":"a Cost-Based Incremental Query Optimizer","author":"Enzyme DataBricks","year":"2022","unstructured":"DataBricks Enzyme, a Cost-Based Incremental Query Optimizer 2022. https:\/\/www.databricks.com\/blog\/2022\/06\/29\/delta-live-tables-announces-new-capabilities-and-performance-optimizations.html"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2021.105646"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3274808.3274827"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223849"},{"key":"e_1_2_1_16_1","first-page":"3","article-title":"Maintenance of Materialized Views: Problems, Techniques, and Applications","volume":"18","author":"Gupta Ashish Kumar","year":"1995","unstructured":"Ashish Kumar Gupta and Inderpal Singh Mumick. 1995. Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18 (1995), 3\u201318.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850590"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3090163.3090165"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSOS-C52956.2021.00027"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICAC.2017.36"},{"key":"e_1_2_1_21_1","volume-title":"Technical report","author":"Olston Christopher","year":"2011","unstructured":"Christopher Olston. Technical report, 2011. Modeling and Scheduling Asynchronous Incremental Workflows. http:\/\/i.stanford.edu\/~olston\/publications\/asynchronousWorkflowsTR.pdf"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989439"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1057\/jors.2009.2"},{"key":"e_1_2_1_24_1","volume-title":"Franklin","author":"Shang Zechao","year":"2020","unstructured":"Zechao Shang, Xi Liang, Dixin Tang, Cong Ding, Aaron J. Elmore, Sanjay Krishnan, and Michael J. Franklin. 2020. CrocodileDB: Efficient Database Execution through Intelligent Deferment. In CIDR."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS47924.2020.00093"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342278"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389756"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457282"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3384708"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421427"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3725688.3725711","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T14:23:17Z","timestamp":1756477397000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3725688.3725711"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2]]},"references-count":30,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["10.14778\/3725688.3725711"],"URL":"https:\/\/doi.org\/10.14778\/3725688.3725711","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,2]]},"assertion":[{"value":"2025-08-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}