← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/optimizer/range.cc

  • Committer: lbieber
  • Date: 2010-10-02 19:48:35 UTC
  • mfrom: (1730.6.19 drizzle-make-lcov)
  • Revision ID: lbieber@orisndriz08-20101002194835-q5zd9qc4lvx1xnfo
Merge Hartmut - clean up lex, now require flex to build, also "make lcov" improvements

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, Inc.
 
4
 *  Copyright (C) 2008-2009 Sun Microsystems
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
109
109
#include <vector>
110
110
#include <algorithm>
111
111
 
112
 
#include <boost/dynamic_bitset.hpp>
113
 
 
114
 
#include "drizzled/check_stack_overrun.h"
 
112
#include "drizzled/sql_base.h"
 
113
#include "drizzled/sql_select.h"
115
114
#include "drizzled/error.h"
 
115
#include "drizzled/optimizer/cost_vector.h"
 
116
#include "drizzled/item/cmpfunc.h"
116
117
#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"
 
118
#include "drizzled/check_stack_overrun.h"
 
119
#include "drizzled/optimizer/sum.h"
 
120
#include "drizzled/optimizer/range.h"
 
121
#include "drizzled/optimizer/quick_range.h"
 
122
#include "drizzled/optimizer/quick_range_select.h"
121
123
#include "drizzled/optimizer/quick_group_min_max_select.h"
122
124
#include "drizzled/optimizer/quick_index_merge_select.h"
123
 
#include "drizzled/optimizer/quick_range.h"
124
 
#include "drizzled/optimizer/quick_range_select.h"
125
125
#include "drizzled/optimizer/quick_ror_intersect_select.h"
126
126
#include "drizzled/optimizer/quick_ror_union_select.h"
127
 
#include "drizzled/optimizer/range.h"
128
 
#include "drizzled/optimizer/range_param.h"
 
127
#include "drizzled/optimizer/table_read_plan.h"
129
128
#include "drizzled/optimizer/sel_arg.h"
130
129
#include "drizzled/optimizer/sel_imerge.h"
131
130
#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"
 
131
#include "drizzled/optimizer/range_param.h"
135
132
#include "drizzled/records.h"
136
 
#include "drizzled/sql_base.h"
137
 
#include "drizzled/sql_select.h"
138
 
#include "drizzled/table_reference.h"
 
133
#include "drizzled/internal/my_sys.h"
 
134
#include "drizzled/internal/iocache.h"
139
135
 
140
136
#include "drizzled/temporal.h" /* Needed in get_mm_leaf() for timestamp -> datetime comparisons */
141
137
 
232
228
  }
233
229
}
234
230
 
 
231
struct st_ror_scan_info;
 
232
 
235
233
static optimizer::SEL_TREE * get_mm_parts(optimizer::RangeParameter *param,
236
234
                               COND *cond_func,
237
235
                               Field *field,
350
348
  {
351
349
    return 0;
352
350
  }
353
 
  if (! (select= new optimizer::SqlSelect()))
 
351
  if (! (select= new optimizer::SqlSelect))
354
352
  {
355
353
    *error= 1;                  // out of memory
356
354
    return 0;
399
397
    delete cond;
400
398
    cond= 0;
401
399
  }
402
 
  file->close_cached_file();
 
400
  close_cached_file(file);
403
401
}
404
402
 
405
403
 
466
464
    MAX_KEY if no such index was found.
467
465
*/
468
466
 
469
 
uint32_t optimizer::get_index_for_order(Table *table, Order *order, ha_rows limit)
 
467
uint32_t optimizer::get_index_for_order(Table *table, order_st *order, ha_rows limit)
470
468
{
471
469
  uint32_t idx;
472
470
  uint32_t match_key= MAX_KEY, match_key_len= MAX_KEY_LENGTH + 1;
473
 
  Order *ord;
 
471
  order_st *ord;
474
472
 
475
473
  for (ord= order; ord; ord= ord->next)
476
474
    if (!ord->asc)
545
543
static int fill_used_fields_bitmap(optimizer::Parameter *param)
546
544
{
547
545
  Table *table= param->table;
 
546
  my_bitmap_map *tmp;
548
547
  uint32_t pk;
549
 
  param->tmp_covered_fields.clear();
550
 
  param->needed_fields.resize(table->getShare()->sizeFields());
551
 
  param->needed_fields.reset();
 
548
  param->tmp_covered_fields.setBitmap(0);
 
549
  param->fields_bitmap_size= table->getShare()->column_bitmap_size;
 
550
  if (!(tmp= (my_bitmap_map*) param->mem_root->alloc_root(param->fields_bitmap_size)) ||
 
551
      param->needed_fields.init(tmp, table->getShare()->sizeFields()))
 
552
  {
 
553
    return 1;
 
554
  }
552
555
 
553
 
  param->needed_fields|= *table->read_set;
554
 
  param->needed_fields|= *table->write_set;
 
556
  param->needed_fields= *table->read_set;
 
557
  bitmap_union(&param->needed_fields, table->write_set);
555
558
 
556
559
  pk= param->table->getShare()->getPrimaryKey();
557
560
  if (pk != MAX_KEY && param->table->cursor->primary_key_is_clustered())
561
564
    KeyPartInfo *key_part_end= key_part +
562
565
                                 param->table->key_info[pk].key_parts;
563
566
    for (;key_part != key_part_end; ++key_part)
564
 
      param->needed_fields.reset(key_part->fieldnr-1);
 
567
      param->needed_fields.clearBit(key_part->fieldnr-1);
565
568
  }
566
569
  return 0;
567
570
}
1187
1190
}
1188
1191
 
1189
1192
 
 
1193
typedef struct st_ror_scan_info
 
1194
{
 
1195
  uint32_t      idx;      /* # of used key in param->keys */
 
1196
  uint32_t      keynr;    /* # of used key in table */
 
1197
  ha_rows   records;  /* estimate of # records this scan will return */
 
1198
 
 
1199
  /* Set of intervals over key fields that will be used for row retrieval. */
 
1200
  optimizer::SEL_ARG   *sel_arg;
 
1201
 
 
1202
  /* Fields used in the query and covered by this ROR scan. */
 
1203
  MyBitmap covered_fields;
 
1204
  uint32_t      used_fields_covered; /* # of set bits in covered_fields */
 
1205
  int       key_rec_length; /* length of key record (including rowid) */
 
1206
 
 
1207
  /*
 
1208
    Cost of reading all index records with values in sel_arg intervals set
 
1209
    (assuming there is no need to access full table records)
 
1210
  */
 
1211
  double    index_read_cost;
 
1212
  uint32_t      first_uncovered_field; /* first unused bit in covered_fields */
 
1213
  uint32_t      key_components; /* # of parts in the key */
 
1214
} ROR_SCAN_INFO;
 
1215
 
1190
1216
 
1191
1217
/*
1192
 
  Create optimizer::RorScanInfo* structure with a single ROR scan on index idx using
 
1218
  Create ROR_SCAN_INFO* structure with a single ROR scan on index idx using
1193
1219
  sel_arg set of intervals.
1194
1220
 
1195
1221
  SYNOPSIS
1204
1230
*/
1205
1231
 
1206
1232
static
1207
 
optimizer::RorScanInfo *make_ror_scan(const optimizer::Parameter *param, int idx, optimizer::SEL_ARG *sel_arg)
 
1233
ROR_SCAN_INFO *make_ror_scan(const optimizer::Parameter *param, int idx, optimizer::SEL_ARG *sel_arg)
1208
1234
{
1209
 
  optimizer::RorScanInfo *ror_scan= NULL;
 
1235
  ROR_SCAN_INFO *ror_scan;
 
1236
  my_bitmap_map *bitmap_buf;
1210
1237
 
1211
1238
  uint32_t keynr;
1212
1239
 
1213
 
  if (!(ror_scan= (optimizer::RorScanInfo*)param->mem_root->alloc_root(sizeof(optimizer::RorScanInfo))))
 
1240
  if (!(ror_scan= (ROR_SCAN_INFO*)param->mem_root->alloc_root(sizeof(ROR_SCAN_INFO))))
1214
1241
    return NULL;
1215
1242
 
1216
1243
  ror_scan->idx= idx;
1220
1247
  ror_scan->sel_arg= sel_arg;
1221
1248
  ror_scan->records= param->table->quick_rows[keynr];
1222
1249
 
1223
 
  ror_scan->covered_fields_size= param->table->getShare()->sizeFields();
1224
 
  boost::dynamic_bitset<> tmp_bitset(param->table->getShare()->sizeFields());
1225
 
  tmp_bitset.reset();
 
1250
  if (!(bitmap_buf= (my_bitmap_map*) param->mem_root->alloc_root(param->fields_bitmap_size)))
 
1251
  {
 
1252
    return NULL;
 
1253
  }
 
1254
 
 
1255
  if (ror_scan->covered_fields.init(bitmap_buf, param->table->getShare()->sizeFields()))
 
1256
  {
 
1257
    return NULL;
 
1258
  }
 
1259
  ror_scan->covered_fields.clearAll();
1226
1260
 
1227
1261
  KeyPartInfo *key_part= param->table->key_info[keynr].key_part;
1228
1262
  KeyPartInfo *key_part_end= key_part +
1229
1263
                               param->table->key_info[keynr].key_parts;
1230
 
  for (; key_part != key_part_end; ++key_part)
 
1264
  for (;key_part != key_part_end; ++key_part)
1231
1265
  {
1232
 
    if (param->needed_fields.test(key_part->fieldnr-1))
1233
 
      tmp_bitset.set(key_part->fieldnr-1);
 
1266
    if (param->needed_fields.isBitSet(key_part->fieldnr-1))
 
1267
      ror_scan->covered_fields.setBit(key_part->fieldnr-1);
1234
1268
  }
1235
1269
  double rows= rows2double(param->table->quick_rows[ror_scan->keynr]);
1236
1270
  ror_scan->index_read_cost=
1237
1271
    param->table->cursor->index_only_read_time(ror_scan->keynr, rows);
1238
 
  ror_scan->covered_fields= tmp_bitset.to_ulong();
1239
 
  return ror_scan;
 
1272
  return(ror_scan);
1240
1273
}
1241
1274
 
1242
1275
 
1243
1276
/*
1244
 
  Compare two optimizer::RorScanInfo** by  E(#records_matched) * key_record_length.
 
1277
  Compare two ROR_SCAN_INFO** by  E(#records_matched) * key_record_length.
1245
1278
  SYNOPSIS
1246
1279
    cmp_ror_scan_info()
1247
1280
      a ptr to first compared value
1253
1286
    1 a > b
1254
1287
*/
1255
1288
 
1256
 
static int cmp_ror_scan_info(optimizer::RorScanInfo** a, optimizer::RorScanInfo** b)
 
1289
static int cmp_ror_scan_info(ROR_SCAN_INFO** a, ROR_SCAN_INFO** b)
1257
1290
{
1258
1291
  double val1= rows2double((*a)->records) * (*a)->key_rec_length;
1259
1292
  double val2= rows2double((*b)->records) * (*b)->key_rec_length;
1262
1295
 
1263
1296
 
1264
1297
/*
1265
 
  Compare two optimizer::RorScanInfo** by
 
1298
  Compare two ROR_SCAN_INFO** by
1266
1299
   (#covered fields in F desc,
1267
1300
    #components asc,
1268
1301
    number of first not covered component asc)
1278
1311
    1 a > b
1279
1312
*/
1280
1313
 
1281
 
static int cmp_ror_scan_info_covering(optimizer::RorScanInfo** a, optimizer::RorScanInfo** b)
 
1314
static int cmp_ror_scan_info_covering(ROR_SCAN_INFO** a, ROR_SCAN_INFO** b)
1282
1315
{
1283
1316
  if ((*a)->used_fields_covered > (*b)->used_fields_covered)
1284
1317
    return -1;
1296
1329
}
1297
1330
 
1298
1331
/* Auxiliary structure for incremental ROR-intersection creation */
1299
 
typedef struct st_ror_intersect_info
 
1332
typedef struct
1300
1333
{
1301
 
  st_ror_intersect_info()
1302
 
    :
1303
 
      param(NULL),
1304
 
      covered_fields(),
1305
 
      out_rows(0.0),
1306
 
      is_covering(false),
1307
 
      index_records(0),
1308
 
      index_scan_costs(0.0),
1309
 
      total_cost(0.0)
1310
 
  {}
1311
 
 
1312
 
  st_ror_intersect_info(const optimizer::Parameter *in_param)
1313
 
    :
1314
 
      param(in_param),
1315
 
      covered_fields(in_param->table->getShare()->sizeFields()),
1316
 
      out_rows(in_param->table->cursor->stats.records),
1317
 
      is_covering(false),
1318
 
      index_records(0),
1319
 
      index_scan_costs(0.0),
1320
 
      total_cost(0.0)
1321
 
  {
1322
 
    covered_fields.reset();
1323
 
  }
1324
 
 
1325
1334
  const optimizer::Parameter *param;
1326
 
  boost::dynamic_bitset<> covered_fields; /* union of fields covered by all scans */
 
1335
  MyBitmap covered_fields; /* union of fields covered by all scans */
1327
1336
  /*
1328
1337
    Fraction of table records that satisfies conditions of all scans.
1329
1338
    This is the number of full records that will be retrieved if a
1339
1348
} ROR_INTERSECT_INFO;
1340
1349
 
1341
1350
 
 
1351
/*
 
1352
  Allocate a ROR_INTERSECT_INFO and initialize it to contain zero scans.
 
1353
 
 
1354
  SYNOPSIS
 
1355
    ror_intersect_init()
 
1356
      param         Parameter from test_quick_select
 
1357
 
 
1358
  RETURN
 
1359
    allocated structure
 
1360
    NULL on error
 
1361
*/
 
1362
 
 
1363
static
 
1364
ROR_INTERSECT_INFO* ror_intersect_init(const optimizer::Parameter *param)
 
1365
{
 
1366
  ROR_INTERSECT_INFO *info;
 
1367
  my_bitmap_map* buf;
 
1368
  if (!(info= (ROR_INTERSECT_INFO*)param->mem_root->alloc_root(sizeof(ROR_INTERSECT_INFO))))
 
1369
    return NULL;
 
1370
  info->param= param;
 
1371
  if (!(buf= (my_bitmap_map*) param->mem_root->alloc_root(param->fields_bitmap_size)))
 
1372
    return NULL;
 
1373
  if (info->covered_fields.init(buf, param->table->getShare()->sizeFields()))
 
1374
    return NULL;
 
1375
  info->is_covering= false;
 
1376
  info->index_scan_costs= 0.0;
 
1377
  info->index_records= 0;
 
1378
  info->out_rows= (double) param->table->cursor->stats.records;
 
1379
  info->covered_fields.clearAll();
 
1380
  return info;
 
1381
}
 
1382
 
1342
1383
static void ror_intersect_cpy(ROR_INTERSECT_INFO *dst,
1343
1384
                              const ROR_INTERSECT_INFO *src)
1344
1385
{
1443
1484
*/
1444
1485
 
1445
1486
static double ror_scan_selectivity(const ROR_INTERSECT_INFO *info,
1446
 
                                   const optimizer::RorScanInfo *scan)
 
1487
                                   const ROR_SCAN_INFO *scan)
1447
1488
{
1448
1489
  double selectivity_mult= 1.0;
1449
1490
  KeyPartInfo *key_part= info->param->table->key_info[scan->keynr].key_part;
1453
1494
  optimizer::SEL_ARG *tuple_arg= NULL;
1454
1495
  key_part_map keypart_map= 0;
1455
1496
  bool cur_covered;
1456
 
  bool prev_covered= test(info->covered_fields.test(key_part->fieldnr-1));
 
1497
  bool prev_covered= test(info->covered_fields.isBitSet(key_part->fieldnr-1));
1457
1498
  key_range min_range;
1458
1499
  key_range max_range;
1459
1500
  min_range.key= key_val;
1466
1507
       sel_arg= sel_arg->next_key_part)
1467
1508
  {
1468
1509
    cur_covered=
1469
 
      test(info->covered_fields.test(key_part[sel_arg->part].fieldnr-1));
 
1510
      test(info->covered_fields.isBitSet(key_part[sel_arg->part].fieldnr-1));
1470
1511
    if (cur_covered != prev_covered)
1471
1512
    {
1472
1513
      /* create (part1val, ..., part{n-1}val) tuple. */
1551
1592
*/
1552
1593
 
1553
1594
static bool ror_intersect_add(ROR_INTERSECT_INFO *info,
1554
 
                              optimizer::RorScanInfo* ror_scan, bool is_cpk_scan)
 
1595
                              ROR_SCAN_INFO* ror_scan, bool is_cpk_scan)
1555
1596
{
1556
1597
  double selectivity_mult= 1.0;
1557
1598
 
1578
1619
  {
1579
1620
    info->index_records += info->param->table->quick_rows[ror_scan->keynr];
1580
1621
    info->index_scan_costs += ror_scan->index_read_cost;
1581
 
    boost::dynamic_bitset<> tmp_bitset= ror_scan->bitsToBitset();
1582
 
    info->covered_fields|= tmp_bitset;
1583
 
    if (! info->is_covering && info->param->needed_fields.is_subset_of(info->covered_fields))
 
1622
    bitmap_union(&info->covered_fields, &ror_scan->covered_fields);
 
1623
    if (!info->is_covering && bitmap_is_subset(&info->param->needed_fields,
 
1624
                                               &info->covered_fields))
1584
1625
    {
1585
1626
      info->is_covering= true;
1586
1627
    }
1587
1628
  }
1588
1629
 
1589
1630
  info->total_cost= info->index_scan_costs;
1590
 
  if (! info->is_covering)
 
1631
  if (!info->is_covering)
1591
1632
  {
1592
1633
    optimizer::CostVector sweep_cost;
1593
1634
    Join *join= info->param->session->lex->select_lex.join;
1638
1679
                                                            optimizer::SEL_TREE *tree,
1639
1680
                                                            double read_time)
1640
1681
{
1641
 
  optimizer::RorScanInfo **ror_scan_mark;
1642
 
  optimizer::RorScanInfo **ror_scans_end= tree->ror_scans_end;
 
1682
  ROR_SCAN_INFO **ror_scan_mark;
 
1683
  ROR_SCAN_INFO **ror_scans_end= tree->ror_scans_end;
1643
1684
 
1644
 
  for (optimizer::RorScanInfo **scan= tree->ror_scans; scan != ror_scans_end; ++scan)
 
1685
  for (ROR_SCAN_INFO **scan= tree->ror_scans; scan != ror_scans_end; ++scan)
1645
1686
    (*scan)->key_components=
1646
1687
      param->table->key_info[(*scan)->keynr].key_parts;
1647
1688
 
1653
1694
  /*I=set of all covering indexes */
1654
1695
  ror_scan_mark= tree->ror_scans;
1655
1696
 
1656
 
  boost::dynamic_bitset<> *covered_fields= &param->tmp_covered_fields;
1657
 
  if (covered_fields->empty())
 
1697
  MyBitmap *covered_fields= &param->tmp_covered_fields;
 
1698
  if (! covered_fields->getBitmap())
1658
1699
  {
1659
 
    covered_fields->resize(param->table->getShare()->sizeFields());
 
1700
    my_bitmap_map *tmp_bitmap= (my_bitmap_map*)param->mem_root->alloc_root(param->fields_bitmap_size);
 
1701
    covered_fields->setBitmap(tmp_bitmap);
1660
1702
  }
1661
 
  covered_fields->reset();
 
1703
  if (! covered_fields->getBitmap() ||
 
1704
      covered_fields->init(covered_fields->getBitmap(),
 
1705
                           param->table->getShare()->sizeFields()))
 
1706
    return 0;
 
1707
  covered_fields->clearAll();
1662
1708
 
1663
1709
  double total_cost= 0.0f;
1664
1710
  ha_rows records=0;
1672
1718
        number of first not covered component
1673
1719
      Calculate and save these values for each of remaining scans.
1674
1720
    */
1675
 
    for (optimizer::RorScanInfo **scan= ror_scan_mark; scan != ror_scans_end; ++scan)
 
1721
    for (ROR_SCAN_INFO **scan= ror_scan_mark; scan != ror_scans_end; ++scan)
1676
1722
    {
1677
 
      /* subtract one bitset from the other */
1678
 
      (*scan)->subtractBitset(*covered_fields);
 
1723
      bitmap_subtract(&(*scan)->covered_fields, covered_fields);
1679
1724
      (*scan)->used_fields_covered=
1680
 
        (*scan)->getBitCount();
1681
 
      (*scan)->first_uncovered_field= (*scan)->findFirstNotSet();
 
1725
        (*scan)->covered_fields.getBitsSet();
 
1726
      (*scan)->first_uncovered_field=
 
1727
        (*scan)->covered_fields.getFirst();
1682
1728
    }
1683
1729
 
1684
1730
    internal::my_qsort(ror_scan_mark, ror_scans_end-ror_scan_mark,
1685
 
                       sizeof(optimizer::RorScanInfo*),
 
1731
                       sizeof(ROR_SCAN_INFO*),
1686
1732
                       (qsort_cmp)cmp_ror_scan_info_covering);
1687
1733
 
1688
1734
    /* I=I-first(I) */
1691
1737
    if (total_cost > read_time)
1692
1738
      return NULL;
1693
1739
    /* F=F-covered by first(I) */
1694
 
    boost::dynamic_bitset<> tmp_bitset= (*ror_scan_mark)->bitsToBitset();
1695
 
    *covered_fields|= tmp_bitset;
1696
 
    all_covered= param->needed_fields.is_subset_of(*covered_fields);
1697
 
  } while ((++ror_scan_mark < ror_scans_end) && ! all_covered);
 
1740
    bitmap_union(covered_fields, &(*ror_scan_mark)->covered_fields);
 
1741
    all_covered= bitmap_is_subset(&param->needed_fields, covered_fields);
 
1742
  } while ((++ror_scan_mark < ror_scans_end) && !all_covered);
1698
1743
 
1699
1744
  if (!all_covered || (ror_scan_mark - tree->ror_scans) == 1)
1700
1745
    return NULL;
1718
1763
  }
1719
1764
 
1720
1765
  uint32_t best_num= (ror_scan_mark - tree->ror_scans);
1721
 
  if (!(trp->first_scan= (optimizer::RorScanInfo**)param->mem_root->alloc_root(sizeof(optimizer::RorScanInfo*)* best_num)))
 
1766
  if (!(trp->first_scan= (ROR_SCAN_INFO**)param->mem_root->alloc_root(sizeof(ROR_SCAN_INFO*)* best_num)))
1722
1767
    return NULL;
1723
 
  memcpy(trp->first_scan, tree->ror_scans, best_num*sizeof(optimizer::RorScanInfo*));
 
1768
  memcpy(trp->first_scan, tree->ror_scans, best_num*sizeof(ROR_SCAN_INFO*));
1724
1769
  trp->last_scan=  trp->first_scan + best_num;
1725
1770
  trp->is_covering= true;
1726
1771
  trp->read_cost= total_cost;
1809
1854
    return NULL;
1810
1855
 
1811
1856
  /*
1812
 
    Step1: Collect ROR-able SEL_ARGs and create optimizer::RorScanInfo for each of
 
1857
    Step1: Collect ROR-able SEL_ARGs and create ROR_SCAN_INFO for each of
1813
1858
    them. Also find and save clustered PK scan if there is one.
1814
1859
  */
1815
 
  optimizer::RorScanInfo **cur_ror_scan= NULL;
1816
 
  optimizer::RorScanInfo *cpk_scan= NULL;
 
1860
  ROR_SCAN_INFO **cur_ror_scan= NULL;
 
1861
  ROR_SCAN_INFO *cpk_scan= NULL;
1817
1862
  uint32_t cpk_no= 0;
1818
1863
  bool cpk_scan_used= false;
1819
1864
 
1820
 
  if (! (tree->ror_scans= (optimizer::RorScanInfo**)param->mem_root->alloc_root(sizeof(optimizer::RorScanInfo*)* param->keys)))
 
1865
  if (! (tree->ror_scans= (ROR_SCAN_INFO**)param->mem_root->alloc_root(sizeof(ROR_SCAN_INFO*)* param->keys)))
1821
1866
  {
1822
1867
    return NULL;
1823
1868
  }
1826
1871
 
1827
1872
  for (idx= 0, cur_ror_scan= tree->ror_scans; idx < param->keys; idx++)
1828
1873
  {
1829
 
    optimizer::RorScanInfo *scan;
 
1874
    ROR_SCAN_INFO *scan;
1830
1875
    if (! tree->ror_scans_map.test(idx))
1831
1876
      continue;
1832
 
    if (! (scan= make_ror_scan(param, idx, tree->keys[idx])))
 
1877
    if (!(scan= make_ror_scan(param, idx, tree->keys[idx])))
1833
1878
      return NULL;
1834
1879
    if (param->real_keynr[idx] == cpk_no)
1835
1880
    {
1843
1888
  tree->ror_scans_end= cur_ror_scan;
1844
1889
  /*
1845
1890
    Ok, [ror_scans, ror_scans_end) is array of ptrs to initialized
1846
 
    optimizer::RorScanInfo's.
 
1891
    ROR_SCAN_INFO's.
1847
1892
    Step 2: Get best ROR-intersection using an approximate algorithm.
1848
1893
  */
1849
 
  internal::my_qsort(tree->ror_scans, tree->n_ror_scans, sizeof(optimizer::RorScanInfo*),
 
1894
  internal::my_qsort(tree->ror_scans, tree->n_ror_scans, sizeof(ROR_SCAN_INFO*),
1850
1895
                     (qsort_cmp)cmp_ror_scan_info);
1851
1896
 
1852
 
  optimizer::RorScanInfo **intersect_scans= NULL; /* ROR scans used in index intersection */
1853
 
  optimizer::RorScanInfo **intersect_scans_end= NULL;
1854
 
  if (! (intersect_scans= (optimizer::RorScanInfo**)param->mem_root->alloc_root(sizeof(optimizer::RorScanInfo*) * tree->n_ror_scans)))
 
1897
  ROR_SCAN_INFO **intersect_scans= NULL; /* ROR scans used in index intersection */
 
1898
  ROR_SCAN_INFO **intersect_scans_end= NULL;
 
1899
  if (! (intersect_scans= (ROR_SCAN_INFO**)param->mem_root->alloc_root(sizeof(ROR_SCAN_INFO*) * tree->n_ror_scans)))
1855
1900
    return NULL;
1856
1901
  intersect_scans_end= intersect_scans;
1857
1902
 
1858
1903
  /* Create and incrementally update ROR intersection. */
1859
 
  ROR_INTERSECT_INFO intersect(param);
1860
 
  ROR_INTERSECT_INFO intersect_best(param);
 
1904
  ROR_INTERSECT_INFO *intersect= NULL;
 
1905
  ROR_INTERSECT_INFO *intersect_best= NULL;
 
1906
  if (! (intersect= ror_intersect_init(param)) ||
 
1907
      ! (intersect_best= ror_intersect_init(param)))
 
1908
    return NULL;
1861
1909
 
1862
1910
  /* [intersect_scans,intersect_scans_best) will hold the best intersection */
1863
 
  optimizer::RorScanInfo **intersect_scans_best= NULL;
 
1911
  ROR_SCAN_INFO **intersect_scans_best= NULL;
1864
1912
  cur_ror_scan= tree->ror_scans;
1865
1913
  intersect_scans_best= intersect_scans;
1866
 
  while (cur_ror_scan != tree->ror_scans_end && ! intersect.is_covering)
 
1914
  while (cur_ror_scan != tree->ror_scans_end && !intersect->is_covering)
1867
1915
  {
1868
1916
    /* S= S + first(R);  R= R - first(R); */
1869
 
    if (! ror_intersect_add(&intersect, *cur_ror_scan, false))
 
1917
    if (!ror_intersect_add(intersect, *cur_ror_scan, false))
1870
1918
    {
1871
1919
      cur_ror_scan++;
1872
1920
      continue;
1874
1922
 
1875
1923
    *(intersect_scans_end++)= *(cur_ror_scan++);
1876
1924
 
1877
 
    if (intersect.total_cost < min_cost)
 
1925
    if (intersect->total_cost < min_cost)
1878
1926
    {
1879
1927
      /* Local minimum found, save it */
1880
 
      ror_intersect_cpy(&intersect_best, &intersect);
 
1928
      ror_intersect_cpy(intersect_best, intersect);
1881
1929
      intersect_scans_best= intersect_scans_end;
1882
 
      min_cost = intersect.total_cost;
 
1930
      min_cost = intersect->total_cost;
1883
1931
    }
1884
1932
  }
1885
1933
 
1888
1936
    return NULL;
1889
1937
  }
1890
1938
 
1891
 
  *are_all_covering= intersect.is_covering;
 
1939
  *are_all_covering= intersect->is_covering;
1892
1940
  uint32_t best_num= intersect_scans_best - intersect_scans;
1893
 
  ror_intersect_cpy(&intersect, &intersect_best);
 
1941
  ror_intersect_cpy(intersect, intersect_best);
1894
1942
 
1895
1943
  /*
1896
1944
    Ok, found the best ROR-intersection of non-CPK key scans.
1897
1945
    Check if we should add a CPK scan. If the obtained ROR-intersection is
1898
1946
    covering, it doesn't make sense to add CPK scan.
1899
1947
  */
1900
 
  if (cpk_scan && ! intersect.is_covering)
 
1948
  if (cpk_scan && !intersect->is_covering)
1901
1949
  {
1902
 
    if (ror_intersect_add(&intersect, cpk_scan, true) &&
1903
 
        (intersect.total_cost < min_cost))
 
1950
    if (ror_intersect_add(intersect, cpk_scan, true) &&
 
1951
        (intersect->total_cost < min_cost))
1904
1952
    {
1905
1953
      cpk_scan_used= true;
1906
1954
      intersect_best= intersect; //just set pointer here
1915
1963
      return trp;
1916
1964
 
1917
1965
    if (! (trp->first_scan=
1918
 
           (optimizer::RorScanInfo**)param->mem_root->alloc_root(sizeof(optimizer::RorScanInfo*)*best_num)))
 
1966
           (ROR_SCAN_INFO**)param->mem_root->alloc_root(sizeof(ROR_SCAN_INFO*)*best_num)))
1919
1967
      return NULL;
1920
 
    memcpy(trp->first_scan, intersect_scans, best_num*sizeof(optimizer::RorScanInfo*));
 
1968
    memcpy(trp->first_scan, intersect_scans, best_num*sizeof(ROR_SCAN_INFO*));
1921
1969
    trp->last_scan=  trp->first_scan + best_num;
1922
 
    trp->is_covering= intersect_best.is_covering;
1923
 
    trp->read_cost= intersect_best.total_cost;
 
1970
    trp->is_covering= intersect_best->is_covering;
 
1971
    trp->read_cost= intersect_best->total_cost;
1924
1972
    /* Prevent divisons by zero */
1925
 
    ha_rows best_rows = double2rows(intersect_best.out_rows);
 
1973
    ha_rows best_rows = double2rows(intersect_best->out_rows);
1926
1974
    if (! best_rows)
1927
1975
      best_rows= 1;
1928
1976
    set_if_smaller(param->table->quick_condition_rows, best_rows);
1929
1977
    trp->records= best_rows;
1930
 
    trp->index_scan_costs= intersect_best.index_scan_costs;
 
1978
    trp->index_scan_costs= intersect_best->index_scan_costs;
1931
1979
    trp->cpk_scan= cpk_scan_used? cpk_scan: NULL;
1932
1980
  }
1933
1981
  return trp;
3259
3307
 
3260
3308
#define CLONE_KEY1_MAYBE 1
3261
3309
#define CLONE_KEY2_MAYBE 2
 
3310
#define swap_clone_flag(A) ((A & 1) << 1) | ((A & 2) >> 1)
3262
3311
 
3263
 
static uint32_t swap_clone_flag(uint32_t a)
3264
 
{
3265
 
  return ((a & 1) << 1) | ((a & 2) >> 1);
3266
 
}
3267
3312
 
3268
3313
static optimizer::SEL_TREE *
3269
3314
tree_and(optimizer::RangeParameter *param, optimizer::SEL_TREE *tree1, optimizer::SEL_TREE *tree2)
3739
3784
  /* Ok got a tuple */
3740
3785
  RANGE_SEQ_ENTRY *cur= &seq->stack[seq->i];
3741
3786
 
3742
 
  range->ptr= (char*)(size_t)(key_tree->part);
 
3787
  range->ptr= (char*)(int)(key_tree->part);
3743
3788
  {
3744
3789
    range->range_flag= cur->min_key_flag | cur->max_key_flag;
3745
3790
 
3983
4028
                            uint32_t mrr_buf_size,
3984
4029
                            memory::Root *parent_alloc)
3985
4030
{
3986
 
  optimizer::QuickRangeSelect *quick= new optimizer::QuickRangeSelect(param->session,
3987
 
                                                                      param->table,
3988
 
                                                                      param->real_keynr[idx],
3989
 
                                                                      test(parent_alloc),
3990
 
                                                                      NULL);
 
4031
  optimizer::QuickRangeSelect *quick= NULL;
 
4032
  bool create_err= false;
 
4033
 
 
4034
  quick= new optimizer::QuickRangeSelect(param->session,
 
4035
                                         param->table,
 
4036
                                         param->real_keynr[idx],
 
4037
                                         test(parent_alloc),
 
4038
                                         NULL,
 
4039
                                         &create_err);
3991
4040
 
3992
4041
  if (quick)
3993
4042
  {
3994
 
          if (get_quick_keys(param,
 
4043
    if (create_err ||
 
4044
              get_quick_keys(param,
3995
4045
                       quick,
3996
4046
                       param->key[idx],
3997
4047
                       key_tree,
4212
4262
}
4213
4263
 
4214
4264
 
4215
 
bool optimizer::QuickSelectInterface::is_keys_used(const boost::dynamic_bitset<>& fields)
 
4265
bool optimizer::QuickSelectInterface::is_keys_used(const MyBitmap *fields)
4216
4266
{
4217
4267
  return is_key_used(head, index, fields);
4218
4268
}
4242
4292
                                                                 table_reference_st *ref,
4243
4293
                                                                 ha_rows records)
4244
4294
{
4245
 
  memory::Root *old_root= NULL;
4246
 
  memory::Root *alloc= NULL;
 
4295
  memory::Root *old_root, *alloc;
 
4296
  optimizer::QuickRangeSelect *quick= NULL;
4247
4297
  KeyInfo *key_info = &table->key_info[ref->key];
4248
4298
  KEY_PART *key_part;
4249
4299
  optimizer::QuickRange *range= NULL;
4250
4300
  uint32_t part;
 
4301
  bool create_err= false;
4251
4302
  optimizer::CostVector cost;
4252
4303
 
4253
4304
  old_root= session->mem_root;
4254
4305
  /* The following call may change session->mem_root */
4255
 
  optimizer::QuickRangeSelect *quick= new optimizer::QuickRangeSelect(session, table, ref->key, 0, 0);
 
4306
  quick= new optimizer::QuickRangeSelect(session, table, ref->key, 0, 0, &create_err);
4256
4307
  /* save mem_root set by QuickRangeSelect constructor */
4257
4308
  alloc= session->mem_root;
4258
4309
  /*
4261
4312
  */
4262
4313
  session->mem_root= old_root;
4263
4314
 
4264
 
  if (! quick)
 
4315
  if (!quick || create_err)
4265
4316
    return 0;                   /* no ranges found */
4266
4317
  if (quick->init())
4267
4318
    goto err;
4583
4634
  uint32_t key_infix_len= 0;          /* Length of key_infix. */
4584
4635
  optimizer::GroupMinMaxReadPlan *read_plan= NULL; /* The eventually constructed TRP. */
4585
4636
  uint32_t key_part_nr;
4586
 
  Order *tmp_group= NULL;
 
4637
  order_st *tmp_group= NULL;
4587
4638
  Item *item= NULL;
4588
4639
  Item_field *item_field= NULL;
4589
4640
 
5572
5623
}
5573
5624
 
5574
5625
 
5575
 
uint32_t optimizer::RorScanInfo::findFirstNotSet() const
5576
 
{
5577
 
  boost::dynamic_bitset<> map= bitsToBitset();
5578
 
  for (boost::dynamic_bitset<>::size_type i= 0; i < map.size(); i++)
5579
 
  {
5580
 
    if (! map.test(i))
5581
 
    {
5582
 
      return i;
5583
 
    }
5584
 
  }
5585
 
  return map.size();
5586
 
}
5587
 
 
5588
 
 
5589
 
size_t optimizer::RorScanInfo::getBitCount() const
5590
 
{
5591
 
  boost::dynamic_bitset<> tmp_bitset= bitsToBitset();
5592
 
  return tmp_bitset.count();
5593
 
}
5594
 
 
5595
 
 
5596
 
void optimizer::RorScanInfo::subtractBitset(const boost::dynamic_bitset<>& in_bitset)
5597
 
{
5598
 
  boost::dynamic_bitset<> tmp_bitset= bitsToBitset();
5599
 
  tmp_bitset-= in_bitset;
5600
 
  covered_fields= tmp_bitset.to_ulong();
5601
 
}
5602
 
 
5603
 
 
5604
 
boost::dynamic_bitset<> optimizer::RorScanInfo::bitsToBitset() const
5605
 
{
5606
 
  string res;
5607
 
  uint64_t conv= covered_fields;
5608
 
  while (conv)
5609
 
  {
5610
 
    res.push_back((conv & 1) + '0');
5611
 
    conv>>= 1;
5612
 
  }
5613
 
  if (! res.empty())
5614
 
  {
5615
 
    std::reverse(res.begin(), res.end());
5616
 
  }
5617
 
  string final(covered_fields_size - res.length(), '0');
5618
 
  final.append(res);
5619
 
  return (boost::dynamic_bitset<>(final));
5620
 
}
5621
 
 
5622
 
 
5623
5626
} /* namespace drizzled */