/ Check-in [a2c347fa]
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 | branch-3.8.2
Files: files | file ages | folders
SHA1: a2c347faf91d82cf8734621bf378a6dd68b00957
User & Date: drh 2014-01-28 00:49:55
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: 6c643e45 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: a2c347fa 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: c697d2f8 user: mistachkin tags: branch-3.8.2
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/btree.c.

  4813   4813   }
  4814   4814   
  4815   4815   /*
  4816   4816   ** Advance the cursor to the next entry in the database.  If
  4817   4817   ** successful then set *pRes=0.  If the cursor
  4818   4818   ** was already pointing to the last entry in the database before
  4819   4819   ** this routine was called, then set *pRes=1.
         4820  +**
         4821  +** The calling function will set *pRes to 0 or 1.  The initial *pRes value
         4822  +** will be 1 if the cursor being stepped corresponds to an SQL index and
         4823  +** if this routine could have been skipped if that SQL index had been
         4824  +** a unique index.  Otherwise the caller will have set *pRes to zero.
         4825  +** Zero is the common case. The btree implementation is free to use the
         4826  +** initial *pRes value as a hint to improve performance, but the current
         4827  +** SQLite btree implementation does not. (Note that the comdb2 btree
         4828  +** implementation does use this hint, however.)
  4820   4829   */
  4821   4830   int sqlite3BtreeNext(BtCursor *pCur, int *pRes){
  4822   4831     int rc;
  4823   4832     int idx;
  4824   4833     MemPage *pPage;
  4825   4834   
  4826   4835     assert( cursorHoldsMutex(pCur) );
  4827   4836     assert( pRes!=0 );
         4837  +  assert( *pRes==0 || *pRes==1 );
  4828   4838     assert( pCur->skipNext==0 || pCur->eState!=CURSOR_VALID );
  4829   4839     if( pCur->eState!=CURSOR_VALID ){
  4830   4840       rc = restoreCursorPosition(pCur);
  4831   4841       if( rc!=SQLITE_OK ){
  4832   4842         *pRes = 0;
  4833   4843         return rc;
  4834   4844       }
................................................................................
  4899   4909   
  4900   4910   
  4901   4911   /*
  4902   4912   ** Step the cursor to the back to the previous entry in the database.  If
  4903   4913   ** successful then set *pRes=0.  If the cursor
  4904   4914   ** was already pointing to the first entry in the database before
  4905   4915   ** this routine was called, then set *pRes=1.
         4916  +**
         4917  +** The calling function will set *pRes to 0 or 1.  The initial *pRes value
         4918  +** will be 1 if the cursor being stepped corresponds to an SQL index and
         4919  +** if this routine could have been skipped if that SQL index had been
         4920  +** a unique index.  Otherwise the caller will have set *pRes to zero.
         4921  +** Zero is the common case. The btree implementation is free to use the
         4922  +** initial *pRes value as a hint to improve performance, but the current
         4923  +** SQLite btree implementation does not. (Note that the comdb2 btree
         4924  +** implementation does use this hint, however.)
  4906   4925   */
  4907   4926   int sqlite3BtreePrevious(BtCursor *pCur, int *pRes){
  4908   4927     int rc;
  4909   4928     MemPage *pPage;
  4910   4929   
  4911   4930     assert( cursorHoldsMutex(pCur) );
  4912   4931     assert( pRes!=0 );
         4932  +  assert( *pRes==0 || *pRes==1 );
  4913   4933     assert( pCur->skipNext==0 || pCur->eState!=CURSOR_VALID );
  4914   4934     pCur->atLast = 0;
  4915   4935     if( pCur->eState!=CURSOR_VALID ){
  4916   4936       if( ALWAYS(pCur->eState>=CURSOR_REQUIRESEEK) ){
  4917   4937         rc = btreeRestoreCursorPosition(pCur);
  4918   4938         if( rc!=SQLITE_OK ){
  4919   4939           *pRes = 0;
................................................................................
  7146   7166     ** the cursor to the largest entry in the tree that is smaller than
  7147   7167     ** the entry being deleted. This cell will replace the cell being deleted
  7148   7168     ** from the internal node. The 'previous' entry is used for this instead
  7149   7169     ** of the 'next' entry, as the previous entry is always a part of the
  7150   7170     ** sub-tree headed by the child page of the cell being deleted. This makes
  7151   7171     ** balancing the tree following the delete operation easier.  */
  7152   7172     if( !pPage->leaf ){
  7153         -    int notUsed;
         7173  +    int notUsed = 0;
  7154   7174       rc = sqlite3BtreePrevious(pCur, &notUsed);
  7155   7175       if( rc ) return rc;
  7156   7176     }
  7157   7177   
  7158   7178     /* Save the positions of any other cursors open on this table before
  7159   7179     ** making any modifications. Make the page containing the entry to be 
  7160   7180     ** deleted writable. Then free any overflow pages associated with the 

Changes to src/vdbe.c.

  3576   3576     pC->deferredMoveto = 0;
  3577   3577     pC->cacheStatus = CACHE_STALE;
  3578   3578   #ifdef SQLITE_TEST
  3579   3579     sqlite3_search_count++;
  3580   3580   #endif
  3581   3581     if( oc>=OP_SeekGe ){  assert( oc==OP_SeekGe || oc==OP_SeekGt );
  3582   3582       if( res<0 || (res==0 && oc==OP_SeekGt) ){
         3583  +      res = 0;
  3583   3584         rc = sqlite3BtreeNext(pC->pCursor, &res);
  3584   3585         if( rc!=SQLITE_OK ) goto abort_due_to_error;
  3585   3586         pC->rowidIsValid = 0;
  3586   3587       }else{
  3587   3588         res = 0;
  3588   3589       }
  3589   3590     }else{
  3590   3591       assert( oc==OP_SeekLt || oc==OP_SeekLe );
  3591   3592       if( res>0 || (res==0 && oc==OP_SeekLt) ){
         3593  +      res = 0;
  3592   3594         rc = sqlite3BtreePrevious(pC->pCursor, &res);
  3593   3595         if( rc!=SQLITE_OK ) goto abort_due_to_error;
  3594   3596         pC->rowidIsValid = 0;
  3595   3597       }else{
  3596   3598         /* res might be negative because the table is empty.  Check to
  3597   3599         ** see if this is the case.
  3598   3600         */
................................................................................
  4438   4440     assert( pOp->p2>0 && pOp->p2<p->nOp );
  4439   4441     if( res ){
  4440   4442       pc = pOp->p2 - 1;
  4441   4443     }
  4442   4444     break;
  4443   4445   }
  4444   4446   
  4445         -/* Opcode: Next P1 P2 * * P5
         4447  +/* Opcode: Next P1 P2 P3 * P5
  4446   4448   **
  4447   4449   ** Advance cursor P1 so that it points to the next key/data pair in its
  4448   4450   ** table or index.  If there are no more key/value pairs then fall through
  4449   4451   ** to the following instruction.  But if the cursor advance was successful,
  4450   4452   ** jump immediately to P2.
  4451   4453   **
  4452   4454   ** The P1 cursor must be for a real table, not a pseudo-table.  P1 must have
  4453   4455   ** been opened prior to this opcode or the program will segfault.
         4456  +**
         4457  +** The P3 value is a hint to the btree implementation. If P3==1, that
         4458  +** means P1 is an SQL index and that this instruction could have been
         4459  +** omitted if that index had been unique.  P3 is usually 0.  P3 is
         4460  +** always either 0 or 1.
  4454   4461   **
  4455   4462   ** P4 is always of type P4_ADVANCE. The function pointer points to
  4456   4463   ** sqlite3BtreeNext().
  4457   4464   **
  4458   4465   ** If P5 is positive and the jump is taken, then event counter
  4459   4466   ** number P5-1 in the prepared statement is incremented.
  4460   4467   **
  4461   4468   ** See also: Prev, NextIfOpen
  4462   4469   */
  4463         -/* Opcode: NextIfOpen P1 P2 * * P5
         4470  +/* Opcode: NextIfOpen P1 P2 P3 * P5
  4464   4471   **
  4465   4472   ** This opcode works just like OP_Next except that if cursor P1 is not
  4466   4473   ** open it behaves a no-op.
  4467   4474   */
  4468         -/* Opcode: Prev P1 P2 * * P5
         4475  +/* Opcode: Prev P1 P2 P3 * P5
  4469   4476   **
  4470   4477   ** Back up cursor P1 so that it points to the previous key/data pair in its
  4471   4478   ** table or index.  If there is no previous key/value pairs then fall through
  4472   4479   ** to the following instruction.  But if the cursor backup was successful,
  4473   4480   ** jump immediately to P2.
  4474   4481   **
  4475   4482   ** The P1 cursor must be for a real table, not a pseudo-table.  If P1 is
  4476   4483   ** not open then the behavior is undefined.
         4484  +**
         4485  +** The P3 value is a hint to the btree implementation. If P3==1, that
         4486  +** means P1 is an SQL index and that this instruction could have been
         4487  +** omitted if that index had been unique.  P3 is usually 0.  P3 is
         4488  +** always either 0 or 1.
  4477   4489   **
  4478   4490   ** P4 is always of type P4_ADVANCE. The function pointer points to
  4479   4491   ** sqlite3BtreePrevious().
  4480   4492   **
  4481   4493   ** If P5 is positive and the jump is taken, then event counter
  4482   4494   ** number P5-1 in the prepared statement is incremented.
  4483   4495   */
  4484         -/* Opcode: PrevIfOpen P1 P2 * * P5
         4496  +/* Opcode: PrevIfOpen P1 P2 P3 * P5
  4485   4497   **
  4486   4498   ** This opcode works just like OP_Prev except that if cursor P1 is not
  4487   4499   ** open it behaves a no-op.
  4488   4500   */
  4489   4501   case OP_SorterNext: {  /* jump */
  4490   4502     VdbeCursor *pC;
  4491   4503     int res;
................................................................................
  4499   4511     if( p->apCsr[pOp->p1]==0 ) break;
  4500   4512     /* Fall through */
  4501   4513   case OP_Prev:          /* jump */
  4502   4514   case OP_Next:          /* jump */
  4503   4515     assert( pOp->p1>=0 && pOp->p1<p->nCursor );
  4504   4516     assert( pOp->p5<ArraySize(p->aCounter) );
  4505   4517     pC = p->apCsr[pOp->p1];
         4518  +  res = pOp->p3;
  4506   4519     assert( pC!=0 );
  4507   4520     assert( pC->deferredMoveto==0 );
  4508   4521     assert( pC->pCursor );
         4522  +  assert( res==0 || (res==1 && pC->isTable==0) );
         4523  +  testcase( res==1 );
  4509   4524     assert( pOp->opcode!=OP_Next || pOp->p4.xAdvance==sqlite3BtreeNext );
  4510   4525     assert( pOp->opcode!=OP_Prev || pOp->p4.xAdvance==sqlite3BtreePrevious );
  4511   4526     assert( pOp->opcode!=OP_NextIfOpen || pOp->p4.xAdvance==sqlite3BtreeNext );
  4512   4527     assert( pOp->opcode!=OP_PrevIfOpen || pOp->p4.xAdvance==sqlite3BtreePrevious);
  4513   4528     rc = pOp->p4.xAdvance(pC->pCursor, &res);
  4514   4529   next_tail:
  4515   4530     pC->cacheStatus = CACHE_STALE;

Changes to src/where.c.

  3178   3178         pLevel->op = OP_Noop;
  3179   3179       }else if( bRev ){
  3180   3180         pLevel->op = OP_Prev;
  3181   3181       }else{
  3182   3182         pLevel->op = OP_Next;
  3183   3183       }
  3184   3184       pLevel->p1 = iIdxCur;
         3185  +    assert( (WHERE_UNQ_WANTED>>16)==1 );
         3186  +    pLevel->p3 = (pLoop->wsFlags>>16)&1;
  3185   3187       if( (pLoop->wsFlags & WHERE_CONSTRAINT)==0 ){
  3186   3188         pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
  3187   3189       }else{
  3188   3190         assert( pLevel->p5==0 );
  3189   3191       }
  3190   3192     }else
  3191   3193   
................................................................................
  3974   3976         pNew->nOut = nRowEst + nInMul + nIn;
  3975   3977       }else if( pTerm->eOperator & (WO_EQ) ){
  3976   3978         assert(
  3977   3979           (pNew->wsFlags & (WHERE_COLUMN_NULL|WHERE_COLUMN_IN|WHERE_SKIPSCAN))!=0
  3978   3980           || nInMul==0
  3979   3981         );
  3980   3982         pNew->wsFlags |= WHERE_COLUMN_EQ;
  3981         -      if( iCol<0  
  3982         -       || (pProbe->onError!=OE_None && nInMul==0
  3983         -           && pNew->u.btree.nEq==pProbe->nKeyCol-1)
  3984         -      ){
         3983  +      if( iCol<0 || (nInMul==0 && pNew->u.btree.nEq==pProbe->nKeyCol-1)){
  3985   3984           assert( (pNew->wsFlags & WHERE_COLUMN_IN)==0 || iCol<0 );
  3986         -        pNew->wsFlags |= WHERE_ONEROW;
         3985  +        if( iCol>=0 && pProbe->onError==OE_None ){
         3986  +          pNew->wsFlags |= WHERE_UNQ_WANTED;
         3987  +        }else{
         3988  +          pNew->wsFlags |= WHERE_ONEROW;
         3989  +        }
  3987   3990         }
  3988   3991         pNew->u.btree.nEq++;
  3989   3992         pNew->nOut = nRowEst + nInMul;
  3990   3993       }else if( pTerm->eOperator & (WO_ISNULL) ){
  3991   3994         pNew->wsFlags |= WHERE_COLUMN_NULL;
  3992   3995         pNew->u.btree.nEq++;
  3993   3996         /* TUNING: IS NULL selects 2 rows */
................................................................................
  5769   5772     sqlite3ExprCacheClear(pParse);
  5770   5773     for(i=pWInfo->nLevel-1; i>=0; i--){
  5771   5774       int addr;
  5772   5775       pLevel = &pWInfo->a[i];
  5773   5776       pLoop = pLevel->pWLoop;
  5774   5777       sqlite3VdbeResolveLabel(v, pLevel->addrCont);
  5775   5778       if( pLevel->op!=OP_Noop ){
  5776         -      sqlite3VdbeAddOp2(v, pLevel->op, pLevel->p1, pLevel->p2);
         5779  +      sqlite3VdbeAddOp3(v, pLevel->op, pLevel->p1, pLevel->p2, pLevel->p3);
  5777   5780         sqlite3VdbeChangeP5(v, pLevel->p5);
  5778   5781       }
  5779   5782       if( pLoop->wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){
  5780   5783         struct InLoop *pIn;
  5781   5784         int j;
  5782   5785         sqlite3VdbeResolveLabel(v, pLevel->addrNxt);
  5783   5786         for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){

Changes to src/whereInt.h.

    66     66     int addrBrk;          /* Jump here to break out of the loop */
    67     67     int addrNxt;          /* Jump here to start the next IN combination */
    68     68     int addrSkip;         /* Jump here for next iteration of skip-scan */
    69     69     int addrCont;         /* Jump here to continue with the next loop cycle */
    70     70     int addrFirst;        /* First instruction of interior of the loop */
    71     71     int addrBody;         /* Beginning of the body of this loop */
    72     72     u8 iFrom;             /* Which entry in the FROM clause */
    73         -  u8 op, p5;            /* Opcode and P5 of the opcode that ends the loop */
           73  +  u8 op, p3, p5;        /* Opcode, P3 & P5 of the opcode that ends the loop */
    74     74     int p1, p2;           /* Operands of the opcode used to ends the loop */
    75     75     union {               /* Information that depends on pWLoop->wsFlags */
    76     76       struct {
    77     77         int nIn;              /* Number of entries in aInLoop[] */
    78     78         struct InLoop {
    79     79           int iCur;              /* The VDBE cursor used by this IN operator */
    80     80           int addrInTop;         /* Top of the IN loop */
................................................................................
   453    453   #define WHERE_INDEXED      0x00000200  /* WhereLoop.u.btree.pIndex is valid */
   454    454   #define WHERE_VIRTUALTABLE 0x00000400  /* WhereLoop.u.vtab is valid */
   455    455   #define WHERE_IN_ABLE      0x00000800  /* Able to support an IN operator */
   456    456   #define WHERE_ONEROW       0x00001000  /* Selects no more than one row */
   457    457   #define WHERE_MULTI_OR     0x00002000  /* OR using multiple indices */
   458    458   #define WHERE_AUTO_INDEX   0x00004000  /* Uses an ephemeral index */
   459    459   #define WHERE_SKIPSCAN     0x00008000  /* Uses the skip-scan algorithm */
          460  +#define WHERE_UNQ_WANTED   0x00010000  /* WHERE_ONEROW would have been helpful*/