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