1
/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2
* vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
4
* Copyright (C) 2008-2009 Sun Microsystems
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.
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.
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
20
#include "drizzled/server_includes.h"
21
#include "drizzled/session.h"
22
#include "drizzled/optimizer/quick_range.h"
23
#include "drizzled/optimizer/quick_range_select.h"
24
#include "mysys/my_bitmap.h"
25
#include "drizzled/memory/multi_malloc.h"
28
using namespace drizzled;
31
optimizer::QuickRangeSelect::QuickRangeSelect(Session *session,
35
MEM_ROOT *parent_alloc,
40
in_ror_merged_scan(false),
55
my_bitmap_map *bitmap= NULL;
60
key_part_info= head->key_info[index].key_part;
61
my_init_dynamic_array(&ranges, sizeof(optimizer::QuickRange*), 16, 16);
63
/* 'session' is not accessible in QuickRangeSelect::reset(). */
64
mrr_buf_size= session->variables.read_rnd_buff_size;
67
if (! no_alloc && ! parent_alloc)
69
// Allocates everything through the internal memroot
70
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
71
session->mem_root= &alloc;
75
memset(&alloc, 0, sizeof(alloc));
79
record= head->record[0];
80
save_read_set= head->read_set;
81
save_write_set= head->write_set;
83
/* Allocate a bitmap for used columns. Using sql_alloc instead of malloc
84
simply as a "fix" to the MySQL 6.0 code that also free()s it at the
85
same time we destroy the mem_root.
88
bitmap= reinterpret_cast<my_bitmap_map*>(sql_alloc(head->s->column_bitmap_size));
91
column_bitmap.setBitmap(NULL);
96
column_bitmap.init(bitmap, head->s->fields);
101
int optimizer::QuickRangeSelect::init()
103
if (cursor->inited != Cursor::NONE)
104
cursor->ha_index_or_rnd_end();
105
return (cursor->ha_index_init(index, 1));
109
void optimizer::QuickRangeSelect::range_end()
111
if (cursor->inited != Cursor::NONE)
112
cursor->ha_index_or_rnd_end();
116
optimizer::QuickRangeSelect::~QuickRangeSelect()
120
/* cursor is NULL for CPK scan on covering ROR-intersection */
127
cursor->extra(HA_EXTRA_NO_KEYREAD);
131
cursor->ha_external_lock(current_session, F_UNLCK);
136
delete_dynamic(&ranges); /* ranges are allocated in alloc */
137
free_root(&alloc,MYF(0));
139
head->column_bitmaps_set(save_read_set, save_write_set);
140
assert(mrr_buf_desc == NULL);
148
int optimizer::QuickRangeSelect::init_ror_merged_scan(bool reuse_handler)
150
Cursor *save_file= cursor, *org_file;
153
in_ror_merged_scan= 1;
156
if (init() || reset())
160
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
164
/* Create a separate Cursor object for this quick select */
167
/* already have own 'Cursor' object. */
171
session= head->in_use;
172
if (! (cursor= head->cursor->clone(session->mem_root)))
175
Manually set the error flag. Note: there seems to be quite a few
176
places where a failure could cause the server to "hang" the client by
177
sending no response to a query. ATM those are not real errors because
178
the storage engine calls in question happen to never fail with the
179
existing storage engines.
181
my_error(ER_OUT_OF_RESOURCES, MYF(0));
182
/* Caller will free the memory */
186
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
188
if (cursor->ha_external_lock(session, F_RDLCK))
191
if (init() || reset())
193
cursor->ha_external_lock(session, F_UNLCK);
198
last_rowid= cursor->ref;
202
We are only going to read key fields and call position() on 'cursor'
203
The following sets head->tmp_set to only use this key and then updates
204
head->read_set and head->write_set to use this bitmap.
205
The now bitmap is stored in 'column_bitmap' which is used in ::get_next()
207
org_file= head->cursor;
208
head->cursor= cursor;
209
/* We don't have to set 'head->keyread' here as the 'cursor' is unique */
210
if (! head->no_keyread)
213
head->mark_columns_used_by_index(index);
215
head->prepare_for_position();
216
head->cursor= org_file;
217
column_bitmap= *head->read_set;
218
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
223
head->column_bitmaps_set(save_read_set, save_write_set);
230
void optimizer::QuickRangeSelect::save_last_pos()
232
cursor->position(record);
236
bool optimizer::QuickRangeSelect::unique_key_range()
238
if (ranges.elements == 1)
240
optimizer::QuickRange *tmp= *((optimizer::QuickRange**)ranges.buffer);
241
if ((tmp->flag & (EQ_RANGE | NULL_RANGE)) == EQ_RANGE)
243
KEY *key=head->key_info+index;
244
return ((key->flags & (HA_NOSAME)) == HA_NOSAME &&
245
key->key_length == tmp->min_length);
252
int optimizer::QuickRangeSelect::reset()
254
uint32_t buf_size= 0;
255
unsigned char *mrange_buff= NULL;
257
HANDLER_BUFFER empty_buf;
259
cur_range= (optimizer::QuickRange**) ranges.buffer;
261
if (cursor->inited == Cursor::NONE && (error= cursor->ha_index_init(index, 1)))
266
/* Allocate buffer if we need one but haven't allocated it yet */
267
if (mrr_buf_size && ! mrr_buf_desc)
269
buf_size= mrr_buf_size;
270
while (buf_size && ! memory::multi_malloc(false,
272
sizeof(*mrr_buf_desc),
277
/* Try to shrink the buffers until both are 0. */
282
return HA_ERR_OUT_OF_MEM;
285
/* Initialize the Cursor buffer. */
286
mrr_buf_desc->buffer= mrange_buff;
287
mrr_buf_desc->buffer_end= mrange_buff + buf_size;
288
mrr_buf_desc->end_of_used_area= mrange_buff;
293
empty_buf.buffer= NULL;
294
empty_buf.buffer_end= NULL;
295
empty_buf.end_of_used_area= NULL;
300
mrr_flags|= HA_MRR_SORTED;
302
RANGE_SEQ_IF seq_funcs= {
303
optimizer::quick_range_seq_init,
304
optimizer::quick_range_seq_next
306
error= cursor->multi_range_read_init(&seq_funcs,
310
mrr_buf_desc ? mrr_buf_desc : &empty_buf);
315
int optimizer::QuickRangeSelect::get_next()
318
if (in_ror_merged_scan)
321
We don't need to signal the bitmap change as the bitmap is always the
322
same for this head->cursor
324
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
327
int result= cursor->multi_range_read_next(&dummy);
329
if (in_ror_merged_scan)
331
/* Restore bitmaps set on entry */
332
head->column_bitmaps_set(save_read_set, save_write_set);
338
int optimizer::QuickRangeSelect::get_next_prefix(uint32_t prefix_length,
339
key_part_map keypart_map,
340
unsigned char *cur_prefix)
345
key_range start_key, end_key;
348
/* Read the next record in the same range with prefix after cur_prefix. */
349
assert(cur_prefix != 0);
350
result= cursor->index_read_map(record,
354
if (result || (cursor->compare_key(cursor->end_range) <= 0))
358
uint32_t count= ranges.elements - (cur_range - (optimizer::QuickRange**) ranges.buffer);
361
/* Ranges have already been used up before. None is left for read. */
363
return HA_ERR_END_OF_FILE;
365
last_range= *(cur_range++);
367
start_key.key= (const unsigned char*) last_range->min_key;
368
start_key.length= min(last_range->min_length, (uint16_t)prefix_length);
369
start_key.keypart_map= last_range->min_keypart_map & keypart_map;
370
start_key.flag= ((last_range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
371
(last_range->flag & EQ_RANGE) ?
372
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
373
end_key.key= (const unsigned char*) last_range->max_key;
374
end_key.length= min(last_range->max_length, (uint16_t)prefix_length);
375
end_key.keypart_map= last_range->max_keypart_map & keypart_map;
377
We use READ_AFTER_KEY here because if we are reading on a key
378
prefix we want to find all keys with this prefix
380
end_key.flag= (last_range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
383
result= cursor->read_range_first(last_range->min_keypart_map ? &start_key : 0,
384
last_range->max_keypart_map ? &end_key : 0,
385
test(last_range->flag & EQ_RANGE),
387
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
388
last_range= 0; // Stop searching
390
if (result != HA_ERR_END_OF_FILE)
392
last_range= 0; // No matching rows; go to next range
397
bool optimizer::QuickRangeSelect::row_in_ranges()
399
optimizer::QuickRange *res= NULL;
401
uint32_t max= ranges.elements - 1;
402
uint32_t mid= (max + min) / 2;
406
if (cmp_next(*(optimizer::QuickRange**)dynamic_array_ptr(&ranges, mid)))
408
/* current row value > mid->max */
413
mid= (min + max) / 2;
415
res= *(optimizer::QuickRange**)dynamic_array_ptr(&ranges, mid);
416
return (! cmp_next(res) && ! cmp_prev(res));
420
int optimizer::QuickRangeSelect::cmp_next(optimizer::QuickRange *range_arg)
422
if (range_arg->flag & NO_MAX_RANGE)
423
return 0; /* key can't be to large */
425
KEY_PART *key_part= key_parts;
426
uint32_t store_length;
428
for (unsigned char *key=range_arg->max_key, *end=key+range_arg->max_length;
430
key+= store_length, key_part++)
433
store_length= key_part->store_length;
434
if (key_part->null_bit)
438
if (! key_part->field->is_null())
442
else if (key_part->field->is_null())
444
key++; // Skip null byte
447
if ((cmp= key_part->field->key_cmp(key, key_part->length)) < 0)
452
return (range_arg->flag & NEAR_MAX) ? 1 : 0; // Exact match
456
int optimizer::QuickRangeSelect::cmp_prev(optimizer::QuickRange *range_arg)
459
if (range_arg->flag & NO_MIN_RANGE)
460
return 0; /* key can't be to small */
462
cmp= key_cmp(key_part_info,
464
range_arg->min_length);
465
if (cmp > 0 || (cmp == 0 && (range_arg->flag & NEAR_MIN) == false))
467
return 1; // outside of range
471
void optimizer::QuickRangeSelect::add_info_string(String *str)
473
KEY *key_info= head->key_info + index;
474
str->append(key_info->name);
478
void optimizer::QuickRangeSelect::add_keys_and_lengths(String *key_names,
479
String *used_lengths)
483
KEY *key_info= head->key_info + index;
484
key_names->append(key_info->name);
485
length= int64_t2str(max_used_key_length, buf, 10) - buf;
486
used_lengths->append(buf, length);
491
This is a hack: we inherit from QUICK_SELECT so that we can use the
492
get_next() interface, but we have to hold a pointer to the original
493
QUICK_SELECT because its data are used all over the place. What
494
should be done is to factor out the data that is needed into a base
495
class (QUICK_SELECT), and then have two subclasses (_ASC and _DESC)
496
which handle the ranges and implement the get_next() function. But
497
for now, this seems to work right at least.
499
optimizer::QuickSelectDescending::QuickSelectDescending(optimizer::QuickRangeSelect *q, uint32_t, bool *)
501
optimizer::QuickRangeSelect(*q),
504
optimizer::QuickRange *r= NULL;
506
optimizer::QuickRange **pr= (optimizer::QuickRange**)ranges.buffer;
507
optimizer::QuickRange **end_range= pr + ranges.elements;
508
for (; pr != end_range; pr++)
509
rev_ranges.push_front(*pr);
511
/* Remove EQ_RANGE flag for keys that are not using the full key */
512
for (r = rev_it++; r; r= rev_it++)
514
if ((r->flag & EQ_RANGE) &&
515
head->key_info[index].key_length != r->max_length)
519
q->dont_free= 1; // Don't free shared mem
524
int optimizer::QuickSelectDescending::get_next()
526
/* The max key is handled as follows:
527
* - if there is NO_MAX_RANGE, start at the end and move backwards
528
* - if it is an EQ_RANGE, which means that max key covers the entire
529
* key, go directly to the key and read through it (sorting backwards is
530
* same as sorting forwards)
531
* - if it is NEAR_MAX, go to the key or next, step back once, and
533
* - otherwise (not NEAR_MAX == include the key), go after the key,
534
* step back once, and move backwards
540
{ // Already read through key
541
result= ((last_range->flag & EQ_RANGE) ?
542
cursor->index_next_same(record, last_range->min_key,
543
last_range->min_length) :
544
cursor->index_prev(record));
547
if (cmp_prev(*rev_it.ref()) == 0)
550
else if (result != HA_ERR_END_OF_FILE)
554
if (! (last_range= rev_it++))
555
return HA_ERR_END_OF_FILE; // All ranges used
557
if (last_range->flag & NO_MAX_RANGE) // Read last record
560
if ((local_error= cursor->index_last(record)))
561
return local_error; // Empty table
562
if (cmp_prev(last_range) == 0)
564
last_range= 0; // No match; go to next range
568
if (last_range->flag & EQ_RANGE)
570
result = cursor->index_read_map(record,
572
last_range->max_keypart_map,
577
assert(last_range->flag & NEAR_MAX ||
578
range_reads_after_key(last_range));
579
result= cursor->index_read_map(record,
581
last_range->max_keypart_map,
582
((last_range->flag & NEAR_MAX) ?
584
HA_READ_PREFIX_LAST_OR_PREV));
588
if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
590
last_range= 0; // Not found, to next range
593
if (cmp_prev(last_range) == 0)
595
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
596
last_range= 0; // Stop searching
597
return 0; // Found key is in range
599
last_range= 0; // To next range
605
* true if this range will require using HA_READ_AFTER_KEY
606
See comment in get_next() about this
608
bool optimizer::QuickSelectDescending::range_reads_after_key(optimizer::QuickRange *range_arg)
610
return ((range_arg->flag & (NO_MAX_RANGE | NEAR_MAX)) ||
611
! (range_arg->flag & EQ_RANGE) ||
612
head->key_info[index].key_length != range_arg->max_length) ? 1 : 0;