/ Check-in [41c27bc0]
Login

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

Overview
Comment:Improved optimizations of views as the right operand of a LEFT JOIN.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: 41c27bc0ff1d3135cdb6273ede4595f5bb0c0e1e1d470ea1633cb525674cf431
User & Date: drh 2017-04-18 11:20:19
References
2017-07-29
03:26 New ticket [de3403bf] Column name shift due to LEFT JOIN query flattening. artifact: e6b7df69 user: drh
2017-06-20
16:15 New ticket [892fc34f] Incorrect query result when a LEFT JOIN subquery is flattened. artifact: d28d6544 user: drh
Context
2017-04-18
13:50
Use sqlite3_table_column_metadata() instead of a SELECT statement to check for the existence of a %_stat table in fts3. This leads to smaller and easier to test code. check-in: dc2a4802 user: dan tags: trunk
11:20
Improved optimizations of views as the right operand of a LEFT JOIN. check-in: 41c27bc0 user: drh tags: trunk
05:49
Refactor the fts3ColumnMethod() function so that all branches can be covered. check-in: e47fdb49 user: dan tags: trunk
2017-04-14
19:03
Add the TK_IF_NULL_ROW opcode to deal with non-NULL result columns in the result set of a view or subquery on the RHS of a LEFT JOIN that gets flattened. Closed-Leaf check-in: 3a5860d8 user: drh tags: left-join-view
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/expr.c.

  3884   3884         break;
  3885   3885       }
  3886   3886   
  3887   3887       case TK_VECTOR: {
  3888   3888         sqlite3ErrorMsg(pParse, "row value misused");
  3889   3889         break;
  3890   3890       }
         3891  +
         3892  +    case TK_IF_NULL_ROW: {
         3893  +      int addrINR;
         3894  +      addrINR = sqlite3VdbeAddOp1(v, OP_IfNullRow, pExpr->iTable);
         3895  +      sqlite3ExprCachePush(pParse);
         3896  +      inReg = sqlite3ExprCodeTarget(pParse, pExpr->pLeft, target);
         3897  +      sqlite3ExprCachePop(pParse);
         3898  +      sqlite3VdbeJumpHere(v, addrINR);
         3899  +      sqlite3VdbeChangeP3(v, addrINR, inReg);
         3900  +      break;
         3901  +    }
  3891   3902   
  3892   3903       /*
  3893   3904       ** Form A:
  3894   3905       **   CASE x WHEN e1 THEN r1 WHEN e2 THEN r2 ... WHEN eN THEN rN ELSE y END
  3895   3906       **
  3896   3907       ** Form B:
  3897   3908       **   CASE WHEN e1 THEN r1 WHEN e2 THEN r2 ... WHEN eN THEN rN ELSE y END

Changes to src/parse.y.

   188    188       A = 0;
   189    189       sqlite3ErrorMsg(pParse, "unknown table option: %.*s", X.n, X.z);
   190    190     }
   191    191   }
   192    192   columnlist ::= columnlist COMMA columnname carglist.
   193    193   columnlist ::= columnname carglist.
   194    194   columnname(A) ::= nm(A) typetoken(Y). {sqlite3AddColumn(pParse,&A,&Y);}
          195  +
          196  +// The following directive causes tokens ABORT, AFTER, ASC, etc. to
          197  +// fallback to ID if they will not parse as their original value.
          198  +// This obviates the need for the "id" nonterminal.
          199  +//
          200  +%fallback ID
          201  +  ABORT ACTION AFTER ANALYZE ASC ATTACH BEFORE BEGIN BY CASCADE CAST COLUMNKW
          202  +  CONFLICT DATABASE DEFERRED DESC DETACH EACH END EXCLUSIVE EXPLAIN FAIL FOR
          203  +  IGNORE IMMEDIATE INITIALLY INSTEAD LIKE_KW MATCH NO PLAN
          204  +  QUERY KEY OF OFFSET PRAGMA RAISE RECURSIVE RELEASE REPLACE RESTRICT ROW
          205  +  ROLLBACK SAVEPOINT TEMP TRIGGER VACUUM VIEW VIRTUAL WITH WITHOUT
          206  +%ifdef SQLITE_OMIT_COMPOUND_SELECT
          207  +  EXCEPT INTERSECT UNION
          208  +%endif SQLITE_OMIT_COMPOUND_SELECT
          209  +  REINDEX RENAME CTIME_KW IF
          210  +  .
          211  +%wildcard ANY.
   195    212   
   196    213   // Define operator precedence early so that this is the first occurrence
   197    214   // of the operator tokens in the grammer.  Keeping the operators together
   198    215   // causes them to be assigned integer values that are close together,
   199    216   // which keeps parser tables smaller.
   200    217   //
   201    218   // The token values assigned to these symbols is determined by the order
................................................................................
   218    235   %right BITNOT.
   219    236   
   220    237   // An IDENTIFIER can be a generic identifier, or one of several
   221    238   // keywords.  Any non-standard keyword can also be an identifier.
   222    239   //
   223    240   %token_class id  ID|INDEXED.
   224    241   
   225         -// The following directive causes tokens ABORT, AFTER, ASC, etc. to
   226         -// fallback to ID if they will not parse as their original value.
   227         -// This obviates the need for the "id" nonterminal.
   228         -//
   229         -%fallback ID
   230         -  ABORT ACTION AFTER ANALYZE ASC ATTACH BEFORE BEGIN BY CASCADE CAST COLUMNKW
   231         -  CONFLICT DATABASE DEFERRED DESC DETACH EACH END EXCLUSIVE EXPLAIN FAIL FOR
   232         -  IGNORE IMMEDIATE INITIALLY INSTEAD LIKE_KW MATCH NO PLAN
   233         -  QUERY KEY OF OFFSET PRAGMA RAISE RECURSIVE RELEASE REPLACE RESTRICT ROW
   234         -  ROLLBACK SAVEPOINT TEMP TRIGGER VACUUM VIEW VIRTUAL WITH WITHOUT
   235         -%ifdef SQLITE_OMIT_COMPOUND_SELECT
   236         -  EXCEPT INTERSECT UNION
   237         -%endif SQLITE_OMIT_COMPOUND_SELECT
   238         -  REINDEX RENAME CTIME_KW IF
   239         -  .
   240         -%wildcard ANY.
   241         -
   242    242   
   243    243   // And "ids" is an identifer-or-string.
   244    244   //
   245    245   %token_class ids  ID|STRING.
   246    246   
   247    247   // The name of a column or table can be any of the following:
   248    248   //

Changes to src/select.c.

  3150   3150   **
  3151   3151   ** All references to columns in table iTable are to be replaced by corresponding
  3152   3152   ** expressions in pEList.
  3153   3153   */
  3154   3154   typedef struct SubstContext {
  3155   3155     Parse *pParse;            /* The parsing context */
  3156   3156     int iTable;               /* Replace references to this table */
         3157  +  int iNewTable;            /* New table number */
         3158  +  int isLeftJoin;           /* Add TK_IF_NULL_ROW opcodes on each replacement */
  3157   3159     ExprList *pEList;         /* Replacement expressions */
  3158   3160   } SubstContext;
  3159   3161   
  3160   3162   /* Forward Declarations */
  3161   3163   static void substExprList(SubstContext*, ExprList*);
  3162   3164   static void substSelect(SubstContext*, Select*, int);
  3163   3165   
................................................................................
  3175   3177   ** of the subquery rather the result set of the subquery.
  3176   3178   */
  3177   3179   static Expr *substExpr(
  3178   3180     SubstContext *pSubst,  /* Description of the substitution */
  3179   3181     Expr *pExpr            /* Expr in which substitution occurs */
  3180   3182   ){
  3181   3183     if( pExpr==0 ) return 0;
         3184  +  if( ExprHasProperty(pExpr, EP_FromJoin) && pExpr->iRightJoinTable==pSubst->iTable ){
         3185  +    pExpr->iRightJoinTable = pSubst->iNewTable;
         3186  +  }
  3182   3187     if( pExpr->op==TK_COLUMN && pExpr->iTable==pSubst->iTable ){
  3183   3188       if( pExpr->iColumn<0 ){
  3184   3189         pExpr->op = TK_NULL;
  3185   3190       }else{
  3186   3191         Expr *pNew;
  3187   3192         Expr *pCopy = pSubst->pEList->a[pExpr->iColumn].pExpr;
         3193  +      Expr ifNullRow;
  3188   3194         assert( pSubst->pEList!=0 && pExpr->iColumn<pSubst->pEList->nExpr );
  3189   3195         assert( pExpr->pLeft==0 && pExpr->pRight==0 );
  3190   3196         if( sqlite3ExprIsVector(pCopy) ){
  3191   3197           sqlite3VectorErrorMsg(pSubst->pParse, pCopy);
  3192   3198         }else{
  3193   3199           sqlite3 *db = pSubst->pParse->db;
         3200  +        if( pSubst->isLeftJoin && pCopy->op!=TK_COLUMN ){
         3201  +          memset(&ifNullRow, 0, sizeof(ifNullRow));
         3202  +          ifNullRow.op = TK_IF_NULL_ROW;
         3203  +          ifNullRow.pLeft = pCopy;
         3204  +          ifNullRow.iTable = pSubst->iNewTable;
         3205  +          pCopy = &ifNullRow;
         3206  +        }
  3194   3207           pNew = sqlite3ExprDup(db, pCopy, 0);
  3195   3208           if( pNew && (pExpr->flags & EP_FromJoin) ){
  3196   3209             pNew->iRightJoinTable = pExpr->iRightJoinTable;
  3197   3210             pNew->flags |= EP_FromJoin;
  3198   3211           }
  3199   3212           sqlite3ExprDelete(db, pExpr);
  3200   3213           pExpr = pNew;
................................................................................
  3280   3293   **   (1)  The subquery and the outer query do not both use aggregates.
  3281   3294   **
  3282   3295   **   (2)  The subquery is not an aggregate or (2a) the outer query is not a join
  3283   3296   **        and (2b) the outer query does not use subqueries other than the one
  3284   3297   **        FROM-clause subquery that is a candidate for flattening.  (2b is
  3285   3298   **        due to ticket [2f7170d73bf9abf80] from 2015-02-09.)
  3286   3299   **
  3287         -**   (3)  The subquery is not the right operand of a left outer join
  3288         -**        (Originally ticket #306.  Strengthened by ticket #3300)
         3300  +**   (3)  The subquery is not the right operand of a LEFT JOIN
         3301  +**        or the subquery is not itself a join.
  3289   3302   **
  3290   3303   **   (4)  The subquery is not DISTINCT.
  3291   3304   **
  3292   3305   **  (**)  At one point restrictions (4) and (5) defined a subset of DISTINCT
  3293   3306   **        sub-queries that were excluded from this optimization. Restriction 
  3294   3307   **        (4) has since been expanded to exclude all DISTINCT subqueries.
  3295   3308   **
  3296   3309   **   (6)  The subquery does not use aggregates or the outer query is not
  3297   3310   **        DISTINCT.
  3298   3311   **
  3299   3312   **   (7)  The subquery has a FROM clause.  TODO:  For subqueries without
  3300         -**        A FROM clause, consider adding a FROM close with the special
         3313  +**        A FROM clause, consider adding a FROM clause with the special
  3301   3314   **        table sqlite_once that consists of a single row containing a
  3302   3315   **        single NULL.
  3303   3316   **
  3304   3317   **   (8)  The subquery does not use LIMIT or the outer query is not a join.
  3305   3318   **
  3306   3319   **   (9)  The subquery does not use LIMIT or the outer query does not use
  3307   3320   **        aggregates.
................................................................................
  3399   3412     Select *pParent;    /* Current UNION ALL term of the other query */
  3400   3413     Select *pSub;       /* The inner query or "subquery" */
  3401   3414     Select *pSub1;      /* Pointer to the rightmost select in sub-query */
  3402   3415     SrcList *pSrc;      /* The FROM clause of the outer query */
  3403   3416     SrcList *pSubSrc;   /* The FROM clause of the subquery */
  3404   3417     ExprList *pList;    /* The result set of the outer query */
  3405   3418     int iParent;        /* VDBE cursor number of the pSub result set temp table */
         3419  +  int iNewParent = -1;/* Replacement table for iParent */
         3420  +  int isLeftJoin = 0; /* True if pSub is the right side of a LEFT JOIN */    
  3406   3421     int i;              /* Loop counter */
  3407   3422     Expr *pWhere;                    /* The WHERE clause */
  3408   3423     struct SrcList_item *pSubitem;   /* The subquery */
  3409   3424     sqlite3 *db = pParse->db;
  3410   3425   
  3411   3426     /* Check to see if flattening is permitted.  Return 0 if not.
  3412   3427     */
................................................................................
  3425   3440       if( (p->pWhere && ExprHasProperty(p->pWhere,EP_Subquery))
  3426   3441        || (sqlite3ExprListFlags(p->pEList) & EP_Subquery)!=0
  3427   3442        || (sqlite3ExprListFlags(p->pOrderBy) & EP_Subquery)!=0
  3428   3443       ){
  3429   3444         return 0;                                          /* Restriction (2b)  */
  3430   3445       }
  3431   3446     }
  3432         -    
         3447  +
  3433   3448     pSubSrc = pSub->pSrc;
  3434   3449     assert( pSubSrc );
  3435   3450     /* Prior to version 3.1.2, when LIMIT and OFFSET had to be simple constants,
  3436   3451     ** not arbitrary expressions, we allowed some combining of LIMIT and OFFSET
  3437   3452     ** because they could be computed at compile-time.  But when LIMIT and OFFSET
  3438   3453     ** became arbitrary expressions, we were forced to add restrictions (13)
  3439   3454     ** and (14). */
................................................................................
  3463   3478     if( pSub->selFlags & (SF_Recursive|SF_MinMaxAgg) ){
  3464   3479       return 0; /* Restrictions (22) and (24) */
  3465   3480     }
  3466   3481     if( (p->selFlags & SF_Recursive) && pSub->pPrior ){
  3467   3482       return 0; /* Restriction (23) */
  3468   3483     }
  3469   3484   
  3470         -  /* OBSOLETE COMMENT 1:
  3471         -  ** Restriction 3:  If the subquery is a join, make sure the subquery is 
  3472         -  ** not used as the right operand of an outer join.  Examples of why this
  3473         -  ** is not allowed:
         3485  +  /*
         3486  +  ** If the subquery is the right operand of a LEFT JOIN, then the
         3487  +  ** subquery may not be a join itself.  Example of why this is not allowed:
  3474   3488     **
  3475   3489     **         t1 LEFT OUTER JOIN (t2 JOIN t3)
  3476   3490     **
  3477   3491     ** If we flatten the above, we would get
  3478   3492     **
  3479   3493     **         (t1 LEFT OUTER JOIN t2) JOIN t3
  3480   3494     **
  3481   3495     ** which is not at all the same thing.
  3482   3496     **
  3483         -  ** OBSOLETE COMMENT 2:
  3484         -  ** Restriction 12:  If the subquery is the right operand of a left outer
  3485         -  ** join, make sure the subquery has no WHERE clause.
  3486         -  ** An examples of why this is not allowed:
  3487         -  **
  3488         -  **         t1 LEFT OUTER JOIN (SELECT * FROM t2 WHERE t2.x>0)
  3489         -  **
  3490         -  ** If we flatten the above, we would get
  3491         -  **
  3492         -  **         (t1 LEFT OUTER JOIN t2) WHERE t2.x>0
  3493         -  **
  3494         -  ** But the t2.x>0 test will always fail on a NULL row of t2, which
  3495         -  ** effectively converts the OUTER JOIN into an INNER JOIN.
  3496         -  **
  3497         -  ** THIS OVERRIDES OBSOLETE COMMENTS 1 AND 2 ABOVE:
  3498         -  ** Ticket #3300 shows that flattening the right term of a LEFT JOIN
  3499         -  ** is fraught with danger.  Best to avoid the whole thing.  If the
  3500         -  ** subquery is the right term of a LEFT JOIN, then do not flatten.
         3497  +  ** See also tickets #306, #350, and #3300.
  3501   3498     */
  3502   3499     if( (pSubitem->fg.jointype & JT_OUTER)!=0 ){
  3503         -    return 0;
         3500  +    isLeftJoin = 1;
         3501  +    if( pSubSrc->nSrc>1 ){
         3502  +      return 0; /* Restriction (3) */
         3503  +    }
  3504   3504     }
  3505   3505   
  3506   3506     /* Restriction 17: If the sub-query is a compound SELECT, then it must
  3507   3507     ** use only the UNION ALL operator. And none of the simple select queries
  3508   3508     ** that make up the compound SELECT are allowed to be aggregate or distinct
  3509   3509     ** queries.
  3510   3510     */
................................................................................
  3705   3705       /* Transfer the FROM clause terms from the subquery into the
  3706   3706       ** outer query.
  3707   3707       */
  3708   3708       for(i=0; i<nSubSrc; i++){
  3709   3709         sqlite3IdListDelete(db, pSrc->a[i+iFrom].pUsing);
  3710   3710         assert( pSrc->a[i+iFrom].fg.isTabFunc==0 );
  3711   3711         pSrc->a[i+iFrom] = pSubSrc->a[i];
         3712  +      iNewParent = pSubSrc->a[i].iCursor;
  3712   3713         memset(&pSubSrc->a[i], 0, sizeof(pSubSrc->a[i]));
  3713   3714       }
  3714   3715       pSrc->a[iFrom].fg.jointype = jointype;
  3715   3716     
  3716   3717       /* Now begin substituting subquery result set expressions for 
  3717   3718       ** references to the iParent in the outer query.
  3718   3719       ** 
................................................................................
  3750   3751         }
  3751   3752         assert( pParent->pOrderBy==0 );
  3752   3753         assert( pSub->pPrior==0 );
  3753   3754         pParent->pOrderBy = pOrderBy;
  3754   3755         pSub->pOrderBy = 0;
  3755   3756       }
  3756   3757       pWhere = sqlite3ExprDup(db, pSub->pWhere, 0);
         3758  +    if( isLeftJoin ){
         3759  +      setJoinExpr(pWhere, iNewParent);
         3760  +    }
  3757   3761       if( subqueryIsAgg ){
  3758   3762         assert( pParent->pHaving==0 );
  3759   3763         pParent->pHaving = pParent->pWhere;
  3760   3764         pParent->pWhere = pWhere;
  3761   3765         pParent->pHaving = sqlite3ExprAnd(db, 
  3762   3766             sqlite3ExprDup(db, pSub->pHaving, 0), pParent->pHaving
  3763   3767         );
................................................................................
  3766   3770       }else{
  3767   3771         pParent->pWhere = sqlite3ExprAnd(db, pWhere, pParent->pWhere);
  3768   3772       }
  3769   3773       if( db->mallocFailed==0 ){
  3770   3774         SubstContext x;
  3771   3775         x.pParse = pParse;
  3772   3776         x.iTable = iParent;
         3777  +      x.iNewTable = iNewParent;
         3778  +      x.isLeftJoin = isLeftJoin;
  3773   3779         x.pEList = pSub->pEList;
  3774   3780         substSelect(&x, pParent, 0);
  3775   3781       }
  3776   3782     
  3777   3783       /* The flattened query is distinct if either the inner or the
  3778   3784       ** outer query is distinct. 
  3779   3785       */
................................................................................
  3874   3880     if( sqlite3ExprIsTableConstant(pWhere, iCursor) ){
  3875   3881       nChng++;
  3876   3882       while( pSubq ){
  3877   3883         SubstContext x;
  3878   3884         pNew = sqlite3ExprDup(pParse->db, pWhere, 0);
  3879   3885         x.pParse = pParse;
  3880   3886         x.iTable = iCursor;
         3887  +      x.iNewTable = iCursor;
         3888  +      x.isLeftJoin = 0;
  3881   3889         x.pEList = pSubq->pEList;
  3882   3890         pNew = substExpr(&x, pNew);
  3883   3891         pSubq->pWhere = sqlite3ExprAnd(pParse->db, pSubq->pWhere, pNew);
  3884   3892         pSubq = pSubq->pPrior;
  3885   3893       }
  3886   3894     }
  3887   3895     return nChng;

Changes to src/treeview.c.

   465    465         sqlite3TreeViewBareExprList(pView, pExpr->x.pList, "VECTOR");
   466    466         break;
   467    467       }
   468    468       case TK_SELECT_COLUMN: {
   469    469         sqlite3TreeViewLine(pView, "SELECT-COLUMN %d", pExpr->iColumn);
   470    470         sqlite3TreeViewSelect(pView, pExpr->pLeft->x.pSelect, 0);
   471    471         break;
          472  +    }
          473  +    case TK_IF_NULL_ROW: {
          474  +      sqlite3TreeViewLine(pView, "IF-NULL-ROW %d", pExpr->iTable);
          475  +      sqlite3TreeViewExpr(pView, pExpr->pLeft, 0);
          476  +      break;
   472    477       }
   473    478       default: {
   474    479         sqlite3TreeViewLine(pView, "op=%d", pExpr->op);
   475    480         break;
   476    481       }
   477    482     }
   478    483     if( zBinOp ){

Changes to src/vdbe.c.

  2426   2426     pIn1 = &aMem[pOp->p1];
  2427   2427     VdbeBranchTaken( (pIn1->flags & MEM_Null)==0, 2);
  2428   2428     if( (pIn1->flags & MEM_Null)==0 ){
  2429   2429       goto jump_to_p2;
  2430   2430     }
  2431   2431     break;
  2432   2432   }
         2433  +
         2434  +/* Opcode: IfNullRow P1 P2 P3 * *
         2435  +** Synopsis: if P1.nullRow then r[P3]=NULL, goto P2
         2436  +**
         2437  +** Check the cursor P1 to see if it is currently pointing at a NULL row.
         2438  +** If it is, then set register P3 to NULL and jump immediately to P2.
         2439  +** If P1 is not on a NULL row, then fall through without making any
         2440  +** changes.
         2441  +*/
         2442  +case OP_IfNullRow: {         /* jump */
         2443  +  assert( pOp->p1>=0 && pOp->p1<p->nCursor );
         2444  +  if( p->apCsr[pOp->p1]->nullRow ){
         2445  +    sqlite3VdbeMemSetNull(aMem + pOp->p3);
         2446  +    goto jump_to_p2;
         2447  +  }
         2448  +  break;
         2449  +}
  2433   2450   
  2434   2451   /* Opcode: Column P1 P2 P3 P4 P5
  2435   2452   ** Synopsis: r[P3]=PX
  2436   2453   **
  2437   2454   ** Interpret the data that cursor P1 points to as a structure built using
  2438   2455   ** the MakeRecord instruction.  (See the MakeRecord opcode for additional
  2439   2456   ** information about the format of the data.)  Extract the P2-th column

Changes to src/where.c.

  5005   5005               pOp->p1 = pLevel->iIdxCur;
  5006   5006             }
  5007   5007             assert( (pLoop->wsFlags & WHERE_IDX_ONLY)==0 || x>=0 
  5008   5008                 || pWInfo->eOnePass );
  5009   5009           }else if( pOp->opcode==OP_Rowid ){
  5010   5010             pOp->p1 = pLevel->iIdxCur;
  5011   5011             pOp->opcode = OP_IdxRowid;
         5012  +        }else if( pOp->opcode==OP_IfNullRow ){
         5013  +          pOp->p1 = pLevel->iIdxCur;
  5012   5014           }
  5013   5015         }
  5014   5016       }
  5015   5017     }
  5016   5018   
  5017   5019     /* Final cleanup
  5018   5020     */
  5019   5021     pParse->nQueryLoop = pWInfo->savedNQueryLoop;
  5020   5022     whereInfoFree(db, pWInfo);
  5021   5023     return;
  5022   5024   }

Changes to tool/addopcodes.tcl.

    35     35     AGG_FUNCTION
    36     36     AGG_COLUMN
    37     37     UMINUS
    38     38     UPLUS
    39     39     REGISTER
    40     40     VECTOR
    41     41     SELECT_COLUMN
           42  +  IF_NULL_ROW
    42     43     ASTERISK
    43     44     SPAN
    44     45     SPACE
    45     46     ILLEGAL
    46     47   }
    47     48   if {[lrange $extras end-1 end]!="SPACE ILLEGAL"} {
    48     49     error "SPACE and ILLEGAL must be the last two token codes and they\