« back to all changes in this revision
Viewing changes to drizzled/optimizer/quick_range_select.cc
- browse files at revision 1237.13.5
- compare with another revision
- compare with revision 1237.13.5
- download diff
- download tarball
- view history from revision 1237.13.5
- Committer: Padraig O'Sullivan
- Date: 2009-12-07 21:50:09 UTC
- mto: (1192.3.76 pandora-build) (1240.3.1 build) (1241.2.6 build)
- mto: This revision was merged to the branch mainline in revision 1241.
- Revision ID: osullivan.padraig@gmail.com-20091207215009-y0o88dedx9lz2fl8
Split some classes from the range optimizer out in to their own header and implementation files.
Corrected the case on these classes also to adhere to the coding standards. Cleaned up any style
issues in any code I came across while moving code.
Corrected the case on these classes also to adhere to the coding standards. Cleaned up any style
issues in any code I came across while moving code.
- files added:
- drizzled/optimizer/quick_index_merge_select.cc
- files modified:
- drizzled/Makefile.am
added
removed
drizzled/optimizer/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
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 "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"
26
27
using namespace std;
28
using namespace drizzled;
29
30
31
optimizer::QuickRangeSelect::QuickRangeSelect(Session *session,
32
Table *table,
33
uint32_t key_nr,
34
bool no_alloc,
35
MEM_ROOT *parent_alloc,
36
bool *create_error)
37
:
38
cursor(NULL),
39
ranges(),
40
in_ror_merged_scan(false),
41
column_bitmap(),
42
save_read_set(NULL),
43
save_write_set(NULL),
44
free_file(false),
45
cur_range(NULL),
46
last_range(NULL),
47
qr_traversal_ctx(),
48
mrr_buf_size(0),
49
mrr_buf_desc(NULL),
50
key_parts(NULL),
51
dont_free(false),
52
mrr_flags(0),
53
alloc()
54
{
55
my_bitmap_map *bitmap= NULL;
56
57
sorted= 0;
58
index= key_nr;
59
head= table;
60
key_part_info= head->key_info[index].key_part;
61
my_init_dynamic_array(&ranges, sizeof(optimizer::QuickRange*), 16, 16);
62
63
/* 'session' is not accessible in QuickRangeSelect::reset(). */
64
mrr_buf_size= session->variables.read_rnd_buff_size;
65
mrr_buf_desc= NULL;
66
67
if (! no_alloc && ! parent_alloc)
68
{
69
// Allocates everything through the internal memroot
70
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
71
session->mem_root= &alloc;
72
}
73
else
74
{
75
memset(&alloc, 0, sizeof(alloc));
76
}
77
78
cursor= head->cursor;
79
record= head->record[0];
80
save_read_set= head->read_set;
81
save_write_set= head->write_set;
82
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.
86
*/
87
88
bitmap= reinterpret_cast<my_bitmap_map*>(sql_alloc(head->s->column_bitmap_size));
89
if (! bitmap)
90
{
91
column_bitmap.setBitmap(NULL);
92
*create_error= 1;
93
}
94
else
95
{
96
column_bitmap.init(bitmap, head->s->fields);
97
}
98
}
99
100
101
int optimizer::QuickRangeSelect::init()
102
{
103
if (cursor->inited != Cursor::NONE)
104
cursor->ha_index_or_rnd_end();
105
return (cursor->ha_index_init(index, 1));
106
}
107
108
109
void optimizer::QuickRangeSelect::range_end()
110
{
111
if (cursor->inited != Cursor::NONE)
112
cursor->ha_index_or_rnd_end();
113
}
114
115
116
optimizer::QuickRangeSelect::~QuickRangeSelect()
117
{
118
if (! dont_free)
119
{
120
/* cursor is NULL for CPK scan on covering ROR-intersection */
121
if (cursor)
122
{
123
range_end();
124
if (head->key_read)
125
{
126
head->key_read= 0;
127
cursor->extra(HA_EXTRA_NO_KEYREAD);
128
}
129
if (free_file)
130
{
131
cursor->ha_external_lock(current_session, F_UNLCK);
132
cursor->close();
133
delete cursor;
134
}
135
}
136
delete_dynamic(&ranges); /* ranges are allocated in alloc */
137
free_root(&alloc,MYF(0));
138
}
139
head->column_bitmaps_set(save_read_set, save_write_set);
140
assert(mrr_buf_desc == NULL);
141
if (mrr_buf_desc)
142
{
143
free(mrr_buf_desc);
144
}
145
}
146
147
148
int optimizer::QuickRangeSelect::init_ror_merged_scan(bool reuse_handler)
149
{
150
Cursor *save_file= cursor, *org_file;
151
Session *session;
152
153
in_ror_merged_scan= 1;
154
if (reuse_handler)
155
{
156
if (init() || reset())
157
{
158
return 0;
159
}
160
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
161
goto end;
162
}
163
164
/* Create a separate Cursor object for this quick select */
165
if (free_file)
166
{
167
/* already have own 'Cursor' object. */
168
return 0;
169
}
170
171
session= head->in_use;
172
if (! (cursor= head->cursor->clone(session->mem_root)))
173
{
174
/*
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.
180
*/
181
my_error(ER_OUT_OF_RESOURCES, MYF(0));
182
/* Caller will free the memory */
183
goto failure;
184
}
185
186
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
187
188
if (cursor->ha_external_lock(session, F_RDLCK))
189
goto failure;
190
191
if (init() || reset())
192
{
193
cursor->ha_external_lock(session, F_UNLCK);
194
cursor->close();
195
goto failure;
196
}
197
free_file= true;
198
last_rowid= cursor->ref;
199
200
end:
201
/*
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()
206
*/
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)
211
{
212
head->key_read= 1;
213
head->mark_columns_used_by_index(index);
214
}
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);
219
220
return 0;
221
222
failure:
223
head->column_bitmaps_set(save_read_set, save_write_set);
224
delete cursor;
225
cursor= save_file;
226
return 0;
227
}
228
229
230
void optimizer::QuickRangeSelect::save_last_pos()
231
{
232
cursor->position(record);
233
}
234
235
236
bool optimizer::QuickRangeSelect::unique_key_range()
237
{
238
if (ranges.elements == 1)
239
{
240
optimizer::QuickRange *tmp= *((optimizer::QuickRange**)ranges.buffer);
241
if ((tmp->flag & (EQ_RANGE | NULL_RANGE)) == EQ_RANGE)
242
{
243
KEY *key=head->key_info+index;
244
return ((key->flags & (HA_NOSAME)) == HA_NOSAME &&
245
key->key_length == tmp->min_length);
246
}
247
}
248
return false;
249
}
250
251
252
int optimizer::QuickRangeSelect::reset()
253
{
254
uint32_t buf_size= 0;
255
unsigned char *mrange_buff= NULL;
256
int error= 0;
257
HANDLER_BUFFER empty_buf;
258
last_range= NULL;
259
cur_range= (optimizer::QuickRange**) ranges.buffer;
260
261
if (cursor->inited == Cursor::NONE && (error= cursor->ha_index_init(index, 1)))
262
{
263
return error;
264
}
265
266
/* Allocate buffer if we need one but haven't allocated it yet */
267
if (mrr_buf_size && ! mrr_buf_desc)
268
{
269
buf_size= mrr_buf_size;
270
while (buf_size && ! memory::multi_malloc(false,
271
&mrr_buf_desc,
272
sizeof(*mrr_buf_desc),
273
&mrange_buff,
274
buf_size,
275
NULL))
276
{
277
/* Try to shrink the buffers until both are 0. */
278
buf_size/= 2;
279
}
280
if (! mrr_buf_desc)
281
{
282
return HA_ERR_OUT_OF_MEM;
283
}
284
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;
289
}
290
291
if (! mrr_buf_desc)
292
{
293
empty_buf.buffer= NULL;
294
empty_buf.buffer_end= NULL;
295
empty_buf.end_of_used_area= NULL;
296
}
297
298
if (sorted)
299
{
300
mrr_flags|= HA_MRR_SORTED;
301
}
302
RANGE_SEQ_IF seq_funcs= {
303
optimizer::quick_range_seq_init,
304
optimizer::quick_range_seq_next
305
};
306
error= cursor->multi_range_read_init(&seq_funcs,
307
(void*) this,
308
ranges.elements,
309
mrr_flags,
310
mrr_buf_desc ? mrr_buf_desc : &empty_buf);
311
return error;
312
}
313
314
315
int optimizer::QuickRangeSelect::get_next()
316
{
317
char *dummy= NULL;
318
if (in_ror_merged_scan)
319
{
320
/*
321
We don't need to signal the bitmap change as the bitmap is always the
322
same for this head->cursor
323
*/
324
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
325
}
326
327
int result= cursor->multi_range_read_next(&dummy);
328
329
if (in_ror_merged_scan)
330
{
331
/* Restore bitmaps set on entry */
332
head->column_bitmaps_set(save_read_set, save_write_set);
333
}
334
return result;
335
}
336
337
338
int optimizer::QuickRangeSelect::get_next_prefix(uint32_t prefix_length,
339
key_part_map keypart_map,
340
unsigned char *cur_prefix)
341
{
342
for (;;)
343
{
344
int result;
345
key_range start_key, end_key;
346
if (last_range)
347
{
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,
351
cur_prefix,
352
keypart_map,
353
HA_READ_AFTER_KEY);
354
if (result || (cursor->compare_key(cursor->end_range) <= 0))
355
return result;
356
}
357
358
uint32_t count= ranges.elements - (cur_range - (optimizer::QuickRange**) ranges.buffer);
359
if (count == 0)
360
{
361
/* Ranges have already been used up before. None is left for read. */
362
last_range= 0;
363
return HA_ERR_END_OF_FILE;
364
}
365
last_range= *(cur_range++);
366
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;
376
/*
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
379
*/
380
end_key.flag= (last_range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
381
HA_READ_AFTER_KEY);
382
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),
386
sorted);
387
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
388
last_range= 0; // Stop searching
389
390
if (result != HA_ERR_END_OF_FILE)
391
return result;
392
last_range= 0; // No matching rows; go to next range
393
}
394
}
395
396
397
bool optimizer::QuickRangeSelect::row_in_ranges()
398
{
399
optimizer::QuickRange *res= NULL;
400
uint32_t min= 0;
401
uint32_t max= ranges.elements - 1;
402
uint32_t mid= (max + min) / 2;
403
404
while (min != max)
405
{
406
if (cmp_next(*(optimizer::QuickRange**)dynamic_array_ptr(&ranges, mid)))
407
{
408
/* current row value > mid->max */
409
min= mid + 1;
410
}
411
else
412
max= mid;
413
mid= (min + max) / 2;
414
}
415
res= *(optimizer::QuickRange**)dynamic_array_ptr(&ranges, mid);
416
return (! cmp_next(res) && ! cmp_prev(res));
417
}
418
419
420
int optimizer::QuickRangeSelect::cmp_next(optimizer::QuickRange *range_arg)
421
{
422
if (range_arg->flag & NO_MAX_RANGE)
423
return 0; /* key can't be to large */
424
425
KEY_PART *key_part= key_parts;
426
uint32_t store_length;
427
428
for (unsigned char *key=range_arg->max_key, *end=key+range_arg->max_length;
429
key < end;
430
key+= store_length, key_part++)
431
{
432
int cmp;
433
store_length= key_part->store_length;
434
if (key_part->null_bit)
435
{
436
if (*key)
437
{
438
if (! key_part->field->is_null())
439
return 1;
440
continue;
441
}
442
else if (key_part->field->is_null())
443
return 0;
444
key++; // Skip null byte
445
store_length--;
446
}
447
if ((cmp= key_part->field->key_cmp(key, key_part->length)) < 0)
448
return 0;
449
if (cmp > 0)
450
return 1;
451
}
452
return (range_arg->flag & NEAR_MAX) ? 1 : 0; // Exact match
453
}
454
455
456
int optimizer::QuickRangeSelect::cmp_prev(optimizer::QuickRange *range_arg)
457
{
458
int cmp;
459
if (range_arg->flag & NO_MIN_RANGE)
460
return 0; /* key can't be to small */
461
462
cmp= key_cmp(key_part_info,
463
range_arg->min_key,
464
range_arg->min_length);
465
if (cmp > 0 || (cmp == 0 && (range_arg->flag & NEAR_MIN) == false))
466
return 0;
467
return 1; // outside of range
468
}
469
470
471
void optimizer::QuickRangeSelect::add_info_string(String *str)
472
{
473
KEY *key_info= head->key_info + index;
474
str->append(key_info->name);
475
}
476
477
478
void optimizer::QuickRangeSelect::add_keys_and_lengths(String *key_names,
479
String *used_lengths)
480
{
481
char buf[64];
482
uint32_t length;
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);
487
}
488
489
490
/*
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.
498
*/
499
optimizer::QuickSelectDescending::QuickSelectDescending(optimizer::QuickRangeSelect *q, uint32_t, bool *)
500
:
501
optimizer::QuickRangeSelect(*q),
502
rev_it(rev_ranges)
503
{
504
optimizer::QuickRange *r= NULL;
505
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);
510
511
/* Remove EQ_RANGE flag for keys that are not using the full key */
512
for (r = rev_it++; r; r= rev_it++)
513
{
514
if ((r->flag & EQ_RANGE) &&
515
head->key_info[index].key_length != r->max_length)
516
r->flag&= ~EQ_RANGE;
517
}
518
rev_it.rewind();
519
q->dont_free= 1; // Don't free shared mem
520
delete q;
521
}
522
523
524
int optimizer::QuickSelectDescending::get_next()
525
{
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
532
* move backwards
533
* - otherwise (not NEAR_MAX == include the key), go after the key,
534
* step back once, and move backwards
535
*/
536
for (;;)
537
{
538
int result;
539
if (last_range)
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));
545
if (! result)
546
{
547
if (cmp_prev(*rev_it.ref()) == 0)
548
return 0;
549
}
550
else if (result != HA_ERR_END_OF_FILE)
551
return result;
552
}
553
554
if (! (last_range= rev_it++))
555
return HA_ERR_END_OF_FILE; // All ranges used
556
557
if (last_range->flag & NO_MAX_RANGE) // Read last record
558
{
559
int local_error;
560
if ((local_error= cursor->index_last(record)))
561
return local_error; // Empty table
562
if (cmp_prev(last_range) == 0)
563
return 0;
564
last_range= 0; // No match; go to next range
565
continue;
566
}
567
568
if (last_range->flag & EQ_RANGE)
569
{
570
result = cursor->index_read_map(record,
571
last_range->max_key,
572
last_range->max_keypart_map,
573
HA_READ_KEY_EXACT);
574
}
575
else
576
{
577
assert(last_range->flag & NEAR_MAX ||
578
range_reads_after_key(last_range));
579
result= cursor->index_read_map(record,
580
last_range->max_key,
581
last_range->max_keypart_map,
582
((last_range->flag & NEAR_MAX) ?
583
HA_READ_BEFORE_KEY :
584
HA_READ_PREFIX_LAST_OR_PREV));
585
}
586
if (result)
587
{
588
if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
589
return result;
590
last_range= 0; // Not found, to next range
591
continue;
592
}
593
if (cmp_prev(last_range) == 0)
594
{
595
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
596
last_range= 0; // Stop searching
597
return 0; // Found key is in range
598
}
599
last_range= 0; // To next range
600
}
601
}
602
603
604
/*
605
* true if this range will require using HA_READ_AFTER_KEY
606
See comment in get_next() about this
607
*/
608
bool optimizer::QuickSelectDescending::range_reads_after_key(optimizer::QuickRange *range_arg)
609
{
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;
613
}
614
615
Loggerhead is a web-based interface for Breezy
Version: 2.0.1