/ Check-in [dd568c27]
Login

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

Overview
Comment:Add the left join strength reduction optimization. Enhance the push-down optimization so that it works with many LEFT JOINs.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: dd568c27b1d7656388ea5b4132cc0265aedd7348d265d8e8c7412b00b28a31aa
User & Date: drh 2018-03-22 12:00:43
References
2019-02-05
13:55 New ticket [5948e09b] Incorrect result from LEFT JOIN. artifact: 5400ddb5 user: drh
2018-03-27
15:13
The push-down optimization was being too aggressive such that it sometimes generated incorrect results. Reinstate the restriction (4) (with qualifications) that was removed by check-ins [b5d3dd8cb0b1e4] and [dd568c27b1d765]. check-in: f08c1731 user: drh tags: trunk
2018-03-24
15:47
Yet another fault in the sqlite3ExprImpliesNotNull() routine, causing errors in the LEFT JOIN strength reduction optimization of check-in [dd568c27b1d76563]. check-in: e88cf3d4 user: drh tags: trunk
13:24
Bug fix in the LEFT JOIN strength reduction optimization of check-in [dd568c27b1d76563]. The sqlite3ExprImpliesNotNull() routine was mistakenly assuming that a CASE expression must always be NULL if contained any reference to a variable that was NULL. check-in: cf171abe user: drh tags: trunk
Context
2018-03-22
17:02
Fix a test script problem causing rbuvacuum.test to fail when run along with other tests. check-in: 901cb3b6 user: dan tags: trunk
12:00
Add the left join strength reduction optimization. Enhance the push-down optimization so that it works with many LEFT JOINs. check-in: dd568c27 user: drh tags: trunk
11:28
Add the --valid-sql option to the optfuzz test program. check-in: a8dfeec7 user: drh tags: trunk
2018-03-21
01:59
Relax LEFT-JOIN restrictions on the push-down optimization. Closed-Leaf check-in: b5d3dd8c user: drh tags: join-strength-reduction
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)
          394  +     && (iTable<0 || p->iRightJoinTable==iTable) ){
          395  +      ExprClearProperty(p, EP_FromJoin);
          396  +    }
          397  +    if( p->op==TK_FUNCTION && p->x.pList ){
          398  +      int i;
          399  +      for(i=0; i<p->x.pList->nExpr; i++){
          400  +        unsetJoinExpr(p->x.pList->a[i].pExpr, iTable);
          401  +      }
          402  +    }
          403  +    unsetJoinExpr(p->pLeft, iTable);
          404  +    p = p->pRight;
          405  +  } 
          406  +}
   384    407   
   385    408   /*
   386    409   ** This routine processes the join information for a SELECT statement.
   387    410   ** ON and USING clauses are converted into extra terms of the WHERE clause.
   388    411   ** NATURAL joins also create extra WHERE clause terms.
   389    412   **
   390    413   ** The terms of a FROM clause are contained in the Select.pSrc structure.
................................................................................
  3830   3853   **           to suppress it. **)
  3831   3854   **
  3832   3855   **   (2) The inner query is the recursive part of a common table expression.
  3833   3856   **
  3834   3857   **   (3) The inner query has a LIMIT clause (since the changes to the WHERE
  3835   3858   **       close would change the meaning of the LIMIT).
  3836   3859   **
  3837         -**   (4) The inner query is the right operand of a LEFT JOIN.  (The caller
  3838         -**       enforces this restriction since this routine does not have enough
  3839         -**       information to know.)
         3860  +**   (4) (** This restriction was removed on 2018-03-21.  It used to read:
         3861  +**       The inner query is the right operand of a LEFT JOIN. **)
  3840   3862   **
  3841   3863   **   (5) The WHERE clause expression originates in the ON or USING clause
  3842         -**       of a LEFT JOIN.
         3864  +**       of a LEFT JOIN where iCursor is not the right-hand table of that
         3865  +**       left join.  An example:
         3866  +**
         3867  +**           SELECT *
         3868  +**           FROM (SELECT 1 AS a1 UNION ALL SELECT 2) AS aa
         3869  +**           JOIN (SELECT 1 AS b2 UNION ALL SELECT 2) AS bb ON (a1=b2)
         3870  +**           LEFT JOIN (SELECT 8 AS c3 UNION ALL SELECT 9) AS cc ON (b2=2);
         3871  +**
         3872  +**       The correct answer is three rows:  (1,1,NULL),(2,2,8),(2,2,9).
         3873  +**       But if the (b2=2) term were to be pushed down into the bb subquery,
         3874  +**       then the (1,1,NULL) row would be suppressed.
  3843   3875   **
  3844   3876   ** Return 0 if no changes are made and non-zero if one or more WHERE clause
  3845   3877   ** terms are duplicated into the subquery.
  3846   3878   */
  3847   3879   static int pushDownWhereTerms(
  3848   3880     Parse *pParse,        /* Parse context (for malloc() and error reporting) */
  3849   3881     Select *pSubq,        /* The subquery whose WHERE clause is to be augmented */
................................................................................
  3871   3903     if( pSubq->pLimit!=0 ){
  3872   3904       return 0; /* restriction (3) */
  3873   3905     }
  3874   3906     while( pWhere->op==TK_AND ){
  3875   3907       nChng += pushDownWhereTerms(pParse, pSubq, pWhere->pRight, iCursor);
  3876   3908       pWhere = pWhere->pLeft;
  3877   3909     }
  3878         -  if( ExprHasProperty(pWhere,EP_FromJoin) ) return 0; /* restriction (5) */
         3910  +  if( ExprHasProperty(pWhere,EP_FromJoin) && pWhere->iRightJoinTable!=iCursor ){
         3911  +    return 0; /* restriction (5) */
         3912  +  }
  3879   3913     if( sqlite3ExprIsTableConstant(pWhere, iCursor) ){
  3880   3914       nChng++;
  3881   3915       while( pSubq ){
  3882   3916         SubstContext x;
  3883   3917         pNew = sqlite3ExprDup(pParse->db, pWhere, 0);
         3918  +      unsetJoinExpr(pNew, -1);
  3884   3919         x.pParse = pParse;
  3885   3920         x.iTable = iCursor;
  3886   3921         x.iNewTable = iCursor;
  3887   3922         x.isLeftJoin = 0;
  3888   3923         x.pEList = pSubq->pEList;
  3889   3924         pNew = substExpr(&x, pNew);
  3890   3925         if( pSubq->selFlags & SF_Aggregate ){
................................................................................
  5171   5206     ** does not already exist */
  5172   5207     v = sqlite3GetVdbe(pParse);
  5173   5208     if( v==0 ) goto select_end;
  5174   5209     if( pDest->eDest==SRT_Output ){
  5175   5210       generateColumnNames(pParse, p);
  5176   5211     }
  5177   5212   
  5178         -  /* Try to flatten subqueries in the FROM clause up into the main query
         5213  +  /* Try to various optimizations (flattening subqueries, and strength
         5214  +  ** reduction of join operators) in the FROM clause up into the main query
  5179   5215     */
  5180   5216   #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
  5181   5217     for(i=0; !p->pPrior && i<pTabList->nSrc; i++){
  5182   5218       struct SrcList_item *pItem = &pTabList->a[i];
  5183   5219       Select *pSub = pItem->pSelect;
  5184   5220       Table *pTab = pItem->pTab;
         5221  +
         5222  +    /* Convert LEFT JOIN into JOIN if there are terms of the right table
         5223  +    ** of the LEFT JOIN used in the WHERE clause.
         5224  +    */
         5225  +    if( (pItem->fg.jointype & JT_LEFT)!=0
         5226  +     && sqlite3ExprImpliesNonNullRow(p->pWhere, pItem->iCursor)
         5227  +     && OptimizationEnabled(db, SQLITE_SimplifyJoin)
         5228  +    ){
         5229  +      SELECTTRACE(0x100,pParse,p,
         5230  +                ("LEFT-JOIN simplifies to JOIN on term %d\n",i));
         5231  +      pItem->fg.jointype &= ~(JT_LEFT|JT_OUTER);
         5232  +      unsetJoinExpr(p->pWhere, pItem->iCursor);
         5233  +    }
         5234  +
         5235  +    /* No futher action if this term of the FROM clause is no a subquery */
  5185   5236       if( pSub==0 ) continue;
  5186   5237   
  5187   5238       /* Catch mismatch in the declared columns of a view and the number of
  5188   5239       ** columns in the SELECT on the RHS */
  5189   5240       if( pTab->nCol!=pSub->pEList->nExpr ){
  5190   5241         sqlite3ErrorMsg(pParse, "expected %d columns for '%s' but got %d",
  5191   5242                         pTab->nCol, pTab->zName, pSub->pEList->nExpr);
................................................................................
  5318   5369       ** an exact limit.
  5319   5370       */
  5320   5371       pParse->nHeight += sqlite3SelectExprHeight(p);
  5321   5372   
  5322   5373       /* Make copies of constant WHERE-clause terms in the outer query down
  5323   5374       ** inside the subquery.  This can help the subquery to run more efficiently.
  5324   5375       */
  5325         -    if( (pItem->fg.jointype & JT_OUTER)==0
  5326         -     && OptimizationEnabled(db, SQLITE_PushDown)
         5376  +    if( OptimizationEnabled(db, SQLITE_PushDown)
  5327   5377        && pushDownWhereTerms(pParse, pSub, p->pWhere, pItem->iCursor)
  5328   5378       ){
  5329   5379   #if SELECTTRACE_ENABLED
  5330   5380         if( sqlite3SelectTrace & 0x100 ){
  5331   5381           SELECTTRACE(0x100,pParse,p,("After WHERE-clause push-down:\n"));
  5332   5382           sqlite3TreeViewSelect(0, p, 0);
  5333   5383         }

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/cursorhint2.test.

   132    132   
   133    133   do_extract_hints_test 2.5 {
   134    134     SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE 1 = coalesce(b, 1)
   135    135   } {
   136    136     x2 {EQ(c0,r[2])}
   137    137   }
   138    138   
   139         -do_extract_hints_test 2.6 {
   140         -  SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE 0 = (b IS NOT NULL)
   141         -} {
   142         -  x2 {EQ(c0,r[2])}
   143         -}
   144         -
   145         -do_extract_hints_test 2.7 {
   146         -  SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE 0 = (b IS NOT +NULL)
   147         -} {
   148         -  x2 {EQ(c0,r[2])}
   149         -}
   150         -
   151         -do_extract_hints_test 2.8 {
   152         -  SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE b IS NOT +NULL
   153         -} {
   154         -  x2 {EQ(c0,r[2])}
   155         -}
   156         -
   157         -do_extract_hints_test 2.9 {
   158         -  SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE CASE b WHEN 0 THEN 0 ELSE 1 END;
   159         -} {
   160         -  x2 {EQ(c0,r[2])}
   161         -}
   162         -
   163         -do_extract_hints_test 2.10 {
   164         -  SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE x2.b = 32+32
   165         -} {
   166         -  x2 {AND(EQ(c1,ADD(32,32)),EQ(c0,r[2]))}
   167         -}
   168         -
   169         -ifcapable !icu {
   170         -  # This test only works using the built-in LIKE, not the ICU LIKE extension.
   171         -  do_extract_hints_test 2.11 {
   172         -    SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE x2.b LIKE 'abc%'
          139  +if {0} {
          140  +  # These tests no longer work due to the LEFT-JOIN strength reduction
          141  +  # optimization
          142  +  do_extract_hints_test 2.6 {
          143  +    SELECT * FROM x1 CROSS JOIN x2 ON (a=x) WHERE 0 = (b IS NOT NULL)
          144  +  } {
          145  +    x2 {EQ(c0,r[2])}
          146  +  }
          147  +  
          148  +  do_extract_hints_test 2.7 {
          149  +    SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE 0 = (b IS NOT +NULL)
          150  +  } {
          151  +    x2 {EQ(c0,r[2])}
          152  +  }
          153  +  
          154  +  do_extract_hints_test 2.8 {
          155  +    SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE b IS NOT +NULL
          156  +  } {
          157  +    x2 {EQ(c0,r[2])}
          158  +  }
          159  +  
          160  +  do_extract_hints_test 2.9 {
          161  +    SELECT * FROM x1 LEFT JOIN x2 ON (a=x)
          162  +      WHERE CASE b WHEN 0 THEN 0 ELSE 1 END;
          163  +  } {
          164  +    x2 {EQ(c0,r[2])}
          165  +  }
          166  +  
          167  +  do_extract_hints_test 2.10 {
          168  +    SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE x2.b = 32+32
   173    169     } {
   174         -    x2 {AND(expr,EQ(c0,r[2]))}
          170  +    x2 {AND(EQ(c1,ADD(32,32)),EQ(c0,r[2]))}
          171  +  }
          172  +  
          173  +  ifcapable !icu {
          174  +    # This test only works using the built-in LIKE, not the ICU LIKE extension.
          175  +    do_extract_hints_test 2.11 {
          176  +      SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE x2.b LIKE 'abc%'
          177  +    } {
          178  +      x2 {AND(expr,EQ(c0,r[2]))}
          179  +    }
   175    180     }
   176    181   }
   177         -
          182  +  
   178    183   do_extract_hints_test 2.12 {
   179    184     SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE coalesce(x2.b, 1)
   180    185   } {
   181    186     x2 {EQ(c0,r[2])}
   182    187   }
   183    188   
   184    189   finish_test

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