drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
key_field.cc
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
21#include <config.h>
22
23#include <drizzled/sql_select.h>
24#include <drizzled/nested_join.h>
25#include <drizzled/item/cmpfunc.h>
26#include <drizzled/table.h>
27#include <drizzled/optimizer/key_field.h>
28#include <drizzled/optimizer/key_use.h>
29#include <drizzled/sql_lex.h>
30#include <drizzled/item/subselect.h>
31#include <drizzled/key_part_info.h>
32
33#include <vector>
34
35using namespace std;
36
37namespace drizzled
38{
39
40void optimizer::add_key_part(DYNAMIC_ARRAY *keyuse_array,
41 optimizer::KeyField *key_field)
42{
43 Field *field= key_field->getField();
44 Table *form= field->getTable();
45
46 if (key_field->isEqualityCondition() &&
47 ! (key_field->getOptimizeFlags() & KEY_OPTIMIZE_EXISTS))
48 {
49 for (uint32_t key= 0; key < form->sizeKeys(); key++)
50 {
51 if (! (form->keys_in_use_for_query.test(key)))
52 continue;
53
54 uint32_t key_parts= (uint32_t) form->key_info[key].key_parts;
55 for (uint32_t part= 0; part < key_parts; part++)
56 {
57 if (field->eq(form->key_info[key].key_part[part].field))
58 {
59 optimizer::KeyUse keyuse(field->getTable(),
60 key_field->getValue(),
61 key_field->getValue()->used_tables(),
62 key,
63 part,
64 key_field->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL,
65 1 << part,
66 0,
67 key_field->rejectNullValues(),
68 key_field->getConditionalGuard());
69 keyuse_array->push_back(&keyuse);
70 }
71 }
72 }
73 }
74}
75
76void optimizer::add_key_fields_for_nj(Join *join,
77 TableList *nested_join_table,
79 uint32_t *and_level,
80 vector<optimizer::SargableParam> &sargables)
81{
82 List<TableList>::iterator li(nested_join_table->getNestedJoin()->join_list.begin());
83 List<TableList>::iterator li2(nested_join_table->getNestedJoin()->join_list.begin());
84 bool have_another= false;
85 table_map tables= 0;
86 TableList *table;
87 assert(nested_join_table->getNestedJoin());
88
89 while ((table= li++) || (have_another && (li=li2, have_another=false,
90 (table= li++))))
91 {
92 if (table->getNestedJoin())
93 {
94 if (! table->on_expr)
95 {
96 /* It's a semi-join nest. Walk into it as if it wasn't a nest */
97 have_another= true;
98 li2= li;
99 li= List<TableList>::iterator(table->getNestedJoin()->join_list.begin());
100 }
101 else
102 add_key_fields_for_nj(join, table, end, and_level, sargables);
103 }
104 else
105 if (! table->on_expr)
106 tables|= table->table->map;
107 }
108 if (nested_join_table->on_expr)
109 {
110 add_key_fields(join,
111 end,
112 and_level,
113 nested_join_table->on_expr,
114 tables,
115 sargables);
116 }
117}
118
119optimizer::KeyField *optimizer::merge_key_fields(optimizer::KeyField *start,
120 optimizer::KeyField *new_fields,
122 uint32_t and_level)
123{
124 if (start == new_fields)
125 return start; // Impossible or
126 if (new_fields == end)
127 return start; // No new fields, skip all
128
129 optimizer::KeyField *first_free= new_fields;
130
131 /* Mark all found fields in old array */
132 for (; new_fields != end; new_fields++)
133 {
134 for (optimizer::KeyField *old= start; old != first_free; old++)
135 {
136 if (old->getField() == new_fields->getField())
137 {
138 /*
139 NOTE: below const_item() call really works as "!used_tables()", i.e.
140 it can return false where it is feasible to make it return true.
141
142 The cause is as follows: Some of the tables are already known to be
143 const tables (the detection code is in make_join_statistics(),
144 above the update_ref_and_keys() call), but we didn't propagate
145 information about this: Table::const_table is not set to true, and
146 Item::update_used_tables() hasn't been called for each item.
147 The result of this is that we're missing some 'ref' accesses.
148 TODO: OptimizerTeam: Fix this
149 */
150 if (! new_fields->getValue()->const_item())
151 {
152 /*
153 If the value matches, we can use the key reference.
154 If not, we keep it until we have examined all new values
155 */
156 if (old->getValue()->eq(new_fields->getValue(), old->getField()->binary()))
157 {
158 old->setLevel(and_level);
159 old->setOptimizeFlags(((old->getOptimizeFlags() &
160 new_fields->getOptimizeFlags() &
161 KEY_OPTIMIZE_EXISTS) |
162 ((old->getOptimizeFlags() |
163 new_fields->getOptimizeFlags()) &
164 KEY_OPTIMIZE_REF_OR_NULL)));
165 old->setRejectNullValues(old->rejectNullValues() &&
166 new_fields->rejectNullValues());
167 }
168 }
169 else if (old->isEqualityCondition() &&
170 new_fields->isEqualityCondition() &&
171 old->getValue()->eq_by_collation(new_fields->getValue(),
172 old->getField()->binary(),
173 old->getField()->charset()))
174
175 {
176 old->setLevel(and_level);
177 old->setOptimizeFlags(((old->getOptimizeFlags() &
178 new_fields->getOptimizeFlags() &
179 KEY_OPTIMIZE_EXISTS) |
180 ((old->getOptimizeFlags() |
181 new_fields->getOptimizeFlags()) &
182 KEY_OPTIMIZE_REF_OR_NULL)));
183 old->setRejectNullValues(old->rejectNullValues() &&
184 new_fields->rejectNullValues());
185 }
186 else if (old->isEqualityCondition() &&
187 new_fields->isEqualityCondition() &&
188 ((old->getValue()->const_item() &&
189 old->getValue()->is_null()) ||
190 new_fields->getValue()->is_null()))
191 {
192 /* field = expression OR field IS NULL */
193 old->setLevel(and_level);
194 old->setOptimizeFlags(KEY_OPTIMIZE_REF_OR_NULL);
195 /*
196 Remember the NOT NULL value unless the value does not depend
197 on other tables.
198 */
199 if (! old->getValue()->used_tables() &&
200 old->getValue()->is_null())
201 {
202 old->setValue(new_fields->getValue());
203 }
204 /* The referred expression can be NULL: */
205 old->setRejectNullValues(false);
206 }
207 else
208 {
209 /*
210 We are comparing two different const. In this case we can't
211 use a key-lookup on this so it's better to remove the value
212 and let the range optimzier handle it
213 */
214 if (old == --first_free) // If last item
215 break;
216 *old= *first_free; // Remove old value
217 old--; // Retry this value
218 }
219 }
220 }
221 }
222 /* Remove all not used items */
223 for (optimizer::KeyField *old= start; old != first_free;)
224 {
225 if (old->getLevel() != and_level)
226 { // Not used in all levels
227 if (old == --first_free)
228 break;
229 *old= *first_free; // Remove old value
230 continue;
231 }
232 old++;
233 }
234 return first_free;
235}
236
237void optimizer::add_key_field(optimizer::KeyField **key_fields,
238 uint32_t and_level,
239 Item_func *cond,
240 Field *field,
241 bool eq_func,
242 Item **value,
243 uint32_t num_values,
244 table_map usable_tables,
245 vector<optimizer::SargableParam> &sargables)
246{
247 uint32_t exists_optimize= 0;
248 if (! (field->flags & PART_KEY_FLAG))
249 {
250 // Don't remove column IS NULL on a LEFT JOIN table
251 if (! eq_func || (*value)->type() != Item::NULL_ITEM ||
252 ! field->getTable()->maybe_null || field->null_ptr)
253 return; // Not a key. Skip it
254 exists_optimize= KEY_OPTIMIZE_EXISTS;
255 assert(num_values == 1);
256 }
257 else
258 {
259 table_map used_tables= 0;
260 bool optimizable= 0;
261 for (uint32_t i= 0; i < num_values; i++)
262 {
263 used_tables|= (value[i])->used_tables();
264 if (! ((value[i])->used_tables() & (field->getTable()->map | RAND_TABLE_BIT)))
265 optimizable= 1;
266 }
267 if (! optimizable)
268 return;
269 if (! (usable_tables & field->getTable()->map))
270 {
271 if (! eq_func || (*value)->type() != Item::NULL_ITEM ||
272 ! field->getTable()->maybe_null || field->null_ptr)
273 return; // Can't use left join optimize
274 exists_optimize= KEY_OPTIMIZE_EXISTS;
275 }
276 else
277 {
278 JoinTable *stat= field->getTable()->reginfo.join_tab;
279 key_map possible_keys= field->key_start;
280 possible_keys&= field->getTable()->keys_in_use_for_query;
281 stat[0].keys|= possible_keys; // Add possible keys
282
283 /*
284 Save the following cases:
285 Field op constant
286 Field LIKE constant where constant doesn't start with a wildcard
287 Field = field2 where field2 is in a different table
288 Field op formula
289 Field IS NULL
290 Field IS NOT NULL
291 Field BETWEEN ...
292 Field IN ...
293 */
294 stat[0].key_dependent|= used_tables;
295
296 bool is_const= 1;
297 for (uint32_t i= 0; i < num_values; i++)
298 {
299 if (! (is_const&= value[i]->const_item()))
300 break;
301 }
302 if (is_const)
303 stat[0].const_keys|= possible_keys;
304 else if (! eq_func)
305 {
306 /*
307 Save info to be able check whether this predicate can be
308 considered as sargable for range analisis after reading const tables.
309 We do not save info about equalities as update_const_equal_items
310 will take care of updating info on keys from sargable equalities.
311 */
312 optimizer::SargableParam tmp(field, value, num_values);
313 sargables.push_back(tmp);
314 }
315 /*
316 We can't always use indexes when comparing a string index to a
317 number. cmp_type() is checked to allow compare of dates to numbers.
318 eq_func is NEVER true when num_values > 1
319 */
320 if (! eq_func)
321 {
322 /*
323 Additional optimization: if we're processing
324 "t.key BETWEEN c1 AND c1" then proceed as if we were processing
325 "t.key = c1".
326 TODO: This is a very limited fix. A more generic fix is possible.
327 There are 2 options:
328 A) Make equality propagation code be able to handle BETWEEN
329 (including cases like t1.key BETWEEN t2.key AND t3.key)
330 B) Make range optimizer to infer additional "t.key = c" equalities
331 and use them in equality propagation process (see details in
332 OptimizerKBAndTodo)
333 */
334 if ((cond->functype() != Item_func::BETWEEN) ||
335 ((Item_func_between*) cond)->negated ||
336 ! value[0]->eq(value[1], field->binary()))
337 return;
338 eq_func= true;
339 }
340
341 if (field->result_type() == STRING_RESULT)
342 {
343 if ((*value)->result_type() != STRING_RESULT)
344 {
345 if (field->cmp_type() != (*value)->result_type())
346 return;
347 }
348 else
349 {
350 /*
351 We can't use indexes if the effective collation
352 of the operation differ from the field collation.
353 */
354 if (field->cmp_type() == STRING_RESULT &&
355 ((Field_str*)field)->charset() != cond->compare_collation())
356 return;
357 }
358 }
359 }
360 }
361 /*
362 For the moment eq_func is always true. This slot is reserved for future
363 extensions where we want to remembers other things than just eq comparisons
364 */
365 assert(eq_func);
366 /* Store possible eq field */
367 (*key_fields)->setField(field);
368 (*key_fields)->setEqualityConditionUsed(eq_func);
369 (*key_fields)->setValue(*value);
370 (*key_fields)->setLevel(and_level);
371 (*key_fields)->setOptimizeFlags(exists_optimize);
372 /*
373 If the condition has form "tbl.keypart = othertbl.field" and
374 othertbl.field can be NULL, there will be no matches if othertbl.field
375 has NULL value.
376 We use null_rejecting in add_not_null_conds() to add
377 'othertbl.field IS NOT NULL' to tab->select_cond.
378 */
379 (*key_fields)->setRejectNullValues((cond->functype() == Item_func::EQ_FUNC ||
380 cond->functype() == Item_func::MULT_EQUAL_FUNC) &&
381 ((*value)->type() == Item::FIELD_ITEM) &&
382 ((Item_field*)*value)->field->maybe_null());
383 (*key_fields)->setConditionalGuard(NULL);
384 (*key_fields)++;
385}
386
387void optimizer::add_key_equal_fields(optimizer::KeyField **key_fields,
388 uint32_t and_level,
389 Item_func *cond,
390 Item_field *field_item,
391 bool eq_func,
392 Item **val,
393 uint32_t num_values,
394 table_map usable_tables,
395 vector<optimizer::SargableParam> &sargables)
396{
397 Field *field= field_item->field;
398 add_key_field(key_fields, and_level, cond, field,
399 eq_func, val, num_values, usable_tables, sargables);
400 Item_equal *item_equal= field_item->item_equal;
401 if (item_equal)
402 {
403 /*
404 Add to the set of possible key values every substitution of
405 the field for an equal field included into item_equal
406 */
407 Item_equal_iterator it(item_equal->begin());
408 Item_field *item;
409 while ((item= it++))
410 {
411 if (! field->eq(item->field))
412 {
413 add_key_field(key_fields, and_level, cond, item->field,
414 eq_func, val, num_values, usable_tables,
415 sargables);
416 }
417 }
418 }
419}
420
421void optimizer::add_key_fields(Join *join,
422 optimizer::KeyField **key_fields,
423 uint32_t *and_level,
424 COND *cond,
425 table_map usable_tables,
426 vector<optimizer::SargableParam> &sargables)
427{
428 if (cond->type() == Item_func::COND_ITEM)
429 {
430 List<Item>::iterator li(((Item_cond*) cond)->argument_list()->begin());
431 optimizer::KeyField *org_key_fields= *key_fields;
432
433 if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
434 {
435 Item *item;
436 while ((item= li++))
437 {
438 add_key_fields(join,
439 key_fields,
440 and_level,
441 item,
442 usable_tables,
443 sargables);
444 }
445 for (; org_key_fields != *key_fields; org_key_fields++)
446 org_key_fields->setLevel(*and_level);
447 }
448 else
449 {
450 (*and_level)++;
451 add_key_fields(join,
452 key_fields,
453 and_level,
454 li++,
455 usable_tables,
456 sargables);
457 Item *item;
458 while ((item= li++))
459 {
460 optimizer::KeyField *start_key_fields= *key_fields;
461 (*and_level)++;
462 add_key_fields(join,
463 key_fields,
464 and_level,
465 item,
466 usable_tables,
467 sargables);
468 *key_fields= merge_key_fields(org_key_fields, start_key_fields,
469 *key_fields, ++(*and_level));
470 }
471 }
472 return;
473 }
474
475 /*
476 Subquery optimization: Conditions that are pushed down into subqueries
477 are wrapped into Item_func_trig_cond. We process the wrapped condition
478 but need to set cond_guard for KeyUse elements generated from it.
479 */
480 {
481 if (cond->type() == Item::FUNC_ITEM &&
482 ((Item_func*)cond)->functype() == Item_func::TRIG_COND_FUNC)
483 {
484 Item *cond_arg= ((Item_func*)cond)->arguments()[0];
485 if (! join->group_list &&
486 ! join->order &&
487 join->unit->item &&
488 join->unit->item->substype() == Item_subselect::IN_SUBS &&
489 ! join->unit->is_union())
490 {
491 optimizer::KeyField *save= *key_fields;
492 add_key_fields(join,
493 key_fields,
494 and_level,
495 cond_arg,
496 usable_tables,
497 sargables);
498 /* Indicate that this ref access candidate is for subquery lookup */
499 for (; save != *key_fields; save++)
500 save->setConditionalGuard(((Item_func_trig_cond*)cond)->get_trig_var());
501 }
502 return;
503 }
504 }
505
506 /* If item is of type 'field op field/constant' add it to key_fields */
507 if (cond->type() != Item::FUNC_ITEM)
508 return;
509 Item_func *cond_func= (Item_func*) cond;
510 switch (cond_func->select_optimize())
511 {
512 case Item_func::OPTIMIZE_NONE:
513 break;
514 case Item_func::OPTIMIZE_KEY:
515 {
516 Item **values;
517 // BETWEEN, IN, NE
518 if (cond_func->key_item()->real_item()->type() == Item::FIELD_ITEM &&
519 ! (cond_func->used_tables() & OUTER_REF_TABLE_BIT))
520 {
521 values= cond_func->arguments() + 1;
522 if (cond_func->functype() == Item_func::NE_FUNC &&
523 cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
524 ! (cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
525 values--;
526 assert(cond_func->functype() != Item_func::IN_FUNC ||
527 cond_func->argument_count() != 2);
528 add_key_equal_fields(key_fields, *and_level, cond_func,
529 (Item_field*) (cond_func->key_item()->real_item()),
530 0, values,
531 cond_func->argument_count()-1,
532 usable_tables, sargables);
533 }
534 if (cond_func->functype() == Item_func::BETWEEN)
535 {
536 values= cond_func->arguments();
537 for (uint32_t i= 1 ; i < cond_func->argument_count(); i++)
538 {
539 Item_field *field_item;
540 if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM
541 &&
542 ! (cond_func->arguments()[i]->used_tables() & OUTER_REF_TABLE_BIT))
543 {
544 field_item= (Item_field *) (cond_func->arguments()[i]->real_item());
545 add_key_equal_fields(key_fields, *and_level, cond_func,
546 field_item, 0, values, 1, usable_tables,
547 sargables);
548 }
549 }
550 }
551 break;
552 }
553 case Item_func::OPTIMIZE_OP:
554 {
555 bool equal_func= (cond_func->functype() == Item_func::EQ_FUNC ||
556 cond_func->functype() == Item_func::EQUAL_FUNC);
557
558 if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
559 ! (cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
560 {
561 add_key_equal_fields(key_fields, *and_level, cond_func,
562 (Item_field*) (cond_func->arguments()[0])->real_item(),
563 equal_func,
564 cond_func->arguments()+1, 1, usable_tables,
565 sargables);
566 }
567 if (cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
568 cond_func->functype() != Item_func::LIKE_FUNC &&
569 ! (cond_func->arguments()[1]->used_tables() & OUTER_REF_TABLE_BIT))
570 {
571 add_key_equal_fields(key_fields, *and_level, cond_func,
572 (Item_field*) (cond_func->arguments()[1])->real_item(), equal_func,
573 cond_func->arguments(),1,usable_tables,
574 sargables);
575 }
576 break;
577 }
578 case Item_func::OPTIMIZE_NULL:
579 /* column_name IS [NOT] NULL */
580 if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
581 ! (cond_func->used_tables() & OUTER_REF_TABLE_BIT))
582 {
583 Item *tmp= new Item_null;
584 if (DRIZZLE_UNLIKELY(! tmp)) // Should never be true
585 return;
586 add_key_equal_fields(key_fields, *and_level, cond_func,
587 (Item_field*) (cond_func->arguments()[0])->real_item(),
588 cond_func->functype() == Item_func::ISNULL_FUNC,
589 &tmp, 1, usable_tables, sargables);
590 }
591 break;
592 case Item_func::OPTIMIZE_EQUAL:
593 Item_equal *item_equal= (Item_equal *) cond;
594 Item *const_item= item_equal->get_const();
595 Item_equal_iterator it(item_equal->begin());
596 Item_field *item;
597 if (const_item)
598 {
599 /*
600 For each field field1 from item_equal consider the equality
601 field1=const_item as a condition allowing an index access of the table
602 with field1 by the keys value of field1.
603 */
604 while ((item= it++))
605 {
606 add_key_field(key_fields, *and_level, cond_func, item->field,
607 true, &const_item, 1, usable_tables, sargables);
608 }
609 }
610 else
611 {
612 /*
613 Consider all pairs of different fields included into item_equal.
614 For each of them (field1, field1) consider the equality
615 field1=field2 as a condition allowing an index access of the table
616 with field1 by the keys value of field2.
617 */
618 Item_equal_iterator fi(item_equal->begin());
619 while ((item= fi++))
620 {
621 Field *field= item->field;
622 while ((item= it++))
623 {
624 if (! field->eq(item->field))
625 {
626 add_key_field(key_fields, *and_level, cond_func, field,
627 true, (Item **) &item, 1, usable_tables,
628 sargables);
629 }
630 }
631 it= item_equal->begin();
632 }
633 }
634 break;
635 }
636}
637
638} /* namespace drizzled */
TODO: Rename this file - func.h is stupid.
STL namespace.