~drizzle-trunk/drizzle/development

rollup.setNullItems((Item_null_result**) session->mem.alloc((sizeof(Item*) + sizeof(Item**) + sizeof(List<Item>) + ref_pointer_array_size) * send_group_parts));

2231

rollup.setFields((List<Item>*) (rollup.getNullItems() + send_group_parts));

2232

rollup.setRefPointerArrays((Item***) (rollup.getFields() + send_group_parts));

2233

Item** ref_array= (Item**) (rollup.getRefPointerArrays()+send_group_parts);

2234

2235

2236

Prepare space for field list for the different levels

2237

These will be filled up in rollup_make_fields()

2238

2239

for (uint32_t i= 0 ; i < send_group_parts ; i++)

2240

{

2241

rollup.getNullItems()[i]= new (session->mem) Item_null_result();

2242

List<Item> *rollup_fields= &rollup.getFields()[i];

2243

rollup_fields->clear();

2244

rollup.getRefPointerArrays()[i]= ref_array;

2245

ref_array+= all_fields.size();

2246

}

2247

2248

for (uint32_t i= 0 ; i < send_group_parts; i++)

2249

{

2250

for (uint32_t j= 0 ; j < fields_list.size() ; j++)

2251

{

2252

rollup.getFields()[i].push_back(rollup.getNullItems()[i]);

2253

}

2254

}

2255

2256

List<Item>::iterator it(all_fields.begin());

2257

while (Item* item= it++)

2258

{

2259

Order *group_tmp;

2260

bool found_in_group= 0;

2261

2262

for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)

2263

{

2264

if (*group_tmp->item == item)

2265

{

2266

item->maybe_null= 1;

2267

found_in_group= 1;

2268

if (item->const_item())

2269

{

2270

2271

For ROLLUP queries each constant item referenced in GROUP BY list

2272

is wrapped up into an Item_func object yielding the same value

2273

as the constant item. The objects of the wrapper class are never

2274

considered as constant items and besides they inherit all

2275

properties of the Item_result_field class.

2276

This wrapping allows us to ensure writing constant items

2277

into temporary tables whenever the result of the ROLLUP

2278

operation has to be written into a temporary table, e.g. when

2279

ROLLUP is used together with DISTINCT in the SELECT list.

2280

Usually when creating temporary tables for a intermidiate

2281

result we do not include fields for constant expressions.

2282

2283

Item* new_item= new Item_func_rollup_const(item);

2284

new_item->fix_fields(session, NULL);

2285

*it.ref()= new_item;

2286

for (Order *tmp= group_tmp; tmp; tmp= tmp->next)

2287

{

2288

if (*tmp->item == item)

2289

*tmp->item= new_item;

2290

}

2291

}

2292

}

2293

}

2294

if (item->type() == Item::FUNC_ITEM && !found_in_group)

2295

{

2296

bool changed= false;

2297

if (change_group_ref(session, (Item_func *) item, group_list, &changed))

2298

return 1;

2299

2300

We have to prevent creation of a field in a temporary table for

2301

an expression that contains GROUP BY attributes.

2302

Marking the expression item as 'with_sum_func' will ensure this.

2303

2304

if (changed)

2305

item->with_sum_func= 1;

2306

}

2307

}

2308

return 0;

2309

}

2310

2311

/**

2312

Fill up rollup structures with pointers to fields to use.

2313

2314

Creates copies of item_sum items for each sum level.

2315

2316

@param fields_arg List of all fields (hidden and real ones)

2317

@param sel_fields Pointer to selected fields

2318

@param func Store here a pointer to all fields

2319

2320

@retval

2321

0 if ok;

2322

In this case func is pointing to next not used element.

2323

@retval

2324

1 on error

2325

2326

bool Join::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields, Item_sum ***func)

2327

{

2328

List<Item>::iterator it(fields_arg.begin());

2329

Item *first_field= &sel_fields.front();

2330

uint32_t level;

2331

2332

2333

Create field lists for the different levels

2334

2335

The idea here is to have a separate field list for each rollup level to

2336

avoid all runtime checks of which columns should be NULL.

2337

2338

The list is stored in reverse order to get sum function in such an order

2339

in func that it makes it easy to reset them with init_sum_functions()

2340

2341

Assuming: SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP

2342

2343

rollup.fields[0] will contain list where a,b,c is NULL

2344

rollup.fields[1] will contain list where b,c is NULL

2345

...

2346

rollup.ref_pointer_array[#] points to fields for rollup.fields[#]

2347

...

2348

sum_funcs_end[0] points to all sum functions

2349

sum_funcs_end[1] points to all sum functions, except grand totals

2350

...

2351

2352

2353

for (level=0 ; level < send_group_parts ; level++)

2354

{

2355

uint32_t i;

2356

uint32_t pos= send_group_parts - level -1;

2357

bool real_fields= 0;

2358

Item *item;

2359

List<Item>::iterator new_it(rollup.getFields()[pos].begin());

2360

Item **ref_array_start= rollup.getRefPointerArrays()[pos];

2361

Order *start_group;

2362

2363

/* Point to first hidden field */

2364

Item **ref_array= ref_array_start + fields_arg.size()-1;

2365

2366

/* Remember where the sum functions ends for the previous level */

2367

sum_funcs_end[pos+1]= *func;

2368

2369

/* Find the start of the group for this level */

2370

for (i= 0, start_group= group_list ;i++ < pos ;start_group= start_group->next)

2371

{}

2372

2373

it= fields_arg.begin();

2374

while ((item= it++))

2375

{

2376

if (item == first_field)

2377

{

2378

real_fields= 1; // End of hidden fields

2379

ref_array= ref_array_start;

2380

}

2381

2382

if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&

2383

(!((Item_sum*) item)->depended_from() ||

2384

((Item_sum *)item)->depended_from() == select_lex))

2385

2386

{

2387

2388

This is a top level summary function that must be replaced with

2389

a sum function that is reset for this level.

2390

2391

NOTE: This code creates an object which is not that nice in a

2392

sub select. Fortunately it's not common to have rollup in

2393

sub selects.

2394

2395

item= item->copy_or_same(session);

2396

((Item_sum*) item)->make_unique();

2397

*(*func)= (Item_sum*) item;

2398

(*func)++;

2399

}

2400

else

2401

{

2402

/* Check if this is something that is part of this group by */

2403

Order *group_tmp;

2404

for (group_tmp= start_group, i= pos ;

2405

group_tmp ; group_tmp= group_tmp->next, i++)

2406

{

2407

if (*group_tmp->item == item)

2408

{

2409

2410

This is an element that is used by the GROUP BY and should be

2411

set to NULL in this level

2412

2413

Item_null_result *null_item= new (session->mem) Item_null_result();

2414

item->maybe_null= 1; // Value will be null sometimes

2415

null_item->result_field= item->get_tmp_table_field();

2416

item= null_item;

2417

break;

2418

}

2419

}

2420

}

2421

*ref_array= item;

2422

if (real_fields)

2423

{

2424

(void) new_it++; // Point to next item

2425

new_it.replace(item); // Replace previous

2426

ref_array++;

2427

}

2428

else

2429

ref_array--;

2430

}

2431

}

2432

sum_funcs_end[0]= *func; // Point to last function

2433

return 0;

2434

}

2435

2436

/**

2437

Send all rollup levels higher than the current one to the client.

2438

2439

@b SAMPLE

2440

@code

2441

SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP

2442

@endcode

2443

2444

@param idx Level we are on:

2445

- 0 = Total sum level

2446

- 1 = First group changed (a)

2447

- 2 = Second group changed (a,b)

2448

2449

@retval

2450

0 ok

2451

@retval

2452

1 If send_data_failed()

2453

2454

int Join::rollup_send_data(uint32_t idx)

2455

{

2456

for (uint32_t i= send_group_parts ; i-- > idx ; )

2457

{

2458

/* Get reference pointers to sum functions in place */

2459

memcpy(ref_pointer_array, rollup.getRefPointerArrays()[i], ref_pointer_array_size);

2460

2461

if ((!having || having->val_int()))

2462

{

2463

if (send_records < unit->select_limit_cnt && do_send_rows && result->send_data(rollup.getFields()[i]))

2464

{

2465

return 1;

2466

}

2467

send_records++;

2468

}

2469

}

2470

/* Restore ref_pointer_array */

2471

set_items_ref_array(current_ref_pointer_array);

2472

2473

return 0;

2474

}

2475

2476

/**

2477

Write all rollup levels higher than the current one to a temp table.

2478

2479

@b SAMPLE

2480

@code

2481

SELECT a, b, SUM(c) FROM t1 GROUP BY a,b WITH ROLLUP

2482

@endcode

2483

2484

@param idx Level we are on:

2485

- 0 = Total sum level

2486

- 1 = First group changed (a)

2487

- 2 = Second group changed (a,b)

2488

@param table reference to temp table

2489

2490

@retval

2491

0 ok

2492

@retval

2493

1 if write_data_failed()

2494

2495

int Join::rollup_write_data(uint32_t idx, Table *table_arg)

2496

{

2497

for (uint32_t i= send_group_parts ; i-- > idx ; )

2498

{

2499

/* Get reference pointers to sum functions in place */

2500

memcpy(ref_pointer_array, rollup.getRefPointerArrays()[i],

2501

ref_pointer_array_size);

2502

if ((!having || having->val_int()))

2503

{

2504

List<Item>::iterator it(rollup.getFields()[i].begin());

2505

while (Item* item= it++)

2506

{

2507

if (item->type() == Item::NULL_ITEM && item->is_result_field())

2508

item->save_in_result_field(1);

2509

}

2510

copy_sum_funcs(sum_funcs_end[i+1], sum_funcs_end[i]);

2511

if (table_arg->cursor->insertRecord(table_arg->getInsertRecord()))

2512

{

2513

my_error(ER_USE_SQL_BIG_RESULT, MYF(0));

2514

return 1;

2515

}

2516

}

2517

}

2518

/* Restore ref_pointer_array */

2519

set_items_ref_array(current_ref_pointer_array);

2520

2521

return 0;

2522

}

2523

2524

/**

2525

clear results if there are not rows found for group

2526

(end_send_group/end_write_group)

2527

2528

void Join::clear()

2529

{

2530

clear_tables(this);

2531

copy_fields(&tmp_table_param);

2532

2533

if (sum_funcs)

2534

{

2535

Item_sum *func, **func_ptr= sum_funcs;

2536

while ((func= *(func_ptr++)))

2537

func->clear();

2538

}

2539

}

2540

2541

/**

2542

change select_result object of Join.

2543

2544

@param res new select_result object

2545

2546

@retval

2547

false OK

2548

@retval

2549

true error

2550

2551

bool Join::change_result(select_result *res)

2552

{

2553

result= res;

2554

if (result->prepare(fields_list, select_lex->master_unit()))

2555

{

2556

return true;

2557

}

2558

return false;

2559

}

2560

2561

/**

2562

Cache constant expressions in WHERE, HAVING, ON conditions.

2563

2564

2565

void Join::cache_const_exprs()

2566

{

2567

bool cache_flag= false;

2568

bool *analyzer_arg= &cache_flag;

2569

2570

/* No need in cache if all tables are constant. */

2571

if (const_tables == tables)

2572

return;

2573

2574

if (conds)

2575

conds->compile(&Item::cache_const_expr_analyzer, (unsigned char **)&analyzer_arg,

2576

&Item::cache_const_expr_transformer, (unsigned char *)&cache_flag);

2577

cache_flag= false;

2578

if (having)

2579

having->compile(&Item::cache_const_expr_analyzer, (unsigned char **)&analyzer_arg,

2580

&Item::cache_const_expr_transformer, (unsigned char *)&cache_flag);

2581

2582

for (JoinTable *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)

2583

{

2584

if (*tab->on_expr_ref)

2585

{

2586

cache_flag= false;

2587

(*tab->on_expr_ref)->compile(&Item::cache_const_expr_analyzer,

2588

(unsigned char **)&analyzer_arg,

2589

&Item::cache_const_expr_transformer,

2590

(unsigned char *)&cache_flag);

2591

}

2592

}

2593

}

2594

2595

/**

2596

@brief

2597

2598

Process one record of the nested loop join.

2599

2600

@details

2601

2602

This function will evaluate parts of WHERE/ON clauses that are

2603

applicable to the partial record on hand and in case of success

2604

submit this record to the next level of the nested loop.

2605

2606

enum_nested_loop_state evaluate_join_record(Join *join, JoinTable *join_tab, int error)

2607

{

2608

bool not_used_in_distinct= join_tab->not_used_in_distinct;

2609

ha_rows found_records= join->found_records;

2610

COND *select_cond= join_tab->select_cond;

2611

2612

if (error > 0 || (join->session->is_error())) // Fatal error

2613

return NESTED_LOOP_ERROR;

2614

if (error < 0)

2615

return NESTED_LOOP_NO_MORE_ROWS;

2616

if (join->session->getKilled()) // Aborted by user

2617

{

2618

join->session->send_kill_message();

2619

return NESTED_LOOP_KILLED;

2620

}

2621

if (!select_cond || select_cond->val_int())

2622

{

2623

2624

There is no select condition or the attached pushed down

2625

condition is true => a match is found.

2626

2627

bool found= 1;

2628

while (join_tab->first_unmatched && found)

2629

{

2630

2631

The while condition is always false if join_tab is not

2632

the last inner join table of an outer join operation.

2633

2634

JoinTable *first_unmatched= join_tab->first_unmatched;

2635

2636

Mark that a match for current outer table is found.

2637

This activates push down conditional predicates attached

2638

to the all inner tables of the outer join.

2639

2640

first_unmatched->found= 1;

2641

for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)

2642

{

2643

if (tab->table->reginfo.not_exists_optimize)

2644

return NESTED_LOOP_NO_MORE_ROWS;

2645

/* Check all predicates that has just been activated. */

2646

2647

Actually all predicates non-guarded by first_unmatched->found

2648

will be re-evaluated again. It could be fixed, but, probably,

2649

it's not worth doing now.

2650

2651

if (tab->select_cond && !tab->select_cond->val_int())

2652

{

2653

/* The condition attached to table tab is false */

2654

if (tab == join_tab)

2655

found= 0;

2656

else

2657

{

2658

2659

Set a return point if rejected predicate is attached

2660

not to the last table of the current nest level.

2661

2662

join->return_tab= tab;

2663

return NESTED_LOOP_OK;

2664

}

2665

}

2666

}

2667

2668

Check whether join_tab is not the last inner table

2669

for another embedding outer join.

2670

2671

if ((first_unmatched= first_unmatched->first_upper) &&

2672

first_unmatched->last_inner != join_tab)

2673

first_unmatched= 0;

2674

join_tab->first_unmatched= first_unmatched;

2675

}

2676

2677

JoinTable *return_tab= join->return_tab;

2678

join_tab->found_match= true;

2679

2680

2681

It was not just a return to lower loop level when one

2682

of the newly activated predicates is evaluated as false

2683

(See above join->return_tab= tab).

2684

2685

join->examined_rows++;

2686

join->session->row_count++;

2687

2688

if (found)

2689

{

2690

enum enum_nested_loop_state rc;

2691

/* A match from join_tab is found for the current partial join. */

2692

rc= (*join_tab->next_select)(join, join_tab+1, 0);

2693

if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)

2694

return rc;

2695

if (return_tab < join->return_tab)

2696

join->return_tab= return_tab;

2697

2698

if (join->return_tab < join_tab)

2699

return NESTED_LOOP_OK;

2700

2701

Test if this was a SELECT DISTINCT query on a table that

2702

was not in the field list; In this case we can abort if

2703

we found a row, as no new rows can be added to the result.

2704

2705

if (not_used_in_distinct && found_records != join->found_records)

2706

return NESTED_LOOP_NO_MORE_ROWS;

2707

}

2708

else

2709

join_tab->read_record.cursor->unlock_row();

2710

}

2711

else

2712

{

2713

2714

The condition pushed down to the table join_tab rejects all rows

2715

with the beginning coinciding with the current partial join.

2716

2717

join->examined_rows++;

2718

join->session->row_count++;

2719

join_tab->read_record.cursor->unlock_row();

2720

}

2721

return NESTED_LOOP_OK;

2722

}

2723

2724

/**

2725

@details

2726

Construct a NULL complimented partial join record and feed it to the next

2727

level of the nested loop. This function is used in case we have

2728

an OUTER join and no matching record was found.

2729

2730

enum_nested_loop_state evaluate_null_complemented_join_record(Join *join, JoinTable *join_tab)

2731

{

2732

2733

The table join_tab is the first inner table of a outer join operation

2734

and no matches has been found for the current outer row.

2735

2736

JoinTable *last_inner_tab= join_tab->last_inner;

2737

/* Cache variables for faster loop */

2738

COND *select_cond;

2739

for ( ; join_tab <= last_inner_tab ; join_tab++)

2740

{

2741

/* Change the the values of guard predicate variables. */

2742

join_tab->found= 1;

2743

join_tab->not_null_compl= 0;

2744

/* The outer row is complemented by nulls for each inner tables */

2745

join_tab->table->restoreRecordAsDefault(); // Make empty record

2746

join_tab->table->mark_as_null_row(); // For group by without error

2747

select_cond= join_tab->select_cond;

2748

/* Check all attached conditions for inner table rows. */

2749

if (select_cond && !select_cond->val_int())

2750

return NESTED_LOOP_OK;

2751

}

2752

join_tab--;

2753

2754

The row complemented by nulls might be the first row

2755

of embedding outer joins.

2756

If so, perform the same actions as in the code

2757

for the first regular outer join row above.

2758

2759

for ( ; ; )

2760

{

2761

JoinTable *first_unmatched= join_tab->first_unmatched;

2762

if ((first_unmatched= first_unmatched->first_upper) && first_unmatched->last_inner != join_tab)

2763

first_unmatched= 0;

2764

join_tab->first_unmatched= first_unmatched;

2765

if (! first_unmatched)

2766

break;

2767

first_unmatched->found= 1;

2768

for (JoinTable *tab= first_unmatched; tab <= join_tab; tab++)

2769

{

2770

if (tab->select_cond && !tab->select_cond->val_int())

2771

{

2772

join->return_tab= tab;

2773

return NESTED_LOOP_OK;

2774

}

2775

}

2776

}

2777

2778

The row complemented by nulls satisfies all conditions

2779

attached to inner tables.

2780

Send the row complemented by nulls to be joined with the

2781

remaining tables.

2782

2783

return (*join_tab->next_select)(join, join_tab+1, 0);

2784

}

2785

2786

enum_nested_loop_state flush_cached_records(Join *join, JoinTable *join_tab, bool skip_last)

2787

{

2788

enum_nested_loop_state rc= NESTED_LOOP_OK;

2789

int error;

2790

ReadRecord *info;

2791

2792

join_tab->table->null_row= 0;

2793

if (!join_tab->cache.records)

2794

{

2795

return NESTED_LOOP_OK; /* Nothing to do */

2796

}

2797

2798

if (skip_last)

2799

{

2800

(void) join_tab->cache.store_record_in_cache(); // Must save this for later

2801

}

2802

2803

2804

if (join_tab->use_quick == 2)

2805

{

2806

delete join_tab->select->quick;

2807

join_tab->select->quick= 0;

2808

}

2809

/* read through all records */

2810

if ((error=join_init_read_record(join_tab)))

2811

{

2812

join_tab->cache.reset_cache_write();

2813

return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;

2814

}

2815

2816

for (JoinTable *tmp=join->join_tab; tmp != join_tab ; tmp++)

2817

{

2818

tmp->status=tmp->table->status;

2819

tmp->table->status=0;

2820

}

2821

2822

info= &join_tab->read_record;

2823

2824

{

2825

if (join->session->getKilled())

2826

{

2827

join->session->send_kill_message();

2828

return NESTED_LOOP_KILLED;

2829

}

2830

optimizer::SqlSelect *select= join_tab->select;

2831

if (rc == NESTED_LOOP_OK &&

2832

(!join_tab->cache.select || !join_tab->cache.select->skip_record()))

2833

{

2834

uint32_t i;

2835

join_tab->cache.reset_cache_read();

2836

for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)

2837

{

2838

join_tab->readCachedRecord();

2839

if (!select || !select->skip_record())

2840

{

2841

int res= 0;

2842

2843

rc= (join_tab->next_select)(join,join_tab+1,0);

2844

if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)

2845

{

2846

join_tab->cache.reset_cache_write();

2847

return rc;

2848

}

2849

2850

if (res == -1)

2851

return NESTED_LOOP_ERROR;

2852

}

2853

}

2854

}

2855

} while (!(error=info->read_record(info)));

2856

2857

if (skip_last)

2858

join_tab->readCachedRecord(); // Restore current record

2859

join_tab->cache.reset_cache_write();

2860

if (error > 0) // Fatal error

2861

return NESTED_LOOP_ERROR;

2862

for (JoinTable *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)

2863

tmp2->table->status=tmp2->status;

2864

return NESTED_LOOP_OK;

2865

}

2866

2867

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

2868

DESCRIPTION

2869

Functions that end one nested loop iteration. Different functions

2870

are used to support GROUP BY clause and to redirect records

2871

to a table (e.g. in case of SELECT into a temporary table) or to the

2872

network client.

2873

2874

RETURN VALUES

2875

NESTED_LOOP_OK - the record has been successfully handled

2876

NESTED_LOOP_ERROR - a fatal error (like table corruption)

2877

was detected

2878

NESTED_LOOP_KILLED - thread shutdown was requested while processing

2879

the record

2880

NESTED_LOOP_QUERY_LIMIT - the record has been successfully handled;

2881

additionally, the nested loop produced the

2882

number of rows specified in the LIMIT clause

2883

for the query

2884

NESTED_LOOP_CURSOR_LIMIT - the record has been successfully handled;

2885

additionally, there is a cursor and the nested

2886

loop algorithm produced the number of rows

2887

that is specified for current cursor fetch

2888

operation.

2889

All return values except NESTED_LOOP_OK abort the nested loop.

2890

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

2891

enum_nested_loop_state end_send(Join *join, JoinTable *, bool end_of_records)

2892

{

2893

if (! end_of_records)

2894

{

2895

int error;

2896

if (join->having && join->having->val_int() == 0)

2897

return NESTED_LOOP_OK; // Didn't match having

2898

error= 0;

2899

if (join->do_send_rows)

2900

error=join->result->send_data(*join->fields);

2901

if (error)

2902

return NESTED_LOOP_ERROR;

2903

if (++join->send_records >= join->unit->select_limit_cnt && join->do_send_rows)

2904

{

2905

if (join->select_options & OPTION_FOUND_ROWS)

2906

{

2907

JoinTable *jt=join->join_tab;

2908

if ((join->tables == 1) && !join->tmp_table && !join->sort_and_group

2909

&& !join->send_group_parts && !join->having && !jt->select_cond &&

2910

!(jt->select && jt->select->quick) &&

2911

(jt->table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&

2912

(jt->ref.key < 0))

2913

{

2914

/* Join over all rows in table; Return number of found rows */

2915

Table *table= jt->table;

2916

2917

join->select_options^= OPTION_FOUND_ROWS;

2918

if (table->sort.record_pointers ||

2919

(table->sort.io_cache && table->sort.io_cache->inited()))

2920

{

2921

/* Using filesort */

2922

join->send_records= table->sort.found_records;

2923

}

2924

else

2925

{

2926

table->cursor->info(HA_STATUS_VARIABLE);

2927

join->send_records= table->cursor->stats.records;

2928

}

2929

}

2930

else

2931

{

2932

join->do_send_rows= 0;

2933

if (join->unit->fake_select_lex)

2934

join->unit->fake_select_lex->select_limit= 0;

2935

return NESTED_LOOP_OK;

2936

}

2937

}

2938

return NESTED_LOOP_QUERY_LIMIT; // Abort nicely

2939

}

2940

else if (join->send_records >= join->fetch_limit)

2941

{

2942

2943

There is a server side cursor and all rows for

2944

this fetch request are sent.

2945

2946

return NESTED_LOOP_CURSOR_LIMIT;

2947

}

2948

}

2949

2950

return NESTED_LOOP_OK;

2951

}

2952

2953

enum_nested_loop_state end_write(Join *join, JoinTable *, bool end_of_records)

2954

{

2955

Table *table= join->tmp_table;

2956

2957

if (join->session->getKilled()) // Aborted by user

2958

{

2959

join->session->send_kill_message();

2960

return NESTED_LOOP_KILLED;

2961

}

2962

if (!end_of_records)

2963

{

2964

copy_fields(&join->tmp_table_param);

2965

if (copy_funcs(join->tmp_table_param.items_to_copy, join->session))

2966

return NESTED_LOOP_ERROR;

2967

if (!join->having || join->having->val_int())

2968

{

2969

int error;

2970

join->found_records++;

2971

if ((error=table->cursor->insertRecord(table->getInsertRecord())))

2972

{

2973

if (!table->cursor->is_fatal_error(error, HA_CHECK_DUP))

2974

{

2975

return NESTED_LOOP_OK;

2976

}

2977

2978

my_error(ER_USE_SQL_BIG_RESULT, MYF(0));

2979

return NESTED_LOOP_ERROR; // Table is_full error

2980

}

2981

if (++join->send_records >= join->tmp_table_param.end_write_records && join->do_send_rows)

2982

{

2983

if (!(join->select_options & OPTION_FOUND_ROWS))

2984

return NESTED_LOOP_QUERY_LIMIT;

2985

join->do_send_rows= 0;

2986

join->unit->select_limit_cnt= HA_POS_ERROR;

2987

return NESTED_LOOP_OK;

2988

}

2989

}

2990

}

2991

2992

return NESTED_LOOP_OK;

2993

}

2994

2995

/** Group by searching after group record and updating it if possible. */

2996

enum_nested_loop_state end_update(Join *join, JoinTable *, bool end_of_records)

2997

{

2998

Table *table= join->tmp_table;

2999

Order *group;

3000

int error;

3001

3002

if (end_of_records)

3003

return NESTED_LOOP_OK;

3004

if (join->session->getKilled()) // Aborted by user

3005

{

3006

join->session->send_kill_message();

3007

return NESTED_LOOP_KILLED;

3008

}

3009

3010

join->found_records++;

3011

copy_fields(&join->tmp_table_param); // Groups are copied twice.

3012

/* Make a key of group index */

3013

for (group=table->group ; group ; group=group->next)

3014

{

3015

Item *item= *group->item;

3016

item->save_org_in_field(group->field);

3017

/* Store in the used key if the field was 0 */

3018

if (item->maybe_null)

3019

group->buff[-1]= (char) group->field->is_null();

3020

}

3021

if (!table->cursor->index_read_map(table->getUpdateRecord(),

3022

join->tmp_table_param.group_buff,

3023

HA_WHOLE_KEY,

3024

HA_READ_KEY_EXACT))

3025

{ /* Update old record */

3026

table->restoreRecord();

3027

update_tmptable_sum_func(join->sum_funcs,table);

3028

if ((error= table->cursor->updateRecord(table->getUpdateRecord(),

3029

table->getInsertRecord())))

3030

{

3031

table->print_error(error,MYF(0));

3032

return NESTED_LOOP_ERROR;

3033

}

3034

return NESTED_LOOP_OK;

3035

}

3036

3037

3038

Copy null bits from group key to table

3039

We can't copy all data as the key may have different format

3040

as the row data (for example as with VARCHAR keys)

3041

3042

KeyPartInfo *key_part;

3043

for (group=table->group,key_part=table->key_info[0].key_part;

3044

group ;

3045

group=group->next,key_part++)

3046

{

3047

if (key_part->null_bit)

3048

memcpy(table->getInsertRecord()+key_part->offset, group->buff, 1);

3049

}

3050

init_tmptable_sum_functions(join->sum_funcs);

3051

if (copy_funcs(join->tmp_table_param.items_to_copy, join->session))

3052

return NESTED_LOOP_ERROR;

3053

if ((error=table->cursor->insertRecord(table->getInsertRecord())))

3054

{

3055

my_error(ER_USE_SQL_BIG_RESULT, MYF(0));

3056

return NESTED_LOOP_ERROR; // Table is_full error

3057

}

3058

join->send_records++;

3059

return NESTED_LOOP_OK;

3060

}

3061

3062

/** Like end_update, but this is done with unique constraints instead of keys. */

3063

enum_nested_loop_state end_unique_update(Join *join, JoinTable *, bool end_of_records)

3064

{

3065

Table *table= join->tmp_table;

3066

int error;

3067

3068

if (end_of_records)

3069

return NESTED_LOOP_OK;

3070

if (join->session->getKilled()) // Aborted by user

3071

{

3072

join->session->send_kill_message();

3073

return NESTED_LOOP_KILLED;

3074

}

3075

3076

init_tmptable_sum_functions(join->sum_funcs);

3077

copy_fields(&join->tmp_table_param); // Groups are copied twice.

3078

if (copy_funcs(join->tmp_table_param.items_to_copy, join->session))

3079

return NESTED_LOOP_ERROR;

3080

3081

if (!(error= table->cursor->insertRecord(table->getInsertRecord())))

3082

join->send_records++; // New group

3083

else

3084

{

3085

if ((int) table->get_dup_key(error) < 0)

3086

{

3087

table->print_error(error,MYF(0));

3088

return NESTED_LOOP_ERROR;

3089

}

3090

if (table->cursor->rnd_pos(table->getUpdateRecord(),table->cursor->dup_ref))

3091

{

3092

table->print_error(error,MYF(0));

3093

return NESTED_LOOP_ERROR;

3094

}

3095

table->restoreRecord();

3096

update_tmptable_sum_func(join->sum_funcs,table);

3097

if ((error= table->cursor->updateRecord(table->getUpdateRecord(),

3098

table->getInsertRecord())))

3099

{

3100

table->print_error(error,MYF(0));

3101

return NESTED_LOOP_ERROR;

3102

}

3103

}

3104

return NESTED_LOOP_OK;

3105

}

3106

3107

/**

3108

allocate group fields or take prepared (cached).

3109

3110

@param main_join join of current select

3111

@param curr_join current join (join of current select or temporary copy

3112

of it)

3113

3114

@retval

3115

0 ok

3116

@retval

3117

1 failed

3118

3119

static bool make_group_fields(Join *main_join, Join *curr_join)

3120

{

3121

if (main_join->group_fields_cache.size())

3122

{

3123

curr_join->group_fields= main_join->group_fields_cache;

3124

curr_join->sort_and_group= 1;

3125

}

3126

else

3127

{

3128

if (alloc_group_fields(curr_join, curr_join->group_list))

3129

return 1;

3130

main_join->group_fields_cache= curr_join->group_fields;

3131

}

3132

return (0);

3133

}

3134

3135

/**

3136

calc how big buffer we need for comparing group entries.

3137

3138

static void calc_group_buffer(Join *join, Order *group)

3139

{

3140

uint32_t key_length=0, parts=0, null_parts=0;

3141

3142

if (group)

3143

join->group= 1;

3144

for (; group ; group=group->next)

3145

{

3146

Item *group_item= *group->item;

3147

Field *field= group_item->get_tmp_table_field();

3148

if (field)

3149

{

3150

enum_field_types type;

3151

if ((type= field->type()) == DRIZZLE_TYPE_BLOB)

3152

key_length+=MAX_BLOB_WIDTH; // Can't be used as a key

3153

else if (type == DRIZZLE_TYPE_VARCHAR)

3154

key_length+= field->field_length + HA_KEY_BLOB_LENGTH;

3155

else

3156

key_length+= field->pack_length();

3157

}

3158

else

3159

{

3160

switch (group_item->result_type()) {

3161

case REAL_RESULT:

3162

key_length+= sizeof(double);

3163

break;

3164

3165

case INT_RESULT:

3166

key_length+= sizeof(int64_t);

3167

break;

3168

3169

case DECIMAL_RESULT:

3170

key_length+= class_decimal_get_binary_size(group_item->max_length -

3171

(group_item->decimals ? 1 : 0),

3172

group_item->decimals);

3173

break;

3174

3175

case STRING_RESULT:

3176

{

3177

enum enum_field_types type= group_item->field_type();

3178

3179

As items represented as DATE/TIME fields in the group buffer

3180

have STRING_RESULT result type, we increase the length

3181

by 8 as maximum pack length of such fields.

3182

3183

if (field::isDateTime(type))

3184

{

3185

key_length+= 8;

3186

}

3187

else

3188

{

3189

3190

Group strings are taken as varstrings and require an length field.

3191

A field is not yet created by create_tmp_field()

3192

and the sizes should match up.

3193

3194

key_length+= group_item->max_length + HA_KEY_BLOB_LENGTH;

3195

}

3196

3197

break;

3198

}

3199

3200

case ROW_RESULT:

3201

/* This case should never be choosen */

3202

assert(0);

3203

my_error(ER_OUT_OF_RESOURCES, MYF(ME_FATALERROR));

3204

}

3205

}

3206

3207

parts++;

3208

3209

if (group_item->maybe_null)

3210

null_parts++;

3211

}

3212

3213

join->tmp_table_param.group_length=key_length+null_parts;

3214

join->tmp_table_param.group_parts=parts;

3215

join->tmp_table_param.group_null_parts=null_parts;

3216

}

3217

3218

/**

3219

Get a list of buffers for saveing last group.

3220

3221

Groups are saved in reverse order for easyer check loop.

3222

3223

static bool alloc_group_fields(Join *join, Order *group)

3224

{

3225

if (group)

3226

{

3227

for (; group ; group=group->next)

3228

{

3229

Cached_item *tmp= new_Cached_item(join->session, *group->item);

3230

if (!tmp)

3231

return true;

3232

join->group_fields.push_front(tmp);

3233

}

3234

}

3235

join->sort_and_group=1; /* Mark for do_select */

3236

return false;

3237

}

3238

3239

static uint32_t cache_record_length(Join *join,uint32_t idx)

3240

{

3241

uint32_t length=0;

3242

JoinTable **pos,**end;

3243

Session *session=join->session;

3244

3245

for (pos=join->best_ref+join->const_tables,end=join->best_ref+idx ;

3246

pos != end ;

3247

pos++)

3248

{

3249

JoinTable *join_tab= *pos;

3250

if (!join_tab->used_fieldlength) /* Not calced yet */

3251

calc_used_field_length(session, join_tab);

3252

length+=join_tab->used_fieldlength;

3253

}

3254

return length;

3255

}

3256

3257

3258

Get the number of different row combinations for subset of partial join

3259

3260

SYNOPSIS

3261

prev_record_reads()

3262

join The join structure

3263

idx Number of tables in the partial join order (i.e. the

3264

partial join order is in join->positions[0..idx-1])

3265

found_ref Bitmap of tables for which we need to find # of distinct

3266

row combinations.

3267

3268

DESCRIPTION

3269

Given a partial join order (in join->positions[0..idx-1]) and a subset of

3270

tables within that join order (specified in found_ref), find out how many

3271

distinct row combinations of subset tables will be in the result of the

3272

partial join order.

3273

3274

This is used as follows: Suppose we have a table accessed with a ref-based

3275

method. The ref access depends on current rows of tables in found_ref.

3276

We want to count # of different ref accesses. We assume two ref accesses

3277

will be different if at least one of access parameters is different.

3278

Example: consider a query

3279

3280

SELECT * FROM t1, t2, t3 WHERE t1.key=c1 AND t2.key=c2 AND t3.key=t1.field

3281

3282

and a join order:

3283

t1, ref access on t1.key=c1

3284

t2, ref access on t2.key=c2

3285

t3, ref access on t3.key=t1.field

3286

3287

For t1: n_ref_scans = 1, n_distinct_ref_scans = 1

3288

For t2: n_ref_scans = records_read(t1), n_distinct_ref_scans=1

3289

For t3: n_ref_scans = records_read(t1)*records_read(t2)

3290

n_distinct_ref_scans = #records_read(t1)

3291

3292

The reason for having this function (at least the latest version of it)

3293

is that we need to account for buffering in join execution.

3294

3295

An edge-case example: if we have a non-first table in join accessed via

3296

ref(const) or ref(param) where there is a small number of different

3297

values of param, then the access will likely hit the disk cache and will

3298

not require any disk seeks.

3299

3300

The proper solution would be to assume an LRU disk cache of some size,

3301

calculate probability of cache hits, etc. For now we just count

3302

identical ref accesses as one.

3303

3304

RETURN

3305

Expected number of row combinations

3306

3307

static double prev_record_reads(Join *join, uint32_t idx, table_map found_ref)

3308

{

3309

double found=1.0;

3310

optimizer::Position *pos_end= join->getSpecificPosInPartialPlan(-1);

3311

for (optimizer::Position *pos= join->getSpecificPosInPartialPlan(idx - 1);

3312

pos != pos_end;

3313

pos--)

3314

{

3315

if (pos->examinePosition(found_ref))

3316

{

3317

found_ref|= pos->getRefDependMap();

3318

3319

For the case of "t1 LEFT Join t2 ON ..." where t2 is a const table

3320

with no matching row we will get position[t2].records_read==0.

3321

Actually the size of output is one null-complemented row, therefore

3322

we will use value of 1 whenever we get records_read==0.

3323

3324

Note

3325

- the above case can't occur if inner part of outer join has more

3326

than one table: table with no matches will not be marked as const.

3327

3328

- Ideally we should add 1 to records_read for every possible null-

3329

complemented row. We're not doing it because: 1. it will require

3330

non-trivial code and add overhead. 2. The value of records_read

3331

is an inprecise estimate and adding 1 (or, in the worst case,

3332

#max_nested_outer_joins=64-1) will not make it any more precise.

3333

3334

if (pos->getFanout() > DBL_EPSILON)

3335

found*= pos->getFanout();

3336

}

3337

}

3338

return found;

3339

}

3340

3341

/**

3342

Set up join struct according to best position.

3343

3344

static bool get_best_combination(Join *join)

3345

{

3346

uint32_t i,tablenr;

3347

table_map used_tables;

3348

JoinTable *join_tab,*j;

3349

optimizer::KeyUse *keyuse;

3350

uint32_t table_count;

3351

Session *session=join->session;

3352

optimizer::Position cur_pos;

3353

3354

table_count=join->tables;

3355

join->join_tab=join_tab= new (session->mem) JoinTable[table_count];

3356

join->full_join=0;

3357

3358

used_tables= OUTER_REF_TABLE_BIT; // Outer row is already read

3359

for (j=join_tab, tablenr=0 ; tablenr < table_count ; tablenr++,j++)

3360

{

3361

Table *form;

3362

cur_pos= join->getPosFromOptimalPlan(tablenr);

3363

*j= *cur_pos.getJoinTable();

3364

form=join->table[tablenr]=j->table;

3365

used_tables|= form->map;

3366

form->reginfo.join_tab=j;

3367

if (!*j->on_expr_ref)

3368

form->reginfo.not_exists_optimize=0; // Only with LEFT Join

3369

if (j->type == AM_CONST)

3370

continue; // Handled in make_join_stat..

3371

3372

j->ref.key = -1;

3373

j->ref.key_parts=0;

3374

3375

if (j->type == AM_SYSTEM)

3376

continue;

3377

if (j->keys.none() || ! (keyuse= cur_pos.getKeyUse()))

3378

{

3379

j->type= AM_ALL;

3380

if (tablenr != join->const_tables)

3381

join->full_join=1;

3382

}

3383

else if (create_ref_for_key(join, j, keyuse, used_tables))

3384

return true; // Something went wrong

3385

}

3386

3387

for (i=0 ; i < table_count ; i++)

3388

join->map2table[join->join_tab[i].table->tablenr]=join->join_tab+i;

3389

update_depend_map(join);

3390

return 0;

3391

}

3392

3393

/** Save const tables first as used tables. */

3394

static void set_position(Join *join,

3395

uint32_t idx,

3396

JoinTable *table,

3397

optimizer::KeyUse *key)

3398

{

3399

optimizer::Position tmp_pos(1.0, /* This is a const table */

3400

0.0,

3401

table,

3402

key,

3403

0);

3404

join->setPosInPartialPlan(idx, tmp_pos);

3405

3406

/* Move the const table as down as possible in best_ref */

3407

JoinTable **pos=join->best_ref+idx+1;

3408

JoinTable *next=join->best_ref[idx];

3409

for (;next != table ; pos++)

3410

{

3411

JoinTable *tmp=pos[0];

3412

pos[0]=next;

3413

next=tmp;

3414

}

3415

join->best_ref[idx]=table;

3416

}

3417

3418

/**

3419

Selects and invokes a search strategy for an optimal query plan.

3420

3421

The function checks user-configurable parameters that control the search

3422

strategy for an optimal plan, selects the search method and then invokes

3423

it. Each specific optimization procedure stores the final optimal plan in

3424

the array 'join->best_positions', and the cost of the plan in

3425

'join->best_read'.

3426

3427

@param join pointer to the structure providing all context info for

3428

the query

3429

@param join_tables set of the tables in the query

3430

3431

@retval

3432

false ok

3433

@retval

3434

true Fatal error

3435

3436

static bool choose_plan(Join *join, table_map join_tables)

3437

{

3438

uint32_t search_depth= join->session->variables.optimizer_search_depth;

3439

uint32_t prune_level= join->session->variables.optimizer_prune_level;

3440

bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);

3441

3442

join->cur_embedding_map.reset();

3443

reset_nj_counters(join->join_list);

3444

3445

if (SELECT_STRAIGHT_JOIN option is set)

3446

reorder tables so dependent tables come after tables they depend

3447

on, otherwise keep tables in the order they were specified in the query

3448

else

3449

Apply heuristic: pre-sort all access plans with respect to the number of

3450

records accessed.

3451

3452

internal::my_qsort(join->best_ref + join->const_tables,

3453

join->tables - join->const_tables, sizeof(JoinTable*),

3454

straight_join ? join_tab_cmp_straight : join_tab_cmp);

3455

if (straight_join)

3456

{

3457

optimize_straight_join(join, join_tables);

3458

}

3459

else

3460

{

3461

if (search_depth == 0)

3462

/* Automatically determine a reasonable value for 'search_depth' */

3463

search_depth= determine_search_depth(join);

3464

if (greedy_search(join, join_tables, search_depth, prune_level))

3465

return true;

3466

}

3467

3468

3469

Store the cost of this query into a user variable

3470

Don't update last_query_cost for statements that are not "flat joins" :

3471

i.e. they have subqueries, unions or call stored procedures.

3472

TODO: calculate a correct cost for a query with subqueries and UNIONs.

3473

3474

if (join->session->lex().is_single_level_stmt())

3475

join->session->status_var.last_query_cost= join->best_read;

3476

return false;

3477

}

3478

3479

/**

3480

Find the best access path for an extension of a partial execution

3481

plan and add this path to the plan.

3482

3483

The function finds the best access path to table 's' from the passed

3484

partial plan where an access path is the general term for any means to

3485

access the data in 's'. An access path may use either an index or a scan,

3486

whichever is cheaper. The input partial plan is passed via the array

3487

'join->positions' of length 'idx'. The chosen access method for 's' and its

3488

cost are stored in 'join->positions[idx]'.

3489

3490

@param join pointer to the structure providing all context info

3491

for the query

3492

@param s the table to be joined by the function

3493

@param session thread for the connection that submitted the query

3494

@param remaining_tables set of tables not included into the partial plan yet

3495

@param idx the length of the partial plan

3496

@param record_count estimate for the number of records returned by the

3497

partial plan

3498

@param read_time the cost of the partial plan

3499

3500

@return

3501

None

3502

3503

static void best_access_path(Join *join,

3504

JoinTable *s,

3505

Session *session,

3506

table_map remaining_tables,

3507

uint32_t idx,

3508

double record_count,

3509

double)

3510

{

3511

optimizer::KeyUse *best_key= NULL;

3512

uint32_t best_max_key_part= 0;

3513

bool found_constraint= 0;

3514

double best= DBL_MAX;

3515

double best_time= DBL_MAX;

3516

double records= DBL_MAX;

3517

table_map best_ref_depends_map= 0;

3518

double tmp;

3519

ha_rows rec;

3520

3521

if (s->keyuse)

3522

{ /* Use key if possible */

3523

Table *table= s->table;

3524

optimizer::KeyUse *keyuse= NULL;

3525

optimizer::KeyUse *start_key= NULL;

3526

double best_records= DBL_MAX;

3527

uint32_t max_key_part=0;

3528

3529

/* Test how we can use keys */

3530

rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key

3531

for (keyuse= s->keyuse; keyuse->getTable() == table; )

3532

{

3533

key_part_map found_part= 0;

3534

table_map found_ref= 0;

3535

uint32_t key= keyuse->getKey();

3536

KeyInfo *keyinfo= table->key_info + key;

3537

/* Bitmap of keyparts where the ref access is over 'keypart=const': */

3538

key_part_map const_part= 0;

3539

/* The or-null keypart in ref-or-null access: */

3540

key_part_map ref_or_null_part= 0;

3541

3542

/* Calculate how many key segments of the current key we can use */

3543

start_key= keyuse;

3544

3545

do /* For each keypart */

3546

{

3547

uint32_t keypart= keyuse->getKeypart();

3548

table_map best_part_found_ref= 0;

3549

double best_prev_record_reads= DBL_MAX;

3550

3551

do /* For each way to access the keypart */

3552

{

3553

3554

3555

if 1. expression doesn't refer to forward tables

3556

2. we won't get two ref-or-null's

3557

3558

if (! (remaining_tables & keyuse->getUsedTables()) &&

3559

! (ref_or_null_part && (keyuse->getOptimizeFlags() &

3560

KEY_OPTIMIZE_REF_OR_NULL)))

3561

{

3562

found_part|= keyuse->getKeypartMap();

3563

if (! (keyuse->getUsedTables() & ~join->const_table_map))

3564

const_part|= keyuse->getKeypartMap();

3565

3566

double tmp2= prev_record_reads(join, idx, (found_ref |

3567

keyuse->getUsedTables()));

3568

if (tmp2 < best_prev_record_reads)

3569

{

3570

best_part_found_ref= keyuse->getUsedTables() & ~join->const_table_map;

3571

best_prev_record_reads= tmp2;

3572

}

3573

if (rec > keyuse->getTableRows())

3574

rec= keyuse->getTableRows();

3575

3576

If there is one 'key_column IS NULL' expression, we can

3577

use this ref_or_null optimisation of this field

3578

3579

if (keyuse->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL)

3580

ref_or_null_part|= keyuse->getKeypartMap();

3581

}

3582

3583

keyuse++;

3584

} while (keyuse->getTable() == table && keyuse->getKey() == key &&

3585

keyuse->getKeypart() == keypart);

3586

found_ref|= best_part_found_ref;

3587

} while (keyuse->getTable() == table && keyuse->getKey() == key);

3588

3589

3590

Assume that that each key matches a proportional part of table.

3591

3592

if (!found_part)

3593

continue; // Nothing usable found

3594

3595

if (rec < MATCHING_ROWS_IN_OTHER_TABLE)

3596

rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables

3597

3598

{

3599

found_constraint= 1;

3600

3601

3602

Check if we found full key

3603

3604

if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&

3605

!ref_or_null_part)

3606

{ /* use eq key */

3607

max_key_part= UINT32_MAX;

3608

if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)

3609

{

3610

tmp = prev_record_reads(join, idx, found_ref);

3611

records=1.0;

3612

}

3613

else

3614

{

3615

if (!found_ref)

3616

{ /* We found a const key */

3617

3618

ReuseRangeEstimateForRef-1:

3619

We get here if we've found a ref(const) (c_i are constants):

3620

"(keypart1=c1) AND ... AND (keypartN=cN)" [ref_const_cond]

3621

3622

If range optimizer was able to construct a "range"

3623

access on this index, then its condition "quick_cond" was

3624

eqivalent to ref_const_cond (*), and we can re-use E(#rows)

3625

from the range optimizer.

3626

3627

Proof of (*): By properties of range and ref optimizers

3628

quick_cond will be equal or tighther than ref_const_cond.

3629

ref_const_cond already covers "smallest" possible interval -

3630

a singlepoint interval over all keyparts. Therefore,

3631

quick_cond is equivalent to ref_const_cond (if it was an

3632

empty interval we wouldn't have got here).

3633

3634

if (table->quick_keys.test(key))

3635

records= (double) table->quick_rows[key];

3636

else

3637

{

3638

/* quick_range couldn't use key! */

3639

records= (double) s->records/rec;

3640

}

3641

}

3642

else

3643

{

3644

if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))

3645

{ /* Prefer longer keys */

3646

records=

3647

((double) s->records / (double) rec *

3648

(1.0 +

3649

((double) (table->getShare()->max_key_length-keyinfo->key_length) /

3650

(double) table->getShare()->max_key_length)));

3651

if (records < 2.0)

3652

records=2.0; /* Can't be as good as a unique */

3653

}

3654

3655

ReuseRangeEstimateForRef-2: We get here if we could not reuse

3656

E(#rows) from range optimizer. Make another try:

3657

3658

If range optimizer produced E(#rows) for a prefix of the ref

3659

access we're considering, and that E(#rows) is lower then our

3660

current estimate, make an adjustment. The criteria of when we

3661

can make an adjustment is a special case of the criteria used

3662

in ReuseRangeEstimateForRef-3.

3663

3664

if (table->quick_keys.test(key) &&

3665

const_part & (1 << table->quick_key_parts[key]) &&

3666

table->quick_n_ranges[key] == 1 &&

3667

records > (double) table->quick_rows[key])

3668

{

3669

records= (double) table->quick_rows[key];

3670

}

3671

}

3672

/* Limit the number of matched rows */

3673

tmp= records;

3674

set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);

3675

if (table->covering_keys.test(key))

3676

{

3677

/* we can use only index tree */

3678

tmp= record_count * table->cursor->index_only_read_time(key, tmp);

3679

}

3680

else

3681

tmp= record_count * min(tmp,s->worst_seeks);

3682

}

3683

}

3684

else

3685

{

3686

3687

Use as much key-parts as possible and a uniq key is better

3688

than a not unique key

3689

Set tmp to (previous record count) * (records / combination)

3690

3691

if ((found_part & 1) &&

3692

(!(table->index_flags(key) & HA_ONLY_WHOLE_INDEX) ||

3693

found_part == PREV_BITS(uint, keyinfo->key_parts)))

3694

{

3695

max_key_part= max_part_bit(found_part);

3696

3697

ReuseRangeEstimateForRef-3:

3698

We're now considering a ref[or_null] access via

3699

(t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR

3700

(same-as-above but with one cond replaced

3701

with "t.keypart_i IS NULL")] (**)

3702

3703

Try re-using E(#rows) from "range" optimizer:

3704

We can do so if "range" optimizer used the same intervals as

3705

in (**). The intervals used by range optimizer may be not

3706

available at this point (as "range" access might have choosen to

3707

create quick select over another index), so we can't compare

3708

them to (**). We'll make indirect judgements instead.

3709

The sufficient conditions for re-use are:

3710

(C1) All e_i in (**) are constants, i.e. found_ref==false. (if

3711

this is not satisfied we have no way to know which ranges

3712

will be actually scanned by 'ref' until we execute the

3713

join)

3714

(C2) max #key parts in 'range' access == K == max_key_part (this

3715

is apparently a necessary requirement)

3716

3717

We also have a property that "range optimizer produces equal or

3718

tighter set of scan intervals than ref(const) optimizer". Each

3719

of the intervals in (**) are "tightest possible" intervals when

3720

one limits itself to using keyparts 1..K (which we do in #2).

3721

From here it follows that range access used either one, or

3722

both of the (I1) and (I2) intervals:

3723

3724

(t.keypart1=c1 AND ... AND t.keypartK=eK) (I1)

3725

(same-as-above but with one cond replaced

3726

with "t.keypart_i IS NULL") (I2)

3727

3728

The remaining part is to exclude the situation where range

3729

optimizer used one interval while we're considering

3730

ref-or-null and looking for estimate for two intervals. This

3731

is done by last limitation:

3732

3733

(C3) "range optimizer used (have ref_or_null?2:1) intervals"

3734

3735

if (table->quick_keys.test(key) && !found_ref && //(C1)

3736

table->quick_key_parts[key] == max_key_part && //(C2)

3737

table->quick_n_ranges[key] == 1+((ref_or_null_part)?1:0)) //(C3)

3738

{

3739

tmp= records= (double) table->quick_rows[key];

3740

}

3741

else

3742

{

3743

/* Check if we have statistic about the distribution */

3744

if ((records= keyinfo->rec_per_key[max_key_part-1]))

3745

{

3746

3747

Fix for the case where the index statistics is too

3748

optimistic: If

3749

(1) We're considering ref(const) and there is quick select

3750

on the same index,

3751

(2) and that quick select uses more keyparts (i.e. it will

3752

scan equal/smaller interval then this ref(const))

3753

(3) and E(#rows) for quick select is higher then our

3754

estimate,

3755

Then

3756

We'll use E(#rows) from quick select.

3757

3758

Q: Why do we choose to use 'ref'? Won't quick select be

3759

cheaper in some cases ?

3760

TODO: figure this out and adjust the plan choice if needed.

3761

3762

if (!found_ref && table->quick_keys.test(key) && // (1)

3763

table->quick_key_parts[key] > max_key_part && // (2)

3764

records < (double)table->quick_rows[key]) // (3)

3765

records= (double)table->quick_rows[key];

3766

3767

tmp= records;

3768

}

3769

else

3770

{

3771

3772

Assume that the first key part matches 1% of the cursor

3773

and that the whole key matches 10 (duplicates) or 1

3774

(unique) records.

3775

Assume also that more key matches proportionally more

3776

records

3777

This gives the formula:

3778

records = (x * (b-a) + a*c-b)/(c-1)

3779

3780

b = records matched by whole key

3781

a = records matched by first key part (1% of all records?)

3782

c = number of key parts in key

3783

x = used key parts (1 <= x <= c)

3784

3785

double rec_per_key;

3786

if (!(rec_per_key=(double)

3787

keyinfo->rec_per_key[keyinfo->key_parts-1]))

3788

rec_per_key=(double) s->records/rec+1;

3789

3790

if (!s->records)

3791

tmp = 0;

3792

else if (rec_per_key/(double) s->records >= 0.01)

3793

tmp = rec_per_key;

3794

else

3795

{

3796

double a=s->records*0.01;

3797

if (keyinfo->key_parts > 1)

3798

tmp= (max_key_part * (rec_per_key - a) +

3799

a*keyinfo->key_parts - rec_per_key)/

3800

(keyinfo->key_parts-1);

3801

else

3802

tmp= a;

3803

set_if_bigger(tmp,1.0);

3804

}

3805

records = (uint32_t) tmp;

3806

}

3807

3808

if (ref_or_null_part)

3809

{

3810

/* We need to do two key searches to find key */

3811

tmp *= 2.0;

3812

records *= 2.0;

3813

}

3814

3815

3816

ReuseRangeEstimateForRef-4: We get here if we could not reuse

3817

E(#rows) from range optimizer. Make another try:

3818

3819

If range optimizer produced E(#rows) for a prefix of the ref

3820

access we're considering, and that E(#rows) is lower then our

3821

current estimate, make the adjustment.

3822

3823

The decision whether we can re-use the estimate from the range

3824

optimizer is the same as in ReuseRangeEstimateForRef-3,

3825

applied to first table->quick_key_parts[key] key parts.

3826

3827

if (table->quick_keys.test(key) &&

3828

table->quick_key_parts[key] <= max_key_part &&

3829

const_part & (1 << table->quick_key_parts[key]) &&

3830

table->quick_n_ranges[key] == 1 + ((ref_or_null_part &

3831

const_part) ? 1 : 0) &&

3832

records > (double) table->quick_rows[key])

3833

{

3834

tmp= records= (double) table->quick_rows[key];

3835

}

3836

}

3837

3838

/* Limit the number of matched rows */

3839

set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);

3840

if (table->covering_keys.test(key))

3841

{

3842

/* we can use only index tree */

3843

tmp= record_count * table->cursor->index_only_read_time(key, tmp);

3844

}

3845

else

3846

tmp= record_count * min(tmp,s->worst_seeks);

3847

}

3848

else

3849

tmp= best_time; // Do nothing

3850

}

3851

3852

}

3853

if (tmp < best_time - records/(double) TIME_FOR_COMPARE)

3854

{

3855

best_time= tmp + records/(double) TIME_FOR_COMPARE;

3856

best= tmp;

3857

best_records= records;

3858

best_key= start_key;

3859

best_max_key_part= max_key_part;

3860

best_ref_depends_map= found_ref;

3861

}

3862

}

3863

records= best_records;

3864

}

3865

3866

3867

Don't test table scan if it can't be better.

3868

Prefer key lookup if we would use the same key for scanning.

3869

3870

Don't do a table scan on InnoDB tables, if we can read the used

3871

parts of the row from any of the used index.

3872

This is because table scans uses index and we would not win

3873

anything by using a table scan.

3874

3875

A word for word translation of the below if-statement in sergefp's

3876

understanding: we check if we should use table scan if:

3877

(1) The found 'ref' access produces more records than a table scan

3878

(or index scan, or quick select), or 'ref' is more expensive than

3879

any of them.

3880

(2) This doesn't hold: the best way to perform table scan is to to perform

3881

'range' access using index IDX, and the best way to perform 'ref'

3882

access is to use the same index IDX, with the same or more key parts.

3883

(note: it is not clear how this rule is/should be extended to

3884

index_merge quick selects)

3885

(3) See above note about InnoDB.

3886

(4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access

3887

path, but there is no quick select)

3888

If the condition in the above brackets holds, then the only possible

3889

"table scan" access method is ALL/index (there is no quick select).

3890

Since we have a 'ref' access path, and FORCE INDEX instructs us to

3891

choose it over ALL/index, there is no need to consider a full table

3892

scan.

3893

3894

if ((records >= s->found_records || best > s->read_time) && // (1)

3895

! (s->quick && best_key && s->quick->index == best_key->getKey() && // (2)

3896

best_max_key_part >= s->table->quick_key_parts[best_key->getKey()]) &&// (2)

3897

! ((s->table->cursor->getEngine()->check_flag(HTON_BIT_TABLE_SCAN_ON_INDEX)) && // (3)

3898

! s->table->covering_keys.none() && best_key && !s->quick) && // (3)

3899

! (s->table->force_index && best_key && !s->quick)) // (4)

3900

{ // Check full join

3901

ha_rows rnd_records= s->found_records;

3902

3903

If there is a filtering condition on the table (i.e. ref analyzer found

3904

at least one "table.keyXpartY= exprZ", where exprZ refers only to tables

3905

preceding this table in the join order we're now considering), then

3906

assume that 25% of the rows will be filtered out by this condition.

3907

3908

This heuristic is supposed to force tables used in exprZ to be before

3909

this table in join order.

3910

3911

if (found_constraint)

3912

rnd_records-= rnd_records/4;

3913

3914

3915

If applicable, get a more accurate estimate. Don't use the two

3916

heuristics at once.

3917

3918

if (s->table->quick_condition_rows != s->found_records)

3919

rnd_records= s->table->quick_condition_rows;

3920

3921

3922

Range optimizer never proposes a RANGE if it isn't better

3923

than FULL: so if RANGE is present, it's always preferred to FULL.

3924

Here we estimate its cost.

3925

3926

if (s->quick)

3927

{

3928

3929

For each record we:

3930

- read record range through 'quick'

3931

- skip rows which does not satisfy WHERE constraints

3932

TODO:

3933

We take into account possible use of join cache for ALL/index

3934

access (see first else-branch below), but we don't take it into

3935

account here for range/index_merge access. Find out why this is so.

3936

3937

tmp= record_count *

3938

(s->quick->read_time +

3939

(s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);

3940

}

3941

else

3942

{

3943

/* Estimate cost of reading table. */

3944

tmp= s->table->cursor->scan_time();

3945

if (s->table->map & join->outer_join) // Can't use join cache

3946

{

3947

3948

For each record we have to:

3949

- read the whole table record

3950

- skip rows which does not satisfy join condition

3951

3952

tmp= record_count *

3953

(tmp +

3954

(s->records - rnd_records)/(double) TIME_FOR_COMPARE);

3955

}

3956

else

3957

{

3958

/* We read the table as many times as join buffer becomes full. */

3959

tmp*= (1.0 + floor((double) cache_record_length(join,idx) *

3960

record_count /

3961

(double) session->variables.join_buff_size));

3962

3963

We don't make full cartesian product between rows in the scanned

3964

table and existing records because we skip all rows from the

3965

scanned table, which does not satisfy join condition when

3966

we read the table (see flush_cached_records for details). Here we

3967

take into account cost to read and skip these records.

3968

3969

tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;

3970

}

3971

}

3972

3973

3974

We estimate the cost of evaluating WHERE clause for found records

3975

as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus

3976

tmp give us total cost of using Table SCAN

3977

3978

if (best == DBL_MAX ||

3979

(tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records <

3980

best + record_count/(double) TIME_FOR_COMPARE*records))

3981

{

3982

3983

If the table has a range (s->quick is set) make_join_select()

3984

will ensure that this will be used

3985

3986

best= tmp;

3987

records= rnd_records;

3988

best_key= 0;

3989

/* range/index_merge/ALL/index access method are "independent", so: */

3990

best_ref_depends_map= 0;

3991

}

3992

}

3993

3994

/* Update the cost information for the current partial plan */

3995

optimizer::Position tmp_pos(records,

3996

best,

3997

3998

best_key,

3999

best_ref_depends_map);

4000

join->setPosInPartialPlan(idx, tmp_pos);

4001

4002

if (!best_key &&

4003

idx == join->const_tables &&

4004

s->table == join->sort_by_table &&

4005

join->unit->select_limit_cnt >= records)

4006

join->sort_by_table= (Table*) 1; // Must use temporary table

4007

4008

return;

4009

}

4010

4011

/**

4012

Select the best ways to access the tables in a query without reordering them.

4013

4014

Find the best access paths for each query table and compute their costs

4015

according to their order in the array 'join->best_ref' (thus without

4016

reordering the join tables). The function calls sequentially

4017

'best_access_path' for each table in the query to select the best table

4018

access method. The final optimal plan is stored in the array

4019

'join->best_positions', and the corresponding cost in 'join->best_read'.

4020

4021

@param join pointer to the structure providing all context info for

4022

the query

4023

@param join_tables set of the tables in the query

4024

4025

@note

4026

This function can be applied to:

4027

- queries with STRAIGHT_JOIN

4028

- internally to compute the cost of an arbitrary QEP

4029

@par

4030

Thus 'optimize_straight_join' can be used at any stage of the query

4031

optimization process to finalize a QEP as it is.

4032

4033

static void optimize_straight_join(Join *join, table_map join_tables)

4034

{

4035

JoinTable *s;

4036

optimizer::Position partial_pos;

4037

uint32_t idx= join->const_tables;

4038

double record_count= 1.0;

4039

double read_time= 0.0;

4040

4041

for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)

4042

{

4043

/* Find the best access method from 's' to the current partial plan */

4044

best_access_path(join, s, join->session, join_tables, idx,

4045

record_count, read_time);

4046

/* compute the cost of the new plan extended with 's' */

4047

partial_pos= join->getPosFromPartialPlan(idx);

4048

record_count*= partial_pos.getFanout();

4049

read_time+= partial_pos.getCost();

4050

join_tables&= ~(s->table->map);

4051

++idx;

4052

}

4053

4054

read_time+= record_count / (double) TIME_FOR_COMPARE;

4055

partial_pos= join->getPosFromPartialPlan(join->const_tables);

4056

if (join->sort_by_table &&

4057

partial_pos.hasTableForSorting(join->sort_by_table))

4058

read_time+= record_count; // We have to make a temp table

4059

join->copyPartialPlanIntoOptimalPlan(idx);

4060

join->best_read= read_time;

4061

}

4062

4063

/**

4064

Find a good, possibly optimal, query execution plan (QEP) by a greedy search.

4065

4066

The search procedure uses a hybrid greedy/exhaustive search with controlled

4067

exhaustiveness. The search is performed in N = card(remaining_tables)

4068

steps. Each step evaluates how promising is each of the unoptimized tables,

4069

selects the most promising table, and extends the current partial QEP with

4070

that table. Currenly the most 'promising' table is the one with least

4071

expensive extension.\

4072

4073

There are two extreme cases:

4074

-# When (card(remaining_tables) < search_depth), the estimate finds the

4075

best complete continuation of the partial QEP. This continuation can be

4076

used directly as a result of the search.

4077

-# When (search_depth == 1) the 'best_extension_by_limited_search'

4078

consideres the extension of the current QEP with each of the remaining

4079

unoptimized tables.

4080

4081

All other cases are in-between these two extremes. Thus the parameter

4082

'search_depth' controlls the exhaustiveness of the search. The higher the

4083

value, the longer the optimizaton time and possibly the better the

4084

resulting plan. The lower the value, the fewer alternative plans are

4085

estimated, but the more likely to get a bad QEP.

4086

4087

All intermediate and final results of the procedure are stored in 'join':

4088

- join->positions : modified for every partial QEP that is explored

4089

- join->best_positions: modified for the current best complete QEP

4090

- join->best_read : modified for the current best complete QEP

4091

- join->best_ref : might be partially reordered

4092

4093

The final optimal plan is stored in 'join->best_positions', and its

4094

corresponding cost in 'join->best_read'.

4095

4096

@note

4097

The following pseudocode describes the algorithm of 'greedy_search':

4098

4099

@code

4100

procedure greedy_search

4101

input: remaining_tables

4102

output: pplan;

4103

{

4104

pplan = <>;

4105

do {

4106

(t, a) = best_extension(pplan, remaining_tables);

4107

pplan = concat(pplan, (t, a));

4108

remaining_tables = remaining_tables - t;

4109

} while (remaining_tables != {})

4110

return pplan;

4111

}

4112

4113

@endcode

4114

where 'best_extension' is a placeholder for a procedure that selects the

4115

most "promising" of all tables in 'remaining_tables'.

4116

Currently this estimate is performed by calling

4117

'best_extension_by_limited_search' to evaluate all extensions of the

4118

current QEP of size 'search_depth', thus the complexity of 'greedy_search'

4119

mainly depends on that of 'best_extension_by_limited_search'.

4120

4121

@par

4122

If 'best_extension()' == 'best_extension_by_limited_search()', then the

4123

worst-case complexity of this algorithm is <=

4124

O(N*N^search_depth/search_depth). When serch_depth >= N, then the

4125

complexity of greedy_search is O(N!).

4126

4127

@par

4128

In the future, 'greedy_search' might be extended to support other

4129

implementations of 'best_extension', e.g. some simpler quadratic procedure.

4130

4131

@param join pointer to the structure providing all context info

4132

for the query

4133

@param remaining_tables set of tables not included into the partial plan yet

4134

@param search_depth controlls the exhaustiveness of the search

4135

@param prune_level the pruning heuristics that should be applied during

4136

4137

4138

@retval

4139

false ok

4140

@retval

4141

true Fatal error

4142

4143

static bool greedy_search(Join *join,

4144

table_map remaining_tables,

4145

uint32_t search_depth,

4146

uint32_t prune_level)

4147

{

4148

double record_count= 1.0;

4149

double read_time= 0.0;

4150

uint32_t idx= join->const_tables; // index into 'join->best_ref'

4151

uint32_t best_idx;

4152

uint32_t size_remain; // cardinality of remaining_tables

4153

optimizer::Position best_pos;

4154

JoinTable *best_table; // the next plan node to be added to the curr QEP

4155

4156

/* number of tables that remain to be optimized */

4157

size_remain= internal::my_count_bits(remaining_tables);

4158

4159

do {

4160

/* Find the extension of the current QEP with the lowest cost */

4161

join->best_read= DBL_MAX;

4162

if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,

4163

read_time, search_depth, prune_level))

4164

return true;

4165

4166

if (size_remain <= search_depth)

4167

{

4168

4169

'join->best_positions' contains a complete optimal extension of the

4170

current partial QEP.

4171

4172

return false;

4173

}

4174

4175

/* select the first table in the optimal extension as most promising */

4176

best_pos= join->getPosFromOptimalPlan(idx);

4177

best_table= best_pos.getJoinTable();

4178

4179

Each subsequent loop of 'best_extension_by_limited_search' uses

4180

'join->positions' for cost estimates, therefore we have to update its

4181

value.

4182

4183

join->setPosInPartialPlan(idx, best_pos);

4184

4185

4186

We need to make best_extension_by_limited_search aware of the fact

4187

that it's not starting from top level, but from a rather specific

4188

position in the list of nested joins.

4189

4190

check_interleaving_with_nj (best_table);

4191

4192

4193

4194

/* find the position of 'best_table' in 'join->best_ref' */

4195

best_idx= idx;

4196

JoinTable *pos= join->best_ref[best_idx];

4197

while (pos && best_table != pos)

4198

pos= join->best_ref[++best_idx];

4199

assert((pos != NULL)); // should always find 'best_table'

4200

/* move 'best_table' at the first free position in the array of joins */

4201

std::swap(join->best_ref[idx], join->best_ref[best_idx]);

4202

4203

/* compute the cost of the new plan extended with 'best_table' */

4204

optimizer::Position partial_pos= join->getPosFromPartialPlan(idx);

4205

record_count*= partial_pos.getFanout();

4206

read_time+= partial_pos.getCost();

4207

4208

remaining_tables&= ~(best_table->table->map);

4209

--size_remain;

4210

++idx;

4211

} while (true);

4212

}

4213

4214

4215

/**

4216

Find a good, possibly optimal, query execution plan (QEP) by a possibly

4217

exhaustive search.

4218

4219

The procedure searches for the optimal ordering of the query tables in set

4220

'remaining_tables' of size N, and the corresponding optimal access paths to

4221

each table. The choice of a table order and an access path for each table

4222

constitutes a query execution plan (QEP) that fully specifies how to

4223

execute the query.

4224

4225

The maximal size of the found plan is controlled by the parameter

4226

'search_depth'. When search_depth == N, the resulting plan is complete and

4227

can be used directly as a QEP. If search_depth < N, the found plan consists

4228

of only some of the query tables. Such "partial" optimal plans are useful

4229

only as input to query optimization procedures, and cannot be used directly

4230

to execute a query.

4231

4232

The algorithm begins with an empty partial plan stored in 'join->positions'

4233

and a set of N tables - 'remaining_tables'. Each step of the algorithm

4234

evaluates the cost of the partial plan extended by all access plans for

4235

each of the relations in 'remaining_tables', expands the current partial

4236

plan with the access plan that results in lowest cost of the expanded

4237

partial plan, and removes the corresponding relation from

4238

'remaining_tables'. The algorithm continues until it either constructs a

4239

complete optimal plan, or constructs an optimal plartial plan with size =

4240

search_depth.

4241

4242

The final optimal plan is stored in 'join->best_positions'. The

4243

corresponding cost of the optimal plan is in 'join->best_read'.

4244

4245

@note

4246

The procedure uses a recursive depth-first search where the depth of the

4247

recursion (and thus the exhaustiveness of the search) is controlled by the

4248

parameter 'search_depth'.

4249

4250

@note

4251

The pseudocode below describes the algorithm of

4252

'best_extension_by_limited_search'. The worst-case complexity of this

4253

algorithm is O(N*N^search_depth/search_depth). When serch_depth >= N, then

4254

the complexity of greedy_search is O(N!).

4255

4256

@code

4257

procedure best_extension_by_limited_search(

4258

pplan in, // in, partial plan of tables-joined-so-far

4259

pplan_cost, // in, cost of pplan

4260

remaining_tables, // in, set of tables not referenced in pplan

4261

best_plan_so_far, // in/out, best plan found so far

4262

best_plan_so_far_cost,// in/out, cost of best_plan_so_far

4263

search_depth) // in, maximum size of the plans being considered

4264

{

4265

for each table T from remaining_tables

4266

{

4267

// Calculate the cost of using table T as above

4268

cost = complex-series-of-calculations;

4269

4270

// Add the cost to the cost so far.

4271

pplan_cost+= cost;

4272

4273

if (pplan_cost >= best_plan_so_far_cost)

4274

// pplan_cost already too great, stop search

4275

continue;

4276

4277

pplan= expand pplan by best_access_method;

4278

remaining_tables= remaining_tables - table T;

4279

if (remaining_tables is not an empty set

4280

and

4281

search_depth > 1)

4282

{

4283

best_extension_by_limited_search(pplan, pplan_cost,

4284

remaining_tables,

4285

best_plan_so_far,

4286

best_plan_so_far_cost,

4287

search_depth - 1);

4288

}

4289

else

4290

{

4291

best_plan_so_far_cost= pplan_cost;

4292

best_plan_so_far= pplan;

4293

}

4294

}

4295

}

4296

@endcode

4297

4298

@note

4299

When 'best_extension_by_limited_search' is called for the first time,

4300

'join->best_read' must be set to the largest possible value (e.g. DBL_MAX).

4301

The actual implementation provides a way to optionally use pruning

4302

heuristic (controlled by the parameter 'prune_level') to reduce the search

4303

space by skipping some partial plans.

4304

4305

@note

4306

The parameter 'search_depth' provides control over the recursion

4307

depth, and thus the size of the resulting optimal plan.

4308

4309

@param join pointer to the structure providing all context info

4310

for the query

4311

@param remaining_tables set of tables not included into the partial plan yet

4312

@param idx length of the partial QEP in 'join->positions';

4313

since a depth-first search is used, also corresponds

4314

to the current depth of the search tree;

4315

also an index in the array 'join->best_ref';

4316

@param record_count estimate for the number of records returned by the

4317

best partial plan

4318

@param read_time the cost of the best partial plan

4319

@param search_depth maximum depth of the recursion and thus size of the

4320

found optimal plan

4321

(0 < search_depth <= join->tables+1).

4322

@param prune_level pruning heuristics that should be applied during

4323

optimization

4324

(values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS)

4325

4326

@retval

4327

false ok

4328

@retval

4329

true Fatal error

4330

4331

static bool best_extension_by_limited_search(Join *join,

4332

table_map remaining_tables,

4333

uint32_t idx,

4334

double record_count,

4335

double read_time,

4336

uint32_t search_depth,

4337

uint32_t prune_level)

4338

{

4339

Session *session= join->session;

4340

if (session->getKilled()) // Abort

4341

return true;

4342

4343

4344

'join' is a partial plan with lower cost than the best plan so far,

4345

so continue expanding it further with the tables in 'remaining_tables'.

4346

4347

JoinTable *s;

4348

double best_record_count= DBL_MAX;

4349

double best_read_time= DBL_MAX;

4350

optimizer::Position partial_pos;

4351

4352

for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)

4353

{

4354

table_map real_table_bit= s->table->map;

4355

if ((remaining_tables & real_table_bit) &&

4356

! (remaining_tables & s->dependent) &&

4357

(! idx || ! check_interleaving_with_nj(s)))

4358

{

4359

double current_record_count, current_read_time;

4360

4361

4362

psergey-insideout-todo:

4363

when best_access_path() detects it could do an InsideOut scan or

4364

some other scan, have it return an insideout scan and a flag that

4365

requests to "fork" this loop iteration. (Q: how does that behave

4366

when the depth is insufficient??)

4367

4368

/* Find the best access method from 's' to the current partial plan */

4369

best_access_path(join, s, session, remaining_tables, idx,

4370

record_count, read_time);

4371

/* Compute the cost of extending the plan with 's' */

4372

partial_pos= join->getPosFromPartialPlan(idx);

4373

current_record_count= record_count * partial_pos.getFanout();

4374

current_read_time= read_time + partial_pos.getCost();

4375

4376

/* Expand only partial plans with lower cost than the best QEP so far */

4377

if ((current_read_time +

4378

current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)

4379

{

4380

restore_prev_nj_state(s);

4381

continue;

4382

}

4383

4384

4385

Prune some less promising partial plans. This heuristic may miss

4386

the optimal QEPs, thus it results in a non-exhaustive search.

4387

4388

if (prune_level == 1)

4389

{

4390

if (best_record_count > current_record_count ||

4391

best_read_time > current_read_time ||

4392

(idx == join->const_tables && s->table == join->sort_by_table)) // 's' is the first table in the QEP

4393

{

4394

if (best_record_count >= current_record_count &&

4395

best_read_time >= current_read_time &&

4396

/* TODO: What is the reasoning behind this condition? */

4397

(! (s->key_dependent & remaining_tables) ||

4398

partial_pos.isConstTable()))

4399

{

4400

best_record_count= current_record_count;

4401

best_read_time= current_read_time;

4402

}

4403

}

4404

else

4405

{

4406

restore_prev_nj_state(s);

4407

continue;

4408

}

4409

}

4410

4411

if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )

4412

{ /* Recursively expand the current partial plan */

4413

std::swap(join->best_ref[idx], *pos);

4414

if (best_extension_by_limited_search(join,

4415

remaining_tables & ~real_table_bit,

4416

idx + 1,

4417

current_record_count,

4418

current_read_time,

4419

search_depth - 1,

4420

prune_level))

4421

return true;

4422

std::swap(join->best_ref[idx], *pos);

4423

}

4424

else

4425

{ /*

4426

'join' is either the best partial QEP with 'search_depth' relations,

4427

or the best complete QEP so far, whichever is smaller.

4428

4429

partial_pos= join->getPosFromPartialPlan(join->const_tables);

4430

current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;

4431

if (join->sort_by_table &&

4432

partial_pos.hasTableForSorting(join->sort_by_table))

4433

/* We have to make a temp table */

4434

current_read_time+= current_record_count;

4435

if ((search_depth == 1) || (current_read_time < join->best_read))

4436

{

4437

join->copyPartialPlanIntoOptimalPlan(idx + 1);

4438

join->best_read= current_read_time - 0.001;

4439

}

4440

}

4441

restore_prev_nj_state(s);

4442

}

4443

}

4444

return false;

4445

}

4446

4447

/**

4448

Heuristic procedure to automatically guess a reasonable degree of

4449

exhaustiveness for the greedy search procedure.

4450

4451

The procedure estimates the optimization time and selects a search depth

4452

big enough to result in a near-optimal QEP, that doesn't take too long to

4453

find. If the number of tables in the query exceeds some constant, then

4454

search_depth is set to this constant.

4455

4456

@param join pointer to the structure providing all context info for

4457

the query

4458

4459

@note

4460

This is an extremely simplistic implementation that serves as a stub for a

4461

more advanced analysis of the join. Ideally the search depth should be

4462

determined by learning from previous query optimizations, because it will

4463

depend on the CPU power (and other factors).

4464

4465

@todo

4466

this value should be determined dynamically, based on statistics:

4467

uint32_t max_tables_for_exhaustive_opt= 7;

4468

4469

@todo

4470

this value could be determined by some mapping of the form:

4471

depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]

4472

4473

@return

4474

A positive integer that specifies the search depth (and thus the

4475

exhaustiveness) of the depth-first search algorithm used by

4476

'greedy_search'.

4477

4478

static uint32_t determine_search_depth(Join *join)

4479

{

4480

uint32_t table_count= join->tables - join->const_tables;

4481

uint32_t search_depth;

4482

/* TODO: this value should be determined dynamically, based on statistics: */

4483

uint32_t max_tables_for_exhaustive_opt= 7;

4484

4485

if (table_count <= max_tables_for_exhaustive_opt)

4486

search_depth= table_count+1; // use exhaustive for small number of tables

4487

else

4488

4489

TODO: this value could be determined by some mapping of the form:

4490

depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]

4491

4492

search_depth= max_tables_for_exhaustive_opt; // use greedy search

4493

4494

return search_depth;

4495

}

4496

4497

static void make_simple_join(Join *join,Table *tmp_table)

4498

{

4499

4500

Reuse Table * and JoinTable if already allocated by a previous call

4501

to this function through Join::exec (may happen for sub-queries).

4502

4503

if (!join->table_reexec)

4504

{

4505

join->table_reexec= new (join->session->mem) Table*;

4506

if (join->tmp_join)

4507

join->tmp_join->table_reexec= join->table_reexec;

4508

}

4509

if (!join->join_tab_reexec)

4510

{

4511

join->join_tab_reexec= new (join->session->mem) JoinTable;

4512

if (join->tmp_join)

4513

join->tmp_join->join_tab_reexec= join->join_tab_reexec;

4514

}

4515

Table** tableptr= join->table_reexec;

4516

JoinTable* join_tab= join->join_tab_reexec;

4517

4518

join->join_tab=join_tab;

4519

join->table=tableptr; tableptr[0]=tmp_table;

4520

join->tables=1;

4521

join->const_tables=0;

4522

join->const_table_map=0;

4523

join->tmp_table_param.field_count= join->tmp_table_param.sum_func_count=

4524

join->tmp_table_param.func_count=0;

4525

join->tmp_table_param.copy_field=join->tmp_table_param.copy_field_end=0;

4526

join->first_record=join->sort_and_group=0;

4527

join->send_records=(ha_rows) 0;

4528

join->group=0;

4529

join->row_limit=join->unit->select_limit_cnt;

4530

join->do_send_rows = (join->row_limit) ? 1 : 0;

4531

4532

join_tab->table=tmp_table;

4533

join_tab->select=0;

4534

join_tab->select_cond=0;

4535

join_tab->quick=0;

4536

join_tab->type= AM_ALL; /* Map through all records */

4537

join_tab->keys.set(); /* test everything in quick */

4538

join_tab->info=0;

4539

join_tab->on_expr_ref=0;

4540

join_tab->last_inner= 0;

4541

join_tab->first_unmatched= 0;

4542

join_tab->ref.key = -1;

4543

join_tab->not_used_in_distinct=0;

4544

join_tab->read_first_record= join_init_read_record;

4545

join_tab->join=join;

4546

join_tab->ref.key_parts= 0;

4547

join_tab->read_record.init();

4548

tmp_table->status=0;

4549

tmp_table->null_row=0;

4550

}

4551

4552

/**

4553

Fill in outer join related info for the execution plan structure.

4554

4555

For each outer join operation left after simplification of the

4556

original query the function set up the following pointers in the linear

4557

structure join->join_tab representing the selected execution plan.

4558

The first inner table t0 for the operation is set to refer to the last

4559

inner table tk through the field t0->last_inner.

4560

Any inner table ti for the operation are set to refer to the first

4561

inner table ti->first_inner.

4562

The first inner table t0 for the operation is set to refer to the

4563

first inner table of the embedding outer join operation, if there is any,

4564

through the field t0->first_upper.

4565

The on expression for the outer join operation is attached to the

4566

corresponding first inner table through the field t0->on_expr_ref.

4567

Here ti are structures of the JoinTable type.

4568

4569

EXAMPLE. For the query:

4570

@code

4571

SELECT * FROM t1

4572

LEFT JOIN

4573

(t2, t3 LEFT JOIN t4 ON t3.a=t4.a)

4574

ON (t1.a=t2.a AND t1.b=t3.b)

4575

WHERE t1.c > 5,

4576

@endcode

4577

4578

given the execution plan with the table order t1,t2,t3,t4

4579

is selected, the following references will be set;

4580

t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2]

4581

t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2],

4582

on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to

4583

*t2->on_expr_ref, while t3.a=t4.a will be attached to *t4->on_expr_ref.

4584

4585

@param join reference to the info fully describing the query

4586

4587

@note

4588

The function assumes that the simplification procedure has been

4589

already applied to the join query (see simplify_joins).

4590

This function can be called only after the execution plan

4591

has been chosen.

4592

4593

static void make_outerjoin_info(Join *join)

4594

{

4595

for (uint32_t i=join->const_tables ; i < join->tables ; i++)

4596

{

4597

JoinTable *tab=join->join_tab+i;

4598

Table *table=tab->table;

4599

TableList *tbl= table->pos_in_table_list;

4600

TableList *embedding= tbl->getEmbedding();

4601

4602

if (tbl->outer_join)

4603

{

4604

4605

Table tab is the only one inner table for outer join.

4606

(Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a

4607

is in the query above.)

4608

4609

tab->last_inner= tab->first_inner= tab;

4610

tab->on_expr_ref= &tbl->on_expr;

4611

tab->cond_equal= tbl->cond_equal;

4612

if (embedding)

4613

tab->first_upper= embedding->getNestedJoin()->first_nested;

4614

}

4615

for ( ; embedding ; embedding= embedding->getEmbedding())

4616

{

4617

/* Ignore sj-nests: */

4618

if (!embedding->on_expr)

4619

continue;

4620

NestedJoin *nested_join= embedding->getNestedJoin();

4621

if (!nested_join->counter_)

4622

{

4623

4624

Table tab is the first inner table for nested_join.

4625

Save reference to it in the nested join structure.

4626

4627

nested_join->first_nested= tab;

4628

tab->on_expr_ref= &embedding->on_expr;

4629

tab->cond_equal= tbl->cond_equal;

4630

if (embedding->getEmbedding())

4631

tab->first_upper= embedding->getEmbedding()->getNestedJoin()->first_nested;

4632

}

4633

if (!tab->first_inner)

4634

tab->first_inner= nested_join->first_nested;

4635

if (++nested_join->counter_ < nested_join->join_list.size())

4636

break;

4637

/* Table tab is the last inner table for nested join. */

4638

nested_join->first_nested->last_inner= tab;

4639

}

4640

}

4641

return;

4642

}

4643

4644

static bool make_join_select(Join *join,

4645

optimizer::SqlSelect *select,

4646

COND *cond)

4647

{

4648

Session *session= join->session;

4649

optimizer::Position cur_pos;

4650

if (select)

4651

{

4652

add_not_null_conds(join);

4653

table_map used_tables;

4654

if (cond) /* Because of QUICK_GROUP_MIN_MAX_SELECT */

4655

{ /* there may be a select without a cond. */

4656

if (join->tables > 1)

4657

cond->update_used_tables(); // Tablenr may have changed

4658

if (join->const_tables == join->tables &&

4659

session->lex().current_select->master_unit() ==

4660

&session->lex().unit) // not upper level SELECT

4661

join->const_table_map|=RAND_TABLE_BIT;

4662

{ // Check const tables

4663

COND *const_cond=

4664

make_cond_for_table(cond,

4665

join->const_table_map,

4666

0, 1);

4667

for (JoinTable *tab= join->join_tab+join->const_tables;

4668

tab < join->join_tab+join->tables ; tab++)

4669

{

4670

if (*tab->on_expr_ref)

4671

{

4672

JoinTable *cond_tab= tab->first_inner;

4673

COND *tmp= make_cond_for_table(*tab->on_expr_ref,

4674

join->const_table_map,

4675

( table_map) 0, 0);

4676

if (!tmp)

4677

continue;

4678

tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);

4679

if (! tmp)

4680

return 1;

4681

tmp->quick_fix_field();

4682

cond_tab->select_cond= !cond_tab->select_cond ? tmp :

4683

new Item_cond_and(cond_tab->select_cond,

4684

tmp);

4685

if (! cond_tab->select_cond)

4686

return 1;

4687

cond_tab->select_cond->quick_fix_field();

4688

}

4689

}

4690

if (const_cond && ! const_cond->val_int())

4691

{

4692

return 1; // Impossible const condition

4693

}

4694

}

4695

}

4696

used_tables=((select->const_tables=join->const_table_map) |

4697

OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);

4698

for (uint32_t i=join->const_tables ; i < join->tables ; i++)

4699

{

4700

JoinTable *tab=join->join_tab+i;

4701

4702

first_inner is the X in queries like:

4703

SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X

4704

4705

JoinTable *first_inner_tab= tab->first_inner;

4706

table_map current_map= tab->table->map;

4707

bool use_quick_range=0;

4708

COND *tmp;

4709

4710

4711

Following force including random expression in last table condition.

4712

It solve problem with select like SELECT * FROM t1 WHERE rand() > 0.5

4713

4714

if (i == join->tables-1)

4715

current_map|= OUTER_REF_TABLE_BIT | RAND_TABLE_BIT;

4716

used_tables|=current_map;

4717

4718

if (tab->type == AM_REF && tab->quick &&

4719

(uint32_t) tab->ref.key == tab->quick->index &&

4720

tab->ref.key_length < tab->quick->max_used_key_length)

4721

{

4722

/* Range uses longer key; Use this instead of ref on key */

4723

tab->type= AM_ALL;

4724

use_quick_range= 1;

4725

tab->use_quick= 1;

4726

tab->ref.key= -1;

4727

tab->ref.key_parts= 0; // Don't use ref key.

4728

cur_pos= join->getPosFromOptimalPlan(i);

4729

cur_pos.setFanout(tab->quick->records);

4730

4731

We will use join cache here : prevent sorting of the first

4732

table only and sort at the end.

4733

4734

if (i != join->const_tables && join->tables > join->const_tables + 1)

4735

join->full_join= 1;

4736

}

4737

4738

if (join->full_join and not session->lex().current_select->is_cross and not cond)

4739

{

4740

my_error(ER_CARTESIAN_JOIN_ATTEMPTED, MYF(0));

4741

return 1;

4742

}

4743

4744

tmp= NULL;

4745

if (cond)

4746

tmp= make_cond_for_table(cond,used_tables,current_map, 0);

4747

if (cond && !tmp && tab->quick)

4748

{ // Outer join

4749

if (tab->type != AM_ALL)

4750

{

4751

4752

Don't use the quick method

4753

We come here in the case where we have 'key=constant' and

4754

the test is removed by make_cond_for_table()

4755

4756

delete tab->quick;

4757

tab->quick= 0;

4758

}

4759

else

4760

{

4761

4762

Hack to handle the case where we only refer to a table

4763

in the ON part of an OUTER JOIN. In this case we want the code

4764

below to check if we should use 'quick' instead.

4765

4766

tmp= new Item_int((int64_t) 1,1); // Always true

4767

}

4768

4769

}

4770

if (tmp || !cond || tab->type == AM_REF || tab->type == AM_REF_OR_NULL ||

4771

tab->type == AM_EQ_REF)

4772

{

4773

optimizer::SqlSelect *sel= tab->select= ((optimizer::SqlSelect*)session->mem.memdup(select, sizeof(*select)));

4774

4775

If tab is an inner table of an outer join operation,

4776

add a match guard to the pushed down predicate.

4777

The guard will turn the predicate on only after

4778

the first match for outer tables is encountered.

4779

4780

if (cond && tmp)

4781

{

4782

4783

Because of QUICK_GROUP_MIN_MAX_SELECT there may be a select without

4784

a cond, so neutralize the hack above.

4785

4786

if (! (tmp= add_found_match_trig_cond(first_inner_tab, tmp, 0)))

4787

return 1;

4788

tab->select_cond=sel->cond=tmp;

4789

}

4790

else

4791

tab->select_cond= sel->cond= NULL;

4792

4793

sel->head=tab->table;

4794

if (tab->quick)

4795

{

4796

/* Use quick key read if it's a constant and it's not used

4797

with key reading */

4798

if (tab->needed_reg.none() && tab->type != AM_EQ_REF

4799

&& (tab->type != AM_REF || (uint32_t) tab->ref.key == tab->quick->index))

4800

{

4801

sel->quick=tab->quick; // Use value from get_quick_...

4802

sel->quick_keys.reset();

4803

sel->needed_reg.reset();

4804

}

4805

else

4806

{

4807

delete tab->quick;

4808

}

4809

tab->quick= 0;

4810

}

4811

uint32_t ref_key= static_cast<uint32_t>(sel->head->reginfo.join_tab->ref.key + 1);

4812

if (i == join->const_tables && ref_key)

4813

{

4814

if (tab->const_keys.any() &&

4815

tab->table->reginfo.impossible_range)

4816

return 1;

4817

}

4818

else if (tab->type == AM_ALL && ! use_quick_range)

4819

{

4820

if (tab->const_keys.any() &&

4821

tab->table->reginfo.impossible_range)

4822

return 1; // Impossible range

4823

4824

We plan to scan all rows.

4825

Check again if we should use an index.

4826

We could have used an column from a previous table in

4827

the index if we are using limit and this is the first table

4828

4829

4830

cur_pos= join->getPosFromOptimalPlan(i);

4831

if ((cond && (! ((tab->keys & tab->const_keys) == tab->keys) && i > 0)) ||

4832

(! tab->const_keys.none() && (i == join->const_tables) &&

4833

(join->unit->select_limit_cnt < cur_pos.getFanout()) && ((join->select_options & OPTION_FOUND_ROWS) == false)))

4834

{

4835

/* Join with outer join condition */

4836

COND *orig_cond= sel->cond;

4837

sel->cond= and_conds(sel->cond, *tab->on_expr_ref);

4838

4839

4840

We can't call sel->cond->fix_fields,

4841

as it will break tab->on_expr if it's AND condition

4842

(fix_fields currently removes extra AND/OR levels).

4843

Yet attributes of the just built condition are not needed.

4844

Thus we call sel->cond->quick_fix_field for safety.

4845

4846

if (sel->cond && ! sel->cond->fixed)

4847

sel->cond->quick_fix_field();

4848

4849

if (sel->test_quick_select(session, tab->keys,

4850

used_tables & ~ current_map,

4851

(join->select_options &

4852

OPTION_FOUND_ROWS ?

4853

HA_POS_ERROR :

4854

join->unit->select_limit_cnt), 0,

4855

false) < 0)

4856

{

4857

4858

Before reporting "Impossible WHERE" for the whole query

4859

we have to check isn't it only "impossible ON" instead

4860

4861

sel->cond=orig_cond;

4862

if (! *tab->on_expr_ref ||

4863

sel->test_quick_select(session, tab->keys,

4864

used_tables & ~ current_map,

4865

(join->select_options &

4866

OPTION_FOUND_ROWS ?

4867

HA_POS_ERROR :

4868

join->unit->select_limit_cnt),0,

4869

false) < 0)

4870

return 1; // Impossible WHERE

4871

}

4872

else

4873

sel->cond=orig_cond;

4874

4875

/* Fix for EXPLAIN */

4876

if (sel->quick)

4877

{

4878

cur_pos= join->getPosFromOptimalPlan(i);

4879

cur_pos.setFanout(static_cast<double>(sel->quick->records));

4880

}

4881

}

4882

else

4883

{

4884

sel->needed_reg= tab->needed_reg;

4885

sel->quick_keys.reset();

4886

}

4887

if (!((tab->checked_keys & sel->quick_keys) == sel->quick_keys) ||

4888

!((tab->checked_keys & sel->needed_reg) == sel->needed_reg))

4889

{

4890

tab->keys= sel->quick_keys;

4891

tab->keys|= sel->needed_reg;

4892

tab->use_quick= (!sel->needed_reg.none() &&

4893

(select->quick_keys.none() ||

4894

(select->quick &&

4895

(select->quick->records >= 100L)))) ?

4896

2 : 1;

4897

sel->read_tables= used_tables & ~current_map;

4898

}

4899

if (i != join->const_tables && tab->use_quick != 2)

4900

{ /* Read with cache */

4901

if (cond &&

4902

(tmp=make_cond_for_table(cond,

4903

join->const_table_map |

4904

current_map,

4905

current_map, 0)))

4906

{

4907

tab->cache.select= (optimizer::SqlSelect*)session->mem.memdup(sel, sizeof(optimizer::SqlSelect));

4908

tab->cache.select->cond= tmp;

4909

tab->cache.select->read_tables= join->const_table_map;

4910

}

4911

}

4912

}

4913

}

4914

4915

4916

Push down conditions from all on expressions.

4917

Each of these conditions are guarded by a variable

4918

that turns if off just before null complemented row for

4919

outer joins is formed. Thus, the condition from an

4920

'on expression' are guaranteed not to be checked for

4921

the null complemented row.

4922

4923

4924

/* First push down constant conditions from on expressions */

4925

for (JoinTable *join_tab= join->join_tab+join->const_tables;

4926

join_tab < join->join_tab+join->tables ; join_tab++)

4927

{

4928

if (*join_tab->on_expr_ref)

4929

{

4930

JoinTable *cond_tab= join_tab->first_inner;

4931

tmp= make_cond_for_table(*join_tab->on_expr_ref,

4932

join->const_table_map,

4933

(table_map) 0, 0);

4934

if (!tmp)

4935

continue;

4936

tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);

4937

if (! tmp)

4938

return 1;

4939

tmp->quick_fix_field();

4940

cond_tab->select_cond= !cond_tab->select_cond ? tmp :

4941

new Item_cond_and(cond_tab->select_cond,tmp);

4942

if (! cond_tab->select_cond)

4943

return 1;

4944

cond_tab->select_cond->quick_fix_field();

4945

}

4946

}

4947

4948

/* Push down non-constant conditions from on expressions */

4949

JoinTable *last_tab= tab;

4950

while (first_inner_tab && first_inner_tab->last_inner == last_tab)

4951

{

4952

4953

Table tab is the last inner table of an outer join.

4954

An on expression is always attached to it.

4955

4956

COND *on_expr= *first_inner_tab->on_expr_ref;

4957

4958

table_map used_tables2= (join->const_table_map |

4959

OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);

4960

for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++)

4961

{

4962

current_map= tab->table->map;

4963

used_tables2|= current_map;

4964

COND *tmp_cond= make_cond_for_table(on_expr, used_tables2,

4965

current_map, 0);

4966

if (tmp_cond)

4967

{

4968

JoinTable *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;

4969

4970

First add the guards for match variables of

4971

all embedding outer join operations.

4972

4973

if (!(tmp_cond= add_found_match_trig_cond(cond_tab->first_inner,

4974

tmp_cond,

4975

first_inner_tab)))

4976

return 1;

4977

4978

Now add the guard turning the predicate off for

4979

the null complemented row.

4980

4981

tmp_cond= new Item_func_trig_cond(tmp_cond,

4982

&first_inner_tab->

4983

not_null_compl);

4984

if (tmp_cond)

4985

tmp_cond->quick_fix_field();

4986

/* Add the predicate to other pushed down predicates */

4987

cond_tab->select_cond= !cond_tab->select_cond ? tmp_cond :

4988

new Item_cond_and(cond_tab->select_cond,

4989

tmp_cond);

4990

if (! cond_tab->select_cond)

4991

return 1;

4992

cond_tab->select_cond->quick_fix_field();

4993

}

4994

}

4995

first_inner_tab= first_inner_tab->first_upper;

4996

}

4997

}

4998

}

4999

return 0;

5000

}

5001

5002

5003

Plan refinement stage: do various set ups for the executioner

5004

5005

SYNOPSIS

5006

make_join_readinfo()

5007

join Join being processed

5008

options Join's options (checking for SELECT_DESCRIBE,

5009

SELECT_NO_JOIN_CACHE)

5010

no_jbuf_after Don't use join buffering after table with this number.

5011

5012

DESCRIPTION

5013

Plan refinement stage: do various set ups for the executioner

5014

- set up use of join buffering

5015

- push index conditions

5016

- increment counters

5017

- etc

5018

5019

RETURN

5020

false - OK

5021

true - Out of memory

5022

5023

static void make_join_readinfo(Join& join)

5024

{

5025

bool sorted= true;

5026

5027

for (uint32_t i= join.const_tables; i < join.tables; i++)

5028

{

5029

JoinTable *tab=join.join_tab+i;

5030

Table *table=tab->table;

5031

tab->read_record.table= table;

5032

tab->read_record.cursor= table->cursor;

5033

tab->next_select=sub_select; /* normal select */

5034

5035

TODO: don't always instruct first table's ref/range access method to

5036

produce sorted output.

5037

5038

tab->sorted= sorted;

5039

sorted= false; // only first must be sorted

5040

5041

if (tab->insideout_match_tab)

5042

{

5043

tab->insideout_buf= join.session->mem.alloc(tab->table->key_info[tab->index].key_length);

5044

}

5045

5046

optimizer::AccessMethodFactory::create(tab->type)->getStats(*table, *tab);

5047

}

5048

5049

join.join_tab[join.tables-1].next_select= NULL; /* Set by do_select */

5050

}

5051

5052

/** Update the dependency map for the tables. */

5053

static void update_depend_map(Join *join)

5054

{

5055

JoinTable *join_tab=join->join_tab, *end=join_tab+join->tables;

5056

5057

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

5058

{

5059

table_reference_st *ref= &join_tab->ref;

5060

table_map depend_map= 0;

5061

Item **item=ref->items;

5062

uint32_t i;

5063

for (i=0 ; i < ref->key_parts ; i++,item++)

5064

depend_map|=(*item)->used_tables();

5065

ref->depend_map=depend_map & ~OUTER_REF_TABLE_BIT;

5066

depend_map&= ~OUTER_REF_TABLE_BIT;

5067

for (JoinTable **tab=join->map2table; depend_map; tab++,depend_map>>=1 )

5068

{

5069

if (depend_map & 1)

5070

ref->depend_map|=(*tab)->ref.depend_map;

5071

}

5072

}

5073

}

5074

5075

/** Update the dependency map for the sort order. */

5076

static void update_depend_map(Join *join, Order *order)

5077

{

5078

for (; order ; order=order->next)

5079

{

5080

table_map depend_map;

5081

order->item[0]->update_used_tables();

5082

order->depend_map=depend_map=order->item[0]->used_tables();

5083

// Not item_sum(), RAND() and no reference to table outside of sub select

5084

if (!(order->depend_map & (OUTER_REF_TABLE_BIT | RAND_TABLE_BIT))

5085

&& !order->item[0]->with_sum_func)

5086

{

5087

for (JoinTable **tab=join->map2table; depend_map; tab++, depend_map>>=1)

5088

{

5089

if (depend_map & 1)

5090

order->depend_map|=(*tab)->ref.depend_map;

5091

}

5092

}

5093

}

5094

}

5095

5096

/**

5097

Remove all constants and check if order_st only contains simple

5098

expressions.

5099

5100

simple_order is set to 1 if sort_order only uses fields from head table

5101

and the head table is not a LEFT JOIN table.

5102

5103

@param join Join handler

5104

@param first_order List of SORT or GROUP order

5105

@param cond WHERE statement

5106

@param change_list Set to 1 if we should remove things from list.

5107

If this is not set, then only simple_order is

5108

calculated.

5109

@param simple_order Set to 1 if we are only using simple expressions

5110

5111

@return

5112

Returns new sort order

5113

5114

static Order *remove_constants(Join *join,Order *first_order, COND *cond, bool change_list, bool *simple_order)

5115

{

5116

if (join->tables == join->const_tables)

5117

return change_list ? 0 : first_order; // No need to sort

5118

5119

Order *order,**prev_ptr;

5120

table_map first_table= join->join_tab[join->const_tables].table->map;

5121

table_map not_const_tables= ~join->const_table_map;

5122

table_map ref;

5123

5124

prev_ptr= &first_order;

5125

*simple_order= *join->join_tab[join->const_tables].on_expr_ref ? 0 : 1;

5126

5127

/* NOTE: A variable of not_const_tables ^ first_table; breaks gcc 2.7 */

5128

5129

update_depend_map(join, first_order);

5130

for (order=first_order; order ; order=order->next)

5131

{

5132

table_map order_tables=order->item[0]->used_tables();

5133

if (order->item[0]->with_sum_func)

5134

*simple_order=0; // Must do a temp table to sort

5135

else if (!(order_tables & not_const_tables))

5136

{

5137

if (order->item[0]->with_subselect)

5138

order->item[0]->val_str(&order->item[0]->str_value);

5139

continue; // skip const item

5140

}

5141

else

5142

{

5143

if (order_tables & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT))

5144

*simple_order=0;

5145

else

5146

{

5147

Item *comp_item=0;

5148

if (cond && const_expression_in_where(cond,order->item[0], &comp_item))

5149

{

5150

continue;

5151

}

5152

if ((ref=order_tables & (not_const_tables ^ first_table)))

5153

{

5154

if (!(order_tables & first_table) &&

5155

only_eq_ref_tables(join,first_order, ref))

5156

{

5157

continue;

5158

}

5159

*simple_order=0; // Must do a temp table to sort

5160

}

5161

}

5162

}

5163

if (change_list)

5164

*prev_ptr= order; // use this entry

5165

prev_ptr= &order->next;

5166

}

5167

if (change_list)

5168

*prev_ptr=0;

5169

if (prev_ptr == &first_order) // Nothing to sort/group

5170

*simple_order=1;

5171

return(first_order);

5172

}

5173

5174

static void return_zero_rows(Join *join, select_result *result, TableList *tables, List<Item> &fields, bool send_row, uint64_t select_options, const char *info, Item *having)

5175

{

5176

if (select_options & SELECT_DESCRIBE)

5177

{

5178

optimizer::ExplainPlan planner(join, false, false, false, info);

5179

planner.printPlan();

5180

return;

5181

}

5182

5183

join->join_free();

5184

5185

if (send_row)

5186

{

5187

for (TableList *table= tables; table; table= table->next_leaf)

5188

table->table->mark_as_null_row(); // All fields are NULL

5189

if (having && having->val_int() == 0)

5190

send_row=0;

5191

}

5192

result->send_fields(fields);

5193

if (send_row)

5194

{

5195

List<Item>::iterator it(fields.begin());

5196

while (Item* item= it++)

5197

item->no_rows_in_result();

5198

result->send_data(fields);

5199

}

5200

result->send_eof(); // Should be safe

5201

/* Update results for FOUND_ROWS */

5202

join->session->limit_found_rows= join->session->examined_row_count= 0;

5203

}

5204

5205

/**

5206

Simplify joins replacing outer joins by inner joins whenever it's

5207

possible.

5208

5209

The function, during a retrieval of join_list, eliminates those

5210

outer joins that can be converted into inner join, possibly nested.

5211

It also moves the on expressions for the converted outer joins

5212

and from inner joins to conds.

5213

The function also calculates some attributes for nested joins:

5214

- used_tables

5215

- not_null_tables

5216

- dep_tables.

5217

- on_expr_dep_tables

5218

The first two attributes are used to test whether an outer join can

5219

be substituted for an inner join. The third attribute represents the

5220

relation 'to be dependent on' for tables. If table t2 is dependent

5221

on table t1, then in any evaluated execution plan table access to

5222

table t2 must precede access to table t2. This relation is used also

5223

to check whether the query contains invalid cross-references.

5224

The forth attribute is an auxiliary one and is used to calculate

5225

dep_tables.

5226

As the attribute dep_tables qualifies possibles orders of tables in the

5227

execution plan, the dependencies required by the straight join

5228

modifiers are reflected in this attribute as well.

5229

The function also removes all braces that can be removed from the join

5230

expression without changing its meaning.

5231

5232

@note

5233

An outer join can be replaced by an inner join if the where condition

5234

or the on expression for an embedding nested join contains a conjunctive

5235

predicate rejecting null values for some attribute of the inner tables.

5236

5237

E.g. in the query:

5238

@code

5239

SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a WHERE t2.b < 5

5240

@endcode

5241

the predicate t2.b < 5 rejects nulls.

5242

The query is converted first to:

5243

@code

5244

SELECT * FROM t1 INNER JOIN t2 ON t2.a=t1.a WHERE t2.b < 5

5245

@endcode

5246

then to the equivalent form:

5247

@code

5248

SELECT * FROM t1, t2 ON t2.a=t1.a WHERE t2.b < 5 AND t2.a=t1.a

5249

@endcode

5250

5251

5252

Similarly the following query:

5253

@code

5254

SELECT * from t1 LEFT JOIN (t2, t3) ON t2.a=t1.a t3.b=t1.b

5255

WHERE t2.c < 5

5256

@endcode

5257

is converted to:

5258

@code

5259

SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b

5260

5261

@endcode

5262

5263

One conversion might trigger another:

5264

@code

5265

SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a

5266

LEFT JOIN t3 ON t3.b=t2.b

5267

WHERE t3 IS NOT NULL =>

5268

SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a, t3

5269

WHERE t3 IS NOT NULL AND t3.b=t2.b =>

5270

SELECT * FROM t1, t2, t3

5271

WHERE t3 IS NOT NULL AND t3.b=t2.b AND t2.a=t1.a

5272

@endcode

5273

5274

The function removes all unnecessary braces from the expression

5275

produced by the conversions.

5276

E.g.

5277

@code

5278

SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b

5279

@endcode

5280

finally is converted to:

5281

@code

5282

SELECT * FROM t1, t2, t3 WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b

5283

5284

@endcode

5285

5286

5287

It also will remove braces from the following queries:

5288

@code

5289

SELECT * from (t1 LEFT JOIN t2 ON t2.a=t1.a) LEFT JOIN t3 ON t3.b=t2.b

5290

SELECT * from (t1, (t2,t3)) WHERE t1.a=t2.a AND t2.b=t3.b.

5291

@endcode

5292

5293

The benefit of this simplification procedure is that it might return

5294

a query for which the optimizer can evaluate execution plan with more

5295

join orders. With a left join operation the optimizer does not

5296

consider any plan where one of the inner tables is before some of outer

5297

tables.

5298

5299

IMPLEMENTATION

5300

The function is implemented by a recursive procedure. On the recursive

5301

ascent all attributes are calculated, all outer joins that can be

5302

converted are replaced and then all unnecessary braces are removed.

5303

As join list contains join tables in the reverse order sequential

5304

elimination of outer joins does not require extra recursive calls.

5305

5306

SEMI-JOIN NOTES

5307

Remove all semi-joins that have are within another semi-join (i.e. have

5308

an "ancestor" semi-join nest)

5309

5310

EXAMPLES

5311

Here is an example of a join query with invalid cross references:

5312

@code

5313

SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t3.a LEFT JOIN t3 ON t3.b=t1.b

5314

@endcode

5315

5316

@param join reference to the query info

5317

@param join_list list representation of the join to be converted

5318

@param conds conditions to add on expressions for converted joins

5319

@param top true <=> conds is the where condition

5320

5321

@return

5322

- The new condition, if success

5323

- 0, otherwise

5324

5325

static COND *simplify_joins(Join *join, List<TableList> *join_list, COND *conds, bool top)

5326

{

5327

NestedJoin *nested_join;

5328

TableList *prev_table= 0;

5329

List<TableList>::iterator li(join_list->begin());

5330

5331

5332

Try to simplify join operations from join_list.

5333

The most outer join operation is checked for conversion first.

5334

5335

while (TableList* table= li++)

5336

{

5337

table_map used_tables;

5338

table_map not_null_tables= (table_map) 0;

5339

5340

if ((nested_join= table->getNestedJoin()))

5341

{

5342

5343

If the element of join_list is a nested join apply

5344

the procedure to its nested join list first.

5345

5346

if (table->on_expr)

5347

{

5348

Item *expr= table->on_expr;

5349

5350

If an on expression E is attached to the table,

5351

check all null rejected predicates in this expression.

5352

If such a predicate over an attribute belonging to

5353

an inner table of an embedded outer join is found,

5354

the outer join is converted to an inner join and

5355

the corresponding on expression is added to E.

5356

5357

expr= simplify_joins(join, &nested_join->join_list, expr, false);

5358

5359

if (!table->prep_on_expr || expr != table->on_expr)

5360

{

5361

assert(expr);

5362

5363

table->on_expr= expr;

5364

table->prep_on_expr= expr->copy_andor_structure(join->session);

5365

}

5366

}

5367

nested_join->used_tables= (table_map) 0;

5368

nested_join->not_null_tables=(table_map) 0;

5369

conds= simplify_joins(join, &nested_join->join_list, conds, top);

5370

used_tables= nested_join->used_tables;

5371

not_null_tables= nested_join->not_null_tables;

5372

}

5373

else

5374

{

5375

if (!table->prep_on_expr)

5376

table->prep_on_expr= table->on_expr;

5377

used_tables= table->table->map;

5378

if (conds)

5379

not_null_tables= conds->not_null_tables();

5380

}

5381

5382

if (table->getEmbedding())

5383

{

5384

table->getEmbedding()->getNestedJoin()->used_tables|= used_tables;

5385

table->getEmbedding()->getNestedJoin()->not_null_tables|= not_null_tables;

5386

}

5387

5388

if (!table->outer_join || (used_tables & not_null_tables))

5389

{

5390

5391

For some of the inner tables there are conjunctive predicates

5392

that reject nulls => the outer join can be replaced by an inner join.

5393

5394

table->outer_join= 0;

5395

if (table->on_expr)

5396

{

5397

/* Add ON expression to the WHERE or upper-level ON condition. */

5398

if (conds)

5399

{

5400

conds= and_conds(conds, table->on_expr);

5401

conds->top_level_item();

5402

/* conds is always a new item as both cond and on_expr existed */

5403

assert(!conds->fixed);

5404

conds->fix_fields(join->session, &conds);

5405

}

5406

else

5407

conds= table->on_expr;

5408

table->prep_on_expr= table->on_expr= 0;

5409

}

5410

}

5411

5412

if (!top)

5413

continue;

5414

5415

5416

Only inner tables of non-convertible outer joins

5417

remain with on_expr.

5418

5419

if (table->on_expr)

5420

{

5421

table->setDepTables(table->getDepTables() | table->on_expr->used_tables());

5422

if (table->getEmbedding())

5423

{

5424

table->setDepTables(table->getDepTables() & ~table->getEmbedding()->getNestedJoin()->used_tables);

5425

5426

Embedding table depends on tables used

5427

in embedded on expressions.

5428

5429

table->getEmbedding()->setOnExprDepTables(table->getEmbedding()->getOnExprDepTables() & table->on_expr->used_tables());

5430

}

5431

else

5432

table->setDepTables(table->getDepTables() & ~table->table->map);

5433

}

5434

5435

if (prev_table)

5436

{

5437

//If this is straight join, set prev table to be dependent on all tables

5438

//from this nested join, so that correct join order is selected.

5439

if ((test(join->select_options & SELECT_STRAIGHT_JOIN)) ||

5440

prev_table->straight)

5441

prev_table->setDepTables(prev_table->getDepTables() | used_tables);

5442

if (prev_table->on_expr)

5443

{

5444

prev_table->setDepTables(prev_table->getDepTables() | table->getOnExprDepTables());

5445

table_map prev_used_tables= prev_table->getNestedJoin() ?

5446

prev_table->getNestedJoin()->used_tables :

5447

prev_table->table->map;

5448

5449

If on expression contains only references to inner tables

5450

we still make the inner tables dependent on the outer tables.

5451

It would be enough to set dependency only on one outer table

5452

for them. Yet this is really a rare case.

5453

5454

if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))

5455

prev_table->setDepTables(prev_table->getDepTables() | used_tables);

5456

}

5457

}

5458

prev_table= table;

5459

}

5460

5461

5462

Flatten nested joins that can be flattened.

5463

no ON expression and not a semi-join => can be flattened.

5464

5465

li= join_list->begin();

5466

while (TableList* table= li++)

5467

{

5468

nested_join= table->getNestedJoin();

5469

if (nested_join && !table->on_expr)

5470

{

5471

List<TableList>::iterator it(nested_join->join_list.begin());

5472

while (TableList* tbl= it++)

5473

{

5474

tbl->setEmbedding(table->getEmbedding());

5475

tbl->setJoinList(table->getJoinList());

5476

}

5477

li.replace(nested_join->join_list);

5478

}

5479

}

5480

return(conds);

5481

}

5482

5483

static int remove_duplicates(Join *join, Table *entry,List<Item> &fields, Item *having)

5484

{

5485

entry->reginfo.lock_type=TL_WRITE;

5486

5487

/* Calculate how many saved fields there is in list */

5488

uint32_t field_count= 0;

5489

List<Item>::iterator it(fields.begin());

5490

while (Item* item=it++)

5491

{

5492

if (item->get_tmp_table_field() && ! item->const_item())

5493

field_count++;

5494

}

5495

5496

if (!field_count && !(join->select_options & OPTION_FOUND_ROWS) && !having)

5497

{ // only const items with no OPTION_FOUND_ROWS

5498

join->unit->select_limit_cnt= 1; // Only send first row

5499

return 0;

5500

}

5501

Field **first_field=entry->getFields() + entry->getShare()->sizeFields() - field_count;

5502

uint32_t offset= field_count ? entry->getField(entry->getShare()->sizeFields() - field_count)->offset(entry->getInsertRecord()) : 0;

5503

uint32_t reclength= entry->getShare()->getRecordLength() - offset;

5504

5505

entry->free_io_cache(); // Safety

5506

entry->cursor->info(HA_STATUS_VARIABLE);

5507

int error;

5508

if (entry->getShare()->db_type() == heap_engine ||

5509

(!entry->getShare()->blob_fields &&

5510

((ALIGN_SIZE(reclength) + HASH_OVERHEAD) * entry->cursor->stats.records < join->session->variables.sortbuff_size)))

5511

{

5512

error= remove_dup_with_hash_index(join->session, entry, field_count, first_field, reclength, having);

5513

}

5514

else

5515

{

5516

error= remove_dup_with_compare(join->session, entry, first_field, offset, having);

5517

}

5518

free_blobs(first_field);

5519

return error;

5520

}

5521

5522

/**

5523

Function to setup clauses without sum functions.

5524

5525

static int setup_without_group(Session *session,

5526

Item **ref_pointer_array,

5527

TableList *tables,

5528

TableList *,

5529

List<Item> &fields,

5530

List<Item> &all_fields,

5531

COND **conds,

5532

Order *order,

5533

Order *group,

5534

bool *hidden_group_fields)

5535

{

5536

int res;

5537

nesting_map save_allow_sum_func=session->lex().allow_sum_func;

5538

5539

session->lex().allow_sum_func&= ~(1 << session->lex().current_select->nest_level);

5540

res= session->setup_conds(tables, conds);

5541

5542

session->lex().allow_sum_func|= 1 << session->lex().current_select->nest_level;

5543

res= res || setup_order(session, ref_pointer_array, tables, fields, all_fields, order);

5544

session->lex().allow_sum_func&= ~(1 << session->lex().current_select->nest_level);

5545

res= res || setup_group(session, ref_pointer_array, tables, fields, all_fields, group, hidden_group_fields);

5546

session->lex().allow_sum_func= save_allow_sum_func;

5547

return res;

5548

}

5549

5550

/**

5551

Calculate the best possible join and initialize the join structure.

5552

5553

@retval

5554

0 ok

5555

@retval

5556

1 Fatal error

5557

5558

static bool make_join_statistics(Join *join, TableList *tables, COND *conds, DYNAMIC_ARRAY *keyuse_array)

5559

{

5560

int error;

5561

Table *table;

5562

uint32_t i;

5563

uint32_t table_count;

5564

uint32_t const_count;

5565

uint32_t key;

5566

table_map found_const_table_map;

5567

table_map all_table_map;

5568

table_map found_ref;

5569

table_map refs;

5570

key_map const_ref;

5571

key_map eq_part;

5572

Table **table_vector= NULL;

5573

JoinTable *stat= NULL;

5574

JoinTable *stat_end= NULL;

5575

JoinTable *s= NULL;

5576

JoinTable **stat_ref= NULL;

5577

optimizer::KeyUse *keyuse= NULL;

5578

optimizer::KeyUse *start_keyuse= NULL;

5579

table_map outer_join= 0;

5580

vector<optimizer::SargableParam> sargables;

5581

JoinTable *stat_vector[MAX_TABLES+1];

5582

optimizer::Position *partial_pos;

5583

5584

table_count= join->tables;

5585

stat= (JoinTable*) join->session->mem.calloc(sizeof(JoinTable)*table_count);

5586

stat_ref= new (join->session->mem) JoinTable*[MAX_TABLES];

5587

table_vector= new (join->session->mem) Table*[2 * table_count];

5588

5589

join->best_ref=stat_vector;

5590

5591

stat_end=stat+table_count;

5592

found_const_table_map= all_table_map=0;

5593

const_count=0;

5594

5595

for (s= stat, i= 0;

5596

tables;

5597

s++, tables= tables->next_leaf, i++)

5598

{

5599

TableList *embedding= tables->getEmbedding();

5600

stat_vector[i]=s;

5601

s->keys.reset();

5602

s->const_keys.reset();

5603

s->checked_keys.reset();

5604

s->needed_reg.reset();

5605

table_vector[i]=s->table=table=tables->table;

5606

table->pos_in_table_list= tables;

5607

assert(table->cursor);

5608

error= table->cursor->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);

5609

if (error)

5610

{

5611

table->print_error(error, MYF(0));

5612

return 1;

5613

}

5614

table->quick_keys.reset();

5615

table->reginfo.join_tab=s;

5616

table->reginfo.not_exists_optimize=0;

5617

memset(table->const_key_parts, 0, sizeof(key_part_map)*table->getShare()->sizeKeys());

5618

all_table_map|= table->map;

5619

s->join=join;

5620

s->info=0; // For describe

5621

5622

s->dependent= tables->getDepTables();

5623

s->key_dependent= 0;

5624

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

5625

5626

s->on_expr_ref= &tables->on_expr;

5627

if (*s->on_expr_ref)

5628

{

5629

/* s is the only inner table of an outer join */

5630

if (!table->cursor->stats.records && !embedding)

5631

{ // Empty table

5632

s->dependent= 0; // Ignore LEFT JOIN depend.

5633

set_position(join, const_count++, s, NULL);

5634

continue;

5635

}

5636

outer_join|= table->map;

5637

s->embedding_map.reset();

5638

for (;embedding; embedding= embedding->getEmbedding())

5639

s->embedding_map|= embedding->getNestedJoin()->nj_map;

5640

continue;

5641

}

5642

if (embedding && !(false && ! embedding->getEmbedding()))

5643

{

5644

/* s belongs to a nested join, maybe to several embedded joins */

5645

s->embedding_map.reset();

5646

5647

{

5648

NestedJoin *nested_join= embedding->getNestedJoin();

5649

s->embedding_map|= nested_join->nj_map;

5650

s->dependent|= embedding->getDepTables();

5651

embedding= embedding->getEmbedding();

5652

outer_join|= nested_join->used_tables;

5653

}

5654

while (embedding);

5655

continue;

5656

}

5657

if ((table->cursor->stats.records <= 1) && !s->dependent &&

5658

(table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&

5659

!join->no_const_tables)

5660

{

5661

set_position(join, const_count++, s, NULL);

5662

}

5663

}

5664

stat_vector[i]=0;

5665

join->outer_join=outer_join;

5666

5667

if (join->outer_join)

5668

{

5669

5670

Build transitive closure for relation 'to be dependent on'.

5671

This will speed up the plan search for many cases with outer joins,

5672

as well as allow us to catch illegal cross references/

5673

Warshall's algorithm is used to build the transitive closure.

5674

As we use bitmaps to represent the relation the complexity

5675

of the algorithm is O((number of tables)^2).

5676

5677

for (i= 0; i < table_count; i++)

5678

{

5679

uint32_t j;

5680

table= stat[i].table;

5681

5682

if (!table->reginfo.join_tab->dependent)

5683

continue;

5684

5685

for (j= 0, s= stat; j < table_count; j++, s++)

5686

{

5687

if (s->dependent & table->map)

5688

{

5689

table_map was_dependent= s->dependent;

5690

s->dependent |= table->reginfo.join_tab->dependent;

5691

if (i > j && s->dependent != was_dependent)

5692

{

5693

i= j= 1;

5694

break;

5695

}

5696

}

5697

}

5698

}

5699

/* Catch illegal cross references for outer joins */

5700

for (i= 0, s= stat ; i < table_count ; i++, s++)

5701

{

5702

if (s->dependent & s->table->map)

5703

{

5704

join->tables=0; // Don't use join->table

5705

my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));

5706

return 1;

5707

}

5708

if (outer_join & s->table->map)

5709

s->table->maybe_null= 1;

5710

5711

s->key_dependent= s->dependent;

5712

}

5713

}

5714

5715

if (conds || outer_join)

5716

update_ref_and_keys(join->session, keyuse_array, stat, join->tables, conds, join->cond_equal, ~outer_join, join->select_lex, sargables);

5717

5718

/* Read tables with 0 or 1 rows (system tables) */

5719

join->const_table_map= 0;

5720

5721

optimizer::Position *p_pos= join->getFirstPosInPartialPlan();

5722

optimizer::Position *p_end= join->getSpecificPosInPartialPlan(const_count);

5723

while (p_pos < p_end)

5724

{

5725

int tmp;

5726

s= p_pos->getJoinTable();

5727

s->type= AM_SYSTEM;

5728

join->const_table_map|=s->table->map;

5729

if ((tmp= s->joinReadConstTable(p_pos)))

5730

{

5731

if (tmp > 0)

5732

return 1; // Fatal error

5733

}

5734

else

5735

found_const_table_map|= s->table->map;

5736

p_pos++;

5737

}

5738

5739

/* loop until no more const tables are found */

5740

int ref_changed;

5741

5742

{

5743

more_const_tables_found:

5744

ref_changed = 0;

5745

found_ref=0;

5746

5747

5748

We only have to loop from stat_vector + const_count as

5749

set_position() will move all const_tables first in stat_vector

5750

5751

5752

for (JoinTable **pos= stat_vector+const_count; (s= *pos); pos++)

5753

{

5754

table= s->table;

5755

5756

5757

If equi-join condition by a key is null rejecting and after a

5758

substitution of a const table the key value happens to be null

5759

then we can state that there are no matches for this equi-join.

5760

5761

if ((keyuse= s->keyuse) && *s->on_expr_ref && s->embedding_map.none())

5762

{

5763

5764

When performing an outer join operation if there are no matching rows

5765

for the single row of the outer table all the inner tables are to be

5766

null complemented and thus considered as constant tables.

5767

Here we apply this consideration to the case of outer join operations

5768

with a single inner table only because the case with nested tables

5769

would require a more thorough analysis.

5770

TODO. Apply single row substitution to null complemented inner tables

5771

for nested outer join operations.

5772

5773

while (keyuse->getTable() == table)

5774

{

5775

if (! (keyuse->getVal()->used_tables() & ~join->const_table_map) &&

5776

keyuse->getVal()->is_null() && keyuse->isNullRejected())

5777

{

5778

s->type= AM_CONST;

5779

table->mark_as_null_row();

5780

found_const_table_map|= table->map;

5781

join->const_table_map|= table->map;

5782

set_position(join, const_count++, s, NULL);

5783

goto more_const_tables_found;

5784

}

5785

keyuse++;

5786

}

5787

}

5788

5789

if (s->dependent) // If dependent on some table

5790

{

5791

// All dep. must be constants

5792

if (s->dependent & ~(found_const_table_map))

5793

continue;

5794

if (table->cursor->stats.records <= 1L &&

5795

(table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&

5796

!table->pos_in_table_list->getEmbedding())

5797

{ // system table

5798

int tmp= 0;

5799

s->type= AM_SYSTEM;

5800

join->const_table_map|=table->map;

5801

set_position(join, const_count++, s, NULL);

5802

partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);

5803

if ((tmp= s->joinReadConstTable(partial_pos)))

5804

{

5805

if (tmp > 0)

5806

return 1; // Fatal error

5807

}

5808

else

5809

found_const_table_map|= table->map;

5810

continue;

5811

}

5812

}

5813

/* check if table can be read by key or table only uses const refs */

5814

if ((keyuse=s->keyuse))

5815

{

5816

s->type= AM_REF;

5817

while (keyuse->getTable() == table)

5818

{

5819

start_keyuse= keyuse;

5820

key= keyuse->getKey();

5821

s->keys.set(key); // QQ: remove this ?

5822

5823

refs= 0;

5824

const_ref.reset();

5825

eq_part.reset();

5826

5827

{

5828

if (keyuse->getVal()->type() != Item::NULL_ITEM &&

5829

! keyuse->getOptimizeFlags())

5830

{

5831

if (! ((~found_const_table_map) & keyuse->getUsedTables()))

5832

const_ref.set(keyuse->getKeypart());

5833

else

5834

refs|= keyuse->getUsedTables();

5835

eq_part.set(keyuse->getKeypart());

5836

}

5837

keyuse++;

5838

} while (keyuse->getTable() == table && keyuse->getKey() == key);

5839

5840

if (is_keymap_prefix(eq_part, table->key_info[key].key_parts) &&

5841

! table->pos_in_table_list->getEmbedding())

5842

{

5843

if ((table->key_info[key].flags & (HA_NOSAME)) == HA_NOSAME)

5844

{

5845

if (const_ref == eq_part)

5846

{ // Found everything for ref.

5847

int tmp;

5848

ref_changed = 1;

5849

s->type= AM_CONST;

5850

join->const_table_map|= table->map;

5851

set_position(join, const_count++, s, start_keyuse);

5852

if (create_ref_for_key(join, s, start_keyuse, found_const_table_map))

5853

return 1;

5854

partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);

5855

if ((tmp=s->joinReadConstTable(partial_pos)))

5856

{

5857

if (tmp > 0)

5858

return 1; // Fatal error

5859

}

5860

else

5861

found_const_table_map|= table->map;

5862

break;

5863

}

5864

else

5865

found_ref|= refs; // Table is const if all refs are const

5866

}

5867

else if (const_ref == eq_part)

5868

s->const_keys.set(key);

5869

}

5870

}

5871

}

5872

}

5873

} while (join->const_table_map & found_ref && ref_changed);

5874

5875

5876

Update info on indexes that can be used for search lookups as

5877

reading const tables may has added new sargable predicates.

5878

5879

if (const_count && ! sargables.empty())

5880

{

5881

BOOST_FOREACH(vector<optimizer::SargableParam>::reference iter, sargables)

5882

{

5883

Field& field= *iter.getField();

5884

JoinTable *join_tab= field.getTable()->reginfo.join_tab;

5885

key_map possible_keys= field.key_start & field.getTable()->keys_in_use_for_query;

5886

bool is_const= true;

5887

for (uint32_t j= 0; j < iter.getNumValues(); j++)

5888

is_const&= iter.isConstItem(j);

5889

if (is_const)

5890

join_tab[0].const_keys|= possible_keys;

5891

}

5892

}

5893

5894

/* Calc how many (possible) matched records in each table */

5895

5896

for (s=stat ; s < stat_end ; s++)

5897

{

5898

if (s->type == AM_SYSTEM || s->type == AM_CONST)

5899

{

5900

/* Only one matching row */

5901

s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;

5902

continue;

5903

}

5904

/* Approximate found rows and time to read them */

5905

s->found_records=s->records=s->table->cursor->stats.records;

5906

s->read_time=(ha_rows) s->table->cursor->scan_time();

5907

5908

5909

Set a max range of how many seeks we can expect when using keys

5910

This is can't be to high as otherwise we are likely to use

5911

table scan.

5912

5913

s->worst_seeks= min((double) s->found_records / 10,

5914

(double) s->read_time*3);

5915

if (s->worst_seeks < 2.0) // Fix for small tables

5916

s->worst_seeks=2.0;

5917

5918

5919

Add to stat->const_keys those indexes for which all group fields or

5920

all select distinct fields participate in one index.

5921

5922

add_group_and_distinct_keys(join, s);

5923

5924

if (s->const_keys.any() &&

5925

!s->table->pos_in_table_list->getEmbedding())

5926

{

5927

ha_rows records;

5928

optimizer::SqlSelect *select= NULL;

5929

select= optimizer::make_select(s->table, found_const_table_map, found_const_table_map, *s->on_expr_ref ? *s->on_expr_ref : conds, 1, &error);

5930

if (! select)

5931

return 1;

5932

records= get_quick_record_count(join->session, select, s->table, &s->const_keys, join->row_limit);

5933

s->quick=select->quick;

5934

s->needed_reg=select->needed_reg;

5935

select->quick=0;

5936

5937

if (records == 0 && s->table->reginfo.impossible_range)

5938

{

5939

5940

Impossible WHERE or ON expression

5941

In case of ON, we mark that the we match one empty NULL row.

5942

In case of WHERE, don't set found_const_table_map to get the

5943

caller to abort with a zero row result.

5944

5945

join->const_table_map|= s->table->map;

5946

set_position(join, const_count++, s, NULL);

5947

s->type= AM_CONST;

5948

if (*s->on_expr_ref)

5949

{

5950

/* Generate empty row */

5951

s->info= "Impossible ON condition";

5952

found_const_table_map|= s->table->map;

5953

s->type= AM_CONST;

5954

s->table->mark_as_null_row(); // All fields are NULL

5955

}

5956

}

5957

if (records != HA_POS_ERROR)

5958

{

5959

s->found_records=records;

5960

s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);

5961

}

5962

delete select;

5963

}

5964

}

5965

5966

join->join_tab=stat;

5967

join->map2table=stat_ref;

5968

join->table= join->all_tables=table_vector;

5969

join->const_tables=const_count;

5970

join->found_const_table_map=found_const_table_map;

5971

5972

/* Find an optimal join order of the non-constant tables. */

5973

if (join->const_tables != join->tables)

5974

{

5975

optimize_keyuse(join, keyuse_array);

5976

// @note c_str() is not likely to be valid here if dtrace expects it to

5977

// exist for any period of time.

5978

DRIZZLE_QUERY_OPT_CHOOSE_PLAN_START(join->session->getQueryString()->c_str(), join->session->thread_id);

5979

bool res= choose_plan(join, all_table_map & ~join->const_table_map);

5980

DRIZZLE_QUERY_OPT_CHOOSE_PLAN_DONE(res ? 1 : 0);

5981

if (res)

5982

return true;

5983

}

5984

else

5985

{

5986

join->copyPartialPlanIntoOptimalPlan(join->const_tables);

5987

join->best_read= 1.0;

5988

}

5989

/* Generate an execution plan from the found optimal join order. */

5990

return join->session->getKilled() || get_best_combination(join);

5991

}

5992

5993

/**

5994

Assign each nested join structure a bit in the nested join bitset.

5995

5996

Assign each nested join structure (except "confluent" ones - those that

5997

embed only one element) a bit in the nested join bitset.

5998

5999

@param join Join being processed

6000

@param join_list List of tables

6001

@param first_unused Number of first unused bit in the nest joing bitset before the

6002

call

6003

6004

@note

6005

This function is called after simplify_joins(), when there are no

6006

redundant nested joins, #non_confluent_nested_joins <= #tables_in_join so

6007

we will not run out of bits in the nested join bitset.

6008

6009

@return

6010

First unused bit in the nest join bitset after the call.

6011

6012

static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused)

6013

{

6014

List<TableList>::iterator li(join_list->begin());

6015

while (TableList* table= li++)

6016

{

6017

if (NestedJoin* nested_join= table->getNestedJoin())

6018

{

6019

6020

It is guaranteed by simplify_joins() function that a nested join

6021

that has only one child is either

6022

- a single-table view (the child is the underlying table), or

6023

- a single-table semi-join nest

6024

6025

We don't assign bits to such sj-nests because

6026

1. it is redundant (a "sequence" of one table cannot be interleaved

6027

with anything)

6028

2. we could run out of bits in the nested join bitset otherwise.

6029

6030

if (nested_join->join_list.size() != 1)

6031

{

6032

/* Don't assign bits to sj-nests */

6033

if (table->on_expr)

6034

nested_join->nj_map.set(first_unused++);

6035

first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,

6036

first_unused);

6037

}

6038

}

6039

}

6040

return(first_unused);

6041

}

6042

6043

6044

/**

6045

Return table number if there is only one table in sort order

6046

and group and order is compatible, else return 0.

6047

6048

static Table *get_sort_by_table(Order *a, Order *b,TableList *tables)

6049

{

6050

table_map map= 0;

6051

6052

if (!a)

6053

a= b; // Only one need to be given

6054

else if (!b)

6055

b= a;

6056

6057

for (; a && b; a=a->next,b=b->next)

6058

{

6059

if (!(*a->item)->eq(*b->item,1))

6060

return NULL;

6061

map|= a->item[0]->used_tables();

6062

}

6063

if (!map || (map & (RAND_TABLE_BIT | OUTER_REF_TABLE_BIT)))

6064

return NULL;

6065

6066

for (; !(map & tables->table->map); tables= tables->next_leaf) {};

6067

if (map != tables->table->map)

6068

return NULL; // More than one table

6069

return tables->table;

6070

}

6071

6072

/**

6073

Set NestedJoin::counter=0 in all nested joins in passed list.

6074

6075

Recursively set NestedJoin::counter=0 for all nested joins contained in

6076

the passed join_list.

6077

6078

@param join_list List of nested joins to process. It may also contain base

6079

tables which will be ignored.

6080

6081

static void reset_nj_counters(List<TableList> *join_list)

6082

{

6083

List<TableList>::iterator li(join_list->begin());

6084

while (TableList* table= li++)

6085

{

6086

NestedJoin *nested_join;

6087

if ((nested_join= table->getNestedJoin()))

6088

{

6089

nested_join->counter_= 0;

6090

reset_nj_counters(&nested_join->join_list);

6091

}

6092

}

6093

}

6094

6095

/**

6096

Return 1 if second is a subpart of first argument.

6097

6098

If first parts has different direction, change it to second part

6099

(group is sorted like order)

6100

6101

static bool test_if_subpart(Order *a, Order *b)

6102

{

6103

for (; a && b; a=a->next,b=b->next)

6104

{

6105

if ((*a->item)->eq(*b->item,1))

6106

a->asc=b->asc;

6107

else

6108

return 0;

6109

}

6110

return test(!b);

6111

}

6112

6113

/**

6114

Nested joins perspective: Remove the last table from the join order.

6115

6116

The algorithm is the reciprocal of check_interleaving_with_nj(), hence

6117

parent join nest nodes are updated only when the last table in its child

6118

node is removed. The ASCII graphic below will clarify.

6119

6120

%A table nesting such as <tt> t1 x [ ( t2 x t3 ) x ( t4 x t5 ) ] </tt>is

6121

represented by the below join nest tree.

6122

6123

@verbatim

6124

NJ1

6125

_/ / \

6126

_/ / NJ2

6127

_/ / / \

6128

/ / / \

6129

t1 x [ (t2 x t3) x (t4 x t5) ]

6130

@endverbatim

6131

6132

At the point in time when check_interleaving_with_nj() adds the table t5 to

6133

the query execution plan, QEP, it also directs the node named NJ2 to mark

6134

the table as covered. NJ2 does so by incrementing its @c counter

6135

member. Since all of NJ2's tables are now covered by the QEP, the algorithm

6136

proceeds up the tree to NJ1, incrementing its counter as well. All join

6137

nests are now completely covered by the QEP.

6138

6139

restore_prev_nj_state() does the above in reverse. As seen above, the node

6140

NJ1 contains the nodes t2, t3, and NJ2. Its counter being equal to 3 means

6141

that the plan covers t2, t3, and NJ2, @e and that the sub-plan (t4 x t5)

6142

completely covers NJ2. The removal of t5 from the partial plan will first

6143

decrement NJ2's counter to 1. It will then detect that NJ2 went from being

6144

completely to partially covered, and hence the algorithm must continue

6145

upwards to NJ1 and decrement its counter to 2. %A subsequent removal of t4

6146

will however not influence NJ1 since it did not un-cover the last table in

6147

NJ2.

6148

6149

SYNOPSIS

6150

restore_prev_nj_state()

6151

last join table to remove, it is assumed to be the last in current

6152

partial join order.

6153

6154

DESCRIPTION

6155

6156

Remove the last table from the partial join order and update the nested

6157

joins counters and join->cur_embedding_map. It is ok to call this

6158

function for the first table in join order (for which

6159

check_interleaving_with_nj has not been called)

6160

6161

@param last join table to remove, it is assumed to be the last in current

6162

partial join order.

6163

6164

6165

static void restore_prev_nj_state(JoinTable *last)

6166

{

6167

TableList *last_emb= last->table->pos_in_table_list->getEmbedding();

6168

Join *join= last->join;

6169

for (;last_emb != NULL; last_emb= last_emb->getEmbedding())

6170

{

6171

NestedJoin *nest= last_emb->getNestedJoin();

6172

6173

bool was_fully_covered= nest->is_fully_covered();

6174

6175

if (--nest->counter_ == 0)

6176

join->cur_embedding_map&= ~nest->nj_map;

6177

6178

if (!was_fully_covered)

6179

break;

6180

6181

join->cur_embedding_map|= nest->nj_map;

6182

}

6183

}

6184

6185

/**

6186

Create a condition for a const reference and add this to the

6187

currenct select for the table.

6188

6189

static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab)

6190

{

6191

if (!join_tab->ref.key_parts)

6192

return false;

6193

6194

Item_cond_and *cond=new Item_cond_and();

6195

Table *table=join_tab->table;

6196

6197

for (uint32_t i=0 ; i < join_tab->ref.key_parts ; i++)

6198

{

6199

Field *field=table->getField(table->key_info[join_tab->ref.key].key_part[i].fieldnr - 1);

6200

Item *value=join_tab->ref.items[i];

6201

cond->add(new Item_func_equal(new Item_field(field), value));

6202

}

6203

if (session->is_fatal_error)

6204

return true;

6205

6206

if (!cond->fixed)

6207

cond->fix_fields(session, (Item**)&cond);

6208

int error = 0;

6209

if (join_tab->select)

6210

{

6211

cond->add(join_tab->select->cond);

6212

join_tab->select_cond=join_tab->select->cond=cond;

6213

}

6214

else if ((join_tab->select= optimizer::make_select(join_tab->table, 0, 0, cond, 0, &error)))

6215

join_tab->select_cond=cond;

6216

6217

return error;

6218

}

6219

6220

static void free_blobs(Field **ptr)

6221

{

6222

for (; *ptr ; ptr++)

6223

{

6224

if ((*ptr)->flags & BLOB_FLAG)

6225

((Field_blob *) (*ptr))->free();

6226

}

6227

}

6228

6229

/**

6230

@} (end of group Query_Optimizer)

6231

6232

6233

} /* namespace drizzled */

Older »