Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Refactor some jump opcodes in the VDBE. Add JumpZeroIncr and DecrJumpZero. Fix the LIKE optimization to work with DESC sort order. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | like-opt-fix |
Files: | files | file ages | folders |
SHA1: |
26cb5145bf52f8c3fffa8c69b6c24aee |
User & Date: | drh 2015-03-07 00:57:37.923 |
Context
2015-03-07
| ||
02:51 | Fix problems with reverse order sorting and indexes in the LIKE optimization. (check-in: 564b8fe794 user: drh tags: like-opt-fix) | |
00:57 | Refactor some jump opcodes in the VDBE. Add JumpZeroIncr and DecrJumpZero. Fix the LIKE optimization to work with DESC sort order. (check-in: 26cb5145bf user: drh tags: like-opt-fix) | |
2015-03-06
| ||
20:49 | Test cases added. Comments fixed. Proposed solution for ticket [05f43be8fdda9fbd9]. (check-in: 6b993bd540 user: drh tags: like-opt-fix) | |
Changes
Changes to src/func.c.
︙ | ︙ | |||
1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 | /* ** pExpr points to an expression which implements a function. If ** it is appropriate to apply the LIKE optimization to that function ** 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. */ int sqlite3IsLikeFunction(sqlite3 *db, Expr *pExpr, int *pIsNocase, char *aWc){ FuncDef *pDef; if( pExpr->op!=TK_FUNCTION || !pExpr->x.pList || pExpr->x.pList->nExpr!=2 ){ | > > > > > | 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 | /* ** pExpr points to an expression which implements a function. If ** it is appropriate to apply the LIKE optimization to that function ** 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; if( pExpr->op!=TK_FUNCTION || !pExpr->x.pList || pExpr->x.pList->nExpr!=2 ){ |
︙ | ︙ |
Changes to src/select.c.
︙ | ︙ | |||
559 560 561 562 563 564 565 | if( pSort->sortFlags & SORTFLAG_UseSorter ){ op = OP_SorterInsert; }else{ op = OP_IdxInsert; } sqlite3VdbeAddOp2(v, op, pSort->iECursor, regRecord); if( pSelect->iLimit ){ | | < < | < | | 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 | if( pSort->sortFlags & SORTFLAG_UseSorter ){ op = OP_SorterInsert; }else{ op = OP_IdxInsert; } sqlite3VdbeAddOp2(v, op, pSort->iECursor, regRecord); if( pSelect->iLimit ){ int addr; int iLimit; if( pSelect->iOffset ){ iLimit = pSelect->iOffset+1; }else{ iLimit = pSelect->iLimit; } addr = sqlite3VdbeAddOp3(v, OP_IfNotZero, iLimit, 0, -1); VdbeCoverage(v); sqlite3VdbeAddOp1(v, OP_Last, pSort->iECursor); sqlite3VdbeAddOp1(v, OP_Delete, pSort->iECursor); sqlite3VdbeJumpHere(v, addr); } } /* ** Add code to implement the OFFSET */ static void codeOffset( |
︙ | ︙ | |||
969 970 971 972 973 974 975 | } /* Jump to the end of the loop if the LIMIT is reached. Except, if ** there is a sorter, in which case the sorter has already limited ** the output for us. */ if( pSort==0 && p->iLimit ){ | | | 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 | } /* Jump to the end of the loop if the LIMIT is reached. Except, if ** there is a sorter, in which case the sorter has already limited ** the output for us. */ if( pSort==0 && p->iLimit ){ sqlite3VdbeAddOp2(v, OP_DecrJumpZero, p->iLimit, iBreak); VdbeCoverage(v); } } /* ** Allocate a KeyInfo object sufficient for an index of N key columns and ** X extra columns. */ |
︙ | ︙ | |||
1822 1823 1824 1825 1826 1827 1828 | }else if( n>=0 && p->nSelectRow>(u64)n ){ p->nSelectRow = n; } }else{ sqlite3ExprCode(pParse, p->pLimit, iLimit); sqlite3VdbeAddOp1(v, OP_MustBeInt, iLimit); VdbeCoverage(v); VdbeComment((v, "LIMIT counter")); | | | 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 | }else if( n>=0 && p->nSelectRow>(u64)n ){ p->nSelectRow = n; } }else{ sqlite3ExprCode(pParse, p->pLimit, iLimit); sqlite3VdbeAddOp1(v, OP_MustBeInt, iLimit); VdbeCoverage(v); VdbeComment((v, "LIMIT counter")); sqlite3VdbeAddOp2(v, OP_IfNot, iLimit, iBreak); VdbeCoverage(v); } if( p->pOffset ){ p->iOffset = iOffset = ++pParse->nMem; pParse->nMem++; /* Allocate an extra register for limit+offset */ sqlite3ExprCode(pParse, p->pOffset, iOffset); sqlite3VdbeAddOp1(v, OP_MustBeInt, iOffset); VdbeCoverage(v); VdbeComment((v, "OFFSET counter")); |
︙ | ︙ | |||
2041 2042 2043 2044 2045 2046 2047 | /* Output the single row in Current */ addrCont = sqlite3VdbeMakeLabel(v); codeOffset(v, regOffset, addrCont); selectInnerLoop(pParse, p, p->pEList, iCurrent, 0, 0, pDest, addrCont, addrBreak); if( regLimit ){ | | | 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 | /* Output the single row in Current */ addrCont = sqlite3VdbeMakeLabel(v); codeOffset(v, regOffset, addrCont); selectInnerLoop(pParse, p, p->pEList, iCurrent, 0, 0, pDest, addrCont, addrBreak); if( regLimit ){ sqlite3VdbeAddOp2(v, OP_DecrJumpZero, regLimit, addrBreak); VdbeCoverage(v); } sqlite3VdbeResolveLabel(v, addrCont); /* Execute the recursive SELECT taking the single row in Current as ** the value for the recursive-table. Store the results in the Queue. */ |
︙ | ︙ | |||
2266 2267 2268 2269 2270 2271 2272 | if( rc ){ goto multi_select_end; } p->pPrior = 0; p->iLimit = pPrior->iLimit; p->iOffset = pPrior->iOffset; if( p->iLimit ){ | | | 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 | if( rc ){ goto multi_select_end; } p->pPrior = 0; p->iLimit = pPrior->iLimit; p->iOffset = pPrior->iOffset; if( p->iLimit ){ addr = sqlite3VdbeAddOp1(v, OP_IfNot, p->iLimit); VdbeCoverage(v); VdbeComment((v, "Jump ahead if LIMIT reached")); } explainSetInteger(iSub2, pParse->iNextSelectId); rc = sqlite3Select(pParse, p, &dest); testcase( rc!=SQLITE_OK ); pDelete = p->pPrior; p->pPrior = pPrior; |
︙ | ︙ | |||
2667 2668 2669 2670 2671 2672 2673 | break; } } /* Jump to the end of the loop if the LIMIT is reached. */ if( p->iLimit ){ | | | 2664 2665 2666 2667 2668 2669 2670 2671 2672 2673 2674 2675 2676 2677 2678 | break; } } /* Jump to the end of the loop if the LIMIT is reached. */ if( p->iLimit ){ sqlite3VdbeAddOp2(v, OP_DecrJumpZero, p->iLimit, iBreak); VdbeCoverage(v); } /* Generate the subroutine return */ sqlite3VdbeResolveLabel(v, iContinue); sqlite3VdbeAddOp1(v, OP_Return, regReturn); |
︙ | ︙ |
Changes to src/vdbe.c.
︙ | ︙ | |||
5581 5582 5583 5584 5585 5586 5587 | break; } #endif /* SQLITE_OMIT_AUTOINCREMENT */ /* Opcode: IfPos P1 P2 * * * ** Synopsis: if r[P1]>0 goto P2 ** | > | > | < > | 5581 5582 5583 5584 5585 5586 5587 5588 5589 5590 5591 5592 5593 5594 5595 5596 5597 5598 5599 5600 | break; } #endif /* SQLITE_OMIT_AUTOINCREMENT */ /* Opcode: IfPos P1 P2 * * * ** Synopsis: if r[P1]>0 goto 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. ** ** 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]; assert( pIn1->flags&MEM_Int ); VdbeBranchTaken( pIn1->u.i>0, 2); if( pIn1->u.i>0 ){ pc = pOp->p2 - 1; |
︙ | ︙ | |||
5613 5614 5615 5616 5617 5618 5619 | VdbeBranchTaken(pIn1->u.i<0, 2); if( pIn1->u.i<0 ){ pc = pOp->p2 - 1; } break; } | | | | | > | > > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 5615 5616 5617 5618 5619 5620 5621 5622 5623 5624 5625 5626 5627 5628 5629 5630 5631 5632 5633 5634 5635 5636 5637 5638 5639 5640 5641 5642 5643 5644 5645 5646 5647 5648 5649 5650 5651 5652 5653 5654 5655 5656 5657 5658 5659 5660 5661 5662 5663 5664 5665 5666 5667 5668 5669 5670 5671 5672 5673 5674 5675 5676 5677 5678 5679 5680 5681 | VdbeBranchTaken(pIn1->u.i<0, 2); if( pIn1->u.i<0 ){ pc = pOp->p2 - 1; } break; } /* Opcode: IfNotZero P1 P2 P3 * * ** Synopsis: if r[P1]!=0 then r[P1]+=P3, goto 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_IfNotZero: { /* jump, in1 */ pIn1 = &aMem[pOp->p1]; assert( pIn1->flags&MEM_Int ); 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; } 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]) ** ** Execute the step function for an aggregate. The ** function has P5 arguments. P4 is a pointer to the FuncDef ** structure that specifies the function. Use register ** P3 as the accumulator. |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
3013 3014 3015 3016 3017 3018 3019 | #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. ** | | > > > > > | | 3013 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 3029 3030 3031 3032 3033 3034 3035 3036 3037 | #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 |
︙ | ︙ | |||
3362 3363 3364 3365 3366 3367 3368 3369 3370 3371 3372 3373 3374 3375 | nExtraReg = 1; if( pRangeStart && (pRangeStart->wtFlags & TERM_LIKEOPT)!=0 && (pRangeEnd->wtFlags & TERM_LIKEOPT)!=0 ){ pLevel->iLikeRepCntr = ++pParse->nMem; sqlite3VdbeAddOp2(v, OP_Integer, 0, pLevel->iLikeRepCntr); pLevel->addrLikeRep = sqlite3VdbeCurrentAddr(v); } if( pRangeStart==0 && (j = pIdx->aiColumn[nEq])>=0 && pIdx->pTable->aCol[j].notNull==0 ){ bSeekPastNull = 1; | > | 3367 3368 3369 3370 3371 3372 3373 3374 3375 3376 3377 3378 3379 3380 3381 | nExtraReg = 1; if( pRangeStart && (pRangeStart->wtFlags & TERM_LIKEOPT)!=0 && (pRangeEnd->wtFlags & TERM_LIKEOPT)!=0 ){ pLevel->iLikeRepCntr = ++pParse->nMem; sqlite3VdbeAddOp2(v, OP_Integer, 0, 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 ){ bSeekPastNull = 1; |
︙ | ︙ | |||
3391 3392 3393 3394 3395 3396 3397 3398 3399 3400 3401 3402 3403 3404 | ** start and end terms (pRangeStart and pRangeEnd). */ if( (nEq<pIdx->nKeyCol && bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC)) || (bRev && pIdx->nKeyCol==nEq) ){ SWAP(WhereTerm *, pRangeEnd, pRangeStart); SWAP(u8, bSeekPastNull, bStopAtNull); } testcase( pRangeStart && (pRangeStart->eOperator & WO_LE)!=0 ); testcase( pRangeStart && (pRangeStart->eOperator & WO_GE)!=0 ); testcase( pRangeEnd && (pRangeEnd->eOperator & WO_LE)!=0 ); testcase( pRangeEnd && (pRangeEnd->eOperator & WO_GE)!=0 ); startEq = !pRangeStart || pRangeStart->eOperator & (WO_LE|WO_GE); | > > > | 3397 3398 3399 3400 3401 3402 3403 3404 3405 3406 3407 3408 3409 3410 3411 3412 3413 | ** start and end terms (pRangeStart and pRangeEnd). */ if( (nEq<pIdx->nKeyCol && bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC)) || (bRev && pIdx->nKeyCol==nEq) ){ SWAP(WhereTerm *, pRangeEnd, pRangeStart); SWAP(u8, bSeekPastNull, bStopAtNull); if( pLevel->addrLikeRep ){ sqlite3VdbeChangeP1(v, pLevel->addrLikeRep-1, 1); } } testcase( pRangeStart && (pRangeStart->eOperator & WO_LE)!=0 ); testcase( pRangeStart && (pRangeStart->eOperator & WO_GE)!=0 ); testcase( pRangeEnd && (pRangeEnd->eOperator & WO_LE)!=0 ); testcase( pRangeEnd && (pRangeEnd->eOperator & WO_GE)!=0 ); startEq = !pRangeStart || pRangeStart->eOperator & (WO_LE|WO_GE); |
︙ | ︙ | |||
3860 3861 3862 3863 3864 3865 3866 | pE = pTerm->pExpr; assert( pE!=0 ); if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){ continue; } if( pTerm->wtFlags & TERM_LIKECOND ){ assert( pLevel->iLikeRepCntr>0 ); | | | 3869 3870 3871 3872 3873 3874 3875 3876 3877 3878 3879 3880 3881 3882 3883 | pE = pTerm->pExpr; assert( pE!=0 ); 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; } |
︙ | ︙ | |||
6669 6670 6671 6672 6673 6674 6675 | if( pLevel->addrSkip ){ sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrSkip); VdbeComment((v, "next skip-scan on %s", pLoop->u.btree.pIndex->zName)); sqlite3VdbeJumpHere(v, pLevel->addrSkip); sqlite3VdbeJumpHere(v, pLevel->addrSkip-2); } if( pLevel->addrLikeRep ){ | < < | > | | | 6678 6679 6680 6681 6682 6683 6684 6685 6686 6687 6688 6689 6690 6691 6692 6693 6694 6695 | if( pLevel->addrSkip ){ sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrSkip); VdbeComment((v, "next skip-scan on %s", pLoop->u.btree.pIndex->zName)); sqlite3VdbeJumpHere(v, pLevel->addrSkip); sqlite3VdbeJumpHere(v, pLevel->addrSkip-2); } if( pLevel->addrLikeRep ){ sqlite3VdbeAddOp2(v, pLevel->op==OP_Prev ? OP_DecrJumpZero : OP_JumpZeroIncr, 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 || (pLoop->wsFlags & WHERE_INDEXED)!=0 ); if( (pLoop->wsFlags & WHERE_IDX_ONLY)==0 ){ sqlite3VdbeAddOp1(v, OP_NullRow, pTabList->a[i].iCursor); |
︙ | ︙ |
Changes to test/like3.test.
︙ | ︙ | |||
52 53 54 55 56 57 58 59 60 | INSERT INTO t2 SELECT a, b FROM t1; CREATE INDEX t2ba ON t2(b,a); SELECT a, b FROM t2 WHERE b GLOB 'ab*' ORDER BY +a; } {1 abc 4 abc} do_execsql_test like3-1.4 { SELECT a, b FROM t2 WHERE +b GLOB 'ab*' ORDER BY +a; } {1 abc 4 abc} finish_test | > > > > > > > > > > > > > > | 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | INSERT INTO t2 SELECT a, b FROM t1; CREATE INDEX t2ba ON t2(b,a); SELECT a, b FROM t2 WHERE b GLOB 'ab*' ORDER BY +a; } {1 abc 4 abc} do_execsql_test like3-1.4 { SELECT a, b FROM t2 WHERE +b GLOB 'ab*' ORDER BY +a; } {1 abc 4 abc} do_execsql_test like3-3.0 { CREATE TABLE t3(x TEXT PRIMARY KEY COLLATE nocase); INSERT INTO t3(x) VALUES('aaa'),('abc'),('abd'),('abe'),('acz'); INSERT INTO t3(x) SELECT CAST(x AS blob) FROM t3; SELECT quote(x) FROM t3 WHERE x LIKE 'ab%' ORDER BY x; } {'abc' 'abd' 'abe' X'616263' X'616264' X'616265'} do_execsql_test like3-3.1 { SELECT quote(x) FROM t3 WHERE x LIKE 'ab%' ORDER BY x DESC; } {X'616265' X'616264' X'616263' 'abe' 'abd' 'abc'} do_execsql_test like3-3.1ck { SELECT quote(x) FROM t3 WHERE x LIKE 'ab%' ORDER BY +x DESC; } {X'616265' X'616264' X'616263' 'abe' 'abd' 'abc'} finish_test |