SQLite

    Bitmask m;                  /* Bitmask value for j or bestJ */
    int isOptimal;              /* Iterator for optimal/non-optimal search */
    int nUnconstrained;         /* Number tables without INDEXED BY */
    Bitmask notIndexed;         /* Mask of tables that cannot use an index */

    memset(&bestPlan, 0, sizeof(bestPlan));
    bestPlan.rCost = SQLITE_BIG_DBL;
    WHERETRACE(("*** Begin search for loop %d ***\n", i));

    /* 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 first test is always performed if there are two or more entries
    ** remaining and never performed if there is only one FROM clause entry

          if( j==iFrom ) iFrom++;
          continue;
        }
        mask = (isOptimal ? m : notReady);
        pOrderBy = ((i==0 && ppOrderBy )?*ppOrderBy:0);
        if( pTabItem->pIndex==0 ) nUnconstrained++;
  
        WHERETRACE(("=== trying table %d with isOptimal=%d ===\n",
                    j, isOptimal));
        assert( pTabItem->pTab );
#ifndef SQLITE_OMIT_VIRTUALTABLE
        if( IsVirtual(pTabItem->pTab) ){
          sqlite3_index_info **pp = &pWInfo->a[j].pIdxInfo;
          bestVirtualIndex(pParse, pWC, pTabItem, mask, notReady, pOrderBy,
                           &sCost, pp);
        }else 

            && (bestJ<0 || (notIndexed&m)!=0               /* (2) */
                || (sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0)
            && (nUnconstrained==0 || pTabItem->pIndex==0   /* (3) */
                || NEVER((sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0))
            && (bestJ<0 || sCost.rCost<bestPlan.rCost      /* (4) */
                || (sCost.rCost<=bestPlan.rCost && sCost.nRow<bestPlan.nRow))
        ){
          WHERETRACE(("=== table %d is best so far"
                      " with cost=%g and nRow=%g\n",
                      j, sCost.rCost, sCost.nRow));
          bestPlan = sCost;
          bestJ = j;
        }
        if( doNotReorder ) break;
      }
    }
    assert( bestJ>=0 );
    assert( notReady & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
    WHERETRACE(("*** Optimizer selects table %d for loop %d"
                " with cost=%g and nRow=%g\n",
                bestJ, pLevel-pWInfo->a, bestPlan.rCost, bestPlan.nRow));
    if( (bestPlan.plan.wsFlags & WHERE_ORDERBY)!=0 ){
      *ppOrderBy = 0;
    }
    andFlags &= bestPlan.plan.wsFlags;
    pLevel->plan = bestPlan.plan;
    testcase( bestPlan.plan.wsFlags & WHERE_INDEXED );
    testcase( bestPlan.plan.wsFlags & WHERE_TEMP_INDEX );

         OR a=23
         OR (f GLOB '?defg*' AND f GLOB 'cdef*')
         OR d<0.0
         OR (d>=22.0 AND d<23.0 AND d NOT NULL)
         OR a=91
  }
} {2 22 23 28 54 80 91 scan 0 sort 0}

# test case for the performance regression fixed by
# check-in 28ba6255282b on 2010-10-21 02:05:06
#
# The test case that follows is code from an actual
# application with identifiers change and unused columns
# remove.
#
do_test where7-3.1 {
  db eval {
    CREATE TABLE t301 (
        c8 INTEGER PRIMARY KEY,
        c6 INTEGER,
        c4 INTEGER,
        c7 INTEGER,
        FOREIGN KEY (c4) REFERENCES series(c4)
    );
    CREATE INDEX t301_c6 on t301(c6);
    CREATE INDEX t301_c4 on t301(c4);
    CREATE INDEX t301_c7 on t301(c7);
    
    CREATE TABLE t302 (
        c1 INTEGER PRIMARY KEY,
        c8 INTEGER,
        c5 INTEGER,
        c3 INTEGER,
        c2 INTEGER,
        c4 INTEGER,
        FOREIGN KEY (c8) REFERENCES t301(c8)
    );
    CREATE INDEX t302_c3 on t302(c3);
    CREATE INDEX t302_c8_c3 on t302(c8, c3);
    CREATE INDEX t302_c5 on t302(c5);
    
    EXPLAIN QUERY PLAN
    SELECT t302.c1 
      FROM t302 JOIN t301 ON t302.c8 = t301.c8
      WHERE t302.c2 = 19571
        AND t302.c3 > 1287603136
        AND (t301.c4 = 1407449685622784
             OR t301.c8 = 1407424651264000)
     ORDER BY t302.c5 LIMIT 200;
  }
} {0 1 {TABLE t301 VIA MULTI-INDEX UNION} 1 0 {TABLE t302 WITH INDEX t302_c8_c3} 0 0 {TABLE t301 WITH INDEX t301_c4} 0 0 {TABLE t301 USING PRIMARY KEY}}

finish_test