← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/optimizer/range.cc

  • Committer: patrick crews
  • Date: 2011-06-08 03:02:27 UTC
  • mto: This revision was merged to the branch mainline in revision 2329.
  • Revision ID: gleebix@gmail.com-20110608030227-updkyv2652zvfajc
Initial voodoo worked to give us a crashme mode.  Need docs still

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/optimizer/range.cc
1
1
/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2
2
 *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
3
3
 *
4
 
 *  Copyright (C) 2008-2009 Sun Microsystems
 
4
 *  Copyright (C) 2008-2009 Sun Microsystems, Inc.
5
5
 *
6
6
 *  This program is free software; you can redistribute it and/or modify
7
7
 *  it under the terms of the GNU General Public License as published by
100
100
           subject and may omit some details.
101
101
*/
102
102
 
103
 
#include "config.h"
 
103
#include <config.h>
104
104
 
105
105
#include <math.h>
106
106
#include <float.h>
111
111
 
112
112
#include <boost/dynamic_bitset.hpp>
113
113
 
114
 
#include "drizzled/sql_base.h"
115
 
#include "drizzled/sql_select.h"
116
 
#include "drizzled/error.h"
117
 
#include "drizzled/optimizer/cost_vector.h"
118
 
#include "drizzled/item/cmpfunc.h"
119
 
#include "drizzled/field/num.h"
120
 
#include "drizzled/check_stack_overrun.h"
121
 
#include "drizzled/optimizer/sum.h"
122
 
#include "drizzled/optimizer/range.h"
123
 
#include "drizzled/optimizer/quick_range.h"
124
 
#include "drizzled/optimizer/quick_range_select.h"
125
 
#include "drizzled/optimizer/quick_group_min_max_select.h"
126
 
#include "drizzled/optimizer/quick_index_merge_select.h"
127
 
#include "drizzled/optimizer/quick_ror_intersect_select.h"
128
 
#include "drizzled/optimizer/quick_ror_union_select.h"
129
 
#include "drizzled/optimizer/table_read_plan.h"
130
 
#include "drizzled/optimizer/sel_arg.h"
131
 
#include "drizzled/optimizer/sel_imerge.h"
132
 
#include "drizzled/optimizer/sel_tree.h"
133
 
#include "drizzled/optimizer/range_param.h"
134
 
#include "drizzled/records.h"
135
 
#include "drizzled/internal/my_sys.h"
136
 
#include "drizzled/internal/iocache.h"
137
 
 
138
 
#include "drizzled/temporal.h" /* Needed in get_mm_leaf() for timestamp -> datetime comparisons */
 
114
#include <drizzled/check_stack_overrun.h>
 
115
#include <drizzled/error.h>
 
116
#include <drizzled/field/num.h>
 
117
#include <drizzled/internal/iocache.h>
 
118
#include <drizzled/internal/my_sys.h>
 
119
#include <drizzled/item/cmpfunc.h>
 
120
#include <drizzled/optimizer/cost_vector.h>
 
121
#include <drizzled/optimizer/quick_group_min_max_select.h>
 
122
#include <drizzled/optimizer/quick_index_merge_select.h>
 
123
#include <drizzled/optimizer/quick_range.h>
 
124
#include <drizzled/optimizer/quick_range_select.h>
 
125
#include <drizzled/optimizer/quick_ror_intersect_select.h>
 
126
#include <drizzled/optimizer/quick_ror_union_select.h>
 
127
#include <drizzled/optimizer/range.h>
 
128
#include <drizzled/optimizer/range_param.h>
 
129
#include <drizzled/optimizer/sel_arg.h>
 
130
#include <drizzled/optimizer/sel_imerge.h>
 
131
#include <drizzled/optimizer/sel_tree.h>
 
132
#include <drizzled/optimizer/sum.h>
 
133
#include <drizzled/optimizer/table_read_plan.h>
 
134
#include <drizzled/plugin/storage_engine.h>
 
135
#include <drizzled/records.h>
 
136
#include <drizzled/sql_base.h>
 
137
#include <drizzled/sql_select.h>
 
138
#include <drizzled/table_reference.h>
 
139
#include <drizzled/session.h>
 
140
#include <drizzled/key.h>
 
141
#include <drizzled/unique.h>
 
142
#include <drizzled/temporal.h> /* Needed in get_mm_leaf() for timestamp -> datetime comparisons */
 
143
#include <drizzled/sql_lex.h>
 
144
#include <drizzled/system_variables.h>
139
145
 
140
146
using namespace std;
141
 
namespace drizzled
142
 
{
 
147
 
 
148
namespace drizzled {
143
149
 
144
150
#define HA_END_SPACE_KEY 0
145
151
 
213
219
  else
214
220
  {
215
221
    double n_blocks=
216
 
      ceil(uint64_t2double(table->cursor->stats.data_file_length) / IO_SIZE);
 
222
      ceil(static_cast<double>(table->cursor->stats.data_file_length) / IO_SIZE);
217
223
    double busy_blocks=
218
 
      n_blocks * (1.0 - pow(1.0 - 1.0/n_blocks, rows2double(nrows)));
 
224
      n_blocks * (1.0 - pow(1.0 - 1.0/n_blocks, static_cast<double>(nrows)));
219
225
    if (busy_blocks < 1.0)
220
226
      busy_blocks= 1.0;
221
227
 
348
354
  {
349
355
    return 0;
350
356
  }
351
 
  if (! (select= new optimizer::SqlSelect))
 
357
  if (! (select= new optimizer::SqlSelect()))
352
358
  {
353
359
    *error= 1;                  // out of memory
354
360
    return 0;
360
366
 
361
367
  if (head->sort.io_cache)
362
368
  {
363
 
    memcpy(select->file, head->sort.io_cache, sizeof(internal::IO_CACHE));
 
369
    memcpy(select->file, head->sort.io_cache, sizeof(internal::io_cache_st));
364
370
    select->records=(ha_rows) (select->file->end_of_file/
365
371
                               head->cursor->ref_length);
366
372
    delete head->sort.io_cache;
374
380
  :
375
381
    quick(NULL),
376
382
    cond(NULL),
377
 
    file(static_cast<internal::IO_CACHE *>(memory::sql_calloc(sizeof(internal::IO_CACHE)))),
 
383
    file(static_cast<internal::io_cache_st *>(memory::sql_calloc(sizeof(internal::io_cache_st)))),
378
384
    free_cond(false)
379
385
{
380
386
  quick_keys.reset();
737
743
    {
738
744
      int key_for_use= head->find_shortest_key(&head->covering_keys);
739
745
      double key_read_time=
740
 
        param.table->cursor->index_only_read_time(key_for_use,
741
 
                                                rows2double(records)) +
 
746
        param.table->cursor->index_only_read_time(key_for_use, records) +
742
747
        (double) records / TIME_FOR_COMPARE;
743
748
      if (key_read_time < read_time)
744
749
        read_time= key_read_time;
808
813
          objects are not allowed so don't use ROR-intersection for
809
814
          table deletes.
810
815
        */
811
 
        if ((session->lex->sql_command != SQLCOM_DELETE))
 
816
        if ((session->lex().sql_command != SQLCOM_DELETE))
812
817
        {
813
818
          /*
814
819
            Get best non-covering ROR-intersection plan and prepare data for
836
841
        optimizer::SEL_IMERGE *imerge= NULL;
837
842
        optimizer::TableReadPlan *best_conj_trp= NULL;
838
843
        optimizer::TableReadPlan *new_conj_trp= NULL;
839
 
        List_iterator_fast<optimizer::SEL_IMERGE> it(tree->merges);
 
844
        List<optimizer::SEL_IMERGE>::iterator it(tree->merges.begin());
840
845
        while ((imerge= it++))
841
846
        {
842
847
          new_conj_trp= get_best_disjunct_quick(session, &param, imerge, best_read_time);
1041
1046
  /* Calculate cost(rowid_to_row_scan) */
1042
1047
  {
1043
1048
    optimizer::CostVector sweep_cost;
1044
 
    Join *join= param->session->lex->select_lex.join;
 
1049
    Join *join= param->session->lex().select_lex.join;
1045
1050
    bool is_interrupted= test(join && join->tables == 1);
1046
1051
    get_sweep_read_cost(param->table, non_cpk_scan_records, is_interrupted,
1047
1052
                        &sweep_cost);
1084
1089
  }
1085
1090
 
1086
1091
build_ror_index_merge:
1087
 
  if (!all_scans_ror_able || param->session->lex->sql_command == SQLCOM_DELETE)
 
1092
  if (!all_scans_ror_able || param->session->lex().sql_command == SQLCOM_DELETE)
1088
1093
    return(imerge_trp);
1089
1094
 
1090
1095
  /* Ok, it is possible to build a ROR-union, try it. */
1117
1122
      cost= param->table->cursor->
1118
1123
              read_time(param->real_keynr[(*cur_child)->key_idx], 1,
1119
1124
                        (*cur_child)->records) +
1120
 
              rows2double((*cur_child)->records) / TIME_FOR_COMPARE;
 
1125
              static_cast<double>((*cur_child)->records) / TIME_FOR_COMPARE;
1121
1126
    }
1122
1127
    else
1123
1128
      cost= read_time;
1159
1164
  double roru_total_cost;
1160
1165
  {
1161
1166
    optimizer::CostVector sweep_cost;
1162
 
    Join *join= param->session->lex->select_lex.join;
 
1167
    Join *join= param->session->lex().select_lex.join;
1163
1168
    bool is_interrupted= test(join && join->tables == 1);
1164
1169
    get_sweep_read_cost(param->table, roru_total_records, is_interrupted,
1165
1170
                        &sweep_cost);
1166
1171
    roru_total_cost= roru_index_costs +
1167
 
                     rows2double(roru_total_records)*log((double)n_child_scans) /
 
1172
                     static_cast<double>(roru_total_records)*log((double)n_child_scans) /
1168
1173
                     (TIME_FOR_COMPARE_ROWID * M_LN2) +
1169
1174
                     sweep_cost.total_cost();
1170
1175
  }
1230
1235
    if (param->needed_fields.test(key_part->fieldnr-1))
1231
1236
      tmp_bitset.set(key_part->fieldnr-1);
1232
1237
  }
1233
 
  double rows= rows2double(param->table->quick_rows[ror_scan->keynr]);
 
1238
  double rows= param->table->quick_rows[ror_scan->keynr];
1234
1239
  ror_scan->index_read_cost=
1235
1240
    param->table->cursor->index_only_read_time(ror_scan->keynr, rows);
1236
1241
  ror_scan->covered_fields= tmp_bitset.to_ulong();
1253
1258
 
1254
1259
static int cmp_ror_scan_info(optimizer::RorScanInfo** a, optimizer::RorScanInfo** b)
1255
1260
{
1256
 
  double val1= rows2double((*a)->records) * (*a)->key_rec_length;
1257
 
  double val2= rows2double((*b)->records) * (*b)->key_rec_length;
 
1261
  double val1= static_cast<double>((*a)->records) * (*a)->key_rec_length;
 
1262
  double val2= static_cast<double>((*b)->records) * (*b)->key_rec_length;
1258
1263
  return (val1 < val2)? -1: (val1 == val2)? 0 : 1;
1259
1264
}
1260
1265
 
1490
1495
      if (cur_covered)
1491
1496
      {
1492
1497
        /* uncovered -> covered */
1493
 
        double tmp= rows2double(records)/rows2double(prev_records);
1494
 
        selectivity_mult *= tmp;
 
1498
        selectivity_mult *= static_cast<double>(records) / prev_records;
1495
1499
        prev_records= HA_POS_ERROR;
1496
1500
      }
1497
1501
      else
1504
1508
  }
1505
1509
  if (!prev_covered)
1506
1510
  {
1507
 
    double tmp= rows2double(info->param->table->quick_rows[scan->keynr]) /
1508
 
                rows2double(prev_records);
1509
 
    selectivity_mult *= tmp;
 
1511
    selectivity_mult *= static_cast<double>(info->param->table->quick_rows[scan->keynr]) / prev_records;
1510
1512
  }
1511
 
  return(selectivity_mult);
 
1513
  return selectivity_mult;
1512
1514
}
1513
1515
 
1514
1516
 
1569
1571
      each record of every scan. Assuming 1/TIME_FOR_COMPARE_ROWID
1570
1572
      per check this gives us:
1571
1573
    */
1572
 
    info->index_scan_costs += rows2double(info->index_records) /
 
1574
    info->index_scan_costs += static_cast<double>(info->index_records) /
1573
1575
                              TIME_FOR_COMPARE_ROWID;
1574
1576
  }
1575
1577
  else
1588
1590
  if (! info->is_covering)
1589
1591
  {
1590
1592
    optimizer::CostVector sweep_cost;
1591
 
    Join *join= info->param->session->lex->select_lex.join;
 
1593
    Join *join= info->param->session->lex().select_lex.join;
1592
1594
    bool is_interrupted= test(join && join->tables == 1);
1593
1595
    get_sweep_read_cost(info->param->table, double2rows(info->out_rows),
1594
1596
                        is_interrupted, &sweep_cost);
1702
1704
    cost total_cost.
1703
1705
  */
1704
1706
  /* Add priority queue use cost. */
1705
 
  total_cost += rows2double(records)*
 
1707
  total_cost += static_cast<double>(records) *
1706
1708
                log((double)(ror_scan_mark - tree->ror_scans)) /
1707
1709
                (TIME_FOR_COMPARE_ROWID * M_LN2);
1708
1710
 
2533
2535
  Item_equal *item_equal= field_item->item_equal;
2534
2536
  if (item_equal)
2535
2537
  {
2536
 
    Item_equal_iterator it(*item_equal);
 
2538
    Item_equal_iterator it(item_equal->begin());
2537
2539
    Item_field *item;
2538
2540
    while ((item= it++))
2539
2541
    {
2564
2566
 
2565
2567
  if (cond->type() == Item::COND_ITEM)
2566
2568
  {
2567
 
    List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
 
2569
    List<Item>::iterator li(((Item_cond*) cond)->argument_list()->begin());
2568
2570
 
2569
2571
    if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
2570
2572
    {
2688
2690
    Item_equal *item_equal= (Item_equal *) cond;
2689
2691
    if (!(value= item_equal->get_const()))
2690
2692
      return 0;
2691
 
    Item_equal_iterator it(*item_equal);
 
2693
    Item_equal_iterator it(item_equal->begin());
2692
2694
    ref_tables= value->used_tables();
2693
2695
    while ((field_item= it++))
2694
2696
    {
2976
2978
   * it is, then we must convert to the highest Timestamp value (or lowest,
2977
2979
   * depending on whether the datetime is before or after the epoch.
2978
2980
   */
2979
 
  if (field->type() == DRIZZLE_TYPE_TIMESTAMP)
 
2981
  if (field->is_timestamp())
2980
2982
  {
2981
2983
    /*
2982
2984
     * The left-side of the range comparison is a timestamp field.  Therefore,
3115
3117
               (value->val_int() < 0))
3116
3118
        type = Item_func::GE_FUNC;
3117
3119
    }
 
3120
    else if (err == 1)
 
3121
    {
 
3122
      tree= new (alloc) optimizer::SEL_ARG(field, 0, 0);
 
3123
      tree->type= optimizer::SEL_ARG::IMPOSSIBLE;
 
3124
      goto end;
 
3125
    }
3118
3126
  }
3119
3127
  else if (err < 0)
3120
3128
  {
3257
3265
 
3258
3266
#define CLONE_KEY1_MAYBE 1
3259
3267
#define CLONE_KEY2_MAYBE 2
3260
 
#define swap_clone_flag(A) ((A & 1) << 1) | ((A & 2) >> 1)
3261
3268
 
 
3269
static uint32_t swap_clone_flag(uint32_t a)
 
3270
{
 
3271
  return ((a & 1) << 1) | ((a & 2) >> 1);
 
3272
}
3262
3273
 
3263
3274
static optimizer::SEL_TREE *
3264
3275
tree_and(optimizer::RangeParameter *param, optimizer::SEL_TREE *tree1, optimizer::SEL_TREE *tree2)
3310
3321
  /* dispose index_merge if there is a "range" option */
3311
3322
  if (result_keys.any())
3312
3323
  {
3313
 
    tree1->merges.empty();
 
3324
    tree1->merges.clear();
3314
3325
    return(tree1);
3315
3326
  }
3316
3327
 
3332
3343
  optimizer::SEL_ARG *next= NULL;
3333
3344
  ulong use_count=key1->use_count;
3334
3345
 
3335
 
  if (key1->elements != 1)
 
3346
  if (key1->size() != 1)
3336
3347
  {
3337
 
    key2->use_count+=key1->elements-1; //psergey: why we don't count that key1 has n-k-p?
3338
 
    key2->increment_use_count((int) key1->elements-1);
 
3348
    key2->use_count+=key1->size()-1; //psergey: why we don't count that key1 has n-k-p?
 
3349
    key2->increment_use_count((int) key1->size()-1);
3339
3350
  }
3340
3351
  if (key1->type == optimizer::SEL_ARG::MAYBE_KEY)
3341
3352
  {
3855
3866
      !(pk_is_clustered && keynr == param->table->getShare()->getPrimaryKey()))
3856
3867
     *mrr_flags |= HA_MRR_INDEX_ONLY;
3857
3868
 
3858
 
  if (session->lex->sql_command != SQLCOM_SELECT)
 
3869
  if (session->lex().sql_command != SQLCOM_SELECT)
3859
3870
    *mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
3860
3871
 
3861
3872
  *bufsize= param->session->variables.read_rnd_buff_size;
4160
4171
  set_if_bigger(quick->max_used_key_length, (uint32_t)range->min_length);
4161
4172
  set_if_bigger(quick->max_used_key_length, (uint32_t)range->max_length);
4162
4173
  set_if_bigger(quick->used_key_parts, (uint32_t) key_tree->part+1);
4163
 
  if (insert_dynamic(&quick->ranges, (unsigned char*) &range))
4164
 
  {
4165
 
    return 1;
4166
 
  }
 
4174
  quick->ranges.push_back(&range);
4167
4175
 
4168
4176
 end:
4169
4177
  if (key_tree->right != &optimizer::null_element)
4287
4295
    key_part->null_bit=     key_info->key_part[part].null_bit;
4288
4296
    key_part->flag=         (uint8_t) key_info->key_part[part].key_part_flag;
4289
4297
  }
4290
 
  if (insert_dynamic(&quick->ranges,(unsigned char*)&range))
4291
 
    goto err;
 
4298
  quick->ranges.push_back(&range);
4292
4299
 
4293
4300
  /*
4294
4301
     Add a NULL range if REF_OR_NULL optimization is used.
4308
4315
                                 make_prev_keypart_map(ref->key_parts), EQ_RANGE)))
4309
4316
      goto err;
4310
4317
    *ref->null_ref_key= 0;              // Clear null byte
4311
 
    if (insert_dynamic(&quick->ranges,(unsigned char*)&null_range))
4312
 
      goto err;
 
4318
    quick->ranges.push_back(&null_range);
4313
4319
  }
4314
4320
 
4315
4321
  /* Call multi_range_read_info() to get the MRR flags and buffer size */
4316
4322
  quick->mrr_flags= HA_MRR_NO_ASSOCIATION |
4317
4323
                    (table->key_read ? HA_MRR_INDEX_ONLY : 0);
4318
 
  if (session->lex->sql_command != SQLCOM_SELECT)
 
4324
  if (session->lex().sql_command != SQLCOM_SELECT)
4319
4325
    quick->mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
4320
4326
 
4321
4327
  quick->mrr_buf_size= session->variables.read_rnd_buff_size;
4350
4356
  quick->qr_traversal_ctx.first=  (optimizer::QuickRange**)quick->ranges.buffer;
4351
4357
  quick->qr_traversal_ctx.cur=    (optimizer::QuickRange**)quick->ranges.buffer;
4352
4358
  quick->qr_traversal_ctx.last=   quick->qr_traversal_ctx.cur +
4353
 
                                  quick->ranges.elements;
 
4359
                                  quick->ranges.size();
4354
4360
  return &quick->qr_traversal_ctx;
4355
4361
}
4356
4362
 
4563
4569
get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree)
4564
4570
{
4565
4571
  Session *session= param->session;
4566
 
  Join *join= session->lex->current_select->join;
 
4572
  Join *join= session->lex().current_select->join;
4567
4573
  Table *table= param->table;
4568
4574
  bool have_min= false;              /* true if there is a MIN function. */
4569
4575
  bool have_max= false;              /* true if there is a MAX function. */
4595
4601
    return NULL;
4596
4602
 
4597
4603
  /* Analyze the query in more detail. */
4598
 
  List_iterator<Item> select_items_it(join->fields_list);
 
4604
  List<Item>::iterator select_items_it(join->fields_list.begin());
4599
4605
 
4600
4606
  /* Check (SA1,SA4) and store the only MIN/MAX argument - the C attribute.*/
4601
4607
  if (join->make_sum_func_list(join->all_fields, join->fields_list, 1))
4751
4757
    */
4752
4758
    else if (join->select_distinct)
4753
4759
    {
4754
 
      select_items_it.rewind();
 
4760
      select_items_it= join->fields_list.begin();
4755
4761
      used_key_parts_map.reset();
4756
4762
      uint32_t max_key_part= 0;
4757
4763
      while ((item= select_items_it++))
4765
4771
        */
4766
4772
        if (used_key_parts_map.test(key_part_nr))
4767
4773
          continue;
4768
 
        if (key_part_nr < 1 || key_part_nr > join->fields_list.elements)
 
4774
        if (key_part_nr < 1 || key_part_nr > join->fields_list.size())
4769
4775
          goto next_index;
4770
4776
        cur_part= cur_index_info->key_part + key_part_nr - 1;
4771
4777
        cur_group_prefix_len+= cur_part->store_length;
5032
5038
  Item::Type cond_type= cond->type();
5033
5039
  if (cond_type == Item::COND_ITEM) /* 'AND' or 'OR' */
5034
5040
  {
5035
 
    List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
 
5041
    List<Item>::iterator li(((Item_cond*) cond)->argument_list()->begin());
5036
5042
    Item *and_or_arg= NULL;
5037
5043
    while ((and_or_arg= li++))
5038
5044
    {
5467
5473
  optimizer::QuickGroupMinMaxSelect *quick= NULL;
5468
5474
 
5469
5475
  quick= new optimizer::QuickGroupMinMaxSelect(param->table,
5470
 
                                               param->session->lex->current_select->join,
 
5476
                                               param->session->lex().current_select->join,
5471
5477
                                               have_min,
5472
5478
                                               have_max,
5473
5479
                                               min_max_arg_part,