« back to all changes in this revision
Viewing changes to drizzled/optimizer/range.cc
- browse files at revision 1241.13.7
- compare with another revision
- compare with revision 582
- download diff
- download tarball
- view history from revision 1241.13.7
- Committer: Monty Taylor
- Date: 2009-12-19 19:09:29 UTC
- mfrom: (1245.1.2 staging)
- mto: (1241.12.8 out-of-tree)
- mto: This revision was merged to the branch mainline in revision 1250.
- Revision ID: mordred@inaugust.com-20091219190929-00qw0lmx1p8lpzsz
Merged with trunk.
- files added:
- drizzled/optimizer/explain_plan.cc
- files renamed:
- plugin/memcached_functions/tests/start_mc.sh => plugin/memcached_functions/start_mc.sh.in
- files modified:
- .bzrignore
added
removed
drizzled/optimizer/range.cc
127
127
#include "drizzled/optimizer/range.h"
128
128
#include "drizzled/optimizer/quick_range.h"
129
129
#include "drizzled/optimizer/quick_range_select.h"
130
#include "drizzled/optimizer/quick_group_min_max_select.h"
130
131
#include "drizzled/optimizer/quick_index_merge_select.h"
132
#include "drizzled/optimizer/quick_ror_intersect_select.h"
133
#include "drizzled/optimizer/quick_ror_union_select.h"
134
#include "drizzled/optimizer/table_read_plan.h"
131
135
#include "drizzled/optimizer/sel_arg.h"
132
136
#include "drizzled/optimizer/range_param.h"
133
137
#include "drizzled/records.h"
278
282
/* Note that #records for each key scan is stored in table->quick_rows */
279
283
};
280
284
281
class TABLE_READ_PLAN;
282
class TRP_RANGE;
283
class TRP_ROR_INTERSECT;
284
class TRP_ROR_UNION;
285
class TRP_ROR_INDEX_MERGE;
286
class TRP_GROUP_MIN_MAX;
287
288
285
struct st_ror_scan_info;
289
286
290
287
static SEL_TREE * get_mm_parts(optimizer::RangeParameter *param,
314
311
uint32_t *bufsize,
315
312
COST_VECT *cost);
316
313
317
static TRP_RANGE *get_key_scans_params(optimizer::Parameter *param,
318
SEL_TREE *tree,
319
bool index_read_must_be_used,
320
bool update_tbl_stats,
321
double read_time);
322
323
static
324
TRP_ROR_INTERSECT *get_best_ror_intersect(const optimizer::Parameter *param,
325
SEL_TREE *tree,
326
double read_time,
327
bool *are_all_covering);
328
329
static
330
TRP_ROR_INTERSECT *get_best_covering_ror_intersect(optimizer::Parameter *param,
331
SEL_TREE *tree,
332
double read_time);
333
334
static
335
TABLE_READ_PLAN *get_best_disjunct_quick(optimizer::Parameter *param,
336
SEL_IMERGE *imerge,
337
double read_time);
338
339
static
340
TRP_GROUP_MIN_MAX *get_best_group_min_max(optimizer::Parameter *param, SEL_TREE *tree);
314
static optimizer::TRP_RANGE *get_key_scans_params(optimizer::Parameter *param,
315
SEL_TREE *tree,
316
bool index_read_must_be_used,
317
bool update_tbl_stats,
318
double read_time);
319
320
static
321
optimizer::TRP_ROR_INTERSECT *get_best_ror_intersect(const optimizer::Parameter *param,
322
SEL_TREE *tree,
323
double read_time,
324
bool *are_all_covering);
325
326
static
327
optimizer::TRP_ROR_INTERSECT *get_best_covering_ror_intersect(optimizer::Parameter *param,
328
SEL_TREE *tree,
329
double read_time);
330
331
static
332
optimizer::TABLE_READ_PLAN *get_best_disjunct_quick(optimizer::Parameter *param,
333
SEL_IMERGE *imerge,
334
double read_time);
335
336
static
337
optimizer::TRP_GROUP_MIN_MAX *get_best_group_min_max(optimizer::Parameter *param, SEL_TREE *tree);
341
338
342
339
static void print_sel_tree(optimizer::Parameter *param,
343
340
SEL_TREE *tree,
597
594
*/
598
595
599
596
optimizer::SqlSelect *optimizer::make_select(Table *head,
600
table_map const_tables,
601
table_map read_tables,
602
COND *conds,
603
bool allow_null_cond,
604
int *error)
597
table_map const_tables,
598
table_map read_tables,
599
COND *conds,
600
bool allow_null_cond,
601
int *error)
605
602
{
606
603
optimizer::SqlSelect *select= NULL;
607
604
633
630
}
634
631
635
632
636
optimizer::SqlSelect::SqlSelect() :quick(0),cond(0),free_cond(0)
633
optimizer::SqlSelect::SqlSelect()
634
:
635
quick(NULL),
636
cond(NULL),
637
free_cond(false)
637
638
{
638
639
quick_keys.reset();
639
640
needed_reg.reset();
647
648
quick= 0;
648
649
if (free_cond)
649
650
{
650
free_cond=0;
651
free_cond= 0;
651
652
delete cond;
652
653
cond= 0;
653
654
}
661
662
}
662
663
663
664
664
bool optimizer::SqlSelect::check_quick(Session *session, bool force_quick_range,
665
ha_rows limit)
665
bool optimizer::SqlSelect::check_quick(Session *session,
666
bool force_quick_range,
667
ha_rows limit)
666
668
{
667
669
key_map tmp;
668
670
tmp.set();
669
return test_quick_select(session, tmp, 0, limit,
670
force_quick_range, false) < 0;
671
return (test_quick_select(session,
672
tmp,
673
0,
674
limit,
675
force_quick_range,
676
false) < 0);
671
677
}
672
678
673
679
674
680
bool optimizer::SqlSelect::skip_record()
675
681
{
676
return cond ? cond->val_int() == 0 : 0;
682
return (cond ? cond->val_int() == 0 : 0);
677
683
}
678
684
679
685
684
690
{}
685
691
686
692
687
688
optimizer::QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(Session *session_param,
689
Table *table,
690
bool retrieve_full_rows,
691
MEM_ROOT *parent_alloc)
692
:
693
cpk_quick(NULL),
694
session(session_param),
695
need_to_fetch_row(retrieve_full_rows),
696
scans_inited(false)
697
{
698
index= MAX_KEY;
699
head= table;
700
record= head->record[0];
701
if (! parent_alloc)
702
{
703
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
704
}
705
else
706
{
707
memset(&alloc, 0, sizeof(MEM_ROOT));
708
}
709
last_rowid= (unsigned char*) alloc_root(parent_alloc? parent_alloc : &alloc,
710
head->cursor->ref_length);
711
}
712
713
714
/*
715
Do post-constructor initialization.
716
SYNOPSIS
717
QUICK_ROR_INTERSECT_SELECT::init()
718
719
RETURN
720
0 OK
721
other Error code
722
*/
723
724
int optimizer::QUICK_ROR_INTERSECT_SELECT::init()
725
{
726
/* Check if last_rowid was successfully allocated in ctor */
727
return (! last_rowid);
728
}
729
730
731
/*
732
Initialize this quick select to be a part of a ROR-merged scan.
733
SYNOPSIS
734
QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan()
735
reuse_handler If true, use head->cursor, otherwise create separate
736
Cursor object.
737
RETURN
738
0 OK
739
other error code
740
*/
741
int optimizer::QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan(bool reuse_handler)
742
{
743
List_iterator_fast<optimizer::QuickRangeSelect> quick_it(quick_selects);
744
optimizer::QuickRangeSelect *quick= NULL;
745
746
/* Initialize all merged "children" quick selects */
747
assert(!need_to_fetch_row || reuse_handler);
748
if (! need_to_fetch_row && reuse_handler)
749
{
750
quick= quick_it++;
751
/*
752
There is no use of this->cursor. Use it for the first of merged range
753
selects.
754
*/
755
if (quick->init_ror_merged_scan(true))
756
return 0;
757
quick->cursor->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
758
}
759
while ((quick= quick_it++))
760
{
761
if (quick->init_ror_merged_scan(false))
762
{
763
return 0;
764
}
765
quick->cursor->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
766
/* All merged scans share the same record buffer in intersection. */
767
quick->record= head->record[0];
768
}
769
770
if (need_to_fetch_row && head->cursor->ha_rnd_init(1))
771
{
772
return 0;
773
}
774
return 0;
775
}
776
777
778
/*
779
Initialize quick select for row retrieval.
780
SYNOPSIS
781
reset()
782
RETURN
783
0 OK
784
other Error code
785
*/
786
787
int optimizer::QUICK_ROR_INTERSECT_SELECT::reset()
788
{
789
if (! scans_inited && init_ror_merged_scan(true))
790
{
791
return 0;
792
}
793
scans_inited= true;
794
List_iterator_fast<optimizer::QuickRangeSelect> it(quick_selects);
795
optimizer::QuickRangeSelect *quick= NULL;
796
while ((quick= it++))
797
{
798
quick->reset();
799
}
800
return 0;
801
}
802
803
804
/*
805
Add a merged quick select to this ROR-intersection quick select.
806
807
SYNOPSIS
808
QUICK_ROR_INTERSECT_SELECT::push_quick_back()
809
quick Quick select to be added. The quick select must return
810
rows in rowid order.
811
NOTES
812
This call can only be made before init() is called.
813
814
RETURN
815
false OK
816
true Out of memory.
817
*/
818
819
bool
820
optimizer::QUICK_ROR_INTERSECT_SELECT::push_quick_back(optimizer::QuickRangeSelect *quick)
821
{
822
return quick_selects.push_back(quick);
823
}
824
825
optimizer::QUICK_ROR_INTERSECT_SELECT::~QUICK_ROR_INTERSECT_SELECT()
826
{
827
quick_selects.delete_elements();
828
delete cpk_quick;
829
free_root(&alloc,MYF(0));
830
if (need_to_fetch_row && head->cursor->inited != Cursor::NONE)
831
{
832
head->cursor->ha_rnd_end();
833
}
834
return;
835
}
836
837
838
optimizer::QUICK_ROR_UNION_SELECT::QUICK_ROR_UNION_SELECT(Session *session_param,
839
Table *table)
840
:
841
session(session_param),
842
scans_inited(false)
843
{
844
index= MAX_KEY;
845
head= table;
846
rowid_length= table->cursor->ref_length;
847
record= head->record[0];
848
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
849
session_param->mem_root= &alloc;
850
}
851
852
/*
853
* Function object that is used as the comparison function
854
* for the priority queue in the QUICK_ROR_UNION_SELECT
855
* class.
856
*/
857
class optimizer::compare_functor
858
{
859
optimizer::QUICK_ROR_UNION_SELECT *self;
860
public:
861
compare_functor(optimizer::QUICK_ROR_UNION_SELECT *in_arg)
862
: self(in_arg) { }
863
inline bool operator()(const optimizer::QuickSelectInterface *i, const optimizer::QuickSelectInterface *j) const
864
{
865
int val= self->head->cursor->cmp_ref(i->last_rowid,
866
j->last_rowid);
867
return (val >= 0);
868
}
869
};
870
871
/*
872
Do post-constructor initialization.
873
SYNOPSIS
874
QUICK_ROR_UNION_SELECT::init()
875
876
RETURN
877
0 OK
878
other Error code
879
*/
880
881
int optimizer::QUICK_ROR_UNION_SELECT::init()
882
{
883
queue=
884
new priority_queue<optimizer::QuickSelectInterface *,
885
vector<optimizer::QuickSelectInterface *>,
886
optimizer::compare_functor >(optimizer::compare_functor(this));
887
if (! (cur_rowid= (unsigned char*) alloc_root(&alloc, 2*head->cursor->ref_length)))
888
{
889
return 0;
890
}
891
prev_rowid= cur_rowid + head->cursor->ref_length;
892
return 0;
893
}
894
895
896
/*
897
Initialize quick select for row retrieval.
898
SYNOPSIS
899
reset()
900
901
RETURN
902
0 OK
903
other Error code
904
*/
905
906
int optimizer::QUICK_ROR_UNION_SELECT::reset()
907
{
908
QuickSelectInterface *quick= NULL;
909
int error;
910
have_prev_rowid= false;
911
if (! scans_inited)
912
{
913
List_iterator_fast<QuickSelectInterface> it(quick_selects);
914
while ((quick= it++))
915
{
916
if (quick->init_ror_merged_scan(false))
917
{
918
return 0;
919
}
920
}
921
scans_inited= true;
922
}
923
while (! queue->empty())
924
{
925
queue->pop();
926
}
927
/*
928
Initialize scans for merged quick selects and put all merged quick
929
selects into the queue.
930
*/
931
List_iterator_fast<QuickSelectInterface> it(quick_selects);
932
while ((quick= it++))
933
{
934
if (quick->reset())
935
{
936
return 0;
937
}
938
if ((error= quick->get_next()))
939
{
940
if (error == HA_ERR_END_OF_FILE)
941
{
942
continue;
943
}
944
return(error);
945
}
946
quick->save_last_pos();
947
queue->push(quick);
948
}
949
950
if (head->cursor->ha_rnd_init(1))
951
{
952
return 0;
953
}
954
955
return 0;
956
}
957
958
959
bool
960
optimizer::QUICK_ROR_UNION_SELECT::push_quick_back(QuickSelectInterface *quick_sel_range)
961
{
962
return quick_selects.push_back(quick_sel_range);
963
}
964
965
optimizer::QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT()
966
{
967
while (! queue->empty())
968
{
969
queue->pop();
970
}
971
delete queue;
972
quick_selects.delete_elements();
973
if (head->cursor->inited != Cursor::NONE)
974
{
975
head->cursor->ha_rnd_end();
976
}
977
free_root(&alloc,MYF(0));
978
return;
979
}
980
981
982
693
/*
983
694
Find the best index to retrieve first N records in given order
984
695
1069
780
}
1070
781
1071
782
1072
/*
1073
Table rows retrieval plan. Range optimizer creates QuickSelectInterface-derived
1074
objects from table read plans.
1075
*/
1076
class TABLE_READ_PLAN
1077
{
1078
public:
1079
/*
1080
Plan read cost, with or without cost of full row retrieval, depending
1081
on plan creation parameters.
1082
*/
1083
double read_cost;
1084
ha_rows records; /* estimate of #rows to be examined */
1085
1086
/*
1087
If true, the scan returns rows in rowid order. This is used only for
1088
scans that can be both ROR and non-ROR.
1089
*/
1090
bool is_ror;
1091
1092
/*
1093
Create quick select for this plan.
1094
SYNOPSIS
1095
make_quick()
1096
param Parameter from test_quick_select
1097
retrieve_full_rows If true, created quick select will do full record
1098
retrieval.
1099
parent_alloc Memory pool to use, if any.
1100
1101
NOTES
1102
retrieve_full_rows is ignored by some implementations.
1103
1104
RETURN
1105
created quick select
1106
NULL on any error.
1107
*/
1108
virtual optimizer::QuickSelectInterface *make_quick(optimizer::Parameter *param,
1109
bool retrieve_full_rows,
1110
MEM_ROOT *parent_alloc=NULL) = 0;
1111
1112
/* Table read plans are allocated on MEM_ROOT and are never deleted */
1113
static void *operator new(size_t size, MEM_ROOT *mem_root)
1114
{ return (void*) alloc_root(mem_root, (uint32_t) size); }
1115
static void operator delete(void *, size_t)
1116
{ TRASH(ptr, size); }
1117
static void operator delete(void *, MEM_ROOT *)
1118
{ /* Never called */ }
1119
virtual ~TABLE_READ_PLAN() {} /* Remove gcc warning */
1120
1121
};
1122
1123
class TRP_ROR_INTERSECT;
1124
class TRP_ROR_UNION;
1125
class TRP_INDEX_MERGE;
1126
1127
1128
/*
1129
Plan for a QuickRangeSelect scan.
1130
TRP_RANGE::make_quick ignores retrieve_full_rows parameter because
1131
QuickRangeSelect doesn't distinguish between 'index only' scans and full
1132
record retrieval scans.
1133
*/
1134
1135
class TRP_RANGE : public TABLE_READ_PLAN
1136
{
1137
public:
1138
optimizer::SEL_ARG *key; /* set of intervals to be used in "range" method retrieval */
1139
uint32_t key_idx; /* key number in Parameter::key */
1140
uint32_t mrr_flags;
1141
uint32_t mrr_buf_size;
1142
1143
TRP_RANGE(optimizer::SEL_ARG *key_arg, uint32_t idx_arg, uint32_t mrr_flags_arg)
1144
:
1145
key(key_arg),
1146
key_idx(idx_arg),
1147
mrr_flags(mrr_flags_arg)
1148
{}
1149
virtual ~TRP_RANGE() {} /* Remove gcc warning */
1150
1151
optimizer::QuickSelectInterface *make_quick(optimizer::Parameter *param, bool, MEM_ROOT *parent_alloc)
1152
{
1153
optimizer::QuickRangeSelect *quick= NULL;
1154
if ((quick= optimizer::get_quick_select(param,
1155
key_idx,
1156
key,
1157
mrr_flags,
1158
mrr_buf_size,
1159
parent_alloc)))
1160
{
1161
quick->records= records;
1162
quick->read_time= read_cost;
1163
}
1164
return quick;
1165
}
1166
};
1167
1168
1169
/* Plan for QUICK_ROR_INTERSECT_SELECT scan. */
1170
1171
class TRP_ROR_INTERSECT : public TABLE_READ_PLAN
1172
{
1173
public:
1174
TRP_ROR_INTERSECT() {} /* Remove gcc warning */
1175
virtual ~TRP_ROR_INTERSECT() {} /* Remove gcc warning */
1176
optimizer::QuickSelectInterface *make_quick(optimizer::Parameter *param,
1177
bool retrieve_full_rows,
1178
MEM_ROOT *parent_alloc);
1179
1180
/* Array of pointers to ROR range scans used in this intersection */
1181
struct st_ror_scan_info **first_scan;
1182
struct st_ror_scan_info **last_scan; /* End of the above array */
1183
struct st_ror_scan_info *cpk_scan; /* Clustered PK scan, if there is one */
1184
bool is_covering; /* true if no row retrieval phase is necessary */
1185
double index_scan_costs; /* SUM(cost(index_scan)) */
1186
};
1187
1188
1189
/*
1190
Plan for QUICK_ROR_UNION_SELECT scan.
1191
QUICK_ROR_UNION_SELECT always retrieves full rows, so retrieve_full_rows
1192
is ignored by make_quick.
1193
*/
1194
1195
class TRP_ROR_UNION : public TABLE_READ_PLAN
1196
{
1197
public:
1198
TRP_ROR_UNION() {} /* Remove gcc warning */
1199
virtual ~TRP_ROR_UNION() {} /* Remove gcc warning */
1200
optimizer::QuickSelectInterface *make_quick(optimizer::Parameter *param,
1201
bool retrieve_full_rows,
1202
MEM_ROOT *parent_alloc);
1203
TABLE_READ_PLAN **first_ror; /* array of ptrs to plans for merged scans */
1204
TABLE_READ_PLAN **last_ror; /* end of the above array */
1205
};
1206
1207
1208
/*
1209
Plan for QuickIndexMergeSelect scan.
1210
QUICK_ROR_INTERSECT_SELECT always retrieves full rows, so retrieve_full_rows
1211
is ignored by make_quick.
1212
*/
1213
1214
class TRP_INDEX_MERGE : public TABLE_READ_PLAN
1215
{
1216
public:
1217
TRP_INDEX_MERGE() {} /* Remove gcc warning */
1218
virtual ~TRP_INDEX_MERGE() {} /* Remove gcc warning */
1219
optimizer::QuickSelectInterface *make_quick(optimizer::Parameter *param,
1220
bool retrieve_full_rows,
1221
MEM_ROOT *parent_alloc);
1222
TRP_RANGE **range_scans; /* array of ptrs to plans of merged scans */
1223
TRP_RANGE **range_scans_end; /* end of the array */
1224
};
1225
1226
1227
/*
1228
Plan for a QUICK_GROUP_MIN_MAX_SELECT scan.
1229
*/
1230
1231
class TRP_GROUP_MIN_MAX : public TABLE_READ_PLAN
1232
{
1233
private:
1234
bool have_min, have_max;
1235
KEY_PART_INFO *min_max_arg_part;
1236
uint32_t group_prefix_len;
1237
uint32_t used_key_parts;
1238
uint32_t group_key_parts;
1239
KEY *index_info;
1240
uint32_t index;
1241
uint32_t key_infix_len;
1242
unsigned char key_infix[MAX_KEY_LENGTH];
1243
SEL_TREE *range_tree; /* Represents all range predicates in the query. */
1244
optimizer::SEL_ARG *index_tree; /* The SEL_ARG sub-tree corresponding to index_info. */
1245
uint32_t param_idx; /* Index of used key in param->key. */
1246
/* Number of records selected by the ranges in index_tree. */
1247
public:
1248
ha_rows quick_prefix_records;
1249
public:
1250
TRP_GROUP_MIN_MAX(bool have_min_arg, bool have_max_arg,
1251
KEY_PART_INFO *min_max_arg_part_arg,
1252
uint32_t group_prefix_len_arg, uint32_t used_key_parts_arg,
1253
uint32_t group_key_parts_arg, KEY *index_info_arg,
1254
uint32_t index_arg, uint32_t key_infix_len_arg,
1255
unsigned char *key_infix_arg,
1256
SEL_TREE *tree_arg, optimizer::SEL_ARG *index_tree_arg,
1257
uint32_t param_idx_arg, ha_rows quick_prefix_records_arg)
1258
:
1259
have_min(have_min_arg),
1260
have_max(have_max_arg),
1261
min_max_arg_part(min_max_arg_part_arg),
1262
group_prefix_len(group_prefix_len_arg),
1263
used_key_parts(used_key_parts_arg),
1264
group_key_parts(group_key_parts_arg),
1265
index_info(index_info_arg),
1266
index(index_arg),
1267
key_infix_len(key_infix_len_arg),
1268
range_tree(tree_arg),
1269
index_tree(index_tree_arg),
1270
param_idx(param_idx_arg),
1271
quick_prefix_records(quick_prefix_records_arg)
1272
{
1273
if (key_infix_len)
1274
memcpy(this->key_infix, key_infix_arg, key_infix_len);
1275
}
1276
virtual ~TRP_GROUP_MIN_MAX() {} /* Remove gcc warning */
1277
1278
optimizer::QuickSelectInterface *make_quick(optimizer::Parameter *param,
1279
bool retrieve_full_rows,
1280
MEM_ROOT *parent_alloc);
1281
};
1282
1283
783
1284
784
/*
1285
785
Fill param->needed_fields with bitmap of fields used in the query.
1391
891
*/
1392
892
1393
893
int optimizer::SqlSelect::test_quick_select(Session *session,
1394
key_map keys_to_use,
1395
table_map prev_tables,
1396
ha_rows limit,
1397
bool force_quick_range,
1398
bool ordered_output)
894
key_map keys_to_use,
895
table_map prev_tables,
896
ha_rows limit,
897
bool force_quick_range,
898
bool ordered_output)
1399
899
{
1400
900
uint32_t idx;
1401
901
double scan_time;
1501
1001
read_time= key_read_time;
1502
1002
}
1503
1003
1504
TABLE_READ_PLAN *best_trp= NULL;
1505
TRP_GROUP_MIN_MAX *group_trp;
1004
optimizer::TABLE_READ_PLAN *best_trp= NULL;
1005
optimizer::TRP_GROUP_MIN_MAX *group_trp= NULL;
1506
1006
double best_read_time= read_time;
1507
1007
1508
1008
if (cond)
1525
1025
}
1526
1026
1527
1027
/*
1528
Try to construct a QUICK_GROUP_MIN_MAX_SELECT.
1028
Try to construct a QuickGroupMinMaxSelect.
1529
1029
Notice that it can be constructed no matter if there is a range tree.
1530
1030
*/
1531
1031
group_trp= get_best_group_min_max(¶m, tree);
1548
1048
*/
1549
1049
if (tree->merges.is_empty())
1550
1050
{
1551
TRP_RANGE *range_trp;
1552
TRP_ROR_INTERSECT *rori_trp;
1051
optimizer::TRP_RANGE *range_trp= NULL;
1052
optimizer::TRP_ROR_INTERSECT *rori_trp= NULL;
1553
1053
bool can_build_covering= false;
1554
1054
1555
1055
/* Get best 'range' plan and prepare data for making other plans */
1591
1091
{
1592
1092
/* Try creating index_merge/ROR-union scan. */
1593
1093
SEL_IMERGE *imerge;
1594
TABLE_READ_PLAN *best_conj_trp= NULL, *new_conj_trp;
1094
optimizer::TABLE_READ_PLAN *best_conj_trp= NULL;
1095
optimizer::TABLE_READ_PLAN *new_conj_trp= NULL;
1595
1096
List_iterator_fast<SEL_IMERGE> it(tree->merges);
1596
1097
while ((imerge= it++))
1597
1098
{
1700
1201
*/
1701
1202
1702
1203
static
1703
TABLE_READ_PLAN *get_best_disjunct_quick(optimizer::Parameter *param,
1704
SEL_IMERGE *imerge,
1705
double read_time)
1204
optimizer::TABLE_READ_PLAN *get_best_disjunct_quick(optimizer::Parameter *param,
1205
SEL_IMERGE *imerge,
1206
double read_time)
1706
1207
{
1707
1208
SEL_TREE **ptree;
1708
TRP_INDEX_MERGE *imerge_trp= NULL;
1209
optimizer::TRP_INDEX_MERGE *imerge_trp= NULL;
1709
1210
uint32_t n_child_scans= imerge->trees_next - imerge->trees;
1710
TRP_RANGE **range_scans;
1711
TRP_RANGE **cur_child;
1712
TRP_RANGE **cpk_scan= NULL;
1211
optimizer::TRP_RANGE **range_scans= NULL;
1212
optimizer::TRP_RANGE **cur_child= NULL;
1213
optimizer::TRP_RANGE **cpk_scan= NULL;
1713
1214
bool imerge_too_expensive= false;
1714
1215
double imerge_cost= 0.0;
1715
1216
ha_rows cpk_scan_records= 0;
1718
1219
bool all_scans_ror_able= true;
1719
1220
bool all_scans_rors= true;
1720
1221
uint32_t unique_calc_buff_size;
1721
TABLE_READ_PLAN **roru_read_plans;
1722
TABLE_READ_PLAN **cur_roru_plan;
1222
optimizer::TABLE_READ_PLAN **roru_read_plans= NULL;
1223
optimizer::TABLE_READ_PLAN **cur_roru_plan= NULL;
1723
1224
double roru_index_costs;
1724
1225
ha_rows roru_total_records;
1725
1226
double roru_intersect_part= 1.0;
1726
1227
1727
if (!(range_scans= (TRP_RANGE**)alloc_root(param->mem_root,
1728
sizeof(TRP_RANGE*)*
1729
n_child_scans)))
1228
if (!(range_scans= (optimizer::TRP_RANGE**)alloc_root(param->mem_root,
1229
sizeof(optimizer::TRP_RANGE*)*
1230
n_child_scans)))
1730
1231
return NULL;
1731
1232
/*
1732
1233
Collect best 'range' scan for each of disjuncts, and, while doing so,
1776
1277
}
1777
1278
if (all_scans_rors)
1778
1279
{
1779
roru_read_plans= (TABLE_READ_PLAN**)range_scans;
1280
roru_read_plans= (optimizer::TABLE_READ_PLAN**)range_scans;
1780
1281
goto skip_to_ror_scan;
1781
1282
}
1782
1283
if (cpk_scan)
1819
1320
param->session->variables.sortbuff_size);
1820
1321
if (imerge_cost < read_time)
1821
1322
{
1822
if ((imerge_trp= new (param->mem_root)TRP_INDEX_MERGE))
1323
if ((imerge_trp= new (param->mem_root) optimizer::TRP_INDEX_MERGE))
1823
1324
{
1824
1325
imerge_trp->read_cost= imerge_cost;
1825
1326
imerge_trp->records= non_cpk_scan_records + cpk_scan_records;
1838
1339
/* Ok, it is possible to build a ROR-union, try it. */
1839
1340
bool dummy;
1840
1341
if (!(roru_read_plans=
1841
(TABLE_READ_PLAN**)alloc_root(param->mem_root,
1842
sizeof(TABLE_READ_PLAN*)*
1843
n_child_scans)))
1342
(optimizer::TABLE_READ_PLAN**)alloc_root(param->mem_root,
1343
sizeof(optimizer::TABLE_READ_PLAN*)*
1344
n_child_scans)))
1844
1345
return(imerge_trp);
1845
1346
skip_to_ror_scan:
1846
1347
roru_index_costs= 0.0;
1870
1371
else
1871
1372
cost= read_time;
1872
1373
1873
TABLE_READ_PLAN *prev_plan= *cur_child;
1374
optimizer::TABLE_READ_PLAN *prev_plan= *cur_child;
1874
1375
if (!(*cur_roru_plan= get_best_ror_intersect(param, *ptree, cost,
1875
1376
&dummy)))
1876
1377
{
1882
1383
}
1883
1384
else
1884
1385
roru_index_costs +=
1885
((TRP_ROR_INTERSECT*)(*cur_roru_plan))->index_scan_costs;
1386
((optimizer::TRP_ROR_INTERSECT*)(*cur_roru_plan))->index_scan_costs;
1886
1387
roru_total_records += (*cur_roru_plan)->records;
1887
1388
roru_intersect_part *= (*cur_roru_plan)->records /
1888
1389
param->table->cursor->stats.records;
1917
1418
sweep_cost.total_cost();
1918
1419
}
1919
1420
1920
TRP_ROR_UNION* roru;
1421
optimizer::TRP_ROR_UNION *roru= NULL;
1921
1422
if (roru_total_cost < read_time)
1922
1423
{
1923
if ((roru= new (param->mem_root) TRP_ROR_UNION))
1424
if ((roru= new (param->mem_root) optimizer::TRP_ROR_UNION))
1924
1425
{
1925
1426
roru->first_ror= roru_read_plans;
1926
1427
roru->last_ror= roru_read_plans + n_child_scans;
1927
1428
roru->read_cost= roru_total_cost;
1928
1429
roru->records= roru_total_records;
1929
return(roru);
1430
return roru;
1930
1431
}
1931
1432
}
1932
1433
return(imerge_trp);
2450
1951
*/
2451
1952
2452
1953
static
2453
TRP_ROR_INTERSECT *get_best_ror_intersect(const optimizer::Parameter *param,
2454
SEL_TREE *tree,
2455
double read_time,
2456
bool *are_all_covering)
1954
optimizer::TRP_ROR_INTERSECT *get_best_ror_intersect(const optimizer::Parameter *param,
1955
SEL_TREE *tree,
1956
double read_time,
1957
bool *are_all_covering)
2457
1958
{
2458
1959
uint32_t idx;
2459
1960
double min_cost= DBL_MAX;
2576
2077
}
2577
2078
2578
2079
/* Ok, return ROR-intersect plan if we have found one */
2579
TRP_ROR_INTERSECT *trp= NULL;
2080
optimizer::TRP_ROR_INTERSECT *trp= NULL;
2580
2081
if (min_cost < read_time && (cpk_scan_used || best_num > 1))
2581
2082
{
2582
if (!(trp= new (param->mem_root) TRP_ROR_INTERSECT))
2583
return(trp);
2584
if (!(trp->first_scan=
2083
if (! (trp= new (param->mem_root) optimizer::TRP_ROR_INTERSECT))
2084
return trp;
2085
2086
if (! (trp->first_scan=
2585
2087
(ROR_SCAN_INFO**)alloc_root(param->mem_root,
2586
2088
sizeof(ROR_SCAN_INFO*)*best_num)))
2587
2089
return NULL;
2636
2138
*/
2637
2139
2638
2140
static
2639
TRP_ROR_INTERSECT *get_best_covering_ror_intersect(optimizer::Parameter *param,
2640
SEL_TREE *tree,
2641
double read_time)
2141
optimizer::TRP_ROR_INTERSECT *get_best_covering_ror_intersect(optimizer::Parameter *param,
2142
SEL_TREE *tree,
2143
double read_time)
2642
2144
{
2643
2145
ROR_SCAN_INFO **ror_scan_mark;
2644
2146
ROR_SCAN_INFO **ror_scans_end= tree->ror_scans_end;
2728
2230
if (total_cost > read_time)
2729
2231
return NULL;
2730
2232
2731
TRP_ROR_INTERSECT *trp;
2732
if (!(trp= new (param->mem_root) TRP_ROR_INTERSECT))
2733
return(trp);
2233
optimizer::TRP_ROR_INTERSECT *trp= NULL;
2234
if (! (trp= new (param->mem_root) optimizer::TRP_ROR_INTERSECT))
2235
{
2236
return trp;
2237
}
2238
2734
2239
uint32_t best_num= (ror_scan_mark - tree->ror_scans);
2735
2240
if (!(trp->first_scan= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
2736
2241
sizeof(ROR_SCAN_INFO*)*
2774
2279
NULL if no plan found or error occurred
2775
2280
*/
2776
2281
2777
static TRP_RANGE *get_key_scans_params(optimizer::Parameter *param,
2778
SEL_TREE *tree,
2779
bool index_read_must_be_used,
2780
bool update_tbl_stats,
2781
double read_time)
2282
static optimizer::TRP_RANGE *get_key_scans_params(optimizer::Parameter *param,
2283
SEL_TREE *tree,
2284
bool index_read_must_be_used,
2285
bool update_tbl_stats,
2286
double read_time)
2782
2287
{
2783
2288
uint32_t idx;
2784
optimizer::SEL_ARG **key,**end, **key_to_read= NULL;
2289
optimizer::SEL_ARG **key= NULL;
2290
optimizer::SEL_ARG **end= NULL;
2291
optimizer::SEL_ARG **key_to_read= NULL;
2785
2292
ha_rows best_records= 0;
2786
uint32_t best_mrr_flags= 0, best_buf_size= 0;
2787
TRP_RANGE* read_plan= NULL;
2293
uint32_t best_mrr_flags= 0;
2294
uint32_t best_buf_size= 0;
2295
optimizer::TRP_RANGE *read_plan= NULL;
2788
2296
/*
2789
2297
Note that there may be trees that have type SEL_TREE::KEY but contain no
2790
2298
key reads at all, e.g. tree for expression "key1 is not null" where key1
2833
2341
if (key_to_read)
2834
2342
{
2835
2343
idx= key_to_read - tree->keys;
2836
if ((read_plan= new (param->mem_root) TRP_RANGE(*key_to_read, idx,
2837
best_mrr_flags)))
2344
if ((read_plan= new (param->mem_root) optimizer::TRP_RANGE(*key_to_read, idx,
2345
best_mrr_flags)))
2838
2346
{
2839
2347
read_plan->records= best_records;
2840
2348
read_plan->is_ror= tree->ror_scans_map.test(idx);
2847
2355
}
2848
2356
2849
2357
2850
optimizer::QuickSelectInterface *TRP_INDEX_MERGE::make_quick(optimizer::Parameter *param, bool, MEM_ROOT *)
2358
optimizer::QuickSelectInterface *optimizer::TRP_INDEX_MERGE::make_quick(optimizer::Parameter *param, bool, MEM_ROOT *)
2851
2359
{
2852
2360
optimizer::QuickIndexMergeSelect *quick_imerge;
2853
2361
optimizer::QuickRangeSelect *quick= NULL;
2859
2367
2860
2368
quick_imerge->records= records;
2861
2369
quick_imerge->read_time= read_cost;
2862
for (TRP_RANGE **range_scan= range_scans; range_scan != range_scans_end;
2370
for (optimizer::TRP_RANGE **range_scan= range_scans;
2371
range_scan != range_scans_end;
2863
2372
range_scan++)
2864
2373
{
2865
if (!(quick= (optimizer::QuickRangeSelect*)
2866
((*range_scan)->make_quick(param, false, &quick_imerge->alloc)))||
2374
if (! (quick= (optimizer::QuickRangeSelect*)
2375
((*range_scan)->make_quick(param, false, &quick_imerge->alloc))) ||
2867
2376
quick_imerge->push_quick_back(quick))
2868
2377
{
2869
2378
delete quick;
2874
2383
return quick_imerge;
2875
2384
}
2876
2385
2877
optimizer::QuickSelectInterface *TRP_ROR_INTERSECT::make_quick(optimizer::Parameter *param,
2878
bool retrieve_full_rows,
2879
MEM_ROOT *parent_alloc)
2386
optimizer::QuickSelectInterface *optimizer::TRP_ROR_INTERSECT::make_quick(optimizer::Parameter *param,
2387
bool retrieve_full_rows,
2388
MEM_ROOT *parent_alloc)
2880
2389
{
2881
optimizer::QUICK_ROR_INTERSECT_SELECT *quick_intersect= NULL;
2390
optimizer::QuickRorIntersectSelect *quick_intersect= NULL;
2882
2391
optimizer::QuickRangeSelect *quick= NULL;
2883
2392
MEM_ROOT *alloc= NULL;
2884
2393
2885
2394
if ((quick_intersect=
2886
new optimizer::QUICK_ROR_INTERSECT_SELECT(param->session,
2887
param->table,
2888
(retrieve_full_rows? (! is_covering) : false),
2889
parent_alloc)))
2395
new optimizer::QuickRorIntersectSelect(param->session,
2396
param->table,
2397
(retrieve_full_rows? (! is_covering) : false),
2398
parent_alloc)))
2890
2399
{
2891
2400
print_ror_scans_arr(param->table,
2892
2401
"creating ROR-intersect",
2929
2438
}
2930
2439
2931
2440
2932
optimizer::QuickSelectInterface *TRP_ROR_UNION::make_quick(optimizer::Parameter *param, bool, MEM_ROOT *)
2441
optimizer::QuickSelectInterface *optimizer::TRP_ROR_UNION::make_quick(optimizer::Parameter *param, bool, MEM_ROOT *)
2933
2442
{
2934
optimizer::QUICK_ROR_UNION_SELECT *quick_roru;
2935
TABLE_READ_PLAN **scan;
2936
optimizer::QuickSelectInterface *quick;
2443
optimizer::QuickRorUnionSelect *quick_roru= NULL;
2444
optimizer::TABLE_READ_PLAN **scan= NULL;
2445
optimizer::QuickSelectInterface *quick= NULL;
2937
2446
/*
2938
2447
It is impossible to construct a ROR-union that will not retrieve full
2939
2448
rows, ignore retrieve_full_rows parameter.
2940
2449
*/
2941
if ((quick_roru= new optimizer::QUICK_ROR_UNION_SELECT(param->session, param->table)))
2450
if ((quick_roru= new optimizer::QuickRorUnionSelect(param->session, param->table)))
2942
2451
{
2943
2452
for (scan= first_ror; scan != last_ror; scan++)
2944
2453
{
2951
2460
quick_roru->records= records;
2952
2461
quick_roru->read_time= read_cost;
2953
2462
}
2954
return(quick_roru);
2463
return quick_roru;
2955
2464
}
2956
2465
2957
2466
2971
2480
# Pointer to tree built tree
2972
2481
0 on error
2973
2482
*/
2974
2975
2483
static SEL_TREE *get_ne_mm_tree(optimizer::RangeParameter *param,
2976
2484
Item_func *cond_func,
2977
2485
Field *field,
3010
2518
RETURN
3011
2519
Pointer to the tree built tree
3012
2520
*/
3013
3014
2521
static SEL_TREE *get_func_mm_tree(optimizer::RangeParameter *param,
3015
2522
Item_func *cond_func,
3016
Field *field, Item *value,
3017
Item_result cmp_type, bool inv)
2523
Field *field,
2524
Item *value,
2525
Item_result cmp_type,
2526
bool inv)
3018
2527
{
3019
SEL_TREE *tree= 0;
2528
SEL_TREE *tree= NULL;
3020
2529
3021
switch (cond_func->functype()) {
2530
switch (cond_func->functype())
2531
{
3022
2532
3023
2533
case Item_func::NE_FUNC:
3024
2534
tree= get_ne_mm_tree(param, cond_func, field, value, value, cmp_type);
3026
2536
3027
2537
case Item_func::BETWEEN:
3028
2538
{
3029
if (!value)
2539
if (! value)
3030
2540
{
3031
2541
if (inv)
3032
2542
{
3033
tree= get_ne_mm_tree(param, cond_func, field, cond_func->arguments()[1],
3034
cond_func->arguments()[2], cmp_type);
2543
tree= get_ne_mm_tree(param,
2544
cond_func,
2545
field,
2546
cond_func->arguments()[1],
2547
cond_func->arguments()[2],
2548
cmp_type);
3035
2549
}
3036
2550
else
3037
2551
{
3038
tree= get_mm_parts(param, cond_func, field, Item_func::GE_FUNC,
3039
cond_func->arguments()[1],cmp_type);
2552
tree= get_mm_parts(param,
2553
cond_func,
2554
field,
2555
Item_func::GE_FUNC,
2556
cond_func->arguments()[1],
2557
cmp_type);
3040
2558
if (tree)
3041
2559
{
3042
tree= tree_and(param, tree, get_mm_parts(param, cond_func, field,
3043
Item_func::LE_FUNC,
3044
cond_func->arguments()[2],
3045
cmp_type));
2560
tree= tree_and(param,
2561
tree,
2562
get_mm_parts(param, cond_func, field,
2563
Item_func::LE_FUNC,
2564
cond_func->arguments()[2],
2565
cmp_type));
3046
2566
}
3047
2567
}
3048
2568
}
3049
2569
else
3050
tree= get_mm_parts(param, cond_func, field,
2570
tree= get_mm_parts(param,
2571
cond_func,
2572
field,
3051
2573
(inv ?
3052
2574
(value == (Item*)1 ? Item_func::GT_FUNC :
3053
2575
Item_func::LT_FUNC):
3054
2576
(value == (Item*)1 ? Item_func::LE_FUNC :
3055
2577
Item_func::GE_FUNC)),
3056
cond_func->arguments()[0], cmp_type);
2578
cond_func->arguments()[0],
2579
cmp_type);
3057
2580
break;
3058
2581
}
3059
2582
case Item_func::IN_FUNC:
3060
2583
{
3061
Item_func_in *func=(Item_func_in*) cond_func;
2584
Item_func_in *func= (Item_func_in*) cond_func;
3062
2585
3063
2586
/*
3064
2587
Array for IN() is constructed when all values have the same result
3065
2588
type. Tree won't be built for values with different result types,
3066
2589
so we check it here to avoid unnecessary work.
3067
2590
*/
3068
if (!func->arg_types_compatible)
2591
if (! func->arg_types_compatible)
3069
2592
break;
3070
2593
3071
2594
if (inv)
3113
2636
Item *value_item= func->array->create_item();
3114
2637
param->session->mem_root= tmp_root;
3115
2638
3116
if (func->array->count > NOT_IN_IGNORE_THRESHOLD || !value_item)
2639
if (func->array->count > NOT_IN_IGNORE_THRESHOLD || ! value_item)
3117
2640
break;
3118
2641
3119
2642
/* Get a SEL_TREE for "(-inf|NULL) < X < c_0" interval. */
3121
2644
do
3122
2645
{
3123
2646
func->array->value_to_item(i, value_item);
3124
tree= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
3125
value_item, cmp_type);
3126
if (!tree)
2647
tree= get_mm_parts(param,
2648
cond_func,
2649
field, Item_func::LT_FUNC,
2650
value_item,
2651
cmp_type);
2652
if (! tree)
3127
2653
break;
3128
2654
i++;
3129
2655
} while (i < func->array->count && tree->type == SEL_TREE::IMPOSSIBLE);
5480
5006
}
5481
5007
5482
5008
5483
bool optimizer::QUICK_ROR_INTERSECT_SELECT::is_keys_used(const MyBitmap *fields)
5484
{
5485
optimizer::QuickRangeSelect *quick;
5486
List_iterator_fast<optimizer::QuickRangeSelect> it(quick_selects);
5487
while ((quick= it++))
5488
{
5489
if (is_key_used(head, quick->index, fields))
5490
return 1;
5491
}
5492
return 0;
5493
}
5494
5495
bool optimizer::QUICK_ROR_UNION_SELECT::is_keys_used(const MyBitmap *fields)
5496
{
5497
optimizer::QuickSelectInterface *quick;
5498
List_iterator_fast<optimizer::QuickSelectInterface> it(quick_selects);
5499
while ((quick= it++))
5500
{
5501
if (quick->is_keys_used(fields))
5502
return 1;
5503
}
5504
return 0;
5505
}
5506
5507
5508
5009
/*
5509
5010
Create quick select from ref/ref_or_null scan.
5510
5011
5625
5126
5626
5127
5627
5128
/*
5628
Retrieve next record.
5629
SYNOPSIS
5630
QUICK_ROR_INTERSECT_SELECT::get_next()
5631
5632
NOTES
5633
Invariant on enter/exit: all intersected selects have retrieved all index
5634
records with rowid <= some_rowid_val and no intersected select has
5635
retrieved any index records with rowid > some_rowid_val.
5636
We start fresh and loop until we have retrieved the same rowid in each of
5637
the key scans or we got an error.
5638
5639
If a Clustered PK scan is present, it is used only to check if row
5640
satisfies its condition (and never used for row retrieval).
5641
5642
RETURN
5643
0 - Ok
5644
other - Error code if any error occurred.
5645
*/
5646
5647
int optimizer::QUICK_ROR_INTERSECT_SELECT::get_next()
5648
{
5649
List_iterator_fast<optimizer::QuickRangeSelect> quick_it(quick_selects);
5650
optimizer::QuickRangeSelect* quick;
5651
int error, cmp;
5652
uint32_t last_rowid_count=0;
5653
5654
do
5655
{
5656
/* Get a rowid for first quick and save it as a 'candidate' */
5657
quick= quick_it++;
5658
error= quick->get_next();
5659
if (cpk_quick)
5660
{
5661
while (!error && !cpk_quick->row_in_ranges())
5662
error= quick->get_next();
5663
}
5664
if (error)
5665
return(error);
5666
5667
quick->cursor->position(quick->record);
5668
memcpy(last_rowid, quick->cursor->ref, head->cursor->ref_length);
5669
last_rowid_count= 1;
5670
5671
while (last_rowid_count < quick_selects.elements)
5672
{
5673
if (!(quick= quick_it++))
5674
{
5675
quick_it.rewind();
5676
quick= quick_it++;
5677
}
5678
5679
do
5680
{
5681
if ((error= quick->get_next()))
5682
return(error);
5683
quick->cursor->position(quick->record);
5684
cmp= head->cursor->cmp_ref(quick->cursor->ref, last_rowid);
5685
} while (cmp < 0);
5686
5687
/* Ok, current select 'caught up' and returned ref >= cur_ref */
5688
if (cmp > 0)
5689
{
5690
/* Found a row with ref > cur_ref. Make it a new 'candidate' */
5691
if (cpk_quick)
5692
{
5693
while (!cpk_quick->row_in_ranges())
5694
{
5695
if ((error= quick->get_next()))
5696
return(error);
5697
}
5698
}
5699
memcpy(last_rowid, quick->cursor->ref, head->cursor->ref_length);
5700
last_rowid_count= 1;
5701
}
5702
else
5703
{
5704
/* current 'candidate' row confirmed by this select */
5705
last_rowid_count++;
5706
}
5707
}
5708
5709
/* We get here if we got the same row ref in all scans. */
5710
if (need_to_fetch_row)
5711
error= head->cursor->rnd_pos(head->record[0], last_rowid);
5712
} while (error == HA_ERR_RECORD_DELETED);
5713
return(error);
5714
}
5715
5716
5717
/*
5718
Retrieve next record.
5719
SYNOPSIS
5720
QUICK_ROR_UNION_SELECT::get_next()
5721
5722
NOTES
5723
Enter/exit invariant:
5724
For each quick select in the queue a {key,rowid} tuple has been
5725
retrieved but the corresponding row hasn't been passed to output.
5726
5727
RETURN
5728
0 - Ok
5729
other - Error code if any error occurred.
5730
*/
5731
5732
int optimizer::QUICK_ROR_UNION_SELECT::get_next()
5733
{
5734
int error, dup_row;
5735
optimizer::QuickSelectInterface *quick;
5736
unsigned char *tmp;
5737
5738
do
5739
{
5740
do
5741
{
5742
if (queue->empty())
5743
return(HA_ERR_END_OF_FILE);
5744
/* Ok, we have a queue with >= 1 scans */
5745
5746
quick= queue->top();
5747
memcpy(cur_rowid, quick->last_rowid, rowid_length);
5748
5749
/* put into queue rowid from the same stream as top element */
5750
if ((error= quick->get_next()))
5751
{
5752
if (error != HA_ERR_END_OF_FILE)
5753
return(error);
5754
queue->pop();
5755
}
5756
else
5757
{
5758
quick->save_last_pos();
5759
queue->pop();
5760
queue->push(quick);
5761
}
5762
5763
if (!have_prev_rowid)
5764
{
5765
/* No rows have been returned yet */
5766
dup_row= false;
5767
have_prev_rowid= true;
5768
}
5769
else
5770
dup_row= !head->cursor->cmp_ref(cur_rowid, prev_rowid);
5771
} while (dup_row);
5772
5773
tmp= cur_rowid;
5774
cur_rowid= prev_rowid;
5775
prev_rowid= tmp;
5776
5777
error= head->cursor->rnd_pos(quick->record, prev_rowid);
5778
} while (error == HA_ERR_RECORD_DELETED);
5779
return(error);
5780
}
5781
5782
5783
/*
5784
5129
Range sequence interface implementation for array<QuickRange>: initialize
5785
5130
5786
5131
SYNOPSIS
5848
5193
}
5849
5194
5850
5195
5851
void optimizer::QUICK_ROR_INTERSECT_SELECT::add_info_string(String *str)
5852
{
5853
bool first= true;
5854
optimizer::QuickRangeSelect *quick;
5855
List_iterator_fast<optimizer::QuickRangeSelect> it(quick_selects);
5856
str->append(STRING_WITH_LEN("intersect("));
5857
while ((quick= it++))
5858
{
5859
KEY *key_info= head->key_info + quick->index;
5860
if (! first)
5861
str->append(',');
5862
else
5863
first= false;
5864
str->append(key_info->name);
5865
}
5866
if (cpk_quick)
5867
{
5868
KEY *key_info= head->key_info + cpk_quick->index;
5869
str->append(',');
5870
str->append(key_info->name);
5871
}
5872
str->append(')');
5873
}
5874
5875
5876
void optimizer::QUICK_ROR_UNION_SELECT::add_info_string(String *str)
5877
{
5878
bool first= true;
5879
optimizer::QuickSelectInterface *quick;
5880
List_iterator_fast<optimizer::QuickSelectInterface> it(quick_selects);
5881
str->append(STRING_WITH_LEN("union("));
5882
while ((quick= it++))
5883
{
5884
if (! first)
5885
str->append(',');
5886
else
5887
first= false;
5888
quick->add_info_string(str);
5889
}
5890
str->append(')');
5891
}
5892
5893
5894
void optimizer::QUICK_ROR_INTERSECT_SELECT::add_keys_and_lengths(String *key_names,
5895
String *used_lengths)
5896
{
5897
char buf[64];
5898
uint32_t length;
5899
bool first= true;
5900
optimizer::QuickRangeSelect *quick;
5901
List_iterator_fast<optimizer::QuickRangeSelect> it(quick_selects);
5902
while ((quick= it++))
5903
{
5904
KEY *key_info= head->key_info + quick->index;
5905
if (first)
5906
first= false;
5907
else
5908
{
5909
key_names->append(',');
5910
used_lengths->append(',');
5911
}
5912
key_names->append(key_info->name);
5913
length= int64_t2str(quick->max_used_key_length, buf, 10) - buf;
5914
used_lengths->append(buf, length);
5915
}
5916
5917
if (cpk_quick)
5918
{
5919
KEY *key_info= head->key_info + cpk_quick->index;
5920
key_names->append(',');
5921
key_names->append(key_info->name);
5922
length= int64_t2str(cpk_quick->max_used_key_length, buf, 10) - buf;
5923
used_lengths->append(',');
5924
used_lengths->append(buf, length);
5925
}
5926
}
5927
5928
5929
void optimizer::QUICK_ROR_UNION_SELECT::add_keys_and_lengths(String *key_names,
5930
String *used_lengths)
5931
{
5932
bool first= true;
5933
optimizer::QuickSelectInterface *quick;
5934
List_iterator_fast<optimizer::QuickSelectInterface> it(quick_selects);
5935
while ((quick= it++))
5936
{
5937
if (first)
5938
first= false;
5939
else
5940
{
5941
used_lengths->append(',');
5942
key_names->append(',');
5943
}
5944
quick->add_keys_and_lengths(key_names, used_lengths);
5945
}
5946
}
5947
5948
5949
/*******************************************************************************
5950
* Implementation of QUICK_GROUP_MIN_MAX_SELECT
5951
*******************************************************************************/
5952
5953
5196
static inline uint32_t get_field_keypart(KEY *index, Field *field);
5954
5197
5955
5198
static inline optimizer::SEL_ARG * get_index_range_tree(uint32_t index,
5993
5236
sel_tree Range tree generated by get_mm_tree
5994
5237
5995
5238
DESCRIPTION
5996
Test whether a query can be computed via a QUICK_GROUP_MIN_MAX_SELECT.
5997
Queries computable via a QUICK_GROUP_MIN_MAX_SELECT must satisfy the
5239
Test whether a query can be computed via a QuickGroupMinMaxSelect.
5240
Queries computable via a QuickGroupMinMaxSelect must satisfy the
5998
5241
following conditions:
5999
5242
A) Table T has at least one compound index I of the form:
6000
5243
I = <A_1, ...,A_k, [B_1,..., B_m], C, [D_1,...,D_n]>
6078
5321
NOTES
6079
5322
If the current query satisfies the conditions above, and if
6080
5323
(mem_root! = NULL), then the function constructs and returns a new TRP
6081
object, that is later used to construct a new QUICK_GROUP_MIN_MAX_SELECT.
5324
object, that is later used to construct a new QuickGroupMinMaxSelect.
6082
5325
If (mem_root == NULL), then the function only tests whether the current
6083
5326
query satisfies the conditions above, and, if so, sets
6084
5327
is_applicable = true.
6110
5353
If mem_root == NULL
6111
5354
- NULL
6112
5355
*/
6113
static TRP_GROUP_MIN_MAX *
5356
static optimizer::TRP_GROUP_MIN_MAX *
6114
5357
get_best_group_min_max(optimizer::Parameter *param, SEL_TREE *tree)
6115
5358
{
6116
5359
Session *session= param->session;
6127
5370
uint32_t used_key_parts= 0; /* Number of index key parts used for access. */
6128
5371
unsigned char key_infix[MAX_KEY_LENGTH]; /* Constants from equality predicates.*/
6129
5372
uint32_t key_infix_len= 0; /* Length of key_infix. */
6130
TRP_GROUP_MIN_MAX *read_plan= NULL; /* The eventually constructed TRP. */
5373
optimizer::TRP_GROUP_MIN_MAX *read_plan= NULL; /* The eventually constructed TRP. */
6131
5374
uint32_t key_part_nr;
6132
5375
order_st *tmp_group= NULL;
6133
5376
Item *item= NULL;
6526
5769
6527
5770
/* The query passes all tests, so construct a new TRP object. */
6528
5771
read_plan=
6529
new(param->mem_root) TRP_GROUP_MIN_MAX(have_min,
6530
have_max,
6531
min_max_arg_part,
6532
group_prefix_len,
6533
used_key_parts,
6534
group_key_parts,
6535
index_info,
6536
index,
6537
key_infix_len,
6538
(key_infix_len > 0) ? key_infix : NULL,
6539
tree,
6540
best_index_tree,
6541
best_param_idx,
6542
best_quick_prefix_records);
5772
new(param->mem_root) optimizer::TRP_GROUP_MIN_MAX(have_min,
5773
have_max,
5774
min_max_arg_part,
5775
group_prefix_len,
5776
used_key_parts,
5777
group_key_parts,
5778
index_info,
5779
index,
5780
key_infix_len,
5781
(key_infix_len > 0) ? key_infix : NULL,
5782
tree,
5783
best_index_tree,
5784
best_param_idx,
5785
best_quick_prefix_records);
6543
5786
if (read_plan)
6544
5787
{
6545
5788
if (tree && read_plan->quick_prefix_records == 0)
6835
6078
RETURN
6836
6079
Pointer to the SEL_ARG subtree that corresponds to index.
6837
6080
*/
6838
optimizer::SEL_ARG * get_index_range_tree(uint32_t index,
6839
SEL_TREE* range_tree,
6840
optimizer::Parameter *param,
6841
uint32_t *param_idx)
6081
optimizer::SEL_ARG *get_index_range_tree(uint32_t index,
6082
SEL_TREE* range_tree,
6083
optimizer::Parameter *param,
6084
uint32_t *param_idx)
6842
6085
{
6843
6086
uint32_t idx= 0; /* Index nr in param->key_parts */
6844
6087
while (idx < param->keys)
7002
6245
7003
6246
NOTES
7004
6247
Make_quick ignores the retrieve_full_rows parameter because
7005
QUICK_GROUP_MIN_MAX_SELECT always performs 'index only' scans.
6248
QuickGroupMinMaxSelect always performs 'index only' scans.
7006
6249
The other parameter are ignored as well because all necessary
7007
6250
data to create the QUICK object is computed at this TRP creation
7008
6251
time.
7009
6252
7010
6253
RETURN
7011
New QUICK_GROUP_MIN_MAX_SELECT object if successfully created,
6254
New QuickGroupMinMaxSelect object if successfully created,
7012
6255
NULL otherwise.
7013
6256
*/
7014
6257
optimizer::QuickSelectInterface *
7015
TRP_GROUP_MIN_MAX::make_quick(optimizer::Parameter *param, bool, MEM_ROOT *parent_alloc)
6258
optimizer::TRP_GROUP_MIN_MAX::make_quick(optimizer::Parameter *param, bool, MEM_ROOT *parent_alloc)
7016
6259
{
7017
optimizer::QUICK_GROUP_MIN_MAX_SELECT *quick= NULL;
6260
optimizer::QuickGroupMinMaxSelect *quick= NULL;
7018
6261
7019
quick= new optimizer::QUICK_GROUP_MIN_MAX_SELECT(param->table,
7020
param->session->lex->current_select->join,
7021
have_min,
7022
have_max,
7023
min_max_arg_part,
7024
group_prefix_len,
7025
group_key_parts,
7026
used_key_parts,
7027
index_info,
7028
index,
7029
read_cost,
7030
records,
7031
key_infix_len,
7032
key_infix,
7033
parent_alloc);
6262
quick= new optimizer::QuickGroupMinMaxSelect(param->table,
6263
param->session->lex->current_select->join,
6264
have_min,
6265
have_max,
6266
min_max_arg_part,
6267
group_prefix_len,
6268
group_key_parts,
6269
used_key_parts,
6270
index_info,
6271
index,
6272
read_cost,
6273
records,
6274
key_infix_len,
6275
key_infix,
6276
parent_alloc);
7034
6277
if (! quick)
7035
6278
{
7036
6279
return NULL;
7100
6343
}
7101
6344
7102
6345
7103
/*
7104
Construct new quick select for group queries with min/max.
7105
7106
SYNOPSIS
7107
QUICK_GROUP_MIN_MAX_SELECT::QUICK_GROUP_MIN_MAX_SELECT()
7108
table The table being accessed
7109
join Descriptor of the current query
7110
have_min true if the query selects a MIN function
7111
have_max true if the query selects a MAX function
7112
min_max_arg_part The only argument field of all MIN/MAX functions
7113
group_prefix_len Length of all key parts in the group prefix
7114
prefix_key_parts All key parts in the group prefix
7115
index_info The index chosen for data access
7116
use_index The id of index_info
7117
read_cost Cost of this access method
7118
records Number of records returned
7119
key_infix_len Length of the key infix appended to the group prefix
7120
key_infix Infix of constants from equality predicates
7121
parent_alloc Memory pool for this and quick_prefix_select data
7122
7123
RETURN
7124
None
7125
*/
7126
optimizer::QUICK_GROUP_MIN_MAX_SELECT::
7127
QUICK_GROUP_MIN_MAX_SELECT(Table *table,
7128
JOIN *join_arg,
7129
bool have_min_arg,
7130
bool have_max_arg,
7131
KEY_PART_INFO *min_max_arg_part_arg,
7132
uint32_t group_prefix_len_arg,
7133
uint32_t group_key_parts_arg,
7134
uint32_t used_key_parts_arg,
7135
KEY *index_info_arg,
7136
uint32_t use_index,
7137
double read_cost_arg,
7138
ha_rows records_arg,
7139
uint32_t key_infix_len_arg,
7140
unsigned char *key_infix_arg,
7141
MEM_ROOT *parent_alloc)
7142
:
7143
join(join_arg),
7144
index_info(index_info_arg),
7145
group_prefix_len(group_prefix_len_arg),
7146
group_key_parts(group_key_parts_arg),
7147
have_min(have_min_arg),
7148
have_max(have_max_arg),
7149
seen_first_key(false),
7150
min_max_arg_part(min_max_arg_part_arg),
7151
key_infix(key_infix_arg),
7152
key_infix_len(key_infix_len_arg),
7153
min_functions_it(NULL),
7154
max_functions_it(NULL)
7155
{
7156
head= table;
7157
cursor= head->cursor;
7158
index= use_index;
7159
record= head->record[0];
7160
tmp_record= head->record[1];
7161
read_time= read_cost_arg;
7162
records= records_arg;
7163
used_key_parts= used_key_parts_arg;
7164
real_key_parts= used_key_parts_arg;
7165
real_prefix_len= group_prefix_len + key_infix_len;
7166
group_prefix= NULL;
7167
min_max_arg_len= min_max_arg_part ? min_max_arg_part->store_length : 0;
7168
7169
/*
7170
We can't have parent_alloc set as the init function can't handle this case
7171
yet.
7172
*/
7173
assert(! parent_alloc);
7174
if (! parent_alloc)
7175
{
7176
init_sql_alloc(&alloc, join->session->variables.range_alloc_block_size, 0);
7177
join->session->mem_root= &alloc;
7178
}
7179
else
7180
memset(&alloc, 0, sizeof(MEM_ROOT)); // ensure that it's not used
7181
}
7182
7183
7184
/*
7185
Do post-constructor initialization.
7186
7187
SYNOPSIS
7188
QUICK_GROUP_MIN_MAX_SELECT::init()
7189
7190
DESCRIPTION
7191
The method performs initialization that cannot be done in the constructor
7192
such as memory allocations that may fail. It allocates memory for the
7193
group prefix and inifix buffers, and for the lists of MIN/MAX item to be
7194
updated during execution.
7195
7196
RETURN
7197
0 OK
7198
other Error code
7199
*/
7200
int optimizer::QUICK_GROUP_MIN_MAX_SELECT::init()
7201
{
7202
if (group_prefix) /* Already initialized. */
7203
return 0;
7204
7205
if (! (last_prefix= (unsigned char*) alloc_root(&alloc, group_prefix_len)))
7206
return 1;
7207
/*
7208
We may use group_prefix to store keys with all select fields, so allocate
7209
enough space for it.
7210
*/
7211
if (! (group_prefix= (unsigned char*) alloc_root(&alloc,
7212
real_prefix_len + min_max_arg_len)))
7213
return 1;
7214
7215
if (key_infix_len > 0)
7216
{
7217
/*
7218
The memory location pointed to by key_infix will be deleted soon, so
7219
allocate a new buffer and copy the key_infix into it.
7220
*/
7221
unsigned char *tmp_key_infix= (unsigned char*) alloc_root(&alloc, key_infix_len);
7222
if (! tmp_key_infix)
7223
return 1;
7224
memcpy(tmp_key_infix, this->key_infix, key_infix_len);
7225
this->key_infix= tmp_key_infix;
7226
}
7227
7228
if (min_max_arg_part)
7229
{
7230
if (my_init_dynamic_array(&min_max_ranges, sizeof(optimizer::QuickRange*), 16, 16))
7231
return 1;
7232
7233
if (have_min)
7234
{
7235
if (! (min_functions= new List<Item_sum>))
7236
return 1;
7237
}
7238
else
7239
min_functions= NULL;
7240
if (have_max)
7241
{
7242
if (! (max_functions= new List<Item_sum>))
7243
return 1;
7244
}
7245
else
7246
max_functions= NULL;
7247
7248
Item_sum *min_max_item= NULL;
7249
Item_sum **func_ptr= join->sum_funcs;
7250
while ((min_max_item= *(func_ptr++)))
7251
{
7252
if (have_min && (min_max_item->sum_func() == Item_sum::MIN_FUNC))
7253
min_functions->push_back(min_max_item);
7254
else if (have_max && (min_max_item->sum_func() == Item_sum::MAX_FUNC))
7255
max_functions->push_back(min_max_item);
7256
}
7257
7258
if (have_min)
7259
{
7260
if (! (min_functions_it= new List_iterator<Item_sum>(*min_functions)))
7261
return 1;
7262
}
7263
7264
if (have_max)
7265
{
7266
if (! (max_functions_it= new List_iterator<Item_sum>(*max_functions)))
7267
return 1;
7268
}
7269
}
7270
else
7271
min_max_ranges.elements= 0;
7272
7273
return 0;
7274
}
7275
7276
7277
optimizer::QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT()
7278
{
7279
if (cursor->inited != Cursor::NONE)
7280
{
7281
cursor->ha_index_end();
7282
}
7283
if (min_max_arg_part)
7284
{
7285
delete_dynamic(&min_max_ranges);
7286
}
7287
free_root(&alloc,MYF(0));
7288
delete min_functions_it;
7289
delete max_functions_it;
7290
delete quick_prefix_select;
7291
}
7292
7293
7294
/*
7295
Eventually create and add a new quick range object.
7296
7297
SYNOPSIS
7298
QUICK_GROUP_MIN_MAX_SELECT::add_range()
7299
sel_range Range object from which a
7300
7301
NOTES
7302
Construct a new QuickRange object from a SEL_ARG object, and
7303
add it to the array min_max_ranges. If sel_arg is an infinite
7304
range, e.g. (x < 5 or x > 4), then skip it and do not construct
7305
a quick range.
7306
7307
RETURN
7308
false on success
7309
true otherwise
7310
*/
7311
bool optimizer::QUICK_GROUP_MIN_MAX_SELECT::add_range(SEL_ARG *sel_range)
7312
{
7313
optimizer::QuickRange *range= NULL;
7314
uint32_t range_flag= sel_range->min_flag | sel_range->max_flag;
7315
7316
/* Skip (-inf,+inf) ranges, e.g. (x < 5 or x > 4). */
7317
if ((range_flag & NO_MIN_RANGE) && (range_flag & NO_MAX_RANGE))
7318
return false;
7319
7320
if (! (sel_range->min_flag & NO_MIN_RANGE) &&
7321
! (sel_range->max_flag & NO_MAX_RANGE))
7322
{
7323
if (sel_range->maybe_null &&
7324
sel_range->min_value[0] && sel_range->max_value[0])
7325
range_flag|= NULL_RANGE; /* IS NULL condition */
7326
else if (memcmp(sel_range->min_value, sel_range->max_value,
7327
min_max_arg_len) == 0)
7328
range_flag|= EQ_RANGE; /* equality condition */
7329
}
7330
range= new optimizer::QuickRange(sel_range->min_value,
7331
min_max_arg_len,
7332
make_keypart_map(sel_range->part),
7333
sel_range->max_value,
7334
min_max_arg_len,
7335
make_keypart_map(sel_range->part),
7336
range_flag);
7337
if (! range)
7338
return true;
7339
if (insert_dynamic(&min_max_ranges, (unsigned char*)&range))
7340
return true;
7341
return false;
7342
}
7343
7344
7345
/*
7346
Opens the ranges if there are more conditions in quick_prefix_select than
7347
the ones used for jumping through the prefixes.
7348
7349
SYNOPSIS
7350
QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges()
7351
7352
NOTES
7353
quick_prefix_select is made over the conditions on the whole key.
7354
It defines a number of ranges of length x.
7355
However when jumping through the prefixes we use only the the first
7356
few most significant keyparts in the range key. However if there
7357
are more keyparts to follow the ones we are using we must make the
7358
condition on the key inclusive (because x < "ab" means
7359
x[0] < 'a' OR (x[0] == 'a' AND x[1] < 'b').
7360
To achive the above we must turn off the NEAR_MIN/NEAR_MAX
7361
*/
7362
void optimizer::QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges()
7363
{
7364
if (quick_prefix_select &&
7365
group_prefix_len < quick_prefix_select->max_used_key_length)
7366
{
7367
DYNAMIC_ARRAY *arr= NULL;
7368
uint32_t inx;
7369
7370
for (inx= 0, arr= &quick_prefix_select->ranges; inx < arr->elements; inx++)
7371
{
7372
optimizer::QuickRange *range= NULL;
7373
7374
get_dynamic(arr, (unsigned char*)&range, inx);
7375
range->flag &= ~(NEAR_MIN | NEAR_MAX);
7376
}
7377
}
7378
}
7379
7380
7381
/*
7382
Determine the total number and length of the keys that will be used for
7383
index lookup.
7384
7385
SYNOPSIS
7386
QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
7387
7388
DESCRIPTION
7389
The total length of the keys used for index lookup depends on whether
7390
there are any predicates referencing the min/max argument, and/or if
7391
the min/max argument field can be NULL.
7392
This function does an optimistic analysis whether the search key might
7393
be extended by a constant for the min/max keypart. It is 'optimistic'
7394
because during actual execution it may happen that a particular range
7395
is skipped, and then a shorter key will be used. However this is data
7396
dependent and can't be easily estimated here.
7397
7398
RETURN
7399
None
7400
*/
7401
void optimizer::QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
7402
{
7403
max_used_key_length= real_prefix_len;
7404
if (min_max_ranges.elements > 0)
7405
{
7406
optimizer::QuickRange *cur_range= NULL;
7407
if (have_min)
7408
{ /* Check if the right-most range has a lower boundary. */
7409
get_dynamic(&min_max_ranges,
7410
(unsigned char*) &cur_range,
7411
min_max_ranges.elements - 1);
7412
if (! (cur_range->flag & NO_MIN_RANGE))
7413
{
7414
max_used_key_length+= min_max_arg_len;
7415
used_key_parts++;
7416
return;
7417
}
7418
}
7419
if (have_max)
7420
{ /* Check if the left-most range has an upper boundary. */
7421
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, 0);
7422
if (! (cur_range->flag & NO_MAX_RANGE))
7423
{
7424
max_used_key_length+= min_max_arg_len;
7425
used_key_parts++;
7426
return;
7427
}
7428
}
7429
}
7430
else if (have_min && min_max_arg_part &&
7431
min_max_arg_part->field->real_maybe_null())
7432
{
7433
/*
7434
If a MIN/MAX argument value is NULL, we can quickly determine
7435
that we're in the beginning of the next group, because NULLs
7436
are always < any other value. This allows us to quickly
7437
determine the end of the current group and jump to the next
7438
group (see next_min()) and thus effectively increases the
7439
usable key length.
7440
*/
7441
max_used_key_length+= min_max_arg_len;
7442
used_key_parts++;
7443
}
7444
}
7445
7446
7447
/*
7448
Initialize a quick group min/max select for key retrieval.
7449
7450
SYNOPSIS
7451
QUICK_GROUP_MIN_MAX_SELECT::reset()
7452
7453
DESCRIPTION
7454
Initialize the index chosen for access and find and store the prefix
7455
of the last group. The method is expensive since it performs disk access.
7456
7457
RETURN
7458
0 OK
7459
other Error code
7460
*/
7461
int optimizer::QUICK_GROUP_MIN_MAX_SELECT::reset(void)
7462
{
7463
int result;
7464
7465
cursor->extra(HA_EXTRA_KEYREAD); /* We need only the key attributes */
7466
if ((result= cursor->ha_index_init(index,1)))
7467
return result;
7468
if (quick_prefix_select && quick_prefix_select->reset())
7469
return 0;
7470
result= cursor->index_last(record);
7471
if (result == HA_ERR_END_OF_FILE)
7472
return 0;
7473
/* Save the prefix of the last group. */
7474
key_copy(last_prefix, record, index_info, group_prefix_len);
7475
7476
return 0;
7477
}
7478
7479
7480
7481
/*
7482
Get the next key containing the MIN and/or MAX key for the next group.
7483
7484
SYNOPSIS
7485
QUICK_GROUP_MIN_MAX_SELECT::get_next()
7486
7487
DESCRIPTION
7488
The method finds the next subsequent group of records that satisfies the
7489
query conditions and finds the keys that contain the MIN/MAX values for
7490
the key part referenced by the MIN/MAX function(s). Once a group and its
7491
MIN/MAX values are found, store these values in the Item_sum objects for
7492
the MIN/MAX functions. The rest of the values in the result row are stored
7493
in the Item_field::result_field of each select field. If the query does
7494
not contain MIN and/or MAX functions, then the function only finds the
7495
group prefix, which is a query answer itself.
7496
7497
NOTES
7498
If both MIN and MAX are computed, then we use the fact that if there is
7499
no MIN key, there can't be a MAX key as well, so we can skip looking
7500
for a MAX key in this case.
7501
7502
RETURN
7503
0 on success
7504
HA_ERR_END_OF_FILE if returned all keys
7505
other if some error occurred
7506
*/
7507
int optimizer::QUICK_GROUP_MIN_MAX_SELECT::get_next()
7508
{
7509
int min_res= 0;
7510
int max_res= 0;
7511
int result= 0;
7512
int is_last_prefix= 0;
7513
7514
/*
7515
Loop until a group is found that satisfies all query conditions or the last
7516
group is reached.
7517
*/
7518
do
7519
{
7520
result= next_prefix();
7521
/*
7522
Check if this is the last group prefix. Notice that at this point
7523
this->record contains the current prefix in record format.
7524
*/
7525
if (! result)
7526
{
7527
is_last_prefix= key_cmp(index_info->key_part, last_prefix,
7528
group_prefix_len);
7529
assert(is_last_prefix <= 0);
7530
}
7531
else
7532
{
7533
if (result == HA_ERR_KEY_NOT_FOUND)
7534
continue;
7535
break;
7536
}
7537
7538
if (have_min)
7539
{
7540
min_res= next_min();
7541
if (min_res == 0)
7542
update_min_result();
7543
}
7544
/* If there is no MIN in the group, there is no MAX either. */
7545
if ((have_max && !have_min) ||
7546
(have_max && have_min && (min_res == 0)))
7547
{
7548
max_res= next_max();
7549
if (max_res == 0)
7550
update_max_result();
7551
/* If a MIN was found, a MAX must have been found as well. */
7552
assert(((have_max && !have_min) ||
7553
(have_max && have_min && (max_res == 0))));
7554
}
7555
/*
7556
If this is just a GROUP BY or DISTINCT without MIN or MAX and there
7557
are equality predicates for the key parts after the group, find the
7558
first sub-group with the extended prefix.
7559
*/
7560
if (! have_min && ! have_max && key_infix_len > 0)
7561
result= cursor->index_read_map(record,
7562
group_prefix,
7563
make_prev_keypart_map(real_key_parts),
7564
HA_READ_KEY_EXACT);
7565
7566
result= have_min ? min_res : have_max ? max_res : result;
7567
} while ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
7568
is_last_prefix != 0);
7569
7570
if (result == 0)
7571
{
7572
/*
7573
Partially mimic the behavior of end_select_send. Copy the
7574
field data from Item_field::field into Item_field::result_field
7575
of each non-aggregated field (the group fields, and optionally
7576
other fields in non-ANSI SQL mode).
7577
*/
7578
copy_fields(&join->tmp_table_param);
7579
}
7580
else if (result == HA_ERR_KEY_NOT_FOUND)
7581
result= HA_ERR_END_OF_FILE;
7582
7583
return result;
7584
}
7585
7586
7587
/*
7588
Retrieve the minimal key in the next group.
7589
7590
SYNOPSIS
7591
QUICK_GROUP_MIN_MAX_SELECT::next_min()
7592
7593
DESCRIPTION
7594
Find the minimal key within this group such that the key satisfies the query
7595
conditions and NULL semantics. The found key is loaded into this->record.
7596
7597
IMPLEMENTATION
7598
Depending on the values of min_max_ranges.elements, key_infix_len, and
7599
whether there is a NULL in the MIN field, this function may directly
7600
return without any data access. In this case we use the key loaded into
7601
this->record by the call to this->next_prefix() just before this call.
7602
7603
RETURN
7604
0 on success
7605
HA_ERR_KEY_NOT_FOUND if no MIN key was found that fulfills all conditions.
7606
HA_ERR_END_OF_FILE - "" -
7607
other if some error occurred
7608
*/
7609
int optimizer::QUICK_GROUP_MIN_MAX_SELECT::next_min()
7610
{
7611
int result= 0;
7612
7613
/* Find the MIN key using the eventually extended group prefix. */
7614
if (min_max_ranges.elements > 0)
7615
{
7616
if ((result= next_min_in_range()))
7617
return result;
7618
}
7619
else
7620
{
7621
/* Apply the constant equality conditions to the non-group select fields */
7622
if (key_infix_len > 0)
7623
{
7624
if ((result= cursor->index_read_map(record,
7625
group_prefix,
7626
make_prev_keypart_map(real_key_parts),
7627
HA_READ_KEY_EXACT)))
7628
return result;
7629
}
7630
7631
/*
7632
If the min/max argument field is NULL, skip subsequent rows in the same
7633
group with NULL in it. Notice that:
7634
- if the first row in a group doesn't have a NULL in the field, no row
7635
in the same group has (because NULL < any other value),
7636
- min_max_arg_part->field->ptr points to some place in 'record'.
7637
*/
7638
if (min_max_arg_part && min_max_arg_part->field->is_null())
7639
{
7640
/* Find the first subsequent record without NULL in the MIN/MAX field. */
7641
key_copy(tmp_record, record, index_info, 0);
7642
result= cursor->index_read_map(record,
7643
tmp_record,
7644
make_keypart_map(real_key_parts),
7645
HA_READ_AFTER_KEY);
7646
/*
7647
Check if the new record belongs to the current group by comparing its
7648
prefix with the group's prefix. If it is from the next group, then the
7649
whole group has NULLs in the MIN/MAX field, so use the first record in
7650
the group as a result.
7651
TODO:
7652
It is possible to reuse this new record as the result candidate for the
7653
next call to next_min(), and to save one lookup in the next call. For
7654
this add a new member 'this->next_group_prefix'.
7655
*/
7656
if (! result)
7657
{
7658
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
7659
key_restore(record, tmp_record, index_info, 0);
7660
}
7661
else if (result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE)
7662
result= 0; /* There is a result in any case. */
7663
}
7664
}
7665
7666
/*
7667
If the MIN attribute is non-nullable, this->record already contains the
7668
MIN key in the group, so just return.
7669
*/
7670
return result;
7671
}
7672
7673
7674
/*
7675
Retrieve the maximal key in the next group.
7676
7677
SYNOPSIS
7678
QUICK_GROUP_MIN_MAX_SELECT::next_max()
7679
7680
DESCRIPTION
7681
Lookup the maximal key of the group, and store it into this->record.
7682
7683
RETURN
7684
0 on success
7685
HA_ERR_KEY_NOT_FOUND if no MAX key was found that fulfills all conditions.
7686
HA_ERR_END_OF_FILE - "" -
7687
other if some error occurred
7688
*/
7689
int optimizer::QUICK_GROUP_MIN_MAX_SELECT::next_max()
7690
{
7691
int result= 0;
7692
7693
/* Get the last key in the (possibly extended) group. */
7694
if (min_max_ranges.elements > 0)
7695
result= next_max_in_range();
7696
else
7697
result= cursor->index_read_map(record,
7698
group_prefix,
7699
make_prev_keypart_map(real_key_parts),
7700
HA_READ_PREFIX_LAST);
7701
return result;
7702
}
7703
7704
7705
/*
7706
Determine the prefix of the next group.
7707
7708
SYNOPSIS
7709
QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
7710
7711
DESCRIPTION
7712
Determine the prefix of the next group that satisfies the query conditions.
7713
If there is a range condition referencing the group attributes, use a
7714
QuickRangeSelect object to retrieve the *first* key that satisfies the
7715
condition. If there is a key infix of constants, append this infix
7716
immediately after the group attributes. The possibly extended prefix is
7717
stored in this->group_prefix. The first key of the found group is stored in
7718
this->record, on which relies this->next_min().
7719
7720
RETURN
7721
0 on success
7722
HA_ERR_KEY_NOT_FOUND if there is no key with the formed prefix
7723
HA_ERR_END_OF_FILE if there are no more keys
7724
other if some error occurred
7725
*/
7726
int optimizer::QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
7727
{
7728
int result= 0;
7729
7730
if (quick_prefix_select)
7731
{
7732
unsigned char *cur_prefix= seen_first_key ? group_prefix : NULL;
7733
if ((result= quick_prefix_select->get_next_prefix(group_prefix_len,
7734
make_prev_keypart_map(group_key_parts),
7735
cur_prefix)))
7736
return result;
7737
seen_first_key= true;
7738
}
7739
else
7740
{
7741
if (! seen_first_key)
7742
{
7743
result= cursor->index_first(record);
7744
if (result)
7745
return result;
7746
seen_first_key= true;
7747
}
7748
else
7749
{
7750
/* Load the first key in this group into record. */
7751
result= cursor->index_read_map(record,
7752
group_prefix,
7753
make_prev_keypart_map(group_key_parts),
7754
HA_READ_AFTER_KEY);
7755
if (result)
7756
return result;
7757
}
7758
}
7759
7760
/* Save the prefix of this group for subsequent calls. */
7761
key_copy(group_prefix, record, index_info, group_prefix_len);
7762
/* Append key_infix to group_prefix. */
7763
if (key_infix_len > 0)
7764
memcpy(group_prefix + group_prefix_len,
7765
key_infix,
7766
key_infix_len);
7767
7768
return 0;
7769
}
7770
7771
7772
/*
7773
Find the minimal key in a group that satisfies some range conditions for the
7774
min/max argument field.
7775
7776
SYNOPSIS
7777
QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
7778
7779
DESCRIPTION
7780
Given the sequence of ranges min_max_ranges, find the minimal key that is
7781
in the left-most possible range. If there is no such key, then the current
7782
group does not have a MIN key that satisfies the WHERE clause. If a key is
7783
found, its value is stored in this->record.
7784
7785
RETURN
7786
0 on success
7787
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
7788
the ranges
7789
HA_ERR_END_OF_FILE - "" -
7790
other if some error
7791
*/
7792
int optimizer::QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
7793
{
7794
ha_rkey_function find_flag;
7795
key_part_map keypart_map;
7796
optimizer::QuickRange *cur_range= NULL;
7797
bool found_null= false;
7798
int result= HA_ERR_KEY_NOT_FOUND;
7799
basic_string<unsigned char> max_key;
7800
7801
max_key.reserve(real_prefix_len + min_max_arg_len);
7802
7803
assert(min_max_ranges.elements > 0);
7804
7805
for (uint32_t range_idx= 0; range_idx < min_max_ranges.elements; range_idx++)
7806
{ /* Search from the left-most range to the right. */
7807
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, range_idx);
7808
7809
/*
7810
If the current value for the min/max argument is bigger than the right
7811
boundary of cur_range, there is no need to check this range.
7812
*/
7813
if (range_idx != 0 && !(cur_range->flag & NO_MAX_RANGE) &&
7814
(key_cmp(min_max_arg_part,
7815
(const unsigned char*) cur_range->max_key,
7816
min_max_arg_len) == 1))
7817
continue;
7818
7819
if (cur_range->flag & NO_MIN_RANGE)
7820
{
7821
keypart_map= make_prev_keypart_map(real_key_parts);
7822
find_flag= HA_READ_KEY_EXACT;
7823
}
7824
else
7825
{
7826
/* Extend the search key with the lower boundary for this range. */
7827
memcpy(group_prefix + real_prefix_len,
7828
cur_range->min_key,
7829
cur_range->min_length);
7830
keypart_map= make_keypart_map(real_key_parts);
7831
find_flag= (cur_range->flag & (EQ_RANGE | NULL_RANGE)) ?
7832
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MIN) ?
7833
HA_READ_AFTER_KEY : HA_READ_KEY_OR_NEXT;
7834
}
7835
7836
result= cursor->index_read_map(record, group_prefix, keypart_map, find_flag);
7837
if (result)
7838
{
7839
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
7840
(cur_range->flag & (EQ_RANGE | NULL_RANGE)))
7841
continue; /* Check the next range. */
7842
7843
/*
7844
In all other cases (HA_ERR_*, HA_READ_KEY_EXACT with NO_MIN_RANGE,
7845
HA_READ_AFTER_KEY, HA_READ_KEY_OR_NEXT) if the lookup failed for this
7846
range, it can't succeed for any other subsequent range.
7847
*/
7848
break;
7849
}
7850
7851
/* A key was found. */
7852
if (cur_range->flag & EQ_RANGE)
7853
break; /* No need to perform the checks below for equal keys. */
7854
7855
if (cur_range->flag & NULL_RANGE)
7856
{
7857
/*
7858
Remember this key, and continue looking for a non-NULL key that
7859
satisfies some other condition.
7860
*/
7861
memcpy(tmp_record, record, head->s->rec_buff_length);
7862
found_null= true;
7863
continue;
7864
}
7865
7866
/* Check if record belongs to the current group. */
7867
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
7868
{
7869
result= HA_ERR_KEY_NOT_FOUND;
7870
continue;
7871
}
7872
7873
/* If there is an upper limit, check if the found key is in the range. */
7874
if (! (cur_range->flag & NO_MAX_RANGE) )
7875
{
7876
/* Compose the MAX key for the range. */
7877
max_key.clear();
7878
max_key.append(group_prefix, real_prefix_len);
7879
max_key.append(cur_range->max_key, cur_range->max_length);
7880
/* Compare the found key with max_key. */
7881
int cmp_res= key_cmp(index_info->key_part,
7882
max_key.data(),
7883
real_prefix_len + min_max_arg_len);
7884
if (! (((cur_range->flag & NEAR_MAX) && (cmp_res == -1)) ||
7885
(cmp_res <= 0)))
7886
{
7887
result= HA_ERR_KEY_NOT_FOUND;
7888
continue;
7889
}
7890
}
7891
/* If we got to this point, the current key qualifies as MIN. */
7892
assert(result == 0);
7893
break;
7894
}
7895
/*
7896
If there was a key with NULL in the MIN/MAX field, and there was no other
7897
key without NULL from the same group that satisfies some other condition,
7898
then use the key with the NULL.
7899
*/
7900
if (found_null && result)
7901
{
7902
memcpy(record, tmp_record, head->s->rec_buff_length);
7903
result= 0;
7904
}
7905
return result;
7906
}
7907
7908
7909
/*
7910
Find the maximal key in a group that satisfies some range conditions for the
7911
min/max argument field.
7912
7913
SYNOPSIS
7914
QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
7915
7916
DESCRIPTION
7917
Given the sequence of ranges min_max_ranges, find the maximal key that is
7918
in the right-most possible range. If there is no such key, then the current
7919
group does not have a MAX key that satisfies the WHERE clause. If a key is
7920
found, its value is stored in this->record.
7921
7922
RETURN
7923
0 on success
7924
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
7925
the ranges
7926
HA_ERR_END_OF_FILE - "" -
7927
other if some error
7928
*/
7929
int optimizer::QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
7930
{
7931
ha_rkey_function find_flag;
7932
key_part_map keypart_map;
7933
optimizer::QuickRange *cur_range= NULL;
7934
int result= 0;
7935
basic_string<unsigned char> min_key;
7936
min_key.reserve(real_prefix_len + min_max_arg_len);
7937
7938
assert(min_max_ranges.elements > 0);
7939
7940
for (uint32_t range_idx= min_max_ranges.elements; range_idx > 0; range_idx--)
7941
{ /* Search from the right-most range to the left. */
7942
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, range_idx - 1);
7943
7944
/*
7945
If the current value for the min/max argument is smaller than the left
7946
boundary of cur_range, there is no need to check this range.
7947
*/
7948
if (range_idx != min_max_ranges.elements &&
7949
! (cur_range->flag & NO_MIN_RANGE) &&
7950
(key_cmp(min_max_arg_part,
7951
(const unsigned char*) cur_range->min_key,
7952
min_max_arg_len) == -1))
7953
continue;
7954
7955
if (cur_range->flag & NO_MAX_RANGE)
7956
{
7957
keypart_map= make_prev_keypart_map(real_key_parts);
7958
find_flag= HA_READ_PREFIX_LAST;
7959
}
7960
else
7961
{
7962
/* Extend the search key with the upper boundary for this range. */
7963
memcpy(group_prefix + real_prefix_len,
7964
cur_range->max_key,
7965
cur_range->max_length);
7966
keypart_map= make_keypart_map(real_key_parts);
7967
find_flag= (cur_range->flag & EQ_RANGE) ?
7968
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MAX) ?
7969
HA_READ_BEFORE_KEY : HA_READ_PREFIX_LAST_OR_PREV;
7970
}
7971
7972
result= cursor->index_read_map(record, group_prefix, keypart_map, find_flag);
7973
7974
if (result)
7975
{
7976
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
7977
(cur_range->flag & EQ_RANGE))
7978
continue; /* Check the next range. */
7979
7980
/*
7981
In no key was found with this upper bound, there certainly are no keys
7982
in the ranges to the left.
7983
*/
7984
return result;
7985
}
7986
/* A key was found. */
7987
if (cur_range->flag & EQ_RANGE)
7988
return 0; /* No need to perform the checks below for equal keys. */
7989
7990
/* Check if record belongs to the current group. */
7991
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
7992
continue; // Row not found
7993
7994
/* If there is a lower limit, check if the found key is in the range. */
7995
if (! (cur_range->flag & NO_MIN_RANGE) )
7996
{
7997
/* Compose the MIN key for the range. */
7998
min_key.clear();
7999
min_key.append(group_prefix, real_prefix_len);
8000
min_key.append(cur_range->min_key, cur_range->min_length);
8001
8002
/* Compare the found key with min_key. */
8003
int cmp_res= key_cmp(index_info->key_part,
8004
min_key.data(),
8005
real_prefix_len + min_max_arg_len);
8006
if (! (((cur_range->flag & NEAR_MIN) && (cmp_res == 1)) ||
8007
(cmp_res >= 0)))
8008
continue;
8009
}
8010
/* If we got to this point, the current key qualifies as MAX. */
8011
return result;
8012
}
8013
return HA_ERR_KEY_NOT_FOUND;
8014
}
8015
8016
8017
/*
8018
Update all MIN function results with the newly found value.
8019
8020
SYNOPSIS
8021
QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
8022
8023
DESCRIPTION
8024
The method iterates through all MIN functions and updates the result value
8025
of each function by calling Item_sum::reset(), which in turn picks the new
8026
result value from this->head->record[0], previously updated by
8027
next_min(). The updated value is stored in a member variable of each of the
8028
Item_sum objects, depending on the value type.
8029
8030
IMPLEMENTATION
8031
The update must be done separately for MIN and MAX, immediately after
8032
next_min() was called and before next_max() is called, because both MIN and
8033
MAX take their result value from the same buffer this->head->record[0]
8034
(i.e. this->record).
8035
8036
RETURN
8037
None
8038
*/
8039
void optimizer::QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
8040
{
8041
Item_sum *min_func= NULL;
8042
8043
min_functions_it->rewind();
8044
while ((min_func= (*min_functions_it)++))
8045
min_func->reset();
8046
}
8047
8048
8049
/*
8050
Update all MAX function results with the newly found value.
8051
8052
SYNOPSIS
8053
QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
8054
8055
DESCRIPTION
8056
The method iterates through all MAX functions and updates the result value
8057
of each function by calling Item_sum::reset(), which in turn picks the new
8058
result value from this->head->record[0], previously updated by
8059
next_max(). The updated value is stored in a member variable of each of the
8060
Item_sum objects, depending on the value type.
8061
8062
IMPLEMENTATION
8063
The update must be done separately for MIN and MAX, immediately after
8064
next_max() was called, because both MIN and MAX take their result value
8065
from the same buffer this->head->record[0] (i.e. this->record).
8066
8067
RETURN
8068
None
8069
*/
8070
void optimizer::QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
8071
{
8072
Item_sum *max_func= NULL;
8073
8074
max_functions_it->rewind();
8075
while ((max_func= (*max_functions_it)++))
8076
max_func->reset();
8077
}
8078
8079
8080
/*
8081
Append comma-separated list of keys this quick select uses to key_names;
8082
append comma-separated list of corresponding used lengths to used_lengths.
8083
8084
SYNOPSIS
8085
QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths()
8086
key_names [out] Names of used indexes
8087
used_lengths [out] Corresponding lengths of the index names
8088
8089
DESCRIPTION
8090
This method is used by select_describe to extract the names of the
8091
indexes used by a quick select.
8092
8093
*/
8094
void optimizer::QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths(String *key_names,
8095
String *used_lengths)
8096
{
8097
char buf[64];
8098
uint32_t length;
8099
key_names->append(index_info->name);
8100
length= int64_t2str(max_used_key_length, buf, 10) - buf;
8101
used_lengths->append(buf, length);
8102
}
6346
optimizer::QuickSelectInterface *optimizer::TRP_RANGE::make_quick(optimizer::Parameter *param, bool, MEM_ROOT *parent_alloc)
6347
{
6348
optimizer::QuickRangeSelect *quick= NULL;
6349
if ((quick= optimizer::get_quick_select(param,
6350
key_idx,
6351
key,
6352
mrr_flags,
6353
mrr_buf_size,
6354
parent_alloc)))
6355
{
6356
quick->records= records;
6357
quick->read_time= read_cost;
6358
}
6359
return quick;
6360
}
6361
8103
6362
8104
6363
static void print_sel_tree(optimizer::Parameter *param, SEL_TREE *tree, key_map *tree_map, const char *)
8105
6364
{
Loggerhead is a web-based interface for Breezy
Version: 2.0.1