← 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-10-22 23:45:01 UTC
  • Revision ID: monty@inaugust.com-20081022234501-hwybvprata8ba98l
Moved handler_error_messages array out of header file. Moved associated
functions to live with it.

Show diffs side-by-side

added added

removed removed

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