1288
1285
used_key_parts(0)
1291
optimizer::QuickRangeSelect::QuickRangeSelect(Session *session,
1295
MEM_ROOT *parent_alloc,
1303
my_bitmap_map *bitmap= NULL;
1305
in_ror_merged_scan= 0;
1309
key_part_info= head->key_info[index].key_part;
1310
my_init_dynamic_array(&ranges, sizeof(optimizer::QuickRange*), 16, 16);
1312
/* 'session' is not accessible in QuickRangeSelect::reset(). */
1313
mrr_buf_size= session->variables.read_rnd_buff_size;
1316
if (!no_alloc && !parent_alloc)
1318
// Allocates everything through the internal memroot
1319
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1320
session->mem_root= &alloc;
1323
memset(&alloc, 0, sizeof(alloc));
1324
cursor= head->cursor;
1325
record= head->record[0];
1326
save_read_set= head->read_set;
1327
save_write_set= head->write_set;
1329
/* Allocate a bitmap for used columns. Using sql_alloc instead of malloc
1330
simply as a "fix" to the MySQL 6.0 code that also free()s it at the
1331
same time we destroy the mem_root.
1334
bitmap= reinterpret_cast<my_bitmap_map*>(sql_alloc(head->s->column_bitmap_size));
1337
column_bitmap.setBitmap(NULL);
1342
column_bitmap.init(bitmap, head->s->fields);
1347
int optimizer::QuickRangeSelect::init()
1349
if (cursor->inited != Cursor::NONE)
1350
cursor->ha_index_or_rnd_end();
1351
return (cursor->ha_index_init(index, 1));
1355
void optimizer::QuickRangeSelect::range_end()
1357
if (cursor->inited != Cursor::NONE)
1358
cursor->ha_index_or_rnd_end();
1362
optimizer::QuickRangeSelect::~QuickRangeSelect()
1366
/* cursor is NULL for CPK scan on covering ROR-intersection */
1373
cursor->extra(HA_EXTRA_NO_KEYREAD);
1377
cursor->ha_external_lock(current_session, F_UNLCK);
1382
delete_dynamic(&ranges); /* ranges are allocated in alloc */
1383
free_root(&alloc,MYF(0));
1385
head->column_bitmaps_set(save_read_set, save_write_set);
1386
assert(mrr_buf_desc == NULL);
1394
optimizer::QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(Session *session_param,
1397
pk_quick_select(NULL),
1398
session(session_param)
1402
memset(&read_record, 0, sizeof(read_record));
1403
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1407
int optimizer::QUICK_INDEX_MERGE_SELECT::init()
1412
int optimizer::QUICK_INDEX_MERGE_SELECT::reset()
1414
return (read_keys_and_merge());
1418
optimizer::QUICK_INDEX_MERGE_SELECT::push_quick_back(optimizer::QuickRangeSelect *quick_sel_range)
1421
Save quick_select that does scan on clustered primary key as it will be
1422
processed separately.
1424
if (head->cursor->primary_key_is_clustered() &&
1425
quick_sel_range->index == head->s->primary_key)
1427
pk_quick_select= quick_sel_range;
1431
return quick_selects.push_back(quick_sel_range);
1436
optimizer::QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT()
1438
List_iterator_fast<optimizer::QuickRangeSelect> quick_it(quick_selects);
1439
optimizer::QuickRangeSelect* quick;
1441
while ((quick= quick_it++))
1443
quick->cursor= NULL;
1445
quick_selects.delete_elements();
1446
delete pk_quick_select;
1447
free_root(&alloc,MYF(0));
1452
1290
optimizer::QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(Session *session_param,
1496
Initialize this quick select to be a ROR-merged scan.
1499
QuickRangeSelect::init_ror_merged_scan()
1500
reuse_handler If true, use head->cursor, otherwise create a separate
1504
This function creates and prepares for subsequent use a separate Cursor
1505
object if it can't reuse head->cursor. The reason for this is that during
1506
ROR-merge several key scans are performed simultaneously, and a single
1507
Cursor is only capable of preserving context of a single key scan.
1509
In ROR-merge the quick select doing merge does full records retrieval,
1510
merged quick selects read only keys.
1513
0 ROR child scan initialized, ok to use.
1517
int optimizer::QuickRangeSelect::init_ror_merged_scan(bool reuse_handler)
1519
Cursor *save_file= cursor, *org_file;
1522
in_ror_merged_scan= 1;
1525
if (init() || reset())
1529
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1533
/* Create a separate Cursor object for this quick select */
1536
/* already have own 'Cursor' object. */
1540
session= head->in_use;
1541
if (! (cursor= head->cursor->clone(session->mem_root)))
1544
Manually set the error flag. Note: there seems to be quite a few
1545
places where a failure could cause the server to "hang" the client by
1546
sending no response to a query. ATM those are not real errors because
1547
the storage engine calls in question happen to never fail with the
1548
existing storage engines.
1550
my_error(ER_OUT_OF_RESOURCES, MYF(0));
1551
/* Caller will free the memory */
1555
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1557
if (cursor->ha_external_lock(session, F_RDLCK))
1560
if (init() || reset())
1562
cursor->ha_external_lock(session, F_UNLCK);
1567
last_rowid= cursor->ref;
1571
We are only going to read key fields and call position() on 'cursor'
1572
The following sets head->tmp_set to only use this key and then updates
1573
head->read_set and head->write_set to use this bitmap.
1574
The now bitmap is stored in 'column_bitmap' which is used in ::get_next()
1576
org_file= head->cursor;
1577
head->cursor= cursor;
1578
/* We don't have to set 'head->keyread' here as the 'cursor' is unique */
1579
if (! head->no_keyread)
1582
head->mark_columns_used_by_index(index);
1584
head->prepare_for_position();
1585
head->cursor= org_file;
1586
column_bitmap= *head->read_set;
1587
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1592
head->column_bitmaps_set(save_read_set, save_write_set);
1599
void optimizer::QuickRangeSelect::save_last_pos()
1601
cursor->position(record);
1606
1334
Initialize this quick select to be a part of a ROR-merged scan.
1608
1336
QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan()
7146
Perform key scans for all used indexes (except CPK), get rowids and merge
7147
them into an ordered non-recurrent sequence of rowids.
7149
The merge/duplicate removal is performed using Unique class. We put all
7150
rowids into Unique, get the sorted sequence and destroy the Unique.
7152
If table has a clustered primary key that covers all rows (true for bdb
7153
and innodb currently) and one of the index_merge scans is a scan on PK,
7154
then rows that will be retrieved by PK scan are not put into Unique and
7155
primary key scan is not performed here, it is performed later separately.
7162
int optimizer::QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
7164
List_iterator_fast<optimizer::QuickRangeSelect> cur_quick_it(quick_selects);
7165
optimizer::QuickRangeSelect* cur_quick;
7168
Cursor *cursor= head->cursor;
7170
cursor->extra(HA_EXTRA_KEYREAD);
7171
head->prepare_for_position();
7173
cur_quick_it.rewind();
7174
cur_quick= cur_quick_it++;
7175
assert(cur_quick != 0);
7178
We reuse the same instance of Cursor so we need to call both init and
7181
if (cur_quick->init() || cur_quick->reset())
7184
unique= new Unique(refpos_order_cmp, (void *)cursor,
7186
session->variables.sortbuff_size);
7191
while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE)
7193
cur_quick->range_end();
7194
cur_quick= cur_quick_it++;
7198
if (cur_quick->cursor->inited != Cursor::NONE)
7199
cur_quick->cursor->ha_index_end();
7200
if (cur_quick->init() || cur_quick->reset())
7206
if (result != HA_ERR_END_OF_FILE)
7208
cur_quick->range_end();
7214
if (session->killed)
7217
/* skip row if it will be retrieved by clustered PK scan */
7218
if (pk_quick_select && pk_quick_select->row_in_ranges())
7221
cur_quick->cursor->position(cur_quick->record);
7222
result= unique->unique_add((char*)cur_quick->cursor->ref);
7228
/* ok, all row ids are in Unique */
7229
result= unique->get(head);
7231
doing_pk_scan= false;
7232
/* index_merge currently doesn't support "using index" at all */
7233
cursor->extra(HA_EXTRA_NO_KEYREAD);
7234
/* start table scan */
7235
init_read_record(&read_record, session, head, (optimizer::SqlSelect*) 0, 1, 1);
7241
Get next row for index_merge.
7243
The rows are read from
7244
1. rowids stored in Unique.
7245
2. QuickRangeSelect with clustered primary key (if any).
7246
The sets of rows retrieved in 1) and 2) are guaranteed to be disjoint.
7249
int optimizer::QUICK_INDEX_MERGE_SELECT::get_next()
7254
return(pk_quick_select->get_next());
7256
if ((result= read_record.read_record(&read_record)) == -1)
7258
result= HA_ERR_END_OF_FILE;
7259
end_read_record(&read_record);
7260
/* All rows from Unique have been retrieved, do a clustered PK scan */
7261
if (pk_quick_select)
7263
doing_pk_scan= true;
7264
if ((result= pk_quick_select->init()) ||
7265
(result= pk_quick_select->reset()))
7267
return(pk_quick_select->get_next());
7276
6831
Retrieve next record.
7278
6833
QUICK_ROR_INTERSECT_SELECT::get_next()
7563
Get next possible record using quick-struct.
7566
QuickRangeSelect::get_next()
7569
Record is read into table->record[0]
7573
HA_ERR_END_OF_FILE No (more) rows in range
7576
int optimizer::QuickRangeSelect::get_next()
7579
if (in_ror_merged_scan)
7582
We don't need to signal the bitmap change as the bitmap is always the
7583
same for this head->cursor
7585
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
7588
int result= cursor->multi_range_read_next(&dummy);
7590
if (in_ror_merged_scan)
7592
/* Restore bitmaps set on entry */
7593
head->column_bitmaps_set(save_read_set, save_write_set);
7600
Get the next record with a different prefix.
7603
QuickRangeSelect::get_next_prefix()
7604
prefix_length length of cur_prefix
7605
cur_prefix prefix of a key to be searched for
7608
Each subsequent call to the method retrieves the first record that has a
7609
prefix with length prefix_length different from cur_prefix, such that the
7610
record with the new prefix is within the ranges described by
7611
this->ranges. The record found is stored into the buffer pointed by
7613
The method is useful for GROUP-BY queries with range conditions to
7614
discover the prefix of the next group that satisfies the range conditions.
7617
This method is a modified copy of QuickRangeSelect::get_next(), so both
7618
methods should be unified into a more general one to reduce code
7623
HA_ERR_END_OF_FILE if returned all keys
7624
other if some error occurred
7626
int optimizer::QuickRangeSelect::get_next_prefix(uint32_t prefix_length,
7627
key_part_map keypart_map,
7628
unsigned char *cur_prefix)
7633
key_range start_key, end_key;
7636
/* Read the next record in the same range with prefix after cur_prefix. */
7637
assert(cur_prefix != 0);
7638
result= cursor->index_read_map(record,
7642
if (result || (cursor->compare_key(cursor->end_range) <= 0))
7646
uint32_t count= ranges.elements - (cur_range - (optimizer::QuickRange**) ranges.buffer);
7649
/* Ranges have already been used up before. None is left for read. */
7651
return HA_ERR_END_OF_FILE;
7653
last_range= *(cur_range++);
7655
start_key.key= (const unsigned char*) last_range->min_key;
7656
start_key.length= min(last_range->min_length, (uint16_t)prefix_length);
7657
start_key.keypart_map= last_range->min_keypart_map & keypart_map;
7658
start_key.flag= ((last_range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7659
(last_range->flag & EQ_RANGE) ?
7660
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7661
end_key.key= (const unsigned char*) last_range->max_key;
7662
end_key.length= min(last_range->max_length, (uint16_t)prefix_length);
7663
end_key.keypart_map= last_range->max_keypart_map & keypart_map;
7665
We use READ_AFTER_KEY here because if we are reading on a key
7666
prefix we want to find all keys with this prefix
7668
end_key.flag= (last_range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7671
result= cursor->read_range_first(last_range->min_keypart_map ? &start_key : 0,
7672
last_range->max_keypart_map ? &end_key : 0,
7673
test(last_range->flag & EQ_RANGE),
7675
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7676
last_range= 0; // Stop searching
7678
if (result != HA_ERR_END_OF_FILE)
7680
last_range= 0; // No matching rows; go to next range
7686
Check if current row will be retrieved by this QuickRangeSelect
7689
It is assumed that currently a scan is being done on another index
7690
which reads all necessary parts of the index that is scanned by this
7692
The implementation does a binary search on sorted array of disjoint
7693
ranges, without taking size of range into account.
7695
This function is used to filter out clustered PK scan rows in
7696
index_merge quick select.
7699
true if current row will be retrieved by this quick select
7702
bool optimizer::QuickRangeSelect::row_in_ranges()
7704
optimizer::QuickRange *res= NULL;
7706
uint32_t max= ranges.elements - 1;
7707
uint32_t mid= (max + min) / 2;
7711
if (cmp_next(*(optimizer::QuickRange**)dynamic_array_ptr(&ranges, mid)))
7713
/* current row value > mid->max */
7718
mid= (min + max) / 2;
7720
res= *(optimizer::QuickRange**)dynamic_array_ptr(&ranges, mid);
7721
return (! cmp_next(res) && ! cmp_prev(res));
7725
This is a hack: we inherit from QUICK_SELECT so that we can use the
7726
get_next() interface, but we have to hold a pointer to the original
7727
QUICK_SELECT because its data are used all over the place. What
7728
should be done is to factor out the data that is needed into a base
7729
class (QUICK_SELECT), and then have two subclasses (_ASC and _DESC)
7730
which handle the ranges and implement the get_next() function. But
7731
for now, this seems to work right at least.
7733
optimizer::QUICK_SELECT_DESC::QUICK_SELECT_DESC(optimizer::QuickRangeSelect *q, uint32_t, bool *)
7735
optimizer::QuickRangeSelect(*q),
7738
optimizer::QuickRange *r= NULL;
7740
optimizer::QuickRange **pr= (optimizer::QuickRange**)ranges.buffer;
7741
optimizer::QuickRange **end_range= pr + ranges.elements;
7742
for (; pr != end_range; pr++)
7743
rev_ranges.push_front(*pr);
7745
/* Remove EQ_RANGE flag for keys that are not using the full key */
7746
for (r = rev_it++; r; r= rev_it++)
7748
if ((r->flag & EQ_RANGE) &&
7749
head->key_info[index].key_length != r->max_length)
7750
r->flag&= ~EQ_RANGE;
7753
q->dont_free= 1; // Don't free shared mem
7758
int optimizer::QUICK_SELECT_DESC::get_next()
7760
/* The max key is handled as follows:
7761
* - if there is NO_MAX_RANGE, start at the end and move backwards
7762
* - if it is an EQ_RANGE, which means that max key covers the entire
7763
* key, go directly to the key and read through it (sorting backwards is
7764
* same as sorting forwards)
7765
* - if it is NEAR_MAX, go to the key or next, step back once, and
7767
* - otherwise (not NEAR_MAX == include the key), go after the key,
7768
* step back once, and move backwards
7774
{ // Already read through key
7775
result= ((last_range->flag & EQ_RANGE) ?
7776
cursor->index_next_same(record, last_range->min_key,
7777
last_range->min_length) :
7778
cursor->index_prev(record));
7781
if (cmp_prev(*rev_it.ref()) == 0)
7784
else if (result != HA_ERR_END_OF_FILE)
7788
if (! (last_range= rev_it++))
7789
return HA_ERR_END_OF_FILE; // All ranges used
7791
if (last_range->flag & NO_MAX_RANGE) // Read last record
7794
if ((local_error= cursor->index_last(record)))
7795
return local_error; // Empty table
7796
if (cmp_prev(last_range) == 0)
7798
last_range= 0; // No match; go to next range
7802
if (last_range->flag & EQ_RANGE)
7804
result = cursor->index_read_map(record,
7805
last_range->max_key,
7806
last_range->max_keypart_map,
7811
assert(last_range->flag & NEAR_MAX ||
7812
range_reads_after_key(last_range));
7813
result= cursor->index_read_map(record,
7814
last_range->max_key,
7815
last_range->max_keypart_map,
7816
((last_range->flag & NEAR_MAX) ?
7817
HA_READ_BEFORE_KEY :
7818
HA_READ_PREFIX_LAST_OR_PREV));
7822
if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
7824
last_range= 0; // Not found, to next range
7827
if (cmp_prev(last_range) == 0)
7829
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7830
last_range= 0; // Stop searching
7831
return 0; // Found key is in range
7833
last_range= 0; // To next range
7839
Compare if found key is over max-value
7840
Returns 0 if key <= range->max_key
7841
TODO: Figure out why can't this function be as simple as cmp_prev().
7844
int optimizer::QuickRangeSelect::cmp_next(optimizer::QuickRange *range_arg)
7846
if (range_arg->flag & NO_MAX_RANGE)
7847
return 0; /* key can't be to large */
7849
KEY_PART *key_part= key_parts;
7850
uint32_t store_length;
7852
for (unsigned char *key=range_arg->max_key, *end=key+range_arg->max_length;
7854
key+= store_length, key_part++)
7857
store_length= key_part->store_length;
7858
if (key_part->null_bit)
7862
if (! key_part->field->is_null())
7866
else if (key_part->field->is_null())
7868
key++; // Skip null byte
7871
if ((cmp= key_part->field->key_cmp(key, key_part->length)) < 0)
7876
return (range_arg->flag & NEAR_MAX) ? 1 : 0; // Exact match
7881
Returns 0 if found key is inside range (found key >= range->min_key).
7883
int optimizer::QuickRangeSelect::cmp_prev(optimizer::QuickRange *range_arg)
7886
if (range_arg->flag & NO_MIN_RANGE)
7887
return 0; /* key can't be to small */
7889
cmp= key_cmp(key_part_info,
7891
range_arg->min_length);
7892
if (cmp > 0 || (cmp == 0 && (range_arg->flag & NEAR_MIN) == false))
7894
return 1; // outside of range
7899
* true if this range will require using HA_READ_AFTER_KEY
7900
See comment in get_next() about this
7902
bool optimizer::QUICK_SELECT_DESC::range_reads_after_key(optimizer::QuickRange *range_arg)
7904
return ((range_arg->flag & (NO_MAX_RANGE | NEAR_MAX)) ||
7905
! (range_arg->flag & EQ_RANGE) ||
7906
head->key_info[index].key_length != range_arg->max_length) ? 1 : 0;
7910
void optimizer::QuickRangeSelect::add_info_string(String *str)
7912
KEY *key_info= head->key_info + index;
7913
str->append(key_info->name);
7916
void optimizer::QUICK_INDEX_MERGE_SELECT::add_info_string(String *str)
7918
optimizer::QuickRangeSelect *quick= NULL;
7920
List_iterator_fast<optimizer::QuickRangeSelect> it(quick_selects);
7921
str->append(STRING_WITH_LEN("sort_union("));
7922
while ((quick= it++))
7928
quick->add_info_string(str);
7930
if (pk_quick_select)
7933
pk_quick_select->add_info_string(str);
7939
7054
void optimizer::QUICK_ROR_INTERSECT_SELECT::add_info_string(String *str)
7941
7056
bool first= true;