12
12
You should have received a copy of the GNU General Public License
13
13
along with this program; if not, write to the Free Software
14
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
14
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
20
select_query and join optimization
20
mysql_select and join optimization
22
22
@defgroup Query_Optimizer Query Optimizer
28
28
#include <iostream>
29
29
#include <algorithm>
32
#include <drizzled/sql_select.h> /* include join.h */
34
#include <drizzled/error.h>
35
#include <drizzled/gettext.h>
36
#include <drizzled/util/test.h>
37
#include <drizzled/name_resolution_context_state.h>
38
#include <drizzled/nested_join.h>
39
#include <drizzled/probes.h>
40
#include <drizzled/show.h>
41
#include <drizzled/item/cache.h>
42
#include <drizzled/item/cmpfunc.h>
43
#include <drizzled/item/copy_string.h>
44
#include <drizzled/item/uint.h>
45
#include <drizzled/cached_item.h>
46
#include <drizzled/sql_base.h>
47
#include <drizzled/field/blob.h>
48
#include <drizzled/check_stack_overrun.h>
49
#include <drizzled/lock.h>
50
#include <drizzled/item/outer_ref.h>
51
#include <drizzled/index_hint.h>
52
#include <drizzled/records.h>
53
#include <drizzled/internal/iocache.h>
54
#include <drizzled/drizzled.h>
55
#include <drizzled/plugin/storage_engine.h>
57
#include <drizzled/sql_union.h>
58
#include <drizzled/optimizer/key_field.h>
59
#include <drizzled/optimizer/position.h>
60
#include <drizzled/optimizer/sargable_param.h>
61
#include <drizzled/optimizer/key_use.h>
62
#include <drizzled/optimizer/range.h>
63
#include <drizzled/optimizer/quick_range_select.h>
64
#include <drizzled/optimizer/quick_ror_intersect_select.h>
66
#include <drizzled/filesort.h>
67
#include <drizzled/sql_lex.h>
68
#include <drizzled/session.h>
69
#include <drizzled/sort_field.h>
70
#include <drizzled/select_result.h>
32
#include "drizzled/sql_select.h" /* include join.h */
34
#include "drizzled/error.h"
35
#include "drizzled/gettext.h"
36
#include "drizzled/util/test.h"
37
#include "drizzled/name_resolution_context_state.h"
38
#include "drizzled/nested_join.h"
39
#include "drizzled/probes.h"
40
#include "drizzled/show.h"
41
#include "drizzled/item/cache.h"
42
#include "drizzled/item/cmpfunc.h"
43
#include "drizzled/item/copy_string.h"
44
#include "drizzled/item/uint.h"
45
#include "drizzled/cached_item.h"
46
#include "drizzled/sql_base.h"
47
#include "drizzled/field/blob.h"
48
#include "drizzled/check_stack_overrun.h"
49
#include "drizzled/lock.h"
50
#include "drizzled/item/outer_ref.h"
51
#include "drizzled/index_hint.h"
52
#include "drizzled/records.h"
53
#include "drizzled/internal/iocache.h"
55
#include "drizzled/sql_union.h"
56
#include "drizzled/optimizer/key_field.h"
57
#include "drizzled/optimizer/position.h"
58
#include "drizzled/optimizer/sargable_param.h"
59
#include "drizzled/optimizer/key_use.h"
60
#include "drizzled/optimizer/range.h"
61
#include "drizzled/optimizer/quick_range_select.h"
62
#include "drizzled/optimizer/quick_ror_intersect_select.h"
72
64
using namespace std;
136
128
unit->set_limit(unit->global_parameters);
137
129
session->session_marker= 0;
139
'options' of select_query will be set in JOIN, as far as JOIN for
131
'options' of mysql_select will be set in JOIN, as far as JOIN for
140
132
every PS/SP execution new, we will not need reset this flag if
141
133
setup_tables_done_option changed for next rexecution
143
res= select_query(session,
144
&select_lex->ref_pointer_array,
135
res= mysql_select(session, &select_lex->ref_pointer_array,
145
136
(TableList*) select_lex->table_list.first,
146
select_lex->with_wild,
147
select_lex->item_list,
137
select_lex->with_wild, select_lex->item_list,
148
138
select_lex->where,
149
139
select_lex->order_list.elements +
150
140
select_lex->group_list.elements,
151
(Order*) select_lex->order_list.first,
152
(Order*) select_lex->group_list.first,
141
(order_st*) select_lex->order_list.first,
142
(order_st*) select_lex->group_list.first,
153
143
select_lex->having,
154
144
select_lex->options | session->options |
155
145
setup_tables_done_option,
1220
Check if given expression uses only table fields covered by the given index
1223
uses_index_fields_only()
1224
item Expression to check
1225
tbl The table having the index
1226
keyno The index number
1227
other_tbls_ok true <=> Fields of other non-const tables are allowed
1230
Check if given expression only uses fields covered by index #keyno in the
1231
table tbl. The expression can use any fields in any other tables.
1233
The expression is guaranteed not to be AND or OR - those constructs are
1234
handled outside of this function.
1240
static bool uses_index_fields_only(Item *item, Table *tbl, uint32_t keyno, bool other_tbls_ok)
1242
if (item->const_item())
1246
Don't push down the triggered conditions. Nested outer joins execution
1247
code may need to evaluate a condition several times (both triggered and
1248
untriggered), and there is no way to put thi
1249
TODO: Consider cloning the triggered condition and using the copies for:
1250
1. push the first copy down, to have most restrictive index condition
1252
2. Put the second copy into tab->select_cond.
1254
if (item->type() == Item::FUNC_ITEM &&
1255
((Item_func*)item)->functype() == Item_func::TRIG_COND_FUNC)
1258
if (!(item->used_tables() & tbl->map))
1259
return other_tbls_ok;
1261
Item::Type item_type= item->type();
1262
switch (item_type) {
1263
case Item::FUNC_ITEM:
1265
/* This is a function, apply condition recursively to arguments */
1266
Item_func *item_func= (Item_func*)item;
1268
Item **item_end= (item_func->arguments()) + item_func->argument_count();
1269
for (child= item_func->arguments(); child != item_end; child++)
1271
if (!uses_index_fields_only(*child, tbl, keyno, other_tbls_ok))
1276
case Item::COND_ITEM:
1278
/* This is a function, apply condition recursively to arguments */
1279
List_iterator<Item> li(*((Item_cond*)item)->argument_list());
1281
while ((list_item=li++))
1283
if (!uses_index_fields_only(item, tbl, keyno, other_tbls_ok))
1288
case Item::FIELD_ITEM:
1290
Item_field *item_field= (Item_field*)item;
1291
if (item_field->field->getTable() != tbl)
1293
return item_field->field->part_of_key.test(keyno);
1295
case Item::REF_ITEM:
1296
return uses_index_fields_only(item->real_item(), tbl, keyno,
1299
return false; /* Play it safe, don't push unknown non-const items */
1216
1303
#define ICP_COND_USES_INDEX_ONLY 10
1306
Get a part of the condition that can be checked using only index fields
1309
make_cond_for_index()
1310
cond The source condition
1311
table The table that is partially available
1312
keyno The index in the above table. Only fields covered by the index
1314
other_tbls_ok true <=> Fields of other non-const tables are allowed
1317
Get a part of the condition that can be checked when for the given table
1318
we have values only of fields covered by some index. The condition may
1319
refer to other tables, it is assumed that we have values of all of their
1323
make_cond_for_index(
1324
"cond(t1.field) AND cond(t2.key1) AND cond(t2.non_key) AND cond(t2.key2)",
1327
"cond(t1.field) AND cond(t2.key2)"
1330
Index condition, or NULL if no condition could be inferred.
1332
static Item *make_cond_for_index(Item *cond, Table *table, uint32_t keyno, bool other_tbls_ok)
1336
if (cond->type() == Item::COND_ITEM)
1338
uint32_t n_marked= 0;
1339
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
1341
Item_cond_and *new_cond=new Item_cond_and;
1344
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
1348
Item *fix= make_cond_for_index(item, table, keyno, other_tbls_ok);
1350
new_cond->argument_list()->push_back(fix);
1351
n_marked += test(item->marker == ICP_COND_USES_INDEX_ONLY);
1353
if (n_marked ==((Item_cond*)cond)->argument_list()->elements)
1354
cond->marker= ICP_COND_USES_INDEX_ONLY;
1355
switch (new_cond->argument_list()->elements) {
1359
return new_cond->argument_list()->head();
1361
new_cond->quick_fix_field();
1367
Item_cond_or *new_cond=new Item_cond_or;
1370
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
1374
Item *fix= make_cond_for_index(item, table, keyno, other_tbls_ok);
1377
new_cond->argument_list()->push_back(fix);
1378
n_marked += test(item->marker == ICP_COND_USES_INDEX_ONLY);
1380
if (n_marked ==((Item_cond*)cond)->argument_list()->elements)
1381
cond->marker= ICP_COND_USES_INDEX_ONLY;
1382
new_cond->quick_fix_field();
1383
new_cond->top_level_item();
1388
if (!uses_index_fields_only(cond, table, keyno, other_tbls_ok))
1390
cond->marker= ICP_COND_USES_INDEX_ONLY;
1395
static Item *make_cond_remainder(Item *cond, bool exclude_index)
1397
if (exclude_index && cond->marker == ICP_COND_USES_INDEX_ONLY)
1398
return 0; /* Already checked */
1400
if (cond->type() == Item::COND_ITEM)
1402
table_map tbl_map= 0;
1403
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
1405
/* Create new top level AND item */
1406
Item_cond_and *new_cond=new Item_cond_and;
1409
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
1413
Item *fix= make_cond_remainder(item, exclude_index);
1416
new_cond->argument_list()->push_back(fix);
1417
tbl_map |= fix->used_tables();
1420
switch (new_cond->argument_list()->elements) {
1424
return new_cond->argument_list()->head();
1426
new_cond->quick_fix_field();
1427
((Item_cond*)new_cond)->used_tables_cache= tbl_map;
1433
Item_cond_or *new_cond=new Item_cond_or;
1436
List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
1440
Item *fix= make_cond_remainder(item, false);
1443
new_cond->argument_list()->push_back(fix);
1444
tbl_map |= fix->used_tables();
1446
new_cond->quick_fix_field();
1447
((Item_cond*)new_cond)->used_tables_cache= tbl_map;
1448
new_cond->top_level_item();
1220
1456
cleanup JoinTable.
1222
1458
void JoinTable::cleanup()
1224
safe_delete(select);
1227
1464
if (cache.buff)
1229
size_t size= cache.end - cache.buff;
1230
global_join_buffer.sub(size);
1231
1465
free(cache.buff);
3600
int join_read_const_table(JoinTable *tab, optimizer::Position *pos)
3603
Table *table=tab->table;
3604
table->const_table=1;
3606
table->status=STATUS_NO_RECORD;
3608
if (tab->type == AM_SYSTEM)
3610
if ((error=join_read_system(tab)))
3611
{ // Info for DESCRIBE
3612
tab->info="const row not found";
3613
/* Mark for EXPLAIN that the row was not found */
3614
pos->setFanout(0.0);
3615
pos->clearRefDependMap();
3616
if (! table->maybe_null || error > 0)
3622
if (! table->key_read &&
3623
table->covering_keys.test(tab->ref.key) &&
3624
! table->no_keyread &&
3625
(int) table->reginfo.lock_type <= (int) TL_READ_WITH_SHARED_LOCKS)
3628
table->cursor->extra(HA_EXTRA_KEYREAD);
3629
tab->index= tab->ref.key;
3631
error=join_read_const(tab);
3632
if (table->key_read)
3635
table->cursor->extra(HA_EXTRA_NO_KEYREAD);
3639
tab->info="unique row not found";
3640
/* Mark for EXPLAIN that the row was not found */
3641
pos->setFanout(0.0);
3642
pos->clearRefDependMap();
3643
if (!table->maybe_null || error > 0)
3647
if (*tab->on_expr_ref && !table->null_row)
3649
if ((table->null_row= test((*tab->on_expr_ref)->val_int() == 0)))
3650
table->mark_as_null_row();
3652
if (!table->null_row)
3653
table->maybe_null=0;
3655
/* Check appearance of new constant items in Item_equal objects */
3656
Join *join= tab->join;
3658
update_const_equal_items(join->conds, tab);
3660
for (tbl= join->select_lex->leaf_tables; tbl; tbl= tbl->next_leaf)
3662
TableList *embedded;
3663
TableList *embedding= tbl;
3666
embedded= embedding;
3667
if (embedded->on_expr)
3668
update_const_equal_items(embedded->on_expr, tab);
3669
embedding= embedded->getEmbedding();
3672
embedding->getNestedJoin()->join_list.head() == embedded);
3678
int join_read_system(JoinTable *tab)
3680
Table *table= tab->table;
3682
if (table->status & STATUS_GARBAGE) // If first read
3684
if ((error=table->cursor->read_first_row(table->getInsertRecord(),
3685
table->getShare()->getPrimaryKey())))
3687
if (error != HA_ERR_END_OF_FILE)
3688
return table->report_error(error);
3689
tab->table->mark_as_null_row();
3690
table->emptyRecord(); // Make empty record
3693
table->storeRecord();
3695
else if (!table->status) // Only happens with left join
3696
table->restoreRecord(); // restore old record
3698
return table->status ? -1 : 0;
3375
3702
Read a (constant) table when there is at most one matching row.