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 |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
3b58f5f06648205a47e5cace0201269c |
User & Date: | dan 2011-11-16 15:27:09.116 |
References
2011-11-16
| ||
15:41 | Fix an invalid assert() statement added by [3b58f5f066]. (check-in: 888b09dd8f user: dan tags: trunk) | |
Context
2011-11-16
| ||
15:41 | Fix an invalid assert() statement added by [3b58f5f066]. (check-in: 888b09dd8f 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: 3b58f5f066 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: 4fb3ca756a user: dan tags: trunk) | |
Changes
Changes to src/insert.c.
︙ | ︙ | |||
43 44 45 46 47 48 49 | ** ------------------------------ ** 'a' TEXT ** 'b' NONE ** 'c' NUMERIC ** 'd' INTEGER ** 'e' REAL ** | | | 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | ** ------------------------------ ** 'a' TEXT ** 'b' NONE ** 'c' NUMERIC ** 'd' INTEGER ** 'e' REAL ** ** An extra 'd' is appended to the end of the string to cover the ** rowid that appears as the last column in every index. ** ** Memory for the buffer containing the column index affinity string ** is managed along with the rest of the Index structure. It will be ** released when sqlite3DeleteIndex() is called. */ const char *sqlite3IndexAffinityStr(Vdbe *v, Index *pIdx){ |
︙ | ︙ | |||
71 72 73 74 75 76 77 | if( !pIdx->zColAff ){ db->mallocFailed = 1; return 0; } for(n=0; n<pIdx->nColumn; n++){ pIdx->zColAff[n] = pTab->aCol[pIdx->aiColumn[n]].affinity; } | | | 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 | if( !pIdx->zColAff ){ db->mallocFailed = 1; return 0; } for(n=0; n<pIdx->nColumn; n++){ pIdx->zColAff[n] = pTab->aCol[pIdx->aiColumn[n]].affinity; } pIdx->zColAff[n++] = SQLITE_AFF_INTEGER; pIdx->zColAff[n] = 0; } return pIdx->zColAff; } /* |
︙ | ︙ |
Changes to src/vdbe.c.
︙ | ︙ | |||
4612 4613 4614 4615 4616 4617 4618 | if( ALWAYS(pC->pCursor!=0) ){ assert( pC->deferredMoveto==0 ); assert( pOp->p5==0 || pOp->p5==1 ); assert( pOp->p4type==P4_INT32 ); r.pKeyInfo = pC->pKeyInfo; r.nField = (u16)pOp->p4.i; if( pOp->p5 ){ | | | | 4612 4613 4614 4615 4616 4617 4618 4619 4620 4621 4622 4623 4624 4625 4626 4627 4628 | if( ALWAYS(pC->pCursor!=0) ){ assert( pC->deferredMoveto==0 ); assert( pOp->p5==0 || pOp->p5==1 ); assert( pOp->p4type==P4_INT32 ); r.pKeyInfo = pC->pKeyInfo; r.nField = (u16)pOp->p4.i; if( pOp->p5 ){ r.flags = UNPACKED_INCRKEY | UNPACKED_PREFIX_MATCH; }else{ r.flags = UNPACKED_PREFIX_MATCH; } r.aMem = &aMem[pOp->p3]; #ifdef SQLITE_DEBUG { int i; for(i=0; i<r.nField; i++) assert( memIsValid(&r.aMem[i]) ); } #endif rc = sqlite3VdbeIdxKeyCompare(pC, &r, &res); if( pOp->opcode==OP_IdxLT ){ |
︙ | ︙ |
Changes to src/vdbeaux.c.
︙ | ︙ | |||
3162 3163 3164 3165 3166 3167 3168 | return SQLITE_CORRUPT_BKPT; } memset(&m, 0, sizeof(m)); rc = sqlite3VdbeMemFromBtree(pC->pCursor, 0, (int)nCellKey, 1, &m); if( rc ){ return rc; } | | | 3162 3163 3164 3165 3166 3167 3168 3169 3170 3171 3172 3173 3174 3175 3176 | return SQLITE_CORRUPT_BKPT; } memset(&m, 0, sizeof(m)); rc = sqlite3VdbeMemFromBtree(pC->pCursor, 0, (int)nCellKey, 1, &m); if( rc ){ return rc; } assert( pUnpacked->flags & UNPACKED_PREFIX_SEARCH ); *res = sqlite3VdbeRecordCompare(m.n, m.z, pUnpacked); sqlite3VdbeMemRelease(&m); return SQLITE_OK; } /* ** This routine sets the value to be returned by subsequent calls to |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
600 601 602 603 604 605 606 | for(; pWC; pWC=pWC->pOuter){ for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){ if( pTerm->leftCursor==iCur && (pTerm->prereqRight & notReady)==0 && pTerm->u.leftColumn==iColumn && (pTerm->eOperator & op)!=0 ){ | | | 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 | for(; pWC; pWC=pWC->pOuter){ for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){ if( pTerm->leftCursor==iCur && (pTerm->prereqRight & notReady)==0 && pTerm->u.leftColumn==iColumn && (pTerm->eOperator & op)!=0 ){ if( iColumn>=0 && pIdx && pTerm->eOperator!=WO_ISNULL ){ Expr *pX = pTerm->pExpr; CollSeq *pColl; char idxaff; int j; Parse *pParse = pWC->pParse; idxaff = pIdx->pTable->aCol[iColumn].affinity; |
︙ | ︙ | |||
3048 3049 3050 3051 3052 3053 3054 | wsFlags |= WHERE_COLUMN_NULL; } #ifdef SQLITE_ENABLE_STAT3 if( nEq==0 && pProbe->aSample ) pFirstTerm = pTerm; #endif used |= pTerm->prereqRight; } | | > > > | > > > > > > > > > > > | | < < < < < < | 3048 3049 3050 3051 3052 3053 3054 3055 3056 3057 3058 3059 3060 3061 3062 3063 3064 3065 3066 3067 3068 3069 3070 3071 3072 3073 3074 3075 3076 3077 3078 3079 3080 3081 3082 3083 3084 3085 3086 3087 3088 3089 3090 3091 3092 3093 3094 3095 3096 3097 | wsFlags |= WHERE_COLUMN_NULL; } #ifdef SQLITE_ENABLE_STAT3 if( nEq==0 && pProbe->aSample ) pFirstTerm = pTerm; #endif used |= pTerm->prereqRight; } /* If the index being considered is UNIQUE, and there is an equality ** constraint for all columns in the index, then this search will find ** at most a single row. In this case set the WHERE_UNIQUE flag to ** indicate this to the caller. ** ** Otherwise, if the search may find more than one row, test to see if ** there is a range constraint on indexed column (nEq+1) that can be ** optimized using the index. */ if( nEq==pProbe->nColumn && pProbe->onError!=OE_None ){ testcase( wsFlags & WHERE_COLUMN_IN ); testcase( wsFlags & WHERE_COLUMN_NULL ); if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){ wsFlags |= WHERE_UNIQUE; } }else if( pProbe->bUnordered==0 ){ int j = (nEq==pProbe->nColumn ? -1 : pProbe->aiColumn[nEq]); if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){ WhereTerm *pTop = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pIdx); WhereTerm *pBtm = findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pIdx); whereRangeScanEst(pParse, pProbe, nEq, pBtm, pTop, &rangeDiv); if( pTop ){ nBound = 1; wsFlags |= WHERE_TOP_LIMIT; used |= pTop->prereqRight; testcase( pTop->pWC!=pWC ); } if( pBtm ){ nBound++; wsFlags |= WHERE_BTM_LIMIT; used |= pBtm->prereqRight; testcase( pBtm->pWC!=pWC ); } wsFlags |= (WHERE_COLUMN_RANGE|WHERE_ROWID_RANGE); } } /* If there is an ORDER BY clause and the index being considered will ** naturally scan rows in the required order, set the appropriate flags ** in wsFlags. Otherwise, if there is an ORDER BY clause but the index ** will scan rows in a different order, set the bSort variable. */ if( isSortingIndex( |
︙ | ︙ | |||
3686 3687 3688 3689 3690 3691 3692 | sqlite3StrAccumAppend(&txt, " (", 2); for(i=0; i<nEq; i++){ explainAppendTerm(&txt, i, aCol[aiColumn[i]].zName, "="); } j = i; if( pPlan->wsFlags&WHERE_BTM_LIMIT ){ | > | > | | 3694 3695 3696 3697 3698 3699 3700 3701 3702 3703 3704 3705 3706 3707 3708 3709 3710 3711 3712 3713 | sqlite3StrAccumAppend(&txt, " (", 2); for(i=0; i<nEq; i++){ explainAppendTerm(&txt, i, aCol[aiColumn[i]].zName, "="); } j = i; if( pPlan->wsFlags&WHERE_BTM_LIMIT ){ char *z = (j==pIndex->nColumn ) ? "rowid" : aCol[aiColumn[j]].zName; explainAppendTerm(&txt, i++, z, ">"); } if( pPlan->wsFlags&WHERE_TOP_LIMIT ){ char *z = (j==pIndex->nColumn ) ? "rowid" : aCol[aiColumn[j]].zName; explainAppendTerm(&txt, i, z, "<"); } sqlite3StrAccumAppend(&txt, ")", 1); return sqlite3StrAccumFinish(&txt); } /* ** This function is a no-op unless currently processing an EXPLAIN QUERY PLAN |
︙ | ︙ | |||
4047 4048 4049 4050 4051 4052 4053 | int nExtraReg = 0; /* Number of extra registers needed */ int op; /* Instruction opcode */ char *zStartAff; /* Affinity for start of range constraint */ char *zEndAff; /* Affinity for end of range constraint */ pIdx = pLevel->plan.u.pIdx; iIdxCur = pLevel->iIdxCur; | | | 4057 4058 4059 4060 4061 4062 4063 4064 4065 4066 4067 4068 4069 4070 4071 | int nExtraReg = 0; /* Number of extra registers needed */ int op; /* Instruction opcode */ char *zStartAff; /* Affinity for start of range constraint */ char *zEndAff; /* Affinity for end of range constraint */ pIdx = pLevel->plan.u.pIdx; iIdxCur = pLevel->iIdxCur; k = (nEq==pIdx->nColumn ? -1 : pIdx->aiColumn[nEq]); /* If this loop satisfies a sort order (pOrderBy) request that ** was passed to this function to implement a "SELECT min(x) ..." ** query, then the caller will only allow the loop to run for ** a single iteration. This means that the first row returned ** should not have a NULL value stored in 'x'. If column 'x' is ** the first one after the nEq equality constraints in the index, |
︙ | ︙ | |||
4093 4094 4095 4096 4097 4098 4099 | zEndAff = sqlite3DbStrDup(pParse->db, zStartAff); addrNxt = pLevel->addrNxt; /* If we are doing a reverse order scan on an ascending index, or ** a forward order scan on a descending index, interchange the ** start and end terms (pRangeStart and pRangeEnd). */ | | > > | 4103 4104 4105 4106 4107 4108 4109 4110 4111 4112 4113 4114 4115 4116 4117 4118 4119 | zEndAff = sqlite3DbStrDup(pParse->db, zStartAff); addrNxt = pLevel->addrNxt; /* If we are doing a reverse order scan on an ascending index, or ** a forward order scan on a descending index, interchange the ** start and end terms (pRangeStart and pRangeEnd). */ if( (nEq<pIdx->nColumn && bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC)) || (bRev && pIdx->nColumn==nEq) ){ SWAP(WhereTerm *, pRangeEnd, pRangeStart); } testcase( pRangeStart && pRangeStart->eOperator & WO_LE ); testcase( pRangeStart && pRangeStart->eOperator & WO_GE ); testcase( pRangeEnd && pRangeEnd->eOperator & WO_LE ); testcase( pRangeEnd && pRangeEnd->eOperator & WO_GE ); |
︙ | ︙ |
Added test/whereC.test.
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | # 2011 November 16 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # set testdir [file dirname $argv0] source $testdir/tester.tcl set testprefix whereC do_execsql_test 1.0 { CREATE TABLE t1(i INTEGER PRIMARY KEY, a, b INTEGER); INSERT INTO t1 VALUES(1, 1, 1); INSERT INTO t1 VALUES(2, 1, 1); INSERT INTO t1 VALUES(3, 1, 2); INSERT INTO t1 VALUES(4, 1, 2); INSERT INTO t1 VALUES(5, 1, 2); INSERT INTO t1 VALUES(6, 1, 3); INSERT INTO t1 VALUES(7, 1, 3); INSERT INTO t1 VALUES(8, 2, 1); INSERT INTO t1 VALUES(9, 2, 1); INSERT INTO t1 VALUES(10, 2, 2); INSERT INTO t1 VALUES(11, 2, 2); INSERT INTO t1 VALUES(12, 2, 2); INSERT INTO t1 VALUES(13, 2, 3); INSERT INTO t1 VALUES(14, 2, 3); INSERT INTO t1 VALUES(15, 2, 1); INSERT INTO t1 VALUES(16, 2, 1); INSERT INTO t1 VALUES(17, 2, 2); INSERT INTO t1 VALUES(18, 2, 2); INSERT INTO t1 VALUES(19, 2, 2); INSERT INTO t1 VALUES(20, 2, 3); INSERT INTO t1 VALUES(21, 2, 3); CREATE INDEX i1 ON t1(a, b); } foreach {tn sql res} { 1 "SELECT i FROM t1 WHERE a=1 AND b=2 AND i>3" {4 5} 2 "SELECT i FROM t1 WHERE rowid='12'" {12} 3 "SELECT i FROM t1 WHERE a=1 AND b='2'" {3 4 5} 4 "SELECT i FROM t1 WHERE a=1 AND b='2' AND i>'3'" {4 5} 5 "SELECT i FROM t1 WHERE a=1 AND b='2' AND i<5" {3 4} 6 "SELECT i FROM t1 WHERE a=2 AND b=2 AND i<12" {10 11} 7 "SELECT i FROM t1 WHERE a IN(1, 2) AND b=2 AND i<11" {3 4 5 10} 8 "SELECT i FROM t1 WHERE a=2 AND b=2 AND i BETWEEN 10 AND 12" {10 11 12} 9 "SELECT i FROM t1 WHERE a=2 AND b=2 AND i BETWEEN 11 AND 12" {11 12} 10 "SELECT i FROM t1 WHERE a=2 AND b=2 AND i BETWEEN 10 AND 11" {10 11} 11 "SELECT i FROM t1 WHERE a=2 AND b=2 AND i BETWEEN 12 AND 10" {} 12 "SELECT i FROM t1 WHERE a=2 AND b=2 AND i<NULL" {} 13 "SELECT i FROM t1 WHERE a=2 AND b=2 AND i>=NULL" {} 14 "SELECT i FROM t1 WHERE a=1 AND b='2' AND i<4.5" {3 4} } { do_execsql_test 1.$tn.1 $sql $res do_execsql_test 1.$tn.2 "$sql ORDER BY i ASC" [lsort -integer -inc $res] do_execsql_test 1.$tn.3 "$sql ORDER BY i DESC" [lsort -integer -dec $res] } finish_test |