Preliminary code to support RIGHT JOIN. Everything seems to work, except that

the code to compute the unmatched rows for the RIGHT JOIN has not yet been
added, so the result of a RIGHT JOIN is currently the same as an INNER JOIN.

FossilOrigin-Name: 415abd6731b8e8a605adabfa6066c8a852a8531c300df41325d5f7e75cae5a70

8 files changed, 72 insertions, 64 deletions

diff --git a/src/build.c b/src/build.c
index da862fa70..7181011c3 100644
--- a/src/build.c
+++ b/src/build.c
@@ -5071,10 +5071,22 @@ void sqlite3SrcListFuncArgs(Parse *pParse, SrcList *p, ExprList *pList){
 void sqlite3SrcListShiftJoinType(SrcList *p){
   if( p ){
     int i;
+    u8 allFlags = 0;
     for(i=p->nSrc-1; i>0; i--){
-      p->a[i].fg.jointype = p->a[i-1].fg.jointype;
+      allFlags |= p->a[i].fg.jointype = p->a[i-1].fg.jointype;
     }
     p->a[0].fg.jointype = 0;
+
+    /* All terms to the left of a RIGHT JOIN should be tagged with the
+    ** JT_LTORJ flags */
+    if( allFlags & JT_RIGHT ){
+      for(i=p->nSrc-1; ALWAYS(i>0) && (p->a[i].fg.jointype&JT_RIGHT)==0; i--){}
+      i--;
+      assert( i>=0 );
+      do{
+        p->a[i--].fg.jointype |= JT_LTORJ;
+      }while( i>=0 );
+    }
   }
 }
 
diff --git a/src/resolve.c b/src/resolve.c
index 30785ca70..ac00564da 100644
--- a/src/resolve.c
+++ b/src/resolve.c
@@ -367,9 +367,7 @@ static int lookupName(
         pExpr->iTable = pMatch->iCursor;
         assert( ExprUseYTab(pExpr) );
         pExpr->y.pTab = pMatch->pTab;
-        /* RIGHT JOIN not (yet) supported */
-        assert( (pMatch->fg.jointype & JT_RIGHT)==0 );
-        if( (pMatch->fg.jointype & JT_LEFT)!=0 ){
+        if( (pMatch->fg.jointype & (JT_LEFT|JT_LTORJ))!=0 ){
           ExprSetProperty(pExpr, EP_CanBeNull);
         }
         pSchema = pExpr->y.pTab->pSchema;
diff --git a/src/select.c b/src/select.c
index 7ac23bd38..b9321aece 100644
--- a/src/select.c
+++ b/src/select.c
@@ -301,10 +301,6 @@ int sqlite3JoinType(Parse *pParse, Token *pA, Token *pB, Token *pC){
     sqlite3ErrorMsg(pParse, "unknown or unsupported join type: "
        "%T%s%T%s%T", pA, zSp1, pB, zSp2, pC);
     jointype = JT_INNER;
-  }else if( (jointype & JT_RIGHT)!=0 ){
-    sqlite3ErrorMsg(pParse, 
-      "RIGHT and FULL OUTER JOINs are not currently supported");
-    jointype = JT_INNER;
   }
   return jointype;
 }
@@ -6589,7 +6585,7 @@ int sqlite3Select(
      && i==0
      && (p->selFlags & SF_ComplexResult)!=0
      && (pTabList->nSrc==1
-         || (pTabList->a[1].fg.jointype&(JT_LEFT|JT_CROSS))!=0)
+         || (pTabList->a[1].fg.jointype&(JT_OUTER|JT_CROSS))!=0)
     ){
       continue;
     }
@@ -6741,8 +6737,8 @@ int sqlite3Select(
     */
     if( i==0
      && (pTabList->nSrc==1
-            || (pTabList->a[1].fg.jointype&(JT_LEFT|JT_CROSS))!=0)  /* (1) */
-     && (pItem->fg.isCte==0 || pItem->u2.pCteUse->eM10d!=M10d_Yes)  /* (2) */
+            || (pTabList->a[1].fg.jointype&(JT_OUTER|JT_CROSS))!=0)  /* (1) */
+     && (pItem->fg.isCte==0 || pItem->u2.pCteUse->eM10d!=M10d_Yes)   /* (2) */
     ){
       /* Implement a co-routine that will return a single row of the result
       ** set on each invocation.
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index ead20c9a2..264a9d373 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -3132,13 +3132,14 @@ struct SrcList {
 /*
 ** Permitted values of the SrcList.a.jointype field
 */
-#define JT_INNER     0x0001    /* Any kind of inner or cross join */
-#define JT_CROSS     0x0002    /* Explicit use of the CROSS keyword */
-#define JT_NATURAL   0x0004    /* True for a "natural" join */
-#define JT_LEFT      0x0008    /* Left outer join */
-#define JT_RIGHT     0x0010    /* Right outer join */
-#define JT_OUTER     0x0020    /* The "OUTER" keyword is present */
-#define JT_ERROR     0x0040    /* unknown or unsupported join type */
+#define JT_INNER     0x01    /* Any kind of inner or cross join */
+#define JT_CROSS     0x02    /* Explicit use of the CROSS keyword */
+#define JT_NATURAL   0x04    /* True for a "natural" join */
+#define JT_LEFT      0x08    /* Left outer join */
+#define JT_RIGHT     0x10    /* Right outer join */
+#define JT_OUTER     0x20    /* The "OUTER" keyword is present */
+#define JT_LTORJ     0x40    /* One of the LEFT operands of a RIGHT JOIN */
+#define JT_ERROR     0x80    /* unknown or unsupported join type */
 
 
 /*
diff --git a/src/treeview.c b/src/treeview.c
index 91aff8ddf..f32064cd8 100644
--- a/src/treeview.c
+++ b/src/treeview.c
@@ -144,8 +144,12 @@ void sqlite3TreeViewSrcList(TreeView *pView, const SrcList *pSrc){
       sqlite3_str_appendf(&x, " tab=%Q nCol=%d ptr=%p used=%llx",
            pItem->pTab->zName, pItem->pTab->nCol, pItem->pTab, pItem->colUsed);
     }
-    if( pItem->fg.jointype & JT_LEFT ){
+    if( (pItem->fg.jointype & (JT_LEFT|JT_RIGHT))==(JT_LEFT|JT_RIGHT) ){
+      sqlite3_str_appendf(&x, " FULL-OUTER-JOIN");
+    }else if( pItem->fg.jointype & JT_LEFT ){
       sqlite3_str_appendf(&x, " LEFT-JOIN");
+    }else if( pItem->fg.jointype & JT_RIGHT ){
+      sqlite3_str_appendf(&x, " RIGHT-JOIN");
     }else if( pItem->fg.jointype & JT_CROSS ){
       sqlite3_str_appendf(&x, " CROSS-JOIN");
     }
diff --git a/src/where.c b/src/where.c
index f08c350b0..60e314e75 100644
--- a/src/where.c
+++ b/src/where.c
@@ -732,13 +732,13 @@ static int termCanDriveIndex(
   char aff;
   if( pTerm->leftCursor!=pSrc->iCursor ) return 0;
   if( (pTerm->eOperator & (WO_EQ|WO_IS))==0 ) return 0;
-  if( (pSrc->fg.jointype & JT_LEFT) 
+  if( (pSrc->fg.jointype & (JT_LEFT|JT_LTORJ))!=0
    && !ExprHasProperty(pTerm->pExpr, EP_FromJoin)
    && (pTerm->eOperator & WO_IS)
   ){
     /* Cannot use an IS term from the WHERE clause as an index driver for
-    ** the RHS of a LEFT JOIN. Such a term can only be used if it is from
-    ** the ON clause.  */
+    ** the RHS of a LEFT JOIN or for the LHS of a RIGHT JOIN. Such a term
+    ** can only be used if it is from the ON clause.  */
     return 0;
   }
   if( (pTerm->prereqRight & notReady)!=0 ) return 0;
@@ -808,7 +808,8 @@ static SQLITE_NOINLINE void constructAutomaticIndex(
     ** WHERE clause (or the ON clause of a LEFT join) that constrain which
     ** rows of the target table (pSrc) that can be used. */
     if( (pTerm->wtFlags & TERM_VIRTUAL)==0
-     && ((pSrc->fg.jointype&JT_LEFT)==0 || ExprHasProperty(pExpr,EP_FromJoin))
+     && ((pSrc->fg.jointype&(JT_LEFT|JT_LTORJ))==0
+               || ExprHasProperty(pExpr,EP_FromJoin))
      && sqlite3ExprIsTableConstant(pExpr, pSrc->iCursor)
     ){
       pPartial = sqlite3ExprAnd(pParse, pPartial,
@@ -1081,7 +1082,7 @@ static SQLITE_NOINLINE void sqlite3ConstructBloomFilter(
       const SrcItem *pTabItem;
       pLevel = &pWInfo->a[iLevel];
       pTabItem = &pWInfo->pTabList->a[pLevel->iFrom];
-      if( pTabItem->fg.jointype & JT_LEFT ) continue;
+      if( pTabItem->fg.jointype & (JT_LEFT|JT_LTORJ) ) continue;
       pLoop = pLevel->pWLoop;
       if( NEVER(pLoop==0) ) continue;
       if( pLoop->prereq & notReady ) continue;
@@ -1154,9 +1155,10 @@ static sqlite3_index_info *allocateIndexInfo(
     assert( pTerm->u.x.leftColumn<pTab->nCol );
 
     /* tag-20191211-002: WHERE-clause constraints are not useful to the
-    ** right-hand table of a LEFT JOIN.  See tag-20191211-001 for the
+    ** right-hand table of a LEFT JOIN nor to the left-hand table of a
+    ** RIGHT JOIN.  See tag-20191211-001 for the
     ** equivalent restriction for ordinary tables. */
-    if( (pSrc->fg.jointype & JT_LEFT)!=0
+    if( (pSrc->fg.jointype & (JT_LEFT|JT_LTORJ))!=0
      && !ExprHasProperty(pTerm->pExpr, EP_FromJoin)
     ){
       continue;
@@ -2600,10 +2602,11 @@ static void whereLoopOutputAdjust(
         **
         ** 2022-03-24:  Self-culling only applies if either the extra terms
         ** are straight comparison operators that are non-true with NULL
-        ** operand, or if the loop is not a LEFT JOIN.
+        ** operand, or if the loop is not an OUTER JOIN.
         */
         if( (pTerm->eOperator & 0x3f)!=0
-         || (pWC->pWInfo->pTabList->a[pLoop->iTab].fg.jointype & JT_LEFT)==0
+         || (pWC->pWInfo->pTabList->a[pLoop->iTab].fg.jointype
+                  & (JT_LEFT|JT_LTORJ))==0
         ){
           pLoop->wsFlags |= WHERE_SELFCULL;
         }
@@ -2810,9 +2813,10 @@ static int whereLoopAddBtreeIndex(
     if( pTerm->wtFlags & TERM_LIKEOPT && pTerm->eOperator==WO_LT ) continue;
 
     /* tag-20191211-001:  Do not allow constraints from the WHERE clause to
-    ** be used by the right table of a LEFT JOIN.  Only constraints in the
+    ** be used by the right table of a LEFT JOIN nor by the left table of a
+    ** RIGHT JOIN.  Only constraints in the
     ** ON clause are allowed.  See tag-20191211-002 for the vtab equivalent. */
-    if( (pSrc->fg.jointype & JT_LEFT)!=0
+    if( (pSrc->fg.jointype & (JT_LEFT|JT_LTORJ))!=0
      && !ExprHasProperty(pTerm->pExpr, EP_FromJoin)
     ){
       continue;
@@ -4114,9 +4118,9 @@ static int whereLoopAddAll(WhereLoopBuilder *pBuilder){
     pNew->iTab = iTab;
     pBuilder->iPlanLimit += SQLITE_QUERY_PLANNER_LIMIT_INCR;
     pNew->maskSelf = sqlite3WhereGetMask(&pWInfo->sMaskSet, pItem->iCursor);
-    if( (pItem->fg.jointype & (JT_LEFT|JT_CROSS))!=0 ){
+    if( (pItem->fg.jointype & (JT_OUTER|JT_CROSS))!=0 ){
       /* This condition is true when pItem is the FROM clause term on the
-      ** right-hand-side of a LEFT or CROSS JOIN.  */
+      ** right-hand-side of a OUTER or CROSS JOIN.  */
       mPrereq = mPrior;
     }else{
       mPrereq = 0;
@@ -4125,7 +4129,7 @@ static int whereLoopAddAll(WhereLoopBuilder *pBuilder){
     if( IsVirtual(pItem->pTab) ){
       SrcItem *p;
       for(p=&pItem[1]; p<pEnd; p++){
-        if( mUnusable || (p->fg.jointype & (JT_LEFT|JT_CROSS)) ){
+        if( mUnusable || (p->fg.jointype & (JT_OUTER|JT_CROSS)) ){
           mUnusable |= sqlite3WhereGetMask(&pWInfo->sMaskSet, p->iCursor);
         }
       }
@@ -5844,6 +5848,10 @@ WhereInfo *sqlite3WhereBegin(
       }
     }
     if( iDb>=0 ) sqlite3CodeVerifySchema(pParse, iDb);
+    if( pTabItem->fg.jointype & JT_RIGHT ){
+      VdbeModuleComment((v, "TO-DO: Setup for the RIGHT JOIN of %s",
+                         pTab->zName));
+    }
   }
   pWInfo->iTop = sqlite3VdbeCurrentAddr(v);
   if( db->mallocFailed ) goto whereBeginError;
@@ -6091,11 +6099,6 @@ void sqlite3WhereEnd(WhereInfo *pWInfo){
                      pWInfo->pTabList->a[pLevel->iFrom].pTab->zName));
   }
 
-  /* The "break" point is here, just past the end of the outer loop.
-  ** Set it.
-  */
-  sqlite3VdbeResolveLabel(v, pWInfo->iBreak);
-
   assert( pWInfo->nLevel<=pTabList->nSrc );
   for(i=0, pLevel=pWInfo->a; i<pWInfo->nLevel; i++, pLevel++){
     int k, last;
@@ -6106,6 +6109,16 @@ void sqlite3WhereEnd(WhereInfo *pWInfo){
     assert( pTab!=0 );
     pLoop = pLevel->pWLoop;
 
+    /* Do RIGHT JOIN processing.  Generate code that will output the
+    ** unmatched rows of the right operand of the RIGHT JOIN with
+    ** all of the columns of the left operand set to NULL.
+    */
+    if( pTabItem->fg.jointype & JT_RIGHT ){
+      VdbeModuleComment((v, "TO-DO: RIGHT JOIN post-processing for %s",
+                            pTab->zName));
+
+    }
+
     /* For a co-routine, change all OP_Column references to the table of
     ** the co-routine into OP_Copy of result contained in a register.
     ** OP_Rowid becomes OP_Null.
@@ -6117,29 +6130,6 @@ void sqlite3WhereEnd(WhereInfo *pWInfo){
       continue;
     }
 
-#ifdef SQLITE_ENABLE_EARLY_CURSOR_CLOSE
-    /* Close all of the cursors that were opened by sqlite3WhereBegin.
-    ** Except, do not close cursors that will be reused by the OR optimization
-    ** (WHERE_OR_SUBCLAUSE).  And do not close the OP_OpenWrite cursors
-    ** created for the ONEPASS optimization.
-    */
-    if( (pTab->tabFlags & TF_Ephemeral)==0
-     && !IsView(pTab)
-     && (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)==0
-    ){
-      int ws = pLoop->wsFlags;
-      if( pWInfo->eOnePass==ONEPASS_OFF && (ws & WHERE_IDX_ONLY)==0 ){
-        sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor);
-      }
-      if( (ws & WHERE_INDEXED)!=0
-       && (ws & (WHERE_IPK|WHERE_AUTO_INDEX))==0 
-       && pLevel->iIdxCur!=pWInfo->aiCurOnePass[1]
-      ){
-        sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur);
-      }
-    }
-#endif
-
     /* If this scan uses an index, make VDBE code substitutions to read data
     ** from the index instead of from the table where possible.  In some cases
     ** this optimization prevents the table from ever being read, which can
@@ -6240,6 +6230,11 @@ void sqlite3WhereEnd(WhereInfo *pWInfo){
     }
   }
 
+  /* The "break" point is here, just past the end of the outer loop.
+  ** Set it.
+  */
+  sqlite3VdbeResolveLabel(v, pWInfo->iBreak);
+
   /* Final cleanup
   */
   if( pWInfo->pExprMods ) whereUndoExprMods(pWInfo);
diff --git a/src/wherecode.c b/src/wherecode.c
index bab514a69..d349a9402 100644
--- a/src/wherecode.c
+++ b/src/wherecode.c
@@ -2604,7 +2604,9 @@ Bitmask sqlite3WhereCodeOneLoopStart(
       }
       pE = pTerm->pExpr;
       assert( pE!=0 );
-      if( (pTabItem->fg.jointype&JT_LEFT) && !ExprHasProperty(pE,EP_FromJoin) ){
+      if( (pTabItem->fg.jointype & (JT_LEFT|JT_LTORJ))
+       && !ExprHasProperty(pE,EP_FromJoin)
+      ){
         continue;
       }
       
@@ -2666,7 +2668,7 @@ Bitmask sqlite3WhereCodeOneLoopStart(
     if( (pTerm->eOperator & (WO_EQ|WO_IS))==0 ) continue;
     if( (pTerm->eOperator & WO_EQUIV)==0 ) continue;
     if( pTerm->leftCursor!=iCur ) continue;
-    if( pTabItem->fg.jointype & JT_LEFT ) continue;
+    if( pTabItem->fg.jointype & (JT_LEFT|JT_LTORJ) ) continue;
     pE = pTerm->pExpr;
 #ifdef WHERETRACE_ENABLED /* 0x800 */
     if( sqlite3WhereTrace & 0x800 ){
diff --git a/src/whereexpr.c b/src/whereexpr.c
index 26a521fff..b74164d1f 100644
--- a/src/whereexpr.c
+++ b/src/whereexpr.c
@@ -1831,7 +1831,7 @@ void sqlite3WhereTabFuncArgs(
     pRhs = sqlite3PExpr(pParse, TK_UPLUS, 
         sqlite3ExprDup(pParse->db, pArgs->a[j].pExpr, 0), 0);
     pTerm = sqlite3PExpr(pParse, TK_EQ, pColRef, pRhs);
-    if( pItem->fg.jointype & JT_LEFT ){
+    if( pItem->fg.jointype & (JT_LEFT|JT_LTORJ) ){
       sqlite3SetJoinExpr(pTerm, pItem->iCursor);
     }
     whereClauseInsert(pWC, pTerm, TERM_DYNAMIC);