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: 3508
Venue: SIGMOD
Year: 2003
Pagerank: 6.0636778e-05
Overall Rank: 5,861 | 59.79%
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,798	SMOKE: Fine-grained Lineage at Interactive Speed	2018	VLDB	9.7361937e-05
4,992	Scalable Ad-hoc Entity Extraction from Text Collections	2008	VLDB	6.4100657e-05
8,424	Sieve: A Middleware Approach to Scalable Access Control for Database Management Systems	2020	VLDB	5.4274637e-05
8,893	Optimizing Disjunctive Queries with Tagged Execution	2024	SIGMOD	5.3504579e-05
9,754	Optimization of Disjunctive Predicates for Main Memory Column Stores	2017	SIGMOD	5.2273974e-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.0024089429
95	Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers	1987	VLDB	0.00034607909
132	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030378624
675	Optimizing Queries over Multimedia Repositories	1996	SIGMOD	0.00015080025
1,073	A General Framework for the Optimization of Object-Oriented Queries	1992	SIGMOD	0.00012300294
1,826	Optimizing Disjunctive Queries with Expensive Predicates	1994	SIGMOD	9.6721003e-05
2,923	Optimizing Boolean Expressions in Object Bases	1992	VLDB	7.9578414e-05
6,451	Efficient Search of Multidimensional B-Trees	1995	VLDB	5.8751993e-05
7,858	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS	5.5305813e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
2	3,813	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD
3	1,826	Optimizing Disjunctive Queries with Expensive Predicates	1994	SIGMOD
4	3,876	Cracking the Database Store	2005	CIDR
5	11,453	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB
6	1,154	Efficient Exploitation of Similar Subexpressions for Query Processing	2007	SIGMOD
7	2,005	Practical Predicate Placement	1994	SIGMOD
8	6,009	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
9	664	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD
10	2,465	Optimization of Queries with User-defined Predicates	1996	VLDB