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.00014578373
Overall Rank
712 | 95.22%
DOI
10.14778/3342263.3342643

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.00011627669
1,596 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 0.00010127607
1,900 Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching 2021 SIGMOD 9.4059063e-05
2,014 RapidMatch: A Holistic Approach to Subgraph Query Processing 2021 VLDB 9.1832045e-05
2,774 GraphScope: A Unified Engine For Big Graph Processing 2021 VLDB 8.0327008e-05
2,959 Sortledton: a Universal, Transactional Graph Data Structure 2022 VLDB 7.8076128e-05
2,974 Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs 2022 VLDB 7.7938744e-05
3,011 Efficient GPU-Accelerated Subgraph Matching 2023 SIGMOD 7.7549462e-05
3,055 The LDBC Social Network Benchmark: Business Intelligence Workload 2023 VLDB 7.6979859e-05
3,160 A Learned Sketch for Subgraph Counting 2021 SIGMOD 7.5807496e-05
3,164 GuP: Fast Subgraph Matching by Guard-based Pruning 2023 SIGMOD 7.5771124e-05
3,204 Columnar Storage and List-based Processing for Graph Database Management Systems 2021 VLDB 7.5400217e-05
4,075 A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024 SIGMOD 6.8188389e-05
4,123 HUGE: An Efficient and Scalable Subgraph Enumeration System 2021 SIGMOD 6.7927568e-05
4,499 ByteGraph: A High-Performance Distributed Graph Database in ByteDance 2022 VLDB 6.5746329e-05
4,511 Circinus: Fast Redundancy-Reduced Subgraph Matching 2023 SIGMOD 6.5681258e-05
4,605 Worst-Case Optimal Graph Joins in Almost No Space 2021 SIGMOD 6.5047683e-05
4,779 Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming 2021 VLDB 6.4163774e-05
4,950 Debunking the Myth of Join Ordering: Toward Robust SQL Analytics 2025 SIGMOD 6.3421691e-05
5,010 Free Join: Unifying Worst-Case Optimal and Traditional Joins 2023 SIGMOD 6.3149028e-05
5,377 RapidFlow: An Efficient Approach to Continuous Subgraph Matching 2022 VLDB 6.1562325e-05
5,422 Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach 2024 VLDB 6.1361195e-05
5,450 Accurate and Fast Approximate Graph Pattern Mining at Scale 2025 VLDB 6.1247776e-05
5,901 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 5.9539374e-05
5,984 An In-Depth Study of Continuous Subgraph Matching 2022 VLDB 5.926237e-05
6,045 PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration 2021 SIGMOD 5.9054678e-05
6,120 LSMGraph: A High-Performance Dynamic Graph Storage System with Multi-Level CSR 2024 SIGMOD 5.880693e-05
6,232 Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024 VLDB 5.84313e-05
6,485 Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges 2022 VLDB 5.7688767e-05
6,504 BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification 2023 VLDB 5.7617085e-05
6,805 Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores 2025 VLDB 5.6780394e-05
6,818 ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation 2024 SIGMOD 5.672718e-05
6,893 PimPam: Efficient Graph Pattern Matching on Real Processing-in-Memory Hardware 2024 SIGMOD 5.6540469e-05
7,251 T-FSM: A Task-Based System for Massively Parallel Frequent Subgraph Pattern Mining from a Big Graph 2023 SIGMOD 5.574104e-05
7,529 Fast Local Subgraph Counting 2024 VLDB 5.5009945e-05
8,641 Making RDBMSs Efficient on Graph Workloads Through Predefined Joins 2022 VLDB 5.2970759e-05
8,891 Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds 2025 VLDB 5.2559789e-05
9,361 Subgraph Matching: A New Decomposition Based Approach 2025 VLDB 5.1868213e-05
9,797 NeuSO: Neural Optimizer for Subgraph Queries 2026 SIGMOD 5.1257999e-05
9,950 HoneyComb: A Parallel Worst-Case Optimal Join on Multicores 2025 SIGMOD 5.1038322e-05
10,057 SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning 2025 SIGMOD 5.0875952e-05
10,062 TC-Match: Fast Time-constrained Continuous Subgraph Matching 2024 VLDB 5.0875952e-05
10,103 Still Asking: How Good Are Query Optimizers, Really? 2025 VLDB 5.0789354e-05
10,127 A Modular Graph-Native Query Optimization Framework 2025 SIGMOD 5.0751052e-05
10,251 TenGraph: A Tensor-Based Graph Query Engine 2024 VLDB 5.0513876e-05
10,254 A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis] 2026 SIGMOD 5.050482e-05
10,270 GraphMatch: Subgraph Query Processing on Steroids 2026 SIGMOD 5.0485061e-05
10,452 Factorized and Vectorized Execution: Optimizing Analytical and Semantic Queries over Relations 2026 SIGMOD 4.9793485e-05
10,609 SG-Serve: Efficient Model Serving for Subgraph-based Graph Representation Learning 2026 SIGMOD 4.9793485e-05
10,617 An Extensive Experimental Study of Indexes in Continuous Subgraph Matching:[Experiments & Analysis] 2026 SIGMOD 4.9793485e-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.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
Previous Page 1 / 1 Next

Semantically Similar Papers