drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
range.cc
1/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2 * vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
3 *
4 * Copyright (C) 2008-2009 Sun Microsystems, Inc.
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; version 2 of the License.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18 */
19
20/*
21 TODO:
22 Fix that MAYBE_KEY are stored in the tree so that we can detect use
23 of full hash keys for queries like:
24
25 select s.id, kws.keyword_id from sites as s,kws where s.id=kws.site_id and kws.keyword_id in (204,205);
26
27*/
28
29/*
30 This cursor contains:
31
32 RangeAnalysisModule
33 A module that accepts a condition, index (or partitioning) description,
34 and builds lists of intervals (in index/partitioning space), such that
35 all possible records that match the condition are contained within the
36 intervals.
37 The entry point for the range analysis module is get_mm_tree() function.
38
39 The lists are returned in form of complicated structure of interlinked
40 optimizer::SEL_TREE/optimizer::SEL_IMERGE/SEL_ARG objects.
41 See quick_range_seq_next, find_used_partitions for examples of how to walk
42 this structure.
43 All direct "users" of this module are located within this cursor, too.
44
45
46 Range/index_merge/groupby-minmax optimizer module
47 A module that accepts a table, condition, and returns
48 - a QUICK_*_SELECT object that can be used to retrieve rows that match
49 the specified condition, or a "no records will match the condition"
50 statement.
51
52 The module entry points are
53 test_quick_select()
54 get_quick_select_for_ref()
55
56
57 Record retrieval code for range/index_merge/groupby-min-max.
58 Implementations of QUICK_*_SELECT classes.
59
60 KeyTupleFormat
61 ~~~~~~~~~~~~~~
62 The code in this cursor (and elsewhere) makes operations on key value tuples.
63 Those tuples are stored in the following format:
64
65 The tuple is a sequence of key part values. The length of key part value
66 depends only on its type (and not depends on the what value is stored)
67
68 KeyTuple: keypart1-data, keypart2-data, ...
69
70 The value of each keypart is stored in the following format:
71
72 keypart_data: [isnull_byte] keypart-value-bytes
73
74 If a keypart may have a NULL value (key_part->field->real_maybe_null() can
75 be used to check this), then the first byte is a NULL indicator with the
76 following valid values:
77 1 - keypart has NULL value.
78 0 - keypart has non-NULL value.
79
80 <questionable-statement> If isnull_byte==1 (NULL value), then the following
81 keypart->length bytes must be 0.
82 </questionable-statement>
83
84 keypart-value-bytes holds the value. Its format depends on the field type.
85 The length of keypart-value-bytes may or may not depend on the value being
86 stored. The default is that length is static and equal to
87 KeyPartInfo::length.
88
89 Key parts with (key_part_flag & HA_BLOB_PART) have length depending of the
90 value:
91
92 keypart-value-bytes: value_length value_bytes
93
94 The value_length part itself occupies HA_KEY_BLOB_LENGTH=2 bytes.
95
96 See key_copy() and key_restore() for code to move data between index tuple
97 and table record
98
99 CAUTION: the above description is only sergefp's understanding of the
100 subject and may omit some details.
101*/
102
103#include <config.h>
104
105#include <math.h>
106#include <float.h>
107
108#include <string>
109#include <vector>
110#include <algorithm>
111
112#include <boost/dynamic_bitset.hpp>
113
114#include <drizzled/check_stack_overrun.h>
115#include <drizzled/error.h>
116#include <drizzled/field/num.h>
117#include <drizzled/internal/iocache.h>
118#include <drizzled/internal/my_sys.h>
119#include <drizzled/item/cmpfunc.h>
120#include <drizzled/optimizer/cost_vector.h>
121#include <drizzled/optimizer/quick_group_min_max_select.h>
122#include <drizzled/optimizer/quick_index_merge_select.h>
123#include <drizzled/optimizer/quick_range.h>
124#include <drizzled/optimizer/quick_range_select.h>
125#include <drizzled/optimizer/quick_ror_intersect_select.h>
126#include <drizzled/optimizer/quick_ror_union_select.h>
127#include <drizzled/optimizer/range.h>
128#include <drizzled/optimizer/range_param.h>
129#include <drizzled/optimizer/sel_arg.h>
130#include <drizzled/optimizer/sel_imerge.h>
131#include <drizzled/optimizer/sel_tree.h>
132#include <drizzled/optimizer/sum.h>
133#include <drizzled/optimizer/table_read_plan.h>
134#include <drizzled/plugin/storage_engine.h>
135#include <drizzled/records.h>
136#include <drizzled/sql_base.h>
137#include <drizzled/sql_select.h>
139#include <drizzled/session.h>
140#include <drizzled/key.h>
141#include <drizzled/unique.h>
142#include <drizzled/temporal.h> /* Needed in get_mm_leaf() for timestamp -> datetime comparisons */
143#include <drizzled/sql_lex.h>
144#include <drizzled/system_variables.h>
145#include <drizzled/key_part_info.h>
146
147using namespace std;
148
149namespace drizzled {
150
151static const int HA_END_SPACE_KEY= 0;
152
153/*
154 Convert double value to #rows. Currently this does floor(), and we
155 might consider using round() instead.
156*/
157static inline ha_rows double2rows(double x)
158{
159 return static_cast<ha_rows>(x);
160}
161
162static unsigned char is_null_string[2]= {1,0};
163
164
207
208static void get_sweep_read_cost(Table *table,
209 ha_rows nrows,
210 bool interrupted,
212{
213 cost->zero();
214 if (table->cursor->primary_key_is_clustered())
215 {
216 cost->setIOCount(table->cursor->read_time(table->getShare()->getPrimaryKey(),
217 static_cast<uint32_t>(nrows),
218 nrows));
219 }
220 else
221 {
222 double n_blocks=
223 ceil(static_cast<double>(table->cursor->stats.data_file_length) / IO_SIZE);
224 double busy_blocks=
225 n_blocks * (1.0 - pow(1.0 - 1.0/n_blocks, static_cast<double>(nrows)));
226 if (busy_blocks < 1.0)
227 busy_blocks= 1.0;
228
229 cost->setIOCount(busy_blocks);
230
231 if (! interrupted)
232 {
233 /* Assume reading is done in one 'sweep' */
234 cost->setAvgIOCost((DISK_SEEK_BASE_COST +
235 DISK_SEEK_PROP_COST*n_blocks/busy_blocks));
236 }
237 }
238}
239
240static optimizer::SEL_TREE * get_mm_parts(optimizer::RangeParameter *param,
241 COND *cond_func,
242 Field *field,
243 Item_func::Functype type,
244 Item *value,
245 Item_result cmp_type);
246
247static optimizer::SEL_ARG *get_mm_leaf(optimizer::RangeParameter *param,
248 COND *cond_func,
249 Field *field,
250 KEY_PART *key_part,
251 Item_func::Functype type,
252 Item *value);
253
254static optimizer::SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond);
255
256static bool is_key_scan_ror(optimizer::Parameter *param, uint32_t keynr, uint8_t nparts);
257
258static ha_rows check_quick_select(Session *session,
259 optimizer::Parameter *param,
260 uint32_t idx,
261 bool index_only,
262 optimizer::SEL_ARG *tree,
263 bool update_tbl_stats,
264 uint32_t *mrr_flags,
265 uint32_t *bufsize,
266 optimizer::CostVector *cost);
267
268static optimizer::RangeReadPlan *get_key_scans_params(Session *session,
269 optimizer::Parameter *param,
270 optimizer::SEL_TREE *tree,
271 bool index_read_must_be_used,
272 bool update_tbl_stats,
273 double read_time);
274
275static
276optimizer::RorIntersectReadPlan *get_best_ror_intersect(const optimizer::Parameter *param,
277 optimizer::SEL_TREE *tree,
278 double read_time,
279 bool *are_all_covering);
280
281static
282optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
283 optimizer::SEL_TREE *tree,
284 double read_time);
285
286static
287optimizer::TableReadPlan *get_best_disjunct_quick(Session *session,
288 optimizer::Parameter *param,
289 optimizer::SEL_IMERGE *imerge,
290 double read_time);
291
292static
293optimizer::GroupMinMaxReadPlan *get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree);
294
295static optimizer::SEL_TREE *tree_and(optimizer::RangeParameter *param,
296 optimizer::SEL_TREE *tree1,
297 optimizer::SEL_TREE *tree2);
298
299static optimizer::SEL_ARG *sel_add(optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);
300
301static optimizer::SEL_ARG *key_and(optimizer::RangeParameter *param,
302 optimizer::SEL_ARG *key1,
303 optimizer::SEL_ARG *key2,
304 uint32_t clone_flag);
305
306static bool get_range(optimizer::SEL_ARG **e1, optimizer::SEL_ARG **e2, optimizer::SEL_ARG *root1);
307
308optimizer::SEL_ARG optimizer::null_element(optimizer::SEL_ARG::IMPOSSIBLE);
309
310static bool null_part_in_key(KEY_PART *key_part,
311 const unsigned char *key,
312 uint32_t length);
313
314bool sel_trees_can_be_ored(optimizer::SEL_TREE *tree1,
315 optimizer::SEL_TREE *tree2,
316 optimizer::RangeParameter *param);
317
318
319
320
321
322
323/*
324 Perform AND operation on two index_merge lists and store result in *im1.
325*/
326
327inline void imerge_list_and_list(List<optimizer::SEL_IMERGE> *im1, List<optimizer::SEL_IMERGE> *im2)
328{
329 im1->concat(im2);
330}
331
332
333/***************************************************************************
334** Basic functions for SqlSelect and QuickRangeSelect
335***************************************************************************/
336
337 /* make a select from mysql info
338 Error is set as following:
339 0 = ok
340 1 = Got some error (out of memory?)
341 */
342
343optimizer::SqlSelect *optimizer::make_select(Table *head,
344 table_map const_tables,
345 table_map read_tables,
346 COND *conds,
347 bool allow_null_cond,
348 int *error)
349{
350 *error= 0;
351
352 if (! conds && ! allow_null_cond)
353 {
354 return 0;
355 }
357 select->read_tables=read_tables;
358 select->const_tables=const_tables;
359 select->head=head;
360 select->cond=conds;
361
362 if (head->sort.io_cache)
363 {
364 memcpy(static_cast<void *>(select->file),
365 static_cast<const void *>(head->sort.io_cache),
366 sizeof(internal::io_cache_st));
367 select->records=(ha_rows) (select->file->end_of_file/
368 head->cursor->ref_length);
369 delete head->sort.io_cache;
370 head->sort.io_cache=0;
371 }
372 return(select);
373}
374
375
376optimizer::SqlSelect::SqlSelect()
377 :
378 quick(NULL),
379 cond(NULL),
380 file(static_cast<internal::io_cache_st *>(memory::sql_calloc(sizeof(internal::io_cache_st)))),
381 free_cond(false)
382{
383 quick_keys.reset();
384 needed_reg.reset();
385 file->clear();
386}
387
388
389void optimizer::SqlSelect::cleanup()
390{
391 delete quick;
392 quick= NULL;
393
394 if (free_cond)
395 {
396 free_cond= 0;
397 delete cond;
398 cond= 0;
399 }
400 file->close_cached_file();
401}
402
403
404optimizer::SqlSelect::~SqlSelect()
405{
406 cleanup();
407}
408
409
410bool optimizer::SqlSelect::check_quick(Session *session,
411 bool force_quick_range,
412 ha_rows limit)
413{
414 key_map tmp;
415 tmp.set();
416 return (test_quick_select(session,
417 tmp,
418 0,
419 limit,
420 force_quick_range,
421 false) < 0);
422}
423
424
425bool optimizer::SqlSelect::skip_record()
426{
427 return (cond ? cond->val_int() == 0 : 0);
428}
429
430
431optimizer::QuickSelectInterface::QuickSelectInterface()
432 :
433 max_used_key_length(0),
434 used_key_parts(0)
435{}
436
437
438/*
439 Find the best index to retrieve first N records in given order
440
441 SYNOPSIS
442 get_index_for_order()
443 table Table to be accessed
444 order Required ordering
445 limit Number of records that will be retrieved
446
447 DESCRIPTION
448 Find the best index that allows to retrieve first #limit records in the
449 given order cheaper then one would retrieve them using full table scan.
450
451 IMPLEMENTATION
452 Run through all table indexes and find the shortest index that allows
453 records to be retrieved in given order. We look for the shortest index
454 as we will have fewer index pages to read with it.
455
456 This function is used only by UPDATE/DELETE, so we take into account how
457 the UPDATE/DELETE code will work:
458 * index can only be scanned in forward direction
459 * HA_EXTRA_KEYREAD will not be used
460 Perhaps these assumptions could be relaxed.
461
462 RETURN
463 Number of the index that produces the required ordering in the cheapest way
464 MAX_KEY if no such index was found.
465*/
466
467uint32_t optimizer::get_index_for_order(Table *table, Order *order, ha_rows limit)
468{
469 uint32_t idx;
470 uint32_t match_key= MAX_KEY, match_key_len= MAX_KEY_LENGTH + 1;
471 Order *ord;
472
473 for (ord= order; ord; ord= ord->next)
474 if (!ord->asc)
475 return MAX_KEY;
476
477 for (idx= 0; idx < table->getShare()->sizeKeys(); idx++)
478 {
479 if (!(table->keys_in_use_for_query.test(idx)))
480 continue;
481 KeyPartInfo *keyinfo= table->key_info[idx].key_part;
482 uint32_t n_parts= table->key_info[idx].key_parts;
483 uint32_t partno= 0;
484
485 /*
486 The below check is sufficient considering we now have either BTREE
487 indexes (records are returned in order for any index prefix) or HASH
488 indexes (records are not returned in order for any index prefix).
489 */
490 if (! (table->index_flags(idx) & HA_READ_ORDER))
491 continue;
492 for (ord= order; ord && partno < n_parts; ord= ord->next, partno++)
493 {
494 Item *item= order->item[0];
495 if (! (item->type() == Item::FIELD_ITEM &&
496 ((Item_field*)item)->field->eq(keyinfo[partno].field)))
497 break;
498 }
499
500 if (! ord && table->key_info[idx].key_length < match_key_len)
501 {
502 /*
503 Ok, the ordering is compatible and this key is shorter then
504 previous match (we want shorter keys as we'll have to read fewer
505 index pages for the same number of records)
506 */
507 match_key= idx;
508 match_key_len= table->key_info[idx].key_length;
509 }
510 }
511
512 if (match_key != MAX_KEY)
513 {
514 /*
515 Found an index that allows records to be retrieved in the requested
516 order. Now we'll check if using the index is cheaper then doing a table
517 scan.
518 */
519 double full_scan_time= table->cursor->scan_time();
520 double index_scan_time= table->cursor->read_time(match_key, 1, limit);
521 if (index_scan_time > full_scan_time)
522 match_key= MAX_KEY;
523 }
524 return match_key;
525}
526
527
528
529/*
530 Fill param->needed_fields with bitmap of fields used in the query.
531 SYNOPSIS
532 fill_used_fields_bitmap()
533 param Parameter from test_quick_select function.
534
535 NOTES
536 Clustered PK members are not put into the bitmap as they are implicitly
537 present in all keys (and it is impossible to avoid reading them).
538 RETURN
539 0 Ok
540 1 Out of memory.
541*/
542
543static int fill_used_fields_bitmap(optimizer::Parameter *param)
544{
545 Table *table= param->table;
546 uint32_t pk;
547 param->tmp_covered_fields.clear();
548 param->needed_fields.resize(table->getShare()->sizeFields());
549 param->needed_fields.reset();
550
551 param->needed_fields|= *table->read_set;
552 param->needed_fields|= *table->write_set;
553
554 pk= param->table->getShare()->getPrimaryKey();
555 if (pk != MAX_KEY && param->table->cursor->primary_key_is_clustered())
556 {
557 /* The table uses clustered PK and it is not internally generated */
558 KeyPartInfo *key_part= param->table->key_info[pk].key_part;
559 KeyPartInfo *key_part_end= key_part +
560 param->table->key_info[pk].key_parts;
561 for (;key_part != key_part_end; ++key_part)
562 param->needed_fields.reset(key_part->fieldnr-1);
563 }
564 return 0;
565}
566
567
568/*
569 Test if a key can be used in different ranges
570
571 SYNOPSIS
572 SqlSelect::test_quick_select()
573 session Current thread
574 keys_to_use Keys to use for range retrieval
575 prev_tables Tables assumed to be already read when the scan is
576 performed (but not read at the moment of this call)
577 limit Query limit
578 force_quick_range Prefer to use range (instead of full table scan) even
579 if it is more expensive.
580
581 NOTES
582 Updates the following in the select parameter:
583 needed_reg - Bits for keys with may be used if all prev regs are read
584 quick - Parameter to use when reading records.
585
586 In the table struct the following information is updated:
587 quick_keys - Which keys can be used
588 quick_rows - How many rows the key matches
589 quick_condition_rows - E(# rows that will satisfy the table condition)
590
591 IMPLEMENTATION
592 quick_condition_rows value is obtained as follows:
593
594 It is a minimum of E(#output rows) for all considered table access
595 methods (range and index_merge accesses over various indexes).
596
597 The obtained value is not a true E(#rows that satisfy table condition)
598 but rather a pessimistic estimate. To obtain a true E(#...) one would
599 need to combine estimates of various access methods, taking into account
600 correlations between sets of rows they will return.
601
602 For example, if values of tbl.key1 and tbl.key2 are independent (a right
603 assumption if we have no information about their correlation) then the
604 correct estimate will be:
605
606 E(#rows("tbl.key1 < c1 AND tbl.key2 < c2")) =
607 = E(#rows(tbl.key1 < c1)) / total_rows(tbl) * E(#rows(tbl.key2 < c2)
608
609 which is smaller than
610
611 MIN(E(#rows(tbl.key1 < c1), E(#rows(tbl.key2 < c2)))
612
613 which is currently produced.
614
615 TODO
616 * Change the value returned in quick_condition_rows from a pessimistic
617 estimate to true E(#rows that satisfy table condition).
618 (we can re-use some of E(#rows) calcuation code from index_merge/intersection
619 for this)
620
621 * Check if this function really needs to modify keys_to_use, and change the
622 code to pass it by reference if it doesn't.
623
624 * In addition to force_quick_range other means can be (an usually are) used
625 to make this function prefer range over full table scan. Figure out if
626 force_quick_range is really needed.
627
628 RETURN
629 -1 if impossible select (i.e. certainly no rows will be selected)
630 0 if can't use quick_select
631 1 if found usable ranges and quick select has been successfully created.
632*/
633
634int optimizer::SqlSelect::test_quick_select(Session *session,
635 key_map keys_to_use,
636 table_map prev_tables,
637 ha_rows limit,
638 bool force_quick_range,
639 bool ordered_output)
640{
641 uint32_t idx;
642 double scan_time;
643
644 delete quick;
645 quick= NULL;
646
647 needed_reg.reset();
648 quick_keys.reset();
649 if (keys_to_use.none())
650 return 0;
651 records= head->cursor->stats.records;
652 if (!records)
653 records++;
654 scan_time= (double) records / TIME_FOR_COMPARE + 1;
655 read_time= (double) head->cursor->scan_time() + scan_time + 1.1;
656 if (head->force_index)
657 scan_time= read_time= DBL_MAX;
658 if (limit < records)
659 read_time= (double) records + scan_time + 1; // Force to use index
660 else if (read_time <= 2.0 && !force_quick_range)
661 return 0; /* No need for quick select */
662
663 keys_to_use&= head->keys_in_use_for_query;
664 if (keys_to_use.any())
665 {
666 memory::Root alloc;
667 optimizer::SEL_TREE *tree= NULL;
668 KEY_PART *key_parts;
669 KeyInfo *key_info;
670 optimizer::Parameter param;
671
672 if (check_stack_overrun(session, 2*STACK_MIN_SIZE, NULL))
673 return 0; // Fatal error flag is set
674
675 /* set up parameter that is passed to all functions */
676 param.session= session;
677 param.prev_tables= prev_tables | const_tables;
678 param.read_tables= read_tables;
679 param.current_table= head->map;
680 param.table=head;
681 param.keys=0;
682 param.mem_root= &alloc;
683 param.old_root= session->mem_root;
684 param.needed_reg= &needed_reg;
685 param.imerge_cost_buff_size= 0;
686 param.using_real_indexes= true;
687 param.remove_jump_scans= true;
688 param.force_default_mrr= ordered_output;
689
690 session->no_errors=1; // Don't warn about NULL
691 alloc.init(session->variables.range_alloc_block_size);
692 param.key_parts= new (alloc) KEY_PART[head->getShare()->key_parts];
693 if (fill_used_fields_bitmap(&param))
694 {
695 session->no_errors=0;
696 alloc.free_root(MYF(0)); // Return memory & allocator
697
698 return 0; // Can't use range
699 }
700 key_parts= param.key_parts;
701 session->mem_root= &alloc;
702
703 /*
704 Make an array with description of all key parts of all table keys.
705 This is used in get_mm_parts function.
706 */
707 key_info= head->key_info;
708 for (idx=0 ; idx < head->getShare()->sizeKeys() ; idx++, key_info++)
709 {
710 KeyPartInfo *key_part_info;
711 if (! keys_to_use.test(idx))
712 continue;
713
714 param.key[param.keys]=key_parts;
715 key_part_info= key_info->key_part;
716 for (uint32_t part=0;
717 part < key_info->key_parts;
718 part++, key_parts++, key_part_info++)
719 {
720 key_parts->key= param.keys;
721 key_parts->part= part;
722 key_parts->length= key_part_info->length;
723 key_parts->store_length= key_part_info->store_length;
724 key_parts->field= key_part_info->field;
725 key_parts->null_bit= key_part_info->null_bit;
726 /* Only HA_PART_KEY_SEG is used */
727 key_parts->flag= (uint8_t) key_part_info->key_part_flag;
728 }
729 param.real_keynr[param.keys++]=idx;
730 }
731 param.key_parts_end=key_parts;
732 param.alloced_sel_args= 0;
733
734 /* Calculate cost of full index read for the shortest covering index */
735 if (!head->covering_keys.none())
736 {
737 int key_for_use= head->find_shortest_key(&head->covering_keys);
738 double key_read_time=
739 param.table->cursor->index_only_read_time(key_for_use, records) +
740 (double) records / TIME_FOR_COMPARE;
741 if (key_read_time < read_time)
742 read_time= key_read_time;
743 }
744
745 optimizer::TableReadPlan *best_trp= NULL;
746 optimizer::GroupMinMaxReadPlan *group_trp= NULL;
747 double best_read_time= read_time;
748
749 if (cond)
750 {
751 if ((tree= get_mm_tree(&param,cond)))
752 {
753 if (tree->type == optimizer::SEL_TREE::IMPOSSIBLE)
754 {
755 records=0L; /* Return -1 from this function. */
756 read_time= (double) HA_POS_ERROR;
757 goto free_mem;
758 }
759 /*
760 If the tree can't be used for range scans, proceed anyway, as we
761 can construct a group-min-max quick select
762 */
763 if (tree->type != optimizer::SEL_TREE::KEY && tree->type != optimizer::SEL_TREE::KEY_SMALLER)
764 tree= NULL;
765 }
766 }
767
768 /*
769 Try to construct a QuickGroupMinMaxSelect.
770 Notice that it can be constructed no matter if there is a range tree.
771 */
772 group_trp= get_best_group_min_max(&param, tree);
773 if (group_trp)
774 {
775 param.table->quick_condition_rows= min(group_trp->records,
776 head->cursor->stats.records);
777 if (group_trp->read_cost < best_read_time)
778 {
779 best_trp= group_trp;
780 best_read_time= best_trp->read_cost;
781 }
782 }
783
784 if (tree)
785 {
786 /*
787 It is possible to use a range-based quick select (but it might be
788 slower than 'all' table scan).
789 */
790 if (tree->merges.is_empty())
791 {
792 optimizer::RangeReadPlan *range_trp= NULL;
793 optimizer::RorIntersectReadPlan *rori_trp= NULL;
794 bool can_build_covering= false;
795
796 /* Get best 'range' plan and prepare data for making other plans */
797 if ((range_trp= get_key_scans_params(session, &param, tree, false, true,
798 best_read_time)))
799 {
800 best_trp= range_trp;
801 best_read_time= best_trp->read_cost;
802 }
803
804 /*
805 Simultaneous key scans and row deletes on several Cursor
806 objects are not allowed so don't use ROR-intersection for
807 table deletes.
808 */
809 if ((session->lex().sql_command != SQLCOM_DELETE))
810 {
811 /*
812 Get best non-covering ROR-intersection plan and prepare data for
813 building covering ROR-intersection.
814 */
815 if ((rori_trp= get_best_ror_intersect(&param, tree, best_read_time,
816 &can_build_covering)))
817 {
818 best_trp= rori_trp;
819 best_read_time= best_trp->read_cost;
820 /*
821 Try constructing covering ROR-intersect only if it looks possible
822 and worth doing.
823 */
824 if (!rori_trp->is_covering && can_build_covering &&
825 (rori_trp= get_best_covering_ror_intersect(&param, tree,
826 best_read_time)))
827 best_trp= rori_trp;
828 }
829 }
830 }
831 else
832 {
833 /* Try creating index_merge/ROR-union scan. */
834 optimizer::SEL_IMERGE *imerge= NULL;
835 optimizer::TableReadPlan *best_conj_trp= NULL;
836 optimizer::TableReadPlan *new_conj_trp= NULL;
837 List<optimizer::SEL_IMERGE>::iterator it(tree->merges.begin());
838 while ((imerge= it++))
839 {
840 new_conj_trp= get_best_disjunct_quick(session, &param, imerge, best_read_time);
841 if (new_conj_trp)
842 set_if_smaller(param.table->quick_condition_rows,
843 new_conj_trp->records);
844 if (!best_conj_trp || (new_conj_trp && new_conj_trp->read_cost <
845 best_conj_trp->read_cost))
846 best_conj_trp= new_conj_trp;
847 }
848 if (best_conj_trp)
849 best_trp= best_conj_trp;
850 }
851 }
852
853 session->mem_root= param.old_root;
854
855 /* If we got a read plan, create a quick select from it. */
856 if (best_trp)
857 {
858 records= best_trp->records;
859 if (! (quick= best_trp->make_quick(&param, true)) || quick->init())
860 {
861 delete quick;
862 quick= NULL;
863 }
864 }
865
866 free_mem:
867 alloc.free_root(MYF(0)); // Return memory & allocator
868 session->mem_root= param.old_root;
869 session->no_errors=0;
870 }
871
872 /*
873 Assume that if the user is using 'limit' we will only need to scan
874 limit rows if we are using a key
875 */
876 return(records ? test(quick) : -1);
877}
878
879/*
880 Get best plan for a optimizer::SEL_IMERGE disjunctive expression.
881 SYNOPSIS
882 get_best_disjunct_quick()
883 session
884 param Parameter from check_quick_select function
885 imerge Expression to use
886 read_time Don't create scans with cost > read_time
887
888 NOTES
889 index_merge cost is calculated as follows:
890 index_merge_cost =
891 cost(index_reads) + (see #1)
892 cost(rowid_to_row_scan) + (see #2)
893 cost(unique_use) (see #3)
894
895 1. cost(index_reads) =SUM_i(cost(index_read_i))
896 For non-CPK scans,
897 cost(index_read_i) = {cost of ordinary 'index only' scan}
898 For CPK scan,
899 cost(index_read_i) = {cost of non-'index only' scan}
900
901 2. cost(rowid_to_row_scan)
902 If table PK is clustered then
903 cost(rowid_to_row_scan) =
904 {cost of ordinary clustered PK scan with n_ranges=n_rows}
905
906 Otherwise, we use the following model to calculate costs:
907 We need to retrieve n_rows rows from cursor that occupies n_blocks blocks.
908 We assume that offsets of rows we need are independent variates with
909 uniform distribution in [0..max_file_offset] range.
910
911 We'll denote block as "busy" if it contains row(s) we need to retrieve
912 and "empty" if doesn't contain rows we need.
913
914 Probability that a block is empty is (1 - 1/n_blocks)^n_rows (this
915 applies to any block in cursor). Let x_i be a variate taking value 1 if
916 block #i is empty and 0 otherwise.
917
918 Then E(x_i) = (1 - 1/n_blocks)^n_rows;
919
920 E(n_empty_blocks) = E(sum(x_i)) = sum(E(x_i)) =
921 = n_blocks * ((1 - 1/n_blocks)^n_rows) =
922 ~= n_blocks * exp(-n_rows/n_blocks).
923
924 E(n_busy_blocks) = n_blocks*(1 - (1 - 1/n_blocks)^n_rows) =
925 ~= n_blocks * (1 - exp(-n_rows/n_blocks)).
926
927 Average size of "hole" between neighbor non-empty blocks is
928 E(hole_size) = n_blocks/E(n_busy_blocks).
929
930 The total cost of reading all needed blocks in one "sweep" is:
931
932 E(n_busy_blocks)*
933 (DISK_SEEK_BASE_COST + DISK_SEEK_PROP_COST*n_blocks/E(n_busy_blocks)).
934
935 3. Cost of Unique use is calculated in Unique::get_use_cost function.
936
937 ROR-union cost is calculated in the same way index_merge, but instead of
938 Unique a priority queue is used.
939
940 RETURN
941 Created read plan
942 NULL - Out of memory or no read scan could be built.
943*/
944
945static
946optimizer::TableReadPlan *get_best_disjunct_quick(Session *session,
947 optimizer::Parameter *param,
948 optimizer::SEL_IMERGE *imerge,
949 double read_time)
950{
951 optimizer::SEL_TREE **ptree= NULL;
952 optimizer::IndexMergeReadPlan *imerge_trp= NULL;
953 uint32_t n_child_scans= imerge->trees_next - imerge->trees;
954 optimizer::RangeReadPlan **range_scans= NULL;
955 optimizer::RangeReadPlan **cur_child= NULL;
956 optimizer::RangeReadPlan **cpk_scan= NULL;
957 bool imerge_too_expensive= false;
958 double imerge_cost= 0.0;
959 ha_rows cpk_scan_records= 0;
960 ha_rows non_cpk_scan_records= 0;
961 bool pk_is_clustered= param->table->cursor->primary_key_is_clustered();
962 bool all_scans_ror_able= true;
963 bool all_scans_rors= true;
964 uint32_t unique_calc_buff_size;
965 optimizer::TableReadPlan **roru_read_plans= NULL;
966 optimizer::TableReadPlan **cur_roru_plan= NULL;
967 double roru_index_costs;
968 ha_rows roru_total_records;
969 double roru_intersect_part= 1.0;
970
971 range_scans= new (*param->mem_root) optimizer::RangeReadPlan*[n_child_scans];
972
973 /*
974 Collect best 'range' scan for each of disjuncts, and, while doing so,
975 analyze possibility of ROR scans. Also calculate some values needed by
976 other parts of the code.
977 */
978 for (ptree= imerge->trees, cur_child= range_scans; ptree != imerge->trees_next; ptree++, cur_child++)
979 {
980 if (!(*cur_child= get_key_scans_params(session, param, *ptree, true, false, read_time)))
981 {
982 /*
983 One of index scans in this index_merge is more expensive than entire
984 table read for another available option. The entire index_merge (and
985 any possible ROR-union) will be more expensive then, too. We continue
986 here only to update SqlSelect members.
987 */
988 imerge_too_expensive= true;
989 }
990 if (imerge_too_expensive)
991 continue;
992
993 imerge_cost += (*cur_child)->read_cost;
994 all_scans_ror_able &= ((*ptree)->n_ror_scans > 0);
995 all_scans_rors &= (*cur_child)->is_ror;
996 if (pk_is_clustered &&
997 param->real_keynr[(*cur_child)->key_idx] ==
998 param->table->getShare()->getPrimaryKey())
999 {
1000 cpk_scan= cur_child;
1001 cpk_scan_records= (*cur_child)->records;
1002 }
1003 else
1004 non_cpk_scan_records += (*cur_child)->records;
1005 }
1006
1007 if (imerge_too_expensive || (imerge_cost > read_time) ||
1008 ((non_cpk_scan_records+cpk_scan_records >= param->table->cursor->stats.records) && compare_ne_double(read_time, DBL_MAX)))
1009 {
1010 /*
1011 Bail out if it is obvious that both index_merge and ROR-union will be
1012 more expensive
1013 */
1014 return NULL;
1015 }
1016 if (all_scans_rors)
1017 {
1018 roru_read_plans= (optimizer::TableReadPlan **) range_scans;
1019 goto skip_to_ror_scan;
1020 }
1021 if (cpk_scan)
1022 {
1023 /*
1024 Add one ROWID comparison for each row retrieved on non-CPK scan. (it
1025 is done in QuickRangeSelect::row_in_ranges)
1026 */
1027 imerge_cost += non_cpk_scan_records / TIME_FOR_COMPARE_ROWID;
1028 }
1029
1030 /* Calculate cost(rowid_to_row_scan) */
1031 {
1032 optimizer::CostVector sweep_cost;
1033 Join *join= param->session->lex().select_lex.join;
1034 bool is_interrupted= test(join && join->tables == 1);
1035 get_sweep_read_cost(param->table, non_cpk_scan_records, is_interrupted,
1036 &sweep_cost);
1037 imerge_cost += sweep_cost.total_cost();
1038 }
1039 if (imerge_cost > read_time)
1040 goto build_ror_index_merge;
1041
1042 /* Add Unique operations cost */
1043 unique_calc_buff_size=
1044 Unique::get_cost_calc_buff_size((ulong)non_cpk_scan_records,
1045 param->table->cursor->ref_length,
1046 param->session->variables.sortbuff_size);
1047 if (param->imerge_cost_buff_size < unique_calc_buff_size)
1048 {
1049 param->imerge_cost_buff= (uint*)param->mem_root->alloc(unique_calc_buff_size);
1050 param->imerge_cost_buff_size= unique_calc_buff_size;
1051 }
1052
1053 imerge_cost +=
1054 Unique::get_use_cost(param->imerge_cost_buff, (uint32_t)non_cpk_scan_records,
1055 param->table->cursor->ref_length,
1056 param->session->variables.sortbuff_size);
1057 if (imerge_cost < read_time)
1058 {
1059 imerge_trp= new (*param->mem_root) optimizer::IndexMergeReadPlan;
1060 imerge_trp->read_cost= imerge_cost;
1061 imerge_trp->records= non_cpk_scan_records + cpk_scan_records;
1062 imerge_trp->records= min(imerge_trp->records, param->table->cursor->stats.records);
1063 imerge_trp->range_scans= range_scans;
1064 imerge_trp->range_scans_end= range_scans + n_child_scans;
1065 read_time= imerge_cost;
1066 }
1067
1068build_ror_index_merge:
1069 if (!all_scans_ror_able || param->session->lex().sql_command == SQLCOM_DELETE)
1070 return(imerge_trp);
1071
1072 /* Ok, it is possible to build a ROR-union, try it. */
1073 bool dummy;
1074 roru_read_plans= new (*param->mem_root) optimizer::TableReadPlan*[n_child_scans];
1075skip_to_ror_scan:
1076 roru_index_costs= 0.0;
1077 roru_total_records= 0;
1078 cur_roru_plan= roru_read_plans;
1079
1080 /* Find 'best' ROR scan for each of trees in disjunction */
1081 for (ptree= imerge->trees, cur_child= range_scans;
1082 ptree != imerge->trees_next;
1083 ptree++, cur_child++, cur_roru_plan++)
1084 {
1085 /*
1086 Assume the best ROR scan is the one that has cheapest full-row-retrieval
1087 scan cost.
1088 Also accumulate index_only scan costs as we'll need them to calculate
1089 overall index_intersection cost.
1090 */
1091 double cost;
1092 if ((*cur_child)->is_ror)
1093 {
1094 /* Ok, we have index_only cost, now get full rows scan cost */
1095 cost= param->table->cursor->
1096 read_time(param->real_keynr[(*cur_child)->key_idx], 1,
1097 (*cur_child)->records) +
1098 static_cast<double>((*cur_child)->records) / TIME_FOR_COMPARE;
1099 }
1100 else
1101 cost= read_time;
1102
1103 optimizer::TableReadPlan *prev_plan= *cur_child;
1104 if (!(*cur_roru_plan= get_best_ror_intersect(param, *ptree, cost,
1105 &dummy)))
1106 {
1107 if (prev_plan->is_ror)
1108 *cur_roru_plan= prev_plan;
1109 else
1110 return(imerge_trp);
1111 roru_index_costs += (*cur_roru_plan)->read_cost;
1112 }
1113 else
1114 roru_index_costs +=
1115 ((optimizer::RorIntersectReadPlan*)(*cur_roru_plan))->index_scan_costs;
1116 roru_total_records += (*cur_roru_plan)->records;
1117 roru_intersect_part *= (*cur_roru_plan)->records /
1118 param->table->cursor->stats.records;
1119 }
1120
1121 /*
1122 rows to retrieve=
1123 SUM(rows_in_scan_i) - table_rows * PROD(rows_in_scan_i / table_rows).
1124 This is valid because index_merge construction guarantees that conditions
1125 in disjunction do not share key parts.
1126 */
1127 roru_total_records -= (ha_rows)(roru_intersect_part*
1128 param->table->cursor->stats.records);
1129 /* ok, got a ROR read plan for each of the disjuncts
1130 Calculate cost:
1131 cost(index_union_scan(scan_1, ... scan_n)) =
1132 SUM_i(cost_of_index_only_scan(scan_i)) +
1133 queue_use_cost(rowid_len, n) +
1134 cost_of_row_retrieval
1135 See get_merge_buffers_cost function for queue_use_cost formula derivation.
1136 */
1137 double roru_total_cost;
1138 {
1139 optimizer::CostVector sweep_cost;
1140 Join *join= param->session->lex().select_lex.join;
1141 bool is_interrupted= test(join && join->tables == 1);
1142 get_sweep_read_cost(param->table, roru_total_records, is_interrupted,
1143 &sweep_cost);
1144 roru_total_cost= roru_index_costs +
1145 static_cast<double>(roru_total_records)*log((double)n_child_scans) /
1146 (TIME_FOR_COMPARE_ROWID * M_LN2) +
1147 sweep_cost.total_cost();
1148 }
1149
1150 optimizer::RorUnionReadPlan *roru= NULL;
1151 if (roru_total_cost < read_time)
1152 {
1153 if ((roru= new (*param->mem_root) optimizer::RorUnionReadPlan))
1154 {
1155 roru->first_ror= roru_read_plans;
1156 roru->last_ror= roru_read_plans + n_child_scans;
1157 roru->read_cost= roru_total_cost;
1158 roru->records= roru_total_records;
1159 return roru;
1160 }
1161 }
1162 return(imerge_trp);
1163}
1164
1165
1166
1167/*
1168 Create optimizer::RorScanInfo* structure with a single ROR scan on index idx using
1169 sel_arg set of intervals.
1170
1171 SYNOPSIS
1172 make_ror_scan()
1173 param Parameter from test_quick_select function
1174 idx Index of key in param->keys
1175 sel_arg Set of intervals for a given key
1176
1177 RETURN
1178 NULL - out of memory
1179 ROR scan structure containing a scan for {idx, sel_arg}
1180*/
1181
1182static
1183optimizer::RorScanInfo *make_ror_scan(const optimizer::Parameter *param, int idx, optimizer::SEL_ARG *sel_arg)
1184{
1185 uint32_t keynr;
1186 optimizer::RorScanInfo* ror_scan= new (*param->mem_root) optimizer::RorScanInfo;
1187
1188 ror_scan->idx= idx;
1189 ror_scan->keynr= keynr= param->real_keynr[idx];
1190 ror_scan->key_rec_length= (param->table->key_info[keynr].key_length +
1191 param->table->cursor->ref_length);
1192 ror_scan->sel_arg= sel_arg;
1193 ror_scan->records= param->table->quick_rows[keynr];
1194
1195 ror_scan->covered_fields_size= param->table->getShare()->sizeFields();
1196 boost::dynamic_bitset<> tmp_bitset(param->table->getShare()->sizeFields());
1197 tmp_bitset.reset();
1198
1199 KeyPartInfo *key_part= param->table->key_info[keynr].key_part;
1200 KeyPartInfo *key_part_end= key_part +
1201 param->table->key_info[keynr].key_parts;
1202 for (; key_part != key_part_end; ++key_part)
1203 {
1204 if (param->needed_fields.test(key_part->fieldnr-1))
1205 tmp_bitset.set(key_part->fieldnr-1);
1206 }
1207 double rows= param->table->quick_rows[ror_scan->keynr];
1208 ror_scan->index_read_cost=
1209 param->table->cursor->index_only_read_time(ror_scan->keynr, rows);
1210 ror_scan->covered_fields= tmp_bitset.to_ulong();
1211 return ror_scan;
1212}
1213
1214
1215/*
1216 Compare two optimizer::RorScanInfo** by E(#records_matched) * key_record_length.
1217 SYNOPSIS
1218 cmp_ror_scan_info()
1219 a ptr to first compared value
1220 b ptr to second compared value
1221
1222 RETURN
1223 -1 a < b
1224 0 a = b
1225 1 a > b
1226*/
1227
1228static int cmp_ror_scan_info(optimizer::RorScanInfo** a, optimizer::RorScanInfo** b)
1229{
1230 double val1= static_cast<double>((*a)->records) * (*a)->key_rec_length;
1231 double val2= static_cast<double>((*b)->records) * (*b)->key_rec_length;
1232 return (val1 < val2)? -1: (compare_double(val1, val2))? 0 : 1;
1233}
1234
1235
1236/*
1237 Compare two optimizer::RorScanInfo** by
1238 (#covered fields in F desc,
1239 #components asc,
1240 number of first not covered component asc)
1241
1242 SYNOPSIS
1243 cmp_ror_scan_info_covering()
1244 a ptr to first compared value
1245 b ptr to second compared value
1246
1247 RETURN
1248 -1 a < b
1249 0 a = b
1250 1 a > b
1251*/
1252
1253static int cmp_ror_scan_info_covering(optimizer::RorScanInfo** a, optimizer::RorScanInfo** b)
1254{
1255 if ((*a)->used_fields_covered > (*b)->used_fields_covered)
1256 return -1;
1257 if ((*a)->used_fields_covered < (*b)->used_fields_covered)
1258 return 1;
1259 if ((*a)->key_components < (*b)->key_components)
1260 return -1;
1261 if ((*a)->key_components > (*b)->key_components)
1262 return 1;
1263 if ((*a)->first_uncovered_field < (*b)->first_uncovered_field)
1264 return -1;
1265 if ((*a)->first_uncovered_field > (*b)->first_uncovered_field)
1266 return 1;
1267 return 0;
1268}
1269
1270/* Auxiliary structure for incremental ROR-intersection creation */
1271typedef struct st_ror_intersect_info
1272{
1273 st_ror_intersect_info()
1274 :
1275 param(NULL),
1276 covered_fields(),
1277 out_rows(0.0),
1278 is_covering(false),
1279 index_records(0),
1280 index_scan_costs(0.0),
1281 total_cost(0.0)
1282 {}
1283
1284 st_ror_intersect_info(const optimizer::Parameter *in_param)
1285 :
1286 param(in_param),
1287 covered_fields(in_param->table->getShare()->sizeFields()),
1288 out_rows(in_param->table->cursor->stats.records),
1289 is_covering(false),
1290 index_records(0),
1291 index_scan_costs(0.0),
1292 total_cost(0.0)
1293 {
1294 covered_fields.reset();
1295 }
1296
1297 const optimizer::Parameter *param;
1298 boost::dynamic_bitset<> covered_fields; /* union of fields covered by all scans */
1299 /*
1300 Fraction of table records that satisfies conditions of all scans.
1301 This is the number of full records that will be retrieved if a
1302 non-index_only index intersection will be employed.
1303 */
1304 double out_rows;
1305 /* true if covered_fields is a superset of needed_fields */
1306 bool is_covering;
1307
1308 ha_rows index_records; /* sum(#records to look in indexes) */
1309 double index_scan_costs; /* SUM(cost of 'index-only' scans) */
1310 double total_cost;
1311} ROR_INTERSECT_INFO;
1312
1313
1314static void ror_intersect_cpy(ROR_INTERSECT_INFO *dst,
1315 const ROR_INTERSECT_INFO *src)
1316{
1317 dst->param= src->param;
1318 dst->covered_fields= src->covered_fields;
1319 dst->out_rows= src->out_rows;
1320 dst->is_covering= src->is_covering;
1321 dst->index_records= src->index_records;
1322 dst->index_scan_costs= src->index_scan_costs;
1323 dst->total_cost= src->total_cost;
1324}
1325
1326
1327/*
1328 Get selectivity of a ROR scan wrt ROR-intersection.
1329
1330 SYNOPSIS
1331 ror_scan_selectivity()
1332 info ROR-interection
1333 scan ROR scan
1334
1335 NOTES
1336 Suppose we have a condition on several keys
1337 cond=k_11=c_11 AND k_12=c_12 AND ... // parts of first key
1338 k_21=c_21 AND k_22=c_22 AND ... // parts of second key
1339 ...
1340 k_n1=c_n1 AND k_n3=c_n3 AND ... (1) //parts of the key used by *scan
1341
1342 where k_ij may be the same as any k_pq (i.e. keys may have common parts).
1343
1344 A full row is retrieved if entire condition holds.
1345
1346 The recursive procedure for finding P(cond) is as follows:
1347
1348 First step:
1349 Pick 1st part of 1st key and break conjunction (1) into two parts:
1350 cond= (k_11=c_11 AND R)
1351
1352 Here R may still contain condition(s) equivalent to k_11=c_11.
1353 Nevertheless, the following holds:
1354
1355 P(k_11=c_11 AND R) = P(k_11=c_11) * P(R | k_11=c_11).
1356
1357 Mark k_11 as fixed field (and satisfied condition) F, save P(F),
1358 save R to be cond and proceed to recursion step.
1359
1360 Recursion step:
1361 We have a set of fixed fields/satisfied conditions) F, probability P(F),
1362 and remaining conjunction R
1363 Pick next key part on current key and its condition "k_ij=c_ij".
1364 We will add "k_ij=c_ij" into F and update P(F).
1365 Lets denote k_ij as t, R = t AND R1, where R1 may still contain t. Then
1366
1367 P((t AND R1)|F) = P(t|F) * P(R1|t|F) = P(t|F) * P(R1|(t AND F)) (2)
1368
1369 (where '|' mean conditional probability, not "or")
1370
1371 Consider the first multiplier in (2). One of the following holds:
1372 a) F contains condition on field used in t (i.e. t AND F = F).
1373 Then P(t|F) = 1
1374
1375 b) F doesn't contain condition on field used in t. Then F and t are
1376 considered independent.
1377
1378 P(t|F) = P(t|(fields_before_t_in_key AND other_fields)) =
1379 = P(t|fields_before_t_in_key).
1380
1381 P(t|fields_before_t_in_key) = #records(fields_before_t_in_key) /
1382 #records(fields_before_t_in_key, t)
1383
1384 The second multiplier is calculated by applying this step recursively.
1385
1386 IMPLEMENTATION
1387 This function calculates the result of application of the "recursion step"
1388 described above for all fixed key members of a single key, accumulating set
1389 of covered fields, selectivity, etc.
1390
1391 The calculation is conducted as follows:
1392 Lets denote #records(keypart1, ... keypartK) as n_k. We need to calculate
1393
1394 n_{k1} n_{k2}
1395 --------- * --------- * .... (3)
1396 n_{k1-1} n_{k2-1}
1397
1398 where k1,k2,... are key parts which fields were not yet marked as fixed
1399 ( this is result of application of option b) of the recursion step for
1400 parts of a single key).
1401 Since it is reasonable to expect that most of the fields are not marked
1402 as fixed, we calculate (3) as
1403
1404 n_{i1} n_{i2}
1405 (3) = n_{max_key_part} / ( --------- * --------- * .... )
1406 n_{i1-1} n_{i2-1}
1407
1408 where i1,i2, .. are key parts that were already marked as fixed.
1409
1410 In order to minimize number of expensive records_in_range calls we group
1411 and reduce adjacent fractions.
1412
1413 RETURN
1414 Selectivity of given ROR scan.
1415*/
1416
1417static double ror_scan_selectivity(const ROR_INTERSECT_INFO *info,
1418 const optimizer::RorScanInfo *scan)
1419{
1420 double selectivity_mult= 1.0;
1421 KeyPartInfo *key_part= info->param->table->key_info[scan->keynr].key_part;
1422 unsigned char key_val[MAX_KEY_LENGTH+MAX_FIELD_WIDTH]; /* key values tuple */
1423 unsigned char *key_ptr= key_val;
1424 optimizer::SEL_ARG *sel_arg= NULL;
1425 optimizer::SEL_ARG *tuple_arg= NULL;
1426 key_part_map keypart_map= 0;
1427 bool cur_covered;
1428 bool prev_covered= test(info->covered_fields.test(key_part->fieldnr-1));
1429 key_range min_range;
1430 key_range max_range;
1431 min_range.key= key_val;
1432 min_range.flag= HA_READ_KEY_EXACT;
1433 max_range.key= key_val;
1434 max_range.flag= HA_READ_AFTER_KEY;
1435 ha_rows prev_records= info->param->table->cursor->stats.records;
1436
1437 for (sel_arg= scan->sel_arg; sel_arg;
1438 sel_arg= sel_arg->next_key_part)
1439 {
1440 cur_covered=
1441 test(info->covered_fields.test(key_part[sel_arg->part].fieldnr-1));
1442 if (cur_covered != prev_covered)
1443 {
1444 /* create (part1val, ..., part{n-1}val) tuple. */
1445 ha_rows records;
1446 if (!tuple_arg)
1447 {
1448 tuple_arg= scan->sel_arg;
1449 /* Here we use the length of the first key part */
1450 tuple_arg->store_min(key_part->store_length, &key_ptr, 0);
1451 keypart_map= 1;
1452 }
1453 while (tuple_arg->next_key_part != sel_arg)
1454 {
1455 tuple_arg= tuple_arg->next_key_part;
1456 tuple_arg->store_min(key_part[tuple_arg->part].store_length,
1457 &key_ptr, 0);
1458 keypart_map= (keypart_map << 1) | 1;
1459 }
1460 min_range.length= max_range.length= (size_t) (key_ptr - key_val);
1461 min_range.keypart_map= max_range.keypart_map= keypart_map;
1462 records= (info->param->table->cursor->
1463 records_in_range(scan->keynr, &min_range, &max_range));
1464 if (cur_covered)
1465 {
1466 /* uncovered -> covered */
1467 selectivity_mult *= static_cast<double>(records) / prev_records;
1468 prev_records= HA_POS_ERROR;
1469 }
1470 else
1471 {
1472 /* covered -> uncovered */
1473 prev_records= records;
1474 }
1475 }
1476 prev_covered= cur_covered;
1477 }
1478 if (!prev_covered)
1479 {
1480 selectivity_mult *= static_cast<double>(info->param->table->quick_rows[scan->keynr]) / prev_records;
1481 }
1482 return selectivity_mult;
1483}
1484
1485
1486/*
1487 Check if adding a ROR scan to a ROR-intersection reduces its cost of
1488 ROR-intersection and if yes, update parameters of ROR-intersection,
1489 including its cost.
1490
1491 SYNOPSIS
1492 ror_intersect_add()
1493 param Parameter from test_quick_select
1494 info ROR-intersection structure to add the scan to.
1495 ror_scan ROR scan info to add.
1496 is_cpk_scan If true, add the scan as CPK scan (this can be inferred
1497 from other parameters and is passed separately only to
1498 avoid duplicating the inference code)
1499
1500 NOTES
1501 Adding a ROR scan to ROR-intersect "makes sense" iff the cost of ROR-
1502 intersection decreases. The cost of ROR-intersection is calculated as
1503 follows:
1504
1505 cost= SUM_i(key_scan_cost_i) + cost_of_full_rows_retrieval
1506
1507 When we add a scan the first increases and the second decreases.
1508
1509 cost_of_full_rows_retrieval=
1510 (union of indexes used covers all needed fields) ?
1511 cost_of_sweep_read(E(rows_to_retrieve), rows_in_table) :
1512 0
1513
1514 E(rows_to_retrieve) = #rows_in_table * ror_scan_selectivity(null, scan1) *
1515 ror_scan_selectivity({scan1}, scan2) * ... *
1516 ror_scan_selectivity({scan1,...}, scanN).
1517 RETURN
1518 true ROR scan added to ROR-intersection, cost updated.
1519 false It doesn't make sense to add this ROR scan to this ROR-intersection.
1520*/
1521
1522static bool ror_intersect_add(ROR_INTERSECT_INFO *info,
1523 optimizer::RorScanInfo* ror_scan, bool is_cpk_scan)
1524{
1525 double selectivity_mult= 1.0;
1526
1527 selectivity_mult = ror_scan_selectivity(info, ror_scan);
1528 if (compare_double(selectivity_mult, 1.0))
1529 {
1530 /* Don't add this scan if it doesn't improve selectivity. */
1531 return false;
1532 }
1533
1534 info->out_rows *= selectivity_mult;
1535
1536 if (is_cpk_scan)
1537 {
1538 /*
1539 CPK scan is used to filter out rows. We apply filtering for
1540 each record of every scan. Assuming 1/TIME_FOR_COMPARE_ROWID
1541 per check this gives us:
1542 */
1543 info->index_scan_costs += static_cast<double>(info->index_records) /
1545 }
1546 else
1547 {
1548 info->index_records += info->param->table->quick_rows[ror_scan->keynr];
1549 info->index_scan_costs += ror_scan->index_read_cost;
1550 boost::dynamic_bitset<> tmp_bitset= ror_scan->bitsToBitset();
1551 info->covered_fields|= tmp_bitset;
1552 if (! info->is_covering && info->param->needed_fields.is_subset_of(info->covered_fields))
1553 {
1554 info->is_covering= true;
1555 }
1556 }
1557
1558 info->total_cost= info->index_scan_costs;
1559 if (! info->is_covering)
1560 {
1561 optimizer::CostVector sweep_cost;
1562 Join *join= info->param->session->lex().select_lex.join;
1563 bool is_interrupted= test(join && join->tables == 1);
1564 get_sweep_read_cost(info->param->table, double2rows(info->out_rows),
1565 is_interrupted, &sweep_cost);
1566 info->total_cost += sweep_cost.total_cost();
1567 }
1568 return true;
1569}
1570
1571
1572/*
1573 Get best covering ROR-intersection.
1574 SYNOPSIS
1575 get_best_covering_ror_intersect()
1576 param Parameter from test_quick_select function.
1577 tree optimizer::SEL_TREE with sets of intervals for different keys.
1578 read_time Don't return table read plans with cost > read_time.
1579
1580 RETURN
1581 Best covering ROR-intersection plan
1582 NULL if no plan found.
1583
1584 NOTES
1585 get_best_ror_intersect must be called for a tree before calling this
1586 function for it.
1587 This function invalidates tree->ror_scans member values.
1588
1589 The following approximate algorithm is used:
1590 I=set of all covering indexes
1591 F=set of all fields to cover
1592 S={}
1593
1594 do
1595 {
1596 Order I by (#covered fields in F desc,
1597 #components asc,
1598 number of first not covered component asc);
1599 F=F-covered by first(I);
1600 S=S+first(I);
1601 I=I-first(I);
1602 } while F is not empty.
1603*/
1604
1605static
1606optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
1607 optimizer::SEL_TREE *tree,
1608 double read_time)
1609{
1610 optimizer::RorScanInfo **ror_scan_mark;
1611 optimizer::RorScanInfo **ror_scans_end= tree->ror_scans_end;
1612
1613 for (optimizer::RorScanInfo **scan= tree->ror_scans; scan != ror_scans_end; ++scan)
1614 (*scan)->key_components=
1615 param->table->key_info[(*scan)->keynr].key_parts;
1616
1617 /*
1618 Run covering-ROR-search algorithm.
1619 Assume set I is [ror_scan .. ror_scans_end)
1620 */
1621
1622 /*I=set of all covering indexes */
1623 ror_scan_mark= tree->ror_scans;
1624
1625 boost::dynamic_bitset<> *covered_fields= &param->tmp_covered_fields;
1626 if (covered_fields->empty())
1627 {
1628 covered_fields->resize(param->table->getShare()->sizeFields());
1629 }
1630 covered_fields->reset();
1631
1632 double total_cost= 0.0f;
1633 ha_rows records=0;
1634 bool all_covered;
1635
1636 do
1637 {
1638 /*
1639 Update changed sorting info:
1640 #covered fields,
1641 number of first not covered component
1642 Calculate and save these values for each of remaining scans.
1643 */
1644 for (optimizer::RorScanInfo **scan= ror_scan_mark; scan != ror_scans_end; ++scan)
1645 {
1646 /* subtract one bitset from the other */
1647 (*scan)->subtractBitset(*covered_fields);
1648 (*scan)->used_fields_covered=
1649 (*scan)->getBitCount();
1650 (*scan)->first_uncovered_field= (*scan)->findFirstNotSet();
1651 }
1652
1653 internal::my_qsort(ror_scan_mark, ror_scans_end-ror_scan_mark,
1654 sizeof(optimizer::RorScanInfo*),
1655 (qsort_cmp)cmp_ror_scan_info_covering);
1656
1657 /* I=I-first(I) */
1658 total_cost += (*ror_scan_mark)->index_read_cost;
1659 records += (*ror_scan_mark)->records;
1660 if (total_cost > read_time)
1661 return NULL;
1662 /* F=F-covered by first(I) */
1663 boost::dynamic_bitset<> tmp_bitset= (*ror_scan_mark)->bitsToBitset();
1664 *covered_fields|= tmp_bitset;
1665 all_covered= param->needed_fields.is_subset_of(*covered_fields);
1666 } while ((++ror_scan_mark < ror_scans_end) && ! all_covered);
1667
1668 if (!all_covered || (ror_scan_mark - tree->ror_scans) == 1)
1669 return NULL;
1670
1671 /*
1672 Ok, [tree->ror_scans .. ror_scan) holds covering index_intersection with
1673 cost total_cost.
1674 */
1675 /* Add priority queue use cost. */
1676 total_cost += static_cast<double>(records) *
1677 log((double)(ror_scan_mark - tree->ror_scans)) /
1678 (TIME_FOR_COMPARE_ROWID * M_LN2);
1679
1680 if (total_cost > read_time)
1681 return NULL;
1682
1683 optimizer::RorIntersectReadPlan* trp= new (*param->mem_root) optimizer::RorIntersectReadPlan;
1684
1685 uint32_t best_num= (ror_scan_mark - tree->ror_scans);
1686 trp->first_scan= new (*param->mem_root) optimizer::RorScanInfo*[best_num];
1687 memcpy(trp->first_scan, tree->ror_scans, best_num*sizeof(optimizer::RorScanInfo*));
1688 trp->last_scan= trp->first_scan + best_num;
1689 trp->is_covering= true;
1690 trp->read_cost= total_cost;
1691 trp->records= records;
1692 trp->cpk_scan= NULL;
1693 set_if_smaller(param->table->quick_condition_rows, records);
1694
1695 return(trp);
1696}
1697
1698
1699/*
1700 Get best ROR-intersection plan using non-covering ROR-intersection search
1701 algorithm. The returned plan may be covering.
1702
1703 SYNOPSIS
1704 get_best_ror_intersect()
1705 param Parameter from test_quick_select function.
1706 tree Transformed restriction condition to be used to look
1707 for ROR scans.
1708 read_time Do not return read plans with cost > read_time.
1709 are_all_covering [out] set to true if union of all scans covers all
1710 fields needed by the query (and it is possible to build
1711 a covering ROR-intersection)
1712
1713 NOTES
1714 get_key_scans_params must be called before this function can be called.
1715
1716 When this function is called by ROR-union construction algorithm it
1717 assumes it is building an uncovered ROR-intersection (and thus # of full
1718 records to be retrieved is wrong here). This is a hack.
1719
1720 IMPLEMENTATION
1721 The approximate best non-covering plan search algorithm is as follows:
1722
1723 find_min_ror_intersection_scan()
1724 {
1725 R= select all ROR scans;
1726 order R by (E(#records_matched) * key_record_length).
1727
1728 S= first(R); -- set of scans that will be used for ROR-intersection
1729 R= R-first(S);
1730 min_cost= cost(S);
1731 min_scan= make_scan(S);
1732 while (R is not empty)
1733 {
1734 firstR= R - first(R);
1735 if (!selectivity(S + firstR < selectivity(S)))
1736 continue;
1737
1738 S= S + first(R);
1739 if (cost(S) < min_cost)
1740 {
1741 min_cost= cost(S);
1742 min_scan= make_scan(S);
1743 }
1744 }
1745 return min_scan;
1746 }
1747
1748 See ror_intersect_add function for ROR intersection costs.
1749
1750 Special handling for Clustered PK scans
1751 Clustered PK contains all table fields, so using it as a regular scan in
1752 index intersection doesn't make sense: a range scan on CPK will be less
1753 expensive in this case.
1754 Clustered PK scan has special handling in ROR-intersection: it is not used
1755 to retrieve rows, instead its condition is used to filter row references
1756 we get from scans on other keys.
1757
1758 RETURN
1759 ROR-intersection table read plan
1760 NULL if out of memory or no suitable plan found.
1761*/
1762
1763static
1764optimizer::RorIntersectReadPlan *get_best_ror_intersect(const optimizer::Parameter *param,
1765 optimizer::SEL_TREE *tree,
1766 double read_time,
1767 bool *are_all_covering)
1768{
1769 uint32_t idx= 0;
1770 double min_cost= DBL_MAX;
1771
1772 if ((tree->n_ror_scans < 2) || ! param->table->cursor->stats.records)
1773 return NULL;
1774
1775 /*
1776 Step1: Collect ROR-able SEL_ARGs and create optimizer::RorScanInfo for each of
1777 them. Also find and save clustered PK scan if there is one.
1778 */
1779 optimizer::RorScanInfo **cur_ror_scan= NULL;
1780 optimizer::RorScanInfo *cpk_scan= NULL;
1781 uint32_t cpk_no= 0;
1782 bool cpk_scan_used= false;
1783
1784 tree->ror_scans= new (*param->mem_root) optimizer::RorScanInfo*[param->keys];
1785 cpk_no= ((param->table->cursor->primary_key_is_clustered()) ? param->table->getShare()->getPrimaryKey() : MAX_KEY);
1786
1787 for (idx= 0, cur_ror_scan= tree->ror_scans; idx < param->keys; idx++)
1788 {
1789 optimizer::RorScanInfo *scan;
1790 if (! tree->ror_scans_map.test(idx))
1791 continue;
1792 if (! (scan= make_ror_scan(param, idx, tree->keys[idx])))
1793 return NULL;
1794 if (param->real_keynr[idx] == cpk_no)
1795 {
1796 cpk_scan= scan;
1797 tree->n_ror_scans--;
1798 }
1799 else
1800 *(cur_ror_scan++)= scan;
1801 }
1802
1803 tree->ror_scans_end= cur_ror_scan;
1804 /*
1805 Ok, [ror_scans, ror_scans_end) is array of ptrs to initialized
1806 optimizer::RorScanInfo's.
1807 Step 2: Get best ROR-intersection using an approximate algorithm.
1808 */
1809 internal::my_qsort(tree->ror_scans, tree->n_ror_scans, sizeof(optimizer::RorScanInfo*),
1810 (qsort_cmp)cmp_ror_scan_info);
1811
1812 optimizer::RorScanInfo **intersect_scans= NULL; /* ROR scans used in index intersection */
1813 optimizer::RorScanInfo **intersect_scans_end= intersect_scans= new (*param->mem_root) optimizer::RorScanInfo*[tree->n_ror_scans];
1814 intersect_scans_end= intersect_scans;
1815
1816 /* Create and incrementally update ROR intersection. */
1817 ROR_INTERSECT_INFO intersect(param);
1818 ROR_INTERSECT_INFO intersect_best(param);
1819
1820 /* [intersect_scans,intersect_scans_best) will hold the best intersection */
1821 optimizer::RorScanInfo **intersect_scans_best= NULL;
1822 cur_ror_scan= tree->ror_scans;
1823 intersect_scans_best= intersect_scans;
1824 while (cur_ror_scan != tree->ror_scans_end && ! intersect.is_covering)
1825 {
1826 /* S= S + first(R); R= R - first(R); */
1827 if (! ror_intersect_add(&intersect, *cur_ror_scan, false))
1828 {
1829 cur_ror_scan++;
1830 continue;
1831 }
1832
1833 *(intersect_scans_end++)= *(cur_ror_scan++);
1834
1835 if (intersect.total_cost < min_cost)
1836 {
1837 /* Local minimum found, save it */
1838 ror_intersect_cpy(&intersect_best, &intersect);
1839 intersect_scans_best= intersect_scans_end;
1840 min_cost = intersect.total_cost;
1841 }
1842 }
1843
1844 if (intersect_scans_best == intersect_scans)
1845 {
1846 return NULL;
1847 }
1848
1849 *are_all_covering= intersect.is_covering;
1850 uint32_t best_num= intersect_scans_best - intersect_scans;
1851 ror_intersect_cpy(&intersect, &intersect_best);
1852
1853 /*
1854 Ok, found the best ROR-intersection of non-CPK key scans.
1855 Check if we should add a CPK scan. If the obtained ROR-intersection is
1856 covering, it doesn't make sense to add CPK scan.
1857 */
1858 if (cpk_scan && ! intersect.is_covering)
1859 {
1860 if (ror_intersect_add(&intersect, cpk_scan, true) &&
1861 (intersect.total_cost < min_cost))
1862 {
1863 cpk_scan_used= true;
1864 intersect_best= intersect; //just set pointer here
1865 }
1866 }
1867
1868 /* Ok, return ROR-intersect plan if we have found one */
1869 optimizer::RorIntersectReadPlan *trp= NULL;
1870 if (min_cost < read_time && (cpk_scan_used || best_num > 1))
1871 {
1872 trp= new (*param->mem_root) optimizer::RorIntersectReadPlan;
1873 trp->first_scan= new (*param->mem_root) optimizer::RorScanInfo*[best_num];
1874 memcpy(trp->first_scan, intersect_scans, best_num*sizeof(optimizer::RorScanInfo*));
1875 trp->last_scan= trp->first_scan + best_num;
1876 trp->is_covering= intersect_best.is_covering;
1877 trp->read_cost= intersect_best.total_cost;
1878 /* Prevent divisons by zero */
1879 ha_rows best_rows = double2rows(intersect_best.out_rows);
1880 if (! best_rows)
1881 best_rows= 1;
1882 set_if_smaller(param->table->quick_condition_rows, best_rows);
1883 trp->records= best_rows;
1884 trp->index_scan_costs= intersect_best.index_scan_costs;
1885 trp->cpk_scan= cpk_scan_used? cpk_scan: NULL;
1886 }
1887 return trp;
1888}
1889
1890
1891/*
1892 Get best "range" table read plan for given optimizer::SEL_TREE, also update some info
1893
1894 SYNOPSIS
1895 get_key_scans_params()
1896 session
1897 param Parameters from test_quick_select
1898 tree Make range select for this optimizer::SEL_TREE
1899 index_read_must_be_used true <=> assume 'index only' option will be set
1900 (except for clustered PK indexes)
1901 update_tbl_stats true <=> update table->quick_* with information
1902 about range scans we've evaluated.
1903 read_time Maximum cost. i.e. don't create read plans with
1904 cost > read_time.
1905
1906 DESCRIPTION
1907 Find the best "range" table read plan for given optimizer::SEL_TREE.
1908 The side effects are
1909 - tree->ror_scans is updated to indicate which scans are ROR scans.
1910 - if update_tbl_stats=true then table->quick_* is updated with info
1911 about every possible range scan.
1912
1913 RETURN
1914 Best range read plan
1915 NULL if no plan found or error occurred
1916*/
1917
1918static optimizer::RangeReadPlan *get_key_scans_params(Session *session,
1919 optimizer::Parameter *param,
1920 optimizer::SEL_TREE *tree,
1921 bool index_read_must_be_used,
1922 bool update_tbl_stats,
1923 double read_time)
1924{
1925 uint32_t idx;
1926 optimizer::SEL_ARG **key= NULL;
1927 optimizer::SEL_ARG **end= NULL;
1928 optimizer::SEL_ARG **key_to_read= NULL;
1929 ha_rows best_records= 0;
1930 uint32_t best_mrr_flags= 0;
1931 uint32_t best_buf_size= 0;
1932 optimizer::RangeReadPlan *read_plan= NULL;
1933 /*
1934 Note that there may be trees that have type optimizer::SEL_TREE::KEY but contain no
1935 key reads at all, e.g. tree for expression "key1 is not null" where key1
1936 is defined as "not null".
1937 */
1938 tree->ror_scans_map.reset();
1939 tree->n_ror_scans= 0;
1940 for (idx= 0,key=tree->keys, end=key+param->keys; key != end; key++,idx++)
1941 {
1942 if (*key)
1943 {
1944 ha_rows found_records;
1945 optimizer::CostVector cost;
1946 double found_read_time= 0.0;
1947 uint32_t mrr_flags, buf_size;
1948 uint32_t keynr= param->real_keynr[idx];
1949 if ((*key)->type == optimizer::SEL_ARG::MAYBE_KEY ||
1950 (*key)->maybe_flag)
1951 param->needed_reg->set(keynr);
1952
1953 bool read_index_only= index_read_must_be_used ||
1954 param->table->covering_keys.test(keynr);
1955
1956 found_records= check_quick_select(session, param, idx, read_index_only, *key,
1957 update_tbl_stats, &mrr_flags,
1958 &buf_size, &cost);
1959 found_read_time= cost.total_cost();
1960 if ((found_records != HA_POS_ERROR) && param->is_ror_scan)
1961 {
1962 tree->n_ror_scans++;
1963 tree->ror_scans_map.set(idx);
1964 }
1965 if (read_time > found_read_time && found_records != HA_POS_ERROR)
1966 {
1967 read_time= found_read_time;
1968 best_records= found_records;
1969 key_to_read= key;
1970 best_mrr_flags= mrr_flags;
1971 best_buf_size= buf_size;
1972 }
1973 }
1974 }
1975
1976 if (key_to_read)
1977 {
1978 idx= key_to_read - tree->keys;
1979 read_plan= new (*param->mem_root) optimizer::RangeReadPlan(*key_to_read, idx, best_mrr_flags);
1980 read_plan->records= best_records;
1981 read_plan->is_ror= tree->ror_scans_map.test(idx);
1982 read_plan->read_cost= read_time;
1983 read_plan->mrr_buf_size= best_buf_size;
1984 }
1985 return read_plan;
1986}
1987
1988
1989optimizer::QuickSelectInterface *optimizer::IndexMergeReadPlan::make_quick(optimizer::Parameter *param, bool, memory::Root *)
1990{
1991 /* index_merge always retrieves full rows, ignore retrieve_full_rows */
1992 optimizer::QuickIndexMergeSelect* quick_imerge= new optimizer::QuickIndexMergeSelect(param->session, param->table);
1993 quick_imerge->records= records;
1994 quick_imerge->read_time= read_cost;
1995 for (optimizer::RangeReadPlan **range_scan= range_scans; range_scan != range_scans_end; range_scan++)
1996 {
1997 optimizer::QuickRangeSelect* quick= (optimizer::QuickRangeSelect*)((*range_scan)->make_quick(param, false, &quick_imerge->alloc));
1998 if (not quick)
1999 {
2000 delete quick;
2001 delete quick_imerge;
2002 return NULL;
2003 }
2004 quick_imerge->push_quick_back(quick);
2005 }
2006 return quick_imerge;
2007}
2008
2009optimizer::QuickSelectInterface *optimizer::RorIntersectReadPlan::make_quick(optimizer::Parameter *param,
2010 bool retrieve_full_rows,
2011 memory::Root *parent_alloc)
2012{
2013 optimizer::QuickRorIntersectSelect *quick_intersect= NULL;
2014 optimizer::QuickRangeSelect *quick= NULL;
2015 memory::Root *alloc= NULL;
2016
2017 if ((quick_intersect=
2018 new optimizer::QuickRorIntersectSelect(param->session,
2019 param->table,
2020 (retrieve_full_rows? (! is_covering) : false),
2021 parent_alloc)))
2022 {
2023 alloc= parent_alloc ? parent_alloc : &quick_intersect->alloc;
2024 for (; first_scan != last_scan; ++first_scan)
2025 {
2026 if (! (quick= optimizer::get_quick_select(param,
2027 (*first_scan)->idx,
2028 (*first_scan)->sel_arg,
2029 HA_MRR_USE_DEFAULT_IMPL | HA_MRR_SORTED,
2030 0,
2031 alloc)))
2032 {
2033 delete quick_intersect;
2034 return NULL;
2035 }
2036 quick_intersect->push_quick_back(quick);
2037 }
2038 if (cpk_scan)
2039 {
2040 if (! (quick= optimizer::get_quick_select(param,
2041 cpk_scan->idx,
2042 cpk_scan->sel_arg,
2043 HA_MRR_USE_DEFAULT_IMPL | HA_MRR_SORTED,
2044 0,
2045 alloc)))
2046 {
2047 delete quick_intersect;
2048 return NULL;
2049 }
2050 quick->resetCursor();
2051 quick_intersect->cpk_quick= quick;
2052 }
2053 quick_intersect->records= records;
2054 quick_intersect->read_time= read_cost;
2055 }
2056 return quick_intersect;
2057}
2058
2059
2060optimizer::QuickSelectInterface *optimizer::RorUnionReadPlan::make_quick(optimizer::Parameter *param, bool, memory::Root *)
2061{
2062 /*
2063 It is impossible to construct a ROR-union that will not retrieve full
2064 rows, ignore retrieve_full_rows parameter.
2065 */
2066 optimizer::QuickRorUnionSelect* quick_roru= new optimizer::QuickRorUnionSelect(param->session, param->table);
2067 for (optimizer::TableReadPlan** scan= first_ror; scan != last_ror; scan++)
2068 {
2069 optimizer::QuickSelectInterface* quick= (*scan)->make_quick(param, false, &quick_roru->alloc);
2070 if (not quick)
2071 return NULL;
2072 quick_roru->push_quick_back(quick);
2073 }
2074 quick_roru->records= records;
2075 quick_roru->read_time= read_cost;
2076 return quick_roru;
2077}
2078
2079
2080/*
2081 Build a optimizer::SEL_TREE for <> or NOT BETWEEN predicate
2082
2083 SYNOPSIS
2084 get_ne_mm_tree()
2085 param Parameter from SqlSelect::test_quick_select
2086 cond_func item for the predicate
2087 field field in the predicate
2088 lt_value constant that field should be smaller
2089 gt_value constant that field should be greaterr
2090 cmp_type compare type for the field
2091
2092 RETURN
2093 # Pointer to tree built tree
2094 0 on error
2095*/
2096static optimizer::SEL_TREE *get_ne_mm_tree(optimizer::RangeParameter *param,
2097 Item_func *cond_func,
2098 Field *field,
2099 Item *lt_value, Item *gt_value,
2100 Item_result cmp_type)
2101{
2102 optimizer::SEL_TREE *tree= NULL;
2103 tree= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
2104 lt_value, cmp_type);
2105 if (tree)
2106 {
2107 tree= tree_or(param,
2108 tree,
2109 get_mm_parts(param, cond_func, field,
2110 Item_func::GT_FUNC,
2111 gt_value,
2112 cmp_type));
2113 }
2114 return tree;
2115}
2116
2117
2118/*
2119 Build a optimizer::SEL_TREE for a simple predicate
2120
2121 SYNOPSIS
2122 get_func_mm_tree()
2123 param Parameter from SqlSelect::test_quick_select
2124 cond_func item for the predicate
2125 field field in the predicate
2126 value constant in the predicate
2127 cmp_type compare type for the field
2128 inv true <> NOT cond_func is considered
2129 (makes sense only when cond_func is BETWEEN or IN)
2130
2131 RETURN
2132 Pointer to the tree built tree
2133*/
2134static optimizer::SEL_TREE *get_func_mm_tree(optimizer::RangeParameter *param,
2135 Item_func *cond_func,
2136 Field *field,
2137 Item *value,
2138 Item_result cmp_type,
2139 bool inv)
2140{
2141 optimizer::SEL_TREE *tree= NULL;
2142
2143 switch (cond_func->functype())
2144 {
2145
2146 case Item_func::NE_FUNC:
2147 tree= get_ne_mm_tree(param, cond_func, field, value, value, cmp_type);
2148 break;
2149
2150 case Item_func::BETWEEN:
2151 {
2152 if (! value)
2153 {
2154 if (inv)
2155 {
2156 tree= get_ne_mm_tree(param,
2157 cond_func,
2158 field,
2159 cond_func->arguments()[1],
2160 cond_func->arguments()[2],
2161 cmp_type);
2162 }
2163 else
2164 {
2165 tree= get_mm_parts(param,
2166 cond_func,
2167 field,
2168 Item_func::GE_FUNC,
2169 cond_func->arguments()[1],
2170 cmp_type);
2171 if (tree)
2172 {
2173 tree= tree_and(param,
2174 tree,
2175 get_mm_parts(param, cond_func, field,
2176 Item_func::LE_FUNC,
2177 cond_func->arguments()[2],
2178 cmp_type));
2179 }
2180 }
2181 }
2182 else
2183 tree= get_mm_parts(param,
2184 cond_func,
2185 field,
2186 (inv ?
2187 (value == (Item*)1 ? Item_func::GT_FUNC :
2188 Item_func::LT_FUNC):
2189 (value == (Item*)1 ? Item_func::LE_FUNC :
2190 Item_func::GE_FUNC)),
2191 cond_func->arguments()[0],
2192 cmp_type);
2193 break;
2194 }
2195 case Item_func::IN_FUNC:
2196 {
2197 Item_func_in *func= (Item_func_in*) cond_func;
2198
2199 /*
2200 Array for IN() is constructed when all values have the same result
2201 type. Tree won't be built for values with different result types,
2202 so we check it here to avoid unnecessary work.
2203 */
2204 if (! func->arg_types_compatible)
2205 break;
2206
2207 if (inv)
2208 {
2209 if (func->array && func->array->result_type() != ROW_RESULT)
2210 {
2211 /*
2212 We get here for conditions in form "t.key NOT IN (c1, c2, ...)",
2213 where c{i} are constants. Our goal is to produce a optimizer::SEL_TREE that
2214 represents intervals:
2215
2216 ($MIN<t.key<c1) OR (c1<t.key<c2) OR (c2<t.key<c3) OR ... (*)
2217
2218 where $MIN is either "-inf" or NULL.
2219
2220 The most straightforward way to produce it is to convert NOT IN
2221 into "(t.key != c1) AND (t.key != c2) AND ... " and let the range
2222 analyzer to build optimizer::SEL_TREE from that. The problem is that the
2223 range analyzer will use O(N^2) memory (which is probably a bug),
2224 and people do use big NOT IN lists (e.g. see BUG#15872, BUG#21282),
2225 will run out of memory.
2226
2227 Another problem with big lists like (*) is that a big list is
2228 unlikely to produce a good "range" access, while considering that
2229 range access will require expensive CPU calculations (and for
2230 MyISAM even index accesses). In short, big NOT IN lists are rarely
2231 worth analyzing.
2232
2233 Considering the above, we'll handle NOT IN as follows:
2234 * if the number of entries in the NOT IN list is less than
2235 NOT_IN_IGNORE_THRESHOLD, construct the optimizer::SEL_TREE (*) manually.
2236 * Otherwise, don't produce a optimizer::SEL_TREE.
2237 */
2238 const unsigned int NOT_IN_IGNORE_THRESHOLD= 1000;
2239 memory::Root *tmp_root= param->mem_root;
2240 param->session->mem_root= param->old_root;
2241 /*
2242 Create one Item_type constant object. We'll need it as
2243 get_mm_parts only accepts constant values wrapped in Item_Type
2244 objects.
2245 We create the Item on param->mem_root which points to
2246 per-statement mem_root (while session->mem_root is currently pointing
2247 to mem_root local to range optimizer).
2248 */
2249 Item *value_item= func->array->create_item();
2250 param->session->mem_root= tmp_root;
2251
2252 if (func->array->count > NOT_IN_IGNORE_THRESHOLD || ! value_item)
2253 break;
2254
2255 /* Get a optimizer::SEL_TREE for "(-inf|NULL) < X < c_0" interval. */
2256 uint32_t i=0;
2257 do
2258 {
2259 func->array->value_to_item(i, value_item);
2260 tree= get_mm_parts(param,
2261 cond_func,
2262 field, Item_func::LT_FUNC,
2263 value_item,
2264 cmp_type);
2265 if (! tree)
2266 break;
2267 i++;
2268 } while (i < func->array->count && tree->type == optimizer::SEL_TREE::IMPOSSIBLE);
2269
2270 if (!tree || tree->type == optimizer::SEL_TREE::IMPOSSIBLE)
2271 {
2272 /* We get here in cases like "t.unsigned NOT IN (-1,-2,-3) */
2273 tree= NULL;
2274 break;
2275 }
2276 optimizer::SEL_TREE *tree2= NULL;
2277 for (; i < func->array->count; i++)
2278 {
2279 if (func->array->compare_elems(i, i-1))
2280 {
2281 /* Get a optimizer::SEL_TREE for "-inf < X < c_i" interval */
2282 func->array->value_to_item(i, value_item);
2283 tree2= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
2284 value_item, cmp_type);
2285 if (!tree2)
2286 {
2287 tree= NULL;
2288 break;
2289 }
2290
2291 /* Change all intervals to be "c_{i-1} < X < c_i" */
2292 for (uint32_t idx= 0; idx < param->keys; idx++)
2293 {
2294 optimizer::SEL_ARG *new_interval, *last_val;
2295 if (((new_interval= tree2->keys[idx])) &&
2296 (tree->keys[idx]) &&
2297 ((last_val= tree->keys[idx]->last())))
2298 {
2299 new_interval->min_value= last_val->max_value;
2300 new_interval->min_flag= NEAR_MIN;
2301 }
2302 }
2303 /*
2304 The following doesn't try to allocate memory so no need to
2305 check for NULL.
2306 */
2307 tree= tree_or(param, tree, tree2);
2308 }
2309 }
2310
2311 if (tree && tree->type != optimizer::SEL_TREE::IMPOSSIBLE)
2312 {
2313 /*
2314 Get the optimizer::SEL_TREE for the last "c_last < X < +inf" interval
2315 (value_item cotains c_last already)
2316 */
2317 tree2= get_mm_parts(param, cond_func, field, Item_func::GT_FUNC,
2318 value_item, cmp_type);
2319 tree= tree_or(param, tree, tree2);
2320 }
2321 }
2322 else
2323 {
2324 tree= get_ne_mm_tree(param, cond_func, field,
2325 func->arguments()[1], func->arguments()[1],
2326 cmp_type);
2327 if (tree)
2328 {
2329 Item **arg, **end;
2330 for (arg= func->arguments()+2, end= arg+func->argument_count()-2;
2331 arg < end ; arg++)
2332 {
2333 tree= tree_and(param, tree, get_ne_mm_tree(param, cond_func, field,
2334 *arg, *arg, cmp_type));
2335 }
2336 }
2337 }
2338 }
2339 else
2340 {
2341 tree= get_mm_parts(param, cond_func, field, Item_func::EQ_FUNC,
2342 func->arguments()[1], cmp_type);
2343 if (tree)
2344 {
2345 Item **arg, **end;
2346 for (arg= func->arguments()+2, end= arg+func->argument_count()-2;
2347 arg < end ; arg++)
2348 {
2349 tree= tree_or(param, tree, get_mm_parts(param, cond_func, field,
2350 Item_func::EQ_FUNC,
2351 *arg, cmp_type));
2352 }
2353 }
2354 }
2355 break;
2356 }
2357 default:
2358 {
2359 /*
2360 Here the function for the following predicates are processed:
2361 <, <=, =, >=, >, LIKE, IS NULL, IS NOT NULL.
2362 If the predicate is of the form (value op field) it is handled
2363 as the equivalent predicate (field rev_op value), e.g.
2364 2 <= a is handled as a >= 2.
2365 */
2366 Item_func::Functype func_type=
2367 (value != cond_func->arguments()[0]) ? cond_func->functype() :
2368 ((Item_bool_func2*) cond_func)->rev_functype();
2369 tree= get_mm_parts(param, cond_func, field, func_type, value, cmp_type);
2370 }
2371 }
2372
2373 return(tree);
2374}
2375
2376
2377/*
2378 Build conjunction of all optimizer::SEL_TREEs for a simple predicate applying equalities
2379
2380 SYNOPSIS
2381 get_full_func_mm_tree()
2382 param Parameter from SqlSelect::test_quick_select
2383 cond_func item for the predicate
2384 field_item field in the predicate
2385 value constant in the predicate
2386 (for BETWEEN it contains the number of the field argument,
2387 for IN it's always 0)
2388 inv true <> NOT cond_func is considered
2389 (makes sense only when cond_func is BETWEEN or IN)
2390
2391 DESCRIPTION
2392 For a simple SARGable predicate of the form (f op c), where f is a field and
2393 c is a constant, the function builds a conjunction of all optimizer::SEL_TREES that can
2394 be obtained by the substitution of f for all different fields equal to f.
2395
2396 NOTES
2397 If the WHERE condition contains a predicate (fi op c),
2398 then not only SELL_TREE for this predicate is built, but
2399 the trees for the results of substitution of fi for
2400 each fj belonging to the same multiple equality as fi
2401 are built as well.
2402 E.g. for WHERE t1.a=t2.a AND t2.a > 10
2403 a optimizer::SEL_TREE for t2.a > 10 will be built for quick select from t2
2404 and
2405 a optimizer::SEL_TREE for t1.a > 10 will be built for quick select from t1.
2406
2407 A BETWEEN predicate of the form (fi [NOT] BETWEEN c1 AND c2) is treated
2408 in a similar way: we build a conjuction of trees for the results
2409 of all substitutions of fi for equal fj.
2410 Yet a predicate of the form (c BETWEEN f1i AND f2i) is processed
2411 differently. It is considered as a conjuction of two SARGable
2412 predicates (f1i <= c) and (f2i <=c) and the function get_full_func_mm_tree
2413 is called for each of them separately producing trees for
2414 AND j (f1j <=c ) and AND j (f2j <= c)
2415 After this these two trees are united in one conjunctive tree.
2416 It's easy to see that the same tree is obtained for
2417 AND j,k (f1j <=c AND f2k<=c)
2418 which is equivalent to
2419 AND j,k (c BETWEEN f1j AND f2k).
2420 The validity of the processing of the predicate (c NOT BETWEEN f1i AND f2i)
2421 which equivalent to (f1i > c OR f2i < c) is not so obvious. Here the
2422 function get_full_func_mm_tree is called for (f1i > c) and (f2i < c)
2423 producing trees for AND j (f1j > c) and AND j (f2j < c). Then this two
2424 trees are united in one OR-tree. The expression
2425 (AND j (f1j > c) OR AND j (f2j < c)
2426 is equivalent to the expression
2427 AND j,k (f1j > c OR f2k < c)
2428 which is just a translation of
2429 AND j,k (c NOT BETWEEN f1j AND f2k)
2430
2431 In the cases when one of the items f1, f2 is a constant c1 we do not create
2432 a tree for it at all. It works for BETWEEN predicates but does not
2433 work for NOT BETWEEN predicates as we have to evaluate the expression
2434 with it. If it is true then the other tree can be completely ignored.
2435 We do not do it now and no trees are built in these cases for
2436 NOT BETWEEN predicates.
2437
2438 As to IN predicates only ones of the form (f IN (c1,...,cn)),
2439 where f1 is a field and c1,...,cn are constant, are considered as
2440 SARGable. We never try to narrow the index scan using predicates of
2441 the form (c IN (c1,...,f,...,cn)).
2442
2443 RETURN
2444 Pointer to the tree representing the built conjunction of optimizer::SEL_TREEs
2445*/
2446
2447static optimizer::SEL_TREE *get_full_func_mm_tree(optimizer::RangeParameter *param,
2448 Item_func *cond_func,
2449 Item_field *field_item, Item *value,
2450 bool inv)
2451{
2452 optimizer::SEL_TREE *tree= 0;
2453 optimizer::SEL_TREE *ftree= 0;
2454 table_map ref_tables= 0;
2455 table_map param_comp= ~(param->prev_tables | param->read_tables |
2456 param->current_table);
2457
2458 for (uint32_t i= 0; i < cond_func->arg_count; i++)
2459 {
2460 Item *arg= cond_func->arguments()[i]->real_item();
2461 if (arg != field_item)
2462 ref_tables|= arg->used_tables();
2463 }
2464
2465 Field *field= field_item->field;
2466 field->setWriteSet();
2467
2468 Item_result cmp_type= field->cmp_type();
2469 if (!((ref_tables | field->getTable()->map) & param_comp))
2470 ftree= get_func_mm_tree(param, cond_func, field, value, cmp_type, inv);
2471 Item_equal *item_equal= field_item->item_equal;
2472 if (item_equal)
2473 {
2474 Item_equal_iterator it(item_equal->begin());
2475 Item_field *item;
2476 while ((item= it++))
2477 {
2478 Field *f= item->field;
2479 f->setWriteSet();
2480
2481 if (field->eq(f))
2482 continue;
2483 if (!((ref_tables | f->getTable()->map) & param_comp))
2484 {
2485 tree= get_func_mm_tree(param, cond_func, f, value, cmp_type, inv);
2486 ftree= !ftree ? tree : tree_and(param, ftree, tree);
2487 }
2488 }
2489 }
2490 return(ftree);
2491}
2492
2493 /* make a select tree of all keys in condition */
2494
2495static optimizer::SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond)
2496{
2497 optimizer::SEL_TREE *tree=0;
2498 optimizer::SEL_TREE *ftree= 0;
2499 Item_field *field_item= 0;
2500 bool inv= false;
2501 Item *value= 0;
2502
2503 if (cond->type() == Item::COND_ITEM)
2504 {
2505 List<Item>::iterator li(((Item_cond*) cond)->argument_list()->begin());
2506
2507 if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
2508 {
2509 tree=0;
2510 while (Item* item=li++)
2511 {
2512 optimizer::SEL_TREE *new_tree= get_mm_tree(param,item);
2513 if (param->session->is_fatal_error ||
2514 param->alloced_sel_args > optimizer::SEL_ARG::MAX_SEL_ARGS)
2515 return 0; // out of memory
2516 tree=tree_and(param,tree,new_tree);
2517 if (tree && tree->type == optimizer::SEL_TREE::IMPOSSIBLE)
2518 break;
2519 }
2520 }
2521 else
2522 { // COND OR
2523 tree= get_mm_tree(param,li++);
2524 if (tree)
2525 {
2526 while (Item* item= li++)
2527 {
2528 optimizer::SEL_TREE *new_tree= get_mm_tree(param,item);
2529 if (!new_tree)
2530 return 0; // out of memory
2531 tree=tree_or(param,tree,new_tree);
2532 if (!tree || tree->type == optimizer::SEL_TREE::ALWAYS)
2533 break;
2534 }
2535 }
2536 }
2537 return(tree);
2538 }
2539 /* Here when simple cond
2540 There are limits on what kinds of const items we can evaluate, grep for
2541 DontEvaluateMaterializedSubqueryTooEarly.
2542 */
2543 if (cond->const_item() && !cond->is_expensive())
2544 {
2545 /*
2546 During the cond->val_int() evaluation we can come across a subselect
2547 item which may allocate memory on the session->mem_root and assumes
2548 all the memory allocated has the same life span as the subselect
2549 item itself. So we have to restore the thread's mem_root here.
2550 */
2551 memory::Root *tmp_root= param->mem_root;
2552 param->session->mem_root= param->old_root;
2553 tree= cond->val_int() ? new(tmp_root) optimizer::SEL_TREE(optimizer::SEL_TREE::ALWAYS) :
2554 new(tmp_root) optimizer::SEL_TREE(optimizer::SEL_TREE::IMPOSSIBLE);
2555 param->session->mem_root= tmp_root;
2556 return(tree);
2557 }
2558
2559 table_map ref_tables= 0;
2560 table_map param_comp= ~(param->prev_tables | param->read_tables |
2561 param->current_table);
2562 if (cond->type() != Item::FUNC_ITEM)
2563 { // Should be a field
2564 ref_tables= cond->used_tables();
2565 if ((ref_tables & param->current_table) ||
2566 (ref_tables & ~(param->prev_tables | param->read_tables)))
2567 return 0;
2568 return(new optimizer::SEL_TREE(optimizer::SEL_TREE::MAYBE));
2569 }
2570
2571 Item_func *cond_func= (Item_func*) cond;
2572 if (cond_func->functype() == Item_func::BETWEEN ||
2573 cond_func->functype() == Item_func::IN_FUNC)
2574 inv= ((Item_func_opt_neg *) cond_func)->negated;
2575 else if (cond_func->select_optimize() == Item_func::OPTIMIZE_NONE)
2576 return 0;
2577
2578 param->cond= cond;
2579
2580 switch (cond_func->functype()) {
2581 case Item_func::BETWEEN:
2582 if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM)
2583 {
2584 field_item= (Item_field*) (cond_func->arguments()[0]->real_item());
2585 ftree= get_full_func_mm_tree(param, cond_func, field_item, NULL, inv);
2586 }
2587
2588 /*
2589 Concerning the code below see the NOTES section in
2590 the comments for the function get_full_func_mm_tree()
2591 */
2592 for (uint32_t i= 1 ; i < cond_func->arg_count ; i++)
2593 {
2594 if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM)
2595 {
2596 field_item= (Item_field*) (cond_func->arguments()[i]->real_item());
2597 optimizer::SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func,
2598 field_item, (Item*)(intptr_t)i, inv);
2599 if (inv)
2600 tree= !tree ? tmp : tree_or(param, tree, tmp);
2601 else
2602 tree= tree_and(param, tree, tmp);
2603 }
2604 else if (inv)
2605 {
2606 tree= 0;
2607 break;
2608 }
2609 }
2610
2611 ftree = tree_and(param, ftree, tree);
2612 break;
2613 case Item_func::IN_FUNC:
2614 {
2615 Item_func_in *func=(Item_func_in*) cond_func;
2616 if (func->key_item()->real_item()->type() != Item::FIELD_ITEM)
2617 return 0;
2618 field_item= (Item_field*) (func->key_item()->real_item());
2619 ftree= get_full_func_mm_tree(param, cond_func, field_item, NULL, inv);
2620 break;
2621 }
2622 case Item_func::MULT_EQUAL_FUNC:
2623 {
2624 Item_equal *item_equal= (Item_equal *) cond;
2625 if (!(value= item_equal->get_const()))
2626 return 0;
2627 Item_equal_iterator it(item_equal->begin());
2628 ref_tables= value->used_tables();
2629 while ((field_item= it++))
2630 {
2631 Field *field= field_item->field;
2632 field->setWriteSet();
2633
2634 Item_result cmp_type= field->cmp_type();
2635 if (!((ref_tables | field->getTable()->map) & param_comp))
2636 {
2637 tree= get_mm_parts(param, cond, field, Item_func::EQ_FUNC,
2638 value,cmp_type);
2639 ftree= !ftree ? tree : tree_and(param, ftree, tree);
2640 }
2641 }
2642
2643 return(ftree);
2644 }
2645 default:
2646 if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM)
2647 {
2648 field_item= (Item_field*) (cond_func->arguments()[0]->real_item());
2649 value= cond_func->arg_count > 1 ? cond_func->arguments()[1] : 0;
2650 }
2651 else if (cond_func->have_rev_func() &&
2652 cond_func->arguments()[1]->real_item()->type() ==
2653 Item::FIELD_ITEM)
2654 {
2655 field_item= (Item_field*) (cond_func->arguments()[1]->real_item());
2656 value= cond_func->arguments()[0];
2657 }
2658 else
2659 return 0;
2660 ftree= get_full_func_mm_tree(param, cond_func, field_item, value, inv);
2661 }
2662
2663 return(ftree);
2664}
2665
2666
2667static optimizer::SEL_TREE *
2668get_mm_parts(optimizer::RangeParameter *param,
2669 COND *cond_func,
2670 Field *field,
2671 Item_func::Functype type,
2672 Item *value, Item_result)
2673{
2674 if (field->getTable() != param->table)
2675 return 0;
2676
2677 KEY_PART *key_part = param->key_parts;
2678 KEY_PART *end = param->key_parts_end;
2679 optimizer::SEL_TREE *tree=0;
2680 if (value &&
2681 value->used_tables() & ~(param->prev_tables | param->read_tables))
2682 return 0;
2683 for (; key_part != end; key_part++)
2684 {
2685 if (field->eq(key_part->field))
2686 {
2687 optimizer::SEL_ARG *sel_arg=0;
2688 if (!tree)
2689 tree= new optimizer::SEL_TREE;
2690 if (!value || !(value->used_tables() & ~param->read_tables))
2691 {
2692 sel_arg= get_mm_leaf(param,cond_func, key_part->field,key_part,type,value);
2693 if (! sel_arg)
2694 continue;
2695 if (sel_arg->type == optimizer::SEL_ARG::IMPOSSIBLE)
2696 {
2697 tree->type=optimizer::SEL_TREE::IMPOSSIBLE;
2698 return(tree);
2699 }
2700 }
2701 else
2702 {
2703 // This key may be used later
2704 sel_arg= new optimizer::SEL_ARG(optimizer::SEL_ARG::MAYBE_KEY);
2705 }
2706 sel_arg->part=(unsigned char) key_part->part;
2707 tree->keys[key_part->key]=sel_add(tree->keys[key_part->key],sel_arg);
2708 tree->keys_map.set(key_part->key);
2709 }
2710 }
2711
2712 return tree;
2713}
2714
2715
2716static optimizer::SEL_ARG *
2717get_mm_leaf(optimizer::RangeParameter *param,
2718 COND *conf_func,
2719 Field *field,
2720 KEY_PART *key_part,
2721 Item_func::Functype type,
2722 Item *value)
2723{
2724 uint32_t maybe_null=(uint32_t) field->real_maybe_null();
2725 bool optimize_range;
2726 optimizer::SEL_ARG *tree= NULL;
2727 memory::Root *alloc= param->mem_root;
2728 unsigned char *str;
2729 int err= 0;
2730
2731 /*
2732 We need to restore the runtime mem_root of the thread in this
2733 function because it evaluates the value of its argument, while
2734 the argument can be any, e.g. a subselect. The subselect
2735 items, in turn, assume that all the memory allocated during
2736 the evaluation has the same life span as the item itself.
2737 TODO: opitimizer/range.cc should not reset session->mem_root at all.
2738 */
2739 param->session->mem_root= param->old_root;
2740 if (!value) // IS NULL or IS NOT NULL
2741 {
2742 if (field->getTable()->maybe_null) // Can't use a key on this
2743 goto end;
2744 if (!maybe_null) // Not null field
2745 {
2746 if (type == Item_func::ISNULL_FUNC)
2747 tree= &optimizer::null_element;
2748 goto end;
2749 }
2750 tree= new (*alloc) optimizer::SEL_ARG(field,is_null_string,is_null_string);
2751 if (type == Item_func::ISNOTNULL_FUNC)
2752 {
2753 tree->min_flag=NEAR_MIN; /* IS NOT NULL -> X > NULL */
2754 tree->max_flag=NO_MAX_RANGE;
2755 }
2756 goto end;
2757 }
2758
2759 /*
2760 1. Usually we can't use an index if the column collation
2761 differ from the operation collation.
2762
2763 2. However, we can reuse a case insensitive index for
2764 the binary searches:
2765
2766 WHERE latin1_swedish_ci_column = 'a' COLLATE lati1_bin;
2767
2768 WHERE latin1_swedish_ci_colimn = BINARY 'a '
2769
2770 */
2771 if (field->result_type() == STRING_RESULT &&
2772 value->result_type() == STRING_RESULT &&
2773 ((Field_str*)field)->charset() != conf_func->compare_collation() &&
2774 !(conf_func->compare_collation()->state & MY_CS_BINSORT))
2775 goto end;
2776
2777 if (param->using_real_indexes)
2778 optimize_range= field->optimize_range(param->real_keynr[key_part->key], key_part->part);
2779 else
2780 optimize_range= true;
2781
2782 if (type == Item_func::LIKE_FUNC)
2783 {
2784 bool like_error;
2785 char buff1[MAX_FIELD_WIDTH];
2786 unsigned char *min_str,*max_str;
2787 String tmp(buff1,sizeof(buff1),value->collation.collation),*res;
2788 size_t length, offset, min_length, max_length;
2789 uint32_t field_length= field->pack_length()+maybe_null;
2790
2791 if (!optimize_range)
2792 goto end;
2793 if (!(res= value->val_str(&tmp)))
2794 {
2795 tree= &optimizer::null_element;
2796 goto end;
2797 }
2798
2799 /*
2800 TODO:
2801 Check if this was a function. This should have be optimized away
2802 in the sql_select.cc
2803 */
2804 if (res != &tmp)
2805 {
2806 tmp.copy(*res); // Get own copy
2807 res= &tmp;
2808 }
2809 if (field->cmp_type() != STRING_RESULT)
2810 goto end; // Can only optimize strings
2811
2812 offset=maybe_null;
2813 length=key_part->store_length;
2814
2815 if (length != key_part->length + maybe_null)
2816 {
2817 /* key packed with length prefix */
2818 offset+= HA_KEY_BLOB_LENGTH;
2819 field_length= length - HA_KEY_BLOB_LENGTH;
2820 }
2821 else
2822 {
2823 if (DRIZZLE_UNLIKELY(length < field_length))
2824 {
2825 /*
2826 This can only happen in a table created with UNIREG where one key
2827 overlaps many fields
2828 */
2829 length= field_length;
2830 }
2831 else
2832 field_length= length;
2833 }
2834 length+=offset;
2835 min_str= alloc->alloc(length*2);
2836 max_str=min_str+length;
2837 if (maybe_null)
2838 max_str[0]= min_str[0]=0;
2839
2840 field_length-= maybe_null;
2841 int escape_code= make_escape_code(field->charset(), ((Item_func_like*)(param->cond))->escape);
2842 like_error= my_like_range(field->charset(),
2843 res->ptr(), res->length(),
2844 escape_code,
2845 internal::wild_one, internal::wild_many,
2846 field_length,
2847 (char*) min_str+offset, (char*) max_str+offset,
2848 &min_length, &max_length);
2849 if (like_error) // Can't optimize with LIKE
2850 goto end;
2851
2852 if (offset != maybe_null) // BLOB or VARCHAR
2853 {
2854 int2store(min_str+maybe_null,min_length);
2855 int2store(max_str+maybe_null,max_length);
2856 }
2857 tree= new (alloc) optimizer::SEL_ARG(field, min_str, max_str);
2858 goto end;
2859 }
2860
2861 if (! optimize_range &&
2862 type != Item_func::EQ_FUNC &&
2863 type != Item_func::EQUAL_FUNC)
2864 goto end; // Can't optimize this
2865
2866 /*
2867 We can't always use indexes when comparing a string index to a number
2868 cmp_type() is checked to allow compare of dates to numbers
2869 */
2870 if (field->result_type() == STRING_RESULT &&
2871 value->result_type() != STRING_RESULT &&
2872 field->cmp_type() != value->result_type())
2873 goto end;
2874
2875 /*
2876 * Some notes from Jay...
2877 *
2878 * OK, so previously, and in MySQL, what the optimizer does here is
2879 * override the sql_mode variable to ignore out-of-range or bad date-
2880 * time values. It does this because the optimizer is populating the
2881 * field variable with the incoming value from the comparison field,
2882 * and the value may exceed the bounds of a proper column type.
2883 *
2884 * For instance, assume the following:
2885 *
2886 * CREATE TABLE t1 (ts TIMESTAMP);
2887 * INSERT INTO t1 ('2009-03-04 00:00:00');
2888 * CREATE TABLE t2 (dt1 DATETIME, dt2 DATETIME);
2889 * INSERT INT t2 ('2003-12-31 00:00:00','2999-12-31 00:00:00');
2890 *
2891 * If we issue this query:
2892 *
2893 * SELECT * FROM t1, t2 WHERE t1.ts BETWEEN t2.dt1 AND t2.dt2;
2894 *
2895 * We will come into bounds issues. Field_timestamp::store() will be
2896 * called with a datetime value of "2999-12-31 00:00:00" and will throw
2897 * an error for out-of-bounds. MySQL solves this via a hack with sql_mode
2898 * but Drizzle always throws errors on bad data storage in a Field class.
2899 *
2900 * Therefore, to get around the problem of the Field class being used for
2901 * "storage" here without actually storing anything...we must check to see
2902 * if the value being stored in a Field_timestamp here is out of range. If
2903 * it is, then we must convert to the highest Timestamp value (or lowest,
2904 * depending on whether the datetime is before or after the epoch.
2905 */
2906 if (field->is_timestamp())
2907 {
2908 /*
2909 * The left-side of the range comparison is a timestamp field. Therefore,
2910 * we must check to see if the value in the right-hand side is outside the
2911 * range of the UNIX epoch, and cut to the epoch bounds if it is.
2912 */
2913 /* Datetime and date columns are Item::FIELD_ITEM ... and have a result type of STRING_RESULT */
2914 if (value->real_item()->type() == Item::FIELD_ITEM
2915 && value->result_type() == STRING_RESULT)
2916 {
2917 char buff[DateTime::MAX_STRING_LENGTH];
2918 String tmp(buff, sizeof(buff), &my_charset_bin);
2919 String *res= value->val_str(&tmp);
2920
2921 if (!res)
2922 goto end;
2923 else
2924 {
2925 /*
2926 * Create a datetime from the string and compare to fixed timestamp
2927 * instances representing the epoch boundaries.
2928 */
2929 DateTime value_datetime;
2930
2931 if (! value_datetime.from_string(res->c_ptr(), (size_t) res->length()))
2932 goto end;
2933
2934 Timestamp max_timestamp;
2935 Timestamp min_timestamp;
2936
2937 (void) max_timestamp.from_time_t((time_t) INT32_MAX);
2938 (void) min_timestamp.from_time_t((time_t) 0);
2939
2940 /* We rely on Temporal class operator overloads to do our comparisons. */
2941 if (value_datetime < min_timestamp)
2942 {
2943 /*
2944 * Datetime in right-hand side column is before UNIX epoch, so adjust to
2945 * lower bound.
2946 */
2947 char new_value_buff[DateTime::MAX_STRING_LENGTH];
2948 int new_value_length;
2949 String new_value_string(new_value_buff, sizeof(new_value_buff), &my_charset_bin);
2950
2951 new_value_length= min_timestamp.to_string(new_value_string.c_ptr(),
2952 DateTime::MAX_STRING_LENGTH);
2953 assert((new_value_length+1) < DateTime::MAX_STRING_LENGTH);
2954 new_value_string.length(new_value_length);
2955 err= value->save_str_value_in_field(field, &new_value_string);
2956 }
2957 else if (value_datetime > max_timestamp)
2958 {
2959 /*
2960 * Datetime in right hand side column is after UNIX epoch, so adjust
2961 * to the higher bound of the epoch.
2962 */
2963 char new_value_buff[DateTime::MAX_STRING_LENGTH];
2964 int new_value_length;
2965 String new_value_string(new_value_buff, sizeof(new_value_buff), &my_charset_bin);
2966
2967 new_value_length= max_timestamp.to_string(new_value_string.c_ptr(),
2968 DateTime::MAX_STRING_LENGTH);
2969 assert((new_value_length+1) < DateTime::MAX_STRING_LENGTH);
2970 new_value_string.length(new_value_length);
2971 err= value->save_str_value_in_field(field, &new_value_string);
2972 }
2973 else
2974 err= value->save_in_field(field, 1);
2975 }
2976 }
2977 else /* Not a datetime -> timestamp comparison */
2978 err= value->save_in_field(field, 1);
2979 }
2980 else /* Not a timestamp comparison */
2981 err= value->save_in_field(field, 1);
2982
2983 if (err > 0)
2984 {
2985 if (field->cmp_type() != value->result_type())
2986 {
2987 if ((type == Item_func::EQ_FUNC || type == Item_func::EQUAL_FUNC) &&
2988 value->result_type() == item_cmp_type(field->result_type(),
2989 value->result_type()))
2990 {
2991 tree= new (alloc) optimizer::SEL_ARG(field, 0, 0);
2992 tree->type= optimizer::SEL_ARG::IMPOSSIBLE;
2993 goto end;
2994 }
2995 else
2996 {
2997 /*
2998 TODO: We should return trees of the type SEL_ARG::IMPOSSIBLE
2999 for the cases like int_field > 999999999999999999999999 as well.
3000 */
3001 tree= 0;
3002 if (err == 3 && field->type() == DRIZZLE_TYPE_DATE &&
3003 (type == Item_func::GT_FUNC || type == Item_func::GE_FUNC ||
3004 type == Item_func::LT_FUNC || type == Item_func::LE_FUNC) )
3005 {
3006 /*
3007 We were saving DATETIME into a DATE column, the conversion went ok
3008 but a non-zero time part was cut off.
3009
3010 In MySQL's SQL dialect, DATE and DATETIME are compared as datetime
3011 values. Index over a DATE column uses DATE comparison. Changing
3012 from one comparison to the other is possible:
3013
3014 datetime(date_col)< '2007-12-10 12:34:55' -> date_col<='2007-12-10'
3015 datetime(date_col)<='2007-12-10 12:34:55' -> date_col<='2007-12-10'
3016
3017 datetime(date_col)> '2007-12-10 12:34:55' -> date_col>='2007-12-10'
3018 datetime(date_col)>='2007-12-10 12:34:55' -> date_col>='2007-12-10'
3019
3020 but we'll need to convert '>' to '>=' and '<' to '<='. This will
3021 be done together with other types at the end of this function
3022 (grep for field_is_equal_to_item)
3023 */
3024 }
3025 else
3026 goto end;
3027 }
3028 }
3029
3030 /*
3031 guaranteed at this point: err > 0; field and const of same type
3032 If an integer got bounded (e.g. to within 0..255 / -128..127)
3033 for < or >, set flags as for <= or >= (no NEAR_MAX / NEAR_MIN)
3034 */
3035 else if (err == 1 && field->result_type() == INT_RESULT)
3036 {
3037 if (type == Item_func::LT_FUNC && (value->val_int() > 0))
3038 type = Item_func::LE_FUNC;
3039 else if (type == Item_func::GT_FUNC &&
3040 !((Field_num*)field)->unsigned_flag &&
3041 !((Item_int*)value)->unsigned_flag &&
3042 (value->val_int() < 0))
3043 type = Item_func::GE_FUNC;
3044 }
3045 else if (err == 1)
3046 {
3047 tree= new (alloc) optimizer::SEL_ARG(field, 0, 0);
3048 tree->type= optimizer::SEL_ARG::IMPOSSIBLE;
3049 goto end;
3050 }
3051 }
3052 else if (err < 0)
3053 {
3054 /* This happens when we try to insert a NULL field in a not null column */
3055 tree= &optimizer::null_element; // cmp with NULL is never true
3056 goto end;
3057 }
3058
3059 /*
3060 Any predicate except "<=>"(null-safe equality operator) involving NULL as a
3061 constant is always FALSE
3062 Put IMPOSSIBLE Tree(null_element) here.
3063 */
3064 if (type != Item_func::EQUAL_FUNC && field->is_real_null())
3065 {
3066 tree= &optimizer::null_element;
3067 goto end;
3068 }
3069
3070 str= alloc->alloc(key_part->store_length+1);
3071 if (maybe_null)
3072 *str= field->is_real_null(); // Set to 1 if null
3073 field->get_key_image(str+maybe_null, key_part->length);
3074 tree= new (alloc) optimizer::SEL_ARG(field, str, str);
3075
3076 /*
3077 Check if we are comparing an UNSIGNED integer with a negative constant.
3078 In this case we know that:
3079 (a) (unsigned_int [< | <=] negative_constant) == false
3080 (b) (unsigned_int [> | >=] negative_constant) == true
3081 In case (a) the condition is false for all values, and in case (b) it
3082 is true for all values, so we can avoid unnecessary retrieval and condition
3083 testing, and we also get correct comparison of unsinged integers with
3084 negative integers (which otherwise fails because at query execution time
3085 negative integers are cast to unsigned if compared with unsigned).
3086 */
3087 if (field->result_type() == INT_RESULT &&
3088 value->result_type() == INT_RESULT &&
3089 ((Field_num*)field)->unsigned_flag && !((Item_int*)value)->unsigned_flag)
3090 {
3091 int64_t item_val= value->val_int();
3092 if (item_val < 0)
3093 {
3094 if (type == Item_func::LT_FUNC || type == Item_func::LE_FUNC)
3095 {
3096 tree->type= optimizer::SEL_ARG::IMPOSSIBLE;
3097 goto end;
3098 }
3099 if (type == Item_func::GT_FUNC || type == Item_func::GE_FUNC)
3100 {
3101 tree= 0;
3102 goto end;
3103 }
3104 }
3105 }
3106
3107 switch (type) {
3108 case Item_func::LT_FUNC:
3109 if (field_is_equal_to_item(field,value))
3110 tree->max_flag=NEAR_MAX;
3111 /* fall through */
3112 case Item_func::LE_FUNC:
3113 if (!maybe_null)
3114 tree->min_flag=NO_MIN_RANGE; /* From start */
3115 else
3116 { // > NULL
3117 tree->min_value=is_null_string;
3118 tree->min_flag=NEAR_MIN;
3119 }
3120 break;
3121 case Item_func::GT_FUNC:
3122 /* Don't use open ranges for partial key_segments */
3123 if (field_is_equal_to_item(field,value) &&
3124 !(key_part->flag & HA_PART_KEY_SEG))
3125 tree->min_flag=NEAR_MIN;
3126 /* fall through */
3127 case Item_func::GE_FUNC:
3128 tree->max_flag=NO_MAX_RANGE;
3129 break;
3130 default:
3131 break;
3132 }
3133
3134end:
3135 param->session->mem_root= alloc;
3136 return(tree);
3137}
3138
3139
3140/******************************************************************************
3141** Tree manipulation functions
3142** If tree is 0 it means that the condition can't be tested. It refers
3143** to a non existent table or to a field in current table with isn't a key.
3144** The different tree flags:
3145** IMPOSSIBLE: Condition is never true
3146** ALWAYS: Condition is always true
3147** MAYBE: Condition may exists when tables are read
3148** MAYBE_KEY: Condition refers to a key that may be used in join loop
3149** KEY_RANGE: Condition uses a key
3150******************************************************************************/
3151
3152/*
3153 Add a new key test to a key when scanning through all keys
3154 This will never be called for same key parts.
3155*/
3156
3157static optimizer::SEL_ARG *
3158sel_add(optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2)
3159{
3160 optimizer::SEL_ARG *root= NULL;
3161 optimizer::SEL_ARG **key_link= NULL;
3162
3163 if (!key1)
3164 return key2;
3165 if (!key2)
3166 return key1;
3167
3168 key_link= &root;
3169 while (key1 && key2)
3170 {
3171 if (key1->part < key2->part)
3172 {
3173 *key_link= key1;
3174 key_link= &key1->next_key_part;
3175 key1=key1->next_key_part;
3176 }
3177 else
3178 {
3179 *key_link= key2;
3180 key_link= &key2->next_key_part;
3181 key2=key2->next_key_part;
3182 }
3183 }
3184 *key_link=key1 ? key1 : key2;
3185 return root;
3186}
3187
3188static const int CLONE_KEY1_MAYBE= 1;
3189static const int CLONE_KEY2_MAYBE= 2;
3190
3191static uint32_t swap_clone_flag(uint32_t a)
3192{
3193 return ((a & 1) << 1) | ((a & 2) >> 1);
3194}
3195
3196static optimizer::SEL_TREE *
3197tree_and(optimizer::RangeParameter *param, optimizer::SEL_TREE *tree1, optimizer::SEL_TREE *tree2)
3198{
3199 if (!tree1)
3200 return(tree2);
3201 if (!tree2)
3202 return(tree1);
3203 if (tree1->type == optimizer::SEL_TREE::IMPOSSIBLE || tree2->type == optimizer::SEL_TREE::ALWAYS)
3204 return(tree1);
3205 if (tree2->type == optimizer::SEL_TREE::IMPOSSIBLE || tree1->type == optimizer::SEL_TREE::ALWAYS)
3206 return(tree2);
3207 if (tree1->type == optimizer::SEL_TREE::MAYBE)
3208 {
3209 if (tree2->type == optimizer::SEL_TREE::KEY)
3210 tree2->type=optimizer::SEL_TREE::KEY_SMALLER;
3211 return(tree2);
3212 }
3213 if (tree2->type == optimizer::SEL_TREE::MAYBE)
3214 {
3215 tree1->type=optimizer::SEL_TREE::KEY_SMALLER;
3216 return(tree1);
3217 }
3218 key_map result_keys;
3219 result_keys.reset();
3220
3221 /* Join the trees key per key */
3222 optimizer::SEL_ARG **key1,**key2,**end;
3223 for (key1= tree1->keys,key2= tree2->keys,end=key1+param->keys ;
3224 key1 != end ; key1++,key2++)
3225 {
3226 uint32_t flag=0;
3227 if (*key1 || *key2)
3228 {
3229 if (*key1 && !(*key1)->simple_key())
3230 flag|=CLONE_KEY1_MAYBE;
3231 if (*key2 && !(*key2)->simple_key())
3232 flag|=CLONE_KEY2_MAYBE;
3233 *key1=key_and(param, *key1, *key2, flag);
3234 if (*key1 && (*key1)->type == optimizer::SEL_ARG::IMPOSSIBLE)
3235 {
3236 tree1->type= optimizer::SEL_TREE::IMPOSSIBLE;
3237 return(tree1);
3238 }
3239 result_keys.set(key1 - tree1->keys);
3240 }
3241 }
3242 tree1->keys_map= result_keys;
3243 /* dispose index_merge if there is a "range" option */
3244 if (result_keys.any())
3245 {
3246 tree1->merges.clear();
3247 return(tree1);
3248 }
3249
3250 /* ok, both trees are index_merge trees */
3251 imerge_list_and_list(&tree1->merges, &tree2->merges);
3252 return(tree1);
3253}
3254
3255
3256
3257/* And key trees where key1->part < key2 -> part */
3258
3259static optimizer::SEL_ARG *
3260and_all_keys(optimizer::RangeParameter *param,
3261 optimizer::SEL_ARG *key1,
3262 optimizer::SEL_ARG *key2,
3263 uint32_t clone_flag)
3264{
3265 optimizer::SEL_ARG *next= NULL;
3266 ulong use_count=key1->use_count;
3267
3268 if (key1->size() != 1)
3269 {
3270 key2->use_count+=key1->size()-1; //psergey: why we don't count that key1 has n-k-p?
3271 key2->increment_use_count((int) key1->size()-1);
3272 }
3273 if (key1->type == optimizer::SEL_ARG::MAYBE_KEY)
3274 {
3275 key1->right= key1->left= &optimizer::null_element;
3276 key1->next= key1->prev= 0;
3277 }
3278 for (next= key1->first(); next ; next=next->next)
3279 {
3280 if (next->next_key_part)
3281 {
3282 optimizer::SEL_ARG *tmp= key_and(param, next->next_key_part, key2, clone_flag);
3283 if (tmp && tmp->type == optimizer::SEL_ARG::IMPOSSIBLE)
3284 {
3285 key1=key1->tree_delete(next);
3286 continue;
3287 }
3288 next->next_key_part=tmp;
3289 if (use_count)
3290 next->increment_use_count(use_count);
3291 if (param->alloced_sel_args > optimizer::SEL_ARG::MAX_SEL_ARGS)
3292 break;
3293 }
3294 else
3295 next->next_key_part=key2;
3296 }
3297 if (! key1)
3298 return &optimizer::null_element; // Impossible ranges
3299 key1->use_count++;
3300 return key1;
3301}
3302
3303
3304/*
3305 Produce a SEL_ARG graph that represents "key1 AND key2"
3306
3307 SYNOPSIS
3308 key_and()
3309 param Range analysis context (needed to track if we have allocated
3310 too many SEL_ARGs)
3311 key1 First argument, root of its RB-tree
3312 key2 Second argument, root of its RB-tree
3313
3314 RETURN
3315 RB-tree root of the resulting SEL_ARG graph.
3316 NULL if the result of AND operation is an empty interval {0}.
3317*/
3318
3319static optimizer::SEL_ARG *
3320key_and(optimizer::RangeParameter *param,
3321 optimizer::SEL_ARG *key1,
3322 optimizer::SEL_ARG *key2,
3323 uint32_t clone_flag)
3324{
3325 if (! key1)
3326 return key2;
3327 if (! key2)
3328 return key1;
3329 if (key1->part != key2->part)
3330 {
3331 if (key1->part > key2->part)
3332 {
3333 std::swap(key1, key2);
3334 clone_flag=swap_clone_flag(clone_flag);
3335 }
3336 // key1->part < key2->part
3337 key1->use_count--;
3338 if (key1->use_count > 0)
3339 if (! (key1= key1->clone_tree(param)))
3340 return 0; // OOM
3341 return and_all_keys(param, key1, key2, clone_flag);
3342 }
3343
3344 if (((clone_flag & CLONE_KEY2_MAYBE) &&
3345 ! (clone_flag & CLONE_KEY1_MAYBE) &&
3346 key2->type != optimizer::SEL_ARG::MAYBE_KEY) ||
3347 key1->type == optimizer::SEL_ARG::MAYBE_KEY)
3348 { // Put simple key in key2
3349 std::swap(key1, key2);
3350 clone_flag= swap_clone_flag(clone_flag);
3351 }
3352
3353 /* If one of the key is MAYBE_KEY then the found region may be smaller */
3354 if (key2->type == optimizer::SEL_ARG::MAYBE_KEY)
3355 {
3356 if (key1->use_count > 1)
3357 {
3358 key1->use_count--;
3359 if (! (key1=key1->clone_tree(param)))
3360 return 0; // OOM
3361 key1->use_count++;
3362 }
3363 if (key1->type == optimizer::SEL_ARG::MAYBE_KEY)
3364 { // Both are maybe key
3365 key1->next_key_part= key_and(param,
3366 key1->next_key_part,
3367 key2->next_key_part,
3368 clone_flag);
3369 if (key1->next_key_part &&
3370 key1->next_key_part->type == optimizer::SEL_ARG::IMPOSSIBLE)
3371 return key1;
3372 }
3373 else
3374 {
3375 key1->maybe_smaller();
3376 if (key2->next_key_part)
3377 {
3378 key1->use_count--; // Incremented in and_all_keys
3379 return and_all_keys(param, key1, key2, clone_flag);
3380 }
3381 key2->use_count--; // Key2 doesn't have a tree
3382 }
3383 return key1;
3384 }
3385
3386 key1->use_count--;
3387 key2->use_count--;
3388 optimizer::SEL_ARG *e1= key1->first();
3389 optimizer::SEL_ARG *e2= key2->first();
3390 optimizer::SEL_ARG *new_tree= NULL;
3391
3392 while (e1 && e2)
3393 {
3394 int cmp= e1->cmp_min_to_min(e2);
3395 if (cmp < 0)
3396 {
3397 if (get_range(&e1, &e2, key1))
3398 continue;
3399 }
3400 else if (get_range(&e2, &e1, key2))
3401 continue;
3402 optimizer::SEL_ARG *next= key_and(param,
3403 e1->next_key_part,
3404 e2->next_key_part,
3405 clone_flag);
3406 e1->increment_use_count(1);
3407 e2->increment_use_count(1);
3408 if (! next || next->type != optimizer::SEL_ARG::IMPOSSIBLE)
3409 {
3410 optimizer::SEL_ARG *new_arg= e1->clone_and(e2);
3411 new_arg->next_key_part=next;
3412 if (! new_tree)
3413 {
3414 new_tree=new_arg;
3415 }
3416 else
3417 new_tree=new_tree->insert(new_arg);
3418 }
3419 if (e1->cmp_max_to_max(e2) < 0)
3420 e1=e1->next; // e1 can't overlapp next e2
3421 else
3422 e2=e2->next;
3423 }
3424 key1->free_tree();
3425 key2->free_tree();
3426 if (! new_tree)
3427 return &optimizer::null_element; // Impossible range
3428 return new_tree;
3429}
3430
3431
3432static bool
3433get_range(optimizer::SEL_ARG **e1, optimizer::SEL_ARG **e2, optimizer::SEL_ARG *root1)
3434{
3435 (*e1)= root1->find_range(*e2); // first e1->min < e2->min
3436 if ((*e1)->cmp_max_to_min(*e2) < 0)
3437 {
3438 if (! ((*e1)=(*e1)->next))
3439 return 1;
3440 if ((*e1)->cmp_min_to_max(*e2) > 0)
3441 {
3442 (*e2)=(*e2)->next;
3443 return 1;
3444 }
3445 }
3446 return 0;
3447}
3448
3449
3450/****************************************************************************
3451 MRR Range Sequence Interface implementation that walks a SEL_ARG* tree.
3452 ****************************************************************************/
3453
3454/* MRR range sequence, SEL_ARG* implementation: stack entry */
3456{
3457 /*
3458 Pointers in min and max keys. They point to right-after-end of key
3459 images. The 0-th entry has these pointing to key tuple start.
3460 */
3461 unsigned char *min_key, *max_key;
3462
3463 /*
3464 Flags, for {keypart0, keypart1, ... this_keypart} subtuple.
3465 min_key_flag may have NULL_RANGE set.
3466 */
3467 uint32_t min_key_flag, max_key_flag;
3468
3469 /* Number of key parts */
3470 uint32_t min_key_parts, max_key_parts;
3471 optimizer::SEL_ARG *key_tree;
3472} RANGE_SEQ_ENTRY;
3473
3474
3475/*
3476 MRR range sequence, SEL_ARG* implementation: SEL_ARG graph traversal context
3477*/
3479{
3480 uint32_t keyno; /* index of used tree in optimizer::SEL_TREE structure */
3481 uint32_t real_keyno; /* Number of the index in tables */
3482 optimizer::Parameter *param;
3483 optimizer::SEL_ARG *start; /* Root node of the traversed SEL_ARG* graph */
3484
3485 RANGE_SEQ_ENTRY stack[MAX_REF_PARTS];
3486 int i; /* Index of last used element in the above array */
3487
3488 bool at_start; /* true <=> The traversal has just started */
3489} SEL_ARG_RANGE_SEQ;
3490
3491
3492/*
3493 Range sequence interface, SEL_ARG* implementation: Initialize the traversal
3494
3495 SYNOPSIS
3496 init()
3497 init_params SEL_ARG tree traversal context
3498 n_ranges [ignored] The number of ranges obtained
3499 flags [ignored] HA_MRR_SINGLE_POINT, HA_MRR_FIXED_KEY
3500
3501 RETURN
3502 Value of init_param
3503*/
3504
3505static range_seq_t sel_arg_range_seq_init(void *init_param, uint32_t, uint32_t)
3506{
3507 SEL_ARG_RANGE_SEQ *seq= (SEL_ARG_RANGE_SEQ*)init_param;
3508 seq->at_start= true;
3509 seq->stack[0].key_tree= NULL;
3510 seq->stack[0].min_key= seq->param->min_key;
3511 seq->stack[0].min_key_flag= 0;
3512 seq->stack[0].min_key_parts= 0;
3513
3514 seq->stack[0].max_key= seq->param->max_key;
3515 seq->stack[0].max_key_flag= 0;
3516 seq->stack[0].max_key_parts= 0;
3517 seq->i= 0;
3518 return init_param;
3519}
3520
3521
3522static void step_down_to(SEL_ARG_RANGE_SEQ *arg, optimizer::SEL_ARG *key_tree)
3523{
3524 RANGE_SEQ_ENTRY *cur= &arg->stack[arg->i+1];
3525 RANGE_SEQ_ENTRY *prev= &arg->stack[arg->i];
3526
3527 cur->key_tree= key_tree;
3528 cur->min_key= prev->min_key;
3529 cur->max_key= prev->max_key;
3530 cur->min_key_parts= prev->min_key_parts;
3531 cur->max_key_parts= prev->max_key_parts;
3532
3533 uint16_t stor_length= arg->param->key[arg->keyno][key_tree->part].store_length;
3534 cur->min_key_parts += key_tree->store_min(stor_length, &cur->min_key,
3535 prev->min_key_flag);
3536 cur->max_key_parts += key_tree->store_max(stor_length, &cur->max_key,
3537 prev->max_key_flag);
3538
3539 cur->min_key_flag= prev->min_key_flag | key_tree->min_flag;
3540 cur->max_key_flag= prev->max_key_flag | key_tree->max_flag;
3541
3542 if (key_tree->is_null_interval())
3543 cur->min_key_flag |= NULL_RANGE;
3544 (arg->i)++;
3545}
3546
3547
3548/*
3549 Range sequence interface, SEL_ARG* implementation: get the next interval
3550
3551 SYNOPSIS
3552 sel_arg_range_seq_next()
3553 rseq Value returned from sel_arg_range_seq_init
3554 range OUT Store information about the range here
3555
3556 DESCRIPTION
3557 This is "get_next" function for Range sequence interface implementation
3558 for SEL_ARG* tree.
3559
3560 IMPLEMENTATION
3561 The traversal also updates those param members:
3562 - is_ror_scan
3563 - range_count
3564 - max_key_part
3565
3566 RETURN
3567 0 Ok
3568 1 No more ranges in the sequence
3569*/
3570
3571//psergey-merge-todo: support check_quick_keys:max_keypart
3572static uint32_t sel_arg_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
3573{
3574 optimizer::SEL_ARG *key_tree;
3575 SEL_ARG_RANGE_SEQ *seq= (SEL_ARG_RANGE_SEQ*)rseq;
3576 if (seq->at_start)
3577 {
3578 key_tree= seq->start;
3579 seq->at_start= false;
3580 goto walk_up_n_right;
3581 }
3582
3583 key_tree= seq->stack[seq->i].key_tree;
3584 /* Ok, we're at some "full tuple" position in the tree */
3585
3586 /* Step down if we can */
3587 if (key_tree->next && key_tree->next != &optimizer::null_element)
3588 {
3589 //step down; (update the tuple, we'll step right and stay there)
3590 seq->i--;
3591 step_down_to(seq, key_tree->next);
3592 key_tree= key_tree->next;
3593 seq->param->is_ror_scan= false;
3594 goto walk_right_n_up;
3595 }
3596
3597 /* Ok, can't step down, walk left until we can step down */
3598 while (1)
3599 {
3600 if (seq->i == 1) // can't step left
3601 return 1;
3602 /* Step left */
3603 seq->i--;
3604 key_tree= seq->stack[seq->i].key_tree;
3605
3606 /* Step down if we can */
3607 if (key_tree->next && key_tree->next != &optimizer::null_element)
3608 {
3609 // Step down; update the tuple
3610 seq->i--;
3611 step_down_to(seq, key_tree->next);
3612 key_tree= key_tree->next;
3613 break;
3614 }
3615 }
3616
3617 /*
3618 Ok, we've stepped down from the path to previous tuple.
3619 Walk right-up while we can
3620 */
3621walk_right_n_up:
3622 while (key_tree->next_key_part && key_tree->next_key_part != &optimizer::null_element &&
3623 key_tree->next_key_part->part == key_tree->part + 1 &&
3624 key_tree->next_key_part->type == optimizer::SEL_ARG::KEY_RANGE)
3625 {
3626 {
3627 RANGE_SEQ_ENTRY *cur= &seq->stack[seq->i];
3628 uint32_t min_key_length= cur->min_key - seq->param->min_key;
3629 uint32_t max_key_length= cur->max_key - seq->param->max_key;
3630 uint32_t len= cur->min_key - cur[-1].min_key;
3631 if (! (min_key_length == max_key_length &&
3632 ! memcmp(cur[-1].min_key, cur[-1].max_key, len) &&
3633 ! key_tree->min_flag && !key_tree->max_flag))
3634 {
3635 seq->param->is_ror_scan= false;
3636 if (! key_tree->min_flag)
3637 cur->min_key_parts +=
3638 key_tree->next_key_part->store_min_key(seq->param->key[seq->keyno],
3639 &cur->min_key,
3640 &cur->min_key_flag);
3641 if (! key_tree->max_flag)
3642 cur->max_key_parts +=
3643 key_tree->next_key_part->store_max_key(seq->param->key[seq->keyno],
3644 &cur->max_key,
3645 &cur->max_key_flag);
3646 break;
3647 }
3648 }
3649
3650 /*
3651 Ok, current atomic interval is in form "t.field=const" and there is
3652 next_key_part interval. Step right, and walk up from there.
3653 */
3654 key_tree= key_tree->next_key_part;
3655
3656walk_up_n_right:
3657 while (key_tree->prev && key_tree->prev != &optimizer::null_element)
3658 {
3659 /* Step up */
3660 key_tree= key_tree->prev;
3661 }
3662 step_down_to(seq, key_tree);
3663 }
3664
3665 /* Ok got a tuple */
3666 RANGE_SEQ_ENTRY *cur= &seq->stack[seq->i];
3667
3668 range->ptr= (char*)(size_t)(key_tree->part);
3669 {
3670 range->range_flag= cur->min_key_flag | cur->max_key_flag;
3671
3672 range->start_key.key= seq->param->min_key;
3673 range->start_key.length= cur->min_key - seq->param->min_key;
3674 range->start_key.keypart_map= make_prev_keypart_map(cur->min_key_parts);
3675 range->start_key.flag= (cur->min_key_flag & NEAR_MIN ? HA_READ_AFTER_KEY :
3676 HA_READ_KEY_EXACT);
3677
3678 range->end_key.key= seq->param->max_key;
3679 range->end_key.length= cur->max_key - seq->param->max_key;
3680 range->end_key.flag= (cur->max_key_flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
3681 HA_READ_AFTER_KEY);
3682 range->end_key.keypart_map= make_prev_keypart_map(cur->max_key_parts);
3683
3684 if (!(cur->min_key_flag & ~NULL_RANGE) && !cur->max_key_flag &&
3685 (uint32_t)key_tree->part+1 == seq->param->table->key_info[seq->real_keyno].key_parts &&
3686 (seq->param->table->key_info[seq->real_keyno].flags & (HA_NOSAME)) ==
3687 HA_NOSAME &&
3688 range->start_key.length == range->end_key.length &&
3689 !memcmp(seq->param->min_key,seq->param->max_key,range->start_key.length))
3690 range->range_flag= UNIQUE_RANGE | (cur->min_key_flag & NULL_RANGE);
3691
3692 if (seq->param->is_ror_scan)
3693 {
3694 /*
3695 If we get here, the condition on the key was converted to form
3696 "(keyXpart1 = c1) AND ... AND (keyXpart{key_tree->part - 1} = cN) AND
3697 somecond(keyXpart{key_tree->part})"
3698 Check if
3699 somecond is "keyXpart{key_tree->part} = const" and
3700 uncovered "tail" of KeyX parts is either empty or is identical to
3701 first members of clustered primary key.
3702 */
3703 if (!(!(cur->min_key_flag & ~NULL_RANGE) && !cur->max_key_flag &&
3704 (range->start_key.length == range->end_key.length) &&
3705 !memcmp(range->start_key.key, range->end_key.key, range->start_key.length) &&
3706 is_key_scan_ror(seq->param, seq->real_keyno, key_tree->part + 1)))
3707 seq->param->is_ror_scan= false;
3708 }
3709 }
3710 seq->param->range_count++;
3711 seq->param->max_key_part= max(seq->param->max_key_part,(uint32_t)key_tree->part);
3712 return 0;
3713}
3714
3715
3716/*
3717 Calculate cost and E(#rows) for a given index and intervals tree
3718
3719 SYNOPSIS
3720 check_quick_select()
3721 param Parameter from test_quick_select
3722 idx Number of index to use in Parameter::key optimizer::SEL_TREE::key
3723 index_only true - assume only index tuples will be accessed
3724 false - assume full table rows will be read
3725 tree Transformed selection condition, tree->key[idx] holds
3726 the intervals for the given index.
3727 update_tbl_stats true <=> update table->quick_* with information
3728 about range scan we've evaluated.
3729 mrr_flags INOUT MRR access flags
3730 cost OUT Scan cost
3731
3732 NOTES
3733 param->is_ror_scan is set to reflect if the key scan is a ROR (see
3734 is_key_scan_ror function for more info)
3735 param->table->quick_*, param->range_count (and maybe others) are
3736 updated with data of given key scan, see quick_range_seq_next for details.
3737
3738 RETURN
3739 Estimate # of records to be retrieved.
3740 HA_POS_ERROR if estimate calculation failed due to table Cursor problems.
3741*/
3742
3743static
3744ha_rows check_quick_select(Session *session,
3745 optimizer::Parameter *param,
3746 uint32_t idx,
3747 bool index_only,
3748 optimizer::SEL_ARG *tree,
3749 bool update_tbl_stats,
3750 uint32_t *mrr_flags,
3751 uint32_t *bufsize,
3752 optimizer::CostVector *cost)
3753{
3754 SEL_ARG_RANGE_SEQ seq;
3755 RANGE_SEQ_IF seq_if = {sel_arg_range_seq_init, sel_arg_range_seq_next};
3756 Cursor *cursor= param->table->cursor;
3757 ha_rows rows;
3758 uint32_t keynr= param->real_keynr[idx];
3759
3760 /* Handle cases when we don't have a valid non-empty list of range */
3761 if (! tree)
3762 return(HA_POS_ERROR);
3763 if (tree->type == optimizer::SEL_ARG::IMPOSSIBLE)
3764 return(0L);
3765 if (tree->type != optimizer::SEL_ARG::KEY_RANGE || tree->part != 0)
3766 return(HA_POS_ERROR);
3767
3768 seq.keyno= idx;
3769 seq.real_keyno= keynr;
3770 seq.param= param;
3771 seq.start= tree;
3772
3773 param->range_count=0;
3774 param->max_key_part=0;
3775
3776 param->is_ror_scan= true;
3777 if (param->table->index_flags(keynr) & HA_KEY_SCAN_NOT_ROR)
3778 param->is_ror_scan= false;
3779
3780 *mrr_flags= param->force_default_mrr? HA_MRR_USE_DEFAULT_IMPL: 0;
3781 *mrr_flags|= HA_MRR_NO_ASSOCIATION;
3782
3783 bool pk_is_clustered= cursor->primary_key_is_clustered();
3784 if (index_only &&
3785 (param->table->index_flags(keynr) & HA_KEYREAD_ONLY) &&
3786 !(pk_is_clustered && keynr == param->table->getShare()->getPrimaryKey()))
3787 *mrr_flags |= HA_MRR_INDEX_ONLY;
3788
3789 if (session->lex().sql_command != SQLCOM_SELECT)
3790 *mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
3791
3792 *bufsize= param->session->variables.read_rnd_buff_size;
3793 rows= cursor->multi_range_read_info_const(keynr, &seq_if, (void*)&seq, 0,
3794 bufsize, mrr_flags, cost);
3795 if (rows != HA_POS_ERROR)
3796 {
3797 param->table->quick_rows[keynr]=rows;
3798 if (update_tbl_stats)
3799 {
3800 param->table->quick_keys.set(keynr);
3801 param->table->quick_key_parts[keynr]=param->max_key_part+1;
3802 param->table->quick_n_ranges[keynr]= param->range_count;
3803 param->table->quick_condition_rows=
3804 min(param->table->quick_condition_rows, rows);
3805 }
3806 }
3807 /* Figure out if the key scan is ROR (returns rows in ROWID order) or not */
3808 message::Table::Index::IndexType key_alg= param->table->key_info[seq.real_keyno].algorithm;
3809 if ((key_alg != message::Table::Index::BTREE)
3810 && (key_alg!= message::Table::Index::UNKNOWN_INDEX))
3811 {
3812 /*
3813 All scans are non-ROR scans for those index types.
3814 TODO: Don't have this logic here, make table engines return
3815 appropriate flags instead.
3816 */
3817 param->is_ror_scan= false;
3818 }
3819 else
3820 {
3821 /* Clustered PK scan is always a ROR scan (TODO: same as above) */
3822 if (param->table->getShare()->getPrimaryKey() == keynr && pk_is_clustered)
3823 param->is_ror_scan= true;
3824 }
3825
3826 return(rows); //psergey-merge:todo: maintain first_null_comp.
3827}
3828
3829
3830/*
3831 Check if key scan on given index with equality conditions on first n key
3832 parts is a ROR scan.
3833
3834 SYNOPSIS
3835 is_key_scan_ror()
3836 param Parameter from test_quick_select
3837 keynr Number of key in the table. The key must not be a clustered
3838 primary key.
3839 nparts Number of first key parts for which equality conditions
3840 are present.
3841
3842 NOTES
3843 ROR (Rowid Ordered Retrieval) key scan is a key scan that produces
3844 ordered sequence of rowids (ha_xxx::cmp_ref is the comparison function)
3845
3846 This function is needed to handle a practically-important special case:
3847 an index scan is a ROR scan if it is done using a condition in form
3848
3849 "key1_1=c_1 AND ... AND key1_n=c_n"
3850
3851 where the index is defined on (key1_1, ..., key1_N [,a_1, ..., a_n])
3852
3853 and the table has a clustered Primary Key defined as
3854 PRIMARY KEY(a_1, ..., a_n, b1, ..., b_k)
3855
3856 i.e. the first key parts of it are identical to uncovered parts ot the
3857 key being scanned. This function assumes that the index flags do not
3858 include HA_KEY_SCAN_NOT_ROR flag (that is checked elsewhere).
3859
3860 Check (1) is made in quick_range_seq_next()
3861
3862 RETURN
3863 true The scan is ROR-scan
3864 false Otherwise
3865*/
3866
3867static bool is_key_scan_ror(optimizer::Parameter *param, uint32_t keynr, uint8_t nparts)
3868{
3869 KeyInfo *table_key= param->table->key_info + keynr;
3870 KeyPartInfo *key_part= table_key->key_part + nparts;
3871 KeyPartInfo *key_part_end= (table_key->key_part +
3872 table_key->key_parts);
3873 uint32_t pk_number;
3874
3875 for (KeyPartInfo *kp= table_key->key_part; kp < key_part; kp++)
3876 {
3877 uint16_t fieldnr= param->table->key_info[keynr].
3878 key_part[kp - table_key->key_part].fieldnr - 1;
3879 if (param->table->getField(fieldnr)->key_length() != kp->length)
3880 return false;
3881 }
3882
3883 if (key_part == key_part_end)
3884 return true;
3885
3886 key_part= table_key->key_part + nparts;
3887 pk_number= param->table->getShare()->getPrimaryKey();
3888 if (!param->table->cursor->primary_key_is_clustered() || pk_number == MAX_KEY)
3889 return false;
3890
3891 KeyPartInfo *pk_part= param->table->key_info[pk_number].key_part;
3892 KeyPartInfo *pk_part_end= pk_part +
3893 param->table->key_info[pk_number].key_parts;
3894 for (;(key_part!=key_part_end) && (pk_part != pk_part_end);
3895 ++key_part, ++pk_part)
3896 {
3897 if ((key_part->field != pk_part->field) ||
3898 (key_part->length != pk_part->length))
3899 return false;
3900 }
3901 return (key_part == key_part_end);
3902}
3903
3904
3905optimizer::QuickRangeSelect *
3906optimizer::get_quick_select(Parameter *param,
3907 uint32_t idx,
3908 optimizer::SEL_ARG *key_tree,
3909 uint32_t mrr_flags,
3910 uint32_t mrr_buf_size,
3911 memory::Root *parent_alloc)
3912{
3913 optimizer::QuickRangeSelect *quick= new optimizer::QuickRangeSelect(param->session,
3914 param->table,
3915 param->real_keynr[idx],
3916 test(parent_alloc),
3917 NULL);
3918
3919 if (quick)
3920 {
3921 if (get_quick_keys(param,
3922 quick,
3923 param->key[idx],
3924 key_tree,
3925 param->min_key,
3926 0,
3927 param->max_key,
3928 0))
3929 {
3930 delete quick;
3931 quick= NULL;
3932 }
3933 else
3934 {
3935 quick->mrr_flags= mrr_flags;
3936 quick->mrr_buf_size= mrr_buf_size;
3937 quick->key_parts= parent_alloc
3938 ? (KEY_PART*)parent_alloc->memdup(param->key[idx], sizeof(KEY_PART)* param->table->key_info[param->real_keynr[idx]].key_parts)
3939 : (KEY_PART*)quick->alloc.memdup(param->key[idx], sizeof(KEY_PART)* param->table->key_info[param->real_keynr[idx]].key_parts);
3940 }
3941 }
3942 return quick;
3943}
3944
3945
3946/*
3947** Fix this to get all possible sub_ranges
3948*/
3949bool
3950optimizer::get_quick_keys(optimizer::Parameter *param,
3951 optimizer::QuickRangeSelect *quick,
3952 KEY_PART *key,
3953 optimizer::SEL_ARG *key_tree,
3954 unsigned char *min_key,
3955 uint32_t min_key_flag,
3956 unsigned char *max_key,
3957 uint32_t max_key_flag)
3958{
3959 optimizer::QuickRange *range= NULL;
3960 uint32_t flag;
3961 int min_part= key_tree->part - 1; // # of keypart values in min_key buffer
3962 int max_part= key_tree->part - 1; // # of keypart values in max_key buffer
3963
3964 if (key_tree->left != &optimizer::null_element)
3965 {
3966 if (get_quick_keys(param,
3967 quick,
3968 key,
3969 key_tree->left,
3970 min_key,
3971 min_key_flag,
3972 max_key,
3973 max_key_flag))
3974 {
3975 return 1;
3976 }
3977 }
3978 unsigned char *tmp_min_key= min_key,*tmp_max_key= max_key;
3979 min_part+= key_tree->store_min(key[key_tree->part].store_length,
3980 &tmp_min_key,min_key_flag);
3981 max_part+= key_tree->store_max(key[key_tree->part].store_length,
3982 &tmp_max_key,max_key_flag);
3983
3984 if (key_tree->next_key_part &&
3985 key_tree->next_key_part->part == key_tree->part+1 &&
3986 key_tree->next_key_part->type == optimizer::SEL_ARG::KEY_RANGE)
3987 { // const key as prefix
3988 if ((tmp_min_key - min_key) == (tmp_max_key - max_key) &&
3989 memcmp(min_key, max_key, (uint32_t)(tmp_max_key - max_key))==0 &&
3990 key_tree->min_flag==0 && key_tree->max_flag==0)
3991 {
3992 if (get_quick_keys(param,
3993 quick,
3994 key,
3995 key_tree->next_key_part,
3996 tmp_min_key,
3997 min_key_flag | key_tree->min_flag,
3998 tmp_max_key,
3999 max_key_flag | key_tree->max_flag))
4000 {
4001 return 1;
4002 }
4003 goto end; // Ugly, but efficient
4004 }
4005 {
4006 uint32_t tmp_min_flag=key_tree->min_flag,tmp_max_flag=key_tree->max_flag;
4007 if (! tmp_min_flag)
4008 {
4009 min_part+= key_tree->next_key_part->store_min_key(key,
4010 &tmp_min_key,
4011 &tmp_min_flag);
4012 }
4013 if (! tmp_max_flag)
4014 {
4015 max_part+= key_tree->next_key_part->store_max_key(key,
4016 &tmp_max_key,
4017 &tmp_max_flag);
4018 }
4019 flag=tmp_min_flag | tmp_max_flag;
4020 }
4021 }
4022 else
4023 {
4024 flag= key_tree->min_flag | key_tree->max_flag;
4025 }
4026
4027 /*
4028 Ensure that some part of min_key and max_key are used. If not,
4029 regard this as no lower/upper range
4030 */
4031 if (tmp_min_key != param->min_key)
4032 {
4033 flag&= ~NO_MIN_RANGE;
4034 }
4035 else
4036 {
4037 flag|= NO_MIN_RANGE;
4038 }
4039 if (tmp_max_key != param->max_key)
4040 {
4041 flag&= ~NO_MAX_RANGE;
4042 }
4043 else
4044 {
4045 flag|= NO_MAX_RANGE;
4046 }
4047 if (flag == 0)
4048 {
4049 uint32_t length= (uint32_t) (tmp_min_key - param->min_key);
4050 if (length == (uint32_t) (tmp_max_key - param->max_key) &&
4051 ! memcmp(param->min_key,param->max_key,length))
4052 {
4053 KeyInfo *table_key= quick->head->key_info+quick->index;
4054 flag= EQ_RANGE;
4055 if ((table_key->flags & (HA_NOSAME)) == HA_NOSAME &&
4056 key->part == table_key->key_parts-1)
4057 {
4058 if (! (table_key->flags & HA_NULL_PART_KEY) ||
4059 ! null_part_in_key(key,
4060 param->min_key,
4061 (uint32_t) (tmp_min_key - param->min_key)))
4062 {
4063 flag|= UNIQUE_RANGE;
4064 }
4065 else
4066 {
4067 flag|= NULL_RANGE;
4068 }
4069 }
4070 }
4071 }
4072
4073 /* Get range for retrieving rows in QUICK_SELECT::get_next */
4074 range= new optimizer::QuickRange(param->min_key,
4075 (uint32_t) (tmp_min_key - param->min_key),
4076 min_part >=0 ? make_keypart_map(min_part) : 0,
4077 param->max_key,
4078 (uint32_t) (tmp_max_key - param->max_key),
4079 max_part >=0 ? make_keypart_map(max_part) : 0,
4080 flag);
4081
4082 set_if_bigger(quick->max_used_key_length, (uint32_t)range->min_length);
4083 set_if_bigger(quick->max_used_key_length, (uint32_t)range->max_length);
4084 set_if_bigger(quick->used_key_parts, (uint32_t) key_tree->part+1);
4085 quick->ranges.push_back(&range);
4086
4087 end:
4088 if (key_tree->right != &optimizer::null_element)
4089 {
4090 return get_quick_keys(param,
4091 quick,
4092 key,
4093 key_tree->right,
4094 min_key,
4095 min_key_flag,
4096 max_key,
4097 max_key_flag);
4098 }
4099 return 0;
4100}
4101
4102/*
4103 Return true if any part of the key is NULL
4104
4105 SYNOPSIS
4106 null_part_in_key()
4107 key_part Array of key parts (index description)
4108 key Key values tuple
4109 length Length of key values tuple in bytes.
4110
4111 RETURN
4112 true The tuple has at least one "keypartX is NULL"
4113 false Otherwise
4114*/
4115
4116static bool null_part_in_key(KEY_PART *key_part, const unsigned char *key, uint32_t length)
4117{
4118 for (const unsigned char *end=key+length ;
4119 key < end;
4120 key+= key_part++->store_length)
4121 {
4122 if (key_part->null_bit && *key)
4123 return 1;
4124 }
4125 return 0;
4126}
4127
4128
4129bool optimizer::QuickSelectInterface::is_keys_used(const boost::dynamic_bitset<>& fields)
4130{
4131 return is_key_used(head, index, fields);
4132}
4133
4134
4135/*
4136 Create quick select from ref/ref_or_null scan.
4137
4138 SYNOPSIS
4139 get_quick_select_for_ref()
4140 session Thread handle
4141 table Table to access
4142 ref ref[_or_null] scan parameters
4143 records Estimate of number of records (needed only to construct
4144 quick select)
4145 NOTES
4146 This allocates things in a new memory root, as this may be called many
4147 times during a query.
4148
4149 RETURN
4150 Quick select that retrieves the same rows as passed ref scan
4151 NULL on error.
4152*/
4153
4154optimizer::QuickRangeSelect *optimizer::get_quick_select_for_ref(Session *session,
4155 Table *table,
4156 table_reference_st *ref,
4157 ha_rows records)
4158{
4159 memory::Root *old_root= NULL;
4160 memory::Root *alloc= NULL;
4161 KeyInfo *key_info = &table->key_info[ref->key];
4162 KEY_PART *key_part;
4163 optimizer::QuickRange *range= NULL;
4164 uint32_t part;
4166
4167 old_root= session->mem_root;
4168 /* The following call may change session->mem_root */
4169 optimizer::QuickRangeSelect *quick= new optimizer::QuickRangeSelect(session, table, ref->key, 0, 0);
4170 /* save mem_root set by QuickRangeSelect constructor */
4171 alloc= session->mem_root;
4172 /*
4173 return back default mem_root (session->mem_root) changed by
4174 QuickRangeSelect constructor
4175 */
4176 session->mem_root= old_root;
4177
4178 if (! quick)
4179 return 0; /* no ranges found */
4180 if (quick->init())
4181 goto err;
4182 quick->records= records;
4183
4184 if (cp_buffer_from_ref(session, ref) && session->is_fatal_error)
4185 goto err; // out of memory
4186 range= new (*alloc) optimizer::QuickRange;
4187
4188 range->min_key= range->max_key= ref->key_buff;
4189 range->min_length= range->max_length= ref->key_length;
4190 range->min_keypart_map= range->max_keypart_map=
4191 make_prev_keypart_map(ref->key_parts);
4192 range->flag= (ref->key_length == key_info->key_length && (key_info->flags & HA_END_SPACE_KEY) == 0) ? EQ_RANGE : 0;
4193
4194 quick->key_parts=key_part= new (quick->alloc) KEY_PART[ref->key_parts];
4195
4196 for (part=0 ; part < ref->key_parts ;part++,key_part++)
4197 {
4198 key_part->part=part;
4199 key_part->field= key_info->key_part[part].field;
4200 key_part->length= key_info->key_part[part].length;
4201 key_part->store_length= key_info->key_part[part].store_length;
4202 key_part->null_bit= key_info->key_part[part].null_bit;
4203 key_part->flag= (uint8_t) key_info->key_part[part].key_part_flag;
4204 }
4205 quick->ranges.push_back(&range);
4206
4207 /*
4208 Add a NULL range if REF_OR_NULL optimization is used.
4209 For example:
4210 if we have "WHERE A=2 OR A IS NULL" we created the (A=2) range above
4211 and have ref->null_ref_key set. Will create a new NULL range here.
4212 */
4213 if (ref->null_ref_key)
4214 {
4215 optimizer::QuickRange *null_range= NULL;
4216
4217 *ref->null_ref_key= 1; // Set null byte then create a range
4218 null_range= new (alloc)
4220 make_prev_keypart_map(ref->key_parts),
4221 ref->key_buff, ref->key_length,
4222 make_prev_keypart_map(ref->key_parts), EQ_RANGE);
4223 *ref->null_ref_key= 0; // Clear null byte
4224 quick->ranges.push_back(&null_range);
4225 }
4226
4227 /* Call multi_range_read_info() to get the MRR flags and buffer size */
4228 quick->mrr_flags= HA_MRR_NO_ASSOCIATION |
4229 (table->key_read ? HA_MRR_INDEX_ONLY : 0);
4230 if (session->lex().sql_command != SQLCOM_SELECT)
4231 quick->mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
4232
4233 quick->mrr_buf_size= session->variables.read_rnd_buff_size;
4234 if (table->cursor->multi_range_read_info(quick->index, 1, (uint32_t)records, &quick->mrr_buf_size, &quick->mrr_flags, &cost))
4235 goto err;
4236
4237 return quick;
4238err:
4239 delete quick;
4240 return 0;
4241}
4242
4243
4244/*
4245 Range sequence interface implementation for array<QuickRange>: initialize
4246
4247 SYNOPSIS
4248 quick_range_seq_init()
4249 init_param Caller-opaque paramenter: QuickRangeSelect* pointer
4250 n_ranges Number of ranges in the sequence (ignored)
4251 flags MRR flags (currently not used)
4252
4253 RETURN
4254 Opaque value to be passed to quick_range_seq_next
4255*/
4256
4257range_seq_t optimizer::quick_range_seq_init(void *init_param, uint32_t, uint32_t)
4258{
4259 optimizer::QuickRangeSelect *quick= (optimizer::QuickRangeSelect*)init_param;
4260 quick->qr_traversal_ctx.first= (optimizer::QuickRange**)quick->ranges.buffer;
4261 quick->qr_traversal_ctx.cur= (optimizer::QuickRange**)quick->ranges.buffer;
4262 quick->qr_traversal_ctx.last= quick->qr_traversal_ctx.cur +
4263 quick->ranges.size();
4264 return &quick->qr_traversal_ctx;
4265}
4266
4267
4268/*
4269 Range sequence interface implementation for array<QuickRange>: get next
4270
4271 SYNOPSIS
4272 quick_range_seq_next()
4273 rseq Value returned from quick_range_seq_init
4274 range OUT Store information about the range here
4275
4276 RETURN
4277 0 Ok
4278 1 No more ranges in the sequence
4279*/
4280uint32_t optimizer::quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
4281{
4282 QuickRangeSequenceContext *ctx= (QuickRangeSequenceContext*) rseq;
4283
4284 if (ctx->cur == ctx->last)
4285 return 1; /* no more ranges */
4286
4287 optimizer::QuickRange *cur= *(ctx->cur);
4288 key_range *start_key= &range->start_key;
4289 key_range *end_key= &range->end_key;
4290
4291 start_key->key= cur->min_key;
4292 start_key->length= cur->min_length;
4293 start_key->keypart_map= cur->min_keypart_map;
4294 start_key->flag= ((cur->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
4295 (cur->flag & EQ_RANGE) ?
4296 HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
4297 end_key->key= cur->max_key;
4298 end_key->length= cur->max_length;
4299 end_key->keypart_map= cur->max_keypart_map;
4300 /*
4301 We use HA_READ_AFTER_KEY here because if we are reading on a key
4302 prefix. We want to find all keys with this prefix.
4303 */
4304 end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
4305 HA_READ_AFTER_KEY);
4306 range->range_flag= cur->flag;
4307 ctx->cur++;
4308 return 0;
4309}
4310
4311
4312static inline uint32_t get_field_keypart(KeyInfo *index, Field *field);
4313
4314static inline optimizer::SEL_ARG * get_index_range_tree(uint32_t index,
4315 optimizer::SEL_TREE *range_tree,
4316 optimizer::Parameter *param,
4317 uint32_t *param_idx);
4318
4319static bool get_constant_key_infix(KeyInfo *index_info,
4320 optimizer::SEL_ARG *index_range_tree,
4321 KeyPartInfo *first_non_group_part,
4322 KeyPartInfo *min_max_arg_part,
4323 KeyPartInfo *last_part,
4324 Session *session,
4325 unsigned char *key_infix,
4326 uint32_t *key_infix_len,
4327 KeyPartInfo **first_non_infix_part);
4328
4329static bool check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item);
4330
4331static void
4332cost_group_min_max(Table* table,
4333 KeyInfo *index_info,
4334 uint32_t used_key_parts,
4335 uint32_t group_key_parts,
4336 optimizer::SEL_TREE *range_tree,
4337 optimizer::SEL_ARG *index_tree,
4338 ha_rows quick_prefix_records,
4339 bool have_min,
4340 bool have_max,
4341 double *read_cost,
4342 ha_rows *records);
4343
4344
4345/*
4346 Test if this access method is applicable to a GROUP query with MIN/MAX
4347 functions, and if so, construct a new TRP object.
4348
4349 SYNOPSIS
4350 get_best_group_min_max()
4351 param Parameter from test_quick_select
4352 sel_tree Range tree generated by get_mm_tree
4353
4354 DESCRIPTION
4355 Test whether a query can be computed via a QuickGroupMinMaxSelect.
4356 Queries computable via a QuickGroupMinMaxSelect must satisfy the
4357 following conditions:
4358 A) Table T has at least one compound index I of the form:
4359 I = <A_1, ...,A_k, [B_1,..., B_m], C, [D_1,...,D_n]>
4360 B) Query conditions:
4361 B0. Q is over a single table T.
4362 B1. The attributes referenced by Q are a subset of the attributes of I.
4363 B2. All attributes QA in Q can be divided into 3 overlapping groups:
4364 - SA = {S_1, ..., S_l, [C]} - from the SELECT clause, where C is
4365 referenced by any number of MIN and/or MAX functions if present.
4366 - WA = {W_1, ..., W_p} - from the WHERE clause
4367 - GA = <G_1, ..., G_k> - from the GROUP BY clause (if any)
4368 = SA - if Q is a DISTINCT query (based on the
4369 equivalence of DISTINCT and GROUP queries.
4370 - NGA = QA - (GA union C) = {NG_1, ..., NG_m} - the ones not in
4371 GROUP BY and not referenced by MIN/MAX functions.
4372 with the following properties specified below.
4373 B3. If Q has a GROUP BY WITH ROLLUP clause the access method is not
4374 applicable.
4375
4376 SA1. There is at most one attribute in SA referenced by any number of
4377 MIN and/or MAX functions which, which if present, is denoted as C.
4378 SA2. The position of the C attribute in the index is after the last A_k.
4379 SA3. The attribute C can be referenced in the WHERE clause only in
4380 predicates of the forms:
4381 - (C {< | <= | > | >= | =} const)
4382 - (const {< | <= | > | >= | =} C)
4383 - (C between const_i and const_j)
4384 - C IS NULL
4385 - C IS NOT NULL
4386 - C != const
4387 SA4. If Q has a GROUP BY clause, there are no other aggregate functions
4388 except MIN and MAX. For queries with DISTINCT, aggregate functions
4389 are allowed.
4390 SA5. The select list in DISTINCT queries should not contain expressions.
4391 GA1. If Q has a GROUP BY clause, then GA is a prefix of I. That is, if
4392 G_i = A_j => i = j.
4393 GA2. If Q has a DISTINCT clause, then there is a permutation of SA that
4394 forms a prefix of I. This permutation is used as the GROUP clause
4395 when the DISTINCT query is converted to a GROUP query.
4396 GA3. The attributes in GA may participate in arbitrary predicates, divided
4397 into two groups:
4398 - RNG(G_1,...,G_q ; where q <= k) is a range condition over the
4399 attributes of a prefix of GA
4400 - PA(G_i1,...G_iq) is an arbitrary predicate over an arbitrary subset
4401 of GA. Since P is applied to only GROUP attributes it filters some
4402 groups, and thus can be applied after the grouping.
4403 GA4. There are no expressions among G_i, just direct column references.
4404 NGA1.If in the index I there is a gap between the last GROUP attribute G_k,
4405 and the MIN/MAX attribute C, then NGA must consist of exactly the
4406 index attributes that constitute the gap. As a result there is a
4407 permutation of NGA that coincides with the gap in the index
4408 <B_1, ..., B_m>.
4409 NGA2.If BA <> {}, then the WHERE clause must contain a conjunction EQ of
4410 equality conditions for all NG_i of the form (NG_i = const) or
4411 (const = NG_i), such that each NG_i is referenced in exactly one
4412 conjunct. Informally, the predicates provide constants to fill the
4413 gap in the index.
4414 WA1. There are no other attributes in the WHERE clause except the ones
4415 referenced in predicates RNG, PA, PC, EQ defined above. Therefore
4416 WA is subset of (GA union NGA union C) for GA,NGA,C that pass the
4417 above tests. By transitivity then it also follows that each WA_i
4418 participates in the index I (if this was already tested for GA, NGA
4419 and C).
4420
4421 C) Overall query form:
4422 SELECT EXPR([A_1,...,A_k], [B_1,...,B_m], [MIN(C)], [MAX(C)])
4423 FROM T
4424 WHERE [RNG(A_1,...,A_p ; where p <= k)]
4425 [AND EQ(B_1,...,B_m)]
4426 [AND PC(C)]
4427 [AND PA(A_i1,...,A_iq)]
4428 GROUP BY A_1,...,A_k
4429 [HAVING PH(A_1, ..., B_1,..., C)]
4430 where EXPR(...) is an arbitrary expression over some or all SELECT fields,
4431 or:
4432 SELECT DISTINCT A_i1,...,A_ik
4433 FROM T
4434 WHERE [RNG(A_1,...,A_p ; where p <= k)]
4435 [AND PA(A_i1,...,A_iq)];
4436
4437 NOTES
4438 If the current query satisfies the conditions above, and if
4439 (mem_root! = NULL), then the function constructs and returns a new TRP
4440 object, that is later used to construct a new QuickGroupMinMaxSelect.
4441 If (mem_root == NULL), then the function only tests whether the current
4442 query satisfies the conditions above, and, if so, sets
4443 is_applicable = true.
4444
4445 Queries with DISTINCT for which index access can be used are transformed
4446 into equivalent group-by queries of the form:
4447
4448 SELECT A_1,...,A_k FROM T
4449 WHERE [RNG(A_1,...,A_p ; where p <= k)]
4450 [AND PA(A_i1,...,A_iq)]
4451 GROUP BY A_1,...,A_k;
4452
4453 The group-by list is a permutation of the select attributes, according
4454 to their order in the index.
4455
4456 TODO
4457 - What happens if the query groups by the MIN/MAX field, and there is no
4458 other field as in: "select min(a) from t1 group by a" ?
4459 - We assume that the general correctness of the GROUP-BY query was checked
4460 before this point. Is this correct, or do we have to check it completely?
4461 - Lift the limitation in condition (B3), that is, make this access method
4462 applicable to ROLLUP queries.
4463
4464 RETURN
4465 If mem_root != NULL
4466 - valid GroupMinMaxReadPlan object if this QUICK class can be used for
4467 the query
4468 - NULL o/w.
4469 If mem_root == NULL
4470 - NULL
4471*/
4472static optimizer::GroupMinMaxReadPlan *
4473get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree)
4474{
4475 Session *session= param->session;
4476 Join *join= session->lex().current_select->join;
4477 Table *table= param->table;
4478 bool have_min= false; /* true if there is a MIN function. */
4479 bool have_max= false; /* true if there is a MAX function. */
4480 Item_field *min_max_arg_item= NULL; // The argument of all MIN/MAX functions
4481 KeyPartInfo *min_max_arg_part= NULL; /* The corresponding keypart. */
4482 uint32_t group_prefix_len= 0; /* Length (in bytes) of the key prefix. */
4483 KeyInfo *index_info= NULL; /* The index chosen for data access. */
4484 uint32_t index= 0; /* The id of the chosen index. */
4485 uint32_t group_key_parts= 0; // Number of index key parts in the group prefix.
4486 uint32_t used_key_parts= 0; /* Number of index key parts used for access. */
4487 unsigned char key_infix[MAX_KEY_LENGTH]; /* Constants from equality predicates.*/
4488 uint32_t key_infix_len= 0; /* Length of key_infix. */
4489 optimizer::GroupMinMaxReadPlan *read_plan= NULL; /* The eventually constructed TRP. */
4490 uint32_t key_part_nr;
4491 Order *tmp_group= NULL;
4492 Item *item= NULL;
4493 Item_field *item_field= NULL;
4494
4495 /* Perform few 'cheap' tests whether this access method is applicable. */
4496 if (! join)
4497 return NULL; /* This is not a select statement. */
4498
4499 if ((join->tables != 1) || /* The query must reference one table. */
4500 ((! join->group_list) && /* Neither GROUP BY nor a DISTINCT query. */
4501 (! join->select_distinct)) ||
4502 (join->select_lex->olap == ROLLUP_TYPE)) /* Check (B3) for ROLLUP */
4503 return NULL;
4504 if (table->getShare()->sizeKeys() == 0) /* There are no indexes to use. */
4505 return NULL;
4506
4507 /* Analyze the query in more detail. */
4508 List<Item>::iterator select_items_it(join->fields_list.begin());
4509
4510 /* Check (SA1,SA4) and store the only MIN/MAX argument - the C attribute.*/
4511 if (join->make_sum_func_list(join->all_fields, join->fields_list, 1))
4512 return NULL;
4513
4514 if (join->sum_funcs[0])
4515 {
4516 Item_sum *min_max_item= NULL;
4517 Item_sum **func_ptr= join->sum_funcs;
4518 while ((min_max_item= *(func_ptr++)))
4519 {
4520 if (min_max_item->sum_func() == Item_sum::MIN_FUNC)
4521 have_min= true;
4522 else if (min_max_item->sum_func() == Item_sum::MAX_FUNC)
4523 have_max= true;
4524 else
4525 return NULL;
4526
4527 /* The argument of MIN/MAX. */
4528 Item *expr= min_max_item->args[0]->real_item();
4529 if (expr->type() == Item::FIELD_ITEM) /* Is it an attribute? */
4530 {
4531 if (! min_max_arg_item)
4532 min_max_arg_item= (Item_field*) expr;
4533 else if (! min_max_arg_item->eq(expr, 1))
4534 return NULL;
4535 }
4536 else
4537 return NULL;
4538 }
4539 }
4540
4541 /* Check (SA5). */
4542 if (join->select_distinct)
4543 {
4544 while ((item= select_items_it++))
4545 {
4546 if (item->type() != Item::FIELD_ITEM)
4547 return NULL;
4548 }
4549 }
4550
4551 /* Check (GA4) - that there are no expressions among the group attributes. */
4552 for (tmp_group= join->group_list; tmp_group; tmp_group= tmp_group->next)
4553 {
4554 if ((*tmp_group->item)->type() != Item::FIELD_ITEM)
4555 return NULL;
4556 }
4557
4558 /*
4559 Check that table has at least one compound index such that the conditions
4560 (GA1,GA2) are all true. If there is more than one such index, select the
4561 first one. Here we set the variables: group_prefix_len and index_info.
4562 */
4563 KeyInfo *cur_index_info= table->key_info;
4564 KeyInfo *cur_index_info_end= cur_index_info + table->getShare()->sizeKeys();
4565 KeyPartInfo *cur_part= NULL;
4566 KeyPartInfo *end_part= NULL; /* Last part for loops. */
4567 /* Last index part. */
4568 KeyPartInfo *last_part= NULL;
4569 KeyPartInfo *first_non_group_part= NULL;
4570 KeyPartInfo *first_non_infix_part= NULL;
4571 uint32_t key_infix_parts= 0;
4572 uint32_t cur_group_key_parts= 0;
4573 uint32_t cur_group_prefix_len= 0;
4574 /* Cost-related variables for the best index so far. */
4575 double best_read_cost= DBL_MAX;
4576 ha_rows best_records= 0;
4577 optimizer::SEL_ARG *best_index_tree= NULL;
4578 ha_rows best_quick_prefix_records= 0;
4579 uint32_t best_param_idx= 0;
4580 double cur_read_cost= DBL_MAX;
4581 ha_rows cur_records;
4582 optimizer::SEL_ARG *cur_index_tree= NULL;
4583 ha_rows cur_quick_prefix_records= 0;
4584 uint32_t cur_param_idx= MAX_KEY;
4585 key_map used_key_parts_map;
4586 uint32_t cur_key_infix_len= 0;
4587 unsigned char cur_key_infix[MAX_KEY_LENGTH];
4588 uint32_t cur_used_key_parts= 0;
4589 uint32_t pk= param->table->getShare()->getPrimaryKey();
4590
4591 for (uint32_t cur_index= 0;
4592 cur_index_info != cur_index_info_end;
4593 cur_index_info++, cur_index++)
4594 {
4595 /* Check (B1) - if current index is covering. */
4596 if (! table->covering_keys.test(cur_index))
4597 goto next_index;
4598
4599 /*
4600 If the current storage manager is such that it appends the primary key to
4601 each index, then the above condition is insufficient to check if the
4602 index is covering. In such cases it may happen that some fields are
4603 covered by the PK index, but not by the current index. Since we can't
4604 use the concatenation of both indexes for index lookup, such an index
4605 does not qualify as covering in our case. If this is the case, below
4606 we check that all query fields are indeed covered by 'cur_index'.
4607 */
4608 if (pk < MAX_KEY && cur_index != pk &&
4609 (table->cursor->getEngine()->check_flag(HTON_BIT_PRIMARY_KEY_IN_READ_INDEX)))
4610 {
4611 /* For each table field */
4612 for (uint32_t i= 0; i < table->getShare()->sizeFields(); i++)
4613 {
4614 Field *cur_field= table->getField(i);
4615 /*
4616 If the field is used in the current query ensure that it's
4617 part of 'cur_index'
4618 */
4619 if ((cur_field->isReadSet()) &&
4620 ! cur_field->part_of_key_not_clustered.test(cur_index))
4621 goto next_index; // Field was not part of key
4622 }
4623 }
4624
4625 /*
4626 Check (GA1) for GROUP BY queries.
4627 */
4628 if (join->group_list)
4629 {
4630 cur_part= cur_index_info->key_part;
4631 end_part= cur_part + cur_index_info->key_parts;
4632 /* Iterate in parallel over the GROUP list and the index parts. */
4633 for (tmp_group= join->group_list;
4634 tmp_group && (cur_part != end_part);
4635 tmp_group= tmp_group->next, cur_part++)
4636 {
4637 /*
4638 TODO:
4639 tmp_group::item is an array of Item, is it OK to consider only the
4640 first Item? If so, then why? What is the array for?
4641 */
4642 /* Above we already checked that all group items are fields. */
4643 assert((*tmp_group->item)->type() == Item::FIELD_ITEM);
4644 Item_field *group_field= (Item_field *) (*tmp_group->item);
4645 if (group_field->field->eq(cur_part->field))
4646 {
4647 cur_group_prefix_len+= cur_part->store_length;
4648 ++cur_group_key_parts;
4649 }
4650 else
4651 goto next_index;
4652 }
4653 }
4654 /*
4655 Check (GA2) if this is a DISTINCT query.
4656 If GA2, then Store a new order_st object in group_fields_array at the
4657 position of the key part of item_field->field. Thus we get the order_st
4658 objects for each field ordered as the corresponding key parts.
4659 Later group_fields_array of order_st objects is used to convert the query
4660 to a GROUP query.
4661 */
4662 else if (join->select_distinct)
4663 {
4664 select_items_it= join->fields_list.begin();
4665 used_key_parts_map.reset();
4666 uint32_t max_key_part= 0;
4667 while ((item= select_items_it++))
4668 {
4669 item_field= (Item_field*) item; /* (SA5) already checked above. */
4670 /* Find the order of the key part in the index. */
4671 key_part_nr= get_field_keypart(cur_index_info, item_field->field);
4672 /*
4673 Check if this attribute was already present in the select list.
4674 If it was present, then its corresponding key part was alredy used.
4675 */
4676 if (used_key_parts_map.test(key_part_nr))
4677 continue;
4678 if (key_part_nr < 1 || key_part_nr > join->fields_list.size())
4679 goto next_index;
4680 cur_part= cur_index_info->key_part + key_part_nr - 1;
4681 cur_group_prefix_len+= cur_part->store_length;
4682 used_key_parts_map.set(key_part_nr);
4683 ++cur_group_key_parts;
4684 max_key_part= max(max_key_part,key_part_nr);
4685 }
4686 /*
4687 Check that used key parts forms a prefix of the index.
4688 To check this we compare bits in all_parts and cur_parts.
4689 all_parts have all bits set from 0 to (max_key_part-1).
4690 cur_parts have bits set for only used keyparts.
4691 */
4692 key_map all_parts;
4693 key_map cur_parts;
4694 for (uint32_t pos= 0; pos < max_key_part; pos++)
4695 all_parts.set(pos);
4696 cur_parts= used_key_parts_map >> 1;
4697 if (all_parts != cur_parts)
4698 goto next_index;
4699 }
4700 else
4701 assert(false);
4702
4703 /* Check (SA2). */
4704 if (min_max_arg_item)
4705 {
4706 key_part_nr= get_field_keypart(cur_index_info, min_max_arg_item->field);
4707 if (key_part_nr <= cur_group_key_parts)
4708 goto next_index;
4709 min_max_arg_part= cur_index_info->key_part + key_part_nr - 1;
4710 }
4711
4712 /*
4713 Check (NGA1, NGA2) and extract a sequence of constants to be used as part
4714 of all search keys.
4715 */
4716
4717 /*
4718 If there is MIN/MAX, each keypart between the last group part and the
4719 MIN/MAX part must participate in one equality with constants, and all
4720 keyparts after the MIN/MAX part must not be referenced in the query.
4721
4722 If there is no MIN/MAX, the keyparts after the last group part can be
4723 referenced only in equalities with constants, and the referenced keyparts
4724 must form a sequence without any gaps that starts immediately after the
4725 last group keypart.
4726 */
4727 last_part= cur_index_info->key_part + cur_index_info->key_parts;
4728 first_non_group_part= (cur_group_key_parts < cur_index_info->key_parts) ?
4729 cur_index_info->key_part + cur_group_key_parts :
4730 NULL;
4731 first_non_infix_part= min_max_arg_part ?
4732 (min_max_arg_part < last_part) ?
4733 min_max_arg_part :
4734 NULL :
4735 NULL;
4736 if (first_non_group_part &&
4737 (! min_max_arg_part || (min_max_arg_part - first_non_group_part > 0)))
4738 {
4739 if (tree)
4740 {
4741 uint32_t dummy;
4742 optimizer::SEL_ARG *index_range_tree= get_index_range_tree(cur_index,
4743 tree,
4744 param,
4745 &dummy);
4746 if (! get_constant_key_infix(cur_index_info,
4747 index_range_tree,
4748 first_non_group_part,
4749 min_max_arg_part,
4750 last_part,
4751 session,
4752 cur_key_infix,
4753 &cur_key_infix_len,
4754 &first_non_infix_part))
4755 {
4756 goto next_index;
4757 }
4758 }
4759 else if (min_max_arg_part &&
4760 (min_max_arg_part - first_non_group_part > 0))
4761 {
4762 /*
4763 There is a gap but no range tree, thus no predicates at all for the
4764 non-group keyparts.
4765 */
4766 goto next_index;
4767 }
4768 else if (first_non_group_part && join->conds)
4769 {
4770 /*
4771 If there is no MIN/MAX function in the query, but some index
4772 key part is referenced in the WHERE clause, then this index
4773 cannot be used because the WHERE condition over the keypart's
4774 field cannot be 'pushed' to the index (because there is no
4775 range 'tree'), and the WHERE clause must be evaluated before
4776 GROUP BY/DISTINCT.
4777 */
4778 /*
4779 Store the first and last keyparts that need to be analyzed
4780 into one array that can be passed as parameter.
4781 */
4782 KeyPartInfo *key_part_range[2];
4783 key_part_range[0]= first_non_group_part;
4784 key_part_range[1]= last_part;
4785
4786 /* Check if cur_part is referenced in the WHERE clause. */
4787 if (join->conds->walk(&Item::find_item_in_field_list_processor,
4788 0,
4789 (unsigned char*) key_part_range))
4790 goto next_index;
4791 }
4792 }
4793
4794 /*
4795 Test (WA1) partially - that no other keypart after the last infix part is
4796 referenced in the query.
4797 */
4798 if (first_non_infix_part)
4799 {
4800 cur_part= first_non_infix_part +
4801 (min_max_arg_part && (min_max_arg_part < last_part));
4802 for (; cur_part != last_part; cur_part++)
4803 {
4804 if (cur_part->field->isReadSet())
4805 goto next_index;
4806 }
4807 }
4808
4809 /* If we got to this point, cur_index_info passes the test. */
4810 key_infix_parts= cur_key_infix_len ?
4811 (first_non_infix_part - first_non_group_part) : 0;
4812 cur_used_key_parts= cur_group_key_parts + key_infix_parts;
4813
4814 /* Compute the cost of using this index. */
4815 if (tree)
4816 {
4817 /* Find the SEL_ARG sub-tree that corresponds to the chosen index. */
4818 cur_index_tree= get_index_range_tree(cur_index,
4819 tree,
4820 param,
4821 &cur_param_idx);
4822 /* Check if this range tree can be used for prefix retrieval. */
4823 optimizer::CostVector dummy_cost;
4824 uint32_t mrr_flags= HA_MRR_USE_DEFAULT_IMPL;
4825 uint32_t mrr_bufsize= 0;
4826 cur_quick_prefix_records= check_quick_select(session,
4827 param,
4828 cur_param_idx,
4829 false /*don't care*/,
4830 cur_index_tree,
4831 true,
4832 &mrr_flags,
4833 &mrr_bufsize,
4834 &dummy_cost);
4835 }
4836 cost_group_min_max(table,
4837 cur_index_info,
4838 cur_used_key_parts,
4839 cur_group_key_parts,
4840 tree,
4841 cur_index_tree,
4842 cur_quick_prefix_records,
4843 have_min,
4844 have_max,
4845 &cur_read_cost,
4846 &cur_records);
4847 /*
4848 If cur_read_cost is lower than best_read_cost use cur_index.
4849 Do not compare doubles directly because they may have different
4850 representations (64 vs. 80 bits).
4851 */
4852 if (cur_read_cost < best_read_cost - (DBL_EPSILON * cur_read_cost))
4853 {
4854 assert(tree != 0 || cur_param_idx == MAX_KEY);
4855 index_info= cur_index_info;
4856 index= cur_index;
4857 best_read_cost= cur_read_cost;
4858 best_records= cur_records;
4859 best_index_tree= cur_index_tree;
4860 best_quick_prefix_records= cur_quick_prefix_records;
4861 best_param_idx= cur_param_idx;
4862 group_key_parts= cur_group_key_parts;
4863 group_prefix_len= cur_group_prefix_len;
4864 key_infix_len= cur_key_infix_len;
4865
4866 if (key_infix_len)
4867 {
4868 memcpy(key_infix, cur_key_infix, sizeof (key_infix));
4869 }
4870
4871 used_key_parts= cur_used_key_parts;
4872 }
4873
4874 next_index:
4875 cur_group_key_parts= 0;
4876 cur_group_prefix_len= 0;
4877 cur_key_infix_len= 0;
4878 }
4879 if (! index_info) /* No usable index found. */
4880 return NULL;
4881
4882 /* Check (SA3) for the where clause. */
4883 if (join->conds && min_max_arg_item &&
4884 ! check_group_min_max_predicates(join->conds, min_max_arg_item))
4885 return NULL;
4886
4887 /* The query passes all tests, so construct a new TRP object. */
4888 read_plan= new (*param->mem_root) optimizer::GroupMinMaxReadPlan(have_min,
4889 have_max,
4890 min_max_arg_part,
4891 group_prefix_len,
4892 used_key_parts,
4893 group_key_parts,
4894 index_info,
4895 index,
4896 key_infix_len,
4897 (key_infix_len > 0) ? key_infix : NULL,
4898 tree,
4899 best_index_tree,
4900 best_param_idx,
4901 best_quick_prefix_records);
4902 if (tree && read_plan->quick_prefix_records == 0)
4903 return NULL;
4904 read_plan->read_cost= best_read_cost;
4905 read_plan->records= best_records;
4906 return read_plan;
4907}
4908
4909
4910/*
4911 Check that the MIN/MAX attribute participates only in range predicates
4912 with constants.
4913
4914 SYNOPSIS
4915 check_group_min_max_predicates()
4916 cond tree (or subtree) describing all or part of the WHERE
4917 clause being analyzed
4918 min_max_arg_item the field referenced by the MIN/MAX function(s)
4919 min_max_arg_part the keypart of the MIN/MAX argument if any
4920
4921 DESCRIPTION
4922 The function walks recursively over the cond tree representing a WHERE
4923 clause, and checks condition (SA3) - if a field is referenced by a MIN/MAX
4924 aggregate function, it is referenced only by one of the following
4925 predicates: {=, !=, <, <=, >, >=, between, is null, is not null}.
4926
4927 RETURN
4928 true if cond passes the test
4929 false o/w
4930*/
4931static bool check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item)
4932{
4933 assert(cond && min_max_arg_item);
4934
4935 cond= cond->real_item();
4936 Item::Type cond_type= cond->type();
4937 if (cond_type == Item::COND_ITEM) /* 'AND' or 'OR' */
4938 {
4939 List<Item>::iterator li(((Item_cond*) cond)->argument_list()->begin());
4940 Item *and_or_arg= NULL;
4941 while ((and_or_arg= li++))
4942 {
4943 if (! check_group_min_max_predicates(and_or_arg, min_max_arg_item))
4944 return false;
4945 }
4946 return true;
4947 }
4948
4949 /*
4950 TODO:
4951 This is a very crude fix to handle sub-selects in the WHERE clause
4952 (Item_subselect objects). With the test below we rule out from the
4953 optimization all queries with subselects in the WHERE clause. What has to
4954 be done, is that here we should analyze whether the subselect references
4955 the MIN/MAX argument field, and disallow the optimization only if this is
4956 so.
4957 */
4958 if (cond_type == Item::SUBSELECT_ITEM)
4959 return false;
4960
4961 /* We presume that at this point there are no other Items than functions. */
4962 assert(cond_type == Item::FUNC_ITEM);
4963
4964 /* Test if cond references only group-by or non-group fields. */
4965 Item_func *pred= (Item_func*) cond;
4966 Item **arguments= pred->arguments();
4967 Item *cur_arg= NULL;
4968 for (uint32_t arg_idx= 0; arg_idx < pred->argument_count (); arg_idx++)
4969 {
4970 cur_arg= arguments[arg_idx]->real_item();
4971 if (cur_arg->type() == Item::FIELD_ITEM)
4972 {
4973 if (min_max_arg_item->eq(cur_arg, 1))
4974 {
4975 /*
4976 If pred references the MIN/MAX argument, check whether pred is a range
4977 condition that compares the MIN/MAX argument with a constant.
4978 */
4979 Item_func::Functype pred_type= pred->functype();
4980 if (pred_type != Item_func::EQUAL_FUNC &&
4981 pred_type != Item_func::LT_FUNC &&
4982 pred_type != Item_func::LE_FUNC &&
4983 pred_type != Item_func::GT_FUNC &&
4984 pred_type != Item_func::GE_FUNC &&
4985 pred_type != Item_func::BETWEEN &&
4986 pred_type != Item_func::ISNULL_FUNC &&
4987 pred_type != Item_func::ISNOTNULL_FUNC &&
4988 pred_type != Item_func::EQ_FUNC &&
4989 pred_type != Item_func::NE_FUNC)
4990 return false;
4991
4992 /* Check that pred compares min_max_arg_item with a constant. */
4993 Item *args[3];
4994 memset(args, 0, 3 * sizeof(Item*));
4995 bool inv= false;
4996 /* Test if this is a comparison of a field and a constant. */
4997 if (! optimizer::simple_pred(pred, args, inv))
4998 return false;
4999
5000 /* Check for compatible string comparisons - similar to get_mm_leaf. */
5001 if (args[0] && args[1] && !args[2] && // this is a binary function
5002 min_max_arg_item->result_type() == STRING_RESULT &&
5003 /*
5004 Don't use an index when comparing strings of different collations.
5005 */
5006 ((args[1]->result_type() == STRING_RESULT &&
5007 ((Field_str*) min_max_arg_item->field)->charset() !=
5008 pred->compare_collation())
5009 ||
5010 /*
5011 We can't always use indexes when comparing a string index to a
5012 number.
5013 */
5014 (args[1]->result_type() != STRING_RESULT &&
5015 min_max_arg_item->field->cmp_type() != args[1]->result_type())))
5016 {
5017 return false;
5018 }
5019 }
5020 }
5021 else if (cur_arg->type() == Item::FUNC_ITEM)
5022 {
5023 if (! check_group_min_max_predicates(cur_arg, min_max_arg_item))
5024 return false;
5025 }
5026 else if (cur_arg->const_item())
5027 {
5028 return true;
5029 }
5030 else
5031 return false;
5032 }
5033
5034 return true;
5035}
5036
5037
5038/*
5039 Extract a sequence of constants from a conjunction of equality predicates.
5040
5041 SYNOPSIS
5042 get_constant_key_infix()
5043 index_info [in] Descriptor of the chosen index.
5044 index_range_tree [in] Range tree for the chosen index
5045 first_non_group_part [in] First index part after group attribute parts
5046 min_max_arg_part [in] The keypart of the MIN/MAX argument if any
5047 last_part [in] Last keypart of the index
5048 session [in] Current thread
5049 key_infix [out] Infix of constants to be used for index lookup
5050 key_infix_len [out] Lenghth of the infix
5051 first_non_infix_part [out] The first keypart after the infix (if any)
5052
5053 DESCRIPTION
5054 Test conditions (NGA1, NGA2) from get_best_group_min_max(). Namely,
5055 for each keypart field NGF_i not in GROUP-BY, check that there is a
5056 constant equality predicate among conds with the form (NGF_i = const_ci) or
5057 (const_ci = NGF_i).
5058 Thus all the NGF_i attributes must fill the 'gap' between the last group-by
5059 attribute and the MIN/MAX attribute in the index (if present). If these
5060 conditions hold, copy each constant from its corresponding predicate into
5061 key_infix, in the order its NG_i attribute appears in the index, and update
5062 key_infix_len with the total length of the key parts in key_infix.
5063
5064 RETURN
5065 true if the index passes the test
5066 false o/w
5067*/
5068static bool
5069get_constant_key_infix(KeyInfo *,
5070 optimizer::SEL_ARG *index_range_tree,
5071 KeyPartInfo *first_non_group_part,
5072 KeyPartInfo *min_max_arg_part,
5073 KeyPartInfo *last_part,
5074 Session *,
5075 unsigned char *key_infix,
5076 uint32_t *key_infix_len,
5077 KeyPartInfo **first_non_infix_part)
5078{
5079 optimizer::SEL_ARG *cur_range= NULL;
5080 KeyPartInfo *cur_part= NULL;
5081 /* End part for the first loop below. */
5082 KeyPartInfo *end_part= min_max_arg_part ? min_max_arg_part : last_part;
5083
5084 *key_infix_len= 0;
5085 unsigned char *key_ptr= key_infix;
5086 for (cur_part= first_non_group_part; cur_part != end_part; cur_part++)
5087 {
5088 /*
5089 Find the range tree for the current keypart. We assume that
5090 index_range_tree points to the leftmost keypart in the index.
5091 */
5092 for (cur_range= index_range_tree; cur_range;
5093 cur_range= cur_range->next_key_part)
5094 {
5095 if (cur_range->field->eq(cur_part->field))
5096 break;
5097 }
5098 if (! cur_range)
5099 {
5100 if (min_max_arg_part)
5101 return false; /* The current keypart has no range predicates at all. */
5102 else
5103 {
5104 *first_non_infix_part= cur_part;
5105 return true;
5106 }
5107 }
5108
5109 /* Check that the current range tree is a single point interval. */
5110 if (cur_range->prev || cur_range->next)
5111 return false; /* This is not the only range predicate for the field. */
5112 if ((cur_range->min_flag & NO_MIN_RANGE) ||
5113 (cur_range->max_flag & NO_MAX_RANGE) ||
5114 (cur_range->min_flag & NEAR_MIN) ||
5115 (cur_range->max_flag & NEAR_MAX))
5116 return false;
5117
5118 uint32_t field_length= cur_part->store_length;
5119 if ((cur_range->maybe_null &&
5120 cur_range->min_value[0] && cur_range->max_value[0]) ||
5121 !memcmp(cur_range->min_value, cur_range->max_value, field_length))
5122 {
5123 /* cur_range specifies 'IS NULL' or an equality condition. */
5124 memcpy(key_ptr, cur_range->min_value, field_length);
5125 key_ptr+= field_length;
5126 *key_infix_len+= field_length;
5127 }
5128 else
5129 return false;
5130 }
5131
5132 if (!min_max_arg_part && (cur_part == last_part))
5133 *first_non_infix_part= last_part;
5134
5135 return true;
5136}
5137
5138
5139/*
5140 Find the key part referenced by a field.
5141
5142 SYNOPSIS
5143 get_field_keypart()
5144 index descriptor of an index
5145 field field that possibly references some key part in index
5146
5147 NOTES
5148 The return value can be used to get a KeyPartInfo pointer by
5149 part= index->key_part + get_field_keypart(...) - 1;
5150
5151 RETURN
5152 Positive number which is the consecutive number of the key part, or
5153 0 if field does not reference any index field.
5154*/
5155static inline uint
5156get_field_keypart(KeyInfo *index, Field *field)
5157{
5158 KeyPartInfo *part= NULL;
5159 KeyPartInfo *end= NULL;
5160
5161 for (part= index->key_part, end= part + index->key_parts; part < end; part++)
5162 {
5163 if (field->eq(part->field))
5164 return part - index->key_part + 1;
5165 }
5166 return 0;
5167}
5168
5169
5170/*
5171 Find the SEL_ARG sub-tree that corresponds to the chosen index.
5172
5173 SYNOPSIS
5174 get_index_range_tree()
5175 index [in] The ID of the index being looked for
5176 range_tree[in] Tree of ranges being searched
5177 param [in] Parameter from SqlSelect::test_quick_select
5178 param_idx [out] Index in the array Parameter::key that corresponds to 'index'
5179
5180 DESCRIPTION
5181
5182 A optimizer::SEL_TREE contains range trees for all usable indexes. This procedure
5183 finds the SEL_ARG sub-tree for 'index'. The members of a optimizer::SEL_TREE are
5184 ordered in the same way as the members of Parameter::key, thus we first find
5185 the corresponding index in the array Parameter::key. This index is returned
5186 through the variable param_idx, to be used later as argument of
5187 check_quick_select().
5188
5189 RETURN
5190 Pointer to the SEL_ARG subtree that corresponds to index.
5191*/
5192optimizer::SEL_ARG *get_index_range_tree(uint32_t index,
5193 optimizer::SEL_TREE* range_tree,
5194 optimizer::Parameter *param,
5195 uint32_t *param_idx)
5196{
5197 uint32_t idx= 0; /* Index nr in param->key_parts */
5198 while (idx < param->keys)
5199 {
5200 if (index == param->real_keynr[idx])
5201 break;
5202 idx++;
5203 }
5204 *param_idx= idx;
5205 return range_tree->keys[idx];
5206}
5207
5208
5209/*
5210 Compute the cost of a quick_group_min_max_select for a particular index.
5211
5212 SYNOPSIS
5213 cost_group_min_max()
5214 table [in] The table being accessed
5215 index_info [in] The index used to access the table
5216 used_key_parts [in] Number of key parts used to access the index
5217 group_key_parts [in] Number of index key parts in the group prefix
5218 range_tree [in] Tree of ranges for all indexes
5219 index_tree [in] The range tree for the current index
5220 quick_prefix_records [in] Number of records retrieved by the internally
5221 used quick range select if any
5222 have_min [in] True if there is a MIN function
5223 have_max [in] True if there is a MAX function
5224 read_cost [out] The cost to retrieve rows via this quick select
5225 records [out] The number of rows retrieved
5226
5227 DESCRIPTION
5228 This method computes the access cost of a GroupMinMaxReadPlan instance and
5229 the number of rows returned. It updates this->read_cost and this->records.
5230
5231 NOTES
5232 The cost computation distinguishes several cases:
5233 1) No equality predicates over non-group attributes (thus no key_infix).
5234 If groups are bigger than blocks on the average, then we assume that it
5235 is very unlikely that block ends are aligned with group ends, thus even
5236 if we look for both MIN and MAX keys, all pairs of neighbor MIN/MAX
5237 keys, except for the first MIN and the last MAX keys, will be in the
5238 same block. If groups are smaller than blocks, then we are going to
5239 read all blocks.
5240 2) There are equality predicates over non-group attributes.
5241 In this case the group prefix is extended by additional constants, and
5242 as a result the min/max values are inside sub-groups of the original
5243 groups. The number of blocks that will be read depends on whether the
5244 ends of these sub-groups will be contained in the same or in different
5245 blocks. We compute the probability for the two ends of a subgroup to be
5246 in two different blocks as the ratio of:
5247 - the number of positions of the left-end of a subgroup inside a group,
5248 such that the right end of the subgroup is past the end of the buffer
5249 containing the left-end, and
5250 - the total number of possible positions for the left-end of the
5251 subgroup, which is the number of keys in the containing group.
5252 We assume it is very unlikely that two ends of subsequent subgroups are
5253 in the same block.
5254 3) The are range predicates over the group attributes.
5255 Then some groups may be filtered by the range predicates. We use the
5256 selectivity of the range predicates to decide how many groups will be
5257 filtered.
5258
5259 TODO
5260 - Take into account the optional range predicates over the MIN/MAX
5261 argument.
5262 - Check if we have a PK index and we use all cols - then each key is a
5263 group, and it will be better to use an index scan.
5264
5265 RETURN
5266 None
5267*/
5268void cost_group_min_max(Table* table,
5269 KeyInfo *index_info,
5270 uint32_t used_key_parts,
5271 uint32_t group_key_parts,
5272 optimizer::SEL_TREE *range_tree,
5273 optimizer::SEL_ARG *,
5274 ha_rows quick_prefix_records,
5275 bool have_min,
5276 bool have_max,
5277 double *read_cost,
5278 ha_rows *records)
5279{
5280 ha_rows table_records;
5281 uint32_t num_groups;
5282 uint32_t num_blocks;
5283 uint32_t keys_per_block;
5284 uint32_t keys_per_group;
5285 uint32_t keys_per_subgroup; /* Average number of keys in sub-groups */
5286 /* formed by a key infix. */
5287 double p_overlap; /* Probability that a sub-group overlaps two blocks. */
5288 double quick_prefix_selectivity;
5289 double io_cost;
5290 double cpu_cost= 0; /* TODO: CPU cost of index_read calls? */
5291
5292 table_records= table->cursor->stats.records;
5293 keys_per_block= (table->cursor->stats.block_size / 2 /
5294 (index_info->key_length + table->cursor->ref_length)
5295 + 1);
5296 num_blocks= (uint32_t) (table_records / keys_per_block) + 1;
5297
5298 /* Compute the number of keys in a group. */
5299 keys_per_group= index_info->rec_per_key[group_key_parts - 1];
5300 if (keys_per_group == 0) /* If there is no statistics try to guess */
5301 /* each group contains 10% of all records */
5302 keys_per_group= (uint32_t)(table_records / 10) + 1;
5303 num_groups= (uint32_t)(table_records / keys_per_group) + 1;
5304
5305 /* Apply the selectivity of the quick select for group prefixes. */
5306 if (range_tree && (quick_prefix_records != HA_POS_ERROR))
5307 {
5308 quick_prefix_selectivity= (double) quick_prefix_records /
5309 (double) table_records;
5310 num_groups= (uint32_t) rint(num_groups * quick_prefix_selectivity);
5311 set_if_bigger(num_groups, 1U);
5312 }
5313
5314 if (used_key_parts > group_key_parts)
5315 { /*
5316 Compute the probability that two ends of a subgroup are inside
5317 different blocks.
5318 */
5319 keys_per_subgroup= index_info->rec_per_key[used_key_parts - 1];
5320 if (keys_per_subgroup >= keys_per_block) /* If a subgroup is bigger than */
5321 p_overlap= 1.0; /* a block, it will overlap at least two blocks. */
5322 else
5323 {
5324 double blocks_per_group= (double) num_blocks / (double) num_groups;
5325 p_overlap= (blocks_per_group * (keys_per_subgroup - 1)) / keys_per_group;
5326 p_overlap= min(p_overlap, 1.0);
5327 }
5328 io_cost= (double) min(num_groups * (1 + p_overlap), (double)num_blocks);
5329 }
5330 else
5331 io_cost= (keys_per_group > keys_per_block) ?
5332 (have_min && have_max) ? (double) (num_groups + 1) :
5333 (double) num_groups :
5334 (double) num_blocks;
5335
5336 /*
5337 TODO: If there is no WHERE clause and no other expressions, there should be
5338 no CPU cost. We leave it here to make this cost comparable to that of index
5339 scan as computed in SqlSelect::test_quick_select().
5340 */
5341 cpu_cost= (double) num_groups / TIME_FOR_COMPARE;
5342
5343 *read_cost= io_cost + cpu_cost;
5344 *records= num_groups;
5345}
5346
5347
5348/*
5349 Construct a new quick select object for queries with group by with min/max.
5350
5351 SYNOPSIS
5352 GroupMinMaxReadPlan::make_quick()
5353 param Parameter from test_quick_select
5354 retrieve_full_rows ignored
5355 parent_alloc Memory pool to use, if any.
5356
5357 NOTES
5358 Make_quick ignores the retrieve_full_rows parameter because
5359 QuickGroupMinMaxSelect always performs 'index only' scans.
5360 The other parameter are ignored as well because all necessary
5361 data to create the QUICK object is computed at this TRP creation
5362 time.
5363
5364 RETURN
5365 New QuickGroupMinMaxSelect object if successfully created,
5366 NULL otherwise.
5367*/
5368optimizer::QuickSelectInterface *
5369optimizer::GroupMinMaxReadPlan::make_quick(optimizer::Parameter *param, bool, memory::Root *parent_alloc)
5370{
5371 optimizer::QuickGroupMinMaxSelect *quick= new optimizer::QuickGroupMinMaxSelect(param->table,
5372 param->session->lex().current_select->join,
5373 have_min,
5374 have_max,
5375 min_max_arg_part,
5376 group_prefix_len,
5377 group_key_parts,
5378 used_key_parts,
5379 index_info,
5380 index,
5381 read_cost,
5382 records,
5383 key_infix_len,
5384 key_infix,
5385 parent_alloc);
5386 if (quick->init())
5387 {
5388 delete quick;
5389 return NULL;
5390 }
5391
5392 if (range_tree)
5393 {
5394 assert(quick_prefix_records > 0);
5395 if (quick_prefix_records == HA_POS_ERROR)
5396 {
5397 quick->quick_prefix_select= NULL; /* Can't construct a quick select. */
5398 }
5399 else
5400 {
5401 /* Make a QuickRangeSelect to be used for group prefix retrieval. */
5402 quick->quick_prefix_select= optimizer::get_quick_select(param,
5403 param_idx,
5404 index_tree,
5405 HA_MRR_USE_DEFAULT_IMPL,
5406 0,
5407 &quick->alloc);
5408 }
5409
5410 /*
5411 Extract the SEL_ARG subtree that contains only ranges for the MIN/MAX
5412 attribute, and create an array of QuickRanges to be used by the
5413 new quick select.
5414 */
5415 if (min_max_arg_part)
5416 {
5417 optimizer::SEL_ARG *min_max_range= index_tree;
5418 while (min_max_range) /* Find the tree for the MIN/MAX key part. */
5419 {
5420 if (min_max_range->field->eq(min_max_arg_part->field))
5421 break;
5422 min_max_range= min_max_range->next_key_part;
5423 }
5424 /* Scroll to the leftmost interval for the MIN/MAX argument. */
5425 while (min_max_range && min_max_range->prev)
5426 min_max_range= min_max_range->prev;
5427 /* Create an array of QuickRanges for the MIN/MAX argument. */
5428 while (min_max_range)
5429 {
5430 if (quick->add_range(min_max_range))
5431 {
5432 delete quick;
5433 quick= NULL;
5434 return NULL;
5435 }
5436 min_max_range= min_max_range->next;
5437 }
5438 }
5439 }
5440 else
5441 quick->quick_prefix_select= NULL;
5442
5443 quick->update_key_stat();
5444 quick->adjust_prefix_ranges();
5445
5446 return quick;
5447}
5448
5449
5450optimizer::QuickSelectInterface *optimizer::RangeReadPlan::make_quick(optimizer::Parameter *param, bool, memory::Root *parent_alloc)
5451{
5452 optimizer::QuickRangeSelect *quick= optimizer::get_quick_select(param, key_idx, key, mrr_flags, mrr_buf_size, parent_alloc);
5453 if (quick)
5454 {
5455 quick->records= records;
5456 quick->read_time= read_cost;
5457 }
5458 return quick;
5459}
5460
5461
5462uint32_t optimizer::RorScanInfo::findFirstNotSet() const
5463{
5464 boost::dynamic_bitset<> map= bitsToBitset();
5465 for (boost::dynamic_bitset<>::size_type i= 0; i < map.size(); i++)
5466 {
5467 if (not map.test(i))
5468 return i;
5469 }
5470 return map.size();
5471}
5472
5473
5474size_t optimizer::RorScanInfo::getBitCount() const
5475{
5476 boost::dynamic_bitset<> tmp_bitset= bitsToBitset();
5477 return tmp_bitset.count();
5478}
5479
5480
5481void optimizer::RorScanInfo::subtractBitset(const boost::dynamic_bitset<>& in_bitset)
5482{
5483 boost::dynamic_bitset<> tmp_bitset= bitsToBitset();
5484 tmp_bitset-= in_bitset;
5485 covered_fields= tmp_bitset.to_ulong();
5486}
5487
5488
5489boost::dynamic_bitset<> optimizer::RorScanInfo::bitsToBitset() const
5490{
5491 string res;
5492 uint64_t conv= covered_fields;
5493 while (conv)
5494 {
5495 res.push_back((conv & 1) + '0');
5496 conv>>= 1;
5497 }
5498 if (! res.empty())
5499 {
5500 std::reverse(res.begin(), res.end());
5501 }
5502 string final(covered_fields_size - res.length(), '0');
5503 final.append(res);
5504 return boost::dynamic_bitset<>(final);
5505}
5506
5507
5508} /* namespace drizzled */
drizzle_system_variables & variables
Definition session.h:195
QuickRangeSequenceContext qr_traversal_ctx
virtual bool is_keys_used(const boost::dynamic_bitset<> &fields)
Definition range.cc:4129
#define TIME_FOR_COMPARE_ROWID
#define STACK_MIN_SIZE
Abort if less stack during eval.
#define TIME_FOR_COMPARE
TODO: Rename this file - func.h is stupid.
bool field_is_equal_to_item(Field *field, Item *item)
Definition item.cc:1486
bool check_stack_overrun(Session *session, long margin, void *)
static void get_sweep_read_cost(Table *table, ha_rows nrows, bool interrupted, optimizer::CostVector *cost)
Definition range.cc:208
STL namespace.
Definition range.cc:3456