← Back to branch summary

~ubuntu-branches/ubuntu/precise/mysql-5.1/precise

« back to all changes in this revision

Viewing changes to sql/sql_select.cc

  • Committer: Bazaar Package Importer
  • Author(s): Chuck Short
  • Date: 2010-06-21 15:31:05 UTC
  • mfrom: (1.1.3 upstream)
  • mto: This revision was merged to the branch mainline in revision 6.
  • Revision ID: james.westby@ubuntu.com-20100621153105-pbbz3t6nyrf9t2zq
Tags: upstream-5.1.48
Import upstream version 5.1.48

Show diffs side-by-side

added added

removed removed

Lines of Context:
sql/sql_select.cc
2709
2709
    /* 
2710
2710
       Build transitive closure for relation 'to be dependent on'.
2711
2711
       This will speed up the plan search for many cases with outer joins,
2712
 
       as well as allow us to catch illegal cross references/
 
2712
       as well as allow us to catch illegal cross references.
2713
2713
       Warshall's algorithm is used to build the transitive closure.
2714
 
       As we use bitmaps to represent the relation the complexity
2715
 
       of the algorithm is O((number of tables)^2). 
 
2714
       As we may restart the outer loop upto 'table_count' times, the
 
2715
       complexity of the algorithm is O((number of tables)^3).
 
2716
       However, most of the iterations will be shortcircuited when
 
2717
       there are no pedendencies to propogate.
2716
2718
    */
2717
 
    for (i= 0, s= stat ; i < table_count ; i++, s++)
 
2719
    for (i= 0 ; i < table_count ; i++)
2718
2720
    {
2719
 
      for (uint j= 0 ; j < table_count ; j++)
 
2721
      uint j;
 
2722
      table= stat[i].table;
 
2723
 
 
2724
      if (!table->reginfo.join_tab->dependent)
 
2725
        continue;
 
2726
 
 
2727
      /* Add my dependencies to other tables depending on me */
 
2728
      for (j= 0, s= stat ; j < table_count ; j++, s++)
2720
2729
      {
2721
 
        table= stat[j].table;
2722
2730
        if (s->dependent & table->map)
 
2731
        {
 
2732
          table_map was_dependent= s->dependent;
2723
2733
          s->dependent |= table->reginfo.join_tab->dependent;
 
2734
          /*
 
2735
            If we change dependencies for a table we already have
 
2736
            processed: Redo dependency propagation from this table.
 
2737
          */
 
2738
          if (i > j && s->dependent != was_dependent)
 
2739
          {
 
2740
            i = j-1;
 
2741
            break;
 
2742
          }
 
2743
        }
2724
2744
      }
2725
 
      if (outer_join & s->table->map)
2726
 
        s->table->maybe_null= 1;
2727
2745
    }
2728
 
    /* Catch illegal cross references for outer joins */
 
2746
 
2729
2747
    for (i= 0, s= stat ; i < table_count ; i++, s++)
2730
2748
    {
 
2749
      /* Catch illegal cross references for outer joins */
2731
2750
      if (s->dependent & s->table->map)
2732
2751
      {
2733
2752
        join->tables=0;                 // Don't use join->table
2734
2753
        my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
2735
2754
        goto error;
2736
2755
      }
 
2756
 
 
2757
      if (outer_join & s->table->map)
 
2758
        s->table->maybe_null= 1;
2737
2759
      s->key_dependent= s->dependent;
2738
2760
    }
2739
2761
  }
2967
2989
      s->quick=select->quick;
2968
2990
      s->needed_reg=select->needed_reg;
2969
2991
      select->quick=0;
2970
 
      if (records == 0 && s->table->reginfo.impossible_range &&
2971
 
          (s->table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT))
 
2992
      if (records == 0 && s->table->reginfo.impossible_range)
2972
2993
      {
2973
2994
        /*
2974
2995
          Impossible WHERE or ON expression
8705
8726
  NESTED_JOIN *nested_join;
8706
8727
  TABLE_LIST *prev_table= 0;
8707
8728
  List_iterator<TABLE_LIST> li(*join_list);
 
8729
  bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
8708
8730
  DBUG_ENTER("simplify_joins");
8709
8731
 
8710
8732
  /* 
8815
8837
    if (prev_table)
8816
8838
    {
8817
8839
      /* The order of tables is reverse: prev_table follows table */
8818
 
      if (prev_table->straight)
 
8840
      if (prev_table->straight || straight_join)
8819
8841
        prev_table->dep_tables|= used_tables;
8820
8842
      if (prev_table->on_expr)
8821
8843
      {
9091
9113
/**
9092
9114
  Nested joins perspective: Remove the last table from the join order.
9093
9115
 
 
9116
  The algorithm is the reciprocal of check_interleaving_with_nj(), hence
 
9117
  parent join nest nodes are updated only when the last table in its child
 
9118
  node is removed. The ASCII graphic below will clarify.
 
9119
 
 
9120
  %A table nesting such as <tt> t1 x [ ( t2 x t3 ) x ( t4 x t5 ) ] </tt>is
 
9121
  represented by the below join nest tree.
 
9122
 
 
9123
  @verbatim
 
9124
                     NJ1
 
9125
                  _/ /  \
 
9126
                _/  /    NJ2
 
9127
              _/   /     / \ 
 
9128
             /    /     /   \
 
9129
   t1 x [ (t2 x t3) x (t4 x t5) ]
 
9130
  @endverbatim
 
9131
 
 
9132
  At the point in time when check_interleaving_with_nj() adds the table t5 to
 
9133
  the query execution plan, QEP, it also directs the node named NJ2 to mark
 
9134
  the table as covered. NJ2 does so by incrementing its @c counter
 
9135
  member. Since all of NJ2's tables are now covered by the QEP, the algorithm
 
9136
  proceeds up the tree to NJ1, incrementing its counter as well. All join
 
9137
  nests are now completely covered by the QEP.
 
9138
 
 
9139
  restore_prev_nj_state() does the above in reverse. As seen above, the node
 
9140
  NJ1 contains the nodes t2, t3, and NJ2. Its counter being equal to 3 means
 
9141
  that the plan covers t2, t3, and NJ2, @e and that the sub-plan (t4 x t5)
 
9142
  completely covers NJ2. The removal of t5 from the partial plan will first
 
9143
  decrement NJ2's counter to 1. It will then detect that NJ2 went from being
 
9144
  completely to partially covered, and hence the algorithm must continue
 
9145
  upwards to NJ1 and decrement its counter to 2. %A subsequent removal of t4
 
9146
  will however not influence NJ1 since it did not un-cover the last table in
 
9147
  NJ2.
 
9148
 
 
9149
  SYNOPSIS
 
9150
    restore_prev_nj_state()
 
9151
      last  join table to remove, it is assumed to be the last in current 
 
9152
            partial join order.
 
9153
     
 
9154
  DESCRIPTION
 
9155
 
9094
9156
    Remove the last table from the partial join order and update the nested
9095
9157
    joins counters and join->cur_embedding_map. It is ok to call this 
9096
9158
    function for the first table in join order (for which 
9104
9166
{
9105
9167
  TABLE_LIST *last_emb= last->table->pos_in_table_list->embedding;
9106
9168
  JOIN *join= last->join;
9107
 
  while (last_emb)
 
9169
  for (;last_emb != NULL; last_emb= last_emb->embedding)
9108
9170
  {
9109
 
    if (!(--last_emb->nested_join->counter))
9110
 
      join->cur_embedding_map&= ~last_emb->nested_join->nj_map;
9111
 
    else if (last_emb->nested_join->join_list.elements-1 ==
9112
 
             last_emb->nested_join->counter) 
9113
 
    {
9114
 
      join->cur_embedding_map|= last_emb->nested_join->nj_map;
9115
 
      break;
9116
 
    }
9117
 
    else
9118
 
      break;
9119
 
    last_emb= last_emb->embedding;
 
9171
    NESTED_JOIN *nest= last_emb->nested_join;
 
9172
    DBUG_ASSERT(nest->counter > 0);
 
9173
    
 
9174
    bool was_fully_covered= nest->is_fully_covered();
 
9175
    
 
9176
    if (--nest->counter == 0)
 
9177
      join->cur_embedding_map&= ~nest->nj_map;
 
9178
    
 
9179
    if (!was_fully_covered)
 
9180
      break;
 
9181
    
 
9182
    join->cur_embedding_map|= nest->nj_map;
9120
9183
  }
9121
9184
}
9122
9185