← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/optimizer/range.h

pandora-build v0.100 - Fixes several bugs found by cb1kenobi. Add several thoughts from folks at LCA.

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
class JOIN;
 
31
class TRP_ROR_INTERSECT; 
 
32
typedef class Item COND;
 
33
typedef struct st_io_cache IO_CACHE;
 
34
 
 
35
typedef struct st_handler_buffer HANDLER_BUFFER;
 
36
 
 
37
typedef struct st_key_part
 
38
{
 
39
  uint16_t key;
 
40
  uint16_t part;
28
41
  /* See KEY_PART_INFO for meaning of the next two: */
29
 
  uint16_t           store_length, length;
30
 
  uint8_t            null_bit;
31
 
  /*
 
42
  uint16_t store_length;
 
43
  uint16_t length;
 
44
  uint8_t null_bit;
 
45
  /**
32
46
    Keypart flags (0 when this structure is used by partition pruning code
33
47
    for fake partitioning index description)
34
48
  */
35
49
  uint8_t flag;
36
 
  Field            *field;
37
 
  Field::imagetype image_type;
 
50
  Field *field;
38
51
} KEY_PART;
39
52
 
40
53
 
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
 
/*
 
54
namespace drizzled
 
55
{
 
56
 
 
57
namespace optimizer
 
58
{
 
59
 
 
60
class Parameter;
 
61
class SEL_ARG;
 
62
 
 
63
/**
72
64
  Quick select interface.
73
65
  This class is a parent for all QUICK_*_SELECT classes.
74
66
 
110
102
    delete quick;
111
103
 
112
104
*/
113
 
 
114
 
class QUICK_SELECT_I
 
105
class QuickSelectInterface
115
106
{
116
107
public:
117
108
  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
 
  /*
 
109
  ha_rows records; /**< estimate of # of records to be retrieved */
 
110
  double read_time; /**< time to perform this retrieval */
 
111
  Table *head;
 
112
  /**
122
113
    Index this quick select uses, or MAX_KEY for quick selects
123
114
    that use several indexes
124
115
  */
125
 
  uint index;
126
 
 
127
 
  /*
 
116
  uint32_t index;
 
117
  /**
128
118
    Total length of first used_key_parts parts of the key.
129
119
    Applicable if index!= MAX_KEY.
130
120
  */
131
 
  uint max_used_key_length;
132
 
 
133
 
  /*
134
 
    Max. number of (first) key parts this quick select uses for retrieval.
 
121
  uint32_t max_used_key_length;
 
122
  /**
 
123
    Maximum number of (first) key parts this quick select uses for retrieval.
135
124
    eg. for "(key1p1=c1 AND key1p2=c2) OR key1p1=c2" used_key_parts == 2.
136
125
    Applicable if index!= MAX_KEY.
137
126
 
138
127
    For QUICK_GROUP_MIN_MAX_SELECT it includes MIN/MAX argument keyparts.
139
128
  */
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 */
 
129
  uint32_t used_key_parts;
 
130
  /**
 
131
   * The rowid of last row retrieved by this quick select. This is used only when
 
132
   * doing ROR-index_merge selects
 
133
   */
 
134
  unsigned char *last_rowid;
 
135
 
 
136
  /**
 
137
   * Table record buffer used by this quick select.
 
138
   */
 
139
  unsigned char *record;
 
140
 
 
141
  QuickSelectInterface();
 
142
  virtual ~QuickSelectInterface(){};
 
143
 
 
144
  /**
 
145
   * Do post-constructor initialization.
 
146
   *
 
147
   * @details
 
148
   *
 
149
   * Performs initializations that should have been in constructor if
 
150
   * it was possible to return errors from constructors. The join optimizer may
 
151
   * create and then delete quick selects without retrieving any rows so init()
 
152
   * must not contain any IO or CPU intensive code.
 
153
   *
 
154
   * If init() call fails the only valid action is to delete this quick select,
 
155
   * reset() and get_next() must not be called.
 
156
   *
 
157
   * @retval
 
158
   *  0      OK
 
159
   * @retval
 
160
   *  other  Error code
 
161
  */
 
162
  virtual int init() = 0;
 
163
 
 
164
  /**
 
165
   * Initializes quick select for row retrieval.
 
166
   *
 
167
   * @details
 
168
   *
 
169
   * 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
   * @retval 
 
177
   *  0      OK
 
178
   * @retval
 
179
   *  other  Error code
 
180
   */
 
181
  virtual int reset(void) = 0;
 
182
  /** Gets next record to retrieve */
 
183
  virtual int get_next() = 0;
 
184
 
 
185
  /** Range end should be called when we have looped over the whole index */
185
186
  virtual void range_end() {}
186
187
 
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
 
188
  virtual bool reverse_sorted() const = 0;
 
189
 
 
190
  virtual bool unique_key_range() const
 
191
  {
 
192
    return false;
 
193
  }
 
194
 
 
195
  enum 
 
196
  {
 
197
    QS_TYPE_RANGE= 0,
 
198
    QS_TYPE_INDEX_MERGE= 1,
 
199
    QS_TYPE_RANGE_DESC= 2,
 
200
    QS_TYPE_ROR_INTERSECT= 4,
 
201
    QS_TYPE_ROR_UNION= 5,
 
202
    QS_TYPE_GROUP_MIN_MAX= 6
197
203
  };
198
204
 
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
 
  */
 
205
  /** Returns the type of this quick select - one of the QS_TYPE_* values */
 
206
  virtual int get_type() const = 0;
 
207
 
 
208
  /**
 
209
   * Initialize this quick select as a merged scan inside a ROR-union or a ROR-
 
210
   * intersection scan. The caller must not additionally call init() if this
 
211
   * function is called.
 
212
   *
 
213
   * @param If true, the quick select may use table->Cursor,
 
214
   *        otherwise it must create and use a separate Cursor
 
215
   *        object.
 
216
   *
 
217
   * @retval
 
218
   *  0     Ok
 
219
   * @retval
 
220
   *  other Error
 
221
   */
 
222
  virtual int init_ror_merged_scan(bool)
 
223
  {
 
224
    assert(0);
 
225
    return 1;
 
226
  }
 
227
 
 
228
  /**
 
229
   * Save ROWID of last retrieved row in file->ref. This used in ROR-merging.
 
230
   */
221
231
  virtual void save_last_pos(){};
222
232
 
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;
 
233
  /**
 
234
   * Append comma-separated list of keys this quick select uses to key_names;
 
235
   * append comma-separated list of corresponding used lengths to used_lengths.
 
236
   * 
 
237
   * @note This is used by during explain plan.
 
238
   */
 
239
  virtual void add_keys_and_lengths(String *key_names, String *used_lengths)=0;
 
240
 
 
241
  /**
 
242
   * Append text representation of quick select structure (what and how is
 
243
   * merged) to str. The result is added to "Extra" field in EXPLAIN output.
 
244
   *
 
245
   * @note
 
246
   *
 
247
   * This function is implemented only by quick selects that merge other quick
 
248
   * selects output and/or can produce output suitable for merging.
 
249
   */
 
250
  virtual void add_info_string(String *) 
 
251
  {}
 
252
  
 
253
  /**
 
254
   * Returns true if any index used by this quick select
 
255
   * uses field which is marked in passed bitmap.
 
256
   */
 
257
  virtual bool is_keys_used(const MyBitmap *fields);
254
258
};
255
259
 
256
 
 
257
260
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
 
*/
 
261
class QuickRange;
 
262
class QuickRangeSelect;
 
263
 
 
264
/**
 
265
 * MRR range sequence, array<QuickRange> implementation: sequence traversal
 
266
 * context.
 
267
 */
266
268
typedef struct st_quick_range_seq_ctx
267
269
{
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 {
 
270
  QuickRange **first;
 
271
  QuickRange **cur;
 
272
  QuickRange **last;
 
273
} QuickRangeSequenceContext;
 
274
 
 
275
range_seq_t quick_range_seq_init(void *init_param, uint32_t n_ranges, uint32_t flags);
 
276
 
 
277
uint32_t quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range);
 
278
 
 
279
/**
 
280
 * Executor class for SELECT statements.
 
281
 *
 
282
 * @details
 
283
 *
 
284
 * The QuickSelectInterface member variable is the implementor
 
285
 * of the SELECT execution.
 
286
 */
 
287
class SqlSelect : public drizzled::memory::SqlAlloc 
 
288
{
691
289
 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;
 
290
  QuickSelectInterface *quick; /**< If quick-select used */
 
291
  COND *cond; /**< where condition */
 
292
  Table *head;
 
293
  IO_CACHE *file; /**< Positions to used records */
 
294
  ha_rows records; /**< Records in use if read from file */
 
295
  double read_time; /**< Time to read rows */
 
296
  key_map quick_keys; /**< Possible quick keys */
 
297
  key_map needed_reg; /**< Possible quick keys after prev tables. */
 
298
  table_map const_tables;
 
299
  table_map read_tables;
 
300
  bool free_cond;
702
301
 
703
 
  SQL_SELECT();
704
 
  ~SQL_SELECT();
 
302
  SqlSelect();
 
303
  ~SqlSelect();
705
304
  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, 
 
305
  bool check_quick(Session *session, bool force_quick_range, ha_rows limit);
 
306
  bool skip_record();
 
307
  int test_quick_select(Session *session, key_map keys, table_map prev_tables,
 
308
                        ha_rows limit, bool force_quick_range,
715
309
                        bool ordered_output);
716
310
};
717
311
 
718
 
QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table,
719
 
                                             struct st_table_ref *ref,
 
312
QuickRangeSelect *get_quick_select_for_ref(Session *session, 
 
313
                                             Table *table,
 
314
                                             struct table_reference_st *ref,
720
315
                                             ha_rows records);
721
 
uint get_index_for_order(TABLE *table, ORDER *order, ha_rows limit);
722
 
 
723
 
#endif
 
316
 
 
317
/*
 
318
  Create a QuickRangeSelect from given key and SEL_ARG tree for that key.
 
319
 
 
320
  SYNOPSIS
 
321
    get_quick_select()
 
322
      param
 
323
      idx            Index of used key in param->key.
 
324
      key_tree       SEL_ARG tree for the used key
 
325
      mrr_flags      MRR parameter for quick select
 
326
      mrr_buf_size   MRR parameter for quick select
 
327
      parent_alloc   If not NULL, use it to allocate memory for
 
328
                     quick select data. Otherwise use quick->alloc.
 
329
  NOTES
 
330
    The caller must call QUICK_SELECT::init for returned quick select.
 
331
 
 
332
    CAUTION! This function may change session->mem_root to a drizzled::memory::Root which will be
 
333
    deallocated when the returned quick select is deleted.
 
334
 
 
335
  RETURN
 
336
    NULL on error
 
337
    otherwise created quick select
 
338
*/
 
339
QuickRangeSelect *get_quick_select(Parameter *param,
 
340
                                   uint32_t index,
 
341
                                   SEL_ARG *key_tree, 
 
342
                                   uint32_t mrr_flags,
 
343
                                   uint32_t mrr_buf_size, 
 
344
                                   drizzled::memory::Root *alloc);
 
345
 
 
346
uint32_t get_index_for_order(Table *table, order_st *order, ha_rows limit);
 
347
 
 
348
SqlSelect *make_select(Table *head, 
 
349
                       table_map const_tables,
 
350
                       table_map read_tables, 
 
351
                       COND *conds,
 
352
                       bool allow_null_cond,
 
353
                       int *error);
 
354
 
 
355
bool get_quick_keys(Parameter *param, 
 
356
                    QuickRangeSelect *quick,
 
357
                    KEY_PART *key,
 
358
                    SEL_ARG *key_tree, 
 
359
                    unsigned char *min_key,
 
360
                    uint32_t min_key_flag,
 
361
                    unsigned char *max_key,
 
362
                    uint32_t max_key_flag);
 
363
 
 
364
} /* namespace optimizer */
 
365
 
 
366
} /* namespace drizzled */
 
367
 
 
368
#endif /* DRIZZLED_OPTIMIZER_RANGE_H */