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 | descendants | both | branch-3.7.2 |
Files: | files | file ages | folders |
SHA1: |
a5aae1743a208e7792497dfebf3e8311 |
User & Date: | drh 2011-03-31 18:36:17.545 |
Context
2011-04-08
| ||
23:04 | Make sure the left-hand side of the IS NOT NULL operator is a simple column and not a general expression before applying the IS NOT NULL optimization. This is a backport of check-in [543f75a6abe3]. (check-in: e8177e0149 user: drh tags: branch-3.7.2) | |
2011-03-31
| ||
18:36 | 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: a5aae1743a user: drh tags: branch-3.7.2) | |
2011-03-17
| ||
01:53 | Backport the "x IS NULL" query planner enhancement of [2353176811f] to the 3.7.2 branch. (check-in: 68daf20d01 user: drh tags: branch-3.7.2) | |
Changes
Changes to src/btree.c.
︙ | ︙ | |||
4548 4549 4550 4551 4552 4553 4554 4555 4556 4557 4558 4559 4560 4561 4562 4563 4564 4565 | } /* ** 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) ); rc = restoreCursorPosition(pCur); if( rc!=SQLITE_OK ){ return rc; } | > > > > > > > > > > > < | 4548 4549 4550 4551 4552 4553 4554 4555 4556 4557 4558 4559 4560 4561 4562 4563 4564 4565 4566 4567 4568 4569 4570 4571 4572 4573 4574 4575 4576 4577 4578 4579 4580 4581 4582 4583 | } /* ** 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 ); rc = restoreCursorPosition(pCur); if( rc!=SQLITE_OK ){ return rc; } if( CURSOR_INVALID==pCur->eState ){ *pRes = 1; return SQLITE_OK; } if( pCur->skipNext>0 ){ pCur->skipNext = 0; *pRes = 0; |
︙ | ︙ | |||
4617 4618 4619 4620 4621 4622 4623 4624 4625 4626 4627 4628 4629 4630 4631 4632 4633 4634 4635 4636 | /* ** 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) ); rc = restoreCursorPosition(pCur); if( rc!=SQLITE_OK ){ return rc; } pCur->atLast = 0; if( CURSOR_INVALID==pCur->eState ){ *pRes = 1; | > > > > > > > > > > > | 4627 4628 4629 4630 4631 4632 4633 4634 4635 4636 4637 4638 4639 4640 4641 4642 4643 4644 4645 4646 4647 4648 4649 4650 4651 4652 4653 4654 4655 4656 4657 | /* ** 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 ); rc = restoreCursorPosition(pCur); if( rc!=SQLITE_OK ){ return rc; } pCur->atLast = 0; if( CURSOR_INVALID==pCur->eState ){ *pRes = 1; |
︙ | ︙ | |||
6774 6775 6776 6777 6778 6779 6780 | ** 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 ){ | | | 6795 6796 6797 6798 6799 6800 6801 6802 6803 6804 6805 6806 6807 6808 6809 | ** 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/sqliteInt.h.
︙ | ︙ | |||
1861 1862 1863 1864 1865 1866 1867 | int iTabCur; /* The VDBE cursor used to access the table */ int iIdxCur; /* The VDBE cursor used to access pIdx */ int addrBrk; /* Jump here to break out of the loop */ int addrNxt; /* Jump here to start the next IN combination */ int addrCont; /* Jump here to continue with the next loop cycle */ int addrFirst; /* First instruction of interior of the loop */ u8 iFrom; /* Which entry in the FROM clause */ | | | | 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 | int iTabCur; /* The VDBE cursor used to access the table */ int iIdxCur; /* The VDBE cursor used to access pIdx */ int addrBrk; /* Jump here to break out of the loop */ int addrNxt; /* Jump here to start the next IN combination */ int addrCont; /* Jump here to continue with the next loop cycle */ int addrFirst; /* First instruction of interior of the loop */ u8 iFrom; /* Which entry in the FROM clause */ u8 op, p3, p5; /* Opcode, P3, and P5 of the end-of-loop instruction */ int p1, p2; /* P1 and P2 operands of the end-of-loop instruction */ union { /* Information that depends on plan.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 */ } *aInLoop; /* Information about each nested IN operator */ |
︙ | ︙ |
Changes to src/vdbe.c.
︙ | ︙ | |||
3309 3310 3311 3312 3313 3314 3315 3316 3317 3318 3319 3320 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330 3331 | 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. */ | > > | 3309 3310 3311 3312 3313 3314 3315 3316 3317 3318 3319 3320 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330 3331 3332 3333 | 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. */ |
︙ | ︙ | |||
4162 4163 4164 4165 4166 4167 4168 | assert( pOp->p2>0 && pOp->p2<p->nOp ); if( res ){ pc = pOp->p2 - 1; } break; } | | > > > > > | > > > > > > | > > > | 4164 4165 4166 4167 4168 4169 4170 4171 4172 4173 4174 4175 4176 4177 4178 4179 4180 4181 4182 4183 4184 4185 4186 4187 4188 4189 4190 4191 4192 4193 4194 4195 4196 4197 4198 4199 4200 4201 4202 4203 4204 4205 4206 4207 4208 4209 4210 4211 4212 4213 4214 4215 4216 4217 4218 4219 4220 4221 4222 4223 4224 4225 4226 4227 4228 4229 4230 4231 4232 4233 4234 4235 4236 | 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. ** ** If P5 is positive and the jump is taken, then event counter ** number P5-1 in the prepared statement is incremented. ** ** 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. ** ** See also: Prev */ /* 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 P5 is positive and the jump is taken, then event counter ** number P5-1 in the prepared statement is incremented. ** ** 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. */ case OP_Prev: /* jump */ case OP_Next: { /* jump */ VdbeCursor *pC; BtCursor *pCrsr; int res; CHECK_FOR_INTERRUPT; assert( pOp->p1>=0 && pOp->p1<p->nCursor ); assert( pOp->p5<=ArraySize(p->aCounter) ); assert( pOp->p3==0 || pOp->p3==1 ); pC = p->apCsr[pOp->p1]; if( pC==0 ){ break; /* See ticket #2273 */ } pCrsr = pC->pCursor; if( pCrsr==0 ){ pC->nullRow = 1; break; } res = pOp->p3; assert( res==0 || pC->isIndex==1 ); testcase( res==1 ); testcase( res==0 ); assert( pC->deferredMoveto==0 ); rc = pOp->opcode==OP_Next ? sqlite3BtreeNext(pCrsr, &res) : sqlite3BtreePrevious(pCrsr, &res); pC->nullRow = (u8)res; pC->cacheStatus = CACHE_STALE; if( res==0 ){ pc = pOp->p2 - 1; |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
249 250 251 252 253 254 255 256 257 258 259 260 261 262 | #define WHERE_IDX_ONLY 0x00800000 /* Use index only - omit table */ #define WHERE_ORDERBY 0x01000000 /* Output will appear in correct order */ #define WHERE_REVERSE 0x02000000 /* Scan in reverse order */ #define WHERE_UNIQUE 0x04000000 /* Selects no more than one row */ #define WHERE_VIRTUALTABLE 0x08000000 /* Use virtual-table processing */ #define WHERE_MULTI_OR 0x10000000 /* OR using multiple indices */ #define WHERE_TEMP_INDEX 0x20000000 /* Uses an ephemeral index */ /* ** Initialize a preallocated WhereClause structure. */ static void whereClauseInit( WhereClause *pWC, /* The WhereClause to be initialized */ Parse *pParse, /* The parsing context */ | > | 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 | #define WHERE_IDX_ONLY 0x00800000 /* Use index only - omit table */ #define WHERE_ORDERBY 0x01000000 /* Output will appear in correct order */ #define WHERE_REVERSE 0x02000000 /* Scan in reverse order */ #define WHERE_UNIQUE 0x04000000 /* Selects no more than one row */ #define WHERE_VIRTUALTABLE 0x08000000 /* Use virtual-table processing */ #define WHERE_MULTI_OR 0x10000000 /* OR using multiple indices */ #define WHERE_TEMP_INDEX 0x20000000 /* Uses an ephemeral index */ #define WHERE_UNQ_WANTED 0x40000000 /* True if UNIQUE would be helpful */ /* ** Initialize a preallocated WhereClause structure. */ static void whereClauseInit( WhereClause *pWC, /* The WhereClause to be initialized */ Parse *pParse, /* The parsing context */ |
︙ | ︙ | |||
2874 2875 2876 2877 2878 2879 2880 | if( pBtm ){ nBound++; wsFlags |= WHERE_BTM_LIMIT; used |= pBtm->prereqRight; } wsFlags |= (WHERE_COLUMN_RANGE|WHERE_ROWID_RANGE); } | | | | 2875 2876 2877 2878 2879 2880 2881 2882 2883 2884 2885 2886 2887 2888 2889 2890 2891 2892 2893 | if( pBtm ){ nBound++; wsFlags |= WHERE_BTM_LIMIT; used |= pBtm->prereqRight; } wsFlags |= (WHERE_COLUMN_RANGE|WHERE_ROWID_RANGE); } }else{ testcase( wsFlags & WHERE_COLUMN_IN ); testcase( wsFlags & WHERE_COLUMN_NULL ); if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){ wsFlags |= (pProbe->onError!=OE_None) ? WHERE_UNIQUE : WHERE_UNQ_WANTED; } } /* If there is an ORDER BY clause and the index being considered will ** naturally scan rows in the required order, set the appropriate flags ** in wsFlags. Otherwise, if there is an ORDER BY clause but the index ** will scan rows in a different order, set the bSort variable. */ |
︙ | ︙ | |||
4012 4013 4014 4015 4016 4017 4018 4019 4020 4021 4022 4023 4024 4025 | pLevel->op = OP_Noop; }else if( bRev ){ pLevel->op = OP_Prev; }else{ pLevel->op = OP_Next; } pLevel->p1 = iIdxCur; }else #ifndef SQLITE_OMIT_OR_OPTIMIZATION if( pLevel->plan.wsFlags & WHERE_MULTI_OR ){ /* Case 4: Two or more separately indexed terms connected by OR ** ** Example: | > > | 4013 4014 4015 4016 4017 4018 4019 4020 4021 4022 4023 4024 4025 4026 4027 4028 | pLevel->op = OP_Noop; }else if( bRev ){ pLevel->op = OP_Prev; }else{ pLevel->op = OP_Next; } pLevel->p1 = iIdxCur; assert( (WHERE_UNQ_WANTED>>30)==1 ); pLevel->p3 = (pLevel->plan.wsFlags>>30)&1; }else #ifndef SQLITE_OMIT_OR_OPTIMIZATION if( pLevel->plan.wsFlags & WHERE_MULTI_OR ){ /* Case 4: Two or more separately indexed terms connected by OR ** ** Example: |
︙ | ︙ | |||
4874 4875 4876 4877 4878 4879 4880 | /* Generate loop termination code. */ sqlite3ExprCacheClear(pParse); for(i=pWInfo->nLevel-1; i>=0; i--){ pLevel = &pWInfo->a[i]; sqlite3VdbeResolveLabel(v, pLevel->addrCont); if( pLevel->op!=OP_Noop ){ | | | 4877 4878 4879 4880 4881 4882 4883 4884 4885 4886 4887 4888 4889 4890 4891 | /* Generate loop termination code. */ sqlite3ExprCacheClear(pParse); for(i=pWInfo->nLevel-1; i>=0; i--){ pLevel = &pWInfo->a[i]; sqlite3VdbeResolveLabel(v, pLevel->addrCont); if( pLevel->op!=OP_Noop ){ sqlite3VdbeAddOp3(v, pLevel->op, pLevel->p1, pLevel->p2, pLevel->p3); sqlite3VdbeChangeP5(v, pLevel->p5); } if( pLevel->plan.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--){ |
︙ | ︙ |
tool/mkopts.tcl became executable.
︙ | ︙ |