Optimizing Recursive Queries with Program Synthesis

Summary: Optimizing recursive queries via program synthesis; introduces the FGH-rule to rewrite recursive programs for faster evaluation. Leverages a program synthesizer, an SMT solver, and an equality saturation system; achieves up to four orders of magnitude speedups on three Datalog systems. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h926827de845cb726
Venue: SIGMOD
Year: 2022
Pagerank: 5.5794956e-05
Overall Rank: 7,167 | 51.96%
DOI: 10.1145/3514221.3517827
PDF: Download (CC BY 4.0)

Incoming Non-self Citations Over Time

Authors

1. Yisu Remy Wang (RelationalAI; University of Washington)
2. Mahmoud Abo Khamis (RelationalAI)
3. Hung Q. Ngo (RelationalAI)
4. Reinhard Pichler (Vienna University of Technology)
5. Dan Suciu (RelationalAI; University of Washington)

BibTeX Citation

@inproceedings{wang_sigmod22,
        title = {{Optimizing Recursive Queries with Program Synthesis}},
        author = {Wang, Yisu Remy and Khamis, Mahmoud Abo and Ngo, Hung Q. and Pichler, Reinhard and Suciu, Dan},
        series = {{SIGMOD} '22},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3514221.3517827},
        url = {https://dl.acm.org/doi/10.1145/3514221.3517827},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,941	SlabCity: Whole-Query Optimization using Program Synthesis	2023	VLDB	5.4056478e-05
8,176	Predicate Pushdown for Data Science Pipelines	2023	SIGMOD	5.3688159e-05
8,376	Optimizing Nested Recursive Queries	2024	SIGMOD	5.3279812e-05
9,833	Raqlet: Cross-Paradigm Compilation for Recursive Queries	2026	CIDR	5.1064323e-05
10,368	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB	5.0064651e-05
10,954	FlowLog: Efficient and Extensible Datalog via Incrementality	2026	VLDB	4.9605343e-05
11,707	The Vadalog Parallel System: Distributed Reasoning with Datalog+/-	2024	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
17	Provenance Semirings	2007	PODS	0.00059660827
18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00058816744
72	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00037421163
556	Optimizing Queries Using Materialized Views: A Practical, Scalable Solution	2001	SIGMOD	0.00016470022
787	Cosette: An Automated Prover for SQL	2017	CIDR	0.00013959502
1,443	Magic is Relevant	1990	SIGMOD	0.00010618161
2,241	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB	8.7710222e-05
2,638	Convergence of Datalog over (Pre-) Semirings	2022	PODS	8.1763678e-05
2,644	Big Data Analytics with Datalog Queries on Spark	2016	SIGMOD	8.1655777e-05
2,953	RaSQL: Greater Power and Performance for Big Data Analytics with Recursive-aggregate-SQL on Spark	2019	SIGMOD	7.8060043e-05
3,635	Minimum and Maximum Predicates in Logic Programming	1991	PODS	7.1266264e-05
3,702	Implementation of Magic-sets in a Relational Database System	1994	SIGMOD	7.0617354e-05
4,175	Asynchronous and Fault-Tolerant Recursive Datalog Evaluation in Shared-Nothing Engines	2015	VLDB	6.7506691e-05
4,505	SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra	2020	VLDB	6.5561966e-05
4,512	A Chase Too Far?	2000	SIGMOD	6.5535364e-05
5,089	Datalog Unchained	2021	PODS	6.2661323e-05
5,608	Datalog and Emerging Applications: An Interactive Tutorial	2011	SIGMOD	6.0506609e-05
5,881	Scaling-Up In-Memory Datalog Processing: Observations and Techniques	2019	VLDB	5.94241e-05
6,670	Data Migration using Datalog Program Synthesis	2020	VLDB	5.6978388e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,937	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS
2	7,282	Rule-Based Translation of Relational Queries into Iterative Programs	1986	SIGMOD
3	5,073	On the Optimization of Recursive Relational Queries: Application to Graph Queries	2020	SIGMOD
4	6,448	Optimizing Existential Datalog Queries	1988	PODS
5	2,112	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD
6	6,764	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
7	13,453	Semigroup techniques in recursive query optimization	1990	PODS
8	10,368	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB
9	8,376	Optimizing Nested Recursive Queries	2024	SIGMOD
10	13,436	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS