← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/optimizer/range.cc

  • Committer: Monty Taylor
  • Date: 2011-02-13 17:26:39 UTC
  • mfrom: (2157.2.2 give-in-to-pkg-config)
  • mto: This revision was merged to the branch mainline in revision 2166.
  • Revision ID: mordred@inaugust.com-20110213172639-nhy7i72sfhoq13ms
Merged in pkg-config fixes.

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