← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/opt_range.cc

  • Committer: Jay Pipes
  • Date: 2009-03-17 06:08:42 UTC
  • mto: This revision was merged to the branch mainline in revision 941.
  • Revision ID: jpipes@serialcoder-20090317060842-lvxno992pxr91kqc
Forgot to add diagnostics_area.cc. thx krow. :)

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>
118
117
 
119
118
using namespace std;
120
119
 
699
698
  bool quick;                           // Don't calulate possible keys
700
699
 
701
700
  uint32_t fields_bitmap_size;
702
 
  bitset<MAX_FIELDS> needed_fields; /* bitmask of fields needed by the query */
703
 
  bitset<MAX_FIELDS> tmp_covered_fields;
 
701
  MY_BITMAP needed_fields;    /* bitmask of fields needed by the query */
 
702
  MY_BITMAP tmp_covered_fields;
704
703
 
705
704
  key_map *needed_reg;        /* ptr to SQL_SELECT::needed_reg */
706
705
 
1091
1090
{}
1092
1091
 
1093
1092
QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(Session *session, Table *table, uint32_t key_nr,
1094
 
                                       bool no_alloc, MEM_ROOT *parent_alloc)
 
1093
                                       bool no_alloc, MEM_ROOT *parent_alloc,
 
1094
                                       bool *create_error)
1095
1095
  :free_file(0),cur_range(NULL),last_range(0),dont_free(0)
1096
1096
{
 
1097
  my_bitmap_map *bitmap;
 
1098
 
1097
1099
  in_ror_merged_scan= 0;
1098
1100
  sorted= 0;
1099
1101
  index= key_nr;
1118
1120
  save_read_set= head->read_set;
1119
1121
  save_write_set= head->write_set;
1120
1122
 
 
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);
1121
1131
  return;
1122
1132
}
1123
1133
 
1159
1169
    }
1160
1170
    delete_dynamic(&ranges); /* ranges are allocated in alloc */
1161
1171
    free_root(&alloc,MYF(0));
 
1172
    free((char*) column_bitmap.bitmap);
1162
1173
  }
1163
1174
  head->column_bitmaps_set(save_read_set, save_write_set);
1164
1175
  if (mrr_buf_desc)
1344
1355
  }
1345
1356
  head->prepare_for_position();
1346
1357
  head->file= org_file;
1347
 
  column_bitmap= *(head->read_set);
 
1358
  bitmap_copy(&column_bitmap, head->read_set);
1348
1359
  head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1349
1360
 
1350
1361
  return 0;
1474
1485
  session_param->mem_root= &alloc;
1475
1486
}
1476
1487
 
1477
 
/*
1478
 
 * Function object that is used as the comparison function
1479
 
 * for the priority queue in the QUICK_ROR_UNION_SELECT
1480
 
 * class.
1481
 
 */
1482
 
class compare_functor
1483
 
{
1484
 
  QUICK_ROR_UNION_SELECT *self;
1485
 
  public:
1486
 
  compare_functor(QUICK_ROR_UNION_SELECT *in_arg)
1487
 
    : self(in_arg) { }
1488
 
  inline bool operator()(const QUICK_SELECT_I *i, const QUICK_SELECT_I *j) const
1489
 
  {
1490
 
    int val= self->head->file->cmp_ref(i->last_rowid,
1491
 
                                       j->last_rowid);
1492
 
    return (val >= 0);
1493
 
  }
1494
 
};
1495
1488
 
1496
1489
/*
1497
1490
  Do post-constructor initialization.
1505
1498
 
1506
1499
int QUICK_ROR_UNION_SELECT::init()
1507
1500
{
1508
 
  queue= 
1509
 
    new priority_queue<QUICK_SELECT_I *, vector<QUICK_SELECT_I *>, compare_functor >(compare_functor(this));
 
1501
  if (init_queue(&queue, quick_selects.elements, 0,
 
1502
                 false, quick_ror_union_select_queue_cmp,
 
1503
                 (void*) this))
 
1504
  {
 
1505
    memset(&queue, 0, sizeof(QUEUE));
 
1506
    return 0;
 
1507
  }
 
1508
 
1510
1509
  if (!(cur_rowid= (unsigned char*) alloc_root(&alloc, 2*head->file->ref_length)))
1511
1510
    return 0;
1512
1511
  prev_rowid= cur_rowid + head->file->ref_length;
1558
1557
    }
1559
1558
    scans_inited= true;
1560
1559
  }
1561
 
  while (!queue->empty())
1562
 
    queue->pop();
 
1560
  queue_remove_all(&queue);
1563
1561
  /*
1564
1562
    Initialize scans for merged quick selects and put all merged quick
1565
1563
    selects into the queue.
1576
1574
      return(error);
1577
1575
    }
1578
1576
    quick->save_last_pos();
1579
 
    queue->push(quick);
 
1577
    queue_insert(&queue, (unsigned char*)quick);
1580
1578
  }
1581
1579
 
1582
1580
  if (head->file->ha_rnd_init(1))
1596
1594
 
1597
1595
QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT()
1598
1596
{
1599
 
  while (!queue->empty())
1600
 
    queue->pop();
1601
 
  delete queue;
 
1597
  delete_queue(&queue);
1602
1598
  quick_selects.delete_elements();
1603
1599
  if (head->file->inited != handler::NONE)
1604
1600
    head->file->ha_rnd_end();
2085
2081
static int fill_used_fields_bitmap(PARAM *param)
2086
2082
{
2087
2083
  Table *table= param->table;
 
2084
  my_bitmap_map *tmp;
2088
2085
  uint32_t pk;
 
2086
  param->tmp_covered_fields.bitmap= 0;
2089
2087
  param->fields_bitmap_size= table->s->column_bitmap_size;
 
2088
  if (!(tmp= (my_bitmap_map*) alloc_root(param->mem_root,
 
2089
                                  param->fields_bitmap_size)) ||
 
2090
      bitmap_init(&param->needed_fields, tmp, table->s->fields, false))
 
2091
    return 1;
2090
2092
 
2091
 
  param->needed_fields = *(table->read_set);
2092
 
  param->needed_fields |= *(table->write_set);
 
2093
  bitmap_copy(&param->needed_fields, table->read_set);
 
2094
  bitmap_union(&param->needed_fields, table->write_set);
2093
2095
 
2094
2096
  pk= param->table->s->primary_key;
2095
2097
  if (pk != MAX_KEY && param->table->file->primary_key_is_clustered())
2099
2101
    KEY_PART_INFO *key_part_end= key_part +
2100
2102
                                 param->table->key_info[pk].key_parts;
2101
2103
    for (;key_part != key_part_end; ++key_part)
2102
 
      param->needed_fields.reset(key_part->fieldnr-1);
 
2104
      bitmap_clear_bit(&param->needed_fields, key_part->fieldnr-1);
2103
2105
  }
2104
2106
  return 0;
2105
2107
}
2722
2724
  SEL_ARG   *sel_arg;
2723
2725
 
2724
2726
  /* Fields used in the query and covered by this ROR scan. */
2725
 
  bitset<MAX_FIELDS> covered_fields;
 
2727
  MY_BITMAP covered_fields;
2726
2728
  uint32_t      used_fields_covered; /* # of set bits in covered_fields */
2727
2729
  int       key_rec_length; /* length of key record (including rowid) */
2728
2730
 
2773
2775
                                                param->fields_bitmap_size)))
2774
2776
    return NULL;
2775
2777
 
2776
 
  ror_scan->covered_fields.reset();
 
2778
  if (bitmap_init(&ror_scan->covered_fields, bitmap_buf,
 
2779
                  param->table->s->fields, false))
 
2780
    return NULL;
 
2781
  bitmap_clear_all(&ror_scan->covered_fields);
2777
2782
 
2778
2783
  KEY_PART_INFO *key_part= param->table->key_info[keynr].key_part;
2779
2784
  KEY_PART_INFO *key_part_end= key_part +
2780
2785
                               param->table->key_info[keynr].key_parts;
2781
2786
  for (;key_part != key_part_end; ++key_part)
2782
2787
  {
2783
 
    if (param->needed_fields.test(key_part->fieldnr-1))
2784
 
      ror_scan->covered_fields.set(key_part->fieldnr-1);
 
2788
    if (bitmap_is_set(&param->needed_fields, key_part->fieldnr-1))
 
2789
      bitmap_set_bit(&ror_scan->covered_fields, key_part->fieldnr-1);
2785
2790
  }
2786
2791
  double rows= rows2double(param->table->quick_rows[ror_scan->keynr]);
2787
2792
  ror_scan->index_read_cost=
2849
2854
typedef struct
2850
2855
{
2851
2856
  const PARAM *param;
2852
 
  bitset<MAX_FIELDS> covered_fields; /* union of fields covered by all scans */
 
2857
  MY_BITMAP covered_fields; /* union of fields covered by all scans */
2853
2858
  /*
2854
2859
    Fraction of table records that satisfies conditions of all scans.
2855
2860
    This is the number of full records that will be retrieved if a
2881
2886
ROR_INTERSECT_INFO* ror_intersect_init(const PARAM *param)
2882
2887
{
2883
2888
  ROR_INTERSECT_INFO *info;
 
2889
  my_bitmap_map* buf;
2884
2890
  if (!(info= (ROR_INTERSECT_INFO*)alloc_root(param->mem_root,
2885
2891
                                              sizeof(ROR_INTERSECT_INFO))))
2886
2892
    return NULL;
2887
2893
  info->param= param;
 
2894
  if (!(buf= (my_bitmap_map*) alloc_root(param->mem_root,
 
2895
                                         param->fields_bitmap_size)))
 
2896
    return NULL;
 
2897
  if (bitmap_init(&info->covered_fields, buf, param->table->s->fields,
 
2898
                  false))
 
2899
    return NULL;
2888
2900
  info->is_covering= false;
2889
2901
  info->index_scan_costs= 0.0;
2890
2902
  info->index_records= 0;
2891
2903
  info->out_rows= (double) param->table->file->stats.records;
2892
 
  info->covered_fields.reset();
 
2904
  bitmap_clear_all(&info->covered_fields);
2893
2905
  return info;
2894
2906
}
2895
2907
 
2896
2908
void ror_intersect_cpy(ROR_INTERSECT_INFO *dst, const ROR_INTERSECT_INFO *src)
2897
2909
{
2898
2910
  dst->param= src->param;
2899
 
  dst->covered_fields= src->covered_fields;
 
2911
  memcpy(dst->covered_fields.bitmap, src->covered_fields.bitmap,
 
2912
         no_bytes_in_map(&src->covered_fields));
2900
2913
  dst->out_rows= src->out_rows;
2901
2914
  dst->is_covering= src->is_covering;
2902
2915
  dst->index_records= src->index_records;
3005
3018
  SEL_ARG *sel_arg, *tuple_arg= NULL;
3006
3019
  key_part_map keypart_map= 0;
3007
3020
  bool cur_covered;
3008
 
  bool prev_covered= test(info->covered_fields.test(key_part->fieldnr-1));
 
3021
  bool prev_covered= test(bitmap_is_set(&info->covered_fields,
 
3022
                                        key_part->fieldnr-1));
3009
3023
  key_range min_range;
3010
3024
  key_range max_range;
3011
3025
  min_range.key= key_val;
3017
3031
  for (sel_arg= scan->sel_arg; sel_arg;
3018
3032
       sel_arg= sel_arg->next_key_part)
3019
3033
  {
3020
 
    cur_covered= test(info->covered_fields.test(key_part[sel_arg->part].fieldnr-1));
 
3034
    cur_covered= test(bitmap_is_set(&info->covered_fields,
 
3035
                                    key_part[sel_arg->part].fieldnr-1));
3021
3036
    if (cur_covered != prev_covered)
3022
3037
    {
3023
3038
      /* create (part1val, ..., part{n-1}val) tuple. */
3129
3144
  {
3130
3145
    info->index_records += info->param->table->quick_rows[ror_scan->keynr];
3131
3146
    info->index_scan_costs += ror_scan->index_read_cost;
3132
 
    info->covered_fields |= ror_scan->covered_fields;
3133
 
    if (!info->is_covering && isBitmapSubset(&info->param->needed_fields,
3134
 
                                             &info->covered_fields))
 
3147
    bitmap_union(&info->covered_fields, &ror_scan->covered_fields);
 
3148
    if (!info->is_covering && bitmap_is_subset(&info->param->needed_fields,
 
3149
                                               &info->covered_fields))
3135
3150
    {
3136
3151
      info->is_covering= true;
3137
3152
    }
3366
3381
  return(trp);
3367
3382
}
3368
3383
 
 
3384
 
3369
3385
/*
3370
3386
  Get best covering ROR-intersection.
3371
3387
  SYNOPSIS
3419
3435
  /*I=set of all covering indexes */
3420
3436
  ror_scan_mark= tree->ror_scans;
3421
3437
 
3422
 
  bitset<MAX_FIELDS> *covered_fields= &param->tmp_covered_fields;
3423
 
  covered_fields->reset();
 
3438
  MY_BITMAP *covered_fields= &param->tmp_covered_fields;
 
3439
  if (!covered_fields->bitmap)
 
3440
    covered_fields->bitmap= (my_bitmap_map*)alloc_root(param->mem_root,
 
3441
                                               param->fields_bitmap_size);
 
3442
  if (!covered_fields->bitmap ||
 
3443
      bitmap_init(covered_fields, covered_fields->bitmap,
 
3444
                  param->table->s->fields, false))
 
3445
    return 0;
 
3446
  bitmap_clear_all(covered_fields);
3424
3447
 
3425
3448
  double total_cost= 0.0f;
3426
3449
  ha_rows records=0;
3439
3462
    */
3440
3463
    for (ROR_SCAN_INFO **scan= ror_scan_mark; scan != ror_scans_end; ++scan)
3441
3464
    {
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);
 
3465
      bitmap_subtract(&(*scan)->covered_fields, covered_fields);
 
3466
      (*scan)->used_fields_covered=
 
3467
        bitmap_bits_set(&(*scan)->covered_fields);
 
3468
      (*scan)->first_uncovered_field=
 
3469
        bitmap_get_first(&(*scan)->covered_fields);
3447
3470
    }
3448
3471
 
3449
3472
    my_qsort(ror_scan_mark, ror_scans_end-ror_scan_mark, sizeof(ROR_SCAN_INFO*),
3459
3482
    if (total_cost > read_time)
3460
3483
      return NULL;
3461
3484
    /* F=F-covered by first(I) */
3462
 
    *covered_fields |= (*ror_scan_mark)->covered_fields;
3463
 
    all_covered= isBitmapSubset(&param->needed_fields, covered_fields);
 
3485
    bitmap_union(covered_fields, &(*ror_scan_mark)->covered_fields);
 
3486
    all_covered= bitmap_is_subset(&param->needed_fields, covered_fields);
3464
3487
  } while ((++ror_scan_mark < ror_scans_end) && !all_covered);
3465
3488
 
3466
3489
  if (!all_covered || (ror_scan_mark - tree->ror_scans) == 1)
6444
6467
 
6445
6468
  quick=new QUICK_RANGE_SELECT(param->session, param->table,
6446
6469
                               param->real_keynr[idx],
6447
 
                               test(parent_alloc), NULL);
 
6470
                               test(parent_alloc), NULL, &create_err);
6448
6471
 
6449
6472
  if (quick)
6450
6473
  {
6571
6594
                               flag)))
6572
6595
    return 1;                   // out of memory
6573
6596
 
6574
 
  set_if_bigger(quick->max_used_key_length, (uint32_t)range->min_length);
6575
 
  set_if_bigger(quick->max_used_key_length, (uint32_t)range->max_length);
 
6597
  set_if_bigger(quick->max_used_key_length, range->min_length);
 
6598
  set_if_bigger(quick->max_used_key_length, range->max_length);
6576
6599
  set_if_bigger(quick->used_key_parts, (uint32_t) key_tree->part+1);
6577
6600
  if (insert_dynamic(&quick->ranges, (unsigned char*) &range))
6578
6601
    return 1;
6633
6656
}
6634
6657
 
6635
6658
 
6636
 
bool QUICK_SELECT_I::is_keys_used(const bitset<MAX_FIELDS> *fields)
 
6659
bool QUICK_SELECT_I::is_keys_used(const MY_BITMAP *fields)
6637
6660
{
6638
6661
  return is_key_used(head, index, fields);
6639
6662
}
6640
6663
 
6641
 
bool QUICK_INDEX_MERGE_SELECT::is_keys_used(const bitset<MAX_FIELDS> *fields)
6642
 
{
6643
 
  QUICK_RANGE_SELECT *quick;
6644
 
  List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
6645
 
  while ((quick= it++))
6646
 
  {
6647
 
    if (is_key_used(head, quick->index, fields))
6648
 
      return 1;
6649
 
  }
6650
 
  return 0;
6651
 
}
6652
 
 
6653
 
bool QUICK_ROR_INTERSECT_SELECT::is_keys_used(const bitset<MAX_FIELDS> *fields)
6654
 
{
6655
 
  QUICK_RANGE_SELECT *quick;
6656
 
  List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
6657
 
  while ((quick= it++))
6658
 
  {
6659
 
    if (is_key_used(head, quick->index, fields))
6660
 
      return 1;
6661
 
  }
6662
 
  return 0;
6663
 
}
6664
 
 
6665
 
bool QUICK_ROR_UNION_SELECT::is_keys_used(const bitset<MAX_FIELDS> *fields)
 
6664
bool QUICK_INDEX_MERGE_SELECT::is_keys_used(const MY_BITMAP *fields)
 
6665
{
 
6666
  QUICK_RANGE_SELECT *quick;
 
6667
  List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
 
6668
  while ((quick= it++))
 
6669
  {
 
6670
    if (is_key_used(head, quick->index, fields))
 
6671
      return 1;
 
6672
  }
 
6673
  return 0;
 
6674
}
 
6675
 
 
6676
bool QUICK_ROR_INTERSECT_SELECT::is_keys_used(const MY_BITMAP *fields)
 
6677
{
 
6678
  QUICK_RANGE_SELECT *quick;
 
6679
  List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
 
6680
  while ((quick= it++))
 
6681
  {
 
6682
    if (is_key_used(head, quick->index, fields))
 
6683
      return 1;
 
6684
  }
 
6685
  return 0;
 
6686
}
 
6687
 
 
6688
bool QUICK_ROR_UNION_SELECT::is_keys_used(const MY_BITMAP *fields)
6666
6689
{
6667
6690
  QUICK_SELECT_I *quick;
6668
6691
  List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
6708
6731
 
6709
6732
  old_root= session->mem_root;
6710
6733
  /* The following call may change session->mem_root */
6711
 
  quick= new QUICK_RANGE_SELECT(session, table, ref->key, 0, 0);
 
6734
  quick= new QUICK_RANGE_SELECT(session, table, ref->key, 0, 0, &create_err);
6712
6735
  /* save mem_root set by QUICK_RANGE_SELECT constructor */
6713
6736
  alloc= session->mem_root;
6714
6737
  /*
7036
7059
  {
7037
7060
    do
7038
7061
    {
7039
 
      if (queue->empty())
 
7062
      if (!queue.elements)
7040
7063
        return(HA_ERR_END_OF_FILE);
7041
7064
      /* Ok, we have a queue with >= 1 scans */
7042
7065
 
7043
 
      quick= queue->top();
 
7066
      quick= (QUICK_SELECT_I*)queue_top(&queue);
7044
7067
      memcpy(cur_rowid, quick->last_rowid, rowid_length);
7045
7068
 
7046
7069
      /* put into queue rowid from the same stream as top element */
7048
7071
      {
7049
7072
        if (error != HA_ERR_END_OF_FILE)
7050
7073
          return(error);
7051
 
        queue->pop();
 
7074
        queue_remove(&queue, 0);
7052
7075
      }
7053
7076
      else
7054
7077
      {
7055
7078
        quick->save_last_pos();
7056
 
        queue->pop();
7057
 
        queue->push(quick);
 
7079
        queue_replaced(&queue);
7058
7080
      }
7059
7081
 
7060
7082
      if (!have_prev_rowid)
8063
8085
          If the field is used in the current query ensure that it's
8064
8086
          part of 'cur_index'
8065
8087
        */
8066
 
        if (table->read_set->test(cur_field->field_index) &&
 
8088
        if (bitmap_is_set(table->read_set, cur_field->field_index) &&
8067
8089
            !cur_field->part_of_key_not_clustered.is_set(cur_index))
8068
8090
          goto next_index;                  // Field was not part of key
8069
8091
      }
8235
8257
                (min_max_arg_part && (min_max_arg_part < last_part));
8236
8258
      for (; cur_part != last_part; cur_part++)
8237
8259
      {
8238
 
        if (table->read_set->test(cur_part->field->field_index))
 
8260
        if (bitmap_is_set(table->read_set, cur_part->field->field_index))
8239
8261
          goto next_index;
8240
8262
      }
8241
8263
    }
8714
8736
    quick_prefix_selectivity= (double) quick_prefix_records /
8715
8737
                              (double) table_records;
8716
8738
    num_groups= (uint32_t) rint(num_groups * quick_prefix_selectivity);
8717
 
    set_if_bigger(num_groups, 1U);
 
8739
    set_if_bigger(num_groups, 1);
8718
8740
  }
8719
8741
 
8720
8742
  if (used_key_parts > group_key_parts)