drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
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
34using namespace std;
35
36namespace drizzled {
37
38
39optimizer::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 alloc= memory::Root();
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
104optimizer::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
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
185end:
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
207failure:
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 {
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;
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;
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
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 */
454optimizer::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 for (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 */
572bool 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.
static void store_length(unsigned char *to, uint32_t length, uint32_t pack_length)
Definition filesort.cc:755
int key_cmp(KeyPartInfo *key_part, const unsigned char *key, uint32_t key_length)
STL namespace.