MySQL Bugs: #38687: AND optimization done without regard to memory consumption

Bug #38687	AND optimization done without regard to memory consumption
Submitted:	9 Aug 2008 1:05	Modified:	14 Aug 2008 20:58
Reporter:	Mark Callaghan	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S2 (Serious)
Version:	5.0	OS:	Any
Assigned to:		CPU Architecture:	Any
Tags:	and, Optimizer, query

Description:
We have a query with a large and complex WHERE clause. It looks like:

WHERE   a.Date >= '2008-06-01' AND a.Date <= '2008-06-30' AND   a.Type = 'Content' AND   a.B = 'Foo' AND (a.CT BETWEEN 0 AND 9 OR a.ConversionType > 1000000) AND   a.DF IN ('586811614135908873','1154364634047097544', ...

There are many values in the in-list. The query text was ~500k. This caused the server to run out of memory meaning the optimizer used about 10GB and wanted more.

The call stack for the point at which the optimizer allocated 1G from the MEM_ROOT used for this query:

#3  0x0000000000905925 in alloc_root (mem_root=0x4708cf10, Size=96) at my_alloc.c:208
#4  0x000000000059af2b in sql_alloc (Size=96) at thr_malloc.cc:41
#5  0x0000000000529adf in Sql_alloc::operator new (size=96) at sql_list.h:28
#6  0x00000000006d544a in SEL_ARG::clone (this=0x2aab137592e8, new_parent=0x2aab4e6850b0, next_arg=0x4708a820) at opt_range.cc:1375
#7  0x00000000006d555c in SEL_ARG::clone (this=0x2aab138a6578, new_parent=0x2aab4e685050, next_arg=0x4708a820) at opt_range.cc:1388
#8  0x00000000006d5503 in SEL_ARG::clone (this=0x2aab1357a060, new_parent=0x2aab4e684ff0, next_arg=0x4708a820) at opt_range.cc:1381
#9  0x00000000006d5503 in SEL_ARG::clone (this=0x2aab134a2870, new_parent=0x2aab4e684b10, next_arg=0x4708a820) at opt_range.cc:1381
#10 0x00000000006d555c in SEL_ARG::clone (this=0x2aab135f0b38, new_parent=0x2aab4e684150, next_arg=0x4708a820) at opt_range.cc:1388
#11 0x00000000006d555c in SEL_ARG::clone (this=0x2aab13437518, new_parent=0x2aab4e6840f0, next_arg=0x4708a820) at opt_range.cc:1388
#12 0x00000000006d5503 in SEL_ARG::clone (this=0x2aab133d2810, new_parent=0x2aab4e684090, next_arg=0x4708a820) at opt_range.cc:1381
#13 0x00000000006d5503 in SEL_ARG::clone (this=0x2aab134158b0, new_parent=0x2aab4e684030, next_arg=0x4708a820) at opt_range.cc:1381
#14 0x00000000006d5503 in SEL_ARG::clone (this=0x2aab13384968, new_parent=0x2aab4e67ca70, next_arg=0x4708a820) at opt_range.cc:1381
#15 0x00000000006d555c in SEL_ARG::clone (this=0x2aab1337d328, new_parent=0x2aab4e672990, next_arg=0x4708a820) at opt_range.cc:1388
#16 0x00000000006d555c in SEL_ARG::clone (this=0x2aab133792a8, new_parent=0x2aab4e672930, next_arg=0x4708a820) at opt_range.cc:1388
#17 0x00000000006d5503 in SEL_ARG::clone (this=0x2aab1336a628, new_parent=0x2aab4e63a650, next_arg=0x4708a820) at opt_range.cc:1381
#18 0x00000000006d555c in SEL_ARG::clone (this=0x2aab13367860, new_parent=0x2aab4e5e03b0, next_arg=0x4708a820) at opt_range.cc:1388
#19 0x00000000006d555c in SEL_ARG::clone (this=0x2aab13369b78, new_parent=0x2aab4e545eb0, next_arg=0x4708a820) at opt_range.cc:1388
#20 0x00000000006d555c in SEL_ARG::clone (this=0x2aab13366af0, new_parent=0x0, next_arg=0x4708a820) at opt_range.cc:1388
#21 0x00000000006d55fb in SEL_ARG::clone_tree (this=0x2aab13366af0) at opt_range.cc:1470
#22 0x00000000006d6537 in key_and (key1=0x2aab13366af0, key2=0x2aab123b2380, clone_flag=3) at opt_range.cc:4731
#23 0x00000000006d69f5 in and_all_keys (key1=0x2aab131d9560, key2=0x2aab13366af0, clone_flag=3) at opt_range.cc:4681
#24 0x00000000006d6564 in key_and (key1=0x2aab131d9560, key2=0x2aab13366af0, clone_flag=3) at opt_range.cc:4733
#25 0x00000000006d69f5 in and_all_keys (key1=0x2aab123b3d08, key2=0x2aab13366af0, clone_flag=3) at opt_range.cc:4681
#26 0x00000000006d6564 in key_and (key1=0x2aab123b3d08, key2=0x2aab13366af0, clone_flag=3) at opt_range.cc:4733
#27 0x00000000006d69f5 in and_all_keys (key1=0x2aab123b2070, key2=0x2aab13366af0, clone_flag=3) at opt_range.cc:4681
#28 0x00000000006d6564 in key_and (key1=0x2aab123b2070, key2=0x2aab13366af0, clone_flag=3) at opt_range.cc:4733
#29 0x00000000006d6d0d in tree_and (param=0x4708ad50, tree1=0x2aab123b29f8, tree2=0x2aab133665f0) at opt_range.cc:4523
#30 0x00000000006e0e63 in get_mm_tree (param=0x4708ad50, cond=0x2aab122d44a8) at opt_range.cc:3936
#31 0x00000000006e5d11 in SQL_SELECT::test_quick_select (this=0x2aab122d5a88, thd=0x2aab11a3d000, keys_to_use={map = 3}, prev_tables=0,
   limit=18446744073709551615, force_quick_range=false) at opt_range.cc:1965
#32 0x0000000000658cf7 in get_quick_record_count (thd=0x2aab11a3d000, select=0x2aab122d5a88, table=0x2aab11af9000, keys=0x2aab122d4970,
   limit=18446744073709551615) at sql_select.cc:2143
#33 0x000000000066e4c9 in make_join_statistics (join=0x2aab122d2b18, tables=0x0, conds=0x2aab122d44a8, keyuse_array=0x2aab122d3cf0)
   at sql_select.cc:2540
#34 0x000000000066f568 in JOIN::optimize (this=0x2aab122d2b18) at sql_select.cc:776

How to repeat:
Unfortunately, I won't give you the DDL and full query.

Suggested fix:
Limit the amount of memory (or CPU time) that can be used by the optimizer for a query.

Making matters worse, it looks like this code only partially handles OOM errors as all callers of SEL_ARG::clone do not check that the return is NULL. Is it OK not to check or will that lead to a segfault later?

SEL_ARG *SEL_ARG::clone(SEL_ARG *new_parent,SEL_ARG **next_arg)
{
  SEL_ARG *tmp;
  if (type != KEY_RANGE)
  {
    if (!(tmp= new SEL_ARG(type)))
      return 0;         // out of memory
    tmp->prev= *next_arg;     // Link into next/prev chain
    (*next_arg)->next=tmp;
    (*next_arg)= tmp;
  }
  else
  {
    if (!(tmp= new SEL_ARG(field,part, min_value,max_value,
         min_flag, max_flag, maybe_flag)))
      return 0;         // OOM
    tmp->parent=new_parent;
    tmp->next_key_part=next_key_part;
    if (left != &null_element)
      tmp->left=left->clone(tmp,next_arg);   <-- does not check for OOM

    tmp->prev= *next_arg;     // Link into next/prev chain
    (*next_arg)->next=tmp;
    (*next_arg)= tmp;

    if (right != &null_element)
      if (!(tmp->right= right->clone(tmp,next_arg)))
  return 0;       // OOM
  }
  increment_use_count(1);
  tmp->color= color;
  tmp->elements= this->elements;
  return tmp;
}

When alloc_root fails because I hardwired it to fail if a heap used more than 1GB, the server dies here.

  void sql_alloc_error_handler(void)
  {
    THD *thd=current_thd;
    if (thd)          // QQ;  To be removed
      thd->fatal_error();     /* purecov: inspected */
    sql_print_error(ER(ER_OUT_OF_RESOURCES));
  }
}

SEL_ARG::clone_tree() might be a good place to check for excessive memory usage and return NULL.

Where else might the problem occur?

When I hardwire my_alloc.c to fail (return NULL) when a given heap uses more than X MB of memory, the overloaded new operators that use sql_alloc cause the program to terminate. If the overloaded new operators used 'throw()' then they would return NULL. I doubt that is a better thing to do given the numerous uses of new in mysql source where the caller does not check for NULL on return.

My fix is:
1) SEL_ARG::clone_tree checks for too many bytes allocated from the MEM_ROOT for the THD and fails if that is the case.
2) MEM_ROOT counts the number of bytes allocated per heap and fails when limit has been exceeded.

The limit for 1) should be less than the limit for 2) to avoid a crash because there is a crash when 2) occurs.

Please see related bug#38296

While 38296 is about the parser, this bug is about the optimizer.
Both have the same root cause: robustness of the code in case of OOM.

Probably related to bug #38006 also.

This may have been fixed in MySQL 5.1 with the addition of MAX_SEL_ARGS to opt_range.cc

And this also appears to be fixed in recent 5.0 versions. Alas, I still use 5.0.37 with a lot of backports.

This bug is a duplicate of Bug #26624.