← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/optimizer/range.cc

  • Committer: Padraig O'Sullivan
  • Date: 2010-02-11 16:22:34 UTC
  • mto: (1300.3.1 query-as-string)
  • mto: This revision was merged to the branch mainline in revision 1307.
  • Revision ID: osullivan.padraig@gmail.com-20100211162234-tkk64v4vdqkb9syv
Removed the found_semicolon member from the parsing stage

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/optimizer/range.cc
37
37
    The entry point for the range analysis module is get_mm_tree() function.
38
38
 
39
39
    The lists are returned in form of complicated structure of interlinked
40
 
    optimizer::SEL_TREE/optimizer::SEL_IMERGE/SEL_ARG objects.
 
40
    SEL_TREE/SEL_IMERGE/SEL_ARG objects.
41
41
    See quick_range_seq_next, find_used_partitions for examples of how to walk
42
42
    this structure.
43
43
    All direct "users" of this module are located within this cursor, too.
44
44
 
45
45
 
 
46
  PartitionPruningModule
 
47
    A module that accepts a partitioned table, condition, and finds which
 
48
    partitions we will need to use in query execution. Search down for
 
49
    "PartitionPruningModule" for description.
 
50
    The module has single entry point - prune_partitions() function.
 
51
 
 
52
 
46
53
  Range/index_merge/groupby-minmax optimizer module
47
54
    A module that accepts a table, condition, and returns
48
55
     - a QUICK_*_SELECT object that can be used to retrieve rows that match
84
91
  keypart-value-bytes holds the value. Its format depends on the field type.
85
92
  The length of keypart-value-bytes may or may not depend on the value being
86
93
  stored. The default is that length is static and equal to
87
 
  KeyPartInfo::length.
 
94
  KEY_PART_INFO::length.
88
95
 
89
96
  Key parts with (key_part_flag & HA_BLOB_PART) have length depending of the
90
97
  value:
109
116
#include <vector>
110
117
#include <algorithm>
111
118
 
112
 
#include <boost/dynamic_bitset.hpp>
113
 
 
114
119
#include "drizzled/sql_base.h"
115
120
#include "drizzled/sql_select.h"
116
121
#include "drizzled/error.h"
117
 
#include "drizzled/optimizer/cost_vector.h"
 
122
#include "drizzled/cost_vect.h"
118
123
#include "drizzled/item/cmpfunc.h"
119
124
#include "drizzled/field/num.h"
120
125
#include "drizzled/check_stack_overrun.h"
128
133
#include "drizzled/optimizer/quick_ror_union_select.h"
129
134
#include "drizzled/optimizer/table_read_plan.h"
130
135
#include "drizzled/optimizer/sel_arg.h"
131
 
#include "drizzled/optimizer/sel_imerge.h"
132
 
#include "drizzled/optimizer/sel_tree.h"
133
136
#include "drizzled/optimizer/range_param.h"
134
137
#include "drizzled/records.h"
135
138
#include "drizzled/internal/my_sys.h"
137
140
 
138
141
#include "drizzled/temporal.h" /* Needed in get_mm_leaf() for timestamp -> datetime comparisons */
139
142
 
 
143
#include "drizzled/memory/multi_malloc.h"
 
144
 
140
145
using namespace std;
141
146
namespace drizzled
142
147
{
201
206
static void get_sweep_read_cost(Table *table,
202
207
                                ha_rows nrows,
203
208
                                bool interrupted,
204
 
                                optimizer::CostVector *cost)
 
209
                                COST_VECT *cost)
205
210
{
206
211
  cost->zero();
207
212
  if (table->cursor->primary_key_is_clustered())
208
213
  {
209
 
    cost->setIOCount(table->cursor->read_time(table->getShare()->getPrimaryKey(),
 
214
    cost->io_count= table->cursor->read_time(table->s->primary_key,
210
215
                                             static_cast<uint32_t>(nrows),
211
 
                                             nrows));
 
216
                                             nrows);
212
217
  }
213
218
  else
214
219
  {
219
224
    if (busy_blocks < 1.0)
220
225
      busy_blocks= 1.0;
221
226
 
222
 
    cost->setIOCount(busy_blocks);
 
227
    cost->io_count= busy_blocks;
223
228
 
224
229
    if (! interrupted)
225
230
    {
226
231
      /* Assume reading is done in one 'sweep' */
227
 
      cost->setAvgIOCost((DISK_SEEK_BASE_COST +
228
 
                          DISK_SEEK_PROP_COST*n_blocks/busy_blocks));
 
232
      cost->avg_io_cost= (DISK_SEEK_BASE_COST +
 
233
                          DISK_SEEK_PROP_COST*n_blocks/busy_blocks);
229
234
    }
230
235
  }
231
236
}
232
237
 
233
 
static optimizer::SEL_TREE * get_mm_parts(optimizer::RangeParameter *param,
 
238
class SEL_IMERGE;
 
239
 
 
240
 
 
241
class SEL_TREE :public memory::SqlAlloc
 
242
{
 
243
public:
 
244
  /*
 
245
    Starting an effort to document this field:
 
246
    (for some i, keys[i]->type == optimizer::SEL_ARG::IMPOSSIBLE) =>
 
247
       (type == SEL_TREE::IMPOSSIBLE)
 
248
  */
 
249
  enum Type
 
250
  {
 
251
    IMPOSSIBLE,
 
252
    ALWAYS,
 
253
    MAYBE,
 
254
    KEY,
 
255
    KEY_SMALLER
 
256
  } type;
 
257
 
 
258
  SEL_TREE(enum Type type_arg) :type(type_arg) {}
 
259
  SEL_TREE() :type(KEY)
 
260
  {
 
261
    keys_map.reset();
 
262
    memset(keys, 0, sizeof(keys));
 
263
  }
 
264
  /*
 
265
    Note: there may exist SEL_TREE objects with sel_tree->type=KEY and
 
266
    keys[i]=0 for all i. (SergeyP: it is not clear whether there is any
 
267
    merit in range analyzer functions (e.g. get_mm_parts) returning a
 
268
    pointer to such SEL_TREE instead of NULL)
 
269
  */
 
270
  optimizer::SEL_ARG *keys[MAX_KEY];
 
271
  key_map keys_map;        /* bitmask of non-NULL elements in keys */
 
272
 
 
273
  /*
 
274
    Possible ways to read rows using index_merge. The list is non-empty only
 
275
    if type==KEY. Currently can be non empty only if keys_map.none().
 
276
  */
 
277
  List<SEL_IMERGE> merges;
 
278
 
 
279
  /* The members below are filled/used only after get_mm_tree is done */
 
280
  key_map ror_scans_map;   /* bitmask of ROR scan-able elements in keys */
 
281
  uint32_t n_ror_scans;     /* number of set bits in ror_scans_map */
 
282
 
 
283
  struct st_ror_scan_info **ror_scans;     /* list of ROR key scans */
 
284
  struct st_ror_scan_info **ror_scans_end; /* last ROR scan */
 
285
  /* Note that #records for each key scan is stored in table->quick_rows */
 
286
};
 
287
 
 
288
struct st_ror_scan_info;
 
289
 
 
290
static SEL_TREE * get_mm_parts(optimizer::RangeParameter *param,
234
291
                               COND *cond_func,
235
292
                               Field *field,
236
293
                                                 Item_func::Functype type,
244
301
                                                         Item_func::Functype type,
245
302
                                       Item *value);
246
303
 
247
 
static optimizer::SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond);
 
304
static SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond);
248
305
 
249
306
static bool is_key_scan_ror(optimizer::Parameter *param, uint32_t keynr, uint8_t nparts);
250
307
 
251
 
static ha_rows check_quick_select(Session *session,
252
 
                                  optimizer::Parameter *param,
 
308
static ha_rows check_quick_select(optimizer::Parameter *param,
253
309
                                  uint32_t idx,
254
310
                                  bool index_only,
255
311
                                  optimizer::SEL_ARG *tree,
256
312
                                  bool update_tbl_stats,
257
313
                                  uint32_t *mrr_flags,
258
314
                                  uint32_t *bufsize,
259
 
                                  optimizer::CostVector *cost);
 
315
                                  COST_VECT *cost);
260
316
 
261
 
static optimizer::RangeReadPlan *get_key_scans_params(Session *session,
262
 
                                                      optimizer::Parameter *param,
263
 
                                                      optimizer::SEL_TREE *tree,
 
317
static optimizer::RangeReadPlan *get_key_scans_params(optimizer::Parameter *param,
 
318
                                                      SEL_TREE *tree,
264
319
                                                      bool index_read_must_be_used,
265
320
                                                      bool update_tbl_stats,
266
321
                                                      double read_time);
267
322
 
268
323
static
269
324
optimizer::RorIntersectReadPlan *get_best_ror_intersect(const optimizer::Parameter *param,
270
 
                                                        optimizer::SEL_TREE *tree,
 
325
                                                        SEL_TREE *tree,
271
326
                                                        double read_time,
272
327
                                                        bool *are_all_covering);
273
328
 
274
329
static
275
330
optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
276
 
                                                                 optimizer::SEL_TREE *tree,
 
331
                                                                 SEL_TREE *tree,
277
332
                                                                 double read_time);
278
333
 
279
334
static
280
 
optimizer::TableReadPlan *get_best_disjunct_quick(Session *session,
281
 
                                                  optimizer::Parameter *param,
282
 
                                                  optimizer::SEL_IMERGE *imerge,
 
335
optimizer::TableReadPlan *get_best_disjunct_quick(optimizer::Parameter *param,
 
336
                                                  SEL_IMERGE *imerge,
283
337
                                                  double read_time);
284
338
 
285
339
static
286
 
optimizer::GroupMinMaxReadPlan *get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree);
287
 
 
288
 
static optimizer::SEL_TREE *tree_and(optimizer::RangeParameter *param, 
289
 
                                     optimizer::SEL_TREE *tree1, 
290
 
                                     optimizer::SEL_TREE *tree2);
 
340
optimizer::GroupMinMaxReadPlan *get_best_group_min_max(optimizer::Parameter *param, SEL_TREE *tree);
 
341
 
 
342
static void print_sel_tree(optimizer::Parameter *param,
 
343
                           SEL_TREE *tree,
 
344
                           key_map *tree_map,
 
345
                           const char *msg);
 
346
 
 
347
static void print_ror_scans_arr(Table *table,
 
348
                                const char *msg,
 
349
                                struct st_ror_scan_info **start,
 
350
                                struct st_ror_scan_info **end);
 
351
 
 
352
static SEL_TREE *tree_and(optimizer::RangeParameter *param, SEL_TREE *tree1, SEL_TREE *tree2);
 
353
 
 
354
static SEL_TREE *tree_or(optimizer::RangeParameter *param, SEL_TREE *tree1, SEL_TREE *tree2);
291
355
 
292
356
static optimizer::SEL_ARG *sel_add(optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);
293
357
 
 
358
static optimizer::SEL_ARG *key_or(optimizer::RangeParameter *param, optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);
 
359
 
294
360
static optimizer::SEL_ARG *key_and(optimizer::RangeParameter *param,
295
361
                                   optimizer::SEL_ARG *key1,
296
362
                                   optimizer::SEL_ARG *key2,
298
364
 
299
365
static bool get_range(optimizer::SEL_ARG **e1, optimizer::SEL_ARG **e2, optimizer::SEL_ARG *root1);
300
366
 
 
367
static bool eq_tree(optimizer::SEL_ARG* a, optimizer::SEL_ARG *b);
 
368
 
301
369
optimizer::SEL_ARG optimizer::null_element(optimizer::SEL_ARG::IMPOSSIBLE);
302
370
 
303
371
static bool null_part_in_key(KEY_PART *key_part,
304
372
                             const unsigned char *key,
305
373
                             uint32_t length);
306
374
 
307
 
bool sel_trees_can_be_ored(optimizer::SEL_TREE *tree1, 
308
 
                           optimizer::SEL_TREE *tree2, 
309
 
                           optimizer::RangeParameter *param);
310
 
 
311
 
 
312
 
 
313
 
 
 
375
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, optimizer::RangeParameter *param);
 
376
 
 
377
 
 
378
/*
 
379
  SEL_IMERGE is a list of possible ways to do index merge, i.e. it is
 
380
  a condition in the following form:
 
381
   (t_1||t_2||...||t_N) && (next)
 
382
 
 
383
  where all t_i are SEL_TREEs, next is another SEL_IMERGE and no pair
 
384
  (t_i,t_j) contains SEL_ARGS for the same index.
 
385
 
 
386
  SEL_TREE contained in SEL_IMERGE always has merges=NULL.
 
387
 
 
388
  This class relies on memory manager to do the cleanup.
 
389
*/
 
390
 
 
391
class SEL_IMERGE : public memory::SqlAlloc
 
392
{
 
393
  enum { PREALLOCED_TREES= 10};
 
394
public:
 
395
  SEL_TREE *trees_prealloced[PREALLOCED_TREES];
 
396
  SEL_TREE **trees;             /* trees used to do index_merge   */
 
397
  SEL_TREE **trees_next;        /* last of these trees            */
 
398
  SEL_TREE **trees_end;         /* end of allocated space         */
 
399
 
 
400
  optimizer::SEL_ARG  ***best_keys;        /* best keys to read in SEL_TREEs */
 
401
 
 
402
  SEL_IMERGE() :
 
403
    trees(&trees_prealloced[0]),
 
404
    trees_next(trees),
 
405
    trees_end(trees + PREALLOCED_TREES)
 
406
  {}
 
407
  int or_sel_tree(optimizer::RangeParameter *param, SEL_TREE *tree);
 
408
  int or_sel_tree_with_checks(optimizer::RangeParameter *param, SEL_TREE *new_tree);
 
409
  int or_sel_imerge_with_checks(optimizer::RangeParameter *param, SEL_IMERGE* imerge);
 
410
};
 
411
 
 
412
 
 
413
/*
 
414
  Add SEL_TREE to this index_merge without any checks,
 
415
 
 
416
  NOTES
 
417
    This function implements the following:
 
418
      (x_1||...||x_N) || t = (x_1||...||x_N||t), where x_i, t are SEL_TREEs
 
419
 
 
420
  RETURN
 
421
     0 - OK
 
422
    -1 - Out of memory.
 
423
*/
 
424
int SEL_IMERGE::or_sel_tree(optimizer::RangeParameter *param, SEL_TREE *tree)
 
425
{
 
426
  if (trees_next == trees_end)
 
427
  {
 
428
    const int realloc_ratio= 2;         /* Double size for next round */
 
429
    uint32_t old_elements= (trees_end - trees);
 
430
    uint32_t old_size= sizeof(SEL_TREE**) * old_elements;
 
431
    uint32_t new_size= old_size * realloc_ratio;
 
432
    SEL_TREE **new_trees;
 
433
    if (!(new_trees= (SEL_TREE**)alloc_root(param->mem_root, new_size)))
 
434
      return -1;
 
435
    memcpy(new_trees, trees, old_size);
 
436
    trees= new_trees;
 
437
    trees_next= trees + old_elements;
 
438
    trees_end= trees + old_elements * realloc_ratio;
 
439
  }
 
440
  *(trees_next++)= tree;
 
441
  return 0;
 
442
}
 
443
 
 
444
 
 
445
/*
 
446
  Perform OR operation on this SEL_IMERGE and supplied SEL_TREE new_tree,
 
447
  combining new_tree with one of the trees in this SEL_IMERGE if they both
 
448
  have SEL_ARGs for the same key.
 
449
 
 
450
  SYNOPSIS
 
451
    or_sel_tree_with_checks()
 
452
      param    Parameter from SqlSelect::test_quick_select
 
453
      new_tree SEL_TREE with type KEY or KEY_SMALLER.
 
454
 
 
455
  NOTES
 
456
    This does the following:
 
457
    (t_1||...||t_k)||new_tree =
 
458
     either
 
459
       = (t_1||...||t_k||new_tree)
 
460
     or
 
461
       = (t_1||....||(t_j|| new_tree)||...||t_k),
 
462
 
 
463
     where t_i, y are SEL_TREEs.
 
464
    new_tree is combined with the first t_j it has a SEL_ARG on common
 
465
    key with. As a consequence of this, choice of keys to do index_merge
 
466
    read may depend on the order of conditions in WHERE part of the query.
 
467
 
 
468
  RETURN
 
469
    0  OK
 
470
    1  One of the trees was combined with new_tree to SEL_TREE::ALWAYS,
 
471
       and (*this) should be discarded.
 
472
   -1  An error occurred.
 
473
*/
 
474
int SEL_IMERGE::or_sel_tree_with_checks(optimizer::RangeParameter *param, SEL_TREE *new_tree)
 
475
{
 
476
  for (SEL_TREE** tree = trees;
 
477
       tree != trees_next;
 
478
       tree++)
 
479
  {
 
480
    if (sel_trees_can_be_ored(*tree, new_tree, param))
 
481
    {
 
482
      *tree = tree_or(param, *tree, new_tree);
 
483
      if (!*tree)
 
484
        return 1;
 
485
      if (((*tree)->type == SEL_TREE::MAYBE) ||
 
486
          ((*tree)->type == SEL_TREE::ALWAYS))
 
487
        return 1;
 
488
      /* SEL_TREE::IMPOSSIBLE is impossible here */
 
489
      return 0;
 
490
    }
 
491
  }
 
492
 
 
493
  /* New tree cannot be combined with any of existing trees. */
 
494
  return or_sel_tree(param, new_tree);
 
495
}
 
496
 
 
497
 
 
498
/*
 
499
  Perform OR operation on this index_merge and supplied index_merge list.
 
500
 
 
501
  RETURN
 
502
    0 - OK
 
503
    1 - One of conditions in result is always true and this SEL_IMERGE
 
504
        should be discarded.
 
505
   -1 - An error occurred
 
506
*/
 
507
 
 
508
int SEL_IMERGE::or_sel_imerge_with_checks(optimizer::RangeParameter *param, SEL_IMERGE* imerge)
 
509
{
 
510
  for (SEL_TREE** tree= imerge->trees;
 
511
       tree != imerge->trees_next;
 
512
       tree++)
 
513
  {
 
514
    if (or_sel_tree_with_checks(param, *tree))
 
515
      return 1;
 
516
  }
 
517
  return 0;
 
518
}
314
519
 
315
520
 
316
521
/*
317
522
  Perform AND operation on two index_merge lists and store result in *im1.
318
523
*/
319
524
 
320
 
inline void imerge_list_and_list(List<optimizer::SEL_IMERGE> *im1, List<optimizer::SEL_IMERGE> *im2)
 
525
inline void imerge_list_and_list(List<SEL_IMERGE> *im1, List<SEL_IMERGE> *im2)
321
526
{
322
527
  im1->concat(im2);
323
528
}
324
529
 
325
530
 
 
531
/*
 
532
  Perform OR operation on 2 index_merge lists, storing result in first list.
 
533
 
 
534
  NOTES
 
535
    The following conversion is implemented:
 
536
     (a_1 &&...&& a_N)||(b_1 &&...&& b_K) = AND_i,j(a_i || b_j) =>
 
537
      => (a_1||b_1).
 
538
 
 
539
    i.e. all conjuncts except the first one are currently dropped.
 
540
    This is done to avoid producing N*K ways to do index_merge.
 
541
 
 
542
    If (a_1||b_1) produce a condition that is always true, NULL is returned
 
543
    and index_merge is discarded (while it is actually possible to try
 
544
    harder).
 
545
 
 
546
    As a consequence of this, choice of keys to do index_merge read may depend
 
547
    on the order of conditions in WHERE part of the query.
 
548
 
 
549
  RETURN
 
550
    0     OK, result is stored in *im1
 
551
    other Error, both passed lists are unusable
 
552
*/
 
553
 
 
554
static int imerge_list_or_list(optimizer::RangeParameter *param,
 
555
                               List<SEL_IMERGE> *im1,
 
556
                               List<SEL_IMERGE> *im2)
 
557
{
 
558
  SEL_IMERGE *imerge= im1->head();
 
559
  im1->empty();
 
560
  im1->push_back(imerge);
 
561
 
 
562
  return imerge->or_sel_imerge_with_checks(param, im2->head());
 
563
}
 
564
 
 
565
 
 
566
/*
 
567
  Perform OR operation on index_merge list and key tree.
 
568
 
 
569
  RETURN
 
570
     0     OK, result is stored in *im1.
 
571
     other Error
 
572
 */
 
573
 
 
574
static int imerge_list_or_tree(optimizer::RangeParameter *param,
 
575
                               List<SEL_IMERGE> *im1,
 
576
                               SEL_TREE *tree)
 
577
{
 
578
  SEL_IMERGE *imerge;
 
579
  List_iterator<SEL_IMERGE> it(*im1);
 
580
  while ((imerge= it++))
 
581
  {
 
582
    if (imerge->or_sel_tree_with_checks(param, tree))
 
583
      it.remove();
 
584
  }
 
585
  return im1->is_empty();
 
586
}
 
587
 
 
588
 
326
589
/***************************************************************************
327
590
** Basic functions for SqlSelect and QuickRangeSelect
328
591
***************************************************************************/
385
648
 
386
649
void optimizer::SqlSelect::cleanup()
387
650
{
388
 
  if (quick)
389
 
  {
390
 
    delete quick;
391
 
    quick= NULL;
392
 
  }
393
 
 
 
651
  delete quick;
 
652
  quick= 0;
394
653
  if (free_cond)
395
654
  {
396
655
    free_cond= 0;
397
656
    delete cond;
398
657
    cond= 0;
399
658
  }
400
 
  file->close_cached_file();
 
659
  close_cached_file(file);
401
660
}
402
661
 
403
662
 
464
723
    MAX_KEY if no such index was found.
465
724
*/
466
725
 
467
 
uint32_t optimizer::get_index_for_order(Table *table, Order *order, ha_rows limit)
 
726
uint32_t optimizer::get_index_for_order(Table *table, order_st *order, ha_rows limit)
468
727
{
469
728
  uint32_t idx;
470
729
  uint32_t match_key= MAX_KEY, match_key_len= MAX_KEY_LENGTH + 1;
471
 
  Order *ord;
 
730
  order_st *ord;
472
731
 
473
732
  for (ord= order; ord; ord= ord->next)
474
733
    if (!ord->asc)
475
734
      return MAX_KEY;
476
735
 
477
 
  for (idx= 0; idx < table->getShare()->sizeKeys(); idx++)
 
736
  for (idx= 0; idx < table->s->keys; idx++)
478
737
  {
479
738
    if (!(table->keys_in_use_for_query.test(idx)))
480
739
      continue;
481
 
    KeyPartInfo *keyinfo= table->key_info[idx].key_part;
 
740
    KEY_PART_INFO *keyinfo= table->key_info[idx].key_part;
482
741
    uint32_t n_parts=  table->key_info[idx].key_parts;
483
742
    uint32_t partno= 0;
484
743
 
543
802
static int fill_used_fields_bitmap(optimizer::Parameter *param)
544
803
{
545
804
  Table *table= param->table;
 
805
  my_bitmap_map *tmp;
546
806
  uint32_t pk;
547
 
  param->tmp_covered_fields.clear();
548
 
  param->needed_fields.resize(table->getShare()->sizeFields());
549
 
  param->needed_fields.reset();
550
 
 
551
 
  param->needed_fields|= *table->read_set;
552
 
  param->needed_fields|= *table->write_set;
553
 
 
554
 
  pk= param->table->getShare()->getPrimaryKey();
 
807
  param->tmp_covered_fields.setBitmap(0);
 
808
  param->fields_bitmap_size= table->s->column_bitmap_size;
 
809
  if (!(tmp= (my_bitmap_map*) alloc_root(param->mem_root,
 
810
                                  param->fields_bitmap_size)) ||
 
811
      param->needed_fields.init(tmp, table->s->fields))
 
812
    return 1;
 
813
 
 
814
  param->needed_fields= *table->read_set;
 
815
  bitmap_union(&param->needed_fields, table->write_set);
 
816
 
 
817
  pk= param->table->s->primary_key;
555
818
  if (pk != MAX_KEY && param->table->cursor->primary_key_is_clustered())
556
819
  {
557
820
    /* The table uses clustered PK and it is not internally generated */
558
 
    KeyPartInfo *key_part= param->table->key_info[pk].key_part;
559
 
    KeyPartInfo *key_part_end= key_part +
 
821
    KEY_PART_INFO *key_part= param->table->key_info[pk].key_part;
 
822
    KEY_PART_INFO *key_part_end= key_part +
560
823
                                 param->table->key_info[pk].key_parts;
561
824
    for (;key_part != key_part_end; ++key_part)
562
 
      param->needed_fields.reset(key_part->fieldnr-1);
 
825
      param->needed_fields.clearBit(key_part->fieldnr-1);
563
826
  }
564
827
  return 0;
565
828
}
640
903
{
641
904
  uint32_t idx;
642
905
  double scan_time;
643
 
  if (quick)
644
 
  {
645
 
    delete quick;
646
 
    quick= NULL;
647
 
  }
 
906
  delete quick;
 
907
  quick=0;
648
908
  needed_reg.reset();
649
909
  quick_keys.reset();
650
910
  if (keys_to_use.none())
665
925
  if (keys_to_use.any())
666
926
  {
667
927
    memory::Root alloc;
668
 
    optimizer::SEL_TREE *tree= NULL;
 
928
    SEL_TREE *tree= NULL;
669
929
    KEY_PART *key_parts;
670
 
    KeyInfo *key_info;
 
930
    KEY *key_info;
671
931
    optimizer::Parameter param;
672
932
 
673
933
    if (check_stack_overrun(session, 2*STACK_MIN_SIZE, NULL))
690
950
 
691
951
    session->no_errors=1;                               // Don't warn about NULL
692
952
    memory::init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
693
 
    if (!(param.key_parts= (KEY_PART*) alloc.alloc_root( sizeof(KEY_PART) * head->getShare()->key_parts)) ||
 
953
    if (!(param.key_parts= (KEY_PART*) alloc_root(&alloc,
 
954
                                                  sizeof(KEY_PART)*
 
955
                                                  head->s->key_parts)) ||
694
956
        fill_used_fields_bitmap(&param))
695
957
    {
696
958
      session->no_errors=0;
697
 
      alloc.free_root(MYF(0));                  // Return memory & allocator
698
 
 
 
959
      free_root(&alloc,MYF(0));                 // Return memory & allocator
699
960
      return 0;                         // Can't use range
700
961
    }
701
962
    key_parts= param.key_parts;
706
967
      This is used in get_mm_parts function.
707
968
    */
708
969
    key_info= head->key_info;
709
 
    for (idx=0 ; idx < head->getShare()->sizeKeys() ; idx++, key_info++)
 
970
    for (idx=0 ; idx < head->s->keys ; idx++, key_info++)
710
971
    {
711
 
      KeyPartInfo *key_part_info;
 
972
      KEY_PART_INFO *key_part_info;
712
973
      if (! keys_to_use.test(idx))
713
974
        continue;
714
975
 
752
1013
    {
753
1014
      if ((tree= get_mm_tree(&param,cond)))
754
1015
      {
755
 
        if (tree->type == optimizer::SEL_TREE::IMPOSSIBLE)
 
1016
        if (tree->type == SEL_TREE::IMPOSSIBLE)
756
1017
        {
757
1018
          records=0L;                      /* Return -1 from this function. */
758
1019
          read_time= (double) HA_POS_ERROR;
762
1023
          If the tree can't be used for range scans, proceed anyway, as we
763
1024
          can construct a group-min-max quick select
764
1025
        */
765
 
        if (tree->type != optimizer::SEL_TREE::KEY && tree->type != optimizer::SEL_TREE::KEY_SMALLER)
 
1026
        if (tree->type != SEL_TREE::KEY && tree->type != SEL_TREE::KEY_SMALLER)
766
1027
          tree= NULL;
767
1028
      }
768
1029
    }
796
1057
        bool can_build_covering= false;
797
1058
 
798
1059
        /* Get best 'range' plan and prepare data for making other plans */
799
 
        if ((range_trp= get_key_scans_params(session, &param, tree, false, true,
 
1060
        if ((range_trp= get_key_scans_params(&param, tree, false, true,
800
1061
                                             best_read_time)))
801
1062
        {
802
1063
          best_trp= range_trp;
833
1094
      else
834
1095
      {
835
1096
        /* Try creating index_merge/ROR-union scan. */
836
 
        optimizer::SEL_IMERGE *imerge= NULL;
 
1097
        SEL_IMERGE *imerge= NULL;
837
1098
        optimizer::TableReadPlan *best_conj_trp= NULL;
838
1099
        optimizer::TableReadPlan *new_conj_trp= NULL;
839
 
        List_iterator_fast<optimizer::SEL_IMERGE> it(tree->merges);
 
1100
        List_iterator_fast<SEL_IMERGE> it(tree->merges);
840
1101
        while ((imerge= it++))
841
1102
        {
842
 
          new_conj_trp= get_best_disjunct_quick(session, &param, imerge, best_read_time);
 
1103
          new_conj_trp= get_best_disjunct_quick(&param, imerge, best_read_time);
843
1104
          if (new_conj_trp)
844
1105
            set_if_smaller(param.table->quick_condition_rows,
845
1106
                           new_conj_trp->records);
860
1121
      records= best_trp->records;
861
1122
      if (! (quick= best_trp->make_quick(&param, true)) || quick->init())
862
1123
      {
863
 
        /* quick can already be free here */
864
 
        if (quick)
865
 
        {
866
 
          delete quick;
867
 
          quick= NULL;
868
 
        }
 
1124
        delete quick;
 
1125
        quick= NULL;
869
1126
      }
870
1127
    }
871
1128
 
872
1129
  free_mem:
873
 
    alloc.free_root(MYF(0));                    // Return memory & allocator
 
1130
    free_root(&alloc,MYF(0));                   // Return memory & allocator
874
1131
    session->mem_root= param.old_root;
875
1132
    session->no_errors=0;
876
1133
  }
883
1140
}
884
1141
 
885
1142
/*
886
 
  Get best plan for a optimizer::SEL_IMERGE disjunctive expression.
 
1143
  Get best plan for a SEL_IMERGE disjunctive expression.
887
1144
  SYNOPSIS
888
1145
    get_best_disjunct_quick()
889
 
      session
890
1146
      param     Parameter from check_quick_select function
891
1147
      imerge    Expression to use
892
1148
      read_time Don't create scans with cost > read_time
949
1205
*/
950
1206
 
951
1207
static
952
 
optimizer::TableReadPlan *get_best_disjunct_quick(Session *session,
953
 
                                                  optimizer::Parameter *param,
954
 
                                                  optimizer::SEL_IMERGE *imerge,
 
1208
optimizer::TableReadPlan *get_best_disjunct_quick(optimizer::Parameter *param,
 
1209
                                                  SEL_IMERGE *imerge,
955
1210
                                                  double read_time)
956
1211
{
957
 
  optimizer::SEL_TREE **ptree= NULL;
 
1212
  SEL_TREE **ptree;
958
1213
  optimizer::IndexMergeReadPlan *imerge_trp= NULL;
959
1214
  uint32_t n_child_scans= imerge->trees_next - imerge->trees;
960
1215
  optimizer::RangeReadPlan **range_scans= NULL;
974
1229
  ha_rows roru_total_records;
975
1230
  double roru_intersect_part= 1.0;
976
1231
 
977
 
  if (! (range_scans= (optimizer::RangeReadPlan**)param->mem_root->alloc_root(sizeof(optimizer::RangeReadPlan*)* n_child_scans)))
978
 
  {
 
1232
  if (! (range_scans= (optimizer::RangeReadPlan**)alloc_root(param->mem_root,
 
1233
                                                             sizeof(optimizer::RangeReadPlan*)*
 
1234
                                                             n_child_scans)))
979
1235
    return NULL;
980
 
  }
981
 
 
982
1236
  /*
983
1237
    Collect best 'range' scan for each of disjuncts, and, while doing so,
984
1238
    analyze possibility of ROR scans. Also calculate some values needed by
988
1242
       ptree != imerge->trees_next;
989
1243
       ptree++, cur_child++)
990
1244
  {
991
 
    if (!(*cur_child= get_key_scans_params(session, param, *ptree, true, false, read_time)))
 
1245
    print_sel_tree(param, *ptree, &(*ptree)->keys_map, "tree in SEL_IMERGE");
 
1246
    if (!(*cur_child= get_key_scans_params(param, *ptree, true, false, read_time)))
992
1247
    {
993
1248
      /*
994
1249
        One of index scans in this index_merge is more expensive than entire
1006
1261
    all_scans_rors &= (*cur_child)->is_ror;
1007
1262
    if (pk_is_clustered &&
1008
1263
        param->real_keynr[(*cur_child)->key_idx] ==
1009
 
        param->table->getShare()->getPrimaryKey())
 
1264
        param->table->s->primary_key)
1010
1265
    {
1011
1266
      cpk_scan= cur_child;
1012
1267
      cpk_scan_records= (*cur_child)->records;
1040
1295
 
1041
1296
  /* Calculate cost(rowid_to_row_scan) */
1042
1297
  {
1043
 
    optimizer::CostVector sweep_cost;
1044
 
    Join *join= param->session->lex->select_lex.join;
 
1298
    COST_VECT sweep_cost;
 
1299
    JOIN *join= param->session->lex->select_lex.join;
1045
1300
    bool is_interrupted= test(join && join->tables == 1);
1046
1301
    get_sweep_read_cost(param->table, non_cpk_scan_records, is_interrupted,
1047
1302
                        &sweep_cost);
1057
1312
                                    param->session->variables.sortbuff_size);
1058
1313
  if (param->imerge_cost_buff_size < unique_calc_buff_size)
1059
1314
  {
1060
 
    if (!(param->imerge_cost_buff= (uint*)param->mem_root->alloc_root(unique_calc_buff_size)))
1061
 
    {
 
1315
    if (!(param->imerge_cost_buff= (uint*)alloc_root(param->mem_root,
 
1316
                                                     unique_calc_buff_size)))
1062
1317
      return NULL;
1063
 
    }
1064
 
 
1065
1318
    param->imerge_cost_buff_size= unique_calc_buff_size;
1066
1319
  }
1067
1320
 
1090
1343
  /* Ok, it is possible to build a ROR-union, try it. */
1091
1344
  bool dummy;
1092
1345
  if (! (roru_read_plans=
1093
 
          (optimizer::TableReadPlan **) param->mem_root->alloc_root(sizeof(optimizer::TableReadPlan*) * n_child_scans)))
1094
 
  {
 
1346
          (optimizer::TableReadPlan **) alloc_root(param->mem_root,
 
1347
                                                   sizeof(optimizer::TableReadPlan*)*
 
1348
                                                   n_child_scans)))
1095
1349
    return imerge_trp;
1096
 
  }
1097
1350
skip_to_ror_scan:
1098
1351
  roru_index_costs= 0.0;
1099
1352
  roru_total_records= 0;
1158
1411
  */
1159
1412
  double roru_total_cost;
1160
1413
  {
1161
 
    optimizer::CostVector sweep_cost;
1162
 
    Join *join= param->session->lex->select_lex.join;
 
1414
    COST_VECT sweep_cost;
 
1415
    JOIN *join= param->session->lex->select_lex.join;
1163
1416
    bool is_interrupted= test(join && join->tables == 1);
1164
1417
    get_sweep_read_cost(param->table, roru_total_records, is_interrupted,
1165
1418
                        &sweep_cost);
1185
1438
}
1186
1439
 
1187
1440
 
 
1441
typedef struct st_ror_scan_info
 
1442
{
 
1443
  uint32_t      idx;      /* # of used key in param->keys */
 
1444
  uint32_t      keynr;    /* # of used key in table */
 
1445
  ha_rows   records;  /* estimate of # records this scan will return */
 
1446
 
 
1447
  /* Set of intervals over key fields that will be used for row retrieval. */
 
1448
  optimizer::SEL_ARG   *sel_arg;
 
1449
 
 
1450
  /* Fields used in the query and covered by this ROR scan. */
 
1451
  MyBitmap covered_fields;
 
1452
  uint32_t      used_fields_covered; /* # of set bits in covered_fields */
 
1453
  int       key_rec_length; /* length of key record (including rowid) */
 
1454
 
 
1455
  /*
 
1456
    Cost of reading all index records with values in sel_arg intervals set
 
1457
    (assuming there is no need to access full table records)
 
1458
  */
 
1459
  double    index_read_cost;
 
1460
  uint32_t      first_uncovered_field; /* first unused bit in covered_fields */
 
1461
  uint32_t      key_components; /* # of parts in the key */
 
1462
} ROR_SCAN_INFO;
 
1463
 
1188
1464
 
1189
1465
/*
1190
 
  Create optimizer::RorScanInfo* structure with a single ROR scan on index idx using
 
1466
  Create ROR_SCAN_INFO* structure with a single ROR scan on index idx using
1191
1467
  sel_arg set of intervals.
1192
1468
 
1193
1469
  SYNOPSIS
1202
1478
*/
1203
1479
 
1204
1480
static
1205
 
optimizer::RorScanInfo *make_ror_scan(const optimizer::Parameter *param, int idx, optimizer::SEL_ARG *sel_arg)
 
1481
ROR_SCAN_INFO *make_ror_scan(const optimizer::Parameter *param, int idx, optimizer::SEL_ARG *sel_arg)
1206
1482
{
1207
 
  optimizer::RorScanInfo *ror_scan= NULL;
 
1483
  ROR_SCAN_INFO *ror_scan;
 
1484
  my_bitmap_map *bitmap_buf;
1208
1485
 
1209
1486
  uint32_t keynr;
1210
1487
 
1211
 
  if (!(ror_scan= (optimizer::RorScanInfo*)param->mem_root->alloc_root(sizeof(optimizer::RorScanInfo))))
 
1488
  if (!(ror_scan= (ROR_SCAN_INFO*)alloc_root(param->mem_root,
 
1489
                                             sizeof(ROR_SCAN_INFO))))
1212
1490
    return NULL;
1213
1491
 
1214
1492
  ror_scan->idx= idx;
1218
1496
  ror_scan->sel_arg= sel_arg;
1219
1497
  ror_scan->records= param->table->quick_rows[keynr];
1220
1498
 
1221
 
  ror_scan->covered_fields_size= param->table->getShare()->sizeFields();
1222
 
  boost::dynamic_bitset<> tmp_bitset(param->table->getShare()->sizeFields());
1223
 
  tmp_bitset.reset();
1224
 
 
1225
 
  KeyPartInfo *key_part= param->table->key_info[keynr].key_part;
1226
 
  KeyPartInfo *key_part_end= key_part +
 
1499
  if (!(bitmap_buf= (my_bitmap_map*) alloc_root(param->mem_root,
 
1500
                                                param->fields_bitmap_size)))
 
1501
    return NULL;
 
1502
 
 
1503
  if (ror_scan->covered_fields.init(bitmap_buf,
 
1504
                                    param->table->s->fields))
 
1505
    return NULL;
 
1506
  ror_scan->covered_fields.clearAll();
 
1507
 
 
1508
  KEY_PART_INFO *key_part= param->table->key_info[keynr].key_part;
 
1509
  KEY_PART_INFO *key_part_end= key_part +
1227
1510
                               param->table->key_info[keynr].key_parts;
1228
 
  for (; key_part != key_part_end; ++key_part)
 
1511
  for (;key_part != key_part_end; ++key_part)
1229
1512
  {
1230
 
    if (param->needed_fields.test(key_part->fieldnr-1))
1231
 
      tmp_bitset.set(key_part->fieldnr-1);
 
1513
    if (param->needed_fields.isBitSet(key_part->fieldnr-1))
 
1514
      ror_scan->covered_fields.setBit(key_part->fieldnr-1);
1232
1515
  }
1233
1516
  double rows= rows2double(param->table->quick_rows[ror_scan->keynr]);
1234
1517
  ror_scan->index_read_cost=
1235
1518
    param->table->cursor->index_only_read_time(ror_scan->keynr, rows);
1236
 
  ror_scan->covered_fields= tmp_bitset.to_ulong();
1237
 
  return ror_scan;
 
1519
  return(ror_scan);
1238
1520
}
1239
1521
 
1240
1522
 
1241
1523
/*
1242
 
  Compare two optimizer::RorScanInfo** by  E(#records_matched) * key_record_length.
 
1524
  Compare two ROR_SCAN_INFO** by  E(#records_matched) * key_record_length.
1243
1525
  SYNOPSIS
1244
1526
    cmp_ror_scan_info()
1245
1527
      a ptr to first compared value
1251
1533
    1 a > b
1252
1534
*/
1253
1535
 
1254
 
static int cmp_ror_scan_info(optimizer::RorScanInfo** a, optimizer::RorScanInfo** b)
 
1536
static int cmp_ror_scan_info(ROR_SCAN_INFO** a, ROR_SCAN_INFO** b)
1255
1537
{
1256
1538
  double val1= rows2double((*a)->records) * (*a)->key_rec_length;
1257
1539
  double val2= rows2double((*b)->records) * (*b)->key_rec_length;
1258
1540
  return (val1 < val2)? -1: (val1 == val2)? 0 : 1;
1259
1541
}
1260
1542
 
1261
 
 
1262
1543
/*
1263
 
  Compare two optimizer::RorScanInfo** by
 
1544
  Compare two ROR_SCAN_INFO** by
1264
1545
   (#covered fields in F desc,
1265
1546
    #components asc,
1266
1547
    number of first not covered component asc)
1276
1557
    1 a > b
1277
1558
*/
1278
1559
 
1279
 
static int cmp_ror_scan_info_covering(optimizer::RorScanInfo** a, optimizer::RorScanInfo** b)
 
1560
static int cmp_ror_scan_info_covering(ROR_SCAN_INFO** a, ROR_SCAN_INFO** b)
1280
1561
{
1281
1562
  if ((*a)->used_fields_covered > (*b)->used_fields_covered)
1282
1563
    return -1;
1293
1574
  return 0;
1294
1575
}
1295
1576
 
 
1577
 
1296
1578
/* Auxiliary structure for incremental ROR-intersection creation */
1297
 
typedef struct st_ror_intersect_info
 
1579
typedef struct
1298
1580
{
1299
 
  st_ror_intersect_info()
1300
 
    :
1301
 
      param(NULL),
1302
 
      covered_fields(),
1303
 
      out_rows(0.0),
1304
 
      is_covering(false),
1305
 
      index_records(0),
1306
 
      index_scan_costs(0.0),
1307
 
      total_cost(0.0)
1308
 
  {}
1309
 
 
1310
 
  st_ror_intersect_info(const optimizer::Parameter *in_param)
1311
 
    :
1312
 
      param(in_param),
1313
 
      covered_fields(in_param->table->getShare()->sizeFields()),
1314
 
      out_rows(in_param->table->cursor->stats.records),
1315
 
      is_covering(false),
1316
 
      index_records(0),
1317
 
      index_scan_costs(0.0),
1318
 
      total_cost(0.0)
1319
 
  {
1320
 
    covered_fields.reset();
1321
 
  }
1322
 
 
1323
1581
  const optimizer::Parameter *param;
1324
 
  boost::dynamic_bitset<> covered_fields; /* union of fields covered by all scans */
 
1582
  MyBitmap covered_fields; /* union of fields covered by all scans */
1325
1583
  /*
1326
1584
    Fraction of table records that satisfies conditions of all scans.
1327
1585
    This is the number of full records that will be retrieved if a
1337
1595
} ROR_INTERSECT_INFO;
1338
1596
 
1339
1597
 
 
1598
/*
 
1599
  Allocate a ROR_INTERSECT_INFO and initialize it to contain zero scans.
 
1600
 
 
1601
  SYNOPSIS
 
1602
    ror_intersect_init()
 
1603
      param         Parameter from test_quick_select
 
1604
 
 
1605
  RETURN
 
1606
    allocated structure
 
1607
    NULL on error
 
1608
*/
 
1609
 
 
1610
static
 
1611
ROR_INTERSECT_INFO* ror_intersect_init(const optimizer::Parameter *param)
 
1612
{
 
1613
  ROR_INTERSECT_INFO *info;
 
1614
  my_bitmap_map* buf;
 
1615
  if (!(info= (ROR_INTERSECT_INFO*)alloc_root(param->mem_root,
 
1616
                                              sizeof(ROR_INTERSECT_INFO))))
 
1617
    return NULL;
 
1618
  info->param= param;
 
1619
  if (!(buf= (my_bitmap_map*) alloc_root(param->mem_root,
 
1620
                                         param->fields_bitmap_size)))
 
1621
    return NULL;
 
1622
  if (info->covered_fields.init(buf, param->table->s->fields))
 
1623
    return NULL;
 
1624
  info->is_covering= false;
 
1625
  info->index_scan_costs= 0.0;
 
1626
  info->index_records= 0;
 
1627
  info->out_rows= (double) param->table->cursor->stats.records;
 
1628
  info->covered_fields.clearAll();
 
1629
  return info;
 
1630
}
 
1631
 
1340
1632
static void ror_intersect_cpy(ROR_INTERSECT_INFO *dst,
1341
1633
                              const ROR_INTERSECT_INFO *src)
1342
1634
{
1441
1733
*/
1442
1734
 
1443
1735
static double ror_scan_selectivity(const ROR_INTERSECT_INFO *info,
1444
 
                                   const optimizer::RorScanInfo *scan)
 
1736
                                   const ROR_SCAN_INFO *scan)
1445
1737
{
1446
1738
  double selectivity_mult= 1.0;
1447
 
  KeyPartInfo *key_part= info->param->table->key_info[scan->keynr].key_part;
 
1739
  KEY_PART_INFO *key_part= info->param->table->key_info[scan->keynr].key_part;
1448
1740
  unsigned char key_val[MAX_KEY_LENGTH+MAX_FIELD_WIDTH]; /* key values tuple */
1449
1741
  unsigned char *key_ptr= key_val;
1450
1742
  optimizer::SEL_ARG *sel_arg= NULL;
1451
1743
  optimizer::SEL_ARG *tuple_arg= NULL;
1452
1744
  key_part_map keypart_map= 0;
1453
1745
  bool cur_covered;
1454
 
  bool prev_covered= test(info->covered_fields.test(key_part->fieldnr-1));
 
1746
  bool prev_covered= test(info->covered_fields.isBitSet(key_part->fieldnr-1));
1455
1747
  key_range min_range;
1456
1748
  key_range max_range;
1457
1749
  min_range.key= key_val;
1464
1756
       sel_arg= sel_arg->next_key_part)
1465
1757
  {
1466
1758
    cur_covered=
1467
 
      test(info->covered_fields.test(key_part[sel_arg->part].fieldnr-1));
 
1759
      test(info->covered_fields.isBitSet(key_part[sel_arg->part].fieldnr-1));
1468
1760
    if (cur_covered != prev_covered)
1469
1761
    {
1470
1762
      /* create (part1val, ..., part{n-1}val) tuple. */
1549
1841
*/
1550
1842
 
1551
1843
static bool ror_intersect_add(ROR_INTERSECT_INFO *info,
1552
 
                              optimizer::RorScanInfo* ror_scan, bool is_cpk_scan)
 
1844
                              ROR_SCAN_INFO* ror_scan, bool is_cpk_scan)
1553
1845
{
1554
1846
  double selectivity_mult= 1.0;
1555
1847
 
1576
1868
  {
1577
1869
    info->index_records += info->param->table->quick_rows[ror_scan->keynr];
1578
1870
    info->index_scan_costs += ror_scan->index_read_cost;
1579
 
    boost::dynamic_bitset<> tmp_bitset= ror_scan->bitsToBitset();
1580
 
    info->covered_fields|= tmp_bitset;
1581
 
    if (! info->is_covering && info->param->needed_fields.is_subset_of(info->covered_fields))
 
1871
    bitmap_union(&info->covered_fields, &ror_scan->covered_fields);
 
1872
    if (!info->is_covering && bitmap_is_subset(&info->param->needed_fields,
 
1873
                                               &info->covered_fields))
1582
1874
    {
1583
1875
      info->is_covering= true;
1584
1876
    }
1585
1877
  }
1586
1878
 
1587
1879
  info->total_cost= info->index_scan_costs;
1588
 
  if (! info->is_covering)
 
1880
  if (!info->is_covering)
1589
1881
  {
1590
 
    optimizer::CostVector sweep_cost;
1591
 
    Join *join= info->param->session->lex->select_lex.join;
 
1882
    COST_VECT sweep_cost;
 
1883
    JOIN *join= info->param->session->lex->select_lex.join;
1592
1884
    bool is_interrupted= test(join && join->tables == 1);
1593
1885
    get_sweep_read_cost(info->param->table, double2rows(info->out_rows),
1594
1886
                        is_interrupted, &sweep_cost);
1599
1891
 
1600
1892
 
1601
1893
/*
1602
 
  Get best covering ROR-intersection.
1603
 
  SYNOPSIS
1604
 
    get_best_covering_ror_intersect()
1605
 
      param     Parameter from test_quick_select function.
1606
 
      tree      optimizer::SEL_TREE with sets of intervals for different keys.
1607
 
      read_time Don't return table read plans with cost > read_time.
1608
 
 
1609
 
  RETURN
1610
 
    Best covering ROR-intersection plan
1611
 
    NULL if no plan found.
1612
 
 
1613
 
  NOTES
1614
 
    get_best_ror_intersect must be called for a tree before calling this
1615
 
    function for it.
1616
 
    This function invalidates tree->ror_scans member values.
1617
 
 
1618
 
  The following approximate algorithm is used:
1619
 
    I=set of all covering indexes
1620
 
    F=set of all fields to cover
1621
 
    S={}
1622
 
 
1623
 
    do
1624
 
    {
1625
 
      Order I by (#covered fields in F desc,
1626
 
                  #components asc,
1627
 
                  number of first not covered component asc);
1628
 
      F=F-covered by first(I);
1629
 
      S=S+first(I);
1630
 
      I=I-first(I);
1631
 
    } while F is not empty.
1632
 
*/
1633
 
 
1634
 
static
1635
 
optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
1636
 
                                                            optimizer::SEL_TREE *tree,
1637
 
                                                            double read_time)
1638
 
{
1639
 
  optimizer::RorScanInfo **ror_scan_mark;
1640
 
  optimizer::RorScanInfo **ror_scans_end= tree->ror_scans_end;
1641
 
 
1642
 
  for (optimizer::RorScanInfo **scan= tree->ror_scans; scan != ror_scans_end; ++scan)
1643
 
    (*scan)->key_components=
1644
 
      param->table->key_info[(*scan)->keynr].key_parts;
1645
 
 
1646
 
  /*
1647
 
    Run covering-ROR-search algorithm.
1648
 
    Assume set I is [ror_scan .. ror_scans_end)
1649
 
  */
1650
 
 
1651
 
  /*I=set of all covering indexes */
1652
 
  ror_scan_mark= tree->ror_scans;
1653
 
 
1654
 
  boost::dynamic_bitset<> *covered_fields= &param->tmp_covered_fields;
1655
 
  if (covered_fields->empty())
1656
 
  {
1657
 
    covered_fields->resize(param->table->getShare()->sizeFields());
1658
 
  }
1659
 
  covered_fields->reset();
1660
 
 
1661
 
  double total_cost= 0.0f;
1662
 
  ha_rows records=0;
1663
 
  bool all_covered;
1664
 
 
1665
 
  do
1666
 
  {
1667
 
    /*
1668
 
      Update changed sorting info:
1669
 
        #covered fields,
1670
 
        number of first not covered component
1671
 
      Calculate and save these values for each of remaining scans.
1672
 
    */
1673
 
    for (optimizer::RorScanInfo **scan= ror_scan_mark; scan != ror_scans_end; ++scan)
1674
 
    {
1675
 
      /* subtract one bitset from the other */
1676
 
      (*scan)->subtractBitset(*covered_fields);
1677
 
      (*scan)->used_fields_covered=
1678
 
        (*scan)->getBitCount();
1679
 
      (*scan)->first_uncovered_field= (*scan)->findFirstNotSet();
1680
 
    }
1681
 
 
1682
 
    internal::my_qsort(ror_scan_mark, ror_scans_end-ror_scan_mark,
1683
 
                       sizeof(optimizer::RorScanInfo*),
1684
 
                       (qsort_cmp)cmp_ror_scan_info_covering);
1685
 
 
1686
 
    /* I=I-first(I) */
1687
 
    total_cost += (*ror_scan_mark)->index_read_cost;
1688
 
    records += (*ror_scan_mark)->records;
1689
 
    if (total_cost > read_time)
1690
 
      return NULL;
1691
 
    /* F=F-covered by first(I) */
1692
 
    boost::dynamic_bitset<> tmp_bitset= (*ror_scan_mark)->bitsToBitset();
1693
 
    *covered_fields|= tmp_bitset;
1694
 
    all_covered= param->needed_fields.is_subset_of(*covered_fields);
1695
 
  } while ((++ror_scan_mark < ror_scans_end) && ! all_covered);
1696
 
 
1697
 
  if (!all_covered || (ror_scan_mark - tree->ror_scans) == 1)
1698
 
    return NULL;
1699
 
 
1700
 
  /*
1701
 
    Ok, [tree->ror_scans .. ror_scan) holds covering index_intersection with
1702
 
    cost total_cost.
1703
 
  */
1704
 
  /* Add priority queue use cost. */
1705
 
  total_cost += rows2double(records)*
1706
 
                log((double)(ror_scan_mark - tree->ror_scans)) /
1707
 
                (TIME_FOR_COMPARE_ROWID * M_LN2);
1708
 
 
1709
 
  if (total_cost > read_time)
1710
 
    return NULL;
1711
 
 
1712
 
  optimizer::RorIntersectReadPlan *trp= NULL;
1713
 
  if (! (trp= new (param->mem_root) optimizer::RorIntersectReadPlan))
1714
 
  {
1715
 
    return trp;
1716
 
  }
1717
 
 
1718
 
  uint32_t best_num= (ror_scan_mark - tree->ror_scans);
1719
 
  if (!(trp->first_scan= (optimizer::RorScanInfo**)param->mem_root->alloc_root(sizeof(optimizer::RorScanInfo*)* best_num)))
1720
 
    return NULL;
1721
 
  memcpy(trp->first_scan, tree->ror_scans, best_num*sizeof(optimizer::RorScanInfo*));
1722
 
  trp->last_scan=  trp->first_scan + best_num;
1723
 
  trp->is_covering= true;
1724
 
  trp->read_cost= total_cost;
1725
 
  trp->records= records;
1726
 
  trp->cpk_scan= NULL;
1727
 
  set_if_smaller(param->table->quick_condition_rows, records);
1728
 
 
1729
 
  return(trp);
1730
 
}
1731
 
 
1732
 
 
1733
 
/*
1734
1894
  Get best ROR-intersection plan using non-covering ROR-intersection search
1735
1895
  algorithm. The returned plan may be covering.
1736
1896
 
1796
1956
 
1797
1957
static
1798
1958
optimizer::RorIntersectReadPlan *get_best_ror_intersect(const optimizer::Parameter *param,
1799
 
                                                   optimizer::SEL_TREE *tree,
 
1959
                                                   SEL_TREE *tree,
1800
1960
                                                   double read_time,
1801
1961
                                                   bool *are_all_covering)
1802
1962
{
1803
 
  uint32_t idx= 0;
 
1963
  uint32_t idx;
1804
1964
  double min_cost= DBL_MAX;
1805
1965
 
1806
 
  if ((tree->n_ror_scans < 2) || ! param->table->cursor->stats.records)
 
1966
  if ((tree->n_ror_scans < 2) || !param->table->cursor->stats.records)
1807
1967
    return NULL;
1808
1968
 
1809
1969
  /*
1810
 
    Step1: Collect ROR-able SEL_ARGs and create optimizer::RorScanInfo for each of
 
1970
    Step1: Collect ROR-able SEL_ARGs and create ROR_SCAN_INFO for each of
1811
1971
    them. Also find and save clustered PK scan if there is one.
1812
1972
  */
1813
 
  optimizer::RorScanInfo **cur_ror_scan= NULL;
1814
 
  optimizer::RorScanInfo *cpk_scan= NULL;
1815
 
  uint32_t cpk_no= 0;
 
1973
  ROR_SCAN_INFO **cur_ror_scan;
 
1974
  ROR_SCAN_INFO *cpk_scan= NULL;
 
1975
  uint32_t cpk_no;
1816
1976
  bool cpk_scan_used= false;
1817
1977
 
1818
 
  if (! (tree->ror_scans= (optimizer::RorScanInfo**)param->mem_root->alloc_root(sizeof(optimizer::RorScanInfo*)* param->keys)))
1819
 
  {
 
1978
  if (!(tree->ror_scans= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
 
1979
                                                     sizeof(ROR_SCAN_INFO*)*
 
1980
                                                     param->keys)))
1820
1981
    return NULL;
1821
 
  }
1822
1982
  cpk_no= ((param->table->cursor->primary_key_is_clustered()) ?
1823
 
           param->table->getShare()->getPrimaryKey() : MAX_KEY);
 
1983
           param->table->s->primary_key : MAX_KEY);
1824
1984
 
1825
1985
  for (idx= 0, cur_ror_scan= tree->ror_scans; idx < param->keys; idx++)
1826
1986
  {
1827
 
    optimizer::RorScanInfo *scan;
 
1987
    ROR_SCAN_INFO *scan;
1828
1988
    if (! tree->ror_scans_map.test(idx))
1829
1989
      continue;
1830
 
    if (! (scan= make_ror_scan(param, idx, tree->keys[idx])))
 
1990
    if (!(scan= make_ror_scan(param, idx, tree->keys[idx])))
1831
1991
      return NULL;
1832
1992
    if (param->real_keynr[idx] == cpk_no)
1833
1993
    {
1839
1999
  }
1840
2000
 
1841
2001
  tree->ror_scans_end= cur_ror_scan;
 
2002
  print_ror_scans_arr(param->table, "original",
 
2003
                                          tree->ror_scans,
 
2004
                                          tree->ror_scans_end);
1842
2005
  /*
1843
2006
    Ok, [ror_scans, ror_scans_end) is array of ptrs to initialized
1844
 
    optimizer::RorScanInfo's.
 
2007
    ROR_SCAN_INFO's.
1845
2008
    Step 2: Get best ROR-intersection using an approximate algorithm.
1846
2009
  */
1847
 
  internal::my_qsort(tree->ror_scans, tree->n_ror_scans, sizeof(optimizer::RorScanInfo*),
 
2010
  internal::my_qsort(tree->ror_scans, tree->n_ror_scans, sizeof(ROR_SCAN_INFO*),
1848
2011
                     (qsort_cmp)cmp_ror_scan_info);
 
2012
  print_ror_scans_arr(param->table, "ordered",
 
2013
                                          tree->ror_scans,
 
2014
                                          tree->ror_scans_end);
1849
2015
 
1850
 
  optimizer::RorScanInfo **intersect_scans= NULL; /* ROR scans used in index intersection */
1851
 
  optimizer::RorScanInfo **intersect_scans_end= NULL;
1852
 
  if (! (intersect_scans= (optimizer::RorScanInfo**)param->mem_root->alloc_root(sizeof(optimizer::RorScanInfo*) * tree->n_ror_scans)))
 
2016
  ROR_SCAN_INFO **intersect_scans; /* ROR scans used in index intersection */
 
2017
  ROR_SCAN_INFO **intersect_scans_end;
 
2018
  if (!(intersect_scans= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
 
2019
                                                     sizeof(ROR_SCAN_INFO*)*
 
2020
                                                     tree->n_ror_scans)))
1853
2021
    return NULL;
1854
2022
  intersect_scans_end= intersect_scans;
1855
2023
 
1856
2024
  /* Create and incrementally update ROR intersection. */
1857
 
  ROR_INTERSECT_INFO intersect(param);
1858
 
  ROR_INTERSECT_INFO intersect_best(param);
 
2025
  ROR_INTERSECT_INFO *intersect, *intersect_best;
 
2026
  if (!(intersect= ror_intersect_init(param)) ||
 
2027
      !(intersect_best= ror_intersect_init(param)))
 
2028
    return NULL;
1859
2029
 
1860
2030
  /* [intersect_scans,intersect_scans_best) will hold the best intersection */
1861
 
  optimizer::RorScanInfo **intersect_scans_best= NULL;
 
2031
  ROR_SCAN_INFO **intersect_scans_best;
1862
2032
  cur_ror_scan= tree->ror_scans;
1863
2033
  intersect_scans_best= intersect_scans;
1864
 
  while (cur_ror_scan != tree->ror_scans_end && ! intersect.is_covering)
 
2034
  while (cur_ror_scan != tree->ror_scans_end && !intersect->is_covering)
1865
2035
  {
1866
2036
    /* S= S + first(R);  R= R - first(R); */
1867
 
    if (! ror_intersect_add(&intersect, *cur_ror_scan, false))
 
2037
    if (!ror_intersect_add(intersect, *cur_ror_scan, false))
1868
2038
    {
1869
2039
      cur_ror_scan++;
1870
2040
      continue;
1872
2042
 
1873
2043
    *(intersect_scans_end++)= *(cur_ror_scan++);
1874
2044
 
1875
 
    if (intersect.total_cost < min_cost)
 
2045
    if (intersect->total_cost < min_cost)
1876
2046
    {
1877
2047
      /* Local minimum found, save it */
1878
 
      ror_intersect_cpy(&intersect_best, &intersect);
 
2048
      ror_intersect_cpy(intersect_best, intersect);
1879
2049
      intersect_scans_best= intersect_scans_end;
1880
 
      min_cost = intersect.total_cost;
 
2050
      min_cost = intersect->total_cost;
1881
2051
    }
1882
2052
  }
1883
2053
 
1886
2056
    return NULL;
1887
2057
  }
1888
2058
 
1889
 
  *are_all_covering= intersect.is_covering;
 
2059
  print_ror_scans_arr(param->table,
 
2060
                                          "best ROR-intersection",
 
2061
                                          intersect_scans,
 
2062
                                          intersect_scans_best);
 
2063
 
 
2064
  *are_all_covering= intersect->is_covering;
1890
2065
  uint32_t best_num= intersect_scans_best - intersect_scans;
1891
 
  ror_intersect_cpy(&intersect, &intersect_best);
 
2066
  ror_intersect_cpy(intersect, intersect_best);
1892
2067
 
1893
2068
  /*
1894
2069
    Ok, found the best ROR-intersection of non-CPK key scans.
1895
2070
    Check if we should add a CPK scan. If the obtained ROR-intersection is
1896
2071
    covering, it doesn't make sense to add CPK scan.
1897
2072
  */
1898
 
  if (cpk_scan && ! intersect.is_covering)
 
2073
  if (cpk_scan && !intersect->is_covering)
1899
2074
  {
1900
 
    if (ror_intersect_add(&intersect, cpk_scan, true) &&
1901
 
        (intersect.total_cost < min_cost))
 
2075
    if (ror_intersect_add(intersect, cpk_scan, true) &&
 
2076
        (intersect->total_cost < min_cost))
1902
2077
    {
1903
2078
      cpk_scan_used= true;
1904
2079
      intersect_best= intersect; //just set pointer here
1913
2088
      return trp;
1914
2089
 
1915
2090
    if (! (trp->first_scan=
1916
 
           (optimizer::RorScanInfo**)param->mem_root->alloc_root(sizeof(optimizer::RorScanInfo*)*best_num)))
 
2091
           (ROR_SCAN_INFO**)alloc_root(param->mem_root,
 
2092
                                       sizeof(ROR_SCAN_INFO*)*best_num)))
1917
2093
      return NULL;
1918
 
    memcpy(trp->first_scan, intersect_scans, best_num*sizeof(optimizer::RorScanInfo*));
 
2094
    memcpy(trp->first_scan, intersect_scans, best_num*sizeof(ROR_SCAN_INFO*));
1919
2095
    trp->last_scan=  trp->first_scan + best_num;
1920
 
    trp->is_covering= intersect_best.is_covering;
1921
 
    trp->read_cost= intersect_best.total_cost;
 
2096
    trp->is_covering= intersect_best->is_covering;
 
2097
    trp->read_cost= intersect_best->total_cost;
1922
2098
    /* Prevent divisons by zero */
1923
 
    ha_rows best_rows = double2rows(intersect_best.out_rows);
1924
 
    if (! best_rows)
 
2099
    ha_rows best_rows = double2rows(intersect_best->out_rows);
 
2100
    if (!best_rows)
1925
2101
      best_rows= 1;
1926
2102
    set_if_smaller(param->table->quick_condition_rows, best_rows);
1927
2103
    trp->records= best_rows;
1928
 
    trp->index_scan_costs= intersect_best.index_scan_costs;
 
2104
    trp->index_scan_costs= intersect_best->index_scan_costs;
1929
2105
    trp->cpk_scan= cpk_scan_used? cpk_scan: NULL;
1930
2106
  }
1931
 
  return trp;
1932
 
}
1933
 
 
1934
 
 
1935
 
/*
1936
 
  Get best "range" table read plan for given optimizer::SEL_TREE, also update some info
 
2107
  return(trp);
 
2108
}
 
2109
 
 
2110
 
 
2111
/*
 
2112
  Get best covering ROR-intersection.
 
2113
  SYNOPSIS
 
2114
    get_best_covering_ror_intersect()
 
2115
      param     Parameter from test_quick_select function.
 
2116
      tree      SEL_TREE with sets of intervals for different keys.
 
2117
      read_time Don't return table read plans with cost > read_time.
 
2118
 
 
2119
  RETURN
 
2120
    Best covering ROR-intersection plan
 
2121
    NULL if no plan found.
 
2122
 
 
2123
  NOTES
 
2124
    get_best_ror_intersect must be called for a tree before calling this
 
2125
    function for it.
 
2126
    This function invalidates tree->ror_scans member values.
 
2127
 
 
2128
  The following approximate algorithm is used:
 
2129
    I=set of all covering indexes
 
2130
    F=set of all fields to cover
 
2131
    S={}
 
2132
 
 
2133
    do
 
2134
    {
 
2135
      Order I by (#covered fields in F desc,
 
2136
                  #components asc,
 
2137
                  number of first not covered component asc);
 
2138
      F=F-covered by first(I);
 
2139
      S=S+first(I);
 
2140
      I=I-first(I);
 
2141
    } while F is not empty.
 
2142
*/
 
2143
 
 
2144
static
 
2145
optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
 
2146
                                                            SEL_TREE *tree,
 
2147
                                                            double read_time)
 
2148
{
 
2149
  ROR_SCAN_INFO **ror_scan_mark;
 
2150
  ROR_SCAN_INFO **ror_scans_end= tree->ror_scans_end;
 
2151
 
 
2152
  for (ROR_SCAN_INFO **scan= tree->ror_scans; scan != ror_scans_end; ++scan)
 
2153
    (*scan)->key_components=
 
2154
      param->table->key_info[(*scan)->keynr].key_parts;
 
2155
 
 
2156
  /*
 
2157
    Run covering-ROR-search algorithm.
 
2158
    Assume set I is [ror_scan .. ror_scans_end)
 
2159
  */
 
2160
 
 
2161
  /*I=set of all covering indexes */
 
2162
  ror_scan_mark= tree->ror_scans;
 
2163
 
 
2164
  MyBitmap *covered_fields= &param->tmp_covered_fields;
 
2165
  if (! covered_fields->getBitmap())
 
2166
  {
 
2167
    my_bitmap_map *tmp_bitmap= (my_bitmap_map*)alloc_root(param->mem_root,
 
2168
                                               param->fields_bitmap_size);
 
2169
    covered_fields->setBitmap(tmp_bitmap);
 
2170
  }
 
2171
  if (! covered_fields->getBitmap() ||
 
2172
      covered_fields->init(covered_fields->getBitmap(),
 
2173
                           param->table->s->fields))
 
2174
    return 0;
 
2175
  covered_fields->clearAll();
 
2176
 
 
2177
  double total_cost= 0.0f;
 
2178
  ha_rows records=0;
 
2179
  bool all_covered;
 
2180
 
 
2181
  print_ror_scans_arr(param->table,
 
2182
                                           "building covering ROR-I",
 
2183
                                           ror_scan_mark, ror_scans_end);
 
2184
  do
 
2185
  {
 
2186
    /*
 
2187
      Update changed sorting info:
 
2188
        #covered fields,
 
2189
        number of first not covered component
 
2190
      Calculate and save these values for each of remaining scans.
 
2191
    */
 
2192
    for (ROR_SCAN_INFO **scan= ror_scan_mark; scan != ror_scans_end; ++scan)
 
2193
    {
 
2194
      bitmap_subtract(&(*scan)->covered_fields, covered_fields);
 
2195
      (*scan)->used_fields_covered=
 
2196
        (*scan)->covered_fields.getBitsSet();
 
2197
      (*scan)->first_uncovered_field=
 
2198
        (*scan)->covered_fields.getFirst();
 
2199
    }
 
2200
 
 
2201
    internal::my_qsort(ror_scan_mark, ror_scans_end-ror_scan_mark,
 
2202
                       sizeof(ROR_SCAN_INFO*),
 
2203
                       (qsort_cmp)cmp_ror_scan_info_covering);
 
2204
 
 
2205
    print_ror_scans_arr(param->table,
 
2206
                                             "remaining scans",
 
2207
                                             ror_scan_mark, ror_scans_end);
 
2208
 
 
2209
    /* I=I-first(I) */
 
2210
    total_cost += (*ror_scan_mark)->index_read_cost;
 
2211
    records += (*ror_scan_mark)->records;
 
2212
    if (total_cost > read_time)
 
2213
      return NULL;
 
2214
    /* F=F-covered by first(I) */
 
2215
    bitmap_union(covered_fields, &(*ror_scan_mark)->covered_fields);
 
2216
    all_covered= bitmap_is_subset(&param->needed_fields, covered_fields);
 
2217
  } while ((++ror_scan_mark < ror_scans_end) && !all_covered);
 
2218
 
 
2219
  if (!all_covered || (ror_scan_mark - tree->ror_scans) == 1)
 
2220
    return NULL;
 
2221
 
 
2222
  /*
 
2223
    Ok, [tree->ror_scans .. ror_scan) holds covering index_intersection with
 
2224
    cost total_cost.
 
2225
  */
 
2226
  print_ror_scans_arr(param->table,
 
2227
                                           "creating covering ROR-intersect",
 
2228
                                           tree->ror_scans, ror_scan_mark);
 
2229
 
 
2230
  /* Add priority queue use cost. */
 
2231
  total_cost += rows2double(records)*
 
2232
                log((double)(ror_scan_mark - tree->ror_scans)) /
 
2233
                (TIME_FOR_COMPARE_ROWID * M_LN2);
 
2234
 
 
2235
  if (total_cost > read_time)
 
2236
    return NULL;
 
2237
 
 
2238
  optimizer::RorIntersectReadPlan *trp= NULL;
 
2239
  if (! (trp= new (param->mem_root) optimizer::RorIntersectReadPlan))
 
2240
  {
 
2241
    return trp;
 
2242
  }
 
2243
 
 
2244
  uint32_t best_num= (ror_scan_mark - tree->ror_scans);
 
2245
  if (!(trp->first_scan= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
 
2246
                                                     sizeof(ROR_SCAN_INFO*)*
 
2247
                                                     best_num)))
 
2248
    return NULL;
 
2249
  memcpy(trp->first_scan, tree->ror_scans, best_num*sizeof(ROR_SCAN_INFO*));
 
2250
  trp->last_scan=  trp->first_scan + best_num;
 
2251
  trp->is_covering= true;
 
2252
  trp->read_cost= total_cost;
 
2253
  trp->records= records;
 
2254
  trp->cpk_scan= NULL;
 
2255
  set_if_smaller(param->table->quick_condition_rows, records);
 
2256
 
 
2257
  return(trp);
 
2258
}
 
2259
 
 
2260
 
 
2261
/*
 
2262
  Get best "range" table read plan for given SEL_TREE, also update some info
1937
2263
 
1938
2264
  SYNOPSIS
1939
2265
    get_key_scans_params()
1940
 
      session
1941
2266
      param                    Parameters from test_quick_select
1942
 
      tree                     Make range select for this optimizer::SEL_TREE
 
2267
      tree                     Make range select for this SEL_TREE
1943
2268
      index_read_must_be_used  true <=> assume 'index only' option will be set
1944
2269
                               (except for clustered PK indexes)
1945
2270
      update_tbl_stats         true <=> update table->quick_* with information
1948
2273
                               cost > read_time.
1949
2274
 
1950
2275
  DESCRIPTION
1951
 
    Find the best "range" table read plan for given optimizer::SEL_TREE.
 
2276
    Find the best "range" table read plan for given SEL_TREE.
1952
2277
    The side effects are
1953
2278
     - tree->ror_scans is updated to indicate which scans are ROR scans.
1954
2279
     - if update_tbl_stats=true then table->quick_* is updated with info
1959
2284
    NULL if no plan found or error occurred
1960
2285
*/
1961
2286
 
1962
 
static optimizer::RangeReadPlan *get_key_scans_params(Session *session,
1963
 
                                                      optimizer::Parameter *param,
1964
 
                                                      optimizer::SEL_TREE *tree,
 
2287
static optimizer::RangeReadPlan *get_key_scans_params(optimizer::Parameter *param,
 
2288
                                                      SEL_TREE *tree,
1965
2289
                                                      bool index_read_must_be_used,
1966
2290
                                                      bool update_tbl_stats,
1967
2291
                                                      double read_time)
1975
2299
  uint32_t best_buf_size= 0;
1976
2300
  optimizer::RangeReadPlan *read_plan= NULL;
1977
2301
  /*
1978
 
    Note that there may be trees that have type optimizer::SEL_TREE::KEY but contain no
 
2302
    Note that there may be trees that have type SEL_TREE::KEY but contain no
1979
2303
    key reads at all, e.g. tree for expression "key1 is not null" where key1
1980
2304
    is defined as "not null".
1981
2305
  */
 
2306
  print_sel_tree(param, tree, &tree->keys_map, "tree scans");
1982
2307
  tree->ror_scans_map.reset();
1983
2308
  tree->n_ror_scans= 0;
1984
2309
  for (idx= 0,key=tree->keys, end=key+param->keys; key != end; key++,idx++)
1986
2311
    if (*key)
1987
2312
    {
1988
2313
      ha_rows found_records;
1989
 
      optimizer::CostVector cost;
 
2314
      COST_VECT cost;
1990
2315
      double found_read_time= 0.0;
1991
2316
      uint32_t mrr_flags, buf_size;
1992
2317
      uint32_t keynr= param->real_keynr[idx];
1997
2322
      bool read_index_only= index_read_must_be_used ||
1998
2323
                            param->table->covering_keys.test(keynr);
1999
2324
 
2000
 
      found_records= check_quick_select(session, param, idx, read_index_only, *key,
 
2325
      found_records= check_quick_select(param, idx, read_index_only, *key,
2001
2326
                                        update_tbl_stats, &mrr_flags,
2002
2327
                                        &buf_size, &cost);
2003
2328
      found_read_time= cost.total_cost();
2017
2342
    }
2018
2343
  }
2019
2344
 
 
2345
  print_sel_tree(param, tree, &tree->ror_scans_map, "ROR scans");
2020
2346
  if (key_to_read)
2021
2347
  {
2022
2348
    idx= key_to_read - tree->keys;
2076
2402
                                                (retrieve_full_rows? (! is_covering) : false),
2077
2403
                                                parent_alloc)))
2078
2404
  {
 
2405
    print_ror_scans_arr(param->table,
 
2406
                        "creating ROR-intersect",
 
2407
                        first_scan,
 
2408
                        last_scan);
2079
2409
    alloc= parent_alloc ? parent_alloc : &quick_intersect->alloc;
2080
2410
    for (; first_scan != last_scan; ++first_scan)
2081
2411
    {
2140
2470
 
2141
2471
 
2142
2472
/*
2143
 
  Build a optimizer::SEL_TREE for <> or NOT BETWEEN predicate
 
2473
  Build a SEL_TREE for <> or NOT BETWEEN predicate
2144
2474
 
2145
2475
  SYNOPSIS
2146
2476
    get_ne_mm_tree()
2155
2485
    #  Pointer to tree built tree
2156
2486
    0  on error
2157
2487
*/
2158
 
static optimizer::SEL_TREE *get_ne_mm_tree(optimizer::RangeParameter *param,
 
2488
static SEL_TREE *get_ne_mm_tree(optimizer::RangeParameter *param,
2159
2489
                                Item_func *cond_func,
2160
2490
                                Field *field,
2161
2491
                                Item *lt_value, Item *gt_value,
2162
2492
                                Item_result cmp_type)
2163
2493
{
2164
 
  optimizer::SEL_TREE *tree= NULL;
 
2494
  SEL_TREE *tree;
2165
2495
  tree= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
2166
2496
                     lt_value, cmp_type);
2167
2497
  if (tree)
2178
2508
 
2179
2509
 
2180
2510
/*
2181
 
  Build a optimizer::SEL_TREE for a simple predicate
 
2511
  Build a SEL_TREE for a simple predicate
2182
2512
 
2183
2513
  SYNOPSIS
2184
2514
    get_func_mm_tree()
2193
2523
  RETURN
2194
2524
    Pointer to the tree built tree
2195
2525
*/
2196
 
static optimizer::SEL_TREE *get_func_mm_tree(optimizer::RangeParameter *param,
 
2526
static SEL_TREE *get_func_mm_tree(optimizer::RangeParameter *param,
2197
2527
                                  Item_func *cond_func,
2198
2528
                                  Field *field, 
2199
2529
                                  Item *value,
2200
2530
                                  Item_result cmp_type, 
2201
2531
                                  bool inv)
2202
2532
{
2203
 
  optimizer::SEL_TREE *tree= NULL;
 
2533
  SEL_TREE *tree= NULL;
2204
2534
 
2205
2535
  switch (cond_func->functype()) 
2206
2536
  {
2272
2602
      {
2273
2603
        /*
2274
2604
          We get here for conditions in form "t.key NOT IN (c1, c2, ...)",
2275
 
          where c{i} are constants. Our goal is to produce a optimizer::SEL_TREE that
 
2605
          where c{i} are constants. Our goal is to produce a SEL_TREE that
2276
2606
          represents intervals:
2277
2607
 
2278
2608
          ($MIN<t.key<c1) OR (c1<t.key<c2) OR (c2<t.key<c3) OR ...    (*)
2281
2611
 
2282
2612
          The most straightforward way to produce it is to convert NOT IN
2283
2613
          into "(t.key != c1) AND (t.key != c2) AND ... " and let the range
2284
 
          analyzer to build optimizer::SEL_TREE from that. The problem is that the
 
2614
          analyzer to build SEL_TREE from that. The problem is that the
2285
2615
          range analyzer will use O(N^2) memory (which is probably a bug),
2286
2616
          and people do use big NOT IN lists (e.g. see BUG#15872, BUG#21282),
2287
2617
          will run out of memory.
2294
2624
 
2295
2625
          Considering the above, we'll handle NOT IN as follows:
2296
2626
          * if the number of entries in the NOT IN list is less than
2297
 
            NOT_IN_IGNORE_THRESHOLD, construct the optimizer::SEL_TREE (*) manually.
2298
 
          * Otherwise, don't produce a optimizer::SEL_TREE.
 
2627
            NOT_IN_IGNORE_THRESHOLD, construct the SEL_TREE (*) manually.
 
2628
          * Otherwise, don't produce a SEL_TREE.
2299
2629
        */
2300
2630
#define NOT_IN_IGNORE_THRESHOLD 1000
2301
2631
        memory::Root *tmp_root= param->mem_root;
2314
2644
        if (func->array->count > NOT_IN_IGNORE_THRESHOLD || ! value_item)
2315
2645
          break;
2316
2646
 
2317
 
        /* Get a optimizer::SEL_TREE for "(-inf|NULL) < X < c_0" interval.  */
 
2647
        /* Get a SEL_TREE for "(-inf|NULL) < X < c_0" interval.  */
2318
2648
        uint32_t i=0;
2319
2649
        do
2320
2650
        {
2327
2657
          if (! tree)
2328
2658
            break;
2329
2659
          i++;
2330
 
        } while (i < func->array->count && tree->type == optimizer::SEL_TREE::IMPOSSIBLE);
 
2660
        } while (i < func->array->count && tree->type == SEL_TREE::IMPOSSIBLE);
2331
2661
 
2332
 
        if (!tree || tree->type == optimizer::SEL_TREE::IMPOSSIBLE)
 
2662
        if (!tree || tree->type == SEL_TREE::IMPOSSIBLE)
2333
2663
        {
2334
2664
          /* We get here in cases like "t.unsigned NOT IN (-1,-2,-3) */
2335
2665
          tree= NULL;
2336
2666
          break;
2337
2667
        }
2338
 
        optimizer::SEL_TREE *tree2= NULL;
 
2668
        SEL_TREE *tree2;
2339
2669
        for (; i < func->array->count; i++)
2340
2670
        {
2341
2671
          if (func->array->compare_elems(i, i-1))
2342
2672
          {
2343
 
            /* Get a optimizer::SEL_TREE for "-inf < X < c_i" interval */
 
2673
            /* Get a SEL_TREE for "-inf < X < c_i" interval */
2344
2674
            func->array->value_to_item(i, value_item);
2345
2675
            tree2= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
2346
2676
                                value_item, cmp_type);
2370
2700
          }
2371
2701
        }
2372
2702
 
2373
 
        if (tree && tree->type != optimizer::SEL_TREE::IMPOSSIBLE)
 
2703
        if (tree && tree->type != SEL_TREE::IMPOSSIBLE)
2374
2704
        {
2375
2705
          /*
2376
 
            Get the optimizer::SEL_TREE for the last "c_last < X < +inf" interval
 
2706
            Get the SEL_TREE for the last "c_last < X < +inf" interval
2377
2707
            (value_item cotains c_last already)
2378
2708
          */
2379
2709
          tree2= get_mm_parts(param, cond_func, field, Item_func::GT_FUNC,
2437
2767
 
2438
2768
 
2439
2769
/*
2440
 
  Build conjunction of all optimizer::SEL_TREEs for a simple predicate applying equalities
 
2770
  Build conjunction of all SEL_TREEs for a simple predicate applying equalities
2441
2771
 
2442
2772
  SYNOPSIS
2443
2773
    get_full_func_mm_tree()
2452
2782
 
2453
2783
  DESCRIPTION
2454
2784
    For a simple SARGable predicate of the form (f op c), where f is a field and
2455
 
    c is a constant, the function builds a conjunction of all optimizer::SEL_TREES that can
 
2785
    c is a constant, the function builds a conjunction of all SEL_TREES that can
2456
2786
    be obtained by the substitution of f for all different fields equal to f.
2457
2787
 
2458
2788
  NOTES
2462
2792
    each fj belonging to the same multiple equality as fi
2463
2793
    are built as well.
2464
2794
    E.g. for WHERE t1.a=t2.a AND t2.a > 10
2465
 
    a optimizer::SEL_TREE for t2.a > 10 will be built for quick select from t2
 
2795
    a SEL_TREE for t2.a > 10 will be built for quick select from t2
2466
2796
    and
2467
 
    a optimizer::SEL_TREE for t1.a > 10 will be built for quick select from t1.
 
2797
    a SEL_TREE for t1.a > 10 will be built for quick select from t1.
2468
2798
 
2469
2799
    A BETWEEN predicate of the form (fi [NOT] BETWEEN c1 AND c2) is treated
2470
2800
    in a similar way: we build a conjuction of trees for the results
2503
2833
    the form (c IN (c1,...,f,...,cn)).
2504
2834
 
2505
2835
  RETURN
2506
 
    Pointer to the tree representing the built conjunction of optimizer::SEL_TREEs
 
2836
    Pointer to the tree representing the built conjunction of SEL_TREEs
2507
2837
*/
2508
2838
 
2509
 
static optimizer::SEL_TREE *get_full_func_mm_tree(optimizer::RangeParameter *param,
 
2839
static SEL_TREE *get_full_func_mm_tree(optimizer::RangeParameter *param,
2510
2840
                                       Item_func *cond_func,
2511
2841
                                       Item_field *field_item, Item *value,
2512
2842
                                       bool inv)
2513
2843
{
2514
 
  optimizer::SEL_TREE *tree= 0;
2515
 
  optimizer::SEL_TREE *ftree= 0;
 
2844
  SEL_TREE *tree= 0;
 
2845
  SEL_TREE *ftree= 0;
2516
2846
  table_map ref_tables= 0;
2517
2847
  table_map param_comp= ~(param->prev_tables | param->read_tables |
2518
2848
                          param->current_table);
2528
2858
  field->setWriteSet();
2529
2859
 
2530
2860
  Item_result cmp_type= field->cmp_type();
2531
 
  if (!((ref_tables | field->getTable()->map) & param_comp))
 
2861
  if (!((ref_tables | field->table->map) & param_comp))
2532
2862
    ftree= get_func_mm_tree(param, cond_func, field, value, cmp_type, inv);
2533
2863
  Item_equal *item_equal= field_item->item_equal;
2534
2864
  if (item_equal)
2542
2872
 
2543
2873
      if (field->eq(f))
2544
2874
        continue;
2545
 
      if (!((ref_tables | f->getTable()->map) & param_comp))
 
2875
      if (!((ref_tables | f->table->map) & param_comp))
2546
2876
      {
2547
2877
        tree= get_func_mm_tree(param, cond_func, f, value, cmp_type, inv);
2548
2878
        ftree= !ftree ? tree : tree_and(param, ftree, tree);
2554
2884
 
2555
2885
        /* make a select tree of all keys in condition */
2556
2886
 
2557
 
static optimizer::SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond)
 
2887
static SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond)
2558
2888
{
2559
 
  optimizer::SEL_TREE *tree=0;
2560
 
  optimizer::SEL_TREE *ftree= 0;
 
2889
  SEL_TREE *tree=0;
 
2890
  SEL_TREE *ftree= 0;
2561
2891
  Item_field *field_item= 0;
2562
2892
  bool inv= false;
2563
2893
  Item *value= 0;
2572
2902
      Item *item;
2573
2903
      while ((item=li++))
2574
2904
      {
2575
 
        optimizer::SEL_TREE *new_tree= get_mm_tree(param,item);
 
2905
        SEL_TREE *new_tree= get_mm_tree(param,item);
2576
2906
        if (param->session->is_fatal_error ||
2577
2907
            param->alloced_sel_args > optimizer::SEL_ARG::MAX_SEL_ARGS)
2578
2908
          return 0;     // out of memory
2579
2909
        tree=tree_and(param,tree,new_tree);
2580
 
        if (tree && tree->type == optimizer::SEL_TREE::IMPOSSIBLE)
 
2910
        if (tree && tree->type == SEL_TREE::IMPOSSIBLE)
2581
2911
          break;
2582
2912
      }
2583
2913
    }
2589
2919
        Item *item;
2590
2920
        while ((item=li++))
2591
2921
        {
2592
 
          optimizer::SEL_TREE *new_tree= get_mm_tree(param,item);
 
2922
          SEL_TREE *new_tree= get_mm_tree(param,item);
2593
2923
          if (!new_tree)
2594
2924
            return 0;   // out of memory
2595
2925
          tree=tree_or(param,tree,new_tree);
2596
 
          if (!tree || tree->type == optimizer::SEL_TREE::ALWAYS)
 
2926
          if (!tree || tree->type == SEL_TREE::ALWAYS)
2597
2927
            break;
2598
2928
        }
2599
2929
      }
2600
2930
    }
2601
2931
    return(tree);
2602
2932
  }
2603
 
  /* Here when simple cond
2604
 
     There are limits on what kinds of const items we can evaluate, grep for
2605
 
     DontEvaluateMaterializedSubqueryTooEarly.
2606
 
  */
2607
 
  if (cond->const_item()  && !cond->is_expensive())
 
2933
  /* Here when simple cond */
 
2934
  if (cond->const_item())
2608
2935
  {
2609
2936
    /*
2610
2937
      During the cond->val_int() evaluation we can come across a subselect
2614
2941
    */
2615
2942
    memory::Root *tmp_root= param->mem_root;
2616
2943
    param->session->mem_root= param->old_root;
2617
 
    tree= cond->val_int() ? new(tmp_root) optimizer::SEL_TREE(optimizer::SEL_TREE::ALWAYS) :
2618
 
                            new(tmp_root) optimizer::SEL_TREE(optimizer::SEL_TREE::IMPOSSIBLE);
 
2944
    tree= cond->val_int() ? new(tmp_root) SEL_TREE(SEL_TREE::ALWAYS) :
 
2945
                            new(tmp_root) SEL_TREE(SEL_TREE::IMPOSSIBLE);
2619
2946
    param->session->mem_root= tmp_root;
2620
2947
    return(tree);
2621
2948
  }
2629
2956
    if ((ref_tables & param->current_table) ||
2630
2957
        (ref_tables & ~(param->prev_tables | param->read_tables)))
2631
2958
      return 0;
2632
 
    return(new optimizer::SEL_TREE(optimizer::SEL_TREE::MAYBE));
 
2959
    return(new SEL_TREE(SEL_TREE::MAYBE));
2633
2960
  }
2634
2961
 
2635
2962
  Item_func *cond_func= (Item_func*) cond;
2658
2985
      if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM)
2659
2986
      {
2660
2987
        field_item= (Item_field*) (cond_func->arguments()[i]->real_item());
2661
 
        optimizer::SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func,
 
2988
        SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func,
2662
2989
                                    field_item, (Item*)(intptr_t)i, inv);
2663
2990
        if (inv)
2664
2991
          tree= !tree ? tmp : tree_or(param, tree, tmp);
2696
3023
      field->setWriteSet();
2697
3024
 
2698
3025
      Item_result cmp_type= field->cmp_type();
2699
 
      if (!((ref_tables | field->getTable()->map) & param_comp))
 
3026
      if (!((ref_tables | field->table->map) & param_comp))
2700
3027
      {
2701
3028
        tree= get_mm_parts(param, cond, field, Item_func::EQ_FUNC,
2702
3029
                           value,cmp_type);
2728
3055
}
2729
3056
 
2730
3057
 
2731
 
static optimizer::SEL_TREE *
 
3058
static SEL_TREE *
2732
3059
get_mm_parts(optimizer::RangeParameter *param,
2733
3060
             COND *cond_func,
2734
3061
             Field *field,
2735
3062
                   Item_func::Functype type,
2736
3063
                   Item *value, Item_result)
2737
3064
{
2738
 
  if (field->getTable() != param->table)
 
3065
  if (field->table != param->table)
2739
3066
    return 0;
2740
3067
 
2741
3068
  KEY_PART *key_part = param->key_parts;
2742
3069
  KEY_PART *end = param->key_parts_end;
2743
 
  optimizer::SEL_TREE *tree=0;
 
3070
  SEL_TREE *tree=0;
2744
3071
  if (value &&
2745
3072
      value->used_tables() & ~(param->prev_tables | param->read_tables))
2746
3073
    return 0;
2749
3076
    if (field->eq(key_part->field))
2750
3077
    {
2751
3078
      optimizer::SEL_ARG *sel_arg=0;
2752
 
      if (!tree && !(tree=new optimizer::SEL_TREE()))
 
3079
      if (!tree && !(tree=new SEL_TREE()))
2753
3080
        return 0;                               // OOM
2754
3081
      if (!value || !(value->used_tables() & ~param->read_tables))
2755
3082
      {
2759
3086
          continue;
2760
3087
        if (sel_arg->type == optimizer::SEL_ARG::IMPOSSIBLE)
2761
3088
        {
2762
 
          tree->type=optimizer::SEL_TREE::IMPOSSIBLE;
 
3089
          tree->type=SEL_TREE::IMPOSSIBLE;
2763
3090
          return(tree);
2764
3091
        }
2765
3092
      }
2805
3132
  param->session->mem_root= param->old_root;
2806
3133
  if (!value)                                   // IS NULL or IS NOT NULL
2807
3134
  {
2808
 
    if (field->getTable()->maybe_null)          // Can't use a key on this
 
3135
    if (field->table->maybe_null)               // Can't use a key on this
2809
3136
      goto end;
2810
3137
    if (!maybe_null)                            // Not null field
2811
3138
    {
2890
3217
    {
2891
3218
      if (unlikely(length < field_length))
2892
3219
      {
2893
 
        /*
2894
 
          This can only happen in a table created with UNIREG where one key
2895
 
          overlaps many fields
2896
 
        */
2897
 
        length= field_length;
 
3220
        /*
 
3221
          This can only happen in a table created with UNIREG where one key
 
3222
          overlaps many fields
 
3223
        */
 
3224
        length= field_length;
2898
3225
      }
2899
3226
      else
2900
 
        field_length= length;
 
3227
        field_length= length;
2901
3228
    }
2902
3229
    length+=offset;
2903
 
    if (!(min_str= (unsigned char*) alloc->alloc_root(length*2)))
2904
 
    {
 
3230
    if (!(min_str= (unsigned char*) alloc_root(alloc, length*2)))
2905
3231
      goto end;
2906
 
    }
2907
3232
 
2908
3233
    max_str=min_str+length;
2909
3234
    if (maybe_null)
3122
3447
    tree= &optimizer::null_element;                        // cmp with NULL is never true
3123
3448
    goto end;
3124
3449
  }
3125
 
 
3126
 
  /*
3127
 
    Any predicate except "<=>"(null-safe equality operator) involving NULL as a
3128
 
    constant is always FALSE
3129
 
    Put IMPOSSIBLE Tree(null_element) here.
3130
 
  */  
3131
 
  if (type != Item_func::EQUAL_FUNC && field->is_real_null())
3132
 
  {
3133
 
    tree= &optimizer::null_element;
3134
 
    goto end;
3135
 
  }
3136
 
 
3137
 
  str= (unsigned char*) alloc->alloc_root(key_part->store_length+1);
 
3450
  str= (unsigned char*) alloc_root(alloc, key_part->store_length+1);
3138
3451
  if (!str)
3139
3452
    goto end;
3140
3453
  if (maybe_null)
3260
3573
#define swap_clone_flag(A) ((A & 1) << 1) | ((A & 2) >> 1)
3261
3574
 
3262
3575
 
3263
 
static optimizer::SEL_TREE *
3264
 
tree_and(optimizer::RangeParameter *param, optimizer::SEL_TREE *tree1, optimizer::SEL_TREE *tree2)
 
3576
static SEL_TREE *
 
3577
tree_and(optimizer::RangeParameter *param, SEL_TREE *tree1, SEL_TREE *tree2)
3265
3578
{
3266
3579
  if (!tree1)
3267
3580
    return(tree2);
3268
3581
  if (!tree2)
3269
3582
    return(tree1);
3270
 
  if (tree1->type == optimizer::SEL_TREE::IMPOSSIBLE || tree2->type == optimizer::SEL_TREE::ALWAYS)
 
3583
  if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
3271
3584
    return(tree1);
3272
 
  if (tree2->type == optimizer::SEL_TREE::IMPOSSIBLE || tree1->type == optimizer::SEL_TREE::ALWAYS)
 
3585
  if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
3273
3586
    return(tree2);
3274
 
  if (tree1->type == optimizer::SEL_TREE::MAYBE)
 
3587
  if (tree1->type == SEL_TREE::MAYBE)
3275
3588
  {
3276
 
    if (tree2->type == optimizer::SEL_TREE::KEY)
3277
 
      tree2->type=optimizer::SEL_TREE::KEY_SMALLER;
 
3589
    if (tree2->type == SEL_TREE::KEY)
 
3590
      tree2->type=SEL_TREE::KEY_SMALLER;
3278
3591
    return(tree2);
3279
3592
  }
3280
 
  if (tree2->type == optimizer::SEL_TREE::MAYBE)
 
3593
  if (tree2->type == SEL_TREE::MAYBE)
3281
3594
  {
3282
 
    tree1->type=optimizer::SEL_TREE::KEY_SMALLER;
 
3595
    tree1->type=SEL_TREE::KEY_SMALLER;
3283
3596
    return(tree1);
3284
3597
  }
3285
3598
  key_map  result_keys;
3300
3613
      *key1=key_and(param, *key1, *key2, flag);
3301
3614
      if (*key1 && (*key1)->type == optimizer::SEL_ARG::IMPOSSIBLE)
3302
3615
      {
3303
 
        tree1->type= optimizer::SEL_TREE::IMPOSSIBLE;
 
3616
        tree1->type= SEL_TREE::IMPOSSIBLE;
3304
3617
        return(tree1);
3305
3618
      }
3306
3619
      result_keys.set(key1 - tree1->keys);
3320
3633
}
3321
3634
 
3322
3635
 
 
3636
/*
 
3637
  Check if two SEL_TREES can be combined into one (i.e. a single key range
 
3638
  read can be constructed for "cond_of_tree1 OR cond_of_tree2" ) without
 
3639
  using index_merge.
 
3640
*/
 
3641
 
 
3642
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2,
 
3643
                           optimizer::RangeParameter* param)
 
3644
{
 
3645
  key_map common_keys= tree1->keys_map;
 
3646
  common_keys&= tree2->keys_map;
 
3647
 
 
3648
  if (common_keys.none())
 
3649
    return false;
 
3650
 
 
3651
  /* trees have a common key, check if they refer to same key part */
 
3652
  optimizer::SEL_ARG **key1,**key2;
 
3653
  for (uint32_t key_no=0; key_no < param->keys; key_no++)
 
3654
  {
 
3655
    if (common_keys.test(key_no))
 
3656
    {
 
3657
      key1= tree1->keys + key_no;
 
3658
      key2= tree2->keys + key_no;
 
3659
      if ((*key1)->part == (*key2)->part)
 
3660
      {
 
3661
        return true;
 
3662
      }
 
3663
    }
 
3664
  }
 
3665
  return false;
 
3666
}
 
3667
 
 
3668
 
 
3669
/*
 
3670
  Remove the trees that are not suitable for record retrieval.
 
3671
  SYNOPSIS
 
3672
    param  Range analysis parameter
 
3673
    tree   Tree to be processed, tree->type is KEY or KEY_SMALLER
 
3674
 
 
3675
  DESCRIPTION
 
3676
    This function walks through tree->keys[] and removes the SEL_ARG* trees
 
3677
    that are not "maybe" trees (*) and cannot be used to construct quick range
 
3678
    selects.
 
3679
    (*) - have type MAYBE or MAYBE_KEY. Perhaps we should remove trees of
 
3680
          these types here as well.
 
3681
 
 
3682
    A SEL_ARG* tree cannot be used to construct quick select if it has
 
3683
    tree->part != 0. (e.g. it could represent "keypart2 < const").
 
3684
 
 
3685
    WHY THIS FUNCTION IS NEEDED
 
3686
 
 
3687
    Normally we allow construction of SEL_TREE objects that have SEL_ARG
 
3688
    trees that do not allow quick range select construction. For example for
 
3689
    " keypart1=1 AND keypart2=2 " the execution will proceed as follows:
 
3690
    tree1= SEL_TREE { SEL_ARG{keypart1=1} }
 
3691
    tree2= SEL_TREE { SEL_ARG{keypart2=2} } -- can't make quick range select
 
3692
                                               from this
 
3693
    call tree_and(tree1, tree2) -- this joins SEL_ARGs into a usable SEL_ARG
 
3694
                                   tree.
 
3695
 
 
3696
    There is an exception though: when we construct index_merge SEL_TREE,
 
3697
    any SEL_ARG* tree that cannot be used to construct quick range select can
 
3698
    be removed, because current range analysis code doesn't provide any way
 
3699
    that tree could be later combined with another tree.
 
3700
    Consider an example: we should not construct
 
3701
    st1 = SEL_TREE {
 
3702
      merges = SEL_IMERGE {
 
3703
                            SEL_TREE(t.key1part1 = 1),
 
3704
                            SEL_TREE(t.key2part2 = 2)   -- (*)
 
3705
                          }
 
3706
                   };
 
3707
    because
 
3708
     - (*) cannot be used to construct quick range select,
 
3709
     - There is no execution path that would cause (*) to be converted to
 
3710
       a tree that could be used.
 
3711
 
 
3712
    The latter is easy to verify: first, notice that the only way to convert
 
3713
    (*) into a usable tree is to call tree_and(something, (*)).
 
3714
 
 
3715
    Second look at what tree_and/tree_or function would do when passed a
 
3716
    SEL_TREE that has the structure like st1 tree has, and conlcude that
 
3717
    tree_and(something, (*)) will not be called.
 
3718
 
 
3719
  RETURN
 
3720
    0  Ok, some suitable trees left
 
3721
    1  No tree->keys[] left.
 
3722
*/
 
3723
 
 
3724
static bool remove_nonrange_trees(optimizer::RangeParameter *param, SEL_TREE *tree)
 
3725
{
 
3726
  bool res= false;
 
3727
  for (uint32_t i=0; i < param->keys; i++)
 
3728
  {
 
3729
    if (tree->keys[i])
 
3730
    {
 
3731
      if (tree->keys[i]->part)
 
3732
      {
 
3733
        tree->keys[i]= NULL;
 
3734
        tree->keys_map.reset(i);
 
3735
      }
 
3736
      else
 
3737
        res= true;
 
3738
    }
 
3739
  }
 
3740
  return !res;
 
3741
}
 
3742
 
 
3743
 
 
3744
static SEL_TREE *
 
3745
tree_or(optimizer::RangeParameter *param,SEL_TREE *tree1,SEL_TREE *tree2)
 
3746
{
 
3747
  if (!tree1 || !tree2)
 
3748
    return 0;
 
3749
  if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
 
3750
    return(tree2);
 
3751
  if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
 
3752
    return(tree1);
 
3753
  if (tree1->type == SEL_TREE::MAYBE)
 
3754
    return(tree1);                              // Can't use this
 
3755
  if (tree2->type == SEL_TREE::MAYBE)
 
3756
    return(tree2);
 
3757
 
 
3758
  SEL_TREE *result= 0;
 
3759
  key_map  result_keys;
 
3760
  result_keys.reset();
 
3761
  if (sel_trees_can_be_ored(tree1, tree2, param))
 
3762
  {
 
3763
    /* Join the trees key per key */
 
3764
    optimizer::SEL_ARG **key1,**key2,**end;
 
3765
    for (key1= tree1->keys,key2= tree2->keys,end= key1+param->keys ;
 
3766
         key1 != end ; key1++,key2++)
 
3767
    {
 
3768
      *key1=key_or(param, *key1, *key2);
 
3769
      if (*key1)
 
3770
      {
 
3771
        result=tree1;                           // Added to tree1
 
3772
        result_keys.set(key1 - tree1->keys);
 
3773
      }
 
3774
    }
 
3775
    if (result)
 
3776
      result->keys_map= result_keys;
 
3777
  }
 
3778
  else
 
3779
  {
 
3780
    /* ok, two trees have KEY type but cannot be used without index merge */
 
3781
    if (tree1->merges.is_empty() && tree2->merges.is_empty())
 
3782
    {
 
3783
      if (param->remove_jump_scans)
 
3784
      {
 
3785
        bool no_trees= remove_nonrange_trees(param, tree1);
 
3786
        no_trees= no_trees || remove_nonrange_trees(param, tree2);
 
3787
        if (no_trees)
 
3788
          return(new SEL_TREE(SEL_TREE::ALWAYS));
 
3789
      }
 
3790
      SEL_IMERGE *merge;
 
3791
      /* both trees are "range" trees, produce new index merge structure */
 
3792
      if (!(result= new SEL_TREE()) || !(merge= new SEL_IMERGE()) ||
 
3793
          (result->merges.push_back(merge)) ||
 
3794
          (merge->or_sel_tree(param, tree1)) ||
 
3795
          (merge->or_sel_tree(param, tree2)))
 
3796
        result= NULL;
 
3797
      else
 
3798
        result->type= tree1->type;
 
3799
    }
 
3800
    else if (!tree1->merges.is_empty() && !tree2->merges.is_empty())
 
3801
    {
 
3802
      if (imerge_list_or_list(param, &tree1->merges, &tree2->merges))
 
3803
        result= new SEL_TREE(SEL_TREE::ALWAYS);
 
3804
      else
 
3805
        result= tree1;
 
3806
    }
 
3807
    else
 
3808
    {
 
3809
      /* one tree is index merge tree and another is range tree */
 
3810
      if (tree1->merges.is_empty())
 
3811
        std::swap(tree1, tree2);
 
3812
 
 
3813
      if (param->remove_jump_scans && remove_nonrange_trees(param, tree2))
 
3814
         return(new SEL_TREE(SEL_TREE::ALWAYS));
 
3815
      /* add tree2 to tree1->merges, checking if it collapses to ALWAYS */
 
3816
      if (imerge_list_or_tree(param, &tree1->merges, tree2))
 
3817
        result= new SEL_TREE(SEL_TREE::ALWAYS);
 
3818
      else
 
3819
        result= tree1;
 
3820
    }
 
3821
  }
 
3822
  return result;
 
3823
}
 
3824
 
3323
3825
 
3324
3826
/* And key trees where key1->part < key2 -> part */
3325
3827
 
3516
4018
}
3517
4019
 
3518
4020
 
 
4021
static optimizer::SEL_ARG *
 
4022
key_or(optimizer::RangeParameter *param, optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2)
 
4023
{
 
4024
  if (! key1)
 
4025
  {
 
4026
    if (key2)
 
4027
    {
 
4028
      key2->use_count--;
 
4029
      key2->free_tree();
 
4030
    }
 
4031
    return 0;
 
4032
  }
 
4033
  if (! key2)
 
4034
  {
 
4035
    key1->use_count--;
 
4036
    key1->free_tree();
 
4037
    return 0;
 
4038
  }
 
4039
  key1->use_count--;
 
4040
  key2->use_count--;
 
4041
 
 
4042
  if (key1->part != key2->part)
 
4043
  {
 
4044
    key1->free_tree();
 
4045
    key2->free_tree();
 
4046
    return 0;                                   // Can't optimize this
 
4047
  }
 
4048
 
 
4049
  // If one of the key is MAYBE_KEY then the found region may be bigger
 
4050
  if (key1->type == optimizer::SEL_ARG::MAYBE_KEY)
 
4051
  {
 
4052
    key2->free_tree();
 
4053
    key1->use_count++;
 
4054
    return key1;
 
4055
  }
 
4056
  if (key2->type == optimizer::SEL_ARG::MAYBE_KEY)
 
4057
  {
 
4058
    key1->free_tree();
 
4059
    key2->use_count++;
 
4060
    return key2;
 
4061
  }
 
4062
 
 
4063
  if (key1->use_count > 0)
 
4064
  {
 
4065
    if (key2->use_count == 0 || key1->elements > key2->elements)
 
4066
    {
 
4067
      std::swap(key1,key2);
 
4068
    }
 
4069
    if (key1->use_count > 0 || !(key1=key1->clone_tree(param)))
 
4070
      return 0;                                 // OOM
 
4071
  }
 
4072
 
 
4073
  // Add tree at key2 to tree at key1
 
4074
  bool key2_shared= key2->use_count != 0;
 
4075
  key1->maybe_flag|= key2->maybe_flag;
 
4076
 
 
4077
  for (key2=key2->first(); key2; )
 
4078
  {
 
4079
    optimizer::SEL_ARG *tmp= key1->find_range(key2); // Find key1.min <= key2.min
 
4080
    int cmp;
 
4081
 
 
4082
    if (! tmp)
 
4083
    {
 
4084
      tmp=key1->first(); // tmp.min > key2.min
 
4085
      cmp= -1;
 
4086
    }
 
4087
    else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
 
4088
    {                                           // Found tmp.max < key2.min
 
4089
      optimizer::SEL_ARG *next= tmp->next;
 
4090
      if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part))
 
4091
      {
 
4092
        // Join near ranges like tmp.max < 0 and key2.min >= 0
 
4093
        optimizer::SEL_ARG *key2_next=key2->next;
 
4094
        if (key2_shared)
 
4095
        {
 
4096
          if (! (key2=new optimizer::SEL_ARG(*key2)))
 
4097
            return 0;           // out of memory
 
4098
          key2->increment_use_count(key1->use_count+1);
 
4099
          key2->next= key2_next; // New copy of key2
 
4100
        }
 
4101
        key2->copy_min(tmp);
 
4102
        if (! (key1=key1->tree_delete(tmp)))
 
4103
        {                                       // Only one key in tree
 
4104
          key1= key2;
 
4105
          key1->make_root();
 
4106
          key2= key2_next;
 
4107
          break;
 
4108
        }
 
4109
      }
 
4110
      if (! (tmp= next)) // tmp.min > key2.min
 
4111
        break; // Copy rest of key2
 
4112
    }
 
4113
    if (cmp < 0)
 
4114
    {                                           // tmp.min > key2.min
 
4115
      int tmp_cmp;
 
4116
      if ((tmp_cmp= tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max
 
4117
      {
 
4118
        if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
 
4119
        {                                       // ranges are connected
 
4120
          tmp->copy_min_to_min(key2);
 
4121
          key1->merge_flags(key2);
 
4122
          if (tmp->min_flag & NO_MIN_RANGE &&
 
4123
              tmp->max_flag & NO_MAX_RANGE)
 
4124
          {
 
4125
            if (key1->maybe_flag)
 
4126
              return new optimizer::SEL_ARG(optimizer::SEL_ARG::MAYBE_KEY);
 
4127
            return 0;
 
4128
          }
 
4129
          key2->increment_use_count(-1);        // Free not used tree
 
4130
          key2= key2->next;
 
4131
          continue;
 
4132
        }
 
4133
        else
 
4134
        {
 
4135
          optimizer::SEL_ARG *next= key2->next; // Keys are not overlapping
 
4136
          if (key2_shared)
 
4137
          {
 
4138
            optimizer::SEL_ARG *cpy= new optimizer::SEL_ARG(*key2); // Must make copy
 
4139
            if (! cpy)
 
4140
              return 0; // OOM
 
4141
            key1= key1->insert(cpy);
 
4142
            key2->increment_use_count(key1->use_count+1);
 
4143
          }
 
4144
          else
 
4145
            key1= key1->insert(key2);           // Will destroy key2_root
 
4146
          key2= next;
 
4147
          continue;
 
4148
        }
 
4149
      }
 
4150
    }
 
4151
 
 
4152
    // tmp.max >= key2.min && tmp.min <= key.cmax(overlapping ranges)
 
4153
    if (eq_tree(tmp->next_key_part,key2->next_key_part))
 
4154
    {
 
4155
      if (tmp->is_same(key2))
 
4156
      {
 
4157
        tmp->merge_flags(key2);                 // Copy maybe flags
 
4158
        key2->increment_use_count(-1);          // Free not used tree
 
4159
      }
 
4160
      else
 
4161
      {
 
4162
        optimizer::SEL_ARG *last= tmp;
 
4163
        while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
 
4164
               eq_tree(last->next->next_key_part,key2->next_key_part))
 
4165
        {
 
4166
          optimizer::SEL_ARG *save= last;
 
4167
          last= last->next;
 
4168
          key1= key1->tree_delete(save);
 
4169
        }
 
4170
        last->copy_min(tmp);
 
4171
        if (last->copy_min(key2) || last->copy_max(key2))
 
4172
        {                                       // Full range
 
4173
          key1->free_tree();
 
4174
          for (; key2; key2= key2->next)
 
4175
            key2->increment_use_count(-1);      // Free not used tree
 
4176
          if (key1->maybe_flag)
 
4177
            return new optimizer::SEL_ARG(optimizer::SEL_ARG::MAYBE_KEY);
 
4178
          return 0;
 
4179
        }
 
4180
      }
 
4181
      key2= key2->next;
 
4182
      continue;
 
4183
    }
 
4184
 
 
4185
    if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
 
4186
    {                                           // tmp.min <= x < key2.min
 
4187
      optimizer::SEL_ARG *new_arg= tmp->clone_first(key2);
 
4188
      if (! new_arg)
 
4189
        return 0;                               // OOM
 
4190
      if ((new_arg->next_key_part= key1->next_key_part))
 
4191
        new_arg->increment_use_count(key1->use_count+1);
 
4192
      tmp->copy_min_to_min(key2);
 
4193
      key1= key1->insert(new_arg);
 
4194
    }
 
4195
 
 
4196
    // tmp.min >= key2.min && tmp.min <= key2.max
 
4197
    optimizer::SEL_ARG key(*key2); // Get copy we can modify
 
4198
    for (;;)
 
4199
    {
 
4200
      if (tmp->cmp_min_to_min(&key) > 0)
 
4201
      {                                         // key.min <= x < tmp.min
 
4202
        optimizer::SEL_ARG *new_arg= key.clone_first(tmp);
 
4203
        if (! new_arg)
 
4204
          return 0;                             // OOM
 
4205
        if ((new_arg->next_key_part=key.next_key_part))
 
4206
          new_arg->increment_use_count(key1->use_count+1);
 
4207
        key1= key1->insert(new_arg);
 
4208
      }
 
4209
      if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
 
4210
      {                                         // tmp.min. <= x <= tmp.max
 
4211
        tmp->maybe_flag|= key.maybe_flag;
 
4212
        key.increment_use_count(key1->use_count+1);
 
4213
        tmp->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
 
4214
        if (! cmp)                              // Key2 is ready
 
4215
          break;
 
4216
        key.copy_max_to_min(tmp);
 
4217
        if (! (tmp= tmp->next))
 
4218
        {
 
4219
          optimizer::SEL_ARG *tmp2= new optimizer::SEL_ARG(key);
 
4220
          if (! tmp2)
 
4221
            return 0;                           // OOM
 
4222
          key1= key1->insert(tmp2);
 
4223
          key2= key2->next;
 
4224
          goto end;
 
4225
        }
 
4226
        if (tmp->cmp_min_to_max(&key) > 0)
 
4227
        {
 
4228
          optimizer::SEL_ARG *tmp2= new optimizer::SEL_ARG(key);
 
4229
          if (! tmp2)
 
4230
            return 0;                           // OOM
 
4231
          key1= key1->insert(tmp2);
 
4232
          break;
 
4233
        }
 
4234
      }
 
4235
      else
 
4236
      {
 
4237
        optimizer::SEL_ARG *new_arg= tmp->clone_last(&key); // tmp.min <= x <= key.max
 
4238
        if (! new_arg)
 
4239
          return 0;                             // OOM
 
4240
        tmp->copy_max_to_min(&key);
 
4241
        tmp->increment_use_count(key1->use_count+1);
 
4242
        /* Increment key count as it may be used for next loop */
 
4243
        key.increment_use_count(1);
 
4244
        new_arg->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
 
4245
        key1= key1->insert(new_arg);
 
4246
        break;
 
4247
      }
 
4248
    }
 
4249
    key2= key2->next;
 
4250
  }
 
4251
 
 
4252
end:
 
4253
  while (key2)
 
4254
  {
 
4255
    optimizer::SEL_ARG *next= key2->next;
 
4256
    if (key2_shared)
 
4257
    {
 
4258
      optimizer::SEL_ARG *tmp= new optimizer::SEL_ARG(*key2);           // Must make copy
 
4259
      if (! tmp)
 
4260
        return 0;
 
4261
      key2->increment_use_count(key1->use_count+1);
 
4262
      key1= key1->insert(tmp);
 
4263
    }
 
4264
    else
 
4265
      key1= key1->insert(key2);                 // Will destroy key2_root
 
4266
    key2= next;
 
4267
  }
 
4268
  key1->use_count++;
 
4269
  return key1;
 
4270
}
 
4271
 
 
4272
 
 
4273
/* Compare if two trees are equal */
 
4274
static bool eq_tree(optimizer::SEL_ARG *a, optimizer::SEL_ARG *b)
 
4275
{
 
4276
  if (a == b)
 
4277
  {
 
4278
    return true;
 
4279
  }
 
4280
 
 
4281
  if (! a || ! b || ! a->is_same(b))
 
4282
  {
 
4283
    return false;
 
4284
  }
 
4285
 
 
4286
  if (a->left != &optimizer::null_element && b->left != &optimizer::null_element)
 
4287
  {
 
4288
    if (! eq_tree(a->left,b->left))
 
4289
      return false;
 
4290
  }
 
4291
  else if (a->left != &optimizer::null_element || b->left != &optimizer::null_element)
 
4292
  {
 
4293
    return false;
 
4294
  }
 
4295
 
 
4296
  if (a->right != &optimizer::null_element && b->right != &optimizer::null_element)
 
4297
  {
 
4298
    if (! eq_tree(a->right,b->right))
 
4299
      return false;
 
4300
  }
 
4301
  else if (a->right != &optimizer::null_element || b->right != &optimizer::null_element)
 
4302
  {
 
4303
    return false;
 
4304
  }
 
4305
 
 
4306
  if (a->next_key_part != b->next_key_part)
 
4307
  {                                             // Sub range
 
4308
    if (! a->next_key_part != ! b->next_key_part ||
 
4309
              ! eq_tree(a->next_key_part, b->next_key_part))
 
4310
      return false;
 
4311
  }
 
4312
 
 
4313
  return true;
 
4314
}
 
4315
 
 
4316
 
3519
4317
/****************************************************************************
3520
4318
  MRR Range Sequence Interface implementation that walks a SEL_ARG* tree.
3521
4319
 ****************************************************************************/
3546
4344
*/
3547
4345
typedef struct st_sel_arg_range_seq
3548
4346
{
3549
 
  uint32_t keyno;      /* index of used tree in optimizer::SEL_TREE structure */
 
4347
  uint32_t keyno;      /* index of used tree in SEL_TREE structure */
3550
4348
  uint32_t real_keyno; /* Number of the index in tables */
3551
4349
  optimizer::Parameter *param;
3552
4350
  optimizer::SEL_ARG *start; /* Root node of the traversed SEL_ARG* graph */
3734
4532
  /* Ok got a tuple */
3735
4533
  RANGE_SEQ_ENTRY *cur= &seq->stack[seq->i];
3736
4534
 
3737
 
  range->ptr= (char*)(size_t)(key_tree->part);
 
4535
  range->ptr= (char*)(int)(key_tree->part);
3738
4536
  {
3739
4537
    range->range_flag= cur->min_key_flag | cur->max_key_flag;
3740
4538
 
3788
4586
  SYNOPSIS
3789
4587
    check_quick_select()
3790
4588
      param             Parameter from test_quick_select
3791
 
      idx               Number of index to use in Parameter::key optimizer::SEL_TREE::key
 
4589
      idx               Number of index to use in Parameter::key SEL_TREE::key
3792
4590
      index_only        true  - assume only index tuples will be accessed
3793
4591
                        false - assume full table rows will be read
3794
4592
      tree              Transformed selection condition, tree->key[idx] holds
3810
4608
*/
3811
4609
 
3812
4610
static
3813
 
ha_rows check_quick_select(Session *session,
3814
 
                           optimizer::Parameter *param,
 
4611
ha_rows check_quick_select(optimizer::Parameter *param,
3815
4612
                           uint32_t idx,
3816
4613
                           bool index_only,
3817
4614
                           optimizer::SEL_ARG *tree,
3818
4615
                           bool update_tbl_stats,
3819
4616
                           uint32_t *mrr_flags,
3820
4617
                           uint32_t *bufsize,
3821
 
                           optimizer::CostVector *cost)
 
4618
                           COST_VECT *cost)
3822
4619
{
3823
4620
  SEL_ARG_RANGE_SEQ seq;
3824
4621
  RANGE_SEQ_IF seq_if = {sel_arg_range_seq_init, sel_arg_range_seq_next};
3852
4649
  bool pk_is_clustered= cursor->primary_key_is_clustered();
3853
4650
  if (index_only &&
3854
4651
      (param->table->index_flags(keynr) & HA_KEYREAD_ONLY) &&
3855
 
      !(pk_is_clustered && keynr == param->table->getShare()->getPrimaryKey()))
 
4652
      !(pk_is_clustered && keynr == param->table->s->primary_key))
3856
4653
     *mrr_flags |= HA_MRR_INDEX_ONLY;
3857
4654
 
3858
 
  if (session->lex->sql_command != SQLCOM_SELECT)
 
4655
  if (current_session->lex->sql_command != SQLCOM_SELECT)
3859
4656
    *mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
3860
4657
 
3861
4658
  *bufsize= param->session->variables.read_rnd_buff_size;
3887
4684
  else
3888
4685
  {
3889
4686
    /* Clustered PK scan is always a ROR scan (TODO: same as above) */
3890
 
    if (param->table->getShare()->getPrimaryKey() == keynr && pk_is_clustered)
 
4687
    if (param->table->s->primary_key == keynr && pk_is_clustered)
3891
4688
      param->is_ror_scan= true;
3892
4689
  }
3893
4690
 
3934
4731
 
3935
4732
static bool is_key_scan_ror(optimizer::Parameter *param, uint32_t keynr, uint8_t nparts)
3936
4733
{
3937
 
  KeyInfo *table_key= param->table->key_info + keynr;
3938
 
  KeyPartInfo *key_part= table_key->key_part + nparts;
3939
 
  KeyPartInfo *key_part_end= (table_key->key_part +
 
4734
  KEY *table_key= param->table->key_info + keynr;
 
4735
  KEY_PART_INFO *key_part= table_key->key_part + nparts;
 
4736
  KEY_PART_INFO *key_part_end= (table_key->key_part +
3940
4737
                                table_key->key_parts);
3941
4738
  uint32_t pk_number;
3942
4739
 
3943
 
  for (KeyPartInfo *kp= table_key->key_part; kp < key_part; kp++)
 
4740
  for (KEY_PART_INFO *kp= table_key->key_part; kp < key_part; kp++)
3944
4741
  {
3945
4742
    uint16_t fieldnr= param->table->key_info[keynr].
3946
4743
                    key_part[kp - table_key->key_part].fieldnr - 1;
3947
 
    if (param->table->getField(fieldnr)->key_length() != kp->length)
 
4744
    if (param->table->field[fieldnr]->key_length() != kp->length)
3948
4745
      return false;
3949
4746
  }
3950
4747
 
3952
4749
    return true;
3953
4750
 
3954
4751
  key_part= table_key->key_part + nparts;
3955
 
  pk_number= param->table->getShare()->getPrimaryKey();
 
4752
  pk_number= param->table->s->primary_key;
3956
4753
  if (!param->table->cursor->primary_key_is_clustered() || pk_number == MAX_KEY)
3957
4754
    return false;
3958
4755
 
3959
 
  KeyPartInfo *pk_part= param->table->key_info[pk_number].key_part;
3960
 
  KeyPartInfo *pk_part_end= pk_part +
 
4756
  KEY_PART_INFO *pk_part= param->table->key_info[pk_number].key_part;
 
4757
  KEY_PART_INFO *pk_part_end= pk_part +
3961
4758
                              param->table->key_info[pk_number].key_parts;
3962
4759
  for (;(key_part!=key_part_end) && (pk_part != pk_part_end);
3963
4760
       ++key_part, ++pk_part)
3978
4775
                            uint32_t mrr_buf_size,
3979
4776
                            memory::Root *parent_alloc)
3980
4777
{
3981
 
  optimizer::QuickRangeSelect *quick= new optimizer::QuickRangeSelect(param->session,
3982
 
                                                                      param->table,
3983
 
                                                                      param->real_keynr[idx],
3984
 
                                                                      test(parent_alloc),
3985
 
                                                                      NULL);
 
4778
  optimizer::QuickRangeSelect *quick= NULL;
 
4779
  bool create_err= false;
 
4780
 
 
4781
  quick= new optimizer::QuickRangeSelect(param->session,
 
4782
                                         param->table,
 
4783
                                         param->real_keynr[idx],
 
4784
                                         test(parent_alloc),
 
4785
                                         NULL,
 
4786
                                         &create_err);
3986
4787
 
3987
4788
  if (quick)
3988
4789
  {
3989
 
          if (get_quick_keys(param,
 
4790
    if (create_err ||
 
4791
              get_quick_keys(param,
3990
4792
                       quick,
3991
4793
                       param->key[idx],
3992
4794
                       key_tree,
4002
4804
    {
4003
4805
      quick->mrr_flags= mrr_flags;
4004
4806
      quick->mrr_buf_size= mrr_buf_size;
4005
 
      if (parent_alloc)
4006
 
      {
4007
 
        quick->key_parts=(KEY_PART*)
4008
 
          parent_alloc->memdup_root( (char*) param->key[idx], sizeof(KEY_PART)* param->table->key_info[param->real_keynr[idx]].key_parts);
4009
 
      }
4010
 
      else
4011
 
      {
4012
 
        quick->key_parts=(KEY_PART*)
4013
 
          quick->alloc.memdup_root((char*) param->key[idx], sizeof(KEY_PART)* param->table->key_info[param->real_keynr[idx]].key_parts);
4014
 
      }
 
4807
      quick->key_parts=(KEY_PART*)
 
4808
        memdup_root(parent_alloc? parent_alloc : &quick->alloc,
 
4809
                    (char*) param->key[idx],
 
4810
                    sizeof(KEY_PART)*
 
4811
                    param->table->key_info[param->real_keynr[idx]].key_parts);
4015
4812
    }
4016
4813
  }
4017
4814
  return quick;
4125
4922
    if (length == (uint32_t) (tmp_max_key - param->max_key) &&
4126
4923
              ! memcmp(param->min_key,param->max_key,length))
4127
4924
    {
4128
 
      KeyInfo *table_key= quick->head->key_info+quick->index;
 
4925
      KEY *table_key= quick->head->key_info+quick->index;
4129
4926
      flag= EQ_RANGE;
4130
4927
      if ((table_key->flags & (HA_NOSAME)) == HA_NOSAME &&
4131
4928
                key->part == table_key->key_parts-1)
4207
5004
}
4208
5005
 
4209
5006
 
4210
 
bool optimizer::QuickSelectInterface::is_keys_used(const boost::dynamic_bitset<>& fields)
 
5007
bool optimizer::QuickSelectInterface::is_keys_used(const MyBitmap *fields)
4211
5008
{
4212
5009
  return is_key_used(head, index, fields);
4213
5010
}
4237
5034
                                                                 table_reference_st *ref,
4238
5035
                                                                 ha_rows records)
4239
5036
{
4240
 
  memory::Root *old_root= NULL;
4241
 
  memory::Root *alloc= NULL;
4242
 
  KeyInfo *key_info = &table->key_info[ref->key];
 
5037
  memory::Root *old_root, *alloc;
 
5038
  optimizer::QuickRangeSelect *quick= NULL;
 
5039
  KEY *key_info = &table->key_info[ref->key];
4243
5040
  KEY_PART *key_part;
4244
5041
  optimizer::QuickRange *range= NULL;
4245
5042
  uint32_t part;
4246
 
  optimizer::CostVector cost;
 
5043
  bool create_err= false;
 
5044
  COST_VECT cost;
4247
5045
 
4248
5046
  old_root= session->mem_root;
4249
5047
  /* The following call may change session->mem_root */
4250
 
  optimizer::QuickRangeSelect *quick= new optimizer::QuickRangeSelect(session, table, ref->key, 0, 0);
 
5048
  quick= new optimizer::QuickRangeSelect(session, table, ref->key, 0, 0, &create_err);
4251
5049
  /* save mem_root set by QuickRangeSelect constructor */
4252
5050
  alloc= session->mem_root;
4253
5051
  /*
4256
5054
  */
4257
5055
  session->mem_root= old_root;
4258
5056
 
4259
 
  if (! quick)
 
5057
  if (!quick || create_err)
4260
5058
    return 0;                   /* no ranges found */
4261
5059
  if (quick->init())
4262
5060
    goto err;
4275
5073
 
4276
5074
 
4277
5075
  if (!(quick->key_parts=key_part=(KEY_PART *)
4278
 
        quick->alloc.alloc_root(sizeof(KEY_PART)*ref->key_parts)))
 
5076
        alloc_root(&quick->alloc,sizeof(KEY_PART)*ref->key_parts)))
4279
5077
    goto err;
4280
5078
 
4281
5079
  for (part=0 ; part < ref->key_parts ;part++,key_part++)
4320
5118
 
4321
5119
  quick->mrr_buf_size= session->variables.read_rnd_buff_size;
4322
5120
  if (table->cursor->multi_range_read_info(quick->index, 1, (uint32_t)records,
4323
 
                                           &quick->mrr_buf_size,
4324
 
                                           &quick->mrr_flags, &cost))
 
5121
                                         &quick->mrr_buf_size,
 
5122
                                         &quick->mrr_flags, &cost))
4325
5123
    goto err;
4326
5124
 
4327
5125
  return quick;
4399
5197
}
4400
5198
 
4401
5199
 
4402
 
static inline uint32_t get_field_keypart(KeyInfo *index, Field *field);
 
5200
static inline uint32_t get_field_keypart(KEY *index, Field *field);
4403
5201
 
4404
5202
static inline optimizer::SEL_ARG * get_index_range_tree(uint32_t index,
4405
 
                                                        optimizer::SEL_TREE *range_tree,
 
5203
                                                        SEL_TREE *range_tree,
4406
5204
                                                        optimizer::Parameter *param,
4407
5205
                                                        uint32_t *param_idx);
4408
5206
 
4409
 
static bool get_constant_key_infix(KeyInfo *index_info,
 
5207
static bool get_constant_key_infix(KEY *index_info,
4410
5208
                                   optimizer::SEL_ARG *index_range_tree,
4411
 
                                   KeyPartInfo *first_non_group_part,
4412
 
                                   KeyPartInfo *min_max_arg_part,
4413
 
                                   KeyPartInfo *last_part,
 
5209
                                   KEY_PART_INFO *first_non_group_part,
 
5210
                                   KEY_PART_INFO *min_max_arg_part,
 
5211
                                   KEY_PART_INFO *last_part,
4414
5212
                                   Session *session,
4415
5213
                                   unsigned char *key_infix,
4416
5214
                                   uint32_t *key_infix_len,
4417
 
                                   KeyPartInfo **first_non_infix_part);
 
5215
                                   KEY_PART_INFO **first_non_infix_part);
4418
5216
 
4419
5217
static bool check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item);
4420
5218
 
4421
5219
static void
4422
5220
cost_group_min_max(Table* table,
4423
 
                   KeyInfo *index_info,
 
5221
                   KEY *index_info,
4424
5222
                   uint32_t used_key_parts,
4425
5223
                   uint32_t group_key_parts,
4426
 
                   optimizer::SEL_TREE *range_tree,
 
5224
                   SEL_TREE *range_tree,
4427
5225
                   optimizer::SEL_ARG *index_tree,
4428
5226
                   ha_rows quick_prefix_records,
4429
5227
                   bool have_min,
4560
5358
    - NULL
4561
5359
*/
4562
5360
static optimizer::GroupMinMaxReadPlan *
4563
 
get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree)
 
5361
get_best_group_min_max(optimizer::Parameter *param, SEL_TREE *tree)
4564
5362
{
4565
5363
  Session *session= param->session;
4566
 
  Join *join= session->lex->current_select->join;
 
5364
  JOIN *join= session->lex->current_select->join;
4567
5365
  Table *table= param->table;
4568
5366
  bool have_min= false;              /* true if there is a MIN function. */
4569
5367
  bool have_max= false;              /* true if there is a MAX function. */
4570
5368
  Item_field *min_max_arg_item= NULL; // The argument of all MIN/MAX functions
4571
 
  KeyPartInfo *min_max_arg_part= NULL; /* The corresponding keypart. */
 
5369
  KEY_PART_INFO *min_max_arg_part= NULL; /* The corresponding keypart. */
4572
5370
  uint32_t group_prefix_len= 0; /* Length (in bytes) of the key prefix. */
4573
 
  KeyInfo *index_info= NULL;    /* The index chosen for data access. */
 
5371
  KEY *index_info= NULL;    /* The index chosen for data access. */
4574
5372
  uint32_t index= 0;            /* The id of the chosen index. */
4575
5373
  uint32_t group_key_parts= 0;  // Number of index key parts in the group prefix.
4576
5374
  uint32_t used_key_parts= 0;   /* Number of index key parts used for access. */
4578
5376
  uint32_t key_infix_len= 0;          /* Length of key_infix. */
4579
5377
  optimizer::GroupMinMaxReadPlan *read_plan= NULL; /* The eventually constructed TRP. */
4580
5378
  uint32_t key_part_nr;
4581
 
  Order *tmp_group= NULL;
 
5379
  order_st *tmp_group= NULL;
4582
5380
  Item *item= NULL;
4583
5381
  Item_field *item_field= NULL;
4584
5382
 
4591
5389
       (! join->select_distinct)) ||
4592
5390
      (join->select_lex->olap == ROLLUP_TYPE)) /* Check (B3) for ROLLUP */
4593
5391
    return NULL;
4594
 
  if (table->getShare()->sizeKeys() == 0)        /* There are no indexes to use. */
 
5392
  if (table->s->keys == 0)        /* There are no indexes to use. */
4595
5393
    return NULL;
4596
5394
 
4597
5395
  /* Analyze the query in more detail. */
4650
5448
    (GA1,GA2) are all true. If there is more than one such index, select the
4651
5449
    first one. Here we set the variables: group_prefix_len and index_info.
4652
5450
  */
4653
 
  KeyInfo *cur_index_info= table->key_info;
4654
 
  KeyInfo *cur_index_info_end= cur_index_info + table->getShare()->sizeKeys();
4655
 
  KeyPartInfo *cur_part= NULL;
4656
 
  KeyPartInfo *end_part= NULL; /* Last part for loops. */
 
5451
  KEY *cur_index_info= table->key_info;
 
5452
  KEY *cur_index_info_end= cur_index_info + table->s->keys;
 
5453
  KEY_PART_INFO *cur_part= NULL;
 
5454
  KEY_PART_INFO *end_part= NULL; /* Last part for loops. */
4657
5455
  /* Last index part. */
4658
 
  KeyPartInfo *last_part= NULL;
4659
 
  KeyPartInfo *first_non_group_part= NULL;
4660
 
  KeyPartInfo *first_non_infix_part= NULL;
 
5456
  KEY_PART_INFO *last_part= NULL;
 
5457
  KEY_PART_INFO *first_non_group_part= NULL;
 
5458
  KEY_PART_INFO *first_non_infix_part= NULL;
4661
5459
  uint32_t key_infix_parts= 0;
4662
5460
  uint32_t cur_group_key_parts= 0;
4663
5461
  uint32_t cur_group_prefix_len= 0;
4676
5474
  uint32_t cur_key_infix_len= 0;
4677
5475
  unsigned char cur_key_infix[MAX_KEY_LENGTH];
4678
5476
  uint32_t cur_used_key_parts= 0;
4679
 
  uint32_t pk= param->table->getShare()->getPrimaryKey();
 
5477
  uint32_t pk= param->table->s->primary_key;
4680
5478
 
4681
5479
  for (uint32_t cur_index= 0;
4682
5480
       cur_index_info != cur_index_info_end;
4699
5497
        (table->cursor->getEngine()->check_flag(HTON_BIT_PRIMARY_KEY_IN_READ_INDEX)))
4700
5498
    {
4701
5499
      /* For each table field */
4702
 
      for (uint32_t i= 0; i < table->getShare()->sizeFields(); i++)
 
5500
      for (uint32_t i= 0; i < table->s->fields; i++)
4703
5501
      {
4704
 
        Field *cur_field= table->getField(i);
 
5502
        Field *cur_field= table->field[i];
4705
5503
        /*
4706
5504
          If the field is used in the current query ensure that it's
4707
5505
          part of 'cur_index'
4869
5667
          Store the first and last keyparts that need to be analyzed
4870
5668
          into one array that can be passed as parameter.
4871
5669
        */
4872
 
        KeyPartInfo *key_part_range[2];
 
5670
        KEY_PART_INFO *key_part_range[2];
4873
5671
        key_part_range[0]= first_non_group_part;
4874
5672
        key_part_range[1]= last_part;
4875
5673
 
4910
5708
                                           param,
4911
5709
                                           &cur_param_idx);
4912
5710
      /* Check if this range tree can be used for prefix retrieval. */
4913
 
      optimizer::CostVector dummy_cost;
 
5711
      COST_VECT dummy_cost;
4914
5712
      uint32_t mrr_flags= HA_MRR_USE_DEFAULT_IMPL;
4915
5713
      uint32_t mrr_bufsize= 0;
4916
 
      cur_quick_prefix_records= check_quick_select(session,
4917
 
                                                   param,
 
5714
      cur_quick_prefix_records= check_quick_select(param,
4918
5715
                                                   cur_param_idx,
4919
5716
                                                   false /*don't care*/,
4920
5717
                                                   cur_index_tree,
5162
5959
    false o/w
5163
5960
*/
5164
5961
static bool
5165
 
get_constant_key_infix(KeyInfo *,
 
5962
get_constant_key_infix(KEY *,
5166
5963
                       optimizer::SEL_ARG *index_range_tree,
5167
 
                       KeyPartInfo *first_non_group_part,
5168
 
                       KeyPartInfo *min_max_arg_part,
5169
 
                       KeyPartInfo *last_part,
 
5964
                       KEY_PART_INFO *first_non_group_part,
 
5965
                       KEY_PART_INFO *min_max_arg_part,
 
5966
                       KEY_PART_INFO *last_part,
5170
5967
                       Session *,
5171
5968
                       unsigned char *key_infix,
5172
5969
                       uint32_t *key_infix_len,
5173
 
                       KeyPartInfo **first_non_infix_part)
 
5970
                       KEY_PART_INFO **first_non_infix_part)
5174
5971
{
5175
5972
  optimizer::SEL_ARG *cur_range= NULL;
5176
 
  KeyPartInfo *cur_part= NULL;
 
5973
  KEY_PART_INFO *cur_part= NULL;
5177
5974
  /* End part for the first loop below. */
5178
 
  KeyPartInfo *end_part= min_max_arg_part ? min_max_arg_part : last_part;
 
5975
  KEY_PART_INFO *end_part= min_max_arg_part ? min_max_arg_part : last_part;
5179
5976
 
5180
5977
  *key_infix_len= 0;
5181
5978
  unsigned char *key_ptr= key_infix;
5241
6038
    field  field that possibly references some key part in index
5242
6039
 
5243
6040
  NOTES
5244
 
    The return value can be used to get a KeyPartInfo pointer by
 
6041
    The return value can be used to get a KEY_PART_INFO pointer by
5245
6042
    part= index->key_part + get_field_keypart(...) - 1;
5246
6043
 
5247
6044
  RETURN
5249
6046
    0 if field does not reference any index field.
5250
6047
*/
5251
6048
static inline uint
5252
 
get_field_keypart(KeyInfo *index, Field *field)
 
6049
get_field_keypart(KEY *index, Field *field)
5253
6050
{
5254
 
  KeyPartInfo *part= NULL;
5255
 
  KeyPartInfo *end= NULL;
 
6051
  KEY_PART_INFO *part= NULL;
 
6052
  KEY_PART_INFO *end= NULL;
5256
6053
 
5257
6054
  for (part= index->key_part, end= part + index->key_parts; part < end; part++)
5258
6055
  {
5275
6072
 
5276
6073
  DESCRIPTION
5277
6074
 
5278
 
    A optimizer::SEL_TREE contains range trees for all usable indexes. This procedure
5279
 
    finds the SEL_ARG sub-tree for 'index'. The members of a optimizer::SEL_TREE are
 
6075
    A SEL_TREE contains range trees for all usable indexes. This procedure
 
6076
    finds the SEL_ARG sub-tree for 'index'. The members of a SEL_TREE are
5280
6077
    ordered in the same way as the members of Parameter::key, thus we first find
5281
6078
    the corresponding index in the array Parameter::key. This index is returned
5282
6079
    through the variable param_idx, to be used later as argument of
5286
6083
    Pointer to the SEL_ARG subtree that corresponds to index.
5287
6084
*/
5288
6085
optimizer::SEL_ARG *get_index_range_tree(uint32_t index,
5289
 
                                         optimizer::SEL_TREE* range_tree,
 
6086
                                         SEL_TREE* range_tree,
5290
6087
                                         optimizer::Parameter *param,
5291
6088
                                         uint32_t *param_idx)
5292
6089
{
5362
6159
    None
5363
6160
*/
5364
6161
void cost_group_min_max(Table* table,
5365
 
                        KeyInfo *index_info,
 
6162
                        KEY *index_info,
5366
6163
                        uint32_t used_key_parts,
5367
6164
                        uint32_t group_key_parts,
5368
 
                        optimizer::SEL_TREE *range_tree,
 
6165
                        SEL_TREE *range_tree,
5369
6166
                        optimizer::SEL_ARG *,
5370
6167
                        ha_rows quick_prefix_records,
5371
6168
                        bool have_min,
5567
6364
}
5568
6365
 
5569
6366
 
5570
 
uint32_t optimizer::RorScanInfo::findFirstNotSet() const
 
6367
static void print_sel_tree(optimizer::Parameter *param, SEL_TREE *tree, key_map *tree_map, const char *)
5571
6368
{
5572
 
  boost::dynamic_bitset<> map= bitsToBitset();
5573
 
  for (boost::dynamic_bitset<>::size_type i= 0; i < map.size(); i++)
 
6369
  optimizer::SEL_ARG **key= NULL;
 
6370
  optimizer::SEL_ARG **end= NULL;
 
6371
  int idx= 0;
 
6372
  char buff[1024];
 
6373
 
 
6374
  String tmp(buff,sizeof(buff),&my_charset_bin);
 
6375
  tmp.length(0);
 
6376
  for (idx= 0, key=tree->keys, end= key + param->keys;
 
6377
       key != end;
 
6378
       key++, idx++)
5574
6379
  {
5575
 
    if (! map.test(i))
 
6380
    if (tree_map->test(idx))
5576
6381
    {
5577
 
      return i;
 
6382
      uint32_t keynr= param->real_keynr[idx];
 
6383
      if (tmp.length())
 
6384
        tmp.append(',');
 
6385
      tmp.append(param->table->key_info[keynr].name);
5578
6386
    }
5579
6387
  }
5580
 
  return map.size();
5581
 
}
5582
 
 
5583
 
 
5584
 
size_t optimizer::RorScanInfo::getBitCount() const
5585
 
{
5586
 
  boost::dynamic_bitset<> tmp_bitset= bitsToBitset();
5587
 
  return tmp_bitset.count();
5588
 
}
5589
 
 
5590
 
 
5591
 
void optimizer::RorScanInfo::subtractBitset(const boost::dynamic_bitset<>& in_bitset)
5592
 
{
5593
 
  boost::dynamic_bitset<> tmp_bitset= bitsToBitset();
5594
 
  tmp_bitset-= in_bitset;
5595
 
  covered_fields= tmp_bitset.to_ulong();
5596
 
}
5597
 
 
5598
 
 
5599
 
boost::dynamic_bitset<> optimizer::RorScanInfo::bitsToBitset() const
5600
 
{
5601
 
  string res;
5602
 
  uint64_t conv= covered_fields;
5603
 
  while (conv)
5604
 
  {
5605
 
    res.push_back((conv & 1) + '0');
5606
 
    conv>>= 1;
5607
 
  }
5608
 
  if (! res.empty())
5609
 
  {
5610
 
    std::reverse(res.begin(), res.end());
5611
 
  }
5612
 
  string final(covered_fields_size - res.length(), '0');
5613
 
  final.append(res);
5614
 
  return (boost::dynamic_bitset<>(final));
5615
 
}
5616
 
 
 
6388
  if (! tmp.length())
 
6389
    tmp.append(STRING_WITH_LEN("(empty)"));
 
6390
}
 
6391
 
 
6392
 
 
6393
static void print_ror_scans_arr(Table *table,
 
6394
                                const char *,
 
6395
                                struct st_ror_scan_info **start,
 
6396
                                struct st_ror_scan_info **end)
 
6397
{
 
6398
  char buff[1024];
 
6399
  String tmp(buff,sizeof(buff),&my_charset_bin);
 
6400
  tmp.length(0);
 
6401
  for (; start != end; start++)
 
6402
  {
 
6403
    if (tmp.length())
 
6404
      tmp.append(',');
 
6405
    tmp.append(table->key_info[(*start)->keynr].name);
 
6406
  }
 
6407
  if (! tmp.length())
 
6408
    tmp.append(STRING_WITH_LEN("(empty)"));
 
6409
}
5617
6410
 
5618
6411
} /* namespace drizzled */