~drizzle-trunk/drizzle/development

/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-

 *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:

 *

 *  Copyright (C) 2008-2009 Sun Microsystems, Inc.

 *

 *  This program is free software; you can redistribute it and/or modify

 *  it under the terms of the GNU General Public License as published by

 *  the Free Software Foundation; version 2 of the License.

 *

 *  This program is distributed in the hope that it will be useful,

 *  but WITHOUT ANY WARRANTY; without even the implied warranty of

 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 *  GNU General Public License for more details.

 *

 *  You should have received a copy of the GNU General Public License

 *  along with this program; if not, write to the Free Software

 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

 */

#pragma once

namespace drizzled {

namespace optimizer {

/*

  A construction block of the SEL_ARG-graph.

  The following description only covers graphs of SEL_ARG objects with

  sel_arg->type==KEY_RANGE:

  One SEL_ARG object represents an "elementary interval" in form

      min_value <=?  table.keypartX  <=? max_value

  The interval is a non-empty interval of any kind: with[out] minimum/maximum

  bound, [half]open/closed, single-point interval, etc.

  1. SEL_ARG GRAPH STRUCTURE

  SEL_ARG objects are linked together in a graph. The meaning of the graph

  is better demostrated by an example:

     tree->keys[i]

      |

      |             $              $

      |    part=1   $     part=2   $    part=3

      |             $              $

      |  +-------+  $   +-------+  $   +--------+

      |  | kp1<1 |--$-->| kp2=5 |--$-->| kp3=10 |

      |  +-------+  $   +-------+  $   +--------+

      |      |      $              $       |

      |      |      $              $   +--------+

      |      |      $              $   | kp3=12 |

      |      |      $              $   +--------+

      |  +-------+  $              $

      \->| kp1=2 |--$--------------$-+

         +-------+  $              $ |   +--------+

             |      $              $  ==>| kp3=11 |

         +-------+  $              $ |   +--------+

         | kp1=3 |--$--------------$-+       |

         +-------+  $              $     +--------+

             |      $              $     | kp3=14 |

            ...     $              $     +--------+

  The entire graph is partitioned into "interval lists".

  An interval list is a sequence of ordered disjoint intervals over the same

  key part. SEL_ARG are linked via "next" and "prev" pointers. Additionally,

  all intervals in the list form an RB-tree, linked via left/right/parent

  pointers. The RB-tree root SEL_ARG object will be further called "root of the

  interval list".

    In the example pic, there are 4 interval lists:

    "kp<1 OR kp1=2 OR kp1=3", "kp2=5", "kp3=10 OR kp3=12", "kp3=11 OR kp3=13".

    The vertical lines represent SEL_ARG::next/prev pointers.

  In an interval list, each member X may have SEL_ARG::next_key_part pointer

  pointing to the root of another interval list Y. The pointed interval list

  must cover a key part with greater number (i.e. Y->part > X->part).

    In the example pic, the next_key_part pointers are represented by

    horisontal lines.

  2. SEL_ARG GRAPH SEMANTICS

  It represents a condition in a special form (we don't have a name for it ATM)

  The SEL_ARG::next/prev is "OR", and next_key_part is "AND".

  For example, the picture represents the condition in form:

   (kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR

   (kp1=2 AND (kp3=11 OR kp3=14)) OR

   (kp1=3 AND (kp3=11 OR kp3=14))

  3. SEL_ARG GRAPH USE

  Use get_mm_tree() to construct SEL_ARG graph from WHERE condition.

  Then walk the SEL_ARG graph and get a list of dijsoint ordered key

  intervals (i.e. intervals in form

   (constA1, .., const1_K) < (keypart1,.., keypartK) < (constB1, .., constB_K)

  Those intervals can be used to access the index. The uses are in:

   - check_quick_select() - Walk the SEL_ARG graph and find an estimate of

                            how many table records are contained within all

                            intervals.

   - get_quick_select()   - Walk the SEL_ARG, materialize the key intervals,

                            and create QuickRangeSelect object that will

                            read records within these intervals.

  4. SPACE COMPLEXITY NOTES

    SEL_ARG graph is a representation of an ordered disjoint sequence of

    intervals over the ordered set of index tuple values.

    For multi-part keys, one can construct a WHERE expression such that its

    list of intervals will be of combinatorial size. Here is an example:

      (keypart1 IN (1,2, ..., n1)) AND

      (keypart2 IN (1,2, ..., n2)) AND

      (keypart3 IN (1,2, ..., n3))

    For this WHERE clause the list of intervals will have n1*n2*n3 intervals

    of form

      (keypart1, keypart2, keypart3) = (k1, k2, k3), where 1 <= k{i} <= n{i}

    SEL_ARG graph structure aims to reduce the amount of required space by

    "sharing" the elementary intervals when possible (the pic at the

    beginning of this comment has examples of such sharing). The sharing may

    prevent combinatorial blowup:

      There are WHERE clauses that have combinatorial-size interval lists but

      will be represented by a compact SEL_ARG graph.

      Example:

        (keypartN IN (1,2, ..., n1)) AND

        ...

        (keypart2 IN (1,2, ..., n2)) AND

        (keypart1 IN (1,2, ..., n3))

    but not in all cases:

    - There are WHERE clauses that do have a compact SEL_ARG-graph

      representation but get_mm_tree() and its callees will construct a

      graph of combinatorial size.

      Example:

        (keypart1 IN (1,2, ..., n1)) AND

        (keypart2 IN (1,2, ..., n2)) AND

        ...

        (keypartN IN (1,2, ..., n3))

    - There are WHERE clauses for which the minimal possible SEL_ARG graph

      representation will have combinatorial size.

      Example:

        By induction: Let's take any interval on some keypart in the middle:

           kp15=c0

        Then let's AND it with this interval 'structure' from preceding and

        following keyparts:

          (kp14=c1 AND kp16=c3) OR keypart14=c2) (*)

        We will obtain this SEL_ARG graph:

             kp14     $      kp15      $      kp16

                      $                $

         +---------+  $   +---------+  $   +---------+

         | kp14=c1 |--$-->| kp15=c0 |--$-->| kp16=c3 |

         +---------+  $   +---------+  $   +---------+

              |       $                $

         +---------+  $   +---------+  $

         | kp14=c2 |--$-->| kp15=c0 |  $

         +---------+  $   +---------+  $

                      $                $

       Note that we had to duplicate "kp15=c0" and there was no way to avoid

       that.

       The induction step: AND the obtained expression with another "wrapping"

       expression like (*).

       When the process ends because of the limit on max. number of keyparts

       we'll have:

         WHERE clause length  is O(3*#max_keyparts)

         SEL_ARG graph size   is O(2^(#max_keyparts/2))

       (it is also possible to construct a case where instead of 2 in 2^n we

        have a bigger constant, e.g. 4, and get a graph with 4^(31/2)= 2^31

        nodes)

    We avoid consuming too much memory by setting a limit on the number of

    SEL_ARG object we can construct during one range analysis invocation.

*/

class SEL_ARG :public memory::SqlAlloc

{

public:

  uint8_t min_flag,max_flag,maybe_flag;

  uint8_t part;					// Which key part

  uint8_t maybe_null;

  /*

    Number of children of this element in the RB-tree, plus 1 for this

    element itself.

  */

  uint16_t elements;

  /*

    Valid only for elements which are RB-tree roots: Number of times this

    RB-tree is referred to (it is referred by SEL_ARG::next_key_part or by

    SEL_TREE::keys[i] or by a temporary SEL_ARG* variable)

  */

  ulong use_count;

  Field *field;

  unsigned char *min_value,*max_value;			// Pointer to range

  /*

    eq_tree() requires that left == right == 0 if the type is MAYBE_KEY.

   */

  SEL_ARG *left,*right;   /* R-B tree children */

  SEL_ARG *next,*prev;    /* Links for bi-directional interval list */

  SEL_ARG *parent;        /* R-B tree parent */

  SEL_ARG *next_key_part;

  enum leaf_color { BLACK,RED } color;

  enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type;

  enum 

  { 

    MAX_SEL_ARGS = 16000 

  };

  SEL_ARG() {}

  SEL_ARG(SEL_ARG &);

  SEL_ARG(Field *,const unsigned char *, const unsigned char *);

  SEL_ARG(Field *field, 

          uint8_t part, 

          unsigned char *min_value, 

          unsigned char *max_value,

	        uint8_t min_flag, 

          uint8_t max_flag, 

          uint8_t maybe_flag);

  SEL_ARG(enum Type type_arg)

    :

      min_flag(0),

      elements(1),

      use_count(1),

      left(0),

      right(0),

      next_key_part(0),

      color(BLACK), 

      type(type_arg)

  {}

  int size() const

  {

    return elements;

  }

  inline bool is_same(SEL_ARG *arg)

  {

    if (type != arg->type || part != arg->part)

      return 0;

    if (type != KEY_RANGE)

      return 1;

    return (cmp_min_to_min(arg) == 0 && cmp_max_to_max(arg) == 0);

  }

  inline void merge_flags(SEL_ARG *arg) 

  { 

    maybe_flag|= arg->maybe_flag; 

  }

  inline void maybe_smaller() 

  { 

    maybe_flag= 1; 

  }

  /* Return true iff it's a single-point null interval */

  inline bool is_null_interval() 

  { 

    return (maybe_null && max_value[0] == 1);

  }

  inline int cmp_min_to_min(SEL_ARG *arg)

  {

    return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag);

  }

  inline int cmp_min_to_max(SEL_ARG *arg)

  {

    return sel_cmp(field,min_value, arg->max_value, min_flag, arg->max_flag);

  }

  inline int cmp_max_to_max(SEL_ARG *arg)

  {

    return sel_cmp(field,max_value, arg->max_value, max_flag, arg->max_flag);

  }

  inline int cmp_max_to_min(SEL_ARG *arg)

  {

    return sel_cmp(field,max_value, arg->min_value, max_flag, arg->min_flag);

  }

  SEL_ARG *clone_and(SEL_ARG *arg);

  SEL_ARG *clone_first(SEL_ARG *arg);

  SEL_ARG *clone_last(SEL_ARG *arg);

  SEL_ARG *clone(RangeParameter *param, SEL_ARG *new_parent, SEL_ARG **next);

  bool copy_min(SEL_ARG *arg);

  bool copy_max(SEL_ARG *arg);

  void copy_min_to_min(SEL_ARG *arg);

  void copy_min_to_max(SEL_ARG *arg);

  void copy_max_to_min(SEL_ARG *arg);

  /* returns a number of keypart values (0 or 1) appended to the key buffer */

  int store_min(uint32_t length, unsigned char **min_key, uint32_t min_key_flag);

  /* returns a number of keypart values (0 or 1) appended to the key buffer */

  int store_max(uint32_t length, unsigned char **max_key, uint32_t max_key_flag);

  /* returns a number of keypart values appended to the key buffer */

  int store_min_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag);

  /* returns a number of keypart values appended to the key buffer */

  int store_max_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag);

  SEL_ARG *insert(SEL_ARG *key);

  SEL_ARG *tree_delete(SEL_ARG *key);

  SEL_ARG *find_range(SEL_ARG *key);

  SEL_ARG *rb_insert(SEL_ARG *leaf);

  friend SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key, SEL_ARG *par);

  SEL_ARG *first();

  SEL_ARG *last();

  void make_root();

  inline bool simple_key()

  {

    return (! next_key_part && elements == 1);

  }

  void increment_use_count(long count)

  {

    if (next_key_part)

    {

      next_key_part->use_count+= count;

      count*= (next_key_part->use_count - count);

      for (SEL_ARG *pos= next_key_part->first(); pos; pos= pos->next)

        if (pos->next_key_part)

          pos->increment_use_count(count);

    }

  }

  void free_tree()

  {

    for (SEL_ARG *pos= first(); pos; pos= pos->next)

      if (pos->next_key_part)

      {

        pos->next_key_part->use_count--;

        pos->next_key_part->free_tree();

      }

  }

  inline SEL_ARG **parent_ptr()

  {

    return parent->left == this ? &parent->left : &parent->right;

  }

  /*

    Check if this SEL_ARG object represents a single-point interval

    SYNOPSIS

      is_singlepoint()

    DESCRIPTION

      Check if this SEL_ARG object (not tree) represents a single-point

      interval, i.e. if it represents a "keypart = const" or

      "keypart IS NULL".

    RETURN

      true   This SEL_ARG object represents a singlepoint interval

      false  Otherwise

  */

  bool is_singlepoint()

  {

    /*

      Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field)

      flags, and the same for right edge.

    */

    if (min_flag || max_flag)

      return false;

    unsigned char *min_val= min_value;

    unsigned char *max_val= max_value;

    if (maybe_null)

    {

      /* First byte is a NULL value indicator */

      if (*min_val != *max_val)

        return false;

      if (*min_val)

        return true; /* This "x IS NULL" */

      min_val++;

      max_val++;

    }

    return ! field->key_cmp(min_val, max_val);

  }

  SEL_ARG *clone_tree(RangeParameter *param);

private:

  /*

     Check if a compare is ok, when one takes ranges in account

     Returns -2 or 2 if the ranges where 'joined' like  < 2 and >= 2

   */

  int sel_cmp(Field *in_field, 

              unsigned char *a, 

              unsigned char *b, 

              uint8_t a_flag,

              uint8_t b_flag)

  {

    int cmp= 0;

    /* First check if there was a compare to a min or max element */

    if (a_flag & (NO_MIN_RANGE | NO_MAX_RANGE))

    {

      if ((a_flag & (NO_MIN_RANGE | NO_MAX_RANGE)) ==

          (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE)))

        return 0;

      return (a_flag & NO_MIN_RANGE) ? -1 : 1;

    }

    if (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE))

      return (b_flag & NO_MIN_RANGE) ? 1 : -1;

    if (in_field->real_maybe_null())			// If null is part of key

    {

      if (*a != *b)

      {

        return *a ? -1 : 1;

      }

      if (*a)

        goto end;					// NULL where equal

      a++; b++;					// Skip NULL marker

    }

    cmp= in_field->key_cmp(a , b);

    if (cmp) return cmp < 0 ? -1 : 1;		// The values differed

    // Check if the compared equal arguments was defined with open/closed range

end:

    if (a_flag & (NEAR_MIN | NEAR_MAX))

    {

      if ((a_flag & (NEAR_MIN | NEAR_MAX)) == (b_flag & (NEAR_MIN | NEAR_MAX)))

        return 0;

      if (! (b_flag & (NEAR_MIN | NEAR_MAX)))

        return (a_flag & NEAR_MIN) ? 2 : -2;

      return (a_flag & NEAR_MIN) ? 1 : -1;

    }

    if (b_flag & (NEAR_MIN | NEAR_MAX))

      return (b_flag & NEAR_MIN) ? -2 : 2;

    return 0;					// The elements where equal

  }

};

SEL_ARG *rb_delete_fixup(SEL_ARG *root,

                         SEL_ARG *key,

                         SEL_ARG *par);

extern SEL_ARG null_element;

} /* namespace optimizer */

} /* namespace drizzled */