← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/optimizer/range.h

  • Committer: Brian Aker
  • Date: 2011-02-22 06:12:02 UTC
  • mfrom: (2190.1.6 drizzle-build)
  • Revision ID: brian@tangent.org-20110222061202-k03czxykqy4x9hjs
List update, header fixes, multiple symbols, and David deletes some code.

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/optimizer/range.h
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 Sun Microsystems
 
4
 *  Copyright (C) 2008-2009 Sun Microsystems, Inc.
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
17
17
 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
18
18
 */
19
19
 
20
 
 
21
20
/* classes to use when handling where clause */
22
21
 
23
 
#ifndef DRIZZLED_OPT_RANGE_H
24
 
#define DRIZZLED_OPT_RANGE_H
 
22
#ifndef DRIZZLED_OPTIMIZER_RANGE_H
 
23
#define DRIZZLED_OPTIMIZER_RANGE_H
25
24
 
26
25
#include <drizzled/field.h>
27
 
#include <mysys/queues.h>
28
26
#include <drizzled/item/sum.h>
29
 
 
30
 
class JOIN;
 
27
#include <drizzled/table_reference.h>
 
28
 
 
29
#include <queue>
 
30
 
 
31
#include <boost/dynamic_bitset.hpp>
 
32
 
 
33
namespace drizzled
 
34
{
 
35
 
 
36
class Join;
 
37
class RorIntersectReadPlan; 
31
38
typedef class Item COND;
32
39
 
33
 
typedef struct st_handler_buffer HANDLER_BUFFER;
 
40
namespace internal
 
41
{
 
42
typedef struct st_io_cache IO_CACHE;
 
43
}
34
44
 
35
 
typedef struct st_key_part {
36
 
  uint16_t           key,part;
37
 
  /* See KEY_PART_INFO for meaning of the next two: */
38
 
  uint16_t           store_length, length;
39
 
  uint8_t            null_bit;
40
 
  /*
 
45
typedef struct st_key_part
 
46
{
 
47
  uint16_t key;
 
48
  uint16_t part;
 
49
  /* See KeyPartInfo for meaning of the next two: */
 
50
  uint16_t store_length;
 
51
  uint16_t length;
 
52
  uint8_t null_bit;
 
53
  /**
41
54
    Keypart flags (0 when this structure is used by partition pruning code
42
55
    for fake partitioning index description)
43
56
  */
44
57
  uint8_t flag;
45
 
  Field            *field;
46
 
  Field::imagetype image_type;
 
58
  Field *field;
47
59
} KEY_PART;
48
60
 
49
61
 
50
 
class QUICK_RANGE :public Sql_alloc {
51
 
 public:
52
 
  unsigned char *min_key,*max_key;
53
 
  uint16_t min_length,max_length,flag;
54
 
  key_part_map min_keypart_map, // bitmap of used keyparts in min_key
55
 
               max_keypart_map; // bitmap of used keyparts in max_key
56
 
#ifdef HAVE_purify
57
 
  uint16_t dummy;                                       /* Avoid warnings on 'flag' */
58
 
#endif
59
 
  QUICK_RANGE();                                /* Full range */
60
 
  QUICK_RANGE(const unsigned char *min_key_arg, uint32_t min_length_arg,
61
 
              key_part_map min_keypart_map_arg,
62
 
              const unsigned char *max_key_arg, uint32_t max_length_arg,
63
 
              key_part_map max_keypart_map_arg,
64
 
              uint32_t flag_arg)
65
 
    : min_key((unsigned char*) sql_memdup(min_key_arg,min_length_arg+1)),
66
 
      max_key((unsigned char*) sql_memdup(max_key_arg,max_length_arg+1)),
67
 
      min_length((uint16_t) min_length_arg),
68
 
      max_length((uint16_t) max_length_arg),
69
 
      flag((uint16_t) flag_arg),
70
 
      min_keypart_map(min_keypart_map_arg),
71
 
      max_keypart_map(max_keypart_map_arg)
72
 
    {
73
 
#ifdef HAVE_purify
74
 
      dummy=0;
75
 
#endif
76
 
    }
77
 
};
78
 
 
79
 
 
80
 
/*
 
62
namespace optimizer
 
63
{
 
64
 
 
65
class Parameter;
 
66
class SEL_ARG;
 
67
 
 
68
/**
81
69
  Quick select interface.
82
70
  This class is a parent for all QUICK_*_SELECT classes.
83
71
 
119
107
    delete quick;
120
108
 
121
109
*/
122
 
 
123
 
class QUICK_SELECT_I
 
110
class QuickSelectInterface
124
111
{
125
112
public:
126
113
  bool sorted;
127
 
  ha_rows records;  /* estimate of # of records to be retrieved */
128
 
  double  read_time; /* time to perform this retrieval          */
129
 
  Table   *head;
130
 
  /*
 
114
  ha_rows records; /**< estimate of # of records to be retrieved */
 
115
  double read_time; /**< time to perform this retrieval */
 
116
  Table *head;
 
117
  /**
131
118
    Index this quick select uses, or MAX_KEY for quick selects
132
119
    that use several indexes
133
120
  */
134
121
  uint32_t index;
135
 
 
136
 
  /*
 
122
  /**
137
123
    Total length of first used_key_parts parts of the key.
138
124
    Applicable if index!= MAX_KEY.
139
125
  */
140
126
  uint32_t max_used_key_length;
141
 
 
142
 
  /*
143
 
    Max. number of (first) key parts this quick select uses for retrieval.
 
127
  /**
 
128
    Maximum number of (first) key parts this quick select uses for retrieval.
144
129
    eg. for "(key1p1=c1 AND key1p2=c2) OR key1p1=c2" used_key_parts == 2.
145
130
    Applicable if index!= MAX_KEY.
146
131
 
147
132
    For QUICK_GROUP_MIN_MAX_SELECT it includes MIN/MAX argument keyparts.
148
133
  */
149
134
  uint32_t used_key_parts;
150
 
 
151
 
  QUICK_SELECT_I();
152
 
  virtual ~QUICK_SELECT_I(){};
153
 
 
154
 
  /*
155
 
    Do post-constructor initialization.
156
 
    SYNOPSIS
157
 
      init()
158
 
 
159
 
    init() performs initializations that should have been in constructor if
160
 
    it was possible to return errors from constructors. The join optimizer may
161
 
    create and then delete quick selects without retrieving any rows so init()
162
 
    must not contain any IO or CPU intensive code.
163
 
 
164
 
    If init() call fails the only valid action is to delete this quick select,
165
 
    reset() and get_next() must not be called.
166
 
 
167
 
    RETURN
168
 
      0      OK
169
 
      other  Error code
170
 
  */
171
 
  virtual int  init() = 0;
172
 
 
173
 
  /*
174
 
    Initialize quick select for row retrieval.
175
 
    SYNOPSIS
176
 
      reset()
177
 
 
178
 
    reset() should be called when it is certain that row retrieval will be
179
 
    necessary. This call may do heavyweight initialization like buffering first
180
 
    N records etc. If reset() call fails get_next() must not be called.
181
 
    Note that reset() may be called several times if 
182
 
     * the quick select is executed in a subselect
183
 
     * a JOIN buffer is used
184
 
    
185
 
    RETURN
186
 
      0      OK
187
 
      other  Error code
188
 
  */
189
 
  virtual int  reset(void) = 0;
190
 
 
191
 
  virtual int  get_next() = 0;   /* get next record to retrieve */
192
 
 
193
 
  /* Range end should be called when we have looped over the whole index */
 
135
  /**
 
136
   * The rowid of last row retrieved by this quick select. This is used only when
 
137
   * doing ROR-index_merge selects
 
138
   */
 
139
  unsigned char *last_rowid;
 
140
 
 
141
  /**
 
142
   * Table record buffer used by this quick select.
 
143
   */
 
144
  unsigned char *record;
 
145
 
 
146
  QuickSelectInterface();
 
147
  virtual ~QuickSelectInterface(){};
 
148
 
 
149
  /**
 
150
   * Do post-constructor initialization.
 
151
   *
 
152
   * @details
 
153
   *
 
154
   * Performs initializations that should have been in constructor if
 
155
   * it was possible to return errors from constructors. The join optimizer may
 
156
   * create and then delete quick selects without retrieving any rows so init()
 
157
   * must not contain any IO or CPU intensive code.
 
158
   *
 
159
   * If init() call fails the only valid action is to delete this quick select,
 
160
   * reset() and get_next() must not be called.
 
161
   *
 
162
   * @retval
 
163
   *  0      OK
 
164
   * @retval
 
165
   *  other  Error code
 
166
  */
 
167
  virtual int init() = 0;
 
168
 
 
169
  /**
 
170
   * Initializes quick select for row retrieval.
 
171
   *
 
172
   * @details
 
173
   *
 
174
   * Should be called when it is certain that row retrieval will be
 
175
   * necessary. This call may do heavyweight initialization like buffering first
 
176
   * N records etc. If reset() call fails get_next() must not be called.
 
177
   * Note that reset() may be called several times if
 
178
   * - the quick select is executed in a subselect
 
179
   * - a JOIN buffer is used
 
180
   *
 
181
   * @retval 
 
182
   *  0      OK
 
183
   * @retval
 
184
   *  other  Error code
 
185
   */
 
186
  virtual int reset(void) = 0;
 
187
  /** Gets next record to retrieve */
 
188
  virtual int get_next() = 0;
 
189
 
 
190
  /** Range end should be called when we have looped over the whole index */
194
191
  virtual void range_end() {}
195
192
 
196
 
  virtual bool reverse_sorted() = 0;
197
 
  virtual bool unique_key_range() { return false; }
198
 
 
199
 
  enum {
200
 
    QS_TYPE_RANGE = 0,
201
 
    QS_TYPE_INDEX_MERGE = 1,
202
 
    QS_TYPE_RANGE_DESC = 2,
203
 
    QS_TYPE_ROR_INTERSECT = 4,
204
 
    QS_TYPE_ROR_UNION = 5,
205
 
    QS_TYPE_GROUP_MIN_MAX = 6
 
193
  virtual bool reverse_sorted() const = 0;
 
194
 
 
195
  virtual bool unique_key_range() const
 
196
  {
 
197
    return false;
 
198
  }
 
199
 
 
200
  enum 
 
201
  {
 
202
    QS_TYPE_RANGE= 0,
 
203
    QS_TYPE_INDEX_MERGE= 1,
 
204
    QS_TYPE_RANGE_DESC= 2,
 
205
    QS_TYPE_ROR_INTERSECT= 4,
 
206
    QS_TYPE_ROR_UNION= 5,
 
207
    QS_TYPE_GROUP_MIN_MAX= 6
206
208
  };
207
209
 
208
 
  /* Get type of this quick select - one of the QS_TYPE_* values */
209
 
  virtual int get_type() = 0;
 
210
  /** Returns the type of this quick select - one of the QS_TYPE_* values */
 
211
  virtual int get_type() const = 0;
210
212
 
211
 
  /*
212
 
    Initialize this quick select as a merged scan inside a ROR-union or a ROR-
213
 
    intersection scan. The caller must not additionally call init() if this
214
 
    function is called.
215
 
    SYNOPSIS
216
 
      init_ror_merged_scan()
217
 
        reuse_handler  If true, the quick select may use table->handler,
218
 
                       otherwise it must create and use a separate handler
219
 
                       object.
220
 
    RETURN
221
 
      0     Ok
222
 
      other Error
223
 
  */
 
213
  /**
 
214
   * Initialize this quick select as a merged scan inside a ROR-union or a ROR-
 
215
   * intersection scan. The caller must not additionally call init() if this
 
216
   * function is called.
 
217
   *
 
218
   * @param If true, the quick select may use table->Cursor,
 
219
   *        otherwise it must create and use a separate Cursor
 
220
   *        object.
 
221
   *
 
222
   * @retval
 
223
   *  0     Ok
 
224
   * @retval
 
225
   *  other Error
 
226
   */
224
227
  virtual int init_ror_merged_scan(bool)
225
 
  { assert(0); return 1; }
 
228
  {
 
229
    assert(0);
 
230
    return 1;
 
231
  }
226
232
 
227
 
  /*
228
 
    Save ROWID of last retrieved row in file->ref. This used in ROR-merging.
229
 
  */
 
233
  /**
 
234
   * Save ROWID of last retrieved row in file->ref. This used in ROR-merging.
 
235
   */
230
236
  virtual void save_last_pos(){};
231
237
 
232
 
  /*
233
 
    Append comma-separated list of keys this quick select uses to key_names;
234
 
    append comma-separated list of corresponding used lengths to used_lengths.
235
 
    This is used by select_describe.
236
 
  */
237
 
  virtual void add_keys_and_lengths(String *key_names,
238
 
                                    String *used_lengths)=0;
239
 
 
240
 
  /*
241
 
    Append text representation of quick select structure (what and how is
242
 
    merged) to str. The result is added to "Extra" field in EXPLAIN output.
243
 
    This function is implemented only by quick selects that merge other quick
244
 
    selects output and/or can produce output suitable for merging.
245
 
  */
246
 
  virtual void add_info_string(String *) {};
247
 
  /*
248
 
    Return 1 if any index used by this quick select
249
 
    uses field which is marked in passed bitmap.
250
 
  */
251
 
  virtual bool is_keys_used(const MY_BITMAP *fields);
252
 
 
253
 
  /*
254
 
    rowid of last row retrieved by this quick select. This is used only when
255
 
    doing ROR-index_merge selects
256
 
  */
257
 
  unsigned char    *last_rowid;
258
 
 
259
 
  /*
260
 
    Table record buffer used by this quick select.
261
 
  */
262
 
  unsigned char    *record;
 
238
  /**
 
239
   * Append comma-separated list of keys this quick select uses to key_names;
 
240
   * append comma-separated list of corresponding used lengths to used_lengths.
 
241
   * 
 
242
   * @note This is used by during explain plan.
 
243
   */
 
244
  virtual void add_keys_and_lengths(std::string *key_names,
 
245
                                    std::string *used_lengths)=0;
 
246
 
 
247
  /**
 
248
   * Append text representation of quick select structure (what and how is
 
249
   * merged) to str. The result is added to "Extra" field in EXPLAIN output.
 
250
   *
 
251
   * @note
 
252
   *
 
253
   * This function is implemented only by quick selects that merge other quick
 
254
   * selects output and/or can produce output suitable for merging.
 
255
   */
 
256
  virtual void add_info_string(std::string *)
 
257
  {}
 
258
 
 
259
  /**
 
260
   * Returns true if any index used by this quick select
 
261
   * uses field which is marked in passed bitmap.
 
262
   */
 
263
  virtual bool is_keys_used(const boost::dynamic_bitset<>& fields);
263
264
};
264
265
 
265
 
 
266
266
struct st_qsel_param;
267
 
class PARAM;
268
 
class SEL_ARG;
269
 
 
270
 
 
271
 
/*
272
 
  MRR range sequence, array<QUICK_RANGE> implementation: sequence traversal
273
 
  context.
274
 
*/
 
267
class QuickRange;
 
268
class QuickRangeSelect;
 
269
 
 
270
/**
 
271
 * MRR range sequence, array<QuickRange> implementation: sequence traversal
 
272
 * context.
 
273
 */
275
274
typedef struct st_quick_range_seq_ctx
276
275
{
277
 
  QUICK_RANGE **first;
278
 
  QUICK_RANGE **cur;
279
 
  QUICK_RANGE **last;
280
 
} QUICK_RANGE_SEQ_CTX;
 
276
  QuickRange **first;
 
277
  QuickRange **cur;
 
278
  QuickRange **last;
 
279
} QuickRangeSequenceContext;
281
280
 
282
281
range_seq_t quick_range_seq_init(void *init_param, uint32_t n_ranges, uint32_t flags);
 
282
 
283
283
uint32_t quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range);
284
284
 
285
 
 
286
 
/*
287
 
  Quick select that does a range scan on a single key. The records are
288
 
  returned in key order.
289
 
*/
290
 
class QUICK_RANGE_SELECT : public QUICK_SELECT_I
291
 
{
292
 
protected:
293
 
  handler *file;
294
 
  DYNAMIC_ARRAY ranges;     /* ordered array of range ptrs */
295
 
 
296
 
  /* Members to deal with case when this quick select is a ROR-merged scan */
297
 
  bool in_ror_merged_scan;
298
 
  MY_BITMAP column_bitmap, *save_read_set, *save_write_set;
299
 
  bool free_file;   /* TRUE <=> this->file is "owned" by this quick select */
300
 
 
301
 
  /* Range pointers to be used when not using MRR interface */
302
 
  QUICK_RANGE **cur_range;  /* current element in ranges  */
303
 
  QUICK_RANGE *last_range;
304
 
  
305
 
  /* Members needed to use the MRR interface */
306
 
  QUICK_RANGE_SEQ_CTX qr_traversal_ctx;
307
 
public:
308
 
  uint32_t mrr_flags; /* Flags to be used with MRR interface */
309
 
protected:
310
 
  uint32_t mrr_buf_size; /* copy from session->variables.read_rnd_buff_size */  
311
 
  HANDLER_BUFFER *mrr_buf_desc; /* the handler buffer */
312
 
 
313
 
  /* Info about index we're scanning */
314
 
  KEY_PART *key_parts;
315
 
  KEY_PART_INFO *key_part_info;
316
 
  
317
 
  bool dont_free; /* Used by QUICK_SELECT_DESC */
318
 
 
319
 
  int cmp_next(QUICK_RANGE *range);
320
 
  int cmp_prev(QUICK_RANGE *range);
321
 
  bool row_in_ranges();
322
 
public:
323
 
  MEM_ROOT alloc;
324
 
 
325
 
  QUICK_RANGE_SELECT(Session *session, Table *table,uint32_t index_arg,bool no_alloc,
326
 
                     MEM_ROOT *parent_alloc, bool *create_err);
327
 
  ~QUICK_RANGE_SELECT();
328
 
 
329
 
  int init();
330
 
  int reset(void);
331
 
  int get_next();
332
 
  void range_end();
333
 
  int get_next_prefix(uint32_t prefix_length, key_part_map keypart_map,
334
 
                      unsigned char *cur_prefix);
335
 
  bool reverse_sorted() { return 0; }
336
 
  bool unique_key_range();
337
 
  int init_ror_merged_scan(bool reuse_handler);
338
 
  void save_last_pos();
339
 
  int get_type() { return QS_TYPE_RANGE; }
340
 
  void add_keys_and_lengths(String *key_names, String *used_lengths);
341
 
  void add_info_string(String *str);
342
 
private:
343
 
  /* Used only by QUICK_SELECT_DESC */
344
 
  QUICK_RANGE_SELECT(const QUICK_RANGE_SELECT& org) : QUICK_SELECT_I()
345
 
  {
346
 
    memmove(this, &org, sizeof(*this));
347
 
    /* 
348
 
      Use default MRR implementation for reverse scans. No table engine
349
 
      currently can do an MRR scan with output in reverse index order.
350
 
    */
351
 
    mrr_buf_desc= NULL;
352
 
    mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
353
 
    mrr_buf_size= 0;
354
 
  }
355
 
  friend class TRP_ROR_INTERSECT;
356
 
  friend
357
 
  QUICK_RANGE_SELECT *get_quick_select_for_ref(Session *session, Table *table,
358
 
                                               struct st_table_ref *ref,
359
 
                                               ha_rows records);
360
 
  friend bool get_quick_keys(PARAM *param, QUICK_RANGE_SELECT *quick, 
361
 
                             KEY_PART *key, SEL_ARG *key_tree, 
362
 
                             unsigned char *min_key, uint32_t min_key_flag,
363
 
                             unsigned char *max_key, uint32_t max_key_flag);
364
 
  friend QUICK_RANGE_SELECT *get_quick_select(PARAM*,uint32_t idx,
365
 
                                              SEL_ARG *key_tree,
366
 
                                              uint32_t mrr_flags,
367
 
                                              uint32_t mrr_buf_size,
368
 
                                              MEM_ROOT *alloc);
369
 
  friend class QUICK_SELECT_DESC;
370
 
  friend class QUICK_INDEX_MERGE_SELECT;
371
 
  friend class QUICK_ROR_INTERSECT_SELECT;
372
 
  friend class QUICK_GROUP_MIN_MAX_SELECT;
373
 
  friend uint32_t quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range);
374
 
  friend range_seq_t quick_range_seq_init(void *init_param,
375
 
                                          uint32_t n_ranges, uint32_t flags);
376
 
  friend void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
377
 
                              bool distinct,const char *message);
378
 
};
379
 
 
380
 
 
381
 
/*
382
 
  QUICK_INDEX_MERGE_SELECT - index_merge access method quick select.
383
 
 
384
 
    QUICK_INDEX_MERGE_SELECT uses
385
 
     * QUICK_RANGE_SELECTs to get rows
386
 
     * Unique class to remove duplicate rows
387
 
 
388
 
  INDEX MERGE OPTIMIZER
389
 
    Current implementation doesn't detect all cases where index_merge could
390
 
    be used, in particular:
391
 
     * index_merge will never be used if range scan is possible (even if
392
 
       range scan is more expensive)
393
 
 
394
 
     * index_merge+'using index' is not supported (this the consequence of
395
 
       the above restriction)
396
 
 
397
 
     * If WHERE part contains complex nested AND and OR conditions, some ways
398
 
       to retrieve rows using index_merge will not be considered. The choice
399
 
       of read plan may depend on the order of conjuncts/disjuncts in WHERE
400
 
       part of the query, see comments near imerge_list_or_list and
401
 
       SEL_IMERGE::or_sel_tree_with_checks functions for details.
402
 
 
403
 
     * There is no "index_merge_ref" method (but index_merge on non-first
404
 
       table in join is possible with 'range checked for each record').
405
 
 
406
 
    See comments around SEL_IMERGE class and test_quick_select for more
407
 
    details.
408
 
 
409
 
  ROW RETRIEVAL ALGORITHM
410
 
 
411
 
    index_merge uses Unique class for duplicates removal.  index_merge takes
412
 
    advantage of Clustered Primary Key (CPK) if the table has one.
413
 
    The index_merge algorithm consists of two phases:
414
 
 
415
 
    Phase 1 (implemented in QUICK_INDEX_MERGE_SELECT::prepare_unique):
416
 
    prepare()
417
 
    {
418
 
      activate 'index only';
419
 
      while(retrieve next row for non-CPK scan)
420
 
      {
421
 
        if (there is a CPK scan and row will be retrieved by it)
422
 
          skip this row;
423
 
        else
424
 
          put its rowid into Unique;
425
 
      }
426
 
      deactivate 'index only';
427
 
    }
428
 
 
429
 
    Phase 2 (implemented as sequence of QUICK_INDEX_MERGE_SELECT::get_next
430
 
    calls):
431
 
 
432
 
    fetch()
433
 
    {
434
 
      retrieve all rows from row pointers stored in Unique;
435
 
      free Unique;
436
 
      retrieve all rows for CPK scan;
437
 
    }
438
 
*/
439
 
 
440
 
class QUICK_INDEX_MERGE_SELECT : public QUICK_SELECT_I
441
 
{
442
 
public:
443
 
  QUICK_INDEX_MERGE_SELECT(Session *session, Table *table);
444
 
  ~QUICK_INDEX_MERGE_SELECT();
445
 
 
446
 
  int  init();
447
 
  int  reset(void);
448
 
  int  get_next();
449
 
  bool reverse_sorted() { return false; }
450
 
  bool unique_key_range() { return false; }
451
 
  int get_type() { return QS_TYPE_INDEX_MERGE; }
452
 
  void add_keys_and_lengths(String *key_names, String *used_lengths);
453
 
  void add_info_string(String *str);
454
 
  bool is_keys_used(const MY_BITMAP *fields);
455
 
 
456
 
  bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range);
457
 
 
458
 
  /* range quick selects this index_merge read consists of */
459
 
  List<QUICK_RANGE_SELECT> quick_selects;
460
 
 
461
 
  /* quick select that uses clustered primary key (NULL if none) */
462
 
  QUICK_RANGE_SELECT* pk_quick_select;
463
 
 
464
 
  /* true if this select is currently doing a clustered PK scan */
465
 
  bool  doing_pk_scan;
466
 
 
467
 
  MEM_ROOT alloc;
468
 
  Session *session;
469
 
  int read_keys_and_merge();
470
 
 
471
 
  /* used to get rows collected in Unique */
472
 
  READ_RECORD read_record;
473
 
};
474
 
 
475
 
 
476
 
/*
477
 
  Rowid-Ordered Retrieval (ROR) index intersection quick select.
478
 
  This quick select produces intersection of row sequences returned
479
 
  by several QUICK_RANGE_SELECTs it "merges".
480
 
 
481
 
  All merged QUICK_RANGE_SELECTs must return rowids in rowid order.
482
 
  QUICK_ROR_INTERSECT_SELECT will return rows in rowid order, too.
483
 
 
484
 
  All merged quick selects retrieve {rowid, covered_fields} tuples (not full
485
 
  table records).
486
 
  QUICK_ROR_INTERSECT_SELECT retrieves full records if it is not being used
487
 
  by QUICK_ROR_INTERSECT_SELECT and all merged quick selects together don't
488
 
  cover needed all fields.
489
 
 
490
 
  If one of the merged quick selects is a Clustered PK range scan, it is
491
 
  used only to filter rowid sequence produced by other merged quick selects.
492
 
*/
493
 
 
494
 
class QUICK_ROR_INTERSECT_SELECT : public QUICK_SELECT_I
495
 
{
496
 
public:
497
 
  QUICK_ROR_INTERSECT_SELECT(Session *session, Table *table,
498
 
                             bool retrieve_full_rows,
499
 
                             MEM_ROOT *parent_alloc);
500
 
  ~QUICK_ROR_INTERSECT_SELECT();
501
 
 
502
 
  int  init();
503
 
  int  reset(void);
504
 
  int  get_next();
505
 
  bool reverse_sorted() { return false; }
506
 
  bool unique_key_range() { return false; }
507
 
  int get_type() { return QS_TYPE_ROR_INTERSECT; }
508
 
  void add_keys_and_lengths(String *key_names, String *used_lengths);
509
 
  void add_info_string(String *str);
510
 
  bool is_keys_used(const MY_BITMAP *fields);
511
 
  int init_ror_merged_scan(bool reuse_handler);
512
 
  bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range);
513
 
 
514
 
  /*
515
 
    Range quick selects this intersection consists of, not including
516
 
    cpk_quick.
517
 
  */
518
 
  List<QUICK_RANGE_SELECT> quick_selects;
519
 
 
520
 
  /*
521
 
    Merged quick select that uses Clustered PK, if there is one. This quick
522
 
    select is not used for row retrieval, it is used for row retrieval.
523
 
  */
524
 
  QUICK_RANGE_SELECT *cpk_quick;
525
 
 
526
 
  MEM_ROOT alloc; /* Memory pool for this and merged quick selects data. */
527
 
  Session *session;       /* current thread */
528
 
  bool need_to_fetch_row; /* if true, do retrieve full table records. */
529
 
  /* in top-level quick select, true if merged scans where initialized */
530
 
  bool scans_inited; 
531
 
};
532
 
 
533
 
 
534
 
/*
535
 
  Rowid-Ordered Retrieval index union select.
536
 
  This quick select produces union of row sequences returned by several
537
 
  quick select it "merges".
538
 
 
539
 
  All merged quick selects must return rowids in rowid order.
540
 
  QUICK_ROR_UNION_SELECT will return rows in rowid order, too.
541
 
 
542
 
  All merged quick selects are set not to retrieve full table records.
543
 
  ROR-union quick select always retrieves full records.
544
 
 
545
 
*/
546
 
 
547
 
class QUICK_ROR_UNION_SELECT : public QUICK_SELECT_I
548
 
{
549
 
public:
550
 
  QUICK_ROR_UNION_SELECT(Session *session, Table *table);
551
 
  ~QUICK_ROR_UNION_SELECT();
552
 
 
553
 
  int  init();
554
 
  int  reset(void);
555
 
  int  get_next();
556
 
  bool reverse_sorted() { return false; }
557
 
  bool unique_key_range() { return false; }
558
 
  int get_type() { return QS_TYPE_ROR_UNION; }
559
 
  void add_keys_and_lengths(String *key_names, String *used_lengths);
560
 
  void add_info_string(String *str);
561
 
  bool is_keys_used(const MY_BITMAP *fields);
562
 
 
563
 
  bool push_quick_back(QUICK_SELECT_I *quick_sel_range);
564
 
 
565
 
  List<QUICK_SELECT_I> quick_selects; /* Merged quick selects */
566
 
 
567
 
  QUEUE queue;    /* Priority queue for merge operation */
568
 
  MEM_ROOT alloc; /* Memory pool for this and merged quick selects data. */
569
 
 
570
 
  Session *session;             /* current thread */
571
 
  unsigned char *cur_rowid;      /* buffer used in get_next() */
572
 
  unsigned char *prev_rowid;     /* rowid of last row returned by get_next() */
573
 
  bool have_prev_rowid; /* true if prev_rowid has valid data */
574
 
  uint32_t rowid_length;    /* table rowid length */
575
 
private:
576
 
  static int queue_cmp(void *arg, unsigned char *val1, unsigned char *val2);
577
 
  bool scans_inited; 
578
 
};
579
 
 
580
 
 
581
 
/*
582
 
  Index scan for GROUP-BY queries with MIN/MAX aggregate functions.
583
 
 
584
 
  This class provides a specialized index access method for GROUP-BY queries
585
 
  of the forms:
586
 
 
587
 
       SELECT A_1,...,A_k, [B_1,...,B_m], [MIN(C)], [MAX(C)]
588
 
         FROM T
589
 
        WHERE [RNG(A_1,...,A_p ; where p <= k)]
590
 
         [AND EQ(B_1,...,B_m)]
591
 
         [AND PC(C)]
592
 
         [AND PA(A_i1,...,A_iq)]
593
 
       GROUP BY A_1,...,A_k;
594
 
 
595
 
    or
596
 
 
597
 
       SELECT DISTINCT A_i1,...,A_ik
598
 
         FROM T
599
 
        WHERE [RNG(A_1,...,A_p ; where p <= k)]
600
 
         [AND PA(A_i1,...,A_iq)];
601
 
 
602
 
  where all selected fields are parts of the same index.
603
 
  The class of queries that can be processed by this quick select is fully
604
 
  specified in the description of get_best_trp_group_min_max() in opt_range.cc.
605
 
 
606
 
  The get_next() method directly produces result tuples, thus obviating the
607
 
  need to call end_send_group() because all grouping is already done inside
608
 
  get_next().
609
 
 
610
 
  Since one of the requirements is that all select fields are part of the same
611
 
  index, this class produces only index keys, and not complete records.
612
 
*/
613
 
 
614
 
class QUICK_GROUP_MIN_MAX_SELECT : public QUICK_SELECT_I
615
 
{
616
 
private:
617
 
  handler *file;         /* The handler used to get data. */
618
 
  JOIN *join;            /* Descriptor of the current query */
619
 
  KEY  *index_info;      /* The index chosen for data access */
620
 
  unsigned char *record;          /* Buffer where the next record is returned. */
621
 
  unsigned char *tmp_record;      /* Temporary storage for next_min(), next_max(). */
622
 
  unsigned char *group_prefix;    /* Key prefix consisting of the GROUP fields. */
623
 
  uint32_t group_prefix_len; /* Length of the group prefix. */
624
 
  uint32_t group_key_parts;  /* A number of keyparts in the group prefix */
625
 
  unsigned char *last_prefix;     /* Prefix of the last group for detecting EOF. */
626
 
  bool have_min;         /* Specify whether we are computing */
627
 
  bool have_max;         /*   a MIN, a MAX, or both.         */
628
 
  bool seen_first_key;   /* Denotes whether the first key was retrieved.*/
629
 
  KEY_PART_INFO *min_max_arg_part; /* The keypart of the only argument field */
630
 
                                   /* of all MIN/MAX functions.              */
631
 
  uint32_t min_max_arg_len;  /* The length of the MIN/MAX argument field */
632
 
  unsigned char *key_infix;       /* Infix of constants from equality predicates. */
633
 
  uint32_t key_infix_len;
634
 
  DYNAMIC_ARRAY min_max_ranges; /* Array of range ptrs for the MIN/MAX field. */
635
 
  uint32_t real_prefix_len; /* Length of key prefix extended with key_infix. */
636
 
  uint32_t real_key_parts;  /* A number of keyparts in the above value.      */
637
 
  List<Item_sum> *min_functions;
638
 
  List<Item_sum> *max_functions;
639
 
  List_iterator<Item_sum> *min_functions_it;
640
 
  List_iterator<Item_sum> *max_functions_it;
641
 
public:
642
 
  /*
643
 
    The following two members are public to allow easy access from
644
 
    TRP_GROUP_MIN_MAX::make_quick()
645
 
  */
646
 
  MEM_ROOT alloc; /* Memory pool for this and quick_prefix_select data. */
647
 
  QUICK_RANGE_SELECT *quick_prefix_select;/* For retrieval of group prefixes. */
648
 
private:
649
 
  int  next_prefix();
650
 
  int  next_min_in_range();
651
 
  int  next_max_in_range();
652
 
  int  next_min();
653
 
  int  next_max();
654
 
  void update_min_result();
655
 
  void update_max_result();
656
 
public:
657
 
  QUICK_GROUP_MIN_MAX_SELECT(Table *table, JOIN *join, bool have_min,
658
 
                             bool have_max, KEY_PART_INFO *min_max_arg_part,
659
 
                             uint32_t group_prefix_len, uint32_t group_key_parts,
660
 
                             uint32_t used_key_parts, KEY *index_info, uint
661
 
                             use_index, double read_cost, ha_rows records, uint
662
 
                             key_infix_len, unsigned char *key_infix, MEM_ROOT
663
 
                             *parent_alloc);
664
 
  ~QUICK_GROUP_MIN_MAX_SELECT();
665
 
  bool add_range(SEL_ARG *sel_range);
666
 
  void update_key_stat();
667
 
  void adjust_prefix_ranges();
668
 
  bool alloc_buffers();
669
 
  int init();
670
 
  int reset();
671
 
  int get_next();
672
 
  bool reverse_sorted() { return false; }
673
 
  bool unique_key_range() { return false; }
674
 
  int get_type() { return QS_TYPE_GROUP_MIN_MAX; }
675
 
  void add_keys_and_lengths(String *key_names, String *used_lengths);
676
 
};
677
 
 
678
 
 
679
 
class QUICK_SELECT_DESC: public QUICK_RANGE_SELECT
680
 
{
681
 
public:
682
 
  QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint32_t used_key_parts, 
683
 
                    bool *create_err);
684
 
  int get_next();
685
 
  bool reverse_sorted() { return 1; }
686
 
  int get_type() { return QS_TYPE_RANGE_DESC; }
687
 
private:
688
 
  bool range_reads_after_key(QUICK_RANGE *range);
689
 
#ifdef NOT_USED
690
 
  bool test_if_null_range(QUICK_RANGE *range, uint32_t used_key_parts);
691
 
#endif
692
 
  int reset(void) { rev_it.rewind(); return QUICK_RANGE_SELECT::reset(); }
693
 
  List<QUICK_RANGE> rev_ranges;
694
 
  List_iterator<QUICK_RANGE> rev_it;
695
 
};
696
 
 
697
 
 
698
 
class SQL_SELECT :public Sql_alloc {
 
285
/**
 
286
 * Executor class for SELECT statements.
 
287
 *
 
288
 * @details
 
289
 *
 
290
 * The QuickSelectInterface member variable is the implementor
 
291
 * of the SELECT execution.
 
292
 */
 
293
class SqlSelect : public memory::SqlAlloc 
 
294
{
699
295
 public:
700
 
  QUICK_SELECT_I *quick;        // If quick-select used
701
 
  COND          *cond;          // where condition
 
296
  QuickSelectInterface *quick; /**< If quick-select used */
 
297
  COND *cond; /**< where condition */
702
298
  Table *head;
703
 
  IO_CACHE file;                // Positions to used records
704
 
  ha_rows records;              // Records in use if read from file
705
 
  double read_time;             // Time to read rows
706
 
  key_map quick_keys;           // Possible quick keys
707
 
  key_map needed_reg;           // Possible quick keys after prev tables.
708
 
  table_map const_tables,read_tables;
709
 
  bool  free_cond;
 
299
  internal::IO_CACHE *file; /**< Positions to used records */
 
300
  ha_rows records; /**< Records in use if read from file */
 
301
  double read_time; /**< Time to read rows */
 
302
  key_map quick_keys; /**< Possible quick keys */
 
303
  key_map needed_reg; /**< Possible quick keys after prev tables. */
 
304
  table_map const_tables;
 
305
  table_map read_tables;
 
306
  bool free_cond;
710
307
 
711
 
  SQL_SELECT();
712
 
  ~SQL_SELECT();
 
308
  SqlSelect();
 
309
  ~SqlSelect();
713
310
  void cleanup();
714
311
  bool check_quick(Session *session, bool force_quick_range, ha_rows limit);
715
312
  bool skip_record();
718
315
                        bool ordered_output);
719
316
};
720
317
 
721
 
QUICK_RANGE_SELECT *get_quick_select_for_ref(Session *session, Table *table,
722
 
                                             struct st_table_ref *ref,
723
 
                                             ha_rows records);
724
 
uint32_t get_index_for_order(Table *table, order_st *order, ha_rows limit);
725
 
 
726
 
#endif
 
318
QuickRangeSelect *get_quick_select_for_ref(Session *session, 
 
319
                                           Table *table,
 
320
                                           table_reference_st *ref,
 
321
                                           ha_rows records);
 
322
 
 
323
/*
 
324
  Create a QuickRangeSelect from given key and SEL_ARG tree for that key.
 
325
 
 
326
  SYNOPSIS
 
327
    get_quick_select()
 
328
      param
 
329
      idx            Index of used key in param->key.
 
330
      key_tree       SEL_ARG tree for the used key
 
331
      mrr_flags      MRR parameter for quick select
 
332
      mrr_buf_size   MRR parameter for quick select
 
333
      parent_alloc   If not NULL, use it to allocate memory for
 
334
                     quick select data. Otherwise use quick->alloc.
 
335
  NOTES
 
336
    The caller must call QUICK_SELECT::init for returned quick select.
 
337
 
 
338
    CAUTION! This function may change session->mem_root to a memory::Root which will be
 
339
    deallocated when the returned quick select is deleted.
 
340
 
 
341
  RETURN
 
342
    NULL on error
 
343
    otherwise created quick select
 
344
*/
 
345
QuickRangeSelect *get_quick_select(Parameter *param,
 
346
                                   uint32_t index,
 
347
                                   SEL_ARG *key_tree, 
 
348
                                   uint32_t mrr_flags,
 
349
                                   uint32_t mrr_buf_size, 
 
350
                                   memory::Root *alloc);
 
351
 
 
352
uint32_t get_index_for_order(Table *table, Order *order, ha_rows limit);
 
353
 
 
354
SqlSelect *make_select(Table *head, 
 
355
                       table_map const_tables,
 
356
                       table_map read_tables, 
 
357
                       COND *conds,
 
358
                       bool allow_null_cond,
 
359
                       int *error);
 
360
 
 
361
bool get_quick_keys(Parameter *param, 
 
362
                    QuickRangeSelect *quick,
 
363
                    KEY_PART *key,
 
364
                    SEL_ARG *key_tree, 
 
365
                    unsigned char *min_key,
 
366
                    uint32_t min_key_flag,
 
367
                    unsigned char *max_key,
 
368
                    uint32_t max_key_flag);
 
369
 
 
370
} /* namespace optimizer */
 
371
 
 
372
} /* namespace drizzled */
 
373
 
 
374
#endif /* DRIZZLED_OPTIMIZER_RANGE_H */