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: h7843e732377589eb
Venue: SIGMOD
Year: 2007
Pagerank: 0.00011856159
Overall Rank: 1,137 | 92.39%
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 34 of 34 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
408	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00018836656
825	MRShare: Sharing Across Multiple Queries in MapReduce	2010	VLDB	0.00013600553
1,505	Keyword Search in Databases: The Power of RDBMS	2009	SIGMOD	0.00010424285
1,757	Selecting Subexpressions to Materialize at Datacenter Scale	2018	VLDB	9.7050769e-05
1,790	Lazy Maintenance of Materialized Views	2007	VLDB	9.6228433e-05
2,092	An Architecture for Recycling Intermediates in a Column-store	2009	SIGMOD	9.0432353e-05
2,237	Shared Workload Optimization	2014	VLDB	8.7777395e-05
2,577	Plan-based Complex Event Detection across Distributed Sources	2008	VLDB	8.2538023e-05
2,792	EVA: A Symbolic Approach to Accelerating Exploratory Video Analytics with Materialized Views	2022	SIGMOD	7.9895218e-05
3,104	On Optimizing Operator Fusion Plans for Large-Scale Machine Learning in SystemML	2018	VLDB	7.6281929e-05
3,226	Efficient and Provable Multi-Query Optimization	2017	PODS	7.4987658e-05
3,550	Computation Reuse in Analytics Job Service at Microsoft	2018	SIGMOD	7.1895215e-05
4,022	Automated Generation of Materialized Views in Oracle	2020	VLDB	6.8345671e-05
4,041	Real-Time Multi-Pattern Detection over Event Streams	2019	SIGMOD	6.8217898e-05
4,080	Smurf: Self-Service String Matching Using Random Forests	2019	VLDB	6.8020845e-05
4,354	LIMA: Fine-grained Lineage Tracing and Reuse in Machine Learning Systems	2021	SIGMOD	6.6318545e-05
5,794	Lemo: A Cache-Enhanced Learned Optimizer for Concurrent Queries	2023	SIGMOD	5.9759435e-05
5,807	OLTPShare: The Case for Sharing in OLTP Workloads	2018	VLDB	5.9709922e-05
6,781	Teaching an RDBMS about ontological constraints	2016	VLDB	5.6685378e-05
6,977	Jigsaw: A Data Storage and Query Processing Engine for Irregular Table Partitioning	2021	SIGMOD	5.6135617e-05
7,347	Scalable Multi-Query Execution using Reinforcement Learning	2021	SIGMOD	5.5308106e-05
7,502	Extending Graph Patterns with Conditions	2020	SIGMOD	5.4943054e-05
7,741	Resource-efficient Shared Query Execution via Exploiting Time Slackness	2021	SIGMOD	5.4469162e-05
7,846	Sharing Work in Keyword Search over Databases	2011	SIGMOD	5.4254046e-05
8,335	View Selection in Semantic Web Databases	2012	VLDB	5.3369178e-05
8,678	Optimization of Common Table Expressions in MPP Database Systems	2015	VLDB	5.2744774e-05
8,724	View Selection over Knowledge Graphs in Triple Stores	2021	VLDB	5.2705676e-05
9,502	Optimizing Complex Queries with Multiple Relation Instances	2008	SIGMOD	5.1533173e-05
10,873	BaCon: Efficient Batch Processing of Counting Queries	2026	VLDB	4.9605343e-05
10,966	Benchmarking the Full Pipeline of Materialized-View-Based Query Rewriting	2026	VLDB	4.9605343e-05
11,590	Atom: An Efficient Query Serving System for Embedding-based Knowledge Graph Reasoning with Operator-level Batching	2024	SIGMOD	4.9605343e-05
11,670	Grouping, Subsumption, and Disjunctive Join Optimizations in Oracle	2024	VLDB	4.9605343e-05
12,629	Efficient Implementation of Generalized Quantification in Relational Query Languages	2013	VLDB	4.9605343e-05
12,801	Ten Thousand SQLs: Parallel Keyword Queries Computing	2010	VLDB	4.9605343e-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
89	Automated Selection of Materialized Views and Indexes for SQL Databases	2000	VLDB	0.00035265687
129	Efficient and Extensible Algorithms for Multi Query Optimization	2000	SIGMOD	0.00030314403
155	Common Expression Analysis in Database Applications	1982	SIGMOD	0.0002844242
556	Optimizing Queries Using Materialized Views: A Practical, Scalable Solution	2001	SIGMOD	0.00016470022
746	Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time	1996	SIGMOD	0.0001426147
927	Materialized View Selection and Maintenance Using Multi-Query Optimization	2001	SIGMOD	0.00013020035
2,132	Reusing Invariants: A New Strategy for Correlated Queries	1998	SIGMOD	8.9837489e-05
2,626	Cost-Based Optimization of Decision Support Queries using Transient-Views	1998	SIGMOD	8.1919956e-05
4,114	Optimizing Refresh of a Set of Materialized Views	2005	VLDB	6.7859696e-05
6,824	Stacked Indexed Views in Microsoft SQL Server	2005	SIGMOD	5.6568082e-05

Semantically Similar Papers

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