1237.13.44
by Padraig O'Sullivan
Moved the SEL_TREE and SEL_IMERGE classes out into their own header and implementation files. |
1 |
/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
|
2 |
* vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
|
|
3 |
*
|
|
1999.6.1
by kalebral at gmail
update Copyright strings to a more common format to help with creating the master debian copyright file |
4 |
* Copyright (C) 2008-2009 Sun Microsystems, Inc.
|
1237.13.44
by Padraig O'Sullivan
Moved the SEL_TREE and SEL_IMERGE classes out into their own header and implementation files. |
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 |
||
2234
by Brian Aker
Mass removal of ifdef/endif in favor of pragma once. |
20 |
#pragma once
|
1237.13.44
by Padraig O'Sullivan
Moved the SEL_TREE and SEL_IMERGE classes out into their own header and implementation files. |
21 |
|
2173.2.1
by Monty Taylor
Fixes incorrect usage of include |
22 |
#include <drizzled/memory/sql_alloc.h> |
1237.13.44
by Padraig O'Sullivan
Moved the SEL_TREE and SEL_IMERGE classes out into their own header and implementation files. |
23 |
|
2252.1.25
by Olaf van der Spek
Common fwd |
24 |
namespace drizzled { |
25 |
namespace optimizer { |
|
1237.13.44
by Padraig O'Sullivan
Moved the SEL_TREE and SEL_IMERGE classes out into their own header and implementation files. |
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 |
||
1802.16.16
by Padraig O'Sullivan
Convert struct to class and move it into optimizer namespace. |
69 |
RorScanInfo **ror_scans; /* list of ROR key scans */ |
70 |
RorScanInfo **ror_scans_end; /* last ROR scan */ |
|
1237.13.44
by Padraig O'Sullivan
Moved the SEL_TREE and SEL_IMERGE classes out into their own header and implementation files. |
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 |
*/
|
|
2318.6.47
by Olaf van der Spek
Refactor |
80 |
bool sel_trees_can_be_ored(const SEL_TREE&, const SEL_TREE&, const RangeParameter&); |
1237.13.44
by Padraig O'Sullivan
Moved the SEL_TREE and SEL_IMERGE classes out into their own header and implementation files. |
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 |