MySQL  8.0.27
Source Code Documentation
range_optimizer.h
Go to the documentation of this file.
1 /* Copyright (c) 2000, 2021, Oracle and/or its affiliates.
2 
3  This program is free software; you can redistribute it and/or modify
4  it under the terms of the GNU General Public License, version 2.0,
5  as published by the Free Software Foundation.
6 
7  This program is also distributed with certain software (including
8  but not limited to OpenSSL) that is licensed under separate terms,
9  as designated in a particular file or component or in included license
10  documentation. The authors of MySQL hereby grant you an additional
11  permission to link the program and your derivative works with the
12  separately licensed software that they have included with MySQL.
13 
14  This program is distributed in the hope that it will be useful,
15  but WITHOUT ANY WARRANTY; without even the implied warranty of
16  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  GNU General Public License, version 2.0, for more details.
18 
19  You should have received a copy of the GNU General Public License
20  along with this program; if not, write to the Free Software
21  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
22 
23 /* classes to use when handling where clause */
24 
25 #ifndef SQL_RANGE_OPTIMIZER_RANGE_OPTIMIZER_H_
26 #define SQL_RANGE_OPTIMIZER_RANGE_OPTIMIZER_H_
27 
28 #include <assert.h>
29 #include <sys/types.h>
30 #include <algorithm>
31 
32 #include "my_base.h"
33 #include "my_inttypes.h"
34 #include "my_table_map.h"
35 #include "prealloced_array.h" // Prealloced_array
36 #include "sql/field.h" // Field
37 #include "sql/handler.h"
38 #include "sql/item_func.h"
39 #include "sql/key_spec.h"
40 #include "sql/malloc_allocator.h" // IWYU pragma: keep
41 #include "sql/sql_bitmap.h"
42 #include "sql/sql_const.h"
43 #include "sql_string.h"
44 
45 class Item;
46 class Opt_trace_context;
47 class Query_block;
48 class THD;
49 struct MY_BITMAP;
50 struct TABLE;
51 
52 struct KEY_PART {
54  /* See KEY_PART_INFO for meaning of the next two: */
57  /*
58  Keypart flags (0 when this structure is used by partition pruning code
59  for fake partitioning index description)
60  */
64 };
65 
66 class QUICK_RANGE {
67  public:
70 
71  /// Stores bitwise-or'ed bits defined in enum key_range_flags.
73 
74  /**
75  Stores one of the HA_READ_MBR_XXX items in enum ha_rkey_function, only
76  effective when flag has a GEOM_FLAG bit.
77  */
79  key_part_map min_keypart_map, // bitmap of used keyparts in min_key
80  max_keypart_map; // bitmap of used keyparts in max_key
81 
82  QUICK_RANGE(); /* Full range */
83  QUICK_RANGE(const uchar *min_key_arg, uint min_length_arg,
84  key_part_map min_keypart_map_arg, const uchar *max_key_arg,
85  uint max_length_arg, key_part_map max_keypart_map_arg,
86  uint flag_arg, enum ha_rkey_function rkey_func);
87 
88  /**
89  Initalizes a key_range object for communication with storage engine.
90 
91  This function facilitates communication with the Storage Engine API by
92  translating the minimum endpoint of the interval represented by this
93  QUICK_RANGE into an index range endpoint specifier for the engine.
94 
95  @param kr Pointer to an uninitialized key_range C struct.
96 
97  @param prefix_length The length of the search key prefix to be used for
98  lookup.
99 
100  @param keypart_map A set (bitmap) of keyparts to be used.
101  */
102  void make_min_endpoint(key_range *kr, uint prefix_length,
103  key_part_map keypart_map) {
104  make_min_endpoint(kr);
105  kr->length = std::min(kr->length, prefix_length);
106  kr->keypart_map &= keypart_map;
107  }
108 
109  /**
110  Initalizes a key_range object for communication with storage engine.
111 
112  This function facilitates communication with the Storage Engine API by
113  translating the minimum endpoint of the interval represented by this
114  QUICK_RANGE into an index range endpoint specifier for the engine.
115 
116  @param kr Pointer to an uninitialized key_range C struct.
117  */
119  kr->key = (const uchar *)min_key;
120  kr->length = min_length;
122  kr->flag = ((flag & NEAR_MIN) ? HA_READ_AFTER_KEY
125  }
126 
127  /**
128  Initalizes a key_range object for communication with storage engine.
129 
130  This function facilitates communication with the Storage Engine API by
131  translating the maximum endpoint of the interval represented by this
132  QUICK_RANGE into an index range endpoint specifier for the engine.
133 
134  @param kr Pointer to an uninitialized key_range C struct.
135 
136  @param prefix_length The length of the search key prefix to be used for
137  lookup.
138 
139  @param keypart_map A set (bitmap) of keyparts to be used.
140  */
141  void make_max_endpoint(key_range *kr, uint prefix_length,
142  key_part_map keypart_map) {
143  make_max_endpoint(kr);
144  kr->length = std::min(kr->length, prefix_length);
145  kr->keypart_map &= keypart_map;
146  }
147 
148  /**
149  Initalizes a key_range object for communication with storage engine.
150 
151  This function facilitates communication with the Storage Engine API by
152  translating the maximum endpoint of the interval represented by this
153  QUICK_RANGE into an index range endpoint specifier for the engine.
154 
155  @param kr Pointer to an uninitialized key_range C struct.
156  */
158  kr->key = (const uchar *)max_key;
159  kr->length = max_length;
161  /*
162  We use READ_AFTER_KEY here because if we are reading on a key
163  prefix we want to find all keys with this prefix
164  */
166  }
167 };
168 
177 };
178 
179 /*
180  Quick select interface.
181  This class is a parent for all QUICK_*_SELECT classes.
182 
183  The usage scenario is as follows:
184  1. Create quick select
185  quick = new (mem_root) QUICK_XXX_SELECT(...);
186 
187  2. Perform lightweight initialization. This can be done in 2 ways:
188  2.a: Regular initialization
189  if (quick->init())
190  {
191  //the only valid action after failed init() call is destroy
192  destroy(quick);
193  }
194  2.b: Special initialization for quick selects merged by QUICK_ROR_*_SELECT
195  if (quick->init_ror_merged_scan())
196  destroy(quick);
197 
198  3. Perform zero, one, or more scans.
199  while (...)
200  {
201  // initialize quick select for scan. This may allocate
202  // buffers and/or prefetch rows.
203  if (quick->reset())
204  {
205  //the only valid action after failed reset() call is destroy
206  destroy(quick);
207  //abort query
208  }
209 
210  // perform the scan
211  do
212  {
213  res= quick->get_next();
214  } while (res && ...)
215  }
216 
217  4. Destroy the select:
218  destroy(quick);
219 */
220 
222  public:
223  ha_rows records; /* estimate of # of records to be retrieved */
224  Cost_estimate cost_est; ///> cost to perform this retrieval
226  /*
227  Index this quick select uses, or MAX_KEY for quick selects
228  that use several indexes
229  */
231 
232  /*
233  Total length of first used_key_parts parts of the key.
234  Applicable if index!= MAX_KEY.
235  */
237 
238  /*
239  Max. number of (first) key parts this quick select uses for retrieval.
240  eg. for "(key1p1=c1 AND key1p2=c2) OR key1p1=c2" used_key_parts == 2.
241  Applicable if index!= MAX_KEY.
242 
243  For QUICK_GROUP_MIN_MAX_SELECT it includes MIN/MAX argument keyparts.
244  */
246  /**
247  true if creation of the object is forced by the hint.
248  The flag is used to skip ref evaluation in find_best_ref() function.
249  It also enables using of QUICK_SELECT object in
250  Optimize_table_order::best_access_path() regardless of the evaluation cost.
251  */
253 
254  QUICK_SELECT_I();
255  QUICK_SELECT_I(const QUICK_SELECT_I &) = default;
256  virtual ~QUICK_SELECT_I() = default;
257 
258  /*
259  Do post-constructor initialization.
260  SYNOPSIS
261  init()
262 
263  init() performs initializations that should have been in constructor if
264  it was possible to return errors from constructors. The join optimizer may
265  create and then destroy quick selects without retrieving any rows so init()
266  must not contain any IO or CPU intensive code.
267 
268  If init() call fails the only valid action is to destroy this quick select,
269  reset() and get_next() must not be called.
270 
271  RETURN
272  0 OK
273  other Error code
274  */
275  virtual int init() = 0;
276 
277  /*
278  Initialize quick select for row retrieval.
279  SYNOPSIS
280  reset()
281 
282  reset() should be called when it is certain that row retrieval will be
283  necessary. This call may do heavyweight initialization like buffering first
284  N records etc. If reset() call fails get_next() must not be called.
285  Note that reset() may be called several times if
286  * the quick select is executed in a subselect
287  * a JOIN buffer is used
288 
289  RETURN
290  0 OK
291  other Error code
292  */
293  virtual int reset(void) = 0;
294 
295  virtual int get_next() = 0; /* get next record to retrieve */
296 
297  /* Range end should be called when we have looped over the whole index */
298  virtual void range_end() {}
299 
300  /**
301  Whether the range access method returns records in reverse order.
302  */
303  virtual bool reverse_sorted() const = 0;
304  /**
305  Whether the range access method is capable of returning records
306  in reverse order.
307  */
308  virtual bool reverse_sort_possible() const = 0;
309  virtual bool unique_key_range() { return false; }
310 
311  /*
312  Request that this quick select produces sorted output.
313  Not all quick selects can provide sorted output, the caller is responsible
314  for calling this function only for those quick selects that can.
315  The implementation is also allowed to provide sorted output even if it
316  was not requested if benificial, or required by implementation
317  internals.
318  */
319  virtual void need_sorted_output() = 0;
320 
321  /* Get type of this quick select */
322  virtual RangeScanType get_type() const = 0;
323  virtual bool is_loose_index_scan() const = 0;
324  virtual bool is_agg_loose_index_scan() const = 0;
325 
326  /*
327  Initialize this quick select as a merged scan inside a ROR-union or a ROR-
328  intersection scan. The caller must not additionally call init() if this
329  function is called.
330  SYNOPSIS
331  init_ror_merged_scan()
332  reuse_handler If true, the quick select may use table->handler,
333  otherwise it must create and use a separate handler
334  object.
335  RETURN
336  0 Ok
337  other Error
338  */
339  virtual int init_ror_merged_scan(bool reuse_handler [[maybe_unused]]) {
340  assert(0);
341  return 1;
342  }
343 
344  /*
345  Save ROWID of last retrieved row in file->ref. This used in ROR-merging.
346  */
347  virtual void save_last_pos() {}
348 
349  /*
350  Append comma-separated list of keys this quick select uses to key_names;
351  append comma-separated list of corresponding used lengths to used_lengths.
352  This is used by select_describe.
353  */
354  virtual void add_keys_and_lengths(String *key_names,
355  String *used_lengths) = 0;
356 
357  /*
358  Append text representation of quick select structure (what and how is
359  merged) to str. The result is added to "Extra" field in EXPLAIN output.
360  This function is implemented only by quick selects that merge other quick
361  selects output and/or can produce output suitable for merging.
362  */
363  virtual void add_info_string(String *str [[maybe_unused]]) {}
364  /*
365  Return 1 if any index used by this quick select
366  uses field which is marked in passed bitmap.
367  */
368  virtual bool is_keys_used(const MY_BITMAP *fields);
369 
370  /*
371  rowid of last row retrieved by this quick select. This is used only when
372  doing ROR-index_merge selects
373  */
375 
376  /*
377  Table record buffer used by this quick select.
378  */
380 #ifndef NDEBUG
381  /*
382  Print quick select information to DBUG_FILE. Caller is responsible
383  for locking DBUG_FILE before this call and unlocking it afterwards.
384  */
385  virtual void dbug_dump(int indent, bool verbose) = 0;
386 #endif
387 
388  /*
389  Returns a QUICK_SELECT with reverse order of to the index.
390  */
391  virtual QUICK_SELECT_I *make_reverse(uint used_key_parts_arg
392  [[maybe_unused]]) {
393  return nullptr;
394  }
395  virtual void set_handler(handler *file_arg [[maybe_unused]]) {}
396 
397  /**
398  Get the fields used by the range access method.
399 
400  @param[out] used_fields Bitmap of fields that this range access
401  method uses.
402  */
403  virtual void get_fields_used(MY_BITMAP *used_fields) = 0;
405 };
406 
409 
410 int test_quick_select(THD *thd, MEM_ROOT *return_mem_root,
411  MEM_ROOT *temp_mem_root, Key_map keys_to_use,
412  table_map prev_tables, table_map read_tables,
413  ha_rows limit, bool force_quick_range,
414  const enum_order interesting_order, TABLE *table,
415  bool skip_records_in_range, Item *cond,
416  Key_map *needed_reg, QUICK_SELECT_I **quick,
417  bool ignore_table_scan, Query_block *query_block);
418 
419 void store_key_image_to_rec(Field *field, uchar *ptr, uint len);
420 
421 extern String null_string;
422 
423 /// Global initialization of the null_element. Call on server start.
424 void range_optimizer_init();
425 
426 /// Global destruction of the null_element. Call on server stop.
427 void range_optimizer_free();
428 
429 /**
430  Test if 'value' is comparable to 'field' when setting up range
431  access for predicate "field OP value". 'field' is a field in the
432  table being optimized for while 'value' is whatever 'field' is
433  compared to.
434 
435  @param cond_func the predicate item that compares 'field' with 'value'
436  @param field field in the predicate
437  @param itype itMBR if indexed field is spatial, itRAW otherwise
438  @param comp_type comparator for the predicate
439  @param value whatever 'field' is compared to
440 
441  @return true if 'field' and 'value' are comparable, false otherwise
442 */
443 
444 bool comparable_in_index(Item *cond_func, const Field *field,
445  const Field::imagetype itype,
446  Item_func::Functype comp_type, const Item *value);
447 
448 #endif // SQL_RANGE_OPTIMIZER_RANGE_OPTIMIZER_H_
Definition: sql_bitmap.h:137
Used to store optimizer cost estimates.
Definition: handler.h:3423
Definition: field.h:590
imagetype
Definition: field.h:743
Functype
Definition: item_func.h:178
Base class that is used to represent any kind of expression in a relational query.
Definition: item.h:802
A per-session context which is always available at any point of execution, because in practice it's a...
Definition: opt_trace_context.h:89
Definition: range_optimizer.h:66
void make_max_endpoint(key_range *kr)
Initalizes a key_range object for communication with storage engine.
Definition: range_optimizer.h:157
uint16 flag
Stores bitwise-or'ed bits defined in enum key_range_flags.
Definition: range_optimizer.h:72
void make_min_endpoint(key_range *kr, uint prefix_length, key_part_map keypart_map)
Initalizes a key_range object for communication with storage engine.
Definition: range_optimizer.h:102
uint16 min_length
Definition: range_optimizer.h:69
uint16 max_length
Definition: range_optimizer.h:69
QUICK_RANGE()
Definition: range_optimizer.cc:310
uchar * min_key
Definition: range_optimizer.h:68
key_part_map min_keypart_map
Definition: range_optimizer.h:79
void make_max_endpoint(key_range *kr, uint prefix_length, key_part_map keypart_map)
Initalizes a key_range object for communication with storage engine.
Definition: range_optimizer.h:141
key_part_map max_keypart_map
Definition: range_optimizer.h:80
uchar * max_key
Definition: range_optimizer.h:68
void make_min_endpoint(key_range *kr)
Initalizes a key_range object for communication with storage engine.
Definition: range_optimizer.h:118
enum ha_rkey_function rkey_func_flag
Stores one of the HA_READ_MBR_XXX items in enum ha_rkey_function, only effective when flag has a GEOM...
Definition: range_optimizer.h:78
Definition: range_optimizer.h:221
virtual bool is_keys_used(const MY_BITMAP *fields)
Definition: range_optimizer.cc:1368
virtual bool is_agg_loose_index_scan() const =0
virtual void need_sorted_output()=0
virtual QUICK_SELECT_I * make_reverse(uint used_key_parts_arg[[maybe_unused]])
Definition: range_optimizer.h:391
void trace_quick_description(Opt_trace_context *trace)
Definition: range_optimizer.cc:301
virtual RangeScanType get_type() const =0
virtual int get_next()=0
uint max_used_key_length
Definition: range_optimizer.h:236
virtual void get_fields_used(MY_BITMAP *used_fields)=0
Get the fields used by the range access method.
virtual bool reverse_sort_possible() const =0
Whether the range access method is capable of returning records in reverse order.
virtual void set_handler(handler *file_arg[[maybe_unused]])
Definition: range_optimizer.h:395
virtual void add_info_string(String *str[[maybe_unused]])
Definition: range_optimizer.h:363
virtual bool reverse_sorted() const =0
Whether the range access method returns records in reverse order.
bool forced_by_hint
true if creation of the object is forced by the hint.
Definition: range_optimizer.h:252
virtual void save_last_pos()
Definition: range_optimizer.h:347
uchar * record
Definition: range_optimizer.h:379
Cost_estimate cost_est
Definition: range_optimizer.h:224
virtual bool unique_key_range()
Definition: range_optimizer.h:309
TABLE * m_table
cost to perform this retrieval
Definition: range_optimizer.h:225
virtual void range_end()
Definition: range_optimizer.h:298
virtual void dbug_dump(int indent, bool verbose)=0
QUICK_SELECT_I(const QUICK_SELECT_I &)=default
virtual bool is_loose_index_scan() const =0
virtual int init()=0
uint index
Definition: range_optimizer.h:230
virtual void add_keys_and_lengths(String *key_names, String *used_lengths)=0
QUICK_SELECT_I()
Definition: range_optimizer.cc:298
virtual ~QUICK_SELECT_I()=default
virtual int init_ror_merged_scan(bool reuse_handler[[maybe_unused]])
Definition: range_optimizer.h:339
uchar * last_rowid
Definition: range_optimizer.h:374
uint used_key_parts
Definition: range_optimizer.h:245
ha_rows records
Definition: range_optimizer.h:223
virtual int reset(void)=0
This class represents a query block, aka a query specification, which is a query consisting of a SELE...
Definition: sql_lex.h:1123
Using this class is fraught with peril, and you need to be very careful when doing so.
Definition: sql_string.h:165
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_class.h:821
The handler class is the interface for dynamically loadable storage engines.
Definition: handler.h:4131
enum_order
Definition: key_spec.h:64
This file includes constants used by all storage engines.
ha_rkey_function
Definition: my_base.h:77
@ HA_READ_KEY_EXACT
Definition: my_base.h:78
@ HA_READ_AFTER_KEY
Definition: my_base.h:81
@ HA_READ_BEFORE_KEY
Definition: my_base.h:82
@ HA_READ_KEY_OR_NEXT
Definition: my_base.h:79
@ NEAR_MIN
Definition: my_base.h:1081
@ EQ_RANGE
Definition: my_base.h:1095
@ NEAR_MAX
Definition: my_base.h:1083
ulong key_part_map
Definition: my_base.h:1006
my_off_t ha_rows
Definition: my_base.h:1138
Some integer typedefs for easier portability.
uint8_t uint8
Definition: my_inttypes.h:62
unsigned char uchar
Definition: my_inttypes.h:51
uint16_t uint16
Definition: my_inttypes.h:64
uint64_t table_map
Definition: my_table_map.h:29
static bool quick
Definition: mysql.cc:154
static uint verbose
Definition: mysqlcheck.cc:64
std::string str(const mysqlrouter::ConfigGenerator::Options::Endpoint &ep)
Definition: config_generator.cc:1056
const string value("\"Value\"")
RangeScanType
Definition: range_optimizer.h:169
@ QS_TYPE_RANGE_DESC
Definition: range_optimizer.h:171
@ QS_TYPE_INDEX_MERGE
Definition: range_optimizer.h:172
@ QS_TYPE_ROR_UNION
Definition: range_optimizer.h:174
@ QS_TYPE_ROR_INTERSECT
Definition: range_optimizer.h:173
@ QS_TYPE_RANGE
Definition: range_optimizer.h:170
@ QS_TYPE_GROUP_MIN_MAX
Definition: range_optimizer.h:175
@ QS_TYPE_SKIP_SCAN
Definition: range_optimizer.h:176
int test_quick_select(THD *thd, MEM_ROOT *return_mem_root, MEM_ROOT *temp_mem_root, Key_map keys_to_use, table_map prev_tables, table_map read_tables, ha_rows limit, bool force_quick_range, const enum_order interesting_order, TABLE *table, bool skip_records_in_range, Item *cond, Key_map *needed_reg, QUICK_SELECT_I **quick, bool ignore_table_scan, Query_block *query_block)
Definition: range_optimizer.cc:474
String null_string
void store_key_image_to_rec(Field *field, uchar *ptr, uint len)
Definition: partition_pruning.cc:448
bool comparable_in_index(Item *cond_func, const Field *field, const Field::imagetype itype, Item_func::Functype comp_type, const Item *value)
Test if 'value' is comparable to 'field' when setting up range access for predicate "field OP value".
Definition: range_optimizer.cc:1251
void range_optimizer_free()
Global destruction of the null_element. Call on server stop.
Definition: range_optimizer.cc:168
void range_optimizer_init()
Global initialization of the null_element. Call on server start.
Definition: range_optimizer.cc:162
File containing constants that can be used throughout the server.
Our own string classes, used pervasively throughout the executor.
Definition: range_optimizer.h:52
Field::imagetype image_type
Definition: range_optimizer.h:63
uint16 store_length
Definition: range_optimizer.h:55
uint16 flag
Definition: range_optimizer.h:61
uint8 null_bit
Definition: range_optimizer.h:56
Field * field
Definition: range_optimizer.h:62
uint16 part
Definition: range_optimizer.h:53
uint16 key
Definition: range_optimizer.h:53
uint16 length
Definition: range_optimizer.h:55
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:78
Definition: my_bitmap.h:41
Definition: table.h:1394
Definition: my_base.h:1122
uint length
Definition: my_base.h:1124
enum ha_rkey_function flag
Definition: my_base.h:1126
key_part_map keypart_map
Definition: my_base.h:1125
const uchar * key
Definition: my_base.h:1123
unsigned int uint
Definition: uca-dump.cc:29