← 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: 2010-02-07 01:33:54 UTC
  • Revision ID: brian@gaz-20100207013354-d2pg1n68u5c09pgo
Remove giant include header to its own file.

Show diffs side-by-side

added added

removed removed

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