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

Support descending indexes in the range optimizer



    • Type: Task
    • Status: In Testing (View Workflow)
    • Priority: Major
    • Resolution: Unresolved
    • Fix Version/s: 10.8
    • Component/s: Optimizer
    • Labels:


      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



              elenst Elena Stepanova
              psergei Sergei Petrunia
              0 Vote for this issue
              7 Start watching this issue



                  Git Integration