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