Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins

Summary: Cost-based optimizer for subgraph queries with worst-case optimal plans, enabling hybrid plans that mix binary joins and multiway intersections. Introduces intersection-cost, expands plan space beyond tree decompositions, and adds adaptive reordering during execution in Graphflow DBMS. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h35a4dd0f128c0179
Venue: VLDB
Year: 2019
Pagerank: 0.00014578373
Overall Rank: 712 | 95.22%
DOI: 10.14778/3342263.3342643

Incoming Non-self Citations Over Time

Authors

1. Amine Mhedhbi (University of Waterloo)
2. Semih Salihoglu (University of Waterloo)

BibTeX Citation

@article{mhedhbi_vldb19,
        title = {{Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins}},
        author = {Mhedhbi, Amine and Salihoglu, Semih},
        journal = {PVLDB},
        series = {{VLDB} '19},
        volume = {12},
        number = {11},
        pages = {1692--1704},
        doi = {10.14778/3342263.3342643},
        url = {https://doi.org/10.14778/3342263.3342643},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 66 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,675	R2O: A Dual-Layer Framework for Joint Rewriting and Ordering in Distributed Property Graph Query Optimization	2026	SIGMOD	4.9793485e-05
10,710	TurboLynx: Schemaless Graph Engine Strikes Back for General-Purpose Analytics	2026	VLDB	4.9793485e-05
10,734	CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination	2026	VLDB	4.9793485e-05
10,768	One Join Order Does Not Fit All: Reducing Intermediate Results with Per-Split Query Plans	2026	VLDB	4.9793485e-05
10,788	Subgraph Enumeration: Beyond Tree Decomposition	2026	VLDB	4.9793485e-05
10,802	BaCon: Efficient Batch Processing of Counting Queries	2026	VLDB	4.9793485e-05
10,817	A Unified Query Planning Framework for Conjunctive Regular Path Queries	2026	VLDB	4.9793485e-05
10,854	Worst-Case Optimal BGPs on Temporal Graphs	2026	VLDB	4.9793485e-05
10,882	Efficient GPU-Accelerated Local Subgraph Counting	2026	VLDB	4.9793485e-05
10,989	Aquila: A High-Concurrency System for Incremental Graph Query	2026	VLDB	4.9793485e-05
11,203	cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns	2025	SIGMOD	4.9793485e-05
11,535	Atom: An Efficient Query Serving System for Embedding-based Knowledge Graph Reasoning with Operator-level Batching	2024	SIGMOD	4.9793485e-05
11,546	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	4.9793485e-05
11,606	KGFabric: A Scalable Knowledge Graph Warehouse for Enterprise Data Interconnection	2024	VLDB	4.9793485e-05
11,984	Vertex-centric Parallel Computation of SQL Queries	2021	SIGMOD	4.9793485e-05
12,095	IDAR: Fast Supergraph Search Using DAG Integration	2020	VLDB	4.9793485e-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
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061066921
176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00026700508
208	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00024884544
402	Worst-case Optimal Join Algorithms	2012	PODS	0.00019104625
438	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018286607
466	Design and Implementation of the LogicBlox System	2015	SIGMOD	0.00017773029
657	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.0001505607
736	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00014363536
919	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB	0.00013083677
1,045	Graphflow: An Active Graph Database	2017	SIGMOD	0.00012322402
1,046	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD	0.00012319866
1,186	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.0001160797
1,249	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	0.00011340141
1,292	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011152286
1,410	A Distributed Graph Engine for Web Scale RDF Data	2013	VLDB	0.00010742208
1,873	Real-Time Twitter Recommendation: Online Motif Detection in Large Dynamic Graphs	2014	VLDB	9.4579851e-05
2,020	Scalable Distributed Subgraph Enumeration	2017	VLDB	9.1729558e-05
4,337	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD	6.6541797e-05
7,159	SPARTex: A Vertex-Centric Framework for RDF Data Analytics	2015	VLDB	5.5964781e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,164	Efficient Query Re-optimization with Judicious Subquery Selections	2023	SIGMOD
2	2,728	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS
3	8,651	Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation	2026	VLDB
4	143	Optimization of Nonrecursive Queries	1986	VLDB
5	2,136	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB
6	1,186	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD
7	315	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS
8	3,797	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD
9	10,508	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
10	1,596	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB