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