Guilhem,
> Hello,
>
> I see the default value for this variable is 62 (i.e. exhaustive search
> for the best query plan, as we allow maximum ~64 tables in a join). It's
> so in 5.0, 5.1, 6.0-codebase.
>
> I remember Timour explaining that indeed beyond 7 tables, exhaustive
> search becomes very costly.
>
> --optimizer-search-depth=0, documented as "make a reasonable choice",
> chooses min(number of tables, 7) (see determine_search_depth() in
> sql_select.cc).
Yes, however this is a crude estimate based on some benchmarks, and
the factorial worst-case complexity (7 ! = 5 040, 8 ! = 40 320,
9 ! = 362 880) - after 7 it grows very fast.
>
> Why is exhaustive (62) the default? I guess most users use the default
> (naturally), which is why choosing a good default is important...
>
> Does anyone have an idea or some background about this default?
>
I have some recollection that there were few main reasons for the
decision to keep exhaustive search as the default:
- backwards compatibility,
- the hypothesis that most users have joins with few tables,
- it is not clear how far from optimal plans do we get by using a greedy
search.
Since the greedy search was the first feature I implemented for MySQL, I
agreed with the above arguments. No one needed to change them since then,
there has been no single user request I am aware of.
To Monty's question the search depth is MAX_TABLES + 1 and not MAX_TABLES -
the answer is in the function best_extension_by_limited_search(). It needs
one extra recursive call to detect a complete plan and return it.
You can verify this yourself by a simple example of e.g. a two-way join. It
is possible to redesign best_extension_by_limited_search() to work with just
MAX_TABLES, but I don't see the point in such excersise.
The comment for the function best_extension_by_limited_search() clearly
states that "(0 < search_depth <= join->tables+1)", and describes the
algorithm.
I hope my explanation was clear.
Timour
