revision-id: 59af76ef3434a4beb21c7e7c52800b539be23b7f (mariadb-10.6.1-250-g59af76ef343) parent(s): de4426358101575648e968b4cdae35527da74b23 author: Sergei Petrunia committer: Sergei Petrunia timestamp: 2021-12-20 23:51:55 +0300 message: Reverse-ordered indexes: remove SEL_ARG::is_ascending Get the information from the array of KEY_PART structures that describes the [pseudo-]index that is being analyzed. --- sql/item_geofunc.cc | 2 +- sql/opt_range.cc | 76 +++++++++++++++++++++++++--------------------------- sql/opt_range.h | 55 +++++++++++++++++-------------------- sql/opt_range_mrr.cc | 27 ++++++++++--------- 4 files changed, 77 insertions(+), 83 deletions(-) diff --git a/sql/item_geofunc.cc b/sql/item_geofunc.cc index a2a99bcdf8f..0fdcf9e94e2 100644 --- a/sql/item_geofunc.cc +++ b/sql/item_geofunc.cc @@ -1084,7 +1084,7 @@ Item_func_spatial_rel::get_mm_leaf(RANGE_OPT_PARAM *param, field->get_key_image(str, key_part->length, key_part->image_type); SEL_ARG *tree; - if (!(tree= new (param->mem_root) SEL_ARG(field, true, str, str))) + if (!(tree= new (param->mem_root) SEL_ARG(field, str, str))) DBUG_RETURN(0); // out of memory switch (type) { diff --git a/sql/opt_range.cc b/sql/opt_range.cc index ae2b5060625..bbb7b3d87fa 100644 --- a/sql/opt_range.cc +++ b/sql/opt_range.cc @@ -1879,7 +1879,6 @@ SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_alloc() max_flag=arg.max_flag; maybe_flag=arg.maybe_flag; maybe_null=arg.maybe_null; - is_ascending= arg.is_ascending; part=arg.part; field=arg.field; min_value=arg.min_value; @@ -1905,10 +1904,9 @@ inline void SEL_ARG::make_root() use_count=0; elements=1; } -SEL_ARG::SEL_ARG(Field *f, bool is_asc, const uchar *min_value_arg, +SEL_ARG::SEL_ARG(Field *f, const uchar *min_value_arg, const uchar *max_value_arg) :min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()), - is_ascending(is_asc), 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), weight(1) @@ -1917,11 +1915,11 @@ SEL_ARG::SEL_ARG(Field *f, bool is_asc, const uchar *min_value_arg, max_part_no= 1; } -SEL_ARG::SEL_ARG(Field *field_,uint8 part_, bool is_asc_, +SEL_ARG::SEL_ARG(Field *field_,uint8 part_, uchar *min_value_, uchar *max_value_, uint8 min_flag_,uint8 max_flag_,uint8 maybe_flag_) :min_flag(min_flag_),max_flag(max_flag_),maybe_flag(maybe_flag_), - part(part_),maybe_null(field_->real_maybe_null()), is_ascending(is_asc_), + 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), weight(1) @@ -1941,8 +1939,8 @@ SEL_ARG::SEL_ARG(Field *field_,uint8 part_, bool is_asc_, class SEL_ARG_LE: public SEL_ARG { public: - SEL_ARG_LE(const uchar *key, Field *field, bool is_asc) - :SEL_ARG(field, is_asc, key, key) + SEL_ARG_LE(const uchar *key, Field *field) + :SEL_ARG(field, key, key) { if (!field->real_maybe_null()) min_flag= NO_MIN_RANGE; // From start @@ -1962,17 +1960,17 @@ class SEL_ARG_LT: public SEL_ARG_LE Use this constructor if value->save_in_field() went precisely, without any data rounding or truncation. */ - SEL_ARG_LT(const uchar *key, Field *field, bool is_asc) - :SEL_ARG_LE(key, field, is_asc) + SEL_ARG_LT(const uchar *key, Field *field) + :SEL_ARG_LE(key, field) { max_flag= NEAR_MAX; } /* Use this constructor if value->save_in_field() returned success, but we don't know if rounding or truncation happened (as some Field::store() do not report minor data changes). */ - SEL_ARG_LT(THD *thd, const uchar *key, Field *field, bool is_asc, + SEL_ARG_LT(THD *thd, const uchar *key, Field *field, Item *value) - :SEL_ARG_LE(key, field, is_asc) + :SEL_ARG_LE(key, field) { if (stored_field_cmp_to_item(thd, field, value) == 0) max_flag= NEAR_MAX; @@ -1988,7 +1986,7 @@ class SEL_ARG_GT: public SEL_ARG without any data rounding or truncation. */ SEL_ARG_GT(const uchar *key, const KEY_PART *key_part, Field *field) - :SEL_ARG(field, !(key_part->flag & HA_REVERSE_SORT), key, key) + :SEL_ARG(field, key, key) { // Don't use open ranges for partial key_segments if (!(key_part->flag & HA_PART_KEY_SEG)) @@ -2002,7 +2000,7 @@ class SEL_ARG_GT: public SEL_ARG */ SEL_ARG_GT(THD *thd, const uchar *key, const KEY_PART *key_part, Field *field, Item *value) - :SEL_ARG(field, !(key_part->flag & HA_REVERSE_SORT), key, key) + :SEL_ARG(field, key, key) { // Don't use open ranges for partial key_segments if ((!(key_part->flag & HA_PART_KEY_SEG)) && @@ -2020,8 +2018,8 @@ class SEL_ARG_GE: public SEL_ARG Use this constructor if value->save_in_field() went precisely, without any data rounding or truncation. */ - SEL_ARG_GE(const uchar *key, Field *field, bool is_asc) - :SEL_ARG(field, is_asc, key, key) + SEL_ARG_GE(const uchar *key, Field *field) + :SEL_ARG(field, key, key) { max_flag= NO_MAX_RANGE; } @@ -2032,7 +2030,7 @@ class SEL_ARG_GE: public SEL_ARG */ SEL_ARG_GE(THD *thd, const uchar *key, const KEY_PART *key_part, Field *field, Item *value) - :SEL_ARG(field, !(key_part->flag & HA_REVERSE_SORT), key, key) + :SEL_ARG(field, key, key) { // Don't use open ranges for partial key_segments if ((!(key_part->flag & HA_PART_KEY_SEG)) && @@ -2063,7 +2061,7 @@ SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, } else { - if (!(tmp= new (param->mem_root) SEL_ARG(field, part, is_ascending, + if (!(tmp= new (param->mem_root) SEL_ARG(field, part, min_value, max_value, min_flag, max_flag, maybe_flag))) return 0; // OOM @@ -3244,6 +3242,7 @@ double records_in_column_ranges(PARAM *param, uint idx, seq.keyno= idx; seq.real_keyno= MAX_KEY; + seq.key_parts= param->key[idx]; seq.param= param; seq.start= tree; seq.is_ror_scan= FALSE; @@ -8669,8 +8668,7 @@ Item_func_null_predicate::get_mm_leaf(RANGE_OPT_PARAM *param, if (!field->real_maybe_null()) DBUG_RETURN(type == ISNULL_FUNC ? &null_element : NULL); SEL_ARG *tree; - bool is_asc= !(key_part->flag & HA_REVERSE_SORT); - if (!(tree= new (alloc) SEL_ARG(field, is_asc, is_null_string, is_null_string))) + if (!(tree= new (alloc) SEL_ARG(field, is_null_string, is_null_string))) DBUG_RETURN(0); if (type == Item_func::ISNOTNULL_FUNC) { @@ -8770,8 +8768,7 @@ Item_func_like::get_mm_leaf(RANGE_OPT_PARAM *param, int2store(min_str + maybe_null, min_length); int2store(max_str + maybe_null, max_length); } - bool is_asc= !(key_part->flag & HA_REVERSE_SORT); - SEL_ARG *tree= new (param->mem_root) SEL_ARG(field, is_asc, min_str, max_str); + SEL_ARG *tree= new (param->mem_root) SEL_ARG(field, min_str, max_str); DBUG_RETURN(tree); } @@ -9019,19 +9016,18 @@ SEL_ARG *Field::stored_field_make_mm_leaf(RANGE_OPT_PARAM *param, if (!(str= make_key_image(param->mem_root, key_part))) DBUG_RETURN(0); - bool is_asc= !(key_part->flag & HA_REVERSE_SORT); switch (op) { case SCALAR_CMP_LE: - DBUG_RETURN(new (mem_root) SEL_ARG_LE(str, this, is_asc)); + DBUG_RETURN(new (mem_root) SEL_ARG_LE(str, this)); case SCALAR_CMP_LT: - DBUG_RETURN(new (mem_root) SEL_ARG_LT(thd, str, this, is_asc, value)); + DBUG_RETURN(new (mem_root) SEL_ARG_LT(thd, str, this, value)); case SCALAR_CMP_GT: DBUG_RETURN(new (mem_root) SEL_ARG_GT(thd, str, key_part, this, value)); case SCALAR_CMP_GE: DBUG_RETURN(new (mem_root) SEL_ARG_GE(thd, str, key_part, this, value)); case SCALAR_CMP_EQ: case SCALAR_CMP_EQUAL: - DBUG_RETURN(new (mem_root) SEL_ARG(this, is_asc, str, str)); + DBUG_RETURN(new (mem_root) SEL_ARG(this, str, str)); break; } DBUG_ASSERT(0); @@ -9049,19 +9045,18 @@ SEL_ARG *Field::stored_field_make_mm_leaf_exact(RANGE_OPT_PARAM *param, if (!(str= make_key_image(param->mem_root, key_part))) DBUG_RETURN(0); - bool is_asc= !(key_part->flag & HA_REVERSE_SORT); switch (op) { case SCALAR_CMP_LE: - DBUG_RETURN(new (param->mem_root) SEL_ARG_LE(str, this, is_asc)); + DBUG_RETURN(new (param->mem_root) SEL_ARG_LE(str, this)); case SCALAR_CMP_LT: - DBUG_RETURN(new (param->mem_root) SEL_ARG_LT(str, this, is_asc)); + DBUG_RETURN(new (param->mem_root) SEL_ARG_LT(str, this)); case SCALAR_CMP_GT: DBUG_RETURN(new (param->mem_root) SEL_ARG_GT(str, key_part, this)); case SCALAR_CMP_GE: - DBUG_RETURN(new (param->mem_root) SEL_ARG_GE(str, this, is_asc)); + DBUG_RETURN(new (param->mem_root) SEL_ARG_GE(str, this)); case SCALAR_CMP_EQ: case SCALAR_CMP_EQUAL: - DBUG_RETURN(new (param->mem_root) SEL_ARG(this, is_asc, str, str)); + DBUG_RETURN(new (param->mem_root) SEL_ARG(this, str, str)); break; } DBUG_ASSERT(0); @@ -11531,6 +11526,7 @@ ha_rows check_quick_select(PARAM *param, uint idx, bool index_only, seq.keyno= idx; seq.real_keyno= keynr; + seq.key_parts= param->key[idx]; seq.param= param; seq.start= tree; @@ -11785,9 +11781,9 @@ void SEL_ARG::store_next_min_max_keys(KEY_PART *key, int *min_part, int *max_part) { DBUG_ASSERT(next_key_part); - bool asc = next_key_part->is_ascending; + const bool asc = !(key[next_key_part->part].flag & HA_REVERSE_SORT); - if (!get_min_flag()) + if (!get_min_flag(key)) { if (asc) { @@ -11802,7 +11798,7 @@ void SEL_ARG::store_next_min_max_keys(KEY_PART *key, *cur_min_flag = invert_max_flag(tmp_flag); } } - if (!get_max_flag()) + if (!get_max_flag(key)) { if (asc) { @@ -11832,7 +11828,8 @@ get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key, int min_part= key_tree->part-1, // # of keypart values in min_key buffer max_part= key_tree->part-1; // # of keypart values in max_key buffer - SEL_ARG *next_tree = key_tree->is_ascending ? key_tree->left : key_tree->right; + const bool asc = !(key[key_tree->part].flag & HA_REVERSE_SORT); + SEL_ARG *next_tree = asc ? key_tree->left : key_tree->right; if (next_tree != &null_element) { if (get_quick_keys(param,quick,key,next_tree, @@ -11841,7 +11838,7 @@ get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key, } uchar *tmp_min_key=min_key,*tmp_max_key=max_key; - key_tree->store_min_max(key[key_tree->part].store_length, + key_tree->store_min_max(key, key[key_tree->part].store_length, &tmp_min_key, min_key_flag, &tmp_max_key, max_key_flag, &min_part, &max_part); @@ -11864,8 +11861,8 @@ get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key, goto end; // Ugly, but efficient } { - uint tmp_min_flag= key_tree->get_min_flag(); - uint tmp_max_flag= key_tree->get_max_flag(); + uint tmp_min_flag= key_tree->get_min_flag(key); + uint tmp_max_flag= key_tree->get_max_flag(key); key_tree->store_next_min_max_keys(key, &tmp_min_key, &tmp_min_flag, @@ -11876,7 +11873,7 @@ get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key, } else { - if (key_tree->is_ascending) + if (asc) { flag= (key_tree->min_flag & GEOM_FLAG) ? key_tree->min_flag: (key_tree->min_flag | @@ -11948,7 +11945,7 @@ get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key, return 1; end: - next_tree = key_tree->is_ascending ? key_tree->right : key_tree->left; + next_tree= asc ? key_tree->right : key_tree->left; if (next_tree != &null_element) return get_quick_keys(param,quick,key,next_tree, min_key,min_key_flag, @@ -16559,6 +16556,7 @@ static void trace_ranges(Json_writer_array *range_trace, uint n_key_parts= param->table->actual_n_key_parts(keyinfo); DBUG_ASSERT(range_trace->trace_started()); seq.keyno= idx; + seq.key_parts= param->key[idx]; seq.real_keyno= param->real_keynr[idx]; seq.param= param; seq.start= keypart; diff --git a/sql/opt_range.h b/sql/opt_range.h index 6864a5c583a..f3ccd4d8311 100644 --- a/sql/opt_range.h +++ b/sql/opt_range.h @@ -306,11 +306,6 @@ class SEL_ARG :public Sql_alloc uint8 min_flag,max_flag,maybe_flag; uint8 part; // Which key part uint8 maybe_null; - /* - Whether the keypart is ascending or descending. - See HowRangeOptimizerHandlesDescKeyparts for details. - */ - uint8 is_ascending; /* The ordinal number the least significant component encountered in the ranges of the SEL_ARG tree (the first component has number 1) @@ -361,14 +356,14 @@ class SEL_ARG :public Sql_alloc SEL_ARG() {} SEL_ARG(SEL_ARG &); - SEL_ARG(Field *, bool is_asc, const uchar *, const uchar *); - SEL_ARG(Field *field, uint8 part, bool is_asc, + SEL_ARG(Field *, const uchar *, const uchar *); + SEL_ARG(Field *field, uint8 part, uchar *min_value, uchar *max_value, uint8 min_flag, uint8 max_flag, uint8 maybe_flag); /* This is used to construct degenerate SEL_ARGS like ALWAYS, IMPOSSIBLE, etc */ SEL_ARG(enum Type type_arg) - :min_flag(0), is_ascending(false), + :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), weight(1) @@ -447,20 +442,20 @@ class SEL_ARG :public Sql_alloc { new_max=arg->max_value; flag_max=arg->max_flag; } - return new (thd->mem_root) SEL_ARG(field, part, is_ascending, + return new (thd->mem_root) SEL_ARG(field, part, new_min, new_max, flag_min, flag_max, MY_TEST(maybe_flag && arg->maybe_flag)); } SEL_ARG *clone_first(SEL_ARG *arg) { // min <= X < arg->min - return new SEL_ARG(field, part, is_ascending, min_value, arg->min_value, + return new SEL_ARG(field, part, min_value, arg->min_value, min_flag, arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX, maybe_flag | arg->maybe_flag); } SEL_ARG *clone_last(SEL_ARG *arg) { // min <= X <= key_max - return new SEL_ARG(field, part, is_ascending, min_value, arg->max_value, + return new SEL_ARG(field, part, min_value, arg->max_value, min_flag, arg->max_flag, maybe_flag | arg->maybe_flag); } SEL_ARG *clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, SEL_ARG **next); @@ -544,44 +539,45 @@ class SEL_ARG :public Sql_alloc } /* Save minimum and maximum, taking index order into account */ - void store_min_max(uint length, + void store_min_max(KEY_PART *kp, + uint length, uchar **min_key, uint min_flag, uchar **max_key, uint max_flag, int *min_part, int *max_part) { - if (is_ascending) { - *min_part += store_min(length, min_key, min_flag); - *max_part += store_max(length, max_key, max_flag); - } else { + if (kp[part].flag & HA_REVERSE_SORT) { *max_part += store_min(length, max_key, min_flag); *min_part += store_max(length, min_key, max_flag); + } else { + *min_part += store_min(length, min_key, min_flag); + *max_part += store_max(length, max_key, max_flag); } } /* Get the flag for range's starting endpoint, taking index order into account. */ - uint get_min_flag() + uint get_min_flag(KEY_PART *kp) { - return (is_ascending ? min_flag : invert_max_flag(max_flag)); + return (kp[part].flag & HA_REVERSE_SORT)? invert_max_flag(max_flag) : min_flag; } /* Get the flag for range's starting endpoint, taking index order into account. */ - uint get_max_flag() + uint get_max_flag(KEY_PART *kp) { - return (is_ascending ? max_flag : invert_min_flag(min_flag)); + return (kp[part].flag & HA_REVERSE_SORT)? invert_min_flag(min_flag) : max_flag ; } /* Get the previous interval, taking index order into account */ - inline SEL_ARG* index_order_prev() + inline SEL_ARG* index_order_prev(KEY_PART *kp) { - return is_ascending? prev: next; + return (kp[part].flag & HA_REVERSE_SORT)? next : prev; } /* Get the next interval, taking index order into account */ - inline SEL_ARG* index_order_next() + inline SEL_ARG* index_order_next(KEY_PART *kp) { - return is_ascending? next: prev; + return (kp[part].flag & HA_REVERSE_SORT)? prev : next; } /* @@ -621,7 +617,7 @@ class SEL_ARG :public Sql_alloc nkp->part == key_tree->part+1 && !(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN))) { - const bool asc = nkp->is_ascending; + const bool asc = !(key[key_tree->part].flag & HA_REVERSE_SORT); if (start_key == asc) { res+= nkp->store_min_key(key, range_key, range_key_flag, last_part, @@ -657,7 +653,7 @@ class SEL_ARG :public Sql_alloc nkp->part == key_tree->part+1 && !(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX))) { - const bool asc = nkp->is_ascending; + const bool asc = !(key[key_tree->part].flag & HA_REVERSE_SORT); if ((!start_key && asc) || (start_key && !asc)) { res += nkp->store_max_key(key, range_key, range_key_flag, last_part, @@ -785,9 +781,6 @@ class SEL_ARG :public Sql_alloc Range Optimizer handles this as follows: - The SEL_ARG object has SEL_ARG::is_ascending which specifies whether the - keypart is ascending. - Other than that, the SEL_ARG graph is built without any regard to DESC keyparts. @@ -799,7 +792,7 @@ class SEL_ARG :public Sql_alloc kp1 BETWEEN 10 and 20 (RANGE-1) - the SEL_ARG will have min_value=10, max_value=20, is_ascending=false. + the SEL_ARG will have min_value=10, max_value=20 The ordering of key parts is taken into account when SEL_ARG graph is linearized to ranges, in sel_arg_range_seq_next() and get_quick_keys(). @@ -850,7 +843,7 @@ class SEL_ARG_IMPOSSIBLE: public SEL_ARG { public: SEL_ARG_IMPOSSIBLE(Field *field) - :SEL_ARG(field, false, 0, 0) + :SEL_ARG(field, 0, 0) { type= SEL_ARG::IMPOSSIBLE; } diff --git a/sql/opt_range_mrr.cc b/sql/opt_range_mrr.cc index 8877e15d5b5..452a6864f06 100644 --- a/sql/opt_range_mrr.cc +++ b/sql/opt_range_mrr.cc @@ -47,6 +47,7 @@ typedef struct st_sel_arg_range_seq uint keyno; /* index of used tree in SEL_TREE structure */ uint real_keyno; /* Number of the index in tables */ PARAM *param; + KEY_PART *key_parts; SEL_ARG *start; /* Root node of the traversed SEL_ARG* graph */ RANGE_SEQ_ENTRY stack[MAX_REF_PARTS]; @@ -106,13 +107,13 @@ static void step_down_to(SEL_ARG_RANGE_SEQ *arg, SEL_ARG *key_tree) uint16 stor_length= arg->param->key[arg->keyno][key_tree->part].store_length; - key_tree->store_min_max(stor_length, + key_tree->store_min_max(arg->key_parts, stor_length, &cur->min_key, prev->min_key_flag, &cur->max_key, prev->max_key_flag, &cur->min_key_parts, &cur->max_key_parts); - cur->min_key_flag= prev->min_key_flag | key_tree->get_min_flag(); - cur->max_key_flag= prev->max_key_flag | key_tree->get_max_flag(); + cur->min_key_flag= prev->min_key_flag | key_tree->get_min_flag(arg->key_parts); + cur->max_key_flag= prev->max_key_flag | key_tree->get_max_flag(arg->key_parts); if (key_tree->is_null_interval()) cur->min_key_flag |= NULL_RANGE; @@ -166,12 +167,13 @@ bool sel_arg_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range) /* Ok, we're at some "full tuple" position in the tree */ /* Step down if we can */ - if (key_tree->index_order_next() && key_tree->index_order_next() != &null_element) + if (key_tree->index_order_next(seq->key_parts) && + key_tree->index_order_next(seq->key_parts) != &null_element) { //step down; (update the tuple, we'll step right and stay there) seq->i--; - step_down_to(seq, key_tree->index_order_next()); - key_tree= key_tree->index_order_next(); + step_down_to(seq, key_tree->index_order_next(seq->key_parts)); + key_tree= key_tree->index_order_next(seq->key_parts); seq->is_ror_scan= FALSE; goto walk_right_n_up; } @@ -186,12 +188,13 @@ bool sel_arg_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range) key_tree= seq->stack[seq->i].key_tree; /* Step down if we can */ - if (key_tree->index_order_next() && key_tree->index_order_next() != &null_element) + if (key_tree->index_order_next(seq->key_parts) && + key_tree->index_order_next(seq->key_parts) != &null_element) { // Step down; update the tuple seq->i--; - step_down_to(seq, key_tree->index_order_next()); - key_tree= key_tree->index_order_next(); + step_down_to(seq, key_tree->index_order_next(seq->key_parts)); + key_tree= key_tree->index_order_next(seq->key_parts); break; } } @@ -230,11 +233,11 @@ bool sel_arg_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range) key_tree= key_tree->next_key_part; walk_up_n_right: - while (key_tree->index_order_prev() && - key_tree->index_order_prev() != &null_element) + while (key_tree->index_order_prev(seq->key_parts) && + key_tree->index_order_prev(seq->key_parts) != &null_element) { /* Step up */ - key_tree= key_tree->index_order_prev(); + key_tree= key_tree->index_order_prev(seq->key_parts); } step_down_to(seq, key_tree); }