← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/opt_range.cc

  • Committer: Brian Aker
  • Date: 2009-04-13 16:22:40 UTC
  • mfrom: (971.1.78 mordred)
  • Revision ID: brian@gaz-20090413162240-ugi3gvhofmcuglzl
Merge Monty

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/opt_range.cc
114
114
#include "drizzled/temporal.h" /* Needed in get_mm_leaf() for timestamp -> datetime comparisons */
115
115
 
116
116
#include <string>
 
117
#include <bitset>
117
118
 
118
119
using namespace std;
119
120
 
698
699
  bool quick;                           // Don't calulate possible keys
699
700
 
700
701
  uint32_t fields_bitmap_size;
701
 
  MY_BITMAP needed_fields;    /* bitmask of fields needed by the query */
702
 
  MY_BITMAP tmp_covered_fields;
 
702
  bitset<MAX_FIELDS> needed_fields; /* bitmask of fields needed by the query */
 
703
  bitset<MAX_FIELDS> tmp_covered_fields;
703
704
 
704
705
  key_map *needed_reg;        /* ptr to SQL_SELECT::needed_reg */
705
706
 
1090
1091
{}
1091
1092
 
1092
1093
QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(Session *session, Table *table, uint32_t key_nr,
1093
 
                                       bool no_alloc, MEM_ROOT *parent_alloc,
1094
 
                                       bool *create_error)
 
1094
                                       bool no_alloc, MEM_ROOT *parent_alloc)
1095
1095
  :free_file(0),cur_range(NULL),last_range(0),dont_free(0)
1096
1096
{
1097
 
  my_bitmap_map *bitmap;
1098
 
 
1099
1097
  in_ror_merged_scan= 0;
1100
1098
  sorted= 0;
1101
1099
  index= key_nr;
1120
1118
  save_read_set= head->read_set;
1121
1119
  save_write_set= head->write_set;
1122
1120
 
1123
 
  /* Allocate a bitmap for used columns (Q: why not on MEM_ROOT?) */
1124
 
  if (!(bitmap= (my_bitmap_map*) malloc(head->s->column_bitmap_size)))
1125
 
  {
1126
 
    column_bitmap.bitmap= 0;
1127
 
    *create_error= 1;
1128
 
  }
1129
 
  else
1130
 
    bitmap_init(&column_bitmap, bitmap, head->s->fields, false);
1131
1121
  return;
1132
1122
}
1133
1123
 
1169
1159
    }
1170
1160
    delete_dynamic(&ranges); /* ranges are allocated in alloc */
1171
1161
    free_root(&alloc,MYF(0));
1172
 
    free((char*) column_bitmap.bitmap);
1173
1162
  }
1174
1163
  head->column_bitmaps_set(save_read_set, save_write_set);
1175
1164
  if (mrr_buf_desc)
1355
1344
  }
1356
1345
  head->prepare_for_position();
1357
1346
  head->file= org_file;
1358
 
  bitmap_copy(&column_bitmap, head->read_set);
 
1347
  column_bitmap= *(head->read_set);
1359
1348
  head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1360
1349
 
1361
1350
  return 0;
2096
2085
static int fill_used_fields_bitmap(PARAM *param)
2097
2086
{
2098
2087
  Table *table= param->table;
2099
 
  my_bitmap_map *tmp;
2100
2088
  uint32_t pk;
2101
 
  param->tmp_covered_fields.bitmap= 0;
2102
2089
  param->fields_bitmap_size= table->s->column_bitmap_size;
2103
 
  if (!(tmp= (my_bitmap_map*) alloc_root(param->mem_root,
2104
 
                                  param->fields_bitmap_size)) ||
2105
 
      bitmap_init(&param->needed_fields, tmp, table->s->fields, false))
2106
 
    return 1;
2107
2090
 
2108
 
  bitmap_copy(&param->needed_fields, table->read_set);
2109
 
  bitmap_union(&param->needed_fields, table->write_set);
 
2091
  param->needed_fields = *(table->read_set);
 
2092
  param->needed_fields |= *(table->write_set);
2110
2093
 
2111
2094
  pk= param->table->s->primary_key;
2112
2095
  if (pk != MAX_KEY && param->table->file->primary_key_is_clustered())
2116
2099
    KEY_PART_INFO *key_part_end= key_part +
2117
2100
                                 param->table->key_info[pk].key_parts;
2118
2101
    for (;key_part != key_part_end; ++key_part)
2119
 
      bitmap_clear_bit(&param->needed_fields, key_part->fieldnr-1);
 
2102
      param->needed_fields.reset(key_part->fieldnr-1);
2120
2103
  }
2121
2104
  return 0;
2122
2105
}
2739
2722
  SEL_ARG   *sel_arg;
2740
2723
 
2741
2724
  /* Fields used in the query and covered by this ROR scan. */
2742
 
  MY_BITMAP covered_fields;
 
2725
  bitset<MAX_FIELDS> covered_fields;
2743
2726
  uint32_t      used_fields_covered; /* # of set bits in covered_fields */
2744
2727
  int       key_rec_length; /* length of key record (including rowid) */
2745
2728
 
2790
2773
                                                param->fields_bitmap_size)))
2791
2774
    return NULL;
2792
2775
 
2793
 
  if (bitmap_init(&ror_scan->covered_fields, bitmap_buf,
2794
 
                  param->table->s->fields, false))
2795
 
    return NULL;
2796
 
  bitmap_clear_all(&ror_scan->covered_fields);
 
2776
  ror_scan->covered_fields.reset();
2797
2777
 
2798
2778
  KEY_PART_INFO *key_part= param->table->key_info[keynr].key_part;
2799
2779
  KEY_PART_INFO *key_part_end= key_part +
2800
2780
                               param->table->key_info[keynr].key_parts;
2801
2781
  for (;key_part != key_part_end; ++key_part)
2802
2782
  {
2803
 
    if (bitmap_is_set(&param->needed_fields, key_part->fieldnr-1))
2804
 
      bitmap_set_bit(&ror_scan->covered_fields, key_part->fieldnr-1);
 
2783
    if (param->needed_fields.test(key_part->fieldnr-1))
 
2784
      ror_scan->covered_fields.set(key_part->fieldnr-1);
2805
2785
  }
2806
2786
  double rows= rows2double(param->table->quick_rows[ror_scan->keynr]);
2807
2787
  ror_scan->index_read_cost=
2869
2849
typedef struct
2870
2850
{
2871
2851
  const PARAM *param;
2872
 
  MY_BITMAP covered_fields; /* union of fields covered by all scans */
 
2852
  bitset<MAX_FIELDS> covered_fields; /* union of fields covered by all scans */
2873
2853
  /*
2874
2854
    Fraction of table records that satisfies conditions of all scans.
2875
2855
    This is the number of full records that will be retrieved if a
2901
2881
ROR_INTERSECT_INFO* ror_intersect_init(const PARAM *param)
2902
2882
{
2903
2883
  ROR_INTERSECT_INFO *info;
2904
 
  my_bitmap_map* buf;
2905
2884
  if (!(info= (ROR_INTERSECT_INFO*)alloc_root(param->mem_root,
2906
2885
                                              sizeof(ROR_INTERSECT_INFO))))
2907
2886
    return NULL;
2908
2887
  info->param= param;
2909
 
  if (!(buf= (my_bitmap_map*) alloc_root(param->mem_root,
2910
 
                                         param->fields_bitmap_size)))
2911
 
    return NULL;
2912
 
  if (bitmap_init(&info->covered_fields, buf, param->table->s->fields,
2913
 
                  false))
2914
 
    return NULL;
2915
2888
  info->is_covering= false;
2916
2889
  info->index_scan_costs= 0.0;
2917
2890
  info->index_records= 0;
2918
2891
  info->out_rows= (double) param->table->file->stats.records;
2919
 
  bitmap_clear_all(&info->covered_fields);
 
2892
  info->covered_fields.reset();
2920
2893
  return info;
2921
2894
}
2922
2895
 
2923
2896
void ror_intersect_cpy(ROR_INTERSECT_INFO *dst, const ROR_INTERSECT_INFO *src)
2924
2897
{
2925
2898
  dst->param= src->param;
2926
 
  memcpy(dst->covered_fields.bitmap, src->covered_fields.bitmap,
2927
 
         no_bytes_in_map(&src->covered_fields));
 
2899
  dst->covered_fields= src->covered_fields;
2928
2900
  dst->out_rows= src->out_rows;
2929
2901
  dst->is_covering= src->is_covering;
2930
2902
  dst->index_records= src->index_records;
3033
3005
  SEL_ARG *sel_arg, *tuple_arg= NULL;
3034
3006
  key_part_map keypart_map= 0;
3035
3007
  bool cur_covered;
3036
 
  bool prev_covered= test(bitmap_is_set(&info->covered_fields,
3037
 
                                        key_part->fieldnr-1));
 
3008
  bool prev_covered= test(info->covered_fields.test(key_part->fieldnr-1));
3038
3009
  key_range min_range;
3039
3010
  key_range max_range;
3040
3011
  min_range.key= key_val;
3046
3017
  for (sel_arg= scan->sel_arg; sel_arg;
3047
3018
       sel_arg= sel_arg->next_key_part)
3048
3019
  {
3049
 
    cur_covered= test(bitmap_is_set(&info->covered_fields,
3050
 
                                    key_part[sel_arg->part].fieldnr-1));
 
3020
    cur_covered= test(info->covered_fields.test(key_part[sel_arg->part].fieldnr-1));
3051
3021
    if (cur_covered != prev_covered)
3052
3022
    {
3053
3023
      /* create (part1val, ..., part{n-1}val) tuple. */
3159
3129
  {
3160
3130
    info->index_records += info->param->table->quick_rows[ror_scan->keynr];
3161
3131
    info->index_scan_costs += ror_scan->index_read_cost;
3162
 
    bitmap_union(&info->covered_fields, &ror_scan->covered_fields);
3163
 
    if (!info->is_covering && bitmap_is_subset(&info->param->needed_fields,
3164
 
                                               &info->covered_fields))
 
3132
    info->covered_fields |= ror_scan->covered_fields;
 
3133
    if (! info->is_covering &&
 
3134
        ((info->covered_fields & info->param->needed_fields) == info->param->needed_fields))
3165
3135
    {
3166
3136
      info->is_covering= true;
3167
3137
    }
3396
3366
  return(trp);
3397
3367
}
3398
3368
 
3399
 
 
3400
3369
/*
3401
3370
  Get best covering ROR-intersection.
3402
3371
  SYNOPSIS
3450
3419
  /*I=set of all covering indexes */
3451
3420
  ror_scan_mark= tree->ror_scans;
3452
3421
 
3453
 
  MY_BITMAP *covered_fields= &param->tmp_covered_fields;
3454
 
  if (!covered_fields->bitmap)
3455
 
    covered_fields->bitmap= (my_bitmap_map*)alloc_root(param->mem_root,
3456
 
                                               param->fields_bitmap_size);
3457
 
  if (!covered_fields->bitmap ||
3458
 
      bitmap_init(covered_fields, covered_fields->bitmap,
3459
 
                  param->table->s->fields, false))
3460
 
    return 0;
3461
 
  bitmap_clear_all(covered_fields);
 
3422
  bitset<MAX_FIELDS> *covered_fields= &param->tmp_covered_fields;
 
3423
  covered_fields->reset();
3462
3424
 
3463
3425
  double total_cost= 0.0f;
3464
3426
  ha_rows records=0;
3477
3439
    */
3478
3440
    for (ROR_SCAN_INFO **scan= ror_scan_mark; scan != ror_scans_end; ++scan)
3479
3441
    {
3480
 
      bitmap_subtract(&(*scan)->covered_fields, covered_fields);
3481
 
      (*scan)->used_fields_covered=
3482
 
        bitmap_bits_set(&(*scan)->covered_fields);
3483
 
      (*scan)->first_uncovered_field=
3484
 
        bitmap_get_first(&(*scan)->covered_fields);
 
3442
      /* subtract a bitset */
 
3443
      (*scan)->covered_fields &= covered_fields->flip();
 
3444
      covered_fields->flip();
 
3445
      (*scan)->used_fields_covered= (*scan)->covered_fields.count();
 
3446
      (*scan)->first_uncovered_field= getFirstBitPos((*scan)->covered_fields);
3485
3447
    }
3486
3448
 
3487
3449
    my_qsort(ror_scan_mark, ror_scans_end-ror_scan_mark, sizeof(ROR_SCAN_INFO*),
3497
3459
    if (total_cost > read_time)
3498
3460
      return NULL;
3499
3461
    /* F=F-covered by first(I) */
3500
 
    bitmap_union(covered_fields, &(*ror_scan_mark)->covered_fields);
3501
 
    all_covered= bitmap_is_subset(&param->needed_fields, covered_fields);
 
3462
    *covered_fields|= (*ror_scan_mark)->covered_fields;
 
3463
    /*
 
3464
     * Check whether the param->needed_fields bitset is a subset of
 
3465
     * the covered_fields bitset. If the param->needed_fields bitset
 
3466
     * is a subset of covered_fields, then set all_covered to 
 
3467
     * true; otherwise, set it to false.
 
3468
     */
 
3469
    all_covered= ((*covered_fields & param->needed_fields) == param->needed_fields);
3502
3470
  } while ((++ror_scan_mark < ror_scans_end) && !all_covered);
3503
3471
 
3504
3472
  if (!all_covered || (ror_scan_mark - tree->ror_scans) == 1)
6482
6450
 
6483
6451
  quick=new QUICK_RANGE_SELECT(param->session, param->table,
6484
6452
                               param->real_keynr[idx],
6485
 
                               test(parent_alloc), NULL, &create_err);
 
6453
                               test(parent_alloc), NULL);
6486
6454
 
6487
6455
  if (quick)
6488
6456
  {
6671
6639
}
6672
6640
 
6673
6641
 
6674
 
bool QUICK_SELECT_I::is_keys_used(const MY_BITMAP *fields)
 
6642
bool QUICK_SELECT_I::is_keys_used(const bitset<MAX_FIELDS> *fields)
6675
6643
{
6676
6644
  return is_key_used(head, index, fields);
6677
6645
}
6678
6646
 
6679
 
bool QUICK_INDEX_MERGE_SELECT::is_keys_used(const MY_BITMAP *fields)
6680
 
{
6681
 
  QUICK_RANGE_SELECT *quick;
6682
 
  List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
6683
 
  while ((quick= it++))
6684
 
  {
6685
 
    if (is_key_used(head, quick->index, fields))
6686
 
      return 1;
6687
 
  }
6688
 
  return 0;
6689
 
}
6690
 
 
6691
 
bool QUICK_ROR_INTERSECT_SELECT::is_keys_used(const MY_BITMAP *fields)
6692
 
{
6693
 
  QUICK_RANGE_SELECT *quick;
6694
 
  List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
6695
 
  while ((quick= it++))
6696
 
  {
6697
 
    if (is_key_used(head, quick->index, fields))
6698
 
      return 1;
6699
 
  }
6700
 
  return 0;
6701
 
}
6702
 
 
6703
 
bool QUICK_ROR_UNION_SELECT::is_keys_used(const MY_BITMAP *fields)
 
6647
bool QUICK_INDEX_MERGE_SELECT::is_keys_used(const bitset<MAX_FIELDS> *fields)
 
6648
{
 
6649
  QUICK_RANGE_SELECT *quick;
 
6650
  List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
 
6651
  while ((quick= it++))
 
6652
  {
 
6653
    if (is_key_used(head, quick->index, fields))
 
6654
      return 1;
 
6655
  }
 
6656
  return 0;
 
6657
}
 
6658
 
 
6659
bool QUICK_ROR_INTERSECT_SELECT::is_keys_used(const bitset<MAX_FIELDS> *fields)
 
6660
{
 
6661
  QUICK_RANGE_SELECT *quick;
 
6662
  List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
 
6663
  while ((quick= it++))
 
6664
  {
 
6665
    if (is_key_used(head, quick->index, fields))
 
6666
      return 1;
 
6667
  }
 
6668
  return 0;
 
6669
}
 
6670
 
 
6671
bool QUICK_ROR_UNION_SELECT::is_keys_used(const bitset<MAX_FIELDS> *fields)
6704
6672
{
6705
6673
  QUICK_SELECT_I *quick;
6706
6674
  List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
6746
6714
 
6747
6715
  old_root= session->mem_root;
6748
6716
  /* The following call may change session->mem_root */
6749
 
  quick= new QUICK_RANGE_SELECT(session, table, ref->key, 0, 0, &create_err);
 
6717
  quick= new QUICK_RANGE_SELECT(session, table, ref->key, 0, 0);
6750
6718
  /* save mem_root set by QUICK_RANGE_SELECT constructor */
6751
6719
  alloc= session->mem_root;
6752
6720
  /*
8101
8069
          If the field is used in the current query ensure that it's
8102
8070
          part of 'cur_index'
8103
8071
        */
8104
 
        if (bitmap_is_set(table->read_set, cur_field->field_index) &&
 
8072
        if (table->read_set->test(cur_field->field_index) &&
8105
8073
            !cur_field->part_of_key_not_clustered.is_set(cur_index))
8106
8074
          goto next_index;                  // Field was not part of key
8107
8075
      }
8273
8241
                (min_max_arg_part && (min_max_arg_part < last_part));
8274
8242
      for (; cur_part != last_part; cur_part++)
8275
8243
      {
8276
 
        if (bitmap_is_set(table->read_set, cur_part->field->field_index))
 
8244
        if (table->read_set->test(cur_part->field->field_index))
8277
8245
          goto next_index;
8278
8246
      }
8279
8247
    }