revision-id: 7cdd4fe6440879e9309d036362414d483c642122 (mariadb-10.4.11-420-g7cdd4fe6440) parent(s): c2ac0ce1f02e3ae2b1de5c07ba40bed25c30dc40 author: Sergei Petrunia committer: Sergei Petrunia timestamp: 2020-11-05 19:41:58 +0300 message: MDEV-9750: Quick memory exhaustion with 'extended_keys=on' ... Do not produce SEL_ARG graphs that would yield huge numbers of ranges. Introduce a concept of SEL_ARG graph's "weight". If we are about to produce a graph whose "weight" exceeds the limit, remove the parts of SEL_ARG graph that represent the biggest key parts. Do so until the graph's is within the limit. --- mysql-test/main/range.result | 46 +++++++++++ mysql-test/main/range.test | 34 ++++++++ mysql-test/main/range_mrr_icp.result | 46 +++++++++++ sql/opt_range.cc | 147 ++++++++++++++++++++++++++++++++++- sql/opt_range.h | 12 ++- 5 files changed, 282 insertions(+), 3 deletions(-) diff --git a/mysql-test/main/range.result b/mysql-test/main/range.result index b708628b625..9800d931dd6 100644 --- a/mysql-test/main/range.result +++ b/mysql-test/main/range.result @@ -3135,6 +3135,52 @@ drop table t1,ten,t2; # # End of 10.2 tests # +# +# MDEV-9750: Quick memory exhaustion with 'extended_keys=on'... +# +create table t1 ( +kp1 int, +kp2 int, +kp3 int, +kp4 int, +key key1(kp1, kp2, kp3,kp4) +); +insert into t1 values (1,1,1,1),(2,2,2,2),(3,3,3,3); +set @tmp_9750=@@optimizer_trace; +set optimizer_trace=1; +explain select * from t1 where +kp1 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20) and +kp2 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20) and +kp3 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20) and +kp4 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20) +; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 index key1 key1 20 NULL 3 Using where; Using index +set @json= (select json_detailed(JSON_EXTRACT(trace, '$**.range_scan_alternatives')) +from information_schema.optimizer_trace); +# This will show 3-component ranges. +# The ranges were produced, but the optimizer has cut away kp4 +# to keep the number of ranges at manageable level: +select left(@json, 500); +left(@json, 500) +[ + + [ + + { + "index": "key1", + "ranges": + [ + "(1,1,1) <= (kp1,kp2,kp3) <= (1,1,1)", + "(1,1,2) <= (kp1,kp2,kp3) <= (1,1,2)", + "(1,1,3) <= (kp1,kp2,kp3) <= (1,1,3)", + "(1,1,4) <= (kp1,kp2,kp3) <= (1,1,4)", + "(1,1,5) <= (kp1,kp2,kp3) <= (1,1,5)", + "(1,1,6) <= (kp1,kp2,kp3) <= (1,1,6)", + "(1,1,7) <= (kp1,kp2,kp3) <= (1,1,7)", + " +set optimizer_trace=@tmp_9750; +drop table t1; set global innodb_stats_persistent= @innodb_stats_persistent_save; set global innodb_stats_persistent_sample_pages= @innodb_stats_persistent_sample_pages_save; diff --git a/mysql-test/main/range.test b/mysql-test/main/range.test index b5980a8f616..642ae3f8a08 100644 --- a/mysql-test/main/range.test +++ b/mysql-test/main/range.test @@ -2119,6 +2119,40 @@ drop table t1,ten,t2; --echo # End of 10.2 tests --echo # +--echo # +--echo # MDEV-9750: Quick memory exhaustion with 'extended_keys=on'... +--echo # + +create table t1 ( + kp1 int, + kp2 int, + kp3 int, + kp4 int, + key key1(kp1, kp2, kp3,kp4) +); + +insert into t1 values (1,1,1,1),(2,2,2,2),(3,3,3,3); + +# 20 * 20 * 20 *20 = 400*400 = 160,000 ranges +set @tmp_9750=@@optimizer_trace; +set optimizer_trace=1; +explain select * from t1 where + kp1 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20) and + kp2 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20) and + kp3 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20) and + kp4 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20) +; + +set @json= (select json_detailed(JSON_EXTRACT(trace, '$**.range_scan_alternatives')) + from information_schema.optimizer_trace); +--echo # This will show 3-component ranges. +--echo # The ranges were produced, but the optimizer has cut away kp4 +--echo # to keep the number of ranges at manageable level: +select left(@json, 500); + +set optimizer_trace=@tmp_9750; +drop table t1; + set global innodb_stats_persistent= @innodb_stats_persistent_save; set global innodb_stats_persistent_sample_pages= @innodb_stats_persistent_sample_pages_save; diff --git a/mysql-test/main/range_mrr_icp.result b/mysql-test/main/range_mrr_icp.result index 04c3ad2780d..128f23d71f6 100644 --- a/mysql-test/main/range_mrr_icp.result +++ b/mysql-test/main/range_mrr_icp.result @@ -3132,6 +3132,52 @@ drop table t1,ten,t2; # # End of 10.2 tests # +# +# MDEV-9750: Quick memory exhaustion with 'extended_keys=on'... +# +create table t1 ( +kp1 int, +kp2 int, +kp3 int, +kp4 int, +key key1(kp1, kp2, kp3,kp4) +); +insert into t1 values (1,1,1,1),(2,2,2,2),(3,3,3,3); +set @tmp_9750=@@optimizer_trace; +set optimizer_trace=1; +explain select * from t1 where +kp1 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20) and +kp2 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20) and +kp3 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20) and +kp4 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20) +; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 index key1 key1 20 NULL 3 Using where; Using index +set @json= (select json_detailed(JSON_EXTRACT(trace, '$**.range_scan_alternatives')) +from information_schema.optimizer_trace); +# This will show 3-component ranges. +# The ranges were produced, but the optimizer has cut away kp4 +# to keep the number of ranges at manageable level: +select left(@json, 500); +left(@json, 500) +[ + + [ + + { + "index": "key1", + "ranges": + [ + "(1,1,1) <= (kp1,kp2,kp3) <= (1,1,1)", + "(1,1,2) <= (kp1,kp2,kp3) <= (1,1,2)", + "(1,1,3) <= (kp1,kp2,kp3) <= (1,1,3)", + "(1,1,4) <= (kp1,kp2,kp3) <= (1,1,4)", + "(1,1,5) <= (kp1,kp2,kp3) <= (1,1,5)", + "(1,1,6) <= (kp1,kp2,kp3) <= (1,1,6)", + "(1,1,7) <= (kp1,kp2,kp3) <= (1,1,7)", + " +set optimizer_trace=@tmp_9750; +drop table t1; set global innodb_stats_persistent= @innodb_stats_persistent_save; set global innodb_stats_persistent_sample_pages= @innodb_stats_persistent_sample_pages_save; diff --git a/sql/opt_range.cc b/sql/opt_range.cc index eed7baab377..7af555dbd17 100644 --- a/sql/opt_range.cc +++ b/sql/opt_range.cc @@ -410,6 +410,8 @@ static bool null_part_in_key(KEY_PART *key_part, const uchar *key, uint length); static bool is_key_scan_ror(PARAM *param, uint keynr, uint8 nparts); +static SEL_ARG *enforce_sel_arg_weight_limit(SEL_ARG *sel_arg); + #include "opt_range_mrr.cc" static bool sel_trees_have_common_keys(SEL_TREE *tree1, SEL_TREE *tree2, @@ -1877,6 +1879,7 @@ SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_alloc() next_key_part=arg.next_key_part; max_part_no= arg.max_part_no; use_count=1; elements=1; + weight=1; } @@ -1893,7 +1896,7 @@ SEL_ARG::SEL_ARG(Field *f,const uchar *min_value_arg, :min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()), elements(1), use_count(1), field(f), min_value((uchar*) min_value_arg), max_value((uchar*) max_value_arg), next(0),prev(0), - next_key_part(0), color(BLACK), type(KEY_RANGE) + next_key_part(0), color(BLACK), type(KEY_RANGE), weight(1) { left=right= &null_element; max_part_no= 1; @@ -1905,7 +1908,7 @@ SEL_ARG::SEL_ARG(Field *field_,uint8 part_, :min_flag(min_flag_),max_flag(max_flag_),maybe_flag(maybe_flag_), part(part_),maybe_null(field_->real_maybe_null()), elements(1),use_count(1), field(field_), min_value(min_value_), max_value(max_value_), - next(0),prev(0),next_key_part(0),color(BLACK),type(KEY_RANGE) + next(0),prev(0),next_key_part(0),color(BLACK),type(KEY_RANGE), weight(1) { max_part_no= part+1; left=right= &null_element; @@ -9723,6 +9726,8 @@ and_all_keys(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2, key1->right= key1->left= &null_element; key1->next= key1->prev= 0; } + uint new_weight= 0; + for (next=key1->first(); next ; next=next->next) { if (next->next_key_part) @@ -9734,18 +9739,24 @@ and_all_keys(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2, continue; } next->next_key_part=tmp; + new_weight += 1 + tmp->weight; if (use_count) next->increment_use_count(use_count); if (param->alloced_sel_args > SEL_ARG::MAX_SEL_ARGS) break; } else + { + new_weight += 1 + key2->weight; next->next_key_part=key2; + } } if (!key1) return &null_element; // Impossible ranges key1->use_count++; key1->max_part_no= MY_MAX(key2->max_part_no, key2->part+1); + key1->weight= new_weight; + key1= enforce_sel_arg_weight_limit(key1); return key1; } @@ -9780,6 +9791,17 @@ key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2, uint clone_flag) clone_flag=swap_clone_flag(clone_flag); } // key1->part < key2->part + + /* + Do not combine the trees if their total weight is likely to exceed the + MAX_WEIGHT. + (It is possible that key1 has next_key_part that has empty overlap with + key2. In this case, the combined tree will have a smaller weight than we + predict. We assume this is rare.) + */ + if (key1->weight + key1->elements*key2->weight > SEL_ARG::MAX_WEIGHT) + return key1; + key1->use_count--; if (key1->use_count > 0) if (!(key1= key1->clone_tree(param))) @@ -9810,6 +9832,9 @@ key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2, uint clone_flag) { // Both are maybe key key1->next_key_part=key_and(param, key1->next_key_part, key2->next_key_part, clone_flag); + + key1->weight = 1 + (key1->next_key_part? key1->next_key_part->weight : 0); + if (key1->next_key_part && key1->next_key_part->type == SEL_ARG::IMPOSSIBLE) return key1; @@ -9839,6 +9864,7 @@ key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2, uint clone_flag) key2->use_count--; SEL_ARG *e1=key1->first(), *e2=key2->first(), *new_tree=0; uint max_part_no= MY_MAX(key1->max_part_no, key2->max_part_no); + uint new_weight= 0; // Weight of the result tree while (e1 && e2) { @@ -9860,6 +9886,7 @@ key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2, uint clone_flag) if (!new_arg) return &null_element; // End of memory new_arg->next_key_part=next; + new_weight += 1 + (next? next->weight: 0); if (!new_tree) { new_tree=new_arg; @@ -9877,6 +9904,8 @@ key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2, uint clone_flag) if (!new_tree) return &null_element; // Impossible range new_tree->max_part_no= max_part_no; + new_tree->weight= new_weight; + new_tree= enforce_sel_arg_weight_limit(new_tree); return new_tree; } @@ -10553,7 +10582,21 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2) } key1->use_count++; + /* Re-compute the result tree's weight. */ + { + uint new_weight= 0; + const SEL_ARG *sl; + for (sl= key1->first(); sl ; sl= sl->next) + { + new_weight++; + if (sl->next_key_part) + new_weight += sl->next_key_part->weight; + } + key1->weight= new_weight; + } + key1->max_part_no= max_part_no; + key1= enforce_sel_arg_weight_limit(key1); return key1; } @@ -10590,6 +10633,98 @@ static bool eq_tree(SEL_ARG* a,SEL_ARG *b) } +/* + Compute the MAX(key part) in this SEL_ARG graph. +*/ +uint SEL_ARG::get_max_key_part() const +{ + const SEL_ARG *cur; + uint max_part= part; + for (cur= first(); cur ; cur=cur->next) + { + if (cur->next_key_part) + { + uint mp= cur->next_key_part->get_max_key_part(); + max_part = MY_MAX(part, mp); + } + } + return max_part; +} + + +/* + Remove the SEL_ARG graph elements which have part > max_part. + + @detail + Also update weight for the graph and any modified subgraphs. +*/ + +void prune_sel_arg_graph(SEL_ARG *sel_arg, uint max_part) +{ + SEL_ARG *cur; + DBUG_ASSERT(max_part >= sel_arg->part); + + for (cur= sel_arg->first(); cur ; cur=cur->next) + { + if (cur->next_key_part) + { + if (cur->next_key_part->part > max_part) + { + // Remove cur->next_key_part. + sel_arg->weight -= cur->next_key_part->weight; + cur->next_key_part= NULL; + } + else + { + uint old_weight = cur->next_key_part->weight; + prune_sel_arg_graph(cur->next_key_part, max_part); + old_weight -= cur->next_key_part->weight; + sel_arg->weight -= old_weight; + } + } + } +} + + +/* + @brief + Make sure the passed SEL_ARG graph's weight is below SEL_ARG::MAX_WEIGHT, + by cutting off branches if necessary. + + @detail + @see declaration of SEL_ARG::weight for definition of weight. + + This function attempts to reduce the graph's weight by cutting off + SEL_ARG::next_key_part connections if necessary. + + We start with maximum used keypart and then remove one keypart after + another until the graph's weight is within the limit. + + @return + tree pointer The tree after processing, + NULL If it was not possible to reduce the weight of the tree below the + limit. +*/ + +SEL_ARG *enforce_sel_arg_weight_limit(SEL_ARG *sel_arg) +{ + while (1) + { + if (sel_arg->weight <= SEL_ARG::MAX_WEIGHT) + return sel_arg; + + uint max_part= sel_arg->get_max_key_part(); + if (max_part == sel_arg->part) + return NULL; + + max_part--; + //uint weight1= sel_arg->weight; + prune_sel_arg_graph(sel_arg, max_part); + //fprintf(stderr, "AAA: enforce_weight_limit: %d -> %d\n", weight1, sel_arg->weight); + } +} + + SEL_ARG * SEL_ARG::insert(SEL_ARG *key) { @@ -10628,6 +10763,8 @@ SEL_ARG::insert(SEL_ARG *key) SEL_ARG *root=rb_insert(key); // rebalance tree root->use_count=this->use_count; // copy root info root->elements= this->elements+1; + // Add the weight: weight of this element (=1) + next_key_part's weight + root->weight += 1 + (next_key_part? next_key_part->weight: 0); root->maybe_flag=this->maybe_flag; return root; } @@ -10685,6 +10822,11 @@ SEL_ARG::tree_delete(SEL_ARG *key) root=this; this->parent= 0; + // Compute the weight the tree will have after the element is removed + // We remove the element itself (weight=1) + // and the sub-graph connected to its next_key_part. + uint new_weight= root->weight - (1 + (key->next_key_part? + key->next_key_part->weight : 0)); /* Unlink from list */ if (key->prev) key->prev->next=key->next; @@ -10736,6 +10878,7 @@ SEL_ARG::tree_delete(SEL_ARG *key) test_rb_tree(root,root->parent); root->use_count=this->use_count; // Fix root counters + root->weight = new_weight; root->elements=this->elements-1; root->maybe_flag=this->maybe_flag; DBUG_RETURN(root); diff --git a/sql/opt_range.h b/sql/opt_range.h index 11d9f80865a..613e8efa4f3 100644 --- a/sql/opt_range.h +++ b/sql/opt_range.h @@ -236,6 +236,9 @@ class SEL_ARG :public Sql_alloc /* The ordinal number the least significant component encountered in the ranges of the SEL_ARG tree (the first component has number 1) + + Note: this number is currently not precise, it is an upper bound. + @seealso SEL_ARG::get_max_key_part() */ uint16 max_part_no; /* @@ -263,6 +266,10 @@ class SEL_ARG :public Sql_alloc enum leaf_color { BLACK,RED } color; enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type; + uint weight; + enum { MAX_WEIGHT = 32000 }; + + /* See RANGE_OPT_PARAM::alloced_sel_args */ enum { MAX_SEL_ARGS = 16000 }; SEL_ARG() {} @@ -273,7 +280,7 @@ class SEL_ARG :public Sql_alloc SEL_ARG(enum Type type_arg) :min_flag(0), max_part_no(0) /* first key part means 1. 0 mean 'no parts'*/, elements(1),use_count(1),left(0),right(0), - next_key_part(0), color(BLACK), type(type_arg) + next_key_part(0), color(BLACK), type(type_arg), weight(1) {} /** returns true if a range predicate is equal. Use all_same() @@ -287,6 +294,9 @@ class SEL_ARG :public Sql_alloc return true; return cmp_min_to_min(arg) == 0 && cmp_max_to_max(arg) == 0; } + + uint get_max_key_part() const; + /** returns true if all the predicates in the keypart tree are equal */