MWL#17: Table elimination

- Last fixes

sql/item.cc:
  MWL#17: Table elimination
  - Don't make multiple calls of ::walk(check_column_usage_processor),
    call once and cache the value
sql/item.h:
  MWL#17: Table elimination
  - s/KEYUSE::usable/KEYUSE::type/, more comments
sql/opt_table_elimination.cc:
  MWL#17: Table elimination
  - Don't make multiple calls of ::walk(check_column_usage_processor),
    call once and cache the value
sql/sql_select.cc:
  MWL#17: Table elimination
  - s/KEYUSE::usable/KEYUSE::type/, more comments
sql/sql_select.h:
  MWL#17: Table elimination
  - s/KEYUSE::usable/KEYUSE::type/, more comments
sql/table.h:
  MWL#17: Table elimination
  - Better comments

6 files changed, 139 insertions, 66 deletions

diff --git a/sql/item.cc b/sql/item.cc
index f1511fdf321..a010b98cd40 100644
--- a/sql/item.cc
+++ b/sql/item.cc
@@ -1920,10 +1920,6 @@ bool Item_field::check_column_usage_processor(uchar *arg)
 {
   Field_processor_info* info=(Field_processor_info*)arg;
 
-  /* It is ok if this is a column of an allowed table: */
-  if (used_tables() & ~info->allowed_tables)
-    return FALSE;
-
   if (field->table == info->table)
   {
     /* It is not ok to use columns that are not part of the key of interest: */
@@ -1936,18 +1932,17 @@ bool Item_field::check_column_usage_processor(uchar *arg)
     {
       if (field->field_index == key->key_part[part].field->field_index)
       {
+        if (part == info->forbidden_part)
+          return TRUE;
         info->needed_key_parts |= key_part_map(1) << part;
         break;
       }
     }
     return FALSE;
   }
-
-  /* 
-    We get here when this refers to a table that's neither the table of
-    interest, nor one of the allowed tables. 
-  */
-  return TRUE;
+  else
+    info->used_tables |= this->used_tables();
+  return FALSE;
 }
 
 
diff --git a/sql/item.h b/sql/item.h
index 6f0bf02bdae..0e74c742d99 100644
--- a/sql/item.h
+++ b/sql/item.h
@@ -1018,11 +1018,14 @@ public:
 };
 
 /* Data for Item::check_column_usage_processor */
-typedef struct  
-{
-  table_map allowed_tables;
-  TABLE *table;
-  uint keyno;
+typedef struct 
+{
+  TABLE *table;         /* Table of interest */
+  uint keyno;           /* Index of interest */
+  uint forbidden_part;  /* key part which one is not allowed to refer to */
+  /* [Set by processor] used tables, besides the table of interest */
+  table_map used_tables; 
+  /* [Set by processor] Parts of index of interest that expression refers to */
   uint needed_key_parts;
 } Field_processor_info;
 
diff --git a/sql/opt_table_elimination.cc b/sql/opt_table_elimination.cc
index 4da061d0e60..11868b6160d 100644
--- a/sql/opt_table_elimination.cc
+++ b/sql/opt_table_elimination.cc
@@ -166,9 +166,8 @@ void eliminate_tables(JOIN *join)
   DESCRIPTION
 
   RETURN
-    Number of base tables left after elimination. 0 means everything was
-    eliminated. Tables that belong to the
-    children of this join nest are also counted.
+    Number of children left after elimination. 0 means everything was
+    eliminated.
 
 //    TRUE   The entire join list can be eliminated (caller should remove)
 //    FALSE  Otherwise
@@ -188,7 +187,7 @@ eliminate_tables_for_list(JOIN *join, TABLE **leaves_arr,
   table_map tables_used_on_left= 0;
   TABLE **cur_table= leaves_arr;
   bool children_have_multiple_matches= FALSE;
-  uint base_tables= 0;
+  uint remaining_children= 0;
 
   while ((tbl= it++))
   {
@@ -209,8 +208,9 @@ eliminate_tables_for_list(JOIN *join, TABLE **leaves_arr,
         {
           mark_as_eliminated(join, tbl);
         }
+        else
+          remaining_children++;
         tbl->nested_join->n_tables= n;
-        base_tables += n;
       }
       else
       {
@@ -222,7 +222,7 @@ eliminate_tables_for_list(JOIN *join, TABLE **leaves_arr,
           mark_as_eliminated(join, tbl);
         }
         else 
-          base_tables++;
+          remaining_children++;
       }
       tables_used_on_left |= tbl->on_expr->used_tables();
       children_have_multiple_matches= children_have_multiple_matches ||  
@@ -231,7 +231,7 @@ eliminate_tables_for_list(JOIN *join, TABLE **leaves_arr,
     else
     {
       DBUG_ASSERT(!tbl->nested_join);
-      base_tables++;
+      remaining_children++;
     }
 
     if (tbl->table)
@@ -271,10 +271,10 @@ eliminate_tables_for_list(JOIN *join, TABLE **leaves_arr,
         This join_list can be eliminated. Signal about this to the caller by
         returning number of tables.
       */
-      base_tables= 0;
+      remaining_children= 0;
     }
   }
-  return base_tables;
+  return remaining_children;
 }
 
 
@@ -330,7 +330,7 @@ static bool table_has_one_match(TABLE *table, table_map bound_tables,
       
       do  /* For each keypart and each way to read it */
       {
-        if (keyuse->usable == 1)
+        if (keyuse->type == KEYUSE_USABLE)
         {
           if(!(keyuse->used_tables & ~bound_tables) &&
              !(keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL))
@@ -400,12 +400,56 @@ extra_keyuses_bind_all_keyparts(table_map bound_tables, TABLE *table,
                                 uint n_keyuses, table_map bound_parts)
 {
   /*
-    Current implementation needs some keyparts to be already bound to start
-    inferences: 
+    We need 
+     - some 'unusable' KEYUSE elements to work on
+     - some keyparts to be already bound to start inferences: 
   */
   if (n_keyuses && bound_parts)
   {
-    KEY *keyinfo= table->key_info + key_start->key; 
+    KEY *keyinfo= table->key_info + key_start->key;
+    bool bound_more_parts;
+    do 
+    {
+      bound_more_parts= FALSE;
+      for (KEYUSE *k= key_start; k!=key_end; k++)
+      {
+        if (k->type == KEYUSE_UNKNOWN)
+        {
+          Field_processor_info fp= {table, k->key, k->keypart, 0, 0};
+          if (k->val->walk(&Item::check_column_usage_processor, FALSE, 
+                            (uchar*)&fp))
+            k->type= KEYUSE_NO_BIND;
+          else
+          {
+            k->used_tables= fp.used_tables;
+            k->keypart_map= fp.needed_key_parts;
+            k->type= KEYUSE_BIND;
+          }
+        }
+        
+        if (k->type == KEYUSE_BIND)
+        {
+          /*
+            If this is a binding keyuse, such that
+             - all tables it refers to are bound,
+             - all parts it refers to are bound
+             - but the key part it binds is not itself bound
+          */
+          if (!(k->used_tables & ~bound_tables) && 
+              !(k->keypart_map & ~bound_parts) && 
+              !(bound_parts & key_part_map(1) << k->keypart))
+          {
+            bound_parts|= key_part_map(1) << k->keypart;
+            if (bound_parts == PREV_BITS(key_part_map, keyinfo->key_parts))
+              return TRUE;
+            bound_more_parts= TRUE;
+          }
+        }
+      }
+    } while (bound_more_parts);
+  }
+  return FALSE;
+#if 0
     Keyuse_w_needed_reg *uses;
     if (!(uses= (Keyuse_w_needed_reg*)my_alloca(sizeof(Keyuse_w_needed_reg)*
                                                 n_keyuses)))
@@ -450,8 +494,7 @@ extra_keyuses_bind_all_keyparts(table_map bound_tables, TABLE *table,
           return TRUE;
       }
     } while (n_bounded != 0);
-  }
-  return FALSE;
+#endif 
 }
 
 
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index 729ee190a0f..b5771bc0d42 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -2762,7 +2762,7 @@ make_join_statistics(JOIN *join, TABLE_LIST *tables_arg, COND *conds,
 	{
 	  start_keyuse=keyuse;
 	  key=keyuse->key;
-	  if (keyuse->usable == 1)
+	  if (keyuse->type == KEYUSE_USABLE)
             s->keys.set_bit(key);               // QQ: remove this ?
 
 	  refs=0;
@@ -2770,8 +2770,8 @@ make_join_statistics(JOIN *join, TABLE_LIST *tables_arg, COND *conds,
 	  eq_part.clear_all();
 	  do
 	  {
-            if (keyuse->usable==1 && keyuse->val->type() != Item::NULL_ITEM && 
-                !keyuse->optimize)
+            if (keyuse->type == KEYUSE_USABLE && 
+                keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize)
 	    {
 	      if (!((~found_const_table_map) & keyuse->used_tables))
 		const_ref.set_bit(keyuse->keypart);
@@ -2971,7 +2971,7 @@ typedef struct key_field_t {
   */
   bool          null_rejecting; 
   bool         *cond_guard; /* See KEYUSE::cond_guard */
-  bool          usable; /* See KEYUSE::usable */
+  enum keyuse_type type; /* See KEYUSE::type */
 } KEY_FIELD;
 
 
@@ -3069,7 +3069,7 @@ merge_key_fields(KEY_FIELD *start,KEY_FIELD *new_fields,KEY_FIELD *end,
               be, too (TODO: shouldn't that apply to the above
               null_rejecting and optimize attributes?)
             */
-            DBUG_ASSERT(old->usable == new_fields->usable);
+            DBUG_ASSERT(old->type == new_fields->type);
 	  }
 	}
 	else if (old->eq_func && new_fields->eq_func &&
@@ -3085,12 +3085,13 @@ merge_key_fields(KEY_FIELD *start,KEY_FIELD *new_fields,KEY_FIELD *end,
           old->null_rejecting= (old->null_rejecting &&
                                 new_fields->null_rejecting);
           // "t.key_col=const" predicates are always usable
-          DBUG_ASSERT(old->usable && new_fields->usable);
+          DBUG_ASSERT(old->type == KEYUSE_USABLE && 
+                      new_fields->type == KEYUSE_USABLE);
 	}
 	else if (old->eq_func && new_fields->eq_func &&
-		 ((new_fields->usable && old->val->const_item() && 
-                   old->val->is_null()) || 
-                 ((old->usable && new_fields->val->is_null()))))
+		 ((new_fields->type == KEYUSE_USABLE && 
+                   old->val->const_item() && old->val->is_null()) || 
+                 ((old->type == KEYUSE_USABLE && new_fields->val->is_null()))))
                 /* TODO ^ why is the above asymmetric, why const_item()? */
 	{
 	  /* field = expression OR field IS NULL */
@@ -3181,9 +3182,6 @@ add_key_field(KEY_FIELD **key_fields,uint and_level, Item_func *cond,
       if (!((value[i])->used_tables() & (field->table->map | RAND_TABLE_BIT)))
         optimizable=1;
     }
-    // psergey-tbl-elim:
-    // if (!optimizable)
-    //  return;
     if (!(usable_tables & field->table->map))
     {
       if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
@@ -3290,7 +3288,7 @@ add_key_field(KEY_FIELD **key_fields,uint and_level, Item_func *cond,
   (*key_fields)->val=		*value;
   (*key_fields)->level=		and_level;
   (*key_fields)->optimize=	exists_optimize;
-  (*key_fields)->usable=	optimizable;
+  (*key_fields)->type=	        optimizable? KEYUSE_USABLE : KEYUSE_UNKNOWN;
   /*
     If the condition has form "tbl.keypart = othertbl.field" and 
     othertbl.field can be NULL, there will be no matches if othertbl.field 
@@ -3602,12 +3600,7 @@ add_key_part(DYNAMIC_ARRAY *keyuse_array,KEY_FIELD *key_field)
 	  keyuse.optimize= key_field->optimize & KEY_OPTIMIZE_REF_OR_NULL;
           keyuse.null_rejecting= key_field->null_rejecting;
           keyuse.cond_guard= key_field->cond_guard;
-          if (!(keyuse.usable= key_field->usable))
-          {
-            /* The following will have special meanings: */
-            keyuse.keypart_map= 0;
-            keyuse.used_tables= 0;
-          }
+          keyuse.type= key_field->type;
 	  VOID(insert_dynamic(keyuse_array,(uchar*) &keyuse));
 	}
       }
@@ -3674,7 +3667,7 @@ add_ft_keys(DYNAMIC_ARRAY *keyuse_array,
   keyuse.used_tables=cond_func->key_item()->used_tables();
   keyuse.optimize= 0;
   keyuse.keypart_map= 0;
-  keyuse.usable= 1;
+  keyuse.type= KEYUSE_USABLE;
   VOID(insert_dynamic(keyuse_array,(uchar*) &keyuse));
 }
 
@@ -3691,8 +3684,10 @@ sort_keyuse(KEYUSE *a,KEYUSE *b)
     return (int) (a->keypart - b->keypart);
 
   // Usable ones go before the unusable
-  if (a->usable != b->usable)
-    return (int)b->usable - (int)a->usable;
+  int a_ok= test(a->type == KEYUSE_USABLE);
+  int b_ok= test(b->type == KEYUSE_USABLE);
+  if (a_ok != b_ok)
+    return a_ok? -1 : 1;
 
   // Place const values before other ones
   if ((res= test((a->used_tables & ~OUTER_REF_TABLE_BIT)) -
@@ -3904,7 +3899,7 @@ update_ref_and_keys(THD *thd, DYNAMIC_ARRAY *keyuse,JOIN_TAB *join_tab,
     found_eq_constant=0;
     for (i=0 ; i < keyuse->elements-1 ; i++,use++)
     {
-      if (use->usable == 1 && !use->used_tables && 
+      if (use->type == KEYUSE_USABLE && !use->used_tables && 
           use->optimize != KEY_OPTIMIZE_REF_OR_NULL)
 	use->table->const_key_parts[use->key]|= use->keypart_map;
       if (use->keypart != FT_KEYPART)
@@ -3929,7 +3924,7 @@ update_ref_and_keys(THD *thd, DYNAMIC_ARRAY *keyuse,JOIN_TAB *join_tab,
       /* Save ptr to first use */
       if (!use->table->reginfo.join_tab->keyuse)
 	use->table->reginfo.join_tab->keyuse=save_pos;
-      if (use->usable == 1)
+      if (use->type == KEYUSE_USABLE)
         use->table->reginfo.join_tab->checked_keys.set_bit(use->key);
       save_pos++;
     }
@@ -3960,7 +3955,7 @@ static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array)
       To avoid bad matches, we don't make ref_table_rows less than 100.
     */
     keyuse->ref_table_rows= ~(ha_rows) 0;	// If no ref
-    if (keyuse->usable == 1 && keyuse->used_tables &
+    if (keyuse->type == KEYUSE_USABLE && keyuse->used_tables &
 	(map= (keyuse->used_tables & ~join->const_table_map &
 	       ~OUTER_REF_TABLE_BIT)))
     {
@@ -4152,7 +4147,7 @@ best_access_path(JOIN      *join,
             if 1. expression doesn't refer to forward tables
                2. we won't get two ref-or-null's
           */
-          if (keyuse->usable == 1&& 
+          if (keyuse->type == KEYUSE_USABLE && 
               !(remaining_tables & keyuse->used_tables) &&
               !(ref_or_null_part && (keyuse->optimize &
                                      KEY_OPTIMIZE_REF_OR_NULL)))
@@ -5607,7 +5602,8 @@ static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
     */
     do
     {
-      if (!(~used_tables & keyuse->used_tables) && keyuse->usable == 1)
+      if (!(~used_tables & keyuse->used_tables) && 
+          keyuse->type == KEYUSE_USABLE)
       {
 	if (keyparts == keyuse->keypart &&
 	    !(found_part_ref_or_null & keyuse->optimize))
@@ -5658,7 +5654,7 @@ static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
     for (i=0 ; i < keyparts ; keyuse++,i++)
     {
       while (keyuse->keypart != i || ((~used_tables) & keyuse->used_tables) ||
-             !(keyuse->usable == 1))
+             !(keyuse->type == KEYUSE_USABLE))
       {
 	keyuse++;				/* Skip other parts */
       }
@@ -16709,9 +16705,9 @@ static void print_join(THD *thd,
     the fact that the first table can't be inner table of an outer join.
   */
   DBUG_ASSERT(!eliminated_tables || 
-              !((*table)->table && ((*table)->table->map & eliminated_tables) ||
-                (*table)->nested_join && !((*table)->nested_join->used_tables &
-                                           ~eliminated_tables)));
+              !(((*table)->table && ((*table)->table->map & eliminated_tables)) ||
+                ((*table)->nested_join && !((*table)->nested_join->used_tables &
+                                           ~eliminated_tables))));
   (*table)->print(thd, eliminated_tables, str, query_type);
 
   TABLE_LIST **end= table + tables->elements;
diff --git a/sql/sql_select.h b/sql/sql_select.h
index ae334a2f012..c3d0dacd78b 100644
--- a/sql/sql_select.h
+++ b/sql/sql_select.h
@@ -33,6 +33,40 @@
 #define KEY_OPTIMIZE_EXISTS		1
 #define KEY_OPTIMIZE_REF_OR_NULL	2
 
+/* KEYUSE element types */
+enum keyuse_type
+{
+  /* 
+    val refers to the same table, this is either KEYUSE_BIND or KEYUSE_NO_BIND
+    type, we didn't determine which one yet.
+  */
+  KEYUSE_UNKNOWN= 0,
+  /* 
+    'regular' keyuse, i.e. it represents one of the following
+      * t.keyXpartY = func(constants, other-tables)
+      * t.keyXpartY IS NULL 
+      * t.keyXpartY = func(constants, other-tables) OR t.keyXpartY IS NULL 
+    and can be used to construct ref acces
+  */
+  KEYUSE_USABLE,
+  /*
+    The keyuse represents a condition in form: 
+      
+      t.uniq_keyXpartY = func(other parts of uniq_keyX)
+    
+    This can't be used to construct uniq_keyX but we could use it to determine
+    that the table will produce at most one match.
+  */
+  KEYUSE_BIND,
+  /*
+    Keyuse that's not usable for ref access and doesn't meet the criteria of
+    KEYUSE_BIND. Examples:
+      t.keyXpartY = func(t.keyXpartY)
+      t.keyXpartY = func(column of t that's not covered by keyX)
+  */
+  KEYUSE_NO_BIND
+};
+
 typedef struct keyuse_t {
   TABLE *table;
   Item	*val;				/**< or value if no field */
@@ -64,7 +98,7 @@ typedef struct keyuse_t {
               This equality cannot be used for index access but is useful
               for table elimination.
   */
-  int usable;
+  enum keyuse_type type;
 } KEYUSE;
 
 class store_key;
diff --git a/sql/table.h b/sql/table.h
index e342fb7194c..d3c1542420b 100644
--- a/sql/table.h
+++ b/sql/table.h
@@ -1618,7 +1618,8 @@ typedef struct st_nested_join
   List<TABLE_LIST>  join_list;       /* list of elements in the nested join */
   /* 
     Bitmap of tables within this nested join (including those embedded within
-    its children). Eliminated tables are still in the bitmap */
+    its children), including tables removed by table elimination.
+  */
   table_map         used_tables;
   table_map         not_null_tables; /* tables that rejects nulls           */
   struct st_join_table *first_nested;/* the first nested table in the plan  */
@@ -1628,11 +1629,12 @@ typedef struct st_nested_join
     2. check_interleaving_with_nj/restore_prev_nj_state (these are called
        by the join optimizer. 
     Before each use the counters are zeroed by reset_nj_counters.
-    Meaning, in both cases: number of base tables within this nested join and
-    its children. Eliminated tables are not counted.
   */
   uint              counter;
-  /* Tables left after elimination */
+  /*
+    Number of elements in join_list that were not (or contain table(s) that 
+    weren't) removed by table elimination.
+  */
   uint              n_tables;
   nested_join_map   nj_map;          /* Bit used to identify this nested join*/
 } NESTED_JOIN;