From ec3de56263e748603b954e29ca35bacb3e386176 Mon Sep 17 00:00:00 2001 From: unknown Date: Tue, 27 Mar 2007 09:48:10 -0700 Subject: Fixed bug #27348. If a set function with a outer reference s(outer_ref) cannot be aggregated the outer query against which the reference has been resolved then MySQL interpretes s(outer_ref) in the same way as it would interpret s(const). Hovever the standard requires throwing an error in this situation. Added some code to support this requirement in ansi mode. Corrected another minor bug in Item_sum::check_sum_func. mysql-test/r/subselect.result: Added a test case for bug #27348. mysql-test/t/subselect.test: Added a test case for bug #27348. sql/item_sum.cc: Fixed bug #27348. If a set function with a outer reference s(outer_ref) cannot be aggregated the outer query against which the reference has been resolved then MySQL interprets s(outer_ref) in the same way as it would interpret s(const). Hovever the standard requires throwing an error in this situation. Added some code to support this requirement in ansi mode. Corrected another minor bug in Item_sum::check_sum_func. --- mysql-test/r/subselect.result | 23 +++++++++++++++++++++++ mysql-test/t/subselect.test | 27 +++++++++++++++++++++++++++ sql/item_sum.cc | 7 +++++-- 3 files changed, 55 insertions(+), 2 deletions(-) diff --git a/mysql-test/r/subselect.result b/mysql-test/r/subselect.result index 81f087fe8fa..d5a1c0b2451 100644 --- a/mysql-test/r/subselect.result +++ b/mysql-test/r/subselect.result @@ -3924,3 +3924,26 @@ c a (SELECT GROUP_CONCAT(COUNT(a)+1) FROM t2 WHERE m = a) 3 3 4 1 4 2,2 DROP table t1,t2; +CREATE TABLE t1 (a int, b int); +INSERT INTO t1 VALUES (2,22),(1,11),(2,22); +SELECT a FROM t1 WHERE (SELECT COUNT(b) FROM DUAL) > 0 GROUP BY a; +a +1 +2 +SELECT a FROM t1 WHERE (SELECT COUNT(b) FROM DUAL) > 1 GROUP BY a; +a +SELECT a FROM t1 t0 +WHERE (SELECT COUNT(t0.b) FROM t1 t WHERE t.b>20) GROUP BY a; +a +1 +2 +SET @@sql_mode='ansi'; +SELECT a FROM t1 WHERE (SELECT COUNT(b) FROM DUAL) > 0 GROUP BY a; +ERROR HY000: Invalid use of group function +SELECT a FROM t1 WHERE (SELECT COUNT(b) FROM DUAL) > 1 GROUP BY a; +ERROR HY000: Invalid use of group function +SELECT a FROM t1 t0 +WHERE (SELECT COUNT(t0.b) FROM t1 t WHERE t.b>20) GROUP BY a; +ERROR HY000: Invalid use of group function +SET @@sql_mode=default; +DROP TABLE t1; diff --git a/mysql-test/t/subselect.test b/mysql-test/t/subselect.test index efd54ca95d1..182b9b27ef7 100644 --- a/mysql-test/t/subselect.test +++ b/mysql-test/t/subselect.test @@ -2782,3 +2782,30 @@ SELECT COUNT(*) c, a, FROM t1 GROUP BY a; DROP table t1,t2; + +# +# Bug #27348: SET FUNCTION used in a subquery from WHERE condition +# + +CREATE TABLE t1 (a int, b int); +INSERT INTO t1 VALUES (2,22),(1,11),(2,22); + +SELECT a FROM t1 WHERE (SELECT COUNT(b) FROM DUAL) > 0 GROUP BY a; +SELECT a FROM t1 WHERE (SELECT COUNT(b) FROM DUAL) > 1 GROUP BY a; + +SELECT a FROM t1 t0 + WHERE (SELECT COUNT(t0.b) FROM t1 t WHERE t.b>20) GROUP BY a; + +SET @@sql_mode='ansi'; +--error 1111 +SELECT a FROM t1 WHERE (SELECT COUNT(b) FROM DUAL) > 0 GROUP BY a; +--error 1111 +SELECT a FROM t1 WHERE (SELECT COUNT(b) FROM DUAL) > 1 GROUP BY a; + +--error 1111 +SELECT a FROM t1 t0 + WHERE (SELECT COUNT(t0.b) FROM t1 t WHERE t.b>20) GROUP BY a; + +SET @@sql_mode=default; + +DROP TABLE t1; diff --git a/sql/item_sum.cc b/sql/item_sum.cc index 368dc9a7d38..e10357dc0e0 100644 --- a/sql/item_sum.cc +++ b/sql/item_sum.cc @@ -149,6 +149,8 @@ bool Item_sum::check_sum_func(THD *thd, Item **ref) if (register_sum_func(thd, ref)) return TRUE; invalid= aggr_level < 0 && !(allow_sum_func & (1 << nest_level)); + if (!invalid && thd->variables.sql_mode & MODE_ANSI) + invalid= aggr_level < 0 && max_arg_level < nest_level; } if (!invalid && aggr_level < 0) { @@ -164,8 +166,9 @@ bool Item_sum::check_sum_func(THD *thd, Item **ref) Additionally we have to check whether possible nested set functions are acceptable here: they are not, if the level of aggregation of some of them is less than aggr_level. - */ - invalid= aggr_level <= max_sum_func_level; + */ + if (!invalid) + invalid= aggr_level <= max_sum_func_level; if (invalid) { my_message(ER_INVALID_GROUP_FUNC_USE, ER(ER_INVALID_GROUP_FUNC_USE), -- cgit v1.2.1 From 425304f5626a2b2a0fc2ada1e0f306a3465341b4 Mon Sep 17 00:00:00 2001 From: unknown Date: Wed, 28 Mar 2007 18:38:42 +0400 Subject: BUG#26625: crash in range optimizer (out of mem) - Define Sql_alloc::operator new() as thow() so that C++ compiler handles NULL return values (there is no testcase as there is no portable way to set limit on the amount of memory that a process can allocate) sql/sql_list.h: BUG#26625: crash in range optimizer (out of mem) - Define Sql_alloc::operator new() as thow() so that C++ compiler handles NULL return values --- sql/sql_list.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/sql/sql_list.h b/sql/sql_list.h index 47379ab1ddf..2075361a398 100644 --- a/sql/sql_list.h +++ b/sql/sql_list.h @@ -30,7 +30,7 @@ class Sql_alloc { public: - static void *operator new(size_t size) + static void *operator new(size_t size) throw () { return (void*) sql_alloc((uint) size); } @@ -38,7 +38,7 @@ public: { return (void*) sql_alloc((uint) size); } - static void *operator new(size_t size, MEM_ROOT *mem_root) + static void *operator new(size_t size, MEM_ROOT *mem_root) throw () { return (void*) alloc_root(mem_root, (uint) size); } static void operator delete(void *ptr, size_t size) { TRASH(ptr, size); } static void operator delete(void *ptr, MEM_ROOT *mem_root) -- cgit v1.2.1 From 60189d3512798b054220f65468cddce88f8c3166 Mon Sep 17 00:00:00 2001 From: unknown Date: Wed, 28 Mar 2007 19:05:30 +0400 Subject: Delete: sql/mysqld.cc.rej --- sql/mysqld.cc.rej | 161 ------------------------------------------------------ 1 file changed, 161 deletions(-) delete mode 100644 sql/mysqld.cc.rej diff --git a/sql/mysqld.cc.rej b/sql/mysqld.cc.rej deleted file mode 100644 index bd7338143ae..00000000000 --- a/sql/mysqld.cc.rej +++ /dev/null @@ -1,161 +0,0 @@ -*************** -*** 177,188 **** - } /* cplusplus */ - - -- #if defined(HAVE_LINUXTHREADS) -- #define THR_KILL_SIGNAL SIGINT -- #else -- #define THR_KILL_SIGNAL SIGUSR2 // Can't use this with LinuxThreads -- #endif -- - #ifdef HAVE_GLIBC2_STYLE_GETHOSTBYNAME_R - #include - #else ---- 177,182 ---- - } /* cplusplus */ - - - #ifdef HAVE_GLIBC2_STYLE_GETHOSTBYNAME_R - #include - #else -*************** -*** 505,510 **** - static void clean_up_mutexes(void); - static int test_if_case_insensitive(const char *dir_name); - static void create_pid_file(); - - /**************************************************************************** - ** Code to end mysqld ---- 499,505 ---- - static void clean_up_mutexes(void); - static int test_if_case_insensitive(const char *dir_name); - static void create_pid_file(); -+ static uint get_thread_lib(void); - - /**************************************************************************** - ** Code to end mysqld -*************** -*** 544,550 **** - DBUG_PRINT("info",("Waiting for select_thread")); - - #ifndef DONT_USE_THR_ALARM -! if (pthread_kill(select_thread,THR_CLIENT_ALARM)) - break; // allready dead - #endif - set_timespec(abstime, 2); ---- 539,546 ---- - DBUG_PRINT("info",("Waiting for select_thread")); - - #ifndef DONT_USE_THR_ALARM -! if (pthread_kill(select_thread, -! thd_lib_detected == THD_LIB_LT ? SIGALRM : SIGUSR1)) - break; // allready dead - #endif - set_timespec(abstime, 2); -*************** -*** 844,850 **** - sig,my_thread_id()); - } - #ifdef DONT_REMEMBER_SIGNAL -! sigset(sig,print_signal_warning); /* int. thread system calls */ - #endif - #if !defined(__WIN__) && !defined(OS2) && !defined(__NETWARE__) - if (sig == SIGALRM) ---- 840,846 ---- - sig,my_thread_id()); - } - #ifdef DONT_REMEMBER_SIGNAL -! my_sigset(sig, print_signal_warning); /* int. thread system calls */ - #endif - #if !defined(__WIN__) && !defined(OS2) && !defined(__NETWARE__) - if (sig == SIGALRM) -*************** -*** 1841,1848 **** - DBUG_ENTER("init_signals"); - - if (test_flags & TEST_SIGINT) -! sigset(THR_KILL_SIGNAL,end_thread_signal); -! sigset(THR_SERVER_ALARM,print_signal_warning); // Should never be called! - - if (!(test_flags & TEST_NO_STACKTRACE) || (test_flags & TEST_CORE_ON_SIGNAL)) - { ---- 1837,1847 ---- - DBUG_ENTER("init_signals"); - - if (test_flags & TEST_SIGINT) -! { -! my_sigset(thd_lib_detected == THD_LIB_LT ? SIGINT : SIGUSR2, -! end_thread_signal); -! } -! my_sigset(THR_SERVER_ALARM, print_signal_warning); // Should never be called! - - if (!(test_flags & TEST_NO_STACKTRACE) || (test_flags & TEST_CORE_ON_SIGNAL)) - { -*************** -*** 1877,1883 **** - #endif - (void) sigemptyset(&set); - #ifdef THREAD_SPECIFIC_SIGPIPE -! sigset(SIGPIPE,abort_thread); - sigaddset(&set,SIGPIPE); - #else - (void) signal(SIGPIPE,SIG_IGN); // Can't know which thread ---- 1876,1882 ---- - #endif - (void) sigemptyset(&set); - #ifdef THREAD_SPECIFIC_SIGPIPE -! my_sigset(SIGPIPE, abort_thread); - sigaddset(&set,SIGPIPE); - #else - (void) signal(SIGPIPE,SIG_IGN); // Can't know which thread -*************** -*** 2237,2244 **** - MY_INIT(argv[0]); // init my_sys library & pthreads - tzset(); // Set tzname - - start_time=time((time_t*) 0); -- - #ifdef OS2 - { - // fix timezone for daylight saving ---- 2236,2243 ---- - MY_INIT(argv[0]); // init my_sys library & pthreads - tzset(); // Set tzname - -+ thd_lib_detected= get_thread_lib(); - start_time=time((time_t*) 0); - #ifdef OS2 - { - // fix timezone for daylight saving -*************** -*** 5547,5552 **** - (void) my_write(file, (byte*) buff, (uint) (end-buff),MYF(MY_WME)); - (void) my_close(file, MYF(0)); - } - } - - ---- 5546,5567 ---- - (void) my_write(file, (byte*) buff, (uint) (end-buff),MYF(MY_WME)); - (void) my_close(file, MYF(0)); - } -+ } -+ -+ -+ static uint get_thread_lib(void) -+ { -+ char buff[64]; -+ -+ #ifdef _CS_GNU_LIBPTHREAD_VERSION -+ confstr(_CS_GNU_LIBPTHREAD_VERSION, buff, sizeof(buff)); -+ -+ if (!strncasecmp(buff, "NPTL", 4)) -+ return THD_LIB_NPTL; -+ else if (!strncasecmp(buff, "linuxthreads", 12)) -+ return THD_LIB_LT; -+ #endif -+ return THD_LIB_OTHER; - } - - -- cgit v1.2.1 From 9639eb3dda5347ecc342de94da3cc0e025e5c058 Mon Sep 17 00:00:00 2001 From: unknown Date: Wed, 28 Mar 2007 20:16:01 +0400 Subject: BUG#26624: high mem usage (crash) in range optimizer - Added PARAM::alloced_sel_args where we count the # of SEL_ARGs created by SEL_ARG tree cloning operations. - Made the range analyzer to shortcut and not do any more cloning if we've already created MAX_SEL_ARGS SEL_ARG objects in cloning. - Added comments about space complexity of SEL_ARG-graph representation. mysql-test/r/range.result: BUG#26624: Testcase mysql-test/t/range.test: BUG#26624: Testcase --- mysql-test/r/range.result | 28 ++++++++ mysql-test/t/range.test | 32 +++++++++ sql/opt_range.cc | 162 +++++++++++++++++++++++++++++++++++++--------- 3 files changed, 191 insertions(+), 31 deletions(-) diff --git a/mysql-test/r/range.result b/mysql-test/r/range.result index 4d6cafb61d1..15d5f1a0183 100644 --- a/mysql-test/r/range.result +++ b/mysql-test/r/range.result @@ -701,4 +701,32 @@ d8c4177d225791924.30714720 d8c4177d2380fc201.39666693 d8c4177d24ccef970.14957924 DROP TABLE t1; +create table t1 ( +c1 char(10), c2 char(10), c3 char(10), c4 char(10), +c5 char(10), c6 char(10), c7 char(10), c8 char(10), +c9 char(10), c10 char(10), c11 char(10), c12 char(10), +c13 char(10), c14 char(10), c15 char(10), c16 char(10), +index(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12,c13,c14,c15,c16) +); +insert into t1 (c1) values ('1'),('1'),('1'),('1'); +select * from t1 where +c1 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") +and c2 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") +and c3 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") +and c4 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") +and c5 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") +and c6 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") +and c7 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") +and c8 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") +and c9 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") +and c10 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") +and c11 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") +and c12 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") +and c13 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") +and c14 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") +and c15 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") +and c16 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") +; +c1 c2 c3 c4 c5 c6 c7 c8 c9 c10 c11 c12 c13 c14 c15 c16 +drop table t1; End of 4.1 tests diff --git a/mysql-test/t/range.test b/mysql-test/t/range.test index 68ba43a8ba9..1e4cb91c03f 100644 --- a/mysql-test/t/range.test +++ b/mysql-test/t/range.test @@ -563,4 +563,36 @@ SELECT s.oxid FROM t1 v, t1 s DROP TABLE t1; +# BUG#26624 high mem usage (crash) in range optimizer (depends on order of fields in where) +create table t1 ( + c1 char(10), c2 char(10), c3 char(10), c4 char(10), + c5 char(10), c6 char(10), c7 char(10), c8 char(10), + c9 char(10), c10 char(10), c11 char(10), c12 char(10), + c13 char(10), c14 char(10), c15 char(10), c16 char(10), + index(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12,c13,c14,c15,c16) +); + +insert into t1 (c1) values ('1'),('1'),('1'),('1'); + +# This must run without crash and fast: +select * from t1 where + c1 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") + and c2 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") + and c3 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") + and c4 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") + and c5 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") + and c6 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") + and c7 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") + and c8 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") + and c9 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") + and c10 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") + and c11 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") + and c12 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") + and c13 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") + and c14 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") + and c15 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") + and c16 in ("abcdefgh", "123456789", "qwertyuio", "asddfgh") +; +drop table t1; + --echo End of 4.1 tests diff --git a/sql/opt_range.cc b/sql/opt_range.cc index 06e42ff363f..11ba6c0e465 100644 --- a/sql/opt_range.cc +++ b/sql/opt_range.cc @@ -128,6 +128,89 @@ static char is_null_string[2]= {1,0}; - get_quick_select() - Walk the SEL_ARG, materialize the key intervals, and create QUICK_RANGE_SELECT object that will read records within these intervals. + + 4. SPACE COMPLEXITY NOTES + + SEL_ARG graph is a representation of an ordered disjoint sequence of + intervals over the ordered set of index tuple values. + + For multi-part keys, one can construct a WHERE expression such that its + list of intervals will be of combinatorial size. Here is an example: + + (keypart1 IN (1,2, ..., n1)) AND + (keypart2 IN (1,2, ..., n2)) AND + (keypart3 IN (1,2, ..., n3)) + + For this WHERE clause the list of intervals will have n1*n2*n3 intervals + of form + + (keypart1, keypart2, keypart3) = (k1, k2, k3), where 1 <= k{i} <= n{i} + + SEL_ARG graph structure aims to reduce the amount of required space by + "sharing" the elementary intervals when possible (the pic at the + beginning of this comment has examples of such sharing). The sharing may + prevent combinatorial blowup: + + There are WHERE clauses that have combinatorial-size interval lists but + will be represented by a compact SEL_ARG graph. + Example: + (keypartN IN (1,2, ..., n1)) AND + ... + (keypart2 IN (1,2, ..., n2)) AND + (keypart1 IN (1,2, ..., n3)) + + but not in all cases: + + - There are WHERE clauses that do have a compact SEL_ARG-graph + representation but get_mm_tree() and its callees will construct a + graph of combinatorial size. + Example: + (keypart1 IN (1,2, ..., n1)) AND + (keypart2 IN (1,2, ..., n2)) AND + ... + (keypartN IN (1,2, ..., n3)) + + - There are WHERE clauses for which the minimal possible SEL_ARG graph + representation will have combinatorial size. + Example: + By induction: Let's take any interval on some keypart in the middle: + + kp15=1 + + Then let's AND it with this interval 'structure' from preceding and + following keyparts: + + (kp14=c1 AND kp16=c3) OR keypart14=c2) (*) + + We will obtain this SEL_ARG graph: + + kp14 $ kp15 $ kp16 + $ $ + +---------+ $ +--------+ $ +---------+ + | kp14=c1 |--$-->| kp15=1 |--$-->| kp16=c3 | + +---------+ $ +--------+ $ +---------+ + | $ $ + +---------+ $ +--------+ $ + | kp14=c2 |--$-->| kp15=1 | $ + +---------+ $ +--------+ $ + $ $ + + Note that we had to duplicate "kp15=1" and there was no way to avoid + that. + The induction step: AND the obtained expression with another "wrapping" + expression like (*). + When the process ends because of the limit on max. number of keyparts + we'll have: + + WHERE clause length is O(3*#max_keyparts) + SEL_ARG graph size is O(2^(#max_keyparts/2)) + + (it is also possible to construct a case where instead of 2 in 2^n we + have a bigger constant, e.g. 4, and get a graph with 4^(31/2)= 2^31 + nodes) + + We avoid consuming too much memory by setting a limit on the number of + SEL_ARG object we can construct during one range analysis invocation. */ class SEL_ARG :public Sql_alloc @@ -158,6 +241,8 @@ public: enum leaf_color { BLACK,RED } color; enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type; + enum { MAX_SEL_ARGS = 64000 }; + SEL_ARG() {} SEL_ARG(SEL_ARG &); SEL_ARG(Field *,const char *,const char *); @@ -227,7 +312,8 @@ public: return new SEL_ARG(field, part, min_value, arg->max_value, min_flag, arg->max_flag, maybe_flag | arg->maybe_flag); } - SEL_ARG *clone(SEL_ARG *new_parent,SEL_ARG **next); + SEL_ARG *clone(struct st_qsel_param *param, SEL_ARG *new_parent, + SEL_ARG **next); bool copy_min(SEL_ARG* arg) { // Get overlapping range @@ -365,7 +451,7 @@ public: { return parent->left == this ? &parent->left : &parent->right; } - SEL_ARG *clone_tree(); + SEL_ARG *clone_tree(struct st_qsel_param *param); }; @@ -391,6 +477,8 @@ typedef struct st_qsel_param { max_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH]; bool quick; // Don't calulate possible keys COND *cond; + /* Numbr of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */ + uint alloced_sel_args; } PARAM; static SEL_TREE * get_mm_parts(PARAM *param,COND *cond_func,Field *field, @@ -413,8 +501,8 @@ static void print_quick(QUICK_SELECT *quick,const key_map* needed_reg); static SEL_TREE *tree_and(PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2); static SEL_TREE *tree_or(PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2); static SEL_ARG *sel_add(SEL_ARG *key1,SEL_ARG *key2); -static SEL_ARG *key_or(SEL_ARG *key1,SEL_ARG *key2); -static SEL_ARG *key_and(SEL_ARG *key1,SEL_ARG *key2,uint clone_flag); +static SEL_ARG *key_or(PARAM *param, SEL_ARG *key1,SEL_ARG *key2); +static SEL_ARG *key_and(PARAM *param, SEL_ARG *key1,SEL_ARG *key2,uint clone_flag); static bool get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1); static bool get_quick_keys(PARAM *param,QUICK_SELECT *quick,KEY_PART *key, SEL_ARG *key_tree,char *min_key,uint min_key_flag, @@ -424,6 +512,7 @@ static bool eq_tree(SEL_ARG* a,SEL_ARG *b); static SEL_ARG null_element(SEL_ARG::IMPOSSIBLE); static bool null_part_in_key(KEY_PART *key_part, const char *key, uint length); + /*************************************************************************** ** Basic functions for SQL_SELECT and QUICK_SELECT ***************************************************************************/ @@ -568,12 +657,17 @@ SEL_ARG::SEL_ARG(Field *field_,uint8 part_,char *min_value_,char *max_value_, left=right= &null_element; } -SEL_ARG *SEL_ARG::clone(SEL_ARG *new_parent,SEL_ARG **next_arg) +SEL_ARG *SEL_ARG::clone(PARAM *param, SEL_ARG *new_parent, SEL_ARG **next_arg) { SEL_ARG *tmp; + + /* Bail out if we have already generated too many SEL_ARGs */ + if (++param->alloced_sel_args > MAX_SEL_ARGS) + return 0; + if (type != KEY_RANGE) { - if (!(tmp= new SEL_ARG(type))) + if (!(tmp= new (param->mem_root) SEL_ARG(type))) return 0; // out of memory tmp->prev= *next_arg; // Link into next/prev chain (*next_arg)->next=tmp; @@ -581,20 +675,20 @@ SEL_ARG *SEL_ARG::clone(SEL_ARG *new_parent,SEL_ARG **next_arg) } else { - if (!(tmp= new SEL_ARG(field,part, min_value,max_value, - min_flag, max_flag, maybe_flag))) + if (!(tmp= new (param->mem_root) 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); + tmp->left=left->clone(param, tmp, next_arg); 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))) + if (!(tmp->right= right->clone(param, tmp, next_arg))) return 0; // OOM } increment_use_count(1); @@ -672,11 +766,12 @@ static int sel_cmp(Field *field, char *a,char *b,uint8 a_flag,uint8 b_flag) } -SEL_ARG *SEL_ARG::clone_tree() +SEL_ARG *SEL_ARG::clone_tree(PARAM *param) { SEL_ARG tmp_link,*next_arg,*root; next_arg= &tmp_link; - root= clone((SEL_ARG *) 0, &next_arg); + if (!(root= clone(param, (SEL_ARG *) 0, &next_arg))) + return 0; next_arg->next=0; // Fix last link tmp_link.next->prev=0; // Fix first link if (root) // If not OOM @@ -890,6 +985,7 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use, param.real_keynr[param.keys++]=idx; } param.key_parts_end=key_parts; + param.alloced_sel_args= 0; if ((tree=get_mm_tree(¶m,cond))) { @@ -991,7 +1087,8 @@ static SEL_TREE *get_mm_tree(PARAM *param,COND *cond) while ((item=li++)) { SEL_TREE *new_tree=get_mm_tree(param,item); - if (param->thd->is_fatal_error) + if (param->thd->is_fatal_error || + param->alloced_sel_args > SEL_ARG::MAX_SEL_ARGS) DBUG_RETURN(0); // out of memory tree=tree_and(param,tree,new_tree); if (tree && tree->type == SEL_TREE::IMPOSSIBLE) @@ -1524,7 +1621,7 @@ tree_and(PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2) tree1->type=SEL_TREE::KEY_SMALLER; DBUG_RETURN(tree1); } - + /* Join the trees key per key */ SEL_ARG **key1,**key2,**end; for (key1= tree1->keys,key2= tree2->keys,end=key1+param->keys ; @@ -1537,7 +1634,7 @@ tree_and(PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2) flag|=CLONE_KEY1_MAYBE; if (*key2 && !(*key2)->simple_key()) flag|=CLONE_KEY2_MAYBE; - *key1=key_and(*key1,*key2,flag); + *key1=key_and(param, *key1, *key2, flag); if (*key1 && (*key1)->type == SEL_ARG::IMPOSSIBLE) { tree1->type= SEL_TREE::IMPOSSIBLE; @@ -1574,7 +1671,7 @@ tree_or(PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2) for (key1= tree1->keys,key2= tree2->keys,end=key1+param->keys ; key1 != end ; key1++,key2++) { - *key1=key_or(*key1,*key2); + *key1= key_or(param, *key1, *key2); if (*key1) { result=tree1; // Added to tree1 @@ -1590,14 +1687,14 @@ tree_or(PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2) /* And key trees where key1->part < key2 -> part */ static SEL_ARG * -and_all_keys(SEL_ARG *key1,SEL_ARG *key2,uint clone_flag) +and_all_keys(PARAM *param, SEL_ARG *key1, SEL_ARG *key2, uint clone_flag) { SEL_ARG *next; ulong use_count=key1->use_count; if (key1->elements != 1) { - key2->use_count+=key1->elements-1; + key2->use_count+=key1->elements-1; //psergey: why we don't count that key1 has n-k-p? key2->increment_use_count((int) key1->elements-1); } if (key1->type == SEL_ARG::MAYBE_KEY) @@ -1609,7 +1706,7 @@ and_all_keys(SEL_ARG *key1,SEL_ARG *key2,uint clone_flag) { if (next->next_key_part) { - SEL_ARG *tmp=key_and(next->next_key_part,key2,clone_flag); + SEL_ARG *tmp= key_and(param, next->next_key_part, key2, clone_flag); if (tmp && tmp->type == SEL_ARG::IMPOSSIBLE) { key1=key1->tree_delete(next); @@ -1618,6 +1715,8 @@ and_all_keys(SEL_ARG *key1,SEL_ARG *key2,uint clone_flag) next->next_key_part=tmp; if (use_count) next->increment_use_count(use_count); + if (param->alloced_sel_args > SEL_ARG::MAX_SEL_ARGS) + break; } else next->next_key_part=key2; @@ -1644,7 +1743,7 @@ and_all_keys(SEL_ARG *key1,SEL_ARG *key2,uint clone_flag) */ static SEL_ARG * -key_and(SEL_ARG *key1, SEL_ARG *key2, uint clone_flag) +key_and(PARAM *param, SEL_ARG *key1, SEL_ARG *key2, uint clone_flag) { if (!key1) return key2; @@ -1660,9 +1759,9 @@ key_and(SEL_ARG *key1, SEL_ARG *key2, uint clone_flag) // key1->part < key2->part key1->use_count--; if (key1->use_count > 0) - if (!(key1= key1->clone_tree())) + if (!(key1= key1->clone_tree(param))) return 0; // OOM - return and_all_keys(key1,key2,clone_flag); + return and_all_keys(param, key1, key2, clone_flag); } if (((clone_flag & CLONE_KEY2_MAYBE) && @@ -1680,14 +1779,14 @@ key_and(SEL_ARG *key1, SEL_ARG *key2, uint clone_flag) if (key1->use_count > 1) { key1->use_count--; - if (!(key1=key1->clone_tree())) + if (!(key1=key1->clone_tree(param))) return 0; // OOM key1->use_count++; } if (key1->type == SEL_ARG::MAYBE_KEY) { // Both are maybe key - key1->next_key_part=key_and(key1->next_key_part,key2->next_key_part, - clone_flag); + key1->next_key_part=key_and(param, key1->next_key_part, + key2->next_key_part, clone_flag); if (key1->next_key_part && key1->next_key_part->type == SEL_ARG::IMPOSSIBLE) return key1; @@ -1698,7 +1797,7 @@ key_and(SEL_ARG *key1, SEL_ARG *key2, uint clone_flag) if (key2->next_key_part) { key1->use_count--; // Incremented in and_all_keys - return and_all_keys(key1,key2,clone_flag); + return and_all_keys(param, key1, key2, clone_flag); } key2->use_count--; // Key2 doesn't have a tree } @@ -1727,7 +1826,8 @@ key_and(SEL_ARG *key1, SEL_ARG *key2, uint clone_flag) } else if (get_range(&e2,&e1,key2)) continue; - SEL_ARG *next=key_and(e1->next_key_part,e2->next_key_part,clone_flag); + SEL_ARG *next=key_and(param, e1->next_key_part, e2->next_key_part, + clone_flag); e1->increment_use_count(1); e2->increment_use_count(1); if (!next || next->type != SEL_ARG::IMPOSSIBLE) @@ -1775,7 +1875,7 @@ get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1) static SEL_ARG * -key_or(SEL_ARG *key1,SEL_ARG *key2) +key_or(PARAM *param, SEL_ARG *key1,SEL_ARG *key2) { if (!key1) { @@ -1823,7 +1923,7 @@ key_or(SEL_ARG *key1,SEL_ARG *key2) { swap_variables(SEL_ARG *,key1,key2); } - if (key1->use_count > 0 || !(key1=key1->clone_tree())) + if (key1->use_count > 0 || !(key1=key1->clone_tree(param))) return 0; // OOM } @@ -1967,7 +2067,7 @@ key_or(SEL_ARG *key1,SEL_ARG *key2) { // tmp.min. <= x <= tmp.max tmp->maybe_flag|= key.maybe_flag; key.increment_use_count(key1->use_count+1); - tmp->next_key_part=key_or(tmp->next_key_part,key.next_key_part); + tmp->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part); if (!cmp) // Key2 is ready break; key.copy_max_to_min(tmp); @@ -1998,7 +2098,7 @@ key_or(SEL_ARG *key1,SEL_ARG *key2) tmp->increment_use_count(key1->use_count+1); /* Increment key count as it may be used for next loop */ key.increment_use_count(1); - new_arg->next_key_part=key_or(tmp->next_key_part,key.next_key_part); + new_arg->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part); key1=key1->insert(new_arg); break; } -- cgit v1.2.1 From 9b358f811b046ce5e188235d7e3d60424d5579e7 Mon Sep 17 00:00:00 2001 From: unknown Date: Thu, 29 Mar 2007 10:27:58 +0400 Subject: BUG#26624: high mem usage (crash) in range optimizer - Post-review fixes --- sql/opt_range.cc | 29 +++++++++++++++-------------- 1 file changed, 15 insertions(+), 14 deletions(-) diff --git a/sql/opt_range.cc b/sql/opt_range.cc index 11ba6c0e465..ca8f31f5775 100644 --- a/sql/opt_range.cc +++ b/sql/opt_range.cc @@ -175,7 +175,7 @@ static char is_null_string[2]= {1,0}; Example: By induction: Let's take any interval on some keypart in the middle: - kp15=1 + kp15=c0 Then let's AND it with this interval 'structure' from preceding and following keyparts: @@ -184,18 +184,18 @@ static char is_null_string[2]= {1,0}; We will obtain this SEL_ARG graph: - kp14 $ kp15 $ kp16 - $ $ - +---------+ $ +--------+ $ +---------+ - | kp14=c1 |--$-->| kp15=1 |--$-->| kp16=c3 | - +---------+ $ +--------+ $ +---------+ - | $ $ - +---------+ $ +--------+ $ - | kp14=c2 |--$-->| kp15=1 | $ - +---------+ $ +--------+ $ - $ $ + kp14 $ kp15 $ kp16 + $ $ + +---------+ $ +---------+ $ +---------+ + | kp14=c1 |--$-->| kp15=c0 |--$-->| kp16=c3 | + +---------+ $ +---------+ $ +---------+ + | $ $ + +---------+ $ +---------+ $ + | kp14=c2 |--$-->| kp15=c0 | $ + +---------+ $ +---------+ $ + $ $ - Note that we had to duplicate "kp15=1" and there was no way to avoid + Note that we had to duplicate "kp15=c0" and there was no way to avoid that. The induction step: AND the obtained expression with another "wrapping" expression like (*). @@ -477,7 +477,7 @@ typedef struct st_qsel_param { max_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH]; bool quick; // Don't calulate possible keys COND *cond; - /* Numbr of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */ + /* Number of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */ uint alloced_sel_args; } PARAM; @@ -681,7 +681,8 @@ SEL_ARG *SEL_ARG::clone(PARAM *param, SEL_ARG *new_parent, SEL_ARG **next_arg) tmp->parent=new_parent; tmp->next_key_part=next_key_part; if (left != &null_element) - tmp->left=left->clone(param, tmp, next_arg); + if (!(tmp->left=left->clone(param, tmp, next_arg))) + return 0; // OOM tmp->prev= *next_arg; // Link into next/prev chain (*next_arg)->next=tmp; -- cgit v1.2.1