[prev] 56 [next]

Cost-based Query Optimiser

Approximate algorithm for cost-based optimisation:

translate SQL query to RAexp
for enough transformations RA' of RAexp {
    for each node e of RA' (recursively) {
        select RelOp method for e
        plan[i++] = RelOp method for e
    }
    cost = 0
    for each op in plan[]
        { cost += Cost(op) }
    if (cost < MinCost)
        { MinCost = cost;  BestPlan = plan }
}

Heuristics: push selections down, consider only left-deep join trees.