← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/join.cc

  • Committer: Prafulla Tekawade
  • Date: 2010-07-18 03:36:32 UTC
  • mto: (1662.1.4 rollup)
  • mto: This revision was merged to the branch mainline in revision 1664.
  • Revision ID: prafulla_t@users.sourceforge.net-20100718033632-p7q6qtgliqbhe38p
Fix for Bug 592444

There were two problems:
o. In greedy_search optimizer method, best_extension_by_limited search
   maintains join embedding(nestedness) of tables added so far, so that 
   correct(valid)  join order is selected
   These are requirements from nested outer join executioner.
   The problem was, embedding_map was not correctly updated when a table 
   is added to optimal plan outside best_extension_by_limited search, 
   by greedy_search method. We need to update join->cur_embedding_map
   correctly here so that execution plan for other tables get
   generated.
   Invoked checked_interleaving_with_nj from greedy_search on the
   best_table selected. Fixed its prototype to take only one JoinTab
   This is same as mysql 5.1 source tree.
o. The other problem was, join->cur_embedding_map was not restored correctly
   when a table is added to the optimal plan to reflect the current embedding 
   map. 
   Taken good documented method restore_prev_nj_state which restores 
   cur_embedding_map from mysql 5.1 source tree and modified it for drizzled 
   code.

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/join.cc
4040
4040
    */
4041
4041
    join->setPosInPartialPlan(idx, best_pos);
4042
4042
 
 
4043
    /*
 
4044
      We need to make best_extension_by_limited_search aware of the fact
 
4045
      that it's not starting from top level, but from a rather specific
 
4046
      position in the list of nested joins.
 
4047
    */
 
4048
    check_interleaving_with_nj (best_table);
 
4049
    
 
4050
      
 
4051
 
4043
4052
    /* find the position of 'best_table' in 'join->best_ref' */
4044
4053
    best_idx= idx;
4045
4054
    JoinTable *pos= join->best_ref[best_idx];
4201
4210
  for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
4202
4211
  {
4203
4212
    table_map real_table_bit= s->table->map;
4204
 
    if (idx)
4205
 
    {
4206
 
      partial_pos= join->getPosFromPartialPlan(idx - 1);
4207
 
    }
4208
4213
    if ((remaining_tables & real_table_bit) &&
4209
4214
        ! (remaining_tables & s->dependent) &&
4210
 
        (! idx || ! check_interleaving_with_nj(partial_pos.getJoinTable(), s)))
 
4215
        (! idx || ! check_interleaving_with_nj(s)))
4211
4216
    {
4212
4217
      double current_record_count, current_read_time;
4213
4218
 
6014
6019
/**
6015
6020
  Nested joins perspective: Remove the last table from the join order.
6016
6021
 
 
6022
  The algorithm is the reciprocal of check_interleaving_with_nj(), hence
 
6023
  parent join nest nodes are updated only when the last table in its child
 
6024
  node is removed. The ASCII graphic below will clarify.
 
6025
 
 
6026
  %A table nesting such as <tt> t1 x [ ( t2 x t3 ) x ( t4 x t5 ) ] </tt>is
 
6027
  represented by the below join nest tree.
 
6028
 
 
6029
  @verbatim
 
6030
                     NJ1
 
6031
                  _/ /  \
 
6032
                _/  /    NJ2
 
6033
              _/   /     / \ 
 
6034
             /    /     /   \
 
6035
   t1 x [ (t2 x t3) x (t4 x t5) ]
 
6036
  @endverbatim
 
6037
 
 
6038
  At the point in time when check_interleaving_with_nj() adds the table t5 to
 
6039
  the query execution plan, QEP, it also directs the node named NJ2 to mark
 
6040
  the table as covered. NJ2 does so by incrementing its @c counter
 
6041
  member. Since all of NJ2's tables are now covered by the QEP, the algorithm
 
6042
  proceeds up the tree to NJ1, incrementing its counter as well. All join
 
6043
  nests are now completely covered by the QEP.
 
6044
 
 
6045
  restore_prev_nj_state() does the above in reverse. As seen above, the node
 
6046
  NJ1 contains the nodes t2, t3, and NJ2. Its counter being equal to 3 means
 
6047
  that the plan covers t2, t3, and NJ2, @e and that the sub-plan (t4 x t5)
 
6048
  completely covers NJ2. The removal of t5 from the partial plan will first
 
6049
  decrement NJ2's counter to 1. It will then detect that NJ2 went from being
 
6050
  completely to partially covered, and hence the algorithm must continue
 
6051
  upwards to NJ1 and decrement its counter to 2. %A subsequent removal of t4
 
6052
  will however not influence NJ1 since it did not un-cover the last table in
 
6053
  NJ2.
 
6054
 
 
6055
  SYNOPSIS
 
6056
    restore_prev_nj_state()
 
6057
      last  join table to remove, it is assumed to be the last in current 
 
6058
            partial join order.
 
6059
     
 
6060
  DESCRIPTION
 
6061
 
6017
6062
    Remove the last table from the partial join order and update the nested
6018
 
    joins counters and join->cur_embedding_map. It is ok to call this
6019
 
    function for the first table in join order (for which
 
6063
    joins counters and join->cur_embedding_map. It is ok to call this 
 
6064
    function for the first table in join order (for which 
6020
6065
    check_interleaving_with_nj has not been called)
6021
6066
 
6022
6067
  @param last  join table to remove, it is assumed to be the last in current
6023
6068
               partial join order.
6024
6069
*/
 
6070
 
6025
6071
static void restore_prev_nj_state(JoinTable *last)
6026
6072
{
6027
6073
  TableList *last_emb= last->table->pos_in_table_list->getEmbedding();
6028
6074
  Join *join= last->join;
6029
 
  while (last_emb)
 
6075
  for (;last_emb != NULL; last_emb= last_emb->getEmbedding())
6030
6076
  {
6031
 
    if (last_emb->on_expr)
6032
 
    {
6033
 
      if (!(--last_emb->getNestedJoin()->counter_))
6034
 
        join->cur_embedding_map&= ~last_emb->getNestedJoin()->nj_map;
6035
 
      else if (last_emb->getNestedJoin()->join_list.elements-1 ==
6036
 
               last_emb->getNestedJoin()->counter_)
6037
 
        join->cur_embedding_map|= last_emb->getNestedJoin()->nj_map;
6038
 
      else
6039
 
        break;
6040
 
    }
6041
 
    last_emb= last_emb->getEmbedding();
 
6077
    nested_join_st *nest= last_emb->getNestedJoin();
 
6078
    
 
6079
    bool was_fully_covered= nest->is_fully_covered();
 
6080
    
 
6081
    if (--nest->counter_ == 0)
 
6082
      join->cur_embedding_map&= ~nest->nj_map;
 
6083
    
 
6084
    if (!was_fully_covered)
 
6085
      break;
 
6086
    
 
6087
    join->cur_embedding_map|= nest->nj_map;
6042
6088
  }
6043
6089
}
6044
6090
 
6045
 
 
6046
6091
/**
6047
6092
  Create a condition for a const reference and add this to the
6048
6093
  currenct select for the table.