« back to all changes in this revision
Viewing changes to drizzled/join.cc
- browse files at revision 1120
- compare with another revision
- compare with revision 2008
- download diff
- download tarball
- view history from revision 1120
- Committer: Brian Aker
- Date: 2009-08-20 22:37:23 UTC
- mfrom: (1115.3.10 captain)
- Revision ID: brian@gaz-20090820223723-mi4rirwlvuerj345
Merge Jay
- files added:
- drizzled/optimizer
- files removed:
- plugin/md5/Makefile.am
- files modified:
- config/autorun.sh
added
removed
drizzled/join.cc
42
42
#include "drizzled/join_cache.h"
43
43
#include "drizzled/show.h"
44
44
#include "drizzled/field/blob.h"
45
#include "drizzled/optimizer/position.h"
46
#include "drizzled/optimizer/sargable_param.h"
45
47
#include "mysys/my_bit.h"
46
48
47
49
#include <algorithm>
48
50
49
51
using namespace std;
52
using namespace drizzled;
50
53
51
54
/** Declarations of static functions used in this source file. */
52
55
static bool make_group_fields(JOIN *main_join, JOIN *curr_join);
53
56
static void calc_group_buffer(JOIN *join,order_st *group);
54
57
static bool alloc_group_fields(JOIN *join,order_st *group);
55
/*
56
TODO: 'find_best' is here only temporarily until 'greedy_search' is
57
tested and approved.
58
*/
59
static bool find_best(JOIN *join,table_map rest_tables,uint32_t index, double record_count,double read_time);
60
58
static uint32_t cache_record_length(JOIN *join, uint32_t index);
61
59
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref);
62
60
static bool get_best_combination(JOIN *join);
3014
3012
return false;
3015
3013
}
3016
3014
3017
/**
3018
@todo
3019
- TODO: this function is here only temporarily until 'greedy_search' is
3020
tested and accepted.
3021
3022
RETURN VALUES
3023
false ok
3024
true Fatal error
3025
*/
3026
static bool find_best(JOIN *join,table_map rest_tables,uint32_t idx,double record_count, double read_time)
3027
{
3028
Session *session= join->session;
3029
Position partial_pos;
3030
if (session->killed)
3031
{
3032
return true;
3033
}
3034
3035
if (! rest_tables)
3036
{
3037
read_time+= record_count/(double) TIME_FOR_COMPARE;
3038
partial_pos= join->getPosFromPartialPlan(join->const_tables);
3039
if (join->sort_by_table &&
3040
join->sort_by_table !=
3041
partial_pos.table->table)
3042
{
3043
read_time+= record_count; // We have to make a temp table
3044
}
3045
if (read_time < join->best_read)
3046
{
3047
join->copyPartialPlanIntoOptimalPlan(idx);
3048
join->best_read= read_time - 0.001;
3049
}
3050
return false;
3051
}
3052
if (read_time+record_count/(double) TIME_FOR_COMPARE >= join->best_read)
3053
{
3054
return false; /* Found better before */
3055
}
3056
3057
JoinTable *s;
3058
double best_record_count= DBL_MAX;
3059
double best_read_time= DBL_MAX;
3060
for (JoinTable **pos= join->best_ref+idx ; (s= *pos) ; pos++)
3061
{
3062
table_map real_table_bit= s->table->map;
3063
if (idx)
3064
{
3065
partial_pos= join->getPosFromPartialPlan(idx - 1);
3066
}
3067
if ((rest_tables & real_table_bit) && !(rest_tables & s->dependent) &&
3068
(! idx || ! check_interleaving_with_nj(partial_pos.table, s)))
3069
{
3070
double records, best;
3071
best_access_path(join, s, session, rest_tables, idx, record_count,
3072
read_time);
3073
partial_pos= join->getPosFromPartialPlan(idx);
3074
records= partial_pos.records_read;
3075
best= partial_pos.read_time;
3076
/*
3077
Go to the next level only if there hasn't been a better key on
3078
this level! This will cut down the search for a lot simple cases!
3079
*/
3080
double current_record_count= record_count * records;
3081
double current_read_time= read_time + best;
3082
if (best_record_count > current_record_count ||
3083
best_read_time > current_read_time ||
3084
(idx == join->const_tables && s->table == join->sort_by_table))
3085
{
3086
if (best_record_count >= current_record_count &&
3087
best_read_time >= current_read_time &&
3088
(! (s->key_dependent & rest_tables) ||
3089
partial_pos.isConstTable()))
3090
{
3091
best_record_count= current_record_count;
3092
best_read_time= current_read_time;
3093
}
3094
std::swap(join->best_ref[idx], *pos);
3095
if (find_best(join,rest_tables & ~real_table_bit,idx+1,
3096
current_record_count,current_read_time))
3097
{
3098
return true;
3099
}
3100
std::swap(join->best_ref[idx], *pos);
3101
}
3102
restore_prev_nj_state(s);
3103
if (join->select_options & SELECT_STRAIGHT_JOIN)
3104
break; // Don't test all combinations
3105
}
3106
}
3107
return false;
3108
}
3109
3110
3015
static uint32_t cache_record_length(JOIN *join,uint32_t idx)
3111
3016
{
3112
3017
uint32_t length=0;
3178
3083
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref)
3179
3084
{
3180
3085
double found=1.0;
3181
Position *pos_end= join->getSpecificPosInPartialPlan(-1);
3182
for (Position *pos= join->getSpecificPosInPartialPlan(idx - 1);
3086
optimizer::Position *pos_end= join->getSpecificPosInPartialPlan(-1);
3087
for (optimizer::Position *pos= join->getSpecificPosInPartialPlan(idx - 1);
3183
3088
pos != pos_end;
3184
3089
pos--)
3185
3090
{
3186
if (pos->table->table->map & found_ref)
3091
if (pos->examinePosition(found_ref))
3187
3092
{
3188
found_ref|= pos->ref_depend_map;
3093
found_ref|= pos->getRefDependMap();
3189
3094
/*
3190
3095
For the case of "t1 LEFT JOIN t2 ON ..." where t2 is a const table
3191
3096
with no matching row we will get position[t2].records_read==0.
3202
3107
is an inprecise estimate and adding 1 (or, in the worst case,
3203
3108
#max_nested_outer_joins=64-1) will not make it any more precise.
3204
3109
*/
3205
if (pos->records_read > DBL_EPSILON)
3206
found*= pos->records_read;
3110
if (pos->getFanout() > DBL_EPSILON)
3111
found*= pos->getFanout();
3207
3112
}
3208
3113
}
3209
3114
return found;
3220
3125
KeyUse *keyuse;
3221
3126
uint32_t table_count;
3222
3127
Session *session=join->session;
3223
Position cur_pos;
3128
optimizer::Position cur_pos;
3224
3129
3225
3130
table_count=join->tables;
3226
3131
if (!(join->join_tab=join_tab=
3234
3139
{
3235
3140
Table *form;
3236
3141
cur_pos= join->getPosFromOptimalPlan(tablenr);
3237
*j= *cur_pos.table;
3142
*j= *cur_pos.getJoinTable();
3238
3143
form=join->table[tablenr]=j->table;
3239
3144
used_tables|= form->map;
3240
3145
form->reginfo.join_tab=j;
3248
3153
3249
3154
if (j->type == AM_SYSTEM)
3250
3155
continue;
3251
if (j->keys.none() || !(keyuse= cur_pos.key))
3156
if (j->keys.none() || ! (keyuse= cur_pos.getKeyUse()))
3252
3157
{
3253
3158
j->type= AM_ALL;
3254
3159
if (tablenr != join->const_tables)
3267
3172
/** Save const tables first as used tables. */
3268
3173
static void set_position(JOIN *join,uint32_t idx,JoinTable *table,KeyUse *key)
3269
3174
{
3270
Position tmp_pos;
3271
tmp_pos.table= table;
3272
tmp_pos.key= key;
3273
tmp_pos.records_read= 1.0; /* This is a const table */
3274
tmp_pos.ref_depend_map= 0;
3175
optimizer::Position tmp_pos(1.0, /* This is a const table */
3176
0.0,
3177
table,
3178
key,
3179
0);
3275
3180
join->setPosInPartialPlan(idx, tmp_pos);
3276
3181
3277
3182
/* Move the const table as down as possible in best_ref */
3299
3204
the query
3300
3205
@param join_tables set of the tables in the query
3301
3206
3302
@todo
3303
'MAX_TABLES+2' denotes the old implementation of find_best before
3304
the greedy version. Will be removed when greedy_search is approved.
3305
3306
3207
@retval
3307
3208
false ok
3308
3209
@retval
3333
3234
}
3334
3235
else
3335
3236
{
3336
if (search_depth == MAX_TABLES+2)
3337
{ /*
3338
TODO: 'MAX_TABLES+2' denotes the old implementation of find_best before
3339
the greedy version. Will be removed when greedy_search is approved.
3340
*/
3341
join->best_read= DBL_MAX;
3342
if (find_best(join, join_tables, join->const_tables, 1.0, 0.0))
3343
return(true);
3344
}
3345
else
3346
{
3347
if (search_depth == 0)
3348
/* Automatically determine a reasonable value for 'search_depth' */
3349
search_depth= determine_search_depth(join);
3350
if (greedy_search(join, join_tables, search_depth, prune_level))
3351
return(true);
3352
}
3237
if (search_depth == 0)
3238
/* Automatically determine a reasonable value for 'search_depth' */
3239
search_depth= determine_search_depth(join);
3240
if (greedy_search(join, join_tables, search_depth, prune_level))
3241
return true;
3353
3242
}
3354
3243
3355
3244
/*
3878
3767
}
3879
3768
3880
3769
/* Update the cost information for the current partial plan */
3881
Position tmp_pos;
3882
tmp_pos.records_read= records;
3883
tmp_pos.read_time= best;
3884
tmp_pos.key= best_key;
3885
tmp_pos.table= s;
3886
tmp_pos.ref_depend_map= best_ref_depends_map;
3770
optimizer::Position tmp_pos(records,
3771
best,
3772
s,
3773
best_key,
3774
best_ref_depends_map);
3887
3775
join->setPosInPartialPlan(idx, tmp_pos);
3888
3776
3889
3777
if (!best_key &&
3920
3808
static void optimize_straight_join(JOIN *join, table_map join_tables)
3921
3809
{
3922
3810
JoinTable *s;
3923
Position partial_pos;
3811
optimizer::Position partial_pos;
3924
3812
uint32_t idx= join->const_tables;
3925
3813
double record_count= 1.0;
3926
3814
double read_time= 0.0;
3932
3820
record_count, read_time);
3933
3821
/* compute the cost of the new plan extended with 's' */
3934
3822
partial_pos= join->getPosFromPartialPlan(idx);
3935
record_count*= partial_pos.records_read;
3936
read_time+= partial_pos.read_time;
3823
record_count*= partial_pos.getFanout();
3824
read_time+= partial_pos.getCost();
3937
3825
join_tables&= ~(s->table->map);
3938
3826
++idx;
3939
3827
}
3941
3829
read_time+= record_count / (double) TIME_FOR_COMPARE;
3942
3830
partial_pos= join->getPosFromPartialPlan(join->const_tables);
3943
3831
if (join->sort_by_table &&
3944
join->sort_by_table != partial_pos.table->table)
3832
partial_pos.hasTableForSorting(join->sort_by_table))
3945
3833
read_time+= record_count; // We have to make a temp table
3946
3834
join->copyPartialPlanIntoOptimalPlan(idx);
3947
3835
join->best_read= read_time;
4037
3925
uint32_t idx= join->const_tables; // index into 'join->best_ref'
4038
3926
uint32_t best_idx;
4039
3927
uint32_t size_remain; // cardinality of remaining_tables
4040
Position best_pos;
3928
optimizer::Position best_pos;
4041
3929
JoinTable *best_table; // the next plan node to be added to the curr QEP
4042
3930
4043
3931
/* number of tables that remain to be optimized */
4061
3949
4062
3950
/* select the first table in the optimal extension as most promising */
4063
3951
best_pos= join->getPosFromOptimalPlan(idx);
4064
best_table= best_pos.table;
3952
best_table= best_pos.getJoinTable();
4065
3953
/*
4066
3954
Each subsequent loop of 'best_extension_by_limited_search' uses
4067
3955
'join->positions' for cost estimates, therefore we have to update its
4079
3967
std::swap(join->best_ref[idx], join->best_ref[best_idx]);
4080
3968
4081
3969
/* compute the cost of the new plan extended with 'best_table' */
4082
Position partial_pos= join->getPosFromPartialPlan(idx);
4083
record_count*= partial_pos.records_read;
4084
read_time+= partial_pos.read_time;
3970
optimizer::Position partial_pos= join->getPosFromPartialPlan(idx);
3971
record_count*= partial_pos.getFanout();
3972
read_time+= partial_pos.getCost();
4085
3973
4086
3974
remaining_tables&= ~(best_table->table->map);
4087
3975
--size_remain;
4225
4113
JoinTable *s;
4226
4114
double best_record_count= DBL_MAX;
4227
4115
double best_read_time= DBL_MAX;
4228
Position partial_pos;
4116
optimizer::Position partial_pos;
4229
4117
4230
4118
for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
4231
4119
{
4235
4123
partial_pos= join->getPosFromPartialPlan(idx - 1);
4236
4124
}
4237
4125
if ((remaining_tables & real_table_bit) &&
4238
!(remaining_tables & s->dependent) &&
4239
(!idx || !check_interleaving_with_nj(partial_pos.table, s)))
4126
! (remaining_tables & s->dependent) &&
4127
(! idx || ! check_interleaving_with_nj(partial_pos.getJoinTable(), s)))
4240
4128
{
4241
4129
double current_record_count, current_read_time;
4242
4130
4252
4140
record_count, read_time);
4253
4141
/* Compute the cost of extending the plan with 's' */
4254
4142
partial_pos= join->getPosFromPartialPlan(idx);
4255
current_record_count= record_count * partial_pos.records_read;
4256
current_read_time= read_time + partial_pos.read_time;
4143
current_record_count= record_count * partial_pos.getFanout();
4144
current_read_time= read_time + partial_pos.getCost();
4257
4145
4258
4146
/* Expand only partial plans with lower cost than the best QEP so far */
4259
4147
if ((current_read_time +
4311
4199
partial_pos= join->getPosFromPartialPlan(join->const_tables);
4312
4200
current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
4313
4201
if (join->sort_by_table &&
4314
join->sort_by_table !=
4315
partial_pos.table->table)
4202
partial_pos.hasTableForSorting(join->sort_by_table))
4316
4203
/* We have to make a temp table */
4317
4204
current_read_time+= current_record_count;
4318
4205
if ((search_depth == 1) || (current_read_time < join->best_read))
4535
4422
static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
4536
4423
{
4537
4424
Session *session= join->session;
4538
Position cur_pos;
4425
optimizer::Position cur_pos;
4539
4426
if (select)
4540
4427
{
4541
4428
add_not_null_conds(join);
4615
4502
tab->ref.key= -1;
4616
4503
tab->ref.key_parts= 0; // Don't use ref key.
4617
4504
cur_pos= join->getPosFromOptimalPlan(i);
4618
cur_pos.records_read= rows2double(tab->quick->records);
4505
cur_pos.setFanout(rows2double(tab->quick->records));
4619
4506
/*
4620
4507
We will use join cache here : prevent sorting of the first
4621
4508
table only and sort at the end.
4717
4604
cur_pos= join->getPosFromOptimalPlan(i);
4718
4605
if ((cond && (! ((tab->keys & tab->const_keys) == tab->keys) && i > 0)) ||
4719
4606
(! tab->const_keys.none() && (i == join->const_tables) &&
4720
(join->unit->select_limit_cnt < cur_pos.records_read) && ((join->select_options & OPTION_FOUND_ROWS) == false)))
4607
(join->unit->select_limit_cnt < cur_pos.getFanout()) && ((join->select_options & OPTION_FOUND_ROWS) == false)))
4721
4608
{
4722
4609
/* Join with outer join condition */
4723
4610
COND *orig_cond= sel->cond;
4763
4650
if (sel->quick)
4764
4651
{
4765
4652
cur_pos= join->getPosFromOptimalPlan(i);
4766
cur_pos.records_read= (double)sel->quick->records;
4653
cur_pos.setFanout(static_cast<double>(sel->quick->records));
4767
4654
}
4768
4655
}
4769
4656
else
5632
5519
JoinTable *stat,*stat_end,*s,**stat_ref;
5633
5520
KeyUse *keyuse,*start_keyuse;
5634
5521
table_map outer_join=0;
5635
SARGABLE_PARAM *sargables= 0;
5522
vector<optimizer::SargableParam> sargables;
5636
5523
JoinTable *stat_vector[MAX_TABLES+1];
5637
Position *partial_pos;
5524
optimizer::Position *partial_pos;
5638
5525
5639
5526
table_count=join->tables;
5640
5527
stat=(JoinTable*) join->session->calloc(sizeof(JoinTable)*table_count);
5760
5647
if (conds || outer_join)
5761
5648
if (update_ref_and_keys(join->session, keyuse_array, stat, join->tables,
5762
5649
conds, join->cond_equal,
5763
~outer_join, join->select_lex, &sargables))
5650
~outer_join, join->select_lex, sargables))
5764
5651
return 1;
5765
5652
5766
5653
/* Read tables with 0 or 1 rows (system tables) */
5767
5654
join->const_table_map= 0;
5768
5655
5769
Position *p_pos= join->getFirstPosInPartialPlan();
5770
Position *p_end= join->getSpecificPosInPartialPlan(const_count);
5656
optimizer::Position *p_pos= join->getFirstPosInPartialPlan();
5657
optimizer::Position *p_end= join->getSpecificPosInPartialPlan(const_count);
5771
5658
while (p_pos < p_end)
5772
5659
{
5773
5660
int tmp;
5774
s= p_pos->table;
5661
s= p_pos->getJoinTable();
5775
5662
s->type= AM_SYSTEM;
5776
5663
join->const_table_map|=s->table->map;
5777
5664
if ((tmp= join_read_const_table(s, p_pos)))
5923
5810
Update info on indexes that can be used for search lookups as
5924
5811
reading const tables may has added new sargable predicates.
5925
5812
*/
5926
if (const_count && sargables)
5813
if (const_count && ! sargables.empty())
5927
5814
{
5928
for( ; sargables->field ; sargables++)
5815
vector<optimizer::SargableParam>::iterator iter= sargables.begin();
5816
while (iter != sargables.end())
5929
5817
{
5930
Field *field= sargables->field;
5818
Field *field= (*iter).getField();
5931
5819
JoinTable *join_tab= field->table->reginfo.join_tab;
5932
5820
key_map possible_keys= field->key_start;
5933
5821
possible_keys&= field->table->keys_in_use_for_query;
5934
bool is_const= 1;
5935
for (uint32_t j=0; j < sargables->num_values; j++)
5936
is_const&= sargables->arg_value[j]->const_item();
5822
bool is_const= true;
5823
for (uint32_t j= 0; j < (*iter).getNumValues(); j++)
5824
is_const&= (*iter).isConstItem(j);
5937
5825
if (is_const)
5938
5826
join_tab[0].const_keys|= possible_keys;
5827
++iter;
5939
5828
}
5940
5829
}
5941
5830
Loggerhead is a web-based interface for Breezy
Version: 2.0.1