You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@calcite.apache.org by "Julian Hyde (JIRA)" <ji...@apache.org> on 2014/07/30 20:40:39 UTC
[jira] [Updated] (OPTIQ-357) Run heuristic join algorithm several
times with noise
[ https://issues.apache.org/jira/browse/OPTIQ-357?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Julian Hyde updated OPTIQ-357:
------------------------------
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.
was:
The heuristic join algorithm (OptimizeBushyJoinRule) 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.
> Run heuristic join algorithm several times with noise
> -----------------------------------------------------
>
> Key: OPTIQ-357
> URL: https://issues.apache.org/jira/browse/OPTIQ-357
> Project: Optiq
> Issue Type: Bug
> Reporter: Julian Hyde
> Assignee: Julian Hyde
>
> 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.
--
This message was sent by Atlassian JIRA
(v6.2#6252)