12
12
You should have received a copy of the GNU General Public License
13
13
along with this program; if not, write to the Free Software
14
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
14
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
20
select_query and join optimization
20
mysql_select and join optimization
22
23
@defgroup Query_Optimizer Query Optimizer
26
#include <drizzled/server_includes.h>
27
#include <drizzled/sql_select.h>
28
#include <drizzled/sj_tmp_table.h>
29
#include <drizzled/table_map_iterator.h>
31
#include <mysys/my_bit.h>
32
#include <drizzled/error.h>
33
#include <drizzled/gettext.h>
34
#include <drizzled/util/test.h>
35
#include <drizzled/name_resolution_context_state.h>
36
#include <drizzled/nested_join.h>
37
#include <drizzled/probes.h>
38
#include <drizzled/show.h>
39
#include <drizzled/item/cache.h>
40
#include <drizzled/item/cmpfunc.h>
41
#include <drizzled/item/copy_string.h>
42
#include <drizzled/item/uint.h>
43
#include <drizzled/cached_item.h>
44
#include <drizzled/sql_base.h>
45
#include <drizzled/field/blob.h>
46
#include <drizzled/check_stack_overrun.h>
47
#include <drizzled/lock.h>
48
#include <drizzled/item/outer_ref.h>
32
#include "drizzled/sql_select.h" /* include join.h */
34
#include "drizzled/error.h"
35
#include "drizzled/gettext.h"
36
#include "drizzled/util/test.h"
37
#include "drizzled/name_resolution_context_state.h"
38
#include "drizzled/nested_join.h"
39
#include "drizzled/probes.h"
40
#include "drizzled/show.h"
41
#include "drizzled/item/cache.h"
42
#include "drizzled/item/cmpfunc.h"
43
#include "drizzled/item/copy_string.h"
44
#include "drizzled/item/uint.h"
45
#include "drizzled/cached_item.h"
46
#include "drizzled/sql_base.h"
47
#include "drizzled/field/blob.h"
48
#include "drizzled/check_stack_overrun.h"
49
#include "drizzled/lock.h"
50
#include "drizzled/item/outer_ref.h"
51
#include "drizzled/index_hint.h"
52
#include "drizzled/records.h"
53
#include "drizzled/internal/iocache.h"
54
#include "drizzled/drizzled.h"
55
#include "drizzled/plugin/storage_engine.h"
57
#include "drizzled/sql_union.h"
58
#include "drizzled/optimizer/key_field.h"
59
#include "drizzled/optimizer/position.h"
60
#include "drizzled/optimizer/sargable_param.h"
61
#include "drizzled/optimizer/key_use.h"
62
#include "drizzled/optimizer/range.h"
63
#include "drizzled/optimizer/quick_range_select.h"
64
#include "drizzled/optimizer/quick_ror_intersect_select.h"
66
#include "drizzled/filesort.h"
68
52
using namespace std;
73
static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b);
54
const char *join_type_str[]={ "UNKNOWN","system","const","eq_ref","ref",
55
"MAYBE_REF","ALL","range","index",
56
"ref_or_null","unique_subquery","index_subquery",
60
struct st_sargable_param;
62
static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array);
63
static bool make_join_statistics(JOIN *join, TableList *leaves, COND *conds,
64
DYNAMIC_ARRAY *keyuse);
65
static bool update_ref_and_keys(Session *session, DYNAMIC_ARRAY *keyuse,
67
uint32_t tables, COND *conds,
68
COND_EQUAL *cond_equal,
69
table_map table_map, Select_Lex *select_lex,
70
st_sargable_param **sargables);
71
static int sort_keyuse(KEYUSE *a,KEYUSE *b);
72
static void set_position(JOIN *join,uint32_t index,JOIN_TAB *table,KEYUSE *key);
73
static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
74
table_map used_tables);
75
static bool choose_plan(JOIN *join,table_map join_tables);
77
static void best_access_path(JOIN *join, JOIN_TAB *s, Session *session,
78
table_map remaining_tables, uint32_t idx,
79
double record_count, double read_time);
80
static void optimize_straight_join(JOIN *join, table_map join_tables);
81
static bool greedy_search(JOIN *join, table_map remaining_tables,
82
uint32_t depth, uint32_t prune_level);
83
static bool best_extension_by_limited_search(JOIN *join,
84
table_map remaining_tables,
85
uint32_t idx, double record_count,
86
double read_time, uint32_t depth,
87
uint32_t prune_level);
88
static uint32_t determine_search_depth(JOIN* join);
89
extern "C" int join_tab_cmp(const void* ptr1, const void* ptr2);
90
extern "C" int join_tab_cmp_straight(const void* ptr1, const void* ptr2);
92
TODO: 'find_best' is here only temporarily until 'greedy_search' is
95
static bool find_best(JOIN *join,table_map rest_tables,uint32_t index,
96
double record_count,double read_time);
97
static uint32_t cache_record_length(JOIN *join,uint32_t index);
98
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref);
99
static bool get_best_combination(JOIN *join);
100
static store_key *get_store_key(Session *session,
101
KEYUSE *keyuse, table_map used_tables,
102
KEY_PART_INFO *key_part, unsigned char *key_buff,
103
uint32_t maybe_null);
104
static bool make_simple_join(JOIN *join,Table *tmp_table);
105
static void make_outerjoin_info(JOIN *join);
106
static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *item);
107
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after);
108
static bool only_eq_ref_tables(JOIN *join, order_st *order, table_map tables);
109
static void update_depend_map(JOIN *join);
110
static void update_depend_map(JOIN *join, order_st *order);
111
static order_st *remove_constants(JOIN *join,order_st *first_order,COND *cond,
112
bool change_list, bool *simple_order);
113
static int return_zero_rows(JOIN *join, select_result *res,TableList *tables,
114
List<Item> &fields, bool send_row,
115
uint64_t select_options, const char *info,
74
117
static COND *build_equal_items(Session *session, COND *cond,
75
118
COND_EQUAL *inherited,
76
119
List<TableList> *join_list,
77
120
COND_EQUAL **cond_equal_ref);
121
static COND* substitute_for_best_equal_field(COND *cond,
122
COND_EQUAL *cond_equal,
123
void *table_join_idx);
124
static COND *simplify_joins(JOIN *join, List<TableList> *join_list,
125
COND *conds, bool top, bool in_sj);
126
static bool check_interleaving_with_nj(JOIN_TAB *last, JOIN_TAB *next);
127
static void restore_prev_nj_state(JOIN_TAB *last);
128
static void reset_nj_counters(List<TableList> *join_list);
129
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list,
130
uint32_t first_unused);
133
void advance_sj_state(const table_map remaining_tables, const JOIN_TAB *tab);
134
static void restore_prev_sj_state(const table_map remaining_tables,
135
const JOIN_TAB *tab);
137
static COND *optimize_cond(JOIN *join, COND *conds,
138
List<TableList> *join_list,
139
Item::cond_result *cond_value);
140
static bool const_expression_in_where(COND *conds,Item *item, Item **comp_item);
141
static int do_select(JOIN *join,List<Item> *fields,Table *tmp_table);
143
static enum_nested_loop_state
144
evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,
146
static enum_nested_loop_state
147
evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab);
148
static enum_nested_loop_state
149
flush_cached_records(JOIN *join, JOIN_TAB *join_tab, bool skip_last);
150
static enum_nested_loop_state
151
end_send(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
152
static enum_nested_loop_state
153
end_write(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
154
static enum_nested_loop_state
155
end_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
156
static enum_nested_loop_state
157
end_unique_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
159
static int join_read_const_table(JOIN_TAB *tab, POSITION *pos);
160
static int join_read_system(JOIN_TAB *tab);
161
static int join_read_const(JOIN_TAB *tab);
162
static int join_read_key(JOIN_TAB *tab);
163
static int join_read_always_key(JOIN_TAB *tab);
164
static int join_read_last_key(JOIN_TAB *tab);
165
static int join_no_more_records(READ_RECORD *info);
166
static int join_read_next(READ_RECORD *info);
167
static int join_read_next_different(READ_RECORD *info);
168
static int join_init_quick_read_record(JOIN_TAB *tab);
169
static int test_if_quick_select(JOIN_TAB *tab);
170
static int join_init_read_record(JOIN_TAB *tab);
171
static int join_read_first(JOIN_TAB *tab);
172
static int join_read_next_same(READ_RECORD *info);
173
static int join_read_next_same_diff(READ_RECORD *info);
174
static int join_read_last(JOIN_TAB *tab);
175
static int join_read_prev_same(READ_RECORD *info);
176
static int join_read_prev(READ_RECORD *info);
177
int join_read_always_key_or_null(JOIN_TAB *tab);
178
int join_read_next_same_or_null(READ_RECORD *info);
179
static COND *make_cond_for_table(COND *cond,table_map table,
180
table_map used_table,
181
bool exclude_expensive_cond);
79
182
static Item* part_of_refkey(Table *form,Field *field);
80
static bool cmp_buffer_with_ref(JoinTable *tab);
81
static void change_cond_ref_to_const(Session *session,
82
list<COND_CMP>& save_list,
87
static bool copy_blobs(Field **ptr);
183
static bool test_if_skip_sort_order(JOIN_TAB *tab,order_st *order,
184
ha_rows select_limit, bool no_changes,
186
static bool list_contains_unique_index(Table *table,
187
bool (*find_func) (Field *, void *), void *data);
188
static bool find_field_in_item_list (Field *field, void *data);
189
static bool find_field_in_order_list (Field *field, void *data);
190
static int create_sort_index(Session *session, JOIN *join, order_st *order,
191
ha_rows filesort_limit, ha_rows select_limit,
193
static int remove_duplicates(JOIN *join,Table *entry,List<Item> &fields,
195
static int remove_dup_with_compare(Session *session, Table *entry, Field **field,
196
uint32_t offset, Item *having);
197
static int remove_dup_with_hash_index(Session *session,Table *table,
198
uint32_t field_count, Field **first_field,
199
uint32_t key_length, Item *having);
200
static int join_init_cache(Session *session,JOIN_TAB *tables,uint32_t table_count);
201
static uint32_t used_blob_length(CACHE_FIELD **ptr);
202
static bool store_record_in_cache(JOIN_CACHE *cache);
203
static void reset_cache_read(JOIN_CACHE *cache);
204
static void reset_cache_write(JOIN_CACHE *cache);
205
static void read_cached_record(JOIN_TAB *tab);
206
static bool cmp_buffer_with_ref(JOIN_TAB *tab);
207
static order_st *create_distinct_group(Session *session, Item **ref_pointer_array,
208
order_st *order, List<Item> &fields,
209
List<Item> &all_fields,
210
bool *all_order_by_fields_used);
211
static bool test_if_subpart(order_st *a,order_st *b);
212
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables);
213
static void calc_group_buffer(JOIN *join,order_st *group);
214
static bool make_group_fields(JOIN *main_join, JOIN *curr_join);
215
static bool alloc_group_fields(JOIN *join,order_st *group);
216
// Create list for using with tempory table
217
static bool change_to_use_tmp_fields(Session *session, Item **ref_pointer_array,
218
List<Item> &new_list1,
219
List<Item> &new_list2,
220
uint32_t elements, List<Item> &items);
221
// Create list for using with tempory table
222
static bool change_refs_to_tmp_fields(Session *session, Item **ref_pointer_array,
223
List<Item> &new_list1,
224
List<Item> &new_list2,
225
uint32_t elements, List<Item> &items);
226
static void init_tmptable_sum_functions(Item_sum **func);
227
static void update_tmptable_sum_func(Item_sum **func,Table *tmp_table);
228
static void copy_sum_funcs(Item_sum **func_ptr, Item_sum **end);
229
static bool add_ref_to_table_cond(Session *session, JOIN_TAB *join_tab);
230
static bool setup_sum_funcs(Session *session, Item_sum **func_ptr);
231
static bool init_sum_functions(Item_sum **func, Item_sum **end);
232
static bool update_sum_func(Item_sum **func);
233
void select_describe(JOIN *join, bool need_tmp_table,bool need_order,
234
bool distinct, const char *message=NULL);
235
static Item *remove_additional_cond(Item* conds);
236
static void add_group_and_distinct_keys(JOIN *join, JOIN_TAB *join_tab);
237
static bool test_if_ref(Item_field *left_item,Item *right_item);
238
static bool replace_where_subcondition(JOIN *join, Item *old_cond,
239
Item *new_cond, bool fix_fields);
89
241
static bool eval_const_cond(COND *cond)
91
243
return ((Item_func*) cond)->val_int() ? true : false;
95
248
This is used to mark equalities that were made from i-th IN-equality.
96
249
We limit semi-join InsideOut optimization to handling max 64 inequalities,
417
Function to setup clauses without sum functions.
419
inline int setup_without_group(Session *session, Item **ref_pointer_array,
423
List<Item> &all_fields,
426
order_st *group, bool *hidden_group_fields)
429
nesting_map save_allow_sum_func=session->lex->allow_sum_func ;
431
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
432
res= setup_conds(session, tables, leaves, conds);
434
session->lex->allow_sum_func|= 1 << session->lex->current_select->nest_level;
435
res= res || setup_order(session, ref_pointer_array, tables, fields, all_fields,
437
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
438
res= res || setup_group(session, ref_pointer_array, tables, fields, all_fields,
439
group, hidden_group_fields);
440
session->lex->allow_sum_func= save_allow_sum_func;
272
444
/*****************************************************************************
273
445
Check fields, find best join, do the select and output fields.
274
select_query assumes that all tables are already opened
446
mysql_select assumes that all tables are already opened
275
447
*****************************************************************************/
450
Prepare of whole select (including sub queries in future).
453
Add check of calculation of GROUP functions and fields:
454
SELECT COUNT(*)+table.col1 from table1;
462
JOIN::prepare(Item ***rref_pointer_array,
463
TableList *tables_init,
464
uint32_t wild_num, COND *conds_init, uint32_t og_num,
465
order_st *order_init, order_st *group_init,
467
Select_Lex *select_lex_arg,
468
Select_Lex_Unit *unit_arg)
470
// to prevent double initialization on EXPLAIN
476
group_list= group_init;
478
tables_list= tables_init;
479
select_lex= select_lex_arg;
480
select_lex->join= this;
481
join_list= &select_lex->top_join_list;
482
union_part= unit_arg->is_union();
484
session->lex->current_select->is_item_list_lookup= 1;
486
If we have already executed SELECT, then it have not sense to prevent
487
its table from update (see unique_table())
489
if (session->derived_tables_processing)
490
select_lex->exclude_from_table_unique_test= true;
492
/* Check that all tables, fields, conds and order are ok */
494
if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
495
setup_tables_and_check_access(session, &select_lex->context, join_list,
496
tables_list, &select_lex->leaf_tables,
500
TableList *table_ptr;
501
for (table_ptr= select_lex->leaf_tables;
503
table_ptr= table_ptr->next_leaf)
506
if (setup_wild(session, tables_list, fields_list, &all_fields, wild_num) ||
507
select_lex->setup_ref_array(session, og_num) ||
508
setup_fields(session, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ,
510
setup_without_group(session, (*rref_pointer_array), tables_list,
511
select_lex->leaf_tables, fields_list,
512
all_fields, &conds, order, group_list,
513
&hidden_group_fields))
514
return(-1); /* purecov: inspected */
516
ref_pointer_array= *rref_pointer_array;
520
nesting_map save_allow_sum_func= session->lex->allow_sum_func;
521
session->where="having clause";
522
session->lex->allow_sum_func|= 1 << select_lex_arg->nest_level;
523
select_lex->having_fix_field= 1;
524
bool having_fix_rc= (!having->fixed &&
525
(having->fix_fields(session, &having) ||
526
having->check_cols(1)));
527
select_lex->having_fix_field= 0;
528
if (having_fix_rc || session->is_error())
529
return(-1); /* purecov: inspected */
530
session->lex->allow_sum_func= save_allow_sum_func;
534
Item_subselect *subselect;
535
Item_in_subselect *in_subs= NULL;
537
Are we in a subquery predicate?
538
TODO: the block below will be executed for every PS execution without need.
540
if ((subselect= select_lex->master_unit()->item))
542
bool do_semijoin= !test(session->variables.optimizer_switch &
543
OPTIMIZER_SWITCH_NO_SEMIJOIN);
544
if (subselect->substype() == Item_subselect::IN_SUBS)
545
in_subs= (Item_in_subselect*)subselect;
548
Check if we're in subquery that is a candidate for flattening into a
549
semi-join (which is done done in flatten_subqueries()). The
551
1. Subquery predicate is an IN/=ANY subq predicate
552
2. Subquery is a single SELECT (not a UNION)
553
3. Subquery does not have GROUP BY or order_st BY
554
4. Subquery does not use aggregate functions or HAVING
555
5. Subquery predicate is at the AND-top-level of ON/WHERE clause
556
6. No execution method was already chosen (by a prepared statement).
558
(*). We are not in a subquery of a single table UPDATE/DELETE that
559
doesn't have a JOIN (TODO: We should handle this at some
560
point by switching to multi-table UPDATE/DELETE)
562
(**). We're not in a confluent table-less subquery, like
566
!select_lex->master_unit()->first_select()->next_select() && // 2
567
!select_lex->group_list.elements && !order && // 3
568
!having && !select_lex->with_sum_func && // 4
569
session->session_marker && // 5
570
select_lex->outer_select()->join && // (*)
571
select_lex->master_unit()->first_select()->leaf_tables && // (**)
573
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
576
if (!in_subs->left_expr->fixed &&
577
in_subs->left_expr->fix_fields(session, &in_subs->left_expr))
582
Check that the right part of the subselect contains no more than one
583
column. E.g. in SELECT 1 IN (SELECT * ..) the right part is (SELECT * ...)
585
if (subselect->substype() == Item_subselect::IN_SUBS &&
586
(select_lex->item_list.elements !=
587
((Item_in_subselect*)subselect)->left_expr->cols()))
589
my_error(ER_OPERAND_COLUMNS, MYF(0), ((Item_in_subselect*)subselect)->left_expr->cols());
594
/* Register the subquery for further processing */
595
select_lex->outer_select()->join->sj_subselects.append(session->mem_root, in_subs);
596
in_subs->expr_join_nest= (TableList*)session->session_marker;
600
bool do_materialize= !test(session->variables.optimizer_switch &
601
OPTIMIZER_SWITCH_NO_MATERIALIZATION);
603
Check if the subquery predicate can be executed via materialization.
604
The required conditions are:
605
1. Subquery predicate is an IN/=ANY subq predicate
606
2. Subquery is a single SELECT (not a UNION)
607
3. Subquery is not a table-less query. In this case there is no
608
point in materializing.
609
4. Subquery predicate is a top-level predicate
610
(this implies it is not negated)
611
TODO: this is a limitation that should be lifeted once we
612
implement correct NULL semantics (WL#3830)
613
5. Subquery is non-correlated
615
This is an overly restrictive condition. It can be extended to:
616
(Subquery is non-correlated ||
617
Subquery is correlated to any query outer to IN predicate ||
618
(Subquery is correlated to the immediate outer query &&
619
Subquery !contains {GROUP BY, order_st BY [LIMIT],
620
aggregate functions) && subquery predicate is not under "NOT IN"))
621
6. No execution method was already chosen (by a prepared statement).
623
(*) The subquery must be part of a SELECT statement. The current
624
condition also excludes multi-table update statements.
626
We have to determine whether we will perform subquery materialization
627
before calling the IN=>EXISTS transformation, so that we know whether to
628
perform the whole transformation or only that part of it which wraps
629
Item_in_subselect in an Item_in_optimizer.
631
if (do_materialize &&
633
!select_lex->master_unit()->first_select()->next_select() && // 2
634
select_lex->master_unit()->first_select()->leaf_tables && // 3
635
session->lex->sql_command == SQLCOM_SELECT) // *
637
if (in_subs->is_top_level_item() && // 4
638
!in_subs->is_correlated && // 5
639
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
640
in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
643
Item_subselect::trans_res trans_res;
644
if ((trans_res= subselect->select_transformer(this)) !=
645
Item_subselect::RES_OK)
647
return((trans_res == Item_subselect::RES_ERROR));
656
for (ord= order; ord; ord= ord->next)
658
Item *item= *ord->item;
659
if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
660
item->split_sum_func(session, ref_pointer_array, all_fields);
664
if (having && having->with_sum_func)
665
having->split_sum_func(session, ref_pointer_array, all_fields,
667
if (select_lex->inner_sum_func_list)
669
Item_sum *end=select_lex->inner_sum_func_list;
670
Item_sum *item_sum= end;
673
item_sum= item_sum->next;
674
item_sum->split_sum_func(session, ref_pointer_array,
675
all_fields, item_sum->ref_by, false);
676
} while (item_sum != end);
679
if (select_lex->inner_refs_list.elements &&
680
fix_inner_refs(session, all_fields, select_lex, ref_pointer_array))
684
Check if there are references to un-aggregated columns when computing
685
aggregate functions with implicit grouping (there is no GROUP BY).
687
MODE_ONLY_FULL_GROUP_BY is enabled here by default
689
if (!group_list && select_lex->full_group_by_flag == (NON_AGG_FIELD_USED | SUM_FUNC_USED))
691
my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
692
ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
696
/* Caclulate the number of groups */
698
for (order_st *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
703
goto err; /* purecov: inspected */
705
if (result && result->prepare(fields_list, unit_arg))
706
goto err; /* purecov: inspected */
708
/* Init join struct */
709
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
710
ref_pointer_array_size= all_fields.elements*sizeof(Item*);
711
this->group= group_list != 0;
714
#ifdef RESTRICTED_GROUP
715
if (sum_func_count && !group_list && (func_count || field_count))
717
my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
721
if (select_lex->olap == ROLLUP_TYPE && rollup_init())
723
if (alloc_func_list())
729
return(-1); /* purecov: inspected */
734
Remove the predicates pushed down into the subquery
737
JOIN::remove_subq_pushed_predicates()
738
where IN Must be NULL
739
OUT The remaining WHERE condition, or NULL
742
Given that this join will be executed using (unique|index)_subquery,
743
without "checking NULL", remove the predicates that were pushed down
746
If the subquery compares scalar values, we can remove the condition that
747
was wrapped into trig_cond (it will be checked when needed by the subquery
750
If the subquery compares row values, we need to keep the wrapped
751
equalities in the WHERE clause: when the left (outer) tuple has both NULL
752
and non-NULL values, we'll do a full table scan and will rely on the
753
equalities corresponding to non-NULL parts of left tuple to filter out
754
non-matching records.
756
TODO: We can remove the equalities that will be guaranteed to be true by the
757
fact that subquery engine will be using index lookup. This must be done only
758
for cases where there are no conversion errors of significance, e.g. 257
759
that is searched in a byte. But this requires homogenization of the return
760
codes of all Field*::store() methods.
763
void JOIN::remove_subq_pushed_predicates(Item **where)
765
if (conds->type() == Item::FUNC_ITEM &&
766
((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
767
((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
768
((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
769
test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
770
((Item_func *)conds)->arguments()[0]))
278
779
Index lookup-based subquery: save some flags for EXPLAIN output
818
Check if the table's rowid is included in the temptable
821
sj_table_is_included()
823
join_tab The table to be checked
826
SemiJoinDuplicateElimination: check the table's rowid should be included
827
in the temptable. This is so if
829
1. The table is not embedded within some semi-join nest
830
2. The has been pulled out of a semi-join nest, or
832
3. The table is functionally dependent on some previous table
834
[4. This is also true for constant tables that can't be
835
NULL-complemented but this function is not called for such tables]
838
true - Include table's rowid
842
static bool sj_table_is_included(JOIN *join, JOIN_TAB *join_tab)
844
if (join_tab->emb_sj_nest)
847
/* Check if this table is functionally dependent on the tables that
848
are within the same outer join nest
850
TableList *embedding= join_tab->table->pos_in_table_list->embedding;
851
if (join_tab->type == JT_EQ_REF)
853
Table_map_iterator it(join_tab->ref.depend_map & ~PSEUDO_TABLE_BITS);
855
while ((idx= it.next_bit())!=Table_map_iterator::BITMAP_END)
857
JOIN_TAB *ref_tab= join->join_tab + idx;
858
if (embedding == ref_tab->table->pos_in_table_list->embedding)
861
/* Ok, functionally dependent */
864
/* Not functionally dependent => need to include*/
870
Setup the strategies to eliminate semi-join duplicates.
873
setup_semijoin_dups_elimination()
875
options Join options (needed to see if join buffering will be
877
no_jbuf_after Another bit of information re where join buffering will
881
Setup the strategies to eliminate semi-join duplicates. ATM there are 3
884
1. DuplicateWeedout (use of temptable to remove duplicates based on rowids
886
2. FirstMatch (pick only the 1st matching row combination of inner tables)
887
3. InsideOut (scanning the sj-inner table in a way that groups duplicates
888
together and picking the 1st one)
890
The join order has "duplicate-generating ranges", and every range is
891
served by one strategy or a combination of FirstMatch with with some
894
"Duplicate-generating range" is defined as a range within the join order
895
that contains all of the inner tables of a semi-join. All ranges must be
896
disjoint, if tables of several semi-joins are interleaved, then the ranges
897
are joined together, which is equivalent to converting
898
SELECT ... WHERE oe1 IN (SELECT ie1 ...) AND oe2 IN (SELECT ie2 )
900
SELECT ... WHERE (oe1, oe2) IN (SELECT ie1, ie2 ... ...)
903
Applicability conditions are as follows:
905
DuplicateWeedout strategy
906
~~~~~~~~~~~~~~~~~~~~~~~~~
908
(ot|nt)* [ it ((it|ot|nt)* (it|ot))] (nt)*
909
+------+ +=========================+ +---+
912
(1) - Prefix of OuterTables (those that participate in
913
IN-equality and/or are correlated with subquery) and outer
914
Noncorrelated Tables.
915
(2) - The handled range. The range starts with the first sj-inner
916
table, and covers all sj-inner and outer tables
917
Within the range, Inner, Outer, outer Noncorrelated tables
918
may follow in any order.
919
(3) - The suffix of outer Noncorrelated tables.
924
(ot|nt)* [ it ((it|nt)* it) ] (nt)*
925
+------+ +==================+ +---+
928
(1) - Prefix of outer and non-correlated tables
929
(2) - The handled range, which may contain only inner and
930
non-correlated tables.
931
(3) - The suffix of outer Noncorrelated tables.
936
(ot|ct|nt) [ insideout_tbl (ot|nt|it)* it ] (ot|nt)*
937
+--------+ +===========+ +=============+ +------+
940
(1) - Prefix that may contain any outer tables. The prefix must contain
941
all the non-trivially correlated outer tables. (non-trivially means
942
that the correlation is not just through the IN-equality).
944
(2) - Inner table for which the InsideOut scan is performed.
946
(3) - The remainder of the duplicate-generating range. It is served by
947
application of FirstMatch strategy, with the exception that
948
outer IN-correlated tables are considered to be non-correlated.
950
(4) - THe suffix of outer and outer non-correlated tables.
952
If several strategies are applicable, their relative priorities are:
957
This function walks over the join order and sets up the strategies by
958
setting appropriate members in join_tab structures.
962
true Out of memory error
966
int setup_semijoin_dups_elimination(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
968
table_map cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
971
0 - invalid (EOF marker),
973
2 - Temptable (maybe confluent),
974
3 - Temptable with join buffering
977
uint32_t start_idx; /* Left range bound */
978
uint32_t end_idx; /* Right range bound */
980
For Temptable strategy: Bitmap of all outer and correlated tables from
981
all involved join nests.
983
table_map outer_tables;
984
} dups_ranges [MAX_TABLES];
986
TableList *emb_insideout_nest= NULL;
987
table_map emb_sj_map= 0; /* A bitmap of sj-nests (that is, their sj-inner
988
tables) whose ranges we're in */
989
table_map emb_outer_tables= 0; /* sj-outer tables for those sj-nests */
990
table_map range_start_map= 0; /* table_map at current range start */
991
bool dealing_with_jbuf= false; /* true <=> table within cur range uses join buf */
996
First pass: locate the duplicate-generating ranges and pick the strategies.
998
for (i=join->const_tables ; i < join->tables ; i++)
1000
JOIN_TAB *tab=join->join_tab+i;
1001
Table *table=tab->table;
1002
cur_map |= table->map;
1004
if (tab->emb_sj_nest) // Encountered an sj-inner table
1008
dups_ranges[cur_range].start_idx= i;
1009
range_start_map= cur_map & ~table->map;
1011
Remember if this is a possible start of range that is covered by
1012
the InsideOut strategy (the reason that it is not covered could
1013
be that it overlaps with anther semi-join's range. we don't
1014
support InsideOut for joined ranges)
1016
if (join->best_positions[i].use_insideout_scan)
1017
emb_insideout_nest= tab->emb_sj_nest;
1020
emb_sj_map |= tab->emb_sj_nest->sj_inner_tables;
1021
emb_outer_tables |= tab->emb_sj_nest->nested_join->sj_depends_on;
1023
if (tab->emb_sj_nest != emb_insideout_nest)
1026
Two different semi-joins interleave. This cannot be handled by
1029
emb_insideout_nest= NULL;
1033
if (emb_sj_map) /* We're in duplicate-generating range */
1035
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
1036
tab->type == JT_ALL && tab->use_quick != 2 && !tab->first_inner &&
1037
i <= no_jbuf_after && !dealing_with_jbuf)
1040
This table uses join buffering, which makes use of FirstMatch or
1041
InsideOut strategies impossible for the current and (we assume)
1042
preceding duplicate-producing ranges.
1043
That is, for the join order:
1045
x x [ x x] x [x x x] x [x x X* x] x
1047
+-----+ +-----+ | join buffering use
1050
we'll have to remove r1 and r2 and use duplicate-elimination
1051
strategy that spans all the tables, starting from the very 1st
1054
dealing_with_jbuf= true;
1055
emb_insideout_nest= false;
1058
Absorb all preceding duplicate-eliminating ranges. Their strategies
1061
for (int prev_range= 0; prev_range < cur_range; prev_range++)
1063
dups_ranges[cur_range].outer_tables |=
1064
dups_ranges[prev_range].outer_tables;
1066
dups_ranges[0].start_idx= 0; /* Will need to start from the 1st table */
1067
dups_ranges[0].outer_tables= dups_ranges[cur_range].outer_tables;
1072
Check if we are at the end of duplicate-producing range. We are if
1074
1. It's an InsideOut range (which presumes all correlated tables are
1075
in the prefix), and all inner tables are in the join order prefix,
1077
2. It's a DuplicateElimination range (possibly covering several
1078
SJ-nests), and all inner, outer, and correlated tables of all
1079
sj-nests are in the join order prefix.
1081
bool end_of_range= false;
1082
if (emb_insideout_nest &&
1083
bitmap_covers(cur_map, emb_insideout_nest->sj_inner_tables))
1085
/* Save that this range is handled with InsideOut: */
1086
dups_ranges[cur_range].strategy= 1;
1089
else if (bitmap_covers(cur_map, emb_outer_tables | emb_sj_map))
1092
This is a complete range to be handled with either DuplicateWeedout
1095
dups_ranges[cur_range].strategy= dealing_with_jbuf? 3 : 2;
1097
This will hold tables from within the range that need to be put
1098
into the join buffer before we can use the FirstMatch on its tail.
1100
dups_ranges[cur_range].outer_tables= emb_outer_tables &
1107
dups_ranges[cur_range].end_idx= i+1;
1108
emb_sj_map= emb_outer_tables= 0;
1109
emb_insideout_nest= NULL;
1110
dealing_with_jbuf= false;
1111
dups_ranges[++cur_range].strategy= 0;
1116
Session *session= join->session;
1117
SJ_TMP_TABLE **next_sjtbl_ptr= &join->sj_tmp_tables;
1119
Second pass: setup the chosen strategies
1121
for (int j= 0; j < cur_range; j++)
1123
JOIN_TAB *tab=join->join_tab + dups_ranges[j].start_idx;
1125
if (dups_ranges[j].strategy == 1) // InsideOut strategy
1127
tab->insideout_match_tab= join->join_tab + dups_ranges[j].end_idx - 1;
1130
else // DuplicateWeedout strategy
1132
SJ_TMP_TABLE::TAB sjtabs[MAX_TABLES];
1133
table_map weed_cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
1134
uint32_t jt_rowid_offset= 0; // # tuple bytes are already occupied (w/o NULL bytes)
1135
uint32_t jt_null_bits= 0; // # null bits in tuple bytes
1136
SJ_TMP_TABLE::TAB *last_tab= sjtabs;
1137
uint32_t rowid_keep_flags= JOIN_TAB::CALL_POSITION | JOIN_TAB::KEEP_ROWID;
1138
JOIN_TAB *last_outer_tab= tab - 1;
1140
Walk through the range and remember
1141
- tables that need their rowids to be put into temptable
1142
- the last outer table
1144
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
1146
if (sj_table_is_included(join, tab))
1148
last_tab->join_tab= tab;
1149
last_tab->rowid_offset= jt_rowid_offset;
1150
jt_rowid_offset += tab->table->file->ref_length;
1151
if (tab->table->maybe_null)
1153
last_tab->null_byte= jt_null_bits / 8;
1154
last_tab->null_bit= jt_null_bits++;
1157
tab->table->prepare_for_position();
1158
tab->rowid_keep_flags= rowid_keep_flags;
1160
weed_cur_map |= tab->table->map;
1161
if (!tab->emb_sj_nest && bitmap_covers(weed_cur_map,
1162
dups_ranges[j].outer_tables))
1163
last_outer_tab= tab;
1166
if (jt_rowid_offset) /* Temptable has at least one rowid */
1168
SJ_TMP_TABLE *sjtbl;
1169
uint32_t tabs_size= (last_tab - sjtabs) * sizeof(SJ_TMP_TABLE::TAB);
1170
if (!(sjtbl= (SJ_TMP_TABLE*)session->alloc(sizeof(SJ_TMP_TABLE))) ||
1171
!(sjtbl->tabs= (SJ_TMP_TABLE::TAB*) session->alloc(tabs_size)))
1173
memcpy(sjtbl->tabs, sjtabs, tabs_size);
1174
sjtbl->tabs_end= sjtbl->tabs + (last_tab - sjtabs);
1175
sjtbl->rowid_len= jt_rowid_offset;
1176
sjtbl->null_bits= jt_null_bits;
1177
sjtbl->null_bytes= (jt_null_bits + 7)/8;
1179
*next_sjtbl_ptr= sjtbl;
1180
next_sjtbl_ptr= &(sjtbl->next);
1184
create_duplicate_weedout_tmp_table(session,
1189
join->join_tab[dups_ranges[j].start_idx].flush_weedout_table= sjtbl;
1190
join->join_tab[dups_ranges[j].end_idx - 1].check_weed_out_table= sjtbl;
1192
tab= last_outer_tab + 1;
1193
jump_to= last_outer_tab;
1196
/* Create the FirstMatch tail */
1197
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
1199
if (tab->emb_sj_nest)
1200
tab->do_firstmatch= jump_to;
1209
static void cleanup_sj_tmp_tables(JOIN *join)
1211
for (SJ_TMP_TABLE *sj_tbl= join->sj_tmp_tables; sj_tbl;
1212
sj_tbl= sj_tbl->next)
1214
if (sj_tbl->tmp_table)
1216
sj_tbl->tmp_table->free_tmp_table(join->session);
1219
join->sj_tmp_tables= NULL;
1222
uint32_t make_join_orderinfo(JOIN *join);
1225
global select optimisation.
1228
error code saved in field 'error'
1239
// to prevent double initialization on EXPLAIN
1244
session->set_proc_info("optimizing");
1245
row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
1246
unit->select_limit_cnt);
1247
/* select_limit is used to decide if we are likely to scan the whole table */
1248
select_limit= unit->select_limit_cnt;
1249
if (having || (select_options & OPTION_FOUND_ROWS))
1250
select_limit= HA_POS_ERROR;
1251
do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
1252
// Ignore errors of execution if option IGNORE present
1253
if (session->lex->ignore)
1254
session->lex->current_select->no_error= 1;
1256
#ifdef HAVE_REF_TO_FIELDS // Not done yet
1257
/* Add HAVING to WHERE if possible */
1258
if (having && !group_list && !sum_func_count)
1265
else if ((conds=new Item_cond_and(conds,having)))
1268
Item_cond_and can't be fixed after creation, so we do not check
1271
conds->fix_fields(session, &conds);
1272
conds->change_ref_to_fields(session, tables_list);
1273
conds->top_level_item();
1279
/* Convert all outer joins to inner joins if possible */
1280
conds= simplify_joins(this, join_list, conds, true, false);
1281
build_bitmap_for_nested_joins(join_list, 0);
1283
conds= optimize_cond(this, conds, join_list, &cond_value);
1284
if (session->is_error())
1291
having= optimize_cond(this, having, join_list, &having_value);
1292
if (session->is_error())
1297
if (select_lex->where)
1298
select_lex->cond_value= cond_value;
1299
if (select_lex->having)
1300
select_lex->having_value= having_value;
1302
if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
1303
(!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
1304
{ /* Impossible cond */
1305
zero_result_cause= having_value == Item::COND_FALSE ?
1306
"Impossible HAVING" : "Impossible WHERE";
1312
/* Optimize count(*), cmin() and cmax() */
1313
if (tables_list && tmp_table_param.sum_func_count && ! group_list)
1317
opt_sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
1318
to the WHERE conditions,
1319
or 1 if all items were resolved,
1320
or 0, or an error number HA_ERR_...
1322
if ((res=opt_sum_query(select_lex->leaf_tables, all_fields, conds)))
1324
if (res == HA_ERR_KEY_NOT_FOUND)
1326
zero_result_cause= "No matching min/max row";
1337
zero_result_cause= "No matching min/max row";
1341
zero_result_cause= "Select tables optimized away";
1342
tables_list= 0; // All tables resolved
1344
Extract all table-independent conditions and replace the WHERE
1345
clause with them. All other conditions were computed by opt_sum_query
1346
and the MIN/MAX/COUNT function(s) have been replaced by constants,
1347
so there is no need to compute the whole WHERE clause again.
1348
Notice that make_cond_for_table() will always succeed to remove all
1349
computed conditions, because opt_sum_query() is applicable only to
1351
Preserve conditions for EXPLAIN.
1353
if (conds && !(session->lex->describe & DESCRIBE_EXTENDED))
1355
COND *table_independent_conds=
1356
make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
1357
conds= table_independent_conds;
1366
error= -1; // Error is sent to client
1367
sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
1369
/* Calculate how to do the join */
1370
session->set_proc_info("statistics");
1371
if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
1372
session->is_fatal_error)
1377
/* Remove distinct if only const tables */
1378
select_distinct= select_distinct && (const_tables != tables);
1379
session->set_proc_info("preparing");
1380
if (result->initialize_tables(this))
1382
return(1); // error == -1
1384
if (const_table_map != found_const_table_map &&
1385
!(select_options & SELECT_DESCRIBE) &&
1387
!(conds->used_tables() & RAND_TABLE_BIT) ||
1388
select_lex->master_unit() == &session->lex->unit)) // upper level SELECT
1390
zero_result_cause= "no matching row in const table";
1394
if (!(session->options & OPTION_BIG_SELECTS) &&
1395
best_read > (double) session->variables.max_join_size &&
1396
!(select_options & SELECT_DESCRIBE))
1397
{ /* purecov: inspected */
1398
my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
1402
if (const_tables && !session->locked_tables &&
1403
!(select_options & SELECT_NO_UNLOCK))
1404
mysql_unlock_some_tables(session, table, const_tables);
1405
if (!conds && outer_join)
1407
/* Handle the case where we have an OUTER JOIN without a WHERE */
1408
conds=new Item_int((int64_t) 1,1); // Always true
1410
select= make_select(*table, const_table_map,
1411
const_table_map, conds, 1, &error);
1413
{ /* purecov: inspected */
1414
error= -1; /* purecov: inspected */
1418
reset_nj_counters(join_list);
1419
make_outerjoin_info(this);
1422
Among the equal fields belonging to the same multiple equality
1423
choose the one that is to be retrieved first and substitute
1424
all references to these in where condition for a reference for
1429
conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
1430
conds->update_used_tables();
1434
Permorm the the optimization on fields evaluation mentioned above
1435
for all on expressions.
1437
for (JOIN_TAB *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
1439
if (*tab->on_expr_ref)
1441
*tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
1444
(*tab->on_expr_ref)->update_used_tables();
1448
if (conds &&!outer_join && const_table_map != found_const_table_map &&
1449
(select_options & SELECT_DESCRIBE) &&
1450
select_lex->master_unit() == &session->lex->unit) // upper level SELECT
1452
conds=new Item_int((int64_t) 0,1); // Always false
1454
if (make_join_select(this, select, conds))
1457
"Impossible WHERE noticed after reading const tables";
1458
return(0); // error == 0
1461
error= -1; /* if goto err */
1463
/* Optimize distinct away if possible */
1465
order_st *org_order= order;
1466
order=remove_constants(this, order,conds,1, &simple_order);
1467
if (session->is_error())
1474
If we are using order_st BY NULL or order_st BY const_expression,
1475
return result in any order (even if we are using a GROUP BY)
1477
if (!order && org_order)
1481
Check if we can optimize away GROUP BY/DISTINCT.
1482
We can do that if there are no aggregate functions, the
1483
fields in DISTINCT clause (if present) and/or columns in GROUP BY
1484
(if present) contain direct references to all key parts of
1485
an unique index (in whatever order) and if the key parts of the
1486
unique index cannot contain NULLs.
1487
Note that the unique keys for DISTINCT and GROUP BY should not
1488
be the same (as long as they are unique).
1490
The FROM clause must contain a single non-constant table.
1492
if (tables - const_tables == 1 && (group_list || select_distinct) &&
1493
!tmp_table_param.sum_func_count &&
1494
(!join_tab[const_tables].select ||
1495
!join_tab[const_tables].select->quick ||
1496
join_tab[const_tables].select->quick->get_type() !=
1497
QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX))
1500
list_contains_unique_index(join_tab[const_tables].table,
1501
find_field_in_order_list,
1502
(void *) group_list))
1505
We have found that grouping can be removed since groups correspond to
1506
only one row anyway, but we still have to guarantee correct result
1507
order. The line below effectively rewrites the query from GROUP BY
1508
<fields> to order_st BY <fields>. There are two exceptions:
1509
- if skip_sort_order is set (see above), then we can simply skip
1511
- we can only rewrite order_st BY if the order_st BY fields are 'compatible'
1512
with the GROUP BY ones, i.e. either one is a prefix of another.
1513
We only check if the order_st BY is a prefix of GROUP BY. In this case
1514
test_if_subpart() copies the ASC/DESC attributes from the original
1516
If GROUP BY is a prefix of order_st BY, then it is safe to leave
1519
if (!order || test_if_subpart(group_list, order))
1520
order= skip_sort_order ? 0 : group_list;
1522
If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
1523
rewritten to IGNORE INDEX FOR order_st BY(fields).
1525
join_tab->table->keys_in_use_for_order_by=
1526
join_tab->table->keys_in_use_for_group_by;
1530
if (select_distinct &&
1531
list_contains_unique_index(join_tab[const_tables].table,
1532
find_field_in_item_list,
1533
(void *) &fields_list))
1538
if (group_list || tmp_table_param.sum_func_count)
1540
if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)
1543
else if (select_distinct && tables - const_tables == 1)
1546
We are only using one table. In this case we change DISTINCT to a
1548
- The GROUP BY can be done through indexes (no sort) and the order_st
1549
BY only uses selected fields.
1550
(In this case we can later optimize away GROUP BY and order_st BY)
1551
- We are scanning the whole table without LIMIT
1553
- We are using CALC_FOUND_ROWS
1554
- We are using an order_st BY that can't be optimized away.
1556
We don't want to use this optimization when we are using LIMIT
1557
because in this case we can just create a temporary table that
1558
holds LIMIT rows and stop when this table is full.
1560
JOIN_TAB *tab= &join_tab[const_tables];
1561
bool all_order_fields_used;
1563
skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
1564
&tab->table->keys_in_use_for_order_by);
1565
if ((group_list=create_distinct_group(session, select_lex->ref_pointer_array,
1566
order, fields_list, all_fields,
1567
&all_order_fields_used)))
1569
bool skip_group= (skip_sort_order &&
1570
test_if_skip_sort_order(tab, group_list, select_limit, 1,
1571
&tab->table->keys_in_use_for_group_by) != 0);
1572
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
1573
if ((skip_group && all_order_fields_used) ||
1574
select_limit == HA_POS_ERROR ||
1575
(order && !skip_sort_order))
1577
/* Change DISTINCT to GROUP BY */
1580
if (all_order_fields_used)
1582
if (order && skip_sort_order)
1585
Force MySQL to read the table in sorted order to get result in
1588
tmp_table_param.quick_group=0;
1592
group=1; // For end_write_group
1597
else if (session->is_fatal_error) // End of memory
1602
order_st *old_group_list;
1603
group_list= remove_constants(this, (old_group_list= group_list), conds,
1604
rollup.state == ROLLUP::STATE_NONE,
1606
if (session->is_error())
1611
if (old_group_list && !group_list)
1614
if (!group_list && group)
1616
order=0; // The output has only one row
1618
select_distinct= 0; // No need in distinct for 1 row
1619
group_optimized_away= 1;
1622
calc_group_buffer(this, group_list);
1623
send_group_parts= tmp_table_param.group_parts; /* Save org parts */
1625
if (test_if_subpart(group_list, order) ||
1626
(!group_list && tmp_table_param.sum_func_count))
1629
// Can't use sort on head table if using row cache
1639
Check if we need to create a temporary table.
1640
This has to be done if all tables are not already read (const tables)
1641
and one of the following conditions holds:
1642
- We are using DISTINCT (simple distinct's are already optimized away)
1643
- We are using an order_st BY or GROUP BY on fields not in the first table
1644
- We are using different order_st BY and GROUP BY orders
1645
- The user wants us to buffer the result.
1647
need_tmp= (const_tables != tables &&
1648
((select_distinct || !simple_order || !simple_group) ||
1649
(group_list && order) ||
1650
test(select_options & OPTION_BUFFER_RESULT)));
1652
uint32_t no_jbuf_after= make_join_orderinfo(this);
1653
uint64_t select_opts_for_readinfo=
1654
(select_options & (SELECT_DESCRIBE | SELECT_NO_JOIN_CACHE)) | (0);
1656
sj_tmp_tables= NULL;
1657
if (!select_lex->sj_nests.is_empty())
1658
setup_semijoin_dups_elimination(this, select_opts_for_readinfo,
1661
// No cache for MATCH == 'Don't use join buffering when we use MATCH'.
1662
if (make_join_readinfo(this, select_opts_for_readinfo, no_jbuf_after))
1665
/* Create all structures needed for materialized subquery execution. */
1666
if (setup_subquery_materialization())
1670
is this simple IN subquery?
1672
if (!group_list && !order &&
1673
unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
1674
tables == 1 && conds &&
1680
if (join_tab[0].type == JT_EQ_REF &&
1681
join_tab[0].ref.items[0]->name == in_left_expr_name)
1683
remove_subq_pushed_predicates(&where);
1684
save_index_subquery_explain_info(join_tab, where);
1685
join_tab[0].type= JT_UNIQUE_SUBQUERY;
1689
subselect_uniquesubquery_engine(session,
1694
else if (join_tab[0].type == JT_REF &&
1695
join_tab[0].ref.items[0]->name == in_left_expr_name)
1697
remove_subq_pushed_predicates(&where);
1698
save_index_subquery_explain_info(join_tab, where);
1699
join_tab[0].type= JT_INDEX_SUBQUERY;
1703
subselect_indexsubquery_engine(session,
1710
} else if (join_tab[0].type == JT_REF_OR_NULL &&
1711
join_tab[0].ref.items[0]->name == in_left_expr_name &&
1712
having->name == in_having_cond)
1714
join_tab[0].type= JT_INDEX_SUBQUERY;
1716
conds= remove_additional_cond(conds);
1717
save_index_subquery_explain_info(join_tab, conds);
1719
change_engine(new subselect_indexsubquery_engine(session,
1729
Need to tell handlers that to play it safe, it should fetch all
1730
columns of the primary key of the tables: this is because MySQL may
1731
build row pointers for the rows, and for all columns of the primary key
1732
the read set has not necessarily been set by the server code.
1734
if (need_tmp || select_distinct || group_list || order)
1736
for (uint32_t i = const_tables; i < tables; i++)
1737
join_tab[i].table->prepare_for_position();
1740
if (const_tables != tables)
1743
Because filesort always does a full table scan or a quick range scan
1744
we must add the removed reference to the select for the table.
1745
We only need to do this when we have a simple_order or simple_group
1746
as in other cases the join is done before the sort.
1748
if ((order || group_list) &&
1749
(join_tab[const_tables].type != JT_ALL) &&
1750
(join_tab[const_tables].type != JT_REF_OR_NULL) &&
1751
((order && simple_order) || (group_list && simple_group)))
1753
if (add_ref_to_table_cond(session,&join_tab[const_tables])) {
1758
if (!(select_options & SELECT_BIG_RESULT) &&
1761
!test_if_skip_sort_order(&join_tab[const_tables], group_list,
1762
unit->select_limit_cnt, 0,
1763
&join_tab[const_tables].table->
1764
keys_in_use_for_group_by))) ||
1766
tmp_table_param.quick_group)
1768
need_tmp=1; simple_order=simple_group=0; // Force tmp table without sort
1773
Force using of tmp table if sorting by a SP or UDF function due to
1774
their expensive and probably non-deterministic nature.
1776
for (order_st *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
1778
Item *item= *tmp_order->item;
1779
if (item->is_expensive())
1781
/* Force tmp table without sort */
1782
need_tmp=1; simple_order=simple_group=0;
1790
if (select_options & SELECT_DESCRIBE)
1798
The loose index scan access method guarantees that all grouping or
1799
duplicate row elimination (for distinct) is already performed
1800
during data retrieval, and that all MIN/MAX functions are already
1801
computed for each group. Thus all MIN/MAX functions should be
1802
treated as regular functions, and there is no need to perform
1803
grouping in the main execution loop.
1804
Notice that currently loose index scan is applicable only for
1805
single table queries, thus it is sufficient to test only the first
1806
join_tab element of the plan for its access method.
1808
if (join_tab->is_using_loose_index_scan())
1809
tmp_table_param.precomputed_group_by= true;
1811
/* Create a tmp table if distinct or if the sort is too complicated */
1814
session->set_proc_info("Creating tmp table");
1816
init_items_ref_array();
1818
tmp_table_param.hidden_field_count= (all_fields.elements -
1819
fields_list.elements);
1820
order_st *tmp_group= ((!simple_group && !(test_flags & TEST_NO_KEY_GROUP)) ? group_list :
1823
Pushing LIMIT to the temporary table creation is not applicable
1824
when there is order_st BY or GROUP BY or there is no GROUP BY, but
1825
there are aggregate functions, because in all these cases we need
1828
ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
1830
!session->lex->current_select->with_sum_func) ?
1831
select_limit : HA_POS_ERROR;
1833
if (!(exec_tmp_table1=
1834
create_tmp_table(session, &tmp_table_param, all_fields,
1836
group_list ? 0 : select_distinct,
1837
group_list && simple_group,
1846
We don't have to store rows in temp table that doesn't match HAVING if:
1847
- we are sorting the table and writing complete group rows to the
1849
- We are using DISTINCT without resolving the distinct as a GROUP BY
1852
If having is not handled here, it will be checked before the row
1853
is sent to the client.
1856
(sort_and_group || (exec_tmp_table1->distinct && !group_list)))
1859
/* if group or order on first table, sort first */
1860
if (group_list && simple_group)
1862
session->set_proc_info("Sorting for group");
1863
if (create_sort_index(session, this, group_list,
1864
HA_POS_ERROR, HA_POS_ERROR, false) ||
1865
alloc_group_fields(this, group_list) ||
1866
make_sum_func_list(all_fields, fields_list, 1) ||
1867
setup_sum_funcs(session, sum_funcs))
1875
if (make_sum_func_list(all_fields, fields_list, 0) ||
1876
setup_sum_funcs(session, sum_funcs))
1881
if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
1883
session->set_proc_info("Sorting for order");
1884
if (create_sort_index(session, this, order,
1885
HA_POS_ERROR, HA_POS_ERROR, true))
1894
Optimize distinct when used on some of the tables
1895
SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
1896
In this case we can stop scanning t2 when we have found one t1.a
1899
if (exec_tmp_table1->distinct)
1901
table_map used_tables= session->used_tables;
1902
JOIN_TAB *last_join_tab= join_tab+tables-1;
1905
if (used_tables & last_join_tab->table->map)
1907
last_join_tab->not_used_in_distinct=1;
1908
} while (last_join_tab-- != join_tab);
1909
/* Optimize "select distinct b from t1 order by key_part_1 limit #" */
1910
if (order && skip_sort_order)
1912
/* Should always succeed */
1913
if (test_if_skip_sort_order(&join_tab[const_tables],
1914
order, unit->select_limit_cnt, 0,
1915
&join_tab[const_tables].table->
1916
keys_in_use_for_order_by))
1922
If this join belongs to an uncacheable subquery save
1925
if (select_lex->uncacheable && !is_top_level_join() &&
1926
init_save_join_tab())
1927
return(-1); /* purecov: inspected */
1936
Restore values in temporary join.
1938
void JOIN::restore_tmp()
1940
memcpy(tmp_join, this, (size_t) sizeof(JOIN));
1947
unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1948
select_lex->offset_limit->val_uint() :
1953
if (exec_tmp_table1)
1955
exec_tmp_table1->file->extra(HA_EXTRA_RESET_STATE);
1956
exec_tmp_table1->file->ha_delete_all_rows();
1957
free_io_cache(exec_tmp_table1);
1958
filesort_free_buffers(exec_tmp_table1,0);
1960
if (exec_tmp_table2)
1962
exec_tmp_table2->file->extra(HA_EXTRA_RESET_STATE);
1963
exec_tmp_table2->file->ha_delete_all_rows();
1964
free_io_cache(exec_tmp_table2);
1965
filesort_free_buffers(exec_tmp_table2,0);
1968
set_items_ref_array(items0);
1971
memcpy(join_tab, join_tab_save, sizeof(JOIN_TAB) * tables);
1976
/* Reset of sum functions */
1979
Item_sum *func, **func_ptr= sum_funcs;
1980
while ((func= *(func_ptr++)))
1988
@brief Save the original join layout
1990
@details Saves the original join layout so it can be reused in
1991
re-execution and for EXPLAIN.
1993
@return Operation status
1995
@retval 1 error occurred.
1999
JOIN::init_save_join_tab()
2001
if (!(tmp_join= (JOIN*)session->alloc(sizeof(JOIN))))
2002
return 1; /* purecov: inspected */
2003
error= 0; // Ensure that tmp_join.error= 0
2010
JOIN::save_join_tab()
2012
if (!join_tab_save && select_lex->master_unit()->uncacheable)
2014
if (!(join_tab_save= (JOIN_TAB*)session->memdup((unsigned char*) join_tab,
2015
sizeof(JOIN_TAB) * tables)))
2026
Note, that create_sort_index calls test_if_skip_sort_order and may
2027
finally replace sorting with index scan if there is a LIMIT clause in
2028
the query. It's never shown in EXPLAIN!
2031
When can we have here session->net.report_error not zero?
2035
List<Item> *columns_list= &fields_list;
2038
session->set_proc_info("executing");
2041
if (!tables_list && (tables || !select_lex->with_sum_func))
2043
/* Only test of functions */
2044
if (select_options & SELECT_DESCRIBE)
2045
select_describe(this, false, false, false, (zero_result_cause?zero_result_cause:"No tables used"));
2048
result->send_fields(*columns_list, Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
2050
We have to test for 'conds' here as the WHERE may not be constant
2051
even if we don't have any tables for prepared statements or if
2052
conds uses something like 'rand()'.
2054
if (cond_value != Item::COND_FALSE &&
2055
(!conds || conds->val_int()) &&
2056
(!having || having->val_int()))
2058
if (do_send_rows && result->send_data(fields_list))
2062
error= (int) result->send_eof();
2063
send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 : session->sent_row_count);
2068
error= (int) result->send_eof();
2072
/* Single select (without union) always returns 0 or 1 row */
2073
session->limit_found_rows= send_records;
2074
session->examined_row_count= 0;
2078
Don't reset the found rows count if there're no tables as
2079
FOUND_ROWS() may be called. Never reset the examined row count here.
2080
It must be accumulated from all join iterations of all join parts.
2083
session->limit_found_rows= 0;
2085
if (zero_result_cause)
2087
(void) return_zero_rows(this, result, select_lex->leaf_tables,
2089
send_row_on_empty_set(),
2096
if ((this->select_lex->options & OPTION_SCHEMA_TABLE) && get_schema_tables_result(this, PROCESSED_BY_JOIN_EXEC))
2099
if (select_options & SELECT_DESCRIBE)
2102
Check if we managed to optimize order_st BY away and don't use temporary
2103
table to resolve order_st BY: in that case, we only may need to do
2104
filesort for GROUP BY.
2106
if (!order && !no_order && (!skip_sort_order || !need_tmp))
2108
/* Reset 'order' to 'group_list' and reinit variables describing 'order' */
2110
simple_order= simple_group;
2113
if (order && (order != group_list || !(select_options & SELECT_BIG_RESULT)))
2115
if (const_tables == tables
2116
|| ((simple_order || skip_sort_order)
2117
&& test_if_skip_sort_order(&join_tab[const_tables], order, select_limit, 0, &join_tab[const_tables].table->keys_in_use_for_query)))
2121
select_describe(this, need_tmp, order != 0 && !skip_sort_order, select_distinct, !tables ? "No tables used" : NULL);
2125
JOIN *curr_join= this;
2126
List<Item> *curr_all_fields= &all_fields;
2127
List<Item> *curr_fields_list= &fields_list;
2128
Table *curr_tmp_table= 0;
2130
Initialize examined rows here because the values from all join parts
2131
must be accumulated in examined_row_count. Hence every join
2132
iteration must count from zero.
2134
curr_join->examined_rows= 0;
2136
/* Create a tmp table if distinct or if the sort is too complicated */
2142
We are in a non cacheable sub query. Get the saved join structure
2144
(curr_join may have been modified during last exection and we need
2147
curr_join= tmp_join;
2149
curr_tmp_table= exec_tmp_table1;
2151
/* Copy data to the temporary table */
2152
session->set_proc_info("Copying to tmp table");
2153
if (! curr_join->sort_and_group && curr_join->const_tables != curr_join->tables)
2154
curr_join->join_tab[curr_join->const_tables].sorted= 0;
2155
if ((tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
2160
curr_tmp_table->file->info(HA_STATUS_VARIABLE);
2162
if (curr_join->having)
2163
curr_join->having= curr_join->tmp_having= 0; // Allready done
2165
/* Change sum_fields reference to calculated fields in tmp_table */
2166
curr_join->all_fields= *curr_all_fields;
2169
items1= items0 + all_fields.elements;
2170
if (sort_and_group || curr_tmp_table->group)
2172
if (change_to_use_tmp_fields(session, items1,
2173
tmp_fields_list1, tmp_all_fields1,
2174
fields_list.elements, all_fields))
2179
if (change_refs_to_tmp_fields(session, items1,
2180
tmp_fields_list1, tmp_all_fields1,
2181
fields_list.elements, all_fields))
2184
curr_join->tmp_all_fields1= tmp_all_fields1;
2185
curr_join->tmp_fields_list1= tmp_fields_list1;
2186
curr_join->items1= items1;
2188
curr_all_fields= &tmp_all_fields1;
2189
curr_fields_list= &tmp_fields_list1;
2190
curr_join->set_items_ref_array(items1);
2192
if (sort_and_group || curr_tmp_table->group)
2194
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count
2195
+ curr_join->tmp_table_param.func_count;
2196
curr_join->tmp_table_param.sum_func_count= 0;
2197
curr_join->tmp_table_param.func_count= 0;
2201
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.func_count;
2202
curr_join->tmp_table_param.func_count= 0;
2205
if (curr_tmp_table->group)
2206
{ // Already grouped
2207
if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
2208
curr_join->order= curr_join->group_list; /* order by group */
2209
curr_join->group_list= 0;
2213
If we have different sort & group then we must sort the data by group
2214
and copy it to another tmp table
2215
This code is also used if we are using distinct something
2216
we haven't been able to store in the temporary table yet
2217
like SEC_TO_TIME(SUM(...)).
2220
if ((curr_join->group_list && (!test_if_subpart(curr_join->group_list, curr_join->order) || curr_join->select_distinct))
2221
|| (curr_join->select_distinct && curr_join->tmp_table_param.using_indirect_summary_function))
2222
{ /* Must copy to another table */
2223
/* Free first data from old join */
2224
curr_join->join_free();
2225
if (make_simple_join(curr_join, curr_tmp_table))
2227
calc_group_buffer(curr_join, group_list);
2228
count_field_types(select_lex, &curr_join->tmp_table_param,
2229
curr_join->tmp_all_fields1,
2230
curr_join->select_distinct && !curr_join->group_list);
2231
curr_join->tmp_table_param.hidden_field_count= curr_join->tmp_all_fields1.elements
2232
- curr_join->tmp_fields_list1.elements;
2234
if (exec_tmp_table2)
2235
curr_tmp_table= exec_tmp_table2;
2238
/* group data to new table */
2241
If the access method is loose index scan then all MIN/MAX
2242
functions are precomputed, and should be treated as regular
2243
functions. See extended comment in JOIN::exec.
2245
if (curr_join->join_tab->is_using_loose_index_scan())
2246
curr_join->tmp_table_param.precomputed_group_by= true;
2248
if (!(curr_tmp_table=
2249
exec_tmp_table2= create_tmp_table(session,
2250
&curr_join->tmp_table_param,
2253
curr_join->select_distinct &&
2254
!curr_join->group_list,
2255
1, curr_join->select_options,
2259
curr_join->exec_tmp_table2= exec_tmp_table2;
2261
if (curr_join->group_list)
2263
session->set_proc_info("Creating sort index");
2264
if (curr_join->join_tab == join_tab && save_join_tab())
2268
if (create_sort_index(session, curr_join, curr_join->group_list,
2269
HA_POS_ERROR, HA_POS_ERROR, false) ||
2270
make_group_fields(this, curr_join))
2274
sortorder= curr_join->sortorder;
2277
session->set_proc_info("Copying to group table");
2279
if (curr_join != this)
2283
curr_join->sum_funcs= sum_funcs2;
2284
curr_join->sum_funcs_end= sum_funcs_end2;
2288
curr_join->alloc_func_list();
2289
sum_funcs2= curr_join->sum_funcs;
2290
sum_funcs_end2= curr_join->sum_funcs_end;
2293
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list, 1, true))
2295
curr_join->group_list= 0;
2297
if (!curr_join->sort_and_group && (curr_join->const_tables != curr_join->tables))
2298
curr_join->join_tab[curr_join->const_tables].sorted= 0;
2300
if (setup_sum_funcs(curr_join->session, curr_join->sum_funcs)
2301
|| (tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
2306
end_read_record(&curr_join->join_tab->read_record);
2307
curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
2308
curr_join->join_tab[0].table= 0; // Table is freed
2310
// No sum funcs anymore
2313
items2= items1 + all_fields.elements;
2314
if (change_to_use_tmp_fields(session, items2,
2315
tmp_fields_list2, tmp_all_fields2,
2316
fields_list.elements, tmp_all_fields1))
2318
curr_join->tmp_fields_list2= tmp_fields_list2;
2319
curr_join->tmp_all_fields2= tmp_all_fields2;
2321
curr_fields_list= &curr_join->tmp_fields_list2;
2322
curr_all_fields= &curr_join->tmp_all_fields2;
2323
curr_join->set_items_ref_array(items2);
2324
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count;
2325
curr_join->tmp_table_param.sum_func_count= 0;
2327
if (curr_tmp_table->distinct)
2328
curr_join->select_distinct=0; /* Each row is unique */
2330
curr_join->join_free(); /* Free quick selects */
2331
if (curr_join->select_distinct && ! curr_join->group_list)
2333
session->set_proc_info("Removing duplicates");
2334
if (curr_join->tmp_having)
2335
curr_join->tmp_having->update_used_tables();
2337
if (remove_duplicates(curr_join, curr_tmp_table,
2338
*curr_fields_list, curr_join->tmp_having))
2341
curr_join->tmp_having=0;
2342
curr_join->select_distinct=0;
2344
curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
2345
if (make_simple_join(curr_join, curr_tmp_table))
2347
calc_group_buffer(curr_join, curr_join->group_list);
2348
count_field_types(select_lex, &curr_join->tmp_table_param, *curr_all_fields, 0);
2352
if (curr_join->group || curr_join->tmp_table_param.sum_func_count)
2354
if (make_group_fields(this, curr_join))
2360
init_items_ref_array();
2361
items3= ref_pointer_array + (all_fields.elements*4);
2362
setup_copy_fields(session, &curr_join->tmp_table_param,
2363
items3, tmp_fields_list3, tmp_all_fields3,
2364
curr_fields_list->elements, *curr_all_fields);
2365
tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
2366
tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
2367
tmp_table_param.save_copy_field_end= curr_join->tmp_table_param.copy_field_end;
2368
curr_join->tmp_all_fields3= tmp_all_fields3;
2369
curr_join->tmp_fields_list3= tmp_fields_list3;
2373
curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
2374
curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
2375
curr_join->tmp_table_param.copy_field_end= tmp_table_param.save_copy_field_end;
2377
curr_fields_list= &tmp_fields_list3;
2378
curr_all_fields= &tmp_all_fields3;
2379
curr_join->set_items_ref_array(items3);
2381
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
2383
setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
2384
session->is_fatal_error)
2387
if (curr_join->group_list || curr_join->order)
2389
session->set_proc_info("Sorting result");
2390
/* If we have already done the group, add HAVING to sorted table */
2391
if (curr_join->tmp_having && ! curr_join->group_list && ! curr_join->sort_and_group)
2393
// Some tables may have been const
2394
curr_join->tmp_having->update_used_tables();
2395
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables];
2396
table_map used_tables= (curr_join->const_table_map |
2397
curr_table->table->map);
2399
Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having, used_tables, used_tables, 0);
2400
if (sort_table_cond)
2402
if (!curr_table->select)
2403
if (!(curr_table->select= new SQL_SELECT))
2405
if (!curr_table->select->cond)
2406
curr_table->select->cond= sort_table_cond;
2407
else // This should never happen
2409
if (!(curr_table->select->cond=
2410
new Item_cond_and(curr_table->select->cond,
2414
Item_cond_and do not need fix_fields for execution, its parameters
2415
are fixed or do not need fix_fields, too
2417
curr_table->select->cond->quick_fix_field();
2419
curr_table->select_cond= curr_table->select->cond;
2420
curr_table->select_cond->top_level_item();
2421
curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
2428
curr_join->select_limit= HA_POS_ERROR;
2432
We can abort sorting after session->select_limit rows if we there is no
2433
WHERE clause for any tables after the sorted one.
2435
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
2436
JOIN_TAB *end_table= &curr_join->join_tab[curr_join->tables];
2437
for (; curr_table < end_table ; curr_table++)
2440
table->keyuse is set in the case there was an original WHERE clause
2441
on the table that was optimized away.
2443
if (curr_table->select_cond ||
2444
(curr_table->keyuse && !curr_table->first_inner))
2446
/* We have to sort all rows */
2447
curr_join->select_limit= HA_POS_ERROR;
2452
if (curr_join->join_tab == join_tab && save_join_tab())
2455
Here we sort rows for order_st BY/GROUP BY clause, if the optimiser
2456
chose FILESORT to be faster than INDEX SCAN or there is no
2457
suitable index present.
2458
Note, that create_sort_index calls test_if_skip_sort_order and may
2459
finally replace sorting with index scan if there is a LIMIT clause in
2460
the query. XXX: it's never shown in EXPLAIN!
2461
OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
2463
if (create_sort_index(session, curr_join,
2464
curr_join->group_list ?
2465
curr_join->group_list : curr_join->order,
2466
curr_join->select_limit,
2467
(select_options & OPTION_FOUND_ROWS ?
2468
HA_POS_ERROR : unit->select_limit_cnt),
2469
curr_join->group_list ? true : false))
2472
sortorder= curr_join->sortorder;
2473
if (curr_join->const_tables != curr_join->tables &&
2474
!curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
2477
If no IO cache exists for the first table then we are using an
2478
INDEX SCAN and no filesort. Thus we should not remove the sorted
2479
attribute on the INDEX SCAN.
2485
/* XXX: When can we have here session->is_error() not zero? */
2486
if (session->is_error())
2488
error= session->is_error();
2491
curr_join->having= curr_join->tmp_having;
2492
curr_join->fields= curr_fields_list;
2494
session->set_proc_info("Sending data");
2495
result->send_fields(*curr_fields_list,
2496
Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
2497
error= do_select(curr_join, curr_fields_list, NULL);
2498
session->limit_found_rows= curr_join->send_records;
2500
/* Accumulate the counts from all join iterations of all join parts. */
2501
session->examined_row_count+= curr_join->examined_rows;
2504
With EXPLAIN EXTENDED we have to restore original ref_array
2505
for a derived table which is always materialized.
2506
Otherwise we would not be able to print the query correctly.
2508
if (items0 && (session->lex->describe & DESCRIBE_EXTENDED) && select_lex->linkage == DERIVED_TABLE_TYPE)
2509
set_items_ref_array(items0);
2518
Return error that hold JOIN.
2522
select_lex->join= 0;
2526
if (join_tab != tmp_join->join_tab)
2528
JOIN_TAB *tab, *end;
2529
for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
2532
tmp_join->tmp_join= 0;
2533
tmp_table_param.copy_field=0;
2534
return(tmp_join->destroy());
2539
if (exec_tmp_table1)
2540
exec_tmp_table1->free_tmp_table(session);
2541
if (exec_tmp_table2)
2542
exec_tmp_table2->free_tmp_table(session);
2544
delete_dynamic(&keyuse);
313
2549
An entry point to single-unit select (a select without UNION).
315
@param session thread Cursor
2551
@param session thread handler
316
2552
@param rref_pointer_array a reference to ref_pointer_array of
317
2553
the top-level select_lex for this query
318
2554
@param tables list of all tables used in this query.
448
2683
return(join->error);
451
inline Item *and_items(Item* cond, Item *item)
2687
int subq_sj_candidate_cmp(Item_in_subselect* const *el1,
2688
Item_in_subselect* const *el2)
2690
return ((*el1)->sj_convert_priority < (*el2)->sj_convert_priority) ? 1 :
2691
( ((*el1)->sj_convert_priority == (*el2)->sj_convert_priority)? 0 : -1);
2695
inline Item * and_items(Item* cond, Item *item)
453
2697
return (cond? (new Item_cond_and(cond, item)) : item);
2701
static TableList *alloc_join_nest(Session *session)
2704
if (!(tbl= (TableList*) session->calloc(ALIGN_SIZE(sizeof(TableList))+
2705
sizeof(nested_join_st))))
2707
tbl->nested_join= (nested_join_st*) ((unsigned char*)tbl +
2708
ALIGN_SIZE(sizeof(TableList)));
2713
void fix_list_after_tbl_changes(Select_Lex *new_parent, List<TableList> *tlist)
2715
List_iterator<TableList> it(*tlist);
2717
while ((table= it++))
2720
table->on_expr->fix_after_pullout(new_parent, &table->on_expr);
2721
if (table->nested_join)
2722
fix_list_after_tbl_changes(new_parent, &table->nested_join->join_list);
2728
Convert a subquery predicate into a TableList semi-join nest
2731
convert_subq_to_sj()
2732
parent_join Parent join, the one that has subq_pred in its WHERE/ON
2734
subq_pred Subquery predicate to be converted
2737
Convert a subquery predicate into a TableList semi-join nest. All the
2738
prerequisites are already checked, so the conversion is always successfull.
2740
Prepared Statements: the transformation is permanent:
2741
- Changes in TableList structures are naturally permanent
2742
- Item tree changes are performed on statement MEM_ROOT:
2743
= we activate statement MEM_ROOT
2744
= this function is called before the first fix_prepare_information
2747
This is intended because the criteria for subquery-to-sj conversion remain
2748
constant for the lifetime of the Prepared Statement.
2752
true Out of memory error
2755
bool convert_subq_to_sj(JOIN *parent_join, Item_in_subselect *subq_pred)
2757
Select_Lex *parent_lex= parent_join->select_lex;
2758
TableList *emb_tbl_nest= NULL;
2759
List<TableList> *emb_join_list= &parent_lex->top_join_list;
2760
Session *session= parent_join->session;
2763
1. Find out where to put the predicate into.
2764
Note: for "t1 LEFT JOIN t2" this will be t2, a leaf.
2766
if ((void*)subq_pred->expr_join_nest != (void*)1)
2768
if (subq_pred->expr_join_nest->nested_join)
2773
... [LEFT] JOIN ( ... ) ON (subquery AND whatever) ...
2775
The sj-nest will be inserted into the brackets nest.
2777
emb_tbl_nest= subq_pred->expr_join_nest;
2778
emb_join_list= &emb_tbl_nest->nested_join->join_list;
2780
else if (!subq_pred->expr_join_nest->outer_join)
2785
... INNER JOIN tblX ON (subquery AND whatever) ...
2787
The sj-nest will be tblX's "sibling", i.e. another child of its
2788
parent. This is ok because tblX is joined as an inner join.
2790
emb_tbl_nest= subq_pred->expr_join_nest->embedding;
2792
emb_join_list= &emb_tbl_nest->nested_join->join_list;
2794
else if (!subq_pred->expr_join_nest->nested_join)
2796
TableList *outer_tbl= subq_pred->expr_join_nest;
2797
TableList *wrap_nest;
2801
... LEFT JOIN tbl ON (on_expr AND subq_pred) ...
2803
we'll need to convert it into:
2805
... LEFT JOIN ( tbl SJ (subq_tables) ) ON (on_expr AND subq_pred) ...
2807
|<----- wrap_nest ---->|
2809
Q: other subqueries may be pointing to this element. What to do?
2810
A1: simple solution: copy *subq_pred->expr_join_nest= *parent_nest.
2811
But we'll need to fix other pointers.
2812
A2: Another way: have TableList::next_ptr so the following
2813
subqueries know the table has been nested.
2814
A3: changes in the TableList::outer_join will make everything work
2817
if (!(wrap_nest= alloc_join_nest(parent_join->session)))
2821
wrap_nest->embedding= outer_tbl->embedding;
2822
wrap_nest->join_list= outer_tbl->join_list;
2823
wrap_nest->alias= (char*) "(sj-wrap)";
2825
wrap_nest->nested_join->join_list.empty();
2826
wrap_nest->nested_join->join_list.push_back(outer_tbl);
2828
outer_tbl->embedding= wrap_nest;
2829
outer_tbl->join_list= &wrap_nest->nested_join->join_list;
2832
wrap_nest will take place of outer_tbl, so move the outer join flag
2835
wrap_nest->outer_join= outer_tbl->outer_join;
2836
outer_tbl->outer_join= 0;
2838
wrap_nest->on_expr= outer_tbl->on_expr;
2839
outer_tbl->on_expr= NULL;
2841
List_iterator<TableList> li(*wrap_nest->join_list);
2845
if (tbl == outer_tbl)
2847
li.replace(wrap_nest);
2852
Ok now wrap_nest 'contains' outer_tbl and we're ready to add the
2853
semi-join nest into it
2855
emb_join_list= &wrap_nest->nested_join->join_list;
2856
emb_tbl_nest= wrap_nest;
2861
nested_join_st *nested_join;
2862
if (!(sj_nest= alloc_join_nest(parent_join->session)))
2866
nested_join= sj_nest->nested_join;
2868
sj_nest->join_list= emb_join_list;
2869
sj_nest->embedding= emb_tbl_nest;
2870
sj_nest->alias= (char*) "(sj-nest)";
2871
/* Nests do not participate in those 'chains', so: */
2872
/* sj_nest->next_leaf= sj_nest->next_local= sj_nest->next_global == NULL*/
2873
emb_join_list->push_back(sj_nest);
2876
nested_join->used_tables and nested_join->not_null_tables are
2877
initialized in simplify_joins().
2881
2. Walk through subquery's top list and set 'embedding' to point to the
2884
Select_Lex *subq_lex= subq_pred->unit->first_select();
2885
nested_join->join_list.empty();
2886
List_iterator_fast<TableList> li(subq_lex->top_join_list);
2887
TableList *tl, *last_leaf;
2890
tl->embedding= sj_nest;
2891
tl->join_list= &nested_join->join_list;
2892
nested_join->join_list.push_back(tl);
2896
Reconnect the next_leaf chain.
2897
TODO: Do we have to put subquery's tables at the end of the chain?
2898
Inserting them at the beginning would be a bit faster.
2899
NOTE: We actually insert them at the front! That's because the order is
2900
reversed in this list.
2902
for (tl= parent_lex->leaf_tables; tl->next_leaf; tl= tl->next_leaf) {};
2903
tl->next_leaf= subq_lex->leaf_tables;
2907
Same as above for next_local chain
2908
(a theory: a next_local chain always starts with ::leaf_tables
2909
because view's tables are inserted after the view)
2911
for (tl= parent_lex->leaf_tables; tl->next_local; tl= tl->next_local) {};
2912
tl->next_local= subq_lex->leaf_tables;
2914
/* A theory: no need to re-connect the next_global chain */
2916
/* 3. Remove the original subquery predicate from the WHERE/ON */
2918
// The subqueries were replaced for Item_int(1) earlier
2919
subq_pred->exec_method= Item_in_subselect::SEMI_JOIN; // for subsequent executions
2920
/*TODO: also reset the 'with_subselect' there. */
2922
/* n. Adjust the parent_join->tables counter */
2923
uint32_t table_no= parent_join->tables;
2924
/* n. Walk through child's tables and adjust table->map */
2925
for (tl= subq_lex->leaf_tables; tl; tl= tl->next_leaf, table_no++)
2927
tl->table->tablenr= table_no;
2928
tl->table->map= ((table_map)1) << table_no;
2929
Select_Lex *old_sl= tl->select_lex;
2930
tl->select_lex= parent_join->select_lex;
2931
for(TableList *emb= tl->embedding; emb && emb->select_lex == old_sl; emb= emb->embedding)
2932
emb->select_lex= parent_join->select_lex;
2934
parent_join->tables += subq_lex->join->tables;
2937
Put the subquery's WHERE into semi-join's sj_on_expr
2938
Add the subquery-induced equalities too.
2940
Select_Lex *save_lex= session->lex->current_select;
2941
session->lex->current_select=subq_lex;
2942
if (!subq_pred->left_expr->fixed &&
2943
subq_pred->left_expr->fix_fields(session, &subq_pred->left_expr))
2945
session->lex->current_select=save_lex;
2947
sj_nest->nested_join->sj_corr_tables= subq_pred->used_tables();
2948
sj_nest->nested_join->sj_depends_on= subq_pred->used_tables() |
2949
subq_pred->left_expr->used_tables();
2950
sj_nest->sj_on_expr= subq_lex->where;
2953
Create the IN-equalities and inject them into semi-join's ON expression.
2954
Additionally, for InsideOut strategy
2955
- Record the number of IN-equalities.
2956
- Create list of pointers to (oe1, ..., ieN). We'll need the list to
2957
see which of the expressions are bound and which are not (for those
2958
we'll produce a distinct stream of (ie_i1,...ie_ik).
2960
(TODO: can we just create a list of pointers and hope the expressions
2961
will not substitute themselves on fix_fields()? or we need to wrap
2962
them into Item_direct_view_refs and store pointers to those. The
2963
pointers to Item_direct_view_refs are guaranteed to be stable as
2964
Item_direct_view_refs doesn't substitute itself with anything in
2965
Item_direct_view_ref::fix_fields.
2967
sj_nest->sj_in_exprs= subq_pred->left_expr->cols();
2968
sj_nest->nested_join->sj_outer_expr_list.empty();
2970
if (subq_pred->left_expr->cols() == 1)
2972
nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr);
2974
Item *item_eq= new Item_func_eq(subq_pred->left_expr,
2975
subq_lex->ref_pointer_array[0]);
2976
item_eq->name= (char*)subq_sj_cond_name;
2977
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
2981
for (uint32_t i= 0; i < subq_pred->left_expr->cols(); i++)
2983
nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr->
2986
new Item_func_eq(subq_pred->left_expr->element_index(i),
2987
subq_lex->ref_pointer_array[i]);
2988
item_eq->name= (char*)subq_sj_cond_name + (i % 64);
2989
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
2992
/* Fix the created equality and AND */
2993
sj_nest->sj_on_expr->fix_fields(parent_join->session, &sj_nest->sj_on_expr);
2996
Walk through sj nest's WHERE and ON expressions and call
2997
item->fix_table_changes() for all items.
2999
sj_nest->sj_on_expr->fix_after_pullout(parent_lex, &sj_nest->sj_on_expr);
3000
fix_list_after_tbl_changes(parent_lex, &sj_nest->nested_join->join_list);
3003
/* Unlink the child select_lex so it doesn't show up in EXPLAIN: */
3004
subq_lex->master_unit()->exclude_level();
3006
/* Inject sj_on_expr into the parent's WHERE or ON */
3009
emb_tbl_nest->on_expr= and_items(emb_tbl_nest->on_expr,
3010
sj_nest->sj_on_expr);
3011
emb_tbl_nest->on_expr->fix_fields(parent_join->session, &emb_tbl_nest->on_expr);
3015
/* Inject into the WHERE */
3016
parent_join->conds= and_items(parent_join->conds, sj_nest->sj_on_expr);
3017
parent_join->conds->fix_fields(parent_join->session, &parent_join->conds);
3018
parent_join->select_lex->where= parent_join->conds;
3026
Convert candidate subquery predicates to semi-joins
3029
JOIN::flatten_subqueries()
3032
Convert candidate subquery predicates to semi-joins.
3039
bool JOIN::flatten_subqueries()
3041
Item_in_subselect **in_subq;
3042
Item_in_subselect **in_subq_end;
3044
if (sj_subselects.elements() == 0)
3047
/* 1. Fix children subqueries */
3048
for (in_subq= sj_subselects.front(), in_subq_end= sj_subselects.back();
3049
in_subq != in_subq_end; in_subq++)
3051
JOIN *child_join= (*in_subq)->unit->first_select()->join;
3052
child_join->outer_tables = child_join->tables;
3053
if (child_join->flatten_subqueries())
3055
(*in_subq)->sj_convert_priority=
3056
(*in_subq)->is_correlated * MAX_TABLES + child_join->outer_tables;
3059
bool outer_join_disable_semi_join= false;
3061
* Temporary measure: disable semi-joins when they are together with outer
3064
* @see LP Bug #314911
3066
for (TableList *tbl= select_lex->leaf_tables; tbl; tbl=tbl->next_leaf)
3068
TableList *embedding= tbl->embedding;
3069
if (tbl->on_expr || (tbl->embedding && !(embedding->sj_on_expr &&
3070
!embedding->embedding)))
3072
in_subq= sj_subselects.front();
3073
outer_join_disable_semi_join= true;
3077
if (! outer_join_disable_semi_join)
3080
2. Pick which subqueries to convert:
3081
sort the subquery array
3082
- prefer correlated subqueries over uncorrelated;
3083
- prefer subqueries that have greater number of outer tables;
3085
sj_subselects.sort(subq_sj_candidate_cmp);
3086
// #tables-in-parent-query + #tables-in-subquery < MAX_TABLES
3087
/* Replace all subqueries to be flattened with Item_int(1) */
3088
for (in_subq= sj_subselects.front();
3089
in_subq != in_subq_end &&
3090
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
3093
if (replace_where_subcondition(this, *in_subq, new Item_int(1), false))
3097
for (in_subq= sj_subselects.front();
3098
in_subq != in_subq_end &&
3099
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
3102
if (convert_subq_to_sj(this, *in_subq))
3107
/* 3. Finalize those we didn't convert */
3108
for (; in_subq!= in_subq_end; in_subq++)
3110
JOIN *child_join= (*in_subq)->unit->first_select()->join;
3111
Item_subselect::trans_res res;
3112
(*in_subq)->changed= 0;
3113
(*in_subq)->fixed= 0;
3114
res= (*in_subq)->select_transformer(child_join);
3115
if (res == Item_subselect::RES_ERROR)
3118
(*in_subq)->changed= 1;
3119
(*in_subq)->fixed= 1;
3121
Item *substitute= (*in_subq)->substitution;
3122
bool do_fix_fields= !(*in_subq)->substitution->fixed;
3123
if (replace_where_subcondition(this, *in_subq, substitute, do_fix_fields))
3126
//if ((*in_subq)->fix_fields(session, (*in_subq)->ref_ptr))
3129
sj_subselects.clear();
3134
Setup for execution all subqueries of a query, for which the optimizer
3135
chose hash semi-join.
3137
@details Iterate over all subqueries of the query, and if they are under an
3138
IN predicate, and the optimizer chose to compute it via hash semi-join:
3139
- try to initialize all data structures needed for the materialized execution
3140
of the IN predicate,
3141
- if this fails, then perform the IN=>EXISTS transformation which was
3142
previously blocked during JOIN::prepare.
3144
This method is part of the "code generation" query processing phase.
3146
This phase must be called after substitute_for_best_equal_field() because
3147
that function may replace items with other items from a multiple equality,
3148
and we need to reference the correct items in the index access method of the
3151
@return Operation status
3152
@retval false success.
3153
@retval true error occurred.
3155
bool JOIN::setup_subquery_materialization()
3157
for (Select_Lex_Unit *un= select_lex->first_inner_unit(); un;
3158
un= un->next_unit())
3160
for (Select_Lex *sl= un->first_select(); sl; sl= sl->next_select())
3162
Item_subselect *subquery_predicate= sl->master_unit()->item;
3163
if (subquery_predicate &&
3164
subquery_predicate->substype() == Item_subselect::IN_SUBS)
3166
Item_in_subselect *in_subs= (Item_in_subselect*) subquery_predicate;
3167
if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION &&
3168
in_subs->setup_engine())
3178
Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
3181
find_eq_ref_candidate()
3182
table Table to be checked
3183
sj_inner_tables Bitmap of inner tables. eq_ref(inner_table) doesn't
3187
Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
3190
Check again if it is feasible to factor common parts with constant table
3194
true - There exists an eq_ref(outer-tables) candidate
3198
bool find_eq_ref_candidate(Table *table, table_map sj_inner_tables)
3200
KEYUSE *keyuse= table->reginfo.join_tab->keyuse;
3205
while (1) /* For each key */
3208
KEY *keyinfo= table->key_info + key;
3209
key_part_map bound_parts= 0;
3210
if ((keyinfo->flags & HA_NOSAME) == HA_NOSAME)
3212
do /* For all equalities on all key parts */
3214
/* Check if this is "t.keypart = expr(outer_tables) */
3215
if (!(keyuse->used_tables & sj_inner_tables) &&
3216
!(keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL))
3218
bound_parts |= 1 << keyuse->keypart;
3221
} while (keyuse->key == key && keyuse->table == table);
3223
if (bound_parts == PREV_BITS(uint, keyinfo->key_parts))
3225
if (keyuse->table != table)
3233
if (keyuse->table != table)
3236
while (keyuse->key == key);
3245
Pull tables out of semi-join nests, if possible
3248
pull_out_semijoin_tables()
3249
join The join where to do the semi-join flattening
3252
Try to pull tables out of semi-join nests.
3255
When this function is called, the join may have several semi-join nests
3256
(possibly within different semi-join nests), but it is guaranteed that
3257
one semi-join nest does not contain another.
3260
A table can be pulled out of the semi-join nest if
3261
- It is a constant table
3265
* Pulled out tables have JOIN_TAB::emb_sj_nest == NULL (like the outer
3267
* Tables that were not pulled out have JOIN_TAB::emb_sj_nest.
3268
* Semi-join nests TableList::sj_inner_tables
3270
This operation is (and should be) performed at each PS execution since
3271
tables may become/cease to be constant across PS reexecutions.
3275
1 - Out of memory error
3278
int pull_out_semijoin_tables(JOIN *join)
3281
List_iterator<TableList> sj_list_it(join->select_lex->sj_nests);
3283
/* Try pulling out of the each of the semi-joins */
3284
while ((sj_nest= sj_list_it++))
3286
/* Action #1: Mark the constant tables to be pulled out */
3287
table_map pulled_tables= 0;
3289
List_iterator<TableList> child_li(sj_nest->nested_join->join_list);
3291
while ((tbl= child_li++))
3295
tbl->table->reginfo.join_tab->emb_sj_nest= sj_nest;
3296
if (tbl->table->map & join->const_table_map)
3298
pulled_tables |= tbl->table->map;
3304
Action #2: Find which tables we can pull out based on
3305
update_ref_and_keys() data. Note that pulling one table out can allow
3306
us to pull out some other tables too.
3308
bool pulled_a_table;
3311
pulled_a_table= false;
3313
while ((tbl= child_li++))
3315
if (tbl->table && !(pulled_tables & tbl->table->map))
3317
if (find_eq_ref_candidate(tbl->table,
3318
sj_nest->nested_join->used_tables &
3321
pulled_a_table= true;
3322
pulled_tables |= tbl->table->map;
3326
} while (pulled_a_table);
3329
if ((sj_nest)->nested_join->used_tables == pulled_tables)
3331
(sj_nest)->sj_inner_tables= 0;
3332
while ((tbl= child_li++))
3335
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
3340
/* Record the bitmap of inner tables, mark the inner tables */
3341
table_map inner_tables=(sj_nest)->nested_join->used_tables &
3343
(sj_nest)->sj_inner_tables= inner_tables;
3344
while ((tbl= child_li++))
3348
if (inner_tables & tbl->table->map)
3349
tbl->table->reginfo.join_tab->emb_sj_nest= (sj_nest);
3351
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
456
3359
/*****************************************************************************
457
Create JoinTableS, make a guess about the table types,
3360
Create JOIN_TABS, make a guess about the table types,
458
3361
Approximate how many records will be used in each table
459
3362
*****************************************************************************/
460
ha_rows get_quick_record_count(Session *session, optimizer::SqlSelect *select, Table *table, const key_map *keys,ha_rows limit)
3365
static ha_rows get_quick_record_count(Session *session, SQL_SELECT *select,
3367
const key_map *keys,ha_rows limit)
463
3370
if (check_stack_overrun(session, STACK_MIN_SIZE, NULL))
478
3385
return(HA_POS_ERROR); /* This shouldn't happend */
3389
This structure is used to collect info on potentially sargable
3390
predicates in order to check whether they become sargable after
3391
reading const tables.
3392
We form a bitmap of indexes that can be used for sargable predicates.
3393
Only such indexes are involved in range analysis.
3395
typedef struct st_sargable_param
3397
Field *field; /* field against which to check sargability */
3398
Item **arg_value; /* values of potential keys for lookups */
3399
uint32_t num_values; /* number of values in the above array */
3403
Calculate the best possible join and initialize the join structure.
3412
make_join_statistics(JOIN *join, TableList *tables, COND *conds,
3413
DYNAMIC_ARRAY *keyuse_array)
3417
uint32_t i,table_count,const_count,key;
3418
table_map found_const_table_map, all_table_map, found_ref, refs;
3419
key_map const_ref, eq_part;
3420
Table **table_vector;
3421
JOIN_TAB *stat,*stat_end,*s,**stat_ref;
3422
KEYUSE *keyuse,*start_keyuse;
3423
table_map outer_join=0;
3424
SARGABLE_PARAM *sargables= 0;
3425
JOIN_TAB *stat_vector[MAX_TABLES+1];
3427
table_count=join->tables;
3428
stat=(JOIN_TAB*) join->session->calloc(sizeof(JOIN_TAB)*table_count);
3429
stat_ref=(JOIN_TAB**) join->session->alloc(sizeof(JOIN_TAB*)*MAX_TABLES);
3430
table_vector=(Table**) join->session->alloc(sizeof(Table*)*(table_count*2));
3431
if (!stat || !stat_ref || !table_vector)
3432
return(1); // Eom /* purecov: inspected */
3434
join->best_ref=stat_vector;
3436
stat_end=stat+table_count;
3437
found_const_table_map= all_table_map=0;
3442
s++, tables= tables->next_leaf, i++)
3444
TableList *embedding= tables->embedding;
3447
s->const_keys.init();
3448
s->checked_keys.init();
3449
s->needed_reg.init();
3450
table_vector[i]=s->table=table=tables->table;
3451
table->pos_in_table_list= tables;
3452
error= table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
3455
table->file->print_error(error, MYF(0));
3458
table->quick_keys.clear_all();
3459
table->reginfo.join_tab=s;
3460
table->reginfo.not_exists_optimize=0;
3461
memset(table->const_key_parts, 0,
3462
sizeof(key_part_map)*table->s->keys);
3463
all_table_map|= table->map;
3465
s->info=0; // For describe
3467
s->dependent= tables->dep_tables;
3468
s->key_dependent= 0;
3469
if (tables->schema_table)
3470
table->file->stats.records= 2;
3471
table->quick_condition_rows= table->file->stats.records;
3473
s->on_expr_ref= &tables->on_expr;
3474
if (*s->on_expr_ref)
3476
/* s is the only inner table of an outer join */
3477
if (!table->file->stats.records && !embedding)
3479
s->dependent= 0; // Ignore LEFT JOIN depend.
3480
set_position(join,const_count++,s,(KEYUSE*) 0);
3483
outer_join|= table->map;
3484
s->embedding_map= 0;
3485
for (;embedding; embedding= embedding->embedding)
3486
s->embedding_map|= embedding->nested_join->nj_map;
3489
if (embedding && !(embedding->sj_on_expr && ! embedding->embedding))
3491
/* s belongs to a nested join, maybe to several embedded joins */
3492
s->embedding_map= 0;
3495
nested_join_st *nested_join= embedding->nested_join;
3496
s->embedding_map|=nested_join->nj_map;
3497
s->dependent|= embedding->dep_tables;
3498
embedding= embedding->embedding;
3499
outer_join|= nested_join->used_tables;
3504
if ((table->file->stats.records <= 1) &&
3506
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) && !join->no_const_tables)
3508
set_position(join,const_count++,s,(KEYUSE*) 0);
3512
join->outer_join=outer_join;
3514
if (join->outer_join)
3517
Build transitive closure for relation 'to be dependent on'.
3518
This will speed up the plan search for many cases with outer joins,
3519
as well as allow us to catch illegal cross references/
3520
Warshall's algorithm is used to build the transitive closure.
3521
As we use bitmaps to represent the relation the complexity
3522
of the algorithm is O((number of tables)^2).
3524
for (i= 0, s= stat ; i < table_count ; i++, s++)
3526
for (uint32_t j= 0 ; j < table_count ; j++)
3528
table= stat[j].table;
3529
if (s->dependent & table->map)
3530
s->dependent |= table->reginfo.join_tab->dependent;
3533
s->table->maybe_null= 1;
3535
/* Catch illegal cross references for outer joins */
3536
for (i= 0, s= stat ; i < table_count ; i++, s++)
3538
if (s->dependent & s->table->map)
3540
join->tables=0; // Don't use join->table
3541
my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
3544
s->key_dependent= s->dependent;
3548
if (conds || outer_join)
3549
if (update_ref_and_keys(join->session, keyuse_array, stat, join->tables,
3550
conds, join->cond_equal,
3551
~outer_join, join->select_lex, &sargables))
3554
/* Read tables with 0 or 1 rows (system tables) */
3555
join->const_table_map= 0;
3557
for (POSITION *p_pos=join->positions, *p_end=p_pos+const_count;
3564
join->const_table_map|=s->table->map;
3565
if ((tmp=join_read_const_table(s, p_pos)))
3568
return(1); // Fatal error
3571
found_const_table_map|= s->table->map;
3574
/* loop until no more const tables are found */
3578
more_const_tables_found:
3583
We only have to loop from stat_vector + const_count as
3584
set_position() will move all const_tables first in stat_vector
3587
for (JOIN_TAB **pos=stat_vector+const_count ; (s= *pos) ; pos++)
3592
If equi-join condition by a key is null rejecting and after a
3593
substitution of a const table the key value happens to be null
3594
then we can state that there are no matches for this equi-join.
3596
if ((keyuse= s->keyuse) && *s->on_expr_ref && !s->embedding_map)
3599
When performing an outer join operation if there are no matching rows
3600
for the single row of the outer table all the inner tables are to be
3601
null complemented and thus considered as constant tables.
3602
Here we apply this consideration to the case of outer join operations
3603
with a single inner table only because the case with nested tables
3604
would require a more thorough analysis.
3605
TODO. Apply single row substitution to null complemented inner tables
3606
for nested outer join operations.
3608
while (keyuse->table == table)
3610
if (!(keyuse->val->used_tables() & ~join->const_table_map) &&
3611
keyuse->val->is_null() && keyuse->null_rejecting)
3614
mark_as_null_row(table);
3615
found_const_table_map|= table->map;
3616
join->const_table_map|= table->map;
3617
set_position(join,const_count++,s,(KEYUSE*) 0);
3618
goto more_const_tables_found;
3624
if (s->dependent) // If dependent on some table
3626
// All dep. must be constants
3627
if (s->dependent & ~(found_const_table_map))
3629
if (table->file->stats.records <= 1L &&
3630
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
3631
!table->pos_in_table_list->embedding)
3635
join->const_table_map|=table->map;
3636
set_position(join,const_count++,s,(KEYUSE*) 0);
3637
if ((tmp= join_read_const_table(s, join->positions+const_count-1)))
3640
return(1); // Fatal error
3643
found_const_table_map|= table->map;
3647
/* check if table can be read by key or table only uses const refs */
3648
if ((keyuse=s->keyuse))
3651
while (keyuse->table == table)
3653
start_keyuse=keyuse;
3655
s->keys.set_bit(key); // QQ: remove this ?
3658
const_ref.clear_all();
3659
eq_part.clear_all();
3662
if (keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize)
3664
if (!((~found_const_table_map) & keyuse->used_tables))
3665
const_ref.set_bit(keyuse->keypart);
3667
refs|=keyuse->used_tables;
3668
eq_part.set_bit(keyuse->keypart);
3671
} while (keyuse->table == table && keyuse->key == key);
3673
if (eq_part.is_prefix(table->key_info[key].key_parts) &&
3674
!table->pos_in_table_list->embedding)
3676
if ((table->key_info[key].flags & (HA_NOSAME))
3679
if (const_ref == eq_part)
3680
{ // Found everything for ref.
3684
join->const_table_map|=table->map;
3685
set_position(join,const_count++,s,start_keyuse);
3686
if (create_ref_for_key(join, s, start_keyuse,
3687
found_const_table_map))
3689
if ((tmp=join_read_const_table(s,
3690
join->positions+const_count-1)))
3693
return(1); // Fatal error
3696
found_const_table_map|= table->map;
3700
found_ref|= refs; // Table is const if all refs are const
3702
else if (const_ref == eq_part)
3703
s->const_keys.set_bit(key);
3708
} while (join->const_table_map & found_ref && ref_changed);
3711
Update info on indexes that can be used for search lookups as
3712
reading const tables may has added new sargable predicates.
3714
if (const_count && sargables)
3716
for( ; sargables->field ; sargables++)
3718
Field *field= sargables->field;
3719
JOIN_TAB *join_tab= field->table->reginfo.join_tab;
3720
key_map possible_keys= field->key_start;
3721
possible_keys.intersect(field->table->keys_in_use_for_query);
3723
for (uint32_t j=0; j < sargables->num_values; j++)
3724
is_const&= sargables->arg_value[j]->const_item();
3726
join_tab[0].const_keys.merge(possible_keys);
3730
if (pull_out_semijoin_tables(join))
3733
/* Calc how many (possible) matched records in each table */
3735
for (s=stat ; s < stat_end ; s++)
3737
if (s->type == JT_SYSTEM || s->type == JT_CONST)
3739
/* Only one matching row */
3740
s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
3743
/* Approximate found rows and time to read them */
3744
s->found_records=s->records=s->table->file->stats.records;
3745
s->read_time=(ha_rows) s->table->file->scan_time();
3748
Set a max range of how many seeks we can expect when using keys
3749
This is can't be to high as otherwise we are likely to use
3752
s->worst_seeks= cmin((double) s->found_records / 10,
3753
(double) s->read_time*3);
3754
if (s->worst_seeks < 2.0) // Fix for small tables
3758
Add to stat->const_keys those indexes for which all group fields or
3759
all select distinct fields participate in one index.
3761
add_group_and_distinct_keys(join, s);
3763
if (!s->const_keys.is_clear_all() &&
3764
!s->table->pos_in_table_list->embedding)
3768
select= make_select(s->table, found_const_table_map,
3769
found_const_table_map,
3770
*s->on_expr_ref ? *s->on_expr_ref : conds,
3774
records= get_quick_record_count(join->session, select, s->table,
3775
&s->const_keys, join->row_limit);
3776
s->quick=select->quick;
3777
s->needed_reg=select->needed_reg;
3779
if (records == 0 && s->table->reginfo.impossible_range)
3782
Impossible WHERE or ON expression
3783
In case of ON, we mark that the we match one empty NULL row.
3784
In case of WHERE, don't set found_const_table_map to get the
3785
caller to abort with a zero row result.
3787
join->const_table_map|= s->table->map;
3788
set_position(join,const_count++,s,(KEYUSE*) 0);
3790
if (*s->on_expr_ref)
3792
/* Generate empty row */
3793
s->info= "Impossible ON condition";
3794
found_const_table_map|= s->table->map;
3796
mark_as_null_row(s->table); // All fields are NULL
3799
if (records != HA_POS_ERROR)
3801
s->found_records=records;
3802
s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
3808
join->join_tab=stat;
3809
join->map2table=stat_ref;
3810
join->table= join->all_tables=table_vector;
3811
join->const_tables=const_count;
3812
join->found_const_table_map=found_const_table_map;
3814
/* Find an optimal join order of the non-constant tables. */
3815
if (join->const_tables != join->tables)
3817
optimize_keyuse(join, keyuse_array);
3818
if (choose_plan(join, all_table_map & ~join->const_table_map))
3823
memcpy(join->best_positions, join->positions,
3824
sizeof(POSITION)*join->const_tables);
3825
join->best_read=1.0;
3827
/* Generate an execution plan from the found optimal join order. */
3828
return(join->session->killed || get_best_combination(join));
481
3832
/*****************************************************************************
482
3833
Check with keys are used and with tables references with tables
483
3834
Updates in stat:
486
3837
keyuse Pointer to possible keys
487
3838
*****************************************************************************/
3840
/// Used when finding key fields
3841
typedef struct key_field_t {
3843
Item *val; ///< May be empty if diff constant
3845
uint optimize; // KEY_OPTIMIZE_*
3848
If true, the condition this struct represents will not be satisfied
3851
bool null_rejecting;
3852
bool *cond_guard; /* See KEYUSE::cond_guard */
3853
uint32_t sj_pred_no; /* See KEYUSE::sj_pred_no */
3857
Merge new key definitions to old ones, remove those not used in both.
3859
This is called for OR between different levels.
3861
To be able to do 'ref_or_null' we merge a comparison of a column
3862
and 'column IS NULL' to one test. This is useful for sub select queries
3863
that are internally transformed to something like:.
3866
SELECT * FROM t1 WHERE t1.key=outer_ref_field or t1.key IS NULL
3869
KEY_FIELD::null_rejecting is processed as follows: @n
3870
result has null_rejecting=true if it is set for both ORed references.
3872
- (t2.key = t1.field OR t2.key = t1.field) -> null_rejecting=true
3873
- (t2.key = t1.field OR t2.key <=> t1.field) -> null_rejecting=false
3876
The result of this is that we're missing some 'ref' accesses.
3877
OptimizerTeam: Fix this
3881
merge_key_fields(KEY_FIELD *start,KEY_FIELD *new_fields,KEY_FIELD *end,
3884
if (start == new_fields)
3885
return start; // Impossible or
3886
if (new_fields == end)
3887
return start; // No new fields, skip all
3889
KEY_FIELD *first_free=new_fields;
3891
/* Mark all found fields in old array */
3892
for (; new_fields != end ; new_fields++)
3894
for (KEY_FIELD *old=start ; old != first_free ; old++)
3896
if (old->field == new_fields->field)
3899
NOTE: below const_item() call really works as "!used_tables()", i.e.
3900
it can return false where it is feasible to make it return true.
3902
The cause is as follows: Some of the tables are already known to be
3903
const tables (the detection code is in make_join_statistics(),
3904
above the update_ref_and_keys() call), but we didn't propagate
3905
information about this: Table::const_table is not set to true, and
3906
Item::update_used_tables() hasn't been called for each item.
3907
The result of this is that we're missing some 'ref' accesses.
3908
TODO: OptimizerTeam: Fix this
3910
if (!new_fields->val->const_item())
3913
If the value matches, we can use the key reference.
3914
If not, we keep it until we have examined all new values
3916
if (old->val->eq(new_fields->val, old->field->binary()))
3918
old->level= and_level;
3919
old->optimize= ((old->optimize & new_fields->optimize &
3920
KEY_OPTIMIZE_EXISTS) |
3921
((old->optimize | new_fields->optimize) &
3922
KEY_OPTIMIZE_REF_OR_NULL));
3923
old->null_rejecting= (old->null_rejecting &&
3924
new_fields->null_rejecting);
3927
else if (old->eq_func && new_fields->eq_func &&
3928
old->val->eq_by_collation(new_fields->val,
3929
old->field->binary(),
3930
old->field->charset()))
3933
old->level= and_level;
3934
old->optimize= ((old->optimize & new_fields->optimize &
3935
KEY_OPTIMIZE_EXISTS) |
3936
((old->optimize | new_fields->optimize) &
3937
KEY_OPTIMIZE_REF_OR_NULL));
3938
old->null_rejecting= (old->null_rejecting &&
3939
new_fields->null_rejecting);
3941
else if (old->eq_func && new_fields->eq_func &&
3942
((old->val->const_item() && old->val->is_null()) ||
3943
new_fields->val->is_null()))
3945
/* field = expression OR field IS NULL */
3946
old->level= and_level;
3947
old->optimize= KEY_OPTIMIZE_REF_OR_NULL;
3949
Remember the NOT NULL value unless the value does not depend
3952
if (!old->val->used_tables() && old->val->is_null())
3953
old->val= new_fields->val;
3954
/* The referred expression can be NULL: */
3955
old->null_rejecting= 0;
3960
We are comparing two different const. In this case we can't
3961
use a key-lookup on this so it's better to remove the value
3962
and let the range optimzier handle it
3964
if (old == --first_free) // If last item
3966
*old= *first_free; // Remove old value
3967
old--; // Retry this value
3972
/* Remove all not used items */
3973
for (KEY_FIELD *old=start ; old != first_free ;)
3975
if (old->level != and_level)
3976
{ // Not used in all levels
3977
if (old == --first_free)
3979
*old= *first_free; // Remove old value
3989
Add a possible key to array of possible keys if it's usable as a key
3991
@param key_fields Pointer to add key, if usable
3992
@param and_level And level, to be stored in KEY_FIELD
3993
@param cond Condition predicate
3994
@param field Field used in comparision
3995
@param eq_func True if we used =, <=> or IS NULL
3996
@param value Value used for comparison with field
3997
@param usable_tables Tables which can be used for key optimization
3998
@param sargables IN/OUT Array of found sargable candidates
4001
If we are doing a NOT NULL comparison on a NOT NULL field in a outer join
4002
table, we store this to be able to do not exists optimization later.
4005
*key_fields is incremented if we stored a key in the array
4009
add_key_field(KEY_FIELD **key_fields,uint32_t and_level, Item_func *cond,
4010
Field *field, bool eq_func, Item **value, uint32_t num_values,
4011
table_map usable_tables, SARGABLE_PARAM **sargables)
4013
uint32_t exists_optimize= 0;
4014
if (!(field->flags & PART_KEY_FLAG))
4016
// Don't remove column IS NULL on a LEFT JOIN table
4017
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
4018
!field->table->maybe_null || field->null_ptr)
4019
return; // Not a key. Skip it
4020
exists_optimize= KEY_OPTIMIZE_EXISTS;
4021
assert(num_values == 1);
4025
table_map used_tables=0;
4027
for (uint32_t i=0; i<num_values; i++)
4029
used_tables|=(value[i])->used_tables();
4030
if (!((value[i])->used_tables() & (field->table->map | RAND_TABLE_BIT)))
4035
if (!(usable_tables & field->table->map))
4037
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
4038
!field->table->maybe_null || field->null_ptr)
4039
return; // Can't use left join optimize
4040
exists_optimize= KEY_OPTIMIZE_EXISTS;
4044
JOIN_TAB *stat=field->table->reginfo.join_tab;
4045
key_map possible_keys=field->key_start;
4046
possible_keys.intersect(field->table->keys_in_use_for_query);
4047
stat[0].keys.merge(possible_keys); // Add possible keys
4050
Save the following cases:
4052
Field LIKE constant where constant doesn't start with a wildcard
4053
Field = field2 where field2 is in a different table
4060
stat[0].key_dependent|=used_tables;
4063
for (uint32_t i=0; i<num_values; i++)
4065
if (!(is_const&= value[i]->const_item()))
4069
stat[0].const_keys.merge(possible_keys);
4073
Save info to be able check whether this predicate can be
4074
considered as sargable for range analisis after reading const tables.
4075
We do not save info about equalities as update_const_equal_items
4076
will take care of updating info on keys from sargable equalities.
4079
(*sargables)->field= field;
4080
(*sargables)->arg_value= value;
4081
(*sargables)->num_values= num_values;
4084
We can't always use indexes when comparing a string index to a
4085
number. cmp_type() is checked to allow compare of dates to numbers.
4086
eq_func is NEVER true when num_values > 1
4091
Additional optimization: if we're processing
4092
"t.key BETWEEN c1 AND c1" then proceed as if we were processing
4094
TODO: This is a very limited fix. A more generic fix is possible.
4095
There are 2 options:
4096
A) Make equality propagation code be able to handle BETWEEN
4097
(including cases like t1.key BETWEEN t2.key AND t3.key)
4098
B) Make range optimizer to infer additional "t.key = c" equalities
4099
and use them in equality propagation process (see details in
4102
if ((cond->functype() != Item_func::BETWEEN) ||
4103
((Item_func_between*) cond)->negated ||
4104
!value[0]->eq(value[1], field->binary()))
4109
if (field->result_type() == STRING_RESULT)
4111
if ((*value)->result_type() != STRING_RESULT)
4113
if (field->cmp_type() != (*value)->result_type())
4119
We can't use indexes if the effective collation
4120
of the operation differ from the field collation.
4122
if (field->cmp_type() == STRING_RESULT &&
4123
((Field_str*)field)->charset() != cond->compare_collation())
4130
For the moment eq_func is always true. This slot is reserved for future
4131
extensions where we want to remembers other things than just eq comparisons
4134
/* Store possible eq field */
4135
(*key_fields)->field= field;
4136
(*key_fields)->eq_func= eq_func;
4137
(*key_fields)->val= *value;
4138
(*key_fields)->level= and_level;
4139
(*key_fields)->optimize= exists_optimize;
4141
If the condition has form "tbl.keypart = othertbl.field" and
4142
othertbl.field can be NULL, there will be no matches if othertbl.field
4144
We use null_rejecting in add_not_null_conds() to add
4145
'othertbl.field IS NOT NULL' to tab->select_cond.
4147
(*key_fields)->null_rejecting= ((cond->functype() == Item_func::EQ_FUNC ||
4148
cond->functype() == Item_func::MULT_EQUAL_FUNC) &&
4149
((*value)->type() == Item::FIELD_ITEM) &&
4150
((Item_field*)*value)->field->maybe_null());
4151
(*key_fields)->cond_guard= NULL;
4152
(*key_fields)->sj_pred_no= (cond->name >= subq_sj_cond_name &&
4153
cond->name < subq_sj_cond_name + 64)?
4154
cond->name - subq_sj_cond_name: UINT_MAX;
4159
Add possible keys to array of possible keys originated from a simple
4162
@param key_fields Pointer to add key, if usable
4163
@param and_level And level, to be stored in KEY_FIELD
4164
@param cond Condition predicate
4165
@param field Field used in comparision
4166
@param eq_func True if we used =, <=> or IS NULL
4167
@param value Value used for comparison with field
4168
Is NULL for BETWEEN and IN
4169
@param usable_tables Tables which can be used for key optimization
4170
@param sargables IN/OUT Array of found sargable candidates
4173
If field items f1 and f2 belong to the same multiple equality and
4174
a key is added for f1, the the same key is added for f2.
4177
*key_fields is incremented if we stored a key in the array
4181
add_key_equal_fields(KEY_FIELD **key_fields, uint32_t and_level,
4182
Item_func *cond, Item_field *field_item,
4183
bool eq_func, Item **val,
4184
uint32_t num_values, table_map usable_tables,
4185
SARGABLE_PARAM **sargables)
4187
Field *field= field_item->field;
4188
add_key_field(key_fields, and_level, cond, field,
4189
eq_func, val, num_values, usable_tables, sargables);
4190
Item_equal *item_equal= field_item->item_equal;
4194
Add to the set of possible key values every substitution of
4195
the field for an equal field included into item_equal
4197
Item_equal_iterator it(*item_equal);
4199
while ((item= it++))
4201
if (!field->eq(item->field))
4203
add_key_field(key_fields, and_level, cond, item->field,
4204
eq_func, val, num_values, usable_tables,
4212
add_key_fields(JOIN *join, KEY_FIELD **key_fields, uint32_t *and_level,
4213
COND *cond, table_map usable_tables,
4214
SARGABLE_PARAM **sargables)
4216
if (cond->type() == Item_func::COND_ITEM)
4218
List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
4219
KEY_FIELD *org_key_fields= *key_fields;
4221
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
4225
add_key_fields(join, key_fields, and_level, item, usable_tables,
4227
for (; org_key_fields != *key_fields ; org_key_fields++)
4228
org_key_fields->level= *and_level;
4233
add_key_fields(join, key_fields, and_level, li++, usable_tables,
4238
KEY_FIELD *start_key_fields= *key_fields;
4240
add_key_fields(join, key_fields, and_level, item, usable_tables,
4242
*key_fields=merge_key_fields(org_key_fields,start_key_fields,
4243
*key_fields,++(*and_level));
4250
Subquery optimization: Conditions that are pushed down into subqueries
4251
are wrapped into Item_func_trig_cond. We process the wrapped condition
4252
but need to set cond_guard for KEYUSE elements generated from it.
4255
if (cond->type() == Item::FUNC_ITEM &&
4256
((Item_func*)cond)->functype() == Item_func::TRIG_COND_FUNC)
4258
Item *cond_arg= ((Item_func*)cond)->arguments()[0];
4259
if (!join->group_list && !join->order &&
4261
join->unit->item->substype() == Item_subselect::IN_SUBS &&
4262
!join->unit->is_union())
4264
KEY_FIELD *save= *key_fields;
4265
add_key_fields(join, key_fields, and_level, cond_arg, usable_tables,
4267
// Indicate that this ref access candidate is for subquery lookup:
4268
for (; save != *key_fields; save++)
4269
save->cond_guard= ((Item_func_trig_cond*)cond)->get_trig_var();
4275
/* If item is of type 'field op field/constant' add it to key_fields */
4276
if (cond->type() != Item::FUNC_ITEM)
4278
Item_func *cond_func= (Item_func*) cond;
4279
switch (cond_func->select_optimize()) {
4280
case Item_func::OPTIMIZE_NONE:
4282
case Item_func::OPTIMIZE_KEY:
4286
if (cond_func->key_item()->real_item()->type() == Item::FIELD_ITEM &&
4287
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
4289
values= cond_func->arguments()+1;
4290
if (cond_func->functype() == Item_func::NE_FUNC &&
4291
cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
4292
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
4294
assert(cond_func->functype() != Item_func::IN_FUNC ||
4295
cond_func->argument_count() != 2);
4296
add_key_equal_fields(key_fields, *and_level, cond_func,
4297
(Item_field*) (cond_func->key_item()->real_item()),
4299
cond_func->argument_count()-1,
4300
usable_tables, sargables);
4302
if (cond_func->functype() == Item_func::BETWEEN)
4304
values= cond_func->arguments();
4305
for (uint32_t i= 1 ; i < cond_func->argument_count() ; i++)
4307
Item_field *field_item;
4308
if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM
4310
!(cond_func->arguments()[i]->used_tables() & OUTER_REF_TABLE_BIT))
4312
field_item= (Item_field *) (cond_func->arguments()[i]->real_item());
4313
add_key_equal_fields(key_fields, *and_level, cond_func,
4314
field_item, 0, values, 1, usable_tables,
4321
case Item_func::OPTIMIZE_OP:
4323
bool equal_func=(cond_func->functype() == Item_func::EQ_FUNC ||
4324
cond_func->functype() == Item_func::EQUAL_FUNC);
4326
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
4327
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
4329
add_key_equal_fields(key_fields, *and_level, cond_func,
4330
(Item_field*) (cond_func->arguments()[0])->real_item(),
4332
cond_func->arguments()+1, 1, usable_tables,
4335
if (cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
4336
cond_func->functype() != Item_func::LIKE_FUNC &&
4337
!(cond_func->arguments()[1]->used_tables() & OUTER_REF_TABLE_BIT))
4339
add_key_equal_fields(key_fields, *and_level, cond_func,
4340
(Item_field*) (cond_func->arguments()[1])->real_item(),
4342
cond_func->arguments(),1,usable_tables,
4347
case Item_func::OPTIMIZE_NULL:
4348
/* column_name IS [NOT] NULL */
4349
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
4350
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
4352
Item *tmp=new Item_null;
4353
if (unlikely(!tmp)) // Should never be true
4355
add_key_equal_fields(key_fields, *and_level, cond_func,
4356
(Item_field*) (cond_func->arguments()[0])->real_item(),
4357
cond_func->functype() == Item_func::ISNULL_FUNC,
4358
&tmp, 1, usable_tables, sargables);
4361
case Item_func::OPTIMIZE_EQUAL:
4362
Item_equal *item_equal= (Item_equal *) cond;
4363
Item *const_item= item_equal->get_const();
4364
Item_equal_iterator it(*item_equal);
4369
For each field field1 from item_equal consider the equality
4370
field1=const_item as a condition allowing an index access of the table
4371
with field1 by the keys value of field1.
4373
while ((item= it++))
4375
add_key_field(key_fields, *and_level, cond_func, item->field,
4376
true, &const_item, 1, usable_tables, sargables);
4382
Consider all pairs of different fields included into item_equal.
4383
For each of them (field1, field1) consider the equality
4384
field1=field2 as a condition allowing an index access of the table
4385
with field1 by the keys value of field2.
4387
Item_equal_iterator fi(*item_equal);
4388
while ((item= fi++))
4390
Field *field= item->field;
4391
while ((item= it++))
4393
if (!field->eq(item->field))
4395
add_key_field(key_fields, *and_level, cond_func, field,
4396
true, (Item **) &item, 1, usable_tables,
491
4408
Add all keys with uses 'field' for some keypart.
493
4410
If field->and_level != and_level then only mark key_part as const_part.
495
uint32_t max_part_bit(key_part_map bits)
4414
max_part_bit(key_part_map bits)
498
4417
for (found=0; bits & 1 ; found++,bits>>=1) ;
502
static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b)
4422
add_key_part(DYNAMIC_ARRAY *keyuse_array,KEY_FIELD *key_field)
4424
Field *field=key_field->field;
4425
Table *form= field->table;
4428
if (key_field->eq_func && !(key_field->optimize & KEY_OPTIMIZE_EXISTS))
4430
for (uint32_t key= 0 ; key < form->sizeKeys() ; key++)
4432
if (!(form->keys_in_use_for_query.is_set(key)))
4435
uint32_t key_parts= (uint32_t) form->key_info[key].key_parts;
4436
for (uint32_t part=0 ; part < key_parts ; part++)
4438
if (field->eq(form->key_info[key].key_part[part].field))
4440
keyuse.table= field->table;
4441
keyuse.val = key_field->val;
4443
keyuse.keypart=part;
4444
keyuse.keypart_map= (key_part_map) 1 << part;
4445
keyuse.used_tables=key_field->val->used_tables();
4446
keyuse.optimize= key_field->optimize & KEY_OPTIMIZE_REF_OR_NULL;
4447
keyuse.null_rejecting= key_field->null_rejecting;
4448
keyuse.cond_guard= key_field->cond_guard;
4449
keyuse.sj_pred_no= key_field->sj_pred_no;
4450
insert_dynamic(keyuse_array,(unsigned char*) &keyuse);
4458
sort_keyuse(KEYUSE *a,KEYUSE *b)
505
if (a->getTable()->tablenr != b->getTable()->tablenr)
506
return static_cast<int>((a->getTable()->tablenr - b->getTable()->tablenr));
507
if (a->getKey() != b->getKey())
508
return static_cast<int>((a->getKey() - b->getKey()));
509
if (a->getKeypart() != b->getKeypart())
510
return static_cast<int>((a->getKeypart() - b->getKeypart()));
4461
if (a->table->tablenr != b->table->tablenr)
4462
return (int) (a->table->tablenr - b->table->tablenr);
4463
if (a->key != b->key)
4464
return (int) (a->key - b->key);
4465
if (a->keypart != b->keypart)
4466
return (int) (a->keypart - b->keypart);
511
4467
// Place const values before other ones
512
if ((res= test((a->getUsedTables() & ~OUTER_REF_TABLE_BIT)) -
513
test((b->getUsedTables() & ~OUTER_REF_TABLE_BIT))))
4468
if ((res= test((a->used_tables & ~OUTER_REF_TABLE_BIT)) -
4469
test((b->used_tables & ~OUTER_REF_TABLE_BIT))))
515
4471
/* Place rows that are not 'OPTIMIZE_REF_OR_NULL' first */
516
return static_cast<int>(((a->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL) -
517
(b->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL)));
4472
return (int) ((a->optimize & KEY_OPTIMIZE_REF_OR_NULL) -
4473
(b->optimize & KEY_OPTIMIZE_REF_OR_NULL));
4478
Add to KEY_FIELD array all 'ref' access candidates within nested join.
4480
This function populates KEY_FIELD array with entries generated from the
4481
ON condition of the given nested join, and does the same for nested joins
4482
contained within this nested join.
4484
@param[in] nested_join_table Nested join pseudo-table to process
4485
@param[in,out] end End of the key field array
4486
@param[in,out] and_level And-level
4487
@param[in,out] sargables Array of found sargable candidates
4491
We can add accesses to the tables that are direct children of this nested
4492
join (1), and are not inner tables w.r.t their neighbours (2).
4494
Example for #1 (outer brackets pair denotes nested join this function is
4497
... LEFT JOIN (t1 LEFT JOIN (t2 ... ) ) ON cond
4501
... LEFT JOIN (t1 LEFT JOIN t2 ) ON cond
4503
In examples 1-2 for condition cond, we can add 'ref' access candidates to
4507
... LEFT JOIN (t1, t2 LEFT JOIN t3 ON inner_cond) ON cond
4509
Here we can add 'ref' access candidates for t1 and t2, but not for t3.
4512
static void add_key_fields_for_nj(JOIN *join, TableList *nested_join_table,
4513
KEY_FIELD **end, uint32_t *and_level,
4514
SARGABLE_PARAM **sargables)
4516
List_iterator<TableList> li(nested_join_table->nested_join->join_list);
4517
List_iterator<TableList> li2(nested_join_table->nested_join->join_list);
4518
bool have_another = false;
4519
table_map tables= 0;
4521
assert(nested_join_table->nested_join);
4523
while ((table= li++) || (have_another && (li=li2, have_another=false,
4526
if (table->nested_join)
4528
if (!table->on_expr)
4530
/* It's a semi-join nest. Walk into it as if it wasn't a nest */
4533
li= List_iterator<TableList>(table->nested_join->join_list);
4536
add_key_fields_for_nj(join, table, end, and_level, sargables);
4539
if (!table->on_expr)
4540
tables |= table->table->map;
4542
if (nested_join_table->on_expr)
4543
add_key_fields(join, end, and_level, nested_join_table->on_expr, tables,
777
4807
/* Intersect the keys of all group fields. */
778
4808
cur_item= indexed_fields_it++;
779
possible_keys|= cur_item->field->part_of_key;
4809
possible_keys.merge(cur_item->field->part_of_key);
780
4810
while ((cur_item= indexed_fields_it++))
782
possible_keys&= cur_item->field->part_of_key;
785
if (possible_keys.any())
786
join_tab->const_keys|= possible_keys;
790
Compare two JoinTable objects based on the number of accessed records.
792
@param ptr1 pointer to first JoinTable object
793
@param ptr2 pointer to second JoinTable object
4812
possible_keys.intersect(cur_item->field->part_of_key);
4815
if (!possible_keys.is_clear_all())
4816
join_tab->const_keys.merge(possible_keys);
4820
/*****************************************************************************
4821
Go through all combinations of not marked tables and find the one
4822
which uses least records
4823
*****************************************************************************/
4825
/** Save const tables first as used tables. */
4828
set_position(JOIN *join,uint32_t idx,JOIN_TAB *table,KEYUSE *key)
4830
join->positions[idx].table= table;
4831
join->positions[idx].key=key;
4832
join->positions[idx].records_read=1.0; /* This is a const table */
4833
join->positions[idx].ref_depend_map= 0;
4835
/* Move the const table as down as possible in best_ref */
4836
JOIN_TAB **pos=join->best_ref+idx+1;
4837
JOIN_TAB *next=join->best_ref[idx];
4838
for (;next != table ; pos++)
4840
JOIN_TAB *tmp=pos[0];
4844
join->best_ref[idx]=table;
4849
Given a semi-join nest, find out which of the IN-equalities are bound
4852
get_bound_sj_equalities()
4853
sj_nest Semi-join nest
4854
remaining_tables Tables that are not yet bound
4857
Given a semi-join nest, find out which of the IN-equalities have their
4858
left part expression bound (i.e. the said expression doesn't refer to
4859
any of remaining_tables and can be evaluated).
4862
Bitmap of bound IN-equalities.
4865
uint64_t get_bound_sj_equalities(TableList *sj_nest,
4866
table_map remaining_tables)
4868
List_iterator<Item> li(sj_nest->nested_join->sj_outer_expr_list);
4872
while ((item= li++))
4875
Q: should this take into account equality propagation and how?
4876
A: If e->outer_side is an Item_field, walk over the equality
4877
class and see if there is an element that is bound?
4878
(this is an optional feature)
4880
if (!(item->used_tables() & remaining_tables))
4890
Find the best access path for an extension of a partial execution
4891
plan and add this path to the plan.
4893
The function finds the best access path to table 's' from the passed
4894
partial plan where an access path is the general term for any means to
4895
access the data in 's'. An access path may use either an index or a scan,
4896
whichever is cheaper. The input partial plan is passed via the array
4897
'join->positions' of length 'idx'. The chosen access method for 's' and its
4898
cost are stored in 'join->positions[idx]'.
4900
@param join pointer to the structure providing all context info
4902
@param s the table to be joined by the function
4903
@param session thread for the connection that submitted the query
4904
@param remaining_tables set of tables not included into the partial plan yet
4905
@param idx the length of the partial plan
4906
@param record_count estimate for the number of records returned by the
4908
@param read_time the cost of the partial plan
4915
best_access_path(JOIN *join,
4918
table_map remaining_tables,
4920
double record_count,
4923
KEYUSE *best_key= 0;
4924
uint32_t best_max_key_part= 0;
4925
bool found_constraint= 0;
4926
double best= DBL_MAX;
4927
double best_time= DBL_MAX;
4928
double records= DBL_MAX;
4929
table_map best_ref_depends_map= 0;
4932
uint32_t best_is_sj_inside_out= 0;
4935
{ /* Use key if possible */
4936
Table *table= s->table;
4937
KEYUSE *keyuse,*start_key=0;
4938
double best_records= DBL_MAX;
4939
uint32_t max_key_part=0;
4940
uint64_t bound_sj_equalities= 0;
4941
bool try_sj_inside_out= false;
4943
Discover the bound equalites. We need to do this, if
4944
1. The next table is an SJ-inner table, and
4945
2. It is the first table from that semijoin, and
4946
3. We're not within a semi-join range (i.e. all semi-joins either have
4947
all or none of their tables in join_table_map), except
4948
s->emb_sj_nest (which we've just entered).
4949
3. All correlation references from this sj-nest are bound
4951
if (s->emb_sj_nest && // (1)
4952
s->emb_sj_nest->sj_in_exprs < 64 &&
4953
((remaining_tables & s->emb_sj_nest->sj_inner_tables) == // (2)
4954
s->emb_sj_nest->sj_inner_tables) && // (2)
4955
join->cur_emb_sj_nests == s->emb_sj_nest->sj_inner_tables && // (3)
4956
!(remaining_tables & s->emb_sj_nest->nested_join->sj_corr_tables)) // (4)
4958
/* This table is an InsideOut scan candidate */
4959
bound_sj_equalities= get_bound_sj_equalities(s->emb_sj_nest,
4961
try_sj_inside_out= true;
4964
/* Test how we can use keys */
4965
rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key
4966
for (keyuse=s->keyuse ; keyuse->table == table ;)
4968
key_part_map found_part= 0;
4969
table_map found_ref= 0;
4970
uint32_t key= keyuse->key;
4971
KEY *keyinfo= table->key_info+key;
4972
/* Bitmap of keyparts where the ref access is over 'keypart=const': */
4973
key_part_map const_part= 0;
4974
/* The or-null keypart in ref-or-null access: */
4975
key_part_map ref_or_null_part= 0;
4977
/* Calculate how many key segments of the current key we can use */
4979
uint64_t handled_sj_equalities=0;
4980
key_part_map sj_insideout_map= 0;
4982
do /* For each keypart */
4984
uint32_t keypart= keyuse->keypart;
4985
table_map best_part_found_ref= 0;
4986
double best_prev_record_reads= DBL_MAX;
4988
do /* For each way to access the keypart */
4992
if 1. expression doesn't refer to forward tables
4993
2. we won't get two ref-or-null's
4995
if (!(remaining_tables & keyuse->used_tables) &&
4996
!(ref_or_null_part && (keyuse->optimize &
4997
KEY_OPTIMIZE_REF_OR_NULL)))
4999
found_part|= keyuse->keypart_map;
5000
if (!(keyuse->used_tables & ~join->const_table_map))
5001
const_part|= keyuse->keypart_map;
5003
double tmp2= prev_record_reads(join, idx, (found_ref |
5004
keyuse->used_tables));
5005
if (tmp2 < best_prev_record_reads)
5007
best_part_found_ref= keyuse->used_tables & ~join->const_table_map;
5008
best_prev_record_reads= tmp2;
5010
if (rec > keyuse->ref_table_rows)
5011
rec= keyuse->ref_table_rows;
5013
If there is one 'key_column IS NULL' expression, we can
5014
use this ref_or_null optimisation of this field
5016
if (keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL)
5017
ref_or_null_part |= keyuse->keypart_map;
5020
if (try_sj_inside_out && keyuse->sj_pred_no != UINT_MAX)
5022
if (!(remaining_tables & keyuse->used_tables))
5023
bound_sj_equalities |= 1UL << keyuse->sj_pred_no;
5026
handled_sj_equalities |= 1UL << keyuse->sj_pred_no;
5027
sj_insideout_map |= ((key_part_map)1) << keyuse->keypart;
5032
} while (keyuse->table == table && keyuse->key == key &&
5033
keyuse->keypart == keypart);
5034
found_ref|= best_part_found_ref;
5035
} while (keyuse->table == table && keyuse->key == key);
5038
Assume that that each key matches a proportional part of table.
5040
if (!found_part && !handled_sj_equalities)
5041
continue; // Nothing usable found
5043
if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
5044
rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables
5046
bool sj_inside_out_scan= false;
5048
found_constraint= 1;
5050
Check if InsideOut scan is applicable:
5051
1. All IN-equalities are either "bound" or "handled"
5052
2. Index keyparts are
5055
if (try_sj_inside_out &&
5056
table->covering_keys.is_set(key) &&
5057
(handled_sj_equalities | bound_sj_equalities) == // (1)
5058
PREV_BITS(uint64_t, s->emb_sj_nest->sj_in_exprs)) // (1)
5060
uint32_t n_fixed_parts= max_part_bit(found_part);
5061
if (n_fixed_parts != keyinfo->key_parts &&
5062
(PREV_BITS(uint, n_fixed_parts) | sj_insideout_map) ==
5063
PREV_BITS(uint, keyinfo->key_parts))
5066
Not all parts are fixed. Produce bitmap of remaining bits and
5067
check if all of them are covered.
5069
sj_inside_out_scan= true;
5073
It's a confluent ref scan.
5075
That is, all found KEYUSE elements refer to IN-equalities,
5076
and there is really no ref access because there is no
5077
t.keypart0 = {bound expression}
5079
Calculate the cost of complete loose index scan.
5081
records= (double)s->table->file->stats.records;
5083
/* The cost is entire index scan cost (divided by 2) */
5084
best_time= s->table->file->index_only_read_time(key, records);
5086
/* Now figure how many different keys we will get */
5088
if ((rpc= keyinfo->rec_per_key[keyinfo->key_parts-1]))
5089
records= records / rpc;
5096
Check if we found full key
5098
if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&
5101
max_key_part= UINT32_MAX;
5102
if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
5104
tmp = prev_record_reads(join, idx, found_ref);
5110
{ /* We found a const key */
5112
ReuseRangeEstimateForRef-1:
5113
We get here if we've found a ref(const) (c_i are constants):
5114
"(keypart1=c1) AND ... AND (keypartN=cN)" [ref_const_cond]
5116
If range optimizer was able to construct a "range"
5117
access on this index, then its condition "quick_cond" was
5118
eqivalent to ref_const_cond (*), and we can re-use E(#rows)
5119
from the range optimizer.
5121
Proof of (*): By properties of range and ref optimizers
5122
quick_cond will be equal or tighther than ref_const_cond.
5123
ref_const_cond already covers "smallest" possible interval -
5124
a singlepoint interval over all keyparts. Therefore,
5125
quick_cond is equivalent to ref_const_cond (if it was an
5126
empty interval we wouldn't have got here).
5128
if (table->quick_keys.is_set(key))
5129
records= (double) table->quick_rows[key];
5132
/* quick_range couldn't use key! */
5133
records= (double) s->records/rec;
5138
if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
5139
{ /* Prefer longer keys */
5141
((double) s->records / (double) rec *
5143
((double) (table->s->max_key_length-keyinfo->key_length) /
5144
(double) table->s->max_key_length)));
5146
records=2.0; /* Can't be as good as a unique */
5149
ReuseRangeEstimateForRef-2: We get here if we could not reuse
5150
E(#rows) from range optimizer. Make another try:
5152
If range optimizer produced E(#rows) for a prefix of the ref
5153
access we're considering, and that E(#rows) is lower then our
5154
current estimate, make an adjustment. The criteria of when we
5155
can make an adjustment is a special case of the criteria used
5156
in ReuseRangeEstimateForRef-3.
5158
if (table->quick_keys.is_set(key) &&
5159
const_part & (1 << table->quick_key_parts[key]) &&
5160
table->quick_n_ranges[key] == 1 &&
5161
records > (double) table->quick_rows[key])
5163
records= (double) table->quick_rows[key];
5166
/* Limit the number of matched rows */
5168
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
5169
if (table->covering_keys.is_set(key))
5171
/* we can use only index tree */
5172
tmp= record_count * table->file->index_only_read_time(key, tmp);
5175
tmp= record_count*cmin(tmp,s->worst_seeks);
5181
Use as much key-parts as possible and a uniq key is better
5182
than a not unique key
5183
Set tmp to (previous record count) * (records / combination)
5185
if ((found_part & 1) &&
5186
(!(table->file->index_flags(key, 0, 0) & HA_ONLY_WHOLE_INDEX) ||
5187
found_part == PREV_BITS(uint,keyinfo->key_parts)))
5189
max_key_part= max_part_bit(found_part);
5191
ReuseRangeEstimateForRef-3:
5192
We're now considering a ref[or_null] access via
5193
(t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR
5194
(same-as-above but with one cond replaced
5195
with "t.keypart_i IS NULL")] (**)
5197
Try re-using E(#rows) from "range" optimizer:
5198
We can do so if "range" optimizer used the same intervals as
5199
in (**). The intervals used by range optimizer may be not
5200
available at this point (as "range" access might have choosen to
5201
create quick select over another index), so we can't compare
5202
them to (**). We'll make indirect judgements instead.
5203
The sufficient conditions for re-use are:
5204
(C1) All e_i in (**) are constants, i.e. found_ref==false. (if
5205
this is not satisfied we have no way to know which ranges
5206
will be actually scanned by 'ref' until we execute the
5208
(C2) max #key parts in 'range' access == K == max_key_part (this
5209
is apparently a necessary requirement)
5211
We also have a property that "range optimizer produces equal or
5212
tighter set of scan intervals than ref(const) optimizer". Each
5213
of the intervals in (**) are "tightest possible" intervals when
5214
one limits itself to using keyparts 1..K (which we do in #2).
5215
From here it follows that range access used either one, or
5216
both of the (I1) and (I2) intervals:
5218
(t.keypart1=c1 AND ... AND t.keypartK=eK) (I1)
5219
(same-as-above but with one cond replaced
5220
with "t.keypart_i IS NULL") (I2)
5222
The remaining part is to exclude the situation where range
5223
optimizer used one interval while we're considering
5224
ref-or-null and looking for estimate for two intervals. This
5225
is done by last limitation:
5227
(C3) "range optimizer used (have ref_or_null?2:1) intervals"
5229
if (table->quick_keys.is_set(key) && !found_ref && //(C1)
5230
table->quick_key_parts[key] == max_key_part && //(C2)
5231
table->quick_n_ranges[key] == 1+((ref_or_null_part)?1:0)) //(C3)
5233
tmp= records= (double) table->quick_rows[key];
5237
/* Check if we have statistic about the distribution */
5238
if ((records= keyinfo->rec_per_key[max_key_part-1]))
5241
Fix for the case where the index statistics is too
5243
(1) We're considering ref(const) and there is quick select
5245
(2) and that quick select uses more keyparts (i.e. it will
5246
scan equal/smaller interval then this ref(const))
5247
(3) and E(#rows) for quick select is higher then our
5250
We'll use E(#rows) from quick select.
5252
Q: Why do we choose to use 'ref'? Won't quick select be
5253
cheaper in some cases ?
5254
TODO: figure this out and adjust the plan choice if needed.
5256
if (!found_ref && table->quick_keys.is_set(key) && // (1)
5257
table->quick_key_parts[key] > max_key_part && // (2)
5258
records < (double)table->quick_rows[key]) // (3)
5259
records= (double)table->quick_rows[key];
5266
Assume that the first key part matches 1% of the file
5267
and that the whole key matches 10 (duplicates) or 1
5269
Assume also that more key matches proportionally more
5271
This gives the formula:
5272
records = (x * (b-a) + a*c-b)/(c-1)
5274
b = records matched by whole key
5275
a = records matched by first key part (1% of all records?)
5276
c = number of key parts in key
5277
x = used key parts (1 <= x <= c)
5280
if (!(rec_per_key=(double)
5281
keyinfo->rec_per_key[keyinfo->key_parts-1]))
5282
rec_per_key=(double) s->records/rec+1;
5286
else if (rec_per_key/(double) s->records >= 0.01)
5290
double a=s->records*0.01;
5291
if (keyinfo->key_parts > 1)
5292
tmp= (max_key_part * (rec_per_key - a) +
5293
a*keyinfo->key_parts - rec_per_key)/
5294
(keyinfo->key_parts-1);
5297
set_if_bigger(tmp,1.0);
5299
records = (uint32_t) tmp;
5302
if (ref_or_null_part)
5304
/* We need to do two key searches to find key */
5310
ReuseRangeEstimateForRef-4: We get here if we could not reuse
5311
E(#rows) from range optimizer. Make another try:
5313
If range optimizer produced E(#rows) for a prefix of the ref
5314
access we're considering, and that E(#rows) is lower then our
5315
current estimate, make the adjustment.
5317
The decision whether we can re-use the estimate from the range
5318
optimizer is the same as in ReuseRangeEstimateForRef-3,
5319
applied to first table->quick_key_parts[key] key parts.
5321
if (table->quick_keys.is_set(key) &&
5322
table->quick_key_parts[key] <= max_key_part &&
5323
const_part & (1 << table->quick_key_parts[key]) &&
5324
table->quick_n_ranges[key] == 1 + ((ref_or_null_part &
5325
const_part) ? 1 : 0) &&
5326
records > (double) table->quick_rows[key])
5328
tmp= records= (double) table->quick_rows[key];
5332
/* Limit the number of matched rows */
5333
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
5334
if (table->covering_keys.is_set(key))
5336
/* we can use only index tree */
5337
tmp= record_count * table->file->index_only_read_time(key, tmp);
5340
tmp= record_count * cmin(tmp,s->worst_seeks);
5343
tmp= best_time; // Do nothing
5346
if (sj_inside_out_scan && !start_key)
5354
if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
5356
best_time= tmp + records/(double) TIME_FOR_COMPARE;
5358
best_records= records;
5359
best_key= start_key;
5360
best_max_key_part= max_key_part;
5361
best_ref_depends_map= found_ref;
5362
best_is_sj_inside_out= sj_inside_out_scan;
5365
records= best_records;
5369
Don't test table scan if it can't be better.
5370
Prefer key lookup if we would use the same key for scanning.
5372
Don't do a table scan on InnoDB tables, if we can read the used
5373
parts of the row from any of the used index.
5374
This is because table scans uses index and we would not win
5375
anything by using a table scan.
5377
A word for word translation of the below if-statement in sergefp's
5378
understanding: we check if we should use table scan if:
5379
(1) The found 'ref' access produces more records than a table scan
5380
(or index scan, or quick select), or 'ref' is more expensive than
5382
(2) This doesn't hold: the best way to perform table scan is to to perform
5383
'range' access using index IDX, and the best way to perform 'ref'
5384
access is to use the same index IDX, with the same or more key parts.
5385
(note: it is not clear how this rule is/should be extended to
5386
index_merge quick selects)
5387
(3) See above note about InnoDB.
5388
(4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access
5389
path, but there is no quick select)
5390
If the condition in the above brackets holds, then the only possible
5391
"table scan" access method is ALL/index (there is no quick select).
5392
Since we have a 'ref' access path, and FORCE INDEX instructs us to
5393
choose it over ALL/index, there is no need to consider a full table
5396
if ((records >= s->found_records || best > s->read_time) && // (1)
5397
!(s->quick && best_key && s->quick->index == best_key->key && // (2)
5398
best_max_key_part >= s->table->quick_key_parts[best_key->key]) &&// (2)
5399
!((s->table->file->ha_table_flags() & HA_TABLE_SCAN_ON_INDEX) && // (3)
5400
! s->table->covering_keys.is_clear_all() && best_key && !s->quick) &&// (3)
5401
!(s->table->force_index && best_key && !s->quick)) // (4)
5402
{ // Check full join
5403
ha_rows rnd_records= s->found_records;
5405
If there is a filtering condition on the table (i.e. ref analyzer found
5406
at least one "table.keyXpartY= exprZ", where exprZ refers only to tables
5407
preceding this table in the join order we're now considering), then
5408
assume that 25% of the rows will be filtered out by this condition.
5410
This heuristic is supposed to force tables used in exprZ to be before
5411
this table in join order.
5413
if (found_constraint)
5414
rnd_records-= rnd_records/4;
5417
If applicable, get a more accurate estimate. Don't use the two
5420
if (s->table->quick_condition_rows != s->found_records)
5421
rnd_records= s->table->quick_condition_rows;
5424
Range optimizer never proposes a RANGE if it isn't better
5425
than FULL: so if RANGE is present, it's always preferred to FULL.
5426
Here we estimate its cost.
5432
- read record range through 'quick'
5433
- skip rows which does not satisfy WHERE constraints
5435
We take into account possible use of join cache for ALL/index
5436
access (see first else-branch below), but we don't take it into
5437
account here for range/index_merge access. Find out why this is so.
5440
(s->quick->read_time +
5441
(s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
5445
/* Estimate cost of reading table. */
5446
tmp= s->table->file->scan_time();
5447
if (s->table->map & join->outer_join) // Can't use join cache
5450
For each record we have to:
5451
- read the whole table record
5452
- skip rows which does not satisfy join condition
5456
(s->records - rnd_records)/(double) TIME_FOR_COMPARE);
5460
/* We read the table as many times as join buffer becomes full. */
5461
tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
5463
(double) session->variables.join_buff_size));
5465
We don't make full cartesian product between rows in the scanned
5466
table and existing records because we skip all rows from the
5467
scanned table, which does not satisfy join condition when
5468
we read the table (see flush_cached_records for details). Here we
5469
take into account cost to read and skip these records.
5471
tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
5476
We estimate the cost of evaluating WHERE clause for found records
5477
as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus
5478
tmp give us total cost of using Table SCAN
5480
if (best == DBL_MAX ||
5481
(tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records <
5482
best + record_count/(double) TIME_FOR_COMPARE*records))
5485
If the table has a range (s->quick is set) make_join_select()
5486
will ensure that this will be used
5489
records= rows2double(rnd_records);
5491
/* range/index_merge/ALL/index access method are "independent", so: */
5492
best_ref_depends_map= 0;
5493
best_is_sj_inside_out= false;
5497
/* Update the cost information for the current partial plan */
5498
join->positions[idx].records_read= records;
5499
join->positions[idx].read_time= best;
5500
join->positions[idx].key= best_key;
5501
join->positions[idx].table= s;
5502
join->positions[idx].ref_depend_map= best_ref_depends_map;
5503
join->positions[idx].use_insideout_scan= best_is_sj_inside_out;
5506
idx == join->const_tables &&
5507
s->table == join->sort_by_table &&
5508
join->unit->select_limit_cnt >= records)
5509
join->sort_by_table= (Table*) 1; // Must use temporary table
5516
Selects and invokes a search strategy for an optimal query plan.
5518
The function checks user-configurable parameters that control the search
5519
strategy for an optimal plan, selects the search method and then invokes
5520
it. Each specific optimization procedure stores the final optimal plan in
5521
the array 'join->best_positions', and the cost of the plan in
5524
@param join pointer to the structure providing all context info for
5526
@param join_tables set of the tables in the query
5529
'MAX_TABLES+2' denotes the old implementation of find_best before
5530
the greedy version. Will be removed when greedy_search is approved.
5539
choose_plan(JOIN *join, table_map join_tables)
5541
uint32_t search_depth= join->session->variables.optimizer_search_depth;
5542
uint32_t prune_level= join->session->variables.optimizer_prune_level;
5543
bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
5545
join->cur_embedding_map= 0;
5546
reset_nj_counters(join->join_list);
5548
if (SELECT_STRAIGHT_JOIN option is set)
5549
reorder tables so dependent tables come after tables they depend
5550
on, otherwise keep tables in the order they were specified in the query
5552
Apply heuristic: pre-sort all access plans with respect to the number of
5555
my_qsort(join->best_ref + join->const_tables,
5556
join->tables - join->const_tables, sizeof(JOIN_TAB*),
5557
straight_join ? join_tab_cmp_straight : join_tab_cmp);
5558
join->cur_emb_sj_nests= 0;
5561
optimize_straight_join(join, join_tables);
5565
if (search_depth == MAX_TABLES+2)
5567
TODO: 'MAX_TABLES+2' denotes the old implementation of find_best before
5568
the greedy version. Will be removed when greedy_search is approved.
5570
join->best_read= DBL_MAX;
5571
if (find_best(join, join_tables, join->const_tables, 1.0, 0.0))
5576
if (search_depth == 0)
5577
/* Automatically determine a reasonable value for 'search_depth' */
5578
search_depth= determine_search_depth(join);
5579
if (greedy_search(join, join_tables, search_depth, prune_level))
5585
Store the cost of this query into a user variable
5586
Don't update last_query_cost for statements that are not "flat joins" :
5587
i.e. they have subqueries, unions or call stored procedures.
5588
TODO: calculate a correct cost for a query with subqueries and UNIONs.
5590
if (join->session->lex->is_single_level_stmt())
5591
join->session->status_var.last_query_cost= join->best_read;
5597
Compare two JOIN_TAB objects based on the number of accessed records.
5599
@param ptr1 pointer to first JOIN_TAB object
5600
@param ptr2 pointer to second JOIN_TAB object
796
5603
The order relation implemented by join_tab_cmp() is not transitive,
5655
Heuristic procedure to automatically guess a reasonable degree of
5656
exhaustiveness for the greedy search procedure.
5658
The procedure estimates the optimization time and selects a search depth
5659
big enough to result in a near-optimal QEP, that doesn't take too long to
5660
find. If the number of tables in the query exceeds some constant, then
5661
search_depth is set to this constant.
5663
@param join pointer to the structure providing all context info for
5667
This is an extremely simplistic implementation that serves as a stub for a
5668
more advanced analysis of the join. Ideally the search depth should be
5669
determined by learning from previous query optimizations, because it will
5670
depend on the CPU power (and other factors).
5673
this value should be determined dynamically, based on statistics:
5674
uint32_t max_tables_for_exhaustive_opt= 7;
5677
this value could be determined by some mapping of the form:
5678
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
5681
A positive integer that specifies the search depth (and thus the
5682
exhaustiveness) of the depth-first search algorithm used by
5687
determine_search_depth(JOIN *join)
5689
uint32_t table_count= join->tables - join->const_tables;
5690
uint32_t search_depth;
5691
/* TODO: this value should be determined dynamically, based on statistics: */
5692
uint32_t max_tables_for_exhaustive_opt= 7;
5694
if (table_count <= max_tables_for_exhaustive_opt)
5695
search_depth= table_count+1; // use exhaustive for small number of tables
5698
TODO: this value could be determined by some mapping of the form:
5699
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
5701
search_depth= max_tables_for_exhaustive_opt; // use greedy search
5703
return search_depth;
5708
Select the best ways to access the tables in a query without reordering them.
5710
Find the best access paths for each query table and compute their costs
5711
according to their order in the array 'join->best_ref' (thus without
5712
reordering the join tables). The function calls sequentially
5713
'best_access_path' for each table in the query to select the best table
5714
access method. The final optimal plan is stored in the array
5715
'join->best_positions', and the corresponding cost in 'join->best_read'.
5717
@param join pointer to the structure providing all context info for
5719
@param join_tables set of the tables in the query
5722
This function can be applied to:
5723
- queries with STRAIGHT_JOIN
5724
- internally to compute the cost of an arbitrary QEP
5726
Thus 'optimize_straight_join' can be used at any stage of the query
5727
optimization process to finalize a QEP as it is.
5731
optimize_straight_join(JOIN *join, table_map join_tables)
5734
uint32_t idx= join->const_tables;
5735
double record_count= 1.0;
5736
double read_time= 0.0;
5738
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
5740
/* Find the best access method from 's' to the current partial plan */
5741
advance_sj_state(join_tables, s);
5742
best_access_path(join, s, join->session, join_tables, idx,
5743
record_count, read_time);
5744
/* compute the cost of the new plan extended with 's' */
5745
record_count*= join->positions[idx].records_read;
5746
read_time+= join->positions[idx].read_time;
5747
join_tables&= ~(s->table->map);
5751
read_time+= record_count / (double) TIME_FOR_COMPARE;
5752
if (join->sort_by_table &&
5753
join->sort_by_table != join->positions[join->const_tables].table->table)
5754
read_time+= record_count; // We have to make a temp table
5755
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
5756
join->best_read= read_time;
5761
Find a good, possibly optimal, query execution plan (QEP) by a greedy search.
5763
The search procedure uses a hybrid greedy/exhaustive search with controlled
5764
exhaustiveness. The search is performed in N = card(remaining_tables)
5765
steps. Each step evaluates how promising is each of the unoptimized tables,
5766
selects the most promising table, and extends the current partial QEP with
5767
that table. Currenly the most 'promising' table is the one with least
5768
expensive extension.\
5770
There are two extreme cases:
5771
-# When (card(remaining_tables) < search_depth), the estimate finds the
5772
best complete continuation of the partial QEP. This continuation can be
5773
used directly as a result of the search.
5774
-# When (search_depth == 1) the 'best_extension_by_limited_search'
5775
consideres the extension of the current QEP with each of the remaining
5778
All other cases are in-between these two extremes. Thus the parameter
5779
'search_depth' controlls the exhaustiveness of the search. The higher the
5780
value, the longer the optimizaton time and possibly the better the
5781
resulting plan. The lower the value, the fewer alternative plans are
5782
estimated, but the more likely to get a bad QEP.
5784
All intermediate and final results of the procedure are stored in 'join':
5785
- join->positions : modified for every partial QEP that is explored
5786
- join->best_positions: modified for the current best complete QEP
5787
- join->best_read : modified for the current best complete QEP
5788
- join->best_ref : might be partially reordered
5790
The final optimal plan is stored in 'join->best_positions', and its
5791
corresponding cost in 'join->best_read'.
5794
The following pseudocode describes the algorithm of 'greedy_search':
5797
procedure greedy_search
5798
input: remaining_tables
5803
(t, a) = best_extension(pplan, remaining_tables);
5804
pplan = concat(pplan, (t, a));
5805
remaining_tables = remaining_tables - t;
5806
} while (remaining_tables != {})
5811
where 'best_extension' is a placeholder for a procedure that selects the
5812
most "promising" of all tables in 'remaining_tables'.
5813
Currently this estimate is performed by calling
5814
'best_extension_by_limited_search' to evaluate all extensions of the
5815
current QEP of size 'search_depth', thus the complexity of 'greedy_search'
5816
mainly depends on that of 'best_extension_by_limited_search'.
5819
If 'best_extension()' == 'best_extension_by_limited_search()', then the
5820
worst-case complexity of this algorithm is <=
5821
O(N*N^search_depth/search_depth). When serch_depth >= N, then the
5822
complexity of greedy_search is O(N!).
5825
In the future, 'greedy_search' might be extended to support other
5826
implementations of 'best_extension', e.g. some simpler quadratic procedure.
5828
@param join pointer to the structure providing all context info
5830
@param remaining_tables set of tables not included into the partial plan yet
5831
@param search_depth controlls the exhaustiveness of the search
5832
@param prune_level the pruning heuristics that should be applied during
5842
greedy_search(JOIN *join,
5843
table_map remaining_tables,
5844
uint32_t search_depth,
5845
uint32_t prune_level)
5847
double record_count= 1.0;
5848
double read_time= 0.0;
5849
uint32_t idx= join->const_tables; // index into 'join->best_ref'
5851
uint32_t size_remain; // cardinality of remaining_tables
5853
JOIN_TAB *best_table; // the next plan node to be added to the curr QEP
5855
/* number of tables that remain to be optimized */
5856
size_remain= my_count_bits(remaining_tables);
5859
/* Find the extension of the current QEP with the lowest cost */
5860
join->best_read= DBL_MAX;
5861
if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,
5862
read_time, search_depth, prune_level))
5865
if (size_remain <= search_depth)
5868
'join->best_positions' contains a complete optimal extension of the
5869
current partial QEP.
5874
/* select the first table in the optimal extension as most promising */
5875
best_pos= join->best_positions[idx];
5876
best_table= best_pos.table;
5878
Each subsequent loop of 'best_extension_by_limited_search' uses
5879
'join->positions' for cost estimates, therefore we have to update its
5882
join->positions[idx]= best_pos;
5884
/* find the position of 'best_table' in 'join->best_ref' */
5886
JOIN_TAB *pos= join->best_ref[best_idx];
5887
while (pos && best_table != pos)
5888
pos= join->best_ref[++best_idx];
5889
assert((pos != NULL)); // should always find 'best_table'
5890
/* move 'best_table' at the first free position in the array of joins */
5891
std::swap(join->best_ref[idx], join->best_ref[best_idx]);
5893
/* compute the cost of the new plan extended with 'best_table' */
5894
record_count*= join->positions[idx].records_read;
5895
read_time+= join->positions[idx].read_time;
5897
remaining_tables&= ~(best_table->table->map);
5905
Find a good, possibly optimal, query execution plan (QEP) by a possibly
5908
The procedure searches for the optimal ordering of the query tables in set
5909
'remaining_tables' of size N, and the corresponding optimal access paths to
5910
each table. The choice of a table order and an access path for each table
5911
constitutes a query execution plan (QEP) that fully specifies how to
5914
The maximal size of the found plan is controlled by the parameter
5915
'search_depth'. When search_depth == N, the resulting plan is complete and
5916
can be used directly as a QEP. If search_depth < N, the found plan consists
5917
of only some of the query tables. Such "partial" optimal plans are useful
5918
only as input to query optimization procedures, and cannot be used directly
5921
The algorithm begins with an empty partial plan stored in 'join->positions'
5922
and a set of N tables - 'remaining_tables'. Each step of the algorithm
5923
evaluates the cost of the partial plan extended by all access plans for
5924
each of the relations in 'remaining_tables', expands the current partial
5925
plan with the access plan that results in lowest cost of the expanded
5926
partial plan, and removes the corresponding relation from
5927
'remaining_tables'. The algorithm continues until it either constructs a
5928
complete optimal plan, or constructs an optimal plartial plan with size =
5931
The final optimal plan is stored in 'join->best_positions'. The
5932
corresponding cost of the optimal plan is in 'join->best_read'.
5935
The procedure uses a recursive depth-first search where the depth of the
5936
recursion (and thus the exhaustiveness of the search) is controlled by the
5937
parameter 'search_depth'.
5940
The pseudocode below describes the algorithm of
5941
'best_extension_by_limited_search'. The worst-case complexity of this
5942
algorithm is O(N*N^search_depth/search_depth). When serch_depth >= N, then
5943
the complexity of greedy_search is O(N!).
5946
procedure best_extension_by_limited_search(
5947
pplan in, // in, partial plan of tables-joined-so-far
5948
pplan_cost, // in, cost of pplan
5949
remaining_tables, // in, set of tables not referenced in pplan
5950
best_plan_so_far, // in/out, best plan found so far
5951
best_plan_so_far_cost,// in/out, cost of best_plan_so_far
5952
search_depth) // in, maximum size of the plans being considered
5954
for each table T from remaining_tables
5956
// Calculate the cost of using table T as above
5957
cost = complex-series-of-calculations;
5959
// Add the cost to the cost so far.
5962
if (pplan_cost >= best_plan_so_far_cost)
5963
// pplan_cost already too great, stop search
5966
pplan= expand pplan by best_access_method;
5967
remaining_tables= remaining_tables - table T;
5968
if (remaining_tables is not an empty set
5972
best_extension_by_limited_search(pplan, pplan_cost,
5975
best_plan_so_far_cost,
5980
best_plan_so_far_cost= pplan_cost;
5981
best_plan_so_far= pplan;
5988
When 'best_extension_by_limited_search' is called for the first time,
5989
'join->best_read' must be set to the largest possible value (e.g. DBL_MAX).
5990
The actual implementation provides a way to optionally use pruning
5991
heuristic (controlled by the parameter 'prune_level') to reduce the search
5992
space by skipping some partial plans.
5995
The parameter 'search_depth' provides control over the recursion
5996
depth, and thus the size of the resulting optimal plan.
5998
@param join pointer to the structure providing all context info
6000
@param remaining_tables set of tables not included into the partial plan yet
6001
@param idx length of the partial QEP in 'join->positions';
6002
since a depth-first search is used, also corresponds
6003
to the current depth of the search tree;
6004
also an index in the array 'join->best_ref';
6005
@param record_count estimate for the number of records returned by the
6007
@param read_time the cost of the best partial plan
6008
@param search_depth maximum depth of the recursion and thus size of the
6010
(0 < search_depth <= join->tables+1).
6011
@param prune_level pruning heuristics that should be applied during
6013
(values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS)
6022
best_extension_by_limited_search(JOIN *join,
6023
table_map remaining_tables,
6025
double record_count,
6027
uint32_t search_depth,
6028
uint32_t prune_level)
6030
Session *session= join->session;
6031
if (session->killed) // Abort
6035
'join' is a partial plan with lower cost than the best plan so far,
6036
so continue expanding it further with the tables in 'remaining_tables'.
6039
double best_record_count= DBL_MAX;
6040
double best_read_time= DBL_MAX;
6042
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
6044
table_map real_table_bit= s->table->map;
6045
if ((remaining_tables & real_table_bit) &&
6046
!(remaining_tables & s->dependent) &&
6047
(!idx || !check_interleaving_with_nj(join->positions[idx-1].table, s)))
6049
double current_record_count, current_read_time;
6050
advance_sj_state(remaining_tables, s);
6053
psergey-insideout-todo:
6054
when best_access_path() detects it could do an InsideOut scan or
6055
some other scan, have it return an insideout scan and a flag that
6056
requests to "fork" this loop iteration. (Q: how does that behave
6057
when the depth is insufficient??)
6059
/* Find the best access method from 's' to the current partial plan */
6060
best_access_path(join, s, session, remaining_tables, idx,
6061
record_count, read_time);
6062
/* Compute the cost of extending the plan with 's' */
6063
current_record_count= record_count * join->positions[idx].records_read;
6064
current_read_time= read_time + join->positions[idx].read_time;
6066
/* Expand only partial plans with lower cost than the best QEP so far */
6067
if ((current_read_time +
6068
current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
6070
restore_prev_nj_state(s);
6071
restore_prev_sj_state(remaining_tables, s);
6076
Prune some less promising partial plans. This heuristic may miss
6077
the optimal QEPs, thus it results in a non-exhaustive search.
6079
if (prune_level == 1)
6081
if (best_record_count > current_record_count ||
6082
best_read_time > current_read_time ||
6083
(idx == join->const_tables && s->table == join->sort_by_table)) // 's' is the first table in the QEP
6085
if (best_record_count >= current_record_count &&
6086
best_read_time >= current_read_time &&
6087
/* TODO: What is the reasoning behind this condition? */
6088
(!(s->key_dependent & remaining_tables) ||
6089
join->positions[idx].records_read < 2.0))
6091
best_record_count= current_record_count;
6092
best_read_time= current_read_time;
6097
restore_prev_nj_state(s);
6098
restore_prev_sj_state(remaining_tables, s);
6103
if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )
6104
{ /* Recursively expand the current partial plan */
6105
std::swap(join->best_ref[idx], *pos);
6106
if (best_extension_by_limited_search(join,
6107
remaining_tables & ~real_table_bit,
6109
current_record_count,
6114
std::swap(join->best_ref[idx], *pos);
6118
'join' is either the best partial QEP with 'search_depth' relations,
6119
or the best complete QEP so far, whichever is smaller.
6121
current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
6122
if (join->sort_by_table &&
6123
join->sort_by_table !=
6124
join->positions[join->const_tables].table->table)
6125
/* We have to make a temp table */
6126
current_read_time+= current_record_count;
6127
if ((search_depth == 1) || (current_read_time < join->best_read))
6129
memcpy(join->best_positions, join->positions,
6130
sizeof(POSITION) * (idx + 1));
6131
join->best_read= current_read_time - 0.001;
6134
restore_prev_nj_state(s);
6135
restore_prev_sj_state(remaining_tables, s);
6144
- TODO: this function is here only temporarily until 'greedy_search' is
6145
tested and accepted.
6152
find_best(JOIN *join,table_map rest_tables,uint32_t idx,double record_count,
6155
Session *session= join->session;
6156
if (session->killed)
6160
read_time+=record_count/(double) TIME_FOR_COMPARE;
6161
if (join->sort_by_table &&
6162
join->sort_by_table !=
6163
join->positions[join->const_tables].table->table)
6164
read_time+=record_count; // We have to make a temp table
6165
if (read_time < join->best_read)
6167
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
6168
join->best_read= read_time - 0.001;
6172
if (read_time+record_count/(double) TIME_FOR_COMPARE >= join->best_read)
6173
return(false); /* Found better before */
6176
double best_record_count=DBL_MAX,best_read_time=DBL_MAX;
6177
for (JOIN_TAB **pos=join->best_ref+idx ; (s=*pos) ; pos++)
6179
table_map real_table_bit=s->table->map;
6180
if ((rest_tables & real_table_bit) && !(rest_tables & s->dependent) &&
6181
(!idx|| !check_interleaving_with_nj(join->positions[idx-1].table, s)))
6183
double records, best;
6184
advance_sj_state(rest_tables, s);
6185
best_access_path(join, s, session, rest_tables, idx, record_count,
6187
records= join->positions[idx].records_read;
6188
best= join->positions[idx].read_time;
6190
Go to the next level only if there hasn't been a better key on
6191
this level! This will cut down the search for a lot simple cases!
6193
double current_record_count=record_count*records;
6194
double current_read_time=read_time+best;
6195
if (best_record_count > current_record_count ||
6196
best_read_time > current_read_time ||
6197
(idx == join->const_tables && s->table == join->sort_by_table))
6199
if (best_record_count >= current_record_count &&
6200
best_read_time >= current_read_time &&
6201
(!(s->key_dependent & rest_tables) || records < 2.0))
6203
best_record_count=current_record_count;
6204
best_read_time=current_read_time;
6206
std::swap(join->best_ref[idx], *pos);
6207
if (find_best(join,rest_tables & ~real_table_bit,idx+1,
6208
current_record_count,current_read_time))
6210
std::swap(join->best_ref[idx], *pos);
6212
restore_prev_nj_state(s);
6213
restore_prev_sj_state(rest_tables, s);
6214
if (join->select_options & SELECT_STRAIGHT_JOIN)
6215
break; // Don't test all combinations
845
6223
Find how much space the prevous read not const tables takes in cache.
847
void calc_used_field_length(Session *, JoinTable *join_tab)
6226
static void calc_used_field_length(Session *, JOIN_TAB *join_tab)
849
6228
uint32_t null_fields,blobs,fields,rec_length;
850
6229
Field **f_ptr,*field;
6230
MY_BITMAP *read_set= join_tab->table->read_set;;
852
6232
null_fields= blobs= fields= rec_length=0;
853
for (f_ptr=join_tab->table->getFields() ; (field= *f_ptr) ; f_ptr++)
6233
for (f_ptr=join_tab->table->field ; (field= *f_ptr) ; f_ptr++)
855
if (field->isReadSet())
6235
if (bitmap_is_set(read_set, field->field_index))
857
6237
uint32_t flags=field->flags;
859
6239
rec_length+=field->pack_length();
860
6240
if (flags & BLOB_FLAG)
862
6242
if (!(flags & NOT_NULL_FLAG))
866
6246
if (null_fields)
869
6249
rec_length+=sizeof(bool);
872
uint32_t blob_length=(uint32_t) (join_tab->table->cursor->stats.mean_rec_length-
873
(join_tab->table->getRecordLength()- rec_length));
874
rec_length+= max((uint32_t)4,blob_length);
876
join_tab->used_fields= fields;
877
join_tab->used_fieldlength= rec_length;
878
join_tab->used_blobs= blobs;
881
StoredKey *get_store_key(Session *session,
882
optimizer::KeyUse *keyuse,
883
table_map used_tables,
884
KeyPartInfo *key_part,
885
unsigned char *key_buff,
888
Item_ref *key_use_val= static_cast<Item_ref *>(keyuse->getVal());
889
if (! ((~used_tables) & keyuse->getUsedTables())) // if const item
6252
uint32_t blob_length=(uint32_t) (join_tab->table->file->stats.mean_rec_length-
6253
(join_tab->table->getRecordLength()- rec_length));
6254
rec_length+=(uint32_t) cmax((uint32_t)4,blob_length);
6256
join_tab->used_fields=fields;
6257
join_tab->used_fieldlength=rec_length;
6258
join_tab->used_blobs=blobs;
6263
cache_record_length(JOIN *join,uint32_t idx)
6266
JOIN_TAB **pos,**end;
6267
Session *session=join->session;
6269
for (pos=join->best_ref+join->const_tables,end=join->best_ref+idx ;
6273
JOIN_TAB *join_tab= *pos;
6274
if (!join_tab->used_fieldlength) /* Not calced yet */
6275
calc_used_field_length(session, join_tab);
6276
length+=join_tab->used_fieldlength;
6283
Get the number of different row combinations for subset of partial join
6287
join The join structure
6288
idx Number of tables in the partial join order (i.e. the
6289
partial join order is in join->positions[0..idx-1])
6290
found_ref Bitmap of tables for which we need to find # of distinct
6294
Given a partial join order (in join->positions[0..idx-1]) and a subset of
6295
tables within that join order (specified in found_ref), find out how many
6296
distinct row combinations of subset tables will be in the result of the
6299
This is used as follows: Suppose we have a table accessed with a ref-based
6300
method. The ref access depends on current rows of tables in found_ref.
6301
We want to count # of different ref accesses. We assume two ref accesses
6302
will be different if at least one of access parameters is different.
6303
Example: consider a query
6305
SELECT * FROM t1, t2, t3 WHERE t1.key=c1 AND t2.key=c2 AND t3.key=t1.field
6308
t1, ref access on t1.key=c1
6309
t2, ref access on t2.key=c2
6310
t3, ref access on t3.key=t1.field
6312
For t1: n_ref_scans = 1, n_distinct_ref_scans = 1
6313
For t2: n_ref_scans = records_read(t1), n_distinct_ref_scans=1
6314
For t3: n_ref_scans = records_read(t1)*records_read(t2)
6315
n_distinct_ref_scans = #records_read(t1)
6317
The reason for having this function (at least the latest version of it)
6318
is that we need to account for buffering in join execution.
6320
An edge-case example: if we have a non-first table in join accessed via
6321
ref(const) or ref(param) where there is a small number of different
6322
values of param, then the access will likely hit the disk cache and will
6323
not require any disk seeks.
6325
The proper solution would be to assume an LRU disk cache of some size,
6326
calculate probability of cache hits, etc. For now we just count
6327
identical ref accesses as one.
6330
Expected number of row combinations
6334
prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref)
6337
POSITION *pos_end= join->positions - 1;
6338
for (POSITION *pos= join->positions + idx - 1; pos != pos_end; pos--)
6340
if (pos->table->table->map & found_ref)
6342
found_ref|= pos->ref_depend_map;
6344
For the case of "t1 LEFT JOIN t2 ON ..." where t2 is a const table
6345
with no matching row we will get position[t2].records_read==0.
6346
Actually the size of output is one null-complemented row, therefore
6347
we will use value of 1 whenever we get records_read==0.
6350
- the above case can't occur if inner part of outer join has more
6351
than one table: table with no matches will not be marked as const.
6353
- Ideally we should add 1 to records_read for every possible null-
6354
complemented row. We're not doing it because: 1. it will require
6355
non-trivial code and add overhead. 2. The value of records_read
6356
is an inprecise estimate and adding 1 (or, in the worst case,
6357
#max_nested_outer_joins=64-1) will not make it any more precise.
6359
if (pos->records_read > DBL_EPSILON)
6360
found*= pos->records_read;
6368
Set up join struct according to best position.
6372
get_best_combination(JOIN *join)
6375
table_map used_tables;
6376
JOIN_TAB *join_tab,*j;
6378
uint32_t table_count;
6379
Session *session=join->session;
6381
table_count=join->tables;
6382
if (!(join->join_tab=join_tab=
6383
(JOIN_TAB*) session->alloc(sizeof(JOIN_TAB)*table_count)))
6388
used_tables= OUTER_REF_TABLE_BIT; // Outer row is already read
6389
for (j=join_tab, tablenr=0 ; tablenr < table_count ; tablenr++,j++)
6392
*j= *join->best_positions[tablenr].table;
6393
form=join->table[tablenr]=j->table;
6394
used_tables|= form->map;
6395
form->reginfo.join_tab=j;
6396
if (!*j->on_expr_ref)
6397
form->reginfo.not_exists_optimize=0; // Only with LEFT JOIN
6398
if (j->type == JT_CONST)
6399
continue; // Handled in make_join_stat..
6404
if (j->type == JT_SYSTEM)
6406
if (j->keys.is_clear_all() || !(keyuse= join->best_positions[tablenr].key))
6409
if (tablenr != join->const_tables)
6412
else if (create_ref_for_key(join, j, keyuse, used_tables))
6413
return(true); // Something went wrong
6416
for (i=0 ; i < table_count ; i++)
6417
join->map2table[join->join_tab[i].table->tablenr]=join->join_tab+i;
6418
update_depend_map(join);
6423
static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
6424
table_map used_tables)
6426
KEYUSE *keyuse=org_keyuse;
6427
Session *session= join->session;
6428
uint32_t keyparts,length,key;
6432
/* Use best key from find_best */
6435
keyinfo=table->key_info+key;
6439
uint32_t found_part_ref_or_null= 0;
6441
Calculate length for the used key
6442
Stop if there is a missing key part or when we find second key_part
6443
with KEY_OPTIMIZE_REF_OR_NULL
6447
if (!(~used_tables & keyuse->used_tables))
6449
if (keyparts == keyuse->keypart &&
6450
!(found_part_ref_or_null & keyuse->optimize))
6453
length+= keyinfo->key_part[keyuse->keypart].store_length;
6454
found_part_ref_or_null|= keyuse->optimize;
6458
} while (keyuse->table == table && keyuse->key == key);
6461
/* set up fieldref */
6462
keyinfo=table->key_info+key;
6463
j->ref.key_parts=keyparts;
6464
j->ref.key_length=length;
6465
j->ref.key=(int) key;
6466
if (!(j->ref.key_buff= (unsigned char*) session->calloc(ALIGN_SIZE(length)*2)) ||
6467
!(j->ref.key_copy= (store_key**) session->alloc((sizeof(store_key*) *
6469
!(j->ref.items= (Item**) session->alloc(sizeof(Item*)*keyparts)) ||
6470
!(j->ref.cond_guards= (bool**) session->alloc(sizeof(uint*)*keyparts)))
6474
j->ref.key_buff2=j->ref.key_buff+ALIGN_SIZE(length);
6476
j->ref.null_rejecting= 0;
6477
j->ref.disable_cache= false;
6480
store_key **ref_key= j->ref.key_copy;
6481
unsigned char *key_buff=j->ref.key_buff, *null_ref_key= 0;
6482
bool keyuse_uses_no_tables= true;
6485
for (i=0 ; i < keyparts ; keyuse++,i++)
6487
while (keyuse->keypart != i ||
6488
((~used_tables) & keyuse->used_tables))
6489
keyuse++; /* Skip other parts */
6491
uint32_t maybe_null= test(keyinfo->key_part[i].null_bit);
6492
j->ref.items[i]=keyuse->val; // Save for cond removal
6493
j->ref.cond_guards[i]= keyuse->cond_guard;
6494
if (keyuse->null_rejecting)
6495
j->ref.null_rejecting |= 1 << i;
6496
keyuse_uses_no_tables= keyuse_uses_no_tables && !keyuse->used_tables;
6497
if (!keyuse->used_tables &&
6498
!(join->select_options & SELECT_DESCRIBE))
6499
{ // Compare against constant
6500
store_key_item tmp(session, keyinfo->key_part[i].field,
6501
key_buff + maybe_null,
6502
maybe_null ? key_buff : 0,
6503
keyinfo->key_part[i].length, keyuse->val);
6504
if (session->is_fatal_error)
6509
*ref_key++= get_store_key(session,
6510
keyuse,join->const_table_map,
6511
&keyinfo->key_part[i],
6512
key_buff, maybe_null);
6514
Remember if we are going to use REF_OR_NULL
6515
But only if field _really_ can be null i.e. we force JT_REF
6516
instead of JT_REF_OR_NULL in case if field can't be null
6518
if ((keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL) && maybe_null)
6519
null_ref_key= key_buff;
6520
key_buff+=keyinfo->key_part[i].store_length;
6523
*ref_key=0; // end_marker
6524
if (j->type == JT_CONST)
6525
j->table->const_table= 1;
6526
else if (((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) != HA_NOSAME) ||
6527
keyparts != keyinfo->key_parts || null_ref_key)
6529
/* Must read with repeat */
6530
j->type= null_ref_key ? JT_REF_OR_NULL : JT_REF;
6531
j->ref.null_ref_key= null_ref_key;
6533
else if (keyuse_uses_no_tables)
6536
This happen if we are using a constant expression in the ON part
6538
SELECT * FROM a LEFT JOIN b ON b.key=30
6539
Here we should not mark the table as a 'const' as a field may
6540
have a 'normal' value or a NULL value.
6552
get_store_key(Session *session, KEYUSE *keyuse, table_map used_tables,
6553
KEY_PART_INFO *key_part, unsigned char *key_buff, uint32_t maybe_null)
6555
if (!((~used_tables) & keyuse->used_tables)) // if const item
891
6557
return new store_key_const_item(session,
892
6558
key_part->field,
893
6559
key_buff + maybe_null,
894
6560
maybe_null ? key_buff : 0,
895
6561
key_part->length,
898
else if (key_use_val->type() == Item::FIELD_ITEM ||
899
(key_use_val->type() == Item::REF_ITEM &&
900
key_use_val->ref_type() == Item_ref::OUTER_REF &&
901
(*(Item_ref**)((Item_ref*)key_use_val)->ref)->ref_type() == Item_ref::DIRECT_REF &&
902
key_use_val->real_item()->type() == Item::FIELD_ITEM))
6564
else if (keyuse->val->type() == Item::FIELD_ITEM ||
6565
(keyuse->val->type() == Item::REF_ITEM &&
6566
((Item_ref*)keyuse->val)->ref_type() == Item_ref::OUTER_REF &&
6567
(*(Item_ref**)((Item_ref*)keyuse->val)->ref)->ref_type() ==
6568
Item_ref::DIRECT_REF &&
6569
keyuse->val->real_item()->type() == Item::FIELD_ITEM))
904
6570
return new store_key_field(session,
905
6571
key_part->field,
906
6572
key_buff + maybe_null,
907
6573
maybe_null ? key_buff : 0,
908
6574
key_part->length,
909
((Item_field*) key_use_val->real_item())->field,
910
key_use_val->full_name());
6575
((Item_field*) keyuse->val->real_item())->field,
6576
keyuse->val->full_name());
912
6577
return new store_key_item(session,
913
6578
key_part->field,
914
6579
key_buff + maybe_null,
915
6580
maybe_null ? key_buff : 0,
916
6581
key_part->length,
6826
Fill in outer join related info for the execution plan structure.
6828
For each outer join operation left after simplification of the
6829
original query the function set up the following pointers in the linear
6830
structure join->join_tab representing the selected execution plan.
6831
The first inner table t0 for the operation is set to refer to the last
6832
inner table tk through the field t0->last_inner.
6833
Any inner table ti for the operation are set to refer to the first
6834
inner table ti->first_inner.
6835
The first inner table t0 for the operation is set to refer to the
6836
first inner table of the embedding outer join operation, if there is any,
6837
through the field t0->first_upper.
6838
The on expression for the outer join operation is attached to the
6839
corresponding first inner table through the field t0->on_expr_ref.
6840
Here ti are structures of the JOIN_TAB type.
6842
EXAMPLE. For the query:
6846
(t2, t3 LEFT JOIN t4 ON t3.a=t4.a)
6847
ON (t1.a=t2.a AND t1.b=t3.b)
6851
given the execution plan with the table order t1,t2,t3,t4
6852
is selected, the following references will be set;
6853
t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2]
6854
t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2],
6855
on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to
6856
*t2->on_expr_ref, while t3.a=t4.a will be attached to *t4->on_expr_ref.
6858
@param join reference to the info fully describing the query
6861
The function assumes that the simplification procedure has been
6862
already applied to the join query (see simplify_joins).
6863
This function can be called only after the execution plan
6868
make_outerjoin_info(JOIN *join)
6870
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
6872
JOIN_TAB *tab=join->join_tab+i;
6873
Table *table=tab->table;
6874
TableList *tbl= table->pos_in_table_list;
6875
TableList *embedding= tbl->embedding;
6877
if (tbl->outer_join)
6880
Table tab is the only one inner table for outer join.
6881
(Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a
6882
is in the query above.)
6884
tab->last_inner= tab->first_inner= tab;
6885
tab->on_expr_ref= &tbl->on_expr;
6886
tab->cond_equal= tbl->cond_equal;
6888
tab->first_upper= embedding->nested_join->first_nested;
6890
for ( ; embedding ; embedding= embedding->embedding)
6892
/* Ignore sj-nests: */
6893
if (!embedding->on_expr)
6895
nested_join_st *nested_join= embedding->nested_join;
6896
if (!nested_join->counter_)
6899
Table tab is the first inner table for nested_join.
6900
Save reference to it in the nested join structure.
6902
nested_join->first_nested= tab;
6903
tab->on_expr_ref= &embedding->on_expr;
6904
tab->cond_equal= tbl->cond_equal;
6905
if (embedding->embedding)
6906
tab->first_upper= embedding->embedding->nested_join->first_nested;
6908
if (!tab->first_inner)
6909
tab->first_inner= nested_join->first_nested;
6910
if (++nested_join->counter_ < nested_join->join_list.elements)
6912
/* Table tab is the last inner table for nested join. */
6913
nested_join->first_nested->last_inner= tab;
6921
make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
6923
Session *session= join->session;
6926
add_not_null_conds(join);
6927
table_map used_tables;
6928
if (cond) /* Because of QUICK_GROUP_MIN_MAX_SELECT */
6929
{ /* there may be a select without a cond. */
6930
if (join->tables > 1)
6931
cond->update_used_tables(); // Tablenr may have changed
6932
if (join->const_tables == join->tables &&
6933
session->lex->current_select->master_unit() ==
6934
&session->lex->unit) // not upper level SELECT
6935
join->const_table_map|=RAND_TABLE_BIT;
6936
{ // Check const tables
6938
make_cond_for_table(cond,
6939
join->const_table_map,
6941
for (JOIN_TAB *tab= join->join_tab+join->const_tables;
6942
tab < join->join_tab+join->tables ; tab++)
6944
if (*tab->on_expr_ref)
6946
JOIN_TAB *cond_tab= tab->first_inner;
6947
COND *tmp= make_cond_for_table(*tab->on_expr_ref,
6948
join->const_table_map,
6952
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
6955
tmp->quick_fix_field();
6956
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
6957
new Item_cond_and(cond_tab->select_cond,
6959
if (!cond_tab->select_cond)
6961
cond_tab->select_cond->quick_fix_field();
6964
if (const_cond && !const_cond->val_int())
6966
return(1); // Impossible const condition
6970
used_tables=((select->const_tables=join->const_table_map) |
6971
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
6972
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
6974
JOIN_TAB *tab=join->join_tab+i;
6976
first_inner is the X in queries like:
6977
SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X
6979
JOIN_TAB *first_inner_tab= tab->first_inner;
6980
table_map current_map= tab->table->map;
6981
bool use_quick_range=0;
6985
Following force including random expression in last table condition.
6986
It solve problem with select like SELECT * FROM t1 WHERE rand() > 0.5
6988
if (i == join->tables-1)
6989
current_map|= OUTER_REF_TABLE_BIT | RAND_TABLE_BIT;
6990
used_tables|=current_map;
6992
if (tab->type == JT_REF && tab->quick &&
6993
(uint32_t) tab->ref.key == tab->quick->index &&
6994
tab->ref.key_length < tab->quick->max_used_key_length)
6996
/* Range uses longer key; Use this instead of ref on key */
7001
tab->ref.key_parts=0; // Don't use ref key.
7002
join->best_positions[i].records_read= rows2double(tab->quick->records);
7004
We will use join cache here : prevent sorting of the first
7005
table only and sort at the end.
7007
if (i != join->const_tables && join->tables > join->const_tables + 1)
7013
tmp= make_cond_for_table(cond,used_tables,current_map, 0);
7014
if (cond && !tmp && tab->quick)
7016
if (tab->type != JT_ALL)
7019
Don't use the quick method
7020
We come here in the case where we have 'key=constant' and
7021
the test is removed by make_cond_for_table()
7029
Hack to handle the case where we only refer to a table
7030
in the ON part of an OUTER JOIN. In this case we want the code
7031
below to check if we should use 'quick' instead.
7033
tmp= new Item_int((int64_t) 1,1); // Always true
7037
if (tmp || !cond || tab->type == JT_REF || tab->type == JT_REF_OR_NULL ||
7038
tab->type == JT_EQ_REF)
7040
SQL_SELECT *sel= tab->select= ((SQL_SELECT*)
7041
session->memdup((unsigned char*) select,
7044
return(1); // End of memory
7046
If tab is an inner table of an outer join operation,
7047
add a match guard to the pushed down predicate.
7048
The guard will turn the predicate on only after
7049
the first match for outer tables is encountered.
7054
Because of QUICK_GROUP_MIN_MAX_SELECT there may be a select without
7055
a cond, so neutralize the hack above.
7057
if (!(tmp= add_found_match_trig_cond(first_inner_tab, tmp, 0)))
7059
tab->select_cond=sel->cond=tmp;
7060
/* Push condition to storage engine if this is enabled
7061
and the condition is not guarded */
7062
tab->table->file->pushed_cond= NULL;
7063
if (session->variables.engine_condition_pushdown)
7066
make_cond_for_table(tmp, current_map, current_map, 0);
7069
/* Push condition to handler */
7070
if (!tab->table->file->cond_push(push_cond))
7071
tab->table->file->pushed_cond= push_cond;
7076
tab->select_cond= sel->cond= NULL;
7078
sel->head=tab->table;
7081
/* Use quick key read if it's a constant and it's not used
7083
if (tab->needed_reg.is_clear_all() && tab->type != JT_EQ_REF
7084
&& (tab->type != JT_REF || (uint32_t) tab->ref.key == tab->quick->index))
7086
sel->quick=tab->quick; // Use value from get_quick_...
7087
sel->quick_keys.clear_all();
7088
sel->needed_reg.clear_all();
7096
uint32_t ref_key=(uint32_t) sel->head->reginfo.join_tab->ref.key+1;
7097
if (i == join->const_tables && ref_key)
7099
if (!tab->const_keys.is_clear_all() &&
7100
tab->table->reginfo.impossible_range)
7103
else if (tab->type == JT_ALL && ! use_quick_range)
7105
if (!tab->const_keys.is_clear_all() &&
7106
tab->table->reginfo.impossible_range)
7107
return(1); // Impossible range
7109
We plan to scan all rows.
7110
Check again if we should use an index.
7111
We could have used an column from a previous table in
7112
the index if we are using limit and this is the first table
7115
if ((cond && (!tab->keys.is_subset(tab->const_keys) && i > 0)) ||
7116
(!tab->const_keys.is_clear_all() && (i == join->const_tables) && (join->unit->select_limit_cnt < join->best_positions[i].records_read) && ((join->select_options & OPTION_FOUND_ROWS) == false)))
7118
/* Join with outer join condition */
7119
COND *orig_cond=sel->cond;
7120
sel->cond= and_conds(sel->cond, *tab->on_expr_ref);
7123
We can't call sel->cond->fix_fields,
7124
as it will break tab->on_expr if it's AND condition
7125
(fix_fields currently removes extra AND/OR levels).
7126
Yet attributes of the just built condition are not needed.
7127
Thus we call sel->cond->quick_fix_field for safety.
7129
if (sel->cond && !sel->cond->fixed)
7130
sel->cond->quick_fix_field();
7132
if (sel->test_quick_select(session, tab->keys,
7133
used_tables & ~ current_map,
7134
(join->select_options &
7137
join->unit->select_limit_cnt), 0,
7141
Before reporting "Impossible WHERE" for the whole query
7142
we have to check isn't it only "impossible ON" instead
7144
sel->cond=orig_cond;
7145
if (!*tab->on_expr_ref ||
7146
sel->test_quick_select(session, tab->keys,
7147
used_tables & ~ current_map,
7148
(join->select_options &
7151
join->unit->select_limit_cnt),0,
7153
return(1); // Impossible WHERE
7156
sel->cond=orig_cond;
7158
/* Fix for EXPLAIN */
7160
join->best_positions[i].records_read= (double)sel->quick->records;
7164
sel->needed_reg=tab->needed_reg;
7165
sel->quick_keys.clear_all();
7167
if (!sel->quick_keys.is_subset(tab->checked_keys) ||
7168
!sel->needed_reg.is_subset(tab->checked_keys))
7170
tab->keys=sel->quick_keys;
7171
tab->keys.merge(sel->needed_reg);
7172
tab->use_quick= (!sel->needed_reg.is_clear_all() &&
7173
(select->quick_keys.is_clear_all() ||
7175
(select->quick->records >= 100L)))) ?
7177
sel->read_tables= used_tables & ~current_map;
7179
if (i != join->const_tables && tab->use_quick != 2)
7180
{ /* Read with cache */
7182
(tmp=make_cond_for_table(cond,
7183
join->const_table_map |
7187
tab->cache.select=(SQL_SELECT*)
7188
session->memdup((unsigned char*) sel, sizeof(SQL_SELECT));
7189
tab->cache.select->cond=tmp;
7190
tab->cache.select->read_tables=join->const_table_map;
7197
Push down conditions from all on expressions.
7198
Each of these conditions are guarded by a variable
7199
that turns if off just before null complemented row for
7200
outer joins is formed. Thus, the condition from an
7201
'on expression' are guaranteed not to be checked for
7202
the null complemented row.
7205
/* First push down constant conditions from on expressions */
7206
for (JOIN_TAB *join_tab= join->join_tab+join->const_tables;
7207
join_tab < join->join_tab+join->tables ; join_tab++)
7209
if (*join_tab->on_expr_ref)
7211
JOIN_TAB *cond_tab= join_tab->first_inner;
7212
tmp= make_cond_for_table(*join_tab->on_expr_ref,
7213
join->const_table_map,
7217
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
7220
tmp->quick_fix_field();
7221
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
7222
new Item_cond_and(cond_tab->select_cond,tmp);
7223
if (!cond_tab->select_cond)
7225
cond_tab->select_cond->quick_fix_field();
7229
/* Push down non-constant conditions from on expressions */
7230
JOIN_TAB *last_tab= tab;
7231
while (first_inner_tab && first_inner_tab->last_inner == last_tab)
7234
Table tab is the last inner table of an outer join.
7235
An on expression is always attached to it.
7237
COND *on_expr= *first_inner_tab->on_expr_ref;
7239
table_map used_tables2= (join->const_table_map |
7240
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
7241
for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++)
7243
current_map= tab->table->map;
7244
used_tables2|= current_map;
7245
COND *tmp_cond= make_cond_for_table(on_expr, used_tables2,
7249
JOIN_TAB *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;
7251
First add the guards for match variables of
7252
all embedding outer join operations.
7254
if (!(tmp_cond= add_found_match_trig_cond(cond_tab->first_inner,
7259
Now add the guard turning the predicate off for
7260
the null complemented row.
7262
tmp_cond= new Item_func_trig_cond(tmp_cond,
7266
tmp_cond->quick_fix_field();
7267
/* Add the predicate to other pushed down predicates */
7268
cond_tab->select_cond= !cond_tab->select_cond ? tmp_cond :
7269
new Item_cond_and(cond_tab->select_cond,
7271
if (!cond_tab->select_cond)
7273
cond_tab->select_cond->quick_fix_field();
7276
first_inner_tab= first_inner_tab->first_upper;
7285
Check if given expression uses only table fields covered by the given index
7288
uses_index_fields_only()
7289
item Expression to check
7290
tbl The table having the index
7291
keyno The index number
7292
other_tbls_ok true <=> Fields of other non-const tables are allowed
7295
Check if given expression only uses fields covered by index #keyno in the
7296
table tbl. The expression can use any fields in any other tables.
7298
The expression is guaranteed not to be AND or OR - those constructs are
7299
handled outside of this function.
7306
bool uses_index_fields_only(Item *item, Table *tbl, uint32_t keyno,
7309
if (item->const_item())
7313
Don't push down the triggered conditions. Nested outer joins execution
7314
code may need to evaluate a condition several times (both triggered and
7315
untriggered), and there is no way to put thi
7316
TODO: Consider cloning the triggered condition and using the copies for:
7317
1. push the first copy down, to have most restrictive index condition
7319
2. Put the second copy into tab->select_cond.
7321
if (item->type() == Item::FUNC_ITEM &&
7322
((Item_func*)item)->functype() == Item_func::TRIG_COND_FUNC)
7325
if (!(item->used_tables() & tbl->map))
7326
return other_tbls_ok;
7328
Item::Type item_type= item->type();
7329
switch (item_type) {
7330
case Item::FUNC_ITEM:
7332
/* This is a function, apply condition recursively to arguments */
7333
Item_func *item_func= (Item_func*)item;
7335
Item **item_end= (item_func->arguments()) + item_func->argument_count();
7336
for (child= item_func->arguments(); child != item_end; child++)
7338
if (!uses_index_fields_only(*child, tbl, keyno, other_tbls_ok))
7343
case Item::COND_ITEM:
7345
/* This is a function, apply condition recursively to arguments */
7346
List_iterator<Item> li(*((Item_cond*)item)->argument_list());
7348
while ((list_item=li++))
7350
if (!uses_index_fields_only(item, tbl, keyno, other_tbls_ok))
7355
case Item::FIELD_ITEM:
7357
Item_field *item_field= (Item_field*)item;
7358
if (item_field->field->table != tbl)
7360
return item_field->field->part_of_key.is_set(keyno);
7362
case Item::REF_ITEM:
7363
return uses_index_fields_only(item->real_item(), tbl, keyno,
7366
return false; /* Play it safe, don't push unknown non-const items */
1212
7371
#define ICP_COND_USES_INDEX_ONLY 10
1218
void JoinTable::cleanup()
7374
Get a part of the condition that can be checked using only index fields
7377
make_cond_for_index()
7378
cond The source condition
7379
table The table that is partially available
7380
keyno The index in the above table. Only fields covered by the index
7382
other_tbls_ok true <=> Fields of other non-const tables are allowed
7385
Get a part of the condition that can be checked when for the given table
7386
we have values only of fields covered by some index. The condition may
7387
refer to other tables, it is assumed that we have values of all of their
7391
make_cond_for_index(
7392
"cond(t1.field) AND cond(t2.key1) AND cond(t2.non_key) AND cond(t2.key2)",
7395
"cond(t1.field) AND cond(t2.key2)"
7398
Index condition, or NULL if no condition could be inferred.
7401
Item *make_cond_for_index(Item *cond, Table *table, uint32_t keyno,
7406
if (cond->type() == Item::COND_ITEM)
7408
uint32_t n_marked= 0;
7409
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
7411
Item_cond_and *new_cond=new Item_cond_and;
7414
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7418
Item *fix= make_cond_for_index(item, table, keyno, other_tbls_ok);
7420
new_cond->argument_list()->push_back(fix);
7421
n_marked += test(item->marker == ICP_COND_USES_INDEX_ONLY);
7423
if (n_marked ==((Item_cond*)cond)->argument_list()->elements)
7424
cond->marker= ICP_COND_USES_INDEX_ONLY;
7425
switch (new_cond->argument_list()->elements) {
7429
return new_cond->argument_list()->head();
7431
new_cond->quick_fix_field();
7437
Item_cond_or *new_cond=new Item_cond_or;
7440
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7444
Item *fix= make_cond_for_index(item, table, keyno, other_tbls_ok);
7447
new_cond->argument_list()->push_back(fix);
7448
n_marked += test(item->marker == ICP_COND_USES_INDEX_ONLY);
7450
if (n_marked ==((Item_cond*)cond)->argument_list()->elements)
7451
cond->marker= ICP_COND_USES_INDEX_ONLY;
7452
new_cond->quick_fix_field();
7453
new_cond->top_level_item();
7458
if (!uses_index_fields_only(cond, table, keyno, other_tbls_ok))
7460
cond->marker= ICP_COND_USES_INDEX_ONLY;
7465
Item *make_cond_remainder(Item *cond, bool exclude_index)
7467
if (exclude_index && cond->marker == ICP_COND_USES_INDEX_ONLY)
7468
return 0; /* Already checked */
7470
if (cond->type() == Item::COND_ITEM)
7472
table_map tbl_map= 0;
7473
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
7475
/* Create new top level AND item */
7476
Item_cond_and *new_cond=new Item_cond_and;
7479
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7483
Item *fix= make_cond_remainder(item, exclude_index);
7486
new_cond->argument_list()->push_back(fix);
7487
tbl_map |= fix->used_tables();
7490
switch (new_cond->argument_list()->elements) {
7494
return new_cond->argument_list()->head();
7496
new_cond->quick_fix_field();
7497
((Item_cond*)new_cond)->used_tables_cache= tbl_map;
7503
Item_cond_or *new_cond=new Item_cond_or;
7506
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
7510
Item *fix= make_cond_remainder(item, false);
7513
new_cond->argument_list()->push_back(fix);
7514
tbl_map |= fix->used_tables();
7516
new_cond->quick_fix_field();
7517
((Item_cond*)new_cond)->used_tables_cache= tbl_map;
7518
new_cond->top_level_item();
7527
Try to extract and push the index condition
7531
tab A join tab that has tab->table->file and its condition
7533
keyno Index for which extract and push the condition
7534
other_tbls_ok true <=> Fields of other non-const tables are allowed
7537
Try to extract and push the index condition down to table handler
7540
static void push_index_cond(JOIN_TAB *tab, uint32_t keyno, bool other_tbls_ok)
7543
if (tab->table->file->index_flags(keyno, 0, 1) & HA_DO_INDEX_COND_PUSHDOWN &&
7544
tab->join->session->variables.engine_condition_pushdown)
7546
idx_cond= make_cond_for_index(tab->select_cond, tab->table, keyno,
7551
tab->pre_idx_push_select_cond= tab->select_cond;
7552
Item *idx_remainder_cond=
7553
tab->table->file->idx_cond_push(keyno, idx_cond);
7556
Disable eq_ref's "lookup cache" if we've pushed down an index
7558
TODO: This check happens to work on current ICP implementations, but
7559
there may exist a compliant implementation that will not work
7560
correctly with it. Sort this out when we stabilize the condition
7563
if (idx_remainder_cond != idx_cond)
7564
tab->ref.disable_cache= true;
7566
Item *row_cond= make_cond_remainder(tab->select_cond, true);
7570
if (!idx_remainder_cond)
7571
tab->select_cond= row_cond;
7574
tab->select_cond= new Item_cond_and(row_cond, idx_remainder_cond);
7575
tab->select_cond->quick_fix_field();
7576
((Item_cond_and*)tab->select_cond)->used_tables_cache=
7577
row_cond->used_tables() | idx_remainder_cond->used_tables();
7581
tab->select_cond= idx_remainder_cond;
7584
tab->select->cond= tab->select_cond;
7594
Determine if the set is already ordered for order_st BY, so it can
7595
disable join cache because it will change the ordering of the results.
7596
Code handles sort table that is at any location (not only first after
7597
the const tables) despite the fact that it's currently prohibited.
7598
We must disable join cache if the first non-const table alone is
7599
ordered. If there is a temp table the ordering is done as a last
7600
operation and doesn't prevent join cache usage.
7602
uint32_t make_join_orderinfo(JOIN *join)
7606
return join->tables;
7608
for (i=join->const_tables ; i < join->tables ; i++)
7610
JOIN_TAB *tab=join->join_tab+i;
7611
Table *table=tab->table;
7612
if ((table == join->sort_by_table &&
7613
(!join->order || join->skip_sort_order)) ||
7614
(join->sort_by_table == (Table *) 1 && i != join->const_tables))
7624
Plan refinement stage: do various set ups for the executioner
7627
make_join_readinfo()
7628
join Join being processed
7629
options Join's options (checking for SELECT_DESCRIBE,
7630
SELECT_NO_JOIN_CACHE)
7631
no_jbuf_after Don't use join buffering after table with this number.
7634
Plan refinement stage: do various set ups for the executioner
7635
- set up use of join buffering
7636
- push index conditions
7637
- increment counters
7642
true - Out of memory
7646
make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
7649
bool statistics= test(!(join->select_options & SELECT_DESCRIBE));
7652
for (i=join->const_tables ; i < join->tables ; i++)
7654
JOIN_TAB *tab=join->join_tab+i;
7655
Table *table=tab->table;
7656
bool using_join_cache;
7657
tab->read_record.table= table;
7658
tab->read_record.file=table->file;
7659
tab->next_select=sub_select; /* normal select */
7661
TODO: don't always instruct first table's ref/range access method to
7662
produce sorted output.
7664
tab->sorted= sorted;
7665
sorted= 0; // only first must be sorted
7666
if (tab->insideout_match_tab)
7668
if (!(tab->insideout_buf= (unsigned char*)join->session->alloc(tab->table->key_info
7673
switch (tab->type) {
7674
case JT_SYSTEM: // Only happens with left join
7675
table->status=STATUS_NO_RECORD;
7676
tab->read_first_record= join_read_system;
7677
tab->read_record.read_record= join_no_more_records;
7679
case JT_CONST: // Only happens with left join
7680
table->status=STATUS_NO_RECORD;
7681
tab->read_first_record= join_read_const;
7682
tab->read_record.read_record= join_no_more_records;
7683
if (table->covering_keys.is_set(tab->ref.key) &&
7687
table->file->extra(HA_EXTRA_KEYREAD);
7691
table->status=STATUS_NO_RECORD;
7694
delete tab->select->quick;
7695
tab->select->quick=0;
7699
tab->read_first_record= join_read_key;
7700
tab->read_record.read_record= join_no_more_records;
7701
if (table->covering_keys.is_set(tab->ref.key) &&
7705
table->file->extra(HA_EXTRA_KEYREAD);
7708
push_index_cond(tab, tab->ref.key, true);
7710
case JT_REF_OR_NULL:
7712
table->status=STATUS_NO_RECORD;
7715
delete tab->select->quick;
7716
tab->select->quick=0;
7720
if (table->covering_keys.is_set(tab->ref.key) &&
7724
table->file->extra(HA_EXTRA_KEYREAD);
7727
push_index_cond(tab, tab->ref.key, true);
7728
if (tab->type == JT_REF)
7730
tab->read_first_record= join_read_always_key;
7731
tab->read_record.read_record= tab->insideout_match_tab?
7732
join_read_next_same_diff : join_read_next_same;
7736
tab->read_first_record= join_read_always_key_or_null;
7737
tab->read_record.read_record= join_read_next_same_or_null;
7742
If previous table use cache
7743
If the incoming data set is already sorted don't use cache.
7745
table->status=STATUS_NO_RECORD;
7746
using_join_cache= false;
7747
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
7748
tab->use_quick != 2 && !tab->first_inner && i <= no_jbuf_after &&
7749
!tab->insideout_match_tab)
7751
if ((options & SELECT_DESCRIBE) ||
7752
!join_init_cache(join->session,join->join_tab+join->const_tables,
7753
i-join->const_tables))
7755
using_join_cache= true;
7756
tab[-1].next_select=sub_select_cache; /* Patch previous */
7759
/* These init changes read_record */
7760
if (tab->use_quick == 2)
7762
join->session->server_status|=SERVER_QUERY_NO_GOOD_INDEX_USED;
7763
tab->read_first_record= join_init_quick_read_record;
7765
status_var_increment(join->session->status_var.select_range_check_count);
7769
tab->read_first_record= join_init_read_record;
7770
if (i == join->const_tables)
7772
if (tab->select && tab->select->quick)
7775
status_var_increment(join->session->status_var.select_range_count);
7779
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
7781
status_var_increment(join->session->status_var.select_scan_count);
7786
if (tab->select && tab->select->quick)
7789
status_var_increment(join->session->status_var.select_full_range_join_count);
7793
join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
7795
status_var_increment(join->session->status_var.select_full_join_count);
7798
if (!table->no_keyread)
7800
if (tab->select && tab->select->quick &&
7801
tab->select->quick->index != MAX_KEY && //not index_merge
7802
table->covering_keys.is_set(tab->select->quick->index))
7805
table->file->extra(HA_EXTRA_KEYREAD);
7807
else if (!table->covering_keys.is_clear_all() &&
7808
!(tab->select && tab->select->quick))
7809
{ // Only read index tree
7810
if (!tab->insideout_match_tab)
7813
See bug #26447: "Using the clustered index for a table scan
7814
is always faster than using a secondary index".
7816
if (table->s->primary_key != MAX_KEY &&
7817
table->file->primary_key_is_clustered())
7818
tab->index= table->s->primary_key;
7820
tab->index= table->find_shortest_key(&table->covering_keys);
7822
tab->read_first_record= join_read_first;
7823
tab->type=JT_NEXT; // Read with index_first / index_next
7826
if (tab->select && tab->select->quick &&
7827
tab->select->quick->index != MAX_KEY && ! tab->table->key_read)
7828
push_index_cond(tab, tab->select->quick->index, !using_join_cache);
7832
break; /* purecov: deadcode */
7835
abort(); /* purecov: deadcode */
7838
join->join_tab[join->tables-1].next_select=0; /* Set by do_select */
7844
Give error if we some tables are done with a full join.
7846
This is used by multi_table_update and multi_table_delete when running
7849
@param join Join condition
7854
1 Error (full join used)
7857
bool error_if_full_join(JOIN *join)
7859
for (JOIN_TAB *tab=join->join_tab, *end=join->join_tab+join->tables;
7863
if (tab->type == JT_ALL && (!tab->select || !tab->select->quick))
7865
my_message(ER_UPDATE_WITHOUT_KEY_IN_SAFE_MODE,
7866
ER(ER_UPDATE_WITHOUT_KEY_IN_SAFE_MODE), MYF(0));
7878
void JOIN_TAB::cleanup()
1224
7884
if (cache.buff)
1226
size_t size= cache.end - cache.buff;
1227
global_join_buffer.sub(size);
1228
7885
free(cache.buff);
2512
9589
if (!(left_const && right_const) &&
2513
9590
args[0]->result_type() == args[1]->result_type())
2517
resolve_const_item(session, &args[1], args[0]);
2518
func->update_used_tables();
2519
change_cond_ref_to_const(session, save_list, and_father, and_father,
2522
else if (left_const)
2524
resolve_const_item(session, &args[0], args[1]);
2525
func->update_used_tables();
2526
change_cond_ref_to_const(session, save_list, and_father, and_father,
9594
resolve_const_item(session, &args[1], args[0]);
9595
func->update_used_tables();
9596
change_cond_ref_to_const(session, save_list, and_father, and_father,
9599
else if (left_const)
9601
resolve_const_item(session, &args[0], args[1]);
9602
func->update_used_tables();
9603
change_cond_ref_to_const(session, save_list, and_father, and_father,
9613
Simplify joins replacing outer joins by inner joins whenever it's
9616
The function, during a retrieval of join_list, eliminates those
9617
outer joins that can be converted into inner join, possibly nested.
9618
It also moves the on expressions for the converted outer joins
9619
and from inner joins to conds.
9620
The function also calculates some attributes for nested joins:
9624
- on_expr_dep_tables
9625
The first two attributes are used to test whether an outer join can
9626
be substituted for an inner join. The third attribute represents the
9627
relation 'to be dependent on' for tables. If table t2 is dependent
9628
on table t1, then in any evaluated execution plan table access to
9629
table t2 must precede access to table t2. This relation is used also
9630
to check whether the query contains invalid cross-references.
9631
The forth attribute is an auxiliary one and is used to calculate
9633
As the attribute dep_tables qualifies possibles orders of tables in the
9634
execution plan, the dependencies required by the straight join
9635
modifiers are reflected in this attribute as well.
9636
The function also removes all braces that can be removed from the join
9637
expression without changing its meaning.
9640
An outer join can be replaced by an inner join if the where condition
9641
or the on expression for an embedding nested join contains a conjunctive
9642
predicate rejecting null values for some attribute of the inner tables.
9646
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
9648
the predicate t2.b < 5 rejects nulls.
9649
The query is converted first to:
9651
SELECT * FROM t1 INNER JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
9653
then to the equivalent form:
9655
SELECT * FROM t1, t2 ON t2.a=t1.a WHERE t2.b < 5 AND t2.a=t1.a
9659
Similarly the following query:
9661
SELECT * from t1 LEFT JOIN (t2, t3) ON t2.a=t1.a t3.b=t1.b
9666
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b
9670
One conversion might trigger another:
9672
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a
9673
LEFT JOIN t3 ON t3.b=t2.b
9674
WHERE t3 IS NOT NULL =>
9675
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a, t3
9676
WHERE t3 IS NOT NULL AND t3.b=t2.b =>
9677
SELECT * FROM t1, t2, t3
9678
WHERE t3 IS NOT NULL AND t3.b=t2.b AND t2.a=t1.a
9681
The function removes all unnecessary braces from the expression
9682
produced by the conversions.
9685
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
9687
finally is converted to:
9689
SELECT * FROM t1, t2, t3 WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
9694
It also will remove braces from the following queries:
9696
SELECT * from (t1 LEFT JOIN t2 ON t2.a=t1.a) LEFT JOIN t3 ON t3.b=t2.b
9697
SELECT * from (t1, (t2,t3)) WHERE t1.a=t2.a AND t2.b=t3.b.
9700
The benefit of this simplification procedure is that it might return
9701
a query for which the optimizer can evaluate execution plan with more
9702
join orders. With a left join operation the optimizer does not
9703
consider any plan where one of the inner tables is before some of outer
9707
The function is implemented by a recursive procedure. On the recursive
9708
ascent all attributes are calculated, all outer joins that can be
9709
converted are replaced and then all unnecessary braces are removed.
9710
As join list contains join tables in the reverse order sequential
9711
elimination of outer joins does not require extra recursive calls.
9714
Remove all semi-joins that have are within another semi-join (i.e. have
9715
an "ancestor" semi-join nest)
9718
Here is an example of a join query with invalid cross references:
9720
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t3.a LEFT JOIN t3 ON t3.b=t1.b
9723
@param join reference to the query info
9724
@param join_list list representation of the join to be converted
9725
@param conds conditions to add on expressions for converted joins
9726
@param top true <=> conds is the where condition
9729
- The new condition, if success
9734
simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top,
9738
nested_join_st *nested_join;
9739
TableList *prev_table= 0;
9740
List_iterator<TableList> li(*join_list);
9743
Try to simplify join operations from join_list.
9744
The most outer join operation is checked for conversion first.
9746
while ((table= li++))
9748
table_map used_tables;
9749
table_map not_null_tables= (table_map) 0;
9751
if ((nested_join= table->nested_join))
9754
If the element of join_list is a nested join apply
9755
the procedure to its nested join list first.
9759
Item *expr= table->on_expr;
9761
If an on expression E is attached to the table,
9762
check all null rejected predicates in this expression.
9763
If such a predicate over an attribute belonging to
9764
an inner table of an embedded outer join is found,
9765
the outer join is converted to an inner join and
9766
the corresponding on expression is added to E.
9768
expr= simplify_joins(join, &nested_join->join_list,
9769
expr, false, in_sj || table->sj_on_expr);
9771
if (!table->prep_on_expr || expr != table->on_expr)
9775
table->on_expr= expr;
9776
table->prep_on_expr= expr->copy_andor_structure(join->session);
9779
nested_join->used_tables= (table_map) 0;
9780
nested_join->not_null_tables=(table_map) 0;
9781
conds= simplify_joins(join, &nested_join->join_list, conds, top,
9782
in_sj || table->sj_on_expr);
9783
used_tables= nested_join->used_tables;
9784
not_null_tables= nested_join->not_null_tables;
9788
if (!table->prep_on_expr)
9789
table->prep_on_expr= table->on_expr;
9790
used_tables= table->table->map;
9792
not_null_tables= conds->not_null_tables();
9795
if (table->embedding)
9797
table->embedding->nested_join->used_tables|= used_tables;
9798
table->embedding->nested_join->not_null_tables|= not_null_tables;
9801
if (!table->outer_join || (used_tables & not_null_tables))
9804
For some of the inner tables there are conjunctive predicates
9805
that reject nulls => the outer join can be replaced by an inner join.
9807
table->outer_join= 0;
9810
/* Add ON expression to the WHERE or upper-level ON condition. */
9813
conds= and_conds(conds, table->on_expr);
9814
conds->top_level_item();
9815
/* conds is always a new item as both cond and on_expr existed */
9816
assert(!conds->fixed);
9817
conds->fix_fields(join->session, &conds);
9820
conds= table->on_expr;
9821
table->prep_on_expr= table->on_expr= 0;
9829
Only inner tables of non-convertible outer joins
9830
remain with on_expr.
9834
table->dep_tables|= table->on_expr->used_tables();
9835
if (table->embedding)
9837
table->dep_tables&= ~table->embedding->nested_join->used_tables;
9839
Embedding table depends on tables used
9840
in embedded on expressions.
9842
table->embedding->on_expr_dep_tables|= table->on_expr->used_tables();
9845
table->dep_tables&= ~table->table->map;
9850
/* The order of tables is reverse: prev_table follows table */
9851
if (prev_table->straight)
9852
prev_table->dep_tables|= used_tables;
9853
if (prev_table->on_expr)
9855
prev_table->dep_tables|= table->on_expr_dep_tables;
9856
table_map prev_used_tables= prev_table->nested_join ?
9857
prev_table->nested_join->used_tables :
9858
prev_table->table->map;
9860
If on expression contains only references to inner tables
9861
we still make the inner tables dependent on the outer tables.
9862
It would be enough to set dependency only on one outer table
9863
for them. Yet this is really a rare case.
9865
if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
9866
prev_table->dep_tables|= used_tables;
9873
Flatten nested joins that can be flattened.
9874
no ON expression and not a semi-join => can be flattened.
9877
while ((table= li++))
9879
nested_join= table->nested_join;
9880
if (table->sj_on_expr && !in_sj)
9883
If this is a semi-join that is not contained within another semi-join,
9884
leave it intact (otherwise it is flattened)
9886
join->select_lex->sj_nests.push_back(table);
9888
else if (nested_join && !table->on_expr)
9891
List_iterator<TableList> it(nested_join->join_list);
9894
tbl->embedding= table->embedding;
9895
tbl->join_list= table->join_list;
9897
li.replace(nested_join->join_list);
9905
Assign each nested join structure a bit in nested_join_map.
9907
Assign each nested join structure (except "confluent" ones - those that
9908
embed only one element) a bit in nested_join_map.
9910
@param join Join being processed
9911
@param join_list List of tables
9912
@param first_unused Number of first unused bit in nested_join_map before the
9916
This function is called after simplify_joins(), when there are no
9917
redundant nested joins, #non_confluent_nested_joins <= #tables_in_join so
9918
we will not run out of bits in nested_join_map.
9921
First unused bit in nested_join_map after the call.
9924
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list,
9925
uint32_t first_unused)
9927
List_iterator<TableList> li(*join_list);
9929
while ((table= li++))
9931
nested_join_st *nested_join;
9932
if ((nested_join= table->nested_join))
9935
It is guaranteed by simplify_joins() function that a nested join
9936
that has only one child is either
9937
- a single-table view (the child is the underlying table), or
9938
- a single-table semi-join nest
9940
We don't assign bits to such sj-nests because
9941
1. it is redundant (a "sequence" of one table cannot be interleaved
9943
2. we could run out bits in nested_join_map otherwise.
9945
if (nested_join->join_list.elements != 1)
9947
/* Don't assign bits to sj-nests */
9949
nested_join->nj_map= (nested_join_map) 1 << first_unused++;
9950
first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
9955
return(first_unused);
9960
Set nested_join_st::counter=0 in all nested joins in passed list.
9962
Recursively set nested_join_st::counter=0 for all nested joins contained in
9963
the passed join_list.
9965
@param join_list List of nested joins to process. It may also contain base
9966
tables which will be ignored.
9969
static void reset_nj_counters(List<TableList> *join_list)
9971
List_iterator<TableList> li(*join_list);
9973
while ((table= li++))
9975
nested_join_st *nested_join;
9976
if ((nested_join= table->nested_join))
9978
nested_join->counter_= 0;
9979
reset_nj_counters(&nested_join->join_list);
2535
9987
Check interleaving with an inner tables of an outer join for
3359
int safe_index_read(JoinTable *tab)
10901
SemiJoinDuplicateElimination: Weed out duplicate row combinations
10904
do_sj_dups_weedout()
10908
1 The row combination is a duplicate (discard it)
10909
0 The row combination is not a duplicate (continue)
10912
int do_sj_dups_weedout(Session *session, SJ_TMP_TABLE *sjtbl)
10915
SJ_TMP_TABLE::TAB *tab= sjtbl->tabs;
10916
SJ_TMP_TABLE::TAB *tab_end= sjtbl->tabs_end;
10917
unsigned char *ptr= sjtbl->tmp_table->record[0] + 1;
10918
unsigned char *nulls_ptr= ptr;
10920
/* Put the the rowids tuple into table->record[0]: */
10922
// 1. Store the length
10923
if (((Field_varstring*)(sjtbl->tmp_table->field[0]))->length_bytes == 1)
10925
*ptr= (unsigned char)(sjtbl->rowid_len + sjtbl->null_bytes);
10930
int2store(ptr, sjtbl->rowid_len + sjtbl->null_bytes);
10934
// 2. Zero the null bytes
10935
if (sjtbl->null_bytes)
10937
memset(ptr, 0, sjtbl->null_bytes);
10938
ptr += sjtbl->null_bytes;
10941
// 3. Put the rowids
10942
for (uint32_t i=0; tab != tab_end; tab++, i++)
10944
handler *h= tab->join_tab->table->file;
10945
if (tab->join_tab->table->maybe_null && tab->join_tab->table->null_row)
10947
/* It's a NULL-complemented row */
10948
*(nulls_ptr + tab->null_byte) |= tab->null_bit;
10949
memset(ptr + tab->rowid_offset, 0, h->ref_length);
10953
/* Copy the rowid value */
10954
if (tab->join_tab->rowid_keep_flags & JOIN_TAB::CALL_POSITION)
10955
h->position(tab->join_tab->table->record[0]);
10956
memcpy(ptr + tab->rowid_offset, h->ref, h->ref_length);
10960
error= sjtbl->tmp_table->file->ha_write_row(sjtbl->tmp_table->record[0]);
10963
/* create_myisam_from_heap will generate error if needed */
10964
if (sjtbl->tmp_table->file->is_fatal_error(error, HA_CHECK_DUP) &&
10965
create_myisam_from_heap(session, sjtbl->tmp_table, sjtbl->start_recinfo,
10966
&sjtbl->recinfo, error, 1))
10968
//return (error == HA_ERR_FOUND_DUPP_KEY || error== HA_ERR_FOUND_DUPP_UNIQUE) ? 1: -1;
10976
SemiJoinDuplicateElimination: Reset the temporary table
10979
int do_sj_reset(SJ_TMP_TABLE *sj_tbl)
10981
if (sj_tbl->tmp_table)
10982
return sj_tbl->tmp_table->file->ha_delete_all_rows();
10987
Process one record of the nested loop join.
10989
This function will evaluate parts of WHERE/ON clauses that are
10990
applicable to the partial record on hand and in case of success
10991
submit this record to the next level of the nested loop.
10994
static enum_nested_loop_state
10995
evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,
10998
bool not_used_in_distinct=join_tab->not_used_in_distinct;
10999
ha_rows found_records=join->found_records;
11000
COND *select_cond= join_tab->select_cond;
11002
if (error > 0 || (join->session->is_error())) // Fatal error
11003
return NESTED_LOOP_ERROR;
11005
return NESTED_LOOP_NO_MORE_ROWS;
11006
if (join->session->killed) // Aborted by user
11008
join->session->send_kill_message();
11009
return NESTED_LOOP_KILLED; /* purecov: inspected */
11011
if (!select_cond || select_cond->val_int())
11014
There is no select condition or the attached pushed down
11015
condition is true => a match is found.
11018
while (join_tab->first_unmatched && found)
11021
The while condition is always false if join_tab is not
11022
the last inner join table of an outer join operation.
11024
JOIN_TAB *first_unmatched= join_tab->first_unmatched;
11026
Mark that a match for current outer table is found.
11027
This activates push down conditional predicates attached
11028
to the all inner tables of the outer join.
11030
first_unmatched->found= 1;
11031
for (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)
11033
if (tab->table->reginfo.not_exists_optimize)
11034
return NESTED_LOOP_NO_MORE_ROWS;
11035
/* Check all predicates that has just been activated. */
11037
Actually all predicates non-guarded by first_unmatched->found
11038
will be re-evaluated again. It could be fixed, but, probably,
11039
it's not worth doing now.
11041
if (tab->select_cond && !tab->select_cond->val_int())
11043
/* The condition attached to table tab is false */
11044
if (tab == join_tab)
11049
Set a return point if rejected predicate is attached
11050
not to the last table of the current nest level.
11052
join->return_tab= tab;
11053
return NESTED_LOOP_OK;
11058
Check whether join_tab is not the last inner table
11059
for another embedding outer join.
11061
if ((first_unmatched= first_unmatched->first_upper) &&
11062
first_unmatched->last_inner != join_tab)
11063
first_unmatched= 0;
11064
join_tab->first_unmatched= first_unmatched;
11067
JOIN_TAB *return_tab= join->return_tab;
11068
join_tab->found_match= true;
11069
if (join_tab->check_weed_out_table)
11071
int res= do_sj_dups_weedout(join->session, join_tab->check_weed_out_table);
11073
return NESTED_LOOP_ERROR;
11075
return NESTED_LOOP_OK;
11077
else if (join_tab->do_firstmatch)
11080
We should return to the join_tab->do_firstmatch after we have
11081
enumerated all the suffixes for current prefix row combination
11083
return_tab= join_tab->do_firstmatch;
11087
It was not just a return to lower loop level when one
11088
of the newly activated predicates is evaluated as false
11089
(See above join->return_tab= tab).
11091
join->examined_rows++;
11092
join->session->row_count++;
11096
enum enum_nested_loop_state rc;
11097
/* A match from join_tab is found for the current partial join. */
11098
rc= (*join_tab->next_select)(join, join_tab+1, 0);
11099
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
11101
if (return_tab < join->return_tab)
11102
join->return_tab= return_tab;
11104
if (join->return_tab < join_tab)
11105
return NESTED_LOOP_OK;
11107
Test if this was a SELECT DISTINCT query on a table that
11108
was not in the field list; In this case we can abort if
11109
we found a row, as no new rows can be added to the result.
11111
if (not_used_in_distinct && found_records != join->found_records)
11112
return NESTED_LOOP_NO_MORE_ROWS;
11115
join_tab->read_record.file->unlock_row();
11120
The condition pushed down to the table join_tab rejects all rows
11121
with the beginning coinciding with the current partial join.
11123
join->examined_rows++;
11124
join->session->row_count++;
11125
join_tab->read_record.file->unlock_row();
11127
return NESTED_LOOP_OK;
11134
Construct a NULL complimented partial join record and feed it to the next
11135
level of the nested loop. This function is used in case we have
11136
an OUTER join and no matching record was found.
11139
static enum_nested_loop_state
11140
evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab)
11143
The table join_tab is the first inner table of a outer join operation
11144
and no matches has been found for the current outer row.
11146
JOIN_TAB *last_inner_tab= join_tab->last_inner;
11147
/* Cache variables for faster loop */
11149
for ( ; join_tab <= last_inner_tab ; join_tab++)
11151
/* Change the the values of guard predicate variables. */
11152
join_tab->found= 1;
11153
join_tab->not_null_compl= 0;
11154
/* The outer row is complemented by nulls for each inner tables */
11155
restore_record(join_tab->table,s->default_values); // Make empty record
11156
mark_as_null_row(join_tab->table); // For group by without error
11157
select_cond= join_tab->select_cond;
11158
/* Check all attached conditions for inner table rows. */
11159
if (select_cond && !select_cond->val_int())
11160
return NESTED_LOOP_OK;
11164
The row complemented by nulls might be the first row
11165
of embedding outer joins.
11166
If so, perform the same actions as in the code
11167
for the first regular outer join row above.
11171
JOIN_TAB *first_unmatched= join_tab->first_unmatched;
11172
if ((first_unmatched= first_unmatched->first_upper) &&
11173
first_unmatched->last_inner != join_tab)
11174
first_unmatched= 0;
11175
join_tab->first_unmatched= first_unmatched;
11176
if (!first_unmatched)
11178
first_unmatched->found= 1;
11179
for (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)
11181
if (tab->select_cond && !tab->select_cond->val_int())
11183
join->return_tab= tab;
11184
return NESTED_LOOP_OK;
11189
The row complemented by nulls satisfies all conditions
11190
attached to inner tables.
11191
Send the row complemented by nulls to be joined with the
11194
return (*join_tab->next_select)(join, join_tab+1, 0);
11198
static enum_nested_loop_state
11199
flush_cached_records(JOIN *join,JOIN_TAB *join_tab,bool skip_last)
11201
enum_nested_loop_state rc= NESTED_LOOP_OK;
11205
join_tab->table->null_row= 0;
11206
if (!join_tab->cache.records)
11207
return NESTED_LOOP_OK; /* Nothing to do */
11209
(void) store_record_in_cache(&join_tab->cache); // Must save this for later
11210
if (join_tab->use_quick == 2)
11212
if (join_tab->select->quick)
11213
{ /* Used quick select last. reset it */
11214
delete join_tab->select->quick;
11215
join_tab->select->quick=0;
11218
/* read through all records */
11219
if ((error=join_init_read_record(join_tab)))
11221
reset_cache_write(&join_tab->cache);
11222
return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
11225
for (JOIN_TAB *tmp=join->join_tab; tmp != join_tab ; tmp++)
11227
tmp->status=tmp->table->status;
11228
tmp->table->status=0;
11231
info= &join_tab->read_record;
11234
if (join->session->killed)
11236
join->session->send_kill_message();
11237
return NESTED_LOOP_KILLED; // Aborted by user /* purecov: inspected */
11239
SQL_SELECT *select=join_tab->select;
11240
if (rc == NESTED_LOOP_OK &&
11241
(!join_tab->cache.select || !join_tab->cache.select->skip_record()))
11244
reset_cache_read(&join_tab->cache);
11245
for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
11247
read_cached_record(join_tab);
11248
if (!select || !select->skip_record())
11251
if (!join_tab->check_weed_out_table ||
11252
!(res= do_sj_dups_weedout(join->session, join_tab->check_weed_out_table)))
11254
rc= (join_tab->next_select)(join,join_tab+1,0);
11255
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
11257
reset_cache_write(&join_tab->cache);
11262
return NESTED_LOOP_ERROR;
11266
} while (!(error=info->read_record(info)));
11269
read_cached_record(join_tab); // Restore current record
11270
reset_cache_write(&join_tab->cache);
11271
if (error > 0) // Fatal error
11272
return NESTED_LOOP_ERROR; /* purecov: inspected */
11273
for (JOIN_TAB *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
11274
tmp2->table->status=tmp2->status;
11275
return NESTED_LOOP_OK;
11278
int safe_index_read(JOIN_TAB *tab)
3362
11281
Table *table= tab->table;
3363
if ((error=table->cursor->index_read_map(table->getInsertRecord(),
11282
if ((error=table->file->index_read_map(table->record[0],
3364
11283
tab->ref.key_buff,
3365
11284
make_prev_keypart_map(tab->ref.key_parts),
3366
11285
HA_READ_KEY_EXACT)))
15336
/** Allocate memory needed for other rollup functions. */
15338
bool JOIN::rollup_init()
15343
tmp_table_param.quick_group= 0; // Can't create groups in tmp table
15344
rollup.state= ROLLUP::STATE_INITED;
15347
Create pointers to the different sum function groups
15348
These are updated by rollup_make_fields()
15350
tmp_table_param.group_parts= send_group_parts;
15352
if (!(rollup.null_items= (Item_null_result**) session->alloc((sizeof(Item*) +
15354
sizeof(List<Item>) +
15355
ref_pointer_array_size)
15356
* send_group_parts )))
15359
rollup.fields= (List<Item>*) (rollup.null_items + send_group_parts);
15360
rollup.ref_pointer_arrays= (Item***) (rollup.fields + send_group_parts);
15361
ref_array= (Item**) (rollup.ref_pointer_arrays+send_group_parts);
15364
Prepare space for field list for the different levels
15365
These will be filled up in rollup_make_fields()
15367
for (i= 0 ; i < send_group_parts ; i++)
15369
rollup.null_items[i]= new (session->mem_root) Item_null_result();
15370
List<Item> *rollup_fields= &rollup.fields[i];
15371
rollup_fields->empty();
15372
rollup.ref_pointer_arrays[i]= ref_array;
15373
ref_array+= all_fields.elements;
15375
for (i= 0 ; i < send_group_parts; i++)
15377
for (j=0 ; j < fields_list.elements ; j++)
15378
rollup.fields[i].push_back(rollup.null_items[i]);
15380
List_iterator<Item> it(all_fields);
15382
while ((item= it++))
15384
order_st *group_tmp;
15385
bool found_in_group= 0;
15387
for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
15389
if (*group_tmp->item == item)
15391
item->maybe_null= 1;
15393
if (item->const_item())
15396
For ROLLUP queries each constant item referenced in GROUP BY list
15397
is wrapped up into an Item_func object yielding the same value
15398
as the constant item. The objects of the wrapper class are never
15399
considered as constant items and besides they inherit all
15400
properties of the Item_result_field class.
15401
This wrapping allows us to ensure writing constant items
15402
into temporary tables whenever the result of the ROLLUP
15403
operation has to be written into a temporary table, e.g. when
15404
ROLLUP is used together with DISTINCT in the SELECT list.
15405
Usually when creating temporary tables for a intermidiate
15406
result we do not include fields for constant expressions.
15408
Item* new_item= new Item_func_rollup_const(item);
15411
new_item->fix_fields(session, (Item **) 0);
15412
session->change_item_tree(it.ref(), new_item);
15413
for (order_st *tmp= group_tmp; tmp; tmp= tmp->next)
15415
if (*tmp->item == item)
15416
session->change_item_tree(tmp->item, new_item);
15421
if (item->type() == Item::FUNC_ITEM && !found_in_group)
15423
bool changed= false;
15424
if (change_group_ref(session, (Item_func *) item, group_list, &changed))
15427
We have to prevent creation of a field in a temporary table for
15428
an expression that contains GROUP BY attributes.
15429
Marking the expression item as 'with_sum_func' will ensure this.
15432
item->with_sum_func= 1;
15440
Fill up rollup structures with pointers to fields to use.
15442
Creates copies of item_sum items for each sum level.
15444
@param fields_arg List of all fields (hidden and real ones)
15445
@param sel_fields Pointer to selected fields
15446
@param func Store here a pointer to all fields
15450
In this case func is pointing to next not used element.
15455
bool JOIN::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields,
15458
List_iterator_fast<Item> it(fields_arg);
15459
Item *first_field= sel_fields.head();
15463
Create field lists for the different levels
15465
The idea here is to have a separate field list for each rollup level to
15466
avoid all runtime checks of which columns should be NULL.
15468
The list is stored in reverse order to get sum function in such an order
15469
in func that it makes it easy to reset them with init_sum_functions()
15471
Assuming: SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
15473
rollup.fields[0] will contain list where a,b,c is NULL
15474
rollup.fields[1] will contain list where b,c is NULL
15476
rollup.ref_pointer_array[#] points to fields for rollup.fields[#]
15478
sum_funcs_end[0] points to all sum functions
15479
sum_funcs_end[1] points to all sum functions, except grand totals
15483
for (level=0 ; level < send_group_parts ; level++)
15486
uint32_t pos= send_group_parts - level -1;
15487
bool real_fields= 0;
15489
List_iterator<Item> new_it(rollup.fields[pos]);
15490
Item **ref_array_start= rollup.ref_pointer_arrays[pos];
15491
order_st *start_group;
15493
/* Point to first hidden field */
15494
Item **ref_array= ref_array_start + fields_arg.elements-1;
15496
/* Remember where the sum functions ends for the previous level */
15497
sum_funcs_end[pos+1]= *func;
15499
/* Find the start of the group for this level */
15500
for (i= 0, start_group= group_list ;
15502
start_group= start_group->next)
15506
while ((item= it++))
15508
if (item == first_field)
15510
real_fields= 1; // End of hidden fields
15511
ref_array= ref_array_start;
15514
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
15515
(!((Item_sum*) item)->depended_from() ||
15516
((Item_sum *)item)->depended_from() == select_lex))
15520
This is a top level summary function that must be replaced with
15521
a sum function that is reset for this level.
15523
NOTE: This code creates an object which is not that nice in a
15524
sub select. Fortunately it's not common to have rollup in
15527
item= item->copy_or_same(session);
15528
((Item_sum*) item)->make_unique();
15529
*(*func)= (Item_sum*) item;
15534
/* Check if this is something that is part of this group by */
15535
order_st *group_tmp;
15536
for (group_tmp= start_group, i= pos ;
15537
group_tmp ; group_tmp= group_tmp->next, i++)
15539
if (*group_tmp->item == item)
15542
This is an element that is used by the GROUP BY and should be
15543
set to NULL in this level
15545
Item_null_result *null_item= new (session->mem_root) Item_null_result();
15548
item->maybe_null= 1; // Value will be null sometimes
15549
null_item->result_field= item->get_tmp_table_field();
15558
(void) new_it++; // Point to next item
15559
new_it.replace(item); // Replace previous
15566
sum_funcs_end[0]= *func; // Point to last function
15571
Send all rollup levels higher than the current one to the client.
15575
SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
15578
@param idx Level we are on:
15579
- 0 = Total sum level
15580
- 1 = First group changed (a)
15581
- 2 = Second group changed (a,b)
15586
1 If send_data_failed()
15589
int JOIN::rollup_send_data(uint32_t idx)
15592
for (i= send_group_parts ; i-- > idx ; )
15594
/* Get reference pointers to sum functions in place */
15595
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
15596
ref_pointer_array_size);
15597
if ((!having || having->val_int()))
15599
if (send_records < unit->select_limit_cnt && do_send_rows &&
15600
result->send_data(rollup.fields[i]))
15605
/* Restore ref_pointer_array */
15606
set_items_ref_array(current_ref_pointer_array);
15611
Write all rollup levels higher than the current one to a temp table.
15615
SELECT a, b, SUM(c) FROM t1 GROUP BY a,b WITH ROLLUP
15618
@param idx Level we are on:
15619
- 0 = Total sum level
15620
- 1 = First group changed (a)
15621
- 2 = Second group changed (a,b)
15622
@param table reference to temp table
15627
1 if write_data_failed()
15630
int JOIN::rollup_write_data(uint32_t idx, Table *table_arg)
15633
for (i= send_group_parts ; i-- > idx ; )
15635
/* Get reference pointers to sum functions in place */
15636
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
15637
ref_pointer_array_size);
15638
if ((!having || having->val_int()))
15642
List_iterator_fast<Item> it(rollup.fields[i]);
15643
while ((item= it++))
15645
if (item->type() == Item::NULL_ITEM && item->is_result_field())
15646
item->save_in_result_field(1);
15648
copy_sum_funcs(sum_funcs_end[i+1], sum_funcs_end[i]);
15649
if ((write_error= table_arg->file->ha_write_row(table_arg->record[0])))
15651
if (create_myisam_from_heap(session, table_arg,
15652
tmp_table_param.start_recinfo,
15653
&tmp_table_param.recinfo,
15659
/* Restore ref_pointer_array */
15660
set_items_ref_array(current_ref_pointer_array);
15665
clear results if there are not rows found for group
15666
(end_send_group/end_write_group)
15671
clear_tables(this);
15672
copy_fields(&tmp_table_param);
15676
Item_sum *func, **func_ptr= sum_funcs;
15677
while ((func= *(func_ptr++)))
15685
Send a description about what how the select will be done to stdout.
15688
void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
15689
bool distinct,const char *message)
15691
List<Item> field_list;
15692
List<Item> item_list;
15693
Session *session=join->session;
15694
select_result *result=join->result;
15695
Item *item_null= new Item_null();
15696
const CHARSET_INFO * const cs= system_charset_info;
15698
/* Don't log this into the slow query log */
15699
session->server_status&= ~(SERVER_QUERY_NO_INDEX_USED | SERVER_QUERY_NO_GOOD_INDEX_USED);
15700
join->unit->offset_limit_cnt= 0;
15703
NOTE: the number/types of items pushed into item_list must be in sync with
15704
EXPLAIN column types as they're "defined" in Session::send_explain_fields()
15708
item_list.push_back(new Item_int((int32_t)
15709
join->select_lex->select_number));
15710
item_list.push_back(new Item_string(join->select_lex->type,
15711
strlen(join->select_lex->type), cs));
15712
for (uint32_t i=0 ; i < 7; i++)
15713
item_list.push_back(item_null);
15714
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15715
item_list.push_back(item_null);
15717
item_list.push_back(new Item_string(message,strlen(message),cs));
15718
if (result->send_data(item_list))
15721
else if (join->select_lex == join->unit->fake_select_lex)
15724
here we assume that the query will return at least two rows, so we
15725
show "filesort" in EXPLAIN. Of course, sometimes we'll be wrong
15726
and no filesort will be actually done, but executing all selects in
15727
the UNION to provide precise EXPLAIN information will hardly be
15730
char table_name_buffer[NAME_LEN];
15733
item_list.push_back(new Item_null);
15735
item_list.push_back(new Item_string(join->select_lex->type,
15736
strlen(join->select_lex->type),
15740
Select_Lex *sl= join->unit->first_select();
15741
uint32_t len= 6, lastop= 0;
15742
memcpy(table_name_buffer, STRING_WITH_LEN("<union"));
15743
for (; sl && len + lastop + 5 < NAME_LEN; sl= sl->next_select())
15746
lastop= snprintf(table_name_buffer + len, NAME_LEN - len,
15747
"%u,", sl->select_number);
15749
if (sl || len + lastop >= NAME_LEN)
15751
memcpy(table_name_buffer + len, STRING_WITH_LEN("...>") + 1);
15757
table_name_buffer[len - 1]= '>'; // change ',' to '>'
15759
item_list.push_back(new Item_string(table_name_buffer, len, cs));
15762
item_list.push_back(new Item_string(join_type_str[JT_ALL],
15763
strlen(join_type_str[JT_ALL]),
15765
/* possible_keys */
15766
item_list.push_back(item_null);
15768
item_list.push_back(item_null);
15770
item_list.push_back(item_null);
15772
item_list.push_back(item_null);
15774
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15775
item_list.push_back(item_null);
15777
item_list.push_back(item_null);
15779
if (join->unit->global_parameters->order_list.first)
15780
item_list.push_back(new Item_string("Using filesort",
15783
item_list.push_back(new Item_string("", 0, cs));
15785
if (result->send_data(item_list))
15790
table_map used_tables=0;
15791
for (uint32_t i=0 ; i < join->tables ; i++)
15793
JOIN_TAB *tab=join->join_tab+i;
15794
Table *table=tab->table;
15795
TableList *table_list= tab->table->pos_in_table_list;
15797
char buff1[512], buff2[512], buff3[512];
15798
char keylen_str_buf[64];
15799
String extra(buff, sizeof(buff),cs);
15800
char table_name_buffer[NAME_LEN];
15801
String tmp1(buff1,sizeof(buff1),cs);
15802
String tmp2(buff2,sizeof(buff2),cs);
15803
String tmp3(buff3,sizeof(buff3),cs);
15812
item_list.push_back(new Item_uint((uint32_t)
15813
join->select_lex->select_number));
15815
item_list.push_back(new Item_string(join->select_lex->type,
15816
strlen(join->select_lex->type),
15818
if (tab->type == JT_ALL && tab->select && tab->select->quick)
15820
quick_type= tab->select->quick->get_type();
15821
if ((quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE) ||
15822
(quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT) ||
15823
(quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION))
15824
tab->type = JT_INDEX_MERGE;
15826
tab->type = JT_RANGE;
15829
if (table->derived_select_number)
15831
/* Derived table name generation */
15832
int len= snprintf(table_name_buffer, sizeof(table_name_buffer)-1,
15834
table->derived_select_number);
15835
item_list.push_back(new Item_string(table_name_buffer, len, cs));
15839
TableList *real_table= table->pos_in_table_list;
15840
item_list.push_back(new Item_string(real_table->alias,
15841
strlen(real_table->alias),
15844
/* "type" column */
15845
item_list.push_back(new Item_string(join_type_str[tab->type],
15846
strlen(join_type_str[tab->type]),
15848
/* Build "possible_keys" value and add it to item_list */
15849
if (!tab->keys.is_clear_all())
15852
for (j=0 ; j < table->s->keys ; j++)
15854
if (tab->keys.is_set(j))
15858
tmp1.append(table->key_info[j].name,
15859
strlen(table->key_info[j].name),
15860
system_charset_info);
15865
item_list.push_back(new Item_string(tmp1.ptr(),tmp1.length(),cs));
15867
item_list.push_back(item_null);
15869
/* Build "key", "key_len", and "ref" values and add them to item_list */
15870
if (tab->ref.key_parts)
15872
KEY *key_info=table->key_info+ tab->ref.key;
15873
register uint32_t length;
15874
item_list.push_back(new Item_string(key_info->name,
15875
strlen(key_info->name),
15876
system_charset_info));
15877
length= int64_t2str(tab->ref.key_length, keylen_str_buf, 10) -
15879
item_list.push_back(new Item_string(keylen_str_buf, length,
15880
system_charset_info));
15881
for (store_key **ref=tab->ref.key_copy ; *ref ; ref++)
15885
tmp2.append((*ref)->name(), strlen((*ref)->name()),
15886
system_charset_info);
15888
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15890
else if (tab->type == JT_NEXT)
15892
KEY *key_info=table->key_info+ tab->index;
15893
register uint32_t length;
15894
item_list.push_back(new Item_string(key_info->name,
15895
strlen(key_info->name),cs));
15896
length= int64_t2str(key_info->key_length, keylen_str_buf, 10) -
15898
item_list.push_back(new Item_string(keylen_str_buf,
15900
system_charset_info));
15901
item_list.push_back(item_null);
15903
else if (tab->select && tab->select->quick)
15905
tab->select->quick->add_keys_and_lengths(&tmp2, &tmp3);
15906
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15907
item_list.push_back(new Item_string(tmp3.ptr(),tmp3.length(),cs));
15908
item_list.push_back(item_null);
15912
if (table_list->schema_table && table_list->schema_table->i_s_requested_object & OPTIMIZE_I_S_TABLE)
15914
const char *tmp_buff;
15916
if (table_list->has_db_lookup_value)
15918
f_idx= table_list->schema_table->idx_field1;
15919
tmp_buff= table_list->schema_table->fields_info[f_idx].field_name;
15920
tmp2.append(tmp_buff, strlen(tmp_buff), cs);
15922
if (table_list->has_table_lookup_value)
15924
if (table_list->has_db_lookup_value)
15926
f_idx= table_list->schema_table->idx_field2;
15927
tmp_buff= table_list->schema_table->fields_info[f_idx].field_name;
15928
tmp2.append(tmp_buff, strlen(tmp_buff), cs);
15931
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15933
item_list.push_back(item_null);
15936
item_list.push_back(item_null);
15937
item_list.push_back(item_null);
15938
item_list.push_back(item_null);
15941
/* Add "rows" field to item_list. */
15942
if (table_list->schema_table)
15945
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15946
item_list.push_back(item_null);
15948
item_list.push_back(item_null);
15952
double examined_rows;
15953
if (tab->select && tab->select->quick)
15954
examined_rows= rows2double(tab->select->quick->records);
15955
else if (tab->type == JT_NEXT || tab->type == JT_ALL)
15956
examined_rows= rows2double(tab->limit ? tab->limit :
15957
tab->table->file->records());
15959
examined_rows= join->best_positions[i].records_read;
15961
item_list.push_back(new Item_int((int64_t) (uint64_t) examined_rows,
15962
MY_INT64_NUM_DECIMAL_DIGITS));
15964
/* Add "filtered" field to item_list. */
15965
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15969
f= (float) (100.0 * join->best_positions[i].records_read /
15971
item_list.push_back(new Item_float(f, 2));
15975
/* Build "Extra" field and add it to item_list. */
15976
bool key_read=table->key_read;
15977
if ((tab->type == JT_NEXT || tab->type == JT_CONST) &&
15978
table->covering_keys.is_set(tab->index))
15980
if (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT &&
15981
!((QUICK_ROR_INTERSECT_SELECT*)tab->select->quick)->need_to_fetch_row)
15985
item_list.push_back(new Item_string(tab->info,strlen(tab->info),cs));
15986
else if (tab->packed_info & TAB_INFO_HAVE_VALUE)
15988
if (tab->packed_info & TAB_INFO_USING_INDEX)
15989
extra.append(STRING_WITH_LEN("; Using index"));
15990
if (tab->packed_info & TAB_INFO_USING_WHERE)
15991
extra.append(STRING_WITH_LEN("; Using where"));
15992
if (tab->packed_info & TAB_INFO_FULL_SCAN_ON_NULL)
15993
extra.append(STRING_WITH_LEN("; Full scan on NULL key"));
15994
/* Skip initial "; "*/
15995
const char *str= extra.ptr();
15996
uint32_t len= extra.length();
16002
item_list.push_back(new Item_string(str, len, cs));
16006
uint32_t keyno= MAX_KEY;
16007
if (tab->ref.key_parts)
16008
keyno= tab->ref.key;
16009
else if (tab->select && tab->select->quick)
16010
keyno = tab->select->quick->index;
16012
if (keyno != MAX_KEY && keyno == table->file->pushed_idx_cond_keyno &&
16013
table->file->pushed_idx_cond)
16014
extra.append(STRING_WITH_LEN("; Using index condition"));
16016
if (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION ||
16017
quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT ||
16018
quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE)
16020
extra.append(STRING_WITH_LEN("; Using "));
16021
tab->select->quick->add_info_string(&extra);
16025
if (tab->use_quick == 2)
16027
/* 4 bits per 1 hex digit + terminating '\0' */
16028
char buf[MAX_KEY / 4 + 1];
16029
extra.append(STRING_WITH_LEN("; Range checked for each "
16030
"record (index map: 0x"));
16031
extra.append(tab->keys.print(buf));
16034
else if (tab->select->cond)
16036
const COND *pushed_cond= tab->table->file->pushed_cond;
16038
if (session->variables.engine_condition_pushdown && pushed_cond)
16040
extra.append(STRING_WITH_LEN("; Using where with pushed "
16042
if (session->lex->describe & DESCRIBE_EXTENDED)
16044
extra.append(STRING_WITH_LEN(": "));
16045
((COND *)pushed_cond)->print(&extra, QT_ORDINARY);
16049
extra.append(STRING_WITH_LEN("; Using where"));
16054
if (quick_type == QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX)
16055
extra.append(STRING_WITH_LEN("; Using index for group-by"));
16057
extra.append(STRING_WITH_LEN("; Using index"));
16059
if (table->reginfo.not_exists_optimize)
16060
extra.append(STRING_WITH_LEN("; Not exists"));
16062
if (quick_type == QUICK_SELECT_I::QS_TYPE_RANGE &&
16063
!(((QUICK_RANGE_SELECT*)(tab->select->quick))->mrr_flags &
16064
HA_MRR_USE_DEFAULT_IMPL))
16066
extra.append(STRING_WITH_LEN("; Using MRR"));
16069
if (table_list->schema_table &&
16070
table_list->schema_table->i_s_requested_object & OPTIMIZE_I_S_TABLE)
16072
if (!table_list->table_open_method)
16073
extra.append(STRING_WITH_LEN("; Skip_open_table"));
16074
else if (table_list->table_open_method == OPEN_FRM_ONLY)
16075
extra.append(STRING_WITH_LEN("; Open_frm_only"));
16077
extra.append(STRING_WITH_LEN("; Open_full_table"));
16078
if (table_list->has_db_lookup_value &&
16079
table_list->has_table_lookup_value)
16080
extra.append(STRING_WITH_LEN("; Scanned 0 databases"));
16081
else if (table_list->has_db_lookup_value ||
16082
table_list->has_table_lookup_value)
16083
extra.append(STRING_WITH_LEN("; Scanned 1 database"));
16085
extra.append(STRING_WITH_LEN("; Scanned all databases"));
16087
if (need_tmp_table)
16090
extra.append(STRING_WITH_LEN("; Using temporary"));
16095
extra.append(STRING_WITH_LEN("; Using filesort"));
16097
if (distinct & test_all_bits(used_tables,session->used_tables))
16098
extra.append(STRING_WITH_LEN("; Distinct"));
16100
if (tab->insideout_match_tab)
16102
extra.append(STRING_WITH_LEN("; LooseScan"));
16105
if (tab->flush_weedout_table)
16106
extra.append(STRING_WITH_LEN("; Start temporary"));
16107
else if (tab->check_weed_out_table)
16108
extra.append(STRING_WITH_LEN("; End temporary"));
16109
else if (tab->do_firstmatch)
16111
extra.append(STRING_WITH_LEN("; FirstMatch("));
16112
Table *prev_table=tab->do_firstmatch->table;
16113
if (prev_table->derived_select_number)
16115
char namebuf[NAME_LEN];
16116
/* Derived table name generation */
16117
int len= snprintf(namebuf, sizeof(namebuf)-1,
16119
prev_table->derived_select_number);
16120
extra.append(namebuf, len);
16123
extra.append(prev_table->pos_in_table_list->alias);
16124
extra.append(STRING_WITH_LEN(")"));
16127
for (uint32_t part= 0; part < tab->ref.key_parts; part++)
16129
if (tab->ref.cond_guards[part])
16131
extra.append(STRING_WITH_LEN("; Full scan on NULL key"));
16136
if (i > 0 && tab[-1].next_select == sub_select_cache)
16137
extra.append(STRING_WITH_LEN("; Using join buffer"));
16139
/* Skip initial "; "*/
16140
const char *str= extra.ptr();
16141
uint32_t len= extra.length();
16147
item_list.push_back(new Item_string(str, len, cs));
16149
// For next iteration
16150
used_tables|=table->map;
16151
if (result->send_data(item_list))
16155
for (Select_Lex_Unit *unit= join->select_lex->first_inner_unit();
16157
unit= unit->next_unit())
16159
if (mysql_explain_union(session, unit, result))
16166
bool mysql_explain_union(Session *session, Select_Lex_Unit *unit, select_result *result)
16169
Select_Lex *first= unit->first_select();
16171
for (Select_Lex *sl= first;
16173
sl= sl->next_select())
16175
// drop UNCACHEABLE_EXPLAIN, because it is for internal usage only
16176
uint8_t uncacheable= (sl->uncacheable & ~UNCACHEABLE_EXPLAIN);
16177
sl->type= (((&session->lex->select_lex)==sl)?
16178
(sl->first_inner_unit() || sl->next_select() ?
16179
"PRIMARY" : "SIMPLE"):
16181
((sl->linkage == DERIVED_TABLE_TYPE) ?
16183
((uncacheable & UNCACHEABLE_DEPENDENT) ?
16184
"DEPENDENT SUBQUERY":
16185
(uncacheable?"UNCACHEABLE SUBQUERY":
16187
((uncacheable & UNCACHEABLE_DEPENDENT) ?
16189
uncacheable?"UNCACHEABLE UNION":
16191
sl->options|= SELECT_DESCRIBE;
16193
if (unit->is_union())
16195
unit->fake_select_lex->select_number= UINT_MAX; // jost for initialization
16196
unit->fake_select_lex->type= "UNION RESULT";
16197
unit->fake_select_lex->options|= SELECT_DESCRIBE;
16198
if (!(res= unit->prepare(session, result, SELECT_NO_UNLOCK | SELECT_DESCRIBE)))
16200
res|= unit->cleanup();
16204
session->lex->current_select= first;
16205
unit->set_limit(unit->global_parameters);
16206
res= mysql_select(session, &first->ref_pointer_array,
16207
(TableList*) first->table_list.first,
16208
first->with_wild, first->item_list,
16210
first->order_list.elements +
16211
first->group_list.elements,
16212
(order_st*) first->order_list.first,
16213
(order_st*) first->group_list.first,
16215
first->options | session->options | SELECT_DESCRIBE,
16216
result, unit, first);
16218
return(res || session->is_error());
6256
16222
static void print_table_array(Session *session, String *str, TableList **table,
6257
16223
TableList **end)