← 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: 2008-10-29 13:46:43 UTC
  • Revision ID: brian@tangent.org-20081029134643-z6jcwjvyruhk2vlu
Updates for ignore file.

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, Inc.
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 <boost/dynamic_bitset.hpp>
26
 
#include <vector>
27
 
 
28
 
namespace drizzled
29
 
{
30
 
 
31
 
class Cursor;
32
 
 
33
 
namespace optimizer
34
 
{
35
 
 
36
 
/**
37
 
 * Quick select that does a range scan on a single key. 
38
 
 *
39
 
 * The records are returned in key order.
40
 
 * 
41
 
 */
42
 
class QuickRangeSelect : public QuickSelectInterface
43
 
{
44
 
protected:
45
 
  Cursor *cursor;
46
 
  DYNAMIC_ARRAY ranges; /**< ordered array of range ptrs */
47
 
 
48
 
  /** Members to deal with case when this quick select is a ROR-merged scan */
49
 
  bool in_ror_merged_scan;
50
 
  boost::dynamic_bitset<> *column_bitmap;
51
 
  boost::dynamic_bitset<> *save_read_set;
52
 
  boost::dynamic_bitset<> *save_write_set;
53
 
  bool free_file; /**< True when this->file is "owned" by this quick select */
54
 
 
55
 
  /* Range pointers to be used when not using MRR interface */
56
 
  QuickRange **cur_range; /**< current element in ranges  */
57
 
  QuickRange *last_range;
58
 
 
59
 
  /** Members needed to use the MRR interface */
60
 
  QuickRangeSequenceContext qr_traversal_ctx;
61
 
  uint32_t mrr_buf_size; /**< copy from session->variables.read_rnd_buff_size */
62
 
 
63
 
  /** Info about index we're scanning */
64
 
  KEY_PART *key_parts;
65
 
  KeyPartInfo *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
 
 
112
 
  ~QuickRangeSelect();
113
 
 
114
 
  int init();
115
 
 
116
 
  int reset(void);
117
 
 
118
 
  /**
119
 
   * Get next possible record using quick-struct.
120
 
   *
121
 
   * SYNOPSIS
122
 
   * QuickRangeSelect::get_next()
123
 
   *
124
 
   * NOTES
125
 
   * Record is read into table->getInsertRecord()
126
 
   *
127
 
   * RETURN
128
 
   * @retval 0                  Found row
129
 
   * @retval HA_ERR_END_OF_FILE No (more) rows in range
130
 
   * @retaval # Error code
131
 
   */
132
 
  int get_next();
133
 
 
134
 
  void range_end();
135
 
 
136
 
  /**
137
 
   * Get the next record with a different prefix.
138
 
   *
139
 
   * SYNOPSIS
140
 
   * QuickRangeSelect::get_next_prefix()
141
 
   * @param[in] prefix_length  length of cur_prefix
142
 
   * @param[in] cur_prefix     prefix of a key to be searched for
143
 
   *
144
 
   * DESCRIPTION
145
 
   * Each subsequent call to the method retrieves the first record that has a
146
 
   * prefix with length prefix_length different from cur_prefix, such that the
147
 
   * record with the new prefix is within the ranges described by
148
 
   * this->ranges. The record found is stored into the buffer pointed by
149
 
   * this->record.
150
 
   * The method is useful for GROUP-BY queries with range conditions to
151
 
   * discover the prefix of the next group that satisfies the range conditions.
152
 
   *
153
 
   * @todo
154
 
   * This method is a modified copy of QuickRangeSelect::get_next(), so both
155
 
   * methods should be unified into a more general one to reduce code
156
 
   * duplication.
157
 
   *
158
 
   * RETURN
159
 
   * @retval 0                  on success
160
 
   * @retval HA_ERR_END_OF_FILE if returned all keys
161
 
   * @retval other              if some error occurred
162
 
   */
163
 
  int get_next_prefix(uint32_t prefix_length,
164
 
                      key_part_map keypart_map,
165
 
                      unsigned char *cur_prefix);
166
 
 
167
 
  bool reverse_sorted() const
168
 
  {
169
 
    return false;
170
 
  }
171
 
 
172
 
  /**
173
 
   * @return true if there is only one range and this uses the whole primary key
174
 
   */
175
 
  bool unique_key_range() const;
176
 
 
177
 
  /**
178
 
   * Initialize this quick select to be a ROR-merged scan.
179
 
   *
180
 
   * SYNOPSIS
181
 
   * QuickRangeSelect::init_ror_merged_scan()
182
 
   * @param[in] reuse_handler If true, use head->cursor, otherwise create a separate Cursor object
183
 
   *
184
 
   * NOTES
185
 
   * This function creates and prepares for subsequent use a separate Cursor
186
 
   * object if it can't reuse head->cursor. The reason for this is that during
187
 
   * ROR-merge several key scans are performed simultaneously, and a single
188
 
   * Cursor is only capable of preserving context of a single key scan.
189
 
   *
190
 
   * In ROR-merge the quick select doing merge does full records retrieval,
191
 
   * merged quick selects read only keys.
192
 
   *
193
 
   * RETURN
194
 
   * @reval 0  ROR child scan initialized, ok to use.
195
 
   * @retval 1  error
196
 
   */
197
 
  int init_ror_merged_scan(bool reuse_handler);
198
 
 
199
 
  void save_last_pos();
200
 
 
201
 
  int get_type() const
202
 
  {
203
 
    return QS_TYPE_RANGE;
204
 
  }
205
 
 
206
 
  void add_keys_and_lengths(std::string *key_names, std::string *used_lengths);
207
 
 
208
 
  void add_info_string(std::string *str);
209
 
 
210
 
  void resetCursor()
211
 
  {
212
 
    cursor= NULL;
213
 
  }
214
 
 
215
 
private:
216
 
 
217
 
  /* Used only by QuickSelectDescending */
218
 
  QuickRangeSelect(const QuickRangeSelect& org) : QuickSelectInterface()
219
 
  {
220
 
    memmove(this, &org, sizeof(*this));
221
 
    /*
222
 
      Use default MRR implementation for reverse scans. No table engine
223
 
      currently can do an MRR scan with output in reverse index order.
224
 
    */
225
 
    mrr_flags|= HA_MRR_USE_DEFAULT_IMPL;
226
 
    mrr_buf_size= 0;
227
 
  }
228
 
 
229
 
  friend class ::drizzled::RorIntersectReadPlan; 
230
 
 
231
 
  friend
232
 
  QuickRangeSelect *get_quick_select_for_ref(Session *session, Table *table,
233
 
                                             struct table_reference_st *ref,
234
 
                                             ha_rows records);
235
 
 
236
 
  friend bool get_quick_keys(Parameter *param, 
237
 
                             QuickRangeSelect *quick,
238
 
                             KEY_PART *key, 
239
 
                             SEL_ARG *key_tree,
240
 
                             unsigned char *min_key, 
241
 
                             uint32_t min_key_flag,
242
 
                             unsigned char *max_key, 
243
 
                             uint32_t max_key_flag);
244
 
 
245
 
  friend QuickRangeSelect *get_quick_select(Parameter *,
246
 
                                            uint32_t idx,
247
 
                                            SEL_ARG *key_tree,
248
 
                                            uint32_t mrr_flags,
249
 
                                            uint32_t mrr_buf_size,
250
 
                                            memory::Root *alloc);
251
 
  friend class QuickSelectDescending;
252
 
 
253
 
  friend class QuickIndexMergeSelect;
254
 
 
255
 
  friend class QuickRorIntersectSelect;
256
 
 
257
 
  friend class QuickGroupMinMaxSelect;
258
 
 
259
 
  friend uint32_t quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range);
260
 
 
261
 
  friend range_seq_t quick_range_seq_init(void *init_param,
262
 
                                          uint32_t n_ranges, 
263
 
                                          uint32_t flags);
264
 
 
265
 
  friend void select_describe(Join *join, 
266
 
                              bool need_tmp_table, 
267
 
                              bool need_order,
268
 
                              bool distinct,
269
 
                              const char *message);
270
 
};
271
 
 
272
 
class QuickSelectDescending : public QuickRangeSelect
273
 
{
274
 
public:
275
 
 
276
 
  QuickSelectDescending(QuickRangeSelect *q, 
277
 
                        uint32_t used_key_parts,
278
 
                        bool *create_err);
279
 
 
280
 
  int get_next();
281
 
 
282
 
  bool reverse_sorted() const
283
 
  { 
284
 
    return true; 
285
 
  }
286
 
 
287
 
  int get_type() const
288
 
  { 
289
 
    return QS_TYPE_RANGE_DESC;
290
 
  }
291
 
 
292
 
private:
293
 
 
294
 
  bool range_reads_after_key(QuickRange *range);
295
 
 
296
 
  int reset(void) 
297
 
  { 
298
 
    rev_it= rev_ranges.begin();
299
 
    return QuickRangeSelect::reset();
300
 
  }
301
 
 
302
 
  std::vector<QuickRange *> rev_ranges;
303
 
 
304
 
  std::vector<QuickRange *>::iterator rev_it;
305
 
 
306
 
};
307
 
 
308
 
} /* namespace optimizer */
309
 
 
310
 
} /* namespace drizzled */
311
 
 
312
 
#endif /* DRIZZLED_OPTIMIZER_QUICK_RANGE_SELECT_H */