← Back to branch summary

~ubuntu-branches/ubuntu/trusty/drizzle/trusty

« back to all changes in this revision

Viewing changes to drizzled/optimizer/sel_tree.h

  • Committer: Bazaar Package Importer
  • Author(s): Monty Taylor
  • Date: 2010-10-02 14:17:48 UTC
  • mfrom: (1.1.1 upstream)
  • mto: (2.1.17 sid)
  • mto: This revision was merged to the branch mainline in revision 3.
  • Revision ID: james.westby@ubuntu.com-20101002141748-m6vbfbfjhrw1153e
Tags: 2010.09.1802-1
* New upstream release.
* Removed pid-file argument hack.
* Updated GPL-2 address to be new address.
* Directly copy in drizzledump.1 since debian doesn't have sphinx 1.0 yet.
* Link to jquery from libjs-jquery. Add it as a depend.
* Add drizzled.8 symlink to the install files.

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/optimizer/sel_tree.h
 
1
/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
 
2
 *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
 
3
 *
 
4
 *  Copyright (C) 2008-2009 Sun Microsystems
 
5
 *
 
6
 *  This program is free software; you can redistribute it and/or modify
 
7
 *  it under the terms of the GNU General Public License as published by
 
8
 *  the Free Software Foundation; version 2 of the License.
 
9
 *
 
10
 *  This program is distributed in the hope that it will be useful,
 
11
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
12
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
13
 *  GNU General Public License for more details.
 
14
 *
 
15
 *  You should have received a copy of the GNU General Public License
 
16
 *  along with this program; if not, write to the Free Software
 
17
 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 
18
 */
 
19
 
 
20
#ifndef DRIZZLED_OPTIMIZER_SEL_TREE_H
 
21
#define DRIZZLED_OPTIMIZER_SEL_TREE_H
 
22
 
 
23
#include "drizzled/memory/sql_alloc.h"
 
24
 
 
25
namespace drizzled
 
26
{
 
27
 
 
28
namespace optimizer
 
29
{
 
30
 
 
31
class RangeParameter;
 
32
class SEL_IMERGE;
 
33
class SEL_ARG;
 
34
 
 
35
class SEL_TREE : public drizzled::memory::SqlAlloc
 
36
{
 
37
public:
 
38
  /*
 
39
    Starting an effort to document this field:
 
40
    (for some i, keys[i]->type == optimizer::SEL_ARG::IMPOSSIBLE) =>
 
41
       (type == SEL_TREE::IMPOSSIBLE)
 
42
  */
 
43
  enum Type
 
44
  {
 
45
    IMPOSSIBLE,
 
46
    ALWAYS,
 
47
    MAYBE,
 
48
    KEY,
 
49
    KEY_SMALLER
 
50
  } type;
 
51
 
 
52
  SEL_TREE(enum Type type_arg) :type(type_arg) {}
 
53
  SEL_TREE() :type(KEY)
 
54
  {
 
55
    keys_map.reset();
 
56
    memset(keys, 0, sizeof(keys));
 
57
  }
 
58
  /*
 
59
    Note: there may exist SEL_TREE objects with sel_tree->type=KEY and
 
60
    keys[i]=0 for all i. (SergeyP: it is not clear whether there is any
 
61
    merit in range analyzer functions (e.g. get_mm_parts) returning a
 
62
    pointer to such SEL_TREE instead of NULL)
 
63
  */
 
64
  SEL_ARG *keys[MAX_KEY];
 
65
  key_map keys_map;        /* bitmask of non-NULL elements in keys */
 
66
 
 
67
  /*
 
68
    Possible ways to read rows using index_merge. The list is non-empty only
 
69
    if type==KEY. Currently can be non empty only if keys_map.none().
 
70
  */
 
71
  List<SEL_IMERGE> merges;
 
72
 
 
73
  /* The members below are filled/used only after get_mm_tree is done */
 
74
  key_map ror_scans_map;   /* bitmask of ROR scan-able elements in keys */
 
75
  uint32_t n_ror_scans;     /* number of set bits in ror_scans_map */
 
76
 
 
77
  struct st_ror_scan_info **ror_scans;     /* list of ROR key scans */
 
78
  struct st_ror_scan_info **ror_scans_end; /* last ROR scan */
 
79
  /* Note that #records for each key scan is stored in table->quick_rows */
 
80
 
 
81
};
 
82
 
 
83
/*
 
84
  Check if two optimizer::SEL_TREES can be combined into one (i.e. a single key range
 
85
  read can be constructed for "cond_of_tree1 OR cond_of_tree2" ) without
 
86
  using index_merge.
 
87
*/
 
88
bool sel_trees_can_be_ored(SEL_TREE *tree1, 
 
89
                           SEL_TREE *tree2,
 
90
                           RangeParameter* param);
 
91
 
 
92
SEL_TREE *
 
93
tree_or(RangeParameter *param, SEL_TREE *tree1, SEL_TREE *tree2);
 
94
 
 
95
/*
 
96
   Remove the trees that are not suitable for record retrieval.
 
97
   SYNOPSIS
 
98
   param  Range analysis parameter
 
99
   tree   Tree to be processed, tree->type is KEY or KEY_SMALLER
 
100
 
 
101
   DESCRIPTION
 
102
   This function walks through tree->keys[] and removes the SEL_ARG* trees
 
103
   that are not "maybe" trees (*) and cannot be used to construct quick range
 
104
   selects.
 
105
   (*) - have type MAYBE or MAYBE_KEY. Perhaps we should remove trees of
 
106
   these types here as well.
 
107
 
 
108
   A SEL_ARG* tree cannot be used to construct quick select if it has
 
109
   tree->part != 0. (e.g. it could represent "keypart2 < const").
 
110
 
 
111
   WHY THIS FUNCTION IS NEEDED
 
112
 
 
113
   Normally we allow construction of optimizer::SEL_TREE objects that have SEL_ARG
 
114
   trees that do not allow quick range select construction. For example for
 
115
   " keypart1=1 AND keypart2=2 " the execution will proceed as follows:
 
116
   tree1= optimizer::SEL_TREE { SEL_ARG{keypart1=1} }
 
117
   tree2= optimizer::SEL_TREE { SEL_ARG{keypart2=2} } -- can't make quick range select
 
118
   from this
 
119
   call tree_and(tree1, tree2) -- this joins SEL_ARGs into a usable SEL_ARG
 
120
   tree.
 
121
 
 
122
   There is an exception though: when we construct index_merge optimizer::SEL_TREE,
 
123
   any SEL_ARG* tree that cannot be used to construct quick range select can
 
124
   be removed, because current range analysis code doesn't provide any way
 
125
   that tree could be later combined with another tree.
 
126
   Consider an example: we should not construct
 
127
   st1 = optimizer::SEL_TREE {
 
128
   merges = SEL_IMERGE {
 
129
   optimizer::SEL_TREE(t.key1part1 = 1),
 
130
   optimizer::SEL_TREE(t.key2part2 = 2)   -- (*)
 
131
   }
 
132
   };
 
133
   because
 
134
   - (*) cannot be used to construct quick range select,
 
135
   - There is no execution path that would cause (*) to be converted to
 
136
   a tree that could be used.
 
137
 
 
138
   The latter is easy to verify: first, notice that the only way to convert
 
139
   (*) into a usable tree is to call tree_and(something, (*)).
 
140
 
 
141
   Second look at what tree_and/tree_or function would do when passed a
 
142
   optimizer::SEL_TREE that has the structure like st1 tree has, and conlcude that
 
143
   tree_and(something, (*)) will not be called.
 
144
 
 
145
   RETURN
 
146
   0  Ok, some suitable trees left
 
147
   1  No tree->keys[] left.
 
148
 */
 
149
bool remove_nonrange_trees(RangeParameter *param, SEL_TREE *tree);
 
150
 
 
151
} /* namespace optimizer */
 
152
 
 
153
} /* namespace drizzled */
 
154
 
 
155
#endif /* DRIZZLED_OPTIMIZER_SEL_TREE_H */