← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/optimizer/sel_tree.cc

  • Committer: Mark Atwood
  • Date: 2011-06-24 02:13:02 UTC
  • mfrom: (2318.6.56 rf)
  • Revision ID: me@mark.atwood.name-20110624021302-y9oiksid220xan9s
merge lp:~olafvdspek/drizzle/refactor14

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/optimizer/sel_tree.cc
34
34
static optimizer::SEL_ARG *key_or(optimizer::RangeParameter *param, optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);
35
35
static bool eq_tree(optimizer::SEL_ARG* a, optimizer::SEL_ARG *b);
36
36
 
37
 
bool optimizer::sel_trees_can_be_ored(optimizer::SEL_TREE *tree1, 
38
 
                                      optimizer::SEL_TREE *tree2,
39
 
                                      optimizer::RangeParameter* param)
 
37
bool optimizer::sel_trees_can_be_ored(const SEL_TREE& tree1, const SEL_TREE& tree2, const RangeParameter& param)
40
38
{
41
 
  key_map common_keys= tree1->keys_map;
42
 
  common_keys&= tree2->keys_map;
 
39
  key_map common_keys= tree1.keys_map;
 
40
  common_keys&= tree2.keys_map;
43
41
 
44
42
  if (common_keys.none())
45
 
  {
46
43
    return false;
47
 
  }
48
44
 
49
45
  /* trees have a common key, check if they refer to same key part */
50
 
  optimizer::SEL_ARG **key1,**key2;
51
 
  for (uint32_t key_no=0; key_no < param->keys; key_no++)
 
46
  for (uint32_t key_no= 0; key_no < param.keys; key_no++)
52
47
  {
53
 
    if (common_keys.test(key_no))
54
 
    {
55
 
      key1= tree1->keys + key_no;
56
 
      key2= tree2->keys + key_no;
57
 
      if ((*key1)->part == (*key2)->part)
58
 
      {
59
 
        return true;
60
 
      }
61
 
    }
 
48
    if (common_keys.test(key_no) && tree1.keys[key_no]->part == tree2.keys[key_no]->part)
 
49
      return true;
62
50
  }
63
51
  return false;
64
52
}
87
75
    other Error, both passed lists are unusable
88
76
*/
89
77
 
90
 
static int imerge_list_or_list(optimizer::RangeParameter *param,
91
 
                               List<optimizer::SEL_IMERGE> *im1,
92
 
                               List<optimizer::SEL_IMERGE> *im2)
 
78
static int imerge_list_or_list(optimizer::RangeParameter *param, List<optimizer::SEL_IMERGE> *im1, List<optimizer::SEL_IMERGE> *im2)
93
79
{
94
80
  optimizer::SEL_IMERGE *imerge= &im1->front();
95
81
  im1->clear();
96
82
  im1->push_back(imerge);
97
83
 
98
 
  return imerge->or_sel_imerge_with_checks(param, &im2->front());
 
84
  return imerge->or_sel_imerge_with_checks(*param, im2->front());
99
85
}
100
86
 
101
87
 
107
93
     other Error
108
94
 */
109
95
 
110
 
static int imerge_list_or_tree(optimizer::RangeParameter *param,
111
 
                               List<optimizer::SEL_IMERGE> *im1,
112
 
                               optimizer::SEL_TREE *tree)
 
96
static int imerge_list_or_tree(optimizer::RangeParameter& param, List<optimizer::SEL_IMERGE>& im1, optimizer::SEL_TREE& tree)
113
97
{
114
 
  optimizer::SEL_IMERGE *imerge= NULL;
115
 
  List_iterator<optimizer::SEL_IMERGE> it(im1->begin());
116
 
  while ((imerge= it++))
 
98
  List_iterator<optimizer::SEL_IMERGE> it(im1.begin());
 
99
  while (optimizer::SEL_IMERGE* imerge= it++)
117
100
  {
118
101
    if (imerge->or_sel_tree_with_checks(param, tree))
119
102
      it.remove();
120
103
  }
121
 
  return im1->is_empty();
 
104
  return im1.is_empty();
122
105
}
123
106
 
124
107
 
125
 
optimizer::SEL_TREE *
126
 
optimizer::tree_or(optimizer::RangeParameter *param,
127
 
                   optimizer::SEL_TREE *tree1,
128
 
                   optimizer::SEL_TREE *tree2)
 
108
optimizer::SEL_TREE* optimizer::tree_or(optimizer::RangeParameter *param, optimizer::SEL_TREE *tree1, optimizer::SEL_TREE *tree2)
129
109
{
130
110
  if (! tree1 || ! tree2)
131
 
  {
132
111
    return 0;
133
 
  }
134
112
 
135
 
  if (tree1->type == optimizer::SEL_TREE::IMPOSSIBLE || tree2->type == optimizer::SEL_TREE::ALWAYS)
136
 
  {
 
113
  if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
137
114
    return tree2;
138
 
  }
139
115
 
140
 
  if (tree2->type == optimizer::SEL_TREE::IMPOSSIBLE || tree1->type == optimizer::SEL_TREE::ALWAYS)
141
 
  {
 
116
  if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
142
117
    return tree1;
143
 
  }
144
118
 
145
 
  if (tree1->type == optimizer::SEL_TREE::MAYBE)
146
 
  {
 
119
  if (tree1->type == SEL_TREE::MAYBE)
147
120
    return tree1; // Can't use this
148
 
  }
149
121
 
150
 
  if (tree2->type == optimizer::SEL_TREE::MAYBE)
151
 
  {
 
122
  if (tree2->type == SEL_TREE::MAYBE)
152
123
    return tree2;
153
 
  }
154
124
 
155
 
  optimizer::SEL_TREE *result= NULL;
 
125
  SEL_TREE *result= NULL;
156
126
  key_map  result_keys;
157
127
  result_keys.reset();
158
 
  if (sel_trees_can_be_ored(tree1, tree2, param))
 
128
  if (sel_trees_can_be_ored(*tree1, *tree2, *param))
159
129
  {
160
130
    /* Join the trees key per key */
161
 
    optimizer::SEL_ARG **key1= NULL;
162
 
    optimizer::SEL_ARG **key2= NULL;
163
 
    optimizer::SEL_ARG **end= NULL;
164
 
    for (key1= tree1->keys,key2= tree2->keys,end= key1+param->keys;
165
 
         key1 != end; 
166
 
         key1++, key2++)
 
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++)
167
135
    {
168
136
      *key1= key_or(param, *key1, *key2);
169
137
      if (*key1)
180
148
    /* ok, two trees have KEY type but cannot be used without index merge */
181
149
    if (tree1->merges.is_empty() && tree2->merges.is_empty())
182
150
    {
183
 
      if (param->remove_jump_scans)
184
 
      {
185
 
        bool no_trees= optimizer::remove_nonrange_trees(param, tree1);
186
 
        no_trees= no_trees || optimizer::remove_nonrange_trees(param, tree2);
187
 
        if (no_trees)
188
 
        {
189
 
          return (new optimizer::SEL_TREE(optimizer::SEL_TREE::ALWAYS));
190
 
        }
191
 
      }
192
 
      optimizer::SEL_IMERGE *merge= NULL;
 
151
      if (param->remove_jump_scans && (remove_nonrange_trees(param, tree1) || remove_nonrange_trees(param, tree2)))
 
152
        return new SEL_TREE(SEL_TREE::ALWAYS);
193
153
      /* both trees are "range" trees, produce new index merge structure */
194
 
                        result= new optimizer::SEL_TREE();
195
 
                        merge= new optimizer::SEL_IMERGE();
 
154
                        result= new SEL_TREE();
 
155
                        SEL_IMERGE* merge= new SEL_IMERGE();
196
156
                        result->merges.push_back(merge);
197
 
      if (merge->or_sel_tree(param, tree1) || merge->or_sel_tree(param, tree2))
198
 
      {
199
 
        result= NULL;
200
 
      }
201
 
      else
202
 
      {
203
 
        result->type= tree1->type;
204
 
      }
 
157
      merge->or_sel_tree(param, tree1);
 
158
      merge->or_sel_tree(param, tree2);
 
159
      result->type= tree1->type;
205
160
    }
206
161
    else if (!tree1->merges.is_empty() && !tree2->merges.is_empty())
207
162
    {
208
 
      if (imerge_list_or_list(param, &tree1->merges, &tree2->merges))
209
 
        result= new optimizer::SEL_TREE(optimizer::SEL_TREE::ALWAYS);
210
 
      else
211
 
        result= tree1;
 
163
      result= imerge_list_or_list(param, &tree1->merges, &tree2->merges)
 
164
        ? new SEL_TREE(SEL_TREE::ALWAYS)
 
165
        : tree1;
212
166
    }
213
167
    else
214
168
    {
216
170
      if (tree1->merges.is_empty())
217
171
        std::swap(tree1, tree2);
218
172
 
219
 
      if (param->remove_jump_scans && optimizer::remove_nonrange_trees(param, tree2))
220
 
         return(new optimizer::SEL_TREE(optimizer::SEL_TREE::ALWAYS));
 
173
      if (param->remove_jump_scans && remove_nonrange_trees(param, tree2))
 
174
         return new SEL_TREE(SEL_TREE::ALWAYS);
221
175
      /* add tree2 to tree1->merges, checking if it collapses to ALWAYS */
222
 
      if (imerge_list_or_tree(param, &tree1->merges, tree2))
223
 
        result= new optimizer::SEL_TREE(optimizer::SEL_TREE::ALWAYS);
224
 
      else
225
 
        result= tree1;
 
176
      result= imerge_list_or_tree(*param, tree1->merges, *tree2)
 
177
        ? new SEL_TREE(SEL_TREE::ALWAYS)
 
178
        : tree1;
226
179
    }
227
180
  }
228
181
  return result;
537
490
*/
538
491
bool optimizer::remove_nonrange_trees(optimizer::RangeParameter *param, optimizer::SEL_TREE *tree)
539
492
{
540
 
  bool res= false;
 
493
  bool res= true;
541
494
  for (uint32_t i= 0; i < param->keys; i++)
542
495
  {
543
496
    if (tree->keys[i])
548
501
        tree->keys_map.reset(i);
549
502
      }
550
503
      else
551
 
        res= true;
 
504
        res= false;
552
505
    }
553
506
  }
554
 
  return ! res;
 
507
  return res;
555
508
}
556
509
 
557
510
 
559
512
static bool eq_tree(optimizer::SEL_ARG *a, optimizer::SEL_ARG *b)
560
513
{
561
514
  if (a == b)
562
 
  {
563
515
    return true;
564
 
  }
565
516
 
566
517
  if (! a || ! b || ! a->is_same(b))
567
518
  {