Lower bound pruning?

[fabianmurariu]

Feature Request

Summary

Query optimization is a hobby of mine so if I miss something do let me know. I've been comparing Xu's paper and the original Columbia implementation with the noisepage optimizer (and a bit of orca) and I noticed a few things.

1. group cost LB is never updated and always set to -1
2. In OptimizeExpressionCostWithEnforcedProperty cur_total_cost is set to 0 then compared to infinity
3. In OptimizeGroup GetCostLB is compared (>) with context GetCostUpperBound (infinity or close to)
4. context upper bound seems to be set to infinity - cost so far (which basically means almost infinity)
5. Columbia estimation of cost LB (Figure 24) is nowhere to be found, noisepage does however DeriveStats but that seems to estimate cardinalities (not used for pruning)

Solution

Is LB pruning not worth it?

1. Figure out a place to calculate LB for a child OptimizeExpressionCostWithEnforcedProperty seems a good candidate
2. set the context upper bound to the correct value (start with infinity then set it to the best value we found so far ??)
3. compare child LB to upper bound and avoid exploring child group