When the optimizer concatenates several PlanEnumerations via some Slots, it creates the cross-product of their PlanImplementations and tries to concatenate them. This scales exponentially with the number of PlanEnumerations and should be avoided. For that matter, there is room for improvement:
If PlanEnumerations overlap w.r.t. the enumerated OperatorAlternatives, their PlanImplementations can only be concatenated if they agree on the corresponding selected Alternatives. This criterion allows to avoid enumerating the whole cross product (similar to DB join techniques).
What is more, due to our enumeration algorithm, PlanEnumerations should either be disjoint or identical. This facilitates the implementation of above proposed pruning technique in situations with nPlanEnumerations, because we don't need to inspect all n*(n-1)/2PlanEnumeration pairs, but merely need to group the concatenation Slots by their PlanEnumeration.
While this pruning technique is of course not taking away the exponential complexity of the whole problem (because it might not always be applicable), I have some good hope that in practical situations it can be quite effective.
Furthermore, this observation should also be incorporated with the concatenation priorities.
sekruse
commented
7 years ago
When the optimizer concatenates several
PlanEnumerations via someSlots, it creates the cross-product of theirPlanImplementations and tries to concatenate them. This scales exponentially with the number ofPlanEnumerations and should be avoided. For that matter, there is room for improvement:PlanEnumerations overlap w.r.t. the enumeratedOperatorAlternatives, theirPlanImplementations can only be concatenated if they agree on the corresponding selectedAlternatives. This criterion allows to avoid enumerating the whole cross product (similar to DB join techniques).PlanEnumerations should either be disjoint or identical. This facilitates the implementation of above proposed pruning technique in situations with nPlanEnumerations, because we don't need to inspect all n*(n-1)/2PlanEnumerationpairs, but merely need to group the concatenationSlots by theirPlanEnumeration.While this pruning technique is of course not taking away the exponential complexity of the whole problem (because it might not always be applicable), I have some good hope that in practical situations it can be quite effective.
Furthermore, this observation should also be incorporated with the concatenation priorities.