{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:12:52Z","timestamp":1779174772890,"version":"3.51.4"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-sa\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>Despite decades of research into query optimization, optimizing queries with disjunctive predicate expressions remains a challenge. Solutions employed by existing systems (if any) are often simplistic and lead to much redundant work being performed by the execution engine. To address these problems, we propose a novel form of query execution called tagged execution. Tagged execution groups tuples into subrelations based on which predicates in the query they satisfy (or don't satisfy) and tags them with that information. These tags then provide additional context for query operators to take advantage of during runtime, allowing them to eliminate much of the redundant work performed by traditional engines and realize predicate pushdown optimizations for disjunctive predicates. However, tagged execution brings its own challenges, and the question of what tags to create is a nontrivial one. Careless creation of tags can lead to an exponential blowup in the tag space, with the overhead outweighing the benefits. To address this issue, we present a technique called tag generalization to minimize the space of tags. We implemented the tagged execution model with tag generalization in our system Basilisk, and our evaluation showed an average 2.7x speedup in runtime over the traditional execution model with up to a 19x speedup in certain situations.<\/jats:p>","DOI":"10.1145\/3654961","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-25","source":"Crossref","is-referenced-by-count":3,"title":["Optimizing Disjunctive Queries with Tagged Execution"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-4692-0757","authenticated-orcid":false,"given":"Albert","family":"Kim","sequence":"first","affiliation":[{"name":"CSAIL, MIT, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7470-3265","authenticated-orcid":false,"given":"Samuel","family":"Madden","sequence":"additional","affiliation":[{"name":"CSAIL, MIT, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Laurenz Albe. 2018. Avoid OR for Better PostgreSQL Query Performance. https:\/\/www.cybertec-postgresql.com\/en\/avoid-or-for-better-performance\/"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335420"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687659"},{"key":"e_1_2_1_4_1","volume-title":"An Optimization of Disjunctive Queries: Union-Pushdown","author":"Lee Chang","unstructured":"Jae-young Chang and Sang-goo Lee. 1997. An Optimization of Disjunctive Queries: Union-Pushdown. In COMPSAC. IEEE Computer Society, 356--361."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872802"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335432"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.842265"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807171"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168654"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732279.2732280"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/1921071.1921077"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/359581.359600"},{"key":"e_1_2_1_13_1","first-page":"7","article-title":"Adaptive Query Processing","volume":"23","author":"Hellerstein Joseph M.","year":"2000","unstructured":"Joseph M. Hellerstein, Michael J. Franklin, Sirish Chandrasekaran, Amol Deshpande, Kris Hildrum, Samuel Madden, Vijayshankar Raman, and Mehul A. Shah. 2000. Adaptive Query Processing: Technology in Evolution. IEEE Data Eng. Bull. 23, 2 (2000), 7--18. http:\/\/www.cs.cmu.edu\/~natassa\/courses\/15--721\/papers\/hellerstein.pdf","journal-title":"Technology in Evolution. IEEE Data Eng. Bull."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data. 267--276","author":"Joseph","unstructured":"Joseph M. Hellerstein and Michael Stonebraker. 1993. Predicate Migration: Optimizing Queries with Expensive Predicates. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data. 267--276."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3538712.3538715"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516376"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0405736101"},{"key":"e_1_2_1_18_1","volume-title":"Query Optimization in Database Systems. ACM Computing Surveys (CSUR) (June","author":"KochJurgen JarkeMatthias","year":"1984","unstructured":"JarkeMatthias and KochJurgen. 1984. Query Optimization in Database Systems. ACM Computing Surveys (CSUR) (June 1984). https:\/\/dl.acm.org\/doi\/abs\/10.1145\/356924.356928"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457266"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064022"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00095"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191906"},{"key":"e_1_2_1_23_1","volume-title":"Atalay Mert Ileri, and Sam Madden","author":"Kim Albert","year":"2022","unstructured":"Albert Kim, Atalay Mert Ileri, and Sam Madden. 2022. Optimizing Query Predicates with Disjunctions for Column Stores. arXiv:2002.00540 [cs] http:\/\/arxiv.org\/abs\/2002.00540"},{"key":"e_1_2_1_24_1","unstructured":"Albert Kim and Samuel Madden. 2024. Optimizing Disjunctive Queries with Tagged Execution. arXiv:2404.09109 [cs] http:\/\/arxiv.org\/abs\/2404.09109"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316773"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367518"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564698"},{"key":"e_1_2_1_29_1","volume-title":"Simon","author":"Melton Jim","year":"1993","unstructured":"Jim Melton and Alan R. Simon. 1993. Understanding the New SQL: A Complete Guide. Morgan Kaufmann. https:\/\/books.google.com\/books?hl=en&lr=&id=ZOOMSTZ4T_QC&oi=fnd&pg=PA1&dq=Understanding+the+New+SQL:+A+Complete+Guide&ots=e3HaeNQ5hu&sig=7hniGDnnji36apNp8_6hvtt5VtY"},{"key":"e_1_2_1_30_1","unstructured":"Murali Muralikrishna. 1988. Optimization of Multiple-Disjunct Queries in a Relational Database System. Technical Report. University of Wisconsin-Madison Department of Computer Sciences."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/308386.308452"},{"key":"e_1_2_1_32_1","volume-title":"Russell and Peter Norvig","author":"Stuart","year":"2016","unstructured":"Stuart J. Russell and Peter Norvig. 2016. Artificial Intelligence: A Modern Approach. Malaysia; Pearson Education Limited,."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_34_1","first-page":"11","article-title":"Bypassing Joins in Disjunctive Queries","volume":"95","author":"Steinbrunn Michael","year":"1995","unstructured":"Michael Steinbrunn, Klaus Peithner, Guido Moerkotte, and Alfons Kemper. 1995. Bypassing Joins in Disjunctive Queries. In VLDB, Vol. 95. 11--15.","journal-title":"VLDB"},{"key":"e_1_2_1_35_1","volume-title":"Rowe","author":"Stonebraker Michael","year":"1986","unstructured":"Michael Stonebraker and Lawrence A. Rowe. 1986. The Design of Postgres. Vol. 15. ACM."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/102675.102678"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654961","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654961","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:42:18Z","timestamp":1755787338000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654961"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654961"],"URL":"https:\/\/doi.org\/10.1145\/3654961","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}