« back to all changes in this revision
Viewing changes to drizzled/optimizer/range.cc
- browse files at revision 1337.4.8
- compare with another revision
- compare with revision 2306
- download diff
- download tarball
- view history from revision 1337.4.8
- Committer: Eric Day
- Date: 2010-03-19 22:57:47 UTC
- mfrom: (1337.5.4 mysql-protocol-password-udf)
- mto: This revision was merged to the branch mainline in revision 1409.
- Revision ID: eday@oddments.org-20100319225747-1zst3vzjvm2d3r1y
Merged trunk and mysql-protocol-password-udf changes.
- files added:
- drizzled/optimizer/sel_imerge.cc
- plugin/information_schema_dictionary
- plugin/information_schema_dictionary/tests
- plugin/information_schema_dictionary/tests/r
- plugin/information_schema_dictionary/tests/t
- plugin/mysql_protocol/prototest
- plugin/mysql_protocol/prototest/prototest
- plugin/mysql_protocol/prototest/prototest/mysql
- plugin/mysql_protocol/tests
- plugin/mysql_protocol/tests/r
- plugin/mysql_protocol/tests/t
- plugin/table_cache_dictionary
- plugin/table_cache_dictionary/tests
- plugin/table_cache_dictionary/tests/r
- plugin/table_cache_dictionary/tests/t
- files removed:
- plugin/mysql_protocol/tests
- plugin/mysql_protocol/tests/r
- plugin/mysql_protocol/tests/t
- files renamed:
- drizzled/util/sha1.cc => drizzled/algorithm/sha1.cc
- drizzled/util/sha1.h => drizzled/algorithm/sha1.h
- m4/pandora_have_innodb.m4 => m4/pandora_have_libinnodb.m4
- plugin/mysql_protocol/tests/r/mysql_password.result => plugin/mysql_protocol/tests/r/mysql_password.result
- plugin/mysql_protocol/tests/t/mysql_password.test => plugin/mysql_protocol/tests/t/mysql_password.test
- files modified:
- config/pandora-plugin
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.
44
44
45
45
46
PartitionPruningModule
47
A module that accepts a partitioned table, condition, and finds which
48
partitions we will need to use in query execution. Search down for
49
"PartitionPruningModule" for description.
50
The module has single entry point - prune_partitions() function.
51
52
53
46
Range/index_merge/groupby-minmax optimizer module
54
47
A module that accepts a table, condition, and returns
55
48
- a QUICK_*_SELECT object that can be used to retrieve rows that match
133
126
#include "drizzled/optimizer/quick_ror_union_select.h"
134
127
#include "drizzled/optimizer/table_read_plan.h"
135
128
#include "drizzled/optimizer/sel_arg.h"
129
#include "drizzled/optimizer/sel_imerge.h"
130
#include "drizzled/optimizer/sel_tree.h"
136
131
#include "drizzled/optimizer/range_param.h"
137
132
#include "drizzled/records.h"
138
133
#include "drizzled/internal/my_sys.h"
235
230
}
236
231
}
237
232
238
class SEL_IMERGE;
239
240
241
class SEL_TREE :public memory::SqlAlloc
242
{
243
public:
244
/*
245
Starting an effort to document this field:
246
(for some i, keys[i]->type == optimizer::SEL_ARG::IMPOSSIBLE) =>
247
(type == SEL_TREE::IMPOSSIBLE)
248
*/
249
enum Type
250
{
251
IMPOSSIBLE,
252
ALWAYS,
253
MAYBE,
254
KEY,
255
KEY_SMALLER
256
} type;
257
258
SEL_TREE(enum Type type_arg) :type(type_arg) {}
259
SEL_TREE() :type(KEY)
260
{
261
keys_map.reset();
262
memset(keys, 0, sizeof(keys));
263
}
264
/*
265
Note: there may exist SEL_TREE objects with sel_tree->type=KEY and
266
keys[i]=0 for all i. (SergeyP: it is not clear whether there is any
267
merit in range analyzer functions (e.g. get_mm_parts) returning a
268
pointer to such SEL_TREE instead of NULL)
269
*/
270
optimizer::SEL_ARG *keys[MAX_KEY];
271
key_map keys_map; /* bitmask of non-NULL elements in keys */
272
273
/*
274
Possible ways to read rows using index_merge. The list is non-empty only
275
if type==KEY. Currently can be non empty only if keys_map.none().
276
*/
277
List<SEL_IMERGE> merges;
278
279
/* The members below are filled/used only after get_mm_tree is done */
280
key_map ror_scans_map; /* bitmask of ROR scan-able elements in keys */
281
uint32_t n_ror_scans; /* number of set bits in ror_scans_map */
282
283
struct st_ror_scan_info **ror_scans; /* list of ROR key scans */
284
struct st_ror_scan_info **ror_scans_end; /* last ROR scan */
285
/* Note that #records for each key scan is stored in table->quick_rows */
286
};
287
288
233
struct st_ror_scan_info;
289
234
290
static SEL_TREE * get_mm_parts(optimizer::RangeParameter *param,
235
static optimizer::SEL_TREE * get_mm_parts(optimizer::RangeParameter *param,
291
236
COND *cond_func,
292
237
Field *field,
293
238
Item_func::Functype type,
301
246
Item_func::Functype type,
302
247
Item *value);
303
248
304
static SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond);
249
static optimizer::SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond);
305
250
306
251
static bool is_key_scan_ror(optimizer::Parameter *param, uint32_t keynr, uint8_t nparts);
307
252
315
260
COST_VECT *cost);
316
261
317
262
static optimizer::RangeReadPlan *get_key_scans_params(optimizer::Parameter *param,
318
SEL_TREE *tree,
263
optimizer::SEL_TREE *tree,
319
264
bool index_read_must_be_used,
320
265
bool update_tbl_stats,
321
266
double read_time);
322
267
323
268
static
324
269
optimizer::RorIntersectReadPlan *get_best_ror_intersect(const optimizer::Parameter *param,
325
SEL_TREE *tree,
270
optimizer::SEL_TREE *tree,
326
271
double read_time,
327
272
bool *are_all_covering);
328
273
329
274
static
330
275
optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
331
SEL_TREE *tree,
276
optimizer::SEL_TREE *tree,
332
277
double read_time);
333
278
334
279
static
335
280
optimizer::TableReadPlan *get_best_disjunct_quick(optimizer::Parameter *param,
336
SEL_IMERGE *imerge,
281
optimizer::SEL_IMERGE *imerge,
337
282
double read_time);
338
283
339
284
static
340
optimizer::GroupMinMaxReadPlan *get_best_group_min_max(optimizer::Parameter *param, SEL_TREE *tree);
341
342
static void print_sel_tree(optimizer::Parameter *param,
343
SEL_TREE *tree,
344
key_map *tree_map,
345
const char *msg);
346
347
static void print_ror_scans_arr(Table *table,
348
const char *msg,
349
struct st_ror_scan_info **start,
350
struct st_ror_scan_info **end);
351
static void print_ror_scans_vector(Table *table,
352
const char *msg,
353
vector<struct st_ror_scan_info *> &vec);
354
355
static SEL_TREE *tree_and(optimizer::RangeParameter *param, SEL_TREE *tree1, SEL_TREE *tree2);
356
357
static SEL_TREE *tree_or(optimizer::RangeParameter *param, SEL_TREE *tree1, SEL_TREE *tree2);
285
optimizer::GroupMinMaxReadPlan *get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree);
286
287
static optimizer::SEL_TREE *tree_and(optimizer::RangeParameter *param,
288
optimizer::SEL_TREE *tree1,
289
optimizer::SEL_TREE *tree2);
358
290
359
291
static optimizer::SEL_ARG *sel_add(optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);
360
292
361
static optimizer::SEL_ARG *key_or(optimizer::RangeParameter *param, optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);
362
363
293
static optimizer::SEL_ARG *key_and(optimizer::RangeParameter *param,
364
294
optimizer::SEL_ARG *key1,
365
295
optimizer::SEL_ARG *key2,
367
297
368
298
static bool get_range(optimizer::SEL_ARG **e1, optimizer::SEL_ARG **e2, optimizer::SEL_ARG *root1);
369
299
370
static bool eq_tree(optimizer::SEL_ARG* a, optimizer::SEL_ARG *b);
371
372
300
optimizer::SEL_ARG optimizer::null_element(optimizer::SEL_ARG::IMPOSSIBLE);
373
301
374
302
static bool null_part_in_key(KEY_PART *key_part,
375
303
const unsigned char *key,
376
304
uint32_t length);
377
305
378
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, optimizer::RangeParameter *param);
379
380
381
/*
382
SEL_IMERGE is a list of possible ways to do index merge, i.e. it is
383
a condition in the following form:
384
(t_1||t_2||...||t_N) && (next)
385
386
where all t_i are SEL_TREEs, next is another SEL_IMERGE and no pair
387
(t_i,t_j) contains SEL_ARGS for the same index.
388
389
SEL_TREE contained in SEL_IMERGE always has merges=NULL.
390
391
This class relies on memory manager to do the cleanup.
392
*/
393
394
class SEL_IMERGE : public memory::SqlAlloc
395
{
396
enum { PREALLOCED_TREES= 10};
397
public:
398
SEL_TREE *trees_prealloced[PREALLOCED_TREES];
399
SEL_TREE **trees; /* trees used to do index_merge */
400
SEL_TREE **trees_next; /* last of these trees */
401
SEL_TREE **trees_end; /* end of allocated space */
402
403
optimizer::SEL_ARG ***best_keys; /* best keys to read in SEL_TREEs */
404
405
SEL_IMERGE() :
406
trees(&trees_prealloced[0]),
407
trees_next(trees),
408
trees_end(trees + PREALLOCED_TREES)
409
{}
410
int or_sel_tree(optimizer::RangeParameter *param, SEL_TREE *tree);
411
int or_sel_tree_with_checks(optimizer::RangeParameter *param, SEL_TREE *new_tree);
412
int or_sel_imerge_with_checks(optimizer::RangeParameter *param, SEL_IMERGE* imerge);
413
};
414
415
416
/*
417
Add SEL_TREE to this index_merge without any checks,
418
419
NOTES
420
This function implements the following:
421
(x_1||...||x_N) || t = (x_1||...||x_N||t), where x_i, t are SEL_TREEs
422
423
RETURN
424
0 - OK
425
-1 - Out of memory.
426
*/
427
int SEL_IMERGE::or_sel_tree(optimizer::RangeParameter *param, SEL_TREE *tree)
428
{
429
if (trees_next == trees_end)
430
{
431
const int realloc_ratio= 2; /* Double size for next round */
432
uint32_t old_elements= (trees_end - trees);
433
uint32_t old_size= sizeof(SEL_TREE**) * old_elements;
434
uint32_t new_size= old_size * realloc_ratio;
435
SEL_TREE **new_trees;
436
if (!(new_trees= (SEL_TREE**)alloc_root(param->mem_root, new_size)))
437
return -1;
438
memcpy(new_trees, trees, old_size);
439
trees= new_trees;
440
trees_next= trees + old_elements;
441
trees_end= trees + old_elements * realloc_ratio;
442
}
443
*(trees_next++)= tree;
444
return 0;
445
}
446
447
448
/*
449
Perform OR operation on this SEL_IMERGE and supplied SEL_TREE new_tree,
450
combining new_tree with one of the trees in this SEL_IMERGE if they both
451
have SEL_ARGs for the same key.
452
453
SYNOPSIS
454
or_sel_tree_with_checks()
455
param Parameter from SqlSelect::test_quick_select
456
new_tree SEL_TREE with type KEY or KEY_SMALLER.
457
458
NOTES
459
This does the following:
460
(t_1||...||t_k)||new_tree =
461
either
462
= (t_1||...||t_k||new_tree)
463
or
464
= (t_1||....||(t_j|| new_tree)||...||t_k),
465
466
where t_i, y are SEL_TREEs.
467
new_tree is combined with the first t_j it has a SEL_ARG on common
468
key with. As a consequence of this, choice of keys to do index_merge
469
read may depend on the order of conditions in WHERE part of the query.
470
471
RETURN
472
0 OK
473
1 One of the trees was combined with new_tree to SEL_TREE::ALWAYS,
474
and (*this) should be discarded.
475
-1 An error occurred.
476
*/
477
int SEL_IMERGE::or_sel_tree_with_checks(optimizer::RangeParameter *param, SEL_TREE *new_tree)
478
{
479
for (SEL_TREE** tree = trees;
480
tree != trees_next;
481
tree++)
482
{
483
if (sel_trees_can_be_ored(*tree, new_tree, param))
484
{
485
*tree = tree_or(param, *tree, new_tree);
486
if (!*tree)
487
return 1;
488
if (((*tree)->type == SEL_TREE::MAYBE) ||
489
((*tree)->type == SEL_TREE::ALWAYS))
490
return 1;
491
/* SEL_TREE::IMPOSSIBLE is impossible here */
492
return 0;
493
}
494
}
495
496
/* New tree cannot be combined with any of existing trees. */
497
return or_sel_tree(param, new_tree);
498
}
499
500
501
/*
502
Perform OR operation on this index_merge and supplied index_merge list.
503
504
RETURN
505
0 - OK
506
1 - One of conditions in result is always true and this SEL_IMERGE
507
should be discarded.
508
-1 - An error occurred
509
*/
510
511
int SEL_IMERGE::or_sel_imerge_with_checks(optimizer::RangeParameter *param, SEL_IMERGE* imerge)
512
{
513
for (SEL_TREE** tree= imerge->trees;
514
tree != imerge->trees_next;
515
tree++)
516
{
517
if (or_sel_tree_with_checks(param, *tree))
518
return 1;
519
}
520
return 0;
521
}
306
bool sel_trees_can_be_ored(optimizer::SEL_TREE *tree1,
307
optimizer::SEL_TREE *tree2,
308
optimizer::RangeParameter *param);
309
310
311
312
522
313
523
314
524
315
/*
525
316
Perform AND operation on two index_merge lists and store result in *im1.
526
317
*/
527
318
528
inline void imerge_list_and_list(List<SEL_IMERGE> *im1, List<SEL_IMERGE> *im2)
319
inline void imerge_list_and_list(List<optimizer::SEL_IMERGE> *im1, List<optimizer::SEL_IMERGE> *im2)
529
320
{
530
321
im1->concat(im2);
531
322
}
532
323
533
324
534
/*
535
Perform OR operation on 2 index_merge lists, storing result in first list.
536
537
NOTES
538
The following conversion is implemented:
539
(a_1 &&...&& a_N)||(b_1 &&...&& b_K) = AND_i,j(a_i || b_j) =>
540
=> (a_1||b_1).
541
542
i.e. all conjuncts except the first one are currently dropped.
543
This is done to avoid producing N*K ways to do index_merge.
544
545
If (a_1||b_1) produce a condition that is always true, NULL is returned
546
and index_merge is discarded (while it is actually possible to try
547
harder).
548
549
As a consequence of this, choice of keys to do index_merge read may depend
550
on the order of conditions in WHERE part of the query.
551
552
RETURN
553
0 OK, result is stored in *im1
554
other Error, both passed lists are unusable
555
*/
556
557
static int imerge_list_or_list(optimizer::RangeParameter *param,
558
List<SEL_IMERGE> *im1,
559
List<SEL_IMERGE> *im2)
560
{
561
SEL_IMERGE *imerge= im1->head();
562
im1->empty();
563
im1->push_back(imerge);
564
565
return imerge->or_sel_imerge_with_checks(param, im2->head());
566
}
567
568
569
/*
570
Perform OR operation on index_merge list and key tree.
571
572
RETURN
573
0 OK, result is stored in *im1.
574
other Error
575
*/
576
577
static int imerge_list_or_tree(optimizer::RangeParameter *param,
578
List<SEL_IMERGE> *im1,
579
SEL_TREE *tree)
580
{
581
SEL_IMERGE *imerge;
582
List_iterator<SEL_IMERGE> it(*im1);
583
while ((imerge= it++))
584
{
585
if (imerge->or_sel_tree_with_checks(param, tree))
586
it.remove();
587
}
588
return im1->is_empty();
589
}
590
591
592
325
/***************************************************************************
593
326
** Basic functions for SqlSelect and QuickRangeSelect
594
327
***************************************************************************/
928
661
if (keys_to_use.any())
929
662
{
930
663
memory::Root alloc;
931
SEL_TREE *tree= NULL;
664
optimizer::SEL_TREE *tree= NULL;
932
665
KEY_PART *key_parts;
933
666
KEY *key_info;
934
667
optimizer::Parameter param;
1016
749
{
1017
750
if ((tree= get_mm_tree(¶m,cond)))
1018
751
{
1019
if (tree->type == SEL_TREE::IMPOSSIBLE)
752
if (tree->type == optimizer::SEL_TREE::IMPOSSIBLE)
1020
753
{
1021
754
records=0L; /* Return -1 from this function. */
1022
755
read_time= (double) HA_POS_ERROR;
1026
759
If the tree can't be used for range scans, proceed anyway, as we
1027
760
can construct a group-min-max quick select
1028
761
*/
1029
if (tree->type != SEL_TREE::KEY && tree->type != SEL_TREE::KEY_SMALLER)
762
if (tree->type != optimizer::SEL_TREE::KEY && tree->type != optimizer::SEL_TREE::KEY_SMALLER)
1030
763
tree= NULL;
1031
764
}
1032
765
}
1097
830
else
1098
831
{
1099
832
/* Try creating index_merge/ROR-union scan. */
1100
SEL_IMERGE *imerge= NULL;
833
optimizer::SEL_IMERGE *imerge= NULL;
1101
834
optimizer::TableReadPlan *best_conj_trp= NULL;
1102
835
optimizer::TableReadPlan *new_conj_trp= NULL;
1103
List_iterator_fast<SEL_IMERGE> it(tree->merges);
836
List_iterator_fast<optimizer::SEL_IMERGE> it(tree->merges);
1104
837
while ((imerge= it++))
1105
838
{
1106
839
new_conj_trp= get_best_disjunct_quick(¶m, imerge, best_read_time);
1143
876
}
1144
877
1145
878
/*
1146
Get best plan for a SEL_IMERGE disjunctive expression.
879
Get best plan for a optimizer::SEL_IMERGE disjunctive expression.
1147
880
SYNOPSIS
1148
881
get_best_disjunct_quick()
1149
882
param Parameter from check_quick_select function
1209
942
1210
943
static
1211
944
optimizer::TableReadPlan *get_best_disjunct_quick(optimizer::Parameter *param,
1212
SEL_IMERGE *imerge,
945
optimizer::SEL_IMERGE *imerge,
1213
946
double read_time)
1214
947
{
1215
SEL_TREE **ptree;
948
optimizer::SEL_TREE **ptree= NULL;
1216
949
optimizer::IndexMergeReadPlan *imerge_trp= NULL;
1217
950
uint32_t n_child_scans= imerge->trees_next - imerge->trees;
1218
951
optimizer::RangeReadPlan **range_scans= NULL;
1245
978
ptree != imerge->trees_next;
1246
979
ptree++, cur_child++)
1247
980
{
1248
print_sel_tree(param, *ptree, &(*ptree)->keys_map, "tree in SEL_IMERGE");
1249
981
if (!(*cur_child= get_key_scans_params(param, *ptree, true, false, read_time)))
1250
982
{
1251
983
/*
1960
1692
1961
1693
static
1962
1694
optimizer::RorIntersectReadPlan *get_best_ror_intersect(const optimizer::Parameter *param,
1963
SEL_TREE *tree,
1695
optimizer::SEL_TREE *tree,
1964
1696
double read_time,
1965
1697
bool *are_all_covering)
1966
1698
{
1967
uint32_t idx;
1699
uint32_t idx= 0;
1968
1700
double min_cost= DBL_MAX;
1969
1701
1970
if ((tree->n_ror_scans < 2) || !param->table->cursor->stats.records)
1702
if ((tree->n_ror_scans < 2) || ! param->table->cursor->stats.records)
1971
1703
return NULL;
1972
1704
1973
1705
/*
1974
1706
Step1: Collect ROR-able SEL_ARGs and create ROR_SCAN_INFO for each of
1975
1707
them. Also find and save clustered PK scan if there is one.
1976
1708
*/
1977
ROR_SCAN_INFO **cur_ror_scan;
1709
ROR_SCAN_INFO **cur_ror_scan= NULL;
1978
1710
ROR_SCAN_INFO *cpk_scan= NULL;
1979
uint32_t cpk_no;
1711
uint32_t cpk_no= 0;
1980
1712
bool cpk_scan_used= false;
1981
1713
1982
if (!(tree->ror_scans= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
1983
sizeof(ROR_SCAN_INFO*)*
1984
param->keys)))
1714
if (! (tree->ror_scans= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
1715
sizeof(ROR_SCAN_INFO*)*
1716
param->keys)))
1985
1717
return NULL;
1986
1718
cpk_no= ((param->table->cursor->primary_key_is_clustered()) ?
1987
1719
param->table->s->primary_key : MAX_KEY);
2003
1735
}
2004
1736
2005
1737
tree->ror_scans_end= cur_ror_scan;
2006
print_ror_scans_arr(param->table, "original",
2007
tree->ror_scans,
2008
tree->ror_scans_end);
2009
1738
/*
2010
1739
Ok, [ror_scans, ror_scans_end) is array of ptrs to initialized
2011
1740
ROR_SCAN_INFO's.
2013
1742
*/
2014
1743
internal::my_qsort(tree->ror_scans, tree->n_ror_scans, sizeof(ROR_SCAN_INFO*),
2015
1744
(qsort_cmp)cmp_ror_scan_info);
2016
print_ror_scans_arr(param->table, "ordered",
2017
tree->ror_scans,
2018
tree->ror_scans_end);
2019
1745
2020
ROR_SCAN_INFO **intersect_scans; /* ROR scans used in index intersection */
2021
ROR_SCAN_INFO **intersect_scans_end;
2022
if (!(intersect_scans= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
2023
sizeof(ROR_SCAN_INFO*)*
2024
tree->n_ror_scans)))
1746
ROR_SCAN_INFO **intersect_scans= NULL; /* ROR scans used in index intersection */
1747
ROR_SCAN_INFO **intersect_scans_end= NULL;
1748
if (! (intersect_scans= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
1749
sizeof(ROR_SCAN_INFO*)*
1750
tree->n_ror_scans)))
2025
1751
return NULL;
2026
1752
intersect_scans_end= intersect_scans;
2027
1753
2028
1754
/* Create and incrementally update ROR intersection. */
2029
ROR_INTERSECT_INFO *intersect, *intersect_best;
2030
if (!(intersect= ror_intersect_init(param)) ||
2031
!(intersect_best= ror_intersect_init(param)))
1755
ROR_INTERSECT_INFO *intersect= NULL;
1756
ROR_INTERSECT_INFO *intersect_best= NULL;
1757
if (! (intersect= ror_intersect_init(param)) ||
1758
! (intersect_best= ror_intersect_init(param)))
2032
1759
return NULL;
2033
1760
2034
1761
/* [intersect_scans,intersect_scans_best) will hold the best intersection */
2035
ROR_SCAN_INFO **intersect_scans_best;
1762
ROR_SCAN_INFO **intersect_scans_best= NULL;
2036
1763
cur_ror_scan= tree->ror_scans;
2037
1764
intersect_scans_best= intersect_scans;
2038
1765
while (cur_ror_scan != tree->ror_scans_end && !intersect->is_covering)
2060
1787
return NULL;
2061
1788
}
2062
1789
2063
print_ror_scans_arr(param->table,
2064
"best ROR-intersection",
2065
intersect_scans,
2066
intersect_scans_best);
2067
2068
1790
*are_all_covering= intersect->is_covering;
2069
1791
uint32_t best_num= intersect_scans_best - intersect_scans;
2070
1792
ror_intersect_cpy(intersect, intersect_best);
2096
1818
trp->read_cost= intersect_best->total_cost;
2097
1819
/* Prevent divisons by zero */
2098
1820
ha_rows best_rows = double2rows(intersect_best->out_rows);
2099
if (!best_rows)
1821
if (! best_rows)
2100
1822
best_rows= 1;
2101
1823
set_if_smaller(param->table->quick_condition_rows, best_rows);
2102
1824
trp->records= best_rows;
2103
1825
trp->setCostOfIndexScans(intersect_best->index_scan_costs);
2104
1826
trp->cpk_scan= cpk_scan_used? cpk_scan: NULL;
2105
1827
}
2106
return(trp);
1828
return trp;
2107
1829
}
2108
1830
2109
1831
2112
1834
SYNOPSIS
2113
1835
get_best_covering_ror_intersect()
2114
1836
param Parameter from test_quick_select function.
2115
tree SEL_TREE with sets of intervals for different keys.
1837
tree optimizer::SEL_TREE with sets of intervals for different keys.
2116
1838
read_time Don't return table read plans with cost > read_time.
2117
1839
2118
1840
RETURN
2142
1864
2143
1865
static
2144
1866
optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
2145
SEL_TREE *tree,
1867
optimizer::SEL_TREE *tree,
2146
1868
double read_time)
2147
1869
{
2148
1870
ROR_SCAN_INFO **ror_scan_mark;
2177
1899
ha_rows records=0;
2178
1900
bool all_covered;
2179
1901
2180
print_ror_scans_arr(param->table,
2181
"building covering ROR-I",
2182
ror_scan_mark, ror_scans_end);
2183
1902
do
2184
1903
{
2185
1904
/*
2201
1920
sizeof(ROR_SCAN_INFO*),
2202
1921
(qsort_cmp)cmp_ror_scan_info_covering);
2203
1922
2204
print_ror_scans_arr(param->table,
2205
"remaining scans",
2206
ror_scan_mark, ror_scans_end);
2207
2208
1923
/* I=I-first(I) */
2209
1924
total_cost += (*ror_scan_mark)->index_read_cost;
2210
1925
records += (*ror_scan_mark)->records;
2222
1937
Ok, [tree->ror_scans .. ror_scan) holds covering index_intersection with
2223
1938
cost total_cost.
2224
1939
*/
2225
print_ror_scans_arr(param->table,
2226
"creating covering ROR-intersect",
2227
tree->ror_scans, ror_scan_mark);
2228
2229
1940
/* Add priority queue use cost. */
2230
1941
total_cost += rows2double(records)*
2231
1942
log((double)(ror_scan_mark - tree->ror_scans)) /
2253
1964
2254
1965
2255
1966
/*
2256
Get best "range" table read plan for given SEL_TREE, also update some info
1967
Get best "range" table read plan for given optimizer::SEL_TREE, also update some info
2257
1968
2258
1969
SYNOPSIS
2259
1970
get_key_scans_params()
2260
1971
param Parameters from test_quick_select
2261
tree Make range select for this SEL_TREE
1972
tree Make range select for this optimizer::SEL_TREE
2262
1973
index_read_must_be_used true <=> assume 'index only' option will be set
2263
1974
(except for clustered PK indexes)
2264
1975
update_tbl_stats true <=> update table->quick_* with information
2267
1978
cost > read_time.
2268
1979
2269
1980
DESCRIPTION
2270
Find the best "range" table read plan for given SEL_TREE.
1981
Find the best "range" table read plan for given optimizer::SEL_TREE.
2271
1982
The side effects are
2272
1983
- tree->ror_scans is updated to indicate which scans are ROR scans.
2273
1984
- if update_tbl_stats=true then table->quick_* is updated with info
2279
1990
*/
2280
1991
2281
1992
static optimizer::RangeReadPlan *get_key_scans_params(optimizer::Parameter *param,
2282
SEL_TREE *tree,
1993
optimizer::SEL_TREE *tree,
2283
1994
bool index_read_must_be_used,
2284
1995
bool update_tbl_stats,
2285
1996
double read_time)
2293
2004
uint32_t best_buf_size= 0;
2294
2005
optimizer::RangeReadPlan *read_plan= NULL;
2295
2006
/*
2296
Note that there may be trees that have type SEL_TREE::KEY but contain no
2007
Note that there may be trees that have type optimizer::SEL_TREE::KEY but contain no
2297
2008
key reads at all, e.g. tree for expression "key1 is not null" where key1
2298
2009
is defined as "not null".
2299
2010
*/
2300
print_sel_tree(param, tree, &tree->keys_map, "tree scans");
2301
2011
tree->ror_scans_map.reset();
2302
2012
tree->n_ror_scans= 0;
2303
2013
for (idx= 0,key=tree->keys, end=key+param->keys; key != end; key++,idx++)
2336
2046
}
2337
2047
}
2338
2048
2339
print_sel_tree(param, tree, &tree->ror_scans_map, "ROR scans");
2340
2049
if (key_to_read)
2341
2050
{
2342
2051
idx= key_to_read - tree->keys;
2396
2105
(retrieve_full_rows? (! is_covering) : false),
2397
2106
parent_alloc)))
2398
2107
{
2399
print_ror_scans_vector(param->table,
2400
"creating ROR-intersect",
2401
ror_range_scans);
2402
2108
alloc= parent_alloc ? parent_alloc : &quick_intersect->alloc;
2403
2109
for (vector<struct st_ror_scan_info *>::iterator it= ror_range_scans.begin();
2404
2110
it != ror_range_scans.end();
2466
2172
2467
2173
2468
2174
/*
2469
Build a SEL_TREE for <> or NOT BETWEEN predicate
2175
Build a optimizer::SEL_TREE for <> or NOT BETWEEN predicate
2470
2176
2471
2177
SYNOPSIS
2472
2178
get_ne_mm_tree()
2481
2187
# Pointer to tree built tree
2482
2188
0 on error
2483
2189
*/
2484
static SEL_TREE *get_ne_mm_tree(optimizer::RangeParameter *param,
2190
static optimizer::SEL_TREE *get_ne_mm_tree(optimizer::RangeParameter *param,
2485
2191
Item_func *cond_func,
2486
2192
Field *field,
2487
2193
Item *lt_value, Item *gt_value,
2488
2194
Item_result cmp_type)
2489
2195
{
2490
SEL_TREE *tree;
2196
optimizer::SEL_TREE *tree= NULL;
2491
2197
tree= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
2492
2198
lt_value, cmp_type);
2493
2199
if (tree)
2504
2210
2505
2211
2506
2212
/*
2507
Build a SEL_TREE for a simple predicate
2213
Build a optimizer::SEL_TREE for a simple predicate
2508
2214
2509
2215
SYNOPSIS
2510
2216
get_func_mm_tree()
2519
2225
RETURN
2520
2226
Pointer to the tree built tree
2521
2227
*/
2522
static SEL_TREE *get_func_mm_tree(optimizer::RangeParameter *param,
2228
static optimizer::SEL_TREE *get_func_mm_tree(optimizer::RangeParameter *param,
2523
2229
Item_func *cond_func,
2524
2230
Field *field,
2525
2231
Item *value,
2526
2232
Item_result cmp_type,
2527
2233
bool inv)
2528
2234
{
2529
SEL_TREE *tree= NULL;
2235
optimizer::SEL_TREE *tree= NULL;
2530
2236
2531
2237
switch (cond_func->functype())
2532
2238
{
2598
2304
{
2599
2305
/*
2600
2306
We get here for conditions in form "t.key NOT IN (c1, c2, ...)",
2601
where c{i} are constants. Our goal is to produce a SEL_TREE that
2307
where c{i} are constants. Our goal is to produce a optimizer::SEL_TREE that
2602
2308
represents intervals:
2603
2309
2604
2310
($MIN<t.key<c1) OR (c1<t.key<c2) OR (c2<t.key<c3) OR ... (*)
2607
2313
2608
2314
The most straightforward way to produce it is to convert NOT IN
2609
2315
into "(t.key != c1) AND (t.key != c2) AND ... " and let the range
2610
analyzer to build SEL_TREE from that. The problem is that the
2316
analyzer to build optimizer::SEL_TREE from that. The problem is that the
2611
2317
range analyzer will use O(N^2) memory (which is probably a bug),
2612
2318
and people do use big NOT IN lists (e.g. see BUG#15872, BUG#21282),
2613
2319
will run out of memory.
2620
2326
2621
2327
Considering the above, we'll handle NOT IN as follows:
2622
2328
* if the number of entries in the NOT IN list is less than
2623
NOT_IN_IGNORE_THRESHOLD, construct the SEL_TREE (*) manually.
2624
* Otherwise, don't produce a SEL_TREE.
2329
NOT_IN_IGNORE_THRESHOLD, construct the optimizer::SEL_TREE (*) manually.
2330
* Otherwise, don't produce a optimizer::SEL_TREE.
2625
2331
*/
2626
2332
#define NOT_IN_IGNORE_THRESHOLD 1000
2627
2333
memory::Root *tmp_root= param->mem_root;
2640
2346
if (func->array->count > NOT_IN_IGNORE_THRESHOLD || ! value_item)
2641
2347
break;
2642
2348
2643
/* Get a SEL_TREE for "(-inf|NULL) < X < c_0" interval. */
2349
/* Get a optimizer::SEL_TREE for "(-inf|NULL) < X < c_0" interval. */
2644
2350
uint32_t i=0;
2645
2351
do
2646
2352
{
2653
2359
if (! tree)
2654
2360
break;
2655
2361
i++;
2656
} while (i < func->array->count && tree->type == SEL_TREE::IMPOSSIBLE);
2362
} while (i < func->array->count && tree->type == optimizer::SEL_TREE::IMPOSSIBLE);
2657
2363
2658
if (!tree || tree->type == SEL_TREE::IMPOSSIBLE)
2364
if (!tree || tree->type == optimizer::SEL_TREE::IMPOSSIBLE)
2659
2365
{
2660
2366
/* We get here in cases like "t.unsigned NOT IN (-1,-2,-3) */
2661
2367
tree= NULL;
2662
2368
break;
2663
2369
}
2664
SEL_TREE *tree2;
2370
optimizer::SEL_TREE *tree2= NULL;
2665
2371
for (; i < func->array->count; i++)
2666
2372
{
2667
2373
if (func->array->compare_elems(i, i-1))
2668
2374
{
2669
/* Get a SEL_TREE for "-inf < X < c_i" interval */
2375
/* Get a optimizer::SEL_TREE for "-inf < X < c_i" interval */
2670
2376
func->array->value_to_item(i, value_item);
2671
2377
tree2= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
2672
2378
value_item, cmp_type);
2696
2402
}
2697
2403
}
2698
2404
2699
if (tree && tree->type != SEL_TREE::IMPOSSIBLE)
2405
if (tree && tree->type != optimizer::SEL_TREE::IMPOSSIBLE)
2700
2406
{
2701
2407
/*
2702
Get the SEL_TREE for the last "c_last < X < +inf" interval
2408
Get the optimizer::SEL_TREE for the last "c_last < X < +inf" interval
2703
2409
(value_item cotains c_last already)
2704
2410
*/
2705
2411
tree2= get_mm_parts(param, cond_func, field, Item_func::GT_FUNC,
2763
2469
2764
2470
2765
2471
/*
2766
Build conjunction of all SEL_TREEs for a simple predicate applying equalities
2472
Build conjunction of all optimizer::SEL_TREEs for a simple predicate applying equalities
2767
2473
2768
2474
SYNOPSIS
2769
2475
get_full_func_mm_tree()
2778
2484
2779
2485
DESCRIPTION
2780
2486
For a simple SARGable predicate of the form (f op c), where f is a field and
2781
c is a constant, the function builds a conjunction of all SEL_TREES that can
2487
c is a constant, the function builds a conjunction of all optimizer::SEL_TREES that can
2782
2488
be obtained by the substitution of f for all different fields equal to f.
2783
2489
2784
2490
NOTES
2788
2494
each fj belonging to the same multiple equality as fi
2789
2495
are built as well.
2790
2496
E.g. for WHERE t1.a=t2.a AND t2.a > 10
2791
a SEL_TREE for t2.a > 10 will be built for quick select from t2
2497
a optimizer::SEL_TREE for t2.a > 10 will be built for quick select from t2
2792
2498
and
2793
a SEL_TREE for t1.a > 10 will be built for quick select from t1.
2499
a optimizer::SEL_TREE for t1.a > 10 will be built for quick select from t1.
2794
2500
2795
2501
A BETWEEN predicate of the form (fi [NOT] BETWEEN c1 AND c2) is treated
2796
2502
in a similar way: we build a conjuction of trees for the results
2829
2535
the form (c IN (c1,...,f,...,cn)).
2830
2536
2831
2537
RETURN
2832
Pointer to the tree representing the built conjunction of SEL_TREEs
2538
Pointer to the tree representing the built conjunction of optimizer::SEL_TREEs
2833
2539
*/
2834
2540
2835
static SEL_TREE *get_full_func_mm_tree(optimizer::RangeParameter *param,
2541
static optimizer::SEL_TREE *get_full_func_mm_tree(optimizer::RangeParameter *param,
2836
2542
Item_func *cond_func,
2837
2543
Item_field *field_item, Item *value,
2838
2544
bool inv)
2839
2545
{
2840
SEL_TREE *tree= 0;
2841
SEL_TREE *ftree= 0;
2546
optimizer::SEL_TREE *tree= 0;
2547
optimizer::SEL_TREE *ftree= 0;
2842
2548
table_map ref_tables= 0;
2843
2549
table_map param_comp= ~(param->prev_tables | param->read_tables |
2844
2550
param->current_table);
2880
2586
2881
2587
/* make a select tree of all keys in condition */
2882
2588
2883
static SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond)
2589
static optimizer::SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond)
2884
2590
{
2885
SEL_TREE *tree=0;
2886
SEL_TREE *ftree= 0;
2591
optimizer::SEL_TREE *tree=0;
2592
optimizer::SEL_TREE *ftree= 0;
2887
2593
Item_field *field_item= 0;
2888
2594
bool inv= false;
2889
2595
Item *value= 0;
2898
2604
Item *item;
2899
2605
while ((item=li++))
2900
2606
{
2901
SEL_TREE *new_tree= get_mm_tree(param,item);
2607
optimizer::SEL_TREE *new_tree= get_mm_tree(param,item);
2902
2608
if (param->session->is_fatal_error ||
2903
2609
param->alloced_sel_args > optimizer::SEL_ARG::MAX_SEL_ARGS)
2904
2610
return 0; // out of memory
2905
2611
tree=tree_and(param,tree,new_tree);
2906
if (tree && tree->type == SEL_TREE::IMPOSSIBLE)
2612
if (tree && tree->type == optimizer::SEL_TREE::IMPOSSIBLE)
2907
2613
break;
2908
2614
}
2909
2615
}
2915
2621
Item *item;
2916
2622
while ((item=li++))
2917
2623
{
2918
SEL_TREE *new_tree= get_mm_tree(param,item);
2624
optimizer::SEL_TREE *new_tree= get_mm_tree(param,item);
2919
2625
if (!new_tree)
2920
2626
return 0; // out of memory
2921
2627
tree=tree_or(param,tree,new_tree);
2922
if (!tree || tree->type == SEL_TREE::ALWAYS)
2628
if (!tree || tree->type == optimizer::SEL_TREE::ALWAYS)
2923
2629
break;
2924
2630
}
2925
2631
}
2937
2643
*/
2938
2644
memory::Root *tmp_root= param->mem_root;
2939
2645
param->session->mem_root= param->old_root;
2940
tree= cond->val_int() ? new(tmp_root) SEL_TREE(SEL_TREE::ALWAYS) :
2941
new(tmp_root) SEL_TREE(SEL_TREE::IMPOSSIBLE);
2646
tree= cond->val_int() ? new(tmp_root) optimizer::SEL_TREE(optimizer::SEL_TREE::ALWAYS) :
2647
new(tmp_root) optimizer::SEL_TREE(optimizer::SEL_TREE::IMPOSSIBLE);
2942
2648
param->session->mem_root= tmp_root;
2943
2649
return(tree);
2944
2650
}
2952
2658
if ((ref_tables & param->current_table) ||
2953
2659
(ref_tables & ~(param->prev_tables | param->read_tables)))
2954
2660
return 0;
2955
return(new SEL_TREE(SEL_TREE::MAYBE));
2661
return(new optimizer::SEL_TREE(optimizer::SEL_TREE::MAYBE));
2956
2662
}
2957
2663
2958
2664
Item_func *cond_func= (Item_func*) cond;
2981
2687
if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM)
2982
2688
{
2983
2689
field_item= (Item_field*) (cond_func->arguments()[i]->real_item());
2984
SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func,
2690
optimizer::SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func,
2985
2691
field_item, (Item*)(intptr_t)i, inv);
2986
2692
if (inv)
2987
2693
tree= !tree ? tmp : tree_or(param, tree, tmp);
3051
2757
}
3052
2758
3053
2759
3054
static SEL_TREE *
2760
static optimizer::SEL_TREE *
3055
2761
get_mm_parts(optimizer::RangeParameter *param,
3056
2762
COND *cond_func,
3057
2763
Field *field,
3063
2769
3064
2770
KEY_PART *key_part = param->key_parts;
3065
2771
KEY_PART *end = param->key_parts_end;
3066
SEL_TREE *tree=0;
2772
optimizer::SEL_TREE *tree=0;
3067
2773
if (value &&
3068
2774
value->used_tables() & ~(param->prev_tables | param->read_tables))
3069
2775
return 0;
3072
2778
if (field->eq(key_part->field))
3073
2779
{
3074
2780
optimizer::SEL_ARG *sel_arg=0;
3075
if (!tree && !(tree=new SEL_TREE()))
2781
if (!tree && !(tree=new optimizer::SEL_TREE()))
3076
2782
return 0; // OOM
3077
2783
if (!value || !(value->used_tables() & ~param->read_tables))
3078
2784
{
3082
2788
continue;
3083
2789
if (sel_arg->type == optimizer::SEL_ARG::IMPOSSIBLE)
3084
2790
{
3085
tree->type=SEL_TREE::IMPOSSIBLE;
2791
tree->type=optimizer::SEL_TREE::IMPOSSIBLE;
3086
2792
return(tree);
3087
2793
}
3088
2794
}
3569
3275
#define swap_clone_flag(A) ((A & 1) << 1) | ((A & 2) >> 1)
3570
3276
3571
3277
3572
static SEL_TREE *
3573
tree_and(optimizer::RangeParameter *param, SEL_TREE *tree1, SEL_TREE *tree2)
3278
static optimizer::SEL_TREE *
3279
tree_and(optimizer::RangeParameter *param, optimizer::SEL_TREE *tree1, optimizer::SEL_TREE *tree2)
3574
3280
{
3575
3281
if (!tree1)
3576
3282
return(tree2);
3577
3283
if (!tree2)
3578
3284
return(tree1);
3579
if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
3285
if (tree1->type == optimizer::SEL_TREE::IMPOSSIBLE || tree2->type == optimizer::SEL_TREE::ALWAYS)
3580
3286
return(tree1);
3581
if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
3287
if (tree2->type == optimizer::SEL_TREE::IMPOSSIBLE || tree1->type == optimizer::SEL_TREE::ALWAYS)
3582
3288
return(tree2);
3583
if (tree1->type == SEL_TREE::MAYBE)
3289
if (tree1->type == optimizer::SEL_TREE::MAYBE)
3584
3290
{
3585
if (tree2->type == SEL_TREE::KEY)
3586
tree2->type=SEL_TREE::KEY_SMALLER;
3291
if (tree2->type == optimizer::SEL_TREE::KEY)
3292
tree2->type=optimizer::SEL_TREE::KEY_SMALLER;
3587
3293
return(tree2);
3588
3294
}
3589
if (tree2->type == SEL_TREE::MAYBE)
3295
if (tree2->type == optimizer::SEL_TREE::MAYBE)
3590
3296
{
3591
tree1->type=SEL_TREE::KEY_SMALLER;
3297
tree1->type=optimizer::SEL_TREE::KEY_SMALLER;
3592
3298
return(tree1);
3593
3299
}
3594
3300
key_map result_keys;
3609
3315
*key1=key_and(param, *key1, *key2, flag);
3610
3316
if (*key1 && (*key1)->type == optimizer::SEL_ARG::IMPOSSIBLE)
3611
3317
{
3612
tree1->type= SEL_TREE::IMPOSSIBLE;
3318
tree1->type= optimizer::SEL_TREE::IMPOSSIBLE;
3613
3319
return(tree1);
3614
3320
}
3615
3321
result_keys.set(key1 - tree1->keys);
3629
3335
}
3630
3336
3631
3337
3632
/*
3633
Check if two SEL_TREES can be combined into one (i.e. a single key range
3634
read can be constructed for "cond_of_tree1 OR cond_of_tree2" ) without
3635
using index_merge.
3636
*/
3637
3638
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2,
3639
optimizer::RangeParameter* param)
3640
{
3641
key_map common_keys= tree1->keys_map;
3642
common_keys&= tree2->keys_map;
3643
3644
if (common_keys.none())
3645
return false;
3646
3647
/* trees have a common key, check if they refer to same key part */
3648
optimizer::SEL_ARG **key1,**key2;
3649
for (uint32_t key_no=0; key_no < param->keys; key_no++)
3650
{
3651
if (common_keys.test(key_no))
3652
{
3653
key1= tree1->keys + key_no;
3654
key2= tree2->keys + key_no;
3655
if ((*key1)->part == (*key2)->part)
3656
{
3657
return true;
3658
}
3659
}
3660
}
3661
return false;
3662
}
3663
3664
3665
/*
3666
Remove the trees that are not suitable for record retrieval.
3667
SYNOPSIS
3668
param Range analysis parameter
3669
tree Tree to be processed, tree->type is KEY or KEY_SMALLER
3670
3671
DESCRIPTION
3672
This function walks through tree->keys[] and removes the SEL_ARG* trees
3673
that are not "maybe" trees (*) and cannot be used to construct quick range
3674
selects.
3675
(*) - have type MAYBE or MAYBE_KEY. Perhaps we should remove trees of
3676
these types here as well.
3677
3678
A SEL_ARG* tree cannot be used to construct quick select if it has
3679
tree->part != 0. (e.g. it could represent "keypart2 < const").
3680
3681
WHY THIS FUNCTION IS NEEDED
3682
3683
Normally we allow construction of SEL_TREE objects that have SEL_ARG
3684
trees that do not allow quick range select construction. For example for
3685
" keypart1=1 AND keypart2=2 " the execution will proceed as follows:
3686
tree1= SEL_TREE { SEL_ARG{keypart1=1} }
3687
tree2= SEL_TREE { SEL_ARG{keypart2=2} } -- can't make quick range select
3688
from this
3689
call tree_and(tree1, tree2) -- this joins SEL_ARGs into a usable SEL_ARG
3690
tree.
3691
3692
There is an exception though: when we construct index_merge SEL_TREE,
3693
any SEL_ARG* tree that cannot be used to construct quick range select can
3694
be removed, because current range analysis code doesn't provide any way
3695
that tree could be later combined with another tree.
3696
Consider an example: we should not construct
3697
st1 = SEL_TREE {
3698
merges = SEL_IMERGE {
3699
SEL_TREE(t.key1part1 = 1),
3700
SEL_TREE(t.key2part2 = 2) -- (*)
3701
}
3702
};
3703
because
3704
- (*) cannot be used to construct quick range select,
3705
- There is no execution path that would cause (*) to be converted to
3706
a tree that could be used.
3707
3708
The latter is easy to verify: first, notice that the only way to convert
3709
(*) into a usable tree is to call tree_and(something, (*)).
3710
3711
Second look at what tree_and/tree_or function would do when passed a
3712
SEL_TREE that has the structure like st1 tree has, and conlcude that
3713
tree_and(something, (*)) will not be called.
3714
3715
RETURN
3716
0 Ok, some suitable trees left
3717
1 No tree->keys[] left.
3718
*/
3719
3720
static bool remove_nonrange_trees(optimizer::RangeParameter *param, SEL_TREE *tree)
3721
{
3722
bool res= false;
3723
for (uint32_t i=0; i < param->keys; i++)
3724
{
3725
if (tree->keys[i])
3726
{
3727
if (tree->keys[i]->part)
3728
{
3729
tree->keys[i]= NULL;
3730
tree->keys_map.reset(i);
3731
}
3732
else
3733
res= true;
3734
}
3735
}
3736
return !res;
3737
}
3738
3739
3740
static SEL_TREE *
3741
tree_or(optimizer::RangeParameter *param,SEL_TREE *tree1,SEL_TREE *tree2)
3742
{
3743
if (!tree1 || !tree2)
3744
return 0;
3745
if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
3746
return(tree2);
3747
if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
3748
return(tree1);
3749
if (tree1->type == SEL_TREE::MAYBE)
3750
return(tree1); // Can't use this
3751
if (tree2->type == SEL_TREE::MAYBE)
3752
return(tree2);
3753
3754
SEL_TREE *result= 0;
3755
key_map result_keys;
3756
result_keys.reset();
3757
if (sel_trees_can_be_ored(tree1, tree2, param))
3758
{
3759
/* Join the trees key per key */
3760
optimizer::SEL_ARG **key1,**key2,**end;
3761
for (key1= tree1->keys,key2= tree2->keys,end= key1+param->keys ;
3762
key1 != end ; key1++,key2++)
3763
{
3764
*key1=key_or(param, *key1, *key2);
3765
if (*key1)
3766
{
3767
result=tree1; // Added to tree1
3768
result_keys.set(key1 - tree1->keys);
3769
}
3770
}
3771
if (result)
3772
result->keys_map= result_keys;
3773
}
3774
else
3775
{
3776
/* ok, two trees have KEY type but cannot be used without index merge */
3777
if (tree1->merges.is_empty() && tree2->merges.is_empty())
3778
{
3779
if (param->remove_jump_scans)
3780
{
3781
bool no_trees= remove_nonrange_trees(param, tree1);
3782
no_trees= no_trees || remove_nonrange_trees(param, tree2);
3783
if (no_trees)
3784
return(new SEL_TREE(SEL_TREE::ALWAYS));
3785
}
3786
SEL_IMERGE *merge;
3787
/* both trees are "range" trees, produce new index merge structure */
3788
if (!(result= new SEL_TREE()) || !(merge= new SEL_IMERGE()) ||
3789
(result->merges.push_back(merge)) ||
3790
(merge->or_sel_tree(param, tree1)) ||
3791
(merge->or_sel_tree(param, tree2)))
3792
result= NULL;
3793
else
3794
result->type= tree1->type;
3795
}
3796
else if (!tree1->merges.is_empty() && !tree2->merges.is_empty())
3797
{
3798
if (imerge_list_or_list(param, &tree1->merges, &tree2->merges))
3799
result= new SEL_TREE(SEL_TREE::ALWAYS);
3800
else
3801
result= tree1;
3802
}
3803
else
3804
{
3805
/* one tree is index merge tree and another is range tree */
3806
if (tree1->merges.is_empty())
3807
std::swap(tree1, tree2);
3808
3809
if (param->remove_jump_scans && remove_nonrange_trees(param, tree2))
3810
return(new SEL_TREE(SEL_TREE::ALWAYS));
3811
/* add tree2 to tree1->merges, checking if it collapses to ALWAYS */
3812
if (imerge_list_or_tree(param, &tree1->merges, tree2))
3813
result= new SEL_TREE(SEL_TREE::ALWAYS);
3814
else
3815
result= tree1;
3816
}
3817
}
3818
return result;
3819
}
3820
3821
3338
3822
3339
/* And key trees where key1->part < key2 -> part */
3823
3340
4014
3531
}
4015
3532
4016
3533
4017
static optimizer::SEL_ARG *
4018
key_or(optimizer::RangeParameter *param, optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2)
4019
{
4020
if (! key1)
4021
{
4022
if (key2)
4023
{
4024
key2->use_count--;
4025
key2->free_tree();
4026
}
4027
return 0;
4028
}
4029
if (! key2)
4030
{
4031
key1->use_count--;
4032
key1->free_tree();
4033
return 0;
4034
}
4035
key1->use_count--;
4036
key2->use_count--;
4037
4038
if (key1->part != key2->part)
4039
{
4040
key1->free_tree();
4041
key2->free_tree();
4042
return 0; // Can't optimize this
4043
}
4044
4045
// If one of the key is MAYBE_KEY then the found region may be bigger
4046
if (key1->type == optimizer::SEL_ARG::MAYBE_KEY)
4047
{
4048
key2->free_tree();
4049
key1->use_count++;
4050
return key1;
4051
}
4052
if (key2->type == optimizer::SEL_ARG::MAYBE_KEY)
4053
{
4054
key1->free_tree();
4055
key2->use_count++;
4056
return key2;
4057
}
4058
4059
if (key1->use_count > 0)
4060
{
4061
if (key2->use_count == 0 || key1->elements > key2->elements)
4062
{
4063
std::swap(key1,key2);
4064
}
4065
if (key1->use_count > 0 || !(key1=key1->clone_tree(param)))
4066
return 0; // OOM
4067
}
4068
4069
// Add tree at key2 to tree at key1
4070
bool key2_shared= key2->use_count != 0;
4071
key1->maybe_flag|= key2->maybe_flag;
4072
4073
for (key2=key2->first(); key2; )
4074
{
4075
optimizer::SEL_ARG *tmp= key1->find_range(key2); // Find key1.min <= key2.min
4076
int cmp;
4077
4078
if (! tmp)
4079
{
4080
tmp=key1->first(); // tmp.min > key2.min
4081
cmp= -1;
4082
}
4083
else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
4084
{ // Found tmp.max < key2.min
4085
optimizer::SEL_ARG *next= tmp->next;
4086
if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part))
4087
{
4088
// Join near ranges like tmp.max < 0 and key2.min >= 0
4089
optimizer::SEL_ARG *key2_next=key2->next;
4090
if (key2_shared)
4091
{
4092
if (! (key2=new optimizer::SEL_ARG(*key2)))
4093
return 0; // out of memory
4094
key2->increment_use_count(key1->use_count+1);
4095
key2->next= key2_next; // New copy of key2
4096
}
4097
key2->copy_min(tmp);
4098
if (! (key1=key1->tree_delete(tmp)))
4099
{ // Only one key in tree
4100
key1= key2;
4101
key1->make_root();
4102
key2= key2_next;
4103
break;
4104
}
4105
}
4106
if (! (tmp= next)) // tmp.min > key2.min
4107
break; // Copy rest of key2
4108
}
4109
if (cmp < 0)
4110
{ // tmp.min > key2.min
4111
int tmp_cmp;
4112
if ((tmp_cmp= tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max
4113
{
4114
if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
4115
{ // ranges are connected
4116
tmp->copy_min_to_min(key2);
4117
key1->merge_flags(key2);
4118
if (tmp->min_flag & NO_MIN_RANGE &&
4119
tmp->max_flag & NO_MAX_RANGE)
4120
{
4121
if (key1->maybe_flag)
4122
return new optimizer::SEL_ARG(optimizer::SEL_ARG::MAYBE_KEY);
4123
return 0;
4124
}
4125
key2->increment_use_count(-1); // Free not used tree
4126
key2= key2->next;
4127
continue;
4128
}
4129
else
4130
{
4131
optimizer::SEL_ARG *next= key2->next; // Keys are not overlapping
4132
if (key2_shared)
4133
{
4134
optimizer::SEL_ARG *cpy= new optimizer::SEL_ARG(*key2); // Must make copy
4135
if (! cpy)
4136
return 0; // OOM
4137
key1= key1->insert(cpy);
4138
key2->increment_use_count(key1->use_count+1);
4139
}
4140
else
4141
key1= key1->insert(key2); // Will destroy key2_root
4142
key2= next;
4143
continue;
4144
}
4145
}
4146
}
4147
4148
// tmp.max >= key2.min && tmp.min <= key.cmax(overlapping ranges)
4149
if (eq_tree(tmp->next_key_part,key2->next_key_part))
4150
{
4151
if (tmp->is_same(key2))
4152
{
4153
tmp->merge_flags(key2); // Copy maybe flags
4154
key2->increment_use_count(-1); // Free not used tree
4155
}
4156
else
4157
{
4158
optimizer::SEL_ARG *last= tmp;
4159
while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
4160
eq_tree(last->next->next_key_part,key2->next_key_part))
4161
{
4162
optimizer::SEL_ARG *save= last;
4163
last= last->next;
4164
key1= key1->tree_delete(save);
4165
}
4166
last->copy_min(tmp);
4167
if (last->copy_min(key2) || last->copy_max(key2))
4168
{ // Full range
4169
key1->free_tree();
4170
for (; key2; key2= key2->next)
4171
key2->increment_use_count(-1); // Free not used tree
4172
if (key1->maybe_flag)
4173
return new optimizer::SEL_ARG(optimizer::SEL_ARG::MAYBE_KEY);
4174
return 0;
4175
}
4176
}
4177
key2= key2->next;
4178
continue;
4179
}
4180
4181
if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
4182
{ // tmp.min <= x < key2.min
4183
optimizer::SEL_ARG *new_arg= tmp->clone_first(key2);
4184
if (! new_arg)
4185
return 0; // OOM
4186
if ((new_arg->next_key_part= key1->next_key_part))
4187
new_arg->increment_use_count(key1->use_count+1);
4188
tmp->copy_min_to_min(key2);
4189
key1= key1->insert(new_arg);
4190
}
4191
4192
// tmp.min >= key2.min && tmp.min <= key2.max
4193
optimizer::SEL_ARG key(*key2); // Get copy we can modify
4194
for (;;)
4195
{
4196
if (tmp->cmp_min_to_min(&key) > 0)
4197
{ // key.min <= x < tmp.min
4198
optimizer::SEL_ARG *new_arg= key.clone_first(tmp);
4199
if (! new_arg)
4200
return 0; // OOM
4201
if ((new_arg->next_key_part=key.next_key_part))
4202
new_arg->increment_use_count(key1->use_count+1);
4203
key1= key1->insert(new_arg);
4204
}
4205
if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
4206
{ // tmp.min. <= x <= tmp.max
4207
tmp->maybe_flag|= key.maybe_flag;
4208
key.increment_use_count(key1->use_count+1);
4209
tmp->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
4210
if (! cmp) // Key2 is ready
4211
break;
4212
key.copy_max_to_min(tmp);
4213
if (! (tmp= tmp->next))
4214
{
4215
optimizer::SEL_ARG *tmp2= new optimizer::SEL_ARG(key);
4216
if (! tmp2)
4217
return 0; // OOM
4218
key1= key1->insert(tmp2);
4219
key2= key2->next;
4220
goto end;
4221
}
4222
if (tmp->cmp_min_to_max(&key) > 0)
4223
{
4224
optimizer::SEL_ARG *tmp2= new optimizer::SEL_ARG(key);
4225
if (! tmp2)
4226
return 0; // OOM
4227
key1= key1->insert(tmp2);
4228
break;
4229
}
4230
}
4231
else
4232
{
4233
optimizer::SEL_ARG *new_arg= tmp->clone_last(&key); // tmp.min <= x <= key.max
4234
if (! new_arg)
4235
return 0; // OOM
4236
tmp->copy_max_to_min(&key);
4237
tmp->increment_use_count(key1->use_count+1);
4238
/* Increment key count as it may be used for next loop */
4239
key.increment_use_count(1);
4240
new_arg->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
4241
key1= key1->insert(new_arg);
4242
break;
4243
}
4244
}
4245
key2= key2->next;
4246
}
4247
4248
end:
4249
while (key2)
4250
{
4251
optimizer::SEL_ARG *next= key2->next;
4252
if (key2_shared)
4253
{
4254
optimizer::SEL_ARG *tmp= new optimizer::SEL_ARG(*key2); // Must make copy
4255
if (! tmp)
4256
return 0;
4257
key2->increment_use_count(key1->use_count+1);
4258
key1= key1->insert(tmp);
4259
}
4260
else
4261
key1= key1->insert(key2); // Will destroy key2_root
4262
key2= next;
4263
}
4264
key1->use_count++;
4265
return key1;
4266
}
4267
4268
4269
/* Compare if two trees are equal */
4270
static bool eq_tree(optimizer::SEL_ARG *a, optimizer::SEL_ARG *b)
4271
{
4272
if (a == b)
4273
{
4274
return true;
4275
}
4276
4277
if (! a || ! b || ! a->is_same(b))
4278
{
4279
return false;
4280
}
4281
4282
if (a->left != &optimizer::null_element && b->left != &optimizer::null_element)
4283
{
4284
if (! eq_tree(a->left,b->left))
4285
return false;
4286
}
4287
else if (a->left != &optimizer::null_element || b->left != &optimizer::null_element)
4288
{
4289
return false;
4290
}
4291
4292
if (a->right != &optimizer::null_element && b->right != &optimizer::null_element)
4293
{
4294
if (! eq_tree(a->right,b->right))
4295
return false;
4296
}
4297
else if (a->right != &optimizer::null_element || b->right != &optimizer::null_element)
4298
{
4299
return false;
4300
}
4301
4302
if (a->next_key_part != b->next_key_part)
4303
{ // Sub range
4304
if (! a->next_key_part != ! b->next_key_part ||
4305
! eq_tree(a->next_key_part, b->next_key_part))
4306
return false;
4307
}
4308
4309
return true;
4310
}
4311
4312
4313
3534
/****************************************************************************
4314
3535
MRR Range Sequence Interface implementation that walks a SEL_ARG* tree.
4315
3536
****************************************************************************/
4340
3561
*/
4341
3562
typedef struct st_sel_arg_range_seq
4342
3563
{
4343
uint32_t keyno; /* index of used tree in SEL_TREE structure */
3564
uint32_t keyno; /* index of used tree in optimizer::SEL_TREE structure */
4344
3565
uint32_t real_keyno; /* Number of the index in tables */
4345
3566
optimizer::Parameter *param;
4346
3567
optimizer::SEL_ARG *start; /* Root node of the traversed SEL_ARG* graph */
4582
3803
SYNOPSIS
4583
3804
check_quick_select()
4584
3805
param Parameter from test_quick_select
4585
idx Number of index to use in Parameter::key SEL_TREE::key
3806
idx Number of index to use in Parameter::key optimizer::SEL_TREE::key
4586
3807
index_only true - assume only index tuples will be accessed
4587
3808
false - assume full table rows will be read
4588
3809
tree Transformed selection condition, tree->key[idx] holds
5196
4417
static inline uint32_t get_field_keypart(KEY *index, Field *field);
5197
4418
5198
4419
static inline optimizer::SEL_ARG * get_index_range_tree(uint32_t index,
5199
SEL_TREE *range_tree,
4420
optimizer::SEL_TREE *range_tree,
5200
4421
optimizer::Parameter *param,
5201
4422
uint32_t *param_idx);
5202
4423
5217
4438
KEY *index_info,
5218
4439
uint32_t used_key_parts,
5219
4440
uint32_t group_key_parts,
5220
SEL_TREE *range_tree,
4441
optimizer::SEL_TREE *range_tree,
5221
4442
optimizer::SEL_ARG *index_tree,
5222
4443
ha_rows quick_prefix_records,
5223
4444
bool have_min,
5354
4575
- NULL
5355
4576
*/
5356
4577
static optimizer::GroupMinMaxReadPlan *
5357
get_best_group_min_max(optimizer::Parameter *param, SEL_TREE *tree)
4578
get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree)
5358
4579
{
5359
4580
Session *session= param->session;
5360
4581
JOIN *join= session->lex->current_select->join;
6068
5289
6069
5290
DESCRIPTION
6070
5291
6071
A SEL_TREE contains range trees for all usable indexes. This procedure
6072
finds the SEL_ARG sub-tree for 'index'. The members of a SEL_TREE are
5292
A optimizer::SEL_TREE contains range trees for all usable indexes. This procedure
5293
finds the SEL_ARG sub-tree for 'index'. The members of a optimizer::SEL_TREE are
6073
5294
ordered in the same way as the members of Parameter::key, thus we first find
6074
5295
the corresponding index in the array Parameter::key. This index is returned
6075
5296
through the variable param_idx, to be used later as argument of
6079
5300
Pointer to the SEL_ARG subtree that corresponds to index.
6080
5301
*/
6081
5302
optimizer::SEL_ARG *get_index_range_tree(uint32_t index,
6082
SEL_TREE* range_tree,
5303
optimizer::SEL_TREE* range_tree,
6083
5304
optimizer::Parameter *param,
6084
5305
uint32_t *param_idx)
6085
5306
{
6158
5379
KEY *index_info,
6159
5380
uint32_t used_key_parts,
6160
5381
uint32_t group_key_parts,
6161
SEL_TREE *range_tree,
5382
optimizer::SEL_TREE *range_tree,
6162
5383
optimizer::SEL_ARG *,
6163
5384
ha_rows quick_prefix_records,
6164
5385
bool have_min,
6360
5581
}
6361
5582
6362
5583
6363
static void print_sel_tree(optimizer::Parameter *param, SEL_TREE *tree, key_map *tree_map, const char *)
6364
{
6365
optimizer::SEL_ARG **key= NULL;
6366
optimizer::SEL_ARG **end= NULL;
6367
int idx= 0;
6368
char buff[1024];
6369
6370
String tmp(buff,sizeof(buff),&my_charset_bin);
6371
tmp.length(0);
6372
for (idx= 0, key=tree->keys, end= key + param->keys;
6373
key != end;
6374
key++, idx++)
6375
{
6376
if (tree_map->test(idx))
6377
{
6378
uint32_t keynr= param->real_keynr[idx];
6379
if (tmp.length())
6380
tmp.append(',');
6381
tmp.append(param->table->key_info[keynr].name);
6382
}
6383
}
6384
if (! tmp.length())
6385
tmp.append(STRING_WITH_LEN("(empty)"));
6386
}
6387
6388
6389
static void print_ror_scans_arr(Table *table,
6390
const char *,
6391
struct st_ror_scan_info **start,
6392
struct st_ror_scan_info **end)
6393
{
6394
char buff[1024];
6395
String tmp(buff,sizeof(buff),&my_charset_bin);
6396
tmp.length(0);
6397
for (; start != end; start++)
6398
{
6399
if (tmp.length())
6400
tmp.append(',');
6401
tmp.append(table->key_info[(*start)->keynr].name);
6402
}
6403
if (! tmp.length())
6404
tmp.append(STRING_WITH_LEN("(empty)"));
6405
}
6406
6407
static void print_ror_scans_vector(Table *table,
6408
const char *,
6409
vector<struct st_ror_scan_info *> &vec)
6410
{
6411
char buff[1024];
6412
String tmp(buff,sizeof(buff),&my_charset_bin);
6413
tmp.length(0);
6414
for (vector<struct st_ror_scan_info *>::iterator it= vec.begin();
6415
it != vec.end();
6416
++it)
6417
{
6418
if (tmp.length())
6419
tmp.append(',');
6420
tmp.append(table->key_info[(*it)->keynr].name);
6421
}
6422
if (! tmp.length())
6423
tmp.append(STRING_WITH_LEN("(empty)"));
6424
}
6425
6426
5584
} /* namespace drizzled */
Loggerhead is a web-based interface for Breezy
Version: 2.0.1