Uploaded image for project: 'MariaDB Server'
  1. MariaDB Server
  2. MDEV-26996

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.


      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.


        Issue Links



              serg Sergei Golubchik
              psergei Sergei Petrunia
              0 Vote for this issue
              8 Start watching this issue



                Git Integration

                  Error rendering 'com.xiplink.jira.git.jira_git_plugin:git-issue-webpanel'. Please contact your Jira administrators.