1 #ifndef SQL_SELECT_INCLUDED
2 #define SQL_SELECT_INCLUDED
3
4 /* Copyright (c) 2000, 2019, Oracle and/or its affiliates. All rights reserved.
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, version 2.0,
8 as published by the Free Software Foundation.
9
10 This program is also distributed with certain software (including
11 but not limited to OpenSSL) that is licensed under separate terms,
12 as designated in a particular file or component or in included license
13 documentation. The authors of MySQL hereby grant you an additional
14 permission to link the program and your derivative works with the
15 separately licensed software that they have included with MySQL.
16
17 This program is distributed in the hope that it will be useful,
18 but WITHOUT ANY WARRANTY; without even the implied warranty of
19 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 GNU General Public License, version 2.0, for more details.
21
22 You should have received a copy of the GNU General Public License
23 along with this program; if not, write to the Free Software
24 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
25
26 /**
27 @file sql/sql_select.h
28 */
29
30 #include <limits.h>
31 #include <stddef.h>
32 #include <sys/types.h>
33
34 #include "my_base.h"
35 #include "my_dbug.h"
36 #include "my_inttypes.h"
37 #include "my_sqlcommand.h"
38 #include "my_table_map.h"
39 #include "sql/item_cmpfunc.h" // Item_cond_and
40 #include "sql/opt_costmodel.h"
41 #include "sql/sql_bitmap.h"
42 #include "sql/sql_cmd_dml.h" // Sql_cmd_dml
43 #include "sql/sql_const.h"
44 #include "sql/sql_opt_exec_shared.h" // join_type
45
46 class Field;
47 class Item;
48 class Item_func;
49 class JOIN_TAB;
50 class KEY;
51 class QEP_TAB;
52 class Query_result;
53 class SELECT_LEX;
54 class Select_lex_visitor;
55 class SJ_TMP_TABLE;
56 class Temp_table_param;
57 class THD;
58 template <class T>
59 class List;
60 struct LEX;
61 struct MYSQL_LEX_CSTRING;
62 struct ORDER;
63 struct SJ_TMP_TABLE_TAB;
64 struct TABLE;
65 struct TABLE_LIST;
66
67 typedef ulonglong nested_join_map;
68
69 class Sql_cmd_select : public Sql_cmd_dml {
70 public:
Sql_cmd_select(Query_result * result_arg)71 explicit Sql_cmd_select(Query_result *result_arg) : Sql_cmd_dml() {
72 result = result_arg;
73 }
74
sql_command_code()75 enum_sql_command sql_command_code() const override { return SQLCOM_SELECT; }
76
is_data_change_stmt()77 bool is_data_change_stmt() const override { return false; }
78
79 bool accept(THD *thd, Select_lex_visitor *visitor) override;
80
81 const MYSQL_LEX_CSTRING *eligible_secondary_storage_engine() const override;
82
83 protected:
84 bool precheck(THD *thd) override;
85
86 bool prepare_inner(THD *thd) override;
87 };
88
89 /**
90 Returns a constant of type 'type' with the 'A' lowest-weight bits set.
91 Example: LOWER_BITS(uint, 3) == 7.
92 Requirement: A < sizeof(type) * 8.
93 */
94 #define LOWER_BITS(type, A) ((type)(((type)1 << (A)) - 1))
95
96 /* Values in optimize */
97 #define KEY_OPTIMIZE_EXISTS 1
98 #define KEY_OPTIMIZE_REF_OR_NULL 2
99 #define FT_KEYPART (MAX_REF_PARTS + 10)
100
101 /**
102 A Key_use represents an equality predicate of the form (table.column = val),
103 where the column is indexed by @c keypart in @c key and @c val is either a
104 constant, a column from other table, or an expression over column(s) from
105 other table(s). If @c val is not a constant, then the Key_use specifies an
106 equi-join predicate, and @c table must be put in the join plan after all
107 tables in @c used_tables.
108
109 At an abstract level a Key_use instance can be viewed as a directed arc
110 of an equi-join graph, where the arc originates from the table(s)
111 containing the column(s) that produce the values used for index lookup
112 into @c table, and the arc points into @c table.
113
114 For instance, assuming there is only an index t3(c), the query
115
116 @code
117 SELECT * FROM t1, t2, t3
118 WHERE t1.a = t3.c AND
119 t2.b = t3.c;
120 @endcode
121
122 would generate two arcs (instances of Key_use)
123
124 @code
125 t1-- a ->- c --.
126 |
127 V
128 t3
129 ^
130 |
131 t2-- b ->- c --'
132 @endcode
133
134 If there were indexes t1(a), and t2(b), then the equi-join graph
135 would have two additional arcs "c->a" and "c->b" recording the fact
136 that it is possible to perform lookup in either direction.
137
138 @code
139 t1-- a ->- c --. ,-- c -<- b --- t2
140 ^ | | ^
141 | | | |
142 `-- a -<- c - v v-- c ->- b ----'
143 t3
144 @endcode
145
146 The query
147
148 @code
149 SELECT * FROM t1, t2, t3 WHERE t1.a + t2.b = t3.c;
150 @endcode
151
152 can be viewed as a graph with one "multi-source" arc:
153
154 @code
155 t1-- a ---
156 |
157 >-- c --> t3
158 |
159 t2-- b ---
160 @endcode
161
162 The graph of all equi-join conditions usable for index lookup is
163 stored as an ordered sequence of Key_use elements in
164 JOIN::keyuse_array. See sort_keyuse() for details on the
165 ordering. Each JOIN_TAB::keyuse points to the first array element
166 with the same table.
167 */
168 class Key_use {
169 public:
170 // We need the default constructor for unit testing.
Key_use()171 Key_use()
172 : table_ref(nullptr),
173 val(nullptr),
174 used_tables(0),
175 key(0),
176 keypart(0),
177 optimize(0),
178 keypart_map(0),
179 ref_table_rows(0),
180 null_rejecting(false),
181 cond_guard(nullptr),
182 sj_pred_no(UINT_MAX),
183 bound_keyparts(0),
184 fanout(0.0),
185 read_cost(0.0) {}
186
Key_use(TABLE_LIST * table_ref_arg,Item * val_arg,table_map used_tables_arg,uint key_arg,uint keypart_arg,uint optimize_arg,key_part_map keypart_map_arg,ha_rows ref_table_rows_arg,bool null_rejecting_arg,bool * cond_guard_arg,uint sj_pred_no_arg)187 Key_use(TABLE_LIST *table_ref_arg, Item *val_arg, table_map used_tables_arg,
188 uint key_arg, uint keypart_arg, uint optimize_arg,
189 key_part_map keypart_map_arg, ha_rows ref_table_rows_arg,
190 bool null_rejecting_arg, bool *cond_guard_arg, uint sj_pred_no_arg)
191 : table_ref(table_ref_arg),
192 val(val_arg),
193 used_tables(used_tables_arg),
194 key(key_arg),
195 keypart(keypart_arg),
196 optimize(optimize_arg),
197 keypart_map(keypart_map_arg),
198 ref_table_rows(ref_table_rows_arg),
199 null_rejecting(null_rejecting_arg),
200 cond_guard(cond_guard_arg),
201 sj_pred_no(sj_pred_no_arg),
202 bound_keyparts(0),
203 fanout(0.0),
204 read_cost(0.0) {}
205
206 TABLE_LIST *table_ref; ///< table owning the index
207
208 /**
209 Value used for lookup into @c key. It may be an Item_field, a
210 constant or any other expression. If @c val contains a field from
211 another table, then we have a join condition, and the table(s) of
212 the field(s) in @c val should be before @c table in the join plan.
213 */
214 Item *val;
215
216 /**
217 All tables used in @c val, that is all tables that provide bindings
218 for the expression @c val. These tables must be in the plan before
219 executing the equi-join described by a Key_use.
220 */
221 table_map used_tables;
222 uint key; ///< number of index
223 uint keypart; ///< used part of the index
224 uint optimize; ///< 0, or KEY_OPTIMIZE_*
225 key_part_map keypart_map; ///< like keypart, but as a bitmap
226 ha_rows ref_table_rows; ///< Estimate of how many rows for a key value
227 /**
228 If true, the comparison this value was created from will not be
229 satisfied if val has NULL 'value'.
230 Not used if the index is fulltext (such index cannot be used for
231 equalities).
232 */
233 bool null_rejecting;
234 /**
235 !NULL - This Key_use was created from an equality that was wrapped into
236 an Item_func_trig_cond. This means the equality (and validity of
237 this Key_use element) can be turned on and off. The on/off state
238 is indicted by the pointed value:
239 *cond_guard == true @<=@> equality condition is on
240 *cond_guard == false @<=@> equality condition is off
241
242 NULL - Otherwise (the source equality can't be turned off)
243
244 Not used if the index is fulltext (such index cannot be used for
245 equalities).
246 */
247 bool *cond_guard;
248 /**
249 0..63 @<=@> This was created from semi-join IN-equality # sj_pred_no.
250 UINT_MAX Otherwise
251
252 Not used if the index is fulltext (such index cannot be used for
253 semijoin).
254
255 @see get_semi_join_select_list_index()
256 */
257 uint sj_pred_no;
258
259 /*
260 The three members below are different from the rest of Key_use: they are
261 set only by Optimize_table_order, and they change with the currently
262 considered join prefix.
263 */
264
265 /**
266 The key columns which are equal to expressions depending only of earlier
267 tables of the current join prefix.
268 This information is stored only in the first Key_use of the index.
269 */
270 key_part_map bound_keyparts;
271
272 /**
273 Fanout of the ref access path for this index, in the current join
274 prefix.
275 This information is stored only in the first Key_use of the index.
276 */
277 double fanout;
278
279 /**
280 Cost of the ref access path for the current join prefix, i.e. the
281 cost of using ref access once multiplied by estimated number of
282 partial rows from tables earlier in the join sequence.
283 read_cost does NOT include cost of processing rows on the
284 server side (row_evaluate_cost).
285
286 Example: If the cost of ref access on this index is 5, and the
287 estimated number of partial rows from earlier tables is 10,
288 read_cost=50.
289
290 This information is stored only in the first Key_use of the index.
291 */
292 double read_cost;
293 };
294
295 /// @returns join type according to quick select type used
296 join_type calc_join_type(int quick_type);
297
298 class JOIN;
299
300 #define SJ_OPT_NONE 0
301 #define SJ_OPT_DUPS_WEEDOUT 1
302 #define SJ_OPT_LOOSE_SCAN 2
303 #define SJ_OPT_FIRST_MATCH 3
304 #define SJ_OPT_MATERIALIZE_LOOKUP 4
305 #define SJ_OPT_MATERIALIZE_SCAN 5
306
sj_is_materialize_strategy(uint strategy)307 inline bool sj_is_materialize_strategy(uint strategy) {
308 return strategy >= SJ_OPT_MATERIALIZE_LOOKUP;
309 }
310
311 /**
312 Bits describing quick select type
313 */
314 enum quick_type { QS_NONE, QS_RANGE, QS_DYNAMIC_RANGE };
315
316 /**
317 A position of table within a join order. This structure is primarily used
318 as a part of @c join->positions and @c join->best_positions arrays.
319
320 One POSITION element contains information about:
321 - Which table is accessed
322 - Which access method was chosen
323 = Its cost and \#of output records
324 - Semi-join strategy choice. Note that there are two different
325 representation formats:
326 1. The one used during join optimization
327 2. The one used at plan refinement/code generation stage.
328 We call fix_semijoin_strategies_for_picked_join_order() to switch
329 between #1 and #2. See that function's comment for more details.
330
331 - Semi-join optimization state. When we're running join optimization,
332 we main a state for every semi-join strategy which are various
333 variables that tell us if/at which point we could consider applying the
334 strategy.
335 The variables are really a function of join prefix but they are too
336 expensive to re-caclulate for every join prefix we consider, so we
337 maintain current state in join->positions[\#tables_in_prefix]. See
338 advance_sj_state() for details.
339
340 This class has to stay a POD, because it is memcpy'd in many places.
341 */
342
343 struct POSITION {
344 /**
345 The number of rows that will be fetched by the chosen access
346 method per each row combination of previous tables. That is:
347
348 rows_fetched = selectivity(access_condition) * cardinality(table)
349
350 where 'access_condition' is whatever condition was chosen for
351 index access, depending on the access method ('ref', 'range',
352 etc.)
353
354 @note For index/table scans, rows_fetched may be less than
355 the number of rows in the table because the cost of evaluating
356 constant conditions is included in the scan cost, and the number
357 of rows produced by these scans is the estimated number of rows
358 that pass the constant conditions. @see
359 Optimize_table_order::calculate_scan_cost() . But this is only during
360 planning; make_join_readinfo() simplifies it for EXPLAIN.
361 */
362 double rows_fetched;
363
364 /**
365 Cost of accessing the table in course of the entire complete join
366 execution, i.e. cost of one access method use (e.g. 'range' or
367 'ref' scan ) multiplied by estimated number of rows from tables
368 earlier in the join sequence.
369
370 read_cost does NOT include cost of processing rows within the
371 executor (row_evaluate_cost).
372 */
373 double read_cost;
374
375 /**
376 The fraction of the 'rows_fetched' rows that will pass the table
377 conditions that were NOT used by the access method. If, e.g.,
378
379 "SELECT ... WHERE t1.colx = 4 and t1.coly @> 5"
380
381 is resolved by ref access on t1.colx, filter_effect will be the
382 fraction of rows that will pass the "t1.coly @> 5" predicate. The
383 valid range is 0..1, where 0.0 means that no rows will pass the
384 table conditions and 1.0 means that all rows will pass.
385
386 It is used to calculate how many row combinations will be joined
387 with the next table, @see prefix_rowcount below.
388
389 @note With condition filtering enabled, it is possible to get
390 a fanout = rows_fetched * filter_effect that is less than 1.0.
391 Consider, e.g., a join between t1 and t2:
392
393 "SELECT ... WHERE t1.col1=t2.colx and t2.coly OP @<something@>"
394
395 where t1 is a prefix table and the optimizer currently calculates
396 the cost of adding t2 to the join. Assume that the chosen access
397 method on t2 is a 'ref' access on 'colx' that is estimated to
398 produce 2 rows per row from t1 (i.e., rows_fetched = 2). It will
399 in this case be perfectly fine to calculate a filtering effect
400 @<0.5 (resulting in "rows_fetched * filter_effect @< 1.0") from the
401 predicate "t2.coly OP @<something@>". If so, the number of row
402 combinations from (t1,t2) is lower than the prefix_rowcount of t1.
403
404 The above is just an example of how the fanout of a table can
405 become less than one. It can happen for any access method.
406 */
407 float filter_effect;
408
409 /**
410 prefix_rowcount and prefix_cost form a stack of partial join
411 order costs and output sizes
412
413 prefix_rowcount: The number of row combinations that will be
414 joined to the next table in the join sequence.
415
416 For a joined table it is calculated as
417 prefix_rowcount =
418 last_table.prefix_rowcount * rows_fetched * filter_effect
419
420 @see filter_effect
421
422 For a semijoined table it may be less than this formula due to
423 duplicate elimination.
424 */
425 double prefix_rowcount;
426 double prefix_cost;
427
428 JOIN_TAB *table;
429
430 /**
431 NULL - 'index' or 'range' or 'index_merge' or 'ALL' access is used.
432 Other - [eq_]ref[_or_null] access is used. Pointer to {t.keypart1 = expr}
433 */
434 Key_use *key;
435
436 /** If ref-based access is used: bitmap of tables this table depends on */
437 table_map ref_depend_map;
438 bool use_join_buffer;
439
440 /**
441 Current optimization state: Semi-join strategy to be used for this
442 and preceding join tables.
443
444 Join optimizer sets this for the *last* join_tab in the
445 duplicate-generating range. That is, in order to interpret this field,
446 one needs to traverse join->[best_]positions array from right to left.
447 When you see a join table with sj_strategy!= SJ_OPT_NONE, some other
448 field (depending on the strategy) tells how many preceding positions
449 this applies to. The values of covered_preceding_positions->sj_strategy
450 must be ignored.
451 */
452 uint sj_strategy;
453 /**
454 Valid only after fix_semijoin_strategies_for_picked_join_order() call:
455 if sj_strategy!=SJ_OPT_NONE, this is the number of subsequent tables that
456 are covered by the specified semi-join strategy
457 */
458 uint n_sj_tables;
459
460 /**
461 Bitmap of semi-join inner tables that are in the join prefix and for
462 which there's no provision yet for how to eliminate semi-join duplicates
463 which they produce.
464 */
465 table_map dups_producing_tables;
466
467 /* LooseScan strategy members */
468
469 /* The first (i.e. driving) table we're doing loose scan for */
470 uint first_loosescan_table;
471 /*
472 Tables that need to be in the prefix before we can calculate the cost
473 of using LooseScan strategy.
474 */
475 table_map loosescan_need_tables;
476
477 /*
478 keyno - Planning to do LooseScan on this key. If keyuse is NULL then
479 this is a full index scan, otherwise this is a ref+loosescan
480 scan (and keyno matches the KEUSE's)
481 MAX_KEY - Not doing a LooseScan
482 */
483 uint loosescan_key; // final (one for strategy instance )
484 uint loosescan_parts; /* Number of keyparts to be kept distinct */
485
486 /* FirstMatch strategy */
487 /*
488 Index of the first inner table that we intend to handle with this
489 strategy
490 */
491 uint first_firstmatch_table;
492 /**
493 Value of Optimize_table_order::cur_embedding_map after this table has
494 been added to the plan. Used to constrain FirstMatch table orders.
495 */
496 nested_join_map cur_embedding_map;
497 /*
498 Tables that were not in the join prefix when we've started considering
499 FirstMatch strategy.
500 */
501 table_map first_firstmatch_rtbl;
502 /*
503 Tables that need to be in the prefix before we can calculate the cost
504 of using FirstMatch strategy.
505 */
506 table_map firstmatch_need_tables;
507
508 /* Duplicate Weedout strategy */
509 /* The first table that the strategy will need to handle */
510 uint first_dupsweedout_table;
511 /*
512 Tables that we will need to have in the prefix to do the weedout step
513 (all inner and all outer that the involved semi-joins are correlated with)
514 */
515 table_map dupsweedout_tables;
516
517 /* SJ-Materialization-Scan strategy */
518 /* The last inner table (valid once we're after it) */
519 uint sjm_scan_last_inner;
520 /*
521 Tables that we need to have in the prefix to calculate the correct cost.
522 Basically, we need all inner tables and outer tables mentioned in the
523 semi-join's ON expression so we can correctly account for fanout.
524 */
525 table_map sjm_scan_need_tables;
526
527 /**
528 Even if the query has no semijoin, two sj-related members are read and
529 must thus have been set, by this function.
530 */
no_semijoinPOSITION531 void no_semijoin() {
532 sj_strategy = SJ_OPT_NONE;
533 dups_producing_tables = 0;
534 }
535 /**
536 Set complete estimated cost and produced rowcount for the prefix of tables
537 up to and including this table, in the join plan.
538
539 @param cost Estimated cost
540 @param rowcount Estimated row count
541 */
set_prefix_costPOSITION542 void set_prefix_cost(double cost, double rowcount) {
543 prefix_cost = cost;
544 prefix_rowcount = rowcount;
545 }
546 /**
547 Set complete estimated cost and produced rowcount for the prefix of tables
548 up to and including this table, calculated from the cost of the previous
549 stage, the fanout of the current stage and the cost to process a row at
550 the current stage.
551
552 @param idx Index of position object within array, if zero there is no
553 "previous" stage that can be added.
554 @param cm Cost model that provides the actual calculation
555 */
set_prefix_join_costPOSITION556 void set_prefix_join_cost(uint idx, const Cost_model_server *cm) {
557 if (idx == 0) {
558 prefix_rowcount = rows_fetched;
559 prefix_cost = read_cost + cm->row_evaluate_cost(prefix_rowcount);
560 } else {
561 prefix_rowcount = (this - 1)->prefix_rowcount * rows_fetched;
562 prefix_cost = (this - 1)->prefix_cost + read_cost +
563 cm->row_evaluate_cost(prefix_rowcount);
564 }
565 prefix_rowcount *= filter_effect;
566 }
567 };
568
569 /**
570 Query optimization plan node.
571
572 Specifies:
573
574 - a table access operation on the table specified by this node, and
575
576 - a join between the result of the set of previous plan nodes and
577 this plan node.
578 */
579 class JOIN_TAB : public QEP_shared_owner {
580 public:
581 JOIN_TAB();
582
583 void set_table(TABLE *t);
584
585 /// Sets the pointer to the join condition of TABLE_LIST
586 void init_join_cond_ref(TABLE_LIST *tl);
587
588 /// @returns join condition
join_cond()589 Item *join_cond() const { return *m_join_cond_ref; }
590
591 /**
592 Sets join condition
593 @note this also changes TABLE_LIST::m_join_cond.
594 */
set_join_cond(Item * cond)595 void set_join_cond(Item *cond) { *m_join_cond_ref = cond; }
596
597 /// Set the combined condition for a table (may be performed several times)
set_condition(Item * to)598 void set_condition(Item *to) {
599 if (condition() != to) {
600 m_qs->set_condition(to);
601 // Condition changes, so some indexes may become usable or not:
602 quick_order_tested.clear_all();
603 }
604 }
605
use_join_cache()606 uint use_join_cache() const { return m_use_join_cache; }
set_use_join_cache(uint u)607 void set_use_join_cache(uint u) { m_use_join_cache = u; }
keyuse()608 Key_use *keyuse() const { return m_keyuse; }
set_keyuse(Key_use * k)609 void set_keyuse(Key_use *k) { m_keyuse = k; }
610
611 TABLE_LIST *table_ref; /**< points to table reference */
612
613 private:
614 Key_use *m_keyuse; /**< pointer to first used key */
615
616 /**
617 Pointer to the associated join condition:
618
619 - if this is a table with position==NULL (e.g. internal sort/group
620 temporary table), pointer is NULL
621
622 - otherwise, pointer is the address of some TABLE_LIST::m_join_cond.
623 Thus, the pointee is the same as TABLE_LIST::m_join_cond (changing one
624 changes the other; thus, optimizations made on the second are reflected
625 in SELECT_LEX::print_table_array() which uses the first one).
626 */
627 Item **m_join_cond_ref;
628
629 public:
630 COND_EQUAL *cond_equal; /**< multiple equalities for the on expression*/
631
632 /**
633 The maximum value for the cost of seek operations for key lookup
634 during ref access. The cost model for ref access assumes every key
635 lookup will cause reading a block from disk. With many key lookups
636 into the same table, most of the blocks will soon be in a memory
637 buffer. As a consequence, there will in most cases be an upper
638 limit on the number of actual disk accesses the ref access will
639 cause. This variable is used for storing a maximum cost estimate
640 for the disk accesses for ref access. It is used for limiting the
641 cost estimate for ref access to a more realistic value than
642 assuming every key lookup causes a random disk access. Without
643 having this upper limit for the cost of ref access, table scan
644 would be more likely to be chosen for cases where ref access
645 performs better.
646 */
647 double worst_seeks;
648 /** Keys with constant part. Subset of keys. */
649 Key_map const_keys;
650 Key_map checked_keys; /**< Keys checked */
651 /**
652 Keys which can be used for skip scan access. We store it
653 separately from tab->const_keys & join_tab->keys() to avoid
654 unnecessary printing of the prossible keys in EXPLAIN output
655 as some of these keys can be marked not usable for skip scan later.
656 More strict check for prossible keys is performed in
657 get_best_skip_scan() function.
658 */
659 Key_map skip_scan_keys;
660 Key_map needed_reg;
661
662 /**
663 Used to avoid repeated range analysis for the same key in
664 test_if_skip_sort_order(). This would otherwise happen if the best
665 range access plan found for a key is turned down.
666 quick_order_tested is cleared every time the select condition for
667 this JOIN_TAB changes since a new condition may give another plan
668 and cost from range analysis.
669 */
670 Key_map quick_order_tested;
671
672 /*
673 Number of records that will be scanned (yes scanned, not returned) by the
674 best 'independent' access method, i.e. table scan or QUICK_*_SELECT)
675 */
676 ha_rows found_records;
677 /*
678 Cost of accessing the table using "ALL" or range/index_merge access
679 method (but not 'index' for some reason), i.e. this matches method which
680 E(#records) is in found_records.
681 */
682 double read_time;
683 /**
684 The set of tables that this table depends on. Used for outer join and
685 straight join dependencies.
686 */
687 table_map dependent;
688 /**
689 The set of tables that are referenced by key from this table.
690 */
691 table_map key_dependent;
692
693 public:
694 uint used_fieldlength;
695 enum quick_type use_quick;
696
697 /**
698 Join buffering strategy.
699 After optimization it contains chosen join buffering strategy (if any).
700 */
701 uint m_use_join_cache;
702
703 /* SemiJoinDuplicateElimination variables: */
704 /*
705 Embedding SJ-nest (may be not the direct parent), or NULL if none.
706 It is the closest semijoin or antijoin nest.
707 This variable holds the result of table pullout.
708 */
709 TABLE_LIST *emb_sj_nest;
710
711 /* NestedOuterJoins: Bitmap of nested joins this table is part of */
712 nested_join_map embedding_map;
713
714 /** Flags from SE's MRR implementation, to be used by JOIN_CACHE */
715 uint join_cache_flags;
716
717 /** true <=> AM will scan backward */
718 bool reversed_access;
719
720 /** Clean up associated table after query execution, including resources */
721 void cleanup();
722
723 /// @returns semijoin strategy for this table.
724 uint get_sj_strategy() const;
725
726 private:
727 JOIN_TAB(const JOIN_TAB &); // not defined
728 JOIN_TAB &operator=(const JOIN_TAB &); // not defined
729 };
730
JOIN_TAB()731 inline JOIN_TAB::JOIN_TAB()
732 : QEP_shared_owner(),
733 table_ref(nullptr),
734 m_keyuse(nullptr),
735 m_join_cond_ref(nullptr),
736 cond_equal(nullptr),
737 worst_seeks(0.0),
738 const_keys(),
739 checked_keys(),
740 skip_scan_keys(),
741 needed_reg(),
742 quick_order_tested(),
743 found_records(0),
744 read_time(0),
745 dependent(0),
746 key_dependent(0),
747 used_fieldlength(0),
748 use_quick(QS_NONE),
749 m_use_join_cache(0),
750 emb_sj_nest(nullptr),
751 embedding_map(0),
752 join_cache_flags(0),
753 reversed_access(false) {}
754
755 /* Extern functions in sql_select.cc */
756 void count_field_types(SELECT_LEX *select_lex, Temp_table_param *param,
757 List<Item> &fields, bool reset_with_sum_func,
758 bool save_sum_fields);
759 uint find_shortest_key(TABLE *table, const Key_map *usable_keys);
760
761 /* functions from opt_sum.cc */
762 bool simple_pred(Item_func *func_item, Item **args, bool *inv_order);
763
764 enum aggregate_evaluated {
765 AGGR_COMPLETE, // All aggregates were evaluated
766 AGGR_REGULAR, // Aggregates not fully evaluated, regular execution required
767 AGGR_DELAYED, // Aggregates not fully evaluated, execute with ha_records()
768 AGGR_EMPTY // Source tables empty, aggregates are NULL or 0 (for COUNT)
769 };
770
771 bool optimize_aggregated_query(THD *thd, SELECT_LEX *select,
772 List<Item> &all_fields, Item *conds,
773 aggregate_evaluated *decision);
774
775 /* from sql_delete.cc, used by opt_range.cc */
776 extern "C" int refpos_order_cmp(const void *arg, const void *a, const void *b);
777
778 /// The name of store_key instances that represent constant items.
779 constexpr const char *STORE_KEY_CONST_NAME = "const";
780
781 /** class to copying an field/item to a key struct */
782
783 class store_key {
784 public:
785 bool null_key{false}; /* true <=> the value of the key has a null part */
786 enum store_key_result { STORE_KEY_OK, STORE_KEY_FATAL, STORE_KEY_CONV };
787 store_key(THD *thd, Field *field_arg, uchar *ptr, uchar *null, uint length);
788 virtual ~store_key() = default;
789 virtual const char *name() const = 0;
790
791 /**
792 @brief sets ignore truncation warnings mode and calls the real copy method
793
794 @details this function makes sure truncation warnings when preparing the
795 key buffers don't end up as errors (because of an enclosing INSERT/UPDATE).
796 */
797 store_key_result copy();
798
799 protected:
800 Field *to_field; // Store data here
801
802 virtual enum store_key_result copy_inner() = 0;
803 };
804
805 class store_key_field final : public store_key {
806 Copy_field m_copy_field;
807 const char *m_field_name;
808
809 public:
810 store_key_field(THD *thd, Field *to_field_arg, uchar *ptr,
811 uchar *null_ptr_arg, uint length, Field *from_field,
812 const char *name_arg);
813
name()814 const char *name() const override { return m_field_name; }
815
816 // Change the source field to be another field. Used only by
817 // CreateBKAIterator, when rewriting multi-equalities used in ref access.
818 void replace_from_field(Field *from_field);
819
820 protected:
821 enum store_key_result copy_inner() override;
822 };
823 class store_key_item : public store_key {
824 protected:
825 Item *item;
826
827 public:
828 store_key_item(THD *thd, Field *to_field_arg, uchar *ptr, uchar *null_ptr_arg,
829 uint length, Item *item_arg);
name()830 const char *name() const override { return "func"; }
831
832 protected:
833 enum store_key_result copy_inner() override;
834 };
835
836 /*
837 Class used for unique constraint implementation by subselect_hash_sj_engine.
838 It uses store_key_item implementation to do actual copying, but after
839 that, copy_inner calculates hash of each key part for unique constraint.
840 */
841
842 class store_key_hash_item final : public store_key_item {
843 ulonglong *hash;
844
845 public:
store_key_hash_item(THD * thd,Field * to_field_arg,uchar * ptr,uchar * null_ptr_arg,uint length,Item * item_arg,ulonglong * hash_arg)846 store_key_hash_item(THD *thd, Field *to_field_arg, uchar *ptr,
847 uchar *null_ptr_arg, uint length, Item *item_arg,
848 ulonglong *hash_arg)
849 : store_key_item(thd, to_field_arg, ptr, null_ptr_arg, length, item_arg),
850 hash(hash_arg) {}
name()851 const char *name() const override { return "func"; }
852
853 protected:
854 enum store_key_result copy_inner() override;
855 };
856
857 bool error_if_full_join(JOIN *join);
858 bool handle_query(THD *thd, LEX *lex, Query_result *result,
859 ulonglong added_options, ulonglong removed_options);
860
861 // Statement timeout function(s)
862 bool set_statement_timer(THD *thd);
863 void reset_statement_timer(THD *thd);
864
865 void free_underlaid_joins(THD *thd, SELECT_LEX *select);
866
867 void calc_used_field_length(TABLE *table, bool needs_rowid, uint *p_used_fields,
868 uint *p_used_fieldlength, uint *p_used_blobs,
869 bool *p_used_null_fields,
870 bool *p_used_uneven_bit_fields);
871
872 ORDER *simple_remove_const(ORDER *order, Item *where);
873 bool const_expression_in_where(Item *cond, Item *comp_item,
874 const Field *comp_field = nullptr,
875 Item **const_item = nullptr);
876 bool test_if_subpart(ORDER *a, ORDER *b);
877 void calc_group_buffer(JOIN *join, ORDER *group);
878 bool make_join_readinfo(JOIN *join, uint no_jbuf_after);
879 bool create_ref_for_key(JOIN *join, JOIN_TAB *j, Key_use *org_keyuse,
880 table_map used_tables);
881 bool types_allow_materialization(Item *outer, Item *inner);
882 bool and_conditions(Item **e1, Item *e2);
883
884 /**
885 Create a AND item of two existing items.
886 A new Item_cond_and item is created with the two supplied items as
887 arguments.
888
889 @note About handling of null pointers as arguments: if the first
890 argument is a null pointer, then the item given as second argument is
891 returned (no new Item_cond_and item is created). The second argument
892 must not be a null pointer.
893
894 @param cond the first argument to the new AND condition
895 @param item the second argument to the new AND condtion
896
897 @return the new AND item
898 */
and_items(Item * cond,Item * item)899 static inline Item *and_items(Item *cond, Item *item) {
900 DBUG_ASSERT(item != nullptr);
901 return (cond ? (new Item_cond_and(cond, item)) : item);
902 }
903
904 /// A variant of the above, guaranteed to return Item_bool_func.
and_items(Item * cond,Item_bool_func * item)905 static inline Item_bool_func *and_items(Item *cond, Item_bool_func *item) {
906 DBUG_ASSERT(item != nullptr);
907 return (cond ? (new Item_cond_and(cond, item)) : item);
908 }
909
910 uint actual_key_parts(const KEY *key_info);
911
912 class ORDER_with_src;
913
914 uint get_index_for_order(ORDER_with_src *order, QEP_TAB *tab, ha_rows limit,
915 bool *need_sort, bool *reverse);
916 int test_if_order_by_key(ORDER_with_src *order, TABLE *table, uint idx,
917 uint *used_key_parts, bool *skip_quick);
918 bool test_if_cheaper_ordering(const JOIN_TAB *tab, ORDER_with_src *order,
919 TABLE *table, Key_map usable_keys, int key,
920 ha_rows select_limit, int *new_key,
921 int *new_key_direction, ha_rows *new_select_limit,
922 uint *new_used_key_parts = nullptr,
923 uint *saved_best_key_parts = nullptr);
924 /**
925 Calculate properties of ref key: key length, number of used key parts,
926 dependency map, possibility of null.
927
928 @param keyuse Array of keys to consider
929 @param tab join_tab to calculate ref parameters for
930 @param key number of the key to use
931 @param used_tables tables read prior to this table
932 @param [out] chosen_keyuses when given, this function will fill array with
933 chosen keyuses
934 @param [out] length_out calculated length of the ref
935 @param [out] keyparts_out calculated number of used keyparts
936 @param [out] dep_map when given, calculated dependency map
937 @param [out] maybe_null when given, calculated maybe_null property
938 */
939
940 void calc_length_and_keyparts(Key_use *keyuse, JOIN_TAB *tab, const uint key,
941 table_map used_tables, Key_use **chosen_keyuses,
942 uint *length_out, uint *keyparts_out,
943 table_map *dep_map, bool *maybe_null);
944
945 /**
946 Set up the support structures (NULL bits, row offsets, etc.) for a semijoin
947 duplicate weedout table. The object is allocated on the given THD's MEM_ROOT.
948
949 @param thd the THD to allocate the object on
950 @param join the JOIN that will own the temporary table (ie., has the
951 responsibility to destroy it after use)
952 @param first_tab first table in row key (inclusive)
953 @param last_tab last table in row key (exclusive)
954 */
955 SJ_TMP_TABLE *create_sj_tmp_table(THD *thd, JOIN *join,
956 SJ_TMP_TABLE_TAB *first_tab,
957 SJ_TMP_TABLE_TAB *last_tab);
958
959 #endif /* SQL_SELECT_INCLUDED */
960