SQLite

NLTLIBPATHS = "/LIBPATH:$(NCRTLIBPATH)" "/LIBPATH:$(NSDKLIBPATH)"
!ENDIF

# C compiler and options for use in building executables that
# will run on the target platform.  (BCC and TCC are usually the
# same unless your are cross-compiling.)
#
TCC = $(CC) -W3 -DSQLITE_OS_WIN=1 -I$(TOP) -I$(TOP)\src -fp:precise
RCC = $(RC) -DSQLITE_OS_WIN=1 -I$(TOP) -I$(TOP)\src

# When compiling the library for use in the WinRT environment,
# the following compile-time options must be used as well to
# disable use of Win32 APIs that are not available and to enable
# use of Win32 APIs that are specific to Windows 8 and/or WinRT.
#
!IF $(FOR_WINRT)!=0

opcodes.lo:	opcodes.c
	$(LTCOMPILE) -c opcodes.c

# Rule to build the Win32 resources object file.
#
sqlite3res.lo:	$(TOP)\src\sqlite3.rc $(HDR)
	echo #ifndef SQLITE_RESOURCE_VERSION > sqlite3rc.h
	for /F %%V in ('type "$(TOP)\VERSION"') do ( \
		echo #define SQLITE_RESOURCE_VERSION %%V \
			| $(NAWK) "/.*/ { gsub(/[.]/,\",\");print }" >> sqlite3rc.h \
	)
	echo #endif >> sqlite3rc.h
	$(LTRCOMPILE) -fo sqlite3res.lo $(TOP)\src\sqlite3.rc

# Rules to build individual *.lo files from files in the src directory.

}

/*
** Remove the entry with rowid=iDelete from the r-tree structure.
*/
static int rtreeDeleteRowid(Rtree *pRtree, sqlite3_int64 iDelete){
  int rc;                         /* Return code */
  RtreeNode *pLeaf = 0;           /* Leaf node containing record iDelete */
  int iCell;                      /* Index of iDelete cell in pLeaf */
  RtreeNode *pRoot;               /* Root node of rtree structure */


  /* Obtain a reference to the root node to initialise Rtree.iDepth */
  rc = nodeAcquire(pRtree, 1, 0, &pRoot);

  /* If the azData[] array contains more than one element, elements
  ** (azData[2]..azData[argc-1]) contain a new record to insert into
  ** the r-tree structure.
  */
  if( rc==SQLITE_OK && nData>1 ){
    /* Insert the new record into the r-tree */
    RtreeNode *pLeaf = 0;

    /* Figure out the rowid of the new row. */
    if( bHaveRowid==0 ){
      rc = newRowid(pRtree, &cell.iRowid);
    }
    *pRowid = cell.iRowid;

static int backupOnePage(sqlite3_backup *p, Pgno iSrcPg, const u8 *zSrcData){
  Pager * const pDestPager = sqlite3BtreePager(p->pDest);
  const int nSrcPgsz = sqlite3BtreeGetPageSize(p->pSrc);
  int nDestPgsz = sqlite3BtreeGetPageSize(p->pDest);
  const int nCopy = MIN(nSrcPgsz, nDestPgsz);
  const i64 iEnd = (i64)iSrcPg*(i64)nSrcPgsz;
#ifdef SQLITE_HAS_CODEC
  /* Use BtreeGetReserveNoMutex() for the source b-tree, as although it is
  ** guaranteed that the shared-mutex is held by this thread, handle
  ** p->pSrc may not actually be the owner.  */
  int nSrcReserve = sqlite3BtreeGetReserveNoMutex(p->pSrc);
  int nDestReserve = sqlite3BtreeGetReserve(p->pDest);
#endif

  int rc = SQLITE_OK;
  i64 iOff;

  assert( sqlite3BtreeGetReserveNoMutex(p->pSrc)>=0 );
  assert( p->bDestLocked );
  assert( !isFatalError(p->rc) );
  assert( iSrcPg!=PENDING_BYTE_PAGE(p->pSrc->pBt) );
  assert( zSrcData );

  /* Catch the case where the destination is an in-memory database and the
  ** page sizes of the source and destination differ. 

/*
** Return the currently defined page size
*/
int sqlite3BtreeGetPageSize(Btree *p){
  return p->pBt->pageSize;
}

#if defined(SQLITE_HAS_CODEC) || defined(SQLITE_DEBUG)
/*
** This function is similar to sqlite3BtreeGetReserve(), except that it
** may only be called if it is guaranteed that the b-tree mutex is already
** held.
**
** This is useful in one special case in the backup API code where it is
** known that the shared b-tree mutex is held, but the mutex on the 
** database handle that owns *p is not. In this case if sqlite3BtreeEnter()
** were to be called, it might collide with some other operation on the
** database handle that owns *p, causing undefined behaviour.
*/
int sqlite3BtreeGetReserveNoMutex(Btree *p){
  assert( sqlite3_mutex_held(p->pBt->mutex) );
  return p->pBt->pageSize - p->pBt->usableSize;
}
#endif /* SQLITE_HAS_CODEC || SQLITE_DEBUG */

#if !defined(SQLITE_OMIT_PAGER_PRAGMAS) || !defined(SQLITE_OMIT_VACUUM)
/*
** Return the number of bytes of space at the end of every page that
** are intentually left unused.  This is the "reserved" space that is
** sometimes used by extensions.
*/

  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  btreeParseCellPtr(pPage, pCell, &info);
  if( info.iOverflow==0 ){
    return SQLITE_OK;  /* No overflow pages. Return without doing anything */
  }
  if( pCell+info.iOverflow+3 > pPage->aData+pPage->maskPage ){
    return SQLITE_CORRUPT_BKPT;  /* Cell extends past end of page */
  }
  ovflPgno = get4byte(&pCell[info.iOverflow]);
  assert( pBt->usableSize > 4 );
  ovflPageSize = pBt->usableSize - 4;
  nOvfl = (info.nPayload - info.nLocal + ovflPageSize - 1)/ovflPageSize;
  assert( ovflPgno==0 || nOvfl>0 );
  while( nOvfl-- ){

** size of a cell stored within an internal node is always less than 1/4
** of the page-size, the aOvflSpace[] buffer is guaranteed to be large
** enough for all overflow cells.
**
** If aOvflSpace is set to a null pointer, this function returns 
** SQLITE_NOMEM.
*/
#if defined(_MSC_VER) && _MSC_VER >= 1700 && defined(_M_ARM)
#pragma optimize("", off)
#endif
static int balance_nonroot(
  MemPage *pParent,               /* Parent page of siblings being balanced */
  int iParentIdx,                 /* Index of "the page" in pParent */
  u8 *aOvflSpace,                 /* page-size bytes of space for parent ovfl */
  int isRoot,                     /* True if pParent is a root-page */
  int bBulk                       /* True if this call is part of a bulk load */
){

  }
  for(i=0; i<nNew; i++){
    releasePage(apNew[i]);
  }

  return rc;
}
#if defined(_MSC_VER) && _MSC_VER >= 1700 && defined(_M_ARM)
#pragma optimize("", on)
#endif


/*
** This function is called when the root page of a b-tree structure is
** overfull (has one or more overflow pages).
**
** A new child page is allocated and the contents of the current root

int sqlite3BtreeSyncDisabled(Btree*);
int sqlite3BtreeSetPageSize(Btree *p, int nPagesize, int nReserve, int eFix);
int sqlite3BtreeGetPageSize(Btree*);
int sqlite3BtreeMaxPageCount(Btree*,int);
u32 sqlite3BtreeLastPage(Btree*);
int sqlite3BtreeSecureDelete(Btree*,int);
int sqlite3BtreeGetReserve(Btree*);
#if defined(SQLITE_HAS_CODEC) || defined(SQLITE_DEBUG)
int sqlite3BtreeGetReserveNoMutex(Btree *p);
#endif
int sqlite3BtreeSetAutoVacuum(Btree *, int);
int sqlite3BtreeGetAutoVacuum(Btree *);
int sqlite3BtreeBeginTrans(Btree*,int);
int sqlite3BtreeCommitPhaseOne(Btree*, const char *zMaster);
int sqlite3BtreeCommitPhaseTwo(Btree*, int);
int sqlite3BtreeCommit(Btree*);
int sqlite3BtreeRollback(Btree*,int);

    }else{
      sqlite3VdbeAddOp3(v, OP_Column, iCur, idx, regBase+j);
      sqlite3ColumnDefault(v, pTab, idx, -1);
    }
  }
  if( doMakeRec ){
    const char *zAff;
    if( pTab->pSelect
     || OptimizationDisabled(pParse->db, SQLITE_IdxRealAsInt)
    ){
      zAff = 0;
    }else{
      zAff = sqlite3IndexAffinityStr(v, pIdx);
    }
    sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase, nCol+1, regOut);
    sqlite3VdbeChangeP4(v, -1, zAff, P4_TRANSIENT);
  }

  assert( iReg>0 );  /* Register numbers are always positive */
  assert( iCol>=-1 && iCol<32768 );  /* Finite column numbers */

  /* The SQLITE_ColumnCache flag disables the column cache.  This is used
  ** for testing only - to verify that SQLite always gets the same answer
  ** with and without the column cache.
  */
  if( OptimizationDisabled(pParse->db, SQLITE_ColumnCache) ) return;

  /* First replace any existing entry.
  **
  ** Actually, the way the column cache is currently used, we are guaranteed
  ** that the object will never already be in cache.  Verify this guarantee.
  */
#ifndef NDEBUG

** interface.  This allows test logic to verify that the same answer is
** obtained for queries regardless of whether or not constants are
** precomputed into registers or if they are inserted in-line.
*/
void sqlite3ExprCodeConstants(Parse *pParse, Expr *pExpr){
  Walker w;
  if( pParse->cookieGoto ) return;
  if( OptimizationDisabled(pParse->db, SQLITE_FactorOutConst) ) return;
  w.xExprCallback = evalConstExpr;
  w.xSelectCallback = 0;
  w.pParse = pParse;
  sqlite3WalkExpr(&w, pExpr);
}

  int (*xBusy)(void*,int),
  void *pArg
){
  sqlite3_mutex_enter(db->mutex);
  db->busyHandler.xFunc = xBusy;
  db->busyHandler.pArg = pArg;
  db->busyHandler.nBusy = 0;
  db->busyTimeout = 0;
  sqlite3_mutex_leave(db->mutex);
  return SQLITE_OK;
}

#ifndef SQLITE_OMIT_PROGRESS_CALLBACK
/*
** This routine sets the progress callback for an Sqlite database to the

/*
** This routine installs a default busy handler that waits for the
** specified number of milliseconds before returning 0.
*/
int sqlite3_busy_timeout(sqlite3 *db, int ms){
  if( ms>0 ){

    sqlite3_busy_handler(db, sqliteDefaultBusyCallback, (void*)db);
    db->busyTimeout = ms;
  }else{
    sqlite3_busy_handler(db, 0, 0);
  }
  return SQLITE_OK;
}

/*

    ** operation N should be 0.  The idea is that a test program (like the
    ** SQL Logic Test or SLT test module) can run the same SQL multiple times
    ** with various optimizations disabled to verify that the same answer
    ** is obtained in every case.
    */
    case SQLITE_TESTCTRL_OPTIMIZATIONS: {
      sqlite3 *db = va_arg(ap, sqlite3*);
      db->dbOptFlags = (u8)(va_arg(ap, int) & 0xff);

      break;
    }

#ifdef SQLITE_N_KEYWORD
    /* sqlite3_test_control(SQLITE_TESTCTRL_ISKEYWORD, const char *zWord)
    **
    ** If zWord is a keyword recognized by the parser, then return the

static int seekAndRead(unixFile *id, sqlite3_int64 offset, void *pBuf, int cnt){
  int got;
  int prior = 0;
#if (!defined(USE_PREAD) && !defined(USE_PREAD64))
  i64 newOffset;
#endif
  TIMER_START;
  assert( cnt==(cnt&0x1ffff) );
  cnt &= 0x1ffff;
  do{
#if defined(USE_PREAD)
    got = osPread(id->h, pBuf, cnt, offset);
    SimulateIOError( got = -1 );
#elif defined(USE_PREAD64)
    got = osPread64(id->h, pBuf, cnt, offset);
    SimulateIOError( got = -1 );

** is set before returning.
*/
static int seekAndWrite(unixFile *id, i64 offset, const void *pBuf, int cnt){
  int got;
#if (!defined(USE_PREAD) && !defined(USE_PREAD64))
  i64 newOffset;
#endif
  assert( cnt==(cnt&0x1ffff) );
  cnt &= 0x1ffff;
  TIMER_START;
#if defined(USE_PREAD)
  do{ got = osPwrite(id->h, pBuf, cnt, offset); }while( got<0 && errno==EINTR );
#elif defined(USE_PREAD64)
  do{ got = osPwrite64(id->h, pBuf, cnt, offset);}while( got<0 && errno==EINTR);
#else
  do{

      if( rc==SQLITE_OK ){
        pPager->dbFileSize = nPage;
      }
    }
  }
  return rc;
}

/*
** Return a sanitized version of the sector-size of OS file pFile. The
** return value is guaranteed to lie between 32 and MAX_SECTOR_SIZE.
*/
int sqlite3SectorSize(sqlite3_file *pFile){
  int iRet = sqlite3OsSectorSize(pFile);
  if( iRet<32 ){
    iRet = 512;
  }else if( iRet>MAX_SECTOR_SIZE ){
    assert( MAX_SECTOR_SIZE>=512 );
    iRet = MAX_SECTOR_SIZE;
  }
  return iRet;
}

/*
** Set the value of the Pager.sectorSize variable for the given
** pager based on the value returned by the xSectorSize method
** of the open database file. The sector size will be used used 
** to determine the size and alignment of journal header and 
** master journal pointers within created journal files.

              SQLITE_IOCAP_POWERSAFE_OVERWRITE)!=0
  ){
    /* Sector size doesn't matter for temporary files. Also, the file
    ** may not have been opened yet, in which case the OsSectorSize()
    ** call will segfault. */
    pPager->sectorSize = 512;
  }else{


    pPager->sectorSize = sqlite3SectorSize(pPager->fd);





  }
}

/*
** Playback the journal and thus restore the database file to
** the state it was in before we started making changes.  
**

** retried. If it returns zero, then the SQLITE_BUSY error is
** returned to the caller of the pager API function.
*/
void sqlite3PagerSetBusyhandler(
  Pager *pPager,                       /* Pager object */
  int (*xBusyHandler)(void *),         /* Pointer to busy-handler function */
  void *pBusyHandlerArg                /* Argument to pass to xBusyHandler */
){
  pPager->xBusyHandler = xBusyHandler;
  pPager->pBusyHandlerArg = pBusyHandlerArg;

  if( isOpen(pPager->fd) ){
    void **ap = (void **)&pPager->xBusyHandler;
    assert( ((int(*)(void *))(ap[0]))==xBusyHandler );
    assert( ap[1]==pBusyHandlerArg );
    sqlite3OsFileControl(pPager->fd, SQLITE_FCNTL_BUSYHANDLER, (void *)ap);
  }
}

/*
** Change the page size used by the Pager object. The new page size 
** is passed in *pPageSize.
**
** If the pager is in the error state when this function is called, it

sqlite3_file *sqlite3PagerFile(Pager*);
const char *sqlite3PagerJournalname(Pager*);
int sqlite3PagerNosync(Pager*);
void *sqlite3PagerTempSpace(Pager*);
int sqlite3PagerIsMemdb(Pager*);
void sqlite3PagerCacheStat(Pager *, int, int, int *);
void sqlite3PagerClearCache(Pager *);
int sqlite3SectorSize(sqlite3_file *);

/* Functions used to truncate the database file. */
void sqlite3PagerTruncateImage(Pager*,Pgno);

#if defined(SQLITE_HAS_CODEC) && !defined(SQLITE_OMIT_WAL)
void *sqlite3PagerCodec(DbPage *);
#endif

  ** connection.  If it returns SQLITE_OK, then assume that the VFS
  ** handled the pragma and generate a no-op prepared statement.
  */
  aFcntl[0] = 0;
  aFcntl[1] = zLeft;
  aFcntl[2] = zRight;
  aFcntl[3] = 0;
  db->busyHandler.nBusy = 0;
  rc = sqlite3_file_control(db, zDb, SQLITE_FCNTL_PRAGMA, (void*)aFcntl);
  if( rc==SQLITE_OK ){
    if( aFcntl[0] ){
      int mem = ++pParse->nMem;
      sqlite3VdbeAddOp4(v, OP_String8, 0, mem, 0, aFcntl[0], 0);
      sqlite3VdbeSetNumCols(v, 1);
      sqlite3VdbeSetColName(v, 0, COLNAME_NAME, "result", SQLITE_STATIC);

  ** This pragma attempts to free as much memory as possible from the
  ** current database connection.
  */
  if( sqlite3StrICmp(zLeft, "shrink_memory")==0 ){
    sqlite3_db_release_memory(db);
  }else

  /*
  **   PRAGMA busy_timeout
  **   PRAGMA busy_timeout = N
  **
  ** Call sqlite3_busy_timeout(db, N).  Return the current timeout value
  ** if one is set.  If no busy handler or a different busy handler is set
  ** then 0 is returned.  Setting the busy_timeout to 0 or negative
  ** disables the timeout.
  */
  if( sqlite3StrICmp(zLeft, "busy_timeout")==0 ){
    if( zRight ){
      sqlite3_busy_timeout(db, sqlite3Atoi(zRight));
    }
    returnSingleInt(pParse, "timeout",  db->busyTimeout);
  }else

#if defined(SQLITE_DEBUG) || defined(SQLITE_TEST)
  /*
  ** Report the current state of file logs for all databases
  */
  if( sqlite3StrICmp(zLeft, "lock_status")==0 ){
    static const char *const azLockName[] = {
      "unlocked", "shared", "reserved", "pending", "exclusive"

  struct SrcList_item *pSubitem;   /* The subquery */
  sqlite3 *db = pParse->db;

  /* Check to see if flattening is permitted.  Return 0 if not.
  */
  assert( p!=0 );
  assert( p->pPrior==0 );  /* Unable to flatten compound queries */
  if( OptimizationDisabled(db, SQLITE_QueryFlattener) ) return 0;
  pSrc = p->pSrc;
  assert( pSrc && iFrom>=0 && iFrom<pSrc->nSrc );
  pSubitem = &pSrc->a[iFrom];
  iParent = pSubitem->iCursor;
  pSub = pSubitem->pSelect;
  assert( pSub!=0 );
  if( isAgg && subqueryIsAgg ) return 0;                 /* Restriction (1)  */

  ** identical, then disable the ORDER BY clause since the GROUP BY
  ** will cause elements to come out in the correct order.  This is
  ** an optimization - the correct answer should result regardless.
  ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER
  ** to disable this optimization for testing purposes.
  */
  if( sqlite3ExprListCompare(p->pGroupBy, pOrderBy)==0
         && OptimizationEnabled(db, SQLITE_GroupByOrder) ){
    pOrderBy = 0;
  }

  /* If the query is DISTINCT with an ORDER BY but is not an aggregate, and 
  ** if the select-list is the same as the ORDER BY list, then this query
  ** can be rewritten as a GROUP BY. In other words, this:
  **

        resetAccumulator(pParse, &sAggInfo);
        pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pMinMax,0,flag,0);
        if( pWInfo==0 ){
          sqlite3ExprListDelete(db, pDel);
          goto select_end;
        }
        updateAccumulator(pParse, &sAggInfo);
        assert( pMinMax==0 || pMinMax->nExpr==1 );
        if( pWInfo->nOBSat>0 ){
          sqlite3VdbeAddOp2(v, OP_Goto, 0, pWInfo->iBreak);
          VdbeComment((v, "%s() by index",
                (flag==WHERE_ORDERBY_MIN?"min":"max")));
        }
        sqlite3WhereEnd(pWInfo);
        finalizeAggFunctions(pParse, &sAggInfo);

** prepared statement.  ^If the [SQLITE_FCNTL_PRAGMA] file control returns
** any result code other than [SQLITE_OK] or [SQLITE_NOTFOUND], that means
** that the VFS encountered an error while handling the [PRAGMA] and the
** compilation of the PRAGMA fails with an error.  ^The [SQLITE_FCNTL_PRAGMA]
** file control occurs at the beginning of pragma statement analysis and so
** it is able to override built-in [PRAGMA] statements.
** </ul>
**
** <li>[[SQLITE_FCNTL_BUSYHANDLER]]
** ^This file-control may be invoked by SQLite on the database file handle
** shortly after it is opened in order to provide a custom VFS with access
** to the connections busy-handler callback. The argument is of type (void **)
** - an array of two (void *) values. The first (void *) actually points
** to a function of type (int (*)(void *)). In order to invoke the connections
** busy-handler, this function should be invoked with the second (void *) in
** the array as the only argument. If it returns non-zero, then the operation
** should be retried. If it returns zero, the custom VFS should abandon the
** current operation.
*/
#define SQLITE_FCNTL_LOCKSTATE               1
#define SQLITE_GET_LOCKPROXYFILE             2
#define SQLITE_SET_LOCKPROXYFILE             3
#define SQLITE_LAST_ERRNO                    4
#define SQLITE_FCNTL_SIZE_HINT               5
#define SQLITE_FCNTL_CHUNK_SIZE              6
#define SQLITE_FCNTL_FILE_POINTER            7
#define SQLITE_FCNTL_SYNC_OMITTED            8
#define SQLITE_FCNTL_WIN32_AV_RETRY          9
#define SQLITE_FCNTL_PERSIST_WAL            10
#define SQLITE_FCNTL_OVERWRITE              11
#define SQLITE_FCNTL_VFSNAME                12
#define SQLITE_FCNTL_POWERSAFE_OVERWRITE    13
#define SQLITE_FCNTL_PRAGMA                 14
#define SQLITE_FCNTL_BUSYHANDLER            15

/*
** CAPI3REF: Mutex Handle
**
** The mutex module within SQLite defines [sqlite3_mutex] to be an
** abstract type for a mutex object.  The SQLite core never looks
** at the internal representation of an [sqlite3_mutex].  It only

  Db *aDb;                      /* All backends */
  int nDb;                      /* Number of backends currently in use */
  int flags;                    /* Miscellaneous flags. See below */
  i64 lastRowid;                /* ROWID of most recent insert (see above) */
  unsigned int openFlags;       /* Flags passed to sqlite3_vfs.xOpen() */
  int errCode;                  /* Most recent error code (SQLITE_*) */
  int errMask;                  /* & result codes with this before returning */
  u8 dbOptFlags;                /* Flags to enable/disable optimizations */
  u8 autoCommit;                /* The auto-commit flag. */
  u8 temp_store;                /* 1: file 2: memory 0: default */
  u8 mallocFailed;              /* True if we have seen a malloc failure */
  u8 dfltLockMode;              /* Default locking-mode for attached dbs */
  signed char nextAutovac;      /* Autovac setting after VACUUM if >=0 */
  u8 suppressErr;               /* Do not issue error messages if true */
  u8 vtabOnConflict;            /* Value to return for s3_vtab_on_conflict() */

** A macro to discover the encoding of a database.
*/
#define ENC(db) ((db)->aDb[0].pSchema->enc)

/*
** Possible values for the sqlite3.flags.
*/
#define SQLITE_VdbeTrace      0x00000001  /* True to trace VDBE execution */
#define SQLITE_InternChanges  0x00000002  /* Uncommitted Hash table changes */
#define SQLITE_FullColNames   0x00000004  /* Show full column names on SELECT */
#define SQLITE_ShortColNames  0x00000008  /* Show short columns names */
#define SQLITE_CountRows      0x00000010  /* Count rows changed by INSERT, */
                                          /*   DELETE, or UPDATE and return */
                                          /*   the count using a callback. */
#define SQLITE_NullCallback   0x00000020  /* Invoke the callback once if the */
                                          /*   result set is empty */
#define SQLITE_SqlTrace       0x00000040  /* Debug print SQL as it executes */
#define SQLITE_VdbeListing    0x00000080  /* Debug listings of VDBE programs */
#define SQLITE_WriteSchema    0x00000100  /* OK to update SQLITE_MASTER */
                         /*   0x00000200  Unused */
#define SQLITE_IgnoreChecks   0x00000400  /* Do not enforce check constraints */
#define SQLITE_ReadUncommitted 0x0000800  /* For shared-cache mode */
#define SQLITE_LegacyFileFmt  0x00001000  /* Create new databases in format 1 */
#define SQLITE_FullFSync      0x00002000  /* Use full fsync on the backend */
#define SQLITE_CkptFullFSync  0x00004000  /* Use full fsync for checkpoint */
#define SQLITE_RecoveryMode   0x00008000  /* Ignore schema errors */
#define SQLITE_ReverseOrder   0x00010000  /* Reverse unordered SELECTs */
#define SQLITE_RecTriggers    0x00020000  /* Enable recursive triggers */
#define SQLITE_ForeignKeys    0x00040000  /* Enforce foreign key constraints  */
#define SQLITE_AutoIndex      0x00080000  /* Enable automatic indexes */
#define SQLITE_PreferBuiltin  0x00100000  /* Preference to built-in funcs */
#define SQLITE_LoadExtension  0x00200000  /* Enable load_extension */
#define SQLITE_EnableTrigger  0x00400000  /* True to enable triggers */

/*
** Bits of the sqlite3.dbOptFlags field that are used by the
** sqlite3_test_control(SQLITE_TESTCTRL_OPTIMIZATIONS,...) interface to
** selectively disable various optimizations.
*/
#define SQLITE_QueryFlattener 0x0001   /* Query flattening */
#define SQLITE_ColumnCache    0x0002   /* Column cache */
#define SQLITE_GroupByOrder   0x0004   /* GROUPBY cover of ORDERBY */
#define SQLITE_FactorOutConst 0x0008   /* Constant factoring */
#define SQLITE_IdxRealAsInt   0x0010   /* Store REAL as INT in indices */
#define SQLITE_DistinctOpt    0x0020   /* DISTINCT using indexes */
#define SQLITE_CoverIdxScan   0x0040   /* Covering index scans */
#define SQLITE_OrderByIdxJoin 0x0080   /* ORDER BY of joins via index */
#define SQLITE_AllOpts        0x00ff   /* All optimizations */

/*
** Macros for testing whether or not optimizations are enabled or disabled.
*/
#ifndef SQLITE_OMIT_BUILTIN_TEST
#define OptimizationDisabled(db, mask)  (((db)->dbOptFlags&(mask))!=0)
#define OptimizationEnabled(db, mask)   (((db)->dbOptFlags&(mask))==0)
#else
#define OptimizationDisabled(db, mask)  0
#define OptimizationEnabled(db, mask)   1
#endif

/*
** Possible values for the sqlite.magic field.
** The numbers are obtained at random and have no special meaning, other
** than being distinct from one another.
*/
#define SQLITE_MAGIC_OPEN     0xa029a697  /* Database is open */

** Within the union, pIdx is only used when wsFlags&WHERE_INDEXED is true.
** pTerm is only used when wsFlags&WHERE_MULTI_OR is true.  And pVtabIdx
** is only used when wsFlags&WHERE_VIRTUALTABLE is true.  It is never the
** case that more than one of these conditions is true.
*/
struct WherePlan {
  u32 wsFlags;                   /* WHERE_* flags that describe the strategy */
  u16 nEq;                       /* Number of == constraints */
  u16 nOBSat;                    /* Number of ORDER BY terms satisfied */
  double nRow;                   /* Estimated number of rows (for EQP) */
  union {
    Index *pIdx;                   /* Index when WHERE_INDEXED is true */
    struct WhereTerm *pTerm;       /* WHERE clause term for OR-search */
    sqlite3_index_info *pVtabIdx;  /* Virtual table index to use */
  } u;
};

#undef TCL_STORAGE_CLASS
#define TCL_STORAGE_CLASS DLLEXPORT
#endif /* BUILD_sqlite */

#define NUM_PREPARED_STMTS 10
#define MAX_PREPARED_STMTS 100

/* Forward declaration */
typedef struct SqliteDb SqliteDb;








/*
** New SQL functions can be created as TCL scripts.  Each such function
** is described by an instance of the following structure.
*/
typedef struct SqlFunc SqlFunc;
struct SqlFunc {
  Tcl_Interp *interp;   /* The TCL interpret to execute the function */
  Tcl_Obj *pScript;     /* The Tcl_Obj representation of the script */
  SqliteDb *pDb;        /* Database connection that owns this function */
  int useEvalObjv;      /* True if it is safe to use Tcl_EvalObjv */
  char *zName;          /* Name of this function */
  SqlFunc *pNext;       /* Next function on the list of them all */
};

/*
** New collation sequences function can be created as TCL scripts.  Each such

** that has been opened by the SQLite TCL interface.
**
** If this module is built with SQLITE_TEST defined (to create the SQLite
** testfixture executable), then it may be configured to use either
** sqlite3_prepare_v2() or sqlite3_prepare() to prepare SQL statements.
** If SqliteDb.bLegacyPrepare is true, sqlite3_prepare() is used.
*/

struct SqliteDb {
  sqlite3 *db;               /* The "real" database structure. MUST BE FIRST */
  Tcl_Interp *interp;        /* The interpreter used for this database */
  char *zBusy;               /* The busy callback routine */
  char *zCommit;             /* The commit hook callback routine */
  char *zTrace;              /* The trace callback routine */
  char *zProfile;            /* The profile callback routine */

  for(p=pDb->pFunc; p; p=p->pNext){ 
    if( strcmp(p->zName, pNew->zName)==0 ){
      Tcl_Free((char*)pNew);
      return p;
    }
  }
  pNew->interp = pDb->interp;
  pNew->pDb = pDb;
  pNew->pScript = 0;
  pNew->pNext = pDb->pFunc;
  pDb->pFunc = pNew;
  return pNew;
}

/*

  SqliteDb *pDb = (SqliteDb*)db;
  flushStmtCache(pDb);
  closeIncrblobChannels(pDb);
  sqlite3_close(pDb->db);
  while( pDb->pFunc ){
    SqlFunc *pFunc = pDb->pFunc;
    pDb->pFunc = pFunc->pNext;
    assert( pFunc->pDb==pDb );
    Tcl_DecrRefCount(pFunc->pScript);
    Tcl_Free((char*)pFunc);
  }
  while( pDb->pCollate ){
    SqlCollate *pCollate = pDb->pCollate;
    pDb->pCollate = pCollate->pNext;
    Tcl_Free((char*)pCollate);

        }
        case SQLITE_FLOAT: {
          double r = sqlite3_value_double(pIn);
          pVal = Tcl_NewDoubleObj(r);
          break;
        }
        case SQLITE_NULL: {
          pVal = Tcl_NewStringObj(p->pDb->zNull, -1);
          break;
        }
        default: {
          int bytes = sqlite3_value_bytes(pIn);
          pVal = Tcl_NewStringObj((char *)sqlite3_value_text(pIn), bytes);
          break;
        }

  }else{
    rc = 999;
  }
  return rc;
}
#endif /* SQLITE_OMIT_AUTHORIZATION */





















/*
** This routine reads a line of text from FILE in, stores
** the text in memory obtained from malloc() and returns a pointer
** to the text.  NULL is returned at end of file, or if malloc()
** fails.
**
** The interface is like "readline" but no command-line editing

  
  /* If no prepared statement was found. Compile the SQL text. Also allocate
  ** a new SqlPreparedStmt structure.  */
  if( pPreStmt==0 ){
    int nByte;

    if( SQLITE_OK!=dbPrepare(pDb, zSql, &pStmt, pzOut) ){
      Tcl_SetObjResult(interp, Tcl_NewStringObj(sqlite3_errmsg(pDb->db), -1));
      return TCL_ERROR;
    }
    if( pStmt==0 ){
      if( SQLITE_OK!=sqlite3_errcode(pDb->db) ){
        /* A compile-time error in the statement. */
        Tcl_SetObjResult(interp, Tcl_NewStringObj(sqlite3_errmsg(pDb->db), -1));
        return TCL_ERROR;
      }else{
        /* The statement was a no-op.  Continue to the next statement
        ** in the SQL string.
        */
        return TCL_OK;
      }

    int nCol;                     /* Number of columns returned by pStmt */
    Tcl_Obj **apColName = 0;      /* Array of column names */

    p->nCol = nCol = sqlite3_column_count(pStmt);
    if( nCol>0 && (papColName || p->pArray) ){
      apColName = (Tcl_Obj**)Tcl_Alloc( sizeof(Tcl_Obj*)*nCol );
      for(i=0; i<nCol; i++){
        apColName[i] = Tcl_NewStringObj(sqlite3_column_name(pStmt,i), -1);
        Tcl_IncrRefCount(apColName[i]);
      }
      p->apColName = apColName;
    }

    /* If results are being stored in an array variable, then create
    ** the array(*) entry for that array

          ** interface, retry prepare()/step() on the same SQL statement.
          ** This only happens once. If there is a second SQLITE_SCHEMA
          ** error, the error will be returned to the caller. */
          p->zSql = zPrevSql;
          continue;
        }
#endif
        Tcl_SetObjResult(pDb->interp,
                         Tcl_NewStringObj(sqlite3_errmsg(pDb->db), -1));
        return TCL_ERROR;
      }else{
        dbReleaseStmt(pDb, pPreStmt, 0);
      }
    }
  }

        return Tcl_NewWideIntObj(v);
      }
    }
    case SQLITE_FLOAT: {
      return Tcl_NewDoubleObj(sqlite3_column_double(pStmt, iCol));
    }
    case SQLITE_NULL: {
      return Tcl_NewStringObj(p->pDb->zNull, -1);
    }
  }

  return Tcl_NewStringObj((char*)sqlite3_column_text(pStmt, iCol), -1);
}

/*
** If using Tcl version 8.6 or greater, use the NR functions to avoid
** recursive evalution of scripts by the [db eval] and [db trans]
** commands. Even if the headers used while compiling the extension
** are 8.6 or newer, the code still tests the Tcl version at runtime.

    Tcl_AppendResult(interp, "incrblob not available in this build", 0);
    return TCL_ERROR;
#else
    int isReadonly = 0;
    const char *zDb = "main";
    const char *zTable;
    const char *zColumn;
    Tcl_WideInt iRow;

    /* Check for the -readonly option */
    if( objc>3 && strcmp(Tcl_GetString(objv[2]), "-readonly")==0 ){
      isReadonly = 1;
    }

    if( objc!=(5+isReadonly) && objc!=(6+isReadonly) ){

        pDb->zNull = Tcl_Alloc( len + 1 );
        memcpy(pDb->zNull, zNull, len);
        pDb->zNull[len] = '\0';
      }else{
        pDb->zNull = 0;
      }
    }
    Tcl_SetObjResult(interp, Tcl_NewStringObj(pDb->zNull, -1));
    break;
  }

  /*
  **     $db last_insert_rowid 
  **
  ** Return an integer which is the ROWID for the most recent insert.

  void * clientData,
  Tcl_Interp *interp,
  int objc,
  Tcl_Obj *CONST objv[]
){
  sqlite3_stmt *pStmt;
  int idx;
  Tcl_WideInt value;
  int rc;

  if( objc!=4 ){
    Tcl_AppendResult(interp, "wrong # args: should be \"",
        Tcl_GetStringFromObj(objv[0], 0), " STMT N VALUE", 0);
    return TCL_ERROR;
  }

static int test_soft_heap_limit(
  void * clientData,
  Tcl_Interp *interp,
  int objc,
  Tcl_Obj *CONST objv[]
){
  sqlite3_int64 amt;
  Tcl_WideInt N = -1;
  if( objc!=1 && objc!=2 ){
    Tcl_WrongNumArgs(interp, 1, objv, "?N?");
    return TCL_ERROR;
  }
  if( objc==2 ){
    if( Tcl_GetWideIntFromObj(interp, objv[1], &N) ) return TCL_ERROR;
  }

*/
static int file_control_sizehint_test(
  ClientData clientData, /* Pointer to sqlite3_enable_XXX function */
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int objc,              /* Number of arguments */
  Tcl_Obj *CONST objv[]  /* Command arguments */
){
  Tcl_WideInt nSize;              /* Hinted size */
  char *zDb;                      /* Db name ("main", "temp" etc.) */
  sqlite3 *db;                    /* Database handle */
  int rc;                         /* file_control() return code */

  if( objc!=4 ){
    Tcl_WrongNumArgs(interp, 1, objv, "DB DBNAME SIZE");
    return TCL_ERROR;

  const char *zOpt;
  int onoff;
  int mask = 0;
  static const struct {
    const char *zOptName;
    int mask;
  } aOpt[] = {
    { "all",              SQLITE_AllOpts        },
    { "query-flattener",  SQLITE_QueryFlattener },
    { "column-cache",     SQLITE_ColumnCache    },
    { "groupby-order",    SQLITE_GroupByOrder   },
    { "factor-constants", SQLITE_FactorOutConst },
    { "real-as-int",      SQLITE_IdxRealAsInt   },
    { "distinct-opt",     SQLITE_DistinctOpt    },
    { "cover-idx-scan",   SQLITE_CoverIdxScan   },
    { "order-by-idx-join",SQLITE_OrderByIdxJoin },
  };

  if( objc!=4 ){
    Tcl_WrongNumArgs(interp, 1, objv, "DB OPT BOOLEAN");
    return TCL_ERROR;
  }
  if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR;

#ifndef SQLITE_OMIT_VIRTUALTABLE
  a = sqlite3_malloc( sizeof(a[0])*n );
  if( a==0 ){
    Tcl_AppendResult(interp, "SQLITE_NOMEM", (char*)0);
    return TCL_ERROR;
  }
  for(i=0; i<n; i++){
    Tcl_WideInt x = 0;
    Tcl_GetWideIntFromObj(0, objv[i+2], &x);
    a[i] = x;
  }
  rc = sqlite3_intarray_bind(pArray, n, a, sqlite3_free);
  if( rc!=SQLITE_OK ){
    Tcl_AppendResult(interp, sqlite3TestErrorName(rc), (char*)0);
    return TCL_ERROR;
  }
#endif

    pFile = 0;
  }
  rc = fwrite(pBuf, size, nmemb, p->f);

  /* If the write was incomplete, adjust the file size and group size
  ** downward */
  if( rc<nmemb && pFile ){
    size_t nWritten = rc;
    sqlite3_int64 iNewEnd = iOfst + size*nWritten;
    if( iNewEnd<iEnd ) iNewEnd = iEnd;
    quotaEnter();
    pFile->pGroup->iSize += iNewEnd - pFile->iSize;
    pFile->iSize = iNewEnd;
    quotaLeave();
  }

  Tcl_IncrRefCount(pEval);
  Tcl_ListObjAppendElement(0, pEval, Tcl_NewStringObj(zFilename, -1));
  Tcl_ListObjAppendElement(0, pEval, pVarname);
  Tcl_ListObjAppendElement(0, pEval, Tcl_NewWideIntObj(iSize));
  rc = Tcl_EvalObjEx(p->interp, pEval, TCL_EVAL_GLOBAL);

  if( rc==TCL_OK ){
    Tcl_WideInt x;
    Tcl_Obj *pLimit = Tcl_ObjGetVar2(p->interp, pVarname, 0, 0);
    rc = Tcl_GetWideIntFromObj(p->interp, pLimit, &x);
    *piLimit = x;
    Tcl_UnsetVar(p->interp, Tcl_GetString(pVarname), 0);
  }

  Tcl_DecrRefCount(pEval);
  Tcl_DecrRefCount(pVarname);
  if( rc!=TCL_OK ) Tcl_BackgroundError(p->interp);
}

static int test_quota_set(
  void * clientData,
  Tcl_Interp *interp,
  int objc,
  Tcl_Obj *CONST objv[]
){
  const char *zPattern;           /* File pattern to configure */
  Tcl_WideInt iLimit;             /* Initial quota in bytes */
  Tcl_Obj *pScript;               /* Tcl script to invoke to increase quota */
  int rc;                         /* Value returned by quota_set() */
  TclQuotaCallback *p;            /* Callback object */
  int nScript;                    /* Length of callback script */
  void (*xDestroy)(void*);        /* Optional destructor for pArg */
  void (*xCallback)(const char *, sqlite3_int64 *, sqlite3_int64, void *);

  if( Tcl_GetIntFromObj(interp, objv[3], &nElem) ) return TCL_ERROR;
  zBuf = (char*)sqlite3_malloc( sz*nElem + 1 );
  if( zBuf==0 ){
    Tcl_SetResult(interp, "out of memory", TCL_STATIC);
    return TCL_ERROR;
  }
  got = sqlite3_quota_fread(zBuf, sz, nElem, p);

  zBuf[got*sz] = 0;
  Tcl_SetResult(interp, zBuf, TCL_VOLATILE);
  sqlite3_free(zBuf);
  return TCL_OK;
}

/*

  ** final frame is repeated (with its commit mark) until the next sector
  ** boundary is crossed.  Only the part of the WAL prior to the last
  ** sector boundary is synced; the part of the last frame that extends
  ** past the sector boundary is written after the sync.
  */
  if( isCommit && (sync_flags & WAL_SYNC_TRANSACTIONS)!=0 ){
    if( pWal->padToSectorBoundary ){
      int sectorSize = sqlite3SectorSize(pWal->pWalFd);
      w.iSyncPoint = ((iOffset+sectorSize-1)/sectorSize)*sectorSize;
      while( iOffset<w.iSyncPoint ){
        rc = walWriteOneFrame(&w, pLast, nTruncate, iOffset);
        if( rc ) return rc;
        iOffset += szFrame;
        nExtra++;
      }

#define WHERE_COLUMN_NULL  0x00080000  /* x IS NULL */
#define WHERE_INDEXED      0x000f0000  /* Anything that uses an index */
#define WHERE_NOT_FULLSCAN 0x100f3000  /* Does not do a full table scan */
#define WHERE_IN_ABLE      0x000f1000  /* Able to support an IN operator */
#define WHERE_TOP_LIMIT    0x00100000  /* x<EXPR or x<=EXPR constraint */
#define WHERE_BTM_LIMIT    0x00200000  /* x>EXPR or x>=EXPR constraint */
#define WHERE_BOTH_LIMIT   0x00300000  /* Both x>EXPR and x<EXPR */
#define WHERE_IDX_ONLY     0x00400000  /* Use index only - omit table */
#define WHERE_ORDERED      0x00800000  /* Output will appear in correct order */
#define WHERE_REVERSE      0x01000000  /* Scan in reverse order */
#define WHERE_UNIQUE       0x02000000  /* Selects no more than one row */
#define WHERE_ALL_UNIQUE   0x04000000  /* This and all prior have one row */
#define WHERE_VIRTUALTABLE 0x08000000  /* Use virtual-table processing */
#define WHERE_MULTI_OR     0x10000000  /* OR using multiple indices */
#define WHERE_TEMP_INDEX   0x20000000  /* Uses an ephemeral index */
#define WHERE_DISTINCT     0x40000000  /* Correct order for DISTINCT */
#define WHERE_COVER_SCAN   0x80000000  /* Full scan of a covering index */

/*
** This module contains many separate subroutines that work together to
** find the best indices to use for accessing a particular table in a query.
** An instance of the following structure holds context information about the
** index search so that it can be more easily passed between the various
** routines.
*/
typedef struct WhereBestIdx WhereBestIdx;
struct WhereBestIdx {
  Parse *pParse;                  /* Parser context */
  WhereClause *pWC;               /* The WHERE clause */
  struct SrcList_item *pSrc;      /* The FROM clause term to search */
  Bitmask notReady;               /* Mask of cursors not available */
  Bitmask notValid;               /* Cursors not available for any purpose */
  ExprList *pOrderBy;             /* The ORDER BY clause */
  ExprList *pDistinct;            /* The select-list if query is DISTINCT */
  sqlite3_index_info **ppIdxInfo; /* Index information passed to xBestIndex */
  int i, n;                       /* Which loop is being coded; # of loops */
  WhereLevel *aLevel;             /* Info about outer loops */
  WhereCost cost;                 /* Lowest cost query plan */
};

/*
** Return TRUE if the probe cost is less than the baseline cost
*/
static int compareCost(const WhereCost *pProbe, const WhereCost *pBaseline){
  if( pProbe->rCost<pBaseline->rCost ) return 1;
  if( pProbe->rCost>pBaseline->rCost ) return 0;
  if( pProbe->plan.nOBSat>pBaseline->plan.nOBSat ) return 1;
  if( pProbe->plan.nRow<pBaseline->plan.nRow ) return 1;
  return 0;
}

/*
** Initialize a preallocated WhereClause structure.
*/
static void whereClauseInit(
  WhereClause *pWC,        /* The WhereClause to be initialized */
  Parse *pParse,           /* The parsing context */

  /* Prevent ON clause terms of a LEFT JOIN from being used to drive
  ** an index for tables to the left of the join.
  */
  pTerm->prereqRight |= extraRight;
}

/*
** Return TRUE if the given index is UNIQUE and all columns past the
** first nSkip columns are NOT NULL.
*/
static int indexIsUniqueNotNull(Index *pIdx, int nSkip){
  Table *pTab = pIdx->pTable;


  int i;
  if( pIdx->onError==OE_None ) return 0;
  for(i=nSkip; i<pIdx->nColumn; i++){

    int j = pIdx->aiColumn[i];
    assert( j>=0 && j<pTab->nCol );

    if( pTab->aCol[j].notNull==0 ) return 0;
  }

  return 1;
}

/*
** This function searches the expression list passed as the second argument
** for an expression of type TK_COLUMN that refers to the same column and
** uses the same collation sequence as the iCol'th column of index pIdx.
** Argument iBase is the cursor number used for the table that pIdx refers

  int base,                       /* Cursor number for the table pIdx is on */
  ExprList *pDistinct,            /* The DISTINCT expressions */
  int nEqCol                      /* Number of index columns with == */
){
  Bitmask mask = 0;               /* Mask of unaccounted for pDistinct exprs */
  int i;                          /* Iterator variable */

  assert( pDistinct!=0 );
  if( pIdx->zName==0 || pDistinct->nExpr>=BMS ) return 0;
  testcase( pDistinct->nExpr==BMS-1 );

  /* Loop through all the expressions in the distinct list. If any of them
  ** are not simple column references, return early. Otherwise, test if the
  ** WHERE clause contains a "col=X" clause. If it does, the expression
  ** can be ignored. If it does not, and the column does not belong to the
  ** same table as index pIdx, return early. Finally, if there is no

      return 1;
    }
  }

  return 0;
}
































































































































































/*
** Prepare a crude estimate of the logarithm of the input value.
** The results need not be exact.  This is only used for estimating
** the total cost of performing operations with O(logN) or O(NlogN)
** complexity.  Because N is just a guess, it is no great tragedy if
** logN is a little off.
*/

#define TRACE_IDX_INPUTS(A)
#define TRACE_IDX_OUTPUTS(A)
#endif

/* 
** Required because bestIndex() is called by bestOrClauseIndex() 
*/
static void bestIndex(WhereBestIdx*);



/*
** This routine attempts to find an scanning strategy that can be used 
** to optimize an 'OR' expression that is part of a WHERE clause. 
**
** The table associated with FROM clause term pSrc may be either a
** regular B-Tree table or a virtual table.
*/
static void bestOrClauseIndex(WhereBestIdx *p){








#ifndef SQLITE_OMIT_OR_OPTIMIZATION
  WhereClause *pWC = p->pWC;           /* The WHERE clause */
  struct SrcList_item *pSrc = p->pSrc; /* The FROM clause term to search */
  const int iCur = pSrc->iCursor;      /* The cursor of the table  */
  const Bitmask maskSrc = getMask(pWC->pMaskSet, iCur);  /* Bitmask for pSrc */
  WhereTerm * const pWCEnd = &pWC->a[pWC->nTerm];        /* End of pWC->a[] */
  WhereTerm *pTerm;                    /* A single term of the WHERE clause */

  /* The OR-clause optimization is disallowed if the INDEXED BY or
  ** NOT INDEXED clauses are used or if the WHERE_AND_ONLY bit is set. */
  if( pSrc->notIndexed || pSrc->pIndex!=0 ){
    return;
  }
  if( pWC->wctrlFlags & WHERE_AND_ONLY ){
    return;
  }

  /* Search the WHERE clause terms for a usable WO_OR term. */
  for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
    if( pTerm->eOperator==WO_OR 
     && ((pTerm->prereqAll & ~maskSrc) & p->notReady)==0
     && (pTerm->u.pOrInfo->indexable & maskSrc)!=0 
    ){
      WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
      WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
      WhereTerm *pOrTerm;
      int flags = WHERE_MULTI_OR;
      double rTotal = 0;
      double nRow = 0;
      Bitmask used = 0;
      WhereBestIdx sBOI;

      sBOI = *p;
      sBOI.pOrderBy = 0;
      sBOI.pDistinct = 0;
      sBOI.ppIdxInfo = 0;
      for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){

        WHERETRACE(("... Multi-index OR testing for term %d of %d....\n", 
          (pOrTerm - pOrWC->a), (pTerm - pWC->a)
        ));
        if( pOrTerm->eOperator==WO_AND ){
          sBOI.pWC = &pOrTerm->u.pAndInfo->wc;
          bestIndex(&sBOI);
        }else if( pOrTerm->leftCursor==iCur ){
          WhereClause tempWC;
          tempWC.pParse = pWC->pParse;
          tempWC.pMaskSet = pWC->pMaskSet;
          tempWC.pOuter = pWC;
          tempWC.op = TK_AND;
          tempWC.a = pOrTerm;
          tempWC.wctrlFlags = 0;
          tempWC.nTerm = 1;
          sBOI.pWC = &tempWC;
          bestIndex(&sBOI);
        }else{
          continue;
        }
        rTotal += sBOI.cost.rCost;
        nRow += sBOI.cost.plan.nRow;
        used |= sBOI.cost.used;
        if( rTotal>=p->cost.rCost ) break;
      }

      /* If there is an ORDER BY clause, increase the scan cost to account 
      ** for the cost of the sort. */
      if( p->pOrderBy!=0 ){
        WHERETRACE(("... sorting increases OR cost %.9g to %.9g\n",
                    rTotal, rTotal+nRow*estLog(nRow)));
        rTotal += nRow*estLog(nRow);
      }

      /* If the cost of scanning using this OR term for optimization is
      ** less than the current cost stored in pCost, replace the contents
      ** of pCost. */
      WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n", rTotal, nRow));
      if( rTotal<p->cost.rCost ){
        p->cost.rCost = rTotal;
        p->cost.used = used;
        p->cost.plan.nRow = nRow;
        p->cost.plan.nOBSat = p->i ? p->aLevel[p->i-1].plan.nOBSat : 0;
        p->cost.plan.wsFlags = flags;
        p->cost.plan.u.pTerm = pTerm;
      }
    }
  }
#endif /* SQLITE_OMIT_OR_OPTIMIZATION */
}

#ifndef SQLITE_OMIT_AUTOMATIC_INDEX

** If the query plan for pSrc specified in pCost is a full table scan
** and indexing is allows (if there is no NOT INDEXED clause) and it
** possible to construct a transient index that would perform better
** than a full table scan even when the cost of constructing the index
** is taken into account, then alter the query plan to use the
** transient index.
*/
static void bestAutomaticIndex(WhereBestIdx *p){
  Parse *pParse = p->pParse;            /* The parsing context */
  WhereClause *pWC = p->pWC;            /* The WHERE clause */
  struct SrcList_item *pSrc = p->pSrc;  /* The FROM clause term to search */



  double nTableRow;                     /* Rows in the input table */
  double logN;                          /* log(nTableRow) */
  double costTempIdx;         /* per-query cost of the transient index */
  WhereTerm *pTerm;           /* A single term of the WHERE clause */
  WhereTerm *pWCEnd;          /* End of pWC->a[] */
  Table *pTable;              /* Table tht might be indexed */

  if( pParse->nQueryLoop<=(double)1 ){
    /* There is no point in building an automatic index for a single scan */
    return;
  }
  if( (pParse->db->flags & SQLITE_AutoIndex)==0 ){
    /* Automatic indices are disabled at run-time */
    return;
  }
  if( (p->cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0 ){
    /* We already have some kind of index in use for this query. */
    return;
  }
  if( pSrc->notIndexed ){
    /* The NOT INDEXED clause appears in the SQL. */
    return;
  }
  if( pSrc->isCorrelated ){
    /* The source is a correlated sub-query. No point in indexing it. */
    return;
  }

  assert( pParse->nQueryLoop >= (double)1 );
  pTable = pSrc->pTab;
  nTableRow = pTable->nRowEst;
  logN = estLog(nTableRow);
  costTempIdx = 2*logN*(nTableRow/pParse->nQueryLoop + 1);
  if( costTempIdx>=p->cost.rCost ){
    /* The cost of creating the transient table would be greater than
    ** doing the full table scan */
    return;
  }

  /* Search for any equality comparison term */
  pWCEnd = &pWC->a[pWC->nTerm];
  for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
    if( termCanDriveIndex(pTerm, pSrc, p->notReady) ){
      WHERETRACE(("auto-index reduces cost from %.1f to %.1f\n",
                    p->cost.rCost, costTempIdx));
      p->cost.rCost = costTempIdx;
      p->cost.plan.nRow = logN + 1;
      p->cost.plan.wsFlags = WHERE_TEMP_INDEX;
      p->cost.used = pTerm->prereqRight;
      break;
    }
  }
}
#else
# define bestAutomaticIndex(A)  /* no-op */
#endif /* SQLITE_OMIT_AUTOMATIC_INDEX */


#ifndef SQLITE_OMIT_AUTOMATIC_INDEX
/*
** Generate code to construct the Index object for an automatic index
** and to set up the WhereLevel object pLevel so that the code generator

#ifndef SQLITE_OMIT_VIRTUALTABLE
/*
** Allocate and populate an sqlite3_index_info structure. It is the 
** responsibility of the caller to eventually release the structure
** by passing the pointer returned by this function to sqlite3_free().
*/
static sqlite3_index_info *allocateIndexInfo(WhereBestIdx *p){
  Parse *pParse = p->pParse; 
  WhereClause *pWC = p->pWC;
  struct SrcList_item *pSrc = p->pSrc;
  ExprList *pOrderBy = p->pOrderBy;

  int i, j;
  int nTerm;
  struct sqlite3_index_constraint *pIdxCons;
  struct sqlite3_index_orderby *pIdxOrderBy;
  struct sqlite3_index_constraint_usage *pUsage;
  WhereTerm *pTerm;
  int nOrderBy;

  /* If the ORDER BY clause contains only columns in the current 
  ** virtual table then allocate space for the aOrderBy part of
  ** the sqlite3_index_info structure.
  */
  nOrderBy = 0;
  if( pOrderBy ){
    int n = pOrderBy->nExpr;
    for(i=0; i<n; i++){
      Expr *pExpr = pOrderBy->a[i].pExpr;
      if( pExpr->op!=TK_COLUMN || pExpr->iTable!=pSrc->iCursor ) break;
    }
    if( i==n){
      nOrderBy = n;
    }
  }

  /* Allocate the sqlite3_index_info structure
  */
  pIdxInfo = sqlite3DbMallocZero(pParse->db, sizeof(*pIdxInfo)
                           + (sizeof(*pIdxCons) + sizeof(*pUsage))*nTerm

** same virtual table.  The sqlite3_index_info structure is created
** and initialized on the first invocation and reused on all subsequent
** invocations.  The sqlite3_index_info structure is also used when
** code is generated to access the virtual table.  The whereInfoDelete() 
** routine takes care of freeing the sqlite3_index_info structure after
** everybody has finished with it.
*/
static void bestVirtualIndex(WhereBestIdx *p){
  Parse *pParse = p->pParse;      /* The parsing context */
  WhereClause *pWC = p->pWC;      /* The WHERE clause */
  struct SrcList_item *pSrc = p->pSrc; /* The FROM clause term to search */






  Table *pTab = pSrc->pTab;
  sqlite3_index_info *pIdxInfo;
  struct sqlite3_index_constraint *pIdxCons;
  struct sqlite3_index_constraint_usage *pUsage;
  WhereTerm *pTerm;
  int i, j;
  int nOrderBy;
  double rCost;

  /* Make sure wsFlags is initialized to some sane value. Otherwise, if the 
  ** malloc in allocateIndexInfo() fails and this function returns leaving
  ** wsFlags in an uninitialized state, the caller may behave unpredictably.
  */
  memset(&p->cost, 0, sizeof(p->cost));
  p->cost.plan.wsFlags = WHERE_VIRTUALTABLE;

  /* If the sqlite3_index_info structure has not been previously
  ** allocated and initialized, then allocate and initialize it now.
  */
  pIdxInfo = *p->ppIdxInfo;
  if( pIdxInfo==0 ){
    *p->ppIdxInfo = pIdxInfo = allocateIndexInfo(p);
  }
  if( pIdxInfo==0 ){
    return;
  }

  /* At this point, the sqlite3_index_info structure that pIdxInfo points
  ** to will have been initialized, either during the current invocation or

  ** each time.
  */
  pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
  pUsage = pIdxInfo->aConstraintUsage;
  for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
    j = pIdxCons->iTermOffset;
    pTerm = &pWC->a[j];
    pIdxCons->usable = (pTerm->prereqRight&p->notReady) ? 0 : 1;
  }
  memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
  if( pIdxInfo->needToFreeIdxStr ){
    sqlite3_free(pIdxInfo->idxStr);
  }
  pIdxInfo->idxStr = 0;
  pIdxInfo->idxNum = 0;
  pIdxInfo->needToFreeIdxStr = 0;
  pIdxInfo->orderByConsumed = 0;
  /* ((double)2) In case of SQLITE_OMIT_FLOATING_POINT... */
  pIdxInfo->estimatedCost = SQLITE_BIG_DBL / ((double)2);
  nOrderBy = pIdxInfo->nOrderBy;
  if( !p->pOrderBy ){
    pIdxInfo->nOrderBy = 0;
  }

  if( vtabBestIndex(pParse, pTab, pIdxInfo) ){
    return;
  }

  pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
  for(i=0; i<pIdxInfo->nConstraint; i++){
    if( pUsage[i].argvIndex>0 ){
      p->cost.used |= pWC->a[pIdxCons[i].iTermOffset].prereqRight;
    }
  }

  /* If there is an ORDER BY clause, and the selected virtual table index
  ** does not satisfy it, increase the cost of the scan accordingly. This
  ** matches the processing for non-virtual tables in bestBtreeIndex().
  */
  rCost = pIdxInfo->estimatedCost;
  if( p->pOrderBy && pIdxInfo->orderByConsumed==0 ){
    rCost += estLog(rCost)*rCost;
  }

  /* The cost is not allowed to be larger than SQLITE_BIG_DBL (the
  ** inital value of lowestCost in this loop. If it is, then the
  ** (cost<lowestCost) test below will never be true.
  ** 
  ** Use "(double)2" instead of "2.0" in case OMIT_FLOATING_POINT 
  ** is defined.
  */
  if( (SQLITE_BIG_DBL/((double)2))<rCost ){
    p->cost.rCost = (SQLITE_BIG_DBL/((double)2));
  }else{
    p->cost.rCost = rCost;
  }
  p->cost.plan.u.pVtabIdx = pIdxInfo;
  if( pIdxInfo->orderByConsumed ){
    p->cost.plan.wsFlags |= WHERE_ORDERED;
    p->cost.plan.nOBSat = nOrderBy;
  }else{
    p->cost.plan.nOBSat = p->i ? p->aLevel[p->i-1].plan.nOBSat : 0;
  }
  p->cost.plan.nEq = 0;
  pIdxInfo->nOrderBy = nOrderBy;

  /* Try to find a more efficient access pattern by using multiple indexes
  ** to optimize an OR expression within the WHERE clause. 
  */
  bestOrClauseIndex(p);
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

#ifdef SQLITE_ENABLE_STAT3
/*
** Estimate the location of a particular key among all keys in an
** index.  Store the results in aStat as follows:

    *pnRow = nRowEst;
    WHERETRACE(("IN row estimate: est=%g\n", nRowEst));
  }
  return rc;
}
#endif /* defined(SQLITE_ENABLE_STAT3) */

/*
** Check to see if column iCol of the table with cursor iTab will appear
** in sorted order according to the current query plan.  Return true if
** it will and false if not.  
**
** If *pbRev is initially 2 (meaning "unknown") then set *pbRev to the
** sort order of iTab.iCol.  If *pbRev is 0 or 1 but does not match
** the sort order of iTab.iCol, then consider the column to be unordered.
*/
static int isOrderedColumn(WhereBestIdx *p, int iTab, int iCol, int *pbRev){
  int i, j;
  WhereLevel *pLevel = &p->aLevel[p->i-1];
  Index *pIdx;
  u8 sortOrder;
  for(i=p->i-1; i>=0; i--, pLevel--){
    if( pLevel->iTabCur!=iTab ) continue;
    if( (pLevel->plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){
      return 1;
    }
    if( (pLevel->plan.wsFlags & WHERE_ORDERED)==0 ){
      return 0;
    }
    if( (pIdx = pLevel->plan.u.pIdx)!=0 ){
      if( iCol<0 ){
        sortOrder = 0;
        testcase( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 );
      }else{
        int n = pIdx->nColumn;
        for(j=0; j<n; j++){
          if( iCol==pIdx->aiColumn[j] ) break;
        }
        if( j>=n ) return 0;
        sortOrder = pIdx->aSortOrder[j];
        testcase( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 );
      }
    }else{
      if( iCol!=(-1) ) return 0;
      sortOrder = 0;
      testcase( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 );
    }
    if( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 ){
      assert( sortOrder==0 || sortOrder==1 );
      testcase( sortOrder==1 );
      sortOrder = 1 - sortOrder;
    }
    if( *pbRev==2 ){
      *pbRev = sortOrder;
      return 1;
    }
    return (*pbRev==sortOrder);
  }
  return 0;
}

/*
** pTerm is an == constraint.  Check to see if the other side of
** the == is a constant or a value that is guaranteed to be ordered
** by outer loops.  Return 1 if pTerm is ordered, and 0 if not.
*/
static int isOrderedTerm(WhereBestIdx *p, WhereTerm *pTerm, int *pbRev){
  Expr *pExpr = pTerm->pExpr;
  assert( pExpr->op==TK_EQ );
  assert( pExpr->pLeft!=0 && pExpr->pLeft->op==TK_COLUMN );
  assert( pExpr->pRight!=0 );
  if( pTerm->prereqRight==0 ){
    return 1;  /* RHS of the == is a constant */
  }
  if( pExpr->pRight->op==TK_COLUMN 
   && isOrderedColumn(p, pExpr->pRight->iTable, pExpr->pRight->iColumn, pbRev)
  ){
    return 1;
  }

  /* If we cannot prove that the constraint is ordered, assume it is not */
  return 0;
}

/*
** This routine decides if pIdx can be used to satisfy the ORDER BY
** clause, either in whole or in part.  The return value is the 
** cumulative number of terms in the ORDER BY clause that are satisfied
** by the index pIdx and other indices in outer loops.
**
** The table being queried has a cursor number of "base".  pIdx is the
** index that is postulated for use to access the table.
**
** nEqCol is the number of columns of pIdx that are used as equality
** constraints and where the other side of the == is an ordered column
** or constant.  An "order column" in the previous sentence means a column
** in table from an outer loop whose values will always appear in the 
** correct order due to othre index, or because the outer loop generates
** a unique result.  Any of the first nEqCol columns of pIdx may be missing
** from the ORDER BY clause and the match can still be a success.
**
** The *pbRev value is set to 0 order 1 depending on whether or not
** pIdx should be run in the forward order or in reverse order.
*/
static int isSortingIndex(
  WhereBestIdx *p,    /* Best index search context */
  Index *pIdx,        /* The index we are testing */
  int base,           /* Cursor number for the table to be sorted */
  int nEqCol,         /* Number of index columns with ordered == constraints */
  int wsFlags,        /* Index usages flags */
  int bOuterRev,      /* True if outer loops scan in reverse order */
  int *pbRev          /* Set to 1 for reverse-order scan of pIdx */
){
  int i;                        /* Number of pIdx terms used */
  int j;                        /* Number of ORDER BY terms satisfied */
  int sortOrder = 0;            /* XOR of index and ORDER BY sort direction */
  int nTerm;                    /* Number of ORDER BY terms */
  struct ExprList_item *pTerm;  /* A term of the ORDER BY clause */
  ExprList *pOrderBy;           /* The ORDER BY clause */
  Parse *pParse = p->pParse;    /* Parser context */
  sqlite3 *db = pParse->db;     /* Database connection */
  int nPriorSat;                /* ORDER BY terms satisfied by outer loops */
  int seenRowid = 0;            /* True if an ORDER BY rowid term is seen */
  int nEqOneRow;                /* Idx columns that ref unique values */

  if( p->i==0 ){
    nPriorSat = 0;
  }else{
    nPriorSat = p->aLevel[p->i-1].plan.nOBSat;
    if( OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return nPriorSat;
  }
  if( nEqCol==0 ){
    if( p->i && (p->aLevel[p->i-1].plan.wsFlags & WHERE_ORDERED)==0 ){
      return nPriorSat;
    }
    nEqOneRow = 0;
  }else if( p->i==0 || (p->aLevel[p->i-1].plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){
    nEqOneRow = nEqCol;
  }else{
    sortOrder = bOuterRev;
    nEqOneRow = -1;
  }
  pOrderBy = p->pOrderBy;
  assert( pOrderBy!=0 );
  if( wsFlags & WHERE_COLUMN_IN ) return nPriorSat;
  if( pIdx->bUnordered ) return nPriorSat;
  nTerm = pOrderBy->nExpr;
  assert( nTerm>0 );

  /* Argument pIdx must either point to a 'real' named index structure, 
  ** or an index structure allocated on the stack by bestBtreeIndex() to
  ** represent the rowid index that is part of every table.  */
  assert( pIdx->zName || (pIdx->nColumn==1 && pIdx->aiColumn[0]==-1) );

  /* Match terms of the ORDER BY clause against columns of
  ** the index.
  **
  ** Note that indices have pIdx->nColumn regular columns plus
  ** one additional column containing the rowid.  The rowid column
  ** of the index is also allowed to match against the ORDER BY
  ** clause.
  */
  for(i=0,j=nPriorSat,pTerm=&pOrderBy->a[j]; j<nTerm; i++){
    Expr *pExpr;       /* The expression of the ORDER BY pTerm */
    CollSeq *pColl;    /* The collating sequence of pExpr */
    int termSortOrder; /* Sort order for this term */
    int iColumn;       /* The i-th column of the index.  -1 for rowid */
    int iSortOrder;    /* 1 for DESC, 0 for ASC on the i-th index term */
    const char *zColl; /* Name of the collating sequence for i-th index term */

    assert( i<=pIdx->nColumn );
    pExpr = pTerm->pExpr;
    if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){
      /* Can not use an index sort on anything that is not a column in the
      ** left-most table of the FROM clause */
      break;
    }
    pColl = sqlite3ExprCollSeq(pParse, pExpr);
    if( !pColl ){
      pColl = db->pDfltColl;
    }
    if( pIdx->zName && i<pIdx->nColumn ){
      iColumn = pIdx->aiColumn[i];
      if( iColumn==pIdx->pTable->iPKey ){
        iColumn = -1;
      }
      iSortOrder = pIdx->aSortOrder[i];
      zColl = pIdx->azColl[i];
    }else{
      iColumn = -1;
      iSortOrder = 0;
      zColl = pColl->zName;
    }
    if( pExpr->iColumn!=iColumn || sqlite3StrICmp(pColl->zName, zColl) ){
      /* Term j of the ORDER BY clause does not match column i of the index */
      if( i<nEqCol ){
        /* If an index column that is constrained by == fails to match an
        ** ORDER BY term, that is OK.  Just ignore that column of the index
        */
        continue;
      }else if( i==pIdx->nColumn ){
        /* Index column i is the rowid.  All other terms match. */
        break;
      }else{
        /* If an index column fails to match and is not constrained by ==
        ** then the index cannot satisfy the ORDER BY constraint.
        */
        return nPriorSat;
      }
    }
    assert( pIdx->aSortOrder!=0 || iColumn==-1 );
    assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 );
    assert( iSortOrder==0 || iSortOrder==1 );
    termSortOrder = iSortOrder ^ pTerm->sortOrder;
    if( i>nEqOneRow ){
      if( termSortOrder!=sortOrder ){
        /* Indices can only be used if all ORDER BY terms past the
        ** equality constraints have the correct DESC or ASC. */
        break;
      }
    }else{
      sortOrder = termSortOrder;
    }
    j++;
    pTerm++;
    if( iColumn<0 ){
      seenRowid = 1;
      break;
    }
  }
  *pbRev = sortOrder;

  /* If there was an "ORDER BY rowid" term that matched, or it is only
  ** possible for a single row from this table to match, then skip over
  ** any additional ORDER BY terms dealing with this table.
  */
  if( seenRowid ||
     (   (wsFlags & WHERE_COLUMN_NULL)==0
      && i>=pIdx->nColumn
      && indexIsUniqueNotNull(pIdx, nEqCol)
     )
  ){
    /* Advance j over additional ORDER BY terms associated with base */
    WhereMaskSet *pMS = p->pWC->pMaskSet;
    Bitmask m = ~getMask(pMS, base);
    while( j<nTerm && (exprTableUsage(pMS, pOrderBy->a[j].pExpr)&m)==0 ){
      j++;
    }
  }
  return j;
}

/*
** Find the best query plan for accessing a particular table.  Write the
** best query plan and its cost into the p->cost.

**
** The lowest cost plan wins.  The cost is an estimate of the amount of
** CPU and disk I/O needed to process the requested result.
** Factors that influence cost include:
**
**    *  The estimated number of rows that will be retrieved.  (The
**       fewer the better.)

** then the cost is calculated in the usual way.
**
** If a NOT INDEXED clause (pSrc->notIndexed!=0) was attached to the table 
** in the SELECT statement, then no indexes are considered. However, the 
** selected plan may still take advantage of the built-in rowid primary key
** index.
*/
static void bestBtreeIndex(WhereBestIdx *p){
  Parse *pParse = p->pParse;  /* The parsing context */
  WhereClause *pWC = p->pWC;  /* The WHERE clause */
  struct SrcList_item *pSrc = p->pSrc; /* The FROM clause term to search */






  int iCur = pSrc->iCursor;   /* The cursor of the table to be accessed */
  Index *pProbe;              /* An index we are evaluating */
  Index *pIdx;                /* Copy of pProbe, or zero for IPK index */
  int eqTermMask;             /* Current mask of valid equality operators */
  int idxEqTermMask;          /* Index mask of valid equality operators */
  Index sPk;                  /* A fake index object for the primary key */
  tRowcnt aiRowEstPk[2];      /* The aiRowEst[] value for the sPk index */
  int aiColumnPk = -1;        /* The aColumn[] value for the sPk index */
  int wsFlagMask;             /* Allowed flags in p->cost.plan.wsFlag */

  /* Initialize the cost to a worst-case value */
  memset(&p->cost, 0, sizeof(p->cost));
  p->cost.rCost = SQLITE_BIG_DBL;

  /* If the pSrc table is the right table of a LEFT JOIN then we may not
  ** use an index to satisfy IS NULL constraints on that table.  This is
  ** because columns might end up being NULL if the table does not match -
  ** a circumstance which the index cannot help us discover.  Ticket #2177.
  */
  if( pSrc->jointype & JT_LEFT ){

    pIdx = 0;
  }

  /* Loop over all indices looking for the best one to use
  */
  for(; pProbe; pIdx=pProbe=pProbe->pNext){
    const tRowcnt * const aiRowEst = pProbe->aiRowEst;
    WhereCost pc;               /* Cost of using pProbe */

    double log10N = (double)1;  /* base-10 logarithm of nRow (inexact) */
    int bRev = 2;               /* 0=forward scan.  1=reverse.  2=undecided */



    /* The following variables are populated based on the properties of
    ** index being evaluated. They are then used to determine the expected
    ** cost and number of rows returned.
    **
    **  pc.plan.nEq: 
    **    Number of equality terms that can be implemented using the index.
    **    In other words, the number of initial fields in the index that
    **    are used in == or IN or NOT NULL constraints of the WHERE clause.
    **
    **  nInMul:  
    **    The "in-multiplier". This is an estimate of how many seek operations 
    **    SQLite must perform on the index in question. For example, if the 

    **
    **    nInMul is set to 1.
    **
    **    If there exists a WHERE term of the form "x IN (SELECT ...)", then 
    **    the sub-select is assumed to return 25 rows for the purposes of 
    **    determining nInMul.
    **
    **  nOrdered:
    **    The number of equality terms that are constrainted by outer loop
    **    variables that are well-ordered.
    **
    **  bInEst:  
    **    Set to true if there was at least one "x IN (SELECT ...)" term used 
    **    in determining the value of nInMul.  Note that the RHS of the
    **    IN operator must be a SELECT, not a value list, for this variable
    **    to be true.
    **
    **  rangeDiv:
    **    An estimate of a divisor by which to reduce the search space due
    **    to inequality constraints.  In the absence of sqlite_stat3 ANALYZE
    **    data, a single inequality reduces the search space to 1/4rd its
    **    original size (rangeDiv==4).  Two inequalities reduce the search
    **    space to 1/16th of its original size (rangeDiv==16).
    **
    **  bSort:   
    **    Boolean. True if there is an ORDER BY clause that will require an 
    **    external sort (i.e. scanning the index being evaluated will not 
    **    correctly order records).
    **
    **  bDist:
    **    Boolean. True if there is a DISTINCT clause that will require an 
    **    external btree.
    **
    **  bLookup: 
    **    Boolean. True if a table lookup is required for each index entry
    **    visited.  In other words, true if this is not a covering index.
    **    This is always false for the rowid primary key index of a table.
    **    For other indexes, it is true unless all the columns of the table
    **    used by the SELECT statement are present in the index (such an
    **    index is sometimes described as a covering index).
    **    For example, given the index on (a, b), the second of the following 
    **    two queries requires table b-tree lookups in order to find the value
    **    of column c, but the first does not because columns a and b are
    **    both available in the index.
    **
    **             SELECT a, b    FROM tbl WHERE a = 1;
    **             SELECT a, b, c FROM tbl WHERE a = 1;
    */
    int nOrdered;                 /* Number of ordered terms matching index */
    int bInEst = 0;               /* True if "x IN (SELECT...)" seen */
    int nInMul = 1;               /* Number of distinct equalities to lookup */
    double rangeDiv = (double)1;  /* Estimated reduction in search space */
    int nBound = 0;               /* Number of range constraints seen */
    int bSort;                    /* True if external sort required */
    int bDist;                    /* True if index cannot help with DISTINCT */
    int bLookup = 0;              /* True if not a covering index */
    int nPriorSat;                /* ORDER BY terms satisfied by outer loops */
    int nOrderBy;                 /* Number of ORDER BY terms */
    WhereTerm *pTerm;             /* A single term of the WHERE clause */
#ifdef SQLITE_ENABLE_STAT3
    WhereTerm *pFirstTerm = 0;    /* First term matching the index */
#endif

    memset(&pc, 0, sizeof(pc));
    nOrderBy = p->pOrderBy ? p->pOrderBy->nExpr : 0;
    if( p->i ){
      nPriorSat = pc.plan.nOBSat = p->aLevel[p->i-1].plan.nOBSat;
      bSort = nPriorSat<nOrderBy;
      bDist = 0;
    }else{
      nPriorSat = pc.plan.nOBSat = 0;
      bSort = nOrderBy>0;
      bDist = p->pDistinct!=0;
    }

    /* Determine the values of pc.plan.nEq and nInMul */
    for(pc.plan.nEq=nOrdered=0; pc.plan.nEq<pProbe->nColumn; pc.plan.nEq++){
      int j = pProbe->aiColumn[pc.plan.nEq];
      pTerm = findTerm(pWC, iCur, j, p->notReady, eqTermMask, pIdx);
      if( pTerm==0 ) break;
      pc.plan.wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ);
      testcase( pTerm->pWC!=pWC );
      if( pTerm->eOperator & WO_IN ){
        Expr *pExpr = pTerm->pExpr;
        pc.plan.wsFlags |= WHERE_COLUMN_IN;
        if( ExprHasProperty(pExpr, EP_xIsSelect) ){
          /* "x IN (SELECT ...)":  Assume the SELECT returns 25 rows */
          nInMul *= 25;
          bInEst = 1;
        }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
          /* "x IN (value, value, ...)" */
          nInMul *= pExpr->x.pList->nExpr;
        }
      }else if( pTerm->eOperator & WO_ISNULL ){
        pc.plan.wsFlags |= WHERE_COLUMN_NULL;
        if( pc.plan.nEq==nOrdered ) nOrdered++;
      }else if( bSort && pc.plan.nEq==nOrdered
             && isOrderedTerm(p,pTerm,&bRev) ){
        nOrdered++;
      }
#ifdef SQLITE_ENABLE_STAT3
      if( pc.plan.nEq==0 && pProbe->aSample ) pFirstTerm = pTerm;
#endif
      pc.used |= pTerm->prereqRight;
    }
 
    /* If the index being considered is UNIQUE, and there is an equality 
    ** constraint for all columns in the index, then this search will find
    ** at most a single row. In this case set the WHERE_UNIQUE flag to 
    ** indicate this to the caller.
    **
    ** Otherwise, if the search may find more than one row, test to see if
    ** there is a range constraint on indexed column (pc.plan.nEq+1) that can be 
    ** optimized using the index. 
    */
    if( pc.plan.nEq==pProbe->nColumn && pProbe->onError!=OE_None ){
      testcase( pc.plan.wsFlags & WHERE_COLUMN_IN );
      testcase( pc.plan.wsFlags & WHERE_COLUMN_NULL );
      if( (pc.plan.wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){
        pc.plan.wsFlags |= WHERE_UNIQUE;
        if( p->i==0 || (p->aLevel[p->i-1].plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){
          pc.plan.wsFlags |= WHERE_ALL_UNIQUE;
        }
      }
    }else if( pProbe->bUnordered==0 ){
      int j;
      j = (pc.plan.nEq==pProbe->nColumn ? -1 : pProbe->aiColumn[pc.plan.nEq]);
      if( findTerm(pWC, iCur, j, p->notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){
        WhereTerm *pTop, *pBtm;
        pTop = findTerm(pWC, iCur, j, p->notReady, WO_LT|WO_LE, pIdx);
        pBtm = findTerm(pWC, iCur, j, p->notReady, WO_GT|WO_GE, pIdx);
        whereRangeScanEst(pParse, pProbe, pc.plan.nEq, pBtm, pTop, &rangeDiv);
        if( pTop ){
          nBound = 1;
          pc.plan.wsFlags |= WHERE_TOP_LIMIT;
          pc.used |= pTop->prereqRight;
          testcase( pTop->pWC!=pWC );
        }
        if( pBtm ){
          nBound++;
          pc.plan.wsFlags |= WHERE_BTM_LIMIT;
          pc.used |= pBtm->prereqRight;
          testcase( pBtm->pWC!=pWC );
        }
        pc.plan.wsFlags |= (WHERE_COLUMN_RANGE|WHERE_ROWID_RANGE);
      }
    }

    /* If there is an ORDER BY clause and the index being considered will
    ** naturally scan rows in the required order, set the appropriate flags
    ** in pc.plan.wsFlags. Otherwise, if there is an ORDER BY clause but
    ** the index will scan rows in a different order, set the bSort
    ** variable.  */
    assert( bRev>=0 && bRev<=2 );
    if( bSort ){
      testcase( bRev==0 );
      testcase( bRev==1 );
      testcase( bRev==2 );
      pc.plan.nOBSat = isSortingIndex(p, pProbe, iCur, nOrdered,
                                 pc.plan.wsFlags, bRev&1, &bRev);
      if( nPriorSat<pc.plan.nOBSat || (pc.plan.wsFlags & WHERE_UNIQUE)!=0 ){
        pc.plan.wsFlags |= WHERE_ORDERED;
      }
      if( nOrderBy==pc.plan.nOBSat ){
        bSort = 0;
        pc.plan.wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE;
      }
      if( bRev & 1 ) pc.plan.wsFlags |= WHERE_REVERSE;
    }

    /* If there is a DISTINCT qualifier and this index will scan rows in
    ** order of the DISTINCT expressions, clear bDist and set the appropriate
    ** flags in pc.plan.wsFlags. */
    if( bDist
     && isDistinctIndex(pParse, pWC, pProbe, iCur, p->pDistinct, pc.plan.nEq)
     && (pc.plan.wsFlags & WHERE_COLUMN_IN)==0
    ){
      bDist = 0;
      pc.plan.wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE|WHERE_DISTINCT;
    }

    /* If currently calculating the cost of using an index (not the IPK
    ** index), determine if all required column data may be obtained without 
    ** using the main table (i.e. if the index is a covering
    ** index for this query). If it is, set the WHERE_IDX_ONLY flag in
    ** pc.plan.wsFlags. Otherwise, set the bLookup variable to true.  */
    if( pIdx ){
      Bitmask m = pSrc->colUsed;
      int j;
      for(j=0; j<pIdx->nColumn; j++){
        int x = pIdx->aiColumn[j];
        if( x<BMS-1 ){
          m &= ~(((Bitmask)1)<<x);
        }
      }
      if( m==0 ){
        pc.plan.wsFlags |= WHERE_IDX_ONLY;
      }else{
        bLookup = 1;
      }
    }

    /*
    ** Estimate the number of rows of output.  For an "x IN (SELECT...)"
    ** constraint, do not let the estimate exceed half the rows in the table.
    */
    pc.plan.nRow = (double)(aiRowEst[pc.plan.nEq] * nInMul);
    if( bInEst && pc.plan.nRow*2>aiRowEst[0] ){
      pc.plan.nRow = aiRowEst[0]/2;
      nInMul = (int)(pc.plan.nRow / aiRowEst[pc.plan.nEq]);
    }

#ifdef SQLITE_ENABLE_STAT3
    /* If the constraint is of the form x=VALUE or x IN (E1,E2,...)
    ** and we do not think that values of x are unique and if histogram
    ** data is available for column x, then it might be possible
    ** to get a better estimate on the number of rows based on
    ** VALUE and how common that value is according to the histogram.
    */
    if( pc.plan.nRow>(double)1 && pc.plan.nEq==1
     && pFirstTerm!=0 && aiRowEst[1]>1 ){
      assert( (pFirstTerm->eOperator & (WO_EQ|WO_ISNULL|WO_IN))!=0 );
      if( pFirstTerm->eOperator & (WO_EQ|WO_ISNULL) ){
        testcase( pFirstTerm->eOperator==WO_EQ );
        testcase( pFirstTerm->eOperator==WO_ISNULL );
        whereEqualScanEst(pParse, pProbe, pFirstTerm->pExpr->pRight,
                          &pc.plan.nRow);
      }else if( bInEst==0 ){
        assert( pFirstTerm->eOperator==WO_IN );
        whereInScanEst(pParse, pProbe, pFirstTerm->pExpr->x.pList,
                       &pc.plan.nRow);
      }
    }
#endif /* SQLITE_ENABLE_STAT3 */

    /* Adjust the number of output rows and downward to reflect rows
    ** that are excluded by range constraints.
    */
    pc.plan.nRow = pc.plan.nRow/rangeDiv;
    if( pc.plan.nRow<1 ) pc.plan.nRow = 1;

    /* Experiments run on real SQLite databases show that the time needed
    ** to do a binary search to locate a row in a table or index is roughly
    ** log10(N) times the time to move from one row to the next row within
    ** a table or index.  The actual times can vary, with the size of
    ** records being an important factor.  Both moves and searches are
    ** slower with larger records, presumably because fewer records fit
    ** on one page and hence more pages have to be fetched.
    **
    ** The ANALYZE command and the sqlite_stat1 and sqlite_stat3 tables do
    ** not give us data on the relative sizes of table and index records.
    ** So this computation assumes table records are about twice as big
    ** as index records
    */
    if( (pc.plan.wsFlags&~(WHERE_REVERSE|WHERE_ORDERED))==WHERE_IDX_ONLY
     && (pWC->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
     && sqlite3GlobalConfig.bUseCis

     && OptimizationEnabled(pParse->db, SQLITE_CoverIdxScan)

    ){
      /* This index is not useful for indexing, but it is a covering index.
      ** A full-scan of the index might be a little faster than a full-scan
      ** of the table, so give this case a cost slightly less than a table
      ** scan. */
      pc.rCost = aiRowEst[0]*3 + pProbe->nColumn;
      pc.plan.wsFlags |= WHERE_COVER_SCAN|WHERE_COLUMN_RANGE;
    }else if( (pc.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ){
      /* The cost of a full table scan is a number of move operations equal
      ** to the number of rows in the table.
      **
      ** We add an additional 4x penalty to full table scans.  This causes
      ** the cost function to err on the side of choosing an index over
      ** choosing a full scan.  This 4x full-scan penalty is an arguable
      ** decision and one which we expect to revisit in the future.  But
      ** it seems to be working well enough at the moment.
      */
      pc.rCost = aiRowEst[0]*4;
      pc.plan.wsFlags &= ~WHERE_IDX_ONLY;
      if( pIdx ) pc.plan.wsFlags &= ~WHERE_ORDERED;
    }else{
      log10N = estLog(aiRowEst[0]);
      pc.rCost = pc.plan.nRow;
      if( pIdx ){
        if( bLookup ){
          /* For an index lookup followed by a table lookup:
          **    nInMul index searches to find the start of each index range
          **  + nRow steps through the index
          **  + nRow table searches to lookup the table entry using the rowid
          */
          pc.rCost += (nInMul + pc.plan.nRow)*log10N;
        }else{
          /* For a covering index:
          **     nInMul index searches to find the initial entry 
          **   + nRow steps through the index
          */
          pc.rCost += nInMul*log10N;
        }
      }else{
        /* For a rowid primary key lookup:
        **    nInMult table searches to find the initial entry for each range
        **  + nRow steps through the table
        */
        pc.rCost += nInMul*log10N;
      }
    }

    /* Add in the estimated cost of sorting the result.  Actual experimental
    ** measurements of sorting performance in SQLite show that sorting time
    ** adds C*N*log10(N) to the cost, where N is the number of rows to be 
    ** sorted and C is a factor between 1.95 and 4.3.  We will split the
    ** difference and select C of 3.0.
    */
    if( bSort ){
      double m = estLog(pc.plan.nRow*(nOrderBy - pc.plan.nOBSat)/nOrderBy);
      m *= (double)(pc.plan.nOBSat ? 2 : 3);
      pc.rCost += pc.plan.nRow*m;
    }
    if( bDist ){
      pc.rCost += pc.plan.nRow*estLog(pc.plan.nRow)*3;
    }

    /**** Cost of using this index has now been computed ****/

    /* If there are additional constraints on this table that cannot
    ** be used with the current index, but which might lower the number
    ** of output rows, adjust the nRow value accordingly.  This only 
    ** matters if the current index is the least costly, so do not bother
    ** with this step if we already know this index will not be chosen.
    ** Also, never reduce the output row count below 2 using this step.
    **
    ** It is critical that the notValid mask be used here instead of
    ** the notReady mask.  When computing an "optimal" index, the notReady
    ** mask will only have one bit set - the bit for the current table.
    ** The notValid mask, on the other hand, always has all bits set for
    ** tables that are not in outer loops.  If notReady is used here instead
    ** of notValid, then a optimal index that depends on inner joins loops
    ** might be selected even when there exists an optimal index that has
    ** no such dependency.
    */
    if( pc.plan.nRow>2 && pc.rCost<=p->cost.rCost ){
      int k;                       /* Loop counter */
      int nSkipEq = pc.plan.nEq;   /* Number of == constraints to skip */
      int nSkipRange = nBound;     /* Number of < constraints to skip */
      Bitmask thisTab;             /* Bitmap for pSrc */

      thisTab = getMask(pWC->pMaskSet, iCur);
      for(pTerm=pWC->a, k=pWC->nTerm; pc.plan.nRow>2 && k; k--, pTerm++){
        if( pTerm->wtFlags & TERM_VIRTUAL ) continue;
        if( (pTerm->prereqAll & p->notValid)!=thisTab ) continue;
        if( pTerm->eOperator & (WO_EQ|WO_IN|WO_ISNULL) ){
          if( nSkipEq ){
            /* Ignore the first pc.plan.nEq equality matches since the index
            ** has already accounted for these */
            nSkipEq--;
          }else{
            /* Assume each additional equality match reduces the result
            ** set size by a factor of 10 */
            pc.plan.nRow /= 10;
          }
        }else if( pTerm->eOperator & (WO_LT|WO_LE|WO_GT|WO_GE) ){
          if( nSkipRange ){
            /* Ignore the first nSkipRange range constraints since the index
            ** has already accounted for these */
            nSkipRange--;
          }else{
            /* Assume each additional range constraint reduces the result
            ** set size by a factor of 3.  Indexed range constraints reduce
            ** the search space by a larger factor: 4.  We make indexed range
            ** more selective intentionally because of the subjective 
            ** observation that indexed range constraints really are more
            ** selective in practice, on average. */
            pc.plan.nRow /= 3;
          }
        }else if( pTerm->eOperator!=WO_NOOP ){
          /* Any other expression lowers the output row count by half */
          pc.plan.nRow /= 2;
        }
      }
      if( pc.plan.nRow<2 ) pc.plan.nRow = 2;
    }


    WHERETRACE((
      "%s(%s):\n"
      "    nEq=%d nInMul=%d rangeDiv=%d bSort=%d bLookup=%d wsFlags=0x%08x\n"
      "    notReady=0x%llx log10N=%.1f nRow=%.1f cost=%.1f\n"
      "    used=0x%llx nOrdered=%d nOBSat=%d\n",
      pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk"), 
      pc.plan.nEq, nInMul, (int)rangeDiv, bSort, bLookup, pc.plan.wsFlags,
      p->notReady, log10N, pc.plan.nRow, pc.rCost, pc.used, nOrdered,
      pc.plan.nOBSat
    ));

    /* If this index is the best we have seen so far, then record this
    ** index and its cost in the p->cost structure.
    */
    if( (!pIdx || pc.plan.wsFlags) && compareCost(&pc, &p->cost) ){


      p->cost = pc;


      p->cost.plan.wsFlags &= wsFlagMask;

      p->cost.plan.u.pIdx = pIdx;
    }

    /* If there was an INDEXED BY clause, then only that one index is
    ** considered. */
    if( pSrc->pIndex ) break;

    /* Reset masks for the next index in the loop */
    wsFlagMask = ~(WHERE_ROWID_EQ|WHERE_ROWID_RANGE);
    eqTermMask = idxEqTermMask;
  }

  /* If there is no ORDER BY clause and the SQLITE_ReverseOrder flag
  ** is set, then reverse the order that the index will be scanned
  ** in. This is used for application testing, to help find cases
  ** where application behaviour depends on the (undefined) order that
  ** SQLite outputs rows in in the absence of an ORDER BY clause.  */
  if( !p->pOrderBy && pParse->db->flags & SQLITE_ReverseOrder ){
    p->cost.plan.wsFlags |= WHERE_REVERSE;
  }

  assert( p->pOrderBy || (p->cost.plan.wsFlags&WHERE_ORDERED)==0 );
  assert( p->cost.plan.u.pIdx==0 || (p->cost.plan.wsFlags&WHERE_ROWID_EQ)==0 );
  assert( pSrc->pIndex==0 
       || p->cost.plan.u.pIdx==0 
       || p->cost.plan.u.pIdx==pSrc->pIndex 
  );

  WHERETRACE(("best index is: %s\n",

         p->cost.plan.u.pIdx ? p->cost.plan.u.pIdx->zName : "ipk"));

  
  bestOrClauseIndex(p);
  bestAutomaticIndex(p);
  p->cost.plan.wsFlags |= eqTermMask;
}

/*
** Find the query plan for accessing table pSrc->pTab. Write the
** best query plan and its cost into the WhereCost object supplied 
** as the last parameter. This function may calculate the cost of
** both real and virtual table scans.
**
** This function does not take ORDER BY or DISTINCT into account.  Nor
** does it remember the virtual table query plan.  All it does is compute
** the cost while determining if an OR optimization is applicable.  The
** details will be reconsidered later if the optimization is found to be
** applicable.
*/
static void bestIndex(WhereBestIdx *p){







#ifndef SQLITE_OMIT_VIRTUALTABLE
  if( IsVirtual(p->pSrc->pTab) ){
    sqlite3_index_info *pIdxInfo = 0;
    p->ppIdxInfo = &pIdxInfo;
    bestVirtualIndex(p);
    if( pIdxInfo->needToFreeIdxStr ){
      sqlite3_free(pIdxInfo->idxStr);
    }
    sqlite3DbFree(p->pParse->db, pIdxInfo);
  }else
#endif
  {
    bestBtreeIndex(p);
  }
}

/*
** Disable a term in the WHERE clause.  Except, do not disable the term
** if it controls a LEFT OUTER JOIN and it did not originate in the ON
** or USING clause of that join.

    ** query, then the caller will only allow the loop to run for
    ** a single iteration. This means that the first row returned
    ** should not have a NULL value stored in 'x'. If column 'x' is
    ** the first one after the nEq equality constraints in the index,
    ** this requires some special handling.
    */
    if( (wctrlFlags&WHERE_ORDERBY_MIN)!=0
     && (pLevel->plan.wsFlags&WHERE_ORDERED)
     && (pIdx->nColumn>nEq)
    ){
      /* assert( pOrderBy->nExpr==1 ); */
      /* assert( pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq] ); */
      isMinQuery = 1;
      nExtraReg = 1;
    }

  SrcList *pTabList,    /* A list of all tables to be scanned */
  Expr *pWhere,         /* The WHERE clause */
  ExprList *pOrderBy,   /* An ORDER BY clause, or NULL */
  ExprList *pDistinct,  /* The select-list for DISTINCT queries - or NULL */
  u16 wctrlFlags,       /* One of the WHERE_* flags defined in sqliteInt.h */
  int iIdxCur           /* If WHERE_ONETABLE_ONLY is set, index cursor number */
){

  int nByteWInfo;            /* Num. bytes allocated for WhereInfo struct */
  int nTabList;              /* Number of elements in pTabList */
  WhereInfo *pWInfo;         /* Will become the return value of this function */
  Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
  Bitmask notReady;          /* Cursors that are not yet positioned */
  WhereBestIdx sWBI;         /* Best index search context */
  WhereMaskSet *pMaskSet;    /* The expression mask set */


  WhereLevel *pLevel;        /* A single level in pWInfo->a[] */
  int iFrom;                 /* First unused FROM clause element */
  int andFlags;              /* AND-ed combination of all pWC->a[].wtFlags */
  int ii;                    /* Loop counter */
  sqlite3 *db;               /* Database connection */


  /* Variable initialization */
  memset(&sWBI, 0, sizeof(sWBI));
  sWBI.pParse = pParse;

  /* The number of tables in the FROM clause is limited by the number of
  ** bits in a Bitmask 
  */
  testcase( pTabList->nSrc==BMS );
  if( pTabList->nSrc>BMS ){
    sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS);
    return 0;

    pWInfo = 0;
    goto whereBeginError;
  }
  pWInfo->nLevel = nTabList;
  pWInfo->pParse = pParse;
  pWInfo->pTabList = pTabList;
  pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
  pWInfo->pWC = sWBI.pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo];
  pWInfo->wctrlFlags = wctrlFlags;
  pWInfo->savedNQueryLoop = pParse->nQueryLoop;
  pMaskSet = (WhereMaskSet*)&sWBI.pWC[1];
  sWBI.aLevel = pWInfo->a;

  /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via
  ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */
  if( OptimizationDisabled(db, SQLITE_DistinctOpt) ) pDistinct = 0;

  /* Split the WHERE clause into separate subexpressions where each
  ** subexpression is separated by an AND operator.
  */
  initMaskSet(pMaskSet);
  whereClauseInit(sWBI.pWC, pParse, pMaskSet, wctrlFlags);
  sqlite3ExprCodeConstants(pParse, pWhere);
  whereSplit(sWBI.pWC, pWhere, TK_AND);   /* IMP: R-15842-53296 */
    
  /* Special case: a WHERE clause that is constant.  Evaluate the
  ** expression and either jump over all of the code or fall thru.
  */
  if( pWhere && (nTabList==0 || sqlite3ExprIsConstantNotJoin(pWhere)) ){
    sqlite3ExprIfFalse(pParse, pWhere, pWInfo->iBreak, SQLITE_JUMPIFNULL);
    pWhere = 0;

  ** with virtual tables.
  **
  ** Note that bitmasks are created for all pTabList->nSrc tables in
  ** pTabList, not just the first nTabList tables.  nTabList is normally
  ** equal to pTabList->nSrc but might be shortened to 1 if the
  ** WHERE_ONETABLE_ONLY flag is set.
  */
  assert( sWBI.pWC->vmask==0 && pMaskSet->n==0 );
  for(ii=0; ii<pTabList->nSrc; ii++){
    createMask(pMaskSet, pTabList->a[ii].iCursor);
#ifndef SQLITE_OMIT_VIRTUALTABLE
    if( ALWAYS(pTabList->a[ii].pTab) && IsVirtual(pTabList->a[ii].pTab) ){
      sWBI.pWC->vmask |= ((Bitmask)1 << ii);
    }
#endif
  }
#ifndef NDEBUG
  {
    Bitmask toTheLeft = 0;
    for(ii=0; ii<pTabList->nSrc; ii++){
      Bitmask m = getMask(pMaskSet, pTabList->a[ii].iCursor);
      assert( (m-1)==toTheLeft );
      toTheLeft |= m;
    }
  }
#endif

  /* Analyze all of the subexpressions.  Note that exprAnalyze() might
  ** add new virtual terms onto the end of the WHERE clause.  We do not
  ** want to analyze these virtual terms, so start analyzing at the end
  ** and work forward so that the added virtual terms are never processed.
  */
  exprAnalyzeAll(pTabList, sWBI.pWC);
  if( db->mallocFailed ){
    goto whereBeginError;
  }

  /* Check if the DISTINCT qualifier, if there is one, is redundant. 
  ** If it is, then set pDistinct to NULL and WhereInfo.eDistinct to
  ** WHERE_DISTINCT_UNIQUE to tell the caller to ignore the DISTINCT.
  */
  if( pDistinct && isDistinctRedundant(pParse, pTabList, sWBI.pWC, pDistinct) ){
    pDistinct = 0;
    pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
  }

  /* Chose the best index to use for each table in the FROM clause.
  **
  ** This loop fills in the following fields:
  **
  **   pWInfo->a[].pIdx      The index to use for this level of the loop.
  **   pWInfo->a[].wsFlags   WHERE_xxx flags associated with pIdx
  **   pWInfo->a[].nEq       The number of == and IN constraints
  **   pWInfo->a[].iFrom     Which term of the FROM clause is being coded
  **   pWInfo->a[].iTabCur   The VDBE cursor for the database table
  **   pWInfo->a[].iIdxCur   The VDBE cursor for the index
  **   pWInfo->a[].pTerm     When wsFlags==WO_OR, the OR-clause term
  **
  ** This loop also figures out the nesting order of tables in the FROM
  ** clause.
  */
  sWBI.notValid = ~(Bitmask)0;
  sWBI.pOrderBy = pOrderBy;
  sWBI.n = nTabList;
  sWBI.pDistinct = pDistinct;
  andFlags = ~0;
  WHERETRACE(("*** Optimizer Start ***\n"));
  for(sWBI.i=iFrom=0, pLevel=pWInfo->a; sWBI.i<nTabList; sWBI.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 */
    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", sWBI.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
    ** to choose from.  The first test looks for an "optimal" scan.  In
    ** this context an optimal scan is one that uses the same strategy
    ** for the given FROM clause entry as would be selected if the entry
    ** were used as the innermost nested loop.  In other words, a table
    ** is chosen such that the cost of running that table cannot be reduced
    ** by waiting for other tables to run first.  This "optimal" test works
    ** by first assuming that the FROM clause is on the inner loop and finding
    ** its query plan, then checking to see if that query plan uses any
    ** other FROM clause terms that are sWBI.notValid.  If no notValid terms
    ** are used then the "optimal" query plan works.
    **
    ** Note that the WhereCost.nRow parameter for an optimal scan might
    ** not be as small as it would be if the table really were the innermost
    ** join.  The nRow value can be reduced by WHERE clause constraints
    ** that do not use indices.  But this nRow reduction only happens if the
    ** table really is the innermost join.  
    **

    ** 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;
    notIndexed = 0;
    for(isOptimal=(iFrom<nTabList-1); isOptimal>=0 && bestJ<0; isOptimal--){

      for(j=iFrom, sWBI.pSrc=&pTabList->a[j]; j<nTabList; j++, sWBI.pSrc++){
        int doNotReorder;    /* True if this table should not be reordered */



  
        doNotReorder =  (sWBI.pSrc->jointype & (JT_LEFT|JT_CROSS))!=0;
        if( j!=iFrom && doNotReorder ) break;
        m = getMask(pMaskSet, sWBI.pSrc->iCursor);
        if( (m & sWBI.notValid)==0 ){
          if( j==iFrom ) iFrom++;
          continue;
        }
        sWBI.notReady = (isOptimal ? m : sWBI.notValid);


        if( sWBI.pSrc->pIndex==0 ) nUnconstrained++;
  
        WHERETRACE(("=== trying table %d (%s) with isOptimal=%d ===\n",
                    j, sWBI.pSrc->pTab->zName, isOptimal));
        assert( sWBI.pSrc->pTab );
#ifndef SQLITE_OMIT_VIRTUALTABLE
        if( IsVirtual(sWBI.pSrc->pTab) ){
          sWBI.ppIdxInfo = &pWInfo->a[j].pIdxInfo;
          bestVirtualIndex(&sWBI);

        }else 
#endif
        {
          bestBtreeIndex(&sWBI);

        }
        assert( isOptimal || (sWBI.cost.used&sWBI.notValid)==0 );

        /* If an INDEXED BY clause is present, then the plan must use that
        ** index if it uses any index at all */
        assert( sWBI.pSrc->pIndex==0 
                  || (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0
                  || sWBI.cost.plan.u.pIdx==sWBI.pSrc->pIndex );

        if( isOptimal && (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ){
          notIndexed |= m;
        }

        /* Conditions under which this table becomes the best so far:
        **
        **   (1) The table must not depend on other tables that have not
        **       yet run.  (In other words, it must not depend on tables
        **       in inner loops.)
        **
        **   (2) A full-table-scan plan cannot supercede indexed plan unless
        **       the full-table-scan is an "optimal" plan as defined above.
        **
        **   (3) 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.  This rule ensures
        **       that a best-so-far is always selected even if an impossible
        **       combination of INDEXED BY clauses are given.  The error
        **       will be detected and relayed back to the application later.
        **       The NEVER() comes about because rule (2) above prevents
        **       An indexable full-table-scan from reaching rule (3).
        **
        **   (4) The plan cost must be lower than prior plans, where "cost"
        **       is defined by the compareCost() function above. 
        */
        if( (sWBI.cost.used&sWBI.notValid)==0                    /* (1) */
            && (bestJ<0 || (notIndexed&m)!=0                     /* (2) */
                || (bestPlan.plan.wsFlags & WHERE_NOT_FULLSCAN)==0
                || (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0)
            && (nUnconstrained==0 || sWBI.pSrc->pIndex==0        /* (3) */
                || NEVER((sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0))
            && (bestJ<0 || compareCost(&sWBI.cost, &bestPlan))   /* (4) */


        ){
          WHERETRACE(("=== table %d (%s) is best so far\n"
                      "    cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=%08x\n",
                      j, sWBI.pSrc->pTab->zName,
                      sWBI.cost.rCost, sWBI.cost.plan.nRow,
                      sWBI.cost.plan.nOBSat, sWBI.cost.plan.wsFlags));
          bestPlan = sWBI.cost;
          bestJ = j;
        }
        if( doNotReorder ) break;
      }
    }
    assert( bestJ>=0 );
    assert( sWBI.notValid & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
    WHERETRACE(("*** Optimizer selects table %d (%s) for loop %d with:\n"
                "    cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=0x%08x\n",
                bestJ, pTabList->a[bestJ].pTab->zName,
                pLevel-pWInfo->a, bestPlan.rCost, bestPlan.plan.nRow,
                bestPlan.plan.nOBSat, bestPlan.plan.wsFlags));


    if( (bestPlan.plan.wsFlags & WHERE_DISTINCT)!=0 ){
      assert( pWInfo->eDistinct==0 );
      pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
    }
    andFlags &= bestPlan.plan.wsFlags;
    pLevel->plan = bestPlan.plan;
    pLevel->iTabCur = pTabList->a[bestJ].iCursor;
    testcase( bestPlan.plan.wsFlags & WHERE_INDEXED );
    testcase( bestPlan.plan.wsFlags & WHERE_TEMP_INDEX );
    if( bestPlan.plan.wsFlags & (WHERE_INDEXED|WHERE_TEMP_INDEX) ){
      if( (wctrlFlags & WHERE_ONETABLE_ONLY) 
       && (bestPlan.plan.wsFlags & WHERE_TEMP_INDEX)==0 
      ){
        pLevel->iIdxCur = iIdxCur;
      }else{
        pLevel->iIdxCur = pParse->nTab++;
      }
    }else{
      pLevel->iIdxCur = -1;
    }
    sWBI.notValid &= ~getMask(pMaskSet, pTabList->a[bestJ].iCursor);
    pLevel->iFrom = (u8)bestJ;
    if( bestPlan.plan.nRow>=(double)1 ){
      pParse->nQueryLoop *= bestPlan.plan.nRow;
    }

    /* Check that if the table scanned by this loop iteration had an
    ** INDEXED BY clause attached to it, that the named index is being

      }
    }
  }
  WHERETRACE(("*** Optimizer Finished ***\n"));
  if( pParse->nErr || db->mallocFailed ){
    goto whereBeginError;
  }
  if( nTabList ){
    pLevel--;
    pWInfo->nOBSat = pLevel->plan.nOBSat;
  }else{
    pWInfo->nOBSat = 0;
  }

  /* If the total query only selects a single row, then the ORDER BY
  ** clause is irrelevant.
  */
  if( (andFlags & WHERE_UNIQUE)!=0 && pOrderBy ){
    assert( nTabList==0 || (pLevel->plan.wsFlags & WHERE_ALL_UNIQUE)!=0 );
    pWInfo->nOBSat = pOrderBy->nExpr;
  }

  /* If the caller is an UPDATE or DELETE statement that is requesting
  ** to use a one-pass algorithm, determine if this is appropriate.
  ** The one-pass algorithm only works if the WHERE clause constraints
  ** the statement to update a single row.
  */
  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;
  }

  /* Open all tables in the pTabList and any indices selected for
  ** searching those tables.
  */
  sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
  notReady = ~(Bitmask)0;
  pWInfo->nRowOut = (double)1;
  for(ii=0, pLevel=pWInfo->a; ii<nTabList; ii++, pLevel++){
    Table *pTab;     /* Table to open */
    int iDb;         /* Index of database containing table/index */
    struct SrcList_item *pTabItem;

    pTabItem = &pTabList->a[pLevel->iFrom];
    pTab = pTabItem->pTab;

    pWInfo->nRowOut *= pLevel->plan.nRow;
    iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
    if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ){
      /* Do nothing */
    }else
#ifndef SQLITE_OMIT_VIRTUALTABLE
    if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){

        assert( n<=pTab->nCol );
      }
    }else{
      sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
    }
#ifndef SQLITE_OMIT_AUTOMATIC_INDEX
    if( (pLevel->plan.wsFlags & WHERE_TEMP_INDEX)!=0 ){
      constructAutomaticIndex(pParse, sWBI.pWC, pTabItem, notReady, pLevel);
    }else
#endif
    if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
      Index *pIx = pLevel->plan.u.pIdx;
      KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIx);
      int iIndexCur = pLevel->iIdxCur;
      assert( pIx->pSchema==pTab->pSchema );
      assert( iIndexCur>=0 );
      sqlite3VdbeAddOp4(v, OP_OpenRead, iIndexCur, pIx->tnum, iDb,
                        (char*)pKey, P4_KEYINFO_HANDOFF);
      VdbeComment((v, "%s", pIx->zName));
    }
    sqlite3CodeVerifySchema(pParse, iDb);
    notReady &= ~getMask(sWBI.pWC->pMaskSet, pTabItem->iCursor);
  }
  pWInfo->iTop = sqlite3VdbeCurrentAddr(v);
  if( db->mallocFailed ) goto whereBeginError;

  /* Generate the code to do the search.  Each iteration of the for
  ** loop below generates code for a single nested loop of the VM
  ** program.
  */
  notReady = ~(Bitmask)0;
  for(ii=0; ii<nTabList; ii++){
    pLevel = &pWInfo->a[ii];
    explainOneScan(pParse, pTabList, pLevel, ii, pLevel->iFrom, wctrlFlags);
    notReady = codeOneLoopStart(pWInfo, ii, wctrlFlags, notReady);
    pWInfo->iContinue = pLevel->addrCont;
  }

#ifdef SQLITE_TEST  /* For testing and debugging use only */
  /* Record in the query plan information about the current table
  ** and the index used to access it (if any).  If the table itself
  ** is not used, its name is just '{}'.  If no index is used
  ** the index is listed as "{}".  If the primary key is used the
  ** index name is '*'.
  */
  for(ii=0; ii<nTabList; ii++){
    char *z;
    int n;
    int w;
    struct SrcList_item *pTabItem;

    pLevel = &pWInfo->a[ii];
    w = pLevel->plan.wsFlags;
    pTabItem = &pTabList->a[pLevel->iFrom];
    z = pTabItem->zAlias;
    if( z==0 ) z = pTabItem->pTab->zName;
    n = sqlite3Strlen30(z);
    if( n+nQPlan < sizeof(sqlite3_query_plan)-10 ){
      if( (w & WHERE_IDX_ONLY)!=0 && (w & WHERE_COVER_SCAN)==0 ){

# focus of this script testing the ability of SQLite to handle database
# files larger than 4GB.
#
# $Id: bigfile.test,v 1.12 2009/03/05 04:27:08 shane Exp $
#

if {[file exists skip-big-file]} return
if {$tcl_platform(os)=="Darwin"} return

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

# Do not use a codec for this file, as the database is manipulated using
# external methods (the [fake_big_file] and [hexio_write] commands).
#

#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script testing the ability of SQLite to handle database
# files larger than 4GB.
#

if {[file exists skip-big-file]} return
if {$tcl_platform(os)=="Darwin"} return

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

# Create a small database.
#

# These tests - collate5-3.* - focus on compound SELECT queries that 
# feature ORDER BY clauses.
#
do_test collate5-3.0 {
  execsql {
    SELECT a FROM collate5t1 UNION ALL SELECT a FROM collate5t2 ORDER BY 1;
  }
} {/[aA] [aA] [aA] [aA] [bB] [bB] [bB] [bB] [nN] [nN]/}
do_test collate5-3.1 {
  execsql {
    SELECT a FROM collate5t2 UNION ALL SELECT a FROM collate5t1 ORDER BY 1;
  }
} {A A B B N a a b b n}
do_test collate5-3.2 {
  execsql {

    SELECT a, count(*) FROM collate5t1 GROUP BY a;
  }]
} {a 2 b 2}
do_test collate5-4.2 {
  execsql {
    SELECT a, b, count(*) FROM collate5t1 GROUP BY a, b ORDER BY a, b;
  }
} {/[aA] 1(.0)? 2 [bB] 2 1 [bB] 3 1/}
do_test collate5-4.3 {
  execsql {
    DROP TABLE collate5t1;
  }
} {}

finish_test

#   These tests also show that the following is not untrue:
#
# EVIDENCE-OF: R-25883-55063 The expressions in the GROUP BY clause do
# not have to be expressions that appear in the result.
#
do_select_tests e_select-4.9 {
  1  "SELECT group_concat(one), two FROM b1 GROUP BY two" {
    /#,# f   1 o   #,#   s #,# t/
  }
  2  "SELECT group_concat(one), sum(one) FROM b1 GROUP BY (one>4)" {
    1,2,3,4 10    5,6,7 18
  }
  3  "SELECT group_concat(one) FROM b1 GROUP BY (two>'o'), one%2" {
    4  1,5    2,6   3,7
  }
  4  "SELECT group_concat(one) FROM b1 GROUP BY (one==2 OR two=='o')" {
    4,3,5,7,6    1,2
  }
}

# EVIDENCE-OF: R-14926-50129 For the purposes of grouping rows, NULL
# values are considered equal.
#
do_select_tests e_select-4.10 {
  1  "SELECT group_concat(y) FROM b2 GROUP BY x" {/#,#   3   #,#/}
  2  "SELECT count(*) FROM b2 GROUP BY CASE WHEN y<4 THEN NULL ELSE 0 END" {4 1}
} 

# EVIDENCE-OF: R-10470-30318 The usual rules for selecting a collation
# sequence with which to compare text values apply when evaluating
# expressions in a GROUP BY clause.
#

     1 2 3    1 2 -20    1 4  93    1 5 -1   
  }
  7  "SELECT * FROM d1 ORDER BY 1 DESC, 2, 3" {
     2 4 93   2 5 -1     1 2 -20    1 2 3    
     1 2 7    1 2 8      1 4  93    1 5 -1   
  }
  8  "SELECT z, x FROM d1 ORDER BY 2" {
     /# 1    # 1    # 1   # 1 
      # 1    # 1    # 2   # 2/
  }
  9  "SELECT z, x FROM d1 ORDER BY 1" {
     /-20 1  -1 #   -1 #   3 1
     7 1     8 1   93 #   93 #/   
  }
}

# EVIDENCE-OF: R-63286-51977 If the ORDER BY expression is an identifier
# that corresponds to the alias of one of the output columns, then the
# expression is considered an alias for that column.
#
do_select_tests e_select-8.5 {
  1   "SELECT z+1 AS abc FROM d1 ORDER BY abc" {
    -19 0 0 4 8 9 94 94
  }
  2   "SELECT z+1 AS abc FROM d1 ORDER BY abc DESC" {
    94 94 9 8 4 0 0 -19
  }
  3  "SELECT z AS x, x AS z FROM d1 ORDER BY z" {
    /# 1    # 1    # 1    # 1    # 1    # 1    # 2    # 2/
  }
  4  "SELECT z AS x, x AS z FROM d1 ORDER BY x" {
    /-20 1    -1 #    -1 #    3 1    7 1    8 1    93 #    93 #/
  }
}

# EVIDENCE-OF: R-65068-27207 Otherwise, if the ORDER BY expression is
# any other expression, it is evaluated and the returned value used to
# order the output rows.
#

  INSERT INTO x5_rules VALUES(0, 'a', '0.1.2.3.4.5.6.7.8.9.a', 1);
  DROP TABLE x5;
  CREATE VIRTUAL TABLE x5 USING fuzzer(x5_rules);
  SELECT length(word) FROM x5 WHERE word MATCH 'a' LIMIT 50;
} {1 21 41 61 81}

finish_test

#
do_test lock-2.8 {
  db2 timeout 400
  execsql BEGIN
  execsql {UPDATE t1 SET a = 0 WHERE 0}
  catchsql {BEGIN EXCLUSIVE;} db2
} {1 {database is locked}}
do_test lock-2.8b {
  db2 eval {PRAGMA busy_timeout}
} {400}
do_test lock-2.9 {
  db2 timeout 0
  execsql COMMIT
} {}
do_test lock-2.9b {
  db2 eval {PRAGMA busy_timeout}
} {0}
integrity_check lock-2.10
do_test lock-2.11 {
  db2 eval {PRAGMA busy_timeout(400)}
  execsql BEGIN
  execsql {UPDATE t1 SET a = 0 WHERE 0}
  catchsql {BEGIN EXCLUSIVE;} db2
} {1 {database is locked}}
do_test lock-2.11b {
  db2 eval {PRAGMA busy_timeout}
} {400}
do_test lock-2.12 {
  db2 eval {PRAGMA busy_timeout(0)}
  execsql COMMIT
} {}
do_test lock-2.12b {
  db2 eval {PRAGMA busy_timeout}
} {0}
integrity_check lock-2.13

# Try to start two transactions in a row
#
do_test lock-3.1 {
  execsql {BEGIN TRANSACTION}
  set r [catch {execsql {BEGIN TRANSACTION}} msg]
  execsql {ROLLBACK}

# 2012 Sept 27
#
# 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 of this file is testing that the optimizations that disable
# ORDER BY clauses when the natural order of a query is correct.
#


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

# Generate test data for a join.  Verify that the join gets the
# correct answer.
#
do_test 1.0 {
  db eval {
    BEGIN;
    CREATE TABLE album(
      aid INTEGER PRIMARY KEY,
      title TEXT UNIQUE NOT NULL
    );
    CREATE TABLE track(
      tid INTEGER PRIMARY KEY,
      aid INTEGER NOT NULL REFERENCES album,
      tn INTEGER NOT NULL,
      name TEXT,
      UNIQUE(aid, tn)
    );
    INSERT INTO album VALUES(1, '1-one'), (2, '2-two'), (3, '3-three');
    INSERT INTO track VALUES
        (NULL, 1, 1, 'one-a'),
        (NULL, 2, 2, 'two-b'),
        (NULL, 3, 3, 'three-c'),
        (NULL, 1, 3, 'one-c'),
        (NULL, 2, 1, 'two-a'),
        (NULL, 3, 1, 'three-a');
    COMMIT;
  }
} {}
do_test 1.1a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {one-a one-c two-a two-b three-a three-c}

# Verify that the ORDER BY clause is optimized out
#
do_test 1.1b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {~/ORDER BY/}  ;# ORDER BY optimized out

# The same query with ORDER BY clause optimization disabled via + operators
# should give exactly the same answer.
#
do_test 1.2a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn
  }
} {one-a one-c two-a two-b three-a three-c}

# The output is sorted manually in this case.
#
do_test 1.2b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn
  }
} {/ORDER BY/}   ;# separate sorting pass due to "+" on ORDER BY terms

# The same query with ORDER BY optimizations turned off via built-in test.
#
do_test 1.3a {
  optimization_control db order-by-idx-join 0
  db cache flush
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {one-a one-c two-a two-b three-a three-c}
do_test 1.3b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {/ORDER BY/}   ;# separate sorting pass due to disabled optimization
optimization_control db all 1
db cache flush

# Reverse order sorts
#
do_test 1.4a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
  }
} {three-a three-c two-a two-b one-a one-c}
do_test 1.4b {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn
  }
} {three-a three-c two-a two-b one-a one-c}  ;# verify same order after sorting
do_test 1.4c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
  }
} {/ORDER BY/}  ;# separate sorting pass due to mixed DESC/ASC


do_test 1.5a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {one-c one-a two-b two-a three-c three-a}
do_test 1.5b {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC
  }
} {one-c one-a two-b two-a three-c three-a}  ;# verify same order after sorting
do_test 1.5c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {/ORDER BY/}  ;# separate sorting pass due to mixed DESC/ASC

do_test 1.6a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
  }
} {three-c three-a two-b two-a one-c one-a}
do_test 1.6b {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn DESC
  }
} {three-c three-a two-b two-a one-c one-a}  ;# verify same order after sorting
do_test 1.6c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
  }
} {~/ORDER BY/}  ;# ORDER BY optimized-out


# Reconstruct the test data to use indices rather than integer primary keys.
#
do_test 2.0 {
  db eval {
    BEGIN;
    DROP TABLE album;
    DROP TABLE track;
    CREATE TABLE album(
      aid INT PRIMARY KEY,
      title TEXT NOT NULL
    );
    CREATE INDEX album_i1 ON album(title, aid);
    CREATE TABLE track(
      aid INTEGER NOT NULL REFERENCES album,
      tn INTEGER NOT NULL,
      name TEXT,
      UNIQUE(aid, tn)
    );
    INSERT INTO album VALUES(1, '1-one'), (20, '2-two'), (3, '3-three');
    INSERT INTO track VALUES
        (1,  1, 'one-a'),
        (20, 2, 'two-b'),
        (3,  3, 'three-c'),
        (1,  3, 'one-c'),
        (20, 1, 'two-a'),
        (3,  1, 'three-a');
    COMMIT;
  }
} {}
do_test 2.1a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {one-a one-c two-a two-b three-a three-c}

# Verify that the ORDER BY clause is optimized out
#
do_test 2.1b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {~/ORDER BY/}  ;# ORDER BY optimized out

do_test 2.1c {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, aid, tn
  }
} {one-a one-c two-a two-b three-a three-c}
do_test 2.1d {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, aid, tn
  }
} {~/ORDER BY/}  ;# ORDER BY optimized out

# The same query with ORDER BY clause optimization disabled via + operators
# should give exactly the same answer.
#
do_test 2.2a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn
  }
} {one-a one-c two-a two-b three-a three-c}

# The output is sorted manually in this case.
#
do_test 2.2b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn
  }
} {/ORDER BY/}   ;# separate sorting pass due to "+" on ORDER BY terms

# The same query with ORDER BY optimizations turned off via built-in test.
#
do_test 2.3a {
  optimization_control db order-by-idx-join 0
  db cache flush
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {one-a one-c two-a two-b three-a three-c}
do_test 2.3b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {/ORDER BY/}   ;# separate sorting pass due to disabled optimization
optimization_control db all 1
db cache flush

# Reverse order sorts
#
do_test 2.4a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
  }
} {three-a three-c two-a two-b one-a one-c}
do_test 2.4b {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn
  }
} {three-a three-c two-a two-b one-a one-c}  ;# verify same order after sorting
do_test 2.4c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
  }
} {/ORDER BY/}  ;# separate sorting pass due to mixed DESC/ASC


do_test 2.5a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {one-c one-a two-b two-a three-c three-a}
do_test 2.5b {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC
  }
} {one-c one-a two-b two-a three-c three-a}  ;# verify same order after sorting
do_test 2.5c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {/ORDER BY/}  ;# separate sorting pass due to mixed ASC/DESC

do_test 2.6a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
  }
} {three-c three-a two-b two-a one-c one-a}
do_test 2.6b {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn DESC
  }
} {three-c three-a two-b two-a one-c one-a}  ;# verify same order after sorting
do_test 2.6c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
  }
} {~/ORDER BY/}  ;# ORDER BY optimized out


# Generate another test dataset, but this time using mixed ASC/DESC indices.
#
do_test 3.0 {
  db eval {
    BEGIN;
    DROP TABLE album;
    DROP TABLE track;
    CREATE TABLE album(
      aid INTEGER PRIMARY KEY,
      title TEXT UNIQUE NOT NULL
    );
    CREATE TABLE track(
      tid INTEGER PRIMARY KEY,
      aid INTEGER NOT NULL REFERENCES album,
      tn INTEGER NOT NULL,
      name TEXT,
      UNIQUE(aid ASC, tn DESC)
    );
    INSERT INTO album VALUES(1, '1-one'), (2, '2-two'), (3, '3-three');
    INSERT INTO track VALUES
        (NULL, 1, 1, 'one-a'),
        (NULL, 2, 2, 'two-b'),
        (NULL, 3, 3, 'three-c'),
        (NULL, 1, 3, 'one-c'),
        (NULL, 2, 1, 'two-a'),
        (NULL, 3, 1, 'three-a');
    COMMIT;
  }
} {}
do_test 3.1a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {one-c one-a two-b two-a three-c three-a}

# Verify that the ORDER BY clause is optimized out
#
do_test 3.1b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {~/ORDER BY/}  ;# ORDER BY optimized out

# The same query with ORDER BY clause optimization disabled via + operators
# should give exactly the same answer.
#
do_test 3.2a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC
  }
} {one-c one-a two-b two-a three-c three-a}

# The output is sorted manually in this case.
#
do_test 3.2b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC
  }
} {/ORDER BY/}   ;# separate sorting pass due to "+" on ORDER BY terms

# The same query with ORDER BY optimizations turned off via built-in test.
#
do_test 3.3a {
  optimization_control db order-by-idx-join 0
  db cache flush
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {one-c one-a two-b two-a three-c three-a}
do_test 3.3b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
  }
} {/ORDER BY/}   ;# separate sorting pass due to disabled optimization
optimization_control db all 1
db cache flush

# Without the mixed ASC/DESC on ORDER BY
#
do_test 3.4a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {one-a one-c two-a two-b three-a three-c}
do_test 3.4b {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn
  }
} {one-a one-c two-a two-b three-a three-c}  ;# verify same order after sorting
do_test 3.4c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  }
} {/ORDER BY/}  ;# separate sorting pass due to mismatched DESC/ASC


do_test 3.5a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
  }
} {three-c three-a two-b two-a one-c one-a}
do_test 3.5b {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn DESC
  }
} {three-c three-a two-b two-a one-c one-a}  ;# verify same order after sorting
do_test 3.5c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
  }
} {/ORDER BY/}  ;# separate sorting pass due to mismatched ASC/DESC


do_test 3.6a {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
  }
} {three-a three-c two-a two-b one-a one-c}
do_test 3.6b {
  db eval {
    SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn
  }
} {three-a three-c two-a two-b one-a one-c}  ;# verify same order after sorting
do_test 3.6c {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
  }
} {~/ORDER BY/}  ;# inverted ASC/DESC is optimized out


finish_test

# 2012 Sept 27
#
# 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 of this file is testing that the optimizations that disable
# ORDER BY clauses when the natural order of a query is correct.
#


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

# Generate test data for a join.  Verify that the join gets the
# correct answer.
#
do_test 1.0 {
  db eval {
    CREATE TABLE t1(a INTEGER PRIMARY KEY, b);
    INSERT INTO t1 VALUES(1,11), (2,22);
    CREATE TABLE t2(d, e, UNIQUE(d,e));
    INSERT INTO t2 VALUES(10, 'ten'), (11,'eleven'), (12,'twelve'),
                         (11, 'oneteen');
  }
} {}

do_test 1.1a {
  db eval {
    SELECT e FROM t1, t2 WHERE a=1 AND d=b ORDER BY d, e;
  }
} {eleven oneteen}
do_test 1.1b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT e FROM t1, t2 WHERE a=1 AND d=b ORDER BY d, e;
  }
} {~/ORDER BY/}

do_test 1.2a {
  db eval {
    SELECT e FROM t1, t2 WHERE a=1 AND d=b ORDER BY e;
  }
} {eleven oneteen}
do_test 1.2b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT e FROM t1, t2 WHERE a=1 AND d=b ORDER BY e;
  }
} {~/ORDER BY/}

do_test 1.3a {
  db eval {
    SELECT e, b FROM t1, t2 WHERE a=1 ORDER BY d, e;
  }
} {ten 11 eleven 11 oneteen 11 twelve 11}
do_test 1.3b {
  db eval {
    EXPLAIN QUERY PLAN
    SELECT e, b FROM t1, t2 WHERE a=1 ORDER BY d, e;
  }
} {~/ORDER BY/}

# The following tests derived from TH3 test module cov1/where34.test
#
do_test 2.0 {
  db eval {
    CREATE TABLE t31(a,b); CREATE INDEX t31ab ON t31(a,b);
    CREATE TABLE t32(c,d); CREATE INDEX t32cd ON t32(c,d);
    CREATE TABLE t33(e,f); CREATE INDEX t33ef ON t33(e,f);
    CREATE TABLE t34(g,h); CREATE INDEX t34gh ON t34(g,h);
    
    INSERT INTO t31 VALUES(1,4), (2,3), (1,3);
    INSERT INTO t32 VALUES(4,5), (3,6), (3,7), (4,8);
    INSERT INTO t33 VALUES(5,9), (7,10), (6,11), (8,12), (8,13), (7,14);
    INSERT INTO t34 VALUES(11,20), (10,21), (12,22), (9,23), (13,24),
                          (14,25), (12,26);
    SELECT a||','||c||','||e||','||g FROM t31, t32, t33, t34
     WHERE c=b AND e=d AND g=f
     ORDER BY a ASC, c ASC, e DESC, g ASC;
  }
} {1,3,7,10 1,3,7,14 1,3,6,11 1,4,8,12 1,4,8,12 1,4,8,13 1,4,5,9 2,3,7,10 2,3,7,14 2,3,6,11}
do_test 2.1 {
  db eval {
    SELECT a||','||c||','||e||','||g FROM t31, t32, t33, t34
     WHERE c=b AND e=d AND g=f
     ORDER BY +a ASC, +c ASC, +e DESC, +g ASC;
  }
} {1,3,7,10 1,3,7,14 1,3,6,11 1,4,8,12 1,4,8,12 1,4,8,13 1,4,5,9 2,3,7,10 2,3,7,14 2,3,6,11}
do_test 2.2 {
  db eval {
    SELECT a||','||c||','||e||','||g FROM t31, t32, t33, t34
     WHERE c=b AND e=d AND g=f
     ORDER BY a ASC, c ASC, e ASC, g ASC;
  }
} {1,3,6,11 1,3,7,10 1,3,7,14 1,4,5,9 1,4,8,12 1,4,8,12 1,4,8,13 2,3,6,11 2,3,7,10 2,3,7,14}
do_test 2.3 {
  optimization_control db cover-idx-scan off
  db cache flush
  db eval {
    SELECT a||','||c||','||e||','||g FROM t31, t32, t33, t34
     WHERE c=b AND e=d AND g=f
     ORDER BY a ASC, c ASC, e ASC, g ASC;
  }
} {1,3,6,11 1,3,7,10 1,3,7,14 1,4,5,9 1,4,8,12 1,4,8,12 1,4,8,13 2,3,6,11 2,3,7,10 2,3,7,14}  
optimization_control db all on
db cache flush



finish_test

# modify and reset the NULL representation
#
do_test tcl-8.1 {
  db nullvalue NaN
  execsql {INSERT INTO t1 VALUES(30,NULL)}
  db eval {SELECT * FROM t1 WHERE b IS NULL}
} {30 NaN}
proc concatFunc args {return [join $args {}]}
do_test tcl-8.2 {
  db function concat concatFunc
  db eval {SELECT concat('a', b, 'z') FROM t1 WHERE b is NULL}
} {aNaNz}
do_test tcl-8.3 {
  db nullvalue NULL
  db nullvalue
} {NULL}
do_test tcl-8.4 {
  db nullvalue {}
  db eval {SELECT * FROM t1 WHERE b IS NULL}
} {30 {}}
do_test tcl-8.5 {
  db function concat concatFunc
  db eval {SELECT concat('a', b, 'z') FROM t1 WHERE b is NULL}
} {az}

# Test the return type of user-defined functions
#
do_test tcl-9.1 {
  db function ret_str {return "hi"}
  execsql {SELECT typeof(ret_str())}
} {text}

  if {![info exists ::G(match)] || [string match $::G(match) $name]} {
    if {[catch {uplevel #0 "$cmd;\n"} result]} {
      puts "\nError: $result"
      fail_test $name
    } else {
      if {[regexp {^~?/.*/$} $expected]} {
        if {[string index $expected 0]=="~"} {
          set re [string map {# {[-0-9.]+}} [string range $expected 2 end-1]]
          set ok [expr {![regexp $re $result]}]
        } else {
          set re [string map {# {[-0-9.]+}} [string range $expected 1 end-1]]
          set ok [regexp $re $result]
        }
      } else {
        set ok [expr {[string compare $result $expected]==0}]
      }
      if {!$ok} {
        # if {![info exists ::testprefix] || $::testprefix eq ""} {

do_test tkt-cbd05-1.3 {
  execsql { 
    SELECT tbl,idx,group_concat(sample,' ') 
    FROM sqlite_stat3 
    WHERE idx = 't1_x' 
    GROUP BY tbl,idx
  }
} {/t1 t1_x .[ ABCDEFGHI]{10}./}

do_test tkt-cbd05-2.1 {
  db eval {
    DROP TABLE t1;
    CREATE TABLE t1(a INTEGER PRIMARY KEY, b BLOB UNIQUE NOT NULL);
    CREATE INDEX t1_x ON t1(b);
    INSERT INTO t1 VALUES(NULL, X'');

do_test tkt-cbd05-2.3 {
  execsql { 
    SELECT tbl,idx,group_concat(sample,' ') 
    FROM sqlite_stat3 
    WHERE idx = 't1_x' 
    GROUP BY tbl,idx
  }
} {/t1 t1_x .[ ABCDEFGHI]{10}./}

finish_test

    CREATE TABLE t8(a INTEGER PRIMARY KEY, b TEXT UNIQUE);
    INSERT INTO t8 VALUES(1,'one');
    INSERT INTO t8 VALUES(4,'four');
  }
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.a, y.b
  } 
} {1/4 1/1 4/4 4/1 nosort}
do_test where-14.2 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.a, y.b DESC
  } 
} {1/1 1/4 4/1 4/4 nosort}
do_test where-14.3 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.a, x.b
  } 
} {1/4 1/1 4/4 4/1 nosort}
do_test where-14.4 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.a, x.b DESC
  } 
} {1/4 1/1 4/4 4/1 nosort}
do_test where-14.5 {
  # This test case changed from "nosort" to "sort". See ticket 2a5629202f.
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a||x.b
  } 
} {/4/[14] 4/[14] 1/[14] 1/[14] sort/}
do_test where-14.6 {
  # This test case changed from "nosort" to "sort". See ticket 2a5629202f.
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, x.a||x.b DESC
  } 
} {/4/[14] 4/[14] 1/[14] 1/[14] sort/}
do_test where-14.7 {
  cksort {
    SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.b, y.a||y.b
  } 
} {4/1 4/4 1/1 1/4 sort}
do_test where-14.7.1 {
  cksort {