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.9305837e-05
Overall Rank: 5,960 | 59.95%
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,713	SMOKE: Fine-grained Lineage at Interactive Speed	2018	VLDB	9.8129981e-05
4,737	Scalable Ad-hoc Entity Extraction from Text Collections	2008	VLDB	6.442156e-05
8,604	Sieve: A Middleware Approach to Scalable Access Control for Database Management Systems	2020	VLDB	5.3031743e-05
9,060	Optimizing Disjunctive Queries with Tagged Execution	2024	SIGMOD	5.227932e-05
9,939	Optimization of Disjunctive Predicates for Main Memory Column Stores	2017	SIGMOD	5.1076896e-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.0023943337
97	Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers	1987	VLDB	0.00034111286
125	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030462671
686	Optimizing Queries over Multimedia Repositories	1996	SIGMOD	0.00014769852
1,099	A General Framework for the Optimization of Object-Oriented Queries	1992	SIGMOD	0.000120317
1,860	Optimizing Disjunctive Queries with Expensive Predicates	1994	SIGMOD	9.4862912e-05
2,984	Optimizing Boolean Expressions in Object Bases	1992	VLDB	7.780464e-05
6,587	Efficient Search of Multidimensional B-Trees	1995	VLDB	5.7409998e-05
8,020	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS	5.4042188e-05

Semantically Similar Papers

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