Index: src/sqliteInt.h ================================================================== --- src/sqliteInt.h +++ src/sqliteInt.h @@ -573,10 +573,15 @@ ** A convenience macro that returns the number of elements in ** an array. */ #define ArraySize(X) ((int)(sizeof(X)/sizeof(X[0]))) +/* +** Determine if the argument is a power of two +*/ +#define IsPowerOfTwo(X) (((X)&((X)-1))==0) + /* ** The following value as a destructor means to use sqlite3DbFree(). ** The sqlite3DbFree() routine requires two parameters instead of the ** one parameter that destructors normally want. So we have to introduce ** this magic value that the code knows to handle differently. Any @@ -971,10 +976,11 @@ #define SQLITE_IdxRealAsInt 0x0010 /* Store REAL as INT in indices */ #define SQLITE_DistinctOpt 0x0020 /* DISTINCT using indexes */ #define SQLITE_CoverIdxScan 0x0040 /* Covering index scans */ #define SQLITE_OrderByIdxJoin 0x0080 /* ORDER BY of joins via index */ #define SQLITE_SubqCoroutine 0x0100 /* Evaluate subqueries as coroutines */ +#define SQLITE_Transitive 0x0200 /* Transitive constraints */ #define SQLITE_AllOpts 0xffff /* All optimizations */ /* ** Macros for testing whether or not optimizations are enabled or disabled. */ Index: src/where.c ================================================================== --- src/where.c +++ src/where.c @@ -96,12 +96,12 @@ Expr *pExpr; /* Pointer to the subexpression that is this term */ int iParent; /* Disable pWC->a[iParent] when this term disabled */ int leftCursor; /* Cursor number of X in "X " */ union { int leftColumn; /* Column number of X in "X " */ - WhereOrInfo *pOrInfo; /* Extra information if eOperator==WO_OR */ - WhereAndInfo *pAndInfo; /* Extra information if eOperator==WO_AND */ + WhereOrInfo *pOrInfo; /* Extra information if (eOperator & WO_OR)!=0 */ + WhereAndInfo *pAndInfo; /* Extra information if (eOperator& WO_AND)!=0 */ } u; u16 eOperator; /* A WO_xx value describing */ u8 wtFlags; /* TERM_xxx bit flags. See below */ u8 nChild; /* Number of children that must disable us */ WhereClause *pWC; /* The clause this term is part of */ @@ -225,10 +225,11 @@ #define WO_GE (WO_EQ<<(TK_GE-TK_EQ)) #define WO_MATCH 0x040 #define WO_ISNULL 0x080 #define WO_OR 0x100 /* Two or more OR-connected terms */ #define WO_AND 0x200 /* Two or more AND-connected terms */ +#define WO_EQUIV 0x400 /* Of the form A==B, both columns */ #define WO_NOOP 0x800 /* This term does not restrict search space */ #define WO_ALL 0xfff /* Mask of all possible WO_* values */ #define WO_SINGLE 0x0ff /* Mask of all non-compound WO_* values */ @@ -627,58 +628,112 @@ /* ** Search for a term in the WHERE clause that is of the form "X " ** where X is a reference to the iColumn of table iCur and is one of ** the WO_xx operator codes specified by the op parameter. ** Return a pointer to the term. Return 0 if not found. +** +** The term returned might by Y= if there is another constraint in +** the WHERE clause that specifies that X=Y. Any such constraints will be +** identified by the WO_EQUIV bit in the pTerm->eOperator field. The +** aEquiv[] array holds X and all its equivalents, with each SQL variable +** taking up two slots in aEquiv[]. The first slot is for the cursor number +** and the second is for the column number. There are 22 slots in aEquiv[] +** so that means we can look for X plus up to 10 other equivalent values. +** Hence a search for X will return if X=A1 and A1=A2 and A2=A3 +** and ... and A9=A10 and A10=. +** +** If there are multiple terms in the WHERE clause of the form "X " +** then try for the one with no dependencies on - in other words where +** is a constant expression of some kind. Only return entries of +** the form "X Y" where Y is a column in another table if no terms of +** the form "X " exist. Other than this priority, if there +** are two or more terms that match, then the choice of which term to return +** is arbitrary. */ static WhereTerm *findTerm( WhereClause *pWC, /* The WHERE clause to be searched */ int iCur, /* Cursor number of LHS */ int iColumn, /* Column number of LHS */ Bitmask notReady, /* RHS must not overlap with this mask */ u32 op, /* Mask of WO_xx values describing operator */ Index *pIdx /* Must be compatible with this index, if not NULL */ ){ - WhereTerm *pTerm; - int k; + WhereTerm *pTerm; /* Term being examined as possible result */ + WhereTerm *pResult = 0; /* The answer to return */ + WhereClause *pWCOrig = pWC; /* Original pWC value */ + int j, k; /* Loop counters */ + Expr *pX; /* Pointer to an expression */ + Parse *pParse; /* Parsing context */ + int iOrigCol = iColumn; /* Original value of iColumn */ + int nEquiv = 2; /* Number of entires in aEquiv[] */ + int iEquiv = 2; /* Number of entries of aEquiv[] processed so far */ + int aEquiv[22]; /* iCur,iColumn and up to 10 other equivalents */ + assert( iCur>=0 ); - op &= WO_ALL; - for(; pWC; pWC=pWC->pOuter){ - for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){ - if( pTerm->leftCursor==iCur - && (pTerm->prereqRight & notReady)==0 - && pTerm->u.leftColumn==iColumn - && (pTerm->eOperator & op)!=0 - ){ - if( iColumn>=0 && pIdx && pTerm->eOperator!=WO_ISNULL ){ - Expr *pX = pTerm->pExpr; - CollSeq *pColl; - char idxaff; - int j; - Parse *pParse = pWC->pParse; - - idxaff = pIdx->pTable->aCol[iColumn].affinity; - if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue; - - /* Figure out the collation sequence required from an index for - ** it to be useful for optimising expression pX. Store this - ** value in variable pColl. - */ - assert(pX->pLeft); - pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight); - if( pColl==0 ) pColl = pParse->db->pDfltColl; - - for(j=0; pIdx->aiColumn[j]!=iColumn; j++){ - if( NEVER(j>=pIdx->nColumn) ) return 0; - } - if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue; - } - return pTerm; - } - } - } - return 0; + aEquiv[0] = iCur; + aEquiv[1] = iColumn; + for(;;){ + for(pWC=pWCOrig; pWC; pWC=pWC->pOuter){ + for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){ + if( pTerm->leftCursor==iCur + && pTerm->u.leftColumn==iColumn + ){ + if( (pTerm->prereqRight & notReady)==0 + && (pTerm->eOperator & op & WO_ALL)!=0 + ){ + if( iOrigCol>=0 && pIdx && (pTerm->eOperator & WO_ISNULL)==0 ){ + CollSeq *pColl; + char idxaff; + + pX = pTerm->pExpr; + pParse = pWC->pParse; + idxaff = pIdx->pTable->aCol[iOrigCol].affinity; + if( !sqlite3IndexAffinityOk(pX, idxaff) ){ + continue; + } + + /* Figure out the collation sequence required from an index for + ** it to be useful for optimising expression pX. Store this + ** value in variable pColl. + */ + assert(pX->pLeft); + pColl = sqlite3BinaryCompareCollSeq(pParse,pX->pLeft,pX->pRight); + if( pColl==0 ) pColl = pParse->db->pDfltColl; + + for(j=0; pIdx->aiColumn[j]!=iOrigCol; j++){ + if( NEVER(j>=pIdx->nColumn) ) return 0; + } + if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ){ + continue; + } + } + pResult = pTerm; + if( pTerm->prereqRight==0 ) goto findTerm_success; + } + if( (pTerm->eOperator & WO_EQUIV)!=0 + && nEquivpExpr->pRight); + assert( pX->op==TK_COLUMN ); + for(j=0; jiTable && aEquiv[j+1]==pX->iColumn ) break; + } + if( j==nEquiv ){ + aEquiv[j] = pX->iTable; + aEquiv[j+1] = pX->iColumn; + nEquiv += 2; + } + } + } + } + } + if( iEquiv>=nEquiv ) break; + iCur = aEquiv[iEquiv++]; + iColumn = aEquiv[iEquiv++]; + } +findTerm_success: + return pResult; } /* Forward reference */ static void exprAnalyze(SrcList*, WhereClause*, int); @@ -952,11 +1007,10 @@ indexable = ~(Bitmask)0; chngToIN = ~(pWC->vmask); for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0 && indexable; i--, pOrTerm++){ if( (pOrTerm->eOperator & WO_SINGLE)==0 ){ WhereAndInfo *pAndInfo; - assert( pOrTerm->eOperator==0 ); assert( (pOrTerm->wtFlags & (TERM_ANDINFO|TERM_ORINFO))==0 ); chngToIN = 0; pAndInfo = sqlite3DbMallocRaw(db, sizeof(*pAndInfo)); if( pAndInfo ){ WhereClause *pAndWC; @@ -991,11 +1045,11 @@ if( pOrTerm->wtFlags & TERM_VIRTUAL ){ WhereTerm *pOther = &pOrWc->a[pOrTerm->iParent]; b |= getMask(pMaskSet, pOther->leftCursor); } indexable &= b; - if( pOrTerm->eOperator!=WO_EQ ){ + if( (pOrTerm->eOperator & WO_EQ)==0 ){ chngToIN = 0; }else{ chngToIN &= b; } } @@ -1042,11 +1096,11 @@ ** and column is found but leave okToChngToIN false if not found. */ for(j=0; j<2 && !okToChngToIN; j++){ pOrTerm = pOrWc->a; for(i=pOrWc->nTerm-1; i>=0; i--, pOrTerm++){ - assert( pOrTerm->eOperator==WO_EQ ); + assert( pOrTerm->eOperator & WO_EQ ); pOrTerm->wtFlags &= ~TERM_OR_OK; if( pOrTerm->leftCursor==iCursor ){ /* This is the 2-bit case and we are on the second iteration and ** current term is from the first iteration. So skip this term. */ assert( j==1 ); @@ -1068,21 +1122,21 @@ } if( i<0 ){ /* No candidate table+column was found. This can only occur ** on the second iteration */ assert( j==1 ); - assert( (chngToIN&(chngToIN-1))==0 ); + assert( IsPowerOfTwo(chngToIN) ); assert( chngToIN==getMask(pMaskSet, iCursor) ); break; } testcase( j==1 ); /* We have found a candidate table and column. Check to see if that ** table and column is common to every term in the OR clause */ okToChngToIN = 1; for(; i>=0 && okToChngToIN; i--, pOrTerm++){ - assert( pOrTerm->eOperator==WO_EQ ); + assert( pOrTerm->eOperator & WO_EQ ); if( pOrTerm->leftCursor!=iCursor ){ pOrTerm->wtFlags &= ~TERM_OR_OK; }else if( pOrTerm->u.leftColumn!=iColumn ){ okToChngToIN = 0; }else{ @@ -1114,11 +1168,11 @@ Expr *pLeft = 0; /* The LHS of the IN operator */ Expr *pNew; /* The complete IN operator */ for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0; i--, pOrTerm++){ if( (pOrTerm->wtFlags & TERM_OR_OK)==0 ) continue; - assert( pOrTerm->eOperator==WO_EQ ); + assert( pOrTerm->eOperator & WO_EQ ); assert( pOrTerm->leftCursor==iCursor ); assert( pOrTerm->u.leftColumn==iColumn ); pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight, 0); pList = sqlite3ExprListAppend(pWC->pParse, pList, pDup); pLeft = pOrTerm->pExpr->pLeft; @@ -1143,11 +1197,10 @@ pTerm->eOperator = WO_NOOP; /* case 1 trumps case 2 */ } } } #endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */ - /* ** The input to this routine is an WhereTerm structure with only the ** "pExpr" field filled in. The job of this routine is to analyze the ** subexpression and populate all the other fields of the WhereTerm @@ -1213,21 +1266,23 @@ } pTerm->prereqAll = prereqAll; pTerm->leftCursor = -1; pTerm->iParent = -1; pTerm->eOperator = 0; - if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){ + if( allowedOp(op) ){ Expr *pLeft = sqlite3ExprSkipCollate(pExpr->pLeft); Expr *pRight = sqlite3ExprSkipCollate(pExpr->pRight); + u16 opMask = (pTerm->prereqRight & prereqLeft)==0 ? WO_ALL : WO_EQUIV; if( pLeft->op==TK_COLUMN ){ pTerm->leftCursor = pLeft->iTable; pTerm->u.leftColumn = pLeft->iColumn; - pTerm->eOperator = operatorMask(op); + pTerm->eOperator = operatorMask(op) & opMask; } if( pRight && pRight->op==TK_COLUMN ){ WhereTerm *pNew; Expr *pDup; + u16 eExtraOp = 0; /* Extra bits for pNew->eOperator */ if( pTerm->leftCursor>=0 ){ int idxNew; pDup = sqlite3ExprDup(db, pExpr, 0); if( db->mallocFailed ){ sqlite3ExprDelete(db, pDup); @@ -1238,10 +1293,17 @@ pNew = &pWC->a[idxNew]; pNew->iParent = idxTerm; pTerm = &pWC->a[idxTerm]; pTerm->nChild = 1; pTerm->wtFlags |= TERM_COPIED; + if( pExpr->op==TK_EQ + && !ExprHasProperty(pExpr, EP_FromJoin) + && OptimizationEnabled(db, SQLITE_Transitive) + ){ + pTerm->eOperator |= WO_EQUIV; + eExtraOp = WO_EQUIV; + } }else{ pDup = pExpr; pNew = pTerm; } exprCommute(pParse, pDup); @@ -1249,11 +1311,11 @@ pNew->leftCursor = pLeft->iTable; pNew->u.leftColumn = pLeft->iColumn; testcase( (prereqLeft | extraRight) != prereqLeft ); pNew->prereqRight = prereqLeft | extraRight; pNew->prereqAll = prereqAll; - pNew->eOperator = operatorMask(pDup->op); + pNew->eOperator = (operatorMask(pDup->op) + eExtraOp) & opMask; } } #ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION /* If a term is the BETWEEN operator, create two new virtual terms @@ -1708,11 +1770,11 @@ return; } /* Search the WHERE clause terms for a usable WO_OR term. */ for(pTerm=pWC->a; pTermeOperator==WO_OR + if( (pTerm->eOperator & WO_OR)!=0 && ((pTerm->prereqAll & ~maskSrc) & p->notReady)==0 && (pTerm->u.pOrInfo->indexable & maskSrc)!=0 ){ WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc; WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm]; @@ -1729,11 +1791,11 @@ sBOI.ppIdxInfo = 0; for(pOrTerm=pOrWC->a; pOrTerma), (pTerm - pWC->a) )); - if( pOrTerm->eOperator==WO_AND ){ + if( (pOrTerm->eOperator& WO_AND)!=0 ){ sBOI.pWC = &pOrTerm->u.pAndInfo->wc; bestIndex(&sBOI); }else if( pOrTerm->leftCursor==iCur ){ WhereClause tempWC; tempWC.pParse = pWC->pParse; @@ -1790,11 +1852,11 @@ struct SrcList_item *pSrc, /* Table we are trying to access */ Bitmask notReady /* Tables in outer loops of the join */ ){ char aff; if( pTerm->leftCursor!=pSrc->iCursor ) return 0; - if( pTerm->eOperator!=WO_EQ ) return 0; + if( (pTerm->eOperator & WO_EQ)==0 ) return 0; if( (pTerm->prereqRight & notReady)!=0 ) return 0; aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity; if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0; return 1; } @@ -2052,13 +2114,13 @@ /* Count the number of possible WHERE clause constraints referring ** to this virtual table */ for(i=nTerm=0, pTerm=pWC->a; inTerm; i++, pTerm++){ if( pTerm->leftCursor != pSrc->iCursor ) continue; - assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 ); - testcase( pTerm->eOperator==WO_IN ); - testcase( pTerm->eOperator==WO_ISNULL ); + assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) ); + testcase( pTerm->eOperator & WO_IN ); + testcase( pTerm->eOperator & WO_ISNULL ); if( pTerm->eOperator & (WO_ISNULL) ) continue; if( pTerm->wtFlags & TERM_VNULL ) continue; nTerm++; } @@ -2105,18 +2167,18 @@ pUsage; for(i=j=0, pTerm=pWC->a; inTerm; i++, pTerm++){ u8 op; if( pTerm->leftCursor != pSrc->iCursor ) continue; - assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 ); - testcase( pTerm->eOperator==WO_IN ); - testcase( pTerm->eOperator==WO_ISNULL ); + assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) ); + testcase( pTerm->eOperator & WO_IN ); + testcase( pTerm->eOperator & WO_ISNULL ); if( pTerm->eOperator & (WO_ISNULL) ) continue; if( pTerm->wtFlags & TERM_VNULL ) continue; pIdxCons[j].iColumn = pTerm->u.leftColumn; pIdxCons[j].iTermOffset = i; - op = (u8)pTerm->eOperator; + op = (u8)pTerm->eOperator & WO_ALL; if( op==WO_IN ) op = WO_EQ; pIdxCons[j].op = op; /* The direct assignment in the previous line is possible only because ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical. The ** following asserts verify this fact. */ @@ -2282,11 +2344,11 @@ pUsage = pIdxInfo->aConstraintUsage; for(i=0; inConstraint; i++, pIdxCons++){ j = pIdxCons->iTermOffset; pTerm = &pWC->a[j]; if( (pTerm->prereqRight&p->notReady)==0 - && (bAllowIN || pTerm->eOperator!=WO_IN) + && (bAllowIN || (pTerm->eOperator & WO_IN)==0) ){ pIdxCons->usable = 1; }else{ pIdxCons->usable = 0; } @@ -2314,11 +2376,11 @@ for(i=0; inConstraint; i++, pIdxCons++){ if( pUsage[i].argvIndex>0 ){ j = pIdxCons->iTermOffset; pTerm = &pWC->a[j]; p->cost.used |= pTerm->prereqRight; - if( pTerm->eOperator==WO_IN && pUsage[i].omit==0 ){ + if( (pTerm->eOperator & WO_IN)!=0 && pUsage[i].omit==0 ){ /* Do not attempt to use an IN constraint if the virtual table ** says that the equivalent EQ constraint cannot be safely omitted. ** If we do attempt to use such a constraint, some rows might be ** repeated in the output. */ break; @@ -2620,28 +2682,28 @@ u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity; if( pLower ){ Expr *pExpr = pLower->pExpr->pRight; rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal); - assert( pLower->eOperator==WO_GT || pLower->eOperator==WO_GE ); + assert( (pLower->eOperator & (WO_GT|WO_GE))!=0 ); if( rc==SQLITE_OK && whereKeyStats(pParse, p, pRangeVal, 0, a)==SQLITE_OK ){ iLower = a[0]; - if( pLower->eOperator==WO_GT ) iLower += a[1]; + if( (pLower->eOperator & WO_GT)!=0 ) iLower += a[1]; } sqlite3ValueFree(pRangeVal); } if( rc==SQLITE_OK && pUpper ){ Expr *pExpr = pUpper->pExpr->pRight; rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal); - assert( pUpper->eOperator==WO_LT || pUpper->eOperator==WO_LE ); + assert( (pUpper->eOperator & (WO_LT|WO_LE))!=0 ); if( rc==SQLITE_OK && whereKeyStats(pParse, p, pRangeVal, 1, a)==SQLITE_OK ){ iUpper = a[0]; - if( pUpper->eOperator==WO_LE ) iUpper += a[1]; + if( (pUpper->eOperator & WO_LE)!=0 ) iUpper += a[1]; } sqlite3ValueFree(pRangeVal); } if( rc==SQLITE_OK ){ if( iUpper<=iLower ){ @@ -2945,16 +3007,16 @@ ** if there are any X= or X IS NULL constraints in the WHERE clause. */ pConstraint = findTerm(p->pWC, base, iColumn, p->notReady, WO_EQ|WO_ISNULL|WO_IN, pIdx); if( pConstraint==0 ){ isEq = 0; - }else if( pConstraint->eOperator==WO_IN ){ + }else if( (pConstraint->eOperator & WO_IN)!=0 ){ /* Constraints of the form: "X IN ..." cannot be used with an ORDER BY ** because we do not know in what order the values on the RHS of the IN ** operator will occur. */ break; - }else if( pConstraint->eOperator==WO_ISNULL ){ + }else if( (pConstraint->eOperator & WO_ISNULL)!=0 ){ uniqueNotNull = 0; isEq = 1; /* "X IS NULL" means X has only a single value */ }else if( pConstraint->prereqRight==0 ){ isEq = 1; /* Constraint "X=constant" means X has only a single value */ }else{ @@ -3363,16 +3425,17 @@ */ if( pc.plan.nRow>(double)1 && pc.plan.nEq==1 && pFirstTerm!=0 && aiRowEst[1]>1 ){ assert( (pFirstTerm->eOperator & (WO_EQ|WO_ISNULL|WO_IN))!=0 ); if( pFirstTerm->eOperator & (WO_EQ|WO_ISNULL) ){ - testcase( pFirstTerm->eOperator==WO_EQ ); - testcase( pFirstTerm->eOperator==WO_ISNULL ); + testcase( pFirstTerm->eOperator & WO_EQ ); + testcase( pFirstTerm->eOperator & WO_EQUIV ); + testcase( pFirstTerm->eOperator & WO_ISNULL ); whereEqualScanEst(pParse, pProbe, pFirstTerm->pExpr->pRight, &pc.plan.nRow); }else if( bInEst==0 ){ - assert( pFirstTerm->eOperator==WO_IN ); + assert( pFirstTerm->eOperator & WO_IN ); whereInScanEst(pParse, pProbe, pFirstTerm->pExpr->x.pList, &pc.plan.nRow); } } #endif /* SQLITE_ENABLE_STAT3 */ @@ -3515,11 +3578,11 @@ ** more selective intentionally because of the subjective ** observation that indexed range constraints really are more ** selective in practice, on average. */ pc.plan.nRow /= 3; } - }else if( pTerm->eOperator!=WO_NOOP ){ + }else if( (pTerm->eOperator & WO_NOOP)==0 ){ /* Any other expression lowers the output row count by half */ pc.plan.nRow /= 2; } } if( pc.plan.nRow<2 ) pc.plan.nRow = 2; @@ -4151,11 +4214,10 @@ */ iReleaseReg = sqlite3GetTempReg(pParse); pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0); assert( pTerm!=0 ); assert( pTerm->pExpr!=0 ); - assert( pTerm->leftCursor==iCur ); assert( omitTable==0 ); testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */ iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, iReleaseReg); addrNxt = pLevel->addrNxt; sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt); @@ -4542,11 +4604,11 @@ int ii; /* Loop counter */ Expr *pAndExpr = 0; /* An ".. AND (...)" expression */ pTerm = pLevel->plan.u.pTerm; assert( pTerm!=0 ); - assert( pTerm->eOperator==WO_OR ); + assert( pTerm->eOperator & WO_OR ); assert( (pTerm->wtFlags & TERM_ORINFO)!=0 ); pOrWc = &pTerm->u.pOrInfo->wc; pLevel->op = OP_Return; pLevel->p1 = regReturn; @@ -4615,11 +4677,11 @@ } } for(ii=0; iinTerm; ii++){ WhereTerm *pOrTerm = &pOrWc->a[ii]; - if( pOrTerm->leftCursor==iCur || pOrTerm->eOperator==WO_AND ){ + if( pOrTerm->leftCursor==iCur || (pOrTerm->eOperator & WO_AND)!=0 ){ WhereInfo *pSubWInfo; /* Info for single OR-term scan */ Expr *pOrExpr = pOrTerm->pExpr; if( pAndExpr ){ pAndExpr->pLeft = pOrExpr; pOrExpr = pAndExpr; Index: test/autoindex1.test ================================================================== --- test/autoindex1.test +++ test/autoindex1.test @@ -255,7 +255,131 @@ } { 0 0 0 {SCAN TABLE t5 (~100000 rows)} 0 0 0 {USE TEMP B-TREE FOR ORDER BY} } +# The following checks a performance issue reported on the sqlite-dev +# mailing list on 2013-01-10 +# +do_execsql_test autoindex1-800 { + CREATE TABLE accounts( + _id INTEGER PRIMARY KEY AUTOINCREMENT, + account_name TEXT, + account_type TEXT, + data_set TEXT + ); + CREATE TABLE data( + _id INTEGER PRIMARY KEY AUTOINCREMENT, + package_id INTEGER REFERENCES package(_id), + mimetype_id INTEGER REFERENCES mimetype(_id) NOT NULL, + raw_contact_id INTEGER REFERENCES raw_contacts(_id) NOT NULL, + is_read_only INTEGER NOT NULL DEFAULT 0, + is_primary INTEGER NOT NULL DEFAULT 0, + is_super_primary INTEGER NOT NULL DEFAULT 0, + data_version INTEGER NOT NULL DEFAULT 0, + data1 TEXT, + data2 TEXT, + data3 TEXT, + data4 TEXT, + data5 TEXT, + data6 TEXT, + data7 TEXT, + data8 TEXT, + data9 TEXT, + data10 TEXT, + data11 TEXT, + data12 TEXT, + data13 TEXT, + data14 TEXT, + data15 TEXT, + data_sync1 TEXT, + data_sync2 TEXT, + data_sync3 TEXT, + data_sync4 TEXT + ); + CREATE TABLE mimetypes( + _id INTEGER PRIMARY KEY AUTOINCREMENT, + mimetype TEXT NOT NULL + ); + CREATE TABLE raw_contacts( + _id INTEGER PRIMARY KEY AUTOINCREMENT, + account_id INTEGER REFERENCES accounts(_id), + sourceid TEXT, + raw_contact_is_read_only INTEGER NOT NULL DEFAULT 0, + version INTEGER NOT NULL DEFAULT 1, + dirty INTEGER NOT NULL DEFAULT 0, + deleted INTEGER NOT NULL DEFAULT 0, + contact_id INTEGER REFERENCES contacts(_id), + aggregation_mode INTEGER NOT NULL DEFAULT 0, + aggregation_needed INTEGER NOT NULL DEFAULT 1, + custom_ringtone TEXT, + send_to_voicemail INTEGER NOT NULL DEFAULT 0, + times_contacted INTEGER NOT NULL DEFAULT 0, + last_time_contacted INTEGER, + starred INTEGER NOT NULL DEFAULT 0, + display_name TEXT, + display_name_alt TEXT, + display_name_source INTEGER NOT NULL DEFAULT 0, + phonetic_name TEXT, + phonetic_name_style TEXT, + sort_key TEXT, + sort_key_alt TEXT, + name_verified INTEGER NOT NULL DEFAULT 0, + sync1 TEXT, + sync2 TEXT, + sync3 TEXT, + sync4 TEXT, + sync_uid TEXT, + sync_version INTEGER NOT NULL DEFAULT 1, + has_calendar_event INTEGER NOT NULL DEFAULT 0, + modified_time INTEGER, + is_restricted INTEGER DEFAULT 0, + yp_source TEXT, + method_selected INTEGER DEFAULT 0, + custom_vibration_type INTEGER DEFAULT 0, + custom_ringtone_path TEXT, + message_notification TEXT, + message_notification_path TEXT + ); + CREATE INDEX data_mimetype_data1_index ON data (mimetype_id,data1); + CREATE INDEX data_raw_contact_id ON data (raw_contact_id); + CREATE UNIQUE INDEX mime_type ON mimetypes (mimetype); + CREATE INDEX raw_contact_sort_key1_index ON raw_contacts (sort_key); + CREATE INDEX raw_contact_sort_key2_index ON raw_contacts (sort_key_alt); + CREATE INDEX raw_contacts_contact_id_index ON raw_contacts (contact_id); + CREATE INDEX raw_contacts_source_id_account_id_index + ON raw_contacts (sourceid, account_id); + ANALYZE sqlite_master; + INSERT INTO sqlite_stat1 + VALUES('raw_contacts','raw_contact_sort_key2_index','1600 4'); + INSERT INTO sqlite_stat1 + VALUES('raw_contacts','raw_contact_sort_key1_index','1600 4'); + INSERT INTO sqlite_stat1 + VALUES('raw_contacts','raw_contacts_source_id_account_id_index', + '1600 1600 1600'); + INSERT INTO sqlite_stat1 + VALUES('raw_contacts','raw_contacts_contact_id_index','1600 1'); + INSERT INTO sqlite_stat1 VALUES('mimetypes','mime_type','12 1'); + INSERT INTO sqlite_stat1 + VALUES('data','data_mimetype_data1_index','9819 2455 3'); + INSERT INTO sqlite_stat1 VALUES('data','data_raw_contact_id','9819 7'); + INSERT INTO sqlite_stat1 VALUES('accounts',NULL,'1'); + DROP TABLE IF EXISTS sqlite_stat3; + ANALYZE sqlite_master; + + EXPLAIN QUERY PLAN + SELECT * FROM + data JOIN mimetypes ON (data.mimetype_id=mimetypes._id) + JOIN raw_contacts ON (data.raw_contact_id=raw_contacts._id) + JOIN accounts ON (raw_contacts.account_id=accounts._id) + WHERE mimetype_id=10 AND data14 IS NOT NULL; +} {/SEARCH TABLE data .*SEARCH TABLE raw_contacts/} +do_execsql_test autoindex1-801 { + EXPLAIN QUERY PLAN + SELECT * FROM + data JOIN mimetypes ON (data.mimetype_id=mimetypes._id) + JOIN raw_contacts ON (data.raw_contact_id=raw_contacts._id) + JOIN accounts ON (raw_contacts.account_id=accounts._id) + WHERE mimetypes._id=10 AND data14 IS NOT NULL; +} {/SEARCH TABLE data .*SEARCH TABLE raw_contacts/} finish_test ADDED test/transitive1.test Index: test/transitive1.test ================================================================== --- /dev/null +++ test/transitive1.test @@ -0,0 +1,50 @@ +# 2013 April 17 +# +# The author disclaims copyright to this source code. In place of +# a legal notice, here is a blessing: +# +# May you do good and not evil. +# May you find forgiveness for yourself and forgive others. +# May you share freely, never taking more than you give. +# +#************************************************************************* +# This file implements regression tests for SQLite library. The +# focus of this script is testing of transitive WHERE clause constraints +# + +set testdir [file dirname $argv0] +source $testdir/tester.tcl + +do_execsql_test transitive1-100 { + CREATE TABLE t1(a TEXT, b TEXT, c TEXT COLLATE NOCASE); + INSERT INTO t1 VALUES('abc','abc','Abc'); + INSERT INTO t1 VALUES('def','def','def'); + INSERT INTO t1 VALUES('ghi','ghi','GHI'); + CREATE INDEX t1a1 ON t1(a); + CREATE INDEX t1a2 ON t1(a COLLATE nocase); + + SELECT * FROM t1 WHERE a=b AND c=b AND c='DEF'; +} {def def def} +do_execsql_test transitive1-110 { + SELECT * FROM t1 WHERE a=b AND c=b AND c>='DEF' ORDER BY +a; +} {def def def ghi ghi GHI} +do_execsql_test transitive1-120 { + SELECT * FROM t1 WHERE a=b AND c=b AND c<='DEF' ORDER BY +a; +} {abc abc Abc def def def} + +do_execsql_test transitive1-200 { + CREATE TABLE t2(a INTEGER, b INTEGER, c TEXT); + INSERT INTO t2 VALUES(100,100,100); + INSERT INTO t2 VALUES(20,20,20); + INSERT INTO t2 VALUES(3,3,3); + + SELECT * FROM t2 WHERE a=b AND c=b AND c=20; +} {20 20 20} +do_execsql_test transitive1-210 { + SELECT * FROM t2 WHERE a=b AND c=b AND c>=20 ORDER BY +a; +} {3 3 3 20 20 20} +do_execsql_test transitive1-220 { + SELECT * FROM t2 WHERE a=b AND c=b AND c<=20 ORDER BY +a; +} {20 20 20 100 100 100} + +finish_test