/ Check-in [5b7abecc]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:If terms of the WHERE clause require that the right table in a LEFT JOIN not be a null row, then simplify the LEFT JOIN into an ordinary JOIN.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | join-strength-reduction
Files: files | file ages | folders
SHA3-256: 5b7abecc7ab8ccbbb8cb5e0f672e67625c2555ad03442efbf34cb395f5bb71a8
User & Date: drh 2018-03-20 21:16:15
Context
2018-03-20
22:52
Do a more thorough job of cleaning traces of the strength-reduced LEFT JOIN. check-in: 08833dda user: drh tags: join-strength-reduction
21:16
If terms of the WHERE clause require that the right table in a LEFT JOIN not be a null row, then simplify the LEFT JOIN into an ordinary JOIN. check-in: 5b7abecc user: drh tags: join-strength-reduction
19:02
Fix incorrect testcase labels on two cases in join5.test. No changes to code. check-in: 4661ac81 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/expr.c.

  4996   4996     if( pE2->op==TK_NOTNULL && pE1->op!=TK_ISNULL && pE1->op!=TK_IS ){
  4997   4997       Expr *pX = sqlite3ExprSkipCollate(pE1->pLeft);
  4998   4998       testcase( pX!=pE1->pLeft );
  4999   4999       if( sqlite3ExprCompare(pParse, pX, pE2->pLeft, iTab)==0 ) return 1;
  5000   5000     }
  5001   5001     return 0;
  5002   5002   }
         5003  +
         5004  +/*
         5005  +** This is the Expr node callback for sqlite3ExprImpliesNotNullRow().
         5006  +** If the expression node requires that the table at pWalker->iCur
         5007  +** have a non-NULL column, then set pWalker->eCode to 1 and abort.
         5008  +*/
         5009  +static int impliesNotNullRow(Walker *pWalker, Expr *pExpr){
         5010  +  if( ExprHasProperty(pExpr, EP_FromJoin) ) return WRC_Prune;
         5011  +  switch( pExpr->op ){
         5012  +    case TK_ISNULL:
         5013  +    case TK_IS:
         5014  +    case TK_OR:
         5015  +    case TK_FUNCTION:
         5016  +    case TK_AGG_FUNCTION:
         5017  +      return WRC_Prune;
         5018  +    case TK_COLUMN:
         5019  +    case TK_AGG_COLUMN:
         5020  +      if( pWalker->u.iCur==pExpr->iTable ){
         5021  +        pWalker->eCode = 1;
         5022  +        return WRC_Abort;
         5023  +      }
         5024  +      return WRC_Prune;
         5025  +    default:
         5026  +      return WRC_Continue;
         5027  +  }
         5028  +}
         5029  +
         5030  +/*
         5031  +** Return true (non-zero) if expression p can only be true if at least
         5032  +** one column of table iTab is non-null.  In other words, return true
         5033  +** if expression p will always be NULL or false if every column of iTab
         5034  +** is NULL.
         5035  +**
         5036  +** Terms of p that are marked with EP_FromJoin (and hence that come from
         5037  +** the ON or USING clauses of LEFT JOINS) are excluded from the analysis.
         5038  +**
         5039  +** This routine is used to check if a LEFT JOIN can be converted into
         5040  +** an ordinary JOIN.  The p argument is the WHERE clause.  If the WHERE
         5041  +** clause requires that some column of the right table of the LEFT JOIN
         5042  +** be non-NULL, then the LEFT JOIN can be safely converted into an
         5043  +** ordinary join.
         5044  +*/
         5045  +int sqlite3ExprImpliesNonNullRow(Expr *p, int iTab){
         5046  +  Walker w;
         5047  +  w.xExprCallback = impliesNotNullRow;
         5048  +  w.xSelectCallback = 0;
         5049  +  w.xSelectCallback2 = 0;
         5050  +  w.eCode = 0;
         5051  +  w.u.iCur = iTab;
         5052  +  sqlite3WalkExpr(&w, p);
         5053  +  return w.eCode;
         5054  +}
  5003   5055   
  5004   5056   /*
  5005   5057   ** An instance of the following structure is used by the tree walker
  5006   5058   ** to determine if an expression can be evaluated by reference to the
  5007   5059   ** index only, without having to do a search for the corresponding
  5008   5060   ** table entry.  The IdxCover.pIdx field is the index.  IdxCover.iCur
  5009   5061   ** is the cursor for the table.

Changes to src/select.c.

   377    377           setJoinExpr(p->x.pList->a[i].pExpr, iTable);
   378    378         }
   379    379       }
   380    380       setJoinExpr(p->pLeft, iTable);
   381    381       p = p->pRight;
   382    382     } 
   383    383   }
          384  +
          385  +/* Undo the work of setJoinExpr().  In the expression tree p, convert every
          386  +** term that is marked with EP_FromJoin and iRightJoinTable==iTable into
          387  +** an ordinary term that omits the EP_FromJoin mark.
          388  +**
          389  +** This happens when a LEFT JOIN is simplified into an ordinary JOIN.
          390  +*/
          391  +static void unsetJoinExpr(Expr *p, int iTable){
          392  +  while( p ){
          393  +    if( ExprHasProperty(p, EP_FromJoin) && p->iRightJoinTable==iTable ){
          394  +      ExprClearProperty(p, EP_FromJoin);
          395  +    }
          396  +    if( p->op==TK_FUNCTION && p->x.pList ){
          397  +      int i;
          398  +      for(i=0; i<p->x.pList->nExpr; i++){
          399  +        unsetJoinExpr(p->x.pList->a[i].pExpr, iTable);
          400  +      }
          401  +    }
          402  +    unsetJoinExpr(p->pLeft, iTable);
          403  +    p = p->pRight;
          404  +  } 
          405  +}
   384    406   
   385    407   /*
   386    408   ** This routine processes the join information for a SELECT statement.
   387    409   ** ON and USING clauses are converted into extra terms of the WHERE clause.
   388    410   ** NATURAL joins also create extra WHERE clause terms.
   389    411   **
   390    412   ** The terms of a FROM clause are contained in the Select.pSrc structure.
................................................................................
  5171   5193     ** does not already exist */
  5172   5194     v = sqlite3GetVdbe(pParse);
  5173   5195     if( v==0 ) goto select_end;
  5174   5196     if( pDest->eDest==SRT_Output ){
  5175   5197       generateColumnNames(pParse, p);
  5176   5198     }
  5177   5199   
  5178         -  /* Try to flatten subqueries in the FROM clause up into the main query
         5200  +  /* Try to various optimizations (flattening subqueries, and strength
         5201  +  ** reduction of join operators) in the FROM clause up into the main query
  5179   5202     */
  5180   5203   #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
  5181   5204     for(i=0; !p->pPrior && i<pTabList->nSrc; i++){
  5182   5205       struct SrcList_item *pItem = &pTabList->a[i];
  5183   5206       Select *pSub = pItem->pSelect;
  5184   5207       Table *pTab = pItem->pTab;
         5208  +
         5209  +    /* Convert LEFT JOIN into JOIN if there are terms of the right table
         5210  +    ** of the LEFT JOIN used in the WHERE clause.
         5211  +    */
         5212  +    if( (pItem->fg.jointype & JT_LEFT)!=0
         5213  +     && sqlite3ExprImpliesNonNullRow(p->pWhere, pItem->iCursor)
         5214  +     && OptimizationEnabled(db, SQLITE_SimplifyJoin)
         5215  +    ){
         5216  +      SELECTTRACE(0x100,pParse,p,
         5217  +                ("LEFT-JOIN simplifies to JOIN on term %d\n",i));
         5218  +      pItem->fg.jointype &= ~JT_LEFT;
         5219  +      unsetJoinExpr(p->pWhere, pItem->iCursor);
         5220  +    }
         5221  +
         5222  +    /* No futher action if this term of the FROM clause is no a subquery */
  5185   5223       if( pSub==0 ) continue;
  5186   5224   
  5187   5225       /* Catch mismatch in the declared columns of a view and the number of
  5188   5226       ** columns in the SELECT on the RHS */
  5189   5227       if( pTab->nCol!=pSub->pEList->nExpr ){
  5190   5228         sqlite3ErrorMsg(pParse, "expected %d columns for '%s' but got %d",
  5191   5229                         pTab->nCol, pTab->zName, pSub->pEList->nExpr);

Changes to src/sqliteInt.h.

  1529   1529   #define SQLITE_Transitive     0x0080   /* Transitive constraints */
  1530   1530   #define SQLITE_OmitNoopJoin   0x0100   /* Omit unused tables in joins */
  1531   1531   #define SQLITE_CountOfView    0x0200   /* The count-of-view optimization */
  1532   1532   #define SQLITE_CursorHints    0x0400   /* Add OP_CursorHint opcodes */
  1533   1533   #define SQLITE_Stat34         0x0800   /* Use STAT3 or STAT4 data */
  1534   1534      /* TH3 expects the Stat34  ^^^^^^ value to be 0x0800.  Don't change it */
  1535   1535   #define SQLITE_PushDown       0x1000   /* The push-down optimization */
         1536  +#define SQLITE_SimplifyJoin   0x2000   /* Convert LEFT JOIN to JOIN */
  1536   1537   #define SQLITE_AllOpts        0xffff   /* All optimizations */
  1537   1538   
  1538   1539   /*
  1539   1540   ** Macros for testing whether or not optimizations are enabled or disabled.
  1540   1541   */
  1541   1542   #define OptimizationDisabled(db, mask)  (((db)->dbOptFlags&(mask))!=0)
  1542   1543   #define OptimizationEnabled(db, mask)   (((db)->dbOptFlags&(mask))==0)
................................................................................
  3819   3820   void sqlite3Vacuum(Parse*,Token*);
  3820   3821   int sqlite3RunVacuum(char**, sqlite3*, int);
  3821   3822   char *sqlite3NameFromToken(sqlite3*, Token*);
  3822   3823   int sqlite3ExprCompare(Parse*,Expr*, Expr*, int);
  3823   3824   int sqlite3ExprCompareSkip(Expr*, Expr*, int);
  3824   3825   int sqlite3ExprListCompare(ExprList*, ExprList*, int);
  3825   3826   int sqlite3ExprImpliesExpr(Parse*,Expr*, Expr*, int);
         3827  +int sqlite3ExprImpliesNonNullRow(Expr*,int);
  3826   3828   void sqlite3ExprAnalyzeAggregates(NameContext*, Expr*);
  3827   3829   void sqlite3ExprAnalyzeAggList(NameContext*,ExprList*);
  3828   3830   int sqlite3ExprCoveredByIndex(Expr*, int iCur, Index *pIdx);
  3829   3831   int sqlite3FunctionUsesThisSrc(Expr*, SrcList*);
  3830   3832   Vdbe *sqlite3GetVdbe(Parse*);
  3831   3833   #ifndef SQLITE_UNTESTABLE
  3832   3834   void sqlite3PrngSaveState(void);

Changes to test/e_select.test.

   744    744   do_execsql_test e_select-3.1.5 { SELECT k FROM x1 WHERE x IS NULL } {4 5}
   745    745   do_execsql_test e_select-3.1.6 { SELECT k FROM x1 WHERE z - 78.43 } {2 4 6}
   746    746   
   747    747   do_execsql_test e_select-3.2.1a {
   748    748     SELECT k FROM x1 LEFT JOIN x2 USING(k)
   749    749   } {1 2 3 4 5 6}
   750    750   do_execsql_test e_select-3.2.1b {
   751         -  SELECT k FROM x1 LEFT JOIN x2 USING(k) WHERE x2.k
          751  +  SELECT k FROM x1 LEFT JOIN x2 USING(k) WHERE x2.k ORDER BY +k
   752    752   } {1 3 5}
   753    753   do_execsql_test e_select-3.2.2 {
   754    754     SELECT k FROM x1 LEFT JOIN x2 USING(k) WHERE x2.k IS NULL
   755    755   } {2 4 6}
   756    756   
   757    757   do_execsql_test e_select-3.2.3 {
   758    758     SELECT k FROM x1 NATURAL JOIN x2 WHERE x2.k

Changes to test/join2.test.

    82     82     CREATE TABLE cc(c);
    83     83     INSERT INTO aa VALUES('one');
    84     84     INSERT INTO bb VALUES('one');
    85     85     INSERT INTO cc VALUES('one');
    86     86   }
    87     87   
    88     88   do_catchsql_test 2.1 {
    89         -  SELECT * FROM aa LEFT JOIN cc ON (a=b) JOIN bb ON (b=c);
           89  +  SELECT * FROM aa LEFT JOIN cc ON (a=b) JOIN bb ON (b=coalesce(c,1));
    90     90   } {1 {ON clause references tables to its right}}
    91     91   do_catchsql_test 2.2 {
    92     92     SELECT * FROM aa JOIN cc ON (a=b) JOIN bb ON (b=c);
    93     93   } {0 {one one one}}
    94     94   
    95     95   #-------------------------------------------------------------------------
    96     96   # Test that a problem causing where.c to overlook opportunities to