/ Check-in [3b58f5f0]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Where possible, take advantage of the rowid at the end of index records to optimize range constraints (<, >, <=, >=) on the rowid column.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 3b58f5f06648205a47e5cace0201269c406e476a
User & Date: dan 2011-11-16 15:27:09
References
2011-11-16
15:41
Fix an invalid assert() statement added by [3b58f5f066]. check-in: 888b09dd user: dan tags: trunk
Context
2011-11-16
15:41
Fix an invalid assert() statement added by [3b58f5f066]. check-in: 888b09dd user: dan tags: trunk
15:27
Where possible, take advantage of the rowid at the end of index records to optimize range constraints (<, >, <=, >=) on the rowid column. check-in: 3b58f5f0 user: dan tags: trunk
08:18
Update memsubsys1.test to account for the recently increased size of the MemPage structure in btreeInt.h. check-in: 4fb3ca75 user: dan tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/insert.c.

    43     43   **  ------------------------------
    44     44   **  'a'            TEXT
    45     45   **  'b'            NONE
    46     46   **  'c'            NUMERIC
    47     47   **  'd'            INTEGER
    48     48   **  'e'            REAL
    49     49   **
    50         -** An extra 'b' is appended to the end of the string to cover the
           50  +** An extra 'd' is appended to the end of the string to cover the
    51     51   ** rowid that appears as the last column in every index.
    52     52   **
    53     53   ** Memory for the buffer containing the column index affinity string
    54     54   ** is managed along with the rest of the Index structure. It will be
    55     55   ** released when sqlite3DeleteIndex() is called.
    56     56   */
    57     57   const char *sqlite3IndexAffinityStr(Vdbe *v, Index *pIdx){
................................................................................
    71     71       if( !pIdx->zColAff ){
    72     72         db->mallocFailed = 1;
    73     73         return 0;
    74     74       }
    75     75       for(n=0; n<pIdx->nColumn; n++){
    76     76         pIdx->zColAff[n] = pTab->aCol[pIdx->aiColumn[n]].affinity;
    77     77       }
    78         -    pIdx->zColAff[n++] = SQLITE_AFF_NONE;
           78  +    pIdx->zColAff[n++] = SQLITE_AFF_INTEGER;
    79     79       pIdx->zColAff[n] = 0;
    80     80     }
    81     81    
    82     82     return pIdx->zColAff;
    83     83   }
    84     84   
    85     85   /*

Changes to src/vdbe.c.

  4612   4612     if( ALWAYS(pC->pCursor!=0) ){
  4613   4613       assert( pC->deferredMoveto==0 );
  4614   4614       assert( pOp->p5==0 || pOp->p5==1 );
  4615   4615       assert( pOp->p4type==P4_INT32 );
  4616   4616       r.pKeyInfo = pC->pKeyInfo;
  4617   4617       r.nField = (u16)pOp->p4.i;
  4618   4618       if( pOp->p5 ){
  4619         -      r.flags = UNPACKED_INCRKEY | UNPACKED_IGNORE_ROWID;
         4619  +      r.flags = UNPACKED_INCRKEY | UNPACKED_PREFIX_MATCH;
  4620   4620       }else{
  4621         -      r.flags = UNPACKED_IGNORE_ROWID;
         4621  +      r.flags = UNPACKED_PREFIX_MATCH;
  4622   4622       }
  4623   4623       r.aMem = &aMem[pOp->p3];
  4624   4624   #ifdef SQLITE_DEBUG
  4625   4625       { int i; for(i=0; i<r.nField; i++) assert( memIsValid(&r.aMem[i]) ); }
  4626   4626   #endif
  4627   4627       rc = sqlite3VdbeIdxKeyCompare(pC, &r, &res);
  4628   4628       if( pOp->opcode==OP_IdxLT ){

Changes to src/vdbeaux.c.

  3162   3162       return SQLITE_CORRUPT_BKPT;
  3163   3163     }
  3164   3164     memset(&m, 0, sizeof(m));
  3165   3165     rc = sqlite3VdbeMemFromBtree(pC->pCursor, 0, (int)nCellKey, 1, &m);
  3166   3166     if( rc ){
  3167   3167       return rc;
  3168   3168     }
  3169         -  assert( pUnpacked->flags & UNPACKED_IGNORE_ROWID );
         3169  +  assert( pUnpacked->flags & UNPACKED_PREFIX_SEARCH );
  3170   3170     *res = sqlite3VdbeRecordCompare(m.n, m.z, pUnpacked);
  3171   3171     sqlite3VdbeMemRelease(&m);
  3172   3172     return SQLITE_OK;
  3173   3173   }
  3174   3174   
  3175   3175   /*
  3176   3176   ** This routine sets the value to be returned by subsequent calls to

Changes to src/where.c.

   600    600     for(; pWC; pWC=pWC->pOuter){
   601    601       for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
   602    602         if( pTerm->leftCursor==iCur
   603    603            && (pTerm->prereqRight & notReady)==0
   604    604            && pTerm->u.leftColumn==iColumn
   605    605            && (pTerm->eOperator & op)!=0
   606    606         ){
   607         -        if( pIdx && pTerm->eOperator!=WO_ISNULL ){
          607  +        if( iColumn>=0 && pIdx && pTerm->eOperator!=WO_ISNULL ){
   608    608             Expr *pX = pTerm->pExpr;
   609    609             CollSeq *pColl;
   610    610             char idxaff;
   611    611             int j;
   612    612             Parse *pParse = pWC->pParse;
   613    613     
   614    614             idxaff = pIdx->pTable->aCol[iColumn].affinity;
................................................................................
  3048   3048           wsFlags |= WHERE_COLUMN_NULL;
  3049   3049         }
  3050   3050   #ifdef SQLITE_ENABLE_STAT3
  3051   3051         if( nEq==0 && pProbe->aSample ) pFirstTerm = pTerm;
  3052   3052   #endif
  3053   3053         used |= pTerm->prereqRight;
  3054   3054       }
  3055         -
  3056         -    /* Determine the value of rangeDiv */
  3057         -    if( nEq<pProbe->nColumn && pProbe->bUnordered==0 ){
  3058         -      int j = pProbe->aiColumn[nEq];
         3055  + 
         3056  +    /* If the index being considered is UNIQUE, and there is an equality 
         3057  +    ** constraint for all columns in the index, then this search will find
         3058  +    ** at most a single row. In this case set the WHERE_UNIQUE flag to 
         3059  +    ** indicate this to the caller.
         3060  +    **
         3061  +    ** Otherwise, if the search may find more than one row, test to see if
         3062  +    ** there is a range constraint on indexed column (nEq+1) that can be 
         3063  +    ** optimized using the index. 
         3064  +    */
         3065  +    if( nEq==pProbe->nColumn && pProbe->onError!=OE_None ){
         3066  +      testcase( wsFlags & WHERE_COLUMN_IN );
         3067  +      testcase( wsFlags & WHERE_COLUMN_NULL );
         3068  +      if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){
         3069  +        wsFlags |= WHERE_UNIQUE;
         3070  +      }
         3071  +    }else if( pProbe->bUnordered==0 ){
         3072  +      int j = (nEq==pProbe->nColumn ? -1 : pProbe->aiColumn[nEq]);
  3059   3073         if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){
  3060   3074           WhereTerm *pTop = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pIdx);
  3061   3075           WhereTerm *pBtm = findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pIdx);
  3062   3076           whereRangeScanEst(pParse, pProbe, nEq, pBtm, pTop, &rangeDiv);
  3063   3077           if( pTop ){
  3064   3078             nBound = 1;
  3065   3079             wsFlags |= WHERE_TOP_LIMIT;
................................................................................
  3070   3084             nBound++;
  3071   3085             wsFlags |= WHERE_BTM_LIMIT;
  3072   3086             used |= pBtm->prereqRight;
  3073   3087             testcase( pBtm->pWC!=pWC );
  3074   3088           }
  3075   3089           wsFlags |= (WHERE_COLUMN_RANGE|WHERE_ROWID_RANGE);
  3076   3090         }
  3077         -    }else if( pProbe->onError!=OE_None ){
  3078         -      testcase( wsFlags & WHERE_COLUMN_IN );
  3079         -      testcase( wsFlags & WHERE_COLUMN_NULL );
  3080         -      if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){
  3081         -        wsFlags |= WHERE_UNIQUE;
  3082         -      }
  3083   3091       }
  3084   3092   
  3085   3093       /* If there is an ORDER BY clause and the index being considered will
  3086   3094       ** naturally scan rows in the required order, set the appropriate flags
  3087   3095       ** in wsFlags. Otherwise, if there is an ORDER BY clause but the index
  3088   3096       ** will scan rows in a different order, set the bSort variable.  */
  3089   3097       if( isSortingIndex(
................................................................................
  3686   3694     sqlite3StrAccumAppend(&txt, " (", 2);
  3687   3695     for(i=0; i<nEq; i++){
  3688   3696       explainAppendTerm(&txt, i, aCol[aiColumn[i]].zName, "=");
  3689   3697     }
  3690   3698   
  3691   3699     j = i;
  3692   3700     if( pPlan->wsFlags&WHERE_BTM_LIMIT ){
  3693         -    explainAppendTerm(&txt, i++, aCol[aiColumn[j]].zName, ">");
         3701  +    char *z = (j==pIndex->nColumn ) ? "rowid" : aCol[aiColumn[j]].zName;
         3702  +    explainAppendTerm(&txt, i++, z, ">");
  3694   3703     }
  3695   3704     if( pPlan->wsFlags&WHERE_TOP_LIMIT ){
  3696         -    explainAppendTerm(&txt, i, aCol[aiColumn[j]].zName, "<");
         3705  +    char *z = (j==pIndex->nColumn ) ? "rowid" : aCol[aiColumn[j]].zName;
         3706  +    explainAppendTerm(&txt, i, z, "<");
  3697   3707     }
  3698   3708     sqlite3StrAccumAppend(&txt, ")", 1);
  3699   3709     return sqlite3StrAccumFinish(&txt);
  3700   3710   }
  3701   3711   
  3702   3712   /*
  3703   3713   ** This function is a no-op unless currently processing an EXPLAIN QUERY PLAN
................................................................................
  4047   4057       int nExtraReg = 0;           /* Number of extra registers needed */
  4048   4058       int op;                      /* Instruction opcode */
  4049   4059       char *zStartAff;             /* Affinity for start of range constraint */
  4050   4060       char *zEndAff;               /* Affinity for end of range constraint */
  4051   4061   
  4052   4062       pIdx = pLevel->plan.u.pIdx;
  4053   4063       iIdxCur = pLevel->iIdxCur;
  4054         -    k = pIdx->aiColumn[nEq];     /* Column for inequality constraints */
         4064  +    k = (nEq==pIdx->nColumn ? -1 : pIdx->aiColumn[nEq]);
  4055   4065   
  4056   4066       /* If this loop satisfies a sort order (pOrderBy) request that 
  4057   4067       ** was passed to this function to implement a "SELECT min(x) ..." 
  4058   4068       ** query, then the caller will only allow the loop to run for
  4059   4069       ** a single iteration. This means that the first row returned
  4060   4070       ** should not have a NULL value stored in 'x'. If column 'x' is
  4061   4071       ** the first one after the nEq equality constraints in the index,
................................................................................
  4093   4103       zEndAff = sqlite3DbStrDup(pParse->db, zStartAff);
  4094   4104       addrNxt = pLevel->addrNxt;
  4095   4105   
  4096   4106       /* If we are doing a reverse order scan on an ascending index, or
  4097   4107       ** a forward order scan on a descending index, interchange the 
  4098   4108       ** start and end terms (pRangeStart and pRangeEnd).
  4099   4109       */
  4100         -    if( nEq<pIdx->nColumn && bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC) ){
         4110  +    if( (nEq<pIdx->nColumn && bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC))
         4111  +     || (bRev && pIdx->nColumn==nEq)
         4112  +    ){
  4101   4113         SWAP(WhereTerm *, pRangeEnd, pRangeStart);
  4102   4114       }
  4103   4115   
  4104   4116       testcase( pRangeStart && pRangeStart->eOperator & WO_LE );
  4105   4117       testcase( pRangeStart && pRangeStart->eOperator & WO_GE );
  4106   4118       testcase( pRangeEnd && pRangeEnd->eOperator & WO_LE );
  4107   4119       testcase( pRangeEnd && pRangeEnd->eOperator & WO_GE );

Added test/whereC.test.

            1  +# 2011 November 16
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#***********************************************************************
           11  +#
           12  +
           13  +set testdir [file dirname $argv0]
           14  +source $testdir/tester.tcl
           15  +set testprefix whereC
           16  +
           17  +do_execsql_test 1.0 {
           18  +  CREATE TABLE t1(i INTEGER PRIMARY KEY, a, b INTEGER);
           19  +
           20  +  INSERT INTO t1 VALUES(1, 1, 1);
           21  +  INSERT INTO t1 VALUES(2, 1, 1);
           22  +  INSERT INTO t1 VALUES(3, 1, 2);
           23  +  INSERT INTO t1 VALUES(4, 1, 2);
           24  +  INSERT INTO t1 VALUES(5, 1, 2);
           25  +  INSERT INTO t1 VALUES(6, 1, 3);
           26  +  INSERT INTO t1 VALUES(7, 1, 3);
           27  +
           28  +  INSERT INTO t1 VALUES(8, 2, 1);
           29  +  INSERT INTO t1 VALUES(9, 2, 1);
           30  +  INSERT INTO t1 VALUES(10, 2, 2);
           31  +  INSERT INTO t1 VALUES(11, 2, 2);
           32  +  INSERT INTO t1 VALUES(12, 2, 2);
           33  +  INSERT INTO t1 VALUES(13, 2, 3);
           34  +  INSERT INTO t1 VALUES(14, 2, 3);
           35  +
           36  +  INSERT INTO t1 VALUES(15, 2, 1);
           37  +  INSERT INTO t1 VALUES(16, 2, 1);
           38  +  INSERT INTO t1 VALUES(17, 2, 2);
           39  +  INSERT INTO t1 VALUES(18, 2, 2);
           40  +  INSERT INTO t1 VALUES(19, 2, 2);
           41  +  INSERT INTO t1 VALUES(20, 2, 3);
           42  +  INSERT INTO t1 VALUES(21, 2, 3);
           43  +
           44  +  CREATE INDEX i1 ON t1(a, b);
           45  +}
           46  +
           47  +foreach {tn sql res} {
           48  +  1   "SELECT i FROM t1 WHERE a=1 AND b=2 AND i>3"         {4 5}
           49  +  2   "SELECT i FROM t1 WHERE rowid='12'"                  {12}
           50  +  3   "SELECT i FROM t1 WHERE a=1 AND b='2'"               {3 4 5}
           51  +  4   "SELECT i FROM t1 WHERE a=1 AND b='2' AND i>'3'"     {4 5}
           52  +  5   "SELECT i FROM t1 WHERE a=1 AND b='2' AND i<5"       {3 4}
           53  +  6   "SELECT i FROM t1 WHERE a=2 AND b=2 AND i<12"        {10 11}
           54  +  7   "SELECT i FROM t1 WHERE a IN(1, 2) AND b=2 AND i<11" {3 4 5 10}
           55  +  8   "SELECT i FROM t1 WHERE a=2 AND b=2 AND i BETWEEN 10 AND 12" {10 11 12}
           56  +  9   "SELECT i FROM t1 WHERE a=2 AND b=2 AND i BETWEEN 11 AND 12" {11 12}
           57  + 10   "SELECT i FROM t1 WHERE a=2 AND b=2 AND i BETWEEN 10 AND 11" {10 11}
           58  + 11   "SELECT i FROM t1 WHERE a=2 AND b=2 AND i BETWEEN 12 AND 10" {}
           59  + 12   "SELECT i FROM t1 WHERE a=2 AND b=2 AND i<NULL"      {}
           60  + 13   "SELECT i FROM t1 WHERE a=2 AND b=2 AND i>=NULL"     {}
           61  + 14   "SELECT i FROM t1 WHERE a=1 AND b='2' AND i<4.5"     {3 4}
           62  +} {
           63  +  do_execsql_test 1.$tn.1 $sql $res
           64  +  do_execsql_test 1.$tn.2 "$sql ORDER BY i ASC"  [lsort -integer -inc  $res]
           65  +  do_execsql_test 1.$tn.3 "$sql ORDER BY i DESC" [lsort -integer -dec  $res]
           66  +}
           67  +
           68  +
           69  +finish_test
           70  +