BUG#15872: Don't run the range analyzer on "t1.keypart NOT IN (const1, ..., )", as that consumes

too much memory. Instead, either create the equvalent SEL_TREE manually, or create only two ranges that
strictly include the area to scan
(Note: just to re-iterate: increasing NOT_IN_IGNORE_THRESHOLD will make optimization run slower for big 
IN-lists, but the server will not run out of memory. O(N^2) memory use has been eliminated)


mysql-test/r/func_in.result:
  Testcase for BUG#15872
mysql-test/t/func_in.test:
  Testcase for BUG#15872
sql/item.cc:
  BUG#15872: Added Item_decimal::set_decimal_value()
sql/item.h:
  UG#15872: Added Item_decimal::set_decimal_value()
sql/item_cmpfunc.h:
  BUG#15872: Added in_vector::create_item(), in_vector::value_to_item() and their implementations in concrete
  classes.
sql/opt_range.cc:
  BUG#15872: Don't run the range analyzer on "t1.keypart NOT IN (const1, ..., )", as that 
  consumes too much memory. Instead, either 
   A) create the equivalent SEL_TREE manually, making use of the fact that item_not_in->array
      has an ordered IN-list, or
   B) create only two ranges: (-inf|NULL) < X < min_value_from_in_list,  max_value_from_in_list < X
  (Choose #B if the IN-list has > 10K elements)

1 files changed, 84 insertions, 9 deletions

diff --git a/sql/opt_range.cc b/sql/opt_range.cc
index ae02bb8934c..2610e4fc1c8 100644
--- a/sql/opt_range.cc
+++ b/sql/opt_range.cc
@@ -3501,17 +3501,92 @@ static SEL_TREE *get_func_mm_tree(PARAM *param, Item_func *cond_func,
 
     if (inv)
     {
-      tree= get_ne_mm_tree(param, cond_func, field,
-                           func->arguments()[1], func->arguments()[1],
-                           cmp_type);
-      if (tree)
+      /*
+        We get here for conditions like "t.keypart NOT IN (....)".
+        
+        If the IN-list contains only constants (and func->array is an ordered
+        array of them), we construct the appropriate SEL_ARG tree manually, 
+        because constructing it using the range analyzer (as 
+        AND_i( t.keypart != c_i)) will cause lots of memory to be consumed
+        (see BUG#15872). 
+      */
+      if (func->array && func->cmp_type != ROW_RESULT)
       {
-        Item **arg, **end;
-        for (arg= func->arguments()+2, end= arg+func->argument_count()-2;
-             arg < end ; arg++)
+        /* 
+          Create one Item_type constant object. We'll need it as
+          get_mm_parts only accepts constant values wrapped in Item_Type
+          objects.
+          We create the Item on param->mem_root which points to
+          per-statement mem_root (while thd->mem_root is currently pointing
+          to mem_root local to range optimizer).
+        */
+        MEM_ROOT *tmp_root= param->mem_root;
+        param->thd->mem_root= param->old_root;
+        Item *value_item= func->array->create_item();
+        param->thd->mem_root= tmp_root;
+
+        if (!value_item)
+          break;
+        
+        /* Get a SEL_TREE for "-inf < X < c_0" interval */
+        func->array->value_to_item(0, value_item);
+        tree= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
+                           value_item, cmp_type);
+        if (!tree)
+          break;
+#define NOT_IN_IGNORE_THRESHOLD 1000        
+        SEL_TREE *tree2;
+        if (func->array->count < NOT_IN_IGNORE_THRESHOLD)
+        {
+          for (uint i=1; i < func->array->count; i++)
+          {
+            if (func->array->compare_elems(i, i-1))
+            {
+              /* Get a SEL_TREE for "-inf < X < c_i" interval */
+              func->array->value_to_item(i, value_item);
+              tree2= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
+                                  value_item, cmp_type);
+              
+              /* Change all intervals to be "c_{i-1} < X < c_i" */
+              for (uint idx= 0; idx < param->keys; idx++)
+              {
+                SEL_ARG *new_interval;
+                if ((new_interval=  tree2->keys[idx]))
+                {
+                  SEL_ARG *last_val= tree->keys[idx]->last();
+                  new_interval->min_value= last_val->max_value;
+                  new_interval->min_flag= NEAR_MIN;
+                }
+              }
+              tree= tree_or(param, tree, tree2);
+            }
+          }
+        }
+        else
+          func->array->value_to_item(func->array->count - 1, value_item);
+
+        /* 
+          Get the SEL_TREE for the last "c_last < X < +inf" interval 
+          (value_item cotains c_last already)
+        */
+        tree2= get_mm_parts(param, cond_func, field, Item_func::GT_FUNC,
+                            value_item, cmp_type);
+        tree= tree_or(param, tree, tree2);
+      }
+      else
+      {
+        tree= get_ne_mm_tree(param, cond_func, field,
+                             func->arguments()[1], func->arguments()[1],
+                             cmp_type);
+        if (tree)
         {
-          tree=  tree_and(param, tree, get_ne_mm_tree(param, cond_func, field, 
-                                                      *arg, *arg, cmp_type));
+          Item **arg, **end;
+          for (arg= func->arguments()+2, end= arg+func->argument_count()-2;
+               arg < end ; arg++)
+          {
+            tree=  tree_and(param, tree, get_ne_mm_tree(param, cond_func, field, 
+                                                        *arg, *arg, cmp_type));
+          }
         }
       }
     }