1
/* Copyright 2000-2008 MySQL AB, 2008 Sun Microsystems, Inc.
1
/* Copyright (c) 2000, 2011, Oracle and/or its affiliates. All rights reserved.
3
3
This program is free software; you can redistribute it and/or modify
4
4
it under the terms of the GNU General Public License as published by
446
446
range_key, *range_key_flag);
447
447
*range_key_flag|= key_tree->min_flag;
448
448
if (key_tree->next_key_part &&
449
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE &&
449
450
key_tree->next_key_part->part == key_tree->part+1 &&
450
!(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) &&
451
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
451
!(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)))
452
452
res+= key_tree->next_key_part->store_min_key(key, range_key,
462
462
range_key, *range_key_flag);
463
463
(*range_key_flag)|= key_tree->max_flag;
464
464
if (key_tree->next_key_part &&
465
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE &&
465
466
key_tree->next_key_part->part == key_tree->part+1 &&
466
!(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX)) &&
467
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
467
!(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
468
468
res+= key_tree->next_key_part->store_max_key(key, range_key,
5531
5526
SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func,
5532
5527
field_item, (Item*)(intptr)i, inv);
5534
5530
tree= !tree ? tmp : tree_or(param, tree, tmp);
5536
5535
tree= tree_and(param, tree, tmp);
6736
// tmp.max >= key2.min && tmp.min <= key.max (overlapping ranges)
6738
tmp.min >= key2.min && tmp.min <= key.max (overlapping ranges)
6739
key2.min <= tmp.min <= key2.max
6737
6741
if (eq_tree(tmp->next_key_part,key2->next_key_part))
6739
6743
if (tmp->is_same(key2))
6746
Found exact match of key2 inside key1.
6747
Use the relevant range in key1.
6741
6749
tmp->merge_flags(key2); // Copy maybe flags
6742
6750
key2->increment_use_count(-1); // Free not used tree
6746
6754
SEL_ARG *last=tmp;
6757
Find the last range in tmp that overlaps key2 and has the same
6758
condition on the rest of the keyparts.
6747
6760
while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
6748
6761
eq_tree(last->next->next_key_part,key2->next_key_part))
6764
We've found the last overlapping key1 range in last.
6765
This means that the ranges between (and including) the
6766
first overlapping range (tmp) and the last overlapping range
6767
(last) are fully nested into the current range of key2
6768
and can safely be discarded. We just need the minimum endpoint
6769
of the first overlapping range (tmp) so we can compare it with
6770
the minimum endpoint of the enclosing key2 range.
6750
6772
SEL_ARG *save=last;
6751
6773
last=last->next;
6752
6774
key1=key1->tree_delete(save);
6754
last->copy_min(tmp);
6777
The tmp range (the first overlapping range) could have been discarded
6778
by the previous loop. We should re-direct tmp to the new united range
6779
that's taking its place.
6782
last->copy_min(first);
6755
6783
bool full_range= last->copy_min(key2);
6756
6784
if (!full_range)
7265
Count how many times SEL_ARG graph "root" refers to its part "key"
7293
Count how many times SEL_ARG graph "root" refers to its part "key" via
7268
count_key_part_usage()
7269
root An RB-Root node in a SEL_ARG graph.
7270
key Another RB-Root node in that SEL_ARG graph.
7273
The passed "root" node may refer to "key" node via root->next_key_part,
7276
This function counts how many times the node "key" is referred (via
7277
SEL_ARG::next_key_part) by
7278
- intervals of RB-tree pointed by "root",
7279
- intervals of RB-trees that are pointed by SEL_ARG::next_key_part from
7280
intervals of RB-tree pointed by "root",
7296
@param root An RB-Root node in a SEL_ARG graph.
7297
@param key Another RB-Root node in that SEL_ARG graph.
7299
The passed "root" node may refer to "key" node via root->next_key_part,
7302
This function counts how many times the node "key" is referred (via
7303
SEL_ARG::next_key_part) by
7304
- intervals of RB-tree pointed by "root",
7305
- intervals of RB-trees that are pointed by SEL_ARG::next_key_part from
7306
intervals of RB-tree pointed by "root",
7283
Here is an example (horizontal links represent next_key_part pointers,
7284
vertical links - next/prev prev pointers):
7309
Here is an example (horizontal links represent next_key_part pointers,
7310
vertical links - next/prev prev pointers):
7287
7313
|root|-----------------+
7557
7583
param->first_null_comp= key_tree->part+1;
7559
7585
if (key_tree->next_key_part &&
7560
key_tree->next_key_part->part == key_tree->part+1 &&
7561
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
7586
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE &&
7587
key_tree->next_key_part->part == key_tree->part+1)
7562
7588
{ // const key as prefix
7563
7589
if (min_key_length == max_key_length &&
7564
7590
!memcmp(min_key, max_key, (uint) (tmp_max_key - max_key)) &&
7839
7865
&tmp_max_key,max_key_flag);
7841
7867
if (key_tree->next_key_part &&
7842
key_tree->next_key_part->part == key_tree->part+1 &&
7843
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
7868
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE &&
7869
key_tree->next_key_part->part == key_tree->part+1)
7844
7870
{ // const key as prefix
7845
7871
if ((tmp_min_key - min_key) == (tmp_max_key - max_key) &&
7846
7872
memcmp(min_key, max_key, (uint)(tmp_max_key - max_key))==0 &&
8132
8158
List_iterator_fast<QUICK_RANGE_SELECT> cur_quick_it(quick_selects);
8133
8159
QUICK_RANGE_SELECT* cur_quick;
8136
8161
handler *file= head->file;
8137
8162
DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::read_keys_and_merge");
8139
8164
/* We're going to just read rowids. */
8140
file->extra(HA_EXTRA_KEYREAD);
8165
head->set_keyread(TRUE);
8141
8166
head->prepare_for_position();
8143
8168
cur_quick_it.rewind();
8151
8176
if (cur_quick->init() || cur_quick->reset())
8152
8177
DBUG_RETURN(1);
8154
unique= new Unique(refpos_order_cmp, (void *)file,
8156
thd->variables.sortbuff_size);
8181
DBUG_EXECUTE_IF("index_merge_may_not_create_a_Unique", abort(); );
8182
DBUG_EXECUTE_IF("only_one_Unique_may_be_created",
8183
DBUG_SET("+d,index_merge_may_not_create_a_Unique"); );
8185
unique= new Unique(refpos_order_cmp, (void *)file,
8187
thd->variables.sortbuff_size);
8192
DBUG_ASSERT(file->ref_length == unique->get_size());
8193
DBUG_ASSERT(thd->variables.sortbuff_size == unique->get_max_in_memory_size());
8158
8196
DBUG_RETURN(1);
8212
8240
result= unique->get(head);
8214
8241
doing_pk_scan= FALSE;
8215
8242
/* index_merge currently doesn't support "using index" at all */
8216
file->extra(HA_EXTRA_NO_KEYREAD);
8243
head->set_keyread(FALSE);
8217
8244
init_read_record(&read_record, thd, head, (SQL_SELECT*) 0, 1 , 1, TRUE);
8218
8245
DBUG_RETURN(result);
8423
8451
in_range= FALSE;
8424
8452
cur_range= (QUICK_RANGE**) ranges.buffer;
8426
if (file->inited == handler::NONE && (error= file->ha_index_init(index,1)))
8454
if (file->inited == handler::NONE)
8456
if (in_ror_merged_scan)
8457
head->column_bitmaps_set_no_signal(&column_bitmap, &column_bitmap);
8458
if ((error= file->ha_index_init(index,1)))
8429
8462
/* Do not allocate the buffers twice. */
8430
8463
if (multi_range_length)
8552
8583
mrange_slot < mrange_end;
8555
start_key= &mrange_slot->start_key;
8556
end_key= &mrange_slot->end_key;
8557
8586
last_range= *(cur_range++);
8559
start_key->key= (const uchar*) last_range->min_key;
8560
start_key->length= last_range->min_length;
8561
start_key->flag= ((last_range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
8562
(last_range->flag & EQ_RANGE) ?
8563
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
8564
start_key->keypart_map= last_range->min_keypart_map;
8565
end_key->key= (const uchar*) last_range->max_key;
8566
end_key->length= last_range->max_length;
8568
We use HA_READ_AFTER_KEY here because if we are reading on a key
8569
prefix. We want to find all keys with this prefix.
8571
end_key->flag= (last_range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
8573
end_key->keypart_map= last_range->max_keypart_map;
8587
last_range->make_min_endpoint(&mrange_slot->start_key);
8588
last_range->make_max_endpoint(&mrange_slot->end_key);
8575
8589
mrange_slot->range_flag= last_range->flag;
8596
8610
Get the next record with a different prefix.
8599
QUICK_RANGE_SELECT::get_next_prefix()
8600
prefix_length length of cur_prefix
8601
cur_prefix prefix of a key to be searched for
8604
Each subsequent call to the method retrieves the first record that has a
8605
prefix with length prefix_length different from cur_prefix, such that the
8606
record with the new prefix is within the ranges described by
8607
this->ranges. The record found is stored into the buffer pointed by
8609
The method is useful for GROUP-BY queries with range conditions to
8610
discover the prefix of the next group that satisfies the range conditions.
8612
@param prefix_length length of cur_prefix
8613
@param group_key_parts The number of key parts in the group prefix
8614
@param cur_prefix prefix of a key to be searched for
8616
Each subsequent call to the method retrieves the first record that has a
8617
prefix with length prefix_length and which is different from cur_prefix,
8618
such that the record with the new prefix is within the ranges described by
8619
this->ranges. The record found is stored into the buffer pointed by
8620
this->record. The method is useful for GROUP-BY queries with range
8621
conditions to discover the prefix of the next group that satisfies the range
8613
8626
This method is a modified copy of QUICK_RANGE_SELECT::get_next(), so both
8614
8627
methods should be unified into a more general one to reduce code
8619
HA_ERR_END_OF_FILE if returned all keys
8620
other if some error occurred
8630
@retval 0 on success
8631
@retval HA_ERR_END_OF_FILE if returned all keys
8632
@retval other if some error occurred
8623
8635
int QUICK_RANGE_SELECT::get_next_prefix(uint prefix_length,
8624
key_part_map keypart_map,
8636
uint group_key_parts,
8625
8637
uchar *cur_prefix)
8627
8639
DBUG_ENTER("QUICK_RANGE_SELECT::get_next_prefix");
8640
const key_part_map keypart_map= make_prev_keypart_map(group_key_parts);
8632
key_range start_key, end_key;
8633
8645
if (last_range)
8635
8647
/* Read the next record in the same range with prefix after cur_prefix. */
8636
DBUG_ASSERT(cur_prefix != 0);
8648
DBUG_ASSERT(cur_prefix != NULL);
8637
8649
result= file->index_read_map(record, cur_prefix, keypart_map,
8638
8650
HA_READ_AFTER_KEY);
8639
if (result || (file->compare_key(file->end_range) <= 0))
8651
if (result || last_range->max_keypart_map == 0)
8640
8652
DBUG_RETURN(result);
8654
key_range previous_endpoint;
8655
last_range->make_max_endpoint(&previous_endpoint, prefix_length, keypart_map);
8656
if (file->compare_key(&previous_endpoint) <= 0)
8643
8660
uint count= ranges.elements - (cur_range - (QUICK_RANGE**) ranges.buffer);
8650
8667
last_range= *(cur_range++);
8652
start_key.key= (const uchar*) last_range->min_key;
8653
start_key.length= min(last_range->min_length, prefix_length);
8654
start_key.keypart_map= last_range->min_keypart_map & keypart_map;
8655
start_key.flag= ((last_range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
8656
(last_range->flag & EQ_RANGE) ?
8657
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
8658
end_key.key= (const uchar*) last_range->max_key;
8659
end_key.length= min(last_range->max_length, prefix_length);
8660
end_key.keypart_map= last_range->max_keypart_map & keypart_map;
8662
We use READ_AFTER_KEY here because if we are reading on a key
8663
prefix we want to find all keys with this prefix
8665
end_key.flag= (last_range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
8669
key_range start_key, end_key;
8670
last_range->make_min_endpoint(&start_key, prefix_length, keypart_map);
8671
last_range->make_max_endpoint(&end_key, prefix_length, keypart_map);
8668
8673
result= file->read_range_first(last_range->min_keypart_map ? &start_key : 0,
8669
8674
last_range->max_keypart_map ? &end_key : 0,
8761
This is a hack: we inherit from QUICK_SELECT so that we can use the
8766
This is a hack: we inherit from QUICK_RANGE_SELECT so that we can use the
8762
8767
get_next() interface, but we have to hold a pointer to the original
8763
QUICK_SELECT because its data are used all over the place. What
8768
QUICK_RANGE_SELECT because its data are used all over the place. What
8764
8769
should be done is to factor out the data that is needed into a base
8765
8770
class (QUICK_SELECT), and then have two subclasses (_ASC and _DESC)
8766
8771
which handle the ranges and implement the get_next() function. But
10279
10288
uint use_index, double read_cost_arg,
10280
10289
ha_rows records_arg, uint key_infix_len_arg,
10281
10290
uchar *key_infix_arg, MEM_ROOT *parent_alloc)
10282
:join(join_arg), index_info(index_info_arg),
10291
:file(table->file), join(join_arg), index_info(index_info_arg),
10283
10292
group_prefix_len(group_prefix_len_arg),
10284
10293
group_key_parts(group_key_parts_arg), have_min(have_min_arg),
10285
10294
have_max(have_max_arg), seen_first_key(FALSE),