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, 101 insertions, 25 deletions

diff --git a/sql/sql_insert.cc b/sql/sql_insert.cc
index 27342287fcd..ed5172e6974 100644
--- a/sql/sql_insert.cc
+++ b/sql/sql_insert.cc
@@ -106,12 +106,15 @@ static int check_insert_fields(THD *thd, TABLE_LIST *table_list,
   }
   else
   {						// Part field list
-    Name_resolution_context *context= &thd->lex->select_lex.context;
-    TABLE_LIST *save_next= table_list->next_local,
-               *save_context= context->table_list;
-    bool save_resolve_in_select_list=
-      thd->lex->select_lex.context.resolve_in_select_list;
+    SELECT_LEX *select_lex= &thd->lex->select_lex;
+    Name_resolution_context *context= &select_lex->context;
+    TABLE_LIST *save_next_local;
+    TABLE_LIST *save_table_list;
+    TABLE_LIST *save_first_name_resolution_table;
+    TABLE_LIST *save_next_name_resolution_table;
+    bool        save_resolve_in_select_list;
     int res;
+
     if (fields.elements != values.elements)
     {
       my_error(ER_WRONG_VALUE_COUNT_ON_ROW, MYF(0), 1L);
@@ -119,17 +122,39 @@ static int check_insert_fields(THD *thd, TABLE_LIST *table_list,
     }
 
     thd->dupp_field=0;
-    thd->lex->select_lex.no_wrap_view_item= TRUE;
-    /* fields only from first table */
+    select_lex->no_wrap_view_item= TRUE;
+
+    /* Save the state of the current name resolution context. */
+    save_table_list=                  context->table_list;
+    save_first_name_resolution_table= context->first_name_resolution_table;
+    save_next_name_resolution_table=  (context->first_name_resolution_table) ?
+                                      context->first_name_resolution_table->
+                                               next_name_resolution_table :
+                                      NULL;
+    save_resolve_in_select_list=      context->resolve_in_select_list;
+    save_next_local=                  table_list->next_local;
+
+    /*
+      Perform name resolution only in the first table - 'table_list',
+      which is the table that is inserted into.
+    */
     table_list->next_local= 0;
     context->resolve_in_table_list_only(table_list);
     res= setup_fields(thd, 0, fields, 1, 0, 0);
-    table_list->next_local= save_next;
+
+    /* Restore the current context. */
+    table_list->next_local=                save_next_local;
+    context->table_list=                   save_table_list;
+    context->first_name_resolution_table=  save_first_name_resolution_table;
+    if (context->first_name_resolution_table)
+      context->first_name_resolution_table->
+               next_name_resolution_table= save_next_name_resolution_table;
+    context->resolve_in_select_list=       save_resolve_in_select_list;
     thd->lex->select_lex.no_wrap_view_item= FALSE;
-    context->table_list= save_context;
-    context->resolve_in_select_list= save_resolve_in_select_list;
+
     if (res)
       return -1;
+
     if (table_list->effective_algorithm == VIEW_ALGORITHM_MERGE)
     {
       /* it is join view => we need to find table for update */
@@ -254,9 +279,13 @@ bool mysql_insert(THD *thd,TABLE_LIST *table_list,
   ulonglong id;
   COPY_INFO info;
   TABLE *table= 0;
-  TABLE_LIST *next_local;
+  TABLE_LIST *save_table_list;
+  TABLE_LIST *save_next_local;
+  TABLE_LIST *save_first_name_resolution_table;
+  TABLE_LIST *save_next_name_resolution_table;
   List_iterator_fast<List_item> its(values_list);
   List_item *values;
+  Name_resolution_context *context;
 #ifndef EMBEDDED_LIBRARY
   char *query= thd->query;
 #endif
@@ -335,9 +364,23 @@ bool mysql_insert(THD *thd,TABLE_LIST *table_list,
   /* mysql_prepare_insert set table_list->table if it was not set */
   table= table_list->table;
 
-  next_local= table_list->next_local;
+  context= &thd->lex->select_lex.context;
+  /* Save the state of the current name resolution context. */
+  save_table_list=                  context->table_list;
+  save_first_name_resolution_table= context->first_name_resolution_table;
+  save_next_name_resolution_table=  (context->first_name_resolution_table) ?
+                                    context->first_name_resolution_table->
+                                             next_name_resolution_table :
+                                    NULL;
+  save_next_local=                  table_list->next_local;
+
+  /*
+    Perform name resolution only in the first table - 'table_list',
+    which is the table that is inserted into.
+  */
   table_list->next_local= 0;
-  thd->lex->select_lex.context.resolve_in_table_list_only(table_list);
+  context->resolve_in_table_list_only(table_list);
+
   value_count= values->elements;
   while ((values= its++))
   {
@@ -351,7 +394,14 @@ bool mysql_insert(THD *thd,TABLE_LIST *table_list,
       goto abort;
   }
   its.rewind ();
-  table_list->next_local= next_local;
+ 
+  /* Restore the current context. */
+  table_list->next_local= save_next_local;
+  context->first_name_resolution_table= save_first_name_resolution_table;
+  if (context->first_name_resolution_table)
+    context->first_name_resolution_table->
+             next_name_resolution_table= save_next_name_resolution_table;
+
   /*
     Fill in the given fields and dump it to the table file
   */
@@ -707,6 +757,7 @@ static bool mysql_prepare_insert_check_table(THD *thd, TABLE_LIST *table_list,
   DBUG_ENTER("mysql_prepare_insert_check_table");
 
   if (setup_tables(thd, &thd->lex->select_lex.context,
+                   &thd->lex->select_lex.top_join_list,
                    table_list, where, &thd->lex->select_lex.leaf_tables,
 		   select_insert))
     DBUG_RETURN(TRUE);
@@ -761,10 +812,13 @@ bool mysql_prepare_insert(THD *thd, TABLE_LIST *table_list,
                           COND **where, bool select_insert)
 {
   SELECT_LEX *select_lex= &thd->lex->select_lex;
+  Name_resolution_context *context= &select_lex->context;
   TABLE_LIST *save_table_list;
   TABLE_LIST *save_next_local;
+  TABLE_LIST *save_first_name_resolution_table;
+  TABLE_LIST *save_next_name_resolution_table;
+  bool        save_resolve_in_select_list;
   bool insert_into_view= (table_list->view != 0);
-  bool save_resolve_in_select_list;
   bool res= 0;
   DBUG_ENTER("mysql_prepare_insert");
   DBUG_PRINT("enter", ("table_list 0x%lx, table 0x%lx, view %d",
@@ -802,35 +856,57 @@ bool mysql_prepare_insert(THD *thd, TABLE_LIST *table_list,
                                        select_insert))
     DBUG_RETURN(TRUE);
 
-  save_table_list= select_lex->context.table_list;
-  save_resolve_in_select_list= select_lex->context.resolve_in_select_list;
-  save_next_local= table_list->next_local;
+  /* Save the state of the current name resolution context. */
+  save_table_list=                  context->table_list;
+  /* Here first_name_resolution_table points to the first select table. */
+  save_first_name_resolution_table= context->first_name_resolution_table;
+  save_next_name_resolution_table=  (context->first_name_resolution_table) ?
+                                    context->first_name_resolution_table->
+                                             next_name_resolution_table :
+                                    NULL;
+  save_resolve_in_select_list=      context->resolve_in_select_list;
+  save_next_local=                  table_list->next_local;
 
+  /*
+    Perform name resolution only in the first table - 'table_list',
+    which is the table that is inserted into.
+  */
   table_list->next_local= 0;
-  select_lex->context.resolve_in_table_list_only(table_list);
-  if ((values && check_insert_fields(thd, table_list, fields, *values,
+  context->resolve_in_table_list_only(table_list);
+
+  /* Prepare the fields in the statement. */
+  if ((values && check_insert_fields(thd, context->table_list, fields, *values,
                                      !insert_into_view)) ||
       (values && setup_fields(thd, 0, *values, 0, 0, 0)))
     res= TRUE;
   else if (duplic == DUP_UPDATE)
   {
     select_lex->no_wrap_view_item= TRUE;
-    res= check_update_fields(thd, table_list, update_fields);
+    res= check_update_fields(thd, context->table_list, update_fields);
     select_lex->no_wrap_view_item= FALSE;
     if (select_lex->group_list.elements == 0)
     {
       /*
         When we are not using GROUP BY we can refer to other tables in the
-        ON DUPLICATE KEY part
+        ON DUPLICATE KEY part.
       */       
-      table_list->next_local= save_next_local;
+      context->table_list->next_local=       save_next_local;
+      context->first_name_resolution_table->
+               next_name_resolution_table=   save_next_local;
     }
     if (!res)
       res= setup_fields(thd, 0, update_values, 1, 0, 0);
   }
+
+  /* Restore the current context. */
   table_list->next_local= save_next_local;
-  select_lex->context.table_list= save_table_list;
-  select_lex->context.resolve_in_select_list= save_resolve_in_select_list;
+  context->table_list= save_table_list;
+  context->first_name_resolution_table= save_first_name_resolution_table;
+  if (context->first_name_resolution_table)
+    context->first_name_resolution_table->
+             next_name_resolution_table= save_next_name_resolution_table;
+  context->resolve_in_select_list= save_resolve_in_select_list;
+
   if (res)
     DBUG_RETURN(res);