Efficient Exploitation of Similar Subexpressions for Query Processing

Summary: Light-weight detection of similar subexpressions to reuse results across queries/batches. Comprehensive solution: detection, construction, and cost-based optimization; covers batches, nested queries, and materialized views with speedups and low overhead. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3941
Venue: SIGMOD
Year: 2007
Pagerank: 0.00011934202
Overall Rank: 1,154 | 92.09%
DOI: 10.1145/1247480.1247540

Incoming Non-self Citations Over Time

Authors

1. Jingren Zhou (Microsoft)
2. Per-Ake Larson (Microsoft)
3. Johann-Christoph Freytag (Humboldt University of Berlin)
4. Wolfgang Lehner (Technical University of Dresden)

BibTeX Citation

@inproceedings{zhou_sigmod07,
        title = {{Efficient Exploitation of Similar Subexpressions for Query Processing}},
        author = {Zhou, Jingren and Larson, Per-Ake and Freytag, Johann-Christoph and Lehner, Wolfgang},
        series = {{SIGMOD} '07},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1247480.1247540},
        url = {https://dl.acm.org/doi/10.1145/1247480.1247540},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 32 of 32 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
438	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00018471721
803	MRShare: Sharing Across Multiple Queries in MapReduce	2010	VLDB	0.00013899943
1,555	Keyword Search in Databases: The Power of RDBMS	2009	SIGMOD	0.00010370683
1,750	Lazy Maintenance of Materialized Views	2007	VLDB	9.8392477e-05
1,765	Selecting Subexpressions to Materialize at Datacenter Scale	2018	VLDB	9.8079546e-05
2,151	An Architecture for Recycling Intermediates in a Column-store	2009	SIGMOD	9.0784444e-05
2,276	Shared Workload Optimization	2014	VLDB	8.8196376e-05
2,520	Plan-based Complex Event Detection across Distributed Sources	2008	VLDB	8.4741249e-05
2,933	EVA: A Symbolic Approach to Accelerating Exploratory Video Analytics with Materialized Views	2022	SIGMOD	7.9474026e-05
3,205	On Optimizing Operator Fusion Plans for Large-Scale Machine Learning in SystemML	2018	VLDB	7.6386536e-05
3,268	Efficient and Provable Multi-Query Optimization	2017	PODS	7.5810998e-05
3,605	Computation Reuse in Analytics Job Service at Microsoft	2018	SIGMOD	7.2640711e-05
3,946	Real-Time Multi-Pattern Detection over Event Streams	2019	SIGMOD	7.0046969e-05
4,023	Smurf: Self-Service String Matching Using Random Forests	2019	VLDB	6.949387e-05
4,101	Automated Generation of Materialized Views in Oracle	2020	VLDB	6.9009734e-05
4,240	LIMA: Fine-grained Lineage Tracing and Reuse in Machine Learning Systems	2021	SIGMOD	6.809685e-05
5,686	OLTPShare: The Case for Sharing in OLTP Workloads	2018	VLDB	6.1220514e-05
5,701	Lemo: A Cache-Enhanced Learned Optimizer for Concurrent Queries	2023	SIGMOD	6.1167049e-05
6,623	Teaching an RDBMS about ontological constraints	2016	VLDB	5.8206367e-05
6,848	Jigsaw: A Data Storage and Query Processing Engine for Irregular Table Partitioning	2021	SIGMOD	5.7550624e-05
7,213	Scalable Multi-Query Execution using Reinforcement Learning	2021	SIGMOD	5.670422e-05
7,365	Extending Graph Patterns with Conditions	2020	SIGMOD	5.6329929e-05
7,579	Resource-efficient Shared Query Execution via Exploiting Time Slackness	2021	SIGMOD	5.592546e-05
7,670	Sharing Work in Keyword Search over Databases	2011	SIGMOD	5.5709469e-05
8,143	View Selection in Semantic Web Databases	2012	VLDB	5.4801187e-05
8,483	Optimization of Common Table Expressions in MPP Database Systems	2015	VLDB	5.4157148e-05
8,527	View Selection over Knowledge Graphs in Triple Stores	2021	VLDB	5.4119882e-05
9,299	Optimizing Complex Queries with Multiple Relation Instances	2008	SIGMOD	5.2895587e-05
11,192	Atom: An Efficient Query Serving System for Embedding-based Knowledge Graph Reasoning with Operator-level Batching	2024	SIGMOD	5.093636e-05
11,297	Grouping, Subsumption, and Disjunctive Join Optimizations in Oracle	2024	VLDB	5.093636e-05
12,289	Efficient Implementation of Generalized Quantification in Relational Query Languages	2013	VLDB	5.093636e-05
12,461	Ten Thousand SQLs: Parallel Keyword Queries Computing	2010	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
87	Automated Selection of Materialized Views and Indexes for SQL Databases	2000	VLDB	0.00035281619
128	Efficient and Extensible Algorithms for Multi Query Optimization	2000	SIGMOD	0.0003072825
153	Common Expression Analysis in Database Applications	1982	SIGMOD	0.00029032276
559	Optimizing Queries Using Materialized Views: A Practical, Scalable Solution	2001	SIGMOD	0.00016528822
736	Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time	1996	SIGMOD	0.00014508563
929	Materialized View Selection and Maintenance Using Multi-Query Optimization	2001	SIGMOD	0.00013152103
2,093	Reusing Invariants: A New Strategy for Correlated Queries	1998	SIGMOD	9.1831198e-05
2,593	Cost-Based Optimization of Decision Support Queries using Transient-Views	1998	SIGMOD	8.3649196e-05
4,019	Optimizing Refresh of a Set of Materialized Views	2005	VLDB	6.9521212e-05
6,671	Stacked Indexed Views in Microsoft SQL Server	2005	SIGMOD	5.807209e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,009	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
2	10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
3	2,095	Enhanced Subquery Optimizations in Oracle	2009	VLDB
4	559	Optimizing Queries Using Materialized Views: A Practical, Scalable Solution	2001	SIGMOD
5	153	Common Expression Analysis in Database Applications	1982	SIGMOD
6	3,268	Efficient and Provable Multi-Query Optimization	2017	PODS
7	9,756	Efficient Query Re-optimization with Judicious Subquery Selections	2023	SIGMOD
8	543	Orthogonal Optimization of Subqueries and Aggregation	2001	SIGMOD
9	664	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD
10	1,362	Execution Strategies for SQL Subqueries	2007	SIGMOD