← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/optimizer/range.cc

Merge Stewart.

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/optimizer/range.cc
1
1
/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2
2
 *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
3
3
 *
4
 
 *  Copyright (C) 2008-2009 Sun Microsystems, Inc.
 
4
 *  Copyright (C) 2008-2009 Sun Microsystems
5
5
 *
6
6
 *  This program is free software; you can redistribute it and/or modify
7
7
 *  it under the terms of the GNU General Public License as published by
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
 
#include "drizzled/check_stack_overrun.h"
 
119
#include "drizzled/sql_base.h"
 
120
#include "drizzled/sql_select.h"
115
121
#include "drizzled/error.h"
 
122
#include "drizzled/cost_vect.h"
 
123
#include "drizzled/item/cmpfunc.h"
116
124
#include "drizzled/field/num.h"
117
 
#include "drizzled/internal/iocache.h"
118
 
#include "drizzled/internal/my_sys.h"
119
 
#include "drizzled/item/cmpfunc.h"
120
 
#include "drizzled/optimizer/cost_vector.h"
 
125
#include "drizzled/check_stack_overrun.h"
 
126
#include "drizzled/optimizer/sum.h"
 
127
#include "drizzled/optimizer/range.h"
 
128
#include "drizzled/optimizer/quick_range.h"
 
129
#include "drizzled/optimizer/quick_range_select.h"
121
130
#include "drizzled/optimizer/quick_group_min_max_select.h"
122
131
#include "drizzled/optimizer/quick_index_merge_select.h"
123
 
#include "drizzled/optimizer/quick_range.h"
124
 
#include "drizzled/optimizer/quick_range_select.h"
125
132
#include "drizzled/optimizer/quick_ror_intersect_select.h"
126
133
#include "drizzled/optimizer/quick_ror_union_select.h"
127
 
#include "drizzled/optimizer/range.h"
 
134
#include "drizzled/optimizer/table_read_plan.h"
 
135
#include "drizzled/optimizer/sel_arg.h"
128
136
#include "drizzled/optimizer/range_param.h"
129
 
#include "drizzled/optimizer/sel_arg.h"
130
 
#include "drizzled/optimizer/sel_imerge.h"
131
 
#include "drizzled/optimizer/sel_tree.h"
132
 
#include "drizzled/optimizer/sum.h"
133
 
#include "drizzled/optimizer/table_read_plan.h"
134
 
#include "drizzled/plugin/storage_engine.h"
135
137
#include "drizzled/records.h"
136
 
#include "drizzled/sql_base.h"
137
 
#include "drizzled/sql_select.h"
138
 
#include "drizzled/table_reference.h"
 
138
#include "drizzled/internal/my_sys.h"
 
139
#include "drizzled/internal/iocache.h"
139
140
 
140
141
#include "drizzled/temporal.h" /* Needed in get_mm_leaf() for timestamp -> datetime comparisons */
141
142
 
 
143
#include "drizzled/memory/multi_malloc.h"
 
144
 
142
145
using namespace std;
143
146
namespace drizzled
144
147
{
203
206
static void get_sweep_read_cost(Table *table,
204
207
                                ha_rows nrows,
205
208
                                bool interrupted,
206
 
                                optimizer::CostVector *cost)
 
209
                                COST_VECT *cost)
207
210
{
208
211
  cost->zero();
209
212
  if (table->cursor->primary_key_is_clustered())
210
213
  {
211
 
    cost->setIOCount(table->cursor->read_time(table->getShare()->getPrimaryKey(),
 
214
    cost->io_count= table->cursor->read_time(table->s->primary_key,
212
215
                                             static_cast<uint32_t>(nrows),
213
 
                                             nrows));
 
216
                                             nrows);
214
217
  }
215
218
  else
216
219
  {
221
224
    if (busy_blocks < 1.0)
222
225
      busy_blocks= 1.0;
223
226
 
224
 
    cost->setIOCount(busy_blocks);
 
227
    cost->io_count= busy_blocks;
225
228
 
226
229
    if (! interrupted)
227
230
    {
228
231
      /* Assume reading is done in one 'sweep' */
229
 
      cost->setAvgIOCost((DISK_SEEK_BASE_COST +
230
 
                          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);
231
234
    }
232
235
  }
233
236
}
234
237
 
235
 
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,
236
291
                               COND *cond_func,
237
292
                               Field *field,
238
293
                                                 Item_func::Functype type,
246
301
                                                         Item_func::Functype type,
247
302
                                       Item *value);
248
303
 
249
 
static optimizer::SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond);
 
304
static SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond);
250
305
 
251
306
static bool is_key_scan_ror(optimizer::Parameter *param, uint32_t keynr, uint8_t nparts);
252
307
 
253
 
static ha_rows check_quick_select(Session *session,
254
 
                                  optimizer::Parameter *param,
 
308
static ha_rows check_quick_select(optimizer::Parameter *param,
255
309
                                  uint32_t idx,
256
310
                                  bool index_only,
257
311
                                  optimizer::SEL_ARG *tree,
258
312
                                  bool update_tbl_stats,
259
313
                                  uint32_t *mrr_flags,
260
314
                                  uint32_t *bufsize,
261
 
                                  optimizer::CostVector *cost);
 
315
                                  COST_VECT *cost);
262
316
 
263
 
static optimizer::RangeReadPlan *get_key_scans_params(Session *session,
264
 
                                                      optimizer::Parameter *param,
265
 
                                                      optimizer::SEL_TREE *tree,
 
317
static optimizer::RangeReadPlan *get_key_scans_params(optimizer::Parameter *param,
 
318
                                                      SEL_TREE *tree,
266
319
                                                      bool index_read_must_be_used,
267
320
                                                      bool update_tbl_stats,
268
321
                                                      double read_time);
269
322
 
270
323
static
271
324
optimizer::RorIntersectReadPlan *get_best_ror_intersect(const optimizer::Parameter *param,
272
 
                                                        optimizer::SEL_TREE *tree,
 
325
                                                        SEL_TREE *tree,
273
326
                                                        double read_time,
274
327
                                                        bool *are_all_covering);
275
328
 
276
329
static
277
330
optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
278
 
                                                                 optimizer::SEL_TREE *tree,
 
331
                                                                 SEL_TREE *tree,
279
332
                                                                 double read_time);
280
333
 
281
334
static
282
 
optimizer::TableReadPlan *get_best_disjunct_quick(Session *session,
283
 
                                                  optimizer::Parameter *param,
284
 
                                                  optimizer::SEL_IMERGE *imerge,
 
335
optimizer::TableReadPlan *get_best_disjunct_quick(optimizer::Parameter *param,
 
336
                                                  SEL_IMERGE *imerge,
285
337
                                                  double read_time);
286
338
 
287
339
static
288
 
optimizer::GroupMinMaxReadPlan *get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree);
289
 
 
290
 
static optimizer::SEL_TREE *tree_and(optimizer::RangeParameter *param, 
291
 
                                     optimizer::SEL_TREE *tree1, 
292
 
                                     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
static void print_ror_scans_vector(Table *table,
 
352
                                   const char *msg,
 
353
                                   vector<struct st_ror_scan_info *> &vec);
 
354
 
 
355
static SEL_TREE *tree_and(optimizer::RangeParameter *param, SEL_TREE *tree1, SEL_TREE *tree2);
 
356
 
 
357
static SEL_TREE *tree_or(optimizer::RangeParameter *param, SEL_TREE *tree1, SEL_TREE *tree2);
293
358
 
294
359
static optimizer::SEL_ARG *sel_add(optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);
295
360
 
 
361
static optimizer::SEL_ARG *key_or(optimizer::RangeParameter *param, optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);
 
362
 
296
363
static optimizer::SEL_ARG *key_and(optimizer::RangeParameter *param,
297
364
                                   optimizer::SEL_ARG *key1,
298
365
                                   optimizer::SEL_ARG *key2,
300
367
 
301
368
static bool get_range(optimizer::SEL_ARG **e1, optimizer::SEL_ARG **e2, optimizer::SEL_ARG *root1);
302
369
 
 
370
static bool eq_tree(optimizer::SEL_ARG* a, optimizer::SEL_ARG *b);
 
371
 
303
372
optimizer::SEL_ARG optimizer::null_element(optimizer::SEL_ARG::IMPOSSIBLE);
304
373
 
305
374
static bool null_part_in_key(KEY_PART *key_part,
306
375
                             const unsigned char *key,
307
376
                             uint32_t length);
308
377
 
309
 
bool sel_trees_can_be_ored(optimizer::SEL_TREE *tree1, 
310
 
                           optimizer::SEL_TREE *tree2, 
311
 
                           optimizer::RangeParameter *param);
312
 
 
313
 
 
314
 
 
315
 
 
 
378
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, optimizer::RangeParameter *param);
 
379
 
 
380
 
 
381
/*
 
382
  SEL_IMERGE is a list of possible ways to do index merge, i.e. it is
 
383
  a condition in the following form:
 
384
   (t_1||t_2||...||t_N) && (next)
 
385
 
 
386
  where all t_i are SEL_TREEs, next is another SEL_IMERGE and no pair
 
387
  (t_i,t_j) contains SEL_ARGS for the same index.
 
388
 
 
389
  SEL_TREE contained in SEL_IMERGE always has merges=NULL.
 
390
 
 
391
  This class relies on memory manager to do the cleanup.
 
392
*/
 
393
 
 
394
class SEL_IMERGE : public memory::SqlAlloc
 
395
{
 
396
  enum { PREALLOCED_TREES= 10};
 
397
public:
 
398
  SEL_TREE *trees_prealloced[PREALLOCED_TREES];
 
399
  SEL_TREE **trees;             /* trees used to do index_merge   */
 
400
  SEL_TREE **trees_next;        /* last of these trees            */
 
401
  SEL_TREE **trees_end;         /* end of allocated space         */
 
402
 
 
403
  optimizer::SEL_ARG  ***best_keys;        /* best keys to read in SEL_TREEs */
 
404
 
 
405
  SEL_IMERGE() :
 
406
    trees(&trees_prealloced[0]),
 
407
    trees_next(trees),
 
408
    trees_end(trees + PREALLOCED_TREES)
 
409
  {}
 
410
  int or_sel_tree(optimizer::RangeParameter *param, SEL_TREE *tree);
 
411
  int or_sel_tree_with_checks(optimizer::RangeParameter *param, SEL_TREE *new_tree);
 
412
  int or_sel_imerge_with_checks(optimizer::RangeParameter *param, SEL_IMERGE* imerge);
 
413
};
 
414
 
 
415
 
 
416
/*
 
417
  Add SEL_TREE to this index_merge without any checks,
 
418
 
 
419
  NOTES
 
420
    This function implements the following:
 
421
      (x_1||...||x_N) || t = (x_1||...||x_N||t), where x_i, t are SEL_TREEs
 
422
 
 
423
  RETURN
 
424
     0 - OK
 
425
    -1 - Out of memory.
 
426
*/
 
427
int SEL_IMERGE::or_sel_tree(optimizer::RangeParameter *param, SEL_TREE *tree)
 
428
{
 
429
  if (trees_next == trees_end)
 
430
  {
 
431
    const int realloc_ratio= 2;         /* Double size for next round */
 
432
    uint32_t old_elements= (trees_end - trees);
 
433
    uint32_t old_size= sizeof(SEL_TREE**) * old_elements;
 
434
    uint32_t new_size= old_size * realloc_ratio;
 
435
    SEL_TREE **new_trees;
 
436
    if (!(new_trees= (SEL_TREE**)alloc_root(param->mem_root, new_size)))
 
437
      return -1;
 
438
    memcpy(new_trees, trees, old_size);
 
439
    trees= new_trees;
 
440
    trees_next= trees + old_elements;
 
441
    trees_end= trees + old_elements * realloc_ratio;
 
442
  }
 
443
  *(trees_next++)= tree;
 
444
  return 0;
 
445
}
 
446
 
 
447
 
 
448
/*
 
449
  Perform OR operation on this SEL_IMERGE and supplied SEL_TREE new_tree,
 
450
  combining new_tree with one of the trees in this SEL_IMERGE if they both
 
451
  have SEL_ARGs for the same key.
 
452
 
 
453
  SYNOPSIS
 
454
    or_sel_tree_with_checks()
 
455
      param    Parameter from SqlSelect::test_quick_select
 
456
      new_tree SEL_TREE with type KEY or KEY_SMALLER.
 
457
 
 
458
  NOTES
 
459
    This does the following:
 
460
    (t_1||...||t_k)||new_tree =
 
461
     either
 
462
       = (t_1||...||t_k||new_tree)
 
463
     or
 
464
       = (t_1||....||(t_j|| new_tree)||...||t_k),
 
465
 
 
466
     where t_i, y are SEL_TREEs.
 
467
    new_tree is combined with the first t_j it has a SEL_ARG on common
 
468
    key with. As a consequence of this, choice of keys to do index_merge
 
469
    read may depend on the order of conditions in WHERE part of the query.
 
470
 
 
471
  RETURN
 
472
    0  OK
 
473
    1  One of the trees was combined with new_tree to SEL_TREE::ALWAYS,
 
474
       and (*this) should be discarded.
 
475
   -1  An error occurred.
 
476
*/
 
477
int SEL_IMERGE::or_sel_tree_with_checks(optimizer::RangeParameter *param, SEL_TREE *new_tree)
 
478
{
 
479
  for (SEL_TREE** tree = trees;
 
480
       tree != trees_next;
 
481
       tree++)
 
482
  {
 
483
    if (sel_trees_can_be_ored(*tree, new_tree, param))
 
484
    {
 
485
      *tree = tree_or(param, *tree, new_tree);
 
486
      if (!*tree)
 
487
        return 1;
 
488
      if (((*tree)->type == SEL_TREE::MAYBE) ||
 
489
          ((*tree)->type == SEL_TREE::ALWAYS))
 
490
        return 1;
 
491
      /* SEL_TREE::IMPOSSIBLE is impossible here */
 
492
      return 0;
 
493
    }
 
494
  }
 
495
 
 
496
  /* New tree cannot be combined with any of existing trees. */
 
497
  return or_sel_tree(param, new_tree);
 
498
}
 
499
 
 
500
 
 
501
/*
 
502
  Perform OR operation on this index_merge and supplied index_merge list.
 
503
 
 
504
  RETURN
 
505
    0 - OK
 
506
    1 - One of conditions in result is always true and this SEL_IMERGE
 
507
        should be discarded.
 
508
   -1 - An error occurred
 
509
*/
 
510
 
 
511
int SEL_IMERGE::or_sel_imerge_with_checks(optimizer::RangeParameter *param, SEL_IMERGE* imerge)
 
512
{
 
513
  for (SEL_TREE** tree= imerge->trees;
 
514
       tree != imerge->trees_next;
 
515
       tree++)
 
516
  {
 
517
    if (or_sel_tree_with_checks(param, *tree))
 
518
      return 1;
 
519
  }
 
520
  return 0;
 
521
}
316
522
 
317
523
 
318
524
/*
319
525
  Perform AND operation on two index_merge lists and store result in *im1.
320
526
*/
321
527
 
322
 
inline void imerge_list_and_list(List<optimizer::SEL_IMERGE> *im1, List<optimizer::SEL_IMERGE> *im2)
 
528
inline void imerge_list_and_list(List<SEL_IMERGE> *im1, List<SEL_IMERGE> *im2)
323
529
{
324
530
  im1->concat(im2);
325
531
}
326
532
 
327
533
 
 
534
/*
 
535
  Perform OR operation on 2 index_merge lists, storing result in first list.
 
536
 
 
537
  NOTES
 
538
    The following conversion is implemented:
 
539
     (a_1 &&...&& a_N)||(b_1 &&...&& b_K) = AND_i,j(a_i || b_j) =>
 
540
      => (a_1||b_1).
 
541
 
 
542
    i.e. all conjuncts except the first one are currently dropped.
 
543
    This is done to avoid producing N*K ways to do index_merge.
 
544
 
 
545
    If (a_1||b_1) produce a condition that is always true, NULL is returned
 
546
    and index_merge is discarded (while it is actually possible to try
 
547
    harder).
 
548
 
 
549
    As a consequence of this, choice of keys to do index_merge read may depend
 
550
    on the order of conditions in WHERE part of the query.
 
551
 
 
552
  RETURN
 
553
    0     OK, result is stored in *im1
 
554
    other Error, both passed lists are unusable
 
555
*/
 
556
 
 
557
static int imerge_list_or_list(optimizer::RangeParameter *param,
 
558
                               List<SEL_IMERGE> *im1,
 
559
                               List<SEL_IMERGE> *im2)
 
560
{
 
561
  SEL_IMERGE *imerge= im1->head();
 
562
  im1->empty();
 
563
  im1->push_back(imerge);
 
564
 
 
565
  return imerge->or_sel_imerge_with_checks(param, im2->head());
 
566
}
 
567
 
 
568
 
 
569
/*
 
570
  Perform OR operation on index_merge list and key tree.
 
571
 
 
572
  RETURN
 
573
     0     OK, result is stored in *im1.
 
574
     other Error
 
575
 */
 
576
 
 
577
static int imerge_list_or_tree(optimizer::RangeParameter *param,
 
578
                               List<SEL_IMERGE> *im1,
 
579
                               SEL_TREE *tree)
 
580
{
 
581
  SEL_IMERGE *imerge;
 
582
  List_iterator<SEL_IMERGE> it(*im1);
 
583
  while ((imerge= it++))
 
584
  {
 
585
    if (imerge->or_sel_tree_with_checks(param, tree))
 
586
      it.remove();
 
587
  }
 
588
  return im1->is_empty();
 
589
}
 
590
 
 
591
 
328
592
/***************************************************************************
329
593
** Basic functions for SqlSelect and QuickRangeSelect
330
594
***************************************************************************/
350
614
  {
351
615
    return 0;
352
616
  }
353
 
  if (! (select= new optimizer::SqlSelect()))
 
617
  if (! (select= new optimizer::SqlSelect))
354
618
  {
355
619
    *error= 1;                  // out of memory
356
620
    return 0;
387
651
 
388
652
void optimizer::SqlSelect::cleanup()
389
653
{
390
 
  if (quick)
391
 
  {
392
 
    delete quick;
393
 
    quick= NULL;
394
 
  }
395
 
 
 
654
  delete quick;
 
655
  quick= 0;
396
656
  if (free_cond)
397
657
  {
398
658
    free_cond= 0;
399
659
    delete cond;
400
660
    cond= 0;
401
661
  }
402
 
  file->close_cached_file();
 
662
  close_cached_file(file);
403
663
}
404
664
 
405
665
 
466
726
    MAX_KEY if no such index was found.
467
727
*/
468
728
 
469
 
uint32_t optimizer::get_index_for_order(Table *table, Order *order, ha_rows limit)
 
729
uint32_t optimizer::get_index_for_order(Table *table, order_st *order, ha_rows limit)
470
730
{
471
731
  uint32_t idx;
472
732
  uint32_t match_key= MAX_KEY, match_key_len= MAX_KEY_LENGTH + 1;
473
 
  Order *ord;
 
733
  order_st *ord;
474
734
 
475
735
  for (ord= order; ord; ord= ord->next)
476
736
    if (!ord->asc)
477
737
      return MAX_KEY;
478
738
 
479
 
  for (idx= 0; idx < table->getShare()->sizeKeys(); idx++)
 
739
  for (idx= 0; idx < table->s->keys; idx++)
480
740
  {
481
741
    if (!(table->keys_in_use_for_query.test(idx)))
482
742
      continue;
483
 
    KeyPartInfo *keyinfo= table->key_info[idx].key_part;
 
743
    KEY_PART_INFO *keyinfo= table->key_info[idx].key_part;
484
744
    uint32_t n_parts=  table->key_info[idx].key_parts;
485
745
    uint32_t partno= 0;
486
746
 
545
805
static int fill_used_fields_bitmap(optimizer::Parameter *param)
546
806
{
547
807
  Table *table= param->table;
 
808
  my_bitmap_map *tmp;
548
809
  uint32_t pk;
549
 
  param->tmp_covered_fields.clear();
550
 
  param->needed_fields.resize(table->getShare()->sizeFields());
551
 
  param->needed_fields.reset();
552
 
 
553
 
  param->needed_fields|= *table->read_set;
554
 
  param->needed_fields|= *table->write_set;
555
 
 
556
 
  pk= param->table->getShare()->getPrimaryKey();
 
810
  param->tmp_covered_fields.setBitmap(0);
 
811
  param->fields_bitmap_size= table->s->column_bitmap_size;
 
812
  if (!(tmp= (my_bitmap_map*) alloc_root(param->mem_root,
 
813
                                  param->fields_bitmap_size)) ||
 
814
      param->needed_fields.init(tmp, table->s->fields))
 
815
    return 1;
 
816
 
 
817
  param->needed_fields= *table->read_set;
 
818
  bitmap_union(&param->needed_fields, table->write_set);
 
819
 
 
820
  pk= param->table->s->primary_key;
557
821
  if (pk != MAX_KEY && param->table->cursor->primary_key_is_clustered())
558
822
  {
559
823
    /* The table uses clustered PK and it is not internally generated */
560
 
    KeyPartInfo *key_part= param->table->key_info[pk].key_part;
561
 
    KeyPartInfo *key_part_end= key_part +
 
824
    KEY_PART_INFO *key_part= param->table->key_info[pk].key_part;
 
825
    KEY_PART_INFO *key_part_end= key_part +
562
826
                                 param->table->key_info[pk].key_parts;
563
827
    for (;key_part != key_part_end; ++key_part)
564
 
      param->needed_fields.reset(key_part->fieldnr-1);
 
828
      param->needed_fields.clearBit(key_part->fieldnr-1);
565
829
  }
566
830
  return 0;
567
831
}
642
906
{
643
907
  uint32_t idx;
644
908
  double scan_time;
645
 
  if (quick)
646
 
  {
647
 
    delete quick;
648
 
    quick= NULL;
649
 
  }
 
909
  delete quick;
 
910
  quick=0;
650
911
  needed_reg.reset();
651
912
  quick_keys.reset();
652
913
  if (keys_to_use.none())
667
928
  if (keys_to_use.any())
668
929
  {
669
930
    memory::Root alloc;
670
 
    optimizer::SEL_TREE *tree= NULL;
 
931
    SEL_TREE *tree= NULL;
671
932
    KEY_PART *key_parts;
672
 
    KeyInfo *key_info;
 
933
    KEY *key_info;
673
934
    optimizer::Parameter param;
674
935
 
675
936
    if (check_stack_overrun(session, 2*STACK_MIN_SIZE, NULL))
692
953
 
693
954
    session->no_errors=1;                               // Don't warn about NULL
694
955
    memory::init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
695
 
    if (!(param.key_parts= (KEY_PART*) alloc.alloc_root( sizeof(KEY_PART) * head->getShare()->key_parts)) ||
 
956
    if (!(param.key_parts= (KEY_PART*) alloc_root(&alloc,
 
957
                                                  sizeof(KEY_PART)*
 
958
                                                  head->s->key_parts)) ||
696
959
        fill_used_fields_bitmap(&param))
697
960
    {
698
961
      session->no_errors=0;
699
 
      alloc.free_root(MYF(0));                  // Return memory & allocator
700
 
 
 
962
      free_root(&alloc,MYF(0));                 // Return memory & allocator
701
963
      return 0;                         // Can't use range
702
964
    }
703
965
    key_parts= param.key_parts;
708
970
      This is used in get_mm_parts function.
709
971
    */
710
972
    key_info= head->key_info;
711
 
    for (idx=0 ; idx < head->getShare()->sizeKeys() ; idx++, key_info++)
 
973
    for (idx=0 ; idx < head->s->keys ; idx++, key_info++)
712
974
    {
713
 
      KeyPartInfo *key_part_info;
 
975
      KEY_PART_INFO *key_part_info;
714
976
      if (! keys_to_use.test(idx))
715
977
        continue;
716
978
 
754
1016
    {
755
1017
      if ((tree= get_mm_tree(&param,cond)))
756
1018
      {
757
 
        if (tree->type == optimizer::SEL_TREE::IMPOSSIBLE)
 
1019
        if (tree->type == SEL_TREE::IMPOSSIBLE)
758
1020
        {
759
1021
          records=0L;                      /* Return -1 from this function. */
760
1022
          read_time= (double) HA_POS_ERROR;
764
1026
          If the tree can't be used for range scans, proceed anyway, as we
765
1027
          can construct a group-min-max quick select
766
1028
        */
767
 
        if (tree->type != optimizer::SEL_TREE::KEY && tree->type != optimizer::SEL_TREE::KEY_SMALLER)
 
1029
        if (tree->type != SEL_TREE::KEY && tree->type != SEL_TREE::KEY_SMALLER)
768
1030
          tree= NULL;
769
1031
      }
770
1032
    }
798
1060
        bool can_build_covering= false;
799
1061
 
800
1062
        /* Get best 'range' plan and prepare data for making other plans */
801
 
        if ((range_trp= get_key_scans_params(session, &param, tree, false, true,
 
1063
        if ((range_trp= get_key_scans_params(&param, tree, false, true,
802
1064
                                             best_read_time)))
803
1065
        {
804
1066
          best_trp= range_trp;
825
1087
              Try constructing covering ROR-intersect only if it looks possible
826
1088
              and worth doing.
827
1089
            */
828
 
            if (!rori_trp->is_covering && can_build_covering &&
 
1090
            if (rori_trp->isRowRetrievalNecessary() && can_build_covering &&
829
1091
                (rori_trp= get_best_covering_ror_intersect(&param, tree,
830
1092
                                                           best_read_time)))
831
1093
              best_trp= rori_trp;
835
1097
      else
836
1098
      {
837
1099
        /* Try creating index_merge/ROR-union scan. */
838
 
        optimizer::SEL_IMERGE *imerge= NULL;
 
1100
        SEL_IMERGE *imerge= NULL;
839
1101
        optimizer::TableReadPlan *best_conj_trp= NULL;
840
1102
        optimizer::TableReadPlan *new_conj_trp= NULL;
841
 
        List_iterator_fast<optimizer::SEL_IMERGE> it(tree->merges);
 
1103
        List_iterator_fast<SEL_IMERGE> it(tree->merges);
842
1104
        while ((imerge= it++))
843
1105
        {
844
 
          new_conj_trp= get_best_disjunct_quick(session, &param, imerge, best_read_time);
 
1106
          new_conj_trp= get_best_disjunct_quick(&param, imerge, best_read_time);
845
1107
          if (new_conj_trp)
846
1108
            set_if_smaller(param.table->quick_condition_rows,
847
1109
                           new_conj_trp->records);
862
1124
      records= best_trp->records;
863
1125
      if (! (quick= best_trp->make_quick(&param, true)) || quick->init())
864
1126
      {
865
 
        /* quick can already be free here */
866
 
        if (quick)
867
 
        {
868
 
          delete quick;
869
 
          quick= NULL;
870
 
        }
 
1127
        delete quick;
 
1128
        quick= NULL;
871
1129
      }
872
1130
    }
873
1131
 
874
1132
  free_mem:
875
 
    alloc.free_root(MYF(0));                    // Return memory & allocator
 
1133
    free_root(&alloc,MYF(0));                   // Return memory & allocator
876
1134
    session->mem_root= param.old_root;
877
1135
    session->no_errors=0;
878
1136
  }
885
1143
}
886
1144
 
887
1145
/*
888
 
  Get best plan for a optimizer::SEL_IMERGE disjunctive expression.
 
1146
  Get best plan for a SEL_IMERGE disjunctive expression.
889
1147
  SYNOPSIS
890
1148
    get_best_disjunct_quick()
891
 
      session
892
1149
      param     Parameter from check_quick_select function
893
1150
      imerge    Expression to use
894
1151
      read_time Don't create scans with cost > read_time
951
1208
*/
952
1209
 
953
1210
static
954
 
optimizer::TableReadPlan *get_best_disjunct_quick(Session *session,
955
 
                                                  optimizer::Parameter *param,
956
 
                                                  optimizer::SEL_IMERGE *imerge,
 
1211
optimizer::TableReadPlan *get_best_disjunct_quick(optimizer::Parameter *param,
 
1212
                                                  SEL_IMERGE *imerge,
957
1213
                                                  double read_time)
958
1214
{
959
 
  optimizer::SEL_TREE **ptree= NULL;
 
1215
  SEL_TREE **ptree;
960
1216
  optimizer::IndexMergeReadPlan *imerge_trp= NULL;
961
1217
  uint32_t n_child_scans= imerge->trees_next - imerge->trees;
962
1218
  optimizer::RangeReadPlan **range_scans= NULL;
976
1232
  ha_rows roru_total_records;
977
1233
  double roru_intersect_part= 1.0;
978
1234
 
979
 
  if (! (range_scans= (optimizer::RangeReadPlan**)param->mem_root->alloc_root(sizeof(optimizer::RangeReadPlan*)* n_child_scans)))
980
 
  {
 
1235
  if (! (range_scans= (optimizer::RangeReadPlan**)alloc_root(param->mem_root,
 
1236
                                                             sizeof(optimizer::RangeReadPlan*)*
 
1237
                                                             n_child_scans)))
981
1238
    return NULL;
982
 
  }
983
 
 
984
1239
  /*
985
1240
    Collect best 'range' scan for each of disjuncts, and, while doing so,
986
1241
    analyze possibility of ROR scans. Also calculate some values needed by
990
1245
       ptree != imerge->trees_next;
991
1246
       ptree++, cur_child++)
992
1247
  {
993
 
    if (!(*cur_child= get_key_scans_params(session, param, *ptree, true, false, read_time)))
 
1248
    print_sel_tree(param, *ptree, &(*ptree)->keys_map, "tree in SEL_IMERGE");
 
1249
    if (!(*cur_child= get_key_scans_params(param, *ptree, true, false, read_time)))
994
1250
    {
995
1251
      /*
996
1252
        One of index scans in this index_merge is more expensive than entire
1007
1263
    all_scans_ror_able &= ((*ptree)->n_ror_scans > 0);
1008
1264
    all_scans_rors &= (*cur_child)->is_ror;
1009
1265
    if (pk_is_clustered &&
1010
 
        param->real_keynr[(*cur_child)->key_idx] ==
1011
 
        param->table->getShare()->getPrimaryKey())
 
1266
        param->real_keynr[(*cur_child)->getKeyIndex()] ==
 
1267
        param->table->s->primary_key)
1012
1268
    {
1013
1269
      cpk_scan= cur_child;
1014
1270
      cpk_scan_records= (*cur_child)->records;
1042
1298
 
1043
1299
  /* Calculate cost(rowid_to_row_scan) */
1044
1300
  {
1045
 
    optimizer::CostVector sweep_cost;
1046
 
    Join *join= param->session->lex->select_lex.join;
 
1301
    COST_VECT sweep_cost;
 
1302
    JOIN *join= param->session->lex->select_lex.join;
1047
1303
    bool is_interrupted= test(join && join->tables == 1);
1048
1304
    get_sweep_read_cost(param->table, non_cpk_scan_records, is_interrupted,
1049
1305
                        &sweep_cost);
1059
1315
                                    param->session->variables.sortbuff_size);
1060
1316
  if (param->imerge_cost_buff_size < unique_calc_buff_size)
1061
1317
  {
1062
 
    if (!(param->imerge_cost_buff= (uint*)param->mem_root->alloc_root(unique_calc_buff_size)))
1063
 
    {
 
1318
    if (!(param->imerge_cost_buff= (uint*)alloc_root(param->mem_root,
 
1319
                                                     unique_calc_buff_size)))
1064
1320
      return NULL;
1065
 
    }
1066
 
 
1067
1321
    param->imerge_cost_buff_size= unique_calc_buff_size;
1068
1322
  }
1069
1323
 
1092
1346
  /* Ok, it is possible to build a ROR-union, try it. */
1093
1347
  bool dummy;
1094
1348
  if (! (roru_read_plans=
1095
 
          (optimizer::TableReadPlan **) param->mem_root->alloc_root(sizeof(optimizer::TableReadPlan*) * n_child_scans)))
1096
 
  {
 
1349
          (optimizer::TableReadPlan **) alloc_root(param->mem_root,
 
1350
                                                   sizeof(optimizer::TableReadPlan*)*
 
1351
                                                   n_child_scans)))
1097
1352
    return imerge_trp;
1098
 
  }
1099
1353
skip_to_ror_scan:
1100
1354
  roru_index_costs= 0.0;
1101
1355
  roru_total_records= 0;
1117
1371
    {
1118
1372
      /* Ok, we have index_only cost, now get full rows scan cost */
1119
1373
      cost= param->table->cursor->
1120
 
              read_time(param->real_keynr[(*cur_child)->key_idx], 1,
 
1374
              read_time(param->real_keynr[(*cur_child)->getKeyIndex()], 1,
1121
1375
                        (*cur_child)->records) +
1122
1376
              rows2double((*cur_child)->records) / TIME_FOR_COMPARE;
1123
1377
    }
1135
1389
      roru_index_costs += (*cur_roru_plan)->read_cost;
1136
1390
    }
1137
1391
    else
 
1392
    {
1138
1393
      roru_index_costs +=
1139
 
        ((optimizer::RorIntersectReadPlan*)(*cur_roru_plan))->index_scan_costs;
 
1394
        ((optimizer::RorIntersectReadPlan *)(*cur_roru_plan))->getCostOfIndexScans();
 
1395
    }
1140
1396
    roru_total_records += (*cur_roru_plan)->records;
1141
1397
    roru_intersect_part *= (*cur_roru_plan)->records /
1142
1398
                           param->table->cursor->stats.records;
1160
1416
  */
1161
1417
  double roru_total_cost;
1162
1418
  {
1163
 
    optimizer::CostVector sweep_cost;
1164
 
    Join *join= param->session->lex->select_lex.join;
 
1419
    COST_VECT sweep_cost;
 
1420
    JOIN *join= param->session->lex->select_lex.join;
1165
1421
    bool is_interrupted= test(join && join->tables == 1);
1166
1422
    get_sweep_read_cost(param->table, roru_total_records, is_interrupted,
1167
1423
                        &sweep_cost);
1176
1432
  {
1177
1433
    if ((roru= new (param->mem_root) optimizer::RorUnionReadPlan))
1178
1434
    {
1179
 
      roru->first_ror= roru_read_plans;
1180
 
      roru->last_ror= roru_read_plans + n_child_scans;
 
1435
      roru->merged_scans.assign(roru_read_plans, roru_read_plans + n_child_scans);
1181
1436
      roru->read_cost= roru_total_cost;
1182
1437
      roru->records= roru_total_records;
1183
1438
      return roru;
1187
1442
}
1188
1443
 
1189
1444
 
 
1445
typedef struct st_ror_scan_info
 
1446
{
 
1447
  uint32_t      idx;      /* # of used key in param->keys */
 
1448
  uint32_t      keynr;    /* # of used key in table */
 
1449
  ha_rows   records;  /* estimate of # records this scan will return */
 
1450
 
 
1451
  /* Set of intervals over key fields that will be used for row retrieval. */
 
1452
  optimizer::SEL_ARG   *sel_arg;
 
1453
 
 
1454
  /* Fields used in the query and covered by this ROR scan. */
 
1455
  MyBitmap covered_fields;
 
1456
  uint32_t      used_fields_covered; /* # of set bits in covered_fields */
 
1457
  int       key_rec_length; /* length of key record (including rowid) */
 
1458
 
 
1459
  /*
 
1460
    Cost of reading all index records with values in sel_arg intervals set
 
1461
    (assuming there is no need to access full table records)
 
1462
  */
 
1463
  double    index_read_cost;
 
1464
  uint32_t      first_uncovered_field; /* first unused bit in covered_fields */
 
1465
  uint32_t      key_components; /* # of parts in the key */
 
1466
} ROR_SCAN_INFO;
 
1467
 
1190
1468
 
1191
1469
/*
1192
 
  Create optimizer::RorScanInfo* structure with a single ROR scan on index idx using
 
1470
  Create ROR_SCAN_INFO* structure with a single ROR scan on index idx using
1193
1471
  sel_arg set of intervals.
1194
1472
 
1195
1473
  SYNOPSIS
1204
1482
*/
1205
1483
 
1206
1484
static
1207
 
optimizer::RorScanInfo *make_ror_scan(const optimizer::Parameter *param, int idx, optimizer::SEL_ARG *sel_arg)
 
1485
ROR_SCAN_INFO *make_ror_scan(const optimizer::Parameter *param, int idx, optimizer::SEL_ARG *sel_arg)
1208
1486
{
1209
 
  optimizer::RorScanInfo *ror_scan= NULL;
 
1487
  ROR_SCAN_INFO *ror_scan;
 
1488
  my_bitmap_map *bitmap_buf;
1210
1489
 
1211
1490
  uint32_t keynr;
1212
1491
 
1213
 
  if (!(ror_scan= (optimizer::RorScanInfo*)param->mem_root->alloc_root(sizeof(optimizer::RorScanInfo))))
 
1492
  if (!(ror_scan= (ROR_SCAN_INFO*)alloc_root(param->mem_root,
 
1493
                                             sizeof(ROR_SCAN_INFO))))
1214
1494
    return NULL;
1215
1495
 
1216
1496
  ror_scan->idx= idx;
1220
1500
  ror_scan->sel_arg= sel_arg;
1221
1501
  ror_scan->records= param->table->quick_rows[keynr];
1222
1502
 
1223
 
  ror_scan->covered_fields_size= param->table->getShare()->sizeFields();
1224
 
  boost::dynamic_bitset<> tmp_bitset(param->table->getShare()->sizeFields());
1225
 
  tmp_bitset.reset();
1226
 
 
1227
 
  KeyPartInfo *key_part= param->table->key_info[keynr].key_part;
1228
 
  KeyPartInfo *key_part_end= key_part +
 
1503
  if (!(bitmap_buf= (my_bitmap_map*) alloc_root(param->mem_root,
 
1504
                                                param->fields_bitmap_size)))
 
1505
    return NULL;
 
1506
 
 
1507
  if (ror_scan->covered_fields.init(bitmap_buf,
 
1508
                                    param->table->s->fields))
 
1509
    return NULL;
 
1510
  ror_scan->covered_fields.clearAll();
 
1511
 
 
1512
  KEY_PART_INFO *key_part= param->table->key_info[keynr].key_part;
 
1513
  KEY_PART_INFO *key_part_end= key_part +
1229
1514
                               param->table->key_info[keynr].key_parts;
1230
 
  for (; key_part != key_part_end; ++key_part)
 
1515
  for (;key_part != key_part_end; ++key_part)
1231
1516
  {
1232
 
    if (param->needed_fields.test(key_part->fieldnr-1))
1233
 
      tmp_bitset.set(key_part->fieldnr-1);
 
1517
    if (param->needed_fields.isBitSet(key_part->fieldnr-1))
 
1518
      ror_scan->covered_fields.setBit(key_part->fieldnr-1);
1234
1519
  }
1235
1520
  double rows= rows2double(param->table->quick_rows[ror_scan->keynr]);
1236
1521
  ror_scan->index_read_cost=
1237
1522
    param->table->cursor->index_only_read_time(ror_scan->keynr, rows);
1238
 
  ror_scan->covered_fields= tmp_bitset.to_ulong();
1239
 
  return ror_scan;
 
1523
  return(ror_scan);
1240
1524
}
1241
1525
 
1242
1526
 
1243
1527
/*
1244
 
  Compare two optimizer::RorScanInfo** by  E(#records_matched) * key_record_length.
 
1528
  Compare two ROR_SCAN_INFO** by  E(#records_matched) * key_record_length.
1245
1529
  SYNOPSIS
1246
1530
    cmp_ror_scan_info()
1247
1531
      a ptr to first compared value
1253
1537
    1 a > b
1254
1538
*/
1255
1539
 
1256
 
static int cmp_ror_scan_info(optimizer::RorScanInfo** a, optimizer::RorScanInfo** b)
 
1540
static int cmp_ror_scan_info(ROR_SCAN_INFO** a, ROR_SCAN_INFO** b)
1257
1541
{
1258
1542
  double val1= rows2double((*a)->records) * (*a)->key_rec_length;
1259
1543
  double val2= rows2double((*b)->records) * (*b)->key_rec_length;
1260
1544
  return (val1 < val2)? -1: (val1 == val2)? 0 : 1;
1261
1545
}
1262
1546
 
1263
 
 
1264
1547
/*
1265
 
  Compare two optimizer::RorScanInfo** by
 
1548
  Compare two ROR_SCAN_INFO** by
1266
1549
   (#covered fields in F desc,
1267
1550
    #components asc,
1268
1551
    number of first not covered component asc)
1278
1561
    1 a > b
1279
1562
*/
1280
1563
 
1281
 
static int cmp_ror_scan_info_covering(optimizer::RorScanInfo** a, optimizer::RorScanInfo** b)
 
1564
static int cmp_ror_scan_info_covering(ROR_SCAN_INFO** a, ROR_SCAN_INFO** b)
1282
1565
{
1283
1566
  if ((*a)->used_fields_covered > (*b)->used_fields_covered)
1284
1567
    return -1;
1295
1578
  return 0;
1296
1579
}
1297
1580
 
 
1581
 
1298
1582
/* Auxiliary structure for incremental ROR-intersection creation */
1299
 
typedef struct st_ror_intersect_info
 
1583
typedef struct
1300
1584
{
1301
 
  st_ror_intersect_info()
1302
 
    :
1303
 
      param(NULL),
1304
 
      covered_fields(),
1305
 
      out_rows(0.0),
1306
 
      is_covering(false),
1307
 
      index_records(0),
1308
 
      index_scan_costs(0.0),
1309
 
      total_cost(0.0)
1310
 
  {}
1311
 
 
1312
 
  st_ror_intersect_info(const optimizer::Parameter *in_param)
1313
 
    :
1314
 
      param(in_param),
1315
 
      covered_fields(in_param->table->getShare()->sizeFields()),
1316
 
      out_rows(in_param->table->cursor->stats.records),
1317
 
      is_covering(false),
1318
 
      index_records(0),
1319
 
      index_scan_costs(0.0),
1320
 
      total_cost(0.0)
1321
 
  {
1322
 
    covered_fields.reset();
1323
 
  }
1324
 
 
1325
1585
  const optimizer::Parameter *param;
1326
 
  boost::dynamic_bitset<> covered_fields; /* union of fields covered by all scans */
 
1586
  MyBitmap covered_fields; /* union of fields covered by all scans */
1327
1587
  /*
1328
1588
    Fraction of table records that satisfies conditions of all scans.
1329
1589
    This is the number of full records that will be retrieved if a
1339
1599
} ROR_INTERSECT_INFO;
1340
1600
 
1341
1601
 
 
1602
/*
 
1603
  Allocate a ROR_INTERSECT_INFO and initialize it to contain zero scans.
 
1604
 
 
1605
  SYNOPSIS
 
1606
    ror_intersect_init()
 
1607
      param         Parameter from test_quick_select
 
1608
 
 
1609
  RETURN
 
1610
    allocated structure
 
1611
    NULL on error
 
1612
*/
 
1613
 
 
1614
static
 
1615
ROR_INTERSECT_INFO* ror_intersect_init(const optimizer::Parameter *param)
 
1616
{
 
1617
  ROR_INTERSECT_INFO *info;
 
1618
  my_bitmap_map* buf;
 
1619
  if (!(info= (ROR_INTERSECT_INFO*)alloc_root(param->mem_root,
 
1620
                                              sizeof(ROR_INTERSECT_INFO))))
 
1621
    return NULL;
 
1622
  info->param= param;
 
1623
  if (!(buf= (my_bitmap_map*) alloc_root(param->mem_root,
 
1624
                                         param->fields_bitmap_size)))
 
1625
    return NULL;
 
1626
  if (info->covered_fields.init(buf, param->table->s->fields))
 
1627
    return NULL;
 
1628
  info->is_covering= false;
 
1629
  info->index_scan_costs= 0.0;
 
1630
  info->index_records= 0;
 
1631
  info->out_rows= (double) param->table->cursor->stats.records;
 
1632
  info->covered_fields.clearAll();
 
1633
  return info;
 
1634
}
 
1635
 
1342
1636
static void ror_intersect_cpy(ROR_INTERSECT_INFO *dst,
1343
1637
                              const ROR_INTERSECT_INFO *src)
1344
1638
{
1443
1737
*/
1444
1738
 
1445
1739
static double ror_scan_selectivity(const ROR_INTERSECT_INFO *info,
1446
 
                                   const optimizer::RorScanInfo *scan)
 
1740
                                   const ROR_SCAN_INFO *scan)
1447
1741
{
1448
1742
  double selectivity_mult= 1.0;
1449
 
  KeyPartInfo *key_part= info->param->table->key_info[scan->keynr].key_part;
 
1743
  KEY_PART_INFO *key_part= info->param->table->key_info[scan->keynr].key_part;
1450
1744
  unsigned char key_val[MAX_KEY_LENGTH+MAX_FIELD_WIDTH]; /* key values tuple */
1451
1745
  unsigned char *key_ptr= key_val;
1452
1746
  optimizer::SEL_ARG *sel_arg= NULL;
1453
1747
  optimizer::SEL_ARG *tuple_arg= NULL;
1454
1748
  key_part_map keypart_map= 0;
1455
1749
  bool cur_covered;
1456
 
  bool prev_covered= test(info->covered_fields.test(key_part->fieldnr-1));
 
1750
  bool prev_covered= test(info->covered_fields.isBitSet(key_part->fieldnr-1));
1457
1751
  key_range min_range;
1458
1752
  key_range max_range;
1459
1753
  min_range.key= key_val;
1466
1760
       sel_arg= sel_arg->next_key_part)
1467
1761
  {
1468
1762
    cur_covered=
1469
 
      test(info->covered_fields.test(key_part[sel_arg->part].fieldnr-1));
 
1763
      test(info->covered_fields.isBitSet(key_part[sel_arg->part].fieldnr-1));
1470
1764
    if (cur_covered != prev_covered)
1471
1765
    {
1472
1766
      /* create (part1val, ..., part{n-1}val) tuple. */
1551
1845
*/
1552
1846
 
1553
1847
static bool ror_intersect_add(ROR_INTERSECT_INFO *info,
1554
 
                              optimizer::RorScanInfo* ror_scan, bool is_cpk_scan)
 
1848
                              ROR_SCAN_INFO* ror_scan, bool is_cpk_scan)
1555
1849
{
1556
1850
  double selectivity_mult= 1.0;
1557
1851
 
1578
1872
  {
1579
1873
    info->index_records += info->param->table->quick_rows[ror_scan->keynr];
1580
1874
    info->index_scan_costs += ror_scan->index_read_cost;
1581
 
    boost::dynamic_bitset<> tmp_bitset= ror_scan->bitsToBitset();
1582
 
    info->covered_fields|= tmp_bitset;
1583
 
    if (! info->is_covering && info->param->needed_fields.is_subset_of(info->covered_fields))
 
1875
    bitmap_union(&info->covered_fields, &ror_scan->covered_fields);
 
1876
    if (!info->is_covering && bitmap_is_subset(&info->param->needed_fields,
 
1877
                                               &info->covered_fields))
1584
1878
    {
1585
1879
      info->is_covering= true;
1586
1880
    }
1587
1881
  }
1588
1882
 
1589
1883
  info->total_cost= info->index_scan_costs;
1590
 
  if (! info->is_covering)
 
1884
  if (!info->is_covering)
1591
1885
  {
1592
 
    optimizer::CostVector sweep_cost;
1593
 
    Join *join= info->param->session->lex->select_lex.join;
 
1886
    COST_VECT sweep_cost;
 
1887
    JOIN *join= info->param->session->lex->select_lex.join;
1594
1888
    bool is_interrupted= test(join && join->tables == 1);
1595
1889
    get_sweep_read_cost(info->param->table, double2rows(info->out_rows),
1596
1890
                        is_interrupted, &sweep_cost);
1601
1895
 
1602
1896
 
1603
1897
/*
1604
 
  Get best covering ROR-intersection.
1605
 
  SYNOPSIS
1606
 
    get_best_covering_ror_intersect()
1607
 
      param     Parameter from test_quick_select function.
1608
 
      tree      optimizer::SEL_TREE with sets of intervals for different keys.
1609
 
      read_time Don't return table read plans with cost > read_time.
1610
 
 
1611
 
  RETURN
1612
 
    Best covering ROR-intersection plan
1613
 
    NULL if no plan found.
1614
 
 
1615
 
  NOTES
1616
 
    get_best_ror_intersect must be called for a tree before calling this
1617
 
    function for it.
1618
 
    This function invalidates tree->ror_scans member values.
1619
 
 
1620
 
  The following approximate algorithm is used:
1621
 
    I=set of all covering indexes
1622
 
    F=set of all fields to cover
1623
 
    S={}
1624
 
 
1625
 
    do
1626
 
    {
1627
 
      Order I by (#covered fields in F desc,
1628
 
                  #components asc,
1629
 
                  number of first not covered component asc);
1630
 
      F=F-covered by first(I);
1631
 
      S=S+first(I);
1632
 
      I=I-first(I);
1633
 
    } while F is not empty.
1634
 
*/
1635
 
 
1636
 
static
1637
 
optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
1638
 
                                                            optimizer::SEL_TREE *tree,
1639
 
                                                            double read_time)
1640
 
{
1641
 
  optimizer::RorScanInfo **ror_scan_mark;
1642
 
  optimizer::RorScanInfo **ror_scans_end= tree->ror_scans_end;
1643
 
 
1644
 
  for (optimizer::RorScanInfo **scan= tree->ror_scans; scan != ror_scans_end; ++scan)
1645
 
    (*scan)->key_components=
1646
 
      param->table->key_info[(*scan)->keynr].key_parts;
1647
 
 
1648
 
  /*
1649
 
    Run covering-ROR-search algorithm.
1650
 
    Assume set I is [ror_scan .. ror_scans_end)
1651
 
  */
1652
 
 
1653
 
  /*I=set of all covering indexes */
1654
 
  ror_scan_mark= tree->ror_scans;
1655
 
 
1656
 
  boost::dynamic_bitset<> *covered_fields= &param->tmp_covered_fields;
1657
 
  if (covered_fields->empty())
1658
 
  {
1659
 
    covered_fields->resize(param->table->getShare()->sizeFields());
1660
 
  }
1661
 
  covered_fields->reset();
1662
 
 
1663
 
  double total_cost= 0.0f;
1664
 
  ha_rows records=0;
1665
 
  bool all_covered;
1666
 
 
1667
 
  do
1668
 
  {
1669
 
    /*
1670
 
      Update changed sorting info:
1671
 
        #covered fields,
1672
 
        number of first not covered component
1673
 
      Calculate and save these values for each of remaining scans.
1674
 
    */
1675
 
    for (optimizer::RorScanInfo **scan= ror_scan_mark; scan != ror_scans_end; ++scan)
1676
 
    {
1677
 
      /* subtract one bitset from the other */
1678
 
      (*scan)->subtractBitset(*covered_fields);
1679
 
      (*scan)->used_fields_covered=
1680
 
        (*scan)->getBitCount();
1681
 
      (*scan)->first_uncovered_field= (*scan)->findFirstNotSet();
1682
 
    }
1683
 
 
1684
 
    internal::my_qsort(ror_scan_mark, ror_scans_end-ror_scan_mark,
1685
 
                       sizeof(optimizer::RorScanInfo*),
1686
 
                       (qsort_cmp)cmp_ror_scan_info_covering);
1687
 
 
1688
 
    /* I=I-first(I) */
1689
 
    total_cost += (*ror_scan_mark)->index_read_cost;
1690
 
    records += (*ror_scan_mark)->records;
1691
 
    if (total_cost > read_time)
1692
 
      return NULL;
1693
 
    /* F=F-covered by first(I) */
1694
 
    boost::dynamic_bitset<> tmp_bitset= (*ror_scan_mark)->bitsToBitset();
1695
 
    *covered_fields|= tmp_bitset;
1696
 
    all_covered= param->needed_fields.is_subset_of(*covered_fields);
1697
 
  } while ((++ror_scan_mark < ror_scans_end) && ! all_covered);
1698
 
 
1699
 
  if (!all_covered || (ror_scan_mark - tree->ror_scans) == 1)
1700
 
    return NULL;
1701
 
 
1702
 
  /*
1703
 
    Ok, [tree->ror_scans .. ror_scan) holds covering index_intersection with
1704
 
    cost total_cost.
1705
 
  */
1706
 
  /* Add priority queue use cost. */
1707
 
  total_cost += rows2double(records)*
1708
 
                log((double)(ror_scan_mark - tree->ror_scans)) /
1709
 
                (TIME_FOR_COMPARE_ROWID * M_LN2);
1710
 
 
1711
 
  if (total_cost > read_time)
1712
 
    return NULL;
1713
 
 
1714
 
  optimizer::RorIntersectReadPlan *trp= NULL;
1715
 
  if (! (trp= new (param->mem_root) optimizer::RorIntersectReadPlan))
1716
 
  {
1717
 
    return trp;
1718
 
  }
1719
 
 
1720
 
  uint32_t best_num= (ror_scan_mark - tree->ror_scans);
1721
 
  if (!(trp->first_scan= (optimizer::RorScanInfo**)param->mem_root->alloc_root(sizeof(optimizer::RorScanInfo*)* best_num)))
1722
 
    return NULL;
1723
 
  memcpy(trp->first_scan, tree->ror_scans, best_num*sizeof(optimizer::RorScanInfo*));
1724
 
  trp->last_scan=  trp->first_scan + best_num;
1725
 
  trp->is_covering= true;
1726
 
  trp->read_cost= total_cost;
1727
 
  trp->records= records;
1728
 
  trp->cpk_scan= NULL;
1729
 
  set_if_smaller(param->table->quick_condition_rows, records);
1730
 
 
1731
 
  return(trp);
1732
 
}
1733
 
 
1734
 
 
1735
 
/*
1736
1898
  Get best ROR-intersection plan using non-covering ROR-intersection search
1737
1899
  algorithm. The returned plan may be covering.
1738
1900
 
1798
1960
 
1799
1961
static
1800
1962
optimizer::RorIntersectReadPlan *get_best_ror_intersect(const optimizer::Parameter *param,
1801
 
                                                   optimizer::SEL_TREE *tree,
 
1963
                                                   SEL_TREE *tree,
1802
1964
                                                   double read_time,
1803
1965
                                                   bool *are_all_covering)
1804
1966
{
1805
 
  uint32_t idx= 0;
 
1967
  uint32_t idx;
1806
1968
  double min_cost= DBL_MAX;
1807
1969
 
1808
 
  if ((tree->n_ror_scans < 2) || ! param->table->cursor->stats.records)
 
1970
  if ((tree->n_ror_scans < 2) || !param->table->cursor->stats.records)
1809
1971
    return NULL;
1810
1972
 
1811
1973
  /*
1812
 
    Step1: Collect ROR-able SEL_ARGs and create optimizer::RorScanInfo for each of
 
1974
    Step1: Collect ROR-able SEL_ARGs and create ROR_SCAN_INFO for each of
1813
1975
    them. Also find and save clustered PK scan if there is one.
1814
1976
  */
1815
 
  optimizer::RorScanInfo **cur_ror_scan= NULL;
1816
 
  optimizer::RorScanInfo *cpk_scan= NULL;
1817
 
  uint32_t cpk_no= 0;
 
1977
  ROR_SCAN_INFO **cur_ror_scan;
 
1978
  ROR_SCAN_INFO *cpk_scan= NULL;
 
1979
  uint32_t cpk_no;
1818
1980
  bool cpk_scan_used= false;
1819
1981
 
1820
 
  if (! (tree->ror_scans= (optimizer::RorScanInfo**)param->mem_root->alloc_root(sizeof(optimizer::RorScanInfo*)* param->keys)))
1821
 
  {
 
1982
  if (!(tree->ror_scans= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
 
1983
                                                     sizeof(ROR_SCAN_INFO*)*
 
1984
                                                     param->keys)))
1822
1985
    return NULL;
1823
 
  }
1824
1986
  cpk_no= ((param->table->cursor->primary_key_is_clustered()) ?
1825
 
           param->table->getShare()->getPrimaryKey() : MAX_KEY);
 
1987
           param->table->s->primary_key : MAX_KEY);
1826
1988
 
1827
1989
  for (idx= 0, cur_ror_scan= tree->ror_scans; idx < param->keys; idx++)
1828
1990
  {
1829
 
    optimizer::RorScanInfo *scan;
 
1991
    ROR_SCAN_INFO *scan;
1830
1992
    if (! tree->ror_scans_map.test(idx))
1831
1993
      continue;
1832
 
    if (! (scan= make_ror_scan(param, idx, tree->keys[idx])))
 
1994
    if (!(scan= make_ror_scan(param, idx, tree->keys[idx])))
1833
1995
      return NULL;
1834
1996
    if (param->real_keynr[idx] == cpk_no)
1835
1997
    {
1841
2003
  }
1842
2004
 
1843
2005
  tree->ror_scans_end= cur_ror_scan;
 
2006
  print_ror_scans_arr(param->table, "original",
 
2007
                                          tree->ror_scans,
 
2008
                                          tree->ror_scans_end);
1844
2009
  /*
1845
2010
    Ok, [ror_scans, ror_scans_end) is array of ptrs to initialized
1846
 
    optimizer::RorScanInfo's.
 
2011
    ROR_SCAN_INFO's.
1847
2012
    Step 2: Get best ROR-intersection using an approximate algorithm.
1848
2013
  */
1849
 
  internal::my_qsort(tree->ror_scans, tree->n_ror_scans, sizeof(optimizer::RorScanInfo*),
 
2014
  internal::my_qsort(tree->ror_scans, tree->n_ror_scans, sizeof(ROR_SCAN_INFO*),
1850
2015
                     (qsort_cmp)cmp_ror_scan_info);
 
2016
  print_ror_scans_arr(param->table, "ordered",
 
2017
                                          tree->ror_scans,
 
2018
                                          tree->ror_scans_end);
1851
2019
 
1852
 
  optimizer::RorScanInfo **intersect_scans= NULL; /* ROR scans used in index intersection */
1853
 
  optimizer::RorScanInfo **intersect_scans_end= NULL;
1854
 
  if (! (intersect_scans= (optimizer::RorScanInfo**)param->mem_root->alloc_root(sizeof(optimizer::RorScanInfo*) * tree->n_ror_scans)))
 
2020
  ROR_SCAN_INFO **intersect_scans; /* ROR scans used in index intersection */
 
2021
  ROR_SCAN_INFO **intersect_scans_end;
 
2022
  if (!(intersect_scans= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
 
2023
                                                     sizeof(ROR_SCAN_INFO*)*
 
2024
                                                     tree->n_ror_scans)))
1855
2025
    return NULL;
1856
2026
  intersect_scans_end= intersect_scans;
1857
2027
 
1858
2028
  /* Create and incrementally update ROR intersection. */
1859
 
  ROR_INTERSECT_INFO intersect(param);
1860
 
  ROR_INTERSECT_INFO intersect_best(param);
 
2029
  ROR_INTERSECT_INFO *intersect, *intersect_best;
 
2030
  if (!(intersect= ror_intersect_init(param)) ||
 
2031
      !(intersect_best= ror_intersect_init(param)))
 
2032
    return NULL;
1861
2033
 
1862
2034
  /* [intersect_scans,intersect_scans_best) will hold the best intersection */
1863
 
  optimizer::RorScanInfo **intersect_scans_best= NULL;
 
2035
  ROR_SCAN_INFO **intersect_scans_best;
1864
2036
  cur_ror_scan= tree->ror_scans;
1865
2037
  intersect_scans_best= intersect_scans;
1866
 
  while (cur_ror_scan != tree->ror_scans_end && ! intersect.is_covering)
 
2038
  while (cur_ror_scan != tree->ror_scans_end && !intersect->is_covering)
1867
2039
  {
1868
2040
    /* S= S + first(R);  R= R - first(R); */
1869
 
    if (! ror_intersect_add(&intersect, *cur_ror_scan, false))
 
2041
    if (!ror_intersect_add(intersect, *cur_ror_scan, false))
1870
2042
    {
1871
2043
      cur_ror_scan++;
1872
2044
      continue;
1874
2046
 
1875
2047
    *(intersect_scans_end++)= *(cur_ror_scan++);
1876
2048
 
1877
 
    if (intersect.total_cost < min_cost)
 
2049
    if (intersect->total_cost < min_cost)
1878
2050
    {
1879
2051
      /* Local minimum found, save it */
1880
 
      ror_intersect_cpy(&intersect_best, &intersect);
 
2052
      ror_intersect_cpy(intersect_best, intersect);
1881
2053
      intersect_scans_best= intersect_scans_end;
1882
 
      min_cost = intersect.total_cost;
 
2054
      min_cost = intersect->total_cost;
1883
2055
    }
1884
2056
  }
1885
2057
 
1888
2060
    return NULL;
1889
2061
  }
1890
2062
 
1891
 
  *are_all_covering= intersect.is_covering;
 
2063
  print_ror_scans_arr(param->table,
 
2064
                                          "best ROR-intersection",
 
2065
                                          intersect_scans,
 
2066
                                          intersect_scans_best);
 
2067
 
 
2068
  *are_all_covering= intersect->is_covering;
1892
2069
  uint32_t best_num= intersect_scans_best - intersect_scans;
1893
 
  ror_intersect_cpy(&intersect, &intersect_best);
 
2070
  ror_intersect_cpy(intersect, intersect_best);
1894
2071
 
1895
2072
  /*
1896
2073
    Ok, found the best ROR-intersection of non-CPK key scans.
1897
2074
    Check if we should add a CPK scan. If the obtained ROR-intersection is
1898
2075
    covering, it doesn't make sense to add CPK scan.
1899
2076
  */
1900
 
  if (cpk_scan && ! intersect.is_covering)
 
2077
  if (cpk_scan && !intersect->is_covering)
1901
2078
  {
1902
 
    if (ror_intersect_add(&intersect, cpk_scan, true) &&
1903
 
        (intersect.total_cost < min_cost))
 
2079
    if (ror_intersect_add(intersect, cpk_scan, true) &&
 
2080
        (intersect->total_cost < min_cost))
1904
2081
    {
1905
2082
      cpk_scan_used= true;
1906
2083
      intersect_best= intersect; //just set pointer here
1914
2091
    if (! (trp= new (param->mem_root) optimizer::RorIntersectReadPlan))
1915
2092
      return trp;
1916
2093
 
1917
 
    if (! (trp->first_scan=
1918
 
           (optimizer::RorScanInfo**)param->mem_root->alloc_root(sizeof(optimizer::RorScanInfo*)*best_num)))
1919
 
      return NULL;
1920
 
    memcpy(trp->first_scan, intersect_scans, best_num*sizeof(optimizer::RorScanInfo*));
1921
 
    trp->last_scan=  trp->first_scan + best_num;
1922
 
    trp->is_covering= intersect_best.is_covering;
1923
 
    trp->read_cost= intersect_best.total_cost;
 
2094
    trp->ror_range_scans.assign(intersect_scans, intersect_scans + best_num);
 
2095
    trp->setRowRetrievalNecessary(intersect_best->is_covering);
 
2096
    trp->read_cost= intersect_best->total_cost;
1924
2097
    /* Prevent divisons by zero */
1925
 
    ha_rows best_rows = double2rows(intersect_best.out_rows);
1926
 
    if (! best_rows)
 
2098
    ha_rows best_rows = double2rows(intersect_best->out_rows);
 
2099
    if (!best_rows)
1927
2100
      best_rows= 1;
1928
2101
    set_if_smaller(param->table->quick_condition_rows, best_rows);
1929
2102
    trp->records= best_rows;
1930
 
    trp->index_scan_costs= intersect_best.index_scan_costs;
 
2103
    trp->setCostOfIndexScans(intersect_best->index_scan_costs);
1931
2104
    trp->cpk_scan= cpk_scan_used? cpk_scan: NULL;
1932
2105
  }
1933
 
  return trp;
1934
 
}
1935
 
 
1936
 
 
1937
 
/*
1938
 
  Get best "range" table read plan for given optimizer::SEL_TREE, also update some info
 
2106
  return(trp);
 
2107
}
 
2108
 
 
2109
 
 
2110
/*
 
2111
  Get best covering ROR-intersection.
 
2112
  SYNOPSIS
 
2113
    get_best_covering_ror_intersect()
 
2114
      param     Parameter from test_quick_select function.
 
2115
      tree      SEL_TREE with sets of intervals for different keys.
 
2116
      read_time Don't return table read plans with cost > read_time.
 
2117
 
 
2118
  RETURN
 
2119
    Best covering ROR-intersection plan
 
2120
    NULL if no plan found.
 
2121
 
 
2122
  NOTES
 
2123
    get_best_ror_intersect must be called for a tree before calling this
 
2124
    function for it.
 
2125
    This function invalidates tree->ror_scans member values.
 
2126
 
 
2127
  The following approximate algorithm is used:
 
2128
    I=set of all covering indexes
 
2129
    F=set of all fields to cover
 
2130
    S={}
 
2131
 
 
2132
    do
 
2133
    {
 
2134
      Order I by (#covered fields in F desc,
 
2135
                  #components asc,
 
2136
                  number of first not covered component asc);
 
2137
      F=F-covered by first(I);
 
2138
      S=S+first(I);
 
2139
      I=I-first(I);
 
2140
    } while F is not empty.
 
2141
*/
 
2142
 
 
2143
static
 
2144
optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
 
2145
                                                            SEL_TREE *tree,
 
2146
                                                            double read_time)
 
2147
{
 
2148
  ROR_SCAN_INFO **ror_scan_mark;
 
2149
  ROR_SCAN_INFO **ror_scans_end= tree->ror_scans_end;
 
2150
 
 
2151
  for (ROR_SCAN_INFO **scan= tree->ror_scans; scan != ror_scans_end; ++scan)
 
2152
    (*scan)->key_components=
 
2153
      param->table->key_info[(*scan)->keynr].key_parts;
 
2154
 
 
2155
  /*
 
2156
    Run covering-ROR-search algorithm.
 
2157
    Assume set I is [ror_scan .. ror_scans_end)
 
2158
  */
 
2159
 
 
2160
  /*I=set of all covering indexes */
 
2161
  ror_scan_mark= tree->ror_scans;
 
2162
 
 
2163
  MyBitmap *covered_fields= &param->tmp_covered_fields;
 
2164
  if (! covered_fields->getBitmap())
 
2165
  {
 
2166
    my_bitmap_map *tmp_bitmap= (my_bitmap_map*)alloc_root(param->mem_root,
 
2167
                                               param->fields_bitmap_size);
 
2168
    covered_fields->setBitmap(tmp_bitmap);
 
2169
  }
 
2170
  if (! covered_fields->getBitmap() ||
 
2171
      covered_fields->init(covered_fields->getBitmap(),
 
2172
                           param->table->s->fields))
 
2173
    return 0;
 
2174
  covered_fields->clearAll();
 
2175
 
 
2176
  double total_cost= 0.0f;
 
2177
  ha_rows records=0;
 
2178
  bool all_covered;
 
2179
 
 
2180
  print_ror_scans_arr(param->table,
 
2181
                                           "building covering ROR-I",
 
2182
                                           ror_scan_mark, ror_scans_end);
 
2183
  do
 
2184
  {
 
2185
    /*
 
2186
      Update changed sorting info:
 
2187
        #covered fields,
 
2188
        number of first not covered component
 
2189
      Calculate and save these values for each of remaining scans.
 
2190
    */
 
2191
    for (ROR_SCAN_INFO **scan= ror_scan_mark; scan != ror_scans_end; ++scan)
 
2192
    {
 
2193
      bitmap_subtract(&(*scan)->covered_fields, covered_fields);
 
2194
      (*scan)->used_fields_covered=
 
2195
        (*scan)->covered_fields.getBitsSet();
 
2196
      (*scan)->first_uncovered_field=
 
2197
        (*scan)->covered_fields.getFirst();
 
2198
    }
 
2199
 
 
2200
    internal::my_qsort(ror_scan_mark, ror_scans_end-ror_scan_mark,
 
2201
                       sizeof(ROR_SCAN_INFO*),
 
2202
                       (qsort_cmp)cmp_ror_scan_info_covering);
 
2203
 
 
2204
    print_ror_scans_arr(param->table,
 
2205
                                             "remaining scans",
 
2206
                                             ror_scan_mark, ror_scans_end);
 
2207
 
 
2208
    /* I=I-first(I) */
 
2209
    total_cost += (*ror_scan_mark)->index_read_cost;
 
2210
    records += (*ror_scan_mark)->records;
 
2211
    if (total_cost > read_time)
 
2212
      return NULL;
 
2213
    /* F=F-covered by first(I) */
 
2214
    bitmap_union(covered_fields, &(*ror_scan_mark)->covered_fields);
 
2215
    all_covered= bitmap_is_subset(&param->needed_fields, covered_fields);
 
2216
  } while ((++ror_scan_mark < ror_scans_end) && !all_covered);
 
2217
 
 
2218
  if (!all_covered || (ror_scan_mark - tree->ror_scans) == 1)
 
2219
    return NULL;
 
2220
 
 
2221
  /*
 
2222
    Ok, [tree->ror_scans .. ror_scan) holds covering index_intersection with
 
2223
    cost total_cost.
 
2224
  */
 
2225
  print_ror_scans_arr(param->table,
 
2226
                                           "creating covering ROR-intersect",
 
2227
                                           tree->ror_scans, ror_scan_mark);
 
2228
 
 
2229
  /* Add priority queue use cost. */
 
2230
  total_cost += rows2double(records)*
 
2231
                log((double)(ror_scan_mark - tree->ror_scans)) /
 
2232
                (TIME_FOR_COMPARE_ROWID * M_LN2);
 
2233
 
 
2234
  if (total_cost > read_time)
 
2235
    return NULL;
 
2236
 
 
2237
  optimizer::RorIntersectReadPlan *trp= NULL;
 
2238
  if (! (trp= new (param->mem_root) optimizer::RorIntersectReadPlan))
 
2239
  {
 
2240
    return trp;
 
2241
  }
 
2242
 
 
2243
  uint32_t best_num= (ror_scan_mark - tree->ror_scans);
 
2244
  trp->ror_range_scans.assign(tree->ror_scans, tree->ror_scans + best_num);
 
2245
  trp->setRowRetrievalNecessary(true);
 
2246
  trp->read_cost= total_cost;
 
2247
  trp->records= records;
 
2248
  trp->cpk_scan= NULL;
 
2249
  set_if_smaller(param->table->quick_condition_rows, records);
 
2250
 
 
2251
  return(trp);
 
2252
}
 
2253
 
 
2254
 
 
2255
/*
 
2256
  Get best "range" table read plan for given SEL_TREE, also update some info
1939
2257
 
1940
2258
  SYNOPSIS
1941
2259
    get_key_scans_params()
1942
 
      session
1943
2260
      param                    Parameters from test_quick_select
1944
 
      tree                     Make range select for this optimizer::SEL_TREE
 
2261
      tree                     Make range select for this SEL_TREE
1945
2262
      index_read_must_be_used  true <=> assume 'index only' option will be set
1946
2263
                               (except for clustered PK indexes)
1947
2264
      update_tbl_stats         true <=> update table->quick_* with information
1950
2267
                               cost > read_time.
1951
2268
 
1952
2269
  DESCRIPTION
1953
 
    Find the best "range" table read plan for given optimizer::SEL_TREE.
 
2270
    Find the best "range" table read plan for given SEL_TREE.
1954
2271
    The side effects are
1955
2272
     - tree->ror_scans is updated to indicate which scans are ROR scans.
1956
2273
     - if update_tbl_stats=true then table->quick_* is updated with info
1961
2278
    NULL if no plan found or error occurred
1962
2279
*/
1963
2280
 
1964
 
static optimizer::RangeReadPlan *get_key_scans_params(Session *session,
1965
 
                                                      optimizer::Parameter *param,
1966
 
                                                      optimizer::SEL_TREE *tree,
 
2281
static optimizer::RangeReadPlan *get_key_scans_params(optimizer::Parameter *param,
 
2282
                                                      SEL_TREE *tree,
1967
2283
                                                      bool index_read_must_be_used,
1968
2284
                                                      bool update_tbl_stats,
1969
2285
                                                      double read_time)
1977
2293
  uint32_t best_buf_size= 0;
1978
2294
  optimizer::RangeReadPlan *read_plan= NULL;
1979
2295
  /*
1980
 
    Note that there may be trees that have type optimizer::SEL_TREE::KEY but contain no
 
2296
    Note that there may be trees that have type SEL_TREE::KEY but contain no
1981
2297
    key reads at all, e.g. tree for expression "key1 is not null" where key1
1982
2298
    is defined as "not null".
1983
2299
  */
 
2300
  print_sel_tree(param, tree, &tree->keys_map, "tree scans");
1984
2301
  tree->ror_scans_map.reset();
1985
2302
  tree->n_ror_scans= 0;
1986
2303
  for (idx= 0,key=tree->keys, end=key+param->keys; key != end; key++,idx++)
1988
2305
    if (*key)
1989
2306
    {
1990
2307
      ha_rows found_records;
1991
 
      optimizer::CostVector cost;
 
2308
      COST_VECT cost;
1992
2309
      double found_read_time= 0.0;
1993
2310
      uint32_t mrr_flags, buf_size;
1994
2311
      uint32_t keynr= param->real_keynr[idx];
1999
2316
      bool read_index_only= index_read_must_be_used ||
2000
2317
                            param->table->covering_keys.test(keynr);
2001
2318
 
2002
 
      found_records= check_quick_select(session, param, idx, read_index_only, *key,
 
2319
      found_records= check_quick_select(param, idx, read_index_only, *key,
2003
2320
                                        update_tbl_stats, &mrr_flags,
2004
2321
                                        &buf_size, &cost);
2005
2322
      found_read_time= cost.total_cost();
2019
2336
    }
2020
2337
  }
2021
2338
 
 
2339
  print_sel_tree(param, tree, &tree->ror_scans_map, "ROR scans");
2022
2340
  if (key_to_read)
2023
2341
  {
2024
2342
    idx= key_to_read - tree->keys;
2028
2346
      read_plan->records= best_records;
2029
2347
      read_plan->is_ror= tree->ror_scans_map.test(idx);
2030
2348
      read_plan->read_cost= read_time;
2031
 
      read_plan->mrr_buf_size= best_buf_size;
 
2349
      read_plan->setMRRBufferSize(best_buf_size);
2032
2350
    }
2033
2351
  }
2034
2352
 
2078
2396
                                                (retrieve_full_rows? (! is_covering) : false),
2079
2397
                                                parent_alloc)))
2080
2398
  {
 
2399
    print_ror_scans_vector(param->table,
 
2400
                           "creating ROR-intersect",
 
2401
                           ror_range_scans);
2081
2402
    alloc= parent_alloc ? parent_alloc : &quick_intersect->alloc;
2082
 
    for (; first_scan != last_scan; ++first_scan)
 
2403
    for (vector<struct st_ror_scan_info *>::iterator it= ror_range_scans.begin();
 
2404
         it != ror_range_scans.end();
 
2405
         ++it)
2083
2406
    {
2084
2407
      if (! (quick= optimizer::get_quick_select(param,
2085
 
                                                (*first_scan)->idx,
2086
 
                                                (*first_scan)->sel_arg,
 
2408
                                                (*it)->idx,
 
2409
                                                (*it)->sel_arg,
2087
2410
                                                HA_MRR_USE_DEFAULT_IMPL | HA_MRR_SORTED,
2088
2411
                                                0,
2089
2412
                                                alloc)) ||
2118
2441
optimizer::QuickSelectInterface *optimizer::RorUnionReadPlan::make_quick(optimizer::Parameter *param, bool, memory::Root *)
2119
2442
{
2120
2443
  optimizer::QuickRorUnionSelect *quick_roru= NULL;
2121
 
  optimizer::TableReadPlan **scan= NULL;
2122
2444
  optimizer::QuickSelectInterface *quick= NULL;
2123
2445
  /*
2124
2446
    It is impossible to construct a ROR-union that will not retrieve full
2126
2448
  */
2127
2449
  if ((quick_roru= new optimizer::QuickRorUnionSelect(param->session, param->table)))
2128
2450
  {
2129
 
    for (scan= first_ror; scan != last_ror; scan++)
 
2451
    for (vector<optimizer::TableReadPlan *>::iterator it= merged_scans.begin();
 
2452
         it != merged_scans.end();
 
2453
         ++it)
2130
2454
    {
2131
 
      if (! (quick= (*scan)->make_quick(param, false, &quick_roru->alloc)) ||
 
2455
      if (! (quick= (*it)->make_quick(param, false, &quick_roru->alloc)) ||
2132
2456
          quick_roru->push_quick_back(quick))
2133
2457
      {
2134
2458
        return NULL;
2142
2466
 
2143
2467
 
2144
2468
/*
2145
 
  Build a optimizer::SEL_TREE for <> or NOT BETWEEN predicate
 
2469
  Build a SEL_TREE for <> or NOT BETWEEN predicate
2146
2470
 
2147
2471
  SYNOPSIS
2148
2472
    get_ne_mm_tree()
2157
2481
    #  Pointer to tree built tree
2158
2482
    0  on error
2159
2483
*/
2160
 
static optimizer::SEL_TREE *get_ne_mm_tree(optimizer::RangeParameter *param,
 
2484
static SEL_TREE *get_ne_mm_tree(optimizer::RangeParameter *param,
2161
2485
                                Item_func *cond_func,
2162
2486
                                Field *field,
2163
2487
                                Item *lt_value, Item *gt_value,
2164
2488
                                Item_result cmp_type)
2165
2489
{
2166
 
  optimizer::SEL_TREE *tree= NULL;
 
2490
  SEL_TREE *tree;
2167
2491
  tree= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
2168
2492
                     lt_value, cmp_type);
2169
2493
  if (tree)
2180
2504
 
2181
2505
 
2182
2506
/*
2183
 
  Build a optimizer::SEL_TREE for a simple predicate
 
2507
  Build a SEL_TREE for a simple predicate
2184
2508
 
2185
2509
  SYNOPSIS
2186
2510
    get_func_mm_tree()
2195
2519
  RETURN
2196
2520
    Pointer to the tree built tree
2197
2521
*/
2198
 
static optimizer::SEL_TREE *get_func_mm_tree(optimizer::RangeParameter *param,
 
2522
static SEL_TREE *get_func_mm_tree(optimizer::RangeParameter *param,
2199
2523
                                  Item_func *cond_func,
2200
2524
                                  Field *field, 
2201
2525
                                  Item *value,
2202
2526
                                  Item_result cmp_type, 
2203
2527
                                  bool inv)
2204
2528
{
2205
 
  optimizer::SEL_TREE *tree= NULL;
 
2529
  SEL_TREE *tree= NULL;
2206
2530
 
2207
2531
  switch (cond_func->functype()) 
2208
2532
  {
2274
2598
      {
2275
2599
        /*
2276
2600
          We get here for conditions in form "t.key NOT IN (c1, c2, ...)",
2277
 
          where c{i} are constants. Our goal is to produce a optimizer::SEL_TREE that
 
2601
          where c{i} are constants. Our goal is to produce a SEL_TREE that
2278
2602
          represents intervals:
2279
2603
 
2280
2604
          ($MIN<t.key<c1) OR (c1<t.key<c2) OR (c2<t.key<c3) OR ...    (*)
2283
2607
 
2284
2608
          The most straightforward way to produce it is to convert NOT IN
2285
2609
          into "(t.key != c1) AND (t.key != c2) AND ... " and let the range
2286
 
          analyzer to build optimizer::SEL_TREE from that. The problem is that the
 
2610
          analyzer to build SEL_TREE from that. The problem is that the
2287
2611
          range analyzer will use O(N^2) memory (which is probably a bug),
2288
2612
          and people do use big NOT IN lists (e.g. see BUG#15872, BUG#21282),
2289
2613
          will run out of memory.
2296
2620
 
2297
2621
          Considering the above, we'll handle NOT IN as follows:
2298
2622
          * if the number of entries in the NOT IN list is less than
2299
 
            NOT_IN_IGNORE_THRESHOLD, construct the optimizer::SEL_TREE (*) manually.
2300
 
          * Otherwise, don't produce a optimizer::SEL_TREE.
 
2623
            NOT_IN_IGNORE_THRESHOLD, construct the SEL_TREE (*) manually.
 
2624
          * Otherwise, don't produce a SEL_TREE.
2301
2625
        */
2302
2626
#define NOT_IN_IGNORE_THRESHOLD 1000
2303
2627
        memory::Root *tmp_root= param->mem_root;
2316
2640
        if (func->array->count > NOT_IN_IGNORE_THRESHOLD || ! value_item)
2317
2641
          break;
2318
2642
 
2319
 
        /* Get a optimizer::SEL_TREE for "(-inf|NULL) < X < c_0" interval.  */
 
2643
        /* Get a SEL_TREE for "(-inf|NULL) < X < c_0" interval.  */
2320
2644
        uint32_t i=0;
2321
2645
        do
2322
2646
        {
2329
2653
          if (! tree)
2330
2654
            break;
2331
2655
          i++;
2332
 
        } while (i < func->array->count && tree->type == optimizer::SEL_TREE::IMPOSSIBLE);
 
2656
        } while (i < func->array->count && tree->type == SEL_TREE::IMPOSSIBLE);
2333
2657
 
2334
 
        if (!tree || tree->type == optimizer::SEL_TREE::IMPOSSIBLE)
 
2658
        if (!tree || tree->type == SEL_TREE::IMPOSSIBLE)
2335
2659
        {
2336
2660
          /* We get here in cases like "t.unsigned NOT IN (-1,-2,-3) */
2337
2661
          tree= NULL;
2338
2662
          break;
2339
2663
        }
2340
 
        optimizer::SEL_TREE *tree2= NULL;
 
2664
        SEL_TREE *tree2;
2341
2665
        for (; i < func->array->count; i++)
2342
2666
        {
2343
2667
          if (func->array->compare_elems(i, i-1))
2344
2668
          {
2345
 
            /* Get a optimizer::SEL_TREE for "-inf < X < c_i" interval */
 
2669
            /* Get a SEL_TREE for "-inf < X < c_i" interval */
2346
2670
            func->array->value_to_item(i, value_item);
2347
2671
            tree2= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
2348
2672
                                value_item, cmp_type);
2372
2696
          }
2373
2697
        }
2374
2698
 
2375
 
        if (tree && tree->type != optimizer::SEL_TREE::IMPOSSIBLE)
 
2699
        if (tree && tree->type != SEL_TREE::IMPOSSIBLE)
2376
2700
        {
2377
2701
          /*
2378
 
            Get the optimizer::SEL_TREE for the last "c_last < X < +inf" interval
 
2702
            Get the SEL_TREE for the last "c_last < X < +inf" interval
2379
2703
            (value_item cotains c_last already)
2380
2704
          */
2381
2705
          tree2= get_mm_parts(param, cond_func, field, Item_func::GT_FUNC,
2439
2763
 
2440
2764
 
2441
2765
/*
2442
 
  Build conjunction of all optimizer::SEL_TREEs for a simple predicate applying equalities
 
2766
  Build conjunction of all SEL_TREEs for a simple predicate applying equalities
2443
2767
 
2444
2768
  SYNOPSIS
2445
2769
    get_full_func_mm_tree()
2454
2778
 
2455
2779
  DESCRIPTION
2456
2780
    For a simple SARGable predicate of the form (f op c), where f is a field and
2457
 
    c is a constant, the function builds a conjunction of all optimizer::SEL_TREES that can
 
2781
    c is a constant, the function builds a conjunction of all SEL_TREES that can
2458
2782
    be obtained by the substitution of f for all different fields equal to f.
2459
2783
 
2460
2784
  NOTES
2464
2788
    each fj belonging to the same multiple equality as fi
2465
2789
    are built as well.
2466
2790
    E.g. for WHERE t1.a=t2.a AND t2.a > 10
2467
 
    a optimizer::SEL_TREE for t2.a > 10 will be built for quick select from t2
 
2791
    a SEL_TREE for t2.a > 10 will be built for quick select from t2
2468
2792
    and
2469
 
    a optimizer::SEL_TREE for t1.a > 10 will be built for quick select from t1.
 
2793
    a SEL_TREE for t1.a > 10 will be built for quick select from t1.
2470
2794
 
2471
2795
    A BETWEEN predicate of the form (fi [NOT] BETWEEN c1 AND c2) is treated
2472
2796
    in a similar way: we build a conjuction of trees for the results
2505
2829
    the form (c IN (c1,...,f,...,cn)).
2506
2830
 
2507
2831
  RETURN
2508
 
    Pointer to the tree representing the built conjunction of optimizer::SEL_TREEs
 
2832
    Pointer to the tree representing the built conjunction of SEL_TREEs
2509
2833
*/
2510
2834
 
2511
 
static optimizer::SEL_TREE *get_full_func_mm_tree(optimizer::RangeParameter *param,
 
2835
static SEL_TREE *get_full_func_mm_tree(optimizer::RangeParameter *param,
2512
2836
                                       Item_func *cond_func,
2513
2837
                                       Item_field *field_item, Item *value,
2514
2838
                                       bool inv)
2515
2839
{
2516
 
  optimizer::SEL_TREE *tree= 0;
2517
 
  optimizer::SEL_TREE *ftree= 0;
 
2840
  SEL_TREE *tree= 0;
 
2841
  SEL_TREE *ftree= 0;
2518
2842
  table_map ref_tables= 0;
2519
2843
  table_map param_comp= ~(param->prev_tables | param->read_tables |
2520
2844
                          param->current_table);
2530
2854
  field->setWriteSet();
2531
2855
 
2532
2856
  Item_result cmp_type= field->cmp_type();
2533
 
  if (!((ref_tables | field->getTable()->map) & param_comp))
 
2857
  if (!((ref_tables | field->table->map) & param_comp))
2534
2858
    ftree= get_func_mm_tree(param, cond_func, field, value, cmp_type, inv);
2535
2859
  Item_equal *item_equal= field_item->item_equal;
2536
2860
  if (item_equal)
2544
2868
 
2545
2869
      if (field->eq(f))
2546
2870
        continue;
2547
 
      if (!((ref_tables | f->getTable()->map) & param_comp))
 
2871
      if (!((ref_tables | f->table->map) & param_comp))
2548
2872
      {
2549
2873
        tree= get_func_mm_tree(param, cond_func, f, value, cmp_type, inv);
2550
2874
        ftree= !ftree ? tree : tree_and(param, ftree, tree);
2556
2880
 
2557
2881
        /* make a select tree of all keys in condition */
2558
2882
 
2559
 
static optimizer::SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond)
 
2883
static SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond)
2560
2884
{
2561
 
  optimizer::SEL_TREE *tree=0;
2562
 
  optimizer::SEL_TREE *ftree= 0;
 
2885
  SEL_TREE *tree=0;
 
2886
  SEL_TREE *ftree= 0;
2563
2887
  Item_field *field_item= 0;
2564
2888
  bool inv= false;
2565
2889
  Item *value= 0;
2574
2898
      Item *item;
2575
2899
      while ((item=li++))
2576
2900
      {
2577
 
        optimizer::SEL_TREE *new_tree= get_mm_tree(param,item);
 
2901
        SEL_TREE *new_tree= get_mm_tree(param,item);
2578
2902
        if (param->session->is_fatal_error ||
2579
2903
            param->alloced_sel_args > optimizer::SEL_ARG::MAX_SEL_ARGS)
2580
2904
          return 0;     // out of memory
2581
2905
        tree=tree_and(param,tree,new_tree);
2582
 
        if (tree && tree->type == optimizer::SEL_TREE::IMPOSSIBLE)
 
2906
        if (tree && tree->type == SEL_TREE::IMPOSSIBLE)
2583
2907
          break;
2584
2908
      }
2585
2909
    }
2591
2915
        Item *item;
2592
2916
        while ((item=li++))
2593
2917
        {
2594
 
          optimizer::SEL_TREE *new_tree= get_mm_tree(param,item);
 
2918
          SEL_TREE *new_tree= get_mm_tree(param,item);
2595
2919
          if (!new_tree)
2596
2920
            return 0;   // out of memory
2597
2921
          tree=tree_or(param,tree,new_tree);
2598
 
          if (!tree || tree->type == optimizer::SEL_TREE::ALWAYS)
 
2922
          if (!tree || tree->type == SEL_TREE::ALWAYS)
2599
2923
            break;
2600
2924
        }
2601
2925
      }
2602
2926
    }
2603
2927
    return(tree);
2604
2928
  }
2605
 
  /* Here when simple cond
2606
 
     There are limits on what kinds of const items we can evaluate, grep for
2607
 
     DontEvaluateMaterializedSubqueryTooEarly.
2608
 
  */
2609
 
  if (cond->const_item()  && !cond->is_expensive())
 
2929
  /* Here when simple cond */
 
2930
  if (cond->const_item())
2610
2931
  {
2611
2932
    /*
2612
2933
      During the cond->val_int() evaluation we can come across a subselect
2616
2937
    */
2617
2938
    memory::Root *tmp_root= param->mem_root;
2618
2939
    param->session->mem_root= param->old_root;
2619
 
    tree= cond->val_int() ? new(tmp_root) optimizer::SEL_TREE(optimizer::SEL_TREE::ALWAYS) :
2620
 
                            new(tmp_root) optimizer::SEL_TREE(optimizer::SEL_TREE::IMPOSSIBLE);
 
2940
    tree= cond->val_int() ? new(tmp_root) SEL_TREE(SEL_TREE::ALWAYS) :
 
2941
                            new(tmp_root) SEL_TREE(SEL_TREE::IMPOSSIBLE);
2621
2942
    param->session->mem_root= tmp_root;
2622
2943
    return(tree);
2623
2944
  }
2631
2952
    if ((ref_tables & param->current_table) ||
2632
2953
        (ref_tables & ~(param->prev_tables | param->read_tables)))
2633
2954
      return 0;
2634
 
    return(new optimizer::SEL_TREE(optimizer::SEL_TREE::MAYBE));
 
2955
    return(new SEL_TREE(SEL_TREE::MAYBE));
2635
2956
  }
2636
2957
 
2637
2958
  Item_func *cond_func= (Item_func*) cond;
2660
2981
      if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM)
2661
2982
      {
2662
2983
        field_item= (Item_field*) (cond_func->arguments()[i]->real_item());
2663
 
        optimizer::SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func,
 
2984
        SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func,
2664
2985
                                    field_item, (Item*)(intptr_t)i, inv);
2665
2986
        if (inv)
2666
2987
          tree= !tree ? tmp : tree_or(param, tree, tmp);
2698
3019
      field->setWriteSet();
2699
3020
 
2700
3021
      Item_result cmp_type= field->cmp_type();
2701
 
      if (!((ref_tables | field->getTable()->map) & param_comp))
 
3022
      if (!((ref_tables | field->table->map) & param_comp))
2702
3023
      {
2703
3024
        tree= get_mm_parts(param, cond, field, Item_func::EQ_FUNC,
2704
3025
                           value,cmp_type);
2730
3051
}
2731
3052
 
2732
3053
 
2733
 
static optimizer::SEL_TREE *
 
3054
static SEL_TREE *
2734
3055
get_mm_parts(optimizer::RangeParameter *param,
2735
3056
             COND *cond_func,
2736
3057
             Field *field,
2737
3058
                   Item_func::Functype type,
2738
3059
                   Item *value, Item_result)
2739
3060
{
2740
 
  if (field->getTable() != param->table)
 
3061
  if (field->table != param->table)
2741
3062
    return 0;
2742
3063
 
2743
3064
  KEY_PART *key_part = param->key_parts;
2744
3065
  KEY_PART *end = param->key_parts_end;
2745
 
  optimizer::SEL_TREE *tree=0;
 
3066
  SEL_TREE *tree=0;
2746
3067
  if (value &&
2747
3068
      value->used_tables() & ~(param->prev_tables | param->read_tables))
2748
3069
    return 0;
2751
3072
    if (field->eq(key_part->field))
2752
3073
    {
2753
3074
      optimizer::SEL_ARG *sel_arg=0;
2754
 
      if (!tree && !(tree=new optimizer::SEL_TREE()))
 
3075
      if (!tree && !(tree=new SEL_TREE()))
2755
3076
        return 0;                               // OOM
2756
3077
      if (!value || !(value->used_tables() & ~param->read_tables))
2757
3078
      {
2761
3082
          continue;
2762
3083
        if (sel_arg->type == optimizer::SEL_ARG::IMPOSSIBLE)
2763
3084
        {
2764
 
          tree->type=optimizer::SEL_TREE::IMPOSSIBLE;
 
3085
          tree->type=SEL_TREE::IMPOSSIBLE;
2765
3086
          return(tree);
2766
3087
        }
2767
3088
      }
2807
3128
  param->session->mem_root= param->old_root;
2808
3129
  if (!value)                                   // IS NULL or IS NOT NULL
2809
3130
  {
2810
 
    if (field->getTable()->maybe_null)          // Can't use a key on this
 
3131
    if (field->table->maybe_null)               // Can't use a key on this
2811
3132
      goto end;
2812
3133
    if (!maybe_null)                            // Not null field
2813
3134
    {
2892
3213
    {
2893
3214
      if (unlikely(length < field_length))
2894
3215
      {
2895
 
        /*
2896
 
          This can only happen in a table created with UNIREG where one key
2897
 
          overlaps many fields
2898
 
        */
2899
 
        length= field_length;
 
3216
        /*
 
3217
          This can only happen in a table created with UNIREG where one key
 
3218
          overlaps many fields
 
3219
        */
 
3220
        length= field_length;
2900
3221
      }
2901
3222
      else
2902
 
        field_length= length;
 
3223
        field_length= length;
2903
3224
    }
2904
3225
    length+=offset;
2905
 
    if (!(min_str= (unsigned char*) alloc->alloc_root(length*2)))
2906
 
    {
 
3226
    if (!(min_str= (unsigned char*) alloc_root(alloc, length*2)))
2907
3227
      goto end;
2908
 
    }
2909
3228
 
2910
3229
    max_str=min_str+length;
2911
3230
    if (maybe_null)
3124
3443
    tree= &optimizer::null_element;                        // cmp with NULL is never true
3125
3444
    goto end;
3126
3445
  }
3127
 
 
3128
 
  /*
3129
 
    Any predicate except "<=>"(null-safe equality operator) involving NULL as a
3130
 
    constant is always FALSE
3131
 
    Put IMPOSSIBLE Tree(null_element) here.
3132
 
  */  
3133
 
  if (type != Item_func::EQUAL_FUNC && field->is_real_null())
3134
 
  {
3135
 
    tree= &optimizer::null_element;
3136
 
    goto end;
3137
 
  }
3138
 
 
3139
 
  str= (unsigned char*) alloc->alloc_root(key_part->store_length+1);
 
3446
  str= (unsigned char*) alloc_root(alloc, key_part->store_length+1);
3140
3447
  if (!str)
3141
3448
    goto end;
3142
3449
  if (maybe_null)
3259
3566
 
3260
3567
#define CLONE_KEY1_MAYBE 1
3261
3568
#define CLONE_KEY2_MAYBE 2
3262
 
 
3263
 
static uint32_t swap_clone_flag(uint32_t a)
3264
 
{
3265
 
  return ((a & 1) << 1) | ((a & 2) >> 1);
3266
 
}
3267
 
 
3268
 
static optimizer::SEL_TREE *
3269
 
tree_and(optimizer::RangeParameter *param, optimizer::SEL_TREE *tree1, optimizer::SEL_TREE *tree2)
 
3569
#define swap_clone_flag(A) ((A & 1) << 1) | ((A & 2) >> 1)
 
3570
 
 
3571
 
 
3572
static SEL_TREE *
 
3573
tree_and(optimizer::RangeParameter *param, SEL_TREE *tree1, SEL_TREE *tree2)
3270
3574
{
3271
3575
  if (!tree1)
3272
3576
    return(tree2);
3273
3577
  if (!tree2)
3274
3578
    return(tree1);
3275
 
  if (tree1->type == optimizer::SEL_TREE::IMPOSSIBLE || tree2->type == optimizer::SEL_TREE::ALWAYS)
 
3579
  if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
3276
3580
    return(tree1);
3277
 
  if (tree2->type == optimizer::SEL_TREE::IMPOSSIBLE || tree1->type == optimizer::SEL_TREE::ALWAYS)
 
3581
  if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
3278
3582
    return(tree2);
3279
 
  if (tree1->type == optimizer::SEL_TREE::MAYBE)
 
3583
  if (tree1->type == SEL_TREE::MAYBE)
3280
3584
  {
3281
 
    if (tree2->type == optimizer::SEL_TREE::KEY)
3282
 
      tree2->type=optimizer::SEL_TREE::KEY_SMALLER;
 
3585
    if (tree2->type == SEL_TREE::KEY)
 
3586
      tree2->type=SEL_TREE::KEY_SMALLER;
3283
3587
    return(tree2);
3284
3588
  }
3285
 
  if (tree2->type == optimizer::SEL_TREE::MAYBE)
 
3589
  if (tree2->type == SEL_TREE::MAYBE)
3286
3590
  {
3287
 
    tree1->type=optimizer::SEL_TREE::KEY_SMALLER;
 
3591
    tree1->type=SEL_TREE::KEY_SMALLER;
3288
3592
    return(tree1);
3289
3593
  }
3290
3594
  key_map  result_keys;
3305
3609
      *key1=key_and(param, *key1, *key2, flag);
3306
3610
      if (*key1 && (*key1)->type == optimizer::SEL_ARG::IMPOSSIBLE)
3307
3611
      {
3308
 
        tree1->type= optimizer::SEL_TREE::IMPOSSIBLE;
 
3612
        tree1->type= SEL_TREE::IMPOSSIBLE;
3309
3613
        return(tree1);
3310
3614
      }
3311
3615
      result_keys.set(key1 - tree1->keys);
3325
3629
}
3326
3630
 
3327
3631
 
 
3632
/*
 
3633
  Check if two SEL_TREES can be combined into one (i.e. a single key range
 
3634
  read can be constructed for "cond_of_tree1 OR cond_of_tree2" ) without
 
3635
  using index_merge.
 
3636
*/
 
3637
 
 
3638
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2,
 
3639
                           optimizer::RangeParameter* param)
 
3640
{
 
3641
  key_map common_keys= tree1->keys_map;
 
3642
  common_keys&= tree2->keys_map;
 
3643
 
 
3644
  if (common_keys.none())
 
3645
    return false;
 
3646
 
 
3647
  /* trees have a common key, check if they refer to same key part */
 
3648
  optimizer::SEL_ARG **key1,**key2;
 
3649
  for (uint32_t key_no=0; key_no < param->keys; key_no++)
 
3650
  {
 
3651
    if (common_keys.test(key_no))
 
3652
    {
 
3653
      key1= tree1->keys + key_no;
 
3654
      key2= tree2->keys + key_no;
 
3655
      if ((*key1)->part == (*key2)->part)
 
3656
      {
 
3657
        return true;
 
3658
      }
 
3659
    }
 
3660
  }
 
3661
  return false;
 
3662
}
 
3663
 
 
3664
 
 
3665
/*
 
3666
  Remove the trees that are not suitable for record retrieval.
 
3667
  SYNOPSIS
 
3668
    param  Range analysis parameter
 
3669
    tree   Tree to be processed, tree->type is KEY or KEY_SMALLER
 
3670
 
 
3671
  DESCRIPTION
 
3672
    This function walks through tree->keys[] and removes the SEL_ARG* trees
 
3673
    that are not "maybe" trees (*) and cannot be used to construct quick range
 
3674
    selects.
 
3675
    (*) - have type MAYBE or MAYBE_KEY. Perhaps we should remove trees of
 
3676
          these types here as well.
 
3677
 
 
3678
    A SEL_ARG* tree cannot be used to construct quick select if it has
 
3679
    tree->part != 0. (e.g. it could represent "keypart2 < const").
 
3680
 
 
3681
    WHY THIS FUNCTION IS NEEDED
 
3682
 
 
3683
    Normally we allow construction of SEL_TREE objects that have SEL_ARG
 
3684
    trees that do not allow quick range select construction. For example for
 
3685
    " keypart1=1 AND keypart2=2 " the execution will proceed as follows:
 
3686
    tree1= SEL_TREE { SEL_ARG{keypart1=1} }
 
3687
    tree2= SEL_TREE { SEL_ARG{keypart2=2} } -- can't make quick range select
 
3688
                                               from this
 
3689
    call tree_and(tree1, tree2) -- this joins SEL_ARGs into a usable SEL_ARG
 
3690
                                   tree.
 
3691
 
 
3692
    There is an exception though: when we construct index_merge SEL_TREE,
 
3693
    any SEL_ARG* tree that cannot be used to construct quick range select can
 
3694
    be removed, because current range analysis code doesn't provide any way
 
3695
    that tree could be later combined with another tree.
 
3696
    Consider an example: we should not construct
 
3697
    st1 = SEL_TREE {
 
3698
      merges = SEL_IMERGE {
 
3699
                            SEL_TREE(t.key1part1 = 1),
 
3700
                            SEL_TREE(t.key2part2 = 2)   -- (*)
 
3701
                          }
 
3702
                   };
 
3703
    because
 
3704
     - (*) cannot be used to construct quick range select,
 
3705
     - There is no execution path that would cause (*) to be converted to
 
3706
       a tree that could be used.
 
3707
 
 
3708
    The latter is easy to verify: first, notice that the only way to convert
 
3709
    (*) into a usable tree is to call tree_and(something, (*)).
 
3710
 
 
3711
    Second look at what tree_and/tree_or function would do when passed a
 
3712
    SEL_TREE that has the structure like st1 tree has, and conlcude that
 
3713
    tree_and(something, (*)) will not be called.
 
3714
 
 
3715
  RETURN
 
3716
    0  Ok, some suitable trees left
 
3717
    1  No tree->keys[] left.
 
3718
*/
 
3719
 
 
3720
static bool remove_nonrange_trees(optimizer::RangeParameter *param, SEL_TREE *tree)
 
3721
{
 
3722
  bool res= false;
 
3723
  for (uint32_t i=0; i < param->keys; i++)
 
3724
  {
 
3725
    if (tree->keys[i])
 
3726
    {
 
3727
      if (tree->keys[i]->part)
 
3728
      {
 
3729
        tree->keys[i]= NULL;
 
3730
        tree->keys_map.reset(i);
 
3731
      }
 
3732
      else
 
3733
        res= true;
 
3734
    }
 
3735
  }
 
3736
  return !res;
 
3737
}
 
3738
 
 
3739
 
 
3740
static SEL_TREE *
 
3741
tree_or(optimizer::RangeParameter *param,SEL_TREE *tree1,SEL_TREE *tree2)
 
3742
{
 
3743
  if (!tree1 || !tree2)
 
3744
    return 0;
 
3745
  if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
 
3746
    return(tree2);
 
3747
  if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
 
3748
    return(tree1);
 
3749
  if (tree1->type == SEL_TREE::MAYBE)
 
3750
    return(tree1);                              // Can't use this
 
3751
  if (tree2->type == SEL_TREE::MAYBE)
 
3752
    return(tree2);
 
3753
 
 
3754
  SEL_TREE *result= 0;
 
3755
  key_map  result_keys;
 
3756
  result_keys.reset();
 
3757
  if (sel_trees_can_be_ored(tree1, tree2, param))
 
3758
  {
 
3759
    /* Join the trees key per key */
 
3760
    optimizer::SEL_ARG **key1,**key2,**end;
 
3761
    for (key1= tree1->keys,key2= tree2->keys,end= key1+param->keys ;
 
3762
         key1 != end ; key1++,key2++)
 
3763
    {
 
3764
      *key1=key_or(param, *key1, *key2);
 
3765
      if (*key1)
 
3766
      {
 
3767
        result=tree1;                           // Added to tree1
 
3768
        result_keys.set(key1 - tree1->keys);
 
3769
      }
 
3770
    }
 
3771
    if (result)
 
3772
      result->keys_map= result_keys;
 
3773
  }
 
3774
  else
 
3775
  {
 
3776
    /* ok, two trees have KEY type but cannot be used without index merge */
 
3777
    if (tree1->merges.is_empty() && tree2->merges.is_empty())
 
3778
    {
 
3779
      if (param->remove_jump_scans)
 
3780
      {
 
3781
        bool no_trees= remove_nonrange_trees(param, tree1);
 
3782
        no_trees= no_trees || remove_nonrange_trees(param, tree2);
 
3783
        if (no_trees)
 
3784
          return(new SEL_TREE(SEL_TREE::ALWAYS));
 
3785
      }
 
3786
      SEL_IMERGE *merge;
 
3787
      /* both trees are "range" trees, produce new index merge structure */
 
3788
      if (!(result= new SEL_TREE()) || !(merge= new SEL_IMERGE()) ||
 
3789
          (result->merges.push_back(merge)) ||
 
3790
          (merge->or_sel_tree(param, tree1)) ||
 
3791
          (merge->or_sel_tree(param, tree2)))
 
3792
        result= NULL;
 
3793
      else
 
3794
        result->type= tree1->type;
 
3795
    }
 
3796
    else if (!tree1->merges.is_empty() && !tree2->merges.is_empty())
 
3797
    {
 
3798
      if (imerge_list_or_list(param, &tree1->merges, &tree2->merges))
 
3799
        result= new SEL_TREE(SEL_TREE::ALWAYS);
 
3800
      else
 
3801
        result= tree1;
 
3802
    }
 
3803
    else
 
3804
    {
 
3805
      /* one tree is index merge tree and another is range tree */
 
3806
      if (tree1->merges.is_empty())
 
3807
        std::swap(tree1, tree2);
 
3808
 
 
3809
      if (param->remove_jump_scans && remove_nonrange_trees(param, tree2))
 
3810
         return(new SEL_TREE(SEL_TREE::ALWAYS));
 
3811
      /* add tree2 to tree1->merges, checking if it collapses to ALWAYS */
 
3812
      if (imerge_list_or_tree(param, &tree1->merges, tree2))
 
3813
        result= new SEL_TREE(SEL_TREE::ALWAYS);
 
3814
      else
 
3815
        result= tree1;
 
3816
    }
 
3817
  }
 
3818
  return result;
 
3819
}
 
3820
 
3328
3821
 
3329
3822
/* And key trees where key1->part < key2 -> part */
3330
3823
 
3521
4014
}
3522
4015
 
3523
4016
 
 
4017
static optimizer::SEL_ARG *
 
4018
key_or(optimizer::RangeParameter *param, optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2)
 
4019
{
 
4020
  if (! key1)
 
4021
  {
 
4022
    if (key2)
 
4023
    {
 
4024
      key2->use_count--;
 
4025
      key2->free_tree();
 
4026
    }
 
4027
    return 0;
 
4028
  }
 
4029
  if (! key2)
 
4030
  {
 
4031
    key1->use_count--;
 
4032
    key1->free_tree();
 
4033
    return 0;
 
4034
  }
 
4035
  key1->use_count--;
 
4036
  key2->use_count--;
 
4037
 
 
4038
  if (key1->part != key2->part)
 
4039
  {
 
4040
    key1->free_tree();
 
4041
    key2->free_tree();
 
4042
    return 0;                                   // Can't optimize this
 
4043
  }
 
4044
 
 
4045
  // If one of the key is MAYBE_KEY then the found region may be bigger
 
4046
  if (key1->type == optimizer::SEL_ARG::MAYBE_KEY)
 
4047
  {
 
4048
    key2->free_tree();
 
4049
    key1->use_count++;
 
4050
    return key1;
 
4051
  }
 
4052
  if (key2->type == optimizer::SEL_ARG::MAYBE_KEY)
 
4053
  {
 
4054
    key1->free_tree();
 
4055
    key2->use_count++;
 
4056
    return key2;
 
4057
  }
 
4058
 
 
4059
  if (key1->use_count > 0)
 
4060
  {
 
4061
    if (key2->use_count == 0 || key1->elements > key2->elements)
 
4062
    {
 
4063
      std::swap(key1,key2);
 
4064
    }
 
4065
    if (key1->use_count > 0 || !(key1=key1->clone_tree(param)))
 
4066
      return 0;                                 // OOM
 
4067
  }
 
4068
 
 
4069
  // Add tree at key2 to tree at key1
 
4070
  bool key2_shared= key2->use_count != 0;
 
4071
  key1->maybe_flag|= key2->maybe_flag;
 
4072
 
 
4073
  for (key2=key2->first(); key2; )
 
4074
  {
 
4075
    optimizer::SEL_ARG *tmp= key1->find_range(key2); // Find key1.min <= key2.min
 
4076
    int cmp;
 
4077
 
 
4078
    if (! tmp)
 
4079
    {
 
4080
      tmp=key1->first(); // tmp.min > key2.min
 
4081
      cmp= -1;
 
4082
    }
 
4083
    else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
 
4084
    {                                           // Found tmp.max < key2.min
 
4085
      optimizer::SEL_ARG *next= tmp->next;
 
4086
      if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part))
 
4087
      {
 
4088
        // Join near ranges like tmp.max < 0 and key2.min >= 0
 
4089
        optimizer::SEL_ARG *key2_next=key2->next;
 
4090
        if (key2_shared)
 
4091
        {
 
4092
          if (! (key2=new optimizer::SEL_ARG(*key2)))
 
4093
            return 0;           // out of memory
 
4094
          key2->increment_use_count(key1->use_count+1);
 
4095
          key2->next= key2_next; // New copy of key2
 
4096
        }
 
4097
        key2->copy_min(tmp);
 
4098
        if (! (key1=key1->tree_delete(tmp)))
 
4099
        {                                       // Only one key in tree
 
4100
          key1= key2;
 
4101
          key1->make_root();
 
4102
          key2= key2_next;
 
4103
          break;
 
4104
        }
 
4105
      }
 
4106
      if (! (tmp= next)) // tmp.min > key2.min
 
4107
        break; // Copy rest of key2
 
4108
    }
 
4109
    if (cmp < 0)
 
4110
    {                                           // tmp.min > key2.min
 
4111
      int tmp_cmp;
 
4112
      if ((tmp_cmp= tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max
 
4113
      {
 
4114
        if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
 
4115
        {                                       // ranges are connected
 
4116
          tmp->copy_min_to_min(key2);
 
4117
          key1->merge_flags(key2);
 
4118
          if (tmp->min_flag & NO_MIN_RANGE &&
 
4119
              tmp->max_flag & NO_MAX_RANGE)
 
4120
          {
 
4121
            if (key1->maybe_flag)
 
4122
              return new optimizer::SEL_ARG(optimizer::SEL_ARG::MAYBE_KEY);
 
4123
            return 0;
 
4124
          }
 
4125
          key2->increment_use_count(-1);        // Free not used tree
 
4126
          key2= key2->next;
 
4127
          continue;
 
4128
        }
 
4129
        else
 
4130
        {
 
4131
          optimizer::SEL_ARG *next= key2->next; // Keys are not overlapping
 
4132
          if (key2_shared)
 
4133
          {
 
4134
            optimizer::SEL_ARG *cpy= new optimizer::SEL_ARG(*key2); // Must make copy
 
4135
            if (! cpy)
 
4136
              return 0; // OOM
 
4137
            key1= key1->insert(cpy);
 
4138
            key2->increment_use_count(key1->use_count+1);
 
4139
          }
 
4140
          else
 
4141
            key1= key1->insert(key2);           // Will destroy key2_root
 
4142
          key2= next;
 
4143
          continue;
 
4144
        }
 
4145
      }
 
4146
    }
 
4147
 
 
4148
    // tmp.max >= key2.min && tmp.min <= key.cmax(overlapping ranges)
 
4149
    if (eq_tree(tmp->next_key_part,key2->next_key_part))
 
4150
    {
 
4151
      if (tmp->is_same(key2))
 
4152
      {
 
4153
        tmp->merge_flags(key2);                 // Copy maybe flags
 
4154
        key2->increment_use_count(-1);          // Free not used tree
 
4155
      }
 
4156
      else
 
4157
      {
 
4158
        optimizer::SEL_ARG *last= tmp;
 
4159
        while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
 
4160
               eq_tree(last->next->next_key_part,key2->next_key_part))
 
4161
        {
 
4162
          optimizer::SEL_ARG *save= last;
 
4163
          last= last->next;
 
4164
          key1= key1->tree_delete(save);
 
4165
        }
 
4166
        last->copy_min(tmp);
 
4167
        if (last->copy_min(key2) || last->copy_max(key2))
 
4168
        {                                       // Full range
 
4169
          key1->free_tree();
 
4170
          for (; key2; key2= key2->next)
 
4171
            key2->increment_use_count(-1);      // Free not used tree
 
4172
          if (key1->maybe_flag)
 
4173
            return new optimizer::SEL_ARG(optimizer::SEL_ARG::MAYBE_KEY);
 
4174
          return 0;
 
4175
        }
 
4176
      }
 
4177
      key2= key2->next;
 
4178
      continue;
 
4179
    }
 
4180
 
 
4181
    if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
 
4182
    {                                           // tmp.min <= x < key2.min
 
4183
      optimizer::SEL_ARG *new_arg= tmp->clone_first(key2);
 
4184
      if (! new_arg)
 
4185
        return 0;                               // OOM
 
4186
      if ((new_arg->next_key_part= key1->next_key_part))
 
4187
        new_arg->increment_use_count(key1->use_count+1);
 
4188
      tmp->copy_min_to_min(key2);
 
4189
      key1= key1->insert(new_arg);
 
4190
    }
 
4191
 
 
4192
    // tmp.min >= key2.min && tmp.min <= key2.max
 
4193
    optimizer::SEL_ARG key(*key2); // Get copy we can modify
 
4194
    for (;;)
 
4195
    {
 
4196
      if (tmp->cmp_min_to_min(&key) > 0)
 
4197
      {                                         // key.min <= x < tmp.min
 
4198
        optimizer::SEL_ARG *new_arg= key.clone_first(tmp);
 
4199
        if (! new_arg)
 
4200
          return 0;                             // OOM
 
4201
        if ((new_arg->next_key_part=key.next_key_part))
 
4202
          new_arg->increment_use_count(key1->use_count+1);
 
4203
        key1= key1->insert(new_arg);
 
4204
      }
 
4205
      if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
 
4206
      {                                         // tmp.min. <= x <= tmp.max
 
4207
        tmp->maybe_flag|= key.maybe_flag;
 
4208
        key.increment_use_count(key1->use_count+1);
 
4209
        tmp->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
 
4210
        if (! cmp)                              // Key2 is ready
 
4211
          break;
 
4212
        key.copy_max_to_min(tmp);
 
4213
        if (! (tmp= tmp->next))
 
4214
        {
 
4215
          optimizer::SEL_ARG *tmp2= new optimizer::SEL_ARG(key);
 
4216
          if (! tmp2)
 
4217
            return 0;                           // OOM
 
4218
          key1= key1->insert(tmp2);
 
4219
          key2= key2->next;
 
4220
          goto end;
 
4221
        }
 
4222
        if (tmp->cmp_min_to_max(&key) > 0)
 
4223
        {
 
4224
          optimizer::SEL_ARG *tmp2= new optimizer::SEL_ARG(key);
 
4225
          if (! tmp2)
 
4226
            return 0;                           // OOM
 
4227
          key1= key1->insert(tmp2);
 
4228
          break;
 
4229
        }
 
4230
      }
 
4231
      else
 
4232
      {
 
4233
        optimizer::SEL_ARG *new_arg= tmp->clone_last(&key); // tmp.min <= x <= key.max
 
4234
        if (! new_arg)
 
4235
          return 0;                             // OOM
 
4236
        tmp->copy_max_to_min(&key);
 
4237
        tmp->increment_use_count(key1->use_count+1);
 
4238
        /* Increment key count as it may be used for next loop */
 
4239
        key.increment_use_count(1);
 
4240
        new_arg->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
 
4241
        key1= key1->insert(new_arg);
 
4242
        break;
 
4243
      }
 
4244
    }
 
4245
    key2= key2->next;
 
4246
  }
 
4247
 
 
4248
end:
 
4249
  while (key2)
 
4250
  {
 
4251
    optimizer::SEL_ARG *next= key2->next;
 
4252
    if (key2_shared)
 
4253
    {
 
4254
      optimizer::SEL_ARG *tmp= new optimizer::SEL_ARG(*key2);           // Must make copy
 
4255
      if (! tmp)
 
4256
        return 0;
 
4257
      key2->increment_use_count(key1->use_count+1);
 
4258
      key1= key1->insert(tmp);
 
4259
    }
 
4260
    else
 
4261
      key1= key1->insert(key2);                 // Will destroy key2_root
 
4262
    key2= next;
 
4263
  }
 
4264
  key1->use_count++;
 
4265
  return key1;
 
4266
}
 
4267
 
 
4268
 
 
4269
/* Compare if two trees are equal */
 
4270
static bool eq_tree(optimizer::SEL_ARG *a, optimizer::SEL_ARG *b)
 
4271
{
 
4272
  if (a == b)
 
4273
  {
 
4274
    return true;
 
4275
  }
 
4276
 
 
4277
  if (! a || ! b || ! a->is_same(b))
 
4278
  {
 
4279
    return false;
 
4280
  }
 
4281
 
 
4282
  if (a->left != &optimizer::null_element && b->left != &optimizer::null_element)
 
4283
  {
 
4284
    if (! eq_tree(a->left,b->left))
 
4285
      return false;
 
4286
  }
 
4287
  else if (a->left != &optimizer::null_element || b->left != &optimizer::null_element)
 
4288
  {
 
4289
    return false;
 
4290
  }
 
4291
 
 
4292
  if (a->right != &optimizer::null_element && b->right != &optimizer::null_element)
 
4293
  {
 
4294
    if (! eq_tree(a->right,b->right))
 
4295
      return false;
 
4296
  }
 
4297
  else if (a->right != &optimizer::null_element || b->right != &optimizer::null_element)
 
4298
  {
 
4299
    return false;
 
4300
  }
 
4301
 
 
4302
  if (a->next_key_part != b->next_key_part)
 
4303
  {                                             // Sub range
 
4304
    if (! a->next_key_part != ! b->next_key_part ||
 
4305
              ! eq_tree(a->next_key_part, b->next_key_part))
 
4306
      return false;
 
4307
  }
 
4308
 
 
4309
  return true;
 
4310
}
 
4311
 
 
4312
 
3524
4313
/****************************************************************************
3525
4314
  MRR Range Sequence Interface implementation that walks a SEL_ARG* tree.
3526
4315
 ****************************************************************************/
3551
4340
*/
3552
4341
typedef struct st_sel_arg_range_seq
3553
4342
{
3554
 
  uint32_t keyno;      /* index of used tree in optimizer::SEL_TREE structure */
 
4343
  uint32_t keyno;      /* index of used tree in SEL_TREE structure */
3555
4344
  uint32_t real_keyno; /* Number of the index in tables */
3556
4345
  optimizer::Parameter *param;
3557
4346
  optimizer::SEL_ARG *start; /* Root node of the traversed SEL_ARG* graph */
3739
4528
  /* Ok got a tuple */
3740
4529
  RANGE_SEQ_ENTRY *cur= &seq->stack[seq->i];
3741
4530
 
3742
 
  range->ptr= (char*)(size_t)(key_tree->part);
 
4531
  range->ptr= (char*)(int)(key_tree->part);
3743
4532
  {
3744
4533
    range->range_flag= cur->min_key_flag | cur->max_key_flag;
3745
4534
 
3793
4582
  SYNOPSIS
3794
4583
    check_quick_select()
3795
4584
      param             Parameter from test_quick_select
3796
 
      idx               Number of index to use in Parameter::key optimizer::SEL_TREE::key
 
4585
      idx               Number of index to use in Parameter::key SEL_TREE::key
3797
4586
      index_only        true  - assume only index tuples will be accessed
3798
4587
                        false - assume full table rows will be read
3799
4588
      tree              Transformed selection condition, tree->key[idx] holds
3815
4604
*/
3816
4605
 
3817
4606
static
3818
 
ha_rows check_quick_select(Session *session,
3819
 
                           optimizer::Parameter *param,
 
4607
ha_rows check_quick_select(optimizer::Parameter *param,
3820
4608
                           uint32_t idx,
3821
4609
                           bool index_only,
3822
4610
                           optimizer::SEL_ARG *tree,
3823
4611
                           bool update_tbl_stats,
3824
4612
                           uint32_t *mrr_flags,
3825
4613
                           uint32_t *bufsize,
3826
 
                           optimizer::CostVector *cost)
 
4614
                           COST_VECT *cost)
3827
4615
{
3828
4616
  SEL_ARG_RANGE_SEQ seq;
3829
4617
  RANGE_SEQ_IF seq_if = {sel_arg_range_seq_init, sel_arg_range_seq_next};
3857
4645
  bool pk_is_clustered= cursor->primary_key_is_clustered();
3858
4646
  if (index_only &&
3859
4647
      (param->table->index_flags(keynr) & HA_KEYREAD_ONLY) &&
3860
 
      !(pk_is_clustered && keynr == param->table->getShare()->getPrimaryKey()))
 
4648
      !(pk_is_clustered && keynr == param->table->s->primary_key))
3861
4649
     *mrr_flags |= HA_MRR_INDEX_ONLY;
3862
4650
 
3863
 
  if (session->lex->sql_command != SQLCOM_SELECT)
 
4651
  if (current_session->lex->sql_command != SQLCOM_SELECT)
3864
4652
    *mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
3865
4653
 
3866
4654
  *bufsize= param->session->variables.read_rnd_buff_size;
3892
4680
  else
3893
4681
  {
3894
4682
    /* Clustered PK scan is always a ROR scan (TODO: same as above) */
3895
 
    if (param->table->getShare()->getPrimaryKey() == keynr && pk_is_clustered)
 
4683
    if (param->table->s->primary_key == keynr && pk_is_clustered)
3896
4684
      param->is_ror_scan= true;
3897
4685
  }
3898
4686
 
3939
4727
 
3940
4728
static bool is_key_scan_ror(optimizer::Parameter *param, uint32_t keynr, uint8_t nparts)
3941
4729
{
3942
 
  KeyInfo *table_key= param->table->key_info + keynr;
3943
 
  KeyPartInfo *key_part= table_key->key_part + nparts;
3944
 
  KeyPartInfo *key_part_end= (table_key->key_part +
 
4730
  KEY *table_key= param->table->key_info + keynr;
 
4731
  KEY_PART_INFO *key_part= table_key->key_part + nparts;
 
4732
  KEY_PART_INFO *key_part_end= (table_key->key_part +
3945
4733
                                table_key->key_parts);
3946
4734
  uint32_t pk_number;
3947
4735
 
3948
 
  for (KeyPartInfo *kp= table_key->key_part; kp < key_part; kp++)
 
4736
  for (KEY_PART_INFO *kp= table_key->key_part; kp < key_part; kp++)
3949
4737
  {
3950
4738
    uint16_t fieldnr= param->table->key_info[keynr].
3951
4739
                    key_part[kp - table_key->key_part].fieldnr - 1;
3952
 
    if (param->table->getField(fieldnr)->key_length() != kp->length)
 
4740
    if (param->table->field[fieldnr]->key_length() != kp->length)
3953
4741
      return false;
3954
4742
  }
3955
4743
 
3957
4745
    return true;
3958
4746
 
3959
4747
  key_part= table_key->key_part + nparts;
3960
 
  pk_number= param->table->getShare()->getPrimaryKey();
 
4748
  pk_number= param->table->s->primary_key;
3961
4749
  if (!param->table->cursor->primary_key_is_clustered() || pk_number == MAX_KEY)
3962
4750
    return false;
3963
4751
 
3964
 
  KeyPartInfo *pk_part= param->table->key_info[pk_number].key_part;
3965
 
  KeyPartInfo *pk_part_end= pk_part +
 
4752
  KEY_PART_INFO *pk_part= param->table->key_info[pk_number].key_part;
 
4753
  KEY_PART_INFO *pk_part_end= pk_part +
3966
4754
                              param->table->key_info[pk_number].key_parts;
3967
4755
  for (;(key_part!=key_part_end) && (pk_part != pk_part_end);
3968
4756
       ++key_part, ++pk_part)
3983
4771
                            uint32_t mrr_buf_size,
3984
4772
                            memory::Root *parent_alloc)
3985
4773
{
3986
 
  optimizer::QuickRangeSelect *quick= new optimizer::QuickRangeSelect(param->session,
3987
 
                                                                      param->table,
3988
 
                                                                      param->real_keynr[idx],
3989
 
                                                                      test(parent_alloc),
3990
 
                                                                      NULL);
 
4774
  optimizer::QuickRangeSelect *quick= NULL;
 
4775
  bool create_err= false;
 
4776
 
 
4777
  quick= new optimizer::QuickRangeSelect(param->session,
 
4778
                                         param->table,
 
4779
                                         param->real_keynr[idx],
 
4780
                                         test(parent_alloc),
 
4781
                                         NULL,
 
4782
                                         &create_err);
3991
4783
 
3992
4784
  if (quick)
3993
4785
  {
3994
 
          if (get_quick_keys(param,
 
4786
    if (create_err ||
 
4787
              get_quick_keys(param,
3995
4788
                       quick,
3996
4789
                       param->key[idx],
3997
4790
                       key_tree,
4007
4800
    {
4008
4801
      quick->mrr_flags= mrr_flags;
4009
4802
      quick->mrr_buf_size= mrr_buf_size;
4010
 
      if (parent_alloc)
4011
 
      {
4012
 
        quick->key_parts=(KEY_PART*)
4013
 
          parent_alloc->memdup_root( (char*) param->key[idx], sizeof(KEY_PART)* param->table->key_info[param->real_keynr[idx]].key_parts);
4014
 
      }
4015
 
      else
4016
 
      {
4017
 
        quick->key_parts=(KEY_PART*)
4018
 
          quick->alloc.memdup_root((char*) param->key[idx], sizeof(KEY_PART)* param->table->key_info[param->real_keynr[idx]].key_parts);
4019
 
      }
 
4803
      quick->key_parts=(KEY_PART*)
 
4804
        memdup_root(parent_alloc? parent_alloc : &quick->alloc,
 
4805
                    (char*) param->key[idx],
 
4806
                    sizeof(KEY_PART)*
 
4807
                    param->table->key_info[param->real_keynr[idx]].key_parts);
4020
4808
    }
4021
4809
  }
4022
4810
  return quick;
4130
4918
    if (length == (uint32_t) (tmp_max_key - param->max_key) &&
4131
4919
              ! memcmp(param->min_key,param->max_key,length))
4132
4920
    {
4133
 
      KeyInfo *table_key= quick->head->key_info+quick->index;
 
4921
      KEY *table_key= quick->head->key_info+quick->index;
4134
4922
      flag= EQ_RANGE;
4135
4923
      if ((table_key->flags & (HA_NOSAME)) == HA_NOSAME &&
4136
4924
                key->part == table_key->key_parts-1)
4212
5000
}
4213
5001
 
4214
5002
 
4215
 
bool optimizer::QuickSelectInterface::is_keys_used(const boost::dynamic_bitset<>& fields)
 
5003
bool optimizer::QuickSelectInterface::is_keys_used(const MyBitmap *fields)
4216
5004
{
4217
5005
  return is_key_used(head, index, fields);
4218
5006
}
4242
5030
                                                                 table_reference_st *ref,
4243
5031
                                                                 ha_rows records)
4244
5032
{
4245
 
  memory::Root *old_root= NULL;
4246
 
  memory::Root *alloc= NULL;
4247
 
  KeyInfo *key_info = &table->key_info[ref->key];
 
5033
  memory::Root *old_root, *alloc;
 
5034
  optimizer::QuickRangeSelect *quick= NULL;
 
5035
  KEY *key_info = &table->key_info[ref->key];
4248
5036
  KEY_PART *key_part;
4249
5037
  optimizer::QuickRange *range= NULL;
4250
5038
  uint32_t part;
4251
 
  optimizer::CostVector cost;
 
5039
  bool create_err= false;
 
5040
  COST_VECT cost;
4252
5041
 
4253
5042
  old_root= session->mem_root;
4254
5043
  /* The following call may change session->mem_root */
4255
 
  optimizer::QuickRangeSelect *quick= new optimizer::QuickRangeSelect(session, table, ref->key, 0, 0);
 
5044
  quick= new optimizer::QuickRangeSelect(session, table, ref->key, 0, 0, &create_err);
4256
5045
  /* save mem_root set by QuickRangeSelect constructor */
4257
5046
  alloc= session->mem_root;
4258
5047
  /*
4261
5050
  */
4262
5051
  session->mem_root= old_root;
4263
5052
 
4264
 
  if (! quick)
 
5053
  if (!quick || create_err)
4265
5054
    return 0;                   /* no ranges found */
4266
5055
  if (quick->init())
4267
5056
    goto err;
4280
5069
 
4281
5070
 
4282
5071
  if (!(quick->key_parts=key_part=(KEY_PART *)
4283
 
        quick->alloc.alloc_root(sizeof(KEY_PART)*ref->key_parts)))
 
5072
        alloc_root(&quick->alloc,sizeof(KEY_PART)*ref->key_parts)))
4284
5073
    goto err;
4285
5074
 
4286
5075
  for (part=0 ; part < ref->key_parts ;part++,key_part++)
4325
5114
 
4326
5115
  quick->mrr_buf_size= session->variables.read_rnd_buff_size;
4327
5116
  if (table->cursor->multi_range_read_info(quick->index, 1, (uint32_t)records,
4328
 
                                           &quick->mrr_buf_size,
4329
 
                                           &quick->mrr_flags, &cost))
 
5117
                                         &quick->mrr_buf_size,
 
5118
                                         &quick->mrr_flags, &cost))
4330
5119
    goto err;
4331
5120
 
4332
5121
  return quick;
4404
5193
}
4405
5194
 
4406
5195
 
4407
 
static inline uint32_t get_field_keypart(KeyInfo *index, Field *field);
 
5196
static inline uint32_t get_field_keypart(KEY *index, Field *field);
4408
5197
 
4409
5198
static inline optimizer::SEL_ARG * get_index_range_tree(uint32_t index,
4410
 
                                                        optimizer::SEL_TREE *range_tree,
 
5199
                                                        SEL_TREE *range_tree,
4411
5200
                                                        optimizer::Parameter *param,
4412
5201
                                                        uint32_t *param_idx);
4413
5202
 
4414
 
static bool get_constant_key_infix(KeyInfo *index_info,
 
5203
static bool get_constant_key_infix(KEY *index_info,
4415
5204
                                   optimizer::SEL_ARG *index_range_tree,
4416
 
                                   KeyPartInfo *first_non_group_part,
4417
 
                                   KeyPartInfo *min_max_arg_part,
4418
 
                                   KeyPartInfo *last_part,
 
5205
                                   KEY_PART_INFO *first_non_group_part,
 
5206
                                   KEY_PART_INFO *min_max_arg_part,
 
5207
                                   KEY_PART_INFO *last_part,
4419
5208
                                   Session *session,
4420
5209
                                   unsigned char *key_infix,
4421
5210
                                   uint32_t *key_infix_len,
4422
 
                                   KeyPartInfo **first_non_infix_part);
 
5211
                                   KEY_PART_INFO **first_non_infix_part);
4423
5212
 
4424
5213
static bool check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item);
4425
5214
 
4426
5215
static void
4427
5216
cost_group_min_max(Table* table,
4428
 
                   KeyInfo *index_info,
 
5217
                   KEY *index_info,
4429
5218
                   uint32_t used_key_parts,
4430
5219
                   uint32_t group_key_parts,
4431
 
                   optimizer::SEL_TREE *range_tree,
 
5220
                   SEL_TREE *range_tree,
4432
5221
                   optimizer::SEL_ARG *index_tree,
4433
5222
                   ha_rows quick_prefix_records,
4434
5223
                   bool have_min,
4565
5354
    - NULL
4566
5355
*/
4567
5356
static optimizer::GroupMinMaxReadPlan *
4568
 
get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree)
 
5357
get_best_group_min_max(optimizer::Parameter *param, SEL_TREE *tree)
4569
5358
{
4570
5359
  Session *session= param->session;
4571
 
  Join *join= session->lex->current_select->join;
 
5360
  JOIN *join= session->lex->current_select->join;
4572
5361
  Table *table= param->table;
4573
5362
  bool have_min= false;              /* true if there is a MIN function. */
4574
5363
  bool have_max= false;              /* true if there is a MAX function. */
4575
5364
  Item_field *min_max_arg_item= NULL; // The argument of all MIN/MAX functions
4576
 
  KeyPartInfo *min_max_arg_part= NULL; /* The corresponding keypart. */
 
5365
  KEY_PART_INFO *min_max_arg_part= NULL; /* The corresponding keypart. */
4577
5366
  uint32_t group_prefix_len= 0; /* Length (in bytes) of the key prefix. */
4578
 
  KeyInfo *index_info= NULL;    /* The index chosen for data access. */
 
5367
  KEY *index_info= NULL;    /* The index chosen for data access. */
4579
5368
  uint32_t index= 0;            /* The id of the chosen index. */
4580
5369
  uint32_t group_key_parts= 0;  // Number of index key parts in the group prefix.
4581
5370
  uint32_t used_key_parts= 0;   /* Number of index key parts used for access. */
4583
5372
  uint32_t key_infix_len= 0;          /* Length of key_infix. */
4584
5373
  optimizer::GroupMinMaxReadPlan *read_plan= NULL; /* The eventually constructed TRP. */
4585
5374
  uint32_t key_part_nr;
4586
 
  Order *tmp_group= NULL;
 
5375
  order_st *tmp_group= NULL;
4587
5376
  Item *item= NULL;
4588
5377
  Item_field *item_field= NULL;
4589
5378
 
4596
5385
       (! join->select_distinct)) ||
4597
5386
      (join->select_lex->olap == ROLLUP_TYPE)) /* Check (B3) for ROLLUP */
4598
5387
    return NULL;
4599
 
  if (table->getShare()->sizeKeys() == 0)        /* There are no indexes to use. */
 
5388
  if (table->s->keys == 0)        /* There are no indexes to use. */
4600
5389
    return NULL;
4601
5390
 
4602
5391
  /* Analyze the query in more detail. */
4655
5444
    (GA1,GA2) are all true. If there is more than one such index, select the
4656
5445
    first one. Here we set the variables: group_prefix_len and index_info.
4657
5446
  */
4658
 
  KeyInfo *cur_index_info= table->key_info;
4659
 
  KeyInfo *cur_index_info_end= cur_index_info + table->getShare()->sizeKeys();
4660
 
  KeyPartInfo *cur_part= NULL;
4661
 
  KeyPartInfo *end_part= NULL; /* Last part for loops. */
 
5447
  KEY *cur_index_info= table->key_info;
 
5448
  KEY *cur_index_info_end= cur_index_info + table->s->keys;
 
5449
  KEY_PART_INFO *cur_part= NULL;
 
5450
  KEY_PART_INFO *end_part= NULL; /* Last part for loops. */
4662
5451
  /* Last index part. */
4663
 
  KeyPartInfo *last_part= NULL;
4664
 
  KeyPartInfo *first_non_group_part= NULL;
4665
 
  KeyPartInfo *first_non_infix_part= NULL;
 
5452
  KEY_PART_INFO *last_part= NULL;
 
5453
  KEY_PART_INFO *first_non_group_part= NULL;
 
5454
  KEY_PART_INFO *first_non_infix_part= NULL;
4666
5455
  uint32_t key_infix_parts= 0;
4667
5456
  uint32_t cur_group_key_parts= 0;
4668
5457
  uint32_t cur_group_prefix_len= 0;
4681
5470
  uint32_t cur_key_infix_len= 0;
4682
5471
  unsigned char cur_key_infix[MAX_KEY_LENGTH];
4683
5472
  uint32_t cur_used_key_parts= 0;
4684
 
  uint32_t pk= param->table->getShare()->getPrimaryKey();
 
5473
  uint32_t pk= param->table->s->primary_key;
4685
5474
 
4686
5475
  for (uint32_t cur_index= 0;
4687
5476
       cur_index_info != cur_index_info_end;
4704
5493
        (table->cursor->getEngine()->check_flag(HTON_BIT_PRIMARY_KEY_IN_READ_INDEX)))
4705
5494
    {
4706
5495
      /* For each table field */
4707
 
      for (uint32_t i= 0; i < table->getShare()->sizeFields(); i++)
 
5496
      for (uint32_t i= 0; i < table->s->fields; i++)
4708
5497
      {
4709
 
        Field *cur_field= table->getField(i);
 
5498
        Field *cur_field= table->field[i];
4710
5499
        /*
4711
5500
          If the field is used in the current query ensure that it's
4712
5501
          part of 'cur_index'
4874
5663
          Store the first and last keyparts that need to be analyzed
4875
5664
          into one array that can be passed as parameter.
4876
5665
        */
4877
 
        KeyPartInfo *key_part_range[2];
 
5666
        KEY_PART_INFO *key_part_range[2];
4878
5667
        key_part_range[0]= first_non_group_part;
4879
5668
        key_part_range[1]= last_part;
4880
5669
 
4915
5704
                                           param,
4916
5705
                                           &cur_param_idx);
4917
5706
      /* Check if this range tree can be used for prefix retrieval. */
4918
 
      optimizer::CostVector dummy_cost;
 
5707
      COST_VECT dummy_cost;
4919
5708
      uint32_t mrr_flags= HA_MRR_USE_DEFAULT_IMPL;
4920
5709
      uint32_t mrr_bufsize= 0;
4921
 
      cur_quick_prefix_records= check_quick_select(session,
4922
 
                                                   param,
 
5710
      cur_quick_prefix_records= check_quick_select(param,
4923
5711
                                                   cur_param_idx,
4924
5712
                                                   false /*don't care*/,
4925
5713
                                                   cur_index_tree,
5167
5955
    false o/w
5168
5956
*/
5169
5957
static bool
5170
 
get_constant_key_infix(KeyInfo *,
 
5958
get_constant_key_infix(KEY *,
5171
5959
                       optimizer::SEL_ARG *index_range_tree,
5172
 
                       KeyPartInfo *first_non_group_part,
5173
 
                       KeyPartInfo *min_max_arg_part,
5174
 
                       KeyPartInfo *last_part,
 
5960
                       KEY_PART_INFO *first_non_group_part,
 
5961
                       KEY_PART_INFO *min_max_arg_part,
 
5962
                       KEY_PART_INFO *last_part,
5175
5963
                       Session *,
5176
5964
                       unsigned char *key_infix,
5177
5965
                       uint32_t *key_infix_len,
5178
 
                       KeyPartInfo **first_non_infix_part)
 
5966
                       KEY_PART_INFO **first_non_infix_part)
5179
5967
{
5180
5968
  optimizer::SEL_ARG *cur_range= NULL;
5181
 
  KeyPartInfo *cur_part= NULL;
 
5969
  KEY_PART_INFO *cur_part= NULL;
5182
5970
  /* End part for the first loop below. */
5183
 
  KeyPartInfo *end_part= min_max_arg_part ? min_max_arg_part : last_part;
 
5971
  KEY_PART_INFO *end_part= min_max_arg_part ? min_max_arg_part : last_part;
5184
5972
 
5185
5973
  *key_infix_len= 0;
5186
5974
  unsigned char *key_ptr= key_infix;
5246
6034
    field  field that possibly references some key part in index
5247
6035
 
5248
6036
  NOTES
5249
 
    The return value can be used to get a KeyPartInfo pointer by
 
6037
    The return value can be used to get a KEY_PART_INFO pointer by
5250
6038
    part= index->key_part + get_field_keypart(...) - 1;
5251
6039
 
5252
6040
  RETURN
5254
6042
    0 if field does not reference any index field.
5255
6043
*/
5256
6044
static inline uint
5257
 
get_field_keypart(KeyInfo *index, Field *field)
 
6045
get_field_keypart(KEY *index, Field *field)
5258
6046
{
5259
 
  KeyPartInfo *part= NULL;
5260
 
  KeyPartInfo *end= NULL;
 
6047
  KEY_PART_INFO *part= NULL;
 
6048
  KEY_PART_INFO *end= NULL;
5261
6049
 
5262
6050
  for (part= index->key_part, end= part + index->key_parts; part < end; part++)
5263
6051
  {
5280
6068
 
5281
6069
  DESCRIPTION
5282
6070
 
5283
 
    A optimizer::SEL_TREE contains range trees for all usable indexes. This procedure
5284
 
    finds the SEL_ARG sub-tree for 'index'. The members of a optimizer::SEL_TREE are
 
6071
    A SEL_TREE contains range trees for all usable indexes. This procedure
 
6072
    finds the SEL_ARG sub-tree for 'index'. The members of a SEL_TREE are
5285
6073
    ordered in the same way as the members of Parameter::key, thus we first find
5286
6074
    the corresponding index in the array Parameter::key. This index is returned
5287
6075
    through the variable param_idx, to be used later as argument of
5291
6079
    Pointer to the SEL_ARG subtree that corresponds to index.
5292
6080
*/
5293
6081
optimizer::SEL_ARG *get_index_range_tree(uint32_t index,
5294
 
                                         optimizer::SEL_TREE* range_tree,
 
6082
                                         SEL_TREE* range_tree,
5295
6083
                                         optimizer::Parameter *param,
5296
6084
                                         uint32_t *param_idx)
5297
6085
{
5367
6155
    None
5368
6156
*/
5369
6157
void cost_group_min_max(Table* table,
5370
 
                        KeyInfo *index_info,
 
6158
                        KEY *index_info,
5371
6159
                        uint32_t used_key_parts,
5372
6160
                        uint32_t group_key_parts,
5373
 
                        optimizer::SEL_TREE *range_tree,
 
6161
                        SEL_TREE *range_tree,
5374
6162
                        optimizer::SEL_ARG *,
5375
6163
                        ha_rows quick_prefix_records,
5376
6164
                        bool have_min,
5572
6360
}
5573
6361
 
5574
6362
 
5575
 
uint32_t optimizer::RorScanInfo::findFirstNotSet() const
 
6363
static void print_sel_tree(optimizer::Parameter *param, SEL_TREE *tree, key_map *tree_map, const char *)
5576
6364
{
5577
 
  boost::dynamic_bitset<> map= bitsToBitset();
5578
 
  for (boost::dynamic_bitset<>::size_type i= 0; i < map.size(); i++)
 
6365
  optimizer::SEL_ARG **key= NULL;
 
6366
  optimizer::SEL_ARG **end= NULL;
 
6367
  int idx= 0;
 
6368
  char buff[1024];
 
6369
 
 
6370
  String tmp(buff,sizeof(buff),&my_charset_bin);
 
6371
  tmp.length(0);
 
6372
  for (idx= 0, key=tree->keys, end= key + param->keys;
 
6373
       key != end;
 
6374
       key++, idx++)
5579
6375
  {
5580
 
    if (! map.test(i))
 
6376
    if (tree_map->test(idx))
5581
6377
    {
5582
 
      return i;
 
6378
      uint32_t keynr= param->real_keynr[idx];
 
6379
      if (tmp.length())
 
6380
        tmp.append(',');
 
6381
      tmp.append(param->table->key_info[keynr].name);
5583
6382
    }
5584
6383
  }
5585
 
  return map.size();
5586
 
}
5587
 
 
5588
 
 
5589
 
size_t optimizer::RorScanInfo::getBitCount() const
5590
 
{
5591
 
  boost::dynamic_bitset<> tmp_bitset= bitsToBitset();
5592
 
  return tmp_bitset.count();
5593
 
}
5594
 
 
5595
 
 
5596
 
void optimizer::RorScanInfo::subtractBitset(const boost::dynamic_bitset<>& in_bitset)
5597
 
{
5598
 
  boost::dynamic_bitset<> tmp_bitset= bitsToBitset();
5599
 
  tmp_bitset-= in_bitset;
5600
 
  covered_fields= tmp_bitset.to_ulong();
5601
 
}
5602
 
 
5603
 
 
5604
 
boost::dynamic_bitset<> optimizer::RorScanInfo::bitsToBitset() const
5605
 
{
5606
 
  string res;
5607
 
  uint64_t conv= covered_fields;
5608
 
  while (conv)
5609
 
  {
5610
 
    res.push_back((conv & 1) + '0');
5611
 
    conv>>= 1;
5612
 
  }
5613
 
  if (! res.empty())
5614
 
  {
5615
 
    std::reverse(res.begin(), res.end());
5616
 
  }
5617
 
  string final(covered_fields_size - res.length(), '0');
5618
 
  final.append(res);
5619
 
  return (boost::dynamic_bitset<>(final));
5620
 
}
5621
 
 
 
6384
  if (! tmp.length())
 
6385
    tmp.append(STRING_WITH_LEN("(empty)"));
 
6386
}
 
6387
 
 
6388
 
 
6389
static void print_ror_scans_arr(Table *table,
 
6390
                                const char *,
 
6391
                                struct st_ror_scan_info **start,
 
6392
                                struct st_ror_scan_info **end)
 
6393
{
 
6394
  char buff[1024];
 
6395
  String tmp(buff,sizeof(buff),&my_charset_bin);
 
6396
  tmp.length(0);
 
6397
  for (; start != end; start++)
 
6398
  {
 
6399
    if (tmp.length())
 
6400
      tmp.append(',');
 
6401
    tmp.append(table->key_info[(*start)->keynr].name);
 
6402
  }
 
6403
  if (! tmp.length())
 
6404
    tmp.append(STRING_WITH_LEN("(empty)"));
 
6405
}
 
6406
 
 
6407
static void print_ror_scans_vector(Table *table,
 
6408
                                   const char *,
 
6409
                                   vector<struct st_ror_scan_info *> &vec)
 
6410
{
 
6411
  char buff[1024];
 
6412
  String tmp(buff,sizeof(buff),&my_charset_bin);
 
6413
  tmp.length(0);
 
6414
  for (vector<struct st_ror_scan_info *>::iterator it= vec.begin();
 
6415
       it != vec.end();
 
6416
       ++it)
 
6417
  {
 
6418
    if (tmp.length())
 
6419
      tmp.append(',');
 
6420
    tmp.append(table->key_info[(*it)->keynr].name);
 
6421
  }
 
6422
  if (! tmp.length())
 
6423
    tmp.append(STRING_WITH_LEN("(empty)"));
 
6424
}
5622
6425
 
5623
6426
} /* namespace drizzled */