The Operator Ordering Algorithm

• Based on query graphs;

• similar to Kruskal’s spanning tree algorithm, but with a twist:

• is polynomial: O(n3), can handle 100 joins in 32 msecs;

• handles nestings & unnestings as graph dependencies;

• can handle disjunctions and dependent predicates;

• beats other related proposals in performance.

0.6

0.4

0.2

R2

R3

R1

0.24

R1 >< R2

R3

pred13

pred23

pred12

pred13 ? pred23

Previous slide

Next slide

Back to first slide

View graphic version