Drizzled Public API Documentation

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