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: haae79704281b5094
Venue: SIGMOD
Year: 2024
Pagerank: 5.230408e-05
Overall Rank: 9,052 | 39.14%
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,420	Beyond Maximum Common Subgraph: A Framework Maximizing Shared Computation for Multi-Query Subgraph Matching	2026	SIGMOD	4.9793485e-05
11,617	Grouping, Subsumption, and Disjunctive Join Optimizations in Oracle	2024	VLDB	4.9793485e-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.0023947656
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061066921
25	NiagaraCQ: A Scalable Continuous Query System for Internet Databases	2000	SIGMOD	0.00053930011
34	The Design Of Postgres	1986	SIGMOD	0.00049142315
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00040860054
125	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030470848
179	The Vertica Analytic Database: C-Store 7 Years Later	2012	VLDB	0.00026611886
200	Continuously Adaptive Continuous Queries over Streams	2002	SIGMOD	0.000254553
431	HYRISE—A Main Memory Hybrid Storage Engine	2011	VLDB	0.00018403783
667	SharedDB: Killing One Thousand Queries With One Stone	2012	VLDB	0.00014978213
1,034	A Scalable, Predictable Join Operator for Highly Concurrent Data Warehouses	2009	VLDB	0.00012394538
1,859	Optimizing Disjunctive Queries with Expensive Predicates	1994	SIGMOD	9.4898025e-05
2,225	Shared Workload Optimization	2014	VLDB	8.8081001e-05
3,720	Bypassing Joins in Disjunctive Queries	1995	VLDB	7.0715239e-05
4,056	The Case for Precision Sharing	2004	VLDB	6.8261065e-05
5,324	Efficiently Evaluating Complex Boolean Expressions	2010	SIGMOD	6.179987e-05
5,969	Factorizing Complex Predicates in Queries to Exploit Indexes	2003	SIGMOD	5.9317876e-05
8,015	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS	5.406698e-05
8,745	A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions	2021	SIGMOD	5.2879425e-05
9,932	Optimization of Disjunctive Predicates for Main Memory Column Stores	2017	SIGMOD	5.1101087e-05

Semantically Similar Papers

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