« back to all changes in this revision
Viewing changes to drizzled/sql_select.cc
- browse files at revision 1115.3.10
- compare with another revision
- download diff
- download tarball
- view history from revision 1115.3.10
- Committer: Jay Pipes
- Date: 2009-08-20 18:28:11 UTC
- mfrom: (1108.6.52 optimizer)
- mto: This revision was merged to the branch mainline in revision 1120.
- Revision ID: jpipes@serialcoder-20090820182811-akpzlv3042dyyui7
Merge Padraig's optimizer refactoring around pulling structs into real classes...
- files added:
- drizzled/optimizer
- files modified:
- drizzled/Makefile.am
added
removed
drizzled/sql_select.cc
47
47
#include "drizzled/index_hint.h"
48
48
49
49
#include <drizzled/sql_union.h>
50
#include <drizzled/optimizer/key_field.h>
51
#include <drizzled/optimizer/position.h>
52
#include <drizzled/optimizer/sargable_param.h>
50
53
51
54
#include <string>
52
55
#include <iostream>
53
56
#include <algorithm>
57
#include <vector>
54
58
55
59
using namespace std;
60
using namespace drizzled;
56
61
57
62
static const string access_method_str[]=
58
63
{
495
500
keyuse Pointer to possible keys
496
501
*****************************************************************************/
497
502
498
/**
499
Merge new key definitions to old ones, remove those not used in both.
500
501
This is called for OR between different levels.
502
503
To be able to do 'ref_or_null' we merge a comparison of a column
504
and 'column IS NULL' to one test. This is useful for sub select queries
505
that are internally transformed to something like:.
506
507
@code
508
SELECT * FROM t1 WHERE t1.key=outer_ref_field or t1.key IS NULL
509
@endcode
510
511
KEY_FIELD::null_rejecting is processed as follows: @n
512
result has null_rejecting=true if it is set for both ORed references.
513
for example:
514
- (t2.key = t1.field OR t2.key = t1.field) -> null_rejecting=true
515
- (t2.key = t1.field OR t2.key <=> t1.field) -> null_rejecting=false
516
517
@todo
518
The result of this is that we're missing some 'ref' accesses.
519
OptimizerTeam: Fix this
520
*/
521
static KEY_FIELD *merge_key_fields(KEY_FIELD *start,KEY_FIELD *new_fields,KEY_FIELD *end, uint32_t and_level)
522
{
523
if (start == new_fields)
524
return start; // Impossible or
525
if (new_fields == end)
526
return start; // No new fields, skip all
527
528
KEY_FIELD *first_free=new_fields;
529
530
/* Mark all found fields in old array */
531
for (; new_fields != end ; new_fields++)
532
{
533
for (KEY_FIELD *old=start ; old != first_free ; old++)
534
{
535
if (old->field == new_fields->field)
536
{
537
/*
538
NOTE: below const_item() call really works as "!used_tables()", i.e.
539
it can return false where it is feasible to make it return true.
540
541
The cause is as follows: Some of the tables are already known to be
542
const tables (the detection code is in make_join_statistics(),
543
above the update_ref_and_keys() call), but we didn't propagate
544
information about this: Table::const_table is not set to true, and
545
Item::update_used_tables() hasn't been called for each item.
546
The result of this is that we're missing some 'ref' accesses.
547
TODO: OptimizerTeam: Fix this
548
*/
549
if (!new_fields->val->const_item())
550
{
551
/*
552
If the value matches, we can use the key reference.
553
If not, we keep it until we have examined all new values
554
*/
555
if (old->val->eq(new_fields->val, old->field->binary()))
556
{
557
old->level= and_level;
558
old->optimize= ((old->optimize & new_fields->optimize &
559
KEY_OPTIMIZE_EXISTS) |
560
((old->optimize | new_fields->optimize) &
561
KEY_OPTIMIZE_REF_OR_NULL));
562
old->null_rejecting= (old->null_rejecting &&
563
new_fields->null_rejecting);
564
}
565
}
566
else if (old->eq_func && new_fields->eq_func &&
567
old->val->eq_by_collation(new_fields->val,
568
old->field->binary(),
569
old->field->charset()))
570
571
{
572
old->level= and_level;
573
old->optimize= ((old->optimize & new_fields->optimize &
574
KEY_OPTIMIZE_EXISTS) |
575
((old->optimize | new_fields->optimize) &
576
KEY_OPTIMIZE_REF_OR_NULL));
577
old->null_rejecting= (old->null_rejecting &&
578
new_fields->null_rejecting);
579
}
580
else if (old->eq_func && new_fields->eq_func &&
581
((old->val->const_item() && old->val->is_null()) ||
582
new_fields->val->is_null()))
583
{
584
/* field = expression OR field IS NULL */
585
old->level= and_level;
586
old->optimize= KEY_OPTIMIZE_REF_OR_NULL;
587
/*
588
Remember the NOT NULL value unless the value does not depend
589
on other tables.
590
*/
591
if (!old->val->used_tables() && old->val->is_null())
592
old->val= new_fields->val;
593
/* The referred expression can be NULL: */
594
old->null_rejecting= 0;
595
}
596
else
597
{
598
/*
599
We are comparing two different const. In this case we can't
600
use a key-lookup on this so it's better to remove the value
601
and let the range optimzier handle it
602
*/
603
if (old == --first_free) // If last item
604
break;
605
*old= *first_free; // Remove old value
606
old--; // Retry this value
607
}
608
}
609
}
610
}
611
/* Remove all not used items */
612
for (KEY_FIELD *old=start ; old != first_free ;)
613
{
614
if (old->level != and_level)
615
{ // Not used in all levels
616
if (old == --first_free)
617
break;
618
*old= *first_free; // Remove old value
619
continue;
620
}
621
old++;
622
}
623
return first_free;
624
}
625
626
/**
627
Add a possible key to array of possible keys if it's usable as a key
628
629
@param key_fields Pointer to add key, if usable
630
@param and_level And level, to be stored in KEY_FIELD
631
@param cond Condition predicate
632
@param field Field used in comparision
633
@param eq_func True if we used =, <=> or IS NULL
634
@param value Value used for comparison with field
635
@param usable_tables Tables which can be used for key optimization
636
@param sargables IN/OUT Array of found sargable candidates
637
638
@note
639
If we are doing a NOT NULL comparison on a NOT NULL field in a outer join
640
table, we store this to be able to do not exists optimization later.
641
642
@returns
643
*key_fields is incremented if we stored a key in the array
644
*/
645
static void add_key_field(KEY_FIELD **key_fields,
646
uint32_t and_level,
647
Item_func *cond,
648
Field *field,
649
bool eq_func,
650
Item **value,
651
uint32_t num_values,
652
table_map usable_tables,
653
SARGABLE_PARAM **sargables)
654
{
655
uint32_t exists_optimize= 0;
656
if (!(field->flags & PART_KEY_FLAG))
657
{
658
// Don't remove column IS NULL on a LEFT JOIN table
659
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
660
!field->table->maybe_null || field->null_ptr)
661
return; // Not a key. Skip it
662
exists_optimize= KEY_OPTIMIZE_EXISTS;
663
assert(num_values == 1);
664
}
665
else
666
{
667
table_map used_tables=0;
668
bool optimizable=0;
669
for (uint32_t i=0; i<num_values; i++)
670
{
671
used_tables|=(value[i])->used_tables();
672
if (!((value[i])->used_tables() & (field->table->map | RAND_TABLE_BIT)))
673
optimizable=1;
674
}
675
if (!optimizable)
676
return;
677
if (!(usable_tables & field->table->map))
678
{
679
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
680
!field->table->maybe_null || field->null_ptr)
681
return; // Can't use left join optimize
682
exists_optimize= KEY_OPTIMIZE_EXISTS;
683
}
684
else
685
{
686
JoinTable *stat=field->table->reginfo.join_tab;
687
key_map possible_keys= field->key_start;
688
possible_keys&= field->table->keys_in_use_for_query;
689
stat[0].keys|= possible_keys; // Add possible keys
690
691
/*
692
Save the following cases:
693
Field op constant
694
Field LIKE constant where constant doesn't start with a wildcard
695
Field = field2 where field2 is in a different table
696
Field op formula
697
Field IS NULL
698
Field IS NOT NULL
699
Field BETWEEN ...
700
Field IN ...
701
*/
702
stat[0].key_dependent|= used_tables;
703
704
bool is_const=1;
705
for (uint32_t i=0; i<num_values; i++)
706
{
707
if (!(is_const&= value[i]->const_item()))
708
break;
709
}
710
if (is_const)
711
stat[0].const_keys|= possible_keys;
712
else if (!eq_func)
713
{
714
/*
715
Save info to be able check whether this predicate can be
716
considered as sargable for range analisis after reading const tables.
717
We do not save info about equalities as update_const_equal_items
718
will take care of updating info on keys from sargable equalities.
719
*/
720
(*sargables)--;
721
(*sargables)->field= field;
722
(*sargables)->arg_value= value;
723
(*sargables)->num_values= num_values;
724
}
725
/*
726
We can't always use indexes when comparing a string index to a
727
number. cmp_type() is checked to allow compare of dates to numbers.
728
eq_func is NEVER true when num_values > 1
729
*/
730
if (!eq_func)
731
{
732
/*
733
Additional optimization: if we're processing
734
"t.key BETWEEN c1 AND c1" then proceed as if we were processing
735
"t.key = c1".
736
TODO: This is a very limited fix. A more generic fix is possible.
737
There are 2 options:
738
A) Make equality propagation code be able to handle BETWEEN
739
(including cases like t1.key BETWEEN t2.key AND t3.key)
740
B) Make range optimizer to infer additional "t.key = c" equalities
741
and use them in equality propagation process (see details in
742
OptimizerKBAndTodo)
743
*/
744
if ((cond->functype() != Item_func::BETWEEN) ||
745
((Item_func_between*) cond)->negated ||
746
!value[0]->eq(value[1], field->binary()))
747
return;
748
eq_func= true;
749
}
750
751
if (field->result_type() == STRING_RESULT)
752
{
753
if ((*value)->result_type() != STRING_RESULT)
754
{
755
if (field->cmp_type() != (*value)->result_type())
756
return;
757
}
758
else
759
{
760
/*
761
We can't use indexes if the effective collation
762
of the operation differ from the field collation.
763
*/
764
if (field->cmp_type() == STRING_RESULT &&
765
((Field_str*)field)->charset() != cond->compare_collation())
766
return;
767
}
768
}
769
}
770
}
771
/*
772
For the moment eq_func is always true. This slot is reserved for future
773
extensions where we want to remembers other things than just eq comparisons
774
*/
775
assert(eq_func);
776
/* Store possible eq field */
777
(*key_fields)->field= field;
778
(*key_fields)->eq_func= eq_func;
779
(*key_fields)->val= *value;
780
(*key_fields)->level= and_level;
781
(*key_fields)->optimize= exists_optimize;
782
/*
783
If the condition has form "tbl.keypart = othertbl.field" and
784
othertbl.field can be NULL, there will be no matches if othertbl.field
785
has NULL value.
786
We use null_rejecting in add_not_null_conds() to add
787
'othertbl.field IS NOT NULL' to tab->select_cond.
788
*/
789
(*key_fields)->null_rejecting= ((cond->functype() == Item_func::EQ_FUNC ||
790
cond->functype() == Item_func::MULT_EQUAL_FUNC) &&
791
((*value)->type() == Item::FIELD_ITEM) &&
792
((Item_field*)*value)->field->maybe_null());
793
(*key_fields)->cond_guard= NULL;
794
(*key_fields)++;
795
}
796
797
/**
798
Add possible keys to array of possible keys originated from a simple
799
predicate.
800
801
@param key_fields Pointer to add key, if usable
802
@param and_level And level, to be stored in KEY_FIELD
803
@param cond Condition predicate
804
@param field Field used in comparision
805
@param eq_func True if we used =, <=> or IS NULL
806
@param value Value used for comparison with field
807
Is NULL for BETWEEN and IN
808
@param usable_tables Tables which can be used for key optimization
809
@param sargables IN/OUT Array of found sargable candidates
810
811
@note
812
If field items f1 and f2 belong to the same multiple equality and
813
a key is added for f1, the the same key is added for f2.
814
815
@returns
816
*key_fields is incremented if we stored a key in the array
817
*/
818
static void add_key_equal_fields(KEY_FIELD **key_fields,
819
uint32_t and_level,
820
Item_func *cond,
821
Item_field *field_item,
822
bool eq_func,
823
Item **val,
824
uint32_t num_values,
825
table_map usable_tables,
826
SARGABLE_PARAM **sargables)
827
{
828
Field *field= field_item->field;
829
add_key_field(key_fields, and_level, cond, field,
830
eq_func, val, num_values, usable_tables, sargables);
831
Item_equal *item_equal= field_item->item_equal;
832
if (item_equal)
833
{
834
/*
835
Add to the set of possible key values every substitution of
836
the field for an equal field included into item_equal
837
*/
838
Item_equal_iterator it(*item_equal);
839
Item_field *item;
840
while ((item= it++))
841
{
842
if (!field->eq(item->field))
843
{
844
add_key_field(key_fields, and_level, cond, item->field,
845
eq_func, val, num_values, usable_tables,
846
sargables);
847
}
848
}
849
}
850
}
851
852
static void add_key_fields(JOIN *join,
853
KEY_FIELD **key_fields,
854
uint32_t *and_level,
855
COND *cond,
856
table_map usable_tables,
857
SARGABLE_PARAM **sargables)
858
{
859
if (cond->type() == Item_func::COND_ITEM)
860
{
861
List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
862
KEY_FIELD *org_key_fields= *key_fields;
863
864
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
865
{
866
Item *item;
867
while ((item=li++))
868
add_key_fields(join, key_fields, and_level, item, usable_tables,
869
sargables);
870
for (; org_key_fields != *key_fields ; org_key_fields++)
871
org_key_fields->level= *and_level;
872
}
873
else
874
{
875
(*and_level)++;
876
add_key_fields(join, key_fields, and_level, li++, usable_tables,
877
sargables);
878
Item *item;
879
while ((item=li++))
880
{
881
KEY_FIELD *start_key_fields= *key_fields;
882
(*and_level)++;
883
add_key_fields(join, key_fields, and_level, item, usable_tables,
884
sargables);
885
*key_fields=merge_key_fields(org_key_fields,start_key_fields,
886
*key_fields,++(*and_level));
887
}
888
}
889
return;
890
}
891
892
/*
893
Subquery optimization: Conditions that are pushed down into subqueries
894
are wrapped into Item_func_trig_cond. We process the wrapped condition
895
but need to set cond_guard for KeyUse elements generated from it.
896
*/
897
{
898
if (cond->type() == Item::FUNC_ITEM &&
899
((Item_func*)cond)->functype() == Item_func::TRIG_COND_FUNC)
900
{
901
Item *cond_arg= ((Item_func*)cond)->arguments()[0];
902
if (!join->group_list && !join->order &&
903
join->unit->item &&
904
join->unit->item->substype() == Item_subselect::IN_SUBS &&
905
!join->unit->is_union())
906
{
907
KEY_FIELD *save= *key_fields;
908
add_key_fields(join, key_fields, and_level, cond_arg, usable_tables,
909
sargables);
910
// Indicate that this ref access candidate is for subquery lookup:
911
for (; save != *key_fields; save++)
912
save->cond_guard= ((Item_func_trig_cond*)cond)->get_trig_var();
913
}
914
return;
915
}
916
}
917
918
/* If item is of type 'field op field/constant' add it to key_fields */
919
if (cond->type() != Item::FUNC_ITEM)
920
return;
921
Item_func *cond_func= (Item_func*) cond;
922
switch (cond_func->select_optimize()) {
923
case Item_func::OPTIMIZE_NONE:
924
break;
925
case Item_func::OPTIMIZE_KEY:
926
{
927
Item **values;
928
// BETWEEN, IN, NE
929
if (cond_func->key_item()->real_item()->type() == Item::FIELD_ITEM &&
930
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
931
{
932
values= cond_func->arguments()+1;
933
if (cond_func->functype() == Item_func::NE_FUNC &&
934
cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
935
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
936
values--;
937
assert(cond_func->functype() != Item_func::IN_FUNC ||
938
cond_func->argument_count() != 2);
939
add_key_equal_fields(key_fields, *and_level, cond_func,
940
(Item_field*) (cond_func->key_item()->real_item()),
941
0, values,
942
cond_func->argument_count()-1,
943
usable_tables, sargables);
944
}
945
if (cond_func->functype() == Item_func::BETWEEN)
946
{
947
values= cond_func->arguments();
948
for (uint32_t i= 1 ; i < cond_func->argument_count() ; i++)
949
{
950
Item_field *field_item;
951
if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM
952
&&
953
!(cond_func->arguments()[i]->used_tables() & OUTER_REF_TABLE_BIT))
954
{
955
field_item= (Item_field *) (cond_func->arguments()[i]->real_item());
956
add_key_equal_fields(key_fields, *and_level, cond_func,
957
field_item, 0, values, 1, usable_tables,
958
sargables);
959
}
960
}
961
}
962
break;
963
}
964
case Item_func::OPTIMIZE_OP:
965
{
966
bool equal_func=(cond_func->functype() == Item_func::EQ_FUNC ||
967
cond_func->functype() == Item_func::EQUAL_FUNC);
968
969
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
970
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
971
{
972
add_key_equal_fields(key_fields, *and_level, cond_func,
973
(Item_field*) (cond_func->arguments()[0])->real_item(),
974
equal_func,
975
cond_func->arguments()+1, 1, usable_tables,
976
sargables);
977
}
978
if (cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
979
cond_func->functype() != Item_func::LIKE_FUNC &&
980
!(cond_func->arguments()[1]->used_tables() & OUTER_REF_TABLE_BIT))
981
{
982
add_key_equal_fields(key_fields, *and_level, cond_func,
983
(Item_field*) (cond_func->arguments()[1])->real_item(), equal_func,
984
cond_func->arguments(),1,usable_tables,
985
sargables);
986
}
987
break;
988
}
989
case Item_func::OPTIMIZE_NULL:
990
/* column_name IS [NOT] NULL */
991
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
992
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
993
{
994
Item *tmp=new Item_null;
995
if (unlikely(!tmp)) // Should never be true
996
return;
997
add_key_equal_fields(key_fields, *and_level, cond_func,
998
(Item_field*) (cond_func->arguments()[0])->real_item(),
999
cond_func->functype() == Item_func::ISNULL_FUNC,
1000
&tmp, 1, usable_tables, sargables);
1001
}
1002
break;
1003
case Item_func::OPTIMIZE_EQUAL:
1004
Item_equal *item_equal= (Item_equal *) cond;
1005
Item *const_item= item_equal->get_const();
1006
Item_equal_iterator it(*item_equal);
1007
Item_field *item;
1008
if (const_item)
1009
{
1010
/*
1011
For each field field1 from item_equal consider the equality
1012
field1=const_item as a condition allowing an index access of the table
1013
with field1 by the keys value of field1.
1014
*/
1015
while ((item= it++))
1016
{
1017
add_key_field(key_fields, *and_level, cond_func, item->field,
1018
true, &const_item, 1, usable_tables, sargables);
1019
}
1020
}
1021
else
1022
{
1023
/*
1024
Consider all pairs of different fields included into item_equal.
1025
For each of them (field1, field1) consider the equality
1026
field1=field2 as a condition allowing an index access of the table
1027
with field1 by the keys value of field2.
1028
*/
1029
Item_equal_iterator fi(*item_equal);
1030
while ((item= fi++))
1031
{
1032
Field *field= item->field;
1033
while ((item= it++))
1034
{
1035
if (!field->eq(item->field))
1036
{
1037
add_key_field(key_fields, *and_level, cond_func, field,
1038
true, (Item **) &item, 1, usable_tables,
1039
sargables);
1040
}
1041
}
1042
it.rewind();
1043
}
1044
}
1045
break;
1046
}
1047
}
1048
503
1049
504
/**
1050
505
Add all keys with uses 'field' for some keypart.
1058
513
return found;
1059
514
}
1060
515
1061
static void add_key_part(DYNAMIC_ARRAY *keyuse_array,KEY_FIELD *key_field)
1062
{
1063
Field *field=key_field->field;
1064
Table *form= field->table;
1065
KeyUse keyuse;
1066
1067
if (key_field->eq_func && !(key_field->optimize & KEY_OPTIMIZE_EXISTS))
1068
{
1069
for (uint32_t key= 0 ; key < form->sizeKeys() ; key++)
1070
{
1071
if (!(form->keys_in_use_for_query.test(key)))
1072
continue;
1073
1074
uint32_t key_parts= (uint32_t) form->key_info[key].key_parts;
1075
for (uint32_t part=0 ; part < key_parts ; part++)
1076
{
1077
if (field->eq(form->key_info[key].key_part[part].field))
1078
{
1079
keyuse.table= field->table;
1080
keyuse.val = key_field->val;
1081
keyuse.key = key;
1082
keyuse.keypart=part;
1083
keyuse.keypart_map= (key_part_map) 1 << part;
1084
keyuse.used_tables=key_field->val->used_tables();
1085
keyuse.optimize= key_field->optimize & KEY_OPTIMIZE_REF_OR_NULL;
1086
keyuse.null_rejecting= key_field->null_rejecting;
1087
keyuse.cond_guard= key_field->cond_guard;
1088
insert_dynamic(keyuse_array,(unsigned char*) &keyuse);
1089
}
1090
}
1091
}
1092
}
1093
}
1094
1095
516
static int sort_keyuse(KeyUse *a,KeyUse *b)
1096
517
{
1097
518
int res;
1110
531
(b->optimize & KEY_OPTIMIZE_REF_OR_NULL));
1111
532
}
1112
533
1113
/*
1114
Add to KEY_FIELD array all 'ref' access candidates within nested join.
1115
1116
This function populates KEY_FIELD array with entries generated from the
1117
ON condition of the given nested join, and does the same for nested joins
1118
contained within this nested join.
1119
1120
@param[in] nested_join_table Nested join pseudo-table to process
1121
@param[in,out] end End of the key field array
1122
@param[in,out] and_level And-level
1123
@param[in,out] sargables Array of found sargable candidates
1124
1125
1126
@note
1127
We can add accesses to the tables that are direct children of this nested
1128
join (1), and are not inner tables w.r.t their neighbours (2).
1129
1130
Example for #1 (outer brackets pair denotes nested join this function is
1131
invoked for):
1132
@code
1133
... LEFT JOIN (t1 LEFT JOIN (t2 ... ) ) ON cond
1134
@endcode
1135
Example for #2:
1136
@code
1137
... LEFT JOIN (t1 LEFT JOIN t2 ) ON cond
1138
@endcode
1139
In examples 1-2 for condition cond, we can add 'ref' access candidates to
1140
t1 only.
1141
Example #3:
1142
@code
1143
... LEFT JOIN (t1, t2 LEFT JOIN t3 ON inner_cond) ON cond
1144
@endcode
1145
Here we can add 'ref' access candidates for t1 and t2, but not for t3.
1146
*/
1147
static void add_key_fields_for_nj(JOIN *join,
1148
TableList *nested_join_table,
1149
KEY_FIELD **end,
1150
uint32_t *and_level,
1151
SARGABLE_PARAM **sargables)
1152
{
1153
List_iterator<TableList> li(nested_join_table->nested_join->join_list);
1154
List_iterator<TableList> li2(nested_join_table->nested_join->join_list);
1155
bool have_another = false;
1156
table_map tables= 0;
1157
TableList *table;
1158
assert(nested_join_table->nested_join);
1159
1160
while ((table= li++) || (have_another && (li=li2, have_another=false,
1161
(table= li++))))
1162
{
1163
if (table->nested_join)
1164
{
1165
if (!table->on_expr)
1166
{
1167
/* It's a semi-join nest. Walk into it as if it wasn't a nest */
1168
have_another= true;
1169
li2= li;
1170
li= List_iterator<TableList>(table->nested_join->join_list);
1171
}
1172
else
1173
add_key_fields_for_nj(join, table, end, and_level, sargables);
1174
}
1175
else
1176
if (!table->on_expr)
1177
tables |= table->table->map;
1178
}
1179
if (nested_join_table->on_expr)
1180
add_key_fields(join, end, and_level, nested_join_table->on_expr, tables,
1181
sargables);
1182
}
1183
534
1184
535
/**
1185
536
Update keyuse array with all possible keys we can use to fetch rows.
1194
545
for which we can make ref access based the WHERE
1195
546
clause)
1196
547
@param select_lex current SELECT
1197
@param[out] sargables Array of found sargable candidates
548
@param[out] sargables std::vector of found sargable candidates
1198
549
1199
550
@retval
1200
551
0 OK
1209
560
COND_EQUAL *,
1210
561
table_map normal_tables,
1211
562
Select_Lex *select_lex,
1212
SARGABLE_PARAM **sargables)
563
vector<optimizer::SargableParam> &sargables)
1213
564
{
1214
565
uint and_level,i,found_eq_constant;
1215
KEY_FIELD *key_fields, *end, *field;
566
optimizer::KeyField *key_fields, *end, *field;
1216
567
uint32_t sz;
1217
568
uint32_t m= max(select_lex->max_equal_elems,(uint32_t)1);
1218
569
1219
570
/*
1220
We use the same piece of memory to store both KEY_FIELD
1221
and SARGABLE_PARAM structure.
1222
KEY_FIELD values are placed at the beginning this memory
1223
while SARGABLE_PARAM values are put at the end.
1224
All predicates that are used to fill arrays of KEY_FIELD
1225
and SARGABLE_PARAM structures have at most 2 arguments
571
All predicates that are used to fill arrays of KeyField
572
and SargableParam classes have at most 2 arguments
1226
573
except BETWEEN predicates that have 3 arguments and
1227
574
IN predicates.
1228
575
This any predicate if it's not BETWEEN/IN can be used
1229
directly to fill at most 2 array elements, either of KEY_FIELD
1230
or SARGABLE_PARAM type. For a BETWEEN predicate 3 elements
576
directly to fill at most 2 array elements, either of KeyField
577
or SargableParam type. For a BETWEEN predicate 3 elements
1231
578
can be filled as this predicate is considered as
1232
579
saragable with respect to each of its argument.
1233
580
An IN predicate can require at most 1 element as currently
1237
584
can be not more than select_lex->max_equal_elems such
1238
585
substitutions.
1239
586
*/
1240
sz= max(sizeof(KEY_FIELD),sizeof(SARGABLE_PARAM))*
1241
(((session->lex->current_select->cond_count+1)*2 +
587
sz= sizeof(optimizer::KeyField) *
588
(((session->lex->current_select->cond_count+1) +
1242
589
session->lex->current_select->between_count)*m+1);
1243
if (!(key_fields=(KEY_FIELD*) session->alloc(sz)))
590
if (! (key_fields= (optimizer::KeyField*) session->alloc(sz)))
1244
591
return true; /* purecov: inspected */
1245
592
and_level= 0;
1246
593
field= end= key_fields;
1247
*sargables= (SARGABLE_PARAM *) key_fields +
1248
(sz - sizeof((*sargables)[0].field))/sizeof(SARGABLE_PARAM);
1249
/* set a barrier for the array of SARGABLE_PARAM */
1250
(*sargables)[0].field= 0;
1251
594
1252
595
if (my_init_dynamic_array(keyuse,sizeof(KeyUse),20,64))
1253
596
return true;
1786
1129
1787
1130
Implementation overview
1788
1131
1. update_ref_and_keys() accumulates info about null-rejecting
1789
predicates in in KEY_FIELD::null_rejecting
1132
predicates in in KeyField::null_rejecting
1790
1133
1.1 add_key_part saves these to KeyUse.
1791
1134
2. create_ref_for_key copies them to table_reference_st.
1792
1135
3. add_not_null_conds adds "x IS NOT NULL" to join_tab->select_cond of
4249
3592
return 0;
4250
3593
}
4251
3594
4252
int join_read_const_table(JoinTable *tab, Position *pos)
3595
int join_read_const_table(JoinTable *tab, optimizer::Position *pos)
4253
3596
{
4254
3597
int error;
4255
3598
Table *table=tab->table;
4263
3606
{ // Info for DESCRIBE
4264
3607
tab->info="const row not found";
4265
3608
/* Mark for EXPLAIN that the row was not found */
4266
pos->records_read=0.0;
4267
pos->ref_depend_map= 0;
4268
if (!table->maybe_null || error > 0)
3609
pos->setFanout(0.0);
3610
pos->clearRefDependMap();
3611
if (! table->maybe_null || error > 0)
4269
3612
return(error);
4270
3613
}
4271
3614
}
4272
3615
else
4273
3616
{
4274
if (!table->key_read &&
3617
if (! table->key_read &&
4275
3618
table->covering_keys.test(tab->ref.key) &&
4276
!table->no_keyread &&
3619
! table->no_keyread &&
4277
3620
(int) table->reginfo.lock_type <= (int) TL_READ_WITH_SHARED_LOCKS)
4278
3621
{
4279
3622
table->key_read=1;
4290
3633
{
4291
3634
tab->info="unique row not found";
4292
3635
/* Mark for EXPLAIN that the row was not found */
4293
pos->records_read=0.0;
4294
pos->ref_depend_map= 0;
3636
pos->setFanout(0.0);
3637
pos->clearRefDependMap();
4295
3638
if (!table->maybe_null || error > 0)
4296
3639
return(error);
4297
3640
}
5575
4918
uint32_t tablenr= tab - join->join_tab;
5576
4919
ha_rows table_records= table->file->stats.records;
5577
4920
bool group= join->group && order == join->group_list;
5578
Position cur_pos;
4921
optimizer::Position cur_pos;
5579
4922
5580
4923
/*
5581
4924
If not used with LIMIT, only use keys if the whole query can be
5607
4950
keys= usable_keys;
5608
4951
5609
4952
cur_pos= join->getPosFromOptimalPlan(tablenr);
5610
read_time= cur_pos.read_time;
4953
read_time= cur_pos.getCost();
5611
4954
for (uint32_t i= tablenr+1; i < join->tables; i++)
5612
4955
{
5613
4956
cur_pos= join->getPosFromOptimalPlan(i);
5614
fanout*= cur_pos.records_read; // fanout is always >= 1
4957
fanout*= cur_pos.getFanout(); // fanout is always >= 1
5615
4958
}
5616
4959
5617
4960
for (nr=0; nr < table->s->keys ; nr++)
7469
6812
tab->table->file->records());
7470
6813
else
7471
6814
{
7472
Position cur_pos= join->getPosFromOptimalPlan(i);
7473
examined_rows= cur_pos.records_read;
6815
optimizer::Position cur_pos= join->getPosFromOptimalPlan(i);
6816
examined_rows= cur_pos.getFanout();
7474
6817
}
7475
6818
7476
6819
item_list.push_back(new Item_int((int64_t) (uint64_t) examined_rows,
7482
6825
float f= 0.0;
7483
6826
if (examined_rows)
7484
6827
{
7485
Position cur_pos= join->getPosFromOptimalPlan(i);
7486
f= (float) (100.0 * cur_pos.records_read /
6828
optimizer::Position cur_pos= join->getPosFromOptimalPlan(i);
6829
f= (float) (100.0 * cur_pos.getFanout() /
7487
6830
examined_rows);
7488
6831
}
7489
6832
item_list.push_back(new Item_float(f, 2));
Loggerhead is a web-based interface for Breezy
Version: 2.0.1