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: 12046
Venue: VLDB
Year: 2019
Pagerank: 0.00013874588
Overall Rank: 809 | 94.46%
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 10 of 60 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,552	CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination	2026	VLDB	5.093636e-05
10,590	Aquila: A High-Concurrency System for Incremental Graph Query	2026	VLDB	5.093636e-05
10,765	HoneyComb: A Parallel Worst-Case Optimal Join on Multicores	2025	SIGMOD	5.093636e-05
10,787	cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns	2025	SIGMOD	5.093636e-05
11,072	Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds	2025	VLDB	5.093636e-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,205	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	5.093636e-05
11,282	KGFabric: A Scalable Knowledge Graph Warehouse for Enterprise Data Interconnection	2024	VLDB	5.093636e-05
11,677	Vertex-centric Parallel Computation of SQL Queries	2021	SIGMOD	5.093636e-05
11,793	IDAR: Fast Supergraph Search Using DAG Integration	2020	VLDB	5.093636e-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
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
177	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00027100548
211	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00024797217
411	Worst-case Optimal Join Algorithms	2012	PODS	0.00018902089
431	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018577017
490	Design and Implementation of the LogicBlox System	2015	SIGMOD	0.000175757
659	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00015214062
727	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00014565738
901	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB	0.00013334162
1,036	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD	0.00012499878
1,058	Graphflow: An Active Graph Database	2017	SIGMOD	0.00012378784
1,246	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	0.00011504088
1,286	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011320736
1,320	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011166426
1,387	A Distributed Graph Engine for Web Scale RDF Data	2013	VLDB	0.00010949523
1,944	Real-Time Twitter Recommendation: Online Motif Detection in Large Dynamic Graphs	2014	VLDB	9.4354517e-05
2,065	Scalable Distributed Subgraph Enumeration	2017	VLDB	9.2352771e-05
4,244	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD	6.8062787e-05
7,022	SPARTex: A Vertex-Centric Framework for RDF Data Analytics	2015	VLDB	5.7242241e-05

Semantically Similar Papers

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