1
/* - mode: c; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2
* vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
4
* Copyright (C) 2008-2009 Sun Microsystems, Inc.
6
* This program is free software; you can redistribute it and/or modify
7
* it under the terms of the GNU General Public License as published by
8
* the Free Software Foundation; either version 2 of the License, or
9
* (at your option) any later version.
11
* This program is distributed in the hope that it will be useful,
12
* but WITHOUT ANY WARRANTY; without even the implied warranty of
13
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14
* GNU General Public License for more details.
16
* You should have received a copy of the GNU General Public License
17
* along with this program; if not, write to the Free Software
18
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
24
* Implementation of the Join class
26
* @defgroup Query_Optimizer Query Optimizer
35
#include <drizzled/item/cache.h>
36
#include <drizzled/item/cmpfunc.h>
37
#include <drizzled/item/copy_string.h>
38
#include <drizzled/item/uint.h>
39
#include <drizzled/cached_item.h>
40
#include <drizzled/sql_base.h>
41
#include <drizzled/sql_select.h> /* include join.h */
42
#include <drizzled/lock.h>
43
#include <drizzled/nested_join.h>
44
#include <drizzled/join.h>
45
#include <drizzled/join_cache.h>
46
#include <drizzled/show.h>
47
#include <drizzled/field/blob.h>
48
#include <drizzled/optimizer/position.h>
49
#include <drizzled/optimizer/sargable_param.h>
50
#include <drizzled/optimizer/key_use.h>
51
#include <drizzled/optimizer/range.h>
52
#include <drizzled/optimizer/sum.h>
53
#include <drizzled/optimizer/explain_plan.h>
54
#include <drizzled/optimizer/access_method_factory.h>
55
#include <drizzled/optimizer/access_method.h>
56
#include <drizzled/records.h>
57
#include <drizzled/probes.h>
58
#include <drizzled/internal/my_bit.h>
59
#include <drizzled/internal/my_sys.h>
60
#include <drizzled/internal/iocache.h>
61
#include <drizzled/plugin/storage_engine.h>
62
#include <drizzled/session.h>
63
#include <drizzled/select_result.h>
65
#include <drizzled/debug.h>
73
extern plugin::StorageEngine *heap_engine;
75
/** Declarations of static functions used in this source file. */
76
static bool make_group_fields(Join *main_join, Join *curr_join);
77
static void calc_group_buffer(Join *join, Order *group);
78
static bool alloc_group_fields(Join *join, Order *group);
79
static uint32_t cache_record_length(Join *join, uint32_t index);
80
static double prev_record_reads(Join *join, uint32_t idx, table_map found_ref);
81
static bool get_best_combination(Join *join);
82
static void set_position(Join *join,
85
optimizer::KeyUse *key);
86
static bool choose_plan(Join *join,table_map join_tables);
87
static void best_access_path(Join *join, JoinTable *s,
89
table_map remaining_tables,
93
static void optimize_straight_join(Join *join, table_map join_tables);
94
static bool greedy_search(Join *join, table_map remaining_tables, uint32_t depth, uint32_t prune_level);
95
static bool best_extension_by_limited_search(Join *join,
96
table_map remaining_tables,
101
uint32_t prune_level);
102
static uint32_t determine_search_depth(Join* join);
103
static bool make_simple_join(Join *join,Table *tmp_table);
104
static void make_outerjoin_info(Join *join);
105
static bool make_join_select(Join *join, optimizer::SqlSelect *select,COND *item);
106
static bool make_join_readinfo(Join *join);
107
static void update_depend_map(Join *join);
108
static void update_depend_map(Join *join, Order *order);
109
static Order *remove_constants(Join *join,Order *first_order,COND *cond, bool change_list, bool *simple_order);
110
static int return_zero_rows(Join *join,
115
uint64_t select_options,
118
static COND *simplify_joins(Join *join, List<TableList> *join_list, COND *conds, bool top);
119
static int remove_duplicates(Join *join,Table *entry,List<Item> &fields, Item *having);
120
static int setup_without_group(Session *session,
121
Item **ref_pointer_array,
125
List<Item> &all_fields,
129
bool *hidden_group_fields);
130
static bool make_join_statistics(Join *join, TableList *leaves, COND *conds, DYNAMIC_ARRAY *keyuse);
131
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused);
132
static Table *get_sort_by_table(Order *a, Order *b,TableList *tables);
133
static void reset_nj_counters(List<TableList> *join_list);
134
static bool test_if_subpart(Order *a,Order *b);
135
static void restore_prev_nj_state(JoinTable *last);
136
static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab);
137
static void free_blobs(Field **ptr); /* Rename this method...conflicts with another in global namespace... */
139
Join::Join(Session *session_arg,
140
List<Item> &fields_arg,
141
uint64_t select_options_arg,
142
select_result *result_arg) :
154
sort_and_group(false),
158
no_field_update(false),
160
resume_nested_loop(false),
161
no_const_tables(false),
162
select_distinct(false),
163
group_optimized_away(false),
167
skip_sort_order(false),
171
hidden_group_fields(false),
173
found_const_table_map(0),
180
fetch_limit(HA_POS_ERROR),
181
session(session_arg),
182
fields_list(fields_arg),
187
exec_tmp_table1(NULL),
188
exec_tmp_table2(NULL),
193
having_history(NULL),
194
select_options(select_options_arg),
196
lock(session_arg->lock),
198
all_fields(fields_arg),
202
ref_pointer_array(NULL),
207
ref_pointer_array_size(0),
208
zero_result_cause(NULL),
211
join_tab_reexec(NULL)
213
select_distinct= test(select_options & SELECT_DISTINCT);
214
if (&fields_list != &fields_arg) /* only copy if not same*/
215
fields_list= fields_arg;
216
memset(&keyuse, 0, sizeof(keyuse));
217
tmp_table_param.init();
218
tmp_table_param.end_write_records= HA_POS_ERROR;
219
rollup.setState(Rollup::STATE_NONE);
223
* This method is currently only used when a subselect EXPLAIN is performed.
224
* I pulled out the init() method and have simply reset the values to what
225
* was previously in the init() method. See the note about the hack in
228
void Join::reset(Session *session_arg,
229
List<Item> &fields_arg,
230
uint64_t select_options_arg,
231
select_result *result_arg)
244
sort_and_group= false;
248
no_field_update= false;
250
resume_nested_loop= false;
251
no_const_tables= false;
252
select_distinct= false;
253
group_optimized_away= false;
257
skip_sort_order= false;
261
hidden_group_fields= false;
263
found_const_table_map= 0;
270
fetch_limit= HA_POS_ERROR;
271
session= session_arg;
272
fields_list= fields_arg;
277
exec_tmp_table1= NULL;
278
exec_tmp_table2= NULL;
283
having_history= NULL;
284
select_options= select_options_arg;
286
lock= session_arg->lock;
288
all_fields= fields_arg;
292
ref_pointer_array= NULL;
297
ref_pointer_array_size= 0;
298
zero_result_cause= NULL;
301
join_tab_reexec= NULL;
302
select_distinct= test(select_options & SELECT_DISTINCT);
303
if (&fields_list != &fields_arg) /* only copy if not same*/
304
fields_list= fields_arg;
305
memset(&keyuse, 0, sizeof(keyuse));
306
tmp_table_param.init();
307
tmp_table_param.end_write_records= HA_POS_ERROR;
308
rollup.setState(Rollup::STATE_NONE);
311
bool Join::is_top_level_join() const
313
return (unit == &session->getLex()->unit && (unit->fake_select_lex == 0 ||
314
select_lex == unit->fake_select_lex));
318
Prepare of whole select (including sub queries in future).
321
Add check of calculation of GROUP functions and fields:
322
SELECT COUNT(*)+table.col1 from table1;
329
int Join::prepare(Item ***rref_pointer_array,
330
TableList *tables_init,
337
Select_Lex *select_lex_arg,
338
Select_Lex_Unit *unit_arg)
340
// to prevent double initialization on EXPLAIN
346
group_list= group_init;
348
tables_list= tables_init;
349
select_lex= select_lex_arg;
350
select_lex->join= this;
351
join_list= &select_lex->top_join_list;
352
union_part= unit_arg->is_union();
354
session->getLex()->current_select->is_item_list_lookup= 1;
356
If we have already executed SELECT, then it have not sense to prevent
357
its table from update (see unique_table())
359
if (session->derived_tables_processing)
360
select_lex->exclude_from_table_unique_test= true;
362
/* Check that all tables, fields, conds and order are ok */
364
if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
365
setup_tables_and_check_access(session, &select_lex->context, join_list,
366
tables_list, &select_lex->leaf_tables,
372
TableList *table_ptr;
373
for (table_ptr= select_lex->leaf_tables;
375
table_ptr= table_ptr->next_leaf)
381
if (setup_wild(session, fields_list, &all_fields, wild_num) ||
382
select_lex->setup_ref_array(session, og_num) ||
383
setup_fields(session, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ,
385
setup_without_group(session, (*rref_pointer_array), tables_list,
386
select_lex->leaf_tables, fields_list,
387
all_fields, &conds, order, group_list,
388
&hidden_group_fields))
391
ref_pointer_array= *rref_pointer_array;
395
nesting_map save_allow_sum_func= session->getLex()->allow_sum_func;
396
session->setWhere("having clause");
397
session->getLex()->allow_sum_func|= 1 << select_lex_arg->nest_level;
398
select_lex->having_fix_field= 1;
399
bool having_fix_rc= (!having->fixed &&
400
(having->fix_fields(session, &having) ||
401
having->check_cols(1)));
402
select_lex->having_fix_field= 0;
403
if (having_fix_rc || session->is_error())
405
session->getLex()->allow_sum_func= save_allow_sum_func;
409
Item_subselect *subselect;
410
Item_in_subselect *in_subs= NULL;
412
Are we in a subquery predicate?
413
TODO: the block below will be executed for every PS execution without need.
415
if ((subselect= select_lex->master_unit()->item))
417
if (subselect->substype() == Item_subselect::IN_SUBS)
418
in_subs= (Item_in_subselect*)subselect;
421
bool do_materialize= true;
423
Check if the subquery predicate can be executed via materialization.
424
The required conditions are:
425
1. Subquery predicate is an IN/=ANY subq predicate
426
2. Subquery is a single SELECT (not a UNION)
427
3. Subquery is not a table-less query. In this case there is no
428
point in materializing.
429
4. Subquery predicate is a top-level predicate
430
(this implies it is not negated)
431
TODO: this is a limitation that should be lifeted once we
432
implement correct NULL semantics (WL#3830)
433
5. Subquery is non-correlated
435
This is an overly restrictive condition. It can be extended to:
436
(Subquery is non-correlated ||
437
Subquery is correlated to any query outer to IN predicate ||
438
(Subquery is correlated to the immediate outer query &&
439
Subquery !contains {GROUP BY, ORDER BY [LIMIT],
440
aggregate functions) && subquery predicate is not under "NOT IN"))
441
6. No execution method was already chosen (by a prepared statement).
443
(*) The subquery must be part of a SELECT statement. The current
444
condition also excludes multi-table update statements.
446
We have to determine whether we will perform subquery materialization
447
before calling the IN=>EXISTS transformation, so that we know whether to
448
perform the whole transformation or only that part of it which wraps
449
Item_in_subselect in an Item_in_optimizer.
451
if (do_materialize &&
453
!select_lex->master_unit()->first_select()->next_select() && // 2
454
select_lex->master_unit()->first_select()->leaf_tables && // 3
455
session->getLex()->sql_command == SQLCOM_SELECT) // *
457
if (in_subs->is_top_level_item() && // 4
458
!in_subs->is_correlated && // 5
459
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
460
in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
463
Item_subselect::trans_res trans_res;
464
if ((trans_res= subselect->select_transformer(this)) !=
465
Item_subselect::RES_OK)
467
return((trans_res == Item_subselect::RES_ERROR));
476
for (ord= order; ord; ord= ord->next)
478
Item *item= *ord->item;
479
if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
480
item->split_sum_func(session, ref_pointer_array, all_fields);
484
if (having && having->with_sum_func)
485
having->split_sum_func(session, ref_pointer_array, all_fields,
487
if (select_lex->inner_sum_func_list)
489
Item_sum *end=select_lex->inner_sum_func_list;
490
Item_sum *item_sum= end;
493
item_sum= item_sum->next;
494
item_sum->split_sum_func(session, ref_pointer_array,
495
all_fields, item_sum->ref_by, false);
496
} while (item_sum != end);
499
if (select_lex->inner_refs_list.elements &&
500
fix_inner_refs(session, all_fields, select_lex, ref_pointer_array))
504
Check if there are references to un-aggregated columns when computing
505
aggregate functions with implicit grouping (there is no GROUP BY).
507
MODE_ONLY_FULL_GROUP_BY is enabled here by default
510
select_lex->full_group_by_flag.test(NON_AGG_FIELD_USED) &&
511
select_lex->full_group_by_flag.test(SUM_FUNC_USED))
513
my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
514
ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
518
/* Caclulate the number of groups */
520
for (Order *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
528
* The below will create the new table for
529
* CREATE TABLE ... SELECT
531
* @see create_table_from_items() in drizzled/sql_insert.cc
533
if (result && result->prepare(fields_list, unit_arg))
536
/* Init join struct */
537
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
538
ref_pointer_array_size= all_fields.elements*sizeof(Item*);
539
this->group= group_list != 0;
542
#ifdef RESTRICTED_GROUP
543
if (sum_func_count && !group_list && (func_count || field_count))
545
my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
549
if (select_lex->olap == ROLLUP_TYPE && rollup_init())
552
if (alloc_func_list())
559
Remove the predicates pushed down into the subquery
562
Join::remove_subq_pushed_predicates()
563
where IN Must be NULL
564
OUT The remaining WHERE condition, or NULL
567
Given that this join will be executed using (unique|index)_subquery,
568
without "checking NULL", remove the predicates that were pushed down
571
If the subquery compares scalar values, we can remove the condition that
572
was wrapped into trig_cond (it will be checked when needed by the subquery
575
If the subquery compares row values, we need to keep the wrapped
576
equalities in the WHERE clause: when the left (outer) tuple has both NULL
577
and non-NULL values, we'll do a full table scan and will rely on the
578
equalities corresponding to non-NULL parts of left tuple to filter out
579
non-matching records.
581
TODO: We can remove the equalities that will be guaranteed to be true by the
582
fact that subquery engine will be using index lookup. This must be done only
583
for cases where there are no conversion errors of significance, e.g. 257
584
that is searched in a byte. But this requires homogenization of the return
585
codes of all Field*::store() methods.
587
void Join::remove_subq_pushed_predicates(Item **where)
589
if (conds->type() == Item::FUNC_ITEM &&
590
((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
591
((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
592
((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
593
test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
594
((Item_func *)conds)->arguments()[0]))
602
global select optimisation.
605
error code saved in field 'error'
614
// to prevent double initialization on EXPLAIN
619
session->set_proc_info("optimizing");
620
row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
621
unit->select_limit_cnt);
622
/* select_limit is used to decide if we are likely to scan the whole table */
623
select_limit= unit->select_limit_cnt;
624
if (having || (select_options & OPTION_FOUND_ROWS))
625
select_limit= HA_POS_ERROR;
626
do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
627
// Ignore errors of execution if option IGNORE present
628
if (session->getLex()->ignore)
629
session->getLex()->current_select->no_error= 1;
631
#ifdef HAVE_REF_TO_FIELDS // Not done yet
632
/* Add HAVING to WHERE if possible */
633
if (having && !group_list && !sum_func_count)
640
else if ((conds=new Item_cond_and(conds,having)))
643
Item_cond_and can't be fixed after creation, so we do not check
646
conds->fix_fields(session, &conds);
647
conds->change_ref_to_fields(session, tables_list);
648
conds->top_level_item();
654
/* Convert all outer joins to inner joins if possible */
655
conds= simplify_joins(this, join_list, conds, true);
656
build_bitmap_for_nested_joins(join_list, 0);
658
conds= optimize_cond(this, conds, join_list, &cond_value);
659
if (session->is_error())
666
having= optimize_cond(this, having, join_list, &having_value);
667
if (session->is_error())
672
if (select_lex->where)
673
select_lex->cond_value= cond_value;
674
if (select_lex->having)
675
select_lex->having_value= having_value;
677
if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
678
(!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
679
{ /* Impossible cond */
680
zero_result_cause= having_value == Item::COND_FALSE ?
681
"Impossible HAVING" : "Impossible WHERE";
683
goto setup_subq_exit;
687
/* Optimize count(*), cmin() and cmax() */
688
if (tables_list && tmp_table_param.sum_func_count && ! group_list)
692
optimizer::sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
693
to the WHERE conditions,
694
or 1 if all items were resolved,
695
or 0, or an error number HA_ERR_...
697
if ((res= optimizer::sum_query(select_lex->leaf_tables, all_fields, conds)))
699
if (res == HA_ERR_KEY_NOT_FOUND)
701
zero_result_cause= "No matching min/max row";
703
goto setup_subq_exit;
712
zero_result_cause= "No matching min/max row";
714
goto setup_subq_exit;
716
zero_result_cause= "Select tables optimized away";
717
tables_list= 0; // All tables resolved
718
const_tables= tables;
720
Extract all table-independent conditions and replace the WHERE
721
clause with them. All other conditions were computed by optimizer::sum_query
722
and the MIN/MAX/COUNT function(s) have been replaced by constants,
723
so there is no need to compute the whole WHERE clause again.
724
Notice that make_cond_for_table() will always succeed to remove all
725
computed conditions, because optimizer::sum_query() is applicable only to
727
Preserve conditions for EXPLAIN.
729
if (conds && !(session->getLex()->describe & DESCRIBE_EXTENDED))
731
COND *table_independent_conds= make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
732
conds= table_independent_conds;
734
goto setup_subq_exit;
742
error= -1; // Error is sent to client
743
sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
745
/* Calculate how to do the join */
746
session->set_proc_info("statistics");
747
if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
748
session->is_fatal_error)
753
/* Remove distinct if only const tables */
754
select_distinct= select_distinct && (const_tables != tables);
755
session->set_proc_info("preparing");
756
if (result->initialize_tables(this))
758
return 1; // error == -1
760
if (const_table_map != found_const_table_map &&
761
!(select_options & SELECT_DESCRIBE) &&
763
!(conds->used_tables() & RAND_TABLE_BIT) ||
764
select_lex->master_unit() == &session->getLex()->unit)) // upper level SELECT
766
zero_result_cause= "no matching row in const table";
767
goto setup_subq_exit;
769
if (!(session->options & OPTION_BIG_SELECTS) &&
770
best_read > (double) session->variables.max_join_size &&
771
!(select_options & SELECT_DESCRIBE))
773
my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
777
if (const_tables && !(select_options & SELECT_NO_UNLOCK))
778
session->unlockSomeTables(table, const_tables);
779
if (!conds && outer_join)
781
/* Handle the case where we have an OUTER JOIN without a WHERE */
782
conds=new Item_int((int64_t) 1,1); // Always true
784
select= optimizer::make_select(*table, const_table_map,
785
const_table_map, conds, 1, &error);
792
reset_nj_counters(join_list);
793
make_outerjoin_info(this);
796
Among the equal fields belonging to the same multiple equality
797
choose the one that is to be retrieved first and substitute
798
all references to these in where condition for a reference for
803
conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
804
conds->update_used_tables();
808
Permorm the the optimization on fields evaluation mentioned above
809
for all on expressions.
811
for (JoinTable *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
813
if (*tab->on_expr_ref)
815
*tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
818
(*tab->on_expr_ref)->update_used_tables();
822
if (conds &&!outer_join && const_table_map != found_const_table_map &&
823
(select_options & SELECT_DESCRIBE) &&
824
select_lex->master_unit() == &session->getLex()->unit) // upper level SELECT
826
conds=new Item_int((int64_t) 0,1); // Always false
829
if (make_join_select(this, select, conds))
832
"Impossible WHERE noticed after reading const tables";
833
goto setup_subq_exit;
836
error= -1; /* if goto err */
838
/* Optimize distinct away if possible */
840
Order *org_order= order;
841
order= remove_constants(this, order,conds,1, &simple_order);
842
if (session->is_error())
849
If we are using ORDER BY NULL or ORDER BY const_expression,
850
return result in any order (even if we are using a GROUP BY)
852
if (!order && org_order)
856
Check if we can optimize away GROUP BY/DISTINCT.
857
We can do that if there are no aggregate functions, the
858
fields in DISTINCT clause (if present) and/or columns in GROUP BY
859
(if present) contain direct references to all key parts of
860
an unique index (in whatever order) and if the key parts of the
861
unique index cannot contain NULLs.
862
Note that the unique keys for DISTINCT and GROUP BY should not
863
be the same (as long as they are unique).
865
The FROM clause must contain a single non-constant table.
867
if (tables - const_tables == 1 && (group_list || select_distinct) &&
868
! tmp_table_param.sum_func_count &&
869
(! join_tab[const_tables].select ||
870
! join_tab[const_tables].select->quick ||
871
join_tab[const_tables].select->quick->get_type() !=
872
optimizer::QuickSelectInterface::QS_TYPE_GROUP_MIN_MAX))
874
if (group_list && list_contains_unique_index(join_tab[const_tables].table, find_field_in_order_list, (void *) group_list))
877
We have found that grouping can be removed since groups correspond to
878
only one row anyway, but we still have to guarantee correct result
879
order. The line below effectively rewrites the query from GROUP BY
880
<fields> to ORDER BY <fields>. There are two exceptions:
881
- if skip_sort_order is set (see above), then we can simply skip
883
- we can only rewrite ORDER BY if the ORDER BY fields are 'compatible'
884
with the GROUP BY ones, i.e. either one is a prefix of another.
885
We only check if the ORDER BY is a prefix of GROUP BY. In this case
886
test_if_subpart() copies the ASC/DESC attributes from the original
888
If GROUP BY is a prefix of order_st BY, then it is safe to leave
891
if (! order || test_if_subpart(group_list, order))
892
order= skip_sort_order ? 0 : group_list;
894
If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
895
rewritten to IGNORE INDEX FOR order_st BY(fields).
897
join_tab->table->keys_in_use_for_order_by=
898
join_tab->table->keys_in_use_for_group_by;
902
if (select_distinct &&
903
list_contains_unique_index(join_tab[const_tables].table,
904
find_field_in_item_list,
905
(void *) &fields_list))
910
if (group_list || tmp_table_param.sum_func_count)
912
if (! hidden_group_fields && rollup.getState() == Rollup::STATE_NONE)
915
else if (select_distinct && tables - const_tables == 1)
918
We are only using one table. In this case we change DISTINCT to a
920
- The GROUP BY can be done through indexes (no sort) and the order_st
921
BY only uses selected fields.
922
(In this case we can later optimize away GROUP BY and order_st BY)
923
- We are scanning the whole table without LIMIT
925
- We are using CALC_FOUND_ROWS
926
- We are using an ORDER BY that can't be optimized away.
928
We don't want to use this optimization when we are using LIMIT
929
because in this case we can just create a temporary table that
930
holds LIMIT rows and stop when this table is full.
932
JoinTable *tab= &join_tab[const_tables];
933
bool all_order_fields_used;
935
skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
936
&tab->table->keys_in_use_for_order_by);
937
if ((group_list=create_distinct_group(session, select_lex->ref_pointer_array,
938
order, fields_list, all_fields,
939
&all_order_fields_used)))
941
bool skip_group= (skip_sort_order &&
942
test_if_skip_sort_order(tab, group_list, select_limit, 1,
943
&tab->table->keys_in_use_for_group_by) != 0);
944
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
945
if ((skip_group && all_order_fields_used) ||
946
select_limit == HA_POS_ERROR ||
947
(order && !skip_sort_order))
949
/* Change DISTINCT to GROUP BY */
952
if (all_order_fields_used)
954
if (order && skip_sort_order)
957
Force MySQL to read the table in sorted order to get result in
960
tmp_table_param.quick_group=0;
964
group=1; // For end_write_group
969
else if (session->is_fatal_error) // End of memory
974
Order *old_group_list;
975
group_list= remove_constants(this, (old_group_list= group_list), conds,
976
rollup.getState() == Rollup::STATE_NONE,
978
if (session->is_error())
983
if (old_group_list && !group_list)
986
if (!group_list && group)
988
order=0; // The output has only one row
990
select_distinct= 0; // No need in distinct for 1 row
991
group_optimized_away= 1;
994
calc_group_buffer(this, group_list);
995
send_group_parts= tmp_table_param.group_parts; /* Save org parts */
997
if (test_if_subpart(group_list, order) ||
998
(!group_list && tmp_table_param.sum_func_count))
1001
// Can't use sort on head table if using row cache
1011
Check if we need to create a temporary table.
1012
This has to be done if all tables are not already read (const tables)
1013
and one of the following conditions holds:
1014
- We are using DISTINCT (simple distinct's are already optimized away)
1015
- We are using an ORDER BY or GROUP BY on fields not in the first table
1016
- We are using different ORDER BY and GROUP BY orders
1017
- The user wants us to buffer the result.
1019
need_tmp= (const_tables != tables &&
1020
((select_distinct || !simple_order || !simple_group) ||
1021
(group_list && order) ||
1022
test(select_options & OPTION_BUFFER_RESULT)));
1024
// No cache for MATCH == 'Don't use join buffering when we use MATCH'.
1025
if (make_join_readinfo(this))
1028
/* Create all structures needed for materialized subquery execution. */
1029
if (setup_subquery_materialization())
1032
/* Cache constant expressions in WHERE, HAVING, ON clauses. */
1033
cache_const_exprs();
1036
is this simple IN subquery?
1038
if (!group_list && !order &&
1039
unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
1040
tables == 1 && conds &&
1046
if (join_tab[0].type == AM_EQ_REF && join_tab[0].ref.items[0]->name == in_left_expr_name)
1048
remove_subq_pushed_predicates(&where);
1049
save_index_subquery_explain_info(join_tab, where);
1050
join_tab[0].type= AM_UNIQUE_SUBQUERY;
1052
return(unit->item->change_engine(new subselect_uniquesubquery_engine(session, join_tab, unit->item, where)));
1054
else if (join_tab[0].type == AM_REF &&
1055
join_tab[0].ref.items[0]->name == in_left_expr_name)
1057
remove_subq_pushed_predicates(&where);
1058
save_index_subquery_explain_info(join_tab, where);
1059
join_tab[0].type= AM_INDEX_SUBQUERY;
1061
return(unit->item->change_engine(new subselect_indexsubquery_engine(session, join_tab, unit->item, where, NULL, 0)));
1064
else if (join_tab[0].type == AM_REF_OR_NULL &&
1065
join_tab[0].ref.items[0]->name == in_left_expr_name &&
1066
having->name == in_having_cond)
1068
join_tab[0].type= AM_INDEX_SUBQUERY;
1070
conds= remove_additional_cond(conds);
1071
save_index_subquery_explain_info(join_tab, conds);
1072
return(unit->item->change_engine(new subselect_indexsubquery_engine(session, join_tab, unit->item, conds, having, 1)));
1077
Need to tell handlers that to play it safe, it should fetch all
1078
columns of the primary key of the tables: this is because MySQL may
1079
build row pointers for the rows, and for all columns of the primary key
1080
the read set has not necessarily been set by the server code.
1082
if (need_tmp || select_distinct || group_list || order)
1084
for (uint32_t i = const_tables; i < tables; i++)
1085
join_tab[i].table->prepare_for_position();
1088
if (const_tables != tables)
1091
Because filesort always does a full table scan or a quick range scan
1092
we must add the removed reference to the select for the table.
1093
We only need to do this when we have a simple_order or simple_group
1094
as in other cases the join is done before the sort.
1096
if ((order || group_list) &&
1097
(join_tab[const_tables].type != AM_ALL) &&
1098
(join_tab[const_tables].type != AM_REF_OR_NULL) &&
1099
((order && simple_order) || (group_list && simple_group)))
1101
if (add_ref_to_table_cond(session,&join_tab[const_tables])) {
1106
if (!(select_options & SELECT_BIG_RESULT) &&
1109
!test_if_skip_sort_order(&join_tab[const_tables], group_list,
1110
unit->select_limit_cnt, 0,
1111
&join_tab[const_tables].table->
1112
keys_in_use_for_group_by))) ||
1114
tmp_table_param.quick_group)
1116
need_tmp=1; simple_order=simple_group=0; // Force tmp table without sort
1121
Force using of tmp table if sorting by a SP or UDF function due to
1122
their expensive and probably non-deterministic nature.
1124
for (Order *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
1126
Item *item= *tmp_order->item;
1127
if (item->is_expensive())
1129
/* Force tmp table without sort */
1130
need_tmp=1; simple_order=simple_group=0;
1138
if (select_options & SELECT_DESCRIBE)
1146
The loose index scan access method guarantees that all grouping or
1147
duplicate row elimination (for distinct) is already performed
1148
during data retrieval, and that all MIN/MAX functions are already
1149
computed for each group. Thus all MIN/MAX functions should be
1150
treated as regular functions, and there is no need to perform
1151
grouping in the main execution loop.
1152
Notice that currently loose index scan is applicable only for
1153
single table queries, thus it is sufficient to test only the first
1154
join_tab element of the plan for its access method.
1156
if (join_tab->is_using_loose_index_scan())
1157
tmp_table_param.precomputed_group_by= true;
1159
/* Create a tmp table if distinct or if the sort is too complicated */
1162
session->set_proc_info("Creating tmp table");
1164
init_items_ref_array();
1166
tmp_table_param.hidden_field_count= (all_fields.elements -
1167
fields_list.elements);
1168
Order *tmp_group= (((not simple_group) or not (getDebug().test(debug::NO_KEY_GROUP))) ? group_list : (Order*) 0);
1171
Pushing LIMIT to the temporary table creation is not applicable
1172
when there is ORDER BY or GROUP BY or there is no GROUP BY, but
1173
there are aggregate functions, because in all these cases we need
1176
ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
1178
!session->getLex()->current_select->with_sum_func) ?
1179
select_limit : HA_POS_ERROR;
1181
if (!(exec_tmp_table1=
1182
create_tmp_table(session, &tmp_table_param, all_fields,
1184
group_list ? 0 : select_distinct,
1185
group_list && simple_group,
1194
We don't have to store rows in temp table that doesn't match HAVING if:
1195
- we are sorting the table and writing complete group rows to the
1197
- We are using DISTINCT without resolving the distinct as a GROUP BY
1200
If having is not handled here, it will be checked before the row
1201
is sent to the client.
1203
if (tmp_having && (sort_and_group || (exec_tmp_table1->distinct && !group_list)))
1206
/* if group or order on first table, sort first */
1207
if (group_list && simple_group)
1209
session->set_proc_info("Sorting for group");
1210
if (create_sort_index(session, this, group_list,
1211
HA_POS_ERROR, HA_POS_ERROR, false) ||
1212
alloc_group_fields(this, group_list) ||
1213
make_sum_func_list(all_fields, fields_list, 1) ||
1214
setup_sum_funcs(session, sum_funcs))
1222
if (make_sum_func_list(all_fields, fields_list, 0) ||
1223
setup_sum_funcs(session, sum_funcs))
1228
if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
1230
session->set_proc_info("Sorting for order");
1231
if (create_sort_index(session, this, order,
1232
HA_POS_ERROR, HA_POS_ERROR, true))
1241
Optimize distinct when used on some of the tables
1242
SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
1243
In this case we can stop scanning t2 when we have found one t1.a
1246
if (exec_tmp_table1->distinct)
1248
table_map used_tables= session->used_tables;
1249
JoinTable *last_join_tab= join_tab+tables-1;
1252
if (used_tables & last_join_tab->table->map)
1254
last_join_tab->not_used_in_distinct=1;
1255
} while (last_join_tab-- != join_tab);
1256
/* Optimize "select distinct b from t1 order by key_part_1 limit #" */
1257
if (order && skip_sort_order)
1259
/* Should always succeed */
1260
if (test_if_skip_sort_order(&join_tab[const_tables],
1261
order, unit->select_limit_cnt, 0,
1262
&join_tab[const_tables].table->
1263
keys_in_use_for_order_by))
1269
If this join belongs to an uncacheable subquery save
1272
if (select_lex->uncacheable.any() &&
1273
! is_top_level_join() &&
1274
init_save_join_tab())
1284
/* Even with zero matching rows, subqueries in the HAVING clause
1285
may need to be evaluated if there are aggregate functions in the query.
1287
if (setup_subquery_materialization())
1294
Restore values in temporary join.
1296
void Join::restore_tmp()
1298
memcpy(tmp_join, this, (size_t) sizeof(Join));
1303
unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1304
select_lex->offset_limit->val_uint() :
1309
if (exec_tmp_table1)
1311
exec_tmp_table1->cursor->extra(HA_EXTRA_RESET_STATE);
1312
exec_tmp_table1->cursor->ha_delete_all_rows();
1313
exec_tmp_table1->free_io_cache();
1314
exec_tmp_table1->filesort_free_buffers();
1316
if (exec_tmp_table2)
1318
exec_tmp_table2->cursor->extra(HA_EXTRA_RESET_STATE);
1319
exec_tmp_table2->cursor->ha_delete_all_rows();
1320
exec_tmp_table2->free_io_cache();
1321
exec_tmp_table2->filesort_free_buffers();
1324
set_items_ref_array(items0);
1327
memcpy(join_tab, join_tab_save, sizeof(JoinTable) * tables);
1332
/* Reset of sum functions */
1335
Item_sum *func, **func_ptr= sum_funcs;
1336
while ((func= *(func_ptr++)))
1344
@brief Save the original join layout
1346
@details Saves the original join layout so it can be reused in
1347
re-execution and for EXPLAIN.
1349
@return Operation status
1351
@retval 1 error occurred.
1353
bool Join::init_save_join_tab()
1355
if (!(tmp_join= (Join*)session->getMemRoot()->allocate(sizeof(Join))))
1358
error= 0; // Ensure that tmp_join.error= 0
1364
bool Join::save_join_tab()
1366
if (! join_tab_save && select_lex->master_unit()->uncacheable.any())
1368
if (!(join_tab_save= (JoinTable*)session->getMemRoot()->duplicate((unsigned char*) join_tab,
1369
sizeof(JoinTable) * tables)))
1379
Note, that create_sort_index calls test_if_skip_sort_order and may
1380
finally replace sorting with index scan if there is a LIMIT clause in
1381
the query. It's never shown in EXPLAIN!
1384
When can we have here session->net.report_error not zero?
1388
List<Item> *columns_list= &fields_list;
1391
session->set_proc_info("executing");
1394
if (!tables_list && (tables || !select_lex->with_sum_func))
1396
/* Only test of functions */
1397
if (select_options & SELECT_DESCRIBE)
1399
optimizer::ExplainPlan planner(this,
1403
(zero_result_cause ? zero_result_cause : "No tables used"));
1404
planner.printPlan();
1408
result->send_fields(*columns_list);
1410
We have to test for 'conds' here as the WHERE may not be constant
1411
even if we don't have any tables for prepared statements or if
1412
conds uses something like 'rand()'.
1414
if (cond_value != Item::COND_FALSE &&
1415
(!conds || conds->val_int()) &&
1416
(!having || having->val_int()))
1418
if (do_send_rows && result->send_data(fields_list))
1422
error= (int) result->send_eof();
1423
send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 : session->sent_row_count);
1428
error= (int) result->send_eof();
1432
/* Single select (without union) always returns 0 or 1 row */
1433
session->limit_found_rows= send_records;
1434
session->examined_row_count= 0;
1438
Don't reset the found rows count if there're no tables as
1439
FOUND_ROWS() may be called. Never reset the examined row count here.
1440
It must be accumulated from all join iterations of all join parts.
1443
session->limit_found_rows= 0;
1445
if (zero_result_cause)
1447
(void) return_zero_rows(this, result, select_lex->leaf_tables,
1449
send_row_on_empty_set(),
1456
if (select_options & SELECT_DESCRIBE)
1459
Check if we managed to optimize ORDER BY away and don't use temporary
1460
table to resolve order_st BY: in that case, we only may need to do
1461
filesort for GROUP BY.
1463
if (!order && !no_order && (!skip_sort_order || !need_tmp))
1465
/* Reset 'order' to 'group_list' and reinit variables describing 'order' */
1467
simple_order= simple_group;
1470
if (order && (order != group_list || !(select_options & SELECT_BIG_RESULT)))
1472
if (const_tables == tables
1473
|| ((simple_order || skip_sort_order)
1474
&& test_if_skip_sort_order(&join_tab[const_tables], order, select_limit, 0, &join_tab[const_tables].table->keys_in_use_for_query)))
1478
optimizer::ExplainPlan planner(this,
1480
order != 0 && ! skip_sort_order,
1482
! tables ? "No tables used" : NULL);
1483
planner.printPlan();
1487
Join *curr_join= this;
1488
List<Item> *curr_all_fields= &all_fields;
1489
List<Item> *curr_fields_list= &fields_list;
1490
Table *curr_tmp_table= 0;
1492
Initialize examined rows here because the values from all join parts
1493
must be accumulated in examined_row_count. Hence every join
1494
iteration must count from zero.
1496
curr_join->examined_rows= 0;
1498
/* Create a tmp table if distinct or if the sort is too complicated */
1504
We are in a non cacheable sub query. Get the saved join structure
1506
(curr_join may have been modified during last exection and we need
1509
curr_join= tmp_join;
1511
curr_tmp_table= exec_tmp_table1;
1513
/* Copy data to the temporary table */
1514
session->set_proc_info("Copying to tmp table");
1515
if (! curr_join->sort_and_group && curr_join->const_tables != curr_join->tables)
1516
curr_join->join_tab[curr_join->const_tables].sorted= 0;
1517
if ((tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
1522
curr_tmp_table->cursor->info(HA_STATUS_VARIABLE);
1524
if (curr_join->having)
1525
curr_join->having= curr_join->tmp_having= 0; // Allready done
1527
/* Change sum_fields reference to calculated fields in tmp_table */
1528
curr_join->all_fields= *curr_all_fields;
1531
items1= items0 + all_fields.elements;
1532
if (sort_and_group || curr_tmp_table->group)
1534
if (change_to_use_tmp_fields(session, items1,
1535
tmp_fields_list1, tmp_all_fields1,
1536
fields_list.elements, all_fields))
1541
if (change_refs_to_tmp_fields(session, items1,
1542
tmp_fields_list1, tmp_all_fields1,
1543
fields_list.elements, all_fields))
1546
curr_join->tmp_all_fields1= tmp_all_fields1;
1547
curr_join->tmp_fields_list1= tmp_fields_list1;
1548
curr_join->items1= items1;
1550
curr_all_fields= &tmp_all_fields1;
1551
curr_fields_list= &tmp_fields_list1;
1552
curr_join->set_items_ref_array(items1);
1554
if (sort_and_group || curr_tmp_table->group)
1556
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count
1557
+ curr_join->tmp_table_param.func_count;
1558
curr_join->tmp_table_param.sum_func_count= 0;
1559
curr_join->tmp_table_param.func_count= 0;
1563
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.func_count;
1564
curr_join->tmp_table_param.func_count= 0;
1567
if (curr_tmp_table->group)
1568
{ // Already grouped
1569
if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
1570
curr_join->order= curr_join->group_list; /* order by group */
1571
curr_join->group_list= 0;
1575
If we have different sort & group then we must sort the data by group
1576
and copy it to another tmp table
1577
This code is also used if we are using distinct something
1578
we haven't been able to store in the temporary table yet
1579
like SEC_TO_TIME(SUM(...)).
1582
if ((curr_join->group_list && (!test_if_subpart(curr_join->group_list, curr_join->order) || curr_join->select_distinct))
1583
|| (curr_join->select_distinct && curr_join->tmp_table_param.using_indirect_summary_function))
1584
{ /* Must copy to another table */
1585
/* Free first data from old join */
1586
curr_join->join_free();
1587
if (make_simple_join(curr_join, curr_tmp_table))
1589
calc_group_buffer(curr_join, group_list);
1590
count_field_types(select_lex, &curr_join->tmp_table_param,
1591
curr_join->tmp_all_fields1,
1592
curr_join->select_distinct && !curr_join->group_list);
1593
curr_join->tmp_table_param.hidden_field_count= curr_join->tmp_all_fields1.elements
1594
- curr_join->tmp_fields_list1.elements;
1596
if (exec_tmp_table2)
1598
curr_tmp_table= exec_tmp_table2;
1602
/* group data to new table */
1605
If the access method is loose index scan then all MIN/MAX
1606
functions are precomputed, and should be treated as regular
1607
functions. See extended comment in Join::exec.
1609
if (curr_join->join_tab->is_using_loose_index_scan())
1610
curr_join->tmp_table_param.precomputed_group_by= true;
1612
if (!(curr_tmp_table=
1613
exec_tmp_table2= create_tmp_table(session,
1614
&curr_join->tmp_table_param,
1617
curr_join->select_distinct &&
1618
!curr_join->group_list,
1619
1, curr_join->select_options,
1626
curr_join->exec_tmp_table2= exec_tmp_table2;
1628
if (curr_join->group_list)
1630
session->set_proc_info("Creating sort index");
1631
if (curr_join->join_tab == join_tab && save_join_tab())
1635
if (create_sort_index(session, curr_join, curr_join->group_list,
1636
HA_POS_ERROR, HA_POS_ERROR, false) ||
1637
make_group_fields(this, curr_join))
1641
sortorder= curr_join->sortorder;
1644
session->set_proc_info("Copying to group table");
1646
if (curr_join != this)
1650
curr_join->sum_funcs= sum_funcs2;
1651
curr_join->sum_funcs_end= sum_funcs_end2;
1655
curr_join->alloc_func_list();
1656
sum_funcs2= curr_join->sum_funcs;
1657
sum_funcs_end2= curr_join->sum_funcs_end;
1660
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list, 1, true))
1662
curr_join->group_list= 0;
1664
if (!curr_join->sort_and_group && (curr_join->const_tables != curr_join->tables))
1665
curr_join->join_tab[curr_join->const_tables].sorted= 0;
1667
if (setup_sum_funcs(curr_join->session, curr_join->sum_funcs)
1668
|| (tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
1673
curr_join->join_tab->read_record.end_read_record();
1674
curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
1675
curr_join->join_tab[0].table= 0; // Table is freed
1677
// No sum funcs anymore
1680
items2= items1 + all_fields.elements;
1681
if (change_to_use_tmp_fields(session, items2,
1682
tmp_fields_list2, tmp_all_fields2,
1683
fields_list.elements, tmp_all_fields1))
1685
curr_join->tmp_fields_list2= tmp_fields_list2;
1686
curr_join->tmp_all_fields2= tmp_all_fields2;
1688
curr_fields_list= &curr_join->tmp_fields_list2;
1689
curr_all_fields= &curr_join->tmp_all_fields2;
1690
curr_join->set_items_ref_array(items2);
1691
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count;
1692
curr_join->tmp_table_param.sum_func_count= 0;
1694
if (curr_tmp_table->distinct)
1695
curr_join->select_distinct=0; /* Each row is unique */
1697
curr_join->join_free(); /* Free quick selects */
1698
if (curr_join->select_distinct && ! curr_join->group_list)
1700
session->set_proc_info("Removing duplicates");
1701
if (curr_join->tmp_having)
1702
curr_join->tmp_having->update_used_tables();
1704
if (remove_duplicates(curr_join, curr_tmp_table,
1705
*curr_fields_list, curr_join->tmp_having))
1708
curr_join->tmp_having=0;
1709
curr_join->select_distinct=0;
1711
curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
1712
if (make_simple_join(curr_join, curr_tmp_table))
1714
calc_group_buffer(curr_join, curr_join->group_list);
1715
count_field_types(select_lex, &curr_join->tmp_table_param, *curr_all_fields, 0);
1719
if (curr_join->group || curr_join->tmp_table_param.sum_func_count)
1721
if (make_group_fields(this, curr_join))
1727
init_items_ref_array();
1728
items3= ref_pointer_array + (all_fields.elements*4);
1729
setup_copy_fields(session, &curr_join->tmp_table_param,
1730
items3, tmp_fields_list3, tmp_all_fields3,
1731
curr_fields_list->elements, *curr_all_fields);
1732
tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
1733
tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
1734
tmp_table_param.save_copy_field_end= curr_join->tmp_table_param.copy_field_end;
1735
curr_join->tmp_all_fields3= tmp_all_fields3;
1736
curr_join->tmp_fields_list3= tmp_fields_list3;
1740
curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
1741
curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
1742
curr_join->tmp_table_param.copy_field_end= tmp_table_param.save_copy_field_end;
1744
curr_fields_list= &tmp_fields_list3;
1745
curr_all_fields= &tmp_all_fields3;
1746
curr_join->set_items_ref_array(items3);
1748
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
1750
setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
1751
session->is_fatal_error)
1754
if (curr_join->group_list || curr_join->order)
1756
session->set_proc_info("Sorting result");
1757
/* If we have already done the group, add HAVING to sorted table */
1758
if (curr_join->tmp_having && ! curr_join->group_list && ! curr_join->sort_and_group)
1760
// Some tables may have been const
1761
curr_join->tmp_having->update_used_tables();
1762
JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables];
1763
table_map used_tables= (curr_join->const_table_map |
1764
curr_table->table->map);
1766
Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having, used_tables, used_tables, 0);
1767
if (sort_table_cond)
1769
if (!curr_table->select)
1770
if (!(curr_table->select= new optimizer::SqlSelect()))
1772
if (!curr_table->select->cond)
1773
curr_table->select->cond= sort_table_cond;
1774
else // This should never happen
1776
if (!(curr_table->select->cond=
1777
new Item_cond_and(curr_table->select->cond,
1781
Item_cond_and do not need fix_fields for execution, its parameters
1782
are fixed or do not need fix_fields, too
1784
curr_table->select->cond->quick_fix_field();
1786
curr_table->select_cond= curr_table->select->cond;
1787
curr_table->select_cond->top_level_item();
1788
curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
1795
curr_join->select_limit= HA_POS_ERROR;
1799
We can abort sorting after session->select_limit rows if we there is no
1800
WHERE clause for any tables after the sorted one.
1802
JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
1803
JoinTable *end_table= &curr_join->join_tab[curr_join->tables];
1804
for (; curr_table < end_table ; curr_table++)
1807
table->keyuse is set in the case there was an original WHERE clause
1808
on the table that was optimized away.
1810
if (curr_table->select_cond ||
1811
(curr_table->keyuse && !curr_table->first_inner))
1813
/* We have to sort all rows */
1814
curr_join->select_limit= HA_POS_ERROR;
1819
if (curr_join->join_tab == join_tab && save_join_tab())
1822
Here we sort rows for order_st BY/GROUP BY clause, if the optimiser
1823
chose FILESORT to be faster than INDEX SCAN or there is no
1824
suitable index present.
1825
Note, that create_sort_index calls test_if_skip_sort_order and may
1826
finally replace sorting with index scan if there is a LIMIT clause in
1827
the query. XXX: it's never shown in EXPLAIN!
1828
OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
1830
if (create_sort_index(session, curr_join,
1831
curr_join->group_list ?
1832
curr_join->group_list : curr_join->order,
1833
curr_join->select_limit,
1834
(select_options & OPTION_FOUND_ROWS ?
1835
HA_POS_ERROR : unit->select_limit_cnt),
1836
curr_join->group_list ? true : false))
1839
sortorder= curr_join->sortorder;
1840
if (curr_join->const_tables != curr_join->tables &&
1841
!curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
1844
If no IO cache exists for the first table then we are using an
1845
INDEX SCAN and no filesort. Thus we should not remove the sorted
1846
attribute on the INDEX SCAN.
1852
/* XXX: When can we have here session->is_error() not zero? */
1853
if (session->is_error())
1855
error= session->is_error();
1858
curr_join->having= curr_join->tmp_having;
1859
curr_join->fields= curr_fields_list;
1861
session->set_proc_info("Sending data");
1862
result->send_fields(*curr_fields_list);
1863
error= do_select(curr_join, curr_fields_list, NULL);
1864
session->limit_found_rows= curr_join->send_records;
1866
/* Accumulate the counts from all join iterations of all join parts. */
1867
session->examined_row_count+= curr_join->examined_rows;
1870
With EXPLAIN EXTENDED we have to restore original ref_array
1871
for a derived table which is always materialized.
1872
Otherwise we would not be able to print the query correctly.
1874
if (items0 && (session->getLex()->describe & DESCRIBE_EXTENDED) && select_lex->linkage == DERIVED_TABLE_TYPE)
1875
set_items_ref_array(items0);
1884
Return error that hold Join.
1888
select_lex->join= 0;
1892
if (join_tab != tmp_join->join_tab)
1894
JoinTable *tab, *end;
1895
for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
1898
tmp_join->tmp_join= 0;
1899
tmp_table_param.copy_field=0;
1900
return(tmp_join->destroy());
1905
exec_tmp_table1= NULL;
1906
exec_tmp_table2= NULL;
1908
delete_dynamic(&keyuse);
1914
Setup for execution all subqueries of a query, for which the optimizer
1915
chose hash semi-join.
1917
@details Iterate over all subqueries of the query, and if they are under an
1918
IN predicate, and the optimizer chose to compute it via hash semi-join:
1919
- try to initialize all data structures needed for the materialized execution
1920
of the IN predicate,
1921
- if this fails, then perform the IN=>EXISTS transformation which was
1922
previously blocked during Join::prepare.
1924
This method is part of the "code generation" query processing phase.
1926
This phase must be called after substitute_for_best_equal_field() because
1927
that function may replace items with other items from a multiple equality,
1928
and we need to reference the correct items in the index access method of the
1931
@return Operation status
1932
@retval false success.
1933
@retval true error occurred.
1935
bool Join::setup_subquery_materialization()
1937
for (Select_Lex_Unit *un= select_lex->first_inner_unit(); un;
1938
un= un->next_unit())
1940
for (Select_Lex *sl= un->first_select(); sl; sl= sl->next_select())
1942
Item_subselect *subquery_predicate= sl->master_unit()->item;
1943
if (subquery_predicate &&
1944
subquery_predicate->substype() == Item_subselect::IN_SUBS)
1946
Item_in_subselect *in_subs= (Item_in_subselect*) subquery_predicate;
1947
if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION &&
1948
in_subs->setup_engine())
1957
Partially cleanup Join after it has executed: close index or rnd read
1958
(table cursors), free quick selects.
1960
This function is called in the end of execution of a Join, before the used
1961
tables are unlocked and closed.
1963
For a join that is resolved using a temporary table, the first sweep is
1964
performed against actual tables and an intermediate result is inserted
1965
into the temprorary table.
1966
The last sweep is performed against the temporary table. Therefore,
1967
the base tables and associated buffers used to fill the temporary table
1968
are no longer needed, and this function is called to free them.
1970
For a join that is performed without a temporary table, this function
1971
is called after all rows are sent, but before EOF packet is sent.
1973
For a simple SELECT with no subqueries this function performs a full
1974
cleanup of the Join and calls unlockReadTables to free used base
1977
If a Join is executed for a subquery or if it has a subquery, we can't
1978
do the full cleanup and need to do a partial cleanup only.
1979
- If a Join is not the top level join, we must not unlock the tables
1980
because the outer select may not have been evaluated yet, and we
1981
can't unlock only selected tables of a query.
1982
- Additionally, if this Join corresponds to a correlated subquery, we
1983
should not free quick selects and join buffers because they will be
1984
needed for the next execution of the correlated subquery.
1985
- However, if this is a Join for a [sub]select, which is not
1986
a correlated subquery itself, but has subqueries, we can free it
1987
fully and also free Joins of all its subqueries. The exception
1988
is a subquery in SELECT list, e.g: @n
1989
SELECT a, (select cmax(b) from t1) group by c @n
1990
This subquery will not be evaluated at first sweep and its value will
1991
not be inserted into the temporary table. Instead, it's evaluated
1992
when selecting from the temporary table. Therefore, it can't be freed
1993
here even though it's not correlated.
1996
Unlock tables even if the join isn't top level select in the tree
1998
void Join::join_free()
2000
Select_Lex_Unit *tmp_unit;
2003
Optimization: if not EXPLAIN and we are done with the Join,
2006
bool full= (select_lex->uncacheable.none() && ! session->getLex()->describe);
2007
bool can_unlock= full;
2011
for (tmp_unit= select_lex->first_inner_unit();
2013
tmp_unit= tmp_unit->next_unit())
2014
for (sl= tmp_unit->first_select(); sl; sl= sl->next_select())
2016
Item_subselect *subselect= sl->master_unit()->item;
2017
bool full_local= full && (!subselect ||
2018
(subselect->is_evaluated() &&
2019
!subselect->is_uncacheable()));
2021
If this join is evaluated, we can fully clean it up and clean up all
2022
its underlying joins even if they are correlated -- they will not be
2023
used any more anyway.
2024
If this join is not yet evaluated, we still must clean it up to
2025
close its table cursors -- it may never get evaluated, as in case of
2026
... HAVING false OR a IN (SELECT ...))
2027
but all table cursors must be closed before the unlock.
2029
sl->cleanup_all_joins(full_local);
2030
/* Can't unlock if at least one Join is still needed */
2031
can_unlock= can_unlock && full_local;
2035
We are not using tables anymore
2036
Unlock all tables. We may be in an INSERT .... SELECT statement.
2038
if (can_unlock && lock && session->lock &&
2039
!(select_options & SELECT_NO_UNLOCK) &&
2040
!select_lex->subquery_in_having &&
2041
(select_lex == (session->getLex()->unit.fake_select_lex ?
2042
session->getLex()->unit.fake_select_lex : &session->getLex()->select_lex)))
2045
TODO: unlock tables even if the join isn't top level select in the
2048
session->unlockReadTables(lock); // Don't free join->lock
2057
Free resources of given join.
2059
@param fill true if we should free all resources, call with full==1
2060
should be last, before it this function can be called with
2064
With subquery this function definitely will be called several times,
2065
but even for simple query it can be called several times.
2067
void Join::cleanup(bool full)
2072
Only a sorted table may be cached. This sorted table is always the
2073
first non const table in join->table
2075
if (tables > const_tables) // Test for not-const tables
2077
table[const_tables]->free_io_cache();
2078
table[const_tables]->filesort_free_buffers(full);
2084
JoinTable *tab,*end;
2088
for (tab= join_tab, end= tab+tables; tab != end; tab++)
2094
for (tab= join_tab, end= tab+tables; tab != end; tab++)
2097
tab->table->cursor->ha_index_or_rnd_end();
2103
We are not using tables anymore
2104
Unlock all tables. We may be in an INSERT .... SELECT statement.
2109
tmp_table_param.copy_field= 0;
2110
group_fields.delete_elements();
2112
We can't call delete_elements() on copy_funcs as this will cause
2113
problems in free_elements() as some of the elements are then deleted.
2115
tmp_table_param.copy_funcs.clear();
2117
If we have tmp_join and 'this' Join is not tmp_join and
2118
tmp_table_param.copy_field's of them are equal then we have to remove
2119
pointer to tmp_table_param.copy_field from tmp_join, because it qill
2120
be removed in tmp_table_param.cleanup().
2124
tmp_join->tmp_table_param.copy_field ==
2125
tmp_table_param.copy_field)
2127
tmp_join->tmp_table_param.copy_field=
2128
tmp_join->tmp_table_param.save_copy_field= 0;
2130
tmp_table_param.cleanup();
2136
used only in Join::clear
2138
static void clear_tables(Join *join)
2141
must clear only the non-const tables, as const tables
2142
are not re-calculated.
2144
for (uint32_t i= join->const_tables; i < join->tables; i++)
2146
join->table[i]->mark_as_null_row(); // All fields are NULL
2151
Make an array of pointers to sum_functions to speed up
2152
sum_func calculation.
2159
bool Join::alloc_func_list()
2161
uint32_t func_count, group_parts;
2163
func_count= tmp_table_param.sum_func_count;
2165
If we are using rollup, we need a copy of the summary functions for
2168
if (rollup.getState() != Rollup::STATE_NONE)
2169
func_count*= (send_group_parts+1);
2171
group_parts= send_group_parts;
2173
If distinct, reserve memory for possible
2174
disctinct->group_by optimization
2176
if (select_distinct)
2178
group_parts+= fields_list.elements;
2180
If the order_st clause is specified then it's possible that
2181
it also will be optimized, so reserve space for it too
2186
for (ord= order; ord; ord= ord->next)
2191
/* This must use calloc() as rollup_make_fields depends on this */
2192
sum_funcs= (Item_sum**) session->calloc(sizeof(Item_sum**) * (func_count+1) +
2193
sizeof(Item_sum***) * (group_parts+1));
2194
sum_funcs_end= (Item_sum***) (sum_funcs+func_count+1);
2195
return(sum_funcs == 0);
2199
Initialize 'sum_funcs' array with all Item_sum objects.
2201
@param field_list All items
2202
@param send_fields Items in select list
2203
@param before_group_by Set to 1 if this is called before GROUP BY handling
2204
@param recompute Set to true if sum_funcs must be recomputed
2211
bool Join::make_sum_func_list(List<Item> &field_list,
2212
List<Item> &send_fields,
2213
bool before_group_by,
2216
List<Item>::iterator it(field_list.begin());
2220
if (*sum_funcs && !recompute)
2221
return(false); /* We have already initialized sum_funcs. */
2226
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
2227
(!((Item_sum*) item)->depended_from() ||
2228
((Item_sum *)item)->depended_from() == select_lex))
2229
*func++= (Item_sum*) item;
2231
if (before_group_by && rollup.getState() == Rollup::STATE_INITED)
2233
rollup.setState(Rollup::STATE_READY);
2234
if (rollup_make_fields(field_list, send_fields, &func))
2235
return true; // Should never happen
2237
else if (rollup.getState() == Rollup::STATE_NONE)
2239
for (uint32_t i=0 ; i <= send_group_parts ;i++)
2240
sum_funcs_end[i]= func;
2242
else if (rollup.getState() == Rollup::STATE_READY)
2243
return(false); // Don't put end marker
2244
*func=0; // End marker
2248
/** Allocate memory needed for other rollup functions. */
2249
bool Join::rollup_init()
2253
tmp_table_param.quick_group= 0; // Can't create groups in tmp table
2254
rollup.setState(Rollup::STATE_INITED);
2257
Create pointers to the different sum function groups
2258
These are updated by rollup_make_fields()
2260
tmp_table_param.group_parts= send_group_parts;
2262
rollup.setNullItems((Item_null_result**) session->getMemRoot()->allocate((sizeof(Item*) +
2264
sizeof(List<Item>) +
2265
ref_pointer_array_size)
2266
* send_group_parts ));
2267
if (! rollup.getNullItems())
2272
rollup.setFields((List<Item>*) (rollup.getNullItems() + send_group_parts));
2273
rollup.setRefPointerArrays((Item***) (rollup.getFields() + send_group_parts));
2274
ref_array= (Item**) (rollup.getRefPointerArrays()+send_group_parts);
2277
Prepare space for field list for the different levels
2278
These will be filled up in rollup_make_fields()
2280
for (uint32_t i= 0 ; i < send_group_parts ; i++)
2282
rollup.getNullItems()[i]= new (session->mem_root) Item_null_result();
2283
List<Item> *rollup_fields= &rollup.getFields()[i];
2284
rollup_fields->clear();
2285
rollup.getRefPointerArrays()[i]= ref_array;
2286
ref_array+= all_fields.elements;
2289
for (uint32_t i= 0 ; i < send_group_parts; i++)
2291
for (uint32_t j= 0 ; j < fields_list.elements ; j++)
2293
rollup.getFields()[i].push_back(rollup.getNullItems()[i]);
2297
List<Item>::iterator it(all_fields.begin());
2299
while ((item= it++))
2302
bool found_in_group= 0;
2304
for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
2306
if (*group_tmp->item == item)
2308
item->maybe_null= 1;
2310
if (item->const_item())
2313
For ROLLUP queries each constant item referenced in GROUP BY list
2314
is wrapped up into an Item_func object yielding the same value
2315
as the constant item. The objects of the wrapper class are never
2316
considered as constant items and besides they inherit all
2317
properties of the Item_result_field class.
2318
This wrapping allows us to ensure writing constant items
2319
into temporary tables whenever the result of the ROLLUP
2320
operation has to be written into a temporary table, e.g. when
2321
ROLLUP is used together with DISTINCT in the SELECT list.
2322
Usually when creating temporary tables for a intermidiate
2323
result we do not include fields for constant expressions.
2325
Item* new_item= new Item_func_rollup_const(item);
2328
new_item->fix_fields(session, (Item **) 0);
2329
session->change_item_tree(it.ref(), new_item);
2330
for (Order *tmp= group_tmp; tmp; tmp= tmp->next)
2332
if (*tmp->item == item)
2333
session->change_item_tree(tmp->item, new_item);
2338
if (item->type() == Item::FUNC_ITEM && !found_in_group)
2340
bool changed= false;
2341
if (change_group_ref(session, (Item_func *) item, group_list, &changed))
2344
We have to prevent creation of a field in a temporary table for
2345
an expression that contains GROUP BY attributes.
2346
Marking the expression item as 'with_sum_func' will ensure this.
2349
item->with_sum_func= 1;
2356
Fill up rollup structures with pointers to fields to use.
2358
Creates copies of item_sum items for each sum level.
2360
@param fields_arg List of all fields (hidden and real ones)
2361
@param sel_fields Pointer to selected fields
2362
@param func Store here a pointer to all fields
2366
In this case func is pointing to next not used element.
2370
bool Join::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields, Item_sum ***func)
2372
List<Item>::iterator it(fields_arg.begin());
2373
Item *first_field= sel_fields.head();
2377
Create field lists for the different levels
2379
The idea here is to have a separate field list for each rollup level to
2380
avoid all runtime checks of which columns should be NULL.
2382
The list is stored in reverse order to get sum function in such an order
2383
in func that it makes it easy to reset them with init_sum_functions()
2385
Assuming: SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
2387
rollup.fields[0] will contain list where a,b,c is NULL
2388
rollup.fields[1] will contain list where b,c is NULL
2390
rollup.ref_pointer_array[#] points to fields for rollup.fields[#]
2392
sum_funcs_end[0] points to all sum functions
2393
sum_funcs_end[1] points to all sum functions, except grand totals
2397
for (level=0 ; level < send_group_parts ; level++)
2400
uint32_t pos= send_group_parts - level -1;
2401
bool real_fields= 0;
2403
List<Item>::iterator new_it(rollup.getFields()[pos].begin());
2404
Item **ref_array_start= rollup.getRefPointerArrays()[pos];
2407
/* Point to first hidden field */
2408
Item **ref_array= ref_array_start + fields_arg.elements-1;
2410
/* Remember where the sum functions ends for the previous level */
2411
sum_funcs_end[pos+1]= *func;
2413
/* Find the start of the group for this level */
2414
for (i= 0, start_group= group_list ;i++ < pos ;start_group= start_group->next)
2417
it= fields_arg.begin();
2418
while ((item= it++))
2420
if (item == first_field)
2422
real_fields= 1; // End of hidden fields
2423
ref_array= ref_array_start;
2426
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
2427
(!((Item_sum*) item)->depended_from() ||
2428
((Item_sum *)item)->depended_from() == select_lex))
2432
This is a top level summary function that must be replaced with
2433
a sum function that is reset for this level.
2435
NOTE: This code creates an object which is not that nice in a
2436
sub select. Fortunately it's not common to have rollup in
2439
item= item->copy_or_same(session);
2440
((Item_sum*) item)->make_unique();
2441
*(*func)= (Item_sum*) item;
2446
/* Check if this is something that is part of this group by */
2448
for (group_tmp= start_group, i= pos ;
2449
group_tmp ; group_tmp= group_tmp->next, i++)
2451
if (*group_tmp->item == item)
2454
This is an element that is used by the GROUP BY and should be
2455
set to NULL in this level
2457
Item_null_result *null_item= new (session->mem_root) Item_null_result();
2460
item->maybe_null= 1; // Value will be null sometimes
2461
null_item->result_field= item->get_tmp_table_field();
2470
(void) new_it++; // Point to next item
2471
new_it.replace(item); // Replace previous
2478
sum_funcs_end[0]= *func; // Point to last function
2483
Send all rollup levels higher than the current one to the client.
2487
SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
2490
@param idx Level we are on:
2491
- 0 = Total sum level
2492
- 1 = First group changed (a)
2493
- 2 = Second group changed (a,b)
2498
1 If send_data_failed()
2500
int Join::rollup_send_data(uint32_t idx)
2502
for (uint32_t i= send_group_parts ; i-- > idx ; )
2504
/* Get reference pointers to sum functions in place */
2505
memcpy(ref_pointer_array, rollup.getRefPointerArrays()[i], ref_pointer_array_size);
2507
if ((!having || having->val_int()))
2509
if (send_records < unit->select_limit_cnt && do_send_rows && result->send_data(rollup.getFields()[i]))
2516
/* Restore ref_pointer_array */
2517
set_items_ref_array(current_ref_pointer_array);
2523
Write all rollup levels higher than the current one to a temp table.
2527
SELECT a, b, SUM(c) FROM t1 GROUP BY a,b WITH ROLLUP
2530
@param idx Level we are on:
2531
- 0 = Total sum level
2532
- 1 = First group changed (a)
2533
- 2 = Second group changed (a,b)
2534
@param table reference to temp table
2539
1 if write_data_failed()
2541
int Join::rollup_write_data(uint32_t idx, Table *table_arg)
2543
for (uint32_t i= send_group_parts ; i-- > idx ; )
2545
/* Get reference pointers to sum functions in place */
2546
memcpy(ref_pointer_array, rollup.getRefPointerArrays()[i],
2547
ref_pointer_array_size);
2548
if ((!having || having->val_int()))
2552
List<Item>::iterator it(rollup.getFields()[i].begin());
2553
while ((item= it++))
2555
if (item->type() == Item::NULL_ITEM && item->is_result_field())
2556
item->save_in_result_field(1);
2558
copy_sum_funcs(sum_funcs_end[i+1], sum_funcs_end[i]);
2559
if ((write_error= table_arg->cursor->insertRecord(table_arg->getInsertRecord())))
2561
my_error(ER_USE_SQL_BIG_RESULT, MYF(0));
2566
/* Restore ref_pointer_array */
2567
set_items_ref_array(current_ref_pointer_array);
2573
clear results if there are not rows found for group
2574
(end_send_group/end_write_group)
2579
copy_fields(&tmp_table_param);
2583
Item_sum *func, **func_ptr= sum_funcs;
2584
while ((func= *(func_ptr++)))
2590
change select_result object of Join.
2592
@param res new select_result object
2599
bool Join::change_result(select_result *res)
2602
if (result->prepare(fields_list, select_lex->master_unit()))
2610
Cache constant expressions in WHERE, HAVING, ON conditions.
2613
void Join::cache_const_exprs()
2615
bool cache_flag= false;
2616
bool *analyzer_arg= &cache_flag;
2618
/* No need in cache if all tables are constant. */
2619
if (const_tables == tables)
2623
conds->compile(&Item::cache_const_expr_analyzer, (unsigned char **)&analyzer_arg,
2624
&Item::cache_const_expr_transformer, (unsigned char *)&cache_flag);
2627
having->compile(&Item::cache_const_expr_analyzer, (unsigned char **)&analyzer_arg,
2628
&Item::cache_const_expr_transformer, (unsigned char *)&cache_flag);
2630
for (JoinTable *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
2632
if (*tab->on_expr_ref)
2635
(*tab->on_expr_ref)->compile(&Item::cache_const_expr_analyzer,
2636
(unsigned char **)&analyzer_arg,
2637
&Item::cache_const_expr_transformer,
2638
(unsigned char *)&cache_flag);
2646
Process one record of the nested loop join.
2650
This function will evaluate parts of WHERE/ON clauses that are
2651
applicable to the partial record on hand and in case of success
2652
submit this record to the next level of the nested loop.
2654
enum_nested_loop_state evaluate_join_record(Join *join, JoinTable *join_tab, int error)
2656
bool not_used_in_distinct= join_tab->not_used_in_distinct;
2657
ha_rows found_records= join->found_records;
2658
COND *select_cond= join_tab->select_cond;
2660
if (error > 0 || (join->session->is_error())) // Fatal error
2661
return NESTED_LOOP_ERROR;
2663
return NESTED_LOOP_NO_MORE_ROWS;
2664
if (join->session->getKilled()) // Aborted by user
2666
join->session->send_kill_message();
2667
return NESTED_LOOP_KILLED;
2669
if (!select_cond || select_cond->val_int())
2672
There is no select condition or the attached pushed down
2673
condition is true => a match is found.
2676
while (join_tab->first_unmatched && found)
2679
The while condition is always false if join_tab is not
2680
the last inner join table of an outer join operation.
2682
JoinTable *first_unmatched= join_tab->first_unmatched;
2684
Mark that a match for current outer table is found.
2685
This activates push down conditional predicates attached
2686
to the all inner tables of the outer join.
2688
first_unmatched->found= 1;
2689
for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)
2691
if (tab->table->reginfo.not_exists_optimize)
2692
return NESTED_LOOP_NO_MORE_ROWS;
2693
/* Check all predicates that has just been activated. */
2695
Actually all predicates non-guarded by first_unmatched->found
2696
will be re-evaluated again. It could be fixed, but, probably,
2697
it's not worth doing now.
2699
if (tab->select_cond && !tab->select_cond->val_int())
2701
/* The condition attached to table tab is false */
2702
if (tab == join_tab)
2707
Set a return point if rejected predicate is attached
2708
not to the last table of the current nest level.
2710
join->return_tab= tab;
2711
return NESTED_LOOP_OK;
2716
Check whether join_tab is not the last inner table
2717
for another embedding outer join.
2719
if ((first_unmatched= first_unmatched->first_upper) &&
2720
first_unmatched->last_inner != join_tab)
2722
join_tab->first_unmatched= first_unmatched;
2725
JoinTable *return_tab= join->return_tab;
2726
join_tab->found_match= true;
2729
It was not just a return to lower loop level when one
2730
of the newly activated predicates is evaluated as false
2731
(See above join->return_tab= tab).
2733
join->examined_rows++;
2734
join->session->row_count++;
2738
enum enum_nested_loop_state rc;
2739
/* A match from join_tab is found for the current partial join. */
2740
rc= (*join_tab->next_select)(join, join_tab+1, 0);
2741
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2743
if (return_tab < join->return_tab)
2744
join->return_tab= return_tab;
2746
if (join->return_tab < join_tab)
2747
return NESTED_LOOP_OK;
2749
Test if this was a SELECT DISTINCT query on a table that
2750
was not in the field list; In this case we can abort if
2751
we found a row, as no new rows can be added to the result.
2753
if (not_used_in_distinct && found_records != join->found_records)
2754
return NESTED_LOOP_NO_MORE_ROWS;
2757
join_tab->read_record.cursor->unlock_row();
2762
The condition pushed down to the table join_tab rejects all rows
2763
with the beginning coinciding with the current partial join.
2765
join->examined_rows++;
2766
join->session->row_count++;
2767
join_tab->read_record.cursor->unlock_row();
2769
return NESTED_LOOP_OK;
2774
Construct a NULL complimented partial join record and feed it to the next
2775
level of the nested loop. This function is used in case we have
2776
an OUTER join and no matching record was found.
2778
enum_nested_loop_state evaluate_null_complemented_join_record(Join *join, JoinTable *join_tab)
2781
The table join_tab is the first inner table of a outer join operation
2782
and no matches has been found for the current outer row.
2784
JoinTable *last_inner_tab= join_tab->last_inner;
2785
/* Cache variables for faster loop */
2787
for ( ; join_tab <= last_inner_tab ; join_tab++)
2789
/* Change the the values of guard predicate variables. */
2791
join_tab->not_null_compl= 0;
2792
/* The outer row is complemented by nulls for each inner tables */
2793
join_tab->table->restoreRecordAsDefault(); // Make empty record
2794
join_tab->table->mark_as_null_row(); // For group by without error
2795
select_cond= join_tab->select_cond;
2796
/* Check all attached conditions for inner table rows. */
2797
if (select_cond && !select_cond->val_int())
2798
return NESTED_LOOP_OK;
2802
The row complemented by nulls might be the first row
2803
of embedding outer joins.
2804
If so, perform the same actions as in the code
2805
for the first regular outer join row above.
2809
JoinTable *first_unmatched= join_tab->first_unmatched;
2810
if ((first_unmatched= first_unmatched->first_upper) && first_unmatched->last_inner != join_tab)
2812
join_tab->first_unmatched= first_unmatched;
2813
if (! first_unmatched)
2815
first_unmatched->found= 1;
2816
for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)
2818
if (tab->select_cond && !tab->select_cond->val_int())
2820
join->return_tab= tab;
2821
return NESTED_LOOP_OK;
2826
The row complemented by nulls satisfies all conditions
2827
attached to inner tables.
2828
Send the row complemented by nulls to be joined with the
2831
return (*join_tab->next_select)(join, join_tab+1, 0);
2834
enum_nested_loop_state flush_cached_records(Join *join, JoinTable *join_tab, bool skip_last)
2836
enum_nested_loop_state rc= NESTED_LOOP_OK;
2840
join_tab->table->null_row= 0;
2841
if (!join_tab->cache.records)
2843
return NESTED_LOOP_OK; /* Nothing to do */
2848
(void) join_tab->cache.store_record_in_cache(); // Must save this for later
2852
if (join_tab->use_quick == 2)
2854
if (join_tab->select->quick)
2855
{ /* Used quick select last. reset it */
2856
delete join_tab->select->quick;
2857
join_tab->select->quick=0;
2860
/* read through all records */
2861
if ((error=join_init_read_record(join_tab)))
2863
join_tab->cache.reset_cache_write();
2864
return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
2867
for (JoinTable *tmp=join->join_tab; tmp != join_tab ; tmp++)
2869
tmp->status=tmp->table->status;
2870
tmp->table->status=0;
2873
info= &join_tab->read_record;
2876
if (join->session->getKilled())
2878
join->session->send_kill_message();
2879
return NESTED_LOOP_KILLED;
2881
optimizer::SqlSelect *select= join_tab->select;
2882
if (rc == NESTED_LOOP_OK &&
2883
(!join_tab->cache.select || !join_tab->cache.select->skip_record()))
2886
join_tab->cache.reset_cache_read();
2887
for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
2889
join_tab->readCachedRecord();
2890
if (!select || !select->skip_record())
2894
rc= (join_tab->next_select)(join,join_tab+1,0);
2895
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2897
join_tab->cache.reset_cache_write();
2902
return NESTED_LOOP_ERROR;
2906
} while (!(error=info->read_record(info)));
2909
join_tab->readCachedRecord(); // Restore current record
2910
join_tab->cache.reset_cache_write();
2911
if (error > 0) // Fatal error
2912
return NESTED_LOOP_ERROR;
2913
for (JoinTable *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
2914
tmp2->table->status=tmp2->status;
2915
return NESTED_LOOP_OK;
2918
/*****************************************************************************
2920
Functions that end one nested loop iteration. Different functions
2921
are used to support GROUP BY clause and to redirect records
2922
to a table (e.g. in case of SELECT into a temporary table) or to the
2926
NESTED_LOOP_OK - the record has been successfully handled
2927
NESTED_LOOP_ERROR - a fatal error (like table corruption)
2929
NESTED_LOOP_KILLED - thread shutdown was requested while processing
2931
NESTED_LOOP_QUERY_LIMIT - the record has been successfully handled;
2932
additionally, the nested loop produced the
2933
number of rows specified in the LIMIT clause
2935
NESTED_LOOP_CURSOR_LIMIT - the record has been successfully handled;
2936
additionally, there is a cursor and the nested
2937
loop algorithm produced the number of rows
2938
that is specified for current cursor fetch
2940
All return values except NESTED_LOOP_OK abort the nested loop.
2941
*****************************************************************************/
2942
enum_nested_loop_state end_send(Join *join, JoinTable *, bool end_of_records)
2944
if (! end_of_records)
2947
if (join->having && join->having->val_int() == 0)
2948
return NESTED_LOOP_OK; // Didn't match having
2950
if (join->do_send_rows)
2951
error=join->result->send_data(*join->fields);
2953
return NESTED_LOOP_ERROR;
2954
if (++join->send_records >= join->unit->select_limit_cnt && join->do_send_rows)
2956
if (join->select_options & OPTION_FOUND_ROWS)
2958
JoinTable *jt=join->join_tab;
2959
if ((join->tables == 1) && !join->tmp_table && !join->sort_and_group
2960
&& !join->send_group_parts && !join->having && !jt->select_cond &&
2961
!(jt->select && jt->select->quick) &&
2962
(jt->table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
2965
/* Join over all rows in table; Return number of found rows */
2966
Table *table= jt->table;
2968
join->select_options^= OPTION_FOUND_ROWS;
2969
if (table->sort.record_pointers ||
2970
(table->sort.io_cache && my_b_inited(table->sort.io_cache)))
2972
/* Using filesort */
2973
join->send_records= table->sort.found_records;
2977
table->cursor->info(HA_STATUS_VARIABLE);
2978
join->send_records= table->cursor->stats.records;
2983
join->do_send_rows= 0;
2984
if (join->unit->fake_select_lex)
2985
join->unit->fake_select_lex->select_limit= 0;
2986
return NESTED_LOOP_OK;
2989
return NESTED_LOOP_QUERY_LIMIT; // Abort nicely
2991
else if (join->send_records >= join->fetch_limit)
2994
There is a server side cursor and all rows for
2995
this fetch request are sent.
2997
return NESTED_LOOP_CURSOR_LIMIT;
3001
return NESTED_LOOP_OK;
3004
enum_nested_loop_state end_write(Join *join, JoinTable *, bool end_of_records)
3006
Table *table= join->tmp_table;
3008
if (join->session->getKilled()) // Aborted by user
3010
join->session->send_kill_message();
3011
return NESTED_LOOP_KILLED;
3013
if (!end_of_records)
3015
copy_fields(&join->tmp_table_param);
3016
if (copy_funcs(join->tmp_table_param.items_to_copy, join->session))
3017
return NESTED_LOOP_ERROR;
3018
if (!join->having || join->having->val_int())
3021
join->found_records++;
3022
if ((error=table->cursor->insertRecord(table->getInsertRecord())))
3024
if (!table->cursor->is_fatal_error(error, HA_CHECK_DUP))
3026
return NESTED_LOOP_OK;
3029
my_error(ER_USE_SQL_BIG_RESULT, MYF(0));
3030
return NESTED_LOOP_ERROR; // Table is_full error
3032
if (++join->send_records >= join->tmp_table_param.end_write_records && join->do_send_rows)
3034
if (!(join->select_options & OPTION_FOUND_ROWS))
3035
return NESTED_LOOP_QUERY_LIMIT;
3036
join->do_send_rows= 0;
3037
join->unit->select_limit_cnt= HA_POS_ERROR;
3038
return NESTED_LOOP_OK;
3043
return NESTED_LOOP_OK;
3046
/** Group by searching after group record and updating it if possible. */
3047
enum_nested_loop_state end_update(Join *join, JoinTable *, bool end_of_records)
3049
Table *table= join->tmp_table;
3054
return NESTED_LOOP_OK;
3055
if (join->session->getKilled()) // Aborted by user
3057
join->session->send_kill_message();
3058
return NESTED_LOOP_KILLED;
3061
join->found_records++;
3062
copy_fields(&join->tmp_table_param); // Groups are copied twice.
3063
/* Make a key of group index */
3064
for (group=table->group ; group ; group=group->next)
3066
Item *item= *group->item;
3067
item->save_org_in_field(group->field);
3068
/* Store in the used key if the field was 0 */
3069
if (item->maybe_null)
3070
group->buff[-1]= (char) group->field->is_null();
3072
if (!table->cursor->index_read_map(table->getUpdateRecord(),
3073
join->tmp_table_param.group_buff,
3076
{ /* Update old record */
3077
table->restoreRecord();
3078
update_tmptable_sum_func(join->sum_funcs,table);
3079
if ((error= table->cursor->updateRecord(table->getUpdateRecord(),
3080
table->getInsertRecord())))
3082
table->print_error(error,MYF(0));
3083
return NESTED_LOOP_ERROR;
3085
return NESTED_LOOP_OK;
3089
Copy null bits from group key to table
3090
We can't copy all data as the key may have different format
3091
as the row data (for example as with VARCHAR keys)
3093
KeyPartInfo *key_part;
3094
for (group=table->group,key_part=table->key_info[0].key_part;
3096
group=group->next,key_part++)
3098
if (key_part->null_bit)
3099
memcpy(table->getInsertRecord()+key_part->offset, group->buff, 1);
3101
init_tmptable_sum_functions(join->sum_funcs);
3102
if (copy_funcs(join->tmp_table_param.items_to_copy, join->session))
3103
return NESTED_LOOP_ERROR;
3104
if ((error=table->cursor->insertRecord(table->getInsertRecord())))
3106
my_error(ER_USE_SQL_BIG_RESULT, MYF(0));
3107
return NESTED_LOOP_ERROR; // Table is_full error
3109
join->send_records++;
3110
return NESTED_LOOP_OK;
3113
/** Like end_update, but this is done with unique constraints instead of keys. */
3114
enum_nested_loop_state end_unique_update(Join *join, JoinTable *, bool end_of_records)
3116
Table *table= join->tmp_table;
3120
return NESTED_LOOP_OK;
3121
if (join->session->getKilled()) // Aborted by user
3123
join->session->send_kill_message();
3124
return NESTED_LOOP_KILLED;
3127
init_tmptable_sum_functions(join->sum_funcs);
3128
copy_fields(&join->tmp_table_param); // Groups are copied twice.
3129
if (copy_funcs(join->tmp_table_param.items_to_copy, join->session))
3130
return NESTED_LOOP_ERROR;
3132
if (!(error= table->cursor->insertRecord(table->getInsertRecord())))
3133
join->send_records++; // New group
3136
if ((int) table->get_dup_key(error) < 0)
3138
table->print_error(error,MYF(0));
3139
return NESTED_LOOP_ERROR;
3141
if (table->cursor->rnd_pos(table->getUpdateRecord(),table->cursor->dup_ref))
3143
table->print_error(error,MYF(0));
3144
return NESTED_LOOP_ERROR;
3146
table->restoreRecord();
3147
update_tmptable_sum_func(join->sum_funcs,table);
3148
if ((error= table->cursor->updateRecord(table->getUpdateRecord(),
3149
table->getInsertRecord())))
3151
table->print_error(error,MYF(0));
3152
return NESTED_LOOP_ERROR;
3155
return NESTED_LOOP_OK;
3159
allocate group fields or take prepared (cached).
3161
@param main_join join of current select
3162
@param curr_join current join (join of current select or temporary copy
3170
static bool make_group_fields(Join *main_join, Join *curr_join)
3172
if (main_join->group_fields_cache.elements)
3174
curr_join->group_fields= main_join->group_fields_cache;
3175
curr_join->sort_and_group= 1;
3179
if (alloc_group_fields(curr_join, curr_join->group_list))
3181
main_join->group_fields_cache= curr_join->group_fields;
3187
calc how big buffer we need for comparing group entries.
3189
static void calc_group_buffer(Join *join, Order *group)
3191
uint32_t key_length=0, parts=0, null_parts=0;
3195
for (; group ; group=group->next)
3197
Item *group_item= *group->item;
3198
Field *field= group_item->get_tmp_table_field();
3201
enum_field_types type;
3202
if ((type= field->type()) == DRIZZLE_TYPE_BLOB)
3203
key_length+=MAX_BLOB_WIDTH; // Can't be used as a key
3204
else if (type == DRIZZLE_TYPE_VARCHAR)
3205
key_length+= field->field_length + HA_KEY_BLOB_LENGTH;
3207
key_length+= field->pack_length();
3211
switch (group_item->result_type()) {
3213
key_length+= sizeof(double);
3217
key_length+= sizeof(int64_t);
3220
case DECIMAL_RESULT:
3221
key_length+= class_decimal_get_binary_size(group_item->max_length -
3222
(group_item->decimals ? 1 : 0),
3223
group_item->decimals);
3228
enum enum_field_types type= group_item->field_type();
3230
As items represented as DATE/TIME fields in the group buffer
3231
have STRING_RESULT result type, we increase the length
3232
by 8 as maximum pack length of such fields.
3234
if (field::isDateTime(type))
3241
Group strings are taken as varstrings and require an length field.
3242
A field is not yet created by create_tmp_field()
3243
and the sizes should match up.
3245
key_length+= group_item->max_length + HA_KEY_BLOB_LENGTH;
3252
/* This case should never be choosen */
3254
my_error(ER_OUT_OF_RESOURCES, MYF(ME_FATALERROR));
3260
if (group_item->maybe_null)
3264
join->tmp_table_param.group_length=key_length+null_parts;
3265
join->tmp_table_param.group_parts=parts;
3266
join->tmp_table_param.group_null_parts=null_parts;
3270
Get a list of buffers for saveing last group.
3272
Groups are saved in reverse order for easyer check loop.
3274
static bool alloc_group_fields(Join *join, Order *group)
3278
for (; group ; group=group->next)
3280
Cached_item *tmp= new_Cached_item(join->session, *group->item);
3281
if (!tmp || join->group_fields.push_front(tmp))
3285
join->sort_and_group=1; /* Mark for do_select */
3289
static uint32_t cache_record_length(Join *join,uint32_t idx)
3292
JoinTable **pos,**end;
3293
Session *session=join->session;
3295
for (pos=join->best_ref+join->const_tables,end=join->best_ref+idx ;
3299
JoinTable *join_tab= *pos;
3300
if (!join_tab->used_fieldlength) /* Not calced yet */
3301
calc_used_field_length(session, join_tab);
3302
length+=join_tab->used_fieldlength;
3308
Get the number of different row combinations for subset of partial join
3312
join The join structure
3313
idx Number of tables in the partial join order (i.e. the
3314
partial join order is in join->positions[0..idx-1])
3315
found_ref Bitmap of tables for which we need to find # of distinct
3319
Given a partial join order (in join->positions[0..idx-1]) and a subset of
3320
tables within that join order (specified in found_ref), find out how many
3321
distinct row combinations of subset tables will be in the result of the
3324
This is used as follows: Suppose we have a table accessed with a ref-based
3325
method. The ref access depends on current rows of tables in found_ref.
3326
We want to count # of different ref accesses. We assume two ref accesses
3327
will be different if at least one of access parameters is different.
3328
Example: consider a query
3330
SELECT * FROM t1, t2, t3 WHERE t1.key=c1 AND t2.key=c2 AND t3.key=t1.field
3333
t1, ref access on t1.key=c1
3334
t2, ref access on t2.key=c2
3335
t3, ref access on t3.key=t1.field
3337
For t1: n_ref_scans = 1, n_distinct_ref_scans = 1
3338
For t2: n_ref_scans = records_read(t1), n_distinct_ref_scans=1
3339
For t3: n_ref_scans = records_read(t1)*records_read(t2)
3340
n_distinct_ref_scans = #records_read(t1)
3342
The reason for having this function (at least the latest version of it)
3343
is that we need to account for buffering in join execution.
3345
An edge-case example: if we have a non-first table in join accessed via
3346
ref(const) or ref(param) where there is a small number of different
3347
values of param, then the access will likely hit the disk cache and will
3348
not require any disk seeks.
3350
The proper solution would be to assume an LRU disk cache of some size,
3351
calculate probability of cache hits, etc. For now we just count
3352
identical ref accesses as one.
3355
Expected number of row combinations
3357
static double prev_record_reads(Join *join, uint32_t idx, table_map found_ref)
3360
optimizer::Position *pos_end= join->getSpecificPosInPartialPlan(-1);
3361
for (optimizer::Position *pos= join->getSpecificPosInPartialPlan(idx - 1);
3365
if (pos->examinePosition(found_ref))
3367
found_ref|= pos->getRefDependMap();
3369
For the case of "t1 LEFT Join t2 ON ..." where t2 is a const table
3370
with no matching row we will get position[t2].records_read==0.
3371
Actually the size of output is one null-complemented row, therefore
3372
we will use value of 1 whenever we get records_read==0.
3375
- the above case can't occur if inner part of outer join has more
3376
than one table: table with no matches will not be marked as const.
3378
- Ideally we should add 1 to records_read for every possible null-
3379
complemented row. We're not doing it because: 1. it will require
3380
non-trivial code and add overhead. 2. The value of records_read
3381
is an inprecise estimate and adding 1 (or, in the worst case,
3382
#max_nested_outer_joins=64-1) will not make it any more precise.
3384
if (pos->getFanout() > DBL_EPSILON)
3385
found*= pos->getFanout();
3392
Set up join struct according to best position.
3394
static bool get_best_combination(Join *join)
3397
table_map used_tables;
3398
JoinTable *join_tab,*j;
3399
optimizer::KeyUse *keyuse;
3400
uint32_t table_count;
3401
Session *session=join->session;
3402
optimizer::Position cur_pos;
3404
table_count=join->tables;
3405
if (!(join->join_tab=join_tab=
3406
(JoinTable*) session->getMemRoot()->allocate(sizeof(JoinTable)*table_count)))
3409
for (i= 0; i < table_count; i++)
3410
new (join_tab+i) JoinTable();
3414
used_tables= OUTER_REF_TABLE_BIT; // Outer row is already read
3415
for (j=join_tab, tablenr=0 ; tablenr < table_count ; tablenr++,j++)
3418
cur_pos= join->getPosFromOptimalPlan(tablenr);
3419
*j= *cur_pos.getJoinTable();
3420
form=join->table[tablenr]=j->table;
3421
used_tables|= form->map;
3422
form->reginfo.join_tab=j;
3423
if (!*j->on_expr_ref)
3424
form->reginfo.not_exists_optimize=0; // Only with LEFT Join
3425
if (j->type == AM_CONST)
3426
continue; // Handled in make_join_stat..
3431
if (j->type == AM_SYSTEM)
3433
if (j->keys.none() || ! (keyuse= cur_pos.getKeyUse()))
3436
if (tablenr != join->const_tables)
3439
else if (create_ref_for_key(join, j, keyuse, used_tables))
3440
return(true); // Something went wrong
3443
for (i=0 ; i < table_count ; i++)
3444
join->map2table[join->join_tab[i].table->tablenr]=join->join_tab+i;
3445
update_depend_map(join);
3449
/** Save const tables first as used tables. */
3450
static void set_position(Join *join,
3453
optimizer::KeyUse *key)
3455
optimizer::Position tmp_pos(1.0, /* This is a const table */
3460
join->setPosInPartialPlan(idx, tmp_pos);
3462
/* Move the const table as down as possible in best_ref */
3463
JoinTable **pos=join->best_ref+idx+1;
3464
JoinTable *next=join->best_ref[idx];
3465
for (;next != table ; pos++)
3467
JoinTable *tmp=pos[0];
3471
join->best_ref[idx]=table;
3475
Selects and invokes a search strategy for an optimal query plan.
3477
The function checks user-configurable parameters that control the search
3478
strategy for an optimal plan, selects the search method and then invokes
3479
it. Each specific optimization procedure stores the final optimal plan in
3480
the array 'join->best_positions', and the cost of the plan in
3483
@param join pointer to the structure providing all context info for
3485
@param join_tables set of the tables in the query
3492
static bool choose_plan(Join *join, table_map join_tables)
3494
uint32_t search_depth= join->session->variables.optimizer_search_depth;
3495
uint32_t prune_level= join->session->variables.optimizer_prune_level;
3496
bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
3498
join->cur_embedding_map.reset();
3499
reset_nj_counters(join->join_list);
3501
if (SELECT_STRAIGHT_JOIN option is set)
3502
reorder tables so dependent tables come after tables they depend
3503
on, otherwise keep tables in the order they were specified in the query
3505
Apply heuristic: pre-sort all access plans with respect to the number of
3508
internal::my_qsort(join->best_ref + join->const_tables,
3509
join->tables - join->const_tables, sizeof(JoinTable*),
3510
straight_join ? join_tab_cmp_straight : join_tab_cmp);
3513
optimize_straight_join(join, join_tables);
3517
if (search_depth == 0)
3518
/* Automatically determine a reasonable value for 'search_depth' */
3519
search_depth= determine_search_depth(join);
3520
if (greedy_search(join, join_tables, search_depth, prune_level))
3525
Store the cost of this query into a user variable
3526
Don't update last_query_cost for statements that are not "flat joins" :
3527
i.e. they have subqueries, unions or call stored procedures.
3528
TODO: calculate a correct cost for a query with subqueries and UNIONs.
3530
if (join->session->getLex()->is_single_level_stmt())
3531
join->session->status_var.last_query_cost= join->best_read;
3536
Find the best access path for an extension of a partial execution
3537
plan and add this path to the plan.
3539
The function finds the best access path to table 's' from the passed
3540
partial plan where an access path is the general term for any means to
3541
access the data in 's'. An access path may use either an index or a scan,
3542
whichever is cheaper. The input partial plan is passed via the array
3543
'join->positions' of length 'idx'. The chosen access method for 's' and its
3544
cost are stored in 'join->positions[idx]'.
3546
@param join pointer to the structure providing all context info
3548
@param s the table to be joined by the function
3549
@param session thread for the connection that submitted the query
3550
@param remaining_tables set of tables not included into the partial plan yet
3551
@param idx the length of the partial plan
3552
@param record_count estimate for the number of records returned by the
3554
@param read_time the cost of the partial plan
3559
static void best_access_path(Join *join,
3562
table_map remaining_tables,
3564
double record_count,
3567
optimizer::KeyUse *best_key= NULL;
3568
uint32_t best_max_key_part= 0;
3569
bool found_constraint= 0;
3570
double best= DBL_MAX;
3571
double best_time= DBL_MAX;
3572
double records= DBL_MAX;
3573
table_map best_ref_depends_map= 0;
3578
{ /* Use key if possible */
3579
Table *table= s->table;
3580
optimizer::KeyUse *keyuse= NULL;
3581
optimizer::KeyUse *start_key= NULL;
3582
double best_records= DBL_MAX;
3583
uint32_t max_key_part=0;
3585
/* Test how we can use keys */
3586
rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key
3587
for (keyuse= s->keyuse; keyuse->getTable() == table; )
3589
key_part_map found_part= 0;
3590
table_map found_ref= 0;
3591
uint32_t key= keyuse->getKey();
3592
KeyInfo *keyinfo= table->key_info + key;
3593
/* Bitmap of keyparts where the ref access is over 'keypart=const': */
3594
key_part_map const_part= 0;
3595
/* The or-null keypart in ref-or-null access: */
3596
key_part_map ref_or_null_part= 0;
3598
/* Calculate how many key segments of the current key we can use */
3601
do /* For each keypart */
3603
uint32_t keypart= keyuse->getKeypart();
3604
table_map best_part_found_ref= 0;
3605
double best_prev_record_reads= DBL_MAX;
3607
do /* For each way to access the keypart */
3611
if 1. expression doesn't refer to forward tables
3612
2. we won't get two ref-or-null's
3614
if (! (remaining_tables & keyuse->getUsedTables()) &&
3615
! (ref_or_null_part && (keyuse->getOptimizeFlags() &
3616
KEY_OPTIMIZE_REF_OR_NULL)))
3618
found_part|= keyuse->getKeypartMap();
3619
if (! (keyuse->getUsedTables() & ~join->const_table_map))
3620
const_part|= keyuse->getKeypartMap();
3622
double tmp2= prev_record_reads(join, idx, (found_ref |
3623
keyuse->getUsedTables()));
3624
if (tmp2 < best_prev_record_reads)
3626
best_part_found_ref= keyuse->getUsedTables() & ~join->const_table_map;
3627
best_prev_record_reads= tmp2;
3629
if (rec > keyuse->getTableRows())
3630
rec= keyuse->getTableRows();
3632
If there is one 'key_column IS NULL' expression, we can
3633
use this ref_or_null optimisation of this field
3635
if (keyuse->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL)
3636
ref_or_null_part|= keyuse->getKeypartMap();
3640
} while (keyuse->getTable() == table && keyuse->getKey() == key &&
3641
keyuse->getKeypart() == keypart);
3642
found_ref|= best_part_found_ref;
3643
} while (keyuse->getTable() == table && keyuse->getKey() == key);
3646
Assume that that each key matches a proportional part of table.
3649
continue; // Nothing usable found
3651
if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
3652
rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables
3655
found_constraint= 1;
3658
Check if we found full key
3660
if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&
3663
max_key_part= UINT32_MAX;
3664
if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
3666
tmp = prev_record_reads(join, idx, found_ref);
3672
{ /* We found a const key */
3674
ReuseRangeEstimateForRef-1:
3675
We get here if we've found a ref(const) (c_i are constants):
3676
"(keypart1=c1) AND ... AND (keypartN=cN)" [ref_const_cond]
3678
If range optimizer was able to construct a "range"
3679
access on this index, then its condition "quick_cond" was
3680
eqivalent to ref_const_cond (*), and we can re-use E(#rows)
3681
from the range optimizer.
3683
Proof of (*): By properties of range and ref optimizers
3684
quick_cond will be equal or tighther than ref_const_cond.
3685
ref_const_cond already covers "smallest" possible interval -
3686
a singlepoint interval over all keyparts. Therefore,
3687
quick_cond is equivalent to ref_const_cond (if it was an
3688
empty interval we wouldn't have got here).
3690
if (table->quick_keys.test(key))
3691
records= (double) table->quick_rows[key];
3694
/* quick_range couldn't use key! */
3695
records= (double) s->records/rec;
3700
if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
3701
{ /* Prefer longer keys */
3703
((double) s->records / (double) rec *
3705
((double) (table->getShare()->max_key_length-keyinfo->key_length) /
3706
(double) table->getShare()->max_key_length)));
3708
records=2.0; /* Can't be as good as a unique */
3711
ReuseRangeEstimateForRef-2: We get here if we could not reuse
3712
E(#rows) from range optimizer. Make another try:
3714
If range optimizer produced E(#rows) for a prefix of the ref
3715
access we're considering, and that E(#rows) is lower then our
3716
current estimate, make an adjustment. The criteria of when we
3717
can make an adjustment is a special case of the criteria used
3718
in ReuseRangeEstimateForRef-3.
3720
if (table->quick_keys.test(key) &&
3721
const_part & (1 << table->quick_key_parts[key]) &&
3722
table->quick_n_ranges[key] == 1 &&
3723
records > (double) table->quick_rows[key])
3725
records= (double) table->quick_rows[key];
3728
/* Limit the number of matched rows */
3730
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
3731
if (table->covering_keys.test(key))
3733
/* we can use only index tree */
3734
tmp= record_count * table->cursor->index_only_read_time(key, tmp);
3737
tmp= record_count * min(tmp,s->worst_seeks);
3743
Use as much key-parts as possible and a uniq key is better
3744
than a not unique key
3745
Set tmp to (previous record count) * (records / combination)
3747
if ((found_part & 1) &&
3748
(!(table->index_flags(key) & HA_ONLY_WHOLE_INDEX) ||
3749
found_part == PREV_BITS(uint, keyinfo->key_parts)))
3751
max_key_part= max_part_bit(found_part);
3753
ReuseRangeEstimateForRef-3:
3754
We're now considering a ref[or_null] access via
3755
(t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR
3756
(same-as-above but with one cond replaced
3757
with "t.keypart_i IS NULL")] (**)
3759
Try re-using E(#rows) from "range" optimizer:
3760
We can do so if "range" optimizer used the same intervals as
3761
in (**). The intervals used by range optimizer may be not
3762
available at this point (as "range" access might have choosen to
3763
create quick select over another index), so we can't compare
3764
them to (**). We'll make indirect judgements instead.
3765
The sufficient conditions for re-use are:
3766
(C1) All e_i in (**) are constants, i.e. found_ref==false. (if
3767
this is not satisfied we have no way to know which ranges
3768
will be actually scanned by 'ref' until we execute the
3770
(C2) max #key parts in 'range' access == K == max_key_part (this
3771
is apparently a necessary requirement)
3773
We also have a property that "range optimizer produces equal or
3774
tighter set of scan intervals than ref(const) optimizer". Each
3775
of the intervals in (**) are "tightest possible" intervals when
3776
one limits itself to using keyparts 1..K (which we do in #2).
3777
From here it follows that range access used either one, or
3778
both of the (I1) and (I2) intervals:
3780
(t.keypart1=c1 AND ... AND t.keypartK=eK) (I1)
3781
(same-as-above but with one cond replaced
3782
with "t.keypart_i IS NULL") (I2)
3784
The remaining part is to exclude the situation where range
3785
optimizer used one interval while we're considering
3786
ref-or-null and looking for estimate for two intervals. This
3787
is done by last limitation:
3789
(C3) "range optimizer used (have ref_or_null?2:1) intervals"
3791
if (table->quick_keys.test(key) && !found_ref && //(C1)
3792
table->quick_key_parts[key] == max_key_part && //(C2)
3793
table->quick_n_ranges[key] == 1+((ref_or_null_part)?1:0)) //(C3)
3795
tmp= records= (double) table->quick_rows[key];
3799
/* Check if we have statistic about the distribution */
3800
if ((records= keyinfo->rec_per_key[max_key_part-1]))
3803
Fix for the case where the index statistics is too
3805
(1) We're considering ref(const) and there is quick select
3807
(2) and that quick select uses more keyparts (i.e. it will
3808
scan equal/smaller interval then this ref(const))
3809
(3) and E(#rows) for quick select is higher then our
3812
We'll use E(#rows) from quick select.
3814
Q: Why do we choose to use 'ref'? Won't quick select be
3815
cheaper in some cases ?
3816
TODO: figure this out and adjust the plan choice if needed.
3818
if (!found_ref && table->quick_keys.test(key) && // (1)
3819
table->quick_key_parts[key] > max_key_part && // (2)
3820
records < (double)table->quick_rows[key]) // (3)
3821
records= (double)table->quick_rows[key];
3828
Assume that the first key part matches 1% of the cursor
3829
and that the whole key matches 10 (duplicates) or 1
3831
Assume also that more key matches proportionally more
3833
This gives the formula:
3834
records = (x * (b-a) + a*c-b)/(c-1)
3836
b = records matched by whole key
3837
a = records matched by first key part (1% of all records?)
3838
c = number of key parts in key
3839
x = used key parts (1 <= x <= c)
3842
if (!(rec_per_key=(double)
3843
keyinfo->rec_per_key[keyinfo->key_parts-1]))
3844
rec_per_key=(double) s->records/rec+1;
3848
else if (rec_per_key/(double) s->records >= 0.01)
3852
double a=s->records*0.01;
3853
if (keyinfo->key_parts > 1)
3854
tmp= (max_key_part * (rec_per_key - a) +
3855
a*keyinfo->key_parts - rec_per_key)/
3856
(keyinfo->key_parts-1);
3859
set_if_bigger(tmp,1.0);
3861
records = (uint32_t) tmp;
3864
if (ref_or_null_part)
3866
/* We need to do two key searches to find key */
3872
ReuseRangeEstimateForRef-4: We get here if we could not reuse
3873
E(#rows) from range optimizer. Make another try:
3875
If range optimizer produced E(#rows) for a prefix of the ref
3876
access we're considering, and that E(#rows) is lower then our
3877
current estimate, make the adjustment.
3879
The decision whether we can re-use the estimate from the range
3880
optimizer is the same as in ReuseRangeEstimateForRef-3,
3881
applied to first table->quick_key_parts[key] key parts.
3883
if (table->quick_keys.test(key) &&
3884
table->quick_key_parts[key] <= max_key_part &&
3885
const_part & (1 << table->quick_key_parts[key]) &&
3886
table->quick_n_ranges[key] == 1 + ((ref_or_null_part &
3887
const_part) ? 1 : 0) &&
3888
records > (double) table->quick_rows[key])
3890
tmp= records= (double) table->quick_rows[key];
3894
/* Limit the number of matched rows */
3895
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
3896
if (table->covering_keys.test(key))
3898
/* we can use only index tree */
3899
tmp= record_count * table->cursor->index_only_read_time(key, tmp);
3902
tmp= record_count * min(tmp,s->worst_seeks);
3905
tmp= best_time; // Do nothing
3909
if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
3911
best_time= tmp + records/(double) TIME_FOR_COMPARE;
3913
best_records= records;
3914
best_key= start_key;
3915
best_max_key_part= max_key_part;
3916
best_ref_depends_map= found_ref;
3919
records= best_records;
3923
Don't test table scan if it can't be better.
3924
Prefer key lookup if we would use the same key for scanning.
3926
Don't do a table scan on InnoDB tables, if we can read the used
3927
parts of the row from any of the used index.
3928
This is because table scans uses index and we would not win
3929
anything by using a table scan.
3931
A word for word translation of the below if-statement in sergefp's
3932
understanding: we check if we should use table scan if:
3933
(1) The found 'ref' access produces more records than a table scan
3934
(or index scan, or quick select), or 'ref' is more expensive than
3936
(2) This doesn't hold: the best way to perform table scan is to to perform
3937
'range' access using index IDX, and the best way to perform 'ref'
3938
access is to use the same index IDX, with the same or more key parts.
3939
(note: it is not clear how this rule is/should be extended to
3940
index_merge quick selects)
3941
(3) See above note about InnoDB.
3942
(4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access
3943
path, but there is no quick select)
3944
If the condition in the above brackets holds, then the only possible
3945
"table scan" access method is ALL/index (there is no quick select).
3946
Since we have a 'ref' access path, and FORCE INDEX instructs us to
3947
choose it over ALL/index, there is no need to consider a full table
3950
if ((records >= s->found_records || best > s->read_time) && // (1)
3951
! (s->quick && best_key && s->quick->index == best_key->getKey() && // (2)
3952
best_max_key_part >= s->table->quick_key_parts[best_key->getKey()]) &&// (2)
3953
! ((s->table->cursor->getEngine()->check_flag(HTON_BIT_TABLE_SCAN_ON_INDEX)) && // (3)
3954
! s->table->covering_keys.none() && best_key && !s->quick) && // (3)
3955
! (s->table->force_index && best_key && !s->quick)) // (4)
3956
{ // Check full join
3957
ha_rows rnd_records= s->found_records;
3959
If there is a filtering condition on the table (i.e. ref analyzer found
3960
at least one "table.keyXpartY= exprZ", where exprZ refers only to tables
3961
preceding this table in the join order we're now considering), then
3962
assume that 25% of the rows will be filtered out by this condition.
3964
This heuristic is supposed to force tables used in exprZ to be before
3965
this table in join order.
3967
if (found_constraint)
3968
rnd_records-= rnd_records/4;
3971
If applicable, get a more accurate estimate. Don't use the two
3974
if (s->table->quick_condition_rows != s->found_records)
3975
rnd_records= s->table->quick_condition_rows;
3978
Range optimizer never proposes a RANGE if it isn't better
3979
than FULL: so if RANGE is present, it's always preferred to FULL.
3980
Here we estimate its cost.
3986
- read record range through 'quick'
3987
- skip rows which does not satisfy WHERE constraints
3989
We take into account possible use of join cache for ALL/index
3990
access (see first else-branch below), but we don't take it into
3991
account here for range/index_merge access. Find out why this is so.
3994
(s->quick->read_time +
3995
(s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
3999
/* Estimate cost of reading table. */
4000
tmp= s->table->cursor->scan_time();
4001
if (s->table->map & join->outer_join) // Can't use join cache
4004
For each record we have to:
4005
- read the whole table record
4006
- skip rows which does not satisfy join condition
4010
(s->records - rnd_records)/(double) TIME_FOR_COMPARE);
4014
/* We read the table as many times as join buffer becomes full. */
4015
tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
4017
(double) session->variables.join_buff_size));
4019
We don't make full cartesian product between rows in the scanned
4020
table and existing records because we skip all rows from the
4021
scanned table, which does not satisfy join condition when
4022
we read the table (see flush_cached_records for details). Here we
4023
take into account cost to read and skip these records.
4025
tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
4030
We estimate the cost of evaluating WHERE clause for found records
4031
as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus
4032
tmp give us total cost of using Table SCAN
4034
if (best == DBL_MAX ||
4035
(tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records <
4036
best + record_count/(double) TIME_FOR_COMPARE*records))
4039
If the table has a range (s->quick is set) make_join_select()
4040
will ensure that this will be used
4043
records= rnd_records;
4045
/* range/index_merge/ALL/index access method are "independent", so: */
4046
best_ref_depends_map= 0;
4050
/* Update the cost information for the current partial plan */
4051
optimizer::Position tmp_pos(records,
4055
best_ref_depends_map);
4056
join->setPosInPartialPlan(idx, tmp_pos);
4059
idx == join->const_tables &&
4060
s->table == join->sort_by_table &&
4061
join->unit->select_limit_cnt >= records)
4062
join->sort_by_table= (Table*) 1; // Must use temporary table
4068
Select the best ways to access the tables in a query without reordering them.
4070
Find the best access paths for each query table and compute their costs
4071
according to their order in the array 'join->best_ref' (thus without
4072
reordering the join tables). The function calls sequentially
4073
'best_access_path' for each table in the query to select the best table
4074
access method. The final optimal plan is stored in the array
4075
'join->best_positions', and the corresponding cost in 'join->best_read'.
4077
@param join pointer to the structure providing all context info for
4079
@param join_tables set of the tables in the query
4082
This function can be applied to:
4083
- queries with STRAIGHT_JOIN
4084
- internally to compute the cost of an arbitrary QEP
4086
Thus 'optimize_straight_join' can be used at any stage of the query
4087
optimization process to finalize a QEP as it is.
4089
static void optimize_straight_join(Join *join, table_map join_tables)
4092
optimizer::Position partial_pos;
4093
uint32_t idx= join->const_tables;
4094
double record_count= 1.0;
4095
double read_time= 0.0;
4097
for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
4099
/* Find the best access method from 's' to the current partial plan */
4100
best_access_path(join, s, join->session, join_tables, idx,
4101
record_count, read_time);
4102
/* compute the cost of the new plan extended with 's' */
4103
partial_pos= join->getPosFromPartialPlan(idx);
4104
record_count*= partial_pos.getFanout();
4105
read_time+= partial_pos.getCost();
4106
join_tables&= ~(s->table->map);
4110
read_time+= record_count / (double) TIME_FOR_COMPARE;
4111
partial_pos= join->getPosFromPartialPlan(join->const_tables);
4112
if (join->sort_by_table &&
4113
partial_pos.hasTableForSorting(join->sort_by_table))
4114
read_time+= record_count; // We have to make a temp table
4115
join->copyPartialPlanIntoOptimalPlan(idx);
4116
join->best_read= read_time;
4120
Find a good, possibly optimal, query execution plan (QEP) by a greedy search.
4122
The search procedure uses a hybrid greedy/exhaustive search with controlled
4123
exhaustiveness. The search is performed in N = card(remaining_tables)
4124
steps. Each step evaluates how promising is each of the unoptimized tables,
4125
selects the most promising table, and extends the current partial QEP with
4126
that table. Currenly the most 'promising' table is the one with least
4127
expensive extension.\
4129
There are two extreme cases:
4130
-# When (card(remaining_tables) < search_depth), the estimate finds the
4131
best complete continuation of the partial QEP. This continuation can be
4132
used directly as a result of the search.
4133
-# When (search_depth == 1) the 'best_extension_by_limited_search'
4134
consideres the extension of the current QEP with each of the remaining
4137
All other cases are in-between these two extremes. Thus the parameter
4138
'search_depth' controlls the exhaustiveness of the search. The higher the
4139
value, the longer the optimizaton time and possibly the better the
4140
resulting plan. The lower the value, the fewer alternative plans are
4141
estimated, but the more likely to get a bad QEP.
4143
All intermediate and final results of the procedure are stored in 'join':
4144
- join->positions : modified for every partial QEP that is explored
4145
- join->best_positions: modified for the current best complete QEP
4146
- join->best_read : modified for the current best complete QEP
4147
- join->best_ref : might be partially reordered
4149
The final optimal plan is stored in 'join->best_positions', and its
4150
corresponding cost in 'join->best_read'.
4153
The following pseudocode describes the algorithm of 'greedy_search':
4156
procedure greedy_search
4157
input: remaining_tables
4162
(t, a) = best_extension(pplan, remaining_tables);
4163
pplan = concat(pplan, (t, a));
4164
remaining_tables = remaining_tables - t;
4165
} while (remaining_tables != {})
4170
where 'best_extension' is a placeholder for a procedure that selects the
4171
most "promising" of all tables in 'remaining_tables'.
4172
Currently this estimate is performed by calling
4173
'best_extension_by_limited_search' to evaluate all extensions of the
4174
current QEP of size 'search_depth', thus the complexity of 'greedy_search'
4175
mainly depends on that of 'best_extension_by_limited_search'.
4178
If 'best_extension()' == 'best_extension_by_limited_search()', then the
4179
worst-case complexity of this algorithm is <=
4180
O(N*N^search_depth/search_depth). When serch_depth >= N, then the
4181
complexity of greedy_search is O(N!).
4184
In the future, 'greedy_search' might be extended to support other
4185
implementations of 'best_extension', e.g. some simpler quadratic procedure.
4187
@param join pointer to the structure providing all context info
4189
@param remaining_tables set of tables not included into the partial plan yet
4190
@param search_depth controlls the exhaustiveness of the search
4191
@param prune_level the pruning heuristics that should be applied during
4199
static bool greedy_search(Join *join,
4200
table_map remaining_tables,
4201
uint32_t search_depth,
4202
uint32_t prune_level)
4204
double record_count= 1.0;
4205
double read_time= 0.0;
4206
uint32_t idx= join->const_tables; // index into 'join->best_ref'
4208
uint32_t size_remain; // cardinality of remaining_tables
4209
optimizer::Position best_pos;
4210
JoinTable *best_table; // the next plan node to be added to the curr QEP
4212
/* number of tables that remain to be optimized */
4213
size_remain= internal::my_count_bits(remaining_tables);
4216
/* Find the extension of the current QEP with the lowest cost */
4217
join->best_read= DBL_MAX;
4218
if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,
4219
read_time, search_depth, prune_level))
4222
if (size_remain <= search_depth)
4225
'join->best_positions' contains a complete optimal extension of the
4226
current partial QEP.
4231
/* select the first table in the optimal extension as most promising */
4232
best_pos= join->getPosFromOptimalPlan(idx);
4233
best_table= best_pos.getJoinTable();
4235
Each subsequent loop of 'best_extension_by_limited_search' uses
4236
'join->positions' for cost estimates, therefore we have to update its
4239
join->setPosInPartialPlan(idx, best_pos);
4242
We need to make best_extension_by_limited_search aware of the fact
4243
that it's not starting from top level, but from a rather specific
4244
position in the list of nested joins.
4246
check_interleaving_with_nj (best_table);
4250
/* find the position of 'best_table' in 'join->best_ref' */
4252
JoinTable *pos= join->best_ref[best_idx];
4253
while (pos && best_table != pos)
4254
pos= join->best_ref[++best_idx];
4255
assert((pos != NULL)); // should always find 'best_table'
4256
/* move 'best_table' at the first free position in the array of joins */
4257
std::swap(join->best_ref[idx], join->best_ref[best_idx]);
4259
/* compute the cost of the new plan extended with 'best_table' */
4260
optimizer::Position partial_pos= join->getPosFromPartialPlan(idx);
4261
record_count*= partial_pos.getFanout();
4262
read_time+= partial_pos.getCost();
4264
remaining_tables&= ~(best_table->table->map);
4272
Find a good, possibly optimal, query execution plan (QEP) by a possibly
4275
The procedure searches for the optimal ordering of the query tables in set
4276
'remaining_tables' of size N, and the corresponding optimal access paths to
4277
each table. The choice of a table order and an access path for each table
4278
constitutes a query execution plan (QEP) that fully specifies how to
4281
The maximal size of the found plan is controlled by the parameter
4282
'search_depth'. When search_depth == N, the resulting plan is complete and
4283
can be used directly as a QEP. If search_depth < N, the found plan consists
4284
of only some of the query tables. Such "partial" optimal plans are useful
4285
only as input to query optimization procedures, and cannot be used directly
4288
The algorithm begins with an empty partial plan stored in 'join->positions'
4289
and a set of N tables - 'remaining_tables'. Each step of the algorithm
4290
evaluates the cost of the partial plan extended by all access plans for
4291
each of the relations in 'remaining_tables', expands the current partial
4292
plan with the access plan that results in lowest cost of the expanded
4293
partial plan, and removes the corresponding relation from
4294
'remaining_tables'. The algorithm continues until it either constructs a
4295
complete optimal plan, or constructs an optimal plartial plan with size =
4298
The final optimal plan is stored in 'join->best_positions'. The
4299
corresponding cost of the optimal plan is in 'join->best_read'.
4302
The procedure uses a recursive depth-first search where the depth of the
4303
recursion (and thus the exhaustiveness of the search) is controlled by the
4304
parameter 'search_depth'.
4307
The pseudocode below describes the algorithm of
4308
'best_extension_by_limited_search'. The worst-case complexity of this
4309
algorithm is O(N*N^search_depth/search_depth). When serch_depth >= N, then
4310
the complexity of greedy_search is O(N!).
4313
procedure best_extension_by_limited_search(
4314
pplan in, // in, partial plan of tables-joined-so-far
4315
pplan_cost, // in, cost of pplan
4316
remaining_tables, // in, set of tables not referenced in pplan
4317
best_plan_so_far, // in/out, best plan found so far
4318
best_plan_so_far_cost,// in/out, cost of best_plan_so_far
4319
search_depth) // in, maximum size of the plans being considered
4321
for each table T from remaining_tables
4323
// Calculate the cost of using table T as above
4324
cost = complex-series-of-calculations;
4326
// Add the cost to the cost so far.
4329
if (pplan_cost >= best_plan_so_far_cost)
4330
// pplan_cost already too great, stop search
4333
pplan= expand pplan by best_access_method;
4334
remaining_tables= remaining_tables - table T;
4335
if (remaining_tables is not an empty set
4339
best_extension_by_limited_search(pplan, pplan_cost,
4342
best_plan_so_far_cost,
4347
best_plan_so_far_cost= pplan_cost;
4348
best_plan_so_far= pplan;
4355
When 'best_extension_by_limited_search' is called for the first time,
4356
'join->best_read' must be set to the largest possible value (e.g. DBL_MAX).
4357
The actual implementation provides a way to optionally use pruning
4358
heuristic (controlled by the parameter 'prune_level') to reduce the search
4359
space by skipping some partial plans.
4362
The parameter 'search_depth' provides control over the recursion
4363
depth, and thus the size of the resulting optimal plan.
4365
@param join pointer to the structure providing all context info
4367
@param remaining_tables set of tables not included into the partial plan yet
4368
@param idx length of the partial QEP in 'join->positions';
4369
since a depth-first search is used, also corresponds
4370
to the current depth of the search tree;
4371
also an index in the array 'join->best_ref';
4372
@param record_count estimate for the number of records returned by the
4374
@param read_time the cost of the best partial plan
4375
@param search_depth maximum depth of the recursion and thus size of the
4377
(0 < search_depth <= join->tables+1).
4378
@param prune_level pruning heuristics that should be applied during
4380
(values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS)
4387
static bool best_extension_by_limited_search(Join *join,
4388
table_map remaining_tables,
4390
double record_count,
4392
uint32_t search_depth,
4393
uint32_t prune_level)
4395
Session *session= join->session;
4396
if (session->getKilled()) // Abort
4400
'join' is a partial plan with lower cost than the best plan so far,
4401
so continue expanding it further with the tables in 'remaining_tables'.
4404
double best_record_count= DBL_MAX;
4405
double best_read_time= DBL_MAX;
4406
optimizer::Position partial_pos;
4408
for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
4410
table_map real_table_bit= s->table->map;
4411
if ((remaining_tables & real_table_bit) &&
4412
! (remaining_tables & s->dependent) &&
4413
(! idx || ! check_interleaving_with_nj(s)))
4415
double current_record_count, current_read_time;
4418
psergey-insideout-todo:
4419
when best_access_path() detects it could do an InsideOut scan or
4420
some other scan, have it return an insideout scan and a flag that
4421
requests to "fork" this loop iteration. (Q: how does that behave
4422
when the depth is insufficient??)
4424
/* Find the best access method from 's' to the current partial plan */
4425
best_access_path(join, s, session, remaining_tables, idx,
4426
record_count, read_time);
4427
/* Compute the cost of extending the plan with 's' */
4428
partial_pos= join->getPosFromPartialPlan(idx);
4429
current_record_count= record_count * partial_pos.getFanout();
4430
current_read_time= read_time + partial_pos.getCost();
4432
/* Expand only partial plans with lower cost than the best QEP so far */
4433
if ((current_read_time +
4434
current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
4436
restore_prev_nj_state(s);
4441
Prune some less promising partial plans. This heuristic may miss
4442
the optimal QEPs, thus it results in a non-exhaustive search.
4444
if (prune_level == 1)
4446
if (best_record_count > current_record_count ||
4447
best_read_time > current_read_time ||
4448
(idx == join->const_tables && s->table == join->sort_by_table)) // 's' is the first table in the QEP
4450
if (best_record_count >= current_record_count &&
4451
best_read_time >= current_read_time &&
4452
/* TODO: What is the reasoning behind this condition? */
4453
(! (s->key_dependent & remaining_tables) ||
4454
partial_pos.isConstTable()))
4456
best_record_count= current_record_count;
4457
best_read_time= current_read_time;
4462
restore_prev_nj_state(s);
4467
if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )
4468
{ /* Recursively expand the current partial plan */
4469
std::swap(join->best_ref[idx], *pos);
4470
if (best_extension_by_limited_search(join,
4471
remaining_tables & ~real_table_bit,
4473
current_record_count,
4478
std::swap(join->best_ref[idx], *pos);
4482
'join' is either the best partial QEP with 'search_depth' relations,
4483
or the best complete QEP so far, whichever is smaller.
4485
partial_pos= join->getPosFromPartialPlan(join->const_tables);
4486
current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
4487
if (join->sort_by_table &&
4488
partial_pos.hasTableForSorting(join->sort_by_table))
4489
/* We have to make a temp table */
4490
current_read_time+= current_record_count;
4491
if ((search_depth == 1) || (current_read_time < join->best_read))
4493
join->copyPartialPlanIntoOptimalPlan(idx + 1);
4494
join->best_read= current_read_time - 0.001;
4497
restore_prev_nj_state(s);
4504
Heuristic procedure to automatically guess a reasonable degree of
4505
exhaustiveness for the greedy search procedure.
4507
The procedure estimates the optimization time and selects a search depth
4508
big enough to result in a near-optimal QEP, that doesn't take too long to
4509
find. If the number of tables in the query exceeds some constant, then
4510
search_depth is set to this constant.
4512
@param join pointer to the structure providing all context info for
4516
This is an extremely simplistic implementation that serves as a stub for a
4517
more advanced analysis of the join. Ideally the search depth should be
4518
determined by learning from previous query optimizations, because it will
4519
depend on the CPU power (and other factors).
4522
this value should be determined dynamically, based on statistics:
4523
uint32_t max_tables_for_exhaustive_opt= 7;
4526
this value could be determined by some mapping of the form:
4527
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
4530
A positive integer that specifies the search depth (and thus the
4531
exhaustiveness) of the depth-first search algorithm used by
4534
static uint32_t determine_search_depth(Join *join)
4536
uint32_t table_count= join->tables - join->const_tables;
4537
uint32_t search_depth;
4538
/* TODO: this value should be determined dynamically, based on statistics: */
4539
uint32_t max_tables_for_exhaustive_opt= 7;
4541
if (table_count <= max_tables_for_exhaustive_opt)
4542
search_depth= table_count+1; // use exhaustive for small number of tables
4545
TODO: this value could be determined by some mapping of the form:
4546
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
4548
search_depth= max_tables_for_exhaustive_opt; // use greedy search
4550
return search_depth;
4553
static bool make_simple_join(Join *join,Table *tmp_table)
4556
JoinTable *join_tab;
4559
Reuse Table * and JoinTable if already allocated by a previous call
4560
to this function through Join::exec (may happen for sub-queries).
4562
if (!join->table_reexec)
4564
if (!(join->table_reexec= (Table**) join->session->getMemRoot()->allocate(sizeof(Table*))))
4567
join->tmp_join->table_reexec= join->table_reexec;
4569
if (!join->join_tab_reexec)
4571
if (!(join->join_tab_reexec=
4572
(JoinTable*) join->session->getMemRoot()->allocate(sizeof(JoinTable))))
4574
new (join->join_tab_reexec) JoinTable();
4576
join->tmp_join->join_tab_reexec= join->join_tab_reexec;
4578
tableptr= join->table_reexec;
4579
join_tab= join->join_tab_reexec;
4581
join->join_tab=join_tab;
4582
join->table=tableptr; tableptr[0]=tmp_table;
4584
join->const_tables=0;
4585
join->const_table_map=0;
4586
join->tmp_table_param.field_count= join->tmp_table_param.sum_func_count=
4587
join->tmp_table_param.func_count=0;
4588
join->tmp_table_param.copy_field=join->tmp_table_param.copy_field_end=0;
4589
join->first_record=join->sort_and_group=0;
4590
join->send_records=(ha_rows) 0;
4592
join->row_limit=join->unit->select_limit_cnt;
4593
join->do_send_rows = (join->row_limit) ? 1 : 0;
4595
join_tab->table=tmp_table;
4597
join_tab->select_cond=0;
4599
join_tab->type= AM_ALL; /* Map through all records */
4600
join_tab->keys.set(); /* test everything in quick */
4602
join_tab->on_expr_ref=0;
4603
join_tab->last_inner= 0;
4604
join_tab->first_unmatched= 0;
4605
join_tab->ref.key = -1;
4606
join_tab->not_used_in_distinct=0;
4607
join_tab->read_first_record= join_init_read_record;
4608
join_tab->join=join;
4609
join_tab->ref.key_parts= 0;
4610
join_tab->read_record.init();
4611
tmp_table->status=0;
4612
tmp_table->null_row=0;
4618
Fill in outer join related info for the execution plan structure.
4620
For each outer join operation left after simplification of the
4621
original query the function set up the following pointers in the linear
4622
structure join->join_tab representing the selected execution plan.
4623
The first inner table t0 for the operation is set to refer to the last
4624
inner table tk through the field t0->last_inner.
4625
Any inner table ti for the operation are set to refer to the first
4626
inner table ti->first_inner.
4627
The first inner table t0 for the operation is set to refer to the
4628
first inner table of the embedding outer join operation, if there is any,
4629
through the field t0->first_upper.
4630
The on expression for the outer join operation is attached to the
4631
corresponding first inner table through the field t0->on_expr_ref.
4632
Here ti are structures of the JoinTable type.
4634
EXAMPLE. For the query:
4638
(t2, t3 LEFT JOIN t4 ON t3.a=t4.a)
4639
ON (t1.a=t2.a AND t1.b=t3.b)
4643
given the execution plan with the table order t1,t2,t3,t4
4644
is selected, the following references will be set;
4645
t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2]
4646
t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2],
4647
on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to
4648
*t2->on_expr_ref, while t3.a=t4.a will be attached to *t4->on_expr_ref.
4650
@param join reference to the info fully describing the query
4653
The function assumes that the simplification procedure has been
4654
already applied to the join query (see simplify_joins).
4655
This function can be called only after the execution plan
4658
static void make_outerjoin_info(Join *join)
4660
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
4662
JoinTable *tab=join->join_tab+i;
4663
Table *table=tab->table;
4664
TableList *tbl= table->pos_in_table_list;
4665
TableList *embedding= tbl->getEmbedding();
4667
if (tbl->outer_join)
4670
Table tab is the only one inner table for outer join.
4671
(Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a
4672
is in the query above.)
4674
tab->last_inner= tab->first_inner= tab;
4675
tab->on_expr_ref= &tbl->on_expr;
4676
tab->cond_equal= tbl->cond_equal;
4678
tab->first_upper= embedding->getNestedJoin()->first_nested;
4680
for ( ; embedding ; embedding= embedding->getEmbedding())
4682
/* Ignore sj-nests: */
4683
if (!embedding->on_expr)
4685
NestedJoin *nested_join= embedding->getNestedJoin();
4686
if (!nested_join->counter_)
4689
Table tab is the first inner table for nested_join.
4690
Save reference to it in the nested join structure.
4692
nested_join->first_nested= tab;
4693
tab->on_expr_ref= &embedding->on_expr;
4694
tab->cond_equal= tbl->cond_equal;
4695
if (embedding->getEmbedding())
4696
tab->first_upper= embedding->getEmbedding()->getNestedJoin()->first_nested;
4698
if (!tab->first_inner)
4699
tab->first_inner= nested_join->first_nested;
4700
if (++nested_join->counter_ < nested_join->join_list.elements)
4702
/* Table tab is the last inner table for nested join. */
4703
nested_join->first_nested->last_inner= tab;
4709
static bool make_join_select(Join *join,
4710
optimizer::SqlSelect *select,
4713
Session *session= join->session;
4714
optimizer::Position cur_pos;
4717
add_not_null_conds(join);
4718
table_map used_tables;
4719
if (cond) /* Because of QUICK_GROUP_MIN_MAX_SELECT */
4720
{ /* there may be a select without a cond. */
4721
if (join->tables > 1)
4722
cond->update_used_tables(); // Tablenr may have changed
4723
if (join->const_tables == join->tables &&
4724
session->getLex()->current_select->master_unit() ==
4725
&session->getLex()->unit) // not upper level SELECT
4726
join->const_table_map|=RAND_TABLE_BIT;
4727
{ // Check const tables
4729
make_cond_for_table(cond,
4730
join->const_table_map,
4732
for (JoinTable *tab= join->join_tab+join->const_tables;
4733
tab < join->join_tab+join->tables ; tab++)
4735
if (*tab->on_expr_ref)
4737
JoinTable *cond_tab= tab->first_inner;
4738
COND *tmp= make_cond_for_table(*tab->on_expr_ref,
4739
join->const_table_map,
4743
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
4746
tmp->quick_fix_field();
4747
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
4748
new Item_cond_and(cond_tab->select_cond,
4750
if (! cond_tab->select_cond)
4752
cond_tab->select_cond->quick_fix_field();
4755
if (const_cond && ! const_cond->val_int())
4757
return 1; // Impossible const condition
4761
used_tables=((select->const_tables=join->const_table_map) |
4762
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
4763
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
4765
JoinTable *tab=join->join_tab+i;
4767
first_inner is the X in queries like:
4768
SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X
4770
JoinTable *first_inner_tab= tab->first_inner;
4771
table_map current_map= tab->table->map;
4772
bool use_quick_range=0;
4776
Following force including random expression in last table condition.
4777
It solve problem with select like SELECT * FROM t1 WHERE rand() > 0.5
4779
if (i == join->tables-1)
4780
current_map|= OUTER_REF_TABLE_BIT | RAND_TABLE_BIT;
4781
used_tables|=current_map;
4783
if (tab->type == AM_REF && tab->quick &&
4784
(uint32_t) tab->ref.key == tab->quick->index &&
4785
tab->ref.key_length < tab->quick->max_used_key_length)
4787
/* Range uses longer key; Use this instead of ref on key */
4792
tab->ref.key_parts= 0; // Don't use ref key.
4793
cur_pos= join->getPosFromOptimalPlan(i);
4794
cur_pos.setFanout(tab->quick->records);
4796
We will use join cache here : prevent sorting of the first
4797
table only and sort at the end.
4799
if (i != join->const_tables && join->tables > join->const_tables + 1)
4803
if (join->full_join and not session->getLex()->current_select->is_cross and not cond)
4805
my_error(ER_CARTESIAN_JOIN_ATTEMPTED, MYF(0));
4811
tmp= make_cond_for_table(cond,used_tables,current_map, 0);
4812
if (cond && !tmp && tab->quick)
4814
if (tab->type != AM_ALL)
4817
Don't use the quick method
4818
We come here in the case where we have 'key=constant' and
4819
the test is removed by make_cond_for_table()
4827
Hack to handle the case where we only refer to a table
4828
in the ON part of an OUTER JOIN. In this case we want the code
4829
below to check if we should use 'quick' instead.
4831
tmp= new Item_int((int64_t) 1,1); // Always true
4835
if (tmp || !cond || tab->type == AM_REF || tab->type == AM_REF_OR_NULL ||
4836
tab->type == AM_EQ_REF)
4838
optimizer::SqlSelect *sel= tab->select= ((optimizer::SqlSelect*)
4839
session->getMemRoot()->duplicate((unsigned char*) select,
4842
return 1; // End of memory
4844
If tab is an inner table of an outer join operation,
4845
add a match guard to the pushed down predicate.
4846
The guard will turn the predicate on only after
4847
the first match for outer tables is encountered.
4852
Because of QUICK_GROUP_MIN_MAX_SELECT there may be a select without
4853
a cond, so neutralize the hack above.
4855
if (! (tmp= add_found_match_trig_cond(first_inner_tab, tmp, 0)))
4857
tab->select_cond=sel->cond=tmp;
4860
tab->select_cond= sel->cond= NULL;
4862
sel->head=tab->table;
4865
/* Use quick key read if it's a constant and it's not used
4867
if (tab->needed_reg.none() && tab->type != AM_EQ_REF
4868
&& (tab->type != AM_REF || (uint32_t) tab->ref.key == tab->quick->index))
4870
sel->quick=tab->quick; // Use value from get_quick_...
4871
sel->quick_keys.reset();
4872
sel->needed_reg.reset();
4880
uint32_t ref_key= static_cast<uint32_t>(sel->head->reginfo.join_tab->ref.key + 1);
4881
if (i == join->const_tables && ref_key)
4883
if (tab->const_keys.any() &&
4884
tab->table->reginfo.impossible_range)
4887
else if (tab->type == AM_ALL && ! use_quick_range)
4889
if (tab->const_keys.any() &&
4890
tab->table->reginfo.impossible_range)
4891
return 1; // Impossible range
4893
We plan to scan all rows.
4894
Check again if we should use an index.
4895
We could have used an column from a previous table in
4896
the index if we are using limit and this is the first table
4899
cur_pos= join->getPosFromOptimalPlan(i);
4900
if ((cond && (! ((tab->keys & tab->const_keys) == tab->keys) && i > 0)) ||
4901
(! tab->const_keys.none() && (i == join->const_tables) &&
4902
(join->unit->select_limit_cnt < cur_pos.getFanout()) && ((join->select_options & OPTION_FOUND_ROWS) == false)))
4904
/* Join with outer join condition */
4905
COND *orig_cond= sel->cond;
4906
sel->cond= and_conds(sel->cond, *tab->on_expr_ref);
4909
We can't call sel->cond->fix_fields,
4910
as it will break tab->on_expr if it's AND condition
4911
(fix_fields currently removes extra AND/OR levels).
4912
Yet attributes of the just built condition are not needed.
4913
Thus we call sel->cond->quick_fix_field for safety.
4915
if (sel->cond && ! sel->cond->fixed)
4916
sel->cond->quick_fix_field();
4918
if (sel->test_quick_select(session, tab->keys,
4919
used_tables & ~ current_map,
4920
(join->select_options &
4923
join->unit->select_limit_cnt), 0,
4927
Before reporting "Impossible WHERE" for the whole query
4928
we have to check isn't it only "impossible ON" instead
4930
sel->cond=orig_cond;
4931
if (! *tab->on_expr_ref ||
4932
sel->test_quick_select(session, tab->keys,
4933
used_tables & ~ current_map,
4934
(join->select_options &
4937
join->unit->select_limit_cnt),0,
4939
return 1; // Impossible WHERE
4942
sel->cond=orig_cond;
4944
/* Fix for EXPLAIN */
4947
cur_pos= join->getPosFromOptimalPlan(i);
4948
cur_pos.setFanout(static_cast<double>(sel->quick->records));
4953
sel->needed_reg= tab->needed_reg;
4954
sel->quick_keys.reset();
4956
if (!((tab->checked_keys & sel->quick_keys) == sel->quick_keys) ||
4957
!((tab->checked_keys & sel->needed_reg) == sel->needed_reg))
4959
tab->keys= sel->quick_keys;
4960
tab->keys|= sel->needed_reg;
4961
tab->use_quick= (!sel->needed_reg.none() &&
4962
(select->quick_keys.none() ||
4964
(select->quick->records >= 100L)))) ?
4966
sel->read_tables= used_tables & ~current_map;
4968
if (i != join->const_tables && tab->use_quick != 2)
4969
{ /* Read with cache */
4971
(tmp=make_cond_for_table(cond,
4972
join->const_table_map |
4976
tab->cache.select= (optimizer::SqlSelect*)
4977
session->getMemRoot()->duplicate((unsigned char*) sel, sizeof(optimizer::SqlSelect));
4978
tab->cache.select->cond= tmp;
4979
tab->cache.select->read_tables= join->const_table_map;
4986
Push down conditions from all on expressions.
4987
Each of these conditions are guarded by a variable
4988
that turns if off just before null complemented row for
4989
outer joins is formed. Thus, the condition from an
4990
'on expression' are guaranteed not to be checked for
4991
the null complemented row.
4994
/* First push down constant conditions from on expressions */
4995
for (JoinTable *join_tab= join->join_tab+join->const_tables;
4996
join_tab < join->join_tab+join->tables ; join_tab++)
4998
if (*join_tab->on_expr_ref)
5000
JoinTable *cond_tab= join_tab->first_inner;
5001
tmp= make_cond_for_table(*join_tab->on_expr_ref,
5002
join->const_table_map,
5006
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
5009
tmp->quick_fix_field();
5010
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
5011
new Item_cond_and(cond_tab->select_cond,tmp);
5012
if (! cond_tab->select_cond)
5014
cond_tab->select_cond->quick_fix_field();
5018
/* Push down non-constant conditions from on expressions */
5019
JoinTable *last_tab= tab;
5020
while (first_inner_tab && first_inner_tab->last_inner == last_tab)
5023
Table tab is the last inner table of an outer join.
5024
An on expression is always attached to it.
5026
COND *on_expr= *first_inner_tab->on_expr_ref;
5028
table_map used_tables2= (join->const_table_map |
5029
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
5030
for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++)
5032
current_map= tab->table->map;
5033
used_tables2|= current_map;
5034
COND *tmp_cond= make_cond_for_table(on_expr, used_tables2,
5038
JoinTable *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;
5040
First add the guards for match variables of
5041
all embedding outer join operations.
5043
if (!(tmp_cond= add_found_match_trig_cond(cond_tab->first_inner,
5048
Now add the guard turning the predicate off for
5049
the null complemented row.
5051
tmp_cond= new Item_func_trig_cond(tmp_cond,
5055
tmp_cond->quick_fix_field();
5056
/* Add the predicate to other pushed down predicates */
5057
cond_tab->select_cond= !cond_tab->select_cond ? tmp_cond :
5058
new Item_cond_and(cond_tab->select_cond,
5060
if (! cond_tab->select_cond)
5062
cond_tab->select_cond->quick_fix_field();
5065
first_inner_tab= first_inner_tab->first_upper;
5073
Plan refinement stage: do various set ups for the executioner
5076
make_join_readinfo()
5077
join Join being processed
5078
options Join's options (checking for SELECT_DESCRIBE,
5079
SELECT_NO_JOIN_CACHE)
5080
no_jbuf_after Don't use join buffering after table with this number.
5083
Plan refinement stage: do various set ups for the executioner
5084
- set up use of join buffering
5085
- push index conditions
5086
- increment counters
5091
true - Out of memory
5093
static bool make_join_readinfo(Join *join)
5097
for (uint32_t i= join->const_tables ; i < join->tables ; i++)
5099
JoinTable *tab=join->join_tab+i;
5100
Table *table=tab->table;
5101
tab->read_record.table= table;
5102
tab->read_record.cursor= table->cursor;
5103
tab->next_select=sub_select; /* normal select */
5105
TODO: don't always instruct first table's ref/range access method to
5106
produce sorted output.
5108
tab->sorted= sorted;
5109
sorted= false; // only first must be sorted
5111
if (tab->insideout_match_tab)
5113
if (! (tab->insideout_buf= (unsigned char*) join->session->getMemRoot()->allocate(tab->table->key_info
5119
optimizer::AccessMethodFactory &factory= optimizer::AccessMethodFactory::singleton();
5120
boost::shared_ptr<optimizer::AccessMethod> access_method(factory.createAccessMethod(tab->type));
5122
if (! access_method)
5126
* Is abort() the correct thing to call here? I call this here because it was what was called in
5127
* the default case for the switch statement that used to be here.
5132
access_method->getStats(table, tab);
5135
join->join_tab[join->tables-1].next_select= NULL; /* Set by do_select */
5140
/** Update the dependency map for the tables. */
5141
static void update_depend_map(Join *join)
5143
JoinTable *join_tab=join->join_tab, *end=join_tab+join->tables;
5145
for (; join_tab != end ; join_tab++)
5147
table_reference_st *ref= &join_tab->ref;
5148
table_map depend_map= 0;
5149
Item **item=ref->items;
5151
for (i=0 ; i < ref->key_parts ; i++,item++)
5152
depend_map|=(*item)->used_tables();
5153
ref->depend_map=depend_map & ~OUTER_REF_TABLE_BIT;
5154
depend_map&= ~OUTER_REF_TABLE_BIT;
5155
for (JoinTable **tab=join->map2table; depend_map; tab++,depend_map>>=1 )
5158
ref->depend_map|=(*tab)->ref.depend_map;
5163
/** Update the dependency map for the sort order. */
5164
static void update_depend_map(Join *join, Order *order)
5166
for (; order ; order=order->next)
5168
table_map depend_map;
5169
order->item[0]->update_used_tables();
5170
order->depend_map=depend_map=order->item[0]->used_tables();
5171
// Not item_sum(), RAND() and no reference to table outside of sub select
5172
if (!(order->depend_map & (OUTER_REF_TABLE_BIT | RAND_TABLE_BIT))
5173
&& !order->item[0]->with_sum_func)
5175
for (JoinTable **tab=join->map2table; depend_map; tab++, depend_map>>=1)
5178
order->depend_map|=(*tab)->ref.depend_map;
5185
Remove all constants and check if order_st only contains simple
5188
simple_order is set to 1 if sort_order only uses fields from head table
5189
and the head table is not a LEFT JOIN table.
5191
@param join Join handler
5192
@param first_order List of SORT or GROUP order
5193
@param cond WHERE statement
5194
@param change_list Set to 1 if we should remove things from list.
5195
If this is not set, then only simple_order is
5197
@param simple_order Set to 1 if we are only using simple expressions
5200
Returns new sort order
5202
static Order *remove_constants(Join *join,Order *first_order, COND *cond, bool change_list, bool *simple_order)
5204
if (join->tables == join->const_tables)
5205
return change_list ? 0 : first_order; // No need to sort
5207
Order *order,**prev_ptr;
5208
table_map first_table= join->join_tab[join->const_tables].table->map;
5209
table_map not_const_tables= ~join->const_table_map;
5212
prev_ptr= &first_order;
5213
*simple_order= *join->join_tab[join->const_tables].on_expr_ref ? 0 : 1;
5215
/* NOTE: A variable of not_const_tables ^ first_table; breaks gcc 2.7 */
5217
update_depend_map(join, first_order);
5218
for (order=first_order; order ; order=order->next)
5220
table_map order_tables=order->item[0]->used_tables();
5221
if (order->item[0]->with_sum_func)
5222
*simple_order=0; // Must do a temp table to sort
5223
else if (!(order_tables & not_const_tables))
5225
if (order->item[0]->with_subselect)
5226
order->item[0]->val_str(&order->item[0]->str_value);
5227
continue; // skip const item
5231
if (order_tables & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT))
5236
if (cond && const_expression_in_where(cond,order->item[0], &comp_item))
5240
if ((ref=order_tables & (not_const_tables ^ first_table)))
5242
if (!(order_tables & first_table) &&
5243
only_eq_ref_tables(join,first_order, ref))
5247
*simple_order=0; // Must do a temp table to sort
5252
*prev_ptr= order; // use this entry
5253
prev_ptr= &order->next;
5257
if (prev_ptr == &first_order) // Nothing to sort/group
5259
return(first_order);
5262
static int return_zero_rows(Join *join,
5263
select_result *result,
5267
uint64_t select_options,
5271
if (select_options & SELECT_DESCRIBE)
5273
optimizer::ExplainPlan planner(join,
5278
planner.printPlan();
5286
for (TableList *table= tables; table; table= table->next_leaf)
5287
table->table->mark_as_null_row(); // All fields are NULL
5288
if (having && having->val_int() == 0)
5291
if (! (result->send_fields(fields)))
5295
List<Item>::iterator it(fields.begin());
5297
while ((item= it++))
5298
item->no_rows_in_result();
5299
result->send_data(fields);
5301
result->send_eof(); // Should be safe
5303
/* Update results for FOUND_ROWS */
5304
join->session->limit_found_rows= join->session->examined_row_count= 0;
5309
Simplify joins replacing outer joins by inner joins whenever it's
5312
The function, during a retrieval of join_list, eliminates those
5313
outer joins that can be converted into inner join, possibly nested.
5314
It also moves the on expressions for the converted outer joins
5315
and from inner joins to conds.
5316
The function also calculates some attributes for nested joins:
5320
- on_expr_dep_tables
5321
The first two attributes are used to test whether an outer join can
5322
be substituted for an inner join. The third attribute represents the
5323
relation 'to be dependent on' for tables. If table t2 is dependent
5324
on table t1, then in any evaluated execution plan table access to
5325
table t2 must precede access to table t2. This relation is used also
5326
to check whether the query contains invalid cross-references.
5327
The forth attribute is an auxiliary one and is used to calculate
5329
As the attribute dep_tables qualifies possibles orders of tables in the
5330
execution plan, the dependencies required by the straight join
5331
modifiers are reflected in this attribute as well.
5332
The function also removes all braces that can be removed from the join
5333
expression without changing its meaning.
5336
An outer join can be replaced by an inner join if the where condition
5337
or the on expression for an embedding nested join contains a conjunctive
5338
predicate rejecting null values for some attribute of the inner tables.
5342
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
5344
the predicate t2.b < 5 rejects nulls.
5345
The query is converted first to:
5347
SELECT * FROM t1 INNER JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
5349
then to the equivalent form:
5351
SELECT * FROM t1, t2 ON t2.a=t1.a WHERE t2.b < 5 AND t2.a=t1.a
5355
Similarly the following query:
5357
SELECT * from t1 LEFT JOIN (t2, t3) ON t2.a=t1.a t3.b=t1.b
5362
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b
5366
One conversion might trigger another:
5368
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a
5369
LEFT JOIN t3 ON t3.b=t2.b
5370
WHERE t3 IS NOT NULL =>
5371
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a, t3
5372
WHERE t3 IS NOT NULL AND t3.b=t2.b =>
5373
SELECT * FROM t1, t2, t3
5374
WHERE t3 IS NOT NULL AND t3.b=t2.b AND t2.a=t1.a
5377
The function removes all unnecessary braces from the expression
5378
produced by the conversions.
5381
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
5383
finally is converted to:
5385
SELECT * FROM t1, t2, t3 WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
5390
It also will remove braces from the following queries:
5392
SELECT * from (t1 LEFT JOIN t2 ON t2.a=t1.a) LEFT JOIN t3 ON t3.b=t2.b
5393
SELECT * from (t1, (t2,t3)) WHERE t1.a=t2.a AND t2.b=t3.b.
5396
The benefit of this simplification procedure is that it might return
5397
a query for which the optimizer can evaluate execution plan with more
5398
join orders. With a left join operation the optimizer does not
5399
consider any plan where one of the inner tables is before some of outer
5403
The function is implemented by a recursive procedure. On the recursive
5404
ascent all attributes are calculated, all outer joins that can be
5405
converted are replaced and then all unnecessary braces are removed.
5406
As join list contains join tables in the reverse order sequential
5407
elimination of outer joins does not require extra recursive calls.
5410
Remove all semi-joins that have are within another semi-join (i.e. have
5411
an "ancestor" semi-join nest)
5414
Here is an example of a join query with invalid cross references:
5416
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t3.a LEFT JOIN t3 ON t3.b=t1.b
5419
@param join reference to the query info
5420
@param join_list list representation of the join to be converted
5421
@param conds conditions to add on expressions for converted joins
5422
@param top true <=> conds is the where condition
5425
- The new condition, if success
5428
static COND *simplify_joins(Join *join, List<TableList> *join_list, COND *conds, bool top)
5431
NestedJoin *nested_join;
5432
TableList *prev_table= 0;
5433
List<TableList>::iterator li(join_list->begin());
5436
Try to simplify join operations from join_list.
5437
The most outer join operation is checked for conversion first.
5439
while ((table= li++))
5441
table_map used_tables;
5442
table_map not_null_tables= (table_map) 0;
5444
if ((nested_join= table->getNestedJoin()))
5447
If the element of join_list is a nested join apply
5448
the procedure to its nested join list first.
5452
Item *expr= table->on_expr;
5454
If an on expression E is attached to the table,
5455
check all null rejected predicates in this expression.
5456
If such a predicate over an attribute belonging to
5457
an inner table of an embedded outer join is found,
5458
the outer join is converted to an inner join and
5459
the corresponding on expression is added to E.
5461
expr= simplify_joins(join, &nested_join->join_list, expr, false);
5463
if (!table->prep_on_expr || expr != table->on_expr)
5467
table->on_expr= expr;
5468
table->prep_on_expr= expr->copy_andor_structure(join->session);
5471
nested_join->used_tables= (table_map) 0;
5472
nested_join->not_null_tables=(table_map) 0;
5473
conds= simplify_joins(join, &nested_join->join_list, conds, top);
5474
used_tables= nested_join->used_tables;
5475
not_null_tables= nested_join->not_null_tables;
5479
if (!table->prep_on_expr)
5480
table->prep_on_expr= table->on_expr;
5481
used_tables= table->table->map;
5483
not_null_tables= conds->not_null_tables();
5486
if (table->getEmbedding())
5488
table->getEmbedding()->getNestedJoin()->used_tables|= used_tables;
5489
table->getEmbedding()->getNestedJoin()->not_null_tables|= not_null_tables;
5492
if (!table->outer_join || (used_tables & not_null_tables))
5495
For some of the inner tables there are conjunctive predicates
5496
that reject nulls => the outer join can be replaced by an inner join.
5498
table->outer_join= 0;
5501
/* Add ON expression to the WHERE or upper-level ON condition. */
5504
conds= and_conds(conds, table->on_expr);
5505
conds->top_level_item();
5506
/* conds is always a new item as both cond and on_expr existed */
5507
assert(!conds->fixed);
5508
conds->fix_fields(join->session, &conds);
5511
conds= table->on_expr;
5512
table->prep_on_expr= table->on_expr= 0;
5520
Only inner tables of non-convertible outer joins
5521
remain with on_expr.
5525
table->setDepTables(table->getDepTables() | table->on_expr->used_tables());
5526
if (table->getEmbedding())
5528
table->setDepTables(table->getDepTables() & ~table->getEmbedding()->getNestedJoin()->used_tables);
5530
Embedding table depends on tables used
5531
in embedded on expressions.
5533
table->getEmbedding()->setOnExprDepTables(table->getEmbedding()->getOnExprDepTables() & table->on_expr->used_tables());
5536
table->setDepTables(table->getDepTables() & ~table->table->map);
5541
//If this is straight join, set prev table to be dependent on all tables
5542
//from this nested join, so that correct join order is selected.
5543
if ((test(join->select_options & SELECT_STRAIGHT_JOIN)) ||
5544
prev_table->straight)
5545
prev_table->setDepTables(prev_table->getDepTables() | used_tables);
5546
if (prev_table->on_expr)
5548
prev_table->setDepTables(prev_table->getDepTables() | table->getOnExprDepTables());
5549
table_map prev_used_tables= prev_table->getNestedJoin() ?
5550
prev_table->getNestedJoin()->used_tables :
5551
prev_table->table->map;
5553
If on expression contains only references to inner tables
5554
we still make the inner tables dependent on the outer tables.
5555
It would be enough to set dependency only on one outer table
5556
for them. Yet this is really a rare case.
5558
if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
5559
prev_table->setDepTables(prev_table->getDepTables() | used_tables);
5566
Flatten nested joins that can be flattened.
5567
no ON expression and not a semi-join => can be flattened.
5569
li= join_list->begin();
5570
while ((table= li++))
5572
nested_join= table->getNestedJoin();
5573
if (nested_join && !table->on_expr)
5576
List<TableList>::iterator it(nested_join->join_list.begin());
5579
tbl->setEmbedding(table->getEmbedding());
5580
tbl->setJoinList(table->getJoinList());
5582
li.replace(nested_join->join_list);
5588
static int remove_duplicates(Join *join, Table *entry,List<Item> &fields, Item *having)
5591
uint32_t reclength,offset;
5592
uint32_t field_count;
5593
Session *session= join->session;
5595
entry->reginfo.lock_type=TL_WRITE;
5597
/* Calculate how many saved fields there is in list */
5599
List<Item>::iterator it(fields.begin());
5603
if (item->get_tmp_table_field() && ! item->const_item())
5607
if (!field_count && !(join->select_options & OPTION_FOUND_ROWS) && !having)
5608
{ // only const items with no OPTION_FOUND_ROWS
5609
join->unit->select_limit_cnt= 1; // Only send first row
5612
Field **first_field=entry->getFields() + entry->getShare()->sizeFields() - field_count;
5613
offset= (field_count ?
5614
entry->getField(entry->getShare()->sizeFields() - field_count)->offset(entry->getInsertRecord()) : 0);
5615
reclength= entry->getShare()->getRecordLength() - offset;
5617
entry->free_io_cache(); // Safety
5618
entry->cursor->info(HA_STATUS_VARIABLE);
5619
if (entry->getShare()->db_type() == heap_engine ||
5620
(!entry->getShare()->blob_fields &&
5621
((ALIGN_SIZE(reclength) + HASH_OVERHEAD) * entry->cursor->stats.records <
5622
session->variables.sortbuff_size)))
5624
error= remove_dup_with_hash_index(join->session, entry,
5625
field_count, first_field,
5630
error= remove_dup_with_compare(join->session, entry, first_field, offset, having);
5633
free_blobs(first_field);
5639
Function to setup clauses without sum functions.
5641
static int setup_without_group(Session *session,
5642
Item **ref_pointer_array,
5646
List<Item> &all_fields,
5650
bool *hidden_group_fields)
5653
nesting_map save_allow_sum_func=session->getLex()->allow_sum_func ;
5655
session->getLex()->allow_sum_func&= ~(1 << session->getLex()->current_select->nest_level);
5656
res= session->setup_conds(tables, conds);
5658
session->getLex()->allow_sum_func|= 1 << session->getLex()->current_select->nest_level;
5659
res= res || setup_order(session, ref_pointer_array, tables, fields, all_fields,
5661
session->getLex()->allow_sum_func&= ~(1 << session->getLex()->current_select->nest_level);
5662
res= res || setup_group(session, ref_pointer_array, tables, fields, all_fields,
5663
group, hidden_group_fields);
5664
session->getLex()->allow_sum_func= save_allow_sum_func;
5669
Calculate the best possible join and initialize the join structure.
5676
static bool make_join_statistics(Join *join, TableList *tables, COND *conds, DYNAMIC_ARRAY *keyuse_array)
5681
uint32_t table_count;
5682
uint32_t const_count;
5684
table_map found_const_table_map;
5685
table_map all_table_map;
5686
table_map found_ref;
5690
Table **table_vector= NULL;
5691
JoinTable *stat= NULL;
5692
JoinTable *stat_end= NULL;
5694
JoinTable **stat_ref= NULL;
5695
optimizer::KeyUse *keyuse= NULL;
5696
optimizer::KeyUse *start_keyuse= NULL;
5697
table_map outer_join= 0;
5698
vector<optimizer::SargableParam> sargables;
5699
JoinTable *stat_vector[MAX_TABLES+1];
5700
optimizer::Position *partial_pos;
5702
table_count= join->tables;
5703
stat= (JoinTable*) join->session->calloc(sizeof(JoinTable)*table_count);
5704
stat_ref= (JoinTable**) join->session->getMemRoot()->allocate(sizeof(JoinTable*)*MAX_TABLES);
5705
table_vector= (Table**) join->session->getMemRoot()->allocate(sizeof(Table*)*(table_count*2));
5706
if (! stat || ! stat_ref || ! table_vector)
5709
join->best_ref=stat_vector;
5711
stat_end=stat+table_count;
5712
found_const_table_map= all_table_map=0;
5717
s++, tables= tables->next_leaf, i++)
5719
TableList *embedding= tables->getEmbedding();
5722
s->const_keys.reset();
5723
s->checked_keys.reset();
5724
s->needed_reg.reset();
5725
table_vector[i]=s->table=table=tables->table;
5726
table->pos_in_table_list= tables;
5727
assert(table->cursor);
5728
error= table->cursor->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
5731
table->print_error(error, MYF(0));
5734
table->quick_keys.reset();
5735
table->reginfo.join_tab=s;
5736
table->reginfo.not_exists_optimize=0;
5737
memset(table->const_key_parts, 0,
5738
sizeof(key_part_map)*table->getShare()->sizeKeys());
5739
all_table_map|= table->map;
5741
s->info=0; // For describe
5743
s->dependent= tables->getDepTables();
5744
s->key_dependent= 0;
5745
table->quick_condition_rows= table->cursor->stats.records;
5747
s->on_expr_ref= &tables->on_expr;
5748
if (*s->on_expr_ref)
5750
/* s is the only inner table of an outer join */
5751
if (!table->cursor->stats.records && !embedding)
5753
s->dependent= 0; // Ignore LEFT JOIN depend.
5754
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5757
outer_join|= table->map;
5758
s->embedding_map.reset();
5759
for (;embedding; embedding= embedding->getEmbedding())
5760
s->embedding_map|= embedding->getNestedJoin()->nj_map;
5763
if (embedding && !(false && ! embedding->getEmbedding()))
5765
/* s belongs to a nested join, maybe to several embedded joins */
5766
s->embedding_map.reset();
5769
NestedJoin *nested_join= embedding->getNestedJoin();
5770
s->embedding_map|= nested_join->nj_map;
5771
s->dependent|= embedding->getDepTables();
5772
embedding= embedding->getEmbedding();
5773
outer_join|= nested_join->used_tables;
5778
if ((table->cursor->stats.records <= 1) && !s->dependent &&
5779
(table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
5780
!join->no_const_tables)
5782
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5786
join->outer_join=outer_join;
5788
if (join->outer_join)
5791
Build transitive closure for relation 'to be dependent on'.
5792
This will speed up the plan search for many cases with outer joins,
5793
as well as allow us to catch illegal cross references/
5794
Warshall's algorithm is used to build the transitive closure.
5795
As we use bitmaps to represent the relation the complexity
5796
of the algorithm is O((number of tables)^2).
5798
for (i= 0; i < table_count; i++)
5801
table= stat[i].table;
5803
if (!table->reginfo.join_tab->dependent)
5806
for (j= 0, s= stat; j < table_count; j++, s++)
5808
if (s->dependent & table->map)
5810
table_map was_dependent= s->dependent;
5811
s->dependent |= table->reginfo.join_tab->dependent;
5812
if (i > j && s->dependent != was_dependent)
5820
/* Catch illegal cross references for outer joins */
5821
for (i= 0, s= stat ; i < table_count ; i++, s++)
5823
if (s->dependent & s->table->map)
5825
join->tables=0; // Don't use join->table
5826
my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
5829
if (outer_join & s->table->map)
5830
s->table->maybe_null= 1;
5832
s->key_dependent= s->dependent;
5836
if (conds || outer_join)
5837
if (update_ref_and_keys(join->session, keyuse_array, stat, join->tables,
5838
conds, join->cond_equal,
5839
~outer_join, join->select_lex, sargables))
5842
/* Read tables with 0 or 1 rows (system tables) */
5843
join->const_table_map= 0;
5845
optimizer::Position *p_pos= join->getFirstPosInPartialPlan();
5846
optimizer::Position *p_end= join->getSpecificPosInPartialPlan(const_count);
5847
while (p_pos < p_end)
5850
s= p_pos->getJoinTable();
5852
join->const_table_map|=s->table->map;
5853
if ((tmp= s->joinReadConstTable(p_pos)))
5856
return 1; // Fatal error
5859
found_const_table_map|= s->table->map;
5863
/* loop until no more const tables are found */
5867
more_const_tables_found:
5872
We only have to loop from stat_vector + const_count as
5873
set_position() will move all const_tables first in stat_vector
5876
for (JoinTable **pos= stat_vector+const_count; (s= *pos); pos++)
5881
If equi-join condition by a key is null rejecting and after a
5882
substitution of a const table the key value happens to be null
5883
then we can state that there are no matches for this equi-join.
5885
if ((keyuse= s->keyuse) && *s->on_expr_ref && s->embedding_map.none())
5888
When performing an outer join operation if there are no matching rows
5889
for the single row of the outer table all the inner tables are to be
5890
null complemented and thus considered as constant tables.
5891
Here we apply this consideration to the case of outer join operations
5892
with a single inner table only because the case with nested tables
5893
would require a more thorough analysis.
5894
TODO. Apply single row substitution to null complemented inner tables
5895
for nested outer join operations.
5897
while (keyuse->getTable() == table)
5899
if (! (keyuse->getVal()->used_tables() & ~join->const_table_map) &&
5900
keyuse->getVal()->is_null() && keyuse->isNullRejected())
5903
table->mark_as_null_row();
5904
found_const_table_map|= table->map;
5905
join->const_table_map|= table->map;
5906
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5907
goto more_const_tables_found;
5913
if (s->dependent) // If dependent on some table
5915
// All dep. must be constants
5916
if (s->dependent & ~(found_const_table_map))
5918
if (table->cursor->stats.records <= 1L &&
5919
(table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
5920
!table->pos_in_table_list->getEmbedding())
5924
join->const_table_map|=table->map;
5925
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
5926
partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);
5927
if ((tmp= s->joinReadConstTable(partial_pos)))
5930
return 1; // Fatal error
5933
found_const_table_map|= table->map;
5937
/* check if table can be read by key or table only uses const refs */
5938
if ((keyuse=s->keyuse))
5941
while (keyuse->getTable() == table)
5943
start_keyuse= keyuse;
5944
key= keyuse->getKey();
5945
s->keys.set(key); // QQ: remove this ?
5952
if (keyuse->getVal()->type() != Item::NULL_ITEM &&
5953
! keyuse->getOptimizeFlags())
5955
if (! ((~found_const_table_map) & keyuse->getUsedTables()))
5956
const_ref.set(keyuse->getKeypart());
5958
refs|= keyuse->getUsedTables();
5959
eq_part.set(keyuse->getKeypart());
5962
} while (keyuse->getTable() == table && keyuse->getKey() == key);
5964
if (is_keymap_prefix(eq_part, table->key_info[key].key_parts) &&
5965
! table->pos_in_table_list->getEmbedding())
5967
if ((table->key_info[key].flags & (HA_NOSAME)) == HA_NOSAME)
5969
if (const_ref == eq_part)
5970
{ // Found everything for ref.
5974
join->const_table_map|= table->map;
5975
set_position(join, const_count++, s, start_keyuse);
5976
if (create_ref_for_key(join, s, start_keyuse, found_const_table_map))
5978
partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);
5979
if ((tmp=s->joinReadConstTable(partial_pos)))
5982
return 1; // Fatal error
5985
found_const_table_map|= table->map;
5989
found_ref|= refs; // Table is const if all refs are const
5991
else if (const_ref == eq_part)
5992
s->const_keys.set(key);
5997
} while (join->const_table_map & found_ref && ref_changed);
6000
Update info on indexes that can be used for search lookups as
6001
reading const tables may has added new sargable predicates.
6003
if (const_count && ! sargables.empty())
6005
vector<optimizer::SargableParam>::iterator iter= sargables.begin();
6006
while (iter != sargables.end())
6008
Field *field= (*iter).getField();
6009
JoinTable *join_tab= field->getTable()->reginfo.join_tab;
6010
key_map possible_keys= field->key_start;
6011
possible_keys&= field->getTable()->keys_in_use_for_query;
6012
bool is_const= true;
6013
for (uint32_t j= 0; j < (*iter).getNumValues(); j++)
6014
is_const&= (*iter).isConstItem(j);
6016
join_tab[0].const_keys|= possible_keys;
6021
/* Calc how many (possible) matched records in each table */
6023
for (s=stat ; s < stat_end ; s++)
6025
if (s->type == AM_SYSTEM || s->type == AM_CONST)
6027
/* Only one matching row */
6028
s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
6031
/* Approximate found rows and time to read them */
6032
s->found_records=s->records=s->table->cursor->stats.records;
6033
s->read_time=(ha_rows) s->table->cursor->scan_time();
6036
Set a max range of how many seeks we can expect when using keys
6037
This is can't be to high as otherwise we are likely to use
6040
s->worst_seeks= min((double) s->found_records / 10,
6041
(double) s->read_time*3);
6042
if (s->worst_seeks < 2.0) // Fix for small tables
6046
Add to stat->const_keys those indexes for which all group fields or
6047
all select distinct fields participate in one index.
6049
add_group_and_distinct_keys(join, s);
6051
if (s->const_keys.any() &&
6052
!s->table->pos_in_table_list->getEmbedding())
6055
optimizer::SqlSelect *select= NULL;
6056
select= optimizer::make_select(s->table, found_const_table_map, found_const_table_map, *s->on_expr_ref ? *s->on_expr_ref : conds, 1, &error);
6059
records= get_quick_record_count(join->session, select, s->table, &s->const_keys, join->row_limit);
6060
s->quick=select->quick;
6061
s->needed_reg=select->needed_reg;
6064
if (records == 0 && s->table->reginfo.impossible_range)
6067
Impossible WHERE or ON expression
6068
In case of ON, we mark that the we match one empty NULL row.
6069
In case of WHERE, don't set found_const_table_map to get the
6070
caller to abort with a zero row result.
6072
join->const_table_map|= s->table->map;
6073
set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
6075
if (*s->on_expr_ref)
6077
/* Generate empty row */
6078
s->info= "Impossible ON condition";
6079
found_const_table_map|= s->table->map;
6081
s->table->mark_as_null_row(); // All fields are NULL
6084
if (records != HA_POS_ERROR)
6086
s->found_records=records;
6087
s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
6093
join->join_tab=stat;
6094
join->map2table=stat_ref;
6095
join->table= join->all_tables=table_vector;
6096
join->const_tables=const_count;
6097
join->found_const_table_map=found_const_table_map;
6099
/* Find an optimal join order of the non-constant tables. */
6100
if (join->const_tables != join->tables)
6102
optimize_keyuse(join, keyuse_array);
6103
// @note c_str() is not likely to be valid here if dtrace expects it to
6104
// exist for any period of time.
6105
DRIZZLE_QUERY_OPT_CHOOSE_PLAN_START(join->session->getQueryString()->c_str(), join->session->thread_id);
6106
bool res= choose_plan(join, all_table_map & ~join->const_table_map);
6107
DRIZZLE_QUERY_OPT_CHOOSE_PLAN_DONE(res ? 1 : 0);
6113
join->copyPartialPlanIntoOptimalPlan(join->const_tables);
6114
join->best_read= 1.0;
6116
/* Generate an execution plan from the found optimal join order. */
6117
return (join->session->getKilled() || get_best_combination(join));
6121
Assign each nested join structure a bit in the nested join bitset.
6123
Assign each nested join structure (except "confluent" ones - those that
6124
embed only one element) a bit in the nested join bitset.
6126
@param join Join being processed
6127
@param join_list List of tables
6128
@param first_unused Number of first unused bit in the nest joing bitset before the
6132
This function is called after simplify_joins(), when there are no
6133
redundant nested joins, #non_confluent_nested_joins <= #tables_in_join so
6134
we will not run out of bits in the nested join bitset.
6137
First unused bit in the nest join bitset after the call.
6139
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused)
6141
List<TableList>::iterator li(join_list->begin());
6143
while ((table= li++))
6145
NestedJoin *nested_join;
6146
if ((nested_join= table->getNestedJoin()))
6149
It is guaranteed by simplify_joins() function that a nested join
6150
that has only one child is either
6151
- a single-table view (the child is the underlying table), or
6152
- a single-table semi-join nest
6154
We don't assign bits to such sj-nests because
6155
1. it is redundant (a "sequence" of one table cannot be interleaved
6157
2. we could run out of bits in the nested join bitset otherwise.
6159
if (nested_join->join_list.elements != 1)
6161
/* Don't assign bits to sj-nests */
6163
nested_join->nj_map.set(first_unused++);
6164
first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
6169
return(first_unused);
6174
Return table number if there is only one table in sort order
6175
and group and order is compatible, else return 0.
6177
static Table *get_sort_by_table(Order *a, Order *b,TableList *tables)
6179
table_map map= (table_map) 0;
6182
a= b; // Only one need to be given
6186
for (; a && b; a=a->next,b=b->next)
6188
if (!(*a->item)->eq(*b->item,1))
6189
return (Table *) NULL;
6190
map|= a->item[0]->used_tables();
6192
if (!map || (map & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT)))
6193
return (Table *) NULL;
6195
for (; !(map & tables->table->map); tables= tables->next_leaf) {};
6196
if (map != tables->table->map)
6197
return (Table *) NULL; // More than one table
6198
return tables->table;
6202
Set NestedJoin::counter=0 in all nested joins in passed list.
6204
Recursively set NestedJoin::counter=0 for all nested joins contained in
6205
the passed join_list.
6207
@param join_list List of nested joins to process. It may also contain base
6208
tables which will be ignored.
6210
static void reset_nj_counters(List<TableList> *join_list)
6212
List<TableList>::iterator li(join_list->begin());
6214
while ((table= li++))
6216
NestedJoin *nested_join;
6217
if ((nested_join= table->getNestedJoin()))
6219
nested_join->counter_= 0;
6220
reset_nj_counters(&nested_join->join_list);
6227
Return 1 if second is a subpart of first argument.
6229
If first parts has different direction, change it to second part
6230
(group is sorted like order)
6232
static bool test_if_subpart(Order *a, Order *b)
6234
for (; a && b; a=a->next,b=b->next)
6236
if ((*a->item)->eq(*b->item,1))
6245
Nested joins perspective: Remove the last table from the join order.
6247
The algorithm is the reciprocal of check_interleaving_with_nj(), hence
6248
parent join nest nodes are updated only when the last table in its child
6249
node is removed. The ASCII graphic below will clarify.
6251
%A table nesting such as <tt> t1 x [ ( t2 x t3 ) x ( t4 x t5 ) ] </tt>is
6252
represented by the below join nest tree.
6260
t1 x [ (t2 x t3) x (t4 x t5) ]
6263
At the point in time when check_interleaving_with_nj() adds the table t5 to
6264
the query execution plan, QEP, it also directs the node named NJ2 to mark
6265
the table as covered. NJ2 does so by incrementing its @c counter
6266
member. Since all of NJ2's tables are now covered by the QEP, the algorithm
6267
proceeds up the tree to NJ1, incrementing its counter as well. All join
6268
nests are now completely covered by the QEP.
6270
restore_prev_nj_state() does the above in reverse. As seen above, the node
6271
NJ1 contains the nodes t2, t3, and NJ2. Its counter being equal to 3 means
6272
that the plan covers t2, t3, and NJ2, @e and that the sub-plan (t4 x t5)
6273
completely covers NJ2. The removal of t5 from the partial plan will first
6274
decrement NJ2's counter to 1. It will then detect that NJ2 went from being
6275
completely to partially covered, and hence the algorithm must continue
6276
upwards to NJ1 and decrement its counter to 2. %A subsequent removal of t4
6277
will however not influence NJ1 since it did not un-cover the last table in
6281
restore_prev_nj_state()
6282
last join table to remove, it is assumed to be the last in current
6287
Remove the last table from the partial join order and update the nested
6288
joins counters and join->cur_embedding_map. It is ok to call this
6289
function for the first table in join order (for which
6290
check_interleaving_with_nj has not been called)
6292
@param last join table to remove, it is assumed to be the last in current
6296
static void restore_prev_nj_state(JoinTable *last)
6298
TableList *last_emb= last->table->pos_in_table_list->getEmbedding();
6299
Join *join= last->join;
6300
for (;last_emb != NULL; last_emb= last_emb->getEmbedding())
6302
NestedJoin *nest= last_emb->getNestedJoin();
6304
bool was_fully_covered= nest->is_fully_covered();
6306
if (--nest->counter_ == 0)
6307
join->cur_embedding_map&= ~nest->nj_map;
6309
if (!was_fully_covered)
6312
join->cur_embedding_map|= nest->nj_map;
6317
Create a condition for a const reference and add this to the
6318
currenct select for the table.
6320
static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab)
6322
if (!join_tab->ref.key_parts)
6325
Item_cond_and *cond=new Item_cond_and();
6326
Table *table=join_tab->table;
6331
for (uint32_t i=0 ; i < join_tab->ref.key_parts ; i++)
6333
Field *field=table->getField(table->key_info[join_tab->ref.key].key_part[i].fieldnr - 1);
6334
Item *value=join_tab->ref.items[i];
6335
cond->add(new Item_func_equal(new Item_field(field), value));
6337
if (session->is_fatal_error)
6341
cond->fix_fields(session, (Item**)&cond);
6342
if (join_tab->select)
6344
error=(int) cond->add(join_tab->select->cond);
6345
join_tab->select_cond=join_tab->select->cond=cond;
6347
else if ((join_tab->select= optimizer::make_select(join_tab->table, 0, 0, cond, 0,
6349
join_tab->select_cond=cond;
6351
return(error ? true : false);
6354
static void free_blobs(Field **ptr)
6356
for (; *ptr ; ptr++)
6358
if ((*ptr)->flags & BLOB_FLAG)
6359
((Field_blob *) (*ptr))->free();
6364
@} (end of group Query_Optimizer)
6367
} /* namespace drizzled */
added
removed
drizzled/join.cc
