Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Provide hints to the btree layer Next and Previous primitives to let them know if they can be no-ops if the underlying index is unique. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | branch-3.8.2 |
Files: | files | file ages | folders |
SHA1: |
a2c347faf91d82cf8734621bf378a6dd |
User & Date: | drh 2014-01-28 00:49:55.352 |
Context
2014-02-03
| ||
14:04 | Provide hints to the btree layer Next and Previous primitives to let them know if they can be no-ops if the underlying index is unique. (check-in: 6c643e45c2 user: drh tags: trunk) | |
2014-01-28
| ||
00:49 | Provide hints to the btree layer Next and Previous primitives to let them know if they can be no-ops if the underlying index is unique. (Leaf check-in: a2c347faf9 user: drh tags: branch-3.8.2) | |
2014-01-15
| ||
00:24 | Merge recent fixes from trunk. Cherrypick of [c43b59dac1], [a221aa82bb], [e1eba1fb09], and [1e131094b5]. (check-in: c697d2f83c user: mistachkin tags: branch-3.8.2) | |
Changes
Changes to src/btree.c.
︙ | ︙ | |||
4813 4814 4815 4816 4817 4818 4819 4820 4821 4822 4823 4824 4825 4826 4827 4828 4829 4830 4831 4832 4833 4834 | } /* ** Advance the cursor to the next entry in the database. If ** successful then set *pRes=0. If the cursor ** was already pointing to the last entry in the database before ** this routine was called, then set *pRes=1. */ int sqlite3BtreeNext(BtCursor *pCur, int *pRes){ int rc; int idx; MemPage *pPage; assert( cursorHoldsMutex(pCur) ); assert( pRes!=0 ); assert( pCur->skipNext==0 || pCur->eState!=CURSOR_VALID ); if( pCur->eState!=CURSOR_VALID ){ rc = restoreCursorPosition(pCur); if( rc!=SQLITE_OK ){ *pRes = 0; return rc; } | > > > > > > > > > > | 4813 4814 4815 4816 4817 4818 4819 4820 4821 4822 4823 4824 4825 4826 4827 4828 4829 4830 4831 4832 4833 4834 4835 4836 4837 4838 4839 4840 4841 4842 4843 4844 | } /* ** Advance the cursor to the next entry in the database. If ** successful then set *pRes=0. If the cursor ** was already pointing to the last entry in the database before ** this routine was called, then set *pRes=1. ** ** The calling function will set *pRes to 0 or 1. The initial *pRes value ** will be 1 if the cursor being stepped corresponds to an SQL index and ** if this routine could have been skipped if that SQL index had been ** a unique index. Otherwise the caller will have set *pRes to zero. ** Zero is the common case. The btree implementation is free to use the ** initial *pRes value as a hint to improve performance, but the current ** SQLite btree implementation does not. (Note that the comdb2 btree ** implementation does use this hint, however.) */ int sqlite3BtreeNext(BtCursor *pCur, int *pRes){ int rc; int idx; MemPage *pPage; assert( cursorHoldsMutex(pCur) ); assert( pRes!=0 ); assert( *pRes==0 || *pRes==1 ); assert( pCur->skipNext==0 || pCur->eState!=CURSOR_VALID ); if( pCur->eState!=CURSOR_VALID ){ rc = restoreCursorPosition(pCur); if( rc!=SQLITE_OK ){ *pRes = 0; return rc; } |
︙ | ︙ | |||
4899 4900 4901 4902 4903 4904 4905 4906 4907 4908 4909 4910 4911 4912 4913 4914 4915 4916 4917 4918 4919 | /* ** Step the cursor to the back to the previous entry in the database. If ** successful then set *pRes=0. If the cursor ** was already pointing to the first entry in the database before ** this routine was called, then set *pRes=1. */ int sqlite3BtreePrevious(BtCursor *pCur, int *pRes){ int rc; MemPage *pPage; assert( cursorHoldsMutex(pCur) ); assert( pRes!=0 ); assert( pCur->skipNext==0 || pCur->eState!=CURSOR_VALID ); pCur->atLast = 0; if( pCur->eState!=CURSOR_VALID ){ if( ALWAYS(pCur->eState>=CURSOR_REQUIRESEEK) ){ rc = btreeRestoreCursorPosition(pCur); if( rc!=SQLITE_OK ){ *pRes = 0; | > > > > > > > > > > | 4909 4910 4911 4912 4913 4914 4915 4916 4917 4918 4919 4920 4921 4922 4923 4924 4925 4926 4927 4928 4929 4930 4931 4932 4933 4934 4935 4936 4937 4938 4939 | /* ** Step the cursor to the back to the previous entry in the database. If ** successful then set *pRes=0. If the cursor ** was already pointing to the first entry in the database before ** this routine was called, then set *pRes=1. ** ** The calling function will set *pRes to 0 or 1. The initial *pRes value ** will be 1 if the cursor being stepped corresponds to an SQL index and ** if this routine could have been skipped if that SQL index had been ** a unique index. Otherwise the caller will have set *pRes to zero. ** Zero is the common case. The btree implementation is free to use the ** initial *pRes value as a hint to improve performance, but the current ** SQLite btree implementation does not. (Note that the comdb2 btree ** implementation does use this hint, however.) */ int sqlite3BtreePrevious(BtCursor *pCur, int *pRes){ int rc; MemPage *pPage; assert( cursorHoldsMutex(pCur) ); assert( pRes!=0 ); assert( *pRes==0 || *pRes==1 ); assert( pCur->skipNext==0 || pCur->eState!=CURSOR_VALID ); pCur->atLast = 0; if( pCur->eState!=CURSOR_VALID ){ if( ALWAYS(pCur->eState>=CURSOR_REQUIRESEEK) ){ rc = btreeRestoreCursorPosition(pCur); if( rc!=SQLITE_OK ){ *pRes = 0; |
︙ | ︙ | |||
7146 7147 7148 7149 7150 7151 7152 | ** the cursor to the largest entry in the tree that is smaller than ** the entry being deleted. This cell will replace the cell being deleted ** from the internal node. The 'previous' entry is used for this instead ** of the 'next' entry, as the previous entry is always a part of the ** sub-tree headed by the child page of the cell being deleted. This makes ** balancing the tree following the delete operation easier. */ if( !pPage->leaf ){ | | | 7166 7167 7168 7169 7170 7171 7172 7173 7174 7175 7176 7177 7178 7179 7180 | ** the cursor to the largest entry in the tree that is smaller than ** the entry being deleted. This cell will replace the cell being deleted ** from the internal node. The 'previous' entry is used for this instead ** of the 'next' entry, as the previous entry is always a part of the ** sub-tree headed by the child page of the cell being deleted. This makes ** balancing the tree following the delete operation easier. */ if( !pPage->leaf ){ int notUsed = 0; rc = sqlite3BtreePrevious(pCur, ¬Used); if( rc ) return rc; } /* Save the positions of any other cursors open on this table before ** making any modifications. Make the page containing the entry to be ** deleted writable. Then free any overflow pages associated with the |
︙ | ︙ |
Changes to src/vdbe.c.
︙ | ︙ | |||
3576 3577 3578 3579 3580 3581 3582 3583 3584 3585 3586 3587 3588 3589 3590 3591 3592 3593 3594 3595 3596 3597 3598 | pC->deferredMoveto = 0; pC->cacheStatus = CACHE_STALE; #ifdef SQLITE_TEST sqlite3_search_count++; #endif if( oc>=OP_SeekGe ){ assert( oc==OP_SeekGe || oc==OP_SeekGt ); if( res<0 || (res==0 && oc==OP_SeekGt) ){ rc = sqlite3BtreeNext(pC->pCursor, &res); if( rc!=SQLITE_OK ) goto abort_due_to_error; pC->rowidIsValid = 0; }else{ res = 0; } }else{ assert( oc==OP_SeekLt || oc==OP_SeekLe ); if( res>0 || (res==0 && oc==OP_SeekLt) ){ rc = sqlite3BtreePrevious(pC->pCursor, &res); if( rc!=SQLITE_OK ) goto abort_due_to_error; pC->rowidIsValid = 0; }else{ /* res might be negative because the table is empty. Check to ** see if this is the case. */ | > > | 3576 3577 3578 3579 3580 3581 3582 3583 3584 3585 3586 3587 3588 3589 3590 3591 3592 3593 3594 3595 3596 3597 3598 3599 3600 | pC->deferredMoveto = 0; pC->cacheStatus = CACHE_STALE; #ifdef SQLITE_TEST sqlite3_search_count++; #endif if( oc>=OP_SeekGe ){ assert( oc==OP_SeekGe || oc==OP_SeekGt ); if( res<0 || (res==0 && oc==OP_SeekGt) ){ res = 0; rc = sqlite3BtreeNext(pC->pCursor, &res); if( rc!=SQLITE_OK ) goto abort_due_to_error; pC->rowidIsValid = 0; }else{ res = 0; } }else{ assert( oc==OP_SeekLt || oc==OP_SeekLe ); if( res>0 || (res==0 && oc==OP_SeekLt) ){ res = 0; rc = sqlite3BtreePrevious(pC->pCursor, &res); if( rc!=SQLITE_OK ) goto abort_due_to_error; pC->rowidIsValid = 0; }else{ /* res might be negative because the table is empty. Check to ** see if this is the case. */ |
︙ | ︙ | |||
4438 4439 4440 4441 4442 4443 4444 | assert( pOp->p2>0 && pOp->p2<p->nOp ); if( res ){ pc = pOp->p2 - 1; } break; } | | > > > > > | | > > > > > | | 4440 4441 4442 4443 4444 4445 4446 4447 4448 4449 4450 4451 4452 4453 4454 4455 4456 4457 4458 4459 4460 4461 4462 4463 4464 4465 4466 4467 4468 4469 4470 4471 4472 4473 4474 4475 4476 4477 4478 4479 4480 4481 4482 4483 4484 4485 4486 4487 4488 4489 4490 4491 4492 4493 4494 4495 4496 4497 4498 4499 4500 4501 4502 4503 | assert( pOp->p2>0 && pOp->p2<p->nOp ); if( res ){ pc = pOp->p2 - 1; } break; } /* Opcode: Next P1 P2 P3 * P5 ** ** Advance cursor P1 so that it points to the next key/data pair in its ** table or index. If there are no more key/value pairs then fall through ** to the following instruction. But if the cursor advance was successful, ** jump immediately to P2. ** ** The P1 cursor must be for a real table, not a pseudo-table. P1 must have ** been opened prior to this opcode or the program will segfault. ** ** The P3 value is a hint to the btree implementation. If P3==1, that ** means P1 is an SQL index and that this instruction could have been ** omitted if that index had been unique. P3 is usually 0. P3 is ** always either 0 or 1. ** ** P4 is always of type P4_ADVANCE. The function pointer points to ** sqlite3BtreeNext(). ** ** If P5 is positive and the jump is taken, then event counter ** number P5-1 in the prepared statement is incremented. ** ** See also: Prev, NextIfOpen */ /* Opcode: NextIfOpen P1 P2 P3 * P5 ** ** This opcode works just like OP_Next except that if cursor P1 is not ** open it behaves a no-op. */ /* Opcode: Prev P1 P2 P3 * P5 ** ** Back up cursor P1 so that it points to the previous key/data pair in its ** table or index. If there is no previous key/value pairs then fall through ** to the following instruction. But if the cursor backup was successful, ** jump immediately to P2. ** ** The P1 cursor must be for a real table, not a pseudo-table. If P1 is ** not open then the behavior is undefined. ** ** The P3 value is a hint to the btree implementation. If P3==1, that ** means P1 is an SQL index and that this instruction could have been ** omitted if that index had been unique. P3 is usually 0. P3 is ** always either 0 or 1. ** ** P4 is always of type P4_ADVANCE. The function pointer points to ** sqlite3BtreePrevious(). ** ** If P5 is positive and the jump is taken, then event counter ** number P5-1 in the prepared statement is incremented. */ /* Opcode: PrevIfOpen P1 P2 P3 * P5 ** ** This opcode works just like OP_Prev except that if cursor P1 is not ** open it behaves a no-op. */ case OP_SorterNext: { /* jump */ VdbeCursor *pC; int res; |
︙ | ︙ | |||
4499 4500 4501 4502 4503 4504 4505 4506 4507 4508 4509 4510 4511 4512 4513 4514 4515 | if( p->apCsr[pOp->p1]==0 ) break; /* Fall through */ case OP_Prev: /* jump */ case OP_Next: /* jump */ assert( pOp->p1>=0 && pOp->p1<p->nCursor ); assert( pOp->p5<ArraySize(p->aCounter) ); pC = p->apCsr[pOp->p1]; assert( pC!=0 ); assert( pC->deferredMoveto==0 ); assert( pC->pCursor ); assert( pOp->opcode!=OP_Next || pOp->p4.xAdvance==sqlite3BtreeNext ); assert( pOp->opcode!=OP_Prev || pOp->p4.xAdvance==sqlite3BtreePrevious ); assert( pOp->opcode!=OP_NextIfOpen || pOp->p4.xAdvance==sqlite3BtreeNext ); assert( pOp->opcode!=OP_PrevIfOpen || pOp->p4.xAdvance==sqlite3BtreePrevious); rc = pOp->p4.xAdvance(pC->pCursor, &res); next_tail: pC->cacheStatus = CACHE_STALE; | > > > | 4511 4512 4513 4514 4515 4516 4517 4518 4519 4520 4521 4522 4523 4524 4525 4526 4527 4528 4529 4530 | if( p->apCsr[pOp->p1]==0 ) break; /* Fall through */ case OP_Prev: /* jump */ case OP_Next: /* jump */ assert( pOp->p1>=0 && pOp->p1<p->nCursor ); assert( pOp->p5<ArraySize(p->aCounter) ); pC = p->apCsr[pOp->p1]; res = pOp->p3; assert( pC!=0 ); assert( pC->deferredMoveto==0 ); assert( pC->pCursor ); assert( res==0 || (res==1 && pC->isTable==0) ); testcase( res==1 ); assert( pOp->opcode!=OP_Next || pOp->p4.xAdvance==sqlite3BtreeNext ); assert( pOp->opcode!=OP_Prev || pOp->p4.xAdvance==sqlite3BtreePrevious ); assert( pOp->opcode!=OP_NextIfOpen || pOp->p4.xAdvance==sqlite3BtreeNext ); assert( pOp->opcode!=OP_PrevIfOpen || pOp->p4.xAdvance==sqlite3BtreePrevious); rc = pOp->p4.xAdvance(pC->pCursor, &res); next_tail: pC->cacheStatus = CACHE_STALE; |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
3178 3179 3180 3181 3182 3183 3184 3185 3186 3187 3188 3189 3190 3191 | pLevel->op = OP_Noop; }else if( bRev ){ pLevel->op = OP_Prev; }else{ pLevel->op = OP_Next; } pLevel->p1 = iIdxCur; if( (pLoop->wsFlags & WHERE_CONSTRAINT)==0 ){ pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP; }else{ assert( pLevel->p5==0 ); } }else | > > | 3178 3179 3180 3181 3182 3183 3184 3185 3186 3187 3188 3189 3190 3191 3192 3193 | pLevel->op = OP_Noop; }else if( bRev ){ pLevel->op = OP_Prev; }else{ pLevel->op = OP_Next; } pLevel->p1 = iIdxCur; assert( (WHERE_UNQ_WANTED>>16)==1 ); pLevel->p3 = (pLoop->wsFlags>>16)&1; if( (pLoop->wsFlags & WHERE_CONSTRAINT)==0 ){ pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP; }else{ assert( pLevel->p5==0 ); } }else |
︙ | ︙ | |||
3974 3975 3976 3977 3978 3979 3980 | pNew->nOut = nRowEst + nInMul + nIn; }else if( pTerm->eOperator & (WO_EQ) ){ assert( (pNew->wsFlags & (WHERE_COLUMN_NULL|WHERE_COLUMN_IN|WHERE_SKIPSCAN))!=0 || nInMul==0 ); pNew->wsFlags |= WHERE_COLUMN_EQ; | < < | < > > > | > | 3976 3977 3978 3979 3980 3981 3982 3983 3984 3985 3986 3987 3988 3989 3990 3991 3992 3993 3994 3995 3996 | pNew->nOut = nRowEst + nInMul + nIn; }else if( pTerm->eOperator & (WO_EQ) ){ assert( (pNew->wsFlags & (WHERE_COLUMN_NULL|WHERE_COLUMN_IN|WHERE_SKIPSCAN))!=0 || nInMul==0 ); pNew->wsFlags |= WHERE_COLUMN_EQ; if( iCol<0 || (nInMul==0 && pNew->u.btree.nEq==pProbe->nKeyCol-1)){ assert( (pNew->wsFlags & WHERE_COLUMN_IN)==0 || iCol<0 ); if( iCol>=0 && pProbe->onError==OE_None ){ pNew->wsFlags |= WHERE_UNQ_WANTED; }else{ pNew->wsFlags |= WHERE_ONEROW; } } pNew->u.btree.nEq++; pNew->nOut = nRowEst + nInMul; }else if( pTerm->eOperator & (WO_ISNULL) ){ pNew->wsFlags |= WHERE_COLUMN_NULL; pNew->u.btree.nEq++; /* TUNING: IS NULL selects 2 rows */ |
︙ | ︙ | |||
5769 5770 5771 5772 5773 5774 5775 | sqlite3ExprCacheClear(pParse); for(i=pWInfo->nLevel-1; i>=0; i--){ int addr; pLevel = &pWInfo->a[i]; pLoop = pLevel->pWLoop; sqlite3VdbeResolveLabel(v, pLevel->addrCont); if( pLevel->op!=OP_Noop ){ | | | 5772 5773 5774 5775 5776 5777 5778 5779 5780 5781 5782 5783 5784 5785 5786 | sqlite3ExprCacheClear(pParse); for(i=pWInfo->nLevel-1; i>=0; i--){ int addr; pLevel = &pWInfo->a[i]; pLoop = pLevel->pWLoop; sqlite3VdbeResolveLabel(v, pLevel->addrCont); if( pLevel->op!=OP_Noop ){ sqlite3VdbeAddOp3(v, pLevel->op, pLevel->p1, pLevel->p2, pLevel->p3); sqlite3VdbeChangeP5(v, pLevel->p5); } if( pLoop->wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){ struct InLoop *pIn; int j; sqlite3VdbeResolveLabel(v, pLevel->addrNxt); for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){ |
︙ | ︙ |
Changes to src/whereInt.h.
︙ | ︙ | |||
66 67 68 69 70 71 72 | int addrBrk; /* Jump here to break out of the loop */ int addrNxt; /* Jump here to start the next IN combination */ int addrSkip; /* Jump here for next iteration of skip-scan */ 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 */ u8 iFrom; /* Which entry in the FROM clause */ | | | 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | int addrBrk; /* Jump here to break out of the loop */ int addrNxt; /* Jump here to start the next IN combination */ int addrSkip; /* Jump here for next iteration of skip-scan */ 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 */ 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 */ union { /* Information that depends on pWLoop->wsFlags */ struct { int nIn; /* Number of entries in aInLoop[] */ struct InLoop { int iCur; /* The VDBE cursor used by this IN operator */ int addrInTop; /* Top of the IN loop */ |
︙ | ︙ | |||
453 454 455 456 457 458 459 | #define WHERE_INDEXED 0x00000200 /* WhereLoop.u.btree.pIndex is valid */ #define WHERE_VIRTUALTABLE 0x00000400 /* WhereLoop.u.vtab is valid */ #define WHERE_IN_ABLE 0x00000800 /* Able to support an IN operator */ #define WHERE_ONEROW 0x00001000 /* Selects no more than one row */ #define WHERE_MULTI_OR 0x00002000 /* OR using multiple indices */ #define WHERE_AUTO_INDEX 0x00004000 /* Uses an ephemeral index */ #define WHERE_SKIPSCAN 0x00008000 /* Uses the skip-scan algorithm */ | > | 453 454 455 456 457 458 459 460 | #define WHERE_INDEXED 0x00000200 /* WhereLoop.u.btree.pIndex is valid */ #define WHERE_VIRTUALTABLE 0x00000400 /* WhereLoop.u.vtab is valid */ #define WHERE_IN_ABLE 0x00000800 /* Able to support an IN operator */ #define WHERE_ONEROW 0x00001000 /* Selects no more than one row */ #define WHERE_MULTI_OR 0x00002000 /* OR using multiple indices */ #define WHERE_AUTO_INDEX 0x00004000 /* Uses an ephemeral index */ #define WHERE_SKIPSCAN 0x00008000 /* Uses the skip-scan algorithm */ #define WHERE_UNQ_WANTED 0x00010000 /* WHERE_ONEROW would have been helpful*/ |