/ Check-in [95b1f9bf]
Login
☰Home Timeline Branches

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Simplified implementation of indexing with the IS operator.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | index-is-operator
Files: files | file ages | folders
SHA1: 95b1f9bf14e490c6c6bba9ea78aeab712a44aab5
User & Date: drh 2015-05-13 19:33:41
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: 4541688b user: drh tags: index-is-operator)
2015-05-13
19:33
Simplified implementation of indexing with the IS operator. (check-in: 95b1f9bf user: drh tags: index-is-operator)
17:54
Add testcase() macros and comments and a few test-cases. (check-in: 24263d08 user: drh tags: index-is-operator)
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c. 

1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
....
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
....
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
....
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
....
2979
2980
2981
2982
2983
2984
2985
2986
2987
2988
2989
2990
2991
2992
2993
2994
2995
2996
....
3631
3632
3633
3634
3635
3636
3637
3638
3639
3640
3641
3642
3643
3644
3645
3646
....
3678
3679
3680
3681
3682
3683
3684
3685
3686
3687
3688
3689
3690
3691
3692
3693

    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);
................................................................................
        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;
      testcase( pTerm->pExpr->op==TK_IS );
      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);
      testcase( pRangeStart->pExpr->op==TK_IS );
      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);
      testcase( pRangeEnd->pExpr->op==TK_IS );
      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)








|







 







|







 







|
<







 







|







 







<
<
|
<







 







<
|







 







<
|








1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
....
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
....
1471
1472
1473
1474
1475
1476
1477
1478

1479
1480
1481
1482
1483
1484
1485
....
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
....
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

    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);
................................................................................
        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;
................................................................................

#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;
................................................................................
    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);
................................................................................
        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;
        }
................................................................................

    /* 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)

Changes to src/whereInt.h. 

276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
...
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440

#  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 */
................................................................................
/*
** 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
#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 */








|







 







|








276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
...
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440

#  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 */
................................................................................
/*
** 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
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}

} {
  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








>









55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

  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]
}


finish_test

This page was generated in about 0.026s by Fossil 2.14 [4740cf7589] 2020-11-29 19:33:14