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.
200 University Avenue West
Waterloo, ON N2L 3G1