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