diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/func.c | 5 | ||||
-rw-r--r-- | src/select.c | 19 | ||||
-rw-r--r-- | src/vdbe.c | 72 | ||||
-rw-r--r-- | src/where.c | 133 | ||||
-rw-r--r-- | src/whereInt.h | 7 |
5 files changed, 195 insertions, 41 deletions
diff --git a/src/func.c b/src/func.c index 30990a30f..d917bdbec 100644 --- a/src/func.c +++ b/src/func.c @@ -1650,6 +1650,11 @@ void sqlite3RegisterLikeFunctions(sqlite3 *db, int caseSensitive){ ** then set aWc[0] through aWc[2] to the wildcard characters and ** return TRUE. If the function is not a LIKE-style function then ** return FALSE. +** +** *pIsNocase is set to true if uppercase and lowercase are equivalent for +** the function (default for LIKE). If the function makes the distinction +** between uppercase and lowercase (as does GLOB) then *pIsNocase is set to +** false. */ int sqlite3IsLikeFunction(sqlite3 *db, Expr *pExpr, int *pIsNocase, char *aWc){ FuncDef *pDef; diff --git a/src/select.c b/src/select.c index 91b3d4345..a9cecaa39 100644 --- a/src/select.c +++ b/src/select.c @@ -563,20 +563,17 @@ static void pushOntoSorter( } sqlite3VdbeAddOp2(v, op, pSort->iECursor, regRecord); if( pSelect->iLimit ){ - int addr1, addr2; + int addr; int iLimit; if( pSelect->iOffset ){ iLimit = pSelect->iOffset+1; }else{ iLimit = pSelect->iLimit; } - addr1 = sqlite3VdbeAddOp1(v, OP_IfZero, iLimit); VdbeCoverage(v); - sqlite3VdbeAddOp2(v, OP_AddImm, iLimit, -1); - addr2 = sqlite3VdbeAddOp0(v, OP_Goto); - sqlite3VdbeJumpHere(v, addr1); + addr = sqlite3VdbeAddOp3(v, OP_IfNotZero, iLimit, 0, -1); VdbeCoverage(v); sqlite3VdbeAddOp1(v, OP_Last, pSort->iECursor); sqlite3VdbeAddOp1(v, OP_Delete, pSort->iECursor); - sqlite3VdbeJumpHere(v, addr2); + sqlite3VdbeJumpHere(v, addr); } } @@ -973,7 +970,7 @@ static void selectInnerLoop( ** the output for us. */ if( pSort==0 && p->iLimit ){ - sqlite3VdbeAddOp3(v, OP_IfZero, p->iLimit, iBreak, -1); VdbeCoverage(v); + sqlite3VdbeAddOp2(v, OP_DecrJumpZero, p->iLimit, iBreak); VdbeCoverage(v); } } @@ -1826,7 +1823,7 @@ static void computeLimitRegisters(Parse *pParse, Select *p, int iBreak){ sqlite3ExprCode(pParse, p->pLimit, iLimit); sqlite3VdbeAddOp1(v, OP_MustBeInt, iLimit); VdbeCoverage(v); VdbeComment((v, "LIMIT counter")); - sqlite3VdbeAddOp2(v, OP_IfZero, iLimit, iBreak); VdbeCoverage(v); + sqlite3VdbeAddOp2(v, OP_IfNot, iLimit, iBreak); VdbeCoverage(v); } if( p->pOffset ){ p->iOffset = iOffset = ++pParse->nMem; @@ -2045,7 +2042,7 @@ static void generateWithRecursiveQuery( selectInnerLoop(pParse, p, p->pEList, iCurrent, 0, 0, pDest, addrCont, addrBreak); if( regLimit ){ - sqlite3VdbeAddOp3(v, OP_IfZero, regLimit, addrBreak, -1); + sqlite3VdbeAddOp2(v, OP_DecrJumpZero, regLimit, addrBreak); VdbeCoverage(v); } sqlite3VdbeResolveLabel(v, addrCont); @@ -2270,7 +2267,7 @@ static int multiSelect( p->iLimit = pPrior->iLimit; p->iOffset = pPrior->iOffset; if( p->iLimit ){ - addr = sqlite3VdbeAddOp1(v, OP_IfZero, p->iLimit); VdbeCoverage(v); + addr = sqlite3VdbeAddOp1(v, OP_IfNot, p->iLimit); VdbeCoverage(v); VdbeComment((v, "Jump ahead if LIMIT reached")); } explainSetInteger(iSub2, pParse->iNextSelectId); @@ -2671,7 +2668,7 @@ static int generateOutputSubroutine( /* Jump to the end of the loop if the LIMIT is reached. */ if( p->iLimit ){ - sqlite3VdbeAddOp3(v, OP_IfZero, p->iLimit, iBreak, -1); VdbeCoverage(v); + sqlite3VdbeAddOp2(v, OP_DecrJumpZero, p->iLimit, iBreak); VdbeCoverage(v); } /* Generate the subroutine return diff --git a/src/vdbe.c b/src/vdbe.c index 39a334f29..f81bfa8a7 100644 --- a/src/vdbe.c +++ b/src/vdbe.c @@ -1015,7 +1015,7 @@ case OP_Real: { /* same as TK_FLOAT, out2-prerelease */ ** Synopsis: r[P2]='P4' ** ** P4 points to a nul terminated UTF-8 string. This opcode is transformed -** into a String before it is executed for the first time. During +** into a String opcode before it is executed for the first time. During ** this transformation, the length of string P4 is computed and stored ** as the P1 parameter. */ @@ -1047,10 +1047,15 @@ case OP_String8: { /* same as TK_STRING, out2-prerelease */ /* Fall through to the next case, OP_String */ } -/* Opcode: String P1 P2 * P4 * +/* Opcode: String P1 P2 P3 P4 P5 ** Synopsis: r[P2]='P4' (len=P1) ** ** The string value P4 of length P1 (bytes) is stored in register P2. +** +** If P5!=0 and the content of register P3 is greater than zero, then +** the datatype of the register P2 is converted to BLOB. The content is +** the same sequence of bytes, it is merely interpreted as a BLOB instead +** of a string, as if it had been CAST. */ case OP_String: { /* out2-prerelease */ assert( pOp->p4.z!=0 ); @@ -1059,6 +1064,13 @@ case OP_String: { /* out2-prerelease */ pOut->n = pOp->p1; pOut->enc = encoding; UPDATE_MAX_BLOBSIZE(pOut); + if( pOp->p5 ){ + assert( pOp->p3>0 ); + assert( pOp->p3<=(p->nMem-p->nCursor) ); + pIn3 = &aMem[pOp->p3]; + assert( pIn3->flags & MEM_Int ); + if( pIn3->u.i ) pOut->flags = MEM_Blob|MEM_Static|MEM_Term; + } break; } @@ -5573,10 +5585,12 @@ case OP_MemMax: { /* in2 */ /* Opcode: IfPos P1 P2 * * * ** Synopsis: if r[P1]>0 goto P2 ** -** If the value of register P1 is 1 or greater, jump to P2. +** Register P1 must contain an integer. +** If the value of register P1 is 1 or greater, jump to P2 and +** add the literal value P3 to register P1. ** -** It is illegal to use this instruction on a register that does -** not contain an integer. An assertion fault will result if you try. +** If the initial value of register P1 is less than 1, then the +** value is unchanged and control passes through to the next instruction. */ case OP_IfPos: { /* jump, in1 */ pIn1 = &aMem[pOp->p1]; @@ -5605,16 +5619,34 @@ case OP_IfNeg: { /* jump, in1 */ break; } -/* Opcode: IfZero P1 P2 P3 * * -** Synopsis: r[P1]+=P3, if r[P1]==0 goto P2 +/* Opcode: IfNotZero P1 P2 P3 * * +** Synopsis: if r[P1]!=0 then r[P1]+=P3, goto P2 ** -** The register P1 must contain an integer. Add literal P3 to the -** value in register P1. If the result is exactly 0, jump to P2. +** Register P1 must contain an integer. If the content of register P1 is +** initially nonzero, then add P3 to P1 and jump to P2. If register P1 is +** initially zero, leave it unchanged and fall through. */ -case OP_IfZero: { /* jump, in1 */ +case OP_IfNotZero: { /* jump, in1 */ pIn1 = &aMem[pOp->p1]; assert( pIn1->flags&MEM_Int ); - pIn1->u.i += pOp->p3; + VdbeBranchTaken(pIn1->u.i<0, 2); + if( pIn1->u.i ){ + pIn1->u.i += pOp->p3; + pc = pOp->p2 - 1; + } + break; +} + +/* Opcode: DecrJumpZero P1 P2 * * * +** Synopsis: if (--r[P1])==0 goto P2 +** +** Register P1 must hold an integer. Decrement the value in register P1 +** then jump to P2 if the new value is exactly zero. +*/ +case OP_DecrJumpZero: { /* jump, in1 */ + pIn1 = &aMem[pOp->p1]; + assert( pIn1->flags&MEM_Int ); + pIn1->u.i--; VdbeBranchTaken(pIn1->u.i==0, 2); if( pIn1->u.i==0 ){ pc = pOp->p2 - 1; @@ -5622,6 +5654,24 @@ case OP_IfZero: { /* jump, in1 */ break; } + +/* Opcode: JumpZeroIncr P1 P2 * * * +** Synopsis: if (r[P1]++)==0 ) goto P2 +** +** The register P1 must contain an integer. If register P1 is initially +** zero, then jump to P2. Increment register P1 regardless of whether or +** not the jump is taken. +*/ +case OP_JumpZeroIncr: { /* jump, in1 */ + pIn1 = &aMem[pOp->p1]; + assert( pIn1->flags&MEM_Int ); + VdbeBranchTaken(pIn1->u.i==0, 2); + if( (pIn1->u.i++)==0 ){ + pc = pOp->p2 - 1; + } + break; +} + /* Opcode: AggStep * P2 P3 P4 P5 ** Synopsis: accum=r[P3] step(r[P2@P5]) ** diff --git a/src/where.c b/src/where.c index fedc67a79..64c9652b0 100644 --- a/src/where.c +++ b/src/where.c @@ -202,7 +202,7 @@ static void whereClauseClear(WhereClause *pWC){ ** calling this routine. Such pointers may be reinitialized by referencing ** the pWC->a[] array. */ -static int whereClauseInsert(WhereClause *pWC, Expr *p, u8 wtFlags){ +static int whereClauseInsert(WhereClause *pWC, Expr *p, u16 wtFlags){ WhereTerm *pTerm; int idx; testcase( wtFlags & TERM_VIRTUAL ); @@ -627,7 +627,11 @@ static void exprAnalyzeAll( ** so and false if not. ** ** In order for the operator to be optimizible, the RHS must be a string -** literal that does not begin with a wildcard. +** literal that does not begin with a wildcard. The LHS must be a column +** that may only be NULL, a string, or a BLOB, never a number. (This means +** that virtual tables cannot participate in the LIKE optimization.) If the +** collating sequence for the column on the LHS must be appropriate for +** the operator. */ static int isLikeOrGlob( Parse *pParse, /* Parsing and code generating context */ @@ -656,7 +660,7 @@ static int isLikeOrGlob( pLeft = pList->a[1].pExpr; if( pLeft->op!=TK_COLUMN || sqlite3ExprAffinity(pLeft)!=SQLITE_AFF_TEXT - || IsVirtual(pLeft->pTab) + || IsVirtual(pLeft->pTab) /* Value might be numeric */ ){ /* IMP: R-02065-49465 The left-hand side of the LIKE or GLOB operator must ** be the name of an indexed column with TEXT affinity. */ @@ -1105,7 +1109,7 @@ static void exprAnalyze( Bitmask extraRight = 0; /* Extra dependencies on LEFT JOIN */ Expr *pStr1 = 0; /* RHS of LIKE/GLOB operator */ int isComplete = 0; /* RHS of LIKE/GLOB ends with wildcard */ - int noCase = 0; /* LIKE/GLOB distinguishes case */ + int noCase = 0; /* uppercase equivalent to lowercase */ int op; /* Top-level operator. pExpr->op */ Parse *pParse = pWInfo->pParse; /* Parsing context */ sqlite3 *db = pParse->db; /* Database connection */ @@ -1243,12 +1247,15 @@ static void exprAnalyze( /* Add constraints to reduce the search space on a LIKE or GLOB ** operator. ** - ** A like pattern of the form "x LIKE 'abc%'" is changed into constraints + ** A like pattern of the form "x LIKE 'aBc%'" is changed into constraints ** - ** x>='abc' AND x<'abd' AND x LIKE 'abc%' + ** x>='ABC' AND x<'abd' AND x LIKE 'aBc%' ** ** The last character of the prefix "abc" is incremented to form the - ** termination condition "abd". + ** termination condition "abd". If case is not significant (the default + ** for LIKE) then the lower-bound is made all uppercase and the upper- + ** bound is made all lowercase so that the bounds also work when comparing + ** BLOBs. */ if( pWC->op==TK_AND && isLikeOrGlob(pParse, pExpr, &pStr1, &isComplete, &noCase) @@ -1260,9 +1267,25 @@ static void exprAnalyze( int idxNew1; int idxNew2; Token sCollSeqName; /* Name of collating sequence */ + const u16 wtFlags = TERM_LIKEOPT | TERM_VIRTUAL | TERM_DYNAMIC; pLeft = pExpr->x.pList->a[1].pExpr; pStr2 = sqlite3ExprDup(db, pStr1, 0); + + /* Convert the lower bound to upper-case and the upper bound to + ** lower-case (upper-case is less than lower-case in ASCII) so that + ** the range constraints also work for BLOBs + */ + if( noCase && !pParse->db->mallocFailed ){ + int i; + char c; + pTerm->wtFlags |= TERM_LIKE; + for(i=0; (c = pStr1->u.zToken[i])!=0; i++){ + pStr1->u.zToken[i] = sqlite3Toupper(c); + pStr2->u.zToken[i] = sqlite3Tolower(c); + } + } + if( !db->mallocFailed ){ u8 c, *pC; /* Last character before the first wildcard */ pC = (u8*)&pStr2->u.zToken[sqlite3Strlen30(pStr2->u.zToken)-1]; @@ -1282,11 +1305,11 @@ static void exprAnalyze( sCollSeqName.z = noCase ? "NOCASE" : "BINARY"; sCollSeqName.n = 6; pNewExpr1 = sqlite3ExprDup(db, pLeft, 0); - pNewExpr1 = sqlite3PExpr(pParse, TK_GE, + pNewExpr1 = sqlite3PExpr(pParse, TK_GE, sqlite3ExprAddCollateToken(pParse,pNewExpr1,&sCollSeqName), pStr1, 0); transferJoinMarkings(pNewExpr1, pExpr); - idxNew1 = whereClauseInsert(pWC, pNewExpr1, TERM_VIRTUAL|TERM_DYNAMIC); + idxNew1 = whereClauseInsert(pWC, pNewExpr1, wtFlags); testcase( idxNew1==0 ); exprAnalyze(pSrc, pWC, idxNew1); pNewExpr2 = sqlite3ExprDup(db, pLeft, 0); @@ -1294,7 +1317,7 @@ static void exprAnalyze( sqlite3ExprAddCollateToken(pParse,pNewExpr2,&sCollSeqName), pStr2, 0); transferJoinMarkings(pNewExpr2, pExpr); - idxNew2 = whereClauseInsert(pWC, pNewExpr2, TERM_VIRTUAL|TERM_DYNAMIC); + idxNew2 = whereClauseInsert(pWC, pNewExpr2, wtFlags); testcase( idxNew2==0 ); exprAnalyze(pSrc, pWC, idxNew2); pTerm = &pWC->a[idxTerm]; @@ -2469,20 +2492,43 @@ static int whereInScanEst( ** but joins might run a little slower. The trick is to disable as much ** as we can without disabling too much. If we disabled in (1), we'd get ** the wrong answer. See ticket #813. +** +** If all the children of a term are disabled, then that term is also +** automatically disabled. In this way, terms get disabled if derived +** virtual terms are tested first. For example: +** +** x GLOB 'abc*' AND x>='abc' AND x<'acd' +** \___________/ \______/ \_____/ +** parent child1 child2 +** +** Only the parent term was in the original WHERE clause. The child1 +** and child2 terms were added by the LIKE optimization. If both of +** the virtual child terms are valid, then testing of the parent can be +** skipped. +** +** Usually the parent term is marked as TERM_CODED. But if the parent +** term was originally TERM_LIKE, then the parent gets TERM_LIKECOND instead. +** The TERM_LIKECOND marking indicates that the term should be coded inside +** a conditional such that is only evaluated on the second pass of a +** LIKE-optimization loop, when scanning BLOBs instead of strings. */ static void disableTerm(WhereLevel *pLevel, WhereTerm *pTerm){ - if( pTerm + int nLoop = 0; + while( pTerm && (pTerm->wtFlags & TERM_CODED)==0 && (pLevel->iLeftJoin==0 || ExprHasProperty(pTerm->pExpr, EP_FromJoin)) && (pLevel->notReady & pTerm->prereqAll)==0 ){ - pTerm->wtFlags |= TERM_CODED; - if( pTerm->iParent>=0 ){ - WhereTerm *pOther = &pTerm->pWC->a[pTerm->iParent]; - if( (--pOther->nChild)==0 ){ - disableTerm(pLevel, pOther); - } + if( nLoop && (pTerm->wtFlags & TERM_LIKE)!=0 ){ + pTerm->wtFlags |= TERM_LIKECOND; + }else{ + pTerm->wtFlags |= TERM_CODED; } + if( pTerm->iParent<0 ) break; + pTerm = &pTerm->pWC->a[pTerm->iParent]; + pTerm->nChild--; + if( pTerm->nChild!=0 ) break; + nLoop++; } } @@ -2966,7 +3012,26 @@ static void addScanStatus( # define addScanStatus(a, b, c, d) ((void)d) #endif - +/* +** Look at the last instruction coded. If that instruction is OP_String8 +** and if pLoop->iLikeRepCntr is non-zero, then change the P3 to be +** pLoop->iLikeRepCntr and set P5. +** +** The LIKE optimization trys to evaluate "x LIKE 'abc%'" as a range +** expression: "x>='ABC' AND x<'abd'". But this requires that the range +** scan loop run twice, once for strings and a second time for BLOBs. +** The OP_String opcodes on the second pass convert the upper and lower +** bound string contants to blobs. This routine makes the necessary changes +** to the OP_String opcodes for that to happen. +*/ +static void whereLikeOptimizationStringFixup(Vdbe *v, WhereLevel *pLevel){ + VdbeOp *pOp; + pOp = sqlite3VdbeGetOp(v, -1); + if( pLevel->iLikeRepCntr && pOp->opcode==OP_String8 ){ + pOp->p3 = pLevel->iLikeRepCntr; + pOp->p5 = 1; + } +} /* ** Generate code for the start of the iLevel-th loop in the WHERE clause @@ -3300,6 +3365,19 @@ static Bitmask codeOneLoopStart( if( pLoop->wsFlags & WHERE_TOP_LIMIT ){ pRangeEnd = pLoop->aLTerm[j++]; nExtraReg = 1; + if( pRangeStart + && (pRangeStart->wtFlags & TERM_LIKEOPT)!=0 + && (pRangeEnd->wtFlags & TERM_LIKEOPT)!=0 + ){ + pLevel->iLikeRepCntr = ++pParse->nMem; + testcase( bRev ); + testcase( pIdx->aSortOrder[nEq]==SQLITE_SO_DESC ); + sqlite3VdbeAddOp2(v, OP_Integer, + bRev ^ (pIdx->aSortOrder[nEq]==SQLITE_SO_DESC), + pLevel->iLikeRepCntr); + VdbeComment((v, "LIKE loop counter")); + pLevel->addrLikeRep = sqlite3VdbeCurrentAddr(v); + } if( pRangeStart==0 && (j = pIdx->aiColumn[nEq])>=0 && pIdx->pTable->aCol[j].notNull==0 @@ -3342,6 +3420,7 @@ static Bitmask codeOneLoopStart( if( pRangeStart ){ Expr *pRight = pRangeStart->pExpr->pRight; sqlite3ExprCode(pParse, pRight, regBase+nEq); + whereLikeOptimizationStringFixup(v, pLevel); if( (pRangeStart->wtFlags & TERM_VNULL)==0 && sqlite3ExprCanBeNull(pRight) ){ @@ -3387,6 +3466,7 @@ static Bitmask codeOneLoopStart( Expr *pRight = pRangeEnd->pExpr->pRight; sqlite3ExprCacheRemove(pParse, regBase+nEq, 1); sqlite3ExprCode(pParse, pRight, regBase+nEq); + whereLikeOptimizationStringFixup(v, pLevel); if( (pRangeEnd->wtFlags & TERM_VNULL)==0 && sqlite3ExprCanBeNull(pRight) ){ @@ -3777,6 +3857,7 @@ static Bitmask codeOneLoopStart( */ for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){ Expr *pE; + int skipLikeAddr = 0; testcase( pTerm->wtFlags & TERM_VIRTUAL ); testcase( pTerm->wtFlags & TERM_CODED ); if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue; @@ -3791,7 +3872,13 @@ static Bitmask codeOneLoopStart( if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){ continue; } + if( pTerm->wtFlags & TERM_LIKECOND ){ + assert( pLevel->iLikeRepCntr>0 ); + skipLikeAddr = sqlite3VdbeAddOp1(v, OP_IfNot, pLevel->iLikeRepCntr); + VdbeCoverage(v); + } sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL); + if( skipLikeAddr ) sqlite3VdbeJumpHere(v, skipLikeAddr); pTerm->wtFlags |= TERM_CODED; } @@ -6595,6 +6682,16 @@ void sqlite3WhereEnd(WhereInfo *pWInfo){ sqlite3VdbeJumpHere(v, pLevel->addrSkip); sqlite3VdbeJumpHere(v, pLevel->addrSkip-2); } + if( pLevel->addrLikeRep ){ + int op; + if( sqlite3VdbeGetOp(v, pLevel->addrLikeRep-1)->p1 ){ + op = OP_DecrJumpZero; + }else{ + op = OP_JumpZeroIncr; + } + sqlite3VdbeAddOp2(v, op, pLevel->iLikeRepCntr, pLevel->addrLikeRep); + VdbeCoverage(v); + } if( pLevel->iLeftJoin ){ addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin); VdbeCoverage(v); assert( (pLoop->wsFlags & WHERE_IDX_ONLY)==0 diff --git a/src/whereInt.h b/src/whereInt.h index 2ccc6ec06..04cc2029d 100644 --- a/src/whereInt.h +++ b/src/whereInt.h @@ -69,6 +69,8 @@ struct WhereLevel { int addrCont; /* Jump here to continue with the next loop cycle */ int addrFirst; /* First instruction of interior of the loop */ int addrBody; /* Beginning of the body of this loop */ + int iLikeRepCntr; /* LIKE range processing counter register */ + int addrLikeRep; /* LIKE range processing address */ u8 iFrom; /* Which entry in the FROM clause */ u8 op, p3, p5; /* Opcode, P3 & P5 of the opcode that ends the loop */ int p1, p2; /* Operands of the opcode used to ends the loop */ @@ -253,7 +255,7 @@ struct WhereTerm { } u; LogEst truthProb; /* Probability of truth for this expression */ u16 eOperator; /* A WO_xx value describing <op> */ - u8 wtFlags; /* TERM_xxx bit flags. See below */ + u16 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 */ Bitmask prereqRight; /* Bitmask of tables used by pExpr->pRight */ @@ -275,6 +277,9 @@ struct WhereTerm { #else # define TERM_VNULL 0x00 /* Disabled if not using stat3 */ #endif +#define TERM_LIKEOPT 0x100 /* Virtual terms from the LIKE optimization */ +#define TERM_LIKECOND 0x200 /* Conditionally this LIKE operator term */ +#define TERM_LIKE 0x400 /* The original LIKE operator */ /* ** An instance of the WhereScan object is used as an iterator for locating |