Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | An early attempt to get indexes to work with the IS operator. This code passes tests, but much more testing is needed to verify that it works on all corner cases. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | index-is-operator |
| Files: | files | file ages | folders |
| SHA1: |
6f7f1673d00d216a5aa456acb44793a1 |
| User & Date: | drh 2015-05-13 15:24:07 |
Context
|
2015-05-13
| ||
| 17:54 | Add testcase() macros and comments and a few test-cases. (check-in: 24263d08b1 user: drh tags: index-is-operator) | |
| 15:24 | An early attempt to get indexes to work with the IS operator. This code passes tests, but much more testing is needed to verify that it works on all corner cases. (check-in: 6f7f1673d0 user: drh tags: index-is-operator) | |
| 04:50 | Enhancements to the MSVC makefile. (check-in: 59e3e9e764 user: mistachkin tags: trunk) | |
Changes
Changes to src/where.c.
359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 ... 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 .... 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 .... 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 .... 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 .... 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 .... 2788 2789 2790 2791 2792 2793 2794 2795 2796 2797 2798 2799 2800 2801 2802 .... 2973 2974 2975 2976 2977 2978 2979 2980 2981 2982 2983 2984 2985 2986 2987 .... 3622 3623 3624 3625 3626 3627 3628 3629 3630 3631 3632 3633 3634 3635 3636 .... 3668 3669 3670 3671 3672 3673 3674 3675 3676 3677 3678 3679 3680 3681 3682 .... 4154 4155 4156 4157 4158 4159 4160 4161 4162 4163 4164 4165 4166 4167 4168 4169 4170 |
** "=", "<", ">", "<=", ">=", "IN", and "IS NULL"
*/
static int allowedOp(int op){
assert( TK_GT>TK_EQ && TK_GT<TK_GE );
assert( TK_LT>TK_EQ && TK_LT<TK_GE );
assert( TK_LE>TK_EQ && TK_LE<TK_GE );
assert( TK_GE==TK_EQ+4 );
return op==TK_IN || (op>=TK_EQ && op<=TK_GE) || op==TK_ISNULL;
}
/*
** Commute a comparison operator. Expressions of the form "X op Y"
** are converted into "Y op X".
**
** If left/right precedence rules come into play when determining the
................................................................................
static u16 operatorMask(int op){
u16 c;
assert( allowedOp(op) );
if( op==TK_IN ){
c = WO_IN;
}else if( op==TK_ISNULL ){
c = WO_ISNULL;
}else{
assert( (WO_EQ<<(op-TK_EQ)) < 0x7fff );
c = (u16)(WO_EQ<<(op-TK_EQ));
}
assert( op!=TK_ISNULL || c==WO_ISNULL );
assert( op!=TK_IN || c==WO_IN );
assert( op!=TK_EQ || c==WO_EQ );
assert( op!=TK_LT || c==WO_LT );
assert( op!=TK_LE || c==WO_LE );
assert( op!=TK_GT || c==WO_GT );
assert( op!=TK_GE || c==WO_GE );
return c;
}
/*
** Advance to the next WhereTerm that matches according to the criteria
** established when the pScan object was initialized by whereScanInit().
** Return NULL if there are no more matching WhereTerms.
................................................................................
Expr *pRight = sqlite3ExprSkipCollate(pExpr->pRight);
u16 opMask = (pTerm->prereqRight & prereqLeft)==0 ? WO_ALL : WO_EQUIV;
if( pLeft->op==TK_COLUMN ){
pTerm->leftCursor = pLeft->iTable;
pTerm->u.leftColumn = pLeft->iColumn;
pTerm->eOperator = operatorMask(op) & opMask;
}
if( pRight && pRight->op==TK_COLUMN ){
WhereTerm *pNew;
Expr *pDup;
u16 eExtraOp = 0; /* Extra bits for pNew->eOperator */
if( pTerm->leftCursor>=0 ){
int idxNew;
pDup = sqlite3ExprDup(db, pExpr, 0);
................................................................................
if( pExpr->op==TK_EQ
&& !ExprHasProperty(pExpr, EP_FromJoin)
&& OptimizationEnabled(db, SQLITE_Transitive)
){
pTerm->eOperator |= WO_EQUIV;
eExtraOp = WO_EQUIV;
}
}else{
pDup = pExpr;
pNew = pTerm;
}
exprCommute(pParse, pDup);
pLeft = sqlite3ExprSkipCollate(pDup->pLeft);
pNew->leftCursor = pLeft->iTable;
................................................................................
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
/* When sqlite_stat3 histogram data is available an operator of the
** form "x IS NOT NULL" can sometimes be evaluated more efficiently
** as "x>NULL" if x is not an INTEGER PRIMARY KEY. So construct a
** virtual term of that form.
**
** Note that the virtual term must be tagged with TERM_VNULL. This
** TERM_VNULL tag will suppress the not-null check at the beginning
** of the loop. Without the TERM_VNULL flag, the not-null check at
** the start of the loop will prevent any results from being returned.
*/
if( pExpr->op==TK_NOTNULL
&& pExpr->pLeft->op==TK_COLUMN
&& pExpr->pLeft->iColumn>=0
&& OptimizationEnabled(db, SQLITE_Stat34)
){
Expr *pNewExpr;
................................................................................
WhereTerm *pNewTerm;
pNewExpr = sqlite3PExpr(pParse, TK_GT,
sqlite3ExprDup(db, pLeft, 0),
sqlite3PExpr(pParse, TK_NULL, 0, 0, 0), 0);
idxNew = whereClauseInsert(pWC, pNewExpr,
TERM_VIRTUAL|TERM_DYNAMIC|TERM_VNULL);
if( idxNew ){
pNewTerm = &pWC->a[idxNew];
pNewTerm->prereqRight = 0;
pNewTerm->leftCursor = pLeft->iTable;
pNewTerm->u.leftColumn = pLeft->iColumn;
pNewTerm->eOperator = WO_GT;
markTermAsChild(pWC, idxNew, idxTerm);
................................................................................
int iTarget /* Attempt to leave results in this register */
){
Expr *pX = pTerm->pExpr;
Vdbe *v = pParse->pVdbe;
int iReg; /* Register holding results */
assert( iTarget>0 );
if( pX->op==TK_EQ ){
iReg = sqlite3ExprCodeTarget(pParse, pX->pRight, iTarget);
}else if( pX->op==TK_ISNULL ){
iReg = iTarget;
sqlite3VdbeAddOp2(v, OP_Null, 0, iReg);
#ifndef SQLITE_OMIT_SUBQUERY
}else{
int eType;
................................................................................
sqlite3VdbeAddOp2(v, OP_SCopy, r1, regBase+j);
}
}
testcase( pTerm->eOperator & WO_ISNULL );
testcase( pTerm->eOperator & WO_IN );
if( (pTerm->eOperator & (WO_ISNULL|WO_IN))==0 ){
Expr *pRight = pTerm->pExpr->pRight;
if( sqlite3ExprCanBeNull(pRight) ){
sqlite3VdbeAddOp2(v, OP_IsNull, regBase+j, pLevel->addrBrk);
VdbeCoverage(v);
}
if( zAff ){
if( sqlite3CompareAffinity(pRight, zAff[j])==SQLITE_AFF_NONE ){
zAff[j] = SQLITE_AFF_NONE;
}
................................................................................
/* Seek the index cursor to the start of the range. */
nConstraint = nEq;
if( pRangeStart ){
Expr *pRight = pRangeStart->pExpr->pRight;
sqlite3ExprCode(pParse, pRight, regBase+nEq);
whereLikeOptimizationStringFixup(v, pLevel, pRangeStart);
if( (pRangeStart->wtFlags & TERM_VNULL)==0
&& sqlite3ExprCanBeNull(pRight)
){
sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt);
VdbeCoverage(v);
}
if( zStartAff ){
if( sqlite3CompareAffinity(pRight, zStartAff[nEq])==SQLITE_AFF_NONE){
................................................................................
*/
nConstraint = nEq;
if( pRangeEnd ){
Expr *pRight = pRangeEnd->pExpr->pRight;
sqlite3ExprCacheRemove(pParse, regBase+nEq, 1);
sqlite3ExprCode(pParse, pRight, regBase+nEq);
whereLikeOptimizationStringFixup(v, pLevel, pRangeEnd);
if( (pRangeEnd->wtFlags & TERM_VNULL)==0
&& sqlite3ExprCanBeNull(pRight)
){
sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt);
VdbeCoverage(v);
}
if( sqlite3CompareAffinity(pRight, cEndAff)!=SQLITE_AFF_NONE
&& !sqlite3ExprNeedsNoAffinityChange(pRight, cEndAff)
................................................................................
sqlite3DebugPrintf("TERM-%-3d NULL\n", iTerm);
}else{
char zType[4];
memcpy(zType, "...", 4);
if( pTerm->wtFlags & TERM_VIRTUAL ) zType[0] = 'V';
if( pTerm->eOperator & WO_EQUIV ) zType[1] = 'E';
if( ExprHasProperty(pTerm->pExpr, EP_FromJoin) ) zType[2] = 'L';
sqlite3DebugPrintf("TERM-%-3d %p %s cursor=%-3d prob=%-3d op=0x%03x\n",
iTerm, pTerm, zType, pTerm->leftCursor, pTerm->truthProb,
pTerm->eOperator);
sqlite3TreeViewExpr(0, pTerm->pExpr, 0);
}
}
#endif
#ifdef WHERETRACE_ENABLED
/*
|
| > > > > > | | < < | | > | > | | > | | | |
359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 ... 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 .... 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 .... 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 .... 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 .... 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 .... 2791 2792 2793 2794 2795 2796 2797 2798 2799 2800 2801 2802 2803 2804 2805 .... 2976 2977 2978 2979 2980 2981 2982 2983 2984 2985 2986 2987 2988 2989 2990 2991 2992 .... 3627 3628 3629 3630 3631 3632 3633 3634 3635 3636 3637 3638 3639 3640 3641 .... 3673 3674 3675 3676 3677 3678 3679 3680 3681 3682 3683 3684 3685 3686 3687 .... 4159 4160 4161 4162 4163 4164 4165 4166 4167 4168 4169 4170 4171 4172 4173 4174 4175 4176 |
** "=", "<", ">", "<=", ">=", "IN", and "IS NULL"
*/
static int allowedOp(int op){
assert( TK_GT>TK_EQ && TK_GT<TK_GE );
assert( TK_LT>TK_EQ && TK_LT<TK_GE );
assert( TK_LE>TK_EQ && TK_LE<TK_GE );
assert( TK_GE==TK_EQ+4 );
return op==TK_IN || (op>=TK_EQ && op<=TK_GE) || op==TK_ISNULL || op==TK_IS;
}
/*
** Commute a comparison operator. Expressions of the form "X op Y"
** are converted into "Y op X".
**
** If left/right precedence rules come into play when determining the
................................................................................
static u16 operatorMask(int op){
u16 c;
assert( allowedOp(op) );
if( op==TK_IN ){
c = WO_IN;
}else if( op==TK_ISNULL ){
c = WO_ISNULL;
}else if( op==TK_IS ){
c = WO_EQ;
}else{
assert( (WO_EQ<<(op-TK_EQ)) < 0x7fff );
c = (u16)(WO_EQ<<(op-TK_EQ));
}
assert( op!=TK_ISNULL || c==WO_ISNULL );
assert( op!=TK_IN || c==WO_IN );
assert( op!=TK_EQ || c==WO_EQ );
assert( op!=TK_LT || c==WO_LT );
assert( op!=TK_LE || c==WO_LE );
assert( op!=TK_GT || c==WO_GT );
assert( op!=TK_GE || c==WO_GE );
assert( op!=TK_IS || c==WO_EQ );
return c;
}
/*
** Advance to the next WhereTerm that matches according to the criteria
** established when the pScan object was initialized by whereScanInit().
** Return NULL if there are no more matching WhereTerms.
................................................................................
Expr *pRight = sqlite3ExprSkipCollate(pExpr->pRight);
u16 opMask = (pTerm->prereqRight & prereqLeft)==0 ? WO_ALL : WO_EQUIV;
if( pLeft->op==TK_COLUMN ){
pTerm->leftCursor = pLeft->iTable;
pTerm->u.leftColumn = pLeft->iColumn;
pTerm->eOperator = operatorMask(op) & opMask;
}
if( op==TK_IS ) pTerm->wtFlags |= TERM_NULLOK;
if( pRight && pRight->op==TK_COLUMN ){
WhereTerm *pNew;
Expr *pDup;
u16 eExtraOp = 0; /* Extra bits for pNew->eOperator */
if( pTerm->leftCursor>=0 ){
int idxNew;
pDup = sqlite3ExprDup(db, pExpr, 0);
................................................................................
if( pExpr->op==TK_EQ
&& !ExprHasProperty(pExpr, EP_FromJoin)
&& OptimizationEnabled(db, SQLITE_Transitive)
){
pTerm->eOperator |= WO_EQUIV;
eExtraOp = WO_EQUIV;
}
if( op==TK_IS ) pNew->wtFlags |= TERM_NULLOK;
}else{
pDup = pExpr;
pNew = pTerm;
}
exprCommute(pParse, pDup);
pLeft = sqlite3ExprSkipCollate(pDup->pLeft);
pNew->leftCursor = pLeft->iTable;
................................................................................
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
/* When sqlite_stat3 histogram data is available an operator of the
** form "x IS NOT NULL" can sometimes be evaluated more efficiently
** as "x>NULL" if x is not an INTEGER PRIMARY KEY. So construct a
** virtual term of that form.
**
** Note that the virtual term must be tagged with both TERM_VNULL
** and TERM_NULLOK.
*/
if( pExpr->op==TK_NOTNULL
&& pExpr->pLeft->op==TK_COLUMN
&& pExpr->pLeft->iColumn>=0
&& OptimizationEnabled(db, SQLITE_Stat34)
){
Expr *pNewExpr;
................................................................................
WhereTerm *pNewTerm;
pNewExpr = sqlite3PExpr(pParse, TK_GT,
sqlite3ExprDup(db, pLeft, 0),
sqlite3PExpr(pParse, TK_NULL, 0, 0, 0), 0);
idxNew = whereClauseInsert(pWC, pNewExpr,
TERM_VIRTUAL|TERM_DYNAMIC|TERM_VNULL|TERM_NULLOK);
if( idxNew ){
pNewTerm = &pWC->a[idxNew];
pNewTerm->prereqRight = 0;
pNewTerm->leftCursor = pLeft->iTable;
pNewTerm->u.leftColumn = pLeft->iColumn;
pNewTerm->eOperator = WO_GT;
markTermAsChild(pWC, idxNew, idxTerm);
................................................................................
int iTarget /* Attempt to leave results in this register */
){
Expr *pX = pTerm->pExpr;
Vdbe *v = pParse->pVdbe;
int iReg; /* Register holding results */
assert( iTarget>0 );
if( pX->op==TK_EQ || pX->op==TK_IS ){
iReg = sqlite3ExprCodeTarget(pParse, pX->pRight, iTarget);
}else if( pX->op==TK_ISNULL ){
iReg = iTarget;
sqlite3VdbeAddOp2(v, OP_Null, 0, iReg);
#ifndef SQLITE_OMIT_SUBQUERY
}else{
int eType;
................................................................................
sqlite3VdbeAddOp2(v, OP_SCopy, r1, regBase+j);
}
}
testcase( pTerm->eOperator & WO_ISNULL );
testcase( pTerm->eOperator & WO_IN );
if( (pTerm->eOperator & (WO_ISNULL|WO_IN))==0 ){
Expr *pRight = pTerm->pExpr->pRight;
if( (pTerm->wtFlags & TERM_NULLOK)==0
&& sqlite3ExprCanBeNull(pRight)
){
sqlite3VdbeAddOp2(v, OP_IsNull, regBase+j, pLevel->addrBrk);
VdbeCoverage(v);
}
if( zAff ){
if( sqlite3CompareAffinity(pRight, zAff[j])==SQLITE_AFF_NONE ){
zAff[j] = SQLITE_AFF_NONE;
}
................................................................................
/* Seek the index cursor to the start of the range. */
nConstraint = nEq;
if( pRangeStart ){
Expr *pRight = pRangeStart->pExpr->pRight;
sqlite3ExprCode(pParse, pRight, regBase+nEq);
whereLikeOptimizationStringFixup(v, pLevel, pRangeStart);
if( (pRangeStart->wtFlags & TERM_NULLOK)==0
&& sqlite3ExprCanBeNull(pRight)
){
sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt);
VdbeCoverage(v);
}
if( zStartAff ){
if( sqlite3CompareAffinity(pRight, zStartAff[nEq])==SQLITE_AFF_NONE){
................................................................................
*/
nConstraint = nEq;
if( pRangeEnd ){
Expr *pRight = pRangeEnd->pExpr->pRight;
sqlite3ExprCacheRemove(pParse, regBase+nEq, 1);
sqlite3ExprCode(pParse, pRight, regBase+nEq);
whereLikeOptimizationStringFixup(v, pLevel, pRangeEnd);
if( (pRangeEnd->wtFlags & TERM_NULLOK)==0
&& sqlite3ExprCanBeNull(pRight)
){
sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt);
VdbeCoverage(v);
}
if( sqlite3CompareAffinity(pRight, cEndAff)!=SQLITE_AFF_NONE
&& !sqlite3ExprNeedsNoAffinityChange(pRight, cEndAff)
................................................................................
sqlite3DebugPrintf("TERM-%-3d NULL\n", iTerm);
}else{
char zType[4];
memcpy(zType, "...", 4);
if( pTerm->wtFlags & TERM_VIRTUAL ) zType[0] = 'V';
if( pTerm->eOperator & WO_EQUIV ) zType[1] = 'E';
if( ExprHasProperty(pTerm->pExpr, EP_FromJoin) ) zType[2] = 'L';
sqlite3DebugPrintf(
"TERM-%-3d %p %s cursor=%-3d prob=%-3d op=0x%03x wtFlags=0x%04x\n",
iTerm, pTerm, zType, pTerm->leftCursor, pTerm->truthProb,
pTerm->eOperator, pTerm->wtFlags);
sqlite3TreeViewExpr(0, pTerm->pExpr, 0);
}
}
#endif
#ifdef WHERETRACE_ENABLED
/*
|
Changes to src/whereInt.h.
276 277 278 279 280 281 282 283 284 285 286 287 288 289 |
# define TERM_VNULL 0x80 /* Manufactured x>NULL or x<=NULL term */
#else
# define TERM_VNULL 0x00 /* Disabled if not using stat3 */
#endif
#define TERM_LIKEOPT 0x100 /* Virtual terms from the LIKE optimization */
#define TERM_LIKECOND 0x200 /* Conditionally this LIKE operator term */
#define TERM_LIKE 0x400 /* The original LIKE operator */
/*
** An instance of the WhereScan object is used as an iterator for locating
** terms in the WHERE clause that are useful to the query planner.
*/
struct WhereScan {
WhereClause *pOrigWC; /* Original, innermost WhereClause */
|
> |
276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 |
# define TERM_VNULL 0x80 /* Manufactured x>NULL or x<=NULL term */
#else
# define TERM_VNULL 0x00 /* Disabled if not using stat3 */
#endif
#define TERM_LIKEOPT 0x100 /* Virtual terms from the LIKE optimization */
#define TERM_LIKECOND 0x200 /* Conditionally this LIKE operator term */
#define TERM_LIKE 0x400 /* The original LIKE operator */
#define TERM_NULLOK 0x800 /* Comparison operators against NULL work */
/*
** An instance of the WhereScan object is used as an iterator for locating
** terms in the WHERE clause that are useful to the query planner.
*/
struct WhereScan {
WhereClause *pOrigWC; /* Original, innermost WhereClause */
|