Optimizing Disjunctive Queries with Tagged Execution

Summary: Tagged execution for disjunctive predicates: tuples are partitioned into predicate-satisfying subrelations and annotated with tags that let operators eliminate redundant work / recover runtime pushdown. Key challenge is tag-space explosion; tag generalization in Basilisk keeps tags compact and yields 2.7x avg, up to 19x speedups. (summarized by gpt-5.4-mini on May 24 2026)

Paper ID: 6984
Venue: SIGMOD
Year: 2024
Pagerank: 5.3504579e-05
Overall Rank: 8,893 | 38.99%
DOI: 10.1145/3654961

Incoming Non-self Citations Over Time

Authors

1. Albert Kim (Massachusetts Institute of Technology)
2. Samuel Madden (Massachusetts Institute of Technology)

BibTeX Citation

@inproceedings{kim_sigmod24,
        title = {{Optimizing Disjunctive Queries with Tagged Execution}},
        author = {Kim, Albert and Madden, Samuel},
        series = {{SIGMOD} '24},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3654961},
        url = {https://dl.acm.org/doi/10.1145/3654961},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,204	Beyond Maximum Common Subgraph: A Framework Maximizing Shared Computation for Multi-Query Subgraph Matching	2026	SIGMOD	5.093636e-05
11,297	Grouping, Subsumption, and Disjunctive Join Optimizations in Oracle	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 20 of 20 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0024089429
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
25	NiagaraCQ: A Scalable Continuous Query System for Internet Databases	2000	SIGMOD	0.00054667018
34	The Design Of Postgres	1986	SIGMOD	0.00049302774
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00041071971
132	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030378624
186	The Vertica Analytic Database: C-Store 7 Years Later	2012	VLDB	0.00026182534
193	Continuously Adaptive Continuous Queries over Streams	2002	SIGMOD	0.00025964286
428	HYRISE—A Main Memory Hybrid Storage Engine	2011	VLDB	0.00018633493
670	SharedDB: Killing One Thousand Queries With One Stone	2012	VLDB	0.00015157572
1,022	A Scalable, Predictable Join Operator for Highly Concurrent Data Warehouses	2009	VLDB	0.00012602841
1,826	Optimizing Disjunctive Queries with Expensive Predicates	1994	SIGMOD	9.6721003e-05
2,276	Shared Workload Optimization	2014	VLDB	8.8196376e-05
3,656	Bypassing Joins in Disjunctive Queries	1995	VLDB	7.2224287e-05
3,978	The Case for Precision Sharing	2004	VLDB	6.9771565e-05
5,199	Efficiently Evaluating Complex Boolean Expressions	2010	SIGMOD	6.3216824e-05
5,861	Factorizing Complex Predicates in Queries to Exploit Indexes	2003	SIGMOD	6.0636778e-05
7,858	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS	5.5305813e-05
8,577	A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions	2021	SIGMOD	5.409313e-05
9,754	Optimization of Disjunctive Predicates for Main Memory Column Stores	2017	SIGMOD	5.2273974e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,453	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB
2	11,183	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD
3	8,980	Optimization of Multi-Version Expensive Predicates	2007	SIGMOD
4	9,756	Efficient Query Re-optimization with Judicious Subquery Selections	2023	SIGMOD
5	12,289	Efficient Implementation of Generalized Quantification in Relational Query Languages	2013	VLDB
6	9,754	Optimization of Disjunctive Predicates for Main Memory Column Stores	2017	SIGMOD
7	2,465	Optimization of Queries with User-defined Predicates	1996	VLDB
8	6,009	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
9	6,072	Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited	1989	SIGMOD
10	1,826	Optimizing Disjunctive Queries with Expensive Predicates	1994	SIGMOD