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: |
3b58f5f06648205a47e5cace0201269c |
| 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
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 +