/ Check-in [6c643e45]
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 | trunk
Files: files | file ages | folders
SHA1: 6c643e45c274e755dc5a1a65673df79261c774be
User & Date: drh 2014-02-03 14:04:11
Context
2014-02-03
17:04
Performance optimizations in sqlite3PcacheFetch(). check-in: b60cc11e user: drh tags: trunk
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
13:52
Version 3.8.3 check-in: e816dd92 user: drh tags: trunk, release, version-3.8.3
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
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/btree.c.

  4773   4773   }
  4774   4774   
  4775   4775   /*
  4776   4776   ** Advance the cursor to the next entry in the database.  If
  4777   4777   ** successful then set *pRes=0.  If the cursor
  4778   4778   ** was already pointing to the last entry in the database before
  4779   4779   ** this routine was called, then set *pRes=1.
         4780  +**
         4781  +** The calling function will set *pRes to 0 or 1.  The initial *pRes value
         4782  +** will be 1 if the cursor being stepped corresponds to an SQL index and
         4783  +** if this routine could have been skipped if that SQL index had been
         4784  +** a unique index.  Otherwise the caller will have set *pRes to zero.
         4785  +** Zero is the common case. The btree implementation is free to use the
         4786  +** initial *pRes value as a hint to improve performance, but the current
         4787  +** SQLite btree implementation does not. (Note that the comdb2 btree
         4788  +** implementation does use this hint, however.)
  4780   4789   */
  4781   4790   int sqlite3BtreeNext(BtCursor *pCur, int *pRes){
  4782   4791     int rc;
  4783   4792     int idx;
  4784   4793     MemPage *pPage;
  4785   4794   
  4786   4795     assert( cursorHoldsMutex(pCur) );
  4787   4796     assert( pRes!=0 );
         4797  +  assert( *pRes==0 || *pRes==1 );
  4788   4798     assert( pCur->skipNext==0 || pCur->eState!=CURSOR_VALID );
  4789   4799     if( pCur->eState!=CURSOR_VALID ){
  4790   4800       rc = restoreCursorPosition(pCur);
  4791   4801       if( rc!=SQLITE_OK ){
  4792   4802         *pRes = 0;
  4793   4803         return rc;
  4794   4804       }
................................................................................
  4859   4869   
  4860   4870   
  4861   4871   /*
  4862   4872   ** Step the cursor to the back to the previous entry in the database.  If
  4863   4873   ** successful then set *pRes=0.  If the cursor
  4864   4874   ** was already pointing to the first entry in the database before
  4865   4875   ** this routine was called, then set *pRes=1.
         4876  +**
         4877  +** The calling function will set *pRes to 0 or 1.  The initial *pRes value
         4878  +** will be 1 if the cursor being stepped corresponds to an SQL index and
         4879  +** if this routine could have been skipped if that SQL index had been
         4880  +** a unique index.  Otherwise the caller will have set *pRes to zero.
         4881  +** Zero is the common case. The btree implementation is free to use the
         4882  +** initial *pRes value as a hint to improve performance, but the current
         4883  +** SQLite btree implementation does not. (Note that the comdb2 btree
         4884  +** implementation does use this hint, however.)
  4866   4885   */
  4867   4886   int sqlite3BtreePrevious(BtCursor *pCur, int *pRes){
  4868   4887     int rc;
  4869   4888     MemPage *pPage;
  4870   4889   
  4871   4890     assert( cursorHoldsMutex(pCur) );
  4872   4891     assert( pRes!=0 );
         4892  +  assert( *pRes==0 || *pRes==1 );
  4873   4893     assert( pCur->skipNext==0 || pCur->eState!=CURSOR_VALID );
  4874   4894     pCur->atLast = 0;
  4875   4895     if( pCur->eState!=CURSOR_VALID ){
  4876   4896       if( ALWAYS(pCur->eState>=CURSOR_REQUIRESEEK) ){
  4877   4897         rc = btreeRestoreCursorPosition(pCur);
  4878   4898         if( rc!=SQLITE_OK ){
  4879   4899           *pRes = 0;
................................................................................
  7092   7112     ** the cursor to the largest entry in the tree that is smaller than
  7093   7113     ** the entry being deleted. This cell will replace the cell being deleted
  7094   7114     ** from the internal node. The 'previous' entry is used for this instead
  7095   7115     ** of the 'next' entry, as the previous entry is always a part of the
  7096   7116     ** sub-tree headed by the child page of the cell being deleted. This makes
  7097   7117     ** balancing the tree following the delete operation easier.  */
  7098   7118     if( !pPage->leaf ){
  7099         -    int notUsed;
         7119  +    int notUsed = 0;
  7100   7120       rc = sqlite3BtreePrevious(pCur, &notUsed);
  7101   7121       if( rc ) return rc;
  7102   7122     }
  7103   7123   
  7104   7124     /* Save the positions of any other cursors open on this table before
  7105   7125     ** making any modifications. Make the page containing the entry to be 
  7106   7126     ** deleted writable. Then free any overflow pages associated with the 

Changes to src/vdbe.c.

  3595   3595     pC->deferredMoveto = 0;
  3596   3596     pC->cacheStatus = CACHE_STALE;
  3597   3597   #ifdef SQLITE_TEST
  3598   3598     sqlite3_search_count++;
  3599   3599   #endif
  3600   3600     if( oc>=OP_SeekGe ){  assert( oc==OP_SeekGe || oc==OP_SeekGt );
  3601   3601       if( res<0 || (res==0 && oc==OP_SeekGt) ){
         3602  +      res = 0;
  3602   3603         rc = sqlite3BtreeNext(pC->pCursor, &res);
  3603   3604         if( rc!=SQLITE_OK ) goto abort_due_to_error;
  3604   3605         pC->rowidIsValid = 0;
  3605   3606       }else{
  3606   3607         res = 0;
  3607   3608       }
  3608   3609     }else{
  3609   3610       assert( oc==OP_SeekLt || oc==OP_SeekLe );
  3610   3611       if( res>0 || (res==0 && oc==OP_SeekLt) ){
         3612  +      res = 0;
  3611   3613         rc = sqlite3BtreePrevious(pC->pCursor, &res);
  3612   3614         if( rc!=SQLITE_OK ) goto abort_due_to_error;
  3613   3615         pC->rowidIsValid = 0;
  3614   3616       }else{
  3615   3617         /* res might be negative because the table is empty.  Check to
  3616   3618         ** see if this is the case.
  3617   3619         */
................................................................................
  4456   4458     assert( pOp->p2>0 && pOp->p2<p->nOp );
  4457   4459     if( res ){
  4458   4460       pc = pOp->p2 - 1;
  4459   4461     }
  4460   4462     break;
  4461   4463   }
  4462   4464   
  4463         -/* Opcode: Next P1 P2 * * P5
         4465  +/* Opcode: Next P1 P2 P3 * P5
  4464   4466   **
  4465   4467   ** Advance cursor P1 so that it points to the next key/data pair in its
  4466   4468   ** table or index.  If there are no more key/value pairs then fall through
  4467   4469   ** to the following instruction.  But if the cursor advance was successful,
  4468   4470   ** jump immediately to P2.
  4469   4471   **
  4470   4472   ** The P1 cursor must be for a real table, not a pseudo-table.  P1 must have
  4471   4473   ** been opened prior to this opcode or the program will segfault.
         4474  +**
         4475  +** The P3 value is a hint to the btree implementation. If P3==1, that
         4476  +** means P1 is an SQL index and that this instruction could have been
         4477  +** omitted if that index had been unique.  P3 is usually 0.  P3 is
         4478  +** always either 0 or 1.
  4472   4479   **
  4473   4480   ** P4 is always of type P4_ADVANCE. The function pointer points to
  4474   4481   ** sqlite3BtreeNext().
  4475   4482   **
  4476   4483   ** If P5 is positive and the jump is taken, then event counter
  4477   4484   ** number P5-1 in the prepared statement is incremented.
  4478   4485   **
  4479   4486   ** See also: Prev, NextIfOpen
  4480   4487   */
  4481         -/* Opcode: NextIfOpen P1 P2 * * P5
         4488  +/* Opcode: NextIfOpen P1 P2 P3 * P5
  4482   4489   **
  4483   4490   ** This opcode works just like OP_Next except that if cursor P1 is not
  4484   4491   ** open it behaves a no-op.
  4485   4492   */
  4486         -/* Opcode: Prev P1 P2 * * P5
         4493  +/* Opcode: Prev P1 P2 P3 * P5
  4487   4494   **
  4488   4495   ** Back up cursor P1 so that it points to the previous key/data pair in its
  4489   4496   ** table or index.  If there is no previous key/value pairs then fall through
  4490   4497   ** to the following instruction.  But if the cursor backup was successful,
  4491   4498   ** jump immediately to P2.
  4492   4499   **
  4493   4500   ** The P1 cursor must be for a real table, not a pseudo-table.  If P1 is
  4494   4501   ** not open then the behavior is undefined.
         4502  +**
         4503  +** The P3 value is a hint to the btree implementation. If P3==1, that
         4504  +** means P1 is an SQL index and that this instruction could have been
         4505  +** omitted if that index had been unique.  P3 is usually 0.  P3 is
         4506  +** always either 0 or 1.
  4495   4507   **
  4496   4508   ** P4 is always of type P4_ADVANCE. The function pointer points to
  4497   4509   ** sqlite3BtreePrevious().
  4498   4510   **
  4499   4511   ** If P5 is positive and the jump is taken, then event counter
  4500   4512   ** number P5-1 in the prepared statement is incremented.
  4501   4513   */
  4502         -/* Opcode: PrevIfOpen P1 P2 * * P5
         4514  +/* Opcode: PrevIfOpen P1 P2 P3 * P5
  4503   4515   **
  4504   4516   ** This opcode works just like OP_Prev except that if cursor P1 is not
  4505   4517   ** open it behaves a no-op.
  4506   4518   */
  4507   4519   case OP_SorterNext: {  /* jump */
  4508   4520     VdbeCursor *pC;
  4509   4521     int res;
................................................................................
  4517   4529     if( p->apCsr[pOp->p1]==0 ) break;
  4518   4530     /* Fall through */
  4519   4531   case OP_Prev:          /* jump */
  4520   4532   case OP_Next:          /* jump */
  4521   4533     assert( pOp->p1>=0 && pOp->p1<p->nCursor );
  4522   4534     assert( pOp->p5<ArraySize(p->aCounter) );
  4523   4535     pC = p->apCsr[pOp->p1];
         4536  +  res = pOp->p3;
  4524   4537     assert( pC!=0 );
  4525   4538     assert( pC->deferredMoveto==0 );
  4526   4539     assert( pC->pCursor );
         4540  +  assert( res==0 || (res==1 && pC->isTable==0) );
         4541  +  testcase( res==1 );
  4527   4542     assert( pOp->opcode!=OP_Next || pOp->p4.xAdvance==sqlite3BtreeNext );
  4528   4543     assert( pOp->opcode!=OP_Prev || pOp->p4.xAdvance==sqlite3BtreePrevious );
  4529   4544     assert( pOp->opcode!=OP_NextIfOpen || pOp->p4.xAdvance==sqlite3BtreeNext );
  4530   4545     assert( pOp->opcode!=OP_PrevIfOpen || pOp->p4.xAdvance==sqlite3BtreePrevious);
  4531   4546     rc = pOp->p4.xAdvance(pC->pCursor, &res);
  4532   4547   next_tail:
  4533   4548     pC->cacheStatus = CACHE_STALE;

Changes to src/where.c.

  3180   3180         pLevel->op = OP_Noop;
  3181   3181       }else if( bRev ){
  3182   3182         pLevel->op = OP_Prev;
  3183   3183       }else{
  3184   3184         pLevel->op = OP_Next;
  3185   3185       }
  3186   3186       pLevel->p1 = iIdxCur;
         3187  +    assert( (WHERE_UNQ_WANTED>>16)==1 );
         3188  +    pLevel->p3 = (pLoop->wsFlags>>16)&1;
  3187   3189       if( (pLoop->wsFlags & WHERE_CONSTRAINT)==0 ){
  3188   3190         pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
  3189   3191       }else{
  3190   3192         assert( pLevel->p5==0 );
  3191   3193       }
  3192   3194     }else
  3193   3195   
................................................................................
  3982   3984         pNew->nOut = nRowEst + nInMul + nIn;
  3983   3985       }else if( pTerm->eOperator & (WO_EQ) ){
  3984   3986         assert(
  3985   3987           (pNew->wsFlags & (WHERE_COLUMN_NULL|WHERE_COLUMN_IN|WHERE_SKIPSCAN))!=0
  3986   3988           || nInMul==0
  3987   3989         );
  3988   3990         pNew->wsFlags |= WHERE_COLUMN_EQ;
  3989         -      if( iCol<0  
  3990         -       || (pProbe->onError!=OE_None && nInMul==0
  3991         -           && pNew->u.btree.nEq==pProbe->nKeyCol-1)
  3992         -      ){
         3991  +      if( iCol<0 || (nInMul==0 && pNew->u.btree.nEq==pProbe->nKeyCol-1)){
  3993   3992           assert( (pNew->wsFlags & WHERE_COLUMN_IN)==0 || iCol<0 );
  3994         -        pNew->wsFlags |= WHERE_ONEROW;
         3993  +        if( iCol>=0 && pProbe->onError==OE_None ){
         3994  +          pNew->wsFlags |= WHERE_UNQ_WANTED;
         3995  +        }else{
         3996  +          pNew->wsFlags |= WHERE_ONEROW;
         3997  +        }
  3995   3998         }
  3996   3999         pNew->u.btree.nEq++;
  3997   4000         pNew->nOut = nRowEst + nInMul;
  3998   4001       }else if( pTerm->eOperator & (WO_ISNULL) ){
  3999   4002         pNew->wsFlags |= WHERE_COLUMN_NULL;
  4000   4003         pNew->u.btree.nEq++;
  4001   4004         /* TUNING: IS NULL selects 2 rows */
................................................................................
  5781   5784     sqlite3ExprCacheClear(pParse);
  5782   5785     for(i=pWInfo->nLevel-1; i>=0; i--){
  5783   5786       int addr;
  5784   5787       pLevel = &pWInfo->a[i];
  5785   5788       pLoop = pLevel->pWLoop;
  5786   5789       sqlite3VdbeResolveLabel(v, pLevel->addrCont);
  5787   5790       if( pLevel->op!=OP_Noop ){
  5788         -      sqlite3VdbeAddOp2(v, pLevel->op, pLevel->p1, pLevel->p2);
         5791  +      sqlite3VdbeAddOp3(v, pLevel->op, pLevel->p1, pLevel->p2, pLevel->p3);
  5789   5792         sqlite3VdbeChangeP5(v, pLevel->p5);
  5790   5793       }
  5791   5794       if( pLoop->wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){
  5792   5795         struct InLoop *pIn;
  5793   5796         int j;
  5794   5797         sqlite3VdbeResolveLabel(v, pLevel->addrNxt);
  5795   5798         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*/