~drizzle-trunk/drizzle/development : revision 77.1.66

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

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

767

#endif

768

765

769

766

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

770

767

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

1013

1010

int *error)

1014

1011

{

1015

1012

SQL_SELECT *select;

1016

DBUG_ENTER("make_select");

1017

1013

1018

1014

*error=0;

1019

1015

1020

1016

if (!conds && !allow_null_cond)

1021

DBUG_RETURN(0);

1017

return(0);

1022

1018

if (!(select= new SQL_SELECT))

1023

1019

{

1024

1020

*error= 1; // out of memory

1025

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

1021

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

1026

1022

}

1027

1023

select->read_tables=read_tables;

1028

1024

select->const_tables=const_tables;

1037

1033

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

1038

1034

head->sort.io_cache=0;

1039

1035

}

1040

DBUG_RETURN(select);

1036

return(select);

1041

1037

}

1042

1038

1043

1039

1067

1063

cleanup();

1068

1064

}

1069

1065

1070

#undef index // Fix for Unixware 7

1071

1072

1066

QUICK_SELECT_I::QUICK_SELECT_I()

1073

1067

:max_used_key_length(0),

1074

1068

used_key_parts(0)

1080

1074

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

1081

1075

{

1082

1076

my_bitmap_map *bitmap;

1083

DBUG_ENTER("QUICK_RANGE_SELECT::QUICK_RANGE_SELECT");

1084

1077

1085

1078

in_ror_merged_scan= 0;

1086

1079

sorted= 0;

1115

1108

}

1116

1109

else

1117

1110

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

1118

DBUG_VOID_RETURN;

1111

return;

1119

1112

}

1120

1113

1121

1114

1122

1115

int QUICK_RANGE_SELECT::init()

1123

1116

{

1124

DBUG_ENTER("QUICK_RANGE_SELECT::init");

1125

1126

1117

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

1127

1118

file->ha_index_or_rnd_end();

1128

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

1119

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

1129

1120

}

1130

1121

1131

1122

1138

1129

1139

1130

QUICK_RANGE_SELECT::~QUICK_RANGE_SELECT()

1140

1131

{

1141

DBUG_ENTER("QUICK_RANGE_SELECT::~QUICK_RANGE_SELECT");

1142

1132

if (!dont_free)

1143

1133

{

1144

1134

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

1152

1142

}

1153

1143

if (free_file)

1154

1144

{

1155

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

1156

free_file));

1157

1145

file->ha_external_lock(current_thd, F_UNLCK);

1158

1146

file->close();

1159

1147

delete file;

1165

1153

}

1166

1154

head->column_bitmaps_set(save_read_set, save_write_set);

1167

1155

x_free(mrr_buf_desc);

1168

DBUG_VOID_RETURN;

1156

return;

1169

1157

}

1170

1158

1171

1159

1173

1161

TABLE *table)

1174

1162

:pk_quick_select(NULL), thd(thd_param)

1175

1163

{

1176

DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT");

1177

1164

index= MAX_KEY;

1178

1165

head= table;

1179

1166

bzero(&read_record, sizeof(read_record));

1180

1167

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

1181

DBUG_VOID_RETURN;

1168

return;

1182

1169

}

1183

1170

1184

1171

int QUICK_INDEX_MERGE_SELECT::init()

1185

1172

{

1186

DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::init");

1187

DBUG_RETURN(0);

1173

return(0);

1188

1174

}

1189

1175

1190

1176

int QUICK_INDEX_MERGE_SELECT::reset()

1191

1177

{

1192

DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::reset");

1193

DBUG_RETURN(read_keys_and_merge());

1178

return(read_keys_and_merge());

1194

1179

}

1195

1180

1196

1181

bool

1212

1197

{

1213

1198

List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);

1214

1199

QUICK_RANGE_SELECT* quick;

1215

DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT");

1216

1200

quick_it.rewind();

1217

1201

while ((quick= quick_it++))

1218

1202

quick->file= NULL;

1219

1203

quick_selects.delete_elements();

1220

1204

delete pk_quick_select;

1221

1205

free_root(&alloc,MYF(0));

1222

DBUG_VOID_RETURN;

1206

return;

1223

1207

}

1224

1208

1225

1209

1254

1238

1255

1239

int QUICK_ROR_INTERSECT_SELECT::init()

1256

1240

{

1257

DBUG_ENTER("QUICK_ROR_INTERSECT_SELECT::init");

1258

1241

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

1259

DBUG_RETURN(!last_rowid);

1242

return(!last_rowid);

1260

1243

}

1261

1244

1262

1245

1286

1269

{

1287

1270

handler *save_file= file, *org_file;

1288

1271

THD *thd;

1289

DBUG_ENTER("QUICK_RANGE_SELECT::init_ror_merged_scan");

1290

1272

1291

1273

in_ror_merged_scan= 1;

1292

1274

if (reuse_handler)

1293

1275

{

1294

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

1295

1276

if (init() || reset())

1296

1277

{

1297

DBUG_RETURN(1);

1278

return(1);

1298

1279

}

1299

1280

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

1300

1281

goto end;

1304

1285

if (free_file)

1305

1286

{

1306

1287

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

1307

DBUG_RETURN(0);

1288

return(0);

1308

1289

}

1309

1290

1310

1291

thd= head->in_use;

1356

1337

bitmap_copy(&column_bitmap, head->read_set);

1357

1338

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

1358

1339

1359

DBUG_RETURN(0);

1340

return(0);

1360

1341

1361

1342

failure:

1362

1343

head->column_bitmaps_set(save_read_set, save_write_set);

1363

1344

delete file;

1364

1345

file= save_file;

1365

DBUG_RETURN(1);

1346

return(1);

1366

1347

}

1367

1348

1368

1349

1380

1361

{

1381

1362

List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);

1382

1363

QUICK_RANGE_SELECT* quick;

1383

DBUG_ENTER("QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan");

1384

1364

1385

1365

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

1386

DBUG_ASSERT(!need_to_fetch_row || reuse_handler);

1366

assert(!need_to_fetch_row || reuse_handler);

1387

1367

if (!need_to_fetch_row && reuse_handler)

1388

1368

{

1389

1369

quick= quick_it++;

1392

1372

selects.

1393

1373

*/

1394

1374

if (quick->init_ror_merged_scan(true))

1395

DBUG_RETURN(1);

1375

return(1);

1396

1376

quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);

1397

1377

}

1398

1378

while ((quick= quick_it++))

1399

1379

{

1400

1380

if (quick->init_ror_merged_scan(false))

1401

DBUG_RETURN(1);

1381

return(1);

1402

1382

quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);

1403

1383

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

1404

1384

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

1406

1386

1407

1387

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

1408

1388

{

1409

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

1410

DBUG_RETURN(1);

1389

return(1);

1411

1390

}

1412

DBUG_RETURN(0);

1391

return(0);

1413

1392

}

1414

1393

1415

1394

1424

1403

1425

1404

int QUICK_ROR_INTERSECT_SELECT::reset()

1426

1405

{

1427

DBUG_ENTER("QUICK_ROR_INTERSECT_SELECT::reset");

1428

1406

if (!scans_inited && init_ror_merged_scan(true))

1429

DBUG_RETURN(1);

1407

return(1);

1430

1408

scans_inited= true;

1431

1409

List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);

1432

1410

QUICK_RANGE_SELECT *quick;

1433

1411

while ((quick= it++))

1434

1412

quick->reset();

1435

DBUG_RETURN(0);

1413

return(0);

1436

1414

}

1437

1415

1438

1416

1459

1437

1460

1438

QUICK_ROR_INTERSECT_SELECT::~QUICK_ROR_INTERSECT_SELECT()

1461

1439

{

1462

DBUG_ENTER("QUICK_ROR_INTERSECT_SELECT::~QUICK_ROR_INTERSECT_SELECT");

1463

1440

quick_selects.delete_elements();

1464

1441

delete cpk_quick;

1465

1442

free_root(&alloc,MYF(0));

1466

1443

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

1467

1444

head->file->ha_rnd_end();

1468

DBUG_VOID_RETURN;

1445

return;

1469

1446

}

1470

1447

1471

1448

1494

1471

1495

1472

int QUICK_ROR_UNION_SELECT::init()

1496

1473

{

1497

DBUG_ENTER("QUICK_ROR_UNION_SELECT::init");

1498

1474

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

1499

1475

false , QUICK_ROR_UNION_SELECT::queue_cmp,

1500

1476

(void*) this))

1501

1477

{

1502

1478

bzero(&queue, sizeof(QUEUE));

1503

DBUG_RETURN(1);

1479

return(1);

1504

1480

}

1505

1481

1506

1482

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

1507

DBUG_RETURN(1);

1483

return(1);

1508

1484

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

1509

DBUG_RETURN(0);

1485

return(0);

1510

1486

}

1511

1487

1512

1488

1543

1519

{

1544

1520

QUICK_SELECT_I *quick;

1545

1521

int error;

1546

DBUG_ENTER("QUICK_ROR_UNION_SELECT::reset");

1547

1522

have_prev_rowid= false;

1548

1523

if (!scans_inited)

1549

1524

{

1551

1526

while ((quick= it++))

1552

1527

{

1553

1528

if (quick->init_ror_merged_scan(false))

1554

DBUG_RETURN(1);

1529

return(1);

1555

1530

}

1556

1531

scans_inited= true;

1557

1532

}

1564

1539

while ((quick= it++))

1565

1540

{

1566

1541

if (quick->reset())

1567

DBUG_RETURN(1);

1542

return(1);

1568

1543

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

1569

1544

{

1570

1545

if (error == HA_ERR_END_OF_FILE)

1571

1546

continue;

1572

DBUG_RETURN(error);

1547

return(error);

1573

1548

}

1574

1549

quick->save_last_pos();

1575

1550

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

1577

1552

1578

1553

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

1579

1554

{

1580

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

1581

DBUG_RETURN(1);

1555

return(1);

1582

1556

}

1583

1557

1584

DBUG_RETURN(0);

1558

return(0);

1585

1559

}

1586

1560

1587

1561

1593

1567

1594

1568

QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT()

1595

1569

{

1596

DBUG_ENTER("QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT");

1597

1570

delete_queue(&queue);

1598

1571

quick_selects.delete_elements();

1599

1572

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

1600

1573

head->file->ha_rnd_end();

1601

1574

free_root(&alloc,MYF(0));

1602

DBUG_VOID_RETURN;

1575

return;

1603

1576

}

1604

1577

1605

1578

1952

1925

bool retrieve_full_rows __attribute__((__unused__)),

1953

1926

MEM_ROOT *parent_alloc)

1954

1927

{

1955

DBUG_ENTER("TRP_RANGE::make_quick");

1956

1928

QUICK_RANGE_SELECT *quick;

1957

1929

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

1958

1930

parent_alloc)))

1960

1932

quick->records= records;

1961

1933

quick->read_time= read_cost;

1962

1934

}

1963

DBUG_RETURN(quick);

1935

return(quick);

1964

1936

}

1965

1937

};

1966

1938

2185

2157

{

2186

2158

uint idx;

2187

2159

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

2160

delete quick;

2194

2161

quick=0;

2195

2162

needed_reg.clear_all();

2196

2163

quick_keys.clear_all();

2197

2164

if (keys_to_use.is_clear_all())

2198

DBUG_RETURN(0);

2165

return(0);

2199

2166

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

2200

2167

if (!records)

2201

2168

records++; /* purecov: inspected */

2206

2173

if (limit < records)

2207

2174

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

2208

2175

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));

2176

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

2212

2177

2213

2178

keys_to_use.intersect(head->keys_in_use_for_query);

2214

2179

if (!keys_to_use.is_clear_all())

2220

2185

PARAM param;

2221

2186

2222

2187

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

2223

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

2188

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

2224

2189

2225

2190

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

2226

2191

param.thd= thd;

2247

2212

{

2248

2213

thd->no_errors=0;

2249

2214

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

2250

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

2215

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

2251

2216

}

2252

2217

key_parts= param.key_parts;

2253

2218

thd->mem_root= &alloc;

2291

2256

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

2292

2257

rows2double(records)) +

2293

2258

(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

2259

if (key_read_time < read_time)

2297

2260

read_time= key_read_time;

2298

2261

}

2388

2351

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

2389

2352

SEL_IMERGE *imerge;

2390

2353

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

2354

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

2394

2355

while ((imerge= it++))

2395

2356

{

2425

2386

thd->no_errors=0;

2426

2387

}

2427

2388

2428

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

2429

2430

2389

/*

2431

2390

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

2432

2391

limit rows if we are using a key

2433

2392

*/

2434

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

2393

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

2435

2394

}

2436

2395

2437

2396

/*

2522

2481

double roru_index_costs;

2523

2482

ha_rows roru_total_records;

2524

2483

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

2484

2528

2485

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

2529

2486

sizeof(TRP_RANGE*)*

2530

2487

n_child_scans)))

2531

DBUG_RETURN(NULL);

2488

return(NULL);

2532

2489

/*

2533

2490

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

2534

2491

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

2538

2495

ptree != imerge->trees_next;

2539

2496

ptree++, cur_child++)

2540

2497

{

2541

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

2542

"tree in SEL_IMERGE"););

2498

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

2543

2499

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

2544

2500

{

2545

2501

/*

2567

2523

non_cpk_scan_records += (*cur_child)->records;

2568

2524

}

2569

2525

2570

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

2571

2526

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

2572

2527

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

2573

2528

{

2575

2530

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

2576

2531

more expensive

2577

2532

*/

2578

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

2579

"full table scan, bailing out"));

2580

DBUG_RETURN(NULL);

2533

return(NULL);

2581

2534

}

2582

2535

if (all_scans_rors)

2583

2536

{

2602

2555

&sweep_cost);

2603

2556

imerge_cost += sweep_cost.total_cost();

2604

2557

}

2605

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

2606

imerge_cost));

2607

2558

if (imerge_cost > read_time)

2608

2559

goto build_ror_index_merge;

2609

2560

2616

2567

{

2617

2568

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

2618

2569

unique_calc_buff_size)))

2619

DBUG_RETURN(NULL);

2570

return(NULL);

2620

2571

param->imerge_cost_buff_size= unique_calc_buff_size;

2621

2572

}

2622

2573

2624

2575

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

2625

2576

param->table->file->ref_length,

2626

2577

param->thd->variables.sortbuff_size);

2627

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

2628

imerge_cost, read_time));

2629

2578

if (imerge_cost < read_time)

2630

2579

{

2631

2580

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

2642

2591

2643

2592

build_ror_index_merge:

2644

2593

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

2645

DBUG_RETURN(imerge_trp);

2594

return(imerge_trp);

2646

2595

2647

2596

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

2648

2597

bool dummy;

2650

2599

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

2651

2600

sizeof(TABLE_READ_PLAN*)*

2652

2601

n_child_scans)))

2653

DBUG_RETURN(imerge_trp);

2602

return(imerge_trp);

2654

2603

skip_to_ror_scan:

2655

2604

roru_index_costs= 0.0;

2656

2605

roru_total_records= 0;

2686

2635

if (prev_plan->is_ror)

2687

2636

*cur_roru_plan= prev_plan;

2688

2637

else

2689

DBUG_RETURN(imerge_trp);

2638

return(imerge_trp);

2690

2639

roru_index_costs += (*cur_roru_plan)->read_cost;

2691

2640

}

2692

2641

else

2726

2675

sweep_cost.total_cost();

2727

2676

}

2728

2677

2729

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

2730

n_child_scans));

2731

2678

TRP_ROR_UNION* roru;

2732

2679

if (roru_total_cost < read_time)

2733

2680

{

2737

2684

roru->last_ror= roru_read_plans + n_child_scans;

2738

2685

roru->read_cost= roru_total_cost;

2739

2686

roru->records= roru_total_records;

2740

DBUG_RETURN(roru);

2687

return(roru);

2741

2688

}

2742

2689

}

2743

DBUG_RETURN(imerge_trp);

2690

return(imerge_trp);

2744

2691

}

2745

2692

2746

2693

2789

2736

ROR_SCAN_INFO *ror_scan;

2790

2737

my_bitmap_map *bitmap_buf;

2791

2738

uint keynr;

2792

DBUG_ENTER("make_ror_scan");

2793

2739

2794

2740

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

2795

2741

sizeof(ROR_SCAN_INFO))))

2796

DBUG_RETURN(NULL);

2742

return(NULL);

2797

2743

2798

2744

ror_scan->idx= idx;

2799

2745

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

2804

2750

2805

2751

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

2806

2752

param->fields_bitmap_size)))

2807

DBUG_RETURN(NULL);

2753

return(NULL);

2808

2754

2809

2755

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

2810

2756

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

2811

DBUG_RETURN(NULL);

2757

return(NULL);

2812

2758

bitmap_clear_all(&ror_scan->covered_fields);

2813

2759

2814

2760

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

2822

2768

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

2823

2769

ror_scan->index_read_cost=

2824

2770

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

2825

DBUG_RETURN(ror_scan);

2771

return(ror_scan);

2826

2772

}

2827

2773

2828

2774

3058

3004

max_range.key= key_val;

3059

3005

max_range.flag= HA_READ_AFTER_KEY;

3060

3006

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

3061

DBUG_ENTER("ror_scan_selectivity");

3062

3007

3063

3008

for (sel_arg= scan->sel_arg; sel_arg;

3064

3009

sel_arg= sel_arg->next_key_part)

3065

3010

{

3066

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

3067

3011

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

3068

3012

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

3069

3013

if (cur_covered != prev_covered)

3092

3036

{

3093

3037

/* uncovered -> covered */

3094

3038

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

3095

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

3096

3039

selectivity_mult *= tmp;

3097

3040

prev_records= HA_POS_ERROR;

3098

3041

}

3108

3051

{

3109

3052

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

3110

3053

rows2double(prev_records);

3111

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

3112

3054

selectivity_mult *= tmp;

3113

3055

}

3114

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

3115

DBUG_RETURN(selectivity_mult);

3056

return(selectivity_mult);

3116

3057

}

3117

3058

3118

3059

3157

3098

{

3158

3099

double selectivity_mult= 1.0;

3159

3100

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

3101

selectivity_mult = ror_scan_selectivity(info, ror_scan);

3167

3102

if (selectivity_mult == 1.0)

3168

3103

{

3169

3104

/* 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);

3105

return(false);

3172

3106

}

3173

3107

3174

3108

info->out_rows *= selectivity_mult;

3191

3125

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

3192

3126

&info->covered_fields))

3193

3127

{

3194

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

3195

3128

info->is_covering= true;

3196

3129

}

3197

3130

}

3198

3131

3199

3132

info->total_cost= info->index_scan_costs;

3200

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

3201

3133

if (!info->is_covering)

3202

3134

{

3203

3135

COST_VECT sweep_cost;

3206

3138

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

3207

3139

is_interrupted, &sweep_cost);

3208

3140

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

3209

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

3210

3141

}

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);

3142

return(true);

3215

3143

}

3216

3144

3217

3145

3286

3214

{

3287

3215

uint idx;

3288

3216

double min_cost= DBL_MAX;

3289

DBUG_ENTER("get_best_ror_intersect");

3290

3217

3291

3218

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

3292

DBUG_RETURN(NULL);

3219

return(NULL);

3293

3220

3294

3221

/*

3295

3222

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

3324

3251

}

3325

3252

3326

3253

tree->ror_scans_end= cur_ror_scan;

3327

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

3254

print_ror_scans_arr(param->table, "original",

3328

3255

tree->ror_scans,

3329

tree->ror_scans_end););

3256

tree->ror_scans_end);

3330

3257

/*

3331

3258

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

3332

3259

ROR_SCAN_INFO's.

3334

3261

*/

3335

3262

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

3336

3263

(qsort_cmp)cmp_ror_scan_info);

3337

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

3264

print_ror_scans_arr(param->table, "ordered",

3338

3265

tree->ror_scans,

3339

tree->ror_scans_end););

3266

tree->ror_scans_end);

3340

3267

3341

3268

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

3342

3269

ROR_SCAN_INFO **intersect_scans_end;

3378

3305

3379

3306

if (intersect_scans_best == intersect_scans)

3380

3307

{

3381

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

3382

DBUG_RETURN(NULL);

3308

return(NULL);

3383

3309

}

3384

3310

3385

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

3311

print_ror_scans_arr(param->table,

3386

3312

"best ROR-intersection",

3387

3313

intersect_scans,

3388

intersect_scans_best););

3314

intersect_scans_best);

3389

3315

3390

3316

*are_all_covering= intersect->is_covering;

3391

3317

uint best_num= intersect_scans_best - intersect_scans;

3411

3337

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

3412

3338

{

3413

3339

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

3414

DBUG_RETURN(trp);

3340

return(trp);

3415

3341

if (!(trp->first_scan=

3416

3342

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

3417

3343

sizeof(ROR_SCAN_INFO*)*best_num)))

3418

DBUG_RETURN(NULL);

3344

return(NULL);

3419

3345

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

3420

3346

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

3421

3347

trp->is_covering= intersect_best->is_covering;

3428

3354

trp->records= best_rows;

3429

3355

trp->index_scan_costs= intersect_best->index_scan_costs;

3430

3356

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

3357

}

3435

DBUG_RETURN(trp);

3358

return(trp);

3436

3359

}

3437

3360

3438

3361

3476

3399

{

3477

3400

ROR_SCAN_INFO **ror_scan_mark;

3478

3401

ROR_SCAN_INFO **ror_scans_end= tree->ror_scans_end;

3479

DBUG_ENTER("get_best_covering_ror_intersect");

3480

3402

3481

3403

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

3482

3404

(*scan)->key_components=

3497

3419

if (!covered_fields->bitmap ||

3498

3420

bitmap_init(covered_fields, covered_fields->bitmap,

3499

3421

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

3500

DBUG_RETURN(0);

3422

return(0);

3501

3423

bitmap_clear_all(covered_fields);

3502

3424

3503

3425

double total_cost= 0.0f;

3504

3426

ha_rows records=0;

3505

3427

bool all_covered;

3506

3428

3507

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

3508

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

3429

print_ror_scans_arr(param->table,

3509

3430

"building covering ROR-I",

3510

ror_scan_mark, ror_scans_end););

3431

ror_scan_mark, ror_scans_end);

3511

3432

do

3512

3433

{

3513

3434

/*

3528

3449

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

3529

3450

(qsort_cmp)cmp_ror_scan_info_covering);

3530

3451

3531

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

3452

print_ror_scans_arr(param->table,

3532

3453

"remaining scans",

3533

ror_scan_mark, ror_scans_end););

3454

ror_scan_mark, ror_scans_end);

3534

3455

3535

3456

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

3536

3457

total_cost += (*ror_scan_mark)->index_read_cost;

3537

3458

records += (*ror_scan_mark)->records;

3538

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

3539

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

3540

3459

if (total_cost > read_time)

3541

DBUG_RETURN(NULL);

3460

return(NULL);

3542

3461

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

3543

3462

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

3544

3463

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

3545

3464

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

3546

3465

3547

3466

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

3548

DBUG_RETURN(NULL);

3467

return(NULL);

3549

3468

3550

3469

/*

3551

3470

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

3552

3471

cost total_cost.

3553

3472

*/

3554

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

3555

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

3473

print_ror_scans_arr(param->table,

3556

3474

"creating covering ROR-intersect",

3557

tree->ror_scans, ror_scan_mark););

3475

tree->ror_scans, ror_scan_mark);

3558

3476

3559

3477

/* Add priority queue use cost. */

3560

3478

total_cost += rows2double(records)*

3561

3479

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

3562

3480

(TIME_FOR_COMPARE_ROWID * M_LN2);

3563

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

3564

3481

3565

3482

if (total_cost > read_time)

3566

DBUG_RETURN(NULL);

3483

return(NULL);

3567

3484

3568

3485

TRP_ROR_INTERSECT *trp;

3569

3486

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

3570

DBUG_RETURN(trp);

3487

return(trp);

3571

3488

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

3572

3489

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

3573

3490

sizeof(ROR_SCAN_INFO*)*

3574

3491

best_num)))

3575

DBUG_RETURN(NULL);

3492

return(NULL);

3576

3493

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

3577

3494

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

3578

3495

trp->is_covering= true;

3581

3498

trp->cpk_scan= NULL;

3582

3499

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

3583

3500

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);

3501

return(trp);

3588

3502

}

3589

3503

3590

3504

3624

3538

ha_rows best_records= 0;

3625

3539

uint best_mrr_flags= 0, best_buf_size= 0;

3626

3540

TRP_RANGE* read_plan= NULL;

3627

DBUG_ENTER("get_key_scans_params");

3628

3541

/*

3629

3542

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

3630

3543

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

3631

3544

is defined as "not null".

3632

3545

*/

3633

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

3634

"tree scans"););

3546

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

3635

3547

tree->ror_scans_map.clear_all();

3636

3548

tree->n_ror_scans= 0;

3637

3549

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

3670

3582

}

3671

3583

}

3672

3584

3673

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

3674

"ROR scans"););

3585

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

3675

3586

if (key_to_read)

3676

3587

{

3677

3588

idx= key_to_read - tree->keys;

3682

3593

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

3683

3594

read_plan->read_cost= read_time;

3684

3595

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

3596

}

3690

3597

}

3691

else

3692

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

3693

3598

3694

DBUG_RETURN(read_plan);

3599

return(read_plan);

3695

3600

}

3696

3601

3697

3602

3728

3633

{

3729

3634

QUICK_ROR_INTERSECT_SELECT *quick_intrsect;

3730

3635

QUICK_RANGE_SELECT *quick;

3731

DBUG_ENTER("TRP_ROR_INTERSECT::make_quick");

3732

3636

MEM_ROOT *alloc;

3733

3637

3734

3638

if ((quick_intrsect=

3737

3641

false),

3738

3642

parent_alloc)))

3739

3643

{

3740

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

3644

print_ror_scans_arr(param->table,

3741

3645

"creating ROR-intersect",

3742

first_scan, last_scan););

3646

first_scan, last_scan);

3743

3647

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

3744

3648

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

3745

3649

{

3750

3654

quick_intrsect->push_quick_back(quick))

3751

3655

{

3752

3656

delete quick_intrsect;

3753

DBUG_RETURN(NULL);

3657

return(NULL);

3754

3658

}

3755

3659

}

3756

3660

if (cpk_scan)

3761

3665

0, alloc)))

3762

3666

{

3763

3667

delete quick_intrsect;

3764

DBUG_RETURN(NULL);

3668

return(NULL);

3765

3669

}

3766

3670

quick->file= NULL;

3767

3671

quick_intrsect->cpk_quick= quick;

3769

3673

quick_intrsect->records= records;

3770

3674

quick_intrsect->read_time= read_cost;

3771

3675

}

3772

DBUG_RETURN(quick_intrsect);

3676

return(quick_intrsect);

3773

3677

}

3774

3678

3775

3679

3780

3684

QUICK_ROR_UNION_SELECT *quick_roru;

3781

3685

TABLE_READ_PLAN **scan;

3782

3686

QUICK_SELECT_I *quick;

3783

DBUG_ENTER("TRP_ROR_UNION::make_quick");

3784

3687

/*

3785

3688

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

3786

3689

rows, ignore retrieve_full_rows parameter.

3791

3694

{

3792

3695

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

3793

3696

quick_roru->push_quick_back(quick))

3794

DBUG_RETURN(NULL);

3697

return(NULL);

3795

3698

}

3796

3699

quick_roru->records= records;

3797

3700

quick_roru->read_time= read_cost;

3798

3701

}

3799

DBUG_RETURN(quick_roru);

3702

return(quick_roru);

3800

3703

}

3801

3704

3802

3705

3857

3760

Item_result cmp_type, bool inv)

3858

3761

{

3859

3762

SEL_TREE *tree= 0;

3860

DBUG_ENTER("get_func_mm_tree");

3861

3763

3862

3764

switch (cond_func->functype()) {

3863

3765

4072

3974

}

4073

3975

}

4074

3976

4075

DBUG_RETURN(tree);

3977

return(tree);

4076

3978

}

4077

3979

4078

3980

4156

4058

table_map ref_tables= 0;

4157

4059

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

4158

4060

param->current_table);

4159

DBUG_ENTER("get_full_func_mm_tree");

4160

4061

4161

4062

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

4162

4063

{

4185

4086

}

4186

4087

}

4187

4088

}

4188

DBUG_RETURN(ftree);

4089

return(ftree);

4189

4090

}

4190

4091

4191

4092

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

4197

4098

Item_field *field_item= 0;

4198

4099

bool inv= false;

4199

4100

Item *value= 0;

4200

DBUG_ENTER("get_mm_tree");

4201

4101

4202

4102

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

4203

4103

{

4212

4112

SEL_TREE *new_tree=get_mm_tree(param,item);

4213

4113

if (param->thd->is_fatal_error ||

4214

4114

param->alloced_sel_args > SEL_ARG::MAX_SEL_ARGS)

4215

DBUG_RETURN(0); // out of memory

4115

return(0); // out of memory

4216

4116

tree=tree_and(param,tree,new_tree);

4217

4117

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

4218

4118

break;

4228

4128

{

4229

4129

SEL_TREE *new_tree=get_mm_tree(param,item);

4230

4130

if (!new_tree)

4231

DBUG_RETURN(0); // out of memory

4131

return(0); // out of memory

4232

4132

tree=tree_or(param,tree,new_tree);

4233

4133

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

4234

4134

break;

4235

4135

}

4236

4136

}

4237

4137

}

4238

DBUG_RETURN(tree);

4138

return(tree);

4239

4139

}

4240

4140

/* Here when simple cond */

4241

4141

if (cond->const_item())

4251

4151

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

4252

4152

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

4253

4153

param->thd->mem_root= tmp_root;

4254

DBUG_RETURN(tree);

4154

return(tree);

4255

4155

}

4256

4156

4257

4157

table_map ref_tables= 0;

4262

4162

ref_tables= cond->used_tables();

4263

4163

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

4264

4164

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

4265

DBUG_RETURN(0);

4266

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

4165

return(0);

4166

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

4267

4167

}

4268

4168

4269

4169

Item_func *cond_func= (Item_func*) cond;

4271

4171

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

4272

4172

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

4273

4173

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

4274

DBUG_RETURN(0);

4174

return(0);

4275

4175

4276

4176

param->cond= cond;

4277

4177

4312

4212

{

4313

4213

Item_func_in *func=(Item_func_in*) cond_func;

4314

4214

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

4315

DBUG_RETURN(0);

4215

return(0);

4316

4216

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

4317

4217

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

4318

4218

break;

4321

4221

{

4322

4222

Item_equal *item_equal= (Item_equal *) cond;

4323

4223

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

4324

DBUG_RETURN(0);

4224

return(0);

4325

4225

Item_equal_iterator it(*item_equal);

4326

4226

ref_tables= value->used_tables();

4327

4227

while ((field_item= it++))

4336

4236

}

4337

4237

}

4338

4238

4339

DBUG_RETURN(ftree);

4239

return(ftree);

4340

4240

}

4341

4241

default:

4342

4242

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

4352

4252

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

4353

4253

}

4354

4254

else

4355

DBUG_RETURN(0);

4255

return(0);

4356

4256

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

4357

4257

}

4358

4258

4359

DBUG_RETURN(ftree);

4259

return(ftree);

4360

4260

}

4361

4261

4362

4262

4366

4266

Item *value,

4367

4267

Item_result cmp_type __attribute__((__unused__)))

4368

4268

{

4369

DBUG_ENTER("get_mm_parts");

4370

4269

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

4371

DBUG_RETURN(0);

4270

return(0);

4372

4271

4373

4272

KEY_PART *key_part = param->key_parts;

4374

4273

KEY_PART *end = param->key_parts_end;

4375

4274

SEL_TREE *tree=0;

4376

4275

if (value &&

4377

4276

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

4378

DBUG_RETURN(0);

4277

return(0);

4379

4278

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

4380

4279

{

4381

4280

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

4382

4281

{

4383

4282

SEL_ARG *sel_arg=0;

4384

4283

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

4385

DBUG_RETURN(0); // OOM

4284

return(0); // OOM

4386

4285

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

4387

4286

{

4388

4287

sel_arg=get_mm_leaf(param,cond_func,

4392

4291

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

4393

4292

{

4394

4293

tree->type=SEL_TREE::IMPOSSIBLE;

4395

DBUG_RETURN(tree);

4294

return(tree);

4396

4295

}

4397

4296

}

4398

4297

else

4399

4298

{

4400

4299

// This key may be used later

4401

4300

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

4402

DBUG_RETURN(0); // OOM

4301

return(0); // OOM

4403

4302

}

4404

4303

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

4405

4304

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

4407

4306

}

4408

4307

}

4409

4308

4410

DBUG_RETURN(tree);

4309

return(tree);

4411

4310

}

4412

4311

4413

4312

4422

4321

uchar *str;

4423

4322

ulong orig_sql_mode;

4424

4323

int err;

4425

DBUG_ENTER("get_mm_leaf");

4426

4324

4427

4325

/*

4428

4326

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

4719

4617

4720

4618

end:

4721

4619

param->thd->mem_root= alloc;

4722

DBUG_RETURN(tree);

4620

return(tree);

4723

4621

}

4724

4622

4725

4623

4778

4676

static SEL_TREE *

4779

4677

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

4780

4678

{

4781

DBUG_ENTER("tree_and");

4782

4679

if (!tree1)

4783

DBUG_RETURN(tree2);

4680

return(tree2);

4784

4681

if (!tree2)

4785

DBUG_RETURN(tree1);

4682

return(tree1);

4786

4683

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

4787

DBUG_RETURN(tree1);

4684

return(tree1);

4788

4685

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

4789

DBUG_RETURN(tree2);

4686

return(tree2);

4790

4687

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

4791

4688

{

4792

4689

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

4793

4690

tree2->type=SEL_TREE::KEY_SMALLER;

4794

DBUG_RETURN(tree2);

4691

return(tree2);

4795

4692

}

4796

4693

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

4797

4694

{

4798

4695

tree1->type=SEL_TREE::KEY_SMALLER;

4799

DBUG_RETURN(tree1);

4696

return(tree1);

4800

4697

}

4801

4698

key_map result_keys;

4802

4699

result_keys.clear_all();

4817

4714

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

4818

4715

{

4819

4716

tree1->type= SEL_TREE::IMPOSSIBLE;

4820

DBUG_RETURN(tree1);

4717

return(tree1);

4821

4718

}

4822

4719

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

4823

4720

#ifdef EXTRA_DEBUG

4831

4728

if (!result_keys.is_clear_all())

4832

4729

{

4833

4730

tree1->merges.empty();

4834

DBUG_RETURN(tree1);

4731

return(tree1);

4835

4732

}

4836

4733

4837

4734

/* ok, both trees are index_merge trees */

4838

4735

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

4839

DBUG_RETURN(tree1);

4736

return(tree1);

4840

4737

}

4841

4738

4842

4739

4850

4747

RANGE_OPT_PARAM* param)

4851

4748

{

4852

4749

key_map common_keys= tree1->keys_map;

4853

DBUG_ENTER("sel_trees_can_be_ored");

4854

4750

common_keys.intersect(tree2->keys_map);

4855

4751

4856

4752

if (common_keys.is_clear_all())

4857

DBUG_RETURN(false);

4753

return(false);

4858

4754

4859

4755

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

4860

4756

SEL_ARG **key1,**key2;

4866

4762

key2= tree2->keys + key_no;

4867

4763

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

4868

4764

{

4869

DBUG_RETURN(true);

4765

return(true);

4870

4766

}

4871

4767

}

4872

4768

}

4873

DBUG_RETURN(false);

4769

return(false);

4874

4770

}

4875

4771

4876

4772

4952

4848

static SEL_TREE *

4953

4849

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

4954

4850

{

4955

DBUG_ENTER("tree_or");

4956

4851

if (!tree1 || !tree2)

4957

DBUG_RETURN(0);

4852

return(0);

4958

4853

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

4959

DBUG_RETURN(tree2);

4854

return(tree2);

4960

4855

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

4961

DBUG_RETURN(tree1);

4856

return(tree1);

4962

4857

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

4963

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

4858

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

4964

4859

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

4965

DBUG_RETURN(tree2);

4860

return(tree2);

4966

4861

4967

4862

SEL_TREE *result= 0;

4968

4863

key_map result_keys;

4998

4893

bool no_trees= remove_nonrange_trees(param, tree1);

4999

4894

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

5000

4895

if (no_trees)

5001

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

4896

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

5002

4897

}

5003

4898

SEL_IMERGE *merge;

5004

4899

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

5024

4919

swap_variables(SEL_TREE*, tree1, tree2);

5025

4920

5026

4921

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

5027

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

4922

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

5028

4923

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

5029

4924

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

5030

4925

result= new SEL_TREE(SEL_TREE::ALWAYS);

5032

4927

result= tree1;

5033

4928

}

5034

4929

}

5035

DBUG_RETURN(result);

4930

return(result);

5036

4931

}

5037

4932

5038

4933

5594

5489

{

5595

5490

enum leaf_color remove_color;

5596

5491

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

5597

DBUG_ENTER("tree_delete");

5598

5492

5599

5493

root=this;

5600

5494

this->parent= 0;

5644

5538

}

5645

5539

5646

5540

if (root == &null_element)

5647

DBUG_RETURN(0); // Maybe root later

5541

return(0); // Maybe root later

5648

5542

if (remove_color == BLACK)

5649

5543

root=rb_delete_fixup(root,nod,fix_par);

5650

5544

test_rb_tree(root,root->parent);

5652

5546

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

5653

5547

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

5654

5548

root->maybe_flag=this->maybe_flag;

5655

DBUG_RETURN(root);

5549

return(root);

5656

5550

}

5657

5551

5658

5552

6280

6174

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

6281

6175

ha_rows rows;

6282

6176

uint keynr= param->real_keynr[idx];

6283

DBUG_ENTER("check_quick_select");

6284

6177

6285

6178

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

6286

6179

if (!tree)

6287

DBUG_RETURN(HA_POS_ERROR);

6180

return(HA_POS_ERROR);

6288

6181

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

6289

DBUG_RETURN(0L);

6182

return(0L);

6290

6183

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

6291

DBUG_RETURN(HA_POS_ERROR);

6184

return(HA_POS_ERROR);

6292

6185

6293

6186

seq.keyno= idx;

6294

6187

seq.real_keyno= keynr;

6347

6240

param->is_ror_scan= true;

6348

6241

}

6349

6242

6350

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

6351

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

6243

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

6352

6244

}

6353

6245

6354

6246

6456

6348

{

6457

6349

QUICK_RANGE_SELECT *quick;

6458

6350

bool create_err= false;

6459

DBUG_ENTER("get_quick_select");

6460

6351

6461

6352

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

6462

6353

param->real_keynr[idx],

6482

6373

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

6483

6374

}

6484

6375

}

6485

DBUG_RETURN(quick);

6376

return(quick);

6486

6377

}

6487

6378

6488

6379

6831

6722

int result;

6832

6723

Unique *unique;

6833

6724

handler *file= head->file;

6834

DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::read_keys_and_merge");

6835

6725

6836

6726

file->extra(HA_EXTRA_KEYREAD);

6837

6727

head->prepare_for_position();

6838

6728

6839

6729

cur_quick_it.rewind();

6840

6730

cur_quick= cur_quick_it++;

6841

DBUG_ASSERT(cur_quick != 0);

6731

assert(cur_quick != 0);

6842

6732

6843

6733

/*

6844

6734

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

6845

6735

reset here.

6846

6736

*/

6847

6737

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

6848

DBUG_RETURN(1);

6738

return(1);

6849

6739

6850

6740

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

6851

6741

file->ref_length,

6852

6742

thd->variables.sortbuff_size);

6853

6743

if (!unique)

6854

DBUG_RETURN(1);

6744

return(1);

6855

6745

for (;;)

6856

6746

{

6857

6747

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

6864

6754

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

6865

6755

cur_quick->file->ha_index_end();

6866

6756

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

6867

DBUG_RETURN(1);

6757

return(1);

6868

6758

}

6869

6759

6870

6760

if (result)

6872

6762

if (result != HA_ERR_END_OF_FILE)

6873

6763

{

6874

6764

cur_quick->range_end();

6875

DBUG_RETURN(result);

6765

return(result);

6876

6766

}

6877

6767

break;

6878

6768

}

6879

6769

6880

6770

if (thd->killed)

6881

DBUG_RETURN(1);

6771

return(1);

6882

6772

6883

6773

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

6884

6774

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

6887

6777

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

6888

6778

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

6889

6779

if (result)

6890

DBUG_RETURN(1);

6780

return(1);

6891

6781

6892

6782

}

6893

6783

6894

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

6895

6784

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

6896

6785

result= unique->get(head);

6897

6786

delete unique;

6900

6789

file->extra(HA_EXTRA_NO_KEYREAD);

6901

6790

/* start table scan */

6902

6791

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

6903

DBUG_RETURN(result);

6792

return(result);

6904

6793

}

6905

6794

6906

6795

6916

6805

int QUICK_INDEX_MERGE_SELECT::get_next()

6917

6806

{

6918

6807

int result;

6919

DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::get_next");

6920

6808

6921

6809

if (doing_pk_scan)

6922

DBUG_RETURN(pk_quick_select->get_next());

6810

return(pk_quick_select->get_next());

6923

6811

6924

6812

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

6925

6813

{

6931

6819

doing_pk_scan= true;

6932

6820

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

6933

6821

(result= pk_quick_select->reset()))

6934

DBUG_RETURN(result);

6935

DBUG_RETURN(pk_quick_select->get_next());

6822

return(result);

6823

return(pk_quick_select->get_next());

6936

6824

}

6937

6825

}

6938

6826

6939

DBUG_RETURN(result);

6827

return(result);

6940

6828

}

6941

6829

6942

6830

6966

6854

QUICK_RANGE_SELECT* quick;

6967

6855

int error, cmp;

6968

6856

uint last_rowid_count=0;

6969

DBUG_ENTER("QUICK_ROR_INTERSECT_SELECT::get_next");

6970

6857

6971

6858

do

6972

6859

{

6979

6866

error= quick->get_next();

6980

6867

}

6981

6868

if (error)

6982

DBUG_RETURN(error);

6869

return(error);

6983

6870

6984

6871

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

6985

6872

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

6996

6883

do

6997

6884

{

6998

6885

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

6999

DBUG_RETURN(error);

6886

return(error);

7000

6887

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

7001

6888

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

7002

6889

} while (cmp < 0);

7010

6897

while (!cpk_quick->row_in_ranges())

7011

6898

{

7012

6899

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

7013

DBUG_RETURN(error);

6900

return(error);

7014

6901

}

7015

6902

}

7016

6903

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

7027

6914

if (need_to_fetch_row)

7028

6915

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

7029

6916

} while (error == HA_ERR_RECORD_DELETED);

7030

DBUG_RETURN(error);

6917

return(error);

7031

6918

}

7032

6919

7033

6920

7051

6938

int error, dup_row;

7052

6939

QUICK_SELECT_I *quick;

7053

6940

uchar *tmp;

7054

DBUG_ENTER("QUICK_ROR_UNION_SELECT::get_next");

7055

6941

7056

6942

do

7057

6943

{

7058

6944

do

7059

6945

{

7060

6946

if (!queue.elements)

7061

DBUG_RETURN(HA_ERR_END_OF_FILE);

6947

return(HA_ERR_END_OF_FILE);

7062

6948

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

7063

6949

7064

6950

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

7068

6954

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

7069

6955

{

7070

6956

if (error != HA_ERR_END_OF_FILE)

7071

DBUG_RETURN(error);

6957

return(error);

7072

6958

queue_remove(&queue, 0);

7073

6959

}

7074

6960

else

7093

6979

7094

6980

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

7095

6981

} while (error == HA_ERR_RECORD_DELETED);

7096

DBUG_RETURN(error);

6982

return(error);

7097

6983

}

7098

6984

7099

6985

7103

6989

uchar *mrange_buff;

7104

6990

int error;

7105

6991

HANDLER_BUFFER empty_buf;

7106

DBUG_ENTER("QUICK_RANGE_SELECT::reset");

7107

6992

last_range= NULL;

7108

6993

cur_range= (QUICK_RANGE**) ranges.buffer;

7109

6994

7110

6995

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

7111

DBUG_RETURN(error);

6996

return(error);

7112

6997

7113

6998

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

7114

6999

if (mrr_buf_size && !mrr_buf_desc)

7123

7008

buf_size/= 2;

7124

7009

}

7125

7010

if (!mrr_buf_desc)

7126

DBUG_RETURN(HA_ERR_OUT_OF_MEM);

7011

return(HA_ERR_OUT_OF_MEM);

7127

7012

7128

7013

/* Initialize the handler buffer. */

7129

7014

mrr_buf_desc->buffer= mrange_buff;

7140

7025

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

7141

7026

mrr_flags, mrr_buf_desc? mrr_buf_desc:

7142

7027

&empty_buf);

7143

DBUG_RETURN(error);

7028

return(error);

7144

7029

}

7145

7030

7146

7031

7293

7178

int QUICK_RANGE_SELECT::get_next()

7294

7179

{

7295

7180

char *dummy;

7296

DBUG_ENTER("QUICK_RANGE_SELECT::get_next");

7297

7181

if (in_ror_merged_scan)

7298

7182

{

7299

7183

/*

7310

7194

/* Restore bitmaps set on entry */

7311

7195

head->column_bitmaps_set_no_signal(save_read_set, save_write_set);

7312

7196

}

7313

DBUG_RETURN(result);

7197

return(result);

7314

7198

}

7315

7199

7316

7200

7346

7230

key_part_map keypart_map,

7347

7231

uchar *cur_prefix)

7348

7232

{

7349

DBUG_ENTER("QUICK_RANGE_SELECT::get_next_prefix");

7350

7351

7233

for (;;)

7352

7234

{

7353

7235

int result;

7355

7237

if (last_range)

7356

7238

{

7357

7239

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

7358

DBUG_ASSERT(cur_prefix != 0);

7240

assert(cur_prefix != 0);

7359

7241

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

7360

7242

HA_READ_AFTER_KEY);

7361

7243

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

7362

DBUG_RETURN(result);

7244

return(result);

7363

7245

}

7364

7246

7365

7247

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

7367

7249

{

7368

7250

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

7369

7251

last_range= 0;

7370

DBUG_RETURN(HA_ERR_END_OF_FILE);

7252

return(HA_ERR_END_OF_FILE);

7371

7253

}

7372

7254

last_range= *(cur_range++);

7373

7255

7395

7277

last_range= 0; // Stop searching

7396

7278

7397

7279

if (result != HA_ERR_END_OF_FILE)

7398

DBUG_RETURN(result);

7280

return(result);

7399

7281

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

7400

7282

}

7401

7283

}

7478

7360

7479

7361

int QUICK_SELECT_DESC::get_next()

7480

7362

{

7481

DBUG_ENTER("QUICK_SELECT_DESC::get_next");

7482

7483

7363

/* The max key is handled as follows:

7484

7364

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

7485

7365

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

7503

7383

if (!result)

7504

7384

{

7505

7385

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

7506

DBUG_RETURN(0);

7386

return(0);

7507

7387

}

7508

7388

else if (result != HA_ERR_END_OF_FILE)

7509

DBUG_RETURN(result);

7389

return(result);

7510

7390

}

7511

7391

7512

7392

if (!(last_range= rev_it++))

7513

DBUG_RETURN(HA_ERR_END_OF_FILE); // All ranges used

7393

return(HA_ERR_END_OF_FILE); // All ranges used

7514

7394

7515

7395

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

7516

7396

{

7517

7397

int local_error;

7518

7398

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

7519

DBUG_RETURN(local_error); // Empty table

7399

return(local_error); // Empty table

7520

7400

if (cmp_prev(last_range) == 0)

7521

DBUG_RETURN(0);

7401

return(0);

7522

7402

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

7523

7403

continue;

7524

7404

}

7531

7411

}

7532

7412

else

7533

7413

{

7534

DBUG_ASSERT(last_range->flag & NEAR_MAX ||

7414

assert(last_range->flag & NEAR_MAX ||

7535

7415

range_reads_after_key(last_range));

7536

7416

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

7537

7417

last_range->max_keypart_map,

7542

7422

if (result)

7543

7423

{

7544

7424

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

7545

DBUG_RETURN(result);

7425

return(result);

7546

7426

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

7547

7427

continue;

7548

7428

}

7550

7430

{

7551

7431

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

7552

7432

last_range= 0; // Stop searching

7553

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

7433

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

7554

7434

}

7555

7435

last_range= 0; // To next range

7556

7436

}

7975

7855

ORDER *tmp_group;

7976

7856

Item *item;

7977

7857

Item_field *item_field;

7978

DBUG_ENTER("get_best_group_min_max");

7979

7858

7980

7859

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

7981

7860

if (!join)

7982

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

7861

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

7983

7862

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

7984

7863

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

7985

7864

(!join->select_distinct)) ||

7986

7865

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

7987

DBUG_RETURN(NULL);

7866

return(NULL);

7988

7867

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

7989

DBUG_RETURN(NULL);

7868

return(NULL);

7990

7869

7991

7870

/* Analyze the query in more detail. */

7992

7871

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

7993

7872

7994

7873

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

7995

7874

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

7996

DBUG_RETURN(NULL);

7875

return(NULL);

7997

7876

if (join->sum_funcs[0])

7998

7877

{

7999

7878

Item_sum *min_max_item;

8005

7884

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

8006

7885

have_max= true;

8007

7886

else

8008

DBUG_RETURN(NULL);

7887

return(NULL);

8009

7888

8010

7889

/* The argument of MIN/MAX. */

8011

7890

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

8014

7893

if (! min_max_arg_item)

8015

7894

min_max_arg_item= (Item_field*) expr;

8016

7895

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

8017

DBUG_RETURN(NULL);

7896

return(NULL);

8018

7897

}

8019

7898

else

8020

DBUG_RETURN(NULL);

7899

return(NULL);

8021

7900

}

8022

7901

}

8023

7902

8027

7906

while ((item= select_items_it++))

8028

7907

{

8029

7908

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

8030

DBUG_RETURN(NULL);

7909

return(NULL);

8031

7910

}

8032

7911

}

8033

7912

8035

7914

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

8036

7915

{

8037

7916

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

8038

DBUG_RETURN(NULL);

7917

return(NULL);

8039

7918

}

8040

7919

8041

7920

/*

8118

7997

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

8119

7998

*/

8120

7999

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

8121

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

8000

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

8122

8001

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

8123

8002

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

8124

8003

{

8174

8053

goto next_index;

8175

8054

}

8176

8055

else

8177

DBUG_ASSERT(false);

8056

assert(false);

8178

8057

8179

8058

/* Check (SA2). */

8180

8059

if (min_max_arg_item)

8304

8183

*/

8305

8184

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

8306

8185

{

8307

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

8186

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

8308

8187

index_info= cur_index_info;

8309

8188

index= cur_index;

8310

8189

best_read_cost= cur_read_cost;

8321

8200

cur_group_prefix_len= 0;

8322

8201

}

8323

8202

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

8324

DBUG_RETURN(NULL);

8203

return(NULL);

8325

8204

8326

8205

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

8327

8206

if (join->conds && min_max_arg_item &&

8328

8207

!check_group_min_max_predicates(join->conds, min_max_arg_item,

8329

8208

(index_info->flags & HA_SPATIAL) ?

8330

8209

Field::itMBR : Field::itRAW))

8331

DBUG_RETURN(NULL);

8210

return(NULL);

8332

8211

8333

8212

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

8334

8213

read_plan= new (param->mem_root)

8342

8221

if (read_plan)

8343

8222

{

8344

8223

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

8345

DBUG_RETURN(NULL);

8224

return(NULL);

8346

8225

8347

8226

read_plan->read_cost= best_read_cost;

8348

8227

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

8228

}

8354

8229

8355

DBUG_RETURN(read_plan);

8230

return(read_plan);

8356

8231

}

8357

8232

8358

8233

8382

8257

check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item,

8383

8258

Field::imagetype image_type)

8384

8259

{

8385

DBUG_ENTER("check_group_min_max_predicates");

8386

DBUG_ASSERT(cond && min_max_arg_item);

8260

assert(cond && min_max_arg_item);

8387

8261

8388

8262

cond= cond->real_item();

8389

8263

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

8390

8264

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

8391

8265

{

8392

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

8393

8266

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

8394

8267

Item *and_or_arg;

8395

8268

while ((and_or_arg= li++))

8396

8269

{

8397

8270

if (!check_group_min_max_predicates(and_or_arg, min_max_arg_item,

8398

8271

image_type))

8399

DBUG_RETURN(false);

8272

return(false);

8400

8273

}

8401

DBUG_RETURN(true);

8274

return(true);

8402

8275

}

8403

8276

8404

8277

/*

8411

8284

so.

8412

8285

*/

8413

8286

if (cond_type == Item::SUBSELECT_ITEM)

8414

DBUG_RETURN(false);

8287

return(false);

8415

8288

8416

8289

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

8417

DBUG_ASSERT(cond_type == Item::FUNC_ITEM);

8290

assert(cond_type == Item::FUNC_ITEM);

8418

8291

8419

8292

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

8420

8293

Item_func *pred= (Item_func*) cond;

8421

8294

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

8422

8295

Item *cur_arg;

8423

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

8424

8296

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

8425

8297

{

8426

8298

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

8427

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

8428

8299

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

8429

8300

{

8430

8301

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

8444

8315

pred_type != Item_func::ISNOTNULL_FUNC &&

8445

8316

pred_type != Item_func::EQ_FUNC &&

8446

8317

pred_type != Item_func::NE_FUNC)

8447

DBUG_RETURN(false);

8318

return(false);

8448

8319

8449

8320

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

8450

8321

Item *args[3];

8452

8323

bool inv;

8453

8324

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

8454

8325

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

8455

DBUG_RETURN(false);

8326

return(false);

8456

8327

8457

8328

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

8458

8329

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

8471

8342

*/

8472

8343

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

8473

8344

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

8474

DBUG_RETURN(false);

8345

return(false);

8475

8346

}

8476

8347

}

8477

8348

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

8478

8349

{

8479

8350

if (!check_group_min_max_predicates(cur_arg, min_max_arg_item,

8480

8351

image_type))

8481

DBUG_RETURN(false);

8352

return(false);

8482

8353

}

8483

8354

else if (cur_arg->const_item())

8484

8355

{

8485

DBUG_RETURN(true);

8356

return(true);

8486

8357

}

8487

8358

else

8488

DBUG_RETURN(false);

8359

return(false);

8489

8360

}

8490

8361

8491

DBUG_RETURN(true);

8362

return(true);

8492

8363

}

8493

8364

8494

8365

8739

8610

double quick_prefix_selectivity;

8740

8611

double io_cost;

8741

8612

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

8742

DBUG_ENTER("cost_group_min_max");

8743

8613

8744

8614

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

8745

8615

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

8794

8664

8795

8665

*read_cost= io_cost + cpu_cost;

8796

8666

*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;

8667

return;

8803

8668

}

8804

8669

8805

8670

8830

8695

MEM_ROOT *parent_alloc)

8831

8696

{

8832

8697

QUICK_GROUP_MIN_MAX_SELECT *quick;

8833

DBUG_ENTER("TRP_GROUP_MIN_MAX::make_quick");

8834

8698

8835

8699

quick= new QUICK_GROUP_MIN_MAX_SELECT(param->table,

8836

8700

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

8840

8704

read_cost, records, key_infix_len,

8841

8705

key_infix, parent_alloc);

8842

8706

if (!quick)

8843

DBUG_RETURN(NULL);

8707

return(NULL);

8844

8708

8845

8709

if (quick->init())

8846

8710

{

8847

8711

delete quick;

8848

DBUG_RETURN(NULL);

8712

return(NULL);

8849

8713

}

8850

8714

8851

8715

if (range_tree)

8852

8716

{

8853

DBUG_ASSERT(quick_prefix_records > 0);

8717

assert(quick_prefix_records > 0);

8854

8718

if (quick_prefix_records == HA_POS_ERROR)

8855

8719

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

8856

8720

else

8884

8748

{

8885

8749

delete quick;

8886

8750

quick= NULL;

8887

DBUG_RETURN(NULL);

8751

return(NULL);

8888

8752

}

8889

8753

min_max_range= min_max_range->next;

8890

8754

}

8896

8760

quick->update_key_stat();

8897

8761

quick->adjust_prefix_ranges();

8898

8762

8899

DBUG_RETURN(quick);

8763

return(quick);

8900

8764

}

8901

8765

8902

8766

8958

8822

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

8959

8823

yet.

8960

8824

*/

8961

DBUG_ASSERT(!parent_alloc);

8825

assert(!parent_alloc);

8962

8826

if (!parent_alloc)

8963

8827

{

8964

8828

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

9065

8929

9066

8930

QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT()

9067

8931

{

9068

DBUG_ENTER("QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT");

9069

8932

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

9070

8933

file->ha_index_end();

9071

8934

if (min_max_arg_part)

9074

8937

delete min_functions_it;

9075

8938

delete max_functions_it;

9076

8939

delete quick_prefix_select;

9077

DBUG_VOID_RETURN;

8940

return;

9078

8941

}

9079

8942

9080

8943

9248

9111

int QUICK_GROUP_MIN_MAX_SELECT::reset(void)

9249

9112

{

9250

9113

int result;

9251

DBUG_ENTER("QUICK_GROUP_MIN_MAX_SELECT::reset");

9252

9114

9253

9115

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

9254

9116

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

9255

DBUG_RETURN(result);

9117

return(result);

9256

9118

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

9257

DBUG_RETURN(1);

9119

return(1);

9258

9120

result= file->index_last(record);

9259

9121

if (result == HA_ERR_END_OF_FILE)

9260

DBUG_RETURN(0);

9122

return(0);

9261

9123

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

9262

9124

key_copy(last_prefix, record, index_info, group_prefix_len);

9263

9125

9264

DBUG_RETURN(0);

9126

return(0);

9265

9127

}

9266

9128

9267

9129

9300

9162

int result;

9301

9163

int is_last_prefix= 0;

9302

9164

9303

DBUG_ENTER("QUICK_GROUP_MIN_MAX_SELECT::get_next");

9304

9305

9165

/*

9306

9166

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

9307

9167

group is reached.

9317

9177

{

9318

9178

is_last_prefix= key_cmp(index_info->key_part, last_prefix,

9319

9179

group_prefix_len);

9320

DBUG_ASSERT(is_last_prefix <= 0);

9180

assert(is_last_prefix <= 0);

9321

9181

}

9322

9182

else

9323

9183

{

9340

9200

if (max_res == 0)

9341

9201

update_max_result();

9342

9202

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

9343

DBUG_ASSERT((have_max && !have_min) ||

9203

assert((have_max && !have_min) ||

9344

9204

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

9345

9205

}

9346

9206

/*

9370

9230

else if (result == HA_ERR_KEY_NOT_FOUND)

9371

9231

result= HA_ERR_END_OF_FILE;

9372

9232

9373

DBUG_RETURN(result);

9233

return(result);

9374

9234

}

9375

9235

9376

9236

9400

9260

int QUICK_GROUP_MIN_MAX_SELECT::next_min()

9401

9261

{

9402

9262

int result= 0;

9403

DBUG_ENTER("QUICK_GROUP_MIN_MAX_SELECT::next_min");

9404

9263

9405

9264

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

9406

9265

if (min_max_ranges.elements > 0)

9407

9266

{

9408

9267

if ((result= next_min_in_range()))

9409

DBUG_RETURN(result);

9268

return(result);

9410

9269

}

9411

9270

else

9412

9271

{

9416

9275

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

9417

9276

make_prev_keypart_map(real_key_parts),

9418

9277

HA_READ_KEY_EXACT)))

9419

DBUG_RETURN(result);

9278

return(result);

9420

9279

}

9421

9280

9422

9281

/*

9457

9316

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

9458

9317

MIN key in the group, so just return.

9459

9318

*/

9460

DBUG_RETURN(result);

9319

return(result);

9461

9320

}

9462

9321

9463

9322

9481

9340

{

9482

9341

int result;

9483

9342

9484

DBUG_ENTER("QUICK_GROUP_MIN_MAX_SELECT::next_max");

9485

9486

9343

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

9487

9344

if (min_max_ranges.elements > 0)

9488

9345

result= next_max_in_range();

9490

9347

result= file->index_read_map(record, group_prefix,

9491

9348

make_prev_keypart_map(real_key_parts),

9492

9349

HA_READ_PREFIX_LAST);

9493

DBUG_RETURN(result);

9350

return(result);

9494

9351

}

9495

9352

9496

9353

9518

9375

int QUICK_GROUP_MIN_MAX_SELECT::next_prefix()

9519

9376

{

9520

9377

int result;

9521

DBUG_ENTER("QUICK_GROUP_MIN_MAX_SELECT::next_prefix");

9522

9378

9523

9379

if (quick_prefix_select)

9524

9380

{

9525

9381

uchar *cur_prefix= seen_first_key ? group_prefix : NULL;

9526

9382

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

9527

9383

make_prev_keypart_map(group_key_parts), cur_prefix)))

9528

DBUG_RETURN(result);

9384

return(result);

9529

9385

seen_first_key= true;

9530

9386

}

9531

9387

else

9534

9390

{

9535

9391

result= file->index_first(record);

9536

9392

if (result)

9537

DBUG_RETURN(result);

9393

return(result);

9538

9394

seen_first_key= true;

9539

9395

}

9540

9396

else

9544

9400

make_prev_keypart_map(group_key_parts),

9545

9401

HA_READ_AFTER_KEY);

9546

9402

if (result)

9547

DBUG_RETURN(result);

9403

return(result);

9548

9404

}

9549

9405

}

9550

9406

9555

9411

memcpy(group_prefix + group_prefix_len,

9556

9412

key_infix, key_infix_len);

9557

9413

9558

DBUG_RETURN(0);

9414

return(0);

9559

9415

}

9560

9416

9561

9417

9588

9444

bool found_null= false;

9589

9445

int result= HA_ERR_KEY_NOT_FOUND;

9590

9446

9591

DBUG_ASSERT(min_max_ranges.elements > 0);

9447

assert(min_max_ranges.elements > 0);

9592

9448

9593

9449

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

9594

9450

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

9674

9530

}

9675

9531

}

9676

9532

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

9677

DBUG_ASSERT(result == 0);

9533

assert(result == 0);

9678

9534

break;

9679

9535

}

9680

9536

/*

9719

9575

QUICK_RANGE *cur_range;

9720

9576

int result;

9721

9577

9722

DBUG_ASSERT(min_max_ranges.elements > 0);

9578

assert(min_max_ranges.elements > 0);

9723

9579

9724

9580

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

9725

9581

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

9885

9741

used_lengths->append(buf, length);

9886

9742

}

9887

9743

9888

9889

#ifndef DBUG_OFF

9890

9891

9744

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

9892

9745

const char *msg)

9893

9746

{

9894

9747

SEL_ARG **key,**end;

9895

9748

int idx;

9896

9749

char buff[1024];

9897

DBUG_ENTER("print_sel_tree");

9898

9750

9899

9751

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

9900

9752

tmp.length(0);

9913

9765

if (!tmp.length())

9914

9766

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

9915

9767

9916

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

9917

9918

DBUG_VOID_RETURN;

9768

return;

9919

9769

}

9920

9770

9921

9771

9923

9773

struct st_ror_scan_info **start,

9924

9774

struct st_ror_scan_info **end)

9925

9775

{

9926

DBUG_ENTER("print_ror_scans_arr");

9927

9928

9776

char buff[1024];

9929

9777

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

9930

9778

tmp.length(0);

9936

9784

}

9937

9785

if (!tmp.length())

9938

9786

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

9939

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

9940

DBUG_VOID_RETURN;

9941

}

9942

9943

9944

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

9945

** Print a quick range for debugging

9946

** TODO:

9947

** This should be changed to use a String to store each row instead

9948

** of locking the DEBUG stream !

9949

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

9950

9951

static void

9952

print_key(KEY_PART *key_part, const uchar *key, uint used_length)

9953

{

9954

char buff[1024];

9955

const uchar *key_end= key+used_length;

9956

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

9957

uint store_length;

9958

TABLE *table= key_part->field->table;

9959

my_bitmap_map *old_write_set, *old_read_set;

9960

old_write_set= dbug_tmp_use_all_columns(table, table->write_set);

9961

old_read_set= dbug_tmp_use_all_columns(table, table->read_set);

9962

9963

for (; key < key_end; key+=store_length, key_part++)

9964

{

9965

Field *field= key_part->field;

9966

store_length= key_part->store_length;

9967

9968

if (field->real_maybe_null())

9969

{

9970

if (*key)

9971

{

9972

fwrite("NULL",sizeof(char),4,DBUG_FILE);

9973

continue;

9974

}

9975

key++; // Skip null byte

9976

store_length--;

9977

}

9978

field->set_key_image(key, key_part->length);

9979

field->val_str(&tmp);

9980

fwrite(tmp.ptr(),sizeof(char),tmp.length(),DBUG_FILE);

9981

if (key+store_length < key_end)

9982

fputc('/',DBUG_FILE);

9983

}

9984

dbug_tmp_restore_column_map(table->write_set, old_write_set);

9985

dbug_tmp_restore_column_map(table->read_set, old_read_set);

9986

}

9987

9988

9989

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

9990

{

9991

char buf[MAX_KEY/8+1];

9992

TABLE *table;

9993

my_bitmap_map *old_read_map, *old_write_map;

9994

DBUG_ENTER("print_quick");

9995

if (!quick)

9996

DBUG_VOID_RETURN;

9997

DBUG_LOCK_FILE;

9998

9999

table= quick->head;

10000

old_read_map= dbug_tmp_use_all_columns(table, table->read_set);

10001

old_write_map= dbug_tmp_use_all_columns(table, table->write_set);

10002

quick->dbug_dump(0, true);

10003

dbug_tmp_restore_column_map(table->read_set, old_read_map);

10004

dbug_tmp_restore_column_map(table->write_set, old_write_map);

10005

10006

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

10007

10008

DBUG_UNLOCK_FILE;

10009

DBUG_VOID_RETURN;

10010

}

10011

10012

10013

void QUICK_RANGE_SELECT::dbug_dump(int indent, bool verbose)

10014

{

10015

/* purecov: begin inspected */

10016

fprintf(DBUG_FILE, "%*squick range select, key %s, length: %d\n",

10017

indent, "", head->key_info[index].name, max_used_key_length);

10018

10019

if (verbose)

10020

{

10021

QUICK_RANGE *range;

10022

QUICK_RANGE **pr= (QUICK_RANGE**)ranges.buffer;

10023

QUICK_RANGE **end_range= pr + ranges.elements;

10024

for (; pr != end_range; ++pr)

10025

{

10026

fprintf(DBUG_FILE, "%*s", indent + 2, "");

10027

range= *pr;

10028

if (!(range->flag & NO_MIN_RANGE))

10029

{

10030

print_key(key_parts, range->min_key, range->min_length);

10031

if (range->flag & NEAR_MIN)

10032

fputs(" < ",DBUG_FILE);

10033

else

10034

fputs(" <= ",DBUG_FILE);

10035

}

10036

fputs("X",DBUG_FILE);

10037

10038

if (!(range->flag & NO_MAX_RANGE))

10039

{

10040

if (range->flag & NEAR_MAX)

10041

fputs(" < ",DBUG_FILE);

10042

else

10043

fputs(" <= ",DBUG_FILE);

10044

print_key(key_parts, range->max_key, range->max_length);

10045

}

10046

fputs("\n",DBUG_FILE);

10047

}

10048

}

10049

/* purecov: end */

10050

}

10051

10052

void QUICK_INDEX_MERGE_SELECT::dbug_dump(int indent, bool verbose)

10053

{

10054

List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);

10055

QUICK_RANGE_SELECT *quick;

10056

fprintf(DBUG_FILE, "%*squick index_merge select\n", indent, "");

10057

fprintf(DBUG_FILE, "%*smerged scans {\n", indent, "");

10058

while ((quick= it++))

10059

quick->dbug_dump(indent+2, verbose);

10060

if (pk_quick_select)

10061

{

10062

fprintf(DBUG_FILE, "%*sclustered PK quick:\n", indent, "");

10063

pk_quick_select->dbug_dump(indent+2, verbose);

10064

}

10065

fprintf(DBUG_FILE, "%*s}\n", indent, "");

10066

}

10067

10068

void QUICK_ROR_INTERSECT_SELECT::dbug_dump(int indent, bool verbose)

10069

{

10070

List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);

10071

QUICK_RANGE_SELECT *quick;

10072

fprintf(DBUG_FILE, "%*squick ROR-intersect select, %scovering\n",

10073

indent, "", need_to_fetch_row? "":"non-");

10074

fprintf(DBUG_FILE, "%*smerged scans {\n", indent, "");

10075

while ((quick= it++))

10076

quick->dbug_dump(indent+2, verbose);

10077

if (cpk_quick)

10078

{

10079

fprintf(DBUG_FILE, "%*sclustered PK quick:\n", indent, "");

10080

cpk_quick->dbug_dump(indent+2, verbose);

10081

}

10082

fprintf(DBUG_FILE, "%*s}\n", indent, "");

10083

}

10084

10085

void QUICK_ROR_UNION_SELECT::dbug_dump(int indent, bool verbose)

10086

{

10087

List_iterator_fast<QUICK_SELECT_I> it(quick_selects);

10088

QUICK_SELECT_I *quick;

10089

fprintf(DBUG_FILE, "%*squick ROR-union select\n", indent, "");

10090

fprintf(DBUG_FILE, "%*smerged scans {\n", indent, "");

10091

while ((quick= it++))

10092

quick->dbug_dump(indent+2, verbose);

10093

fprintf(DBUG_FILE, "%*s}\n", indent, "");

10094

}

10095

10096

10097

/*

10098

Print quick select information to DBUG_FILE.

10099

10100

SYNOPSIS

10101

QUICK_GROUP_MIN_MAX_SELECT::dbug_dump()

10102

indent Indentation offset

10103

verbose If true show more detailed output.

10104

10105

DESCRIPTION

10106

Print the contents of this quick select to DBUG_FILE. The method also

10107

calls dbug_dump() for the used quick select if any.

10108

10109

IMPLEMENTATION

10110

Caller is responsible for locking DBUG_FILE before this call and unlocking

10111

it afterwards.

10112

10113

RETURN

10114

None

10115

*/

10116

10117

void QUICK_GROUP_MIN_MAX_SELECT::dbug_dump(int indent, bool verbose)

10118

{

10119

fprintf(DBUG_FILE,

10120

"%*squick_group_min_max_select: index %s (%d), length: %d\n",

10121

indent, "", index_info->name, index, max_used_key_length);

10122

if (key_infix_len > 0)

10123

{

10124

fprintf(DBUG_FILE, "%*susing key_infix with length %d:\n",

10125

indent, "", key_infix_len);

10126

}

10127

if (quick_prefix_select)

10128

{

10129

fprintf(DBUG_FILE, "%*susing quick_range_select:\n", indent, "");

10130

quick_prefix_select->dbug_dump(indent + 2, verbose);

10131

}

10132

if (min_max_ranges.elements > 0)

10133

{

10134

fprintf(DBUG_FILE, "%*susing %d quick_ranges for MIN/MAX:\n",

10135

indent, "", min_max_ranges.elements);

10136

}

10137

}

10138

10139

10140

#endif /* NOT_USED */

9787

return;

9788

}

10141

9789

10142

9790

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

10143

9791

** Instantiate templates