« back to all changes in this revision
Viewing changes to drizzled/join.cc
- browse files at revision 1039.5.47
- compare with another revision
- compare with revision 2093
- download diff
- download tarball
- view history from revision 1039.5.47
- Committer: Jay Pipes
- Date: 2009-08-03 14:23:22 UTC
- mfrom: (1107 staging)
- mto: (1143.2.1 replication-group-commit)
- mto: This revision was merged to the branch mainline in revision 1130.
- Revision ID: jpipes@serialcoder-20090803142322-1g67h7su9mocg9ig
Merge trunk
- files added:
- drizzled/command
- files removed:
- client/drizzlecheck.1
- files modified:
- .bzrignore
added
removed
drizzled/join.cc
28
28
*/
29
29
30
30
#include "drizzled/server_includes.h"
31
#include "drizzled/semi_join_table.h"
32
31
#include "drizzled/table_map_iterator.h"
33
32
#include "drizzled/item/cache.h"
34
33
#include "drizzled/item/cmpfunc.h"
94
93
uint64_t select_options,
95
94
const char *info,
96
95
Item *having);
97
static COND *simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top, bool in_sj);
96
static COND *simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top);
98
97
static int remove_duplicates(JOIN *join,Table *entry,List<Item> &fields, Item *having);
99
98
static int setup_without_group(Session *session,
100
99
Item **ref_pointer_array,
113
112
static bool test_if_subpart(order_st *a,order_st *b);
114
113
static void restore_prev_nj_state(JoinTable *last);
115
114
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
115
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, SemiJoinTable *sjtbl);
122
116
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, JoinTable *join_tab);
125
117
126
118
/**
127
119
Prepare of whole select (including sub queries in future).
218
210
*/
219
211
if ((subselect= select_lex->master_unit()->item))
220
212
{
221
bool do_semijoin= !test(session->variables.optimizer_switch &
222
OPTIMIZER_SWITCH_NO_SEMIJOIN);
223
213
if (subselect->substype() == Item_subselect::IN_SUBS)
224
214
in_subs= (Item_in_subselect*)subselect;
225
215
226
/*
227
Check if we're in subquery that is a candidate for flattening into a
228
semi-join (which is done done in flatten_subqueries()). The
229
requirements are:
230
1. Subquery predicate is an IN/=ANY subq predicate
231
2. Subquery is a single SELECT (not a UNION)
232
3. Subquery does not have GROUP BY or order_st BY
233
4. Subquery does not use aggregate functions or HAVING
234
5. Subquery predicate is at the AND-top-level of ON/WHERE clause
235
6. No execution method was already chosen (by a prepared statement).
236
237
(*). We are not in a subquery of a single table UPDATE/DELETE that
238
doesn't have a JOIN (TODO: We should handle this at some
239
point by switching to multi-table UPDATE/DELETE)
240
241
(**). We're not in a confluent table-less subquery, like
242
"SELECT 1".
243
*/
244
if (in_subs && // 1
245
!select_lex->master_unit()->first_select()->next_select() && // 2
246
!select_lex->group_list.elements && !order && // 3
247
!having && !select_lex->with_sum_func && // 4
248
session->session_marker && // 5
249
select_lex->outer_select()->join && // (*)
250
select_lex->master_unit()->first_select()->leaf_tables && // (**)
251
do_semijoin &&
252
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
253
{
254
{
255
if (!in_subs->left_expr->fixed &&
256
in_subs->left_expr->fix_fields(session, &in_subs->left_expr))
257
{
258
return(-1);
259
}
260
/*
261
Check that the right part of the subselect contains no more than one
262
column. E.g. in SELECT 1 IN (SELECT * ..) the right part is (SELECT * ...)
263
*/
264
if (subselect->substype() == Item_subselect::IN_SUBS &&
265
(select_lex->item_list.elements !=
266
((Item_in_subselect*)subselect)->left_expr->cols()))
267
{
268
my_error(ER_OPERAND_COLUMNS, MYF(0), ((Item_in_subselect*)subselect)->left_expr->cols());
269
return(-1);
270
}
271
}
272
273
/* Register the subquery for further processing */
274
select_lex->outer_select()->join->sj_subselects.append(session->mem_root, in_subs);
275
in_subs->expr_join_nest= (TableList*)session->session_marker;
276
}
277
else
278
216
{
279
217
bool do_materialize= !test(session->variables.optimizer_switch &
280
218
OPTIMIZER_SWITCH_NO_MATERIALIZATION);
507
445
#endif
508
446
509
447
/* Convert all outer joins to inner joins if possible */
510
conds= simplify_joins(this, join_list, conds, true, false);
448
conds= simplify_joins(this, join_list, conds, true);
511
449
build_bitmap_for_nested_joins(join_list, 0);
512
450
513
451
conds= optimize_cond(this, conds, join_list, &cond_value);
878
816
uint64_t select_opts_for_readinfo=
879
817
(select_options & (SELECT_DESCRIBE | SELECT_NO_JOIN_CACHE)) | (0);
880
818
881
sj_tmp_tables= NULL;
882
if (!select_lex->sj_nests.is_empty())
883
setup_semijoin_dups_elimination(this, select_opts_for_readinfo, no_jbuf_after);
884
885
819
// No cache for MATCH == 'Don't use join buffering when we use MATCH'.
886
820
if (make_join_readinfo(this, select_opts_for_readinfo, no_jbuf_after))
887
821
return(1);
1761
1695
return(error);
1762
1696
}
1763
1697
1764
/*
1765
Convert candidate subquery predicates to semi-joins
1766
1767
SYNOPSIS
1768
JOIN::flatten_subqueries()
1769
1770
DESCRIPTION
1771
Convert candidate subquery predicates to semi-joins.
1772
1773
RETURN
1774
false OK
1775
true Error
1776
*/
1777
bool JOIN::flatten_subqueries()
1778
{
1779
Item_in_subselect **in_subq;
1780
Item_in_subselect **in_subq_end;
1781
1782
if (sj_subselects.elements() == 0)
1783
return(false);
1784
1785
/* 1. Fix children subqueries */
1786
for (in_subq= sj_subselects.front(), in_subq_end= sj_subselects.back();
1787
in_subq != in_subq_end; in_subq++)
1788
{
1789
JOIN *child_join= (*in_subq)->unit->first_select()->join;
1790
child_join->outer_tables = child_join->tables;
1791
if (child_join->flatten_subqueries())
1792
return(true);
1793
(*in_subq)->sj_convert_priority=
1794
(*in_subq)->is_correlated * MAX_TABLES + child_join->outer_tables;
1795
}
1796
1797
bool outer_join_disable_semi_join= false;
1798
/*
1799
* Temporary measure: disable semi-joins when they are together with outer
1800
* joins.
1801
*
1802
* @see LP Bug #314911
1803
*/
1804
for (TableList *tbl= select_lex->leaf_tables; tbl; tbl=tbl->next_leaf)
1805
{
1806
TableList *embedding= tbl->embedding;
1807
if (tbl->on_expr || (tbl->embedding && !(embedding->sj_on_expr &&
1808
!embedding->embedding)))
1809
{
1810
in_subq= sj_subselects.front();
1811
outer_join_disable_semi_join= true;
1812
}
1813
}
1814
1815
if (! outer_join_disable_semi_join)
1816
{
1817
/*
1818
2. Pick which subqueries to convert:
1819
sort the subquery array
1820
- prefer correlated subqueries over uncorrelated;
1821
- prefer subqueries that have greater number of outer tables;
1822
*/
1823
sj_subselects.sort(subq_sj_candidate_cmp);
1824
// #tables-in-parent-query + #tables-in-subquery < MAX_TABLES
1825
/* Replace all subqueries to be flattened with Item_int(1) */
1826
for (in_subq= sj_subselects.front();
1827
in_subq != in_subq_end &&
1828
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
1829
in_subq++)
1830
{
1831
if (replace_where_subcondition(this, *in_subq, new Item_int(1), false))
1832
return(true);
1833
}
1834
1835
for (in_subq= sj_subselects.front();
1836
in_subq != in_subq_end &&
1837
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
1838
in_subq++)
1839
{
1840
if (convert_subq_to_sj(this, *in_subq))
1841
return(true);
1842
}
1843
}
1844
1845
/* 3. Finalize those we didn't convert */
1846
for (; in_subq!= in_subq_end; in_subq++)
1847
{
1848
JOIN *child_join= (*in_subq)->unit->first_select()->join;
1849
Item_subselect::trans_res res;
1850
(*in_subq)->changed= 0;
1851
(*in_subq)->fixed= 0;
1852
res= (*in_subq)->select_transformer(child_join);
1853
if (res == Item_subselect::RES_ERROR)
1854
return(true);
1855
1856
(*in_subq)->changed= 1;
1857
(*in_subq)->fixed= 1;
1858
1859
Item *substitute= (*in_subq)->substitution;
1860
bool do_fix_fields= !(*in_subq)->substitution->fixed;
1861
if (replace_where_subcondition(this, *in_subq, substitute, do_fix_fields))
1862
return(true);
1863
1864
//if ((*in_subq)->fix_fields(session, (*in_subq)->ref_ptr))
1865
// return(true);
1866
}
1867
sj_subselects.clear();
1868
return(false);
1869
}
1870
1871
1698
/**
1872
1699
Setup for execution all subqueries of a query, for which the optimizer
1873
1700
chose hash semi-join.
2049
1876
tab->table->file->ha_index_or_rnd_end();
2050
1877
}
2051
1878
}
2052
cleanup_sj_tmp_tables(this);//
2053
1879
}
2054
1880
/*
2055
1881
We are not using tables anymore
2663
2489
2664
2490
JoinTable *return_tab= join->return_tab;
2665
2491
join_tab->found_match= true;
2666
if (join_tab->check_weed_out_table)
2667
{
2668
int res= do_sj_dups_weedout(join->session, join_tab->check_weed_out_table);
2669
if (res == -1)
2670
return NESTED_LOOP_ERROR;
2671
if (res == 1)
2672
return NESTED_LOOP_OK;
2673
}
2674
else if (join_tab->do_firstmatch)
2675
{
2676
/*
2677
We should return to the join_tab->do_firstmatch after we have
2678
enumerated all the suffixes for current prefix row combination
2679
*/
2680
return_tab= join_tab->do_firstmatch;
2681
}
2682
2492
2683
2493
/*
2684
2494
It was not just a return to lower loop level when one
2838
2648
if (!select || !select->skip_record())
2839
2649
{
2840
2650
int res= 0;
2841
if (!join_tab->check_weed_out_table ||
2842
!(res= do_sj_dups_weedout(join->session, join_tab->check_weed_out_table)))
2651
2652
rc= (join_tab->next_select)(join,join_tab+1,0);
2653
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2843
2654
{
2844
rc= (join_tab->next_select)(join,join_tab+1,0);
2845
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2846
{
2847
reset_cache_write(&join_tab->cache);
2848
return rc;
2849
}
2655
reset_cache_write(&join_tab->cache);
2656
return rc;
2850
2657
}
2658
2851
2659
if (res == -1)
2852
2660
return NESTED_LOOP_ERROR;
2853
2661
}
3274
3082
(!idx|| !check_interleaving_with_nj(join->positions[idx-1].table, s)))
3275
3083
{
3276
3084
double records, best;
3277
advance_sj_state(rest_tables, s);
3278
3085
best_access_path(join, s, session, rest_tables, idx, record_count,
3279
3086
read_time);
3280
3087
records= join->positions[idx].records_read;
3303
3110
std::swap(join->best_ref[idx], *pos);
3304
3111
}
3305
3112
restore_prev_nj_state(s);
3306
restore_prev_sj_state(rest_tables, s);
3307
3113
if (join->select_options & SELECT_STRAIGHT_JOIN)
3308
3114
break; // Don't test all combinations
3309
3115
}
3525
3331
my_qsort(join->best_ref + join->const_tables,
3526
3332
join->tables - join->const_tables, sizeof(JoinTable*),
3527
3333
straight_join ? join_tab_cmp_straight : join_tab_cmp);
3528
join->cur_emb_sj_nests= 0;
3529
3334
if (straight_join)
3530
3335
{
3531
3336
optimize_straight_join(join, join_tables);
3603
3408
table_map best_ref_depends_map= 0;
3604
3409
double tmp;
3605
3410
ha_rows rec;
3606
uint32_t best_is_sj_inside_out= 0;
3607
3411
3608
3412
if (s->keyuse)
3609
3413
{ /* Use key if possible */
3611
3415
KeyUse *keyuse,*start_key=0;
3612
3416
double best_records= DBL_MAX;
3613
3417
uint32_t max_key_part=0;
3614
uint64_t bound_sj_equalities= 0;
3615
bool try_sj_inside_out= false;
3616
/*
3617
Discover the bound equalites. We need to do this, if
3618
1. The next table is an SJ-inner table, and
3619
2. It is the first table from that semijoin, and
3620
3. We're not within a semi-join range (i.e. all semi-joins either have
3621
all or none of their tables in join_table_map), except
3622
s->emb_sj_nest (which we've just entered).
3623
3. All correlation references from this sj-nest are bound
3624
*/
3625
if (s->emb_sj_nest && // (1)
3626
s->emb_sj_nest->sj_in_exprs < 64 &&
3627
((remaining_tables & s->emb_sj_nest->sj_inner_tables) == // (2)
3628
s->emb_sj_nest->sj_inner_tables) && // (2)
3629
join->cur_emb_sj_nests == s->emb_sj_nest->sj_inner_tables && // (3)
3630
!(remaining_tables & s->emb_sj_nest->nested_join->sj_corr_tables)) // (4)
3631
{
3632
/* This table is an InsideOut scan candidate */
3633
bound_sj_equalities= get_bound_sj_equalities(s->emb_sj_nest,
3634
remaining_tables);
3635
try_sj_inside_out= true;
3636
}
3637
3418
3638
3419
/* Test how we can use keys */
3639
3420
rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key
3650
3431
3651
3432
/* Calculate how many key segments of the current key we can use */
3652
3433
start_key= keyuse;
3653
uint64_t handled_sj_equalities=0;
3654
key_part_map sj_insideout_map= 0;
3655
3434
3656
3435
do /* For each keypart */
3657
3436
{
3691
3470
ref_or_null_part |= keyuse->keypart_map;
3692
3471
}
3693
3472
3694
if (try_sj_inside_out && keyuse->sj_pred_no != UINT_MAX)
3695
{
3696
if (!(remaining_tables & keyuse->used_tables))
3697
bound_sj_equalities |= 1UL << keyuse->sj_pred_no;
3698
else
3699
{
3700
handled_sj_equalities |= 1UL << keyuse->sj_pred_no;
3701
sj_insideout_map |= ((key_part_map)1) << keyuse->keypart;
3702
}
3703
}
3704
3705
3473
keyuse++;
3706
3474
} while (keyuse->table == table && keyuse->key == key &&
3707
3475
keyuse->keypart == keypart);
3711
3479
/*
3712
3480
Assume that that each key matches a proportional part of table.
3713
3481
*/
3714
if (!found_part && !handled_sj_equalities)
3482
if (!found_part)
3715
3483
continue; // Nothing usable found
3716
3484
3717
3485
if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
3718
3486
rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables
3719
3487
3720
bool sj_inside_out_scan= false;
3721
3488
{
3722
3489
found_constraint= 1;
3723
/*
3724
Check if InsideOut scan is applicable:
3725
1. All IN-equalities are either "bound" or "handled"
3726
2. Index keyparts are
3727
...
3728
*/
3729
if (try_sj_inside_out &&
3730
table->covering_keys.test(key) &&
3731
(handled_sj_equalities | bound_sj_equalities) == // (1)
3732
PREV_BITS(uint64_t, s->emb_sj_nest->sj_in_exprs)) // (1)
3733
{
3734
uint32_t n_fixed_parts= max_part_bit(found_part);
3735
if (n_fixed_parts != keyinfo->key_parts &&
3736
(PREV_BITS(uint, n_fixed_parts) | sj_insideout_map) ==
3737
PREV_BITS(uint, keyinfo->key_parts))
3738
{
3739
/*
3740
Not all parts are fixed. Produce bitmap of remaining bits and
3741
check if all of them are covered.
3742
*/
3743
sj_inside_out_scan= true;
3744
if (!n_fixed_parts)
3745
{
3746
/*
3747
It's a confluent ref scan.
3748
3749
That is, all found KeyUse elements refer to IN-equalities,
3750
and there is really no ref access because there is no
3751
t.keypart0 = {bound expression}
3752
3753
Calculate the cost of complete loose index scan.
3754
*/
3755
records= (double)s->table->file->stats.records;
3756
3757
/* The cost is entire index scan cost (divided by 2) */
3758
best_time= s->table->file->index_only_read_time(key, records);
3759
3760
/* Now figure how many different keys we will get */
3761
ulong rpc;
3762
if ((rpc= keyinfo->rec_per_key[keyinfo->key_parts-1]))
3763
records= records / rpc;
3764
start_key= NULL;
3765
}
3766
}
3767
}
3768
3490
3769
3491
/*
3770
3492
Check if we found full key
4017
3739
tmp= best_time; // Do nothing
4018
3740
}
4019
3741
4020
if (sj_inside_out_scan && !start_key)
4021
{
4022
tmp= tmp/2;
4023
if (records)
4024
records= records/2;
4025
}
4026
4027
3742
}
4028
3743
if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
4029
3744
{
4033
3748
best_key= start_key;
4034
3749
best_max_key_part= max_key_part;
4035
3750
best_ref_depends_map= found_ref;
4036
best_is_sj_inside_out= sj_inside_out_scan;
4037
3751
}
4038
3752
}
4039
3753
records= best_records;
4164
3878
best_key= 0;
4165
3879
/* range/index_merge/ALL/index access method are "independent", so: */
4166
3880
best_ref_depends_map= 0;
4167
best_is_sj_inside_out= false;
4168
3881
}
4169
3882
}
4170
3883
4174
3887
join->positions[idx].key= best_key;
4175
3888
join->positions[idx].table= s;
4176
3889
join->positions[idx].ref_depend_map= best_ref_depends_map;
4177
join->positions[idx].use_insideout_scan= best_is_sj_inside_out;
4178
3890
4179
3891
if (!best_key &&
4180
3892
idx == join->const_tables &&
4217
3929
for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
4218
3930
{
4219
3931
/* Find the best access method from 's' to the current partial plan */
4220
advance_sj_state(join_tables, s);
4221
3932
best_access_path(join, s, join->session, join_tables, idx,
4222
3933
record_count, read_time);
4223
3934
/* compute the cost of the new plan extended with 's' */
4521
4232
(!idx || !check_interleaving_with_nj(join->positions[idx-1].table, s)))
4522
4233
{
4523
4234
double current_record_count, current_read_time;
4524
advance_sj_state(remaining_tables, s);
4525
4235
4526
4236
/*
4527
4237
psergey-insideout-todo:
4542
4252
current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
4543
4253
{
4544
4254
restore_prev_nj_state(s);
4545
restore_prev_sj_state(remaining_tables, s);
4546
4255
continue;
4547
4256
}
4548
4257
4569
4278
else
4570
4279
{
4571
4280
restore_prev_nj_state(s);
4572
restore_prev_sj_state(remaining_tables, s);
4573
4281
continue;
4574
4282
}
4575
4283
}
4606
4314
}
4607
4315
}
4608
4316
restore_prev_nj_state(s);
4609
restore_prev_sj_state(remaining_tables, s);
4610
4317
}
4611
4318
}
4612
4319
return(false);
4719
4426
join_tab->read_first_record= join_init_read_record;
4720
4427
join_tab->join=join;
4721
4428
join_tab->ref.key_parts= 0;
4722
join_tab->flush_weedout_table= join_tab->check_weed_out_table= NULL;
4723
join_tab->do_firstmatch= NULL;
4724
4429
memset(&join_tab->read_record, 0, sizeof(join_tab->read_record));
4725
4430
tmp_table->status=0;
4726
4431
tmp_table->null_row=0;
5679
5384
- The new condition, if success
5680
5385
- 0, otherwise
5681
5386
*/
5682
static COND *simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top, bool in_sj)
5387
static COND *simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top)
5683
5388
{
5684
5389
TableList *table;
5685
5390
nested_join_st *nested_join;
5712
5417
the outer join is converted to an inner join and
5713
5418
the corresponding on expression is added to E.
5714
5419
*/
5715
expr= simplify_joins(join, &nested_join->join_list,
5716
expr, false, in_sj || table->sj_on_expr);
5420
expr= simplify_joins(join, &nested_join->join_list, expr, false);
5717
5421
5718
5422
if (!table->prep_on_expr || expr != table->on_expr)
5719
5423
{
5725
5429
}
5726
5430
nested_join->used_tables= (table_map) 0;
5727
5431
nested_join->not_null_tables=(table_map) 0;
5728
conds= simplify_joins(join, &nested_join->join_list, conds, top, in_sj || table->sj_on_expr);
5432
conds= simplify_joins(join, &nested_join->join_list, conds, top);
5729
5433
used_tables= nested_join->used_tables;
5730
5434
not_null_tables= nested_join->not_null_tables;
5731
5435
}
5823
5527
while ((table= li++))
5824
5528
{
5825
5529
nested_join= table->nested_join;
5826
if (table->sj_on_expr && !in_sj)
5827
{
5828
/*
5829
If this is a semi-join that is not contained within another semi-join,
5830
leave it intact (otherwise it is flattened)
5831
*/
5832
join->select_lex->sj_nests.push_back(table);
5833
}
5834
else if (nested_join && !table->on_expr)
5530
if (nested_join && !table->on_expr)
5835
5531
{
5836
5532
TableList *tbl;
5837
5533
List_iterator<TableList> it(nested_join->join_list);
6007
5703
s->embedding_map|= embedding->nested_join->nj_map;
6008
5704
continue;
6009
5705
}
6010
if (embedding && !(embedding->sj_on_expr && ! embedding->embedding))
5706
if (embedding && !(false && ! embedding->embedding))
6011
5707
{
6012
5708
/* s belongs to a nested join, maybe to several embedded joins */
6013
5709
s->embedding_map= 0;
6245
5941
}
6246
5942
}
6247
5943
6248
if (pull_out_semijoin_tables(join))
6249
return(true);
6250
6251
5944
/* Calc how many (possible) matched records in each table */
6252
5945
6253
5946
for (s=stat ; s < stat_end ; s++)
6526
6219
}
6527
6220
6528
6221
/**
6529
Setup the strategies to eliminate semi-join duplicates.
6530
6531
SYNOPSIS
6532
setup_semijoin_dups_elimination()
6533
join Join to process
6534
options Join options (needed to see if join buffering will be
6535
used or not)
6536
no_jbuf_after Another bit of information re where join buffering will
6537
be used.
6538
6539
DESCRIPTION
6540
Setup the strategies to eliminate semi-join duplicates. ATM there are 3
6541
strategies:
6542
6543
1. DuplicateWeedout (use of temptable to remove duplicates based on rowids
6544
of row combinations)
6545
2. FirstMatch (pick only the 1st matching row combination of inner tables)
6546
3. InsideOut (scanning the sj-inner table in a way that groups duplicates
6547
together and picking the 1st one)
6548
6549
The join order has "duplicate-generating ranges", and every range is
6550
served by one strategy or a combination of FirstMatch with with some
6551
other strategy.
6552
6553
"Duplicate-generating range" is defined as a range within the join order
6554
that contains all of the inner tables of a semi-join. All ranges must be
6555
disjoint, if tables of several semi-joins are interleaved, then the ranges
6556
are joined together, which is equivalent to converting
6557
SELECT ... WHERE oe1 IN (SELECT ie1 ...) AND oe2 IN (SELECT ie2 )
6558
to
6559
SELECT ... WHERE (oe1, oe2) IN (SELECT ie1, ie2 ... ...)
6560
.
6561
6562
Applicability conditions are as follows:
6563
6564
DuplicateWeedout strategy
6565
~~~~~~~~~~~~~~~~~~~~~~~~~
6566
6567
(ot|nt)* [ it ((it|ot|nt)* (it|ot))] (nt)*
6568
+------+ +=========================+ +---+
6569
(1) (2) (3)
6570
6571
(1) - Prefix of OuterTables (those that participate in
6572
IN-equality and/or are correlated with subquery) and outer
6573
Noncorrelated Tables.
6574
(2) - The handled range. The range starts with the first sj-inner
6575
table, and covers all sj-inner and outer tables
6576
Within the range, Inner, Outer, outer Noncorrelated tables
6577
may follow in any order.
6578
(3) - The suffix of outer Noncorrelated tables.
6579
6580
FirstMatch strategy
6581
~~~~~~~~~~~~~~~~~~~
6582
6583
(ot|nt)* [ it ((it|nt)* it) ] (nt)*
6584
+------+ +==================+ +---+
6585
(1) (2) (3)
6586
6587
(1) - Prefix of outer and non-correlated tables
6588
(2) - The handled range, which may contain only inner and
6589
non-correlated tables.
6590
(3) - The suffix of outer Noncorrelated tables.
6591
6592
InsideOut strategy
6593
~~~~~~~~~~~~~~~~~~
6594
6595
(ot|ct|nt) [ insideout_tbl (ot|nt|it)* it ] (ot|nt)*
6596
+--------+ +===========+ +=============+ +------+
6597
(1) (2) (3) (4)
6598
6599
(1) - Prefix that may contain any outer tables. The prefix must contain
6600
all the non-trivially correlated outer tables. (non-trivially means
6601
that the correlation is not just through the IN-equality).
6602
6603
(2) - Inner table for which the InsideOut scan is performed.
6604
6605
(3) - The remainder of the duplicate-generating range. It is served by
6606
application of FirstMatch strategy, with the exception that
6607
outer IN-correlated tables are considered to be non-correlated.
6608
6609
(4) - THe suffix of outer and outer non-correlated tables.
6610
6611
If several strategies are applicable, their relative priorities are:
6612
1. InsideOut
6613
2. FirstMatch
6614
3. DuplicateWeedout
6615
6616
This function walks over the join order and sets up the strategies by
6617
setting appropriate members in join_tab structures.
6618
6619
RETURN
6620
false OK
6621
true Out of memory error
6622
*/
6623
static int setup_semijoin_dups_elimination(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
6624
{
6625
table_map cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
6626
struct {
6627
/*
6628
0 - invalid (EOF marker),
6629
1 - InsideOut,
6630
2 - Temptable (maybe confluent),
6631
3 - Temptable with join buffering
6632
*/
6633
uint32_t strategy;
6634
uint32_t start_idx; /* Left range bound */
6635
uint32_t end_idx; /* Right range bound */
6636
/*
6637
For Temptable strategy: Bitmap of all outer and correlated tables from
6638
all involved join nests.
6639
*/
6640
table_map outer_tables;
6641
} dups_ranges [MAX_TABLES];
6642
6643
TableList *emb_insideout_nest= NULL;
6644
table_map emb_sj_map= 0; /* A bitmap of sj-nests (that is, their sj-inner
6645
tables) whose ranges we're in */
6646
table_map emb_outer_tables= 0; /* sj-outer tables for those sj-nests */
6647
table_map range_start_map= 0; /* table_map at current range start */
6648
bool dealing_with_jbuf= false; /* true <=> table within cur range uses join buf */
6649
int cur_range= 0;
6650
uint32_t i;
6651
6652
/*
6653
First pass: locate the duplicate-generating ranges and pick the strategies.
6654
*/
6655
for (i=join->const_tables ; i < join->tables ; i++)
6656
{
6657
JoinTable *tab=join->join_tab+i;
6658
Table *table=tab->table;
6659
cur_map |= table->map;
6660
6661
if (tab->emb_sj_nest) // Encountered an sj-inner table
6662
{
6663
if (!emb_sj_map)
6664
{
6665
dups_ranges[cur_range].start_idx= i;
6666
range_start_map= cur_map & ~table->map;
6667
/*
6668
Remember if this is a possible start of range that is covered by
6669
the InsideOut strategy (the reason that it is not covered could
6670
be that it overlaps with anther semi-join's range. we don't
6671
support InsideOut for joined ranges)
6672
*/
6673
if (join->best_positions[i].use_insideout_scan)
6674
emb_insideout_nest= tab->emb_sj_nest;
6675
}
6676
6677
emb_sj_map |= tab->emb_sj_nest->sj_inner_tables;
6678
emb_outer_tables |= tab->emb_sj_nest->nested_join->sj_depends_on;
6679
6680
if (tab->emb_sj_nest != emb_insideout_nest)
6681
{
6682
/*
6683
Two different semi-joins interleave. This cannot be handled by
6684
InsideOut strategy.
6685
*/
6686
emb_insideout_nest= NULL;
6687
}
6688
}
6689
6690
if (emb_sj_map) /* We're in duplicate-generating range */
6691
{
6692
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
6693
tab->type == JT_ALL && tab->use_quick != 2 && !tab->first_inner &&
6694
i <= no_jbuf_after && !dealing_with_jbuf)
6695
{
6696
/*
6697
This table uses join buffering, which makes use of FirstMatch or
6698
InsideOut strategies impossible for the current and (we assume)
6699
preceding duplicate-producing ranges.
6700
That is, for the join order:
6701
6702
x x [ x x] x [x x x] x [x x X* x] x
6703
| | | | | \
6704
+-----+ +-----+ | join buffering use
6705
r1 r2 we're here
6706
6707
we'll have to remove r1 and r2 and use duplicate-elimination
6708
strategy that spans all the tables, starting from the very 1st
6709
one.
6710
*/
6711
dealing_with_jbuf= true;
6712
emb_insideout_nest= false;
6713
6714
/*
6715
Absorb all preceding duplicate-eliminating ranges. Their strategies
6716
do not matter:
6717
*/
6718
for (int prev_range= 0; prev_range < cur_range; prev_range++)
6719
{
6720
dups_ranges[cur_range].outer_tables |=
6721
dups_ranges[prev_range].outer_tables;
6722
}
6723
dups_ranges[0].start_idx= 0; /* Will need to start from the 1st table */
6724
dups_ranges[0].outer_tables= dups_ranges[cur_range].outer_tables;
6725
cur_range= 0;
6726
}
6727
6728
/*
6729
Check if we are at the end of duplicate-producing range. We are if
6730
6731
1. It's an InsideOut range (which presumes all correlated tables are
6732
in the prefix), and all inner tables are in the join order prefix,
6733
or
6734
2. It's a DuplicateElimination range (possibly covering several
6735
SJ-nests), and all inner, outer, and correlated tables of all
6736
sj-nests are in the join order prefix.
6737
*/
6738
bool end_of_range= false;
6739
if (emb_insideout_nest &&
6740
bitmap_covers(cur_map, emb_insideout_nest->sj_inner_tables))
6741
{
6742
/* Save that this range is handled with InsideOut: */
6743
dups_ranges[cur_range].strategy= 1;
6744
end_of_range= true;
6745
}
6746
else if (bitmap_covers(cur_map, emb_outer_tables | emb_sj_map))
6747
{
6748
/*
6749
This is a complete range to be handled with either DuplicateWeedout
6750
or FirstMatch
6751
*/
6752
dups_ranges[cur_range].strategy= dealing_with_jbuf? 3 : 2;
6753
/*
6754
This will hold tables from within the range that need to be put
6755
into the join buffer before we can use the FirstMatch on its tail.
6756
*/
6757
dups_ranges[cur_range].outer_tables= emb_outer_tables &
6758
~range_start_map;
6759
end_of_range= true;
6760
}
6761
6762
if (end_of_range)
6763
{
6764
dups_ranges[cur_range].end_idx= i+1;
6765
emb_sj_map= emb_outer_tables= 0;
6766
emb_insideout_nest= NULL;
6767
dealing_with_jbuf= false;
6768
dups_ranges[++cur_range].strategy= 0;
6769
}
6770
}
6771
}
6772
6773
Session *session= join->session;
6774
SemiJoinTable **next_sjtbl_ptr= &join->sj_tmp_tables;
6775
/*
6776
Second pass: setup the chosen strategies
6777
*/
6778
for (int j= 0; j < cur_range; j++)
6779
{
6780
JoinTable *tab=join->join_tab + dups_ranges[j].start_idx;
6781
JoinTable *jump_to;
6782
if (dups_ranges[j].strategy == 1) // InsideOut strategy
6783
{
6784
tab->insideout_match_tab= join->join_tab + dups_ranges[j].end_idx - 1;
6785
jump_to= tab++;
6786
}
6787
else // DuplicateWeedout strategy
6788
{
6789
SemiJoinTable::TAB sjtabs[MAX_TABLES];
6790
table_map weed_cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
6791
uint32_t jt_rowid_offset= 0; // # tuple bytes are already occupied (w/o NULL bytes)
6792
uint32_t jt_null_bits= 0; // # null bits in tuple bytes
6793
SemiJoinTable::TAB *last_tab= sjtabs;
6794
uint32_t rowid_keep_flags= JoinTable::CALL_POSITION | JoinTable::KEEP_ROWID;
6795
JoinTable *last_outer_tab= tab - 1;
6796
/*
6797
Walk through the range and remember
6798
- tables that need their rowids to be put into temptable
6799
- the last outer table
6800
*/
6801
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
6802
{
6803
if (sj_table_is_included(join, tab))
6804
{
6805
last_tab->join_tab= tab;
6806
last_tab->rowid_offset= jt_rowid_offset;
6807
jt_rowid_offset += tab->table->file->ref_length;
6808
if (tab->table->maybe_null)
6809
{
6810
last_tab->null_byte= jt_null_bits / 8;
6811
last_tab->null_bit= jt_null_bits++;
6812
}
6813
last_tab++;
6814
tab->table->prepare_for_position();
6815
tab->rowid_keep_flags= rowid_keep_flags;
6816
}
6817
weed_cur_map |= tab->table->map;
6818
if (!tab->emb_sj_nest && bitmap_covers(weed_cur_map,
6819
dups_ranges[j].outer_tables))
6820
last_outer_tab= tab;
6821
}
6822
6823
if (jt_rowid_offset) /* Temptable has at least one rowid */
6824
{
6825
SemiJoinTable *sjtbl;
6826
uint32_t tabs_size= (last_tab - sjtabs) * sizeof(SemiJoinTable::TAB);
6827
if (!(sjtbl= (SemiJoinTable*)session->alloc(sizeof(SemiJoinTable))) ||
6828
!(sjtbl->tabs= (SemiJoinTable::TAB*) session->alloc(tabs_size)))
6829
return(true);
6830
memcpy(sjtbl->tabs, sjtabs, tabs_size);
6831
sjtbl->tabs_end= sjtbl->tabs + (last_tab - sjtabs);
6832
sjtbl->rowid_len= jt_rowid_offset;
6833
sjtbl->null_bits= jt_null_bits;
6834
sjtbl->null_bytes= (jt_null_bits + 7)/8;
6835
6836
*next_sjtbl_ptr= sjtbl;
6837
next_sjtbl_ptr= &(sjtbl->next);
6838
sjtbl->next= NULL;
6839
6840
sjtbl->tmp_table=
6841
sjtbl->createTable(session,
6842
sjtbl->rowid_len +
6843
sjtbl->null_bytes);
6844
6845
join->join_tab[dups_ranges[j].start_idx].flush_weedout_table= sjtbl;
6846
join->join_tab[dups_ranges[j].end_idx - 1].check_weed_out_table= sjtbl;
6847
}
6848
tab= last_outer_tab + 1;
6849
jump_to= last_outer_tab;
6850
}
6851
6852
/* Create the FirstMatch tail */
6853
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
6854
{
6855
if (tab->emb_sj_nest)
6856
tab->do_firstmatch= jump_to;
6857
else
6858
jump_to= tab;
6859
}
6860
}
6861
return(false);
6862
}
6863
6864
static void cleanup_sj_tmp_tables(JOIN *join)
6865
{
6866
for (SemiJoinTable *sj_tbl= join->sj_tmp_tables; sj_tbl;
6867
sj_tbl= sj_tbl->next)
6868
{
6869
if (sj_tbl->tmp_table)
6870
{
6871
sj_tbl->tmp_table->free_tmp_table(join->session);
6872
}
6873
}
6874
join->sj_tmp_tables= NULL;
6875
}
6876
6877
/**
6878
6222
Create a condition for a const reference and add this to the
6879
6223
currenct select for the table.
6880
6224
*/
6913
6257
return(error ? true : false);
6914
6258
}
6915
6259
6916
/**
6917
@brief Replaces an expression destructively inside the expression tree of
6918
the WHERE clase.
6919
6920
@note Because of current requirements for semijoin flattening, we do not
6921
need to recurse here, hence this function will only examine the top-level
6922
AND conditions. (see JOIN::prepare, comment above the line
6923
'if (do_materialize)'
6924
6925
@param join The top-level query.
6926
@param old_cond The expression to be replaced.
6927
@param new_cond The expression to be substituted.
6928
@param do_fix_fields If true, Item::fix_fields(Session*, Item**) is called for
6929
the new expression.
6930
@return <code>true</code> if there was an error, <code>false</code> if
6931
successful.
6932
*/
6933
static bool replace_where_subcondition(JOIN *join, Item *old_cond,
6934
Item *new_cond, bool do_fix_fields)
6935
{
6936
if (join->conds == old_cond) {
6937
join->conds= new_cond;
6938
if (do_fix_fields)
6939
new_cond->fix_fields(join->session, &join->conds);
6940
return false;
6941
}
6942
6943
if (join->conds->type() == Item::COND_ITEM) {
6944
List_iterator<Item> li(*((Item_cond*)join->conds)->argument_list());
6945
Item *item;
6946
while ((item= li++))
6947
if (item == old_cond)
6948
{
6949
li.replace(new_cond);
6950
if (do_fix_fields)
6951
new_cond->fix_fields(join->session, li.ref());
6952
return false;
6953
}
6954
}
6955
6956
return true;
6957
}
6958
6959
/*
6960
Pull tables out of semi-join nests, if possible
6961
6962
SYNOPSIS
6963
pull_out_semijoin_tables()
6964
join The join where to do the semi-join flattening
6965
6966
DESCRIPTION
6967
Try to pull tables out of semi-join nests.
6968
6969
PRECONDITIONS
6970
When this function is called, the join may have several semi-join nests
6971
(possibly within different semi-join nests), but it is guaranteed that
6972
one semi-join nest does not contain another.
6973
6974
ACTION
6975
A table can be pulled out of the semi-join nest if
6976
- It is a constant table
6977
- It is accessed
6978
6979
POSTCONDITIONS
6980
* Pulled out tables have JoinTable::emb_sj_nest == NULL (like the outer
6981
tables)
6982
* Tables that were not pulled out have JoinTable::emb_sj_nest.
6983
* Semi-join nests TableList::sj_inner_tables
6984
6985
This operation is (and should be) performed at each PS execution since
6986
tables may become/cease to be constant across PS reexecutions.
6987
6988
RETURN
6989
0 - OK
6990
1 - Out of memory error
6991
*/
6992
static int pull_out_semijoin_tables(JOIN *join)
6993
{
6994
TableList *sj_nest;
6995
List_iterator<TableList> sj_list_it(join->select_lex->sj_nests);
6996
6997
/* Try pulling out of the each of the semi-joins */
6998
while ((sj_nest= sj_list_it++))
6999
{
7000
/* Action #1: Mark the constant tables to be pulled out */
7001
table_map pulled_tables= 0;
7002
7003
List_iterator<TableList> child_li(sj_nest->nested_join->join_list);
7004
TableList *tbl;
7005
while ((tbl= child_li++))
7006
{
7007
if (tbl->table)
7008
{
7009
tbl->table->reginfo.join_tab->emb_sj_nest= sj_nest;
7010
if (tbl->table->map & join->const_table_map)
7011
{
7012
pulled_tables |= tbl->table->map;
7013
}
7014
}
7015
}
7016
7017
/*
7018
Action #2: Find which tables we can pull out based on
7019
update_ref_and_keys() data. Note that pulling one table out can allow
7020
us to pull out some other tables too.
7021
*/
7022
bool pulled_a_table;
7023
do
7024
{
7025
pulled_a_table= false;
7026
child_li.rewind();
7027
while ((tbl= child_li++))
7028
{
7029
if (tbl->table && !(pulled_tables & tbl->table->map))
7030
{
7031
if (find_eq_ref_candidate(tbl->table,
7032
sj_nest->nested_join->used_tables &
7033
~pulled_tables))
7034
{
7035
pulled_a_table= true;
7036
pulled_tables |= tbl->table->map;
7037
}
7038
}
7039
}
7040
} while (pulled_a_table);
7041
7042
child_li.rewind();
7043
if ((sj_nest)->nested_join->used_tables == pulled_tables)
7044
{
7045
(sj_nest)->sj_inner_tables= 0;
7046
while ((tbl= child_li++))
7047
{
7048
if (tbl->table)
7049
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
7050
}
7051
}
7052
else
7053
{
7054
/* Record the bitmap of inner tables, mark the inner tables */
7055
table_map inner_tables=(sj_nest)->nested_join->used_tables &
7056
~pulled_tables;
7057
(sj_nest)->sj_inner_tables= inner_tables;
7058
while ((tbl= child_li++))
7059
{
7060
if (tbl->table)
7061
{
7062
if (inner_tables & tbl->table->map)
7063
tbl->table->reginfo.join_tab->emb_sj_nest= (sj_nest);
7064
else
7065
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
7066
}
7067
}
7068
}
7069
}
7070
return(0);
7071
}
7072
7073
/*
7074
SemiJoinDuplicateElimination: Weed out duplicate row combinations
7075
7076
SYNPOSIS
7077
do_sj_dups_weedout()
7078
7079
RETURN
7080
-1 Error
7081
1 The row combination is a duplicate (discard it)
7082
0 The row combination is not a duplicate (continue)
7083
*/
7084
static int do_sj_dups_weedout(Session *session, SemiJoinTable *sjtbl)
7085
{
7086
int error;
7087
SemiJoinTable::TAB *tab= sjtbl->tabs;
7088
SemiJoinTable::TAB *tab_end= sjtbl->tabs_end;
7089
unsigned char *ptr= sjtbl->tmp_table->record[0] + 1;
7090
unsigned char *nulls_ptr= ptr;
7091
7092
/* Put the the rowids tuple into table->record[0]: */
7093
7094
// 1. Store the length
7095
if (((Field_varstring*)(sjtbl->tmp_table->field[0]))->length_bytes == 1)
7096
{
7097
*ptr= (unsigned char)(sjtbl->rowid_len + sjtbl->null_bytes);
7098
ptr++;
7099
}
7100
else
7101
{
7102
int2store(ptr, sjtbl->rowid_len + sjtbl->null_bytes);
7103
ptr += 2;
7104
}
7105
7106
// 2. Zero the null bytes
7107
if (sjtbl->null_bytes)
7108
{
7109
memset(ptr, 0, sjtbl->null_bytes);
7110
ptr += sjtbl->null_bytes;
7111
}
7112
7113
// 3. Put the rowids
7114
for (uint32_t i=0; tab != tab_end; tab++, i++)
7115
{
7116
handler *h= tab->join_tab->table->file;
7117
if (tab->join_tab->table->maybe_null && tab->join_tab->table->null_row)
7118
{
7119
/* It's a NULL-complemented row */
7120
*(nulls_ptr + tab->null_byte) |= tab->null_bit;
7121
memset(ptr + tab->rowid_offset, 0, h->ref_length);
7122
}
7123
else
7124
{
7125
/* Copy the rowid value */
7126
if (tab->join_tab->rowid_keep_flags & JoinTable::CALL_POSITION)
7127
h->position(tab->join_tab->table->record[0]);
7128
memcpy(ptr + tab->rowid_offset, h->ref, h->ref_length);
7129
}
7130
}
7131
7132
error= sjtbl->tmp_table->file->ha_write_row(sjtbl->tmp_table->record[0]);
7133
if (error)
7134
{
7135
/* create_myisam_from_heap will generate error if needed */
7136
if (sjtbl->tmp_table->file->is_fatal_error(error, HA_CHECK_DUP) &&
7137
create_myisam_from_heap(session, sjtbl->tmp_table, sjtbl->start_recinfo,
7138
&sjtbl->recinfo, error, 1))
7139
return -1;
7140
//return (error == HA_ERR_FOUND_DUPP_KEY || error== HA_ERR_FOUND_DUPP_UNIQUE) ? 1: -1;
7141
return 1;
7142
}
7143
return 0;
7144
}
7145
7146
6260
static void free_blobs(Field **ptr)
7147
6261
{
7148
6262
for (; *ptr ; ptr++)
7152
6266
}
7153
6267
}
7154
6268
7155
static bool bitmap_covers(const table_map x, const table_map y)
7156
{
7157
return !test(y & ~x);
7158
}
7159
7160
/*
7161
Check if the table's rowid is included in the temptable
7162
7163
SYNOPSIS
7164
sj_table_is_included()
7165
join The join
7166
join_tab The table to be checked
7167
7168
DESCRIPTION
7169
SemiJoinDuplicateElimination: check the table's rowid should be included
7170
in the temptable. This is so if
7171
7172
1. The table is not embedded within some semi-join nest
7173
2. The has been pulled out of a semi-join nest, or
7174
7175
3. The table is functionally dependent on some previous table
7176
7177
[4. This is also true for constant tables that can't be
7178
NULL-complemented but this function is not called for such tables]
7179
7180
RETURN
7181
true - Include table's rowid
7182
false - Don't
7183
*/
7184
static bool sj_table_is_included(JOIN *join, JoinTable *join_tab)
7185
{
7186
if (join_tab->emb_sj_nest)
7187
return false;
7188
7189
/* Check if this table is functionally dependent on the tables that
7190
are within the same outer join nest
7191
*/
7192
TableList *embedding= join_tab->table->pos_in_table_list->embedding;
7193
if (join_tab->type == JT_EQ_REF)
7194
{
7195
Table_map_iterator it(join_tab->ref.depend_map & ~PSEUDO_TABLE_BITS);
7196
uint32_t idx;
7197
while ((idx= it.next_bit())!=Table_map_iterator::BITMAP_END)
7198
{
7199
JoinTable *ref_tab= join->join_tab + idx;
7200
if (embedding == ref_tab->table->pos_in_table_list->embedding)
7201
return true;
7202
}
7203
/* Ok, functionally dependent */
7204
return false;
7205
}
7206
/* Not functionally dependent => need to include*/
7207
return true;
7208
}
7209
7210
6269
/**
7211
6270
@} (end of group Query_Optimizer)
7212
6271
*/
Loggerhead is a web-based interface for Breezy
Version: 2.0.1