R2O: A Dual-Layer Framework for Joint Rewriting and Ordering in Distributed Property Graph Query Optimization

Summary: R2O targets distributed property-graph pattern queries by jointly optimizing partition-aware rewriting and inter-partition join ordering. Uses a dual-layer GNN+RL framework to shrink intermediate results and communication, delivering 1–2 orders-of-magnitude speedups on billion-scale graphs. (summarized by gpt-5-mini on Apr 11 2026)

Paper ID: h630ceec6c0cc1496
Venue: SIGMOD
Year: 2026
Pagerank: 4.9605343e-05
Overall Rank: 10,747 | 27.97%
DOI: 10.1145/3786685
PDF: Download (CC BY 4.0)

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Min Shi (Hunan University)
2. Peng Peng (Hunan University)
3. Xin Xiao (Hunan University)
4. Lei Zou (Peking University)
5. Kenli Li (Hunan University)
6. Xu Zhou (Hunan University)

BibTeX Citation

@inproceedings{shi_sigmod26,
        title = {{R2O: A Dual-Layer Framework for Joint Rewriting and Ordering in Distributed Property Graph Query Optimization}},
        author = {Shi, Min and Peng, Peng and Xiao, Xin and Zou, Lei and Li, Kenli and Zhou, Xu},
        series = {{SIGMOD} '26},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3786685},
        url = {https://dl.acm.org/doi/10.1145/3786685},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 24 of 24 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
142	Neo: A Learned Query Optimizer	2019	VLDB	0.00029114937
355	Bao: Making Learned Query Optimization Practical	2021	SIGMOD	0.00020146245
387	The LDBC Social Network Benchmark: Interactive Workload	2015	SIGMOD	0.00019360364
420	Cypher: An Evolving Query Language for Property Graphs	2018	SIGMOD	0.00018489392
439	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018247958
706	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00014622696
1,253	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	0.00011316982
1,428	Graph Pattern Matching in GQL and SQL/PGQ	2022	SIGMOD	0.000106884
1,608	SQLGraph: An Efficient Relational-Based Property Graph Store	2015	SIGMOD	0.00010074196
1,907	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	9.379165e-05
2,353	TriAD: A Distributed Shared-Nothing RDF Engine based on Asynchronous Message Passing	2014	SIGMOD	8.5756201e-05
2,829	G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching	2020	SIGMOD	7.9469964e-05
3,805	All-in-One: Graph Processing in RDBMSs Revisited	2017	SIGMOD	6.99039e-05
3,885	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB	6.9282318e-05
4,133	HUGE: An Efficient and Scalable Subgraph Enumeration System	2021	SIGMOD	6.7738028e-05
4,300	TurboGraph++: A Scalable and Fast Graph Analytics System	2018	SIGMOD	6.6633635e-05
4,627	Worst-Case Optimal Graph Joins in Almost No Space	2021	SIGMOD	6.4801904e-05
4,835	Taming Subgraph Isomorphism for RDF Query Processing	2015	VLDB	6.3793473e-05
5,717	Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation	2021	SIGMOD	6.0067263e-05
7,427	Galaxybase: A High Performance Native Distributed Graph Database for HTAP	2024	VLDB	5.5140658e-05
7,447	A Study of Partitioning Policies for Graph Analytics on Large-scale Distributed Platforms	2019	VLDB	5.5111792e-05
7,947	S2RDF: RDF Querying with SPARQL on Spark	2016	VLDB	5.4046857e-05
8,508	Optimizing Declarative Graph Queries at Large Scale	2019	SIGMOD	5.3124867e-05
10,168	A Modular Graph-Native Query Optimization Framework	2025	SIGMOD	5.0559291e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,646	Join Order Selection with Deep Reinforcement Learning: Fundamentals, Techniques, and Challenges	2023	VLDB
2	4,423	Avoiding Sorting and Grouping In Processing Queries	2003	VLDB
3	10,635	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD
4	7,394	ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning	2023	VLDB
5	11,856	Demonstrating ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Joins via Reinforcement Learning	2023	VLDB
6	12,432	Let's Rethink Join Optimization in Distributed Systems	2015	CIDR
7	6,743	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD
8	1,712	Rank-aware Query Optimization	2004	SIGMOD
9	3,807	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD
10	11,594	Connectivity-Oriented Property Graph Partitioning for Distributed Graph Pattern Query Processing	2024	SIGMOD