Database Paper Browser

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
11859
Venue
VLDB
Year
2019
Pagerank
0.00012543633
Overall Rank
1,334 | 90.74%
DOI
10.14778/3342263.3342643

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 58 citing papers.

Rank Citing Paper Year Venue Pagerank
1,906 In-Memory Subgraph Matching: An In-depth Study 2020 SIGMOD 0.00010135267
2,281 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 9.122455e-05
3,034 RapidMatch: A Holistic Approach to Subgraph Query Processing 2021 VLDB 7.6737281e-05
3,119 Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching 2021 SIGMOD 7.5393376e-05
3,287 GraphScope: A Unified Engine For Big Graph Processing 2021 VLDB 7.2689944e-05
3,516 Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs 2022 VLDB 7.018912e-05
3,670 The LDBC Social Network Benchmark: Business Intelligence Workload 2023 VLDB 6.8557811e-05
3,733 Sortledton: a Universal, Transactional Graph Data Structure 2022 VLDB 6.8067988e-05
3,781 A Learned Sketch for Subgraph Counting 2021 SIGMOD 6.7691344e-05
4,017 Columnar Storage and List-based Processing for Graph Database Management Systems 2021 VLDB 6.5276062e-05
4,326 GuP: Fast Subgraph Matching by Guard-based Pruning 2023 SIGMOD 6.2772512e-05
4,756 Efficient GPU-Accelerated Subgraph Matching 2023 SIGMOD 5.9364786e-05
5,002 HUGE: An Efficient and Scalable Subgraph Enumeration System 2021 SIGMOD 5.7610359e-05
5,234 ByteGraph: A High-Performance Distributed Graph Database in ByteDance 2022 VLDB 5.609287e-05
5,490 Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming 2021 VLDB 5.4788004e-05
5,502 Circinus: Fast Redundancy-Reduced Subgraph Matching 2023 SIGMOD 5.4730826e-05
5,503 Worst-Case Optimal Graph Joins in Almost No Space 2021 SIGMOD 5.4718854e-05
5,921 RapidFlow: An Efficient Approach to Continuous Subgraph Matching 2022 VLDB 5.2681722e-05
5,968 A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024 SIGMOD 5.2469955e-05
6,207 PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration 2021 SIGMOD 5.1519085e-05
6,288 Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach 2024 VLDB 5.1226099e-05
6,294 Free Join: Unifying Worst-Case Optimal and Traditional Joins 2023 SIGMOD 5.1202075e-05
6,391 An In-Depth Study of Continuous Subgraph Matching 2022 VLDB 5.0780425e-05
6,436 Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024 VLDB 5.0554554e-05
6,640 Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges 2022 VLDB 4.9753538e-05
6,705 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 4.9507418e-05
7,091 BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification 2023 VLDB 4.8304411e-05
7,118 ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation 2024 SIGMOD 4.8204951e-05
7,122 Debunking the Myth of Join Ordering: Toward Robust SQL Analytics 2025 SIGMOD 4.8199209e-05
7,317 Accurate and Fast Approximate Graph Pattern Mining at Scale 2025 VLDB 4.7593708e-05
7,694 LSMGraph: A High-Performance Dynamic Graph Storage System with Multi-Level CSR 2024 SIGMOD 4.6712753e-05
7,936 Fast Local Subgraph Counting 2024 VLDB 4.6089395e-05
8,035 Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores 2025 VLDB 4.5967078e-05
8,487 Making RDBMSs Efficient on Graph Workloads Through Predefined Joins 2022 VLDB 4.4953604e-05
9,272 PimPam: Efficient Graph Pattern Matching on Real Processing-in-Memory Hardware 2024 SIGMOD 4.3621803e-05
9,561 T-FSM: A Task-Based System for Massively Parallel Frequent Subgraph Pattern Mining from a Big Graph 2023 SIGMOD 4.3212967e-05
9,727 SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning 2025 SIGMOD 4.2901665e-05
9,729 TC-Match: Fast Time-constrained Continuous Subgraph Matching 2024 VLDB 4.2901665e-05
9,746 Still Asking: How Good Are Query Optimizers, Really? 2025 VLDB 4.2856385e-05
9,791 A Modular Graph-Native Query Optimization Framework 2025 SIGMOD 4.2777144e-05
9,915 TenGraph: A Tensor-Based Graph Query Engine 2024 VLDB 4.2520778e-05
10,084 GraphMatch: Subgraph Query Processing on Steroids 2026 SIGMOD 4.1905499e-05
10,096 NeuSO: Neural Optimizer for Subgraph Queries 2026 SIGMOD 4.1905499e-05
10,131 A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis] 2026 SIGMOD 4.1905499e-05
10,139 An Extensive Experimental Study of Indexes in Continuous Subgraph Matching:[Experiments & Analysis] 2026 SIGMOD 4.1905499e-05
10,199 R2O: A Dual-Layer Framework for Joint Rewriting and Ordering in Distributed Property Graph Query Optimization 2026 SIGMOD 4.1905499e-05
10,238 TurboLynx: Schemaless Graph Engine Strikes Back for General-Purpose Analytics 2026 VLDB 4.1905499e-05
10,264 CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination 2026 VLDB 4.1905499e-05
10,304 Aquila: A High-Concurrency System for Incremental Graph Query 2026 VLDB 4.1905499e-05
10,498 HoneyComb: A Parallel Worst-Case Optimal Join on Multicores 2025 SIGMOD 4.1905499e-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
71 How Good Are Query Optimizers, Really? 2016 VLDB 0.00059446482
202 Graph Indexing: A Frequent Structure-based Approach 2004 SIGMOD 0.00034881375
341 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00026850764
503 Worst-case Optimal Join Algorithms 2012 PODS 0.00021517145
610 Design and Implementation of the LogicBlox System 2015 SIGMOD 0.00019204048
616 Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism 2008 VLDB 0.00019068362
895 Graph Indexing: Tree + Delta >= Graph 2007 VLDB 0.00015498104
1,045 Estimating the Selectivity of XML Path Expressions for Internet Scale Applications 2001 VLDB 0.00014451072
1,125 Efficient Subgraph Matching by Postponing Cartesian Products 2016 SIGMOD 0.00013829006
1,487 Parallel Subgraph Listing in a Large-Scale Graph 2014 SIGMOD 0.00011691164
1,621 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD 0.00011105663
1,676 A Distributed Graph Engine for Web Scale RDF Data 2013 VLDB 0.000109374
1,746 Graphflow: An Active Graph Database 2017 SIGMOD 0.0001069135
1,938 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00010025547
1,948 Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows 2018 VLDB 9.9938634e-05
2,178 Real-Time Twitter Recommendation: Online Motif Detection in Large Dynamic Graphs 2014 VLDB 9.3645765e-05
2,787 Scalable Distributed Subgraph Enumeration 2017 VLDB 8.1219297e-05
4,641 Algorithmic Aspects of Parallel Query Processing 2018 SIGMOD 6.0215749e-05
8,249 SPARTex: A Vertex-Centric Framework for RDF Data Analytics 2015 VLDB 4.5449877e-05
Previous Page 1 / 1 Next

Semantically Similar Papers