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>
32 using namespace drizzled;
37 bool optimizer::sel_trees_can_be_ored(
const SEL_TREE& tree1,
const SEL_TREE& tree2,
const RangeParameter& param)
39 key_map common_keys= tree1.keys_map;
40 common_keys&= tree2.keys_map;
42 if (common_keys.none())
46 for (uint32_t key_no= 0; key_no < param.keys; key_no++)
48 if (common_keys.test(key_no) && tree1.keys[key_no]->part == tree2.keys[key_no]->part)
82 im1->push_back(imerge);
84 return imerge->or_sel_imerge_with_checks(*param, im2->front());
101 if (imerge->or_sel_tree_with_checks(param, tree))
104 return im1.is_empty();
110 if (! tree1 || ! tree2)
113 if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
116 if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
119 if (tree1->type == SEL_TREE::MAYBE)
122 if (tree2->type == SEL_TREE::MAYBE)
125 SEL_TREE *result= NULL;
128 if (sel_trees_can_be_ored(*tree1, *tree2, *param))
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++)
136 *key1= key_or(param, *key1, *key2);
140 result_keys.set(key1 - tree1->keys);
144 result->keys_map= result_keys;
149 if (tree1->merges.is_empty() && tree2->merges.is_empty())
151 if (param->remove_jump_scans && (remove_nonrange_trees(param, tree1) || remove_nonrange_trees(param, tree2)))
152 return new SEL_TREE(SEL_TREE::ALWAYS);
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;
161 else if (!tree1->merges.is_empty() && !tree2->merges.is_empty())
163 result= imerge_list_or_list(param, &tree1->merges, &tree2->merges)
164 ?
new SEL_TREE(SEL_TREE::ALWAYS)
170 if (tree1->merges.is_empty())
171 std::swap(tree1, tree2);
173 if (param->remove_jump_scans && remove_nonrange_trees(param, tree2))
174 return new SEL_TREE(SEL_TREE::ALWAYS);
176 result= imerge_list_or_tree(*param, tree1->merges, *tree2)
177 ?
new SEL_TREE(SEL_TREE::ALWAYS)
206 if (key1->part != key2->part)
214 if (key1->type == optimizer::SEL_ARG::MAYBE_KEY)
220 if (key2->type == optimizer::SEL_ARG::MAYBE_KEY)
227 if (key1->use_count > 0)
229 if (key2->use_count == 0 || key1->elements > key2->elements)
231 std::swap(key1,key2);
233 if (key1->use_count > 0 || !(key1=key1->clone_tree(param)))
238 bool key2_shared= key2->use_count != 0;
239 key1->maybe_flag|= key2->maybe_flag;
241 for (key2=key2->first(); key2; )
251 else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
254 if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part))
261 key2->increment_use_count(key1->use_count+1);
262 key2->next= key2_next;
265 if (! (key1=key1->tree_delete(tmp)))
279 if ((tmp_cmp= tmp->cmp_min_to_max(key2)) > 0)
281 if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
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)
288 if (key1->maybe_flag)
292 key2->increment_use_count(-1);
304 key1= key1->insert(cpy);
305 key2->increment_use_count(key1->use_count+1);
308 key1= key1->insert(key2);
316 if (eq_tree(tmp->next_key_part,key2->next_key_part))
318 if (tmp->is_same(key2))
320 tmp->merge_flags(key2);
321 key2->increment_use_count(-1);
326 while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
327 eq_tree(last->next->next_key_part,key2->next_key_part))
331 key1= key1->tree_delete(save);
334 if (last->copy_min(key2) || last->copy_max(key2))
337 for (; key2; key2= key2->next)
338 key2->increment_use_count(-1);
339 if (key1->maybe_flag)
348 if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
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);
361 if (tmp->cmp_min_to_min(&key) > 0)
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);
368 if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
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);
375 key.copy_max_to_min(tmp);
376 if (! (tmp= tmp->next))
381 key1= key1->insert(tmp2);
385 if (tmp->cmp_min_to_max(&key) > 0)
390 key1= key1->insert(tmp2);
397 tmp->copy_max_to_min(&key);
398 tmp->increment_use_count(key1->use_count+1);
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);
418 key2->increment_use_count(key1->use_count+1);
419 key1= key1->insert(tmp);
422 key1= key1->insert(key2);
487 for (uint32_t i= 0; i < param->keys; i++)
491 if (tree->keys[i]->part)
494 tree->keys_map.reset(i);
510 if (! a || ! b || ! a->is_same(b))
515 if (a->left != &optimizer::null_element && b->left != &optimizer::null_element)
517 if (! eq_tree(a->left,b->left))
520 else if (a->left != &optimizer::null_element || b->left != &optimizer::null_element)
525 if (a->right != &optimizer::null_element && b->right != &optimizer::null_element)
527 if (! eq_tree(a->right,b->right))
530 else if (a->right != &optimizer::null_element || b->right != &optimizer::null_element)
535 if (a->next_key_part != b->next_key_part)
537 if (! a->next_key_part != ! b->next_key_part ||
538 ! eq_tree(a->next_key_part, b->next_key_part))