← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to sql/opt_range.h

  • Committer: Brian Aker
  • Date: 2008-06-30 18:52:15 UTC
  • Revision ID: brian@tangent.org-20080630185215-n0fr4k0gk5hk785c
Remove dead position (should be in config/)

Show diffs side-by-side

added added

removed removed

Lines of Context:
sql/opt_range.h
1
 
/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2
 
 *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
3
 
 *
4
 
 *  Copyright (C) 2008 Sun Microsystems
5
 
 *
6
 
 *  This program is free software; you can redistribute it and/or modify
7
 
 *  it under the terms of the GNU General Public License as published by
8
 
 *  the Free Software Foundation; version 2 of the License.
9
 
 *
10
 
 *  This program is distributed in the hope that it will be useful,
11
 
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12
 
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13
 
 *  GNU General Public License for more details.
14
 
 *
15
 
 *  You should have received a copy of the GNU General Public License
16
 
 *  along with this program; if not, write to the Free Software
17
 
 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
18
 
 */
 
1
/* Copyright (C) 2000-2006 MySQL AB
 
2
 
 
3
   This program is free software; you can redistribute it and/or modify
 
4
   it under the terms of the GNU General Public License as published by
 
5
   the Free Software Foundation; version 2 of the License.
 
6
 
 
7
   This program is distributed in the hope that it will be useful,
 
8
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
9
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
10
   GNU General Public License for more details.
 
11
 
 
12
   You should have received a copy of the GNU General Public License
 
13
   along with this program; if not, write to the Free Software
 
14
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
19
15
 
20
16
 
21
17
/* classes to use when handling where clause */
22
18
 
23
 
#ifndef DRIZZLED_OPT_RANGE_H
24
 
#define DRIZZLED_OPT_RANGE_H
 
19
#ifndef _opt_range_h
 
20
#define _opt_range_h
25
21
 
26
 
#include <mysys/queues.h>
 
22
#ifdef USE_PRAGMA_INTERFACE
 
23
#pragma interface                       /* gcc class implementation */
 
24
#endif
27
25
 
28
26
typedef struct st_key_part {
29
 
  uint16_t           key,part;
 
27
  uint16           key,part;
30
28
  /* See KEY_PART_INFO for meaning of the next two: */
31
 
  uint16_t           store_length, length;
32
 
  uint8_t            null_bit;
 
29
  uint16           store_length, length;
 
30
  uint8            null_bit;
33
31
  /*
34
32
    Keypart flags (0 when this structure is used by partition pruning code
35
33
    for fake partitioning index description)
36
34
  */
37
 
  uint8_t flag;
 
35
  uint8 flag;
38
36
  Field            *field;
39
37
  Field::imagetype image_type;
40
38
} KEY_PART;
42
40
 
43
41
class QUICK_RANGE :public Sql_alloc {
44
42
 public:
45
 
  unsigned char *min_key,*max_key;
46
 
  uint16_t min_length,max_length,flag;
 
43
  uchar *min_key,*max_key;
 
44
  uint16 min_length,max_length,flag;
47
45
  key_part_map min_keypart_map, // bitmap of used keyparts in min_key
48
46
               max_keypart_map; // bitmap of used keyparts in max_key
49
47
#ifdef HAVE_purify
50
 
  uint16_t dummy;                                       /* Avoid warnings on 'flag' */
 
48
  uint16 dummy;                                 /* Avoid warnings on 'flag' */
51
49
#endif
52
50
  QUICK_RANGE();                                /* Full range */
53
 
  QUICK_RANGE(const unsigned char *min_key_arg, uint32_t min_length_arg,
 
51
  QUICK_RANGE(const uchar *min_key_arg, uint min_length_arg,
54
52
              key_part_map min_keypart_map_arg,
55
 
              const unsigned char *max_key_arg, uint32_t max_length_arg,
 
53
              const uchar *max_key_arg, uint max_length_arg,
56
54
              key_part_map max_keypart_map_arg,
57
 
              uint32_t flag_arg)
58
 
    : min_key((unsigned char*) sql_memdup(min_key_arg,min_length_arg+1)),
59
 
      max_key((unsigned char*) sql_memdup(max_key_arg,max_length_arg+1)),
60
 
      min_length((uint16_t) min_length_arg),
61
 
      max_length((uint16_t) max_length_arg),
62
 
      flag((uint16_t) flag_arg),
 
55
              uint flag_arg)
 
56
    : min_key((uchar*) sql_memdup(min_key_arg,min_length_arg+1)),
 
57
      max_key((uchar*) sql_memdup(max_key_arg,max_length_arg+1)),
 
58
      min_length((uint16) min_length_arg),
 
59
      max_length((uint16) max_length_arg),
 
60
      flag((uint16) flag_arg),
63
61
      min_keypart_map(min_keypart_map_arg),
64
62
      max_keypart_map(max_keypart_map_arg)
65
63
    {
72
70
 
73
71
/*
74
72
  Quick select interface.
75
 
  This class is a parent for all QUICK_*_SELECT classes.
 
73
  This class is a parent for all QUICK_*_SELECT and FT_SELECT classes.
76
74
 
77
75
  The usage scenario is as follows:
78
76
  1. Create quick select
119
117
  bool sorted;
120
118
  ha_rows records;  /* estimate of # of records to be retrieved */
121
119
  double  read_time; /* time to perform this retrieval          */
122
 
  Table   *head;
 
120
  TABLE   *head;
123
121
  /*
124
122
    Index this quick select uses, or MAX_KEY for quick selects
125
123
    that use several indexes
126
124
  */
127
 
  uint32_t index;
 
125
  uint index;
128
126
 
129
127
  /*
130
128
    Total length of first used_key_parts parts of the key.
131
129
    Applicable if index!= MAX_KEY.
132
130
  */
133
 
  uint32_t max_used_key_length;
 
131
  uint max_used_key_length;
134
132
 
135
133
  /*
136
134
    Max. number of (first) key parts this quick select uses for retrieval.
139
137
 
140
138
    For QUICK_GROUP_MIN_MAX_SELECT it includes MIN/MAX argument keyparts.
141
139
  */
142
 
  uint32_t used_key_parts;
 
140
  uint used_key_parts;
143
141
 
144
142
  QUICK_SELECT_I();
145
143
  virtual ~QUICK_SELECT_I(){};
214
212
      0     Ok
215
213
      other Error
216
214
  */
217
 
  virtual int init_ror_merged_scan(bool)
218
 
  { assert(0); return 1; }
 
215
  virtual int init_ror_merged_scan(bool reuse_handler)
 
216
  { DBUG_ASSERT(0); return 1; }
219
217
 
220
218
  /*
221
219
    Save ROWID of last retrieved row in file->ref. This used in ROR-merging.
236
234
    This function is implemented only by quick selects that merge other quick
237
235
    selects output and/or can produce output suitable for merging.
238
236
  */
239
 
  virtual void add_info_string(String *) {};
 
237
  virtual void add_info_string(String *str) {};
240
238
  /*
241
239
    Return 1 if any index used by this quick select
242
240
    uses field which is marked in passed bitmap.
247
245
    rowid of last row retrieved by this quick select. This is used only when
248
246
    doing ROR-index_merge selects
249
247
  */
250
 
  unsigned char    *last_rowid;
 
248
  uchar    *last_rowid;
251
249
 
252
250
  /*
253
251
    Table record buffer used by this quick select.
254
252
  */
255
 
  unsigned char    *record;
 
253
  uchar    *record;
 
254
#ifndef DBUG_OFF
 
255
  /*
 
256
    Print quick select information to DBUG_FILE. Caller is responsible
 
257
    for locking DBUG_FILE before this call and unlocking it afterwards.
 
258
  */
 
259
  virtual void dbug_dump(int indent, bool verbose)= 0;
 
260
#endif
256
261
};
257
262
 
258
263
 
272
277
  QUICK_RANGE **last;
273
278
} QUICK_RANGE_SEQ_CTX;
274
279
 
275
 
range_seq_t quick_range_seq_init(void *init_param, uint32_t n_ranges, uint32_t flags);
276
 
uint32_t quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range);
 
280
range_seq_t quick_range_seq_init(void *init_param, uint n_ranges, uint flags);
 
281
uint quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range);
277
282
 
278
283
 
279
284
/*
298
303
  /* Members needed to use the MRR interface */
299
304
  QUICK_RANGE_SEQ_CTX qr_traversal_ctx;
300
305
public:
301
 
  uint32_t mrr_flags; /* Flags to be used with MRR interface */
 
306
  uint mrr_flags; /* Flags to be used with MRR interface */
302
307
protected:
303
 
  uint32_t mrr_buf_size; /* copy from session->variables.read_rnd_buff_size */  
 
308
  uint mrr_buf_size; /* copy from thd->variables.read_rnd_buff_size */  
304
309
  HANDLER_BUFFER *mrr_buf_desc; /* the handler buffer */
305
310
 
306
311
  /* Info about index we're scanning */
315
320
public:
316
321
  MEM_ROOT alloc;
317
322
 
318
 
  QUICK_RANGE_SELECT(Session *session, Table *table,uint32_t index_arg,bool no_alloc,
 
323
  QUICK_RANGE_SELECT(THD *thd, TABLE *table,uint index_arg,bool no_alloc,
319
324
                     MEM_ROOT *parent_alloc, bool *create_err);
320
325
  ~QUICK_RANGE_SELECT();
321
326
 
323
328
  int reset(void);
324
329
  int get_next();
325
330
  void range_end();
326
 
  int get_next_prefix(uint32_t prefix_length, key_part_map keypart_map,
327
 
                      unsigned char *cur_prefix);
 
331
  int get_next_prefix(uint prefix_length, key_part_map keypart_map,
 
332
                      uchar *cur_prefix);
328
333
  bool reverse_sorted() { return 0; }
329
334
  bool unique_key_range();
330
335
  int init_ror_merged_scan(bool reuse_handler);
333
338
  int get_type() { return QS_TYPE_RANGE; }
334
339
  void add_keys_and_lengths(String *key_names, String *used_lengths);
335
340
  void add_info_string(String *str);
 
341
#ifndef DBUG_OFF
 
342
  void dbug_dump(int indent, bool verbose);
 
343
#endif
336
344
private:
337
345
  /* Used only by QUICK_SELECT_DESC */
338
346
  QUICK_RANGE_SELECT(const QUICK_RANGE_SELECT& org) : QUICK_SELECT_I()
339
347
  {
340
 
    memmove(this, &org, sizeof(*this));
 
348
    bcopy(&org, this, sizeof(*this));
341
349
    /* 
342
350
      Use default MRR implementation for reverse scans. No table engine
343
351
      currently can do an MRR scan with output in reverse index order.
348
356
  }
349
357
  friend class TRP_ROR_INTERSECT;
350
358
  friend
351
 
  QUICK_RANGE_SELECT *get_quick_select_for_ref(Session *session, Table *table,
 
359
  QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table,
352
360
                                               struct st_table_ref *ref,
353
361
                                               ha_rows records);
354
362
  friend bool get_quick_keys(PARAM *param, QUICK_RANGE_SELECT *quick, 
355
363
                             KEY_PART *key, SEL_ARG *key_tree, 
356
 
                             unsigned char *min_key, uint32_t min_key_flag,
357
 
                             unsigned char *max_key, uint32_t max_key_flag);
358
 
  friend QUICK_RANGE_SELECT *get_quick_select(PARAM*,uint32_t idx,
 
364
                             uchar *min_key, uint min_key_flag,
 
365
                             uchar *max_key, uint max_key_flag);
 
366
  friend QUICK_RANGE_SELECT *get_quick_select(PARAM*,uint idx,
359
367
                                              SEL_ARG *key_tree,
360
 
                                              uint32_t mrr_flags,
361
 
                                              uint32_t mrr_buf_size,
 
368
                                              uint mrr_flags,
 
369
                                              uint mrr_buf_size,
362
370
                                              MEM_ROOT *alloc);
363
371
  friend class QUICK_SELECT_DESC;
364
372
  friend class QUICK_INDEX_MERGE_SELECT;
365
373
  friend class QUICK_ROR_INTERSECT_SELECT;
366
374
  friend class QUICK_GROUP_MIN_MAX_SELECT;
367
 
  friend uint32_t quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range);
 
375
  friend uint quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range);
368
376
  friend range_seq_t quick_range_seq_init(void *init_param,
369
 
                                          uint32_t n_ranges, uint32_t flags);
 
377
                                          uint n_ranges, uint flags);
370
378
  friend void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
371
379
                              bool distinct,const char *message);
372
380
};
434
442
class QUICK_INDEX_MERGE_SELECT : public QUICK_SELECT_I
435
443
{
436
444
public:
437
 
  QUICK_INDEX_MERGE_SELECT(Session *session, Table *table);
 
445
  QUICK_INDEX_MERGE_SELECT(THD *thd, TABLE *table);
438
446
  ~QUICK_INDEX_MERGE_SELECT();
439
447
 
440
448
  int  init();
446
454
  void add_keys_and_lengths(String *key_names, String *used_lengths);
447
455
  void add_info_string(String *str);
448
456
  bool is_keys_used(const MY_BITMAP *fields);
 
457
#ifndef DBUG_OFF
 
458
  void dbug_dump(int indent, bool verbose);
 
459
#endif
449
460
 
450
461
  bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range);
451
462
 
459
470
  bool  doing_pk_scan;
460
471
 
461
472
  MEM_ROOT alloc;
462
 
  Session *session;
 
473
  THD *thd;
463
474
  int read_keys_and_merge();
464
475
 
465
476
  /* used to get rows collected in Unique */
488
499
class QUICK_ROR_INTERSECT_SELECT : public QUICK_SELECT_I
489
500
{
490
501
public:
491
 
  QUICK_ROR_INTERSECT_SELECT(Session *session, Table *table,
 
502
  QUICK_ROR_INTERSECT_SELECT(THD *thd, TABLE *table,
492
503
                             bool retrieve_full_rows,
493
504
                             MEM_ROOT *parent_alloc);
494
505
  ~QUICK_ROR_INTERSECT_SELECT();
502
513
  void add_keys_and_lengths(String *key_names, String *used_lengths);
503
514
  void add_info_string(String *str);
504
515
  bool is_keys_used(const MY_BITMAP *fields);
 
516
#ifndef DBUG_OFF
 
517
  void dbug_dump(int indent, bool verbose);
 
518
#endif
505
519
  int init_ror_merged_scan(bool reuse_handler);
506
520
  bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range);
507
521
 
518
532
  QUICK_RANGE_SELECT *cpk_quick;
519
533
 
520
534
  MEM_ROOT alloc; /* Memory pool for this and merged quick selects data. */
521
 
  Session *session;       /* current thread */
 
535
  THD *thd;       /* current thread */
522
536
  bool need_to_fetch_row; /* if true, do retrieve full table records. */
523
537
  /* in top-level quick select, true if merged scans where initialized */
524
538
  bool scans_inited; 
541
555
class QUICK_ROR_UNION_SELECT : public QUICK_SELECT_I
542
556
{
543
557
public:
544
 
  QUICK_ROR_UNION_SELECT(Session *session, Table *table);
 
558
  QUICK_ROR_UNION_SELECT(THD *thd, TABLE *table);
545
559
  ~QUICK_ROR_UNION_SELECT();
546
560
 
547
561
  int  init();
553
567
  void add_keys_and_lengths(String *key_names, String *used_lengths);
554
568
  void add_info_string(String *str);
555
569
  bool is_keys_used(const MY_BITMAP *fields);
 
570
#ifndef DBUG_OFF
 
571
  void dbug_dump(int indent, bool verbose);
 
572
#endif
556
573
 
557
574
  bool push_quick_back(QUICK_SELECT_I *quick_sel_range);
558
575
 
561
578
  QUEUE queue;    /* Priority queue for merge operation */
562
579
  MEM_ROOT alloc; /* Memory pool for this and merged quick selects data. */
563
580
 
564
 
  Session *session;             /* current thread */
565
 
  unsigned char *cur_rowid;      /* buffer used in get_next() */
566
 
  unsigned char *prev_rowid;     /* rowid of last row returned by get_next() */
 
581
  THD *thd;             /* current thread */
 
582
  uchar *cur_rowid;      /* buffer used in get_next() */
 
583
  uchar *prev_rowid;     /* rowid of last row returned by get_next() */
567
584
  bool have_prev_rowid; /* true if prev_rowid has valid data */
568
 
  uint32_t rowid_length;    /* table rowid length */
 
585
  uint rowid_length;    /* table rowid length */
569
586
private:
570
 
  static int queue_cmp(void *arg, unsigned char *val1, unsigned char *val2);
 
587
  static int queue_cmp(void *arg, uchar *val1, uchar *val2);
571
588
  bool scans_inited; 
572
589
};
573
590
 
611
628
  handler *file;         /* The handler used to get data. */
612
629
  JOIN *join;            /* Descriptor of the current query */
613
630
  KEY  *index_info;      /* The index chosen for data access */
614
 
  unsigned char *record;          /* Buffer where the next record is returned. */
615
 
  unsigned char *tmp_record;      /* Temporary storage for next_min(), next_max(). */
616
 
  unsigned char *group_prefix;    /* Key prefix consisting of the GROUP fields. */
617
 
  uint32_t group_prefix_len; /* Length of the group prefix. */
618
 
  uint32_t group_key_parts;  /* A number of keyparts in the group prefix */
619
 
  unsigned char *last_prefix;     /* Prefix of the last group for detecting EOF. */
 
631
  uchar *record;          /* Buffer where the next record is returned. */
 
632
  uchar *tmp_record;      /* Temporary storage for next_min(), next_max(). */
 
633
  uchar *group_prefix;    /* Key prefix consisting of the GROUP fields. */
 
634
  uint group_prefix_len; /* Length of the group prefix. */
 
635
  uint group_key_parts;  /* A number of keyparts in the group prefix */
 
636
  uchar *last_prefix;     /* Prefix of the last group for detecting EOF. */
620
637
  bool have_min;         /* Specify whether we are computing */
621
638
  bool have_max;         /*   a MIN, a MAX, or both.         */
622
639
  bool seen_first_key;   /* Denotes whether the first key was retrieved.*/
623
640
  KEY_PART_INFO *min_max_arg_part; /* The keypart of the only argument field */
624
641
                                   /* of all MIN/MAX functions.              */
625
 
  uint32_t min_max_arg_len;  /* The length of the MIN/MAX argument field */
626
 
  unsigned char *key_infix;       /* Infix of constants from equality predicates. */
627
 
  uint32_t key_infix_len;
 
642
  uint min_max_arg_len;  /* The length of the MIN/MAX argument field */
 
643
  uchar *key_infix;       /* Infix of constants from equality predicates. */
 
644
  uint key_infix_len;
628
645
  DYNAMIC_ARRAY min_max_ranges; /* Array of range ptrs for the MIN/MAX field. */
629
 
  uint32_t real_prefix_len; /* Length of key prefix extended with key_infix. */
630
 
  uint32_t real_key_parts;  /* A number of keyparts in the above value.      */
 
646
  uint real_prefix_len; /* Length of key prefix extended with key_infix. */
 
647
  uint real_key_parts;  /* A number of keyparts in the above value.      */
631
648
  List<Item_sum> *min_functions;
632
649
  List<Item_sum> *max_functions;
633
650
  List_iterator<Item_sum> *min_functions_it;
648
665
  void update_min_result();
649
666
  void update_max_result();
650
667
public:
651
 
  QUICK_GROUP_MIN_MAX_SELECT(Table *table, JOIN *join, bool have_min,
 
668
  QUICK_GROUP_MIN_MAX_SELECT(TABLE *table, JOIN *join, bool have_min,
652
669
                             bool have_max, KEY_PART_INFO *min_max_arg_part,
653
 
                             uint32_t group_prefix_len, uint32_t group_key_parts,
654
 
                             uint32_t used_key_parts, KEY *index_info, uint
 
670
                             uint group_prefix_len, uint group_key_parts,
 
671
                             uint used_key_parts, KEY *index_info, uint
655
672
                             use_index, double read_cost, ha_rows records, uint
656
 
                             key_infix_len, unsigned char *key_infix, MEM_ROOT
 
673
                             key_infix_len, uchar *key_infix, MEM_ROOT
657
674
                             *parent_alloc);
658
675
  ~QUICK_GROUP_MIN_MAX_SELECT();
659
676
  bool add_range(SEL_ARG *sel_range);
667
684
  bool unique_key_range() { return false; }
668
685
  int get_type() { return QS_TYPE_GROUP_MIN_MAX; }
669
686
  void add_keys_and_lengths(String *key_names, String *used_lengths);
 
687
#ifndef DBUG_OFF
 
688
  void dbug_dump(int indent, bool verbose);
 
689
#endif
670
690
};
671
691
 
672
692
 
673
693
class QUICK_SELECT_DESC: public QUICK_RANGE_SELECT
674
694
{
675
695
public:
676
 
  QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint32_t used_key_parts, 
 
696
  QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint used_key_parts, 
677
697
                    bool *create_err);
678
698
  int get_next();
679
699
  bool reverse_sorted() { return 1; }
681
701
private:
682
702
  bool range_reads_after_key(QUICK_RANGE *range);
683
703
#ifdef NOT_USED
684
 
  bool test_if_null_range(QUICK_RANGE *range, uint32_t used_key_parts);
 
704
  bool test_if_null_range(QUICK_RANGE *range, uint used_key_parts);
685
705
#endif
686
706
  int reset(void) { rev_it.rewind(); return QUICK_RANGE_SELECT::reset(); }
687
707
  List<QUICK_RANGE> rev_ranges;
693
713
 public:
694
714
  QUICK_SELECT_I *quick;        // If quick-select used
695
715
  COND          *cond;          // where condition
696
 
  Table *head;
 
716
  TABLE *head;
697
717
  IO_CACHE file;                // Positions to used records
698
718
  ha_rows records;              // Records in use if read from file
699
719
  double read_time;             // Time to read rows
705
725
  SQL_SELECT();
706
726
  ~SQL_SELECT();
707
727
  void cleanup();
708
 
  bool check_quick(Session *session, bool force_quick_range, ha_rows limit)
 
728
  bool check_quick(THD *thd, bool force_quick_range, ha_rows limit)
709
729
  {
710
730
    key_map tmp;
711
731
    tmp.set_all();
712
 
    return test_quick_select(session, tmp, 0, limit, force_quick_range, false) < 0;
 
732
    return test_quick_select(thd, tmp, 0, limit, force_quick_range, FALSE) < 0;
713
733
  }
714
734
  inline bool skip_record() { return cond ? cond->val_int() == 0 : 0; }
715
 
  int test_quick_select(Session *session, key_map keys, table_map prev_tables,
 
735
  int test_quick_select(THD *thd, key_map keys, table_map prev_tables,
716
736
                        ha_rows limit, bool force_quick_range, 
717
737
                        bool ordered_output);
718
738
};
719
739
 
720
 
QUICK_RANGE_SELECT *get_quick_select_for_ref(Session *session, Table *table,
 
740
QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table,
721
741
                                             struct st_table_ref *ref,
722
742
                                             ha_rows records);
723
 
uint32_t get_index_for_order(Table *table, order_st *order, ha_rows limit);
 
743
uint get_index_for_order(TABLE *table, ORDER *order, ha_rows limit);
724
744
 
725
745
#endif