← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/opt_range.h

  • Committer: Monty Taylor
  • Date: 2008-08-05 19:01:20 UTC
  • mto: (266.1.1 codestyle)
  • mto: This revision was merged to the branch mainline in revision 266.
  • Revision ID: monty@inaugust.com-20080805190120-tsuziqz2mfqcw7pe
Removed libmysyslt.la, made mysys a noinst_ and made everything use it. It's
not a standalone lib, there's no reason to pretend otherwise.

Show diffs side-by-side

added added

removed removed

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