SQLite

  return rc;
}

/*
** Insert an OP_CursorHint instruction if it is appropriate to do so.
*/
static void codeCursorHint(
  struct SrcList_item *pTabItem,  /* FROM clause item */
  WhereInfo *pWInfo,    /* The where clause */
  WhereLevel *pLevel,   /* Which loop to provide hints for */
  WhereTerm *pEndRange  /* Hint this end-of-scan boundary term if not NULL */
){
  Parse *pParse = pWInfo->pParse;
  sqlite3 *db = pParse->db;
  Vdbe *v = pParse->pVdbe;

  sWalker.pParse = pParse;
  sWalker.u.pCCurHint = &sHint;
  pWC = &pWInfo->sWC;
  for(i=0; i<pWC->nTerm; i++){
    pTerm = &pWC->a[i];
    if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
    if( pTerm->prereqAll & pLevel->notReady ) continue;

    /* Any terms specified as part of the ON(...) clause for any LEFT 
    ** JOIN for which the current table is not the rhs are omitted
    ** from the cursor-hint. 
    **
    ** If this table is the rhs of a LEFT JOIN, only terms that were
    ** specified as part of the ON(...) clause may be included in the 
    ** hint. This is to address the following:
    **
    **   SELECT ... t1 LEFT JOIN t2 ON (t1.a=t2.b) WHERE t2.c IS NULL;
    **
    ** If the (t2.c IS NULL) constraint is pushed down to the cursor, it
    ** might filter out all rows that match (t1.a=t2.b), causing SQLite
    ** to add a row of NULL values to the output that should not be
    ** present (since the ON clause does actually match rows within t2).
    */
    if( pTabItem->fg.jointype & JT_LEFT ){
      if( !ExprHasProperty(pTerm->pExpr, EP_FromJoin) 
       || pTerm->pExpr->iRightJoinTable!=pTabItem->iCursor
      ){
        continue;
      }
    }else{
      if( ExprHasProperty(pTerm->pExpr, EP_FromJoin) ) continue;
    }

    /* All terms in pWLoop->aLTerm[] except pEndRange are used to initialize
    ** the cursor.  These terms are not needed as hints for a pure range
    ** scan (that has no == terms) so omit them. */
    if( pLoop->u.btree.nEq==0 && pTerm!=pEndRange ){
      for(j=0; j<pLoop->nLTerm && pLoop->aLTerm[j]!=pTerm; j++){}
      if( j<pLoop->nLTerm ) continue;

    sqlite3WalkExpr(&sWalker, pExpr);
    sqlite3VdbeAddOp4(v, OP_CursorHint, 
                      (sHint.pIdx ? sHint.iIdxCur : sHint.iTabCur), 0, 0,
                      (const char*)pExpr, P4_EXPR);
  }
}
#else
# define codeCursorHint(A,B,C,D)  /* No-op */
#endif /* SQLITE_ENABLE_CURSOR_HINTS */

/*
** Cursor iCur is open on an intkey b-tree (a table). Register iRowid contains
** a rowid value just read from cursor iIdxCur, open on index pIdx. This
** function generates code to do a deferred seek of cursor iCur to the 
** rowid stored in register iRowid.

    if( pLoop->wsFlags & WHERE_TOP_LIMIT ) pEnd = pLoop->aLTerm[j++];
    assert( pStart!=0 || pEnd!=0 );
    if( bRev ){
      pTerm = pStart;
      pStart = pEnd;
      pEnd = pTerm;
    }
    codeCursorHint(pTabItem, pWInfo, pLevel, pEnd);
    if( pStart ){
      Expr *pX;             /* The expression that defines the start bound */
      int r1, rTemp;        /* Registers for holding the start boundary */

      /* The following constant maps TK_xx codes into corresponding 
      ** seek opcodes.  It depends on a particular ordering of TK_xx
      */

      SWAP(u8, bSeekPastNull, bStopAtNull);
    }

    /* Generate code to evaluate all constraint terms using == or IN
    ** and store the values of those terms in an array of registers
    ** starting at regBase.
    */
    codeCursorHint(pTabItem, pWInfo, pLevel, pRangeEnd);
    regBase = codeAllEqualityTerms(pParse,pLevel,bRev,nExtraReg,&zStartAff);
    assert( zStartAff==0 || sqlite3Strlen30(zStartAff)>=nEq );
    if( zStartAff ) cEndAff = zStartAff[nEq];
    addrNxt = pLevel->addrNxt;

    testcase( pRangeStart && (pRangeStart->eOperator & WO_LE)!=0 );
    testcase( pRangeStart && (pRangeStart->eOperator & WO_GE)!=0 );

    static const u8 aStart[] = { OP_Rewind, OP_Last };
    assert( bRev==0 || bRev==1 );
    if( pTabItem->fg.isRecursive ){
      /* Tables marked isRecursive have only a single row that is stored in
      ** a pseudo-cursor.  No need to Rewind or Next such cursors. */
      pLevel->op = OP_Noop;
    }else{
      codeCursorHint(pTabItem, pWInfo, pLevel, 0);
      pLevel->op = aStep[bRev];
      pLevel->p1 = iCur;
      pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk);
      VdbeCoverageIf(v, bRev==0);
      VdbeCoverageIf(v, bRev!=0);
      pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
    }

# 2016 June 17
#
# 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.
#
#***********************************************************************
# This file implements regression tests for SQLite library. The
# focus is on testing that cursor-hints are correct for queries
# involving LEFT JOIN.
#


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

ifcapable !cursorhints {
  finish_test
  return
}

proc extract_hints {sql} {

  db eval "SELECT tbl_name, rootpage FROM sqlite_master where rootpage" {
    set lookup($rootpage) $tbl_name
  }

  set ret [list]
  db eval "EXPLAIN $sql" a {
    switch -- $a(opcode) {
      OpenRead {
        set csr($a(p1)) $lookup($a(p2))
      }
      CursorHint { 
        lappend ret $csr($a(p1)) $a(p4) 
      }
    }
  }

  set ret
}

proc do_extract_hints_test {tn sql ret} {
  uplevel [list do_test $tn [list extract_hints $sql] [list {*}$ret]]
}

do_execsql_test 1.0 {
  PRAGMA automatic_index = 0;
  CREATE TABLE t1(a, b);
  CREATE TABLE t2(c, d);
  CREATE TABLE t3(e, f);
}

do_extract_hints_test $tn.1.1 {
  SELECT * FROM t1 WHERE a=1;
} {
  t1 EQ(c0,1)
}

do_extract_hints_test $tn.1.2 {
  SELECT * FROM t1 CROSS JOIN t2 ON (a=c) WHERE d IS NULL;
} {
  t2 {AND(ISNULL(c1),EQ(r[1],c0))}
}

do_extract_hints_test $tn.1.3 {
  SELECT * FROM t1 LEFT JOIN t2 ON (a=c) WHERE d IS NULL;
} {
  t2 {EQ(r[2],c0)}
}

do_extract_hints_test $tn.1.4 {
  SELECT * FROM t1 LEFT JOIN t2 ON (a=c AND a=10) WHERE d IS NULL;
} {
  t2 {AND(EQ(r[2],c0),EQ(r[3],10))}
}

do_extract_hints_test $tn.1.5 {
  SELECT * FROM t1 CROSS JOIN t2 ON (a=c AND a=10) WHERE d IS NULL;
} {
  t1 EQ(c0,10) t2 {AND(ISNULL(c1),EQ(r[3],c0))}
}

do_extract_hints_test $tn.1.6 {
  SELECT * FROM t1 LEFT JOIN t2 ON (a=c) LEFT JOIN t3 ON (d=f);
} {
  t2 {EQ(r[2],c0)} t3 {EQ(r[6],c1)}
}

do_extract_hints_test $tn.1.6 {
  SELECT * FROM t1 LEFT JOIN t2 ON (a=c AND d=e) LEFT JOIN t3 ON (d=f);
} {
  t2 {EQ(r[2],c0)} t3 {EQ(r[6],c1)}
}

finish_test