/ Check-in [7393c81b]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Query optimizer enhancement: In "FROM a,b,c left join d" allow the C table to be reordered with A and B. This used to be the case but the capability was removed by (3203) and (3052) in response to ticket #1652. This change restores the capability. (CVS 3529)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 7393c81b8cb9d4344ae744de9eabcb3af64f1db8
User & Date: drh 2006-12-16 16:25:15
Context
2006-12-18
14:12
Updates to the "Distinctive Features" document. (CVS 3530) check-in: c734585e user: drh tags: trunk
2006-12-16
16:25
Query optimizer enhancement: In "FROM a,b,c left join d" allow the C table to be reordered with A and B. This used to be the case but the capability was removed by (3203) and (3052) in response to ticket #1652. This change restores the capability. (CVS 3529) check-in: 7393c81b user: drh tags: trunk
2006-12-14
01:06
Fix a bug in lemon that leads to an assertion fault given an invalid grammar. The bug and this fix do not effect on SQLite. Ticket #2107. (CVS 3528) check-in: f2ad230f user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/build.c.

    18     18   **     CREATE INDEX
    19     19   **     DROP INDEX
    20     20   **     creating ID lists
    21     21   **     BEGIN TRANSACTION
    22     22   **     COMMIT
    23     23   **     ROLLBACK
    24     24   **
    25         -** $Id: build.c,v 1.411 2006/09/11 23:45:49 drh Exp $
           25  +** $Id: build.c,v 1.412 2006/12/16 16:25:15 drh Exp $
    26     26   */
    27     27   #include "sqliteInt.h"
    28     28   #include <ctype.h>
    29     29   
    30     30   /*
    31     31   ** This routine is called when a new SQL statement is beginning to
    32     32   ** be parsed.  Initialize the pParse structure as needed.
................................................................................
  2936   2936         if( pItem->pSelect ){
  2937   2937           sqlite3SrcListAssignCursors(pParse, pItem->pSelect->pSrc);
  2938   2938         }
  2939   2939       }
  2940   2940     }
  2941   2941   }
  2942   2942   
  2943         -/*
  2944         -** Add an alias to the last identifier on the given identifier list.
  2945         -*/
  2946         -void sqlite3SrcListAddAlias(SrcList *pList, Token *pToken){
  2947         -  if( pList && pList->nSrc>0 ){
  2948         -    pList->a[pList->nSrc-1].zAlias = sqlite3NameFromToken(pToken);
  2949         -  }
  2950         -}
  2951         -
  2952   2943   /*
  2953   2944   ** Delete an entire SrcList including all its substructure.
  2954   2945   */
  2955   2946   void sqlite3SrcListDelete(SrcList *pList){
  2956   2947     int i;
  2957   2948     struct SrcList_item *pItem;
  2958   2949     if( pList==0 ) return;
................................................................................
  2963   2954       sqlite3DeleteTable(0, pItem->pTab);
  2964   2955       sqlite3SelectDelete(pItem->pSelect);
  2965   2956       sqlite3ExprDelete(pItem->pOn);
  2966   2957       sqlite3IdListDelete(pItem->pUsing);
  2967   2958     }
  2968   2959     sqliteFree(pList);
  2969   2960   }
         2961  +
         2962  +/*
         2963  +** This routine is called by the parser to add a new term to the
         2964  +** end of a growing FROM clause.  The "p" parameter is the part of
         2965  +** the FROM clause that has already been constructed.  "p" is NULL
         2966  +** if this is the first term of the FROM clause.  pTable and pDatabase
         2967  +** are the name of the table and database named in the FROM clause term.
         2968  +** pDatabase is NULL if the database name qualifier is missing - the
         2969  +** usual case.  If the term has a alias, then pAlias points to the
         2970  +** alias token.  If the term is a subquery, then pSubquery is the
         2971  +** SELECT statement that the subquery encodes.  The pTable and
         2972  +** pDatabase parameters are NULL for subqueries.  The pOn and pUsing
         2973  +** parameters are the content of the ON and USING clauses.
         2974  +**
         2975  +** Return a new SrcList which encodes is the FROM with the new
         2976  +** term added.
         2977  +*/
         2978  +SrcList *sqlite3SrcListAppendFromTerm(
         2979  +  SrcList *p,             /* The left part of the FROM clause already seen */
         2980  +  Token *pTable,          /* Name of the table to add to the FROM clause */
         2981  +  Token *pDatabase,       /* Name of the database containing pTable */
         2982  +  Token *pAlias,          /* The right-hand side of the AS subexpression */
         2983  +  Select *pSubquery,      /* A subquery used in place of a table name */
         2984  +  Expr *pOn,              /* The ON clause of a join */
         2985  +  IdList *pUsing          /* The USING clause of a join */
         2986  +){
         2987  +  struct SrcList_item *pItem;
         2988  +  p = sqlite3SrcListAppend(p, pTable, pDatabase);
         2989  +  if( p==0 || p->nSrc==0 ){
         2990  +    sqlite3ExprDelete(pOn);
         2991  +    sqlite3IdListDelete(pUsing);
         2992  +    sqlite3SelectDelete(pSubquery);
         2993  +    return p;
         2994  +  }
         2995  +  pItem = &p->a[p->nSrc-1];
         2996  +  if( pAlias && pAlias->n ){
         2997  +    pItem->zAlias = sqlite3NameFromToken(pAlias);
         2998  +  }
         2999  +  pItem->pSelect = pSubquery;
         3000  +  pItem->pOn = pOn;
         3001  +  pItem->pUsing = pUsing;
         3002  +  return p;
         3003  +}
         3004  +
         3005  +/*
         3006  +** When building up a FROM clause in the parser, the join operator
         3007  +** is initially attached to the left operand.  But the code generator
         3008  +** expects the join operator to be on the right operand.  This routine
         3009  +** Shifts all join operators from left to right for an entire FROM
         3010  +** clause.
         3011  +**
         3012  +** Example: Suppose the join is like this:
         3013  +**
         3014  +**           A natural cross join B
         3015  +**
         3016  +** The operator is "natural cross join".  The A and B operands are stored
         3017  +** in p->a[0] and p->a[1], respectively.  The parser initially stores the
         3018  +** operator with A.  This routine shifts that operator over to B.
         3019  +*/
         3020  +void sqlite3SrcListShiftJoinType(SrcList *p){
         3021  +  if( p && p->a ){
         3022  +    int i;
         3023  +    for(i=p->nSrc-1; i>0; i--){
         3024  +      p->a[i].jointype = p->a[i-1].jointype;
         3025  +    }
         3026  +    p->a[0].jointype = 0;
         3027  +  }
         3028  +}
  2970   3029   
  2971   3030   /*
  2972   3031   ** Begin a transaction
  2973   3032   */
  2974   3033   void sqlite3BeginTransaction(Parse *pParse, int type){
  2975   3034     sqlite3 *db;
  2976   3035     Vdbe *v;

Changes to src/expr.c.

     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** This file contains routines used for analyzing expressions and
    13     13   ** for generating VDBE code that evaluates expressions in SQLite.
    14     14   **
    15         -** $Id: expr.c,v 1.269 2006/11/23 11:59:13 drh Exp $
           15  +** $Id: expr.c,v 1.270 2006/12/16 16:25:15 drh Exp $
    16     16   */
    17     17   #include "sqliteInt.h"
    18     18   #include <ctype.h>
    19     19   
    20     20   /*
    21     21   ** Return the 'affinity' of the expression pExpr if any.
    22     22   **
................................................................................
   887    887               pExpr->iTable = pItem->iCursor;
   888    888               pMatch = pItem;
   889    889               pExpr->pSchema = pTab->pSchema;
   890    890               /* Substitute the rowid (column -1) for the INTEGER PRIMARY KEY */
   891    891               pExpr->iColumn = j==pTab->iPKey ? -1 : j;
   892    892               pExpr->affinity = pTab->aCol[j].affinity;
   893    893               pExpr->pColl = sqlite3FindCollSeq(db, ENC(db), zColl,-1, 0);
   894         -            if( pItem->jointype & JT_NATURAL ){
   895         -              /* If this match occurred in the left table of a natural join,
   896         -              ** then skip the right table to avoid a duplicate match */
   897         -              pItem++;
   898         -              i++;
   899         -            }
   900         -            if( (pUsing = pItem->pUsing)!=0 ){
   901         -              /* If this match occurs on a column that is in the USING clause
   902         -              ** of a join, skip the search of the right table of the join
   903         -              ** to avoid a duplicate match there. */
   904         -              int k;
   905         -              for(k=0; k<pUsing->nId; k++){
   906         -                if( sqlite3StrICmp(pUsing->a[k].zName, zCol)==0 ){
   907         -                  pItem++;
   908         -                  i++;
   909         -                  break;
          894  +            if( i<pSrcList->nSrc-1 ){
          895  +              if( pItem[1].jointype & JT_NATURAL ){
          896  +                /* If this match occurred in the left table of a natural join,
          897  +                ** then skip the right table to avoid a duplicate match */
          898  +                pItem++;
          899  +                i++;
          900  +              }else if( (pUsing = pItem[1].pUsing)!=0 ){
          901  +                /* If this match occurs on a column that is in the USING clause
          902  +                ** of a join, skip the search of the right table of the join
          903  +                ** to avoid a duplicate match there. */
          904  +                int k;
          905  +                for(k=0; k<pUsing->nId; k++){
          906  +                  if( sqlite3StrICmp(pUsing->a[k].zName, zCol)==0 ){
          907  +                    pItem++;
          908  +                    i++;
          909  +                    break;
          910  +                  }
   910    911                   }
   911    912                 }
   912    913               }
   913    914               break;
   914    915             }
   915    916           }
   916    917         }

Changes to src/parse.y.

    10     10   **
    11     11   *************************************************************************
    12     12   ** This file contains SQLite's grammar for SQL.  Process this file
    13     13   ** using the lemon parser generator to generate C code that runs
    14     14   ** the parser.  Lemon will also generate a header file containing
    15     15   ** numeric codes for all of the tokens.
    16     16   **
    17         -** @(#) $Id: parse.y,v 1.210 2006/09/21 11:02:17 drh Exp $
           17  +** @(#) $Id: parse.y,v 1.211 2006/12/16 16:25:15 drh Exp $
    18     18   */
    19     19   
    20     20   // All token codes are small integers with #defines that begin with "TK_"
    21     21   %token_prefix TK_
    22     22   
    23     23   // The type of the data attached to each token is Token.  This is also the
    24     24   // default type for non-terminals.
................................................................................
   440    440   %destructor stl_prefix {sqlite3SrcListDelete($$);}
   441    441   %type from {SrcList*}
   442    442   %destructor from {sqlite3SrcListDelete($$);}
   443    443   
   444    444   // A complete FROM clause.
   445    445   //
   446    446   from(A) ::= .                                 {A = sqliteMalloc(sizeof(*A));}
   447         -from(A) ::= FROM seltablist(X).               {A = X;}
          447  +from(A) ::= FROM seltablist(X).               {
          448  +  A = X;
          449  +  sqlite3SrcListShiftJoinType(A);
          450  +}
   448    451   
   449    452   // "seltablist" is a "Select Table List" - the content of the FROM clause
   450    453   // in a SELECT statement.  "stl_prefix" is a prefix of this list.
   451    454   //
   452    455   stl_prefix(A) ::= seltablist(X) joinop(Y).    {
   453    456      A = X;
   454    457      if( A && A->nSrc>0 ) A->a[A->nSrc-1].jointype = Y;
   455    458   }
   456    459   stl_prefix(A) ::= .                           {A = 0;}
   457    460   seltablist(A) ::= stl_prefix(X) nm(Y) dbnm(D) as(Z) on_opt(N) using_opt(U). {
   458         -  A = sqlite3SrcListAppend(X,&Y,&D);
   459         -  if( Z.n ) sqlite3SrcListAddAlias(A,&Z);
   460         -  if( N ){
   461         -    if( A && A->nSrc>1 ){ A->a[A->nSrc-2].pOn = N; }
   462         -    else { sqlite3ExprDelete(N); }
   463         -  }
   464         -  if( U ){
   465         -    if( A && A->nSrc>1 ){ A->a[A->nSrc-2].pUsing = U; }
   466         -    else { sqlite3IdListDelete(U); }
   467         -  }
          461  +  A = sqlite3SrcListAppendFromTerm(X,&Y,&D,&Z,0,N,U);
   468    462   }
   469    463   %ifndef SQLITE_OMIT_SUBQUERY
   470    464     seltablist(A) ::= stl_prefix(X) LP seltablist_paren(S) RP
   471    465                       as(Z) on_opt(N) using_opt(U). {
   472         -    A = sqlite3SrcListAppend(X,0,0);
   473         -    if( A && A->nSrc>0 ) A->a[A->nSrc-1].pSelect = S;
   474         -    if( Z.n ) sqlite3SrcListAddAlias(A,&Z);
   475         -    if( N ){
   476         -      if( A && A->nSrc>1 ){ A->a[A->nSrc-2].pOn = N; }
   477         -      else { sqlite3ExprDelete(N); }
   478         -    }
   479         -    if( U ){
   480         -      if( A && A->nSrc>1 ){ A->a[A->nSrc-2].pUsing = U; }
   481         -      else { sqlite3IdListDelete(U); }
   482         -    }
          466  +    A = sqlite3SrcListAppendFromTerm(X,0,0,&Z,S,N,U);
   483    467     }
   484    468     
   485    469     // A seltablist_paren nonterminal represents anything in a FROM that
   486    470     // is contained inside parentheses.  This can be either a subquery or
   487    471     // a grouping of table and subqueries.
   488    472     //
   489    473     %type seltablist_paren {Select*}
   490    474     %destructor seltablist_paren {sqlite3SelectDelete($$);}
   491    475     seltablist_paren(A) ::= select(S).      {A = S;}
   492    476     seltablist_paren(A) ::= seltablist(F).  {
          477  +     sqlite3SrcListShiftJoinType(F);
   493    478        A = sqlite3SelectNew(0,F,0,0,0,0,0,0,0);
   494    479     }
   495    480   %endif  SQLITE_OMIT_SUBQUERY
   496    481   
   497    482   %type dbnm {Token}
   498    483   dbnm(A) ::= .          {A.z=0; A.n=0;}
   499    484   dbnm(A) ::= DOT nm(X). {A = X;}

Changes to src/select.c.

     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** This file contains C code routines that are called by the parser
    13     13   ** to handle SELECT statements in SQLite.
    14     14   **
    15         -** $Id: select.c,v 1.322 2006/10/13 15:34:17 drh Exp $
           15  +** $Id: select.c,v 1.323 2006/12/16 16:25:15 drh Exp $
    16     16   */
    17     17   #include "sqliteInt.h"
    18     18   
    19     19   
    20     20   /*
    21     21   ** Delete all the content of a Select structure but do not deallocate
    22     22   ** the select structure itself.
................................................................................
   297    297       Table *pRightTab = pRight->pTab;
   298    298   
   299    299       if( pLeftTab==0 || pRightTab==0 ) continue;
   300    300   
   301    301       /* When the NATURAL keyword is present, add WHERE clause terms for
   302    302       ** every column that the two tables have in common.
   303    303       */
   304         -    if( pLeft->jointype & JT_NATURAL ){
   305         -      if( pLeft->pOn || pLeft->pUsing ){
          304  +    if( pRight->jointype & JT_NATURAL ){
          305  +      if( pRight->pOn || pRight->pUsing ){
   306    306           sqlite3ErrorMsg(pParse, "a NATURAL join may not have "
   307    307              "an ON or USING clause", 0);
   308    308           return 1;
   309    309         }
   310    310         for(j=0; j<pLeftTab->nCol; j++){
   311    311           char *zName = pLeftTab->aCol[j].zName;
   312    312           if( columnIndex(pRightTab, zName)>=0 ){
................................................................................
   316    316             
   317    317           }
   318    318         }
   319    319       }
   320    320   
   321    321       /* Disallow both ON and USING clauses in the same join
   322    322       */
   323         -    if( pLeft->pOn && pLeft->pUsing ){
          323  +    if( pRight->pOn && pRight->pUsing ){
   324    324         sqlite3ErrorMsg(pParse, "cannot have both ON and USING "
   325    325           "clauses in the same join");
   326    326         return 1;
   327    327       }
   328    328   
   329    329       /* Add the ON clause to the end of the WHERE clause, connected by
   330    330       ** an AND operator.
   331    331       */
   332         -    if( pLeft->pOn ){
   333         -      setJoinExpr(pLeft->pOn, pRight->iCursor);
   334         -      p->pWhere = sqlite3ExprAnd(p->pWhere, pLeft->pOn);
   335         -      pLeft->pOn = 0;
          332  +    if( pRight->pOn ){
          333  +      setJoinExpr(pRight->pOn, pRight->iCursor);
          334  +      p->pWhere = sqlite3ExprAnd(p->pWhere, pRight->pOn);
          335  +      pRight->pOn = 0;
   336    336       }
   337    337   
   338    338       /* Create extra terms on the WHERE clause for each column named
   339    339       ** in the USING clause.  Example: If the two tables to be joined are 
   340    340       ** A and B and the USING clause names X, Y, and Z, then add this
   341    341       ** to the WHERE clause:    A.X=B.X AND A.Y=B.Y AND A.Z=B.Z
   342    342       ** Report an error if any column mentioned in the USING clause is
   343    343       ** not contained in both tables to be joined.
   344    344       */
   345         -    if( pLeft->pUsing ){
   346         -      IdList *pList = pLeft->pUsing;
          345  +    if( pRight->pUsing ){
          346  +      IdList *pList = pRight->pUsing;
   347    347         for(j=0; j<pList->nId; j++){
   348    348           char *zName = pList->a[j].zName;
   349    349           if( columnIndex(pLeftTab, zName)<0 || columnIndex(pRightTab, zName)<0 ){
   350    350             sqlite3ErrorMsg(pParse, "cannot join using column %s - column "
   351    351               "not present in both tables", zName);
   352    352             return 1;
   353    353           }
................................................................................
  1305   1305             tableSeen = 1;
  1306   1306             for(j=0; j<pTab->nCol; j++){
  1307   1307               Expr *pExpr, *pRight;
  1308   1308               char *zName = pTab->aCol[j].zName;
  1309   1309   
  1310   1310               if( i>0 ){
  1311   1311                 struct SrcList_item *pLeft = &pTabList->a[i-1];
  1312         -              if( (pLeft->jointype & JT_NATURAL)!=0 &&
         1312  +              if( (pLeft[1].jointype & JT_NATURAL)!=0 &&
  1313   1313                           columnIndex(pLeft->pTab, zName)>=0 ){
  1314   1314                   /* In a NATURAL join, omit the join columns from the 
  1315   1315                   ** table on the right */
  1316   1316                   continue;
  1317   1317                 }
  1318         -              if( sqlite3IdListIndex(pLeft->pUsing, zName)>=0 ){
         1318  +              if( sqlite3IdListIndex(pLeft[1].pUsing, zName)>=0 ){
  1319   1319                   /* In a join with a USING clause, omit columns in the
  1320   1320                   ** using clause from the table on the right. */
  1321   1321                   continue;
  1322   1322                 }
  1323   1323               }
  1324   1324               pRight = sqlite3Expr(TK_ID, 0, 0, 0);
  1325   1325               if( pRight==0 ) break;
................................................................................
  2171   2171     **
  2172   2172     ** If we flatten the above, we would get
  2173   2173     **
  2174   2174     **         (t1 LEFT OUTER JOIN t2) JOIN t3
  2175   2175     **
  2176   2176     ** which is not at all the same thing.
  2177   2177     */
  2178         -  if( pSubSrc->nSrc>1 && iFrom>0 && (pSrc->a[iFrom-1].jointype & JT_OUTER)!=0 ){
         2178  +  if( pSubSrc->nSrc>1 && (pSubitem->jointype & JT_OUTER)!=0 ){
  2179   2179       return 0;
  2180   2180     }
  2181   2181   
  2182   2182     /* Restriction 12:  If the subquery is the right operand of a left outer
  2183   2183     ** join, make sure the subquery has no WHERE clause.
  2184   2184     ** An examples of why this is not allowed:
  2185   2185     **
................................................................................
  2188   2188     ** If we flatten the above, we would get
  2189   2189     **
  2190   2190     **         (t1 LEFT OUTER JOIN t2) WHERE t2.x>0
  2191   2191     **
  2192   2192     ** But the t2.x>0 test will always fail on a NULL row of t2, which
  2193   2193     ** effectively converts the OUTER JOIN into an INNER JOIN.
  2194   2194     */
  2195         -  if( iFrom>0 && (pSrc->a[iFrom-1].jointype & JT_OUTER)!=0 
  2196         -      && pSub->pWhere!=0 ){
         2195  +  if( (pSubitem->jointype & JT_OUTER)!=0 && pSub->pWhere!=0 ){
  2197   2196       return 0;
  2198   2197     }
  2199   2198   
  2200   2199     /* If we reach this point, it means flattening is permitted for the
  2201   2200     ** iFrom-th entry of the FROM clause in the outer query.
  2202   2201     */
  2203   2202   
................................................................................
  2228   2227           pSrc->a[i] = pSrc->a[i-extra];
  2229   2228         }
  2230   2229       }
  2231   2230       for(i=0; i<nSubSrc; i++){
  2232   2231         pSrc->a[i+iFrom] = pSubSrc->a[i];
  2233   2232         memset(&pSubSrc->a[i], 0, sizeof(pSubSrc->a[i]));
  2234   2233       }
  2235         -    pSrc->a[iFrom+nSubSrc-1].jointype = jointype;
         2234  +    pSrc->a[iFrom].jointype = jointype;
  2236   2235     }
  2237   2236   
  2238   2237     /* Now begin substituting subquery result set expressions for 
  2239   2238     ** references to the iParent in the outer query.
  2240   2239     ** 
  2241   2240     ** Example:
  2242   2241     **

Changes to src/sqliteInt.h.

     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** Internal interface definitions for SQLite.
    13     13   **
    14         -** @(#) $Id: sqliteInt.h,v 1.530 2006/11/09 00:24:54 drh Exp $
           14  +** @(#) $Id: sqliteInt.h,v 1.531 2006/12/16 16:25:16 drh Exp $
    15     15   */
    16     16   #ifndef _SQLITEINT_H_
    17     17   #define _SQLITEINT_H_
    18     18   
    19     19   /*
    20     20   ** Extra interface definitions for those who need them
    21     21   */
................................................................................
  1613   1613   void sqlite3DropTable(Parse*, SrcList*, int, int);
  1614   1614   void sqlite3DeleteTable(sqlite3*, Table*);
  1615   1615   void sqlite3Insert(Parse*, SrcList*, ExprList*, Select*, IdList*, int);
  1616   1616   int sqlite3ArrayAllocate(void**,int,int);
  1617   1617   IdList *sqlite3IdListAppend(IdList*, Token*);
  1618   1618   int sqlite3IdListIndex(IdList*,const char*);
  1619   1619   SrcList *sqlite3SrcListAppend(SrcList*, Token*, Token*);
  1620         -void sqlite3SrcListAddAlias(SrcList*, Token*);
         1620  +SrcList *sqlite3SrcListAppendFromTerm(SrcList*, Token*, Token*, Token*,
         1621  +                                      Select*, Expr*, IdList*);
         1622  +void sqlite3SrcListShiftJoinType(SrcList*);
  1621   1623   void sqlite3SrcListAssignCursors(Parse*, SrcList*);
  1622   1624   void sqlite3IdListDelete(IdList*);
  1623   1625   void sqlite3SrcListDelete(SrcList*);
  1624   1626   void sqlite3CreateIndex(Parse*,Token*,Token*,SrcList*,ExprList*,int,Token*,
  1625   1627                           Token*, int, int);
  1626   1628   void sqlite3DropIndex(Parse*, SrcList*, int);
  1627   1629   void sqlite3AddKeyType(Vdbe*, ExprList*);

Changes to src/where.c.

    12     12   ** This module contains C code that generates VDBE code used to process
    13     13   ** the WHERE clause of SQL statements.  This module is reponsible for
    14     14   ** generating the code that loops through a table looking for applicable
    15     15   ** rows.  Indices are selected and used to speed the search when doing
    16     16   ** so is applicable.  Because this module is responsible for selecting
    17     17   ** indices, you might also think of this module as the "query optimizer".
    18     18   **
    19         -** $Id: where.c,v 1.232 2006/11/06 15:10:05 drh Exp $
           19  +** $Id: where.c,v 1.233 2006/12/16 16:25:16 drh Exp $
    20     20   */
    21     21   #include "sqliteInt.h"
    22     22   
    23     23   /*
    24     24   ** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
    25     25   */
    26     26   #define BMS  (sizeof(Bitmask)*8)
................................................................................
  1850   1850       int once = 0;               /* True when first table is seen */
  1851   1851       sqlite3_index_info *pIndex; /* Current virtual index */
  1852   1852   
  1853   1853       lowestCost = SQLITE_BIG_DBL;
  1854   1854       for(j=iFrom, pTabItem=&pTabList->a[j]; j<pTabList->nSrc; j++, pTabItem++){
  1855   1855         int doNotReorder;  /* True if this table should not be reordered */
  1856   1856   
  1857         -      doNotReorder =  (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0
  1858         -                   || (j>0 && (pTabItem[-1].jointype & (JT_LEFT|JT_CROSS))!=0);
         1857  +      doNotReorder =  (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0;
  1859   1858         if( once && doNotReorder ) break;
  1860   1859         m = getMask(&maskSet, pTabItem->iCursor);
  1861   1860         if( (m & notReady)==0 ){
  1862   1861           if( j==iFrom ) iFrom++;
  1863   1862           continue;
  1864   1863         }
  1865   1864         assert( pTabItem->pTab );
................................................................................
  2027   2026       brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
  2028   2027       cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
  2029   2028   
  2030   2029       /* If this is the right table of a LEFT OUTER JOIN, allocate and
  2031   2030       ** initialize a memory cell that records if this table matches any
  2032   2031       ** row of the left table of the join.
  2033   2032       */
  2034         -    if( pLevel->iFrom>0 && (pTabItem[-1].jointype & JT_LEFT)!=0 ){
         2033  +    if( pLevel->iFrom>0 && (pTabItem[0].jointype & JT_LEFT)!=0 ){
  2035   2034         if( !pParse->nMem ) pParse->nMem++;
  2036   2035         pLevel->iLeftJoin = pParse->nMem++;
  2037   2036         sqlite3VdbeAddOp(v, OP_MemInt, 0, pLevel->iLeftJoin);
  2038   2037         VdbeComment((v, "# init LEFT JOIN no-match flag"));
  2039   2038       }
  2040   2039   
  2041   2040   #ifndef SQLITE_OMIT_VIRTUALTABLE

Changes to test/where3.test.

     8      8   #    May you share freely, never taking more than you give.
     9      9   #
    10     10   #***********************************************************************
    11     11   # This file implements regression tests for SQLite library.  The
    12     12   # focus of this file is testing the join reordering optimization
    13     13   # in cases that include a LEFT JOIN.
    14     14   #
    15         -# $Id: where3.test,v 1.2 2006/06/06 11:45:55 drh Exp $
           15  +# $Id: where3.test,v 1.3 2006/12/16 16:25:17 drh Exp $
    16     16   
    17     17   set testdir [file dirname $argv0]
    18     18   source $testdir/tester.tcl
    19     19   
    20     20   # The following is from ticket #1652.
    21     21   #
    22     22   # A comma join then a left outer join:  A,B left join C.
................................................................................
    73     73   
    74     74       SELECT parent1.parent1key, child1.value, child2.value
    75     75       FROM parent1
    76     76       LEFT OUTER JOIN child1 ON child1.child1key = parent1.child1key
    77     77       INNER JOIN child2 ON child2.child2key = parent1.child2key;
    78     78     }
    79     79   } {1 {Value for C1.1} {Value for C2.1} 2 {} {Value for C2.2} 3 {Value for C1.3} {Value for C2.3}}
           80  +
           81  +# This procedure executes the SQL.  Then it appends 
           82  +# the ::sqlite_query_plan variable.
           83  +#
           84  +proc queryplan {sql} {
           85  +  set ::sqlite_sort_count 0
           86  +  set data [execsql $sql]
           87  +  return [concat $data $::sqlite_query_plan]
           88  +}
           89  +
           90  +
           91  +# If you have a from clause of the form:   A B C left join D
           92  +# then make sure the query optimizer is able to reorder the 
           93  +# A B C part anyway it wants. 
           94  +#
           95  +# Following the fix to ticket #1652, there was a time when
           96  +# the C table would not reorder.  So the following reorderings
           97  +# were possible:
           98  +#
           99  +#            A B C left join D
          100  +#            B A C left join D
          101  +#
          102  +# But these reorders were not allowed
          103  +#
          104  +#            C A B left join D
          105  +#            A C B left join D
          106  +#            C B A left join D
          107  +#            B C A left join D
          108  +#
          109  +# The following tests are here to verify that the latter four
          110  +# reorderings are allowed again.
          111  +#
          112  +do_test where3-2.1 {
          113  +  execsql {
          114  +    CREATE TABLE tA(apk integer primary key, ax);
          115  +    CREATE TABLE tB(bpk integer primary key, bx);
          116  +    CREATE TABLE tC(cpk integer primary key, cx);
          117  +    CREATE TABLE tD(dpk integer primary key, dx);
          118  +  }
          119  +  queryplan {
          120  +    SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx
          121  +     WHERE cpk=bx AND bpk=ax
          122  +  }
          123  +} {tA {} tB * tC * tD *}
          124  +do_test where3-2.2 {
          125  +  queryplan {
          126  +    SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx
          127  +     WHERE cpk=bx AND apk=bx
          128  +  }
          129  +} {tB {} tA * tC * tD *}
          130  +do_test where3-2.3 {
          131  +  queryplan {
          132  +    SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx
          133  +     WHERE cpk=bx AND apk=bx
          134  +  }
          135  +} {tB {} tA * tC * tD *}
          136  +do_test where3-2.4 {
          137  +  queryplan {
          138  +    SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx
          139  +     WHERE apk=cx AND bpk=ax
          140  +  }
          141  +} {tC {} tA * tB * tD *}
          142  +do_test where3-2.5 {
          143  +  queryplan {
          144  +    SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx
          145  +     WHERE cpk=ax AND bpk=cx
          146  +  }
          147  +} {tA {} tC * tB * tD *}
          148  +do_test where3-2.5 {
          149  +  queryplan {
          150  +    SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx
          151  +     WHERE bpk=cx AND apk=bx
          152  +  }
          153  +} {tC {} tB * tA * tD *}
          154  +do_test where3-2.6 {
          155  +  queryplan {
          156  +    SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx
          157  +     WHERE cpk=bx AND apk=cx
          158  +  }
          159  +} {tB {} tC * tA * tD *}
          160  +
    80    161   
    81    162   finish_test