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