480
Convert a subquery predicate into a TableList semi-join nest
484
parent_join Parent join, the one that has subq_pred in its WHERE/ON
486
subq_pred Subquery predicate to be converted
489
Convert a subquery predicate into a TableList semi-join nest. All the
490
prerequisites are already checked, so the conversion is always successfull.
492
Prepared Statements: the transformation is permanent:
493
- Changes in TableList structures are naturally permanent
494
- Item tree changes are performed on statement MEM_ROOT:
495
= we activate statement MEM_ROOT
496
= this function is called before the first fix_prepare_information
499
This is intended because the criteria for subquery-to-sj conversion remain
500
constant for the lifetime of the Prepared Statement.
504
true Out of memory error
506
bool convert_subq_to_sj(JOIN *parent_join, Item_in_subselect *subq_pred)
508
Select_Lex *parent_lex= parent_join->select_lex;
509
TableList *emb_tbl_nest= NULL;
510
List<TableList> *emb_join_list= &parent_lex->top_join_list;
511
Session *session= parent_join->session;
514
1. Find out where to put the predicate into.
515
Note: for "t1 LEFT JOIN t2" this will be t2, a leaf.
517
if ((void*)subq_pred->expr_join_nest != (void*)1)
519
if (subq_pred->expr_join_nest->nested_join)
524
... [LEFT] JOIN ( ... ) ON (subquery AND whatever) ...
526
The sj-nest will be inserted into the brackets nest.
528
emb_tbl_nest= subq_pred->expr_join_nest;
529
emb_join_list= &emb_tbl_nest->nested_join->join_list;
531
else if (!subq_pred->expr_join_nest->outer_join)
536
... INNER JOIN tblX ON (subquery AND whatever) ...
538
The sj-nest will be tblX's "sibling", i.e. another child of its
539
parent. This is ok because tblX is joined as an inner join.
541
emb_tbl_nest= subq_pred->expr_join_nest->embedding;
543
emb_join_list= &emb_tbl_nest->nested_join->join_list;
545
else if (!subq_pred->expr_join_nest->nested_join)
547
TableList *outer_tbl= subq_pred->expr_join_nest;
548
TableList *wrap_nest;
552
... LEFT JOIN tbl ON (on_expr AND subq_pred) ...
554
we'll need to convert it into:
556
... LEFT JOIN ( tbl SJ (subq_tables) ) ON (on_expr AND subq_pred) ...
558
|<----- wrap_nest ---->|
560
Q: other subqueries may be pointing to this element. What to do?
561
A1: simple solution: copy *subq_pred->expr_join_nest= *parent_nest.
562
But we'll need to fix other pointers.
563
A2: Another way: have TableList::next_ptr so the following
564
subqueries know the table has been nested.
565
A3: changes in the TableList::outer_join will make everything work
568
if (!(wrap_nest= alloc_join_nest(parent_join->session)))
572
wrap_nest->embedding= outer_tbl->embedding;
573
wrap_nest->join_list= outer_tbl->join_list;
574
wrap_nest->alias= (char*) "(sj-wrap)";
576
wrap_nest->nested_join->join_list.empty();
577
wrap_nest->nested_join->join_list.push_back(outer_tbl);
579
outer_tbl->embedding= wrap_nest;
580
outer_tbl->join_list= &wrap_nest->nested_join->join_list;
583
wrap_nest will take place of outer_tbl, so move the outer join flag
586
wrap_nest->outer_join= outer_tbl->outer_join;
587
outer_tbl->outer_join= 0;
589
wrap_nest->on_expr= outer_tbl->on_expr;
590
outer_tbl->on_expr= NULL;
592
List_iterator<TableList> li(*wrap_nest->join_list);
596
if (tbl == outer_tbl)
598
li.replace(wrap_nest);
603
Ok now wrap_nest 'contains' outer_tbl and we're ready to add the
604
semi-join nest into it
606
emb_join_list= &wrap_nest->nested_join->join_list;
607
emb_tbl_nest= wrap_nest;
612
nested_join_st *nested_join;
613
if (!(sj_nest= alloc_join_nest(parent_join->session)))
617
nested_join= sj_nest->nested_join;
619
sj_nest->join_list= emb_join_list;
620
sj_nest->embedding= emb_tbl_nest;
621
sj_nest->alias= (char*) "(sj-nest)";
622
/* Nests do not participate in those 'chains', so: */
623
/* sj_nest->next_leaf= sj_nest->next_local= sj_nest->next_global == NULL*/
624
emb_join_list->push_back(sj_nest);
627
nested_join->used_tables and nested_join->not_null_tables are
628
initialized in simplify_joins().
632
2. Walk through subquery's top list and set 'embedding' to point to the
635
Select_Lex *subq_lex= subq_pred->unit->first_select();
636
nested_join->join_list.empty();
637
List_iterator_fast<TableList> li(subq_lex->top_join_list);
638
TableList *tl, *last_leaf;
641
tl->embedding= sj_nest;
642
tl->join_list= &nested_join->join_list;
643
nested_join->join_list.push_back(tl);
647
Reconnect the next_leaf chain.
648
TODO: Do we have to put subquery's tables at the end of the chain?
649
Inserting them at the beginning would be a bit faster.
650
NOTE: We actually insert them at the front! That's because the order is
651
reversed in this list.
653
for (tl= parent_lex->leaf_tables; tl->next_leaf; tl= tl->next_leaf) {};
654
tl->next_leaf= subq_lex->leaf_tables;
658
Same as above for next_local chain
659
(a theory: a next_local chain always starts with ::leaf_tables
660
because view's tables are inserted after the view)
662
for (tl= parent_lex->leaf_tables; tl->next_local; tl= tl->next_local) {};
663
tl->next_local= subq_lex->leaf_tables;
665
/* A theory: no need to re-connect the next_global chain */
667
/* 3. Remove the original subquery predicate from the WHERE/ON */
669
// The subqueries were replaced for Item_int(1) earlier
670
subq_pred->exec_method= Item_in_subselect::SEMI_JOIN; // for subsequent executions
671
/*TODO: also reset the 'with_subselect' there. */
673
/* n. Adjust the parent_join->tables counter */
674
uint32_t table_no= parent_join->tables;
675
/* n. Walk through child's tables and adjust table->map */
676
for (tl= subq_lex->leaf_tables; tl; tl= tl->next_leaf, table_no++)
678
tl->table->tablenr= table_no;
679
tl->table->map= ((table_map)1) << table_no;
680
Select_Lex *old_sl= tl->select_lex;
681
tl->select_lex= parent_join->select_lex;
682
for(TableList *emb= tl->embedding; emb && emb->select_lex == old_sl; emb= emb->embedding)
683
emb->select_lex= parent_join->select_lex;
685
parent_join->tables += subq_lex->join->tables;
688
Put the subquery's WHERE into semi-join's sj_on_expr
689
Add the subquery-induced equalities too.
691
Select_Lex *save_lex= session->lex->current_select;
692
session->lex->current_select=subq_lex;
693
if (!subq_pred->left_expr->fixed &&
694
subq_pred->left_expr->fix_fields(session, &subq_pred->left_expr))
696
session->lex->current_select=save_lex;
698
sj_nest->nested_join->sj_corr_tables= subq_pred->used_tables();
699
sj_nest->nested_join->sj_depends_on= subq_pred->used_tables() |
700
subq_pred->left_expr->used_tables();
701
sj_nest->sj_on_expr= subq_lex->where;
704
Create the IN-equalities and inject them into semi-join's ON expression.
705
Additionally, for InsideOut strategy
706
- Record the number of IN-equalities.
707
- Create list of pointers to (oe1, ..., ieN). We'll need the list to
708
see which of the expressions are bound and which are not (for those
709
we'll produce a distinct stream of (ie_i1,...ie_ik).
711
(TODO: can we just create a list of pointers and hope the expressions
712
will not substitute themselves on fix_fields()? or we need to wrap
713
them into Item_direct_view_refs and store pointers to those. The
714
pointers to Item_direct_view_refs are guaranteed to be stable as
715
Item_direct_view_refs doesn't substitute itself with anything in
716
Item_direct_view_ref::fix_fields.
718
sj_nest->sj_in_exprs= subq_pred->left_expr->cols();
719
sj_nest->nested_join->sj_outer_expr_list.empty();
721
if (subq_pred->left_expr->cols() == 1)
723
nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr);
725
Item *item_eq= new Item_func_eq(subq_pred->left_expr,
726
subq_lex->ref_pointer_array[0]);
727
item_eq->name= (char*)subq_sj_cond_name;
728
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
732
for (uint32_t i= 0; i < subq_pred->left_expr->cols(); i++)
734
nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr->
737
new Item_func_eq(subq_pred->left_expr->element_index(i),
738
subq_lex->ref_pointer_array[i]);
739
item_eq->name= (char*)subq_sj_cond_name + (i % 64);
740
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
743
/* Fix the created equality and AND */
744
sj_nest->sj_on_expr->fix_fields(parent_join->session, &sj_nest->sj_on_expr);
747
Walk through sj nest's WHERE and ON expressions and call
748
item->fix_table_changes() for all items.
750
sj_nest->sj_on_expr->fix_after_pullout(parent_lex, &sj_nest->sj_on_expr);
751
fix_list_after_tbl_changes(parent_lex, &sj_nest->nested_join->join_list);
754
/* Unlink the child select_lex so it doesn't show up in EXPLAIN: */
755
subq_lex->master_unit()->exclude_level();
757
/* Inject sj_on_expr into the parent's WHERE or ON */
760
emb_tbl_nest->on_expr= and_items(emb_tbl_nest->on_expr,
761
sj_nest->sj_on_expr);
762
emb_tbl_nest->on_expr->fix_fields(parent_join->session, &emb_tbl_nest->on_expr);
766
/* Inject into the WHERE */
767
parent_join->conds= and_items(parent_join->conds, sj_nest->sj_on_expr);
768
parent_join->conds->fix_fields(parent_join->session, &parent_join->conds);
769
parent_join->select_lex->where= parent_join->conds;
776
Check if table's KeyUse elements have an eq_ref(outer_tables) candidate
779
find_eq_ref_candidate()
780
table Table to be checked
781
sj_inner_tables Bitmap of inner tables. eq_ref(inner_table) doesn't
785
Check if table's KeyUse elements have an eq_ref(outer_tables) candidate
788
Check again if it is feasible to factor common parts with constant table
792
true - There exists an eq_ref(outer-tables) candidate
795
bool find_eq_ref_candidate(Table *table, table_map sj_inner_tables)
797
KeyUse *keyuse= table->reginfo.join_tab->keyuse;
802
while (1) /* For each key */
805
KEY *keyinfo= table->key_info + key;
806
key_part_map bound_parts= 0;
807
if ((keyinfo->flags & HA_NOSAME) == HA_NOSAME)
809
do /* For all equalities on all key parts */
811
/* Check if this is "t.keypart = expr(outer_tables) */
812
if (!(keyuse->used_tables & sj_inner_tables) &&
813
!(keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL))
815
bound_parts |= 1 << keyuse->keypart;
818
} while (keyuse->key == key && keyuse->table == table);
820
if (bound_parts == PREV_BITS(uint, keyinfo->key_parts))
822
if (keyuse->table != table)
830
if (keyuse->table != table)
833
while (keyuse->key == key);
840
454
/*****************************************************************************
841
455
Create JoinTableS, make a guess about the table types,
842
456
Approximate how many records will be used in each table
added
removed
drizzled/sql_select.cc
