MySQL Bugs: #54235: Extra rows with join_cache

Bug #54235	Extra rows with join_cache_level=4,6,8 and two LEFT JOIN
Submitted:	4 Jun 2010 14:42	Modified:	23 Nov 2010 3:29
Reporter:	Guilhem Bichot	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S3 (Non-critical)
Version:	next-mr-opt-backporting	OS:	Linux
Assigned to:	Guilhem Bichot	CPU Architecture:	Any
Tags:	join_cache_level, optimizer_switch

Description:
This was discovered by John Embrentsen.
I am using olav@sun.com-20100527125548-8epbdowjxdl2bm3r ; the fix for BUG#52005 doesn't change this bug; neither does the one for BUG#52636.

How to repeat:
-- source include/have_innodb.inc
set storage_engine=innodb;

CREATE TABLE `O` (
  `pk` int NOT NULL AUTO_INCREMENT,
  PRIMARY KEY (`pk`)
);

CREATE TABLE `K` (
  `pk` int(11) NOT NULL AUTO_INCREMENT,
  `col_int_key` int(11) DEFAULT NULL,
  PRIMARY KEY (`pk`),
  KEY `col_int_key` (`col_int_key`)
);

CREATE TABLE `L` (
  `pk` int(11) NOT NULL AUTO_INCREMENT,
  `col_int_key` int(11) DEFAULT NULL,
  `col_datetime` datetime DEFAULT NULL,
  PRIMARY KEY (`pk`),
  KEY `test_idx` (`col_int_key`,`pk`) USING HASH
);

INSERT INTO `L` VALUES (49,-49414144,'2006-06-04 00:00:00');
INSERT INTO `L` VALUES (50,NULL,NULL);

explain SELECT table1 .`col_datetime` 
FROM L table1 
  LEFT  JOIN K table2 
    LEFT  JOIN O table3  ON table2 .`pk` 
  ON table1 .`col_int_key` 
WHERE  6  AND table1 .`col_int_key` OR  7 AND table3 .`pk`;

SELECT table1 .`col_datetime` 
FROM L table1 
  LEFT  JOIN K table2 
    LEFT  JOIN O table3  ON table2 .`pk` 
  ON table1 .`col_int_key` 
WHERE  6  AND table1 .`col_int_key` OR  7 AND table3 .`pk`;

DROP TABLE O;
DROP TABLE K;
DROP TABLE L;

With --mysqld=--optimizer_join_cache_level=X (where X is one of 4,6,8), the result contains one extra row (NULL). Otherwise, the result contains only '2006-06-04 00:00:00' which is correct.

Hello Miguel. Tree is mysql-next-mr-opt-backporting.

Thank you for filing this bug, Guilhem.

I have another case which is likely the same issue:

DROP TABLE IF EXISTS t1, t2, t3;
CREATE TABLE t1 (a int);
CREATE TABLE t2 (a int, b_varchar varchar(10)) ENGINE=InnoDB;
INSERT INTO t2 VALUES (1,'q');
CREATE TABLE t3 (a int, b int);

SELECT t2.b_varchar
FROM t2
  LEFT JOIN
    (t1 LEFT JOIN t3 ON t3.a IS NOT NULL)
  ON t1.a IS NOT NULL
WHERE false OR t3.b IS NOT NULL;

Correct result should be the Empty set (WHERE clause yields false), which is the result I get with MySQL 5.1.

With next-mr-opt-backporting the result is:
+-----------+
| b_varchar |
+-----------+
| q         |
+-----------+
1 row in set (0.00 sec)

This specific case seems to require InnoDB as well as optimizer_join_cache_level=4|6|8.

Thanks John. Yes, it looks similar, the same areas of code are involved.

Thank you for the feedback.

For the record: Same issue observed with LEFT JOIN + RIGHT JOIN or 2 x RIGHT JOIN instead of 2 x LEFT JOIN.

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/111069

3186 Guilhem Bichot	2010-06-14
      BUG#54235 "Extra rows with join_cache_level=4,6,8 and two LEFT JOIN"
      WHERE clause was not fully processed, letting non-matching rows pass.
     @ mysql-test/r/join_outer.result
        correct result
     @ mysql-test/r/join_outer_jcl6.result
        correct result; without the code fix, each SELECT would return two rows, NULL and NULL.
     @ mysql-test/t/join_outer.test
        test for bug
     @ sql/sql_join_cache.cc
        In the test's scenario (see join_outer.test),
        "t1 LEFT JOIN (t2 LEFT JOIN t3 ON ...) ON ... WHERE t1.a OR t3.a",
        chosen plan is t1,t2,t3. As this has an outer join with more than two
        inner tables (t2,t3), join buffering happens only for
        optimizer_join_cache_level>=4 and only with incremental buffers (so,
        even numbers: 4,6,8). Is is then on for t2 and t3 and off for t1.
        
        * Desired behaviour:
        t2 and t3 are empty tables, NULLs should be generated for them (LEFT
        JOIN) and then filtered out by WHERE as t1.a and t3.a are both
        NULL. This happens fine when join buffering is off.
        
        * Important background:
        ** execution is left-to-right: we read a row from t1, then from
        t2, then from t3.
        ** please read all of the function comment of sub_select(), and of
        make_outerjoin_info(), and read
        http://dev.mysql.com/doc/refman/5.1/en/nested-join-optimization.html
        ** This clause is attached to t3:
        (trigcond[t3.found](trigcond[t2.found]((t1.a or t3.a)))
          and trigcond[t3.not_null_compl](t2.a))
        where [X] designates the variable which, if it is false, makes the
        trigcond return true, and if it is true, makes the trigcond return the
        expression in parenthesis (see Item_func_trig_cond). Where "found" is
        the flags "BOOL f1,f2,f3" described in the above http link.
        
        * How the bug comes to life:
        ** sub_select() for t1 reads a row from t1, passes down to t2:
        ** sub_select_cache() for t2 just caches t1's row and returns
        ** sub_select() of t1 repeats for the second row of t1 (which is
        irrelevant here, just helps avoiding the "const table" optimization
        which would mask the bug)
        * sub_select() for t1 is done, now it's time to finalize the result
        (in the "if (end_of_records)" branch), this is going to walk through
        cached rows of t1 and finish joining them:
        ** sub_select_cache() for t2 does that, finds no row in t2, decides
        that NULLs must thus be emitted: for that, JOIN_CACHE::join_records()
        sets join_tab->first_unmatched to t2 (first_unmatched is the "first
        inner table of the embedding nested join" per definition in comment of
        sub_select()), calls JOIN_CACHE::join_null_complements() which sets
        join_tab->first_unmatched->found to true (to say that the partial record
        should be deemed existent as far as WHERE evaluation is concerned),
        generates NULLs for t2's columns, passes down to t3:
        ** sub_select_cache() for t3 generates NULLs for t3's columns, also
        sets join_tab->first_unmatched->found to true (where
        join_tab->first_unmatched is still correctly t2), and applies the WHERE
        clause: because t3's "found" is accidentally left to false, the portion
        of the WHERE which relates to t3 is still "non-triggered", reducing the
        WHERE to "1 OR t2.a" which is true, that's how the record is not
        filtered and is wrongly sent to the client.
        
        * The fix:
        ** so the bug is that t3's "found" is not set to true. When there is
        no join buffering, NULL-complementing is done by
        evaluate_null_complemented_join_record() which does "join_tab->found=1"
        correctly; so t2's "found" is set when the function is called for t2,
        and t3's "found" is set when the function is called for t3. When there
        is join buffering, JOIN_CACHE::join_null_complements() only sets
        join_tab->first_unmatched->found (t2's).
        ** Theoretically there should not be many differences between how the
        WHERE clause is applied to a NULL-complemented record and how it is
        applied to a "really existing" record: the latter happens in
        join_matching_records(), precisely in generate_full_extensions() which
        itself calls check_match(). check_match() properly walks through t2
        and t3 and sets their "found" to true (the first iteration of
        do...while() sets it for t3, the second iteration sets it for t2
        which is t3's "first_upper").
        This setting is done by set_match_flag_if_none() which additionally
        sets a byte in the join buffer ("the match flag"). In detail, a record
        in the join buffer has a copy of "found": see start of
        JOIN_CACHE::create_flag_fields(), this copy is necessary as the cache
        holds many records, is scanned first to look for matches in the
        current table, records with matches then have their "match_flag" set,
        then the cache is scanned a second time, ignoring records with their
        match_flag set (skip_record_if_match()) and NULL-complementing the
        rest.
        ** JOIN_CACHE::join_null_complements() has code which
        looks like a partial copy of check_match(), but omits the bottom step
        (t3) and goes directly to the upper level (t2)
        ** So the fix is to align join_null_complements() with
        join_matching_records(): make it call generate_full_extensions().
        ** For this bug, calling check_match() would be enough, but:
        *** this would be less aligned
        *** generate_full_extensions() calls do_sj_dups_weedout(), which fixes
        BUG 54437 in the case of join cache + duplicates weedout.

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/111639

3207 Guilhem Bichot	2010-06-20
      BUG#54235 "Extra rows with join_cache_level=4,6,8 and two LEFT JOIN"
      WHERE clause was not fully processed, letting non-matching rows pass.
     @ mysql-test/r/join_outer.result
        correct result
     @ mysql-test/r/join_outer_jcl6.result
        correct result; without the code fix, each SELECT would return two rows, NULL and NULL.
     @ mysql-test/t/join_outer.test
        test for bug
     @ sql/sql_join_cache.cc
        In the test's scenario (see join_outer.test),
        "t1 LEFT JOIN (t2 LEFT JOIN t3 ON ...) ON ... WHERE t1.a OR t3.a",
        chosen plan is t1,t2,t3. As this has an outer join with more than two
        inner tables (t2,t3), join buffering happens only for
        optimizer_join_cache_level>=4 and only with incremental buffers (so,
        even numbers: 4,6,8). Is is then on for t2 and t3 and off for t1.
        
        * Desired behaviour:
        t2 and t3 are empty tables, NULLs should be generated for them (LEFT
        JOIN) and then filtered out by WHERE as t1.a and t3.a are both
        NULL. This happens fine when join buffering is off.
        
        * Important background:
        ** execution is left-to-right: we read a row from t1, then from
        t2, then from t3.
        ** please read all of the function comment of sub_select(), and of
        make_outerjoin_info(), and read
        http://dev.mysql.com/doc/refman/5.1/en/nested-join-optimization.html
        ** This clause is attached to t3:
        (trigcond[t3.found](trigcond[t2.found]((t1.a or t3.a)))
          and trigcond[t3.not_null_compl](t2.a))
        where [X] designates the variable which, if it is false, makes the
        trigcond return true, and if it is true, makes the trigcond return the
        expression in parenthesis (see Item_func_trig_cond). Where "found" is
        the flags "BOOL f1,f2,f3" described in the above http link.
        
        * How the bug comes to life:
        ** sub_select() for t1 reads a row from t1, passes down to t2:
        ** sub_select_cache() for t2 just caches t1's row and returns
        ** sub_select() of t1 repeats for the second row of t1 (which is
        irrelevant here, just helps avoiding the "const table" optimization
        which would mask the bug)
        * sub_select() for t1 is done, now it's time to finalize the result
        (in the "if (end_of_records)" branch), this is going to walk through
        cached rows of t1 and finish joining them:
        ** sub_select_cache() for t2 does that, finds no row in t2, decides
        that NULLs must thus be emitted: for that, JOIN_CACHE::join_records()
        sets join_tab->first_unmatched to t2 (first_unmatched is the "first
        inner table of the embedding nested join" per definition in comment of
        sub_select()), calls JOIN_CACHE::join_null_complements() which sets
        join_tab->first_unmatched->found to true (to say that the partial record
        should be deemed existent as far as WHERE evaluation is concerned),
        generates NULLs for t2's columns, passes down to t3:
        ** sub_select_cache() for t3 generates NULLs for t3's columns, also
        sets join_tab->first_unmatched->found to true (where
        join_tab->first_unmatched is still correctly t2), and applies the WHERE
        clause: because t3's "found" is accidentally left to false, the portion
        of the WHERE which relates to t3 is still "non-triggered", reducing the
        WHERE to "1 OR t2.a" which is true, that's how the record is not
        filtered and is wrongly sent to the client.
        
        * The fix:
        ** so the bug is that t3's "found" is not set to true. When there is
        no join buffering, NULL-complementing is done by
        evaluate_null_complemented_join_record() which does "join_tab->found=1"
        correctly; so t2's "found" is set when the function is called for t2,
        and t3's "found" is set when the function is called for t3. When there
        is join buffering, JOIN_CACHE::join_null_complements() only sets
        join_tab->first_unmatched->found (t2's).
        ** Theoretically there should not be many differences between how the
        WHERE clause is applied to a NULL-complemented record and how it is
        applied to a "really existing" record: the latter happens in
        join_matching_records(), precisely in generate_full_extensions() which
        itself calls check_match(). check_match() properly walks through t2
        and t3 and sets their "found" to true (the first iteration of
        do...while() sets it for t3, the second iteration sets it for t2
        which is t3's "first_upper").
        This setting is done by set_match_flag_if_none() which additionally
        sets a byte in the join buffer ("the match flag"). In detail, a record
        in the join buffer has a copy of "found": see start of
        JOIN_CACHE::create_flag_fields(), this copy is necessary as the cache
        holds many records, is scanned first to look for matches in the
        current table, records with matches then have their "match_flag" set,
        then the cache is scanned a second time, ignoring records with their
        match_flag set (skip_record_if_match()) and NULL-complementing the
        rest.
        ** JOIN_CACHE::join_null_complements() has code which
        looks like a partial copy of check_match(), but omits the bottom step
        (t3) and goes directly to the upper level (t2)
        ** So the fix is to align join_null_complements() with
        join_matching_records(): make it call generate_full_extensions().
        ** For this bug, calling check_match() would be enough, but:
        *** this would be less aligned
        *** generate_full_extensions() calls do_sj_dups_weedout(), which fixes
        BUG 54437 in the case of join cache + duplicates weedout.

queued to next-mr-opt-backporting

Pushed into mysql-next-mr (revid:alik@sun.com-20100816062819-bluwgdq8q4xysmlg) (version source revid:alik@sun.com-20100816062612-enatdwnv809iw3s9) (pib:20)

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)

Bug does not appear in any released 5.6.x version. No 5.6.1 changelog entry needed.