drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
optimizer/sum.cc
Go to the documentation of this file.
1/* - mode: c; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2 * vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
3 *
4 * Copyright (C) 2008-2009 Sun Microsystems, Inc.
5 *
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.
10 *
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.
15 *
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
19 */
20
53
54#include <config.h>
55
56#include <drizzled/sql_select.h>
57#include <drizzled/item/sum.h>
58#include <drizzled/item/cmpfunc.h>
59#include <drizzled/optimizer/sum.h>
60#include <drizzled/plugin/storage_engine.h>
61#include <drizzled/table_list.h>
62#include <drizzled/key.h>
63#include <drizzled/error.h>
64#include <drizzled/key_part_info.h>
65
66namespace drizzled
67{
68
69static bool find_key_for_maxmin(bool max_fl,
71 Field* field,
72 COND *cond,
73 uint32_t *range_fl,
74 uint32_t *key_prefix_length);
75
76static int reckey_in_range(bool max_fl,
78 Field* field,
79 COND *cond,
80 uint32_t range_fl,
81 uint32_t prefix_len);
82
83static int maxmin_in_range(bool max_fl, Field *field, COND *cond);
84
85
86/*
87 Get exact count of rows in all tables
88
89 SYNOPSIS
90 get_exact_records()
91 tables List of tables
92
93 NOTES
94 When this is called, we know all table handlers supports HA_HAS_RECORDS
95 or HA_STATS_RECORDS_IS_EXACT
96
97 RETURN
98 UINT64_MAX Error: Could not calculate number of rows
99 # Multiplication of number of rows in all tables
100*/
101static uint64_t get_exact_record_count(TableList *tables)
102{
103 uint64_t count= 1;
104 for (TableList *tl= tables; tl; tl= tl->next_leaf)
105 {
106 ha_rows tmp= tl->table->cursor->records();
107 if ((tmp == HA_POS_ERROR))
108 {
109 return UINT64_MAX;
110 }
111 count*= tmp;
112 }
113 return count;
114}
115
116
117int optimizer::sum_query(TableList *tables, List<Item> &all_fields, COND *conds)
118{
119 List<Item>::iterator it(all_fields.begin());
120 int const_result= 1;
121 bool recalc_const_item= false;
122 uint64_t count= 1;
123 bool is_exact_count= true;
124 bool maybe_exact_count= true;
125 table_map removed_tables= 0;
126 table_map outer_tables= 0;
127 table_map used_tables= 0;
128 table_map where_tables= 0;
129 Item *item= NULL;
130 int error;
131
132 if (conds)
133 {
134 where_tables= conds->used_tables();
135 }
136
137 /*
138 Analyze outer join dependencies, and, if possible, compute the number
139 of returned rows.
140 */
141 for (TableList *tl= tables; tl; tl= tl->next_leaf)
142 {
143 TableList *embedded= NULL;
144 for (embedded= tl; embedded; embedded= embedded->getEmbedding())
145 {
146 if (embedded->on_expr)
147 break;
148 }
149 if (embedded)
150 /* Don't replace expression on a table that is part of an outer join */
151 {
152 outer_tables|= tl->table->map;
153
154 /*
155 We can't optimise LEFT JOIN in cases where the WHERE condition
156 restricts the table that is used, like in:
157 SELECT MAX(t1.a) FROM t1 LEFT JOIN t2 join-condition
158 WHERE t2.field IS NULL;
159 */
160 if (tl->table->map & where_tables)
161 return 0;
162 }
163 else
164 {
165 used_tables|= tl->table->map;
166 }
167
168 /*
169 If the storage manager of 'tl' gives exact row count as part of
170 statistics (cheap), compute the total number of rows. If there are
171 no outer table dependencies, this count may be used as the real count.
172 Schema tables are filled after this function is invoked, so we can't
173 get row count
174 */
175 if (! (tl->table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)))
176 {
177 maybe_exact_count&= test(tl->table->cursor->getEngine()->check_flag(HTON_BIT_HAS_RECORDS));
178 is_exact_count= false;
179 count= 1; // ensure count != 0
180 }
181 else
182 {
183 error= tl->table->cursor->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
184 if(error)
185 {
186 tl->table->print_error(error, MYF(ME_FATALERROR));
187 return error;
188 }
189 count*= tl->table->cursor->stats.records;
190 }
191 }
192
193 /*
194 Iterate through all items in the SELECT clause and replace
195 COUNT(), MIN() and MAX() with constants (if possible).
196 */
197
198 while ((item= it++))
199 {
200 if (item->type() == Item::SUM_FUNC_ITEM)
201 {
202 Item_sum *item_sum= (((Item_sum*) item));
203 switch (item_sum->sum_func())
204 {
205 case Item_sum::COUNT_FUNC:
206 /*
207 If the expr in COUNT(expr) can never be null we can change this
208 to the number of rows in the tables if this number is exact and
209 there are no outer joins.
210 */
211 if (! conds && ! ((Item_sum_count*) item)->args[0]->maybe_null &&
212 ! outer_tables && maybe_exact_count)
213 {
214 if (! is_exact_count)
215 {
216 if ((count= get_exact_record_count(tables)) == UINT64_MAX)
217 {
218 /* Error from handler in counting rows. Don't optimize count() */
219 const_result= 0;
220 continue;
221 }
222 is_exact_count= 1; // count is now exact
223 }
224 ((Item_sum_count*) item)->make_const_count((int64_t) count);
225 recalc_const_item= 1;
226 }
227 else
228 {
229 const_result= 0;
230 }
231 break;
232 case Item_sum::MIN_FUNC:
233 {
234 /*
235 If MIN(expr) is the first part of a key or if all previous
236 parts of the key is found in the COND, then we can use
237 indexes to find the key.
238 */
239 Item *expr=item_sum->args[0];
240 if (expr->real_item()->type() == Item::FIELD_ITEM)
241 {
242 unsigned char key_buff[MAX_KEY_LENGTH];
244 uint32_t range_fl, prefix_len;
245
246 ref.key_buff= key_buff;
247 Item_field *item_field= (Item_field*) (expr->real_item());
248 Table *table= item_field->field->getTable();
249
250 /*
251 Look for a partial key that can be used for optimization.
252 If we succeed, ref.key_length will contain the length of
253 this key, while prefix_len will contain the length of
254 the beginning of this key without field used in MIN().
255 Type of range for the key part for this field will be
256 returned in range_fl.
257 */
258 if (table->cursor->inited ||
259 (outer_tables & table->map) ||
261 &ref,
262 item_field->field,
263 conds,
264 &range_fl,
265 &prefix_len))
266 {
267 const_result= 0;
268 break;
269 }
270 error= table->cursor->startIndexScan(static_cast<uint32_t>(ref.key), 1);
271 if (error)
272 {
273 if (table->key_read)
274 {
275 table->key_read= 0;
276 table->cursor->extra(HA_EXTRA_NO_KEYREAD);
277 }
278 table->print_error(error, MYF(0));
279 return error;
280 }
281
282 if (! ref.key_length)
283 {
284 error= table->cursor->index_first(table->record[0]);
285 }
286 else
287 {
288 /*
289 Use index to replace MIN/MAX functions with their values
290 according to the following rules:
291
292 1) Insert the minimum non-null values where the WHERE clause still
293 matches, or
294 2) a NULL value if there are only NULL values for key_part_k.
295 3) Fail, producing a row of nulls
296
297 Implementation: Read the smallest value using the search key. If
298 the interval is open, read the next value after the search
299 key. If read fails, and we're looking for a MIN() value for a
300 nullable column, test if there is an exact match for the key.
301 */
302 if (! (range_fl & NEAR_MIN))
303 {
304 /*
305 Closed interval: Either The MIN argument is non-nullable, or
306 we have a >= predicate for the MIN argument.
307 */
308 error= table->cursor->index_read_map(table->record[0],
309 ref.key_buff,
310 make_prev_keypart_map(ref.key_parts),
311 HA_READ_KEY_OR_NEXT);
312 }
313 else
314 {
315 /*
316 Open interval: There are two cases:
317 1) We have only MIN() and the argument column is nullable, or
318 2) there is a > predicate on it, nullability is irrelevant.
319 We need to scan the next bigger record first.
320 */
321 error= table->cursor->index_read_map(table->record[0],
322 ref.key_buff,
323 make_prev_keypart_map(ref.key_parts),
324 HA_READ_AFTER_KEY);
325 /*
326 If the found record is outside the group formed by the search
327 prefix, or there is no such record at all, check if all
328 records in that group have NULL in the MIN argument
329 column. If that is the case return that NULL.
330
331 Check if case 1 from above holds. If it does, we should read
332 the skipped tuple.
333 */
334 if (item_field->field->real_maybe_null() &&
335 ref.key_buff[prefix_len] == 1 &&
336 /*
337 Last keypart (i.e. the argument to MIN) is set to NULL by
338 find_key_for_maxmin only if all other keyparts are bound
339 to constants in a conjunction of equalities. Hence, we
340 can detect this by checking only if the last keypart is
341 NULL.
342 */
343 (error == HA_ERR_KEY_NOT_FOUND ||
344 key_cmp_if_same(table, ref.key_buff, ref.key, prefix_len)))
345 {
346 assert(item_field->field->real_maybe_null());
347 error= table->cursor->index_read_map(table->record[0],
348 ref.key_buff,
349 make_prev_keypart_map(ref.key_parts),
350 HA_READ_KEY_EXACT);
351 }
352 }
353 }
354 /* Verify that the read tuple indeed matches the search key */
355 if (! error &&
357 &ref,
358 item_field->field,
359 conds,
360 range_fl,
361 prefix_len))
362 {
363 error= HA_ERR_KEY_NOT_FOUND;
364 }
365 if (table->key_read)
366 {
367 table->key_read= 0;
368 table->cursor->extra(HA_EXTRA_NO_KEYREAD);
369 }
370 table->cursor->endIndexScan();
371 if (error)
372 {
373 if (error == HA_ERR_KEY_NOT_FOUND || error == HA_ERR_END_OF_FILE)
374 {
375 return HA_ERR_KEY_NOT_FOUND; // No rows matching WHERE
376 }
377 /* HA_ERR_LOCK_DEADLOCK or some other error */
378 table->print_error(error, MYF(0));
379 return error;
380 }
381 removed_tables|= table->map;
382 }
383 else if (! expr->const_item() || ! is_exact_count)
384 {
385 /*
386 The optimization is not applicable in both cases:
387 (a) 'expr' is a non-constant expression. Then we can't
388 replace 'expr' by a constant.
389 (b) 'expr' is a costant. According to ANSI, MIN/MAX must return
390 NULL if the query does not return any rows. Thus, if we are not
391 able to determine if the query returns any rows, we can't apply
392 the optimization and replace MIN/MAX with a constant.
393 */
394 const_result= 0;
395 break;
396 }
397 if (! count)
398 {
399 /* If count == 0, then we know that is_exact_count == true. */
400 ((Item_sum_min*) item_sum)->clear(); /* Set to NULL. */
401 }
402 else
403 {
404 ((Item_sum_min*) item_sum)->reset(); /* Set to the constant value. */
405 }
406 ((Item_sum_min*) item_sum)->make_const();
407 recalc_const_item= 1;
408 break;
409 }
410 case Item_sum::MAX_FUNC:
411 {
412 /*
413 If MAX(expr) is the first part of a key or if all previous
414 parts of the key is found in the COND, then we can use
415 indexes to find the key.
416 */
417 Item *expr= item_sum->args[0];
418 if (expr->real_item()->type() == Item::FIELD_ITEM)
419 {
420 unsigned char key_buff[MAX_KEY_LENGTH];
422 uint32_t range_fl, prefix_len;
423
424 ref.key_buff= key_buff;
425 Item_field *item_field= (Item_field*) (expr->real_item());
426 Table *table= item_field->field->getTable();
427
428 /*
429 Look for a partial key that can be used for optimization.
430 If we succeed, ref.key_length will contain the length of
431 this key, while prefix_len will contain the length of
432 the beginning of this key without field used in MAX().
433 Type of range for the key part for this field will be
434 returned in range_fl.
435 */
436 if (table->cursor->inited ||
437 (outer_tables & table->map) ||
439 &ref,
440 item_field->field,
441 conds,
442 &range_fl,
443 &prefix_len))
444 {
445 const_result= 0;
446 break;
447 }
448 error= table->cursor->startIndexScan(static_cast<uint32_t>(ref.key), 1);
449
450 if (! ref.key_length)
451 {
452 error= table->cursor->index_last(table->record[0]);
453 }
454 else
455 {
456 error= table->cursor->index_read_map(table->record[0],
457 key_buff,
458 make_prev_keypart_map(ref.key_parts),
459 range_fl & NEAR_MAX ?
460 HA_READ_BEFORE_KEY :
461 HA_READ_PREFIX_LAST_OR_PREV);
462 }
463 if (! error &&
465 &ref,
466 item_field->field,
467 conds,
468 range_fl,
469 prefix_len))
470 {
471 error= HA_ERR_KEY_NOT_FOUND;
472 }
473 if (table->key_read)
474 {
475 table->key_read= 0;
476 table->cursor->extra(HA_EXTRA_NO_KEYREAD);
477 }
478 table->cursor->endIndexScan();
479 if (error)
480 {
481 if (error == HA_ERR_KEY_NOT_FOUND || error == HA_ERR_END_OF_FILE)
482 {
483 return HA_ERR_KEY_NOT_FOUND; // No rows matching WHERE
484 }
485 /* HA_ERR_LOCK_DEADLOCK or some other error */
486 table->print_error(error, MYF(ME_FATALERROR));
487 return error;
488 }
489 removed_tables|= table->map;
490 }
491 else if (! expr->const_item() || ! is_exact_count)
492 {
493 /*
494 The optimization is not applicable in both cases:
495 (a) 'expr' is a non-constant expression. Then we can't
496 replace 'expr' by a constant.
497 (b) 'expr' is a costant. According to ANSI, MIN/MAX must return
498 NULL if the query does not return any rows. Thus, if we are not
499 able to determine if the query returns any rows, we can't apply
500 the optimization and replace MIN/MAX with a constant.
501 */
502 const_result= 0;
503 break;
504 }
505 if (! count)
506 {
507 /* If count != 1, then we know that is_exact_count == true. */
508 ((Item_sum_max*) item_sum)->clear(); /* Set to NULL. */
509 }
510 else
511 {
512 ((Item_sum_max*) item_sum)->reset(); /* Set to the constant value. */
513 }
514 ((Item_sum_max*) item_sum)->make_const();
515 recalc_const_item= 1;
516 break;
517 }
518 default:
519 const_result= 0;
520 break;
521 }
522 }
523 else if (const_result)
524 {
525 if (recalc_const_item)
526 {
527 item->update_used_tables();
528 }
529 if (! item->const_item())
530 {
531 const_result= 0;
532 }
533 }
534 }
535 /*
536 If we have a where clause, we can only ignore searching in the
537 tables if MIN/MAX optimisation replaced all used tables
538 We do not use replaced values in case of:
539 SELECT MIN(key) FROM table_1, empty_table
540 removed_tables is != 0 if we have used MIN() or MAX().
541 */
542 if (removed_tables && used_tables != removed_tables)
543 {
544 const_result= 0; // We didn't remove all tables
545 }
546 return const_result;
547}
548
549
550bool optimizer::simple_pred(Item_func *func_item, Item **args, bool &inv_order)
551{
552 Item *item= NULL;
553 inv_order= false;
554 switch (func_item->argument_count())
555 {
556 case 0:
557 /* MULT_EQUAL_FUNC */
558 {
559 Item_equal *item_equal= (Item_equal *) func_item;
560 Item_equal_iterator it(item_equal->begin());
561 args[0]= it++;
562 if (it++)
563 {
564 return 0;
565 }
566 if (! (args[1]= item_equal->get_const()))
567 {
568 return 0;
569 }
570 }
571 break;
572 case 1:
573 /* field IS NULL */
574 item= func_item->arguments()[0];
575 if (item->type() != Item::FIELD_ITEM)
576 {
577 return 0;
578 }
579 args[0]= item;
580 break;
581 case 2:
582 /* 'field op const' or 'const op field' */
583 item= func_item->arguments()[0];
584 if (item->type() == Item::FIELD_ITEM)
585 {
586 args[0]= item;
587 item= func_item->arguments()[1];
588 if (! item->const_item())
589 {
590 return 0;
591 }
592 args[1]= item;
593 }
594 else if (item->const_item())
595 {
596 args[1]= item;
597 item= func_item->arguments()[1];
598 if (item->type() != Item::FIELD_ITEM)
599 {
600 return 0;
601 }
602 args[0]= item;
603 inv_order= true;
604 }
605 else
606 {
607 return 0;
608 }
609 break;
610 case 3:
611 /* field BETWEEN const AND const */
612 item= func_item->arguments()[0];
613 if (item->type() == Item::FIELD_ITEM)
614 {
615 args[0]= item;
616 for (int i= 1 ; i <= 2; i++)
617 {
618 item= func_item->arguments()[i];
619 if (! item->const_item())
620 {
621 return 0;
622 }
623 args[i]= item;
624 }
625 }
626 else
627 {
628 return 0;
629 }
630 }
631 return 1;
632}
633
634
664static bool matching_cond(bool max_fl,
666 KeyInfo *keyinfo,
667 KeyPartInfo *field_part,
668 COND *cond,
669 key_part_map *key_part_used,
670 uint32_t *range_fl,
671 uint32_t *prefix_len)
672{
673 if (! cond)
674 {
675 return 1;
676 }
677 Field *field= field_part->field;
678
679 field->setWriteSet();
680
681 if (! (cond->used_tables() & field->getTable()->map))
682 {
683 /* Condition doesn't restrict the used table */
684 return 1;
685 }
686 if (cond->type() == Item::COND_ITEM)
687 {
688 if (((Item_cond*) cond)->functype() == Item_func::COND_OR_FUNC)
689 {
690 return 0;
691 }
692
693 /* AND */
694 List<Item>::iterator li(((Item_cond*) cond)->argument_list()->begin());
695 Item *item;
696 while ((item= li++))
697 {
698 if (! matching_cond(max_fl,
699 ref,
700 keyinfo,
701 field_part,
702 item,
703 key_part_used,
704 range_fl,
705 prefix_len))
706 {
707 return 0;
708 }
709 }
710 return 1;
711 }
712
713 if (cond->type() != Item::FUNC_ITEM)
714 {
715 return 0; // Not operator, can't optimize
716 }
717
718 bool eq_type= false; // =, <=> or IS NULL
719 bool noeq_type= false; // < or >
720 bool less_fl= false; // < or <=
721 bool is_null= false;
722 bool between= false;
723
724 switch (((Item_func*) cond)->functype())
725 {
726 case Item_func::ISNULL_FUNC:
727 is_null= 1; /* fall through */
728 case Item_func::EQ_FUNC:
729 case Item_func::EQUAL_FUNC:
730 eq_type= 1;
731 break;
732 case Item_func::LT_FUNC:
733 noeq_type= 1; /* fall through */
734 case Item_func::LE_FUNC:
735 less_fl= 1;
736 break;
737 case Item_func::GT_FUNC:
738 noeq_type= 1; /* fall through */
739 case Item_func::GE_FUNC:
740 break;
741 case Item_func::BETWEEN:
742 between= 1;
743 break;
744 case Item_func::MULT_EQUAL_FUNC:
745 eq_type= 1;
746 break;
747 default:
748 return 0; // Can't optimize function
749 }
750
751 Item *args[3];
752 bool inv;
753
754 /* Test if this is a comparison of a field and constant */
755 if (! optimizer::simple_pred((Item_func*) cond, args, inv))
756 {
757 return 0;
758 }
759
760 if (inv && ! eq_type)
761 {
762 less_fl= 1 - less_fl; // Convert '<' -> '>' (etc)
763 }
764
765 /* Check if field is part of the tested partial key */
766 unsigned char *key_ptr= ref->key_buff;
767 KeyPartInfo *part= NULL;
768 for (part= keyinfo->key_part; ; key_ptr+= part++->store_length)
769
770 {
771 if (part > field_part)
772 {
773 return 0; // Field is beyond the tested parts
774 }
775 if (part->field->eq(((Item_field*) args[0])->field))
776 {
777 break; // Found a part of the key for the field
778 }
779 }
780
781 bool is_field_part= part == field_part;
782 if (! (is_field_part || eq_type))
783 {
784 return 0;
785 }
786
787 key_part_map org_key_part_used= *key_part_used;
788 if (eq_type || between || max_fl == less_fl)
789 {
790 uint32_t length= (key_ptr-ref->key_buff)+part->store_length;
791 if (ref->key_length < length)
792 {
793 /* Ultimately ref->key_length will contain the length of the search key */
794 ref->key_length= length;
795 ref->key_parts= (part - keyinfo->key_part) + 1;
796 }
797 if (! *prefix_len && part + 1 == field_part)
798 {
799 *prefix_len= length;
800 }
801 if (is_field_part && eq_type)
802 {
803 *prefix_len= ref->key_length;
804 }
805
806 *key_part_used|= (key_part_map) 1 << (part - keyinfo->key_part);
807 }
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)
823 {
824 part->field->set_null();
825 *key_ptr= (unsigned char) 1;
826 }
827 else
828 {
829 store_val_in_field(part->field, args[between && max_fl ? 2 : 1],
830 CHECK_FIELD_IGNORE);
831 if (part->null_bit)
832 {
833 *key_ptr++= (unsigned char) test(part->field->is_null());
834 }
835 part->field->get_key_image(key_ptr, part->length);
836 }
837 if (is_field_part)
838 {
839 if (between || eq_type)
840 {
841 *range_fl&= ~(NO_MAX_RANGE | NO_MIN_RANGE);
842 }
843 else
844 {
845 *range_fl&= ~(max_fl ? NO_MAX_RANGE : NO_MIN_RANGE);
846 if (noeq_type)
847 {
848 *range_fl|= (max_fl ? NEAR_MAX : NEAR_MIN);
849 }
850 else
851 {
852 *range_fl&= ~(max_fl ? NEAR_MAX : NEAR_MIN);
853 }
854 }
855 }
856 }
857 else if (eq_type)
858 {
859 if ((! is_null && !cond->val_int()) ||
860 (is_null && !test(part->field->is_null())))
861 {
862 return 0; // Impossible test
863 }
864 }
865 else if (is_field_part)
866 {
867 *range_fl&= ~(max_fl ? NO_MIN_RANGE : NO_MAX_RANGE);
868 }
869 return 1;
870}
871
872
914static bool find_key_for_maxmin(bool max_fl,
916 Field* field,
917 COND *cond,
918 uint32_t *range_fl,
919 uint32_t *prefix_len)
920{
921 if (! (field->flags & PART_KEY_FLAG))
922 {
923 return 0; // Not key field
924 }
925
926 Table *table= field->getTable();
927 uint32_t idx= 0;
928
929 KeyInfo *keyinfo,*keyinfo_end= NULL;
930 for (keyinfo= table->key_info, keyinfo_end= keyinfo+table->getShare()->sizeKeys();
931 keyinfo != keyinfo_end;
932 keyinfo++,idx++)
933 {
934 KeyPartInfo *part= NULL;
935 KeyPartInfo *part_end= NULL;
936 key_part_map key_part_to_use= 0;
937 /*
938 Perform a check if index is not disabled by ALTER Table
939 or IGNORE INDEX.
940 */
941 if (! table->keys_in_use_for_query.test(idx))
942 {
943 continue;
944 }
945 uint32_t jdx= 0;
946 *prefix_len= 0;
947 for (part= keyinfo->key_part, part_end= part+keyinfo->key_parts;
948 part != part_end;
949 part++, jdx++, key_part_to_use= (key_part_to_use << 1) | 1)
950 {
951 if (! (table->index_flags(idx) & HA_READ_ORDER))
952 {
953 return 0;
954 }
955
956 /* Check whether the index component is partial */
957 Field *part_field= table->getField(part->fieldnr-1);
958 part_field->setWriteSet();
959
960 if ((part_field->flags & BLOB_FLAG) ||
961 part->length < part_field->key_length())
962 {
963 break;
964 }
965
966 if (field->eq(part->field))
967 {
968 ref->key= idx;
969 ref->key_length= 0;
970 ref->key_parts= 0;
971 key_part_map key_part_used= 0;
972 *range_fl= NO_MIN_RANGE | NO_MAX_RANGE;
973 if (matching_cond(max_fl,
974 ref,
975 keyinfo,
976 part,
977 cond,
978 &key_part_used,
979 range_fl,
980 prefix_len) &&
981 ! (key_part_to_use & ~key_part_used))
982 {
983 if (! max_fl && key_part_used == key_part_to_use && part->null_bit)
984 {
985 /*
986 The query is on this form:
987
988 SELECT MIN(key_part_k)
989 FROM t1
990 WHERE key_part_1 = const and ... and key_part_k-1 = const
991
992 If key_part_k is nullable, we want to find the first matching row
993 where key_part_k is not null. The key buffer is now {const, ...,
994 NULL}. This will be passed to the handler along with a flag
995 indicating open interval. If a tuple is read that does not match
996 these search criteria, an attempt will be made to read an exact
997 match for the key buffer.
998 */
999 /* Set the first byte of key_part_k to 1, that means NULL */
1000 ref->key_buff[ref->key_length]= 1;
1001 ref->key_length+= part->store_length;
1002 ref->key_parts++;
1003 assert(ref->key_parts == jdx+1);
1004 *range_fl&= ~NO_MIN_RANGE;
1005 *range_fl|= NEAR_MIN; // Open interval
1006 }
1007 /*
1008 The following test is false when the key in the key tree is
1009 converted (for example to upper case)
1010 */
1011 if (field->part_of_key.test(idx))
1012 {
1013 table->key_read= 1;
1014 table->cursor->extra(HA_EXTRA_KEYREAD);
1015 }
1016 return 1;
1017 }
1018 }
1019 }
1020 }
1021 return 0;
1022}
1023
1024
1040static int reckey_in_range(bool max_fl,
1041 table_reference_st *ref,
1042 Field* field,
1043 COND *cond,
1044 uint32_t range_fl,
1045 uint32_t prefix_len)
1046{
1047 if (key_cmp_if_same(field->getTable(), ref->key_buff, ref->key, prefix_len))
1048 {
1049 return 1;
1050 }
1051 if (! cond || (range_fl & (max_fl ? NO_MIN_RANGE : NO_MAX_RANGE)))
1052 {
1053 return 0;
1054 }
1055 return maxmin_in_range(max_fl, field, cond);
1056}
1057
1058
1071static int maxmin_in_range(bool max_fl, Field* field, COND *cond)
1072{
1073 /* If AND/OR condition */
1074 if (cond->type() == Item::COND_ITEM)
1075 {
1076 List<Item>::iterator li(((Item_cond*) cond)->argument_list()->begin());
1077 while (Item* item= li++)
1078 {
1079 if (maxmin_in_range(max_fl, field, item))
1080 return 1;
1081 }
1082 return 0;
1083 }
1084
1085 if (cond->used_tables() != field->getTable()->map)
1086 {
1087 return 0;
1088 }
1089 bool less_fl= false;
1090 switch (((Item_func*) cond)->functype())
1091 {
1092 case Item_func::BETWEEN:
1093 return cond->val_int() == 0; // Return 1 if WHERE is false
1094 case Item_func::LT_FUNC:
1095 case Item_func::LE_FUNC:
1096 less_fl= 1;
1097 /* fallthrough */
1098 case Item_func::GT_FUNC:
1099 case Item_func::GE_FUNC:
1100 {
1101 Item *item= ((Item_func*) cond)->arguments()[1];
1102 /* In case of 'const op item' we have to swap the operator */
1103 if (! item->const_item())
1104 {
1105 less_fl= 1-less_fl;
1106 }
1107 /*
1108 We only have to check the expression if we are using an expression like
1109 SELECT MAX(b) FROM t1 WHERE a=const AND b>const
1110 not for
1111 SELECT MAX(b) FROM t1 WHERE a=const AND b<const
1112 */
1113 if (max_fl != less_fl)
1114 {
1115 return cond->val_int() == 0; // Return 1 if WHERE is false
1116 }
1117 return 0;
1118 }
1119 case Item_func::EQ_FUNC:
1120 case Item_func::EQUAL_FUNC:
1121 break;
1122 default:
1123 ; // assert(false); // Impossible; Olaf: Not really, assert is hit. BUG?
1124 }
1125 return 0;
1126}
1127
1128} /* namespace drizzled */
1129
virtual uint32_t get_key_image(unsigned char *buff, uint32_t length)
Definition field.h:423
virtual int64_t val_int()=0
virtual table_map used_tables() const
Definition item.h:453
TableList * next_leaf
Definition table_list.h:214
bool store_val_in_field(Field *field, Item *item, enum_check_fields check_flag)
TODO: Rename this file - func.h is stupid.
static bool find_key_for_maxmin(bool max_fl, table_reference_st *ref, Field *field, COND *cond, uint32_t *range_fl, uint32_t *key_prefix_length)
static int reckey_in_range(bool max_fl, table_reference_st *ref, Field *field, COND *cond, uint32_t range_fl, uint32_t prefix_len)
static bool matching_cond(bool max_fl, table_reference_st *ref, KeyInfo *keyinfo, KeyPartInfo *field_part, COND *cond, key_part_map *key_part_used, uint32_t *range_fl, uint32_t *prefix_len)
static int maxmin_in_range(bool max_fl, Field *field, COND *cond)
bool key_cmp_if_same(Table *table, const unsigned char *key, uint32_t idx, uint32_t key_length)