~drizzle-trunk/drizzle/development : revision 1139

46

#include "drizzled/item/outer_ref.h"

47

#include "drizzled/index_hint.h"

48

49

#include <drizzled/sql_union.h>

50

#include <drizzled/optimizer/key_field.h>

51

#include <drizzled/optimizer/position.h>

52

#include <drizzled/optimizer/sargable_param.h>

49

#include "drizzled/sql_union.h"

50

#include "drizzled/optimizer/key_field.h"

51

#include "drizzled/optimizer/position.h"

52

#include "drizzled/optimizer/sargable_param.h"

53

#include "drizzled/optimizer/key_use.h"

53

54

55

#include <string>

55

56

#include <iostream>

76

77

"index_merge"

77

78

};

78

79

static int sort_keyuse(KeyUse *a,KeyUse *b);

80

static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b);

80

81

static COND *build_equal_items(Session *session, COND *cond,

81

82

COND_EQUAL *inherited,

82

83

List<TableList> *join_list,

513

514

return found;

514

515

}

515

516

static int sort_keyuse(KeyUse *a,KeyUse *b)

517

static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b)

517

518

{

518

519

int res;

519

if (a->table->tablenr != b->table->tablenr)

520

return (int) (a->table->tablenr - b->table->tablenr);

521

if (a->key != b->key)

522

return (int) (a->key - b->key);

523

if (a->keypart != b->keypart)

524

return (int) (a->keypart - b->keypart);

520

if (a->getTable()->tablenr != b->getTable()->tablenr)

521

return static_cast<int>((a->getTable()->tablenr - b->getTable()->tablenr));

522

if (a->getKey() != b->getKey())

523

return static_cast<int>((a->getKey() - b->getKey()));

524

if (a->getKeypart() != b->getKeypart())

525

return static_cast<int>((a->getKeypart() - b->getKeypart()));

525

526

// Place const values before other ones

526

if ((res= test((a->used_tables & ~OUTER_REF_TABLE_BIT)) -

527

test((b->used_tables & ~OUTER_REF_TABLE_BIT))))

527

if ((res= test((a->getUsedTables() & ~OUTER_REF_TABLE_BIT)) -

528

test((b->getUsedTables() & ~OUTER_REF_TABLE_BIT))))

528

529

return res;

529

530

/* Place rows that are not 'OPTIMIZE_REF_OR_NULL' first */

530

return (int) ((a->optimize & KEY_OPTIMIZE_REF_OR_NULL) -

531

(b->optimize & KEY_OPTIMIZE_REF_OR_NULL));

531

return static_cast<int>(((a->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL) -

532

(b->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL)));

532

533

}

533

534

535

592

593

and_level= 0;

593

594

field= end= key_fields;

594

595

if (my_init_dynamic_array(keyuse,sizeof(KeyUse),20,64))

596

if (my_init_dynamic_array(keyuse, sizeof(optimizer::KeyUse), 20, 64))

596

597

return true;

597

598

if (cond)

598

599

{

599

600

add_key_fields(join_tab->join, &end, &and_level, cond, normal_tables,

600

601

sargables);

601

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

602

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

602

603

{

603

add_key_part(keyuse,field);

604

add_key_part(keyuse, field);

604

605

/* Mark that we can optimize LEFT JOIN */

605

if (field->val->type() == Item::NULL_ITEM &&

606

!field->field->real_maybe_null())

607

field->field->table->reginfo.not_exists_optimize=1;

606

if (field->getValue()->type() == Item::NULL_ITEM &&

607

! field->getField()->real_maybe_null())

608

{

609

field->getField()->table->reginfo.not_exists_optimize= 1;

610

}

608

611

}

609

612

}

610

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

613

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

611

614

{

612

615

/*

613

616

Block the creation of keys for inner tables of outer joins.

651

654

*/

652

655

if (keyuse->elements)

653

656

{

654

KeyUse key_end,*prev,*save_pos,*use;

657

optimizer::KeyUse key_end,*prev,*save_pos,*use;

655

658

656

my_qsort(keyuse->buffer,keyuse->elements,sizeof(KeyUse),

659

my_qsort(keyuse->buffer,keyuse->elements,sizeof(optimizer::KeyUse),

657

660

(qsort_cmp) sort_keyuse);

658

661

659

662

memset(&key_end, 0, sizeof(key_end)); /* Add for easy testing */

660

663

insert_dynamic(keyuse,(unsigned char*) &key_end);

661

664

662

use=save_pos=dynamic_element(keyuse,0,KeyUse*);

665

use= save_pos= dynamic_element(keyuse, 0, optimizer::KeyUse*);

663

666

prev= &key_end;

664

found_eq_constant=0;

665

for (i=0 ; i < keyuse->elements-1 ; i++,use++)

667

found_eq_constant= 0;

668

for (i= 0; i < keyuse->elements-1; i++, use++)

666

669

{

667

if (!use->used_tables && use->optimize != KEY_OPTIMIZE_REF_OR_NULL)

668

use->table->const_key_parts[use->key]|= use->keypart_map;

669

if (use->key == prev->key && use->table == prev->table)

670

if (! use->getUsedTables() && use->getOptimizeFlags() != KEY_OPTIMIZE_REF_OR_NULL)

671

use->getTable()->const_key_parts[use->getKey()]|= use->getKeypartMap();

672

if (use->getKey() == prev->getKey() && use->getTable() == prev->getTable())

670

673

{

671

if (prev->keypart+1 < use->keypart || ((prev->keypart == use->keypart) && found_eq_constant))

674

if (prev->getKeypart() + 1 < use->getKeypart() ||

675

((prev->getKeypart() == use->getKeypart()) && found_eq_constant))

672

676

continue; /* remove */

673

677

}

674

else if (use->keypart != 0) // First found must be 0

678

else if (use->getKeypart() != 0) // First found must be 0

675

679

continue;

676

680

677

681

#ifdef HAVE_purify

680

684

#endif

681

685

*save_pos= *use;

682

686

prev=use;

683

found_eq_constant= !use->used_tables;

687

found_eq_constant= ! use->getUsedTables();

684

688

/* Save ptr to first use */

685

if (!use->table->reginfo.join_tab->keyuse)

686

use->table->reginfo.join_tab->keyuse=save_pos;

687

use->table->reginfo.join_tab->checked_keys.set(use->key);

689

if (! use->getTable()->reginfo.join_tab->keyuse)

690

use->getTable()->reginfo.join_tab->keyuse= save_pos;

691

use->getTable()->reginfo.join_tab->checked_keys.set(use->getKey());

688

692

save_pos++;

689

693

}

690

i=(uint32_t) (save_pos-(KeyUse*) keyuse->buffer);

691

set_dynamic(keyuse,(unsigned char*) &key_end,i);

692

keyuse->elements=i;

694

i= (uint32_t) (save_pos - (optimizer::KeyUse*) keyuse->buffer);

695

set_dynamic(keyuse, (unsigned char*) &key_end, i);

696

keyuse->elements= i;

693

697

}

694

698

return false;

695

699

}

699

703

*/

700

704

void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array)

701

705

{

702

KeyUse *end,*keyuse= dynamic_element(keyuse_array, 0, KeyUse*);

706

optimizer::KeyUse *end,*keyuse= dynamic_element(keyuse_array,

707

0,

708

optimizer::KeyUse*);

703

709

704

710

for (end= keyuse+ keyuse_array->elements ; keyuse < end ; keyuse++)

705

711

{

712

718

Constant tables are ignored.

713

719

To avoid bad matches, we don't make ref_table_rows less than 100.

714

720

*/

715

keyuse->ref_table_rows= ~(ha_rows) 0; // If no ref

716

if (keyuse->used_tables & (map= (keyuse->used_tables & ~join->const_table_map & ~OUTER_REF_TABLE_BIT)))

721

keyuse->setTableRows(~(ha_rows) 0); // If no ref

722

if (keyuse->getUsedTables() & (map= (keyuse->getUsedTables() & ~join->const_table_map & ~OUTER_REF_TABLE_BIT)))

717

723

{

718

724

uint32_t tablenr;

719

725

for (tablenr=0 ; ! (map & 1) ; map>>=1, tablenr++) ;

720

726

if (map == 1) // Only one table

721

727

{

722

728

Table *tmp_table=join->all_tables[tablenr];

723

keyuse->ref_table_rows= max(tmp_table->file->stats.records, (ha_rows)100);

729

keyuse->setTableRows(max(tmp_table->file->stats.records, (ha_rows)100));

724

730

}

725

731

}

726

732

/*

727

733

Outer reference (external field) is constant for single executing

728

734

of subquery

729

735

*/

730

if (keyuse->used_tables == OUTER_REF_TABLE_BIT)

731

keyuse->ref_table_rows= 1;

736

if (keyuse->getUsedTables() == OUTER_REF_TABLE_BIT)

737

keyuse->setTableRows(1);

732

738

}

733

739

}

734

740

884

890

}

885

891

886

892

StoredKey *get_store_key(Session *session,

887

KeyUse *keyuse,

893

optimizer::KeyUse *keyuse,

888

894

table_map used_tables,

889

KEY_PART_INFO *key_part,

895

KEY_PART_INFO *key_part,

890

896

unsigned char *key_buff,

891

897

uint32_t maybe_null)

892

898

{

893

if (!((~used_tables) & keyuse->used_tables)) // if const item

899

Item_ref *key_use_val= static_cast<Item_ref *>(keyuse->getVal());

900

Item_ref **dir_val= reinterpret_cast<Item_ref **>(key_use_val->ref);

901

if (! ((~used_tables) & keyuse->getUsedTables())) // if const item

894

902

{

895

903

return new store_key_const_item(session,

896

904

key_part->field,

897

905

key_buff + maybe_null,

898

906

maybe_null ? key_buff : 0,

899

907

key_part->length,

900

keyuse->val);

908

key_use_val);

901

909

}

902

else if (keyuse->val->type() == Item::FIELD_ITEM ||

903

(keyuse->val->type() == Item::REF_ITEM &&

904

((Item_ref*)keyuse->val)->ref_type() == Item_ref::OUTER_REF &&

905

(*(Item_ref**)((Item_ref*)keyuse->val)->ref)->ref_type() ==

906

Item_ref::DIRECT_REF &&

907

keyuse->val->real_item()->type() == Item::FIELD_ITEM))

910

else if (key_use_val->type() == Item::FIELD_ITEM ||

911

(key_use_val->type() == Item::REF_ITEM &&

912

key_use_val->ref_type() == Item_ref::OUTER_REF &&

913

(*dir_val)->ref_type() == Item_ref::DIRECT_REF &&

914

key_use_val->real_item()->type() == Item::FIELD_ITEM))

915

{

908

916

return new store_key_field(session,

909

917

key_part->field,

910

918

key_buff + maybe_null,

911

919

maybe_null ? key_buff : 0,

912

920

key_part->length,

913

((Item_field*) keyuse->val->real_item())->field,

914

keyuse->val->full_name());

921

((Item_field*) key_use_val->real_item())->field,

922

key_use_val->full_name());

923

}

915

924

return new store_key_item(session,

916

925

key_part->field,

917

926

key_buff + maybe_null,

918

927

maybe_null ? key_buff : 0,

919

928

key_part->length,

920

keyuse->val);

929

key_use_val);

921

930

}

922

931

923

932

/**

960

969

*e1= e2;

961

970

}

962

971

963

bool create_ref_for_key(JOIN *join, JoinTable *j, KeyUse *org_keyuse,

964

table_map used_tables)

972

bool create_ref_for_key(JOIN *join,

973

JoinTable *j,

974

optimizer::KeyUse *org_keyuse,

975

table_map used_tables)

965

976

{

966

KeyUse *keyuse=org_keyuse;

977

optimizer::KeyUse *keyuse= org_keyuse;

967

978

Session *session= join->session;

968

uint32_t keyparts,length,key;

969

Table *table;

970

KEY *keyinfo;

979

uint32_t keyparts;

980

uint32_t length;

981

uint32_t key;

982

Table *table= NULL;

983

KEY *keyinfo= NULL;

971

984

972

985

/* Use best key from find_best */

973

table=j->table;

974

key=keyuse->key;

975

keyinfo=table->key_info+key;

986

table= j->table;

987

key= keyuse->getKey();

988

keyinfo= table->key_info + key;

976

989

977

990

{

978

keyparts=length=0;

991

keyparts= length= 0;

979

992

uint32_t found_part_ref_or_null= 0;

980

993

/*

981

994

Calculate length for the used key

984

997

*/

985

998

do

986

999

{

987

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

1000

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

988

1001

{

989

if (keyparts == keyuse->keypart &&

990

!(found_part_ref_or_null & keyuse->optimize))

1002

if (keyparts == keyuse->getKeypart() &&

1003

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

991

1004

{

992

1005

keyparts++;

993

length+= keyinfo->key_part[keyuse->keypart].store_length;

994

found_part_ref_or_null|= keyuse->optimize;

1006

length+= keyinfo->key_part[keyuse->getKeypart()].store_length;

1007

found_part_ref_or_null|= keyuse->getOptimizeFlags();

995

1008

}

996

1009

}

997

1010

keyuse++;

998

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

1011

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

999

1012

}

1000

1013

1001

1014

/* set up fieldref */

1018

1031

keyuse=org_keyuse;

1019

1032

1020

1033

StoredKey **ref_key= j->ref.key_copy;

1021

unsigned char *key_buff=j->ref.key_buff, *null_ref_key= 0;

1034

unsigned char *key_buff= j->ref.key_buff, *null_ref_key= 0;

1022

1035

bool keyuse_uses_no_tables= true;

1023

1036

{

1024

uint32_t i;

1025

for (i=0 ; i < keyparts ; keyuse++,i++)

1037

for (uint32_t i= 0; i < keyparts; keyuse++, i++)

1026

1038

{

1027

while (keyuse->keypart != i ||

1028

((~used_tables) & keyuse->used_tables))

1039

while (keyuse->getKeypart() != i ||

1040

((~used_tables) & keyuse->getUsedTables()))

1029

1041

keyuse++; /* Skip other parts */

1030

1042

1031

1043

uint32_t maybe_null= test(keyinfo->key_part[i].null_bit);

1032

j->ref.items[i]=keyuse->val; // Save for cond removal

1033

j->ref.cond_guards[i]= keyuse->cond_guard;

1034

if (keyuse->null_rejecting)

1044

j->ref.items[i]= keyuse->getVal(); // Save for cond removal

1045

j->ref.cond_guards[i]= keyuse->getConditionalGuard();

1046

if (keyuse->isNullRejected())

1035

1047

j->ref.null_rejecting |= 1 << i;

1036

keyuse_uses_no_tables= keyuse_uses_no_tables && !keyuse->used_tables;

1037

if (!keyuse->used_tables && !(join->select_options & SELECT_DESCRIBE))

1048

keyuse_uses_no_tables= keyuse_uses_no_tables && ! keyuse->getUsedTables();

1049

if (! keyuse->getUsedTables() && !(join->select_options & SELECT_DESCRIBE))

1038

1050

{ // Compare against constant

1039

1051

store_key_item tmp(session, keyinfo->key_part[i].field,

1040

1052

key_buff + maybe_null,

1041

1053

maybe_null ? key_buff : 0,

1042

keyinfo->key_part[i].length, keyuse->val);

1054

keyinfo->key_part[i].length, keyuse->getVal());

1043

1055

if (session->is_fatal_error)

1044

1056

return(true);

1045

1057

tmp.copy();

1054

1066

But only if field _really_ can be null i.e. we force AM_REF

1055

1067

instead of AM_REF_OR_NULL in case if field can't be null

1056

1068

*/

1057

if ((keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL) && maybe_null)

1069

if ((keyuse->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL) && maybe_null)

1058

1070

null_ref_key= key_buff;

1059

1071

key_buff+=keyinfo->key_part[i].store_length;

1060

1072

}

1061

1073

}

1062

*ref_key=0; // end_marker

1074

*ref_key= 0; // end_marker

1063

1075

if (j->type == AM_CONST)

1064

1076

j->table->const_table= 1;

1065

1077

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

1082

1094

}

1083

1095

else

1084

1096

j->type= AM_EQ_REF;

1085

return(0);

1097

return 0;

1086

1098

}

1087

1099

1088

1100

/**

1137

1149

*/

1138

1150

void add_not_null_conds(JOIN *join)

1139

1151

{

1140

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

1152

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

1141

1153

{

1142

1154

JoinTable *tab=join->join_tab+i;

1143

1155

if ((tab->type == AM_REF || tab->type == AM_EQ_REF ||

2577

2589

if (possible_keys.any())

2578

2590

{

2579

2591

Table *field_tab= field->table;

2580

KeyUse *use;

2581

for (use= stat->keyuse; use && use->table == field_tab; use++)

2582

if (possible_keys.test(use->key) &&

2583

field_tab->key_info[use->key].key_part[use->keypart].field ==

2592

optimizer::KeyUse *use;

2593

for (use= stat->keyuse; use && use->getTable() == field_tab; use++)

2594

if (possible_keys.test(use->getKey()) &&

2595

field_tab->key_info[use->getKey()].key_part[use->getKeypart()].field ==

2584

2596

field)

2585

field_tab->const_key_parts[use->key]|= use->keypart_map;

2597

field_tab->const_key_parts[use->getKey()]|= use->getKeypartMap();

2586

2598

}

2587

2599

}

2588

2600

}

4492

4504

*/

4493

4505

static int test_if_order_by_key(order_st *order, Table *table, uint32_t idx, uint32_t *used_key_parts)

4494

4506

{

4495

KEY_PART_INFO *key_part,*key_part_end;

4496

key_part=table->key_info[idx].key_part;

4497

key_part_end=key_part+table->key_info[idx].key_parts;

4507

KEY_PART_INFO *key_part= NULL;

4508

KEY_PART_INFO *key_part_end= NULL;

4509

key_part= table->key_info[idx].key_part;

4510

key_part_end= key_part + table->key_info[idx].key_parts;

4498

4511

key_part_map const_key_parts=table->const_key_parts[idx];

4499

int reverse=0;

4512

int reverse= 0;

4500

4513

bool on_primary_key= false;

4501

4514

4502

4515

for (; order ; order=order->next, const_key_parts>>=1)

4576

4589

*/

4577

4590

inline bool is_subkey(KEY_PART_INFO *key_part,

4578

4591

KEY_PART_INFO *ref_key_part,

4579

KEY_PART_INFO *ref_key_part_end)

4592

KEY_PART_INFO *ref_key_part_end)

4580

4593

{

4581

4594

for (; ref_key_part < ref_key_part_end; key_part++, ref_key_part++)

4582

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

4595

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

4583

4596

return 0;

4584

4597

return 1;

4585

4598

}

4599

4612

Table *table,

4600

4613

uint32_t ref,

4601

4614

uint32_t ref_key_parts,

4602

const key_map *usable_keys)

4615

const key_map *usable_keys)

4603

4616

{

4604

4617

uint32_t nr;

4605

4618

uint32_t min_length= UINT32_MAX;

4663

4676

(table->key_info[keynr].flags & HA_NOSAME))

4664

4677

{

4665

4678

KEY *keyinfo= table->key_info + keynr;

4666

KEY_PART_INFO *key_part, *key_part_end;

4679

KEY_PART_INFO *key_part= NULL;

4680

KEY_PART_INFO *key_part_end= NULL;

4667

4681

4668

4682

for (key_part=keyinfo->key_part,

4669

4683

key_part_end=key_part+ keyinfo->key_parts;

4671

4685

key_part++)

4672

4686

{

4673

4687

if (key_part->field->maybe_null() ||

4674

!find_func(key_part->field, data))

4688

! find_func(key_part->field, data))

4675

4689

break;

4676

4690

}

4677

4691

if (key_part == key_part_end)

4858

4872

"part1 = const1 AND part2=const2".

4859

4873

So we build tab->ref from scratch here.

4860

4874

*/

4861

KeyUse *keyuse= tab->keyuse;

4862

while (keyuse->key != new_ref_key && keyuse->table == tab->table)

4875

optimizer::KeyUse *keyuse= tab->keyuse;

4876

while (keyuse->getKey() != new_ref_key && keyuse->getTable() == tab->table)

4863

4877

keyuse++;

4864

4878

4865

4879

if (create_ref_for_key(tab->join, tab, keyuse,