← 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-11-16 23:47:43 UTC
  • mto: (584.1.10 devel)
  • mto: This revision was merged to the branch mainline in revision 589.
  • Revision ID: monty@inaugust.com-20081116234743-c38gmv0pa2kdefaj
Broke out cached_item.

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