DBScholar

Back to papers

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.00014571507
Overall Rank
713 | 95.21%
DOI
10.14778/3342263.3342643
PDF
Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

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 66 citing papers.

Rank Citing Paper Year Venue Pagerank
1,180 In-Memory Subgraph Matching: An In-depth Study 2020 SIGMOD 0.00011622165
1,596 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 0.00010122962
1,901 Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching 2021 SIGMOD 9.4014537e-05
2,017 RapidMatch: A Holistic Approach to Subgraph Query Processing 2021 VLDB 9.1788573e-05
2,775 GraphScope: A Unified Engine For Big Graph Processing 2021 VLDB 8.0288982e-05
2,961 Sortledton: a Universal, Transactional Graph Data Structure 2022 VLDB 7.8039167e-05
2,975 Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs 2022 VLDB 7.7905662e-05
3,012 Efficient GPU-Accelerated Subgraph Matching 2023 SIGMOD 7.7512751e-05
3,058 The LDBC Social Network Benchmark: Business Intelligence Workload 2023 VLDB 7.6943418e-05
3,161 A Learned Sketch for Subgraph Counting 2021 SIGMOD 7.5771609e-05
3,165 GuP: Fast Subgraph Matching by Guard-based Pruning 2023 SIGMOD 7.5735255e-05
3,206 Columnar Storage and List-based Processing for Graph Database Management Systems 2021 VLDB 7.5365348e-05
4,077 A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024 SIGMOD 6.8156109e-05
4,124 HUGE: An Efficient and Scalable Subgraph Enumeration System 2021 SIGMOD 6.7895411e-05
4,501 ByteGraph: A High-Performance Distributed Graph Database in ByteDance 2022 VLDB 6.5715206e-05
4,512 Circinus: Fast Redundancy-Reduced Subgraph Matching 2023 SIGMOD 6.5650165e-05
4,607 Worst-Case Optimal Graph Joins in Almost No Space 2021 SIGMOD 6.501689e-05
4,783 Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming 2021 VLDB 6.4133399e-05
4,945 Debunking the Myth of Join Ordering: Toward Robust SQL Analytics 2025 SIGMOD 6.3418058e-05
5,013 Free Join: Unifying Worst-Case Optimal and Traditional Joins 2023 SIGMOD 6.3119508e-05
5,383 RapidFlow: An Efficient Approach to Continuous Subgraph Matching 2022 VLDB 6.1533182e-05
5,426 Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach 2024 VLDB 6.1332147e-05
5,455 Accurate and Fast Approximate Graph Pattern Mining at Scale 2025 VLDB 6.1218783e-05
5,904 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 5.9511271e-05
5,984 An In-Depth Study of Continuous Subgraph Matching 2022 VLDB 5.9234316e-05
6,047 PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration 2021 SIGMOD 5.9026722e-05
6,121 LSMGraph: A High-Performance Dynamic Graph Storage System with Multi-Level CSR 2024 SIGMOD 5.8779092e-05
6,235 Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024 VLDB 5.8403639e-05
6,487 Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges 2022 VLDB 5.7661458e-05
6,506 BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification 2023 VLDB 5.758981e-05
6,811 Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores 2025 VLDB 5.6754603e-05
6,824 ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation 2024 SIGMOD 5.670071e-05
6,896 PimPam: Efficient Graph Pattern Matching on Real Processing-in-Memory Hardware 2024 SIGMOD 5.6513703e-05
7,253 T-FSM: A Task-Based System for Massively Parallel Frequent Subgraph Pattern Mining from a Big Graph 2023 SIGMOD 5.5714652e-05
7,535 Fast Local Subgraph Counting 2024 VLDB 5.4983904e-05
8,648 Making RDBMSs Efficient on Graph Workloads Through Predefined Joins 2022 VLDB 5.2945683e-05
8,900 Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds 2025 VLDB 5.2534908e-05
9,368 Subgraph Matching: A New Decomposition Based Approach 2025 VLDB 5.1843659e-05
9,804 NeuSO: Neural Optimizer for Subgraph Queries 2026 SIGMOD 5.1233734e-05
9,958 HoneyComb: A Parallel Worst-Case Optimal Join on Multicores 2025 SIGMOD 5.1014161e-05
10,062 SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning 2025 SIGMOD 5.0851868e-05
10,067 TC-Match: Fast Time-constrained Continuous Subgraph Matching 2024 VLDB 5.0851868e-05
10,107 Still Asking: How Good Are Query Optimizers, Really? 2025 VLDB 5.0765311e-05
10,131 A Modular Graph-Native Query Optimization Framework 2025 SIGMOD 5.0727027e-05
10,258 TenGraph: A Tensor-Based Graph Query Engine 2024 VLDB 5.0489964e-05
10,260 A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis] 2026 SIGMOD 5.0480912e-05
10,276 GraphMatch: Subgraph Query Processing on Steroids 2026 SIGMOD 5.0461162e-05
10,463 Factorized and Vectorized Execution: Optimizing Analytical and Semantic Queries over Relations 2026 SIGMOD 4.9769913e-05
10,620 SG-Serve: Efficient Model Serving for Subgraph-based Graph Representation Learning 2026 SIGMOD 4.9769913e-05
10,628 An Extensive Experimental Study of Indexes in Continuous Subgraph Matching:[Experiments & Analysis] 2026 SIGMOD 4.9769913e-05
Previous Page 1 / 2 Next

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.00061067652
176 Graph Indexing: A Frequent Structure-based Approach 2004 SIGMOD 0.00026688651
208 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00024899872
402 Worst-case Optimal Join Algorithms 2012 PODS 0.00019095982
438 Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism 2008 VLDB 0.00018278591
466 Design and Implementation of the LogicBlox System 2015 SIGMOD 0.00017765702
659 Efficient Subgraph Matching by Postponing Cartesian Products 2016 SIGMOD 0.00015048943
737 Graph Indexing: Tree + Delta >= Graph 2007 VLDB 0.00014357361
919 Estimating the Selectivity of XML Path Expressions for Internet Scale Applications 2001 VLDB 0.00013077728
1,042 Parallel Subgraph Listing in a Large-Scale Graph 2014 SIGMOD 0.00012331317
1,046 Graphflow: An Active Graph Database 2017 SIGMOD 0.00012316579
1,185 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD 0.00011607329
1,252 Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows 2018 VLDB 0.00011334813
1,292 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00011147959
1,410 A Distributed Graph Engine for Web Scale RDF Data 2013 VLDB 0.00010737126
1,876 Real-Time Twitter Recommendation: Online Motif Detection in Large Dynamic Graphs 2014 VLDB 9.4535107e-05
2,022 Scalable Distributed Subgraph Enumeration 2017 VLDB 9.1686153e-05
4,337 Algorithmic Aspects of Parallel Query Processing 2018 SIGMOD 6.6510297e-05
7,162 SPARTex: A Vertex-Centric Framework for RDF Data Analytics 2015 VLDB 5.5938323e-05
Previous Page 1 / 1 Next

Semantically Similar Papers