Overview
| SHA1 Hash: | 38852f158ab20bb4d7b264af987ec1538052bec3 |
|---|---|
| Date: | 2013-01-17 17:20:49 |
| User: | drh |
| Comment: | Enhance the query planner to exploit transitivity of join constraints. |
Tags And Properties
- branch=trunk inherited from [704b122e53]
- sym-trunk inherited from [704b122e53]
Changes
Changes to src/sqliteInt.h
571 571 572 /* 572 /* 573 ** A convenience macro that returns the number of elements in 573 ** A convenience macro that returns the number of elements in 574 ** an array. 574 ** an array. 575 */ 575 */ 576 #define ArraySize(X) ((int)(sizeof(X)/sizeof(X[0]))) 576 #define ArraySize(X) ((int)(sizeof(X)/sizeof(X[0]))) 577 577 > 578 /* > 579 ** Determine if the argument is a power of two > 580 */ > 581 #define IsPowerOfTwo(X) (((X)&((X)-1))==0) > 582 578 /* 583 /* 579 ** The following value as a destructor means to use sqlite3DbFree(). 584 ** The following value as a destructor means to use sqlite3DbFree(). 580 ** The sqlite3DbFree() routine requires two parameters instead of the 585 ** The sqlite3DbFree() routine requires two parameters instead of the 581 ** one parameter that destructors normally want. So we have to introduce 586 ** one parameter that destructors normally want. So we have to introduce 582 ** this magic value that the code knows to handle differently. Any 587 ** this magic value that the code knows to handle differently. Any 583 ** pointer will work here as long as it is distinct from SQLITE_STATIC 588 ** pointer will work here as long as it is distinct from SQLITE_STATIC 584 ** and SQLITE_TRANSIENT. 589 ** and SQLITE_TRANSIENT. ................................................................................................................................................................................ 969 #define SQLITE_GroupByOrder 0x0004 /* GROUPBY cover of ORDERBY */ 974 #define SQLITE_GroupByOrder 0x0004 /* GROUPBY cover of ORDERBY */ 970 #define SQLITE_FactorOutConst 0x0008 /* Constant factoring */ 975 #define SQLITE_FactorOutConst 0x0008 /* Constant factoring */ 971 #define SQLITE_IdxRealAsInt 0x0010 /* Store REAL as INT in indices */ 976 #define SQLITE_IdxRealAsInt 0x0010 /* Store REAL as INT in indices */ 972 #define SQLITE_DistinctOpt 0x0020 /* DISTINCT using indexes */ 977 #define SQLITE_DistinctOpt 0x0020 /* DISTINCT using indexes */ 973 #define SQLITE_CoverIdxScan 0x0040 /* Covering index scans */ 978 #define SQLITE_CoverIdxScan 0x0040 /* Covering index scans */ 974 #define SQLITE_OrderByIdxJoin 0x0080 /* ORDER BY of joins via index */ 979 #define SQLITE_OrderByIdxJoin 0x0080 /* ORDER BY of joins via index */ 975 #define SQLITE_SubqCoroutine 0x0100 /* Evaluate subqueries as coroutines */ 980 #define SQLITE_SubqCoroutine 0x0100 /* Evaluate subqueries as coroutines */ > 981 #define SQLITE_Transitive 0x0200 /* Transitive constraints */ 976 #define SQLITE_AllOpts 0xffff /* All optimizations */ 982 #define SQLITE_AllOpts 0xffff /* All optimizations */ 977 983 978 /* 984 /* 979 ** Macros for testing whether or not optimizations are enabled or disabled. 985 ** Macros for testing whether or not optimizations are enabled or disabled. 980 */ 986 */ 981 #ifndef SQLITE_OMIT_BUILTIN_TEST 987 #ifndef SQLITE_OMIT_BUILTIN_TEST 982 #define OptimizationDisabled(db, mask) (((db)->dbOptFlags&(mask))!=0) 988 #define OptimizationDisabled(db, mask) (((db)->dbOptFlags&(mask))!=0)
Changes to src/where.c
94 typedef struct WhereTerm WhereTerm; 94 typedef struct WhereTerm WhereTerm; 95 struct WhereTerm { 95 struct WhereTerm { 96 Expr *pExpr; /* Pointer to the subexpression that is this term */ 96 Expr *pExpr; /* Pointer to the subexpression that is this term */ 97 int iParent; /* Disable pWC->a[iParent] when this term disabled */ 97 int iParent; /* Disable pWC->a[iParent] when this term disabled */ 98 int leftCursor; /* Cursor number of X in "X <op> <expr>" */ 98 int leftCursor; /* Cursor number of X in "X <op> <expr>" */ 99 union { 99 union { 100 int leftColumn; /* Column number of X in "X <op> <expr>" */ 100 int leftColumn; /* Column number of X in "X <op> <expr>" */ 101 WhereOrInfo *pOrInfo; /* Extra information if eOperator==WO_OR */ | 101 WhereOrInfo *pOrInfo; /* Extra information if (eOperator & WO_OR)!=0 */ 102 WhereAndInfo *pAndInfo; /* Extra information if eOperator==WO_AND */ | 102 WhereAndInfo *pAndInfo; /* Extra information if (eOperator& WO_AND)!=0 */ 103 } u; 103 } u; 104 u16 eOperator; /* A WO_xx value describing <op> */ 104 u16 eOperator; /* A WO_xx value describing <op> */ 105 u8 wtFlags; /* TERM_xxx bit flags. See below */ 105 u8 wtFlags; /* TERM_xxx bit flags. See below */ 106 u8 nChild; /* Number of children that must disable us */ 106 u8 nChild; /* Number of children that must disable us */ 107 WhereClause *pWC; /* The clause this term is part of */ 107 WhereClause *pWC; /* The clause this term is part of */ 108 Bitmask prereqRight; /* Bitmask of tables used by pExpr->pRight */ 108 Bitmask prereqRight; /* Bitmask of tables used by pExpr->pRight */ 109 Bitmask prereqAll; /* Bitmask of tables referenced by pExpr */ 109 Bitmask prereqAll; /* Bitmask of tables referenced by pExpr */ ................................................................................................................................................................................ 223 #define WO_LE (WO_EQ<<(TK_LE-TK_EQ)) 223 #define WO_LE (WO_EQ<<(TK_LE-TK_EQ)) 224 #define WO_GT (WO_EQ<<(TK_GT-TK_EQ)) 224 #define WO_GT (WO_EQ<<(TK_GT-TK_EQ)) 225 #define WO_GE (WO_EQ<<(TK_GE-TK_EQ)) 225 #define WO_GE (WO_EQ<<(TK_GE-TK_EQ)) 226 #define WO_MATCH 0x040 226 #define WO_MATCH 0x040 227 #define WO_ISNULL 0x080 227 #define WO_ISNULL 0x080 228 #define WO_OR 0x100 /* Two or more OR-connected terms */ 228 #define WO_OR 0x100 /* Two or more OR-connected terms */ 229 #define WO_AND 0x200 /* Two or more AND-connected terms */ 229 #define WO_AND 0x200 /* Two or more AND-connected terms */ > 230 #define WO_EQUIV 0x400 /* Of the form A==B, both columns */ 230 #define WO_NOOP 0x800 /* This term does not restrict search space */ 231 #define WO_NOOP 0x800 /* This term does not restrict search space */ 231 232 232 #define WO_ALL 0xfff /* Mask of all possible WO_* values */ 233 #define WO_ALL 0xfff /* Mask of all possible WO_* values */ 233 #define WO_SINGLE 0x0ff /* Mask of all non-compound WO_* values */ 234 #define WO_SINGLE 0x0ff /* Mask of all non-compound WO_* values */ 234 235 235 /* 236 /* 236 ** Value for wsFlags returned by bestIndex() and stored in 237 ** Value for wsFlags returned by bestIndex() and stored in ................................................................................................................................................................................ 625 } 626 } 626 627 627 /* 628 /* 628 ** Search for a term in the WHERE clause that is of the form "X <op> <expr>" 629 ** Search for a term in the WHERE clause that is of the form "X <op> <expr>" 629 ** where X is a reference to the iColumn of table iCur and <op> is one of 630 ** where X is a reference to the iColumn of table iCur and <op> is one of 630 ** the WO_xx operator codes specified by the op parameter. 631 ** the WO_xx operator codes specified by the op parameter. 631 ** Return a pointer to the term. Return 0 if not found. 632 ** Return a pointer to the term. Return 0 if not found. > 633 ** > 634 ** The term returned might by Y=<expr> if there is another constraint in > 635 ** the WHERE clause that specifies that X=Y. Any such constraints will be > 636 ** identified by the WO_EQUIV bit in the pTerm->eOperator field. The > 637 ** aEquiv[] array holds X and all its equivalents, with each SQL variable > 638 ** taking up two slots in aEquiv[]. The first slot is for the cursor number > 639 ** and the second is for the column number. There are 22 slots in aEquiv[] > 640 ** so that means we can look for X plus up to 10 other equivalent values. > 641 ** Hence a search for X will return <expr> if X=A1 and A1=A2 and A2=A3 > 642 ** and ... and A9=A10 and A10=<expr>. > 643 ** > 644 ** If there are multiple terms in the WHERE clause of the form "X <op> <expr>" > 645 ** then try for the one with no dependencies on <expr> - in other words where > 646 ** <expr> is a constant expression of some kind. Only return entries of > 647 ** the form "X <op> Y" where Y is a column in another table if no terms of > 648 ** the form "X <op> <const-expr>" exist. Other than this priority, if there > 649 ** are two or more terms that match, then the choice of which term to return > 650 ** is arbitrary. 632 */ 651 */ 633 static WhereTerm *findTerm( 652 static WhereTerm *findTerm( 634 WhereClause *pWC, /* The WHERE clause to be searched */ 653 WhereClause *pWC, /* The WHERE clause to be searched */ 635 int iCur, /* Cursor number of LHS */ 654 int iCur, /* Cursor number of LHS */ 636 int iColumn, /* Column number of LHS */ 655 int iColumn, /* Column number of LHS */ 637 Bitmask notReady, /* RHS must not overlap with this mask */ 656 Bitmask notReady, /* RHS must not overlap with this mask */ 638 u32 op, /* Mask of WO_xx values describing operator */ 657 u32 op, /* Mask of WO_xx values describing operator */ 639 Index *pIdx /* Must be compatible with this index, if not NULL */ 658 Index *pIdx /* Must be compatible with this index, if not NULL */ 640 ){ 659 ){ 641 WhereTerm *pTerm; | 660 WhereTerm *pTerm; /* Term being examined as possible result */ 642 int k; | 661 WhereTerm *pResult = 0; /* The answer to return */ > 662 WhereClause *pWCOrig = pWC; /* Original pWC value */ > 663 int j, k; /* Loop counters */ > 664 Expr *pX; /* Pointer to an expression */ > 665 Parse *pParse; /* Parsing context */ > 666 int iOrigCol = iColumn; /* Original value of iColumn */ > 667 int nEquiv = 2; /* Number of entires in aEquiv[] */ > 668 int iEquiv = 2; /* Number of entries of aEquiv[] processed so far */ > 669 int aEquiv[22]; /* iCur,iColumn and up to 10 other equivalents */ > 670 643 assert( iCur>=0 ); 671 assert( iCur>=0 ); 644 op &= WO_ALL; < > 672 aEquiv[0] = iCur; > 673 aEquiv[1] = iColumn; > 674 for(;;){ 645 for(; pWC; pWC=pWC->pOuter){ | 675 for(pWC=pWCOrig; pWC; pWC=pWC->pOuter){ 646 for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){ | 676 for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){ 647 if( pTerm->leftCursor==iCur | 677 if( pTerm->leftCursor==iCur 648 && (pTerm->prereqRight & notReady)==0 < 649 && pTerm->u.leftColumn==iColumn | 678 && pTerm->u.leftColumn==iColumn > 679 ){ > 680 if( (pTerm->prereqRight & notReady)==0 650 && (pTerm->eOperator & op)!=0 | 681 && (pTerm->eOperator & op & WO_ALL)!=0 651 ){ | 682 ){ 652 if( iColumn>=0 && pIdx && pTerm->eOperator!=WO_ISNULL ){ < 653 Expr *pX = pTerm->pExpr; < > 683 if( iOrigCol>=0 && pIdx && (pTerm->eOperator & WO_ISNULL)==0 ){ 654 CollSeq *pColl; | 684 CollSeq *pColl; 655 char idxaff; | 685 char idxaff; 656 int j; < 657 Parse *pParse = pWC->pParse; < 658 686 > 687 pX = pTerm->pExpr; > 688 pParse = pWC->pParse; 659 idxaff = pIdx->pTable->aCol[iColumn].affinity; | 689 idxaff = pIdx->pTable->aCol[iOrigCol].affinity; 660 if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue; | 690 if( !sqlite3IndexAffinityOk(pX, idxaff) ){ > 691 continue; 661 | 692 } > 693 662 /* Figure out the collation sequence required from an index for | 694 /* Figure out the collation sequence required from an index for 663 ** it to be useful for optimising expression pX. Store this | 695 ** it to be useful for optimising expression pX. Store this 664 ** value in variable pColl. | 696 ** value in variable pColl. 665 */ | 697 */ 666 assert(pX->pLeft); | 698 assert(pX->pLeft); 667 pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight); | 699 pColl = sqlite3BinaryCompareCollSeq(pParse,pX->pLeft,pX->pRight); 668 if( pColl==0 ) pColl = pParse->db->pDfltColl; | 700 if( pColl==0 ) pColl = pParse->db->pDfltColl; 669 701 670 for(j=0; pIdx->aiColumn[j]!=iColumn; j++){ | 702 for(j=0; pIdx->aiColumn[j]!=iOrigCol; j++){ 671 if( NEVER(j>=pIdx->nColumn) ) return 0; | 703 if( NEVER(j>=pIdx->nColumn) ) return 0; 672 } | 704 } 673 if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue; | 705 if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ){ > 706 continue; 674 } | 707 } > 708 } 675 return pTerm; | 709 pResult = pTerm; > 710 if( pTerm->prereqRight==0 ) goto findTerm_success; 676 } | 711 } > 712 if( (pTerm->eOperator & WO_EQUIV)!=0 > 713 && nEquiv<ArraySize(aEquiv) > 714 ){ > 715 pX = sqlite3ExprSkipCollate(pTerm->pExpr->pRight); > 716 assert( pX->op==TK_COLUMN ); > 717 for(j=0; j<nEquiv; j+=2){ > 718 if( aEquiv[j]==pX->iTable && aEquiv[j+1]==pX->iColumn ) break; 677 } | 719 } > 720 if( j==nEquiv ){ > 721 aEquiv[j] = pX->iTable; > 722 aEquiv[j+1] = pX->iColumn; > 723 nEquiv += 2; 678 } | 724 } > 725 } > 726 } > 727 } > 728 } > 729 if( iEquiv>=nEquiv ) break; > 730 iCur = aEquiv[iEquiv++]; > 731 iColumn = aEquiv[iEquiv++]; > 732 } > 733 findTerm_success: 679 return 0; | 734 return pResult; 680 } 735 } 681 736 682 /* Forward reference */ 737 /* Forward reference */ 683 static void exprAnalyze(SrcList*, WhereClause*, int); 738 static void exprAnalyze(SrcList*, WhereClause*, int); 684 739 685 /* 740 /* 686 ** Call exprAnalyze on all terms in a WHERE clause. 741 ** Call exprAnalyze on all terms in a WHERE clause. ................................................................................................................................................................................ 950 ** Compute the set of tables that might satisfy cases 1 or 2. 1005 ** Compute the set of tables that might satisfy cases 1 or 2. 951 */ 1006 */ 952 indexable = ~(Bitmask)0; 1007 indexable = ~(Bitmask)0; 953 chngToIN = ~(pWC->vmask); 1008 chngToIN = ~(pWC->vmask); 954 for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0 && indexable; i--, pOrTerm++){ 1009 for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0 && indexable; i--, pOrTerm++){ 955 if( (pOrTerm->eOperator & WO_SINGLE)==0 ){ 1010 if( (pOrTerm->eOperator & WO_SINGLE)==0 ){ 956 WhereAndInfo *pAndInfo; 1011 WhereAndInfo *pAndInfo; 957 assert( pOrTerm->eOperator==0 ); < 958 assert( (pOrTerm->wtFlags & (TERM_ANDINFO|TERM_ORINFO))==0 ); 1012 assert( (pOrTerm->wtFlags & (TERM_ANDINFO|TERM_ORINFO))==0 ); 959 chngToIN = 0; 1013 chngToIN = 0; 960 pAndInfo = sqlite3DbMallocRaw(db, sizeof(*pAndInfo)); 1014 pAndInfo = sqlite3DbMallocRaw(db, sizeof(*pAndInfo)); 961 if( pAndInfo ){ 1015 if( pAndInfo ){ 962 WhereClause *pAndWC; 1016 WhereClause *pAndWC; 963 WhereTerm *pAndTerm; 1017 WhereTerm *pAndTerm; 964 int j; 1018 int j; ................................................................................................................................................................................ 989 Bitmask b; 1043 Bitmask b; 990 b = getMask(pMaskSet, pOrTerm->leftCursor); 1044 b = getMask(pMaskSet, pOrTerm->leftCursor); 991 if( pOrTerm->wtFlags & TERM_VIRTUAL ){ 1045 if( pOrTerm->wtFlags & TERM_VIRTUAL ){ 992 WhereTerm *pOther = &pOrWc->a[pOrTerm->iParent]; 1046 WhereTerm *pOther = &pOrWc->a[pOrTerm->iParent]; 993 b |= getMask(pMaskSet, pOther->leftCursor); 1047 b |= getMask(pMaskSet, pOther->leftCursor); 994 } 1048 } 995 indexable &= b; 1049 indexable &= b; 996 if( pOrTerm->eOperator!=WO_EQ ){ | 1050 if( (pOrTerm->eOperator & WO_EQ)==0 ){ 997 chngToIN = 0; 1051 chngToIN = 0; 998 }else{ 1052 }else{ 999 chngToIN &= b; 1053 chngToIN &= b; 1000 } 1054 } 1001 } 1055 } 1002 } 1056 } 1003 1057 ................................................................................................................................................................................ 1040 ** will be recorded in iCursor and iColumn. There might not be any 1094 ** will be recorded in iCursor and iColumn. There might not be any 1041 ** such table and column. Set okToChngToIN if an appropriate table 1095 ** such table and column. Set okToChngToIN if an appropriate table 1042 ** and column is found but leave okToChngToIN false if not found. 1096 ** and column is found but leave okToChngToIN false if not found. 1043 */ 1097 */ 1044 for(j=0; j<2 && !okToChngToIN; j++){ 1098 for(j=0; j<2 && !okToChngToIN; j++){ 1045 pOrTerm = pOrWc->a; 1099 pOrTerm = pOrWc->a; 1046 for(i=pOrWc->nTerm-1; i>=0; i--, pOrTerm++){ 1100 for(i=pOrWc->nTerm-1; i>=0; i--, pOrTerm++){ 1047 assert( pOrTerm->eOperator==WO_EQ ); | 1101 assert( pOrTerm->eOperator & WO_EQ ); 1048 pOrTerm->wtFlags &= ~TERM_OR_OK; 1102 pOrTerm->wtFlags &= ~TERM_OR_OK; 1049 if( pOrTerm->leftCursor==iCursor ){ 1103 if( pOrTerm->leftCursor==iCursor ){ 1050 /* This is the 2-bit case and we are on the second iteration and 1104 /* This is the 2-bit case and we are on the second iteration and 1051 ** current term is from the first iteration. So skip this term. */ 1105 ** current term is from the first iteration. So skip this term. */ 1052 assert( j==1 ); 1106 assert( j==1 ); 1053 continue; 1107 continue; 1054 } 1108 } ................................................................................................................................................................................ 1066 iCursor = pOrTerm->leftCursor; 1120 iCursor = pOrTerm->leftCursor; 1067 break; 1121 break; 1068 } 1122 } 1069 if( i<0 ){ 1123 if( i<0 ){ 1070 /* No candidate table+column was found. This can only occur 1124 /* No candidate table+column was found. This can only occur 1071 ** on the second iteration */ 1125 ** on the second iteration */ 1072 assert( j==1 ); 1126 assert( j==1 ); 1073 assert( (chngToIN&(chngToIN-1))==0 ); | 1127 assert( IsPowerOfTwo(chngToIN) ); 1074 assert( chngToIN==getMask(pMaskSet, iCursor) ); 1128 assert( chngToIN==getMask(pMaskSet, iCursor) ); 1075 break; 1129 break; 1076 } 1130 } 1077 testcase( j==1 ); 1131 testcase( j==1 ); 1078 1132 1079 /* We have found a candidate table and column. Check to see if that 1133 /* We have found a candidate table and column. Check to see if that 1080 ** table and column is common to every term in the OR clause */ 1134 ** table and column is common to every term in the OR clause */ 1081 okToChngToIN = 1; 1135 okToChngToIN = 1; 1082 for(; i>=0 && okToChngToIN; i--, pOrTerm++){ 1136 for(; i>=0 && okToChngToIN; i--, pOrTerm++){ 1083 assert( pOrTerm->eOperator==WO_EQ ); | 1137 assert( pOrTerm->eOperator & WO_EQ ); 1084 if( pOrTerm->leftCursor!=iCursor ){ 1138 if( pOrTerm->leftCursor!=iCursor ){ 1085 pOrTerm->wtFlags &= ~TERM_OR_OK; 1139 pOrTerm->wtFlags &= ~TERM_OR_OK; 1086 }else if( pOrTerm->u.leftColumn!=iColumn ){ 1140 }else if( pOrTerm->u.leftColumn!=iColumn ){ 1087 okToChngToIN = 0; 1141 okToChngToIN = 0; 1088 }else{ 1142 }else{ 1089 int affLeft, affRight; 1143 int affLeft, affRight; 1090 /* If the right-hand side is also a column, then the affinities 1144 /* If the right-hand side is also a column, then the affinities ................................................................................................................................................................................ 1112 Expr *pDup; /* A transient duplicate expression */ 1166 Expr *pDup; /* A transient duplicate expression */ 1113 ExprList *pList = 0; /* The RHS of the IN operator */ 1167 ExprList *pList = 0; /* The RHS of the IN operator */ 1114 Expr *pLeft = 0; /* The LHS of the IN operator */ 1168 Expr *pLeft = 0; /* The LHS of the IN operator */ 1115 Expr *pNew; /* The complete IN operator */ 1169 Expr *pNew; /* The complete IN operator */ 1116 1170 1117 for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0; i--, pOrTerm++){ 1171 for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0; i--, pOrTerm++){ 1118 if( (pOrTerm->wtFlags & TERM_OR_OK)==0 ) continue; 1172 if( (pOrTerm->wtFlags & TERM_OR_OK)==0 ) continue; 1119 assert( pOrTerm->eOperator==WO_EQ ); | 1173 assert( pOrTerm->eOperator & WO_EQ ); 1120 assert( pOrTerm->leftCursor==iCursor ); 1174 assert( pOrTerm->leftCursor==iCursor ); 1121 assert( pOrTerm->u.leftColumn==iColumn ); 1175 assert( pOrTerm->u.leftColumn==iColumn ); 1122 pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight, 0); 1176 pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight, 0); 1123 pList = sqlite3ExprListAppend(pWC->pParse, pList, pDup); 1177 pList = sqlite3ExprListAppend(pWC->pParse, pList, pDup); 1124 pLeft = pOrTerm->pExpr->pLeft; 1178 pLeft = pOrTerm->pExpr->pLeft; 1125 } 1179 } 1126 assert( pLeft!=0 ); 1180 assert( pLeft!=0 ); ................................................................................................................................................................................ 1141 sqlite3ExprListDelete(db, pList); 1195 sqlite3ExprListDelete(db, pList); 1142 } 1196 } 1143 pTerm->eOperator = WO_NOOP; /* case 1 trumps case 2 */ 1197 pTerm->eOperator = WO_NOOP; /* case 1 trumps case 2 */ 1144 } 1198 } 1145 } 1199 } 1146 } 1200 } 1147 #endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */ 1201 #endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */ 1148 < 1149 1202 1150 /* 1203 /* 1151 ** The input to this routine is an WhereTerm structure with only the 1204 ** The input to this routine is an WhereTerm structure with only the 1152 ** "pExpr" field filled in. The job of this routine is to analyze the 1205 ** "pExpr" field filled in. The job of this routine is to analyze the 1153 ** subexpression and populate all the other fields of the WhereTerm 1206 ** subexpression and populate all the other fields of the WhereTerm 1154 ** structure. 1207 ** structure. 1155 ** 1208 ** ................................................................................................................................................................................ 1211 extraRight = x-1; /* ON clause terms may not be used with an index 1264 extraRight = x-1; /* ON clause terms may not be used with an index 1212 ** on left table of a LEFT JOIN. Ticket #3015 */ 1265 ** on left table of a LEFT JOIN. Ticket #3015 */ 1213 } 1266 } 1214 pTerm->prereqAll = prereqAll; 1267 pTerm->prereqAll = prereqAll; 1215 pTerm->leftCursor = -1; 1268 pTerm->leftCursor = -1; 1216 pTerm->iParent = -1; 1269 pTerm->iParent = -1; 1217 pTerm->eOperator = 0; 1270 pTerm->eOperator = 0; 1218 if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){ | 1271 if( allowedOp(op) ){ 1219 Expr *pLeft = sqlite3ExprSkipCollate(pExpr->pLeft); 1272 Expr *pLeft = sqlite3ExprSkipCollate(pExpr->pLeft); 1220 Expr *pRight = sqlite3ExprSkipCollate(pExpr->pRight); 1273 Expr *pRight = sqlite3ExprSkipCollate(pExpr->pRight); > 1274 u16 opMask = (pTerm->prereqRight & prereqLeft)==0 ? WO_ALL : WO_EQUIV; 1221 if( pLeft->op==TK_COLUMN ){ 1275 if( pLeft->op==TK_COLUMN ){ 1222 pTerm->leftCursor = pLeft->iTable; 1276 pTerm->leftCursor = pLeft->iTable; 1223 pTerm->u.leftColumn = pLeft->iColumn; 1277 pTerm->u.leftColumn = pLeft->iColumn; 1224 pTerm->eOperator = operatorMask(op); | 1278 pTerm->eOperator = operatorMask(op) & opMask; 1225 } 1279 } 1226 if( pRight && pRight->op==TK_COLUMN ){ 1280 if( pRight && pRight->op==TK_COLUMN ){ 1227 WhereTerm *pNew; 1281 WhereTerm *pNew; 1228 Expr *pDup; 1282 Expr *pDup; > 1283 u16 eExtraOp = 0; /* Extra bits for pNew->eOperator */ 1229 if( pTerm->leftCursor>=0 ){ 1284 if( pTerm->leftCursor>=0 ){ 1230 int idxNew; 1285 int idxNew; 1231 pDup = sqlite3ExprDup(db, pExpr, 0); 1286 pDup = sqlite3ExprDup(db, pExpr, 0); 1232 if( db->mallocFailed ){ 1287 if( db->mallocFailed ){ 1233 sqlite3ExprDelete(db, pDup); 1288 sqlite3ExprDelete(db, pDup); 1234 return; 1289 return; 1235 } 1290 } ................................................................................................................................................................................ 1236 idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC); 1291 idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC); 1237 if( idxNew==0 ) return; 1292 if( idxNew==0 ) return; 1238 pNew = &pWC->a[idxNew]; 1293 pNew = &pWC->a[idxNew]; 1239 pNew->iParent = idxTerm; 1294 pNew->iParent = idxTerm; 1240 pTerm = &pWC->a[idxTerm]; 1295 pTerm = &pWC->a[idxTerm]; 1241 pTerm->nChild = 1; 1296 pTerm->nChild = 1; 1242 pTerm->wtFlags |= TERM_COPIED; 1297 pTerm->wtFlags |= TERM_COPIED; > 1298 if( pExpr->op==TK_EQ > 1299 && !ExprHasProperty(pExpr, EP_FromJoin) > 1300 && OptimizationEnabled(db, SQLITE_Transitive) > 1301 ){ > 1302 pTerm->eOperator |= WO_EQUIV; > 1303 eExtraOp = WO_EQUIV; > 1304 } 1243 }else{ 1305 }else{ 1244 pDup = pExpr; 1306 pDup = pExpr; 1245 pNew = pTerm; 1307 pNew = pTerm; 1246 } 1308 } 1247 exprCommute(pParse, pDup); 1309 exprCommute(pParse, pDup); 1248 pLeft = sqlite3ExprSkipCollate(pDup->pLeft); 1310 pLeft = sqlite3ExprSkipCollate(pDup->pLeft); 1249 pNew->leftCursor = pLeft->iTable; 1311 pNew->leftCursor = pLeft->iTable; 1250 pNew->u.leftColumn = pLeft->iColumn; 1312 pNew->u.leftColumn = pLeft->iColumn; 1251 testcase( (prereqLeft | extraRight) != prereqLeft ); 1313 testcase( (prereqLeft | extraRight) != prereqLeft ); 1252 pNew->prereqRight = prereqLeft | extraRight; 1314 pNew->prereqRight = prereqLeft | extraRight; 1253 pNew->prereqAll = prereqAll; 1315 pNew->prereqAll = prereqAll; 1254 pNew->eOperator = operatorMask(pDup->op); | 1316 pNew->eOperator = (operatorMask(pDup->op) + eExtraOp) & opMask; 1255 } 1317 } 1256 } 1318 } 1257 1319 1258 #ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION 1320 #ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION 1259 /* If a term is the BETWEEN operator, create two new virtual terms 1321 /* If a term is the BETWEEN operator, create two new virtual terms 1260 ** that define the range that the BETWEEN implements. For example: 1322 ** that define the range that the BETWEEN implements. For example: 1261 ** 1323 ** ................................................................................................................................................................................ 1706 } 1768 } 1707 if( pWC->wctrlFlags & WHERE_AND_ONLY ){ 1769 if( pWC->wctrlFlags & WHERE_AND_ONLY ){ 1708 return; 1770 return; 1709 } 1771 } 1710 1772 1711 /* Search the WHERE clause terms for a usable WO_OR term. */ 1773 /* Search the WHERE clause terms for a usable WO_OR term. */ 1712 for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){ 1774 for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){ 1713 if( pTerm->eOperator==WO_OR | 1775 if( (pTerm->eOperator & WO_OR)!=0 1714 && ((pTerm->prereqAll & ~maskSrc) & p->notReady)==0 1776 && ((pTerm->prereqAll & ~maskSrc) & p->notReady)==0 1715 && (pTerm->u.pOrInfo->indexable & maskSrc)!=0 1777 && (pTerm->u.pOrInfo->indexable & maskSrc)!=0 1716 ){ 1778 ){ 1717 WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc; 1779 WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc; 1718 WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm]; 1780 WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm]; 1719 WhereTerm *pOrTerm; 1781 WhereTerm *pOrTerm; 1720 int flags = WHERE_MULTI_OR; 1782 int flags = WHERE_MULTI_OR; ................................................................................................................................................................................ 1727 sBOI.pOrderBy = 0; 1789 sBOI.pOrderBy = 0; 1728 sBOI.pDistinct = 0; 1790 sBOI.pDistinct = 0; 1729 sBOI.ppIdxInfo = 0; 1791 sBOI.ppIdxInfo = 0; 1730 for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){ 1792 for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){ 1731 WHERETRACE(("... Multi-index OR testing for term %d of %d....\n", 1793 WHERETRACE(("... Multi-index OR testing for term %d of %d....\n", 1732 (pOrTerm - pOrWC->a), (pTerm - pWC->a) 1794 (pOrTerm - pOrWC->a), (pTerm - pWC->a) 1733 )); 1795 )); 1734 if( pOrTerm->eOperator==WO_AND ){ | 1796 if( (pOrTerm->eOperator& WO_AND)!=0 ){ 1735 sBOI.pWC = &pOrTerm->u.pAndInfo->wc; 1797 sBOI.pWC = &pOrTerm->u.pAndInfo->wc; 1736 bestIndex(&sBOI); 1798 bestIndex(&sBOI); 1737 }else if( pOrTerm->leftCursor==iCur ){ 1799 }else if( pOrTerm->leftCursor==iCur ){ 1738 WhereClause tempWC; 1800 WhereClause tempWC; 1739 tempWC.pParse = pWC->pParse; 1801 tempWC.pParse = pWC->pParse; 1740 tempWC.pMaskSet = pWC->pMaskSet; 1802 tempWC.pMaskSet = pWC->pMaskSet; 1741 tempWC.pOuter = pWC; 1803 tempWC.pOuter = pWC; ................................................................................................................................................................................ 1788 static int termCanDriveIndex( 1850 static int termCanDriveIndex( 1789 WhereTerm *pTerm, /* WHERE clause term to check */ 1851 WhereTerm *pTerm, /* WHERE clause term to check */ 1790 struct SrcList_item *pSrc, /* Table we are trying to access */ 1852 struct SrcList_item *pSrc, /* Table we are trying to access */ 1791 Bitmask notReady /* Tables in outer loops of the join */ 1853 Bitmask notReady /* Tables in outer loops of the join */ 1792 ){ 1854 ){ 1793 char aff; 1855 char aff; 1794 if( pTerm->leftCursor!=pSrc->iCursor ) return 0; 1856 if( pTerm->leftCursor!=pSrc->iCursor ) return 0; 1795 if( pTerm->eOperator!=WO_EQ ) return 0; | 1857 if( (pTerm->eOperator & WO_EQ)==0 ) return 0; 1796 if( (pTerm->prereqRight & notReady)!=0 ) return 0; 1858 if( (pTerm->prereqRight & notReady)!=0 ) return 0; 1797 aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity; 1859 aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity; 1798 if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0; 1860 if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0; 1799 return 1; 1861 return 1; 1800 } 1862 } 1801 #endif 1863 #endif 1802 1864 ................................................................................................................................................................................ 2050 2112 2051 WHERETRACE(("Recomputing index info for %s...\n", pSrc->pTab->zName)); 2113 WHERETRACE(("Recomputing index info for %s...\n", pSrc->pTab->zName)); 2052 2114 2053 /* Count the number of possible WHERE clause constraints referring 2115 /* Count the number of possible WHERE clause constraints referring 2054 ** to this virtual table */ 2116 ** to this virtual table */ 2055 for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){ 2117 for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){ 2056 if( pTerm->leftCursor != pSrc->iCursor ) continue; 2118 if( pTerm->leftCursor != pSrc->iCursor ) continue; 2057 assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 ); | 2119 assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) ); 2058 testcase( pTerm->eOperator==WO_IN ); | 2120 testcase( pTerm->eOperator & WO_IN ); 2059 testcase( pTerm->eOperator==WO_ISNULL ); | 2121 testcase( pTerm->eOperator & WO_ISNULL ); 2060 if( pTerm->eOperator & (WO_ISNULL) ) continue; 2122 if( pTerm->eOperator & (WO_ISNULL) ) continue; 2061 if( pTerm->wtFlags & TERM_VNULL ) continue; 2123 if( pTerm->wtFlags & TERM_VNULL ) continue; 2062 nTerm++; 2124 nTerm++; 2063 } 2125 } 2064 2126 2065 /* If the ORDER BY clause contains only columns in the current 2127 /* If the ORDER BY clause contains only columns in the current 2066 ** virtual table then allocate space for the aOrderBy part of 2128 ** virtual table then allocate space for the aOrderBy part of ................................................................................................................................................................................ 2103 *(struct sqlite3_index_orderby**)&pIdxInfo->aOrderBy = pIdxOrderBy; 2165 *(struct sqlite3_index_orderby**)&pIdxInfo->aOrderBy = pIdxOrderBy; 2104 *(struct sqlite3_index_constraint_usage**)&pIdxInfo->aConstraintUsage = 2166 *(struct sqlite3_index_constraint_usage**)&pIdxInfo->aConstraintUsage = 2105 pUsage; 2167 pUsage; 2106 2168 2107 for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){ 2169 for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){ 2108 u8 op; 2170 u8 op; 2109 if( pTerm->leftCursor != pSrc->iCursor ) continue; 2171 if( pTerm->leftCursor != pSrc->iCursor ) continue; 2110 assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 ); | 2172 assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) ); 2111 testcase( pTerm->eOperator==WO_IN ); | 2173 testcase( pTerm->eOperator & WO_IN ); 2112 testcase( pTerm->eOperator==WO_ISNULL ); | 2174 testcase( pTerm->eOperator & WO_ISNULL ); 2113 if( pTerm->eOperator & (WO_ISNULL) ) continue; 2175 if( pTerm->eOperator & (WO_ISNULL) ) continue; 2114 if( pTerm->wtFlags & TERM_VNULL ) continue; 2176 if( pTerm->wtFlags & TERM_VNULL ) continue; 2115 pIdxCons[j].iColumn = pTerm->u.leftColumn; 2177 pIdxCons[j].iColumn = pTerm->u.leftColumn; 2116 pIdxCons[j].iTermOffset = i; 2178 pIdxCons[j].iTermOffset = i; 2117 op = (u8)pTerm->eOperator; | 2179 op = (u8)pTerm->eOperator & WO_ALL; 2118 if( op==WO_IN ) op = WO_EQ; 2180 if( op==WO_IN ) op = WO_EQ; 2119 pIdxCons[j].op = op; 2181 pIdxCons[j].op = op; 2120 /* The direct assignment in the previous line is possible only because 2182 /* The direct assignment in the previous line is possible only because 2121 ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical. The 2183 ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical. The 2122 ** following asserts verify this fact. */ 2184 ** following asserts verify this fact. */ 2123 assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ ); 2185 assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ ); 2124 assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT ); 2186 assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT ); ................................................................................................................................................................................ 2280 */ 2342 */ 2281 pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint; 2343 pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint; 2282 pUsage = pIdxInfo->aConstraintUsage; 2344 pUsage = pIdxInfo->aConstraintUsage; 2283 for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){ 2345 for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){ 2284 j = pIdxCons->iTermOffset; 2346 j = pIdxCons->iTermOffset; 2285 pTerm = &pWC->a[j]; 2347 pTerm = &pWC->a[j]; 2286 if( (pTerm->prereqRight&p->notReady)==0 2348 if( (pTerm->prereqRight&p->notReady)==0 2287 && (bAllowIN || pTerm->eOperator!=WO_IN) | 2349 && (bAllowIN || (pTerm->eOperator & WO_IN)==0) 2288 ){ 2350 ){ 2289 pIdxCons->usable = 1; 2351 pIdxCons->usable = 1; 2290 }else{ 2352 }else{ 2291 pIdxCons->usable = 0; 2353 pIdxCons->usable = 0; 2292 } 2354 } 2293 } 2355 } 2294 memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint); 2356 memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint); ................................................................................................................................................................................ 2312 2374 2313 pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint; 2375 pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint; 2314 for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){ 2376 for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){ 2315 if( pUsage[i].argvIndex>0 ){ 2377 if( pUsage[i].argvIndex>0 ){ 2316 j = pIdxCons->iTermOffset; 2378 j = pIdxCons->iTermOffset; 2317 pTerm = &pWC->a[j]; 2379 pTerm = &pWC->a[j]; 2318 p->cost.used |= pTerm->prereqRight; 2380 p->cost.used |= pTerm->prereqRight; 2319 if( pTerm->eOperator==WO_IN && pUsage[i].omit==0 ){ | 2381 if( (pTerm->eOperator & WO_IN)!=0 && pUsage[i].omit==0 ){ 2320 /* Do not attempt to use an IN constraint if the virtual table 2382 /* Do not attempt to use an IN constraint if the virtual table 2321 ** says that the equivalent EQ constraint cannot be safely omitted. 2383 ** says that the equivalent EQ constraint cannot be safely omitted. 2322 ** If we do attempt to use such a constraint, some rows might be 2384 ** If we do attempt to use such a constraint, some rows might be 2323 ** repeated in the output. */ 2385 ** repeated in the output. */ 2324 break; 2386 break; 2325 } 2387 } 2326 } 2388 } ................................................................................................................................................................................ 2618 tRowcnt iUpper = p->aiRowEst[0]; 2680 tRowcnt iUpper = p->aiRowEst[0]; 2619 tRowcnt a[2]; 2681 tRowcnt a[2]; 2620 u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity; 2682 u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity; 2621 2683 2622 if( pLower ){ 2684 if( pLower ){ 2623 Expr *pExpr = pLower->pExpr->pRight; 2685 Expr *pExpr = pLower->pExpr->pRight; 2624 rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal); 2686 rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal); 2625 assert( pLower->eOperator==WO_GT || pLower->eOperator==WO_GE ); | 2687 assert( (pLower->eOperator & (WO_GT|WO_GE))!=0 ); 2626 if( rc==SQLITE_OK 2688 if( rc==SQLITE_OK 2627 && whereKeyStats(pParse, p, pRangeVal, 0, a)==SQLITE_OK 2689 && whereKeyStats(pParse, p, pRangeVal, 0, a)==SQLITE_OK 2628 ){ 2690 ){ 2629 iLower = a[0]; 2691 iLower = a[0]; 2630 if( pLower->eOperator==WO_GT ) iLower += a[1]; | 2692 if( (pLower->eOperator & WO_GT)!=0 ) iLower += a[1]; 2631 } 2693 } 2632 sqlite3ValueFree(pRangeVal); 2694 sqlite3ValueFree(pRangeVal); 2633 } 2695 } 2634 if( rc==SQLITE_OK && pUpper ){ 2696 if( rc==SQLITE_OK && pUpper ){ 2635 Expr *pExpr = pUpper->pExpr->pRight; 2697 Expr *pExpr = pUpper->pExpr->pRight; 2636 rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal); 2698 rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal); 2637 assert( pUpper->eOperator==WO_LT || pUpper->eOperator==WO_LE ); | 2699 assert( (pUpper->eOperator & (WO_LT|WO_LE))!=0 ); 2638 if( rc==SQLITE_OK 2700 if( rc==SQLITE_OK 2639 && whereKeyStats(pParse, p, pRangeVal, 1, a)==SQLITE_OK 2701 && whereKeyStats(pParse, p, pRangeVal, 1, a)==SQLITE_OK 2640 ){ 2702 ){ 2641 iUpper = a[0]; 2703 iUpper = a[0]; 2642 if( pUpper->eOperator==WO_LE ) iUpper += a[1]; | 2704 if( (pUpper->eOperator & WO_LE)!=0 ) iUpper += a[1]; 2643 } 2705 } 2644 sqlite3ValueFree(pRangeVal); 2706 sqlite3ValueFree(pRangeVal); 2645 } 2707 } 2646 if( rc==SQLITE_OK ){ 2708 if( rc==SQLITE_OK ){ 2647 if( iUpper<=iLower ){ 2709 if( iUpper<=iLower ){ 2648 *pRangeDiv = (double)p->aiRowEst[0]; 2710 *pRangeDiv = (double)p->aiRowEst[0]; 2649 }else{ 2711 }else{ ................................................................................................................................................................................ 2943 3005 2944 /* If X is the column in the index and ORDER BY clause, check to see 3006 /* If X is the column in the index and ORDER BY clause, check to see 2945 ** if there are any X= or X IS NULL constraints in the WHERE clause. */ 3007 ** if there are any X= or X IS NULL constraints in the WHERE clause. */ 2946 pConstraint = findTerm(p->pWC, base, iColumn, p->notReady, 3008 pConstraint = findTerm(p->pWC, base, iColumn, p->notReady, 2947 WO_EQ|WO_ISNULL|WO_IN, pIdx); 3009 WO_EQ|WO_ISNULL|WO_IN, pIdx); 2948 if( pConstraint==0 ){ 3010 if( pConstraint==0 ){ 2949 isEq = 0; 3011 isEq = 0; 2950 }else if( pConstraint->eOperator==WO_IN ){ | 3012 }else if( (pConstraint->eOperator & WO_IN)!=0 ){ 2951 /* Constraints of the form: "X IN ..." cannot be used with an ORDER BY 3013 /* Constraints of the form: "X IN ..." cannot be used with an ORDER BY 2952 ** because we do not know in what order the values on the RHS of the IN 3014 ** because we do not know in what order the values on the RHS of the IN 2953 ** operator will occur. */ 3015 ** operator will occur. */ 2954 break; 3016 break; 2955 }else if( pConstraint->eOperator==WO_ISNULL ){ | 3017 }else if( (pConstraint->eOperator & WO_ISNULL)!=0 ){ 2956 uniqueNotNull = 0; 3018 uniqueNotNull = 0; 2957 isEq = 1; /* "X IS NULL" means X has only a single value */ 3019 isEq = 1; /* "X IS NULL" means X has only a single value */ 2958 }else if( pConstraint->prereqRight==0 ){ 3020 }else if( pConstraint->prereqRight==0 ){ 2959 isEq = 1; /* Constraint "X=constant" means X has only a single value */ 3021 isEq = 1; /* Constraint "X=constant" means X has only a single value */ 2960 }else{ 3022 }else{ 2961 Expr *pRight = pConstraint->pExpr->pRight; 3023 Expr *pRight = pConstraint->pExpr->pRight; 2962 if( pRight->op==TK_COLUMN ){ 3024 if( pRight->op==TK_COLUMN ){ ................................................................................................................................................................................ 3361 ** to get a better estimate on the number of rows based on 3423 ** to get a better estimate on the number of rows based on 3362 ** VALUE and how common that value is according to the histogram. 3424 ** VALUE and how common that value is according to the histogram. 3363 */ 3425 */ 3364 if( pc.plan.nRow>(double)1 && pc.plan.nEq==1 3426 if( pc.plan.nRow>(double)1 && pc.plan.nEq==1 3365 && pFirstTerm!=0 && aiRowEst[1]>1 ){ 3427 && pFirstTerm!=0 && aiRowEst[1]>1 ){ 3366 assert( (pFirstTerm->eOperator & (WO_EQ|WO_ISNULL|WO_IN))!=0 ); 3428 assert( (pFirstTerm->eOperator & (WO_EQ|WO_ISNULL|WO_IN))!=0 ); 3367 if( pFirstTerm->eOperator & (WO_EQ|WO_ISNULL) ){ 3429 if( pFirstTerm->eOperator & (WO_EQ|WO_ISNULL) ){ 3368 testcase( pFirstTerm->eOperator==WO_EQ ); | 3430 testcase( pFirstTerm->eOperator & WO_EQ ); 3369 testcase( pFirstTerm->eOperator==WO_ISNULL ); | 3431 testcase( pFirstTerm->eOperator & WO_EQUIV ); > 3432 testcase( pFirstTerm->eOperator & WO_ISNULL ); 3370 whereEqualScanEst(pParse, pProbe, pFirstTerm->pExpr->pRight, 3433 whereEqualScanEst(pParse, pProbe, pFirstTerm->pExpr->pRight, 3371 &pc.plan.nRow); 3434 &pc.plan.nRow); 3372 }else if( bInEst==0 ){ 3435 }else if( bInEst==0 ){ 3373 assert( pFirstTerm->eOperator==WO_IN ); | 3436 assert( pFirstTerm->eOperator & WO_IN ); 3374 whereInScanEst(pParse, pProbe, pFirstTerm->pExpr->x.pList, 3437 whereInScanEst(pParse, pProbe, pFirstTerm->pExpr->x.pList, 3375 &pc.plan.nRow); 3438 &pc.plan.nRow); 3376 } 3439 } 3377 } 3440 } 3378 #endif /* SQLITE_ENABLE_STAT3 */ 3441 #endif /* SQLITE_ENABLE_STAT3 */ 3379 3442 3380 /* Adjust the number of output rows and downward to reflect rows 3443 /* Adjust the number of output rows and downward to reflect rows ................................................................................................................................................................................ 3513 ** set size by a factor of 3. Indexed range constraints reduce 3576 ** set size by a factor of 3. Indexed range constraints reduce 3514 ** the search space by a larger factor: 4. We make indexed range 3577 ** the search space by a larger factor: 4. We make indexed range 3515 ** more selective intentionally because of the subjective 3578 ** more selective intentionally because of the subjective 3516 ** observation that indexed range constraints really are more 3579 ** observation that indexed range constraints really are more 3517 ** selective in practice, on average. */ 3580 ** selective in practice, on average. */ 3518 pc.plan.nRow /= 3; 3581 pc.plan.nRow /= 3; 3519 } 3582 } 3520 }else if( pTerm->eOperator!=WO_NOOP ){ | 3583 }else if( (pTerm->eOperator & WO_NOOP)==0 ){ 3521 /* Any other expression lowers the output row count by half */ 3584 /* Any other expression lowers the output row count by half */ 3522 pc.plan.nRow /= 2; 3585 pc.plan.nRow /= 2; 3523 } 3586 } 3524 } 3587 } 3525 if( pc.plan.nRow<2 ) pc.plan.nRow = 2; 3588 if( pc.plan.nRow<2 ) pc.plan.nRow = 2; 3526 } 3589 } 3527 3590 ................................................................................................................................................................................ 4149 ** we reference multiple rows using a "rowid IN (...)" 4212 ** we reference multiple rows using a "rowid IN (...)" 4150 ** construct. 4213 ** construct. 4151 */ 4214 */ 4152 iReleaseReg = sqlite3GetTempReg(pParse); 4215 iReleaseReg = sqlite3GetTempReg(pParse); 4153 pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0); 4216 pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0); 4154 assert( pTerm!=0 ); 4217 assert( pTerm!=0 ); 4155 assert( pTerm->pExpr!=0 ); 4218 assert( pTerm->pExpr!=0 ); 4156 assert( pTerm->leftCursor==iCur ); < 4157 assert( omitTable==0 ); 4219 assert( omitTable==0 ); 4158 testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */ 4220 testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */ 4159 iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, iReleaseReg); 4221 iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, iReleaseReg); 4160 addrNxt = pLevel->addrNxt; 4222 addrNxt = pLevel->addrNxt; 4161 sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt); 4223 sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt); 4162 sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, iRowidReg); 4224 sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, iRowidReg); 4163 sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg); 4225 sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg); ................................................................................................................................................................................ 4540 int iRetInit; /* Address of regReturn init */ 4602 int iRetInit; /* Address of regReturn init */ 4541 int untestedTerms = 0; /* Some terms not completely tested */ 4603 int untestedTerms = 0; /* Some terms not completely tested */ 4542 int ii; /* Loop counter */ 4604 int ii; /* Loop counter */ 4543 Expr *pAndExpr = 0; /* An ".. AND (...)" expression */ 4605 Expr *pAndExpr = 0; /* An ".. AND (...)" expression */ 4544 4606 4545 pTerm = pLevel->plan.u.pTerm; 4607 pTerm = pLevel->plan.u.pTerm; 4546 assert( pTerm!=0 ); 4608 assert( pTerm!=0 ); 4547 assert( pTerm->eOperator==WO_OR ); | 4609 assert( pTerm->eOperator & WO_OR ); 4548 assert( (pTerm->wtFlags & TERM_ORINFO)!=0 ); 4610 assert( (pTerm->wtFlags & TERM_ORINFO)!=0 ); 4549 pOrWc = &pTerm->u.pOrInfo->wc; 4611 pOrWc = &pTerm->u.pOrInfo->wc; 4550 pLevel->op = OP_Return; 4612 pLevel->op = OP_Return; 4551 pLevel->p1 = regReturn; 4613 pLevel->p1 = regReturn; 4552 4614 4553 /* Set up a new SrcList in pOrTab containing the table being scanned 4615 /* Set up a new SrcList in pOrTab containing the table being scanned 4554 ** by this loop in the a[0] slot and all notReady tables in a[1..] slots. 4616 ** by this loop in the a[0] slot and all notReady tables in a[1..] slots. ................................................................................................................................................................................ 4613 if( pAndExpr ){ 4675 if( pAndExpr ){ 4614 pAndExpr = sqlite3PExpr(pParse, TK_AND, 0, pAndExpr, 0); 4676 pAndExpr = sqlite3PExpr(pParse, TK_AND, 0, pAndExpr, 0); 4615 } 4677 } 4616 } 4678 } 4617 4679 4618 for(ii=0; ii<pOrWc->nTerm; ii++){ 4680 for(ii=0; ii<pOrWc->nTerm; ii++){ 4619 WhereTerm *pOrTerm = &pOrWc->a[ii]; 4681 WhereTerm *pOrTerm = &pOrWc->a[ii]; 4620 if( pOrTerm->leftCursor==iCur || pOrTerm->eOperator==WO_AND ){ | 4682 if( pOrTerm->leftCursor==iCur || (pOrTerm->eOperator & WO_AND)!=0 ){ 4621 WhereInfo *pSubWInfo; /* Info for single OR-term scan */ 4683 WhereInfo *pSubWInfo; /* Info for single OR-term scan */ 4622 Expr *pOrExpr = pOrTerm->pExpr; 4684 Expr *pOrExpr = pOrTerm->pExpr; 4623 if( pAndExpr ){ 4685 if( pAndExpr ){ 4624 pAndExpr->pLeft = pOrExpr; 4686 pAndExpr->pLeft = pOrExpr; 4625 pOrExpr = pAndExpr; 4687 pOrExpr = pAndExpr; 4626 } 4688 } 4627 /* Loop through table entries that match term pOrTerm. */ 4689 /* Loop through table entries that match term pOrTerm. */
Changes to test/autoindex1.test
253 CREATE TABLE t5(a, b, c); 253 CREATE TABLE t5(a, b, c); 254 EXPLAIN QUERY PLAN SELECT a FROM t5 WHERE b=10 ORDER BY c; 254 EXPLAIN QUERY PLAN SELECT a FROM t5 WHERE b=10 ORDER BY c; 255 } { 255 } { 256 0 0 0 {SCAN TABLE t5 (~100000 rows)} 256 0 0 0 {SCAN TABLE t5 (~100000 rows)} 257 0 0 0 {USE TEMP B-TREE FOR ORDER BY} 257 0 0 0 {USE TEMP B-TREE FOR ORDER BY} 258 } 258 } 259 259 > 260 # The following checks a performance issue reported on the sqlite-dev > 261 # mailing list on 2013-01-10 260 | 262 # > 263 do_execsql_test autoindex1-800 { > 264 CREATE TABLE accounts( > 265 _id INTEGER PRIMARY KEY AUTOINCREMENT, > 266 account_name TEXT, > 267 account_type TEXT, > 268 data_set TEXT > 269 ); > 270 CREATE TABLE data( > 271 _id INTEGER PRIMARY KEY AUTOINCREMENT, > 272 package_id INTEGER REFERENCES package(_id), > 273 mimetype_id INTEGER REFERENCES mimetype(_id) NOT NULL, > 274 raw_contact_id INTEGER REFERENCES raw_contacts(_id) NOT NULL, > 275 is_read_only INTEGER NOT NULL DEFAULT 0, > 276 is_primary INTEGER NOT NULL DEFAULT 0, > 277 is_super_primary INTEGER NOT NULL DEFAULT 0, > 278 data_version INTEGER NOT NULL DEFAULT 0, > 279 data1 TEXT, > 280 data2 TEXT, > 281 data3 TEXT, > 282 data4 TEXT, > 283 data5 TEXT, > 284 data6 TEXT, > 285 data7 TEXT, > 286 data8 TEXT, > 287 data9 TEXT, > 288 data10 TEXT, > 289 data11 TEXT, > 290 data12 TEXT, > 291 data13 TEXT, > 292 data14 TEXT, > 293 data15 TEXT, > 294 data_sync1 TEXT, > 295 data_sync2 TEXT, > 296 data_sync3 TEXT, > 297 data_sync4 TEXT > 298 ); > 299 CREATE TABLE mimetypes( > 300 _id INTEGER PRIMARY KEY AUTOINCREMENT, > 301 mimetype TEXT NOT NULL > 302 ); > 303 CREATE TABLE raw_contacts( > 304 _id INTEGER PRIMARY KEY AUTOINCREMENT, > 305 account_id INTEGER REFERENCES accounts(_id), > 306 sourceid TEXT, > 307 raw_contact_is_read_only INTEGER NOT NULL DEFAULT 0, > 308 version INTEGER NOT NULL DEFAULT 1, > 309 dirty INTEGER NOT NULL DEFAULT 0, > 310 deleted INTEGER NOT NULL DEFAULT 0, > 311 contact_id INTEGER REFERENCES contacts(_id), > 312 aggregation_mode INTEGER NOT NULL DEFAULT 0, > 313 aggregation_needed INTEGER NOT NULL DEFAULT 1, > 314 custom_ringtone TEXT, > 315 send_to_voicemail INTEGER NOT NULL DEFAULT 0, > 316 times_contacted INTEGER NOT NULL DEFAULT 0, > 317 last_time_contacted INTEGER, > 318 starred INTEGER NOT NULL DEFAULT 0, > 319 display_name TEXT, > 320 display_name_alt TEXT, > 321 display_name_source INTEGER NOT NULL DEFAULT 0, > 322 phonetic_name TEXT, > 323 phonetic_name_style TEXT, > 324 sort_key TEXT, > 325 sort_key_alt TEXT, > 326 name_verified INTEGER NOT NULL DEFAULT 0, > 327 sync1 TEXT, > 328 sync2 TEXT, > 329 sync3 TEXT, > 330 sync4 TEXT, > 331 sync_uid TEXT, > 332 sync_version INTEGER NOT NULL DEFAULT 1, > 333 has_calendar_event INTEGER NOT NULL DEFAULT 0, > 334 modified_time INTEGER, > 335 is_restricted INTEGER DEFAULT 0, > 336 yp_source TEXT, > 337 method_selected INTEGER DEFAULT 0, > 338 custom_vibration_type INTEGER DEFAULT 0, > 339 custom_ringtone_path TEXT, > 340 message_notification TEXT, > 341 message_notification_path TEXT > 342 ); > 343 CREATE INDEX data_mimetype_data1_index ON data (mimetype_id,data1); > 344 CREATE INDEX data_raw_contact_id ON data (raw_contact_id); > 345 CREATE UNIQUE INDEX mime_type ON mimetypes (mimetype); > 346 CREATE INDEX raw_contact_sort_key1_index ON raw_contacts (sort_key); > 347 CREATE INDEX raw_contact_sort_key2_index ON raw_contacts (sort_key_alt); > 348 CREATE INDEX raw_contacts_contact_id_index ON raw_contacts (contact_id); > 349 CREATE INDEX raw_contacts_source_id_account_id_index > 350 ON raw_contacts (sourceid, account_id); > 351 ANALYZE sqlite_master; > 352 INSERT INTO sqlite_stat1 > 353 VALUES('raw_contacts','raw_contact_sort_key2_index','1600 4'); > 354 INSERT INTO sqlite_stat1 > 355 VALUES('raw_contacts','raw_contact_sort_key1_index','1600 4'); > 356 INSERT INTO sqlite_stat1 > 357 VALUES('raw_contacts','raw_contacts_source_id_account_id_index', > 358 '1600 1600 1600'); > 359 INSERT INTO sqlite_stat1 > 360 VALUES('raw_contacts','raw_contacts_contact_id_index','1600 1'); > 361 INSERT INTO sqlite_stat1 VALUES('mimetypes','mime_type','12 1'); > 362 INSERT INTO sqlite_stat1 > 363 VALUES('data','data_mimetype_data1_index','9819 2455 3'); > 364 INSERT INTO sqlite_stat1 VALUES('data','data_raw_contact_id','9819 7'); > 365 INSERT INTO sqlite_stat1 VALUES('accounts',NULL,'1'); > 366 DROP TABLE IF EXISTS sqlite_stat3; > 367 ANALYZE sqlite_master; > 368 > 369 EXPLAIN QUERY PLAN > 370 SELECT * FROM > 371 data JOIN mimetypes ON (data.mimetype_id=mimetypes._id) > 372 JOIN raw_contacts ON (data.raw_contact_id=raw_contacts._id) > 373 JOIN accounts ON (raw_contacts.account_id=accounts._id) > 374 WHERE mimetype_id=10 AND data14 IS NOT NULL; > 375 } {/SEARCH TABLE data .*SEARCH TABLE raw_contacts/} > 376 do_execsql_test autoindex1-801 { > 377 EXPLAIN QUERY PLAN > 378 SELECT * FROM > 379 data JOIN mimetypes ON (data.mimetype_id=mimetypes._id) > 380 JOIN raw_contacts ON (data.raw_contact_id=raw_contacts._id) > 381 JOIN accounts ON (raw_contacts.account_id=accounts._id) > 382 WHERE mimetypes._id=10 AND data14 IS NOT NULL; > 383 } {/SEARCH TABLE data .*SEARCH TABLE raw_contacts/} > 384 261 finish_test 385 finish_test
Added test/transitive1.test
> 1 # 2013 April 17 > 2 # > 3 # The author disclaims copyright to this source code. In place of > 4 # a legal notice, here is a blessing: > 5 # > 6 # May you do good and not evil. > 7 # May you find forgiveness for yourself and forgive others. > 8 # May you share freely, never taking more than you give. > 9 # > 10 #************************************************************************* > 11 # This file implements regression tests for SQLite library. The > 12 # focus of this script is testing of transitive WHERE clause constraints > 13 # > 14 > 15 set testdir [file dirname $argv0] > 16 source $testdir/tester.tcl > 17 > 18 do_execsql_test transitive1-100 { > 19 CREATE TABLE t1(a TEXT, b TEXT, c TEXT COLLATE NOCASE); > 20 INSERT INTO t1 VALUES('abc','abc','Abc'); > 21 INSERT INTO t1 VALUES('def','def','def'); > 22 INSERT INTO t1 VALUES('ghi','ghi','GHI'); > 23 CREATE INDEX t1a1 ON t1(a); > 24 CREATE INDEX t1a2 ON t1(a COLLATE nocase); > 25 > 26 SELECT * FROM t1 WHERE a=b AND c=b AND c='DEF'; > 27 } {def def def} > 28 do_execsql_test transitive1-110 { > 29 SELECT * FROM t1 WHERE a=b AND c=b AND c>='DEF' ORDER BY +a; > 30 } {def def def ghi ghi GHI} > 31 do_execsql_test transitive1-120 { > 32 SELECT * FROM t1 WHERE a=b AND c=b AND c<='DEF' ORDER BY +a; > 33 } {abc abc Abc def def def} > 34 > 35 do_execsql_test transitive1-200 { > 36 CREATE TABLE t2(a INTEGER, b INTEGER, c TEXT); > 37 INSERT INTO t2 VALUES(100,100,100); > 38 INSERT INTO t2 VALUES(20,20,20); > 39 INSERT INTO t2 VALUES(3,3,3); > 40 > 41 SELECT * FROM t2 WHERE a=b AND c=b AND c=20; > 42 } {20 20 20} > 43 do_execsql_test transitive1-210 { > 44 SELECT * FROM t2 WHERE a=b AND c=b AND c>=20 ORDER BY +a; > 45 } {3 3 3 20 20 20} > 46 do_execsql_test transitive1-220 { > 47 SELECT * FROM t2 WHERE a=b AND c=b AND c<=20 ORDER BY +a; > 48 } {20 20 20 100 100 100} > 49 > 50 finish_test