/ Check-in [c4cb9048]
Login

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

Overview
Comment:When multiple constraints need to be evaluated for a row, do any constraints that involve correlated subqueries last. Hence, the priority is index-covered constraints first, correlated subquery constraints last, and all others in the middle. This is a follow-on and improvement to the push-down optimization of check-in [d7bb79ed].
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256:c4cb90487f34937605732c3959891075e2aabfb0bd05e55c44565d65867093ea
User & Date: drh 2017-07-10 17:00:31
Context
2017-07-10
18:04
Add the "--newlines" option to the ".dump" command in the shell to disable the newline escaping mechanism. check-in: bde431b1 user: drh tags: trunk
17:00
When multiple constraints need to be evaluated for a row, do any constraints that involve correlated subqueries last. Hence, the priority is index-covered constraints first, correlated subquery constraints last, and all others in the middle. This is a follow-on and improvement to the push-down optimization of check-in [d7bb79ed]. check-in: c4cb9048 user: drh tags: trunk
16:38
Additional debugging Noop-comment in the constraint generator when wheretrace is enabled. Closed-Leaf check-in: 0ca7474f user: drh tags: defer-where-subqueries
13:24
For sqlite3TreeView() debugging output, show the Expr.flags field on scalar subqueries. check-in: dc857a96 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/whereInt.h.

280
281
282
283
284
285
286

287
288
289
290
291
292
293
...
369
370
371
372
373
374
375

376
377
378
379
380
381
382
#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 */
................................................................................
** above, the mapping might go like this:  4->3, 5->1, 8->2, 29->0,
** 57->5, 73->4.  Or one of 719 other combinations might be used. It
** does not really matter.  What is important is that sparse cursor
** numbers all get mapped into bit numbers that begin with 0 and contain
** no gaps.
*/
struct WhereMaskSet {

  int n;                        /* Number of assigned cursor values */
  int ix[BMS];                  /* Cursor assigned to each bit */
};

/*
** Initialize a WhereMaskSet object
*/







>







 







>







280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
...
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
#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 */
#define TERM_VARSELECT  0x1000 /* Term.pExpr contains a correlated sub-query */

/*
** 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 */
................................................................................
** above, the mapping might go like this:  4->3, 5->1, 8->2, 29->0,
** 57->5, 73->4.  Or one of 719 other combinations might be used. It
** does not really matter.  What is important is that sparse cursor
** numbers all get mapped into bit numbers that begin with 0 and contain
** no gaps.
*/
struct WhereMaskSet {
  int bVarSelect;               /* Used by sqlite3WhereExprUsage() */
  int n;                        /* Number of assigned cursor values */
  int ix[BMS];                  /* Cursor assigned to each bit */
};

/*
** Initialize a WhereMaskSet object
*/

Changes to src/wherecode.c.

1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
....
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031






2032

2033
2034

2035
2036
2037
2038
2039
2040
2041
....
2045
2046
2047
2048
2049
2050
2051

2052
2053

2054
2055





2056
2057
2058
2059
2060
2061
2062
....
2064
2065
2066
2067
2068
2069
2070






2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
  struct SrcList_item *pTabItem;  /* FROM clause term being coded */
  int addrBrk;                    /* Jump here to break out of the loop */
  int addrHalt;                   /* addrBrk for the outermost loop */
  int addrCont;                   /* Jump here to continue with next cycle */
  int iRowidReg = 0;        /* Rowid is stored in this register, if not zero */
  int iReleaseReg = 0;      /* Temp register to free before returning */
  Index *pIdx = 0;          /* Index used by loop (if any) */
  int loopAgain;            /* True if constraint generator loop should repeat */

  pParse = pWInfo->pParse;
  v = pParse->pVdbe;
  pWC = &pWInfo->sWC;
  db = pParse->db;
  pLevel = &pWInfo->a[iLevel];
  pLoop = pLevel->pWLoop;
................................................................................
#ifdef SQLITE_ENABLE_STMT_SCANSTATUS
  pLevel->addrVisit = sqlite3VdbeCurrentAddr(v);
#endif

  /* Insert code to test every subexpression that can be completely
  ** computed using the current set of tables.
  **
  ** This loop may run either once (pIdx==0) or twice (pIdx!=0). If
  ** it is run twice, then the first iteration codes those sub-expressions
  ** that can be computed using columns from pIdx only (without seeking
  ** the main table cursor). 






  */

  do{
    loopAgain = 0;

    for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){
      Expr *pE;
      int skipLikeAddr = 0;
      testcase( pTerm->wtFlags & TERM_VIRTUAL );
      testcase( pTerm->wtFlags & TERM_CODED );
      if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
      if( (pTerm->prereqAll & pLevel->notReady)!=0 ){
................................................................................
        continue;
      }
      pE = pTerm->pExpr;
      assert( pE!=0 );
      if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){
        continue;
      }

      if( pIdx && !sqlite3ExprCoveredByIndex(pE, pLevel->iTabCur, pIdx) ){
        loopAgain = 1;

        continue;
      }





      if( pTerm->wtFlags & TERM_LIKECOND ){
        /* If the TERM_LIKECOND flag is set, that means that the range search
        ** is sufficient to guarantee that the LIKE operator is true, so we
        ** can skip the call to the like(A,B) function.  But this only works
        ** for strings.  So do not skip the call to the function on the pass
        ** that compares BLOBs. */
#ifdef SQLITE_LIKE_DOESNT_MATCH_BLOBS
................................................................................
#else
        u32 x = pLevel->iLikeRepCntr;
        assert( x>0 );
        skipLikeAddr = sqlite3VdbeAddOp1(v, (x&1)?OP_IfNot:OP_If, (int)(x>>1));
        VdbeCoverage(v);
#endif
      }






      sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL);
      if( skipLikeAddr ) sqlite3VdbeJumpHere(v, skipLikeAddr);
      pTerm->wtFlags |= TERM_CODED;
    }
    pIdx = 0;
  }while( loopAgain );

  /* Insert code to test for implied constraints based on transitivity
  ** of the "==" operator.
  **
  ** Example: If the WHERE clause contains "t1.a=t2.b" and "t2.b=123"
  ** and we are coding the t1 loop and the t2 loop has not yet coded,
  ** then we cannot use the "t1.a=t2.b" constraint, but we can code







|







 







|
|
|
|
>
>
>
>
>
>

>

<
>







 







>
|
<
>


>
>
>
>
>







 







>
>
>
>
>
>




|
|







1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
....
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040

2041
2042
2043
2044
2045
2046
2047
2048
....
2052
2053
2054
2055
2056
2057
2058
2059
2060

2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
....
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
  struct SrcList_item *pTabItem;  /* FROM clause term being coded */
  int addrBrk;                    /* Jump here to break out of the loop */
  int addrHalt;                   /* addrBrk for the outermost loop */
  int addrCont;                   /* Jump here to continue with next cycle */
  int iRowidReg = 0;        /* Rowid is stored in this register, if not zero */
  int iReleaseReg = 0;      /* Temp register to free before returning */
  Index *pIdx = 0;          /* Index used by loop (if any) */
  int iLoop;                /* Iteration of constraint generator loop */

  pParse = pWInfo->pParse;
  v = pParse->pVdbe;
  pWC = &pWInfo->sWC;
  db = pParse->db;
  pLevel = &pWInfo->a[iLevel];
  pLoop = pLevel->pWLoop;
................................................................................
#ifdef SQLITE_ENABLE_STMT_SCANSTATUS
  pLevel->addrVisit = sqlite3VdbeCurrentAddr(v);
#endif

  /* Insert code to test every subexpression that can be completely
  ** computed using the current set of tables.
  **
  ** This loop may run between one and three times, depending on the
  ** constraints to be generated. The value of stack variable iLoop
  ** determines the constraints coded by each iteration, as follows:
  **
  ** iLoop==1: Code only expressions that are entirely covered by pIdx.
  ** iLoop==2: Code remaining expressions that do not contain correlated
  **           sub-queries.  
  ** iLoop==3: Code all remaining expressions.
  **
  ** An effort is made to skip unnecessary iterations of the loop.
  */
  iLoop = (pIdx ? 1 : 2);
  do{

    int iNext = 0;                /* Next value for iLoop */
    for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){
      Expr *pE;
      int skipLikeAddr = 0;
      testcase( pTerm->wtFlags & TERM_VIRTUAL );
      testcase( pTerm->wtFlags & TERM_CODED );
      if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
      if( (pTerm->prereqAll & pLevel->notReady)!=0 ){
................................................................................
        continue;
      }
      pE = pTerm->pExpr;
      assert( pE!=0 );
      if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){
        continue;
      }
      
      if( iLoop==1 && !sqlite3ExprCoveredByIndex(pE, pLevel->iTabCur, pIdx) ){

        iNext = 2;
        continue;
      }
      if( iLoop<3 && (pTerm->wtFlags & TERM_VARSELECT) ){
        if( iNext==0 ) iNext = 3;
        continue;
      }

      if( pTerm->wtFlags & TERM_LIKECOND ){
        /* If the TERM_LIKECOND flag is set, that means that the range search
        ** is sufficient to guarantee that the LIKE operator is true, so we
        ** can skip the call to the like(A,B) function.  But this only works
        ** for strings.  So do not skip the call to the function on the pass
        ** that compares BLOBs. */
#ifdef SQLITE_LIKE_DOESNT_MATCH_BLOBS
................................................................................
#else
        u32 x = pLevel->iLikeRepCntr;
        assert( x>0 );
        skipLikeAddr = sqlite3VdbeAddOp1(v, (x&1)?OP_IfNot:OP_If, (int)(x>>1));
        VdbeCoverage(v);
#endif
      }
#ifdef WHERETRACE_ENABLED /* 0xffff */
      if( sqlite3WhereTrace ){
        VdbeNoopComment((v, "WhereTerm[%d] (%p) priority=%d",
                         pWC->nTerm-j, pTerm, iLoop));
      }
#endif
      sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL);
      if( skipLikeAddr ) sqlite3VdbeJumpHere(v, skipLikeAddr);
      pTerm->wtFlags |= TERM_CODED;
    }
    iLoop = iNext;
  }while( iLoop>0 );

  /* Insert code to test for implied constraints based on transitivity
  ** of the "==" operator.
  **
  ** Example: If the WHERE clause contains "t1.a=t2.b" and "t2.b=123"
  ** and we are coding the t1 loop and the t2 loop has not yet coded,
  ** then we cannot use the "t1.a=t2.b" constraint, but we can code

Changes to src/whereexpr.c.

947
948
949
950
951
952
953

954

955
956
957
958
959
960
961
....
1378
1379
1380
1381
1382
1383
1384
1385

1386

1387

1388
1389
1390
1391
1392
1393
1394
      pTerm->prereqRight = sqlite3WhereExprListUsage(pMaskSet, pExpr->x.pList);
    }
  }else if( op==TK_ISNULL ){
    pTerm->prereqRight = 0;
  }else{
    pTerm->prereqRight = sqlite3WhereExprUsage(pMaskSet, pExpr->pRight);
  }

  prereqAll = sqlite3WhereExprUsage(pMaskSet, pExpr);

  if( ExprHasProperty(pExpr, EP_FromJoin) ){
    Bitmask x = sqlite3WhereGetMask(pMaskSet, pExpr->iRightJoinTable);
    prereqAll |= x;
    extraRight = x-1;  /* ON clause terms may not be used with an index
                       ** on left table of a LEFT JOIN.  Ticket #3015 */
    if( (prereqAll>>1)>=x ){
      sqlite3ErrorMsg(pParse, "ON clause references tables to its right");
................................................................................
  Bitmask mask;
  if( p==0 ) return 0;
  if( p->op==TK_COLUMN ){
    return sqlite3WhereGetMask(pMaskSet, p->iTable);
  }
  mask = (p->op==TK_IF_NULL_ROW) ? sqlite3WhereGetMask(pMaskSet, p->iTable) : 0;
  assert( !ExprHasProperty(p, EP_TokenOnly) );
  if( p->pRight ) mask |= sqlite3WhereExprUsage(pMaskSet, p->pRight);

  if( p->pLeft ) mask |= sqlite3WhereExprUsage(pMaskSet, p->pLeft);

  if( ExprHasProperty(p, EP_xIsSelect) ){

    mask |= exprSelectUsage(pMaskSet, p->x.pSelect);
  }else if( p->x.pList ){
    mask |= sqlite3WhereExprListUsage(pMaskSet, p->x.pList);
  }
  return mask;
}
Bitmask sqlite3WhereExprListUsage(WhereMaskSet *pMaskSet, ExprList *pList){







>

>







 







|
>
|
>
|
>







947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
....
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
      pTerm->prereqRight = sqlite3WhereExprListUsage(pMaskSet, pExpr->x.pList);
    }
  }else if( op==TK_ISNULL ){
    pTerm->prereqRight = 0;
  }else{
    pTerm->prereqRight = sqlite3WhereExprUsage(pMaskSet, pExpr->pRight);
  }
  pMaskSet->bVarSelect = 0;
  prereqAll = sqlite3WhereExprUsage(pMaskSet, pExpr);
  if( pMaskSet->bVarSelect ) pTerm->wtFlags |= TERM_VARSELECT;
  if( ExprHasProperty(pExpr, EP_FromJoin) ){
    Bitmask x = sqlite3WhereGetMask(pMaskSet, pExpr->iRightJoinTable);
    prereqAll |= x;
    extraRight = x-1;  /* ON clause terms may not be used with an index
                       ** on left table of a LEFT JOIN.  Ticket #3015 */
    if( (prereqAll>>1)>=x ){
      sqlite3ErrorMsg(pParse, "ON clause references tables to its right");
................................................................................
  Bitmask mask;
  if( p==0 ) return 0;
  if( p->op==TK_COLUMN ){
    return sqlite3WhereGetMask(pMaskSet, p->iTable);
  }
  mask = (p->op==TK_IF_NULL_ROW) ? sqlite3WhereGetMask(pMaskSet, p->iTable) : 0;
  assert( !ExprHasProperty(p, EP_TokenOnly) );
  if( p->pLeft ) mask |= sqlite3WhereExprUsage(pMaskSet, p->pLeft);
  if( p->pRight ){
    mask |= sqlite3WhereExprUsage(pMaskSet, p->pRight);
    assert( p->x.pList==0 );
  }else if( ExprHasProperty(p, EP_xIsSelect) ){
    if( ExprHasProperty(p, EP_VarSelect) ) pMaskSet->bVarSelect = 1;
    mask |= exprSelectUsage(pMaskSet, p->x.pSelect);
  }else if( p->x.pList ){
    mask |= sqlite3WhereExprListUsage(pMaskSet, p->x.pList);
  }
  return mask;
}
Bitmask sqlite3WhereExprListUsage(WhereMaskSet *pMaskSet, ExprList *pList){

Changes to test/pushdown.test.

51
52
53
54
55
56
57
58

































59
} {b2}

do_test 1.5 {
  set L [list]
  execsql { SELECT * FROM t1 WHERE a=3 AND f(c) AND f(b) }
  set L
} {b3}
  

































finish_test







|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
} {b2}

do_test 1.5 {
  set L [list]
  execsql { SELECT * FROM t1 WHERE a=3 AND f(c) AND f(b) }
  set L
} {b3}

#-----------------------------------------------

do_execsql_test 2.0 {
  CREATE TABLE u1(a, b, c);
  CREATE TABLE u2(x, y, z);

  INSERT INTO u1 VALUES('a1', 'b1', 'c1');
  INSERT INTO u2 VALUES('a1', 'b1', 'c1');
}

do_test 2.1 {
  set L [list]
  execsql {
    SELECT * FROM u1 WHERE f('one')=123 AND 123=(
      SELECT x FROM u2 WHERE x=a AND f('two')
    )
  }
  set L
} {one}

do_test 2.2 {
  set L [list]
  breakpoint
  execsql {
    SELECT * FROM u1 WHERE 123=(
      SELECT x FROM u2 WHERE x=a AND f('two')
    ) AND f('three')=123
  }
  set L
} {three}


  
finish_test