« back to all changes in this revision
Viewing changes to drizzled/optimizer/range.cc
- browse files at revision 1237.13.5
- compare with another revision
- compare with revision 2466
- 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/range.cc
117
117
#include "drizzled/check_stack_overrun.h"
118
118
#include "drizzled/optimizer/sum.h"
119
119
#include "drizzled/optimizer/range.h"
120
#include "drizzled/optimizer/quick_range.h"
121
#include "drizzled/optimizer/quick_range_select.h"
122
#include "drizzled/optimizer/quick_index_merge_select.h"
120
123
#include "drizzled/records.h"
121
124
122
125
#include "drizzled/temporal.h" /* Needed in get_mm_leaf() for timestamp -> datetime comparisons */
141
144
return static_cast<ha_rows>(x);
142
145
}
143
146
144
extern "C" int refpos_order_cmp(void *arg, const void *a, const void *b)
145
{
146
Cursor *cursor= (Cursor*)arg;
147
return cursor->cmp_ref((const unsigned char *) a, (const unsigned char *) b);
148
}
149
150
147
static int sel_cmp(Field *f, unsigned char *a, unsigned char *b, uint8_t a_flag, uint8_t b_flag);
151
148
152
149
static unsigned char is_null_string[2]= {1,0};
1288
1285
used_key_parts(0)
1289
1286
{}
1290
1287
1291
optimizer::QuickRangeSelect::QuickRangeSelect(Session *session,
1292
Table *table,
1293
uint32_t key_nr,
1294
bool no_alloc,
1295
MEM_ROOT *parent_alloc,
1296
bool *create_error)
1297
:
1298
free_file(0),
1299
cur_range(NULL),
1300
last_range(0),
1301
dont_free(0)
1302
{
1303
my_bitmap_map *bitmap= NULL;
1304
1305
in_ror_merged_scan= 0;
1306
sorted= 0;
1307
index= key_nr;
1308
head= table;
1309
key_part_info= head->key_info[index].key_part;
1310
my_init_dynamic_array(&ranges, sizeof(optimizer::QuickRange*), 16, 16);
1311
1312
/* 'session' is not accessible in QuickRangeSelect::reset(). */
1313
mrr_buf_size= session->variables.read_rnd_buff_size;
1314
mrr_buf_desc= NULL;
1315
1316
if (!no_alloc && !parent_alloc)
1317
{
1318
// Allocates everything through the internal memroot
1319
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1320
session->mem_root= &alloc;
1321
}
1322
else
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;
1328
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.
1332
*/
1333
1334
bitmap= reinterpret_cast<my_bitmap_map*>(sql_alloc(head->s->column_bitmap_size));
1335
if (! bitmap)
1336
{
1337
column_bitmap.setBitmap(NULL);
1338
*create_error= 1;
1339
}
1340
else
1341
{
1342
column_bitmap.init(bitmap, head->s->fields);
1343
}
1344
}
1345
1346
1347
int optimizer::QuickRangeSelect::init()
1348
{
1349
if (cursor->inited != Cursor::NONE)
1350
cursor->ha_index_or_rnd_end();
1351
return (cursor->ha_index_init(index, 1));
1352
}
1353
1354
1355
void optimizer::QuickRangeSelect::range_end()
1356
{
1357
if (cursor->inited != Cursor::NONE)
1358
cursor->ha_index_or_rnd_end();
1359
}
1360
1361
1362
optimizer::QuickRangeSelect::~QuickRangeSelect()
1363
{
1364
if (!dont_free)
1365
{
1366
/* cursor is NULL for CPK scan on covering ROR-intersection */
1367
if (cursor)
1368
{
1369
range_end();
1370
if (head->key_read)
1371
{
1372
head->key_read= 0;
1373
cursor->extra(HA_EXTRA_NO_KEYREAD);
1374
}
1375
if (free_file)
1376
{
1377
cursor->ha_external_lock(current_session, F_UNLCK);
1378
cursor->close();
1379
delete cursor;
1380
}
1381
}
1382
delete_dynamic(&ranges); /* ranges are allocated in alloc */
1383
free_root(&alloc,MYF(0));
1384
}
1385
head->column_bitmaps_set(save_read_set, save_write_set);
1386
assert(mrr_buf_desc == NULL);
1387
if (mrr_buf_desc)
1388
{
1389
free(mrr_buf_desc);
1390
}
1391
}
1392
1393
1394
optimizer::QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(Session *session_param,
1395
Table *table)
1396
:
1397
pk_quick_select(NULL),
1398
session(session_param)
1399
{
1400
index= MAX_KEY;
1401
head= table;
1402
memset(&read_record, 0, sizeof(read_record));
1403
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1404
return;
1405
}
1406
1407
int optimizer::QUICK_INDEX_MERGE_SELECT::init()
1408
{
1409
return 0;
1410
}
1411
1412
int optimizer::QUICK_INDEX_MERGE_SELECT::reset()
1413
{
1414
return (read_keys_and_merge());
1415
}
1416
1417
bool
1418
optimizer::QUICK_INDEX_MERGE_SELECT::push_quick_back(optimizer::QuickRangeSelect *quick_sel_range)
1419
{
1420
/*
1421
Save quick_select that does scan on clustered primary key as it will be
1422
processed separately.
1423
*/
1424
if (head->cursor->primary_key_is_clustered() &&
1425
quick_sel_range->index == head->s->primary_key)
1426
{
1427
pk_quick_select= quick_sel_range;
1428
}
1429
else
1430
{
1431
return quick_selects.push_back(quick_sel_range);
1432
}
1433
return 0;
1434
}
1435
1436
optimizer::QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT()
1437
{
1438
List_iterator_fast<optimizer::QuickRangeSelect> quick_it(quick_selects);
1439
optimizer::QuickRangeSelect* quick;
1440
quick_it.rewind();
1441
while ((quick= quick_it++))
1442
{
1443
quick->cursor= NULL;
1444
}
1445
quick_selects.delete_elements();
1446
delete pk_quick_select;
1447
free_root(&alloc,MYF(0));
1448
return;
1449
}
1450
1288
1451
1289
1452
1290
optimizer::QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(Session *session_param,
1493
1331
1494
1332
1495
1333
/*
1496
Initialize this quick select to be a ROR-merged scan.
1497
1498
SYNOPSIS
1499
QuickRangeSelect::init_ror_merged_scan()
1500
reuse_handler If true, use head->cursor, otherwise create a separate
1501
Cursor object
1502
1503
NOTES
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.
1508
1509
In ROR-merge the quick select doing merge does full records retrieval,
1510
merged quick selects read only keys.
1511
1512
RETURN
1513
0 ROR child scan initialized, ok to use.
1514
1 error
1515
*/
1516
1517
int optimizer::QuickRangeSelect::init_ror_merged_scan(bool reuse_handler)
1518
{
1519
Cursor *save_file= cursor, *org_file;
1520
Session *session;
1521
1522
in_ror_merged_scan= 1;
1523
if (reuse_handler)
1524
{
1525
if (init() || reset())
1526
{
1527
return 0;
1528
}
1529
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1530
goto end;
1531
}
1532
1533
/* Create a separate Cursor object for this quick select */
1534
if (free_file)
1535
{
1536
/* already have own 'Cursor' object. */
1537
return 0;
1538
}
1539
1540
session= head->in_use;
1541
if (! (cursor= head->cursor->clone(session->mem_root)))
1542
{
1543
/*
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.
1549
*/
1550
my_error(ER_OUT_OF_RESOURCES, MYF(0));
1551
/* Caller will free the memory */
1552
goto failure;
1553
}
1554
1555
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1556
1557
if (cursor->ha_external_lock(session, F_RDLCK))
1558
goto failure;
1559
1560
if (init() || reset())
1561
{
1562
cursor->ha_external_lock(session, F_UNLCK);
1563
cursor->close();
1564
goto failure;
1565
}
1566
free_file= true;
1567
last_rowid= cursor->ref;
1568
1569
end:
1570
/*
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()
1575
*/
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)
1580
{
1581
head->key_read= 1;
1582
head->mark_columns_used_by_index(index);
1583
}
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);
1588
1589
return 0;
1590
1591
failure:
1592
head->column_bitmaps_set(save_read_set, save_write_set);
1593
delete cursor;
1594
cursor= save_file;
1595
return 0;
1596
}
1597
1598
1599
void optimizer::QuickRangeSelect::save_last_pos()
1600
{
1601
cursor->position(record);
1602
}
1603
1604
1605
/*
1606
1334
Initialize this quick select to be a part of a ROR-merged scan.
1607
1335
SYNOPSIS
1608
1336
QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan()
1615
1343
int optimizer::QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan(bool reuse_handler)
1616
1344
{
1617
1345
List_iterator_fast<optimizer::QuickRangeSelect> quick_it(quick_selects);
1618
optimizer::QuickRangeSelect* quick;
1346
optimizer::QuickRangeSelect *quick= NULL;
1619
1347
1620
1348
/* Initialize all merged "children" quick selects */
1621
1349
assert(!need_to_fetch_row || reuse_handler);
1666
1394
}
1667
1395
scans_inited= true;
1668
1396
List_iterator_fast<optimizer::QuickRangeSelect> it(quick_selects);
1669
optimizer::QuickRangeSelect *quick;
1397
optimizer::QuickRangeSelect *quick= NULL;
1670
1398
while ((quick= it++))
1671
1399
{
1672
1400
quick->reset();
1853
1581
}
1854
1582
1855
1583
1856
optimizer::QuickRange::QuickRange()
1857
:
1858
min_key(0),
1859
max_key(0),
1860
min_length(0),
1861
max_length(0),
1862
flag(NO_MIN_RANGE | NO_MAX_RANGE),
1863
min_keypart_map(0),
1864
max_keypart_map(0)
1865
{}
1866
1867
1584
SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_alloc()
1868
1585
{
1869
1586
type=arg.type;
2259
1976
2260
1977
2261
1978
/*
2262
Plan for QUICK_INDEX_MERGE_SELECT scan.
1979
Plan for QuickIndexMergeSelect scan.
2263
1980
QUICK_ROR_INTERSECT_SELECT always retrieves full rows, so retrieve_full_rows
2264
1981
is ignored by make_quick.
2265
1982
*/
3892
3609
3893
3610
optimizer::QuickSelectInterface *TRP_INDEX_MERGE::make_quick(PARAM *param, bool, MEM_ROOT *)
3894
3611
{
3895
optimizer::QUICK_INDEX_MERGE_SELECT *quick_imerge;
3896
optimizer::QuickRangeSelect *quick;
3612
optimizer::QuickIndexMergeSelect *quick_imerge;
3613
optimizer::QuickRangeSelect *quick= NULL;
3897
3614
/* index_merge always retrieves full rows, ignore retrieve_full_rows */
3898
if (! (quick_imerge= new optimizer::QUICK_INDEX_MERGE_SELECT(param->session, param->table)))
3615
if (! (quick_imerge= new optimizer::QuickIndexMergeSelect(param->session, param->table)))
3899
3616
{
3900
3617
return NULL;
3901
3618
}
6934
6651
}
6935
6652
6936
6653
/*
6937
Return 1 if there is only one range and this uses the whole primary key
6938
*/
6939
6940
bool optimizer::QuickRangeSelect::unique_key_range()
6941
{
6942
if (ranges.elements == 1)
6943
{
6944
optimizer::QuickRange *tmp= *((optimizer::QuickRange**)ranges.buffer);
6945
if ((tmp->flag & (EQ_RANGE | NULL_RANGE)) == EQ_RANGE)
6946
{
6947
KEY *key=head->key_info+index;
6948
return ((key->flags & (HA_NOSAME)) == HA_NOSAME &&
6949
key->key_length == tmp->min_length);
6950
}
6951
}
6952
return 0;
6953
}
6954
6955
6956
6957
/*
6958
6654
Return true if any part of the key is NULL
6959
6655
6960
6656
SYNOPSIS
6986
6682
return is_key_used(head, index, fields);
6987
6683
}
6988
6684
6989
bool optimizer::QUICK_INDEX_MERGE_SELECT::is_keys_used(const MyBitmap *fields)
6990
{
6991
optimizer::QuickRangeSelect *quick= NULL;
6992
List_iterator_fast<QuickRangeSelect> it(quick_selects);
6993
while ((quick= it++))
6994
{
6995
if (is_key_used(head, quick->index, fields))
6996
return 1;
6997
}
6998
return 0;
6999
}
7000
6685
7001
6686
bool optimizer::QUICK_ROR_INTERSECT_SELECT::is_keys_used(const MyBitmap *fields)
7002
6687
{
7143
6828
7144
6829
7145
6830
/*
7146
Perform key scans for all used indexes (except CPK), get rowids and merge
7147
them into an ordered non-recurrent sequence of rowids.
7148
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.
7151
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.
7156
7157
RETURN
7158
0 OK
7159
other error
7160
*/
7161
7162
int optimizer::QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
7163
{
7164
List_iterator_fast<optimizer::QuickRangeSelect> cur_quick_it(quick_selects);
7165
optimizer::QuickRangeSelect* cur_quick;
7166
int result;
7167
Unique *unique;
7168
Cursor *cursor= head->cursor;
7169
7170
cursor->extra(HA_EXTRA_KEYREAD);
7171
head->prepare_for_position();
7172
7173
cur_quick_it.rewind();
7174
cur_quick= cur_quick_it++;
7175
assert(cur_quick != 0);
7176
7177
/*
7178
We reuse the same instance of Cursor so we need to call both init and
7179
reset here.
7180
*/
7181
if (cur_quick->init() || cur_quick->reset())
7182
return 0;
7183
7184
unique= new Unique(refpos_order_cmp, (void *)cursor,
7185
cursor->ref_length,
7186
session->variables.sortbuff_size);
7187
if (!unique)
7188
return 0;
7189
for (;;)
7190
{
7191
while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE)
7192
{
7193
cur_quick->range_end();
7194
cur_quick= cur_quick_it++;
7195
if (!cur_quick)
7196
break;
7197
7198
if (cur_quick->cursor->inited != Cursor::NONE)
7199
cur_quick->cursor->ha_index_end();
7200
if (cur_quick->init() || cur_quick->reset())
7201
return 0;
7202
}
7203
7204
if (result)
7205
{
7206
if (result != HA_ERR_END_OF_FILE)
7207
{
7208
cur_quick->range_end();
7209
return result;
7210
}
7211
break;
7212
}
7213
7214
if (session->killed)
7215
return 0;
7216
7217
/* skip row if it will be retrieved by clustered PK scan */
7218
if (pk_quick_select && pk_quick_select->row_in_ranges())
7219
continue;
7220
7221
cur_quick->cursor->position(cur_quick->record);
7222
result= unique->unique_add((char*)cur_quick->cursor->ref);
7223
if (result)
7224
return 0;
7225
7226
}
7227
7228
/* ok, all row ids are in Unique */
7229
result= unique->get(head);
7230
delete unique;
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);
7236
return result;
7237
}
7238
7239
7240
/*
7241
Get next row for index_merge.
7242
NOTES
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.
7247
*/
7248
7249
int optimizer::QUICK_INDEX_MERGE_SELECT::get_next()
7250
{
7251
int result;
7252
7253
if (doing_pk_scan)
7254
return(pk_quick_select->get_next());
7255
7256
if ((result= read_record.read_record(&read_record)) == -1)
7257
{
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)
7262
{
7263
doing_pk_scan= true;
7264
if ((result= pk_quick_select->init()) ||
7265
(result= pk_quick_select->reset()))
7266
return result;
7267
return(pk_quick_select->get_next());
7268
}
7269
}
7270
7271
return result;
7272
}
7273
7274
7275
/*
7276
6831
Retrieve next record.
7277
6832
SYNOPSIS
7278
6833
QUICK_ROR_INTERSECT_SELECT::get_next()
7428
6983
}
7429
6984
7430
6985
7431
int optimizer::QuickRangeSelect::reset()
7432
{
7433
uint32_t buf_size= 0;
7434
unsigned char *mrange_buff= NULL;
7435
int error= 0;
7436
HANDLER_BUFFER empty_buf;
7437
last_range= NULL;
7438
cur_range= (optimizer::QuickRange**) ranges.buffer;
7439
7440
if (cursor->inited == Cursor::NONE && (error= cursor->ha_index_init(index, 1)))
7441
{
7442
return error;
7443
}
7444
7445
/* Allocate buffer if we need one but haven't allocated it yet */
7446
if (mrr_buf_size && ! mrr_buf_desc)
7447
{
7448
buf_size= mrr_buf_size;
7449
while (buf_size && ! memory::multi_malloc(false,
7450
&mrr_buf_desc,
7451
sizeof(*mrr_buf_desc),
7452
&mrange_buff,
7453
buf_size,
7454
NULL))
7455
{
7456
/* Try to shrink the buffers until both are 0. */
7457
buf_size/= 2;
7458
}
7459
if (! mrr_buf_desc)
7460
{
7461
return HA_ERR_OUT_OF_MEM;
7462
}
7463
7464
/* Initialize the Cursor buffer. */
7465
mrr_buf_desc->buffer= mrange_buff;
7466
mrr_buf_desc->buffer_end= mrange_buff + buf_size;
7467
mrr_buf_desc->end_of_used_area= mrange_buff;
7468
}
7469
7470
if (! mrr_buf_desc)
7471
{
7472
empty_buf.buffer= NULL;
7473
empty_buf.buffer_end= NULL;
7474
empty_buf.end_of_used_area= NULL;
7475
}
7476
7477
if (sorted)
7478
{
7479
mrr_flags|= HA_MRR_SORTED;
7480
}
7481
RANGE_SEQ_IF seq_funcs= {
7482
optimizer::quick_range_seq_init,
7483
optimizer::quick_range_seq_next
7484
};
7485
error= cursor->multi_range_read_init(&seq_funcs,
7486
(void*) this,
7487
ranges.elements,
7488
mrr_flags,
7489
mrr_buf_desc ? mrr_buf_desc : &empty_buf);
7490
return error;
7491
}
7492
7493
7494
6986
/*
7495
6987
Range sequence interface implementation for array<QuickRange>: initialize
7496
6988
7559
7051
}
7560
7052
7561
7053
7562
/*
7563
Get next possible record using quick-struct.
7564
7565
SYNOPSIS
7566
QuickRangeSelect::get_next()
7567
7568
NOTES
7569
Record is read into table->record[0]
7570
7571
RETURN
7572
0 Found row
7573
HA_ERR_END_OF_FILE No (more) rows in range
7574
# Error code
7575
*/
7576
int optimizer::QuickRangeSelect::get_next()
7577
{
7578
char *dummy= NULL;
7579
if (in_ror_merged_scan)
7580
{
7581
/*
7582
We don't need to signal the bitmap change as the bitmap is always the
7583
same for this head->cursor
7584
*/
7585
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
7586
}
7587
7588
int result= cursor->multi_range_read_next(&dummy);
7589
7590
if (in_ror_merged_scan)
7591
{
7592
/* Restore bitmaps set on entry */
7593
head->column_bitmaps_set(save_read_set, save_write_set);
7594
}
7595
return result;
7596
}
7597
7598
7599
/*
7600
Get the next record with a different prefix.
7601
7602
SYNOPSIS
7603
QuickRangeSelect::get_next_prefix()
7604
prefix_length length of cur_prefix
7605
cur_prefix prefix of a key to be searched for
7606
7607
DESCRIPTION
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
7612
this->record.
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.
7615
7616
TODO
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
7619
duplication.
7620
7621
RETURN
7622
0 on success
7623
HA_ERR_END_OF_FILE if returned all keys
7624
other if some error occurred
7625
*/
7626
int optimizer::QuickRangeSelect::get_next_prefix(uint32_t prefix_length,
7627
key_part_map keypart_map,
7628
unsigned char *cur_prefix)
7629
{
7630
for (;;)
7631
{
7632
int result;
7633
key_range start_key, end_key;
7634
if (last_range)
7635
{
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,
7639
cur_prefix,
7640
keypart_map,
7641
HA_READ_AFTER_KEY);
7642
if (result || (cursor->compare_key(cursor->end_range) <= 0))
7643
return result;
7644
}
7645
7646
uint32_t count= ranges.elements - (cur_range - (optimizer::QuickRange**) ranges.buffer);
7647
if (count == 0)
7648
{
7649
/* Ranges have already been used up before. None is left for read. */
7650
last_range= 0;
7651
return HA_ERR_END_OF_FILE;
7652
}
7653
last_range= *(cur_range++);
7654
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;
7664
/*
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
7667
*/
7668
end_key.flag= (last_range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7669
HA_READ_AFTER_KEY);
7670
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),
7674
sorted);
7675
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7676
last_range= 0; // Stop searching
7677
7678
if (result != HA_ERR_END_OF_FILE)
7679
return result;
7680
last_range= 0; // No matching rows; go to next range
7681
}
7682
}
7683
7684
7685
/*
7686
Check if current row will be retrieved by this QuickRangeSelect
7687
7688
NOTES
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
7691
quick select.
7692
The implementation does a binary search on sorted array of disjoint
7693
ranges, without taking size of range into account.
7694
7695
This function is used to filter out clustered PK scan rows in
7696
index_merge quick select.
7697
7698
RETURN
7699
true if current row will be retrieved by this quick select
7700
false if not
7701
*/
7702
bool optimizer::QuickRangeSelect::row_in_ranges()
7703
{
7704
optimizer::QuickRange *res= NULL;
7705
uint32_t min= 0;
7706
uint32_t max= ranges.elements - 1;
7707
uint32_t mid= (max + min) / 2;
7708
7709
while (min != max)
7710
{
7711
if (cmp_next(*(optimizer::QuickRange**)dynamic_array_ptr(&ranges, mid)))
7712
{
7713
/* current row value > mid->max */
7714
min= mid + 1;
7715
}
7716
else
7717
max= mid;
7718
mid= (min + max) / 2;
7719
}
7720
res= *(optimizer::QuickRange**)dynamic_array_ptr(&ranges, mid);
7721
return (! cmp_next(res) && ! cmp_prev(res));
7722
}
7723
7724
/*
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.
7732
*/
7733
optimizer::QUICK_SELECT_DESC::QUICK_SELECT_DESC(optimizer::QuickRangeSelect *q, uint32_t, bool *)
7734
:
7735
optimizer::QuickRangeSelect(*q),
7736
rev_it(rev_ranges)
7737
{
7738
optimizer::QuickRange *r= NULL;
7739
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);
7744
7745
/* Remove EQ_RANGE flag for keys that are not using the full key */
7746
for (r = rev_it++; r; r= rev_it++)
7747
{
7748
if ((r->flag & EQ_RANGE) &&
7749
head->key_info[index].key_length != r->max_length)
7750
r->flag&= ~EQ_RANGE;
7751
}
7752
rev_it.rewind();
7753
q->dont_free= 1; // Don't free shared mem
7754
delete q;
7755
}
7756
7757
7758
int optimizer::QUICK_SELECT_DESC::get_next()
7759
{
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
7766
* move backwards
7767
* - otherwise (not NEAR_MAX == include the key), go after the key,
7768
* step back once, and move backwards
7769
*/
7770
for (;;)
7771
{
7772
int result;
7773
if (last_range)
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));
7779
if (! result)
7780
{
7781
if (cmp_prev(*rev_it.ref()) == 0)
7782
return 0;
7783
}
7784
else if (result != HA_ERR_END_OF_FILE)
7785
return result;
7786
}
7787
7788
if (! (last_range= rev_it++))
7789
return HA_ERR_END_OF_FILE; // All ranges used
7790
7791
if (last_range->flag & NO_MAX_RANGE) // Read last record
7792
{
7793
int local_error;
7794
if ((local_error= cursor->index_last(record)))
7795
return local_error; // Empty table
7796
if (cmp_prev(last_range) == 0)
7797
return 0;
7798
last_range= 0; // No match; go to next range
7799
continue;
7800
}
7801
7802
if (last_range->flag & EQ_RANGE)
7803
{
7804
result = cursor->index_read_map(record,
7805
last_range->max_key,
7806
last_range->max_keypart_map,
7807
HA_READ_KEY_EXACT);
7808
}
7809
else
7810
{
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));
7819
}
7820
if (result)
7821
{
7822
if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
7823
return result;
7824
last_range= 0; // Not found, to next range
7825
continue;
7826
}
7827
if (cmp_prev(last_range) == 0)
7828
{
7829
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7830
last_range= 0; // Stop searching
7831
return 0; // Found key is in range
7832
}
7833
last_range= 0; // To next range
7834
}
7835
}
7836
7837
7838
/*
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().
7842
*/
7843
7844
int optimizer::QuickRangeSelect::cmp_next(optimizer::QuickRange *range_arg)
7845
{
7846
if (range_arg->flag & NO_MAX_RANGE)
7847
return 0; /* key can't be to large */
7848
7849
KEY_PART *key_part= key_parts;
7850
uint32_t store_length;
7851
7852
for (unsigned char *key=range_arg->max_key, *end=key+range_arg->max_length;
7853
key < end;
7854
key+= store_length, key_part++)
7855
{
7856
int cmp;
7857
store_length= key_part->store_length;
7858
if (key_part->null_bit)
7859
{
7860
if (*key)
7861
{
7862
if (! key_part->field->is_null())
7863
return 1;
7864
continue;
7865
}
7866
else if (key_part->field->is_null())
7867
return 0;
7868
key++; // Skip null byte
7869
store_length--;
7870
}
7871
if ((cmp= key_part->field->key_cmp(key, key_part->length)) < 0)
7872
return 0;
7873
if (cmp > 0)
7874
return 1;
7875
}
7876
return (range_arg->flag & NEAR_MAX) ? 1 : 0; // Exact match
7877
}
7878
7879
7880
/*
7881
Returns 0 if found key is inside range (found key >= range->min_key).
7882
*/
7883
int optimizer::QuickRangeSelect::cmp_prev(optimizer::QuickRange *range_arg)
7884
{
7885
int cmp;
7886
if (range_arg->flag & NO_MIN_RANGE)
7887
return 0; /* key can't be to small */
7888
7889
cmp= key_cmp(key_part_info,
7890
range_arg->min_key,
7891
range_arg->min_length);
7892
if (cmp > 0 || (cmp == 0 && (range_arg->flag & NEAR_MIN) == false))
7893
return 0;
7894
return 1; // outside of range
7895
}
7896
7897
7898
/*
7899
* true if this range will require using HA_READ_AFTER_KEY
7900
See comment in get_next() about this
7901
*/
7902
bool optimizer::QUICK_SELECT_DESC::range_reads_after_key(optimizer::QuickRange *range_arg)
7903
{
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;
7907
}
7908
7909
7910
void optimizer::QuickRangeSelect::add_info_string(String *str)
7911
{
7912
KEY *key_info= head->key_info + index;
7913
str->append(key_info->name);
7914
}
7915
7916
void optimizer::QUICK_INDEX_MERGE_SELECT::add_info_string(String *str)
7917
{
7918
optimizer::QuickRangeSelect *quick= NULL;
7919
bool first= true;
7920
List_iterator_fast<optimizer::QuickRangeSelect> it(quick_selects);
7921
str->append(STRING_WITH_LEN("sort_union("));
7922
while ((quick= it++))
7923
{
7924
if (! first)
7925
str->append(',');
7926
else
7927
first= false;
7928
quick->add_info_string(str);
7929
}
7930
if (pk_quick_select)
7931
{
7932
str->append(',');
7933
pk_quick_select->add_info_string(str);
7934
}
7935
str->append(')');
7936
}
7937
7938
7939
7054
void optimizer::QUICK_ROR_INTERSECT_SELECT::add_info_string(String *str)
7940
7055
{
7941
7056
bool first= true;
7979
7094
}
7980
7095
7981
7096
7982
void optimizer::QuickRangeSelect::add_keys_and_lengths(String *key_names,
7983
String *used_lengths)
7984
{
7985
char buf[64];
7986
uint32_t length;
7987
KEY *key_info= head->key_info + index;
7988
key_names->append(key_info->name);
7989
length= int64_t2str(max_used_key_length, buf, 10) - buf;
7990
used_lengths->append(buf, length);
7991
}
7992
7993
7994
void optimizer::QUICK_INDEX_MERGE_SELECT::add_keys_and_lengths(String *key_names,
7995
String *used_lengths)
7996
{
7997
char buf[64];
7998
uint32_t length;
7999
bool first= true;
8000
optimizer::QuickRangeSelect *quick= NULL;
8001
8002
List_iterator_fast<optimizer::QuickRangeSelect> it(quick_selects);
8003
while ((quick= it++))
8004
{
8005
if (first)
8006
first= false;
8007
else
8008
{
8009
key_names->append(',');
8010
used_lengths->append(',');
8011
}
8012
8013
KEY *key_info= head->key_info + quick->index;
8014
key_names->append(key_info->name);
8015
length= int64_t2str(quick->max_used_key_length, buf, 10) - buf;
8016
used_lengths->append(buf, length);
8017
}
8018
if (pk_quick_select)
8019
{
8020
KEY *key_info= head->key_info + pk_quick_select->index;
8021
key_names->append(',');
8022
key_names->append(key_info->name);
8023
length= int64_t2str(pk_quick_select->max_used_key_length, buf, 10) - buf;
8024
used_lengths->append(',');
8025
used_lengths->append(buf, length);
8026
}
8027
}
8028
8029
8030
7097
void optimizer::QUICK_ROR_INTERSECT_SELECT::add_keys_and_lengths(String *key_names,
8031
7098
String *used_lengths)
8032
7099
{
8776
7843
memset(args, 0, 3 * sizeof(Item*));
8777
7844
bool inv= false;
8778
7845
/* Test if this is a comparison of a field and a constant. */
8779
if (! optimizer::simple_pred(pred, args, &inv))
7846
if (! optimizer::simple_pred(pred, args, inv))
8780
7847
return false;
8781
7848
8782
7849
/* Check for compatible string comparisons - similar to get_mm_leaf. */
Loggerhead is a web-based interface for Breezy
Version: 2.0.1