[CALCITE-357] Run heuristic join algorithm several times with noise

• Type: Bug
• Status: Open
• Priority: Major
• Resolution: Unresolved
• Assignee: Unassigned
• Reporter: Julian Hyde
• Created: 30/Jul/14 18:27
• Updated: 22/Feb/19 01:21

Description

The heuristic join algorithm (OptimizeBushyJoinRule) added in OPTIQ-349 is a greedy algorithm and is therefore (I surmise) prone to fall into local minima. If this behavior is observed, a solution would be to run the algorithm several times with some random noise added to the cost function. (Or randomly with small probability taking the 2nd or 3rd best edge rather than the 1st best edge at each step.)

Compare the distinct generated plans according to a cost function, and pick the best (or perhaps best N).

We should wait until we have some cases of the algorithm producing sub-optimal plans before we proceed with this.

Note that the algorithm is also susceptive to bad cost estimates (especially in join selectivity) and this won't help with those.

Issue Links

• is related to: CALCITE-349 Add heuristic join-optimizer that can generate bushy joins