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.227932e-05
Overall Rank: 9,060 | 39.11%
DOI: 10.1145/3654961
PDF: Download (CC BY-SA 4.0)

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,432	Beyond Maximum Common Subgraph: A Framework Maximizing Shared Computation for Multi-Query Subgraph Matching	2026	SIGMOD	4.9769913e-05
11,623	Grouping, Subsumption, and Disjunctive Join Optimizations in Oracle	2024	VLDB	4.9769913e-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.0023943337
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061067652
25	NiagaraCQ: A Scalable Continuous Query System for Internet Databases	2000	SIGMOD	0.00053906051
34	The Design Of Postgres	1986	SIGMOD	0.00049129967
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.000408505
125	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030462671
178	The Vertica Analytic Database: C-Store 7 Years Later	2012	VLDB	0.00026620521
200	Continuously Adaptive Continuous Queries over Streams	2002	SIGMOD	0.00025444144
431	HYRISE—A Main Memory Hybrid Storage Engine	2011	VLDB	0.00018400856
669	SharedDB: Killing One Thousand Queries With One Stone	2012	VLDB	0.00014975391
1,034	A Scalable, Predictable Join Operator for Highly Concurrent Data Warehouses	2009	VLDB	0.00012389548
1,860	Optimizing Disjunctive Queries with Expensive Predicates	1994	SIGMOD	9.4862912e-05
2,225	Shared Workload Optimization	2014	VLDB	8.8062552e-05
3,722	Bypassing Joins in Disjunctive Queries	1995	VLDB	7.0684532e-05
4,057	The Case for Precision Sharing	2004	VLDB	6.8230987e-05
5,330	Efficiently Evaluating Complex Boolean Expressions	2010	SIGMOD	6.1770616e-05
5,960	Factorizing Complex Predicates in Queries to Exploit Indexes	2003	SIGMOD	5.9305837e-05
8,020	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS	5.4042188e-05
8,753	A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions	2021	SIGMOD	5.2854393e-05
9,939	Optimization of Disjunctive Predicates for Main Memory Column Stores	2017	SIGMOD	5.1076896e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,771	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB
2	11,532	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD
3	9,132	Optimization of Multi-Version Expensive Predicates	2007	SIGMOD
4	8,170	Efficient Query Re-optimization with Judicious Subquery Selections	2023	SIGMOD
5	12,586	Efficient Implementation of Generalized Quantification in Relational Query Languages	2013	VLDB
6	9,939	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,108	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
9	6,198	Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited	1989	SIGMOD
10	1,860	Optimizing Disjunctive Queries with Expensive Predicates	1994	SIGMOD