Drizzle

Merge lp:~posulliv/drizzle/optimizer-style-cleanup into lp:~drizzle-trunk/drizzle/development

  1. optimizer-style-cleanup
  2. Merge into development
Proposed by Padraig O'Sullivan
Status: Merged
Merged at revision: not available
Proposed branch: lp:~posulliv/drizzle/optimizer-style-cleanup
Merge into: lp:~drizzle-trunk/drizzle/development
Diff against target: 2727 lines (+1105/-960)
7 files modified
drizzled/include.am (+4/-0)
drizzled/optimizer/range.cc (+116/-958)
drizzled/optimizer/sel_imerge.cc (+98/-0)
drizzled/optimizer/sel_imerge.h (+122/-0)
drizzled/optimizer/sel_tree.cc (+600/-0)
drizzled/optimizer/sel_tree.h (+155/-0)
drizzled/optimizer/table_read_plan.h (+10/-2)
To merge this branch: bzr merge lp:~posulliv/drizzle/optimizer-style-cleanup
Reviewer Review Type Date Requested Status
Drizzle Developers Pending
Review via email: mp+21420@code.launchpad.net

Description of the change

Continues the work of cleaning up some of the optimizer code. Moved some classes into their own header and implementation files. Cleaned up some style issues also.

-Padraig

To post a comment you must log in.

Preview Diff

[H/L] Next/Prev Comment, [J/K] Next/Prev File, [N/P] Next/Prev Hunk
1=== modified file 'drizzled/include.am'
2--- drizzled/include.am 2010-03-05 03:12:24 +0000
3+++ drizzled/include.am 2010-03-16 01:44:16 +0000
4@@ -283,6 +283,8 @@
5 drizzled/optimizer/range_param.h \
6 drizzled/optimizer/sargable_param.h \
7 drizzled/optimizer/sel_arg.h \
8+ drizzled/optimizer/sel_imerge.h \
9+ drizzled/optimizer/sel_tree.h \
10 drizzled/optimizer/sum.h \
11 drizzled/optimizer/table_read_plan.h \
12 drizzled/order.h \
13@@ -647,6 +649,8 @@
14 drizzled/optimizer/quick_ror_union_select.cc \
15 drizzled/optimizer/range.cc \
16 drizzled/optimizer/sel_arg.cc \
17+ drizzled/optimizer/sel_imerge.cc \
18+ drizzled/optimizer/sel_tree.cc \
19 drizzled/optimizer/sum.cc \
20 drizzled/plugin/authentication.cc \
21 drizzled/plugin/authorization.cc \
22
23=== modified file 'drizzled/optimizer/range.cc'
24--- drizzled/optimizer/range.cc 2010-02-10 20:00:52 +0000
25+++ drizzled/optimizer/range.cc 2010-03-16 01:44:16 +0000
26@@ -37,19 +37,12 @@
27 The entry point for the range analysis module is get_mm_tree() function.
28
29 The lists are returned in form of complicated structure of interlinked
30- SEL_TREE/SEL_IMERGE/SEL_ARG objects.
31+ optimizer::SEL_TREE/optimizer::SEL_IMERGE/SEL_ARG objects.
32 See quick_range_seq_next, find_used_partitions for examples of how to walk
33 this structure.
34 All direct "users" of this module are located within this cursor, too.
35
36
37- PartitionPruningModule
38- A module that accepts a partitioned table, condition, and finds which
39- partitions we will need to use in query execution. Search down for
40- "PartitionPruningModule" for description.
41- The module has single entry point - prune_partitions() function.
42-
43-
44 Range/index_merge/groupby-minmax optimizer module
45 A module that accepts a table, condition, and returns
46 - a QUICK_*_SELECT object that can be used to retrieve rows that match
47@@ -133,6 +126,8 @@
48 #include "drizzled/optimizer/quick_ror_union_select.h"
49 #include "drizzled/optimizer/table_read_plan.h"
50 #include "drizzled/optimizer/sel_arg.h"
51+#include "drizzled/optimizer/sel_imerge.h"
52+#include "drizzled/optimizer/sel_tree.h"
53 #include "drizzled/optimizer/range_param.h"
54 #include "drizzled/records.h"
55 #include "drizzled/internal/my_sys.h"
56@@ -235,59 +230,9 @@
57 }
58 }
59
60-class SEL_IMERGE;
61-
62-
63-class SEL_TREE :public memory::SqlAlloc
64-{
65-public:
66- /*
67- Starting an effort to document this field:
68- (for some i, keys[i]->type == optimizer::SEL_ARG::IMPOSSIBLE) =>
69- (type == SEL_TREE::IMPOSSIBLE)
70- */
71- enum Type
72- {
73- IMPOSSIBLE,
74- ALWAYS,
75- MAYBE,
76- KEY,
77- KEY_SMALLER
78- } type;
79-
80- SEL_TREE(enum Type type_arg) :type(type_arg) {}
81- SEL_TREE() :type(KEY)
82- {
83- keys_map.reset();
84- memset(keys, 0, sizeof(keys));
85- }
86- /*
87- Note: there may exist SEL_TREE objects with sel_tree->type=KEY and
88- keys[i]=0 for all i. (SergeyP: it is not clear whether there is any
89- merit in range analyzer functions (e.g. get_mm_parts) returning a
90- pointer to such SEL_TREE instead of NULL)
91- */
92- optimizer::SEL_ARG *keys[MAX_KEY];
93- key_map keys_map; /* bitmask of non-NULL elements in keys */
94-
95- /*
96- Possible ways to read rows using index_merge. The list is non-empty only
97- if type==KEY. Currently can be non empty only if keys_map.none().
98- */
99- List<SEL_IMERGE> merges;
100-
101- /* The members below are filled/used only after get_mm_tree is done */
102- key_map ror_scans_map; /* bitmask of ROR scan-able elements in keys */
103- uint32_t n_ror_scans; /* number of set bits in ror_scans_map */
104-
105- struct st_ror_scan_info **ror_scans; /* list of ROR key scans */
106- struct st_ror_scan_info **ror_scans_end; /* last ROR scan */
107- /* Note that #records for each key scan is stored in table->quick_rows */
108-};
109-
110 struct st_ror_scan_info;
111
112-static SEL_TREE * get_mm_parts(optimizer::RangeParameter *param,
113+static optimizer::SEL_TREE * get_mm_parts(optimizer::RangeParameter *param,
114 COND *cond_func,
115 Field *field,
116 Item_func::Functype type,
117@@ -301,7 +246,7 @@
118 Item_func::Functype type,
119 Item *value);
120
121-static SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond);
122+static optimizer::SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond);
123
124 static bool is_key_scan_ror(optimizer::Parameter *param, uint32_t keynr, uint8_t nparts);
125
126@@ -315,51 +260,36 @@
127 COST_VECT *cost);
128
129 static optimizer::RangeReadPlan *get_key_scans_params(optimizer::Parameter *param,
130- SEL_TREE *tree,
131+ optimizer::SEL_TREE *tree,
132 bool index_read_must_be_used,
133 bool update_tbl_stats,
134 double read_time);
135
136 static
137 optimizer::RorIntersectReadPlan *get_best_ror_intersect(const optimizer::Parameter *param,
138- SEL_TREE *tree,
139+ optimizer::SEL_TREE *tree,
140 double read_time,
141 bool *are_all_covering);
142
143 static
144 optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
145- SEL_TREE *tree,
146+ optimizer::SEL_TREE *tree,
147 double read_time);
148
149 static
150 optimizer::TableReadPlan *get_best_disjunct_quick(optimizer::Parameter *param,
151- SEL_IMERGE *imerge,
152+ optimizer::SEL_IMERGE *imerge,
153 double read_time);
154
155 static
156-optimizer::GroupMinMaxReadPlan *get_best_group_min_max(optimizer::Parameter *param, SEL_TREE *tree);
157-
158-static void print_sel_tree(optimizer::Parameter *param,
159- SEL_TREE *tree,
160- key_map *tree_map,
161- const char *msg);
162-
163-static void print_ror_scans_arr(Table *table,
164- const char *msg,
165- struct st_ror_scan_info **start,
166- struct st_ror_scan_info **end);
167-static void print_ror_scans_vector(Table *table,
168- const char *msg,
169- vector<struct st_ror_scan_info *> &vec);
170-
171-static SEL_TREE *tree_and(optimizer::RangeParameter *param, SEL_TREE *tree1, SEL_TREE *tree2);
172-
173-static SEL_TREE *tree_or(optimizer::RangeParameter *param, SEL_TREE *tree1, SEL_TREE *tree2);
174+optimizer::GroupMinMaxReadPlan *get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree);
175+
176+static optimizer::SEL_TREE *tree_and(optimizer::RangeParameter *param,
177+ optimizer::SEL_TREE *tree1,
178+ optimizer::SEL_TREE *tree2);
179
180 static optimizer::SEL_ARG *sel_add(optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);
181
182-static optimizer::SEL_ARG *key_or(optimizer::RangeParameter *param, optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);
183-
184 static optimizer::SEL_ARG *key_and(optimizer::RangeParameter *param,
185 optimizer::SEL_ARG *key1,
186 optimizer::SEL_ARG *key2,
187@@ -367,228 +297,31 @@
188
189 static bool get_range(optimizer::SEL_ARG **e1, optimizer::SEL_ARG **e2, optimizer::SEL_ARG *root1);
190
191-static bool eq_tree(optimizer::SEL_ARG* a, optimizer::SEL_ARG *b);
192-
193 optimizer::SEL_ARG optimizer::null_element(optimizer::SEL_ARG::IMPOSSIBLE);
194
195 static bool null_part_in_key(KEY_PART *key_part,
196 const unsigned char *key,
197 uint32_t length);
198
199-bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, optimizer::RangeParameter *param);
200-
201-
202-/*
203- SEL_IMERGE is a list of possible ways to do index merge, i.e. it is
204- a condition in the following form:
205- (t_1||t_2||...||t_N) && (next)
206-
207- where all t_i are SEL_TREEs, next is another SEL_IMERGE and no pair
208- (t_i,t_j) contains SEL_ARGS for the same index.
209-
210- SEL_TREE contained in SEL_IMERGE always has merges=NULL.
211-
212- This class relies on memory manager to do the cleanup.
213-*/
214-
215-class SEL_IMERGE : public memory::SqlAlloc
216-{
217- enum { PREALLOCED_TREES= 10};
218-public:
219- SEL_TREE *trees_prealloced[PREALLOCED_TREES];
220- SEL_TREE **trees; /* trees used to do index_merge */
221- SEL_TREE **trees_next; /* last of these trees */
222- SEL_TREE **trees_end; /* end of allocated space */
223-
224- optimizer::SEL_ARG ***best_keys; /* best keys to read in SEL_TREEs */
225-
226- SEL_IMERGE() :
227- trees(&trees_prealloced[0]),
228- trees_next(trees),
229- trees_end(trees + PREALLOCED_TREES)
230- {}
231- int or_sel_tree(optimizer::RangeParameter *param, SEL_TREE *tree);
232- int or_sel_tree_with_checks(optimizer::RangeParameter *param, SEL_TREE *new_tree);
233- int or_sel_imerge_with_checks(optimizer::RangeParameter *param, SEL_IMERGE* imerge);
234-};
235-
236-
237-/*
238- Add SEL_TREE to this index_merge without any checks,
239-
240- NOTES
241- This function implements the following:
242- (x_1||...||x_N) || t = (x_1||...||x_N||t), where x_i, t are SEL_TREEs
243-
244- RETURN
245- 0 - OK
246- -1 - Out of memory.
247-*/
248-int SEL_IMERGE::or_sel_tree(optimizer::RangeParameter *param, SEL_TREE *tree)
249-{
250- if (trees_next == trees_end)
251- {
252- const int realloc_ratio= 2; /* Double size for next round */
253- uint32_t old_elements= (trees_end - trees);
254- uint32_t old_size= sizeof(SEL_TREE**) * old_elements;
255- uint32_t new_size= old_size * realloc_ratio;
256- SEL_TREE **new_trees;
257- if (!(new_trees= (SEL_TREE**)alloc_root(param->mem_root, new_size)))
258- return -1;
259- memcpy(new_trees, trees, old_size);
260- trees= new_trees;
261- trees_next= trees + old_elements;
262- trees_end= trees + old_elements * realloc_ratio;
263- }
264- *(trees_next++)= tree;
265- return 0;
266-}
267-
268-
269-/*
270- Perform OR operation on this SEL_IMERGE and supplied SEL_TREE new_tree,
271- combining new_tree with one of the trees in this SEL_IMERGE if they both
272- have SEL_ARGs for the same key.
273-
274- SYNOPSIS
275- or_sel_tree_with_checks()
276- param Parameter from SqlSelect::test_quick_select
277- new_tree SEL_TREE with type KEY or KEY_SMALLER.
278-
279- NOTES
280- This does the following:
281- (t_1||...||t_k)||new_tree =
282- either
283- = (t_1||...||t_k||new_tree)
284- or
285- = (t_1||....||(t_j|| new_tree)||...||t_k),
286-
287- where t_i, y are SEL_TREEs.
288- new_tree is combined with the first t_j it has a SEL_ARG on common
289- key with. As a consequence of this, choice of keys to do index_merge
290- read may depend on the order of conditions in WHERE part of the query.
291-
292- RETURN
293- 0 OK
294- 1 One of the trees was combined with new_tree to SEL_TREE::ALWAYS,
295- and (*this) should be discarded.
296- -1 An error occurred.
297-*/
298-int SEL_IMERGE::or_sel_tree_with_checks(optimizer::RangeParameter *param, SEL_TREE *new_tree)
299-{
300- for (SEL_TREE** tree = trees;
301- tree != trees_next;
302- tree++)
303- {
304- if (sel_trees_can_be_ored(*tree, new_tree, param))
305- {
306- *tree = tree_or(param, *tree, new_tree);
307- if (!*tree)
308- return 1;
309- if (((*tree)->type == SEL_TREE::MAYBE) ||
310- ((*tree)->type == SEL_TREE::ALWAYS))
311- return 1;
312- /* SEL_TREE::IMPOSSIBLE is impossible here */
313- return 0;
314- }
315- }
316-
317- /* New tree cannot be combined with any of existing trees. */
318- return or_sel_tree(param, new_tree);
319-}
320-
321-
322-/*
323- Perform OR operation on this index_merge and supplied index_merge list.
324-
325- RETURN
326- 0 - OK
327- 1 - One of conditions in result is always true and this SEL_IMERGE
328- should be discarded.
329- -1 - An error occurred
330-*/
331-
332-int SEL_IMERGE::or_sel_imerge_with_checks(optimizer::RangeParameter *param, SEL_IMERGE* imerge)
333-{
334- for (SEL_TREE** tree= imerge->trees;
335- tree != imerge->trees_next;
336- tree++)
337- {
338- if (or_sel_tree_with_checks(param, *tree))
339- return 1;
340- }
341- return 0;
342-}
343+bool sel_trees_can_be_ored(optimizer::SEL_TREE *tree1,
344+ optimizer::SEL_TREE *tree2,
345+ optimizer::RangeParameter *param);
346+
347+
348+
349+
350
351
352 /*
353 Perform AND operation on two index_merge lists and store result in *im1.
354 */
355
356-inline void imerge_list_and_list(List<SEL_IMERGE> *im1, List<SEL_IMERGE> *im2)
357+inline void imerge_list_and_list(List<optimizer::SEL_IMERGE> *im1, List<optimizer::SEL_IMERGE> *im2)
358 {
359 im1->concat(im2);
360 }
361
362
363-/*
364- Perform OR operation on 2 index_merge lists, storing result in first list.
365-
366- NOTES
367- The following conversion is implemented:
368- (a_1 &&...&& a_N)||(b_1 &&...&& b_K) = AND_i,j(a_i || b_j) =>
369- => (a_1||b_1).
370-
371- i.e. all conjuncts except the first one are currently dropped.
372- This is done to avoid producing N*K ways to do index_merge.
373-
374- If (a_1||b_1) produce a condition that is always true, NULL is returned
375- and index_merge is discarded (while it is actually possible to try
376- harder).
377-
378- As a consequence of this, choice of keys to do index_merge read may depend
379- on the order of conditions in WHERE part of the query.
380-
381- RETURN
382- 0 OK, result is stored in *im1
383- other Error, both passed lists are unusable
384-*/
385-
386-static int imerge_list_or_list(optimizer::RangeParameter *param,
387- List<SEL_IMERGE> *im1,
388- List<SEL_IMERGE> *im2)
389-{
390- SEL_IMERGE *imerge= im1->head();
391- im1->empty();
392- im1->push_back(imerge);
393-
394- return imerge->or_sel_imerge_with_checks(param, im2->head());
395-}
396-
397-
398-/*
399- Perform OR operation on index_merge list and key tree.
400-
401- RETURN
402- 0 OK, result is stored in *im1.
403- other Error
404- */
405-
406-static int imerge_list_or_tree(optimizer::RangeParameter *param,
407- List<SEL_IMERGE> *im1,
408- SEL_TREE *tree)
409-{
410- SEL_IMERGE *imerge;
411- List_iterator<SEL_IMERGE> it(*im1);
412- while ((imerge= it++))
413- {
414- if (imerge->or_sel_tree_with_checks(param, tree))
415- it.remove();
416- }
417- return im1->is_empty();
418-}
419-
420-
421 /***************************************************************************
422 ** Basic functions for SqlSelect and QuickRangeSelect
423 ***************************************************************************/
424@@ -928,7 +661,7 @@
425 if (keys_to_use.any())
426 {
427 memory::Root alloc;
428- SEL_TREE *tree= NULL;
429+ optimizer::SEL_TREE *tree= NULL;
430 KEY_PART *key_parts;
431 KEY *key_info;
432 optimizer::Parameter param;
433@@ -1016,7 +749,7 @@
434 {
435 if ((tree= get_mm_tree(&param,cond)))
436 {
437- if (tree->type == SEL_TREE::IMPOSSIBLE)
438+ if (tree->type == optimizer::SEL_TREE::IMPOSSIBLE)
439 {
440 records=0L; /* Return -1 from this function. */
441 read_time= (double) HA_POS_ERROR;
442@@ -1026,7 +759,7 @@
443 If the tree can't be used for range scans, proceed anyway, as we
444 can construct a group-min-max quick select
445 */
446- if (tree->type != SEL_TREE::KEY && tree->type != SEL_TREE::KEY_SMALLER)
447+ if (tree->type != optimizer::SEL_TREE::KEY && tree->type != optimizer::SEL_TREE::KEY_SMALLER)
448 tree= NULL;
449 }
450 }
451@@ -1097,10 +830,10 @@
452 else
453 {
454 /* Try creating index_merge/ROR-union scan. */
455- SEL_IMERGE *imerge= NULL;
456+ optimizer::SEL_IMERGE *imerge= NULL;
457 optimizer::TableReadPlan *best_conj_trp= NULL;
458 optimizer::TableReadPlan *new_conj_trp= NULL;
459- List_iterator_fast<SEL_IMERGE> it(tree->merges);
460+ List_iterator_fast<optimizer::SEL_IMERGE> it(tree->merges);
461 while ((imerge= it++))
462 {
463 new_conj_trp= get_best_disjunct_quick(&param, imerge, best_read_time);
464@@ -1143,7 +876,7 @@
465 }
466
467 /*
468- Get best plan for a SEL_IMERGE disjunctive expression.
469+ Get best plan for a optimizer::SEL_IMERGE disjunctive expression.
470 SYNOPSIS
471 get_best_disjunct_quick()
472 param Parameter from check_quick_select function
473@@ -1209,10 +942,10 @@
474
475 static
476 optimizer::TableReadPlan *get_best_disjunct_quick(optimizer::Parameter *param,
477- SEL_IMERGE *imerge,
478+ optimizer::SEL_IMERGE *imerge,
479 double read_time)
480 {
481- SEL_TREE **ptree;
482+ optimizer::SEL_TREE **ptree= NULL;
483 optimizer::IndexMergeReadPlan *imerge_trp= NULL;
484 uint32_t n_child_scans= imerge->trees_next - imerge->trees;
485 optimizer::RangeReadPlan **range_scans= NULL;
486@@ -1245,7 +978,6 @@
487 ptree != imerge->trees_next;
488 ptree++, cur_child++)
489 {
490- print_sel_tree(param, *ptree, &(*ptree)->keys_map, "tree in SEL_IMERGE");
491 if (!(*cur_child= get_key_scans_params(param, *ptree, true, false, read_time)))
492 {
493 /*
494@@ -1960,28 +1692,28 @@
495
496 static
497 optimizer::RorIntersectReadPlan *get_best_ror_intersect(const optimizer::Parameter *param,
498- SEL_TREE *tree,
499+ optimizer::SEL_TREE *tree,
500 double read_time,
501 bool *are_all_covering)
502 {
503- uint32_t idx;
504+ uint32_t idx= 0;
505 double min_cost= DBL_MAX;
506
507- if ((tree->n_ror_scans < 2) || !param->table->cursor->stats.records)
508+ if ((tree->n_ror_scans < 2) || ! param->table->cursor->stats.records)
509 return NULL;
510
511 /*
512 Step1: Collect ROR-able SEL_ARGs and create ROR_SCAN_INFO for each of
513 them. Also find and save clustered PK scan if there is one.
514 */
515- ROR_SCAN_INFO **cur_ror_scan;
516+ ROR_SCAN_INFO **cur_ror_scan= NULL;
517 ROR_SCAN_INFO *cpk_scan= NULL;
518- uint32_t cpk_no;
519+ uint32_t cpk_no= 0;
520 bool cpk_scan_used= false;
521
522- if (!(tree->ror_scans= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
523- sizeof(ROR_SCAN_INFO*)*
524- param->keys)))
525+ if (! (tree->ror_scans= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
526+ sizeof(ROR_SCAN_INFO*)*
527+ param->keys)))
528 return NULL;
529 cpk_no= ((param->table->cursor->primary_key_is_clustered()) ?
530 param->table->s->primary_key : MAX_KEY);
531@@ -2003,9 +1735,6 @@
532 }
533
534 tree->ror_scans_end= cur_ror_scan;
535- print_ror_scans_arr(param->table, "original",
536- tree->ror_scans,
537- tree->ror_scans_end);
538 /*
539 Ok, [ror_scans, ror_scans_end) is array of ptrs to initialized
540 ROR_SCAN_INFO's.
541@@ -2013,26 +1742,24 @@
542 */
543 internal::my_qsort(tree->ror_scans, tree->n_ror_scans, sizeof(ROR_SCAN_INFO*),
544 (qsort_cmp)cmp_ror_scan_info);
545- print_ror_scans_arr(param->table, "ordered",
546- tree->ror_scans,
547- tree->ror_scans_end);
548
549- ROR_SCAN_INFO **intersect_scans; /* ROR scans used in index intersection */
550- ROR_SCAN_INFO **intersect_scans_end;
551- if (!(intersect_scans= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
552- sizeof(ROR_SCAN_INFO*)*
553- tree->n_ror_scans)))
554+ ROR_SCAN_INFO **intersect_scans= NULL; /* ROR scans used in index intersection */
555+ ROR_SCAN_INFO **intersect_scans_end= NULL;
556+ if (! (intersect_scans= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
557+ sizeof(ROR_SCAN_INFO*)*
558+ tree->n_ror_scans)))
559 return NULL;
560 intersect_scans_end= intersect_scans;
561
562 /* Create and incrementally update ROR intersection. */
563- ROR_INTERSECT_INFO *intersect, *intersect_best;
564- if (!(intersect= ror_intersect_init(param)) ||
565- !(intersect_best= ror_intersect_init(param)))
566+ ROR_INTERSECT_INFO *intersect= NULL;
567+ ROR_INTERSECT_INFO *intersect_best= NULL;
568+ if (! (intersect= ror_intersect_init(param)) ||
569+ ! (intersect_best= ror_intersect_init(param)))
570 return NULL;
571
572 /* [intersect_scans,intersect_scans_best) will hold the best intersection */
573- ROR_SCAN_INFO **intersect_scans_best;
574+ ROR_SCAN_INFO **intersect_scans_best= NULL;
575 cur_ror_scan= tree->ror_scans;
576 intersect_scans_best= intersect_scans;
577 while (cur_ror_scan != tree->ror_scans_end && !intersect->is_covering)
578@@ -2060,11 +1787,6 @@
579 return NULL;
580 }
581
582- print_ror_scans_arr(param->table,
583- "best ROR-intersection",
584- intersect_scans,
585- intersect_scans_best);
586-
587 *are_all_covering= intersect->is_covering;
588 uint32_t best_num= intersect_scans_best - intersect_scans;
589 ror_intersect_cpy(intersect, intersect_best);
590@@ -2096,14 +1818,14 @@
591 trp->read_cost= intersect_best->total_cost;
592 /* Prevent divisons by zero */
593 ha_rows best_rows = double2rows(intersect_best->out_rows);
594- if (!best_rows)
595+ if (! best_rows)
596 best_rows= 1;
597 set_if_smaller(param->table->quick_condition_rows, best_rows);
598 trp->records= best_rows;
599 trp->setCostOfIndexScans(intersect_best->index_scan_costs);
600 trp->cpk_scan= cpk_scan_used? cpk_scan: NULL;
601 }
602- return(trp);
603+ return trp;
604 }
605
606
607@@ -2112,7 +1834,7 @@
608 SYNOPSIS
609 get_best_covering_ror_intersect()
610 param Parameter from test_quick_select function.
611- tree SEL_TREE with sets of intervals for different keys.
612+ tree optimizer::SEL_TREE with sets of intervals for different keys.
613 read_time Don't return table read plans with cost > read_time.
614
615 RETURN
616@@ -2142,7 +1864,7 @@
617
618 static
619 optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
620- SEL_TREE *tree,
621+ optimizer::SEL_TREE *tree,
622 double read_time)
623 {
624 ROR_SCAN_INFO **ror_scan_mark;
625@@ -2177,9 +1899,6 @@
626 ha_rows records=0;
627 bool all_covered;
628
629- print_ror_scans_arr(param->table,
630- "building covering ROR-I",
631- ror_scan_mark, ror_scans_end);
632 do
633 {
634 /*
635@@ -2201,10 +1920,6 @@
636 sizeof(ROR_SCAN_INFO*),
637 (qsort_cmp)cmp_ror_scan_info_covering);
638
639- print_ror_scans_arr(param->table,
640- "remaining scans",
641- ror_scan_mark, ror_scans_end);
642-
643 /* I=I-first(I) */
644 total_cost += (*ror_scan_mark)->index_read_cost;
645 records += (*ror_scan_mark)->records;
646@@ -2222,10 +1937,6 @@
647 Ok, [tree->ror_scans .. ror_scan) holds covering index_intersection with
648 cost total_cost.
649 */
650- print_ror_scans_arr(param->table,
651- "creating covering ROR-intersect",
652- tree->ror_scans, ror_scan_mark);
653-
654 /* Add priority queue use cost. */
655 total_cost += rows2double(records)*
656 log((double)(ror_scan_mark - tree->ror_scans)) /
657@@ -2253,12 +1964,12 @@
658
659
660 /*
661- Get best "range" table read plan for given SEL_TREE, also update some info
662+ Get best "range" table read plan for given optimizer::SEL_TREE, also update some info
663
664 SYNOPSIS
665 get_key_scans_params()
666 param Parameters from test_quick_select
667- tree Make range select for this SEL_TREE
668+ tree Make range select for this optimizer::SEL_TREE
669 index_read_must_be_used true <=> assume 'index only' option will be set
670 (except for clustered PK indexes)
671 update_tbl_stats true <=> update table->quick_* with information
672@@ -2267,7 +1978,7 @@
673 cost > read_time.
674
675 DESCRIPTION
676- Find the best "range" table read plan for given SEL_TREE.
677+ Find the best "range" table read plan for given optimizer::SEL_TREE.
678 The side effects are
679 - tree->ror_scans is updated to indicate which scans are ROR scans.
680 - if update_tbl_stats=true then table->quick_* is updated with info
681@@ -2279,7 +1990,7 @@
682 */
683
684 static optimizer::RangeReadPlan *get_key_scans_params(optimizer::Parameter *param,
685- SEL_TREE *tree,
686+ optimizer::SEL_TREE *tree,
687 bool index_read_must_be_used,
688 bool update_tbl_stats,
689 double read_time)
690@@ -2293,11 +2004,10 @@
691 uint32_t best_buf_size= 0;
692 optimizer::RangeReadPlan *read_plan= NULL;
693 /*
694- Note that there may be trees that have type SEL_TREE::KEY but contain no
695+ Note that there may be trees that have type optimizer::SEL_TREE::KEY but contain no
696 key reads at all, e.g. tree for expression "key1 is not null" where key1
697 is defined as "not null".
698 */
699- print_sel_tree(param, tree, &tree->keys_map, "tree scans");
700 tree->ror_scans_map.reset();
701 tree->n_ror_scans= 0;
702 for (idx= 0,key=tree->keys, end=key+param->keys; key != end; key++,idx++)
703@@ -2336,7 +2046,6 @@
704 }
705 }
706
707- print_sel_tree(param, tree, &tree->ror_scans_map, "ROR scans");
708 if (key_to_read)
709 {
710 idx= key_to_read - tree->keys;
711@@ -2396,9 +2105,6 @@
712 (retrieve_full_rows? (! is_covering) : false),
713 parent_alloc)))
714 {
715- print_ror_scans_vector(param->table,
716- "creating ROR-intersect",
717- ror_range_scans);
718 alloc= parent_alloc ? parent_alloc : &quick_intersect->alloc;
719 for (vector<struct st_ror_scan_info *>::iterator it= ror_range_scans.begin();
720 it != ror_range_scans.end();
721@@ -2466,7 +2172,7 @@
722
723
724 /*
725- Build a SEL_TREE for <> or NOT BETWEEN predicate
726+ Build a optimizer::SEL_TREE for <> or NOT BETWEEN predicate
727
728 SYNOPSIS
729 get_ne_mm_tree()
730@@ -2481,13 +2187,13 @@
731 # Pointer to tree built tree
732 0 on error
733 */
734-static SEL_TREE *get_ne_mm_tree(optimizer::RangeParameter *param,
735+static optimizer::SEL_TREE *get_ne_mm_tree(optimizer::RangeParameter *param,
736 Item_func *cond_func,
737 Field *field,
738 Item *lt_value, Item *gt_value,
739 Item_result cmp_type)
740 {
741- SEL_TREE *tree;
742+ optimizer::SEL_TREE *tree= NULL;
743 tree= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
744 lt_value, cmp_type);
745 if (tree)
746@@ -2504,7 +2210,7 @@
747
748
749 /*
750- Build a SEL_TREE for a simple predicate
751+ Build a optimizer::SEL_TREE for a simple predicate
752
753 SYNOPSIS
754 get_func_mm_tree()
755@@ -2519,14 +2225,14 @@
756 RETURN
757 Pointer to the tree built tree
758 */
759-static SEL_TREE *get_func_mm_tree(optimizer::RangeParameter *param,
760+static optimizer::SEL_TREE *get_func_mm_tree(optimizer::RangeParameter *param,
761 Item_func *cond_func,
762 Field *field,
763 Item *value,
764 Item_result cmp_type,
765 bool inv)
766 {
767- SEL_TREE *tree= NULL;
768+ optimizer::SEL_TREE *tree= NULL;
769
770 switch (cond_func->functype())
771 {
772@@ -2598,7 +2304,7 @@
773 {
774 /*
775 We get here for conditions in form "t.key NOT IN (c1, c2, ...)",
776- where c{i} are constants. Our goal is to produce a SEL_TREE that
777+ where c{i} are constants. Our goal is to produce a optimizer::SEL_TREE that
778 represents intervals:
779
780 ($MIN<t.key<c1) OR (c1<t.key<c2) OR (c2<t.key<c3) OR ... (*)
781@@ -2607,7 +2313,7 @@
782
783 The most straightforward way to produce it is to convert NOT IN
784 into "(t.key != c1) AND (t.key != c2) AND ... " and let the range
785- analyzer to build SEL_TREE from that. The problem is that the
786+ analyzer to build optimizer::SEL_TREE from that. The problem is that the
787 range analyzer will use O(N^2) memory (which is probably a bug),
788 and people do use big NOT IN lists (e.g. see BUG#15872, BUG#21282),
789 will run out of memory.
790@@ -2620,8 +2326,8 @@
791
792 Considering the above, we'll handle NOT IN as follows:
793 * if the number of entries in the NOT IN list is less than
794- NOT_IN_IGNORE_THRESHOLD, construct the SEL_TREE (*) manually.
795- * Otherwise, don't produce a SEL_TREE.
796+ NOT_IN_IGNORE_THRESHOLD, construct the optimizer::SEL_TREE (*) manually.
797+ * Otherwise, don't produce a optimizer::SEL_TREE.
798 */
799 #define NOT_IN_IGNORE_THRESHOLD 1000
800 memory::Root *tmp_root= param->mem_root;
801@@ -2640,7 +2346,7 @@
802 if (func->array->count > NOT_IN_IGNORE_THRESHOLD || ! value_item)
803 break;
804
805- /* Get a SEL_TREE for "(-inf|NULL) < X < c_0" interval. */
806+ /* Get a optimizer::SEL_TREE for "(-inf|NULL) < X < c_0" interval. */
807 uint32_t i=0;
808 do
809 {
810@@ -2653,20 +2359,20 @@
811 if (! tree)
812 break;
813 i++;
814- } while (i < func->array->count && tree->type == SEL_TREE::IMPOSSIBLE);
815+ } while (i < func->array->count && tree->type == optimizer::SEL_TREE::IMPOSSIBLE);
816
817- if (!tree || tree->type == SEL_TREE::IMPOSSIBLE)
818+ if (!tree || tree->type == optimizer::SEL_TREE::IMPOSSIBLE)
819 {
820 /* We get here in cases like "t.unsigned NOT IN (-1,-2,-3) */
821 tree= NULL;
822 break;
823 }
824- SEL_TREE *tree2;
825+ optimizer::SEL_TREE *tree2= NULL;
826 for (; i < func->array->count; i++)
827 {
828 if (func->array->compare_elems(i, i-1))
829 {
830- /* Get a SEL_TREE for "-inf < X < c_i" interval */
831+ /* Get a optimizer::SEL_TREE for "-inf < X < c_i" interval */
832 func->array->value_to_item(i, value_item);
833 tree2= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
834 value_item, cmp_type);
835@@ -2696,10 +2402,10 @@
836 }
837 }
838
839- if (tree && tree->type != SEL_TREE::IMPOSSIBLE)
840+ if (tree && tree->type != optimizer::SEL_TREE::IMPOSSIBLE)
841 {
842 /*
843- Get the SEL_TREE for the last "c_last < X < +inf" interval
844+ Get the optimizer::SEL_TREE for the last "c_last < X < +inf" interval
845 (value_item cotains c_last already)
846 */
847 tree2= get_mm_parts(param, cond_func, field, Item_func::GT_FUNC,
848@@ -2763,7 +2469,7 @@
849
850
851 /*
852- Build conjunction of all SEL_TREEs for a simple predicate applying equalities
853+ Build conjunction of all optimizer::SEL_TREEs for a simple predicate applying equalities
854
855 SYNOPSIS
856 get_full_func_mm_tree()
857@@ -2778,7 +2484,7 @@
858
859 DESCRIPTION
860 For a simple SARGable predicate of the form (f op c), where f is a field and
861- c is a constant, the function builds a conjunction of all SEL_TREES that can
862+ c is a constant, the function builds a conjunction of all optimizer::SEL_TREES that can
863 be obtained by the substitution of f for all different fields equal to f.
864
865 NOTES
866@@ -2788,9 +2494,9 @@
867 each fj belonging to the same multiple equality as fi
868 are built as well.
869 E.g. for WHERE t1.a=t2.a AND t2.a > 10
870- a SEL_TREE for t2.a > 10 will be built for quick select from t2
871+ a optimizer::SEL_TREE for t2.a > 10 will be built for quick select from t2
872 and
873- a SEL_TREE for t1.a > 10 will be built for quick select from t1.
874+ a optimizer::SEL_TREE for t1.a > 10 will be built for quick select from t1.
875
876 A BETWEEN predicate of the form (fi [NOT] BETWEEN c1 AND c2) is treated
877 in a similar way: we build a conjuction of trees for the results
878@@ -2829,16 +2535,16 @@
879 the form (c IN (c1,...,f,...,cn)).
880
881 RETURN
882- Pointer to the tree representing the built conjunction of SEL_TREEs
883+ Pointer to the tree representing the built conjunction of optimizer::SEL_TREEs
884 */
885
886-static SEL_TREE *get_full_func_mm_tree(optimizer::RangeParameter *param,
887+static optimizer::SEL_TREE *get_full_func_mm_tree(optimizer::RangeParameter *param,
888 Item_func *cond_func,
889 Item_field *field_item, Item *value,
890 bool inv)
891 {
892- SEL_TREE *tree= 0;
893- SEL_TREE *ftree= 0;
894+ optimizer::SEL_TREE *tree= 0;
895+ optimizer::SEL_TREE *ftree= 0;
896 table_map ref_tables= 0;
897 table_map param_comp= ~(param->prev_tables | param->read_tables |
898 param->current_table);
899@@ -2880,10 +2586,10 @@
900
901 /* make a select tree of all keys in condition */
902
903-static SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond)
904+static optimizer::SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond)
905 {
906- SEL_TREE *tree=0;
907- SEL_TREE *ftree= 0;
908+ optimizer::SEL_TREE *tree=0;
909+ optimizer::SEL_TREE *ftree= 0;
910 Item_field *field_item= 0;
911 bool inv= false;
912 Item *value= 0;
913@@ -2898,12 +2604,12 @@
914 Item *item;
915 while ((item=li++))
916 {
917- SEL_TREE *new_tree= get_mm_tree(param,item);
918+ optimizer::SEL_TREE *new_tree= get_mm_tree(param,item);
919 if (param->session->is_fatal_error ||
920 param->alloced_sel_args > optimizer::SEL_ARG::MAX_SEL_ARGS)
921 return 0; // out of memory
922 tree=tree_and(param,tree,new_tree);
923- if (tree && tree->type == SEL_TREE::IMPOSSIBLE)
924+ if (tree && tree->type == optimizer::SEL_TREE::IMPOSSIBLE)
925 break;
926 }
927 }
928@@ -2915,11 +2621,11 @@
929 Item *item;
930 while ((item=li++))
931 {
932- SEL_TREE *new_tree= get_mm_tree(param,item);
933+ optimizer::SEL_TREE *new_tree= get_mm_tree(param,item);
934 if (!new_tree)
935 return 0; // out of memory
936 tree=tree_or(param,tree,new_tree);
937- if (!tree || tree->type == SEL_TREE::ALWAYS)
938+ if (!tree || tree->type == optimizer::SEL_TREE::ALWAYS)
939 break;
940 }
941 }
942@@ -2937,8 +2643,8 @@
943 */
944 memory::Root *tmp_root= param->mem_root;
945 param->session->mem_root= param->old_root;
946- tree= cond->val_int() ? new(tmp_root) SEL_TREE(SEL_TREE::ALWAYS) :
947- new(tmp_root) SEL_TREE(SEL_TREE::IMPOSSIBLE);
948+ tree= cond->val_int() ? new(tmp_root) optimizer::SEL_TREE(optimizer::SEL_TREE::ALWAYS) :
949+ new(tmp_root) optimizer::SEL_TREE(optimizer::SEL_TREE::IMPOSSIBLE);
950 param->session->mem_root= tmp_root;
951 return(tree);
952 }
953@@ -2952,7 +2658,7 @@
954 if ((ref_tables & param->current_table) ||
955 (ref_tables & ~(param->prev_tables | param->read_tables)))
956 return 0;
957- return(new SEL_TREE(SEL_TREE::MAYBE));
958+ return(new optimizer::SEL_TREE(optimizer::SEL_TREE::MAYBE));
959 }
960
961 Item_func *cond_func= (Item_func*) cond;
962@@ -2981,7 +2687,7 @@
963 if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM)
964 {
965 field_item= (Item_field*) (cond_func->arguments()[i]->real_item());
966- SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func,
967+ optimizer::SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func,
968 field_item, (Item*)(intptr_t)i, inv);
969 if (inv)
970 tree= !tree ? tmp : tree_or(param, tree, tmp);
971@@ -3051,7 +2757,7 @@
972 }
973
974
975-static SEL_TREE *
976+static optimizer::SEL_TREE *
977 get_mm_parts(optimizer::RangeParameter *param,
978 COND *cond_func,
979 Field *field,
980@@ -3063,7 +2769,7 @@
981
982 KEY_PART *key_part = param->key_parts;
983 KEY_PART *end = param->key_parts_end;
984- SEL_TREE *tree=0;
985+ optimizer::SEL_TREE *tree=0;
986 if (value &&
987 value->used_tables() & ~(param->prev_tables | param->read_tables))
988 return 0;
989@@ -3072,7 +2778,7 @@
990 if (field->eq(key_part->field))
991 {
992 optimizer::SEL_ARG *sel_arg=0;
993- if (!tree && !(tree=new SEL_TREE()))
994+ if (!tree && !(tree=new optimizer::SEL_TREE()))
995 return 0; // OOM
996 if (!value || !(value->used_tables() & ~param->read_tables))
997 {
998@@ -3082,7 +2788,7 @@
999 continue;
1000 if (sel_arg->type == optimizer::SEL_ARG::IMPOSSIBLE)
1001 {
1002- tree->type=SEL_TREE::IMPOSSIBLE;
1003+ tree->type=optimizer::SEL_TREE::IMPOSSIBLE;
1004 return(tree);
1005 }
1006 }
1007@@ -3569,26 +3275,26 @@
1008 #define swap_clone_flag(A) ((A & 1) << 1) | ((A & 2) >> 1)
1009
1010
1011-static SEL_TREE *
1012-tree_and(optimizer::RangeParameter *param, SEL_TREE *tree1, SEL_TREE *tree2)
1013+static optimizer::SEL_TREE *
1014+tree_and(optimizer::RangeParameter *param, optimizer::SEL_TREE *tree1, optimizer::SEL_TREE *tree2)
1015 {
1016 if (!tree1)
1017 return(tree2);
1018 if (!tree2)
1019 return(tree1);
1020- if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
1021+ if (tree1->type == optimizer::SEL_TREE::IMPOSSIBLE || tree2->type == optimizer::SEL_TREE::ALWAYS)
1022 return(tree1);
1023- if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
1024+ if (tree2->type == optimizer::SEL_TREE::IMPOSSIBLE || tree1->type == optimizer::SEL_TREE::ALWAYS)
1025 return(tree2);
1026- if (tree1->type == SEL_TREE::MAYBE)
1027+ if (tree1->type == optimizer::SEL_TREE::MAYBE)
1028 {
1029- if (tree2->type == SEL_TREE::KEY)
1030- tree2->type=SEL_TREE::KEY_SMALLER;
1031+ if (tree2->type == optimizer::SEL_TREE::KEY)
1032+ tree2->type=optimizer::SEL_TREE::KEY_SMALLER;
1033 return(tree2);
1034 }
1035- if (tree2->type == SEL_TREE::MAYBE)
1036+ if (tree2->type == optimizer::SEL_TREE::MAYBE)
1037 {
1038- tree1->type=SEL_TREE::KEY_SMALLER;
1039+ tree1->type=optimizer::SEL_TREE::KEY_SMALLER;
1040 return(tree1);
1041 }
1042 key_map result_keys;
1043@@ -3609,7 +3315,7 @@
1044 *key1=key_and(param, *key1, *key2, flag);
1045 if (*key1 && (*key1)->type == optimizer::SEL_ARG::IMPOSSIBLE)
1046 {
1047- tree1->type= SEL_TREE::IMPOSSIBLE;
1048+ tree1->type= optimizer::SEL_TREE::IMPOSSIBLE;
1049 return(tree1);
1050 }
1051 result_keys.set(key1 - tree1->keys);
1052@@ -3629,195 +3335,6 @@
1053 }
1054
1055
1056-/*
1057- Check if two SEL_TREES can be combined into one (i.e. a single key range
1058- read can be constructed for "cond_of_tree1 OR cond_of_tree2" ) without
1059- using index_merge.
1060-*/
1061-
1062-bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2,
1063- optimizer::RangeParameter* param)
1064-{
1065- key_map common_keys= tree1->keys_map;
1066- common_keys&= tree2->keys_map;
1067-
1068- if (common_keys.none())
1069- return false;
1070-
1071- /* trees have a common key, check if they refer to same key part */
1072- optimizer::SEL_ARG **key1,**key2;
1073- for (uint32_t key_no=0; key_no < param->keys; key_no++)
1074- {
1075- if (common_keys.test(key_no))
1076- {
1077- key1= tree1->keys + key_no;
1078- key2= tree2->keys + key_no;
1079- if ((*key1)->part == (*key2)->part)
1080- {
1081- return true;
1082- }
1083- }
1084- }
1085- return false;
1086-}
1087-
1088-
1089-/*
1090- Remove the trees that are not suitable for record retrieval.
1091- SYNOPSIS
1092- param Range analysis parameter
1093- tree Tree to be processed, tree->type is KEY or KEY_SMALLER
1094-
1095- DESCRIPTION
1096- This function walks through tree->keys[] and removes the SEL_ARG* trees
1097- that are not "maybe" trees (*) and cannot be used to construct quick range
1098- selects.
1099- (*) - have type MAYBE or MAYBE_KEY. Perhaps we should remove trees of
1100- these types here as well.
1101-
1102- A SEL_ARG* tree cannot be used to construct quick select if it has
1103- tree->part != 0. (e.g. it could represent "keypart2 < const").
1104-
1105- WHY THIS FUNCTION IS NEEDED
1106-
1107- Normally we allow construction of SEL_TREE objects that have SEL_ARG
1108- trees that do not allow quick range select construction. For example for
1109- " keypart1=1 AND keypart2=2 " the execution will proceed as follows:
1110- tree1= SEL_TREE { SEL_ARG{keypart1=1} }
1111- tree2= SEL_TREE { SEL_ARG{keypart2=2} } -- can't make quick range select
1112- from this
1113- call tree_and(tree1, tree2) -- this joins SEL_ARGs into a usable SEL_ARG
1114- tree.
1115-
1116- There is an exception though: when we construct index_merge SEL_TREE,
1117- any SEL_ARG* tree that cannot be used to construct quick range select can
1118- be removed, because current range analysis code doesn't provide any way
1119- that tree could be later combined with another tree.
1120- Consider an example: we should not construct
1121- st1 = SEL_TREE {
1122- merges = SEL_IMERGE {
1123- SEL_TREE(t.key1part1 = 1),
1124- SEL_TREE(t.key2part2 = 2) -- (*)
1125- }
1126- };
1127- because
1128- - (*) cannot be used to construct quick range select,
1129- - There is no execution path that would cause (*) to be converted to
1130- a tree that could be used.
1131-
1132- The latter is easy to verify: first, notice that the only way to convert
1133- (*) into a usable tree is to call tree_and(something, (*)).
1134-
1135- Second look at what tree_and/tree_or function would do when passed a
1136- SEL_TREE that has the structure like st1 tree has, and conlcude that
1137- tree_and(something, (*)) will not be called.
1138-
1139- RETURN
1140- 0 Ok, some suitable trees left
1141- 1 No tree->keys[] left.
1142-*/
1143-
1144-static bool remove_nonrange_trees(optimizer::RangeParameter *param, SEL_TREE *tree)
1145-{
1146- bool res= false;
1147- for (uint32_t i=0; i < param->keys; i++)
1148- {
1149- if (tree->keys[i])
1150- {
1151- if (tree->keys[i]->part)
1152- {
1153- tree->keys[i]= NULL;
1154- tree->keys_map.reset(i);
1155- }
1156- else
1157- res= true;
1158- }
1159- }
1160- return !res;
1161-}
1162-
1163-
1164-static SEL_TREE *
1165-tree_or(optimizer::RangeParameter *param,SEL_TREE *tree1,SEL_TREE *tree2)
1166-{
1167- if (!tree1 || !tree2)
1168- return 0;
1169- if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
1170- return(tree2);
1171- if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
1172- return(tree1);
1173- if (tree1->type == SEL_TREE::MAYBE)
1174- return(tree1); // Can't use this
1175- if (tree2->type == SEL_TREE::MAYBE)
1176- return(tree2);
1177-
1178- SEL_TREE *result= 0;
1179- key_map result_keys;
1180- result_keys.reset();
1181- if (sel_trees_can_be_ored(tree1, tree2, param))
1182- {
1183- /* Join the trees key per key */
1184- optimizer::SEL_ARG **key1,**key2,**end;
1185- for (key1= tree1->keys,key2= tree2->keys,end= key1+param->keys ;
1186- key1 != end ; key1++,key2++)
1187- {
1188- *key1=key_or(param, *key1, *key2);
1189- if (*key1)
1190- {
1191- result=tree1; // Added to tree1
1192- result_keys.set(key1 - tree1->keys);
1193- }
1194- }
1195- if (result)
1196- result->keys_map= result_keys;
1197- }
1198- else
1199- {
1200- /* ok, two trees have KEY type but cannot be used without index merge */
1201- if (tree1->merges.is_empty() && tree2->merges.is_empty())
1202- {
1203- if (param->remove_jump_scans)
1204- {
1205- bool no_trees= remove_nonrange_trees(param, tree1);
1206- no_trees= no_trees || remove_nonrange_trees(param, tree2);
1207- if (no_trees)
1208- return(new SEL_TREE(SEL_TREE::ALWAYS));
1209- }
1210- SEL_IMERGE *merge;
1211- /* both trees are "range" trees, produce new index merge structure */
1212- if (!(result= new SEL_TREE()) || !(merge= new SEL_IMERGE()) ||
1213- (result->merges.push_back(merge)) ||
1214- (merge->or_sel_tree(param, tree1)) ||
1215- (merge->or_sel_tree(param, tree2)))
1216- result= NULL;
1217- else
1218- result->type= tree1->type;
1219- }
1220- else if (!tree1->merges.is_empty() && !tree2->merges.is_empty())
1221- {
1222- if (imerge_list_or_list(param, &tree1->merges, &tree2->merges))
1223- result= new SEL_TREE(SEL_TREE::ALWAYS);
1224- else
1225- result= tree1;
1226- }
1227- else
1228- {
1229- /* one tree is index merge tree and another is range tree */
1230- if (tree1->merges.is_empty())
1231- std::swap(tree1, tree2);
1232-
1233- if (param->remove_jump_scans && remove_nonrange_trees(param, tree2))
1234- return(new SEL_TREE(SEL_TREE::ALWAYS));
1235- /* add tree2 to tree1->merges, checking if it collapses to ALWAYS */
1236- if (imerge_list_or_tree(param, &tree1->merges, tree2))
1237- result= new SEL_TREE(SEL_TREE::ALWAYS);
1238- else
1239- result= tree1;
1240- }
1241- }
1242- return result;
1243-}
1244-
1245
1246 /* And key trees where key1->part < key2 -> part */
1247
1248@@ -4014,302 +3531,6 @@
1249 }
1250
1251
1252-static optimizer::SEL_ARG *
1253-key_or(optimizer::RangeParameter *param, optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2)
1254-{
1255- if (! key1)
1256- {
1257- if (key2)
1258- {
1259- key2->use_count--;
1260- key2->free_tree();
1261- }
1262- return 0;
1263- }
1264- if (! key2)
1265- {
1266- key1->use_count--;
1267- key1->free_tree();
1268- return 0;
1269- }
1270- key1->use_count--;
1271- key2->use_count--;
1272-
1273- if (key1->part != key2->part)
1274- {
1275- key1->free_tree();
1276- key2->free_tree();
1277- return 0; // Can't optimize this
1278- }
1279-
1280- // If one of the key is MAYBE_KEY then the found region may be bigger
1281- if (key1->type == optimizer::SEL_ARG::MAYBE_KEY)
1282- {
1283- key2->free_tree();
1284- key1->use_count++;
1285- return key1;
1286- }
1287- if (key2->type == optimizer::SEL_ARG::MAYBE_KEY)
1288- {
1289- key1->free_tree();
1290- key2->use_count++;
1291- return key2;
1292- }
1293-
1294- if (key1->use_count > 0)
1295- {
1296- if (key2->use_count == 0 || key1->elements > key2->elements)
1297- {
1298- std::swap(key1,key2);
1299- }
1300- if (key1->use_count > 0 || !(key1=key1->clone_tree(param)))
1301- return 0; // OOM
1302- }
1303-
1304- // Add tree at key2 to tree at key1
1305- bool key2_shared= key2->use_count != 0;
1306- key1->maybe_flag|= key2->maybe_flag;
1307-
1308- for (key2=key2->first(); key2; )
1309- {
1310- optimizer::SEL_ARG *tmp= key1->find_range(key2); // Find key1.min <= key2.min
1311- int cmp;
1312-
1313- if (! tmp)
1314- {
1315- tmp=key1->first(); // tmp.min > key2.min
1316- cmp= -1;
1317- }
1318- else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
1319- { // Found tmp.max < key2.min
1320- optimizer::SEL_ARG *next= tmp->next;
1321- if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part))
1322- {
1323- // Join near ranges like tmp.max < 0 and key2.min >= 0
1324- optimizer::SEL_ARG *key2_next=key2->next;
1325- if (key2_shared)
1326- {
1327- if (! (key2=new optimizer::SEL_ARG(*key2)))
1328- return 0; // out of memory
1329- key2->increment_use_count(key1->use_count+1);
1330- key2->next= key2_next; // New copy of key2
1331- }
1332- key2->copy_min(tmp);
1333- if (! (key1=key1->tree_delete(tmp)))
1334- { // Only one key in tree
1335- key1= key2;
1336- key1->make_root();
1337- key2= key2_next;
1338- break;
1339- }
1340- }
1341- if (! (tmp= next)) // tmp.min > key2.min
1342- break; // Copy rest of key2
1343- }
1344- if (cmp < 0)
1345- { // tmp.min > key2.min
1346- int tmp_cmp;
1347- if ((tmp_cmp= tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max
1348- {
1349- if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
1350- { // ranges are connected
1351- tmp->copy_min_to_min(key2);
1352- key1->merge_flags(key2);
1353- if (tmp->min_flag & NO_MIN_RANGE &&
1354- tmp->max_flag & NO_MAX_RANGE)
1355- {
1356- if (key1->maybe_flag)
1357- return new optimizer::SEL_ARG(optimizer::SEL_ARG::MAYBE_KEY);
1358- return 0;
1359- }
1360- key2->increment_use_count(-1); // Free not used tree
1361- key2= key2->next;
1362- continue;
1363- }
1364- else
1365- {
1366- optimizer::SEL_ARG *next= key2->next; // Keys are not overlapping
1367- if (key2_shared)
1368- {
1369- optimizer::SEL_ARG *cpy= new optimizer::SEL_ARG(*key2); // Must make copy
1370- if (! cpy)
1371- return 0; // OOM
1372- key1= key1->insert(cpy);
1373- key2->increment_use_count(key1->use_count+1);
1374- }
1375- else
1376- key1= key1->insert(key2); // Will destroy key2_root
1377- key2= next;
1378- continue;
1379- }
1380- }
1381- }
1382-
1383- // tmp.max >= key2.min && tmp.min <= key.cmax(overlapping ranges)
1384- if (eq_tree(tmp->next_key_part,key2->next_key_part))
1385- {
1386- if (tmp->is_same(key2))
1387- {
1388- tmp->merge_flags(key2); // Copy maybe flags
1389- key2->increment_use_count(-1); // Free not used tree
1390- }
1391- else
1392- {
1393- optimizer::SEL_ARG *last= tmp;
1394- while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
1395- eq_tree(last->next->next_key_part,key2->next_key_part))
1396- {
1397- optimizer::SEL_ARG *save= last;
1398- last= last->next;
1399- key1= key1->tree_delete(save);
1400- }
1401- last->copy_min(tmp);
1402- if (last->copy_min(key2) || last->copy_max(key2))
1403- { // Full range
1404- key1->free_tree();
1405- for (; key2; key2= key2->next)
1406- key2->increment_use_count(-1); // Free not used tree
1407- if (key1->maybe_flag)
1408- return new optimizer::SEL_ARG(optimizer::SEL_ARG::MAYBE_KEY);
1409- return 0;
1410- }
1411- }
1412- key2= key2->next;
1413- continue;
1414- }
1415-
1416- if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
1417- { // tmp.min <= x < key2.min
1418- optimizer::SEL_ARG *new_arg= tmp->clone_first(key2);
1419- if (! new_arg)
1420- return 0; // OOM
1421- if ((new_arg->next_key_part= key1->next_key_part))
1422- new_arg->increment_use_count(key1->use_count+1);
1423- tmp->copy_min_to_min(key2);
1424- key1= key1->insert(new_arg);
1425- }
1426-
1427- // tmp.min >= key2.min && tmp.min <= key2.max
1428- optimizer::SEL_ARG key(*key2); // Get copy we can modify
1429- for (;;)
1430- {
1431- if (tmp->cmp_min_to_min(&key) > 0)
1432- { // key.min <= x < tmp.min
1433- optimizer::SEL_ARG *new_arg= key.clone_first(tmp);
1434- if (! new_arg)
1435- return 0; // OOM
1436- if ((new_arg->next_key_part=key.next_key_part))
1437- new_arg->increment_use_count(key1->use_count+1);
1438- key1= key1->insert(new_arg);
1439- }
1440- if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
1441- { // tmp.min. <= x <= tmp.max
1442- tmp->maybe_flag|= key.maybe_flag;
1443- key.increment_use_count(key1->use_count+1);
1444- tmp->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
1445- if (! cmp) // Key2 is ready
1446- break;
1447- key.copy_max_to_min(tmp);
1448- if (! (tmp= tmp->next))
1449- {
1450- optimizer::SEL_ARG *tmp2= new optimizer::SEL_ARG(key);
1451- if (! tmp2)
1452- return 0; // OOM
1453- key1= key1->insert(tmp2);
1454- key2= key2->next;
1455- goto end;
1456- }
1457- if (tmp->cmp_min_to_max(&key) > 0)
1458- {
1459- optimizer::SEL_ARG *tmp2= new optimizer::SEL_ARG(key);
1460- if (! tmp2)
1461- return 0; // OOM
1462- key1= key1->insert(tmp2);
1463- break;
1464- }
1465- }
1466- else
1467- {
1468- optimizer::SEL_ARG *new_arg= tmp->clone_last(&key); // tmp.min <= x <= key.max
1469- if (! new_arg)
1470- return 0; // OOM
1471- tmp->copy_max_to_min(&key);
1472- tmp->increment_use_count(key1->use_count+1);
1473- /* Increment key count as it may be used for next loop */
1474- key.increment_use_count(1);
1475- new_arg->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
1476- key1= key1->insert(new_arg);
1477- break;
1478- }
1479- }
1480- key2= key2->next;
1481- }
1482-
1483-end:
1484- while (key2)
1485- {
1486- optimizer::SEL_ARG *next= key2->next;
1487- if (key2_shared)
1488- {
1489- optimizer::SEL_ARG *tmp= new optimizer::SEL_ARG(*key2); // Must make copy
1490- if (! tmp)
1491- return 0;
1492- key2->increment_use_count(key1->use_count+1);
1493- key1= key1->insert(tmp);
1494- }
1495- else
1496- key1= key1->insert(key2); // Will destroy key2_root
1497- key2= next;
1498- }
1499- key1->use_count++;
1500- return key1;
1501-}
1502-
1503-
1504-/* Compare if two trees are equal */
1505-static bool eq_tree(optimizer::SEL_ARG *a, optimizer::SEL_ARG *b)
1506-{
1507- if (a == b)
1508- {
1509- return true;
1510- }
1511-
1512- if (! a || ! b || ! a->is_same(b))
1513- {
1514- return false;
1515- }
1516-
1517- if (a->left != &optimizer::null_element && b->left != &optimizer::null_element)
1518- {
1519- if (! eq_tree(a->left,b->left))
1520- return false;
1521- }
1522- else if (a->left != &optimizer::null_element || b->left != &optimizer::null_element)
1523- {
1524- return false;
1525- }
1526-
1527- if (a->right != &optimizer::null_element && b->right != &optimizer::null_element)
1528- {
1529- if (! eq_tree(a->right,b->right))
1530- return false;
1531- }
1532- else if (a->right != &optimizer::null_element || b->right != &optimizer::null_element)
1533- {
1534- return false;
1535- }
1536-
1537- if (a->next_key_part != b->next_key_part)
1538- { // Sub range
1539- if (! a->next_key_part != ! b->next_key_part ||
1540- ! eq_tree(a->next_key_part, b->next_key_part))
1541- return false;
1542- }
1543-
1544- return true;
1545-}
1546-
1547-
1548 /****************************************************************************
1549 MRR Range Sequence Interface implementation that walks a SEL_ARG* tree.
1550 ****************************************************************************/
1551@@ -4340,7 +3561,7 @@
1552 */
1553 typedef struct st_sel_arg_range_seq
1554 {
1555- uint32_t keyno; /* index of used tree in SEL_TREE structure */
1556+ uint32_t keyno; /* index of used tree in optimizer::SEL_TREE structure */
1557 uint32_t real_keyno; /* Number of the index in tables */
1558 optimizer::Parameter *param;
1559 optimizer::SEL_ARG *start; /* Root node of the traversed SEL_ARG* graph */
1560@@ -4582,7 +3803,7 @@
1561 SYNOPSIS
1562 check_quick_select()
1563 param Parameter from test_quick_select
1564- idx Number of index to use in Parameter::key SEL_TREE::key
1565+ idx Number of index to use in Parameter::key optimizer::SEL_TREE::key
1566 index_only true - assume only index tuples will be accessed
1567 false - assume full table rows will be read
1568 tree Transformed selection condition, tree->key[idx] holds
1569@@ -5196,7 +4417,7 @@
1570 static inline uint32_t get_field_keypart(KEY *index, Field *field);
1571
1572 static inline optimizer::SEL_ARG * get_index_range_tree(uint32_t index,
1573- SEL_TREE *range_tree,
1574+ optimizer::SEL_TREE *range_tree,
1575 optimizer::Parameter *param,
1576 uint32_t *param_idx);
1577
1578@@ -5217,7 +4438,7 @@
1579 KEY *index_info,
1580 uint32_t used_key_parts,
1581 uint32_t group_key_parts,
1582- SEL_TREE *range_tree,
1583+ optimizer::SEL_TREE *range_tree,
1584 optimizer::SEL_ARG *index_tree,
1585 ha_rows quick_prefix_records,
1586 bool have_min,
1587@@ -5354,7 +4575,7 @@
1588 - NULL
1589 */
1590 static optimizer::GroupMinMaxReadPlan *
1591-get_best_group_min_max(optimizer::Parameter *param, SEL_TREE *tree)
1592+get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree)
1593 {
1594 Session *session= param->session;
1595 JOIN *join= session->lex->current_select->join;
1596@@ -6068,8 +5289,8 @@
1597
1598 DESCRIPTION
1599
1600- A SEL_TREE contains range trees for all usable indexes. This procedure
1601- finds the SEL_ARG sub-tree for 'index'. The members of a SEL_TREE are
1602+ A optimizer::SEL_TREE contains range trees for all usable indexes. This procedure
1603+ finds the SEL_ARG sub-tree for 'index'. The members of a optimizer::SEL_TREE are
1604 ordered in the same way as the members of Parameter::key, thus we first find
1605 the corresponding index in the array Parameter::key. This index is returned
1606 through the variable param_idx, to be used later as argument of
1607@@ -6079,7 +5300,7 @@
1608 Pointer to the SEL_ARG subtree that corresponds to index.
1609 */
1610 optimizer::SEL_ARG *get_index_range_tree(uint32_t index,
1611- SEL_TREE* range_tree,
1612+ optimizer::SEL_TREE* range_tree,
1613 optimizer::Parameter *param,
1614 uint32_t *param_idx)
1615 {
1616@@ -6158,7 +5379,7 @@
1617 KEY *index_info,
1618 uint32_t used_key_parts,
1619 uint32_t group_key_parts,
1620- SEL_TREE *range_tree,
1621+ optimizer::SEL_TREE *range_tree,
1622 optimizer::SEL_ARG *,
1623 ha_rows quick_prefix_records,
1624 bool have_min,
1625@@ -6360,67 +5581,4 @@
1626 }
1627
1628
1629-static void print_sel_tree(optimizer::Parameter *param, SEL_TREE *tree, key_map *tree_map, const char *)
1630-{
1631- optimizer::SEL_ARG **key= NULL;
1632- optimizer::SEL_ARG **end= NULL;
1633- int idx= 0;
1634- char buff[1024];
1635-
1636- String tmp(buff,sizeof(buff),&my_charset_bin);
1637- tmp.length(0);
1638- for (idx= 0, key=tree->keys, end= key + param->keys;
1639- key != end;
1640- key++, idx++)
1641- {
1642- if (tree_map->test(idx))
1643- {
1644- uint32_t keynr= param->real_keynr[idx];
1645- if (tmp.length())
1646- tmp.append(',');
1647- tmp.append(param->table->key_info[keynr].name);
1648- }
1649- }
1650- if (! tmp.length())
1651- tmp.append(STRING_WITH_LEN("(empty)"));
1652-}
1653-
1654-
1655-static void print_ror_scans_arr(Table *table,
1656- const char *,
1657- struct st_ror_scan_info **start,
1658- struct st_ror_scan_info **end)
1659-{
1660- char buff[1024];
1661- String tmp(buff,sizeof(buff),&my_charset_bin);
1662- tmp.length(0);
1663- for (; start != end; start++)
1664- {
1665- if (tmp.length())
1666- tmp.append(',');
1667- tmp.append(table->key_info[(*start)->keynr].name);
1668- }
1669- if (! tmp.length())
1670- tmp.append(STRING_WITH_LEN("(empty)"));
1671-}
1672-
1673-static void print_ror_scans_vector(Table *table,
1674- const char *,
1675- vector<struct st_ror_scan_info *> &vec)
1676-{
1677- char buff[1024];
1678- String tmp(buff,sizeof(buff),&my_charset_bin);
1679- tmp.length(0);
1680- for (vector<struct st_ror_scan_info *>::iterator it= vec.begin();
1681- it != vec.end();
1682- ++it)
1683- {
1684- if (tmp.length())
1685- tmp.append(',');
1686- tmp.append(table->key_info[(*it)->keynr].name);
1687- }
1688- if (! tmp.length())
1689- tmp.append(STRING_WITH_LEN("(empty)"));
1690-}
1691-
1692 } /* namespace drizzled */
1693
1694=== added file 'drizzled/optimizer/sel_imerge.cc'
1695--- drizzled/optimizer/sel_imerge.cc 1970-01-01 00:00:00 +0000
1696+++ drizzled/optimizer/sel_imerge.cc 2010-03-16 01:44:16 +0000
1697@@ -0,0 +1,98 @@
1698+/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
1699+ * vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
1700+ *
1701+ * Copyright (C) 2008-2009 Sun Microsystems
1702+ *
1703+ * This program is free software; you can redistribute it and/or modify
1704+ * it under the terms of the GNU General Public License as published by
1705+ * the Free Software Foundation; version 2 of the License.
1706+ *
1707+ * This program is distributed in the hope that it will be useful,
1708+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
1709+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1710+ * GNU General Public License for more details.
1711+ *
1712+ * You should have received a copy of the GNU General Public License
1713+ * along with this program; if not, write to the Free Software
1714+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
1715+ */
1716+
1717+#include "config.h"
1718+
1719+#include "drizzled/sql_base.h"
1720+#include "drizzled/sql_select.h"
1721+#include "drizzled/memory/sql_alloc.h"
1722+#include "drizzled/optimizer/range.h"
1723+#include "drizzled/optimizer/range_param.h"
1724+#include "drizzled/optimizer/sel_arg.h"
1725+#include "drizzled/optimizer/sel_tree.h"
1726+#include "drizzled/optimizer/sel_imerge.h"
1727+
1728+using namespace std;
1729+using namespace drizzled;
1730+
1731+optimizer::SEL_IMERGE::SEL_IMERGE()
1732+ :
1733+ trees(&trees_prealloced[0]),
1734+ trees_next(trees),
1735+ trees_end(trees + PREALLOCED_TREES)
1736+{}
1737+
1738+
1739+int optimizer::SEL_IMERGE::or_sel_tree(optimizer::RangeParameter *param, optimizer::SEL_TREE *tree)
1740+{
1741+ if (trees_next == trees_end)
1742+ {
1743+ const int realloc_ratio= 2; /* Double size for next round */
1744+ uint32_t old_elements= (trees_end - trees);
1745+ uint32_t old_size= sizeof(optimizer::SEL_TREE**) * old_elements;
1746+ uint32_t new_size= old_size * realloc_ratio;
1747+ optimizer::SEL_TREE **new_trees= NULL;
1748+ if (! (new_trees= (optimizer::SEL_TREE**) alloc_root(param->mem_root, new_size)))
1749+ return -1;
1750+ memcpy(new_trees, trees, old_size);
1751+ trees= new_trees;
1752+ trees_next= trees + old_elements;
1753+ trees_end= trees + old_elements * realloc_ratio;
1754+ }
1755+ *(trees_next++)= tree;
1756+ return 0;
1757+}
1758+
1759+
1760+int optimizer::SEL_IMERGE::or_sel_tree_with_checks(optimizer::RangeParameter *param, optimizer::SEL_TREE *new_tree)
1761+{
1762+ for (optimizer::SEL_TREE** tree = trees;
1763+ tree != trees_next;
1764+ tree++)
1765+ {
1766+ if (sel_trees_can_be_ored(*tree, new_tree, param))
1767+ {
1768+ *tree = tree_or(param, *tree, new_tree);
1769+ if (!*tree)
1770+ return 1;
1771+ if (((*tree)->type == optimizer::SEL_TREE::MAYBE) ||
1772+ ((*tree)->type == optimizer::SEL_TREE::ALWAYS))
1773+ return 1;
1774+ /* optimizer::SEL_TREE::IMPOSSIBLE is impossible here */
1775+ return 0;
1776+ }
1777+ }
1778+
1779+ /* New tree cannot be combined with any of existing trees. */
1780+ return or_sel_tree(param, new_tree);
1781+}
1782+
1783+
1784+int optimizer::SEL_IMERGE::or_sel_imerge_with_checks(optimizer::RangeParameter *param, optimizer::SEL_IMERGE* imerge)
1785+{
1786+ for (optimizer::SEL_TREE** tree= imerge->trees;
1787+ tree != imerge->trees_next;
1788+ tree++)
1789+ {
1790+ if (or_sel_tree_with_checks(param, *tree))
1791+ return 1;
1792+ }
1793+ return 0;
1794+}
1795+
1796
1797=== added file 'drizzled/optimizer/sel_imerge.h'
1798--- drizzled/optimizer/sel_imerge.h 1970-01-01 00:00:00 +0000
1799+++ drizzled/optimizer/sel_imerge.h 2010-03-16 01:44:16 +0000
1800@@ -0,0 +1,122 @@
1801+/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
1802+ * vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
1803+ *
1804+ * Copyright (C) 2008-2009 Sun Microsystems
1805+ *
1806+ * This program is free software; you can redistribute it and/or modify
1807+ * it under the terms of the GNU General Public License as published by
1808+ * the Free Software Foundation; version 2 of the License.
1809+ *
1810+ * This program is distributed in the hope that it will be useful,
1811+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
1812+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1813+ * GNU General Public License for more details.
1814+ *
1815+ * You should have received a copy of the GNU General Public License
1816+ * along with this program; if not, write to the Free Software
1817+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
1818+ */
1819+
1820+#ifndef DRIZZLED_OPTIMIZER_SEL_IMERGE_H
1821+#define DRIZZLED_OPTIMIZER_SEL_IMERGE_H
1822+
1823+#include "drizzled/memory/sql_alloc.h"
1824+
1825+namespace drizzled
1826+{
1827+
1828+namespace optimizer
1829+{
1830+
1831+class RangeParameter;
1832+class SEL_TREE;
1833+class SEL_ARG;
1834+
1835+/*
1836+ SEL_IMERGE is a list of possible ways to do index merge, i.e. it is
1837+ a condition in the following form:
1838+ (t_1||t_2||...||t_N) && (next)
1839+
1840+ where all t_i are optimizer::SEL_TREEs, next is another SEL_IMERGE and no pair
1841+ (t_i,t_j) contains SEL_ARGS for the same index.
1842+
1843+ optimizer::SEL_TREE contained in SEL_IMERGE always has merges=NULL.
1844+
1845+ This class relies on memory manager to do the cleanup.
1846+*/
1847+class SEL_IMERGE : public memory::SqlAlloc
1848+{
1849+ enum { PREALLOCED_TREES= 10};
1850+public:
1851+ SEL_TREE *trees_prealloced[PREALLOCED_TREES];
1852+ SEL_TREE **trees; /* trees used to do index_merge */
1853+ SEL_TREE **trees_next; /* last of these trees */
1854+ SEL_TREE **trees_end; /* end of allocated space */
1855+
1856+ SEL_ARG ***best_keys; /* best keys to read in optimizer::SEL_TREEs */
1857+
1858+ SEL_IMERGE();
1859+
1860+ /*
1861+ Add optimizer::SEL_TREE to this index_merge without any checks,
1862+
1863+ NOTES
1864+ This function implements the following:
1865+ (x_1||...||x_N) || t = (x_1||...||x_N||t), where x_i, t are optimizer::SEL_TREEs
1866+
1867+ RETURN
1868+ 0 - OK
1869+ -1 - Out of memory.
1870+ */
1871+ int or_sel_tree(RangeParameter *param, SEL_TREE *tree);
1872+
1873+ /*
1874+ Perform OR operation on this SEL_IMERGE and supplied optimizer::SEL_TREE new_tree,
1875+ combining new_tree with one of the trees in this SEL_IMERGE if they both
1876+ have SEL_ARGs for the same key.
1877+
1878+ SYNOPSIS
1879+ or_sel_tree_with_checks()
1880+ param Parameter from SqlSelect::test_quick_select
1881+ new_tree optimizer::SEL_TREE with type KEY or KEY_SMALLER.
1882+
1883+ NOTES
1884+ This does the following:
1885+ (t_1||...||t_k)||new_tree =
1886+ either
1887+ = (t_1||...||t_k||new_tree)
1888+ or
1889+ = (t_1||....||(t_j|| new_tree)||...||t_k),
1890+
1891+ where t_i, y are optimizer::SEL_TREEs.
1892+ new_tree is combined with the first t_j it has a SEL_ARG on common
1893+ key with. As a consequence of this, choice of keys to do index_merge
1894+ read may depend on the order of conditions in WHERE part of the query.
1895+
1896+ RETURN
1897+ 0 OK
1898+ 1 One of the trees was combined with new_tree to optimizer::SEL_TREE::ALWAYS,
1899+ and (*this) should be discarded.
1900+ -1 An error occurred.
1901+ */
1902+ int or_sel_tree_with_checks(optimizer::RangeParameter *param, optimizer::SEL_TREE *new_tree);
1903+
1904+ /*
1905+ Perform OR operation on this index_merge and supplied index_merge list.
1906+
1907+ RETURN
1908+ 0 - OK
1909+ 1 - One of conditions in result is always true and this SEL_IMERGE
1910+ should be discarded.
1911+ -1 - An error occurred
1912+ */
1913+ int or_sel_imerge_with_checks(optimizer::RangeParameter *param, SEL_IMERGE* imerge);
1914+
1915+};
1916+
1917+
1918+} /* namespace optimizer */
1919+
1920+} /* namespace drizzled */
1921+
1922+#endif /* DRIZZLED_OPTIMIZER_SEL_IMERGE_H */
1923
1924=== added file 'drizzled/optimizer/sel_tree.cc'
1925--- drizzled/optimizer/sel_tree.cc 1970-01-01 00:00:00 +0000
1926+++ drizzled/optimizer/sel_tree.cc 2010-03-16 01:44:16 +0000
1927@@ -0,0 +1,600 @@
1928+/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
1929+ * vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
1930+ *
1931+ * Copyright (C) 2008-2009 Sun Microsystems
1932+ *
1933+ * This program is free software; you can redistribute it and/or modify
1934+ * it under the terms of the GNU General Public License as published by
1935+ * the Free Software Foundation; version 2 of the License.
1936+ *
1937+ * This program is distributed in the hope that it will be useful,
1938+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
1939+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1940+ * GNU General Public License for more details.
1941+ *
1942+ * You should have received a copy of the GNU General Public License
1943+ * along with this program; if not, write to the Free Software
1944+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
1945+ */
1946+
1947+#include "config.h"
1948+
1949+#include "drizzled/sql_base.h"
1950+#include "drizzled/sql_select.h"
1951+#include "drizzled/memory/sql_alloc.h"
1952+#include "drizzled/optimizer/range.h"
1953+#include "drizzled/optimizer/range_param.h"
1954+#include "drizzled/optimizer/sel_arg.h"
1955+#include "drizzled/optimizer/sel_tree.h"
1956+#include "drizzled/optimizer/sel_imerge.h"
1957+
1958+using namespace std;
1959+using namespace drizzled;
1960+
1961+static optimizer::SEL_ARG *key_or(optimizer::RangeParameter *param, optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);
1962+static bool eq_tree(optimizer::SEL_ARG* a, optimizer::SEL_ARG *b);
1963+
1964+bool optimizer::sel_trees_can_be_ored(optimizer::SEL_TREE *tree1,
1965+ optimizer::SEL_TREE *tree2,
1966+ optimizer::RangeParameter* param)
1967+{
1968+ key_map common_keys= tree1->keys_map;
1969+ common_keys&= tree2->keys_map;
1970+
1971+ if (common_keys.none())
1972+ {
1973+ return false;
1974+ }
1975+
1976+ /* trees have a common key, check if they refer to same key part */
1977+ optimizer::SEL_ARG **key1,**key2;
1978+ for (uint32_t key_no=0; key_no < param->keys; key_no++)
1979+ {
1980+ if (common_keys.test(key_no))
1981+ {
1982+ key1= tree1->keys + key_no;
1983+ key2= tree2->keys + key_no;
1984+ if ((*key1)->part == (*key2)->part)
1985+ {
1986+ return true;
1987+ }
1988+ }
1989+ }
1990+ return false;
1991+}
1992+
1993+
1994+/*
1995+ Perform OR operation on 2 index_merge lists, storing result in first list.
1996+
1997+ NOTES
1998+ The following conversion is implemented:
1999+ (a_1 &&...&& a_N)||(b_1 &&...&& b_K) = AND_i,j(a_i || b_j) =>
2000+ => (a_1||b_1).
2001+
2002+ i.e. all conjuncts except the first one are currently dropped.
2003+ This is done to avoid producing N*K ways to do index_merge.
2004+
2005+ If (a_1||b_1) produce a condition that is always true, NULL is returned
2006+ and index_merge is discarded (while it is actually possible to try
2007+ harder).
2008+
2009+ As a consequence of this, choice of keys to do index_merge read may depend
2010+ on the order of conditions in WHERE part of the query.
2011+
2012+ RETURN
2013+ 0 OK, result is stored in *im1
2014+ other Error, both passed lists are unusable
2015+*/
2016+
2017+static int imerge_list_or_list(optimizer::RangeParameter *param,
2018+ List<optimizer::SEL_IMERGE> *im1,
2019+ List<optimizer::SEL_IMERGE> *im2)
2020+{
2021+ optimizer::SEL_IMERGE *imerge= im1->head();
2022+ im1->empty();
2023+ im1->push_back(imerge);
2024+
2025+ return imerge->or_sel_imerge_with_checks(param, im2->head());
2026+}
2027+
2028+
2029+/*
2030+ Perform OR operation on index_merge list and key tree.
2031+
2032+ RETURN
2033+ 0 OK, result is stored in *im1.
2034+ other Error
2035+ */
2036+
2037+static int imerge_list_or_tree(optimizer::RangeParameter *param,
2038+ List<optimizer::SEL_IMERGE> *im1,
2039+ optimizer::SEL_TREE *tree)
2040+{
2041+ optimizer::SEL_IMERGE *imerge= NULL;
2042+ List_iterator<optimizer::SEL_IMERGE> it(*im1);
2043+ while ((imerge= it++))
2044+ {
2045+ if (imerge->or_sel_tree_with_checks(param, tree))
2046+ it.remove();
2047+ }
2048+ return im1->is_empty();
2049+}
2050+
2051+
2052+optimizer::SEL_TREE *
2053+optimizer::tree_or(optimizer::RangeParameter *param,
2054+ optimizer::SEL_TREE *tree1,
2055+ optimizer::SEL_TREE *tree2)
2056+{
2057+ if (! tree1 || ! tree2)
2058+ {
2059+ return 0;
2060+ }
2061+
2062+ if (tree1->type == optimizer::SEL_TREE::IMPOSSIBLE || tree2->type == optimizer::SEL_TREE::ALWAYS)
2063+ {
2064+ return tree2;
2065+ }
2066+
2067+ if (tree2->type == optimizer::SEL_TREE::IMPOSSIBLE || tree1->type == optimizer::SEL_TREE::ALWAYS)
2068+ {
2069+ return tree1;
2070+ }
2071+
2072+ if (tree1->type == optimizer::SEL_TREE::MAYBE)
2073+ {
2074+ return tree1; // Can't use this
2075+ }
2076+
2077+ if (tree2->type == optimizer::SEL_TREE::MAYBE)
2078+ {
2079+ return tree2;
2080+ }
2081+
2082+ optimizer::SEL_TREE *result= NULL;
2083+ key_map result_keys;
2084+ result_keys.reset();
2085+ if (sel_trees_can_be_ored(tree1, tree2, param))
2086+ {
2087+ /* Join the trees key per key */
2088+ optimizer::SEL_ARG **key1= NULL;
2089+ optimizer::SEL_ARG **key2= NULL;
2090+ optimizer::SEL_ARG **end= NULL;
2091+ for (key1= tree1->keys,key2= tree2->keys,end= key1+param->keys;
2092+ key1 != end;
2093+ key1++, key2++)
2094+ {
2095+ *key1= key_or(param, *key1, *key2);
2096+ if (*key1)
2097+ {
2098+ result= tree1; // Added to tree1
2099+ result_keys.set(key1 - tree1->keys);
2100+ }
2101+ }
2102+ if (result)
2103+ result->keys_map= result_keys;
2104+ }
2105+ else
2106+ {
2107+ /* ok, two trees have KEY type but cannot be used without index merge */
2108+ if (tree1->merges.is_empty() && tree2->merges.is_empty())
2109+ {
2110+ if (param->remove_jump_scans)
2111+ {
2112+ bool no_trees= optimizer::remove_nonrange_trees(param, tree1);
2113+ no_trees= no_trees || optimizer::remove_nonrange_trees(param, tree2);
2114+ if (no_trees)
2115+ {
2116+ return (new optimizer::SEL_TREE(optimizer::SEL_TREE::ALWAYS));
2117+ }
2118+ }
2119+ optimizer::SEL_IMERGE *merge= NULL;
2120+ /* both trees are "range" trees, produce new index merge structure */
2121+ if (! (result= new optimizer::SEL_TREE()) ||
2122+ ! (merge= new optimizer::SEL_IMERGE()) ||
2123+ (result->merges.push_back(merge)) ||
2124+ (merge->or_sel_tree(param, tree1)) ||
2125+ (merge->or_sel_tree(param, tree2)))
2126+ {
2127+ result= NULL;
2128+ }
2129+ else
2130+ {
2131+ result->type= tree1->type;
2132+ }
2133+ }
2134+ else if (!tree1->merges.is_empty() && !tree2->merges.is_empty())
2135+ {
2136+ if (imerge_list_or_list(param, &tree1->merges, &tree2->merges))
2137+ result= new optimizer::SEL_TREE(optimizer::SEL_TREE::ALWAYS);
2138+ else
2139+ result= tree1;
2140+ }
2141+ else
2142+ {
2143+ /* one tree is index merge tree and another is range tree */
2144+ if (tree1->merges.is_empty())
2145+ std::swap(tree1, tree2);
2146+
2147+ if (param->remove_jump_scans && optimizer::remove_nonrange_trees(param, tree2))
2148+ return(new optimizer::SEL_TREE(optimizer::SEL_TREE::ALWAYS));
2149+ /* add tree2 to tree1->merges, checking if it collapses to ALWAYS */
2150+ if (imerge_list_or_tree(param, &tree1->merges, tree2))
2151+ result= new optimizer::SEL_TREE(optimizer::SEL_TREE::ALWAYS);
2152+ else
2153+ result= tree1;
2154+ }
2155+ }
2156+ return result;
2157+}
2158+
2159+
2160+static optimizer::SEL_ARG *
2161+key_or(optimizer::RangeParameter *param, optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2)
2162+{
2163+ if (! key1)
2164+ {
2165+ if (key2)
2166+ {
2167+ key2->use_count--;
2168+ key2->free_tree();
2169+ }
2170+ return 0;
2171+ }
2172+ if (! key2)
2173+ {
2174+ key1->use_count--;
2175+ key1->free_tree();
2176+ return 0;
2177+ }
2178+ key1->use_count--;
2179+ key2->use_count--;
2180+
2181+ if (key1->part != key2->part)
2182+ {
2183+ key1->free_tree();
2184+ key2->free_tree();
2185+ return 0; // Can't optimize this
2186+ }
2187+
2188+ // If one of the key is MAYBE_KEY then the found region may be bigger
2189+ if (key1->type == optimizer::SEL_ARG::MAYBE_KEY)
2190+ {
2191+ key2->free_tree();
2192+ key1->use_count++;
2193+ return key1;
2194+ }
2195+ if (key2->type == optimizer::SEL_ARG::MAYBE_KEY)
2196+ {
2197+ key1->free_tree();
2198+ key2->use_count++;
2199+ return key2;
2200+ }
2201+
2202+ if (key1->use_count > 0)
2203+ {
2204+ if (key2->use_count == 0 || key1->elements > key2->elements)
2205+ {
2206+ std::swap(key1,key2);
2207+ }
2208+ if (key1->use_count > 0 || !(key1=key1->clone_tree(param)))
2209+ return 0; // OOM
2210+ }
2211+
2212+ // Add tree at key2 to tree at key1
2213+ bool key2_shared= key2->use_count != 0;
2214+ key1->maybe_flag|= key2->maybe_flag;
2215+
2216+ for (key2=key2->first(); key2; )
2217+ {
2218+ optimizer::SEL_ARG *tmp= key1->find_range(key2); // Find key1.min <= key2.min
2219+ int cmp;
2220+
2221+ if (! tmp)
2222+ {
2223+ tmp=key1->first(); // tmp.min > key2.min
2224+ cmp= -1;
2225+ }
2226+ else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
2227+ { // Found tmp.max < key2.min
2228+ optimizer::SEL_ARG *next= tmp->next;
2229+ if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part))
2230+ {
2231+ // Join near ranges like tmp.max < 0 and key2.min >= 0
2232+ optimizer::SEL_ARG *key2_next=key2->next;
2233+ if (key2_shared)
2234+ {
2235+ if (! (key2=new optimizer::SEL_ARG(*key2)))
2236+ return 0; // out of memory
2237+ key2->increment_use_count(key1->use_count+1);
2238+ key2->next= key2_next; // New copy of key2
2239+ }
2240+ key2->copy_min(tmp);
2241+ if (! (key1=key1->tree_delete(tmp)))
2242+ { // Only one key in tree
2243+ key1= key2;
2244+ key1->make_root();
2245+ key2= key2_next;
2246+ break;
2247+ }
2248+ }
2249+ if (! (tmp= next)) // tmp.min > key2.min
2250+ break; // Copy rest of key2
2251+ }
2252+ if (cmp < 0)
2253+ { // tmp.min > key2.min
2254+ int tmp_cmp;
2255+ if ((tmp_cmp= tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max
2256+ {
2257+ if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
2258+ { // ranges are connected
2259+ tmp->copy_min_to_min(key2);
2260+ key1->merge_flags(key2);
2261+ if (tmp->min_flag & NO_MIN_RANGE &&
2262+ tmp->max_flag & NO_MAX_RANGE)
2263+ {
2264+ if (key1->maybe_flag)
2265+ return new optimizer::SEL_ARG(optimizer::SEL_ARG::MAYBE_KEY);
2266+ return 0;
2267+ }
2268+ key2->increment_use_count(-1); // Free not used tree
2269+ key2= key2->next;
2270+ continue;
2271+ }
2272+ else
2273+ {
2274+ optimizer::SEL_ARG *next= key2->next; // Keys are not overlapping
2275+ if (key2_shared)
2276+ {
2277+ optimizer::SEL_ARG *cpy= new optimizer::SEL_ARG(*key2); // Must make copy
2278+ if (! cpy)
2279+ return 0; // OOM
2280+ key1= key1->insert(cpy);
2281+ key2->increment_use_count(key1->use_count+1);
2282+ }
2283+ else
2284+ key1= key1->insert(key2); // Will destroy key2_root
2285+ key2= next;
2286+ continue;
2287+ }
2288+ }
2289+ }
2290+
2291+ // tmp.max >= key2.min && tmp.min <= key.cmax(overlapping ranges)
2292+ if (eq_tree(tmp->next_key_part,key2->next_key_part))
2293+ {
2294+ if (tmp->is_same(key2))
2295+ {
2296+ tmp->merge_flags(key2); // Copy maybe flags
2297+ key2->increment_use_count(-1); // Free not used tree
2298+ }
2299+ else
2300+ {
2301+ optimizer::SEL_ARG *last= tmp;
2302+ while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
2303+ eq_tree(last->next->next_key_part,key2->next_key_part))
2304+ {
2305+ optimizer::SEL_ARG *save= last;
2306+ last= last->next;
2307+ key1= key1->tree_delete(save);
2308+ }
2309+ last->copy_min(tmp);
2310+ if (last->copy_min(key2) || last->copy_max(key2))
2311+ { // Full range
2312+ key1->free_tree();
2313+ for (; key2; key2= key2->next)
2314+ key2->increment_use_count(-1); // Free not used tree
2315+ if (key1->maybe_flag)
2316+ return new optimizer::SEL_ARG(optimizer::SEL_ARG::MAYBE_KEY);
2317+ return 0;
2318+ }
2319+ }
2320+ key2= key2->next;
2321+ continue;
2322+ }
2323+
2324+ if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
2325+ { // tmp.min <= x < key2.min
2326+ optimizer::SEL_ARG *new_arg= tmp->clone_first(key2);
2327+ if (! new_arg)
2328+ return 0; // OOM
2329+ if ((new_arg->next_key_part= key1->next_key_part))
2330+ new_arg->increment_use_count(key1->use_count+1);
2331+ tmp->copy_min_to_min(key2);
2332+ key1= key1->insert(new_arg);
2333+ }
2334+
2335+ // tmp.min >= key2.min && tmp.min <= key2.max
2336+ optimizer::SEL_ARG key(*key2); // Get copy we can modify
2337+ for (;;)
2338+ {
2339+ if (tmp->cmp_min_to_min(&key) > 0)
2340+ { // key.min <= x < tmp.min
2341+ optimizer::SEL_ARG *new_arg= key.clone_first(tmp);
2342+ if (! new_arg)
2343+ return 0; // OOM
2344+ if ((new_arg->next_key_part=key.next_key_part))
2345+ new_arg->increment_use_count(key1->use_count+1);
2346+ key1= key1->insert(new_arg);
2347+ }
2348+ if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
2349+ { // tmp.min. <= x <= tmp.max
2350+ tmp->maybe_flag|= key.maybe_flag;
2351+ key.increment_use_count(key1->use_count+1);
2352+ tmp->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
2353+ if (! cmp) // Key2 is ready
2354+ break;
2355+ key.copy_max_to_min(tmp);
2356+ if (! (tmp= tmp->next))
2357+ {
2358+ optimizer::SEL_ARG *tmp2= new optimizer::SEL_ARG(key);
2359+ if (! tmp2)
2360+ return 0; // OOM
2361+ key1= key1->insert(tmp2);
2362+ key2= key2->next;
2363+ goto end;
2364+ }
2365+ if (tmp->cmp_min_to_max(&key) > 0)
2366+ {
2367+ optimizer::SEL_ARG *tmp2= new optimizer::SEL_ARG(key);
2368+ if (! tmp2)
2369+ return 0; // OOM
2370+ key1= key1->insert(tmp2);
2371+ break;
2372+ }
2373+ }
2374+ else
2375+ {
2376+ optimizer::SEL_ARG *new_arg= tmp->clone_last(&key); // tmp.min <= x <= key.max
2377+ if (! new_arg)
2378+ return 0; // OOM
2379+ tmp->copy_max_to_min(&key);
2380+ tmp->increment_use_count(key1->use_count+1);
2381+ /* Increment key count as it may be used for next loop */
2382+ key.increment_use_count(1);
2383+ new_arg->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
2384+ key1= key1->insert(new_arg);
2385+ break;
2386+ }
2387+ }
2388+ key2= key2->next;
2389+ }
2390+
2391+end:
2392+ while (key2)
2393+ {
2394+ optimizer::SEL_ARG *next= key2->next;
2395+ if (key2_shared)
2396+ {
2397+ optimizer::SEL_ARG *tmp= new optimizer::SEL_ARG(*key2); // Must make copy
2398+ if (! tmp)
2399+ return 0;
2400+ key2->increment_use_count(key1->use_count+1);
2401+ key1= key1->insert(tmp);
2402+ }
2403+ else
2404+ key1= key1->insert(key2); // Will destroy key2_root
2405+ key2= next;
2406+ }
2407+ key1->use_count++;
2408+ return key1;
2409+}
2410+
2411+
2412+/*
2413+ Remove the trees that are not suitable for record retrieval.
2414+ SYNOPSIS
2415+ param Range analysis parameter
2416+ tree Tree to be processed, tree->type is KEY or KEY_SMALLER
2417+
2418+ DESCRIPTION
2419+ This function walks through tree->keys[] and removes the SEL_ARG* trees
2420+ that are not "maybe" trees (*) and cannot be used to construct quick range
2421+ selects.
2422+ (*) - have type MAYBE or MAYBE_KEY. Perhaps we should remove trees of
2423+ these types here as well.
2424+
2425+ A SEL_ARG* tree cannot be used to construct quick select if it has
2426+ tree->part != 0. (e.g. it could represent "keypart2 < const").
2427+
2428+ WHY THIS FUNCTION IS NEEDED
2429+
2430+ Normally we allow construction of optimizer::SEL_TREE objects that have SEL_ARG
2431+ trees that do not allow quick range select construction. For example for
2432+ " keypart1=1 AND keypart2=2 " the execution will proceed as follows:
2433+ tree1= optimizer::SEL_TREE { SEL_ARG{keypart1=1} }
2434+ tree2= optimizer::SEL_TREE { SEL_ARG{keypart2=2} } -- can't make quick range select
2435+ from this
2436+ call tree_and(tree1, tree2) -- this joins SEL_ARGs into a usable SEL_ARG
2437+ tree.
2438+
2439+ There is an exception though: when we construct index_merge optimizer::SEL_TREE,
2440+ any SEL_ARG* tree that cannot be used to construct quick range select can
2441+ be removed, because current range analysis code doesn't provide any way
2442+ that tree could be later combined with another tree.
2443+ Consider an example: we should not construct
2444+ st1 = optimizer::SEL_TREE {
2445+ merges = SEL_IMERGE {
2446+ optimizer::SEL_TREE(t.key1part1 = 1),
2447+ optimizer::SEL_TREE(t.key2part2 = 2) -- (*)
2448+ }
2449+ };
2450+ because
2451+ - (*) cannot be used to construct quick range select,
2452+ - There is no execution path that would cause (*) to be converted to
2453+ a tree that could be used.
2454+
2455+ The latter is easy to verify: first, notice that the only way to convert
2456+ (*) into a usable tree is to call tree_and(something, (*)).
2457+
2458+ Second look at what tree_and/tree_or function would do when passed a
2459+ optimizer::SEL_TREE that has the structure like st1 tree has, and conlcude that
2460+ tree_and(something, (*)) will not be called.
2461+
2462+ RETURN
2463+ 0 Ok, some suitable trees left
2464+ 1 No tree->keys[] left.
2465+*/
2466+bool optimizer::remove_nonrange_trees(optimizer::RangeParameter *param, optimizer::SEL_TREE *tree)
2467+{
2468+ bool res= false;
2469+ for (uint32_t i= 0; i < param->keys; i++)
2470+ {
2471+ if (tree->keys[i])
2472+ {
2473+ if (tree->keys[i]->part)
2474+ {
2475+ tree->keys[i]= NULL;
2476+ tree->keys_map.reset(i);
2477+ }
2478+ else
2479+ res= true;
2480+ }
2481+ }
2482+ return ! res;
2483+}
2484+
2485+
2486+/* Compare if two trees are equal */
2487+static bool eq_tree(optimizer::SEL_ARG *a, optimizer::SEL_ARG *b)
2488+{
2489+ if (a == b)
2490+ {
2491+ return true;
2492+ }
2493+
2494+ if (! a || ! b || ! a->is_same(b))
2495+ {
2496+ return false;
2497+ }
2498+
2499+ if (a->left != &optimizer::null_element && b->left != &optimizer::null_element)
2500+ {
2501+ if (! eq_tree(a->left,b->left))
2502+ return false;
2503+ }
2504+ else if (a->left != &optimizer::null_element || b->left != &optimizer::null_element)
2505+ {
2506+ return false;
2507+ }
2508+
2509+ if (a->right != &optimizer::null_element && b->right != &optimizer::null_element)
2510+ {
2511+ if (! eq_tree(a->right,b->right))
2512+ return false;
2513+ }
2514+ else if (a->right != &optimizer::null_element || b->right != &optimizer::null_element)
2515+ {
2516+ return false;
2517+ }
2518+
2519+ if (a->next_key_part != b->next_key_part)
2520+ { // Sub range
2521+ if (! a->next_key_part != ! b->next_key_part ||
2522+ ! eq_tree(a->next_key_part, b->next_key_part))
2523+ return false;
2524+ }
2525+
2526+ return true;
2527+}
2528
2529=== added file 'drizzled/optimizer/sel_tree.h'
2530--- drizzled/optimizer/sel_tree.h 1970-01-01 00:00:00 +0000
2531+++ drizzled/optimizer/sel_tree.h 2010-03-16 01:44:16 +0000
2532@@ -0,0 +1,155 @@
2533+/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2534+ * vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
2535+ *
2536+ * Copyright (C) 2008-2009 Sun Microsystems
2537+ *
2538+ * This program is free software; you can redistribute it and/or modify
2539+ * it under the terms of the GNU General Public License as published by
2540+ * the Free Software Foundation; version 2 of the License.
2541+ *
2542+ * This program is distributed in the hope that it will be useful,
2543+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
2544+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
2545+ * GNU General Public License for more details.
2546+ *
2547+ * You should have received a copy of the GNU General Public License
2548+ * along with this program; if not, write to the Free Software
2549+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
2550+ */
2551+
2552+#ifndef DRIZZLED_OPTIMIZER_SEL_TREE_H
2553+#define DRIZZLED_OPTIMIZER_SEL_TREE_H
2554+
2555+#include "drizzled/memory/sql_alloc.h"
2556+
2557+namespace drizzled
2558+{
2559+
2560+namespace optimizer
2561+{
2562+
2563+class RangeParameter;
2564+class SEL_IMERGE;
2565+class SEL_ARG;
2566+
2567+class SEL_TREE : public drizzled::memory::SqlAlloc
2568+{
2569+public:
2570+ /*
2571+ Starting an effort to document this field:
2572+ (for some i, keys[i]->type == optimizer::SEL_ARG::IMPOSSIBLE) =>
2573+ (type == SEL_TREE::IMPOSSIBLE)
2574+ */
2575+ enum Type
2576+ {
2577+ IMPOSSIBLE,
2578+ ALWAYS,
2579+ MAYBE,
2580+ KEY,
2581+ KEY_SMALLER
2582+ } type;
2583+
2584+ SEL_TREE(enum Type type_arg) :type(type_arg) {}
2585+ SEL_TREE() :type(KEY)
2586+ {
2587+ keys_map.reset();
2588+ memset(keys, 0, sizeof(keys));
2589+ }
2590+ /*
2591+ Note: there may exist SEL_TREE objects with sel_tree->type=KEY and
2592+ keys[i]=0 for all i. (SergeyP: it is not clear whether there is any
2593+ merit in range analyzer functions (e.g. get_mm_parts) returning a
2594+ pointer to such SEL_TREE instead of NULL)
2595+ */
2596+ SEL_ARG *keys[MAX_KEY];
2597+ key_map keys_map; /* bitmask of non-NULL elements in keys */
2598+
2599+ /*
2600+ Possible ways to read rows using index_merge. The list is non-empty only
2601+ if type==KEY. Currently can be non empty only if keys_map.none().
2602+ */
2603+ List<SEL_IMERGE> merges;
2604+
2605+ /* The members below are filled/used only after get_mm_tree is done */
2606+ key_map ror_scans_map; /* bitmask of ROR scan-able elements in keys */
2607+ uint32_t n_ror_scans; /* number of set bits in ror_scans_map */
2608+
2609+ struct st_ror_scan_info **ror_scans; /* list of ROR key scans */
2610+ struct st_ror_scan_info **ror_scans_end; /* last ROR scan */
2611+ /* Note that #records for each key scan is stored in table->quick_rows */
2612+
2613+};
2614+
2615+/*
2616+ Check if two optimizer::SEL_TREES can be combined into one (i.e. a single key range
2617+ read can be constructed for "cond_of_tree1 OR cond_of_tree2" ) without
2618+ using index_merge.
2619+*/
2620+bool sel_trees_can_be_ored(SEL_TREE *tree1,
2621+ SEL_TREE *tree2,
2622+ RangeParameter* param);
2623+
2624+SEL_TREE *
2625+tree_or(RangeParameter *param, SEL_TREE *tree1, SEL_TREE *tree2);
2626+
2627+/*
2628+ Remove the trees that are not suitable for record retrieval.
2629+ SYNOPSIS
2630+ param Range analysis parameter
2631+ tree Tree to be processed, tree->type is KEY or KEY_SMALLER
2632+
2633+ DESCRIPTION
2634+ This function walks through tree->keys[] and removes the SEL_ARG* trees
2635+ that are not "maybe" trees (*) and cannot be used to construct quick range
2636+ selects.
2637+ (*) - have type MAYBE or MAYBE_KEY. Perhaps we should remove trees of
2638+ these types here as well.
2639+
2640+ A SEL_ARG* tree cannot be used to construct quick select if it has
2641+ tree->part != 0. (e.g. it could represent "keypart2 < const").
2642+
2643+ WHY THIS FUNCTION IS NEEDED
2644+
2645+ Normally we allow construction of optimizer::SEL_TREE objects that have SEL_ARG
2646+ trees that do not allow quick range select construction. For example for
2647+ " keypart1=1 AND keypart2=2 " the execution will proceed as follows:
2648+ tree1= optimizer::SEL_TREE { SEL_ARG{keypart1=1} }
2649+ tree2= optimizer::SEL_TREE { SEL_ARG{keypart2=2} } -- can't make quick range select
2650+ from this
2651+ call tree_and(tree1, tree2) -- this joins SEL_ARGs into a usable SEL_ARG
2652+ tree.
2653+
2654+ There is an exception though: when we construct index_merge optimizer::SEL_TREE,
2655+ any SEL_ARG* tree that cannot be used to construct quick range select can
2656+ be removed, because current range analysis code doesn't provide any way
2657+ that tree could be later combined with another tree.
2658+ Consider an example: we should not construct
2659+ st1 = optimizer::SEL_TREE {
2660+ merges = SEL_IMERGE {
2661+ optimizer::SEL_TREE(t.key1part1 = 1),
2662+ optimizer::SEL_TREE(t.key2part2 = 2) -- (*)
2663+ }
2664+ };
2665+ because
2666+ - (*) cannot be used to construct quick range select,
2667+ - There is no execution path that would cause (*) to be converted to
2668+ a tree that could be used.
2669+
2670+ The latter is easy to verify: first, notice that the only way to convert
2671+ (*) into a usable tree is to call tree_and(something, (*)).
2672+
2673+ Second look at what tree_and/tree_or function would do when passed a
2674+ optimizer::SEL_TREE that has the structure like st1 tree has, and conlcude that
2675+ tree_and(something, (*)) will not be called.
2676+
2677+ RETURN
2678+ 0 Ok, some suitable trees left
2679+ 1 No tree->keys[] left.
2680+ */
2681+bool remove_nonrange_trees(RangeParameter *param, SEL_TREE *tree);
2682+
2683+} /* namespace optimizer */
2684+
2685+} /* namespace drizzled */
2686+
2687+#endif /* DRIZZLED_OPTIMIZER_SEL_TREE_H */
2688
2689=== modified file 'drizzled/optimizer/table_read_plan.h'
2690--- drizzled/optimizer/table_read_plan.h 2010-02-10 20:00:52 +0000
2691+++ drizzled/optimizer/table_read_plan.h 2010-03-16 01:44:16 +0000
2692@@ -20,10 +20,11 @@
2693 #ifndef DRIZZLED_OPTIMIZER_TABLE_READ_PLAN_H
2694 #define DRIZZLED_OPTIMIZER_TABLE_READ_PLAN_H
2695
2696+#include "drizzled/util/functors.h"
2697+
2698 namespace drizzled
2699 {
2700
2701-class SEL_TREE;
2702 struct st_ror_scan_info;
2703
2704 namespace optimizer
2705@@ -31,6 +32,7 @@
2706
2707 class Parameter;
2708 class SEL_ARG;
2709+class SEL_TREE;
2710
2711 /*
2712 Table rows retrieval plan. Range optimizer creates QuickSelectInterface-derived
2713@@ -152,7 +154,13 @@
2714 index_scan_costs(0.0)
2715 {}
2716
2717- virtual ~RorIntersectReadPlan() {} /* Remove gcc warning */
2718+ virtual ~RorIntersectReadPlan()
2719+ {
2720+ for_each(ror_range_scans.begin(),
2721+ ror_range_scans.end(),
2722+ DeletePtr());
2723+ ror_range_scans.clear();
2724+ }
2725
2726 QuickSelectInterface *make_quick(Parameter *param,
2727 bool retrieve_full_rows,