1 #ifndef SQL_SELECT_INCLUDED
2 #define SQL_SELECT_INCLUDED
3
4 /* Copyright (c) 2000, 2013, Oracle and/or its affiliates.
5 Copyright (c) 2008, 2020, MariaDB Corporation.
6
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; version 2 of the License.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335 USA */
19
20 /**
21 @file
22
23 @brief
24 classes to use when handling where clause
25 */
26
27 #ifdef USE_PRAGMA_INTERFACE
28 #pragma interface /* gcc class implementation */
29 #endif
30
31 #include "procedure.h"
32 #include "sql_array.h" /* Array */
33 #include "records.h" /* READ_RECORD */
34 #include "opt_range.h" /* SQL_SELECT, QUICK_SELECT_I */
35 #include "filesort.h"
36
37 typedef struct st_join_table JOIN_TAB;
38 /* Values in optimize */
39 #define KEY_OPTIMIZE_EXISTS 1U
40 #define KEY_OPTIMIZE_REF_OR_NULL 2U
41 #define KEY_OPTIMIZE_EQ 4U
42
get_hash_join_key_no()43 inline uint get_hash_join_key_no() { return MAX_KEY; }
44
is_hash_join_key_no(uint key)45 inline bool is_hash_join_key_no(uint key) { return key == MAX_KEY; }
46
47 typedef struct keyuse_t {
48 TABLE *table;
49 Item *val; /**< or value if no field */
50 table_map used_tables;
51 uint key, keypart, optimize;
52 key_part_map keypart_map;
53 ha_rows ref_table_rows;
54 /**
55 If true, the comparison this value was created from will not be
56 satisfied if val has NULL 'value'.
57 */
58 bool null_rejecting;
59 /*
60 !NULL - This KEYUSE was created from an equality that was wrapped into
61 an Item_func_trig_cond. This means the equality (and validity of
62 this KEYUSE element) can be turned on and off. The on/off state
63 is indicted by the pointed value:
64 *cond_guard == TRUE <=> equality condition is on
65 *cond_guard == FALSE <=> equality condition is off
66
67 NULL - Otherwise (the source equality can't be turned off)
68 */
69 bool *cond_guard;
70 /*
71 0..64 <=> This was created from semi-join IN-equality # sj_pred_no.
72 MAX_UINT Otherwise
73 */
74 uint sj_pred_no;
75
76 /*
77 If this is NULL than KEYUSE is always enabled.
78 Otherwise it points to the enabling flag for this keyuse (true <=> enabled)
79 */
80 bool *validity_ref;
81
is_for_hash_joinkeyuse_t82 bool is_for_hash_join() { return is_hash_join_key_no(key); }
83 } KEYUSE;
84
85
86 struct KEYUSE_EXT: public KEYUSE
87 {
88 /*
89 This keyuse can be used only when the partial join being extended
90 contains the tables from this table map
91 */
92 table_map needed_in_prefix;
93 /* The enabling flag for keyuses usable for splitting */
94 bool validity_var;
95 };
96
97 /// Used when finding key fields
98 struct KEY_FIELD {
99 Field *field;
100 Item_bool_func *cond;
101 Item *val; ///< May be empty if diff constant
102 uint level;
103 uint optimize;
104 bool eq_func;
105 /**
106 If true, the condition this struct represents will not be satisfied
107 when val IS NULL.
108 */
109 bool null_rejecting;
110 bool *cond_guard; /* See KEYUSE::cond_guard */
111 uint sj_pred_no; /* See KEYUSE::sj_pred_no */
112 };
113
114
115 #define NO_KEYPART ((uint)(-1))
116
117 class store_key;
118
119 const int NO_REF_PART= uint(-1);
120
121 typedef struct st_table_ref
122 {
123 bool key_err;
124 /** True if something was read into buffer in join_read_key. */
125 bool has_record;
126 uint key_parts; ///< num of ...
127 uint key_length; ///< length of key_buff
128 int key; ///< key no
129 uchar *key_buff; ///< value to look for with key
130 uchar *key_buff2; ///< key_buff+key_length
131 store_key **key_copy; //
132
133 /*
134 Bitmap of key parts which refer to constants. key_copy only has copiers for
135 non-const key parts.
136 */
137 key_part_map const_ref_part_map;
138
139 Item **items; ///< val()'s for each keypart
140 /*
141 Array of pointers to trigger variables. Some/all of the pointers may be
142 NULL. The ref access can be used iff
143
144 for each used key part i, (!cond_guards[i] || *cond_guards[i])
145
146 This array is used by subquery code. The subquery code may inject
147 triggered conditions, i.e. conditions that can be 'switched off'. A ref
148 access created from such condition is not valid when at least one of the
149 underlying conditions is switched off (see subquery code for more details)
150 */
151 bool **cond_guards;
152 /**
153 (null_rejecting & (1<<i)) means the condition is '=' and no matching
154 rows will be produced if items[i] IS NULL (see add_not_null_conds())
155 */
156 key_part_map null_rejecting;
157 table_map depend_map; ///< Table depends on these tables.
158
159 /* null byte position in the key_buf. Used for REF_OR_NULL optimization */
160 uchar *null_ref_key;
161 /*
162 ref_or_null optimization: number of key part that alternates between
163 the lookup value or NULL (there's only one such part).
164 If we're not using ref_or_null, the value is NO_REF_PART
165 */
166 uint null_ref_part;
167
168 /*
169 The number of times the record associated with this key was used
170 in the join.
171 */
172 ha_rows use_count;
173
174 /*
175 TRUE <=> disable the "cache" as doing lookup with the same key value may
176 produce different results (because of Index Condition Pushdown)
177
178 */
179 bool disable_cache;
180
181 /*
182 If true, this ref access was constructed from equalities generated by
183 LATERAL DERIVED (aka GROUP BY splitting) optimization
184 */
185 bool uses_splitting;
186
187 bool tmp_table_index_lookup_init(THD *thd, KEY *tmp_key, Item_iterator &it,
188 bool value, uint skip= 0);
189 bool is_access_triggered();
190 } TABLE_REF;
191
192
193 /*
194 The structs which holds the join connections and join states
195 */
196 enum join_type { JT_UNKNOWN,JT_SYSTEM,JT_CONST,JT_EQ_REF,JT_REF,JT_MAYBE_REF,
197 JT_ALL, JT_RANGE, JT_NEXT, JT_FT, JT_REF_OR_NULL,
198 JT_UNIQUE_SUBQUERY, JT_INDEX_SUBQUERY, JT_INDEX_MERGE,
199 JT_HASH, JT_HASH_RANGE, JT_HASH_NEXT, JT_HASH_INDEX_MERGE};
200
201 class JOIN;
202
203 enum enum_nested_loop_state
204 {
205 NESTED_LOOP_KILLED= -2, NESTED_LOOP_ERROR= -1,
206 NESTED_LOOP_OK= 0, NESTED_LOOP_NO_MORE_ROWS= 1,
207 NESTED_LOOP_QUERY_LIMIT= 3, NESTED_LOOP_CURSOR_LIMIT= 4
208 };
209
210
211 /* Possible sj_strategy values */
212 enum sj_strategy_enum
213 {
214 SJ_OPT_NONE=0,
215 SJ_OPT_DUPS_WEEDOUT=1,
216 SJ_OPT_LOOSE_SCAN =2,
217 SJ_OPT_FIRST_MATCH =3,
218 SJ_OPT_MATERIALIZE =4,
219 SJ_OPT_MATERIALIZE_SCAN=5
220 };
221
222 /* Values for JOIN_TAB::packed_info */
223 #define TAB_INFO_HAVE_VALUE 1U
224 #define TAB_INFO_USING_INDEX 2U
225 #define TAB_INFO_USING_WHERE 4U
226 #define TAB_INFO_FULL_SCAN_ON_NULL 8U
227
228 typedef enum_nested_loop_state
229 (*Next_select_func)(JOIN *, struct st_join_table *, bool);
230 Next_select_func setup_end_select_func(JOIN *join, JOIN_TAB *tab);
231 int rr_sequential(READ_RECORD *info);
232 int rr_sequential_and_unpack(READ_RECORD *info);
233 Item *remove_pushed_top_conjuncts(THD *thd, Item *cond);
234
235 #include "sql_explain.h"
236
237 /**************************************************************************************
238 * New EXPLAIN structures END
239 *************************************************************************************/
240
241 class JOIN_CACHE;
242 class SJ_TMP_TABLE;
243 class JOIN_TAB_RANGE;
244 class AGGR_OP;
245 class Filesort;
246 struct SplM_plan_info;
247 class SplM_opt_info;
248
249 typedef struct st_join_table {
250 TABLE *table;
251 TABLE_LIST *tab_list;
252 KEYUSE *keyuse; /**< pointer to first used key */
253 KEY *hj_key; /**< descriptor of the used best hash join key
254 not supported by any index */
255 SQL_SELECT *select;
256 COND *select_cond;
257 COND *on_precond; /**< part of on condition to check before
258 accessing the first inner table */
259 QUICK_SELECT_I *quick;
260 /*
261 The value of select_cond before we've attempted to do Index Condition
262 Pushdown. We may need to restore everything back if we first choose one
263 index but then reconsider (see test_if_skip_sort_order() for such
264 scenarios).
265 NULL means no index condition pushdown was performed.
266 */
267 Item *pre_idx_push_select_cond;
268 /*
269 Pointer to the associated ON expression. on_expr_ref=!NULL except for
270 degenerate joins.
271
272 Optimization phase: *on_expr_ref!=NULL for tables that are the single
273 tables on the inner side of the outer join (t1 LEFT JOIN t2 ON...)
274
275 Execution phase: *on_expr_ref!=NULL for tables that are first inner tables
276 within an outer join (which may have multiple tables)
277 */
278 Item **on_expr_ref;
279 COND_EQUAL *cond_equal; /**< multiple equalities for the on expression */
280 st_join_table *first_inner; /**< first inner table for including outerjoin */
281 bool found; /**< true after all matches or null complement */
282 bool not_null_compl;/**< true before null complement is added */
283 st_join_table *last_inner; /**< last table table for embedding outer join */
284 st_join_table *first_upper; /**< first inner table for embedding outer join */
285 st_join_table *first_unmatched; /**< used for optimization purposes only */
286
287 /*
288 For join tabs that are inside an SJM bush: root of the bush
289 */
290 st_join_table *bush_root_tab;
291
292 /* TRUE <=> This join_tab is inside an SJM bush and is the last leaf tab here */
293 bool last_leaf_in_bush;
294
295 /*
296 ptr - this is a bush, and ptr points to description of child join_tab
297 range
298 NULL - this join tab has no bush children
299 */
300 JOIN_TAB_RANGE *bush_children;
301
302 /* Special content for EXPLAIN 'Extra' column or NULL if none */
303 enum explain_extra_tag info;
304
305 Table_access_tracker *tracker;
306
307 Table_access_tracker *jbuf_tracker;
308 /*
309 Bitmap of TAB_INFO_* bits that encodes special line for EXPLAIN 'Extra'
310 column, or 0 if there is no info.
311 */
312 uint packed_info;
313
314 // READ_RECORD::Setup_func materialize_table;
315 READ_RECORD::Setup_func read_first_record;
316 Next_select_func next_select;
317 READ_RECORD read_record;
318 /*
319 Currently the following two fields are used only for a [NOT] IN subquery
320 if it is executed by an alternative full table scan when the left operand of
321 the subquery predicate is evaluated to NULL.
322 */
323 READ_RECORD::Setup_func save_read_first_record;/* to save read_first_record */
324 READ_RECORD::Read_func save_read_record;/* to save read_record.read_record */
325 double worst_seeks;
326 key_map const_keys; /**< Keys with constant part */
327 key_map checked_keys; /**< Keys checked in find_best */
328 key_map needed_reg;
329 key_map keys; /**< all keys with can be used */
330
331 /* Either #rows in the table or 1 for const table. */
332 ha_rows records;
333 /*
334 Number of records that will be scanned (yes scanned, not returned) by the
335 best 'independent' access method, i.e. table scan or QUICK_*_SELECT)
336 */
337 ha_rows found_records;
338 /*
339 Cost of accessing the table using "ALL" or range/index_merge access
340 method (but not 'index' for some reason), i.e. this matches method which
341 E(#records) is in found_records.
342 */
343 double read_time;
344
345 /* Copy of POSITION::records_read, set by get_best_combination() */
346 double records_read;
347
348 /* The selectivity of the conditions that can be pushed to the table */
349 double cond_selectivity;
350
351 /* Startup cost for execution */
352 double startup_cost;
353
354 double partial_join_cardinality;
355
356 table_map dependent,key_dependent;
357 /*
358 1 - use quick select
359 2 - use "Range checked for each record"
360 */
361 uint use_quick;
362 /*
363 Index to use. Note: this is valid only for 'index' access, but not range or
364 ref access.
365 */
366 uint index;
367 uint status; ///< Save status for cache
368 uint used_fields;
369 ulong used_fieldlength;
370 ulong max_used_fieldlength;
371 uint used_blobs;
372 uint used_null_fields;
373 uint used_uneven_bit_fields;
374 enum join_type type;
375 bool cached_eq_ref_table,eq_ref_table;
376 bool shortcut_for_distinct;
377 bool sorted;
378 /*
379 If it's not 0 the number stored this field indicates that the index
380 scan has been chosen to access the table data and we expect to scan
381 this number of rows for the table.
382 */
383 ha_rows limit;
384 TABLE_REF ref;
385 /* TRUE <=> condition pushdown supports other tables presence */
386 bool icp_other_tables_ok;
387 /*
388 TRUE <=> condition pushed to the index has to be factored out of
389 the condition pushed to the table
390 */
391 bool idx_cond_fact_out;
392 bool use_join_cache;
393 uint used_join_cache_level;
394 ulong join_buffer_size_limit;
395 JOIN_CACHE *cache;
396 /*
397 Index condition for BKA access join
398 */
399 Item *cache_idx_cond;
400 SQL_SELECT *cache_select;
401 AGGR_OP *aggr;
402 JOIN *join;
403 /*
404 Embedding SJ-nest (may be not the direct parent), or NULL if none.
405 This variable holds the result of table pullout.
406 */
407 TABLE_LIST *emb_sj_nest;
408
409 /* FirstMatch variables (final QEP) */
410 struct st_join_table *first_sj_inner_tab;
411 struct st_join_table *last_sj_inner_tab;
412
413 /* Variables for semi-join duplicate elimination */
414 SJ_TMP_TABLE *flush_weedout_table;
415 SJ_TMP_TABLE *check_weed_out_table;
416 /* for EXPLAIN only: */
417 SJ_TMP_TABLE *first_weedout_table;
418
419 /**
420 reference to saved plan and execution statistics
421 */
422 Explain_table_access *explain_plan;
423
424 /*
425 If set, means we should stop join enumeration after we've got the first
426 match and return to the specified join tab. May point to
427 join->join_tab[-1] which means stop join execution after the first
428 match.
429 */
430 struct st_join_table *do_firstmatch;
431
432 /*
433 ptr - We're doing a LooseScan, this join tab is the first (i.e.
434 "driving") join tab), and ptr points to the last join tab
435 handled by the strategy. loosescan_match_tab->found_match
436 should be checked to see if the current value group had a match.
437 NULL - Not doing a loose scan on this join tab.
438 */
439 struct st_join_table *loosescan_match_tab;
440
441 /* TRUE <=> we are inside LooseScan range */
442 bool inside_loosescan_range;
443
444 /* Buffer to save index tuple to be able to skip duplicates */
445 uchar *loosescan_buf;
446
447 /*
448 Index used by LooseScan (we store it here separately because ref access
449 stores it in tab->ref.key, while range scan stores it in tab->index, etc)
450 */
451 uint loosescan_key;
452
453 /* Length of key tuple (depends on #keyparts used) to store in the above */
454 uint loosescan_key_len;
455
456 /* Used by LooseScan. TRUE<=> there has been a matching record combination */
457 bool found_match;
458
459 /*
460 Used by DuplicateElimination. tab->table->ref must have the rowid
461 whenever we have a current record.
462 */
463 int keep_current_rowid;
464
465 /* NestedOuterJoins: Bitmap of nested joins this table is part of */
466 nested_join_map embedding_map;
467
468 /* Tmp table info */
469 TMP_TABLE_PARAM *tmp_table_param;
470
471 /* Sorting related info */
472 Filesort *filesort;
473 SORT_INFO *filesort_result;
474
475 /*
476 Non-NULL value means this join_tab must do window function computation
477 before reading.
478 */
479 Window_funcs_computation* window_funcs_step;
480
481 /**
482 List of topmost expressions in the select list. The *next* JOIN_TAB
483 in the plan should use it to obtain correct values. Same applicable to
484 all_fields. These lists are needed because after tmp tables functions
485 will be turned to fields. These variables are pointing to
486 tmp_fields_list[123]. Valid only for tmp tables and the last non-tmp
487 table in the query plan.
488 @see JOIN::make_aggr_tables_info()
489 */
490 List<Item> *fields;
491 /** List of all expressions in the select list */
492 List<Item> *all_fields;
493 /*
494 Pointer to the ref array slice which to switch to before sending
495 records. Valid only for tmp tables.
496 */
497 Ref_ptr_array *ref_array;
498
499 /** Number of records saved in tmp table */
500 ha_rows send_records;
501
502 /** HAVING condition for checking prior saving a record into tmp table*/
503 Item *having;
504
505 /** TRUE <=> remove duplicates on this table. */
506 bool distinct;
507
508 /*
509 Semi-join strategy to be used for this join table. This is a copy of
510 POSITION::sj_strategy field. This field is set up by the
511 fix_semijoin_strategies_for_picked_join_order.
512 */
513 enum sj_strategy_enum sj_strategy;
514
515 uint n_sj_tables;
516
517 bool preread_init_done;
518
519 void cleanup();
is_using_loose_index_scanst_join_table520 inline bool is_using_loose_index_scan()
521 {
522 const SQL_SELECT *sel= filesort ? filesort->select : select;
523 return (sel && sel->quick &&
524 (sel->quick->get_type() == QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX));
525 }
is_using_agg_loose_index_scanst_join_table526 bool is_using_agg_loose_index_scan ()
527 {
528 return (is_using_loose_index_scan() &&
529 ((QUICK_GROUP_MIN_MAX_SELECT *)select->quick)->is_agg_distinct());
530 }
is_inner_table_of_semi_join_with_first_matchst_join_table531 bool is_inner_table_of_semi_join_with_first_match()
532 {
533 return first_sj_inner_tab != NULL;
534 }
is_inner_table_of_semijoinst_join_table535 bool is_inner_table_of_semijoin()
536 {
537 return emb_sj_nest != NULL;
538 }
is_inner_table_of_outer_joinst_join_table539 bool is_inner_table_of_outer_join()
540 {
541 return first_inner != NULL;
542 }
is_single_inner_of_semi_join_with_first_matchst_join_table543 bool is_single_inner_of_semi_join_with_first_match()
544 {
545 return first_sj_inner_tab == this && last_sj_inner_tab == this;
546 }
is_single_inner_of_outer_joinst_join_table547 bool is_single_inner_of_outer_join()
548 {
549 return first_inner == this && first_inner->last_inner == this;
550 }
is_first_inner_for_outer_joinst_join_table551 bool is_first_inner_for_outer_join()
552 {
553 return first_inner && first_inner == this;
554 }
use_match_flagst_join_table555 bool use_match_flag()
556 {
557 return is_first_inner_for_outer_join() || first_sj_inner_tab == this ;
558 }
check_only_first_matchst_join_table559 bool check_only_first_match()
560 {
561 return is_inner_table_of_semi_join_with_first_match() ||
562 (is_inner_table_of_outer_join() &&
563 table->reginfo.not_exists_optimize);
564 }
is_last_inner_tablest_join_table565 bool is_last_inner_table()
566 {
567 return (first_inner && first_inner->last_inner == this) ||
568 last_sj_inner_tab == this;
569 }
570 /*
571 Check whether the table belongs to a nest of inner tables of an
572 outer join or to a nest of inner tables of a semi-join
573 */
is_nested_innerst_join_table574 bool is_nested_inner()
575 {
576 if (first_inner &&
577 (first_inner != first_inner->last_inner || first_inner->first_upper))
578 return TRUE;
579 if (first_sj_inner_tab && first_sj_inner_tab != last_sj_inner_tab)
580 return TRUE;
581 return FALSE;
582 }
get_first_inner_tablest_join_table583 struct st_join_table *get_first_inner_table()
584 {
585 if (first_inner)
586 return first_inner;
587 return first_sj_inner_tab;
588 }
set_select_condst_join_table589 void set_select_cond(COND *to, uint line)
590 {
591 DBUG_PRINT("info", ("select_cond changes %p -> %p at line %u tab %p",
592 select_cond, to, line, this));
593 select_cond= to;
594 }
set_condst_join_table595 COND *set_cond(COND *new_cond)
596 {
597 COND *tmp_select_cond= select_cond;
598 set_select_cond(new_cond, __LINE__);
599 if (select)
600 select->cond= new_cond;
601 return tmp_select_cond;
602 }
603 void calc_used_field_length(bool max_fl);
get_used_fieldlengthst_join_table604 ulong get_used_fieldlength()
605 {
606 if (!used_fieldlength)
607 calc_used_field_length(FALSE);
608 return used_fieldlength;
609 }
get_max_used_fieldlengthst_join_table610 ulong get_max_used_fieldlength()
611 {
612 if (!max_used_fieldlength)
613 calc_used_field_length(TRUE);
614 return max_used_fieldlength;
615 }
get_partial_join_cardinalityst_join_table616 double get_partial_join_cardinality() { return partial_join_cardinality; }
617 bool hash_join_is_possible();
618 int make_scan_filter();
is_ref_for_hash_joinst_join_table619 bool is_ref_for_hash_join() { return is_hash_join_key_no(ref.key); }
get_keyinfo_by_key_nost_join_table620 KEY *get_keyinfo_by_key_no(uint key)
621 {
622 return (is_hash_join_key_no(key) ? hj_key : table->key_info+key);
623 }
624 double scan_time();
625 ha_rows get_examined_rows();
626 bool preread_init();
627
is_sjm_nestst_join_table628 bool is_sjm_nest() { return MY_TEST(bush_children); }
629
630 /*
631 If this join_tab reads a non-merged semi-join (also called jtbm), return
632 the select's number. Otherwise, return 0.
633 */
get_non_merged_semijoin_selectst_join_table634 int get_non_merged_semijoin_select() const
635 {
636 Item_in_subselect *subq;
637 if (table->pos_in_table_list &&
638 (subq= table->pos_in_table_list->jtbm_subselect))
639 {
640 return subq->unit->first_select()->select_number;
641 }
642 return 0; /* Not a merged semi-join */
643 }
644
access_from_tables_is_allowedst_join_table645 bool access_from_tables_is_allowed(table_map used_tables,
646 table_map sjm_lookup_tables)
647 {
648 table_map used_sjm_lookup_tables= used_tables & sjm_lookup_tables;
649 return !used_sjm_lookup_tables ||
650 (emb_sj_nest &&
651 !(used_sjm_lookup_tables & ~emb_sj_nest->sj_inner_tables));
652 }
653
654 bool keyuse_is_valid_for_access_in_chosen_plan(JOIN *join, KEYUSE *keyuse);
655
656 void remove_redundant_bnl_scan_conds();
657
658 bool save_explain_data(Explain_table_access *eta, table_map prefix_tables,
659 bool distinct, struct st_join_table *first_top_tab);
660
661 bool use_order() const; ///< Use ordering provided by chosen index?
662 bool sort_table();
663 bool remove_duplicates();
664
665 void partial_cleanup();
666 void add_keyuses_for_splitting();
667 SplM_plan_info *choose_best_splitting(double record_count,
668 table_map remaining_tables);
669 bool fix_splitting(SplM_plan_info *spl_plan, table_map remaining_tables,
670 bool is_const_table);
671 } JOIN_TAB;
672
673
674 #include "sql_join_cache.h"
675
676 enum_nested_loop_state
677 sub_select_cache(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
678 enum_nested_loop_state
679 sub_select(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
680 enum_nested_loop_state
681 sub_select_postjoin_aggr(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
682
683 enum_nested_loop_state
684 end_send_group(JOIN *join, JOIN_TAB *join_tab __attribute__((unused)),
685 bool end_of_records);
686 enum_nested_loop_state
687 end_write_group(JOIN *join, JOIN_TAB *join_tab __attribute__((unused)),
688 bool end_of_records);
689
690
691 struct st_position;
692
693 class Semi_join_strategy_picker
694 {
695 public:
696 /* Called when starting to build a new join prefix */
697 virtual void set_empty() = 0;
698
699 /*
700 Update internal state after another table has been added to the join
701 prefix
702 */
703 virtual void set_from_prev(struct st_position *prev) = 0;
704
705 virtual bool check_qep(JOIN *join,
706 uint idx,
707 table_map remaining_tables,
708 const JOIN_TAB *new_join_tab,
709 double *record_count,
710 double *read_time,
711 table_map *handled_fanout,
712 sj_strategy_enum *strategy,
713 struct st_position *loose_scan_pos) = 0;
714
715 virtual void mark_used() = 0;
716
~Semi_join_strategy_picker()717 virtual ~Semi_join_strategy_picker() {}
718 };
719
720
721 /*
722 Duplicate Weedout strategy optimization state
723 */
724
725 class Duplicate_weedout_picker : public Semi_join_strategy_picker
726 {
727 /* The first table that the strategy will need to handle */
728 uint first_dupsweedout_table;
729
730 /*
731 Tables that we will need to have in the prefix to do the weedout step
732 (all inner and all outer that the involved semi-joins are correlated with)
733 */
734 table_map dupsweedout_tables;
735
736 bool is_used;
737 public:
set_empty()738 void set_empty()
739 {
740 dupsweedout_tables= 0;
741 first_dupsweedout_table= MAX_TABLES;
742 is_used= FALSE;
743 }
744 void set_from_prev(struct st_position *prev);
745
746 bool check_qep(JOIN *join,
747 uint idx,
748 table_map remaining_tables,
749 const JOIN_TAB *new_join_tab,
750 double *record_count,
751 double *read_time,
752 table_map *handled_fanout,
753 sj_strategy_enum *stratey,
754 struct st_position *loose_scan_pos);
755
mark_used()756 void mark_used() { is_used= TRUE; }
757 friend void fix_semijoin_strategies_for_picked_join_order(JOIN *join);
758 };
759
760
761 class Firstmatch_picker : public Semi_join_strategy_picker
762 {
763 /*
764 Index of the first inner table that we intend to handle with this
765 strategy
766 */
767 uint first_firstmatch_table;
768 /*
769 Tables that were not in the join prefix when we've started considering
770 FirstMatch strategy.
771 */
772 table_map first_firstmatch_rtbl;
773 /*
774 Tables that need to be in the prefix before we can calculate the cost
775 of using FirstMatch strategy.
776 */
777 table_map firstmatch_need_tables;
778
779 bool is_used;
780
in_firstmatch_prefix()781 bool in_firstmatch_prefix() { return (first_firstmatch_table != MAX_TABLES); }
invalidate_firstmatch_prefix()782 void invalidate_firstmatch_prefix() { first_firstmatch_table= MAX_TABLES; }
783 public:
set_empty()784 void set_empty()
785 {
786 invalidate_firstmatch_prefix();
787 is_used= FALSE;
788 }
789
790 void set_from_prev(struct st_position *prev);
791 bool check_qep(JOIN *join,
792 uint idx,
793 table_map remaining_tables,
794 const JOIN_TAB *new_join_tab,
795 double *record_count,
796 double *read_time,
797 table_map *handled_fanout,
798 sj_strategy_enum *strategy,
799 struct st_position *loose_scan_pos);
800
mark_used()801 void mark_used() { is_used= TRUE; }
802 friend void fix_semijoin_strategies_for_picked_join_order(JOIN *join);
803 };
804
805
806 class LooseScan_picker : public Semi_join_strategy_picker
807 {
808 /* The first (i.e. driving) table we're doing loose scan for */
809 uint first_loosescan_table;
810 /*
811 Tables that need to be in the prefix before we can calculate the cost
812 of using LooseScan strategy.
813 */
814 table_map loosescan_need_tables;
815
816 /*
817 keyno - Planning to do LooseScan on this key. If keyuse is NULL then
818 this is a full index scan, otherwise this is a ref+loosescan
819 scan (and keyno matches the KEUSE's)
820 MAX_KEY - Not doing a LooseScan
821 */
822 uint loosescan_key; // final (one for strategy instance )
823 uint loosescan_parts; /* Number of keyparts to be kept distinct */
824
825 bool is_used;
826 public:
set_empty()827 void set_empty()
828 {
829 first_loosescan_table= MAX_TABLES;
830 is_used= FALSE;
831 }
832
833 void set_from_prev(struct st_position *prev);
834 bool check_qep(JOIN *join,
835 uint idx,
836 table_map remaining_tables,
837 const JOIN_TAB *new_join_tab,
838 double *record_count,
839 double *read_time,
840 table_map *handled_fanout,
841 sj_strategy_enum *strategy,
842 struct st_position *loose_scan_pos);
mark_used()843 void mark_used() { is_used= TRUE; }
844
845 friend class Loose_scan_opt;
846 friend void best_access_path(JOIN *join,
847 JOIN_TAB *s,
848 table_map remaining_tables,
849 const struct st_position *join_positions,
850 uint idx,
851 bool disable_jbuf,
852 double record_count,
853 struct st_position *pos,
854 struct st_position *loose_scan_pos);
855 friend bool get_best_combination(JOIN *join);
856 friend int setup_semijoin_loosescan(JOIN *join);
857 friend void fix_semijoin_strategies_for_picked_join_order(JOIN *join);
858 };
859
860
861 class Sj_materialization_picker : public Semi_join_strategy_picker
862 {
863 bool is_used;
864
865 /* The last inner table (valid once we're after it) */
866 uint sjm_scan_last_inner;
867 /*
868 Tables that we need to have in the prefix to calculate the correct cost.
869 Basically, we need all inner tables and outer tables mentioned in the
870 semi-join's ON expression so we can correctly account for fanout.
871 */
872 table_map sjm_scan_need_tables;
873
874 public:
set_empty()875 void set_empty()
876 {
877 sjm_scan_need_tables= 0;
878 sjm_scan_last_inner= 0;
879 is_used= FALSE;
880 }
881 void set_from_prev(struct st_position *prev);
882 bool check_qep(JOIN *join,
883 uint idx,
884 table_map remaining_tables,
885 const JOIN_TAB *new_join_tab,
886 double *record_count,
887 double *read_time,
888 table_map *handled_fanout,
889 sj_strategy_enum *strategy,
890 struct st_position *loose_scan_pos);
mark_used()891 void mark_used() { is_used= TRUE; }
892
893 friend void fix_semijoin_strategies_for_picked_join_order(JOIN *join);
894 };
895
896
897 /**
898 Information about a position of table within a join order. Used in join
899 optimization.
900 */
901 typedef struct st_position
902 {
903 /* The table that's put into join order */
904 JOIN_TAB *table;
905
906 /*
907 The "fanout": number of output rows that will be produced (after
908 pushed down selection condition is applied) per each row combination of
909 previous tables.
910 */
911 double records_read;
912
913 /* The selectivity of the pushed down conditions */
914 double cond_selectivity;
915
916 /*
917 Cost accessing the table in course of the entire complete join execution,
918 i.e. cost of one access method use (e.g. 'range' or 'ref' scan ) times
919 number the access method will be invoked.
920 */
921 double read_time;
922
923 /* Cumulative cost and record count for the join prefix */
924 Cost_estimate prefix_cost;
925 double prefix_record_count;
926
927 /*
928 NULL - 'index' or 'range' or 'index_merge' or 'ALL' access is used.
929 Other - [eq_]ref[_or_null] access is used. Pointer to {t.keypart1 = expr}
930 */
931 KEYUSE *key;
932
933 /* If ref-based access is used: bitmap of tables this table depends on */
934 table_map ref_depend_map;
935
936 /*
937 TRUE <=> join buffering will be used. At the moment this is based on
938 *very* imprecise guesses made in best_access_path().
939 */
940 bool use_join_buffer;
941
942 /*
943 Current optimization state: Semi-join strategy to be used for this
944 and preceding join tables.
945
946 Join optimizer sets this for the *last* join_tab in the
947 duplicate-generating range. That is, in order to interpret this field,
948 one needs to traverse join->[best_]positions array from right to left.
949 When you see a join table with sj_strategy!= SJ_OPT_NONE, some other
950 field (depending on the strategy) tells how many preceding positions
951 this applies to. The values of covered_preceding_positions->sj_strategy
952 must be ignored.
953 */
954 enum sj_strategy_enum sj_strategy;
955
956 /*
957 Valid only after fix_semijoin_strategies_for_picked_join_order() call:
958 if sj_strategy!=SJ_OPT_NONE, this is the number of subsequent tables that
959 are covered by the specified semi-join strategy
960 */
961 uint n_sj_tables;
962
963 /*
964 Bitmap of semi-join inner tables that are in the join prefix and for
965 which there's no provision for how to eliminate semi-join duplicates
966 they produce.
967 */
968 table_map dups_producing_tables;
969
970 table_map inner_tables_handled_with_other_sjs;
971
972 Duplicate_weedout_picker dups_weedout_picker;
973 Firstmatch_picker firstmatch_picker;
974 LooseScan_picker loosescan_picker;
975 Sj_materialization_picker sjmat_picker;
976
977 /* Info on splitting plan used at this position */
978 SplM_plan_info *spl_plan;
979 } POSITION;
980
981 typedef Bounds_checked_array<Item_null_result*> Item_null_array;
982
983 typedef struct st_rollup
984 {
985 enum State { STATE_NONE, STATE_INITED, STATE_READY };
986 State state;
987 Item_null_array null_items;
988 Ref_ptr_array *ref_pointer_arrays;
989 List<Item> *fields;
990 } ROLLUP;
991
992
993 class JOIN_TAB_RANGE: public Sql_alloc
994 {
995 public:
996 JOIN_TAB *start;
997 JOIN_TAB *end;
998 };
999
1000 class Pushdown_query;
1001
1002 /**
1003 @brief
1004 Class to perform postjoin aggregation operations
1005
1006 @details
1007 The result records are obtained on the put_record() call.
1008 The aggrgation process is determined by the write_func, it could be:
1009 end_write Simply store all records in tmp table.
1010 end_write_group Perform grouping using join->group_fields,
1011 records are expected to be sorted.
1012 end_update Perform grouping using the key generated on tmp
1013 table. Input records aren't expected to be sorted.
1014 Tmp table uses the heap engine
1015 end_update_unique Same as above, but the engine is myisam.
1016
1017 Lazy table initialization is used - the table will be instantiated and
1018 rnd/index scan started on the first put_record() call.
1019
1020 */
1021
1022 class AGGR_OP :public Sql_alloc
1023 {
1024 public:
1025 JOIN_TAB *join_tab;
1026
AGGR_OP(JOIN_TAB * tab)1027 AGGR_OP(JOIN_TAB *tab) : join_tab(tab), write_func(NULL)
1028 {};
1029
put_record()1030 enum_nested_loop_state put_record() { return put_record(false); };
1031 /*
1032 Send the result of operation further (to a next operation/client)
1033 This function is called after all records were put into tmp table.
1034
1035 @return return one of enum_nested_loop_state values.
1036 */
1037 enum_nested_loop_state end_send();
1038 /** write_func setter */
set_write_func(Next_select_func new_write_func)1039 void set_write_func(Next_select_func new_write_func)
1040 {
1041 write_func= new_write_func;
1042 }
1043
1044 private:
1045 /** Write function that would be used for saving records in tmp table. */
1046 Next_select_func write_func;
1047 enum_nested_loop_state put_record(bool end_of_records);
1048 bool prepare_tmp_table();
1049 };
1050
1051
1052 class JOIN :public Sql_alloc
1053 {
1054 private:
1055 JOIN(const JOIN &rhs); /**< not implemented */
1056 JOIN& operator=(const JOIN &rhs); /**< not implemented */
1057
1058 protected:
1059
1060 /**
1061 The subset of the state of a JOIN that represents an optimized query
1062 execution plan. Allows saving/restoring different JOIN plans for the same
1063 query.
1064 */
1065 class Join_plan_state {
1066 public:
1067 DYNAMIC_ARRAY keyuse; /* Copy of the JOIN::keyuse array. */
1068 POSITION *best_positions; /* Copy of JOIN::best_positions */
1069 /* Copies of the JOIN_TAB::keyuse pointers for each JOIN_TAB. */
1070 KEYUSE **join_tab_keyuse;
1071 /* Copies of JOIN_TAB::checked_keys for each JOIN_TAB. */
1072 key_map *join_tab_checked_keys;
1073 SJ_MATERIALIZATION_INFO **sj_mat_info;
1074 my_bool error;
1075 public:
Join_plan_state(uint tables)1076 Join_plan_state(uint tables) : error(0)
1077 {
1078 keyuse.elements= 0;
1079 keyuse.buffer= NULL;
1080 keyuse.malloc_flags= 0;
1081 best_positions= 0; /* To detect errors */
1082 error= my_multi_malloc(MYF(MY_WME),
1083 &best_positions,
1084 sizeof(*best_positions) * (tables + 1),
1085 &join_tab_keyuse,
1086 sizeof(*join_tab_keyuse) * tables,
1087 &join_tab_checked_keys,
1088 sizeof(*join_tab_checked_keys) * tables,
1089 &sj_mat_info,
1090 sizeof(sj_mat_info) * tables,
1091 NullS) == 0;
1092 }
1093 Join_plan_state(JOIN *join);
~Join_plan_state()1094 ~Join_plan_state()
1095 {
1096 delete_dynamic(&keyuse);
1097 my_free(best_positions);
1098 }
1099 };
1100
1101 /* Results of reoptimizing a JOIN via JOIN::reoptimize(). */
1102 enum enum_reopt_result {
1103 REOPT_NEW_PLAN, /* there is a new reoptimized plan */
1104 REOPT_OLD_PLAN, /* no new improved plan can be found, use the old one */
1105 REOPT_ERROR, /* an irrecovarable error occurred during reoptimization */
1106 REOPT_NONE /* not yet reoptimized */
1107 };
1108
1109 /* Support for plan reoptimization with rewritten conditions. */
1110 enum_reopt_result reoptimize(Item *added_where, table_map join_tables,
1111 Join_plan_state *save_to);
1112 /* Choose a subquery plan for a table-less subquery. */
1113 bool choose_tableless_subquery_plan();
1114 void handle_implicit_grouping_with_window_funcs();
1115
1116 public:
1117 void save_query_plan(Join_plan_state *save_to);
1118 void reset_query_plan();
1119 void restore_query_plan(Join_plan_state *restore_from);
1120
1121 public:
1122 JOIN_TAB *join_tab, **best_ref;
1123
1124 /* List of fields that aren't under an aggregate function */
1125 List<Item_field> non_agg_fields;
1126
1127 JOIN_TAB **map2table; ///< mapping between table indexes and JOIN_TABs
1128 List<JOIN_TAB_RANGE> join_tab_ranges;
1129
1130 /*
1131 Base tables participating in the join. After join optimization is done, the
1132 tables are stored in the join order (but the only really important part is
1133 that const tables are first).
1134 */
1135 TABLE **table;
1136 /**
1137 The table which has an index that allows to produce the requried ordering.
1138 A special value of 0x1 means that the ordering will be produced by
1139 passing 1st non-const table to filesort(). NULL means no such table exists.
1140 */
1141 TABLE *sort_by_table;
1142 /*
1143 Number of tables in the join.
1144 (In MySQL, it is named 'tables' and is also the number of elements in
1145 join->join_tab array. In MariaDB, the latter is not true, so we've renamed
1146 the variable)
1147 */
1148 uint table_count;
1149 uint outer_tables; /**< Number of tables that are not inside semijoin */
1150 uint const_tables;
1151 /*
1152 Number of tables in the top join_tab array. Normally this matches
1153 (join_tab_ranges.head()->end - join_tab_ranges.head()->start).
1154
1155 We keep it here so that it is saved/restored with JOIN::restore_tmp.
1156 */
1157 uint top_join_tab_count;
1158 uint aggr_tables; ///< Number of post-join tmp tables
1159 uint send_group_parts;
1160 /*
1161 True if the query has GROUP BY.
1162 (that is, if group_by != NULL. when DISTINCT is converted into GROUP BY, it
1163 will set this, too. It is not clear why we need a separate var from
1164 group_list)
1165 */
1166 bool group;
1167 bool need_distinct;
1168
1169 /**
1170 Indicates that grouping will be performed on the result set during
1171 query execution. This field belongs to query execution.
1172
1173 @see make_group_fields, alloc_group_fields, JOIN::exec
1174 */
1175 bool sort_and_group;
1176 bool first_record,full_join, no_field_update;
1177 bool hash_join;
1178 bool do_send_rows;
1179 table_map const_table_map;
1180 /**
1181 Bitmap of semijoin tables that the current partial plan decided
1182 to materialize and access by lookups
1183 */
1184 table_map sjm_lookup_tables;
1185 /**
1186 Bitmap of semijoin tables that the chosen plan decided
1187 to materialize to scan the results of materialization
1188 */
1189 table_map sjm_scan_tables;
1190 /*
1191 Constant tables for which we have found a row (as opposed to those for
1192 which we didn't).
1193 */
1194 table_map found_const_table_map;
1195
1196 /* Tables removed by table elimination. Set to 0 before the elimination. */
1197 table_map eliminated_tables;
1198 /*
1199 Bitmap of all inner tables from outer joins (set at start of
1200 make_join_statistics)
1201 */
1202 table_map outer_join;
1203 /* Bitmap of tables used in the select list items */
1204 table_map select_list_used_tables;
1205 ha_rows send_records,found_records,join_examined_rows;
1206
1207 /*
1208 LIMIT for the JOIN operation. When not using aggregation or DISITNCT, this
1209 is the same as select's LIMIT clause specifies.
1210 Note that this doesn't take sql_calc_found_rows into account.
1211 */
1212 ha_rows row_limit;
1213
1214 /*
1215 How many output rows should be produced after GROUP BY.
1216 (if sql_calc_found_rows is used, LIMIT is ignored)
1217 */
1218 ha_rows select_limit;
1219 /*
1220 Number of duplicate rows found in UNION.
1221 */
1222 ha_rows duplicate_rows;
1223 /**
1224 Used to fetch no more than given amount of rows per one
1225 fetch operation of server side cursor.
1226 The value is checked in end_send and end_send_group in fashion, similar
1227 to offset_limit_cnt:
1228 - fetch_limit= HA_POS_ERROR if there is no cursor.
1229 - when we open a cursor, we set fetch_limit to 0,
1230 - on each fetch iteration we add num_rows to fetch to fetch_limit
1231 NOTE: currently always HA_POS_ERROR.
1232 */
1233 ha_rows fetch_limit;
1234
1235 /* Finally picked QEP. This is result of join optimization */
1236 POSITION *best_positions;
1237
1238 Pushdown_query *pushdown_query;
1239 JOIN_TAB *original_join_tab;
1240 uint original_table_count;
1241
1242 /******* Join optimization state members start *******/
1243 /*
1244 pointer - we're doing optimization for a semi-join materialization nest.
1245 NULL - otherwise
1246 */
1247 TABLE_LIST *emb_sjm_nest;
1248
1249 /* Current join optimization state */
1250 POSITION *positions;
1251
1252 /*
1253 Bitmap of nested joins embedding the position at the end of the current
1254 partial join (valid only during join optimizer run).
1255 */
1256 nested_join_map cur_embedding_map;
1257
1258 /*
1259 Bitmap of inner tables of semi-join nests that have a proper subset of
1260 their tables in the current join prefix. That is, of those semi-join
1261 nests that have their tables both in and outside of the join prefix.
1262 */
1263 table_map cur_sj_inner_tables;
1264
1265 /* We also maintain a stack of join optimization states in * join->positions[] */
1266 /******* Join optimization state members end *******/
1267
1268 /*
1269 Tables within complex firstmatch ranges (i.e. those where inner tables are
1270 interleaved with outer tables). Join buffering cannot be used for these.
1271 */
1272 table_map complex_firstmatch_tables;
1273
1274 Next_select_func first_select;
1275 /*
1276 The cost of best complete join plan found so far during optimization,
1277 after optimization phase - cost of picked join order (not taking into
1278 account the changes made by test_if_skip_sort_order()).
1279 */
1280 double best_read;
1281 /*
1282 Estimated result rows (fanout) of the join operation. If this is a subquery
1283 that is reexecuted multiple times, this value includes the estiamted # of
1284 reexecutions. This value is equal to the multiplication of all
1285 join->positions[i].records_read of a JOIN.
1286 */
1287 double join_record_count;
1288 List<Item> *fields;
1289 List<Cached_item> group_fields, group_fields_cache;
1290 THD *thd;
1291 Item_sum **sum_funcs, ***sum_funcs_end;
1292 /** second copy of sumfuncs (for queries with 2 temporary tables */
1293 Item_sum **sum_funcs2, ***sum_funcs_end2;
1294 Procedure *procedure;
1295 Item *having;
1296 Item *tmp_having; ///< To store having when processed temporary table
1297 Item *having_history; ///< Store having for explain
1298 ORDER *group_list_for_estimates;
1299 bool having_is_correlated;
1300 ulonglong select_options;
1301 /*
1302 Bitmap of allowed types of the join caches that
1303 can be used for join operations
1304 */
1305 uint allowed_join_cache_types;
1306 bool allowed_semijoin_with_cache;
1307 bool allowed_outer_join_with_cache;
1308 /* Maximum level of the join caches that can be used for join operations */
1309 uint max_allowed_join_cache_level;
1310 select_result *result;
1311 TMP_TABLE_PARAM tmp_table_param;
1312 MYSQL_LOCK *lock;
1313 /// unit structure (with global parameters) for this select
1314 SELECT_LEX_UNIT *unit;
1315 /// select that processed
1316 SELECT_LEX *select_lex;
1317 /**
1318 TRUE <=> optimizer must not mark any table as a constant table.
1319 This is needed for subqueries in form "a IN (SELECT .. UNION SELECT ..):
1320 when we optimize the select that reads the results of the union from a
1321 temporary table, we must not mark the temp. table as constant because
1322 the number of rows in it may vary from one subquery execution to another.
1323 */
1324 bool no_const_tables;
1325 /*
1326 This flag is set if we call no_rows_in_result() as par of end_group().
1327 This is used as a simple speed optimization to avoiding calling
1328 restore_no_rows_in_result() in ::reinit()
1329 */
1330 bool no_rows_in_result_called;
1331
1332 /**
1333 This is set if SQL_CALC_ROWS was calculated by filesort()
1334 and should be taken from the appropriate JOIN_TAB
1335 */
1336 bool filesort_found_rows;
1337
1338 bool subq_exit_fl;
1339
1340 ROLLUP rollup; ///< Used with rollup
1341
1342 bool mixed_implicit_grouping;
1343 bool select_distinct; ///< Set if SELECT DISTINCT
1344 /**
1345 If we have the GROUP BY statement in the query,
1346 but the group_list was emptied by optimizer, this
1347 flag is TRUE.
1348 It happens when fields in the GROUP BY are from
1349 constant table
1350 */
1351 bool group_optimized_away;
1352
1353 /*
1354 simple_xxxxx is set if ORDER/GROUP BY doesn't include any references
1355 to other tables than the first non-constant table in the JOIN.
1356 It's also set if ORDER/GROUP BY is empty.
1357 Used for deciding for or against using a temporary table to compute
1358 GROUP/ORDER BY.
1359 */
1360 bool simple_order, simple_group;
1361
1362 /*
1363 ordered_index_usage is set if an ordered index access
1364 should be used instead of a filesort when computing
1365 ORDER/GROUP BY.
1366 */
1367 enum
1368 {
1369 ordered_index_void, // No ordered index avail.
1370 ordered_index_group_by, // Use index for GROUP BY
1371 ordered_index_order_by // Use index for ORDER BY
1372 } ordered_index_usage;
1373
1374 /**
1375 Is set only in case if we have a GROUP BY clause
1376 and no ORDER BY after constant elimination of 'order'.
1377 */
1378 bool no_order;
1379 /** Is set if we have a GROUP BY and we have ORDER BY on a constant. */
1380 bool skip_sort_order;
1381
1382 bool need_tmp;
1383 bool hidden_group_fields;
1384 /* TRUE if there was full cleunap of the JOIN */
1385 bool cleaned;
1386 DYNAMIC_ARRAY keyuse;
1387 Item::cond_result cond_value, having_value;
1388 /**
1389 Impossible where after reading const tables
1390 (set in make_join_statistics())
1391 */
1392 bool impossible_where;
1393 List<Item> all_fields; ///< to store all fields that used in query
1394 ///Above list changed to use temporary table
1395 List<Item> tmp_all_fields1, tmp_all_fields2, tmp_all_fields3;
1396 ///Part, shared with list above, emulate following list
1397 List<Item> tmp_fields_list1, tmp_fields_list2, tmp_fields_list3;
1398 List<Item> &fields_list; ///< hold field list passed to mysql_select
1399 List<Item> procedure_fields_list;
1400 int error;
1401
1402 ORDER *order, *group_list, *proc_param; //hold parameters of mysql_select
1403 COND *conds; // ---"---
1404 Item *conds_history; // store WHERE for explain
1405 COND *outer_ref_cond; ///<part of conds containing only outer references
1406 COND *pseudo_bits_cond; // part of conds containing special bita
1407 TABLE_LIST *tables_list; ///<hold 'tables' parameter of mysql_select
1408 List<TABLE_LIST> *join_list; ///< list of joined tables in reverse order
1409 COND_EQUAL *cond_equal;
1410 COND_EQUAL *having_equal;
1411 /*
1412 Constant codition computed during optimization, but evaluated during
1413 join execution. Typically expensive conditions that should not be
1414 evaluated at optimization time.
1415 */
1416 Item *exec_const_cond;
1417 /*
1418 Constant ORDER and/or GROUP expressions that contain subqueries. Such
1419 expressions need to evaluated to verify that the subquery indeed
1420 returns a single row. The evaluation of such expressions is delayed
1421 until query execution.
1422 */
1423 List<Item> exec_const_order_group_cond;
1424 SQL_SELECT *select; ///<created in optimisation phase
1425 JOIN_TAB *return_tab; ///<used only for outer joins
1426
1427 /*
1428 Used pointer reference for this select.
1429 select_lex->ref_pointer_array contains five "slices" of the same length:
1430 |========|========|========|========|========|
1431 ref_ptrs items0 items1 items2 items3
1432 */
1433 Ref_ptr_array ref_ptrs;
1434 // Copy of the initial slice above, to be used with different lists
1435 Ref_ptr_array items0, items1, items2, items3;
1436 // Used by rollup, to restore ref_ptrs after overwriting it.
1437 Ref_ptr_array current_ref_ptrs;
1438
1439 const char *zero_result_cause; ///< not 0 if exec must return zero result
1440
1441 bool union_part; ///< this subselect is part of union
1442
1443 enum join_optimization_state { NOT_OPTIMIZED=0,
1444 OPTIMIZATION_IN_PROGRESS=1,
1445 OPTIMIZATION_PHASE_1_DONE=2,
1446 OPTIMIZATION_DONE=3};
1447 // state of JOIN optimization
1448 enum join_optimization_state optimization_state;
1449 bool initialized; ///< flag to avoid double init_execution calls
1450
1451 Explain_select *explain;
1452
1453 enum { QEP_NOT_PRESENT_YET, QEP_AVAILABLE, QEP_DELETED} have_query_plan;
1454
1455 // if keep_current_rowid=true, whether they should be saved in temporary table
1456 bool tmp_table_keep_current_rowid;
1457
1458 /*
1459 Additional WHERE and HAVING predicates to be considered for IN=>EXISTS
1460 subquery transformation of a JOIN object.
1461 */
1462 Item *in_to_exists_where;
1463 Item *in_to_exists_having;
1464
1465 /* Temporary tables used to weed-out semi-join duplicates */
1466 List<TABLE> sj_tmp_tables;
1467 /* SJM nests that are executed with SJ-Materialization strategy */
1468 List<SJ_MATERIALIZATION_INFO> sjm_info_list;
1469
1470 /** TRUE <=> ref_pointer_array is set to items3. */
1471 bool set_group_rpa;
1472 /** Exec time only: TRUE <=> current group has been sent */
1473 bool group_sent;
1474 /**
1475 TRUE if the query contains an aggregate function but has no GROUP
1476 BY clause.
1477 */
1478 bool implicit_grouping;
1479
1480 bool with_two_phase_optimization;
1481
1482 /* Saved execution plan for this join */
1483 Join_plan_state *save_qep;
1484 /* Info on splittability of the table materialized by this plan*/
1485 SplM_opt_info *spl_opt_info;
1486 /* Contains info on keyuses usable for splitting */
1487 Dynamic_array<KEYUSE_EXT> *ext_keyuses_for_splitting;
1488
1489 JOIN_TAB *sort_and_group_aggr_tab;
1490
JOIN(THD * thd_arg,List<Item> & fields_arg,ulonglong select_options_arg,select_result * result_arg)1491 JOIN(THD *thd_arg, List<Item> &fields_arg, ulonglong select_options_arg,
1492 select_result *result_arg)
1493 :fields_list(fields_arg)
1494 {
1495 init(thd_arg, fields_arg, select_options_arg, result_arg);
1496 }
1497
init(THD * thd_arg,List<Item> & fields_arg,ulonglong select_options_arg,select_result * result_arg)1498 void init(THD *thd_arg, List<Item> &fields_arg, ulonglong select_options_arg,
1499 select_result *result_arg)
1500 {
1501 join_tab= 0;
1502 table= 0;
1503 table_count= 0;
1504 top_join_tab_count= 0;
1505 const_tables= 0;
1506 const_table_map= found_const_table_map= 0;
1507 aggr_tables= 0;
1508 eliminated_tables= 0;
1509 join_list= 0;
1510 implicit_grouping= FALSE;
1511 sort_and_group= 0;
1512 first_record= 0;
1513 do_send_rows= 1;
1514 duplicate_rows= send_records= 0;
1515 found_records= 0;
1516 fetch_limit= HA_POS_ERROR;
1517 thd= thd_arg;
1518 sum_funcs= sum_funcs2= 0;
1519 procedure= 0;
1520 having= tmp_having= having_history= 0;
1521 having_is_correlated= false;
1522 group_list_for_estimates= 0;
1523 select_options= select_options_arg;
1524 result= result_arg;
1525 lock= thd_arg->lock;
1526 select_lex= 0; //for safety
1527 select_distinct= MY_TEST(select_options & SELECT_DISTINCT);
1528 no_order= 0;
1529 simple_order= 0;
1530 simple_group= 0;
1531 ordered_index_usage= ordered_index_void;
1532 need_distinct= 0;
1533 skip_sort_order= 0;
1534 with_two_phase_optimization= 0;
1535 save_qep= 0;
1536 spl_opt_info= 0;
1537 ext_keyuses_for_splitting= 0;
1538 spl_opt_info= 0;
1539 need_tmp= 0;
1540 hidden_group_fields= 0; /*safety*/
1541 error= 0;
1542 select= 0;
1543 return_tab= 0;
1544 ref_ptrs.reset();
1545 items0.reset();
1546 items1.reset();
1547 items2.reset();
1548 items3.reset();
1549 zero_result_cause= 0;
1550 optimization_state= JOIN::NOT_OPTIMIZED;
1551 have_query_plan= QEP_NOT_PRESENT_YET;
1552 initialized= 0;
1553 cleaned= 0;
1554 cond_equal= 0;
1555 having_equal= 0;
1556 exec_const_cond= 0;
1557 group_optimized_away= 0;
1558 no_rows_in_result_called= 0;
1559 positions= best_positions= 0;
1560 pushdown_query= 0;
1561 original_join_tab= 0;
1562 explain= NULL;
1563 tmp_table_keep_current_rowid= 0;
1564
1565 all_fields= fields_arg;
1566 if (&fields_list != &fields_arg) /* Avoid valgrind-warning */
1567 fields_list= fields_arg;
1568 non_agg_fields.empty();
1569 bzero((char*) &keyuse,sizeof(keyuse));
1570 tmp_table_param.init();
1571 tmp_table_param.end_write_records= HA_POS_ERROR;
1572 rollup.state= ROLLUP::STATE_NONE;
1573
1574 no_const_tables= FALSE;
1575 first_select= sub_select;
1576 set_group_rpa= false;
1577 group_sent= 0;
1578
1579 outer_ref_cond= pseudo_bits_cond= NULL;
1580 in_to_exists_where= NULL;
1581 in_to_exists_having= NULL;
1582 emb_sjm_nest= NULL;
1583 sjm_lookup_tables= 0;
1584 sjm_scan_tables= 0;
1585 }
1586
1587 /* True if the plan guarantees that it will be returned zero or one row */
only_const_tables()1588 bool only_const_tables() { return const_tables == table_count; }
1589 /* Number of tables actually joined at the top level */
exec_join_tab_cnt()1590 uint exec_join_tab_cnt() { return tables_list ? top_join_tab_count : 0; }
1591
1592 /*
1593 Number of tables in the join which also includes the temporary tables
1594 created for GROUP BY, DISTINCT , WINDOW FUNCTION etc.
1595 */
total_join_tab_cnt()1596 uint total_join_tab_cnt()
1597 {
1598 return exec_join_tab_cnt() + aggr_tables - 1;
1599 }
1600
1601 int prepare(TABLE_LIST *tables, uint wind_num,
1602 COND *conds, uint og_num, ORDER *order, bool skip_order_by,
1603 ORDER *group, Item *having, ORDER *proc_param, SELECT_LEX *select,
1604 SELECT_LEX_UNIT *unit);
1605 bool prepare_stage2();
1606 int optimize();
1607 int optimize_inner();
1608 int optimize_stage2();
1609 bool build_explain();
1610 int reinit();
1611 int init_execution();
1612 void exec();
1613
1614 void exec_inner();
1615 bool prepare_result(List<Item> **columns_list);
1616 int destroy();
1617 void restore_tmp();
1618 bool alloc_func_list();
1619 bool flatten_subqueries();
1620 bool optimize_unflattened_subqueries();
1621 bool optimize_constant_subqueries();
1622 int init_join_caches();
1623 bool make_sum_func_list(List<Item> &all_fields, List<Item> &send_fields,
1624 bool before_group_by, bool recompute= FALSE);
1625
1626 /// Initialzes a slice, see comments for ref_ptrs above.
ref_ptr_array_slice(size_t slice_num)1627 Ref_ptr_array ref_ptr_array_slice(size_t slice_num)
1628 {
1629 size_t slice_sz= select_lex->ref_pointer_array.size() / 5U;
1630 DBUG_ASSERT(select_lex->ref_pointer_array.size() % 5 == 0);
1631 DBUG_ASSERT(slice_num < 5U);
1632 return Ref_ptr_array(&select_lex->ref_pointer_array[slice_num * slice_sz],
1633 slice_sz);
1634 }
1635
1636 /**
1637 Overwrites one slice with the contents of another slice.
1638 In the normal case, dst and src have the same size().
1639 However: the rollup slices may have smaller size than slice_sz.
1640 */
copy_ref_ptr_array(Ref_ptr_array dst_arr,Ref_ptr_array src_arr)1641 void copy_ref_ptr_array(Ref_ptr_array dst_arr, Ref_ptr_array src_arr)
1642 {
1643 DBUG_ASSERT(dst_arr.size() >= src_arr.size());
1644 if (src_arr.size() == 0)
1645 return;
1646
1647 void *dest= dst_arr.array();
1648 const void *src= src_arr.array();
1649 memcpy(dest, src, src_arr.size() * src_arr.element_size());
1650 }
1651
1652 /// Overwrites 'ref_ptrs' and remembers the the source as 'current'.
set_items_ref_array(Ref_ptr_array src_arr)1653 void set_items_ref_array(Ref_ptr_array src_arr)
1654 {
1655 copy_ref_ptr_array(ref_ptrs, src_arr);
1656 current_ref_ptrs= src_arr;
1657 }
1658
1659 /// Initializes 'items0' and remembers that it is 'current'.
init_items_ref_array()1660 void init_items_ref_array()
1661 {
1662 items0= ref_ptr_array_slice(1);
1663 copy_ref_ptr_array(items0, ref_ptrs);
1664 current_ref_ptrs= items0;
1665 }
1666
1667 bool rollup_init();
1668 bool rollup_process_const_fields();
1669 bool rollup_make_fields(List<Item> &all_fields, List<Item> &fields,
1670 Item_sum ***func);
1671 int rollup_send_data(uint idx);
1672 int rollup_write_data(uint idx, TMP_TABLE_PARAM *tmp_table_param, TABLE *table);
1673 void join_free();
1674 /** Cleanup this JOIN, possibly for reuse */
1675 void cleanup(bool full);
1676 void clear();
send_row_on_empty_set()1677 bool send_row_on_empty_set()
1678 {
1679 return (do_send_rows && implicit_grouping && !group_optimized_away &&
1680 having_value != Item::COND_FALSE);
1681 }
empty_result()1682 bool empty_result() { return (zero_result_cause && !implicit_grouping); }
1683 bool change_result(select_result *new_result, select_result *old_result);
is_top_level_join()1684 bool is_top_level_join() const
1685 {
1686 return (unit == &thd->lex->unit && (unit->fake_select_lex == 0 ||
1687 select_lex == unit->fake_select_lex));
1688 }
1689 void cache_const_exprs();
all_tables_map()1690 inline table_map all_tables_map()
1691 {
1692 return (table_map(1) << table_count) - 1;
1693 }
1694 void drop_unused_derived_keys();
1695 bool get_best_combination();
1696 bool add_sorting_to_table(JOIN_TAB *tab, ORDER *order);
1697 inline void eval_select_list_used_tables();
1698 /*
1699 Return the table for which an index scan can be used to satisfy
1700 the sort order needed by the ORDER BY/(implicit) GROUP BY clause
1701 */
get_sort_by_join_tab()1702 JOIN_TAB *get_sort_by_join_tab()
1703 {
1704 return (need_tmp || !sort_by_table || skip_sort_order ||
1705 ((group || tmp_table_param.sum_func_count) && !group_list)) ?
1706 NULL : join_tab+const_tables;
1707 }
1708 bool setup_subquery_caches();
1709 bool shrink_join_buffers(JOIN_TAB *jt,
1710 ulonglong curr_space,
1711 ulonglong needed_space);
1712 void set_allowed_join_cache_types();
is_allowed_hash_join_access()1713 bool is_allowed_hash_join_access()
1714 {
1715 return MY_TEST(allowed_join_cache_types & JOIN_CACHE_HASHED_BIT) &&
1716 max_allowed_join_cache_level > JOIN_CACHE_HASHED_BIT;
1717 }
1718 /*
1719 Check if we need to create a temporary table.
1720 This has to be done if all tables are not already read (const tables)
1721 and one of the following conditions holds:
1722 - We are using DISTINCT (simple distinct's are already optimized away)
1723 - We are using an ORDER BY or GROUP BY on fields not in the first table
1724 - We are using different ORDER BY and GROUP BY orders
1725 - The user wants us to buffer the result.
1726 - We are using WINDOW functions.
1727 When the WITH ROLLUP modifier is present, we cannot skip temporary table
1728 creation for the DISTINCT clause just because there are only const tables.
1729 */
test_if_need_tmp_table()1730 bool test_if_need_tmp_table()
1731 {
1732 return ((const_tables != table_count &&
1733 ((select_distinct || !simple_order || !simple_group) ||
1734 (group_list && order) ||
1735 MY_TEST(select_options & OPTION_BUFFER_RESULT))) ||
1736 (rollup.state != ROLLUP::STATE_NONE && select_distinct) ||
1737 select_lex->have_window_funcs());
1738 }
1739 bool choose_subquery_plan(table_map join_tables);
1740 void get_partial_cost_and_fanout(int end_tab_idx,
1741 table_map filter_map,
1742 double *read_time_arg,
1743 double *record_count_arg);
1744 void get_prefix_cost_and_fanout(uint n_tables,
1745 double *read_time_arg,
1746 double *record_count_arg);
1747 double get_examined_rows();
1748 /* defined in opt_subselect.cc */
1749 bool transform_max_min_subquery();
1750 /* True if this JOIN is a subquery under an IN predicate. */
is_in_subquery()1751 bool is_in_subquery()
1752 {
1753 return (unit->item && unit->item->is_in_predicate());
1754 }
1755 bool save_explain_data(Explain_query *output, bool can_overwrite,
1756 bool need_tmp_table, bool need_order, bool distinct);
1757 int save_explain_data_intern(Explain_query *output, bool need_tmp_table,
1758 bool need_order, bool distinct,
1759 const char *message);
first_breadth_first_tab()1760 JOIN_TAB *first_breadth_first_tab() { return join_tab; }
1761 bool check_two_phase_optimization(THD *thd);
1762 bool inject_cond_into_where(Item *injected_cond);
1763 bool check_for_splittable_materialized();
1764 void add_keyuses_for_splitting();
1765 bool inject_best_splitting_cond(table_map remaining_tables);
1766 bool fix_all_splittings_in_plan();
1767 bool inject_splitting_cond_for_all_tables_with_split_opt();
1768
1769 bool transform_in_predicates_into_in_subq(THD *thd);
1770 private:
1771 /**
1772 Create a temporary table to be used for processing DISTINCT/ORDER
1773 BY/GROUP BY.
1774
1775 @note Will modify JOIN object wrt sort/group attributes
1776
1777 @param tab the JOIN_TAB object to attach created table to
1778 @param tmp_table_fields List of items that will be used to define
1779 column types of the table.
1780 @param tmp_table_group Group key to use for temporary table, NULL if none.
1781 @param save_sum_fields If true, do not replace Item_sum items in
1782 @c tmp_fields list with Item_field items referring
1783 to fields in temporary table.
1784
1785 @returns false on success, true on failure
1786 */
1787 bool create_postjoin_aggr_table(JOIN_TAB *tab, List<Item> *tmp_table_fields,
1788 ORDER *tmp_table_group,
1789 bool save_sum_fields,
1790 bool distinct,
1791 bool keep_row_ordermake);
1792 /**
1793 Optimize distinct when used on a subset of the tables.
1794
1795 E.g.,: SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
1796 In this case we can stop scanning t2 when we have found one t1.a
1797 */
1798 void optimize_distinct();
1799
1800 void cleanup_item_list(List<Item> &items) const;
1801 bool add_having_as_table_cond(JOIN_TAB *tab);
1802 bool make_aggr_tables_info();
1803 bool add_fields_for_current_rowid(JOIN_TAB *cur, List<Item> *fields);
1804 };
1805
1806 enum enum_with_bush_roots { WITH_BUSH_ROOTS, WITHOUT_BUSH_ROOTS};
1807 enum enum_with_const_tables { WITH_CONST_TABLES, WITHOUT_CONST_TABLES};
1808
1809 JOIN_TAB *first_linear_tab(JOIN *join,
1810 enum enum_with_bush_roots include_bush_roots,
1811 enum enum_with_const_tables const_tbls);
1812 JOIN_TAB *next_linear_tab(JOIN* join, JOIN_TAB* tab,
1813 enum enum_with_bush_roots include_bush_roots);
1814
1815 JOIN_TAB *first_top_level_tab(JOIN *join, enum enum_with_const_tables with_const);
1816 JOIN_TAB *next_top_level_tab(JOIN *join, JOIN_TAB *tab);
1817
1818 typedef struct st_select_check {
1819 uint const_ref,reg_ref;
1820 } SELECT_CHECK;
1821
1822 extern const char *join_type_str[];
1823
1824 /* Extern functions in sql_select.cc */
1825 void count_field_types(SELECT_LEX *select_lex, TMP_TABLE_PARAM *param,
1826 List<Item> &fields, bool reset_with_sum_func);
1827 bool setup_copy_fields(THD *thd, TMP_TABLE_PARAM *param,
1828 Ref_ptr_array ref_pointer_array,
1829 List<Item> &new_list1, List<Item> &new_list2,
1830 uint elements, List<Item> &fields);
1831 void copy_fields(TMP_TABLE_PARAM *param);
1832 bool copy_funcs(Item **func_ptr, const THD *thd);
1833 uint find_shortest_key(TABLE *table, const key_map *usable_keys);
1834 Field* create_tmp_field_from_field(THD *thd, Field* org_field,
1835 LEX_CSTRING *name, TABLE *table,
1836 Item_field *item);
1837
1838 bool is_indexed_agg_distinct(JOIN *join, List<Item_field> *out_args);
1839
1840 /* functions from opt_sum.cc */
1841 bool simple_pred(Item_func *func_item, Item **args, bool *inv_order);
1842 int opt_sum_query(THD* thd,
1843 List<TABLE_LIST> &tables, List<Item> &all_fields, COND *conds);
1844
1845 /* from sql_delete.cc, used by opt_range.cc */
1846 extern "C" int refpos_order_cmp(void* arg, const void *a,const void *b);
1847
1848 /** class to copying an field/item to a key struct */
1849
1850 class store_key :public Sql_alloc
1851 {
1852 public:
1853 bool null_key; /* TRUE <=> the value of the key has a null part */
1854 enum store_key_result { STORE_KEY_OK, STORE_KEY_FATAL, STORE_KEY_CONV };
1855 enum Type { FIELD_STORE_KEY, ITEM_STORE_KEY, CONST_ITEM_STORE_KEY };
store_key(THD * thd,Field * field_arg,uchar * ptr,uchar * null,uint length)1856 store_key(THD *thd, Field *field_arg, uchar *ptr, uchar *null, uint length)
1857 :null_key(0), null_ptr(null), err(0)
1858 {
1859 to_field=field_arg->new_key_field(thd->mem_root, field_arg->table,
1860 ptr, length, null, 1);
1861 }
store_key(store_key & arg)1862 store_key(store_key &arg)
1863 :Sql_alloc(), null_key(arg.null_key), to_field(arg.to_field),
1864 null_ptr(arg.null_ptr), err(arg.err)
1865
1866 {}
~store_key()1867 virtual ~store_key() {} /** Not actually needed */
1868 virtual enum Type type() const=0;
1869 virtual const char *name() const=0;
store_key_is_const()1870 virtual bool store_key_is_const() { return false; }
1871
1872 /**
1873 @brief sets ignore truncation warnings mode and calls the real copy method
1874
1875 @details this function makes sure truncation warnings when preparing the
1876 key buffers don't end up as errors (because of an enclosing INSERT/UPDATE).
1877 */
copy()1878 enum store_key_result copy()
1879 {
1880 enum store_key_result result;
1881 THD *thd= to_field->table->in_use;
1882 Check_level_instant_set check_level_save(thd, CHECK_FIELD_IGNORE);
1883 Sql_mode_save sql_mode(thd);
1884 thd->variables.sql_mode&= ~(MODE_NO_ZERO_IN_DATE | MODE_NO_ZERO_DATE);
1885 thd->variables.sql_mode|= MODE_INVALID_DATES;
1886 result= copy_inner();
1887 return result;
1888 }
1889
1890 protected:
1891 Field *to_field; // Store data here
1892 uchar *null_ptr;
1893 uchar err;
1894
1895 virtual enum store_key_result copy_inner()=0;
1896 };
1897
1898
1899 class store_key_field: public store_key
1900 {
1901 Copy_field copy_field;
1902 const char *field_name;
1903 public:
store_key_field(THD * thd,Field * to_field_arg,uchar * ptr,uchar * null_ptr_arg,uint length,Field * from_field,const char * name_arg)1904 store_key_field(THD *thd, Field *to_field_arg, uchar *ptr,
1905 uchar *null_ptr_arg,
1906 uint length, Field *from_field, const char *name_arg)
1907 :store_key(thd, to_field_arg,ptr,
1908 null_ptr_arg ? null_ptr_arg : from_field->maybe_null() ? &err
1909 : (uchar*) 0, length), field_name(name_arg)
1910 {
1911 if (to_field)
1912 {
1913 copy_field.set(to_field,from_field,0);
1914 }
1915 }
1916
type()1917 enum Type type() const { return FIELD_STORE_KEY; }
name()1918 const char *name() const { return field_name; }
1919
change_source_field(Item_field * fld_item)1920 void change_source_field(Item_field *fld_item)
1921 {
1922 copy_field.set(to_field, fld_item->field, 0);
1923 field_name= fld_item->full_name();
1924 }
1925
1926 protected:
copy_inner()1927 enum store_key_result copy_inner()
1928 {
1929 TABLE *table= copy_field.to_field->table;
1930 MY_BITMAP *old_map= dbug_tmp_use_all_columns(table,
1931 &table->write_set);
1932
1933 /*
1934 It looks like the next statement is needed only for a simplified
1935 hash function over key values used now in BNLH join.
1936 When the implementation of this function will be replaced for a proper
1937 full version this statement probably should be removed.
1938 */
1939 bzero(copy_field.to_ptr,copy_field.to_length);
1940
1941 copy_field.do_copy(©_field);
1942 dbug_tmp_restore_column_map(&table->write_set, old_map);
1943 null_key= to_field->is_null();
1944 return err != 0 ? STORE_KEY_FATAL : STORE_KEY_OK;
1945 }
1946 };
1947
1948
1949 class store_key_item :public store_key
1950 {
1951 protected:
1952 Item *item;
1953 /*
1954 Flag that forces usage of save_val() method which save value of the
1955 item instead of save_in_field() method which saves result.
1956 */
1957 bool use_value;
1958 public:
store_key_item(THD * thd,Field * to_field_arg,uchar * ptr,uchar * null_ptr_arg,uint length,Item * item_arg,bool val)1959 store_key_item(THD *thd, Field *to_field_arg, uchar *ptr,
1960 uchar *null_ptr_arg, uint length, Item *item_arg, bool val)
1961 :store_key(thd, to_field_arg, ptr,
1962 null_ptr_arg ? null_ptr_arg : item_arg->maybe_null ?
1963 &err : (uchar*) 0, length), item(item_arg), use_value(val)
1964 {}
store_key_item(store_key & arg,Item * new_item,bool val)1965 store_key_item(store_key &arg, Item *new_item, bool val)
1966 :store_key(arg), item(new_item), use_value(val)
1967 {}
1968
1969
type()1970 enum Type type() const { return ITEM_STORE_KEY; }
name()1971 const char *name() const { return "func"; }
1972
1973 protected:
copy_inner()1974 enum store_key_result copy_inner()
1975 {
1976 TABLE *table= to_field->table;
1977 MY_BITMAP *old_map= dbug_tmp_use_all_columns(table,
1978 &table->write_set);
1979 int res= FALSE;
1980
1981 /*
1982 It looks like the next statement is needed only for a simplified
1983 hash function over key values used now in BNLH join.
1984 When the implementation of this function will be replaced for a proper
1985 full version this statement probably should be removed.
1986 */
1987 to_field->reset();
1988
1989 if (use_value)
1990 item->save_val(to_field);
1991 else
1992 res= item->save_in_field(to_field, 1);
1993 /*
1994 Item::save_in_field() may call Item::val_xxx(). And if this is a subquery
1995 we need to check for errors executing it and react accordingly
1996 */
1997 if (!res && table->in_use->is_error())
1998 res= 1; /* STORE_KEY_FATAL */
1999 dbug_tmp_restore_column_map(&table->write_set, old_map);
2000 null_key= to_field->is_null() || item->null_value;
2001 return ((err != 0 || res < 0 || res > 2) ? STORE_KEY_FATAL :
2002 (store_key_result) res);
2003 }
2004 };
2005
2006
2007 class store_key_const_item :public store_key_item
2008 {
2009 bool inited;
2010 public:
store_key_const_item(THD * thd,Field * to_field_arg,uchar * ptr,uchar * null_ptr_arg,uint length,Item * item_arg)2011 store_key_const_item(THD *thd, Field *to_field_arg, uchar *ptr,
2012 uchar *null_ptr_arg, uint length,
2013 Item *item_arg)
2014 :store_key_item(thd, to_field_arg, ptr,
2015 null_ptr_arg ? null_ptr_arg : item_arg->maybe_null ?
2016 &err : (uchar*) 0, length, item_arg, FALSE), inited(0)
2017 {
2018 }
store_key_const_item(store_key & arg,Item * new_item)2019 store_key_const_item(store_key &arg, Item *new_item)
2020 :store_key_item(arg, new_item, FALSE), inited(0)
2021 {}
2022
type()2023 enum Type type() const { return CONST_ITEM_STORE_KEY; }
name()2024 const char *name() const { return "const"; }
store_key_is_const()2025 bool store_key_is_const() { return true; }
2026
2027 protected:
copy_inner()2028 enum store_key_result copy_inner()
2029 {
2030 int res;
2031 if (!inited)
2032 {
2033 inited=1;
2034 TABLE *table= to_field->table;
2035 MY_BITMAP *old_map= dbug_tmp_use_all_columns(table,
2036 &table->write_set);
2037 if ((res= item->save_in_field(to_field, 1)))
2038 {
2039 if (!err)
2040 err= res < 0 ? 1 : res; /* 1=STORE_KEY_FATAL */
2041 }
2042 /*
2043 Item::save_in_field() may call Item::val_xxx(). And if this is a subquery
2044 we need to check for errors executing it and react accordingly
2045 */
2046 if (!err && to_field->table->in_use->is_error())
2047 err= 1; /* STORE_KEY_FATAL */
2048 dbug_tmp_restore_column_map(&table->write_set, old_map);
2049 }
2050 null_key= to_field->is_null() || item->null_value;
2051 return (err > 2 ? STORE_KEY_FATAL : (store_key_result) err);
2052 }
2053 };
2054
2055 void best_access_path(JOIN *join, JOIN_TAB *s,
2056 table_map remaining_tables,
2057 const POSITION *join_positions, uint idx,
2058 bool disable_jbuf, double record_count,
2059 POSITION *pos, POSITION *loose_scan_pos);
2060 bool cp_buffer_from_ref(THD *thd, TABLE *table, TABLE_REF *ref);
2061 bool error_if_full_join(JOIN *join);
2062 int report_error(TABLE *table, int error);
2063 int safe_index_read(JOIN_TAB *tab);
2064 int get_quick_record(SQL_SELECT *select);
2065 int setup_order(THD *thd, Ref_ptr_array ref_pointer_array, TABLE_LIST *tables,
2066 List<Item> &fields, List <Item> &all_fields, ORDER *order,
2067 bool from_window_spec= false);
2068 int setup_group(THD *thd, Ref_ptr_array ref_pointer_array, TABLE_LIST *tables,
2069 List<Item> &fields, List<Item> &all_fields, ORDER *order,
2070 bool *hidden_group_fields, bool from_window_spec= false);
2071 bool fix_inner_refs(THD *thd, List<Item> &all_fields, SELECT_LEX *select,
2072 Ref_ptr_array ref_pointer_array);
2073 int join_read_key2(THD *thd, struct st_join_table *tab, TABLE *table,
2074 struct st_table_ref *table_ref);
2075
2076 bool handle_select(THD *thd, LEX *lex, select_result *result,
2077 ulong setup_tables_done_option);
2078 bool mysql_select(THD *thd,
2079 TABLE_LIST *tables, uint wild_num, List<Item> &list,
2080 COND *conds, uint og_num, ORDER *order, ORDER *group,
2081 Item *having, ORDER *proc_param, ulonglong select_type,
2082 select_result *result, SELECT_LEX_UNIT *unit,
2083 SELECT_LEX *select_lex);
2084 void free_underlaid_joins(THD *thd, SELECT_LEX *select);
2085 bool mysql_explain_union(THD *thd, SELECT_LEX_UNIT *unit,
2086 select_result *result);
2087 Field *create_tmp_field(THD *thd, TABLE *table,Item *item, Item::Type type,
2088 Item ***copy_func, Field **from_field,
2089 Field **def_field,
2090 bool group, bool modify_item,
2091 bool table_cant_handle_bit_fields,
2092 bool make_copy_field);
2093
2094 /*
2095 General routine to change field->ptr of a NULL-terminated array of Field
2096 objects. Useful when needed to call val_int, val_str or similar and the
2097 field data is not in table->record[0] but in some other structure.
2098 set_key_field_ptr changes all fields of an index using a key_info object.
2099 All methods presume that there is at least one field to change.
2100 */
2101
2102
2103 class Virtual_tmp_table: public TABLE
2104 {
2105 /**
2106 Destruct collected fields. This method can be called on errors,
2107 when we could not make the virtual temporary table completely,
2108 e.g. when some of the fields could not be created or added.
2109
2110 This is needed to avoid memory leaks, as some fields can be BLOB
2111 variants and thus can have String onboard. Strings must be destructed
2112 as they store data on the heap (not on MEM_ROOT).
2113 */
destruct_fields()2114 void destruct_fields()
2115 {
2116 for (uint i= 0; i < s->fields; i++)
2117 {
2118 field[i]->free();
2119 delete field[i]; // to invoke the field destructor
2120 }
2121 s->fields= 0; // safety
2122 }
2123
2124 protected:
2125 /**
2126 The number of the fields that are going to be in the table.
2127 We remember the number of the fields at init() time, and
2128 at open() we check that all of the fields were really added.
2129 */
2130 uint m_alloced_field_count;
2131
2132 /**
2133 Setup field pointers and null-bit pointers.
2134 */
2135 void setup_field_pointers();
2136
2137 public:
2138 /**
2139 Create a new empty virtual temporary table on the thread mem_root.
2140 After creation, the caller must:
2141 - call init()
2142 - populate the table with new fields using add().
2143 - call open().
2144 @param thd - Current thread.
2145 */
2146 static void *operator new(size_t size, THD *thd) throw();
delete(void * ptr,size_t size)2147 static void operator delete(void *ptr, size_t size) { TRASH_FREE(ptr, size); }
delete(void *,THD *)2148 static void operator delete(void *, THD *) throw(){}
2149
Virtual_tmp_table(THD * thd)2150 Virtual_tmp_table(THD *thd) : m_alloced_field_count(0)
2151 {
2152 reset();
2153 temp_pool_slot= MY_BIT_NONE;
2154 in_use= thd;
2155 copy_blobs= true;
2156 alias.set("", 0, &my_charset_bin);
2157 }
2158
~Virtual_tmp_table()2159 ~Virtual_tmp_table()
2160 {
2161 if (s)
2162 destruct_fields();
2163 }
2164
2165 /**
2166 Allocate components for the given number of fields.
2167 - fields[]
2168 - s->blob_fields[],
2169 - bitmaps: def_read_set, def_write_set, tmp_set, eq_join_set, cond_set.
2170 @param field_count - The number of fields we plan to add to the table.
2171 @returns false - on success.
2172 @returns true - on error.
2173 */
2174 bool init(uint field_count);
2175
2176 /**
2177 Add one Field to the end of the field array, update members:
2178 s->reclength, s->fields, s->blob_fields, s->null_fuelds.
2179 */
add(Field * new_field)2180 bool add(Field *new_field)
2181 {
2182 DBUG_ASSERT(s->fields < m_alloced_field_count);
2183 new_field->init(this);
2184 field[s->fields]= new_field;
2185 s->reclength+= new_field->pack_length();
2186 if (!(new_field->flags & NOT_NULL_FLAG))
2187 s->null_fields++;
2188 if (new_field->flags & BLOB_FLAG)
2189 {
2190 // Note, s->blob_fields was incremented in Field_blob::Field_blob
2191 DBUG_ASSERT(s->blob_fields);
2192 DBUG_ASSERT(s->blob_fields <= m_alloced_field_count);
2193 s->blob_field[s->blob_fields - 1]= s->fields;
2194 }
2195 new_field->field_index= s->fields++;
2196 return false;
2197 }
2198
2199 /**
2200 Add fields from a Spvar_definition list
2201 @returns false - on success.
2202 @returns true - on error.
2203 */
2204 bool add(List<Spvar_definition> &field_list);
2205
2206 /**
2207 Open a virtual table for read/write:
2208 - Setup end markers in TABLE::field and TABLE_SHARE::blob_fields,
2209 - Allocate a buffer in TABLE::record[0].
2210 - Set field pointers (Field::ptr, Field::null_pos, Field::null_bit) to
2211 the allocated record.
2212 This method is called when all of the fields have been added to the table.
2213 After calling this method the table is ready for read and write operations.
2214 @return false - on success
2215 @return true - on error (e.g. could not allocate the record buffer).
2216 */
2217 bool open();
2218
set_all_fields_to_null()2219 void set_all_fields_to_null()
2220 {
2221 for (uint i= 0; i < s->fields; i++)
2222 field[i]->set_null();
2223 }
2224 /**
2225 Set all fields from a compatible item list.
2226 The number of fields in "this" must be equal to the number
2227 of elements in "value".
2228 */
2229 bool sp_set_all_fields_from_item_list(THD *thd, List<Item> &items);
2230
2231 /**
2232 Set all fields from a compatible item.
2233 The number of fields in "this" must be the same with the number
2234 of elements in "value".
2235 */
2236 bool sp_set_all_fields_from_item(THD *thd, Item *value);
2237
2238 /**
2239 Find a ROW element index by its name
2240 Assumes that "this" is used as a storage for a ROW-type SP variable.
2241 @param [OUT] idx - the index of the found field is returned here
2242 @param [IN] field_name - find a field with this name
2243 @return true - on error (the field was not found)
2244 @return false - on success (idx[0] was set to the field index)
2245 */
2246 bool sp_find_field_by_name(uint *idx, const LEX_CSTRING &name) const;
2247
2248 /**
2249 Find a ROW element index by its name.
2250 If the element is not found, and error is issued.
2251 @param [OUT] idx - the index of the found field is returned here
2252 @param [IN] var_name - the name of the ROW variable (for error reporting)
2253 @param [IN] field_name - find a field with this name
2254 @return true - on error (the field was not found)
2255 @return false - on success (idx[0] was set to the field index)
2256 */
2257 bool sp_find_field_by_name_or_error(uint *idx,
2258 const LEX_CSTRING &var_name,
2259 const LEX_CSTRING &field_name) const;
2260 };
2261
2262
2263 /**
2264 Create a reduced TABLE object with properly set up Field list from a
2265 list of field definitions.
2266
2267 The created table doesn't have a table handler associated with
2268 it, has no keys, no group/distinct, no copy_funcs array.
2269 The sole purpose of this TABLE object is to use the power of Field
2270 class to read/write data to/from table->record[0]. Then one can store
2271 the record in any container (RB tree, hash, etc).
2272 The table is created in THD mem_root, so are the table's fields.
2273 Consequently, if you don't BLOB fields, you don't need to free it.
2274
2275 @param thd connection handle
2276 @param field_list list of column definitions
2277
2278 @return
2279 0 if out of memory, or a
2280 TABLE object ready for read and write in case of success
2281 */
2282
2283 inline Virtual_tmp_table *
create_virtual_tmp_table(THD * thd,List<Spvar_definition> & field_list)2284 create_virtual_tmp_table(THD *thd, List<Spvar_definition> &field_list)
2285 {
2286 Virtual_tmp_table *table;
2287 if (!(table= new(thd) Virtual_tmp_table(thd)))
2288 return NULL;
2289
2290 /*
2291 If "simulate_create_virtual_tmp_table_out_of_memory" debug option
2292 is enabled, we now enable "simulate_out_of_memory". This effectively
2293 makes table->init() fail on OOM inside multi_alloc_root().
2294 This is done to test that ~Virtual_tmp_table() called from the "delete"
2295 below correcly handles OOM.
2296 */
2297 DBUG_EXECUTE_IF("simulate_create_virtual_tmp_table_out_of_memory",
2298 DBUG_SET("+d,simulate_out_of_memory"););
2299
2300 if (table->init(field_list.elements) ||
2301 table->add(field_list) ||
2302 table->open())
2303 {
2304 delete table;
2305 return NULL;
2306 }
2307 return table;
2308 }
2309
2310
2311 /**
2312 Create a new virtual temporary table consisting of a single field.
2313 SUM(DISTINCT expr) and similar numeric aggregate functions use this.
2314 @param thd - Current thread
2315 @param field - The field that will be added into the table.
2316 @return NULL - On error.
2317 @return !NULL - A pointer to the created table that is ready
2318 for read and write.
2319 */
2320 inline TABLE *
create_virtual_tmp_table(THD * thd,Field * field)2321 create_virtual_tmp_table(THD *thd, Field *field)
2322 {
2323 Virtual_tmp_table *table;
2324 DBUG_ASSERT(field);
2325 if (!(table= new(thd) Virtual_tmp_table(thd)))
2326 return NULL;
2327 if (table->init(1) ||
2328 table->add(field) ||
2329 table->open())
2330 {
2331 delete table;
2332 return NULL;
2333 }
2334 return table;
2335 }
2336
2337
2338 int test_if_item_cache_changed(List<Cached_item> &list);
2339 int join_init_read_record(JOIN_TAB *tab);
2340 int join_read_record_no_init(JOIN_TAB *tab);
2341 void set_position(JOIN *join,uint idx,JOIN_TAB *table,KEYUSE *key);
and_items(THD * thd,Item * cond,Item * item)2342 inline Item * and_items(THD *thd, Item* cond, Item *item)
2343 {
2344 return (cond ? (new (thd->mem_root) Item_cond_and(thd, cond, item)) : item);
2345 }
or_items(THD * thd,Item * cond,Item * item)2346 inline Item * or_items(THD *thd, Item* cond, Item *item)
2347 {
2348 return (cond ? (new (thd->mem_root) Item_cond_or(thd, cond, item)) : item);
2349 }
2350 bool choose_plan(JOIN *join, table_map join_tables);
2351 void optimize_wo_join_buffering(JOIN *join, uint first_tab, uint last_tab,
2352 table_map last_remaining_tables,
2353 bool first_alt, uint no_jbuf_before,
2354 double *outer_rec_count, double *reopt_cost);
2355 Item_equal *find_item_equal(COND_EQUAL *cond_equal, Field *field,
2356 bool *inherited_fl);
2357 extern bool test_if_ref(Item *,
2358 Item_field *left_item,Item *right_item);
2359
optimizer_flag(THD * thd,uint flag)2360 inline bool optimizer_flag(THD *thd, uint flag)
2361 {
2362 return (thd->variables.optimizer_switch & flag);
2363 }
2364
2365 /*
2366 int print_fake_select_lex_join(select_result_sink *result, bool on_the_fly,
2367 SELECT_LEX *select_lex, uint8 select_options);
2368 */
2369
2370 uint get_index_for_order(ORDER *order, TABLE *table, SQL_SELECT *select,
2371 ha_rows limit, ha_rows *scanned_limit,
2372 bool *need_sort, bool *reverse);
2373 ORDER *simple_remove_const(ORDER *order, COND *where);
2374 bool const_expression_in_where(COND *cond, Item *comp_item,
2375 Field *comp_field= NULL,
2376 Item **const_item= NULL);
2377 bool cond_is_datetime_is_null(Item *cond);
2378 bool cond_has_datetime_is_null(Item *cond);
2379
2380 /* Table elimination entry point function */
2381 void eliminate_tables(JOIN *join);
2382
2383 /* Index Condition Pushdown entry point function */
2384 void push_index_cond(JOIN_TAB *tab, uint keyno);
2385
2386 #define OPT_LINK_EQUAL_FIELDS 1
2387
2388 /* EXPLAIN-related utility functions */
2389 int print_explain_message_line(select_result_sink *result,
2390 uint8 options, bool is_analyze,
2391 uint select_number,
2392 const char *select_type,
2393 ha_rows *rows,
2394 const char *message);
2395 void explain_append_mrr_info(QUICK_RANGE_SELECT *quick, String *res);
2396 int append_possible_keys(MEM_ROOT *alloc, String_list &list, TABLE *table,
2397 key_map possible_keys);
2398
2399 /****************************************************************************
2400 Temporary table support for SQL Runtime
2401 ***************************************************************************/
2402
2403 #define STRING_TOTAL_LENGTH_TO_PACK_ROWS 128
2404 #define AVG_STRING_LENGTH_TO_PACK_ROWS 64
2405 #define RATIO_TO_PACK_ROWS 2
2406 #define MIN_STRING_LENGTH_TO_PACK_ROWS 10
2407
2408 void calc_group_buffer(TMP_TABLE_PARAM *param, ORDER *group);
2409 TABLE *create_tmp_table(THD *thd,TMP_TABLE_PARAM *param,List<Item> &fields,
2410 ORDER *group, bool distinct, bool save_sum_fields,
2411 ulonglong select_options, ha_rows rows_limit,
2412 const LEX_CSTRING *alias, bool do_not_open=FALSE,
2413 bool keep_row_order= FALSE);
2414 void free_tmp_table(THD *thd, TABLE *entry);
2415 bool create_internal_tmp_table_from_heap(THD *thd, TABLE *table,
2416 TMP_ENGINE_COLUMNDEF *start_recinfo,
2417 TMP_ENGINE_COLUMNDEF **recinfo,
2418 int error, bool ignore_last_dupp_key_error,
2419 bool *is_duplicate);
2420 bool create_internal_tmp_table(TABLE *table, KEY *keyinfo,
2421 TMP_ENGINE_COLUMNDEF *start_recinfo,
2422 TMP_ENGINE_COLUMNDEF **recinfo,
2423 ulonglong options);
2424 bool instantiate_tmp_table(TABLE *table, KEY *keyinfo,
2425 TMP_ENGINE_COLUMNDEF *start_recinfo,
2426 TMP_ENGINE_COLUMNDEF **recinfo,
2427 ulonglong options);
2428 bool open_tmp_table(TABLE *table);
2429 void setup_tmp_table_column_bitmaps(TABLE *table, uchar *bitmaps);
2430 double prev_record_reads(const POSITION *positions, uint idx, table_map found_ref);
2431 void fix_list_after_tbl_changes(SELECT_LEX *new_parent, List<TABLE_LIST> *tlist);
2432 double get_tmp_table_lookup_cost(THD *thd, double row_count, uint row_size);
2433 double get_tmp_table_write_cost(THD *thd, double row_count, uint row_size);
2434 void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array);
2435 bool sort_and_filter_keyuse(THD *thd, DYNAMIC_ARRAY *keyuse,
2436 bool skip_unprefixed_keyparts);
2437
2438 struct st_cond_statistic
2439 {
2440 Item *cond;
2441 Field *field_arg;
2442 ulong positive;
2443 };
2444 typedef struct st_cond_statistic COND_STATISTIC;
2445
2446 ulong check_selectivity(THD *thd,
2447 ulong rows_to_read,
2448 TABLE *table,
2449 List<COND_STATISTIC> *conds);
2450
2451 class Pushdown_query: public Sql_alloc
2452 {
2453 public:
2454 SELECT_LEX *select_lex;
2455 bool store_data_in_temp_table;
2456 group_by_handler *handler;
2457 Item *having;
2458
Pushdown_query(SELECT_LEX * select_lex_arg,group_by_handler * handler_arg)2459 Pushdown_query(SELECT_LEX *select_lex_arg, group_by_handler *handler_arg)
2460 : select_lex(select_lex_arg), store_data_in_temp_table(0),
2461 handler(handler_arg), having(0) {}
2462
~Pushdown_query()2463 ~Pushdown_query() { delete handler; }
2464
2465 /* Function that calls the above scan functions */
2466 int execute(JOIN *join);
2467 };
2468
2469 bool test_if_order_compatible(SQL_I_List<ORDER> &a, SQL_I_List<ORDER> &b);
2470 int test_if_group_changed(List<Cached_item> &list);
2471 int create_sort_index(THD *thd, JOIN *join, JOIN_TAB *tab, Filesort *fsort);
2472
2473 JOIN_TAB *first_explain_order_tab(JOIN* join);
2474 JOIN_TAB *next_explain_order_tab(JOIN* join, JOIN_TAB* tab);
2475
2476 #endif /* SQL_SELECT_INCLUDED */
2477