Factorizing Complex Predicates in Queries to Exploit Indexes

Summary: Factorizes complex predicates to expose indexes in decision-support queries. Introduces predicate relaxation to enable factoring; integrates with existing optimizers, offering multi-level strategies that trade plan complexity for optimization time. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h03e578d76407fba0
Venue: SIGMOD
Year: 2003
Pagerank: 5.9317876e-05
Overall Rank: 5,969 | 59.87%
DOI: 10.1145/872757.872802

Incoming Non-self Citations Over Time

Authors

1. Surajit Chaudhuri (Microsoft)
2. Prasanna Ganesan (Stanford University)
3. Sunita Sarawagi (Indian Institute of Technology Mumbai)

BibTeX Citation

@inproceedings{chaudhuri_sigmod03,
        title = {{Factorizing Complex Predicates in Queries to Exploit Indexes}},
        author = {Chaudhuri, Surajit and Ganesan, Prasanna and Sarawagi, Sunita},
        series = {{SIGMOD} '03},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/872757.872802},
        url = {https://dl.acm.org/doi/10.1145/872757.872802},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,746	SMOKE: Fine-grained Lineage at Interactive Speed	2018	VLDB	9.7341914e-05
4,736	Scalable Ad-hoc Entity Extraction from Text Collections	2008	VLDB	6.4451961e-05
8,597	Sieve: A Middleware Approach to Scalable Access Control for Database Management Systems	2020	VLDB	5.305686e-05
9,052	Optimizing Disjunctive Queries with Tagged Execution	2024	SIGMOD	5.230408e-05
9,932	Optimization of Disjunctive Predicates for Main Memory Column Stores	2017	SIGMOD	5.1101087e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 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
97	Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers	1987	VLDB	0.00034124569
125	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030470848
686	Optimizing Queries over Multimedia Repositories	1996	SIGMOD	0.00014775707
1,098	A General Framework for the Optimization of Object-Oriented Queries	1992	SIGMOD	0.00012037216
1,859	Optimizing Disjunctive Queries with Expensive Predicates	1994	SIGMOD	9.4898025e-05
2,983	Optimizing Boolean Expressions in Object Bases	1992	VLDB	7.7839431e-05
6,584	Efficient Search of Multidimensional B-Trees	1995	VLDB	5.7436357e-05
8,015	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS	5.406698e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,508	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
2	3,797	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD
3	1,859	Optimizing Disjunctive Queries with Expensive Predicates	1994	SIGMOD
4	3,951	Cracking the Database Store	2005	CIDR
5	11,765	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB
6	1,131	Efficient Exploitation of Similar Subexpressions for Query Processing	2007	SIGMOD
7	2,032	Practical Predicate Placement	1994	SIGMOD
8	6,106	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
9	646	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD
10	2,516	Optimization of Queries with User-defined Predicates	1996	VLDB