00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #include <config.h>
00021
00022 #include <drizzled/session.h>
00023 #include <drizzled/optimizer/quick_range.h>
00024 #include <drizzled/optimizer/quick_range_select.h>
00025 #include <drizzled/internal/m_string.h>
00026 #include <drizzled/current_session.h>
00027 #include <drizzled/key.h>
00028 #include <drizzled/table.h>
00029
00030 #include <fcntl.h>
00031
00032 using namespace std;
00033
00034 namespace drizzled
00035 {
00036
00037
00038 optimizer::QuickRangeSelect::QuickRangeSelect(Session *session,
00039 Table *table,
00040 uint32_t key_nr,
00041 bool no_alloc,
00042 memory::Root *parent_alloc)
00043 :
00044 cursor(NULL),
00045 ranges(),
00046 in_ror_merged_scan(false),
00047 column_bitmap(NULL),
00048 save_read_set(NULL),
00049 save_write_set(NULL),
00050 free_file(false),
00051 cur_range(NULL),
00052 last_range(NULL),
00053 qr_traversal_ctx(),
00054 mrr_buf_size(0),
00055 key_parts(NULL),
00056 dont_free(false),
00057 mrr_flags(0),
00058 alloc()
00059 {
00060 sorted= 0;
00061 index= key_nr;
00062 head= table;
00063 key_part_info= head->key_info[index].key_part;
00064 my_init_dynamic_array(&ranges, sizeof(optimizer::QuickRange*), 16, 16);
00065
00066
00067 mrr_buf_size= session->variables.read_rnd_buff_size;
00068
00069 if (! no_alloc && ! parent_alloc)
00070 {
00071
00072 memory::init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
00073 session->mem_root= &alloc;
00074 }
00075 else
00076 {
00077 memset(&alloc, 0, sizeof(alloc));
00078 }
00079
00080 cursor= head->cursor;
00081 record= head->record[0];
00082 save_read_set= head->read_set;
00083 save_write_set= head->write_set;
00084 column_bitmap= new boost::dynamic_bitset<>(table->getShare()->sizeFields());
00085 }
00086
00087
00088 int optimizer::QuickRangeSelect::init()
00089 {
00090 if (cursor->inited != Cursor::NONE)
00091 cursor->ha_index_or_rnd_end();
00092 return (cursor->startIndexScan(index, 1));
00093 }
00094
00095
00096 void optimizer::QuickRangeSelect::range_end()
00097 {
00098 if (cursor->inited != Cursor::NONE)
00099 cursor->ha_index_or_rnd_end();
00100 }
00101
00102
00103 optimizer::QuickRangeSelect::~QuickRangeSelect()
00104 {
00105 if (! dont_free)
00106 {
00107
00108 if (cursor)
00109 {
00110 range_end();
00111 if (head->key_read)
00112 {
00113 head->key_read= 0;
00114 cursor->extra(HA_EXTRA_NO_KEYREAD);
00115 }
00116 if (free_file)
00117 {
00118 cursor->ha_external_lock(current_session, F_UNLCK);
00119 cursor->close();
00120 delete cursor;
00121 }
00122 }
00123 delete_dynamic(&ranges);
00124 delete column_bitmap;
00125 alloc.free_root(MYF(0));
00126 }
00127 head->column_bitmaps_set(*save_read_set, *save_write_set);
00128 }
00129
00130
00131 int optimizer::QuickRangeSelect::init_ror_merged_scan(bool reuse_handler)
00132 {
00133 Cursor *save_file= cursor, *org_file;
00134 Session *session;
00135
00136 in_ror_merged_scan= 1;
00137 if (reuse_handler)
00138 {
00139 if (init() || reset())
00140 {
00141 return 0;
00142 }
00143 head->column_bitmaps_set(*column_bitmap, *column_bitmap);
00144 goto end;
00145 }
00146
00147
00148 if (free_file)
00149 {
00150
00151 return 0;
00152 }
00153
00154 session= head->in_use;
00155 if (! (cursor= head->cursor->clone(session->mem_root)))
00156 {
00157
00158
00159
00160
00161
00162
00163
00164 my_error(ER_OUT_OF_RESOURCES, MYF(0));
00165
00166 goto failure;
00167 }
00168
00169 head->column_bitmaps_set(*column_bitmap, *column_bitmap);
00170
00171 if (cursor->ha_external_lock(session, F_RDLCK))
00172 goto failure;
00173
00174 if (init() || reset())
00175 {
00176 cursor->ha_external_lock(session, F_UNLCK);
00177 cursor->close();
00178 goto failure;
00179 }
00180 free_file= true;
00181 last_rowid= cursor->ref;
00182
00183 end:
00184
00185
00186
00187
00188
00189
00190 org_file= head->cursor;
00191 head->cursor= cursor;
00192
00193 if (! head->no_keyread)
00194 {
00195 head->key_read= 1;
00196 head->mark_columns_used_by_index(index);
00197 }
00198 head->prepare_for_position();
00199 head->cursor= org_file;
00200 *column_bitmap|= *head->read_set;
00201 head->column_bitmaps_set(*column_bitmap, *column_bitmap);
00202
00203 return 0;
00204
00205 failure:
00206 head->column_bitmaps_set(*save_read_set, *save_write_set);
00207 delete cursor;
00208 cursor= save_file;
00209 return 0;
00210 }
00211
00212
00213 void optimizer::QuickRangeSelect::save_last_pos()
00214 {
00215 cursor->position(record);
00216 }
00217
00218
00219 bool optimizer::QuickRangeSelect::unique_key_range() const
00220 {
00221 if (ranges.size() == 1)
00222 {
00223 optimizer::QuickRange *tmp= *((optimizer::QuickRange**)ranges.buffer);
00224 if ((tmp->flag & (EQ_RANGE | NULL_RANGE)) == EQ_RANGE)
00225 {
00226 KeyInfo *key=head->key_info+index;
00227 return ((key->flags & (HA_NOSAME)) == HA_NOSAME &&
00228 key->key_length == tmp->min_length);
00229 }
00230 }
00231 return false;
00232 }
00233
00234
00235 int optimizer::QuickRangeSelect::reset()
00236 {
00237 int error= 0;
00238 last_range= NULL;
00239 cur_range= (optimizer::QuickRange**) ranges.buffer;
00240
00241 if (cursor->inited == Cursor::NONE && (error= cursor->startIndexScan(index, 1)))
00242 {
00243 return error;
00244 }
00245
00246
00247
00248
00249
00250
00251 assert(not (mrr_buf_size));
00252
00253 if (sorted)
00254 {
00255 mrr_flags|= HA_MRR_SORTED;
00256 }
00257 RANGE_SEQ_IF seq_funcs= {
00258 optimizer::quick_range_seq_init,
00259 optimizer::quick_range_seq_next
00260 };
00261 error= cursor->multi_range_read_init(&seq_funcs,
00262 (void*) this,
00263 ranges.size(),
00264 mrr_flags);
00265 return error;
00266 }
00267
00268
00269 int optimizer::QuickRangeSelect::get_next()
00270 {
00271 char *dummy= NULL;
00272 if (in_ror_merged_scan)
00273 {
00274
00275
00276
00277
00278 head->column_bitmaps_set(*column_bitmap, *column_bitmap);
00279 }
00280
00281 int result= cursor->multi_range_read_next(&dummy);
00282
00283 if (in_ror_merged_scan)
00284 {
00285
00286 head->column_bitmaps_set(*save_read_set, *save_write_set);
00287 }
00288 return result;
00289 }
00290
00291
00292 int optimizer::QuickRangeSelect::get_next_prefix(uint32_t prefix_length,
00293 key_part_map keypart_map,
00294 unsigned char *cur_prefix)
00295 {
00296 for (;;)
00297 {
00298 int result;
00299 key_range start_key, end_key;
00300 if (last_range)
00301 {
00302
00303 assert(cur_prefix != 0);
00304 result= cursor->index_read_map(record,
00305 cur_prefix,
00306 keypart_map,
00307 HA_READ_AFTER_KEY);
00308 if (result || (cursor->compare_key(cursor->end_range) <= 0))
00309 return result;
00310 }
00311
00312 uint32_t count= ranges.size() - (cur_range - (optimizer::QuickRange**) ranges.buffer);
00313 if (count == 0)
00314 {
00315
00316 last_range= 0;
00317 return HA_ERR_END_OF_FILE;
00318 }
00319 last_range= *(cur_range++);
00320
00321 start_key.key= (const unsigned char*) last_range->min_key;
00322 start_key.length= min(last_range->min_length, (uint16_t)prefix_length);
00323 start_key.keypart_map= last_range->min_keypart_map & keypart_map;
00324 start_key.flag= ((last_range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
00325 (last_range->flag & EQ_RANGE) ?
00326 HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
00327 end_key.key= (const unsigned char*) last_range->max_key;
00328 end_key.length= min(last_range->max_length, (uint16_t)prefix_length);
00329 end_key.keypart_map= last_range->max_keypart_map & keypart_map;
00330
00331
00332
00333
00334 end_key.flag= (last_range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
00335 HA_READ_AFTER_KEY);
00336
00337 result= cursor->read_range_first(last_range->min_keypart_map ? &start_key : 0,
00338 last_range->max_keypart_map ? &end_key : 0,
00339 test(last_range->flag & EQ_RANGE),
00340 sorted);
00341 if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
00342 last_range= 0;
00343
00344 if (result != HA_ERR_END_OF_FILE)
00345 return result;
00346 last_range= 0;
00347 }
00348 }
00349
00350
00351 bool optimizer::QuickRangeSelect::row_in_ranges()
00352 {
00353 optimizer::QuickRange *res= NULL;
00354 uint32_t min= 0;
00355 uint32_t max= ranges.size() - 1;
00356 uint32_t mid= (max + min) / 2;
00357
00358 while (min != max)
00359 {
00360 if (cmp_next(reinterpret_cast<optimizer::QuickRange**>(ranges.buffer)[mid]))
00361 {
00362
00363 min= mid + 1;
00364 }
00365 else
00366 max= mid;
00367 mid= (min + max) / 2;
00368 }
00369 res= reinterpret_cast<optimizer::QuickRange**>(ranges.buffer)[mid];
00370 return not cmp_next(res) && not cmp_prev(res);
00371 }
00372
00373
00374 int optimizer::QuickRangeSelect::cmp_next(optimizer::QuickRange *range_arg)
00375 {
00376 if (range_arg->flag & NO_MAX_RANGE)
00377 return 0;
00378
00379 KEY_PART *key_part= key_parts;
00380 uint32_t store_length;
00381
00382 for (unsigned char *key=range_arg->max_key, *end=key+range_arg->max_length;
00383 key < end;
00384 key+= store_length, key_part++)
00385 {
00386 int cmp;
00387 store_length= key_part->store_length;
00388 if (key_part->null_bit)
00389 {
00390 if (*key)
00391 {
00392 if (! key_part->field->is_null())
00393 return 1;
00394 continue;
00395 }
00396 else if (key_part->field->is_null())
00397 return 0;
00398 key++;
00399 store_length--;
00400 }
00401 if ((cmp= key_part->field->key_cmp(key, key_part->length)) < 0)
00402 return 0;
00403 if (cmp > 0)
00404 return 1;
00405 }
00406 return (range_arg->flag & NEAR_MAX) ? 1 : 0;
00407 }
00408
00409
00410 int optimizer::QuickRangeSelect::cmp_prev(optimizer::QuickRange *range_arg)
00411 {
00412 if (range_arg->flag & NO_MIN_RANGE)
00413 return 0;
00414
00415 int cmp= key_cmp(key_part_info,
00416 range_arg->min_key,
00417 range_arg->min_length);
00418 if (cmp > 0 || (cmp == 0 && (range_arg->flag & NEAR_MIN) == false))
00419 return 0;
00420 return 1;
00421 }
00422
00423
00424 void optimizer::QuickRangeSelect::add_info_string(string *str)
00425 {
00426 KeyInfo *key_info= head->key_info + index;
00427 str->append(key_info->name);
00428 }
00429
00430
00431 void optimizer::QuickRangeSelect::add_keys_and_lengths(string *key_names,
00432 string *used_lengths)
00433 {
00434 char buf[64];
00435 uint32_t length;
00436 KeyInfo *key_info= head->key_info + index;
00437 key_names->append(key_info->name);
00438 length= internal::int64_t2str(max_used_key_length, buf, 10) - buf;
00439 used_lengths->append(buf, length);
00440 }
00441
00442
00443
00444
00445
00446
00447
00448
00449
00450
00451
00452 optimizer::QuickSelectDescending::QuickSelectDescending(optimizer::QuickRangeSelect *q, uint32_t, bool *)
00453 :
00454 optimizer::QuickRangeSelect(*q)
00455 {
00456 optimizer::QuickRange **pr= (optimizer::QuickRange**) ranges.buffer;
00457 optimizer::QuickRange **end_range= pr + ranges.size();
00458 for (; pr != end_range; pr++)
00459 {
00460 rev_ranges.push_back(*pr);
00461 }
00462 rev_it= rev_ranges.begin();
00463
00464
00465 for (vector<optimizer::QuickRange *>::iterator it= rev_ranges.begin();
00466 it != rev_ranges.end();
00467 ++it)
00468 {
00469 optimizer::QuickRange *r= *it;
00470 if ((r->flag & EQ_RANGE) &&
00471 head->key_info[index].key_length != r->max_length)
00472 {
00473 r->flag&= ~EQ_RANGE;
00474 }
00475 }
00476 q->dont_free= 1;
00477 delete q;
00478 }
00479
00480
00481 int optimizer::QuickSelectDescending::get_next()
00482 {
00483
00484
00485
00486
00487
00488
00489
00490
00491
00492
00493 for (;;)
00494 {
00495 int result;
00496 if (last_range)
00497 {
00498 result= ((last_range->flag & EQ_RANGE) ?
00499 cursor->index_next_same(record, last_range->min_key,
00500 last_range->min_length) :
00501 cursor->index_prev(record));
00502 if (! result)
00503 {
00504 if (cmp_prev(*(rev_it - 1)) == 0)
00505 return 0;
00506 }
00507 else if (result != HA_ERR_END_OF_FILE)
00508 return result;
00509 }
00510
00511 if (rev_it == rev_ranges.end())
00512 {
00513 return HA_ERR_END_OF_FILE;
00514 }
00515 last_range= *rev_it;
00516 ++rev_it;
00517
00518 if (last_range->flag & NO_MAX_RANGE)
00519 {
00520 int local_error;
00521 if ((local_error= cursor->index_last(record)))
00522 return local_error;
00523 if (cmp_prev(last_range) == 0)
00524 return 0;
00525 last_range= 0;
00526 continue;
00527 }
00528
00529 if (last_range->flag & EQ_RANGE)
00530 {
00531 result = cursor->index_read_map(record,
00532 last_range->max_key,
00533 last_range->max_keypart_map,
00534 HA_READ_KEY_EXACT);
00535 }
00536 else
00537 {
00538 assert(last_range->flag & NEAR_MAX ||
00539 range_reads_after_key(last_range));
00540 result= cursor->index_read_map(record,
00541 last_range->max_key,
00542 last_range->max_keypart_map,
00543 ((last_range->flag & NEAR_MAX) ?
00544 HA_READ_BEFORE_KEY :
00545 HA_READ_PREFIX_LAST_OR_PREV));
00546 }
00547 if (result)
00548 {
00549 if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
00550 return result;
00551 last_range= 0;
00552 continue;
00553 }
00554 if (cmp_prev(last_range) == 0)
00555 {
00556 if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
00557 last_range= 0;
00558 return 0;
00559 }
00560 last_range= 0;
00561 }
00562 }
00563
00564
00565
00566
00567
00568
00569 bool optimizer::QuickSelectDescending::range_reads_after_key(optimizer::QuickRange *range_arg)
00570 {
00571 return ((range_arg->flag & (NO_MAX_RANGE | NEAR_MAX)) ||
00572 ! (range_arg->flag & EQ_RANGE) ||
00573 head->key_info[index].key_length != range_arg->max_length) ? 1 : 0;
00574 }
00575
00576
00577 }