Drizzled Public API Documentation

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 
31 using namespace std;
32 using namespace drizzled;
33 
35 static bool eq_tree(optimizer::SEL_ARG* a, optimizer::SEL_ARG *b);
36 
37 bool 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 
78 static 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 
96 static 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 
185 static 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  {
378  optimizer::SEL_ARG *tmp2= new optimizer::SEL_ARG(key);
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  {
387  optimizer::SEL_ARG *tmp2= new optimizer::SEL_ARG(key);
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 
409 end:
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 */
484 bool 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 */
505 static 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 }