From: Timour Katchaounov
Date: January 12 2010 4:45pm
Subject: Re: why is the default of --optimizer_search_depth 62?
List-Archive: http://lists.mysql.com/internals/37635
Message-Id: <4B4CA71B.9010208@askmonty.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

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