SQLite

*/
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
/***/ int sqlite3WhereTrace = 0;
#endif
#if defined(SQLITE_DEBUG) \
    && (defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHERETRACE))
# define WHERETRACE(X)  if(sqlite3WhereTrace) sqlite3DebugPrintf X
# define WHERETRACE_ENABLED 1
#else
# define WHERETRACE(X)
#endif

/* Forward reference
*/
typedef struct WhereClause WhereClause;

** term of a join.  The WhereClause object holds a table of these
** objects using (maskSelf,prereq,) as the primary key.  Note that the
** same join term might have multiple associated WhereLoop objects.
*/
struct WhereLoop {
  Bitmask prereq;       /* Bitmask of other loops that must run first */
  Bitmask maskSelf;     /* Bitmask identifying table iTab */
#ifdef SQLITE_DEBUG
  char cId;             /* Symbolic ID of this loop for debugging use */
#endif
  u8 iTab;              /* Position in FROM clause of table coded by this loop */
  u8 iSortIdx;          /* Sorting index number.  0==None */
  u16 nTerm;            /* Number of entries in aTerm[] */
  u32 wsFlags;          /* WHERE_* flags describing the plan */
  double rSetup;        /* One-time setup cost (ex: create transient index) */
  double rRun;          /* Cost of running each loop */
  double nOut;          /* Estimated number of output rows */

/*
** Two routines for printing the content of an sqlite3_index_info
** structure.  Used for testing and debugging only.  If neither
** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines
** are no-ops.
*/
#if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(WHERETRACE_ENABLED)
static void TRACE_IDX_INPUTS(sqlite3_index_info *p){
  int i;
  if( !sqlite3WhereTrace ) return;
  for(i=0; i<p->nConstraint; i++){
    sqlite3DebugPrintf("  constraint[%d]: col=%d termid=%d op=%d usabled=%d\n",
       i,
       p->aConstraint[i].iColumn,

** analysis only.
*/
char sqlite3_query_plan[BMS*2*40];  /* Text of the join */
static int nQPlan = 0;              /* Next free slow in _query_plan[] */

#endif /* SQLITE_TEST */


#ifdef WHERETRACE_ENABLED
/*
** Print a WhereLoop object for debugging purposes
*/
static void whereLoopPrint(WhereLoop *p, SrcList *pTabList){
  int nb = 2*((pTabList->nSrc+15)/16);
  struct SrcList_item *pItem = pTabList->a + p->iTab;
  Table *pTab = pItem->pTab;
  sqlite3DebugPrintf("%c %2d.%0*llx.%0*llx", p->cId,
                     p->iTab, nb, p->maskSelf, nb, p->prereq);
  sqlite3DebugPrintf(" %8s",
                     pItem->zAlias ? pItem->zAlias : pTab->zName);
  if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){
    if( p->u.btree.pIndex ){
      const char *zName = p->u.btree.pIndex->zName;
      if( strncmp(zName, "sqlite_autoindex_", 17)==0 ){

    }else{
      z = sqlite3_mprintf("(%d)", p->u.vtab.idxNum);
    }
    sqlite3DebugPrintf(" %-15s", z);
    sqlite3_free(z);
  }
  sqlite3DebugPrintf(" fg %08x N %2d", p->wsFlags, p->nTerm);
  sqlite3DebugPrintf(" cost %.2g,%.2g,%.2g\n",
                     p->prereq, p->rSetup, p->rRun, p->nOut);
}
#endif

/*
** Deallocate internal memory used by a WhereLoop object
*/

  }
    
  for(i=0; i<=nLoop && nUsed<nOrderBy; i++){
    pLoop = i<nLoop ? pPath->aLoop[i] : pLast;
    assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 );
    isUnique = 1;
    if( pLoop->wsFlags & WHERE_IPK ){
      if( (pLoop->wsFlags & WHERE_COLUMN_IN)!=0 ) isUnique = 0;
      if( pLoop->u.btree.nEq!=1 ) isUnique = 0;
      pIndex = 0;
      nColumn = 1;
    }else if( pLoop->u.btree.pIndex==0 ){
      return 0;
    }else{
      pIndex = pLoop->u.btree.pIndex;
      nColumn = pIndex->nColumn;

  }
  if( nUsed==nOrderBy ){
    *pRevMask = revMask;
    return 1;
  }
  return -1;
}

#ifdef WHERETRACE_ENABLED
/* For debugging use only: */
static const char *wherePathName(WherePath *pPath, int nLoop, WhereLoop *pLast){
  static char zName[65];
  int i;
  for(i=0; i<nLoop; i++){ zName[i] = pPath->aLoop[i]->cId; }
  if( pLast ) zName[i++] = pLast->cId;
  zName[i] = 0;
  return zName;
}
#endif


/*
** Given the list of WhereLoop objects on pWInfo->pLoops, this routine
** attempts to find the lowest cost path that visits each WhereLoop
** once.  This path is then loaded into the pWInfo->a[].pWLoop fields.
**

        /* Check to see if pWLoop should be added to the mxChoice best so far */
        for(jj=0, pTo=aTo; jj<nTo; jj++, pTo++){
          if( pTo->maskLoop==maskNew && pTo->isOrderedValid==isOrderedValid ){
            break;
          }
        }
        if( jj>=nTo ){
          if( nTo>=mxChoice && rCost>=mxCost ){
#ifdef WHERETRACE_ENABLE
            if( sqlite3WhereTrace>=3 ){
              sqlite3DebugPrintf("Skip   %s cost=%-7.2g order=%c\n",
                  wherePathName(pFrom, iLoop, pWLoop), rCost,
                  isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?');
            }
#endif
            continue;
          }
          /* Add a new Path to the aTo[] set */
          if( nTo<mxChoice ){
            /* Increase the size of the aTo set by one */
            jj = nTo++;
          }else{
            /* New path replaces the prior worst to keep count below mxChoice */
            for(jj=nTo-1; aTo[jj].rCost<mxCost; jj--){ assert(jj>0); }
          }
          pTo = &aTo[jj];
#ifdef WHERETRACE_ENABLED
          if( sqlite3WhereTrace>=3 ){
            sqlite3DebugPrintf("New    %s cost=%-7.2g order=%c\n",
                wherePathName(pFrom, iLoop, pWLoop), rCost,
                isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?');
          }
#endif
        }else{
          if( pTo->rCost<=rCost ){
#ifdef WHERETRACE_ENABLED
            if( sqlite3WhereTrace>=3 ){
              sqlite3DebugPrintf(
                  "Skip   %s cost=%-7.2g order=%c",
                  wherePathName(pFrom, iLoop, pWLoop), rCost,
                  isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?');
              sqlite3DebugPrintf("   vs %s cost=%-7.2g order=%c\n",
                  wherePathName(pTo, iLoop+1, 0), pTo->rCost,
                  pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?');
            }
#endif
            continue;
          }
          /* A new and better score for a previously created equivalent path */
#ifdef WHERETRACE_ENABLED
          if( sqlite3WhereTrace>=3 ){
            sqlite3DebugPrintf(
                "Update %s cost=%-7.2g order=%c",
                wherePathName(pFrom, iLoop, pWLoop), rCost,
                isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?');
            sqlite3DebugPrintf("  was %s cost=%-7.2g order=%c\n",
                wherePathName(pTo, iLoop+1, 0), pTo->rCost,
                pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?');
          }
#endif
        }
        /* pWLoop is a winner.  Add it to the set of best so far */
        pTo->maskLoop = pFrom->maskLoop | pWLoop->maskSelf;
        pTo->revLoop = revMask;
        pTo->nRow = pFrom->nRow * pWLoop->nOut;
        pTo->rCost = rCost;
        pTo->isOrderedValid = isOrderedValid;
        pTo->isOrdered = isOrdered;
        memcpy(pTo->aLoop, pFrom->aLoop, sizeof(WhereLoop*)*iLoop);
        pTo->aLoop[iLoop] = pWLoop;
        if( nTo>=mxChoice ){
          mxCost = aTo[0].rCost;
          for(jj=1, pTo=&aTo[1]; jj<mxChoice; jj++, pTo++){
            if( pTo->rCost>mxCost ) mxCost = pTo->rCost;
          }
        }
      }
    }

#ifdef WHERETRACE_ENABLED
    if( sqlite3WhereTrace>=2 ){
      sqlite3DebugPrintf("---- round %d ----\n", iLoop);
      for(ii=0, pTo=aTo; ii<nTo; ii++, pTo++){
        sqlite3DebugPrintf("%2d: %s cost=%-7.2g nrow=%-7.2g order=%c\n",
           ii, wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow,
           pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?');


      }
    }
#endif

    /* Swap the roles of aFrom and aTo for the next generation */
    pFrom = aTo;
    aTo = aFrom;

  /* Construct the WhereLoop objects */
  WHERETRACE(("*** Optimizer Start ***\n"));
  rc = whereLoopAddAll(&sWLB);
  if( rc ) goto whereBeginError;

  /* Display all of the WhereLoop objects if wheretrace is enabled */

#ifdef WHERETRACE_ENABLED
  if( sqlite3WhereTrace ){
    WhereLoop *p;
    int i = 0;
    static char zLabel[] = "0123456789abcdefghijklmnopqrstuvwyxz"
                                     "ABCDEFGHIJKLMNOPQRSTUVWYXZ";
    for(p=pWInfo->pLoops; p; p=p->pNextLoop){
      p->cId = zLabel[(i++)%sizeof(zLabel)];
      whereLoopPrint(p, pTabList);
    }
  }
#endif

  wherePathSolver(pWInfo);
  if( db->mallocFailed ) goto whereBeginError;

#ifdef WHERETRACE_ENABLED
  if( sqlite3WhereTrace ){
    int ii;
    sqlite3DebugPrintf("------------ Solution -------------");
    if( pWInfo->nOBSat ){
      sqlite3DebugPrintf(" ORDER BY omitted\n");
    }else{
      sqlite3DebugPrintf("\n");

  */
  assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 );
  if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_UNIQUE)!=0 ){
    pWInfo->okOnePass = 1;
    pWInfo->a[0].plan.wsFlags &= ~WHERE_IDX_ONLY;
  }

#if 1
  /* Scaffolding:  Check the new query plan against the old.  Report any
  ** discrepencies */
  for(ii=0; ii<nTabList; ii++){
    if( pWInfo->a[ii].iFrom!=pWInfo->a[ii].pWLoop->iTab ){
      sqlite3DebugPrintf("(QP-Mismatch)");
      break;
    }

  }
} {72057594037927935 17}
do_test boundary3-2.1.3 {
  db eval {
    SELECT t1.rowid, x FROM t1 JOIN t2 ON t2.r=t1.rowid WHERE t2.a=17
  }
} {72057594037927935 00ffffffffffffff}
exit
do_test boundary3-2.1.gt.1 {
  db eval {
    SELECT t2.a FROM t1 JOIN t2 USING(a)
     WHERE t1.rowid > 72057594037927935 ORDER BY t2.a
  }
} {3 28}
do_test boundary3-2.1.gt.2 {