1/*
2 Copyright (c) 2009, 2012, Monty Program Ab
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; version 2 of the License.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; if not, write to the Free Software
15 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1301 USA */
16
17#include "mariadb.h"
18#include "sql_select.h"
19#include "sql_test.h"
20
21/****************************************************************************
22 * Index Condition Pushdown code starts
23 ***************************************************************************/
24/*
25 Check if given expression uses only table fields covered by the given index
26
27 SYNOPSIS
28 uses_index_fields_only()
29 item Expression to check
30 tbl The table having the index
31 keyno The index number
32 other_tbls_ok TRUE <=> Fields of other non-const tables are allowed
33
34 DESCRIPTION
35 Check if given expression only uses fields covered by index #keyno in the
36 table tbl. The expression can use any fields in any other tables.
37
38 The expression is guaranteed not to be AND or OR - those constructs are
39 handled outside of this function.
40
41 RETURN
42 TRUE Yes
43 FALSE No
44*/
45
46bool uses_index_fields_only(Item *item, TABLE *tbl, uint keyno,
47 bool other_tbls_ok)
48{
49 if (item->walk(&Item::limit_index_condition_pushdown_processor, FALSE, NULL))
50 {
51 return FALSE;
52 }
53
54 if (item->const_item())
55 return TRUE;
56
57 /*
58 Don't push down the triggered conditions. Nested outer joins execution
59 code may need to evaluate a condition several times (both triggered and
60 untriggered), and there is no way to put thi
61 TODO: Consider cloning the triggered condition and using the copies for:
62 1. push the first copy down, to have most restrictive index condition
63 possible
64 2. Put the second copy into tab->select_cond.
65 */
66 if (item->type() == Item::FUNC_ITEM &&
67 ((Item_func*)item)->functype() == Item_func::TRIG_COND_FUNC)
68 return FALSE;
69
70 if (!(item->used_tables() & tbl->map))
71 return other_tbls_ok;
72
73 Item::Type item_type= item->type();
74 switch (item_type) {
75 case Item::FUNC_ITEM:
76 {
77 /* This is a function, apply condition recursively to arguments */
78 Item_func *item_func= (Item_func*)item;
79 Item **child;
80 Item **item_end= (item_func->arguments()) + item_func->argument_count();
81 for (child= item_func->arguments(); child != item_end; child++)
82 {
83 if (!uses_index_fields_only(*child, tbl, keyno, other_tbls_ok))
84 return FALSE;
85 }
86 return TRUE;
87 }
88 case Item::COND_ITEM:
89 {
90 /*
91 This is a AND/OR condition. Regular AND/OR clauses are handled by
92 make_cond_for_index() which will chop off the part that can be
93 checked with index. This code is for handling non-top-level AND/ORs,
94 e.g. func(x AND y).
95 */
96 List_iterator<Item> li(*((Item_cond*)item)->argument_list());
97 Item *item;
98 while ((item=li++))
99 {
100 if (!uses_index_fields_only(item, tbl, keyno, other_tbls_ok))
101 return FALSE;
102 }
103 return TRUE;
104 }
105 case Item::FIELD_ITEM:
106 {
107 Item_field *item_field= (Item_field*)item;
108 Field *field= item_field->field;
109 if (field->table != tbl)
110 return TRUE;
111 /*
112 The below is probably a repetition - the first part checks the
113 other two, but let's play it safe:
114 */
115 if(!field->part_of_key.is_set(keyno) ||
116 field->type() == MYSQL_TYPE_GEOMETRY ||
117 field->type() == MYSQL_TYPE_BLOB)
118 return FALSE;
119 KEY *key_info= tbl->key_info + keyno;
120 KEY_PART_INFO *key_part= key_info->key_part;
121 KEY_PART_INFO *key_part_end= key_part + key_info->user_defined_key_parts;
122 for ( ; key_part < key_part_end; key_part++)
123 {
124 if (field->eq(key_part->field))
125 return !(key_part->key_part_flag & HA_PART_KEY_SEG);
126 }
127 if ((tbl->file->ha_table_flags() & HA_PRIMARY_KEY_IN_READ_INDEX) &&
128 tbl->s->primary_key != MAX_KEY &&
129 tbl->s->primary_key != keyno)
130 {
131 key_info= tbl->key_info + tbl->s->primary_key;
132 key_part= key_info->key_part;
133 key_part_end= key_part + key_info->user_defined_key_parts;
134 for ( ; key_part < key_part_end; key_part++)
135 {
136 /*
137 It does not make sense to use the fact that the engine can read in
138 a full field if the key if the index is built only over a part
139 of this field.
140 */
141 if (field->eq(key_part->field))
142 return !(key_part->key_part_flag & HA_PART_KEY_SEG);
143 }
144 }
145 return FALSE;
146 }
147 case Item::REF_ITEM:
148 return uses_index_fields_only(item->real_item(), tbl, keyno,
149 other_tbls_ok);
150 default:
151 return FALSE; /* Play it safe, don't push unknown non-const items */
152 }
153}
154
155#define ICP_COND_USES_INDEX_ONLY 10
156
157/*
158 Get a part of the condition that can be checked using only index fields
159
160 SYNOPSIS
161 make_cond_for_index()
162 cond The source condition
163 table The table that is partially available
164 keyno The index in the above table. Only fields covered by the index
165 are available
166 other_tbls_ok TRUE <=> Fields of other non-const tables are allowed
167
168 DESCRIPTION
169 Get a part of the condition that can be checked when for the given table
170 we have values only of fields covered by some index. The condition may
171 refer to other tables, it is assumed that we have values of all of their
172 fields.
173
174 Example:
175 make_cond_for_index(
176 "cond(t1.field) AND cond(t2.key1) AND cond(t2.non_key) AND cond(t2.key2)",
177 t2, keyno(t2.key1))
178 will return
179 "cond(t1.field) AND cond(t2.key2)"
180
181 RETURN
182 Index condition, or NULL if no condition could be inferred.
183*/
184
185static Item *make_cond_for_index(THD *thd, Item *cond, TABLE *table, uint keyno,
186 bool other_tbls_ok)
187{
188 if (!cond)
189 return NULL;
190 if (cond->type() == Item::COND_ITEM)
191 {
192 uint n_marked= 0;
193 if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
194 {
195 table_map used_tables= 0;
196 Item_cond_and *new_cond= new (thd->mem_root) Item_cond_and(thd);
197 if (!new_cond)
198 return (COND*) 0;
199 List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
200 Item *item;
201 while ((item=li++))
202 {
203 Item *fix= make_cond_for_index(thd, item, table, keyno, other_tbls_ok);
204 if (fix)
205 {
206 new_cond->argument_list()->push_back(fix, thd->mem_root);
207 used_tables|= fix->used_tables();
208 }
209 if (MY_TEST(item->marker == ICP_COND_USES_INDEX_ONLY))
210 {
211 n_marked++;
212 item->marker= 0;
213 }
214 }
215 if (n_marked ==((Item_cond*)cond)->argument_list()->elements)
216 cond->marker= ICP_COND_USES_INDEX_ONLY;
217 switch (new_cond->argument_list()->elements) {
218 case 0:
219 return (COND*) 0;
220 case 1:
221 new_cond->used_tables_cache= used_tables;
222 return new_cond->argument_list()->head();
223 default:
224 new_cond->quick_fix_field();
225 new_cond->used_tables_cache= used_tables;
226 return new_cond;
227 }
228 }
229 else /* It's OR */
230 {
231 Item_cond_or *new_cond= new (thd->mem_root) Item_cond_or(thd);
232 if (!new_cond)
233 return (COND*) 0;
234 List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
235 Item *item;
236 while ((item=li++))
237 {
238 Item *fix= make_cond_for_index(thd, item, table, keyno, other_tbls_ok);
239 if (!fix)
240 return (COND*) 0;
241 new_cond->argument_list()->push_back(fix, thd->mem_root);
242 if (MY_TEST(item->marker == ICP_COND_USES_INDEX_ONLY))
243 {
244 n_marked++;
245 item->marker= 0;
246 }
247 }
248 if (n_marked ==((Item_cond*)cond)->argument_list()->elements)
249 cond->marker= ICP_COND_USES_INDEX_ONLY;
250 new_cond->quick_fix_field();
251 new_cond->used_tables_cache= ((Item_cond_or*) cond)->used_tables_cache;
252 new_cond->top_level_item();
253 return new_cond;
254 }
255 }
256
257 if (!uses_index_fields_only(cond, table, keyno, other_tbls_ok))
258 return (COND*) 0;
259 cond->marker= ICP_COND_USES_INDEX_ONLY;
260 return cond;
261}
262
263
264static Item *make_cond_remainder(THD *thd, Item *cond, TABLE *table, uint keyno,
265 bool other_tbls_ok, bool exclude_index)
266{
267 if (cond->type() == Item::COND_ITEM)
268 {
269 table_map tbl_map= 0;
270 if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
271 {
272 /* Create new top level AND item */
273 Item_cond_and *new_cond= new (thd->mem_root) Item_cond_and(thd);
274 if (!new_cond)
275 return (COND*) 0;
276 List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
277 Item *item;
278 while ((item=li++))
279 {
280 Item *fix= make_cond_remainder(thd, item, table, keyno,
281 other_tbls_ok, exclude_index);
282 if (fix)
283 {
284 new_cond->argument_list()->push_back(fix, thd->mem_root);
285 tbl_map |= fix->used_tables();
286 }
287 }
288 switch (new_cond->argument_list()->elements) {
289 case 0:
290 return (COND*) 0;
291 case 1:
292 return new_cond->argument_list()->head();
293 default:
294 new_cond->quick_fix_field();
295 ((Item_cond*)new_cond)->used_tables_cache= tbl_map;
296 return new_cond;
297 }
298 }
299 else /* It's OR */
300 {
301 Item_cond_or *new_cond= new (thd->mem_root) Item_cond_or(thd);
302 if (!new_cond)
303 return (COND*) 0;
304 List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
305 Item *item;
306 while ((item=li++))
307 {
308 Item *fix= make_cond_remainder(thd, item, table, keyno,
309 other_tbls_ok, FALSE);
310 if (!fix)
311 return (COND*) 0;
312 new_cond->argument_list()->push_back(fix, thd->mem_root);
313 tbl_map |= fix->used_tables();
314 }
315 new_cond->quick_fix_field();
316 ((Item_cond*)new_cond)->used_tables_cache= tbl_map;
317 new_cond->top_level_item();
318 return new_cond;
319 }
320 }
321 else
322 {
323 if (exclude_index &&
324 uses_index_fields_only(cond, table, keyno, other_tbls_ok))
325 return 0;
326 else
327 return cond;
328 }
329}
330
331
332/*
333 Try to extract and push the index condition
334
335 SYNOPSIS
336 push_index_cond()
337 tab A join tab that has tab->table->file and its condition
338 in tab->select_cond
339 keyno Index for which extract and push the condition
340
341 DESCRIPTION
342 Try to extract and push the index condition down to table handler
343*/
344
345void push_index_cond(JOIN_TAB *tab, uint keyno)
346{
347 DBUG_ENTER("push_index_cond");
348 Item *idx_cond;
349
350 /*
351 Backported the following from MySQL 5.6:
352 6. The index is not a clustered index. The performance improvement
353 of pushing an index condition on a clustered key is much lower
354 than on a non-clustered key. This restriction should be
355 re-evaluated when WL#6061 is implemented.
356 */
357 if ((tab->table->file->index_flags(keyno, 0, 1) &
358 HA_DO_INDEX_COND_PUSHDOWN) &&
359 optimizer_flag(tab->join->thd, OPTIMIZER_SWITCH_INDEX_COND_PUSHDOWN) &&
360 tab->join->thd->lex->sql_command != SQLCOM_UPDATE_MULTI &&
361 tab->join->thd->lex->sql_command != SQLCOM_DELETE_MULTI &&
362 tab->type != JT_CONST && tab->type != JT_SYSTEM &&
363 !(keyno == tab->table->s->primary_key && // (6)
364 tab->table->file->primary_key_is_clustered())) // (6)
365
366 {
367 DBUG_EXECUTE("where",
368 print_where(tab->select_cond, "full cond", QT_ORDINARY););
369
370 idx_cond= make_cond_for_index(tab->join->thd, tab->select_cond, tab->table,
371 keyno, tab->icp_other_tables_ok);
372
373 DBUG_EXECUTE("where",
374 print_where(idx_cond, "idx cond", QT_ORDINARY););
375
376 if (idx_cond)
377 {
378 Item *idx_remainder_cond= 0;
379 tab->pre_idx_push_select_cond= tab->select_cond;
380 /*
381 For BKA cache we store condition to special BKA cache field
382 because evaluation of the condition requires additional operations
383 before the evaluation. This condition is used in
384 JOIN_CACHE_BKA[_UNIQUE]::skip_index_tuple() functions.
385 */
386 if (tab->use_join_cache &&
387 /*
388 if cache is used then the value is TRUE only
389 for BKA[_UNIQUE] cache (see check_join_cache_usage func).
390 */
391 tab->icp_other_tables_ok &&
392 (idx_cond->used_tables() &
393 ~(tab->table->map | tab->join->const_table_map)))
394 tab->cache_idx_cond= idx_cond;
395 else
396 idx_remainder_cond= tab->table->file->idx_cond_push(keyno, idx_cond);
397
398 /*
399 Disable eq_ref's "lookup cache" if we've pushed down an index
400 condition.
401 TODO: This check happens to work on current ICP implementations, but
402 there may exist a compliant implementation that will not work
403 correctly with it. Sort this out when we stabilize the condition
404 pushdown APIs.
405 */
406 if (idx_remainder_cond != idx_cond)
407 tab->ref.disable_cache= TRUE;
408
409 Item *row_cond= tab->idx_cond_fact_out ?
410 make_cond_remainder(tab->join->thd, tab->select_cond,
411 tab->table, keyno,
412 tab->icp_other_tables_ok, TRUE) :
413 tab->pre_idx_push_select_cond;
414
415 DBUG_EXECUTE("where",
416 print_where(row_cond, "remainder cond", QT_ORDINARY););
417
418 if (row_cond)
419 {
420 if (!idx_remainder_cond)
421 tab->select_cond= row_cond;
422 else
423 {
424 COND *new_cond= new (tab->join->thd->mem_root)
425 Item_cond_and(tab->join->thd, row_cond, idx_remainder_cond);
426 tab->select_cond= new_cond;
427 tab->select_cond->quick_fix_field();
428 ((Item_cond_and*)tab->select_cond)->used_tables_cache=
429 row_cond->used_tables() | idx_remainder_cond->used_tables();
430 }
431 }
432 else
433 tab->select_cond= idx_remainder_cond;
434 if (tab->select)
435 {
436 DBUG_EXECUTE("where",
437 print_where(tab->select->cond,
438 "select_cond",
439 QT_ORDINARY););
440
441 tab->select->cond= tab->select_cond;
442 tab->select->pre_idx_push_select_cond= tab->pre_idx_push_select_cond;
443 }
444 }
445 }
446 DBUG_VOID_RETURN;
447}
448
449
450