Bug #44019 Wrong results with a star-join query when BKA is used
Submitted: 1 Apr 2009 19:45 Modified: 20 Nov 2010 23:20
Reporter: Igor Babaev Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S1 (Critical)
Version:6.0 bzr OS:Any
Assigned to: Igor Babaev
Triage: Triaged: D2 (Serious)

[1 Apr 2009 19:45] Igor Babaev
Description:
In some cases when BKA is used with join_cache_level equal to 6 multi-join queries  may return wrong results. It may happen only when at least 3 tables are accessed by keys from some previous tables.  

How to repeat:
Create and populate tables t1,t2,t3,t4 with the following commands:

  create table t1 (a int, b int, c int, d int);
  create table t2 (b int, e varchar(16), index idx(b));
  create table t3 (d int, f varchar(16), index idx(d));
  create table t4 (c int, g varchar(16), index idx(c));
  insert into t2 values
    (30, 'bbb'), (10, 'b'), (70, 'bbbbbbb'), (60, 'bbbbbb'),
    (31, 'bbb'), (11, 'b'), (71, 'bbbbbbb'), (61, 'bbbbbb'),
    (32, 'bbb'), (12, 'b'), (72, 'bbbbbbb'), (62, 'bbbbbb');
  insert into t2 values
    (30, 'bbb'), (10, 'b'), (70, 'bbbbbbb'), (60, 'bbbbbb'),
    (31, 'bbb'), (11, 'b'), (71, 'bbbbbbb'), (61, 'bbbbbb'),
    (32, 'bbb'), (12, 'b'), (72, 'bbbbbbb'), (62, 'bbbbbb');
  insert into t4 values
    (200, 'cc'), (600, 'cccccc'), (300, 'ccc'), (500, 'ccccc'),
    (201, 'cc'), (601, 'cccccc'), (301, 'ccc'), (501, 'ccccc'),
    (202, 'cc'), (602, 'cccccc'), (302, 'ccc'), (502, 'ccccc');

The run:

  analyze table t2,t3,t4;

After this you can get the following results:

mysql> set join_cache_level=1;
Query OK, 0 rows affected (0.00 sec)

mysql> explain select t1.a, t1.b, t1.c, t1.d, t2.e, t3.f, t4.g from t1,t2,t3,t4 where t2.b=t1.b and t3.d=t1.d and t4.c=t1.c;
+----+-------------+-------+------+---------------+------+---------+-----------+------+-------+
| id | select_type | table | type | possible_keys | key  | key_len | ref       | rows | Extra |
+----+-------------+-------+------+---------------+------+---------+-----------+------+-------+
|  1 | SIMPLE      | t1    | ALL  | NULL          | NULL | NULL    | NULL      |    7 |       |
|  1 | SIMPLE      | t2    | ref  | idx           | idx  | 5       | test.t1.b |    1 |       |
|  1 | SIMPLE      | t3    | ref  | idx           | idx  | 5       | test.t1.d |    1 |       |
|  1 | SIMPLE      | t4    | ref  | idx           | idx  | 5       | test.t1.c |    1 |       |
+----+-------------+-------+------+---------------+------+---------+-----------+------+-------+
4 rows in set (0.00 sec)

mysql> select t1.a, t1.b, t1.c, t1.d, t2.e, t3.f, t4.g from t1,t2,t3,t4 where t2.b=t1.b and t3.d=t1.d and t4.c=t1.c;
+------+------+------+------+------+------+------+
| a    | b    | c    | d    | e    | f    | g    |
+------+------+------+------+------+------+------+
|    3 |   30 |  300 | 3000 | bbb  | ddd  | ccc  |
+------+------+------+------+------+------+------+
1 row in set (0.01 sec)

mysql> set join_cache_level=6;
Query OK, 0 rows affected (0.00 sec)

mysql> explain select t1.a, t1.b, t1.c, t1.d, t2.e, t3.f, t4.g from t1,t2,t3,t4 where t2.b=t1.b and t3.d=t1.d and t4.c=t1.c;
+----+-------------+-------+------+---------------+------+---------+-----------+------+-------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref       | rows | Extra             |
+----+-------------+-------+------+---------------+------+---------+-----------+------+-------------------+
|  1 | SIMPLE      | t1    | ALL  | NULL          | NULL | NULL    | NULL      |    7 |                   |
|  1 | SIMPLE      | t2    | ref  | idx           | idx  | 5       | test.t1.b |    1 | Using join buffer |
|  1 | SIMPLE      | t3    | ref  | idx           | idx  | 5       | test.t1.d |    1 | Using join buffer |
|  1 | SIMPLE      | t4    | ref  | idx           | idx  | 5       | test.t1.c |    1 | Using join buffer |
+----+-------------+-------+------+---------------+------+---------+-----------+------+-------------------+
4 rows in set (0.00 sec)

mysql> select t1.a, t1.b, t1.c, t1.d, t2.e, t3.f, t4.g from t1,t2,t3,t4 where t2.b=t1.b and t3.d=t1.d and t4.c=t1.c;
Empty set (0.01 sec)

If join_cache_level=5|7|8 the query returns correct results.
[1 Apr 2009 20:02] Igor Babaev
This problem originally was reported by Gene Pang from Google. The query he submitted required some modification of the BKA code. Though the modification is quite acceptable it's not in the development tree yet.
[2 Apr 2009 5:12] Sveta Smirnova
Thank you for the report.

In all cases I get

1       SIMPLE  NULL    NULL    NULL    NULL    NULL    NULL    NULL    Impossible WHERE noticed after reading const tables

and no results.

Which tree and revision do you use? Does t1 really contains no rows?
[2 Apr 2009 5:54] Sveta Smirnova
With InnoDB I get different results, but same in all cases and not like in the initial description:

explain select t1.a, t1.b, t1.c, t1.d, t2.e, t3.f, t4.g from t1,t2,t3,t4 where
t2.b=t1.b and t3.d=t1.d and t4.c=t1.c;
id      select_type     table   type    possible_keys   key     key_len ref     rows    Extra
1       SIMPLE  t1      ALL     NULL    NULL    NULL    NULL    1
1       SIMPLE  t3      ref     idx     idx     5       test.t1.d       1
1       SIMPLE  t4      ref     idx     idx     5       test.t1.c       1
1       SIMPLE  t2      ref     idx     idx     5       test.t1.b       1
select t1.a, t1.b, t1.c, t1.d, t2.e, t3.f, t4.g from t1,t2,t3,t4 where t2.b=t1.b
and t3.d=t1.d and t4.c=t1.c;
a       b       c       d       e       f       g
[2 Apr 2009 6:16] Igor Babaev
Correction:
The database is to be populated with the following commands:

insert into t2 values
  (30, 'bbb'), (10, 'b'), (70, 'bbbbbbb'), (60, 'bbbbbb'),
  (31, 'bbb'), (11, 'b'), (71, 'bbbbbbb'), (61, 'bbbbbb'),
  (32, 'bbb'), (12, 'b'), (72, 'bbbbbbb'), (62, 'bbbbbb');
insert into t3 values
  (4000, 'dddd'), (3000, 'ddd'), (1000, 'd'), (8000, 'dddddddd'),
  (4001, 'dddd'), (3001, 'ddd'), (1001, 'd'), (8001, 'dddddddd'),
  (4002, 'dddd'), (3002, 'ddd'), (1002, 'd'), (8002, 'dddddddd');
insert into t4 values
  (200, 'cc'), (600, 'cccccc'), (300, 'ccc'), (500, 'ccccc'),
  (201, 'cc'), (601, 'cccccc'), (301, 'ccc'), (501, 'ccccc'),
  (202, 'cc'), (602, 'cccccc'), (302, 'ccc'), (502, 'ccccc');
[2 Apr 2009 6:34] Igor Babaev
Correction2:
The tables t1,t2,t3,t4 is to be populated with the following commands:

insert into t1 values
  (5, 50, 500, 5000), (3, 30, 300, 3000), (9, 90, 900, 9000),
  (2, 20, 200, 2000), (4, 40, 400, 4000), (8, 80, 800, 800), (7, 70, 700, 7000);
insert into t2 values
  (30, 'bbb'), (10, 'b'), (70, 'bbbbbbb'), (60, 'bbbbbb'),
  (31, 'bbb'), (11, 'b'), (71, 'bbbbbbb'), (61, 'bbbbbb'),
  (32, 'bbb'), (12, 'b'), (72, 'bbbbbbb'), (62, 'bbbbbb');
insert into t3 values
  (4000, 'dddd'), (3000, 'ddd'), (1000, 'd'), (8000, 'dddddddd'),
  (4001, 'dddd'), (3001, 'ddd'), (1001, 'd'), (8001, 'dddddddd'),
  (4002, 'dddd'), (3002, 'ddd'), (1002, 'd'), (8002, 'dddddddd');
insert into t4 values
  (200, 'cc'), (600, 'cccccc'), (300, 'ccc'), (500, 'ccccc'),
  (201, 'cc'), (601, 'cccccc'), (301, 'ccc'), (501, 'ccccc'),
  (202, 'cc'), (602, 'cccccc'), (302, 'ccc'), (502, 'ccccc');
[2 Apr 2009 6:39] Sveta Smirnova
Thank you for the feedback.

Verified as described.
[4 Apr 2009 5:39] 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/71382

2734 Igor Babaev	2009-04-03
      Fixed bug #44019.
      This bug happened when incremental (linked) join buffers were
      employed to join several tables. 
      If some fields stored in one of such incremental join buffers
      are used to build keys to access tables that follow the next
      joined table, then offsets of these fields are saved at the 
      very end of the records stored in the join buffer.
      These offsets allow us to read only those record fields that
      are needed for building key values.
      Each field whose offset is saved gets its own unique number
      that determines the position of the offset for the field in
      the sequence of field offsets stored for a record.
      In a general case the order of the offsets in the sequence
      does not comply with the order of the corresponding fields.
      This fact was ignored by the code of the function
      JOIN_CACHE:: write_record_data. 
         
      modified:
        mysql-test/r/join_cache.result
        mysql-test/t/join_cache.test
        sql/sql_join_cache.cc
[20 Apr 2009 15:47] Bugs System
Pushed into 6.0.11-alpha (revid:sergefp@mysql.com-20090417211236-fy28y9o1w8p4ic9m) (version source revid:igor@mysql.com-20090404054052-zzlv2ln1dpkjdn3s) (merge vers: 6.0.11-alpha) (pib:6)
[23 Apr 2009 1:33] Paul Dubois
Noted in 6.0.11 changelog.

In some cases, when the Batched Key Access algorithm is used with
join_cache_level equal to 6, multi-join queries could return
incorrect results.
[16 Aug 2010 6:38] Bugs System
Pushed into mysql-next-mr (revid:alik@sun.com-20100816062819-bluwgdq8q4xysmlg) (version source revid:alik@sun.com-20100816062612-enatdwnv809iw3s9) (pib:20)
[13 Nov 2010 16:07] 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)
[20 Nov 2010 23:21] Paul Dubois
Noted in 5.6.1 changelog.
[23 Nov 2010 2:11] Paul Dubois
Correction: No 5.6.1 changelog entry. Bug does not appear in any released 5.6.x version.