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 |
Timelines: | family | ancestors | descendants | both | partial-indices |
Files: | files | file ages | folders |
SHA1: |
8e07aa2ad5579aeb82174ce5bd432ddb |
User & Date: | drh 2013-08-01 13:04:46.842 |
Context
2013-08-01
| ||
15:09 | More test cases and corresponding bug fixes. (check-in: 0c8cfdfae2 user: drh tags: partial-indices) | |
13:04 | Fill out an initial implementation of the sqlite3ExprImpliesExpr() function. (check-in: 8e07aa2ad5 user: drh tags: partial-indices) | |
12:21 | Refactor internal function name sqlite3VdbeGetValue() to sqlite3VdbeGetBoundValue(). (check-in: 81834c3023 user: drh tags: partial-indices) | |
Changes
Changes to src/expr.c.
︙ | ︙ | |||
3794 3795 3796 3797 3798 3799 3800 3801 3802 3803 3804 3805 3806 3807 3808 3809 3810 | /* ** Do a deep comparison of two expression trees. Return 0 if the two ** expressions are completely identical. Return 1 if they differ only ** by a COLLATE operator at the top level. Return 2 if there are differences ** other than the top-level COLLATE operator. ** ** Sometimes this routine will return 2 even if the two expressions ** really are equivalent. If we cannot prove that the expressions are ** identical, we return 2 just to be safe. So if this routine ** returns 2, then you do not really know for certain if the two ** expressions are the same. But if you get a 0 or 1 return, then you ** can be sure the expressions are the same. In the places where ** this routine is used, it does not hurt to get an extra 2 - that ** just might result in some slightly slower code. But returning ** an incorrect 0 or 1 could lead to a malfunction. */ | > > > | | | | | | | > > > > | | | | > > | > > > > > > > > > > > > > > > > > | | 3794 3795 3796 3797 3798 3799 3800 3801 3802 3803 3804 3805 3806 3807 3808 3809 3810 3811 3812 3813 3814 3815 3816 3817 3818 3819 3820 3821 3822 3823 3824 3825 3826 3827 3828 3829 3830 3831 3832 3833 3834 3835 3836 3837 3838 3839 3840 3841 3842 3843 3844 3845 3846 3847 3848 3849 3850 3851 3852 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 3882 3883 3884 3885 3886 3887 3888 3889 3890 3891 3892 3893 3894 3895 3896 3897 3898 3899 3900 3901 3902 3903 3904 3905 3906 3907 3908 3909 3910 3911 3912 3913 3914 3915 3916 3917 3918 3919 3920 3921 3922 3923 | /* ** Do a deep comparison of two expression trees. Return 0 if the two ** expressions are completely identical. Return 1 if they differ only ** by a COLLATE operator at the top level. Return 2 if there are differences ** other than the top-level COLLATE operator. ** ** If any subelement of pB has Expr.iTable==(-1) then it is allowed ** to compare equal to an equivalent element in pA with Expr.iTable==iTab. ** ** Sometimes this routine will return 2 even if the two expressions ** really are equivalent. If we cannot prove that the expressions are ** identical, we return 2 just to be safe. So if this routine ** returns 2, then you do not really know for certain if the two ** expressions are the same. But if you get a 0 or 1 return, then you ** can be sure the expressions are the same. In the places where ** this routine is used, it does not hurt to get an extra 2 - that ** just might result in some slightly slower code. But returning ** an incorrect 0 or 1 could lead to a malfunction. */ int sqlite3ExprCompare(Expr *pA, Expr *pB, int iTab){ if( pA==0||pB==0 ){ return pB==pA ? 0 : 2; } assert( !ExprHasAnyProperty(pA, EP_TokenOnly|EP_Reduced) ); assert( !ExprHasAnyProperty(pB, EP_TokenOnly|EP_Reduced) ); if( ExprHasProperty(pA, EP_xIsSelect) || ExprHasProperty(pB, EP_xIsSelect) ){ return 2; } if( (pA->flags & EP_Distinct)!=(pB->flags & EP_Distinct) ) return 2; if( pA->op!=pB->op ){ if( pA->op==TK_COLLATE && sqlite3ExprCompare(pA->pLeft, pB, iTab)<2 ){ return 1; } if( pB->op==TK_COLLATE && sqlite3ExprCompare(pA, pB->pLeft, iTab)<2 ){ return 1; } return 2; } if( sqlite3ExprCompare(pA->pLeft, pB->pLeft, iTab) ) return 2; if( sqlite3ExprCompare(pA->pRight, pB->pRight, iTab) ) return 2; if( sqlite3ExprListCompare(pA->x.pList, pB->x.pList, iTab) ) return 2; if( pA->iColumn!=pB->iColumn ) return 2; if( pA->iTable!=pB->iTable && (pA->iTable!=iTab || pB->iTable>=0) ) return 2; if( ExprHasProperty(pA, EP_IntValue) ){ if( !ExprHasProperty(pB, EP_IntValue) || pA->u.iValue!=pB->u.iValue ){ return 2; } }else if( pA->op!=TK_COLUMN && ALWAYS(pA->op!=TK_AGG_COLUMN) && pA->u.zToken){ if( ExprHasProperty(pB, EP_IntValue) || NEVER(pB->u.zToken==0) ) return 2; if( strcmp(pA->u.zToken,pB->u.zToken)!=0 ){ return pA->op==TK_COLLATE ? 1 : 2; } } return 0; } /* ** Compare two ExprList objects. Return 0 if they are identical and ** non-zero if they differ in any way. ** ** If any subelement of pB has Expr.iTable==(-1) then it is allowed ** to compare equal to an equivalent element in pA with Expr.iTable==iTab. ** ** This routine might return non-zero for equivalent ExprLists. The ** only consequence will be disabled optimizations. But this routine ** must never return 0 if the two ExprList objects are different, or ** a malfunction will result. ** ** Two NULL pointers are considered to be the same. But a NULL pointer ** always differs from a non-NULL pointer. */ int sqlite3ExprListCompare(ExprList *pA, ExprList *pB, int iTab){ int i; if( pA==0 && pB==0 ) return 0; if( pA==0 || pB==0 ) return 1; if( pA->nExpr!=pB->nExpr ) return 1; for(i=0; i<pA->nExpr; i++){ Expr *pExprA = pA->a[i].pExpr; Expr *pExprB = pB->a[i].pExpr; if( pA->a[i].sortOrder!=pB->a[i].sortOrder ) return 1; if( sqlite3ExprCompare(pExprA, pExprB, iTab) ) return 1; } return 0; } /* ** Return true if we can prove the pE2 will always be true if pE1 is ** true. Return false if we cannot complete the proof or if pE2 might ** be false. Examples: ** ** pE1: x==5 pE2: x==5 Result: true ** pE1: x>0 pE2: x==5 Result: false ** pE1: x=21 pE2: x=21 OR y=43 Result: true ** pE1: x!=123 pE2: x IS NOT NULL Result: true ** pE1: x!=?1 pE2: x IS NOT NULL Result: true ** pE1: x IS NULL pE2: x IS NOT NULL Result: false ** pE1: x IS ?2 pE2: x IS NOT NULL Reuslt: false ** ** When comparing TK_COLUMN nodes between pE1 and pE2, if pE2 has ** Expr.iTable<0 then assume a table number given by iTab. ** ** When in doubt, return false. Returning true might give a performance ** improvement. Returning false might cause a performance reduction, but ** it will always give the correct answer and is hence always safe. */ int sqlite3ExprImpliesExpr(Expr *pE1, Expr *pE2, int iTab){ if( sqlite3ExprCompare(pE1, pE2, iTab)==0 ){ return 1; } if( pE2->op==TK_OR && (sqlite3ExprImpliesExpr(pE1, pE2->pLeft, iTab) || sqlite3ExprImpliesExpr(pE1, pE2->pRight, iTab) ) ){ return 1; } if( pE2->op==TK_NOTNULL && sqlite3ExprCompare(pE1->pLeft, pE2->pLeft, iTab)==0 && (pE1->op!=TK_ISNULL && pE1->op!=TK_IS) ){ return 1; } return 0; } /* ** An instance of the following structure is used by the tree walker ** to count references to table columns in the arguments of an ** aggregate function, in order to implement the ** sqlite3FunctionThisSrc() routine. |
︙ | ︙ | |||
4066 4067 4068 4069 4070 4071 4072 | && pWalker->walkerDepth==pExpr->op2 ){ /* Check to see if pExpr is a duplicate of another aggregate ** function that is already in the pAggInfo structure */ struct AggInfo_func *pItem = pAggInfo->aFunc; for(i=0; i<pAggInfo->nFunc; i++, pItem++){ | | | 4092 4093 4094 4095 4096 4097 4098 4099 4100 4101 4102 4103 4104 4105 4106 | && pWalker->walkerDepth==pExpr->op2 ){ /* Check to see if pExpr is a duplicate of another aggregate ** function that is already in the pAggInfo structure */ struct AggInfo_func *pItem = pAggInfo->aFunc; for(i=0; i<pAggInfo->nFunc; i++, pItem++){ if( sqlite3ExprCompare(pItem->pExpr, pExpr, -1)==0 ){ break; } } if( i>=pAggInfo->nFunc ){ /* pExpr is original. Make a new entry in pAggInfo->aFunc[] */ u8 enc = ENC(pParse->db); |
︙ | ︙ |
Changes to src/insert.c.
︙ | ︙ | |||
1644 1645 1646 1647 1648 1649 1650 | if( pSrc->aSortOrder[i]!=pDest->aSortOrder[i] ){ return 0; /* Different sort orders */ } if( !xferCompatibleCollation(pSrc->azColl[i],pDest->azColl[i]) ){ return 0; /* Different collating sequences */ } } | | | 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 | if( pSrc->aSortOrder[i]!=pDest->aSortOrder[i] ){ return 0; /* Different sort orders */ } if( !xferCompatibleCollation(pSrc->azColl[i],pDest->azColl[i]) ){ return 0; /* Different collating sequences */ } } if( sqlite3ExprCompare(pSrc->pPartIdxWhere, pDest->pPartIdxWhere, -1) ){ return 0; /* Different WHERE clauses */ } /* If no test above fails then the indices must be compatible */ return 1; } |
︙ | ︙ | |||
1802 1803 1804 1805 1806 1807 1808 | if( xferCompatibleIndex(pDestIdx, pSrcIdx) ) break; } if( pSrcIdx==0 ){ return 0; /* pDestIdx has no corresponding index in pSrc */ } } #ifndef SQLITE_OMIT_CHECK | | | 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 | if( xferCompatibleIndex(pDestIdx, pSrcIdx) ) break; } if( pSrcIdx==0 ){ return 0; /* pDestIdx has no corresponding index in pSrc */ } } #ifndef SQLITE_OMIT_CHECK if( pDest->pCheck && sqlite3ExprListCompare(pSrc->pCheck,pDest->pCheck,-1) ){ return 0; /* Tables have different CHECK constraints. Ticket #2252 */ } #endif #ifndef SQLITE_OMIT_FOREIGN_KEY /* Disallow the transfer optimization if the destination table constains ** any foreign key constraints. This is more restrictive than necessary. ** But the main beneficiary of the transfer optimization is the VACUUM |
︙ | ︙ |
Changes to src/resolve.c.
︙ | ︙ | |||
821 822 823 824 825 826 827 | if( rc ) return 0; /* Try to match the ORDER BY expression against an expression ** in the result set. Return an 1-based index of the matching ** result-set entry. */ for(i=0; i<pEList->nExpr; i++){ | | | 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 | if( rc ) return 0; /* Try to match the ORDER BY expression against an expression ** in the result set. Return an 1-based index of the matching ** result-set entry. */ for(i=0; i<pEList->nExpr; i++){ if( sqlite3ExprCompare(pEList->a[i].pExpr, pE, -1)<2 ){ return i+1; } } /* If no match, return 0. */ return 0; } |
︙ | ︙ | |||
1049 1050 1051 1052 1053 1054 1055 | /* Otherwise, treat the ORDER BY term as an ordinary expression */ pItem->iOrderByCol = 0; if( sqlite3ResolveExprNames(pNC, pE) ){ return 1; } for(j=0; j<pSelect->pEList->nExpr; j++){ | | | 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 | /* Otherwise, treat the ORDER BY term as an ordinary expression */ pItem->iOrderByCol = 0; if( sqlite3ResolveExprNames(pNC, pE) ){ return 1; } for(j=0; j<pSelect->pEList->nExpr; j++){ if( sqlite3ExprCompare(pE, pSelect->pEList->a[j].pExpr, -1)==0 ){ pItem->iOrderByCol = j+1; } } } return sqlite3ResolveOrderGroupBy(pParse, pSelect, pOrderBy, zType); } |
︙ | ︙ |
Changes to src/select.c.
︙ | ︙ | |||
4173 4174 4175 4176 4177 4178 4179 | /* If there is both a GROUP BY and an ORDER BY clause and they are ** identical, then disable the ORDER BY clause since the GROUP BY ** will cause elements to come out in the correct order. This is ** an optimization - the correct answer should result regardless. ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER ** to disable this optimization for testing purposes. */ | | | | 4173 4174 4175 4176 4177 4178 4179 4180 4181 4182 4183 4184 4185 4186 4187 4188 4189 4190 4191 4192 4193 4194 4195 4196 4197 4198 4199 4200 4201 4202 4203 4204 4205 4206 4207 4208 | /* If there is both a GROUP BY and an ORDER BY clause and they are ** identical, then disable the ORDER BY clause since the GROUP BY ** will cause elements to come out in the correct order. This is ** an optimization - the correct answer should result regardless. ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER ** to disable this optimization for testing purposes. */ if( sqlite3ExprListCompare(p->pGroupBy, pOrderBy, -1)==0 && OptimizationEnabled(db, SQLITE_GroupByOrder) ){ pOrderBy = 0; } /* If the query is DISTINCT with an ORDER BY but is not an aggregate, and ** if the select-list is the same as the ORDER BY list, then this query ** can be rewritten as a GROUP BY. In other words, this: ** ** SELECT DISTINCT xyz FROM ... ORDER BY xyz ** ** is transformed to: ** ** SELECT xyz FROM ... GROUP BY xyz ** ** The second form is preferred as a single index (or temp-table) may be ** used for both the ORDER BY and DISTINCT processing. As originally ** written the query must use a temp-table for at least one of the ORDER ** BY and DISTINCT, and an index or separate temp-table for the other. */ if( (p->selFlags & (SF_Distinct|SF_Aggregate))==SF_Distinct && sqlite3ExprListCompare(pOrderBy, p->pEList, -1)==0 ){ p->selFlags &= ~SF_Distinct; p->pGroupBy = sqlite3ExprListDup(db, p->pEList, 0); pGroupBy = p->pGroupBy; pOrderBy = 0; /* Notice that even thought SF_Distinct has been cleared from p->selFlags, ** the sDistinct.isTnct is still set. Hence, isTnct represents the |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
2830 2831 2832 2833 2834 2835 2836 | Table *sqlite3LocateTableItem(Parse*,int isView,struct SrcList_item *); Index *sqlite3FindIndex(sqlite3*,const char*, const char*); void sqlite3UnlinkAndDeleteTable(sqlite3*,int,const char*); void sqlite3UnlinkAndDeleteIndex(sqlite3*,int,const char*); void sqlite3Vacuum(Parse*); int sqlite3RunVacuum(char**, sqlite3*); char *sqlite3NameFromToken(sqlite3*, Token*); | | | | 2830 2831 2832 2833 2834 2835 2836 2837 2838 2839 2840 2841 2842 2843 2844 2845 | Table *sqlite3LocateTableItem(Parse*,int isView,struct SrcList_item *); Index *sqlite3FindIndex(sqlite3*,const char*, const char*); void sqlite3UnlinkAndDeleteTable(sqlite3*,int,const char*); void sqlite3UnlinkAndDeleteIndex(sqlite3*,int,const char*); void sqlite3Vacuum(Parse*); int sqlite3RunVacuum(char**, sqlite3*); char *sqlite3NameFromToken(sqlite3*, Token*); int sqlite3ExprCompare(Expr*, Expr*, int); int sqlite3ExprListCompare(ExprList*, ExprList*, int); int sqlite3ExprImpliesExpr(Expr*, Expr*, int); void sqlite3ExprAnalyzeAggregates(NameContext*, Expr*); void sqlite3ExprAnalyzeAggList(NameContext*,ExprList*); int sqlite3FunctionUsesThisSrc(Expr*, SrcList*); Vdbe *sqlite3GetVdbe(Parse*); void sqlite3PrngSaveState(void); void sqlite3PrngRestoreState(void); |
︙ | ︙ |