join_nested.test, join_nested.result:

  new file
Many files:
  Nested joins added.


sql/item_cmpfunc.h:
  Nested joins added.
sql/item_func.h:
  Nested joins added.
sql/sql_base.cc:
  Nested joins added.
sql/sql_lex.cc:
  Nested joins added.
sql/sql_lex.h:
  Nested joins added.
sql/sql_parse.cc:
  Nested joins added.
sql/sql_select.cc:
  Nested joins added.
sql/sql_select.h:
  Nested joins added.
sql/sql_yacc.yy:
  Nested joins added.
sql/table.h:
  Nested joins added.
mysql-test/r/join_outer.result:
  Nested joins added.
mysql-test/r/select.result:
  Nested joins added.

10 files changed, 1290 insertions, 198 deletions

diff --git a/sql/item_cmpfunc.h b/sql/item_cmpfunc.h
index 541bc47557d..04819688e0d 100644
--- a/sql/item_cmpfunc.h
+++ b/sql/item_cmpfunc.h
@@ -214,6 +214,40 @@ public:
   Item *neg_transformer();
 };
 
+
+/*
+  The class Item_func_trig_cond is used for guarded predicates 
+  which are employed only for internal purposes.
+  A guarded predicates is an object consisting of an a regular or
+  a guarded predicate P and a pointer to a boolean guard variable g. 
+  A guarded predicate P/g is evaluated to true if the value of the
+  guard g is false, otherwise it is evaluated to the same value that
+  the predicate P: val(P/g)= g ? val(P):true.
+  Guarded predicates allow us to include predicates into a conjunction
+  conditionally. Currently they are utilized for pushed down predicates
+  in queries with outer join operations.
+
+  In the future, probably, it makes sense to extend this class to
+  the objects consisting of three elements: a predicate P, a pointer
+  to a variable g and a firing value s with following evaluation
+  rule: val(P/g,s)= g==s? val(P) : true. It will allow us to build only
+  one item for the objects of the form P/g1/g2... 
+
+  Objects of this class are built only for query execution after
+  the execution plan has been already selected. That's why this
+  class needs only val_int out of generic methods. 
+*/
+
+class Item_func_trig_cond: public Item_bool_func
+{
+  bool *trig_var;
+public:
+  Item_func_trig_cond(Item *a, bool *f) : Item_bool_func(a) { trig_var= f; }
+  longlong val_int() { return *trig_var ? args[0]->val_int() : 1; }
+  enum Functype functype() const { return TRIG_COND_FUNC; };
+  const char *func_name() const { return "trigcond"; };
+};
+
 class Item_func_not_all :public Item_func_not
 {
   bool abort_on_null;
@@ -793,7 +827,7 @@ public:
   }
   const char *func_name() const { return "isnotnull"; }
   optimize_type select_optimize() const { return OPTIMIZE_NULL; }
-  table_map not_null_tables() const { return 0; }
+  table_map not_null_tables() const { return used_tables(); }
   Item *neg_transformer();
   void print(String *str);
 };
diff --git a/sql/item_func.h b/sql/item_func.h
index c2aa62ec2d7..f20946a79fd 100644
--- a/sql/item_func.h
+++ b/sql/item_func.h
@@ -47,7 +47,7 @@ public:
 		  SP_CONTAINS_FUNC,SP_OVERLAPS_FUNC,
 		  SP_STARTPOINT,SP_ENDPOINT,SP_EXTERIORRING,
 		  SP_POINTN,SP_GEOMETRYN,SP_INTERIORRINGN,
-		  NOT_FUNC, NOT_ALL_FUNC,
+		  NOT_FUNC, NOT_ALL_FUNC, TRIG_COND_FUNC,
                   GUSERVAR_FUNC};
   enum optimize_type { OPTIMIZE_NONE,OPTIMIZE_KEY,OPTIMIZE_OP, OPTIMIZE_NULL };
   enum Type type() const { return FUNC_ITEM; }
diff --git a/sql/sql_base.cc b/sql/sql_base.cc
index 02ecb158ebe..7240b8cc271 100644
--- a/sql/sql_base.cc
+++ b/sql/sql_base.cc
@@ -2204,80 +2204,110 @@ int setup_conds(THD *thd,TABLE_LIST *tables,COND **conds)
     thd->where="where clause";
     if ((*conds)->fix_fields(thd, tables, conds) || (*conds)->check_cols(1))
       DBUG_RETURN(1);
-    not_null_tables= (*conds)->not_null_tables();
   }
 
   /* Check if we are using outer joins */
   for (TABLE_LIST *table=tables ; table ; table=table->next)
   {
-    if (table->on_expr)
-    {
-      /* Make a join an a expression */
-      thd->where="on clause";
-      if (table->on_expr->fix_fields(thd, tables, &table->on_expr) ||
-	  table->on_expr->check_cols(1))
-	DBUG_RETURN(1);
-      thd->lex->current_select->cond_count++;
-
-      /*
-	If it's a normal join or a LEFT JOIN which can be optimized away
-	add the ON/USING expression to the WHERE
-      */
-      if (!table->outer_join ||
-	  ((table->table->map & not_null_tables) &&
-	   !(specialflag & SPECIAL_NO_NEW_FUNC)))
+    TABLE_LIST *embedded;
+    TABLE_LIST *embedding= table;
+    do
+    { 
+      embedded= embedding;
+      if (embedded->on_expr)
       {
-	table->outer_join= 0;
-	if (!(*conds=and_conds(*conds, table->on_expr)))
+        /* Make a join an a expression */
+        thd->where="on clause";
+        if (embedded->on_expr->fix_fields(thd, tables, &embedded->on_expr) ||
+	    embedded->on_expr->check_cols(1))
 	  DBUG_RETURN(1);
-	table->on_expr=0;
+        thd->lex->current_select->cond_count++;
       }
-    }
-    if (table->natural_join)
-    {
-      /* Make a join of all fields with have the same name */
-      TABLE *t1=table->table;
-      TABLE *t2=table->natural_join->table;
-      Item_cond_and *cond_and=new Item_cond_and();
-      if (!cond_and)				// If not out of memory
-	DBUG_RETURN(1);
-      cond_and->top_level_item();
-
-      uint i,j;
-      for (i=0 ; i < t1->fields ; i++)
+      if (embedded->natural_join)
       {
-	// TODO: This could be optimized to use hashed names if t2 had a hash
-	for (j=0 ; j < t2->fields ; j++)
-	{
-	  if (!my_strcasecmp(system_charset_info,
-			     t1->field[i]->field_name,
-			     t2->field[j]->field_name))
+        /* Make a join of all fields with have the same name */
+        TABLE_LIST *tab1= embedded;
+        TABLE_LIST *tab2= embedded->natural_join;
+        if (!(embedded->outer_join & JOIN_TYPE_RIGHT))
+        {
+          while (tab1->nested_join)
+          {
+            TABLE_LIST *next;
+            List_iterator_fast<TABLE_LIST> it(tab1->nested_join->join_list);
+            tab1= it++;
+            while ((next= it++))
+              tab1= next;
+          }
+        }
+        else
+        {
+          while (tab1->nested_join)
+            tab1= tab1->nested_join->join_list.head();
+        }
+        if (embedded->outer_join & JOIN_TYPE_RIGHT)
+        {
+          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;
+          }
+        }
+        else
+        {
+          while (tab2->nested_join)
+            tab2= tab2->nested_join->join_list.head();
+        }
+        TABLE *t1=tab1->table;
+        TABLE *t2=tab2->table;
+        Item_cond_and *cond_and=new Item_cond_and();
+        if (!cond_and)				// If not out of memory
+	  DBUG_RETURN(1);
+        cond_and->top_level_item();
+
+        uint i,j;
+        for (i=0 ; i < t1->fields ; i++)
+        {
+	  // TODO: This could be optimized to use hashed names if t2 had a hash
+	  for (j=0 ; j < t2->fields ; j++)
 	  {
-	    Item_func_eq *tmp=new Item_func_eq(new Item_field(t1->field[i]),
-					       new Item_field(t2->field[j]));
-	    if (!tmp)
-	      DBUG_RETURN(1);
-	    tmp->fix_length_and_dec();	// Update cmp_type
-	    tmp->const_item_cache=0;
-	    /* Mark field used for table cache */
-	    t1->field[i]->query_id=t2->field[j]->query_id=thd->query_id;
-	    cond_and->list.push_back(tmp);
-	    t1->used_keys.intersect(t1->field[i]->part_of_key);
-	    t2->used_keys.intersect(t2->field[j]->part_of_key);
-	    break;
+	    if (!my_strcasecmp(system_charset_info,
+			       t1->field[i]->field_name,
+			       t2->field[j]->field_name))
+	    {
+	      Item_func_eq *tmp=new Item_func_eq(new Item_field(t1->field[i]),
+					         new Item_field(t2->field[j]));
+	      if (!tmp)
+	        DBUG_RETURN(1);
+	      tmp->fix_length_and_dec();	// Update cmp_type
+	      tmp->const_item_cache=0;
+	      /* Mark field used for table cache */
+	      t1->field[i]->query_id=t2->field[j]->query_id=thd->query_id;
+	      cond_and->list.push_back(tmp);
+	      t1->used_keys.intersect(t1->field[i]->part_of_key);
+	      t2->used_keys.intersect(t2->field[j]->part_of_key);
+	      break;
+	    }
 	  }
-	}
+        }
+        cond_and->used_tables_cache= t1->map | t2->map;
+        thd->lex->current_select->cond_count+= cond_and->list.elements;
+        COND *on_expr= cond_and;
+        on_expr->fix_fields(thd, 0, &on_expr);
+        if (!embedded->outer_join)			// Not left join
+        {
+	  if (!(*conds=and_conds(*conds, on_expr)))
+	    DBUG_RETURN(1);
+        }
+        else
+	  embedded->on_expr=and_conds(embedded->on_expr,on_expr);
       }
-      cond_and->used_tables_cache= t1->map | t2->map;
-      thd->lex->current_select->cond_count+= cond_and->list.elements;
-      if (!table->outer_join)			// Not left join
-      {
-	if (!(*conds=and_conds(*conds, cond_and)))
-	  DBUG_RETURN(1);
-      }
-      else
-	table->on_expr=and_conds(table->on_expr,cond_and);
+      embedding= embedded->embedding;
     }
+    while (embedding &&
+           embedding->nested_join->join_list.head() == embedded);
   }
   DBUG_RETURN(test(thd->net.report_error));
 }
diff --git a/sql/sql_lex.cc b/sql/sql_lex.cc
index b0381ae1d30..7f2488f16b5 100644
--- a/sql/sql_lex.cc
+++ b/sql/sql_lex.cc
@@ -1014,6 +1014,9 @@ void st_select_lex::init_query()
 {
   st_select_lex_node::init_query();
   table_list.empty();
+  top_join_list.empty();
+  join_list= &top_join_list;
+  embedding= 0;
   item_list.empty();
   join= 0;
   where= 0;
diff --git a/sql/sql_lex.h b/sql/sql_lex.h
index fb7d8415e91..7c234a976cf 100644
--- a/sql/sql_lex.h
+++ b/sql/sql_lex.h
@@ -400,7 +400,10 @@ public:
   List<Item_func_match> *ftfunc_list;
   List<Item_func_match> ftfunc_list_alloc;
   JOIN *join; /* after JOIN::prepare it is pointer to corresponding JOIN */
-  const char *type; /* type of select for EXPLAIN */
+  List<TABLE_LIST> top_join_list; /* join list of the top level          */
+  List<TABLE_LIST> *join_list;    /* list for the currently parsed join  */  
+  TABLE_LIST *embedding;          /* table embedding to the above list   */
+  const char *type;               /* type of select for EXPLAIN          */
 
   SQL_LIST order_list;                /* ORDER clause */
   List<List_item>     expr_list;
@@ -488,6 +491,12 @@ public:
 				List<String> *ignore_index= 0,
                                 LEX_STRING *option= 0);
   TABLE_LIST* get_table_list();
+  bool init_nested_join(THD *thd);
+  TABLE_LIST *end_nested_join(THD *thd);
+  TABLE_LIST *nest_last_join(THD *thd);
+  void save_names_for_using_list(TABLE_LIST *tab1, TABLE_LIST *tab2);
+  void add_joined_table(TABLE_LIST *table);
+  TABLE_LIST *convert_right_join();
   List<Item>* get_item_list();
   List<String>* get_use_index();
   List<String>* get_ignore_index();
diff --git a/sql/sql_parse.cc b/sql/sql_parse.cc
index 104db400133..4a29db75e66 100644
--- a/sql/sql_parse.cc
+++ b/sql/sql_parse.cc
@@ -4687,6 +4687,238 @@ TABLE_LIST *st_select_lex::add_table_to_list(THD *thd,
 
 
 /*
+  Initialize a new table list for a nested join
+
+  SYNOPSIS
+    init_table_list() 
+    thd         current thread
+  
+  DESCRIPTION
+    The function initializes a structure of the TABLE_LIST type
+    for a nested join. It sets up its nested join list as empty.
+    The created structure is added to the front of the current
+    join list in the st_select_lex object. Then the function
+    changes the current nest level for joins to refer to the newly
+    created empty list after having saved the info on the old level
+    in the initialized structure.
+
+  RETURN VALUE
+    0,  if success
+    1,  otherwise
+*/
+
+bool st_select_lex::init_nested_join(THD *thd)
+{
+  TABLE_LIST *ptr;
+  NESTED_JOIN *nested_join;
+  DBUG_ENTER("init_nested_join");
+  
+  if (!(ptr = (TABLE_LIST *) thd->calloc(sizeof(TABLE_LIST))) ||
+      !(nested_join= ptr->nested_join=
+                    (NESTED_JOIN *) thd->calloc(sizeof(NESTED_JOIN))))
+    DBUG_RETURN(1);
+  join_list->push_front(ptr);
+  ptr->embedding= embedding;
+  ptr->join_list= join_list;
+  embedding= ptr;
+  join_list= &nested_join->join_list;
+  join_list->empty();
+  nested_join->used_tables= nested_join->not_null_tables= (table_map) 0;
+  DBUG_RETURN(0);
+}
+
+
+/*
+  End a nested join table list
+
+  SYNOPSIS
+    end_nested_join()
+    thd         current thread
+
+  DESCRIPTION
+    The function returns to the previous join nest level.
+    If the current level contains only one member, the function
+    moves it one level up, eliminating the nest. 
+
+  RETURN VALUE
+    Pointer to TABLE_LIST element added to the total table list, if success
+    0, otherwise
+*/
+
+TABLE_LIST *st_select_lex::end_nested_join(THD *thd)
+{
+  TABLE_LIST *ptr;
+  DBUG_ENTER("end_nested_join");
+  ptr= embedding;
+  join_list= ptr->join_list;
+  embedding= ptr->embedding;
+  NESTED_JOIN *nested_join= ptr->nested_join;
+  if (nested_join->join_list.elements == 1)
+  {
+    TABLE_LIST *embedded= nested_join->join_list.head();
+    join_list->pop();
+    embedded->join_list= join_list;
+    embedded->embedding= embedding;
+    join_list->push_front(embedded);
+    ptr= embedded;
+  }
+  DBUG_RETURN(ptr);
+}
+
+
+/*
+  Nest last join operation
+
+  SYNOPSIS
+    nest_last_join() 
+    thd         current thread
+
+  DESCRIPTION
+    The function nest last join operation as if it was enclosed in braces.
+
+  RETURN VALUE
+    Pointer to TABLE_LIST element created for the new nested join, if success
+    0, otherwise
+*/
+
+TABLE_LIST *st_select_lex::nest_last_join(THD *thd)
+{
+  TABLE_LIST *ptr;
+  NESTED_JOIN *nested_join;
+  DBUG_ENTER("nest_last_join");
+  
+  if (!(ptr = (TABLE_LIST *) thd->calloc(sizeof(TABLE_LIST))) ||
+      !(nested_join= ptr->nested_join=
+                    (NESTED_JOIN *) thd->calloc(sizeof(NESTED_JOIN))))
+    DBUG_RETURN(0);
+  ptr->embedding= embedding;
+  ptr->join_list= join_list;
+  List<TABLE_LIST> *embedded_list= &nested_join->join_list;
+  embedded_list->empty();
+  for (int i=0; i < 2; i++)
+  {
+    TABLE_LIST *table= join_list->pop();
+    table->join_list= embedded_list;
+    table->embedding= ptr;
+    embedded_list->push_back(table);
+  }
+  join_list->push_front(ptr);
+  nested_join->used_tables= nested_join->not_null_tables= (table_map) 0;
+  DBUG_RETURN(ptr);
+}
+
+
+/*
+  Save names for a join with using clase
+   
+  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
+    add_joined_table()
+    table       the table to add
+
+  DESCRIPTION
+    The function puts a table in front of the current join list
+    of st_select_lex object.
+    Thus, joined tables are put into this list in the reverse order
+    (the most outer join operation follows first).
+
+  RETURN VALUE
+    None
+*/
+
+void st_select_lex::add_joined_table(TABLE_LIST *table)
+{
+  DBUG_ENTER("add_joined_table");
+  join_list->push_front(table);
+  table->join_list= join_list;
+  table->embedding= embedding;
+  DBUG_VOID_RETURN;
+}
+
+
+/*
+  Convert a right join into equivalent left join
+
+  SYNOPSIS
+    convert_right_join()
+    thd         current thread
+  
+  DESCRIPTION 
+    The function takes the current join list t[0],t[1] ... and 
+    effectively converts it into the list t[1],t[0] ...
+    Although the outer_join flag for the new nested table contains
+    JOIN_TYPE_RIGHT, it will be handled as the inner table of a left join
+    operation.
+
+  EXAMPLES
+    SELECT * FROM t1 RIGHT JOIN t2 ON on_expr =>
+      SELECT * FROM t2 LEFT JOIN t1 ON on_expr
+
+    SELECT * FROM t1,t2 RIGHT JOIN t3 ON on_expr =>
+      SELECT * FROM t1,t3 LEFT JOIN t2 ON on_expr
+
+    SELECT * FROM t1,t2 RIGHT JOIN (t3,t4) ON on_expr =>
+      SELECT * FROM t1,(t3,t4) LEFT JOIN t2 ON on_expr
+
+    SELECT * FROM t1 LEFT JOIN t2 ON on_expr1 RIGHT JOIN t3  ON on_expr2 =>
+      SELECT * FROM t3 LEFT JOIN (t1 LEFT JOIN t2 ON on_expr2) ON on_expr1
+
+  RETURN
+    Pointer to the table representing the inner table, if success
+    0, otherwise
+*/
+
+TABLE_LIST *st_select_lex::convert_right_join() 
+{
+  TABLE_LIST *tab2= join_list->pop();
+  TABLE_LIST *tab1= join_list->pop(); 
+  DBUG_ENTER("convert_right_join");
+
+  join_list->push_front(tab2);
+  join_list->push_front(tab1);
+  tab1->outer_join|= JOIN_TYPE_RIGHT;
+
+  DBUG_RETURN(tab1);
+}
+
+/*
   Set lock for all tables in current select level
 
   SYNOPSIS:
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index 9f26d7458d0..bf53a36457f 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -61,6 +61,7 @@ static store_key *get_store_key(THD *thd,
 				KEY_PART_INFO *key_part, char *key_buff,
 				uint maybe_null);
 static bool make_simple_join(JOIN *join,TABLE *tmp_table);
+static void make_outerjoin_info(JOIN *join);
 static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *item);
 static void make_join_readinfo(JOIN *join,uint options);
 static bool only_eq_ref_tables(JOIN *join, ORDER *order, table_map tables);
@@ -73,7 +74,10 @@ static int return_zero_rows(JOIN *join, select_result *res,TABLE_LIST *tables,
 			    uint select_options, const char *info,
 			    Item *having, Procedure *proc,
 			    SELECT_LEX_UNIT *unit);
+static COND *simplify_joins(JOIN *join, List<TABLE_LIST> *join_list,
+                            COND *conds, bool top);
 static COND *optimize_cond(COND *conds,Item::cond_result *cond_value);
+static bool resolve_nested_join (TABLE_LIST *table);
 static COND *remove_eq_conds(COND *cond,Item::cond_result *cond_value);
 static bool const_expression_in_where(COND *conds,Item *item, Item **comp_item);
 static bool open_tmp_table(TABLE *table);
@@ -128,6 +132,7 @@ static int remove_dup_with_compare(THD *thd, TABLE *entry, Field **field,
 				   ulong offset,Item *having);
 static int remove_dup_with_hash_index(THD *thd, TABLE *table,
 				      uint field_count, Field **first_field,
+
 				      ulong key_length,Item *having);
 static int join_init_cache(THD *thd,JOIN_TAB *tables,uint table_count);
 static ulong used_blob_length(CACHE_FIELD **ptr);
@@ -299,6 +304,7 @@ JOIN::prepare(Item ***rref_pointer_array,
   tables_list= tables_init;
   select_lex= select_lex_arg;
   select_lex->join= this;
+  join_list= &select_lex->top_join_list;
   union_part= (unit_arg->first_select()->next_select() != 0);
 
   /* Check that all tables, fields, conds and order are ok */
@@ -486,7 +492,6 @@ bool JOIN::test_in_subselect(Item **where)
   return 0;
 }
 
-
 /*
   global select optimisation.
   return 0 - success
@@ -524,6 +529,9 @@ JOIN::optimize()
   }
 #endif
 
+  /* Convert all outer joins to inner joins if possible */
+  conds= simplify_joins(this, join_list, conds, TRUE);
+
   conds= optimize_cond(conds,&cond_value);
   if (thd->net.report_error)
   {
@@ -637,6 +645,9 @@ JOIN::optimize()
     DBUG_PRINT("error",("Error: make_select() failed"));
     DBUG_RETURN(1);
   }
+
+  make_outerjoin_info(this);
+
   if (make_join_select(this, select, conds))
   {
     zero_result_cause=
@@ -1456,7 +1467,7 @@ JOIN::exec()
 	    at least one row generated from the table.
 	  */
 	  if (curr_table->select_cond ||
-	      (curr_table->keyuse && !curr_table->on_expr))
+	      (curr_table->keyuse && !curr_table->first_inner))
 	  {
 	    /* We have to sort all rows */
 	    curr_join->select_limit= HA_POS_ERROR;
@@ -1676,6 +1687,7 @@ make_join_statistics(JOIN *join,TABLE_LIST *tables,COND *conds,
 		     DYNAMIC_ARRAY *keyuse_array)
 {
   int error;
+  TABLE *table;
   uint i,table_count,const_count,key;
   table_map found_const_table_map, all_table_map, found_ref, refs;
   key_map const_ref, eq_part;
@@ -1701,13 +1713,15 @@ make_join_statistics(JOIN *join,TABLE_LIST *tables,COND *conds,
 
   for (s=stat,i=0 ; tables ; s++,tables=tables->next,i++)
   {
-    TABLE *table;
+    table_map dep_tables;
+    TABLE_LIST *embedding= tables->embedding;
     stat_vector[i]=s;
     s->keys.init();
     s->const_keys.init();
     s->checked_keys.init();
     s->needed_reg.init();
     table_vector[i]=s->table=table=tables->table;
+    table->pos_in_table_list= tables;
     table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);// record count
     table->quick_keys.clear_all();
     table->reginfo.join_tab=s;
@@ -1716,29 +1730,36 @@ make_join_statistics(JOIN *join,TABLE_LIST *tables,COND *conds,
     all_table_map|= table->map;
     s->join=join;
     s->info=0;					// For describe
+
+    s->dependent= tables->dep_tables;
+    s->key_dependent= 0;
+
     if ((s->on_expr=tables->on_expr))
     {
-      /* Left join */
+      /* s is the only inner table of an outer join */
       if (!table->file->records)
       {						// Empty table
-	s->key_dependent=s->dependent=0;	// Ignore LEFT JOIN depend.
+        s->dependent= 0;                        // Ignore LEFT JOIN depend.
 	set_position(join,const_count++,s,(KEYUSE*) 0);
 	continue;
       }
-      s->key_dependent=s->dependent=
-	s->on_expr->used_tables() & ~(table->map);
-      if (table->outer_join & JOIN_TYPE_LEFT)
-	s->dependent|=stat_vector[i-1]->dependent | table_vector[i-1]->map;
-      if (tables->outer_join & JOIN_TYPE_RIGHT)
-	s->dependent|=tables->next->table->map;
-      outer_join|=table->map;
+      outer_join|= table->map;
       continue;
     }
-    if (tables->straight)			// We don't have to move this
-      s->dependent= table_vector[i-1]->map | stat_vector[i-1]->dependent;
-    else
-      s->dependent=(table_map) 0;
-    s->key_dependent=(table_map) 0;
+    if (embedding)
+    {
+      /* s belongs to a nested join, maybe to several embedded joins */
+      do
+      {
+        NESTED_JOIN *nested_join= embedding->nested_join;
+        s->dependent|= embedding->dep_tables;
+        embedding= embedding->embedding;
+        outer_join|= nested_join->used_tables;
+      }
+      while (embedding);
+      continue;
+    }
+
     if ((table->system || table->file->records <= 1) && ! s->dependent &&
 	!(table->file->table_flags() & HA_NOT_EXACT_COUNT) &&
         !table->fulltext_searched)
@@ -1749,39 +1770,35 @@ make_join_statistics(JOIN *join,TABLE_LIST *tables,COND *conds,
   stat_vector[i]=0;
   join->outer_join=outer_join;
 
-  /*
-    If outer join: Re-arrange tables in stat_vector so that outer join
-    tables are after all tables it is dependent of.
-    For example: SELECT * from A LEFT JOIN B ON B.c=C.c, C WHERE A.C=C.C
-    Will shift table B after table C.
-  */
-  if (outer_join)
+  if (join->outer_join)
   {
-    table_map used_tables=0L;
-    for (i=0 ; i < join->tables-1 ; i++)
+    /* 
+       Build transitive closure for relation 'to be dependent on'.
+       This will speed up the plan search for many cases with outer joins,
+       as well as allow us to catch illegal cross references/
+       Warshall's algorithm is used to build the transitive closure.
+       As we use bitmaps to represent the relation the complexity
+       of the algorithm is O(number of tables). 
+    */
+    for (i= 0, s= stat ; i < table_count ; i++, s++)
     {
-      if (stat_vector[i]->dependent & ~used_tables)
+      for (uint j= 0 ; j < table_count ; j++)
       {
-	JOIN_TAB *save= stat_vector[i];
-	uint j;
-	for (j=i+1;
-	     j < join->tables && stat_vector[j]->dependent & ~used_tables;
-	     j++)
-	{
-	  JOIN_TAB *tmp=stat_vector[j];		// Move element up
-	  stat_vector[j]=save;
-	  save=tmp;
-	}
-	if (j == join->tables)
-	{
-	  join->tables=0;			// Don't use join->table
-	  my_error(ER_WRONG_OUTER_JOIN,MYF(0));
-	  DBUG_RETURN(1);
-	}
-	stat_vector[i]=stat_vector[j];
-	stat_vector[j]=save;
+        table= stat[j].table;
+        if (s->dependent & table->map)
+          s->dependent |= table->reginfo.join_tab->dependent;
+      }
+    }
+    /* Catch illegal cross references for outer joins */
+    for (i= 0, s= stat ; i < table_count ; i++, s++)
+    {
+      if (s->dependent & s->table->map)
+      {
+        join->tables=0;			// Don't use join->table
+        my_error(ER_WRONG_OUTER_JOIN,MYF(0));
+        DBUG_RETURN(1);
       }
-      used_tables|= stat_vector[i]->table->map;
+      s->key_dependent= s->dependent;
     }
   }
 
@@ -1824,7 +1841,7 @@ make_join_statistics(JOIN *join,TABLE_LIST *tables,COND *conds,
 
     for (JOIN_TAB **pos=stat_vector+const_count ; (s= *pos) ; pos++)
     {
-      TABLE *table=s->table;
+      table=s->table;
       if (s->dependent)				// If dependent on some table
       {
 	// All dep. must be constants
@@ -2481,11 +2498,32 @@ update_ref_and_keys(THD *thd, DYNAMIC_ARRAY *keyuse,JOIN_TAB *join_tab,
   }
   for (i=0 ; i < tables ; i++)
   {
+    /*
+      Block the creation of keys for inner tables of outer joins.
+      Here only the outer joins that can not be converted to
+      inner joins are left and all nests that can be eliminated
+      are flattened.
+      In the future when we introduce conditional accesses
+      for inner tables in outer joins these keys will be taken
+      into account as well.
+    */ 
     if (join_tab[i].on_expr)
     {
       add_key_fields(join_tab,&end,&and_level,join_tab[i].on_expr,
 		     join_tab[i].table->map);
     }
+    else 
+    {
+      TABLE_LIST *tab= join_tab[i].table->pos_in_table_list;
+      TABLE_LIST *embedding= tab->embedding;
+      if (embedding)
+      {
+        NESTED_JOIN *nested_join= embedding->nested_join;
+        if (nested_join->join_list.head() == tab)
+          add_key_fields(join_tab, &end, &and_level, embedding->on_expr,
+                         nested_join->used_tables);
+      }
+    }
   }
   /* fill keyuse with found key parts */
   for ( ; field != end ; field++)
@@ -2923,7 +2961,7 @@ find_best(JOIN *join,table_map rest_tables,uint idx,double record_count,
         {
           /* Estimate cost of reading table. */
           tmp= s->table->file->scan_time();
-          if (s->on_expr)                         // Can't use join cache
+          if (s->table->map  & join->outer_join)      // Can't use join cache
           {
             /*
               For each record we have to:
@@ -3357,6 +3395,8 @@ make_simple_join(JOIN *join,TABLE *tmp_table)
   join_tab->keys.init(~0);                      /* test everything in quick */
   join_tab->info=0;
   join_tab->on_expr=0;
+  join_tab->last_inner= 0;
+  join_tab->first_unmatched= 0;
   join_tab->ref.key = -1;
   join_tab->not_used_in_distinct=0;
   join_tab->read_first_record= join_init_read_record;
@@ -3368,6 +3408,134 @@ make_simple_join(JOIN *join,TABLE *tmp_table)
 }
 
 
+/*
+  Build a predicate guarded by match variables for embedding outer joins
+
+  SYNOPSIS
+    add_found_match_trig_cond()
+    tab       the first inner table for most nested outer join
+    cond      the predicate to be guarded
+    root_tab  the first inner table to stop
+
+  DESCRIPTION
+    The function recursively adds guards for predicate cond
+    assending from tab to the first inner table  next embedding
+    nested outer join and so on until it reaches root_tab
+    (root_tab can be 0).
+
+  RETURN VALUE
+    pointer to the guarded predicate, if success
+    0, otherwise
+*/ 
+
+static COND*
+add_found_match_trig_cond(JOIN_TAB *tab, COND *cond, JOIN_TAB *root_tab)
+{
+  COND *tmp;
+  if (tab == root_tab || !cond)
+    return cond;
+  if ((tmp= add_found_match_trig_cond(tab->first_upper, cond, root_tab)))
+  {
+    tmp= new Item_func_trig_cond(tmp, &tab->found);
+  }
+  return tmp;
+}
+
+
+/*
+   Fill in outer join related info for the execution plan structure
+
+  SYNOPSIS
+    make_outerjoin_info()
+    join - reference to the info fully describing the query
+
+  DESCRIPTION
+    For each outer join operation left after simplification of the
+    original query the function set up the following pointers in the linear
+    structure join->join_tab representing the selected execution plan.
+    The first inner table t0 for the operation is set to refer to the last
+    inner table tk through the field t0->last_inner.
+    Any inner table ti for the operation are set to refer to the first
+    inner table ti->first_inner.
+    The first inner table t0 for the operation is set to refer to the
+    first inner table of the embedding outer join operation, if there is any,
+    through the field t0->first_upper.
+    The on expression for the outer join operation is attached to the
+    corresponding first inner table through the field t0->on_expr.
+    Here ti are structures of the JOIN_TAB type.
+
+  EXAMPLE
+    For rhe query: 
+      SELECT * FROM t1
+                    LEFT JOIN
+                    (t2, t3 LEFT JOIN t4 ON t3.a=t4.a)
+                    ON (t1.a=t2.a AND t1.b=t3.b)
+        WHERE t1.c > 5,
+    given the execution plan with the table order t1,t2,t3,t4
+    is selected, the following references will be set;
+    t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2]
+    t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2],
+    on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to t2->on_expr,
+    while t3.a=t4.a will be attached to t4->on_expr.
+            
+  NOTES
+    The function assumes that the simplification procedure has been
+    already applied to the join query (see simplify_joins).
+    This function can be called only after the execution plan
+    has been chosen.
+   
+  RETURN VALUE
+    None.
+*/
+ 
+static void
+make_outerjoin_info(JOIN *join)
+{
+  for (uint i=join->const_tables ; i < join->tables ; i++)
+  {
+    JOIN_TAB *tab=join->join_tab+i;
+    TABLE *table=tab->table;
+    TABLE_LIST *tbl= table->pos_in_table_list;
+    TABLE_LIST *embedding= tbl->embedding;
+
+    if (tbl->outer_join)
+    {
+      /* 
+        Table tab is the only one inner table for outer join.
+        (Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a
+        is in the query above.)
+      */
+      tab->last_inner= tab->first_inner= tab;
+      tab->on_expr= tbl->on_expr;
+      if (embedding)
+        tab->first_upper= embedding->nested_join->first_nested;
+    }    
+    while (embedding)
+    {
+      NESTED_JOIN *nested_join= embedding->nested_join;
+      if (!nested_join->counter)
+      {
+        /* 
+          Table tab is the first inner table for nested_join.
+          Save reference to it in the nested join structure.
+        */ 
+        nested_join->first_nested= tab;
+        tab->on_expr= embedding->on_expr;
+        if (embedding->embedding)
+          tab->first_upper= embedding->embedding->nested_join->first_nested;
+      }
+      if (!tab->first_inner)  
+        tab->first_inner= nested_join->first_nested;
+      if (++nested_join->counter < nested_join->join_list.elements)
+        break;
+      /* Table tab is the last inner table for nested join. */
+      nested_join->first_nested->last_inner= tab;
+      embedding= embedding->embedding;
+    }
+  }
+}
+
+
 static bool
 make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
 {
@@ -3394,6 +3562,7 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
     for (uint i=join->const_tables ; i < join->tables ; i++)
     {
       JOIN_TAB *tab=join->join_tab+i;
+      JOIN_TAB *first_inner_tab= tab->first_inner; 
       table_map current_map= tab->table->map;
       /*
 	Following force including random expression in last table condition.
@@ -3432,7 +3601,16 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
 	  join->thd->memdup((gptr) select, sizeof(SQL_SELECT));
 	if (!sel)
 	  DBUG_RETURN(1);			// End of memory
+        /*
+          If tab is an inner table of an outer join operation,
+          add a match guard to the pushed down predicate.
+          The guard will turn the predicate on only after
+          the first match for outer tables is encountered.
+	*/        
+        if (!(tmp= add_found_match_trig_cond(first_inner_tab, tmp, 0)))
+          DBUG_RETURN(1);
 	tab->select_cond=sel->cond=tmp;
+
 	sel->head=tab->table;
 	if (tab->quick)
 	{
@@ -3540,13 +3718,62 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
 	    }
 	  }
 	}
+      } 
+      
+      /* 
+        Push down all predicates from on expressions.
+        Each of these predicated are guarded by a variable
+        that turns if off just before null complemented row for
+        outer joins is formed. Thus, the predicates from an
+        'on expression' are guaranteed not to be checked for
+        the null complemented row.
+      */ 
+      JOIN_TAB *last_tab= tab;
+      while (first_inner_tab && first_inner_tab->last_inner == last_tab)
+      {  
+        /* 
+          Table tab is the last inner table of an outer join.
+          An on expression is always attached to it.
+	*/     
+        COND *on_expr= first_inner_tab->on_expr;
+
+        table_map used_tables= join->const_table_map |
+		               OUTER_REF_TABLE_BIT | RAND_TABLE_BIT;
+	for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++)
+        {
+          current_map= tab->table->map;
+          used_tables|= current_map;
+          COND *tmp= make_cond_for_table(on_expr, used_tables, current_map);
+          if (tmp)
+          {
+            JOIN_TAB *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;
+            /*
+              First add the guards for match variables of
+              all embedding outer join operations.
+	    */
+            if (!(tmp= add_found_match_trig_cond(cond_tab->first_inner,
+                                                 tmp, first_inner_tab)))
+              DBUG_RETURN(1);
+            /* 
+              Now add the guard turning the predicate off for 
+              the null complemented row.
+	    */ 
+            tmp= new Item_func_trig_cond(tmp, 
+                                         &first_inner_tab->not_null_compl);
+	    /* Add the predicate to other pushed down predicates */
+            cond_tab->select_cond= !cond_tab->select_cond ? tmp :
+	                          new Item_cond_and(cond_tab->select_cond,tmp);
+            if (!cond_tab->select_cond)
+	      DBUG_RETURN(1);
+          }              
+        }
+        first_inner_tab= first_inner_tab->first_upper;       
       }
     }
   }
   DBUG_RETURN(0);
 }
 
-
 static void
 make_join_readinfo(JOIN *join, uint options)
 {
@@ -3631,7 +3858,7 @@ make_join_readinfo(JOIN *join, uint options)
       */
       table->status=STATUS_NO_RECORD;
       if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
-	  tab->use_quick != 2 && !tab->on_expr)
+          tab->use_quick != 2 && !tab->first_inner)
       {
 	if ((options & SELECT_DESCRIBE) ||
 	    !join_init_cache(join->thd,join->join_tab+join->const_tables,
@@ -4334,6 +4561,231 @@ COND *eliminate_not_funcs(COND *cond)
 }
 
 
+/*
+  Simplify joins replacing outer joins by inner joins whenever it's possible
+
+  SYNOPSIS
+    simplify_joins()
+    join        reference to the query info
+    join_list   list representation of the join to be converted
+    conds       conditions to add on expressions for converted joins
+    top         true <=> conds is the where condition  
+
+  DESCRIPTION
+    The function, during a retrieval of join_list,  eliminates those
+    outer joins that can be converted into inner join, possibly nested.
+    It also moves the on expressions for the converted outer joins
+    and from inner joins to conds.
+    The function also calculates some attributes for nested joins:
+    - used_tables    
+    - not_null_tables
+    - dep_tables.
+    - on_expr_dep_tables
+    The first two attributes are used to test whether an outer join can
+    be substituted for an inner join. The third attribute represents the
+    relation 'to be dependent on' for tables. If table t2 is dependent
+    on table t1, then in any evaluated execution plan table access to
+    table t2 must precede access to table t2. This relation is used also
+    to check whether the query contains  invalid cross-references.
+    The forth attribute is an auxiliary one and is used to calculate
+    dep_tables.
+    As the attribute dep_tables qualifies possibles orders of tables in the
+    execution plan, the dependencies required by the straight join
+    modifiers are reflected in this attribute as well.
+    The function also removes all braces that can be removed from the join
+    expression without changing its meaning.
+
+  NOTES
+    An outer join can be replaced by an inner join if the where condition
+    or the on expression for an embedding nested join contains a conjunctive
+    predicate rejecting null values for some attribute of the inner tables.
+
+    E.g. in the query:    
+      SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
+    the predicate t2.b < 5 rejects nulls.
+    The query is converted first to:
+      SELECT * FROM t1 INNER JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
+    then to the equivalent form:
+      SELECT * FROM t1, t2 ON t2.a=t1.a WHERE t2.b < 5 AND t2.a=t1.a.
+
+    Similarly the following query:
+      SELECT * from t1 LEFT JOIN (t2, t3) ON t2.a=t1.a t3.b=t1.b
+        WHERE t2.c < 5  
+    is converted to:
+      SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b 
+
+    One conversion might trigger another:
+      SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a
+                       LEFT JOIN t3 ON t3.b=t2.b
+        WHERE t3 IS NOT NULL =>
+      SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a, t3
+        WHERE t3 IS NOT NULL AND t3.b=t2.b => 
+      SELECT * FROM t1, t2, t3
+        WHERE t3 IS NOT NULL AND t3.b=t2.b AND t2.a=t1.a
+   
+    The function removes all unnecessary braces from the expression
+    produced by the conversions.
+    E.g. SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b
+    finally is converted to: 
+      SELECT * FROM t1, t2, t3 WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b
+
+    It also will remove braces from the following queries:
+      SELECT * from (t1 LEFT JOIN t2 ON t2.a=t1.a) LEFT JOIN t3 ON t3.b=t2.b
+      SELECT * from (t1, (t2,t3)) WHERE t1.a=t2.a AND t2.b=t3.b.
+
+    The benefit of this simplification procedure is that it might return 
+    a query for which the optimizer can evaluate execution plan with more
+    join orders. With a left join operation the optimizer does not
+    consider any plan where one of the inner tables is before some of outer
+    tables.
+
+  IMPLEMENTATION.
+    The function is implemented by a recursive procedure.  On the recursive
+    ascent all attributes are calculated, all outer joins that can be
+    converted are replaced and then all unnecessary braces are removed.
+    As join list contains join tables in the reverse order sequential
+    elimination of outer joins does not requite extra recursive calls.
+
+  EXAMPLES
+    Here is an example of a join query with invalid cross references:
+      SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t3.a LEFT JOIN ON  t3.b=t1.b 
+     
+  RETURN VALUE
+    The new condition, if success
+    0, otherwise  
+*/
+
+static COND *
+simplify_joins(JOIN *join, List<TABLE_LIST> *join_list, COND *conds, bool top)
+{
+  TABLE_LIST *table;
+  NESTED_JOIN *nested_join;
+  TABLE_LIST *prev_table= 0;
+  List_iterator<TABLE_LIST> li(*join_list);
+
+  /* 
+    Try to simplify join operations from join_list.
+    The most outer join operation is checked for conversion first. 
+  */
+  while ((table= li++))
+  {
+    table_map used_tables;
+    table_map not_null_tables= (table_map) 0;
+
+    if ((nested_join= table->nested_join))
+    {
+      /* 
+         If the element of join_list is a nested join apply
+         the procedure to its nested join list first.
+      */
+      if (table->on_expr)
+      {
+        /* 
+           If an on expression E is attached to the table, 
+           check all null rejected predicates in this expression.
+           If such a predicate over an attribute belonging to
+           an inner table of an embedded outer join is found,
+           the outer join is converted to an inner join and
+           the corresponding on expression is added to E. 
+	*/ 
+        table->on_expr= simplify_joins(join, &nested_join->join_list,
+                                       table->on_expr, top && FALSE);
+      }
+      nested_join->used_tables= (table_map) 0;
+      nested_join->not_null_tables=(table_map) 0;
+      conds= simplify_joins(join, &nested_join->join_list, conds, top);
+      used_tables= nested_join->used_tables;
+      not_null_tables= nested_join->not_null_tables;  
+    }
+    else
+    {
+      used_tables= table->table->map;
+      if (conds)
+        not_null_tables= conds->not_null_tables();
+    }
+      
+    if (table->embedding)
+    {
+      table->embedding->nested_join->used_tables|= used_tables;
+      table->embedding->nested_join->not_null_tables|= not_null_tables;
+    }
+
+    if (!table->outer_join || (used_tables & not_null_tables))
+    {
+      /* 
+        For some of the inner tables there are conjunctive predicates
+        that reject nulls => the outer join can be replaced by an inner join.
+      */
+      table->outer_join= 0;
+      if (table->on_expr)
+      {
+        /* Add on expression to the where condition. */
+        if (conds)
+        {
+          conds= and_conds(conds, table->on_expr);
+          conds->fix_fields(join->thd, 0, &conds);
+        }
+        else
+          conds= table->on_expr; 
+        table->on_expr= 0;
+      }
+    }
+    
+    if (!top)
+      continue;
+
+    /* 
+      Only inner tables of non-convertible outer joins
+      remain with on_expr.
+    */ 
+    if (table->on_expr)
+    {
+      table->dep_tables|= table->on_expr->used_tables(); 
+      if (table->embedding)
+      {
+        table->dep_tables&= ~table->embedding->nested_join->used_tables;   
+        /*
+           Embedding table depends on tables used
+           in embedded on expressions. 
+        */
+        table->embedding->on_expr_dep_tables|= table->on_expr->used_tables();
+      }
+      else
+        table->dep_tables&= ~table->table->map;
+    }
+
+    if (prev_table)
+    {
+      /* The order of tables is reverse: prev_table follows table */
+      if (prev_table->straight)
+        prev_table->dep_tables|= used_tables;
+      if (prev_table->on_expr)
+        prev_table->dep_tables|= table->on_expr_dep_tables;
+    }
+    prev_table= table;
+  }
+    
+  /* Flatten nested joins that can be flattened. */
+  li.rewind();
+  while((table= li++))
+  {
+    nested_join= table->nested_join;
+    if (nested_join && !table->on_expr)
+    {
+      TABLE_LIST *tbl;
+      List_iterator<TABLE_LIST> it(nested_join->join_list);
+      while ((tbl= it++))
+      {
+        tbl->embedding= table->embedding;
+        tbl->join_list= table->join_list;
+      }      
+      li.replace(nested_join->join_list);
+    }
+  }
+  return conds;         
+}
+      
+
 static COND *
 optimize_cond(COND *conds,Item::cond_result *cond_value)
 {
@@ -4567,7 +5019,6 @@ const_expression_in_where(COND *cond, Item *comp_item, Item **const_item)
   return 0;
 }
 
-
 /****************************************************************************
   Create internal temporary table
 ****************************************************************************/
@@ -5587,7 +6038,7 @@ do_select(JOIN *join,List<Item> *fields,TABLE *table,Procedure *procedure)
   if (join->tables == join->const_tables)
   {
     /*
-      HAVING will be chcked after processing aggregate functions,
+      HAVING will be checked after processing aggregate functions,
       But WHERE should checkd here (we alredy have read tables)
     */
     if (!join->conds || join->conds->val_int())
@@ -5675,21 +6126,144 @@ sub_select_cache(JOIN *join,JOIN_TAB *join_tab,bool end_of_records)
   return sub_select(join,join_tab,end_of_records); /* Use ordinary select */
 }
 
+/*
+  Retrieve records ends with a given beginning from the result of a join  
+
+  SYNPOSIS
+    sub_select()
+    join      pointer to the structure providing all context info for the query
+    join_tab  the first next table of the execution plan to be retrieved
+    end_records  true when we need to perform final steps of retrival   
+
+  DESCRIPTION
+    For a given partial join record consisting of records from the tables 
+    preceding the table join_tab in the execution plan, the function
+    retrieves all matching full records from the result set and
+    send them to the result set stream. 
+
+  NOTES
+    The function effectively implements the  final (n-k) nested loops
+    of nested loops join algorithm, where k is the ordinal number of
+    the join_tab table and n is the total number of tables in the join query.
+    It performs nested loops joins with all conjunctive predicates from
+    the where condition pushed as low to the tables as possible.
+    E.g. for the query
+      SELECT * FROM t1,t2,t3 
+        WHERE t1.a=t2.a AND t2.b=t3.b AND t1.a BETWEEN 5 AND 9
+    the predicate (t1.a BETWEEN 5 AND 9) will be pushed to table t1,
+    given the selected plan prescribes to nest retrievals of the
+    joined tables in the following order: t1,t2,t3.
+    A pushed down predicate are attached to the table which it pushed to,
+    at the field select_cond.
+    When executing a nested loop of level k the function runs through
+    the rows of 'join_tab' and for each row checks the pushed condition
+    attached to the table.
+    If it is false the function moves to the next row of the
+    table. If the condition is true the function recursively executes (n-k-1)
+    remaining embedded nested loops.
+    The situation becomes more complicated if outer joins are involved in
+    the execution plan. In this case the pushed down predicates can be
+    checked only at certain conditions.
+    Suppose for the query
+      SELECT * FROM t1 LEFT JOIN (t2,t3) ON t3.a=t1.a 
+        WHERE t1>2 AND (t2.b>5 OR t2.b IS NULL)
+    the optimizer has chosen a plan with the table order t1,t2,t3.  
+    The predicate P1=t1>2 will be pushed down to the table t1, while the
+    predicate P2=(t2.b>5 OR t2.b IS NULL) will be attached to the table
+    t2. But the second predicate can not be unconditionally tested right
+    after a row from t2 has been read. This can be done only after the
+    first row with t3.a=t1.a has been encountered.
+    Thus, the second predicate P2 is supplied with a guarded value that are
+    stored in the field 'found' of the first inner table for the outer join
+    (table t2). When the first row with t3.a=t1.a for the  current row 
+    of table t1  appears, the value becomes true. For now on the predicate
+    is evaluated immediately after the row of table t2 has been read.
+    When the first row with t3.a=t1.a has been encountered all
+    conditions attached to the inner tables t2,t3 must be evaluated.
+    Only when all of them are true the row is sent to the output stream.
+    If not, the function returns to the lowest nest level that has a false
+    attached condition.
+    The predicates from on expressions are also pushed down. If in the 
+    the above example the on expression were (t3.a=t1.a AND t2.a=t1.a),
+    then t1.a=t2.a would be pushed down to table t2, and without any
+    guard.
+    If after the run through all rows of table t2, the first inner table
+    for the outer join operation, it turns out that no matches are
+    found for the current row of t1, then current row from table t1
+    is complemented by nulls  for t2 and t3. Then the pushed down predicates
+    are checked for the composed row almost in the same way as it had
+    been done for the first row with a match. The only difference is
+    the predicates  from on expressions are not checked. 
+
+  IMPLEMENTATION
+    The function forms output rows for a current partial join of k
+    tables tables recursively.
+    For each partial join record ending with a certain row from
+    join_tab it calls sub_select that builds all possible matching
+    tails from the result set.
+    To be able  check predicates conditionally items of the class
+    Item_func_trig_cond  are employed.
+    An object of  this class is constructed from an item of class COND
+    and a pointer to a guarding boolean variable.
+    When the value of the guard variable is true the value of the object
+    is the same as the value of the predicate, otherwise it's just returns
+    true. 
+    To carry out a return to a nested loop level of join table t the pointer 
+    to t is remembered in the field 'return_tab' of the join structure.
+    Consider the following query:
+      SELECT * FROM t1,
+                    LEFT JOIN
+                    (t2, t3 LEFT JOIN (t4,t5) ON t5.a=t3.a)
+                    ON t4.a=t2.a
+         WHERE (t2.b=5 OR t2.b IS NULL) AND (t4.b=2 OR t4.b IS NULL)
+    Suppose the chosen execution plan dictates the order t1,t2,t3,t4,t5
+    and suppose for a given joined rows from tables t1,t2,t3 there are
+    no rows in the result set yet.
+    When first row from t5 that satisfies the on condition
+    t5.a=t3.a is found, the pushed down predicate t4.b=2 OR t4.b IS NULL
+    becomes 'activated', as well the predicate t4.a=t2.a. But
+    the predicate (t2.b=5 OR t2.b IS NULL) can not be checked until
+    t4.a=t2.a becomes true. 
+    In order not to re-evaluate the predicates that were already evaluated
+    as attached pushed down predicates, a pointer to the the first
+    most inner unmatched table is maintained in join_tab->first_unmatched.
+    Thus, when the first row from t5 with t5.a=t3.a is found
+    this pointer for t5 is changed from t4 to t2.             
+
+  RETURN
+    0, if success
+    # of the error, otherwise
+    
+*/
 
 static int
 sub_select(JOIN *join,JOIN_TAB *join_tab,bool end_of_records)
 {
-
   join_tab->table->null_row=0;
   if (end_of_records)
     return (*join_tab->next_select)(join,join_tab+1,end_of_records);
 
-  /* Cache variables for faster loop */
   int error;
-  bool found=0;
-  COND *on_expr=join_tab->on_expr, *select_cond=join_tab->select_cond;
+  JOIN_TAB *first_unmatched;
+  JOIN_TAB *tab;
+  bool found= 0;
+  /* Cache variables for faster loop */
+  COND *select_cond= join_tab->select_cond;
+  JOIN_TAB *first_inner_tab= join_tab->first_inner;
+   
   my_bool *report_error= &(join->thd->net.report_error);
 
+  if (join_tab->last_inner)
+  { /* join_tab is the first inner table for an outer join operation. */
+
+    /* Set initial state of guard variables for this table.*/
+    join_tab->found=0;
+    join_tab->not_null_compl= 1;
+
+    /* Set first_unmatched for the last inner table of this group */
+    join_tab->last_inner->first_unmatched= join_tab; 
+  }
+
   if (!(error=(*join_tab->read_first_record)(join_tab)))
   {
     bool not_exists_optimize= join_tab->table->reginfo.not_exists_optimize;
@@ -5705,17 +6279,83 @@ sub_select(JOIN *join,JOIN_TAB *join_tab,bool end_of_records)
 	join->thd->send_kill_message();
 	return -2;				/* purecov: inspected */
       }
-      join->examined_rows++;
-      join->thd->row_count++;
-      if (!on_expr || on_expr->val_int())
+      if (!select_cond || select_cond->val_int())
       {
-	found=1;
-	if (not_exists_optimize)
-	  break;			// Searching after not null columns
-	if (!select_cond || select_cond->val_int())
-	{
-	  if ((error=(*join_tab->next_select)(join,join_tab+1,0)) < 0)
+        /* 
+          There is no select condition or the attached pushed down
+          condition is true => a match is found.
+	*/
+        bool found= 1;
+	while (join_tab->first_unmatched && found)
+        {
+          /*
+             The while condition is always false if join_tab is not
+             the last inner join table of an outer join operation. 
+	  */ 
+          first_unmatched= join_tab->first_unmatched;
+          /*
+             Mark that a match for current outer table is found.
+             This activates push down conditional predicates attached
+             to the all inner tables of the outer join.
+	  */  
+          first_unmatched->found= 1;
+          for (tab= first_unmatched; tab <= join_tab; tab++)
+          { 
+            /* Check all predicates that has just been activated. */
+            /*
+              Actually all predicates non-guarded by first_unmatched->found
+              will be re-evaluated again. It could be fixed, but, probably,
+              it's not worth doing now.
+	    */ 
+            if (tab->select_cond && !tab->select_cond->val_int())
+            {
+              /* The condition attached to table tab is false */
+              if (tab == join_tab)
+                found= 0;
+              else
+              {
+                /*
+                  Set a return point if rejected predicate is attached 
+                  not to the last table of the current nest level.
+		*/
+                join->return_tab= tab;
+                return 0;
+              }
+            }
+          }
+          /* 
+             Check whether join_tab is not the last inner table
+             for another embedding outer join.
+          */
+          if ((first_unmatched= first_unmatched->first_upper) &&
+              first_unmatched->last_inner != join_tab)
+            first_unmatched= 0;
+          join_tab->first_unmatched= first_unmatched;
+        }
+        
+        /*
+           It was not just a return to lower loop level when one
+           of the newly activated predicates is evaluated as false 
+           (See above join->return_tab= tab).
+	*/             
+        join->examined_rows++;
+        join->thd->row_count++;
+              
+        if (found)
+        {
+          if (not_exists_optimize)
+            break;
+          /* A match from join_tab is found for the current partial join. */
+	  if ((error=(*join_tab->next_select)(join, join_tab+1, 0)) < 0)
 	    return error;
+          if (join->return_tab)
+          {
+            /* We are just returning to the nest level of join->return_tab. */
+            if (join->return_tab != join_tab)
+              return 0;
+            /* The return point is reached */
+	    join->return_tab= 0;
+          }
 	  /*
 	    Test if this was a SELECT DISTINCT query on a table that
 	    was not in the field list;  In this case we can abort if
@@ -5725,22 +6365,78 @@ sub_select(JOIN *join,JOIN_TAB *join_tab,bool end_of_records)
 	    return 0;
 	}
 	else
-	  info->file->unlock_row();
+	  info->file->unlock_row();    
+      }
+      else
+      {
+        /* 
+           The condition pushed down to the table join_tab rejects all rows 
+           with the beginning coinciding with the current partial join.
+	*/ 
+        join->examined_rows++;
+        join->thd->row_count++;
       }
+ 
     } while (!(error=info->read_record(info)) && !(*report_error));
   }
   if (error > 0 || (*report_error))				// Fatal error
     return -1;
 
-  if (!found && on_expr)
-  {						// OUTER JOIN
-    restore_record(join_tab->table,default_values);		// Make empty record
-    mark_as_null_row(join_tab->table);		// For group by without error
-    if (!select_cond || select_cond->val_int())
-    {
-      if ((error=(*join_tab->next_select)(join,join_tab+1,0)) < 0)
-	return error;				/* purecov: inspected */
+  if (join_tab->last_inner && !join_tab->found)
+  {        
+    /* 
+      The table join_tab is the first inner table of a outer join operation
+      and no matches has been found for the current outer row.
+    */
+    JOIN_TAB *last_inner_tab= join_tab->last_inner;
+    for ( ; join_tab <= last_inner_tab ; join_tab++)
+    { 
+      /* Change the the values of guard predicate variables. */
+      join_tab->found= 1;
+      join_tab->not_null_compl= 0;
+      /* The outer row is complemented by nulls for each inner tables */
+      restore_record(join_tab->table,default_values);  // Make empty record
+      mark_as_null_row(join_tab->table);       // For group by without error
+      select_cond= join_tab->select_cond;
+      /* Check all attached conditions for inner table rows. */
+      if (select_cond && !select_cond->val_int())
+        return 0;
+    }    
+    join_tab--;
+    /* 
+       The row complemented by nulls might be the first row
+       of embedding outer joins. 
+       If so, perform the same actions as in the code 
+       for the first regular outer join row above.
+    */
+    for ( ; ; )
+    {
+      first_unmatched= join_tab->first_unmatched;
+      if ((first_unmatched= first_unmatched->first_upper) &&
+          first_unmatched->last_inner != join_tab)
+        first_unmatched= 0;
+      join_tab->first_unmatched= first_unmatched;
+      if (!first_unmatched)
+        break;
+      first_unmatched->found= 1;
+      for (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)
+      {  
+        if (tab->select_cond && !tab->select_cond->val_int())
+        {
+          if (tab != join_tab)
+            join->return_tab= tab;
+          return 0;
+        }
+      }
     }
+    /*
+      The row complemented by nulls satisfies all conditions
+      attached to inner tables.
+      Send the row complemented by nulls to be joined with the 
+      remaining tables.
+    */     
+    if ((error=(*join_tab->next_select)(join, join_tab+1 ,0)) < 0)
+      return error;
   }
   return 0;
 }
@@ -7217,6 +7913,8 @@ create_sort_index(THD *thd, JOIN *join, ORDER *order,
   delete select;				// filesort did select
   tab->select=0;
   tab->select_cond=0;
+  tab->last_inner= 0;
+  tab->first_unmatched= 0;
   tab->type=JT_ALL;				// Read with normal read_record
   tab->read_first_record= join_init_read_record;
   tab->join->examined_rows+=examined_rows;
@@ -9296,11 +9994,35 @@ void st_select_lex::print(THD *thd, String *str)
   if (table_list.elements)
   {
     str->append(" from ", 6);
-    Item *next_on= 0;
     for (TABLE_LIST *table= (TABLE_LIST *) table_list.first;
 	 table;
 	 table= table->next)
     {
+      TABLE_LIST *embedded=table;
+      TABLE_LIST *embedding= table->embedding;
+      while (embedding)
+      {
+        TABLE_LIST *next;
+        NESTED_JOIN *nested_join= table->embedding->nested_join;
+        List_iterator_fast<TABLE_LIST> it(nested_join->join_list);
+        TABLE_LIST *tab= it++;
+        while ((next= it++))
+          tab= next;
+        if (tab != embedded)
+          break;
+        str->append('(');
+	if (embedded->outer_join & JOIN_TYPE_RIGHT)
+	  str->append(" right join ", 12);
+	else if (embedded->outer_join & JOIN_TYPE_LEFT)
+	  str->append(" left join ", 11);
+	else if (embedded->straight)
+	  str->append(" straight_join ", 15);
+	else
+	  str->append(" join ", 6);
+        embedded= embedding;
+        embedding= embedding->embedding;
+      }
+
       if (table->derived)
       {
 	str->append('(');
@@ -9320,35 +10042,43 @@ void st_select_lex::print(THD *thd, String *str)
 	}
       }
 
-      if (table->on_expr && ((table->outer_join & JOIN_TYPE_LEFT) ||
-			     !(table->outer_join & JOIN_TYPE_RIGHT)))
-	next_on= table->on_expr;
-
-      if (next_on)
+      if (table->on_expr)
       {
 	str->append(" on(", 4);
-	next_on->print(str);
+	table->on_expr->print(str);
 	str->append(')');
-	next_on= 0;
       }
 
       TABLE_LIST *next_table;
       if ((next_table= table->next))
       {
-	if (table->outer_join & JOIN_TYPE_RIGHT)
-	{
+	if (next_table->outer_join & JOIN_TYPE_RIGHT)
 	  str->append(" right join ", 12);
-	  if (!(table->outer_join & JOIN_TYPE_LEFT) &&
-	      table->on_expr)
-	    next_on= table->on_expr;	    
-	}
-	else if (next_table->straight)
-	  str->append(" straight_join ", 15);
 	else if (next_table->outer_join & JOIN_TYPE_LEFT)
 	  str->append(" left join ", 11);
+	else if (next_table->straight)
+	  str->append(" straight_join ", 15);
 	else
 	  str->append(" join ", 6);
       }
+
+      embedded=table;
+      embedding= table->embedding;
+      while (embedding)
+      {
+        NESTED_JOIN *nested_join= table->embedding->nested_join;
+        if (nested_join->join_list.head() != embedded)
+          break;
+        str->append(')');
+        if (embedding->on_expr)
+        {
+	  str->append(" on(", 4);
+	  embedding->on_expr->print(str);
+	  str->append(')');
+        }
+        embedded= embedding;
+        embedding= embedding->embedding;
+      }
     }
   }
 
diff --git a/sql/sql_select.h b/sql/sql_select.h
index 9bba4e9318e..09c741030af 100644
--- a/sql/sql_select.h
+++ b/sql/sql_select.h
@@ -73,7 +73,6 @@ typedef struct st_join_cache {
 /*
 ** The structs which holds the join connections and join states
 */
-
 enum join_type { JT_UNKNOWN,JT_SYSTEM,JT_CONST,JT_EQ_REF,JT_REF,JT_MAYBE_REF,
 		 JT_ALL, JT_RANGE, JT_NEXT, JT_FT, JT_REF_OR_NULL,
 		 JT_UNIQUE_SUBQUERY, JT_INDEX_SUBQUERY, JT_INDEX_MERGE};
@@ -86,7 +85,13 @@ typedef struct st_join_table {
   SQL_SELECT	*select;
   COND		*select_cond;
   QUICK_SELECT_I *quick;
-  Item		*on_expr;
+  Item		*on_expr;       /* associated on expression                  */
+  st_join_table *first_inner;   /* first inner table for including outerjoin */
+  bool           found;         /* true after all matches or null complement */
+  bool           not_null_compl;/* true before null complement is added      */
+  st_join_table *last_inner;    /* last table table for embedding outer join */
+  st_join_table *first_upper;  /* first inner table for embedding outer join */
+  st_join_table *first_unmatched; /* used for optimization purposes only     */
   const char	*info;
   byte		*null_ref_key;
   int		(*read_first_record)(struct st_join_table *tab);
@@ -196,8 +201,10 @@ class JOIN :public Sql_alloc
   ORDER *order, *group_list, *proc_param; //hold parameters of mysql_select
   COND *conds;                            // ---"---
   Item *conds_history;                    // store WHERE for explain
-  TABLE_LIST *tables_list;           //hold 'tables' parameter of mysql_selec
+  TABLE_LIST *tables_list;           //hold 'tables' parameter of mysql_select
+  List<TABLE_LIST> *join_list;       // list of joined tables in reverse order
   SQL_SELECT *select;                //created in optimisation phase
+  JOIN_TAB *return_tab;              //used only for outer joins
   Item **ref_pointer_array; //used pointer reference for this select
   // Copy of above to be used with different lists
   Item **items0, **items1, **items2, **items3, **current_ref_pointer_array;
@@ -221,6 +228,7 @@ class JOIN :public Sql_alloc
     table= 0;
     tables= 0;
     const_tables= 0;
+    join_list= 0;
     sort_and_group= 0;
     first_record= 0;
     do_send_rows= 1;
@@ -251,6 +259,7 @@ class JOIN :public Sql_alloc
     fields_list= fields_arg;
     error= 0;
     select= 0;
+    return_tab= 0;
     ref_pointer_array= items0= items1= items2= items3= 0;
     ref_pointer_array_size= 0;
     zero_result_cause= 0;
diff --git a/sql/sql_yacc.yy b/sql/sql_yacc.yy
index a5ec1a20959..f879de93ac6 100644
--- a/sql/sql_yacc.yy
+++ b/sql/sql_yacc.yy
@@ -698,6 +698,7 @@ bool my_yyoverflow(short **a, YYSTYPE **b,int *yystacksize);
 
 %type <table_list>
 	join_table_list  join_table
+        table_factor table_ref
 
 %type <udf>
 	UDF_CHAR_FUNC UDF_FLOAT_FUNC UDF_INT_FUNC
@@ -4192,59 +4193,80 @@ when_list2:
 	    sel->when_list.head()->push_back($5);
 	  };
 
+table_ref:
+        table_factor            { $$=$1; }
+        | join_table            { $$=$1; }
+          { 
+	    LEX *lex= Lex;
+            if (!($$= lex->current_select->nest_last_join(lex->thd)))
+              YYABORT;
+          }     	        
+        ;
+
 join_table_list:
-	'(' join_table_list ')'	{ $$=$2; }
-	| join_table		{ $$=$1; }
-	| join_table_list ',' join_table_list { $$=$3; }
-	| join_table_list normal_join join_table_list { $$=$3; }
-	| join_table_list STRAIGHT_JOIN join_table_list
-	  { $$=$3 ; $1->next->straight=1; }
-	| join_table_list normal_join join_table_list ON expr
+        table_ref { $$=$1; }
+        | join_table_list ',' table_ref { $$=$3; }
+        ;
+
+join_table:
+        table_ref normal_join table_ref { $$=$3; }
+	| table_ref STRAIGHT_JOIN table_factor
+	  { $3->straight=1; $$=$3 ; }
+	| table_ref normal_join table_ref ON expr
 	  { add_join_on($3,$5); $$=$3; }
-	| join_table_list normal_join join_table_list
+	| table_ref normal_join table_ref
 	  USING
 	  {
 	    SELECT_LEX *sel= Select;
-	    sel->db1=$1->db; sel->table1=$1->alias;
-	    sel->db2=$3->db; sel->table2=$3->alias;
+            sel->save_names_for_using_list($1, $3);
 	  }
 	  '(' using_list ')'
 	  { add_join_on($3,$7); $$=$3; }
 
-	| join_table_list LEFT opt_outer JOIN_SYM join_table_list ON expr
+	| table_ref LEFT opt_outer JOIN_SYM table_ref ON expr
 	  { add_join_on($5,$7); $5->outer_join|=JOIN_TYPE_LEFT; $$=$5; }
-	| join_table_list LEFT opt_outer JOIN_SYM join_table_list
+	| table_ref LEFT opt_outer JOIN_SYM table_ref
 	  {
 	    SELECT_LEX *sel= Select;
-	    sel->db1=$1->db; sel->table1=$1->alias;
-	    sel->db2=$5->db; sel->table2=$5->alias;
+            sel->save_names_for_using_list($1, $5);
 	  }
 	  USING '(' using_list ')'
 	  { add_join_on($5,$9); $5->outer_join|=JOIN_TYPE_LEFT; $$=$5; }
-	| join_table_list NATURAL LEFT opt_outer JOIN_SYM join_table_list
+	| table_ref NATURAL LEFT opt_outer JOIN_SYM table_factor
 	  {
-	    add_join_natural($1,$1->next);
-	    $1->next->outer_join|=JOIN_TYPE_LEFT;
+	    add_join_natural($1,$6);
+	    $6->outer_join|=JOIN_TYPE_LEFT;
 	    $$=$6;
 	  }
-	| join_table_list RIGHT opt_outer JOIN_SYM join_table_list ON expr
-	  { add_join_on($1,$7); $1->outer_join|=JOIN_TYPE_RIGHT; $$=$5; }
-	| join_table_list RIGHT opt_outer JOIN_SYM join_table_list
+	| table_ref RIGHT opt_outer JOIN_SYM table_ref ON expr
+          { 
+	    LEX *lex= Lex;
+            if (!($$= lex->current_select->convert_right_join()))
+              YYABORT;
+            add_join_on($$, $7);
+          }
+	| table_ref RIGHT opt_outer JOIN_SYM table_ref
 	  {
 	    SELECT_LEX *sel= Select;
-	    sel->db1=$1->db; sel->table1=$1->alias;
-	    sel->db2=$5->db; sel->table2=$5->alias;
+            sel->save_names_for_using_list($1, $5);
 	  }
 	  USING '(' using_list ')'
-	  { add_join_on($1,$9); $1->outer_join|=JOIN_TYPE_RIGHT; $$=$5; }
-	| join_table_list NATURAL RIGHT opt_outer JOIN_SYM join_table_list
+          { 
+	    LEX *lex= Lex;
+            if (!($$= lex->current_select->convert_right_join()))
+              YYABORT;
+            add_join_on($$, $9);
+          }
+	| table_ref NATURAL RIGHT opt_outer JOIN_SYM table_factor
 	  {
-	    add_join_natural($1->next,$1);
-	    $1->outer_join|=JOIN_TYPE_RIGHT;
-	    $$=$6;
+	    add_join_natural($6,$1);
+	    LEX *lex= Lex;
+            if (!($$= lex->current_select->convert_right_join()))
+              YYABORT;
 	  }
-	| join_table_list NATURAL JOIN_SYM join_table_list
-	  { add_join_natural($1,$1->next); $$=$4; };
+	| table_ref NATURAL JOIN_SYM table_factor
+	  { add_join_natural($1,$4); $$=$4; };
+        
 
 normal_join:
 	JOIN_SYM		{}
@@ -4252,7 +4274,7 @@ normal_join:
 	| CROSS JOIN_SYM	{}
 	;
 
-join_table:
+table_factor:
 	{
 	  SELECT_LEX *sel= Select;
 	  sel->use_index_ptr=sel->ignore_index_ptr=0;
@@ -4268,8 +4290,21 @@ join_table:
 					   sel->get_use_index(),
 					   sel->get_ignore_index())))
 	    YYABORT;
+          sel->add_joined_table($$); 
 	}
-	| '{' ident join_table LEFT OUTER JOIN_SYM join_table ON expr '}'
+        | '('
+          { 
+            LEX *lex= Lex;
+            if (lex->current_select->init_nested_join(lex->thd))
+              YYABORT;
+          }            
+          join_table_list ')'
+          {
+            LEX *lex= Lex;
+            if (!($$= lex->current_select->end_nested_join(lex->thd)))
+              YYABORT;
+          }	
+	| '{' ident table_ref LEFT OUTER JOIN_SYM table_ref ON expr '}'
 	  { add_join_on($7,$9); $7->outer_join|=JOIN_TYPE_LEFT; $$=$7; }
         | '(' SELECT_SYM select_derived ')' opt_table_alias
 	{
@@ -4289,6 +4324,7 @@ join_table:
 	                          (List<String> *)0)))
 
 	    YYABORT;
+          lex->current_select->add_joined_table($$);           
 	};
 
 select_derived:
diff --git a/sql/table.h b/sql/table.h
index ba7349d33fc..4f4ab42f3e9 100644
--- a/sql/table.h
+++ b/sql/table.h
@@ -143,12 +143,8 @@ struct st_table {
   uint		quick_key_parts[MAX_KEY];
   key_part_map  const_key_parts[MAX_KEY];
   ulong		query_id;
-
-  union					/* Temporary variables */
-  {
-    uint        temp_pool_slot;		/* Used by intern temp tables */
-    struct st_table_list *pos_in_table_list;
-  };
+  uint        temp_pool_slot;		/* Used by intern temp tables */
+  struct st_table_list *pos_in_table_list;/* Element referring to this table */
   /* number of select if it is derived table */
   uint          derived_select_number;
   THD		*in_use;		/* Which thread uses this */
@@ -178,10 +174,24 @@ typedef struct st_table_list
   uint32        db_length, real_name_length;
   bool		straight;		/* optimize with prev table */
   bool          updating;               /* for replicate-do/ignore table */
-  bool		force_index;		/* Prefer index over table scan */
-  bool          ignore_leaves;          /* Preload only non-leaf nodes */
+  bool		force_index;		/* prefer index over table scan */
+  bool          ignore_leaves;          /* preload only non-leaf nodes */
+  table_map     dep_tables;             /* tables the table depends on      */
+  table_map     on_expr_dep_tables;     /* tables on expression depends on  */ 
+  struct st_nested_join *nested_join;   /* if the element is a nested join  */
+  st_table_list *embedding;             /* nested join containing the table */
+  List<struct st_table_list> *join_list;/* join list the table belongs to   */ 
 } TABLE_LIST;
 
+typedef struct st_nested_join
+{
+  List<TABLE_LIST>  join_list;       /* list of elements in the nested join */
+  table_map         used_tables;     /* bitmap of tables in the nested join */
+  table_map         not_null_tables; /* tables that rejects nulls           */ 
+  struct st_join_table *first_nested;/* the first nested table in the plan  */
+  uint              counter;         /* to count tables in the nested join  */
+} NESTED_JOIN;
+  
 typedef struct st_changed_table_list
 {
   struct	st_changed_table_list *next;
@@ -189,8 +199,7 @@ typedef struct st_changed_table_list
   uint32        key_length;
 } CHANGED_TABLE_LIST;
 
-typedef struct st_open_table_list
-{
+typedef struct st_open_table_list{
   struct st_open_table_list *next;
   char	*db,*table;
   uint32 in_use,locked;