MySQL Lists are EOL. Please join:

List:Commits« Previous MessageNext Message »
From:igor Date:December 7 2007 8:05am
Subject:bk commit into 5.2 tree (igor:1.2593)
View as plain text  
Below is the list of changes that have just been committed into a local
5.2 repository of igor. When igor 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, 2007-12-07 00:05:10-08:00, igor@stripped +2 -0
  WL #2771: BKA, prototype: supported linked join caches.

  sql/sql_select.cc@stripped, 2007-12-07 00:05:07-08:00, igor@stripped +422 -82
    WL #2771: BKA, prototype: supported linked join caches.

  sql/sql_select.h@stripped, 2007-12-07 00:05:07-08:00, igor@stripped +108 -25
    WL #2771: BKA, prototype: supported linked join caches.

diff -Nrup a/sql/sql_select.cc b/sql/sql_select.cc
--- a/sql/sql_select.cc	2007-11-08 13:29:47 -08:00
+++ b/sql/sql_select.cc	2007-12-07 00:05:07 -08:00
@@ -6979,6 +6979,7 @@ make_simple_join(JOIN *join,TABLE *tmp_t
   join->row_limit=join->unit->select_limit_cnt;
   join->do_send_rows = (join->row_limit) ? 1 : 0;
 
+  join_tab->use_join_cache= FALSE;
   join_tab->cache= 0;			        /* No caching */
   join_tab->cache_select= 0;
   join_tab->table=tmp_table;
@@ -7997,6 +7998,9 @@ make_join_readinfo(JOIN *join, ulonglong
     JOIN_TAB *tab=join->join_tab+i;
     TABLE *table=tab->table;
     bool using_join_cache;
+    JOIN_TAB *first_inner= tab->first_inner;
+    while (first_inner && first_inner->first_upper)
+      first_inner= first_inner->first_upper;
     tab->read_record.table= table;
     tab->read_record.file=table->file;
     tab->next_select=sub_select;		/* normal select */
@@ -8056,16 +8060,16 @@ make_join_readinfo(JOIN *join, ulonglong
       tab->read_record.read_record= join_no_more_records;
       using_join_cache= FALSE;
 
-#if 1
+#if 0
 #else
       {
         bool do_bka= !test(join->thd->variables.optimizer_switch &
                            OPTIMIZER_SWITCH_NO_BKA);
         if (do_bka &&
             i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
-            tab->use_quick != 2 && 
-            (!tab->first_inner || 
-             tab->is_single_inner_of_outer_join()) &&
+            tab->use_quick != 2 &&
+            (!first_inner || tab == first_inner ||
+             first_inner->use_join_cache) && 
             (!tab->emb_sj_nest ||
              tab->is_single_inner_of_semi_join_with_first_match()) &&
             i <= no_jbuf_after)
@@ -8073,11 +8077,13 @@ make_join_readinfo(JOIN *join, ulonglong
           uint flag= HA_MRR_NO_NULL_ENDPOINTS;
           COST_VECT cost;
           uint bufsz= 4096;
+          JOIN_CACHE *prev_cache= (tab-1)->cache ? (tab-1)->cache : 0;
           table->file->multi_range_read_info(tab->ref.key, 10, 20,
                                              &bufsz, &flag, &cost);  
 	  if (!(flag & HA_MRR_USE_DEFAULT_IMPL) &&
               ((options & SELECT_DESCRIBE) ||
-               (tab->cache || (tab->cache= new JOIN_CACHE_BKA(join, tab))) &&
+               (tab->cache ||
+                (tab->cache= new JOIN_CACHE_BKA(join, tab, prev_cache))) &&
 	       !tab->cache->init()))
 	  {
             using_join_cache= TRUE;
@@ -8086,6 +8092,7 @@ make_join_readinfo(JOIN *join, ulonglong
         }
       }
 #endif
+      tab->use_join_cache= using_join_cache;
       if (table->covering_keys.is_set(tab->ref.key) &&
 	  !table->no_keyread)
       {
@@ -8112,16 +8119,17 @@ make_join_readinfo(JOIN *join, ulonglong
 	tab->read_record.read_record= tab->insideout_match_tab? 
            join_read_next_same_diff : join_read_next_same;
  
-#if 1
+#if 0
 #else   
         bool do_bka= !test(join->thd->variables.optimizer_switch &
                            OPTIMIZER_SWITCH_NO_BKA);
+        JOIN_CACHE *prev_cache= (tab-1)->cache ? (tab-1)->cache : 0;
 
         if (do_bka &&
             i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
             tab->use_quick != 2 &&
-            (!tab->first_inner || 
-             tab->is_single_inner_of_outer_join()) &&
+            (!first_inner || tab == first_inner ||
+             first_inner->use_join_cache) && 
             (!tab->emb_sj_nest ||
              tab->is_single_inner_of_semi_join_with_first_match()) &&
             i <= no_jbuf_after)
@@ -8133,7 +8141,8 @@ make_join_readinfo(JOIN *join, ulonglong
                                              &bufsz, &flag, &cost);  
 	  if (!(flag & HA_MRR_USE_DEFAULT_IMPL) &&
               ((options & SELECT_DESCRIBE) ||
-               (tab->cache || (tab->cache= new JOIN_CACHE_BKA(join, tab))) &&
+               (tab->cache ||
+                (tab->cache= new JOIN_CACHE_BKA(join, tab, prev_cache))) &&
 	       !tab->cache->init()))
 	  {
             using_join_cache= TRUE;
@@ -8147,6 +8156,7 @@ make_join_readinfo(JOIN *join, ulonglong
 	tab->read_first_record= join_read_always_key_or_null;
 	tab->read_record.read_record= join_read_next_same_or_null;
       }
+      tab->use_join_cache= using_join_cache;
       if (table->covering_keys.is_set(tab->ref.key) &&
 	  !table->no_keyread)
       {
@@ -8168,22 +8178,24 @@ make_join_readinfo(JOIN *join, ulonglong
       */
       table->status=STATUS_NO_RECORD;
       using_join_cache= FALSE;
-#if 1
+#if 0
       if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
           tab->use_quick != 2 && !tab->first_inner && i <= no_jbuf_after &&
           !tab->insideout_match_tab)
 #else
       if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
           tab->use_quick != 2 &&
-          (!tab->first_inner || 
-           tab->is_single_inner_of_outer_join()) &&
-           (!tab->emb_sj_nest ||
-            tab->is_single_inner_of_semi_join_with_first_match()) &&
+          (!first_inner || tab == first_inner ||
+           first_inner->use_join_cache) && 
+          (!tab->emb_sj_nest ||
+           tab->is_single_inner_of_semi_join_with_first_match()) &&
           i <= no_jbuf_after)
 #endif
       {
+        JOIN_CACHE *prev_cache= (tab-1)->cache ? (tab-1)->cache : 0;
 	if ((options & SELECT_DESCRIBE) ||
-            (tab->cache || (tab->cache= new JOIN_CACHE_BNL(join, tab))) &&
+            (tab->cache ||
+             (tab->cache= new JOIN_CACHE_BNL(join, tab,prev_cache))) &&
 	    !tab->cache->init())
 	{
           using_join_cache= TRUE;
@@ -8247,6 +8259,7 @@ make_join_readinfo(JOIN *join, ulonglong
 	    tab->type=JT_NEXT;		// Read with index_first / index_next
 	  }
 	}
+        tab->use_join_cache= using_join_cache;
         if (tab->select && tab->select->quick &&
             tab->select->quick->index != MAX_KEY && ! tab->table->key_read)
           push_index_cond(tab, tab->select->quick->index, !using_join_cache);
@@ -13504,11 +13517,10 @@ evaluate_null_complemented_join_record(J
 
 
 enum_nested_loop_state
-JOIN_CACHE_BNL::join_records(bool skip_last)
+JOIN_CACHE_BNL::join_matching_records(bool skip_last)
 {
   uint i;
   bool semi_join_flag= mrr_mode == HA_MRR_SEMI_JOIN;
-  bool outer_join_flag= use_match_flag && !semi_join_flag;
   enum_nested_loop_state rc= NESTED_LOOP_OK;
   int error;
   READ_RECORD *info;
@@ -13529,7 +13541,6 @@ JOIN_CACHE_BNL::join_records(bool skip_l
   /* read through all records */
   if ((error=join_init_read_record(join_tab)))
   {
-    reset(TRUE);
     return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
   }
 
@@ -13551,16 +13562,16 @@ JOIN_CACHE_BNL::join_records(bool skip_l
         (!select || !select->skip_record()))
     {
       reset(FALSE);
-      join_tab->not_null_compl= 1;
+
       for (i= records - test(skip_last) ; i-- > 0 ;)
       { 
         if (!semi_join_flag || !skip_record_if_match())
         {
 	  get_record();
-          if (!join_tab->select || !join_tab->select->skip_record())
+          if (check_match(get_record_pos()))
           {
             int res= 0;
-            if (use_match_flag)
+            if (semi_join_flag)
               set_match_flag(1);
             if (!join_tab->check_weed_out_table || 
                 !(res= do_sj_dups_weedout(join->thd,
@@ -13581,11 +13592,6 @@ JOIN_CACHE_BNL::join_records(bool skip_l
     }
   } while (!(error=info->read_record(info)));
 
-  if (outer_join_flag)
-    rc= add_null_complemented_records(records - test(skip_last));                 
-  if (skip_last)
-    get_record();		                // Restore current record
-  reset(TRUE);
   if (error > 0)				// Fatal error
     return NESTED_LOOP_ERROR;                   /* purecov: inspected */
   for (JOIN_TAB *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
@@ -16178,6 +16184,7 @@ uint add_prefix_addon_field(uchar *str, 
   copy->strip= 0;
   copy->blob_field= 0;
   copy->field= 0;
+  copy->ext_key_arg_no= 0;
   copy->get_rowid= NULL;
   (*field)++;
   (*fields)++;
@@ -16206,6 +16213,7 @@ uint add_table_fields_to_join_cache(JOIN
         (*field_ptr)++;
       }
       copy->field= *f_ptr;
+      copy->ext_key_arg_no= 0;
       copy->get_rowid= NULL;
       (*field)++;
     }
@@ -16225,7 +16233,9 @@ bool JOIN_CACHE_BKA::check_emb_key_usage
   KEY *keyinfo= table->key_info+ ref->key;
   if (join_tab->type != JT_EQ_REF)
     return FALSE;
-  if (key_arg_fields != ref->key_parts)
+  if (local_key_arg_fields != 0 && local_key_arg_fields != ref->key_parts)
+    return FALSE;
+  if (global_key_arg_fields != 0 && ref->key_parts != 1)
     return FALSE;
   for (i=0; i < ref->key_parts; i++)
   {
@@ -16241,7 +16251,7 @@ bool JOIN_CACHE_BKA::check_emb_key_usage
       return FALSE;
   }
   for (i= 0, copy= field+prefix_addon_fields;
-       i < key_arg_fields;
+       i < local_key_arg_fields;
        i++, copy++)
   {
     if (copy->strip)
@@ -16257,7 +16267,7 @@ bool JOIN_CACHE_BKA::check_emb_key_usage
     Item *item= ref->items[i]->real_item();
     Field *fld= ((Item_field *) item)->field;
     CACHE_FIELD *init_copy= field+prefix_addon_fields+i; 
-    for (j= i, copy= init_copy; i < key_arg_fields;  i++, copy++)
+    for (j= i, copy= init_copy; i < local_key_arg_fields;  i++, copy++)
     {
       if (fld->eq(copy->field))
       {
@@ -16272,7 +16282,7 @@ bool JOIN_CACHE_BKA::check_emb_key_usage
     }
   }
 
-  return TRUE;
+  return ((use_emb_key= TRUE));
 }    
     
 
@@ -16286,6 +16296,7 @@ JOIN_CACHE::init()
   CACHE_FIELD **copy_ptr;
   JOIN_TAB *tab_start;
   JOIN_TAB *tab;
+  uint gl_key_arg_fields= 0;
   DBUG_ENTER("JOIN_CACHE::init");
 
   use_match_flag= FALSE;
@@ -16297,15 +16308,18 @@ JOIN_CACHE::init()
     use_match_flag= TRUE;
     mrr_mode= HA_MRR_SEMI_JOIN;
   }
-  if (join_tab->first_inner && join_tab->first_inner == join_tab->last_inner)
+  if (join_tab->first_inner && join_tab->first_inner == join_tab)
     use_match_flag= TRUE;
 
   fields= blobs= 0;
   prefix_addon_fields= 0;
+  ext_key_arg_fields= 0;
 
   select= join_tab->cache_select;
-  tab_start= join->join_tab+join->const_tables;
+  tab_start= prev_cache ? prev_cache->join_tab :
+                          join->join_tab+join->const_tables;
   tables= table_count= join_tab-tab_start;
+
   for (i= 0, tab= tab_start; i < table_count ; i++, tab++)
   {
     if (!tab->used_fieldlength)		/* Not calced yet */
@@ -16320,35 +16334,52 @@ JOIN_CACHE::init()
       tab->used_fieldlength += tab->table->file->ref_length;
     }
   }
+ 
+  if (is_key_access())
+  {
+    ((JOIN_CACHE_BKA *) this)->set_key_arg_fields(FALSE, 0);
+    ((JOIN_CACHE_BKA *) this)->set_key_arg_fields(TRUE, 0);
+    ((JOIN_CACHE_BKA *) this)->use_emb_key= FALSE;
+
+    /* Mark all fields that can be used as arguments for this key access */
+ 
+    TABLE_REF *ref= &join_tab->ref;
+    JOIN_CACHE *cache= this;
+    do
+    {
+      for (tab= cache->join_tab-cache->tables; tab < cache->join_tab ; tab++)
+      { 
+        bitmap_clear_all(&tab->table->tmp_set);
+        for (uint j= 0; j < ref->key_parts; j++)
+        {
+          Item *ref_item= ref->items[j]; 
+          if (!(tab->table->map & ref_item->used_tables()))
+	    continue;
+	  ref_item->walk(&Item::add_field_to_set_processor, 1,
+                         (uchar *) &tab->table->tmp_set);
+        }
+        uint key_args= bitmap_bits_set(&tab->table->tmp_set);
+        if (key_args)
+          ((JOIN_CACHE_BKA *) this)->incr_key_arg_fields(key_args,
+                                                         cache == this);
+      }
+      cache= cache->prev_cache;
+    } 
+    while (cache);
+    gl_key_arg_fields= ((JOIN_CACHE_BKA *) this)->get_key_arg_fields(FALSE);
+  }  
+
+
   if (!(field=(CACHE_FIELD*)
 	sql_alloc(sizeof(CACHE_FIELD)*(fields+table_count*2+1)+
-                  sizeof(CACHE_FIELD*)*(blobs+1))))
+                  sizeof(CACHE_FIELD*)*(gl_key_arg_fields+blobs+1))))
   {
     my_free((uchar*) buff,MYF(0));		/* purecov: inspected */
     buff=0;				        /* purecov: inspected */
     DBUG_RETURN(1);				/* purecov: inspected */
   }
   copy= field;
-  copy_ptr= blob_ptr= (CACHE_FIELD**) (field+fields+table_count*2+
-                                       test(use_match_flag));
-
-  if (is_key_access())
-  { 
-    TABLE_REF *ref= &join_tab->ref;
-    for (i= 0, tab= tab_start; i < table_count ; i++, tab++)
-    {
-      
-      bitmap_clear_all(&tab->table->tmp_set);
-      for (uint j= 0; j < ref->key_parts; j++)
-      {
-        Item *ref_item= ref->items[j]; 
-        if (!(tab->table->map & ref_item->used_tables()))
-	  continue;
-	ref_item->walk(&Item::add_field_to_set_processor, 1,
-                       (uchar *) &tab->table->tmp_set);
-      }
-    }
-  }  
+  copy_ptr= (CACHE_FIELD**) (field+fields+table_count*2+test(use_match_flag));
 
   length=0;
 
@@ -16390,18 +16421,47 @@ JOIN_CACHE::init()
   }
   fields+= prefix_addon_fields;
 
-  /* Now copy fields from ref if any */
   if (is_key_access())
   {
+    /* 
+      Set pointers to the cache fields in previous caches
+      that  are used to build keys for this key access.
+    */
+    JOIN_CACHE *cache= this;
+    while (gl_key_arg_fields)
+    {
+      cache= cache->prev_cache;
+      for (tab= cache->join_tab-cache->tables; tab < cache->join_tab ; tab++)
+      { 
+        CACHE_FIELD *cache_copy;
+        MY_BITMAP *key_read_set= &tab->table->tmp_set;
+        if (bitmap_is_clear_all(key_read_set))
+          continue;
+        cache_copy= cache->field+cache->prefix_addon_fields;
+        for (i= cache->prefix_addon_fields; i < cache->fields; i++, cache_copy++)
+        {
+          if (bitmap_is_set(key_read_set, cache_copy->field->field_index))
+          {
+            *copy_ptr++= cache_copy;
+            gl_key_arg_fields--;
+            if (!cache_copy->ext_key_arg_no)
+	      cache->register_ext_key_arg_field(cache_copy);
+          }
+        }
+      }
+    } 
+    
+    /* Now copy fields from ref if any */
+    blob_ptr= copy_ptr;
     for (i=0, tab= tab_start; i < table_count ; i++, tab++)
     {
       length+= add_table_fields_to_join_cache(tab, &tab->table->tmp_set,  
                                               &copy, &copy_ptr);
     }
-    JOIN_CACHE_BKA *cache= (JOIN_CACHE_BKA *) this;
-    cache->set_key_arg_count((copy-field)-prefix_addon_fields);
-    cache->use_emb_key= cache->check_emb_key_usage();
+    ((JOIN_CACHE_BKA *) this)->check_emb_key_usage();
   }
+  else
+    blob_ptr= copy_ptr;
    
   /* Copy the remaining table fields */    
   for (i=0, tab= tab_start; i < table_count ; i++, tab++)
@@ -16425,8 +16485,9 @@ JOIN_CACHE::init()
       copy->str= table->file->ref;
       copy->length= table->file->ref_length;      copy->strip=0;
       copy->blob_field=0;
-      copy->get_rowid= NULL;
       copy->field= 0;
+      copy->ext_key_arg_no= 0;
+      copy->get_rowid= NULL;
       if (tab->rowid_keep_flags & JOIN_TAB::CALL_POSITION)
       {
         /* We will need to call h->position(): */
@@ -16468,6 +16529,7 @@ uint JOIN_CACHE::write_record_data(bool 
 {
   uint i;
   uint len;
+  uchar *data_pos;
   uchar *rec_len_ptr= 0;
   CACHE_FIELD *copy;
   uchar *pos= this->pos;
@@ -16501,6 +16563,15 @@ uint JOIN_CACHE::write_record_data(bool 
     pos+= sizeof(uint32);
   }
 
+  if (prev_cache)
+  {
+    uchar *prev_rec_pos= prev_cache->get_record_pos();
+    memcpy(pos, &prev_rec_pos, sizeof(uchar *));
+    pos+= sizeof(uchar *);
+  } 
+
+  data_pos= pos;
+
   if (use_match_flag)
     *field[0].str= 0;
 
@@ -16515,7 +16586,13 @@ uint JOIN_CACHE::write_record_data(bool 
   for ( ; copy < end_field; copy++)
   {
     if (copy->field && copy->field->maybe_null() && copy->field->is_null())
+    {
+      if (copy->ext_key_arg_no)
+        copy->offset= 0;
       continue;              // Do not copy a field if its value is null 
+    }
+    if (copy->ext_key_arg_no)
+      copy->offset= pos-data_pos;
     if (copy->blob_field)
     {
       if (last_record)
@@ -16558,6 +16635,18 @@ uint JOIN_CACHE::write_record_data(bool 
       }
     }
   }
+  if (ext_key_arg_fields)
+  {
+    for (copy= field+prefix_addon_fields; copy < end_field ; copy++)
+    {
+      if (copy->ext_key_arg_no)
+      {
+        int4store(pos, copy->offset);
+        pos+= sizeof(uint32);
+      }
+    }
+  }
+
   if (rec_len_ptr)
     int4store(rec_len_ptr, (uint32) (pos-rec_len_ptr-sizeof(uint32)));
   this->pos= pos;
@@ -16628,7 +16717,41 @@ uint JOIN_CACHE::read_record_field(CACHE
   pos+= len;
   return len;
 }
-  
+
+bool JOIN_CACHE::read_ext_key_arg_field(CACHE_FIELD *copy,
+                                        uchar *rec_ptr, 
+                                        bool last_record,
+                                        uint *len)
+{
+  uint offset;
+  if (copy < field || copy >= field+fields)
+    return FALSE;
+  if (!*len)
+  {
+    uchar *len_ptr= rec_ptr;
+    if (prev_cache)
+      len_ptr-= sizeof(uchar *);
+    *len= uint4korr(len_ptr-sizeof(uint32));
+  }
+  offset= uint4korr(rec_ptr-
+                    (prev_cache ? sizeof(uchar *) : 0)+
+                    (*len)-
+                    sizeof(uint32)*
+                    (ext_key_arg_fields+1-copy->ext_key_arg_no));  
+  bool is_null= FALSE;
+  if (offset == 0 && prefix_addon_fields)
+    is_null= TRUE;
+  if (is_null)
+    copy->field->set_null();
+  else
+  {
+    copy->field->set_notnull(); 
+    pos= rec_ptr+offset;
+    read_record_field(copy, last_record);
+  }
+  return TRUE;
+}
+   
 uint JOIN_CACHE::read_record_data()
 {
   CACHE_FIELD *copy= field;
@@ -16638,7 +16761,7 @@ uint JOIN_CACHE::read_record_data()
   
   if (record_nr == records)
     return 0;
-  record_nr++;
+  record_nr++;  
 
   /* First match flag, read null bits and null_row flag for each record */
   copy+= read_prefix_addon_fields();
@@ -16651,6 +16774,167 @@ uint JOIN_CACHE::read_record_data()
 }
 
 
+bool JOIN_CACHE::set_match_flag_if_none(JOIN_TAB *first_inner,
+                                        uchar *rec_ptr)
+{
+  if (!first_inner->cache)
+  {
+    first_inner->found= 1;
+    return TRUE;
+  }
+  uchar *prev_rec_ptr= rec_ptr;
+  JOIN_CACHE *cache= this;
+  while (cache->join_tab != first_inner)
+  {
+    memcpy(&prev_rec_ptr, prev_rec_ptr-sizeof(uchar *), sizeof(uchar *));
+    cache= cache->prev_cache;
+  } 
+  if (*prev_rec_ptr == 0)
+  {
+    *prev_rec_ptr= 1;
+    first_inner->found= 1;
+    return TRUE;  
+  }
+  return FALSE;
+}
+
+
+enum_nested_loop_state
+JOIN_CACHE::join_records(bool skip_last)
+{
+  JOIN_TAB *tab;
+  enum_nested_loop_state rc= NESTED_LOOP_OK;
+  bool is_first_inner= join_tab->first_inner && 
+                       join_tab->first_inner == join_tab;
+  if (is_first_inner)
+    join_tab->not_null_compl= TRUE;
+  if (!join_tab->first_inner || join_tab->first_inner->not_null_compl)
+  {
+    rc= join_matching_records(skip_last);   
+    if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
+    {
+      reset(TRUE);
+      return rc;
+    }
+    if (is_first_inner)
+    {
+      if (next_cache)
+      {
+        rc= next_cache->join_records(skip_last);
+        if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
+        {
+          reset(TRUE);
+          return rc;
+        }
+      }
+      join_tab->not_null_compl= FALSE;
+      for (tab= join_tab->first_inner; tab <= join_tab->last_inner; tab++)
+        tab->first_unmatched= join_tab->first_inner;
+    }
+  }
+  if (join_tab->first_unmatched && !join_tab->first_unmatched->not_null_compl)
+  {
+    reset(FALSE);
+    rc= join_null_records(skip_last);   
+    if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
+    {
+      reset(TRUE);
+      return rc;
+    }
+  }
+  if(next_cache)
+  {
+    rc= next_cache->join_records(skip_last);
+    if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
+    {
+      reset(TRUE);
+      return rc;
+    }
+  }
+  if (is_first_inner)
+  {
+    for (tab= join_tab->first_inner; tab <= join_tab->last_inner; tab++)
+      tab->first_unmatched= 0;
+  } 
+ 
+  if (skip_last)
+  {
+    DBUG_ASSERT(!is_key_access());
+    get_record();		                // Restore current record
+  }
+  reset(TRUE);
+  return rc;
+}
+
+inline
+bool JOIN_CACHE::check_match(uchar *rec_ptr)
+{
+  if (join_tab->select && join_tab->select->skip_record())
+    return FALSE;
+
+  if (!join_tab->first_inner ||
+      join_tab->first_inner->last_inner != join_tab)
+    return TRUE;
+
+  /* 
+     This is the last inner table of an outer join,
+     and maybe of other embedding outer joins. 
+  */
+  JOIN_TAB *first_inner= join_tab->first_inner;
+  do
+  {
+    if (!set_match_flag_if_none(first_inner, rec_ptr))
+      return TRUE;
+    /* 
+      This is the first match for the outer table row.
+      The function set_match_flag_if_none has turned the flag
+      first_inner->found on. The pushed down predicates for
+      inner tables must be re-evaluated with this flag on.
+    */      
+    for (JOIN_TAB *tab= first_inner; tab <= join_tab; tab++)
+    {
+      if (tab->select && tab->select->skip_record())
+        return FALSE;
+    }
+  }
+  while ((first_inner= first_inner->first_upper));
+  
+  return TRUE;
+} 
+
+/* 
+  The following inplementation of the JOIN_CACHE::check_match
+  employs only one loop but its code is harder to understand
+*/
+#if 0
+inline
+bool JOIN_CACHE::check_match(uchar *rec_ptr)
+{
+  JOIN_TAB *tab= join_tab;
+  JOIN_TAB *first_inner= 0;
+  if (tab->first_inner && tab->first_inner->last_inner == tab)
+    first_inner= tab->first_inner : 0;
+  do
+  {
+    if (tab->select && tab->select->skip_record()));
+      return FALSE;
+    if (tab == join_tab) 
+    {                     
+      if (first_inner && 
+          !set_match_flag_if_none(tab->first_inner, rec_ptr))
+        break;
+      tab= first_inner;
+      if (first_inner)
+        first_inner= first_inner->first_upper;
+    }
+    else
+      tab++;
+  } while (tab);
+  return TRUE;
+}
+#endif
+
+     
 static range_seq_t bka_range_seq_init(void *init_param, uint n_ranges, uint flags)
 {
   DBUG_ENTER("bka_range_seq_init");
@@ -16697,6 +16981,8 @@ uint JOIN_CACHE_BKA::get_next_key(uchar 
   uint len;
   uint32 rec_len;
   uchar *init_pos;
+  uchar *prev_rec_pos;
+  JOIN_CACHE *cache;
   CACHE_FIELD *copy= field;
   bool last_record= record_nr == ptr_record;
   
@@ -16706,10 +16992,44 @@ uint JOIN_CACHE_BKA::get_next_key(uchar 
    
   rec_len= uint4korr(pos);
   pos+= 4;
-  rec_pos= init_pos= pos;
+  init_pos= pos;
+
+  if (prev_cache)
+  {
+    if (global_key_arg_fields)
+      memcpy(&prev_rec_pos, pos, sizeof(uchar *));
+    pos+= sizeof(uchar *);
+  }
+
+  rec_pos= pos;
 
   copy+= read_prefix_addon_fields();
  
+  if (global_key_arg_fields)
+  {
+    uint arg_key_count= global_key_arg_fields;
+    CACHE_FIELD **copy_ptr= blob_ptr-arg_key_count;
+    for (cache= prev_cache; ; cache= cache->prev_cache)
+    { 
+      uint len= 0;
+      while (!cache->get_ext_key_arg_fields())
+      {
+        memcpy(&prev_rec_pos, prev_rec_pos-sizeof(uchar *), sizeof(uchar *));
+        cache= cache->prev_cache;
+      }
+      while (arg_key_count && 
+             cache->read_ext_key_arg_field(*copy_ptr, prev_rec_pos, 
+                                           FALSE, &len)) // now FALSE is a stub
+      {
+        copy_ptr++;
+        --arg_key_count;
+      }
+      if (!arg_key_count)
+        break;
+      memcpy(&prev_rec_pos, prev_rec_pos-sizeof(uchar *), sizeof(uchar *));
+    }
+  }
+      
   if (use_emb_key)
   {
     *key= pos;
@@ -16717,7 +17037,9 @@ uint JOIN_CACHE_BKA::get_next_key(uchar 
   }
   else
   {
-    for (uint i= 0; i < key_arg_fields; i++, copy++)
+    cache= this;
+    
+    for (uint i= 0; i < local_key_arg_fields; i++, copy++)
       read_record_field(copy, last_record);
     
     TABLE_REF *ref= &join_tab->ref;
@@ -16732,10 +17054,9 @@ uint JOIN_CACHE_BKA::get_next_key(uchar 
 }  
 
 enum_nested_loop_state
-JOIN_CACHE_BKA::join_records(bool skip_last)
+JOIN_CACHE_BKA::join_matching_records(bool skip_last)
 {
   bool semi_join_flag= mrr_mode == HA_MRR_SEMI_JOIN;
-  bool outer_join_flag= use_match_flag && !semi_join_flag;
   handler *file= join_tab->table->file;
   enum_nested_loop_state rc= NESTED_LOOP_OK;
   int error;
@@ -16774,10 +17095,11 @@ JOIN_CACHE_BKA::join_records(bool skip_l
       if (!semi_join_flag || !get_match_flag_by_pos(rec_ptr))
       {
         get_record_by_pos(rec_ptr);
-        if (!join_tab->select || !join_tab->select->skip_record())
-        {
+        
+        if (check_match(rec_ptr))
+        {    
           int res= 0;
-          if (use_match_flag)
+          if (semi_join_flag)
              set_match_flag(1);
           if (!join_tab->check_weed_out_table || 
               !(res= do_sj_dups_weedout(join->thd,
@@ -16797,35 +17119,53 @@ JOIN_CACHE_BKA::join_records(bool skip_l
     }
   }
 
-  if (outer_join_flag)
-    rc= add_null_complemented_records(records);
-
-  reset(TRUE);
-  if (error > 0 && error != HA_ERR_END_OF_FILE)				// Fatal error
+  if (error > 0 && error != HA_ERR_END_OF_FILE)	    // Fatal error
     return NESTED_LOOP_ERROR;                   /* purecov: inspected */
   for (JOIN_TAB *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
     tmp2->table->status= tmp2->status;
   return rc;
 }
 
-enum_nested_loop_state JOIN_CACHE::add_null_complemented_records(uint count)
+
+enum_nested_loop_state JOIN_CACHE::join_null_records(bool skip_last)
 {
   enum_nested_loop_state rc= NESTED_LOOP_OK;
-  COND *select_cond= join_tab->select_cond;
-  reset(FALSE);
-  join_tab->not_null_compl= 0;
-  for ( ; count ; count-- )
+  bool is_first_inner= join_tab == join_tab->first_unmatched;
+  bool is_last_inner= join_tab == join_tab->first_unmatched->last_inner; 
+  uint count= records - (is_key_access() ? 0 : test(skip_last));
+  DBUG_ASSERT(join_tab->first_inner);
+  for ( ; count; count--)
   { 
-    if (!skip_record_if_match())
+   next:
+    if (join->thd->killed)
+    {
+      join->thd->send_kill_message();
+      return NESTED_LOOP_KILLED; // Aborted by user /* purecov: inspected */
+    }
+    if (!is_first_inner || !skip_record_if_match())
     {
       get_record();
-      join_tab->found= 1;   
       /* The outer row is complemented by nulls for each inner tables */
-      restore_record(join_tab->table,s->default_values);
+      restore_record(join_tab->table, s->default_values);
       mark_as_null_row(join_tab->table);  
       /* Check all attached conditions for inner table rows. */
-      if (select_cond && !select_cond->val_int())
+      if (join_tab->select && join_tab->select->skip_record())
         continue;
+      if (is_last_inner)
+      { 
+        JOIN_TAB *first_upper= join_tab->first_unmatched->first_upper;
+        while (first_upper)
+        {
+          if (!set_match_flag_if_none(first_upper, get_record_pos()))
+            break;
+          for (JOIN_TAB* tab= first_upper; tab <= join_tab; tab++)
+          {
+            if (tab->select && tab->select->skip_record())
+              goto next;
+          }
+          first_upper= first_upper->first_upper;
+        }
+      }
       rc= (*join_tab->next_select)(join, join_tab+1, 0);
       if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
       {
@@ -16834,6 +17174,7 @@ enum_nested_loop_state JOIN_CACHE::add_n
       }
     }
   }
+
   return rc;
 }
 
@@ -16878,7 +17219,6 @@ cmp_buffer_with_ref(JOIN_TAB *tab)
   return memcmp(tab->ref.key_buff2, tab->ref.key_buff, tab->ref.key_length)
     != 0;
 }
-
 
 bool
 cp_buffer_from_ref(THD *thd, TABLE *table, TABLE_REF *ref)
diff -Nrup a/sql/sql_select.h b/sql/sql_select.h
--- a/sql/sql_select.h	2007-10-28 02:51:28 -07:00
+++ b/sql/sql_select.h	2007-12-07 00:05:07 -08:00
@@ -205,6 +205,7 @@ typedef struct st_join_table {
   */ 
   ha_rows       limit; 
   TABLE_REF	ref;
+  bool          use_join_cache;
   JOIN_CACHE	*cache;
   SQL_SELECT    *cache_select;
   JOIN		*join;
@@ -286,6 +287,8 @@ typedef struct st_cache_field {
   uint blob_length; /* Valid IFF blob_field != 0 */
   Field_blob *blob_field;
   bool strip; /* TRUE <=> Strip endspaces ?? */
+  uint ext_key_arg_no; /* used to build keys for other BKA join caches */
+  uint offset;
   Field *field;     /* for some cache fields may be null */
 
   TABLE *get_rowid; /* _ != NULL <=> */
@@ -308,6 +311,7 @@ protected:
   uint fields;
   uint blobs;
   uint prefix_addon_fields;
+  uint ext_key_arg_fields;
   uint length;           
   uint records;          /* number of records written into the cache */
   uint record_nr; 
@@ -322,12 +326,14 @@ protected:
   uint read_record_field(CACHE_FIELD *copy, bool last_record);
   uint read_record_data(); 
   virtual uint pack_length()
-  { return length; }
+  { return length + (prev_cache ? sizeof(uchar *) : 0); }
   virtual uint addon_length()
   { return 0; }
   uchar *rec_pos;
 public:
   JOIN_TAB *join_tab;
+  JOIN_CACHE *prev_cache;
+  JOIN_CACHE *next_cache;
   bool use_match_flag;
   uint mrr_mode;
   virtual ~JOIN_CACHE() {}
@@ -337,36 +343,67 @@ public:
   uint get_record_nr() { return record_nr; }
   void set_record_nr(uint arg) { record_nr= arg; }
   bool with_length_prepanded()
- { return is_key_access() || use_match_flag; }
+  { return is_key_access() || use_match_flag || ext_key_arg_fields; }
   ulong used_blob_length();
   void free()
   { 
     x_free(buff);
     buff= 0;
   }
+  void register_ext_key_arg_field(CACHE_FIELD *copy)
+  {
+    copy->ext_key_arg_no= ++ext_key_arg_fields;
+    length+= sizeof(uint32);
+  }
+  uint get_ext_key_arg_fields()
+  { 
+    return ext_key_arg_fields;
+  }
+  bool read_ext_key_arg_field(CACHE_FIELD *copy, uchar *rec_ptr, 
+                              bool last_record, uint *len);
   virtual bool is_key_access() { return FALSE; }
   virtual int init();
   virtual void reset(bool is_for_write);    
   virtual bool put_record()= 0;
   virtual bool get_record()= 0;
-  virtual enum_nested_loop_state join_records(bool skip_last)= 0;
+  virtual void get_record_by_pos(uchar *rec_ptr)
+  {
+    uchar *save_pos= pos;
+    uint save_record_nr= record_nr;
+    record_nr= 0;
+    if (prev_cache)
+    {
+      uchar *prev_rec_pos;
+      memcpy(&prev_rec_pos, rec_ptr-sizeof(uchar *), sizeof(uchar *));
+      prev_cache->get_record_by_pos(prev_rec_pos);
+    }
+    rec_pos= pos= rec_ptr;
+    read_record_data();
+    pos= save_pos;
+    record_nr= save_record_nr;
+  }
+  enum_nested_loop_state join_records(bool skip_last);
+  bool check_match(uchar *rec_ptr);
+  virtual enum_nested_loop_state join_matching_records(bool skip_last)= 0;
+  virtual enum_nested_loop_state join_null_records(bool skip_last);
   virtual uchar *get_record_pos()
   {
     return rec_pos;
   }
   
   void set_match_flag(bool set) { (*get_record_pos())= (uchar)set; }
+  bool set_match_flag_if_none(JOIN_TAB *first_inner, uchar *rec_ptr);
   bool skip_record_if_match()
   {
     DBUG_ASSERT(use_match_flag && with_length_prepanded());
-    if (test(*(pos+sizeof(uint32))))
+    uint offset= sizeof(uint32) + (prev_cache ? sizeof(uchar *) : 0);
+    if (test(*(pos+offset)))
     {
       pos+= sizeof(uint32) + uint4korr(pos);
       return TRUE;
     }
     return FALSE;
-  }
-  enum_nested_loop_state add_null_complemented_records(uint count);      
+  }      
     
 };
 
@@ -377,6 +414,16 @@ public:
   { 
     join= j;
     join_tab= tab;
+    prev_cache= next_cache= 0;
+  }
+  JOIN_CACHE_BNL(JOIN *j, JOIN_TAB *tab, JOIN_CACHE *prev)
+  { 
+    join= j;
+    join_tab= tab;
+    prev_cache= prev;
+    next_cache= 0;
+    if (prev)
+      prev->next_cache= this;
   }
   bool put_record()
   { 
@@ -386,18 +433,30 @@ public:
   }
   bool get_record()
   { 
+    bool res;
     if (with_length_prepanded())
       pos+= sizeof(uint32);
+    if (prev_cache)
+    {
+      uchar *prev_rec_pos;
+      memcpy(&prev_rec_pos, pos, sizeof(uchar *));
+      pos+= sizeof(uchar *);
+      prev_cache->get_record_by_pos(prev_rec_pos);
+    }
     rec_pos= pos;
-    return read_record_data() == 0; 
+    res= read_record_data() == 0;
+    if (ext_key_arg_fields)
+      pos+= sizeof(uint32)*ext_key_arg_fields;
+    return res; 
   }
-  enum_nested_loop_state join_records(bool skip_last);
+  enum_nested_loop_state join_matching_records(bool skip_last);
 };
 
 class JOIN_CACHE_BKA :public JOIN_CACHE
 {
 protected:
-  uint key_arg_fields;
+  uint local_key_arg_fields;
+  uint global_key_arg_fields;
   HANDLER_BUFFER mrr_buff;
 public:
   bool use_emb_key;
@@ -407,9 +466,19 @@ public:
   { 
     join= j;
     join_tab= tab;
+    prev_cache= next_cache= 0;
+  }
+  JOIN_CACHE_BKA(JOIN *j, JOIN_TAB *tab, JOIN_CACHE* prev)
+  { 
+    join= j;
+    join_tab= tab;
+    prev_cache= prev;
+    next_cache= 0;
+    if (prev)
+      prev->next_cache= this;
   }
   uint pack_length()
-  { return length+sizeof(uint32); }
+  { return JOIN_CACHE::pack_length() + sizeof(uint32); }
   uint addon_length()
   { 
     TABLE_REF *ref= &join_tab->ref;
@@ -438,9 +507,20 @@ public:
   }
   bool get_record()
   { 
+    bool res;
     pos+= sizeof(uint32);
+    if (prev_cache)
+    {
+      uchar *prev_rec_pos;
+      memcpy(&prev_rec_pos, pos, sizeof(uchar *));
+      pos+= sizeof(uchar *);
+      prev_cache->get_record_by_pos(prev_rec_pos);
+    }    
     rec_pos= pos;
-    return read_record_data() == 0;
+    res= read_record_data() == 0;
+    if (ext_key_arg_fields)
+      pos+= sizeof(uint32)*ext_key_arg_fields;
+    return res; 
   }
   bool is_key_access() { return TRUE; }
   int init()
@@ -448,9 +528,23 @@ public:
     int res= JOIN_CACHE::init();
     return res;
   }
-  void set_key_arg_count(uint cnt) 
+  void incr_key_arg_fields(uint d, bool is_local_cnt)
   {
-    key_arg_fields= cnt;
+    if (is_local_cnt)
+      local_key_arg_fields+= d;
+    else
+      global_key_arg_fields+= d;
+  }
+  uint get_key_arg_fields(bool is_local_cnt)
+  {
+    return is_local_cnt ? local_key_arg_fields : global_key_arg_fields;
+  }
+  void set_key_arg_fields(bool is_local_cnt, uint cnt)
+  {
+    if (is_local_cnt) 
+      local_key_arg_fields= cnt;
+    else
+      global_key_arg_fields= cnt;
   }
   bool check_emb_key_usage();
   virtual void reset(bool is_for_write)
@@ -460,17 +554,6 @@ public:
       end_pos= end;
   }
   virtual uint get_next_key(uchar **key);    
-  virtual void get_record_by_pos(uchar *rec_ptr)
-  {
-    uchar *save_pos= pos;
-    uint save_record_nr= record_nr;
-    pos= rec_ptr;
-    rec_pos= pos;
-    record_nr= 0;
-    read_record_data();
-    pos= save_pos;
-    record_nr= save_record_nr;
-  }
   virtual void init_mrr_buff()
   {
     mrr_buff.buffer= end_pos;
@@ -478,7 +561,7 @@ public:
   }
   virtual bool get_match_flag_by_pos(uchar *rec_pos)
   { return test(*rec_pos); }
-  enum_nested_loop_state join_records(bool skip_last);
+  enum_nested_loop_state join_matching_records(bool skip_last);
 };
 
 enum_nested_loop_state sub_select_cache(JOIN *join, JOIN_TAB *join_tab, bool
Thread
bk commit into 5.2 tree (igor:1.2593)igor7 Dec