← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/optimizer/sel_tree.cc

  • Committer: Padraig O'Sullivan
  • Date: 2009-09-13 01:03:01 UTC
  • mto: (1126.9.2 captain-20090915-01)
  • mto: This revision was merged to the branch mainline in revision 1133.
  • Revision ID: osullivan.padraig@gmail.com-20090913010301-tcvvezipx1124acy
Added calls to the dtrace delete begin/end probes.

Show diffs side-by-side

added added

removed removed

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