~drizzle-trunk/drizzle/development : revision 125

757

static

758

TRP_GROUP_MIN_MAX *get_best_group_min_max(PARAM *param, SEL_TREE *tree);

759

760

#ifndef DBUG_OFF

761

760

static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,

762

761

const char *msg);

763

762

static void print_ror_scans_arr(TABLE *table, const char *msg,

764

763

struct st_ror_scan_info **start,

765

764

struct st_ror_scan_info **end);

766

765

static void print_quick(QUICK_SELECT_I *quick, const key_map *needed_reg);

767

#endif

768

766

769

767

static SEL_TREE *tree_and(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);

770

768

static SEL_TREE *tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);

1013

1011

int *error)

1014

1012

{

1015

1013

SQL_SELECT *select;

1016

DBUG_ENTER("make_select");

1017

1014

1018

1015

*error=0;

1019

1016

1020

1017

if (!conds && !allow_null_cond)

1021

DBUG_RETURN(0);

1018

return(0);

1022

1019

if (!(select= new SQL_SELECT))

1023

1020

{

1024

1021

*error= 1; // out of memory

1025

DBUG_RETURN(0); /* purecov: inspected */

1022

return(0); /* purecov: inspected */

1026

1023

}

1027

1024

select->read_tables=read_tables;

1028

1025

select->const_tables=const_tables;

1037

1034

my_free(head->sort.io_cache, MYF(0));

1038

1035

head->sort.io_cache=0;

1039

1036

}

1040

DBUG_RETURN(select);

1037

return(select);

1041

1038

}

1042

1039

1043

1040

1067

1064

cleanup();

1068

1065

}

1069

1066

1070

#undef index // Fix for Unixware 7

1071

1072

1067

QUICK_SELECT_I::QUICK_SELECT_I()

1073

1068

:max_used_key_length(0),

1074

1069

used_key_parts(0)

1080

1075

:free_file(0),cur_range(NULL),last_range(0),dont_free(0)

1081

1076

{

1082

1077

my_bitmap_map *bitmap;

1083

DBUG_ENTER("QUICK_RANGE_SELECT::QUICK_RANGE_SELECT");

1084

1078

1085

1079

in_ror_merged_scan= 0;

1086

1080

sorted= 0;

1115

1109

}

1116

1110

else

1117

1111

bitmap_init(&column_bitmap, bitmap, head->s->fields, false);

1118

DBUG_VOID_RETURN;

1112

return;

1119

1113

}

1120

1114

1121

1115

1122

1116

int QUICK_RANGE_SELECT::init()

1123

1117

{

1124

DBUG_ENTER("QUICK_RANGE_SELECT::init");

1125

1126

1118

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

1127

1119

file->ha_index_or_rnd_end();

1128

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

1120

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

1129

1121

}

1130

1122

1131

1123

1138

1130

1139

1131

QUICK_RANGE_SELECT::~QUICK_RANGE_SELECT()

1140

1132

{

1141

DBUG_ENTER("QUICK_RANGE_SELECT::~QUICK_RANGE_SELECT");

1142

1133

if (!dont_free)

1143

1134

{

1144

1135

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

1152

1143

}

1153

1144

if (free_file)

1154

1145

{

1155

DBUG_PRINT("info", ("Freeing separate handler 0x%lx (free: %d)", (long) file,

1156

free_file));

1157

1146

file->ha_external_lock(current_thd, F_UNLCK);

1158

1147

file->close();

1159

1148

delete file;

1165

1154

}

1166

1155

head->column_bitmaps_set(save_read_set, save_write_set);

1167

1156

x_free(mrr_buf_desc);

1168

DBUG_VOID_RETURN;

1157

return;

1169

1158

}

1170

1159

1171

1160

1173

1162

TABLE *table)

1174

1163

:pk_quick_select(NULL), thd(thd_param)

1175

1164

{

1176

DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT");

1177

1165

index= MAX_KEY;

1178

1166

head= table;

1179

1167

bzero(&read_record, sizeof(read_record));

1180

1168

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

1181

DBUG_VOID_RETURN;

1169

return;

1182

1170

}

1183

1171

1184

1172

int QUICK_INDEX_MERGE_SELECT::init()

1185

1173

{

1186

DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::init");

1187

DBUG_RETURN(0);

1174

return(0);

1188

1175

}

1189

1176

1190

1177

int QUICK_INDEX_MERGE_SELECT::reset()

1191

1178

{

1192

DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::reset");

1193

DBUG_RETURN(read_keys_and_merge());

1179

return(read_keys_and_merge());

1194

1180

}

1195

1181

1196

1182

bool

1212

1198

{

1213

1199

List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);

1214

1200

QUICK_RANGE_SELECT* quick;

1215

DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT");

1216

1201

quick_it.rewind();

1217

1202

while ((quick= quick_it++))

1218

1203

quick->file= NULL;

1219

1204

quick_selects.delete_elements();

1220

1205

delete pk_quick_select;

1221

1206

free_root(&alloc,MYF(0));

1222

DBUG_VOID_RETURN;

1207

return;

1223

1208

}

1224

1209

1225

1210

1254

1239

1255

1240

int QUICK_ROR_INTERSECT_SELECT::init()

1256

1241

{

1257

DBUG_ENTER("QUICK_ROR_INTERSECT_SELECT::init");

1258

1242

/* Check if last_rowid was successfully allocated in ctor */

1259

DBUG_RETURN(!last_rowid);

1243

return(!last_rowid);

1260

1244

}

1261

1245

1262

1246

1286

1270

{

1287

1271

handler *save_file= file, *org_file;

1288

1272

THD *thd;

1289

DBUG_ENTER("QUICK_RANGE_SELECT::init_ror_merged_scan");

1290

1273

1291

1274

in_ror_merged_scan= 1;

1292

1275

if (reuse_handler)

1293

1276

{

1294

DBUG_PRINT("info", ("Reusing handler 0x%lx", (long) file));

1295

1277

if (init() || reset())

1296

1278

{

1297

DBUG_RETURN(1);

1279

return(1);

1298

1280

}

1299

1281

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

1300

1282

goto end;

1304

1286

if (free_file)

1305

1287

{

1306

1288

/* already have own 'handler' object. */

1307

DBUG_RETURN(0);

1289

return(0);

1308

1290

}

1309

1291

1310

1292

thd= head->in_use;

1356

1338

bitmap_copy(&column_bitmap, head->read_set);

1357

1339

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

1358

1340

1359

DBUG_RETURN(0);

1341

return(0);

1360

1342

1361

1343

failure:

1362

1344

head->column_bitmaps_set(save_read_set, save_write_set);

1363

1345

delete file;

1364

1346

file= save_file;

1365

DBUG_RETURN(1);

1347

return(1);

1366

1348

}

1367

1349

1368

1350

1380

1362

{

1381

1363

List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);

1382

1364

QUICK_RANGE_SELECT* quick;

1383

DBUG_ENTER("QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan");

1384

1365

1385

1366

/* Initialize all merged "children" quick selects */

1386

DBUG_ASSERT(!need_to_fetch_row || reuse_handler);

1367

assert(!need_to_fetch_row || reuse_handler);

1387

1368

if (!need_to_fetch_row && reuse_handler)

1388

1369

{

1389

1370

quick= quick_it++;

1392

1373

selects.

1393

1374

*/

1394

1375

if (quick->init_ror_merged_scan(true))

1395

DBUG_RETURN(1);

1376

return(1);

1396

1377

quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);

1397

1378

}

1398

1379

while ((quick= quick_it++))

1399

1380

{

1400

1381

if (quick->init_ror_merged_scan(false))

1401

DBUG_RETURN(1);

1382

return(1);

1402

1383

quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);

1403

1384

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

1404

1385

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

1406

1387

1407

1388

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

1408

1389

{

1409

DBUG_PRINT("error", ("ROR index_merge rnd_init call failed"));

1410

DBUG_RETURN(1);

1390

return(1);

1411

1391

}

1412

DBUG_RETURN(0);

1392

return(0);

1413

1393

}

1414

1394

1415

1395

1424

1404

1425

1405

int QUICK_ROR_INTERSECT_SELECT::reset()

1426

1406

{

1427

DBUG_ENTER("QUICK_ROR_INTERSECT_SELECT::reset");

1428

1407

if (!scans_inited && init_ror_merged_scan(true))

1429

DBUG_RETURN(1);

1408

return(1);

1430

1409

scans_inited= true;

1431

1410

List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);

1432

1411

QUICK_RANGE_SELECT *quick;

1433

1412

while ((quick= it++))

1434

1413

quick->reset();

1435

DBUG_RETURN(0);

1414

return(0);

1436

1415

}

1437

1416

1438

1417

1459

1438

1460

1439

QUICK_ROR_INTERSECT_SELECT::~QUICK_ROR_INTERSECT_SELECT()

1461

1440

{

1462

DBUG_ENTER("QUICK_ROR_INTERSECT_SELECT::~QUICK_ROR_INTERSECT_SELECT");

1463

1441

quick_selects.delete_elements();

1464

1442

delete cpk_quick;

1465

1443

free_root(&alloc,MYF(0));

1466

1444

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

1467

1445

head->file->ha_rnd_end();

1468

DBUG_VOID_RETURN;

1446

return;

1469

1447

}

1470

1448

1471

1449

1494

1472

1495

1473

int QUICK_ROR_UNION_SELECT::init()

1496

1474

{

1497

DBUG_ENTER("QUICK_ROR_UNION_SELECT::init");

1498

1475

if (init_queue(&queue, quick_selects.elements, 0,

1499

1476

false , QUICK_ROR_UNION_SELECT::queue_cmp,

1500

1477

(void*) this))

1501

1478

{

1502

1479

bzero(&queue, sizeof(QUEUE));

1503

DBUG_RETURN(1);

1480

return(1);

1504

1481

}

1505

1482

1506

1483

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

1507

DBUG_RETURN(1);

1484

return(1);

1508

1485

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

1509

DBUG_RETURN(0);

1486

return(0);

1510

1487

}

1511

1488

1512

1489

1543

1520

{

1544

1521

QUICK_SELECT_I *quick;

1545

1522

int error;

1546

DBUG_ENTER("QUICK_ROR_UNION_SELECT::reset");

1547

1523

have_prev_rowid= false;

1548

1524

if (!scans_inited)

1549

1525

{

1551

1527

while ((quick= it++))

1552

1528

{

1553

1529

if (quick->init_ror_merged_scan(false))

1554

DBUG_RETURN(1);

1530

return(1);

1555

1531

}

1556

1532

scans_inited= true;

1557

1533

}

1564

1540

while ((quick= it++))

1565

1541

{

1566

1542

if (quick->reset())

1567

DBUG_RETURN(1);

1543

return(1);

1568

1544

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

1569

1545

{

1570

1546

if (error == HA_ERR_END_OF_FILE)

1571

1547

continue;

1572

DBUG_RETURN(error);

1548

return(error);

1573

1549

}

1574

1550

quick->save_last_pos();

1575

1551

queue_insert(&queue, (uchar*)quick);

1577

1553

1578

1554

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

1579

1555

{

1580

DBUG_PRINT("error", ("ROR index_merge rnd_init call failed"));

1581

DBUG_RETURN(1);

1556

return(1);

1582

1557

}

1583

1558

1584

DBUG_RETURN(0);

1559

return(0);

1585

1560

}

1586

1561

1587

1562

1593

1568

1594

1569

QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT()

1595

1570

{

1596

DBUG_ENTER("QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT");

1597

1571

delete_queue(&queue);

1598

1572

quick_selects.delete_elements();

1599

1573

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

1600

1574

head->file->ha_rnd_end();

1601

1575

free_root(&alloc,MYF(0));

1602

DBUG_VOID_RETURN;

1576

return;

1603

1577

}

1604

1578

1605

1579

1952

1926

bool retrieve_full_rows __attribute__((__unused__)),

1953

1927

MEM_ROOT *parent_alloc)

1954

1928

{

1955

DBUG_ENTER("TRP_RANGE::make_quick");

1956

1929

QUICK_RANGE_SELECT *quick;

1957

1930

if ((quick= get_quick_select(param, key_idx, key, mrr_flags, mrr_buf_size,

1958

1931

parent_alloc)))

1960

1933

quick->records= records;

1961

1934

quick->read_time= read_cost;

1962

1935

}

1963

DBUG_RETURN(quick);

1936

return(quick);

1964

1937

}

1965

1938

};

1966

1939

2185

2158

{

2186

2159

uint idx;

2187

2160

double scan_time;

2188

DBUG_ENTER("SQL_SELECT::test_quick_select");

2189

DBUG_PRINT("enter",("keys_to_use: %lu prev_tables: %lu const_tables: %lu",

2190

(ulong) keys_to_use.to_ulonglong(), (ulong) prev_tables,

2191

(ulong) const_tables));

2192

DBUG_PRINT("info", ("records: %lu", (ulong) head->file->stats.records));

2193

2161

delete quick;

2194

2162

quick=0;

2195

2163

needed_reg.clear_all();

2196

2164

quick_keys.clear_all();

2197

2165

if (keys_to_use.is_clear_all())

2198

DBUG_RETURN(0);

2166

return(0);

2199

2167

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

2200

2168

if (!records)

2201

2169

records++; /* purecov: inspected */

2206

2174

if (limit < records)

2207

2175

read_time= (double) records + scan_time + 1; // Force to use index

2208

2176

else if (read_time <= 2.0 && !force_quick_range)

2209

DBUG_RETURN(0); /* No need for quick select */

2210

2211

DBUG_PRINT("info",("Time to scan table: %g", read_time));

2177

return(0); /* No need for quick select */

2212

2178

2213

2179

keys_to_use.intersect(head->keys_in_use_for_query);

2214

2180

if (!keys_to_use.is_clear_all())

2220

2186

PARAM param;

2221

2187

2222

2188

if (check_stack_overrun(thd, 2*STACK_MIN_SIZE, NULL))

2223

DBUG_RETURN(0); // Fatal error flag is set

2189

return(0); // Fatal error flag is set

2224

2190

2225

2191

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

2226

2192

param.thd= thd;

2247

2213

{

2248

2214

thd->no_errors=0;

2249

2215

free_root(&alloc,MYF(0)); // Return memory & allocator

2250

DBUG_RETURN(0); // Can't use range

2216

return(0); // Can't use range

2251

2217

}

2252

2218

key_parts= param.key_parts;

2253

2219

thd->mem_root= &alloc;

2291

2257

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

2292

2258

rows2double(records)) +

2293

2259

(double) records / TIME_FOR_COMPARE;

2294

DBUG_PRINT("info", ("'all'+'using index' scan will be using key %d, "

2295

"read time %g", key_for_use, key_read_time));

2296

2260

if (key_read_time < read_time)

2297

2261

read_time= key_read_time;

2298

2262

}

2388

2352

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

2389

2353

SEL_IMERGE *imerge;

2390

2354

TABLE_READ_PLAN *best_conj_trp= NULL, *new_conj_trp;

2391

DBUG_PRINT("info",("No range reads possible,"

2392

" trying to construct index_merge"));

2393

2355

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

2394

2356

while ((imerge= it++))

2395

2357

{

2425

2387

thd->no_errors=0;

2426

2388

}

2427

2389

2428

DBUG_EXECUTE("info", print_quick(quick, &needed_reg););

2390

print_quick(quick, &needed_reg);

2429

2391

2430

2392

/*

2431

2393

Assume that if the user is using 'limit' we will only need to scan

2432

2394

limit rows if we are using a key

2433

2395

*/

2434

DBUG_RETURN(records ? test(quick) : -1);

2396

return(records ? test(quick) : -1);

2435

2397

}

2436

2398

2437

2399

/*

2522

2484

double roru_index_costs;

2523

2485

ha_rows roru_total_records;

2524

2486

double roru_intersect_part= 1.0;

2525

DBUG_ENTER("get_best_disjunct_quick");

2526

DBUG_PRINT("info", ("Full table scan cost: %g", read_time));

2527

2487

2528

2488

if (!(range_scans= (TRP_RANGE**)alloc_root(param->mem_root,

2529

2489

sizeof(TRP_RANGE*)*

2530

2490

n_child_scans)))

2531

DBUG_RETURN(NULL);

2491

return(NULL);

2532

2492

/*

2533

2493

Collect best 'range' scan for each of disjuncts, and, while doing so,

2534

2494

analyze possibility of ROR scans. Also calculate some values needed by

2538

2498

ptree != imerge->trees_next;

2539

2499

ptree++, cur_child++)

2540

2500

{

2541

DBUG_EXECUTE("info", print_sel_tree(param, *ptree, &(*ptree)->keys_map,

2542

"tree in SEL_IMERGE"););

2501

print_sel_tree(param, *ptree, &(*ptree)->keys_map, "tree in SEL_IMERGE");

2543

2502

if (!(*cur_child= get_key_scans_params(param, *ptree, true, false, read_time)))

2544

2503

{

2545

2504

/*

2567

2526

non_cpk_scan_records += (*cur_child)->records;

2568

2527

}

2569

2528

2570

DBUG_PRINT("info", ("index_merge scans cost %g", imerge_cost));

2571

2529

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

2572

2530

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

2573

2531

{

2575

2533

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

2576

2534

more expensive

2577

2535

*/

2578

DBUG_PRINT("info", ("Sum of index_merge scans is more expensive than "

2579

"full table scan, bailing out"));

2580

DBUG_RETURN(NULL);

2536

return(NULL);

2581

2537

}

2582

2538

if (all_scans_rors)

2583

2539

{

2602

2558

&sweep_cost);

2603

2559

imerge_cost += sweep_cost.total_cost();

2604

2560

}

2605

DBUG_PRINT("info",("index_merge cost with rowid-to-row scan: %g",

2606

imerge_cost));

2607

2561

if (imerge_cost > read_time)

2608

2562

goto build_ror_index_merge;

2609

2563

2616

2570

{

2617

2571

if (!(param->imerge_cost_buff= (uint*)alloc_root(param->mem_root,

2618

2572

unique_calc_buff_size)))

2619

DBUG_RETURN(NULL);

2573

return(NULL);

2620

2574

param->imerge_cost_buff_size= unique_calc_buff_size;

2621

2575

}

2622

2576

2624

2578

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

2625

2579

param->table->file->ref_length,

2626

2580

param->thd->variables.sortbuff_size);

2627

DBUG_PRINT("info",("index_merge total cost: %g (wanted: less then %g)",

2628

imerge_cost, read_time));

2629

2581

if (imerge_cost < read_time)

2630

2582

{

2631

2583

if ((imerge_trp= new (param->mem_root)TRP_INDEX_MERGE))

2642

2594

2643

2595

build_ror_index_merge:

2644

2596

if (!all_scans_ror_able || param->thd->lex->sql_command == SQLCOM_DELETE)

2645

DBUG_RETURN(imerge_trp);

2597

return(imerge_trp);

2646

2598

2647

2599

/* Ok, it is possible to build a ROR-union, try it. */

2648

2600

bool dummy;

2650

2602

(TABLE_READ_PLAN**)alloc_root(param->mem_root,

2651

2603

sizeof(TABLE_READ_PLAN*)*

2652

2604

n_child_scans)))

2653

DBUG_RETURN(imerge_trp);

2605

return(imerge_trp);

2654

2606

skip_to_ror_scan:

2655

2607

roru_index_costs= 0.0;

2656

2608

roru_total_records= 0;

2686

2638

if (prev_plan->is_ror)

2687

2639

*cur_roru_plan= prev_plan;

2688

2640

else

2689

DBUG_RETURN(imerge_trp);

2641

return(imerge_trp);

2690

2642

roru_index_costs += (*cur_roru_plan)->read_cost;

2691

2643

}

2692

2644

else

2726

2678

sweep_cost.total_cost();

2727

2679

}

2728

2680

2729

DBUG_PRINT("info", ("ROR-union: cost %g, %d members", roru_total_cost,

2730

n_child_scans));

2731

2681

TRP_ROR_UNION* roru;

2732

2682

if (roru_total_cost < read_time)

2733

2683

{

2737

2687

roru->last_ror= roru_read_plans + n_child_scans;

2738

2688

roru->read_cost= roru_total_cost;

2739

2689

roru->records= roru_total_records;

2740

DBUG_RETURN(roru);

2690

return(roru);

2741

2691

}

2742

2692

}

2743

DBUG_RETURN(imerge_trp);

2693

return(imerge_trp);

2744

2694

}

2745

2695

2746

2696

2789

2739

ROR_SCAN_INFO *ror_scan;

2790

2740

my_bitmap_map *bitmap_buf;

2791

2741

uint keynr;

2792

DBUG_ENTER("make_ror_scan");

2793

2742

2794

2743

if (!(ror_scan= (ROR_SCAN_INFO*)alloc_root(param->mem_root,

2795

2744

sizeof(ROR_SCAN_INFO))))

2796

DBUG_RETURN(NULL);

2745

return(NULL);

2797

2746

2798

2747

ror_scan->idx= idx;

2799

2748

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

2804

2753

2805

2754

if (!(bitmap_buf= (my_bitmap_map*) alloc_root(param->mem_root,

2806

2755

param->fields_bitmap_size)))

2807

DBUG_RETURN(NULL);

2756

return(NULL);

2808

2757

2809

2758

if (bitmap_init(&ror_scan->covered_fields, bitmap_buf,

2810

2759

param->table->s->fields, false))

2811

DBUG_RETURN(NULL);

2760

return(NULL);

2812

2761

bitmap_clear_all(&ror_scan->covered_fields);

2813

2762

2814

2763

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

2822

2771

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

2823

2772

ror_scan->index_read_cost=

2824

2773

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

2825

DBUG_RETURN(ror_scan);

2774

return(ror_scan);

2826

2775

}

2827

2776

2828

2777

3058

3007

max_range.key= key_val;

3059

3008

max_range.flag= HA_READ_AFTER_KEY;

3060

3009

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

3061

DBUG_ENTER("ror_scan_selectivity");

3062

3010

3063

3011

for (sel_arg= scan->sel_arg; sel_arg;

3064

3012

sel_arg= sel_arg->next_key_part)

3065

3013

{

3066

DBUG_PRINT("info",("sel_arg step"));

3067

3014

cur_covered= test(bitmap_is_set(&info->covered_fields,

3068

3015

key_part[sel_arg->part].fieldnr-1));

3069

3016

if (cur_covered != prev_covered)

3092

3039

{

3093

3040

/* uncovered -> covered */

3094

3041

double tmp= rows2double(records)/rows2double(prev_records);

3095

DBUG_PRINT("info", ("Selectivity multiplier: %g", tmp));

3096

3042

selectivity_mult *= tmp;

3097

3043

prev_records= HA_POS_ERROR;

3098

3044

}

3108

3054

{

3109

3055

double tmp= rows2double(info->param->table->quick_rows[scan->keynr]) /

3110

3056

rows2double(prev_records);

3111

DBUG_PRINT("info", ("Selectivity multiplier: %g", tmp));

3112

3057

selectivity_mult *= tmp;

3113

3058

}

3114

DBUG_PRINT("info", ("Returning multiplier: %g", selectivity_mult));

3115

DBUG_RETURN(selectivity_mult);

3059

return(selectivity_mult);

3116

3060

}

3117

3061

3118

3062

3157

3101

{

3158

3102

double selectivity_mult= 1.0;

3159

3103

3160

DBUG_ENTER("ror_intersect_add");

3161

DBUG_PRINT("info", ("Current out_rows= %g", info->out_rows));

3162

DBUG_PRINT("info", ("Adding scan on %s",

3163

info->param->table->key_info[ror_scan->keynr].name));

3164

DBUG_PRINT("info", ("is_cpk_scan: %d",is_cpk_scan));

3165

3166

3104

selectivity_mult = ror_scan_selectivity(info, ror_scan);

3167

3105

if (selectivity_mult == 1.0)

3168

3106

{

3169

3107

/* Don't add this scan if it doesn't improve selectivity. */

3170

DBUG_PRINT("info", ("The scan doesn't improve selectivity."));

3171

DBUG_RETURN(false);

3108

return(false);

3172

3109

}

3173

3110

3174

3111

info->out_rows *= selectivity_mult;

3191

3128

if (!info->is_covering && bitmap_is_subset(&info->param->needed_fields,

3192

3129

&info->covered_fields))

3193

3130

{

3194

DBUG_PRINT("info", ("ROR-intersect is covering now"));

3195

3131

info->is_covering= true;

3196

3132

}

3197

3133

}

3198

3134

3199

3135

info->total_cost= info->index_scan_costs;

3200

DBUG_PRINT("info", ("info->total_cost: %g", info->total_cost));

3201

3136

if (!info->is_covering)

3202

3137

{

3203

3138

COST_VECT sweep_cost;

3206

3141

get_sweep_read_cost(info->param->table, double2rows(info->out_rows),

3207

3142

is_interrupted, &sweep_cost);

3208

3143

info->total_cost += sweep_cost.total_cost();

3209

DBUG_PRINT("info", ("info->total_cost= %g", info->total_cost));

3210

3144

}

3211

DBUG_PRINT("info", ("New out_rows: %g", info->out_rows));

3212

DBUG_PRINT("info", ("New cost: %g, %scovering", info->total_cost,

3213

info->is_covering?"" : "non-"));

3214

DBUG_RETURN(true);

3145

return(true);

3215

3146

}

3216

3147

3217

3148

3286

3217

{

3287

3218

uint idx;

3288

3219

double min_cost= DBL_MAX;

3289

DBUG_ENTER("get_best_ror_intersect");

3290

3220

3291

3221

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

3292

DBUG_RETURN(NULL);

3222

return(NULL);

3293

3223

3294

3224

/*

3295

3225

Step1: Collect ROR-able SEL_ARGs and create ROR_SCAN_INFO for each of

3324

3254

}

3325

3255

3326

3256

tree->ror_scans_end= cur_ror_scan;

3327

DBUG_EXECUTE("info",print_ror_scans_arr(param->table, "original",

3257

print_ror_scans_arr(param->table, "original",

3328

3258

tree->ror_scans,

3329

tree->ror_scans_end););

3259

tree->ror_scans_end);

3330

3260

/*

3331

3261

Ok, [ror_scans, ror_scans_end) is array of ptrs to initialized

3332

3262

ROR_SCAN_INFO's.

3334

3264

*/

3335

3265

my_qsort(tree->ror_scans, tree->n_ror_scans, sizeof(ROR_SCAN_INFO*),

3336

3266

(qsort_cmp)cmp_ror_scan_info);

3337

DBUG_EXECUTE("info",print_ror_scans_arr(param->table, "ordered",

3267

print_ror_scans_arr(param->table, "ordered",

3338

3268

tree->ror_scans,

3339

tree->ror_scans_end););

3269

tree->ror_scans_end);

3340

3270

3341

3271

ROR_SCAN_INFO **intersect_scans; /* ROR scans used in index intersection */

3342

3272

ROR_SCAN_INFO **intersect_scans_end;

3378

3308

3379

3309

if (intersect_scans_best == intersect_scans)

3380

3310

{

3381

DBUG_PRINT("info", ("None of scans increase selectivity"));

3382

DBUG_RETURN(NULL);

3311

return(NULL);

3383

3312

}

3384

3313

3385

DBUG_EXECUTE("info",print_ror_scans_arr(param->table,

3314

print_ror_scans_arr(param->table,

3386

3315

"best ROR-intersection",

3387

3316

intersect_scans,

3388

intersect_scans_best););

3317

intersect_scans_best);

3389

3318

3390

3319

*are_all_covering= intersect->is_covering;

3391

3320

uint best_num= intersect_scans_best - intersect_scans;

3411

3340

if (min_cost < read_time && (cpk_scan_used || best_num > 1))

3412

3341

{

3413

3342

if (!(trp= new (param->mem_root) TRP_ROR_INTERSECT))

3414

DBUG_RETURN(trp);

3343

return(trp);

3415

3344

if (!(trp->first_scan=

3416

3345

(ROR_SCAN_INFO**)alloc_root(param->mem_root,

3417

3346

sizeof(ROR_SCAN_INFO*)*best_num)))

3418

DBUG_RETURN(NULL);

3347

return(NULL);

3419

3348

memcpy(trp->first_scan, intersect_scans, best_num*sizeof(ROR_SCAN_INFO*));

3420

3349

trp->last_scan= trp->first_scan + best_num;

3421

3350

trp->is_covering= intersect_best->is_covering;

3428

3357

trp->records= best_rows;

3429

3358

trp->index_scan_costs= intersect_best->index_scan_costs;

3430

3359

trp->cpk_scan= cpk_scan_used? cpk_scan: NULL;

3431

DBUG_PRINT("info", ("Returning non-covering ROR-intersect plan:"

3432

"cost %g, records %lu",

3433

trp->read_cost, (ulong) trp->records));

3434

3360

}

3435

DBUG_RETURN(trp);

3361

return(trp);

3436

3362

}

3437

3363

3438

3364

3476

3402

{

3477

3403

ROR_SCAN_INFO **ror_scan_mark;

3478

3404

ROR_SCAN_INFO **ror_scans_end= tree->ror_scans_end;

3479

DBUG_ENTER("get_best_covering_ror_intersect");

3480

3405

3481

3406

for (ROR_SCAN_INFO **scan= tree->ror_scans; scan != ror_scans_end; ++scan)

3482

3407

(*scan)->key_components=

3497

3422

if (!covered_fields->bitmap ||

3498

3423

bitmap_init(covered_fields, covered_fields->bitmap,

3499

3424

param->table->s->fields, false))

3500

DBUG_RETURN(0);

3425

return(0);

3501

3426

bitmap_clear_all(covered_fields);

3502

3427

3503

3428

double total_cost= 0.0f;

3504

3429

ha_rows records=0;

3505

3430

bool all_covered;

3506

3431

3507

DBUG_PRINT("info", ("Building covering ROR-intersection"));

3508

DBUG_EXECUTE("info", print_ror_scans_arr(param->table,

3432

print_ror_scans_arr(param->table,

3509

3433

"building covering ROR-I",

3510

ror_scan_mark, ror_scans_end););

3434

ror_scan_mark, ror_scans_end);

3511

3435

do

3512

3436

{

3513

3437

/*

3528

3452

my_qsort(ror_scan_mark, ror_scans_end-ror_scan_mark, sizeof(ROR_SCAN_INFO*),

3529

3453

(qsort_cmp)cmp_ror_scan_info_covering);

3530

3454

3531

DBUG_EXECUTE("info", print_ror_scans_arr(param->table,

3455

print_ror_scans_arr(param->table,

3532

3456

"remaining scans",

3533

ror_scan_mark, ror_scans_end););

3457

ror_scan_mark, ror_scans_end);

3534

3458

3535

3459

/* I=I-first(I) */

3536

3460

total_cost += (*ror_scan_mark)->index_read_cost;

3537

3461

records += (*ror_scan_mark)->records;

3538

DBUG_PRINT("info", ("Adding scan on %s",

3539

param->table->key_info[(*ror_scan_mark)->keynr].name));

3540

3462

if (total_cost > read_time)

3541

DBUG_RETURN(NULL);

3463

return(NULL);

3542

3464

/* F=F-covered by first(I) */

3543

3465

bitmap_union(covered_fields, &(*ror_scan_mark)->covered_fields);

3544

3466

all_covered= bitmap_is_subset(&param->needed_fields, covered_fields);

3545

3467

} while ((++ror_scan_mark < ror_scans_end) && !all_covered);

3546

3468

3547

3469

if (!all_covered || (ror_scan_mark - tree->ror_scans) == 1)

3548

DBUG_RETURN(NULL);

3470

return(NULL);

3549

3471

3550

3472

/*

3551

3473

Ok, [tree->ror_scans .. ror_scan) holds covering index_intersection with

3552

3474

cost total_cost.

3553

3475

*/

3554

DBUG_PRINT("info", ("Covering ROR-intersect scans cost: %g", total_cost));

3555

DBUG_EXECUTE("info", print_ror_scans_arr(param->table,

3476

print_ror_scans_arr(param->table,

3556

3477

"creating covering ROR-intersect",

3557

tree->ror_scans, ror_scan_mark););

3478

tree->ror_scans, ror_scan_mark);

3558

3479

3559

3480

/* Add priority queue use cost. */

3560

3481

total_cost += rows2double(records)*

3561

3482

log((double)(ror_scan_mark - tree->ror_scans)) /

3562

3483

(TIME_FOR_COMPARE_ROWID * M_LN2);

3563

DBUG_PRINT("info", ("Covering ROR-intersect full cost: %g", total_cost));

3564

3484

3565

3485

if (total_cost > read_time)

3566

DBUG_RETURN(NULL);

3486

return(NULL);

3567

3487

3568

3488

TRP_ROR_INTERSECT *trp;

3569

3489

if (!(trp= new (param->mem_root) TRP_ROR_INTERSECT))

3570

DBUG_RETURN(trp);

3490

return(trp);

3571

3491

uint best_num= (ror_scan_mark - tree->ror_scans);

3572

3492

if (!(trp->first_scan= (ROR_SCAN_INFO**)alloc_root(param->mem_root,

3573

3493

sizeof(ROR_SCAN_INFO*)*

3574

3494

best_num)))

3575

DBUG_RETURN(NULL);

3495

return(NULL);

3576

3496

memcpy(trp->first_scan, tree->ror_scans, best_num*sizeof(ROR_SCAN_INFO*));

3577

3497

trp->last_scan= trp->first_scan + best_num;

3578

3498

trp->is_covering= true;

3581

3501

trp->cpk_scan= NULL;

3582

3502

set_if_smaller(param->table->quick_condition_rows, records);

3583

3503

3584

DBUG_PRINT("info",

3585

("Returning covering ROR-intersect plan: cost %g, records %lu",

3586

trp->read_cost, (ulong) trp->records));

3587

DBUG_RETURN(trp);

3504

return(trp);

3588

3505

}

3589

3506

3590

3507

3624

3541

ha_rows best_records= 0;

3625

3542

uint best_mrr_flags= 0, best_buf_size= 0;

3626

3543

TRP_RANGE* read_plan= NULL;

3627

DBUG_ENTER("get_key_scans_params");

3628

3544

/*

3629

3545

Note that there may be trees that have type SEL_TREE::KEY but contain no

3630

3546

key reads at all, e.g. tree for expression "key1 is not null" where key1

3631

3547

is defined as "not null".

3632

3548

*/

3633

DBUG_EXECUTE("info", print_sel_tree(param, tree, &tree->keys_map,

3634

"tree scans"););

3549

print_sel_tree(param, tree, &tree->keys_map, "tree scans");

3635

3550

tree->ror_scans_map.clear_all();

3636

3551

tree->n_ror_scans= 0;

3637

3552

for (idx= 0,key=tree->keys, end=key+param->keys; key != end; key++,idx++)

3670

3585

}

3671

3586

}

3672

3587

3673

DBUG_EXECUTE("info", print_sel_tree(param, tree, &tree->ror_scans_map,

3674

"ROR scans"););

3588

print_sel_tree(param, tree, &tree->ror_scans_map, "ROR scans");

3675

3589

if (key_to_read)

3676

3590

{

3677

3591

idx= key_to_read - tree->keys;

3682

3596

read_plan->is_ror= tree->ror_scans_map.is_set(idx);

3683

3597

read_plan->read_cost= read_time;

3684

3598

read_plan->mrr_buf_size= best_buf_size;

3685

DBUG_PRINT("info",

3686

("Returning range plan for key %s, cost %g, records %lu",

3687

param->table->key_info[param->real_keynr[idx]].name,

3688

read_plan->read_cost, (ulong) read_plan->records));

3689

3599

}

3690

3600

}

3691

else

3692

DBUG_PRINT("info", ("No 'range' table read plan found"));

3693

3601

3694

DBUG_RETURN(read_plan);

3602

return(read_plan);

3695

3603

}

3696

3604

3697

3605

3728

3636

{

3729

3637

QUICK_ROR_INTERSECT_SELECT *quick_intrsect;

3730

3638

QUICK_RANGE_SELECT *quick;

3731

DBUG_ENTER("TRP_ROR_INTERSECT::make_quick");

3732

3639

MEM_ROOT *alloc;

3733

3640

3734

3641

if ((quick_intrsect=

3737

3644

false),

3738

3645

parent_alloc)))

3739

3646

{

3740

DBUG_EXECUTE("info", print_ror_scans_arr(param->table,

3647

print_ror_scans_arr(param->table,

3741

3648

"creating ROR-intersect",

3742

first_scan, last_scan););

3649

first_scan, last_scan);

3743

3650

alloc= parent_alloc? parent_alloc: &quick_intrsect->alloc;

3744

3651

for (; first_scan != last_scan;++first_scan)

3745

3652

{

3750

3657

quick_intrsect->push_quick_back(quick))

3751

3658

{

3752

3659

delete quick_intrsect;

3753

DBUG_RETURN(NULL);

3660

return(NULL);

3754

3661

}

3755

3662

}

3756

3663

if (cpk_scan)

3761

3668

0, alloc)))

3762

3669

{

3763

3670

delete quick_intrsect;

3764

DBUG_RETURN(NULL);

3671

return(NULL);

3765

3672

}

3766

3673

quick->file= NULL;

3767

3674

quick_intrsect->cpk_quick= quick;

3769

3676

quick_intrsect->records= records;

3770

3677

quick_intrsect->read_time= read_cost;

3771

3678

}

3772

DBUG_RETURN(quick_intrsect);

3679

return(quick_intrsect);

3773

3680

}

3774

3681

3775

3682

3780

3687

QUICK_ROR_UNION_SELECT *quick_roru;

3781

3688

TABLE_READ_PLAN **scan;

3782

3689

QUICK_SELECT_I *quick;

3783

DBUG_ENTER("TRP_ROR_UNION::make_quick");

3784

3690

/*

3785

3691

It is impossible to construct a ROR-union that will not retrieve full

3786

3692

rows, ignore retrieve_full_rows parameter.

3791

3697

{

3792

3698

if (!(quick= (*scan)->make_quick(param, false, &quick_roru->alloc)) ||

3793

3699

quick_roru->push_quick_back(quick))

3794

DBUG_RETURN(NULL);

3700

return(NULL);

3795

3701

}

3796

3702

quick_roru->records= records;

3797

3703

quick_roru->read_time= read_cost;

3798

3704

}

3799

DBUG_RETURN(quick_roru);

3705

return(quick_roru);

3800

3706

}

3801

3707

3802

3708

3857

3763

Item_result cmp_type, bool inv)

3858

3764

{

3859

3765

SEL_TREE *tree= 0;

3860

DBUG_ENTER("get_func_mm_tree");

3861

3766

3862

3767

switch (cond_func->functype()) {

3863

3768

4072

3977

}

4073

3978

}

4074

3979

4075

DBUG_RETURN(tree);

3980

return(tree);

4076

3981

}

4077

3982

4078

3983

4156

4061

table_map ref_tables= 0;

4157

4062

table_map param_comp= ~(param->prev_tables | param->read_tables |

4158

4063

param->current_table);

4159

DBUG_ENTER("get_full_func_mm_tree");

4160

4064

4161

4065

for (uint i= 0; i < cond_func->arg_count; i++)

4162

4066

{

4185

4089

}

4186

4090

}

4187

4091

}

4188

DBUG_RETURN(ftree);

4092

return(ftree);

4189

4093

}

4190

4094

4191

4095

/* make a select tree of all keys in condition */

4197

4101

Item_field *field_item= 0;

4198

4102

bool inv= false;

4199

4103

Item *value= 0;

4200

DBUG_ENTER("get_mm_tree");

4201

4104

4202

4105

if (cond->type() == Item::COND_ITEM)

4203

4106

{

4212

4115

SEL_TREE *new_tree=get_mm_tree(param,item);

4213

4116

if (param->thd->is_fatal_error ||

4214

4117

param->alloced_sel_args > SEL_ARG::MAX_SEL_ARGS)

4215

DBUG_RETURN(0); // out of memory

4118

return(0); // out of memory

4216

4119

tree=tree_and(param,tree,new_tree);

4217

4120

if (tree && tree->type == SEL_TREE::IMPOSSIBLE)

4218

4121

break;

4228

4131

{

4229

4132

SEL_TREE *new_tree=get_mm_tree(param,item);

4230

4133

if (!new_tree)

4231

DBUG_RETURN(0); // out of memory

4134

return(0); // out of memory

4232

4135

tree=tree_or(param,tree,new_tree);

4233

4136

if (!tree || tree->type == SEL_TREE::ALWAYS)

4234

4137

break;

4235

4138

}

4236

4139

}

4237

4140

}

4238

DBUG_RETURN(tree);

4141

return(tree);

4239

4142

}

4240

4143

/* Here when simple cond */

4241

4144

if (cond->const_item())

4251

4154

tree= cond->val_int() ? new(tmp_root) SEL_TREE(SEL_TREE::ALWAYS) :

4252

4155

new(tmp_root) SEL_TREE(SEL_TREE::IMPOSSIBLE);

4253

4156

param->thd->mem_root= tmp_root;

4254

DBUG_RETURN(tree);

4157

return(tree);

4255

4158

}

4256

4159

4257

4160

table_map ref_tables= 0;

4262

4165

ref_tables= cond->used_tables();

4263

4166

if ((ref_tables & param->current_table) ||

4264

4167

(ref_tables & ~(param->prev_tables | param->read_tables)))

4265

DBUG_RETURN(0);

4266

DBUG_RETURN(new SEL_TREE(SEL_TREE::MAYBE));

4168

return(0);

4169

return(new SEL_TREE(SEL_TREE::MAYBE));

4267

4170

}

4268

4171

4269

4172

Item_func *cond_func= (Item_func*) cond;

4271

4174

cond_func->functype() == Item_func::IN_FUNC)

4272

4175

inv= ((Item_func_opt_neg *) cond_func)->negated;

4273

4176

else if (cond_func->select_optimize() == Item_func::OPTIMIZE_NONE)

4274

DBUG_RETURN(0);

4177

return(0);

4275

4178

4276

4179

param->cond= cond;

4277

4180

4312

4215

{

4313

4216

Item_func_in *func=(Item_func_in*) cond_func;

4314

4217

if (func->key_item()->real_item()->type() != Item::FIELD_ITEM)

4315

DBUG_RETURN(0);

4218

return(0);

4316

4219

field_item= (Item_field*) (func->key_item()->real_item());

4317

4220

ftree= get_full_func_mm_tree(param, cond_func, field_item, NULL, inv);

4318

4221

break;

4321

4224

{

4322

4225

Item_equal *item_equal= (Item_equal *) cond;

4323

4226

if (!(value= item_equal->get_const()))

4324

DBUG_RETURN(0);

4227

return(0);

4325

4228

Item_equal_iterator it(*item_equal);

4326

4229

ref_tables= value->used_tables();

4327

4230

while ((field_item= it++))

4336

4239

}

4337

4240

}

4338

4241

4339

DBUG_RETURN(ftree);

4242

return(ftree);

4340

4243

}

4341

4244

default:

4342

4245

if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM)

4352

4255

value= cond_func->arguments()[0];

4353

4256

}

4354

4257

else

4355

DBUG_RETURN(0);

4258

return(0);

4356

4259

ftree= get_full_func_mm_tree(param, cond_func, field_item, value, inv);

4357

4260

}

4358

4261

4359

DBUG_RETURN(ftree);

4262

return(ftree);

4360

4263

}

4361

4264

4362

4265

4366

4269

Item *value,

4367

4270

Item_result cmp_type __attribute__((__unused__)))

4368

4271

{

4369

DBUG_ENTER("get_mm_parts");

4370

4272

if (field->table != param->table)

4371

DBUG_RETURN(0);

4273

return(0);

4372

4274

4373

4275

KEY_PART *key_part = param->key_parts;

4374

4276

KEY_PART *end = param->key_parts_end;

4375

4277

SEL_TREE *tree=0;

4376

4278

if (value &&

4377

4279

value->used_tables() & ~(param->prev_tables | param->read_tables))

4378

DBUG_RETURN(0);

4280

return(0);

4379

4281

for (; key_part != end ; key_part++)

4380

4282

{

4381

4283

if (field->eq(key_part->field))

4382

4284

{

4383

4285

SEL_ARG *sel_arg=0;

4384

4286

if (!tree && !(tree=new SEL_TREE()))

4385

DBUG_RETURN(0); // OOM

4287

return(0); // OOM

4386

4288

if (!value || !(value->used_tables() & ~param->read_tables))

4387

4289

{

4388

4290

sel_arg=get_mm_leaf(param,cond_func,

4392

4294

if (sel_arg->type == SEL_ARG::IMPOSSIBLE)

4393

4295

{

4394

4296

tree->type=SEL_TREE::IMPOSSIBLE;

4395

DBUG_RETURN(tree);

4297

return(tree);

4396

4298

}

4397

4299

}

4398

4300

else

4399

4301

{

4400

4302

// This key may be used later

4401

4303

if (!(sel_arg= new SEL_ARG(SEL_ARG::MAYBE_KEY)))

4402

DBUG_RETURN(0); // OOM

4304

return(0); // OOM

4403

4305

}

4404

4306

sel_arg->part=(uchar) key_part->part;

4405

4307

tree->keys[key_part->key]=sel_add(tree->keys[key_part->key],sel_arg);

4407

4309

}

4408

4310

}

4409

4311

4410

DBUG_RETURN(tree);

4312

return(tree);

4411

4313

}

4412

4314

4413

4315

4422

4324

uchar *str;

4423

4325

ulong orig_sql_mode;

4424

4326

int err;

4425

DBUG_ENTER("get_mm_leaf");

4426

4327

4427

4328

/*

4428

4329

We need to restore the runtime mem_root of the thread in this

4719

4620

4720

4621

end:

4721

4622

param->thd->mem_root= alloc;

4722

DBUG_RETURN(tree);

4623

return(tree);

4723

4624

}

4724

4625

4725

4626

4778

4679

static SEL_TREE *

4779

4680

tree_and(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2)

4780

4681

{

4781

DBUG_ENTER("tree_and");

4782

4682

if (!tree1)

4783

DBUG_RETURN(tree2);

4683

return(tree2);

4784

4684

if (!tree2)

4785

DBUG_RETURN(tree1);

4685

return(tree1);

4786

4686

if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)

4787

DBUG_RETURN(tree1);

4687

return(tree1);

4788

4688

if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)

4789

DBUG_RETURN(tree2);

4689

return(tree2);

4790

4690

if (tree1->type == SEL_TREE::MAYBE)

4791

4691

{

4792

4692

if (tree2->type == SEL_TREE::KEY)

4793

4693

tree2->type=SEL_TREE::KEY_SMALLER;

4794

DBUG_RETURN(tree2);

4694

return(tree2);

4795

4695

}

4796

4696

if (tree2->type == SEL_TREE::MAYBE)

4797

4697

{

4798

4698

tree1->type=SEL_TREE::KEY_SMALLER;

4799

DBUG_RETURN(tree1);

4699

return(tree1);

4800

4700

}

4801

4701

key_map result_keys;

4802

4702

result_keys.clear_all();

4817

4717

if (*key1 && (*key1)->type == SEL_ARG::IMPOSSIBLE)

4818

4718

{

4819

4719

tree1->type= SEL_TREE::IMPOSSIBLE;

4820

DBUG_RETURN(tree1);

4720

return(tree1);

4821

4721

}

4822

4722

result_keys.set_bit(key1 - tree1->keys);

4823

4723

#ifdef EXTRA_DEBUG

4831

4731

if (!result_keys.is_clear_all())

4832

4732

{

4833

4733

tree1->merges.empty();

4834

DBUG_RETURN(tree1);

4734

return(tree1);

4835

4735

}

4836

4736

4837

4737

/* ok, both trees are index_merge trees */

4838

4738

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

4839

DBUG_RETURN(tree1);

4739

return(tree1);

4840

4740

}

4841

4741

4842

4742

4850

4750

RANGE_OPT_PARAM* param)

4851

4751

{

4852

4752

key_map common_keys= tree1->keys_map;

4853

DBUG_ENTER("sel_trees_can_be_ored");

4854

4753

common_keys.intersect(tree2->keys_map);

4855

4754

4856

4755

if (common_keys.is_clear_all())

4857

DBUG_RETURN(false);

4756

return(false);

4858

4757

4859

4758

/* trees have a common key, check if they refer to same key part */

4860

4759

SEL_ARG **key1,**key2;

4866

4765

key2= tree2->keys + key_no;

4867

4766

if ((*key1)->part == (*key2)->part)

4868

4767

{

4869

DBUG_RETURN(true);

4768

return(true);

4870

4769

}

4871

4770

}

4872

4771

}

4873

DBUG_RETURN(false);

4772

return(false);

4874

4773

}

4875

4774

4876

4775

4952

4851

static SEL_TREE *

4953

4852

tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2)

4954

4853

{

4955

DBUG_ENTER("tree_or");

4956

4854

if (!tree1 || !tree2)

4957

DBUG_RETURN(0);

4855

return(0);

4958

4856

if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)

4959

DBUG_RETURN(tree2);

4857

return(tree2);

4960

4858

if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)

4961

DBUG_RETURN(tree1);

4859

return(tree1);

4962

4860

if (tree1->type == SEL_TREE::MAYBE)

4963

DBUG_RETURN(tree1); // Can't use this

4861

return(tree1); // Can't use this

4964

4862

if (tree2->type == SEL_TREE::MAYBE)

4965

DBUG_RETURN(tree2);

4863

return(tree2);

4966

4864

4967

4865

SEL_TREE *result= 0;

4968

4866

key_map result_keys;

4998

4896

bool no_trees= remove_nonrange_trees(param, tree1);

4999

4897

no_trees= no_trees || remove_nonrange_trees(param, tree2);

5000

4898

if (no_trees)

5001

DBUG_RETURN(new SEL_TREE(SEL_TREE::ALWAYS));

4899

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

5002

4900

}

5003

4901

SEL_IMERGE *merge;

5004

4902

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

5024

4922

swap_variables(SEL_TREE*, tree1, tree2);

5025

4923

5026

4924

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

5027

DBUG_RETURN(new SEL_TREE(SEL_TREE::ALWAYS));

4925

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

5028

4926

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

5029

4927

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

5030

4928

result= new SEL_TREE(SEL_TREE::ALWAYS);

5032

4930

result= tree1;

5033

4931

}

5034

4932

}

5035

DBUG_RETURN(result);

4933

return(result);

5036

4934

}

5037

4935

5038

4936

5594

5492

{

5595

5493

enum leaf_color remove_color;

5596

5494

SEL_ARG *root,*nod,**par,*fix_par;

5597

DBUG_ENTER("tree_delete");

5598

5495

5599

5496

root=this;

5600

5497

this->parent= 0;

5644

5541

}

5645

5542

5646

5543

if (root == &null_element)

5647

DBUG_RETURN(0); // Maybe root later

5544

return(0); // Maybe root later

5648

5545

if (remove_color == BLACK)

5649

5546

root=rb_delete_fixup(root,nod,fix_par);

5650

5547

test_rb_tree(root,root->parent);

5652

5549

root->use_count=this->use_count; // Fix root counters

5653

5550

root->elements=this->elements-1;

5654

5551

root->maybe_flag=this->maybe_flag;

5655

DBUG_RETURN(root);

5552

return(root);

5656

5553

}

5657

5554

5658

5555

6280

6177

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

6281

6178

ha_rows rows;

6282

6179

uint keynr= param->real_keynr[idx];

6283

DBUG_ENTER("check_quick_select");

6284

6180

6285

6181

/* Handle cases when we don't have a valid non-empty list of range */

6286

6182

if (!tree)

6287

DBUG_RETURN(HA_POS_ERROR);

6183

return(HA_POS_ERROR);

6288

6184

if (tree->type == SEL_ARG::IMPOSSIBLE)

6289

DBUG_RETURN(0L);

6185

return(0L);

6290

6186

if (tree->type != SEL_ARG::KEY_RANGE || tree->part != 0)

6291

DBUG_RETURN(HA_POS_ERROR);

6187

return(HA_POS_ERROR);

6292

6188

6293

6189

seq.keyno= idx;

6294

6190

seq.real_keyno= keynr;

6347

6243

param->is_ror_scan= true;

6348

6244

}

6349

6245

6350

DBUG_PRINT("exit", ("Records: %lu", (ulong) rows));

6351

DBUG_RETURN(rows); //psergey-merge:todo: maintain first_null_comp.

6246

return(rows); //psergey-merge:todo: maintain first_null_comp.

6352

6247

}

6353

6248

6354

6249

6456

6351

{

6457

6352

QUICK_RANGE_SELECT *quick;

6458

6353

bool create_err= false;

6459

DBUG_ENTER("get_quick_select");

6460

6354

6461

6355

quick=new QUICK_RANGE_SELECT(param->thd, param->table,

6462

6356

param->real_keynr[idx],

6482

6376

param->table->key_info[param->real_keynr[idx]].key_parts);

6483

6377

}

6484

6378

}

6485

DBUG_RETURN(quick);

6379

return(quick);

6486

6380

}

6487

6381

6488

6382

6831

6725

int result;

6832

6726

Unique *unique;

6833

6727

handler *file= head->file;

6834

DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::read_keys_and_merge");

6835

6728

6836

6729

file->extra(HA_EXTRA_KEYREAD);

6837

6730

head->prepare_for_position();

6838

6731

6839

6732

cur_quick_it.rewind();

6840

6733

cur_quick= cur_quick_it++;

6841

DBUG_ASSERT(cur_quick != 0);

6734

assert(cur_quick != 0);

6842

6735

6843

6736

/*

6844

6737

We reuse the same instance of handler so we need to call both init and

6845

6738

reset here.

6846

6739

*/

6847

6740

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

6848

DBUG_RETURN(1);

6741

return(1);

6849

6742

6850

6743

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

6851

6744

file->ref_length,

6852

6745

thd->variables.sortbuff_size);

6853

6746

if (!unique)

6854

DBUG_RETURN(1);

6747

return(1);

6855

6748

for (;;)

6856

6749

{

6857

6750

while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE)

6864

6757

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

6865

6758

cur_quick->file->ha_index_end();

6866

6759

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

6867

DBUG_RETURN(1);

6760

return(1);

6868

6761

}

6869

6762

6870

6763

if (result)

6872

6765

if (result != HA_ERR_END_OF_FILE)

6873

6766

{

6874

6767

cur_quick->range_end();

6875

DBUG_RETURN(result);

6768

return(result);

6876

6769

}

6877

6770

break;

6878

6771

}

6879

6772

6880

6773

if (thd->killed)

6881

DBUG_RETURN(1);

6774

return(1);

6882

6775

6883

6776

/* skip row if it will be retrieved by clustered PK scan */

6884

6777

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

6887

6780

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

6888

6781

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

6889

6782

if (result)

6890

DBUG_RETURN(1);

6783

return(1);

6891

6784

6892

6785

}

6893

6786

6894

DBUG_PRINT("info", ("ok"));

6895

6787

/* ok, all row ids are in Unique */

6896

6788

result= unique->get(head);

6897

6789

delete unique;

6900

6792

file->extra(HA_EXTRA_NO_KEYREAD);

6901

6793

/* start table scan */

6902

6794

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

6903

DBUG_RETURN(result);

6795

return(result);

6904

6796

}

6905

6797

6906

6798

6916

6808

int QUICK_INDEX_MERGE_SELECT::get_next()

6917

6809

{

6918

6810

int result;

6919

DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::get_next");

6920

6811

6921

6812

if (doing_pk_scan)

6922

DBUG_RETURN(pk_quick_select->get_next());

6813

return(pk_quick_select->get_next());

6923

6814

6924

6815

if ((result= read_record.read_record(&read_record)) == -1)

6925

6816

{

6931

6822

doing_pk_scan= true;

6932

6823

if ((result= pk_quick_select->init()) ||

6933

6824

(result= pk_quick_select->reset()))

6934

DBUG_RETURN(result);

6935

DBUG_RETURN(pk_quick_select->get_next());

6825

return(result);

6826

return(pk_quick_select->get_next());

6936

6827

}

6937

6828

}

6938

6829

6939

DBUG_RETURN(result);

6830

return(result);

6940

6831

}

6941

6832

6942

6833

6966

6857

QUICK_RANGE_SELECT* quick;

6967

6858

int error, cmp;

6968

6859

uint last_rowid_count=0;

6969

DBUG_ENTER("QUICK_ROR_INTERSECT_SELECT::get_next");

6970

6860

6971

6861

do

6972

6862

{

6979

6869

error= quick->get_next();

6980

6870

}

6981

6871

if (error)

6982

DBUG_RETURN(error);

6872

return(error);

6983

6873

6984

6874

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

6985

6875

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

6996

6886

do

6997

6887

{

6998

6888

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

6999

DBUG_RETURN(error);

6889

return(error);

7000

6890

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

7001

6891

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

7002

6892

} while (cmp < 0);

7010

6900

while (!cpk_quick->row_in_ranges())

7011

6901

{

7012

6902

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

7013

DBUG_RETURN(error);

6903

return(error);

7014

6904

}

7015

6905

}

7016

6906

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

7027

6917

if (need_to_fetch_row)

7028

6918

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

7029

6919

} while (error == HA_ERR_RECORD_DELETED);

7030

DBUG_RETURN(error);

6920

return(error);

7031

6921

}

7032

6922

7033

6923

7051

6941

int error, dup_row;

7052

6942

QUICK_SELECT_I *quick;

7053

6943

uchar *tmp;

7054

DBUG_ENTER("QUICK_ROR_UNION_SELECT::get_next");

7055

6944

7056

6945

do

7057

6946

{

7058

6947

do

7059

6948

{

7060

6949

if (!queue.elements)

7061

DBUG_RETURN(HA_ERR_END_OF_FILE);

6950

return(HA_ERR_END_OF_FILE);

7062

6951

/* Ok, we have a queue with >= 1 scans */

7063

6952

7064

6953

quick= (QUICK_SELECT_I*)queue_top(&queue);

7068

6957

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

7069

6958

{

7070

6959

if (error != HA_ERR_END_OF_FILE)

7071

DBUG_RETURN(error);

6960

return(error);

7072

6961

queue_remove(&queue, 0);

7073

6962

}

7074

6963

else

7093

6982

7094

6983

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

7095

6984

} while (error == HA_ERR_RECORD_DELETED);

7096

DBUG_RETURN(error);

6985

return(error);

7097

6986

}

7098

6987

7099

6988

7103

6992

uchar *mrange_buff;

7104

6993

int error;

7105

6994

HANDLER_BUFFER empty_buf;

7106

DBUG_ENTER("QUICK_RANGE_SELECT::reset");

7107

6995

last_range= NULL;

7108

6996

cur_range= (QUICK_RANGE**) ranges.buffer;

7109

6997

7110

6998

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

7111

DBUG_RETURN(error);

6999

return(error);

7112

7000

7113

7001

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

7114

7002

if (mrr_buf_size && !mrr_buf_desc)

7123

7011

buf_size/= 2;

7124

7012

}

7125

7013

if (!mrr_buf_desc)

7126

DBUG_RETURN(HA_ERR_OUT_OF_MEM);

7014

return(HA_ERR_OUT_OF_MEM);

7127

7015

7128

7016

/* Initialize the handler buffer. */

7129

7017

mrr_buf_desc->buffer= mrange_buff;

7140

7028

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

7141

7029

mrr_flags, mrr_buf_desc? mrr_buf_desc:

7142

7030

&empty_buf);

7143

DBUG_RETURN(error);

7031

return(error);

7144

7032

}

7145

7033

7146

7034

7293

7181

int QUICK_RANGE_SELECT::get_next()

7294

7182

{

7295

7183

char *dummy;

7296

DBUG_ENTER("QUICK_RANGE_SELECT::get_next");

7297

7184

if (in_ror_merged_scan)

7298

7185

{

7299

7186

/*

7310

7197

/* Restore bitmaps set on entry */

7311

7198

head->column_bitmaps_set_no_signal(save_read_set, save_write_set);

7312

7199

}

7313

DBUG_RETURN(result);

7200

return(result);

7314

7201

}

7315

7202

7316

7203

7346

7233

key_part_map keypart_map,

7347

7234

uchar *cur_prefix)

7348

7235

{

7349

DBUG_ENTER("QUICK_RANGE_SELECT::get_next_prefix");

7350

7351

7236

for (;;)

7352

7237

{

7353

7238

int result;

7355

7240

if (last_range)

7356

7241

{

7357

7242

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

7358

DBUG_ASSERT(cur_prefix != 0);

7243

assert(cur_prefix != 0);

7359

7244

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

7360

7245

HA_READ_AFTER_KEY);

7361

7246

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

7362

DBUG_RETURN(result);

7247

return(result);

7363

7248

}

7364

7249

7365

7250

uint count= ranges.elements - (cur_range - (QUICK_RANGE**) ranges.buffer);

7367

7252

{

7368

7253

/* Ranges have already been used up before. None is left for read. */

7369

7254

last_range= 0;

7370

DBUG_RETURN(HA_ERR_END_OF_FILE);

7255

return(HA_ERR_END_OF_FILE);

7371

7256

}

7372

7257

last_range= *(cur_range++);

7373

7258

7395

7280

last_range= 0; // Stop searching

7396

7281

7397

7282

if (result != HA_ERR_END_OF_FILE)

7398

DBUG_RETURN(result);

7283

return(result);

7399

7284

last_range= 0; // No matching rows; go to next range

7400

7285

}

7401

7286

}

7478

7363

7479

7364

int QUICK_SELECT_DESC::get_next()

7480

7365

{

7481

DBUG_ENTER("QUICK_SELECT_DESC::get_next");

7482

7483

7366

/* The max key is handled as follows:

7484

7367

* - if there is NO_MAX_RANGE, start at the end and move backwards

7485

7368

* - if it is an EQ_RANGE, which means that max key covers the entire

7503

7386

if (!result)

7504

7387

{

7505

7388

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

7506

DBUG_RETURN(0);

7389

return(0);

7507

7390

}

7508

7391

else if (result != HA_ERR_END_OF_FILE)

7509

DBUG_RETURN(result);

7392

return(result);

7510

7393

}

7511

7394

7512

7395

if (!(last_range= rev_it++))

7513

DBUG_RETURN(HA_ERR_END_OF_FILE); // All ranges used

7396

return(HA_ERR_END_OF_FILE); // All ranges used

7514

7397

7515

7398

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

7516

7399

{

7517

7400

int local_error;

7518

7401

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

7519

DBUG_RETURN(local_error); // Empty table

7402

return(local_error); // Empty table

7520

7403

if (cmp_prev(last_range) == 0)

7521

DBUG_RETURN(0);

7404

return(0);

7522

7405

last_range= 0; // No match; go to next range

7523

7406

continue;

7524

7407

}

7531

7414

}

7532

7415

else

7533

7416

{

7534

DBUG_ASSERT(last_range->flag & NEAR_MAX ||

7417

assert(last_range->flag & NEAR_MAX ||

7535

7418

range_reads_after_key(last_range));

7536

7419

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

7537

7420

last_range->max_keypart_map,

7542

7425

if (result)

7543

7426

{

7544

7427

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

7545

DBUG_RETURN(result);

7428

return(result);

7546

7429

last_range= 0; // Not found, to next range

7547

7430

continue;

7548

7431

}

7550

7433

{

7551

7434

if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))

7552

7435

last_range= 0; // Stop searching

7553

DBUG_RETURN(0); // Found key is in range

7436

return(0); // Found key is in range

7554

7437

}

7555

7438

last_range= 0; // To next range

7556

7439

}

7975

7858

ORDER *tmp_group;

7976

7859

Item *item;

7977

7860

Item_field *item_field;

7978

DBUG_ENTER("get_best_group_min_max");

7979

7861

7980

7862

/* Perform few 'cheap' tests whether this access method is applicable. */

7981

7863

if (!join)

7982

DBUG_RETURN(NULL); /* This is not a select statement. */

7864

return(NULL); /* This is not a select statement. */

7983

7865

if ((join->tables != 1) || /* The query must reference one table. */

7984

7866

((!join->group_list) && /* Neither GROUP BY nor a DISTINCT query. */

7985

7867

(!join->select_distinct)) ||

7986

7868

(join->select_lex->olap == ROLLUP_TYPE)) /* Check (B3) for ROLLUP */

7987

DBUG_RETURN(NULL);

7869

return(NULL);

7988

7870

if (table->s->keys == 0) /* There are no indexes to use. */

7989

DBUG_RETURN(NULL);

7871

return(NULL);

7990

7872

7991

7873

/* Analyze the query in more detail. */

7992

7874

List_iterator<Item> select_items_it(join->fields_list);

7993

7875

7994

7876

/* Check (SA1,SA4) and store the only MIN/MAX argument - the C attribute.*/

7995

7877

if (join->make_sum_func_list(join->all_fields, join->fields_list, 1))

7996

DBUG_RETURN(NULL);

7878

return(NULL);

7997

7879

if (join->sum_funcs[0])

7998

7880

{

7999

7881

Item_sum *min_max_item;

8005

7887

else if (min_max_item->sum_func() == Item_sum::MAX_FUNC)

8006

7888

have_max= true;

8007

7889

else

8008

DBUG_RETURN(NULL);

7890

return(NULL);

8009

7891

8010

7892

/* The argument of MIN/MAX. */

8011

7893

Item *expr= min_max_item->args[0]->real_item();

8014

7896

if (! min_max_arg_item)

8015

7897

min_max_arg_item= (Item_field*) expr;

8016

7898

else if (! min_max_arg_item->eq(expr, 1))

8017

DBUG_RETURN(NULL);

7899

return(NULL);

8018

7900

}

8019

7901

else

8020

DBUG_RETURN(NULL);

7902

return(NULL);

8021

7903

}

8022

7904

}

8023

7905

8027

7909

while ((item= select_items_it++))

8028

7910

{

8029

7911

if (item->type() != Item::FIELD_ITEM)

8030

DBUG_RETURN(NULL);

7912

return(NULL);

8031

7913

}

8032

7914

}

8033

7915

8035

7917

for (tmp_group= join->group_list; tmp_group; tmp_group= tmp_group->next)

8036

7918

{

8037

7919

if ((*tmp_group->item)->type() != Item::FIELD_ITEM)

8038

DBUG_RETURN(NULL);

7920

return(NULL);

8039

7921

}

8040

7922

8041

7923

/*

8118

8000

first Item? If so, then why? What is the array for?

8119

8001

*/

8120

8002

/* Above we already checked that all group items are fields. */

8121

DBUG_ASSERT((*tmp_group->item)->type() == Item::FIELD_ITEM);

8003

assert((*tmp_group->item)->type() == Item::FIELD_ITEM);

8122

8004

Item_field *group_field= (Item_field *) (*tmp_group->item);

8123

8005

if (group_field->field->eq(cur_part->field))

8124

8006

{

8174

8056

goto next_index;

8175

8057

}

8176

8058

else

8177

DBUG_ASSERT(false);

8059

assert(false);

8178

8060

8179

8061

/* Check (SA2). */

8180

8062

if (min_max_arg_item)

8304

8186

*/

8305

8187

if (cur_read_cost < best_read_cost - (DBL_EPSILON * cur_read_cost))

8306

8188

{

8307

DBUG_ASSERT(tree != 0 || cur_param_idx == MAX_KEY);

8189

assert(tree != 0 || cur_param_idx == MAX_KEY);

8308

8190

index_info= cur_index_info;

8309

8191

index= cur_index;

8310

8192

best_read_cost= cur_read_cost;

8321

8203

cur_group_prefix_len= 0;

8322

8204

}

8323

8205

if (!index_info) /* No usable index found. */

8324

DBUG_RETURN(NULL);

8206

return(NULL);

8325

8207

8326

8208

/* Check (SA3) for the where clause. */

8327

8209

if (join->conds && min_max_arg_item &&

8328

8210

!check_group_min_max_predicates(join->conds, min_max_arg_item,

8329

8211

(index_info->flags & HA_SPATIAL) ?

8330

8212

Field::itMBR : Field::itRAW))

8331

DBUG_RETURN(NULL);

8213

return(NULL);

8332

8214

8333

8215

/* The query passes all tests, so construct a new TRP object. */

8334

8216

read_plan= new (param->mem_root)

8342

8224

if (read_plan)

8343

8225

{

8344

8226

if (tree && read_plan->quick_prefix_records == 0)

8345

DBUG_RETURN(NULL);

8227

return(NULL);

8346

8228

8347

8229

read_plan->read_cost= best_read_cost;

8348

8230

read_plan->records= best_records;

8349

8350

DBUG_PRINT("info",

8351

("Returning group min/max plan: cost: %g, records: %lu",

8352

read_plan->read_cost, (ulong) read_plan->records));

8353

8231

}

8354

8232

8355

DBUG_RETURN(read_plan);

8233

return(read_plan);

8356

8234

}

8357

8235

8358

8236

8382

8260

check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item,

8383

8261

Field::imagetype image_type)

8384

8262

{

8385

DBUG_ENTER("check_group_min_max_predicates");

8386

DBUG_ASSERT(cond && min_max_arg_item);

8263

assert(cond && min_max_arg_item);

8387

8264

8388

8265

cond= cond->real_item();

8389

8266

Item::Type cond_type= cond->type();

8390

8267

if (cond_type == Item::COND_ITEM) /* 'AND' or 'OR' */

8391

8268

{

8392

DBUG_PRINT("info", ("Analyzing: %s", ((Item_func*) cond)->func_name()));

8393

8269

List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());

8394

8270

Item *and_or_arg;

8395

8271

while ((and_or_arg= li++))

8396

8272

{

8397

8273

if (!check_group_min_max_predicates(and_or_arg, min_max_arg_item,

8398

8274

image_type))

8399

DBUG_RETURN(false);

8275

return(false);

8400

8276

}

8401

DBUG_RETURN(true);

8277

return(true);

8402

8278

}

8403

8279

8404

8280

/*

8411

8287

so.

8412

8288

*/

8413

8289

if (cond_type == Item::SUBSELECT_ITEM)

8414

DBUG_RETURN(false);

8290

return(false);

8415

8291

8416

8292

/* We presume that at this point there are no other Items than functions. */

8417

DBUG_ASSERT(cond_type == Item::FUNC_ITEM);

8293

assert(cond_type == Item::FUNC_ITEM);

8418

8294

8419

8295

/* Test if cond references only group-by or non-group fields. */

8420

8296

Item_func *pred= (Item_func*) cond;

8421

8297

Item **arguments= pred->arguments();

8422

8298

Item *cur_arg;

8423

DBUG_PRINT("info", ("Analyzing: %s", pred->func_name()));

8424

8299

for (uint arg_idx= 0; arg_idx < pred->argument_count (); arg_idx++)

8425

8300

{

8426

8301

cur_arg= arguments[arg_idx]->real_item();

8427

DBUG_PRINT("info", ("cur_arg: %s", cur_arg->full_name()));

8428

8302

if (cur_arg->type() == Item::FIELD_ITEM)

8429

8303

{

8430

8304

if (min_max_arg_item->eq(cur_arg, 1))

8444

8318

pred_type != Item_func::ISNOTNULL_FUNC &&

8445

8319

pred_type != Item_func::EQ_FUNC &&

8446

8320

pred_type != Item_func::NE_FUNC)

8447

DBUG_RETURN(false);

8321

return(false);

8448

8322

8449

8323

/* Check that pred compares min_max_arg_item with a constant. */

8450

8324

Item *args[3];

8452

8326

bool inv;

8453

8327

/* Test if this is a comparison of a field and a constant. */

8454

8328

if (!simple_pred(pred, args, &inv))

8455

DBUG_RETURN(false);

8329

return(false);

8456

8330

8457

8331

/* Check for compatible string comparisons - similar to get_mm_leaf. */

8458

8332

if (args[0] && args[1] && !args[2] && // this is a binary function

8471

8345

*/

8472

8346

(args[1]->result_type() != STRING_RESULT &&

8473

8347

min_max_arg_item->field->cmp_type() != args[1]->result_type())))

8474

DBUG_RETURN(false);

8348

return(false);

8475

8349

}

8476

8350

}

8477

8351

else if (cur_arg->type() == Item::FUNC_ITEM)

8478

8352

{

8479

8353

if (!check_group_min_max_predicates(cur_arg, min_max_arg_item,

8480

8354

image_type))

8481

DBUG_RETURN(false);

8355

return(false);

8482

8356

}

8483

8357

else if (cur_arg->const_item())

8484

8358

{

8485

DBUG_RETURN(true);

8359

return(true);

8486

8360

}

8487

8361

else

8488

DBUG_RETURN(false);

8362

return(false);

8489

8363

}

8490

8364

8491

DBUG_RETURN(true);

8365

return(true);

8492

8366

}

8493

8367

8494

8368

8739

8613

double quick_prefix_selectivity;

8740

8614

double io_cost;

8741

8615

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

8742

DBUG_ENTER("cost_group_min_max");

8743

8616

8744

8617

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

8745

8618

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

8794

8667

8795

8668

*read_cost= io_cost + cpu_cost;

8796

8669

*records= num_groups;

8797

8798

DBUG_PRINT("info",

8799

("table rows: %lu keys/block: %u keys/group: %u result rows: %lu blocks: %u",

8800

(ulong)table_records, keys_per_block, keys_per_group,

8801

(ulong) *records, num_blocks));

8802

DBUG_VOID_RETURN;

8670

return;

8803

8671

}

8804

8672

8805

8673

8830

8698

MEM_ROOT *parent_alloc)

8831

8699

{

8832

8700

QUICK_GROUP_MIN_MAX_SELECT *quick;

8833

DBUG_ENTER("TRP_GROUP_MIN_MAX::make_quick");

8834

8701

8835

8702

quick= new QUICK_GROUP_MIN_MAX_SELECT(param->table,

8836

8703

param->thd->lex->current_select->join,

8840

8707

read_cost, records, key_infix_len,

8841

8708

key_infix, parent_alloc);

8842

8709

if (!quick)

8843

DBUG_RETURN(NULL);

8710

return(NULL);

8844

8711

8845

8712

if (quick->init())

8846

8713

{

8847

8714

delete quick;

8848

DBUG_RETURN(NULL);

8715

return(NULL);

8849

8716

}

8850

8717

8851

8718

if (range_tree)

8852

8719

{

8853

DBUG_ASSERT(quick_prefix_records > 0);

8720

assert(quick_prefix_records > 0);

8854

8721

if (quick_prefix_records == HA_POS_ERROR)

8855

8722

quick->quick_prefix_select= NULL; /* Can't construct a quick select. */

8856

8723

else

8884

8751

{

8885

8752

delete quick;

8886

8753

quick= NULL;

8887

DBUG_RETURN(NULL);

8754

return(NULL);

8888

8755

}

8889

8756

min_max_range= min_max_range->next;

8890

8757

}

8896

8763

quick->update_key_stat();

8897

8764

quick->adjust_prefix_ranges();

8898

8765

8899

DBUG_RETURN(quick);

8766

return(quick);

8900

8767

}

8901

8768

8902

8769

8958

8825

We can't have parent_alloc set as the init function can't handle this case

8959

8826

yet.

8960

8827

*/

8961

DBUG_ASSERT(!parent_alloc);

8828

assert(!parent_alloc);

8962

8829

if (!parent_alloc)

8963

8830

{

8964

8831

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

9065

8932

9066

8933

QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT()

9067

8934

{

9068

DBUG_ENTER("QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT");

9069

8935

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

9070

8936

file->ha_index_end();

9071

8937

if (min_max_arg_part)

9074

8940

delete min_functions_it;

9075

8941

delete max_functions_it;

9076

8942

delete quick_prefix_select;

9077

DBUG_VOID_RETURN;

8943

return;

9078

8944

}

9079

8945

9080

8946

9248

9114

int QUICK_GROUP_MIN_MAX_SELECT::reset(void)

9249

9115

{

9250

9116

int result;

9251

DBUG_ENTER("QUICK_GROUP_MIN_MAX_SELECT::reset");

9252

9117

9253

9118

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

9254

9119

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

9255

DBUG_RETURN(result);

9120

return(result);

9256

9121

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

9257

DBUG_RETURN(1);

9122

return(1);

9258

9123

result= file->index_last(record);

9259

9124

if (result == HA_ERR_END_OF_FILE)

9260

DBUG_RETURN(0);

9125

return(0);

9261

9126

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

9262

9127

key_copy(last_prefix, record, index_info, group_prefix_len);

9263

9128

9264

DBUG_RETURN(0);

9129

return(0);

9265

9130

}

9266

9131

9267

9132

9300

9165

int result;

9301

9166

int is_last_prefix= 0;

9302

9167

9303

DBUG_ENTER("QUICK_GROUP_MIN_MAX_SELECT::get_next");

9304

9305

9168

/*

9306

9169

Loop until a group is found that satisfies all query conditions or the last

9307

9170

group is reached.

9317

9180

{

9318

9181

is_last_prefix= key_cmp(index_info->key_part, last_prefix,

9319

9182

group_prefix_len);

9320

DBUG_ASSERT(is_last_prefix <= 0);

9183

assert(is_last_prefix <= 0);

9321

9184

}

9322

9185

else

9323

9186

{

9340

9203

if (max_res == 0)

9341

9204

update_max_result();

9342

9205

/* If a MIN was found, a MAX must have been found as well. */

9343

DBUG_ASSERT((have_max && !have_min) ||

9206

assert((have_max && !have_min) ||

9344

9207

(have_max && have_min && (max_res == 0)));

9345

9208

}

9346

9209

/*

9370

9233

else if (result == HA_ERR_KEY_NOT_FOUND)

9371

9234

result= HA_ERR_END_OF_FILE;

9372

9235

9373

DBUG_RETURN(result);

9236

return(result);

9374

9237

}

9375

9238

9376

9239

9400

9263

int QUICK_GROUP_MIN_MAX_SELECT::next_min()

9401

9264

{

9402

9265

int result= 0;

9403

DBUG_ENTER("QUICK_GROUP_MIN_MAX_SELECT::next_min");

9404

9266

9405

9267

/* Find the MIN key using the eventually extended group prefix. */

9406

9268

if (min_max_ranges.elements > 0)

9407

9269

{

9408

9270

if ((result= next_min_in_range()))

9409

DBUG_RETURN(result);

9271

return(result);

9410

9272

}

9411

9273

else

9412

9274

{

9416

9278

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

9417

9279

make_prev_keypart_map(real_key_parts),

9418

9280

HA_READ_KEY_EXACT)))

9419

DBUG_RETURN(result);

9281

return(result);

9420

9282

}

9421

9283

9422

9284

/*

9457

9319

If the MIN attribute is non-nullable, this->record already contains the

9458

9320

MIN key in the group, so just return.

9459

9321

*/

9460

DBUG_RETURN(result);

9322

return(result);

9461

9323

}

9462

9324

9463

9325

9481

9343

{

9482

9344

int result;

9483

9345

9484

DBUG_ENTER("QUICK_GROUP_MIN_MAX_SELECT::next_max");

9485

9486

9346

/* Get the last key in the (possibly extended) group. */

9487

9347

if (min_max_ranges.elements > 0)

9488

9348

result= next_max_in_range();

9490

9350

result= file->index_read_map(record, group_prefix,

9491

9351

make_prev_keypart_map(real_key_parts),

9492

9352

HA_READ_PREFIX_LAST);

9493

DBUG_RETURN(result);

9353

return(result);

9494

9354

}

9495

9355

9496

9356

9518

9378

int QUICK_GROUP_MIN_MAX_SELECT::next_prefix()

9519

9379

{

9520

9380

int result;

9521

DBUG_ENTER("QUICK_GROUP_MIN_MAX_SELECT::next_prefix");

9522

9381

9523

9382

if (quick_prefix_select)

9524

9383

{

9525

9384

uchar *cur_prefix= seen_first_key ? group_prefix : NULL;

9526

9385

if ((result= quick_prefix_select->get_next_prefix(group_prefix_len,

9527

9386

make_prev_keypart_map(group_key_parts), cur_prefix)))

9528

DBUG_RETURN(result);

9387

return(result);

9529

9388

seen_first_key= true;

9530

9389

}

9531

9390

else

9534

9393

{

9535

9394

result= file->index_first(record);

9536

9395

if (result)

9537

DBUG_RETURN(result);

9396

return(result);

9538

9397

seen_first_key= true;

9539

9398

}

9540

9399

else

9544

9403

make_prev_keypart_map(group_key_parts),

9545

9404

HA_READ_AFTER_KEY);

9546

9405

if (result)

9547

DBUG_RETURN(result);

9406

return(result);

9548

9407

}

9549

9408

}

9550

9409

9555

9414

memcpy(group_prefix + group_prefix_len,

9556

9415

key_infix, key_infix_len);

9557

9416

9558

DBUG_RETURN(0);

9417

return(0);

9559

9418

}

9560

9419

9561

9420

9588

9447

bool found_null= false;

9589

9448

int result= HA_ERR_KEY_NOT_FOUND;

9590

9449

9591

DBUG_ASSERT(min_max_ranges.elements > 0);

9450

assert(min_max_ranges.elements > 0);

9592

9451

9593

9452

for (uint range_idx= 0; range_idx < min_max_ranges.elements; range_idx++)

9594

9453

{ /* Search from the left-most range to the right. */

9674

9533

}

9675

9534

}

9676

9535

/* If we got to this point, the current key qualifies as MIN. */

9677

DBUG_ASSERT(result == 0);

9536

assert(result == 0);

9678

9537

break;

9679

9538

}

9680

9539

/*

9719

9578

QUICK_RANGE *cur_range;

9720

9579

int result;

9721

9580

9722

DBUG_ASSERT(min_max_ranges.elements > 0);

9581

assert(min_max_ranges.elements > 0);

9723

9582

9724

9583

for (uint range_idx= min_max_ranges.elements; range_idx > 0; range_idx--)

9725

9584

{ /* Search from the right-most range to the left. */

9885

9744

used_lengths->append(buf, length);

9886

9745

}

9887

9746

9888

9889

#ifndef DBUG_OFF

9890

9891

9747

static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,

9892

9748

const char *msg)

9893

9749

{

9894

9750

SEL_ARG **key,**end;

9895

9751

int idx;

9896

9752

char buff[1024];

9897

DBUG_ENTER("print_sel_tree");

9898

9753

9899

9754

String tmp(buff,sizeof(buff),&my_charset_bin);

9900

9755

tmp.length(0);

9913

9768

if (!tmp.length())

9914

9769

tmp.append(STRING_WITH_LEN("(empty)"));

9915

9770

9916

DBUG_PRINT("info", ("SEL_TREE: 0x%lx (%s) scans: %s", (long) tree, msg, tmp.ptr()));

9917

9918

DBUG_VOID_RETURN;

9771

return;

9919

9772

}

9920

9773

9921

9774

9923

9776

struct st_ror_scan_info **start,

9924

9777

struct st_ror_scan_info **end)

9925

9778

{

9926

DBUG_ENTER("print_ror_scans_arr");

9927

9928

9779

char buff[1024];

9929

9780

String tmp(buff,sizeof(buff),&my_charset_bin);

9930

9781

tmp.length(0);

9936

9787

}

9937

9788

if (!tmp.length())

9938

9789

tmp.append(STRING_WITH_LEN("(empty)"));

9939

DBUG_PRINT("info", ("ROR key scans (%s): %s", msg, tmp.ptr()));

9940

DBUG_VOID_RETURN;

9790

return;

9941

9791

}

9942

9792

9943

9793

9991

9841

char buf[MAX_KEY/8+1];

9992

9842

TABLE *table;

9993

9843

my_bitmap_map *old_read_map, *old_write_map;

9994

DBUG_ENTER("print_quick");

9995

9844

if (!quick)

9996

DBUG_VOID_RETURN;

9845

return;

9997

9846

DBUG_LOCK_FILE;

9998

9847

9999

9848

table= quick->head;

10006

9855

fprintf(DBUG_FILE,"other_keys: 0x%s:\n", needed_reg->print(buf));

10007

9856

10008

9857

DBUG_UNLOCK_FILE;

10009

DBUG_VOID_RETURN;

9858

return;

10010

9859

}

10011

9860

10012

9861

10136

9985

}

10137

9986

}

10138

9987

10139

10140

#endif /* NOT_USED */

10141

10142

9988

/*****************************************************************************

10143

9989

** Instantiate templates

10144

9990

*****************************************************************************/