Drizzled Public API Documentation

sel_tree.h
00001 /* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
00002  *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
00003  *
00004  *  Copyright (C) 2008-2009 Sun Microsystems, Inc.
00005  *
00006  *  This program is free software; you can redistribute it and/or modify
00007  *  it under the terms of the GNU General Public License as published by
00008  *  the Free Software Foundation; version 2 of the License.
00009  *
00010  *  This program is distributed in the hope that it will be useful,
00011  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00012  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00013  *  GNU General Public License for more details.
00014  *
00015  *  You should have received a copy of the GNU General Public License
00016  *  along with this program; if not, write to the Free Software
00017  *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00018  */
00019 
00020 #pragma once
00021 
00022 #include <drizzled/memory/sql_alloc.h>
00023 
00024 namespace drizzled
00025 {
00026 
00027 namespace optimizer
00028 {
00029 
00030 class RangeParameter;
00031 class SEL_IMERGE;
00032 class SEL_ARG;
00033 class RorScanInfo;
00034 
00035 class SEL_TREE : public drizzled::memory::SqlAlloc
00036 {
00037 public:
00038   /*
00039     Starting an effort to document this field:
00040     (for some i, keys[i]->type == optimizer::SEL_ARG::IMPOSSIBLE) =>
00041        (type == SEL_TREE::IMPOSSIBLE)
00042   */
00043   enum Type
00044   {
00045     IMPOSSIBLE,
00046     ALWAYS,
00047     MAYBE,
00048     KEY,
00049     KEY_SMALLER
00050   } type;
00051 
00052   SEL_TREE(enum Type type_arg) :type(type_arg) {}
00053   SEL_TREE() :type(KEY)
00054   {
00055     keys_map.reset();
00056     memset(keys, 0, sizeof(keys));
00057   }
00058   /*
00059     Note: there may exist SEL_TREE objects with sel_tree->type=KEY and
00060     keys[i]=0 for all i. (SergeyP: it is not clear whether there is any
00061     merit in range analyzer functions (e.g. get_mm_parts) returning a
00062     pointer to such SEL_TREE instead of NULL)
00063   */
00064   SEL_ARG *keys[MAX_KEY];
00065   key_map keys_map;        /* bitmask of non-NULL elements in keys */
00066 
00067   /*
00068     Possible ways to read rows using index_merge. The list is non-empty only
00069     if type==KEY. Currently can be non empty only if keys_map.none().
00070   */
00071   List<SEL_IMERGE> merges;
00072 
00073   /* The members below are filled/used only after get_mm_tree is done */
00074   key_map ror_scans_map;   /* bitmask of ROR scan-able elements in keys */
00075   uint32_t n_ror_scans;     /* number of set bits in ror_scans_map */
00076 
00077   RorScanInfo **ror_scans;     /* list of ROR key scans */
00078   RorScanInfo **ror_scans_end; /* last ROR scan */
00079   /* Note that #records for each key scan is stored in table->quick_rows */
00080 
00081 };
00082 
00083 /*
00084   Check if two optimizer::SEL_TREES can be combined into one (i.e. a single key range
00085   read can be constructed for "cond_of_tree1 OR cond_of_tree2" ) without
00086   using index_merge.
00087 */
00088 bool sel_trees_can_be_ored(SEL_TREE *tree1, 
00089                            SEL_TREE *tree2,
00090                            RangeParameter* param);
00091 
00092 SEL_TREE *
00093 tree_or(RangeParameter *param, SEL_TREE *tree1, SEL_TREE *tree2);
00094 
00095 /*
00096    Remove the trees that are not suitable for record retrieval.
00097    SYNOPSIS
00098    param  Range analysis parameter
00099    tree   Tree to be processed, tree->type is KEY or KEY_SMALLER
00100 
00101    DESCRIPTION
00102    This function walks through tree->keys[] and removes the SEL_ARG* trees
00103    that are not "maybe" trees (*) and cannot be used to construct quick range
00104    selects.
00105    (*) - have type MAYBE or MAYBE_KEY. Perhaps we should remove trees of
00106    these types here as well.
00107 
00108    A SEL_ARG* tree cannot be used to construct quick select if it has
00109    tree->part != 0. (e.g. it could represent "keypart2 < const").
00110 
00111    WHY THIS FUNCTION IS NEEDED
00112 
00113    Normally we allow construction of optimizer::SEL_TREE objects that have SEL_ARG
00114    trees that do not allow quick range select construction. For example for
00115    " keypart1=1 AND keypart2=2 " the execution will proceed as follows:
00116    tree1= optimizer::SEL_TREE { SEL_ARG{keypart1=1} }
00117    tree2= optimizer::SEL_TREE { SEL_ARG{keypart2=2} } -- can't make quick range select
00118    from this
00119    call tree_and(tree1, tree2) -- this joins SEL_ARGs into a usable SEL_ARG
00120    tree.
00121 
00122    There is an exception though: when we construct index_merge optimizer::SEL_TREE,
00123    any SEL_ARG* tree that cannot be used to construct quick range select can
00124    be removed, because current range analysis code doesn't provide any way
00125    that tree could be later combined with another tree.
00126    Consider an example: we should not construct
00127    st1 = optimizer::SEL_TREE {
00128    merges = SEL_IMERGE {
00129    optimizer::SEL_TREE(t.key1part1 = 1),
00130    optimizer::SEL_TREE(t.key2part2 = 2)   -- (*)
00131    }
00132    };
00133    because
00134    - (*) cannot be used to construct quick range select,
00135    - There is no execution path that would cause (*) to be converted to
00136    a tree that could be used.
00137 
00138    The latter is easy to verify: first, notice that the only way to convert
00139    (*) into a usable tree is to call tree_and(something, (*)).
00140 
00141    Second look at what tree_and/tree_or function would do when passed a
00142    optimizer::SEL_TREE that has the structure like st1 tree has, and conlcude that
00143    tree_and(something, (*)) will not be called.
00144 
00145    RETURN
00146    0  Ok, some suitable trees left
00147    1  No tree->keys[] left.
00148  */
00149 bool remove_nonrange_trees(RangeParameter *param, SEL_TREE *tree);
00150 
00151 } /* namespace optimizer */
00152 
00153 } /* namespace drizzled */
00154