PhD Seminar • Data Systems — Evaluating Subgraph Queries With a Mix of Tradition and ModernityExport this event to calendar

Wednesday, November 14, 2018 12:15 PM EST

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:

  1. A dynamic programming optimizer for one-time SQs that picks plans that use both multiway intersections and traditional binary joins.
  2. 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.

Location 
DC - William G. Davis Computer Research Centre
1304
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
25
26
27
28
29
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
  1. 2024 (80)
    1. April (8)
    2. March (22)
    3. February (25)
    4. January (25)
  2. 2023 (296)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (25)
    5. August (30)
    6. July (30)
    7. June (22)
    8. May (23)
    9. April (32)
    10. March (31)
    11. February (18)
    12. January (22)
  3. 2022 (245)
  4. 2021 (210)
  5. 2020 (217)
  6. 2019 (255)
  7. 2018 (217)
  8. 2017 (36)
  9. 2016 (21)
  10. 2015 (36)
  11. 2014 (33)
  12. 2013 (23)
  13. 2012 (4)
  14. 2011 (1)
  15. 2010 (1)
  16. 2009 (1)
  17. 2008 (1)