← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/optimizer/quick_range_select.h

  • Committer: Brian Aker
  • Date: 2010-02-10 18:04:24 UTC
  • mfrom: (1286.1.5 build)
  • Revision ID: brian@gaz-20100210180424-03ypoyifmlc2lgcp
Merge of Brian/Padraig

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/optimizer/quick_range_select.h
 
1
/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
 
2
 *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
 
3
 *
 
4
 *  Copyright (C) 2008-2009 Sun Microsystems
 
5
 *
 
6
 *  This program is free software; you can redistribute it and/or modify
 
7
 *  it under the terms of the GNU General Public License as published by
 
8
 *  the Free Software Foundation; version 2 of the License.
 
9
 *
 
10
 *  This program is distributed in the hope that it will be useful,
 
11
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
12
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
13
 *  GNU General Public License for more details.
 
14
 *
 
15
 *  You should have received a copy of the GNU General Public License
 
16
 *  along with this program; if not, write to the Free Software
 
17
 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 
18
 */
 
19
 
 
20
#ifndef DRIZZLED_OPTIMIZER_QUICK_RANGE_SELECT_H
 
21
#define DRIZZLED_OPTIMIZER_QUICK_RANGE_SELECT_H
 
22
 
 
23
#include "drizzled/optimizer/range.h"
 
24
 
 
25
#include <vector>
 
26
 
 
27
namespace drizzled
 
28
{
 
29
 
 
30
class Cursor;
 
31
 
 
32
namespace optimizer
 
33
{
 
34
 
 
35
/**
 
36
 * Quick select that does a range scan on a single key. 
 
37
 *
 
38
 * The records are returned in key order.
 
39
 * 
 
40
 */
 
41
class QuickRangeSelect : public QuickSelectInterface
 
42
{
 
43
protected:
 
44
  Cursor *cursor;
 
45
  DYNAMIC_ARRAY ranges; /**< ordered array of range ptrs */
 
46
 
 
47
  /** Members to deal with case when this quick select is a ROR-merged scan */
 
48
  bool in_ror_merged_scan;
 
49
  MyBitmap column_bitmap;
 
50
  MyBitmap *save_read_set;
 
51
  MyBitmap *save_write_set;
 
52
  bool free_file; /**< True when this->file is "owned" by this quick select */
 
53
 
 
54
  /* Range pointers to be used when not using MRR interface */
 
55
  QuickRange **cur_range; /**< current element in ranges  */
 
56
  QuickRange *last_range;
 
57
 
 
58
  /** Members needed to use the MRR interface */
 
59
  QuickRangeSequenceContext qr_traversal_ctx;
 
60
  uint32_t mrr_buf_size; /**< copy from session->variables.read_rnd_buff_size */
 
61
  HANDLER_BUFFER *mrr_buf_desc; /**< the Cursor buffer */
 
62
 
 
63
  /** Info about index we're scanning */
 
64
  KEY_PART *key_parts;
 
65
  KEY_PART_INFO *key_part_info;
 
66
 
 
67
  bool dont_free; /**< Used by QuickSelectDescending */
 
68
 
 
69
  /**
 
70
   * Compare if found key is over max-value
 
71
   * @return 0 if key <= range->max_key
 
72
   * @todo: Figure out why can't this function be as simple as cmp_prev().
 
73
   */
 
74
  int cmp_next(QuickRange *range);
 
75
 
 
76
  /**
 
77
   * @return 0 if found key is inside range (found key >= range->min_key).
 
78
   */
 
79
  int cmp_prev(QuickRange *range);
 
80
 
 
81
  /**
 
82
   * Check if current row will be retrieved by this QuickRangeSelect
 
83
   *
 
84
   * NOTES
 
85
   * It is assumed that currently a scan is being done on another index
 
86
   * which reads all necessary parts of the index that is scanned by this
 
87
   * quick select.
 
88
   * The implementation does a binary search on sorted array of disjoint
 
89
   * ranges, without taking size of range into account.
 
90
   *
 
91
   * This function is used to filter out clustered PK scan rows in
 
92
   * index_merge quick select.
 
93
   *
 
94
   * RETURN
 
95
   * @retval true  if current row will be retrieved by this quick select
 
96
   * false if not
 
97
   */
 
98
  bool row_in_ranges();
 
99
 
 
100
public:
 
101
 
 
102
  uint32_t mrr_flags; /**< Flags to be used with MRR interface */
 
103
 
 
104
  memory::Root alloc;
 
105
 
 
106
  QuickRangeSelect(Session *session,
 
107
                     Table *table,
 
108
                     uint32_t index_arg,
 
109
                     bool no_alloc,
 
110
                     memory::Root *parent_alloc,
 
111
                     bool *create_err);
 
112
 
 
113
  ~QuickRangeSelect();
 
114
 
 
115
  int init();
 
116
 
 
117
  int reset(void);
 
118
 
 
119
  /**
 
120
   * Get next possible record using quick-struct.
 
121
   *
 
122
   * SYNOPSIS
 
123
   * QuickRangeSelect::get_next()
 
124
   *
 
125
   * NOTES
 
126
   * Record is read into table->record[0]
 
127
   *
 
128
   * RETURN
 
129
   * @retval 0                  Found row
 
130
   * @retval HA_ERR_END_OF_FILE No (more) rows in range
 
131
   * @retaval # Error code
 
132
   */
 
133
  int get_next();
 
134
 
 
135
  void range_end();
 
136
 
 
137
  /**
 
138
   * Get the next record with a different prefix.
 
139
   *
 
140
   * SYNOPSIS
 
141
   * QuickRangeSelect::get_next_prefix()
 
142
   * @param[in] prefix_length  length of cur_prefix
 
143
   * @param[in] cur_prefix     prefix of a key to be searched for
 
144
   *
 
145
   * DESCRIPTION
 
146
   * Each subsequent call to the method retrieves the first record that has a
 
147
   * prefix with length prefix_length different from cur_prefix, such that the
 
148
   * record with the new prefix is within the ranges described by
 
149
   * this->ranges. The record found is stored into the buffer pointed by
 
150
   * this->record.
 
151
   * The method is useful for GROUP-BY queries with range conditions to
 
152
   * discover the prefix of the next group that satisfies the range conditions.
 
153
   *
 
154
   * @todo
 
155
   * This method is a modified copy of QuickRangeSelect::get_next(), so both
 
156
   * methods should be unified into a more general one to reduce code
 
157
   * duplication.
 
158
   *
 
159
   * RETURN
 
160
   * @retval 0                  on success
 
161
   * @retval HA_ERR_END_OF_FILE if returned all keys
 
162
   * @retval other              if some error occurred
 
163
   */
 
164
  int get_next_prefix(uint32_t prefix_length,
 
165
                      key_part_map keypart_map,
 
166
                      unsigned char *cur_prefix);
 
167
 
 
168
  bool reverse_sorted() const
 
169
  {
 
170
    return false;
 
171
  }
 
172
 
 
173
  /**
 
174
   * @return true if there is only one range and this uses the whole primary key
 
175
   */
 
176
  bool unique_key_range() const;
 
177
 
 
178
  /**
 
179
   * Initialize this quick select to be a ROR-merged scan.
 
180
   *
 
181
   * SYNOPSIS
 
182
   * QuickRangeSelect::init_ror_merged_scan()
 
183
   * @param[in] reuse_handler If true, use head->cursor, otherwise create a separate Cursor object
 
184
   *
 
185
   * NOTES
 
186
   * This function creates and prepares for subsequent use a separate Cursor
 
187
   * object if it can't reuse head->cursor. The reason for this is that during
 
188
   * ROR-merge several key scans are performed simultaneously, and a single
 
189
   * Cursor is only capable of preserving context of a single key scan.
 
190
   *
 
191
   * In ROR-merge the quick select doing merge does full records retrieval,
 
192
   * merged quick selects read only keys.
 
193
   *
 
194
   * RETURN
 
195
   * @reval 0  ROR child scan initialized, ok to use.
 
196
   * @retval 1  error
 
197
   */
 
198
  int init_ror_merged_scan(bool reuse_handler);
 
199
 
 
200
  void save_last_pos();
 
201
 
 
202
  int get_type() const
 
203
  {
 
204
    return QS_TYPE_RANGE;
 
205
  }
 
206
 
 
207
  void add_keys_and_lengths(String *key_names, String *used_lengths);
 
208
 
 
209
  void add_info_string(String *str);
 
210
 
 
211
  void resetCursor()
 
212
  {
 
213
    cursor= NULL;
 
214
  }
 
215
 
 
216
private:
 
217
 
 
218
  /* Used only by QuickSelectDescending */
 
219
  QuickRangeSelect(const QuickRangeSelect& org) : QuickSelectInterface()
 
220
  {
 
221
    memmove(this, &org, sizeof(*this));
 
222
    /*
 
223
      Use default MRR implementation for reverse scans. No table engine
 
224
      currently can do an MRR scan with output in reverse index order.
 
225
    */
 
226
    mrr_buf_desc= NULL;
 
227
    mrr_flags|= HA_MRR_USE_DEFAULT_IMPL;
 
228
    mrr_buf_size= 0;
 
229
  }
 
230
 
 
231
  friend class ::drizzled::RorIntersectReadPlan; 
 
232
 
 
233
  friend
 
234
  QuickRangeSelect *get_quick_select_for_ref(Session *session, Table *table,
 
235
                                             struct table_reference_st *ref,
 
236
                                             ha_rows records);
 
237
 
 
238
  friend bool get_quick_keys(Parameter *param, 
 
239
                             QuickRangeSelect *quick,
 
240
                             KEY_PART *key, 
 
241
                             SEL_ARG *key_tree,
 
242
                             unsigned char *min_key, 
 
243
                             uint32_t min_key_flag,
 
244
                             unsigned char *max_key, 
 
245
                             uint32_t max_key_flag);
 
246
 
 
247
  friend QuickRangeSelect *get_quick_select(Parameter *,
 
248
                                            uint32_t idx,
 
249
                                            SEL_ARG *key_tree,
 
250
                                            uint32_t mrr_flags,
 
251
                                            uint32_t mrr_buf_size,
 
252
                                            memory::Root *alloc);
 
253
  friend class QuickSelectDescending;
 
254
 
 
255
  friend class QuickIndexMergeSelect;
 
256
 
 
257
  friend class QuickRorIntersectSelect;
 
258
 
 
259
  friend class QuickGroupMinMaxSelect;
 
260
 
 
261
  friend uint32_t quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range);
 
262
 
 
263
  friend range_seq_t quick_range_seq_init(void *init_param,
 
264
                                          uint32_t n_ranges, 
 
265
                                          uint32_t flags);
 
266
 
 
267
  friend void select_describe(JOIN *join, 
 
268
                              bool need_tmp_table, 
 
269
                              bool need_order,
 
270
                              bool distinct,
 
271
                              const char *message);
 
272
};
 
273
 
 
274
class QuickSelectDescending : public QuickRangeSelect
 
275
{
 
276
public:
 
277
 
 
278
  QuickSelectDescending(QuickRangeSelect *q, 
 
279
                        uint32_t used_key_parts,
 
280
                        bool *create_err);
 
281
 
 
282
  int get_next();
 
283
 
 
284
  bool reverse_sorted() const
 
285
  { 
 
286
    return true; 
 
287
  }
 
288
 
 
289
  int get_type() const
 
290
  { 
 
291
    return QS_TYPE_RANGE_DESC;
 
292
  }
 
293
 
 
294
private:
 
295
 
 
296
  bool range_reads_after_key(QuickRange *range);
 
297
 
 
298
  int reset(void) 
 
299
  { 
 
300
    rev_it= rev_ranges.begin();
 
301
    return QuickRangeSelect::reset();
 
302
  }
 
303
 
 
304
  std::vector<QuickRange *> rev_ranges;
 
305
 
 
306
  std::vector<QuickRange *>::iterator rev_it;
 
307
 
 
308
};
 
309
 
 
310
} /* namespace optimizer */
 
311
 
 
312
} /* namespace drizzled */
 
313
 
 
314
#endif /* DRIZZLED_OPTIMIZER_QUICK_RANGE_SELECT_H */