/ 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.
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
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
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. 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 Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/wherecode.c.

  1125   1125     Vdbe *v;                        /* The prepared stmt under constructions */
  1126   1126     struct SrcList_item *pTabItem;  /* FROM clause term being coded */
  1127   1127     int addrBrk;                    /* Jump here to break out of the loop */
  1128   1128     int addrHalt;                   /* addrBrk for the outermost loop */
  1129   1129     int addrCont;                   /* Jump here to continue with next cycle */
  1130   1130     int iRowidReg = 0;        /* Rowid is stored in this register, if not zero */
  1131   1131     int iReleaseReg = 0;      /* Temp register to free before returning */
         1132  +  Index *pIdx = 0;          /* Index used by loop (if any) */
         1133  +  int loopAgain;            /* True if constraint generator loop should repeat */
  1132   1134   
  1133   1135     pParse = pWInfo->pParse;
  1134   1136     v = pParse->pVdbe;
  1135   1137     pWC = &pWInfo->sWC;
  1136   1138     db = pParse->db;
  1137   1139     pLevel = &pWInfo->a[iLevel];
  1138   1140     pLoop = pLevel->pWLoop;
................................................................................
  1450   1452       int regBase;                 /* Base register holding constraint values */
  1451   1453       WhereTerm *pRangeStart = 0;  /* Inequality constraint at range start */
  1452   1454       WhereTerm *pRangeEnd = 0;    /* Inequality constraint at range end */
  1453   1455       int startEq;                 /* True if range start uses ==, >= or <= */
  1454   1456       int endEq;                   /* True if range end uses ==, >= or <= */
  1455   1457       int start_constraints;       /* Start of range is constrained */
  1456   1458       int nConstraint;             /* Number of constraint terms */
  1457         -    Index *pIdx;                 /* The index we will be using */
  1458   1459       int iIdxCur;                 /* The VDBE cursor for the index */
  1459   1460       int nExtraReg = 0;           /* Number of extra registers needed */
  1460   1461       int op;                      /* Instruction opcode */
  1461   1462       char *zStartAff;             /* Affinity for start of range constraint */
  1462   1463       char *zEndAff = 0;           /* Affinity for end of range constraint */
  1463   1464       u8 bSeekPastNull = 0;        /* True to seek past initial nulls */
  1464   1465       u8 bStopAtNull = 0;          /* Add condition to terminate at NULLs */
................................................................................
  1701   1702       pLevel->p1 = iIdxCur;
  1702   1703       pLevel->p3 = (pLoop->wsFlags&WHERE_UNQ_WANTED)!=0 ? 1:0;
  1703   1704       if( (pLoop->wsFlags & WHERE_CONSTRAINT)==0 ){
  1704   1705         pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
  1705   1706       }else{
  1706   1707         assert( pLevel->p5==0 );
  1707   1708       }
         1709  +    if( omitTable ) pIdx = 0;
  1708   1710     }else
  1709   1711   
  1710   1712   #ifndef SQLITE_OMIT_OR_OPTIMIZATION
  1711   1713     if( pLoop->wsFlags & WHERE_MULTI_OR ){
  1712   1714       /* Case 5:  Two or more separately indexed terms connected by OR
  1713   1715       **
  1714   1716       ** Example:
................................................................................
  2018   2020   
  2019   2021   #ifdef SQLITE_ENABLE_STMT_SCANSTATUS
  2020   2022     pLevel->addrVisit = sqlite3VdbeCurrentAddr(v);
  2021   2023   #endif
  2022   2024   
  2023   2025     /* Insert code to test every subexpression that can be completely
  2024   2026     ** computed using the current set of tables.
         2027  +  **
         2028  +  ** This loop may run either once (pIdx==0) or twice (pIdx!=0). If
         2029  +  ** it is run twice, then the first iteration codes those sub-expressions
         2030  +  ** that can be computed using columns from pIdx only (without seeking
         2031  +  ** the main table cursor). 
  2025   2032     */
  2026         -  for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){
  2027         -    Expr *pE;
  2028         -    int skipLikeAddr = 0;
  2029         -    testcase( pTerm->wtFlags & TERM_VIRTUAL );
  2030         -    testcase( pTerm->wtFlags & TERM_CODED );
  2031         -    if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
  2032         -    if( (pTerm->prereqAll & pLevel->notReady)!=0 ){
  2033         -      testcase( pWInfo->untestedTerms==0
  2034         -               && (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)!=0 );
  2035         -      pWInfo->untestedTerms = 1;
  2036         -      continue;
  2037         -    }
  2038         -    pE = pTerm->pExpr;
  2039         -    assert( pE!=0 );
  2040         -    if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){
  2041         -      continue;
  2042         -    }
  2043         -    if( pTerm->wtFlags & TERM_LIKECOND ){
  2044         -      /* If the TERM_LIKECOND flag is set, that means that the range search
  2045         -      ** is sufficient to guarantee that the LIKE operator is true, so we
  2046         -      ** can skip the call to the like(A,B) function.  But this only works
  2047         -      ** for strings.  So do not skip the call to the function on the pass
  2048         -      ** that compares BLOBs. */
         2033  +  do{
         2034  +    loopAgain = 0;
         2035  +    for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){
         2036  +      Expr *pE;
         2037  +      int skipLikeAddr = 0;
         2038  +      testcase( pTerm->wtFlags & TERM_VIRTUAL );
         2039  +      testcase( pTerm->wtFlags & TERM_CODED );
         2040  +      if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
         2041  +      if( (pTerm->prereqAll & pLevel->notReady)!=0 ){
         2042  +        testcase( pWInfo->untestedTerms==0
         2043  +            && (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)!=0 );
         2044  +        pWInfo->untestedTerms = 1;
         2045  +        continue;
         2046  +      }
         2047  +      pE = pTerm->pExpr;
         2048  +      assert( pE!=0 );
         2049  +      if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){
         2050  +        continue;
         2051  +      }
         2052  +      if( pIdx && !sqlite3ExprCoveredByIndex(pE, pLevel->iTabCur, pIdx) ){
         2053  +        loopAgain = 1;
         2054  +        continue;
         2055  +      }
         2056  +      if( pTerm->wtFlags & TERM_LIKECOND ){
         2057  +        /* If the TERM_LIKECOND flag is set, that means that the range search
         2058  +        ** is sufficient to guarantee that the LIKE operator is true, so we
         2059  +        ** can skip the call to the like(A,B) function.  But this only works
         2060  +        ** for strings.  So do not skip the call to the function on the pass
         2061  +        ** that compares BLOBs. */
  2049   2062   #ifdef SQLITE_LIKE_DOESNT_MATCH_BLOBS
  2050         -      continue;
         2063  +        continue;
  2051   2064   #else
  2052         -      u32 x = pLevel->iLikeRepCntr;
  2053         -      assert( x>0 );
  2054         -      skipLikeAddr = sqlite3VdbeAddOp1(v, (x&1)? OP_IfNot : OP_If, (int)(x>>1));
  2055         -      VdbeCoverage(v);
         2065  +        u32 x = pLevel->iLikeRepCntr;
         2066  +        assert( x>0 );
         2067  +        skipLikeAddr = sqlite3VdbeAddOp1(v, (x&1)?OP_IfNot:OP_If, (int)(x>>1));
         2068  +        VdbeCoverage(v);
  2056   2069   #endif
         2070  +      }
         2071  +      sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL);
         2072  +      if( skipLikeAddr ) sqlite3VdbeJumpHere(v, skipLikeAddr);
         2073  +      pTerm->wtFlags |= TERM_CODED;
  2057   2074       }
  2058         -    sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL);
  2059         -    if( skipLikeAddr ) sqlite3VdbeJumpHere(v, skipLikeAddr);
  2060         -    pTerm->wtFlags |= TERM_CODED;
  2061         -  }
         2075  +    pIdx = 0;
         2076  +  }while( loopAgain );
  2062   2077   
  2063   2078     /* Insert code to test for implied constraints based on transitivity
  2064   2079     ** of the "==" operator.
  2065   2080     **
  2066   2081     ** Example: If the WHERE clause contains "t1.a=t2.b" and "t2.b=123"
  2067   2082     ** and we are coding the t1 loop and the t2 loop has not yet coded,
  2068   2083     ** then we cannot use the "t1.a=t2.b" constraint, but we can code

Added test/pushdown.test.

            1  +# 2017 April 29
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#***********************************************************************
           11  +
           12  +set testdir [file dirname $argv0]
           13  +source $testdir/tester.tcl
           14  +set testprefix pushdown
           15  +
           16  +do_execsql_test 1.0 {
           17  +  CREATE TABLE t1(a, b, c);
           18  +  INSERT INTO t1 VALUES(1, 'b1', 'c1');
           19  +  INSERT INTO t1 VALUES(2, 'b2', 'c2');
           20  +  INSERT INTO t1 VALUES(3, 'b3', 'c3');
           21  +  INSERT INTO t1 VALUES(4, 'b4', 'c4');
           22  +  CREATE INDEX i1 ON t1(a, c);
           23  +}
           24  +
           25  +proc f {val} {
           26  +  lappend ::L $val
           27  +  return 0
           28  +}
           29  +db func f f 
           30  +
           31  +do_test 1.1 {
           32  +  set L [list]
           33  +  execsql { SELECT * FROM t1 WHERE a=2 AND f(b) AND f(c) }
           34  +  set L
           35  +} {c2}
           36  +
           37  +do_test 1.2 {
           38  +  set L [list]
           39  +  execsql { SELECT * FROM t1 WHERE a=3 AND f(c) AND f(b) }
           40  +  set L
           41  +} {c3}
           42  +
           43  +do_execsql_test 1.3 {
           44  +  DROP INDEX i1;
           45  +  CREATE INDEX i1 ON t1(a, b);
           46  +}
           47  +do_test 1.4 {
           48  +  set L [list]
           49  +  execsql { SELECT * FROM t1 WHERE a=2 AND f(b) AND f(c) }
           50  +  set L
           51  +} {b2}
           52  +
           53  +do_test 1.5 {
           54  +  set L [list]
           55  +  execsql { SELECT * FROM t1 WHERE a=3 AND f(c) AND f(b) }
           56  +  set L
           57  +} {b3}
           58  +  
           59  +finish_test