« back to all changes in this revision
Viewing changes to drizzled/optimizer/quick_range_select.cc
- browse files at revision 1240.1.4
- compare with another revision
- compare with revision 2466
- download diff
- download tarball
- view history from revision 1240.1.4
- Committer: Brian Aker
- Date: 2009-12-08 22:02:21 UTC
- mfrom: (1240.3.8 build)
- mto: (1192.3.79 pandora-build)
- mto: This revision was merged to the branch mainline in revision 1241.
- Revision ID: brian@gaz-20091208220221-lni8fg25a4iwr70k
Big merge.
- files added:
- drizzled/optimizer/quick_index_merge_select.cc
- plugin/show_schema_proto
- plugin/show_schema_proto/tests
- plugin/show_schema_proto/tests/r
- plugin/show_schema_proto/tests/t
- 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