~drizzle-trunk/drizzle/development : revision 1208.3.2

23

*/

24

25

/*

26

This file contains:

26

This cursor contains:

27

28

RangeAnalysisModule

29

A module that accepts a condition, index (or partitioning) description,

36

SEL_TREE/SEL_IMERGE/SEL_ARG objects.

37

See quick_range_seq_next, find_used_partitions for examples of how to walk

38

this structure.

39

All direct "users" of this module are located within this file, too.

39

All direct "users" of this module are located within this cursor, too.

40

41

42

PartitionPruningModule

62

63

KeyTupleFormat

64

~~~~~~~~~~~~~~

65

The code in this file (and elsewhere) makes operations on key value tuples.

65

The code in this cursor (and elsewhere) makes operations on key value tuples.

66

Those tuples are stored in the following format:

67

68

The tuple is a sequence of key part values. The length of key part value

136

137

extern "C" int refpos_order_cmp(void* arg, const void *a,const void *b)

138

{

139

Cursor *file= (Cursor*)arg;

140

return file->cmp_ref((const unsigned char*)a, (const unsigned char*)b);

139

Cursor *cursor= (Cursor*)arg;

140

return cursor->cmp_ref((const unsigned char*)a, (const unsigned char*)b);

141

}

142

143

static int sel_cmp(Field *f,unsigned char *a,unsigned char *b,uint8_t a_flag,uint8_t b_flag);

175

actually not a constant, it depends one range of cylinders we're going

176

to access. We make it constant by introducing a fuzzy concept of "typical

177

datafile length" (it's fuzzy as it's hard to tell whether it should

178

include index file, temp.tables etc). Then random seek cost is:

178

include index cursor, temp.tables etc). Then random seek cost is:

179

180

1 = half_rotation_cost + move_cost * 1/3 * typical_data_file_length

181

192

COST_VECT *cost)

193

{

194

cost->zero();

195

if (table->file->primary_key_is_clustered())

195

if (table->cursor->primary_key_is_clustered())

196

{

197

cost->io_count= table->file->read_time(table->s->primary_key,

197

cost->io_count= table->cursor->read_time(table->s->primary_key,

198

(uint32_t) nrows, nrows);

199

}

200

else

201

{

202

double n_blocks=

203

ceil(uint64_t2double(table->file->stats.data_file_length) / IO_SIZE);

203

ceil(uint64_t2double(table->cursor->stats.data_file_length) / IO_SIZE);

204

double busy_blocks=

205

n_blocks * (1.0 - pow(1.0 - 1.0/n_blocks, rows2double(nrows)));

206

if (busy_blocks < 1.0)

721

Possible ways to read rows using index_merge. The list is non-empty only

722

if type==KEY. Currently can be non empty only if keys_map.none().

723

*/

724

vector<SEL_IMERGE*> merges;

724

List<SEL_IMERGE> merges;

725

726

/* The members below are filled/used only after get_mm_tree is done */

727

key_map ror_scans_map; /* bitmask of ROR scan-able elements in keys */

1018

1019

1020

/*

1021

Perform AND operation on two index_merge lists and store result in im1.

1021

Perform AND operation on two index_merge lists and store result in *im1.

1022

*/

1023

1024

inline void imerge_list_and_list(vector<SEL_IMERGE*> &im1, vector<SEL_IMERGE*> &im2)

1024

inline void imerge_list_and_list(List<SEL_IMERGE> *im1, List<SEL_IMERGE> *im2)

1025

{

1026

im1.insert(im1.end(), im2.begin(), im2.end());

1027

im2.clear();

1026

im1->concat(im2);

1028

1027

}

1029

1028

1030

1029

1052

1051

*/

1053

1052

1054

1053

static int imerge_list_or_list(RANGE_OPT_PARAM *param,

1055

vector<SEL_IMERGE*> &im1,

1056

vector<SEL_IMERGE*> &im2)

1054

List<SEL_IMERGE> *im1,

1055

List<SEL_IMERGE> *im2)

1057

1056

{

1058

SEL_IMERGE *imerge= im1.front();

1059

im1.clear();

1060

im1.push_back(imerge);

1057

SEL_IMERGE *imerge= im1->head();

1058

im1->empty();

1059

im1->push_back(imerge);

1061

1060

1062

return imerge->or_sel_imerge_with_checks(param, im2.front());

1061

return imerge->or_sel_imerge_with_checks(param, im2->head());

1063

1062

}

1064

1063

1065

1064

1067

1066

Perform OR operation on index_merge list and key tree.

1068

1067

1069

1068

RETURN

1070

false OK, result is stored in im1.

1071

true Error

1072

*/

1073

1074

static bool imerge_list_or_tree(RANGE_OPT_PARAM *param,

1075

vector<SEL_IMERGE*> &im1,

1076

SEL_TREE *tree)

1069

0 OK, result is stored in *im1.

1070

other Error

1071

*/

1072

1073

static int imerge_list_or_tree(RANGE_OPT_PARAM *param,

1074

List<SEL_IMERGE> *im1,

1075

SEL_TREE *tree)

1077

1076

{

1078

vector<SEL_IMERGE*>::iterator imerge= im1.begin();

1079

1080

while (imerge != im1.end())

1077

SEL_IMERGE *imerge;

1078

List_iterator<SEL_IMERGE> it(*im1);

1079

while ((imerge= it++))

1081

1080

{

1082

if ((*imerge)->or_sel_tree_with_checks(param, tree))

1083

imerge= im1.erase( imerge );

1084

else

1085

++imerge;

1081

if (imerge->or_sel_tree_with_checks(param, tree))

1082

it.remove();

1086

1083

}

1087

1088

return im1.empty();

1084

return im1->is_empty();

1089

1085

}

1090

1086

1091

1087

1124

1120

{

1125

1121

select->file= *head->sort.io_cache;

1126

1122

select->records=(ha_rows) (select->file.end_of_file/

1127

head->file->ref_length);

1123

head->cursor->ref_length);

1128

1124

delete head->sort.io_cache;

1129

1125

head->sort.io_cache=0;

1130

1126

}

1207

1203

}

1208

1204

else

1209

1205

memset(&alloc, 0, sizeof(alloc));

1210

file= head->file;

1206

cursor= head->cursor;

1211

1207

record= head->record[0];

1212

1208

save_read_set= head->read_set;

1213

1209

save_write_set= head->write_set;

1232

1228

1233

1229

int QUICK_RANGE_SELECT::init()

1234

1230

{

1235

if (file->inited != Cursor::NONE)

1236

file->ha_index_or_rnd_end();

1237

return(file->ha_index_init(index, 1));

1231

if (cursor->inited != Cursor::NONE)

1232

cursor->ha_index_or_rnd_end();

1233

return(cursor->ha_index_init(index, 1));

1238

1234

}

1239

1235

1240

1236

1241

1237

void QUICK_RANGE_SELECT::range_end()

1242

1238

{

1243

if (file->inited != Cursor::NONE)

1244

file->ha_index_or_rnd_end();

1239

if (cursor->inited != Cursor::NONE)

1240

cursor->ha_index_or_rnd_end();

1245

1241

}

1246

1242

1247

1243

1249

1245

{

1250

1246

if (!dont_free)

1251

1247

{

1252

/* file is NULL for CPK scan on covering ROR-intersection */

1253

if (file)

1248

/* cursor is NULL for CPK scan on covering ROR-intersection */

1249

if (cursor)

1254

1250

{

1255

1251

range_end();

1256

1252

if (head->key_read)

1257

1253

{

1258

1254

head->key_read= 0;

1259

file->extra(HA_EXTRA_NO_KEYREAD);

1255

cursor->extra(HA_EXTRA_NO_KEYREAD);

1260

1256

}

1261

1257

if (free_file)

1262

1258

{

1263

file->ha_external_lock(current_session, F_UNLCK);

1264

file->close();

1265

delete file;

1259

cursor->ha_external_lock(current_session, F_UNLCK);

1260

cursor->close();

1261

delete cursor;

1266

1262

}

1267

1263

}

1268

1264

delete_dynamic(&ranges); /* ranges are allocated in alloc */

1303

1299

Save quick_select that does scan on clustered primary key as it will be

1304

1300

processed separately.

1305

1301

*/

1306

if (head->file->primary_key_is_clustered() &&

1302

if (head->cursor->primary_key_is_clustered() &&

1307

1303

quick_sel_range->index == head->s->primary_key)

1308

1304

pk_quick_select= quick_sel_range;

1309

1305

else

1317

1313

QUICK_RANGE_SELECT* quick;

1318

1314

quick_it.rewind();

1319

1315

while ((quick= quick_it++))

1320

quick->file= NULL;

1316

quick->cursor= NULL;

1321

1317

quick_selects.delete_elements();

1322

1318

delete pk_quick_select;

1323

1319

free_root(&alloc,MYF(0));

1340

1336

else

1341

1337

memset(&alloc, 0, sizeof(MEM_ROOT));

1342

1338

last_rowid= (unsigned char*) alloc_root(parent_alloc? parent_alloc : &alloc,

1343

head->file->ref_length);

1339

head->cursor->ref_length);

1344

1340

}

1345

1341

1346

1342

1366

1362

1367

1363

SYNOPSIS

1368

1364

QUICK_RANGE_SELECT::init_ror_merged_scan()

1369

reuse_handler If true, use head->file, otherwise create a separate

1365

reuse_handler If true, use head->cursor, otherwise create a separate

1370

1366

Cursor object

1371

1367

1372

1368

NOTES

1373

1369

This function creates and prepares for subsequent use a separate Cursor

1374

object if it can't reuse head->file. The reason for this is that during

1370

object if it can't reuse head->cursor. The reason for this is that during

1375

1371

ROR-merge several key scans are performed simultaneously, and a single

1376

1372

Cursor is only capable of preserving context of a single key scan.

1377

1373

1385

1381

1386

1382

int QUICK_RANGE_SELECT::init_ror_merged_scan(bool reuse_handler)

1387

1383

{

1388

Cursor *save_file= file, *org_file;

1384

Cursor *save_file= cursor, *org_file;

1389

1385

Session *session;

1390

1386

1391

1387

in_ror_merged_scan= 1;

1407

1403

}

1408

1404

1409

1405

session= head->in_use;

1410

if (!(file= head->file->clone(session->mem_root)))

1406

if (!(cursor= head->cursor->clone(session->mem_root)))

1411

1407

{

1412

1408

/*

1413

1409

Manually set the error flag. Note: there seems to be quite a few

1423

1419

1424

1420

head->column_bitmaps_set(&column_bitmap, &column_bitmap);

1425

1421

1426

if (file->ha_external_lock(session, F_RDLCK))

1422

if (cursor->ha_external_lock(session, F_RDLCK))

1427

1423

goto failure;

1428

1424

1429

1425

if (init() || reset())

1430

1426

{

1431

file->ha_external_lock(session, F_UNLCK);

1432

file->close();

1427

cursor->ha_external_lock(session, F_UNLCK);

1428

cursor->close();

1433

1429

goto failure;

1434

1430

}

1435

1431

free_file= true;

1436

last_rowid= file->ref;

1432

last_rowid= cursor->ref;

1437

1433

1438

1434

end:

1439

1435

/*

1440

We are only going to read key fields and call position() on 'file'

1436

We are only going to read key fields and call position() on 'cursor'

1441

1437

The following sets head->tmp_set to only use this key and then updates

1442

1438

head->read_set and head->write_set to use this bitmap.

1443

1439

The now bitmap is stored in 'column_bitmap' which is used in ::get_next()

1444

1440

*/

1445

org_file= head->file;

1446

head->file= file;

1447

/* We don't have to set 'head->keyread' here as the 'file' is unique */

1441

org_file= head->cursor;

1442

head->cursor= cursor;

1443

/* We don't have to set 'head->keyread' here as the 'cursor' is unique */

1448

1444

if (!head->no_keyread)

1449

1445

{

1450

1446

head->key_read= 1;

1451

1447

head->mark_columns_used_by_index(index);

1452

1448

}

1453

1449

head->prepare_for_position();

1454

head->file= org_file;

1450

head->cursor= org_file;

1455

1451

column_bitmap= *head->read_set;

1456

1452

head->column_bitmaps_set(&column_bitmap, &column_bitmap);

1457

1453

1459

1455

1460

1456

failure:

1461

1457

head->column_bitmaps_set(save_read_set, save_write_set);

1462

delete file;

1463

file= save_file;

1458

delete cursor;

1459

cursor= save_file;

1464

1460

return 0;

1465

1461

}

1466

1462

1467

1463

1468

1464

void QUICK_RANGE_SELECT::save_last_pos()

1469

1465

{

1470

file->position(record);

1466

cursor->position(record);

1471

1467

}

1472

1468

1473

1469

1475

1471

Initialize this quick select to be a part of a ROR-merged scan.

1476

1472

SYNOPSIS

1477

1473

QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan()

1478

reuse_handler If true, use head->file, otherwise create separate

1474

reuse_handler If true, use head->cursor, otherwise create separate

1479

1475

Cursor object.

1480

1476

RETURN

1481

1477

0 OK

1492

1488

{

1493

1489

quick= quick_it++;

1494

1490

/*

1495

There is no use of this->file. Use it for the first of merged range

1491

There is no use of this->cursor. Use it for the first of merged range

1496

1492

selects.

1497

1493

*/

1498

1494

if (quick->init_ror_merged_scan(true))

1499

1495

return 0;

1500

quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);

1496

quick->cursor->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);

1501

1497

}

1502

1498

while ((quick= quick_it++))

1503

1499

{

1504

1500

if (quick->init_ror_merged_scan(false))

1505

1501

return 0;

1506

quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);

1502

quick->cursor->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);

1507

1503

/* All merged scans share the same record buffer in intersection. */

1508

1504

quick->record= head->record[0];

1509

1505

}

1510

1506

1511

if (need_to_fetch_row && head->file->ha_rnd_init(1))

1507

if (need_to_fetch_row && head->cursor->ha_rnd_init(1))

1512

1508

{

1513

1509

return 0;

1514

1510

}

1564

1560

quick_selects.delete_elements();

1565

1561

delete cpk_quick;

1566

1562

free_root(&alloc,MYF(0));

1567

if (need_to_fetch_row && head->file->inited != Cursor::NONE)

1568

head->file->ha_rnd_end();

1563

if (need_to_fetch_row && head->cursor->inited != Cursor::NONE)

1564

head->cursor->ha_rnd_end();

1569

1565

return;

1570

1566

}

1571

1567

1576

1572

{

1577

1573

index= MAX_KEY;

1578

1574

head= table;

1579

rowid_length= table->file->ref_length;

1575

rowid_length= table->cursor->ref_length;

1580

1576

record= head->record[0];

1581

1577

init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);

1582

1578

session_param->mem_root= &alloc;

1595

1591

: self(in_arg) { }

1596

1592

inline bool operator()(const QUICK_SELECT_I *i, const QUICK_SELECT_I *j) const

1597

1593

{

1598

int val= self->head->file->cmp_ref(i->last_rowid,

1594

int val= self->head->cursor->cmp_ref(i->last_rowid,

1599

1595

j->last_rowid);

1600

1596

return (val >= 0);

1601

1597

}

1615

1611

{

1616

1612

queue=

1617

1613

new priority_queue<QUICK_SELECT_I *, vector<QUICK_SELECT_I *>, compare_functor >(compare_functor(this));

1618

if (!(cur_rowid= (unsigned char*) alloc_root(&alloc, 2*head->file->ref_length)))

1614

if (!(cur_rowid= (unsigned char*) alloc_root(&alloc, 2*head->cursor->ref_length)))

1619

1615

return 0;

1620

prev_rowid= cur_rowid + head->file->ref_length;

1616

prev_rowid= cur_rowid + head->cursor->ref_length;

1621

1617

return 0;

1622

1618

}

1623

1619

1668

1664

queue->push(quick);

1669

1665

}

1670

1666

1671

if (head->file->ha_rnd_init(1))

1667

if (head->cursor->ha_rnd_init(1))

1672

1668

{

1673

1669

return 0;

1674

1670

}

1689

1685

queue->pop();

1690

1686

delete queue;

1691

1687

quick_selects.delete_elements();

1692

if (head->file->inited != Cursor::NONE)

1693

head->file->ha_rnd_end();

1688

if (head->cursor->inited != Cursor::NONE)

1689

head->cursor->ha_rnd_end();

1694

1690

free_root(&alloc,MYF(0));

1695

1691

return;

1696

1692

}

1925

1921

indexes (records are returned in order for any index prefix) or HASH

1926

1922

indexes (records are not returned in order for any index prefix).

1927

1923

*/

1928

if (!(table->file->index_flags(idx, 0, 1) & HA_READ_ORDER))

1924

if (!(table->cursor->index_flags(idx, 0, 1) & HA_READ_ORDER))

1929

1925

continue;

1930

1926

for (ord= order; ord && partno < n_parts; ord= ord->next, partno++)

1931

1927

{

1954

1950

order. Now we'll check if using the index is cheaper then doing a table

1955

1951

scan.

1956

1952

*/

1957

double full_scan_time= table->file->scan_time();

1958

double index_scan_time= table->file->read_time(match_key, 1, limit);

1953

double full_scan_time= table->cursor->scan_time();

1954

double index_scan_time= table->cursor->read_time(match_key, 1, limit);

1959

1955

if (index_scan_time > full_scan_time)

1960

1956

match_key= MAX_KEY;

1961

1957

}

2187

2183

bitmap_union(&param->needed_fields, table->write_set);

2188

2184

2189

2185

pk= param->table->s->primary_key;

2190

if (pk != MAX_KEY && param->table->file->primary_key_is_clustered())

2186

if (pk != MAX_KEY && param->table->cursor->primary_key_is_clustered())

2191

2187

{

2192

2188

/* The table uses clustered PK and it is not internally generated */

2193

2189

KEY_PART_INFO *key_part= param->table->key_info[pk].key_part;

2279

2275

quick_keys.reset();

2280

2276

if (keys_to_use.none())

2281

2277

return 0;

2282

records= head->file->stats.records;

2278

records= head->cursor->stats.records;

2283

2279

if (!records)

2284

2280

records++;

2285

2281

scan_time= (double) records / TIME_FOR_COMPARE + 1;

2286

read_time= (double) head->file->scan_time() + scan_time + 1.1;

2282

read_time= (double) head->cursor->scan_time() + scan_time + 1.1;

2287

2283

if (head->force_index)

2288

2284

scan_time= read_time= DBL_MAX;

2289

2285

if (limit < records)

2305

2301

2306

2302

/* set up parameter that is passed to all functions */

2307

2303

param.session= session;

2308

param.baseflag= head->file->ha_table_flags();

2304

param.baseflag= head->cursor->ha_table_flags();

2309

2305

param.prev_tables= prev_tables | const_tables;

2310

2306

param.read_tables= read_tables;

2311

2307

param.current_table= head->map;

2369

2365

{

2370

2366

int key_for_use= head->find_shortest_key(&head->covering_keys);

2371

2367

double key_read_time=

2372

param.table->file->index_only_read_time(key_for_use,

2368

param.table->cursor->index_only_read_time(key_for_use,

2373

2369

rows2double(records)) +

2374

2370

(double) records / TIME_FOR_COMPARE;

2375

2371

if (key_read_time < read_time)

2407

2403

if (group_trp)

2408

2404

{

2409

2405

param.table->quick_condition_rows= min(group_trp->records,

2410

head->file->stats.records);

2406

head->cursor->stats.records);

2411

2407

if (group_trp->read_cost < best_read_time)

2412

2408

{

2413

2409

best_trp= group_trp;

2421

2417

It is possible to use a range-based quick select (but it might be

2422

2418

slower than 'all' table scan).

2423

2419

*/

2424

if (tree->merges.empty() == true)

2420

if (tree->merges.is_empty())

2425

2421

{

2426

2422

TRP_RANGE *range_trp;

2427

2423

TRP_ROR_INTERSECT *rori_trp;

2465

2461

else

2466

2462

{

2467

2463

/* Try creating index_merge/ROR-union scan. */

2464

SEL_IMERGE *imerge;

2468

2465

TABLE_READ_PLAN *best_conj_trp= NULL, *new_conj_trp;

2469

vector<SEL_IMERGE*>::iterator imerge= tree->merges.begin();

2470

while (imerge != tree->merges.end())

2466

List_iterator_fast<SEL_IMERGE> it(tree->merges);

2467

while ((imerge= it++))

2471

2468

{

2472

new_conj_trp= get_best_disjunct_quick(&param, *imerge, best_read_time);

2469

new_conj_trp= get_best_disjunct_quick(&param, imerge, best_read_time);

2473

2470

if (new_conj_trp)

2474

2471

set_if_smaller(param.table->quick_condition_rows,

2475

2472

new_conj_trp->records);

2476

2477

2473

if (!best_conj_trp || (new_conj_trp && new_conj_trp->read_cost <

2478

2474

best_conj_trp->read_cost))

2479

2475

best_conj_trp= new_conj_trp;

2480

2481

++imerge;

2482

2476

}

2483

2477

if (best_conj_trp)

2484

2478

best_trp= best_conj_trp;

2538

2532

{cost of ordinary clustered PK scan with n_ranges=n_rows}

2539

2533

2540

2534

Otherwise, we use the following model to calculate costs:

2541

We need to retrieve n_rows rows from file that occupies n_blocks blocks.

2535

We need to retrieve n_rows rows from cursor that occupies n_blocks blocks.

2542

2536

We assume that offsets of rows we need are independent variates with

2543

2537

uniform distribution in [0..max_file_offset] range.

2544

2538

2546

2540

and "empty" if doesn't contain rows we need.

2547

2541

2548

2542

Probability that a block is empty is (1 - 1/n_blocks)^n_rows (this

2549

applies to any block in file). Let x_i be a variate taking value 1 if

2543

applies to any block in cursor). Let x_i be a variate taking value 1 if

2550

2544

block #i is empty and 0 otherwise.

2551

2545

2552

2546

Then E(x_i) = (1 - 1/n_blocks)^n_rows;

2590

2584

double imerge_cost= 0.0;

2591

2585

ha_rows cpk_scan_records= 0;

2592

2586

ha_rows non_cpk_scan_records= 0;

2593

bool pk_is_clustered= param->table->file->primary_key_is_clustered();

2587

bool pk_is_clustered= param->table->cursor->primary_key_is_clustered();

2594

2588

bool all_scans_ror_able= true;

2595

2589

bool all_scans_rors= true;

2596

2590

uint32_t unique_calc_buff_size;

2642

2636

}

2643

2637

2644

2638

if (imerge_too_expensive || (imerge_cost > read_time) ||

2645

((non_cpk_scan_records+cpk_scan_records >= param->table->file->stats.records) && read_time != DBL_MAX))

2639

((non_cpk_scan_records+cpk_scan_records >= param->table->cursor->stats.records) && read_time != DBL_MAX))

2646

2640

{

2647

2641

/*

2648

2642

Bail out if it is obvious that both index_merge and ROR-union will be

2679

2673

/* Add Unique operations cost */

2680

2674

unique_calc_buff_size=

2681

2675

Unique::get_cost_calc_buff_size((ulong)non_cpk_scan_records,

2682

param->table->file->ref_length,

2676

param->table->cursor->ref_length,

2683

2677

param->session->variables.sortbuff_size);

2684

2678

if (param->imerge_cost_buff_size < unique_calc_buff_size)

2685

2679

{

2691

2685

2692

2686

imerge_cost +=

2693

2687

Unique::get_use_cost(param->imerge_cost_buff, (uint32_t)non_cpk_scan_records,

2694

param->table->file->ref_length,

2688

param->table->cursor->ref_length,

2695

2689

param->session->variables.sortbuff_size);

2696

2690

if (imerge_cost < read_time)

2697

2691

{

2700

2694

imerge_trp->read_cost= imerge_cost;

2701

2695

imerge_trp->records= non_cpk_scan_records + cpk_scan_records;

2702

2696

imerge_trp->records= min(imerge_trp->records,

2703

param->table->file->stats.records);

2697

param->table->cursor->stats.records);

2704

2698

imerge_trp->range_scans= range_scans;

2705

2699

imerge_trp->range_scans_end= range_scans + n_child_scans;

2706

2700

read_time= imerge_cost;

2738

2732

if ((*cur_child)->is_ror)

2739

2733

{

2740

2734

/* Ok, we have index_only cost, now get full rows scan cost */

2741

cost= param->table->file->

2735

cost= param->table->cursor->

2742

2736

read_time(param->real_keynr[(*cur_child)->key_idx], 1,

2743

2737

(*cur_child)->records) +

2744

2738

rows2double((*cur_child)->records) / TIME_FOR_COMPARE;

2761

2755

((TRP_ROR_INTERSECT*)(*cur_roru_plan))->index_scan_costs;

2762

2756

roru_total_records += (*cur_roru_plan)->records;

2763

2757

roru_intersect_part *= (*cur_roru_plan)->records /

2764

param->table->file->stats.records;

2758

param->table->cursor->stats.records;

2765

2759

}

2766

2760

2767

2761

/*

2771

2765

in disjunction do not share key parts.

2772

2766

*/

2773

2767

roru_total_records -= (ha_rows)(roru_intersect_part*

2774

param->table->file->stats.records);

2768

param->table->cursor->stats.records);

2775

2769

/* ok, got a ROR read plan for each of the disjuncts

2776

2770

Calculate cost:

2777

2771

cost(index_union_scan(scan_1, ... scan_n)) =

2863

2857

ror_scan->idx= idx;

2864

2858

ror_scan->keynr= keynr= param->real_keynr[idx];

2865

2859

ror_scan->key_rec_length= (param->table->key_info[keynr].key_length +

2866

param->table->file->ref_length);

2860

param->table->cursor->ref_length);

2867

2861

ror_scan->sel_arg= sel_arg;

2868

2862

ror_scan->records= param->table->quick_rows[keynr];

2869

2863

2886

2880

}

2887

2881

double rows= rows2double(param->table->quick_rows[ror_scan->keynr]);

2888

2882

ror_scan->index_read_cost=

2889

param->table->file->index_only_read_time(ror_scan->keynr, rows);

2883

param->table->cursor->index_only_read_time(ror_scan->keynr, rows);

2890

2884

return(ror_scan);

2891

2885

}

2892

2886

2995

2989

info->is_covering= false;

2996

2990

info->index_scan_costs= 0.0;

2997

2991

info->index_records= 0;

2998

info->out_rows= (double) param->table->file->stats.records;

2992

info->out_rows= (double) param->table->cursor->stats.records;

2999

2993

info->covered_fields.clearAll();

3000

2994

return info;

3001

2995

}

3120

3114

min_range.flag= HA_READ_KEY_EXACT;

3121

3115

max_range.key= key_val;

3122

3116

max_range.flag= HA_READ_AFTER_KEY;

3123

ha_rows prev_records= info->param->table->file->stats.records;

3117

ha_rows prev_records= info->param->table->cursor->stats.records;

3124

3118

3125

3119

for (sel_arg= scan->sel_arg; sel_arg;

3126

3120

sel_arg= sel_arg->next_key_part)

3147

3141

}

3148

3142

min_range.length= max_range.length= (size_t) (key_ptr - key_val);

3149

3143

min_range.keypart_map= max_range.keypart_map= keypart_map;

3150

records= (info->param->table->file->

3144

records= (info->param->table->cursor->

3151

3145

records_in_range(scan->keynr, &min_range, &max_range));

3152

3146

if (cur_covered)

3153

3147

{

3332

3326

uint32_t idx;

3333

3327

double min_cost= DBL_MAX;

3334

3328

3335

if ((tree->n_ror_scans < 2) || !param->table->file->stats.records)

3329

if ((tree->n_ror_scans < 2) || !param->table->cursor->stats.records)

3336

3330

return NULL;

3337

3331

3338

3332

/*

3348

3342

sizeof(ROR_SCAN_INFO*)*

3349

3343

param->keys)))

3350

3344

return NULL;

3351

cpk_no= ((param->table->file->primary_key_is_clustered()) ?

3345

cpk_no= ((param->table->cursor->primary_key_is_clustered()) ?

3352

3346

param->table->s->primary_key : MAX_KEY);

3353

3347

3354

3348

for (idx= 0, cur_ror_scan= tree->ror_scans; idx < param->keys; idx++)

3785

3779

delete quick_intrsect;

3786

3780

return NULL;

3787

3781

}

3788

quick->file= NULL;

3782

quick->cursor= NULL;

3789

3783

quick_intrsect->cpk_quick= quick;

3790

3784

}

3791

3785

quick_intrsect->records= records;

4949

4943

/* dispose index_merge if there is a "range" option */

4950

4944

if (result_keys.any())

4951

4945

{

4952

tree1->merges.clear();

4946

tree1->merges.empty();

4953

4947

return(tree1);

4954

4948

}

4955

4949

4956

4950

/* ok, both trees are index_merge trees */

4957

imerge_list_and_list(tree1->merges, tree2->merges);

4951

imerge_list_and_list(&tree1->merges, &tree2->merges);

4958

4952

return(tree1);

4959

4953

}

4960

4954

5108

5102

else

5109

5103

{

5110

5104

/* ok, two trees have KEY type but cannot be used without index merge */

5111

if ((tree1->merges.empty() == true) && (tree2->merges.empty() == true))

5105

if (tree1->merges.is_empty() && tree2->merges.is_empty())

5112

5106

{

5113

5107

if (param->remove_jump_scans)

5114

5108

{

5117

5111

if (no_trees)

5118

5112

return(new SEL_TREE(SEL_TREE::ALWAYS));

5119

5113

}

5120

5121

/* both trees are "range" trees, produce new index merge structure. */

5122

result= new SEL_TREE();

5123

SEL_IMERGE *merge= new SEL_IMERGE();

5124

result->merges.push_back(merge);

5125

5126

if( merge->or_sel_tree(param, tree1) || merge->or_sel_tree(param, tree2))

5114

SEL_IMERGE *merge;

5115

/* both trees are "range" trees, produce new index merge structure */

5116

if (!(result= new SEL_TREE()) || !(merge= new SEL_IMERGE()) ||

5117

(result->merges.push_back(merge)) ||

5118

(merge->or_sel_tree(param, tree1)) ||

5119

(merge->or_sel_tree(param, tree2)))

5127

5120

result= NULL;

5128

5121

else

5129

5122

result->type= tree1->type;

5130

5123

}

5131

else if ((tree1->merges.empty() == false) && (tree2->merges.empty() == false))

5124

else if (!tree1->merges.is_empty() && !tree2->merges.is_empty())

5132

5125

{

5133

if (imerge_list_or_list(param, tree1->merges, tree2->merges))

5126

if (imerge_list_or_list(param, &tree1->merges, &tree2->merges))

5134

5127

result= new SEL_TREE(SEL_TREE::ALWAYS);

5135

5128

else

5136

5129

result= tree1;

5138

5131

else

5139

5132

{

5140

5133

/* one tree is index merge tree and another is range tree */

5141

if (tree1->merges.empty() == true)

5134

if (tree1->merges.is_empty())

5142

5135

std::swap(tree1, tree2);

5143

5136

5144

5137

if (param->remove_jump_scans && remove_nonrange_trees(param, tree2))

5145

5138

return(new SEL_TREE(SEL_TREE::ALWAYS));

5146

5147

5139

/* add tree2 to tree1->merges, checking if it collapses to ALWAYS */

5148

if (imerge_list_or_tree(param, tree1->merges, tree2))

5140

if (imerge_list_or_tree(param, &tree1->merges, tree2))

5149

5141

result= new SEL_TREE(SEL_TREE::ALWAYS);

5150

5142

else

5151

5143

result= tree1;

6398

6390

{

6399

6391

SEL_ARG_RANGE_SEQ seq;

6400

6392

RANGE_SEQ_IF seq_if = {sel_arg_range_seq_init, sel_arg_range_seq_next};

6401

Cursor *file= param->table->file;

6393

Cursor *cursor= param->table->cursor;

6402

6394

ha_rows rows;

6403

6395

uint32_t keynr= param->real_keynr[idx];

6404

6396

6419

6411

param->max_key_part=0;

6420

6412

6421

6413

param->is_ror_scan= true;

6422

if (file->index_flags(keynr, 0, true) & HA_KEY_SCAN_NOT_ROR)

6414

if (cursor->index_flags(keynr, 0, true) & HA_KEY_SCAN_NOT_ROR)

6423

6415

param->is_ror_scan= false;

6424

6416

6425

6417

*mrr_flags= param->force_default_mrr? HA_MRR_USE_DEFAULT_IMPL: 0;

6426

6418

*mrr_flags|= HA_MRR_NO_ASSOCIATION;

6427

6419

6428

bool pk_is_clustered= file->primary_key_is_clustered();

6420

bool pk_is_clustered= cursor->primary_key_is_clustered();

6429

6421

if (index_only &&

6430

(file->index_flags(keynr, param->max_key_part, 1) & HA_KEYREAD_ONLY) &&

6422

(cursor->index_flags(keynr, param->max_key_part, 1) & HA_KEYREAD_ONLY) &&

6431

6423

!(pk_is_clustered && keynr == param->table->s->primary_key))

6432

6424

*mrr_flags |= HA_MRR_INDEX_ONLY;

6433

6425

6435

6427

*mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;

6436

6428

6437

6429

*bufsize= param->session->variables.read_rnd_buff_size;

6438

rows= file->multi_range_read_info_const(keynr, &seq_if, (void*)&seq, 0,

6430

rows= cursor->multi_range_read_info_const(keynr, &seq_if, (void*)&seq, 0,

6439

6431

bufsize, mrr_flags, cost);

6440

6432

if (rows != HA_POS_ERROR)

6441

6433

{

6529

6521

6530

6522

key_part= table_key->key_part + nparts;

6531

6523

pk_number= param->table->s->primary_key;

6532

if (!param->table->file->primary_key_is_clustered() || pk_number == MAX_KEY)

6524

if (!param->table->cursor->primary_key_is_clustered() || pk_number == MAX_KEY)

6533

6525

return false;

6534

6526

6535

6527

KEY_PART_INFO *pk_part= param->table->key_info[pk_number].key_part;

6914

6906

quick->mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;

6915

6907

6916

6908

quick->mrr_buf_size= session->variables.read_rnd_buff_size;

6917

if (table->file->multi_range_read_info(quick->index, 1, (uint32_t)records,

6909

if (table->cursor->multi_range_read_info(quick->index, 1, (uint32_t)records,

6918

6910

&quick->mrr_buf_size,

6919

6911

&quick->mrr_flags, &cost))

6920

6912

goto err;

6949

6941

QUICK_RANGE_SELECT* cur_quick;

6950

6942

int result;

6951

6943

Unique *unique;

6952

Cursor *file= head->file;

6944

Cursor *cursor= head->cursor;

6953

6945

6954

file->extra(HA_EXTRA_KEYREAD);

6946

cursor->extra(HA_EXTRA_KEYREAD);

6955

6947

head->prepare_for_position();

6956

6948

6957

6949

cur_quick_it.rewind();

6965

6957

if (cur_quick->init() || cur_quick->reset())

6966

6958

return 0;

6967

6959

6968

unique= new Unique(refpos_order_cmp, (void *)file,

6969

file->ref_length,

6960

unique= new Unique(refpos_order_cmp, (void *)cursor,

6961

cursor->ref_length,

6970

6962

session->variables.sortbuff_size);

6971

6963

if (!unique)

6972

6964

return 0;

6979

6971

if (!cur_quick)

6980

6972

break;

6981

6973

6982

if (cur_quick->file->inited != Cursor::NONE)

6983

cur_quick->file->ha_index_end();

6974

if (cur_quick->cursor->inited != Cursor::NONE)

6975

cur_quick->cursor->ha_index_end();

6984

6976

if (cur_quick->init() || cur_quick->reset())

6985

6977

return 0;

6986

6978

}

7002

6994

if (pk_quick_select && pk_quick_select->row_in_ranges())

7003

6995

continue;

7004

6996

7005

cur_quick->file->position(cur_quick->record);

7006

result= unique->unique_add((char*)cur_quick->file->ref);

6997

cur_quick->cursor->position(cur_quick->record);

6998

result= unique->unique_add((char*)cur_quick->cursor->ref);

7007

6999

if (result)

7008

7000

return 0;

7009

7001

7014

7006

delete unique;

7015

7007

doing_pk_scan= false;

7016

7008

/* index_merge currently doesn't support "using index" at all */

7017

file->extra(HA_EXTRA_NO_KEYREAD);

7009

cursor->extra(HA_EXTRA_NO_KEYREAD);

7018

7010

/* start table scan */

7019

7011

init_read_record(&read_record, session, head, (SQL_SELECT*) 0, 1, 1);

7020

7012

return result;

7096

7088

if (error)

7097

7089

return(error);

7098

7090

7099

quick->file->position(quick->record);

7100

memcpy(last_rowid, quick->file->ref, head->file->ref_length);

7091

quick->cursor->position(quick->record);

7092

memcpy(last_rowid, quick->cursor->ref, head->cursor->ref_length);

7101

7093

last_rowid_count= 1;

7102

7094

7103

7095

while (last_rowid_count < quick_selects.elements)

7112

7104

{

7113

7105

if ((error= quick->get_next()))

7114

7106

return(error);

7115

quick->file->position(quick->record);

7116

cmp= head->file->cmp_ref(quick->file->ref, last_rowid);

7107

quick->cursor->position(quick->record);

7108

cmp= head->cursor->cmp_ref(quick->cursor->ref, last_rowid);

7117

7109

} while (cmp < 0);

7118

7110

7119

7111

/* Ok, current select 'caught up' and returned ref >= cur_ref */

7128

7120

return(error);

7129

7121

}

7130

7122

}

7131

memcpy(last_rowid, quick->file->ref, head->file->ref_length);

7123

memcpy(last_rowid, quick->cursor->ref, head->cursor->ref_length);

7132

7124

last_rowid_count= 1;

7133

7125

}

7134

7126

else

7140

7132

7141

7133

/* We get here if we got the same row ref in all scans. */

7142

7134

if (need_to_fetch_row)

7143

error= head->file->rnd_pos(head->record[0], last_rowid);

7135

error= head->cursor->rnd_pos(head->record[0], last_rowid);

7144

7136

} while (error == HA_ERR_RECORD_DELETED);

7145

7137

return(error);

7146

7138

}

7199

7191

have_prev_rowid= true;

7200

7192

}

7201

7193

else

7202

dup_row= !head->file->cmp_ref(cur_rowid, prev_rowid);

7194

dup_row= !head->cursor->cmp_ref(cur_rowid, prev_rowid);

7203

7195

} while (dup_row);

7204

7196

7205

7197

tmp= cur_rowid;

7206

7198

cur_rowid= prev_rowid;

7207

7199

prev_rowid= tmp;

7208

7200

7209

error= head->file->rnd_pos(quick->record, prev_rowid);

7201

error= head->cursor->rnd_pos(quick->record, prev_rowid);

7210

7202

} while (error == HA_ERR_RECORD_DELETED);

7211

7203

return(error);

7212

7204

}

7221

7213

last_range= NULL;

7222

7214

cur_range= (QUICK_RANGE**) ranges.buffer;

7223

7215

7224

if (file->inited == Cursor::NONE && (error= file->ha_index_init(index,1)))

7216

if (cursor->inited == Cursor::NONE && (error= cursor->ha_index_init(index,1)))

7225

7217

return(error);

7226

7218

7227

7219

/* Allocate buffer if we need one but haven't allocated it yet */

7251

7243

if (sorted)

7252

7244

mrr_flags |= HA_MRR_SORTED;

7253

7245

RANGE_SEQ_IF seq_funcs= {quick_range_seq_init, quick_range_seq_next};

7254

error= file->multi_range_read_init(&seq_funcs, (void*)this, ranges.elements,

7246

error= cursor->multi_range_read_init(&seq_funcs, (void*)this, ranges.elements,

7255

7247

mrr_flags, mrr_buf_desc? mrr_buf_desc:

7256

7248

&empty_buf);

7257

7249

return(error);

7349

7341

{

7350

7342

/*

7351

7343

We don't need to signal the bitmap change as the bitmap is always the

7352

same for this head->file

7344

same for this head->cursor

7353

7345

*/

7354

7346

head->column_bitmaps_set(&column_bitmap, &column_bitmap);

7355

7347

}

7356

7348

7357

int result= file->multi_range_read_next(&dummy);

7349

int result= cursor->multi_range_read_next(&dummy);

7358

7350

7359

7351

if (in_ror_merged_scan)

7360

7352

{

7405

7397

{

7406

7398

/* Read the next record in the same range with prefix after cur_prefix. */

7407

7399

assert(cur_prefix != 0);

7408

result= file->index_read_map(record, cur_prefix, keypart_map,

7400

result= cursor->index_read_map(record, cur_prefix, keypart_map,

7409

7401

HA_READ_AFTER_KEY);

7410

if (result || (file->compare_key(file->end_range) <= 0))

7402

if (result || (cursor->compare_key(cursor->end_range) <= 0))

7411

7403

return result;

7412

7404

}

7413

7405

7436

7428

end_key.flag= (last_range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :

7437

7429

HA_READ_AFTER_KEY);

7438

7430

7439

result= file->read_range_first(last_range->min_keypart_map ? &start_key : 0,

7431

result= cursor->read_range_first(last_range->min_keypart_map ? &start_key : 0,

7440

7432

last_range->max_keypart_map ? &end_key : 0,

7441

7433

test(last_range->flag & EQ_RANGE),

7442

7434

sorted);

7542

7534

if (last_range)

7543

7535

{ // Already read through key

7544

7536

result = ((last_range->flag & EQ_RANGE)

7545

? file->index_next_same(record, last_range->min_key,

7537

? cursor->index_next_same(record, last_range->min_key,

7546

7538

last_range->min_length) :

7547

file->index_prev(record));

7539

cursor->index_prev(record));

7548

7540

if (!result)

7549

7541

{

7550

7542

if (cmp_prev(*rev_it.ref()) == 0)

7560

7552

if (last_range->flag & NO_MAX_RANGE) // Read last record

7561

7553

{

7562

7554

int local_error;

7563

if ((local_error=file->index_last(record)))

7555

if ((local_error=cursor->index_last(record)))

7564

7556

return(local_error); // Empty table

7565

7557

if (cmp_prev(last_range) == 0)

7566

7558

return 0;

7570

7562

7571

7563

if (last_range->flag & EQ_RANGE)

7572

7564

{

7573

result = file->index_read_map(record, last_range->max_key,

7565

result = cursor->index_read_map(record, last_range->max_key,

7574

7566

last_range->max_keypart_map,

7575

7567

HA_READ_KEY_EXACT);

7576

7568

}

7578

7570

{

7579

7571

assert(last_range->flag & NEAR_MAX ||

7580

7572

range_reads_after_key(last_range));

7581

result=file->index_read_map(record, last_range->max_key,

7573

result=cursor->index_read_map(record, last_range->max_key,

7582

7574

last_range->max_keypart_map,

7583

7575

((last_range->flag & NEAR_MAX) ?

7584

7576

HA_READ_BEFORE_KEY :

8130

8122

we check that all query fields are indeed covered by 'cur_index'.

8131

8123

*/

8132

8124

if (pk < MAX_KEY && cur_index != pk &&

8133

(table->file->ha_table_flags() & HA_PRIMARY_KEY_IN_READ_INDEX))

8125

(table->cursor->ha_table_flags() & HA_PRIMARY_KEY_IN_READ_INDEX))

8134

8126

{

8135

8127

/* For each table field */

8136

8128

for (uint32_t i= 0; i < table->s->fields; i++)

8773

8765

double io_cost;

8774

8766

double cpu_cost= 0; /* TODO: CPU cost of index_read calls? */

8775

8767

8776

table_records= table->file->stats.records;

8777

keys_per_block= (table->file->stats.block_size / 2 /

8778

(index_info->key_length + table->file->ref_length)

8768

table_records= table->cursor->stats.records;

8769

keys_per_block= (table->cursor->stats.block_size / 2 /

8770

(index_info->key_length + table->cursor->ref_length)

8779

8771

+ 1);

8780

8772

num_blocks= (uint32_t)(table_records / keys_per_block) + 1;

8781

8773

8965

8957

max_functions_it(NULL)

8966

8958

{

8967

8959

head= table;

8968

file= head->file;

8960

cursor= head->cursor;

8969

8961

index= use_index;

8970

8962

record= head->record[0];

8971

8963

tmp_record= head->record[1];

9088

9080

9089

9081

QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT()

9090

9082

{

9091

if (file->inited != Cursor::NONE)

9092

file->ha_index_end();

9083

if (cursor->inited != Cursor::NONE)

9084

cursor->ha_index_end();

9093

9085

if (min_max_arg_part)

9094

9086

delete_dynamic(&min_max_ranges);

9095

9087

free_root(&alloc,MYF(0));

9270

9262

{

9271

9263

int result;

9272

9264

9273

file->extra(HA_EXTRA_KEYREAD); /* We need only the key attributes */

9274

if ((result= file->ha_index_init(index,1)))

9265

cursor->extra(HA_EXTRA_KEYREAD); /* We need only the key attributes */

9266

if ((result= cursor->ha_index_init(index,1)))

9275

9267

return result;

9276

9268

if (quick_prefix_select && quick_prefix_select->reset())

9277

9269

return 0;

9278

result= file->index_last(record);

9270

result= cursor->index_last(record);

9279

9271

if (result == HA_ERR_END_OF_FILE)

9280

9272

return 0;

9281

9273

/* Save the prefix of the last group. */

9367

9359

first sub-group with the extended prefix.

9368

9360

*/

9369

9361

if (!have_min && !have_max && key_infix_len > 0)

9370

result= file->index_read_map(record, group_prefix,

9362

result= cursor->index_read_map(record, group_prefix,

9371

9363

make_prev_keypart_map(real_key_parts),

9372

9364

HA_READ_KEY_EXACT);

9373

9365

9430

9422

/* Apply the constant equality conditions to the non-group select fields */

9431

9423

if (key_infix_len > 0)

9432

9424

{

9433

if ((result= file->index_read_map(record, group_prefix,

9425

if ((result= cursor->index_read_map(record, group_prefix,

9434

9426

make_prev_keypart_map(real_key_parts),

9435

9427

HA_READ_KEY_EXACT)))

9436

9428

return result;

9447

9439

{

9448

9440

/* Find the first subsequent record without NULL in the MIN/MAX field. */

9449

9441

key_copy(tmp_record, record, index_info, 0);

9450

result= file->index_read_map(record, tmp_record,

9442

result= cursor->index_read_map(record, tmp_record,

9451

9443

make_keypart_map(real_key_parts),

9452

9444

HA_READ_AFTER_KEY);

9453

9445

/*

9502

9494

if (min_max_ranges.elements > 0)

9503

9495

result= next_max_in_range();

9504

9496

else

9505

result= file->index_read_map(record, group_prefix,

9497

result= cursor->index_read_map(record, group_prefix,

9506

9498

make_prev_keypart_map(real_key_parts),

9507

9499

HA_READ_PREFIX_LAST);

9508

9500

return result;

9546

9538

{

9547

9539

if (!seen_first_key)

9548

9540

{

9549

result= file->index_first(record);

9541

result= cursor->index_first(record);

9550

9542

if (result)

9551

9543

return result;

9552

9544

seen_first_key= true;

9554

9546

else

9555

9547

{

9556

9548

/* Load the first key in this group into record. */

9557

result= file->index_read_map(record, group_prefix,

9549

result= cursor->index_read_map(record, group_prefix,

9558

9550

make_prev_keypart_map(group_key_parts),

9559

9551

HA_READ_AFTER_KEY);

9560

9552

if (result)

9636

9628

HA_READ_AFTER_KEY : HA_READ_KEY_OR_NEXT;

9637

9629

}

9638

9630

9639

result= file->index_read_map(record, group_prefix, keypart_map, find_flag);

9631

result= cursor->index_read_map(record, group_prefix, keypart_map, find_flag);

9640

9632

if (result)

9641

9633

{

9642

9634

if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&

9771

9763

HA_READ_BEFORE_KEY : HA_READ_PREFIX_LAST_OR_PREV;

9772

9764

}

9773

9765

9774

result= file->index_read_map(record, group_prefix, keypart_map, find_flag);

9766

result= cursor->index_read_map(record, group_prefix, keypart_map, find_flag);

9775

9767

9776

9768

if (result)

9777

9769

{