~drizzle-trunk/drizzle/development : revision 352

40

struct st_sargable_param;

41

42

static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array);

43

static bool make_join_statistics(JOIN *join, TABLE_LIST *leaves, COND *conds,

43

static bool make_join_statistics(JOIN *join, TableList *leaves, COND *conds,

44

DYNAMIC_ARRAY *keyuse);

45

static bool update_ref_and_keys(THD *thd, DYNAMIC_ARRAY *keyuse,

46

JOIN_TAB *join_tab,

85

static void make_outerjoin_info(JOIN *join);

86

static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *item);

87

static bool make_join_readinfo(JOIN *join, uint64_t options, uint no_jbuf_after);

88

static bool only_eq_ref_tables(JOIN *join, ORDER *order, table_map tables);

88

static bool only_eq_ref_tables(JOIN *join, order_st *order, table_map tables);

89

static void update_depend_map(JOIN *join);

90

static void update_depend_map(JOIN *join, ORDER *order);

91

static ORDER *remove_const(JOIN *join,ORDER *first_order,COND *cond,

90

static void update_depend_map(JOIN *join, order_st *order);

91

static order_st *remove_const(JOIN *join,order_st *first_order,COND *cond,

92

bool change_list, bool *simple_order);

93

static int return_zero_rows(JOIN *join, select_result *res,TABLE_LIST *tables,

93

static int return_zero_rows(JOIN *join, select_result *res,TableList *tables,

94

List<Item> &fields, bool send_row,

95

uint64_t select_options, const char *info,

96

Item *having);

97

static COND *build_equal_items(THD *thd, COND *cond,

98

COND_EQUAL *inherited,

99

List<TABLE_LIST> *join_list,

99

List<TableList> *join_list,

100

COND_EQUAL **cond_equal_ref);

101

static COND* substitute_for_best_equal_field(COND *cond,

102

COND_EQUAL *cond_equal,

103

void *table_join_idx);

104

static COND *simplify_joins(JOIN *join, List<TABLE_LIST> *join_list,

104

static COND *simplify_joins(JOIN *join, List<TableList> *join_list,

105

COND *conds, bool top, bool in_sj);

106

static bool check_interleaving_with_nj(JOIN_TAB *last, JOIN_TAB *next);

107

static void restore_prev_nj_state(JOIN_TAB *last);

108

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

109

static uint build_bitmap_for_nested_joins(List<TABLE_LIST> *join_list,

108

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

109

static uint build_bitmap_for_nested_joins(List<TableList> *join_list,

110

uint first_unused);

111

112

static

115

const JOIN_TAB *tab);

116

117

static COND *optimize_cond(JOIN *join, COND *conds,

118

List<TABLE_LIST> *join_list,

118

List<TableList> *join_list,

119

Item::cond_result *cond_value);

120

static bool const_expression_in_where(COND *conds,Item *item, Item **comp_item);

121

static int do_select(JOIN *join,List<Item> *fields,Table *tmp_table);

160

table_map used_table,

161

bool exclude_expensive_cond);

162

static Item* part_of_refkey(Table *form,Field *field);

163

static bool test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,

163

static bool test_if_skip_sort_order(JOIN_TAB *tab,order_st *order,

164

ha_rows select_limit, bool no_changes,

165

const key_map *map);

166

static bool list_contains_unique_index(Table *table,

167

bool (*find_func) (Field *, void *), void *data);

168

static bool find_field_in_item_list (Field *field, void *data);

169

static bool find_field_in_order_list (Field *field, void *data);

170

static int create_sort_index(THD *thd, JOIN *join, ORDER *order,

170

static int create_sort_index(THD *thd, JOIN *join, order_st *order,

171

ha_rows filesort_limit, ha_rows select_limit,

172

bool is_order_by);

173

static int remove_duplicates(JOIN *join,Table *entry,List<Item> &fields,

185

static void reset_cache_write(JOIN_CACHE *cache);

186

static void read_cached_record(JOIN_TAB *tab);

187

static bool cmp_buffer_with_ref(JOIN_TAB *tab);

188

static ORDER *create_distinct_group(THD *thd, Item **ref_pointer_array,

189

ORDER *order, List<Item> &fields,

188

static order_st *create_distinct_group(THD *thd, Item **ref_pointer_array,

189

order_st *order, List<Item> &fields,

190

List<Item> &all_fields,

191

bool *all_order_by_fields_used);

192

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

193

static Table *get_sort_by_table(ORDER *a,ORDER *b,TABLE_LIST *tables);

194

static void calc_group_buffer(JOIN *join,ORDER *group);

192

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

193

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

194

static void calc_group_buffer(JOIN *join,order_st *group);

195

static bool make_group_fields(JOIN *main_join, JOIN *curr_join);

196

static bool alloc_group_fields(JOIN *join,ORDER *group);

196

static bool alloc_group_fields(JOIN *join,order_st *group);

197

// Create list for using with tempory table

198

static bool change_to_use_tmp_fields(THD *thd, Item **ref_pointer_array,

199

List<Item> &new_list1,

257

setup_tables_done_option changed for next rexecution

258

*/

259

res= mysql_select(thd, &select_lex->ref_pointer_array,

260

(TABLE_LIST*) select_lex->table_list.first,

260

(TableList*) select_lex->table_list.first,

261

select_lex->with_wild, select_lex->item_list,

262

select_lex->where,

263

select_lex->order_list.elements +

264

select_lex->group_list.elements,

265

(ORDER*) select_lex->order_list.first,

266

(ORDER*) select_lex->group_list.first,

265

(order_st*) select_lex->order_list.first,

266

(order_st*) select_lex->group_list.first,

267

select_lex->having,

268

(ORDER*) lex->proc_list.first,

268

(order_st*) lex->proc_list.first,

269

select_lex->options | thd->options |

270

setup_tables_done_option,

271

result, unit, select_lex);

394

Function to setup clauses without sum functions.

395

*/

396

inline int setup_without_group(THD *thd, Item **ref_pointer_array,

397

TABLE_LIST *tables,

398

TABLE_LIST *leaves,

397

TableList *tables,

398

TableList *leaves,

399

List<Item> &fields,

400

List<Item> &all_fields,

401

COND **conds,

402

ORDER *order,

403

ORDER *group, bool *hidden_group_fields)

402

order_st *order,

403

order_st *group, bool *hidden_group_fields)

404

{

405

int res;

406

nesting_map save_allow_sum_func=thd->lex->allow_sum_func ;

437

*/

438

int

439

JOIN::prepare(Item ***rref_pointer_array,

440

TABLE_LIST *tables_init,

440

TableList *tables_init,

441

uint wild_num, COND *conds_init, uint og_num,

442

ORDER *order_init, ORDER *group_init,

442

order_st *order_init, order_st *group_init,

443

Item *having_init,

444

ORDER *proc_param_init, SELECT_LEX *select_lex_arg,

444

order_st *proc_param_init, SELECT_LEX *select_lex_arg,

445

SELECT_LEX_UNIT *unit_arg)

446

{

447

// to prevent double initialization on EXPLAIN

475

false))

476

return(-1);

477

478

TABLE_LIST *table_ptr;

478

TableList *table_ptr;

479

for (table_ptr= select_lex->leaf_tables;

480

table_ptr;

481

table_ptr= table_ptr->next_leaf)

528

requirements are:

529

1. Subquery predicate is an IN/=ANY subq predicate

530

2. Subquery is a single SELECT (not a UNION)

531

3. Subquery does not have GROUP BY or ORDER BY

531

3. Subquery does not have GROUP BY or order_st BY

532

4. Subquery does not use aggregate functions or HAVING

533

5. Subquery predicate is at the AND-top-level of ON/WHERE clause

534

6. No execution method was already chosen (by a prepared statement).

571

572

/* Register the subquery for further processing */

573

select_lex->outer_select()->join->sj_subselects.append(thd->mem_root, in_subs);

574

in_subs->expr_join_nest= (TABLE_LIST*)thd->thd_marker;

574

in_subs->expr_join_nest= (TableList*)thd->thd_marker;

575

}

576

else

577

{

594

(Subquery is non-correlated ||

595

Subquery is correlated to any query outer to IN predicate ||

596

(Subquery is correlated to the immediate outer query &&

597

Subquery !contains {GROUP BY, ORDER BY [LIMIT],

597

Subquery !contains {GROUP BY, order_st BY [LIMIT],

598

aggregate functions) && subquery predicate is not under "NOT IN"))

599

6. No execution method was already chosen (by a prepared statement).

600

630

631

if (order)

632

{

633

ORDER *ord;

633

order_st *ord;

634

for (ord= order; ord; ord= ord->next)

635

{

636

Item *item= *ord->item;

673

{

674

/* Caclulate the number of groups */

675

send_group_parts= 0;

676

for (ORDER *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)

676

for (order_st *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)

677

send_group_parts++;

678

}

679

825

/* Check if this table is functionally dependent on the tables that

826

are within the same outer join nest

827

*/

828

TABLE_LIST *embedding= join_tab->table->pos_in_table_list->embedding;

828

TableList *embedding= join_tab->table->pos_in_table_list->embedding;

829

if (join_tab->type == JT_EQ_REF)

830

{

831

Table_map_iterator it(join_tab->ref.depend_map & ~PSEUDO_TABLE_BITS);

961

table_map outer_tables;

962

} dups_ranges [MAX_TABLES];

963

964

TABLE_LIST *emb_insideout_nest= NULL;

964

TableList *emb_insideout_nest= NULL;

965

table_map emb_sj_map= 0; /* A bitmap of sj-nests (that is, their sj-inner

966

tables) whose ranges we're in */

967

table_map emb_outer_tables= 0; /* sj-outer tables for those sj-nests */

1449

1450

/* Optimize distinct away if possible */

1451

{

1452

ORDER *org_order= order;

1452

order_st *org_order= order;

1453

order=remove_const(this, order,conds,1, &simple_order);

1454

if (thd->is_error())

1455

{

1458

}

1459

1460

/*

1461

If we are using ORDER BY NULL or ORDER BY const_expression,

1461

If we are using order_st BY NULL or order_st BY const_expression,

1462

return result in any order (even if we are using a GROUP BY)

1463

*/

1464

if (!order && org_order)

1492

We have found that grouping can be removed since groups correspond to

1493

only one row anyway, but we still have to guarantee correct result

1494

order. The line below effectively rewrites the query from GROUP BY

1495

<fields> to ORDER BY <fields>. There are two exceptions:

1495

<fields> to order_st BY <fields>. There are two exceptions:

1496

- if skip_sort_order is set (see above), then we can simply skip

1497

GROUP BY;

1498

- we can only rewrite ORDER BY if the ORDER BY fields are 'compatible'

1498

- we can only rewrite order_st BY if the order_st BY fields are 'compatible'

1499

with the GROUP BY ones, i.e. either one is a prefix of another.

1500

We only check if the ORDER BY is a prefix of GROUP BY. In this case

1500

We only check if the order_st BY is a prefix of GROUP BY. In this case

1501

test_if_subpart() copies the ASC/DESC attributes from the original

1502

ORDER BY fields.

1503

If GROUP BY is a prefix of ORDER BY, then it is safe to leave

1502

order_st BY fields.

1503

If GROUP BY is a prefix of order_st BY, then it is safe to leave

1504

'order' as is.

1505

*/

1506

if (!order || test_if_subpart(group_list, order))

1507

order= skip_sort_order ? 0 : group_list;

1508

/*

1509

If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be

1510

rewritten to IGNORE INDEX FOR ORDER BY(fields).

1510

rewritten to IGNORE INDEX FOR order_st BY(fields).

1511

*/

1512

join_tab->table->keys_in_use_for_order_by=

1513

join_tab->table->keys_in_use_for_group_by;

1532

/*

1533

We are only using one table. In this case we change DISTINCT to a

1534

GROUP BY query if:

1535

- The GROUP BY can be done through indexes (no sort) and the ORDER

1535

- The GROUP BY can be done through indexes (no sort) and the order_st

1536

BY only uses selected fields.

1537

(In this case we can later optimize away GROUP BY and ORDER BY)

1537

(In this case we can later optimize away GROUP BY and order_st BY)

1538

- We are scanning the whole table without LIMIT

1539

This can happen if:

1540

- We are using CALC_FOUND_ROWS

1541

- We are using an ORDER BY that can't be optimized away.

1541

- We are using an order_st BY that can't be optimized away.

1542

1543

We don't want to use this optimization when we are using LIMIT

1544

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

1570

{

1571

/*

1572

Force MySQL to read the table in sorted order to get result in

1573

ORDER BY order.

1573

order_st BY order.

1574

*/

1575

tmp_table_param.quick_group=0;

1576

}

1586

}

1587

simple_group= 0;

1588

{

1589

ORDER *old_group_list;

1589

order_st *old_group_list;

1590

group_list= remove_const(this, (old_group_list= group_list), conds,

1591

rollup.state == ROLLUP::STATE_NONE,

1592

&simple_group);

1627

This has to be done if all tables are not already read (const tables)

1628

and one of the following conditions holds:

1629

- We are using DISTINCT (simple distinct's are already optimized away)

1630

- We are using an ORDER BY or GROUP BY on fields not in the first table

1631

- We are using different ORDER BY and GROUP BY orders

1630

- We are using an order_st BY or GROUP BY on fields not in the first table

1631

- We are using different order_st BY and GROUP BY orders

1632

- The user wants us to buffer the result.

1633

*/

1634

need_tmp= (const_tables != tables &&

1760

Force using of tmp table if sorting by a SP or UDF function due to

1761

their expensive and probably non-deterministic nature.

1762

*/

1763

for (ORDER *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)

1763

for (order_st *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)

1764

{

1765

Item *item= *tmp_order->item;

1766

if (item->is_expensive())

1804

1805

tmp_table_param.hidden_field_count= (all_fields.elements -

1806

fields_list.elements);

1807

ORDER *tmp_group= ((!simple_group && !(test_flags & TEST_NO_KEY_GROUP)) ? group_list :

1808

(ORDER*) 0);

1807

order_st *tmp_group= ((!simple_group && !(test_flags & TEST_NO_KEY_GROUP)) ? group_list :

1808

(order_st*) 0);

1809

/*

1810

Pushing LIMIT to the temporary table creation is not applicable

1811

when there is ORDER BY or GROUP BY or there is no GROUP BY, but

1811

when there is order_st BY or GROUP BY or there is no GROUP BY, but

1812

there are aggregate functions, because in all these cases we need

1813

all result rows.

1814

*/

2091

if (select_options & SELECT_DESCRIBE)

2092

{

2093

/*

2094

Check if we managed to optimize ORDER BY away and don't use temporary

2095

table to resolve ORDER BY: in that case, we only may need to do

2094

Check if we managed to optimize order_st BY away and don't use temporary

2095

table to resolve order_st BY: in that case, we only may need to do

2096

filesort for GROUP BY.

2097

*/

2098

if (!order && !no_order && (!skip_sort_order || !need_tmp))

2253

exec_tmp_table2= create_tmp_table(thd,

2254

&curr_join->tmp_table_param,

2255

*curr_all_fields,

2256

(ORDER*) 0,

2256

(order_st*) 0,

2257

curr_join->select_distinct &&

2258

!curr_join->group_list,

2259

1, curr_join->select_options,

2464

return;

2465

}

2466

/*

2467

Here we sort rows for ORDER BY/GROUP BY clause, if the optimiser

2467

Here we sort rows for order_st BY/GROUP BY clause, if the optimiser

2468

chose FILESORT to be faster than INDEX SCAN or there is no

2469

suitable index present.

2470

Note, that create_sort_index calls test_if_skip_sort_order and may

2584

for a, b and c in this list.

2585

@param conds top level item of an expression representing

2586

WHERE clause of the top level select

2587

@param og_num total number of ORDER BY and GROUP BY clauses

2587

@param og_num total number of order_st BY and GROUP BY clauses

2588

arguments

2589

@param order linked list of ORDER BY agruments

2589

@param order linked list of order_st BY agruments

2590

@param group linked list of GROUP BY arguments

2591

@param having top level item of HAVING expression

2592

@param proc_param list of PROCEDUREs

2611

2612

bool

2613

mysql_select(THD *thd, Item ***rref_pointer_array,

2614

TABLE_LIST *tables, uint wild_num, List<Item> &fields,

2615

COND *conds, uint og_num, ORDER *order, ORDER *group,

2616

Item *having, ORDER *proc_param, uint64_t select_options,

2614

TableList *tables, uint wild_num, List<Item> &fields,

2615

COND *conds, uint og_num, order_st *order, order_st *group,

2616

Item *having, order_st *proc_param, uint64_t select_options,

2617

select_result *result, SELECT_LEX_UNIT *unit,

2618

SELECT_LEX *select_lex)

2619

{

2667

}

2668

}

2669

2670

/* dump_TABLE_LIST_graph(select_lex, select_lex->leaf_tables); */

2670

/* dump_TableList_graph(select_lex, select_lex->leaf_tables); */

2671

if (join->flatten_subqueries())

2672

{

2673

err= 1;

2674

goto err;

2675

}

2676

/* dump_TABLE_LIST_struct(select_lex, select_lex->leaf_tables); */

2676

/* dump_TableList_struct(select_lex, select_lex->leaf_tables); */

2677

2678

if ((err= join->optimize()))

2679

{

2722

}

2723

2724

2725

static TABLE_LIST *alloc_join_nest(THD *thd)

2725

static TableList *alloc_join_nest(THD *thd)

2726

{

2727

TABLE_LIST *tbl;

2728

if (!(tbl= (TABLE_LIST*) thd->calloc(ALIGN_SIZE(sizeof(TABLE_LIST))+

2729

sizeof(NESTED_JOIN))))

2727

TableList *tbl;

2728

if (!(tbl= (TableList*) thd->calloc(ALIGN_SIZE(sizeof(TableList))+

2729

sizeof(nested_join_st))))

2730

return NULL;

2731

tbl->nested_join= (NESTED_JOIN*) ((uchar*)tbl +

2732

ALIGN_SIZE(sizeof(TABLE_LIST)));

2731

tbl->nested_join= (nested_join_st*) ((uchar*)tbl +

2732

ALIGN_SIZE(sizeof(TableList)));

2733

return tbl;

2734

}

2735

2736

2737

void fix_list_after_tbl_changes(SELECT_LEX *new_parent, List<TABLE_LIST> *tlist)

2737

void fix_list_after_tbl_changes(SELECT_LEX *new_parent, List<TableList> *tlist)

2738

{

2739

List_iterator<TABLE_LIST> it(*tlist);

2740

TABLE_LIST *table;

2739

List_iterator<TableList> it(*tlist);

2740

TableList *table;

2741

while ((table= it++))

2742

{

2743

if (table->on_expr)

2749

2750

2751

/*

2752

Convert a subquery predicate into a TABLE_LIST semi-join nest

2752

Convert a subquery predicate into a TableList semi-join nest

2753

2754

SYNOPSIS

2755

convert_subq_to_sj()

2758

subq_pred Subquery predicate to be converted

2759

2760

DESCRIPTION

2761

Convert a subquery predicate into a TABLE_LIST semi-join nest. All the

2761

Convert a subquery predicate into a TableList semi-join nest. All the

2762

prerequisites are already checked, so the conversion is always successfull.

2763

2764

Prepared Statements: the transformation is permanent:

2765

- Changes in TABLE_LIST structures are naturally permanent

2765

- Changes in TableList structures are naturally permanent

2766

- Item tree changes are performed on statement MEM_ROOT:

2767

= we activate statement MEM_ROOT

2768

= this function is called before the first fix_prepare_information

2779

bool convert_subq_to_sj(JOIN *parent_join, Item_in_subselect *subq_pred)

2780

{

2781

SELECT_LEX *parent_lex= parent_join->select_lex;

2782

TABLE_LIST *emb_tbl_nest= NULL;

2783

List<TABLE_LIST> *emb_join_list= &parent_lex->top_join_list;

2782

TableList *emb_tbl_nest= NULL;

2783

List<TableList> *emb_join_list= &parent_lex->top_join_list;

2784

THD *thd= parent_join->thd;

2785

2786

/*

2817

}

2818

else if (!subq_pred->expr_join_nest->nested_join)

2819

{

2820

TABLE_LIST *outer_tbl= subq_pred->expr_join_nest;

2821

TABLE_LIST *wrap_nest;

2820

TableList *outer_tbl= subq_pred->expr_join_nest;

2821

TableList *wrap_nest;

2822

/*

2823

We're dealing with

2824

2833

Q: other subqueries may be pointing to this element. What to do?

2834

A1: simple solution: copy *subq_pred->expr_join_nest= *parent_nest.

2835

But we'll need to fix other pointers.

2836

A2: Another way: have TABLE_LIST::next_ptr so the following

2836

A2: Another way: have TableList::next_ptr so the following

2837

subqueries know the table has been nested.

2838

A3: changes in the TABLE_LIST::outer_join will make everything work

2838

A3: changes in the TableList::outer_join will make everything work

2839

automatically.

2840

*/

2841

if (!(wrap_nest= alloc_join_nest(parent_join->thd)))

2862

wrap_nest->on_expr= outer_tbl->on_expr;

2863

outer_tbl->on_expr= NULL;

2864

2865

List_iterator<TABLE_LIST> li(*wrap_nest->join_list);

2866

TABLE_LIST *tbl;

2865

List_iterator<TableList> li(*wrap_nest->join_list);

2866

TableList *tbl;

2867

while ((tbl= li++))

2868

{

2869

if (tbl == outer_tbl)

2881

}

2882

}

2883

2884

TABLE_LIST *sj_nest;

2885

NESTED_JOIN *nested_join;

2884

TableList *sj_nest;

2885

nested_join_st *nested_join;

2886

if (!(sj_nest= alloc_join_nest(parent_join->thd)))

2887

{

2888

return(true);

2907

*/

2908

st_select_lex *subq_lex= subq_pred->unit->first_select();

2909

nested_join->join_list.empty();

2910

List_iterator_fast<TABLE_LIST> li(subq_lex->top_join_list);

2911

TABLE_LIST *tl, *last_leaf;

2910

List_iterator_fast<TableList> li(subq_lex->top_join_list);

2911

TableList *tl, *last_leaf;

2912

while ((tl= li++))

2913

{

2914

tl->embedding= sj_nest;

2952

tl->table->map= ((table_map)1) << table_no;

2953

SELECT_LEX *old_sl= tl->select_lex;

2954

tl->select_lex= parent_join->select_lex;

2955

for(TABLE_LIST *emb= tl->embedding; emb && emb->select_lex == old_sl; emb= emb->embedding)

2955

for(TableList *emb= tl->embedding; emb && emb->select_lex == old_sl; emb= emb->embedding)

2956

emb->select_lex= parent_join->select_lex;

2957

}

2958

parent_join->tables += subq_lex->join->tables;

3080

(*in_subq)->is_correlated * MAX_TABLES + child_join->outer_tables;

3081

}

3082

3083

//dump_TABLE_LIST_struct(select_lex, select_lex->leaf_tables);

3083

//dump_TableList_struct(select_lex, select_lex->leaf_tables);

3084

/*

3085

2. Pick which subqueries to convert:

3086

sort the subquery array

3271

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

3272

tables)

3273

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

3274

* Semi-join nests TABLE_LIST::sj_inner_tables

3274

* Semi-join nests TableList::sj_inner_tables

3275

3276

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

3277

tables may become/cease to be constant across PS reexecutions.

3283

3284

int pull_out_semijoin_tables(JOIN *join)

3285

{

3286

TABLE_LIST *sj_nest;

3287

List_iterator<TABLE_LIST> sj_list_it(join->select_lex->sj_nests);

3286

TableList *sj_nest;

3287

List_iterator<TableList> sj_list_it(join->select_lex->sj_nests);

3288

3289

/* Try pulling out of the each of the semi-joins */

3290

while ((sj_nest= sj_list_it++))

3292

/* Action #1: Mark the constant tables to be pulled out */

3293

table_map pulled_tables= 0;

3294

3295

List_iterator<TABLE_LIST> child_li(sj_nest->nested_join->join_list);

3296

TABLE_LIST *tbl;

3295

List_iterator<TableList> child_li(sj_nest->nested_join->join_list);

3296

TableList *tbl;

3297

while ((tbl= child_li++))

3298

{

3299

if (tbl->table)

3415

*/

3416

3417

static bool

3418

make_join_statistics(JOIN *join, TABLE_LIST *tables, COND *conds,

3418

make_join_statistics(JOIN *join, TableList *tables, COND *conds,

3419

DYNAMIC_ARRAY *keyuse_array)

3420

{

3421

int error;

3447

tables;

3448

s++, tables= tables->next_leaf, i++)

3449

{

3450

TABLE_LIST *embedding= tables->embedding;

3450

TableList *embedding= tables->embedding;

3451

stat_vector[i]=s;

3452

s->keys.init();

3453

s->const_keys.init();

3498

s->embedding_map= 0;

3499

do

3500

{

3501

NESTED_JOIN *nested_join= embedding->nested_join;

3501

nested_join_st *nested_join= embedding->nested_join;

3502

s->embedding_map|=nested_join->nj_map;

3503

s->dependent|= embedding->dep_tables;

3504

embedding= embedding->embedding;

4515

Here we can add 'ref' access candidates for t1 and t2, but not for t3.

4516

*/

4517

4518

static void add_key_fields_for_nj(JOIN *join, TABLE_LIST *nested_join_table,

4518

static void add_key_fields_for_nj(JOIN *join, TableList *nested_join_table,

4519

KEY_FIELD **end, uint *and_level,

4520

SARGABLE_PARAM **sargables)

4521

{

4522

List_iterator<TABLE_LIST> li(nested_join_table->nested_join->join_list);

4523

List_iterator<TABLE_LIST> li2(nested_join_table->nested_join->join_list);

4522

List_iterator<TableList> li(nested_join_table->nested_join->join_list);

4523

List_iterator<TableList> li2(nested_join_table->nested_join->join_list);

4524

bool have_another = false;

4525

table_map tables= 0;

4526

TABLE_LIST *table;

4526

TableList *table;

4527

assert(nested_join_table->nested_join);

4528

4529

while ((table= li++) || (have_another && (li=li2, have_another=false,

4536

/* It's a semi-join nest. Walk into it as if it wasn't a nest */

4537

have_another= true;

4538

li2= li;

4539

li= List_iterator<TABLE_LIST>(table->nested_join->join_list);

4539

li= List_iterator<TableList>(table->nested_join->join_list);

4540

}

4541

else

4542

add_key_fields_for_nj(join, table, end, and_level, sargables);

4651

4652

/* Process ON conditions for the nested joins */

4653

{

4654

List_iterator<TABLE_LIST> li(*join_tab->join->join_list);

4655

TABLE_LIST *table;

4654

List_iterator<TableList> li(*join_tab->join->join_list);

4655

TableList *table;

4656

while ((table= li++))

4657

{

4658

if (table->nested_join)

4786

{

4787

List<Item_field> indexed_fields;

4788

List_iterator<Item_field> indexed_fields_it(indexed_fields);

4789

ORDER *cur_group;

4789

order_st *cur_group;

4790

Item_field *cur_item;

4791

key_map possible_keys(0);

4792

4869

Bitmap of bound IN-equalities.

4870

*/

4871

4872

uint64_t get_bound_sj_equalities(TABLE_LIST *sj_nest,

4872

uint64_t get_bound_sj_equalities(TableList *sj_nest,

4873

table_map remaining_tables)

4874

{

4875

List_iterator<Item> li(sj_nest->nested_join->sj_outer_expr_list);

6606

Table *table= field->table;

6607

THD *thd= table->in_use;

6608

ha_rows cuted_fields=thd->cuted_fields;

6609

my_bitmap_map *old_map= dbug_tmp_use_all_columns(table,

6610

table->write_set);

6611

6609

6612

6610

/*

6613

6611

we should restore old value of count_cuted_fields because

6618

6616

thd->count_cuted_fields= check_flag;

6619

6617

error= item->save_in_field(field, 1);

6620

6618

thd->count_cuted_fields= old_count_cuted_fields;

6621

dbug_tmp_restore_column_map(table->write_set, old_map);

6622

6619

return error || cuted_fields != thd->cuted_fields;

6623

6620

}

6624

6621

6884

6881

{

6885

6882

JOIN_TAB *tab=join->join_tab+i;

6886

6883

Table *table=tab->table;

6887

TABLE_LIST *tbl= table->pos_in_table_list;

6888

TABLE_LIST *embedding= tbl->embedding;

6884

TableList *tbl= table->pos_in_table_list;

6885

TableList *embedding= tbl->embedding;

6889

6886

6890

6887

if (tbl->outer_join)

6891

6888

{

6905

6902

/* Ignore sj-nests: */

6906

6903

if (!embedding->on_expr)

6907

6904

continue;

6908

NESTED_JOIN *nested_join= embedding->nested_join;

6905

nested_join_st *nested_join= embedding->nested_join;

6909

6906

if (!nested_join->counter_)

6910

6907

{

6911

6908

/*

7604

7601

7605

7602

7606

7603

/*

7607

Determine if the set is already ordered for ORDER BY, so it can

7604

Determine if the set is already ordered for order_st BY, so it can

7608

7605

disable join cache because it will change the ordering of the results.

7609

7606

Code handles sort table that is at any location (not only first after

7610

7607

the const tables) despite the fact that it's currently prohibited.

8092

8089

8093

8090

8094

8091

/**

8095

Remove the following expressions from ORDER BY and GROUP BY:

8092

Remove the following expressions from order_st BY and GROUP BY:

8096

8093

Constant expressions @n

8097

8094

Expression that only uses tables that are of type EQ_REF and the reference

8098

is in the ORDER list or if all refereed tables are of the above type.

8095

is in the order_st list or if all refereed tables are of the above type.

8099

8096

8100

8097

In the following, the X field can be removed:

8101

8098

@code

8102

SELECT * FROM t1,t2 WHERE t1.a=t2.a ORDER BY t1.a,t2.X

8103

SELECT * FROM t1,t2,t3 WHERE t1.a=t2.a AND t2.b=t3.b ORDER BY t1.a,t3.X

8099

SELECT * FROM t1,t2 WHERE t1.a=t2.a order_st BY t1.a,t2.X

8100

SELECT * FROM t1,t2,t3 WHERE t1.a=t2.a AND t2.b=t3.b order_st BY t1.a,t3.X

8104

8101

@endcode

8105

8102

8106

8103

These can't be optimized:

8107

8104

@code

8108

SELECT * FROM t1,t2 WHERE t1.a=t2.a ORDER BY t2.X,t1.a

8109

SELECT * FROM t1,t2 WHERE t1.a=t2.a AND t1.b=t2.b ORDER BY t1.a,t2.c

8110

SELECT * FROM t1,t2 WHERE t1.a=t2.a ORDER BY t2.b,t1.a

8105

SELECT * FROM t1,t2 WHERE t1.a=t2.a order_st BY t2.X,t1.a

8106

SELECT * FROM t1,t2 WHERE t1.a=t2.a AND t1.b=t2.b order_st BY t1.a,t2.c

8107

SELECT * FROM t1,t2 WHERE t1.a=t2.a order_st BY t2.b,t1.a

8111

8108

@endcode

8112

8109

*/

8113

8110

8114

8111

static bool

8115

eq_ref_table(JOIN *join, ORDER *start_order, JOIN_TAB *tab)

8112

eq_ref_table(JOIN *join, order_st *start_order, JOIN_TAB *tab)

8116

8113

{

8117

8114

if (tab->cached_eq_ref_table) // If cached

8118

8115

return tab->eq_ref_table;

8131

8128

{

8132

8129

if (! (*ref_item)->const_item())

8133

8130

{ // Not a const ref

8134

ORDER *order;

8131

order_st *order;

8135

8132

for (order=start_order ; order ; order=order->next)

8136

8133

{

8137

8134

if ((*ref_item)->eq(order->item[0],0))

8142

8139

found++;

8143

8140

assert(!(order->used & map));

8144

8141

order->used|=map;

8145

continue; // Used in ORDER BY

8142

continue; // Used in order_st BY

8146

8143

}

8147

8144

if (!only_eq_ref_tables(join,start_order, (*ref_item)->used_tables()))

8148

8145

return (tab->eq_ref_table=0);

8164

8161

8165

8162

8166

8163

static bool

8167

only_eq_ref_tables(JOIN *join,ORDER *order,table_map tables)

8164

only_eq_ref_tables(JOIN *join,order_st *order,table_map tables)

8168

8165

{

8169

8166

if (specialflag & SPECIAL_SAFE_MODE)

8170

8167

return 0; // skip this optimize /* purecov: inspected */

8206

8203

8207

8204

/** Update the dependency map for the sort order. */

8208

8205

8209

static void update_depend_map(JOIN *join, ORDER *order)

8206

static void update_depend_map(JOIN *join, order_st *order)

8210

8207

{

8211

8208

for (; order ; order=order->next)

8212

8209

{

8230

8227

8231

8228

8232

8229

/**

8233

Remove all constants and check if ORDER only contains simple

8230

Remove all constants and check if order_st only contains simple

8234

8231

expressions.

8235

8232

8236

8233

simple_order is set to 1 if sort_order only uses fields from head table

8248

8245

Returns new sort order

8249

8246

*/

8250

8247

8251

static ORDER *

8252

remove_const(JOIN *join,ORDER *first_order, COND *cond,

8248

static order_st *

8249

remove_const(JOIN *join,order_st *first_order, COND *cond,

8253

8250

bool change_list, bool *simple_order)

8254

8251

{

8255

8252

if (join->tables == join->const_tables)

8256

8253

return change_list ? 0 : first_order; // No need to sort

8257

8254

8258

ORDER *order,**prev_ptr;

8255

order_st *order,**prev_ptr;

8259

8256

table_map first_table= join->join_tab[join->const_tables].table->map;

8260

8257

table_map not_const_tables= ~join->const_table_map;

8261

8258

table_map ref;

8312

8309

8313

8310

8314

8311

static int

8315

return_zero_rows(JOIN *join, select_result *result,TABLE_LIST *tables,

8312

return_zero_rows(JOIN *join, select_result *result,TableList *tables,

8316

8313

List<Item> &fields, bool send_row, uint64_t select_options,

8317

8314

const char *info, Item *having)

8318

8315

{

8326

8323

8327

8324

if (send_row)

8328

8325

{

8329

for (TABLE_LIST *table= tables; table; table= table->next_leaf)

8326

for (TableList *table= tables; table; table= table->next_leaf)

8330

8327

mark_as_null_row(table->table); // All fields are NULL

8331

8328

if (having && having->val_int() == 0)

8332

8329

send_row=0;

9089

9086

9090

9087

static COND *build_equal_items(THD *thd, COND *cond,

9091

9088

COND_EQUAL *inherited,

9092

List<TABLE_LIST> *join_list,

9089

List<TableList> *join_list,

9093

9090

COND_EQUAL **cond_equal_ref)

9094

9091

{

9095

9092

COND_EQUAL *cond_equal= 0;

9117

9114

9118

9115

if (join_list)

9119

9116

{

9120

TABLE_LIST *table;

9121

List_iterator<TABLE_LIST> li(*join_list);

9117

TableList *table;

9118

List_iterator<TableList> li(*join_list);

9122

9119

9123

9120

while ((table= li++))

9124

9121

{

9125

9122

if (table->on_expr)

9126

9123

{

9127

List<TABLE_LIST> *nested_join_list= table->nested_join ?

9124

List<TableList> *nested_join_list= table->nested_join ?

9128

9125

&table->nested_join->join_list : NULL;

9129

9126

/*

9130

9127

We can modify table->on_expr because its old value will

9760

9757

*/

9761

9758

9762

9759

static COND *

9763

simplify_joins(JOIN *join, List<TABLE_LIST> *join_list, COND *conds, bool top,

9760

simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top,

9764

9761

bool in_sj)

9765

9762

{

9766

TABLE_LIST *table;

9767

NESTED_JOIN *nested_join;

9768

TABLE_LIST *prev_table= 0;

9769

List_iterator<TABLE_LIST> li(*join_list);

9763

TableList *table;

9764

nested_join_st *nested_join;

9765

TableList *prev_table= 0;

9766

List_iterator<TableList> li(*join_list);

9770

9767

9771

9768

/*

9772

9769

Try to simplify join operations from join_list.

9916

9913

}

9917

9914

else if (nested_join && !table->on_expr)

9918

9915

{

9919

TABLE_LIST *tbl;

9920

List_iterator<TABLE_LIST> it(nested_join->join_list);

9916

TableList *tbl;

9917

List_iterator<TableList> it(nested_join->join_list);

9921

9918

while ((tbl= it++))

9922

9919

{

9923

9920

tbl->embedding= table->embedding;

9950

9947

First unused bit in nested_join_map after the call.

9951

9948

*/

9952

9949

9953

static uint build_bitmap_for_nested_joins(List<TABLE_LIST> *join_list,

9950

static uint build_bitmap_for_nested_joins(List<TableList> *join_list,

9954

9951

uint first_unused)

9955

9952

{

9956

List_iterator<TABLE_LIST> li(*join_list);

9957

TABLE_LIST *table;

9953

List_iterator<TableList> li(*join_list);

9954

TableList *table;

9958

9955

while ((table= li++))

9959

9956

{

9960

NESTED_JOIN *nested_join;

9957

nested_join_st *nested_join;

9961

9958

if ((nested_join= table->nested_join))

9962

9959

{

9963

9960

/*

9986

9983

9987

9984

9988

9985

/**

9989

Set NESTED_JOIN::counter=0 in all nested joins in passed list.

9986

Set nested_join_st::counter=0 in all nested joins in passed list.

9990

9987

9991

Recursively set NESTED_JOIN::counter=0 for all nested joins contained in

9988

Recursively set nested_join_st::counter=0 for all nested joins contained in

9992

9989

the passed join_list.

9993

9990

9994

9991

@param join_list List of nested joins to process. It may also contain base

9995

9992

tables which will be ignored.

9996

9993

*/

9997

9994

9998

static void reset_nj_counters(List<TABLE_LIST> *join_list)

9995

static void reset_nj_counters(List<TableList> *join_list)

9999

9996

{

10000

List_iterator<TABLE_LIST> li(*join_list);

10001

TABLE_LIST *table;

9997

List_iterator<TableList> li(*join_list);

9998

TableList *table;

10002

9999

while ((table= li++))

10003

10000

{

10004

NESTED_JOIN *nested_join;

10001

nested_join_st *nested_join;

10005

10002

if ((nested_join= table->nested_join))

10006

10003

{

10007

10004

nested_join->counter_= 0;

10024

10021

10025

10022

@verbatim

10026

10023

IMPLEMENTATION

10027

LIMITATIONS ON JOIN ORDER

10024

LIMITATIONS ON JOIN order_st

10028

10025

The nested [outer] joins executioner algorithm imposes these limitations

10029

10026

on join order:

10030

10027

1. "Outer tables first" - any "outer" table must be before any

10088

10085

position:

10089

10086

1. join->cur_embedding_map - bitmap of pairs of brackets (aka nested

10090

10087

joins) we've opened but didn't close.

10091

2. {each NESTED_JOIN structure not simplified away}->counter - number

10088

2. {each nested_join_st structure not simplified away}->counter - number

10092

10089

of this nested join's children that have already been added to to

10093

10090

the partial join order.

10094

10091

@endverbatim

10107

10104

10108

10105

static bool check_interleaving_with_nj(JOIN_TAB *last_tab, JOIN_TAB *next_tab)

10109

10106

{

10110

TABLE_LIST *next_emb= next_tab->table->pos_in_table_list->embedding;

10107

TableList *next_emb= next_tab->table->pos_in_table_list->embedding;

10111

10108

JOIN *join= last_tab->join;

10112

10109

10113

10110

if (join->cur_embedding_map & ~next_tab->embedding_map)

10164

10161

10165

10162

static void restore_prev_nj_state(JOIN_TAB *last)

10166

10163

{

10167

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

10164

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

10168

10165

JOIN *join= last->join;

10169

10166

while (last_emb)

10170

10167

{

10187

10184

static

10188

10185

void advance_sj_state(const table_map remaining_tables, const JOIN_TAB *tab)

10189

10186

{

10190

TABLE_LIST *emb_sj_nest;

10187

TableList *emb_sj_nest;

10191

10188

if ((emb_sj_nest= tab->emb_sj_nest))

10192

10189

{

10193

10190

tab->join->cur_emb_sj_nests |= emb_sj_nest->sj_inner_tables;

10205

10202

static void restore_prev_sj_state(const table_map remaining_tables,

10206

10203

const JOIN_TAB *tab)

10207

10204

{

10208

TABLE_LIST *emb_sj_nest;

10205

TableList *emb_sj_nest;

10209

10206

if ((emb_sj_nest= tab->emb_sj_nest))

10210

10207

{

10211

10208

/* If we're removing the last SJ-inner table, remove the sj-nest */

10219

10216

10220

10217

10221

10218

static COND *

10222

optimize_cond(JOIN *join, COND *conds, List<TABLE_LIST> *join_list,

10219

optimize_cond(JOIN *join, COND *conds, List<TableList> *join_list,

10223

10220

Item::cond_result *cond_value)

10224

10221

{

10225

10222

THD *thd= join->thd;

11395

11392

JOIN *join= tab->join;

11396

11393

if (join->conds)

11397

11394

update_const_equal_items(join->conds, tab);

11398

TABLE_LIST *tbl;

11395

TableList *tbl;

11399

11396

for (tbl= join->select_lex->leaf_tables; tbl; tbl= tbl->next_leaf)

11400

11397

{

11401

TABLE_LIST *embedded;

11402

TABLE_LIST *embedding= tbl;

11398

TableList *embedded;

11399

TableList *embedding= tbl;

11403

11400

do

11404

11401

{

11405

11402

embedded= embedding;

11592

11589

11593

11590

11594

11591

/**

11595

This function is used when optimizing away ORDER BY in

11596

SELECT * FROM t1 WHERE a=1 ORDER BY a DESC,b DESC.

11592

This function is used when optimizing away order_st BY in

11593

SELECT * FROM t1 WHERE a=1 order_st BY a DESC,b DESC.

11597

11594

*/

11598

11595

11599

11596

static int

12087

12084

if (!table->uniques) // If not unique handling

12088

12085

{

12089

12086

/* Copy null values from group to row */

12090

ORDER *group;

12087

order_st *group;

12091

12088

for (group=table->group ; group ; group=group->next)

12092

12089

{

12093

12090

Item *item= *group->item;

12137

12134

bool end_of_records)

12138

12135

{

12139

12136

Table *table=join->tmp_table;

12140

ORDER *group;

12137

order_st *group;

12141

12138

int error;

12142

12139

12143

12140

if (end_of_records)

12595

12592

12596

12593

12597

12594

/**

12598

Test if one can use the key to resolve ORDER BY.

12595

Test if one can use the key to resolve order_st BY.

12599

12596

12600

12597

@param order Sort order

12601

12598

@param table Table to sort

12615

12612

-1 Reverse key can be used

12616

12613

*/

12617

12614

12618

static int test_if_order_by_key(ORDER *order, Table *table, uint idx,

12615

static int test_if_order_by_key(order_st *order, Table *table, uint idx,

12619

12616

uint *used_key_parts)

12620

12617

{

12621

12618

KEY_PART_INFO *key_part,*key_part_end;

12632

12629

12633

12630

/*

12634

12631

Skip key parts that are constants in the WHERE clause.

12635

These are already skipped in the ORDER BY by const_expression_in_where()

12632

These are already skipped in the order_st BY by const_expression_in_where()

12636

12633

*/

12637

12634

for (; const_key_parts & 1 ; const_key_parts>>= 1)

12638

12635

key_part++;

12746

12743

*/

12747

12744

12748

12745

static uint

12749

test_if_subkey(ORDER *order, Table *table, uint ref, uint ref_key_parts,

12746

test_if_subkey(order_st *order, Table *table, uint ref, uint ref_key_parts,

12750

12747

const key_map *usable_keys)

12751

12748

{

12752

12749

uint nr;

12836

12833

12837

12834

/**

12838

12835

Helper function for list_contains_unique_index.

12839

Find a field reference in a list of ORDER structures.

12836

Find a field reference in a list of order_st structures.

12840

12837

Finds a direct reference of the Field in the list.

12841

12838

12842

12839

@param field The field to search for.

12843

@param data ORDER *.The list to search in

12840

@param data order_st *.The list to search in

12844

12841

12845

12842

@retval

12846

12843

1 found

12851

12848

static bool

12852

12849

find_field_in_order_list (Field *field, void *data)

12853

12850

{

12854

ORDER *group= (ORDER *) data;

12851

order_st *group= (order_st *) data;

12855

12852

bool part_found= 0;

12856

for (ORDER *tmp_group= group; tmp_group; tmp_group=tmp_group->next)

12853

for (order_st *tmp_group= group; tmp_group; tmp_group=tmp_group->next)

12857

12854

{

12858

12855

Item *item= (*tmp_group->item)->real_item();

12859

12856

if (item->type() == Item::FIELD_ITEM &&

12903

12900

12904

12901

12905

12902

/**

12906

Test if we can skip the ORDER BY by using an index.

12903

Test if we can skip the order_st BY by using an index.

12907

12904

12908

12905

SYNOPSIS

12909

12906

test_if_skip_sort_order()

12929

12926

*/

12930

12927

12931

12928

static bool

12932

test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,ha_rows select_limit,

12929

test_if_skip_sort_order(JOIN_TAB *tab,order_st *order,ha_rows select_limit,

12933

12930

bool no_changes, const key_map *map)

12934

12931

{

12935

12932

int ref_key;

12947

12944

*/

12948

12945

usable_keys= *map;

12949

12946

12950

for (ORDER *tmp_order=order; tmp_order ; tmp_order=tmp_order->next)

12947

for (order_st *tmp_order=order; tmp_order ; tmp_order=tmp_order->next)

12951

12948

{

12952

12949

Item *item= (*tmp_order->item)->real_item();

12953

12950

if (item->type() != Item::FIELD_ITEM)

13065

13062

Check whether there is an index compatible with the given order

13066

13063

usage of which is cheaper than usage of the ref_key index (ref_key>=0)

13067

13064

or a table scan.

13068

It may be the case if ORDER/GROUP BY is used with LIMIT.

13065

It may be the case if order_st/GROUP BY is used with LIMIT.

13069

13066

*/

13070

13067

uint nr;

13071

13068

key_map keys;

13100

13097

/*

13101

13098

We are adding here also the index specified in FORCE INDEX clause,

13102

13099

if any.

13103

This is to allow users to use index in ORDER BY.

13100

This is to allow users to use index in order_st BY.

13104

13101

*/

13105

13102

if (table->force_index)

13106

13103

keys.merge(group ? table->keys_in_use_for_group_by :

13123

13120

bool is_covering= table->covering_keys.is_set(nr) || (nr == table->s->primary_key && table->file->primary_key_is_clustered());

13124

13121

13125

13122

/*

13126

Don't use an index scan with ORDER BY without limit.

13123

Don't use an index scan with order_st BY without limit.

13127

13124

For GROUP BY without limit always use index scan

13128

13125

if there is a suitable index.

13129

13126

Why we hold to this asymmetry hardly can be explained

13288

13285

}

13289

13286

13290

13287

check_reverse_order:

13291

if (order_direction == -1) // If ORDER BY ... DESC

13288

if (order_direction == -1) // If order_st BY ... DESC

13292

13289

{

13293

13290

if (select && select->quick)

13294

13291

{

13311

13308

return(0); // Use filesort

13312

13309

}

13313

13310

13314

/* ORDER BY range_key DESC */

13311

/* order_st BY range_key DESC */

13315

13312

tmp= new QUICK_SELECT_DESC((QUICK_RANGE_SELECT*)(select->quick),

13316

13313

used_key_parts, &error);

13317

13314

if (!tmp || error)

13328

13325

tab->ref.key >= 0 && tab->ref.key_parts <= used_key_parts)

13329

13326

{

13330

13327

/*

13331

SELECT * FROM t1 WHERE a=1 ORDER BY a DESC,b DESC

13328

SELECT * FROM t1 WHERE a=1 order_st BY a DESC,b DESC

13332

13329

13333

13330

Use a traversal function that starts by reading the last row

13334

13331

with key part (A) and then traverse the index backwards.

13354

13351

filesort_limit Max number of rows that needs to be sorted

13355

13352

select_limit Max number of rows in final output

13356

13353

Used to decide if we should use index or not

13357

is_order_by true if we are sorting on ORDER BY, false if GROUP BY

13354

is_order_by true if we are sorting on order_st BY, false if GROUP BY

13358

13355

Used to decide if we should use index or not

13359

13356

13360

13357

13373

13370

*/

13374

13371

13375

13372

static int

13376

create_sort_index(THD *thd, JOIN *join, ORDER *order,

13373

create_sort_index(THD *thd, JOIN *join, order_st *order,

13377

13374

ha_rows filesort_limit, ha_rows select_limit,

13378

13375

bool is_order_by)

13379

13376

{

13402

13399

is_order_by ? &table->keys_in_use_for_order_by :

13403

13400

&table->keys_in_use_for_group_by))

13404

13401

return(0);

13405

for (ORDER *ord= join->order; ord; ord= ord->next)

13402

for (order_st *ord= join->order; ord; ord= ord->next)

13406

13403

length++;

13407

13404

if (!(join->sortorder=

13408

13405

make_unireg_sortorder(order, &length, join->sortorder)))

13759

13756

}

13760

13757

13761

13758

13762

SORT_FIELD *make_unireg_sortorder(ORDER *order, uint *length,

13759

SORT_FIELD *make_unireg_sortorder(order_st *order, uint *length,

13763

13760

SORT_FIELD *sortorder)

13764

13761

{

13765

13762

uint count;

13766

13763

SORT_FIELD *sort,*pos;

13767

13764

13768

13765

count=0;

13769

for (ORDER *tmp = order; tmp; tmp=tmp->next)

13766

for (order_st *tmp = order; tmp; tmp=tmp->next)

13770

13767

count++;

13771

13768

if (!sortorder)

13772

13769

sortorder= (SORT_FIELD*) sql_alloc(sizeof(SORT_FIELD) *

14112

14109

14113

14110

14114

14111

bool

14115

cp_buffer_from_ref(THD *thd, Table *table, TABLE_REF *ref)

14112

cp_buffer_from_ref(THD *thd, Table *table __attribute__((unused)), TABLE_REF *ref)

14116

14113

{

14117

14114

enum enum_check_fields save_count_cuted_fields= thd->count_cuted_fields;

14118

14115

thd->count_cuted_fields= CHECK_FIELD_IGNORE;

14119

my_bitmap_map *old_map= dbug_tmp_use_all_columns(table, table->write_set);

14120

14116

bool result= 0;

14121

14117

14122

14118

for (store_key **copy=ref->key_copy ; *copy ; copy++)

14128

14124

}

14129

14125

}

14130

14126

thd->count_cuted_fields= save_count_cuted_fields;

14131

dbug_tmp_restore_column_map(table->write_set, old_map);

14132

14127

return result;

14133

14128

}

14134

14129

14138

14133

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

14139

14134

14140

14135

/**

14141

Resolve an ORDER BY or GROUP BY column reference.

14136

Resolve an order_st BY or GROUP BY column reference.

14142

14137

14143

Given a column reference (represented by 'order') from a GROUP BY or ORDER

14138

Given a column reference (represented by 'order') from a GROUP BY or order_st

14144

14139

BY clause, find the actual column it represents. If the column being

14145

14140

resolved is from the GROUP BY clause, the procedure searches the SELECT

14146

14141

list 'fields' and the columns in the FROM list 'tables'. If 'order' is from

14147

the ORDER BY clause, only the SELECT list is being searched.

14142

the order_st BY clause, only the SELECT list is being searched.

14148

14143

14149

14144

If 'order' is resolved to an Item, then order->item is set to the found

14150

14145

Item. If there is no item for the found column (that is, it was resolved

14162

14157

SELECT list)

14163

14158

@param[in,out] all_fields All select, group and order by fields

14164

14159

@param[in] is_group_field True if order is a GROUP field, false if

14165

ORDER by field

14160

order_st by field

14166

14161

14167

14162

@retval

14168

14163

false if OK

14171

14166

*/

14172

14167

14173

14168

static bool

14174

find_order_in_list(THD *thd, Item **ref_pointer_array, TABLE_LIST *tables,

14175

ORDER *order, List<Item> &fields, List<Item> &all_fields,

14169

find_order_in_list(THD *thd, Item **ref_pointer_array, TableList *tables,

14170

order_st *order, List<Item> &fields, List<Item> &all_fields,

14176

14171

bool is_group_field)

14177

14172

{

14178

Item *order_item= *order->item; /* The item from the GROUP/ORDER caluse. */

14173

Item *order_item= *order->item; /* The item from the GROUP/order_st caluse. */

14179

14174

Item::Type order_item_type;

14180

14175

Item **select_item; /* The corresponding item from the SELECT clause. */

14181

14176

Field *from_field; /* The corresponding field from the FROM clause. */

14201

14196

order->counter_used= 1;

14202

14197

return false;

14203

14198

}

14204

/* Lookup the current GROUP/ORDER field in the SELECT clause. */

14199

/* Lookup the current GROUP/order_st field in the SELECT clause. */

14205

14200

select_item= find_item_in_list(order_item, fields, &counter,

14206

14201

REPORT_EXCEPT_NOT_FOUND, &resolution);

14207

14202

if (!select_item)

14307

14302

the field list.

14308

14303

*/

14309

14304

14310

int setup_order(THD *thd, Item **ref_pointer_array, TABLE_LIST *tables,

14311

List<Item> &fields, List<Item> &all_fields, ORDER *order)

14305

int setup_order(THD *thd, Item **ref_pointer_array, TableList *tables,

14306

List<Item> &fields, List<Item> &all_fields, order_st *order)

14312

14307

{

14313

14308

thd->where="order clause";

14314

14309

for (; order; order=order->next)

14348

14343

*/

14349

14344

14350

14345

int

14351

setup_group(THD *thd, Item **ref_pointer_array, TABLE_LIST *tables,

14352

List<Item> &fields, List<Item> &all_fields, ORDER *order,

14346

setup_group(THD *thd, Item **ref_pointer_array, TableList *tables,

14347

List<Item> &fields, List<Item> &all_fields, order_st *order,

14353

14348

bool *hidden_group_fields)

14354

14349

{

14355

14350

*hidden_group_fields=0;

14356

ORDER *ord;

14351

order_st *ord;

14357

14352

14358

14353

if (!order)

14359

14354

return 0; /* Everything is ok */

14444

14439

optimize away 'order by'.

14445

14440

*/

14446

14441

14447

static ORDER *

14442

static order_st *

14448

14443

create_distinct_group(THD *thd, Item **ref_pointer_array,

14449

ORDER *order_list, List<Item> &fields,

14444

order_st *order_list, List<Item> &fields,

14450

14445

List<Item> &all_fields __attribute__((unused)),

14451

14446

bool *all_order_by_fields_used)

14452

14447

{

14453

14448

List_iterator<Item> li(fields);

14454

14449

Item *item;

14455

ORDER *order,*group,**prev;

14450

order_st *order,*group,**prev;

14456

14451

14457

14452

*all_order_by_fields_used= 1;

14458

14453

while ((item=li++))

14463

14458

{

14464

14459

if (order->in_field_list)

14465

14460

{

14466

ORDER *ord=(ORDER*) thd->memdup((char*) order,sizeof(ORDER));

14461

order_st *ord=(order_st*) thd->memdup((char*) order,sizeof(order_st));

14467

14462

if (!ord)

14468

14463

return 0;

14469

14464

*prev=ord;

14483

14478

Don't put duplicate columns from the SELECT list into the

14484

14479

GROUP BY list.

14485

14480

*/

14486

ORDER *ord_iter;

14481

order_st *ord_iter;

14487

14482

for (ord_iter= group; ord_iter; ord_iter= ord_iter->next)

14488

14483

if ((*ord_iter->item)->eq(item, 1))

14489

14484

goto next_item;

14490

14485

14491

ORDER *ord=(ORDER*) thd->calloc(sizeof(ORDER));

14486

order_st *ord=(order_st*) thd->calloc(sizeof(order_st));

14492

14487

if (!ord)

14493

14488

return 0;

14494

14489

14570

14565

*/

14571

14566

14572

14567

static bool

14573

test_if_subpart(ORDER *a,ORDER *b)

14568

test_if_subpart(order_st *a,order_st *b)

14574

14569

{

14575

14570

for (; a && b; a=a->next,b=b->next)

14576

14571

{

14588

14583

*/

14589

14584

14590

14585

static Table *

14591

get_sort_by_table(ORDER *a,ORDER *b,TABLE_LIST *tables)

14586

get_sort_by_table(order_st *a,order_st *b,TableList *tables)

14592

14587

{

14593

14588

table_map map= (table_map) 0;

14594

14589

14618

14613

*/

14619

14614

14620

14615

static void

14621

calc_group_buffer(JOIN *join,ORDER *group)

14616

calc_group_buffer(JOIN *join,order_st *group)

14622

14617

{

14623

14618

uint key_length=0, parts=0, null_parts=0;

14624

14619

14732

14727

*/

14733

14728

14734

14729

static bool

14735

alloc_group_fields(JOIN *join,ORDER *group)

14730

alloc_group_fields(JOIN *join,order_st *group)

14736

14731

{

14737

14732

if (group)

14738

14733

{

14901

14896

*/

14902

14897

if (!(pos=new Item_copy_string(pos)))

14903

14898

goto err;

14904

if (i < border) // HAVING, ORDER and GROUP BY

14899

if (i < border) // HAVING, order_st and GROUP BY

14905

14900

{

14906

14901

if (extra_funcs.push_back(pos))

14907

14902

goto err;

14919

14914

itr++;

14920

14915

itr.sublist(res_selected_fields, elements);

14921

14916

/*

14922

Put elements from HAVING, ORDER BY and GROUP BY last to ensure that any

14917

Put elements from HAVING, order_st BY and GROUP BY last to ensure that any

14923

14918

reference used in these will resolve to a item that is already calculated

14924

14919

*/

14925

14920

param->copy_funcs.concat(&extra_funcs);

14989

14984

{

14990

14985

group_parts+= fields_list.elements;

14991

14986

/*

14992

If the ORDER clause is specified then it's possible that

14987

If the order_st clause is specified then it's possible that

14993

14988

it also will be optimized, so reserve space for it too

14994

14989

*/

14995

14990

if (order)

14996

14991

{

14997

ORDER *ord;

14992

order_st *ord;

14998

14993

for (ord= order; ord; ord= ord->next)

14999

14994

group_parts++;

15000

14995

}

15385

15380

1 on error

15386

15381

*/

15387

15382

15388

static bool change_group_ref(THD *thd, Item_func *expr, ORDER *group_list,

15383

static bool change_group_ref(THD *thd, Item_func *expr, order_st *group_list,

15389

15384

bool *changed)

15390

15385

{

15391

15386

if (expr->arg_count)

15400

15395

Item *item= *arg;

15401

15396

if (item->type() == Item::FIELD_ITEM || item->type() == Item::REF_ITEM)

15402

15397

{

15403

ORDER *group_tmp;

15398

order_st *group_tmp;

15404

15399

for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)

15405

15400

{

15406

15401

if (item->eq(*group_tmp->item,0))

15478

15473

Item *item;

15479

15474

while ((item= it++))

15480

15475

{

15481

ORDER *group_tmp;

15476

order_st *group_tmp;

15482

15477

bool found_in_group= 0;

15483

15478

15484

15479

for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)

15507

15502

return 1;

15508

15503

new_item->fix_fields(thd, (Item **) 0);

15509

15504

thd->change_item_tree(it.ref(), new_item);

15510

for (ORDER *tmp= group_tmp; tmp; tmp= tmp->next)

15505

for (order_st *tmp= group_tmp; tmp; tmp= tmp->next)

15511

15506

{

15512

15507

if (*tmp->item == item)

15513

15508

thd->change_item_tree(tmp->item, new_item);

15585

15580

Item *item;

15586

15581

List_iterator<Item> new_it(rollup.fields[pos]);

15587

15582

Item **ref_array_start= rollup.ref_pointer_arrays[pos];

15588

ORDER *start_group;

15583

order_st *start_group;

15589

15584

15590

15585

/* Point to first hidden field */

15591

15586

Item **ref_array= ref_array_start + fields_arg.elements-1;

15629

15624

else

15630

15625

{

15631

15626

/* Check if this is something that is part of this group by */

15632

ORDER *group_tmp;

15627

order_st *group_tmp;

15633

15628

for (group_tmp= start_group, i= pos ;

15634

15629

group_tmp ; group_tmp= group_tmp->next, i++)

15635

15630

{

15889

15884

{

15890

15885

JOIN_TAB *tab=join->join_tab+i;

15891

15886

Table *table=tab->table;

15892

TABLE_LIST *table_list= tab->table->pos_in_table_list;

15887

TableList *table_list= tab->table->pos_in_table_list;

15893

15888

char buff[512];

15894

15889

char buff1[512], buff2[512], buff3[512];

15895

15890

char keylen_str_buf[64];

15933

15928

}

15934

15929

else

15935

15930

{

15936

TABLE_LIST *real_table= table->pos_in_table_list;

15931

TableList *real_table= table->pos_in_table_list;

15937

15932

item_list.push_back(new Item_string(real_table->alias,

15938

15933

strlen(real_table->alias),

15939

15934

cs));

16302

16297

thd->lex->current_select= first;

16303

16298

unit->set_limit(unit->global_parameters);

16304

16299

res= mysql_select(thd, &first->ref_pointer_array,

16305

(TABLE_LIST*) first->table_list.first,

16300

(TableList*) first->table_list.first,

16306

16301

first->with_wild, first->item_list,

16307

16302

first->where,

16308

16303

first->order_list.elements +

16309

16304

first->group_list.elements,

16310

(ORDER*) first->order_list.first,

16311

(ORDER*) first->group_list.first,

16305

(order_st*) first->order_list.first,

16306

(order_st*) first->group_list.first,

16312

16307

first->having,

16313

(ORDER*) thd->lex->proc_list.first,

16308

(order_st*) thd->lex->proc_list.first,

16314

16309

first->options | thd->options | SELECT_DESCRIBE,

16315

16310

result, unit, first);

16316

16311

}

16318

16313

}

16319

16314

16320

16315

16321

static void print_table_array(THD *thd, String *str, TABLE_LIST **table,

16322

TABLE_LIST **end)

16316

static void print_table_array(THD *thd, String *str, TableList **table,

16317

TableList **end)

16323

16318

{

16324

16319

(*table)->print(thd, str, QT_ORDINARY);

16325

16320

16326

for (TABLE_LIST **tbl= table + 1; tbl < end; tbl++)

16321

for (TableList **tbl= table + 1; tbl < end; tbl++)

16327

16322

{

16328

TABLE_LIST *curr= *tbl;

16323

TableList *curr= *tbl;

16329

16324

if (curr->outer_join)

16330

16325

{

16331

16326

/* MySQL converts right to left joins */

16358

16353

16359

16354

static void print_join(THD *thd,

16360

16355

String *str,

16361

List<TABLE_LIST> *tables,

16356

List<TableList> *tables,

16362

16357

enum_query_type query_type __attribute__((unused)))

16363

16358

{

16364

16359

/* List is reversed => we should reverse it before using */

16365

List_iterator_fast<TABLE_LIST> ti(*tables);

16366

TABLE_LIST **table= (TABLE_LIST **)thd->alloc(sizeof(TABLE_LIST*) *

16360

List_iterator_fast<TableList> ti(*tables);

16361

TableList **table= (TableList **)thd->alloc(sizeof(TableList*) *

16367

16362

tables->elements);

16368

16363

if (table == 0)

16369

16364

return; // out of memory

16370

16365

16371

for (TABLE_LIST **t= table + (tables->elements - 1); t >= table; t--)

16366

for (TableList **t= table + (tables->elements - 1); t >= table; t--)

16372

16367

*t= ti++;

16373

16368

16374

16369

/*

16377

16372

*/

16378

16373

if ((*table)->sj_inner_tables)

16379

16374

{

16380

TABLE_LIST **end= table + tables->elements;

16381

for (TABLE_LIST **t2= table; t2!=end; t2++)

16375

TableList **end= table + tables->elements;

16376

for (TableList **t2= table; t2!=end; t2++)

16382

16377

{

16383

16378

if (!(*t2)->sj_inner_tables)

16384

16379

{

16385

TABLE_LIST *tmp= *t2;

16380

TableList *tmp= *t2;

16386

16381

*t2= *table;

16387

16382

*table= tmp;

16388

16383

break;

16437

16432

@param str string where table should be printed

16438

16433

*/

16439

16434

16440

void TABLE_LIST::print(THD *thd, String *str, enum_query_type query_type)

16435

void TableList::print(THD *thd, String *str, enum_query_type query_type)

16441

16436

{

16442

16437

if (nested_join)

16443

16438

{

16583

16578

if (group_list.elements)

16584

16579

{

16585

16580

str->append(STRING_WITH_LEN(" group by "));

16586

print_order(str, (ORDER *) group_list.first, query_type);

16581

print_order(str, (order_st *) group_list.first, query_type);

16587

16582

switch (olap)

16588

16583

{

16589

16584

case CUBE_TYPE:

16614

16609

if (order_list.elements)

16615

16610

{

16616

16611

str->append(STRING_WITH_LEN(" order by "));

16617

print_order(str, (ORDER *) order_list.first, query_type);

16612

print_order(str, (order_st *) order_list.first, query_type);

16618

16613

}

16619

16614

16620

16615

// limit