1 /* Copyright (c) 2000, 2011, Oracle and/or its affiliates.
2 Copyright (c) 2008, 2017, MariaDB Corporation.
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 St, Fifth Floor, Boston, MA 02110-1335 USA */
16
17
18 /**
19 @file
20
21 Optimising of MIN(), MAX() and COUNT(*) queries without 'group by' clause
22 by replacing the aggregate expression with a constant.
23
24 Given a table with a compound key on columns (a,b,c), the following
25 types of queries are optimised (assuming the table handler supports
26 the required methods)
27
28 @verbatim
29 SELECT COUNT(*) FROM t1[,t2,t3,...]
30 SELECT MIN(b) FROM t1 WHERE a=const
31 SELECT MAX(c) FROM t1 WHERE a=const AND b=const
32 SELECT MAX(b) FROM t1 WHERE a=const AND b<const
33 SELECT MIN(b) FROM t1 WHERE a=const AND b>const
34 SELECT MIN(b) FROM t1 WHERE a=const AND b BETWEEN const AND const
35 SELECT MAX(b) FROM t1 WHERE a=const AND b BETWEEN const AND const
36 @endverbatim
37
38 Instead of '<' one can use '<=', '>', '>=' and '=' as well.
39 Instead of 'a=const' the condition 'a IS NULL' can be used.
40
41 If all selected fields are replaced then we will also remove all
42 involved tables and return the answer without any join. Thus, the
43 following query will be replaced with a row of two constants:
44 @verbatim
45 SELECT MAX(b), MIN(d) FROM t1,t2
46 WHERE a=const AND b<const AND d>const
47 @endverbatim
48 (assuming a index for column d of table t2 is defined)
49 */
50
51 #include "mariadb.h"
52 #include "sql_priv.h"
53 #include "key.h" // key_cmp_if_same
54 #include "sql_select.h"
55
56 static bool find_key_for_maxmin(bool max_fl, TABLE_REF *ref, Field* field,
57 COND *cond, uint *range_fl,
58 uint *key_prefix_length);
59 static int reckey_in_range(bool max_fl, TABLE_REF *ref, Field* field,
60 COND *cond, uint range_fl, uint prefix_len);
61 static int maxmin_in_range(bool max_fl, Field* field, COND *cond);
62
63
64 /*
65 Get exact count of rows in all tables
66
67 SYNOPSIS
68 get_exact_records()
69 tables List of tables
70
71 NOTES
72 When this is called, we know all table handlers supports HA_HAS_RECORDS
73 or HA_STATS_RECORDS_IS_EXACT
74
75 RETURN
76 ULONGLONG_MAX Error: Could not calculate number of rows
77 # Multiplication of number of rows in all tables
78 */
79
get_exact_record_count(List<TABLE_LIST> & tables)80 static ulonglong get_exact_record_count(List<TABLE_LIST> &tables)
81 {
82 ulonglong count= 1;
83 TABLE_LIST *tl;
84 List_iterator<TABLE_LIST> ti(tables);
85 while ((tl= ti++))
86 {
87 ha_rows tmp= tl->table->file->records();
88 if (tmp == HA_POS_ERROR)
89 return ULONGLONG_MAX;
90 count*= tmp;
91 }
92 return count;
93 }
94
95
96 /**
97 Use index to read MIN(field) value.
98
99 @param table Table object
100 @param ref Reference to the structure where we store the key value
101 @item_field Field used in MIN()
102 @range_fl Whether range endpoint is strict less than
103 @prefix_len Length of common key part for the range
104
105 @retval
106 0 No errors
107 HA_ERR_... Otherwise
108 */
109
get_index_min_value(TABLE * table,TABLE_REF * ref,Item_field * item_field,uint range_fl,uint prefix_len)110 static int get_index_min_value(TABLE *table, TABLE_REF *ref,
111 Item_field *item_field, uint range_fl,
112 uint prefix_len)
113 {
114 int error;
115
116 if (!ref->key_length)
117 error= table->file->ha_index_first(table->record[0]);
118 else
119 {
120 /*
121 Use index to replace MIN/MAX functions with their values
122 according to the following rules:
123
124 1) Insert the minimum non-null values where the WHERE clause still
125 matches, or
126 2) a NULL value if there are only NULL values for key_part_k.
127 3) Fail, producing a row of nulls
128
129 Implementation: Read the smallest value using the search key. If
130 the interval is open, read the next value after the search
131 key. If read fails, and we're looking for a MIN() value for a
132 nullable column, test if there is an exact match for the key.
133 */
134 if (!(range_fl & NEAR_MIN))
135 /*
136 Closed interval: Either The MIN argument is non-nullable, or
137 we have a >= predicate for the MIN argument.
138 */
139 error= table->file->ha_index_read_map(table->record[0],
140 ref->key_buff,
141 make_prev_keypart_map(ref->key_parts),
142 HA_READ_KEY_OR_NEXT);
143 else
144 {
145 /*
146 Open interval: There are two cases:
147 1) We have only MIN() and the argument column is nullable, or
148 2) there is a > predicate on it, nullability is irrelevant.
149 We need to scan the next bigger record first.
150 Open interval is not used if the search key involves the last keypart,
151 and it would not work.
152 */
153 DBUG_ASSERT(prefix_len < ref->key_length);
154 error= table->file->ha_index_read_map(table->record[0],
155 ref->key_buff,
156 make_prev_keypart_map(ref->key_parts),
157 HA_READ_AFTER_KEY);
158 /*
159 If the found record is outside the group formed by the search
160 prefix, or there is no such record at all, check if all
161 records in that group have NULL in the MIN argument
162 column. If that is the case return that NULL.
163
164 Check if case 1 from above holds. If it does, we should read
165 the skipped tuple.
166 */
167 if (item_field->field->real_maybe_null() &&
168 ref->key_buff[prefix_len] == 1 &&
169 /*
170 Last keypart (i.e. the argument to MIN) is set to NULL by
171 find_key_for_maxmin only if all other keyparts are bound
172 to constants in a conjunction of equalities. Hence, we
173 can detect this by checking only if the last keypart is
174 NULL.
175 */
176 (error == HA_ERR_KEY_NOT_FOUND ||
177 key_cmp_if_same(table, ref->key_buff, ref->key, prefix_len)))
178 {
179 DBUG_ASSERT(item_field->field->real_maybe_null());
180 error= table->file->ha_index_read_map(table->record[0],
181 ref->key_buff,
182 make_prev_keypart_map(ref->key_parts),
183 HA_READ_KEY_EXACT);
184 }
185 }
186 }
187 return error;
188 }
189
190
191 /**
192 Use index to read MAX(field) value.
193
194 @param table Table object
195 @param ref Reference to the structure where we store the key value
196 @range_fl Whether range endpoint is strict greater than
197
198 @retval
199 0 No errors
200 HA_ERR_... Otherwise
201 */
202
get_index_max_value(TABLE * table,TABLE_REF * ref,uint range_fl)203 static int get_index_max_value(TABLE *table, TABLE_REF *ref, uint range_fl)
204 {
205 return (ref->key_length ?
206 table->file->ha_index_read_map(table->record[0], ref->key_buff,
207 make_prev_keypart_map(ref->key_parts),
208 range_fl & NEAR_MAX ?
209 HA_READ_BEFORE_KEY :
210 HA_READ_PREFIX_LAST_OR_PREV) :
211 table->file->ha_index_last(table->record[0]));
212 }
213
214
215
216 /**
217 Substitutes constants for some COUNT(), MIN() and MAX() functions.
218
219 @param thd thread handler
220 @param tables list of leaves of join table tree
221 @param all_fields All fields to be returned
222 @param conds WHERE clause
223
224 @note
225 This function is only called for queries with aggregate functions and no
226 GROUP BY part. This means that the result set shall contain a single
227 row only
228
229 @retval
230 0 no errors
231 @retval
232 1 if all items were resolved
233 @retval
234 HA_ERR_KEY_NOT_FOUND on impossible conditions
235 @retval
236 HA_ERR_... if a deadlock or a lock wait timeout happens, for example
237 @retval
238 ER_... e.g. ER_SUBQUERY_NO_1_ROW
239 */
240
opt_sum_query(THD * thd,List<TABLE_LIST> & tables,List<Item> & all_fields,COND * conds)241 int opt_sum_query(THD *thd,
242 List<TABLE_LIST> &tables, List<Item> &all_fields, COND *conds)
243 {
244 List_iterator_fast<Item> it(all_fields);
245 List_iterator<TABLE_LIST> ti(tables);
246 TABLE_LIST *tl;
247 int const_result= 1;
248 bool recalc_const_item= 0;
249 ulonglong count= 1;
250 bool is_exact_count= TRUE, maybe_exact_count= TRUE;
251 table_map removed_tables= 0, outer_tables= 0, used_tables= 0;
252 table_map where_tables= 0;
253 Item *item;
254 int error= 0;
255 DBUG_ENTER("opt_sum_query");
256
257 thd->lex->current_select->min_max_opt_list.empty();
258
259 if (conds)
260 where_tables= conds->used_tables();
261
262 /*
263 Analyze outer join dependencies, and, if possible, compute the number
264 of returned rows.
265 */
266 while ((tl= ti++))
267 {
268 TABLE_LIST *embedded;
269 for (embedded= tl ; embedded; embedded= embedded->embedding)
270 {
271 if (embedded->on_expr)
272 break;
273 }
274 if (embedded)
275 /* Don't replace expression on a table that is part of an outer join */
276 {
277 outer_tables|= tl->table->map;
278
279 /*
280 We can't optimise LEFT JOIN in cases where the WHERE condition
281 restricts the table that is used, like in:
282 SELECT MAX(t1.a) FROM t1 LEFT JOIN t2 join-condition
283 WHERE t2.field IS NULL;
284 */
285 if (tl->table->map & where_tables)
286 DBUG_RETURN(0);
287 }
288 else
289 used_tables|= tl->table->map;
290
291 /*
292 If the storage manager of 'tl' gives exact row count as part of
293 statistics (cheap), compute the total number of rows. If there are
294 no outer table dependencies, this count may be used as the real count.
295 Schema tables are filled after this function is invoked, so we can't
296 get row count
297 */
298 if (!(tl->table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) ||
299 tl->schema_table)
300 {
301 maybe_exact_count&= MY_TEST(!tl->schema_table &&
302 (tl->table->file->ha_table_flags() &
303 HA_HAS_RECORDS));
304 is_exact_count= FALSE;
305 count= 1; // ensure count != 0
306 }
307 else if (tl->is_materialized_derived() ||
308 tl->jtbm_subselect)
309 {
310 /*
311 Can't remove a derived table as it's number of rows is just an
312 estimate.
313 */
314 DBUG_RETURN(0);
315 }
316 else
317 {
318 error= tl->table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
319 if (unlikely(error))
320 {
321 tl->table->file->print_error(error, MYF(ME_FATAL));
322 DBUG_RETURN(error);
323 }
324 count*= tl->table->file->stats.records;
325 }
326 }
327
328 /*
329 Iterate through all items in the SELECT clause and replace
330 COUNT(), MIN() and MAX() with constants (if possible).
331 */
332
333 while ((item= it++))
334 {
335 if (item->type() == Item::SUM_FUNC_ITEM)
336 {
337 Item_sum *item_sum= (((Item_sum*) item));
338 switch (item_sum->sum_func()) {
339 case Item_sum::COUNT_FUNC:
340 /*
341 If the expr in COUNT(expr) can never be null we can change this
342 to the number of rows in the tables if this number is exact and
343 there are no outer joins.
344 */
345 if (!conds && !((Item_sum_count*) item)->get_arg(0)->maybe_null &&
346 !outer_tables && maybe_exact_count &&
347 ((item->used_tables() & OUTER_REF_TABLE_BIT) == 0))
348 {
349 if (!is_exact_count)
350 {
351 if ((count= get_exact_record_count(tables)) == ULONGLONG_MAX)
352 {
353 /* Error from handler in counting rows. Don't optimize count() */
354 const_result= 0;
355 continue;
356 }
357 is_exact_count= 1; // count is now exact
358 }
359 ((Item_sum_count*) item)->make_const((longlong) count);
360 recalc_const_item= 1;
361 }
362 else
363 const_result= 0;
364 break;
365 case Item_sum::MIN_FUNC:
366 case Item_sum::MAX_FUNC:
367 {
368 int is_max= MY_TEST(item_sum->sum_func() == Item_sum::MAX_FUNC);
369 /*
370 If MIN/MAX(expr) is the first part of a key or if all previous
371 parts of the key is found in the COND, then we can use
372 indexes to find the key.
373 */
374 Item *expr=item_sum->get_arg(0);
375 if (((expr->used_tables() & OUTER_REF_TABLE_BIT) == 0) &&
376 expr->real_item()->type() == Item::FIELD_ITEM)
377 {
378 uchar key_buff[MAX_KEY_LENGTH];
379 TABLE_REF ref;
380 uint range_fl, prefix_len;
381
382 ref.key_buff= key_buff;
383 Item_field *item_field= (Item_field*) (expr->real_item());
384 TABLE *table= item_field->field->table;
385
386 /*
387 Look for a partial key that can be used for optimization.
388 If we succeed, ref.key_length will contain the length of
389 this key, while prefix_len will contain the length of
390 the beginning of this key without field used in MIN/MAX().
391 Type of range for the key part for this field will be
392 returned in range_fl.
393 */
394 if (table->file->inited || (outer_tables & table->map) ||
395 !find_key_for_maxmin(is_max, &ref, item_field->field, conds,
396 &range_fl, &prefix_len))
397 {
398 const_result= 0;
399 break;
400 }
401 longlong info_limit= 1;
402 error= 0;
403
404 table->file->info_push(INFO_KIND_FORCE_LIMIT_BEGIN, &info_limit);
405 if (!table->const_table)
406 {
407 if (likely(!(error= table->file->ha_index_init((uint) ref.key,
408 1))))
409 error= (is_max ?
410 get_index_max_value(table, &ref, range_fl) :
411 get_index_min_value(table, &ref, item_field, range_fl,
412 prefix_len));
413 }
414 /* Verify that the read tuple indeed matches the search key */
415 if (!error &&
416 reckey_in_range(is_max, &ref, item_field->field,
417 conds, range_fl, prefix_len))
418 error= HA_ERR_KEY_NOT_FOUND;
419 if (!table->const_table)
420 {
421 table->file->ha_end_keyread();
422 table->file->ha_index_end();
423 }
424 table->file->info_push(INFO_KIND_FORCE_LIMIT_END, NULL);
425 if (error)
426 {
427 if (error == HA_ERR_KEY_NOT_FOUND || error == HA_ERR_END_OF_FILE)
428 DBUG_RETURN(HA_ERR_KEY_NOT_FOUND); // No rows matching WHERE
429 /* HA_ERR_LOCK_DEADLOCK or some other error */
430 table->file->print_error(error, MYF(0));
431 DBUG_RETURN(error);
432 }
433 removed_tables|= table->map;
434 }
435 else if (!expr->const_item() || !is_exact_count || conds)
436 {
437 /*
438 The optimization is not applicable in both cases:
439 (a) 'expr' is a non-constant expression. Then we can't
440 replace 'expr' by a constant.
441 (b) 'expr' is a costant. According to ANSI, MIN/MAX must return
442 NULL if the query does not return any rows. Thus, if we are not
443 able to determine if the query returns any rows, we can't apply
444 the optimization and replace MIN/MAX with a constant.
445 (c) there is a WHERE clause. The WHERE conditions may result in
446 an empty result, but the clause cannot be taken into account here.
447 */
448 const_result= 0;
449 break;
450 }
451 item_sum->set_aggregator(item_sum->has_with_distinct() ?
452 Aggregator::DISTINCT_AGGREGATOR :
453 Aggregator::SIMPLE_AGGREGATOR);
454 /*
455 If count == 0 (so is_exact_count == TRUE) and
456 there're no outer joins, set to NULL,
457 otherwise set to the constant value.
458 */
459 if (!count && !outer_tables)
460 {
461 item_sum->aggregator_clear();
462 }
463 else
464 {
465 item_sum->reset_and_add();
466 /*
467 Save a reference to the item for possible rollback
468 of the min/max optimizations for this select
469 */
470 thd->lex->current_select->min_max_opt_list.push_back(item_sum);
471 }
472 item_sum->make_const();
473 recalc_const_item= 1;
474 break;
475 }
476 default:
477 const_result= 0;
478 break;
479 }
480 }
481 else if (const_result)
482 {
483 if (recalc_const_item)
484 item->update_used_tables();
485 if (!item->const_item() && item->type() != Item::WINDOW_FUNC_ITEM)
486 const_result= 0;
487 }
488 }
489
490 if (unlikely(thd->is_error()))
491 DBUG_RETURN(thd->get_stmt_da()->sql_errno());
492
493 /*
494 If we have a where clause, we can only ignore searching in the
495 tables if MIN/MAX optimisation replaced all used tables
496 We do not use replaced values in case of:
497 SELECT MIN(key) FROM table_1, empty_table
498 removed_tables is != 0 if we have used MIN() or MAX().
499 */
500 if (removed_tables && used_tables != removed_tables)
501 const_result= 0; // We didn't remove all tables
502 DBUG_RETURN(const_result);
503 }
504
505
506 /*
507 Check if both item1 and item2 are strings, and item1 has fewer characters
508 than item2.
509 */
510
check_item1_shorter_item2(Item * item1,Item * item2)511 static bool check_item1_shorter_item2(Item *item1, Item *item2)
512 {
513 if (item1->cmp_type() == STRING_RESULT &&
514 item2->cmp_type() == STRING_RESULT)
515 {
516 int len1= item1->max_length / item1->collation.collation->mbmaxlen;
517 int len2= item2->max_length / item2->collation.collation->mbmaxlen;
518 return len1 < len2;
519 }
520 return false; /* When the check is not applicable, it means "not bigger" */
521 }
522
523
524 /**
525 Test if the predicate compares a field with constants.
526
527 @param func_item Predicate item
528 @param[out] args Here we store the field followed by constants
529 @param[out] inv_order Is set to 1 if the predicate is of the form
530 'const op field'
531
532 @retval
533 0 func_item is a simple predicate: a field is compared with a constant
534 whose length does not exceed the max length of the field values
535 @retval
536 1 Otherwise
537 */
538
simple_pred(Item_func * func_item,Item ** args,bool * inv_order)539 bool simple_pred(Item_func *func_item, Item **args, bool *inv_order)
540 {
541 Item *item;
542 *inv_order= 0;
543 switch (func_item->argument_count()) {
544 case 0:
545 /* MULT_EQUAL_FUNC */
546 {
547 Item_equal *item_equal= (Item_equal *) func_item;
548 if (!(args[1]= item_equal->get_const()))
549 return 0;
550 Item_equal_fields_iterator it(*item_equal);
551 if (!(item= it++))
552 return 0;
553 args[0]= item->real_item();
554 if (check_item1_shorter_item2(args[0], args[1]))
555 return 0;
556 if (it++)
557 return 0;
558 }
559 break;
560 case 1:
561 /* field IS NULL */
562 item= func_item->arguments()[0]->real_item();
563 if (item->type() != Item::FIELD_ITEM)
564 return 0;
565 args[0]= item;
566 break;
567 case 2:
568 /* 'field op const' or 'const op field' */
569 item= func_item->arguments()[0]->real_item();
570 if (item->type() == Item::FIELD_ITEM)
571 {
572 args[0]= item;
573 item= func_item->arguments()[1]->real_item();
574 if (!item->const_item())
575 return 0;
576 args[1]= item;
577 }
578 else if (item->const_item())
579 {
580 args[1]= item;
581 item= func_item->arguments()[1]->real_item();
582 if (item->type() != Item::FIELD_ITEM)
583 return 0;
584 args[0]= item;
585 *inv_order= 1;
586 }
587 else
588 return 0;
589 if (check_item1_shorter_item2(args[0], args[1]))
590 return 0;
591 break;
592 case 3:
593 /* field BETWEEN const AND const */
594 item= func_item->arguments()[0]->real_item();
595 if (item->type() == Item::FIELD_ITEM)
596 {
597 args[0]= item;
598 for (int i= 1 ; i <= 2; i++)
599 {
600 item= func_item->arguments()[i]->real_item();
601 if (!item->const_item())
602 return 0;
603 args[i]= item;
604 if (check_item1_shorter_item2(args[0], args[i]))
605 return 0;
606 }
607 }
608 else
609 return 0;
610 }
611 return 1;
612 }
613
614
615 /**
616 Check whether a condition matches a key to get {MAX|MIN}(field):.
617
618 For the index specified by the keyinfo parameter and an index that
619 contains the field as its component (field_part), the function
620 checks whether
621
622 - the condition cond is a conjunction,
623 - all of its conjuncts refer to columns of the same table, and
624 - each conjunct is on one of the following forms:
625 - f_i = const_i or const_i = f_i or f_i IS NULL,
626 where f_i is part of the index
627 - field {<|<=|>=|>|=} const
628 - const {<|<=|>=|>|=} field
629 - field BETWEEN const_1 AND const_2
630
631 As a side-effect, the key value to be used for looking up the MIN/MAX value
632 is actually stored inside the Field object. An interesting feature is that
633 the function will find the most restrictive endpoint by over-eager
634 evaluation of the @c WHERE condition. It continually stores the current
635 endpoint inside the Field object. For a query such as
636
637 @code
638 SELECT MIN(a) FROM t1 WHERE a > 3 AND a > 5;
639 @endcode
640
641 the algorithm will recurse over the conjuction, storing first a 3 in the
642 field. In the next recursive invocation the expression a > 5 is evaluated
643 as 3 > 5 (Due to the dual nature of Field objects as value carriers and
644 field identifiers), which will obviously fail, leading to 5 being stored in
645 the Field object.
646
647 @param[in] max_fl Set to true if we are optimizing MAX(),
648 false means we are optimizing %MIN()
649 @param[in, out] ref Reference to the structure where the function
650 stores the key value
651 @param[in] keyinfo Reference to the key info
652 @param[in] field_part Pointer to the key part for the field
653 @param[in] cond WHERE condition
654 @param[in,out] key_part_used Map of matchings parts. The function will output
655 the set of key parts actually being matched in
656 this set, yet it relies on the caller to
657 initialize the value to zero. This is due
658 to the fact that this value is passed
659 recursively.
660 @param[in,out] range_fl Says whether endpoints use strict greater/less
661 than.
662 @param[out] prefix_len Length of common key part for the range
663 where MAX/MIN is searched for
664
665 @retval
666 false Index can't be used.
667 @retval
668 true We can use the index to get MIN/MAX value
669 */
670
matching_cond(bool max_fl,TABLE_REF * ref,KEY * keyinfo,KEY_PART_INFO * field_part,COND * cond,key_part_map * key_part_used,uint * range_fl,uint * prefix_len)671 static bool matching_cond(bool max_fl, TABLE_REF *ref, KEY *keyinfo,
672 KEY_PART_INFO *field_part, COND *cond,
673 key_part_map *key_part_used, uint *range_fl,
674 uint *prefix_len)
675 {
676 DBUG_ENTER("matching_cond");
677 if (!cond)
678 DBUG_RETURN(TRUE);
679 Field *field= field_part->field;
680 table_map cond_used_tables= cond->used_tables();
681 if (cond_used_tables & OUTER_REF_TABLE_BIT)
682 {
683 DBUG_RETURN(FALSE);
684 }
685 if (!(cond_used_tables & field->table->map) &&
686 MY_TEST(cond_used_tables & ~PSEUDO_TABLE_BITS))
687 {
688 /* Condition doesn't restrict the used table */
689 DBUG_RETURN(!cond->const_item());
690 }
691 else if (cond->is_expensive())
692 DBUG_RETURN(FALSE);
693 if (cond->type() == Item::COND_ITEM)
694 {
695 if (((Item_cond*) cond)->functype() == Item_func::COND_OR_FUNC)
696 DBUG_RETURN(FALSE);
697
698 /* AND */
699 List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
700 Item *item;
701 while ((item= li++))
702 {
703 if (!matching_cond(max_fl, ref, keyinfo, field_part, item,
704 key_part_used, range_fl, prefix_len))
705 DBUG_RETURN(FALSE);
706 }
707 DBUG_RETURN(TRUE);
708 }
709
710 if (cond->type() != Item::FUNC_ITEM)
711 DBUG_RETURN(FALSE); // Not operator, can't optimize
712
713 bool eq_type= 0; // =, <=> or IS NULL
714 bool is_null_safe_eq= FALSE; // The operator is NULL safe, e.g. <=>
715 bool noeq_type= 0; // < or >
716 bool less_fl= 0; // < or <=
717 bool is_null= 0; // IS NULL
718 bool between= 0; // BETWEEN ... AND ...
719
720 switch (((Item_func*) cond)->functype()) {
721 case Item_func::ISNULL_FUNC:
722 is_null= 1; /* fall through */
723 case Item_func::EQ_FUNC:
724 eq_type= TRUE;
725 break;
726 case Item_func::EQUAL_FUNC:
727 eq_type= is_null_safe_eq= TRUE;
728 break;
729 case Item_func::LT_FUNC:
730 noeq_type= 1; /* fall through */
731 case Item_func::LE_FUNC:
732 less_fl= 1;
733 break;
734 case Item_func::GT_FUNC:
735 noeq_type= 1; /* fall through */
736 case Item_func::GE_FUNC:
737 break;
738 case Item_func::BETWEEN:
739 if (((Item_func_between*) cond)->negated)
740 DBUG_RETURN(FALSE);
741 between= 1;
742 break;
743 case Item_func::MULT_EQUAL_FUNC:
744 eq_type= 1;
745 break;
746 default:
747 DBUG_RETURN(FALSE); // Can't optimize function
748 }
749
750 Item *args[3];
751 bool inv;
752
753 /* Test if this is a comparison of a field and constant */
754 if (!simple_pred((Item_func*) cond, args, &inv))
755 DBUG_RETURN(FALSE);
756
757 if (!is_null_safe_eq && !is_null &&
758 (args[1]->is_null() || (between && args[2]->is_null())))
759 DBUG_RETURN(FALSE);
760
761 if (inv && !eq_type)
762 less_fl= 1-less_fl; // Convert '<' -> '>' (etc)
763
764 /* Check if field is part of the tested partial key */
765 uchar *key_ptr= ref->key_buff;
766 KEY_PART_INFO *part;
767 for (part= keyinfo->key_part; ; key_ptr+= part++->store_length)
768
769 {
770 if (part > field_part)
771 DBUG_RETURN(FALSE); // Field is beyond the tested parts
772 if (part->field->eq(((Item_field*) args[0])->field))
773 break; // Found a part of the key for the field
774 }
775
776 bool is_field_part= part == field_part;
777 if (!(is_field_part || eq_type))
778 DBUG_RETURN(FALSE);
779
780 key_part_map org_key_part_used= *key_part_used;
781 if (eq_type || between || max_fl == less_fl)
782 {
783 uint length= (uint)(key_ptr-ref->key_buff)+part->store_length;
784 if (ref->key_length < length)
785 {
786 /* Ultimately ref->key_length will contain the length of the search key */
787 ref->key_length= length;
788 ref->key_parts= (uint)(part - keyinfo->key_part) + 1;
789 }
790 if (!*prefix_len && part+1 == field_part)
791 *prefix_len= length;
792 if (is_field_part && eq_type)
793 *prefix_len= ref->key_length;
794
795 *key_part_used|= (key_part_map) 1 << (part - keyinfo->key_part);
796 }
797
798 if (org_key_part_used == *key_part_used &&
799 /*
800 The current search key is not being extended with a new key part. This
801 means that the a condition is added a key part for which there was a
802 previous condition. We can only overwrite such key parts in some special
803 cases, e.g. a > 2 AND a > 1 (here range_fl must be set to something). In
804 all other cases the WHERE condition is always false anyway.
805 */
806 (eq_type || *range_fl == 0))
807 DBUG_RETURN(FALSE);
808
809 if (org_key_part_used != *key_part_used ||
810 (is_field_part &&
811 (between || eq_type || max_fl == less_fl) && !cond->val_int()))
812 {
813 /*
814 It's the first predicate for this part or a predicate of the
815 following form that moves upper/lower bounds for max/min values:
816 - field BETWEEN const AND const
817 - field = const
818 - field {<|<=} const, when searching for MAX
819 - field {>|>=} const, when searching for MIN
820 */
821
822 if (is_null || (is_null_safe_eq && args[1]->is_null()))
823 {
824 /*
825 If we have a non-nullable index, we cannot use it,
826 since set_null will be ignored, and we will compare uninitialized data.
827 */
828 if (!part->field->real_maybe_null())
829 DBUG_RETURN(FALSE);
830 part->field->set_null();
831 *key_ptr= (uchar) 1;
832 }
833 else
834 {
835 /* Update endpoints for MAX/MIN, see function comment. */
836 Item *value= args[between && max_fl ? 2 : 1];
837 value->save_in_field_no_warnings(part->field, 1);
838 if (part->null_bit)
839 *key_ptr++= (uchar) MY_TEST(part->field->is_null());
840 part->field->get_key_image(key_ptr, part->length, Field::itRAW);
841 }
842 if (is_field_part)
843 {
844 if (between || eq_type)
845 {
846 *range_fl&= ~(NO_MAX_RANGE | NO_MIN_RANGE);
847 *range_fl&= ~(max_fl ? NEAR_MAX : NEAR_MIN);
848 }
849 else
850 {
851 *range_fl&= ~(max_fl ? NO_MAX_RANGE : NO_MIN_RANGE);
852 if (noeq_type)
853 *range_fl|= (max_fl ? NEAR_MAX : NEAR_MIN);
854 else
855 *range_fl&= ~(max_fl ? NEAR_MAX : NEAR_MIN);
856 }
857 }
858 }
859 else if (eq_type)
860 {
861 if ((!is_null && !cond->val_int()) ||
862 (is_null && !MY_TEST(part->field->is_null())))
863 DBUG_RETURN(FALSE); // Impossible test
864 }
865 else if (is_field_part)
866 *range_fl&= ~(max_fl ? NO_MIN_RANGE : NO_MAX_RANGE);
867 DBUG_RETURN(TRUE);
868 }
869
870
871 /**
872 Check whether we can get value for {max|min}(field) by using a key.
873
874 If where-condition is not a conjunction of 0 or more conjuct the
875 function returns false, otherwise it checks whether there is an
876 index including field as its k-th component/part such that:
877
878 -# for each previous component f_i there is one and only one conjunct
879 of the form: f_i= const_i or const_i= f_i or f_i is null
880 -# references to field occur only in conjucts of the form:
881 field {<|<=|>=|>|=} const or const {<|<=|>=|>|=} field or
882 field BETWEEN const1 AND const2
883 -# all references to the columns from the same table as column field
884 occur only in conjucts mentioned above.
885 -# each of k first components the index is not partial, i.e. is not
886 defined on a fixed length proper prefix of the field.
887
888 If such an index exists the function through the ref parameter
889 returns the key value to find max/min for the field using the index,
890 the length of first (k-1) components of the key and flags saying
891 how to apply the key for the search max/min value.
892 (if we have a condition field = const, prefix_len contains the length
893 of the whole search key)
894
895 @param[in] max_fl 0 for MIN(field) / 1 for MAX(field)
896 @param[in,out] ref Reference to the structure we store the key value
897 @param[in] field Field used inside MIN() / MAX()
898 @param[in] cond WHERE condition
899 @param[out] range_fl Bit flags for how to search if key is ok
900 @param[out] prefix_len Length of prefix for the search range
901
902 @note
903 This function may set field->table->key_read to true,
904 which must be reset after index is used!
905 (This can only happen when function returns 1)
906
907 @retval
908 0 Index can not be used to optimize MIN(field)/MAX(field)
909 @retval
910 1 Can use key to optimize MIN()/MAX().
911 In this case ref, range_fl and prefix_len are updated
912 */
913
find_key_for_maxmin(bool max_fl,TABLE_REF * ref,Field * field,COND * cond,uint * range_fl,uint * prefix_len)914 static bool find_key_for_maxmin(bool max_fl, TABLE_REF *ref,
915 Field* field, COND *cond,
916 uint *range_fl, uint *prefix_len)
917 {
918 if (!(field->flags & PART_KEY_FLAG))
919 return FALSE; // Not key field
920
921 DBUG_ENTER("find_key_for_maxmin");
922
923 TABLE *table= field->table;
924 uint idx= 0;
925
926 KEY *keyinfo,*keyinfo_end;
927 for (keyinfo= table->key_info, keyinfo_end= keyinfo+table->s->keys ;
928 keyinfo != keyinfo_end;
929 keyinfo++,idx++)
930 {
931 KEY_PART_INFO *part,*part_end;
932 key_part_map key_part_to_use= 0;
933 /*
934 Perform a check if index is not disabled by ALTER TABLE
935 or IGNORE INDEX.
936 */
937 if (!table->keys_in_use_for_query.is_set(idx))
938 continue;
939 uint jdx= 0;
940 *prefix_len= 0;
941 part_end= keyinfo->key_part+table->actual_n_key_parts(keyinfo);
942 for (part= keyinfo->key_part ;
943 part != part_end ;
944 part++, jdx++, key_part_to_use= (key_part_to_use << 1) | 1)
945 {
946 if (!(table->file->index_flags(idx, jdx, 0) & HA_READ_ORDER))
947 DBUG_RETURN(FALSE);
948
949 /* Check whether the index component is partial */
950 Field *part_field= table->field[part->fieldnr-1];
951 if ((part_field->flags & BLOB_FLAG) ||
952 part->length < part_field->key_length())
953 break;
954
955 if (field->eq(part->field))
956 {
957 ref->key= idx;
958 ref->key_length= 0;
959 ref->key_parts= 0;
960 key_part_map key_part_used= 0;
961 *range_fl= NO_MIN_RANGE | NO_MAX_RANGE;
962 if (matching_cond(max_fl, ref, keyinfo, part, cond,
963 &key_part_used, range_fl, prefix_len) &&
964 !(key_part_to_use & ~key_part_used))
965 {
966 if (!max_fl && key_part_used == key_part_to_use && part->null_bit)
967 {
968 /*
969 The query is on this form:
970
971 SELECT MIN(key_part_k)
972 FROM t1
973 WHERE key_part_1 = const and ... and key_part_k-1 = const
974
975 If key_part_k is nullable, we want to find the first matching row
976 where key_part_k is not null. The key buffer is now {const, ...,
977 NULL}. This will be passed to the handler along with a flag
978 indicating open interval. If a tuple is read that does not match
979 these search criteria, an attempt will be made to read an exact
980 match for the key buffer.
981 */
982 /* Set the first byte of key_part_k to 1, that means NULL */
983 ref->key_buff[ref->key_length]= 1;
984 ref->key_length+= part->store_length;
985 ref->key_parts++;
986 DBUG_ASSERT(ref->key_parts == jdx+1);
987 *range_fl&= ~NO_MIN_RANGE;
988 *range_fl|= NEAR_MIN; // Open interval
989 }
990 /*
991 The following test is false when the key in the key tree is
992 converted (for example to upper case)
993 */
994 if (field->part_of_key.is_set(idx))
995 table->file->ha_start_keyread(idx);
996 DBUG_RETURN(TRUE);
997 }
998 }
999 }
1000 }
1001 DBUG_RETURN(FALSE);
1002 }
1003
1004
1005 /**
1006 Check whether found key is in range specified by conditions.
1007
1008 @param[in] max_fl 0 for MIN(field) / 1 for MAX(field)
1009 @param[in] ref Reference to the key value and info
1010 @param[in] field Field used the MIN/MAX expression
1011 @param[in] cond WHERE condition
1012 @param[in] range_fl Says whether there is a condition to to be checked
1013 @param[in] prefix_len Length of the constant part of the key
1014
1015 @retval
1016 0 ok
1017 @retval
1018 1 WHERE was not true for the found row
1019 */
1020
reckey_in_range(bool max_fl,TABLE_REF * ref,Field * field,COND * cond,uint range_fl,uint prefix_len)1021 static int reckey_in_range(bool max_fl, TABLE_REF *ref, Field* field,
1022 COND *cond, uint range_fl, uint prefix_len)
1023 {
1024 if (key_cmp_if_same(field->table, ref->key_buff, ref->key, prefix_len))
1025 return 1;
1026 if (!cond || (range_fl & (max_fl ? NO_MIN_RANGE : NO_MAX_RANGE)))
1027 return 0;
1028 return maxmin_in_range(max_fl, field, cond);
1029 }
1030
1031
1032 /**
1033 Check whether {MAX|MIN}(field) is in range specified by conditions.
1034
1035 @param[in] max_fl 0 for MIN(field) / 1 for MAX(field)
1036 @param[in] field Field used the MIN/MAX expression
1037 @param[in] cond WHERE condition
1038
1039 @retval
1040 0 ok
1041 @retval
1042 1 WHERE was not true for the found row
1043 */
1044
maxmin_in_range(bool max_fl,Field * field,COND * cond)1045 static int maxmin_in_range(bool max_fl, Field* field, COND *cond)
1046 {
1047 /* If AND/OR condition */
1048 if (cond->type() == Item::COND_ITEM)
1049 {
1050 List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
1051 Item *item;
1052 while ((item= li++))
1053 {
1054 if (maxmin_in_range(max_fl, field, item))
1055 return 1;
1056 }
1057 return 0;
1058 }
1059
1060 if (cond->used_tables() != field->table->map)
1061 return 0;
1062 bool less_fl= 0;
1063 switch (((Item_func*) cond)->functype()) {
1064 case Item_func::BETWEEN:
1065 return cond->val_int() == 0; // Return 1 if WHERE is false
1066 case Item_func::LT_FUNC:
1067 case Item_func::LE_FUNC:
1068 less_fl= 1;
1069 /* fall through */
1070 case Item_func::GT_FUNC:
1071 case Item_func::GE_FUNC:
1072 {
1073 Item *item= ((Item_func*) cond)->arguments()[1];
1074 /* In case of 'const op item' we have to swap the operator */
1075 if (!item->const_item())
1076 less_fl= 1-less_fl;
1077 /*
1078 We only have to check the expression if we are using an expression like
1079 SELECT MAX(b) FROM t1 WHERE a=const AND b>const
1080 not for
1081 SELECT MAX(b) FROM t1 WHERE a=const AND b<const
1082 */
1083 if (max_fl != less_fl)
1084 return cond->val_int() == 0; // Return 1 if WHERE is false
1085 return 0;
1086 }
1087 default:
1088 break; // Ignore
1089 }
1090 return 0;
1091 }
1092
1093