Implementation of WL#2486 -

"Process NATURAL and USING joins according to SQL:2003".

* Some of the main problems fixed by the patch:
  - in "select *" queries the * expanded correctly according to
    ANSI for arbitrary natural/using joins
  - natural/using joins are correctly transformed into JOIN ... ON
    for any number/nesting of the joins.
  - column references are correctly resolved against natural joins
    of any nesting and combined with arbitrary other joins.

* This patch also contains a fix for name resolution of items
  inside the ON condition of JOIN ... ON - in this case items must
  be resolved only against the JOIN operands. To support such
  'local' name resolution, the patch introduces a stack of
  name resolution contexts used at parse time.

NOTICE:
- This patch is not complete in the sense that
  - there are 2 test cases that still do not pass -
    one in join.test, one in select.test. Both are marked
    with a comment "TODO: WL#2486".
  - it does not include a new test specific for the task


mysql-test/include/ps_query.inc:
  Adjusted according to standard NATURAL/USING join semantics.,
mysql-test/r/bdb.result:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/r/derived.result:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/r/errors.result:
  The column as a whole cannot be resolved, so different error message.
mysql-test/r/fulltext.result:
  Adjusted according to standard JOIN ... ON semantics =>
  the ON condition can refer only to the join operands.
mysql-test/r/fulltext_order_by.result:
  More detailed error message.
mysql-test/r/innodb.result:
  Adjusted according to standard NATURAL/USING join semantics.
  This test doesn't pass completetly yet!
mysql-test/r/insert_select.result:
  More detailed error message.
mysql-test/r/join.result:
  Adjusted according to standard NATURAL/USING join semantics.
  
  NOTICE: there is one test case that still fails, and it is
  commeted out and marked with WL#2486 in the test file.
mysql-test/r/join_crash.result:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/r/join_nested.result:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/r/join_outer.result:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/r/multi_update.result:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/r/null_key.result:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/r/order_by.result:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/r/ps_2myisam.result:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/r/ps_3innodb.result:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/r/ps_4heap.result:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/r/ps_5merge.result:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/r/ps_6bdb.result:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/r/ps_7ndb.result:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/r/select.result:
  Adjusted according to standard NATURAL/USING join semantics.
  
  NOTICE: there is one failing test case which is commented with
  WL#2486 in the test file.
mysql-test/r/subselect.result:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/r/type_ranges.result:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/r/union.result:
  More detailed error message.
mysql-test/t/bdb.test:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/t/errors.test:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/t/fulltext.test:
  Adjusted according to standard JOIN ... ON semantics =>
  the ON condition can refer only to the join operands.
mysql-test/t/fulltext_order_by.test:
  More detailed error message.
mysql-test/t/innodb.test:
  Adjusted according to standard NATURAL/USING join semantics.
  This test doesn't pass completetly yet!
mysql-test/t/insert_select.test:
  More detailed error message.
mysql-test/t/join.test:
  Adjusted according to standard NATURAL/USING join semantics.
  
  NOTICE: there is one test case that still fails, and it is
  commeted out and marked with WL#2486 in the test file.
mysql-test/t/join_crash.test:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/t/join_nested.test:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/t/join_outer.test:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/t/null_key.test:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/t/order_by.test:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/t/select.test:
  Adjusted according to standard NATURAL/USING join semantics.
  
  NOTICE: there is one test case that still fails, and it is
  commeted out and marked with WL#2486 in the test file.
mysql-test/t/subselect.test:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/t/type_ranges.test:
  Adjusted according to standard NATURAL/USING join semantics.
mysql-test/t/union.test:
  More detailed error message.
sql/item.cc:
  - extra parameter to find_field_in_tables
  - find_field_in_real_table renamed to find_field_in_table
  - fixed comments/typos
sql/item.h:
  - added [first | last]_name_resolution_table to class
    Name_resolution_context
  - commented old code
  - standardized formatting
sql/mysql_priv.h:
  - refactored the find_field_in_XXX procedures,
  - added a new procedure for natural join table references,
  - renamed the find_field_in_XXX procedures to clearer names
sql/sp.cc:
  - pass the top-most list of the FROM clause to setup_tables
  - extra parameter to find_field_in_tables
sql/sql_acl.cc:
  - renamed find_field_in_table => find_field_in_table_ref
  - extra parameter to find_field_in_table_ref
  - commented old code
sql/sql_base.cc:
  This file contains the core of the implementation of the processing
  of NATURAL/USING joins (WL#2486).
  - added many comments to old code
  - refactored the group of find_field_in_XXX procedures, and added a
    new procedure for natural joins. There is one find_field_in_XXX procedure
    per each type of table reference (stored table, merge view, or natural
    join); one meta-procedure that selects the correct one depeneding on the
    table reference; and one procedure that goes over a list of table
    referenes.
  - NATURAL/USING joins are processed through the procedures:
      mark_common_columns, store_natural_using_join_columns,
      store_top_level_join_columns, setup_natural_join_row_types.
    The entry point to processing NATURAL/USING joins is the
    procedure 'setup_natural_join_row_types'.
  - Replaced the specialized Field_iterator_XXX iterators with one
    generic iterator over the fields of a table reference.
  - Simplified 'insert_fields' and 'setup_conds' due to encapsulation of
    the processing of natural joins in a separate set of procedures.
sql/sql_class.h:
  - Commented old code.
sql/sql_delete.cc:
  - Pass the FROM clause to setup_tables.
sql/sql_help.cc:
  - pass the end name resolution table to find_field_in_tables
  - adjust the list of tables for name resolution
sql/sql_insert.cc:
  - Changed the code that saves and restores the current context to
    support the list of tables for name resolution -
    context->first_name_resolution_table, and
    table_list->next_name_resolution_table.
    Needed to support an ugly trick to resolve inserted columns only in
    the first table.
  - Added Name_resolution_context::[first | last]_name_resolution_table.
  - Commented old code
sql/sql_lex.cc:
  - set select_lex.parent_lex correctly
  - set correct state of the current name resolution context
sql/sql_lex.h:
  - Added a stack of name resolution contexts to support local
    contexts for JOIN ... ON conditions.
  - Commented old code.
sql/sql_load.cc:
  - Pass the FROM clause to setup_tables.
sql/sql_olap.cc:
  - Pass the FROM clause to setup_tables.
sql/sql_parse.cc:
  - correctly set SELECT_LEX::parent_lex
  - set the first table of the current name resoltion context
  - added support for NATURAL/USING joins
  - commented old code
sql/sql_select.cc:
  - Pass the FROM clause to setup_tables.
  - Pass the end table to find_field_in_tables
  - Improved comments
sql/sql_show.cc:
  - Set SELECT_LEX::parent_lex.
sql/sql_update.cc:
  - Pass the FROM clause to setup_tables.
sql/sql_yacc.yy:
  - Added support for a stack of name resolution contexts needed to
    implement name resolution for JOIN ... ON. A context is pushed
    for each new JOIN ... ON, and popped afterwards.
  - Added support for NATURAL/USING joins.
sql/table.cc:
  - Added new class Natural_join_column to hide the heterogeneous
    representation of column references for stored tables and for
    views.
  - Added a new list TABLE_LIST::next_name_resolution_table to
    support name resolution with NATURAL/USING joins. Also added
    other members to TABLE_LIST to support NATURAL/USING joins.
  - Added a generic iterator over the fields of table references
    of various types - class Field_iterator_table_ref
sql/table.h:
  - Added new class Natural_join_column to hide the heterogeneous
    representation of column references for stored tables and for
    views.
  - Added a new list TABLE_LIST::next_name_resolution_table to
    support name resolution with NATURAL/USING joins. Also added
    other members to TABLE_LIST to support NATURAL/USING joins.
  - Added a generic iterator over the fields of table references
    of various types - class Field_iterator_table_ref
tests/mysql_client_test.c:
  Adjusted according to standard NATURAL JOIN syntax.

1 files changed, 142 insertions, 162 deletions

diff --git a/mysql-test/r/select.result b/mysql-test/r/select.result
index a0f6bb7084f..d3409bf8d39 100644
--- a/mysql-test/r/select.result
+++ b/mysql-test/r/select.result
@@ -1350,45 +1350,42 @@ fld1	fld1
 250504	250505
 250505	250505
 insert into t2 (fld1, companynr) values (999999,99);
-select t2.companynr,companyname from t2 left join t4 using (companynr) where t4.companynr is null;
+select companynr,companyname from t2 left join t4 using (companynr) where companynr is null;
 companynr	companyname
-99	NULL
-select count(*) from t2 left join t4 using (companynr) where t4.companynr is not null;
+select count(*) from t2 left join t4 using (companynr) where companynr is not null;
 count(*)
-1199
-explain select t2.companynr,companyname from t2 left join t4 using (companynr) where t4.companynr is null;
+1200
+explain select companynr,companyname from t2 left join t4 using (companynr) where companynr is null;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	1200	
-1	SIMPLE	t4	eq_ref	PRIMARY	PRIMARY	1	test.t2.companynr	1	Using where; Not exists
-explain select t2.companynr,companyname from t4 left join t2 using (companynr) where t2.companynr is null;
+1	SIMPLE	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE
+explain select companynr,companyname from t4 left join t2 using (companynr) where companynr is null;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	1200	Using where; Not exists
+1	SIMPLE	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE
 delete from t2 where fld1=999999;
-explain select t2.companynr,companyname from t4 left join t2 using (companynr) where t2.companynr > 0;
+explain select companynr,companyname from t4 left join t2 using (companynr) where companynr > 0;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	1199	Using where
-1	SIMPLE	t4	eq_ref	PRIMARY	PRIMARY	1	test.t2.companynr	1	
-explain select t2.companynr,companyname from t4 left join t2 using (companynr) where t2.companynr > 0 or t2.companynr < 0;
+1	SIMPLE	t4	ALL	PRIMARY	NULL	NULL	NULL	12	Using where
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	1199	
+explain select companynr,companyname from t4 left join t2 using (companynr) where companynr > 0 or companynr < 0;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	1199	Using where
-1	SIMPLE	t4	eq_ref	PRIMARY	PRIMARY	1	test.t2.companynr	1	
-explain select t2.companynr,companyname from t4 left join t2 using (companynr) where t2.companynr > 0 and t4.companynr > 0;
+1	SIMPLE	t4	ALL	PRIMARY	NULL	NULL	NULL	12	Using where
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	1199	
+explain select companynr,companyname from t4 left join t2 using (companynr) where companynr > 0 and companynr > 0;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	1199	Using where
-1	SIMPLE	t4	eq_ref	PRIMARY	PRIMARY	1	test.t2.companynr	1	
-explain select t2.companynr,companyname from t4 left join t2 using (companynr) where t2.companynr > 0 or t2.companynr is null;
+1	SIMPLE	t4	ALL	PRIMARY	NULL	NULL	NULL	12	Using where
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	1199	
+explain select companynr,companyname from t4 left join t2 using (companynr) where companynr > 0 or companynr is null;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	1199	Using where
-explain select t2.companynr,companyname from t4 left join t2 using (companynr) where t2.companynr > 0 or t2.companynr < 0 or t4.companynr > 0;
+1	SIMPLE	t4	ALL	PRIMARY	NULL	NULL	NULL	12	Using where
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	1199	
+explain select companynr,companyname from t4 left join t2 using (companynr) where companynr > 0 or companynr < 0 or companynr > 0;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t4	ALL	PRIMARY	NULL	NULL	NULL	12	
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	1199	Using where
-explain select t2.companynr,companyname from t4 left join t2 using (companynr) where ifnull(t2.companynr,1)>0;
+1	SIMPLE	t4	ALL	PRIMARY	NULL	NULL	NULL	12	Using where
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	1199	
+explain select companynr,companyname from t4 left join t2 using (companynr) where ifnull(companynr,1)>0;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	1199	Using where
+1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	Using where
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	1199	
 select distinct t2.companynr,t4.companynr from t2,t4 where t2.companynr=t4.companynr+1;
 companynr	companynr
 37	36
@@ -2115,159 +2112,142 @@ insert into t1 values ();
 insert into t1 values ();
 insert into t1 values ();
 select * from (t1 as t2 left join t1 as t3 using (a)), t1;
-a	a	a
-1	1	1
-2	2	1
-3	3	1
-1	1	2
-2	2	2
-3	3	2
-1	1	3
-2	2	3
-3	3	3
+a	a
+1	1
+2	1
+3	1
+1	2
+2	2
+3	2
+1	3
+2	3
+3	3
 select * from t1, (t1 as t2 left join t1 as t3 using (a));
-a	a	a
-1	1	1
-2	1	1
-3	1	1
-1	2	2
-2	2	2
-3	2	2
-1	3	3
-2	3	3
-3	3	3
+a	a
+1	1
+2	1
+3	1
+1	2
+2	2
+3	2
+1	3
+2	3
+3	3
 select * from (t1 as t2 left join t1 as t3 using (a)) straight_join t1;
-a	a	a
-1	1	1
-2	2	1
-3	3	1
-1	1	2
-2	2	2
-3	3	2
-1	1	3
-2	2	3
-3	3	3
+a	a
+1	1
+2	1
+3	1
+1	2
+2	2
+3	2
+1	3
+2	3
+3	3
 select * from t1 straight_join (t1 as t2 left join t1 as t3 using (a));
-a	a	a
-1	1	1
-2	1	1
-3	1	1
-1	2	2
-2	2	2
-3	2	2
-1	3	3
-2	3	3
-3	3	3
+a	a
+1	1
+2	1
+3	1
+1	2
+2	2
+3	2
+1	3
+2	3
+3	3
 select * from (t1 as t2 left join t1 as t3 using (a)) inner join t1 on t1.a>1;
-a	a	a
-1	1	2
-2	2	2
-3	3	2
-1	1	3
-2	2	3
-3	3	3
+a	a
+1	2
+2	2
+3	2
+1	3
+2	3
+3	3
 select * from t1 inner join (t1 as t2 left join t1 as t3 using (a)) on t1.a>1;
-a	a	a
-2	1	1
-3	1	1
-2	2	2
-3	2	2
-2	3	3
-3	3	3
+a	a
+2	1
+3	1
+2	2
+3	2
+2	3
+3	3
 select * from (t1 as t2 left join t1 as t3 using (a)) inner join t1 using ( a );
-a	a	a
-1	1	1
-2	2	2
-3	3	3
+a
+1
+2
+3
 select * from t1 inner join (t1 as t2 left join t1 as t3 using (a)) using ( a );
-a	a	a
-1	1	1
-2	2	2
-3	3	3
+a
+1
+2
+3
 select * from (t1 as t2 left join t1 as t3 using (a)) left outer join t1 on t1.a>1;
-a	a	a
-1	1	2
-1	1	3
-2	2	2
-2	2	3
-3	3	2
-3	3	3
+a	a
+1	2
+1	3
+2	2
+2	3
+3	2
+3	3
 select * from t1 left outer join (t1 as t2 left join t1 as t3 using (a)) on t1.a>1;
-a	a	a
-1	NULL	NULL
-2	1	1
-2	2	2
-2	3	3
-3	1	1
-3	2	2
-3	3	3
+a	a
+1	NULL
+2	1
+2	2
+2	3
+3	1
+3	2
+3	3
 select * from (t1 as t2 left join t1 as t3 using (a)) left join t1 using ( a );
-a	a	a
-1	1	1
-2	2	2
-3	3	3
+a
+1
+2
+3
 select * from t1 left join (t1 as t2 left join t1 as t3 using (a)) using ( a );
-a	a	a
-1	1	1
-2	2	2
-3	3	3
+a
+1
+2
+3
 select * from (t1 as t2 left join t1 as t3 using (a)) natural left join t1;
-a	a	a
-1	1	1
-2	2	2
-3	3	3
+a
+1
+2
+3
 select * from t1 natural left join (t1 as t2 left join t1 as t3 using (a));
-a	a	a
-1	1	1
-2	2	2
-3	3	3
-select * from (t1 as t2 left join t1 as t3 using (a)) right join t1 on t1.a>1;
-a	a	a
-NULL	NULL	1
-1	1	2
-2	2	2
-3	3	2
-1	1	3
-2	2	3
-3	3	3
-select * from t1 right join (t1 as t2 left join t1 as t3 using (a)) on t1.a>1;
-a	a	a
-2	1	1
-3	1	1
-2	2	2
-3	2	2
-2	3	3
-3	3	3
+a
+1
+2
+3
 select * from (t1 as t2 left join t1 as t3 using (a)) right outer join t1 using ( a );
-a	a	a
-1	1	1
-2	2	2
-3	3	3
+a
+1
+2
+3
 select * from t1 right outer join (t1 as t2 left join t1 as t3 using (a)) using ( a );
-a	a	a
-1	1	1
-2	2	2
-3	3	3
+a
+1
+2
+3
 select * from (t1 as t2 left join t1 as t3 using (a)) natural right join t1;
-a	a	a
-1	1	1
-2	2	2
-3	3	3
+a
+1
+2
+3
 select * from t1 natural right join (t1 as t2 left join t1 as t3 using (a));
-a	a	a
-1	1	1
-2	2	2
-3	3	3
+a
+1
+2
+3
 select * from t1 natural join (t1 as t2 left join t1 as t3 using (a));
-a	a
-1	1
-2	2
-3	3
+a
+1
+2
+3
 select * from (t1 as t2 left join t1 as t3 using (a)) natural join t1;
-a	a
-1	1
-2	2
-3	3
+a
+1
+2
+3
 drop table t1;
 CREATE TABLE t1 (  aa char(2),  id int(11) NOT NULL auto_increment,  t2_id int(11) NOT NULL default '0',  PRIMARY KEY  (id),  KEY replace_id (t2_id)) ENGINE=MyISAM;
 INSERT INTO t1 VALUES ("1",8264,2506),("2",8299,2517),("3",8301,2518),("4",8302,2519),("5",8303,2520),("6",8304,2521),("7",8305,2522);