Drizzled Public API Documentation

quick_range_select.cc
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 #include <config.h>
21 
22 #include <drizzled/session.h>
23 #include <drizzled/optimizer/quick_range.h>
24 #include <drizzled/optimizer/quick_range_select.h>
25 #include <drizzled/internal/m_string.h>
26 #include <drizzled/current_session.h>
27 #include <drizzled/key.h>
28 #include <drizzled/table.h>
29 #include <drizzled/util/test.h>
30 #include <drizzled/system_variables.h>
31 
32 #include <fcntl.h>
33 
34 using namespace std;
35 
36 namespace drizzled {
37 
38 
39 optimizer::QuickRangeSelect::QuickRangeSelect(Session *session,
40  Table *table,
41  uint32_t key_nr,
42  bool no_alloc,
43  memory::Root *parent_alloc)
44  :
45  cursor(NULL),
46  ranges(),
47  in_ror_merged_scan(false),
48  column_bitmap(NULL),
49  save_read_set(NULL),
50  save_write_set(NULL),
51  free_file(false),
52  cur_range(NULL),
53  last_range(NULL),
54  qr_traversal_ctx(),
55  mrr_buf_size(0),
56  key_parts(NULL),
57  dont_free(false),
58  mrr_flags(0),
59  alloc()
60 {
61  sorted= 0;
62  index= key_nr;
63  head= table;
64  key_part_info= head->key_info[index].key_part;
65  ranges.init(sizeof(optimizer::QuickRange*), 16, 16);
66 
67  /* 'session' is not accessible in QuickRangeSelect::reset(). */
68  mrr_buf_size= session->variables.read_rnd_buff_size;
69 
70  if (! no_alloc && ! parent_alloc)
71  {
72  // Allocates everything through the internal memroot
73  alloc.init(session->variables.range_alloc_block_size);
74  session->mem_root= &alloc;
75  }
76  else
77  {
78  memset(&alloc, 0, sizeof(alloc));
79  }
80 
81  cursor= head->cursor;
82  record= head->record[0];
83  save_read_set= head->read_set;
84  save_write_set= head->write_set;
85  column_bitmap= new boost::dynamic_bitset<>(table->getShare()->sizeFields());
86 }
87 
88 
90 {
91  if (cursor->inited != Cursor::NONE)
92  cursor->ha_index_or_rnd_end();
93  return (cursor->startIndexScan(index, 1));
94 }
95 
96 
98 {
99  if (cursor->inited != Cursor::NONE)
100  cursor->ha_index_or_rnd_end();
101 }
102 
103 
104 optimizer::QuickRangeSelect::~QuickRangeSelect()
105 {
106  if (! dont_free)
107  {
108  /* cursor is NULL for CPK scan on covering ROR-intersection */
109  if (cursor)
110  {
111  range_end();
112  if (head->key_read)
113  {
114  head->key_read= 0;
115  cursor->extra(HA_EXTRA_NO_KEYREAD);
116  }
117  if (free_file)
118  {
119  cursor->ha_external_lock(current_session, F_UNLCK);
120  cursor->close();
121  delete cursor;
122  }
123  }
124  ranges.free(); /* ranges are allocated in alloc */
125  delete column_bitmap;
126  alloc.free_root(MYF(0));
127  }
128  head->column_bitmaps_set(*save_read_set, *save_write_set);
129 }
130 
131 
133 {
134  Cursor* org_file;
135  Cursor* save_file= cursor;
136  Session* session;
137 
138  in_ror_merged_scan= 1;
139  if (reuse_handler)
140  {
141  if (init() || reset())
142  {
143  return 0;
144  }
145  head->column_bitmaps_set(*column_bitmap, *column_bitmap);
146  goto end;
147  }
148 
149  /* Create a separate Cursor object for this quick select */
150  if (free_file)
151  {
152  /* already have own 'Cursor' object. */
153  return 0;
154  }
155 
156  session= head->in_use;
157  if (not (cursor= head->cursor->clone(session->mem_root)))
158  {
159  /*
160  Manually set the error flag. Note: there seems to be quite a few
161  places where a failure could cause the server to "hang" the client by
162  sending no response to a query. ATM those are not real errors because
163  the storage engine calls in question happen to never fail with the
164  existing storage engines.
165  */
166  my_error(ER_OUT_OF_RESOURCES, MYF(0));
167  /* Caller will free the memory */
168  goto failure;
169  }
170 
171  head->column_bitmaps_set(*column_bitmap, *column_bitmap);
172 
173  if (cursor->ha_external_lock(session, F_RDLCK))
174  goto failure;
175 
176  if (init() || reset())
177  {
178  cursor->ha_external_lock(session, F_UNLCK);
179  cursor->close();
180  goto failure;
181  }
182  free_file= true;
183  last_rowid= cursor->ref;
184 
185 end:
186  /*
187  We are only going to read key fields and call position() on 'cursor'
188  The following sets head->tmp_set to only use this key and then updates
189  head->read_set and head->write_set to use this bitmap.
190  The now bitmap is stored in 'column_bitmap' which is used in ::get_next()
191  */
192  org_file= head->cursor;
193  head->cursor= cursor;
194  /* We don't have to set 'head->keyread' here as the 'cursor' is unique */
195  if (not head->no_keyread)
196  {
197  head->key_read= 1;
198  head->mark_columns_used_by_index(index);
199  }
200  head->prepare_for_position();
201  head->cursor= org_file;
202  *column_bitmap|= *head->read_set;
203  head->column_bitmaps_set(*column_bitmap, *column_bitmap);
204 
205  return 0;
206 
207 failure:
208  head->column_bitmaps_set(*save_read_set, *save_write_set);
209  delete cursor;
210  cursor= save_file;
211  return 0;
212 }
213 
214 
216 {
217  cursor->position(record);
218 }
219 
220 
222 {
223  if (ranges.size() == 1)
224  {
225  optimizer::QuickRange *tmp= *((optimizer::QuickRange**)ranges.buffer);
226  if ((tmp->flag & (EQ_RANGE | NULL_RANGE)) == EQ_RANGE)
227  {
228  KeyInfo *key=head->key_info+index;
229  return ((key->flags & (HA_NOSAME)) == HA_NOSAME &&
230  key->key_length == tmp->min_length);
231  }
232  }
233  return false;
234 }
235 
236 
238 {
239  int error= 0;
240  last_range= NULL;
241  cur_range= (optimizer::QuickRange**) ranges.buffer;
242 
243  if (cursor->inited == Cursor::NONE && (error= cursor->startIndexScan(index, 1)))
244  {
245  return error;
246  }
247 
248  /*
249  (in the past) Allocate buffer if we need one but haven't allocated it yet
250  There is a later assert in th code that hoped to catch random free() that might
251  have done this.
252  */
253  assert(not (mrr_buf_size));
254 
255  if (sorted)
256  {
257  mrr_flags|= HA_MRR_SORTED;
258  }
259  RANGE_SEQ_IF seq_funcs= {
260  optimizer::quick_range_seq_init,
261  optimizer::quick_range_seq_next
262  };
263  error= cursor->multi_range_read_init(&seq_funcs,
264  (void*) this,
265  ranges.size(),
266  mrr_flags);
267  return error;
268 }
269 
270 
272 {
273  char *dummy= NULL;
274  if (in_ror_merged_scan)
275  {
276  /*
277  We don't need to signal the bitmap change as the bitmap is always the
278  same for this head->cursor
279  */
280  head->column_bitmaps_set(*column_bitmap, *column_bitmap);
281  }
282 
283  int result= cursor->multi_range_read_next(&dummy);
284 
285  if (in_ror_merged_scan)
286  {
287  /* Restore bitmaps set on entry */
288  head->column_bitmaps_set(*save_read_set, *save_write_set);
289  }
290  return result;
291 }
292 
293 
295  key_part_map keypart_map,
296  unsigned char *cur_prefix)
297 {
298  for (;;)
299  {
300  int result;
301  key_range start_key, end_key;
302  if (last_range)
303  {
304  /* Read the next record in the same range with prefix after cur_prefix. */
305  assert(cur_prefix != 0);
306  result= cursor->index_read_map(record,
307  cur_prefix,
308  keypart_map,
309  HA_READ_AFTER_KEY);
310  if (result || (cursor->compare_key(cursor->end_range) <= 0))
311  return result;
312  }
313 
314  uint32_t count= ranges.size() - (cur_range - (optimizer::QuickRange**) ranges.buffer);
315  if (count == 0)
316  {
317  /* Ranges have already been used up before. None is left for read. */
318  last_range= 0;
319  return HA_ERR_END_OF_FILE;
320  }
321  last_range= *(cur_range++);
322 
323  start_key.key= (const unsigned char*) last_range->min_key;
324  start_key.length= min(last_range->min_length, (uint16_t)prefix_length);
325  start_key.keypart_map= last_range->min_keypart_map & keypart_map;
326  start_key.flag= ((last_range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
327  (last_range->flag & EQ_RANGE) ?
328  HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
329  end_key.key= (const unsigned char*) last_range->max_key;
330  end_key.length= min(last_range->max_length, (uint16_t)prefix_length);
331  end_key.keypart_map= last_range->max_keypart_map & keypart_map;
332  /*
333  We use READ_AFTER_KEY here because if we are reading on a key
334  prefix we want to find all keys with this prefix
335  */
336  end_key.flag= (last_range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
337  HA_READ_AFTER_KEY);
338 
339  result= cursor->read_range_first(last_range->min_keypart_map ? &start_key : 0,
340  last_range->max_keypart_map ? &end_key : 0,
341  test(last_range->flag & EQ_RANGE),
342  sorted);
343  if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
344  last_range= 0; // Stop searching
345 
346  if (result != HA_ERR_END_OF_FILE)
347  return result;
348  last_range= 0; // No matching rows; go to next range
349  }
350 }
351 
352 
354 {
355  optimizer::QuickRange *res= NULL;
356  uint32_t min= 0;
357  uint32_t max= ranges.size() - 1;
358  uint32_t mid= (max + min) / 2;
359 
360  while (min != max)
361  {
362  if (cmp_next(reinterpret_cast<optimizer::QuickRange**>(ranges.buffer)[mid]))
363  {
364  /* current row value > mid->max */
365  min= mid + 1;
366  }
367  else
368  max= mid;
369  mid= (min + max) / 2;
370  }
371  res= reinterpret_cast<optimizer::QuickRange**>(ranges.buffer)[mid];
372  return not cmp_next(res) && not cmp_prev(res);
373 }
374 
375 
377 {
378  if (range_arg->flag & NO_MAX_RANGE)
379  return 0; /* key can't be to large */
380 
381  KEY_PART *key_part= key_parts;
382  uint32_t store_length;
383 
384  for (unsigned char *key=range_arg->max_key, *end=key+range_arg->max_length;
385  key < end;
386  key+= store_length, key_part++)
387  {
388  int cmp;
389  store_length= key_part->store_length;
390  if (key_part->null_bit)
391  {
392  if (*key)
393  {
394  if (! key_part->field->is_null())
395  return 1;
396  continue;
397  }
398  else if (key_part->field->is_null())
399  return 0;
400  key++; // Skip null byte
401  store_length--;
402  }
403  if ((cmp= key_part->field->key_cmp(key, key_part->length)) < 0)
404  return 0;
405  if (cmp > 0)
406  return 1;
407  }
408  return (range_arg->flag & NEAR_MAX) ? 1 : 0; // Exact match
409 }
410 
411 
413 {
414  if (range_arg->flag & NO_MIN_RANGE)
415  return 0; /* key can't be to small */
416 
417  int cmp= key_cmp(key_part_info,
418  range_arg->min_key,
419  range_arg->min_length);
420  if (cmp > 0 || (cmp == 0 && (range_arg->flag & NEAR_MIN) == false))
421  return 0;
422  return 1; // outside of range
423 }
424 
425 
427 {
428  KeyInfo *key_info= head->key_info + index;
429  str->append(key_info->name);
430 }
431 
432 
434  string *used_lengths)
435 {
436  char buf[64];
437  uint32_t length;
438  KeyInfo *key_info= head->key_info + index;
439  key_names->append(key_info->name);
440  length= internal::int64_t2str(max_used_key_length, buf, 10) - buf;
441  used_lengths->append(buf, length);
442 }
443 
444 
445 /*
446  This is a hack: we inherit from QUICK_SELECT so that we can use the
447  get_next() interface, but we have to hold a pointer to the original
448  QUICK_SELECT because its data are used all over the place. What
449  should be done is to factor out the data that is needed into a base
450  class (QUICK_SELECT), and then have two subclasses (_ASC and _DESC)
451  which handle the ranges and implement the get_next() function. But
452  for now, this seems to work right at least.
453  */
454 optimizer::QuickSelectDescending::QuickSelectDescending(optimizer::QuickRangeSelect *q, uint32_t used_key_parts_arg, bool *)
455  :
456  optimizer::QuickRangeSelect(*q),
457  used_key_parts(used_key_parts_arg)
458 {
460  optimizer::QuickRange **end_range= pr + ranges.size();
461  for (; pr != end_range; pr++)
462  {
463  rev_ranges.push_back(*pr);
464  }
465  rev_it= rev_ranges.begin();
466 
467  /* Remove EQ_RANGE flag for keys that are not using the full key */
468  BOOST_FOREACH(QuickRange* it, rev_ranges)
469  {
470  if ((it->flag & EQ_RANGE) && head->key_info[index].key_length != it->max_length)
471  {
472  it->flag&= ~EQ_RANGE;
473  }
474  }
475  q->dont_free= 1; // Don't free shared mem
476  delete q;
477 }
478 
479 
481 {
482  /* The max key is handled as follows:
483  * - if there is NO_MAX_RANGE, start at the end and move backwards
484  * - if it is an EQ_RANGE, which means that max key covers the entire
485  * key, go directly to the key and read through it (sorting backwards is
486  * same as sorting forwards)
487  * - if it is NEAR_MAX, go to the key or next, step back once, and
488  * move backwards
489  * - otherwise (not NEAR_MAX == include the key), go after the key,
490  * step back once, and move backwards
491  */
492  for (;;)
493  {
494  int result;
495  if (last_range)
496  { // Already read through key
497  result= ((last_range->flag & EQ_RANGE &&
498  used_key_parts <= head->key_info[index].key_parts) ?
499  cursor->index_next_same(record, last_range->min_key,
500  last_range->min_length) :
501  cursor->index_prev(record));
502  if (! result)
503  {
504  if (cmp_prev(*(rev_it - 1)) == 0)
505  return 0;
506  }
507  else if (result != HA_ERR_END_OF_FILE)
508  return result;
509  }
510 
511  if (rev_it == rev_ranges.end())
512  {
513  return HA_ERR_END_OF_FILE; // All ranges used
514  }
515  last_range= *rev_it;
516  ++rev_it;
517 
518  if (last_range->flag & NO_MAX_RANGE) // Read last record
519  {
520  int local_error;
521  if ((local_error= cursor->index_last(record)))
522  return local_error; // Empty table
523  if (cmp_prev(last_range) == 0)
524  return 0;
525  last_range= 0; // No match; go to next range
526  continue;
527  }
528 
529  if (last_range->flag & EQ_RANGE
530  && used_key_parts <= head->key_info[index].key_parts)
531  {
532  result = cursor->index_read_map(record,
533  last_range->max_key,
534  last_range->max_keypart_map,
535  HA_READ_KEY_EXACT);
536  }
537  else
538  {
539  assert(last_range->flag & NEAR_MAX ||
540  (last_range->flag & EQ_RANGE &&
541  used_key_parts > head->key_info[index].key_parts) ||
542  range_reads_after_key(last_range));
543  result= cursor->index_read_map(record,
544  last_range->max_key,
545  last_range->max_keypart_map,
546  ((last_range->flag & NEAR_MAX) ?
547  HA_READ_BEFORE_KEY :
548  HA_READ_PREFIX_LAST_OR_PREV));
549  }
550  if (result)
551  {
552  if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
553  return result;
554  last_range= 0; // Not found, to next range
555  continue;
556  }
557  if (cmp_prev(last_range) == 0)
558  {
559  if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
560  last_range= 0; // Stop searching
561  return 0; // Found key is in range
562  }
563  last_range= 0; // To next range
564  }
565 }
566 
567 
568 /*
569  * true if this range will require using HA_READ_AFTER_KEY
570  See comment in get_next() about this
571  */
572 bool optimizer::QuickSelectDescending::range_reads_after_key(optimizer::QuickRange *range_arg)
573 {
574  return ((range_arg->flag & (NO_MAX_RANGE | NEAR_MAX)) ||
575  ! (range_arg->flag & EQ_RANGE) ||
576  head->key_info[index].key_length != range_arg->max_length) ? 1 : 0;
577 }
578 
579 
580 } /* namespace drizzled */
void add_keys_and_lengths(std::string *key_names, std::string *used_lengths)
int get_next_prefix(uint32_t prefix_length, key_part_map keypart_map, unsigned char *cur_prefix)
TODO: Rename this file - func.h is stupid.
int key_cmp(KeyPartInfo *key_part, const unsigned char *key, uint32_t key_length)
Definition: key.cc:438
KeyInfo * key_info
Definition: table.h:141
static void store_length(unsigned char *to, uint32_t length, uint32_t pack_length)
Definition: filesort.cc:753
int init_ror_merged_scan(bool reuse_handler)
memory::Root * mem_root
Definition: session.h:118