← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/optimizer/range.cc

  • Committer: Stewart Smith
  • Date: 2010-11-03 03:27:09 UTC
  • mto: (1902.1.1 build) (1910.1.2 build)
  • mto: This revision was merged to the branch mainline in revision 1903.
  • Revision ID: stewart@flamingspork.com-20101103032709-oyvfrc6eb8fzj0mr
fix docs warning: docs/unlock.rst:2: (WARNING/2) Title underline too short.

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/optimizer/range.cc
84
84
  keypart-value-bytes holds the value. Its format depends on the field type.
85
85
  The length of keypart-value-bytes may or may not depend on the value being
86
86
  stored. The default is that length is static and equal to
87
 
  KEY_PART_INFO::length.
 
87
  KeyPartInfo::length.
88
88
 
89
89
  Key parts with (key_part_flag & HA_BLOB_PART) have length depending of the
90
90
  value:
109
109
#include <vector>
110
110
#include <algorithm>
111
111
 
 
112
#include <boost/dynamic_bitset.hpp>
 
113
 
112
114
#include "drizzled/sql_base.h"
113
115
#include "drizzled/sql_select.h"
114
116
#include "drizzled/error.h"
135
137
 
136
138
#include "drizzled/temporal.h" /* Needed in get_mm_leaf() for timestamp -> datetime comparisons */
137
139
 
138
 
#include "drizzled/memory/multi_malloc.h"
139
 
 
140
140
using namespace std;
141
141
namespace drizzled
142
142
{
206
206
  cost->zero();
207
207
  if (table->cursor->primary_key_is_clustered())
208
208
  {
209
 
    cost->setIOCount(table->cursor->read_time(table->s->primary_key,
 
209
    cost->setIOCount(table->cursor->read_time(table->getShare()->getPrimaryKey(),
210
210
                                             static_cast<uint32_t>(nrows),
211
211
                                             nrows));
212
212
  }
230
230
  }
231
231
}
232
232
 
233
 
struct st_ror_scan_info;
234
 
 
235
233
static optimizer::SEL_TREE * get_mm_parts(optimizer::RangeParameter *param,
236
234
                               COND *cond_func,
237
235
                               Field *field,
250
248
 
251
249
static bool is_key_scan_ror(optimizer::Parameter *param, uint32_t keynr, uint8_t nparts);
252
250
 
253
 
static ha_rows check_quick_select(optimizer::Parameter *param,
 
251
static ha_rows check_quick_select(Session *session,
 
252
                                  optimizer::Parameter *param,
254
253
                                  uint32_t idx,
255
254
                                  bool index_only,
256
255
                                  optimizer::SEL_ARG *tree,
259
258
                                  uint32_t *bufsize,
260
259
                                  optimizer::CostVector *cost);
261
260
 
262
 
static optimizer::RangeReadPlan *get_key_scans_params(optimizer::Parameter *param,
 
261
static optimizer::RangeReadPlan *get_key_scans_params(Session *session,
 
262
                                                      optimizer::Parameter *param,
263
263
                                                      optimizer::SEL_TREE *tree,
264
264
                                                      bool index_read_must_be_used,
265
265
                                                      bool update_tbl_stats,
277
277
                                                                 double read_time);
278
278
 
279
279
static
280
 
optimizer::TableReadPlan *get_best_disjunct_quick(optimizer::Parameter *param,
 
280
optimizer::TableReadPlan *get_best_disjunct_quick(Session *session,
 
281
                                                  optimizer::Parameter *param,
281
282
                                                  optimizer::SEL_IMERGE *imerge,
282
283
                                                  double read_time);
283
284
 
384
385
 
385
386
void optimizer::SqlSelect::cleanup()
386
387
{
387
 
  delete quick;
388
 
  quick= 0;
 
388
  if (quick)
 
389
  {
 
390
    delete quick;
 
391
    quick= NULL;
 
392
  }
 
393
 
389
394
  if (free_cond)
390
395
  {
391
396
    free_cond= 0;
459
464
    MAX_KEY if no such index was found.
460
465
*/
461
466
 
462
 
uint32_t optimizer::get_index_for_order(Table *table, order_st *order, ha_rows limit)
 
467
uint32_t optimizer::get_index_for_order(Table *table, Order *order, ha_rows limit)
463
468
{
464
469
  uint32_t idx;
465
470
  uint32_t match_key= MAX_KEY, match_key_len= MAX_KEY_LENGTH + 1;
466
 
  order_st *ord;
 
471
  Order *ord;
467
472
 
468
473
  for (ord= order; ord; ord= ord->next)
469
474
    if (!ord->asc)
470
475
      return MAX_KEY;
471
476
 
472
 
  for (idx= 0; idx < table->s->keys; idx++)
 
477
  for (idx= 0; idx < table->getShare()->sizeKeys(); idx++)
473
478
  {
474
479
    if (!(table->keys_in_use_for_query.test(idx)))
475
480
      continue;
476
 
    KEY_PART_INFO *keyinfo= table->key_info[idx].key_part;
 
481
    KeyPartInfo *keyinfo= table->key_info[idx].key_part;
477
482
    uint32_t n_parts=  table->key_info[idx].key_parts;
478
483
    uint32_t partno= 0;
479
484
 
538
543
static int fill_used_fields_bitmap(optimizer::Parameter *param)
539
544
{
540
545
  Table *table= param->table;
541
 
  my_bitmap_map *tmp;
542
546
  uint32_t pk;
543
 
  param->tmp_covered_fields.setBitmap(0);
544
 
  param->fields_bitmap_size= table->s->column_bitmap_size;
545
 
  if (!(tmp= (my_bitmap_map*) alloc_root(param->mem_root,
546
 
                                  param->fields_bitmap_size)) ||
547
 
      param->needed_fields.init(tmp, table->s->fields))
548
 
    return 1;
549
 
 
550
 
  param->needed_fields= *table->read_set;
551
 
  bitmap_union(&param->needed_fields, table->write_set);
552
 
 
553
 
  pk= param->table->s->primary_key;
 
547
  param->tmp_covered_fields.clear();
 
548
  param->needed_fields.resize(table->getShare()->sizeFields());
 
549
  param->needed_fields.reset();
 
550
 
 
551
  param->needed_fields|= *table->read_set;
 
552
  param->needed_fields|= *table->write_set;
 
553
 
 
554
  pk= param->table->getShare()->getPrimaryKey();
554
555
  if (pk != MAX_KEY && param->table->cursor->primary_key_is_clustered())
555
556
  {
556
557
    /* The table uses clustered PK and it is not internally generated */
557
 
    KEY_PART_INFO *key_part= param->table->key_info[pk].key_part;
558
 
    KEY_PART_INFO *key_part_end= key_part +
 
558
    KeyPartInfo *key_part= param->table->key_info[pk].key_part;
 
559
    KeyPartInfo *key_part_end= key_part +
559
560
                                 param->table->key_info[pk].key_parts;
560
561
    for (;key_part != key_part_end; ++key_part)
561
 
      param->needed_fields.clearBit(key_part->fieldnr-1);
 
562
      param->needed_fields.reset(key_part->fieldnr-1);
562
563
  }
563
564
  return 0;
564
565
}
639
640
{
640
641
  uint32_t idx;
641
642
  double scan_time;
642
 
  delete quick;
643
 
  quick=0;
 
643
  if (quick)
 
644
  {
 
645
    delete quick;
 
646
    quick= NULL;
 
647
  }
644
648
  needed_reg.reset();
645
649
  quick_keys.reset();
646
650
  if (keys_to_use.none())
663
667
    memory::Root alloc;
664
668
    optimizer::SEL_TREE *tree= NULL;
665
669
    KEY_PART *key_parts;
666
 
    KEY *key_info;
 
670
    KeyInfo *key_info;
667
671
    optimizer::Parameter param;
668
672
 
669
673
    if (check_stack_overrun(session, 2*STACK_MIN_SIZE, NULL))
686
690
 
687
691
    session->no_errors=1;                               // Don't warn about NULL
688
692
    memory::init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
689
 
    if (!(param.key_parts= (KEY_PART*) alloc_root(&alloc,
690
 
                                                  sizeof(KEY_PART)*
691
 
                                                  head->s->key_parts)) ||
 
693
    if (!(param.key_parts= (KEY_PART*) alloc.alloc_root( sizeof(KEY_PART) * head->getShare()->key_parts)) ||
692
694
        fill_used_fields_bitmap(&param))
693
695
    {
694
696
      session->no_errors=0;
695
 
      free_root(&alloc,MYF(0));                 // Return memory & allocator
 
697
      alloc.free_root(MYF(0));                  // Return memory & allocator
 
698
 
696
699
      return 0;                         // Can't use range
697
700
    }
698
701
    key_parts= param.key_parts;
703
706
      This is used in get_mm_parts function.
704
707
    */
705
708
    key_info= head->key_info;
706
 
    for (idx=0 ; idx < head->s->keys ; idx++, key_info++)
 
709
    for (idx=0 ; idx < head->getShare()->sizeKeys() ; idx++, key_info++)
707
710
    {
708
 
      KEY_PART_INFO *key_part_info;
 
711
      KeyPartInfo *key_part_info;
709
712
      if (! keys_to_use.test(idx))
710
713
        continue;
711
714
 
793
796
        bool can_build_covering= false;
794
797
 
795
798
        /* Get best 'range' plan and prepare data for making other plans */
796
 
        if ((range_trp= get_key_scans_params(&param, tree, false, true,
 
799
        if ((range_trp= get_key_scans_params(session, &param, tree, false, true,
797
800
                                             best_read_time)))
798
801
        {
799
802
          best_trp= range_trp;
820
823
              Try constructing covering ROR-intersect only if it looks possible
821
824
              and worth doing.
822
825
            */
823
 
            if (rori_trp->isRowRetrievalNecessary() && can_build_covering &&
 
826
            if (!rori_trp->is_covering && can_build_covering &&
824
827
                (rori_trp= get_best_covering_ror_intersect(&param, tree,
825
828
                                                           best_read_time)))
826
829
              best_trp= rori_trp;
836
839
        List_iterator_fast<optimizer::SEL_IMERGE> it(tree->merges);
837
840
        while ((imerge= it++))
838
841
        {
839
 
          new_conj_trp= get_best_disjunct_quick(&param, imerge, best_read_time);
 
842
          new_conj_trp= get_best_disjunct_quick(session, &param, imerge, best_read_time);
840
843
          if (new_conj_trp)
841
844
            set_if_smaller(param.table->quick_condition_rows,
842
845
                           new_conj_trp->records);
857
860
      records= best_trp->records;
858
861
      if (! (quick= best_trp->make_quick(&param, true)) || quick->init())
859
862
      {
860
 
        delete quick;
861
 
        quick= NULL;
 
863
        /* quick can already be free here */
 
864
        if (quick)
 
865
        {
 
866
          delete quick;
 
867
          quick= NULL;
 
868
        }
862
869
      }
863
870
    }
864
871
 
865
872
  free_mem:
866
 
    free_root(&alloc,MYF(0));                   // Return memory & allocator
 
873
    alloc.free_root(MYF(0));                    // Return memory & allocator
867
874
    session->mem_root= param.old_root;
868
875
    session->no_errors=0;
869
876
  }
879
886
  Get best plan for a optimizer::SEL_IMERGE disjunctive expression.
880
887
  SYNOPSIS
881
888
    get_best_disjunct_quick()
 
889
      session
882
890
      param     Parameter from check_quick_select function
883
891
      imerge    Expression to use
884
892
      read_time Don't create scans with cost > read_time
941
949
*/
942
950
 
943
951
static
944
 
optimizer::TableReadPlan *get_best_disjunct_quick(optimizer::Parameter *param,
 
952
optimizer::TableReadPlan *get_best_disjunct_quick(Session *session,
 
953
                                                  optimizer::Parameter *param,
945
954
                                                  optimizer::SEL_IMERGE *imerge,
946
955
                                                  double read_time)
947
956
{
965
974
  ha_rows roru_total_records;
966
975
  double roru_intersect_part= 1.0;
967
976
 
968
 
  if (! (range_scans= (optimizer::RangeReadPlan**)alloc_root(param->mem_root,
969
 
                                                             sizeof(optimizer::RangeReadPlan*)*
970
 
                                                             n_child_scans)))
 
977
  if (! (range_scans= (optimizer::RangeReadPlan**)param->mem_root->alloc_root(sizeof(optimizer::RangeReadPlan*)* n_child_scans)))
 
978
  {
971
979
    return NULL;
 
980
  }
 
981
 
972
982
  /*
973
983
    Collect best 'range' scan for each of disjuncts, and, while doing so,
974
984
    analyze possibility of ROR scans. Also calculate some values needed by
978
988
       ptree != imerge->trees_next;
979
989
       ptree++, cur_child++)
980
990
  {
981
 
    if (!(*cur_child= get_key_scans_params(param, *ptree, true, false, read_time)))
 
991
    if (!(*cur_child= get_key_scans_params(session, param, *ptree, true, false, read_time)))
982
992
    {
983
993
      /*
984
994
        One of index scans in this index_merge is more expensive than entire
995
1005
    all_scans_ror_able &= ((*ptree)->n_ror_scans > 0);
996
1006
    all_scans_rors &= (*cur_child)->is_ror;
997
1007
    if (pk_is_clustered &&
998
 
        param->real_keynr[(*cur_child)->getKeyIndex()] ==
999
 
        param->table->s->primary_key)
 
1008
        param->real_keynr[(*cur_child)->key_idx] ==
 
1009
        param->table->getShare()->getPrimaryKey())
1000
1010
    {
1001
1011
      cpk_scan= cur_child;
1002
1012
      cpk_scan_records= (*cur_child)->records;
1031
1041
  /* Calculate cost(rowid_to_row_scan) */
1032
1042
  {
1033
1043
    optimizer::CostVector sweep_cost;
1034
 
    JOIN *join= param->session->lex->select_lex.join;
 
1044
    Join *join= param->session->lex->select_lex.join;
1035
1045
    bool is_interrupted= test(join && join->tables == 1);
1036
1046
    get_sweep_read_cost(param->table, non_cpk_scan_records, is_interrupted,
1037
1047
                        &sweep_cost);
1047
1057
                                    param->session->variables.sortbuff_size);
1048
1058
  if (param->imerge_cost_buff_size < unique_calc_buff_size)
1049
1059
  {
1050
 
    if (!(param->imerge_cost_buff= (uint*)alloc_root(param->mem_root,
1051
 
                                                     unique_calc_buff_size)))
 
1060
    if (!(param->imerge_cost_buff= (uint*)param->mem_root->alloc_root(unique_calc_buff_size)))
 
1061
    {
1052
1062
      return NULL;
 
1063
    }
 
1064
 
1053
1065
    param->imerge_cost_buff_size= unique_calc_buff_size;
1054
1066
  }
1055
1067
 
1078
1090
  /* Ok, it is possible to build a ROR-union, try it. */
1079
1091
  bool dummy;
1080
1092
  if (! (roru_read_plans=
1081
 
          (optimizer::TableReadPlan **) alloc_root(param->mem_root,
1082
 
                                                   sizeof(optimizer::TableReadPlan*)*
1083
 
                                                   n_child_scans)))
 
1093
          (optimizer::TableReadPlan **) param->mem_root->alloc_root(sizeof(optimizer::TableReadPlan*) * n_child_scans)))
 
1094
  {
1084
1095
    return imerge_trp;
 
1096
  }
1085
1097
skip_to_ror_scan:
1086
1098
  roru_index_costs= 0.0;
1087
1099
  roru_total_records= 0;
1103
1115
    {
1104
1116
      /* Ok, we have index_only cost, now get full rows scan cost */
1105
1117
      cost= param->table->cursor->
1106
 
              read_time(param->real_keynr[(*cur_child)->getKeyIndex()], 1,
 
1118
              read_time(param->real_keynr[(*cur_child)->key_idx], 1,
1107
1119
                        (*cur_child)->records) +
1108
1120
              rows2double((*cur_child)->records) / TIME_FOR_COMPARE;
1109
1121
    }
1121
1133
      roru_index_costs += (*cur_roru_plan)->read_cost;
1122
1134
    }
1123
1135
    else
1124
 
    {
1125
1136
      roru_index_costs +=
1126
 
        ((optimizer::RorIntersectReadPlan *)(*cur_roru_plan))->getCostOfIndexScans();
1127
 
    }
 
1137
        ((optimizer::RorIntersectReadPlan*)(*cur_roru_plan))->index_scan_costs;
1128
1138
    roru_total_records += (*cur_roru_plan)->records;
1129
1139
    roru_intersect_part *= (*cur_roru_plan)->records /
1130
1140
                           param->table->cursor->stats.records;
1149
1159
  double roru_total_cost;
1150
1160
  {
1151
1161
    optimizer::CostVector sweep_cost;
1152
 
    JOIN *join= param->session->lex->select_lex.join;
 
1162
    Join *join= param->session->lex->select_lex.join;
1153
1163
    bool is_interrupted= test(join && join->tables == 1);
1154
1164
    get_sweep_read_cost(param->table, roru_total_records, is_interrupted,
1155
1165
                        &sweep_cost);
1164
1174
  {
1165
1175
    if ((roru= new (param->mem_root) optimizer::RorUnionReadPlan))
1166
1176
    {
1167
 
      roru->merged_scans.assign(roru_read_plans, roru_read_plans + n_child_scans);
 
1177
      roru->first_ror= roru_read_plans;
 
1178
      roru->last_ror= roru_read_plans + n_child_scans;
1168
1179
      roru->read_cost= roru_total_cost;
1169
1180
      roru->records= roru_total_records;
1170
1181
      return roru;
1174
1185
}
1175
1186
 
1176
1187
 
1177
 
typedef struct st_ror_scan_info
1178
 
{
1179
 
  uint32_t      idx;      /* # of used key in param->keys */
1180
 
  uint32_t      keynr;    /* # of used key in table */
1181
 
  ha_rows   records;  /* estimate of # records this scan will return */
1182
 
 
1183
 
  /* Set of intervals over key fields that will be used for row retrieval. */
1184
 
  optimizer::SEL_ARG   *sel_arg;
1185
 
 
1186
 
  /* Fields used in the query and covered by this ROR scan. */
1187
 
  MyBitmap covered_fields;
1188
 
  uint32_t      used_fields_covered; /* # of set bits in covered_fields */
1189
 
  int       key_rec_length; /* length of key record (including rowid) */
1190
 
 
1191
 
  /*
1192
 
    Cost of reading all index records with values in sel_arg intervals set
1193
 
    (assuming there is no need to access full table records)
1194
 
  */
1195
 
  double    index_read_cost;
1196
 
  uint32_t      first_uncovered_field; /* first unused bit in covered_fields */
1197
 
  uint32_t      key_components; /* # of parts in the key */
1198
 
} ROR_SCAN_INFO;
1199
 
 
1200
1188
 
1201
1189
/*
1202
 
  Create ROR_SCAN_INFO* structure with a single ROR scan on index idx using
 
1190
  Create optimizer::RorScanInfo* structure with a single ROR scan on index idx using
1203
1191
  sel_arg set of intervals.
1204
1192
 
1205
1193
  SYNOPSIS
1214
1202
*/
1215
1203
 
1216
1204
static
1217
 
ROR_SCAN_INFO *make_ror_scan(const optimizer::Parameter *param, int idx, optimizer::SEL_ARG *sel_arg)
 
1205
optimizer::RorScanInfo *make_ror_scan(const optimizer::Parameter *param, int idx, optimizer::SEL_ARG *sel_arg)
1218
1206
{
1219
 
  ROR_SCAN_INFO *ror_scan;
1220
 
  my_bitmap_map *bitmap_buf;
 
1207
  optimizer::RorScanInfo *ror_scan= NULL;
1221
1208
 
1222
1209
  uint32_t keynr;
1223
1210
 
1224
 
  if (!(ror_scan= (ROR_SCAN_INFO*)alloc_root(param->mem_root,
1225
 
                                             sizeof(ROR_SCAN_INFO))))
 
1211
  if (!(ror_scan= (optimizer::RorScanInfo*)param->mem_root->alloc_root(sizeof(optimizer::RorScanInfo))))
1226
1212
    return NULL;
1227
1213
 
1228
1214
  ror_scan->idx= idx;
1232
1218
  ror_scan->sel_arg= sel_arg;
1233
1219
  ror_scan->records= param->table->quick_rows[keynr];
1234
1220
 
1235
 
  if (!(bitmap_buf= (my_bitmap_map*) alloc_root(param->mem_root,
1236
 
                                                param->fields_bitmap_size)))
1237
 
    return NULL;
1238
 
 
1239
 
  if (ror_scan->covered_fields.init(bitmap_buf,
1240
 
                                    param->table->s->fields))
1241
 
    return NULL;
1242
 
  ror_scan->covered_fields.clearAll();
1243
 
 
1244
 
  KEY_PART_INFO *key_part= param->table->key_info[keynr].key_part;
1245
 
  KEY_PART_INFO *key_part_end= key_part +
 
1221
  ror_scan->covered_fields_size= param->table->getShare()->sizeFields();
 
1222
  boost::dynamic_bitset<> tmp_bitset(param->table->getShare()->sizeFields());
 
1223
  tmp_bitset.reset();
 
1224
 
 
1225
  KeyPartInfo *key_part= param->table->key_info[keynr].key_part;
 
1226
  KeyPartInfo *key_part_end= key_part +
1246
1227
                               param->table->key_info[keynr].key_parts;
1247
 
  for (;key_part != key_part_end; ++key_part)
 
1228
  for (; key_part != key_part_end; ++key_part)
1248
1229
  {
1249
 
    if (param->needed_fields.isBitSet(key_part->fieldnr-1))
1250
 
      ror_scan->covered_fields.setBit(key_part->fieldnr-1);
 
1230
    if (param->needed_fields.test(key_part->fieldnr-1))
 
1231
      tmp_bitset.set(key_part->fieldnr-1);
1251
1232
  }
1252
1233
  double rows= rows2double(param->table->quick_rows[ror_scan->keynr]);
1253
1234
  ror_scan->index_read_cost=
1254
1235
    param->table->cursor->index_only_read_time(ror_scan->keynr, rows);
1255
 
  return(ror_scan);
 
1236
  ror_scan->covered_fields= tmp_bitset.to_ulong();
 
1237
  return ror_scan;
1256
1238
}
1257
1239
 
1258
1240
 
1259
1241
/*
1260
 
  Compare two ROR_SCAN_INFO** by  E(#records_matched) * key_record_length.
 
1242
  Compare two optimizer::RorScanInfo** by  E(#records_matched) * key_record_length.
1261
1243
  SYNOPSIS
1262
1244
    cmp_ror_scan_info()
1263
1245
      a ptr to first compared value
1269
1251
    1 a > b
1270
1252
*/
1271
1253
 
1272
 
static int cmp_ror_scan_info(ROR_SCAN_INFO** a, ROR_SCAN_INFO** b)
 
1254
static int cmp_ror_scan_info(optimizer::RorScanInfo** a, optimizer::RorScanInfo** b)
1273
1255
{
1274
1256
  double val1= rows2double((*a)->records) * (*a)->key_rec_length;
1275
1257
  double val2= rows2double((*b)->records) * (*b)->key_rec_length;
1276
1258
  return (val1 < val2)? -1: (val1 == val2)? 0 : 1;
1277
1259
}
1278
1260
 
 
1261
 
1279
1262
/*
1280
 
  Compare two ROR_SCAN_INFO** by
 
1263
  Compare two optimizer::RorScanInfo** by
1281
1264
   (#covered fields in F desc,
1282
1265
    #components asc,
1283
1266
    number of first not covered component asc)
1293
1276
    1 a > b
1294
1277
*/
1295
1278
 
1296
 
static int cmp_ror_scan_info_covering(ROR_SCAN_INFO** a, ROR_SCAN_INFO** b)
 
1279
static int cmp_ror_scan_info_covering(optimizer::RorScanInfo** a, optimizer::RorScanInfo** b)
1297
1280
{
1298
1281
  if ((*a)->used_fields_covered > (*b)->used_fields_covered)
1299
1282
    return -1;
1310
1293
  return 0;
1311
1294
}
1312
1295
 
1313
 
 
1314
1296
/* Auxiliary structure for incremental ROR-intersection creation */
1315
 
typedef struct
 
1297
typedef struct st_ror_intersect_info
1316
1298
{
 
1299
  st_ror_intersect_info()
 
1300
    :
 
1301
      param(NULL),
 
1302
      covered_fields(),
 
1303
      out_rows(0.0),
 
1304
      is_covering(false),
 
1305
      index_records(0),
 
1306
      index_scan_costs(0.0),
 
1307
      total_cost(0.0)
 
1308
  {}
 
1309
 
 
1310
  st_ror_intersect_info(const optimizer::Parameter *in_param)
 
1311
    :
 
1312
      param(in_param),
 
1313
      covered_fields(in_param->table->getShare()->sizeFields()),
 
1314
      out_rows(in_param->table->cursor->stats.records),
 
1315
      is_covering(false),
 
1316
      index_records(0),
 
1317
      index_scan_costs(0.0),
 
1318
      total_cost(0.0)
 
1319
  {
 
1320
    covered_fields.reset();
 
1321
  }
 
1322
 
1317
1323
  const optimizer::Parameter *param;
1318
 
  MyBitmap covered_fields; /* union of fields covered by all scans */
 
1324
  boost::dynamic_bitset<> covered_fields; /* union of fields covered by all scans */
1319
1325
  /*
1320
1326
    Fraction of table records that satisfies conditions of all scans.
1321
1327
    This is the number of full records that will be retrieved if a
1331
1337
} ROR_INTERSECT_INFO;
1332
1338
 
1333
1339
 
1334
 
/*
1335
 
  Allocate a ROR_INTERSECT_INFO and initialize it to contain zero scans.
1336
 
 
1337
 
  SYNOPSIS
1338
 
    ror_intersect_init()
1339
 
      param         Parameter from test_quick_select
1340
 
 
1341
 
  RETURN
1342
 
    allocated structure
1343
 
    NULL on error
1344
 
*/
1345
 
 
1346
 
static
1347
 
ROR_INTERSECT_INFO* ror_intersect_init(const optimizer::Parameter *param)
1348
 
{
1349
 
  ROR_INTERSECT_INFO *info;
1350
 
  my_bitmap_map* buf;
1351
 
  if (!(info= (ROR_INTERSECT_INFO*)alloc_root(param->mem_root,
1352
 
                                              sizeof(ROR_INTERSECT_INFO))))
1353
 
    return NULL;
1354
 
  info->param= param;
1355
 
  if (!(buf= (my_bitmap_map*) alloc_root(param->mem_root,
1356
 
                                         param->fields_bitmap_size)))
1357
 
    return NULL;
1358
 
  if (info->covered_fields.init(buf, param->table->s->fields))
1359
 
    return NULL;
1360
 
  info->is_covering= false;
1361
 
  info->index_scan_costs= 0.0;
1362
 
  info->index_records= 0;
1363
 
  info->out_rows= (double) param->table->cursor->stats.records;
1364
 
  info->covered_fields.clearAll();
1365
 
  return info;
1366
 
}
1367
 
 
1368
1340
static void ror_intersect_cpy(ROR_INTERSECT_INFO *dst,
1369
1341
                              const ROR_INTERSECT_INFO *src)
1370
1342
{
1469
1441
*/
1470
1442
 
1471
1443
static double ror_scan_selectivity(const ROR_INTERSECT_INFO *info,
1472
 
                                   const ROR_SCAN_INFO *scan)
 
1444
                                   const optimizer::RorScanInfo *scan)
1473
1445
{
1474
1446
  double selectivity_mult= 1.0;
1475
 
  KEY_PART_INFO *key_part= info->param->table->key_info[scan->keynr].key_part;
 
1447
  KeyPartInfo *key_part= info->param->table->key_info[scan->keynr].key_part;
1476
1448
  unsigned char key_val[MAX_KEY_LENGTH+MAX_FIELD_WIDTH]; /* key values tuple */
1477
1449
  unsigned char *key_ptr= key_val;
1478
1450
  optimizer::SEL_ARG *sel_arg= NULL;
1479
1451
  optimizer::SEL_ARG *tuple_arg= NULL;
1480
1452
  key_part_map keypart_map= 0;
1481
1453
  bool cur_covered;
1482
 
  bool prev_covered= test(info->covered_fields.isBitSet(key_part->fieldnr-1));
 
1454
  bool prev_covered= test(info->covered_fields.test(key_part->fieldnr-1));
1483
1455
  key_range min_range;
1484
1456
  key_range max_range;
1485
1457
  min_range.key= key_val;
1492
1464
       sel_arg= sel_arg->next_key_part)
1493
1465
  {
1494
1466
    cur_covered=
1495
 
      test(info->covered_fields.isBitSet(key_part[sel_arg->part].fieldnr-1));
 
1467
      test(info->covered_fields.test(key_part[sel_arg->part].fieldnr-1));
1496
1468
    if (cur_covered != prev_covered)
1497
1469
    {
1498
1470
      /* create (part1val, ..., part{n-1}val) tuple. */
1577
1549
*/
1578
1550
 
1579
1551
static bool ror_intersect_add(ROR_INTERSECT_INFO *info,
1580
 
                              ROR_SCAN_INFO* ror_scan, bool is_cpk_scan)
 
1552
                              optimizer::RorScanInfo* ror_scan, bool is_cpk_scan)
1581
1553
{
1582
1554
  double selectivity_mult= 1.0;
1583
1555
 
1604
1576
  {
1605
1577
    info->index_records += info->param->table->quick_rows[ror_scan->keynr];
1606
1578
    info->index_scan_costs += ror_scan->index_read_cost;
1607
 
    bitmap_union(&info->covered_fields, &ror_scan->covered_fields);
1608
 
    if (!info->is_covering && bitmap_is_subset(&info->param->needed_fields,
1609
 
                                               &info->covered_fields))
 
1579
    boost::dynamic_bitset<> tmp_bitset= ror_scan->bitsToBitset();
 
1580
    info->covered_fields|= tmp_bitset;
 
1581
    if (! info->is_covering && info->param->needed_fields.is_subset_of(info->covered_fields))
1610
1582
    {
1611
1583
      info->is_covering= true;
1612
1584
    }
1613
1585
  }
1614
1586
 
1615
1587
  info->total_cost= info->index_scan_costs;
1616
 
  if (!info->is_covering)
 
1588
  if (! info->is_covering)
1617
1589
  {
1618
1590
    optimizer::CostVector sweep_cost;
1619
 
    JOIN *join= info->param->session->lex->select_lex.join;
 
1591
    Join *join= info->param->session->lex->select_lex.join;
1620
1592
    bool is_interrupted= test(join && join->tables == 1);
1621
1593
    get_sweep_read_cost(info->param->table, double2rows(info->out_rows),
1622
1594
                        is_interrupted, &sweep_cost);
1627
1599
 
1628
1600
 
1629
1601
/*
 
1602
  Get best covering ROR-intersection.
 
1603
  SYNOPSIS
 
1604
    get_best_covering_ror_intersect()
 
1605
      param     Parameter from test_quick_select function.
 
1606
      tree      optimizer::SEL_TREE with sets of intervals for different keys.
 
1607
      read_time Don't return table read plans with cost > read_time.
 
1608
 
 
1609
  RETURN
 
1610
    Best covering ROR-intersection plan
 
1611
    NULL if no plan found.
 
1612
 
 
1613
  NOTES
 
1614
    get_best_ror_intersect must be called for a tree before calling this
 
1615
    function for it.
 
1616
    This function invalidates tree->ror_scans member values.
 
1617
 
 
1618
  The following approximate algorithm is used:
 
1619
    I=set of all covering indexes
 
1620
    F=set of all fields to cover
 
1621
    S={}
 
1622
 
 
1623
    do
 
1624
    {
 
1625
      Order I by (#covered fields in F desc,
 
1626
                  #components asc,
 
1627
                  number of first not covered component asc);
 
1628
      F=F-covered by first(I);
 
1629
      S=S+first(I);
 
1630
      I=I-first(I);
 
1631
    } while F is not empty.
 
1632
*/
 
1633
 
 
1634
static
 
1635
optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
 
1636
                                                            optimizer::SEL_TREE *tree,
 
1637
                                                            double read_time)
 
1638
{
 
1639
  optimizer::RorScanInfo **ror_scan_mark;
 
1640
  optimizer::RorScanInfo **ror_scans_end= tree->ror_scans_end;
 
1641
 
 
1642
  for (optimizer::RorScanInfo **scan= tree->ror_scans; scan != ror_scans_end; ++scan)
 
1643
    (*scan)->key_components=
 
1644
      param->table->key_info[(*scan)->keynr].key_parts;
 
1645
 
 
1646
  /*
 
1647
    Run covering-ROR-search algorithm.
 
1648
    Assume set I is [ror_scan .. ror_scans_end)
 
1649
  */
 
1650
 
 
1651
  /*I=set of all covering indexes */
 
1652
  ror_scan_mark= tree->ror_scans;
 
1653
 
 
1654
  boost::dynamic_bitset<> *covered_fields= &param->tmp_covered_fields;
 
1655
  if (covered_fields->empty())
 
1656
  {
 
1657
    covered_fields->resize(param->table->getShare()->sizeFields());
 
1658
  }
 
1659
  covered_fields->reset();
 
1660
 
 
1661
  double total_cost= 0.0f;
 
1662
  ha_rows records=0;
 
1663
  bool all_covered;
 
1664
 
 
1665
  do
 
1666
  {
 
1667
    /*
 
1668
      Update changed sorting info:
 
1669
        #covered fields,
 
1670
        number of first not covered component
 
1671
      Calculate and save these values for each of remaining scans.
 
1672
    */
 
1673
    for (optimizer::RorScanInfo **scan= ror_scan_mark; scan != ror_scans_end; ++scan)
 
1674
    {
 
1675
      /* subtract one bitset from the other */
 
1676
      (*scan)->subtractBitset(*covered_fields);
 
1677
      (*scan)->used_fields_covered=
 
1678
        (*scan)->getBitCount();
 
1679
      (*scan)->first_uncovered_field= (*scan)->findFirstNotSet();
 
1680
    }
 
1681
 
 
1682
    internal::my_qsort(ror_scan_mark, ror_scans_end-ror_scan_mark,
 
1683
                       sizeof(optimizer::RorScanInfo*),
 
1684
                       (qsort_cmp)cmp_ror_scan_info_covering);
 
1685
 
 
1686
    /* I=I-first(I) */
 
1687
    total_cost += (*ror_scan_mark)->index_read_cost;
 
1688
    records += (*ror_scan_mark)->records;
 
1689
    if (total_cost > read_time)
 
1690
      return NULL;
 
1691
    /* F=F-covered by first(I) */
 
1692
    boost::dynamic_bitset<> tmp_bitset= (*ror_scan_mark)->bitsToBitset();
 
1693
    *covered_fields|= tmp_bitset;
 
1694
    all_covered= param->needed_fields.is_subset_of(*covered_fields);
 
1695
  } while ((++ror_scan_mark < ror_scans_end) && ! all_covered);
 
1696
 
 
1697
  if (!all_covered || (ror_scan_mark - tree->ror_scans) == 1)
 
1698
    return NULL;
 
1699
 
 
1700
  /*
 
1701
    Ok, [tree->ror_scans .. ror_scan) holds covering index_intersection with
 
1702
    cost total_cost.
 
1703
  */
 
1704
  /* Add priority queue use cost. */
 
1705
  total_cost += rows2double(records)*
 
1706
                log((double)(ror_scan_mark - tree->ror_scans)) /
 
1707
                (TIME_FOR_COMPARE_ROWID * M_LN2);
 
1708
 
 
1709
  if (total_cost > read_time)
 
1710
    return NULL;
 
1711
 
 
1712
  optimizer::RorIntersectReadPlan *trp= NULL;
 
1713
  if (! (trp= new (param->mem_root) optimizer::RorIntersectReadPlan))
 
1714
  {
 
1715
    return trp;
 
1716
  }
 
1717
 
 
1718
  uint32_t best_num= (ror_scan_mark - tree->ror_scans);
 
1719
  if (!(trp->first_scan= (optimizer::RorScanInfo**)param->mem_root->alloc_root(sizeof(optimizer::RorScanInfo*)* best_num)))
 
1720
    return NULL;
 
1721
  memcpy(trp->first_scan, tree->ror_scans, best_num*sizeof(optimizer::RorScanInfo*));
 
1722
  trp->last_scan=  trp->first_scan + best_num;
 
1723
  trp->is_covering= true;
 
1724
  trp->read_cost= total_cost;
 
1725
  trp->records= records;
 
1726
  trp->cpk_scan= NULL;
 
1727
  set_if_smaller(param->table->quick_condition_rows, records);
 
1728
 
 
1729
  return(trp);
 
1730
}
 
1731
 
 
1732
 
 
1733
/*
1630
1734
  Get best ROR-intersection plan using non-covering ROR-intersection search
1631
1735
  algorithm. The returned plan may be covering.
1632
1736
 
1703
1807
    return NULL;
1704
1808
 
1705
1809
  /*
1706
 
    Step1: Collect ROR-able SEL_ARGs and create ROR_SCAN_INFO for each of
 
1810
    Step1: Collect ROR-able SEL_ARGs and create optimizer::RorScanInfo for each of
1707
1811
    them. Also find and save clustered PK scan if there is one.
1708
1812
  */
1709
 
  ROR_SCAN_INFO **cur_ror_scan= NULL;
1710
 
  ROR_SCAN_INFO *cpk_scan= NULL;
 
1813
  optimizer::RorScanInfo **cur_ror_scan= NULL;
 
1814
  optimizer::RorScanInfo *cpk_scan= NULL;
1711
1815
  uint32_t cpk_no= 0;
1712
1816
  bool cpk_scan_used= false;
1713
1817
 
1714
 
  if (! (tree->ror_scans= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
1715
 
                                                      sizeof(ROR_SCAN_INFO*)*
1716
 
                                                      param->keys)))
 
1818
  if (! (tree->ror_scans= (optimizer::RorScanInfo**)param->mem_root->alloc_root(sizeof(optimizer::RorScanInfo*)* param->keys)))
 
1819
  {
1717
1820
    return NULL;
 
1821
  }
1718
1822
  cpk_no= ((param->table->cursor->primary_key_is_clustered()) ?
1719
 
           param->table->s->primary_key : MAX_KEY);
 
1823
           param->table->getShare()->getPrimaryKey() : MAX_KEY);
1720
1824
 
1721
1825
  for (idx= 0, cur_ror_scan= tree->ror_scans; idx < param->keys; idx++)
1722
1826
  {
1723
 
    ROR_SCAN_INFO *scan;
 
1827
    optimizer::RorScanInfo *scan;
1724
1828
    if (! tree->ror_scans_map.test(idx))
1725
1829
      continue;
1726
 
    if (!(scan= make_ror_scan(param, idx, tree->keys[idx])))
 
1830
    if (! (scan= make_ror_scan(param, idx, tree->keys[idx])))
1727
1831
      return NULL;
1728
1832
    if (param->real_keynr[idx] == cpk_no)
1729
1833
    {
1737
1841
  tree->ror_scans_end= cur_ror_scan;
1738
1842
  /*
1739
1843
    Ok, [ror_scans, ror_scans_end) is array of ptrs to initialized
1740
 
    ROR_SCAN_INFO's.
 
1844
    optimizer::RorScanInfo's.
1741
1845
    Step 2: Get best ROR-intersection using an approximate algorithm.
1742
1846
  */
1743
 
  internal::my_qsort(tree->ror_scans, tree->n_ror_scans, sizeof(ROR_SCAN_INFO*),
 
1847
  internal::my_qsort(tree->ror_scans, tree->n_ror_scans, sizeof(optimizer::RorScanInfo*),
1744
1848
                     (qsort_cmp)cmp_ror_scan_info);
1745
1849
 
1746
 
  ROR_SCAN_INFO **intersect_scans= NULL; /* ROR scans used in index intersection */
1747
 
  ROR_SCAN_INFO **intersect_scans_end= NULL;
1748
 
  if (! (intersect_scans= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
1749
 
                                                      sizeof(ROR_SCAN_INFO*)*
1750
 
                                                      tree->n_ror_scans)))
 
1850
  optimizer::RorScanInfo **intersect_scans= NULL; /* ROR scans used in index intersection */
 
1851
  optimizer::RorScanInfo **intersect_scans_end= NULL;
 
1852
  if (! (intersect_scans= (optimizer::RorScanInfo**)param->mem_root->alloc_root(sizeof(optimizer::RorScanInfo*) * tree->n_ror_scans)))
1751
1853
    return NULL;
1752
1854
  intersect_scans_end= intersect_scans;
1753
1855
 
1754
1856
  /* Create and incrementally update ROR intersection. */
1755
 
  ROR_INTERSECT_INFO *intersect= NULL;
1756
 
  ROR_INTERSECT_INFO *intersect_best= NULL;
1757
 
  if (! (intersect= ror_intersect_init(param)) ||
1758
 
      ! (intersect_best= ror_intersect_init(param)))
1759
 
    return NULL;
 
1857
  ROR_INTERSECT_INFO intersect(param);
 
1858
  ROR_INTERSECT_INFO intersect_best(param);
1760
1859
 
1761
1860
  /* [intersect_scans,intersect_scans_best) will hold the best intersection */
1762
 
  ROR_SCAN_INFO **intersect_scans_best= NULL;
 
1861
  optimizer::RorScanInfo **intersect_scans_best= NULL;
1763
1862
  cur_ror_scan= tree->ror_scans;
1764
1863
  intersect_scans_best= intersect_scans;
1765
 
  while (cur_ror_scan != tree->ror_scans_end && !intersect->is_covering)
 
1864
  while (cur_ror_scan != tree->ror_scans_end && ! intersect.is_covering)
1766
1865
  {
1767
1866
    /* S= S + first(R);  R= R - first(R); */
1768
 
    if (!ror_intersect_add(intersect, *cur_ror_scan, false))
 
1867
    if (! ror_intersect_add(&intersect, *cur_ror_scan, false))
1769
1868
    {
1770
1869
      cur_ror_scan++;
1771
1870
      continue;
1773
1872
 
1774
1873
    *(intersect_scans_end++)= *(cur_ror_scan++);
1775
1874
 
1776
 
    if (intersect->total_cost < min_cost)
 
1875
    if (intersect.total_cost < min_cost)
1777
1876
    {
1778
1877
      /* Local minimum found, save it */
1779
 
      ror_intersect_cpy(intersect_best, intersect);
 
1878
      ror_intersect_cpy(&intersect_best, &intersect);
1780
1879
      intersect_scans_best= intersect_scans_end;
1781
 
      min_cost = intersect->total_cost;
 
1880
      min_cost = intersect.total_cost;
1782
1881
    }
1783
1882
  }
1784
1883
 
1787
1886
    return NULL;
1788
1887
  }
1789
1888
 
1790
 
  *are_all_covering= intersect->is_covering;
 
1889
  *are_all_covering= intersect.is_covering;
1791
1890
  uint32_t best_num= intersect_scans_best - intersect_scans;
1792
 
  ror_intersect_cpy(intersect, intersect_best);
 
1891
  ror_intersect_cpy(&intersect, &intersect_best);
1793
1892
 
1794
1893
  /*
1795
1894
    Ok, found the best ROR-intersection of non-CPK key scans.
1796
1895
    Check if we should add a CPK scan. If the obtained ROR-intersection is
1797
1896
    covering, it doesn't make sense to add CPK scan.
1798
1897
  */
1799
 
  if (cpk_scan && !intersect->is_covering)
 
1898
  if (cpk_scan && ! intersect.is_covering)
1800
1899
  {
1801
 
    if (ror_intersect_add(intersect, cpk_scan, true) &&
1802
 
        (intersect->total_cost < min_cost))
 
1900
    if (ror_intersect_add(&intersect, cpk_scan, true) &&
 
1901
        (intersect.total_cost < min_cost))
1803
1902
    {
1804
1903
      cpk_scan_used= true;
1805
1904
      intersect_best= intersect; //just set pointer here
1813
1912
    if (! (trp= new (param->mem_root) optimizer::RorIntersectReadPlan))
1814
1913
      return trp;
1815
1914
 
1816
 
    trp->ror_range_scans.assign(intersect_scans, intersect_scans + best_num);
1817
 
    trp->setRowRetrievalNecessary(intersect_best->is_covering);
1818
 
    trp->read_cost= intersect_best->total_cost;
 
1915
    if (! (trp->first_scan=
 
1916
           (optimizer::RorScanInfo**)param->mem_root->alloc_root(sizeof(optimizer::RorScanInfo*)*best_num)))
 
1917
      return NULL;
 
1918
    memcpy(trp->first_scan, intersect_scans, best_num*sizeof(optimizer::RorScanInfo*));
 
1919
    trp->last_scan=  trp->first_scan + best_num;
 
1920
    trp->is_covering= intersect_best.is_covering;
 
1921
    trp->read_cost= intersect_best.total_cost;
1819
1922
    /* Prevent divisons by zero */
1820
 
    ha_rows best_rows = double2rows(intersect_best->out_rows);
 
1923
    ha_rows best_rows = double2rows(intersect_best.out_rows);
1821
1924
    if (! best_rows)
1822
1925
      best_rows= 1;
1823
1926
    set_if_smaller(param->table->quick_condition_rows, best_rows);
1824
1927
    trp->records= best_rows;
1825
 
    trp->setCostOfIndexScans(intersect_best->index_scan_costs);
 
1928
    trp->index_scan_costs= intersect_best.index_scan_costs;
1826
1929
    trp->cpk_scan= cpk_scan_used? cpk_scan: NULL;
1827
1930
  }
1828
1931
  return trp;
1830
1933
 
1831
1934
 
1832
1935
/*
1833
 
  Get best covering ROR-intersection.
1834
 
  SYNOPSIS
1835
 
    get_best_covering_ror_intersect()
1836
 
      param     Parameter from test_quick_select function.
1837
 
      tree      optimizer::SEL_TREE with sets of intervals for different keys.
1838
 
      read_time Don't return table read plans with cost > read_time.
1839
 
 
1840
 
  RETURN
1841
 
    Best covering ROR-intersection plan
1842
 
    NULL if no plan found.
1843
 
 
1844
 
  NOTES
1845
 
    get_best_ror_intersect must be called for a tree before calling this
1846
 
    function for it.
1847
 
    This function invalidates tree->ror_scans member values.
1848
 
 
1849
 
  The following approximate algorithm is used:
1850
 
    I=set of all covering indexes
1851
 
    F=set of all fields to cover
1852
 
    S={}
1853
 
 
1854
 
    do
1855
 
    {
1856
 
      Order I by (#covered fields in F desc,
1857
 
                  #components asc,
1858
 
                  number of first not covered component asc);
1859
 
      F=F-covered by first(I);
1860
 
      S=S+first(I);
1861
 
      I=I-first(I);
1862
 
    } while F is not empty.
1863
 
*/
1864
 
 
1865
 
static
1866
 
optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
1867
 
                                                            optimizer::SEL_TREE *tree,
1868
 
                                                            double read_time)
1869
 
{
1870
 
  ROR_SCAN_INFO **ror_scan_mark;
1871
 
  ROR_SCAN_INFO **ror_scans_end= tree->ror_scans_end;
1872
 
 
1873
 
  for (ROR_SCAN_INFO **scan= tree->ror_scans; scan != ror_scans_end; ++scan)
1874
 
    (*scan)->key_components=
1875
 
      param->table->key_info[(*scan)->keynr].key_parts;
1876
 
 
1877
 
  /*
1878
 
    Run covering-ROR-search algorithm.
1879
 
    Assume set I is [ror_scan .. ror_scans_end)
1880
 
  */
1881
 
 
1882
 
  /*I=set of all covering indexes */
1883
 
  ror_scan_mark= tree->ror_scans;
1884
 
 
1885
 
  MyBitmap *covered_fields= &param->tmp_covered_fields;
1886
 
  if (! covered_fields->getBitmap())
1887
 
  {
1888
 
    my_bitmap_map *tmp_bitmap= (my_bitmap_map*)alloc_root(param->mem_root,
1889
 
                                               param->fields_bitmap_size);
1890
 
    covered_fields->setBitmap(tmp_bitmap);
1891
 
  }
1892
 
  if (! covered_fields->getBitmap() ||
1893
 
      covered_fields->init(covered_fields->getBitmap(),
1894
 
                           param->table->s->fields))
1895
 
    return 0;
1896
 
  covered_fields->clearAll();
1897
 
 
1898
 
  double total_cost= 0.0f;
1899
 
  ha_rows records=0;
1900
 
  bool all_covered;
1901
 
 
1902
 
  do
1903
 
  {
1904
 
    /*
1905
 
      Update changed sorting info:
1906
 
        #covered fields,
1907
 
        number of first not covered component
1908
 
      Calculate and save these values for each of remaining scans.
1909
 
    */
1910
 
    for (ROR_SCAN_INFO **scan= ror_scan_mark; scan != ror_scans_end; ++scan)
1911
 
    {
1912
 
      bitmap_subtract(&(*scan)->covered_fields, covered_fields);
1913
 
      (*scan)->used_fields_covered=
1914
 
        (*scan)->covered_fields.getBitsSet();
1915
 
      (*scan)->first_uncovered_field=
1916
 
        (*scan)->covered_fields.getFirst();
1917
 
    }
1918
 
 
1919
 
    internal::my_qsort(ror_scan_mark, ror_scans_end-ror_scan_mark,
1920
 
                       sizeof(ROR_SCAN_INFO*),
1921
 
                       (qsort_cmp)cmp_ror_scan_info_covering);
1922
 
 
1923
 
    /* I=I-first(I) */
1924
 
    total_cost += (*ror_scan_mark)->index_read_cost;
1925
 
    records += (*ror_scan_mark)->records;
1926
 
    if (total_cost > read_time)
1927
 
      return NULL;
1928
 
    /* F=F-covered by first(I) */
1929
 
    bitmap_union(covered_fields, &(*ror_scan_mark)->covered_fields);
1930
 
    all_covered= bitmap_is_subset(&param->needed_fields, covered_fields);
1931
 
  } while ((++ror_scan_mark < ror_scans_end) && !all_covered);
1932
 
 
1933
 
  if (!all_covered || (ror_scan_mark - tree->ror_scans) == 1)
1934
 
    return NULL;
1935
 
 
1936
 
  /*
1937
 
    Ok, [tree->ror_scans .. ror_scan) holds covering index_intersection with
1938
 
    cost total_cost.
1939
 
  */
1940
 
  /* Add priority queue use cost. */
1941
 
  total_cost += rows2double(records)*
1942
 
                log((double)(ror_scan_mark - tree->ror_scans)) /
1943
 
                (TIME_FOR_COMPARE_ROWID * M_LN2);
1944
 
 
1945
 
  if (total_cost > read_time)
1946
 
    return NULL;
1947
 
 
1948
 
  optimizer::RorIntersectReadPlan *trp= NULL;
1949
 
  if (! (trp= new (param->mem_root) optimizer::RorIntersectReadPlan))
1950
 
  {
1951
 
    return trp;
1952
 
  }
1953
 
 
1954
 
  uint32_t best_num= (ror_scan_mark - tree->ror_scans);
1955
 
  trp->ror_range_scans.assign(tree->ror_scans, tree->ror_scans + best_num);
1956
 
  trp->setRowRetrievalNecessary(true);
1957
 
  trp->read_cost= total_cost;
1958
 
  trp->records= records;
1959
 
  trp->cpk_scan= NULL;
1960
 
  set_if_smaller(param->table->quick_condition_rows, records);
1961
 
 
1962
 
  return(trp);
1963
 
}
1964
 
 
1965
 
 
1966
 
/*
1967
1936
  Get best "range" table read plan for given optimizer::SEL_TREE, also update some info
1968
1937
 
1969
1938
  SYNOPSIS
1970
1939
    get_key_scans_params()
 
1940
      session
1971
1941
      param                    Parameters from test_quick_select
1972
1942
      tree                     Make range select for this optimizer::SEL_TREE
1973
1943
      index_read_must_be_used  true <=> assume 'index only' option will be set
1989
1959
    NULL if no plan found or error occurred
1990
1960
*/
1991
1961
 
1992
 
static optimizer::RangeReadPlan *get_key_scans_params(optimizer::Parameter *param,
 
1962
static optimizer::RangeReadPlan *get_key_scans_params(Session *session,
 
1963
                                                      optimizer::Parameter *param,
1993
1964
                                                      optimizer::SEL_TREE *tree,
1994
1965
                                                      bool index_read_must_be_used,
1995
1966
                                                      bool update_tbl_stats,
2026
1997
      bool read_index_only= index_read_must_be_used ||
2027
1998
                            param->table->covering_keys.test(keynr);
2028
1999
 
2029
 
      found_records= check_quick_select(param, idx, read_index_only, *key,
 
2000
      found_records= check_quick_select(session, param, idx, read_index_only, *key,
2030
2001
                                        update_tbl_stats, &mrr_flags,
2031
2002
                                        &buf_size, &cost);
2032
2003
      found_read_time= cost.total_cost();
2055
2026
      read_plan->records= best_records;
2056
2027
      read_plan->is_ror= tree->ror_scans_map.test(idx);
2057
2028
      read_plan->read_cost= read_time;
2058
 
      read_plan->setMRRBufferSize(best_buf_size);
 
2029
      read_plan->mrr_buf_size= best_buf_size;
2059
2030
    }
2060
2031
  }
2061
2032
 
2106
2077
                                                parent_alloc)))
2107
2078
  {
2108
2079
    alloc= parent_alloc ? parent_alloc : &quick_intersect->alloc;
2109
 
    for (vector<struct st_ror_scan_info *>::iterator it= ror_range_scans.begin();
2110
 
         it != ror_range_scans.end();
2111
 
         ++it)
 
2080
    for (; first_scan != last_scan; ++first_scan)
2112
2081
    {
2113
2082
      if (! (quick= optimizer::get_quick_select(param,
2114
 
                                                (*it)->idx,
2115
 
                                                (*it)->sel_arg,
 
2083
                                                (*first_scan)->idx,
 
2084
                                                (*first_scan)->sel_arg,
2116
2085
                                                HA_MRR_USE_DEFAULT_IMPL | HA_MRR_SORTED,
2117
2086
                                                0,
2118
2087
                                                alloc)) ||
2147
2116
optimizer::QuickSelectInterface *optimizer::RorUnionReadPlan::make_quick(optimizer::Parameter *param, bool, memory::Root *)
2148
2117
{
2149
2118
  optimizer::QuickRorUnionSelect *quick_roru= NULL;
 
2119
  optimizer::TableReadPlan **scan= NULL;
2150
2120
  optimizer::QuickSelectInterface *quick= NULL;
2151
2121
  /*
2152
2122
    It is impossible to construct a ROR-union that will not retrieve full
2154
2124
  */
2155
2125
  if ((quick_roru= new optimizer::QuickRorUnionSelect(param->session, param->table)))
2156
2126
  {
2157
 
    for (vector<optimizer::TableReadPlan *>::iterator it= merged_scans.begin();
2158
 
         it != merged_scans.end();
2159
 
         ++it)
 
2127
    for (scan= first_ror; scan != last_ror; scan++)
2160
2128
    {
2161
 
      if (! (quick= (*it)->make_quick(param, false, &quick_roru->alloc)) ||
 
2129
      if (! (quick= (*scan)->make_quick(param, false, &quick_roru->alloc)) ||
2162
2130
          quick_roru->push_quick_back(quick))
2163
2131
      {
2164
2132
        return NULL;
2560
2528
  field->setWriteSet();
2561
2529
 
2562
2530
  Item_result cmp_type= field->cmp_type();
2563
 
  if (!((ref_tables | field->table->map) & param_comp))
 
2531
  if (!((ref_tables | field->getTable()->map) & param_comp))
2564
2532
    ftree= get_func_mm_tree(param, cond_func, field, value, cmp_type, inv);
2565
2533
  Item_equal *item_equal= field_item->item_equal;
2566
2534
  if (item_equal)
2574
2542
 
2575
2543
      if (field->eq(f))
2576
2544
        continue;
2577
 
      if (!((ref_tables | f->table->map) & param_comp))
 
2545
      if (!((ref_tables | f->getTable()->map) & param_comp))
2578
2546
      {
2579
2547
        tree= get_func_mm_tree(param, cond_func, f, value, cmp_type, inv);
2580
2548
        ftree= !ftree ? tree : tree_and(param, ftree, tree);
2632
2600
    }
2633
2601
    return(tree);
2634
2602
  }
2635
 
  /* Here when simple cond */
2636
 
  if (cond->const_item())
 
2603
  /* Here when simple cond
 
2604
     There are limits on what kinds of const items we can evaluate, grep for
 
2605
     DontEvaluateMaterializedSubqueryTooEarly.
 
2606
  */
 
2607
  if (cond->const_item()  && !cond->is_expensive())
2637
2608
  {
2638
2609
    /*
2639
2610
      During the cond->val_int() evaluation we can come across a subselect
2725
2696
      field->setWriteSet();
2726
2697
 
2727
2698
      Item_result cmp_type= field->cmp_type();
2728
 
      if (!((ref_tables | field->table->map) & param_comp))
 
2699
      if (!((ref_tables | field->getTable()->map) & param_comp))
2729
2700
      {
2730
2701
        tree= get_mm_parts(param, cond, field, Item_func::EQ_FUNC,
2731
2702
                           value,cmp_type);
2764
2735
                   Item_func::Functype type,
2765
2736
                   Item *value, Item_result)
2766
2737
{
2767
 
  if (field->table != param->table)
 
2738
  if (field->getTable() != param->table)
2768
2739
    return 0;
2769
2740
 
2770
2741
  KEY_PART *key_part = param->key_parts;
2834
2805
  param->session->mem_root= param->old_root;
2835
2806
  if (!value)                                   // IS NULL or IS NOT NULL
2836
2807
  {
2837
 
    if (field->table->maybe_null)               // Can't use a key on this
 
2808
    if (field->getTable()->maybe_null)          // Can't use a key on this
2838
2809
      goto end;
2839
2810
    if (!maybe_null)                            // Not null field
2840
2811
    {
2919
2890
    {
2920
2891
      if (unlikely(length < field_length))
2921
2892
      {
2922
 
        /*
2923
 
          This can only happen in a table created with UNIREG where one key
2924
 
          overlaps many fields
2925
 
        */
2926
 
        length= field_length;
 
2893
        /*
 
2894
          This can only happen in a table created with UNIREG where one key
 
2895
          overlaps many fields
 
2896
        */
 
2897
        length= field_length;
2927
2898
      }
2928
2899
      else
2929
 
        field_length= length;
 
2900
        field_length= length;
2930
2901
    }
2931
2902
    length+=offset;
2932
 
    if (!(min_str= (unsigned char*) alloc_root(alloc, length*2)))
 
2903
    if (!(min_str= (unsigned char*) alloc->alloc_root(length*2)))
 
2904
    {
2933
2905
      goto end;
 
2906
    }
2934
2907
 
2935
2908
    max_str=min_str+length;
2936
2909
    if (maybe_null)
3149
3122
    tree= &optimizer::null_element;                        // cmp with NULL is never true
3150
3123
    goto end;
3151
3124
  }
3152
 
  str= (unsigned char*) alloc_root(alloc, key_part->store_length+1);
 
3125
 
 
3126
  /*
 
3127
    Any predicate except "<=>"(null-safe equality operator) involving NULL as a
 
3128
    constant is always FALSE
 
3129
    Put IMPOSSIBLE Tree(null_element) here.
 
3130
  */  
 
3131
  if (type != Item_func::EQUAL_FUNC && field->is_real_null())
 
3132
  {
 
3133
    tree= &optimizer::null_element;
 
3134
    goto end;
 
3135
  }
 
3136
 
 
3137
  str= (unsigned char*) alloc->alloc_root(key_part->store_length+1);
3153
3138
  if (!str)
3154
3139
    goto end;
3155
3140
  if (maybe_null)
3749
3734
  /* Ok got a tuple */
3750
3735
  RANGE_SEQ_ENTRY *cur= &seq->stack[seq->i];
3751
3736
 
3752
 
  range->ptr= (char*)(int)(key_tree->part);
 
3737
  range->ptr= (char*)(size_t)(key_tree->part);
3753
3738
  {
3754
3739
    range->range_flag= cur->min_key_flag | cur->max_key_flag;
3755
3740
 
3825
3810
*/
3826
3811
 
3827
3812
static
3828
 
ha_rows check_quick_select(optimizer::Parameter *param,
 
3813
ha_rows check_quick_select(Session *session,
 
3814
                           optimizer::Parameter *param,
3829
3815
                           uint32_t idx,
3830
3816
                           bool index_only,
3831
3817
                           optimizer::SEL_ARG *tree,
3866
3852
  bool pk_is_clustered= cursor->primary_key_is_clustered();
3867
3853
  if (index_only &&
3868
3854
      (param->table->index_flags(keynr) & HA_KEYREAD_ONLY) &&
3869
 
      !(pk_is_clustered && keynr == param->table->s->primary_key))
 
3855
      !(pk_is_clustered && keynr == param->table->getShare()->getPrimaryKey()))
3870
3856
     *mrr_flags |= HA_MRR_INDEX_ONLY;
3871
3857
 
3872
 
  if (current_session->lex->sql_command != SQLCOM_SELECT)
 
3858
  if (session->lex->sql_command != SQLCOM_SELECT)
3873
3859
    *mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
3874
3860
 
3875
3861
  *bufsize= param->session->variables.read_rnd_buff_size;
3901
3887
  else
3902
3888
  {
3903
3889
    /* Clustered PK scan is always a ROR scan (TODO: same as above) */
3904
 
    if (param->table->s->primary_key == keynr && pk_is_clustered)
 
3890
    if (param->table->getShare()->getPrimaryKey() == keynr && pk_is_clustered)
3905
3891
      param->is_ror_scan= true;
3906
3892
  }
3907
3893
 
3948
3934
 
3949
3935
static bool is_key_scan_ror(optimizer::Parameter *param, uint32_t keynr, uint8_t nparts)
3950
3936
{
3951
 
  KEY *table_key= param->table->key_info + keynr;
3952
 
  KEY_PART_INFO *key_part= table_key->key_part + nparts;
3953
 
  KEY_PART_INFO *key_part_end= (table_key->key_part +
 
3937
  KeyInfo *table_key= param->table->key_info + keynr;
 
3938
  KeyPartInfo *key_part= table_key->key_part + nparts;
 
3939
  KeyPartInfo *key_part_end= (table_key->key_part +
3954
3940
                                table_key->key_parts);
3955
3941
  uint32_t pk_number;
3956
3942
 
3957
 
  for (KEY_PART_INFO *kp= table_key->key_part; kp < key_part; kp++)
 
3943
  for (KeyPartInfo *kp= table_key->key_part; kp < key_part; kp++)
3958
3944
  {
3959
3945
    uint16_t fieldnr= param->table->key_info[keynr].
3960
3946
                    key_part[kp - table_key->key_part].fieldnr - 1;
3961
 
    if (param->table->field[fieldnr]->key_length() != kp->length)
 
3947
    if (param->table->getField(fieldnr)->key_length() != kp->length)
3962
3948
      return false;
3963
3949
  }
3964
3950
 
3966
3952
    return true;
3967
3953
 
3968
3954
  key_part= table_key->key_part + nparts;
3969
 
  pk_number= param->table->s->primary_key;
 
3955
  pk_number= param->table->getShare()->getPrimaryKey();
3970
3956
  if (!param->table->cursor->primary_key_is_clustered() || pk_number == MAX_KEY)
3971
3957
    return false;
3972
3958
 
3973
 
  KEY_PART_INFO *pk_part= param->table->key_info[pk_number].key_part;
3974
 
  KEY_PART_INFO *pk_part_end= pk_part +
 
3959
  KeyPartInfo *pk_part= param->table->key_info[pk_number].key_part;
 
3960
  KeyPartInfo *pk_part_end= pk_part +
3975
3961
                              param->table->key_info[pk_number].key_parts;
3976
3962
  for (;(key_part!=key_part_end) && (pk_part != pk_part_end);
3977
3963
       ++key_part, ++pk_part)
3992
3978
                            uint32_t mrr_buf_size,
3993
3979
                            memory::Root *parent_alloc)
3994
3980
{
3995
 
  optimizer::QuickRangeSelect *quick= NULL;
3996
 
  bool create_err= false;
3997
 
 
3998
 
  quick= new optimizer::QuickRangeSelect(param->session,
3999
 
                                         param->table,
4000
 
                                         param->real_keynr[idx],
4001
 
                                         test(parent_alloc),
4002
 
                                         NULL,
4003
 
                                         &create_err);
 
3981
  optimizer::QuickRangeSelect *quick= new optimizer::QuickRangeSelect(param->session,
 
3982
                                                                      param->table,
 
3983
                                                                      param->real_keynr[idx],
 
3984
                                                                      test(parent_alloc),
 
3985
                                                                      NULL);
4004
3986
 
4005
3987
  if (quick)
4006
3988
  {
4007
 
    if (create_err ||
4008
 
              get_quick_keys(param,
 
3989
          if (get_quick_keys(param,
4009
3990
                       quick,
4010
3991
                       param->key[idx],
4011
3992
                       key_tree,
4021
4002
    {
4022
4003
      quick->mrr_flags= mrr_flags;
4023
4004
      quick->mrr_buf_size= mrr_buf_size;
4024
 
      quick->key_parts=(KEY_PART*)
4025
 
        memdup_root(parent_alloc? parent_alloc : &quick->alloc,
4026
 
                    (char*) param->key[idx],
4027
 
                    sizeof(KEY_PART)*
4028
 
                    param->table->key_info[param->real_keynr[idx]].key_parts);
 
4005
      if (parent_alloc)
 
4006
      {
 
4007
        quick->key_parts=(KEY_PART*)
 
4008
          parent_alloc->memdup_root( (char*) param->key[idx], sizeof(KEY_PART)* param->table->key_info[param->real_keynr[idx]].key_parts);
 
4009
      }
 
4010
      else
 
4011
      {
 
4012
        quick->key_parts=(KEY_PART*)
 
4013
          quick->alloc.memdup_root((char*) param->key[idx], sizeof(KEY_PART)* param->table->key_info[param->real_keynr[idx]].key_parts);
 
4014
      }
4029
4015
    }
4030
4016
  }
4031
4017
  return quick;
4139
4125
    if (length == (uint32_t) (tmp_max_key - param->max_key) &&
4140
4126
              ! memcmp(param->min_key,param->max_key,length))
4141
4127
    {
4142
 
      KEY *table_key= quick->head->key_info+quick->index;
 
4128
      KeyInfo *table_key= quick->head->key_info+quick->index;
4143
4129
      flag= EQ_RANGE;
4144
4130
      if ((table_key->flags & (HA_NOSAME)) == HA_NOSAME &&
4145
4131
                key->part == table_key->key_parts-1)
4221
4207
}
4222
4208
 
4223
4209
 
4224
 
bool optimizer::QuickSelectInterface::is_keys_used(const MyBitmap *fields)
 
4210
bool optimizer::QuickSelectInterface::is_keys_used(const boost::dynamic_bitset<>& fields)
4225
4211
{
4226
4212
  return is_key_used(head, index, fields);
4227
4213
}
4251
4237
                                                                 table_reference_st *ref,
4252
4238
                                                                 ha_rows records)
4253
4239
{
4254
 
  memory::Root *old_root, *alloc;
4255
 
  optimizer::QuickRangeSelect *quick= NULL;
4256
 
  KEY *key_info = &table->key_info[ref->key];
 
4240
  memory::Root *old_root= NULL;
 
4241
  memory::Root *alloc= NULL;
 
4242
  KeyInfo *key_info = &table->key_info[ref->key];
4257
4243
  KEY_PART *key_part;
4258
4244
  optimizer::QuickRange *range= NULL;
4259
4245
  uint32_t part;
4260
 
  bool create_err= false;
4261
4246
  optimizer::CostVector cost;
4262
4247
 
4263
4248
  old_root= session->mem_root;
4264
4249
  /* The following call may change session->mem_root */
4265
 
  quick= new optimizer::QuickRangeSelect(session, table, ref->key, 0, 0, &create_err);
 
4250
  optimizer::QuickRangeSelect *quick= new optimizer::QuickRangeSelect(session, table, ref->key, 0, 0);
4266
4251
  /* save mem_root set by QuickRangeSelect constructor */
4267
4252
  alloc= session->mem_root;
4268
4253
  /*
4271
4256
  */
4272
4257
  session->mem_root= old_root;
4273
4258
 
4274
 
  if (!quick || create_err)
 
4259
  if (! quick)
4275
4260
    return 0;                   /* no ranges found */
4276
4261
  if (quick->init())
4277
4262
    goto err;
4290
4275
 
4291
4276
 
4292
4277
  if (!(quick->key_parts=key_part=(KEY_PART *)
4293
 
        alloc_root(&quick->alloc,sizeof(KEY_PART)*ref->key_parts)))
 
4278
        quick->alloc.alloc_root(sizeof(KEY_PART)*ref->key_parts)))
4294
4279
    goto err;
4295
4280
 
4296
4281
  for (part=0 ; part < ref->key_parts ;part++,key_part++)
4335
4320
 
4336
4321
  quick->mrr_buf_size= session->variables.read_rnd_buff_size;
4337
4322
  if (table->cursor->multi_range_read_info(quick->index, 1, (uint32_t)records,
4338
 
                                         &quick->mrr_buf_size,
4339
 
                                         &quick->mrr_flags, &cost))
 
4323
                                           &quick->mrr_buf_size,
 
4324
                                           &quick->mrr_flags, &cost))
4340
4325
    goto err;
4341
4326
 
4342
4327
  return quick;
4414
4399
}
4415
4400
 
4416
4401
 
4417
 
static inline uint32_t get_field_keypart(KEY *index, Field *field);
 
4402
static inline uint32_t get_field_keypart(KeyInfo *index, Field *field);
4418
4403
 
4419
4404
static inline optimizer::SEL_ARG * get_index_range_tree(uint32_t index,
4420
4405
                                                        optimizer::SEL_TREE *range_tree,
4421
4406
                                                        optimizer::Parameter *param,
4422
4407
                                                        uint32_t *param_idx);
4423
4408
 
4424
 
static bool get_constant_key_infix(KEY *index_info,
 
4409
static bool get_constant_key_infix(KeyInfo *index_info,
4425
4410
                                   optimizer::SEL_ARG *index_range_tree,
4426
 
                                   KEY_PART_INFO *first_non_group_part,
4427
 
                                   KEY_PART_INFO *min_max_arg_part,
4428
 
                                   KEY_PART_INFO *last_part,
 
4411
                                   KeyPartInfo *first_non_group_part,
 
4412
                                   KeyPartInfo *min_max_arg_part,
 
4413
                                   KeyPartInfo *last_part,
4429
4414
                                   Session *session,
4430
4415
                                   unsigned char *key_infix,
4431
4416
                                   uint32_t *key_infix_len,
4432
 
                                   KEY_PART_INFO **first_non_infix_part);
 
4417
                                   KeyPartInfo **first_non_infix_part);
4433
4418
 
4434
4419
static bool check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item);
4435
4420
 
4436
4421
static void
4437
4422
cost_group_min_max(Table* table,
4438
 
                   KEY *index_info,
 
4423
                   KeyInfo *index_info,
4439
4424
                   uint32_t used_key_parts,
4440
4425
                   uint32_t group_key_parts,
4441
4426
                   optimizer::SEL_TREE *range_tree,
4578
4563
get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree)
4579
4564
{
4580
4565
  Session *session= param->session;
4581
 
  JOIN *join= session->lex->current_select->join;
 
4566
  Join *join= session->lex->current_select->join;
4582
4567
  Table *table= param->table;
4583
4568
  bool have_min= false;              /* true if there is a MIN function. */
4584
4569
  bool have_max= false;              /* true if there is a MAX function. */
4585
4570
  Item_field *min_max_arg_item= NULL; // The argument of all MIN/MAX functions
4586
 
  KEY_PART_INFO *min_max_arg_part= NULL; /* The corresponding keypart. */
 
4571
  KeyPartInfo *min_max_arg_part= NULL; /* The corresponding keypart. */
4587
4572
  uint32_t group_prefix_len= 0; /* Length (in bytes) of the key prefix. */
4588
 
  KEY *index_info= NULL;    /* The index chosen for data access. */
 
4573
  KeyInfo *index_info= NULL;    /* The index chosen for data access. */
4589
4574
  uint32_t index= 0;            /* The id of the chosen index. */
4590
4575
  uint32_t group_key_parts= 0;  // Number of index key parts in the group prefix.
4591
4576
  uint32_t used_key_parts= 0;   /* Number of index key parts used for access. */
4593
4578
  uint32_t key_infix_len= 0;          /* Length of key_infix. */
4594
4579
  optimizer::GroupMinMaxReadPlan *read_plan= NULL; /* The eventually constructed TRP. */
4595
4580
  uint32_t key_part_nr;
4596
 
  order_st *tmp_group= NULL;
 
4581
  Order *tmp_group= NULL;
4597
4582
  Item *item= NULL;
4598
4583
  Item_field *item_field= NULL;
4599
4584
 
4606
4591
       (! join->select_distinct)) ||
4607
4592
      (join->select_lex->olap == ROLLUP_TYPE)) /* Check (B3) for ROLLUP */
4608
4593
    return NULL;
4609
 
  if (table->s->keys == 0)        /* There are no indexes to use. */
 
4594
  if (table->getShare()->sizeKeys() == 0)        /* There are no indexes to use. */
4610
4595
    return NULL;
4611
4596
 
4612
4597
  /* Analyze the query in more detail. */
4665
4650
    (GA1,GA2) are all true. If there is more than one such index, select the
4666
4651
    first one. Here we set the variables: group_prefix_len and index_info.
4667
4652
  */
4668
 
  KEY *cur_index_info= table->key_info;
4669
 
  KEY *cur_index_info_end= cur_index_info + table->s->keys;
4670
 
  KEY_PART_INFO *cur_part= NULL;
4671
 
  KEY_PART_INFO *end_part= NULL; /* Last part for loops. */
 
4653
  KeyInfo *cur_index_info= table->key_info;
 
4654
  KeyInfo *cur_index_info_end= cur_index_info + table->getShare()->sizeKeys();
 
4655
  KeyPartInfo *cur_part= NULL;
 
4656
  KeyPartInfo *end_part= NULL; /* Last part for loops. */
4672
4657
  /* Last index part. */
4673
 
  KEY_PART_INFO *last_part= NULL;
4674
 
  KEY_PART_INFO *first_non_group_part= NULL;
4675
 
  KEY_PART_INFO *first_non_infix_part= NULL;
 
4658
  KeyPartInfo *last_part= NULL;
 
4659
  KeyPartInfo *first_non_group_part= NULL;
 
4660
  KeyPartInfo *first_non_infix_part= NULL;
4676
4661
  uint32_t key_infix_parts= 0;
4677
4662
  uint32_t cur_group_key_parts= 0;
4678
4663
  uint32_t cur_group_prefix_len= 0;
4691
4676
  uint32_t cur_key_infix_len= 0;
4692
4677
  unsigned char cur_key_infix[MAX_KEY_LENGTH];
4693
4678
  uint32_t cur_used_key_parts= 0;
4694
 
  uint32_t pk= param->table->s->primary_key;
 
4679
  uint32_t pk= param->table->getShare()->getPrimaryKey();
4695
4680
 
4696
4681
  for (uint32_t cur_index= 0;
4697
4682
       cur_index_info != cur_index_info_end;
4714
4699
        (table->cursor->getEngine()->check_flag(HTON_BIT_PRIMARY_KEY_IN_READ_INDEX)))
4715
4700
    {
4716
4701
      /* For each table field */
4717
 
      for (uint32_t i= 0; i < table->s->fields; i++)
 
4702
      for (uint32_t i= 0; i < table->getShare()->sizeFields(); i++)
4718
4703
      {
4719
 
        Field *cur_field= table->field[i];
 
4704
        Field *cur_field= table->getField(i);
4720
4705
        /*
4721
4706
          If the field is used in the current query ensure that it's
4722
4707
          part of 'cur_index'
4884
4869
          Store the first and last keyparts that need to be analyzed
4885
4870
          into one array that can be passed as parameter.
4886
4871
        */
4887
 
        KEY_PART_INFO *key_part_range[2];
 
4872
        KeyPartInfo *key_part_range[2];
4888
4873
        key_part_range[0]= first_non_group_part;
4889
4874
        key_part_range[1]= last_part;
4890
4875
 
4928
4913
      optimizer::CostVector dummy_cost;
4929
4914
      uint32_t mrr_flags= HA_MRR_USE_DEFAULT_IMPL;
4930
4915
      uint32_t mrr_bufsize= 0;
4931
 
      cur_quick_prefix_records= check_quick_select(param,
 
4916
      cur_quick_prefix_records= check_quick_select(session,
 
4917
                                                   param,
4932
4918
                                                   cur_param_idx,
4933
4919
                                                   false /*don't care*/,
4934
4920
                                                   cur_index_tree,
5176
5162
    false o/w
5177
5163
*/
5178
5164
static bool
5179
 
get_constant_key_infix(KEY *,
 
5165
get_constant_key_infix(KeyInfo *,
5180
5166
                       optimizer::SEL_ARG *index_range_tree,
5181
 
                       KEY_PART_INFO *first_non_group_part,
5182
 
                       KEY_PART_INFO *min_max_arg_part,
5183
 
                       KEY_PART_INFO *last_part,
 
5167
                       KeyPartInfo *first_non_group_part,
 
5168
                       KeyPartInfo *min_max_arg_part,
 
5169
                       KeyPartInfo *last_part,
5184
5170
                       Session *,
5185
5171
                       unsigned char *key_infix,
5186
5172
                       uint32_t *key_infix_len,
5187
 
                       KEY_PART_INFO **first_non_infix_part)
 
5173
                       KeyPartInfo **first_non_infix_part)
5188
5174
{
5189
5175
  optimizer::SEL_ARG *cur_range= NULL;
5190
 
  KEY_PART_INFO *cur_part= NULL;
 
5176
  KeyPartInfo *cur_part= NULL;
5191
5177
  /* End part for the first loop below. */
5192
 
  KEY_PART_INFO *end_part= min_max_arg_part ? min_max_arg_part : last_part;
 
5178
  KeyPartInfo *end_part= min_max_arg_part ? min_max_arg_part : last_part;
5193
5179
 
5194
5180
  *key_infix_len= 0;
5195
5181
  unsigned char *key_ptr= key_infix;
5255
5241
    field  field that possibly references some key part in index
5256
5242
 
5257
5243
  NOTES
5258
 
    The return value can be used to get a KEY_PART_INFO pointer by
 
5244
    The return value can be used to get a KeyPartInfo pointer by
5259
5245
    part= index->key_part + get_field_keypart(...) - 1;
5260
5246
 
5261
5247
  RETURN
5263
5249
    0 if field does not reference any index field.
5264
5250
*/
5265
5251
static inline uint
5266
 
get_field_keypart(KEY *index, Field *field)
 
5252
get_field_keypart(KeyInfo *index, Field *field)
5267
5253
{
5268
 
  KEY_PART_INFO *part= NULL;
5269
 
  KEY_PART_INFO *end= NULL;
 
5254
  KeyPartInfo *part= NULL;
 
5255
  KeyPartInfo *end= NULL;
5270
5256
 
5271
5257
  for (part= index->key_part, end= part + index->key_parts; part < end; part++)
5272
5258
  {
5376
5362
    None
5377
5363
*/
5378
5364
void cost_group_min_max(Table* table,
5379
 
                        KEY *index_info,
 
5365
                        KeyInfo *index_info,
5380
5366
                        uint32_t used_key_parts,
5381
5367
                        uint32_t group_key_parts,
5382
5368
                        optimizer::SEL_TREE *range_tree,
5581
5567
}
5582
5568
 
5583
5569
 
 
5570
uint32_t optimizer::RorScanInfo::findFirstNotSet() const
 
5571
{
 
5572
  boost::dynamic_bitset<> map= bitsToBitset();
 
5573
  for (boost::dynamic_bitset<>::size_type i= 0; i < map.size(); i++)
 
5574
  {
 
5575
    if (! map.test(i))
 
5576
    {
 
5577
      return i;
 
5578
    }
 
5579
  }
 
5580
  return map.size();
 
5581
}
 
5582
 
 
5583
 
 
5584
size_t optimizer::RorScanInfo::getBitCount() const
 
5585
{
 
5586
  boost::dynamic_bitset<> tmp_bitset= bitsToBitset();
 
5587
  return tmp_bitset.count();
 
5588
}
 
5589
 
 
5590
 
 
5591
void optimizer::RorScanInfo::subtractBitset(const boost::dynamic_bitset<>& in_bitset)
 
5592
{
 
5593
  boost::dynamic_bitset<> tmp_bitset= bitsToBitset();
 
5594
  tmp_bitset-= in_bitset;
 
5595
  covered_fields= tmp_bitset.to_ulong();
 
5596
}
 
5597
 
 
5598
 
 
5599
boost::dynamic_bitset<> optimizer::RorScanInfo::bitsToBitset() const
 
5600
{
 
5601
  string res;
 
5602
  uint64_t conv= covered_fields;
 
5603
  while (conv)
 
5604
  {
 
5605
    res.push_back((conv & 1) + '0');
 
5606
    conv>>= 1;
 
5607
  }
 
5608
  if (! res.empty())
 
5609
  {
 
5610
    std::reverse(res.begin(), res.end());
 
5611
  }
 
5612
  string final(covered_fields_size - res.length(), '0');
 
5613
  final.append(res);
 
5614
  return (boost::dynamic_bitset<>(final));
 
5615
}
 
5616
 
 
5617
 
5584
5618
} /* namespace drizzled */