[
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)
