Initial implementation of LEFT OUTER JOIN including the expanded SQL92 join

syntax. The basic functionality is there but there is still a lot of testing
to do. (CVS 587)

FossilOrigin-Name: 99bd1f5b9a1a20bfeefe15c00d96a34a5f40923e

6 files changed, 225 insertions, 23 deletions

diff --git a/src/build.c b/src/build.c
index 76e22e1d6..4b2da5b7b 100644
--- a/src/build.c
+++ b/src/build.c
@@ -25,7 +25,7 @@
 **     ROLLBACK
 **     PRAGMA
 **
-** $Id: build.c,v 1.94 2002/05/24 02:04:33 drh Exp $
+** $Id: build.c,v 1.95 2002/05/24 20:31:37 drh Exp $
 */
 #include "sqliteInt.h"
 #include <ctype.h>
@@ -1595,6 +1595,19 @@ void sqliteIdListDelete(IdList *pList){
 }
 
 /*
+** Return the index in pList of the identifier named zId.  Return -1
+** if not found.
+*/
+int sqliteIdListIndex(IdList *pList, const char *zName){
+  int i;
+  if( pList==0 ) return -1;
+  for(i=0; i<pList->nId; i++){
+    if( sqliteStrICmp(pList->a[i].zName, zName)==0 ) return i;
+  }
+  return -1;
+}
+
+/*
 ** Delete an entire SrcList including all its substructure.
 */
 void sqliteSrcListDelete(SrcList *pList){
diff --git a/src/select.c b/src/select.c
index 9541ef114..f6b719984 100644
--- a/src/select.c
+++ b/src/select.c
@@ -12,7 +12,7 @@
 ** This file contains C code routines that are called by the parser
 ** to handle SELECT statements in SQLite.
 **
-** $Id: select.c,v 1.83 2002/05/24 16:14:15 drh Exp $
+** $Id: select.c,v 1.84 2002/05/24 20:31:37 drh Exp $
 */
 #include "sqliteInt.h"
 
@@ -106,7 +106,11 @@ int sqliteJoinType(Parse *pParse, Token *pA, Token *pB, Token *pC){
       break;
     }
   }
-  if( (jointype & ~JT_INNER)!=0 ){
+  if(
+     (jointype & (JT_INNER|JT_OUTER))==(JT_INNER|JT_OUTER) ||
+     (jointype & JT_ERROR)!=0 ||
+     (jointype & JT_RIGHT)==JT_RIGHT
+  ){
     static Token dummy = { 0, 0 };
     char *zSp1 = " ", *zSp2 = " ";
     if( pB==0 ){ pB = &dummy; zSp1 = 0; }
@@ -120,6 +124,137 @@ int sqliteJoinType(Parse *pParse, Token *pA, Token *pB, Token *pC){
 }
 
 /*
+** Return the index of a column in a table.  Return -1 if the column
+** is not contained in the table.
+*/
+static int columnIndex(Table *pTab, const char *zCol){
+  int i;
+  for(i=0; i<pTab->nCol; i++){
+    if( sqliteStrICmp(pTab->aCol[i].zName, zCol)==0 ) return i;
+  }
+  return -1;
+}
+
+/*
+** Add a term to the WHERE expression in *ppExpr that requires the
+** zCol column to be equal in the two tables pTab1 and pTab2.
+*/
+static void addWhereTerm(
+  const char *zCol,        /* Name of the column */
+  const Table *pTab1,      /* First table */
+  const Table *pTab2,      /* Second table */
+  Expr **ppExpr            /* Add the equality term to this expression */
+){
+  Token dummy;
+  Expr *pE1a, *pE1b, *pE1c;
+  Expr *pE2a, *pE2b, *pE2c;
+  Expr *pE;
+
+  dummy.z = zCol;
+  dummy.n = strlen(zCol);
+  pE1a = sqliteExpr(TK_ID, 0, 0, &dummy);
+  pE2a = sqliteExpr(TK_ID, 0, 0, &dummy);
+  dummy.z = pTab1->zName;
+  dummy.n = strlen(dummy.z);
+  pE1b = sqliteExpr(TK_ID, 0, 0, &dummy);
+  dummy.z = pTab2->zName;
+  dummy.n = strlen(dummy.z);
+  pE2b = sqliteExpr(TK_ID, 0, 0, &dummy);
+  pE1c = sqliteExpr(TK_DOT, pE1b, pE1a, 0);
+  pE2c = sqliteExpr(TK_DOT, pE2b, pE2a, 0);
+  pE = sqliteExpr(TK_EQ, pE1c, pE2c, 0);
+  if( *ppExpr ){
+    *ppExpr = sqliteExpr(TK_AND, *ppExpr, pE, 0);
+  }else{
+    *ppExpr = pE;
+  }
+}
+
+/*
+** This routine processes the join information for a SELECT statement.
+** ON and USING clauses are converted into extra terms of the WHERE clause.
+** NATURAL joins also create extra WHERE clause terms.
+**
+** This routine returns the number of errors encountered.
+*/
+static int sqliteProcessJoin(Parse *pParse, Select *p){
+  SrcList *pSrc;
+  int i, j;
+  pSrc = p->pSrc;
+  for(i=0; i<pSrc->nSrc-1; i++){
+    struct SrcList_item *pTerm = &pSrc->a[i];
+    struct SrcList_item *pOther = &pSrc->a[i+1];
+
+    if( pTerm->pTab==0 || pOther->pTab==0 ) continue;
+
+    /* When the NATURAL keyword is present, add WHERE clause terms for
+    ** every column that the two tables have in common.
+    */
+    if( pTerm->jointype & JT_NATURAL ){
+      Table *pTab;
+      if( pTerm->pOn || pTerm->pUsing ){
+        sqliteSetString(&pParse->zErrMsg, "a NATURAL join may not have "
+           "an ON or USING clause", 0);
+        pParse->nErr++;
+        return 1;
+      }
+      pTab = pTerm->pTab;
+      for(j=0; j<pTab->nCol; j++){
+        if( columnIndex(pOther->pTab, pTab->aCol[j].zName)>=0 ){
+          addWhereTerm(pTab->aCol[j].zName, pTab, pOther->pTab, &p->pWhere);
+        }
+      }
+    }
+
+    /* Disallow both ON and USING clauses in the same join
+    */
+    if( pTerm->pOn && pTerm->pUsing ){
+      sqliteSetString(&pParse->zErrMsg, "cannot have both ON and USING "
+        "clauses in the same join", 0);
+      pParse->nErr++;
+      return 1;
+    }
+
+    /* Add the ON clause to the end of the WHERE clause, connected by
+    ** and AND operator.
+    */
+    if( pTerm->pOn ){
+      if( p->pWhere==0 ){
+        p->pWhere = pTerm->pOn;
+      }else{
+        p->pWhere = sqliteExpr(TK_AND, p->pWhere, pTerm->pOn, 0);
+      }
+      pTerm->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( pTerm->pUsing ){
+      IdList *pList;
+      int j;
+      assert( i<pSrc->nSrc-1 );
+      pList = pTerm->pUsing;
+      for(j=0; j<pList->nId; j++){
+        if( columnIndex(pTerm->pTab, pList->a[i].zName)<0 ||
+            columnIndex(pOther->pTab, pList->a[i].zName)<0 ){
+          sqliteSetString(&pParse->zErrMsg, "cannot join using column ",
+            pList->a[i].zName, " - column not present in both tables", 0);
+          pParse->nErr++;
+          return 1;
+        }
+        addWhereTerm(pList->a[i].zName, pTerm->pTab, pOther->pTab, &p->pWhere);
+      }
+    }
+  }
+  return 0;
+}
+
+/*
 ** Delete the given Select structure and all of its substructures.
 */
 void sqliteSelectDelete(Select *p){
@@ -414,12 +549,15 @@ Table *sqliteResultSetOfSelect(Parse *pParse, char *zTabName, Select *pSelect){
 }
 
 /*
-** For the given SELECT statement, do two things.
+** For the given SELECT statement, do three things.
 **
 **    (1)  Fill in the pTabList->a[].pTab fields in the SrcList that 
 **         defines the set of tables that should be scanned. 
 **
-**    (2)  Scan the list of columns in the result set (pEList) looking
+**    (2)  Add terms to the WHERE clause to accomodate the NATURAL keyword
+**         on joins and the ON and USING clause of joins.
+**
+**    (3)  Scan the list of columns in the result set (pEList) looking
 **         for instances of the "*" operator or the TABLE.* operator.
 **         If found, expand each "*" to be every column in every table
 **         and TABLE.* to be every column in TABLE.
@@ -447,6 +585,12 @@ static int fillInColumnList(Parse *pParse, Select *p){
     if( pTabList->a[i].zName==0 ){
       /* A sub-query in the FROM clause of a SELECT */
       assert( pTabList->a[i].pSelect!=0 );
+      if( pTabList->a[i].zAlias==0 ){
+        char zFakeName[60];
+        sprintf(zFakeName, "sqlite_subquery_%p_",
+           (void*)pTabList->a[i].pSelect);
+        sqliteSetString(&pTabList->a[i].zAlias, zFakeName, 0);
+      }
       pTabList->a[i].pTab = pTab = 
         sqliteResultSetOfSelect(pParse, pTabList->a[i].zAlias,
                                         pTabList->a[i].pSelect);
@@ -473,6 +617,10 @@ static int fillInColumnList(Parse *pParse, Select *p){
     }
   }
 
+  /* Process NATURAL keywords, and ON and USING clauses of joins.
+  */
+  if( sqliteProcessJoin(pParse, p) ) return 1;
+
   /* For every "*" that occurs in the column list, insert the names of
   ** all columns in all tables.  And for every TABLE.* insert the names
   ** of all columns in TABLE.  The parser inserted a special expression
@@ -531,10 +679,23 @@ static int fillInColumnList(Parse *pParse, Select *p){
           tableSeen = 1;
           for(j=0; j<pTab->nCol; j++){
             Expr *pExpr, *pLeft, *pRight;
+            char *zName = pTab->aCol[j].zName;
+
+            if( i>0 && (pTabList->a[i-1].jointype & JT_NATURAL)!=0 &&
+                columnIndex(pTabList->a[i-1].pTab, zName)>=0 ){
+              /* In a NATURAL join, omit the join columns from the 
+              ** table on the right */
+              continue;
+            }
+            if( i>0 && sqliteIdListIndex(pTabList->a[i-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 = sqliteExpr(TK_ID, 0, 0, 0);
             if( pRight==0 ) break;
-            pRight->token.z = pTab->aCol[j].zName;
-            pRight->token.n = strlen(pTab->aCol[j].zName);
+            pRight->token.z = zName;
+            pRight->token.n = strlen(zName);
             if( zTabName ){
               pLeft = sqliteExpr(TK_ID, 0, 0, 0);
               if( pLeft==0 ) break;
@@ -1295,6 +1456,7 @@ int sqliteSelect(
   if( fillInColumnList(pParse, p) ){
     goto select_end;
   }
+  pWhere = p->pWhere;
   pEList = p->pEList;
   if( pEList==0 ) goto select_end;
 
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index c413b5298..d323174e7 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -11,7 +11,7 @@
 *************************************************************************
 ** Internal interface definitions for SQLite.
 **
-** @(#) $Id: sqliteInt.h,v 1.114 2002/05/24 16:14:15 drh Exp $
+** @(#) $Id: sqliteInt.h,v 1.115 2002/05/24 20:31:37 drh Exp $
 */
 #include "sqlite.h"
 #include "hash.h"
@@ -481,6 +481,8 @@ struct WhereLevel {
   int brk;             /* Jump here to break out of the loop */
   int cont;            /* Jump here to continue with the next loop cycle */
   int op, p1, p2;      /* Opcode used to terminate the loop */
+  int iLeftJoin;       /* Memory cell used to implement LEFT OUTER JOIN */
+  int top;             /* First instruction of interior of the loop */
 };
 
 /*
@@ -797,6 +799,7 @@ void sqliteDropTable(Parse*, Token*, int);
 void sqliteDeleteTable(sqlite*, Table*);
 void sqliteInsert(Parse*, Token*, ExprList*, Select*, IdList*, int);
 IdList *sqliteIdListAppend(IdList*, Token*);
+int sqliteIdListIndex(IdList*,const char*);
 SrcList *sqliteSrcListAppend(SrcList*, Token*);
 void sqliteSrcListAddAlias(SrcList*, Token*);
 void sqliteIdListDelete(IdList*);
diff --git a/src/trigger.c b/src/trigger.c
index d53dff219..48e7ecf79 100644
--- a/src/trigger.c
+++ b/src/trigger.c
@@ -388,18 +388,11 @@ void sqliteDropTrigger(Parse *pParse, Token *pName, int nested)
 ** if there is no match.
 */
 static int checkColumnOverLap(IdList *pIdList, ExprList *pEList){
-  int i, e;
-  if( !pIdList )return 1;
-  if( !pEList )return 1;
-
-  for(i = 0; i < pIdList->nId; i++){ 
-    for(e = 0; e < pEList->nExpr; e++){ 
-      if( !sqliteStrICmp(pIdList->a[i].zName, pEList->a[e].zName) ){
-        return 1;
-      }
-    }
+  int e;
+  if( !pIdList || !pEList ) return 1;
+  for(e=0; e<pEList->nExpr; e++){
+    if( sqliteIdListIndex(pIdList, pEList->a[e].zName)>=0 ) return 1;
   }
-
   return 0; 
 }
 
diff --git a/src/vdbe.c b/src/vdbe.c
index d12e55687..af42f9b52 100644
--- a/src/vdbe.c
+++ b/src/vdbe.c
@@ -30,7 +30,7 @@
 ** But other routines are also provided to help in building up
 ** a program instruction by instruction.
 **
-** $Id: vdbe.c,v 1.147 2002/05/24 02:04:34 drh Exp $
+** $Id: vdbe.c,v 1.148 2002/05/24 20:31:37 drh Exp $
 */
 #include "sqliteInt.h"
 #include <ctype.h>
@@ -3452,8 +3452,12 @@ case OP_Next: {
 
   if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
     int res;
-    rc = sqliteBtreeNext(pCrsr, &res);
-    p->aCsr[i].nullRow = res;
+    if( p->aCsr[i].nullRow ){
+      res = 1;
+    }else{
+      rc = sqliteBtreeNext(pCrsr, &res);
+      p->aCsr[i].nullRow = res;
+    }
     if( res==0 ){
       pc = pOp->p2 - 1;
       sqlite_search_count++;
diff --git a/src/where.c b/src/where.c
index 2082d6aec..a3576cae4 100644
--- a/src/where.c
+++ b/src/where.c
@@ -13,7 +13,7 @@
 ** the WHERE clause of SQL statements.  Also found here are subroutines
 ** to generate VDBE code to evaluate expressions.
 **
-** $Id: where.c,v 1.46 2002/05/24 02:04:34 drh Exp $
+** $Id: where.c,v 1.47 2002/05/24 20:31:38 drh Exp $
 */
 #include "sqliteInt.h"
 
@@ -455,6 +455,17 @@ WhereInfo *sqliteWhereBegin(
     Index *pIdx;
     WhereLevel *pLevel = &pWInfo->a[i];
 
+    /* If this is the right table of a LEFT OUTER JOIN, allocate and
+    ** initialize a memory cell that record if this table matches any
+    ** row of the left table in the join.
+    */
+    if( i>0 && (pTabList->a[i-1].jointype & JT_LEFT)!=0 ){
+      if( !pParse->nMem ) pParse->nMem++;
+      pLevel->iLeftJoin = pParse->nMem++;
+      sqliteVdbeAddOp(v, OP_String, 0, 0);
+      sqliteVdbeAddOp(v, OP_MemStore, pLevel->iLeftJoin, 1);
+    }
+
     pIdx = pLevel->pIdx;
     if( i<ARRAYSIZE(iDirectEq) && iDirectEq[i]>=0 ){
       /* Case 1:  We can directly reference a single row using an
@@ -788,6 +799,15 @@ WhereInfo *sqliteWhereBegin(
       aExpr[j].p = 0;
     }
     brk = cont;
+
+    /* For a LEFT OUTER JOIN, generate code that will record the fact that
+    ** at least one row of the right table has matched the left table.  
+    */
+    if( pLevel->iLeftJoin ){
+      pLevel->top = sqliteVdbeCurrentAddr(v);
+      sqliteVdbeAddOp(v, OP_Integer, 1, 0);
+      sqliteVdbeAddOp(v, OP_MemStore, pLevel->iLeftJoin, 1);
+    }
   }
   pWInfo->iContinue = cont;
   if( pushKey && !haveKey ){
@@ -814,6 +834,13 @@ void sqliteWhereEnd(WhereInfo *pWInfo){
       sqliteVdbeAddOp(v, pLevel->op, pLevel->p1, pLevel->p2);
     }
     sqliteVdbeResolveLabel(v, pLevel->brk);
+    if( pLevel->iLeftJoin ){
+      int addr;
+      addr = sqliteVdbeAddOp(v, OP_MemLoad, pLevel->iLeftJoin, 0);
+      sqliteVdbeAddOp(v, OP_NotNull, 0, addr+4);
+      sqliteVdbeAddOp(v, OP_NullRow, base+i, 0);
+      sqliteVdbeAddOp(v, OP_Goto, 0, pLevel->top);
+    }
   }
   sqliteVdbeResolveLabel(v, pWInfo->iBreak);
   for(i=0; i<pTabList->nSrc; i++){