List:Commits« Previous MessageNext Message »
From:Sergey Petrunia Date:October 26 2006 8:49pm
Subject:bk commit into 4.1 tree (sergefp:1.2534) BUG#8804
View as plain text  
Below is the list of changes that have just been committed into a local
4.1 repository of psergey. When psergey does a push these changes will
be propagated to the main repository and, within 24 hours after the
push, to the public repository.
For information on how to access the public repository
see http://dev.mysql.com/doc/mysql/en/installing-source-tree.html

ChangeSet@stripped, 2006-10-27 00:49:23+04:00, sergefp@stripped +9 -0
  BUG#8804: wrong result for "NULL IN (SELECT ...)" 
  Add two execution strategies for "NULL IN (SELECT ...)" : 
   = replace index lookups with ref table scans
   = replace pushed-down-predicate-based ref accesses with full table scans.
    

  sql/item_cmpfunc.cc@stripped, 2006-10-27 00:40:33+04:00, sergefp@stripped +13 -4
    BUG#8804: wrong result for "NULL IN (SELECT ...)" :
    - Make Item_in_optimizer::val_int() execute NULL IN (...) in special way:
      = enable/disable pushed-down conditions
      = cache results of "NULL IN (SELECT ...)" when the select is not correlated.

  sql/item_cmpfunc.h@stripped, 2006-10-27 00:40:33+04:00, sergefp@stripped +27 -20
    BUG#8804: wrong result for "NULL IN (SELECT ...)" :
    - Make Item_in_optimizer::val_int() execute NULL IN (...) in special way:
      = enable/disable pushed-down conditions
      = cache results of "NULL IN (SELECT ...)" when the select is not correlated.
    - Added comments

  sql/item_subselect.cc@stripped, 2006-10-27 00:40:33+04:00, sergefp@stripped +217 -34
    BUG#8804: wrong result for "NULL IN (SELECT ...)" :
    - Change subquery's exec() to exec(bool), to allow second kind of 
      execution - without pushed-down predicates.
    - Implement the second kind of execution for
       = [unique_]index_subquery (do full table scan instead of index lookup)
       = naive execution (just enable/disable predicates)
       = join with pushed-down predicates used for ref[_or_null] accesses
         (change those accesses to full table scans)

  sql/item_subselect.h@stripped, 2006-10-27 00:40:33+04:00, sergefp@stripped +49 -14
    BUG#8804: wrong result for "NULL IN (SELECT ...)" :
    - Change subquery's exec() to exec(bool), to allow second kind of 
      execution - without pushed-down predicates.
    - Implement the second kind of execution for
       = [unique_]index_subquery (do full table scan instead of index lookup)
       = naive execution (just enable/disable predicates)
       = join with pushed-down predicates used for ref[_or_null] accesses
         (change those accesses to full table scans)

  sql/records.cc@stripped, 2006-10-27 00:40:33+04:00, sergefp@stripped +3 -2
    BUG#8804: wrong result for "NULL IN (SELECT ...)": 
    - make rr_sequential() non-static

  sql/sql_lex.cc@stripped, 2006-10-27 00:40:33+04:00, sergefp@stripped +2 -1
    BUG#8804: wrong result for "NULL IN (SELECT ...)" :
    - Add/support st_select_lex::is_correlated flag

  sql/sql_lex.h@stripped, 2006-10-27 00:40:33+04:00, sergefp@stripped +3 -1
    BUG#8804: wrong result for "NULL IN (SELECT ...)" :
    - Add/support st_select_lex::is_correlated flag

  sql/sql_select.cc@stripped, 2006-10-27 00:40:33+04:00, sergefp@stripped +68 -14
    BUG#8804: wrong result for "NULL IN (SELECT ...)" :
    - Make the ref-optimizer to produce KEYUSE::outer_ref to mark the 
      ref accesses that are based on pushed-down outer-select references.
    - Add 'bool null_key' to store_key-derived classes. 

  sql/sql_select.h@stripped, 2006-10-27 00:40:33+04:00, sergefp@stripped +8 -3
    BUG#8804: wrong result for "NULL IN (SELECT ...)" :
    - Add KEYUSE::outer_ref to distinguish outer-select-reference based accesses.
    - Add 'bool null_key' to store_key-derived classes. 

# This is a BitKeeper patch.  What follows are the unified diffs for the
# set of deltas contained in the patch.  The rest of the patch, the part
# that BitKeeper cares about, is below these diffs.
# User:	sergefp
# Host:	pylon.mylan
# Root:	/home/psergey/mysql-4.1-bug8804-review-clean

--- 1.217/sql/item_cmpfunc.cc	2006-10-27 00:49:26 +04:00
+++ 1.218/sql/item_cmpfunc.cc	2006-10-27 00:49:26 +04:00
@@ -697,10 +697,19 @@
         We disable the predicates we've pushed down into subselect, run the
         subselect and see if it has produced any rows.
       */
-      ((Item_in_subselect*)args[1])->enable_pushed_conds= FALSE;
-      longlong tmp= args[1]->val_int_result();
-      null_value= !((Item_in_subselect*)args[1])->engine->no_rows();
-      ((Item_in_subselect*)args[1])->enable_pushed_conds= TRUE;
+      if (!((Item_in_subselect*)args[1])->is_correlated &&
+          result_for_null_param != UNKNOWN)
+      {
+        null_value= result_for_null_param;
+      }
+      else
+      {
+        ((Item_in_subselect*)args[1])->enable_pushed_conds= FALSE;
+        longlong tmp= args[1]->val_int_result();
+        result_for_null_param= null_value= 
+          !((Item_in_subselect*)args[1])->engine->no_rows();
+        ((Item_in_subselect*)args[1])->enable_pushed_conds= TRUE;
+      }
     }
     return 0;
   }

--- 1.120/sql/item_cmpfunc.h	2006-10-27 00:49:26 +04:00
+++ 1.121/sql/item_cmpfunc.h	2006-10-27 00:49:26 +04:00
@@ -133,35 +133,42 @@
 class Item_cache;
 
 
+/*
+  Item_in_optimizer if a function of (left_expr, Item_in_subselect(...))
+
+  
+  Item_in_optimizer is used to wrap an instance of Item_in_subselect. This
+  class does the following:
+   - Evaluates the left expression and store it in Item_cache_* object (it
+     is not clear why we do this)
+   
+   - Shortcut the evaluation of "NULL IN (...)" to NULL in the cases where we
+     don't care if the result is NULL or FALSE.
+
+  psergey's note: it is not very clear why the above functionality should be
+  implemented in this separate class.
+*/
+#define UNKNOWN ((my_bool)-1)
 class Item_in_optimizer: public Item_bool_func
 {
 protected:
   Item_cache *cache;
   bool save_cache;
+  /* 
+    For uncorrelated subqueries: the value of NULL IN (SELECT ...)
+      UNKNOWN - not yet evaluated
+      FALSE   - result is FLSE.
+      TRUE    - result is NULL
+  */
+  my_bool result_for_null_param;
 public:
   Item_in_optimizer(Item *a, Item_in_subselect *b):
-    Item_bool_func(a, my_reinterpret_cast(Item *)(b)), cache(0), save_cache(0)
+    Item_bool_func(a, my_reinterpret_cast(Item *)(b)), cache(0),
+    save_cache(0), result_for_null_param(UNKNOWN)
   {}
   bool fix_fields(THD *, struct st_table_list *, Item **);
   bool fix_left(THD *thd, struct st_table_list *tables, Item **ref);
   bool is_null();
-  /*
-    Item_in_optimizer item is special boolean function. On value request 
-    (one of val, val_int or val_str methods) it evaluate left expression 
-    of IN by storing it value in cache item (one of Item_cache* items), 
-    then it test cache is it NULL. If left expression (cache) is NULL then
-    Item_in_optimizer return NULL, else it evaluate Item_in_subselect.
-
-    psergey: and the above is not correct. NULL IN (SELECT * FROM empty) can
-    evaluate to FALSE in some cases:
-
-    psergey-todo: fix comments here, try to rename. This 'optimizer' doesnt
-    ever attempt to optimize anything!
-
-    This is used for:
-     - direct-execution subqueries.
-     - index-lookup-based subqs.
-  */
   longlong val_int();
   void cleanup();
   const char *func_name() const { return "<in_optimizer>"; }
@@ -909,8 +916,8 @@
 class Item_in_subselect;
 
 /* 
-  psergey: this is like IS NOT NULL but it also remembers if it ever has
- * encountered a NULL... 
+  This is like IS NOT NULL but it also remembers if it ever has
+  encountered a NULL.
 */
 class Item_is_not_null_test :public Item_func_isnull
 {

--- 1.32/sql/records.cc	2006-10-27 00:49:26 +04:00
+++ 1.33/sql/records.cc	2006-10-27 00:49:26 +04:00
@@ -20,7 +20,7 @@
 #include "mysql_priv.h"
 
 static int rr_quick(READ_RECORD *info);
-static int rr_sequential(READ_RECORD *info);
+int rr_sequential(READ_RECORD *info);
 static int rr_from_tempfile(READ_RECORD *info);
 static int rr_unpack_from_tempfile(READ_RECORD *info);
 static int rr_unpack_from_buffer(READ_RECORD *info);
@@ -179,6 +179,7 @@
 } /* init_read_record */
 
 
+
 void end_read_record(READ_RECORD *info)
 {                   /* free cache if used */
   if (info->cache)
@@ -284,7 +285,7 @@
 }
 
 
-static int rr_sequential(READ_RECORD *info)
+int rr_sequential(READ_RECORD *info)
 {
   int tmp;
   while ((tmp=info->file->rnd_next(info->record)))

--- 1.155/sql/sql_lex.cc	2006-10-27 00:49:26 +04:00
+++ 1.156/sql/sql_lex.cc	2006-10-27 00:49:26 +04:00
@@ -1094,7 +1094,7 @@
   select_limit= HA_POS_ERROR;
   offset_limit= 0;
   with_sum_func= 0;
-
+  is_correlated= 0;
 }
 
 /*
@@ -1288,6 +1288,7 @@
       SELECT_LEX_UNIT *munit= s->master_unit();
       munit->uncacheable|= UNCACHEABLE_DEPENDENT;
     }
+  is_correlated= TRUE;
 }
 
 bool st_select_lex_node::set_braces(bool value)      { return 1; }

--- 1.190/sql/sql_lex.h	2006-10-27 00:49:26 +04:00
+++ 1.191/sql/sql_lex.h	2006-10-27 00:49:26 +04:00
@@ -406,7 +406,7 @@
   inline bool is_prepared() { return prepared; }
 
   friend void lex_start(THD *thd, uchar *buf, uint length);
-  friend int subselect_union_engine::exec();
+  friend int subselect_union_engine::exec(bool);
 private:
   bool create_total_list_n_last_return(THD *thd, st_lex *lex,
 				       TABLE_LIST ***result);
@@ -470,6 +470,8 @@
     query processing end even if we use temporary table
   */
   bool subquery_in_having;
+  /* TRUE <=> subquery SELECT (not predicate) is correlated */
+  bool is_correlated;
 
   /* 
      SELECT for SELECT command st_select_lex. Used to privent scaning

--- 1.461/sql/sql_select.cc	2006-10-27 00:49:26 +04:00
+++ 1.462/sql/sql_select.cc	2006-10-27 00:49:26 +04:00
@@ -106,8 +106,8 @@
 static int join_read_prev(READ_RECORD *info);
 static int join_ft_read_first(JOIN_TAB *tab);
 static int join_ft_read_next(READ_RECORD *info);
-static int join_read_always_key_or_null(JOIN_TAB *tab);
-static int join_read_next_same_or_null(READ_RECORD *info);
+int join_read_always_key_or_null(JOIN_TAB *tab);
+int join_read_next_same_or_null(READ_RECORD *info);
 static COND *make_cond_for_table(COND *cond,table_map table,
 				 table_map used_table);
 static Item* part_of_refkey(TABLE *form,Field *field);
@@ -462,6 +462,27 @@
 
 
 /*
+  Check if the passed HAVING clause is a clause added by subquery optimizer
+*/
+
+bool is_having_subq_predicates(Item *having)
+{
+  if (having->type() == Item::FUNC_ITEM)
+  {
+    if (((Item_func *) having)->functype() == Item_func::ISNOTNULLTEST_FUNC)
+      return TRUE;
+    if (((Item_func *) having)->functype() == Item_func::TRIG_COND_FUNC)
+    {
+      having= ((Item_func*)having)->arguments()[0];
+      if (((Item_func *) having)->functype() == Item_func::ISNOTNULLTEST_FUNC)
+        return TRUE;
+    }
+    return TRUE;
+  }
+  return FALSE;
+}
+
+/*
   global select optimisation.
   return 0 - success
          1 - error
@@ -846,9 +867,7 @@
       }
     } else if (join_tab[0].type == JT_REF_OR_NULL &&
 	       join_tab[0].ref.items[0]->name == in_left_expr_name &&
-	       having->type() == Item::FUNC_ITEM &&
-	       ((Item_func *) having)->functype() ==
-	       Item_func::ISNOTNULLTEST_FUNC)
+               is_having_subq_predicates(having))
     {
       join_tab[0].type= JT_INDEX_SUBQUERY;
       error= 0;
@@ -2101,6 +2120,9 @@
     when val IS NULL.
   */
   bool          null_rejecting; 
+
+  /* TRUE<=> This ref access is an outer subquery reference access */
+  bool          outer_ref;
 } KEY_FIELD;
 
 /* Values in optimize */
@@ -2352,6 +2374,7 @@
   (*key_fields)->null_rejecting= ((cond->functype() == Item_func::EQ_FUNC) &&
                                  ((*value)->type() == Item::FIELD_ITEM) &&
                                   ((Item_field*)*value)->field->maybe_null());
+  (*key_fields)->outer_ref=      FALSE;
   (*key_fields)++;
 }
 
@@ -2366,9 +2389,10 @@
       usable_tables   Value to pass to add_key_field
 */
 static void
-add_key_fields(KEY_FIELD **key_fields,uint *and_level,
+add_key_fields(JOIN *join, KEY_FIELD **key_fields,uint *and_level,
 	       COND *cond, table_map usable_tables)
 {
+
   if (cond->type() == Item_func::COND_ITEM)
   {
     List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
@@ -2378,28 +2402,50 @@
     {
       Item *item;
       while ((item=li++))
-	add_key_fields(key_fields,and_level,item,usable_tables);
+	add_key_fields(join, key_fields,and_level,item,usable_tables);
       for (; org_key_fields != *key_fields ; org_key_fields++)
 	org_key_fields->level= *and_level;
     }
     else
     {
       (*and_level)++;
-      add_key_fields(key_fields,and_level,li++,usable_tables);
+      add_key_fields(join, key_fields,and_level,li++,usable_tables);
       Item *item;
       while ((item=li++))
       {
 	KEY_FIELD *start_key_fields= *key_fields;
 	(*and_level)++;
-	add_key_fields(key_fields,and_level,item,usable_tables);
+	add_key_fields(join, key_fields,and_level,item,usable_tables);
 	*key_fields=merge_key_fields(org_key_fields,start_key_fields,
 				     *key_fields,++(*and_level));
       }
     }
     return;
   }
-  /* If item is of type 'field op field/constant' add it to key_fields */
 
+  /* 
+    Subquery optimization: check if the encountered condition is one
+    added by condition push down into subquery.
+  */
+  {
+    if (cond->type() == Item::FUNC_ITEM &&
+        ((Item_func*)cond)->functype() == Item_func::TRIG_COND_FUNC)
+    {
+      cond= ((Item_func*)cond)->arguments()[0];
+      if (!join->group_list && !join->order &&
+          join->unit->item && 
+          join->unit->item->substype() == Item_subselect::IN_SUBS &&
+          !join->unit->first_select()->next_select())
+      {
+        add_key_fields(join, key_fields, and_level, cond, usable_tables);
+        // Indicate that this ref access candidate is for subquery lookup:
+        (*key_fields)[-1].outer_ref= TRUE;
+      }
+      return;
+    }
+  }
+
+  /* If item is of type 'field op field/constant' add it to key_fields */
   if (cond->type() != Item::FUNC_ITEM)
     return;
   Item_func *cond_func= (Item_func*) cond;
@@ -2505,6 +2551,7 @@
 	  keyuse.used_tables=key_field->val->used_tables();
 	  keyuse.optimize= key_field->optimize & KEY_OPTIMIZE_REF_OR_NULL;
           keyuse.null_rejecting= key_field->null_rejecting;
+          keyuse.outer_ref= key_field->outer_ref;
 	  VOID(insert_dynamic(keyuse_array,(gptr) &keyuse));
 	}
       }
@@ -2634,7 +2681,7 @@
     return TRUE;
   if (cond)
   {
-    add_key_fields(&end,&and_level,cond,normal_tables);
+    add_key_fields(join_tab->join, &end,&and_level,cond,normal_tables);
     for (; field != end ; field++)
     {
       add_key_part(keyuse,field);
@@ -2648,7 +2695,7 @@
   {
     if (join_tab[i].on_expr)
     {
-      add_key_fields(&end,&and_level,join_tab[i].on_expr,
+      add_key_fields(join_tab->join, &end,&and_level,join_tab[i].on_expr,
 		     join_tab[i].table->map);
     }
   }
@@ -6592,6 +6639,13 @@
 }
 
 
+int rr_sequential(READ_RECORD *info);
+int init_read_record_seq(JOIN_TAB *tab)
+{
+  tab->read_record.read_record= rr_sequential;
+  return tab->read_record.file->ha_rnd_init(1);
+}
+
 static int
 test_if_quick_select(JOIN_TAB *tab)
 {
@@ -6720,7 +6774,7 @@
   Reading of key with key reference and one part that may be NULL
 */
 
-static int
+int
 join_read_always_key_or_null(JOIN_TAB *tab)
 {
   int res;
@@ -6736,7 +6790,7 @@
 }
 
 
-static int
+int
 join_read_next_same_or_null(READ_RECORD *info)
 {
   int error;

--- 1.81/sql/sql_select.h	2006-10-27 00:49:26 +04:00
+++ 1.82/sql/sql_select.h	2006-10-27 00:49:26 +04:00
@@ -36,6 +36,8 @@
     satisfied if val has NULL 'value'.
   */
   bool null_rejecting;
+  /* TRUE<=> This ref access is an outer subquery reference access */
+  bool outer_ref;
 } KEYUSE;
 
 class store_key;
@@ -363,10 +365,11 @@
   Field *to_field;				// Store data here
   char *null_ptr;
   char err;
- public:
+public:
+  bool null_key; /* TRUE <=> the value of the key has a null part */
   enum store_key_result { STORE_KEY_OK, STORE_KEY_FATAL, STORE_KEY_CONV };
   store_key(THD *thd, Field *field_arg, char *ptr, char *null, uint length)
-    :null_ptr(null),err(0)
+    :null_ptr(null), err(0), null_key(0)
   {
     if (field_arg->type() == FIELD_TYPE_BLOB)
       to_field=new Field_varstring(ptr, length, (uchar*) null, 1, 
@@ -404,6 +407,7 @@
   enum store_key_result copy()
   {
     copy_field.do_copy(&copy_field);
+    null_key= to_field->is_null();
     return err != 0 ? STORE_KEY_FATAL : STORE_KEY_OK;
   }
   const char *name() const { return field_name; }
@@ -424,8 +428,8 @@
   enum store_key_result copy()
   {
     int res= item->save_in_field(to_field, 1);
+    null_key= to_field->is_null() || item->is_null();
     return (err != 0 || res > 2 ? STORE_KEY_FATAL : (store_key_result) res); 
-	                 
   }
   const char *name() const { return "func"; }
 };
@@ -455,6 +459,7 @@
           err= res;
       }
     }
+    null_key= to_field->is_null() || item->null_value;
     return (err > 2 ?  STORE_KEY_FATAL : (store_key_result) err);
   }
   const char *name() const { return "const"; }

--- 1.146/sql/item_subselect.cc	2006-10-27 00:49:26 +04:00
+++ 1.147/sql/item_subselect.cc	2006-10-27 00:49:26 +04:00
@@ -191,7 +191,7 @@
   return res;
 }
 
-bool Item_subselect::exec()
+bool Item_subselect::exec(bool full_scan)
 {
   int res;
   MEM_ROOT *old_root= thd->mem_root;
@@ -201,13 +201,13 @@
     mem root
   */
   thd->mem_root= &thd->main_mem_root;
-  res= engine->exec();
+  res= engine->exec(full_scan);
   thd->mem_root= old_root;
 
   if (engine_changed)
   {
     engine_changed= 0;
-    return exec();
+    return exec(full_scan);
   }
   return (res);
 }
@@ -440,13 +440,13 @@
 
 void Item_singlerow_subselect::bring_value()
 {
-  exec();
+  exec(TRUE);
 }
 
 double Item_singlerow_subselect::val()
 {
   DBUG_ASSERT(fixed == 1);
-  if (!exec() && !value->null_value)
+  if (!exec(TRUE) && !value->null_value)
   {
     null_value= 0;
     return value->val();
@@ -461,7 +461,7 @@
 longlong Item_singlerow_subselect::val_int()
 {
   DBUG_ASSERT(fixed == 1);
-  if (!exec() && !value->null_value)
+  if (!exec(TRUE) && !value->null_value)
   {
     null_value= 0;
     return value->val_int();
@@ -475,7 +475,7 @@
 
 String *Item_singlerow_subselect::val_str (String *str)
 {
-  if (!exec() && !value->null_value)
+  if (!exec(TRUE) && !value->null_value)
   {
     null_value= 0;
     return value->val_str(str);
@@ -527,7 +527,8 @@
 
 Item_in_subselect::Item_in_subselect(Item * left_exp,
 				     st_select_lex *select_lex):
-  Item_exists_subselect(), optimizer(0), transformed(0), upper_item(0)
+  Item_exists_subselect(), optimizer(0), transformed(0),
+  enable_pushed_conds(TRUE), upper_item(0)
 {
   DBUG_ENTER("Item_in_subselect::Item_in_subselect");
   left_expr= left_exp;
@@ -538,6 +539,7 @@
   reset();
   //if test_limit will fail then error will be reported to client
   test_limit(select_lex->master_unit());
+  is_correlated= select_lex->is_correlated;
   DBUG_VOID_RETURN;
 }
 
@@ -570,7 +572,7 @@
 double Item_exists_subselect::val()
 {
   DBUG_ASSERT(fixed == 1);
-  if (exec())
+  if (exec(TRUE))
   {
     reset();
     return 0;
@@ -581,7 +583,7 @@
 longlong Item_exists_subselect::val_int()
 {
   DBUG_ASSERT(fixed == 1);
-  if (exec())
+  if (exec(TRUE))
   {
     reset();
     return 0;
@@ -592,7 +594,7 @@
 String *Item_exists_subselect::val_str(String *str)
 {
   DBUG_ASSERT(fixed == 1);
-  if (exec())
+  if (exec(TRUE))
   {
     reset();
     return 0;
@@ -611,7 +613,7 @@
   DBUG_ASSERT(0);
   DBUG_ASSERT(fixed == 1);
   null_value= 0;
-  if (exec())
+  if (exec(!enable_pushed_conds))
   {
     reset();
     null_value= 1;
@@ -627,7 +629,7 @@
 {
   DBUG_ASSERT(fixed == 1);
   null_value= 0;
-  if (exec())
+  if (exec(!enable_pushed_conds))
   {
     reset();
     null_value= 1;
@@ -648,7 +650,7 @@
   DBUG_ASSERT(0);
   DBUG_ASSERT(fixed == 1);
   null_value= 0;
-  if (exec())
+  if (exec(!enable_pushed_conds))
   {
     reset();
     null_value= 1;
@@ -797,8 +799,12 @@
   item= (Item*) select_lex->item_list.head();
   /*
     Add the left part of a subselect to a WHERE or HAVING clause of
-    the right part, e.g. SELECT 1 IN (SELECT a FROM t1)  =>
-    SELECT Item_in_optimizer(1, SELECT a FROM t1 WHERE a=1)
+    the right part, e.g. 
+    
+       SELECT 1 IN (SELECT a FROM t1)  =>
+       
+       SELECT Item_in_optimizer(1, SELECT a FROM t1 WHERE a=1)
+       
     HAVING is used only if the right part contains a SUM function, a GROUP
     BY or a HAVING clause.
   */
@@ -857,6 +863,12 @@
 	  DBUG_RETURN(RES_ERROR);
 	}
 	select_lex->having_fix_field= 0;
+        /* 
+          NOTE: It is important that we add this "IS NULL" here, even when
+          orig_item can't be NULL. This is needed so that this predicate is
+          only used by ref-analyzer (and, e.g. not used in const
+          propagation)
+        */
 	item= new Item_cond_or(item, new Item_func_isnull(orig_item));
         item= new Item_func_trig_cond(item, &enable_pushed_conds);
       }
@@ -1083,6 +1095,8 @@
 
       where_item= and_items(where_item, item);
     }
+    if (where_item)
+      where_item= new Item_func_trig_cond(where_item, &enable_pushed_conds);
     /*
       AND can't be changed during fix_fields()
       we can assign select_lex->where here, and pass 0 as last
@@ -1096,6 +1110,8 @@
   if (having_item)
   {
     bool res;
+    having_item= new Item_func_trig_cond(having_item, &enable_pushed_conds);
+
     select_lex->having= join->having= and_items(join->having, having_item);
     select_lex->having->top_level_item();
     /*
@@ -1434,7 +1450,11 @@
   DBUG_ASSERT(0);
 }
 
-int subselect_single_select_engine::exec()
+int  init_read_record_seq(JOIN_TAB *tab);
+int join_read_always_key_or_null(JOIN_TAB *tab);
+int join_read_next_same_or_null(READ_RECORD *info);
+
+int subselect_single_select_engine::exec(bool full_scan)
 {
   DBUG_ENTER("subselect_single_select_engine::exec");
   char const *save_where= join->thd->where;
@@ -1469,7 +1489,37 @@
   if (!executed)
   {
     item->reset_value_registration();
+    if (full_scan)
+    {
+      for (uint i=join->const_tables ; i < join->tables ; i++)
+      {
+        JOIN_TAB *tab=join->join_tab+i;
+        if (tab->keyuse && tab->keyuse->outer_ref)
+        {
+          tab->read_first_record= init_read_record_seq;
+          tab->read_record.record= tab->table->record[0];
+          tab->read_record.thd= join->thd;
+          tab->read_record.ref_length= tab->table->file->ref_length;
+        }
+      }
+    }
+    
     join->exec();
+
+    if (full_scan)
+    {
+      for (uint i=join->const_tables ; i < join->tables ; i++)
+      {
+        JOIN_TAB *tab=join->join_tab+i;
+        if (tab->keyuse && tab->keyuse->outer_ref)
+        {
+          tab->read_record.record= 0;
+          tab->read_record.ref_length= 0;
+          tab->read_first_record= join_read_always_key_or_null;
+          tab->read_record.read_record= join_read_next_same_or_null;
+        }
+      }
+    }
     executed= 1;
     join->thd->where= save_where;
     join->thd->lex->current_select= save_select;
@@ -1480,28 +1530,154 @@
   DBUG_RETURN(0);
 }
 
-int subselect_union_engine::exec()
+int subselect_union_engine::exec(bool full_scan)
 {
   char const *save_where= unit->thd->where;
+  /* 
+    Ignore the full_scan parameter: the pushed down predicates are only used
+    for filtering, and the caller has disabled that if necessary.
+  */
   int res= unit->exec();
   unit->thd->where= save_where;
   return res;
 }
 
 
-int subselect_uniquesubquery_engine::exec()
+/*
+  Search for at least on row satisfying select condition
+
+  SYNOPSIS
+    subselect_uniquesubquery_engine::scan_table()
+
+  DESCRIPTION
+    Scan the table using sequential access until we find at least one row
+    satisfying select condition. If the subquery is uncorrelated cache the
+    result and use it on the next call.
+
+  RETURN
+    FALSE - ok
+    TRUE  - an error occured while scanning
+*/
+
+int subselect_uniquesubquery_engine::scan_table()
 {
-  DBUG_ENTER("subselect_uniquesubquery_engine::exec");
   int error;
   TABLE *table= tab->table;
-  for (store_key **copy=tab->ref.key_copy ; *copy ; copy++)
+  DBUG_ENTER("subselect_uniquesubquery_engine::scan_table");
+
+  bool is_uncorrelated= !cond || !(cond->used_tables() & OUTER_REF_TABLE_BIT);
+
+  if (table->file->inited)
+    table->file->ha_index_end();
+
+  table->file->ha_rnd_init(1);
+  table->file->extra_opt(HA_EXTRA_CACHE,
+                         current_thd->variables.read_buff_size);
+  table->null_row= 0;
+  for (;;)
+  {
+    error=table->file->rnd_next(table->record[0]);
+    if (error && error != HA_ERR_END_OF_FILE)
+    {
+      error= report_error(table, error);
+      break;
+    }
+    /* No more rows */
+    if (table->status)
+      break;
+
+    if (!cond || cond->val_int())
+    {
+      is_empty= FALSE;
+      break;
+    }
+  }
+
+  table->file->ha_rnd_end();
+  DBUG_RETURN(error != 0);
+}
+
+
+/*
+  Copy ref key and check for null parts in it
+
+  SYNOPSIS
+    subselect_uniquesubquery_engine::copy_ref_key()
+
+  DESCRIPTION
+    Copy ref key and check for null parts in it.
+
+  RETURN
+    FALSE - ok, index lookup key without keys copied.
+    TRUE  - an error occured while copying the key
+*/
+
+bool subselect_uniquesubquery_engine::copy_ref_key()
+{
+  DBUG_ENTER("subselect_uniquesubquery_engine::copy_ref_key");
+
+  for (store_key **copy= tab->ref.key_copy ; *copy ; copy++)
   {
-    if ((tab->ref.key_err= (*copy)->copy()) & 1)
+    tab->ref.key_err= (*copy)->copy();
+
+    /*
+      When there is a NULL part in the key we don't need to make index
+      lookup for such key thus we don't need to copy whole key.
+      If we later should do a sequential scan return OK. Fail otherwise.
+
+      See also the comment for the subselect_uniquesubquery_engine::exec()
+      function.
+    */
+    null_keypart= (*copy)->null_key;
+    bool top_level= ((Item_in_subselect *) item)->is_top_level_item();
+    if (null_keypart && !top_level)
+      break;
+    if ((tab->ref.key_err) & 1 || (null_keypart && top_level))
     {
-      table->status= STATUS_NOT_FOUND;
+      tab->table->status= STATUS_NOT_FOUND;
       DBUG_RETURN(1);
     }
   }
+  DBUG_RETURN(0);
+}
+
+
+/*
+  Execute subselect
+
+  SYNOPSIS
+    subselect_uniquesubquery_engine::exec()
+
+  DESCRIPTION
+    Find rows corresponding to the ref key using index access.
+    If some part of the lookup key is NULL, then we're evaluating
+      NULL IN (SELECT ... )
+    This is a special case, we don't need to search for NULL in the table,
+    instead
+      the result value is NULL if select produces empty row set
+      the result value is FALSE otherwise.
+    In some cases (IN subselect is a top level item, i.e.
+    abort_on_null==TRUE) the caller doesn't distinguish between
+    the two possible results thus we just return FALSE. Otherwise we
+    make a full table scan to see if we could find one matching row.
+
+  RETURN
+    FALSE - ok
+    TRUE  - an error occured while scanning
+*/
+
+int subselect_uniquesubquery_engine::exec(bool full_scan)
+{
+  DBUG_ENTER("subselect_uniquesubquery_engine::exec");
+  int error;
+  TABLE *table= tab->table;
+ 
+  /* TODO: change to use of 'full_scan' here? */
+  if (copy_ref_key())
+    DBUG_RETURN(1);
+
+  if (null_keypart)
+    DBUG_RETURN(scan_table());
 
   if (!table->file->inited)
     table->file->ha_index_init(tab->ref.key);
@@ -1531,14 +1707,23 @@
 }
 
 
-int subselect_indexsubquery_engine::exec()
+/*
+  DESCRIPTION
+    Resolve subquery using index lookup(s).
+    First look for specified constant, 
+    If not found and we need to check for NULLs, do that too.
+*/
+
+int subselect_indexsubquery_engine::exec(bool full_scan)
 {
-  DBUG_ENTER("subselect_indexsubselect_engine::exec");
+  DBUG_ENTER("subselect_indexsubquery_engine::exec");
   int error;
-  bool null_finding= 0;
+  bool null_finding= 0; /* This is actually 'searching for NULL' */
   TABLE *table= tab->table;
 
   ((Item_in_subselect *) item)->value= 0;
+  is_empty=1;
+  null_keypart= 0;
 
   if (check_null)
   {
@@ -1547,14 +1732,12 @@
     ((Item_in_subselect *) item)->was_null= 0;
   }
 
-  for (store_key **copy=tab->ref.key_copy ; *copy ; copy++)
-  {
-    if ((tab->ref.key_err= (*copy)->copy()) & 1)
-    {
-      table->status= STATUS_NOT_FOUND;
-      DBUG_RETURN(1);
-    }
-  }
+  /* Copy the ref key and check for nulls... */
+  if (copy_ref_key())
+    DBUG_RETURN(1);
+
+  if (null_keypart)
+    DBUG_RETURN(scan_table());
 
   if (!table->file->inited)
     table->file->ha_index_init(tab->ref.key);

--- 1.64/sql/item_subselect.h	2006-10-27 00:49:26 +04:00
+++ 1.65/sql/item_subselect.h	2006-10-27 00:49:26 +04:00
@@ -93,7 +93,7 @@
     return null_value;
   }
   bool fix_fields(THD *thd, TABLE_LIST *tables, Item **ref);
-  virtual bool exec();
+  virtual bool exec(bool full_scan);
   virtual void fix_length_and_dec();
   table_map used_tables() const;
   bool const_item() const;
@@ -200,7 +200,18 @@
   friend class subselect_indexsubquery_engine;
 };
 
-/* IN subselect */
+
+/*
+  IN subselect: this represents "left_exr IN (SELECT ...)"
+
+  This class has: 
+   - (as a descendant of Item_subselect) a "subquery execution engine" which 
+      allows it to evaluate subqueries.
+   - Transformation methods (todo: more on this).
+
+  This class is not used directly, it is "wrapped" into Item_in_optimizer
+  which provides some small bits of subquery evaluation.
+*/
 
 class Item_in_subselect :public Item_exists_subselect
 {
@@ -216,15 +227,15 @@
   bool abort_on_null;
   bool transformed;
 public:
+  bool is_correlated; /* TRUE <=> The underlying SELECT is correlated */
   /* Used to trigger on/off conditions that were pushed down to subselect */
   bool enable_pushed_conds;
-
   Item_func_not_all *upper_item; // point on NOT/NOP before ALL/SOME subquery
 
   Item_in_subselect(Item * left_expr, st_select_lex *select_lex);
   Item_in_subselect()
     :Item_exists_subselect(), optimizer(0), abort_on_null(0), transformed(0),
-     enable_pushed_conds(TRUE), upper_item(0)
+     is_correlated(FALSE), enable_pushed_conds(TRUE), upper_item(0)
   {}
 
   subs_type substype() { return IN_SUBS; }
@@ -296,7 +307,24 @@
   THD * get_thd() { return thd; }
   virtual int prepare()= 0;
   virtual void fix_length_and_dec(Item_cache** row)= 0;
-  virtual int exec()= 0;
+  /*
+    Execute the engine
+    SYNOPSIS
+      exec()
+        full_scan  FALSE - Pushed-down predicates are in effect, the engine
+                           can use optimizations based on them
+                   TRUE  - Disable pushed-down optimizations
+                   
+    DESCRIPTION
+    
+    RETURN
+      0 - Ok
+      
+      1 - An error, or the engine should be "changed" and ran again (the two
+          cases can be distinguished by examining 
+          Item_subselect::engine_changed in the engine 'owner' item)
+  */
+  virtual int exec(bool full_scan)= 0;
   virtual uint cols()= 0; /* return number of columnss in select */
   virtual uint8 uncacheable()= 0; /* query is uncacheable */
   enum Item_result type() { return res_type; }
@@ -312,11 +340,6 @@
   */
   virtual bool no_rows()
   { 
-    /* 
-      psergey-TODO: when working on fix for BUG#8804, change this to be a
-      pure virtual function. ATM it can't as there are no implementations
-      for index lookup-based engines.
-    */
     DBUG_ASSERT(0); return 1;
   }
 };
@@ -336,7 +359,7 @@
   void cleanup();
   int prepare();
   void fix_length_and_dec(Item_cache** row);
-  int exec();
+  int exec(bool full_scan);
   uint cols();
   uint8 uncacheable();
   void exclude();
@@ -358,7 +381,7 @@
   void cleanup();
   int prepare();
   void fix_length_and_dec(Item_cache** row);
-  int exec();
+  int exec(bool full_scan);
   uint cols();
   uint8 uncacheable();
   void exclude();
@@ -371,11 +394,18 @@
 
 
 struct st_join_table;
+
 class subselect_uniquesubquery_engine: public subselect_engine
 {
 protected:
   st_join_table *tab;
   Item *cond;
+  /* 
+    TRUE<=> last execution produced empty set. Valid only when left
+    expression is NULL.
+  */
+  bool is_empty;
+  bool null_keypart; /* TRUE <=> constructed search tuple has a NULL */
 public:
 
   // constructor can assign THD because it will be called after JOIN::prepare
@@ -389,7 +419,7 @@
   void cleanup();
   int prepare();
   void fix_length_and_dec(Item_cache** row);
-  int exec();
+  int exec(bool full_scan);
   uint cols() { return 1; }
   uint8 uncacheable() { return UNCACHEABLE_DEPENDENT; }
   void exclude();
@@ -397,11 +427,16 @@
   void print (String *str);
   int change_item(Item_subselect *si, select_subselect *result);
   bool no_tables();
+
+  int scan_table();
+  bool copy_ref_key();
+  bool no_rows() { return is_empty; }
 };
 
 
 class subselect_indexsubquery_engine: public subselect_uniquesubquery_engine
 {
+  /* FALSE for 'ref', TRUE for 'ref-or-null'. */
   bool check_null;
 public:
 
@@ -412,6 +447,6 @@
     :subselect_uniquesubquery_engine(thd, tab_arg, subs, where),
      check_null(chk_null)
   {}
-  int exec();
+  int exec(bool full_scan);
   void print (String *str);
 };
Thread
bk commit into 4.1 tree (sergefp:1.2534) BUG#8804Sergey Petrunia26 Oct