« back to all changes in this revision
Viewing changes to drizzled/optimizer/range.cc
- browse files at revision 1237.13.44
- compare with another revision
- compare with revision 2069.4.3
- download diff
- download tarball
- view history from revision 1237.13.44
- Committer: Padraig O'Sullivan
- Date: 2010-03-15 14:52:59 UTC
- mto: This revision was merged to the branch mainline in revision 1349.
- Revision ID: osullivan.padraig@gmail.com-20100315145259-jw2g8c3f1yvej12b
Moved the SEL_TREE and SEL_IMERGE classes out into their own header and implementation files.
added
removed
drizzled/optimizer/range.cc
37
37
The entry point for the range analysis module is get_mm_tree() function.
38
38
39
39
The lists are returned in form of complicated structure of interlinked
40
SEL_TREE/SEL_IMERGE/SEL_ARG objects.
40
optimizer::SEL_TREE/optimizer::SEL_IMERGE/SEL_ARG objects.
41
41
See quick_range_seq_next, find_used_partitions for examples of how to walk
42
42
this structure.
43
43
All direct "users" of this module are located within this cursor, too.
126
126
#include "drizzled/optimizer/quick_ror_union_select.h"
127
127
#include "drizzled/optimizer/table_read_plan.h"
128
128
#include "drizzled/optimizer/sel_arg.h"
129
#include "drizzled/optimizer/sel_imerge.h"
130
#include "drizzled/optimizer/sel_tree.h"
129
131
#include "drizzled/optimizer/range_param.h"
130
132
#include "drizzled/records.h"
131
133
#include "drizzled/internal/my_sys.h"
228
230
}
229
231
}
230
232
231
class SEL_IMERGE;
232
233
234
class SEL_TREE :public memory::SqlAlloc
235
{
236
public:
237
/*
238
Starting an effort to document this field:
239
(for some i, keys[i]->type == optimizer::SEL_ARG::IMPOSSIBLE) =>
240
(type == SEL_TREE::IMPOSSIBLE)
241
*/
242
enum Type
243
{
244
IMPOSSIBLE,
245
ALWAYS,
246
MAYBE,
247
KEY,
248
KEY_SMALLER
249
} type;
250
251
SEL_TREE(enum Type type_arg) :type(type_arg) {}
252
SEL_TREE() :type(KEY)
253
{
254
keys_map.reset();
255
memset(keys, 0, sizeof(keys));
256
}
257
/*
258
Note: there may exist SEL_TREE objects with sel_tree->type=KEY and
259
keys[i]=0 for all i. (SergeyP: it is not clear whether there is any
260
merit in range analyzer functions (e.g. get_mm_parts) returning a
261
pointer to such SEL_TREE instead of NULL)
262
*/
263
optimizer::SEL_ARG *keys[MAX_KEY];
264
key_map keys_map; /* bitmask of non-NULL elements in keys */
265
266
/*
267
Possible ways to read rows using index_merge. The list is non-empty only
268
if type==KEY. Currently can be non empty only if keys_map.none().
269
*/
270
List<SEL_IMERGE> merges;
271
272
/* The members below are filled/used only after get_mm_tree is done */
273
key_map ror_scans_map; /* bitmask of ROR scan-able elements in keys */
274
uint32_t n_ror_scans; /* number of set bits in ror_scans_map */
275
276
struct st_ror_scan_info **ror_scans; /* list of ROR key scans */
277
struct st_ror_scan_info **ror_scans_end; /* last ROR scan */
278
/* Note that #records for each key scan is stored in table->quick_rows */
279
};
280
281
233
struct st_ror_scan_info;
282
234
283
static SEL_TREE * get_mm_parts(optimizer::RangeParameter *param,
235
static optimizer::SEL_TREE * get_mm_parts(optimizer::RangeParameter *param,
284
236
COND *cond_func,
285
237
Field *field,
286
238
Item_func::Functype type,
294
246
Item_func::Functype type,
295
247
Item *value);
296
248
297
static SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond);
249
static optimizer::SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond);
298
250
299
251
static bool is_key_scan_ror(optimizer::Parameter *param, uint32_t keynr, uint8_t nparts);
300
252
308
260
COST_VECT *cost);
309
261
310
262
static optimizer::RangeReadPlan *get_key_scans_params(optimizer::Parameter *param,
311
SEL_TREE *tree,
263
optimizer::SEL_TREE *tree,
312
264
bool index_read_must_be_used,
313
265
bool update_tbl_stats,
314
266
double read_time);
315
267
316
268
static
317
269
optimizer::RorIntersectReadPlan *get_best_ror_intersect(const optimizer::Parameter *param,
318
SEL_TREE *tree,
270
optimizer::SEL_TREE *tree,
319
271
double read_time,
320
272
bool *are_all_covering);
321
273
322
274
static
323
275
optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
324
SEL_TREE *tree,
276
optimizer::SEL_TREE *tree,
325
277
double read_time);
326
278
327
279
static
328
280
optimizer::TableReadPlan *get_best_disjunct_quick(optimizer::Parameter *param,
329
SEL_IMERGE *imerge,
281
optimizer::SEL_IMERGE *imerge,
330
282
double read_time);
331
283
332
284
static
333
optimizer::GroupMinMaxReadPlan *get_best_group_min_max(optimizer::Parameter *param, SEL_TREE *tree);
285
optimizer::GroupMinMaxReadPlan *get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree);
334
286
335
287
static void print_sel_tree(optimizer::Parameter *param,
336
SEL_TREE *tree,
288
optimizer::SEL_TREE *tree,
337
289
key_map *tree_map,
338
290
const char *msg);
339
291
340
static SEL_TREE *tree_and(optimizer::RangeParameter *param, SEL_TREE *tree1, SEL_TREE *tree2);
341
342
static SEL_TREE *tree_or(optimizer::RangeParameter *param, SEL_TREE *tree1, SEL_TREE *tree2);
292
static optimizer::SEL_TREE *tree_and(optimizer::RangeParameter *param,
293
optimizer::SEL_TREE *tree1,
294
optimizer::SEL_TREE *tree2);
343
295
344
296
static optimizer::SEL_ARG *sel_add(optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);
345
297
346
static optimizer::SEL_ARG *key_or(optimizer::RangeParameter *param, optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);
347
348
298
static optimizer::SEL_ARG *key_and(optimizer::RangeParameter *param,
349
299
optimizer::SEL_ARG *key1,
350
300
optimizer::SEL_ARG *key2,
352
302
353
303
static bool get_range(optimizer::SEL_ARG **e1, optimizer::SEL_ARG **e2, optimizer::SEL_ARG *root1);
354
304
355
static bool eq_tree(optimizer::SEL_ARG* a, optimizer::SEL_ARG *b);
356
357
305
optimizer::SEL_ARG optimizer::null_element(optimizer::SEL_ARG::IMPOSSIBLE);
358
306
359
307
static bool null_part_in_key(KEY_PART *key_part,
360
308
const unsigned char *key,
361
309
uint32_t length);
362
310
363
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, optimizer::RangeParameter *param);
364
365
366
/*
367
SEL_IMERGE is a list of possible ways to do index merge, i.e. it is
368
a condition in the following form:
369
(t_1||t_2||...||t_N) && (next)
370
371
where all t_i are SEL_TREEs, next is another SEL_IMERGE and no pair
372
(t_i,t_j) contains SEL_ARGS for the same index.
373
374
SEL_TREE contained in SEL_IMERGE always has merges=NULL.
375
376
This class relies on memory manager to do the cleanup.
377
*/
378
379
class SEL_IMERGE : public memory::SqlAlloc
380
{
381
enum { PREALLOCED_TREES= 10};
382
public:
383
SEL_TREE *trees_prealloced[PREALLOCED_TREES];
384
SEL_TREE **trees; /* trees used to do index_merge */
385
SEL_TREE **trees_next; /* last of these trees */
386
SEL_TREE **trees_end; /* end of allocated space */
387
388
optimizer::SEL_ARG ***best_keys; /* best keys to read in SEL_TREEs */
389
390
SEL_IMERGE() :
391
trees(&trees_prealloced[0]),
392
trees_next(trees),
393
trees_end(trees + PREALLOCED_TREES)
394
{}
395
int or_sel_tree(optimizer::RangeParameter *param, SEL_TREE *tree);
396
int or_sel_tree_with_checks(optimizer::RangeParameter *param, SEL_TREE *new_tree);
397
int or_sel_imerge_with_checks(optimizer::RangeParameter *param, SEL_IMERGE* imerge);
398
};
399
400
401
/*
402
Add SEL_TREE to this index_merge without any checks,
403
404
NOTES
405
This function implements the following:
406
(x_1||...||x_N) || t = (x_1||...||x_N||t), where x_i, t are SEL_TREEs
407
408
RETURN
409
0 - OK
410
-1 - Out of memory.
411
*/
412
int SEL_IMERGE::or_sel_tree(optimizer::RangeParameter *param, SEL_TREE *tree)
413
{
414
if (trees_next == trees_end)
415
{
416
const int realloc_ratio= 2; /* Double size for next round */
417
uint32_t old_elements= (trees_end - trees);
418
uint32_t old_size= sizeof(SEL_TREE**) * old_elements;
419
uint32_t new_size= old_size * realloc_ratio;
420
SEL_TREE **new_trees;
421
if (!(new_trees= (SEL_TREE**)alloc_root(param->mem_root, new_size)))
422
return -1;
423
memcpy(new_trees, trees, old_size);
424
trees= new_trees;
425
trees_next= trees + old_elements;
426
trees_end= trees + old_elements * realloc_ratio;
427
}
428
*(trees_next++)= tree;
429
return 0;
430
}
431
432
433
/*
434
Perform OR operation on this SEL_IMERGE and supplied SEL_TREE new_tree,
435
combining new_tree with one of the trees in this SEL_IMERGE if they both
436
have SEL_ARGs for the same key.
437
438
SYNOPSIS
439
or_sel_tree_with_checks()
440
param Parameter from SqlSelect::test_quick_select
441
new_tree SEL_TREE with type KEY or KEY_SMALLER.
442
443
NOTES
444
This does the following:
445
(t_1||...||t_k)||new_tree =
446
either
447
= (t_1||...||t_k||new_tree)
448
or
449
= (t_1||....||(t_j|| new_tree)||...||t_k),
450
451
where t_i, y are SEL_TREEs.
452
new_tree is combined with the first t_j it has a SEL_ARG on common
453
key with. As a consequence of this, choice of keys to do index_merge
454
read may depend on the order of conditions in WHERE part of the query.
455
456
RETURN
457
0 OK
458
1 One of the trees was combined with new_tree to SEL_TREE::ALWAYS,
459
and (*this) should be discarded.
460
-1 An error occurred.
461
*/
462
int SEL_IMERGE::or_sel_tree_with_checks(optimizer::RangeParameter *param, SEL_TREE *new_tree)
463
{
464
for (SEL_TREE** tree = trees;
465
tree != trees_next;
466
tree++)
467
{
468
if (sel_trees_can_be_ored(*tree, new_tree, param))
469
{
470
*tree = tree_or(param, *tree, new_tree);
471
if (!*tree)
472
return 1;
473
if (((*tree)->type == SEL_TREE::MAYBE) ||
474
((*tree)->type == SEL_TREE::ALWAYS))
475
return 1;
476
/* SEL_TREE::IMPOSSIBLE is impossible here */
477
return 0;
478
}
479
}
480
481
/* New tree cannot be combined with any of existing trees. */
482
return or_sel_tree(param, new_tree);
483
}
484
485
486
/*
487
Perform OR operation on this index_merge and supplied index_merge list.
488
489
RETURN
490
0 - OK
491
1 - One of conditions in result is always true and this SEL_IMERGE
492
should be discarded.
493
-1 - An error occurred
494
*/
495
496
int SEL_IMERGE::or_sel_imerge_with_checks(optimizer::RangeParameter *param, SEL_IMERGE* imerge)
497
{
498
for (SEL_TREE** tree= imerge->trees;
499
tree != imerge->trees_next;
500
tree++)
501
{
502
if (or_sel_tree_with_checks(param, *tree))
503
return 1;
504
}
505
return 0;
506
}
311
bool sel_trees_can_be_ored(optimizer::SEL_TREE *tree1,
312
optimizer::SEL_TREE *tree2,
313
optimizer::RangeParameter *param);
314
315
316
317
507
318
508
319
509
320
/*
510
321
Perform AND operation on two index_merge lists and store result in *im1.
511
322
*/
512
323
513
inline void imerge_list_and_list(List<SEL_IMERGE> *im1, List<SEL_IMERGE> *im2)
324
inline void imerge_list_and_list(List<optimizer::SEL_IMERGE> *im1, List<optimizer::SEL_IMERGE> *im2)
514
325
{
515
326
im1->concat(im2);
516
327
}
517
328
518
329
519
/*
520
Perform OR operation on 2 index_merge lists, storing result in first list.
521
522
NOTES
523
The following conversion is implemented:
524
(a_1 &&...&& a_N)||(b_1 &&...&& b_K) = AND_i,j(a_i || b_j) =>
525
=> (a_1||b_1).
526
527
i.e. all conjuncts except the first one are currently dropped.
528
This is done to avoid producing N*K ways to do index_merge.
529
530
If (a_1||b_1) produce a condition that is always true, NULL is returned
531
and index_merge is discarded (while it is actually possible to try
532
harder).
533
534
As a consequence of this, choice of keys to do index_merge read may depend
535
on the order of conditions in WHERE part of the query.
536
537
RETURN
538
0 OK, result is stored in *im1
539
other Error, both passed lists are unusable
540
*/
541
542
static int imerge_list_or_list(optimizer::RangeParameter *param,
543
List<SEL_IMERGE> *im1,
544
List<SEL_IMERGE> *im2)
545
{
546
SEL_IMERGE *imerge= im1->head();
547
im1->empty();
548
im1->push_back(imerge);
549
550
return imerge->or_sel_imerge_with_checks(param, im2->head());
551
}
552
553
554
/*
555
Perform OR operation on index_merge list and key tree.
556
557
RETURN
558
0 OK, result is stored in *im1.
559
other Error
560
*/
561
562
static int imerge_list_or_tree(optimizer::RangeParameter *param,
563
List<SEL_IMERGE> *im1,
564
SEL_TREE *tree)
565
{
566
SEL_IMERGE *imerge;
567
List_iterator<SEL_IMERGE> it(*im1);
568
while ((imerge= it++))
569
{
570
if (imerge->or_sel_tree_with_checks(param, tree))
571
it.remove();
572
}
573
return im1->is_empty();
574
}
575
576
577
330
/***************************************************************************
578
331
** Basic functions for SqlSelect and QuickRangeSelect
579
332
***************************************************************************/
913
666
if (keys_to_use.any())
914
667
{
915
668
memory::Root alloc;
916
SEL_TREE *tree= NULL;
669
optimizer::SEL_TREE *tree= NULL;
917
670
KEY_PART *key_parts;
918
671
KEY *key_info;
919
672
optimizer::Parameter param;
1001
754
{
1002
755
if ((tree= get_mm_tree(¶m,cond)))
1003
756
{
1004
if (tree->type == SEL_TREE::IMPOSSIBLE)
757
if (tree->type == optimizer::SEL_TREE::IMPOSSIBLE)
1005
758
{
1006
759
records=0L; /* Return -1 from this function. */
1007
760
read_time= (double) HA_POS_ERROR;
1011
764
If the tree can't be used for range scans, proceed anyway, as we
1012
765
can construct a group-min-max quick select
1013
766
*/
1014
if (tree->type != SEL_TREE::KEY && tree->type != SEL_TREE::KEY_SMALLER)
767
if (tree->type != optimizer::SEL_TREE::KEY && tree->type != optimizer::SEL_TREE::KEY_SMALLER)
1015
768
tree= NULL;
1016
769
}
1017
770
}
1082
835
else
1083
836
{
1084
837
/* Try creating index_merge/ROR-union scan. */
1085
SEL_IMERGE *imerge= NULL;
838
optimizer::SEL_IMERGE *imerge= NULL;
1086
839
optimizer::TableReadPlan *best_conj_trp= NULL;
1087
840
optimizer::TableReadPlan *new_conj_trp= NULL;
1088
List_iterator_fast<SEL_IMERGE> it(tree->merges);
841
List_iterator_fast<optimizer::SEL_IMERGE> it(tree->merges);
1089
842
while ((imerge= it++))
1090
843
{
1091
844
new_conj_trp= get_best_disjunct_quick(¶m, imerge, best_read_time);
1128
881
}
1129
882
1130
883
/*
1131
Get best plan for a SEL_IMERGE disjunctive expression.
884
Get best plan for a optimizer::SEL_IMERGE disjunctive expression.
1132
885
SYNOPSIS
1133
886
get_best_disjunct_quick()
1134
887
param Parameter from check_quick_select function
1194
947
1195
948
static
1196
949
optimizer::TableReadPlan *get_best_disjunct_quick(optimizer::Parameter *param,
1197
SEL_IMERGE *imerge,
950
optimizer::SEL_IMERGE *imerge,
1198
951
double read_time)
1199
952
{
1200
SEL_TREE **ptree;
953
optimizer::SEL_TREE **ptree= NULL;
1201
954
optimizer::IndexMergeReadPlan *imerge_trp= NULL;
1202
955
uint32_t n_child_scans= imerge->trees_next - imerge->trees;
1203
956
optimizer::RangeReadPlan **range_scans= NULL;
1230
983
ptree != imerge->trees_next;
1231
984
ptree++, cur_child++)
1232
985
{
1233
print_sel_tree(param, *ptree, &(*ptree)->keys_map, "tree in SEL_IMERGE");
986
print_sel_tree(param, *ptree, &(*ptree)->keys_map, "tree in optimizer::SEL_IMERGE");
1234
987
if (!(*cur_child= get_key_scans_params(param, *ptree, true, false, read_time)))
1235
988
{
1236
989
/*
1945
1698
1946
1699
static
1947
1700
optimizer::RorIntersectReadPlan *get_best_ror_intersect(const optimizer::Parameter *param,
1948
SEL_TREE *tree,
1701
optimizer::SEL_TREE *tree,
1949
1702
double read_time,
1950
1703
bool *are_all_covering)
1951
1704
{
2086
1839
SYNOPSIS
2087
1840
get_best_covering_ror_intersect()
2088
1841
param Parameter from test_quick_select function.
2089
tree SEL_TREE with sets of intervals for different keys.
1842
tree optimizer::SEL_TREE with sets of intervals for different keys.
2090
1843
read_time Don't return table read plans with cost > read_time.
2091
1844
2092
1845
RETURN
2116
1869
2117
1870
static
2118
1871
optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
2119
SEL_TREE *tree,
1872
optimizer::SEL_TREE *tree,
2120
1873
double read_time)
2121
1874
{
2122
1875
ROR_SCAN_INFO **ror_scan_mark;
2216
1969
2217
1970
2218
1971
/*
2219
Get best "range" table read plan for given SEL_TREE, also update some info
1972
Get best "range" table read plan for given optimizer::SEL_TREE, also update some info
2220
1973
2221
1974
SYNOPSIS
2222
1975
get_key_scans_params()
2223
1976
param Parameters from test_quick_select
2224
tree Make range select for this SEL_TREE
1977
tree Make range select for this optimizer::SEL_TREE
2225
1978
index_read_must_be_used true <=> assume 'index only' option will be set
2226
1979
(except for clustered PK indexes)
2227
1980
update_tbl_stats true <=> update table->quick_* with information
2230
1983
cost > read_time.
2231
1984
2232
1985
DESCRIPTION
2233
Find the best "range" table read plan for given SEL_TREE.
1986
Find the best "range" table read plan for given optimizer::SEL_TREE.
2234
1987
The side effects are
2235
1988
- tree->ror_scans is updated to indicate which scans are ROR scans.
2236
1989
- if update_tbl_stats=true then table->quick_* is updated with info
2242
1995
*/
2243
1996
2244
1997
static optimizer::RangeReadPlan *get_key_scans_params(optimizer::Parameter *param,
2245
SEL_TREE *tree,
1998
optimizer::SEL_TREE *tree,
2246
1999
bool index_read_must_be_used,
2247
2000
bool update_tbl_stats,
2248
2001
double read_time)
2256
2009
uint32_t best_buf_size= 0;
2257
2010
optimizer::RangeReadPlan *read_plan= NULL;
2258
2011
/*
2259
Note that there may be trees that have type SEL_TREE::KEY but contain no
2012
Note that there may be trees that have type optimizer::SEL_TREE::KEY but contain no
2260
2013
key reads at all, e.g. tree for expression "key1 is not null" where key1
2261
2014
is defined as "not null".
2262
2015
*/
2426
2179
2427
2180
2428
2181
/*
2429
Build a SEL_TREE for <> or NOT BETWEEN predicate
2182
Build a optimizer::SEL_TREE for <> or NOT BETWEEN predicate
2430
2183
2431
2184
SYNOPSIS
2432
2185
get_ne_mm_tree()
2441
2194
# Pointer to tree built tree
2442
2195
0 on error
2443
2196
*/
2444
static SEL_TREE *get_ne_mm_tree(optimizer::RangeParameter *param,
2197
static optimizer::SEL_TREE *get_ne_mm_tree(optimizer::RangeParameter *param,
2445
2198
Item_func *cond_func,
2446
2199
Field *field,
2447
2200
Item *lt_value, Item *gt_value,
2448
2201
Item_result cmp_type)
2449
2202
{
2450
SEL_TREE *tree;
2203
optimizer::SEL_TREE *tree= NULL;
2451
2204
tree= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
2452
2205
lt_value, cmp_type);
2453
2206
if (tree)
2464
2217
2465
2218
2466
2219
/*
2467
Build a SEL_TREE for a simple predicate
2220
Build a optimizer::SEL_TREE for a simple predicate
2468
2221
2469
2222
SYNOPSIS
2470
2223
get_func_mm_tree()
2479
2232
RETURN
2480
2233
Pointer to the tree built tree
2481
2234
*/
2482
static SEL_TREE *get_func_mm_tree(optimizer::RangeParameter *param,
2235
static optimizer::SEL_TREE *get_func_mm_tree(optimizer::RangeParameter *param,
2483
2236
Item_func *cond_func,
2484
2237
Field *field,
2485
2238
Item *value,
2486
2239
Item_result cmp_type,
2487
2240
bool inv)
2488
2241
{
2489
SEL_TREE *tree= NULL;
2242
optimizer::SEL_TREE *tree= NULL;
2490
2243
2491
2244
switch (cond_func->functype())
2492
2245
{
2558
2311
{
2559
2312
/*
2560
2313
We get here for conditions in form "t.key NOT IN (c1, c2, ...)",
2561
where c{i} are constants. Our goal is to produce a SEL_TREE that
2314
where c{i} are constants. Our goal is to produce a optimizer::SEL_TREE that
2562
2315
represents intervals:
2563
2316
2564
2317
($MIN<t.key<c1) OR (c1<t.key<c2) OR (c2<t.key<c3) OR ... (*)
2567
2320
2568
2321
The most straightforward way to produce it is to convert NOT IN
2569
2322
into "(t.key != c1) AND (t.key != c2) AND ... " and let the range
2570
analyzer to build SEL_TREE from that. The problem is that the
2323
analyzer to build optimizer::SEL_TREE from that. The problem is that the
2571
2324
range analyzer will use O(N^2) memory (which is probably a bug),
2572
2325
and people do use big NOT IN lists (e.g. see BUG#15872, BUG#21282),
2573
2326
will run out of memory.
2580
2333
2581
2334
Considering the above, we'll handle NOT IN as follows:
2582
2335
* if the number of entries in the NOT IN list is less than
2583
NOT_IN_IGNORE_THRESHOLD, construct the SEL_TREE (*) manually.
2584
* Otherwise, don't produce a SEL_TREE.
2336
NOT_IN_IGNORE_THRESHOLD, construct the optimizer::SEL_TREE (*) manually.
2337
* Otherwise, don't produce a optimizer::SEL_TREE.
2585
2338
*/
2586
2339
#define NOT_IN_IGNORE_THRESHOLD 1000
2587
2340
memory::Root *tmp_root= param->mem_root;
2600
2353
if (func->array->count > NOT_IN_IGNORE_THRESHOLD || ! value_item)
2601
2354
break;
2602
2355
2603
/* Get a SEL_TREE for "(-inf|NULL) < X < c_0" interval. */
2356
/* Get a optimizer::SEL_TREE for "(-inf|NULL) < X < c_0" interval. */
2604
2357
uint32_t i=0;
2605
2358
do
2606
2359
{
2613
2366
if (! tree)
2614
2367
break;
2615
2368
i++;
2616
} while (i < func->array->count && tree->type == SEL_TREE::IMPOSSIBLE);
2369
} while (i < func->array->count && tree->type == optimizer::SEL_TREE::IMPOSSIBLE);
2617
2370
2618
if (!tree || tree->type == SEL_TREE::IMPOSSIBLE)
2371
if (!tree || tree->type == optimizer::SEL_TREE::IMPOSSIBLE)
2619
2372
{
2620
2373
/* We get here in cases like "t.unsigned NOT IN (-1,-2,-3) */
2621
2374
tree= NULL;
2622
2375
break;
2623
2376
}
2624
SEL_TREE *tree2;
2377
optimizer::SEL_TREE *tree2= NULL;
2625
2378
for (; i < func->array->count; i++)
2626
2379
{
2627
2380
if (func->array->compare_elems(i, i-1))
2628
2381
{
2629
/* Get a SEL_TREE for "-inf < X < c_i" interval */
2382
/* Get a optimizer::SEL_TREE for "-inf < X < c_i" interval */
2630
2383
func->array->value_to_item(i, value_item);
2631
2384
tree2= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
2632
2385
value_item, cmp_type);
2656
2409
}
2657
2410
}
2658
2411
2659
if (tree && tree->type != SEL_TREE::IMPOSSIBLE)
2412
if (tree && tree->type != optimizer::SEL_TREE::IMPOSSIBLE)
2660
2413
{
2661
2414
/*
2662
Get the SEL_TREE for the last "c_last < X < +inf" interval
2415
Get the optimizer::SEL_TREE for the last "c_last < X < +inf" interval
2663
2416
(value_item cotains c_last already)
2664
2417
*/
2665
2418
tree2= get_mm_parts(param, cond_func, field, Item_func::GT_FUNC,
2723
2476
2724
2477
2725
2478
/*
2726
Build conjunction of all SEL_TREEs for a simple predicate applying equalities
2479
Build conjunction of all optimizer::SEL_TREEs for a simple predicate applying equalities
2727
2480
2728
2481
SYNOPSIS
2729
2482
get_full_func_mm_tree()
2738
2491
2739
2492
DESCRIPTION
2740
2493
For a simple SARGable predicate of the form (f op c), where f is a field and
2741
c is a constant, the function builds a conjunction of all SEL_TREES that can
2494
c is a constant, the function builds a conjunction of all optimizer::SEL_TREES that can
2742
2495
be obtained by the substitution of f for all different fields equal to f.
2743
2496
2744
2497
NOTES
2748
2501
each fj belonging to the same multiple equality as fi
2749
2502
are built as well.
2750
2503
E.g. for WHERE t1.a=t2.a AND t2.a > 10
2751
a SEL_TREE for t2.a > 10 will be built for quick select from t2
2504
a optimizer::SEL_TREE for t2.a > 10 will be built for quick select from t2
2752
2505
and
2753
a SEL_TREE for t1.a > 10 will be built for quick select from t1.
2506
a optimizer::SEL_TREE for t1.a > 10 will be built for quick select from t1.
2754
2507
2755
2508
A BETWEEN predicate of the form (fi [NOT] BETWEEN c1 AND c2) is treated
2756
2509
in a similar way: we build a conjuction of trees for the results
2789
2542
the form (c IN (c1,...,f,...,cn)).
2790
2543
2791
2544
RETURN
2792
Pointer to the tree representing the built conjunction of SEL_TREEs
2545
Pointer to the tree representing the built conjunction of optimizer::SEL_TREEs
2793
2546
*/
2794
2547
2795
static SEL_TREE *get_full_func_mm_tree(optimizer::RangeParameter *param,
2548
static optimizer::SEL_TREE *get_full_func_mm_tree(optimizer::RangeParameter *param,
2796
2549
Item_func *cond_func,
2797
2550
Item_field *field_item, Item *value,
2798
2551
bool inv)
2799
2552
{
2800
SEL_TREE *tree= 0;
2801
SEL_TREE *ftree= 0;
2553
optimizer::SEL_TREE *tree= 0;
2554
optimizer::SEL_TREE *ftree= 0;
2802
2555
table_map ref_tables= 0;
2803
2556
table_map param_comp= ~(param->prev_tables | param->read_tables |
2804
2557
param->current_table);
2840
2593
2841
2594
/* make a select tree of all keys in condition */
2842
2595
2843
static SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond)
2596
static optimizer::SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond)
2844
2597
{
2845
SEL_TREE *tree=0;
2846
SEL_TREE *ftree= 0;
2598
optimizer::SEL_TREE *tree=0;
2599
optimizer::SEL_TREE *ftree= 0;
2847
2600
Item_field *field_item= 0;
2848
2601
bool inv= false;
2849
2602
Item *value= 0;
2858
2611
Item *item;
2859
2612
while ((item=li++))
2860
2613
{
2861
SEL_TREE *new_tree= get_mm_tree(param,item);
2614
optimizer::SEL_TREE *new_tree= get_mm_tree(param,item);
2862
2615
if (param->session->is_fatal_error ||
2863
2616
param->alloced_sel_args > optimizer::SEL_ARG::MAX_SEL_ARGS)
2864
2617
return 0; // out of memory
2865
2618
tree=tree_and(param,tree,new_tree);
2866
if (tree && tree->type == SEL_TREE::IMPOSSIBLE)
2619
if (tree && tree->type == optimizer::SEL_TREE::IMPOSSIBLE)
2867
2620
break;
2868
2621
}
2869
2622
}
2875
2628
Item *item;
2876
2629
while ((item=li++))
2877
2630
{
2878
SEL_TREE *new_tree= get_mm_tree(param,item);
2631
optimizer::SEL_TREE *new_tree= get_mm_tree(param,item);
2879
2632
if (!new_tree)
2880
2633
return 0; // out of memory
2881
2634
tree=tree_or(param,tree,new_tree);
2882
if (!tree || tree->type == SEL_TREE::ALWAYS)
2635
if (!tree || tree->type == optimizer::SEL_TREE::ALWAYS)
2883
2636
break;
2884
2637
}
2885
2638
}
2897
2650
*/
2898
2651
memory::Root *tmp_root= param->mem_root;
2899
2652
param->session->mem_root= param->old_root;
2900
tree= cond->val_int() ? new(tmp_root) SEL_TREE(SEL_TREE::ALWAYS) :
2901
new(tmp_root) SEL_TREE(SEL_TREE::IMPOSSIBLE);
2653
tree= cond->val_int() ? new(tmp_root) optimizer::SEL_TREE(optimizer::SEL_TREE::ALWAYS) :
2654
new(tmp_root) optimizer::SEL_TREE(optimizer::SEL_TREE::IMPOSSIBLE);
2902
2655
param->session->mem_root= tmp_root;
2903
2656
return(tree);
2904
2657
}
2912
2665
if ((ref_tables & param->current_table) ||
2913
2666
(ref_tables & ~(param->prev_tables | param->read_tables)))
2914
2667
return 0;
2915
return(new SEL_TREE(SEL_TREE::MAYBE));
2668
return(new optimizer::SEL_TREE(optimizer::SEL_TREE::MAYBE));
2916
2669
}
2917
2670
2918
2671
Item_func *cond_func= (Item_func*) cond;
2941
2694
if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM)
2942
2695
{
2943
2696
field_item= (Item_field*) (cond_func->arguments()[i]->real_item());
2944
SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func,
2697
optimizer::SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func,
2945
2698
field_item, (Item*)(intptr_t)i, inv);
2946
2699
if (inv)
2947
2700
tree= !tree ? tmp : tree_or(param, tree, tmp);
3011
2764
}
3012
2765
3013
2766
3014
static SEL_TREE *
2767
static optimizer::SEL_TREE *
3015
2768
get_mm_parts(optimizer::RangeParameter *param,
3016
2769
COND *cond_func,
3017
2770
Field *field,
3023
2776
3024
2777
KEY_PART *key_part = param->key_parts;
3025
2778
KEY_PART *end = param->key_parts_end;
3026
SEL_TREE *tree=0;
2779
optimizer::SEL_TREE *tree=0;
3027
2780
if (value &&
3028
2781
value->used_tables() & ~(param->prev_tables | param->read_tables))
3029
2782
return 0;
3032
2785
if (field->eq(key_part->field))
3033
2786
{
3034
2787
optimizer::SEL_ARG *sel_arg=0;
3035
if (!tree && !(tree=new SEL_TREE()))
2788
if (!tree && !(tree=new optimizer::SEL_TREE()))
3036
2789
return 0; // OOM
3037
2790
if (!value || !(value->used_tables() & ~param->read_tables))
3038
2791
{
3042
2795
continue;
3043
2796
if (sel_arg->type == optimizer::SEL_ARG::IMPOSSIBLE)
3044
2797
{
3045
tree->type=SEL_TREE::IMPOSSIBLE;
2798
tree->type=optimizer::SEL_TREE::IMPOSSIBLE;
3046
2799
return(tree);
3047
2800
}
3048
2801
}
3529
3282
#define swap_clone_flag(A) ((A & 1) << 1) | ((A & 2) >> 1)
3530
3283
3531
3284
3532
static SEL_TREE *
3533
tree_and(optimizer::RangeParameter *param, SEL_TREE *tree1, SEL_TREE *tree2)
3285
static optimizer::SEL_TREE *
3286
tree_and(optimizer::RangeParameter *param, optimizer::SEL_TREE *tree1, optimizer::SEL_TREE *tree2)
3534
3287
{
3535
3288
if (!tree1)
3536
3289
return(tree2);
3537
3290
if (!tree2)
3538
3291
return(tree1);
3539
if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
3292
if (tree1->type == optimizer::SEL_TREE::IMPOSSIBLE || tree2->type == optimizer::SEL_TREE::ALWAYS)
3540
3293
return(tree1);
3541
if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
3294
if (tree2->type == optimizer::SEL_TREE::IMPOSSIBLE || tree1->type == optimizer::SEL_TREE::ALWAYS)
3542
3295
return(tree2);
3543
if (tree1->type == SEL_TREE::MAYBE)
3296
if (tree1->type == optimizer::SEL_TREE::MAYBE)
3544
3297
{
3545
if (tree2->type == SEL_TREE::KEY)
3546
tree2->type=SEL_TREE::KEY_SMALLER;
3298
if (tree2->type == optimizer::SEL_TREE::KEY)
3299
tree2->type=optimizer::SEL_TREE::KEY_SMALLER;
3547
3300
return(tree2);
3548
3301
}
3549
if (tree2->type == SEL_TREE::MAYBE)
3302
if (tree2->type == optimizer::SEL_TREE::MAYBE)
3550
3303
{
3551
tree1->type=SEL_TREE::KEY_SMALLER;
3304
tree1->type=optimizer::SEL_TREE::KEY_SMALLER;
3552
3305
return(tree1);
3553
3306
}
3554
3307
key_map result_keys;
3569
3322
*key1=key_and(param, *key1, *key2, flag);
3570
3323
if (*key1 && (*key1)->type == optimizer::SEL_ARG::IMPOSSIBLE)
3571
3324
{
3572
tree1->type= SEL_TREE::IMPOSSIBLE;
3325
tree1->type= optimizer::SEL_TREE::IMPOSSIBLE;
3573
3326
return(tree1);
3574
3327
}
3575
3328
result_keys.set(key1 - tree1->keys);
3589
3342
}
3590
3343
3591
3344
3592
/*
3593
Check if two SEL_TREES can be combined into one (i.e. a single key range
3594
read can be constructed for "cond_of_tree1 OR cond_of_tree2" ) without
3595
using index_merge.
3596
*/
3597
3598
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2,
3599
optimizer::RangeParameter* param)
3600
{
3601
key_map common_keys= tree1->keys_map;
3602
common_keys&= tree2->keys_map;
3603
3604
if (common_keys.none())
3605
return false;
3606
3607
/* trees have a common key, check if they refer to same key part */
3608
optimizer::SEL_ARG **key1,**key2;
3609
for (uint32_t key_no=0; key_no < param->keys; key_no++)
3610
{
3611
if (common_keys.test(key_no))
3612
{
3613
key1= tree1->keys + key_no;
3614
key2= tree2->keys + key_no;
3615
if ((*key1)->part == (*key2)->part)
3616
{
3617
return true;
3618
}
3619
}
3620
}
3621
return false;
3622
}
3623
3624
3625
/*
3626
Remove the trees that are not suitable for record retrieval.
3627
SYNOPSIS
3628
param Range analysis parameter
3629
tree Tree to be processed, tree->type is KEY or KEY_SMALLER
3630
3631
DESCRIPTION
3632
This function walks through tree->keys[] and removes the SEL_ARG* trees
3633
that are not "maybe" trees (*) and cannot be used to construct quick range
3634
selects.
3635
(*) - have type MAYBE or MAYBE_KEY. Perhaps we should remove trees of
3636
these types here as well.
3637
3638
A SEL_ARG* tree cannot be used to construct quick select if it has
3639
tree->part != 0. (e.g. it could represent "keypart2 < const").
3640
3641
WHY THIS FUNCTION IS NEEDED
3642
3643
Normally we allow construction of SEL_TREE objects that have SEL_ARG
3644
trees that do not allow quick range select construction. For example for
3645
" keypart1=1 AND keypart2=2 " the execution will proceed as follows:
3646
tree1= SEL_TREE { SEL_ARG{keypart1=1} }
3647
tree2= SEL_TREE { SEL_ARG{keypart2=2} } -- can't make quick range select
3648
from this
3649
call tree_and(tree1, tree2) -- this joins SEL_ARGs into a usable SEL_ARG
3650
tree.
3651
3652
There is an exception though: when we construct index_merge SEL_TREE,
3653
any SEL_ARG* tree that cannot be used to construct quick range select can
3654
be removed, because current range analysis code doesn't provide any way
3655
that tree could be later combined with another tree.
3656
Consider an example: we should not construct
3657
st1 = SEL_TREE {
3658
merges = SEL_IMERGE {
3659
SEL_TREE(t.key1part1 = 1),
3660
SEL_TREE(t.key2part2 = 2) -- (*)
3661
}
3662
};
3663
because
3664
- (*) cannot be used to construct quick range select,
3665
- There is no execution path that would cause (*) to be converted to
3666
a tree that could be used.
3667
3668
The latter is easy to verify: first, notice that the only way to convert
3669
(*) into a usable tree is to call tree_and(something, (*)).
3670
3671
Second look at what tree_and/tree_or function would do when passed a
3672
SEL_TREE that has the structure like st1 tree has, and conlcude that
3673
tree_and(something, (*)) will not be called.
3674
3675
RETURN
3676
0 Ok, some suitable trees left
3677
1 No tree->keys[] left.
3678
*/
3679
3680
static bool remove_nonrange_trees(optimizer::RangeParameter *param, SEL_TREE *tree)
3681
{
3682
bool res= false;
3683
for (uint32_t i=0; i < param->keys; i++)
3684
{
3685
if (tree->keys[i])
3686
{
3687
if (tree->keys[i]->part)
3688
{
3689
tree->keys[i]= NULL;
3690
tree->keys_map.reset(i);
3691
}
3692
else
3693
res= true;
3694
}
3695
}
3696
return !res;
3697
}
3698
3699
3700
static SEL_TREE *
3701
tree_or(optimizer::RangeParameter *param,SEL_TREE *tree1,SEL_TREE *tree2)
3702
{
3703
if (!tree1 || !tree2)
3704
return 0;
3705
if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
3706
return(tree2);
3707
if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
3708
return(tree1);
3709
if (tree1->type == SEL_TREE::MAYBE)
3710
return(tree1); // Can't use this
3711
if (tree2->type == SEL_TREE::MAYBE)
3712
return(tree2);
3713
3714
SEL_TREE *result= 0;
3715
key_map result_keys;
3716
result_keys.reset();
3717
if (sel_trees_can_be_ored(tree1, tree2, param))
3718
{
3719
/* Join the trees key per key */
3720
optimizer::SEL_ARG **key1,**key2,**end;
3721
for (key1= tree1->keys,key2= tree2->keys,end= key1+param->keys ;
3722
key1 != end ; key1++,key2++)
3723
{
3724
*key1=key_or(param, *key1, *key2);
3725
if (*key1)
3726
{
3727
result=tree1; // Added to tree1
3728
result_keys.set(key1 - tree1->keys);
3729
}
3730
}
3731
if (result)
3732
result->keys_map= result_keys;
3733
}
3734
else
3735
{
3736
/* ok, two trees have KEY type but cannot be used without index merge */
3737
if (tree1->merges.is_empty() && tree2->merges.is_empty())
3738
{
3739
if (param->remove_jump_scans)
3740
{
3741
bool no_trees= remove_nonrange_trees(param, tree1);
3742
no_trees= no_trees || remove_nonrange_trees(param, tree2);
3743
if (no_trees)
3744
return(new SEL_TREE(SEL_TREE::ALWAYS));
3745
}
3746
SEL_IMERGE *merge;
3747
/* both trees are "range" trees, produce new index merge structure */
3748
if (!(result= new SEL_TREE()) || !(merge= new SEL_IMERGE()) ||
3749
(result->merges.push_back(merge)) ||
3750
(merge->or_sel_tree(param, tree1)) ||
3751
(merge->or_sel_tree(param, tree2)))
3752
result= NULL;
3753
else
3754
result->type= tree1->type;
3755
}
3756
else if (!tree1->merges.is_empty() && !tree2->merges.is_empty())
3757
{
3758
if (imerge_list_or_list(param, &tree1->merges, &tree2->merges))
3759
result= new SEL_TREE(SEL_TREE::ALWAYS);
3760
else
3761
result= tree1;
3762
}
3763
else
3764
{
3765
/* one tree is index merge tree and another is range tree */
3766
if (tree1->merges.is_empty())
3767
std::swap(tree1, tree2);
3768
3769
if (param->remove_jump_scans && remove_nonrange_trees(param, tree2))
3770
return(new SEL_TREE(SEL_TREE::ALWAYS));
3771
/* add tree2 to tree1->merges, checking if it collapses to ALWAYS */
3772
if (imerge_list_or_tree(param, &tree1->merges, tree2))
3773
result= new SEL_TREE(SEL_TREE::ALWAYS);
3774
else
3775
result= tree1;
3776
}
3777
}
3778
return result;
3779
}
3780
3781
3345
3782
3346
/* And key trees where key1->part < key2 -> part */
3783
3347
3974
3538
}
3975
3539
3976
3540
3977
static optimizer::SEL_ARG *
3978
key_or(optimizer::RangeParameter *param, optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2)
3979
{
3980
if (! key1)
3981
{
3982
if (key2)
3983
{
3984
key2->use_count--;
3985
key2->free_tree();
3986
}
3987
return 0;
3988
}
3989
if (! key2)
3990
{
3991
key1->use_count--;
3992
key1->free_tree();
3993
return 0;
3994
}
3995
key1->use_count--;
3996
key2->use_count--;
3997
3998
if (key1->part != key2->part)
3999
{
4000
key1->free_tree();
4001
key2->free_tree();
4002
return 0; // Can't optimize this
4003
}
4004
4005
// If one of the key is MAYBE_KEY then the found region may be bigger
4006
if (key1->type == optimizer::SEL_ARG::MAYBE_KEY)
4007
{
4008
key2->free_tree();
4009
key1->use_count++;
4010
return key1;
4011
}
4012
if (key2->type == optimizer::SEL_ARG::MAYBE_KEY)
4013
{
4014
key1->free_tree();
4015
key2->use_count++;
4016
return key2;
4017
}
4018
4019
if (key1->use_count > 0)
4020
{
4021
if (key2->use_count == 0 || key1->elements > key2->elements)
4022
{
4023
std::swap(key1,key2);
4024
}
4025
if (key1->use_count > 0 || !(key1=key1->clone_tree(param)))
4026
return 0; // OOM
4027
}
4028
4029
// Add tree at key2 to tree at key1
4030
bool key2_shared= key2->use_count != 0;
4031
key1->maybe_flag|= key2->maybe_flag;
4032
4033
for (key2=key2->first(); key2; )
4034
{
4035
optimizer::SEL_ARG *tmp= key1->find_range(key2); // Find key1.min <= key2.min
4036
int cmp;
4037
4038
if (! tmp)
4039
{
4040
tmp=key1->first(); // tmp.min > key2.min
4041
cmp= -1;
4042
}
4043
else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
4044
{ // Found tmp.max < key2.min
4045
optimizer::SEL_ARG *next= tmp->next;
4046
if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part))
4047
{
4048
// Join near ranges like tmp.max < 0 and key2.min >= 0
4049
optimizer::SEL_ARG *key2_next=key2->next;
4050
if (key2_shared)
4051
{
4052
if (! (key2=new optimizer::SEL_ARG(*key2)))
4053
return 0; // out of memory
4054
key2->increment_use_count(key1->use_count+1);
4055
key2->next= key2_next; // New copy of key2
4056
}
4057
key2->copy_min(tmp);
4058
if (! (key1=key1->tree_delete(tmp)))
4059
{ // Only one key in tree
4060
key1= key2;
4061
key1->make_root();
4062
key2= key2_next;
4063
break;
4064
}
4065
}
4066
if (! (tmp= next)) // tmp.min > key2.min
4067
break; // Copy rest of key2
4068
}
4069
if (cmp < 0)
4070
{ // tmp.min > key2.min
4071
int tmp_cmp;
4072
if ((tmp_cmp= tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max
4073
{
4074
if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
4075
{ // ranges are connected
4076
tmp->copy_min_to_min(key2);
4077
key1->merge_flags(key2);
4078
if (tmp->min_flag & NO_MIN_RANGE &&
4079
tmp->max_flag & NO_MAX_RANGE)
4080
{
4081
if (key1->maybe_flag)
4082
return new optimizer::SEL_ARG(optimizer::SEL_ARG::MAYBE_KEY);
4083
return 0;
4084
}
4085
key2->increment_use_count(-1); // Free not used tree
4086
key2= key2->next;
4087
continue;
4088
}
4089
else
4090
{
4091
optimizer::SEL_ARG *next= key2->next; // Keys are not overlapping
4092
if (key2_shared)
4093
{
4094
optimizer::SEL_ARG *cpy= new optimizer::SEL_ARG(*key2); // Must make copy
4095
if (! cpy)
4096
return 0; // OOM
4097
key1= key1->insert(cpy);
4098
key2->increment_use_count(key1->use_count+1);
4099
}
4100
else
4101
key1= key1->insert(key2); // Will destroy key2_root
4102
key2= next;
4103
continue;
4104
}
4105
}
4106
}
4107
4108
// tmp.max >= key2.min && tmp.min <= key.cmax(overlapping ranges)
4109
if (eq_tree(tmp->next_key_part,key2->next_key_part))
4110
{
4111
if (tmp->is_same(key2))
4112
{
4113
tmp->merge_flags(key2); // Copy maybe flags
4114
key2->increment_use_count(-1); // Free not used tree
4115
}
4116
else
4117
{
4118
optimizer::SEL_ARG *last= tmp;
4119
while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
4120
eq_tree(last->next->next_key_part,key2->next_key_part))
4121
{
4122
optimizer::SEL_ARG *save= last;
4123
last= last->next;
4124
key1= key1->tree_delete(save);
4125
}
4126
last->copy_min(tmp);
4127
if (last->copy_min(key2) || last->copy_max(key2))
4128
{ // Full range
4129
key1->free_tree();
4130
for (; key2; key2= key2->next)
4131
key2->increment_use_count(-1); // Free not used tree
4132
if (key1->maybe_flag)
4133
return new optimizer::SEL_ARG(optimizer::SEL_ARG::MAYBE_KEY);
4134
return 0;
4135
}
4136
}
4137
key2= key2->next;
4138
continue;
4139
}
4140
4141
if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
4142
{ // tmp.min <= x < key2.min
4143
optimizer::SEL_ARG *new_arg= tmp->clone_first(key2);
4144
if (! new_arg)
4145
return 0; // OOM
4146
if ((new_arg->next_key_part= key1->next_key_part))
4147
new_arg->increment_use_count(key1->use_count+1);
4148
tmp->copy_min_to_min(key2);
4149
key1= key1->insert(new_arg);
4150
}
4151
4152
// tmp.min >= key2.min && tmp.min <= key2.max
4153
optimizer::SEL_ARG key(*key2); // Get copy we can modify
4154
for (;;)
4155
{
4156
if (tmp->cmp_min_to_min(&key) > 0)
4157
{ // key.min <= x < tmp.min
4158
optimizer::SEL_ARG *new_arg= key.clone_first(tmp);
4159
if (! new_arg)
4160
return 0; // OOM
4161
if ((new_arg->next_key_part=key.next_key_part))
4162
new_arg->increment_use_count(key1->use_count+1);
4163
key1= key1->insert(new_arg);
4164
}
4165
if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
4166
{ // tmp.min. <= x <= tmp.max
4167
tmp->maybe_flag|= key.maybe_flag;
4168
key.increment_use_count(key1->use_count+1);
4169
tmp->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
4170
if (! cmp) // Key2 is ready
4171
break;
4172
key.copy_max_to_min(tmp);
4173
if (! (tmp= tmp->next))
4174
{
4175
optimizer::SEL_ARG *tmp2= new optimizer::SEL_ARG(key);
4176
if (! tmp2)
4177
return 0; // OOM
4178
key1= key1->insert(tmp2);
4179
key2= key2->next;
4180
goto end;
4181
}
4182
if (tmp->cmp_min_to_max(&key) > 0)
4183
{
4184
optimizer::SEL_ARG *tmp2= new optimizer::SEL_ARG(key);
4185
if (! tmp2)
4186
return 0; // OOM
4187
key1= key1->insert(tmp2);
4188
break;
4189
}
4190
}
4191
else
4192
{
4193
optimizer::SEL_ARG *new_arg= tmp->clone_last(&key); // tmp.min <= x <= key.max
4194
if (! new_arg)
4195
return 0; // OOM
4196
tmp->copy_max_to_min(&key);
4197
tmp->increment_use_count(key1->use_count+1);
4198
/* Increment key count as it may be used for next loop */
4199
key.increment_use_count(1);
4200
new_arg->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
4201
key1= key1->insert(new_arg);
4202
break;
4203
}
4204
}
4205
key2= key2->next;
4206
}
4207
4208
end:
4209
while (key2)
4210
{
4211
optimizer::SEL_ARG *next= key2->next;
4212
if (key2_shared)
4213
{
4214
optimizer::SEL_ARG *tmp= new optimizer::SEL_ARG(*key2); // Must make copy
4215
if (! tmp)
4216
return 0;
4217
key2->increment_use_count(key1->use_count+1);
4218
key1= key1->insert(tmp);
4219
}
4220
else
4221
key1= key1->insert(key2); // Will destroy key2_root
4222
key2= next;
4223
}
4224
key1->use_count++;
4225
return key1;
4226
}
4227
4228
4229
/* Compare if two trees are equal */
4230
static bool eq_tree(optimizer::SEL_ARG *a, optimizer::SEL_ARG *b)
4231
{
4232
if (a == b)
4233
{
4234
return true;
4235
}
4236
4237
if (! a || ! b || ! a->is_same(b))
4238
{
4239
return false;
4240
}
4241
4242
if (a->left != &optimizer::null_element && b->left != &optimizer::null_element)
4243
{
4244
if (! eq_tree(a->left,b->left))
4245
return false;
4246
}
4247
else if (a->left != &optimizer::null_element || b->left != &optimizer::null_element)
4248
{
4249
return false;
4250
}
4251
4252
if (a->right != &optimizer::null_element && b->right != &optimizer::null_element)
4253
{
4254
if (! eq_tree(a->right,b->right))
4255
return false;
4256
}
4257
else if (a->right != &optimizer::null_element || b->right != &optimizer::null_element)
4258
{
4259
return false;
4260
}
4261
4262
if (a->next_key_part != b->next_key_part)
4263
{ // Sub range
4264
if (! a->next_key_part != ! b->next_key_part ||
4265
! eq_tree(a->next_key_part, b->next_key_part))
4266
return false;
4267
}
4268
4269
return true;
4270
}
4271
4272
4273
3541
/****************************************************************************
4274
3542
MRR Range Sequence Interface implementation that walks a SEL_ARG* tree.
4275
3543
****************************************************************************/
4300
3568
*/
4301
3569
typedef struct st_sel_arg_range_seq
4302
3570
{
4303
uint32_t keyno; /* index of used tree in SEL_TREE structure */
3571
uint32_t keyno; /* index of used tree in optimizer::SEL_TREE structure */
4304
3572
uint32_t real_keyno; /* Number of the index in tables */
4305
3573
optimizer::Parameter *param;
4306
3574
optimizer::SEL_ARG *start; /* Root node of the traversed SEL_ARG* graph */
4542
3810
SYNOPSIS
4543
3811
check_quick_select()
4544
3812
param Parameter from test_quick_select
4545
idx Number of index to use in Parameter::key SEL_TREE::key
3813
idx Number of index to use in Parameter::key optimizer::SEL_TREE::key
4546
3814
index_only true - assume only index tuples will be accessed
4547
3815
false - assume full table rows will be read
4548
3816
tree Transformed selection condition, tree->key[idx] holds
5156
4424
static inline uint32_t get_field_keypart(KEY *index, Field *field);
5157
4425
5158
4426
static inline optimizer::SEL_ARG * get_index_range_tree(uint32_t index,
5159
SEL_TREE *range_tree,
4427
optimizer::SEL_TREE *range_tree,
5160
4428
optimizer::Parameter *param,
5161
4429
uint32_t *param_idx);
5162
4430
5177
4445
KEY *index_info,
5178
4446
uint32_t used_key_parts,
5179
4447
uint32_t group_key_parts,
5180
SEL_TREE *range_tree,
4448
optimizer::SEL_TREE *range_tree,
5181
4449
optimizer::SEL_ARG *index_tree,
5182
4450
ha_rows quick_prefix_records,
5183
4451
bool have_min,
5314
4582
- NULL
5315
4583
*/
5316
4584
static optimizer::GroupMinMaxReadPlan *
5317
get_best_group_min_max(optimizer::Parameter *param, SEL_TREE *tree)
4585
get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree)
5318
4586
{
5319
4587
Session *session= param->session;
5320
4588
JOIN *join= session->lex->current_select->join;
6028
5296
6029
5297
DESCRIPTION
6030
5298
6031
A SEL_TREE contains range trees for all usable indexes. This procedure
6032
finds the SEL_ARG sub-tree for 'index'. The members of a SEL_TREE are
5299
A optimizer::SEL_TREE contains range trees for all usable indexes. This procedure
5300
finds the SEL_ARG sub-tree for 'index'. The members of a optimizer::SEL_TREE are
6033
5301
ordered in the same way as the members of Parameter::key, thus we first find
6034
5302
the corresponding index in the array Parameter::key. This index is returned
6035
5303
through the variable param_idx, to be used later as argument of
6039
5307
Pointer to the SEL_ARG subtree that corresponds to index.
6040
5308
*/
6041
5309
optimizer::SEL_ARG *get_index_range_tree(uint32_t index,
6042
SEL_TREE* range_tree,
5310
optimizer::SEL_TREE* range_tree,
6043
5311
optimizer::Parameter *param,
6044
5312
uint32_t *param_idx)
6045
5313
{
6118
5386
KEY *index_info,
6119
5387
uint32_t used_key_parts,
6120
5388
uint32_t group_key_parts,
6121
SEL_TREE *range_tree,
5389
optimizer::SEL_TREE *range_tree,
6122
5390
optimizer::SEL_ARG *,
6123
5391
ha_rows quick_prefix_records,
6124
5392
bool have_min,
6320
5588
}
6321
5589
6322
5590
6323
static void print_sel_tree(optimizer::Parameter *param, SEL_TREE *tree, key_map *tree_map, const char *)
5591
static void print_sel_tree(optimizer::Parameter *param, optimizer::SEL_TREE *tree, key_map *tree_map, const char *)
6324
5592
{
6325
5593
optimizer::SEL_ARG **key= NULL;
6326
5594
optimizer::SEL_ARG **end= NULL;
Loggerhead is a web-based interface for Breezy
Version: 2.0.1