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, 147 insertions, 59 deletions

diff --git a/sql/sql_parse.cc b/sql/sql_parse.cc
index f1950d36b23..7ecbc9dbb19 100644
--- a/sql/sql_parse.cc
+++ b/sql/sql_parse.cc
@@ -2141,6 +2141,8 @@ int prepare_schema_table(THD *thd, LEX *lex, Table_ident *table_ident,
     {
       TABLE_LIST **query_tables_last= lex->query_tables_last;
       sel= new SELECT_LEX();
+      /* 'parent_lex' is used in init_query() so it must be before it. */
+      sel->parent_lex= lex;
       sel->init_query();
       if (!sel->add_table_to_list(thd, table_ident, 0, 0, TL_READ, 
                                  (List<String> *) 0, (List<String> *) 0))
@@ -3244,19 +3246,26 @@ end_with_restore_list:
     if (!(res= open_and_lock_tables(thd, all_tables)))
     {
       /* Skip first table, which is the table we are inserting in */
-      select_lex->table_list.first= (byte*)first_table->next_local;
-
+      TABLE_LIST *second_table= first_table->next_local;
+      select_lex->table_list.first= (byte*) second_table;
+      select_lex->context.table_list= second_table;
+      select_lex->context.first_name_resolution_table= second_table;
       res= mysql_insert_select_prepare(thd);
-      lex->select_lex.context.table_list= first_table->next_local;
       if (!res && (result= new select_insert(first_table, first_table->table,
                                              &lex->field_list,
                                              &lex->update_list,
                                              &lex->value_list,
                                              lex->duplicates, lex->ignore)))
       {
-        /* Skip first table, which is the table we are inserting in */
+        /*
+          Skip first table, which is the table we are inserting in.
+          Below we set context.table_list again because the call above to
+          mysql_insert_select_prepare() calls resolve_in_table_list_only(),
+          which in turn resets context.table_list and
+          context.first_name_resolution_table.
+        */
         select_lex->context.table_list= first_table->next_local;
-
+        select_lex->context.first_name_resolution_table= first_table->next_local;
 	res= handle_select(thd, lex, result, OPTION_SETUP_TABLES_DONE);
         delete result;
       }
@@ -5204,9 +5213,9 @@ mysql_new_select(LEX *lex, bool move_down)
   if (!(select_lex= new (thd->mem_root) SELECT_LEX()))
     DBUG_RETURN(1);
   select_lex->select_number= ++thd->select_number;
+  select_lex->parent_lex= lex; /* Used in init_query. */
   select_lex->init_query();
   select_lex->init_select();
-  select_lex->parent_lex= lex;
   /*
     Don't evaluate this subquery during statement prepare even if
     it's a constant one. The flag is switched off in the end of
@@ -5264,6 +5273,7 @@ mysql_new_select(LEX *lex, bool move_down)
       fake->include_standalone(unit,
 			       (SELECT_LEX_NODE**)&unit->fake_select_lex);
       fake->select_number= INT_MAX;
+      fake->parent_lex= lex; /* Used in init_query. */
       fake->make_empty_select();
       fake->linkage= GLOBAL_OPTIONS_TYPE;
       fake->select_limit= 0;
@@ -5272,6 +5282,11 @@ mysql_new_select(LEX *lex, bool move_down)
       /* allow item list resolving in fake select for ORDER BY */
       fake->context.resolve_in_select_list= TRUE;
       fake->context.select_lex= fake;
+      /*
+        Remove the name resolution context of the fake select from the
+        context stack.
+       */
+      lex->pop_context();
     }
     select_lex->context.outer_context= outer_context;
   }
@@ -5959,6 +5974,7 @@ TABLE_LIST *st_select_lex::add_table_to_list(THD *thd,
                                              LEX_STRING *option)
 {
   register TABLE_LIST *ptr;
+  TABLE_LIST *previous_table_ref; /* The table preceding the current one. */
   char *alias_str;
   LEX *lex= thd->lex;
   DBUG_ENTER("add_table_to_list");
@@ -6054,8 +6070,29 @@ TABLE_LIST *st_select_lex::add_table_to_list(THD *thd,
       }
     }
   }
-  /* Link table in local list (list for current select) */
+  /* Store the table reference preceding the current one. */
+  if (table_list.elements > 0)
+  {
+    previous_table_ref= (TABLE_LIST*) table_list.next;
+    DBUG_ASSERT(previous_table_ref);
+  }
+  /*
+    Link the current table reference in a local list (list for current select).
+    Notice that as a side effect here we set the next_local field of the
+    previous table reference to 'ptr'. Here we also add one element to the
+    list 'table_list'.
+  */
   table_list.link_in_list((byte*) ptr, (byte**) &ptr->next_local);
+  /*
+    Set next_name_resolution_table of the previous table reference to point to
+    the current table reference. In effect the list
+    TABLE_LIST::next_name_resolution_table coincides with
+    TABLE_LIST::next_local. Later this may be changed in
+    store_top_level_join_columns() for NATURAL/USING joins.
+   */
+  if (table_list.elements > 1)
+    previous_table_ref->next_name_resolution_table= ptr;
+  ptr->next_name_resolution_table= NULL;
   /* Link table in global list (all used tables) */
   lex->add_to_query_tables(ptr);
   DBUG_RETURN(ptr);
@@ -6184,6 +6221,19 @@ TABLE_LIST *st_select_lex::nest_last_join(THD *thd)
     table->join_list= embedded_list;
     table->embedding= ptr;
     embedded_list->push_back(table);
+    if (table->natural_join)
+    {
+      ptr->is_natural_join= TRUE;
+      /*
+        If this is a JOIN ... USING, move the list of joined fields to the
+        table reference that describes the join.
+      */
+      if (table->join_using_fields)
+      {
+        ptr->join_using_fields= table->join_using_fields;
+        table->join_using_fields= NULL;
+      }
+    }
   }
   join_list->push_front(ptr);
   nested_join->used_tables= nested_join->not_null_tables= (table_map) 0;
@@ -6192,44 +6242,6 @@ TABLE_LIST *st_select_lex::nest_last_join(THD *thd)
 
 
 /*
-  Save names for a join with using clause
-
-  SYNOPSIS
-    save_names_for_using_list
-    tab1      left table in join
-    tab2      right table in join
-
-  DESCRIPTION
-    The function saves the full names of the tables in st_select_lex
-    to be able to build later an on expression to replace the using clause.
-
-  RETURN VALUE
-    None
-*/
-
-void st_select_lex::save_names_for_using_list(TABLE_LIST *tab1,
-                                              TABLE_LIST *tab2)
-{
-  while (tab1->nested_join)
-  {
-    tab1= tab1->nested_join->join_list.head();
-  }
-  db1= tab1->db;
-  table1= tab1->alias;
-  while (tab2->nested_join)
-  {
-    TABLE_LIST *next;
-    List_iterator_fast<TABLE_LIST> it(tab2->nested_join->join_list);
-    tab2= it++;
-    while ((next= it++))
-      tab2= next;
-  }
-  db2= tab2->db;
-  table2= tab2->alias;
-}
-
-
-/*
   Add a table to the current join list
 
   SYNOPSIS
@@ -6332,16 +6344,71 @@ void st_select_lex::set_lock_for_tables(thr_lock_type lock_type)
 }
 
 
-void add_join_on(TABLE_LIST *b,Item *expr)
+/*
+  Create a new name resolution context for a JOIN ... ON clause.
+
+  SYNOPSIS
+    make_join_on_context()
+    thd       pointer to current thread
+    left_op   lefto operand of the JOIN
+    right_op  rigth operand of the JOIN
+
+  DESCRIPTION
+    Create a new name resolution context for a JOIN ... ON clause,
+    and set the first and last leaves of the list of table references
+    to be used for name resolution.
+
+  RETURN
+    A new context if all is OK
+    NULL - if a memory allocation error occured
+*/
+
+Name_resolution_context *
+make_join_on_context(THD *thd, TABLE_LIST *left_op, TABLE_LIST *right_op)
+{
+  Name_resolution_context *on_context;
+  if (!(on_context= (Name_resolution_context*)
+        thd->calloc(sizeof(Name_resolution_context))))
+    return NULL;
+  on_context->init();
+  on_context->first_name_resolution_table=
+    left_op->first_leaf_for_name_resolution();
+  on_context->last_name_resolution_table=
+    right_op->last_leaf_for_name_resolution();
+  return on_context;
+}
+
+
+/*
+  Add an ON condition to the second operand of a JOIN ... ON.
+
+  SYNOPSIS
+    add_join_on
+    b     the second operand of a JOIN ... ON
+    expr  the condition to be added to the ON clause
+
+  DESCRIPTION
+    Add an ON condition to the right operand of a JOIN ... ON clause.
+
+  RETURN
+    FALSE  if there was some error
+    TRUE   if all is OK
+*/
+
+void add_join_on(TABLE_LIST *b, Item *expr)
 {
   if (expr)
   {
     if (!b->on_expr)
-      b->on_expr=expr;
+      b->on_expr= expr;
     else
     {
-      /* This only happens if you have both a right and left join */
-      b->on_expr=new Item_cond_and(b->on_expr,expr);
+      /*
+        If called from the parser, this happens if you have both a
+        right and left join. If called later, it happens if we add more
+        than one condition to the ON clause.
+      */
+      b->on_expr= new Item_cond_and(b->on_expr,expr);
     }
     b->on_expr->top_level_item();
   }
@@ -6349,28 +6416,49 @@ void add_join_on(TABLE_LIST *b,Item *expr)
 
 
 /*
-  Mark that we have a NATURAL JOIN between two tables
+  Mark that there is a NATURAL JOIN or JOIN ... USING between two
+  tables.
 
   SYNOPSIS
     add_join_natural()
-    a			Table to do normal join with
-    b			Do normal join with this table
-
+    a			Left join argument
+    b			Right join argument
+    using_fields        Field names from USING clause
+  
   IMPLEMENTATION
-    This function just marks that table b should be joined with a.
-    The function setup_cond() will create in b->on_expr a list
-    of equal condition between all fields of the same name.
-
+    This function marks that table b should be joined with a either via
+    a NATURAL JOIN or via JOIN ... USING. Both join types are special
+    cases of each other, so we treat them together. The function
+    setup_conds() creates a list of equal condition between all fields
+    of the same name for NATURAL JOIN or the fields in 'using_fields'
+    for JOIN ... USING. The list of equality conditions is stored
+    either in b->on_expr, or in JOIN::conds, depending on whether there
+    was an outer join.
+
+  EXAMPLE
     SELECT * FROM t1 NATURAL LEFT JOIN t2
      <=>
     SELECT * FROM t1 LEFT JOIN t2 ON (t1.i=t2.i and t1.j=t2.j ... )
+
+    SELECT * FROM t1 NATURAL JOIN t2 WHERE <some_cond>
+     <=>
+    SELECT * FROM t1, t2 WHERE (t1.i=t2.i and t1.j=t2.j and <some_cond>)
+
+    SELECT * FROM t1 JOIN t2 USING(j) WHERE <some_cond>
+     <=>
+    SELECT * FROM t1, t2 WHERE (t1.j=t2.j and <some_cond>)
+
+  RETURN
+    None
 */
 
-void add_join_natural(TABLE_LIST *a,TABLE_LIST *b)
+void add_join_natural(TABLE_LIST *a, TABLE_LIST *b, List<String> *using_fields)
 {
-  b->natural_join=a;
+  b->natural_join= a;
+  b->join_using_fields= using_fields;
 }
 
+
 /*
   Reload/resets privileges and the different caches.