[MDEV-4840] Wrong result (missing rows) on LEFT JOIN with InnoDB tables Created: 2013-08-04  Updated: 2013-08-22  Resolved: 2013-08-22

Status: Closed
Project: MariaDB Server
Component/s: None
Affects Version/s: 10.0.3, 5.5.32, 5.1.67, 5.2.14, 5.3.12
Fix Version/s: 10.0.5, 5.5.33

Type: Bug Priority: Major
Reporter: Elena Stepanova Assignee: Sergei Petrunia
Resolution: Fixed Votes: 0
Labels: None

Issue Links:
Relates

 Description   

With the test case below, the first query produces 3 rows, which I believe to be the correct result:

SELECT * FROM iso_code LEFT JOIN ( city LEFT JOIN country ON city.country_code  = country.code ) ON iso_code.alpha3 = country.code ;
 
alpha3	country_code	name	code	name
 
USA	USA	Austin	USA	United States
 
USA	USA	Boston	USA	United States
 
CAN	NULL	NULL	NULL	NULL

But the second query, which only differs from the previous one by the select list, produces two rows:

SELECT iso_code.alpha3 FROM iso_code LEFT JOIN ( city LEFT JOIN country ON city.country_code  = country.code ) ON iso_code.alpha3 = country.code ;
 
alpha3
 
USA
 
CAN

Reproducible on MariaDB 5.1 from the beginning of time (tried 5.1.42), 5.2, 5.3, 5.5, 10.0.
Not reproducible on MySQL 5.1, 5.5, 5.6.

--source include/have_innodb.inc
 
 
 
CREATE TABLE iso_code (alpha3 VARCHAR(3)) ENGINE=InnoDB;
 
INSERT INTO iso_code VALUES ('USA'),('CAN');
 
 
 
CREATE TABLE city ( country_code VARCHAR(3), name VARCHAR(64)) ENGINE=InnoDB;
 
INSERT INTO city VALUES ('USA','Austin'),('USA','Boston');
 
 
 
CREATE TABLE country ( code VARCHAR(3),  name VARCHAR(64),  PRIMARY KEY (code),  UNIQUE KEY (name)) ENGINE=InnoDB;
 
INSERT INTO country VALUES ('CAN','Canada'),('USA','United States');
 
 
 
SELECT * FROM iso_code LEFT JOIN ( city LEFT JOIN country ON city.country_code  = country.code ) ON iso_code.alpha3 = country.code ;
 
SELECT iso_code.alpha3 FROM iso_code LEFT JOIN ( city LEFT JOIN country ON city.country_code  = country.code ) ON iso_code.alpha3 = country.code ;
 
 
 
 
 
DROP TABLE iso_code, city, country;

EXPLAIN:

EXPLAIN EXTENDED
 
SELECT iso_code.alpha3 FROM iso_code LEFT JOIN ( city LEFT JOIN country ON city.country_code  = country.code ) ON iso_code.alpha3 = country.code ;
 
id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 
1	SIMPLE	iso_code	ALL	NULL	NULL	NULL	NULL	2	100.00	
Warnings:
 
Note	1003	select `test`.`iso_code`.`alpha3` AS `alpha3` from `test`.`iso_code` where 1



 Comments   
Comment by Oleksandr Byelkin [ 2013-08-05 ]

The problem is in removing LEFT JOIN...

Comment by Igor Babaev [ 2013-08-05 ]

I investigated the bug.
This bug is the result of an invalid table elimination: tables 'city' and 'country' are erroneously eliminated by the table elimination code.
Assigned the bug to Sergey Petrunia.

Comment by Sergei Petrunia [ 2013-08-15 ]

Table elimination causes "city LEFT JOIN country ON ...) to be eliminated:
MariaDB [j33]> explain SELECT iso_code.alpha3 FROM iso_code LEFT JOIN ( city LEFT JOIN country ON city.country_code = country.code ) ON iso_code.alpha3 = country.code;
------------------------------------------------------------------+

id select_type table type possible_keys key key_len ref rows Extra

------------------------------------------------------------------+

1 SIMPLE iso_code ALL NULL NULL NULL NULL 2  

------------------------------------------------------------------+

Comment by Sergei Petrunia [ 2013-08-15 ]

... and it is wrong to eliminate that join nest. Lets see what data it has:

select * from city LEFT JOIN country ON city.country_code = country.code;
-------------------------------------+

country_code name code name

-------------------------------------+

USA Austin USA United States
USA Boston USA United States

-------------------------------------+

we execute

select ... from iso_code left join (...) on iso_code.alpha3 = country.code

Apparently, the join nest may produce multiple records with the same
Country.code. Which means, it cannot be eliminated.

Comment by Sergei Petrunia [ 2013-08-15 ]

If one runs EXPLAIN EXTENDED SELECT * ..., they can see:

... from `j33`.`iso_code` left join (`j33`.`city` join `j33`.`country`) on ...

That is , "city LEFT JOIN country" is converted into an inner join. This is not a problem per se.

Comment by Sergei Petrunia [ 2013-08-15 ]

Removing outer->inner join conversion from the consideration:

MariaDB [j33]> SELECT iso_code.alpha3 FROM iso_code LEFT JOIN ( city JOIN country ON city.country_code = country.code ) ON iso_code.alpha3 = country.code;
--------

alpha3

--------

USA
CAN

--------
2 rows in set (0.00 sec)

MariaDB [j33]> set optimizer_switch='table_elimination=off';
Query OK, 0 rows affected (0.00 sec)

MariaDB [j33]> SELECT iso_code.alpha3 FROM iso_code LEFT JOIN ( city JOIN country ON city.country_code = country.code ) ON iso_code.alpha3 = country.code;
--------

alpha3

--------

USA
USA
CAN

--------
3 rows in set (0.01 sec)

Comment by Sergei Petrunia [ 2013-08-15 ]

(gdb) step
check_func_dependency (join=0xa16edf8, dep_tables=6, it=0x991e5800, oj_tbl=0x0, cond=0xa16f1c8) at /home/psergey/dev2/5.5/sql/opt_table_elimination.cc:801

    1. dep_tables = 6 = 4+ 2 = {city, country}

(gdb) p dbug_print_item(cond)
$54 = 0x8dab820 "(multiple equal(`j33`.`iso_code`.`alpha3`, `j33`.`country`.`code`, `j33`.`city`.`country_code`))"

iso_code.alpha3 = country.code = city.country_code

country.code is a PK.
city.country_code is not a PK.

(gdb) fini
Run till exit from #0 check_func_dependency (join=0xa16edf8, dep_tables=6, it=0x991e5800, oj_tbl=0x0, cond=0xa16f1c8) at /home/psergey/dev2/5.5/sql/opt_table_elimination.cc:849
0x08386a3c in eliminate_tables_for_list (join=0xa16edf8, join_list=0xa152c90, list_tables=6, on_expr=0xa16f1c8, tables_used_elsewhere=1) at /home/psergey/dev2/5.5/sql/opt_table_elimination.cc:756
Value returned is $60 = true

    1. ^ This means the nest is eliminated.
Comment by Sergei Petrunia [ 2013-08-15 ]

It seems, the problem is here:
(gdb) wher
#0 Dep_module::touch (this=0xa1704c0) at /home/psergey/dev2/5.5/sql/opt_table_elimination.cc:358
#1 0x083850e2 in Dep_analysis_context::run_wave (this=0x991e5654, new_bound_modules=0x991e5780) at /home/psergey/dev2/5.5/sql/opt_table_elimination.cc:914
#2 0x0838673e in check_func_dependency (join=0xa16edf8, dep_tables=6, it=0x991e5800, oj_tbl=0x0, cond=0xa16f1c8) at /home/psergey/dev2/5.5/sql/opt_table_elimination.cc:848
#3 0x08386a3c in eliminate_tables_for_list (join=0xa16edf8, join_list=0xa152c90, list_tables=6, on_expr=0xa16f1c8, tables_used_elsewhere=1) at /home/psergey/dev2/5.5/sql/opt_table_elimination.cc:756
#4 0x08386857 in eliminate_tables_for_list (join=0xa16edf8, join_list=0xa13cd7c, list_tables=7, on_expr=0x0, tables_used_elsewhere=1) at /home/psergey/dev2/5.5/sql/opt_table_elimination.cc:716
#5 0x08386ddc in eliminate_tables (join=0xa16edf8) at /home/psergey/dev2/5.5/sql/opt_table_elimination.cc:655
#6 0x0828f25c in make_join_statistics (join=0xa16edf8, tables_list=..., conds=0x0, keyuse_array=0xa16eff8) at /home/psergey/dev2/5.5/sql/sql_select.cc:3360
#7 0x08291f83 in JOIN::optimize (this=0xa16edf8) at /home/psergey/dev2/5.5/sql/sql_select.cc:1209

(gdb) p this
$134 = (Dep_module_goal *) 0xa1704c0

358 void touch()

{ unbound_args--; }

The code in Dep_module::touch() assumes that it is called from different sources.
In our case:

1. table "country" has two unique keys.
2. table "city" has no indexes at all.

#2 should prevent Dep_module_goal from ever being marked as bound. However, #1 causes dep_module_goa->touch() be called twice, and the optimizer incorrectly assumes Dep_module_goal is satisfied.

Comment by Sergei Petrunia [ 2013-08-22 ]

This patch fixes the testcase for this bug:

=== modified file 'sql/opt_table_elimination.cc'
— sql/opt_table_elimination.cc 2012-02-17 11:19:38 +0000
+++ sql/opt_table_elimination.cc 2013-08-21 18:02:45 +0000
@@ -892,8 +892,11 @@ bool Dep_analysis_context::run_wave(List
iter= module->init_unbound_values_iter(iter_buf);
while ((value= module->get_next_unbound_value(this, iter)))
{

  • value->make_bound();
  • new_bound_values.push_back(value);
    + if (!value->is_bound())
    + { + value->make_bound(); + new_bound_values.push_back(value); + }

    }
    }
    new_bound_modules->empty();

what I don't understand is why the testcase fails only with InnoDB. The problem that is fixed by this patch is orthogonal to the storage engine being used.

Comment by Sergei Petrunia [ 2013-08-22 ]

CREATE TABLE country ( code VARCHAR(3), name VARCHAR(64), PRIMARY KEY (code), UNIQUE KEY (name)) ENGINE=InnoDB;
...

Breakpoint 14, Dep_value_field::get_next_unbound_module (this=0x7fff9400af08, dac=0x7fffc87c5e00, iter=0x7fffc87c5d00 "`\311\002\224\377\177") at /home/psergey/dev2/5.5/sql/opt_table_elimination.cc:1742
(gdb) p field->field_name
$188 = 0x7fff9401ee59 "code"
(gdb) p *field->table_name
$189 = 0x7fff9400da90 "country"
(gdb) p key_dep->keyno
$190 = 1

That is, country.code is considered to be covered by key#1 in table `country`.
Key #1 is UNIQUE KEY(name). This is extended keys feature at work.

However, the constructor for this unique key assumes that the key as one key
part:

Breakpoint 13, Dep_module_key::Dep_module_key (this=0x7fff9402c960, table_arg=0x7fff9402c910, keyno_arg=1, n_parts_arg=1) at /home/psergey/dev2/5.5/sql/opt_table_elimination.cc:422

note above: keyno_arg=1, n_parts_arg=1

Somehow, extended-keys property is taken into account in one place but not in the other.

Comment by Sergei Petrunia [ 2013-08-22 ]

Dep_value_table *Dep_analysis_context::create_table_value(TABLE *table)

has this code

if (key->flags & HA_NOSAME)
{
Dep_module_key *key_dep;
if (!(key_dep= new Dep_module_key(tbl_dep, i, key->key_parts)))

As for key->key_parts:

(gdb) p *key
$200 = {key_length = 69, flags = 105, key_parts = 1, usable_key_parts = 2,
ext_key_parts = 2 ...

It seems, usable_key_parts should be used instead?

Comment by Sergei Petrunia [ 2013-08-22 ]

Handling extended keys in table elimination.

Table elimination uses primary/unique key definitions to know which set of
columns uniquely defines the table record.

Extending the binding column set makes things worse for table elimination.
Without extended keys, table elimination sees

UNIQUE KEY(col1),
PRIMARY KEY (pk_col)

and is able to infer that "col1=...." makes the table bound.

With extended keys, table elimination sees:

UNIQUE KEY(col1, pk_col)
PRIMARY KEY (pk_col)

and this doesn't allow to infer that "col1=..." makes the table bound.

Generated at Thu Feb 08 06:59:36 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.