Support descending indexes in the range optimizer

Trying to figure out what does one needs to support descending index key parts in the range optimizer.

Range analyzer

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:

1. sel_arg_range_seq_next() and step_down_to().
2. get_quick_keys()

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.

Handling QUICK_GROUP_MIN_MAX_SELECT

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.