Status: Closed (View Workflow)
Trying to figure out what does one needs to support descending index key parts in the range optimizer.
The range analyzer generates "ascending" SEL_ARG data structures. For example, for tbl.key < 10 it will generate a SEL_ARG(min=NULL, max=10).
There are two possible ways to handle DESC key parts:
- Change the generated SEL_ARG structures (so that for the above example, SEL_ARG(min=10, max=NULL) will be generated).
- Leave the SEL_ARG graph as-is, but flip min and max when interpreting it.
(Yes, the second is possible, because there's no "overlap" between key parts in SEL_ARG graphs. They are connected through SEL_ARG::next_key_part, but that's it).
When converting SEL_ARGs to range trees, one can't ignore the DESC attribute anymore.
Example: Consider an index key1(kp1, kp2 DESC)
and a WHERE clause
kp1 BETWEEN 10 and 20 AND kp2 BETWEEN 100 and 200
if both kp1 and kp2 were ASC, one would get this range
(10, 100) <= (kp1,kp2) <= (20, 200)
but since kp2 is DESC, the range needs to be
(10, 200) <= (kp1, kp2) <= (20, 100)
Suggestion how to handle range analyzer
Current solution candidate:
- Leave the range analyzer as-is
- When we are enumerating SEL_ARG graph, "flip" the SEL_ARG graph direction for DESC key parts
- Use min_value instead of max_value and vice versa.
- The same for min_flag and max_flag
- Also, flip SEL_ARG::last() with SEL_ARG::first() and next() with prev().
Overview of things to fix
The fix will be limited to the functions that "convert" SEL_ARG graphs into range bounds:
- sel_arg_range_seq_next() and step_down_to().
get_quick_keys() has a 'key' parameter, key[key_tree->part] has the key descriptor.
sel_arg_range_seq_next() has a pointer to the SEL_ARG_RANGE_SEQ, which can have a pointer to the key with a descriptor.
This will also need handling and is outside of the scope of this task.
What about MySQL
They do have SEL_ARG::is_ascending (Yes, in each SEL_ARG). I do not fully follow their reasoning.
- is part of
MDEV-13756 Implement descending index: KEY (a DESC, b ASC)
- relates to
MDEV-26939 support descending indexes for simple ORDER BY