SQLite

Check-in [d7bb79ed]
Login

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

Overview
Comment:Evaluate WHERE clause terms that reference only the index before evaluating terms that require the table, and thereby avoid seeking the table row if index terms are false. This is called the "push-down" optimization in the MySQL world, we are told. Do not confuse with WHERE-clause push-down.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: d7bb79ed3a40419d143fbe35c310e51fe7b384a22f082a61ad788671d2d33ee0
User & Date: drh 2017-04-29 15:27:04
Original Comment: Evaluate WHERE clause terms that reference only the index before evaluating terms that require the table, and thereby avoid seeking the table row if index terms are false. This is called the "push-down" optimization in the MySQL world, we are told.
References
2017-07-10
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)
2015-06-02
18:09
For FROM-clause subqueries that cannot be flattened, try to push relevant WHERE clause terms of the outer query down into the subquery in order to help the subquery run faster and/or use less memory. Call this the "WHERE-clause push-down optimization". Do not confuse this with the completely different MySQL push-down optimization. (check-in: 6df18e94 user: drh tags: trunk)
Context
2017-04-29
20:53
Automatically transfer terms from the HAVING clause to the WHERE clause of an aggregate query in cases where the result of evaluating the term depends only one one or more of the GROUP BY expressions (and on no other inputs). (check-in: 5375a3ce user: dan tags: having-where-optimization)
18:02
Improvements to opcode documentation in the bytecode engine. No changes to code. (check-in: e54c9f8d user: drh tags: trunk)
15:27
Evaluate WHERE clause terms that reference only the index before evaluating terms that require the table, and thereby avoid seeking the table row if index terms are false. This is called the "push-down" optimization in the MySQL world, we are told. Do not confuse with WHERE-clause push-down. (check-in: d7bb79ed user: drh tags: trunk)
14:56
Minor size and performance improvements to the push-down optimization. (Closed-Leaf check-in: 91dfb61a user: drh tags: pushdown-optimization)
2017-04-26
17:21
Add new test file cachespill.test. (check-in: 2d0b6431 user: dan tags: trunk)
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/wherecode.c.

1125
1126
1127
1128
1129
1130
1131


1132
1133
1134
1135
1136
1137
1138
  Vdbe *v;                        /* The prepared stmt under constructions */
  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 */



  pParse = pWInfo->pParse;
  v = pParse->pVdbe;
  pWC = &pWInfo->sWC;
  db = pParse->db;
  pLevel = &pWInfo->a[iLevel];
  pLoop = pLevel->pWLoop;







>
>







1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
  Vdbe *v;                        /* The prepared stmt under constructions */
  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;
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
    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 *zEndAff = 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 */







<







1452
1453
1454
1455
1456
1457
1458

1459
1460
1461
1462
1463
1464
1465
    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 */

    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 *zEndAff = 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 */
1701
1702
1703
1704
1705
1706
1707

1708
1709
1710
1711
1712
1713
1714
    pLevel->p1 = iIdxCur;
    pLevel->p3 = (pLoop->wsFlags&WHERE_UNQ_WANTED)!=0 ? 1:0;
    if( (pLoop->wsFlags & WHERE_CONSTRAINT)==0 ){
      pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
    }else{
      assert( pLevel->p5==0 );
    }

  }else

#ifndef SQLITE_OMIT_OR_OPTIMIZATION
  if( pLoop->wsFlags & WHERE_MULTI_OR ){
    /* Case 5:  Two or more separately indexed terms connected by OR
    **
    ** Example:







>







1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
    pLevel->p1 = iIdxCur;
    pLevel->p3 = (pLoop->wsFlags&WHERE_UNQ_WANTED)!=0 ? 1:0;
    if( (pLoop->wsFlags & WHERE_CONSTRAINT)==0 ){
      pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
    }else{
      assert( pLevel->p5==0 );
    }
    if( omitTable ) pIdx = 0;
  }else

#ifndef SQLITE_OMIT_OR_OPTIMIZATION
  if( pLoop->wsFlags & WHERE_MULTI_OR ){
    /* Case 5:  Two or more separately indexed terms connected by OR
    **
    ** Example:
2018
2019
2020
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
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061


2062
2063
2064
2065
2066
2067
2068

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





  */


  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 ){
      testcase( pWInfo->untestedTerms==0
               && (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)!=0 );
      pWInfo->untestedTerms = 1;
      continue;
    }
    pE = pTerm->pExpr;
    assert( pE!=0 );
    if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){
      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
      continue;
#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;
  }



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







>
>
>
>
>

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

|

|
|
|
|

|
|
|
|
|
>
>







2020
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
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083

#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 ){
        testcase( pWInfo->untestedTerms==0
            && (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)!=0 );
        pWInfo->untestedTerms = 1;
        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
        continue;
#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

Added test/pushdown.test.























































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
# 2017 April 29
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************

set testdir [file dirname $argv0]
source $testdir/tester.tcl
set testprefix pushdown

do_execsql_test 1.0 {
  CREATE TABLE t1(a, b, c);
  INSERT INTO t1 VALUES(1, 'b1', 'c1');
  INSERT INTO t1 VALUES(2, 'b2', 'c2');
  INSERT INTO t1 VALUES(3, 'b3', 'c3');
  INSERT INTO t1 VALUES(4, 'b4', 'c4');
  CREATE INDEX i1 ON t1(a, c);
}

proc f {val} {
  lappend ::L $val
  return 0
}
db func f f 

do_test 1.1 {
  set L [list]
  execsql { SELECT * FROM t1 WHERE a=2 AND f(b) AND f(c) }
  set L
} {c2}

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

do_execsql_test 1.3 {
  DROP INDEX i1;
  CREATE INDEX i1 ON t1(a, b);
}
do_test 1.4 {
  set L [list]
  execsql { SELECT * FROM t1 WHERE a=2 AND f(b) AND f(c) }
  set L
} {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