Hello Roy,
Roy Lyseng a écrit, Le 21.04.2010 11:31:
> Hi Guilhem,
>
> thanks for a well documented bug fix, it's a reviewer's delight!
>
> Patch approved, see some comments below.
>
> Guilhem Bichot wrote:
>> [resending identical but with all patches in "diff -u" format]
>>
>> Hello,
>>
>> Because the fix for BUG#50595 is better understood as 6 small patches,
>> and because I need to share some analysis with reviewers, I'm not
>> using the ordinary commit mail but some text with patches in
>> attachments.
>>
>> In BUG#50595 we have a case where an EXPLAIN (or the equivalent
>> SELECT) takes 2 seconds in a 6.0-codebase, versus 1.4
>> secs in next-mr (both optimized builds BUILD/compile-pentium64 with
>> gcc, on Linux 64-bit; this was also observed on Solaris 32-bit
>> SPARC and was originally seen on pushbuild2).
>> The case is a bit artificial, a natural join between 20 tables:
>>
>> EXPLAIN SELECT CAST(f1 AS SIGNED INTEGER) AS f1,
>> CAST(f2 AS CHAR) AS f2 FROM test1.v20;
>>
>> v20 is a view which is a join between a base table and a view v19:
>> CREATE VIEW test1.v20 AS SELECT f1, f2
>> FROM test3.t1 tab1 NATURAL JOIN test1.v19 tab2;
>>
>> v19 is a view which is a join between a base table and a view v18,
>> etc: when all views are replaced by their definition ("merged" in the
>> top-level query) it makes a 20-table join.
>> The test and result are attached (bug.*).
>>
>> So the goal is to go from 2 secs to 1.4 secs.
>> I observe that compiler flags are identical; and next-mr is built with
>> gcc, 6.0-codebase with g++, but it's not a cause (building next-mr with
>> g++ doesn't make it slower).
>> The produced query plan is identical. Due to those many 20 tables, the
>> EXPLAIN query spends 95%+ of its time in greedy_search() and that's
>> where the slowdown happens. There is no semijoin in the query.
>>
>> So the culprits are in greedy_search() and what it calls:
>> best_extension_by_limited_search() which itself calls
>> best_access_path()). An analysis of those functions in next-mr vs
>> 6.0-codebase:
>> - in best_extension_by_limited_search(), 6.0-codebase calls semijoin
>> functions (advance_sj_state() and restore_prev_sj_state()). This will
>> prove to be a cause.
>> - best_extension_by_limited_search() does memcpy's of plans, which
>> means POSITION structures. In 6.0-codebase the size of this struct is
>> 184 bytes vs 40 in next-mr (due to semijoin-specific members at
>> least), but this isn't a cause (padding next-mr's POSITION to 184
>> bytes doesn't slow it down).
>> - the number of calls to best_extension_by_limited_search() (6
>> millions) and best_access_path() (14 millions) is the same in
>> 6.0-codebase and next-mr, so the number isn't the cause.
>> - In best_access_path(): 6.0-codebase uses a Loose_scan_opt object and
>> calls its member functions (to evaluate the Loosescan semijoin
>> strategy). This will prove to be a cause.
>>
>> My testcase has no index, and the best_access_path() function above
>> has a lot of index-specific code, so to verify that I wasn't slowing
>> down that index-specific code, I made a variant of the testcase by
>> adding indice (just adding "INDEX(f1),INDEX(f2)" to each CREATE TABLE).
>> With indices, EXPLAIN didn't finish after 55 minutes at 100% CPU (you
>> remember it took 2 secs without indices). The explanation is that
>> without indices, the heuristic of optimizer_prune_level eliminates many
>> plans early (don't ask me why, I don't understand this heuristic, and
>> the comments inside it:
>> /* TODO: What is the reasoning behind this condition? */
>> (!(s->key_dependent & remaining_tables) ||
>> are not encouraging). If I turn if off (optimizer_prune_level=0) then
>> EXPLAIN with no indices starts taking a very long time too.
>> I couldn't research whether this is normal (off-topic with my assigned
>> bug), so for tables with indices (and only in this case), I limited to
>> set optimizer_search_depth=5;
>> Then EXPLAIN takes 1-2 seconds which is workable for my studies.
>> So I have two testcases: one without index (with search_depth=default)
>> and one with index (with search_depth=5), and I benchmark my patches
>> against both testcases.
>>
>> To benchmark, I edit greedy_search() (which is called once in the
>> query): when the function starts I record the time with my_getsystime(),
>> when it returns I record the time again and print the difference; the
>> timer function seems to have a resolution of 100ns, which is enough.
>> Below, timings will be given in milliseconds (ms). When I benchmark, I
>> run the query 20 times, eliminate the two first runs (which seem to have
>> some jitter), then compute the average, and verify that the standard
>> deviation is below 5 ms.
>>
>>
>> no index | % faster than van. 6.0 | index | % faster
>> vanilla next-mr 1427 | -28 | 1280 | -28
>> vanilla 6.0 1979 | 0 | 1770 | 0
>>
>> So 28% is our reduction goal.
>>
>> Patch "if_around_sj_state"
>> ==========================
>>
>> Functions advance_sj_state()/restore_prev_sj_state() (credits to Roy
>> for early finger-pointing at those functions):
>> - do nothing useful for our particular test (no semijoin)
>> - but still take time: oprofile for 6.0-codebase:
>> 474720 67.6149 mysqld best_access_path(JOIN*, etc)
>> 87981 12.5312 mysqld best_extension_by_limited_etc
>> 65706 9.3586 mysqld advance_sj_state(JOIN*, etc)
>> 34818 4.9592 libm-2.10.1.so floor
>> 16248 2.3142 no-vmlinux kernel
>> 9015 1.2840 mysqld handler::scan_time()
>> 9.35% for nothing useful...
>> So the patch puts the calls to advance_sj_state() and its
>> companion restore_prev_sj_state() behind an "if(no semijoin in this
>> query)", so that they are not called if no semijoins.
<cut>
> Another possible solution is to consolidate both "restore" functions
> into e.g. "backout_join_state()" ("backout" because it is the opposite
> of "advance").
> The idx argument to restore_prev_sj_state() is redundant and can be
> removed, and you might even make the entire function inline.
I will try it. Do you mean this:
- introduce
backout_join_state(...)
{
restore_prev_nj_state();
if (some semijoin nests) restore_prev_sj_state();
}
- replace
restore_prev_nj_state(s);
restore_prev_sj_state(remaining_tables, s, idx);
by
backout_join_state(...);
in best_extension_by_limited_search()?
- and this call would hopefully be inlined and thus be as efficient as
the "if around advance_sj_state()" which I added?
