SQLite

  for(i=iFrom=0, pLevel=pWInfo->a; i<nTabList; i++, pLevel++){
    WhereCost bestPlan;         /* Most efficient plan seen so far */
    Index *pIdx;                /* Index for FROM table at pTabItem */
    int j;                      /* For looping over FROM tables */
    int bestJ = -1;             /* The value of j */
    Bitmask m;                  /* Bitmask value for j or bestJ */
    int isOptimal;              /* Iterator for optimal/non-optimal search */
    int nUnconstrained;         /* Number tables without INDEXED BY */

    memset(&bestPlan, 0, sizeof(bestPlan));
    bestPlan.rCost = SQLITE_BIG_DBL;

    /* Loop through the remaining entries in the FROM clause to find the
    ** next nested loop. The loop tests all FROM clause entries
    ** either once or twice. 

    ** The best strategy is to iterate through table t1 first. However it
    ** is not possible to determine this with a simple greedy algorithm.
    ** However, since the cost of a linear scan through table t2 is the same 
    ** as the cost of a linear scan through table t1, a simple greedy 
    ** algorithm may choose to use t2 for the outer loop, which is a much
    ** costlier approach.
    */
    nUnconstrained = 0;
    for(isOptimal=(iFrom<nTabList-1); isOptimal>=0; isOptimal--){
      Bitmask mask;  /* Mask of tables not yet ready */
      for(j=iFrom, pTabItem=&pTabList->a[j]; j<nTabList; j++, pTabItem++){
        int doNotReorder;    /* True if this table should not be reordered */
        WhereCost sCost;     /* Cost information from best[Virtual]Index() */
        ExprList *pOrderBy;  /* ORDER BY clause for index to optimize */
  
        doNotReorder =  (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0;
        if( j!=iFrom && doNotReorder ) break;
        m = getMask(pMaskSet, pTabItem->iCursor);
        if( (m & notReady)==0 ){
          if( j==iFrom ) iFrom++;
          continue;
        }
        mask = (isOptimal ? m : notReady);
        pOrderBy = ((i==0 && ppOrderBy )?*ppOrderBy:0);
        if( pTabItem->pIndex==0 ) nUnconstrained++;
  
        assert( pTabItem->pTab );
#ifndef SQLITE_OMIT_VIRTUALTABLE
        if( IsVirtual(pTabItem->pTab) ){
          sqlite3_index_info **pp = &pWInfo->a[j].pIdxInfo;
          bestVirtualIndex(pParse, pWC, pTabItem, mask, pOrderBy, &sCost, pp);
        }else 
#endif
        {
          bestBtreeIndex(pParse, pWC, pTabItem, mask, pOrderBy, &sCost);
        }
        assert( isOptimal || (sCost.used&notReady)==0 );

        /* Conditions under which this table becomes the best so far:
        **
        **   (1) The table must not depend on other tables that have not
        **       yet run.
        **
        **   (2) A full-table-scan plan cannot supercede another plan unless
        **       the full-table-scan is an optimal plan.
        **
        **   (3) The plan cost must be lower than prior plans or else the
        **       cost must be the same and the number of rows must be lower.
        **
        **   (4) All tables have an INDEXED BY clause or this table lacks an
        **       INDEXED BY clause or this table uses the specific
        **       index specified by its INDEXED BY clause.
        */
        if( (sCost.used&notReady)==0
         && (bestJ<0 || sCost.rCost<bestPlan.rCost
             || (sCost.rCost<=bestPlan.rCost && sCost.nRow<bestPlan.nRow))
        if( (sCost.used&notReady)==0                       /* (1) */
            && (bestJ<0 || isOptimal                       /* (2) */
                || (sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0)
            && (bestJ<0 || sCost.rCost<bestPlan.rCost      /* (3) */
                || (sCost.rCost<=bestPlan.rCost && sCost.nRow<bestPlan.nRow))
            && (nUnconstrained==0 || pTabItem->pIndex==0   /* (4) */
                || pTabItem->pIndex==sCost.plan.u.pIdx)
        ){
          WHERETRACE(("... best so far with cost=%g and nRow=%g\n",
                      sCost.rCost, sCost.nRow));
          bestPlan = sCost;
          bestJ = j;
        }
        if( doNotReorder ) break;

#
do_test indexedby-4.1 {
  EQP { SELECT * FROM t1, t2 WHERE a = c }
} {0 0 {TABLE t1} 1 1 {TABLE t2 WITH INDEX i3}}
do_test indexedby-4.2 {
  EQP { SELECT * FROM t1 INDEXED BY i1, t2 WHERE a = c }
} {0 1 {TABLE t2} 1 0 {TABLE t1 WITH INDEX i1}}
do_test indexedby-4.3 {
  catchsql {
    SELECT * FROM t1 INDEXED BY i1, t2 INDEXED BY i3 WHERE a=c
  }
} {1 {cannot use index: i1}}
do_test indexedby-4.4 {
  catchsql {
    SELECT * FROM t2 INDEXED BY i3, t1 INDEXED BY i1 WHERE a=c
  }
} {1 {cannot use index: i3}}

# Test embedding an INDEXED BY in a CREATE VIEW statement. This block
# also tests that nothing bad happens if an index refered to by
# a CREATE VIEW statement is dropped and recreated.
#
do_test indexedby-5.1 {
  execsql {

do_test where3-2.7 {
  queryplan {
    SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx
     WHERE cpk=bx AND apk=cx
  }
} {tB {} tC * tA * tD *}

# Ticket [13f033c865f878953]
# If the outer loop must be a full table scan, do not let ANALYZE trick
# the planner into use a table for the outer loop that might be indexable
# if held until an inner loop.
# 
do_test where3-3.0 {
  execsql {
    CREATE TABLE t301(a INTEGER PRIMARY KEY,b,c);
    CREATE INDEX t301c ON t301(c);
    INSERT INTO t301 VALUES(1,2,3);
    CREATE TABLE t302(x, y);
    ANALYZE;
    explain query plan
    SELECT * FROM t302, t301 WHERE t302.x=5 AND t301.a=t302.y;
  }
} {0 0 {TABLE t302} 1 1 {TABLE t301 USING PRIMARY KEY}}
do_test where3-3.1 {
  execsql {
    explain query plan
    SELECT * FROM t301, t302 WHERE t302.x=5 AND t301.a=t302.y;
  }
} {0 1 {TABLE t302} 1 0 {TABLE t301 USING PRIMARY KEY}}

finish_test