drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
sel_tree.cc
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#include <config.h>
21
22#include <drizzled/sql_base.h>
23#include <drizzled/sql_select.h>
24#include <drizzled/memory/sql_alloc.h>
25#include <drizzled/optimizer/range.h>
26#include <drizzled/optimizer/range_param.h>
27#include <drizzled/optimizer/sel_arg.h>
28#include <drizzled/optimizer/sel_tree.h>
29#include <drizzled/optimizer/sel_imerge.h>
30
31using namespace std;
32using namespace drizzled;
33
35static bool eq_tree(optimizer::SEL_ARG* a, optimizer::SEL_ARG *b);
36
37bool optimizer::sel_trees_can_be_ored(const SEL_TREE& tree1, const SEL_TREE& tree2, const RangeParameter& param)
38{
39 key_map common_keys= tree1.keys_map;
40 common_keys&= tree2.keys_map;
41
42 if (common_keys.none())
43 return false;
44
45 /* trees have a common key, check if they refer to same key part */
46 for (uint32_t key_no= 0; key_no < param.keys; key_no++)
47 {
48 if (common_keys.test(key_no) && tree1.keys[key_no]->part == tree2.keys[key_no]->part)
49 return true;
50 }
51 return false;
52}
53
54
55/*
56 Perform OR operation on 2 index_merge lists, storing result in first list.
57
58 NOTES
59 The following conversion is implemented:
60 (a_1 &&...&& a_N)||(b_1 &&...&& b_K) = AND_i,j(a_i || b_j) =>
61 => (a_1||b_1).
62
63 i.e. all conjuncts except the first one are currently dropped.
64 This is done to avoid producing N*K ways to do index_merge.
65
66 If (a_1||b_1) produce a condition that is always true, NULL is returned
67 and index_merge is discarded (while it is actually possible to try
68 harder).
69
70 As a consequence of this, choice of keys to do index_merge read may depend
71 on the order of conditions in WHERE part of the query.
72
73 RETURN
74 0 OK, result is stored in *im1
75 other Error, both passed lists are unusable
76*/
77
78static int imerge_list_or_list(optimizer::RangeParameter *param, List<optimizer::SEL_IMERGE> *im1, List<optimizer::SEL_IMERGE> *im2)
79{
80 optimizer::SEL_IMERGE *imerge= &im1->front();
81 im1->clear();
82 im1->push_back(imerge);
83
84 return imerge->or_sel_imerge_with_checks(*param, im2->front());
85}
86
87
88/*
89 Perform OR operation on index_merge list and key tree.
90
91 RETURN
92 0 OK, result is stored in *im1.
93 other Error
94 */
95
96static int imerge_list_or_tree(optimizer::RangeParameter& param, List<optimizer::SEL_IMERGE>& im1, optimizer::SEL_TREE& tree)
97{
99 while (optimizer::SEL_IMERGE* imerge= it++)
100 {
101 if (imerge->or_sel_tree_with_checks(param, tree))
102 it.remove();
103 }
104 return im1.is_empty();
105}
106
107
109{
110 if (! tree1 || ! tree2)
111 return 0;
112
113 if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
114 return tree2;
115
116 if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
117 return tree1;
118
119 if (tree1->type == SEL_TREE::MAYBE)
120 return tree1; // Can't use this
121
122 if (tree2->type == SEL_TREE::MAYBE)
123 return tree2;
124
125 SEL_TREE *result= NULL;
126 key_map result_keys;
127 result_keys.reset();
128 if (sel_trees_can_be_ored(*tree1, *tree2, *param))
129 {
130 /* Join the trees key per key */
131 SEL_ARG** key1= tree1->keys;
132 SEL_ARG** key2= tree2->keys;
133 SEL_ARG** end= key1+param->keys;
134 for (; key1 != end; key1++, key2++)
135 {
136 *key1= key_or(param, *key1, *key2);
137 if (*key1)
138 {
139 result= tree1; // Added to tree1
140 result_keys.set(key1 - tree1->keys);
141 }
142 }
143 if (result)
144 result->keys_map= result_keys;
145 }
146 else
147 {
148 /* ok, two trees have KEY type but cannot be used without index merge */
149 if (tree1->merges.is_empty() && tree2->merges.is_empty())
150 {
151 if (param->remove_jump_scans && (remove_nonrange_trees(param, tree1) || remove_nonrange_trees(param, tree2)))
152 return new SEL_TREE(SEL_TREE::ALWAYS);
153 /* both trees are "range" trees, produce new index merge structure */
154 result= new SEL_TREE();
155 SEL_IMERGE* merge= new SEL_IMERGE();
156 result->merges.push_back(merge);
157 merge->or_sel_tree(param, tree1);
158 merge->or_sel_tree(param, tree2);
159 result->type= tree1->type;
160 }
161 else if (!tree1->merges.is_empty() && !tree2->merges.is_empty())
162 {
163 result= imerge_list_or_list(param, &tree1->merges, &tree2->merges)
164 ? new SEL_TREE(SEL_TREE::ALWAYS)
165 : tree1;
166 }
167 else
168 {
169 /* one tree is index merge tree and another is range tree */
170 if (tree1->merges.is_empty())
171 std::swap(tree1, tree2);
172
173 if (param->remove_jump_scans && remove_nonrange_trees(param, tree2))
174 return new SEL_TREE(SEL_TREE::ALWAYS);
175 /* add tree2 to tree1->merges, checking if it collapses to ALWAYS */
176 result= imerge_list_or_tree(*param, tree1->merges, *tree2)
177 ? new SEL_TREE(SEL_TREE::ALWAYS)
178 : tree1;
179 }
180 }
181 return result;
182}
183
184
185static optimizer::SEL_ARG *
187{
188 if (! key1)
189 {
190 if (key2)
191 {
192 key2->use_count--;
193 key2->free_tree();
194 }
195 return 0;
196 }
197 if (! key2)
198 {
199 key1->use_count--;
200 key1->free_tree();
201 return 0;
202 }
203 key1->use_count--;
204 key2->use_count--;
205
206 if (key1->part != key2->part)
207 {
208 key1->free_tree();
209 key2->free_tree();
210 return 0; // Can't optimize this
211 }
212
213 // If one of the key is MAYBE_KEY then the found region may be bigger
214 if (key1->type == optimizer::SEL_ARG::MAYBE_KEY)
215 {
216 key2->free_tree();
217 key1->use_count++;
218 return key1;
219 }
220 if (key2->type == optimizer::SEL_ARG::MAYBE_KEY)
221 {
222 key1->free_tree();
223 key2->use_count++;
224 return key2;
225 }
226
227 if (key1->use_count > 0)
228 {
229 if (key2->use_count == 0 || key1->elements > key2->elements)
230 {
231 std::swap(key1,key2);
232 }
233 if (key1->use_count > 0 || !(key1=key1->clone_tree(param)))
234 return 0; // OOM
235 }
236
237 // Add tree at key2 to tree at key1
238 bool key2_shared= key2->use_count != 0;
239 key1->maybe_flag|= key2->maybe_flag;
240
241 for (key2=key2->first(); key2; )
242 {
243 optimizer::SEL_ARG *tmp= key1->find_range(key2); // Find key1.min <= key2.min
244 int cmp;
245
246 if (! tmp)
247 {
248 tmp=key1->first(); // tmp.min > key2.min
249 cmp= -1;
250 }
251 else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
252 { // Found tmp.max < key2.min
253 optimizer::SEL_ARG *next= tmp->next;
254 if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part))
255 {
256 // Join near ranges like tmp.max < 0 and key2.min >= 0
257 optimizer::SEL_ARG *key2_next=key2->next;
258 if (key2_shared)
259 {
260 key2=new optimizer::SEL_ARG(*key2);
261 key2->increment_use_count(key1->use_count+1);
262 key2->next= key2_next; // New copy of key2
263 }
264 key2->copy_min(tmp);
265 if (! (key1=key1->tree_delete(tmp)))
266 { // Only one key in tree
267 key1= key2;
268 key1->make_root();
269 key2= key2_next;
270 break;
271 }
272 }
273 if (! (tmp= next)) // tmp.min > key2.min
274 break; // Copy rest of key2
275 }
276 if (cmp < 0)
277 { // tmp.min > key2.min
278 int tmp_cmp;
279 if ((tmp_cmp= tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max
280 {
281 if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
282 { // ranges are connected
283 tmp->copy_min_to_min(key2);
284 key1->merge_flags(key2);
285 if (tmp->min_flag & NO_MIN_RANGE &&
286 tmp->max_flag & NO_MAX_RANGE)
287 {
288 if (key1->maybe_flag)
289 return new optimizer::SEL_ARG(optimizer::SEL_ARG::MAYBE_KEY);
290 return 0;
291 }
292 key2->increment_use_count(-1); // Free not used tree
293 key2= key2->next;
294 continue;
295 }
296 else
297 {
298 optimizer::SEL_ARG *next= key2->next; // Keys are not overlapping
299 if (key2_shared)
300 {
301 optimizer::SEL_ARG *cpy= new optimizer::SEL_ARG(*key2); // Must make copy
302 if (! cpy)
303 return 0; // OOM
304 key1= key1->insert(cpy);
305 key2->increment_use_count(key1->use_count+1);
306 }
307 else
308 key1= key1->insert(key2); // Will destroy key2_root
309 key2= next;
310 continue;
311 }
312 }
313 }
314
315 // tmp.max >= key2.min && tmp.min <= key.cmax(overlapping ranges)
316 if (eq_tree(tmp->next_key_part,key2->next_key_part))
317 {
318 if (tmp->is_same(key2))
319 {
320 tmp->merge_flags(key2); // Copy maybe flags
321 key2->increment_use_count(-1); // Free not used tree
322 }
323 else
324 {
325 optimizer::SEL_ARG *last= tmp;
326 while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
327 eq_tree(last->next->next_key_part,key2->next_key_part))
328 {
329 optimizer::SEL_ARG *save= last;
330 last= last->next;
331 key1= key1->tree_delete(save);
332 }
333 last->copy_min(tmp);
334 if (last->copy_min(key2) || last->copy_max(key2))
335 { // Full range
336 key1->free_tree();
337 for (; key2; key2= key2->next)
338 key2->increment_use_count(-1); // Free not used tree
339 if (key1->maybe_flag)
340 return new optimizer::SEL_ARG(optimizer::SEL_ARG::MAYBE_KEY);
341 return 0;
342 }
343 }
344 key2= key2->next;
345 continue;
346 }
347
348 if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
349 { // tmp.min <= x < key2.min
350 optimizer::SEL_ARG *new_arg= tmp->clone_first(key2);
351 if ((new_arg->next_key_part= key1->next_key_part))
352 new_arg->increment_use_count(key1->use_count+1);
353 tmp->copy_min_to_min(key2);
354 key1= key1->insert(new_arg);
355 }
356
357 // tmp.min >= key2.min && tmp.min <= key2.max
358 optimizer::SEL_ARG key(*key2); // Get copy we can modify
359 for (;;)
360 {
361 if (tmp->cmp_min_to_min(&key) > 0)
362 { // key.min <= x < tmp.min
363 optimizer::SEL_ARG *new_arg= key.clone_first(tmp);
364 if ((new_arg->next_key_part=key.next_key_part))
365 new_arg->increment_use_count(key1->use_count+1);
366 key1= key1->insert(new_arg);
367 }
368 if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
369 { // tmp.min. <= x <= tmp.max
370 tmp->maybe_flag|= key.maybe_flag;
371 key.increment_use_count(key1->use_count+1);
372 tmp->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
373 if (! cmp) // Key2 is ready
374 break;
375 key.copy_max_to_min(tmp);
376 if (! (tmp= tmp->next))
377 {
379 if (! tmp2)
380 return 0; // OOM
381 key1= key1->insert(tmp2);
382 key2= key2->next;
383 goto end;
384 }
385 if (tmp->cmp_min_to_max(&key) > 0)
386 {
388 if (! tmp2)
389 return 0; // OOM
390 key1= key1->insert(tmp2);
391 break;
392 }
393 }
394 else
395 {
396 optimizer::SEL_ARG *new_arg= tmp->clone_last(&key); // tmp.min <= x <= key.max
397 tmp->copy_max_to_min(&key);
398 tmp->increment_use_count(key1->use_count+1);
399 /* Increment key count as it may be used for next loop */
400 key.increment_use_count(1);
401 new_arg->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
402 key1= key1->insert(new_arg);
403 break;
404 }
405 }
406 key2= key2->next;
407 }
408
409end:
410 while (key2)
411 {
412 optimizer::SEL_ARG *next= key2->next;
413 if (key2_shared)
414 {
415 optimizer::SEL_ARG *tmp= new optimizer::SEL_ARG(*key2); // Must make copy
416 if (! tmp)
417 return 0;
418 key2->increment_use_count(key1->use_count+1);
419 key1= key1->insert(tmp);
420 }
421 else
422 key1= key1->insert(key2); // Will destroy key2_root
423 key2= next;
424 }
425 key1->use_count++;
426 return key1;
427}
428
429
430/*
431 Remove the trees that are not suitable for record retrieval.
432 SYNOPSIS
433 param Range analysis parameter
434 tree Tree to be processed, tree->type is KEY or KEY_SMALLER
435
436 DESCRIPTION
437 This function walks through tree->keys[] and removes the SEL_ARG* trees
438 that are not "maybe" trees (*) and cannot be used to construct quick range
439 selects.
440 (*) - have type MAYBE or MAYBE_KEY. Perhaps we should remove trees of
441 these types here as well.
442
443 A SEL_ARG* tree cannot be used to construct quick select if it has
444 tree->part != 0. (e.g. it could represent "keypart2 < const").
445
446 WHY THIS FUNCTION IS NEEDED
447
448 Normally we allow construction of optimizer::SEL_TREE objects that have SEL_ARG
449 trees that do not allow quick range select construction. For example for
450 " keypart1=1 AND keypart2=2 " the execution will proceed as follows:
451 tree1= optimizer::SEL_TREE { SEL_ARG{keypart1=1} }
452 tree2= optimizer::SEL_TREE { SEL_ARG{keypart2=2} } -- can't make quick range select
453 from this
454 call tree_and(tree1, tree2) -- this joins SEL_ARGs into a usable SEL_ARG
455 tree.
456
457 There is an exception though: when we construct index_merge optimizer::SEL_TREE,
458 any SEL_ARG* tree that cannot be used to construct quick range select can
459 be removed, because current range analysis code doesn't provide any way
460 that tree could be later combined with another tree.
461 Consider an example: we should not construct
462 st1 = optimizer::SEL_TREE {
463 merges = SEL_IMERGE {
464 optimizer::SEL_TREE(t.key1part1 = 1),
465 optimizer::SEL_TREE(t.key2part2 = 2) -- (*)
466 }
467 };
468 because
469 - (*) cannot be used to construct quick range select,
470 - There is no execution path that would cause (*) to be converted to
471 a tree that could be used.
472
473 The latter is easy to verify: first, notice that the only way to convert
474 (*) into a usable tree is to call tree_and(something, (*)).
475
476 Second look at what tree_and/tree_or function would do when passed a
477 optimizer::SEL_TREE that has the structure like st1 tree has, and conlcude that
478 tree_and(something, (*)) will not be called.
479
480 RETURN
481 0 Ok, some suitable trees left
482 1 No tree->keys[] left.
483*/
484bool optimizer::remove_nonrange_trees(optimizer::RangeParameter *param, optimizer::SEL_TREE *tree)
485{
486 bool res= true;
487 for (uint32_t i= 0; i < param->keys; i++)
488 {
489 if (tree->keys[i])
490 {
491 if (tree->keys[i]->part)
492 {
493 tree->keys[i]= NULL;
494 tree->keys_map.reset(i);
495 }
496 else
497 res= false;
498 }
499 }
500 return res;
501}
502
503
504/* Compare if two trees are equal */
505static bool eq_tree(optimizer::SEL_ARG *a, optimizer::SEL_ARG *b)
506{
507 if (a == b)
508 return true;
509
510 if (! a || ! b || ! a->is_same(b))
511 {
512 return false;
513 }
514
515 if (a->left != &optimizer::null_element && b->left != &optimizer::null_element)
516 {
517 if (! eq_tree(a->left,b->left))
518 return false;
519 }
520 else if (a->left != &optimizer::null_element || b->left != &optimizer::null_element)
521 {
522 return false;
523 }
524
525 if (a->right != &optimizer::null_element && b->right != &optimizer::null_element)
526 {
527 if (! eq_tree(a->right,b->right))
528 return false;
529 }
530 else if (a->right != &optimizer::null_element || b->right != &optimizer::null_element)
531 {
532 return false;
533 }
534
535 if (a->next_key_part != b->next_key_part)
536 { // Sub range
537 if (! a->next_key_part != ! b->next_key_part ||
538 ! eq_tree(a->next_key_part, b->next_key_part))
539 return false;
540 }
541
542 return true;
543}
TODO: Rename this file - func.h is stupid.
STL namespace.