~drizzle-trunk/drizzle/development : revision 1139

44

#include "drizzled/field/blob.h"

45

#include "drizzled/optimizer/position.h"

46

#include "drizzled/optimizer/sargable_param.h"

47

#include "drizzled/optimizer/key_use.h"

47

48

#include "mysys/my_bit.h"

48

49

50

#include <algorithm>

58

59

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

59

60

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

60

61

static bool get_best_combination(JOIN *join);

61

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

62

static void set_position(JOIN *join,

63

uint32_t index,

64

JoinTable *table,

65

optimizer::KeyUse *key);

62

66

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

63

67

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

64

68

Session *session,

404

408

{

405

409

// to prevent double initialization on EXPLAIN

406

410

if (optimized)

407

return(0);

411

return 0;

408

412

optimized= 1;

409

413

410

414

session->set_proc_info("optimizing");

3122

3126

uint32_t i,tablenr;

3123

3127

table_map used_tables;

3124

3128

JoinTable *join_tab,*j;

3125

KeyUse *keyuse;

3129

optimizer::KeyUse *keyuse;

3126

3130

uint32_t table_count;

3127

3131

Session *session=join->session;

3128

3132

optimizer::Position cur_pos;

3170

3174

}

3171

3175

3172

3176

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

3173

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

3177

static void set_position(JOIN *join,

3178

uint32_t idx,

3179

JoinTable *table,

3180

optimizer::KeyUse *key)

3174

3181

{

3175

3182

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

3176

3183

0.0,

3284

3291

double record_count,

3285

3292

double)

3286

3293

{

3287

KeyUse *best_key= 0;

3288

uint32_t best_max_key_part= 0;

3294

optimizer::KeyUse *best_key= NULL;

3295

uint32_t best_max_key_part= NULL;

3289

3296

bool found_constraint= 0;

3290

double best= DBL_MAX;

3291

double best_time= DBL_MAX;

3292

double records= DBL_MAX;

3297

double best= DBL_MAX;

3298

double best_time= DBL_MAX;

3299

double records= DBL_MAX;

3293

3300

table_map best_ref_depends_map= 0;

3294

3301

double tmp;

3295

3302

ha_rows rec;

3297

3304

if (s->keyuse)

3298

3305

{ /* Use key if possible */

3299

3306

Table *table= s->table;

3300

KeyUse *keyuse,*start_key=0;

3307

optimizer::KeyUse *keyuse= NULL;

3308

optimizer::KeyUse *start_key= NULL;

3301

3309

double best_records= DBL_MAX;

3302

3310

uint32_t max_key_part=0;

3303

3311

3304

3312

/* Test how we can use keys */

3305

3313

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

3306

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

3314

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

3307

3315

{

3308

3316

key_part_map found_part= 0;

3309

3317

table_map found_ref= 0;

3310

uint32_t key= keyuse->key;

3311

KEY *keyinfo= table->key_info+key;

3318

uint32_t key= keyuse->getKey();

3319

KEY *keyinfo= table->key_info + key;

3312

3320

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

3313

3321

key_part_map const_part= 0;

3314

3322

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

3319

3327

3320

3328

do /* For each keypart */

3321

3329

{

3322

uint32_t keypart= keyuse->keypart;

3330

uint32_t keypart= keyuse->getKeypart();

3323

3331

table_map best_part_found_ref= 0;

3324

3332

double best_prev_record_reads= DBL_MAX;

3325

3333

3330

3338

if 1. expression doesn't refer to forward tables

3331

3339

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

3332

3340

*/

3333

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

3334

!(ref_or_null_part && (keyuse->optimize &

3335

KEY_OPTIMIZE_REF_OR_NULL)))

3341

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

3342

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

3343

KEY_OPTIMIZE_REF_OR_NULL)))

3336

3344

{

3337

found_part|= keyuse->keypart_map;

3338

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

3339

const_part|= keyuse->keypart_map;

3345

found_part|= keyuse->getKeypartMap();

3346

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

3347

const_part|= keyuse->getKeypartMap();

3340

3348

3341

3349

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

3342

keyuse->used_tables));

3350

keyuse->getUsedTables()));

3343

3351

if (tmp2 < best_prev_record_reads)

3344

3352

{

3345

best_part_found_ref= keyuse->used_tables & ~join->const_table_map;

3353

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

3346

3354

best_prev_record_reads= tmp2;

3347

3355

}

3348

if (rec > keyuse->ref_table_rows)

3349

rec= keyuse->ref_table_rows;

3356

if (rec > keyuse->getTableRows())

3357

rec= keyuse->getTableRows();

3350

3358

/*

3351

3359

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

3352

3360

use this ref_or_null optimisation of this field

3353

3361

*/

3354

if (keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL)

3355

ref_or_null_part |= keyuse->keypart_map;

3362

if (keyuse->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL)

3363

ref_or_null_part|= keyuse->getKeypartMap();

3356

3364

}

3357

3365

3358

3366

keyuse++;

3359

} while (keyuse->table == table && keyuse->key == key &&

3360

keyuse->keypart == keypart);

3361

found_ref|= best_part_found_ref;

3362

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

3367

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

3368

keyuse->getKeypart() == keypart);

3369

found_ref|= best_part_found_ref;

3370

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

3363

3371

3364

3372

/*

3365

3373

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

3667

3675

scan.

3668

3676

*/

3669

3677

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

3670

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

3671

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

3672

!((s->table->file->ha_table_flags() & HA_TABLE_SCAN_ON_INDEX) && // (3)

3673

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

3674

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

3678

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

3679

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

3680

! ((s->table->file->ha_table_flags() & HA_TABLE_SCAN_ON_INDEX) && // (3)

3681

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

3682

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

3675

3683

{ // Check full join

3676

3684

ha_rows rnd_records= s->found_records;

3677

3685

/*

5512

5520

{

5513

5521

int error;

5514

5522

Table *table;

5515

uint32_t i,table_count,const_count,key;

5516

table_map found_const_table_map, all_table_map, found_ref, refs;

5517

key_map const_ref, eq_part;

5518

Table **table_vector;

5519

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

5520

KeyUse *keyuse,*start_keyuse;

5521

table_map outer_join=0;

5523

uint32_t i;

5524

uint32_t table_count;

5525

uint32_t const_count;

5526

uint32_t key;

5527

table_map found_const_table_map;

5528

table_map all_table_map;

5529

table_map found_ref;

5530

table_map refs;

5531

key_map const_ref;

5532

key_map eq_part;

5533

Table **table_vector= NULL;

5534

JoinTable *stat= NULL;

5535

JoinTable *stat_end= NULL;

5536

JoinTable *s= NULL;

5537

JoinTable **stat_ref= NULL;

5538

optimizer::KeyUse *keyuse= NULL;

5539

optimizer::KeyUse *start_keyuse= NULL;

5540

table_map outer_join= 0;

5522

5541

vector<optimizer::SargableParam> sargables;

5523

5542

JoinTable *stat_vector[MAX_TABLES+1];

5524

5543

optimizer::Position *partial_pos;

5525

5544

5526

table_count=join->tables;

5527

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

5528

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

5529

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

5545

table_count= join->tables;

5546

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

5547

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

5548

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

5530

5549

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

5531

5550

return 1;

5532

5551

5576

5595

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

5577

5596

{ // Empty table

5578

5597

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

5579

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

5598

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

5580

5599

continue;

5581

5600

}

5582

5601

outer_join|= table->map;

5604

5623

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

5605

5624

!join->no_const_tables)

5606

5625

{

5607

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

5626

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

5608

5627

}

5609

5628

}

5610

5629

stat_vector[i]=0;

5684

5703

set_position() will move all const_tables first in stat_vector

5685

5704

*/

5686

5705

5687

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

5706

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

5688

5707

{

5689

table=s->table;

5708

table= s->table;

5690

5709

5691

5710

/*

5692

5711

If equi-join condition by a key is null rejecting and after a

5705

5724

TODO. Apply single row substitution to null complemented inner tables

5706

5725

for nested outer join operations.

5707

5726

*/

5708

while (keyuse->table == table)

5727

while (keyuse->getTable() == table)

5709

5728

{

5710

if (!(keyuse->val->used_tables() & ~join->const_table_map) &&

5711

keyuse->val->is_null() && keyuse->null_rejecting)

5729

if (! (keyuse->getVal()->used_tables() & ~join->const_table_map) &&

5730

keyuse->getVal()->is_null() && keyuse->isNullRejected())

5712

5731

{

5713

5732

s->type= AM_CONST;

5714

5733

table->mark_as_null_row();

5715

5734

found_const_table_map|= table->map;

5716

5735

join->const_table_map|= table->map;

5717

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

5736

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

5718

5737

goto more_const_tables_found;

5719

5738

}

5720

5739

keyuse++;

5733

5752

int tmp= 0;

5734

5753

s->type= AM_SYSTEM;

5735

5754

join->const_table_map|=table->map;

5736

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

5755

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

5737

5756

partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);

5738

5757

if ((tmp= join_read_const_table(s, partial_pos)))

5739

5758

{

5749

5768

if ((keyuse=s->keyuse))

5750

5769

{

5751

5770

s->type= AM_REF;

5752

while (keyuse->table == table)

5771

while (keyuse->getTable() == table)

5753

5772

{

5754

start_keyuse=keyuse;

5755

key=keyuse->key;

5773

start_keyuse= keyuse;

5774

key= keyuse->getKey();

5756

5775

s->keys.set(key); // QQ: remove this ?

5757

5776

5758

refs=0;

5759

const_ref.reset();

5777

refs= 0;

5778

const_ref.reset();

5760

5779

eq_part.reset();

5761

5780

do

5762

5781

{

5763

if (keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize)

5782

if (keyuse->getVal()->type() != Item::NULL_ITEM &&

5783

! keyuse->getOptimizeFlags())

5764

5784

{

5765

if (!((~found_const_table_map) & keyuse->used_tables))

5766

const_ref.set(keyuse->keypart);

5785

if (! ((~found_const_table_map) & keyuse->getUsedTables()))

5786

const_ref.set(keyuse->getKeypart());

5767

5787

else

5768

refs|=keyuse->used_tables;

5769

eq_part.set(keyuse->keypart);

5788

refs|= keyuse->getUsedTables();

5789

eq_part.set(keyuse->getKeypart());

5770

5790

}

5771

5791

keyuse++;

5772

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

5792

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

5773

5793

5774

5794

if (is_keymap_prefix(eq_part, table->key_info[key].key_parts) &&

5775

!table->pos_in_table_list->embedding)

5795

! table->pos_in_table_list->embedding)

5776

5796

{

5777

5797

if ((table->key_info[key].flags & (HA_NOSAME)) == HA_NOSAME)

5778

5798

{

5782

5802

ref_changed = 1;

5783

5803

s->type= AM_CONST;

5784

5804

join->const_table_map|= table->map;

5785

set_position(join,const_count++,s,start_keyuse);

5805

set_position(join, const_count++, s, start_keyuse);

5786

5806

if (create_ref_for_key(join, s, start_keyuse, found_const_table_map))

5787

5807

return 1;

5788

5808

partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);

5879

5899

caller to abort with a zero row result.

5880

5900

*/

5881

5901

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

5882

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

5902

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

5883

5903

s->type= AM_CONST;

5884

5904

if (*s->on_expr_ref)

5885

5905

{