/ Check-in [a5aae174]
Login

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 | SQL archive
Timelines: family | ancestors | descendants | both | branch-3.7.2
Files: files | file ages | folders
SHA1:a5aae1743a208e7792497dfebf3e8311140ae595
User & Date: drh 2011-03-31 18:36:17
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: e8177e01 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: a5aae174 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: 68daf20d user: drh tags: branch-3.7.2
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/btree.c.

  4548   4548   }
  4549   4549   
  4550   4550   /*
  4551   4551   ** Advance the cursor to the next entry in the database.  If
  4552   4552   ** successful then set *pRes=0.  If the cursor
  4553   4553   ** was already pointing to the last entry in the database before
  4554   4554   ** this routine was called, then set *pRes=1.
         4555  +**
         4556  +** The calling function will set *pRes to 0 or 1.  The initial *pRes value
         4557  +** will be 1 if the cursor being stepped corresponds to an SQL index and
         4558  +** if this routine could have been skipped if that SQL index had been
         4559  +** a unique index.  Otherwise the caller will have set *pRes to zero.  
         4560  +** Zero is the common case. The btree implementation is free to use the
         4561  +** initial *pRes value as a hint to improve performance, but the current 
         4562  +** SQLite btree implementation does not. (Note that the comdb2 btree 
         4563  +** implementation does use this hint, however.)
  4555   4564   */
  4556   4565   int sqlite3BtreeNext(BtCursor *pCur, int *pRes){
  4557   4566     int rc;
  4558   4567     int idx;
  4559   4568     MemPage *pPage;
  4560   4569   
  4561   4570     assert( cursorHoldsMutex(pCur) );
         4571  +  assert( pRes!=0 );
         4572  +  assert( *pRes==0 || *pRes==1 );
  4562   4573     rc = restoreCursorPosition(pCur);
  4563   4574     if( rc!=SQLITE_OK ){
  4564   4575       return rc;
  4565   4576     }
  4566         -  assert( pRes!=0 );
  4567   4577     if( CURSOR_INVALID==pCur->eState ){
  4568   4578       *pRes = 1;
  4569   4579       return SQLITE_OK;
  4570   4580     }
  4571   4581     if( pCur->skipNext>0 ){
  4572   4582       pCur->skipNext = 0;
  4573   4583       *pRes = 0;
................................................................................
  4617   4627   
  4618   4628   
  4619   4629   /*
  4620   4630   ** Step the cursor to the back to the previous entry in the database.  If
  4621   4631   ** successful then set *pRes=0.  If the cursor
  4622   4632   ** was already pointing to the first entry in the database before
  4623   4633   ** this routine was called, then set *pRes=1.
         4634  +**
         4635  +** The calling function will set *pRes to 0 or 1.  The initial *pRes value
         4636  +** will be 1 if the cursor being stepped corresponds to an SQL index and
         4637  +** if this routine could have been skipped if that SQL index had been
         4638  +** a unique index.  Otherwise the caller will have set *pRes to zero.  
         4639  +** Zero is the common case. The btree implementation is free to use the
         4640  +** initial *pRes value as a hint to improve performance, but the current 
         4641  +** SQLite btree implementation does not. (Note that the comdb2 btree 
         4642  +** implementation does use this hint, however.)
  4624   4643   */
  4625   4644   int sqlite3BtreePrevious(BtCursor *pCur, int *pRes){
  4626   4645     int rc;
  4627   4646     MemPage *pPage;
  4628   4647   
  4629   4648     assert( cursorHoldsMutex(pCur) );
         4649  +  assert( pRes!=0 );
         4650  +  assert( *pRes==0 || *pRes==1 );
  4630   4651     rc = restoreCursorPosition(pCur);
  4631   4652     if( rc!=SQLITE_OK ){
  4632   4653       return rc;
  4633   4654     }
  4634   4655     pCur->atLast = 0;
  4635   4656     if( CURSOR_INVALID==pCur->eState ){
  4636   4657       *pRes = 1;
................................................................................
  6774   6795     ** the cursor to the largest entry in the tree that is smaller than
  6775   6796     ** the entry being deleted. This cell will replace the cell being deleted
  6776   6797     ** from the internal node. The 'previous' entry is used for this instead
  6777   6798     ** of the 'next' entry, as the previous entry is always a part of the
  6778   6799     ** sub-tree headed by the child page of the cell being deleted. This makes
  6779   6800     ** balancing the tree following the delete operation easier.  */
  6780   6801     if( !pPage->leaf ){
  6781         -    int notUsed;
         6802  +    int notUsed = 0;
  6782   6803       rc = sqlite3BtreePrevious(pCur, &notUsed);
  6783   6804       if( rc ) return rc;
  6784   6805     }
  6785   6806   
  6786   6807     /* Save the positions of any other cursors open on this table before
  6787   6808     ** making any modifications. Make the page containing the entry to be 
  6788   6809     ** deleted writable. Then free any overflow pages associated with the 

Changes to src/sqliteInt.h.

  1861   1861     int iTabCur;          /* The VDBE cursor used to access the table */
  1862   1862     int iIdxCur;          /* The VDBE cursor used to access pIdx */
  1863   1863     int addrBrk;          /* Jump here to break out of the loop */
  1864   1864     int addrNxt;          /* Jump here to start the next IN combination */
  1865   1865     int addrCont;         /* Jump here to continue with the next loop cycle */
  1866   1866     int addrFirst;        /* First instruction of interior of the loop */
  1867   1867     u8 iFrom;             /* Which entry in the FROM clause */
  1868         -  u8 op, p5;            /* Opcode and P5 of the opcode that ends the loop */
  1869         -  int p1, p2;           /* Operands of the opcode used to ends the loop */
         1868  +  u8 op, p3, p5;        /* Opcode, P3, and P5 of the end-of-loop instruction */
         1869  +  int p1, p2;           /* P1 and P2 operands of the end-of-loop instruction */
  1870   1870     union {               /* Information that depends on plan.wsFlags */
  1871   1871       struct {
  1872   1872         int nIn;              /* Number of entries in aInLoop[] */
  1873   1873         struct InLoop {
  1874   1874           int iCur;              /* The VDBE cursor used by this IN operator */
  1875   1875           int addrInTop;         /* Top of the IN loop */
  1876   1876         } *aInLoop;           /* Information about each nested IN operator */

Changes to src/vdbe.c.

  3309   3309       pC->deferredMoveto = 0;
  3310   3310       pC->cacheStatus = CACHE_STALE;
  3311   3311   #ifdef SQLITE_TEST
  3312   3312       sqlite3_search_count++;
  3313   3313   #endif
  3314   3314       if( oc>=OP_SeekGe ){  assert( oc==OP_SeekGe || oc==OP_SeekGt );
  3315   3315         if( res<0 || (res==0 && oc==OP_SeekGt) ){
         3316  +        res = 0;
  3316   3317           rc = sqlite3BtreeNext(pC->pCursor, &res);
  3317   3318           if( rc!=SQLITE_OK ) goto abort_due_to_error;
  3318   3319           pC->rowidIsValid = 0;
  3319   3320         }else{
  3320   3321           res = 0;
  3321   3322         }
  3322   3323       }else{
  3323   3324         assert( oc==OP_SeekLt || oc==OP_SeekLe );
  3324   3325         if( res>0 || (res==0 && oc==OP_SeekLt) ){
         3326  +        res = 0;
  3325   3327           rc = sqlite3BtreePrevious(pC->pCursor, &res);
  3326   3328           if( rc!=SQLITE_OK ) goto abort_due_to_error;
  3327   3329           pC->rowidIsValid = 0;
  3328   3330         }else{
  3329   3331           /* res might be negative because the table is empty.  Check to
  3330   3332           ** see if this is the case.
  3331   3333           */
................................................................................
  4162   4164     assert( pOp->p2>0 && pOp->p2<p->nOp );
  4163   4165     if( res ){
  4164   4166       pc = pOp->p2 - 1;
  4165   4167     }
  4166   4168     break;
  4167   4169   }
  4168   4170   
  4169         -/* Opcode: Next P1 P2 * * P5
         4171  +/* Opcode: Next P1 P2 P3 * P5
  4170   4172   **
  4171   4173   ** Advance cursor P1 so that it points to the next key/data pair in its
  4172   4174   ** table or index.  If there are no more key/value pairs then fall through
  4173   4175   ** to the following instruction.  But if the cursor advance was successful,
  4174   4176   ** jump immediately to P2.
  4175   4177   **
  4176   4178   ** The P1 cursor must be for a real table, not a pseudo-table.
  4177   4179   **
  4178   4180   ** If P5 is positive and the jump is taken, then event counter
  4179   4181   ** number P5-1 in the prepared statement is incremented.
  4180   4182   **
         4183  +** The P3 value is a hint to the btree implementation. If P3==1, that
         4184  +** means P1 is an SQL index and that this instruction could have been
         4185  +** omitted if that index had been unique.  P3 is usually 0.  P3 is 
         4186  +** always either 0 or 1.
         4187  +**
  4181   4188   ** See also: Prev
  4182   4189   */
  4183         -/* Opcode: Prev P1 P2 * * P5
         4190  +/* Opcode: Prev P1 P2 P3 * P5
  4184   4191   **
  4185   4192   ** Back up cursor P1 so that it points to the previous key/data pair in its
  4186   4193   ** table or index.  If there is no previous key/value pairs then fall through
  4187   4194   ** to the following instruction.  But if the cursor backup was successful,
  4188   4195   ** jump immediately to P2.
  4189   4196   **
  4190   4197   ** The P1 cursor must be for a real table, not a pseudo-table.
  4191   4198   **
  4192   4199   ** If P5 is positive and the jump is taken, then event counter
  4193   4200   ** number P5-1 in the prepared statement is incremented.
         4201  +**
         4202  +** The P3 value is a hint to the btree implementation. If P3==1, that
         4203  +** means P1 is an SQL index and that this instruction could have been
         4204  +** omitted if that index had been unique.  P3 is usually 0.  P3 is 
         4205  +** always either 0 or 1.
  4194   4206   */
  4195   4207   case OP_Prev:          /* jump */
  4196   4208   case OP_Next: {        /* jump */
  4197   4209     VdbeCursor *pC;
  4198   4210     BtCursor *pCrsr;
  4199   4211     int res;
  4200   4212   
  4201   4213     CHECK_FOR_INTERRUPT;
  4202   4214     assert( pOp->p1>=0 && pOp->p1<p->nCursor );
  4203   4215     assert( pOp->p5<=ArraySize(p->aCounter) );
         4216  +  assert( pOp->p3==0 || pOp->p3==1 );
  4204   4217     pC = p->apCsr[pOp->p1];
  4205   4218     if( pC==0 ){
  4206   4219       break;  /* See ticket #2273 */
  4207   4220     }
  4208   4221     pCrsr = pC->pCursor;
  4209   4222     if( pCrsr==0 ){
  4210   4223       pC->nullRow = 1;
  4211   4224       break;
  4212   4225     }
  4213         -  res = 1;
         4226  +  res = pOp->p3;
         4227  +  assert( res==0 || pC->isIndex==1 );
         4228  +  testcase( res==1 );
         4229  +  testcase( res==0 );
  4214   4230     assert( pC->deferredMoveto==0 );
  4215   4231     rc = pOp->opcode==OP_Next ? sqlite3BtreeNext(pCrsr, &res) :
  4216   4232                                 sqlite3BtreePrevious(pCrsr, &res);
  4217   4233     pC->nullRow = (u8)res;
  4218   4234     pC->cacheStatus = CACHE_STALE;
  4219   4235     if( res==0 ){
  4220   4236       pc = pOp->p2 - 1;

Changes to src/where.c.

   249    249   #define WHERE_IDX_ONLY     0x00800000  /* Use index only - omit table */
   250    250   #define WHERE_ORDERBY      0x01000000  /* Output will appear in correct order */
   251    251   #define WHERE_REVERSE      0x02000000  /* Scan in reverse order */
   252    252   #define WHERE_UNIQUE       0x04000000  /* Selects no more than one row */
   253    253   #define WHERE_VIRTUALTABLE 0x08000000  /* Use virtual-table processing */
   254    254   #define WHERE_MULTI_OR     0x10000000  /* OR using multiple indices */
   255    255   #define WHERE_TEMP_INDEX   0x20000000  /* Uses an ephemeral index */
          256  +#define WHERE_UNQ_WANTED   0x40000000  /* True if UNIQUE would be helpful */
   256    257   
   257    258   /*
   258    259   ** Initialize a preallocated WhereClause structure.
   259    260   */
   260    261   static void whereClauseInit(
   261    262     WhereClause *pWC,        /* The WhereClause to be initialized */
   262    263     Parse *pParse,           /* The parsing context */
................................................................................
  2874   2875           if( pBtm ){
  2875   2876             nBound++;
  2876   2877             wsFlags |= WHERE_BTM_LIMIT;
  2877   2878             used |= pBtm->prereqRight;
  2878   2879           }
  2879   2880           wsFlags |= (WHERE_COLUMN_RANGE|WHERE_ROWID_RANGE);
  2880   2881         }
  2881         -    }else if( pProbe->onError!=OE_None ){
         2882  +    }else{
  2882   2883         testcase( wsFlags & WHERE_COLUMN_IN );
  2883   2884         testcase( wsFlags & WHERE_COLUMN_NULL );
  2884   2885         if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){
  2885         -        wsFlags |= WHERE_UNIQUE;
         2886  +        wsFlags |= (pProbe->onError!=OE_None) ? WHERE_UNIQUE : WHERE_UNQ_WANTED;
  2886   2887         }
  2887   2888       }
  2888   2889   
  2889   2890       /* If there is an ORDER BY clause and the index being considered will
  2890   2891       ** naturally scan rows in the required order, set the appropriate flags
  2891   2892       ** in wsFlags. Otherwise, if there is an ORDER BY clause but the index
  2892   2893       ** will scan rows in a different order, set the bSort variable.  */
................................................................................
  4012   4013         pLevel->op = OP_Noop;
  4013   4014       }else if( bRev ){
  4014   4015         pLevel->op = OP_Prev;
  4015   4016       }else{
  4016   4017         pLevel->op = OP_Next;
  4017   4018       }
  4018   4019       pLevel->p1 = iIdxCur;
         4020  +    assert( (WHERE_UNQ_WANTED>>30)==1 );
         4021  +    pLevel->p3 = (pLevel->plan.wsFlags>>30)&1;
  4019   4022     }else
  4020   4023   
  4021   4024   #ifndef SQLITE_OMIT_OR_OPTIMIZATION
  4022   4025     if( pLevel->plan.wsFlags & WHERE_MULTI_OR ){
  4023   4026       /* Case 4:  Two or more separately indexed terms connected by OR
  4024   4027       **
  4025   4028       ** Example:
................................................................................
  4874   4877     /* Generate loop termination code.
  4875   4878     */
  4876   4879     sqlite3ExprCacheClear(pParse);
  4877   4880     for(i=pWInfo->nLevel-1; i>=0; i--){
  4878   4881       pLevel = &pWInfo->a[i];
  4879   4882       sqlite3VdbeResolveLabel(v, pLevel->addrCont);
  4880   4883       if( pLevel->op!=OP_Noop ){
  4881         -      sqlite3VdbeAddOp2(v, pLevel->op, pLevel->p1, pLevel->p2);
         4884  +      sqlite3VdbeAddOp3(v, pLevel->op, pLevel->p1, pLevel->p2, pLevel->p3);
  4882   4885         sqlite3VdbeChangeP5(v, pLevel->p5);
  4883   4886       }
  4884   4887       if( pLevel->plan.wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){
  4885   4888         struct InLoop *pIn;
  4886   4889         int j;
  4887   4890         sqlite3VdbeResolveLabel(v, pLevel->addrNxt);
  4888   4891         for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){

tool/mkopts.tcl became executable.