~drizzle-trunk/drizzle/development : revision 1091

28

*/

29

30

#include "drizzled/server_includes.h"

31

#include "drizzled/sj_tmp_table.h"

31

#include "drizzled/semi_join_table.h"

32

#include "drizzled/table_map_iterator.h"

33

#include "drizzled/item/cache.h"

34

#include "drizzled/item/cmpfunc.h"

61

static uint32_t cache_record_length(JOIN *join, uint32_t index);

62

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

63

static bool get_best_combination(JOIN *join);

64

static void set_position(JOIN *join,uint32_t index,JOIN_TAB *table,KEYUSE *key);

64

static void set_position(JOIN *join,uint32_t index,JoinTable *table,KeyUse *key);

65

static bool choose_plan(JOIN *join,table_map join_tables);

66

static void best_access_path(JOIN *join, JOIN_TAB *s,

66

static void best_access_path(JOIN *join, JoinTable *s,

67

Session *session,

68

table_map remaining_tables,

69

uint32_t idx,

111

static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables);

112

static void reset_nj_counters(List<TableList> *join_list);

113

static bool test_if_subpart(order_st *a,order_st *b);

114

static void restore_prev_nj_state(JOIN_TAB *last);

114

static void restore_prev_nj_state(JoinTable *last);

115

static uint32_t make_join_orderinfo(JOIN *join);

116

static int setup_semijoin_dups_elimination(JOIN *join, uint64_t options, uint32_t no_jbuf_after);

117

static void cleanup_sj_tmp_tables(JOIN *join);

118

static bool add_ref_to_table_cond(Session *session, JOIN_TAB *join_tab);

118

static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab);

119

static bool replace_where_subcondition(JOIN *join, Item *old_cond, Item *new_cond, bool fix_fields);

120

static int pull_out_semijoin_tables(JOIN *join);

121

static int do_sj_dups_weedout(Session *session, SJ_TMP_TABLE *sjtbl);

121

static int do_sj_dups_weedout(Session *session, SemiJoinTable *sjtbl);

122

static void free_blobs(Field **ptr); /* Rename this method...conflicts with another in global namespace... */

123

static bool bitmap_covers(const table_map x, const table_map y);

124

static bool sj_table_is_included(JOIN *join, JOIN_TAB *join_tab);

124

static bool sj_table_is_included(JOIN *join, JoinTable *join_tab);

125

126

/**

127

Prepare of whole select (including sub queries in future).

660

Permorm the the optimization on fields evaluation mentioned above

661

for all on expressions.

662

*/

663

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

663

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

664

{

665

if (*tab->on_expr_ref)

666

{

780

because in this case we can just create a temporary table that

781

holds LIMIT rows and stop when this table is full.

782

*/

783

JOIN_TAB *tab= &join_tab[const_tables];

783

JoinTable *tab= &join_tab[const_tables];

784

bool all_order_fields_used;

785

if (order)

786

skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,

1120

if (exec_tmp_table1->distinct)

1121

{

1122

table_map used_tables= session->used_tables;

1123

JOIN_TAB *last_join_tab= join_tab+tables-1;

1123

JoinTable *last_join_tab= join_tab+tables-1;

1124

do

1125

{

1126

if (used_tables & last_join_tab->table->map)

1186

set_items_ref_array(items0);

1187

1188

if (join_tab_save)

1189

memcpy(join_tab, join_tab_save, sizeof(JOIN_TAB) * tables);

1189

memcpy(join_tab, join_tab_save, sizeof(JoinTable) * tables);

1190

1191

if (tmp_join)

1192

restore_tmp();

1225

{

1226

if (!join_tab_save && select_lex->master_unit()->uncacheable)

1227

{

1228

if (!(join_tab_save= (JOIN_TAB*)session->memdup((unsigned char*) join_tab,

1229

sizeof(JOIN_TAB) * tables)))

1228

if (!(join_tab_save= (JoinTable*)session->memdup((unsigned char*) join_tab,

1229

sizeof(JoinTable) * tables)))

1230

return 1;

1231

}

1232

return 0;

1605

{

1606

// Some tables may have been const

1607

curr_join->tmp_having->update_used_tables();

1608

JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables];

1608

JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables];

1609

table_map used_tables= (curr_join->const_table_map |

1610

curr_table->table->map);

1611

1645

We can abort sorting after session->select_limit rows if we there is no

1646

WHERE clause for any tables after the sorted one.

1647

*/

1648

JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables+1];

1649

JOIN_TAB *end_table= &curr_join->join_tab[curr_join->tables];

1648

JoinTable *curr_table= &curr_join->join_tab[curr_join->const_tables+1];

1649

JoinTable *end_table= &curr_join->join_tab[curr_join->tables];

1650

for (; curr_table < end_table ; curr_table++)

1651

{

1652

/*

1738

{

1739

if (join_tab != tmp_join->join_tab)

1740

{

1741

JOIN_TAB *tab, *end;

1741

JoinTable *tab, *end;

1742

for (tab= join_tab, end= tab+tables ; tab != end ; tab++)

1743

tab->cleanup();

1744

}

2021

{

2022

if (table)

2023

{

2024

JOIN_TAB *tab,*end;

2024

JoinTable *tab,*end;

2025

/*

2026

Only a sorted table may be cached. This sorted table is always the

2027

first non const table in join->table

2564

*/

2565

bool error_if_full_join(JOIN *join)

2566

{

2567

for (JOIN_TAB *tab= join->join_tab, *end= join->join_tab+join->tables; tab < end; tab++)

2567

for (JoinTable *tab= join->join_tab, *end= join->join_tab+join->tables; tab < end; tab++)

2568

{

2569

if (tab->type == JT_ALL && (!tab->select || !tab->select->quick))

2570

{

2587

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

2588

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

2589

*/

2590

enum_nested_loop_state evaluate_join_record(JOIN *join, JOIN_TAB *join_tab, int error)

2590

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

2591

{

2592

bool not_used_in_distinct= join_tab->not_used_in_distinct;

2593

ha_rows found_records= join->found_records;

2615

The while condition is always false if join_tab is not

2616

the last inner join table of an outer join operation.

2617

*/

2618

JOIN_TAB *first_unmatched= join_tab->first_unmatched;

2618

JoinTable *first_unmatched= join_tab->first_unmatched;

2619

/*

2620

Mark that a match for current outer table is found.

2621

This activates push down conditional predicates attached

2622

to the all inner tables of the outer join.

2623

*/

2624

first_unmatched->found= 1;

2625

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

2625

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

2626

{

2627

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

2628

return NESTED_LOOP_NO_MORE_ROWS;

2658

join_tab->first_unmatched= first_unmatched;

2659

}

2660

2661

JOIN_TAB *return_tab= join->return_tab;

2661

JoinTable *return_tab= join->return_tab;

2662

join_tab->found_match= true;

2663

if (join_tab->check_weed_out_table)

2664

{

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, JOIN_TAB *join_tab)

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

JOIN_TAB *last_inner_tab= join_tab->last_inner;

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

2758

*/

2759

for ( ; ; )

2760

{

2761

JOIN_TAB *first_unmatched= join_tab->first_unmatched;

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 (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)

2768

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

2769

{

2770

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

2771

{

2783

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

2784

}

2785

2786

enum_nested_loop_state flush_cached_records(JOIN *join, JOIN_TAB *join_tab, bool skip_last)

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;

2809

return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;

2810

}

2811

2812

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

2812

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

2813

{

2814

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

2815

tmp->table->status=0;

2857

reset_cache_write(&join_tab->cache);

2858

if (error > 0) // Fatal error

2859

return NESTED_LOOP_ERROR; /* purecov: inspected */

2860

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

2860

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

2861

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

2862

return NESTED_LOOP_OK;

2863

}

2886

operation.

2887

All return values except NESTED_LOOP_OK abort the nested loop.

2888

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

2889

enum_nested_loop_state end_send(JOIN *join, JOIN_TAB *, bool end_of_records)

2889

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

2890

{

2891

if (! end_of_records)

2892

{

2902

{

2903

if (join->select_options & OPTION_FOUND_ROWS)

2904

{

2905

JOIN_TAB *jt=join->join_tab;

2905

JoinTable *jt=join->join_tab;

2906

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

2907

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

2908

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

2948

return NESTED_LOOP_OK;

2949

}

2950

2951

enum_nested_loop_state end_write(JOIN *join, JOIN_TAB *, bool end_of_records)

2951

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

2952

{

2953

Table *table= join->tmp_table;

2954

2991

}

2992

2993

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

2994

enum_nested_loop_state end_update(JOIN *join, JOIN_TAB *, bool end_of_records)

2994

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

2995

{

2996

Table *table= join->tmp_table;

2997

order_st *group;

3063

}

3064

3065

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

3066

enum_nested_loop_state end_unique_update(JOIN *join, JOIN_TAB *, bool end_of_records)

3066

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

3067

{

3068

Table *table= join->tmp_table;

3069

int error;

3262

if (read_time+record_count/(double) TIME_FOR_COMPARE >= join->best_read)

3263

return(false); /* Found better before */

3264

3265

JOIN_TAB *s;

3265

JoinTable *s;

3266

double best_record_count=DBL_MAX,best_read_time=DBL_MAX;

3267

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

3267

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

3268

{

3269

table_map real_table_bit=s->table->map;

3270

if ((rest_tables & real_table_bit) && !(rest_tables & s->dependent) &&

3311

static uint32_t cache_record_length(JOIN *join,uint32_t idx)

3312

{

3313

uint32_t length=0;

3314

JOIN_TAB **pos,**end;

3314

JoinTable **pos,**end;

3315

Session *session=join->session;

3316

3317

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

3318

pos != end ;

3319

pos++)

3320

{

3321

JOIN_TAB *join_tab= *pos;

3321

JoinTable *join_tab= *pos;

3322

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

3323

calc_used_field_length(session, join_tab);

3324

length+=join_tab->used_fieldlength;

3415

{

3416

uint32_t i,tablenr;

3417

table_map used_tables;

3418

JOIN_TAB *join_tab,*j;

3419

KEYUSE *keyuse;

3418

JoinTable *join_tab,*j;

3419

KeyUse *keyuse;

3420

uint32_t table_count;

3421

Session *session=join->session;

3422

3423

table_count=join->tables;

3424

if (!(join->join_tab=join_tab=

3425

(JOIN_TAB*) session->alloc(sizeof(JOIN_TAB)*table_count)))

3425

(JoinTable*) session->alloc(sizeof(JoinTable)*table_count)))

3426

return(true);

3427

3428

join->full_join=0;

3462

}

3463

3464

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

3465

static void set_position(JOIN *join,uint32_t idx,JOIN_TAB *table,KEYUSE *key)

3465

static void set_position(JOIN *join,uint32_t idx,JoinTable *table,KeyUse *key)

3466

{

3467

join->positions[idx].table= table;

3468

join->positions[idx].key=key;

3470

join->positions[idx].ref_depend_map= 0;

3471

3472

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

3473

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

3474

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

3473

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

3474

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

3475

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

3476

{

3477

JOIN_TAB *tmp=pos[0];

3477

JoinTable *tmp=pos[0];

3478

pos[0]=next;

3479

next=tmp;

3480

}

3520

records accessed.

3521

*/

3522

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

3523

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

3523

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

3524

straight_join ? join_tab_cmp_straight : join_tab_cmp);

3525

join->cur_emb_sj_nests= 0;

3526

if (straight_join)

3584

None

3585

*/

3586

static void best_access_path(JOIN *join,

3587

JOIN_TAB *s,

3587

JoinTable *s,

3588

Session *session,

3589

table_map remaining_tables,

3590

uint32_t idx,

3591

double record_count,

3592

double)

3593

{

3594

KEYUSE *best_key= 0;

3594

KeyUse *best_key= 0;

3595

uint32_t best_max_key_part= 0;

3596

bool found_constraint= 0;

3597

double best= DBL_MAX;

3605

if (s->keyuse)

3606

{ /* Use key if possible */

3607

Table *table= s->table;

3608

KEYUSE *keyuse,*start_key=0;

3608

KeyUse *keyuse,*start_key=0;

3609

double best_records= DBL_MAX;

3610

uint32_t max_key_part=0;

3611

uint64_t bound_sj_equalities= 0;

3743

/*

3744

It's a confluent ref scan.

3745

3746

That is, all found KEYUSE elements refer to IN-equalities,

3746

That is, all found KeyUse elements refer to IN-equalities,

3747

and there is really no ref access because there is no

3748

t.keypart0 = {bound expression}

3749

4206

*/

4207

static void optimize_straight_join(JOIN *join, table_map join_tables)

4208

{

4209

JOIN_TAB *s;

4209

JoinTable *s;

4210

uint32_t idx= join->const_tables;

4211

double record_count= 1.0;

4212

double read_time= 0.0;

4213

4214

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

4214

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

4215

{

4216

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

4217

advance_sj_state(join_tables, s);

4323

uint32_t best_idx;

4324

uint32_t size_remain; // cardinality of remaining_tables

4325

POSITION best_pos;

4326

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

4326

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

4327

4328

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

4329

size_remain= my_count_bits(remaining_tables);

4356

4357

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

4358

best_idx= idx;

4359

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

4359

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

4360

while (pos && best_table != pos)

4361

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

4362

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

4506

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

4507

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

4508

*/

4509

JOIN_TAB *s;

4509

JoinTable *s;

4510

double best_record_count= DBL_MAX;

4511

double best_read_time= DBL_MAX;

4512

4513

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

4513

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

4514

{

4515

table_map real_table_bit= s->table->map;

4516

if ((remaining_tables & real_table_bit) &&

4662

static bool make_simple_join(JOIN *join,Table *tmp_table)

4663

{

4664

Table **tableptr;

4665

JOIN_TAB *join_tab;

4665

JoinTable *join_tab;

4666

4667

/*

4668

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

4668

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

4669

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

4670

*/

4671

if (!join->table_reexec)

4678

if (!join->join_tab_reexec)

4679

{

4680

if (!(join->join_tab_reexec=

4681

(JOIN_TAB*) join->session->alloc(sizeof(JOIN_TAB))))

4681

(JoinTable*) join->session->alloc(sizeof(JoinTable))))

4682

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

4683

if (join->tmp_join)

4684

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

4739

through the field t0->first_upper.

4740

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

4741

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

4742

Here ti are structures of the JOIN_TAB type.

4742

Here ti are structures of the JoinTable type.

4743

4744

EXAMPLE. For the query:

4745

@code

4769

{

4770

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

4771

{

4772

JOIN_TAB *tab=join->join_tab+i;

4772

JoinTable *tab=join->join_tab+i;

4773

Table *table=tab->table;

4774

TableList *tbl= table->pos_in_table_list;

4775

TableList *embedding= tbl->embedding;

4836

make_cond_for_table(cond,

4837

join->const_table_map,

4838

(table_map) 0, 1);

4839

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

4839

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

4840

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

4841

{

4842

if (*tab->on_expr_ref)

4843

{

4844

JOIN_TAB *cond_tab= tab->first_inner;

4844

JoinTable *cond_tab= tab->first_inner;

4845

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

4846

join->const_table_map,

4847

( table_map) 0, 0);

4869

OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);

4870

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

4871

{

4872

JOIN_TAB *tab=join->join_tab+i;

4872

JoinTable *tab=join->join_tab+i;

4873

/*

4874

first_inner is the X in queries like:

4875

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

4876

*/

4877

JOIN_TAB *first_inner_tab= tab->first_inner;

4877

JoinTable *first_inner_tab= tab->first_inner;

4878

table_map current_map= tab->table->map;

4879

bool use_quick_range=0;

4880

COND *tmp;

5101

*/

5102

5103

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

5104

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

5104

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

5105

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

5106

{

5107

if (*join_tab->on_expr_ref)

5108

{

5109

JOIN_TAB *cond_tab= join_tab->first_inner;

5109

JoinTable *cond_tab= join_tab->first_inner;

5110

tmp= make_cond_for_table(*join_tab->on_expr_ref,

5111

join->const_table_map,

5112

(table_map) 0, 0);

5125

}

5126

5127

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

5128

JOIN_TAB *last_tab= tab;

5128

JoinTable *last_tab= tab;

5129

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

5130

{

5131

/*

5144

current_map, 0);

5145

if (tmp_cond)

5146

{

5147

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

5147

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

5148

/*

5149

First add the guards for match variables of

5150

all embedding outer join operations.

5207

5208

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

5209

{

5210

JOIN_TAB *tab=join->join_tab+i;

5210

JoinTable *tab=join->join_tab+i;

5211

Table *table=tab->table;

5212

bool using_join_cache;

5213

tab->read_record.table= table;

5396

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

5397

static void update_depend_map(JOIN *join)

5398

{

5399

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

5399

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

5400

5401

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

5402

{

5408

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

5409

ref->depend_map=depend_map & ~OUTER_REF_TABLE_BIT;

5410

depend_map&= ~OUTER_REF_TABLE_BIT;

5411

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

5411

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

5412

{

5413

if (depend_map & 1)

5414

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

5428

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

5429

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

5430

{

5431

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

5431

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

5432

{

5433

if (depend_map & 1)

5434

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

5936

table_map found_const_table_map, all_table_map, found_ref, refs;

5937

key_map const_ref, eq_part;

5938

Table **table_vector;

5939

JOIN_TAB *stat,*stat_end,*s,**stat_ref;

5940

KEYUSE *keyuse,*start_keyuse;

5939

JoinTable *stat,*stat_end,*s,**stat_ref;

5940

KeyUse *keyuse,*start_keyuse;

5941

table_map outer_join=0;

5942

SARGABLE_PARAM *sargables= 0;

5943

JOIN_TAB *stat_vector[MAX_TABLES+1];

5943

JoinTable *stat_vector[MAX_TABLES+1];

5944

5945

table_count=join->tables;

5946

stat=(JOIN_TAB*) join->session->calloc(sizeof(JOIN_TAB)*table_count);

5947

stat_ref=(JOIN_TAB**) join->session->alloc(sizeof(JOIN_TAB*)*MAX_TABLES);

5946

stat=(JoinTable*) join->session->calloc(sizeof(JoinTable)*table_count);

5947

stat_ref=(JoinTable**) join->session->alloc(sizeof(JoinTable*)*MAX_TABLES);

5948

table_vector=(Table**) join->session->alloc(sizeof(Table*)*(table_count*2));

5949

if (!stat || !stat_ref || !table_vector)

5950

return(1); // Eom /* purecov: inspected */

5995

if (!table->file->stats.records && !embedding)

5996

{ // Empty table

5997

s->dependent= 0; // Ignore LEFT JOIN depend.

5998

set_position(join,const_count++,s,(KEYUSE*) 0);

5998

set_position(join,const_count++,s,(KeyUse*) 0);

5999

continue;

6000

}

6001

outer_join|= table->map;

6023

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

6024

!join->no_const_tables)

6025

{

6026

set_position(join,const_count++,s,(KEYUSE*) 0);

6026

set_position(join,const_count++,s,(KeyUse*) 0);

6027

}

6028

}

6029

stat_vector[i]=0;

6102

set_position() will move all const_tables first in stat_vector

6103

*/

6104

6105

for (JOIN_TAB **pos=stat_vector+const_count ; (s= *pos) ; pos++)

6105

for (JoinTable **pos=stat_vector+const_count ; (s= *pos) ; pos++)

6106

{

6107

table=s->table;

6108

6132

table->mark_as_null_row();

6133

found_const_table_map|= table->map;

6134

join->const_table_map|= table->map;

6135

set_position(join,const_count++,s,(KEYUSE*) 0);

6135

set_position(join,const_count++,s,(KeyUse*) 0);

6136

goto more_const_tables_found;

6137

}

6138

keyuse++;

6151

int tmp= 0;

6152

s->type=JT_SYSTEM;

6153

join->const_table_map|=table->map;

6154

set_position(join,const_count++,s,(KEYUSE*) 0);

6154

set_position(join,const_count++,s,(KeyUse*) 0);

6155

if ((tmp= join_read_const_table(s, join->positions+const_count-1)))

6156

{

6157

if (tmp > 0)

6231

for( ; sargables->field ; sargables++)

6232

{

6233

Field *field= sargables->field;

6234

JOIN_TAB *join_tab= field->table->reginfo.join_tab;

6234

JoinTable *join_tab= field->table->reginfo.join_tab;

6235

key_map possible_keys= field->key_start;

6236

possible_keys&= field->table->keys_in_use_for_query;

6237

bool is_const= 1;

6296

caller to abort with a zero row result.

6297

*/

6298

join->const_table_map|= s->table->map;

6299

set_position(join,const_count++,s,(KEYUSE*) 0);

6299

set_position(join,const_count++,s,(KeyUse*) 0);

6300

s->type= JT_CONST;

6301

if (*s->on_expr_ref)

6302

{

6473

@param last join table to remove, it is assumed to be the last in current

6474

partial join order.

6475

*/

6476

static void restore_prev_nj_state(JOIN_TAB *last)

6476

static void restore_prev_nj_state(JoinTable *last)

6477

{

6478

TableList *last_emb= last->table->pos_in_table_list->embedding;

6479

JOIN *join= last->join;

6510

6511

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

6512

{

6513

JOIN_TAB *tab= join->join_tab+i;

6513

JoinTable *tab= join->join_tab+i;

6514

Table *table= tab->table;

6515

if ((table == join->sort_by_table &&

6516

(!join->order || join->skip_sort_order)) ||

6651

*/

6652

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

6653

{

6654

JOIN_TAB *tab=join->join_tab+i;

6654

JoinTable *tab=join->join_tab+i;

6655

Table *table=tab->table;

6656

cur_map |= table->map;

6657

6768

}

6769

6770

Session *session= join->session;

6771

SJ_TMP_TABLE **next_sjtbl_ptr= &join->sj_tmp_tables;

6771

SemiJoinTable **next_sjtbl_ptr= &join->sj_tmp_tables;

6772

/*

6773

Second pass: setup the chosen strategies

6774

*/

6775

for (int j= 0; j < cur_range; j++)

6776

{

6777

JOIN_TAB *tab=join->join_tab + dups_ranges[j].start_idx;

6778

JOIN_TAB *jump_to;

6777

JoinTable *tab=join->join_tab + dups_ranges[j].start_idx;

6778

JoinTable *jump_to;

6779

if (dups_ranges[j].strategy == 1) // InsideOut strategy

6780

{

6781

tab->insideout_match_tab= join->join_tab + dups_ranges[j].end_idx - 1;

6783

}

6784

else // DuplicateWeedout strategy

6785

{

6786

SJ_TMP_TABLE::TAB sjtabs[MAX_TABLES];

6786

SemiJoinTable::TAB sjtabs[MAX_TABLES];

6787

table_map weed_cur_map= join->const_table_map | PSEUDO_TABLE_BITS;

6788

uint32_t jt_rowid_offset= 0; // # tuple bytes are already occupied (w/o NULL bytes)

6789

uint32_t jt_null_bits= 0; // # null bits in tuple bytes

6790

SJ_TMP_TABLE::TAB *last_tab= sjtabs;

6791

uint32_t rowid_keep_flags= JOIN_TAB::CALL_POSITION | JOIN_TAB::KEEP_ROWID;

6792

JOIN_TAB *last_outer_tab= tab - 1;

6790

SemiJoinTable::TAB *last_tab= sjtabs;

6791

uint32_t rowid_keep_flags= JoinTable::CALL_POSITION | JoinTable::KEEP_ROWID;

6792

JoinTable *last_outer_tab= tab - 1;

6793

/*

6794

Walk through the range and remember

6795

- tables that need their rowids to be put into temptable

6819

6820

if (jt_rowid_offset) /* Temptable has at least one rowid */

6821

{

6822

SJ_TMP_TABLE *sjtbl;

6823

uint32_t tabs_size= (last_tab - sjtabs) * sizeof(SJ_TMP_TABLE::TAB);

6824

if (!(sjtbl= (SJ_TMP_TABLE*)session->alloc(sizeof(SJ_TMP_TABLE))) ||

6825

!(sjtbl->tabs= (SJ_TMP_TABLE::TAB*) session->alloc(tabs_size)))

6822

SemiJoinTable *sjtbl;

6823

uint32_t tabs_size= (last_tab - sjtabs) * sizeof(SemiJoinTable::TAB);

6824

if (!(sjtbl= (SemiJoinTable*)session->alloc(sizeof(SemiJoinTable))) ||

6825

!(sjtbl->tabs= (SemiJoinTable::TAB*) session->alloc(tabs_size)))

6826

return(true);

6827

memcpy(sjtbl->tabs, sjtabs, tabs_size);

6828

sjtbl->tabs_end= sjtbl->tabs + (last_tab - sjtabs);

6835

sjtbl->next= NULL;

6836

6837

sjtbl->tmp_table=

6838

create_duplicate_weedout_tmp_table(session,

6839

sjtbl->rowid_len +

6840

sjtbl->null_bytes,

6841

sjtbl);

6838

sjtbl->createTable(session,

6839

sjtbl->rowid_len +

6840

sjtbl->null_bytes);

6842

6841

6843

6842

join->join_tab[dups_ranges[j].start_idx].flush_weedout_table= sjtbl;

6844

6843

join->join_tab[dups_ranges[j].end_idx - 1].check_weed_out_table= sjtbl;

6861

6860

6862

6861

static void cleanup_sj_tmp_tables(JOIN *join)

6863

6862

{

6864

for (SJ_TMP_TABLE *sj_tbl= join->sj_tmp_tables; sj_tbl;

6863

for (SemiJoinTable *sj_tbl= join->sj_tmp_tables; sj_tbl;

6865

6864

sj_tbl= sj_tbl->next)

6866

6865

{

6867

6866

if (sj_tbl->tmp_table)

6876

6875

Create a condition for a const reference and add this to the

6877

6876

currenct select for the table.

6878

6877

*/

6879

static bool add_ref_to_table_cond(Session *session, JOIN_TAB *join_tab)

6878

static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab)

6880

6879

{

6881

6880

if (!join_tab->ref.key_parts)

6882

6881

return(false);

6975

6974

- It is accessed

6976

6975

6977

6976

POSTCONDITIONS

6978

* Pulled out tables have JOIN_TAB::emb_sj_nest == NULL (like the outer

6977

* Pulled out tables have JoinTable::emb_sj_nest == NULL (like the outer

6979

6978

tables)

6980

* Tables that were not pulled out have JOIN_TAB::emb_sj_nest.

6979

* Tables that were not pulled out have JoinTable::emb_sj_nest.

6981

6980

* Semi-join nests TableList::sj_inner_tables

6982

6981

6983

6982

This operation is (and should be) performed at each PS execution since

7079

7078

1 The row combination is a duplicate (discard it)

7080

7079

0 The row combination is not a duplicate (continue)

7081

7080

*/

7082

static int do_sj_dups_weedout(Session *session, SJ_TMP_TABLE *sjtbl)

7081

static int do_sj_dups_weedout(Session *session, SemiJoinTable *sjtbl)

7083

7082

{

7084

7083

int error;

7085

SJ_TMP_TABLE::TAB *tab= sjtbl->tabs;

7086

SJ_TMP_TABLE::TAB *tab_end= sjtbl->tabs_end;

7084

SemiJoinTable::TAB *tab= sjtbl->tabs;

7085

SemiJoinTable::TAB *tab_end= sjtbl->tabs_end;

7087

7086

unsigned char *ptr= sjtbl->tmp_table->record[0] + 1;

7088

7087

unsigned char *nulls_ptr= ptr;

7089

7088

7121

7120

else

7122

7121

{

7123

7122

/* Copy the rowid value */

7124

if (tab->join_tab->rowid_keep_flags & JOIN_TAB::CALL_POSITION)

7123

if (tab->join_tab->rowid_keep_flags & JoinTable::CALL_POSITION)

7125

7124

h->position(tab->join_tab->table->record[0]);

7126

7125

memcpy(ptr + tab->rowid_offset, h->ref, h->ref_length);

7127

7126

}

7179

7178

true - Include table's rowid

7180

7179

false - Don't

7181

7180

*/

7182

static bool sj_table_is_included(JOIN *join, JOIN_TAB *join_tab)

7181

static bool sj_table_is_included(JOIN *join, JoinTable *join_tab)

7183

7182

{

7184

7183

if (join_tab->emb_sj_nest)

7185

7184

return false;

7194

7193

uint32_t idx;

7195

7194

while ((idx= it.next_bit())!=Table_map_iterator::BITMAP_END)

7196

7195

{

7197

JOIN_TAB *ref_tab= join->join_tab + idx;

7196

JoinTable *ref_tab= join->join_tab + idx;

7198

7197

if (embedding == ref_tab->table->pos_in_table_list->embedding)

7199

7198

return true;

7200

7199

}