← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/optimizer/range.h

Split some classes from the range optimizer out in to their own header and implementation files.
Corrected the case on these classes also to adhere to the coding standards. Cleaned up any style
issues in any code I came across while moving code.

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/optimizer/range.h
58
58
namespace optimizer
59
59
{
60
60
 
61
 
class QuickRange : public Sql_alloc 
62
 
{
63
 
public:
64
 
  unsigned char *min_key;
65
 
  unsigned char *max_key;
66
 
  uint16_t min_length;
67
 
  uint16_t max_length;
68
 
  uint16_t flag;
69
 
  key_part_map min_keypart_map; /**< bitmap of used keyparts in min_key */
70
 
  key_part_map max_keypart_map; /**< bitmap of used keyparts in max_key */
71
 
 
72
 
  QuickRange(); /**< Constructor for a "full range" */
73
 
  QuickRange(const unsigned char *min_key_arg,
74
 
              uint32_t min_length_arg,
75
 
              key_part_map min_keypart_map_arg,
76
 
                    const unsigned char *max_key_arg, 
77
 
              uint32_t max_length_arg,
78
 
              key_part_map max_keypart_map_arg,
79
 
                    uint32_t flag_arg)
80
 
    : 
81
 
      min_key((unsigned char*) sql_memdup(min_key_arg,min_length_arg+1)),
82
 
      max_key((unsigned char*) sql_memdup(max_key_arg,max_length_arg+1)),
83
 
      min_length((uint16_t) min_length_arg),
84
 
      max_length((uint16_t) max_length_arg),
85
 
      flag((uint16_t) flag_arg),
86
 
      min_keypart_map(min_keypart_map_arg),
87
 
      max_keypart_map(max_keypart_map_arg)
88
 
    {}
89
 
};
90
 
 
91
61
/**
92
62
  Quick select interface.
93
63
  This class is a parent for all QUICK_*_SELECT classes.
285
255
};
286
256
 
287
257
struct st_qsel_param;
 
258
class QuickRange;
 
259
class QuickRangeSelect;
288
260
 
289
261
/**
290
262
 * MRR range sequence, array<QuickRange> implementation: sequence traversal
301
273
 
302
274
uint32_t quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range);
303
275
 
304
 
/**
305
 
 * Quick select that does a range scan on a single key. 
306
 
 *
307
 
 * The records are returned in key order.
308
 
 * 
309
 
 */
310
 
class QuickRangeSelect : public QuickSelectInterface
311
 
{
312
 
protected:
313
 
  Cursor *cursor;
314
 
  DYNAMIC_ARRAY ranges; /**< ordered array of range ptrs */
315
 
 
316
 
  /** Members to deal with case when this quick select is a ROR-merged scan */
317
 
  bool in_ror_merged_scan;
318
 
  MyBitmap column_bitmap;
319
 
  MyBitmap *save_read_set;
320
 
  MyBitmap *save_write_set;
321
 
  bool free_file; /**< True when this->file is "owned" by this quick select */
322
 
 
323
 
  /* Range pointers to be used when not using MRR interface */
324
 
  QuickRange **cur_range; /**< current element in ranges  */
325
 
  QuickRange *last_range;
326
 
 
327
 
  /** Members needed to use the MRR interface */
328
 
  QuickRangeSequenceContext qr_traversal_ctx;
329
 
  uint32_t mrr_buf_size; /**< copy from session->variables.read_rnd_buff_size */
330
 
  HANDLER_BUFFER *mrr_buf_desc; /**< the Cursor buffer */
331
 
 
332
 
  /** Info about index we're scanning */
333
 
  KEY_PART *key_parts;
334
 
  KEY_PART_INFO *key_part_info;
335
 
 
336
 
  bool dont_free; /**< Used by QUICK_SELECT_DESC */
337
 
 
338
 
  int cmp_next(QuickRange *range);
339
 
  int cmp_prev(QuickRange *range);
340
 
  bool row_in_ranges();
341
 
public:
342
 
  uint32_t mrr_flags; /**< Flags to be used with MRR interface */
343
 
  MEM_ROOT alloc;
344
 
 
345
 
  QuickRangeSelect(Session *session,
346
 
                     Table *table,
347
 
                     uint32_t index_arg,
348
 
                     bool no_alloc,
349
 
                     MEM_ROOT *parent_alloc,
350
 
                     bool *create_err);
351
 
  ~QuickRangeSelect();
352
 
 
353
 
  int init();
354
 
  int reset(void);
355
 
  int get_next();
356
 
  void range_end();
357
 
  int get_next_prefix(uint32_t prefix_length,
358
 
                      key_part_map keypart_map,
359
 
                      unsigned char *cur_prefix);
360
 
  bool reverse_sorted()
361
 
  {
362
 
    return false;
363
 
  }
364
 
  bool unique_key_range();
365
 
  int init_ror_merged_scan(bool reuse_handler);
366
 
  void save_last_pos();
367
 
  int get_type()
368
 
  {
369
 
    return QS_TYPE_RANGE;
370
 
  }
371
 
  void add_keys_and_lengths(String *key_names, String *used_lengths);
372
 
  void add_info_string(String *str);
373
 
  void resetCursor()
374
 
  {
375
 
    cursor= NULL;
376
 
  }
377
 
private:
378
 
  /* Used only by QUICK_SELECT_DESC */
379
 
  QuickRangeSelect(const QuickRangeSelect& org) : QuickSelectInterface()
380
 
  {
381
 
    memmove(this, &org, sizeof(*this));
382
 
    /*
383
 
      Use default MRR implementation for reverse scans. No table engine
384
 
      currently can do an MRR scan with output in reverse index order.
385
 
    */
386
 
    mrr_buf_desc= NULL;
387
 
    mrr_flags|= HA_MRR_USE_DEFAULT_IMPL;
388
 
    mrr_buf_size= 0;
389
 
  }
390
 
  friend class ::TRP_ROR_INTERSECT; 
391
 
  friend
392
 
  QuickRangeSelect *get_quick_select_for_ref(Session *session, Table *table,
393
 
                                               struct table_reference_st *ref,
394
 
                                               ha_rows records);
395
 
  friend bool get_quick_keys(PARAM *param, QuickRangeSelect *quick,
396
 
                             KEY_PART *key, SEL_ARG *key_tree,
397
 
                             unsigned char *min_key, uint32_t min_key_flag,
398
 
                             unsigned char *max_key, uint32_t max_key_flag);
399
 
  friend QuickRangeSelect *get_quick_select(PARAM*,uint32_t idx,
400
 
                                              SEL_ARG *key_tree,
401
 
                                              uint32_t mrr_flags,
402
 
                                              uint32_t mrr_buf_size,
403
 
                                              MEM_ROOT *alloc);
404
 
  friend class QUICK_SELECT_DESC;
405
 
  friend class QUICK_INDEX_MERGE_SELECT;
406
 
  friend class QUICK_ROR_INTERSECT_SELECT;
407
 
  friend class QUICK_GROUP_MIN_MAX_SELECT;
408
 
  friend uint32_t quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range);
409
 
  friend range_seq_t quick_range_seq_init(void *init_param,
410
 
                                          uint32_t n_ranges, uint32_t flags);
411
 
  friend void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
412
 
                              bool distinct,const char *message);
413
 
};
414
 
 
415
 
/**
416
 
  QUICK_INDEX_MERGE_SELECT - index_merge access method quick select.
417
 
 
418
 
    QUICK_INDEX_MERGE_SELECT uses
419
 
     * QuickRangeSelects to get rows
420
 
     * Unique class to remove duplicate rows
421
 
 
422
 
  INDEX MERGE OPTIMIZER
423
 
    Current implementation doesn't detect all cases where index_merge could
424
 
    be used, in particular:
425
 
     * index_merge will never be used if range scan is possible (even if
426
 
       range scan is more expensive)
427
 
 
428
 
     * index_merge+'using index' is not supported (this the consequence of
429
 
       the above restriction)
430
 
 
431
 
     * If WHERE part contains complex nested AND and OR conditions, some ways
432
 
       to retrieve rows using index_merge will not be considered. The choice
433
 
       of read plan may depend on the order of conjuncts/disjuncts in WHERE
434
 
       part of the query, see comments near imerge_list_or_list and
435
 
       SEL_IMERGE::or_sel_tree_with_checks functions for details.
436
 
 
437
 
     * There is no "index_merge_ref" method (but index_merge on non-first
438
 
       table in join is possible with 'range checked for each record').
439
 
 
440
 
    See comments around SEL_IMERGE class and test_quick_select for more
441
 
    details.
442
 
 
443
 
  ROW RETRIEVAL ALGORITHM
444
 
 
445
 
    index_merge uses Unique class for duplicates removal.  index_merge takes
446
 
    advantage of Clustered Primary Key (CPK) if the table has one.
447
 
    The index_merge algorithm consists of two phases:
448
 
 
449
 
    Phase 1 (implemented in QUICK_INDEX_MERGE_SELECT::prepare_unique):
450
 
    prepare()
451
 
    {
452
 
      activate 'index only';
453
 
      while(retrieve next row for non-CPK scan)
454
 
      {
455
 
        if (there is a CPK scan and row will be retrieved by it)
456
 
          skip this row;
457
 
        else
458
 
          put its rowid into Unique;
459
 
      }
460
 
      deactivate 'index only';
461
 
    }
462
 
 
463
 
    Phase 2 (implemented as sequence of QUICK_INDEX_MERGE_SELECT::get_next
464
 
    calls):
465
 
 
466
 
    fetch()
467
 
    {
468
 
      retrieve all rows from row pointers stored in Unique;
469
 
      free Unique;
470
 
      retrieve all rows for CPK scan;
471
 
    }
472
 
*/
473
 
class QUICK_INDEX_MERGE_SELECT : public QuickSelectInterface
474
 
{
475
 
public:
476
 
  QUICK_INDEX_MERGE_SELECT(Session *session, Table *table);
477
 
  ~QUICK_INDEX_MERGE_SELECT();
478
 
 
479
 
  int init();
480
 
  int reset(void);
481
 
  int get_next();
482
 
  bool reverse_sorted()
483
 
  {
484
 
    return false;
485
 
  }
486
 
  bool unique_key_range()
487
 
  {
488
 
    return false;
489
 
  }
490
 
  int get_type()
491
 
  {
492
 
    return QS_TYPE_INDEX_MERGE;
493
 
  }
494
 
  void add_keys_and_lengths(String *key_names, String *used_lengths);
495
 
  void add_info_string(String *str);
496
 
  bool is_keys_used(const MyBitmap *fields);
497
 
 
498
 
  bool push_quick_back(QuickRangeSelect *quick_sel_range);
499
 
 
500
 
  /* range quick selects this index_merge read consists of */
501
 
  List<QuickRangeSelect> quick_selects;
502
 
 
503
 
  /* quick select that uses clustered primary key (NULL if none) */
504
 
  QuickRangeSelect* pk_quick_select;
505
 
 
506
 
  /* true if this select is currently doing a clustered PK scan */
507
 
  bool  doing_pk_scan;
508
 
 
509
 
  MEM_ROOT alloc;
510
 
  Session *session;
511
 
  int read_keys_and_merge();
512
 
 
513
 
  /* used to get rows collected in Unique */
514
 
  READ_RECORD read_record;
515
 
};
516
 
 
517
276
 
518
277
/**
519
278
  Rowid-Ordered Retrieval (ROR) index intersection quick select.
746
505
  void add_keys_and_lengths(String *key_names, String *used_lengths);
747
506
};
748
507
 
749
 
class QUICK_SELECT_DESC: public QuickRangeSelect
750
 
{
751
 
public:
752
 
  QUICK_SELECT_DESC(QuickRangeSelect *q, uint32_t used_key_parts,
753
 
                    bool *create_err);
754
 
  int get_next();
755
 
  bool reverse_sorted() { return 1; }
756
 
  int get_type() { return QS_TYPE_RANGE_DESC; }
757
 
private:
758
 
  bool range_reads_after_key(QuickRange *range);
759
 
  int reset(void) { rev_it.rewind(); return QuickRangeSelect::reset(); }
760
 
  List<QuickRange> rev_ranges;
761
 
  List_iterator<QuickRange> rev_it;
762
 
};
763
 
 
764
508
/**
765
509
 * Executor class for SELECT statements.
766
510
 *