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
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

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

Rank Citing Paper Year Venue Pagerank
1,237 In-Memory Subgraph Matching: An In-depth Study 2020 SIGMOD 0.00011545768
1,740 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 9.875587e-05
2,035 RapidMatch: A Holistic Approach to Subgraph Query Processing 2021 VLDB 9.2787188e-05
2,190 Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching 2021 SIGMOD 8.9804702e-05
2,915 GraphScope: A Unified Engine For Big Graph Processing 2021 VLDB 7.9666977e-05
3,018 The LDBC Social Network Benchmark: Business Intelligence Workload 2023 VLDB 7.8473755e-05
3,027 Sortledton: a Universal, Transactional Graph Data Structure 2022 VLDB 7.8374092e-05
3,070 Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs 2022 VLDB 7.7900444e-05
3,102 Efficient GPU-Accelerated Subgraph Matching 2023 SIGMOD 7.7568687e-05
3,194 GuP: Fast Subgraph Matching by Guard-based Pruning 2023 SIGMOD 7.6491858e-05
3,283 A Learned Sketch for Subgraph Counting 2021 SIGMOD 7.56675e-05
3,357 Columnar Storage and List-based Processing for Graph Database Management Systems 2021 VLDB 7.4904874e-05
4,158 HUGE: An Efficient and Scalable Subgraph Enumeration System 2021 SIGMOD 6.8628196e-05
4,544 ByteGraph: A High-Performance Distributed Graph Database in ByteDance 2022 VLDB 6.6382612e-05
4,563 Circinus: Fast Redundancy-Reduced Subgraph Matching 2023 SIGMOD 6.6291459e-05
4,722 Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming 2021 VLDB 6.5438628e-05
4,753 Worst-Case Optimal Graph Joins in Almost No Space 2021 SIGMOD 6.5231863e-05
4,983 A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024 SIGMOD 6.4127092e-05
5,275 RapidFlow: An Efficient Approach to Continuous Subgraph Matching 2022 VLDB 6.2873652e-05
5,506 Accurate and Fast Approximate Graph Pattern Mining at Scale 2025 VLDB 6.1925892e-05
5,529 Debunking the Myth of Join Ordering: Toward Robust SQL Analytics 2025 SIGMOD 6.18591e-05
5,781 Free Join: Unifying Worst-Case Optimal and Traditional Joins 2023 SIGMOD 6.0910397e-05
5,870 An In-Depth Study of Continuous Subgraph Matching 2022 VLDB 6.061038e-05
5,938 PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration 2021 SIGMOD 6.0343238e-05
5,942 Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach 2024 VLDB 6.0334209e-05
6,149 Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024 VLDB 5.9581422e-05
6,325 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 5.9125893e-05
6,387 Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges 2022 VLDB 5.8896555e-05
6,393 BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification 2023 VLDB 5.8879832e-05
6,456 LSMGraph: A High-Performance Dynamic Graph Storage System with Multi-Level CSR 2024 SIGMOD 5.8741786e-05
6,704 ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation 2024 SIGMOD 5.797374e-05
7,067 PimPam: Efficient Graph Pattern Matching on Real Processing-in-Memory Hardware 2024 SIGMOD 5.7120928e-05
7,386 Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores 2025 VLDB 5.6273882e-05
8,251 Fast Local Subgraph Counting 2024 VLDB 5.4574671e-05
8,468 Making RDBMSs Efficient on Graph Workloads Through Predefined Joins 2022 VLDB 5.418656e-05
8,478 T-FSM: A Task-Based System for Massively Parallel Frequent Subgraph Pattern Mining from a Big Graph 2023 SIGMOD 5.4170414e-05
9,617 NeuSO: Neural Optimizer for Subgraph Queries 2026 SIGMOD 5.2434488e-05
9,693 Subgraph Matching: A New Decomposition Based Approach 2025 VLDB 5.2351259e-05
9,867 SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning 2025 SIGMOD 5.2043672e-05
9,872 TC-Match: Fast Time-constrained Continuous Subgraph Matching 2024 VLDB 5.2043672e-05
9,920 Still Asking: How Good Are Query Optimizers, Really? 2025 VLDB 5.1955087e-05
9,942 A Modular Graph-Native Query Optimization Framework 2025 SIGMOD 5.1915905e-05
10,060 TenGraph: A Tensor-Based Graph Query Engine 2024 VLDB 5.166346e-05
10,237 Factorized and Vectorized Execution: Optimizing Analytical and Semantic Queries over Relations 2026 SIGMOD 5.093636e-05
10,375 GraphMatch: Subgraph Query Processing on Steroids 2026 SIGMOD 5.093636e-05
10,419 A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis] 2026 SIGMOD 5.093636e-05
10,420 SG-Serve: Efficient Model Serving for Subgraph-based Graph Representation Learning 2026 SIGMOD 5.093636e-05
10,428 An Extensive Experimental Study of Indexes in Continuous Subgraph Matching:[Experiments & Analysis] 2026 SIGMOD 5.093636e-05
10,488 R2O: A Dual-Layer Framework for Joint Rewriting and Ordering in Distributed Property Graph Query Optimization 2026 SIGMOD 5.093636e-05
10,526 TurboLynx: Schemaless Graph Engine Strikes Back for General-Purpose Analytics 2026 VLDB 5.093636e-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
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
Previous Page 1 / 1 Next

Semantically Similar Papers