List:Commits« Previous MessageNext Message »
From:Guilhem Bichot Date:April 26 2010 11:30am
Subject:Re: patches for BUG#50595 (diff -u format)
View as plain text  
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:
>> 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           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.

> 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
   if (some semijoin nests) restore_prev_sj_state();
- replace
         restore_prev_sj_state(remaining_tables, s, idx);
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?
patches for BUG#50595 (diff -u format)Guilhem Bichot18 Apr
  • Re: patches for BUG#50595 (diff -u format)Olav Sandstaa20 Apr
    • Re: patches for BUG#50595 (diff -u format)Guilhem Bichot23 Apr
      • Re: patches for BUG#50595 (diff -u format)Olav Sandstaa23 Apr
        • Re: patches for BUG#50595 (diff -u format)Tor Didriksen23 Apr
      • Re: patches for BUG#50595 (diff -u format)Roy Lyseng26 Apr
  • Re: patches for BUG#50595 (diff -u format)Roy Lyseng21 Apr
    • Re: patches for BUG#50595 (diff -u format)Guilhem Bichot26 Apr
    • Re: patches for BUG#50595 (diff -u format)Guilhem Bichot26 Apr
    • new review needed Re: patches for BUG#50595 (diff -u format)Guilhem Bichot27 Apr
      • Re: new review needed Re: patches for BUG#50595 (diff -u format)Olav Sandstaa27 Apr
        • Re: new review needed Re: patches for BUG#50595 (diff -u format)Guilhem Bichot27 Apr