SQLite

**     CREATE INDEX
**     DROP INDEX
**     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 <ctype.h>

/*
** This routine is called when a new SQL statement is beginning to
** be parsed.  Initialize the pParse structure as needed.

      if( pItem->pSelect ){
        sqlite3SrcListAssignCursors(pParse, pItem->pSelect->pSrc);
      }
    }
  }
}

/*
** 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;
  struct SrcList_item *pItem;
  if( pList==0 ) return;
  for(pItem=pList->a, i=0; i<pList->nSrc; i++, pItem++){
    sqliteFree(pItem->zDatabase);
    sqliteFree(pItem->zName);
    sqliteFree(pItem->zAlias);
    sqlite3DeleteTable(0, pItem->pTab);
    sqlite3SelectDelete(pItem->pSelect);
    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){
  sqlite3 *db;
  Vdbe *v;

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** 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 <ctype.h>

/*
** Return the 'affinity' of the expression pExpr if any.
**

            pExpr->iTable = pItem->iCursor;
            pMatch = pItem;
            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( i<pSrcList->nSrc-1 ){
            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( 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++;
            }
            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; k<pUsing->nId; k++){
                if( sqlite3StrICmp(pUsing->a[k].zName, zCol)==0 ){
                  pItem++;
                  i++;
                  break;
              }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; k<pUsing->nId; k++){
                  if( sqlite3StrICmp(pUsing->a[k].zName, zCol)==0 ){
                    pItem++;
                    i++;
                    break;
                  }
                }
              }
            }
            break;
          }
        }
      }

**
*************************************************************************
** 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_

// The type of the data attached to each token is Token.  This is also the
// default type for non-terminals.

%destructor stl_prefix {sqlite3SrcListDelete($$);}
%type from {SrcList*}
%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).    {
   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);
  A = sqlite3SrcListAppendFromTerm(X,&Y,&D,&Z,0,N,U);
  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); }
  }
}
%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);
    A = sqlite3SrcListAppendFromTerm(X,0,0,&Z,S,N,U);
    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 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.
  //
  %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}
dbnm(A) ::= .          {A.z=0; A.n=0;}
dbnm(A) ::= DOT nm(X). {A = X;}

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** 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"


/*
** Delete all the content of a Select structure but do not deallocate
** the select structure itself.

    Table *pRightTab = pRight->pTab;

    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; j<pLeftTab->nCol; j++){
        char *zName = pLeftTab->aCol[j].zName;
        if( columnIndex(pRightTab, zName)>=0 ){
          addWhereTerm(zName, pLeftTab, pLeft->zAlias, 
                              pRightTab, pRight->zAlias,
                              pRight->iCursor, &p->pWhere);
          
        }
      }
    }

    /* 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; j<pList->nId; 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);
          return 1;
        }

          tableSeen = 1;
          for(j=0; j<pTab->nCol; j++){
            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;
              }
            }
            pRight = sqlite3Expr(TK_ID, 0, 0, 0);
            if( pRight==0 ) break;

  **
  ** If we flatten the above, we would get
  **
  **         (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.
  ** An examples of why this is not allowed:
  **
  **         t1 LEFT OUTER JOIN (SELECT * FROM t2 WHERE t2.x>0)
  **
  ** If we flatten the above, we would get
  **
  **         (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.
  */

        pSrc->a[i] = pSrc->a[i-extra];
      }
    }
    for(i=0; i<nSubSrc; i++){
      pSrc->a[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.
  ** 
  ** Example:
  **

/*
** 2001 September 15
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    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_

/*
** Extra interface definitions for those who need them
*/

void sqlite3DropTable(Parse*, SrcList*, int, int);
void sqlite3DeleteTable(sqlite3*, Table*);
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*);
SrcList *sqlite3SrcListAppendFromTerm(SrcList*, Token*, Token*, Token*,
                                      Select*, Expr*, IdList*);
void sqlite3SrcListAddAlias(SrcList*, Token*);
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);
void sqlite3DropIndex(Parse*, SrcList*, int);
void sqlite3AddKeyType(Vdbe*, ExprList*);

** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is reponsible for
** 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".
*/
#define BMS  (sizeof(Bitmask)*8)

    int once = 0;               /* True when first table is seen */
    sqlite3_index_info *pIndex; /* Current virtual index */

    lowestCost = SQLITE_BIG_DBL;
    for(j=iFrom, pTabItem=&pTabList->a[j]; j<pTabList->nSrc; j++, pTabItem++){
      int doNotReorder;  /* True if this table should not be reordered */

      doNotReorder =  (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0
      doNotReorder =  (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0;
                   || (j>0 && (pTabItem[-1].jointype & (JT_LEFT|JT_CROSS))!=0);
      if( once && doNotReorder ) break;
      m = getMask(&maskSet, pTabItem->iCursor);
      if( (m & notReady)==0 ){
        if( j==iFrom ) iFrom++;
        continue;
      }
      assert( pTabItem->pTab );

    brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
    cont = pLevel->cont = sqlite3VdbeMakeLabel(v);

    /* 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"));
    }

#ifndef SQLITE_OMIT_VIRTUALTABLE

#    May you share freely, never taking more than you give.
#
#***********************************************************************
# 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.
#
# A comma join then a left outer join:  A,B left join C.

    SELECT parent1.parent1key, child1.value, child2.value
    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