revision-id: 8f7e4642c56bd03327947043c5d93a7cbfaaaed3 (mariadb-10.4.11-420-g8f7e4642c56) parent(s): c2ac0ce1f02e3ae2b1de5c07ba40bed25c30dc40 author: Sergei Petrunia committer: Sergei Petrunia timestamp: 2020-11-11 23:26:54 +0300 message: MDEV-9750: Quick memory exhaustion with 'extended_keys=on' ... (Variant #2) 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. Variant #2: Don't call enforce_sel_arg_weight_limit() for sub-graphs, as this has complicated semantics if the subgraph has shared sub-sub-graphs. Instead, do pruning it only after we've constructed the entire SEL_ARG graph. --- mysql-test/main/range.result | 46 +++++++++ mysql-test/main/range.test | 34 +++++++ mysql-test/main/range_mrr_icp.result | 46 +++++++++ sql/opt_range.cc | 182 +++++++++++++++++++++++++++++++++-- sql/opt_range.h | 53 +++++++++- 5 files changed, 354 insertions(+), 7 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..eb093e39011 100644 --- a/sql/opt_range.cc +++ b/sql/opt_range.cc @@ -399,6 +399,11 @@ static SEL_ARG *key_or(RANGE_OPT_PARAM *param, static SEL_ARG *key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2, uint clone_flag); +static SEL_ARG *key_or_with_limit(RANGE_OPT_PARAM *param, + SEL_ARG *key1, SEL_ARG *key2); +static SEL_ARG *key_and_with_limit(RANGE_OPT_PARAM *param, + SEL_ARG *key1, SEL_ARG *key2, + uint clone_flag); static bool get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1); bool get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key, SEL_ARG *key_tree, uchar *min_key,uint min_key_flag, @@ -410,6 +415,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, @@ -706,7 +713,7 @@ int SEL_IMERGE::or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_ARG *key1= (*or_tree)->keys[key_no]; SEL_ARG *key2= tree->keys[key_no]; key2->incr_refs(); - if ((result->keys[key_no]= key_or(param, key1, key2))) + if ((result->keys[key_no]= key_or_with_limit(param, key1, key2))) { result_keys.set_bit(key_no); @@ -1877,6 +1884,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 +1901,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 +1913,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; @@ -5432,7 +5440,7 @@ TABLE_READ_PLAN *merge_same_index_scans(PARAM *param, SEL_IMERGE *imerge, if ((*tree)->keys[key_idx]) (*tree)->keys[key_idx]->incr_refs(); if (((*changed_tree)->keys[key_idx]= - key_or(param, key, (*tree)->keys[key_idx]))) + key_or_with_limit(param, key, (*tree)->keys[key_idx]))) (*changed_tree)->keys_map.set_bit(key_idx); *tree= NULL; removed_cnt++; @@ -9094,7 +9102,7 @@ int and_range_trees(RANGE_OPT_PARAM *param, SEL_TREE *tree1, SEL_TREE *tree2, key2->incr_refs(); } SEL_ARG *key; - if ((result->keys[key_no]= key =key_and(param, key1, key2, flag))) + if ((result->keys[key_no]= key =key_and_with_limit(param, key1, key2, flag))) { if (key && key->type == SEL_ARG::IMPOSSIBLE) { @@ -9637,7 +9645,7 @@ tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2) key1->incr_refs(); key2->incr_refs(); } - if ((result->keys[key_no]= key_or(param, key1, key2))) + if ((result->keys[key_no]= key_or_with_limit(param, key1, key2))) result->keys_map.set_bit(key_no); } result->type= tree1->type; @@ -9723,6 +9731,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 +9744,23 @@ 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; return key1; } @@ -9780,6 +9795,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 +9836,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 +9868,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 +9890,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 +9908,7 @@ 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; return new_tree; } @@ -9899,6 +9931,21 @@ get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1) } +static SEL_ARG *key_or_with_limit(RANGE_OPT_PARAM *param, + SEL_ARG *key1, SEL_ARG *key2) +{ + return enforce_sel_arg_weight_limit(key_or(param, key1, key2)); +} + + +static SEL_ARG *key_and_with_limit(RANGE_OPT_PARAM *param, + SEL_ARG *key1, SEL_ARG *key2, + uint clone_flag) +{ + return enforce_sel_arg_weight_limit(key_and(param, key1, key2, clone_flag)); +} + + /** Combine two range expression under a common OR. On a logical level, the transformation is key_or( expr1, expr2 ) => expr1 OR expr2. @@ -10553,6 +10600,19 @@ 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; return key1; } @@ -10590,6 +10650,108 @@ 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) +{ + if (!sel_arg || sel_arg->type != SEL_ARG::KEY_RANGE) + return 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; + +#ifdef EXTRA_DEBUG + uint weight1= sel_arg->weight; +#endif + + max_part--; + prune_sel_arg_graph(sel_arg, max_part); + +#ifdef EXTRA_DEBUG + DBUG_PRINT("info", ("enforce_sel_arg_weight_limit: %d->%d", weight1, + sel_arg->weight)); +#endif + } +} + + SEL_ARG * SEL_ARG::insert(SEL_ARG *key) { @@ -10628,6 +10790,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 +10849,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 +10905,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..d37339707b8 100644 --- a/sql/opt_range.h +++ b/sql/opt_range.h @@ -223,6 +223,43 @@ class RANGE_OPT_PARAM; 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. + + 5. SEL_ARG GRAPH WEIGHT + + A SEL_ARG graph has a property we call weight, and we define it as follows: + + If the SEL_ARG graph does not have any node with multiple incoming + next_key_part edges, then its weight is the number of SEL_ARG objects used. + + If there is a node with multiple next_key_part edges, clone the node (and + the nodes connected via prev/next links to it) and redirect one of the + incoming next_key_part to the clone. (If the node has "peer" nodes + connected to it via prev/next links, they will have to be cloned as well) + + Repeat this until we get a graph without multiple next_key_part edges + coming into the same node. Then, the number of SEL_ARG objects in the + graph is the weight. + + Example: + + | +-------+ $ $ + \->| kp1=2 |--$--------------$-+ + +-------+ $ $ | +--------+ + | $ $ ==>| kp3=11 | + +-------+ $ $ | +--------+ + | kp1=3 |--$--------------$-+ | + +-------+ $ $ +--------+ + $ $ | kp3=14 | + $ $ +--------+ + + Here, the weight is 2 + 2*2=6. + + The rationale behind the weight is: + - it has the same order-of-magnitude as the number of ranges that the + SEL_ARG graph is describing, + - it is a lot easier to compute, + - it can be updated incrementally when performing AND/OR operations on + parts of the graph. */ class SEL_ARG :public Sql_alloc @@ -236,6 +273,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 +303,14 @@ class SEL_ARG :public Sql_alloc enum leaf_color { BLACK,RED } color; enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type; + /* + For R-B root nodes only: the graph weight, as defined above in the + SEL_ARG GRAPH WEIGHT section. + */ + uint weight; + enum { MAX_WEIGHT = 32000 }; + + /* See RANGE_OPT_PARAM::alloced_sel_args */ enum { MAX_SEL_ARGS = 16000 }; SEL_ARG() {} @@ -273,7 +321,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 +335,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 */