← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/opt_range.h

  • Committer: Monty
  • Date: 2008-10-02 05:41:33 UTC
  • mfrom: (398.1.10 codestyle)
  • Revision ID: mordred@scylla.inaugust.com-20081002054133-tyxv5bmqpazfaqqi
Merged up to 408 of stdint-includes-fix.

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