← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/optimizer/range.cc

  • Committer: Brian Aker
  • Date: 2011-02-22 06:12:02 UTC
  • mfrom: (2190.1.6 drizzle-build)
  • Revision ID: brian@tangent.org-20110222061202-k03czxykqy4x9hjs
List update, header fixes, multiple symbols, and David deletes some code.

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
 
 
141
#include <drizzled/unique.h>
 
142
 
 
143
#include <drizzled/temporal.h> /* Needed in get_mm_leaf() for timestamp -> datetime comparisons */
139
144
 
140
145
using namespace std;
141
146
namespace drizzled
213
218
  else
214
219
  {
215
220
    double n_blocks=
216
 
      ceil(uint64_t2double(table->cursor->stats.data_file_length) / IO_SIZE);
 
221
      ceil(static_cast<double>(table->cursor->stats.data_file_length) / IO_SIZE);
217
222
    double busy_blocks=
218
 
      n_blocks * (1.0 - pow(1.0 - 1.0/n_blocks, rows2double(nrows)));
 
223
      n_blocks * (1.0 - pow(1.0 - 1.0/n_blocks, static_cast<double>(nrows)));
219
224
    if (busy_blocks < 1.0)
220
225
      busy_blocks= 1.0;
221
226
 
348
353
  {
349
354
    return 0;
350
355
  }
351
 
  if (! (select= new optimizer::SqlSelect))
 
356
  if (! (select= new optimizer::SqlSelect()))
352
357
  {
353
358
    *error= 1;                  // out of memory
354
359
    return 0;
397
402
    delete cond;
398
403
    cond= 0;
399
404
  }
400
 
  close_cached_file(file);
 
405
  file->close_cached_file();
401
406
}
402
407
 
403
408
 
464
469
    MAX_KEY if no such index was found.
465
470
*/
466
471
 
467
 
uint32_t optimizer::get_index_for_order(Table *table, order_st *order, ha_rows limit)
 
472
uint32_t optimizer::get_index_for_order(Table *table, Order *order, ha_rows limit)
468
473
{
469
474
  uint32_t idx;
470
475
  uint32_t match_key= MAX_KEY, match_key_len= MAX_KEY_LENGTH + 1;
471
 
  order_st *ord;
 
476
  Order *ord;
472
477
 
473
478
  for (ord= order; ord; ord= ord->next)
474
479
    if (!ord->asc)
737
742
    {
738
743
      int key_for_use= head->find_shortest_key(&head->covering_keys);
739
744
      double key_read_time=
740
 
        param.table->cursor->index_only_read_time(key_for_use,
741
 
                                                rows2double(records)) +
 
745
        param.table->cursor->index_only_read_time(key_for_use, records) +
742
746
        (double) records / TIME_FOR_COMPARE;
743
747
      if (key_read_time < read_time)
744
748
        read_time= key_read_time;
808
812
          objects are not allowed so don't use ROR-intersection for
809
813
          table deletes.
810
814
        */
811
 
        if ((session->lex->sql_command != SQLCOM_DELETE))
 
815
        if ((session->getLex()->sql_command != SQLCOM_DELETE))
812
816
        {
813
817
          /*
814
818
            Get best non-covering ROR-intersection plan and prepare data for
836
840
        optimizer::SEL_IMERGE *imerge= NULL;
837
841
        optimizer::TableReadPlan *best_conj_trp= NULL;
838
842
        optimizer::TableReadPlan *new_conj_trp= NULL;
839
 
        List_iterator_fast<optimizer::SEL_IMERGE> it(tree->merges);
 
843
        List<optimizer::SEL_IMERGE>::iterator it(tree->merges.begin());
840
844
        while ((imerge= it++))
841
845
        {
842
846
          new_conj_trp= get_best_disjunct_quick(session, &param, imerge, best_read_time);
1041
1045
  /* Calculate cost(rowid_to_row_scan) */
1042
1046
  {
1043
1047
    optimizer::CostVector sweep_cost;
1044
 
    Join *join= param->session->lex->select_lex.join;
 
1048
    Join *join= param->session->getLex()->select_lex.join;
1045
1049
    bool is_interrupted= test(join && join->tables == 1);
1046
1050
    get_sweep_read_cost(param->table, non_cpk_scan_records, is_interrupted,
1047
1051
                        &sweep_cost);
1084
1088
  }
1085
1089
 
1086
1090
build_ror_index_merge:
1087
 
  if (!all_scans_ror_able || param->session->lex->sql_command == SQLCOM_DELETE)
 
1091
  if (!all_scans_ror_able || param->session->getLex()->sql_command == SQLCOM_DELETE)
1088
1092
    return(imerge_trp);
1089
1093
 
1090
1094
  /* Ok, it is possible to build a ROR-union, try it. */
1117
1121
      cost= param->table->cursor->
1118
1122
              read_time(param->real_keynr[(*cur_child)->key_idx], 1,
1119
1123
                        (*cur_child)->records) +
1120
 
              rows2double((*cur_child)->records) / TIME_FOR_COMPARE;
 
1124
              static_cast<double>((*cur_child)->records) / TIME_FOR_COMPARE;
1121
1125
    }
1122
1126
    else
1123
1127
      cost= read_time;
1159
1163
  double roru_total_cost;
1160
1164
  {
1161
1165
    optimizer::CostVector sweep_cost;
1162
 
    Join *join= param->session->lex->select_lex.join;
 
1166
    Join *join= param->session->getLex()->select_lex.join;
1163
1167
    bool is_interrupted= test(join && join->tables == 1);
1164
1168
    get_sweep_read_cost(param->table, roru_total_records, is_interrupted,
1165
1169
                        &sweep_cost);
1166
1170
    roru_total_cost= roru_index_costs +
1167
 
                     rows2double(roru_total_records)*log((double)n_child_scans) /
 
1171
                     static_cast<double>(roru_total_records)*log((double)n_child_scans) /
1168
1172
                     (TIME_FOR_COMPARE_ROWID * M_LN2) +
1169
1173
                     sweep_cost.total_cost();
1170
1174
  }
1230
1234
    if (param->needed_fields.test(key_part->fieldnr-1))
1231
1235
      tmp_bitset.set(key_part->fieldnr-1);
1232
1236
  }
1233
 
  double rows= rows2double(param->table->quick_rows[ror_scan->keynr]);
 
1237
  double rows= param->table->quick_rows[ror_scan->keynr];
1234
1238
  ror_scan->index_read_cost=
1235
1239
    param->table->cursor->index_only_read_time(ror_scan->keynr, rows);
1236
1240
  ror_scan->covered_fields= tmp_bitset.to_ulong();
1253
1257
 
1254
1258
static int cmp_ror_scan_info(optimizer::RorScanInfo** a, optimizer::RorScanInfo** b)
1255
1259
{
1256
 
  double val1= rows2double((*a)->records) * (*a)->key_rec_length;
1257
 
  double val2= rows2double((*b)->records) * (*b)->key_rec_length;
 
1260
  double val1= static_cast<double>((*a)->records) * (*a)->key_rec_length;
 
1261
  double val2= static_cast<double>((*b)->records) * (*b)->key_rec_length;
1258
1262
  return (val1 < val2)? -1: (val1 == val2)? 0 : 1;
1259
1263
}
1260
1264
 
1490
1494
      if (cur_covered)
1491
1495
      {
1492
1496
        /* uncovered -> covered */
1493
 
        double tmp= rows2double(records)/rows2double(prev_records);
1494
 
        selectivity_mult *= tmp;
 
1497
        selectivity_mult *= static_cast<double>(records) / prev_records;
1495
1498
        prev_records= HA_POS_ERROR;
1496
1499
      }
1497
1500
      else
1504
1507
  }
1505
1508
  if (!prev_covered)
1506
1509
  {
1507
 
    double tmp= rows2double(info->param->table->quick_rows[scan->keynr]) /
1508
 
                rows2double(prev_records);
1509
 
    selectivity_mult *= tmp;
 
1510
    selectivity_mult *= static_cast<double>(info->param->table->quick_rows[scan->keynr]) / prev_records;
1510
1511
  }
1511
 
  return(selectivity_mult);
 
1512
  return selectivity_mult;
1512
1513
}
1513
1514
 
1514
1515
 
1569
1570
      each record of every scan. Assuming 1/TIME_FOR_COMPARE_ROWID
1570
1571
      per check this gives us:
1571
1572
    */
1572
 
    info->index_scan_costs += rows2double(info->index_records) /
 
1573
    info->index_scan_costs += static_cast<double>(info->index_records) /
1573
1574
                              TIME_FOR_COMPARE_ROWID;
1574
1575
  }
1575
1576
  else
1588
1589
  if (! info->is_covering)
1589
1590
  {
1590
1591
    optimizer::CostVector sweep_cost;
1591
 
    Join *join= info->param->session->lex->select_lex.join;
 
1592
    Join *join= info->param->session->getLex()->select_lex.join;
1592
1593
    bool is_interrupted= test(join && join->tables == 1);
1593
1594
    get_sweep_read_cost(info->param->table, double2rows(info->out_rows),
1594
1595
                        is_interrupted, &sweep_cost);
1702
1703
    cost total_cost.
1703
1704
  */
1704
1705
  /* Add priority queue use cost. */
1705
 
  total_cost += rows2double(records)*
 
1706
  total_cost += static_cast<double>(records) *
1706
1707
                log((double)(ror_scan_mark - tree->ror_scans)) /
1707
1708
                (TIME_FOR_COMPARE_ROWID * M_LN2);
1708
1709
 
2564
2565
 
2565
2566
  if (cond->type() == Item::COND_ITEM)
2566
2567
  {
2567
 
    List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
 
2568
    List<Item>::iterator li(((Item_cond*) cond)->argument_list()->begin());
2568
2569
 
2569
2570
    if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
2570
2571
    {
2976
2977
   * it is, then we must convert to the highest Timestamp value (or lowest,
2977
2978
   * depending on whether the datetime is before or after the epoch.
2978
2979
   */
2979
 
  if (field->type() == DRIZZLE_TYPE_TIMESTAMP)
 
2980
  if (field->is_timestamp())
2980
2981
  {
2981
2982
    /*
2982
2983
     * The left-side of the range comparison is a timestamp field.  Therefore,
3257
3258
 
3258
3259
#define CLONE_KEY1_MAYBE 1
3259
3260
#define CLONE_KEY2_MAYBE 2
3260
 
#define swap_clone_flag(A) ((A & 1) << 1) | ((A & 2) >> 1)
3261
3261
 
 
3262
static uint32_t swap_clone_flag(uint32_t a)
 
3263
{
 
3264
  return ((a & 1) << 1) | ((a & 2) >> 1);
 
3265
}
3262
3266
 
3263
3267
static optimizer::SEL_TREE *
3264
3268
tree_and(optimizer::RangeParameter *param, optimizer::SEL_TREE *tree1, optimizer::SEL_TREE *tree2)
3310
3314
  /* dispose index_merge if there is a "range" option */
3311
3315
  if (result_keys.any())
3312
3316
  {
3313
 
    tree1->merges.empty();
 
3317
    tree1->merges.clear();
3314
3318
    return(tree1);
3315
3319
  }
3316
3320
 
3855
3859
      !(pk_is_clustered && keynr == param->table->getShare()->getPrimaryKey()))
3856
3860
     *mrr_flags |= HA_MRR_INDEX_ONLY;
3857
3861
 
3858
 
  if (session->lex->sql_command != SQLCOM_SELECT)
 
3862
  if (session->getLex()->sql_command != SQLCOM_SELECT)
3859
3863
    *mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
3860
3864
 
3861
3865
  *bufsize= param->session->variables.read_rnd_buff_size;
4315
4319
  /* Call multi_range_read_info() to get the MRR flags and buffer size */
4316
4320
  quick->mrr_flags= HA_MRR_NO_ASSOCIATION |
4317
4321
                    (table->key_read ? HA_MRR_INDEX_ONLY : 0);
4318
 
  if (session->lex->sql_command != SQLCOM_SELECT)
 
4322
  if (session->getLex()->sql_command != SQLCOM_SELECT)
4319
4323
    quick->mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
4320
4324
 
4321
4325
  quick->mrr_buf_size= session->variables.read_rnd_buff_size;
4563
4567
get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree)
4564
4568
{
4565
4569
  Session *session= param->session;
4566
 
  Join *join= session->lex->current_select->join;
 
4570
  Join *join= session->getLex()->current_select->join;
4567
4571
  Table *table= param->table;
4568
4572
  bool have_min= false;              /* true if there is a MIN function. */
4569
4573
  bool have_max= false;              /* true if there is a MAX function. */
4578
4582
  uint32_t key_infix_len= 0;          /* Length of key_infix. */
4579
4583
  optimizer::GroupMinMaxReadPlan *read_plan= NULL; /* The eventually constructed TRP. */
4580
4584
  uint32_t key_part_nr;
4581
 
  order_st *tmp_group= NULL;
 
4585
  Order *tmp_group= NULL;
4582
4586
  Item *item= NULL;
4583
4587
  Item_field *item_field= NULL;
4584
4588
 
4595
4599
    return NULL;
4596
4600
 
4597
4601
  /* Analyze the query in more detail. */
4598
 
  List_iterator<Item> select_items_it(join->fields_list);
 
4602
  List<Item>::iterator select_items_it(join->fields_list.begin());
4599
4603
 
4600
4604
  /* Check (SA1,SA4) and store the only MIN/MAX argument - the C attribute.*/
4601
4605
  if (join->make_sum_func_list(join->all_fields, join->fields_list, 1))
4751
4755
    */
4752
4756
    else if (join->select_distinct)
4753
4757
    {
4754
 
      select_items_it.rewind();
 
4758
      select_items_it= join->fields_list.begin();
4755
4759
      used_key_parts_map.reset();
4756
4760
      uint32_t max_key_part= 0;
4757
4761
      while ((item= select_items_it++))
5032
5036
  Item::Type cond_type= cond->type();
5033
5037
  if (cond_type == Item::COND_ITEM) /* 'AND' or 'OR' */
5034
5038
  {
5035
 
    List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
 
5039
    List<Item>::iterator li(((Item_cond*) cond)->argument_list()->begin());
5036
5040
    Item *and_or_arg= NULL;
5037
5041
    while ((and_or_arg= li++))
5038
5042
    {
5467
5471
  optimizer::QuickGroupMinMaxSelect *quick= NULL;
5468
5472
 
5469
5473
  quick= new optimizer::QuickGroupMinMaxSelect(param->table,
5470
 
                                               param->session->lex->current_select->join,
 
5474
                                               param->session->getLex()->current_select->join,
5471
5475
                                               have_min,
5472
5476
                                               have_max,
5473
5477
                                               min_max_arg_part,