Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Seek past NULLs in a top-constrained search. Avoid checking for NULLs in the body of the search. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA1: | e07a32f30862acf3b322d4d8deb01584 |
| User & Date: | drh 2014-02-14 23:49:13 |
Context
|
2014-02-17
| ||
| 01:13 | Fix the VDBE_PROFILE logic. Add a script to process the output file. check-in: 7adb3da2 user: drh tags: trunk | |
|
2014-02-16
| ||
| 01:55 | Enhance the code generator for INSERT INTO ... SELECT so that the SELECT generates output directly in the registers that INSERT INTO will be using, in many cases, and OP_SCopy operations can thus be avoided. check-in: aa2d8b0e user: drh tags: insert-optimization | |
|
2014-02-14
| ||
| 23:49 | Seek past NULLs in a top-constrained search. Avoid checking for NULLs in the body of the search. check-in: e07a32f3 user: drh tags: trunk | |
| 20:59 | Reduce the number of cases where it is necessary to check for NULL after the loop terminating condition. check-in: 3c1ae447 user: drh tags: trunk | |
Changes
Changes to src/where.c.
2981 2982 2983 2984 2985 2986 2987 2988 2989 2990 2991 2992 2993 2994 2995 2996 2997 2998 2999 3000 3001 3002 3003 3004 3005 3006 3007 3008 3009 .... 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 .... 3029 3030 3031 3032 3033 3034 3035 3036 3037 3038 3039 3040 3041 3042 .... 3048 3049 3050 3051 3052 3053 3054 3055 3056 3057 3058 3059 3060 3061 .... 3079 3080 3081 3082 3083 3084 3085 3086 3087 3088 3089 3090 3091 3092 3093 3094 3095 3096 3097 3098 3099 .... 3114 3115 3116 3117 3118 3119 3120 3121 3122 3123 3124 3125 3126 3127 3128 3129 3130 3131 3132 3133 3134 3135 3136 3137 3138 3139 3140 3141 3142 3143 3144 3145 3146 3147 3148 3149 3150 3151 3152 3153 3154 3155 3156 3157 3158 3159 |
static const u8 aEndOp[] = {
OP_IdxGE, /* 0: (end_constraints && !bRev && !endEq) */
OP_IdxGT, /* 1: (end_constraints && !bRev && endEq) */
OP_IdxLE, /* 2: (end_constraints && bRev && !endEq) */
OP_IdxLT, /* 3: (end_constraints && bRev && endEq) */
};
u16 nEq = pLoop->u.btree.nEq; /* Number of == or IN terms */
int isMinQuery = 0; /* If this is an optimized SELECT min(x).. */
int regBase; /* Base register holding constraint values */
int r1; /* Temp register */
WhereTerm *pRangeStart = 0; /* Inequality constraint at range start */
WhereTerm *pRangeEnd = 0; /* Inequality constraint at range end */
int startEq; /* True if range start uses ==, >= or <= */
int endEq; /* True if range end uses ==, >= or <= */
int start_constraints; /* Start of range is constrained */
int nConstraint; /* Number of constraint terms */
Index *pIdx; /* The index we will be using */
int iIdxCur; /* The VDBE cursor for the index */
int nExtraReg = 0; /* Number of extra registers needed */
int op; /* Instruction opcode */
char *zStartAff; /* Affinity for start of range constraint */
char cEndAff = 0; /* Affinity for end of range constraint */
pIdx = pLoop->u.btree.pIndex;
iIdxCur = pLevel->iIdxCur;
assert( nEq>=pLoop->u.btree.nSkip );
/* If this loop satisfies a sort order (pOrderBy) request that
** was passed to this function to implement a "SELECT min(x) ..."
................................................................................
** this requires some special handling.
*/
if( (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)!=0
&& (pWInfo->bOBSat!=0)
&& (pIdx->nKeyCol>nEq)
){
assert( pLoop->u.btree.nSkip==0 );
isMinQuery = 1;
nExtraReg = 1;
}
/* Find any inequality constraint terms for the start and end
** of the range.
*/
j = nEq;
................................................................................
if( pLoop->wsFlags & WHERE_BTM_LIMIT ){
pRangeStart = pLoop->aLTerm[j++];
nExtraReg = 1;
}
if( pLoop->wsFlags & WHERE_TOP_LIMIT ){
pRangeEnd = pLoop->aLTerm[j++];
nExtraReg = 1;
}
/* Generate code to evaluate all constraint terms using == or IN
** and store the values of those terms in an array of registers
** starting at regBase.
*/
regBase = codeAllEqualityTerms(pParse,pLevel,bRev,nExtraReg,&zStartAff);
................................................................................
** a forward order scan on a descending index, interchange the
** start and end terms (pRangeStart and pRangeEnd).
*/
if( (nEq<pIdx->nKeyCol && bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC))
|| (bRev && pIdx->nKeyCol==nEq)
){
SWAP(WhereTerm *, pRangeEnd, pRangeStart);
}
testcase( pRangeStart && (pRangeStart->eOperator & WO_LE)!=0 );
testcase( pRangeStart && (pRangeStart->eOperator & WO_GE)!=0 );
testcase( pRangeEnd && (pRangeEnd->eOperator & WO_LE)!=0 );
testcase( pRangeEnd && (pRangeEnd->eOperator & WO_GE)!=0 );
startEq = !pRangeStart || pRangeStart->eOperator & (WO_LE|WO_GE);
................................................................................
}
if( sqlite3ExprNeedsNoAffinityChange(pRight, zStartAff[nEq]) ){
zStartAff[nEq] = SQLITE_AFF_NONE;
}
}
nConstraint++;
testcase( pRangeStart->wtFlags & TERM_VIRTUAL );
}else if( isMinQuery ){
sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
nConstraint++;
startEq = 0;
start_constraints = 1;
}
codeApplyAffinity(pParse, regBase, nConstraint, zStartAff);
op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev];
assert( op!=0 );
testcase( op==OP_Rewind );
testcase( op==OP_Last );
testcase( op==OP_SeekGT );
testcase( op==OP_SeekGE );
testcase( op==OP_SeekLE );
................................................................................
if( sqlite3CompareAffinity(pRight, cEndAff)!=SQLITE_AFF_NONE
&& !sqlite3ExprNeedsNoAffinityChange(pRight, cEndAff)
){
codeApplyAffinity(pParse, regBase+nEq, 1, &cEndAff);
}
nConstraint++;
testcase( pRangeEnd->wtFlags & TERM_VIRTUAL );
}
sqlite3DbFree(db, zStartAff);
/* Top of the loop body */
pLevel->p2 = sqlite3VdbeCurrentAddr(v);
/* Check if the index cursor is past the end of the range. */
if( pRangeEnd || nEq ){
op = aEndOp[bRev*2 + endEq];
testcase( op==OP_IdxGT );
testcase( op==OP_IdxGE );
testcase( op==OP_IdxLT );
testcase( op==OP_IdxLE );
sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
}
/* If there are inequality constraint upper bound but not a lower
** bound, then check that the value of the table column that the
** inequality contrains is not NULL since there is alway an implied
** lower bound of "column>NULL".
*/
r1 = sqlite3GetTempReg(pParse);
if( (pLoop->wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))==WHERE_TOP_LIMIT
&& (j = pIdx->aiColumn[nEq])>=0
&& pIdx->pTable->aCol[j].notNull==0
){
sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, nEq, r1);
VdbeComment((v, "%s", pIdx->pTable->aCol[j].zName));
sqlite3VdbeAddOp2(v, OP_IsNull, r1, addrCont);
}
sqlite3ReleaseTempReg(pParse, r1);
/* Seek the table cursor, if required */
disableTerm(pLevel, pRangeStart);
disableTerm(pLevel, pRangeEnd);
if( omitTable ){
/* pIdx is a covering index. No need to access the main table. */
}else if( HasRowid(pIdx->pTable) ){
iRowidReg = iReleaseReg = sqlite3GetTempReg(pParse);
|
< < > > | > > > > > > > > | | > > > > | < < < < < < < < < < < < < < < < |
2981 2982 2983 2984 2985 2986 2987 2988 2989 2990 2991 2992 2993 2994 2995 2996 2997 2998 2999 3000 3001 3002 3003 3004 3005 3006 3007 3008 3009 .... 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 .... 3029 3030 3031 3032 3033 3034 3035 3036 3037 3038 3039 3040 3041 3042 3043 3044 3045 3046 3047 3048 3049 .... 3055 3056 3057 3058 3059 3060 3061 3062 3063 3064 3065 3066 3067 3068 3069 .... 3087 3088 3089 3090 3091 3092 3093 3094 3095 3096 3097 3098 3099 3100 3101 3102 3103 3104 3105 3106 3107 .... 3122 3123 3124 3125 3126 3127 3128 3129 3130 3131 3132 3133 3134 3135 3136 3137 3138 3139 3140 3141 3142 3143 3144 3145 3146 3147 3148 3149 3150 3151 3152 3153 3154 3155 |
static const u8 aEndOp[] = {
OP_IdxGE, /* 0: (end_constraints && !bRev && !endEq) */
OP_IdxGT, /* 1: (end_constraints && !bRev && endEq) */
OP_IdxLE, /* 2: (end_constraints && bRev && !endEq) */
OP_IdxLT, /* 3: (end_constraints && bRev && endEq) */
};
u16 nEq = pLoop->u.btree.nEq; /* Number of == or IN terms */
int regBase; /* Base register holding constraint values */
WhereTerm *pRangeStart = 0; /* Inequality constraint at range start */
WhereTerm *pRangeEnd = 0; /* Inequality constraint at range end */
int startEq; /* True if range start uses ==, >= or <= */
int endEq; /* True if range end uses ==, >= or <= */
int start_constraints; /* Start of range is constrained */
int nConstraint; /* Number of constraint terms */
Index *pIdx; /* The index we will be using */
int iIdxCur; /* The VDBE cursor for the index */
int nExtraReg = 0; /* Number of extra registers needed */
int op; /* Instruction opcode */
char *zStartAff; /* Affinity for start of range constraint */
char cEndAff = 0; /* Affinity for end of range constraint */
u8 bSeekPastNull = 0; /* True to seek past initial nulls */
u8 bStopAtNull = 0; /* Add condition to terminate at NULLs */
pIdx = pLoop->u.btree.pIndex;
iIdxCur = pLevel->iIdxCur;
assert( nEq>=pLoop->u.btree.nSkip );
/* If this loop satisfies a sort order (pOrderBy) request that
** was passed to this function to implement a "SELECT min(x) ..."
................................................................................
** this requires some special handling.
*/
if( (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)!=0
&& (pWInfo->bOBSat!=0)
&& (pIdx->nKeyCol>nEq)
){
assert( pLoop->u.btree.nSkip==0 );
bSeekPastNull = 1;
nExtraReg = 1;
}
/* Find any inequality constraint terms for the start and end
** of the range.
*/
j = nEq;
................................................................................
if( pLoop->wsFlags & WHERE_BTM_LIMIT ){
pRangeStart = pLoop->aLTerm[j++];
nExtraReg = 1;
}
if( pLoop->wsFlags & WHERE_TOP_LIMIT ){
pRangeEnd = pLoop->aLTerm[j++];
nExtraReg = 1;
if( pRangeStart==0
&& (pRangeEnd->wtFlags & TERM_VNULL)==0
&& (j = pIdx->aiColumn[nEq])>=0
&& pIdx->pTable->aCol[j].notNull==0
){
bSeekPastNull = 1;
}
}
/* Generate code to evaluate all constraint terms using == or IN
** and store the values of those terms in an array of registers
** starting at regBase.
*/
regBase = codeAllEqualityTerms(pParse,pLevel,bRev,nExtraReg,&zStartAff);
................................................................................
** a forward order scan on a descending index, interchange the
** start and end terms (pRangeStart and pRangeEnd).
*/
if( (nEq<pIdx->nKeyCol && bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC))
|| (bRev && pIdx->nKeyCol==nEq)
){
SWAP(WhereTerm *, pRangeEnd, pRangeStart);
SWAP(u8, bSeekPastNull, bStopAtNull);
}
testcase( pRangeStart && (pRangeStart->eOperator & WO_LE)!=0 );
testcase( pRangeStart && (pRangeStart->eOperator & WO_GE)!=0 );
testcase( pRangeEnd && (pRangeEnd->eOperator & WO_LE)!=0 );
testcase( pRangeEnd && (pRangeEnd->eOperator & WO_GE)!=0 );
startEq = !pRangeStart || pRangeStart->eOperator & (WO_LE|WO_GE);
................................................................................
}
if( sqlite3ExprNeedsNoAffinityChange(pRight, zStartAff[nEq]) ){
zStartAff[nEq] = SQLITE_AFF_NONE;
}
}
nConstraint++;
testcase( pRangeStart->wtFlags & TERM_VIRTUAL );
}else if( bSeekPastNull ){
sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
nConstraint++;
startEq = 0;
start_constraints = 1;
}
codeApplyAffinity(pParse, regBase, nConstraint - bSeekPastNull, zStartAff);
op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev];
assert( op!=0 );
testcase( op==OP_Rewind );
testcase( op==OP_Last );
testcase( op==OP_SeekGT );
testcase( op==OP_SeekGE );
testcase( op==OP_SeekLE );
................................................................................
if( sqlite3CompareAffinity(pRight, cEndAff)!=SQLITE_AFF_NONE
&& !sqlite3ExprNeedsNoAffinityChange(pRight, cEndAff)
){
codeApplyAffinity(pParse, regBase+nEq, 1, &cEndAff);
}
nConstraint++;
testcase( pRangeEnd->wtFlags & TERM_VIRTUAL );
}else if( bStopAtNull ){
sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
endEq = 0;
nConstraint++;
}
sqlite3DbFree(db, zStartAff);
/* Top of the loop body */
pLevel->p2 = sqlite3VdbeCurrentAddr(v);
/* Check if the index cursor is past the end of the range. */
if( nConstraint ){
op = aEndOp[bRev*2 + endEq];
testcase( op==OP_IdxGT );
testcase( op==OP_IdxGE );
testcase( op==OP_IdxLT );
testcase( op==OP_IdxLE );
sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
}
/* Seek the table cursor, if required */
disableTerm(pLevel, pRangeStart);
disableTerm(pLevel, pRangeEnd);
if( omitTable ){
/* pIdx is a covering index. No need to access the main table. */
}else if( HasRowid(pIdx->pTable) ){
iRowidReg = iReleaseReg = sqlite3GetTempReg(pParse);
|
Changes to test/where.test.
233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 |
count {SELECT w FROM t1 WHERE w==97 AND w==97}
} {97 2}
do_test where-1.34 {
count {SELECT w FROM t1 WHERE w+1==98}
} {97 99}
do_test where-1.35 {
count {SELECT w FROM t1 WHERE w<3}
} {1 2 2}
do_test where-1.36 {
count {SELECT w FROM t1 WHERE w<=3}
} {1 2 3 3}
do_test where-1.37 {
count {SELECT w FROM t1 WHERE w+1<=4 ORDER BY w}
} {1 2 3 99}
do_test where-1.38 {
count {SELECT (w) FROM t1 WHERE (w)>(97)}
} {98 99 100 3}
|
| | |
233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 |
count {SELECT w FROM t1 WHERE w==97 AND w==97}
} {97 2}
do_test where-1.34 {
count {SELECT w FROM t1 WHERE w+1==98}
} {97 99}
do_test where-1.35 {
count {SELECT w FROM t1 WHERE w<3}
} {1 2 3}
do_test where-1.36 {
count {SELECT w FROM t1 WHERE w<=3}
} {1 2 3 4}
do_test where-1.37 {
count {SELECT w FROM t1 WHERE w+1<=4 ORDER BY w}
} {1 2 3 99}
do_test where-1.38 {
count {SELECT (w) FROM t1 WHERE (w)>(97)}
} {98 99 100 3}
|
Changes to test/where4.test.
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
..
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
count {SELECT rowid FROM t1 WHERE w=1 AND +x IS NULL}
} {2 3}
do_test where4-1.5 {
count {SELECT rowid FROM t1 WHERE w=1 AND x>0}
} {1 2}
do_test where4-1.6 {
count {SELECT rowid FROM t1 WHERE w=1 AND x<9}
} {1 3}
do_test where4-1.7 {
count {SELECT rowid FROM t1 WHERE w=1 AND x IS NULL AND y=3}
} {2 2}
do_test where4-1.8 {
count {SELECT rowid FROM t1 WHERE w=1 AND x IS NULL AND y>2}
} {2 2}
do_test where4-1.9 {
................................................................................
count {SELECT rowid FROM t1 WHERE w IS NULL AND x IS NULL}
} {7 2}
do_test where4-1.14 {
count {SELECT rowid FROM t1 WHERE w IS NULL AND x IS NULL AND y IS NULL}
} {7 2}
do_test where4-1.15 {
count {SELECT rowid FROM t1 WHERE w IS NULL AND x IS NULL AND y<0}
} {2}
do_test where4-1.16 {
count {SELECT rowid FROM t1 WHERE w IS NULL AND x IS NULL AND y>=0}
} {1}
do_test where4-2.1 {
execsql {SELECT rowid FROM t1 ORDER BY w, x, y}
} {7 2 1 4 3 6 5}
|
|
|
|
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
..
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
count {SELECT rowid FROM t1 WHERE w=1 AND +x IS NULL}
} {2 3}
do_test where4-1.5 {
count {SELECT rowid FROM t1 WHERE w=1 AND x>0}
} {1 2}
do_test where4-1.6 {
count {SELECT rowid FROM t1 WHERE w=1 AND x<9}
} {1 2}
do_test where4-1.7 {
count {SELECT rowid FROM t1 WHERE w=1 AND x IS NULL AND y=3}
} {2 2}
do_test where4-1.8 {
count {SELECT rowid FROM t1 WHERE w=1 AND x IS NULL AND y>2}
} {2 2}
do_test where4-1.9 {
................................................................................
count {SELECT rowid FROM t1 WHERE w IS NULL AND x IS NULL}
} {7 2}
do_test where4-1.14 {
count {SELECT rowid FROM t1 WHERE w IS NULL AND x IS NULL AND y IS NULL}
} {7 2}
do_test where4-1.15 {
count {SELECT rowid FROM t1 WHERE w IS NULL AND x IS NULL AND y<0}
} {1}
do_test where4-1.16 {
count {SELECT rowid FROM t1 WHERE w IS NULL AND x IS NULL AND y>=0}
} {1}
do_test where4-2.1 {
execsql {SELECT rowid FROM t1 ORDER BY w, x, y}
} {7 2 1 4 3 6 5}
|
Changes to test/where8.test.
83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
do_test where8-1.8 {
# 18 searches. 9 on the index cursor and 9 on the table cursor.
execsql_status2 { SELECT c FROM t1 WHERE a > 1 AND c LIKE 'I%' }
} {II III IV IX 0 0 18}
do_test where8-1.9 {
execsql_status2 { SELECT c FROM t1 WHERE a >= 9 OR b <= 'eight' }
} {IX X VIII 0 0 6}
do_test where8-1.10 {
execsql_status2 {
SELECT c FROM t1 WHERE (a >= 9 AND c != 'X') OR b <= 'eight'
}
} {IX VIII 0 0 6}
do_test where8-1.11 {
execsql_status2 {
SELECT c FROM t1 WHERE (a >= 4 AND a <= 6) OR b = 'nine'
}
} {IV V VI IX 0 0 10}
|
| | |
83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
do_test where8-1.8 {
# 18 searches. 9 on the index cursor and 9 on the table cursor.
execsql_status2 { SELECT c FROM t1 WHERE a > 1 AND c LIKE 'I%' }
} {II III IV IX 0 0 18}
do_test where8-1.9 {
execsql_status2 { SELECT c FROM t1 WHERE a >= 9 OR b <= 'eight' }
} {IX X VIII 0 0 7}
do_test where8-1.10 {
execsql_status2 {
SELECT c FROM t1 WHERE (a >= 9 AND c != 'X') OR b <= 'eight'
}
} {IX VIII 0 0 7}
do_test where8-1.11 {
execsql_status2 {
SELECT c FROM t1 WHERE (a >= 4 AND a <= 6) OR b = 'nine'
}
} {IV V VI IX 0 0 10}
|