← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/optimizer/range.h

Merged Padraig.

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/optimizer/range.h
27
27
 
28
28
#include <queue>
29
29
 
30
 
class PARAM;
31
30
class JOIN;
32
31
class TRP_ROR_INTERSECT; 
33
32
typedef class Item COND;
50
49
  Field *field;
51
50
} KEY_PART;
52
51
 
53
 
class SEL_ARG;
54
52
 
55
53
namespace drizzled
56
54
{
58
56
namespace optimizer
59
57
{
60
58
 
61
 
class QUICK_RANGE : 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
 
  QUICK_RANGE(); /**< Constructor for a "full range" */
72
 
  QUICK_RANGE(const unsigned char *min_key_arg,
73
 
              uint32_t min_length_arg,
74
 
              key_part_map min_keypart_map_arg,
75
 
                    const unsigned char *max_key_arg, 
76
 
              uint32_t max_length_arg,
77
 
              key_part_map max_keypart_map_arg,
78
 
                    uint32_t flag_arg)
79
 
    : 
80
 
      min_key((unsigned char*) sql_memdup(min_key_arg,min_length_arg+1)),
81
 
      max_key((unsigned char*) sql_memdup(max_key_arg,max_length_arg+1)),
82
 
      min_length((uint16_t) min_length_arg),
83
 
      max_length((uint16_t) max_length_arg),
84
 
      flag((uint16_t) flag_arg),
85
 
      min_keypart_map(min_keypart_map_arg),
86
 
      max_keypart_map(max_keypart_map_arg)
87
 
    {}
88
 
};
 
59
class Parameter;
 
60
class SEL_ARG;
89
61
 
90
62
/**
91
63
  Quick select interface.
129
101
    delete quick;
130
102
 
131
103
*/
132
 
class QUICK_SELECT_I
 
104
class QuickSelectInterface
133
105
{
134
106
public:
135
107
  bool sorted;
165
137
   */
166
138
  unsigned char *record;
167
139
 
168
 
  QUICK_SELECT_I();
169
 
  virtual ~QUICK_SELECT_I(){};
 
140
  QuickSelectInterface();
 
141
  virtual ~QuickSelectInterface(){};
170
142
 
171
143
  /**
172
144
   * Do post-constructor initialization.
284
256
};
285
257
 
286
258
struct st_qsel_param;
 
259
class QuickRange;
 
260
class QuickRangeSelect;
287
261
 
288
262
/**
289
 
 * MRR range sequence, array<QUICK_RANGE> implementation: sequence traversal
 
263
 * MRR range sequence, array<QuickRange> implementation: sequence traversal
290
264
 * context.
291
265
 */
292
266
typedef struct st_quick_range_seq_ctx
293
267
{
294
 
  QUICK_RANGE **first;
295
 
  QUICK_RANGE **cur;
296
 
  QUICK_RANGE **last;
297
 
} QUICK_RANGE_SEQ_CTX;
 
268
  QuickRange **first;
 
269
  QuickRange **cur;
 
270
  QuickRange **last;
 
271
} QuickRangeSequenceContext;
298
272
 
299
273
range_seq_t quick_range_seq_init(void *init_param, uint32_t n_ranges, uint32_t flags);
 
274
 
300
275
uint32_t quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range);
301
276
 
302
 
/**
303
 
 * Quick select that does a range scan on a single key. 
304
 
 *
305
 
 * The records are returned in key order.
306
 
 * 
307
 
 */
308
 
class QUICK_RANGE_SELECT : public QUICK_SELECT_I
309
 
{
310
 
protected:
311
 
  Cursor *cursor;
312
 
  DYNAMIC_ARRAY ranges; /**< ordered array of range ptrs */
313
 
 
314
 
  /** Members to deal with case when this quick select is a ROR-merged scan */
315
 
  bool in_ror_merged_scan;
316
 
  MyBitmap column_bitmap;
317
 
  MyBitmap *save_read_set;
318
 
  MyBitmap *save_write_set;
319
 
  bool free_file; /**< True when this->file is "owned" by this quick select */
320
 
 
321
 
  /* Range pointers to be used when not using MRR interface */
322
 
  QUICK_RANGE **cur_range; /**< current element in ranges  */
323
 
  QUICK_RANGE *last_range;
324
 
 
325
 
  /** Members needed to use the MRR interface */
326
 
  QUICK_RANGE_SEQ_CTX qr_traversal_ctx;
327
 
  uint32_t mrr_buf_size; /**< copy from session->variables.read_rnd_buff_size */
328
 
  HANDLER_BUFFER *mrr_buf_desc; /**< the Cursor buffer */
329
 
 
330
 
  /** Info about index we're scanning */
331
 
  KEY_PART *key_parts;
332
 
  KEY_PART_INFO *key_part_info;
333
 
 
334
 
  bool dont_free; /**< Used by QUICK_SELECT_DESC */
335
 
 
336
 
  int cmp_next(QUICK_RANGE *range);
337
 
  int cmp_prev(QUICK_RANGE *range);
338
 
  bool row_in_ranges();
339
 
public:
340
 
  uint32_t mrr_flags; /**< Flags to be used with MRR interface */
341
 
  MEM_ROOT alloc;
342
 
 
343
 
  QUICK_RANGE_SELECT(Session *session,
344
 
                     Table *table,
345
 
                     uint32_t index_arg,
346
 
                     bool no_alloc,
347
 
                     MEM_ROOT *parent_alloc,
348
 
                     bool *create_err);
349
 
  ~QUICK_RANGE_SELECT();
350
 
 
351
 
  int init();
352
 
  int reset(void);
353
 
  int get_next();
354
 
  void range_end();
355
 
  int get_next_prefix(uint32_t prefix_length,
356
 
                      key_part_map keypart_map,
357
 
                      unsigned char *cur_prefix);
358
 
  bool reverse_sorted()
359
 
  {
360
 
    return false;
361
 
  }
362
 
  bool unique_key_range();
363
 
  int init_ror_merged_scan(bool reuse_handler);
364
 
  void save_last_pos();
365
 
  int get_type()
366
 
  {
367
 
    return QS_TYPE_RANGE;
368
 
  }
369
 
  void add_keys_and_lengths(String *key_names, String *used_lengths);
370
 
  void add_info_string(String *str);
371
 
  void resetCursor()
372
 
  {
373
 
    cursor= NULL;
374
 
  }
375
 
private:
376
 
  /* Used only by QUICK_SELECT_DESC */
377
 
  QUICK_RANGE_SELECT(const QUICK_RANGE_SELECT& org) : QUICK_SELECT_I()
378
 
  {
379
 
    memmove(this, &org, sizeof(*this));
380
 
    /*
381
 
      Use default MRR implementation for reverse scans. No table engine
382
 
      currently can do an MRR scan with output in reverse index order.
383
 
    */
384
 
    mrr_buf_desc= NULL;
385
 
    mrr_flags|= HA_MRR_USE_DEFAULT_IMPL;
386
 
    mrr_buf_size= 0;
387
 
  }
388
 
  friend class ::TRP_ROR_INTERSECT; 
389
 
  friend
390
 
  QUICK_RANGE_SELECT *get_quick_select_for_ref(Session *session, Table *table,
391
 
                                               struct table_reference_st *ref,
392
 
                                               ha_rows records);
393
 
  friend bool get_quick_keys(PARAM *param, QUICK_RANGE_SELECT *quick,
394
 
                             KEY_PART *key, SEL_ARG *key_tree,
395
 
                             unsigned char *min_key, uint32_t min_key_flag,
396
 
                             unsigned char *max_key, uint32_t max_key_flag);
397
 
  friend QUICK_RANGE_SELECT *get_quick_select(PARAM*,uint32_t idx,
398
 
                                              SEL_ARG *key_tree,
399
 
                                              uint32_t mrr_flags,
400
 
                                              uint32_t mrr_buf_size,
401
 
                                              MEM_ROOT *alloc);
402
 
  friend class QUICK_SELECT_DESC;
403
 
  friend class QUICK_INDEX_MERGE_SELECT;
404
 
  friend class QUICK_ROR_INTERSECT_SELECT;
405
 
  friend class QUICK_GROUP_MIN_MAX_SELECT;
406
 
  friend uint32_t quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range);
407
 
  friend range_seq_t quick_range_seq_init(void *init_param,
408
 
                                          uint32_t n_ranges, uint32_t flags);
409
 
  friend void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
410
 
                              bool distinct,const char *message);
411
 
};
412
 
 
413
 
/**
414
 
  QUICK_INDEX_MERGE_SELECT - index_merge access method quick select.
415
 
 
416
 
    QUICK_INDEX_MERGE_SELECT uses
417
 
     * QUICK_RANGE_SELECTs to get rows
418
 
     * Unique class to remove duplicate rows
419
 
 
420
 
  INDEX MERGE OPTIMIZER
421
 
    Current implementation doesn't detect all cases where index_merge could
422
 
    be used, in particular:
423
 
     * index_merge will never be used if range scan is possible (even if
424
 
       range scan is more expensive)
425
 
 
426
 
     * index_merge+'using index' is not supported (this the consequence of
427
 
       the above restriction)
428
 
 
429
 
     * If WHERE part contains complex nested AND and OR conditions, some ways
430
 
       to retrieve rows using index_merge will not be considered. The choice
431
 
       of read plan may depend on the order of conjuncts/disjuncts in WHERE
432
 
       part of the query, see comments near imerge_list_or_list and
433
 
       SEL_IMERGE::or_sel_tree_with_checks functions for details.
434
 
 
435
 
     * There is no "index_merge_ref" method (but index_merge on non-first
436
 
       table in join is possible with 'range checked for each record').
437
 
 
438
 
    See comments around SEL_IMERGE class and test_quick_select for more
439
 
    details.
440
 
 
441
 
  ROW RETRIEVAL ALGORITHM
442
 
 
443
 
    index_merge uses Unique class for duplicates removal.  index_merge takes
444
 
    advantage of Clustered Primary Key (CPK) if the table has one.
445
 
    The index_merge algorithm consists of two phases:
446
 
 
447
 
    Phase 1 (implemented in QUICK_INDEX_MERGE_SELECT::prepare_unique):
448
 
    prepare()
449
 
    {
450
 
      activate 'index only';
451
 
      while(retrieve next row for non-CPK scan)
452
 
      {
453
 
        if (there is a CPK scan and row will be retrieved by it)
454
 
          skip this row;
455
 
        else
456
 
          put its rowid into Unique;
457
 
      }
458
 
      deactivate 'index only';
459
 
    }
460
 
 
461
 
    Phase 2 (implemented as sequence of QUICK_INDEX_MERGE_SELECT::get_next
462
 
    calls):
463
 
 
464
 
    fetch()
465
 
    {
466
 
      retrieve all rows from row pointers stored in Unique;
467
 
      free Unique;
468
 
      retrieve all rows for CPK scan;
469
 
    }
470
 
*/
471
 
class QUICK_INDEX_MERGE_SELECT : public QUICK_SELECT_I
472
 
{
473
 
public:
474
 
  QUICK_INDEX_MERGE_SELECT(Session *session, Table *table);
475
 
  ~QUICK_INDEX_MERGE_SELECT();
476
 
 
477
 
  int init();
478
 
  int reset(void);
479
 
  int get_next();
480
 
  bool reverse_sorted()
481
 
  {
482
 
    return false;
483
 
  }
484
 
  bool unique_key_range()
485
 
  {
486
 
    return false;
487
 
  }
488
 
  int get_type()
489
 
  {
490
 
    return QS_TYPE_INDEX_MERGE;
491
 
  }
492
 
  void add_keys_and_lengths(String *key_names, String *used_lengths);
493
 
  void add_info_string(String *str);
494
 
  bool is_keys_used(const MyBitmap *fields);
495
 
 
496
 
  bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range);
497
 
 
498
 
  /* range quick selects this index_merge read consists of */
499
 
  List<QUICK_RANGE_SELECT> quick_selects;
500
 
 
501
 
  /* quick select that uses clustered primary key (NULL if none) */
502
 
  QUICK_RANGE_SELECT* pk_quick_select;
503
 
 
504
 
  /* true if this select is currently doing a clustered PK scan */
505
 
  bool  doing_pk_scan;
506
 
 
507
 
  MEM_ROOT alloc;
508
 
  Session *session;
509
 
  int read_keys_and_merge();
510
 
 
511
 
  /* used to get rows collected in Unique */
512
 
  READ_RECORD read_record;
513
 
};
514
 
 
515
277
 
516
278
/**
517
279
  Rowid-Ordered Retrieval (ROR) index intersection quick select.
518
280
  This quick select produces intersection of row sequences returned
519
 
  by several QUICK_RANGE_SELECTs it "merges".
 
281
  by several QuickRangeSelects it "merges".
520
282
 
521
 
  All merged QUICK_RANGE_SELECTs must return rowids in rowid order.
 
283
  All merged QuickRangeSelects must return rowids in rowid order.
522
284
  QUICK_ROR_INTERSECT_SELECT will return rows in rowid order, too.
523
285
 
524
286
  All merged quick selects retrieve {rowid, covered_fields} tuples (not full
530
292
  If one of the merged quick selects is a Clustered PK range scan, it is
531
293
  used only to filter rowid sequence produced by other merged quick selects.
532
294
*/
533
 
class QUICK_ROR_INTERSECT_SELECT : public QUICK_SELECT_I
 
295
class QUICK_ROR_INTERSECT_SELECT : public QuickSelectInterface
534
296
{
535
297
public:
536
298
  QUICK_ROR_INTERSECT_SELECT(Session *session, Table *table,
557
319
  void add_info_string(String *str);
558
320
  bool is_keys_used(const MyBitmap *fields);
559
321
  int init_ror_merged_scan(bool reuse_handler);
560
 
  bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range);
 
322
  bool push_quick_back(QuickRangeSelect *quick_sel_range);
561
323
 
562
324
  /**
563
325
   * Range quick selects this intersection consists of, not including
564
326
   * cpk_quick.
565
327
   */
566
 
  List<QUICK_RANGE_SELECT> quick_selects;
 
328
  List<QuickRangeSelect> quick_selects;
567
329
 
568
330
  /**
569
331
   * Merged quick select that uses Clustered PK, if there is one. This quick
570
332
   * select is not used for row retrieval, it is used for row retrieval.
571
333
   */
572
 
  QUICK_RANGE_SELECT *cpk_quick;
 
334
  QuickRangeSelect *cpk_quick;
573
335
 
574
336
  MEM_ROOT alloc; /**< Memory pool for this and merged quick selects data. */
575
337
  Session *session; /**< Pointer to the current session */
598
360
  ROR-union quick select always retrieves full records.
599
361
 
600
362
*/
601
 
class QUICK_ROR_UNION_SELECT : public QUICK_SELECT_I
 
363
class QUICK_ROR_UNION_SELECT : public QuickSelectInterface
602
364
{
603
365
public:
604
366
  QUICK_ROR_UNION_SELECT(Session *session, Table *table);
623
385
  void add_info_string(String *str);
624
386
  bool is_keys_used(const MyBitmap *fields);
625
387
 
626
 
  bool push_quick_back(QUICK_SELECT_I *quick_sel_range);
 
388
  bool push_quick_back(QuickSelectInterface *quick_sel_range);
627
389
 
628
 
  List<QUICK_SELECT_I> quick_selects; /**< Merged quick selects */
 
390
  List<QuickSelectInterface> quick_selects; /**< Merged quick selects */
629
391
 
630
392
  /** Priority queue for merge operation */
631
 
  std::priority_queue<QUICK_SELECT_I *, std::vector<QUICK_SELECT_I *>, compare_functor > *queue;
 
393
  std::priority_queue<QuickSelectInterface *, std::vector<QuickSelectInterface *>, compare_functor > *queue;
632
394
  MEM_ROOT alloc; /**< Memory pool for this and merged quick selects data. */
633
395
 
634
396
  Session *session; /**< current thread */
672
434
  Since one of the requirements is that all select fields are part of the same
673
435
  index, this class produces only index keys, and not complete records.
674
436
*/
675
 
class QUICK_GROUP_MIN_MAX_SELECT : public QUICK_SELECT_I
 
437
class QUICK_GROUP_MIN_MAX_SELECT : public QuickSelectInterface
676
438
{
677
439
private:
678
440
  Cursor *cursor; /**< The Cursor used to get data. */
704
466
    TRP_GROUP_MIN_MAX::make_quick()
705
467
  */
706
468
  MEM_ROOT alloc; /**< Memory pool for this and quick_prefix_select data. */
707
 
  QUICK_RANGE_SELECT *quick_prefix_select; /**< For retrieval of group prefixes. */
 
469
  QuickRangeSelect *quick_prefix_select; /**< For retrieval of group prefixes. */
708
470
private:
709
471
  int next_prefix();
710
472
  int next_min_in_range();
744
506
  void add_keys_and_lengths(String *key_names, String *used_lengths);
745
507
};
746
508
 
747
 
class QUICK_SELECT_DESC: public QUICK_RANGE_SELECT
748
 
{
749
 
public:
750
 
  QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint32_t used_key_parts,
751
 
                    bool *create_err);
752
 
  int get_next();
753
 
  bool reverse_sorted() { return 1; }
754
 
  int get_type() { return QS_TYPE_RANGE_DESC; }
755
 
private:
756
 
  bool range_reads_after_key(QUICK_RANGE *range);
757
 
  int reset(void) { rev_it.rewind(); return QUICK_RANGE_SELECT::reset(); }
758
 
  List<QUICK_RANGE> rev_ranges;
759
 
  List_iterator<QUICK_RANGE> rev_it;
760
 
};
761
 
 
762
509
/**
763
510
 * Executor class for SELECT statements.
764
511
 *
765
512
 * @details
766
513
 *
767
 
 * The QUICK_SELECT_I member variable is the implementor
 
514
 * The QuickSelectInterface member variable is the implementor
768
515
 * of the SELECT execution.
769
516
 */
770
 
class SQL_SELECT : public Sql_alloc 
 
517
class SqlSelect : public Sql_alloc 
771
518
{
772
519
 public:
773
 
  QUICK_SELECT_I *quick; /**< If quick-select used */
 
520
  QuickSelectInterface *quick; /**< If quick-select used */
774
521
  COND *cond; /**< where condition */
775
522
  Table *head;
776
523
  IO_CACHE file; /**< Positions to used records */
782
529
  table_map read_tables;
783
530
  bool free_cond;
784
531
 
785
 
  SQL_SELECT();
786
 
  ~SQL_SELECT();
 
532
  SqlSelect();
 
533
  ~SqlSelect();
787
534
  void cleanup();
788
535
  bool check_quick(Session *session, bool force_quick_range, ha_rows limit);
789
536
  bool skip_record();
792
539
                        bool ordered_output);
793
540
};
794
541
 
795
 
QUICK_RANGE_SELECT *get_quick_select_for_ref(Session *session, 
 
542
QuickRangeSelect *get_quick_select_for_ref(Session *session, 
796
543
                                             Table *table,
797
544
                                             struct table_reference_st *ref,
798
545
                                             ha_rows records);
799
546
 
800
547
/*
801
 
  Create a QUICK_RANGE_SELECT from given key and SEL_ARG tree for that key.
 
548
  Create a QuickRangeSelect from given key and SEL_ARG tree for that key.
802
549
 
803
550
  SYNOPSIS
804
551
    get_quick_select()
819
566
    NULL on error
820
567
    otherwise created quick select
821
568
*/
822
 
QUICK_RANGE_SELECT *get_quick_select(PARAM *param,
823
 
                                     uint32_t index,
824
 
                                     SEL_ARG *key_tree, 
825
 
                                     uint32_t mrr_flags,
826
 
                                     uint32_t mrr_buf_size, 
827
 
                                     MEM_ROOT *alloc);
 
569
QuickRangeSelect *get_quick_select(Parameter *param,
 
570
                                   uint32_t index,
 
571
                                   SEL_ARG *key_tree, 
 
572
                                   uint32_t mrr_flags,
 
573
                                   uint32_t mrr_buf_size, 
 
574
                                   MEM_ROOT *alloc);
828
575
 
829
576
uint32_t get_index_for_order(Table *table, order_st *order, ha_rows limit);
830
577
 
831
 
SQL_SELECT *make_select(Table *head, 
 
578
SqlSelect *make_select(Table *head, 
832
579
                        table_map const_tables,
833
580
                                          table_map read_tables, 
834
581
                        COND *conds,
835
582
                        bool allow_null_cond,
836
583
                        int *error);
837
584
 
838
 
bool get_quick_keys(PARAM *param, 
839
 
                    QUICK_RANGE_SELECT *quick,KEY_PART *key,
 
585
bool get_quick_keys(Parameter *param, 
 
586
                    QuickRangeSelect *quick,
 
587
                    KEY_PART *key,
840
588
                    SEL_ARG *key_tree, 
841
589
                    unsigned char *min_key,
842
590
                    uint32_t min_key_flag,