Amine
Mhedhbi,
PhD
candidate
David
R.
Cheriton
School
of
Computer
Science
We study the problem of optimizing subgraph queries (SQs) using the new worst-case optimal (WCO) join plans in Selinger-style cost-based optimizers. WCO plans evaluate SQs by matching one query vertex at a time using multiway intersections. The core problem in optimizing WCO plans is to pick an ordering of the query vertices to match.
We make two contributions:
- A dynamic programming optimizer for one-time SQs that picks plans that use both multiway intersections and traditional binary joins.
- An adaptive technique for one-time SQs that changes the orderings of the WCO (sub-) plans during query execution.
The optimizer uses a subgraph catalogue, which contains cardinality and cost estimates of matching small subgraphs. Our metric for one-time SQs combines (intersection-cost) i-cost with the cost of binary joins. We demonstrate the effectiveness of the plans our optimizers pick and adaptive optimization through extensive experiments.