/ Check-in [8e07aa2a]
Login

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

Overview
Comment:Fill out an initial implementation of the sqlite3ExprImpliesExpr() function.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | partial-indices
Files: files | file ages | folders
SHA1: 8e07aa2ad5579aeb82174ce5bd432ddb9c058bc1
User & Date: drh 2013-08-01 13:04:46
Context
2013-08-01
15:09
More test cases and corresponding bug fixes. check-in: 0c8cfdfa user: drh tags: partial-indices
13:04
Fill out an initial implementation of the sqlite3ExprImpliesExpr() function. check-in: 8e07aa2a user: drh tags: partial-indices
12:21
Refactor internal function name sqlite3VdbeGetValue() to sqlite3VdbeGetBoundValue(). check-in: 81834c30 user: drh tags: partial-indices
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/expr.c.

  3794   3794   
  3795   3795   /*
  3796   3796   ** Do a deep comparison of two expression trees.  Return 0 if the two
  3797   3797   ** expressions are completely identical.  Return 1 if they differ only
  3798   3798   ** by a COLLATE operator at the top level.  Return 2 if there are differences
  3799   3799   ** other than the top-level COLLATE operator.
  3800   3800   **
         3801  +** If any subelement of pB has Expr.iTable==(-1) then it is allowed
         3802  +** to compare equal to an equivalent element in pA with Expr.iTable==iTab.
         3803  +**
  3801   3804   ** Sometimes this routine will return 2 even if the two expressions
  3802   3805   ** really are equivalent.  If we cannot prove that the expressions are
  3803   3806   ** identical, we return 2 just to be safe.  So if this routine
  3804   3807   ** returns 2, then you do not really know for certain if the two
  3805   3808   ** expressions are the same.  But if you get a 0 or 1 return, then you
  3806   3809   ** can be sure the expressions are the same.  In the places where
  3807   3810   ** this routine is used, it does not hurt to get an extra 2 - that
  3808   3811   ** just might result in some slightly slower code.  But returning
  3809   3812   ** an incorrect 0 or 1 could lead to a malfunction.
  3810   3813   */
  3811         -int sqlite3ExprCompare(Expr *pA, Expr *pB){
         3814  +int sqlite3ExprCompare(Expr *pA, Expr *pB, int iTab){
  3812   3815     if( pA==0||pB==0 ){
  3813   3816       return pB==pA ? 0 : 2;
  3814   3817     }
  3815   3818     assert( !ExprHasAnyProperty(pA, EP_TokenOnly|EP_Reduced) );
  3816   3819     assert( !ExprHasAnyProperty(pB, EP_TokenOnly|EP_Reduced) );
  3817   3820     if( ExprHasProperty(pA, EP_xIsSelect) || ExprHasProperty(pB, EP_xIsSelect) ){
  3818   3821       return 2;
  3819   3822     }
  3820   3823     if( (pA->flags & EP_Distinct)!=(pB->flags & EP_Distinct) ) return 2;
  3821   3824     if( pA->op!=pB->op ){
  3822         -    if( pA->op==TK_COLLATE && sqlite3ExprCompare(pA->pLeft, pB)<2 ){
         3825  +    if( pA->op==TK_COLLATE && sqlite3ExprCompare(pA->pLeft, pB, iTab)<2 ){
  3823   3826         return 1;
  3824   3827       }
  3825         -    if( pB->op==TK_COLLATE && sqlite3ExprCompare(pA, pB->pLeft)<2 ){
         3828  +    if( pB->op==TK_COLLATE && sqlite3ExprCompare(pA, pB->pLeft, iTab)<2 ){
  3826   3829         return 1;
  3827   3830       }
  3828   3831       return 2;
  3829   3832     }
  3830         -  if( sqlite3ExprCompare(pA->pLeft, pB->pLeft) ) return 2;
  3831         -  if( sqlite3ExprCompare(pA->pRight, pB->pRight) ) return 2;
  3832         -  if( sqlite3ExprListCompare(pA->x.pList, pB->x.pList) ) return 2;
  3833         -  if( pA->iTable!=pB->iTable || pA->iColumn!=pB->iColumn ) return 2;
         3833  +  if( sqlite3ExprCompare(pA->pLeft, pB->pLeft, iTab) ) return 2;
         3834  +  if( sqlite3ExprCompare(pA->pRight, pB->pRight, iTab) ) return 2;
         3835  +  if( sqlite3ExprListCompare(pA->x.pList, pB->x.pList, iTab) ) return 2;
         3836  +  if( pA->iColumn!=pB->iColumn ) return 2;
         3837  +  if( pA->iTable!=pB->iTable && (pA->iTable!=iTab || pB->iTable>=0) ) return 2;
  3834   3838     if( ExprHasProperty(pA, EP_IntValue) ){
  3835   3839       if( !ExprHasProperty(pB, EP_IntValue) || pA->u.iValue!=pB->u.iValue ){
  3836   3840         return 2;
  3837   3841       }
  3838   3842     }else if( pA->op!=TK_COLUMN && ALWAYS(pA->op!=TK_AGG_COLUMN) && pA->u.zToken){
  3839   3843       if( ExprHasProperty(pB, EP_IntValue) || NEVER(pB->u.zToken==0) ) return 2;
  3840   3844       if( strcmp(pA->u.zToken,pB->u.zToken)!=0 ){
................................................................................
  3844   3848     return 0;
  3845   3849   }
  3846   3850   
  3847   3851   /*
  3848   3852   ** Compare two ExprList objects.  Return 0 if they are identical and 
  3849   3853   ** non-zero if they differ in any way.
  3850   3854   **
         3855  +** If any subelement of pB has Expr.iTable==(-1) then it is allowed
         3856  +** to compare equal to an equivalent element in pA with Expr.iTable==iTab.
         3857  +**
  3851   3858   ** This routine might return non-zero for equivalent ExprLists.  The
  3852   3859   ** only consequence will be disabled optimizations.  But this routine
  3853   3860   ** must never return 0 if the two ExprList objects are different, or
  3854   3861   ** a malfunction will result.
  3855   3862   **
  3856   3863   ** Two NULL pointers are considered to be the same.  But a NULL pointer
  3857   3864   ** always differs from a non-NULL pointer.
  3858   3865   */
  3859         -int sqlite3ExprListCompare(ExprList *pA, ExprList *pB){
         3866  +int sqlite3ExprListCompare(ExprList *pA, ExprList *pB, int iTab){
  3860   3867     int i;
  3861   3868     if( pA==0 && pB==0 ) return 0;
  3862   3869     if( pA==0 || pB==0 ) return 1;
  3863   3870     if( pA->nExpr!=pB->nExpr ) return 1;
  3864   3871     for(i=0; i<pA->nExpr; i++){
  3865   3872       Expr *pExprA = pA->a[i].pExpr;
  3866   3873       Expr *pExprB = pB->a[i].pExpr;
  3867   3874       if( pA->a[i].sortOrder!=pB->a[i].sortOrder ) return 1;
  3868         -    if( sqlite3ExprCompare(pExprA, pExprB) ) return 1;
         3875  +    if( sqlite3ExprCompare(pExprA, pExprB, iTab) ) return 1;
  3869   3876     }
  3870   3877     return 0;
  3871   3878   }
  3872   3879   
  3873   3880   /*
  3874   3881   ** Return true if we can prove the pE2 will always be true if pE1 is
  3875   3882   ** true.  Return false if we cannot complete the proof or if pE2 might
  3876   3883   ** be false.  Examples:
  3877   3884   **
  3878         -**     pE1: x==5      pE2: x>0              Result: true
  3879         -**     pE1: x>0       pE2: x==5             Result: false
  3880         -**     pE1: x!=123    pE2: x IS NOT NULL    Result: true
         3885  +**     pE1: x==5       pE2: x==5             Result: true
         3886  +**     pE1: x>0        pE2: x==5             Result: false
         3887  +**     pE1: x=21       pE2: x=21 OR y=43     Result: true
         3888  +**     pE1: x!=123     pE2: x IS NOT NULL    Result: true
         3889  +**     pE1: x!=?1      pE2: x IS NOT NULL    Result: true
         3890  +**     pE1: x IS NULL  pE2: x IS NOT NULL    Result: false
         3891  +**     pE1: x IS ?2    pE2: x IS NOT NULL    Reuslt: false
  3881   3892   **
  3882   3893   ** When comparing TK_COLUMN nodes between pE1 and pE2, if pE2 has
  3883   3894   ** Expr.iTable<0 then assume a table number given by iTab.
  3884   3895   **
  3885   3896   ** When in doubt, return false.  Returning true might give a performance
  3886   3897   ** improvement.  Returning false might cause a performance reduction, but
  3887   3898   ** it will always give the correct answer and is hence always safe.
  3888   3899   */
  3889   3900   int sqlite3ExprImpliesExpr(Expr *pE1, Expr *pE2, int iTab){
  3890         -  return 0;  /* FIXME: this needs to be worked out */
         3901  +  if( sqlite3ExprCompare(pE1, pE2, iTab)==0 ){
         3902  +    return 1;
         3903  +  }
         3904  +  if( pE2->op==TK_OR
         3905  +   && (sqlite3ExprImpliesExpr(pE1, pE2->pLeft, iTab)
         3906  +             || sqlite3ExprImpliesExpr(pE1, pE2->pRight, iTab) )
         3907  +  ){
         3908  +    return 1;
         3909  +  }
         3910  +  if( pE2->op==TK_NOTNULL
         3911  +   && sqlite3ExprCompare(pE1->pLeft, pE2->pLeft, iTab)==0
         3912  +   && (pE1->op!=TK_ISNULL && pE1->op!=TK_IS)
         3913  +  ){
         3914  +    return 1;
         3915  +  }
         3916  +  return 0;
  3891   3917   }
  3892   3918   
  3893   3919   /*
  3894   3920   ** An instance of the following structure is used by the tree walker
  3895   3921   ** to count references to table columns in the arguments of an 
  3896   3922   ** aggregate function, in order to implement the
  3897   3923   ** sqlite3FunctionThisSrc() routine.
................................................................................
  4066   4092          && pWalker->walkerDepth==pExpr->op2
  4067   4093         ){
  4068   4094           /* Check to see if pExpr is a duplicate of another aggregate 
  4069   4095           ** function that is already in the pAggInfo structure
  4070   4096           */
  4071   4097           struct AggInfo_func *pItem = pAggInfo->aFunc;
  4072   4098           for(i=0; i<pAggInfo->nFunc; i++, pItem++){
  4073         -          if( sqlite3ExprCompare(pItem->pExpr, pExpr)==0 ){
         4099  +          if( sqlite3ExprCompare(pItem->pExpr, pExpr, -1)==0 ){
  4074   4100               break;
  4075   4101             }
  4076   4102           }
  4077   4103           if( i>=pAggInfo->nFunc ){
  4078   4104             /* pExpr is original.  Make a new entry in pAggInfo->aFunc[]
  4079   4105             */
  4080   4106             u8 enc = ENC(pParse->db);

Changes to src/insert.c.

  1644   1644       if( pSrc->aSortOrder[i]!=pDest->aSortOrder[i] ){
  1645   1645         return 0;   /* Different sort orders */
  1646   1646       }
  1647   1647       if( !xferCompatibleCollation(pSrc->azColl[i],pDest->azColl[i]) ){
  1648   1648         return 0;   /* Different collating sequences */
  1649   1649       }
  1650   1650     }
  1651         -  if( sqlite3ExprCompare(pSrc->pPartIdxWhere, pDest->pPartIdxWhere) ){
         1651  +  if( sqlite3ExprCompare(pSrc->pPartIdxWhere, pDest->pPartIdxWhere, -1) ){
  1652   1652       return 0;     /* Different WHERE clauses */
  1653   1653     }
  1654   1654   
  1655   1655     /* If no test above fails then the indices must be compatible */
  1656   1656     return 1;
  1657   1657   }
  1658   1658   
................................................................................
  1802   1802         if( xferCompatibleIndex(pDestIdx, pSrcIdx) ) break;
  1803   1803       }
  1804   1804       if( pSrcIdx==0 ){
  1805   1805         return 0;    /* pDestIdx has no corresponding index in pSrc */
  1806   1806       }
  1807   1807     }
  1808   1808   #ifndef SQLITE_OMIT_CHECK
  1809         -  if( pDest->pCheck && sqlite3ExprListCompare(pSrc->pCheck, pDest->pCheck) ){
         1809  +  if( pDest->pCheck && sqlite3ExprListCompare(pSrc->pCheck,pDest->pCheck,-1) ){
  1810   1810       return 0;   /* Tables have different CHECK constraints.  Ticket #2252 */
  1811   1811     }
  1812   1812   #endif
  1813   1813   #ifndef SQLITE_OMIT_FOREIGN_KEY
  1814   1814     /* Disallow the transfer optimization if the destination table constains
  1815   1815     ** any foreign key constraints.  This is more restrictive than necessary.
  1816   1816     ** But the main beneficiary of the transfer optimization is the VACUUM 

Changes to src/resolve.c.

   821    821     if( rc ) return 0;
   822    822   
   823    823     /* Try to match the ORDER BY expression against an expression
   824    824     ** in the result set.  Return an 1-based index of the matching
   825    825     ** result-set entry.
   826    826     */
   827    827     for(i=0; i<pEList->nExpr; i++){
   828         -    if( sqlite3ExprCompare(pEList->a[i].pExpr, pE)<2 ){
          828  +    if( sqlite3ExprCompare(pEList->a[i].pExpr, pE, -1)<2 ){
   829    829         return i+1;
   830    830       }
   831    831     }
   832    832   
   833    833     /* If no match, return 0. */
   834    834     return 0;
   835    835   }
................................................................................
  1049   1049   
  1050   1050       /* Otherwise, treat the ORDER BY term as an ordinary expression */
  1051   1051       pItem->iOrderByCol = 0;
  1052   1052       if( sqlite3ResolveExprNames(pNC, pE) ){
  1053   1053         return 1;
  1054   1054       }
  1055   1055       for(j=0; j<pSelect->pEList->nExpr; j++){
  1056         -      if( sqlite3ExprCompare(pE, pSelect->pEList->a[j].pExpr)==0 ){
         1056  +      if( sqlite3ExprCompare(pE, pSelect->pEList->a[j].pExpr, -1)==0 ){
  1057   1057           pItem->iOrderByCol = j+1;
  1058   1058         }
  1059   1059       }
  1060   1060     }
  1061   1061     return sqlite3ResolveOrderGroupBy(pParse, pSelect, pOrderBy, zType);
  1062   1062   }
  1063   1063   

Changes to src/select.c.

  4173   4173     /* If there is both a GROUP BY and an ORDER BY clause and they are
  4174   4174     ** identical, then disable the ORDER BY clause since the GROUP BY
  4175   4175     ** will cause elements to come out in the correct order.  This is
  4176   4176     ** an optimization - the correct answer should result regardless.
  4177   4177     ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER
  4178   4178     ** to disable this optimization for testing purposes.
  4179   4179     */
  4180         -  if( sqlite3ExprListCompare(p->pGroupBy, pOrderBy)==0
         4180  +  if( sqlite3ExprListCompare(p->pGroupBy, pOrderBy, -1)==0
  4181   4181            && OptimizationEnabled(db, SQLITE_GroupByOrder) ){
  4182   4182       pOrderBy = 0;
  4183   4183     }
  4184   4184   
  4185   4185     /* If the query is DISTINCT with an ORDER BY but is not an aggregate, and 
  4186   4186     ** if the select-list is the same as the ORDER BY list, then this query
  4187   4187     ** can be rewritten as a GROUP BY. In other words, this:
................................................................................
  4194   4194     **
  4195   4195     ** The second form is preferred as a single index (or temp-table) may be 
  4196   4196     ** used for both the ORDER BY and DISTINCT processing. As originally 
  4197   4197     ** written the query must use a temp-table for at least one of the ORDER 
  4198   4198     ** BY and DISTINCT, and an index or separate temp-table for the other.
  4199   4199     */
  4200   4200     if( (p->selFlags & (SF_Distinct|SF_Aggregate))==SF_Distinct 
  4201         -   && sqlite3ExprListCompare(pOrderBy, p->pEList)==0
         4201  +   && sqlite3ExprListCompare(pOrderBy, p->pEList, -1)==0
  4202   4202     ){
  4203   4203       p->selFlags &= ~SF_Distinct;
  4204   4204       p->pGroupBy = sqlite3ExprListDup(db, p->pEList, 0);
  4205   4205       pGroupBy = p->pGroupBy;
  4206   4206       pOrderBy = 0;
  4207   4207       /* Notice that even thought SF_Distinct has been cleared from p->selFlags,
  4208   4208       ** the sDistinct.isTnct is still set.  Hence, isTnct represents the

Changes to src/sqliteInt.h.

  2830   2830   Table *sqlite3LocateTableItem(Parse*,int isView,struct SrcList_item *);
  2831   2831   Index *sqlite3FindIndex(sqlite3*,const char*, const char*);
  2832   2832   void sqlite3UnlinkAndDeleteTable(sqlite3*,int,const char*);
  2833   2833   void sqlite3UnlinkAndDeleteIndex(sqlite3*,int,const char*);
  2834   2834   void sqlite3Vacuum(Parse*);
  2835   2835   int sqlite3RunVacuum(char**, sqlite3*);
  2836   2836   char *sqlite3NameFromToken(sqlite3*, Token*);
  2837         -int sqlite3ExprCompare(Expr*, Expr*);
  2838         -int sqlite3ExprListCompare(ExprList*, ExprList*);
         2837  +int sqlite3ExprCompare(Expr*, Expr*, int);
         2838  +int sqlite3ExprListCompare(ExprList*, ExprList*, int);
  2839   2839   int sqlite3ExprImpliesExpr(Expr*, Expr*, int);
  2840   2840   void sqlite3ExprAnalyzeAggregates(NameContext*, Expr*);
  2841   2841   void sqlite3ExprAnalyzeAggList(NameContext*,ExprList*);
  2842   2842   int sqlite3FunctionUsesThisSrc(Expr*, SrcList*);
  2843   2843   Vdbe *sqlite3GetVdbe(Parse*);
  2844   2844   void sqlite3PrngSaveState(void);
  2845   2845   void sqlite3PrngRestoreState(void);