SQLite

Check-in [b5d3dd8cb0]
Login

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

Overview
Comment:Relax LEFT-JOIN restrictions on the push-down optimization.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | join-strength-reduction
Files: files | file ages | folders
SHA3-256: b5d3dd8cb0b1e42ed0671a12d22af05194ea9522e4f41fd4bb0deff70b8b0757
User & Date: drh 2018-03-21 01:59:46.055
References
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: f08c1731b0 user: drh tags: trunk)
Context
2018-03-22
12:00
Add the left join strength reduction optimization. Enhance the push-down optimization so that it works with many LEFT JOINs. (check-in: dd568c27b1 user: drh tags: trunk)
2018-03-21
01:59
Relax LEFT-JOIN restrictions on the push-down optimization. (Closed-Leaf check-in: b5d3dd8cb0 user: drh tags: join-strength-reduction)
2018-03-20
22:52
Do a more thorough job of cleaning traces of the strength-reduced LEFT JOIN. (check-in: 08833dda3a user: drh tags: join-strength-reduction)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/select.c.
386
387
388
389
390
391
392
393

394
395
396
397
398
399
400
** term that is marked with EP_FromJoin and iRightJoinTable==iTable into
** an ordinary term that omits the EP_FromJoin mark.
**
** This happens when a LEFT JOIN is simplified into an ordinary JOIN.
*/
static void unsetJoinExpr(Expr *p, int iTable){
  while( p ){
    if( ExprHasProperty(p, EP_FromJoin) && p->iRightJoinTable==iTable ){

      ExprClearProperty(p, EP_FromJoin);
    }
    if( p->op==TK_FUNCTION && p->x.pList ){
      int i;
      for(i=0; i<p->x.pList->nExpr; i++){
        unsetJoinExpr(p->x.pList->a[i].pExpr, iTable);
      }







|
>







386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
** term that is marked with EP_FromJoin and iRightJoinTable==iTable into
** an ordinary term that omits the EP_FromJoin mark.
**
** This happens when a LEFT JOIN is simplified into an ordinary JOIN.
*/
static void unsetJoinExpr(Expr *p, int iTable){
  while( p ){
    if( ExprHasProperty(p, EP_FromJoin)
     && (iTable<0 || p->iRightJoinTable==iTable) ){
      ExprClearProperty(p, EP_FromJoin);
    }
    if( p->op==TK_FUNCTION && p->x.pList ){
      int i;
      for(i=0; i<p->x.pList->nExpr; i++){
        unsetJoinExpr(p->x.pList->a[i].pExpr, iTable);
      }
3852
3853
3854
3855
3856
3857
3858

3859
3860
3861
3862
3863
3864










3865
3866
3867
3868
3869
3870
3871
**           to suppress it. **)
**
**   (2) The inner query is the recursive part of a common table expression.
**
**   (3) The inner query has a LIMIT clause (since the changes to the WHERE
**       close would change the meaning of the LIMIT).
**

**   (4) The inner query is the right operand of a LEFT JOIN.  (The caller
**       enforces this restriction since this routine does not have enough
**       information to know.)
**
**   (5) The WHERE clause expression originates in the ON or USING clause
**       of a LEFT JOIN.










**
** Return 0 if no changes are made and non-zero if one or more WHERE clause
** terms are duplicated into the subquery.
*/
static int pushDownWhereTerms(
  Parse *pParse,        /* Parse context (for malloc() and error reporting) */
  Select *pSubq,        /* The subquery whose WHERE clause is to be augmented */







>
|
<
<


|
>
>
>
>
>
>
>
>
>
>







3853
3854
3855
3856
3857
3858
3859
3860
3861


3862
3863
3864
3865
3866
3867
3868
3869
3870
3871
3872
3873
3874
3875
3876
3877
3878
3879
3880
3881
**           to suppress it. **)
**
**   (2) The inner query is the recursive part of a common table expression.
**
**   (3) The inner query has a LIMIT clause (since the changes to the WHERE
**       close would change the meaning of the LIMIT).
**
**   (4) (** This restriction was removed on 2018-03-21.  It used to read:
**       The inner query is the right operand of a LEFT JOIN. **)


**
**   (5) The WHERE clause expression originates in the ON or USING clause
**       of a LEFT JOIN where iCursor is not the right-hand table of that
**       left join.  An example:
**
**           SELECT *
**           FROM (SELECT 1 AS a1 UNION ALL SELECT 2) AS aa
**           JOIN (SELECT 1 AS b2 UNION ALL SELECT 2) AS bb ON (a1=b2)
**           LEFT JOIN (SELECT 8 AS c3 UNION ALL SELECT 9) AS cc ON (b2=2);
**
**       The correct answer is three rows:  (1,1,NULL),(2,2,8),(2,2,9).
**       But if the (b2=2) term were to be pushed down into the bb subquery,
**       then the (1,1,NULL) row would be suppressed.
**
** Return 0 if no changes are made and non-zero if one or more WHERE clause
** terms are duplicated into the subquery.
*/
static int pushDownWhereTerms(
  Parse *pParse,        /* Parse context (for malloc() and error reporting) */
  Select *pSubq,        /* The subquery whose WHERE clause is to be augmented */
3893
3894
3895
3896
3897
3898
3899
3900


3901
3902
3903
3904
3905

3906
3907
3908
3909
3910
3911
3912
  if( pSubq->pLimit!=0 ){
    return 0; /* restriction (3) */
  }
  while( pWhere->op==TK_AND ){
    nChng += pushDownWhereTerms(pParse, pSubq, pWhere->pRight, iCursor);
    pWhere = pWhere->pLeft;
  }
  if( ExprHasProperty(pWhere,EP_FromJoin) ) return 0; /* restriction (5) */


  if( sqlite3ExprIsTableConstant(pWhere, iCursor) ){
    nChng++;
    while( pSubq ){
      SubstContext x;
      pNew = sqlite3ExprDup(pParse->db, pWhere, 0);

      x.pParse = pParse;
      x.iTable = iCursor;
      x.iNewTable = iCursor;
      x.isLeftJoin = 0;
      x.pEList = pSubq->pEList;
      pNew = substExpr(&x, pNew);
      if( pSubq->selFlags & SF_Aggregate ){







|
>
>





>







3903
3904
3905
3906
3907
3908
3909
3910
3911
3912
3913
3914
3915
3916
3917
3918
3919
3920
3921
3922
3923
3924
3925
  if( pSubq->pLimit!=0 ){
    return 0; /* restriction (3) */
  }
  while( pWhere->op==TK_AND ){
    nChng += pushDownWhereTerms(pParse, pSubq, pWhere->pRight, iCursor);
    pWhere = pWhere->pLeft;
  }
  if( ExprHasProperty(pWhere,EP_FromJoin) && pWhere->iRightJoinTable!=iCursor ){
    return 0; /* restriction (5) */
  }
  if( sqlite3ExprIsTableConstant(pWhere, iCursor) ){
    nChng++;
    while( pSubq ){
      SubstContext x;
      pNew = sqlite3ExprDup(pParse->db, pWhere, 0);
      unsetJoinExpr(pNew, -1);
      x.pParse = pParse;
      x.iTable = iCursor;
      x.iNewTable = iCursor;
      x.isLeftJoin = 0;
      x.pEList = pSubq->pEList;
      pNew = substExpr(&x, pNew);
      if( pSubq->selFlags & SF_Aggregate ){
5356
5357
5358
5359
5360
5361
5362
5363
5364
5365
5366
5367
5368
5369
5370
5371
    ** an exact limit.
    */
    pParse->nHeight += sqlite3SelectExprHeight(p);

    /* Make copies of constant WHERE-clause terms in the outer query down
    ** inside the subquery.  This can help the subquery to run more efficiently.
    */
    if( (pItem->fg.jointype & JT_OUTER)==0
     && OptimizationEnabled(db, SQLITE_PushDown)
     && pushDownWhereTerms(pParse, pSub, p->pWhere, pItem->iCursor)
    ){
#if SELECTTRACE_ENABLED
      if( sqlite3SelectTrace & 0x100 ){
        SELECTTRACE(0x100,pParse,p,("After WHERE-clause push-down:\n"));
        sqlite3TreeViewSelect(0, p, 0);
      }







<
|







5369
5370
5371
5372
5373
5374
5375

5376
5377
5378
5379
5380
5381
5382
5383
    ** an exact limit.
    */
    pParse->nHeight += sqlite3SelectExprHeight(p);

    /* Make copies of constant WHERE-clause terms in the outer query down
    ** inside the subquery.  This can help the subquery to run more efficiently.
    */

    if( OptimizationEnabled(db, SQLITE_PushDown)
     && pushDownWhereTerms(pParse, pSub, p->pWhere, pItem->iCursor)
    ){
#if SELECTTRACE_ENABLED
      if( sqlite3SelectTrace & 0x100 ){
        SELECTTRACE(0x100,pParse,p,("After WHERE-clause push-down:\n"));
        sqlite3TreeViewSelect(0, p, 0);
      }