Index: src/build.c ================================================================== --- src/build.c +++ src/build.c @@ -20,11 +20,11 @@ ** creating ID lists ** BEGIN TRANSACTION ** COMMIT ** ROLLBACK ** -** $Id: build.c,v 1.411 2006/09/11 23:45:49 drh Exp $ +** $Id: build.c,v 1.412 2006/12/16 16:25:15 drh Exp $ */ #include "sqliteInt.h" #include /* @@ -2938,19 +2938,10 @@ } } } } -/* -** Add an alias to the last identifier on the given identifier list. -*/ -void sqlite3SrcListAddAlias(SrcList *pList, Token *pToken){ - if( pList && pList->nSrc>0 ){ - pList->a[pList->nSrc-1].zAlias = sqlite3NameFromToken(pToken); - } -} - /* ** Delete an entire SrcList including all its substructure. */ void sqlite3SrcListDelete(SrcList *pList){ int i; @@ -2965,10 +2956,78 @@ sqlite3ExprDelete(pItem->pOn); sqlite3IdListDelete(pItem->pUsing); } sqliteFree(pList); } + +/* +** This routine is called by the parser to add a new term to the +** end of a growing FROM clause. The "p" parameter is the part of +** the FROM clause that has already been constructed. "p" is NULL +** if this is the first term of the FROM clause. pTable and pDatabase +** are the name of the table and database named in the FROM clause term. +** pDatabase is NULL if the database name qualifier is missing - the +** usual case. If the term has a alias, then pAlias points to the +** alias token. If the term is a subquery, then pSubquery is the +** SELECT statement that the subquery encodes. The pTable and +** pDatabase parameters are NULL for subqueries. The pOn and pUsing +** parameters are the content of the ON and USING clauses. +** +** Return a new SrcList which encodes is the FROM with the new +** term added. +*/ +SrcList *sqlite3SrcListAppendFromTerm( + SrcList *p, /* The left part of the FROM clause already seen */ + Token *pTable, /* Name of the table to add to the FROM clause */ + Token *pDatabase, /* Name of the database containing pTable */ + Token *pAlias, /* The right-hand side of the AS subexpression */ + Select *pSubquery, /* A subquery used in place of a table name */ + Expr *pOn, /* The ON clause of a join */ + IdList *pUsing /* The USING clause of a join */ +){ + struct SrcList_item *pItem; + p = sqlite3SrcListAppend(p, pTable, pDatabase); + if( p==0 || p->nSrc==0 ){ + sqlite3ExprDelete(pOn); + sqlite3IdListDelete(pUsing); + sqlite3SelectDelete(pSubquery); + return p; + } + pItem = &p->a[p->nSrc-1]; + if( pAlias && pAlias->n ){ + pItem->zAlias = sqlite3NameFromToken(pAlias); + } + pItem->pSelect = pSubquery; + pItem->pOn = pOn; + pItem->pUsing = pUsing; + return p; +} + +/* +** When building up a FROM clause in the parser, the join operator +** is initially attached to the left operand. But the code generator +** expects the join operator to be on the right operand. This routine +** Shifts all join operators from left to right for an entire FROM +** clause. +** +** Example: Suppose the join is like this: +** +** A natural cross join B +** +** The operator is "natural cross join". The A and B operands are stored +** in p->a[0] and p->a[1], respectively. The parser initially stores the +** operator with A. This routine shifts that operator over to B. +*/ +void sqlite3SrcListShiftJoinType(SrcList *p){ + if( p && p->a ){ + int i; + for(i=p->nSrc-1; i>0; i--){ + p->a[i].jointype = p->a[i-1].jointype; + } + p->a[0].jointype = 0; + } +} /* ** Begin a transaction */ void sqlite3BeginTransaction(Parse *pParse, int type){ Index: src/expr.c ================================================================== --- src/expr.c +++ src/expr.c @@ -10,11 +10,11 @@ ** ************************************************************************* ** This file contains routines used for analyzing expressions and ** for generating VDBE code that evaluates expressions in SQLite. ** -** $Id: expr.c,v 1.269 2006/11/23 11:59:13 drh Exp $ +** $Id: expr.c,v 1.270 2006/12/16 16:25:15 drh Exp $ */ #include "sqliteInt.h" #include /* @@ -889,26 +889,27 @@ pExpr->pSchema = pTab->pSchema; /* Substitute the rowid (column -1) for the INTEGER PRIMARY KEY */ pExpr->iColumn = j==pTab->iPKey ? -1 : j; pExpr->affinity = pTab->aCol[j].affinity; pExpr->pColl = sqlite3FindCollSeq(db, ENC(db), zColl,-1, 0); - if( pItem->jointype & JT_NATURAL ){ - /* If this match occurred in the left table of a natural join, - ** then skip the right table to avoid a duplicate match */ - pItem++; - i++; - } - if( (pUsing = pItem->pUsing)!=0 ){ - /* If this match occurs on a column that is in the USING clause - ** of a join, skip the search of the right table of the join - ** to avoid a duplicate match there. */ - int k; - for(k=0; knId; k++){ - if( sqlite3StrICmp(pUsing->a[k].zName, zCol)==0 ){ - pItem++; - i++; - break; + if( inSrc-1 ){ + if( pItem[1].jointype & JT_NATURAL ){ + /* If this match occurred in the left table of a natural join, + ** then skip the right table to avoid a duplicate match */ + pItem++; + i++; + }else if( (pUsing = pItem[1].pUsing)!=0 ){ + /* If this match occurs on a column that is in the USING clause + ** of a join, skip the search of the right table of the join + ** to avoid a duplicate match there. */ + int k; + for(k=0; knId; k++){ + if( sqlite3StrICmp(pUsing->a[k].zName, zCol)==0 ){ + pItem++; + i++; + break; + } } } } break; } Index: src/parse.y ================================================================== --- src/parse.y +++ src/parse.y @@ -12,11 +12,11 @@ ** This file contains SQLite's grammar for SQL. Process this file ** using the lemon parser generator to generate C code that runs ** the parser. Lemon will also generate a header file containing ** numeric codes for all of the tokens. ** -** @(#) $Id: parse.y,v 1.210 2006/09/21 11:02:17 drh Exp $ +** @(#) $Id: parse.y,v 1.211 2006/12/16 16:25:15 drh Exp $ */ // All token codes are small integers with #defines that begin with "TK_" %token_prefix TK_ @@ -442,11 +442,14 @@ %destructor from {sqlite3SrcListDelete($$);} // A complete FROM clause. // from(A) ::= . {A = sqliteMalloc(sizeof(*A));} -from(A) ::= FROM seltablist(X). {A = X;} +from(A) ::= FROM seltablist(X). { + A = X; + sqlite3SrcListShiftJoinType(A); +} // "seltablist" is a "Select Table List" - the content of the FROM clause // in a SELECT statement. "stl_prefix" is a prefix of this list. // stl_prefix(A) ::= seltablist(X) joinop(Y). { @@ -453,35 +456,16 @@ A = X; if( A && A->nSrc>0 ) A->a[A->nSrc-1].jointype = Y; } stl_prefix(A) ::= . {A = 0;} seltablist(A) ::= stl_prefix(X) nm(Y) dbnm(D) as(Z) on_opt(N) using_opt(U). { - A = sqlite3SrcListAppend(X,&Y,&D); - if( Z.n ) sqlite3SrcListAddAlias(A,&Z); - if( N ){ - if( A && A->nSrc>1 ){ A->a[A->nSrc-2].pOn = N; } - else { sqlite3ExprDelete(N); } - } - if( U ){ - if( A && A->nSrc>1 ){ A->a[A->nSrc-2].pUsing = U; } - else { sqlite3IdListDelete(U); } - } + A = sqlite3SrcListAppendFromTerm(X,&Y,&D,&Z,0,N,U); } %ifndef SQLITE_OMIT_SUBQUERY seltablist(A) ::= stl_prefix(X) LP seltablist_paren(S) RP as(Z) on_opt(N) using_opt(U). { - A = sqlite3SrcListAppend(X,0,0); - if( A && A->nSrc>0 ) A->a[A->nSrc-1].pSelect = S; - if( Z.n ) sqlite3SrcListAddAlias(A,&Z); - if( N ){ - if( A && A->nSrc>1 ){ A->a[A->nSrc-2].pOn = N; } - else { sqlite3ExprDelete(N); } - } - if( U ){ - if( A && A->nSrc>1 ){ A->a[A->nSrc-2].pUsing = U; } - else { sqlite3IdListDelete(U); } - } + A = sqlite3SrcListAppendFromTerm(X,0,0,&Z,S,N,U); } // A seltablist_paren nonterminal represents anything in a FROM that // is contained inside parentheses. This can be either a subquery or // a grouping of table and subqueries. @@ -488,10 +472,11 @@ // %type seltablist_paren {Select*} %destructor seltablist_paren {sqlite3SelectDelete($$);} seltablist_paren(A) ::= select(S). {A = S;} seltablist_paren(A) ::= seltablist(F). { + sqlite3SrcListShiftJoinType(F); A = sqlite3SelectNew(0,F,0,0,0,0,0,0,0); } %endif SQLITE_OMIT_SUBQUERY %type dbnm {Token} Index: src/select.c ================================================================== --- src/select.c +++ src/select.c @@ -10,11 +10,11 @@ ** ************************************************************************* ** This file contains C code routines that are called by the parser ** to handle SELECT statements in SQLite. ** -** $Id: select.c,v 1.322 2006/10/13 15:34:17 drh Exp $ +** $Id: select.c,v 1.323 2006/12/16 16:25:15 drh Exp $ */ #include "sqliteInt.h" /* @@ -299,12 +299,12 @@ if( pLeftTab==0 || pRightTab==0 ) continue; /* When the NATURAL keyword is present, add WHERE clause terms for ** every column that the two tables have in common. */ - if( pLeft->jointype & JT_NATURAL ){ - if( pLeft->pOn || pLeft->pUsing ){ + if( pRight->jointype & JT_NATURAL ){ + if( pRight->pOn || pRight->pUsing ){ sqlite3ErrorMsg(pParse, "a NATURAL join may not have " "an ON or USING clause", 0); return 1; } for(j=0; jnCol; j++){ @@ -318,34 +318,34 @@ } } /* Disallow both ON and USING clauses in the same join */ - if( pLeft->pOn && pLeft->pUsing ){ + if( pRight->pOn && pRight->pUsing ){ sqlite3ErrorMsg(pParse, "cannot have both ON and USING " "clauses in the same join"); return 1; } /* Add the ON clause to the end of the WHERE clause, connected by ** an AND operator. */ - if( pLeft->pOn ){ - setJoinExpr(pLeft->pOn, pRight->iCursor); - p->pWhere = sqlite3ExprAnd(p->pWhere, pLeft->pOn); - pLeft->pOn = 0; + if( pRight->pOn ){ + setJoinExpr(pRight->pOn, pRight->iCursor); + p->pWhere = sqlite3ExprAnd(p->pWhere, pRight->pOn); + pRight->pOn = 0; } /* Create extra terms on the WHERE clause for each column named ** in the USING clause. Example: If the two tables to be joined are ** A and B and the USING clause names X, Y, and Z, then add this ** to the WHERE clause: A.X=B.X AND A.Y=B.Y AND A.Z=B.Z ** Report an error if any column mentioned in the USING clause is ** not contained in both tables to be joined. */ - if( pLeft->pUsing ){ - IdList *pList = pLeft->pUsing; + if( pRight->pUsing ){ + IdList *pList = pRight->pUsing; for(j=0; jnId; j++){ char *zName = pList->a[j].zName; if( columnIndex(pLeftTab, zName)<0 || columnIndex(pRightTab, zName)<0 ){ sqlite3ErrorMsg(pParse, "cannot join using column %s - column " "not present in both tables", zName); @@ -1307,17 +1307,17 @@ Expr *pExpr, *pRight; char *zName = pTab->aCol[j].zName; if( i>0 ){ struct SrcList_item *pLeft = &pTabList->a[i-1]; - if( (pLeft->jointype & JT_NATURAL)!=0 && + if( (pLeft[1].jointype & JT_NATURAL)!=0 && columnIndex(pLeft->pTab, zName)>=0 ){ /* In a NATURAL join, omit the join columns from the ** table on the right */ continue; } - if( sqlite3IdListIndex(pLeft->pUsing, zName)>=0 ){ + if( sqlite3IdListIndex(pLeft[1].pUsing, zName)>=0 ){ /* In a join with a USING clause, omit columns in the ** using clause from the table on the right. */ continue; } } @@ -2173,11 +2173,11 @@ ** ** (t1 LEFT OUTER JOIN t2) JOIN t3 ** ** which is not at all the same thing. */ - if( pSubSrc->nSrc>1 && iFrom>0 && (pSrc->a[iFrom-1].jointype & JT_OUTER)!=0 ){ + if( pSubSrc->nSrc>1 && (pSubitem->jointype & JT_OUTER)!=0 ){ return 0; } /* Restriction 12: If the subquery is the right operand of a left outer ** join, make sure the subquery has no WHERE clause. @@ -2190,12 +2190,11 @@ ** (t1 LEFT OUTER JOIN t2) WHERE t2.x>0 ** ** But the t2.x>0 test will always fail on a NULL row of t2, which ** effectively converts the OUTER JOIN into an INNER JOIN. */ - if( iFrom>0 && (pSrc->a[iFrom-1].jointype & JT_OUTER)!=0 - && pSub->pWhere!=0 ){ + if( (pSubitem->jointype & JT_OUTER)!=0 && pSub->pWhere!=0 ){ return 0; } /* If we reach this point, it means flattening is permitted for the ** iFrom-th entry of the FROM clause in the outer query. @@ -2230,11 +2229,11 @@ } for(i=0; ia[i+iFrom] = pSubSrc->a[i]; memset(&pSubSrc->a[i], 0, sizeof(pSubSrc->a[i])); } - pSrc->a[iFrom+nSubSrc-1].jointype = jointype; + pSrc->a[iFrom].jointype = jointype; } /* Now begin substituting subquery result set expressions for ** references to the iParent in the outer query. ** Index: src/sqliteInt.h ================================================================== --- src/sqliteInt.h +++ src/sqliteInt.h @@ -9,11 +9,11 @@ ** May you share freely, never taking more than you give. ** ************************************************************************* ** Internal interface definitions for SQLite. ** -** @(#) $Id: sqliteInt.h,v 1.530 2006/11/09 00:24:54 drh Exp $ +** @(#) $Id: sqliteInt.h,v 1.531 2006/12/16 16:25:16 drh Exp $ */ #ifndef _SQLITEINT_H_ #define _SQLITEINT_H_ /* @@ -1615,11 +1615,13 @@ void sqlite3Insert(Parse*, SrcList*, ExprList*, Select*, IdList*, int); int sqlite3ArrayAllocate(void**,int,int); IdList *sqlite3IdListAppend(IdList*, Token*); int sqlite3IdListIndex(IdList*,const char*); SrcList *sqlite3SrcListAppend(SrcList*, Token*, Token*); -void sqlite3SrcListAddAlias(SrcList*, Token*); +SrcList *sqlite3SrcListAppendFromTerm(SrcList*, Token*, Token*, Token*, + Select*, Expr*, IdList*); +void sqlite3SrcListShiftJoinType(SrcList*); void sqlite3SrcListAssignCursors(Parse*, SrcList*); void sqlite3IdListDelete(IdList*); void sqlite3SrcListDelete(SrcList*); void sqlite3CreateIndex(Parse*,Token*,Token*,SrcList*,ExprList*,int,Token*, Token*, int, int); Index: src/where.c ================================================================== --- src/where.c +++ src/where.c @@ -14,11 +14,11 @@ ** generating the code that loops through a table looking for applicable ** rows. Indices are selected and used to speed the search when doing ** so is applicable. Because this module is responsible for selecting ** indices, you might also think of this module as the "query optimizer". ** -** $Id: where.c,v 1.232 2006/11/06 15:10:05 drh Exp $ +** $Id: where.c,v 1.233 2006/12/16 16:25:16 drh Exp $ */ #include "sqliteInt.h" /* ** The number of bits in a Bitmask. "BMS" means "BitMask Size". @@ -1852,12 +1852,11 @@ lowestCost = SQLITE_BIG_DBL; for(j=iFrom, pTabItem=&pTabList->a[j]; jnSrc; j++, pTabItem++){ int doNotReorder; /* True if this table should not be reordered */ - doNotReorder = (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0 - || (j>0 && (pTabItem[-1].jointype & (JT_LEFT|JT_CROSS))!=0); + doNotReorder = (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0; if( once && doNotReorder ) break; m = getMask(&maskSet, pTabItem->iCursor); if( (m & notReady)==0 ){ if( j==iFrom ) iFrom++; continue; @@ -2029,11 +2028,11 @@ /* If this is the right table of a LEFT OUTER JOIN, allocate and ** initialize a memory cell that records if this table matches any ** row of the left table of the join. */ - if( pLevel->iFrom>0 && (pTabItem[-1].jointype & JT_LEFT)!=0 ){ + if( pLevel->iFrom>0 && (pTabItem[0].jointype & JT_LEFT)!=0 ){ if( !pParse->nMem ) pParse->nMem++; pLevel->iLeftJoin = pParse->nMem++; sqlite3VdbeAddOp(v, OP_MemInt, 0, pLevel->iLeftJoin); VdbeComment((v, "# init LEFT JOIN no-match flag")); } Index: test/where3.test ================================================================== --- test/where3.test +++ test/where3.test @@ -10,11 +10,11 @@ #*********************************************************************** # This file implements regression tests for SQLite library. The # focus of this file is testing the join reordering optimization # in cases that include a LEFT JOIN. # -# $Id: where3.test,v 1.2 2006/06/06 11:45:55 drh Exp $ +# $Id: where3.test,v 1.3 2006/12/16 16:25:17 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # The following is from ticket #1652. @@ -75,7 +75,88 @@ FROM parent1 LEFT OUTER JOIN child1 ON child1.child1key = parent1.child1key INNER JOIN child2 ON child2.child2key = parent1.child2key; } } {1 {Value for C1.1} {Value for C2.1} 2 {} {Value for C2.2} 3 {Value for C1.3} {Value for C2.3}} + +# This procedure executes the SQL. Then it appends +# the ::sqlite_query_plan variable. +# +proc queryplan {sql} { + set ::sqlite_sort_count 0 + set data [execsql $sql] + return [concat $data $::sqlite_query_plan] +} + + +# If you have a from clause of the form: A B C left join D +# then make sure the query optimizer is able to reorder the +# A B C part anyway it wants. +# +# Following the fix to ticket #1652, there was a time when +# the C table would not reorder. So the following reorderings +# were possible: +# +# A B C left join D +# B A C left join D +# +# But these reorders were not allowed +# +# C A B left join D +# A C B left join D +# C B A left join D +# B C A left join D +# +# The following tests are here to verify that the latter four +# reorderings are allowed again. +# +do_test where3-2.1 { + execsql { + CREATE TABLE tA(apk integer primary key, ax); + CREATE TABLE tB(bpk integer primary key, bx); + CREATE TABLE tC(cpk integer primary key, cx); + CREATE TABLE tD(dpk integer primary key, dx); + } + queryplan { + SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx + WHERE cpk=bx AND bpk=ax + } +} {tA {} tB * tC * tD *} +do_test where3-2.2 { + queryplan { + SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx + WHERE cpk=bx AND apk=bx + } +} {tB {} tA * tC * tD *} +do_test where3-2.3 { + queryplan { + SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx + WHERE cpk=bx AND apk=bx + } +} {tB {} tA * tC * tD *} +do_test where3-2.4 { + queryplan { + SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx + WHERE apk=cx AND bpk=ax + } +} {tC {} tA * tB * tD *} +do_test where3-2.5 { + queryplan { + SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx + WHERE cpk=ax AND bpk=cx + } +} {tA {} tC * tB * tD *} +do_test where3-2.5 { + queryplan { + SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx + WHERE bpk=cx AND apk=bx + } +} {tC {} tB * tA * tD *} +do_test where3-2.6 { + queryplan { + SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx + WHERE cpk=bx AND apk=cx + } +} {tB {} tC * tA * tD *} + finish_test