Evaluation Order of Operators

Problem: After query unnesting, all operators are promoted

to the same level. Order of evaluation?

Complexity: O(m!?km)

(for m operators, where each one can be evaluated in k ways)

Heuristics:

• dynamic programming of System R: O(3n)

• iterative improvement;

• simulated annealing.

Previous slide

Next slide

Back to first slide

View graphic version