Fixed bug mdev-10454.

The patch actually fixes the old defect of the optimizer that
could not extract keys for range access from IN predicates
with row arguments.

This problem was resolved in the mysql-5.7 code. The patch
supersedes what was done there:
 - it can build range access when not all components of
 the first row argument are refer to the columns of the table
 for which the range access is constructed.
 - it can use equality predicates to build range access
 to the table that is not referred to in this argument.

1 files changed, 213 insertions, 4 deletions

diff --git a/sql/opt_range.cc b/sql/opt_range.cc
index 6d088cad91e..d5de96b860a 100644
--- a/sql/opt_range.cc
+++ b/sql/opt_range.cc
@@ -7211,6 +7211,205 @@ SEL_TREE *Item_func_in::get_func_mm_tree(RANGE_OPT_PARAM *param,
 
 
 /*
+  The structure Key_col_info is purely  auxiliary and is used
+  only in the method Item_func_in::get_func_row_mm_tree
+*/ 
+struct Key_col_info {
+  Field *field;         /* If != NULL the column can be used for keys */
+  cmp_item *comparator; /* If != 0 the column can be evaluated        */
+};
+
+/**
+    Build SEL_TREE for the IN predicate whose arguments are rows 
+
+    @param param          PARAM from SQL_SELECT::test_quick_select
+    @param key_row        First operand of the IN predicate
+
+  @note
+    The function builds a SEL_TREE for in IN predicate in the case
+    when the predicate uses row arguments. First the function
+    detects among the components of the key_row (c[1],...,c[n]) taken 
+    from in the left part the predicate those that can be usable
+    for building SEL_TREE (c[i1],...,c[ik]).  They have to contain
+    items whose real items are  field items referring to the current
+    table or equal to the items referring to the current table.
+    For the remaining components of the row it checks whether they
+    can be evaluated. The result of the analysis is put into the
+    array of structures of the type Key_row_col_info.
+
+    After this the function builds the SEL_TREE for the following 
+    formula that can be inferred from the given IN predicate:
+      c[i11]=a[1][i11] AND ... AND c[i1k1]=a[1][i1k1]
+      OR   
+      ...
+      OR
+      c[im1]=a[m][im1] AND ... AND c[imkm]=a[m][imkm].
+    Here a[1],...,a[m] are all arguments of the IN predicate from
+    the right part and for each j ij1,...,ijkj is a subset of
+    i1,...,ik such that a[j][ij1],...,a[j][ijkj] can be evaluated.
+
+    If for some j there no a[j][i1],...,a[j][ik] can be evaluated
+    then no SEL_TREE can be built for this predicate and the
+    function immediately returns 0.
+
+    If for some j by using evaluated values of key_row it can be
+    proven that c[ij1]=a[j][ij1] AND ... AND c[ijkj]=a[j][ijkj]
+    is always FALSE then this disjunct is omitted. 
+
+  @returns
+    the built SEL_TREE if it can be constructed
+    0 - otherwise.
+*/
+
+SEL_TREE *Item_func_in::get_func_row_mm_tree(RANGE_OPT_PARAM *param,
+                                             Item_row *key_row)
+{
+  DBUG_ENTER("Item_func_in::get_func_row_mm_tree");
+
+  if (negated)
+    DBUG_RETURN(0);
+
+  SEL_TREE *res_tree= 0;
+  uint used_key_cols= 0;
+  uint col_comparators= 0;
+  table_map param_comp= ~(param->prev_tables | param->read_tables |
+                          param->current_table);
+  uint row_cols= key_row->cols();
+  Dynamic_array <Key_col_info> key_cols_info(row_cols);
+  cmp_item_row *row_cmp_item= (cmp_item_row *)
+                              (array ? ((in_row *) array)->get_cmp_item() :
+			               cmp_items[(uint) ROW_RESULT]);
+
+  Item **key_col_ptr= key_row->addr(0);
+  for(uint i= 0; i < row_cols;  i++, key_col_ptr++)
+  {
+    Key_col_info key_col_info= {0, NULL};
+    Item *key_col= *key_col_ptr;
+    if (key_col->real_item()->type() == Item::FIELD_ITEM)
+    {
+      /*
+        The i-th component of key_row can be used for key access if 
+        key_col->real_item() points to a field of the current table or
+        if it is equal to a field item pointing to such a field.
+      */
+      Item_field *col_field_item= (Item_field *) (key_col->real_item());
+      Field *key_col_field= col_field_item->field;
+      if (key_col_field->table->map != param->current_table)
+      {
+        Item_equal *item_equal= col_field_item->item_equal;
+        if (item_equal)
+        {
+          Item_equal_fields_iterator it(*item_equal);
+          while (it++)
+	  {
+            key_col_field= it.get_curr_field();
+            if (key_col_field->table->map == param->current_table)
+              break;
+          }
+        }
+      }
+      if (key_col_field->table->map == param->current_table)
+      {
+        key_col_info.field= key_col_field;
+        used_key_cols++;
+      }
+    }
+    else if (!(key_col->used_tables() & (param_comp | param->current_table))
+             && !key_col->is_expensive())
+    {
+      /* The i-th component of key_row can be evaluated */
+
+      /* See the comment in Item::get_mm_tree_for_const */
+      MEM_ROOT *tmp_root= param->mem_root;
+      param->thd->mem_root= param->old_root;
+
+      key_col->bring_value();
+      key_col_info.comparator= row_cmp_item->get_comparator(i);
+      key_col_info.comparator->store_value(key_col);
+      col_comparators++;
+
+      param->thd->mem_root= tmp_root;
+    }
+    key_cols_info.push(key_col_info);
+  }
+
+  if (!used_key_cols)
+    DBUG_RETURN(0);
+
+  uint omitted_tuples= 0;
+  Item **arg_start= arguments() + 1;
+  Item **arg_end= arg_start + argument_count() - 1;
+  for (Item **arg= arg_start ; arg < arg_end; arg++)
+  {
+    uint i;
+   
+    /* 
+      First check whether the disjunct constructed for *arg
+      is really needed
+    */  
+    Item_row *arg_tuple= (Item_row *) (*arg);
+    if (col_comparators)
+    {
+      MEM_ROOT *tmp_root= param->mem_root;
+      param->thd->mem_root= param->old_root;
+      for (i= 0; i < row_cols; i++)
+      {
+        Key_col_info *key_col_info= &key_cols_info.at(i);
+        if (key_col_info->comparator)
+	{
+          Item *arg_col= arg_tuple->element_index(i);
+          if (!(arg_col->used_tables() & (param_comp | param->current_table)) &&
+	      !arg_col->is_expensive() &&
+              key_col_info->comparator->cmp(arg_col))
+	  {
+            omitted_tuples++;
+            break;
+          }
+        }
+      }
+      param->thd->mem_root= tmp_root;
+      if (i < row_cols)
+        continue;
+    }
+    
+    /* The disjunct for *arg is needed: build it. */     
+    SEL_TREE *and_tree= 0;
+    Item **arg_col_ptr= arg_tuple->addr(0);
+    for (uint i= 0; i < row_cols; i++, arg_col_ptr++)
+    { 
+      Key_col_info *key_col_info= &key_cols_info.at(i);
+      if (!key_col_info->field)
+        continue;
+      Item *arg_col= *arg_col_ptr;
+      if (!(arg_col->used_tables() & (param_comp | param->current_table)) &&
+	  !arg_col->is_expensive())
+      {
+        and_tree= tree_and(param, and_tree, 
+                           get_mm_parts(param,
+                                        key_col_info->field, 
+                                        Item_func::EQ_FUNC,
+                                        arg_col->real_item()));
+      }
+    }
+    if (!and_tree)
+    {
+      res_tree= 0;
+      break;
+    }
+    /* Join the disjunct the the OR tree that is being constructed */
+    res_tree= !res_tree ? and_tree : tree_or(param, res_tree, and_tree);
+  }
+  if (omitted_tuples == argument_count() - 1)
+  {
+    /* It's turned out that all disjuncts are always FALSE */
+    res_tree= new (param->mem_root) SEL_TREE(SEL_TREE::IMPOSSIBLE,
+                                             param->mem_root, param->keys);
+  }
+  DBUG_RETURN(res_tree);
+}
+
+
+/*
   Build conjunction of all SEL_TREEs for a simple predicate applying equalities
  
   SYNOPSIS
@@ -7544,12 +7743,22 @@ SEL_TREE *Item_func_in::get_mm_tree(RANGE_OPT_PARAM *param, Item **cond_ptr)
   if (const_item())
     DBUG_RETURN(get_mm_tree_for_const(param));
 
-  if (key_item()->real_item()->type() != Item::FIELD_ITEM)
+  SEL_TREE *tree= 0;
+  switch (key_item()->real_item()->type()) {
+  case Item::FIELD_ITEM:
+    tree= get_full_func_mm_tree(param,
+                                (Item_field*) (key_item()->real_item()),
+                                NULL);
+    break;
+  case Item::ROW_ITEM:
+    tree= get_func_row_mm_tree(param,
+			       (Item_row *) (key_item()->real_item()));
+    break;
+  default:
     DBUG_RETURN(0);
-  Item_field *field= (Item_field*) (key_item()->real_item());
-  SEL_TREE *tree= get_full_func_mm_tree(param, field, NULL);
+  } 
   DBUG_RETURN(tree);
-}
+} 
 
 
 SEL_TREE *Item_equal::get_mm_tree(RANGE_OPT_PARAM *param, Item **cond_ptr)