Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Simplified implementation of indexing with the IS operator. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | index-is-operator |
Files: | files | file ages | folders |
SHA1: |
95b1f9bf14e490c6c6bba9ea78aeab71 |
User & Date: | drh 2015-05-13 19:33:41.990 |
Context
2015-05-14
| ||
01:05 | A new implementation of indexing with the IS operator that works correctly when the IS operator is in the WHERE clause and the operands are from opposite sides of a LEFT JOIN. (check-in: 4541688b3f user: drh tags: index-is-operator) | |
2015-05-13
| ||
19:33 | Simplified implementation of indexing with the IS operator. (check-in: 95b1f9bf14 user: drh tags: index-is-operator) | |
17:54 | Add testcase() macros and comments and a few test-cases. (check-in: 24263d08b1 user: drh tags: index-is-operator) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
1255 1256 1257 1258 1259 1260 1261 | 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; } | | | 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 | 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_IS; 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); |
︙ | ︙ | |||
1280 1281 1282 1283 1284 1285 1286 | if( pExpr->op==TK_EQ && !ExprHasProperty(pExpr, EP_FromJoin) && OptimizationEnabled(db, SQLITE_Transitive) ){ pTerm->eOperator |= WO_EQUIV; eExtraOp = WO_EQUIV; } | | | 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 | 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_IS; }else{ pDup = pExpr; pNew = pTerm; } exprCommute(pParse, pDup); pLeft = sqlite3ExprSkipCollate(pDup->pLeft); pNew->leftCursor = pLeft->iTable; |
︙ | ︙ | |||
1471 1472 1473 1474 1475 1476 1477 | #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. ** | | < | | 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 | #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. */ if( pExpr->op==TK_NOTNULL && pExpr->pLeft->op==TK_COLUMN && pExpr->pLeft->iColumn>=0 && OptimizationEnabled(db, SQLITE_Stat34) ){ Expr *pNewExpr; Expr *pLeft = pExpr->pLeft; int idxNew; 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); |
︙ | ︙ | |||
2979 2980 2981 2982 2983 2984 2985 | 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; | < | < < | 2978 2979 2980 2981 2982 2983 2984 2985 2986 2987 2988 2989 2990 2991 2992 | 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_IS)==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; } |
︙ | ︙ | |||
3631 3632 3633 3634 3635 3636 3637 | /* 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); | < | | 3627 3628 3629 3630 3631 3632 3633 3634 3635 3636 3637 3638 3639 3640 3641 | /* 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){ |
︙ | ︙ | |||
3678 3679 3680 3681 3682 3683 3684 | */ nConstraint = nEq; if( pRangeEnd ){ Expr *pRight = pRangeEnd->pExpr->pRight; sqlite3ExprCacheRemove(pParse, regBase+nEq, 1); sqlite3ExprCode(pParse, pRight, regBase+nEq); whereLikeOptimizationStringFixup(v, pLevel, pRangeEnd); | < | | 3673 3674 3675 3676 3677 3678 3679 3680 3681 3682 3683 3684 3685 3686 3687 | */ 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) |
︙ | ︙ |
Changes to src/whereInt.h.
︙ | ︙ | |||
276 277 278 279 280 281 282 | # 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 */ | | | 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_IS 0x800 /* Term.pExpr is an IS 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 */ |
︙ | ︙ | |||
426 427 428 429 430 431 432 | /* ** Bitmasks for the operators on WhereTerm objects. These are all ** operators that are of interest to the query planner. An ** OR-ed combination of these values can be used when searching for ** particular WhereTerms within a WhereClause. */ #define WO_IN 0x001 | | | 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 | /* ** Bitmasks for the operators on WhereTerm objects. These are all ** operators that are of interest to the query planner. An ** OR-ed combination of these values can be used when searching for ** particular WhereTerms within a WhereClause. */ #define WO_IN 0x001 #define WO_EQ 0x002 /* Used for both == and IS */ #define WO_LT (WO_EQ<<(TK_LT-TK_EQ)) #define WO_LE (WO_EQ<<(TK_LE-TK_EQ)) #define WO_GT (WO_EQ<<(TK_GT-TK_EQ)) #define WO_GE (WO_EQ<<(TK_GE-TK_EQ)) #define WO_MATCH 0x040 #define WO_ISNULL 0x080 #define WO_OR 0x100 /* Two or more OR-connected terms */ |
︙ | ︙ |
Changes to test/whereC.test.
︙ | ︙ | |||
55 56 57 58 59 60 61 62 63 64 65 66 67 68 | 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] } | > | 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | 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} 15 "SELECT i FROM t1 WHERE rowid IS '12'" {12} } { 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] } |
︙ | ︙ |