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.00014622696
Overall Rank: 706 | 95.27%
DOI: 10.14778/3342263.3342643
PDF: Download (CC BY-NC-ND 4.0)

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 50 of 67 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,171	In-Memory Subgraph Matching: An In-depth Study	2020	SIGMOD	0.00011677799
1,603	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	0.00010090639
1,907	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	9.379165e-05
1,988	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB	9.2301018e-05
2,594	GraphScope: A Unified Engine For Big Graph Processing	2021	VLDB	8.2278437e-05
2,977	Sortledton: a Universal, Transactional Graph Data Structure	2022	VLDB	7.7781129e-05
2,987	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.767043e-05
3,020	Efficient GPU-Accelerated Subgraph Matching	2023	SIGMOD	7.7267183e-05
3,066	The LDBC Social Network Benchmark: Business Intelligence Workload	2023	VLDB	7.6714389e-05
3,105	A Learned Sketch for Subgraph Counting	2021	SIGMOD	7.6278115e-05
3,107	GuP: Fast Subgraph Matching by Guard-based Pruning	2023	SIGMOD	7.6265309e-05
3,215	Columnar Storage and List-based Processing for Graph Database Management Systems	2021	VLDB	7.5117201e-05
4,099	A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction	2024	SIGMOD	6.7940875e-05
4,133	HUGE: An Efficient and Scalable Subgraph Enumeration System	2021	SIGMOD	6.7738028e-05
4,370	Circinus: Fast Redundancy-Reduced Subgraph Matching	2023	SIGMOD	6.6213567e-05
4,520	ByteGraph: A High-Performance Distributed Graph Database in ByteDance	2022	VLDB	6.549791e-05
4,627	Worst-Case Optimal Graph Joins in Almost No Space	2021	SIGMOD	6.4801904e-05
4,801	Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming	2021	VLDB	6.3940913e-05
4,971	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	6.3209003e-05
5,034	Free Join: Unifying Worst-Case Optimal and Traditional Joins	2023	SIGMOD	6.2921115e-05
5,271	Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach	2024	VLDB	6.1891764e-05
5,404	RapidFlow: An Efficient Approach to Continuous Subgraph Matching	2022	VLDB	6.132986e-05
5,471	Accurate and Fast Approximate Graph Pattern Mining at Scale	2025	VLDB	6.1016355e-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
5,995	An In-Depth Study of Continuous Subgraph Matching	2022	VLDB	5.903845e-05
6,061	PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration	2021	SIGMOD	5.8831543e-05
6,135	LSMGraph: A High-Performance Dynamic Graph Storage System with Multi-Level CSR	2024	SIGMOD	5.8584732e-05
6,245	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.8210521e-05
6,251	BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification	2023	VLDB	5.8179719e-05
6,501	Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges	2022	VLDB	5.7470793e-05
6,826	Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores	2025	VLDB	5.6566963e-05
6,840	ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation	2024	SIGMOD	5.6513231e-05
6,909	PimPam: Efficient Graph Pattern Matching on Real Processing-in-Memory Hardware	2024	SIGMOD	5.6336966e-05
7,271	T-FSM: A Task-Based System for Massively Parallel Frequent Subgraph Pattern Mining from a Big Graph	2023	SIGMOD	5.5530425e-05
7,552	Fast Local Subgraph Counting	2024	VLDB	5.4802093e-05
8,667	Making RDBMSs Efficient on Graph Workloads Through Predefined Joins	2022	VLDB	5.2770612e-05
8,899	Subgraph Matching: A New Decomposition Based Approach	2025	VLDB	5.2401722e-05
8,920	Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds	2025	VLDB	5.2361195e-05
9,837	NeuSO: Neural Optimizer for Subgraph Queries	2026	SIGMOD	5.1064323e-05
9,991	HoneyComb: A Parallel Worst-Case Optimal Join on Multicores	2025	SIGMOD	5.0845476e-05
10,094	SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning	2025	SIGMOD	5.068372e-05
10,101	TC-Match: Fast Time-constrained Continuous Subgraph Matching	2024	VLDB	5.068372e-05
10,143	Still Asking: How Good Are Query Optimizers, Really?	2025	VLDB	5.0597449e-05
10,168	A Modular Graph-Native Query Optimization Framework	2025	SIGMOD	5.0559291e-05
10,286	TenGraph: A Tensor-Based Graph Query Engine	2024	VLDB	5.0333144e-05
10,289	A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis]	2026	SIGMOD	5.031399e-05
10,303	GraphMatch: Subgraph Query Processing on Steroids	2026	SIGMOD	5.0294306e-05
10,379	Algebraic Subgraph Counting	2027	SIGMOD	4.9605343e-05
10,529	Factorized and Vectorized Execution: Optimizing Analytical and Semantic Queries over Relations	2026	SIGMOD	4.9605343e-05
10,681	SG-Serve: Efficient Model Serving for Subgraph-based Graph Representation Learning	2026	SIGMOD	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
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061463175
176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00026634326
208	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00024929198
397	Worst-case Optimal Join Algorithms	2012	PODS	0.0001911958
439	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018247958
467	Design and Implementation of the LogicBlox System	2015	SIGMOD	0.00017740891
658	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00015032442
734	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00014334121
919	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB	0.00013042589
1,046	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD	0.00012315969
1,049	Graphflow: An Active Graph Database	2017	SIGMOD	0.00012293903
1,185	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011586181
1,253	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	0.00011316982
1,296	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011119184
1,417	A Distributed Graph Engine for Web Scale RDF Data	2013	VLDB	0.00010706533
1,879	Real-Time Twitter Recommendation: Online Motif Detection in Large Dynamic Graphs	2014	VLDB	9.4293777e-05
2,023	Scalable Distributed Subgraph Enumeration	2017	VLDB	9.1568397e-05
4,357	Algorithmic Aspects of Parallel Query Processing	2018	SIGMOD	6.6290396e-05
7,184	SPARTex: A Vertex-Centric Framework for RDF Data Analytics	2015	VLDB	5.5753492e-05

Semantically Similar Papers

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