49
47
#include "drizzled/lock.h"
50
48
#include "drizzled/item/outer_ref.h"
51
49
#include "drizzled/index_hint.h"
52
#include "drizzled/memory/multi_malloc.h"
53
#include "drizzled/records.h"
54
#include "drizzled/internal/iocache.h"
56
#include "drizzled/sql_union.h"
57
#include "drizzled/optimizer/key_field.h"
58
#include "drizzled/optimizer/position.h"
59
#include "drizzled/optimizer/sargable_param.h"
60
#include "drizzled/optimizer/key_use.h"
61
#include "drizzled/optimizer/range.h"
62
#include "drizzled/optimizer/quick_range_select.h"
63
#include "drizzled/optimizer/quick_ror_intersect_select.h"
65
54
using namespace std;
70
static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b);
56
const char *join_type_str[]={ "UNKNOWN","system","const","eq_ref","ref",
57
"MAYBE_REF","ALL","range","index",
58
"ref_or_null","unique_subquery","index_subquery",
62
struct st_sargable_param;
64
static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array);
65
static bool make_join_statistics(JOIN *join, TableList *leaves, COND *conds,
66
DYNAMIC_ARRAY *keyuse);
67
static bool update_ref_and_keys(Session *session, DYNAMIC_ARRAY *keyuse,
69
uint32_t tables, COND *conds,
70
COND_EQUAL *cond_equal,
71
table_map table_map, Select_Lex *select_lex,
72
st_sargable_param **sargables);
73
static int sort_keyuse(KEYUSE *a,KEYUSE *b);
74
static void set_position(JOIN *join,uint32_t index,JOIN_TAB *table,KEYUSE *key);
75
static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
76
table_map used_tables);
77
static bool choose_plan(JOIN *join,table_map join_tables);
79
static void best_access_path(JOIN *join, JOIN_TAB *s, Session *session,
80
table_map remaining_tables, uint32_t idx,
81
double record_count, double read_time);
82
static void optimize_straight_join(JOIN *join, table_map join_tables);
83
static bool greedy_search(JOIN *join, table_map remaining_tables,
84
uint32_t depth, uint32_t prune_level);
85
static bool best_extension_by_limited_search(JOIN *join,
86
table_map remaining_tables,
87
uint32_t idx, double record_count,
88
double read_time, uint32_t depth,
89
uint32_t prune_level);
90
static uint32_t determine_search_depth(JOIN* join);
91
extern "C" int join_tab_cmp(const void* ptr1, const void* ptr2);
92
extern "C" int join_tab_cmp_straight(const void* ptr1, const void* ptr2);
94
TODO: 'find_best' is here only temporarily until 'greedy_search' is
97
static bool find_best(JOIN *join,table_map rest_tables,uint32_t index,
98
double record_count,double read_time);
99
static uint32_t cache_record_length(JOIN *join,uint32_t index);
100
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref);
101
static bool get_best_combination(JOIN *join);
102
static store_key *get_store_key(Session *session,
103
KEYUSE *keyuse, table_map used_tables,
104
KEY_PART_INFO *key_part, unsigned char *key_buff,
105
uint32_t maybe_null);
106
static bool make_simple_join(JOIN *join,Table *tmp_table);
107
static void make_outerjoin_info(JOIN *join);
108
static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *item);
109
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after);
110
static bool only_eq_ref_tables(JOIN *join, order_st *order, table_map tables);
111
static void update_depend_map(JOIN *join);
112
static void update_depend_map(JOIN *join, order_st *order);
113
static order_st *remove_constants(JOIN *join,order_st *first_order,COND *cond,
114
bool change_list, bool *simple_order);
115
static int return_zero_rows(JOIN *join, select_result *res,TableList *tables,
116
List<Item> &fields, bool send_row,
117
uint64_t select_options, const char *info,
71
119
static COND *build_equal_items(Session *session, COND *cond,
72
120
COND_EQUAL *inherited,
73
121
List<TableList> *join_list,
74
122
COND_EQUAL **cond_equal_ref);
123
static COND* substitute_for_best_equal_field(COND *cond,
124
COND_EQUAL *cond_equal,
125
void *table_join_idx);
126
static COND *simplify_joins(JOIN *join, List<TableList> *join_list,
127
COND *conds, bool top, bool in_sj);
128
static bool check_interleaving_with_nj(JOIN_TAB *last, JOIN_TAB *next);
129
static void restore_prev_nj_state(JOIN_TAB *last);
130
static void reset_nj_counters(List<TableList> *join_list);
131
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list,
132
uint32_t first_unused);
135
void advance_sj_state(const table_map remaining_tables, const JOIN_TAB *tab);
136
static void restore_prev_sj_state(const table_map remaining_tables,
137
const JOIN_TAB *tab);
139
static COND *optimize_cond(JOIN *join, COND *conds,
140
List<TableList> *join_list,
141
Item::cond_result *cond_value);
142
static bool const_expression_in_where(COND *conds,Item *item, Item **comp_item);
143
static int do_select(JOIN *join,List<Item> *fields,Table *tmp_table);
145
static enum_nested_loop_state
146
evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,
148
static enum_nested_loop_state
149
evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab);
150
static enum_nested_loop_state
151
flush_cached_records(JOIN *join, JOIN_TAB *join_tab, bool skip_last);
152
static enum_nested_loop_state
153
end_send(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
154
static enum_nested_loop_state
155
end_write(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
156
static enum_nested_loop_state
157
end_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
158
static enum_nested_loop_state
159
end_unique_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
161
static int join_read_const_table(JOIN_TAB *tab, POSITION *pos);
162
static int join_read_system(JOIN_TAB *tab);
163
static int join_read_const(JOIN_TAB *tab);
164
static int join_read_key(JOIN_TAB *tab);
165
static int join_read_always_key(JOIN_TAB *tab);
166
static int join_read_last_key(JOIN_TAB *tab);
167
static int join_no_more_records(READ_RECORD *info);
168
static int join_read_next(READ_RECORD *info);
169
static int join_read_next_different(READ_RECORD *info);
170
static int join_init_quick_read_record(JOIN_TAB *tab);
171
static int test_if_quick_select(JOIN_TAB *tab);
172
static int join_init_read_record(JOIN_TAB *tab);
173
static int join_read_first(JOIN_TAB *tab);
174
static int join_read_next_same(READ_RECORD *info);
175
static int join_read_next_same_diff(READ_RECORD *info);
176
static int join_read_last(JOIN_TAB *tab);
177
static int join_read_prev_same(READ_RECORD *info);
178
static int join_read_prev(READ_RECORD *info);
179
int join_read_always_key_or_null(JOIN_TAB *tab);
180
int join_read_next_same_or_null(READ_RECORD *info);
181
static COND *make_cond_for_table(COND *cond,table_map table,
182
table_map used_table,
183
bool exclude_expensive_cond);
76
184
static Item* part_of_refkey(Table *form,Field *field);
77
static bool cmp_buffer_with_ref(JoinTable *tab);
78
static void change_cond_ref_to_const(Session *session,
79
vector<COND_CMP>& save_list,
84
static bool copy_blobs(Field **ptr);
185
static bool test_if_skip_sort_order(JOIN_TAB *tab,order_st *order,
186
ha_rows select_limit, bool no_changes,
188
static bool list_contains_unique_index(Table *table,
189
bool (*find_func) (Field *, void *), void *data);
190
static bool find_field_in_item_list (Field *field, void *data);
191
static bool find_field_in_order_list (Field *field, void *data);
192
static int create_sort_index(Session *session, JOIN *join, order_st *order,
193
ha_rows filesort_limit, ha_rows select_limit,
195
static int remove_duplicates(JOIN *join,Table *entry,List<Item> &fields,
197
static int remove_dup_with_compare(Session *session, Table *entry, Field **field,
198
uint32_t offset, Item *having);
199
static int remove_dup_with_hash_index(Session *session,Table *table,
200
uint32_t field_count, Field **first_field,
201
uint32_t key_length, Item *having);
202
static int join_init_cache(Session *session,JOIN_TAB *tables,uint32_t table_count);
203
static uint32_t used_blob_length(CACHE_FIELD **ptr);
204
static bool store_record_in_cache(JOIN_CACHE *cache);
205
static void reset_cache_read(JOIN_CACHE *cache);
206
static void reset_cache_write(JOIN_CACHE *cache);
207
static void read_cached_record(JOIN_TAB *tab);
208
static bool cmp_buffer_with_ref(JOIN_TAB *tab);
209
static order_st *create_distinct_group(Session *session, Item **ref_pointer_array,
210
order_st *order, List<Item> &fields,
211
List<Item> &all_fields,
212
bool *all_order_by_fields_used);
213
static bool test_if_subpart(order_st *a,order_st *b);
214
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables);
215
static void calc_group_buffer(JOIN *join,order_st *group);
216
static bool make_group_fields(JOIN *main_join, JOIN *curr_join);
217
static bool alloc_group_fields(JOIN *join,order_st *group);
218
// Create list for using with tempory table
219
static bool change_to_use_tmp_fields(Session *session, Item **ref_pointer_array,
220
List<Item> &new_list1,
221
List<Item> &new_list2,
222
uint32_t elements, List<Item> &items);
223
// Create list for using with tempory table
224
static bool change_refs_to_tmp_fields(Session *session, Item **ref_pointer_array,
225
List<Item> &new_list1,
226
List<Item> &new_list2,
227
uint32_t elements, List<Item> &items);
228
static void init_tmptable_sum_functions(Item_sum **func);
229
static void update_tmptable_sum_func(Item_sum **func,Table *tmp_table);
230
static void copy_sum_funcs(Item_sum **func_ptr, Item_sum **end);
231
static bool add_ref_to_table_cond(Session *session, JOIN_TAB *join_tab);
232
static bool setup_sum_funcs(Session *session, Item_sum **func_ptr);
233
static bool init_sum_functions(Item_sum **func, Item_sum **end);
234
static bool update_sum_func(Item_sum **func);
235
void select_describe(JOIN *join, bool need_tmp_table,bool need_order,
236
bool distinct, const char *message=NULL);
237
static Item *remove_additional_cond(Item* conds);
238
static void add_group_and_distinct_keys(JOIN *join, JOIN_TAB *join_tab);
239
static bool test_if_ref(Item_field *left_item,Item *right_item);
240
static bool replace_where_subcondition(JOIN *join, Item *old_cond,
241
Item *new_cond, bool fix_fields);
86
243
static bool eval_const_cond(COND *cond)
88
245
return ((Item_func*) cond)->val_int() ? true : false;
92
250
This is used to mark equalities that were made from i-th IN-equality.
93
251
We limit semi-join InsideOut optimization to handling max 64 inequalities,
419
Function to setup clauses without sum functions.
421
inline int setup_without_group(Session *session, Item **ref_pointer_array,
425
List<Item> &all_fields,
428
order_st *group, bool *hidden_group_fields)
431
nesting_map save_allow_sum_func=session->lex->allow_sum_func ;
433
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
434
res= setup_conds(session, tables, leaves, conds);
436
session->lex->allow_sum_func|= 1 << session->lex->current_select->nest_level;
437
res= res || setup_order(session, ref_pointer_array, tables, fields, all_fields,
439
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
440
res= res || setup_group(session, ref_pointer_array, tables, fields, all_fields,
441
group, hidden_group_fields);
442
session->lex->allow_sum_func= save_allow_sum_func;
265
446
/*****************************************************************************
266
447
Check fields, find best join, do the select and output fields.
267
448
mysql_select assumes that all tables are already opened
268
449
*****************************************************************************/
452
Prepare of whole select (including sub queries in future).
455
Add check of calculation of GROUP functions and fields:
456
SELECT COUNT(*)+table.col1 from table1;
464
JOIN::prepare(Item ***rref_pointer_array,
465
TableList *tables_init,
466
uint32_t wild_num, COND *conds_init, uint32_t og_num,
467
order_st *order_init, order_st *group_init,
469
Select_Lex *select_lex_arg,
470
Select_Lex_Unit *unit_arg)
472
// to prevent double initialization on EXPLAIN
478
group_list= group_init;
480
tables_list= tables_init;
481
select_lex= select_lex_arg;
482
select_lex->join= this;
483
join_list= &select_lex->top_join_list;
484
union_part= unit_arg->is_union();
486
session->lex->current_select->is_item_list_lookup= 1;
488
If we have already executed SELECT, then it have not sense to prevent
489
its table from update (see unique_table())
491
if (session->derived_tables_processing)
492
select_lex->exclude_from_table_unique_test= true;
494
/* Check that all tables, fields, conds and order are ok */
496
if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
497
setup_tables_and_check_access(session, &select_lex->context, join_list,
498
tables_list, &select_lex->leaf_tables,
502
TableList *table_ptr;
503
for (table_ptr= select_lex->leaf_tables;
505
table_ptr= table_ptr->next_leaf)
508
if (setup_wild(session, tables_list, fields_list, &all_fields, wild_num) ||
509
select_lex->setup_ref_array(session, og_num) ||
510
setup_fields(session, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ,
512
setup_without_group(session, (*rref_pointer_array), tables_list,
513
select_lex->leaf_tables, fields_list,
514
all_fields, &conds, order, group_list,
515
&hidden_group_fields))
516
return(-1); /* purecov: inspected */
518
ref_pointer_array= *rref_pointer_array;
522
nesting_map save_allow_sum_func= session->lex->allow_sum_func;
523
session->where="having clause";
524
session->lex->allow_sum_func|= 1 << select_lex_arg->nest_level;
525
select_lex->having_fix_field= 1;
526
bool having_fix_rc= (!having->fixed &&
527
(having->fix_fields(session, &having) ||
528
having->check_cols(1)));
529
select_lex->having_fix_field= 0;
530
if (having_fix_rc || session->is_error())
531
return(-1); /* purecov: inspected */
532
session->lex->allow_sum_func= save_allow_sum_func;
536
Item_subselect *subselect;
537
Item_in_subselect *in_subs= NULL;
539
Are we in a subquery predicate?
540
TODO: the block below will be executed for every PS execution without need.
542
if ((subselect= select_lex->master_unit()->item))
544
bool do_semijoin= !test(session->variables.optimizer_switch &
545
OPTIMIZER_SWITCH_NO_SEMIJOIN);
546
if (subselect->substype() == Item_subselect::IN_SUBS)
547
in_subs= (Item_in_subselect*)subselect;
550
Check if we're in subquery that is a candidate for flattening into a
551
semi-join (which is done done in flatten_subqueries()). The
553
1. Subquery predicate is an IN/=ANY subq predicate
554
2. Subquery is a single SELECT (not a UNION)
555
3. Subquery does not have GROUP BY or order_st BY
556
4. Subquery does not use aggregate functions or HAVING
557
5. Subquery predicate is at the AND-top-level of ON/WHERE clause
558
6. No execution method was already chosen (by a prepared statement).
560
(*). We are not in a subquery of a single table UPDATE/DELETE that
561
doesn't have a JOIN (TODO: We should handle this at some
562
point by switching to multi-table UPDATE/DELETE)
564
(**). We're not in a confluent table-less subquery, like
568
!select_lex->master_unit()->first_select()->next_select() && // 2
569
!select_lex->group_list.elements && !order && // 3
570
!having && !select_lex->with_sum_func && // 4
571
session->session_marker && // 5
572
select_lex->outer_select()->join && // (*)
573
select_lex->master_unit()->first_select()->leaf_tables && // (**)
575
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
578
if (!in_subs->left_expr->fixed &&
579
in_subs->left_expr->fix_fields(session, &in_subs->left_expr))
584
Check that the right part of the subselect contains no more than one
585
column. E.g. in SELECT 1 IN (SELECT * ..) the right part is (SELECT * ...)
587
if (subselect->substype() == Item_subselect::IN_SUBS &&
588
(select_lex->item_list.elements !=
589
((Item_in_subselect*)subselect)->left_expr->cols()))
591
my_error(ER_OPERAND_COLUMNS, MYF(0), ((Item_in_subselect*)subselect)->left_expr->cols());
596
/* Register the subquery for further processing */
597
select_lex->outer_select()->join->sj_subselects.append(session->mem_root, in_subs);
598
in_subs->expr_join_nest= (TableList*)session->session_marker;
602
bool do_materialize= !test(session->variables.optimizer_switch &
603
OPTIMIZER_SWITCH_NO_MATERIALIZATION);
605
Check if the subquery predicate can be executed via materialization.
606
The required conditions are:
607
1. Subquery predicate is an IN/=ANY subq predicate
608
2. Subquery is a single SELECT (not a UNION)
609
3. Subquery is not a table-less query. In this case there is no
610
point in materializing.
611
4. Subquery predicate is a top-level predicate
612
(this implies it is not negated)
613
TODO: this is a limitation that should be lifeted once we
614
implement correct NULL semantics (WL#3830)
615
5. Subquery is non-correlated
617
This is an overly restrictive condition. It can be extended to:
618
(Subquery is non-correlated ||
619
Subquery is correlated to any query outer to IN predicate ||
620
(Subquery is correlated to the immediate outer query &&
621
Subquery !contains {GROUP BY, order_st BY [LIMIT],
622
aggregate functions) && subquery predicate is not under "NOT IN"))
623
6. No execution method was already chosen (by a prepared statement).
625
(*) The subquery must be part of a SELECT statement. The current
626
condition also excludes multi-table update statements.
628
We have to determine whether we will perform subquery materialization
629
before calling the IN=>EXISTS transformation, so that we know whether to
630
perform the whole transformation or only that part of it which wraps
631
Item_in_subselect in an Item_in_optimizer.
633
if (do_materialize &&
635
!select_lex->master_unit()->first_select()->next_select() && // 2
636
select_lex->master_unit()->first_select()->leaf_tables && // 3
637
session->lex->sql_command == SQLCOM_SELECT) // *
639
if (in_subs->is_top_level_item() && // 4
640
!in_subs->is_correlated && // 5
641
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
642
in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
645
Item_subselect::trans_res trans_res;
646
if ((trans_res= subselect->select_transformer(this)) !=
647
Item_subselect::RES_OK)
649
return((trans_res == Item_subselect::RES_ERROR));
658
for (ord= order; ord; ord= ord->next)
660
Item *item= *ord->item;
661
if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
662
item->split_sum_func(session, ref_pointer_array, all_fields);
666
if (having && having->with_sum_func)
667
having->split_sum_func(session, ref_pointer_array, all_fields,
669
if (select_lex->inner_sum_func_list)
671
Item_sum *end=select_lex->inner_sum_func_list;
672
Item_sum *item_sum= end;
675
item_sum= item_sum->next;
676
item_sum->split_sum_func(session, ref_pointer_array,
677
all_fields, item_sum->ref_by, false);
678
} while (item_sum != end);
681
if (select_lex->inner_refs_list.elements &&
682
fix_inner_refs(session, all_fields, select_lex, ref_pointer_array))
686
Check if there are references to un-aggregated columns when computing
687
aggregate functions with implicit grouping (there is no GROUP BY).
689
MODE_ONLY_FULL_GROUP_BY is enabled here by default
691
if (!group_list && select_lex->full_group_by_flag == (NON_AGG_FIELD_USED | SUM_FUNC_USED))
693
my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
694
ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
698
/* Caclulate the number of groups */
700
for (order_st *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
705
goto err; /* purecov: inspected */
707
if (result && result->prepare(fields_list, unit_arg))
708
goto err; /* purecov: inspected */
710
/* Init join struct */
711
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
712
ref_pointer_array_size= all_fields.elements*sizeof(Item*);
713
this->group= group_list != 0;
716
#ifdef RESTRICTED_GROUP
717
if (sum_func_count && !group_list && (func_count || field_count))
719
my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
723
if (select_lex->olap == ROLLUP_TYPE && rollup_init())
725
if (alloc_func_list())
731
return(-1); /* purecov: inspected */
736
Remove the predicates pushed down into the subquery
739
JOIN::remove_subq_pushed_predicates()
740
where IN Must be NULL
741
OUT The remaining WHERE condition, or NULL
744
Given that this join will be executed using (unique|index)_subquery,
745
without "checking NULL", remove the predicates that were pushed down
748
If the subquery compares scalar values, we can remove the condition that
749
was wrapped into trig_cond (it will be checked when needed by the subquery
752
If the subquery compares row values, we need to keep the wrapped
753
equalities in the WHERE clause: when the left (outer) tuple has both NULL
754
and non-NULL values, we'll do a full table scan and will rely on the
755
equalities corresponding to non-NULL parts of left tuple to filter out
756
non-matching records.
758
TODO: We can remove the equalities that will be guaranteed to be true by the
759
fact that subquery engine will be using index lookup. This must be done only
760
for cases where there are no conversion errors of significance, e.g. 257
761
that is searched in a byte. But this requires homogenization of the return
762
codes of all Field*::store() methods.
765
void JOIN::remove_subq_pushed_predicates(Item **where)
767
if (conds->type() == Item::FUNC_ITEM &&
768
((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
769
((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
770
((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
771
test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
772
((Item_func *)conds)->arguments()[0]))
271
781
Index lookup-based subquery: save some flags for EXPLAIN output
820
Check if the table's rowid is included in the temptable
823
sj_table_is_included()
825
join_tab The table to be checked
828
SemiJoinDuplicateElimination: check the table's rowid should be included
829
in the temptable. This is so if
831
1. The table is not embedded within some semi-join nest
832
2. The has been pulled out of a semi-join nest, or
834
3. The table is functionally dependent on some previous table
836
[4. This is also true for constant tables that can't be
837
NULL-complemented but this function is not called for such tables]
840
true - Include table's rowid
844
static bool sj_table_is_included(JOIN *join, JOIN_TAB *join_tab)
846
if (join_tab->emb_sj_nest)
849
/* Check if this table is functionally dependent on the tables that
850
are within the same outer join nest
852
TableList *embedding= join_tab->table->pos_in_table_list->embedding;
853
if (join_tab->type == JT_EQ_REF)
855
Table_map_iterator it(join_tab->ref.depend_map & ~PSEUDO_TABLE_BITS);
857
while ((idx= it.next_bit())!=Table_map_iterator::BITMAP_END)
859
JOIN_TAB *ref_tab= join->join_tab + idx;
860
if (embedding == ref_tab->table->pos_in_table_list->embedding)
863
/* Ok, functionally dependent */
866
/* Not functionally dependent => need to include*/
872
Setup the strategies to eliminate semi-join duplicates.
875
setup_semijoin_dups_elimination()
877
options Join options (needed to see if join buffering will be
879
no_jbuf_after Another bit of information re where join buffering will
883
Setup the strategies to eliminate semi-join duplicates. ATM there are 3
886
1. DuplicateWeedout (use of temptable to remove duplicates based on rowids
888
2. FirstMatch (pick only the 1st matching row combination of inner tables)
889
3. InsideOut (scanning the sj-inner table in a way that groups duplicates
890
together and picking the 1st one)
892
The join order has "duplicate-generating ranges", and every range is
893
served by one strategy or a combination of FirstMatch with with some
896
"Duplicate-generating range" is defined as a range within the join order
897
that contains all of the inner tables of a semi-join. All ranges must be
898
disjoint, if tables of several semi-joins are interleaved, then the ranges
899
are joined together, which is equivalent to converting
900
SELECT ... WHERE oe1 IN (SELECT ie1 ...) AND oe2 IN (SELECT ie2 )
902
SELECT ... WHERE (oe1, oe2) IN (SELECT ie1, ie2 ... ...)
905
Applicability conditions are as follows:
907
DuplicateWeedout strategy
908
~~~~~~~~~~~~~~~~~~~~~~~~~
910
(ot|nt)* [ it ((it|ot|nt)* (it|ot))] (nt)*
911
+------+ +=========================+ +---+
914
(1) - Prefix of OuterTables (those that participate in
915
IN-equality and/or are correlated with subquery) and outer
916
Noncorrelated Tables.
917
(2) - The handled range. The range starts with the first sj-inner
918
table, and covers all sj-inner and outer tables
919
Within the range, Inner, Outer, outer Noncorrelated tables
920
may follow in any order.
921
(3) - The suffix of outer Noncorrelated tables.
926
(ot|nt)* [ it ((it|nt)* it) ] (nt)*
927
+------+ +==================+ +---+
930
(1) - Prefix of outer and non-correlated tables
931
(2) - The handled range, which may contain only inner and
932
non-correlated tables.
933
(3) - The suffix of outer Noncorrelated tables.
938
(ot|ct|nt) [ insideout_tbl (ot|nt|it)* it ] (ot|nt)*
939
+--------+ +===========+ +=============+ +------+
942
(1) - Prefix that may contain any outer tables. The prefix must contain
943
all the non-trivially correlated outer tables. (non-trivially means
944
that the correlation is not just through the IN-equality).
946
(2) - Inner table for which the InsideOut scan is performed.
948
(3) - The remainder of the duplicate-generating range. It is served by
949
application of FirstMatch strategy, with the exception that
950
outer IN-correlated tables are considered to be non-correlated.
952
(4) - THe suffix of outer and outer non-correlated tables.
954
If several strategies are applicable, their relative priorities are:
959
This function walks over the join order and sets up the strategies by
960
setting appropriate members in join_tab structures.
964
true Out of memory error
968
int setup_semijoin_dups_elimination(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
970
table_map cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
973
0 - invalid (EOF marker),
975
2 - Temptable (maybe confluent),
976
3 - Temptable with join buffering
979
uint32_t start_idx; /* Left range bound */
980
uint32_t end_idx; /* Right range bound */
982
For Temptable strategy: Bitmap of all outer and correlated tables from
983
all involved join nests.
985
table_map outer_tables;
986
} dups_ranges [MAX_TABLES];
988
TableList *emb_insideout_nest= NULL;
989
table_map emb_sj_map= 0; /* A bitmap of sj-nests (that is, their sj-inner
990
tables) whose ranges we're in */
991
table_map emb_outer_tables= 0; /* sj-outer tables for those sj-nests */
992
table_map range_start_map= 0; /* table_map at current range start */
993
bool dealing_with_jbuf= false; /* true <=> table within cur range uses join buf */
998
First pass: locate the duplicate-generating ranges and pick the strategies.
1000
for (i=join->const_tables ; i < join->tables ; i++)
1002
JOIN_TAB *tab=join->join_tab+i;
1003
Table *table=tab->table;
1004
cur_map |= table->map;
1006
if (tab->emb_sj_nest) // Encountered an sj-inner table
1010
dups_ranges[cur_range].start_idx= i;
1011
range_start_map= cur_map & ~table->map;
1013
Remember if this is a possible start of range that is covered by
1014
the InsideOut strategy (the reason that it is not covered could
1015
be that it overlaps with anther semi-join's range. we don't
1016
support InsideOut for joined ranges)
1018
if (join->best_positions[i].use_insideout_scan)
1019
emb_insideout_nest= tab->emb_sj_nest;
1022
emb_sj_map |= tab->emb_sj_nest->sj_inner_tables;
1023
emb_outer_tables |= tab->emb_sj_nest->nested_join->sj_depends_on;
1025
if (tab->emb_sj_nest != emb_insideout_nest)
1028
Two different semi-joins interleave. This cannot be handled by
1031
emb_insideout_nest= NULL;
1035
if (emb_sj_map) /* We're in duplicate-generating range */
1037
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
1038
tab->type == JT_ALL && tab->use_quick != 2 && !tab->first_inner &&
1039
i <= no_jbuf_after && !dealing_with_jbuf)
1042
This table uses join buffering, which makes use of FirstMatch or
1043
InsideOut strategies impossible for the current and (we assume)
1044
preceding duplicate-producing ranges.
1045
That is, for the join order:
1047
x x [ x x] x [x x x] x [x x X* x] x
1049
+-----+ +-----+ | join buffering use
1052
we'll have to remove r1 and r2 and use duplicate-elimination
1053
strategy that spans all the tables, starting from the very 1st
1056
dealing_with_jbuf= true;
1057
emb_insideout_nest= false;
1060
Absorb all preceding duplicate-eliminating ranges. Their strategies
1063
for (int prev_range= 0; prev_range < cur_range; prev_range++)
1065
dups_ranges[cur_range].outer_tables |=
1066
dups_ranges[prev_range].outer_tables;
1068
dups_ranges[0].start_idx= 0; /* Will need to start from the 1st table */
1069
dups_ranges[0].outer_tables= dups_ranges[cur_range].outer_tables;
1074
Check if we are at the end of duplicate-producing range. We are if
1076
1. It's an InsideOut range (which presumes all correlated tables are
1077
in the prefix), and all inner tables are in the join order prefix,
1079
2. It's a DuplicateElimination range (possibly covering several
1080
SJ-nests), and all inner, outer, and correlated tables of all
1081
sj-nests are in the join order prefix.
1083
bool end_of_range= false;
1084
if (emb_insideout_nest &&
1085
bitmap_covers(cur_map, emb_insideout_nest->sj_inner_tables))
1087
/* Save that this range is handled with InsideOut: */
1088
dups_ranges[cur_range].strategy= 1;
1091
else if (bitmap_covers(cur_map, emb_outer_tables | emb_sj_map))
1094
This is a complete range to be handled with either DuplicateWeedout
1097
dups_ranges[cur_range].strategy= dealing_with_jbuf? 3 : 2;
1099
This will hold tables from within the range that need to be put
1100
into the join buffer before we can use the FirstMatch on its tail.
1102
dups_ranges[cur_range].outer_tables= emb_outer_tables &
1109
dups_ranges[cur_range].end_idx= i+1;
1110
emb_sj_map= emb_outer_tables= 0;
1111
emb_insideout_nest= NULL;
1112
dealing_with_jbuf= false;
1113
dups_ranges[++cur_range].strategy= 0;
1118
Session *session= join->session;
1119
SJ_TMP_TABLE **next_sjtbl_ptr= &join->sj_tmp_tables;
1121
Second pass: setup the chosen strategies
1123
for (int j= 0; j < cur_range; j++)
1125
JOIN_TAB *tab=join->join_tab + dups_ranges[j].start_idx;
1127
if (dups_ranges[j].strategy == 1) // InsideOut strategy
1129
tab->insideout_match_tab= join->join_tab + dups_ranges[j].end_idx - 1;
1132
else // DuplicateWeedout strategy
1134
SJ_TMP_TABLE::TAB sjtabs[MAX_TABLES];
1135
table_map weed_cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
1136
uint32_t jt_rowid_offset= 0; // # tuple bytes are already occupied (w/o NULL bytes)
1137
uint32_t jt_null_bits= 0; // # null bits in tuple bytes
1138
SJ_TMP_TABLE::TAB *last_tab= sjtabs;
1139
uint32_t rowid_keep_flags= JOIN_TAB::CALL_POSITION | JOIN_TAB::KEEP_ROWID;
1140
JOIN_TAB *last_outer_tab= tab - 1;
1142
Walk through the range and remember
1143
- tables that need their rowids to be put into temptable
1144
- the last outer table
1146
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
1148
if (sj_table_is_included(join, tab))
1150
last_tab->join_tab= tab;
1151
last_tab->rowid_offset= jt_rowid_offset;
1152
jt_rowid_offset += tab->table->file->ref_length;
1153
if (tab->table->maybe_null)
1155
last_tab->null_byte= jt_null_bits / 8;
1156
last_tab->null_bit= jt_null_bits++;
1159
tab->table->prepare_for_position();
1160
tab->rowid_keep_flags= rowid_keep_flags;
1162
weed_cur_map |= tab->table->map;
1163
if (!tab->emb_sj_nest && bitmap_covers(weed_cur_map,
1164
dups_ranges[j].outer_tables))
1165
last_outer_tab= tab;
1168
if (jt_rowid_offset) /* Temptable has at least one rowid */
1170
SJ_TMP_TABLE *sjtbl;
1171
uint32_t tabs_size= (last_tab - sjtabs) * sizeof(SJ_TMP_TABLE::TAB);
1172
if (!(sjtbl= (SJ_TMP_TABLE*)session->alloc(sizeof(SJ_TMP_TABLE))) ||
1173
!(sjtbl->tabs= (SJ_TMP_TABLE::TAB*) session->alloc(tabs_size)))
1175
memcpy(sjtbl->tabs, sjtabs, tabs_size);
1176
sjtbl->tabs_end= sjtbl->tabs + (last_tab - sjtabs);
1177
sjtbl->rowid_len= jt_rowid_offset;
1178
sjtbl->null_bits= jt_null_bits;
1179
sjtbl->null_bytes= (jt_null_bits + 7)/8;
1181
*next_sjtbl_ptr= sjtbl;
1182
next_sjtbl_ptr= &(sjtbl->next);
1186
create_duplicate_weedout_tmp_table(session,
1191
join->join_tab[dups_ranges[j].start_idx].flush_weedout_table= sjtbl;
1192
join->join_tab[dups_ranges[j].end_idx - 1].check_weed_out_table= sjtbl;
1194
tab= last_outer_tab + 1;
1195
jump_to= last_outer_tab;
1198
/* Create the FirstMatch tail */
1199
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
1201
if (tab->emb_sj_nest)
1202
tab->do_firstmatch= jump_to;
1211
static void cleanup_sj_tmp_tables(JOIN *join)
1213
for (SJ_TMP_TABLE *sj_tbl= join->sj_tmp_tables; sj_tbl;
1214
sj_tbl= sj_tbl->next)
1216
if (sj_tbl->tmp_table)
1218
sj_tbl->tmp_table->free_tmp_table(join->session);
1221
join->sj_tmp_tables= NULL;
1224
uint32_t make_join_orderinfo(JOIN *join);
1227
global select optimisation.
1230
error code saved in field 'error'
1241
// to prevent double initialization on EXPLAIN
1246
session->set_proc_info("optimizing");
1247
row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
1248
unit->select_limit_cnt);
1249
/* select_limit is used to decide if we are likely to scan the whole table */
1250
select_limit= unit->select_limit_cnt;
1251
if (having || (select_options & OPTION_FOUND_ROWS))
1252
select_limit= HA_POS_ERROR;
1253
do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
1254
// Ignore errors of execution if option IGNORE present
1255
if (session->lex->ignore)
1256
session->lex->current_select->no_error= 1;
1258
#ifdef HAVE_REF_TO_FIELDS // Not done yet
1259
/* Add HAVING to WHERE if possible */
1260
if (having && !group_list && !sum_func_count)
1267
else if ((conds=new Item_cond_and(conds,having)))
1270
Item_cond_and can't be fixed after creation, so we do not check
1273
conds->fix_fields(session, &conds);
1274
conds->change_ref_to_fields(session, tables_list);
1275
conds->top_level_item();
1281
/* Convert all outer joins to inner joins if possible */
1282
conds= simplify_joins(this, join_list, conds, true, false);
1283
build_bitmap_for_nested_joins(join_list, 0);
1285
conds= optimize_cond(this, conds, join_list, &cond_value);
1286
if (session->is_error())
1293
having= optimize_cond(this, having, join_list, &having_value);
1294
if (session->is_error())
1299
if (select_lex->where)
1300
select_lex->cond_value= cond_value;
1301
if (select_lex->having)
1302
select_lex->having_value= having_value;
1304
if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
1305
(!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
1306
{ /* Impossible cond */
1307
zero_result_cause= having_value == Item::COND_FALSE ?
1308
"Impossible HAVING" : "Impossible WHERE";
1314
/* Optimize count(*), cmin() and cmax() */
1315
if (tables_list && tmp_table_param.sum_func_count && ! group_list)
1319
opt_sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
1320
to the WHERE conditions,
1321
or 1 if all items were resolved,
1322
or 0, or an error number HA_ERR_...
1324
if ((res=opt_sum_query(select_lex->leaf_tables, all_fields, conds)))
1326
if (res == HA_ERR_KEY_NOT_FOUND)
1328
zero_result_cause= "No matching min/max row";
1339
zero_result_cause= "No matching min/max row";
1343
zero_result_cause= "Select tables optimized away";
1344
tables_list= 0; // All tables resolved
1346
Extract all table-independent conditions and replace the WHERE
1347
clause with them. All other conditions were computed by opt_sum_query
1348
and the MIN/MAX/COUNT function(s) have been replaced by constants,
1349
so there is no need to compute the whole WHERE clause again.
1350
Notice that make_cond_for_table() will always succeed to remove all
1351
computed conditions, because opt_sum_query() is applicable only to
1353
Preserve conditions for EXPLAIN.
1355
if (conds && !(session->lex->describe & DESCRIBE_EXTENDED))
1357
COND *table_independent_conds=
1358
make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
1359
conds= table_independent_conds;
1368
error= -1; // Error is sent to client
1369
sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
1371
/* Calculate how to do the join */
1372
session->set_proc_info("statistics");
1373
if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
1374
session->is_fatal_error)
1379
/* Remove distinct if only const tables */
1380
select_distinct= select_distinct && (const_tables != tables);
1381
session->set_proc_info("preparing");
1382
if (result->initialize_tables(this))
1384
return(1); // error == -1
1386
if (const_table_map != found_const_table_map &&
1387
!(select_options & SELECT_DESCRIBE) &&
1389
!(conds->used_tables() & RAND_TABLE_BIT) ||
1390
select_lex->master_unit() == &session->lex->unit)) // upper level SELECT
1392
zero_result_cause= "no matching row in const table";
1396
if (!(session->options & OPTION_BIG_SELECTS) &&
1397
best_read > (double) session->variables.max_join_size &&
1398
!(select_options & SELECT_DESCRIBE))
1399
{ /* purecov: inspected */
1400
my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
1404
if (const_tables && !session->locked_tables &&
1405
!(select_options & SELECT_NO_UNLOCK))
1406
mysql_unlock_some_tables(session, table, const_tables);
1407
if (!conds && outer_join)
1409
/* Handle the case where we have an OUTER JOIN without a WHERE */
1410
conds=new Item_int((int64_t) 1,1); // Always true
1412
select= make_select(*table, const_table_map,
1413
const_table_map, conds, 1, &error);
1415
{ /* purecov: inspected */
1416
error= -1; /* purecov: inspected */
1420
reset_nj_counters(join_list);
1421
make_outerjoin_info(this);
1424
Among the equal fields belonging to the same multiple equality
1425
choose the one that is to be retrieved first and substitute
1426
all references to these in where condition for a reference for
1431
conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
1432
conds->update_used_tables();
1436
Permorm the the optimization on fields evaluation mentioned above
1437
for all on expressions.
1439
for (JOIN_TAB *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
1441
if (*tab->on_expr_ref)
1443
*tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
1446
(*tab->on_expr_ref)->update_used_tables();
1450
if (conds &&!outer_join && const_table_map != found_const_table_map &&
1451
(select_options & SELECT_DESCRIBE) &&
1452
select_lex->master_unit() == &session->lex->unit) // upper level SELECT
1454
conds=new Item_int((int64_t) 0,1); // Always false
1456
if (make_join_select(this, select, conds))
1459
"Impossible WHERE noticed after reading const tables";
1460
return(0); // error == 0
1463
error= -1; /* if goto err */
1465
/* Optimize distinct away if possible */
1467
order_st *org_order= order;
1468
order=remove_constants(this, order,conds,1, &simple_order);
1469
if (session->is_error())
1476
If we are using order_st BY NULL or order_st BY const_expression,
1477
return result in any order (even if we are using a GROUP BY)
1479
if (!order && org_order)
1483
Check if we can optimize away GROUP BY/DISTINCT.
1484
We can do that if there are no aggregate functions, the
1485
fields in DISTINCT clause (if present) and/or columns in GROUP BY
1486
(if present) contain direct references to all key parts of
1487
an unique index (in whatever order) and if the key parts of the
1488
unique index cannot contain NULLs.
1489
Note that the unique keys for DISTINCT and GROUP BY should not
1490
be the same (as long as they are unique).
1492
The FROM clause must contain a single non-constant table.
1494
if (tables - const_tables == 1 && (group_list || select_distinct) &&
1495
!tmp_table_param.sum_func_count &&
1496
(!join_tab[const_tables].select ||
1497
!join_tab[const_tables].select->quick ||
1498
join_tab[const_tables].select->quick->get_type() !=
1499
QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX))
1502
list_contains_unique_index(join_tab[const_tables].table,
1503
find_field_in_order_list,
1504
(void *) group_list))
1507
We have found that grouping can be removed since groups correspond to
1508
only one row anyway, but we still have to guarantee correct result
1509
order. The line below effectively rewrites the query from GROUP BY
1510
<fields> to order_st BY <fields>. There are two exceptions:
1511
- if skip_sort_order is set (see above), then we can simply skip
1513
- we can only rewrite order_st BY if the order_st BY fields are 'compatible'
1514
with the GROUP BY ones, i.e. either one is a prefix of another.
1515
We only check if the order_st BY is a prefix of GROUP BY. In this case
1516
test_if_subpart() copies the ASC/DESC attributes from the original
1518
If GROUP BY is a prefix of order_st BY, then it is safe to leave
1521
if (!order || test_if_subpart(group_list, order))
1522
order= skip_sort_order ? 0 : group_list;
1524
If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
1525
rewritten to IGNORE INDEX FOR order_st BY(fields).
1527
join_tab->table->keys_in_use_for_order_by=
1528
join_tab->table->keys_in_use_for_group_by;
1532
if (select_distinct &&
1533
list_contains_unique_index(join_tab[const_tables].table,
1534
find_field_in_item_list,
1535
(void *) &fields_list))
1540
if (group_list || tmp_table_param.sum_func_count)
1542
if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)
1545
else if (select_distinct && tables - const_tables == 1)
1548
We are only using one table. In this case we change DISTINCT to a
1550
- The GROUP BY can be done through indexes (no sort) and the order_st
1551
BY only uses selected fields.
1552
(In this case we can later optimize away GROUP BY and order_st BY)
1553
- We are scanning the whole table without LIMIT
1555
- We are using CALC_FOUND_ROWS
1556
- We are using an order_st BY that can't be optimized away.
1558
We don't want to use this optimization when we are using LIMIT
1559
because in this case we can just create a temporary table that
1560
holds LIMIT rows and stop when this table is full.
1562
JOIN_TAB *tab= &join_tab[const_tables];
1563
bool all_order_fields_used;
1565
skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
1566
&tab->table->keys_in_use_for_order_by);
1567
if ((group_list=create_distinct_group(session, select_lex->ref_pointer_array,
1568
order, fields_list, all_fields,
1569
&all_order_fields_used)))
1571
bool skip_group= (skip_sort_order &&
1572
test_if_skip_sort_order(tab, group_list, select_limit, 1,
1573
&tab->table->keys_in_use_for_group_by) != 0);
1574
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
1575
if ((skip_group && all_order_fields_used) ||
1576
select_limit == HA_POS_ERROR ||
1577
(order && !skip_sort_order))
1579
/* Change DISTINCT to GROUP BY */
1582
if (all_order_fields_used)
1584
if (order && skip_sort_order)
1587
Force MySQL to read the table in sorted order to get result in
1590
tmp_table_param.quick_group=0;
1594
group=1; // For end_write_group
1599
else if (session->is_fatal_error) // End of memory
1604
order_st *old_group_list;
1605
group_list= remove_constants(this, (old_group_list= group_list), conds,
1606
rollup.state == ROLLUP::STATE_NONE,
1608
if (session->is_error())
1613
if (old_group_list && !group_list)
1616
if (!group_list && group)
1618
order=0; // The output has only one row
1620
select_distinct= 0; // No need in distinct for 1 row
1621
group_optimized_away= 1;
1624
calc_group_buffer(this, group_list);
1625
send_group_parts= tmp_table_param.group_parts; /* Save org parts */
1627
if (test_if_subpart(group_list, order) ||
1628
(!group_list && tmp_table_param.sum_func_count))
1631
// Can't use sort on head table if using row cache
1641
Check if we need to create a temporary table.
1642
This has to be done if all tables are not already read (const tables)
1643
and one of the following conditions holds:
1644
- We are using DISTINCT (simple distinct's are already optimized away)
1645
- We are using an order_st BY or GROUP BY on fields not in the first table
1646
- We are using different order_st BY and GROUP BY orders
1647
- The user wants us to buffer the result.
1649
need_tmp= (const_tables != tables &&
1650
((select_distinct || !simple_order || !simple_group) ||
1651
(group_list && order) ||
1652
test(select_options & OPTION_BUFFER_RESULT)));
1654
uint32_t no_jbuf_after= make_join_orderinfo(this);
1655
uint64_t select_opts_for_readinfo=
1656
(select_options & (SELECT_DESCRIBE | SELECT_NO_JOIN_CACHE)) | (0);
1658
sj_tmp_tables= NULL;
1659
if (!select_lex->sj_nests.is_empty())
1660
setup_semijoin_dups_elimination(this, select_opts_for_readinfo,
1663
// No cache for MATCH == 'Don't use join buffering when we use MATCH'.
1664
if (make_join_readinfo(this, select_opts_for_readinfo, no_jbuf_after))
1667
/* Create all structures needed for materialized subquery execution. */
1668
if (setup_subquery_materialization())
1672
is this simple IN subquery?
1674
if (!group_list && !order &&
1675
unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
1676
tables == 1 && conds &&
1682
if (join_tab[0].type == JT_EQ_REF &&
1683
join_tab[0].ref.items[0]->name == in_left_expr_name)
1685
remove_subq_pushed_predicates(&where);
1686
save_index_subquery_explain_info(join_tab, where);
1687
join_tab[0].type= JT_UNIQUE_SUBQUERY;
1691
subselect_uniquesubquery_engine(session,
1696
else if (join_tab[0].type == JT_REF &&
1697
join_tab[0].ref.items[0]->name == in_left_expr_name)
1699
remove_subq_pushed_predicates(&where);
1700
save_index_subquery_explain_info(join_tab, where);
1701
join_tab[0].type= JT_INDEX_SUBQUERY;
1705
subselect_indexsubquery_engine(session,
1712
} else if (join_tab[0].type == JT_REF_OR_NULL &&
1713
join_tab[0].ref.items[0]->name == in_left_expr_name &&
1714
having->name == in_having_cond)
1716
join_tab[0].type= JT_INDEX_SUBQUERY;
1718
conds= remove_additional_cond(conds);
1719
save_index_subquery_explain_info(join_tab, conds);
1721
change_engine(new subselect_indexsubquery_engine(session,
1731
Need to tell handlers that to play it safe, it should fetch all
1732
columns of the primary key of the tables: this is because MySQL may
1733
build row pointers for the rows, and for all columns of the primary key
1734
the read set has not necessarily been set by the server code.
1736
if (need_tmp || select_distinct || group_list || order)
1738
for (uint32_t i = const_tables; i < tables; i++)
1739
join_tab[i].table->prepare_for_position();
1742
if (const_tables != tables)
1745
Because filesort always does a full table scan or a quick range scan
1746
we must add the removed reference to the select for the table.
1747
We only need to do this when we have a simple_order or simple_group
1748
as in other cases the join is done before the sort.
1750
if ((order || group_list) &&
1751
(join_tab[const_tables].type != JT_ALL) &&
1752
(join_tab[const_tables].type != JT_REF_OR_NULL) &&
1753
((order && simple_order) || (group_list && simple_group)))
1755
if (add_ref_to_table_cond(session,&join_tab[const_tables])) {
1760
if (!(select_options & SELECT_BIG_RESULT) &&
1763
!test_if_skip_sort_order(&join_tab[const_tables], group_list,
1764
unit->select_limit_cnt, 0,
1765
&join_tab[const_tables].table->
1766
keys_in_use_for_group_by))) ||
1768
tmp_table_param.quick_group)
1770
need_tmp=1; simple_order=simple_group=0; // Force tmp table without sort
1775
Force using of tmp table if sorting by a SP or UDF function due to
1776
their expensive and probably non-deterministic nature.
1778
for (order_st *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
1780
Item *item= *tmp_order->item;
1781
if (item->is_expensive())
1783
/* Force tmp table without sort */
1784
need_tmp=1; simple_order=simple_group=0;
1792
if (select_options & SELECT_DESCRIBE)
1800
The loose index scan access method guarantees that all grouping or
1801
duplicate row elimination (for distinct) is already performed
1802
during data retrieval, and that all MIN/MAX functions are already
1803
computed for each group. Thus all MIN/MAX functions should be
1804
treated as regular functions, and there is no need to perform
1805
grouping in the main execution loop.
1806
Notice that currently loose index scan is applicable only for
1807
single table queries, thus it is sufficient to test only the first
1808
join_tab element of the plan for its access method.
1810
if (join_tab->is_using_loose_index_scan())
1811
tmp_table_param.precomputed_group_by= true;
1813
/* Create a tmp table if distinct or if the sort is too complicated */
1816
session->set_proc_info("Creating tmp table");
1818
init_items_ref_array();
1820
tmp_table_param.hidden_field_count= (all_fields.elements -
1821
fields_list.elements);
1822
order_st *tmp_group= ((!simple_group && !(test_flags & TEST_NO_KEY_GROUP)) ? group_list :
1825
Pushing LIMIT to the temporary table creation is not applicable
1826
when there is order_st BY or GROUP BY or there is no GROUP BY, but
1827
there are aggregate functions, because in all these cases we need
1830
ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
1832
!session->lex->current_select->with_sum_func) ?
1833
select_limit : HA_POS_ERROR;
1835
if (!(exec_tmp_table1=
1836
create_tmp_table(session, &tmp_table_param, all_fields,
1838
group_list ? 0 : select_distinct,
1839
group_list && simple_group,
1848
We don't have to store rows in temp table that doesn't match HAVING if:
1849
- we are sorting the table and writing complete group rows to the
1851
- We are using DISTINCT without resolving the distinct as a GROUP BY
1854
If having is not handled here, it will be checked before the row
1855
is sent to the client.
1858
(sort_and_group || (exec_tmp_table1->distinct && !group_list)))
1861
/* if group or order on first table, sort first */
1862
if (group_list && simple_group)
1864
session->set_proc_info("Sorting for group");
1865
if (create_sort_index(session, this, group_list,
1866
HA_POS_ERROR, HA_POS_ERROR, false) ||
1867
alloc_group_fields(this, group_list) ||
1868
make_sum_func_list(all_fields, fields_list, 1) ||
1869
setup_sum_funcs(session, sum_funcs))
1877
if (make_sum_func_list(all_fields, fields_list, 0) ||
1878
setup_sum_funcs(session, sum_funcs))
1883
if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
1885
session->set_proc_info("Sorting for order");
1886
if (create_sort_index(session, this, order,
1887
HA_POS_ERROR, HA_POS_ERROR, true))
1896
Optimize distinct when used on some of the tables
1897
SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
1898
In this case we can stop scanning t2 when we have found one t1.a
1901
if (exec_tmp_table1->distinct)
1903
table_map used_tables= session->used_tables;
1904
JOIN_TAB *last_join_tab= join_tab+tables-1;
1907
if (used_tables & last_join_tab->table->map)
1909
last_join_tab->not_used_in_distinct=1;
1910
} while (last_join_tab-- != join_tab);
1911
/* Optimize "select distinct b from t1 order by key_part_1 limit #" */
1912
if (order && skip_sort_order)
1914
/* Should always succeed */
1915
if (test_if_skip_sort_order(&join_tab[const_tables],
1916
order, unit->select_limit_cnt, 0,
1917
&join_tab[const_tables].table->
1918
keys_in_use_for_order_by))
1924
If this join belongs to an uncacheable subquery save
1927
if (select_lex->uncacheable && !is_top_level_join() &&
1928
init_save_join_tab())
1929
return(-1); /* purecov: inspected */
1938
Restore values in temporary join.
1940
void JOIN::restore_tmp()
1942
memcpy(tmp_join, this, (size_t) sizeof(JOIN));
1949
unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1950
select_lex->offset_limit->val_uint() :
1955
if (exec_tmp_table1)
1957
exec_tmp_table1->file->extra(HA_EXTRA_RESET_STATE);
1958
exec_tmp_table1->file->ha_delete_all_rows();
1959
free_io_cache(exec_tmp_table1);
1960
filesort_free_buffers(exec_tmp_table1,0);
1962
if (exec_tmp_table2)
1964
exec_tmp_table2->file->extra(HA_EXTRA_RESET_STATE);
1965
exec_tmp_table2->file->ha_delete_all_rows();
1966
free_io_cache(exec_tmp_table2);
1967
filesort_free_buffers(exec_tmp_table2,0);
1970
set_items_ref_array(items0);
1973
memcpy(join_tab, join_tab_save, sizeof(JOIN_TAB) * tables);
1978
/* Reset of sum functions */
1981
Item_sum *func, **func_ptr= sum_funcs;
1982
while ((func= *(func_ptr++)))
1990
@brief Save the original join layout
1992
@details Saves the original join layout so it can be reused in
1993
re-execution and for EXPLAIN.
1995
@return Operation status
1997
@retval 1 error occurred.
2001
JOIN::init_save_join_tab()
2003
if (!(tmp_join= (JOIN*)session->alloc(sizeof(JOIN))))
2004
return 1; /* purecov: inspected */
2005
error= 0; // Ensure that tmp_join.error= 0
2012
JOIN::save_join_tab()
2014
if (!join_tab_save && select_lex->master_unit()->uncacheable)
2016
if (!(join_tab_save= (JOIN_TAB*)session->memdup((unsigned char*) join_tab,
2017
sizeof(JOIN_TAB) * tables)))
2028
Note, that create_sort_index calls test_if_skip_sort_order and may
2029
finally replace sorting with index scan if there is a LIMIT clause in
2030
the query. It's never shown in EXPLAIN!
2033
When can we have here session->net.report_error not zero?
2037
List<Item> *columns_list= &fields_list;
2040
session->set_proc_info("executing");
2043
if (!tables_list && (tables || !select_lex->with_sum_func))
2045
/* Only test of functions */
2046
if (select_options & SELECT_DESCRIBE)
2047
select_describe(this, false, false, false, (zero_result_cause?zero_result_cause:"No tables used"));
2050
result->send_fields(*columns_list, Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
2052
We have to test for 'conds' here as the WHERE may not be constant
2053
even if we don't have any tables for prepared statements or if
2054
conds uses something like 'rand()'.
2056
if (cond_value != Item::COND_FALSE &&
2057
(!conds || conds->val_int()) &&
2058
(!having || having->val_int()))
2060
if (do_send_rows && result->send_data(fields_list))
2064
error= (int) result->send_eof();
2065
send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 : session->sent_row_count);
2070
error= (int) result->send_eof();
2074
/* Single select (without union) always returns 0 or 1 row */
2075
session->limit_found_rows= send_records;
2076
session->examined_row_count= 0;
2080
Don't reset the found rows count if there're no tables as
2081
FOUND_ROWS() may be called. Never reset the examined row count here.
2082
It must be accumulated from all join iterations of all join parts.
2085
session->limit_found_rows= 0;
2087
if (zero_result_cause)
2089
(void) return_zero_rows(this, result, select_lex->leaf_tables,
2091
send_row_on_empty_set(),
2098
if ((this->select_lex->options & OPTION_SCHEMA_TABLE) && get_schema_tables_result(this, PROCESSED_BY_JOIN_EXEC))
2101
if (select_options & SELECT_DESCRIBE)
2104
Check if we managed to optimize order_st BY away and don't use temporary
2105
table to resolve order_st BY: in that case, we only may need to do
2106
filesort for GROUP BY.
2108
if (!order && !no_order && (!skip_sort_order || !need_tmp))
2110
/* Reset 'order' to 'group_list' and reinit variables describing 'order' */
2112
simple_order= simple_group;
2115
if (order && (order != group_list || !(select_options & SELECT_BIG_RESULT)))
2117
if (const_tables == tables
2118
|| ((simple_order || skip_sort_order)
2119
&& test_if_skip_sort_order(&join_tab[const_tables], order, select_limit, 0, &join_tab[const_tables].table->keys_in_use_for_query)))
2123
select_describe(this, need_tmp, order != 0 && !skip_sort_order, select_distinct, !tables ? "No tables used" : NULL);
2127
JOIN *curr_join= this;
2128
List<Item> *curr_all_fields= &all_fields;
2129
List<Item> *curr_fields_list= &fields_list;
2130
Table *curr_tmp_table= 0;
2132
Initialize examined rows here because the values from all join parts
2133
must be accumulated in examined_row_count. Hence every join
2134
iteration must count from zero.
2136
curr_join->examined_rows= 0;
2138
/* Create a tmp table if distinct or if the sort is too complicated */
2144
We are in a non cacheable sub query. Get the saved join structure
2146
(curr_join may have been modified during last exection and we need
2149
curr_join= tmp_join;
2151
curr_tmp_table= exec_tmp_table1;
2153
/* Copy data to the temporary table */
2154
session->set_proc_info("Copying to tmp table");
2155
if (! curr_join->sort_and_group && curr_join->const_tables != curr_join->tables)
2156
curr_join->join_tab[curr_join->const_tables].sorted= 0;
2157
if ((tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
2162
curr_tmp_table->file->info(HA_STATUS_VARIABLE);
2164
if (curr_join->having)
2165
curr_join->having= curr_join->tmp_having= 0; // Allready done
2167
/* Change sum_fields reference to calculated fields in tmp_table */
2168
curr_join->all_fields= *curr_all_fields;
2171
items1= items0 + all_fields.elements;
2172
if (sort_and_group || curr_tmp_table->group)
2174
if (change_to_use_tmp_fields(session, items1,
2175
tmp_fields_list1, tmp_all_fields1,
2176
fields_list.elements, all_fields))
2181
if (change_refs_to_tmp_fields(session, items1,
2182
tmp_fields_list1, tmp_all_fields1,
2183
fields_list.elements, all_fields))
2186
curr_join->tmp_all_fields1= tmp_all_fields1;
2187
curr_join->tmp_fields_list1= tmp_fields_list1;
2188
curr_join->items1= items1;
2190
curr_all_fields= &tmp_all_fields1;
2191
curr_fields_list= &tmp_fields_list1;
2192
curr_join->set_items_ref_array(items1);
2194
if (sort_and_group || curr_tmp_table->group)
2196
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count
2197
+ curr_join->tmp_table_param.func_count;
2198
curr_join->tmp_table_param.sum_func_count= 0;
2199
curr_join->tmp_table_param.func_count= 0;
2203
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.func_count;
2204
curr_join->tmp_table_param.func_count= 0;
2207
if (curr_tmp_table->group)
2208
{ // Already grouped
2209
if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
2210
curr_join->order= curr_join->group_list; /* order by group */
2211
curr_join->group_list= 0;
2215
If we have different sort & group then we must sort the data by group
2216
and copy it to another tmp table
2217
This code is also used if we are using distinct something
2218
we haven't been able to store in the temporary table yet
2219
like SEC_TO_TIME(SUM(...)).
2222
if ((curr_join->group_list && (!test_if_subpart(curr_join->group_list, curr_join->order) || curr_join->select_distinct))
2223
|| (curr_join->select_distinct && curr_join->tmp_table_param.using_indirect_summary_function))
2224
{ /* Must copy to another table */
2225
/* Free first data from old join */
2226
curr_join->join_free();
2227
if (make_simple_join(curr_join, curr_tmp_table))
2229
calc_group_buffer(curr_join, group_list);
2230
count_field_types(select_lex, &curr_join->tmp_table_param,
2231
curr_join->tmp_all_fields1,
2232
curr_join->select_distinct && !curr_join->group_list);
2233
curr_join->tmp_table_param.hidden_field_count= curr_join->tmp_all_fields1.elements
2234
- curr_join->tmp_fields_list1.elements;
2236
if (exec_tmp_table2)
2237
curr_tmp_table= exec_tmp_table2;
2240
/* group data to new table */
2243
If the access method is loose index scan then all MIN/MAX
2244
functions are precomputed, and should be treated as regular
2245
functions. See extended comment in JOIN::exec.
2247
if (curr_join->join_tab->is_using_loose_index_scan())
2248
curr_join->tmp_table_param.precomputed_group_by= true;
2250
if (!(curr_tmp_table=
2251
exec_tmp_table2= create_tmp_table(session,
2252
&curr_join->tmp_table_param,
2255
curr_join->select_distinct &&
2256
!curr_join->group_list,
2257
1, curr_join->select_options,
2261
curr_join->exec_tmp_table2= exec_tmp_table2;
2263
if (curr_join->group_list)
2265
session->set_proc_info("Creating sort index");
2266
if (curr_join->join_tab == join_tab && save_join_tab())
2270
if (create_sort_index(session, curr_join, curr_join->group_list,
2271
HA_POS_ERROR, HA_POS_ERROR, false) ||
2272
make_group_fields(this, curr_join))
2276
sortorder= curr_join->sortorder;
2279
session->set_proc_info("Copying to group table");
2281
if (curr_join != this)
2285
curr_join->sum_funcs= sum_funcs2;
2286
curr_join->sum_funcs_end= sum_funcs_end2;
2290
curr_join->alloc_func_list();
2291
sum_funcs2= curr_join->sum_funcs;
2292
sum_funcs_end2= curr_join->sum_funcs_end;
2295
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list, 1, true))
2297
curr_join->group_list= 0;
2299
if (!curr_join->sort_and_group && (curr_join->const_tables != curr_join->tables))
2300
curr_join->join_tab[curr_join->const_tables].sorted= 0;
2302
if (setup_sum_funcs(curr_join->session, curr_join->sum_funcs)
2303
|| (tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
2308
end_read_record(&curr_join->join_tab->read_record);
2309
curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
2310
curr_join->join_tab[0].table= 0; // Table is freed
2312
// No sum funcs anymore
2315
items2= items1 + all_fields.elements;
2316
if (change_to_use_tmp_fields(session, items2,
2317
tmp_fields_list2, tmp_all_fields2,
2318
fields_list.elements, tmp_all_fields1))
2320
curr_join->tmp_fields_list2= tmp_fields_list2;
2321
curr_join->tmp_all_fields2= tmp_all_fields2;
2323
curr_fields_list= &curr_join->tmp_fields_list2;
2324
curr_all_fields= &curr_join->tmp_all_fields2;
2325
curr_join->set_items_ref_array(items2);
2326
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count;
2327
curr_join->tmp_table_param.sum_func_count= 0;
2329
if (curr_tmp_table->distinct)
2330
curr_join->select_distinct=0; /* Each row is unique */
2332
curr_join->join_free(); /* Free quick selects */
2333
if (curr_join->select_distinct && ! curr_join->group_list)
2335
session->set_proc_info("Removing duplicates");
2336
if (curr_join->tmp_having)
2337
curr_join->tmp_having->update_used_tables();
2339
if (remove_duplicates(curr_join, curr_tmp_table,
2340
*curr_fields_list, curr_join->tmp_having))
2343
curr_join->tmp_having=0;
2344
curr_join->select_distinct=0;
2346
curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
2347
if (make_simple_join(curr_join, curr_tmp_table))
2349
calc_group_buffer(curr_join, curr_join->group_list);
2350
count_field_types(select_lex, &curr_join->tmp_table_param, *curr_all_fields, 0);
2354
if (curr_join->group || curr_join->tmp_table_param.sum_func_count)
2356
if (make_group_fields(this, curr_join))
2362
init_items_ref_array();
2363
items3= ref_pointer_array + (all_fields.elements*4);
2364
setup_copy_fields(session, &curr_join->tmp_table_param,
2365
items3, tmp_fields_list3, tmp_all_fields3,
2366
curr_fields_list->elements, *curr_all_fields);
2367
tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
2368
tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
2369
tmp_table_param.save_copy_field_end= curr_join->tmp_table_param.copy_field_end;
2370
curr_join->tmp_all_fields3= tmp_all_fields3;
2371
curr_join->tmp_fields_list3= tmp_fields_list3;
2375
curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
2376
curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
2377
curr_join->tmp_table_param.copy_field_end= tmp_table_param.save_copy_field_end;
2379
curr_fields_list= &tmp_fields_list3;
2380
curr_all_fields= &tmp_all_fields3;
2381
curr_join->set_items_ref_array(items3);
2383
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
2385
setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
2386
session->is_fatal_error)
2389
if (curr_join->group_list || curr_join->order)
2391
session->set_proc_info("Sorting result");
2392
/* If we have already done the group, add HAVING to sorted table */
2393
if (curr_join->tmp_having && ! curr_join->group_list && ! curr_join->sort_and_group)
2395
// Some tables may have been const
2396
curr_join->tmp_having->update_used_tables();
2397
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables];
2398
table_map used_tables= (curr_join->const_table_map |
2399
curr_table->table->map);
2401
Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having, used_tables, used_tables, 0);
2402
if (sort_table_cond)
2404
if (!curr_table->select)
2405
if (!(curr_table->select= new SQL_SELECT))
2407
if (!curr_table->select->cond)
2408
curr_table->select->cond= sort_table_cond;
2409
else // This should never happen
2411
if (!(curr_table->select->cond=
2412
new Item_cond_and(curr_table->select->cond,
2416
Item_cond_and do not need fix_fields for execution, its parameters
2417
are fixed or do not need fix_fields, too
2419
curr_table->select->cond->quick_fix_field();
2421
curr_table->select_cond= curr_table->select->cond;
2422
curr_table->select_cond->top_level_item();
2423
curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
2430
curr_join->select_limit= HA_POS_ERROR;
2434
We can abort sorting after session->select_limit rows if we there is no
2435
WHERE clause for any tables after the sorted one.
2437
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
2438
JOIN_TAB *end_table= &curr_join->join_tab[curr_join->tables];
2439
for (; curr_table < end_table ; curr_table++)
2442
table->keyuse is set in the case there was an original WHERE clause
2443
on the table that was optimized away.
2445
if (curr_table->select_cond ||
2446
(curr_table->keyuse && !curr_table->first_inner))
2448
/* We have to sort all rows */
2449
curr_join->select_limit= HA_POS_ERROR;
2454
if (curr_join->join_tab == join_tab && save_join_tab())
2457
Here we sort rows for order_st BY/GROUP BY clause, if the optimiser
2458
chose FILESORT to be faster than INDEX SCAN or there is no
2459
suitable index present.
2460
Note, that create_sort_index calls test_if_skip_sort_order and may
2461
finally replace sorting with index scan if there is a LIMIT clause in
2462
the query. XXX: it's never shown in EXPLAIN!
2463
OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
2465
if (create_sort_index(session, curr_join,
2466
curr_join->group_list ?
2467
curr_join->group_list : curr_join->order,
2468
curr_join->select_limit,
2469
(select_options & OPTION_FOUND_ROWS ?
2470
HA_POS_ERROR : unit->select_limit_cnt),
2471
curr_join->group_list ? true : false))
2474
sortorder= curr_join->sortorder;
2475
if (curr_join->const_tables != curr_join->tables &&
2476
!curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
2479
If no IO cache exists for the first table then we are using an
2480
INDEX SCAN and no filesort. Thus we should not remove the sorted
2481
attribute on the INDEX SCAN.
2487
/* XXX: When can we have here session->is_error() not zero? */
2488
if (session->is_error())
2490
error= session->is_error();
2493
curr_join->having= curr_join->tmp_having;
2494
curr_join->fields= curr_fields_list;
2496
session->set_proc_info("Sending data");
2497
result->send_fields(*curr_fields_list,
2498
Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
2499
error= do_select(curr_join, curr_fields_list, NULL);
2500
session->limit_found_rows= curr_join->send_records;
2502
/* Accumulate the counts from all join iterations of all join parts. */
2503
session->examined_row_count+= curr_join->examined_rows;
2506
With EXPLAIN EXTENDED we have to restore original ref_array
2507
for a derived table which is always materialized.
2508
Otherwise we would not be able to print the query correctly.
2510
if (items0 && (session->lex->describe & DESCRIBE_EXTENDED) && select_lex->linkage == DERIVED_TABLE_TYPE)
2511
set_items_ref_array(items0);
2520
Return error that hold JOIN.
2524
select_lex->join= 0;
2528
if (join_tab != tmp_join->join_tab)
2530
JOIN_TAB *tab, *end;
2531
for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
2534
tmp_join->tmp_join= 0;
2535
tmp_table_param.copy_field=0;
2536
return(tmp_join->destroy());
2541
if (exec_tmp_table1)
2542
exec_tmp_table1->free_tmp_table(session);
2543
if (exec_tmp_table2)
2544
exec_tmp_table2->free_tmp_table(session);
2546
delete_dynamic(&keyuse);
306
2551
An entry point to single-unit select (a select without UNION).
308
@param session thread Cursor
2553
@param session thread handler
309
2554
@param rref_pointer_array a reference to ref_pointer_array of
310
2555
the top-level select_lex for this query
311
2556
@param tables list of all tables used in this query.
2730
Convert a subquery predicate into a TableList semi-join nest
2733
convert_subq_to_sj()
2734
parent_join Parent join, the one that has subq_pred in its WHERE/ON
2736
subq_pred Subquery predicate to be converted
2739
Convert a subquery predicate into a TableList semi-join nest. All the
2740
prerequisites are already checked, so the conversion is always successfull.
2742
Prepared Statements: the transformation is permanent:
2743
- Changes in TableList structures are naturally permanent
2744
- Item tree changes are performed on statement MEM_ROOT:
2745
= we activate statement MEM_ROOT
2746
= this function is called before the first fix_prepare_information
2749
This is intended because the criteria for subquery-to-sj conversion remain
2750
constant for the lifetime of the Prepared Statement.
2754
true Out of memory error
2757
bool convert_subq_to_sj(JOIN *parent_join, Item_in_subselect *subq_pred)
2759
Select_Lex *parent_lex= parent_join->select_lex;
2760
TableList *emb_tbl_nest= NULL;
2761
List<TableList> *emb_join_list= &parent_lex->top_join_list;
2762
Session *session= parent_join->session;
2765
1. Find out where to put the predicate into.
2766
Note: for "t1 LEFT JOIN t2" this will be t2, a leaf.
2768
if ((void*)subq_pred->expr_join_nest != (void*)1)
2770
if (subq_pred->expr_join_nest->nested_join)
2775
... [LEFT] JOIN ( ... ) ON (subquery AND whatever) ...
2777
The sj-nest will be inserted into the brackets nest.
2779
emb_tbl_nest= subq_pred->expr_join_nest;
2780
emb_join_list= &emb_tbl_nest->nested_join->join_list;
2782
else if (!subq_pred->expr_join_nest->outer_join)
2787
... INNER JOIN tblX ON (subquery AND whatever) ...
2789
The sj-nest will be tblX's "sibling", i.e. another child of its
2790
parent. This is ok because tblX is joined as an inner join.
2792
emb_tbl_nest= subq_pred->expr_join_nest->embedding;
2794
emb_join_list= &emb_tbl_nest->nested_join->join_list;
2796
else if (!subq_pred->expr_join_nest->nested_join)
2798
TableList *outer_tbl= subq_pred->expr_join_nest;
2799
TableList *wrap_nest;
2803
... LEFT JOIN tbl ON (on_expr AND subq_pred) ...
2805
we'll need to convert it into:
2807
... LEFT JOIN ( tbl SJ (subq_tables) ) ON (on_expr AND subq_pred) ...
2809
|<----- wrap_nest ---->|
2811
Q: other subqueries may be pointing to this element. What to do?
2812
A1: simple solution: copy *subq_pred->expr_join_nest= *parent_nest.
2813
But we'll need to fix other pointers.
2814
A2: Another way: have TableList::next_ptr so the following
2815
subqueries know the table has been nested.
2816
A3: changes in the TableList::outer_join will make everything work
2819
if (!(wrap_nest= alloc_join_nest(parent_join->session)))
2823
wrap_nest->embedding= outer_tbl->embedding;
2824
wrap_nest->join_list= outer_tbl->join_list;
2825
wrap_nest->alias= (char*) "(sj-wrap)";
2827
wrap_nest->nested_join->join_list.empty();
2828
wrap_nest->nested_join->join_list.push_back(outer_tbl);
2830
outer_tbl->embedding= wrap_nest;
2831
outer_tbl->join_list= &wrap_nest->nested_join->join_list;
2834
wrap_nest will take place of outer_tbl, so move the outer join flag
2837
wrap_nest->outer_join= outer_tbl->outer_join;
2838
outer_tbl->outer_join= 0;
2840
wrap_nest->on_expr= outer_tbl->on_expr;
2841
outer_tbl->on_expr= NULL;
2843
List_iterator<TableList> li(*wrap_nest->join_list);
2847
if (tbl == outer_tbl)
2849
li.replace(wrap_nest);
2854
Ok now wrap_nest 'contains' outer_tbl and we're ready to add the
2855
semi-join nest into it
2857
emb_join_list= &wrap_nest->nested_join->join_list;
2858
emb_tbl_nest= wrap_nest;
2863
nested_join_st *nested_join;
2864
if (!(sj_nest= alloc_join_nest(parent_join->session)))
2868
nested_join= sj_nest->nested_join;
2870
sj_nest->join_list= emb_join_list;
2871
sj_nest->embedding= emb_tbl_nest;
2872
sj_nest->alias= (char*) "(sj-nest)";
2873
/* Nests do not participate in those 'chains', so: */
2874
/* sj_nest->next_leaf= sj_nest->next_local= sj_nest->next_global == NULL*/
2875
emb_join_list->push_back(sj_nest);
2878
nested_join->used_tables and nested_join->not_null_tables are
2879
initialized in simplify_joins().
2883
2. Walk through subquery's top list and set 'embedding' to point to the
2886
Select_Lex *subq_lex= subq_pred->unit->first_select();
2887
nested_join->join_list.empty();
2888
List_iterator_fast<TableList> li(subq_lex->top_join_list);
2889
TableList *tl, *last_leaf;
2892
tl->embedding= sj_nest;
2893
tl->join_list= &nested_join->join_list;
2894
nested_join->join_list.push_back(tl);
2898
Reconnect the next_leaf chain.
2899
TODO: Do we have to put subquery's tables at the end of the chain?
2900
Inserting them at the beginning would be a bit faster.
2901
NOTE: We actually insert them at the front! That's because the order is
2902
reversed in this list.
2904
for (tl= parent_lex->leaf_tables; tl->next_leaf; tl= tl->next_leaf) {};
2905
tl->next_leaf= subq_lex->leaf_tables;
2909
Same as above for next_local chain
2910
(a theory: a next_local chain always starts with ::leaf_tables
2911
because view's tables are inserted after the view)
2913
for (tl= parent_lex->leaf_tables; tl->next_local; tl= tl->next_local) {};
2914
tl->next_local= subq_lex->leaf_tables;
2916
/* A theory: no need to re-connect the next_global chain */
2918
/* 3. Remove the original subquery predicate from the WHERE/ON */
2920
// The subqueries were replaced for Item_int(1) earlier
2921
subq_pred->exec_method= Item_in_subselect::SEMI_JOIN; // for subsequent executions
2922
/*TODO: also reset the 'with_subselect' there. */
2924
/* n. Adjust the parent_join->tables counter */
2925
uint32_t table_no= parent_join->tables;
2926
/* n. Walk through child's tables and adjust table->map */
2927
for (tl= subq_lex->leaf_tables; tl; tl= tl->next_leaf, table_no++)
2929
tl->table->tablenr= table_no;
2930
tl->table->map= ((table_map)1) << table_no;
2931
Select_Lex *old_sl= tl->select_lex;
2932
tl->select_lex= parent_join->select_lex;
2933
for(TableList *emb= tl->embedding; emb && emb->select_lex == old_sl; emb= emb->embedding)
2934
emb->select_lex= parent_join->select_lex;
2936
parent_join->tables += subq_lex->join->tables;
2939
Put the subquery's WHERE into semi-join's sj_on_expr
2940
Add the subquery-induced equalities too.
2942
Select_Lex *save_lex= session->lex->current_select;
2943
session->lex->current_select=subq_lex;
2944
if (!subq_pred->left_expr->fixed &&
2945
subq_pred->left_expr->fix_fields(session, &subq_pred->left_expr))
2947
session->lex->current_select=save_lex;
2949
sj_nest->nested_join->sj_corr_tables= subq_pred->used_tables();
2950
sj_nest->nested_join->sj_depends_on= subq_pred->used_tables() |
2951
subq_pred->left_expr->used_tables();
2952
sj_nest->sj_on_expr= subq_lex->where;
2955
Create the IN-equalities and inject them into semi-join's ON expression.
2956
Additionally, for InsideOut strategy
2957
- Record the number of IN-equalities.
2958
- Create list of pointers to (oe1, ..., ieN). We'll need the list to
2959
see which of the expressions are bound and which are not (for those
2960
we'll produce a distinct stream of (ie_i1,...ie_ik).
2962
(TODO: can we just create a list of pointers and hope the expressions
2963
will not substitute themselves on fix_fields()? or we need to wrap
2964
them into Item_direct_view_refs and store pointers to those. The
2965
pointers to Item_direct_view_refs are guaranteed to be stable as
2966
Item_direct_view_refs doesn't substitute itself with anything in
2967
Item_direct_view_ref::fix_fields.
2969
sj_nest->sj_in_exprs= subq_pred->left_expr->cols();
2970
sj_nest->nested_join->sj_outer_expr_list.empty();
2972
if (subq_pred->left_expr->cols() == 1)
2974
nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr);
2976
Item *item_eq= new Item_func_eq(subq_pred->left_expr,
2977
subq_lex->ref_pointer_array[0]);
2978
item_eq->name= (char*)subq_sj_cond_name;
2979
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
2983
for (uint32_t i= 0; i < subq_pred->left_expr->cols(); i++)
2985
nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr->
2988
new Item_func_eq(subq_pred->left_expr->element_index(i),
2989
subq_lex->ref_pointer_array[i]);
2990
item_eq->name= (char*)subq_sj_cond_name + (i % 64);
2991
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
2994
/* Fix the created equality and AND */
2995
sj_nest->sj_on_expr->fix_fields(parent_join->session, &sj_nest->sj_on_expr);
2998
Walk through sj nest's WHERE and ON expressions and call
2999
item->fix_table_changes() for all items.
3001
sj_nest->sj_on_expr->fix_after_pullout(parent_lex, &sj_nest->sj_on_expr);
3002
fix_list_after_tbl_changes(parent_lex, &sj_nest->nested_join->join_list);
3005
/* Unlink the child select_lex so it doesn't show up in EXPLAIN: */
3006
subq_lex->master_unit()->exclude_level();
3008
/* Inject sj_on_expr into the parent's WHERE or ON */
3011
emb_tbl_nest->on_expr= and_items(emb_tbl_nest->on_expr,
3012
sj_nest->sj_on_expr);
3013
emb_tbl_nest->on_expr->fix_fields(parent_join->session, &emb_tbl_nest->on_expr);
3017
/* Inject into the WHERE */
3018
parent_join->conds= and_items(parent_join->conds, sj_nest->sj_on_expr);
3019
parent_join->conds->fix_fields(parent_join->session, &parent_join->conds);
3020
parent_join->select_lex->where= parent_join->conds;
3028
Convert candidate subquery predicates to semi-joins
3031
JOIN::flatten_subqueries()
3034
Convert candidate subquery predicates to semi-joins.
3041
bool JOIN::flatten_subqueries()
3043
Item_in_subselect **in_subq;
3044
Item_in_subselect **in_subq_end;
3046
if (sj_subselects.elements() == 0)
3049
/* 1. Fix children subqueries */
3050
for (in_subq= sj_subselects.front(), in_subq_end= sj_subselects.back();
3051
in_subq != in_subq_end; in_subq++)
3053
JOIN *child_join= (*in_subq)->unit->first_select()->join;
3054
child_join->outer_tables = child_join->tables;
3055
if (child_join->flatten_subqueries())
3057
(*in_subq)->sj_convert_priority=
3058
(*in_subq)->is_correlated * MAX_TABLES + child_join->outer_tables;
3061
bool outer_join_disable_semi_join= false;
3063
* Temporary measure: disable semi-joins when they are together with outer
3066
* @see LP Bug #314911
3068
for (TableList *tbl= select_lex->leaf_tables; tbl; tbl=tbl->next_leaf)
3070
TableList *embedding= tbl->embedding;
3071
if (tbl->on_expr || (tbl->embedding && !(embedding->sj_on_expr &&
3072
!embedding->embedding)))
3074
in_subq= sj_subselects.front();
3075
outer_join_disable_semi_join= true;
3079
if (! outer_join_disable_semi_join)
3082
2. Pick which subqueries to convert:
3083
sort the subquery array
3084
- prefer correlated subqueries over uncorrelated;
3085
- prefer subqueries that have greater number of outer tables;
3087
sj_subselects.sort(subq_sj_candidate_cmp);
3088
// #tables-in-parent-query + #tables-in-subquery < MAX_TABLES
3089
/* Replace all subqueries to be flattened with Item_int(1) */
3090
for (in_subq= sj_subselects.front();
3091
in_subq != in_subq_end &&
3092
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
3095
if (replace_where_subcondition(this, *in_subq, new Item_int(1), false))
3099
for (in_subq= sj_subselects.front();
3100
in_subq != in_subq_end &&
3101
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
3104
if (convert_subq_to_sj(this, *in_subq))
3109
/* 3. Finalize those we didn't convert */
3110
for (; in_subq!= in_subq_end; in_subq++)
3112
JOIN *child_join= (*in_subq)->unit->first_select()->join;
3113
Item_subselect::trans_res res;
3114
(*in_subq)->changed= 0;
3115
(*in_subq)->fixed= 0;
3116
res= (*in_subq)->select_transformer(child_join);
3117
if (res == Item_subselect::RES_ERROR)
3120
(*in_subq)->changed= 1;
3121
(*in_subq)->fixed= 1;
3123
Item *substitute= (*in_subq)->substitution;
3124
bool do_fix_fields= !(*in_subq)->substitution->fixed;
3125
if (replace_where_subcondition(this, *in_subq, substitute, do_fix_fields))
3128
//if ((*in_subq)->fix_fields(session, (*in_subq)->ref_ptr))
3131
sj_subselects.clear();
3136
Setup for execution all subqueries of a query, for which the optimizer
3137
chose hash semi-join.
3139
@details Iterate over all subqueries of the query, and if they are under an
3140
IN predicate, and the optimizer chose to compute it via hash semi-join:
3141
- try to initialize all data structures needed for the materialized execution
3142
of the IN predicate,
3143
- if this fails, then perform the IN=>EXISTS transformation which was
3144
previously blocked during JOIN::prepare.
3146
This method is part of the "code generation" query processing phase.
3148
This phase must be called after substitute_for_best_equal_field() because
3149
that function may replace items with other items from a multiple equality,
3150
and we need to reference the correct items in the index access method of the
3153
@return Operation status
3154
@retval false success.
3155
@retval true error occurred.
3157
bool JOIN::setup_subquery_materialization()
3159
for (Select_Lex_Unit *un= select_lex->first_inner_unit(); un;
3160
un= un->next_unit())
3162
for (Select_Lex *sl= un->first_select(); sl; sl= sl->next_select())
3164
Item_subselect *subquery_predicate= sl->master_unit()->item;
3165
if (subquery_predicate &&
3166
subquery_predicate->substype() == Item_subselect::IN_SUBS)
3168
Item_in_subselect *in_subs= (Item_in_subselect*) subquery_predicate;
3169
if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION &&
3170
in_subs->setup_engine())
3180
Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
3183
find_eq_ref_candidate()
3184
table Table to be checked
3185
sj_inner_tables Bitmap of inner tables. eq_ref(inner_table) doesn't
3189
Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
3192
Check again if it is feasible to factor common parts with constant table
3196
true - There exists an eq_ref(outer-tables) candidate
3200
bool find_eq_ref_candidate(Table *table, table_map sj_inner_tables)
3202
KEYUSE *keyuse= table->reginfo.join_tab->keyuse;
3207
while (1) /* For each key */
3210
KEY *keyinfo= table->key_info + key;
3211
key_part_map bound_parts= 0;
3212
if ((keyinfo->flags & HA_NOSAME) == HA_NOSAME)
3214
do /* For all equalities on all key parts */
3216
/* Check if this is "t.keypart = expr(outer_tables) */
3217
if (!(keyuse->used_tables & sj_inner_tables) &&
3218
!(keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL))
3220
bound_parts |= 1 << keyuse->keypart;
3223
} while (keyuse->key == key && keyuse->table == table);
3225
if (bound_parts == PREV_BITS(uint, keyinfo->key_parts))
3227
if (keyuse->table != table)
3235
if (keyuse->table != table)
3238
while (keyuse->key == key);
3247
Pull tables out of semi-join nests, if possible
3250
pull_out_semijoin_tables()
3251
join The join where to do the semi-join flattening
3254
Try to pull tables out of semi-join nests.
3257
When this function is called, the join may have several semi-join nests
3258
(possibly within different semi-join nests), but it is guaranteed that
3259
one semi-join nest does not contain another.
3262
A table can be pulled out of the semi-join nest if
3263
- It is a constant table
3267
* Pulled out tables have JOIN_TAB::emb_sj_nest == NULL (like the outer
3269
* Tables that were not pulled out have JOIN_TAB::emb_sj_nest.
3270
* Semi-join nests TableList::sj_inner_tables
3272
This operation is (and should be) performed at each PS execution since
3273
tables may become/cease to be constant across PS reexecutions.
3277
1 - Out of memory error
3280
int pull_out_semijoin_tables(JOIN *join)
3283
List_iterator<TableList> sj_list_it(join->select_lex->sj_nests);
3285
/* Try pulling out of the each of the semi-joins */
3286
while ((sj_nest= sj_list_it++))
3288
/* Action #1: Mark the constant tables to be pulled out */
3289
table_map pulled_tables= 0;
3291
List_iterator<TableList> child_li(sj_nest->nested_join->join_list);
3293
while ((tbl= child_li++))
3297
tbl->table->reginfo.join_tab->emb_sj_nest= sj_nest;
3298
if (tbl->table->map & join->const_table_map)
3300
pulled_tables |= tbl->table->map;
3306
Action #2: Find which tables we can pull out based on
3307
update_ref_and_keys() data. Note that pulling one table out can allow
3308
us to pull out some other tables too.
3310
bool pulled_a_table;
3313
pulled_a_table= false;
3315
while ((tbl= child_li++))
3317
if (tbl->table && !(pulled_tables & tbl->table->map))
3319
if (find_eq_ref_candidate(tbl->table,
3320
sj_nest->nested_join->used_tables &
3323
pulled_a_table= true;
3324
pulled_tables |= tbl->table->map;
3328
} while (pulled_a_table);
3331
if ((sj_nest)->nested_join->used_tables == pulled_tables)
3333
(sj_nest)->sj_inner_tables= 0;
3334
while ((tbl= child_li++))
3337
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
3342
/* Record the bitmap of inner tables, mark the inner tables */
3343
table_map inner_tables=(sj_nest)->nested_join->used_tables &
3345
(sj_nest)->sj_inner_tables= inner_tables;
3346
while ((tbl= child_li++))
3350
if (inner_tables & tbl->table->map)
3351
tbl->table->reginfo.join_tab->emb_sj_nest= (sj_nest);
3353
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
462
3361
/*****************************************************************************
463
Create JoinTableS, make a guess about the table types,
3362
Create JOIN_TABS, make a guess about the table types,
464
3363
Approximate how many records will be used in each table
465
3364
*****************************************************************************/
466
ha_rows get_quick_record_count(Session *session, optimizer::SqlSelect *select, Table *table, const key_map *keys,ha_rows limit)
3367
static ha_rows get_quick_record_count(Session *session, SQL_SELECT *select,
3369
const key_map *keys,ha_rows limit)
469
3372
if (check_stack_overrun(session, STACK_MIN_SIZE, NULL))
484
3387
return(HA_POS_ERROR); /* This shouldn't happend */
3391
This structure is used to collect info on potentially sargable
3392
predicates in order to check whether they become sargable after
3393
reading const tables.
3394
We form a bitmap of indexes that can be used for sargable predicates.
3395
Only such indexes are involved in range analysis.
3397
typedef struct st_sargable_param
3399
Field *field; /* field against which to check sargability */
3400
Item **arg_value; /* values of potential keys for lookups */
3401
uint32_t num_values; /* number of values in the above array */
3405
Calculate the best possible join and initialize the join structure.
3414
make_join_statistics(JOIN *join, TableList *tables, COND *conds,
3415
DYNAMIC_ARRAY *keyuse_array)
3419
uint32_t i,table_count,const_count,key;
3420
table_map found_const_table_map, all_table_map, found_ref, refs;
3421
key_map const_ref, eq_part;
3422
Table **table_vector;
3423
JOIN_TAB *stat,*stat_end,*s,**stat_ref;
3424
KEYUSE *keyuse,*start_keyuse;
3425
table_map outer_join=0;
3426
SARGABLE_PARAM *sargables= 0;
3427
JOIN_TAB *stat_vector[MAX_TABLES+1];
3429
table_count=join->tables;
3430
stat=(JOIN_TAB*) join->session->calloc(sizeof(JOIN_TAB)*table_count);
3431
stat_ref=(JOIN_TAB**) join->session->alloc(sizeof(JOIN_TAB*)*MAX_TABLES);
3432
table_vector=(Table**) join->session->alloc(sizeof(Table*)*(table_count*2));
3433
if (!stat || !stat_ref || !table_vector)
3434
return(1); // Eom /* purecov: inspected */
3436
join->best_ref=stat_vector;
3438
stat_end=stat+table_count;
3439
found_const_table_map= all_table_map=0;
3444
s++, tables= tables->next_leaf, i++)
3446
TableList *embedding= tables->embedding;
3449
s->const_keys.init();
3450
s->checked_keys.init();
3451
s->needed_reg.init();
3452
table_vector[i]=s->table=table=tables->table;
3453
table->pos_in_table_list= tables;
3454
error= table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
3457
table->file->print_error(error, MYF(0));
3460
table->quick_keys.clear_all();
3461
table->reginfo.join_tab=s;
3462
table->reginfo.not_exists_optimize=0;
3463
memset(table->const_key_parts, 0,
3464
sizeof(key_part_map)*table->s->keys);
3465
all_table_map|= table->map;
3467
s->info=0; // For describe
3469
s->dependent= tables->dep_tables;
3470
s->key_dependent= 0;
3471
if (tables->schema_table)
3472
table->file->stats.records= 2;
3473
table->quick_condition_rows= table->file->stats.records;
3475
s->on_expr_ref= &tables->on_expr;
3476
if (*s->on_expr_ref)
3478
/* s is the only inner table of an outer join */
3479
if (!table->file->stats.records && !embedding)
3481
s->dependent= 0; // Ignore LEFT JOIN depend.
3482
set_position(join,const_count++,s,(KEYUSE*) 0);
3485
outer_join|= table->map;
3486
s->embedding_map= 0;
3487
for (;embedding; embedding= embedding->embedding)
3488
s->embedding_map|= embedding->nested_join->nj_map;
3491
if (embedding && !(embedding->sj_on_expr && ! embedding->embedding))
3493
/* s belongs to a nested join, maybe to several embedded joins */
3494
s->embedding_map= 0;
3497
nested_join_st *nested_join= embedding->nested_join;
3498
s->embedding_map|=nested_join->nj_map;
3499
s->dependent|= embedding->dep_tables;
3500
embedding= embedding->embedding;
3501
outer_join|= nested_join->used_tables;
3506
if ((table->file->stats.records <= 1) &&
3508
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) && !join->no_const_tables)
3510
set_position(join,const_count++,s,(KEYUSE*) 0);
3514
join->outer_join=outer_join;
3516
if (join->outer_join)
3519
Build transitive closure for relation 'to be dependent on'.
3520
This will speed up the plan search for many cases with outer joins,
3521
as well as allow us to catch illegal cross references/
3522
Warshall's algorithm is used to build the transitive closure.
3523
As we use bitmaps to represent the relation the complexity
3524
of the algorithm is O((number of tables)^2).
3526
for (i= 0, s= stat ; i < table_count ; i++, s++)
3528
for (uint32_t j= 0 ; j < table_count ; j++)
3530
table= stat[j].table;
3531
if (s->dependent & table->map)
3532
s->dependent |= table->reginfo.join_tab->dependent;
3535
s->table->maybe_null= 1;
3537
/* Catch illegal cross references for outer joins */
3538
for (i= 0, s= stat ; i < table_count ; i++, s++)
3540
if (s->dependent & s->table->map)
3542
join->tables=0; // Don't use join->table
3543
my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
3546
s->key_dependent= s->dependent;
3550
if (conds || outer_join)
3551
if (update_ref_and_keys(join->session, keyuse_array, stat, join->tables,
3552
conds, join->cond_equal,
3553
~outer_join, join->select_lex, &sargables))
3556
/* Read tables with 0 or 1 rows (system tables) */
3557
join->const_table_map= 0;
3559
for (POSITION *p_pos=join->positions, *p_end=p_pos+const_count;
3566
join->const_table_map|=s->table->map;
3567
if ((tmp=join_read_const_table(s, p_pos)))
3570
return(1); // Fatal error
3573
found_const_table_map|= s->table->map;
3576
/* loop until no more const tables are found */
3580
more_const_tables_found:
3585
We only have to loop from stat_vector + const_count as
3586
set_position() will move all const_tables first in stat_vector
3589
for (JOIN_TAB **pos=stat_vector+const_count ; (s= *pos) ; pos++)
3594
If equi-join condition by a key is null rejecting and after a
3595
substitution of a const table the key value happens to be null
3596
then we can state that there are no matches for this equi-join.
3598
if ((keyuse= s->keyuse) && *s->on_expr_ref && !s->embedding_map)
3601
When performing an outer join operation if there are no matching rows
3602
for the single row of the outer table all the inner tables are to be
3603
null complemented and thus considered as constant tables.
3604
Here we apply this consideration to the case of outer join operations
3605
with a single inner table only because the case with nested tables
3606
would require a more thorough analysis.
3607
TODO. Apply single row substitution to null complemented inner tables
3608
for nested outer join operations.
3610
while (keyuse->table == table)
3612
if (!(keyuse->val->used_tables() & ~join->const_table_map) &&
3613
keyuse->val->is_null() && keyuse->null_rejecting)
3616
table->mark_as_null_row();
3617
found_const_table_map|= table->map;
3618
join->const_table_map|= table->map;
3619
set_position(join,const_count++,s,(KEYUSE*) 0);
3620
goto more_const_tables_found;
3626
if (s->dependent) // If dependent on some table
3628
// All dep. must be constants
3629
if (s->dependent & ~(found_const_table_map))
3631
if (table->file->stats.records <= 1L &&
3632
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
3633
!table->pos_in_table_list->embedding)
3637
join->const_table_map|=table->map;
3638
set_position(join,const_count++,s,(KEYUSE*) 0);
3639
if ((tmp= join_read_const_table(s, join->positions+const_count-1)))
3642
return(1); // Fatal error
3645
found_const_table_map|= table->map;
3649
/* check if table can be read by key or table only uses const refs */
3650
if ((keyuse=s->keyuse))
3653
while (keyuse->table == table)
3655
start_keyuse=keyuse;
3657
s->keys.set_bit(key); // QQ: remove this ?
3660
const_ref.clear_all();
3661
eq_part.clear_all();
3664
if (keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize)
3666
if (!((~found_const_table_map) & keyuse->used_tables))
3667
const_ref.set_bit(keyuse->keypart);
3669
refs|=keyuse->used_tables;
3670
eq_part.set_bit(keyuse->keypart);
3673
} while (keyuse->table == table && keyuse->key == key);
3675
if (eq_part.is_prefix(table->key_info[key].key_parts) &&
3676
!table->pos_in_table_list->embedding)
3678
if ((table->key_info[key].flags & (HA_NOSAME))
3681
if (const_ref == eq_part)
3682
{ // Found everything for ref.
3686
join->const_table_map|=table->map;
3687
set_position(join,const_count++,s,start_keyuse);
3688
if (create_ref_for_key(join, s, start_keyuse,
3689
found_const_table_map))
3691
if ((tmp=join_read_const_table(s,
3692
join->positions+const_count-1)))
3695
return(1); // Fatal error
3698
found_const_table_map|= table->map;
3702
found_ref|= refs; // Table is const if all refs are const
3704
else if (const_ref == eq_part)
3705
s->const_keys.set_bit(key);
3710
} while (join->const_table_map & found_ref && ref_changed);
3713
Update info on indexes that can be used for search lookups as
3714
reading const tables may has added new sargable predicates.
3716
if (const_count && sargables)
3718
for( ; sargables->field ; sargables++)
3720
Field *field= sargables->field;
3721
JOIN_TAB *join_tab= field->table->reginfo.join_tab;
3722
key_map possible_keys= field->key_start;
3723
possible_keys.intersect(field->table->keys_in_use_for_query);
3725
for (uint32_t j=0; j < sargables->num_values; j++)
3726
is_const&= sargables->arg_value[j]->const_item();
3728
join_tab[0].const_keys.merge(possible_keys);
3732
if (pull_out_semijoin_tables(join))
3735
/* Calc how many (possible) matched records in each table */
3737
for (s=stat ; s < stat_end ; s++)
3739
if (s->type == JT_SYSTEM || s->type == JT_CONST)
3741
/* Only one matching row */
3742
s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
3745
/* Approximate found rows and time to read them */
3746
s->found_records=s->records=s->table->file->stats.records;
3747
s->read_time=(ha_rows) s->table->file->scan_time();
3750
Set a max range of how many seeks we can expect when using keys
3751
This is can't be to high as otherwise we are likely to use
3754
s->worst_seeks= cmin((double) s->found_records / 10,
3755
(double) s->read_time*3);
3756
if (s->worst_seeks < 2.0) // Fix for small tables
3760
Add to stat->const_keys those indexes for which all group fields or
3761
all select distinct fields participate in one index.
3763
add_group_and_distinct_keys(join, s);
3765
if (!s->const_keys.is_clear_all() &&
3766
!s->table->pos_in_table_list->embedding)
3770
select= make_select(s->table, found_const_table_map,
3771
found_const_table_map,
3772
*s->on_expr_ref ? *s->on_expr_ref : conds,
3776
records= get_quick_record_count(join->session, select, s->table,
3777
&s->const_keys, join->row_limit);
3778
s->quick=select->quick;
3779
s->needed_reg=select->needed_reg;
3781
if (records == 0 && s->table->reginfo.impossible_range)
3784
Impossible WHERE or ON expression
3785
In case of ON, we mark that the we match one empty NULL row.
3786
In case of WHERE, don't set found_const_table_map to get the
3787
caller to abort with a zero row result.
3789
join->const_table_map|= s->table->map;
3790
set_position(join,const_count++,s,(KEYUSE*) 0);
3792
if (*s->on_expr_ref)
3794
/* Generate empty row */
3795
s->info= "Impossible ON condition";
3796
found_const_table_map|= s->table->map;
3798
s->table->mark_as_null_row(); // All fields are NULL
3801
if (records != HA_POS_ERROR)
3803
s->found_records=records;
3804
s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
3810
join->join_tab=stat;
3811
join->map2table=stat_ref;
3812
join->table= join->all_tables=table_vector;
3813
join->const_tables=const_count;
3814
join->found_const_table_map=found_const_table_map;
3816
/* Find an optimal join order of the non-constant tables. */
3817
if (join->const_tables != join->tables)
3819
optimize_keyuse(join, keyuse_array);
3820
if (choose_plan(join, all_table_map & ~join->const_table_map))
3825
memcpy(join->best_positions, join->positions,
3826
sizeof(POSITION)*join->const_tables);
3827
join->best_read=1.0;
3829
/* Generate an execution plan from the found optimal join order. */
3830
return(join->session->killed || get_best_combination(join));
487
3834
/*****************************************************************************
488
3835
Check with keys are used and with tables references with tables
489
3836
Updates in stat:
492
3839
keyuse Pointer to possible keys
493
3840
*****************************************************************************/
3842
/// Used when finding key fields
3843
typedef struct key_field_t {
3845
Item *val; ///< May be empty if diff constant
3847
uint optimize; // KEY_OPTIMIZE_*
3850
If true, the condition this struct represents will not be satisfied
3853
bool null_rejecting;
3854
bool *cond_guard; /* See KEYUSE::cond_guard */
3855
uint32_t sj_pred_no; /* See KEYUSE::sj_pred_no */
3859
Merge new key definitions to old ones, remove those not used in both.
3861
This is called for OR between different levels.
3863
To be able to do 'ref_or_null' we merge a comparison of a column
3864
and 'column IS NULL' to one test. This is useful for sub select queries
3865
that are internally transformed to something like:.
3868
SELECT * FROM t1 WHERE t1.key=outer_ref_field or t1.key IS NULL
3871
KEY_FIELD::null_rejecting is processed as follows: @n
3872
result has null_rejecting=true if it is set for both ORed references.
3874
- (t2.key = t1.field OR t2.key = t1.field) -> null_rejecting=true
3875
- (t2.key = t1.field OR t2.key <=> t1.field) -> null_rejecting=false
3878
The result of this is that we're missing some 'ref' accesses.
3879
OptimizerTeam: Fix this
3883
merge_key_fields(KEY_FIELD *start,KEY_FIELD *new_fields,KEY_FIELD *end,
3886
if (start == new_fields)
3887
return start; // Impossible or
3888
if (new_fields == end)
3889
return start; // No new fields, skip all
3891
KEY_FIELD *first_free=new_fields;
3893
/* Mark all found fields in old array */
3894
for (; new_fields != end ; new_fields++)
3896
for (KEY_FIELD *old=start ; old != first_free ; old++)
3898
if (old->field == new_fields->field)
3901
NOTE: below const_item() call really works as "!used_tables()", i.e.
3902
it can return false where it is feasible to make it return true.
3904
The cause is as follows: Some of the tables are already known to be
3905
const tables (the detection code is in make_join_statistics(),
3906
above the update_ref_and_keys() call), but we didn't propagate
3907
information about this: Table::const_table is not set to true, and
3908
Item::update_used_tables() hasn't been called for each item.
3909
The result of this is that we're missing some 'ref' accesses.
3910
TODO: OptimizerTeam: Fix this
3912
if (!new_fields->val->const_item())
3915
If the value matches, we can use the key reference.
3916
If not, we keep it until we have examined all new values
3918
if (old->val->eq(new_fields->val, old->field->binary()))
3920
old->level= and_level;
3921
old->optimize= ((old->optimize & new_fields->optimize &
3922
KEY_OPTIMIZE_EXISTS) |
3923
((old->optimize | new_fields->optimize) &
3924
KEY_OPTIMIZE_REF_OR_NULL));
3925
old->null_rejecting= (old->null_rejecting &&
3926
new_fields->null_rejecting);
3929
else if (old->eq_func && new_fields->eq_func &&
3930
old->val->eq_by_collation(new_fields->val,
3931
old->field->binary(),
3932
old->field->charset()))
3935
old->level= and_level;
3936
old->optimize= ((old->optimize & new_fields->optimize &
3937
KEY_OPTIMIZE_EXISTS) |
3938
((old->optimize | new_fields->optimize) &
3939
KEY_OPTIMIZE_REF_OR_NULL));
3940
old->null_rejecting= (old->null_rejecting &&
3941
new_fields->null_rejecting);
3943
else if (old->eq_func && new_fields->eq_func &&
3944
((old->val->const_item() && old->val->is_null()) ||
3945
new_fields->val->is_null()))
3947
/* field = expression OR field IS NULL */
3948
old->level= and_level;
3949
old->optimize= KEY_OPTIMIZE_REF_OR_NULL;
3951
Remember the NOT NULL value unless the value does not depend
3954
if (!old->val->used_tables() && old->val->is_null())
3955
old->val= new_fields->val;
3956
/* The referred expression can be NULL: */
3957
old->null_rejecting= 0;
3962
We are comparing two different const. In this case we can't
3963
use a key-lookup on this so it's better to remove the value
3964
and let the range optimzier handle it
3966
if (old == --first_free) // If last item
3968
*old= *first_free; // Remove old value
3969
old--; // Retry this value
3974
/* Remove all not used items */
3975
for (KEY_FIELD *old=start ; old != first_free ;)
3977
if (old->level != and_level)
3978
{ // Not used in all levels
3979
if (old == --first_free)
3981
*old= *first_free; // Remove old value
3991
Add a possible key to array of possible keys if it's usable as a key
3993
@param key_fields Pointer to add key, if usable
3994
@param and_level And level, to be stored in KEY_FIELD
3995
@param cond Condition predicate
3996
@param field Field used in comparision
3997
@param eq_func True if we used =, <=> or IS NULL
3998
@param value Value used for comparison with field
3999
@param usable_tables Tables which can be used for key optimization
4000
@param sargables IN/OUT Array of found sargable candidates
4003
If we are doing a NOT NULL comparison on a NOT NULL field in a outer join
4004
table, we store this to be able to do not exists optimization later.
4007
*key_fields is incremented if we stored a key in the array
4011
add_key_field(KEY_FIELD **key_fields,uint32_t and_level, Item_func *cond,
4012
Field *field, bool eq_func, Item **value, uint32_t num_values,
4013
table_map usable_tables, SARGABLE_PARAM **sargables)
4015
uint32_t exists_optimize= 0;
4016
if (!(field->flags & PART_KEY_FLAG))
4018
// Don't remove column IS NULL on a LEFT JOIN table
4019
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
4020
!field->table->maybe_null || field->null_ptr)
4021
return; // Not a key. Skip it
4022
exists_optimize= KEY_OPTIMIZE_EXISTS;
4023
assert(num_values == 1);
4027
table_map used_tables=0;
4029
for (uint32_t i=0; i<num_values; i++)
4031
used_tables|=(value[i])->used_tables();
4032
if (!((value[i])->used_tables() & (field->table->map | RAND_TABLE_BIT)))
4037
if (!(usable_tables & field->table->map))
4039
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
4040
!field->table->maybe_null || field->null_ptr)
4041
return; // Can't use left join optimize
4042
exists_optimize= KEY_OPTIMIZE_EXISTS;
4046
JOIN_TAB *stat=field->table->reginfo.join_tab;
4047
key_map possible_keys=field->key_start;
4048
possible_keys.intersect(field->table->keys_in_use_for_query);
4049
stat[0].keys.merge(possible_keys); // Add possible keys
4052
Save the following cases:
4054
Field LIKE constant where constant doesn't start with a wildcard
4055
Field = field2 where field2 is in a different table
4062
stat[0].key_dependent|=used_tables;
4065
for (uint32_t i=0; i<num_values; i++)
4067
if (!(is_const&= value[i]->const_item()))
4071
stat[0].const_keys.merge(possible_keys);
4075
Save info to be able check whether this predicate can be
4076
considered as sargable for range analisis after reading const tables.
4077
We do not save info about equalities as update_const_equal_items
4078
will take care of updating info on keys from sargable equalities.
4081
(*sargables)->field= field;
4082
(*sargables)->arg_value= value;
4083
(*sargables)->num_values= num_values;
4086
We can't always use indexes when comparing a string index to a
4087
number. cmp_type() is checked to allow compare of dates to numbers.
4088
eq_func is NEVER true when num_values > 1
4093
Additional optimization: if we're processing
4094
"t.key BETWEEN c1 AND c1" then proceed as if we were processing
4096
TODO: This is a very limited fix. A more generic fix is possible.
4097
There are 2 options:
4098
A) Make equality propagation code be able to handle BETWEEN
4099
(including cases like t1.key BETWEEN t2.key AND t3.key)
4100
B) Make range optimizer to infer additional "t.key = c" equalities
4101
and use them in equality propagation process (see details in
4104
if ((cond->functype() != Item_func::BETWEEN) ||
4105
((Item_func_between*) cond)->negated ||
4106
!value[0]->eq(value[1], field->binary()))
4111
if (field->result_type() == STRING_RESULT)
4113
if ((*value)->result_type() != STRING_RESULT)
4115
if (field->cmp_type() != (*value)->result_type())
4121
We can't use indexes if the effective collation
4122
of the operation differ from the field collation.
4124
if (field->cmp_type() == STRING_RESULT &&
4125
((Field_str*)field)->charset() != cond->compare_collation())
4132
For the moment eq_func is always true. This slot is reserved for future
4133
extensions where we want to remembers other things than just eq comparisons
4136
/* Store possible eq field */
4137
(*key_fields)->field= field;
4138
(*key_fields)->eq_func= eq_func;
4139
(*key_fields)->val= *value;
4140
(*key_fields)->level= and_level;
4141
(*key_fields)->optimize= exists_optimize;
4143
If the condition has form "tbl.keypart = othertbl.field" and
4144
othertbl.field can be NULL, there will be no matches if othertbl.field
4146
We use null_rejecting in add_not_null_conds() to add
4147
'othertbl.field IS NOT NULL' to tab->select_cond.
4149
(*key_fields)->null_rejecting= ((cond->functype() == Item_func::EQ_FUNC ||
4150
cond->functype() == Item_func::MULT_EQUAL_FUNC) &&
4151
((*value)->type() == Item::FIELD_ITEM) &&
4152
((Item_field*)*value)->field->maybe_null());
4153
(*key_fields)->cond_guard= NULL;
4154
(*key_fields)->sj_pred_no= (cond->name >= subq_sj_cond_name &&
4155
cond->name < subq_sj_cond_name + 64)?
4156
cond->name - subq_sj_cond_name: UINT_MAX;
4161
Add possible keys to array of possible keys originated from a simple
4164
@param key_fields Pointer to add key, if usable
4165
@param and_level And level, to be stored in KEY_FIELD
4166
@param cond Condition predicate
4167
@param field Field used in comparision
4168
@param eq_func True if we used =, <=> or IS NULL
4169
@param value Value used for comparison with field
4170
Is NULL for BETWEEN and IN
4171
@param usable_tables Tables which can be used for key optimization
4172
@param sargables IN/OUT Array of found sargable candidates
4175
If field items f1 and f2 belong to the same multiple equality and
4176
a key is added for f1, the the same key is added for f2.
4179
*key_fields is incremented if we stored a key in the array
4183
add_key_equal_fields(KEY_FIELD **key_fields, uint32_t and_level,
4184
Item_func *cond, Item_field *field_item,
4185
bool eq_func, Item **val,
4186
uint32_t num_values, table_map usable_tables,
4187
SARGABLE_PARAM **sargables)
4189
Field *field= field_item->field;
4190
add_key_field(key_fields, and_level, cond, field,
4191
eq_func, val, num_values, usable_tables, sargables);
4192
Item_equal *item_equal= field_item->item_equal;
4196
Add to the set of possible key values every substitution of
4197
the field for an equal field included into item_equal
4199
Item_equal_iterator it(*item_equal);
4201
while ((item= it++))
4203
if (!field->eq(item->field))
4205
add_key_field(key_fields, and_level, cond, item->field,
4206
eq_func, val, num_values, usable_tables,
4214
add_key_fields(JOIN *join, KEY_FIELD **key_fields, uint32_t *and_level,
4215
COND *cond, table_map usable_tables,
4216
SARGABLE_PARAM **sargables)
4218
if (cond->type() == Item_func::COND_ITEM)
4220
List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
4221
KEY_FIELD *org_key_fields= *key_fields;
4223
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
4227
add_key_fields(join, key_fields, and_level, item, usable_tables,
4229
for (; org_key_fields != *key_fields ; org_key_fields++)
4230
org_key_fields->level= *and_level;
4235
add_key_fields(join, key_fields, and_level, li++, usable_tables,
4240
KEY_FIELD *start_key_fields= *key_fields;
4242
add_key_fields(join, key_fields, and_level, item, usable_tables,
4244
*key_fields=merge_key_fields(org_key_fields,start_key_fields,
4245
*key_fields,++(*and_level));
4252
Subquery optimization: Conditions that are pushed down into subqueries
4253
are wrapped into Item_func_trig_cond. We process the wrapped condition
4254
but need to set cond_guard for KEYUSE elements generated from it.
4257
if (cond->type() == Item::FUNC_ITEM &&
4258
((Item_func*)cond)->functype() == Item_func::TRIG_COND_FUNC)
4260
Item *cond_arg= ((Item_func*)cond)->arguments()[0];
4261
if (!join->group_list && !join->order &&
4263
join->unit->item->substype() == Item_subselect::IN_SUBS &&
4264
!join->unit->is_union())
4266
KEY_FIELD *save= *key_fields;
4267
add_key_fields(join, key_fields, and_level, cond_arg, usable_tables,
4269
// Indicate that this ref access candidate is for subquery lookup:
4270
for (; save != *key_fields; save++)
4271
save->cond_guard= ((Item_func_trig_cond*)cond)->get_trig_var();
4277
/* If item is of type 'field op field/constant' add it to key_fields */
4278
if (cond->type() != Item::FUNC_ITEM)
4280
Item_func *cond_func= (Item_func*) cond;
4281
switch (cond_func->select_optimize()) {
4282
case Item_func::OPTIMIZE_NONE:
4284
case Item_func::OPTIMIZE_KEY:
4288
if (cond_func->key_item()->real_item()->type() == Item::FIELD_ITEM &&
4289
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
4291
values= cond_func->arguments()+1;
4292
if (cond_func->functype() == Item_func::NE_FUNC &&
4293
cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
4294
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
4296
assert(cond_func->functype() != Item_func::IN_FUNC ||
4297
cond_func->argument_count() != 2);
4298
add_key_equal_fields(key_fields, *and_level, cond_func,
4299
(Item_field*) (cond_func->key_item()->real_item()),
4301
cond_func->argument_count()-1,
4302
usable_tables, sargables);
4304
if (cond_func->functype() == Item_func::BETWEEN)
4306
values= cond_func->arguments();
4307
for (uint32_t i= 1 ; i < cond_func->argument_count() ; i++)
4309
Item_field *field_item;
4310
if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM
4312
!(cond_func->arguments()[i]->used_tables() & OUTER_REF_TABLE_BIT))
4314
field_item= (Item_field *) (cond_func->arguments()[i]->real_item());
4315
add_key_equal_fields(key_fields, *and_level, cond_func,
4316
field_item, 0, values, 1, usable_tables,
4323
case Item_func::OPTIMIZE_OP:
4325
bool equal_func=(cond_func->functype() == Item_func::EQ_FUNC ||
4326
cond_func->functype() == Item_func::EQUAL_FUNC);
4328
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
4329
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
4331
add_key_equal_fields(key_fields, *and_level, cond_func,
4332
(Item_field*) (cond_func->arguments()[0])->real_item(),
4334
cond_func->arguments()+1, 1, usable_tables,
4337
if (cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
4338
cond_func->functype() != Item_func::LIKE_FUNC &&
4339
!(cond_func->arguments()[1]->used_tables() & OUTER_REF_TABLE_BIT))
4341
add_key_equal_fields(key_fields, *and_level, cond_func,
4342
(Item_field*) (cond_func->arguments()[1])->real_item(),
4344
cond_func->arguments(),1,usable_tables,
4349
case Item_func::OPTIMIZE_NULL:
4350
/* column_name IS [NOT] NULL */
4351
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
4352
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
4354
Item *tmp=new Item_null;
4355
if (unlikely(!tmp)) // Should never be true
4357
add_key_equal_fields(key_fields, *and_level, cond_func,
4358
(Item_field*) (cond_func->arguments()[0])->real_item(),
4359
cond_func->functype() == Item_func::ISNULL_FUNC,
4360
&tmp, 1, usable_tables, sargables);
4363
case Item_func::OPTIMIZE_EQUAL:
4364
Item_equal *item_equal= (Item_equal *) cond;
4365
Item *const_item= item_equal->get_const();
4366
Item_equal_iterator it(*item_equal);
4371
For each field field1 from item_equal consider the equality
4372
field1=const_item as a condition allowing an index access of the table
4373
with field1 by the keys value of field1.
4375
while ((item= it++))
4377
add_key_field(key_fields, *and_level, cond_func, item->field,
4378
true, &const_item, 1, usable_tables, sargables);
4384
Consider all pairs of different fields included into item_equal.
4385
For each of them (field1, field1) consider the equality
4386
field1=field2 as a condition allowing an index access of the table
4387
with field1 by the keys value of field2.
4389
Item_equal_iterator fi(*item_equal);
4390
while ((item= fi++))
4392
Field *field= item->field;
4393
while ((item= it++))
4395
if (!field->eq(item->field))
4397
add_key_field(key_fields, *and_level, cond_func, field,
4398
true, (Item **) &item, 1, usable_tables,
497
4410
Add all keys with uses 'field' for some keypart.
499
4412
If field->and_level != and_level then only mark key_part as const_part.
501
uint32_t max_part_bit(key_part_map bits)
4416
max_part_bit(key_part_map bits)
504
4419
for (found=0; bits & 1 ; found++,bits>>=1) ;
508
static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b)
4424
add_key_part(DYNAMIC_ARRAY *keyuse_array,KEY_FIELD *key_field)
4426
Field *field=key_field->field;
4427
Table *form= field->table;
4430
if (key_field->eq_func && !(key_field->optimize & KEY_OPTIMIZE_EXISTS))
4432
for (uint32_t key= 0 ; key < form->sizeKeys() ; key++)
4434
if (!(form->keys_in_use_for_query.is_set(key)))
4437
uint32_t key_parts= (uint32_t) form->key_info[key].key_parts;
4438
for (uint32_t part=0 ; part < key_parts ; part++)
4440
if (field->eq(form->key_info[key].key_part[part].field))
4442
keyuse.table= field->table;
4443
keyuse.val = key_field->val;
4445
keyuse.keypart=part;
4446
keyuse.keypart_map= (key_part_map) 1 << part;
4447
keyuse.used_tables=key_field->val->used_tables();
4448
keyuse.optimize= key_field->optimize & KEY_OPTIMIZE_REF_OR_NULL;
4449
keyuse.null_rejecting= key_field->null_rejecting;
4450
keyuse.cond_guard= key_field->cond_guard;
4451
keyuse.sj_pred_no= key_field->sj_pred_no;
4452
insert_dynamic(keyuse_array,(unsigned char*) &keyuse);
4460
sort_keyuse(KEYUSE *a,KEYUSE *b)
511
if (a->getTable()->tablenr != b->getTable()->tablenr)
512
return static_cast<int>((a->getTable()->tablenr - b->getTable()->tablenr));
513
if (a->getKey() != b->getKey())
514
return static_cast<int>((a->getKey() - b->getKey()));
515
if (a->getKeypart() != b->getKeypart())
516
return static_cast<int>((a->getKeypart() - b->getKeypart()));
4463
if (a->table->tablenr != b->table->tablenr)
4464
return (int) (a->table->tablenr - b->table->tablenr);
4465
if (a->key != b->key)
4466
return (int) (a->key - b->key);
4467
if (a->keypart != b->keypart)
4468
return (int) (a->keypart - b->keypart);
517
4469
// Place const values before other ones
518
if ((res= test((a->getUsedTables() & ~OUTER_REF_TABLE_BIT)) -
519
test((b->getUsedTables() & ~OUTER_REF_TABLE_BIT))))
4470
if ((res= test((a->used_tables & ~OUTER_REF_TABLE_BIT)) -
4471
test((b->used_tables & ~OUTER_REF_TABLE_BIT))))
521
4473
/* Place rows that are not 'OPTIMIZE_REF_OR_NULL' first */
522
return static_cast<int>(((a->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL) -
523
(b->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL)));
4474
return (int) ((a->optimize & KEY_OPTIMIZE_REF_OR_NULL) -
4475
(b->optimize & KEY_OPTIMIZE_REF_OR_NULL));
4480
Add to KEY_FIELD array all 'ref' access candidates within nested join.
4482
This function populates KEY_FIELD array with entries generated from the
4483
ON condition of the given nested join, and does the same for nested joins
4484
contained within this nested join.
4486
@param[in] nested_join_table Nested join pseudo-table to process
4487
@param[in,out] end End of the key field array
4488
@param[in,out] and_level And-level
4489
@param[in,out] sargables Array of found sargable candidates
4493
We can add accesses to the tables that are direct children of this nested
4494
join (1), and are not inner tables w.r.t their neighbours (2).
4496
Example for #1 (outer brackets pair denotes nested join this function is
4499
... LEFT JOIN (t1 LEFT JOIN (t2 ... ) ) ON cond
4503
... LEFT JOIN (t1 LEFT JOIN t2 ) ON cond
4505
In examples 1-2 for condition cond, we can add 'ref' access candidates to
4509
... LEFT JOIN (t1, t2 LEFT JOIN t3 ON inner_cond) ON cond
4511
Here we can add 'ref' access candidates for t1 and t2, but not for t3.
4514
static void add_key_fields_for_nj(JOIN *join, TableList *nested_join_table,
4515
KEY_FIELD **end, uint32_t *and_level,
4516
SARGABLE_PARAM **sargables)
4518
List_iterator<TableList> li(nested_join_table->nested_join->join_list);
4519
List_iterator<TableList> li2(nested_join_table->nested_join->join_list);
4520
bool have_another = false;
4521
table_map tables= 0;
4523
assert(nested_join_table->nested_join);
4525
while ((table= li++) || (have_another && (li=li2, have_another=false,
4528
if (table->nested_join)
4530
if (!table->on_expr)
4532
/* It's a semi-join nest. Walk into it as if it wasn't a nest */
4535
li= List_iterator<TableList>(table->nested_join->join_list);
4538
add_key_fields_for_nj(join, table, end, and_level, sargables);
4541
if (!table->on_expr)
4542
tables |= table->table->map;
4544
if (nested_join_table->on_expr)
4545
add_key_fields(join, end, and_level, nested_join_table->on_expr, tables,
779
4809
/* Intersect the keys of all group fields. */
780
4810
cur_item= indexed_fields_it++;
781
possible_keys|= cur_item->field->part_of_key;
4811
possible_keys.merge(cur_item->field->part_of_key);
782
4812
while ((cur_item= indexed_fields_it++))
784
possible_keys&= cur_item->field->part_of_key;
787
if (possible_keys.any())
788
join_tab->const_keys|= possible_keys;
792
Compare two JoinTable objects based on the number of accessed records.
794
@param ptr1 pointer to first JoinTable object
795
@param ptr2 pointer to second JoinTable object
4814
possible_keys.intersect(cur_item->field->part_of_key);
4817
if (!possible_keys.is_clear_all())
4818
join_tab->const_keys.merge(possible_keys);
4822
/*****************************************************************************
4823
Go through all combinations of not marked tables and find the one
4824
which uses least records
4825
*****************************************************************************/
4827
/** Save const tables first as used tables. */
4830
set_position(JOIN *join,uint32_t idx,JOIN_TAB *table,KEYUSE *key)
4832
join->positions[idx].table= table;
4833
join->positions[idx].key=key;
4834
join->positions[idx].records_read=1.0; /* This is a const table */
4835
join->positions[idx].ref_depend_map= 0;
4837
/* Move the const table as down as possible in best_ref */
4838
JOIN_TAB **pos=join->best_ref+idx+1;
4839
JOIN_TAB *next=join->best_ref[idx];
4840
for (;next != table ; pos++)
4842
JOIN_TAB *tmp=pos[0];
4846
join->best_ref[idx]=table;
4851
Given a semi-join nest, find out which of the IN-equalities are bound
4854
get_bound_sj_equalities()
4855
sj_nest Semi-join nest
4856
remaining_tables Tables that are not yet bound
4859
Given a semi-join nest, find out which of the IN-equalities have their
4860
left part expression bound (i.e. the said expression doesn't refer to
4861
any of remaining_tables and can be evaluated).
4864
Bitmap of bound IN-equalities.
4867
uint64_t get_bound_sj_equalities(TableList *sj_nest,
4868
table_map remaining_tables)
4870
List_iterator<Item> li(sj_nest->nested_join->sj_outer_expr_list);
4874
while ((item= li++))
4877
Q: should this take into account equality propagation and how?
4878
A: If e->outer_side is an Item_field, walk over the equality
4879
class and see if there is an element that is bound?
4880
(this is an optional feature)
4882
if (!(item->used_tables() & remaining_tables))
4892
Find the best access path for an extension of a partial execution
4893
plan and add this path to the plan.
4895
The function finds the best access path to table 's' from the passed
4896
partial plan where an access path is the general term for any means to
4897
access the data in 's'. An access path may use either an index or a scan,
4898
whichever is cheaper. The input partial plan is passed via the array
4899
'join->positions' of length 'idx'. The chosen access method for 's' and its
4900
cost are stored in 'join->positions[idx]'.
4902
@param join pointer to the structure providing all context info
4904
@param s the table to be joined by the function
4905
@param session thread for the connection that submitted the query
4906
@param remaining_tables set of tables not included into the partial plan yet
4907
@param idx the length of the partial plan
4908
@param record_count estimate for the number of records returned by the
4910
@param read_time the cost of the partial plan
4917
best_access_path(JOIN *join,
4920
table_map remaining_tables,
4922
double record_count,
4925
KEYUSE *best_key= 0;
4926
uint32_t best_max_key_part= 0;
4927
bool found_constraint= 0;
4928
double best= DBL_MAX;
4929
double best_time= DBL_MAX;
4930
double records= DBL_MAX;
4931
table_map best_ref_depends_map= 0;
4934
uint32_t best_is_sj_inside_out= 0;
4937
{ /* Use key if possible */
4938
Table *table= s->table;
4939
KEYUSE *keyuse,*start_key=0;
4940
double best_records= DBL_MAX;
4941
uint32_t max_key_part=0;
4942
uint64_t bound_sj_equalities= 0;
4943
bool try_sj_inside_out= false;
4945
Discover the bound equalites. We need to do this, if
4946
1. The next table is an SJ-inner table, and
4947
2. It is the first table from that semijoin, and
4948
3. We're not within a semi-join range (i.e. all semi-joins either have
4949
all or none of their tables in join_table_map), except
4950
s->emb_sj_nest (which we've just entered).
4951
3. All correlation references from this sj-nest are bound
4953
if (s->emb_sj_nest && // (1)
4954
s->emb_sj_nest->sj_in_exprs < 64 &&
4955
((remaining_tables & s->emb_sj_nest->sj_inner_tables) == // (2)
4956
s->emb_sj_nest->sj_inner_tables) && // (2)
4957
join->cur_emb_sj_nests == s->emb_sj_nest->sj_inner_tables && // (3)
4958
!(remaining_tables & s->emb_sj_nest->nested_join->sj_corr_tables)) // (4)
4960
/* This table is an InsideOut scan candidate */
4961
bound_sj_equalities= get_bound_sj_equalities(s->emb_sj_nest,
4963
try_sj_inside_out= true;
4966
/* Test how we can use keys */
4967
rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key
4968
for (keyuse=s->keyuse ; keyuse->table == table ;)
4970
key_part_map found_part= 0;
4971
table_map found_ref= 0;
4972
uint32_t key= keyuse->key;
4973
KEY *keyinfo= table->key_info+key;
4974
/* Bitmap of keyparts where the ref access is over 'keypart=const': */
4975
key_part_map const_part= 0;
4976
/* The or-null keypart in ref-or-null access: */
4977
key_part_map ref_or_null_part= 0;
4979
/* Calculate how many key segments of the current key we can use */
4981
uint64_t handled_sj_equalities=0;
4982
key_part_map sj_insideout_map= 0;
4984
do /* For each keypart */
4986
uint32_t keypart= keyuse->keypart;
4987
table_map best_part_found_ref= 0;
4988
double best_prev_record_reads= DBL_MAX;
4990
do /* For each way to access the keypart */
4994
if 1. expression doesn't refer to forward tables
4995
2. we won't get two ref-or-null's
4997
if (!(remaining_tables & keyuse->used_tables) &&
4998
!(ref_or_null_part && (keyuse->optimize &
4999
KEY_OPTIMIZE_REF_OR_NULL)))
5001
found_part|= keyuse->keypart_map;
5002
if (!(keyuse->used_tables & ~join->const_table_map))
5003
const_part|= keyuse->keypart_map;
5005
double tmp2= prev_record_reads(join, idx, (found_ref |
5006
keyuse->used_tables));
5007
if (tmp2 < best_prev_record_reads)
5009
best_part_found_ref= keyuse->used_tables & ~join->const_table_map;
5010
best_prev_record_reads= tmp2;
5012
if (rec > keyuse->ref_table_rows)
5013
rec= keyuse->ref_table_rows;
5015
If there is one 'key_column IS NULL' expression, we can
5016
use this ref_or_null optimisation of this field
5018
if (keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL)
5019
ref_or_null_part |= keyuse->keypart_map;
5022
if (try_sj_inside_out && keyuse->sj_pred_no != UINT_MAX)
5024
if (!(remaining_tables & keyuse->used_tables))
5025
bound_sj_equalities |= 1UL << keyuse->sj_pred_no;
5028
handled_sj_equalities |= 1UL << keyuse->sj_pred_no;
5029
sj_insideout_map |= ((key_part_map)1) << keyuse->keypart;
5034
} while (keyuse->table == table && keyuse->key == key &&
5035
keyuse->keypart == keypart);
5036
found_ref|= best_part_found_ref;
5037
} while (keyuse->table == table && keyuse->key == key);
5040
Assume that that each key matches a proportional part of table.
5042
if (!found_part && !handled_sj_equalities)
5043
continue; // Nothing usable found
5045
if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
5046
rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables
5048
bool sj_inside_out_scan= false;
5050
found_constraint= 1;
5052
Check if InsideOut scan is applicable:
5053
1. All IN-equalities are either "bound" or "handled"
5054
2. Index keyparts are
5057
if (try_sj_inside_out &&
5058
table->covering_keys.is_set(key) &&
5059
(handled_sj_equalities | bound_sj_equalities) == // (1)
5060
PREV_BITS(uint64_t, s->emb_sj_nest->sj_in_exprs)) // (1)
5062
uint32_t n_fixed_parts= max_part_bit(found_part);
5063
if (n_fixed_parts != keyinfo->key_parts &&
5064
(PREV_BITS(uint, n_fixed_parts) | sj_insideout_map) ==
5065
PREV_BITS(uint, keyinfo->key_parts))
5068
Not all parts are fixed. Produce bitmap of remaining bits and
5069
check if all of them are covered.
5071
sj_inside_out_scan= true;
5075
It's a confluent ref scan.
5077
That is, all found KEYUSE elements refer to IN-equalities,
5078
and there is really no ref access because there is no
5079
t.keypart0 = {bound expression}
5081
Calculate the cost of complete loose index scan.
5083
records= (double)s->table->file->stats.records;
5085
/* The cost is entire index scan cost (divided by 2) */
5086
best_time= s->table->file->index_only_read_time(key, records);
5088
/* Now figure how many different keys we will get */
5090
if ((rpc= keyinfo->rec_per_key[keyinfo->key_parts-1]))
5091
records= records / rpc;
5098
Check if we found full key
5100
if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&
5103
max_key_part= UINT32_MAX;
5104
if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
5106
tmp = prev_record_reads(join, idx, found_ref);
5112
{ /* We found a const key */
5114
ReuseRangeEstimateForRef-1:
5115
We get here if we've found a ref(const) (c_i are constants):
5116
"(keypart1=c1) AND ... AND (keypartN=cN)" [ref_const_cond]
5118
If range optimizer was able to construct a "range"
5119
access on this index, then its condition "quick_cond" was
5120
eqivalent to ref_const_cond (*), and we can re-use E(#rows)
5121
from the range optimizer.
5123
Proof of (*): By properties of range and ref optimizers
5124
quick_cond will be equal or tighther than ref_const_cond.
5125
ref_const_cond already covers "smallest" possible interval -
5126
a singlepoint interval over all keyparts. Therefore,
5127
quick_cond is equivalent to ref_const_cond (if it was an
5128
empty interval we wouldn't have got here).
5130
if (table->quick_keys.is_set(key))
5131
records= (double) table->quick_rows[key];
5134
/* quick_range couldn't use key! */
5135
records= (double) s->records/rec;
5140
if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
5141
{ /* Prefer longer keys */
5143
((double) s->records / (double) rec *
5145
((double) (table->s->max_key_length-keyinfo->key_length) /
5146
(double) table->s->max_key_length)));
5148
records=2.0; /* Can't be as good as a unique */
5151
ReuseRangeEstimateForRef-2: We get here if we could not reuse
5152
E(#rows) from range optimizer. Make another try:
5154
If range optimizer produced E(#rows) for a prefix of the ref
5155
access we're considering, and that E(#rows) is lower then our
5156
current estimate, make an adjustment. The criteria of when we
5157
can make an adjustment is a special case of the criteria used
5158
in ReuseRangeEstimateForRef-3.
5160
if (table->quick_keys.is_set(key) &&
5161
const_part & (1 << table->quick_key_parts[key]) &&
5162
table->quick_n_ranges[key] == 1 &&
5163
records > (double) table->quick_rows[key])
5165
records= (double) table->quick_rows[key];
5168
/* Limit the number of matched rows */
5170
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
5171
if (table->covering_keys.is_set(key))
5173
/* we can use only index tree */
5174
tmp= record_count * table->file->index_only_read_time(key, tmp);
5177
tmp= record_count*cmin(tmp,s->worst_seeks);
5183
Use as much key-parts as possible and a uniq key is better
5184
than a not unique key
5185
Set tmp to (previous record count) * (records / combination)
5187
if ((found_part & 1) &&
5188
(!(table->file->index_flags(key, 0, 0) & HA_ONLY_WHOLE_INDEX) ||
5189
found_part == PREV_BITS(uint,keyinfo->key_parts)))
5191
max_key_part= max_part_bit(found_part);
5193
ReuseRangeEstimateForRef-3:
5194
We're now considering a ref[or_null] access via
5195
(t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR
5196
(same-as-above but with one cond replaced
5197
with "t.keypart_i IS NULL")] (**)
5199
Try re-using E(#rows) from "range" optimizer:
5200
We can do so if "range" optimizer used the same intervals as
5201
in (**). The intervals used by range optimizer may be not
5202
available at this point (as "range" access might have choosen to
5203
create quick select over another index), so we can't compare
5204
them to (**). We'll make indirect judgements instead.
5205
The sufficient conditions for re-use are:
5206
(C1) All e_i in (**) are constants, i.e. found_ref==false. (if
5207
this is not satisfied we have no way to know which ranges
5208
will be actually scanned by 'ref' until we execute the
5210
(C2) max #key parts in 'range' access == K == max_key_part (this
5211
is apparently a necessary requirement)
5213
We also have a property that "range optimizer produces equal or
5214
tighter set of scan intervals than ref(const) optimizer". Each
5215
of the intervals in (**) are "tightest possible" intervals when
5216
one limits itself to using keyparts 1..K (which we do in #2).
5217
From here it follows that range access used either one, or
5218
both of the (I1) and (I2) intervals:
5220
(t.keypart1=c1 AND ... AND t.keypartK=eK) (I1)
5221
(same-as-above but with one cond replaced
5222
with "t.keypart_i IS NULL") (I2)
5224
The remaining part is to exclude the situation where range
5225
optimizer used one interval while we're considering
5226
ref-or-null and looking for estimate for two intervals. This
5227
is done by last limitation:
5229
(C3) "range optimizer used (have ref_or_null?2:1) intervals"
5231
if (table->quick_keys.is_set(key) && !found_ref && //(C1)
5232
table->quick_key_parts[key] == max_key_part && //(C2)
5233
table->quick_n_ranges[key] == 1+((ref_or_null_part)?1:0)) //(C3)
5235
tmp= records= (double) table->quick_rows[key];
5239
/* Check if we have statistic about the distribution */
5240
if ((records= keyinfo->rec_per_key[max_key_part-1]))
5243
Fix for the case where the index statistics is too
5245
(1) We're considering ref(const) and there is quick select
5247
(2) and that quick select uses more keyparts (i.e. it will
5248
scan equal/smaller interval then this ref(const))
5249
(3) and E(#rows) for quick select is higher then our
5252
We'll use E(#rows) from quick select.
5254
Q: Why do we choose to use 'ref'? Won't quick select be
5255
cheaper in some cases ?
5256
TODO: figure this out and adjust the plan choice if needed.
5258
if (!found_ref && table->quick_keys.is_set(key) && // (1)
5259
table->quick_key_parts[key] > max_key_part && // (2)
5260
records < (double)table->quick_rows[key]) // (3)
5261
records= (double)table->quick_rows[key];
5268
Assume that the first key part matches 1% of the file
5269
and that the whole key matches 10 (duplicates) or 1
5271
Assume also that more key matches proportionally more
5273
This gives the formula:
5274
records = (x * (b-a) + a*c-b)/(c-1)
5276
b = records matched by whole key
5277
a = records matched by first key part (1% of all records?)
5278
c = number of key parts in key
5279
x = used key parts (1 <= x <= c)
5282
if (!(rec_per_key=(double)
5283
keyinfo->rec_per_key[keyinfo->key_parts-1]))
5284
rec_per_key=(double) s->records/rec+1;
5288
else if (rec_per_key/(double) s->records >= 0.01)
5292
double a=s->records*0.01;
5293
if (keyinfo->key_parts > 1)
5294
tmp= (max_key_part * (rec_per_key - a) +
5295
a*keyinfo->key_parts - rec_per_key)/
5296
(keyinfo->key_parts-1);
5299
set_if_bigger(tmp,1.0);
5301
records = (uint32_t) tmp;
5304
if (ref_or_null_part)
5306
/* We need to do two key searches to find key */
5312
ReuseRangeEstimateForRef-4: We get here if we could not reuse
5313
E(#rows) from range optimizer. Make another try:
5315
If range optimizer produced E(#rows) for a prefix of the ref
5316
access we're considering, and that E(#rows) is lower then our
5317
current estimate, make the adjustment.
5319
The decision whether we can re-use the estimate from the range
5320
optimizer is the same as in ReuseRangeEstimateForRef-3,
5321
applied to first table->quick_key_parts[key] key parts.
5323
if (table->quick_keys.is_set(key) &&
5324
table->quick_key_parts[key] <= max_key_part &&
5325
const_part & (1 << table->quick_key_parts[key]) &&
5326
table->quick_n_ranges[key] == 1 + ((ref_or_null_part &
5327
const_part) ? 1 : 0) &&
5328
records > (double) table->quick_rows[key])
5330
tmp= records= (double) table->quick_rows[key];
5334
/* Limit the number of matched rows */
5335
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
5336
if (table->covering_keys.is_set(key))
5338
/* we can use only index tree */
5339
tmp= record_count * table->file->index_only_read_time(key, tmp);
5342
tmp= record_count * cmin(tmp,s->worst_seeks);
5345
tmp= best_time; // Do nothing
5348
if (sj_inside_out_scan && !start_key)
5356
if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
5358
best_time= tmp + records/(double) TIME_FOR_COMPARE;
5360
best_records= records;
5361
best_key= start_key;
5362
best_max_key_part= max_key_part;
5363
best_ref_depends_map= found_ref;
5364
best_is_sj_inside_out= sj_inside_out_scan;
5367
records= best_records;
5371
Don't test table scan if it can't be better.
5372
Prefer key lookup if we would use the same key for scanning.
5374
Don't do a table scan on InnoDB tables, if we can read the used
5375
parts of the row from any of the used index.
5376
This is because table scans uses index and we would not win
5377
anything by using a table scan.
5379
A word for word translation of the below if-statement in sergefp's
5380
understanding: we check if we should use table scan if:
5381
(1) The found 'ref' access produces more records than a table scan
5382
(or index scan, or quick select), or 'ref' is more expensive than
5384
(2) This doesn't hold: the best way to perform table scan is to to perform
5385
'range' access using index IDX, and the best way to perform 'ref'
5386
access is to use the same index IDX, with the same or more key parts.
5387
(note: it is not clear how this rule is/should be extended to
5388
index_merge quick selects)
5389
(3) See above note about InnoDB.
5390
(4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access
5391
path, but there is no quick select)
5392
If the condition in the above brackets holds, then the only possible
5393
"table scan" access method is ALL/index (there is no quick select).
5394
Since we have a 'ref' access path, and FORCE INDEX instructs us to
5395
choose it over ALL/index, there is no need to consider a full table
5398
if ((records >= s->found_records || best > s->read_time) && // (1)
5399
!(s->quick && best_key && s->quick->index == best_key->key && // (2)
5400
best_max_key_part >= s->table->quick_key_parts[best_key->key]) &&// (2)
5401
!((s->table->file->ha_table_flags() & HA_TABLE_SCAN_ON_INDEX) && // (3)
5402
! s->table->covering_keys.is_clear_all() && best_key && !s->quick) &&// (3)
5403
!(s->table->force_index && best_key && !s->quick)) // (4)
5404
{ // Check full join
5405
ha_rows rnd_records= s->found_records;
5407
If there is a filtering condition on the table (i.e. ref analyzer found
5408
at least one "table.keyXpartY= exprZ", where exprZ refers only to tables
5409
preceding this table in the join order we're now considering), then
5410
assume that 25% of the rows will be filtered out by this condition.
5412
This heuristic is supposed to force tables used in exprZ to be before
5413
this table in join order.
5415
if (found_constraint)
5416
rnd_records-= rnd_records/4;
5419
If applicable, get a more accurate estimate. Don't use the two
5422
if (s->table->quick_condition_rows != s->found_records)
5423
rnd_records= s->table->quick_condition_rows;
5426
Range optimizer never proposes a RANGE if it isn't better
5427
than FULL: so if RANGE is present, it's always preferred to FULL.
5428
Here we estimate its cost.
5434
- read record range through 'quick'
5435
- skip rows which does not satisfy WHERE constraints
5437
We take into account possible use of join cache for ALL/index
5438
access (see first else-branch below), but we don't take it into
5439
account here for range/index_merge access. Find out why this is so.
5442
(s->quick->read_time +
5443
(s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
5447
/* Estimate cost of reading table. */
5448
tmp= s->table->file->scan_time();
5449
if (s->table->map & join->outer_join) // Can't use join cache
5452
For each record we have to:
5453
- read the whole table record
5454
- skip rows which does not satisfy join condition
5458
(s->records - rnd_records)/(double) TIME_FOR_COMPARE);
5462
/* We read the table as many times as join buffer becomes full. */
5463
tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
5465
(double) session->variables.join_buff_size));
5467
We don't make full cartesian product between rows in the scanned
5468
table and existing records because we skip all rows from the
5469
scanned table, which does not satisfy join condition when
5470
we read the table (see flush_cached_records for details). Here we
5471
take into account cost to read and skip these records.
5473
tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
5478
We estimate the cost of evaluating WHERE clause for found records
5479
as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus
5480
tmp give us total cost of using Table SCAN
5482
if (best == DBL_MAX ||
5483
(tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records <
5484
best + record_count/(double) TIME_FOR_COMPARE*records))
5487
If the table has a range (s->quick is set) make_join_select()
5488
will ensure that this will be used
5491
records= rows2double(rnd_records);
5493
/* range/index_merge/ALL/index access method are "independent", so: */
5494
best_ref_depends_map= 0;
5495
best_is_sj_inside_out= false;
5499
/* Update the cost information for the current partial plan */
5500
join->positions[idx].records_read= records;
5501
join->positions[idx].read_time= best;
5502
join->positions[idx].key= best_key;
5503
join->positions[idx].table= s;
5504
join->positions[idx].ref_depend_map= best_ref_depends_map;
5505
join->positions[idx].use_insideout_scan= best_is_sj_inside_out;
5508
idx == join->const_tables &&
5509
s->table == join->sort_by_table &&
5510
join->unit->select_limit_cnt >= records)
5511
join->sort_by_table= (Table*) 1; // Must use temporary table
5518
Selects and invokes a search strategy for an optimal query plan.
5520
The function checks user-configurable parameters that control the search
5521
strategy for an optimal plan, selects the search method and then invokes
5522
it. Each specific optimization procedure stores the final optimal plan in
5523
the array 'join->best_positions', and the cost of the plan in
5526
@param join pointer to the structure providing all context info for
5528
@param join_tables set of the tables in the query
5531
'MAX_TABLES+2' denotes the old implementation of find_best before
5532
the greedy version. Will be removed when greedy_search is approved.
5541
choose_plan(JOIN *join, table_map join_tables)
5543
uint32_t search_depth= join->session->variables.optimizer_search_depth;
5544
uint32_t prune_level= join->session->variables.optimizer_prune_level;
5545
bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
5547
join->cur_embedding_map= 0;
5548
reset_nj_counters(join->join_list);
5550
if (SELECT_STRAIGHT_JOIN option is set)
5551
reorder tables so dependent tables come after tables they depend
5552
on, otherwise keep tables in the order they were specified in the query
5554
Apply heuristic: pre-sort all access plans with respect to the number of
5557
my_qsort(join->best_ref + join->const_tables,
5558
join->tables - join->const_tables, sizeof(JOIN_TAB*),
5559
straight_join ? join_tab_cmp_straight : join_tab_cmp);
5560
join->cur_emb_sj_nests= 0;
5563
optimize_straight_join(join, join_tables);
5567
if (search_depth == MAX_TABLES+2)
5569
TODO: 'MAX_TABLES+2' denotes the old implementation of find_best before
5570
the greedy version. Will be removed when greedy_search is approved.
5572
join->best_read= DBL_MAX;
5573
if (find_best(join, join_tables, join->const_tables, 1.0, 0.0))
5578
if (search_depth == 0)
5579
/* Automatically determine a reasonable value for 'search_depth' */
5580
search_depth= determine_search_depth(join);
5581
if (greedy_search(join, join_tables, search_depth, prune_level))
5587
Store the cost of this query into a user variable
5588
Don't update last_query_cost for statements that are not "flat joins" :
5589
i.e. they have subqueries, unions or call stored procedures.
5590
TODO: calculate a correct cost for a query with subqueries and UNIONs.
5592
if (join->session->lex->is_single_level_stmt())
5593
join->session->status_var.last_query_cost= join->best_read;
5599
Compare two JOIN_TAB objects based on the number of accessed records.
5601
@param ptr1 pointer to first JOIN_TAB object
5602
@param ptr2 pointer to second JOIN_TAB object
798
5605
The order relation implemented by join_tab_cmp() is not transitive,
5657
Heuristic procedure to automatically guess a reasonable degree of
5658
exhaustiveness for the greedy search procedure.
5660
The procedure estimates the optimization time and selects a search depth
5661
big enough to result in a near-optimal QEP, that doesn't take too long to
5662
find. If the number of tables in the query exceeds some constant, then
5663
search_depth is set to this constant.
5665
@param join pointer to the structure providing all context info for
5669
This is an extremely simplistic implementation that serves as a stub for a
5670
more advanced analysis of the join. Ideally the search depth should be
5671
determined by learning from previous query optimizations, because it will
5672
depend on the CPU power (and other factors).
5675
this value should be determined dynamically, based on statistics:
5676
uint32_t max_tables_for_exhaustive_opt= 7;
5679
this value could be determined by some mapping of the form:
5680
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
5683
A positive integer that specifies the search depth (and thus the
5684
exhaustiveness) of the depth-first search algorithm used by
5689
determine_search_depth(JOIN *join)
5691
uint32_t table_count= join->tables - join->const_tables;
5692
uint32_t search_depth;
5693
/* TODO: this value should be determined dynamically, based on statistics: */
5694
uint32_t max_tables_for_exhaustive_opt= 7;
5696
if (table_count <= max_tables_for_exhaustive_opt)
5697
search_depth= table_count+1; // use exhaustive for small number of tables
5700
TODO: this value could be determined by some mapping of the form:
5701
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
5703
search_depth= max_tables_for_exhaustive_opt; // use greedy search
5705
return search_depth;
5710
Select the best ways to access the tables in a query without reordering them.
5712
Find the best access paths for each query table and compute their costs
5713
according to their order in the array 'join->best_ref' (thus without
5714
reordering the join tables). The function calls sequentially
5715
'best_access_path' for each table in the query to select the best table
5716
access method. The final optimal plan is stored in the array
5717
'join->best_positions', and the corresponding cost in 'join->best_read'.
5719
@param join pointer to the structure providing all context info for
5721
@param join_tables set of the tables in the query
5724
This function can be applied to:
5725
- queries with STRAIGHT_JOIN
5726
- internally to compute the cost of an arbitrary QEP
5728
Thus 'optimize_straight_join' can be used at any stage of the query
5729
optimization process to finalize a QEP as it is.
5733
optimize_straight_join(JOIN *join, table_map join_tables)
5736
uint32_t idx= join->const_tables;
5737
double record_count= 1.0;
5738
double read_time= 0.0;
5740
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
5742
/* Find the best access method from 's' to the current partial plan */
5743
advance_sj_state(join_tables, s);
5744
best_access_path(join, s, join->session, join_tables, idx,
5745
record_count, read_time);
5746
/* compute the cost of the new plan extended with 's' */
5747
record_count*= join->positions[idx].records_read;
5748
read_time+= join->positions[idx].read_time;
5749
join_tables&= ~(s->table->map);
5753
read_time+= record_count / (double) TIME_FOR_COMPARE;
5754
if (join->sort_by_table &&
5755
join->sort_by_table != join->positions[join->const_tables].table->table)
5756
read_time+= record_count; // We have to make a temp table
5757
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
5758
join->best_read= read_time;
5763
Find a good, possibly optimal, query execution plan (QEP) by a greedy search.
5765
The search procedure uses a hybrid greedy/exhaustive search with controlled
5766
exhaustiveness. The search is performed in N = card(remaining_tables)
5767
steps. Each step evaluates how promising is each of the unoptimized tables,
5768
selects the most promising table, and extends the current partial QEP with
5769
that table. Currenly the most 'promising' table is the one with least
5770
expensive extension.\
5772
There are two extreme cases:
5773
-# When (card(remaining_tables) < search_depth), the estimate finds the
5774
best complete continuation of the partial QEP. This continuation can be
5775
used directly as a result of the search.
5776
-# When (search_depth == 1) the 'best_extension_by_limited_search'
5777
consideres the extension of the current QEP with each of the remaining
5780
All other cases are in-between these two extremes. Thus the parameter
5781
'search_depth' controlls the exhaustiveness of the search. The higher the
5782
value, the longer the optimizaton time and possibly the better the
5783
resulting plan. The lower the value, the fewer alternative plans are
5784
estimated, but the more likely to get a bad QEP.
5786
All intermediate and final results of the procedure are stored in 'join':
5787
- join->positions : modified for every partial QEP that is explored
5788
- join->best_positions: modified for the current best complete QEP
5789
- join->best_read : modified for the current best complete QEP
5790
- join->best_ref : might be partially reordered
5792
The final optimal plan is stored in 'join->best_positions', and its
5793
corresponding cost in 'join->best_read'.
5796
The following pseudocode describes the algorithm of 'greedy_search':
5799
procedure greedy_search
5800
input: remaining_tables
5805
(t, a) = best_extension(pplan, remaining_tables);
5806
pplan = concat(pplan, (t, a));
5807
remaining_tables = remaining_tables - t;
5808
} while (remaining_tables != {})
5813
where 'best_extension' is a placeholder for a procedure that selects the
5814
most "promising" of all tables in 'remaining_tables'.
5815
Currently this estimate is performed by calling
5816
'best_extension_by_limited_search' to evaluate all extensions of the
5817
current QEP of size 'search_depth', thus the complexity of 'greedy_search'
5818
mainly depends on that of 'best_extension_by_limited_search'.
5821
If 'best_extension()' == 'best_extension_by_limited_search()', then the
5822
worst-case complexity of this algorithm is <=
5823
O(N*N^search_depth/search_depth). When serch_depth >= N, then the
5824
complexity of greedy_search is O(N!).
5827
In the future, 'greedy_search' might be extended to support other
5828
implementations of 'best_extension', e.g. some simpler quadratic procedure.
5830
@param join pointer to the structure providing all context info
5832
@param remaining_tables set of tables not included into the partial plan yet
5833
@param search_depth controlls the exhaustiveness of the search
5834
@param prune_level the pruning heuristics that should be applied during
5844
greedy_search(JOIN *join,
5845
table_map remaining_tables,
5846
uint32_t search_depth,
5847
uint32_t prune_level)
5849
double record_count= 1.0;
5850
double read_time= 0.0;
5851
uint32_t idx= join->const_tables; // index into 'join->best_ref'
5853
uint32_t size_remain; // cardinality of remaining_tables
5855
JOIN_TAB *best_table; // the next plan node to be added to the curr QEP
5857
/* number of tables that remain to be optimized */
5858
size_remain= my_count_bits(remaining_tables);
5861
/* Find the extension of the current QEP with the lowest cost */
5862
join->best_read= DBL_MAX;
5863
if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,
5864
read_time, search_depth, prune_level))
5867
if (size_remain <= search_depth)
5870
'join->best_positions' contains a complete optimal extension of the
5871
current partial QEP.
5876
/* select the first table in the optimal extension as most promising */
5877
best_pos= join->best_positions[idx];
5878
best_table= best_pos.table;
5880
Each subsequent loop of 'best_extension_by_limited_search' uses
5881
'join->positions' for cost estimates, therefore we have to update its
5884
join->positions[idx]= best_pos;
5886
/* find the position of 'best_table' in 'join->best_ref' */
5888
JOIN_TAB *pos= join->best_ref[best_idx];
5889
while (pos && best_table != pos)
5890
pos= join->best_ref[++best_idx];
5891
assert((pos != NULL)); // should always find 'best_table'
5892
/* move 'best_table' at the first free position in the array of joins */
5893
std::swap(join->best_ref[idx], join->best_ref[best_idx]);
5895
/* compute the cost of the new plan extended with 'best_table' */
5896
record_count*= join->positions[idx].records_read;
5897
read_time+= join->positions[idx].read_time;
5899
remaining_tables&= ~(best_table->table->map);
5907
Find a good, possibly optimal, query execution plan (QEP) by a possibly
5910
The procedure searches for the optimal ordering of the query tables in set
5911
'remaining_tables' of size N, and the corresponding optimal access paths to
5912
each table. The choice of a table order and an access path for each table
5913
constitutes a query execution plan (QEP) that fully specifies how to
5916
The maximal size of the found plan is controlled by the parameter
5917
'search_depth'. When search_depth == N, the resulting plan is complete and
5918
can be used directly as a QEP. If search_depth < N, the found plan consists
5919
of only some of the query tables. Such "partial" optimal plans are useful
5920
only as input to query optimization procedures, and cannot be used directly
5923
The algorithm begins with an empty partial plan stored in 'join->positions'
5924
and a set of N tables - 'remaining_tables'. Each step of the algorithm
5925
evaluates the cost of the partial plan extended by all access plans for
5926
each of the relations in 'remaining_tables', expands the current partial
5927
plan with the access plan that results in lowest cost of the expanded
5928
partial plan, and removes the corresponding relation from
5929
'remaining_tables'. The algorithm continues until it either constructs a
5930
complete optimal plan, or constructs an optimal plartial plan with size =
5933
The final optimal plan is stored in 'join->best_positions'. The
5934
corresponding cost of the optimal plan is in 'join->best_read'.
5937
The procedure uses a recursive depth-first search where the depth of the
5938
recursion (and thus the exhaustiveness of the search) is controlled by the
5939
parameter 'search_depth'.
5942
The pseudocode below describes the algorithm of
5943
'best_extension_by_limited_search'. The worst-case complexity of this
5944
algorithm is O(N*N^search_depth/search_depth). When serch_depth >= N, then
5945
the complexity of greedy_search is O(N!).
5948
procedure best_extension_by_limited_search(
5949
pplan in, // in, partial plan of tables-joined-so-far
5950
pplan_cost, // in, cost of pplan
5951
remaining_tables, // in, set of tables not referenced in pplan
5952
best_plan_so_far, // in/out, best plan found so far
5953
best_plan_so_far_cost,// in/out, cost of best_plan_so_far
5954
search_depth) // in, maximum size of the plans being considered
5956
for each table T from remaining_tables
5958
// Calculate the cost of using table T as above
5959
cost = complex-series-of-calculations;
5961
// Add the cost to the cost so far.
5964
if (pplan_cost >= best_plan_so_far_cost)
5965
// pplan_cost already too great, stop search
5968
pplan= expand pplan by best_access_method;
5969
remaining_tables= remaining_tables - table T;
5970
if (remaining_tables is not an empty set
5974
best_extension_by_limited_search(pplan, pplan_cost,
5977
best_plan_so_far_cost,
5982
best_plan_so_far_cost= pplan_cost;
5983
best_plan_so_far= pplan;
5990
When 'best_extension_by_limited_search' is called for the first time,
5991
'join->best_read' must be set to the largest possible value (e.g. DBL_MAX).
5992
The actual implementation provides a way to optionally use pruning
5993
heuristic (controlled by the parameter 'prune_level') to reduce the search
5994
space by skipping some partial plans.
5997
The parameter 'search_depth' provides control over the recursion
5998
depth, and thus the size of the resulting optimal plan.
6000
@param join pointer to the structure providing all context info
6002
@param remaining_tables set of tables not included into the partial plan yet
6003
@param idx length of the partial QEP in 'join->positions';
6004
since a depth-first search is used, also corresponds
6005
to the current depth of the search tree;
6006
also an index in the array 'join->best_ref';
6007
@param record_count estimate for the number of records returned by the
6009
@param read_time the cost of the best partial plan
6010
@param search_depth maximum depth of the recursion and thus size of the
6012
(0 < search_depth <= join->tables+1).
6013
@param prune_level pruning heuristics that should be applied during
6015
(values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS)
6024
best_extension_by_limited_search(JOIN *join,
6025
table_map remaining_tables,
6027
double record_count,
6029
uint32_t search_depth,
6030
uint32_t prune_level)
6032
Session *session= join->session;
6033
if (session->killed) // Abort
6037
'join' is a partial plan with lower cost than the best plan so far,
6038
so continue expanding it further with the tables in 'remaining_tables'.
6041
double best_record_count= DBL_MAX;
6042
double best_read_time= DBL_MAX;
6044
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
6046
table_map real_table_bit= s->table->map;
6047
if ((remaining_tables & real_table_bit) &&
6048
!(remaining_tables & s->dependent) &&
6049
(!idx || !check_interleaving_with_nj(join->positions[idx-1].table, s)))
6051
double current_record_count, current_read_time;
6052
advance_sj_state(remaining_tables, s);
6055
psergey-insideout-todo:
6056
when best_access_path() detects it could do an InsideOut scan or
6057
some other scan, have it return an insideout scan and a flag that
6058
requests to "fork" this loop iteration. (Q: how does that behave
6059
when the depth is insufficient??)
6061
/* Find the best access method from 's' to the current partial plan */
6062
best_access_path(join, s, session, remaining_tables, idx,
6063
record_count, read_time);
6064
/* Compute the cost of extending the plan with 's' */
6065
current_record_count= record_count * join->positions[idx].records_read;
6066
current_read_time= read_time + join->positions[idx].read_time;
6068
/* Expand only partial plans with lower cost than the best QEP so far */
6069
if ((current_read_time +
6070
current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
6072
restore_prev_nj_state(s);
6073
restore_prev_sj_state(remaining_tables, s);
6078
Prune some less promising partial plans. This heuristic may miss
6079
the optimal QEPs, thus it results in a non-exhaustive search.
6081
if (prune_level == 1)
6083
if (best_record_count > current_record_count ||
6084
best_read_time > current_read_time ||
6085
(idx == join->const_tables && s->table == join->sort_by_table)) // 's' is the first table in the QEP
6087
if (best_record_count >= current_record_count &&
6088
best_read_time >= current_read_time &&
6089
/* TODO: What is the reasoning behind this condition? */
6090
(!(s->key_dependent & remaining_tables) ||
6091
join->positions[idx].records_read < 2.0))
6093
best_record_count= current_record_count;
6094
best_read_time= current_read_time;
6099
restore_prev_nj_state(s);
6100
restore_prev_sj_state(remaining_tables, s);
6105
if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )
6106
{ /* Recursively expand the current partial plan */
6107
std::swap(join->best_ref[idx], *pos);
6108
if (best_extension_by_limited_search(join,
6109
remaining_tables & ~real_table_bit,
6111
current_record_count,
6116
std::swap(join->best_ref[idx], *pos);
6120
'join' is either the best partial QEP with 'search_depth' relations,
6121
or the best complete QEP so far, whichever is smaller.
6123
current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
6124
if (join->sort_by_table &&
6125
join->sort_by_table !=
6126
join->positions[join->const_tables].table->table)
6127
/* We have to make a temp table */
6128
current_read_time+= current_record_count;
6129
if ((search_depth == 1) || (current_read_time < join->best_read))
6131
memcpy(join->best_positions, join->positions,
6132
sizeof(POSITION) * (idx + 1));
6133
join->best_read= current_read_time - 0.001;
6136
restore_prev_nj_state(s);
6137
restore_prev_sj_state(remaining_tables, s);
6146
- TODO: this function is here only temporarily until 'greedy_search' is
6147
tested and accepted.
6154
find_best(JOIN *join,table_map rest_tables,uint32_t idx,double record_count,
6157
Session *session= join->session;
6158
if (session->killed)
6162
read_time+=record_count/(double) TIME_FOR_COMPARE;
6163
if (join->sort_by_table &&
6164
join->sort_by_table !=
6165
join->positions[join->const_tables].table->table)
6166
read_time+=record_count; // We have to make a temp table
6167
if (read_time < join->best_read)
6169
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
6170
join->best_read= read_time - 0.001;
6174
if (read_time+record_count/(double) TIME_FOR_COMPARE >= join->best_read)
6175
return(false); /* Found better before */
6178
double best_record_count=DBL_MAX,best_read_time=DBL_MAX;
6179
for (JOIN_TAB **pos=join->best_ref+idx ; (s=*pos) ; pos++)
6181
table_map real_table_bit=s->table->map;
6182
if ((rest_tables & real_table_bit) && !(rest_tables & s->dependent) &&
6183
(!idx|| !check_interleaving_with_nj(join->positions[idx-1].table, s)))
6185
double records, best;
6186
advance_sj_state(rest_tables, s);
6187
best_access_path(join, s, session, rest_tables, idx, record_count,
6189
records= join->positions[idx].records_read;
6190
best= join->positions[idx].read_time;
6192
Go to the next level only if there hasn't been a better key on
6193
this level! This will cut down the search for a lot simple cases!
6195
double current_record_count=record_count*records;
6196
double current_read_time=read_time+best;
6197
if (best_record_count > current_record_count ||
6198
best_read_time > current_read_time ||
6199
(idx == join->const_tables && s->table == join->sort_by_table))
6201
if (best_record_count >= current_record_count &&
6202
best_read_time >= current_read_time &&
6203
(!(s->key_dependent & rest_tables) || records < 2.0))
6205
best_record_count=current_record_count;
6206
best_read_time=current_read_time;
6208
std::swap(join->best_ref[idx], *pos);
6209
if (find_best(join,rest_tables & ~real_table_bit,idx+1,
6210
current_record_count,current_read_time))
6212
std::swap(join->best_ref[idx], *pos);
6214
restore_prev_nj_state(s);
6215
restore_prev_sj_state(rest_tables, s);
6216
if (join->select_options & SELECT_STRAIGHT_JOIN)
6217
break; // Don't test all combinations
847
6225
Find how much space the prevous read not const tables takes in cache.
849
void calc_used_field_length(Session *, JoinTable *join_tab)
6228
static void calc_used_field_length(Session *, JOIN_TAB *join_tab)
851
6230
uint32_t null_fields,blobs,fields,rec_length;
852
6231
Field **f_ptr,*field;
6232
bitset<MAX_FIELDS> *read_set= join_tab->table->read_set;
854
6234
null_fields= blobs= fields= rec_length=0;
855
6235
for (f_ptr=join_tab->table->field ; (field= *f_ptr) ; f_ptr++)
857
if (field->isReadSet())
6237
if (read_set->test(field->field_index))
859
6239
uint32_t flags=field->flags;
861
6241
rec_length+=field->pack_length();
862
6242
if (flags & BLOB_FLAG)
864
6244
if (!(flags & NOT_NULL_FLAG))
868
6248
if (null_fields)
871
6251
rec_length+=sizeof(bool);
874
uint32_t blob_length=(uint32_t) (join_tab->table->cursor->stats.mean_rec_length-
875
(join_tab->table->getRecordLength()- rec_length));
876
rec_length+= max((uint32_t)4,blob_length);
6254
uint32_t blob_length=(uint32_t) (join_tab->table->file->stats.mean_rec_length-
6255
(join_tab->table->getRecordLength()- rec_length));
6256
rec_length+=(uint32_t) cmax((uint32_t)4,blob_length);
878
6258
join_tab->used_fields= fields;
879
6259
join_tab->used_fieldlength= rec_length;
880
6260
join_tab->used_blobs= blobs;
883
StoredKey *get_store_key(Session *session,
884
optimizer::KeyUse *keyuse,
885
table_map used_tables,
886
KEY_PART_INFO *key_part,
887
unsigned char *key_buff,
890
Item_ref *key_use_val= static_cast<Item_ref *>(keyuse->getVal());
891
if (! ((~used_tables) & keyuse->getUsedTables())) // if const item
6265
cache_record_length(JOIN *join,uint32_t idx)
6268
JOIN_TAB **pos,**end;
6269
Session *session=join->session;
6271
for (pos=join->best_ref+join->const_tables,end=join->best_ref+idx ;
6275
JOIN_TAB *join_tab= *pos;
6276
if (!join_tab->used_fieldlength) /* Not calced yet */
6277
calc_used_field_length(session, join_tab);
6278
length+=join_tab->used_fieldlength;
6285
Get the number of different row combinations for subset of partial join
6289
join The join structure
6290
idx Number of tables in the partial join order (i.e. the
6291
partial join order is in join->positions[0..idx-1])
6292
found_ref Bitmap of tables for which we need to find # of distinct
6296
Given a partial join order (in join->positions[0..idx-1]) and a subset of
6297
tables within that join order (specified in found_ref), find out how many
6298
distinct row combinations of subset tables will be in the result of the
6301
This is used as follows: Suppose we have a table accessed with a ref-based
6302
method. The ref access depends on current rows of tables in found_ref.
6303
We want to count # of different ref accesses. We assume two ref accesses
6304
will be different if at least one of access parameters is different.
6305
Example: consider a query
6307
SELECT * FROM t1, t2, t3 WHERE t1.key=c1 AND t2.key=c2 AND t3.key=t1.field
6310
t1, ref access on t1.key=c1
6311
t2, ref access on t2.key=c2
6312
t3, ref access on t3.key=t1.field
6314
For t1: n_ref_scans = 1, n_distinct_ref_scans = 1
6315
For t2: n_ref_scans = records_read(t1), n_distinct_ref_scans=1
6316
For t3: n_ref_scans = records_read(t1)*records_read(t2)
6317
n_distinct_ref_scans = #records_read(t1)
6319
The reason for having this function (at least the latest version of it)
6320
is that we need to account for buffering in join execution.
6322
An edge-case example: if we have a non-first table in join accessed via
6323
ref(const) or ref(param) where there is a small number of different
6324
values of param, then the access will likely hit the disk cache and will
6325
not require any disk seeks.
6327
The proper solution would be to assume an LRU disk cache of some size,
6328
calculate probability of cache hits, etc. For now we just count
6329
identical ref accesses as one.
6332
Expected number of row combinations
6336
prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref)
6339
POSITION *pos_end= join->positions - 1;
6340
for (POSITION *pos= join->positions + idx - 1; pos != pos_end; pos--)
6342
if (pos->table->table->map & found_ref)
6344
found_ref|= pos->ref_depend_map;
6346
For the case of "t1 LEFT JOIN t2 ON ..." where t2 is a const table
6347
with no matching row we will get position[t2].records_read==0.
6348
Actually the size of output is one null-complemented row, therefore
6349
we will use value of 1 whenever we get records_read==0.
6352
- the above case can't occur if inner part of outer join has more
6353
than one table: table with no matches will not be marked as const.
6355
- Ideally we should add 1 to records_read for every possible null-
6356
complemented row. We're not doing it because: 1. it will require
6357
non-trivial code and add overhead. 2. The value of records_read
6358
is an inprecise estimate and adding 1 (or, in the worst case,
6359
#max_nested_outer_joins=64-1) will not make it any more precise.
6361
if (pos->records_read > DBL_EPSILON)
6362
found*= pos->records_read;
6370
Set up join struct according to best position.
6374
get_best_combination(JOIN *join)
6377
table_map used_tables;
6378
JOIN_TAB *join_tab,*j;
6380
uint32_t table_count;
6381
Session *session=join->session;
6383
table_count=join->tables;
6384
if (!(join->join_tab=join_tab=
6385
(JOIN_TAB*) session->alloc(sizeof(JOIN_TAB)*table_count)))
6390
used_tables= OUTER_REF_TABLE_BIT; // Outer row is already read
6391
for (j=join_tab, tablenr=0 ; tablenr < table_count ; tablenr++,j++)
6394
*j= *join->best_positions[tablenr].table;
6395
form=join->table[tablenr]=j->table;
6396
used_tables|= form->map;
6397
form->reginfo.join_tab=j;
6398
if (!*j->on_expr_ref)
6399
form->reginfo.not_exists_optimize=0; // Only with LEFT JOIN
6400
if (j->type == JT_CONST)
6401
continue; // Handled in make_join_stat..
6406
if (j->type == JT_SYSTEM)
6408
if (j->keys.is_clear_all() || !(keyuse= join->best_positions[tablenr].key))
6411
if (tablenr != join->const_tables)
6414
else if (create_ref_for_key(join, j, keyuse, used_tables))
6415
return(true); // Something went wrong
6418
for (i=0 ; i < table_count ; i++)
6419
join->map2table[join->join_tab[i].table->tablenr]=join->join_tab+i;
6420
update_depend_map(join);
6425
static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
6426
table_map used_tables)
6428
KEYUSE *keyuse=org_keyuse;
6429
Session *session= join->session;
6430
uint32_t keyparts,length,key;
6434
/* Use best key from find_best */
6437
keyinfo=table->key_info+key;
6441
uint32_t found_part_ref_or_null= 0;
6443
Calculate length for the used key
6444
Stop if there is a missing key part or when we find second key_part
6445
with KEY_OPTIMIZE_REF_OR_NULL
6449
if (!(~used_tables & keyuse->used_tables))
6451
if (keyparts == keyuse->keypart &&
6452
!(found_part_ref_or_null & keyuse->optimize))
6455
length+= keyinfo->key_part[keyuse->keypart].store_length;
6456
found_part_ref_or_null|= keyuse->optimize;
6460
} while (keyuse->table == table && keyuse->key == key);
6463
/* set up fieldref */
6464
keyinfo=table->key_info+key;
6465
j->ref.key_parts=keyparts;
6466
j->ref.key_length=length;
6467
j->ref.key=(int) key;
6468
if (!(j->ref.key_buff= (unsigned char*) session->calloc(ALIGN_SIZE(length)*2)) ||
6469
!(j->ref.key_copy= (store_key**) session->alloc((sizeof(store_key*) *
6471
!(j->ref.items= (Item**) session->alloc(sizeof(Item*)*keyparts)) ||
6472
!(j->ref.cond_guards= (bool**) session->alloc(sizeof(uint*)*keyparts)))
6476
j->ref.key_buff2=j->ref.key_buff+ALIGN_SIZE(length);
6478
j->ref.null_rejecting= 0;
6479
j->ref.disable_cache= false;
6482
store_key **ref_key= j->ref.key_copy;
6483
unsigned char *key_buff=j->ref.key_buff, *null_ref_key= 0;
6484
bool keyuse_uses_no_tables= true;
6487
for (i=0 ; i < keyparts ; keyuse++,i++)
6489
while (keyuse->keypart != i ||
6490
((~used_tables) & keyuse->used_tables))
6491
keyuse++; /* Skip other parts */
6493
uint32_t maybe_null= test(keyinfo->key_part[i].null_bit);
6494
j->ref.items[i]=keyuse->val; // Save for cond removal
6495
j->ref.cond_guards[i]= keyuse->cond_guard;
6496
if (keyuse->null_rejecting)
6497
j->ref.null_rejecting |= 1 << i;
6498
keyuse_uses_no_tables= keyuse_uses_no_tables && !keyuse->used_tables;
6499
if (!keyuse->used_tables &&
6500
!(join->select_options & SELECT_DESCRIBE))
6501
{ // Compare against constant
6502
store_key_item tmp(session, keyinfo->key_part[i].field,
6503
key_buff + maybe_null,
6504
maybe_null ? key_buff : 0,
6505
keyinfo->key_part[i].length, keyuse->val);
6506
if (session->is_fatal_error)
6511
*ref_key++= get_store_key(session,
6512
keyuse,join->const_table_map,
6513
&keyinfo->key_part[i],
6514
key_buff, maybe_null);
6516
Remember if we are going to use REF_OR_NULL
6517
But only if field _really_ can be null i.e. we force JT_REF
6518
instead of JT_REF_OR_NULL in case if field can't be null
6520
if ((keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL) && maybe_null)
6521
null_ref_key= key_buff;
6522
key_buff+=keyinfo->key_part[i].store_length;
6525
*ref_key=0; // end_marker
6526
if (j->type == JT_CONST)
6527
j->table->const_table= 1;
6528
else if (((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) != HA_NOSAME) ||
6529
keyparts != keyinfo->key_parts || null_ref_key)
6531
/* Must read with repeat */
6532
j->type= null_ref_key ? JT_REF_OR_NULL : JT_REF;
6533
j->ref.null_ref_key= null_ref_key;
6535
else if (keyuse_uses_no_tables)
6538
This happen if we are using a constant expression in the ON part
6540
SELECT * FROM a LEFT JOIN b ON b.key=30
6541
Here we should not mark the table as a 'const' as a field may
6542
have a 'normal' value or a NULL value.
6554
get_store_key(Session *session, KEYUSE *keyuse, table_map used_tables,
6555
KEY_PART_INFO *key_part, unsigned char *key_buff, uint32_t maybe_null)
6557
if (!((~used_tables) & keyuse->used_tables)) // if const item
893
6559
return new store_key_const_item(session,
894
6560
key_part->field,
895
6561
key_buff + maybe_null,
896
6562
maybe_null ? key_buff : 0,
897
6563
key_part->length,
900
else if (key_use_val->type() == Item::FIELD_ITEM ||
901
(key_use_val->type() == Item::REF_ITEM &&
902
key_use_val->ref_type() == Item_ref::OUTER_REF &&
903
(*(Item_ref**)((Item_ref*)key_use_val)->ref)->ref_type() == Item_ref::DIRECT_REF &&
904
key_use_val->real_item()->type() == Item::FIELD_ITEM))
6566
else if (keyuse->val->type() == Item::FIELD_ITEM ||
6567
(keyuse->val->type() == Item::REF_ITEM &&
6568
((Item_ref*)keyuse->val)->ref_type() == Item_ref::OUTER_REF &&
6569
(*(Item_ref**)((Item_ref*)keyuse->val)->ref)->ref_type() ==
6570
Item_ref::DIRECT_REF &&
6571
keyuse->val->real_item()->type() == Item::FIELD_ITEM))
906
6572
return new store_key_field(session,
907
6573
key_part->field,
908
6574
key_buff + maybe_null,
909
6575
maybe_null ? key_buff : 0,
910
6576
key_part->length,
911
((Item_field*) key_use_val->real_item())->field,
912
key_use_val->full_name());
6577
((Item_field*) keyuse->val->real_item())->field,
6578
keyuse->val->full_name());
914
6579
return new store_key_item(session,
915
6580
key_part->field,
916
6581
key_buff + maybe_null,
917
6582
maybe_null ? key_buff : 0,
918
6583
key_part->length,
6828
Fill in outer join related info for the execution plan structure.
6830
For each outer join operation left after simplification of the
6831
original query the function set up the following pointers in the linear
6832
structure join->join_tab representing the selected execution plan.
6833
The first inner table t0 for the operation is set to refer to the last
6834
inner table tk through the field t0->last_inner.
6835
Any inner table ti for the operation are set to refer to the first
6836
inner table ti->first_inner.
6837
The first inner table t0 for the operation is set to refer to the
6838
first inner table of the embedding outer join operation, if there is any,
6839
through the field t0->first_upper.
6840
The on expression for the outer join operation is attached to the
6841
corresponding first inner table through the field t0->on_expr_ref.
6842
Here ti are structures of the JOIN_TAB type.
6844
EXAMPLE. For the query:
6848
(t2, t3 LEFT JOIN t4 ON t3.a=t4.a)
6849
ON (t1.a=t2.a AND t1.b=t3.b)
6853
given the execution plan with the table order t1,t2,t3,t4
6854
is selected, the following references will be set;
6855
t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2]
6856
t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2],
6857
on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to
6858
*t2->on_expr_ref, while t3.a=t4.a will be attached to *t4->on_expr_ref.
6860
@param join reference to the info fully describing the query
6863
The function assumes that the simplification procedure has been
6864
already applied to the join query (see simplify_joins).
6865
This function can be called only after the execution plan
6870
make_outerjoin_info(JOIN *join)
6872
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
6874
JOIN_TAB *tab=join->join_tab+i;
6875
Table *table=tab->table;
6876
TableList *tbl= table->pos_in_table_list;
6877
TableList *embedding= tbl->embedding;
6879
if (tbl->outer_join)
6882
Table tab is the only one inner table for outer join.
6883
(Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a
6884
is in the query above.)
6886
tab->last_inner= tab->first_inner= tab;
6887
tab->on_expr_ref= &tbl->on_expr;
6888
tab->cond_equal= tbl->cond_equal;
6890
tab->first_upper= embedding->nested_join->first_nested;
6892
for ( ; embedding ; embedding= embedding->embedding)
6894
/* Ignore sj-nests: */
6895
if (!embedding->on_expr)
6897
nested_join_st *nested_join= embedding->nested_join;
6898
if (!nested_join->counter_)
6901
Table tab is the first inner table for nested_join.
6902
Save reference to it in the nested join structure.
6904
nested_join->first_nested= tab;
6905
tab->on_expr_ref= &embedding->on_expr;
6906
tab->cond_equal= tbl->cond_equal;
6907
if (embedding->embedding)
6908
tab->first_upper= embedding->embedding->nested_join->first_nested;
6910
if (!tab->first_inner)
6911
tab->first_inner= nested_join->first_nested;
6912
if (++nested_join->counter_ < nested_join->join_list.elements)
6914
/* Table tab is the last inner table for nested join. */
6915
nested_join->first_nested->last_inner= tab;
6923
make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
6925
Session *session= join->session;
6928
add_not_null_conds(join);
6929
table_map used_tables;
6930
if (cond) /* Because of QUICK_GROUP_MIN_MAX_SELECT */
6931
{ /* there may be a select without a cond. */
6932
if (join->tables > 1)
6933
cond->update_used_tables(); // Tablenr may have changed
6934
if (join->const_tables == join->tables &&
6935
session->lex->current_select->master_unit() ==
6936
&session->lex->unit) // not upper level SELECT
6937
join->const_table_map|=RAND_TABLE_BIT;
6938
{ // Check const tables
6940
make_cond_for_table(cond,
6941
join->const_table_map,
6943
for (JOIN_TAB *tab= join->join_tab+join->const_tables;
6944
tab < join->join_tab+join->tables ; tab++)
6946
if (*tab->on_expr_ref)
6948
JOIN_TAB *cond_tab= tab->first_inner;
6949
COND *tmp= make_cond_for_table(*tab->on_expr_ref,
6950
join->const_table_map,
6954
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
6957
tmp->quick_fix_field();
6958
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
6959
new Item_cond_and(cond_tab->select_cond,
6961
if (!cond_tab->select_cond)
6963
cond_tab->select_cond->quick_fix_field();
6966
if (const_cond && !const_cond->val_int())
6968
return(1); // Impossible const condition
6972
used_tables=((select->const_tables=join->const_table_map) |
6973
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
6974
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
6976
JOIN_TAB *tab=join->join_tab+i;
6978
first_inner is the X in queries like:
6979
SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X
6981
JOIN_TAB *first_inner_tab= tab->first_inner;
6982
table_map current_map= tab->table->map;
6983
bool use_quick_range=0;
6987
Following force including random expression in last table condition.
6988
It solve problem with select like SELECT * FROM t1 WHERE rand() > 0.5
6990
if (i == join->tables-1)
6991
current_map|= OUTER_REF_TABLE_BIT | RAND_TABLE_BIT;
6992
used_tables|=current_map;
6994
if (tab->type == JT_REF && tab->quick &&
6995
(uint32_t) tab->ref.key == tab->quick->index &&
6996
tab->ref.key_length < tab->quick->max_used_key_length)
6998
/* Range uses longer key; Use this instead of ref on key */
7003
tab->ref.key_parts=0; // Don't use ref key.
7004
join->best_positions[i].records_read= rows2double(tab->quick->records);
7006
We will use join cache here : prevent sorting of the first
7007
table only and sort at the end.
7009
if (i != join->const_tables && join->tables > join->const_tables + 1)
7015
tmp= make_cond_for_table(cond,used_tables,current_map, 0);
7016
if (cond && !tmp && tab->quick)
7018
if (tab->type != JT_ALL)
7021
Don't use the quick method
7022
We come here in the case where we have 'key=constant' and
7023
the test is removed by make_cond_for_table()
7031
Hack to handle the case where we only refer to a table
7032
in the ON part of an OUTER JOIN. In this case we want the code
7033
below to check if we should use 'quick' instead.
7035
tmp= new Item_int((int64_t) 1,1); // Always true
7039
if (tmp || !cond || tab->type == JT_REF || tab->type == JT_REF_OR_NULL ||
7040
tab->type == JT_EQ_REF)
7042
SQL_SELECT *sel= tab->select= ((SQL_SELECT*)
7043
session->memdup((unsigned char*) select,
7046
return(1); // End of memory
7048
If tab is an inner table of an outer join operation,
7049
add a match guard to the pushed down predicate.
7050
The guard will turn the predicate on only after
7051
the first match for outer tables is encountered.
7056
Because of QUICK_GROUP_MIN_MAX_SELECT there may be a select without
7057
a cond, so neutralize the hack above.
7059
if (!(tmp= add_found_match_trig_cond(first_inner_tab, tmp, 0)))
7061
tab->select_cond=sel->cond=tmp;
7062
/* Push condition to storage engine if this is enabled
7063
and the condition is not guarded */
7064
tab->table->file->pushed_cond= NULL;
7065
if (session->variables.engine_condition_pushdown)
7068
make_cond_for_table(tmp, current_map, current_map, 0);
7071
/* Push condition to handler */
7072
if (!tab->table->file->cond_push(push_cond))
7073
tab->table->file->pushed_cond= push_cond;
7078
tab->select_cond= sel->cond= NULL;
7080
sel->head=tab->table;
7083
/* Use quick key read if it's a constant and it's not used
7085
if (tab->needed_reg.is_clear_all() && tab->type != JT_EQ_REF
7086
&& (tab->type != JT_REF || (uint32_t) tab->ref.key == tab->quick->index))
7088
sel->quick=tab->quick; // Use value from get_quick_...
7089
sel->quick_keys.clear_all();
7090
sel->needed_reg.clear_all();
7098
uint32_t ref_key=(uint32_t) sel->head->reginfo.join_tab->ref.key+1;
7099
if (i == join->const_tables && ref_key)
7101
if (!tab->const_keys.is_clear_all() &&
7102
tab->table->reginfo.impossible_range)
7105
else if (tab->type == JT_ALL && ! use_quick_range)
7107
if (!tab->const_keys.is_clear_all() &&
7108
tab->table->reginfo.impossible_range)
7109
return(1); // Impossible range
7111
We plan to scan all rows.
7112
Check again if we should use an index.
7113
We could have used an column from a previous table in
7114
the index if we are using limit and this is the first table
7117
if ((cond && (!tab->keys.is_subset(tab->const_keys) && i > 0)) ||
7118
(!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)))
7120
/* Join with outer join condition */
7121
COND *orig_cond=sel->cond;
7122
sel->cond= and_conds(sel->cond, *tab->on_expr_ref);
7125
We can't call sel->cond->fix_fields,
7126
as it will break tab->on_expr if it's AND condition
7127
(fix_fields currently removes extra AND/OR levels).
7128
Yet attributes of the just built condition are not needed.
7129
Thus we call sel->cond->quick_fix_field for safety.
7131
if (sel->cond && !sel->cond->fixed)
7132
sel->cond->quick_fix_field();
7134
if (sel->test_quick_select(session, tab->keys,
7135
used_tables & ~ current_map,
7136
(join->select_options &
7139
join->unit->select_limit_cnt), 0,
7143
Before reporting "Impossible WHERE" for the whole query
7144
we have to check isn't it only "impossible ON" instead
7146
sel->cond=orig_cond;
7147
if (!*tab->on_expr_ref ||
7148
sel->test_quick_select(session, tab->keys,
7149
used_tables & ~ current_map,
7150
(join->select_options &
7153
join->unit->select_limit_cnt),0,
7155
return(1); // Impossible WHERE
7158
sel->cond=orig_cond;
7160
/* Fix for EXPLAIN */
7162
join->best_positions[i].records_read= (double)sel->quick->records;
7166
sel->needed_reg=tab->needed_reg;
7167
sel->quick_keys.clear_all();
7169
if (!sel->quick_keys.is_subset(tab->checked_keys) ||
7170
!sel->needed_reg.is_subset(tab->checked_keys))
7172
tab->keys=sel->quick_keys;
7173
tab->keys.merge(sel->needed_reg);
7174
tab->use_quick= (!sel->needed_reg.is_clear_all() &&
7175
(select->quick_keys.is_clear_all() ||
7177
(select->quick->records >= 100L)))) ?
7179
sel->read_tables= used_tables & ~current_map;
7181
if (i != join->const_tables && tab->use_quick != 2)
7182
{ /* Read with cache */
7184
(tmp=make_cond_for_table(cond,
7185
join->const_table_map |
7189
tab->cache.select=(SQL_SELECT*)
7190
session->memdup((unsigned char*) sel, sizeof(SQL_SELECT));
7191
tab->cache.select->cond=tmp;
7192
tab->cache.select->read_tables=join->const_table_map;
7199
Push down conditions from all on expressions.
7200
Each of these conditions are guarded by a variable
7201
that turns if off just before null complemented row for
7202
outer joins is formed. Thus, the condition from an
7203
'on expression' are guaranteed not to be checked for
7204
the null complemented row.
7207
/* First push down constant conditions from on expressions */
7208
for (JOIN_TAB *join_tab= join->join_tab+join->const_tables;
7209
join_tab < join->join_tab+join->tables ; join_tab++)
7211
if (*join_tab->on_expr_ref)
7213
JOIN_TAB *cond_tab= join_tab->first_inner;
7214
tmp= make_cond_for_table(*join_tab->on_expr_ref,
7215
join->const_table_map,
7219
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
7222
tmp->quick_fix_field();
7223
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
7224
new Item_cond_and(cond_tab->select_cond,tmp);
7225
if (!cond_tab->select_cond)
7227
cond_tab->select_cond->quick_fix_field();
7231
/* Push down non-constant conditions from on expressions */
7232
JOIN_TAB *last_tab= tab;
7233
while (first_inner_tab && first_inner_tab->last_inner == last_tab)
7236
Table tab is the last inner table of an outer join.
7237
An on expression is always attached to it.
7239
COND *on_expr= *first_inner_tab->on_expr_ref;
7241
table_map used_tables2= (join->const_table_map |
7242
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
7243
for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++)
7245
current_map= tab->table->map;
7246
used_tables2|= current_map;
7247
COND *tmp_cond= make_cond_for_table(on_expr, used_tables2,
7251
JOIN_TAB *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;
7253
First add the guards for match variables of
7254
all embedding outer join operations.
7256
if (!(tmp_cond= add_found_match_trig_cond(cond_tab->first_inner,
7261
Now add the guard turning the predicate off for
7262
the null complemented row.
7264
tmp_cond= new Item_func_trig_cond(tmp_cond,
7268
tmp_cond->quick_fix_field();
7269
/* Add the predicate to other pushed down predicates */
7270
cond_tab->select_cond= !cond_tab->select_cond ? tmp_cond :
7271
new Item_cond_and(cond_tab->select_cond,
7273
if (!cond_tab->select_cond)
7275
cond_tab->select_cond->quick_fix_field();
7278
first_inner_tab= first_inner_tab->first_upper;
1215
7287
Check if given expression uses only table fields covered by the given index
2744
9591
if (!(left_const && right_const) &&
2745
9592
args[0]->result_type() == args[1]->result_type())
2749
resolve_const_item(session, &args[1], args[0]);
2750
func->update_used_tables();
2751
change_cond_ref_to_const(session, save_list, and_father, and_father,
2754
else if (left_const)
2756
resolve_const_item(session, &args[0], args[1]);
2757
func->update_used_tables();
2758
change_cond_ref_to_const(session, save_list, and_father, and_father,
9596
resolve_const_item(session, &args[1], args[0]);
9597
func->update_used_tables();
9598
change_cond_ref_to_const(session, save_list, and_father, and_father,
9601
else if (left_const)
9603
resolve_const_item(session, &args[0], args[1]);
9604
func->update_used_tables();
9605
change_cond_ref_to_const(session, save_list, and_father, and_father,
9615
Simplify joins replacing outer joins by inner joins whenever it's
9618
The function, during a retrieval of join_list, eliminates those
9619
outer joins that can be converted into inner join, possibly nested.
9620
It also moves the on expressions for the converted outer joins
9621
and from inner joins to conds.
9622
The function also calculates some attributes for nested joins:
9626
- on_expr_dep_tables
9627
The first two attributes are used to test whether an outer join can
9628
be substituted for an inner join. The third attribute represents the
9629
relation 'to be dependent on' for tables. If table t2 is dependent
9630
on table t1, then in any evaluated execution plan table access to
9631
table t2 must precede access to table t2. This relation is used also
9632
to check whether the query contains invalid cross-references.
9633
The forth attribute is an auxiliary one and is used to calculate
9635
As the attribute dep_tables qualifies possibles orders of tables in the
9636
execution plan, the dependencies required by the straight join
9637
modifiers are reflected in this attribute as well.
9638
The function also removes all braces that can be removed from the join
9639
expression without changing its meaning.
9642
An outer join can be replaced by an inner join if the where condition
9643
or the on expression for an embedding nested join contains a conjunctive
9644
predicate rejecting null values for some attribute of the inner tables.
9648
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
9650
the predicate t2.b < 5 rejects nulls.
9651
The query is converted first to:
9653
SELECT * FROM t1 INNER JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
9655
then to the equivalent form:
9657
SELECT * FROM t1, t2 ON t2.a=t1.a WHERE t2.b < 5 AND t2.a=t1.a
9661
Similarly the following query:
9663
SELECT * from t1 LEFT JOIN (t2, t3) ON t2.a=t1.a t3.b=t1.b
9668
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b
9672
One conversion might trigger another:
9674
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a
9675
LEFT JOIN t3 ON t3.b=t2.b
9676
WHERE t3 IS NOT NULL =>
9677
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a, t3
9678
WHERE t3 IS NOT NULL AND t3.b=t2.b =>
9679
SELECT * FROM t1, t2, t3
9680
WHERE t3 IS NOT NULL AND t3.b=t2.b AND t2.a=t1.a
9683
The function removes all unnecessary braces from the expression
9684
produced by the conversions.
9687
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
9689
finally is converted to:
9691
SELECT * FROM t1, t2, t3 WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
9696
It also will remove braces from the following queries:
9698
SELECT * from (t1 LEFT JOIN t2 ON t2.a=t1.a) LEFT JOIN t3 ON t3.b=t2.b
9699
SELECT * from (t1, (t2,t3)) WHERE t1.a=t2.a AND t2.b=t3.b.
9702
The benefit of this simplification procedure is that it might return
9703
a query for which the optimizer can evaluate execution plan with more
9704
join orders. With a left join operation the optimizer does not
9705
consider any plan where one of the inner tables is before some of outer
9709
The function is implemented by a recursive procedure. On the recursive
9710
ascent all attributes are calculated, all outer joins that can be
9711
converted are replaced and then all unnecessary braces are removed.
9712
As join list contains join tables in the reverse order sequential
9713
elimination of outer joins does not require extra recursive calls.
9716
Remove all semi-joins that have are within another semi-join (i.e. have
9717
an "ancestor" semi-join nest)
9720
Here is an example of a join query with invalid cross references:
9722
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t3.a LEFT JOIN t3 ON t3.b=t1.b
9725
@param join reference to the query info
9726
@param join_list list representation of the join to be converted
9727
@param conds conditions to add on expressions for converted joins
9728
@param top true <=> conds is the where condition
9731
- The new condition, if success
9736
simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top,
9740
nested_join_st *nested_join;
9741
TableList *prev_table= 0;
9742
List_iterator<TableList> li(*join_list);
9745
Try to simplify join operations from join_list.
9746
The most outer join operation is checked for conversion first.
9748
while ((table= li++))
9750
table_map used_tables;
9751
table_map not_null_tables= (table_map) 0;
9753
if ((nested_join= table->nested_join))
9756
If the element of join_list is a nested join apply
9757
the procedure to its nested join list first.
9761
Item *expr= table->on_expr;
9763
If an on expression E is attached to the table,
9764
check all null rejected predicates in this expression.
9765
If such a predicate over an attribute belonging to
9766
an inner table of an embedded outer join is found,
9767
the outer join is converted to an inner join and
9768
the corresponding on expression is added to E.
9770
expr= simplify_joins(join, &nested_join->join_list,
9771
expr, false, in_sj || table->sj_on_expr);
9773
if (!table->prep_on_expr || expr != table->on_expr)
9777
table->on_expr= expr;
9778
table->prep_on_expr= expr->copy_andor_structure(join->session);
9781
nested_join->used_tables= (table_map) 0;
9782
nested_join->not_null_tables=(table_map) 0;
9783
conds= simplify_joins(join, &nested_join->join_list, conds, top,
9784
in_sj || table->sj_on_expr);
9785
used_tables= nested_join->used_tables;
9786
not_null_tables= nested_join->not_null_tables;
9790
if (!table->prep_on_expr)
9791
table->prep_on_expr= table->on_expr;
9792
used_tables= table->table->map;
9794
not_null_tables= conds->not_null_tables();
9797
if (table->embedding)
9799
table->embedding->nested_join->used_tables|= used_tables;
9800
table->embedding->nested_join->not_null_tables|= not_null_tables;
9803
if (!table->outer_join || (used_tables & not_null_tables))
9806
For some of the inner tables there are conjunctive predicates
9807
that reject nulls => the outer join can be replaced by an inner join.
9809
table->outer_join= 0;
9812
/* Add ON expression to the WHERE or upper-level ON condition. */
9815
conds= and_conds(conds, table->on_expr);
9816
conds->top_level_item();
9817
/* conds is always a new item as both cond and on_expr existed */
9818
assert(!conds->fixed);
9819
conds->fix_fields(join->session, &conds);
9822
conds= table->on_expr;
9823
table->prep_on_expr= table->on_expr= 0;
9831
Only inner tables of non-convertible outer joins
9832
remain with on_expr.
9836
table->dep_tables|= table->on_expr->used_tables();
9837
if (table->embedding)
9839
table->dep_tables&= ~table->embedding->nested_join->used_tables;
9841
Embedding table depends on tables used
9842
in embedded on expressions.
9844
table->embedding->on_expr_dep_tables|= table->on_expr->used_tables();
9847
table->dep_tables&= ~table->table->map;
9852
/* The order of tables is reverse: prev_table follows table */
9853
if (prev_table->straight)
9854
prev_table->dep_tables|= used_tables;
9855
if (prev_table->on_expr)
9857
prev_table->dep_tables|= table->on_expr_dep_tables;
9858
table_map prev_used_tables= prev_table->nested_join ?
9859
prev_table->nested_join->used_tables :
9860
prev_table->table->map;
9862
If on expression contains only references to inner tables
9863
we still make the inner tables dependent on the outer tables.
9864
It would be enough to set dependency only on one outer table
9865
for them. Yet this is really a rare case.
9867
if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
9868
prev_table->dep_tables|= used_tables;
9875
Flatten nested joins that can be flattened.
9876
no ON expression and not a semi-join => can be flattened.
9879
while ((table= li++))
9881
nested_join= table->nested_join;
9882
if (table->sj_on_expr && !in_sj)
9885
If this is a semi-join that is not contained within another semi-join,
9886
leave it intact (otherwise it is flattened)
9888
join->select_lex->sj_nests.push_back(table);
9890
else if (nested_join && !table->on_expr)
9893
List_iterator<TableList> it(nested_join->join_list);
9896
tbl->embedding= table->embedding;
9897
tbl->join_list= table->join_list;
9899
li.replace(nested_join->join_list);
9907
Assign each nested join structure a bit in nested_join_map.
9909
Assign each nested join structure (except "confluent" ones - those that
9910
embed only one element) a bit in nested_join_map.
9912
@param join Join being processed
9913
@param join_list List of tables
9914
@param first_unused Number of first unused bit in nested_join_map before the
9918
This function is called after simplify_joins(), when there are no
9919
redundant nested joins, #non_confluent_nested_joins <= #tables_in_join so
9920
we will not run out of bits in nested_join_map.
9923
First unused bit in nested_join_map after the call.
9926
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list,
9927
uint32_t first_unused)
9929
List_iterator<TableList> li(*join_list);
9931
while ((table= li++))
9933
nested_join_st *nested_join;
9934
if ((nested_join= table->nested_join))
9937
It is guaranteed by simplify_joins() function that a nested join
9938
that has only one child is either
9939
- a single-table view (the child is the underlying table), or
9940
- a single-table semi-join nest
9942
We don't assign bits to such sj-nests because
9943
1. it is redundant (a "sequence" of one table cannot be interleaved
9945
2. we could run out bits in nested_join_map otherwise.
9947
if (nested_join->join_list.elements != 1)
9949
/* Don't assign bits to sj-nests */
9951
nested_join->nj_map= (nested_join_map) 1 << first_unused++;
9952
first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
9957
return(first_unused);
9962
Set nested_join_st::counter=0 in all nested joins in passed list.
9964
Recursively set nested_join_st::counter=0 for all nested joins contained in
9965
the passed join_list.
9967
@param join_list List of nested joins to process. It may also contain base
9968
tables which will be ignored.
9971
static void reset_nj_counters(List<TableList> *join_list)
9973
List_iterator<TableList> li(*join_list);
9975
while ((table= li++))
9977
nested_join_st *nested_join;
9978
if ((nested_join= table->nested_join))
9980
nested_join->counter_= 0;
9981
reset_nj_counters(&nested_join->join_list);
2767
9989
Check interleaving with an inner tables of an outer join for
3585
int safe_index_read(JoinTable *tab)
10903
SemiJoinDuplicateElimination: Weed out duplicate row combinations
10906
do_sj_dups_weedout()
10910
1 The row combination is a duplicate (discard it)
10911
0 The row combination is not a duplicate (continue)
10914
int do_sj_dups_weedout(Session *session, SJ_TMP_TABLE *sjtbl)
10917
SJ_TMP_TABLE::TAB *tab= sjtbl->tabs;
10918
SJ_TMP_TABLE::TAB *tab_end= sjtbl->tabs_end;
10919
unsigned char *ptr= sjtbl->tmp_table->record[0] + 1;
10920
unsigned char *nulls_ptr= ptr;
10922
/* Put the the rowids tuple into table->record[0]: */
10924
// 1. Store the length
10925
if (((Field_varstring*)(sjtbl->tmp_table->field[0]))->length_bytes == 1)
10927
*ptr= (unsigned char)(sjtbl->rowid_len + sjtbl->null_bytes);
10932
int2store(ptr, sjtbl->rowid_len + sjtbl->null_bytes);
10936
// 2. Zero the null bytes
10937
if (sjtbl->null_bytes)
10939
memset(ptr, 0, sjtbl->null_bytes);
10940
ptr += sjtbl->null_bytes;
10943
// 3. Put the rowids
10944
for (uint32_t i=0; tab != tab_end; tab++, i++)
10946
handler *h= tab->join_tab->table->file;
10947
if (tab->join_tab->table->maybe_null && tab->join_tab->table->null_row)
10949
/* It's a NULL-complemented row */
10950
*(nulls_ptr + tab->null_byte) |= tab->null_bit;
10951
memset(ptr + tab->rowid_offset, 0, h->ref_length);
10955
/* Copy the rowid value */
10956
if (tab->join_tab->rowid_keep_flags & JOIN_TAB::CALL_POSITION)
10957
h->position(tab->join_tab->table->record[0]);
10958
memcpy(ptr + tab->rowid_offset, h->ref, h->ref_length);
10962
error= sjtbl->tmp_table->file->ha_write_row(sjtbl->tmp_table->record[0]);
10965
/* create_myisam_from_heap will generate error if needed */
10966
if (sjtbl->tmp_table->file->is_fatal_error(error, HA_CHECK_DUP) &&
10967
create_myisam_from_heap(session, sjtbl->tmp_table, sjtbl->start_recinfo,
10968
&sjtbl->recinfo, error, 1))
10970
//return (error == HA_ERR_FOUND_DUPP_KEY || error== HA_ERR_FOUND_DUPP_UNIQUE) ? 1: -1;
10978
SemiJoinDuplicateElimination: Reset the temporary table
10981
int do_sj_reset(SJ_TMP_TABLE *sj_tbl)
10983
if (sj_tbl->tmp_table)
10984
return sj_tbl->tmp_table->file->ha_delete_all_rows();
10989
Process one record of the nested loop join.
10991
This function will evaluate parts of WHERE/ON clauses that are
10992
applicable to the partial record on hand and in case of success
10993
submit this record to the next level of the nested loop.
10996
static enum_nested_loop_state
10997
evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,
11000
bool not_used_in_distinct=join_tab->not_used_in_distinct;
11001
ha_rows found_records=join->found_records;
11002
COND *select_cond= join_tab->select_cond;
11004
if (error > 0 || (join->session->is_error())) // Fatal error
11005
return NESTED_LOOP_ERROR;
11007
return NESTED_LOOP_NO_MORE_ROWS;
11008
if (join->session->killed) // Aborted by user
11010
join->session->send_kill_message();
11011
return NESTED_LOOP_KILLED; /* purecov: inspected */
11013
if (!select_cond || select_cond->val_int())
11016
There is no select condition or the attached pushed down
11017
condition is true => a match is found.
11020
while (join_tab->first_unmatched && found)
11023
The while condition is always false if join_tab is not
11024
the last inner join table of an outer join operation.
11026
JOIN_TAB *first_unmatched= join_tab->first_unmatched;
11028
Mark that a match for current outer table is found.
11029
This activates push down conditional predicates attached
11030
to the all inner tables of the outer join.
11032
first_unmatched->found= 1;
11033
for (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)
11035
if (tab->table->reginfo.not_exists_optimize)
11036
return NESTED_LOOP_NO_MORE_ROWS;
11037
/* Check all predicates that has just been activated. */
11039
Actually all predicates non-guarded by first_unmatched->found
11040
will be re-evaluated again. It could be fixed, but, probably,
11041
it's not worth doing now.
11043
if (tab->select_cond && !tab->select_cond->val_int())
11045
/* The condition attached to table tab is false */
11046
if (tab == join_tab)
11051
Set a return point if rejected predicate is attached
11052
not to the last table of the current nest level.
11054
join->return_tab= tab;
11055
return NESTED_LOOP_OK;
11060
Check whether join_tab is not the last inner table
11061
for another embedding outer join.
11063
if ((first_unmatched= first_unmatched->first_upper) &&
11064
first_unmatched->last_inner != join_tab)
11065
first_unmatched= 0;
11066
join_tab->first_unmatched= first_unmatched;
11069
JOIN_TAB *return_tab= join->return_tab;
11070
join_tab->found_match= true;
11071
if (join_tab->check_weed_out_table)
11073
int res= do_sj_dups_weedout(join->session, join_tab->check_weed_out_table);
11075
return NESTED_LOOP_ERROR;
11077
return NESTED_LOOP_OK;
11079
else if (join_tab->do_firstmatch)
11082
We should return to the join_tab->do_firstmatch after we have
11083
enumerated all the suffixes for current prefix row combination
11085
return_tab= join_tab->do_firstmatch;
11089
It was not just a return to lower loop level when one
11090
of the newly activated predicates is evaluated as false
11091
(See above join->return_tab= tab).
11093
join->examined_rows++;
11094
join->session->row_count++;
11098
enum enum_nested_loop_state rc;
11099
/* A match from join_tab is found for the current partial join. */
11100
rc= (*join_tab->next_select)(join, join_tab+1, 0);
11101
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
11103
if (return_tab < join->return_tab)
11104
join->return_tab= return_tab;
11106
if (join->return_tab < join_tab)
11107
return NESTED_LOOP_OK;
11109
Test if this was a SELECT DISTINCT query on a table that
11110
was not in the field list; In this case we can abort if
11111
we found a row, as no new rows can be added to the result.
11113
if (not_used_in_distinct && found_records != join->found_records)
11114
return NESTED_LOOP_NO_MORE_ROWS;
11117
join_tab->read_record.file->unlock_row();
11122
The condition pushed down to the table join_tab rejects all rows
11123
with the beginning coinciding with the current partial join.
11125
join->examined_rows++;
11126
join->session->row_count++;
11127
join_tab->read_record.file->unlock_row();
11129
return NESTED_LOOP_OK;
11136
Construct a NULL complimented partial join record and feed it to the next
11137
level of the nested loop. This function is used in case we have
11138
an OUTER join and no matching record was found.
11141
static enum_nested_loop_state
11142
evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab)
11145
The table join_tab is the first inner table of a outer join operation
11146
and no matches has been found for the current outer row.
11148
JOIN_TAB *last_inner_tab= join_tab->last_inner;
11149
/* Cache variables for faster loop */
11151
for ( ; join_tab <= last_inner_tab ; join_tab++)
11153
/* Change the the values of guard predicate variables. */
11154
join_tab->found= 1;
11155
join_tab->not_null_compl= 0;
11156
/* The outer row is complemented by nulls for each inner tables */
11157
restore_record(join_tab->table,s->default_values); // Make empty record
11158
join_tab->table->mark_as_null_row(); // For group by without error
11159
select_cond= join_tab->select_cond;
11160
/* Check all attached conditions for inner table rows. */
11161
if (select_cond && !select_cond->val_int())
11162
return NESTED_LOOP_OK;
11166
The row complemented by nulls might be the first row
11167
of embedding outer joins.
11168
If so, perform the same actions as in the code
11169
for the first regular outer join row above.
11173
JOIN_TAB *first_unmatched= join_tab->first_unmatched;
11174
if ((first_unmatched= first_unmatched->first_upper) &&
11175
first_unmatched->last_inner != join_tab)
11176
first_unmatched= 0;
11177
join_tab->first_unmatched= first_unmatched;
11178
if (!first_unmatched)
11180
first_unmatched->found= 1;
11181
for (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)
11183
if (tab->select_cond && !tab->select_cond->val_int())
11185
join->return_tab= tab;
11186
return NESTED_LOOP_OK;
11191
The row complemented by nulls satisfies all conditions
11192
attached to inner tables.
11193
Send the row complemented by nulls to be joined with the
11196
return (*join_tab->next_select)(join, join_tab+1, 0);
11200
static enum_nested_loop_state
11201
flush_cached_records(JOIN *join,JOIN_TAB *join_tab,bool skip_last)
11203
enum_nested_loop_state rc= NESTED_LOOP_OK;
11207
join_tab->table->null_row= 0;
11208
if (!join_tab->cache.records)
11209
return NESTED_LOOP_OK; /* Nothing to do */
11211
(void) store_record_in_cache(&join_tab->cache); // Must save this for later
11212
if (join_tab->use_quick == 2)
11214
if (join_tab->select->quick)
11215
{ /* Used quick select last. reset it */
11216
delete join_tab->select->quick;
11217
join_tab->select->quick=0;
11220
/* read through all records */
11221
if ((error=join_init_read_record(join_tab)))
11223
reset_cache_write(&join_tab->cache);
11224
return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
11227
for (JOIN_TAB *tmp=join->join_tab; tmp != join_tab ; tmp++)
11229
tmp->status=tmp->table->status;
11230
tmp->table->status=0;
11233
info= &join_tab->read_record;
11236
if (join->session->killed)
11238
join->session->send_kill_message();
11239
return NESTED_LOOP_KILLED; // Aborted by user /* purecov: inspected */
11241
SQL_SELECT *select=join_tab->select;
11242
if (rc == NESTED_LOOP_OK &&
11243
(!join_tab->cache.select || !join_tab->cache.select->skip_record()))
11246
reset_cache_read(&join_tab->cache);
11247
for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
11249
read_cached_record(join_tab);
11250
if (!select || !select->skip_record())
11253
if (!join_tab->check_weed_out_table ||
11254
!(res= do_sj_dups_weedout(join->session, join_tab->check_weed_out_table)))
11256
rc= (join_tab->next_select)(join,join_tab+1,0);
11257
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
11259
reset_cache_write(&join_tab->cache);
11264
return NESTED_LOOP_ERROR;
11268
} while (!(error=info->read_record(info)));
11271
read_cached_record(join_tab); // Restore current record
11272
reset_cache_write(&join_tab->cache);
11273
if (error > 0) // Fatal error
11274
return NESTED_LOOP_ERROR; /* purecov: inspected */
11275
for (JOIN_TAB *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
11276
tmp2->table->status=tmp2->status;
11277
return NESTED_LOOP_OK;
11280
int safe_index_read(JOIN_TAB *tab)
3588
11283
Table *table= tab->table;
3589
if ((error=table->cursor->index_read_map(table->record[0],
11284
if ((error=table->file->index_read_map(table->record[0],
3590
11285
tab->ref.key_buff,
3591
11286
make_prev_keypart_map(tab->ref.key_parts),
3592
11287
HA_READ_KEY_EXACT)))
15338
/** Allocate memory needed for other rollup functions. */
15340
bool JOIN::rollup_init()
15345
tmp_table_param.quick_group= 0; // Can't create groups in tmp table
15346
rollup.state= ROLLUP::STATE_INITED;
15349
Create pointers to the different sum function groups
15350
These are updated by rollup_make_fields()
15352
tmp_table_param.group_parts= send_group_parts;
15354
if (!(rollup.null_items= (Item_null_result**) session->alloc((sizeof(Item*) +
15356
sizeof(List<Item>) +
15357
ref_pointer_array_size)
15358
* send_group_parts )))
15361
rollup.fields= (List<Item>*) (rollup.null_items + send_group_parts);
15362
rollup.ref_pointer_arrays= (Item***) (rollup.fields + send_group_parts);
15363
ref_array= (Item**) (rollup.ref_pointer_arrays+send_group_parts);
15366
Prepare space for field list for the different levels
15367
These will be filled up in rollup_make_fields()
15369
for (i= 0 ; i < send_group_parts ; i++)
15371
rollup.null_items[i]= new (session->mem_root) Item_null_result();
15372
List<Item> *rollup_fields= &rollup.fields[i];
15373
rollup_fields->empty();
15374
rollup.ref_pointer_arrays[i]= ref_array;
15375
ref_array+= all_fields.elements;
15377
for (i= 0 ; i < send_group_parts; i++)
15379
for (j=0 ; j < fields_list.elements ; j++)
15380
rollup.fields[i].push_back(rollup.null_items[i]);
15382
List_iterator<Item> it(all_fields);
15384
while ((item= it++))
15386
order_st *group_tmp;
15387
bool found_in_group= 0;
15389
for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
15391
if (*group_tmp->item == item)
15393
item->maybe_null= 1;
15395
if (item->const_item())
15398
For ROLLUP queries each constant item referenced in GROUP BY list
15399
is wrapped up into an Item_func object yielding the same value
15400
as the constant item. The objects of the wrapper class are never
15401
considered as constant items and besides they inherit all
15402
properties of the Item_result_field class.
15403
This wrapping allows us to ensure writing constant items
15404
into temporary tables whenever the result of the ROLLUP
15405
operation has to be written into a temporary table, e.g. when
15406
ROLLUP is used together with DISTINCT in the SELECT list.
15407
Usually when creating temporary tables for a intermidiate
15408
result we do not include fields for constant expressions.
15410
Item* new_item= new Item_func_rollup_const(item);
15413
new_item->fix_fields(session, (Item **) 0);
15414
session->change_item_tree(it.ref(), new_item);
15415
for (order_st *tmp= group_tmp; tmp; tmp= tmp->next)
15417
if (*tmp->item == item)
15418
session->change_item_tree(tmp->item, new_item);
15423
if (item->type() == Item::FUNC_ITEM && !found_in_group)
15425
bool changed= false;
15426
if (change_group_ref(session, (Item_func *) item, group_list, &changed))
15429
We have to prevent creation of a field in a temporary table for
15430
an expression that contains GROUP BY attributes.
15431
Marking the expression item as 'with_sum_func' will ensure this.
15434
item->with_sum_func= 1;
15442
Fill up rollup structures with pointers to fields to use.
15444
Creates copies of item_sum items for each sum level.
15446
@param fields_arg List of all fields (hidden and real ones)
15447
@param sel_fields Pointer to selected fields
15448
@param func Store here a pointer to all fields
15452
In this case func is pointing to next not used element.
15457
bool JOIN::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields,
15460
List_iterator_fast<Item> it(fields_arg);
15461
Item *first_field= sel_fields.head();
15465
Create field lists for the different levels
15467
The idea here is to have a separate field list for each rollup level to
15468
avoid all runtime checks of which columns should be NULL.
15470
The list is stored in reverse order to get sum function in such an order
15471
in func that it makes it easy to reset them with init_sum_functions()
15473
Assuming: SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
15475
rollup.fields[0] will contain list where a,b,c is NULL
15476
rollup.fields[1] will contain list where b,c is NULL
15478
rollup.ref_pointer_array[#] points to fields for rollup.fields[#]
15480
sum_funcs_end[0] points to all sum functions
15481
sum_funcs_end[1] points to all sum functions, except grand totals
15485
for (level=0 ; level < send_group_parts ; level++)
15488
uint32_t pos= send_group_parts - level -1;
15489
bool real_fields= 0;
15491
List_iterator<Item> new_it(rollup.fields[pos]);
15492
Item **ref_array_start= rollup.ref_pointer_arrays[pos];
15493
order_st *start_group;
15495
/* Point to first hidden field */
15496
Item **ref_array= ref_array_start + fields_arg.elements-1;
15498
/* Remember where the sum functions ends for the previous level */
15499
sum_funcs_end[pos+1]= *func;
15501
/* Find the start of the group for this level */
15502
for (i= 0, start_group= group_list ;
15504
start_group= start_group->next)
15508
while ((item= it++))
15510
if (item == first_field)
15512
real_fields= 1; // End of hidden fields
15513
ref_array= ref_array_start;
15516
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
15517
(!((Item_sum*) item)->depended_from() ||
15518
((Item_sum *)item)->depended_from() == select_lex))
15522
This is a top level summary function that must be replaced with
15523
a sum function that is reset for this level.
15525
NOTE: This code creates an object which is not that nice in a
15526
sub select. Fortunately it's not common to have rollup in
15529
item= item->copy_or_same(session);
15530
((Item_sum*) item)->make_unique();
15531
*(*func)= (Item_sum*) item;
15536
/* Check if this is something that is part of this group by */
15537
order_st *group_tmp;
15538
for (group_tmp= start_group, i= pos ;
15539
group_tmp ; group_tmp= group_tmp->next, i++)
15541
if (*group_tmp->item == item)
15544
This is an element that is used by the GROUP BY and should be
15545
set to NULL in this level
15547
Item_null_result *null_item= new (session->mem_root) Item_null_result();
15550
item->maybe_null= 1; // Value will be null sometimes
15551
null_item->result_field= item->get_tmp_table_field();
15560
(void) new_it++; // Point to next item
15561
new_it.replace(item); // Replace previous
15568
sum_funcs_end[0]= *func; // Point to last function
15573
Send all rollup levels higher than the current one to the client.
15577
SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
15580
@param idx Level we are on:
15581
- 0 = Total sum level
15582
- 1 = First group changed (a)
15583
- 2 = Second group changed (a,b)
15588
1 If send_data_failed()
15591
int JOIN::rollup_send_data(uint32_t idx)
15594
for (i= send_group_parts ; i-- > idx ; )
15596
/* Get reference pointers to sum functions in place */
15597
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
15598
ref_pointer_array_size);
15599
if ((!having || having->val_int()))
15601
if (send_records < unit->select_limit_cnt && do_send_rows &&
15602
result->send_data(rollup.fields[i]))
15607
/* Restore ref_pointer_array */
15608
set_items_ref_array(current_ref_pointer_array);
15613
Write all rollup levels higher than the current one to a temp table.
15617
SELECT a, b, SUM(c) FROM t1 GROUP BY a,b WITH ROLLUP
15620
@param idx Level we are on:
15621
- 0 = Total sum level
15622
- 1 = First group changed (a)
15623
- 2 = Second group changed (a,b)
15624
@param table reference to temp table
15629
1 if write_data_failed()
15632
int JOIN::rollup_write_data(uint32_t idx, Table *table_arg)
15635
for (i= send_group_parts ; i-- > idx ; )
15637
/* Get reference pointers to sum functions in place */
15638
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
15639
ref_pointer_array_size);
15640
if ((!having || having->val_int()))
15644
List_iterator_fast<Item> it(rollup.fields[i]);
15645
while ((item= it++))
15647
if (item->type() == Item::NULL_ITEM && item->is_result_field())
15648
item->save_in_result_field(1);
15650
copy_sum_funcs(sum_funcs_end[i+1], sum_funcs_end[i]);
15651
if ((write_error= table_arg->file->ha_write_row(table_arg->record[0])))
15653
if (create_myisam_from_heap(session, table_arg,
15654
tmp_table_param.start_recinfo,
15655
&tmp_table_param.recinfo,
15661
/* Restore ref_pointer_array */
15662
set_items_ref_array(current_ref_pointer_array);
15667
clear results if there are not rows found for group
15668
(end_send_group/end_write_group)
15673
clear_tables(this);
15674
copy_fields(&tmp_table_param);
15678
Item_sum *func, **func_ptr= sum_funcs;
15679
while ((func= *(func_ptr++)))
15687
Send a description about what how the select will be done to stdout.
15690
void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
15691
bool distinct,const char *message)
15693
List<Item> field_list;
15694
List<Item> item_list;
15695
Session *session=join->session;
15696
select_result *result=join->result;
15697
Item *item_null= new Item_null();
15698
const CHARSET_INFO * const cs= system_charset_info;
15700
/* Don't log this into the slow query log */
15701
session->server_status&= ~(SERVER_QUERY_NO_INDEX_USED | SERVER_QUERY_NO_GOOD_INDEX_USED);
15702
join->unit->offset_limit_cnt= 0;
15705
NOTE: the number/types of items pushed into item_list must be in sync with
15706
EXPLAIN column types as they're "defined" in Session::send_explain_fields()
15710
item_list.push_back(new Item_int((int32_t)
15711
join->select_lex->select_number));
15712
item_list.push_back(new Item_string(join->select_lex->type,
15713
strlen(join->select_lex->type), cs));
15714
for (uint32_t i=0 ; i < 7; i++)
15715
item_list.push_back(item_null);
15716
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15717
item_list.push_back(item_null);
15719
item_list.push_back(new Item_string(message,strlen(message),cs));
15720
if (result->send_data(item_list))
15723
else if (join->select_lex == join->unit->fake_select_lex)
15726
here we assume that the query will return at least two rows, so we
15727
show "filesort" in EXPLAIN. Of course, sometimes we'll be wrong
15728
and no filesort will be actually done, but executing all selects in
15729
the UNION to provide precise EXPLAIN information will hardly be
15732
char table_name_buffer[NAME_LEN];
15735
item_list.push_back(new Item_null);
15737
item_list.push_back(new Item_string(join->select_lex->type,
15738
strlen(join->select_lex->type),
15742
Select_Lex *sl= join->unit->first_select();
15743
uint32_t len= 6, lastop= 0;
15744
memcpy(table_name_buffer, STRING_WITH_LEN("<union"));
15745
for (; sl && len + lastop + 5 < NAME_LEN; sl= sl->next_select())
15748
lastop= snprintf(table_name_buffer + len, NAME_LEN - len,
15749
"%u,", sl->select_number);
15751
if (sl || len + lastop >= NAME_LEN)
15753
memcpy(table_name_buffer + len, STRING_WITH_LEN("...>") + 1);
15759
table_name_buffer[len - 1]= '>'; // change ',' to '>'
15761
item_list.push_back(new Item_string(table_name_buffer, len, cs));
15764
item_list.push_back(new Item_string(join_type_str[JT_ALL],
15765
strlen(join_type_str[JT_ALL]),
15767
/* possible_keys */
15768
item_list.push_back(item_null);
15770
item_list.push_back(item_null);
15772
item_list.push_back(item_null);
15774
item_list.push_back(item_null);
15776
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15777
item_list.push_back(item_null);
15779
item_list.push_back(item_null);
15781
if (join->unit->global_parameters->order_list.first)
15782
item_list.push_back(new Item_string("Using filesort",
15785
item_list.push_back(new Item_string("", 0, cs));
15787
if (result->send_data(item_list))
15792
table_map used_tables=0;
15793
for (uint32_t i=0 ; i < join->tables ; i++)
15795
JOIN_TAB *tab=join->join_tab+i;
15796
Table *table=tab->table;
15797
TableList *table_list= tab->table->pos_in_table_list;
15799
char buff1[512], buff2[512], buff3[512];
15800
char keylen_str_buf[64];
15801
String extra(buff, sizeof(buff),cs);
15802
char table_name_buffer[NAME_LEN];
15803
String tmp1(buff1,sizeof(buff1),cs);
15804
String tmp2(buff2,sizeof(buff2),cs);
15805
String tmp3(buff3,sizeof(buff3),cs);
15814
item_list.push_back(new Item_uint((uint32_t)
15815
join->select_lex->select_number));
15817
item_list.push_back(new Item_string(join->select_lex->type,
15818
strlen(join->select_lex->type),
15820
if (tab->type == JT_ALL && tab->select && tab->select->quick)
15822
quick_type= tab->select->quick->get_type();
15823
if ((quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE) ||
15824
(quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT) ||
15825
(quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION))
15826
tab->type = JT_INDEX_MERGE;
15828
tab->type = JT_RANGE;
15831
if (table->derived_select_number)
15833
/* Derived table name generation */
15834
int len= snprintf(table_name_buffer, sizeof(table_name_buffer)-1,
15836
table->derived_select_number);
15837
item_list.push_back(new Item_string(table_name_buffer, len, cs));
15841
TableList *real_table= table->pos_in_table_list;
15842
item_list.push_back(new Item_string(real_table->alias,
15843
strlen(real_table->alias),
15846
/* "type" column */
15847
item_list.push_back(new Item_string(join_type_str[tab->type],
15848
strlen(join_type_str[tab->type]),
15850
/* Build "possible_keys" value and add it to item_list */
15851
if (!tab->keys.is_clear_all())
15854
for (j=0 ; j < table->s->keys ; j++)
15856
if (tab->keys.is_set(j))
15860
tmp1.append(table->key_info[j].name,
15861
strlen(table->key_info[j].name),
15862
system_charset_info);
15867
item_list.push_back(new Item_string(tmp1.ptr(),tmp1.length(),cs));
15869
item_list.push_back(item_null);
15871
/* Build "key", "key_len", and "ref" values and add them to item_list */
15872
if (tab->ref.key_parts)
15874
KEY *key_info=table->key_info+ tab->ref.key;
15875
register uint32_t length;
15876
item_list.push_back(new Item_string(key_info->name,
15877
strlen(key_info->name),
15878
system_charset_info));
15879
length= int64_t2str(tab->ref.key_length, keylen_str_buf, 10) -
15881
item_list.push_back(new Item_string(keylen_str_buf, length,
15882
system_charset_info));
15883
for (store_key **ref=tab->ref.key_copy ; *ref ; ref++)
15887
tmp2.append((*ref)->name(), strlen((*ref)->name()),
15888
system_charset_info);
15890
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15892
else if (tab->type == JT_NEXT)
15894
KEY *key_info=table->key_info+ tab->index;
15895
register uint32_t length;
15896
item_list.push_back(new Item_string(key_info->name,
15897
strlen(key_info->name),cs));
15898
length= int64_t2str(key_info->key_length, keylen_str_buf, 10) -
15900
item_list.push_back(new Item_string(keylen_str_buf,
15902
system_charset_info));
15903
item_list.push_back(item_null);
15905
else if (tab->select && tab->select->quick)
15907
tab->select->quick->add_keys_and_lengths(&tmp2, &tmp3);
15908
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15909
item_list.push_back(new Item_string(tmp3.ptr(),tmp3.length(),cs));
15910
item_list.push_back(item_null);
15914
if (table_list->schema_table && table_list->schema_table->i_s_requested_object & OPTIMIZE_I_S_TABLE)
15916
const char *tmp_buff;
15918
if (table_list->has_db_lookup_value)
15920
f_idx= table_list->schema_table->idx_field1;
15921
tmp_buff= table_list->schema_table->fields_info[f_idx].field_name;
15922
tmp2.append(tmp_buff, strlen(tmp_buff), cs);
15924
if (table_list->has_table_lookup_value)
15926
if (table_list->has_db_lookup_value)
15928
f_idx= table_list->schema_table->idx_field2;
15929
tmp_buff= table_list->schema_table->fields_info[f_idx].field_name;
15930
tmp2.append(tmp_buff, strlen(tmp_buff), cs);
15933
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15935
item_list.push_back(item_null);
15938
item_list.push_back(item_null);
15939
item_list.push_back(item_null);
15940
item_list.push_back(item_null);
15943
/* Add "rows" field to item_list. */
15944
if (table_list->schema_table)
15947
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15948
item_list.push_back(item_null);
15950
item_list.push_back(item_null);
15954
double examined_rows;
15955
if (tab->select && tab->select->quick)
15956
examined_rows= rows2double(tab->select->quick->records);
15957
else if (tab->type == JT_NEXT || tab->type == JT_ALL)
15958
examined_rows= rows2double(tab->limit ? tab->limit :
15959
tab->table->file->records());
15961
examined_rows= join->best_positions[i].records_read;
15963
item_list.push_back(new Item_int((int64_t) (uint64_t) examined_rows,
15964
MY_INT64_NUM_DECIMAL_DIGITS));
15966
/* Add "filtered" field to item_list. */
15967
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15971
f= (float) (100.0 * join->best_positions[i].records_read /
15973
item_list.push_back(new Item_float(f, 2));
15977
/* Build "Extra" field and add it to item_list. */
15978
bool key_read=table->key_read;
15979
if ((tab->type == JT_NEXT || tab->type == JT_CONST) &&
15980
table->covering_keys.is_set(tab->index))
15982
if (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT &&
15983
!((QUICK_ROR_INTERSECT_SELECT*)tab->select->quick)->need_to_fetch_row)
15987
item_list.push_back(new Item_string(tab->info,strlen(tab->info),cs));
15988
else if (tab->packed_info & TAB_INFO_HAVE_VALUE)
15990
if (tab->packed_info & TAB_INFO_USING_INDEX)
15991
extra.append(STRING_WITH_LEN("; Using index"));
15992
if (tab->packed_info & TAB_INFO_USING_WHERE)
15993
extra.append(STRING_WITH_LEN("; Using where"));
15994
if (tab->packed_info & TAB_INFO_FULL_SCAN_ON_NULL)
15995
extra.append(STRING_WITH_LEN("; Full scan on NULL key"));
15996
/* Skip initial "; "*/
15997
const char *str= extra.ptr();
15998
uint32_t len= extra.length();
16004
item_list.push_back(new Item_string(str, len, cs));
16008
uint32_t keyno= MAX_KEY;
16009
if (tab->ref.key_parts)
16010
keyno= tab->ref.key;
16011
else if (tab->select && tab->select->quick)
16012
keyno = tab->select->quick->index;
16014
if (keyno != MAX_KEY && keyno == table->file->pushed_idx_cond_keyno &&
16015
table->file->pushed_idx_cond)
16016
extra.append(STRING_WITH_LEN("; Using index condition"));
16018
if (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION ||
16019
quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT ||
16020
quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE)
16022
extra.append(STRING_WITH_LEN("; Using "));
16023
tab->select->quick->add_info_string(&extra);
16027
if (tab->use_quick == 2)
16029
/* 4 bits per 1 hex digit + terminating '\0' */
16030
char buf[MAX_KEY / 4 + 1];
16031
extra.append(STRING_WITH_LEN("; Range checked for each "
16032
"record (index map: 0x"));
16033
extra.append(tab->keys.print(buf));
16036
else if (tab->select->cond)
16038
const COND *pushed_cond= tab->table->file->pushed_cond;
16040
if (session->variables.engine_condition_pushdown && pushed_cond)
16042
extra.append(STRING_WITH_LEN("; Using where with pushed "
16044
if (session->lex->describe & DESCRIBE_EXTENDED)
16046
extra.append(STRING_WITH_LEN(": "));
16047
((COND *)pushed_cond)->print(&extra, QT_ORDINARY);
16051
extra.append(STRING_WITH_LEN("; Using where"));
16056
if (quick_type == QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX)
16057
extra.append(STRING_WITH_LEN("; Using index for group-by"));
16059
extra.append(STRING_WITH_LEN("; Using index"));
16061
if (table->reginfo.not_exists_optimize)
16062
extra.append(STRING_WITH_LEN("; Not exists"));
16064
if (quick_type == QUICK_SELECT_I::QS_TYPE_RANGE &&
16065
!(((QUICK_RANGE_SELECT*)(tab->select->quick))->mrr_flags &
16066
HA_MRR_USE_DEFAULT_IMPL))
16068
extra.append(STRING_WITH_LEN("; Using MRR"));
16071
if (table_list->schema_table &&
16072
table_list->schema_table->i_s_requested_object & OPTIMIZE_I_S_TABLE)
16074
if (!table_list->table_open_method)
16075
extra.append(STRING_WITH_LEN("; Skip_open_table"));
16076
else if (table_list->table_open_method == OPEN_FRM_ONLY)
16077
extra.append(STRING_WITH_LEN("; Open_frm_only"));
16079
extra.append(STRING_WITH_LEN("; Open_full_table"));
16080
if (table_list->has_db_lookup_value &&
16081
table_list->has_table_lookup_value)
16082
extra.append(STRING_WITH_LEN("; Scanned 0 databases"));
16083
else if (table_list->has_db_lookup_value ||
16084
table_list->has_table_lookup_value)
16085
extra.append(STRING_WITH_LEN("; Scanned 1 database"));
16087
extra.append(STRING_WITH_LEN("; Scanned all databases"));
16089
if (need_tmp_table)
16092
extra.append(STRING_WITH_LEN("; Using temporary"));
16097
extra.append(STRING_WITH_LEN("; Using filesort"));
16099
if (distinct & test_all_bits(used_tables,session->used_tables))
16100
extra.append(STRING_WITH_LEN("; Distinct"));
16102
if (tab->insideout_match_tab)
16104
extra.append(STRING_WITH_LEN("; LooseScan"));
16107
if (tab->flush_weedout_table)
16108
extra.append(STRING_WITH_LEN("; Start temporary"));
16109
else if (tab->check_weed_out_table)
16110
extra.append(STRING_WITH_LEN("; End temporary"));
16111
else if (tab->do_firstmatch)
16113
extra.append(STRING_WITH_LEN("; FirstMatch("));
16114
Table *prev_table=tab->do_firstmatch->table;
16115
if (prev_table->derived_select_number)
16117
char namebuf[NAME_LEN];
16118
/* Derived table name generation */
16119
int len= snprintf(namebuf, sizeof(namebuf)-1,
16121
prev_table->derived_select_number);
16122
extra.append(namebuf, len);
16125
extra.append(prev_table->pos_in_table_list->alias);
16126
extra.append(STRING_WITH_LEN(")"));
16129
for (uint32_t part= 0; part < tab->ref.key_parts; part++)
16131
if (tab->ref.cond_guards[part])
16133
extra.append(STRING_WITH_LEN("; Full scan on NULL key"));
16138
if (i > 0 && tab[-1].next_select == sub_select_cache)
16139
extra.append(STRING_WITH_LEN("; Using join buffer"));
16141
/* Skip initial "; "*/
16142
const char *str= extra.ptr();
16143
uint32_t len= extra.length();
16149
item_list.push_back(new Item_string(str, len, cs));
16151
// For next iteration
16152
used_tables|=table->map;
16153
if (result->send_data(item_list))
16157
for (Select_Lex_Unit *unit= join->select_lex->first_inner_unit();
16159
unit= unit->next_unit())
16161
if (mysql_explain_union(session, unit, result))
16168
bool mysql_explain_union(Session *session, Select_Lex_Unit *unit, select_result *result)
16171
Select_Lex *first= unit->first_select();
16173
for (Select_Lex *sl= first;
16175
sl= sl->next_select())
16177
// drop UNCACHEABLE_EXPLAIN, because it is for internal usage only
16178
uint8_t uncacheable= (sl->uncacheable & ~UNCACHEABLE_EXPLAIN);
16179
sl->type= (((&session->lex->select_lex)==sl)?
16180
(sl->first_inner_unit() || sl->next_select() ?
16181
"PRIMARY" : "SIMPLE"):
16183
((sl->linkage == DERIVED_TABLE_TYPE) ?
16185
((uncacheable & UNCACHEABLE_DEPENDENT) ?
16186
"DEPENDENT SUBQUERY":
16187
(uncacheable?"UNCACHEABLE SUBQUERY":
16189
((uncacheable & UNCACHEABLE_DEPENDENT) ?
16191
uncacheable?"UNCACHEABLE UNION":
16193
sl->options|= SELECT_DESCRIBE;
16195
if (unit->is_union())
16197
unit->fake_select_lex->select_number= UINT_MAX; // jost for initialization
16198
unit->fake_select_lex->type= "UNION RESULT";
16199
unit->fake_select_lex->options|= SELECT_DESCRIBE;
16200
if (!(res= unit->prepare(session, result, SELECT_NO_UNLOCK | SELECT_DESCRIBE)))
16202
res|= unit->cleanup();
16206
session->lex->current_select= first;
16207
unit->set_limit(unit->global_parameters);
16208
res= mysql_select(session, &first->ref_pointer_array,
16209
(TableList*) first->table_list.first,
16210
first->with_wild, first->item_list,
16212
first->order_list.elements +
16213
first->group_list.elements,
16214
(order_st*) first->order_list.first,
16215
(order_st*) first->group_list.first,
16217
first->options | session->options | SELECT_DESCRIBE,
16218
result, unit, first);
16220
return(res || session->is_error());
6541
16224
static void print_table_array(Session *session, String *str, TableList **table,
6542
16225
TableList **end)
added
removed
drizzled/sql_select.cc
