Bug #55955 crash in MEMORY engine with IN(LEFT JOIN (JOIN))
Submitted: 12 Aug 2010 17:54 Modified: 22 Nov 2010 1:17
Reporter: Guilhem Bichot Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S3 (Non-critical)
Version:mysql-next-mr-opt-backporting OS:Linux
Assigned to: Roy Lyseng CPU Architecture:Any
Tags: optimizer_switch, semijoin

[12 Aug 2010 17:54] Guilhem Bichot
Description:
Since guilhem.bichot@oracle.com-20100812114810-h67bxlu20az1bq25 , which fixes BUG#54437 and thus makes IN(LEFT JOIN) rightfully use semijoin methods instead of producing duplicates, IN(LEFT JOIN) may now use Duplicates Weedout and thus hit Duplicates Weedout bugs.
The SELECT in "how-to-repeat" hits BUG#49129:
select * from t1 where t1.a in (select t2.a from t2 left join (t2 as t2inner,t3) on t2.a=t3.a);
# returns one row ("1") instead of two ("1" and "1")

[note that before the fix for BUG#54437, we would get too many rows instead].

After applying the patch listed in BUG#49129 (which I believe to be correct) I instead get a crash:
Program received signal SIGSEGV, Segmentation fault.
0x00000000008b5095 in hp_movelink (pos=0x3442bd0, next_link=0x0, newlink=0x3442bc0) at /m/bzrrepos_new/54481/storage/heap/hp_hash.c:232
Current language:  auto; currently c
(gdb) bt
#0  0x00000000008b5095 in hp_movelink (pos=0x3442bd0, next_link=0x0, newlink=0x3442bc0) at /m/bzrrepos_new/54481/storage/heap/hp_hash.c:232
#1  0x00000000008b9b0e in hp_write_key (info=0x33f6fb0, keyinfo=0x33f75f0, record=0x33f6ea0 "ÿ\027", recpos=0x3423bd0 "") at /m/bzrrepos_new/54481/etc

How to repeat:
create table t1 (a int);
create table t2 (a int);
create table t3 (a int);
insert into t1 values(1),(1);
insert into t2 values(1),(1);#,(1),(1);
insert into t3 values(2),(2);

select * from t1 where t1.a in (select t2.a from t2 left join (t2 as t2inner,t3) on t2.a=t3.a);

Suggested fix:
This is because we try to insert a malformed record into the duplicates weedout temporary MEMORY table. Which is because the tables "included" in this table are t1,t2inner,t3 (note: t2 isn't). t2inner and t3 should not be included; there is a test for this in sj_table_is_included(): if the table is in a semijoin nest (i.e. join_tab->emb_sj_nest!=NULL), don't include it; but for t2inner and t3, join_tab->emb_sj_nest is NULL. Why? because:
- they are in a nested join
- we have a semijoin nest which contains t2 and the nested join above
- the loop which sets emb_sj_nest, in pull_out_semijoin_tables(), stays on first level: it sets it for t2, then looks at the nested join object, which has tbl->table==NULL, so doesn't set emb_sj_nest for the nested join, and the loop doesn't dive into the nested join. So nested join tables don't get their emb_sj_nest properly set, they are left as "not in a semijoin nest". 
Fix: go down nested_joins when setting emb_sj_nest?
[12 Aug 2010 18:39] MySQL Verification Team
Hi Guilhem,

I did a fresh clone of mysql-next-mr-opt-backporting and I couldn't repeat the crash on Fedora 13 X86_64:

Your MySQL connection id is 1
Server version: 5.6.99-m4-debug Source distribution

Copyright (c) 2000, 2010, Oracle and/or its affiliates. All rights reserved.
This software comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to modify and redistribute it under the GPL v2 license

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

mysql> create table t1 (a int);
Query OK, 0 rows affected (0.22 sec)

mysql> create table t2 (a int);
Query OK, 0 rows affected (0.44 sec)

mysql> create table t3 (a int);
Query OK, 0 rows affected (0.24 sec)

mysql> insert into t1 values(1),(1);
Query OK, 2 rows affected (0.09 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> insert into t2 values(1),(1);#,(1),(1);
Query OK, 2 rows affected (0.08 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> insert into t3 values(2),(2);
Query OK, 2 rows affected (0.07 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> 
mysql> select * from t1 where t1.a in (select t2.a from t2 left join (t2 as t2inner,t3) on
    -> t2.a=t3.a);
+------+
| a    |
+------+
|    1 |
+------+
1 row in set (0.00 sec)

mysql> 

I missed something?. Thanks in advance.
[12 Aug 2010 19:10] Guilhem Bichot
Ola Miguel. Yes, you get only one row (which is a symptom of BUG#49129, you should get two rows). But please read the rest of my bug report, starting from "After applying the patch listed in BUG#49129 (which I believe to be correct) I instead get a crash". You need to apply SergeyP's patch which is in BUG#49129, to reproduce the crash. If you want, you can just trust me and set it to "verified".
[12 Aug 2010 19:50] MySQL Verification Team
Thank you for the feedback.
[2 Sep 2010 14:58] Guilhem Bichot
fix for BUG#49129 has been pushed to next-mr-opt-backporting, now the crash reported here happens as expected.
[16 Sep 2010 11:17] Bugs System
A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/118384

3244 Roy Lyseng	2010-09-16
      Bug#55955: crash in MEMORY engine with IN(LEFT JOIN (JOIN))
      
      As indicated in the "Suggested fix", the problem is that not all
      tables in a semijoin nest has the emb_sj_nest pointer set.
      The pointer is only set if the table is contained immediately within
      the semijoin nest, but according to the documentation in sql_select.h,
      it should be set for all tables within a semijoin nest.
      This is also consistent, as a table can never be included in more than
      one semijoin nest (semijoin nests cannot be nested).
      
      I have also manually inspected all uses of emb_sj_nest, and it seems that
      all uses are still consistent (previously there was an implicit assert
      that emb_sj_nest == embedding, which no longer holds).
      
      mysql-test/include/subquery_sj.inc
        Added test case for bug#55955.
      
      mysql-test/r/subquery_sj_all.result
        Semijoin plan changed from DuplicateWeedout to Materialize.
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_all_jcl6.result
        Semijoin plan changed from DuplicateWeedout to Materialize.
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_all_jcl7.result
        Semijoin plan changed from DuplicateWeedout to Materialize.
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_dupsweed.result
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_dupsweed_jcl6.result
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_dupsweed_jcl7.result
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_firstmatch.result
        Semijoin plan changed from DuplicateWeedout to FirstMatch.
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_firstmatch_jcl6.result
        Semijoin plan changed from DuplicateWeedout to FirstMatch.
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_firstmatch_jcl7.result
        Semijoin plan changed from DuplicateWeedout to FirstMatch.
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_loosescan.result
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_loosescan_jcl6.result
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_loosescan_jcl7.result
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_mat.result
        Semijoin plan changed from DuplicateWeedout to Materialize.
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_mat_jcl6.result
        Semijoin plan changed from DuplicateWeedout to Materialize.
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_mat_jcl7.result
        Semijoin plan changed from DuplicateWeedout to Materialize.
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_mat_nosj.result
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_none.result
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_none_jcl6.result
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_none_jcl7.result
        Added test case result for bug#55955.
      
      sql/sql_select.cc
        Moved setting of emb_sj_nest from pullout_semijoin_tables() to
        make_join_statistics(). pullout_semijoin_tables() only went through
        tables immediately contained in the semijoin nests, and the code
        strictly did not belong here. It is easier to loop over all join
        tabs and check whether they belong to a semijoin nest through
        some nesting.
      
        Also did a few minor cleanups, by using explicit initializers
        instead of assignment to a variable inside an expression,
        adding a set of parentheses to make syntax clearer, fixing some
        argument documentation mistakes, and removing a redundant reference
        to 'sj_corr_tables'.
[20 Sep 2010 14:10] Bugs System
A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/118607

3244 Roy Lyseng	2010-09-20
      Bug#55955: crash in MEMORY engine with IN(LEFT JOIN (JOIN))
      
      As indicated in the "Suggested fix", the problem is that not all
      tables in a semijoin nest has the emb_sj_nest pointer set.
      The pointer is only set if the table is contained immediately within
      the semijoin nest, but according to the documentation in sql_select.h,
      it should be set for all tables within a semijoin nest.
      This is also consistent, as a table can never be included in more than
      one semijoin nest (semijoin nests cannot be nested).
      
      I have also manually inspected all uses of emb_sj_nest, and it seems that
      all uses are still consistent (previously there was an implicit assert
      that emb_sj_nest == embedding, which no longer holds).
      
      There are a few semijoin plan changes. They happened because the choice
      of plan is now taken on a correct basis.
      
      mysql-test/include/subquery_sj.inc
        Added test case for bug#55955.
      
      mysql-test/r/subquery_sj_all.result
        Semijoin plan changed from DuplicateWeedout to Materialize.
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_all_jcl6.result
        Semijoin plan changed from DuplicateWeedout to Materialize.
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_all_jcl7.result
        Semijoin plan changed from DuplicateWeedout to Materialize.
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_dupsweed.result
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_dupsweed_jcl6.result
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_dupsweed_jcl7.result
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_firstmatch.result
        Semijoin plan changed from DuplicateWeedout to FirstMatch.
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_firstmatch_jcl6.result
        Semijoin plan changed from DuplicateWeedout to FirstMatch.
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_firstmatch_jcl7.result
        Semijoin plan changed from DuplicateWeedout to FirstMatch.
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_loosescan.result
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_loosescan_jcl6.result
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_loosescan_jcl7.result
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_mat.result
        Semijoin plan changed from DuplicateWeedout to Materialize.
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_mat_jcl6.result
        Semijoin plan changed from DuplicateWeedout to Materialize.
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_mat_jcl7.result
        Semijoin plan changed from DuplicateWeedout to Materialize.
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_mat_nosj.result
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_none.result
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_none_jcl6.result
        Added test case result for bug#55955.
      
      mysql-test/r/subquery_sj_none_jcl7.result
        Added test case result for bug#55955.
      
      sql/sql_select.cc
        Moved setting of emb_sj_nest from pullout_semijoin_tables() to
        make_join_statistics(). pullout_semijoin_tables() only went through
        tables immediately contained in the semijoin nests, and the code
        strictly did not belong here. It is easier to loop over all join
        tabs and check whether they belong to a semijoin nest through
        some nesting.
      
        Also did a few minor cleanups, by using explicit initializers
        instead of assignment to a variable inside an expression,
        adding a set of parentheses to make syntax clearer, fixing some
        argument documentation mistakes, and removing a redundant reference
        to 'sj_corr_tables' (it is fully contained within sj_depends_on,
        which it is ORed with).
[2 Oct 2010 18:13] Bugs System
Pushed into mysql-next-mr (revid:alexander.nozdrin@oracle.com-20101002181053-6iotvl26uurcoryp) (version source revid:alexander.nozdrin@oracle.com-20101002180917-h0n62akupm3z20nt) (pib:21)
[13 Nov 2010 16:19] Bugs System
Pushed into mysql-trunk 5.6.99-m5 (revid:alexander.nozdrin@oracle.com-20101113155825-czmva9kg4n31anmu) (version source revid:vasil.dimov@oracle.com-20100629074804-359l9m9gniauxr94) (merge vers: 5.6.99-m4) (pib:21)
[22 Nov 2010 1:17] Paul DuBois
Not in any released 5.6.x version. No changelog entry needed.