Generalize the LEFT JOIN strength reduction optimization so that it works for

RIGHT and FULL JOIN as well.  Rename it to the "OUTER JOIN strength reduction"
optimization.

FossilOrigin-Name: d747afda5683ca5feb92866a14ccc4c5127d3378ece5cad2c3da819f2477b457

4 files changed, 65 insertions, 8 deletions

diff --git a/src/expr.c b/src/expr.c
index 7eef6c6ab..707a9ca6b 100644
--- a/src/expr.c
+++ b/src/expr.c
@@ -6017,7 +6017,7 @@ static void bothImplyNotNullRow(Walker *pWalker, Expr *pE1, Expr *pE2){
 static int impliesNotNullRow(Walker *pWalker, Expr *pExpr){
   testcase( pExpr->op==TK_AGG_COLUMN );
   testcase( pExpr->op==TK_AGG_FUNCTION );
-  if( ExprHasProperty(pExpr, EP_OuterON) ) return WRC_Prune;
+  if( ExprHasProperty(pExpr, EP_OuterON|EP_InnerON) ) return WRC_Prune;
   switch( pExpr->op ){
     case TK_ISNOT:
     case TK_ISNULL:
diff --git a/src/main.c b/src/main.c
index d7f366b5e..a617dcea5 100644
--- a/src/main.c
+++ b/src/main.c
@@ -4446,7 +4446,7 @@ int sqlite3_test_control(int op, ...){
     **
     **   op==0       Store the current sqlite3TreeTrace in *ptr
     **   op==1       Set sqlite3TreeTrace to the value *ptr
-    **   op==3       Store the current sqlite3WhereTrace in *ptr
+    **   op==2       Store the current sqlite3WhereTrace in *ptr
     **   op==3       Set sqlite3WhereTrace to the value *ptr
     */
     case SQLITE_TESTCTRL_TRACEFLAGS: {
diff --git a/src/select.c b/src/select.c
index 755c317c9..0058955d1 100644
--- a/src/select.c
+++ b/src/select.c
@@ -7222,16 +7222,52 @@ int sqlite3Select(
     ** to a real table */
     assert( pTab!=0 );
 
-    /* Convert LEFT JOIN into JOIN if there are terms of the right table
-    ** of the LEFT JOIN used in the WHERE clause.
+    /* Try to simplify joins:
+    **
+    **      LEFT JOIN  ->  JOIN
+    **     RIGHT JOIN  ->  JOIN
+    **      FULL JOIN  ->  RIGHT JOIN
+    **
+    ** If terms of the i-th table are used in the WHERE clause in such a
+    ** way that the i-th table cannot be the NULL row of a join, then
+    ** perform the appropriate simplification. This is called
+    ** "OUTER JOIN strength reduction" in the SQLite documentation.
     */
-    if( (pItem->fg.jointype & (JT_LEFT|JT_RIGHT))==JT_LEFT
+    if( (pItem->fg.jointype & (JT_LEFT|JT_LTORJ))!=0
      && sqlite3ExprImpliesNonNullRow(p->pWhere, pItem->iCursor)
      && OptimizationEnabled(db, SQLITE_SimplifyJoin)
     ){
-      TREETRACE(0x1000,pParse,p,
-                ("LEFT-JOIN simplifies to JOIN on term %d\n",i));
-      pItem->fg.jointype &= ~(JT_LEFT|JT_OUTER);
+      if( pItem->fg.jointype & JT_LEFT ){
+        if( pItem->fg.jointype & JT_RIGHT ){
+          TREETRACE(0x1000,pParse,p,
+                    ("FULL-JOIN simplifies to RIGHT-JOIN on term %d\n",i));
+          pItem->fg.jointype &= ~JT_LEFT;
+        }else{
+          TREETRACE(0x1000,pParse,p,
+                    ("LEFT-JOIN simplifies to JOIN on term %d\n",i));
+          pItem->fg.jointype &= ~(JT_LEFT|JT_OUTER);
+        }
+      }
+      if( pItem->fg.jointype & JT_LTORJ ){
+        for(j=i+1; j<pTabList->nSrc; j++){
+          SrcItem *pI2 = &pTabList->a[j];
+          if( pI2->fg.jointype & JT_RIGHT ){
+            if( pI2->fg.jointype & JT_LEFT ){
+              TREETRACE(0x1000,pParse,p,
+                        ("FULL-JOIN simplifies to LEFT-JOIN on term %d\n",j));
+              pI2->fg.jointype &= ~JT_RIGHT;
+            }else{
+              TREETRACE(0x1000,pParse,p,
+                        ("RIGHT-JOIN simplifies to JOIN on term %d\n",j));
+              pI2->fg.jointype &= ~(JT_RIGHT|JT_OUTER);
+            }
+          }
+        }
+        for(j=pTabList->nSrc-1; j>=i; j--){
+          pTabList->a[j].fg.jointype &= ~JT_LTORJ;
+          if( pTabList->a[j].fg.jointype & JT_RIGHT ) break;
+        }
+      }
       assert( pItem->iCursor>=0 );
       unsetJoinExpr(p->pWhere, pItem->iCursor,
                     pTabList->a[0].fg.jointype & JT_LTORJ);
diff --git a/src/test1.c b/src/test1.c
index 772b896ac..cc41bb3ce 100644
--- a/src/test1.c
+++ b/src/test1.c
@@ -7417,6 +7417,26 @@ static int testLocaltime(const void *aliasT, void *aliasTM){
 }
 
 /*
+** .treetrace N
+*/
+static int SQLITE_TCLAPI test_treetrace(
+  void * clientData,
+  Tcl_Interp *interp,
+  int objc,
+  Tcl_Obj *CONST objv[]
+){
+  unsigned int v = 0;
+  if( objc>=2 ){
+    if( Tcl_GetIntFromObj(interp, objv[1], (int*)&v)==TCL_OK ){
+      sqlite3_test_control(SQLITE_TESTCTRL_TRACEFLAGS, 1, &v);
+    }
+  }
+  sqlite3_test_control(SQLITE_TESTCTRL_TRACEFLAGS, 0, &v);
+  Tcl_SetObjResult(interp, Tcl_NewIntObj((int)v));
+  return TCL_OK;
+}
+
+/*
 ** sqlite3_test_control VERB ARGS...
 */
 static int SQLITE_TCLAPI test_test_control(
@@ -8967,6 +8987,7 @@ int Sqlitetest1_Init(Tcl_Interp *interp){
      { "print_explain_query_plan", test_print_eqp, 0  },
 #endif
      { "sqlite3_test_control", test_test_control },
+     { ".treetrace",           test_treetrace    },
 #if SQLITE_OS_UNIX
      { "getrusage", test_getrusage },
 #endif