revision-id: b6a5d3e87a8c33540d7cda3e4a512598fa5b1233 (mariadb-10.4.11-423-gb6a5d3e87a8) parent(s): 00675d2596ff3b15f676a2ee329ea6045adb08b4 author: Sergei Petrunia committer: Sergei Petrunia timestamp: 2021-01-19 15:31:47 +0300 message: MDEV-9750: Quick memory exhaustion with 'extended_keys=on', Part #4 Part #4: - Fix comment - Make tree pruning visible in the optimizer trace. --- mysql-test/main/range.result | 39 +++++++++++++++++++++-- mysql-test/main/range.test | 7 +++-- sql/opt_range.cc | 73 ++++++++++++++++++++++++++------------------ sql/opt_range.h | 29 +++++++++++------- 4 files changed, 103 insertions(+), 45 deletions(-) diff --git a/mysql-test/main/range.result b/mysql-test/main/range.result index c5178885d7f..982a70f94f8 100644 --- a/mysql-test/main/range.result +++ b/mysql-test/main/range.result @@ -3193,8 +3193,8 @@ kp4 in (1,2,3,4,5,6,7,8,9,10) ; 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); +set @trace= (select trace from information_schema.optimizer_trace); +set @json= json_detailed(json_extract(@trace, '$**.range_scan_alternatives')); select left(@json, 500); left(@json, 500) [ @@ -3216,6 +3216,41 @@ left(@json, 500) "(9) <= (kp1) <= (9)", "(10) <= (kp1) <= (10)" +set @json= json_detailed(json_extract(@trace, '$**.setup_range_conditions')); +select left(@json, 2500); +left(@json, 2500) +[ + + [ + + { + "enforce_sel_arg_weight_limit": + { + "index": "key1", + "old_weight": 110, + "new_weight": 10 + } + }, + + { + "enforce_sel_arg_weight_limit": + { + "index": "key1", + "old_weight": 110, + "new_weight": 10 + } + }, + + { + "enforce_sel_arg_weight_limit": + { + "index": "key1", + "old_weight": 110, + "new_weight": 10 + } + } + ] +] ## Repeat the above with a bit higher max_weight: set @tmp9750_weight=@@optimizer_max_sel_arg_weight; set optimizer_max_sel_arg_weight=120; diff --git a/mysql-test/main/range.test b/mysql-test/main/range.test index a9f374afa3d..6a1c51f8939 100644 --- a/mysql-test/main/range.test +++ b/mysql-test/main/range.test @@ -2161,10 +2161,13 @@ explain select * from t1 where kp3 in (1,2,3,4,5,6,7,8,9,10) and kp4 in (1,2,3,4,5,6,7,8,9,10) ; -set @json= (select json_detailed(JSON_EXTRACT(trace, '$**.range_scan_alternatives')) - from information_schema.optimizer_trace); +set @trace= (select trace from information_schema.optimizer_trace); +set @json= json_detailed(json_extract(@trace, '$**.range_scan_alternatives')); select left(@json, 500); +set @json= json_detailed(json_extract(@trace, '$**.setup_range_conditions')); +select left(@json, 2500); + --echo ## Repeat the above with a bit higher max_weight: set @tmp9750_weight=@@optimizer_max_sel_arg_weight; set optimizer_max_sel_arg_weight=120; diff --git a/sql/opt_range.cc b/sql/opt_range.cc index 26d76075e60..b67a85457c5 100644 --- a/sql/opt_range.cc +++ b/sql/opt_range.cc @@ -399,9 +399,9 @@ 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, +static SEL_ARG *key_or_with_limit(RANGE_OPT_PARAM *param, uint keyno, SEL_ARG *key1, SEL_ARG *key2); -static SEL_ARG *key_and_with_limit(RANGE_OPT_PARAM *param, +static SEL_ARG *key_and_with_limit(RANGE_OPT_PARAM *param, uint keyno, SEL_ARG *key1, SEL_ARG *key2, uint clone_flag); static bool get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1); @@ -415,7 +415,9 @@ 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(THD *thd, SEL_ARG *sel_arg); +static +SEL_ARG *enforce_sel_arg_weight_limit(RANGE_OPT_PARAM *param, uint keyno, + SEL_ARG *sel_arg); #include "opt_range_mrr.cc" @@ -713,7 +715,8 @@ 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_with_limit(param, key1, key2))) + if ((result->keys[key_no]= key_or_with_limit(param, key_no, key1, + key2))) { result_keys.set_bit(key_no); @@ -5440,7 +5443,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_with_limit(param, key, (*tree)->keys[key_idx]))) + key_or_with_limit(param, key_idx, key, (*tree)->keys[key_idx]))) (*changed_tree)->keys_map.set_bit(key_idx); *tree= NULL; removed_cnt++; @@ -9102,7 +9105,8 @@ 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_with_limit(param, key1, key2, flag))) + if ((result->keys[key_no]= key= key_and_with_limit(param, key_no, + key1, key2, flag))) { if (key && key->type == SEL_ARG::IMPOSSIBLE) { @@ -9645,7 +9649,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_with_limit(param, key1, key2))) + if ((result->keys[key_no]= key_or_with_limit(param, key_no, key1, key2))) result->keys_map.set_bit(key_no); } result->type= tree1->type; @@ -9968,11 +9972,12 @@ uint SEL_ARG::verify_weight() } #endif -static SEL_ARG *key_or_with_limit(RANGE_OPT_PARAM *param, - SEL_ARG *key1, SEL_ARG *key2) +static +SEL_ARG *key_or_with_limit(RANGE_OPT_PARAM *param, uint keyno, + SEL_ARG *key1, SEL_ARG *key2) { - SEL_ARG *res= enforce_sel_arg_weight_limit(param->thd, key_or(param, - key1, key2)); + SEL_ARG *res= key_or(param, key1, key2); + res= enforce_sel_arg_weight_limit(param, keyno, res); #ifndef DBUG_OFF if (res) res->verify_weight(); @@ -9981,13 +9986,12 @@ static SEL_ARG *key_or_with_limit(RANGE_OPT_PARAM *param, } -static SEL_ARG *key_and_with_limit(RANGE_OPT_PARAM *param, - SEL_ARG *key1, SEL_ARG *key2, - uint clone_flag) +static +SEL_ARG *key_and_with_limit(RANGE_OPT_PARAM *param, uint keyno, + SEL_ARG *key1, SEL_ARG *key2, uint clone_flag) { - SEL_ARG *res= enforce_sel_arg_weight_limit(param->thd, key_and(param, key1, - key2, - clone_flag)); + SEL_ARG *res= key_and(param, key1, key2, clone_flag); + res= enforce_sel_arg_weight_limit(param, keyno, res); #ifndef DBUG_OFF if (res) res->verify_weight(); @@ -10773,33 +10777,42 @@ void prune_sel_arg_graph(SEL_ARG *sel_arg, uint max_part) limit. */ -SEL_ARG *enforce_sel_arg_weight_limit(THD *thd, SEL_ARG *sel_arg) +SEL_ARG *enforce_sel_arg_weight_limit(RANGE_OPT_PARAM *param, uint keyno, + SEL_ARG *sel_arg) { if (!sel_arg || sel_arg->type != SEL_ARG::KEY_RANGE || - !thd->variables.optimizer_max_sel_arg_weight) + !param->thd->variables.optimizer_max_sel_arg_weight) return sel_arg; + uint weight1= sel_arg->weight; + while (1) { - if (sel_arg->weight <= thd->variables.optimizer_max_sel_arg_weight) - return sel_arg; + if (sel_arg->weight <= param->thd->variables.optimizer_max_sel_arg_weight) + break; 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 + { + sel_arg= NULL; + break; + } 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 + uint weight2= sel_arg? sel_arg->weight : 0; + + if (weight2 != weight1) + { + Json_writer_object wrapper(param->thd); + Json_writer_object obj(param->thd, "enforce_sel_arg_weight_limit"); + obj.add("index", param->table->key_info[param->real_keynr[keyno]].name); + obj.add("old_weight", (longlong)weight1); + obj.add("new_weight", (longlong)weight2); } + return sel_arg; } diff --git a/sql/opt_range.h b/sql/opt_range.h index 14b52d358b0..fe4e86c76e6 100644 --- a/sql/opt_range.h +++ b/sql/opt_range.h @@ -228,36 +228,43 @@ class RANGE_OPT_PARAM; A SEL_ARG graph has a property we call weight, and we define it as follows: + <definition> 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) + If there is a node with multiple incoming next_key_part edges, clone that + node, (and the nodes connected to it via prev/next links) and redirect one + of the incoming next_key_part edges to the clone. - 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. + Continue with cloning until we get a graph that has no nodes with multiple + incoming next_key_part edges. Then, the number of SEL_ARG objects in the + graph is the weight of the original graph. + </definition> Example: + kp1 $ kp2 $ kp3 + $ $ | +-------+ $ $ \->| kp1=2 |--$--------------$-+ +-------+ $ $ | +--------+ | $ $ ==>| kp3=11 | +-------+ $ $ | +--------+ - | kp1=3 |--$--------------$-+ | + | kp1>3 |--$--------------$-+ | +-------+ $ $ +--------+ $ $ | kp3=14 | $ $ +--------+ + $ $ | + $ $ +--------+ + $ $ | kp3=14 | + $ $ +--------+ - Here, the weight is 2 + 2*2=6. + Here, the weight is 2 + 2*3=8. - The rationale behind the weight is: + The rationale behind using this definition of 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 is a lot easier to compute than computing the number of ranges, - it can be updated incrementally when performing AND/OR operations on parts of the graph. */