PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins

Amine Mhedhbi, Semih Salihoglu

arXiv:1903.02076v2cs.DB

TL;DR

The paper addresses how to choose query-vertex orderings and plan structures for efficient subgraph-query evaluation. It develops a cost-based optimizer for binary-join, worst-case optimal, and hybrid plans, plus adaptive ordering during execution. Across experiments, plans outside EmptyHeaded’s plan space are up to 68x more efficient, while adaptive ordering improves some runtimes by up to 4.3x.

  • Problem

    Prior theory does not explain how to choose good query-vertex orderings for worst-case optimal plans and ignores binary-join plans that can be efficient on many queries.

  • Method

    A dynamic-programming optimizer enumerates binary-join, worst-case optimal, and hybrid plans, ranks them with intersection cost plus binary-join cost, and adaptively changes worst-case optimal orderings during execution.

  • Results

    Plans outside EmptyHeaded’s plan space are up to 68x more efficient, and adaptive ordering improves some plan runtimes by up to 4.3x.

  • Takeaways & Limitations

    The optimizer generates novel hybrid plans and selects different plan types for different queries and input graphs.

  • Takeaways & Limitations

    Estimation accuracy decreases for larger estimated subgraphs, while increasing catalogue parameters improves accuracy but increases catalogue size or construction time.

Abstract

from arXiv · show

We study the problem of optimizing subgraph queries using the new worst-case optimal join plans. Worst-case optimal plans evaluate queries by matching one query vertex at a time using multiway intersections. The core problem in optimizing worst-case optimal plans is to pick an ordering of the query vertices to match. We design a cost-based optimizer that (i) picks efficient query vertex orderings for worst-case optimal plans; and (ii) generates hybrid plans that mix traditional binary joins with worst-case optimal style multiway intersections. Our cost metric combines the cost of binary joins with a new cost metric called intersection-cost. The plan space of our optimizer contains plans that are not in the plan spaces based on tree decompositions from prior work. In addition to our optimizer, we describe an adaptive technique that changes the orderings of the worst-case optimal sub-plans during query execution. We demonstrate the effectiveness of the plans our optimizer picks and adaptive technique through extensive experiments. Our optimizer is integrated into the Graphflow DBMS.

1. INTRODUCTION

Subgraph-query optimization must balance binary joins, worst-case optimal intersections, and query-vertex orderings. The paper presents a cost-based Graphflow optimizer that generates hybrid plans and adapts orderings during execution.

  • Subgraph queries find instances of a query graph in an input graph and support applications including recommendations, community detection, and fraud detection.
  • Binary-join plans match query edges incrementally, whereas worst-case optimal plans match query vertices using multiway adjacency-list intersections.
  • Worst-case optimal joins address binary joins’ asymptotically worse runtimes on cyclic queries, but prior theory does not specify good vertex orderings or account for binary-join plans.
  • The optimizer uses dynamic programming to enumerate binary-join, worst-case optimal, and hybrid plans, including hybrid plans outside prior generalized hypertree decomposition spaces.
  • Intersection cost estimates intersection work from adjacency-list sizes, while hybrid-plan ranking combines it with binary-join cost and graph-specific statistics.
  • Adaptive query-vertex ordering selects among orderings during execution, improving many worst-case optimal plans and guarding against bad orderings.
  • Plans outside EmptyHeaded’s plan space are up to 68x more efficient, while adaptive ordering improves some runtimes by up to 4.3x.

2. PRELIMINARIES

The preliminaries model labeled, directed, connected subgraph queries and explain Generic Join’s vertex-at-a-time evaluation through query-vertex ordering and iterative partial-match extensions.

  • Queries are assumed directed, connected, labeled, and composed of m query vertices and n query edges; unlabeled queries are represented using a single-label graph version.
  • Generic Join evaluates a query one vertex at a time by first choosing a query-vertex ordering and then computing successive projected subqueries.

3. OPTIMIZING WCO PLANS

WCO plan performance depends on query vertex ordering because adjacency-list directions, intermediate matches, and intersection-cache reuse change the amount of intersection work. Experiments show that suitable orderings can substantially improve runtime, while intersection cost captures these effects.

  • 3.1 WCO Plans and E/I Operator: Each query vertex ordering defines a different WCO plan, evaluated through SCAN and EXTEND/INTERSECT operators.SCAN produces matched edges, while EXTEND/INTERSECT expands partial matches using configured adjacency-list descriptors.
  • 3.2 Effects of QVOs: Three factors determine WCO intersection work: adjacency-list directions, intermediate partial matches, and intersection-cache utilization.These factors motivate comparing plans by the amount of intersection work they perform.
  • 3.2.1 Directions of Intersected Adjacency Lists: 12.1x faster: σ1 than σ2 on BerkStan, showing that the efficient adjacency-list direction depends on input-graph structure.The compared orderings intersect forward, backward, or mixed adjacency lists, and their relative efficiency varies with graph distributions.
  • 3.2.2 Number of Intermediate Partial Matches: EDGE-TRIANGLE plans are significantly faster than EDGE-2PATH plans because unlabeled queries have at least as many 2-edge paths as triangles.Ignoring directions, EDGE-2PATH performs |E| extensions plus |2Path| intersections, whereas EDGE-TRIANGLE performs |E| intersections plus |△| extensions.
  • 3.2.3 Intersection Cache Hits: 4.4x faster on Epinions and 3x faster on Amazon: a2a3a1a4 versus a1a2a3a4 because the former reuses cached intersections.The faster ordering accesses the first two triangle indices consecutively, avoiding t–1 repeated intersections.
  • 3.3 Intersection Cost: Intersection cost measures accessed and intersected adjacency-list sizes while accounting for directions, intermediate matches, and lists omitted through caching.Alternative metrics such as Cout and Cmm capture intermediate-match counts but do not distinguish plans with different directions or cache utilization.

4. FULL PLAN SPACE & DP OPTIMIZER

The optimizer searches a full tree-based plan space combining WCO-style extensions with binary joins, then uses dynamic programming to select low-cost plans. This space includes WCO, BJ, and hybrid plans, including some plans outside prior GHD-based spaces, while pruning plans under a projection constraint.

  • Full plan space: Each plan is a rooted tree whose leaves scan query edges, unary internal nodes perform WCO-style extensions, and binary internal nodes perform hash joins.Unary nodes add one query vertex; binary nodes join two child subqueries on shared query vertices.
  • Full plan space: The plan space contains WCO plans, BJ plans, and hybrid plans satisfying the projection constraint.It also contains hybrid plans that may not correspond to GHD-based plans.
  • Full plan space: Some hybrid plans outside EmptyHeaded’s plan space can be very efficient for particular queries.The paper gives a 6-cycle example not represented in EmptyHeaded’s plan space.
  • Projection constraint: The projection constraint excludes open-triangle BJ plans and certain plans duplicating query edges, which the authors argue can be replaced by more efficient alternatives.Direct triangle computation avoids materializing open triangles, while duplicated edges can close cycles and filter partial matches.
  • DP optimizer: Dynamic programming considers WCO enumeration, one-vertex E/I extensions, and binary joins for each subquery, retaining the lowest estimated-cost plan.The optimizer initializes edge costs and builds plans from k=3 through the full query size.
  • DP optimizer: Dynamic programming may sacrifice globally optimal estimated cost because intersection-cache effects can make a discarded subplan preferable, although experiments matched full enumeration.The optimizer is designed for time-efficient optimization and matched full enumeration in the reported experiments.
  • Large queries: For queries with more than 10 vertices, the optimizer avoids full WCO enumeration and keeps only a default subset of 5 lowest-cost subqueries per iteration.This reduces plan-generation time but may ignore WCO plans that benefit from the intersection cache.

5. COST & CARDINALITY ESTIMATION

The optimizer estimates partial-match cardinalities, intersection costs, and hash-join costs using a sampled subgraph catalogue. Catalogue parameters trade estimation accuracy against catalogue size and construction time.

  • Catalogue: The subgraph catalogue estimates cardinalities, E/I intersection costs, and HASH-JOIN costs for labeled subqueries.Its entries summarize adjacency-list sizes and extension selectivities for small subgraphs.
  • Catalogue: Each catalogue entry records average intersected-list size and the average number of labeled vertices extending a partial match.The two estimates are |A| and µ(Qk).
  • Catalogue construction: The catalogue is built by sampling subgraphs of at most h vertices and extending sampled edges, with h set to 3 and z set to 1000 by default.Sampling avoids enumerating all instances of each smaller subquery.
  • Cardinality estimation: Cardinality estimates multiply catalogue selectivities along a WCO extension sequence, using fallback estimates when entries for larger subgraphs are missing.The paper illustrates fallback estimation with asymmetric and symmetric triangle extensions.
  • Intersection cost: Without cache reuse, an E/I operator’s intersection cost is estimated as the partial-match cardinality multiplied by the average sizes of its intersected adjacency lists.The estimate uses µ(Qk–1) and the catalogue’s |Li| statistics.
  • Intersection cost: With intersection-cache reuse, list-size estimates are multiplied by the smaller cached subquery’s cardinality rather than the full input subquery’s cardinality.Recognizing cache utilization is critical for choosing efficient plans.
  • Limitations: Estimates worsen for subgraphs larger than h, while increasing h or sample size z improves accuracy but enlarges the catalogue or increases construction time.Graph heterogeneity also increases catalogue size.

6. ADAPTIVE WCO PLAN EVALUATION

Adaptive execution revises WCO vertex orderings for each partial match using observed adjacency-list sizes. This can reduce intersection work and improve robustness when average catalogue statistics mislead the fixed optimizer.

  • Motivation: Catalogue statistics average over sampled matches, so individual partial matches can have substantially different adjacency-list sizes and selectivities.Fixed WCO orderings are chosen from these averages, motivating adaptive selection.
  • Example: In the diamond-X example, changing the ordering for solid edges reduces their intersection cost from 2n to 0.The fixed plan’s total cost is 3n, including 2n for solid edges and n for dotted edges.
  • Adaptive plans: The adaptive plan replaces chains of at least two E/I operators and explores connected vertex orderings for each input partial match.In WCO plans, the first two query vertices remain fixed while later vertices are selected adaptively.
  • Adaptive selection: For each partial match, the executor recalculates every candidate ordering’s cost using actual adjacency-list sizes and routes the match to the cheapest next operator.Adaptive operators can feed outputs to multiple subsequent operators.
  • Evaluation: Adaptive QVO selection improves many WCO plans and guards the optimizer against choosing bad orderings.The paper reports this as the principal evaluation outcome for adaptive execution.

7. SYSTEM IMPLEMENTATION

Graphflow implements the optimizer as a single-machine, multithreaded, in-memory graph DBMS with indexed adjacency lists. Work stealing parallelizes scans and allows extensions to proceed without coordination.

  • Graphflow: Graphflow is a single-machine, multithreaded, main-memory graph DBMS implemented in Java and supporting a subset of Cypher.It indexes both forward and backward adjacency lists in sorted vertex-ID order.
  • Indexing: Adjacency lists are partitioned by edge labels and destination-vertex labels for faster access to matching edges.The indexing and partitioning support labeled subgraph-query evaluation.
  • Parallel execution: Work stealing assigns plan copies to workers that scan edge ranges from a shared queue.Workers can perform E/I extensions without coordination.
  • Parallel execution: HASH-JOIN hash tables are partitioned into many ranges to reduce lock contention during construction, while probing proceeds independently.Symmetric hash-and-probe children can share one computed subquery.

8. EVALUATION

Experiments show that plan suitability depends on query structure and data, while the optimizer usually selects optimal or near-optimal plans. Adaptive orderings improve robustness, Graphflow outperforms EH in most comparisons, and its parallel plans scale linearly through 16 cores.

  • Evaluation setup: The evaluation studies optimizer quality, plan suitability, adaptive orderings, EH comparisons, and scalability across diverse datasets and queries.The experiments use 14 queries spanning acyclic and cyclic structures, with up to 7 query vertices and 21 query edges.
  • Plan suitability: WCO plans suit dense cyclic queries, BJ plans suit some acyclic queries, and hybrid plans suit queries with separate small cyclic structures.For acyclic queries, the best plan can vary by dataset; hybrid plans are best for structures such as Q8.
  • Optimizer evaluation: 15 of 31 spectra selected the optimal plan, 21 were within 1.4x of optimal, and 28 were within 2x.Only one experiment was not close to the optimal plan; in two cases exceeding 2x, the absolute runtime difference was under a second.
  • Adaptive plans: Adaptive ordering improves every fixed plan for Q2, Q3, and Q4, with improvements up to 4.3x for one Q5 plan and 2.1x for hybrid Q10 plans.Q6 is an exception: several plans worsen, although adaptation narrows the gap between good and bad orderings; clique overheads are higher.
  • EH comparisons: Graphflow is always faster than EH-b except for two small differences, reaching 68x faster in one instance; supplying better orderings also improves EH consistently.On Q3 Google, Graphflow is 32x faster than EH-b but 1.2x slower than EH-g, showing the effect of query vertex orderings.
  • Plans beyond EH: The optimizer selects plans outside EH’s GHD-based space, including a Q9 plan that joins two triangles before a final 2-way intersection.For Q12, hybrid plans compute 4-paths with binary joins and extend them to 6-cycles with an intersection; the optimal plan varies by dataset.
  • Scalability: Graphflow’s plans scale linearly through 16 physical cores, with only a slight slowdown at 32 cores when all system resources are used.Scalability tests cover Q1, Q2, and the difficult 7-clique Q14 on larger graphs.

9. RELATED WORK

The related-work discussion situates the approach among join algorithms, subgraph systems, adaptive processing, graph indexes, and cardinality-estimation methods. It emphasizes operator-based cost optimization while noting that systematic comparisons with some specialized algorithms remain open.

  • Scope: The paper reviews WCO join algorithms, subgraph-query evaluation, and cardinality-estimation techniques related to its catalogue.It focuses on serial algorithms and single-node systems, while omitting detailed review of distributed solutions and referring to prior work on adaptive relational processing.
  • Specialized algorithms: CFL and related algorithms reduce partial matches through query decomposition, indexing, or structural processing, but systematic comparison with this approach is beyond scope.The paper contrasts these methods with its operator-based design, intended for direct implementation in cost-based DBMS optimizers.
  • Indexes and estimation: Graph indexes for paths, trees, or triangles can complement the proposed optimizer, including triangle indexes that accelerate GJ-based WCO plans.The catalogue is related to existing summaries such as Markov tables and pattern-tree structures.

10. CONCLUSIONS

The paper presents a cost-based dynamic programming optimizer covering WCO, BJ, and hybrid plans, while identifying estimator, enumeration, and optimization-integration limitations.

  • The optimizer enumerates WCO plans, BJ plans, and a large class of hybrid plans.
  • Its i-cost metric captures several runtime effects associated with query vertex orderings.
  • The optimizer generates hybrid plans that mix intersections with binary joins beyond prior subgraph-query optimizer plan spaces.
  • Future work includes advanced cardinality and i-cost estimators, faster enumeration for very large queries, and integrating optimizations for independent query components.

A. SUBSUMED EH PLANS

The optimizer’s plan space contains projection-constrained GHD-based plans, while experiments show that alternative decompositions can differ dramatically in execution time.

  • The optimizer plan space contains EmptyHeaded’s GHD-based plans that satisfy the projection constraint.
  • EmptyHeaded selects a minimum-width GHD using AGM bounds for the worst-case sizes of its subqueries.
  • For every Figure 6 query, the EmptyHeaded plans selected in the experiments satisfied the projection constraint.
  • For Q10, two minimum-width GHDs had width 2, but only one satisfied the projection constraint.
  • 150ms versus more than 30 minutes: on a Gnutella graph, the projection-constrained Q10 GHD finished quickly while the alternative did not.

B. CATALOGUE EXPERIMENTS

Catalogue experiments examine how parameters h and z trade estimation quality against catalogue size and construction time.

  • The experiments evaluate cardinality-estimation quality while omitting adjacency-list-size estimation used in i-cost estimates.
  • Larger h and z values generally produce lower q-error, but increase catalogue size and construction time, respectively.
  • The largest q-error differences occur when increasing h from 3 to 4 and z from 100 to 500.
  • Tables 10 and 11 report q-error alongside construction time or catalogue size for varying z and h values.

C. CFL COMPARISON

Graphflow is compared with CFL and Neo4j on labeled subgraph-query workloads, with faster average runtimes than CFL in most experiments and substantial advantages over Neo4j.

  • CFL postpones Cartesian products by decomposing queries into a dense core and a forest, enabling independent parts to be matched separately.
  • 1.2x to 12.2x: Graphflow is faster than CFL in all but one reported experiment under the stated output-size limits.
  • The paper cautions that faster average runtimes do not establish that Graphflow is universally superior to CFL.
  • Up to 837x: Graphflow’s reported runtimes are significantly faster than Neo4j’s, with implementation differences also contributing to the comparison.
  • Table 13 reports Graphflow and Neo4j runtimes, marking queries that did not finish within 30 minutes.
Loading 1903.02076v2…