SQLite

        delete.lo expr.lo fault.lo func.lo global.lo \
        hash.lo journal.lo insert.lo legacy.lo loadext.lo \
        main.lo malloc.lo mem0.lo mem1.lo mem2.lo mem3.lo mem5.lo \
        memjournal.lo \
        mutex.lo mutex_noop.lo mutex_os2.lo mutex_unix.lo mutex_w32.lo \
        notify.lo opcodes.lo os.lo os_unix.lo os_win.lo os_os2.lo \
        pager.lo parse.lo pcache.lo pcache1.lo pragma.lo prepare.lo printf.lo \
        random.lo resolve.lo rowhash.lo rowset.lo select.lo status.lo \
        table.lo tokenize.lo trigger.lo update.lo \
        util.lo vacuum.lo \
        vdbe.lo vdbeapi.lo vdbeaux.lo vdbeblob.lo vdbemem.lo \
        walker.lo where.lo utf.lo vtab.lo

# Object files for the amalgamation.
#

  $(TOP)/src/pcache.h \
  $(TOP)/src/pcache1.c \
  $(TOP)/src/pragma.c \
  $(TOP)/src/prepare.c \
  $(TOP)/src/printf.c \
  $(TOP)/src/random.c \
  $(TOP)/src/resolve.c \
  $(TOP)/src/rowhash.c \
  $(TOP)/src/rowset.c \
  $(TOP)/src/select.c \
  $(TOP)/src/status.c \
  $(TOP)/src/shell.c \
  $(TOP)/src/sqlite.h.in \
  $(TOP)/src/sqlite3ext.h \
  $(TOP)/src/sqliteInt.h \

random.lo:	$(TOP)/src/random.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/random.c

resolve.lo:	$(TOP)/src/resolve.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/resolve.c

rowhash.lo:	$(TOP)/src/rowhash.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/rowhash.c

rowset.lo:	$(TOP)/src/rowset.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/rowset.c

select.lo:	$(TOP)/src/select.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/select.c

status.lo:	$(TOP)/src/status.c $(HDR)

         func.o global.o hash.o \
         icu.o insert.o journal.o legacy.o loadext.o \
         main.o malloc.o mem0.o mem1.o mem2.o mem3.o mem5.o \
         memjournal.o \
         mutex.o mutex_noop.o mutex_os2.o mutex_unix.o mutex_w32.o \
         notify.o opcodes.o os.o os_os2.o os_unix.o os_win.o \
         pager.o parse.o pcache.o pcache1.o pragma.o prepare.o printf.o \
         random.o resolve.o rowhash.o rowset.o rtree.o select.o status.o \
         table.o tokenize.o trigger.o \
         update.o util.o vacuum.o \
         vdbe.o vdbeapi.o vdbeaux.o vdbeblob.o vdbemem.o \
         walker.o where.o utf.o vtab.o

  $(TOP)/src/pcache.h \
  $(TOP)/src/pcache1.c \
  $(TOP)/src/pragma.c \
  $(TOP)/src/prepare.c \
  $(TOP)/src/printf.c \
  $(TOP)/src/random.c \
  $(TOP)/src/resolve.c \
  $(TOP)/src/rowhash.c \
  $(TOP)/src/rowset.c \
  $(TOP)/src/select.c \
  $(TOP)/src/status.c \
  $(TOP)/src/shell.c \
  $(TOP)/src/sqlite.h.in \
  $(TOP)/src/sqlite3ext.h \
  $(TOP)/src/sqliteInt.h \

/*
** 2009 April 15
**
** 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 contains the implementation of the "row-hash" data structure.
**
** $Id: rowhash.c,v 1.1 2009/04/21 09:02:47 danielk1977 Exp $
*/
#include "sqliteInt.h"

typedef struct RowHashElem RowHashElem;
typedef struct RowHashBlock RowHashBlock;

/*
** Size of heap allocations made by this module. This limit is 
** never exceeded.
*/
#define ROWHASH_ALLOCATION 1024

/*
** Number of elements in the RowHashBlock.aElem[] array. This array is
** sized to make RowHashBlock very close to (without exceeding)
** ROWHASH_ALLOCATION bytes in size.
*/
#define ROWHASH_ELEM_PER_BLOCK (                                            \
    (ROWHASH_ALLOCATION - ROUND8(sizeof(struct RowHashBlockData))) /        \
    sizeof(RowHashElem)                                                     \
)

/*
** Number of pointers that fit into a single allocation of 
** ROWHASH_ALLOCATION bytes.
*/
#define ROWHASH_POINTER_PER_PAGE (ROWHASH_ALLOCATION/sizeof(void *))

/*
** If there are less than this number of elements in the block-list, do not
** bother building a hash-table. Just do a linear search of the list when
** querying.
*/
#define ROWHASH_LINEAR_SEARCH_LIMIT 10

/*
** Element stored in the hash-table.
*/
struct RowHashElem {
  i64 iVal;
  RowHashElem *pNext;
};

/*
** The following structure is either exactly ROWHASH_ALLOCATION bytes in
** size or just slightly less. It stores up to ROWHASH_ELEM_PER_BLOCK 
** RowHashElem structures.
*/
struct RowHashBlock {
  struct RowHashBlockData {
    int nElem;
    RowHashBlock *pNext;
  } data;
  RowHashElem aElem[ROWHASH_ELEM_PER_BLOCK];
};

/*
** RowHash structure. References to a structure of this type are passed
** around and used as opaque handles by code in other modules.
*/
struct RowHash {
  /* Variables populated by sqlite3RowhashInsert() */
  int nEntry;               /* Total number of entries in block-list */
  RowHashBlock *pBlock;     /* Linked list of entries */

  /* Variables populated by makeHashTable() */
  int iSet;                 /* Most recent iSet parameter passed to Test() */
  int iMod;                 /* Number of buckets in hash table */
  int nLeaf;                /* Number of leaf pages in hash table */
  int nHeight;              /* Height of tree containing leaf pages */
  void *pHash;              /* Pointer to root of tree */
  int nLinearLimit;         /* Linear search limit (used if pHash==0) */
};


/*
** Allocate a tree of height nHeight with *pnLeaf leaf pages. Set *pp to
** point to the root of the tree. If the maximum number of leaf pages in a
** tree of height nHeight is less than *pnLeaf, allocate a tree with the 
** maximum possible number of leaves for height nHeight. 
**
** Before returning, subtract the number of leaves in the tree allocated
** from *pnLeaf.
**
** This routine returns SQLITE_NOMEM if a malloc() fails, or SQLITE_OK
** otherwise.
*/
static int allocTable(void **pp, int nHeight, int *pnLeaf){
  void **ap = (void **)sqlite3MallocZero(ROWHASH_ALLOCATION);
  if( !ap ){
    return SQLITE_NOMEM;
  }
  *pp = (void *)ap;
  if( nHeight==0 ){
    (*pnLeaf)--;
  }else{
    int ii;
    for(ii=0; ii<ROWHASH_POINTER_PER_PAGE && *pnLeaf>0; ii++){
      if( allocTable(&ap[ii], nHeight-1, pnLeaf) ){
        return SQLITE_NOMEM;
      }
    }
  }
  return SQLITE_OK;
}

/*
** Delete the tree of height nHeight passed as the first argument.
*/
static void deleteTable(void **ap, int nHeight){
  if( ap ){
    if( nHeight>0 ){
      int ii;
      for(ii=0; ii<ROWHASH_POINTER_PER_PAGE; ii++){
        deleteTable((void **)ap[ii], nHeight-1);
      }
    }
    sqlite3_free(ap);
  }
}

/*
** Delete the hash-table stored in p->pHash. The p->pHash pointer is
** set to zero before returning. This function is the inverse of 
** allocHashTable()
*/
static void deleteHashTable(RowHash *p){
  deleteTable(p->pHash, p->nHeight);
  p->pHash = 0;
}

/*
** Allocate the hash table structure based on the current values of
** p->nLeaf and p->nHeight.
*/
static int allocHashTable(RowHash *p){
  int nLeaf = p->nLeaf;
  assert( p->pHash==0 );
  assert( p->nLeaf>0 );
  return allocTable(&p->pHash, p->nHeight, &nLeaf);
}

/*
** Find the hash-bucket associated with value iVal. Return a pointer to it.
*/
static void **findHashBucket(RowHash *p, i64 iVal){
  int aOffset[16];
  int n = p->nHeight;
  void **ap = p->pHash;
  int h = (((u64)iVal) % p->iMod);
  for(n=0; n<p->nHeight; n++){
    int h1 = h / ROWHASH_POINTER_PER_PAGE;
    aOffset[n] = h - (h1 * ROWHASH_POINTER_PER_PAGE);
    h = h1;
  }
  aOffset[n] = h;
  for(n=p->nHeight; n>0; n--){
    ap = (void **)ap[aOffset[n]];
  }
  return &ap[aOffset[0]];
}

/*
** Build a hash table to query with sqlite3RowhashTest() based on the
** set of values stored in the linked list of RowHashBlock structures.
*/
static int makeHashTable(RowHash *p, int iSet){
  RowHashBlock *pBlock;
  int iMod;
  int nLeaf;
  
  /* Delete the old hash table. */
  deleteHashTable(p);
  assert( p->iSet!=iSet );
  p->iSet = iSet;

  if( p->nEntry<ROWHASH_LINEAR_SEARCH_LIMIT ){
    p->nLinearLimit = p->nEntry;
    return SQLITE_OK;
  }

  /* Determine how many leaves the hash-table will comprise. */
  nLeaf = 1 + (p->nEntry / ROWHASH_POINTER_PER_PAGE);
  iMod = nLeaf*ROWHASH_POINTER_PER_PAGE;
  p->nLeaf = nLeaf;
  p->iMod = iMod;

  /* Set nHeight to the height of the tree that contains the leaf pages. If
  ** RowHash.nHeight is zero, then the whole hash-table fits on a single
  ** leaf. If RowHash.nHeight is 1, then RowHash.pHash points to an array
  ** of pointers to leaf pages. If 2, pHash points to an array of pointers
  ** to arrays of pointers to leaf pages. And so on.
  */
  p->nHeight = 0;
  while( nLeaf>1 ){
    nLeaf = (nLeaf+ROWHASH_POINTER_PER_PAGE-1) / ROWHASH_POINTER_PER_PAGE;
    p->nHeight++;
  }

  /* Allocate the hash-table. */
  if( allocHashTable(p) ){
    return SQLITE_NOMEM;
  }

  /* Insert all values into the hash-table. */
  for(pBlock=p->pBlock; pBlock; pBlock=pBlock->data.pNext){
    RowHashElem * const pEnd = &pBlock->aElem[pBlock->data.nElem];
    RowHashElem *pIter;
    for(pIter=pBlock->aElem; pIter<pEnd; pIter++){
      RowHashElem **ppElem = (RowHashElem **)findHashBucket(p, pIter->iVal);
      pIter->pNext = *ppElem;
      *ppElem = pIter;
    }
  }

  return SQLITE_OK;
}

/*
** Test if value iVal is in the hash table. If so, set *pExists to 1
** before returning. If iVal is not in the hash table, set *pExists to 0.
**
** Return SQLITE_OK if all goes as planned. If a malloc() fails, return
** SQLITE_NOMEM.
*/
int sqlite3RowhashTest(RowHash *p, int iSet, i64 iVal, int *pExists){
  *pExists = 0;
  if( p ){
    assert( p->pBlock );
    if( iSet!=p->iSet && makeHashTable(p, iSet) ){
      return SQLITE_NOMEM;
    }
    if( p->pHash ){
      RowHashElem *pElem = *(RowHashElem **)findHashBucket(p, iVal);
      for(; pElem; pElem=pElem->pNext){
        if( pElem->iVal==iVal ){
          *pExists = 1;
          break;
        }
      }
    }else{
      int ii;
      RowHashElem *aElem = p->pBlock->aElem;
      for(ii=0; ii<p->nLinearLimit; ii++){
        if( aElem[ii].iVal==iVal ){
          *pExists = 1;
          break;
        }
      }
    }
  }
  return SQLITE_OK;
}

/*
** Insert value iVal into the RowHash object.
**
** Return SQLITE_OK if all goes as planned. If a malloc() fails, return
** SQLITE_NOMEM.
*/
int sqlite3RowhashInsert(RowHash **pp, i64 iVal){
  RowHash *p = *pp;
  
  /* If the RowHash structure has not been allocated, allocate it now. */
  if( !p ){
    p = (RowHash*)sqlite3MallocZero(sizeof(RowHash));
    if( !p ){
      return SQLITE_NOMEM;
    }
    *pp = p;
  }

  /* If the current RowHashBlock is full, or if the first RowHashBlock has
  ** not yet been allocated, allocate one now. */ 
  if( !p->pBlock || p->pBlock->data.nElem==ROWHASH_ELEM_PER_BLOCK ){
    RowHashBlock *pBlock = (RowHashBlock*)sqlite3Malloc(sizeof(RowHashBlock));
    if( !pBlock ){
      return SQLITE_NOMEM;
    }
    pBlock->data.nElem = 0;
    pBlock->data.pNext = p->pBlock;
    p->pBlock = pBlock;
  }

  /* Add iVal to the current RowHashBlock. */
  p->pBlock->aElem[p->pBlock->data.nElem].iVal = iVal;
  p->pBlock->data.nElem++;
  p->nEntry++;
  return SQLITE_OK;
}

/*
** Destroy the RowHash object passed as the first argument.
*/
void sqlite3RowhashDestroy(RowHash *p){
  if( p ){
    RowHashBlock *pBlock, *pNext;
    deleteHashTable(p);
    for(pBlock=p->pBlock; pBlock; pBlock=pNext){
      pNext = pBlock->data.pNext;
      sqlite3_free(pBlock);
    }
    sqlite3_free(p);
  }
}

/*
** 2001 September 15
**
** 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.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.855 2009/04/21 09:02:47 danielk1977 Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Include the configuration header output by 'configure' if we're using the
** autoconf-based build

/*
** Forward references to structures
*/
typedef struct AggInfo AggInfo;
typedef struct AuthContext AuthContext;
typedef struct Bitvec Bitvec;
typedef struct RowHash RowHash;
typedef struct RowSet RowSet;
typedef struct CollSeq CollSeq;
typedef struct Column Column;
typedef struct Db Db;
typedef struct Schema Schema;
typedef struct Expr Expr;
typedef struct ExprList ExprList;

#define WHERE_ORDERBY_NORMAL   0x0000 /* No-op */
#define WHERE_ORDERBY_MIN      0x0001 /* ORDER BY processing for min() func */
#define WHERE_ORDERBY_MAX      0x0002 /* ORDER BY processing for max() func */
#define WHERE_ONEPASS_DESIRED  0x0004 /* Want to do one-pass UPDATE/DELETE */
#define WHERE_FILL_ROWSET      0x0008  /* Save results in a RowSet object */
#define WHERE_OMIT_OPEN        0x0010  /* Table cursor are already open */
#define WHERE_OMIT_CLOSE       0x0020  /* Omit close of table & index cursors */
#define WHERE_FILL_ROWHASH     0x0040  /* Save results in a RowHash object */

/*
** The WHERE clause processing routine has two halves.  The
** first part does the start of the WHERE loop and the second
** half does the tail of the WHERE loop.  An instance of
** this structure is returned by the first half and passed
** into the second half to give some continuity.
*/
struct WhereInfo {
  Parse *pParse;       /* Parsing and code generating context */
  u16 wctrlFlags;      /* Flags originally passed to sqlite3WhereBegin() */
  u8 okOnePass;        /* Ok to use one-pass algorithm for UPDATE or DELETE */
  int regRowSet;                 /* Store rowids in this rowset/rowhash */
  int iRowidHandler;             /* Address of OP_RowSet or OP_RowHash */
  SrcList *pTabList;             /* List of tables in the join */
  int iTop;                      /* The very beginning of the WHERE loop */
  int iContinue;                 /* Jump here to continue with next record */
  int iBreak;                    /* Jump here to break out of the loop */
  int nLevel;                    /* Number of nested loop */
  struct WhereClause *pWC;       /* Decomposition of the WHERE clause */
  WhereLevel a[1];               /* Information about each nest loop in WHERE */

u32 sqlite3BitvecSize(Bitvec*);
int sqlite3BitvecBuiltinTest(int,int*);

RowSet *sqlite3RowSetInit(sqlite3*, void*, unsigned int);
void sqlite3RowSetClear(RowSet*);
void sqlite3RowSetInsert(RowSet*, i64);
int sqlite3RowSetNext(RowSet*, i64*);

int sqlite3RowhashInsert(RowHash **pp, i64 iVal);
int sqlite3RowhashTest(RowHash *p, int iSet, i64 iVal, int *pExists);
void sqlite3RowhashDestroy(RowHash *p);

void sqlite3CreateView(Parse*,Token*,Token*,Token*,Select*,int,int);

#if !defined(SQLITE_OMIT_VIEW) || !defined(SQLITE_OMIT_VIRTUALTABLE)
  int sqlite3ViewGetColumnNames(Parse*,Table*);
#else
# define sqlite3ViewGetColumnNames(A,B) 0

**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the virtual table interfaces.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test8.c,v 1.77 2009/04/21 09:02:47 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>

#ifndef SQLITE_OMIT_VIRTUALTABLE

  if( !zQuery ){
    return rc;
  }
  pIdxInfo->idxNum = hashString(zQuery);
  pIdxInfo->idxStr = zQuery;
  pIdxInfo->needToFreeIdxStr = 1;
  if( useCost ){
    pIdxInfo->estimatedCost = cost;
  }else if( useIdx ){
    /* Approximation of log2(nRow). */
    for( ii=0; ii<(sizeof(int)*8); ii++ ){
      if( nRow & (1<<ii) ){
        pIdxInfo->estimatedCost = (double)ii;
      }
    }
  }else{
    pIdxInfo->estimatedCost = (double)nRow;
  }
  return rc;
}

/*
** The xUpdate method for echo module virtual tables.

**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.833 2009/04/21 09:02:47 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "vdbeInt.h"

/*
** The following global variable is incremented every time a cursor
** moves, either by the OP_SeekXX, OP_Next, or OP_Prev opcodes.  The test

    assert( p->apCsr[i]->isTable );
    iKey = intToKey(pIn3->u.i);
    rc = sqlite3BtreeMovetoUnpacked(pCrsr, 0, iKey, 0,&res);
    pC->lastRowid = pIn3->u.i;
    pC->rowidIsValid = res==0 ?1:0;
    pC->nullRow = 0;
    pC->cacheStatus = CACHE_STALE;
    pC->deferredMoveto = 0;
    if( res!=0 ){
      pc = pOp->p2 - 1;
      assert( pC->rowidIsValid==0 );
    }
  }else if( !pC->pseudoTable ){
    /* This happens when an attempt to open a read cursor on the 
    ** sqlite_master table returns SQLITE_EMPTY.

  }else{
    /* A value was pulled from the index */
    assert( pOp->p3>0 && pOp->p3<=p->nMem );
    sqlite3VdbeMemSetInt64(pOut, val);
  }
  break;
}

/* Opcode: RowHash P1 P2 P3 P4
**
** Register P3 is assumed to hold an integer value. If register P1
** contains a rowid-hash object and the rowid-hash object contains
** the value held in P3, jump to register P2. Otherwise, insert the
** integer in P3 into the rowid-hash container.
**
** The rowid-hash is optimized for the case where successive sets
** of integers, where each set contains no duplicates. Each set
** of values is identified by a unique P4 value. The first set
** must have P4==0, the final set P4=-1.
**
** This allows optimizations: (a) when P4==0 there is no need to test
** the row-hash object for P3, as it is guaranteed not to contain it,
** (b) when P4==-1 there is no need to insert the value, as it will
** never be tested for, and (c) when a value that is part of set X is
** inserted, there is no need to search to see if the same value was
** previously inserted as part of set X (only if it was previously
** inserted as part of some other set).
*/
case OP_RowHash: {                     /* jump, in1, in3 */
  int iSet = pOp->p4.i;
  assert( pIn3->flags&MEM_Int );

  /* If there is anything other than a row-hash object in memory cell P1,
  ** delete it now and initialize P1 with an empty row-hash (a null pointer
  ** is an acceptable representation of an empty row-hash).
  */
  if( (pIn1->flags & MEM_RowHash)==0 ){
    sqlite3VdbeMemReleaseExternal(pIn1);
    pIn1->u.pRowHash = 0;
    pIn1->flags = MEM_RowHash;
  }

  assert( pOp->p4type==P4_INT32 );
  if( iSet ){
    int exists;
    rc = sqlite3RowhashTest(pIn1->u.pRowHash, pOp->p4.i, pIn3->u.i, &exists);
    if( exists ){
      pc = pOp->p2 - 1;
      break;
    }
  }
  if( iSet>=0 ){
    rc = sqlite3RowhashInsert(&pIn1->u.pRowHash, pIn3->u.i);
  }
  break;
}


#ifndef SQLITE_OMIT_TRIGGER
/* Opcode: ContextPush * * * 
**
** Save the current Vdbe context such that it can be restored by a ContextPop
** opcode. The context stores the last insert row id, the last statement change

*************************************************************************
** This is the header file for information that is private to the
** VDBE.  This information used to all be at the top of the single
** source code file "vdbe.c".  When that file became too big (over
** 6000 lines long) it was split up into several smaller files and
** this header information was factored out.
**
** $Id: vdbeInt.h,v 1.168 2009/04/21 09:02:47 danielk1977 Exp $
*/
#ifndef _VDBEINT_H_
#define _VDBEINT_H_

/*
** intToKey() and keyToInt() used to transform the rowid.  But with
** the latest versions of the design they are no-ops.

*/
struct Mem {
  union {
    i64 i;              /* Integer value. */
    int nZero;          /* Used when bit MEM_Zero is set in flags */
    FuncDef *pDef;      /* Used only when flags==MEM_Agg */
    RowSet *pRowSet;    /* Used only when flags==MEM_RowSet */
    RowHash *pRowHash;  /* Used only when flags==MEM_RowHash */
  } u;
  double r;           /* Real value */
  sqlite3 *db;        /* The associated database connection */
  char *z;            /* String or BLOB value */
  int n;              /* Number of characters in string value, excluding '\0' */
  u16 flags;          /* Some combination of MEM_Null, MEM_Str, MEM_Dyn, etc. */
  u8  type;           /* One of SQLITE_NULL, SQLITE_TEXT, SQLITE_INTEGER, etc */

*/
#define MEM_Null      0x0001   /* Value is NULL */
#define MEM_Str       0x0002   /* Value is a string */
#define MEM_Int       0x0004   /* Value is an integer */
#define MEM_Real      0x0008   /* Value is a real number */
#define MEM_Blob      0x0010   /* Value is a BLOB */
#define MEM_RowSet    0x0020   /* Value is a RowSet object */
#define MEM_RowHash   0x0040   /* Value is a RowHash object */
#define MEM_TypeMask  0x00ff   /* Mask of type bits */

/* Whenever Mem contains a valid string or blob representation, one of
** the following flags must be set to determine the memory management
** policy for Mem.z.  The MEM_Term flag tells us whether or not the
** string is \000 or \u0000 terminated
*/

**
*************************************************************************
** This file contains code used for creating, destroying, and populating
** a VDBE (or an "sqlite3_stmt" as it is known to the outside world.)  Prior
** to version 2.8.7, all this code was combined into the vdbe.c source file.
** But that file was getting too big so this subroutines were split out.
**
** $Id: vdbeaux.c,v 1.452 2009/04/21 09:02:47 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "vdbeInt.h"



/*

  sqlite3 *db = p->db;
  Mem *pMem;
  closeAllCursorsExceptActiveVtabs(p);
  for(pMem=&p->aMem[1], i=1; i<=p->nMem; i++, pMem++){
    if( pMem->flags & MEM_RowSet ){
      sqlite3RowSetClear(pMem->u.pRowSet);
    }
    if( pMem->flags & MEM_RowHash ){
      sqlite3RowhashDestroy(pMem->u.pRowHash);
    }
    MemSetTypeFlag(pMem, MEM_Null);
  }
  releaseMemArray(&p->aMem[1], p->nMem);
  if( p->contextStack ){
    sqlite3DbFree(db, p->contextStack);
  }
  p->contextStack = 0;

*************************************************************************
**
** This file contains code use to manipulate "Mem" structure.  A "Mem"
** stores a single value in the VDBE.  Mem is an opaque structure visible
** only within the VDBE.  Interface routines refer to a Mem using the
** name sqlite_value
**
** $Id: vdbemem.c,v 1.141 2009/04/21 09:02:47 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "vdbeInt.h"

/*
** Call sqlite3VdbeMemExpandBlob() on the supplied value (type Mem*)
** P if required.

/*
** If the memory cell contains a string value that must be freed by
** invoking an external callback, free it now. Calling this function
** does not free any Mem.zMalloc buffer.
*/
void sqlite3VdbeMemReleaseExternal(Mem *p){
  assert( p->db==0 || sqlite3_mutex_held(p->db->mutex) );
  if( p->flags&(MEM_Agg|MEM_Dyn|MEM_RowSet|MEM_RowHash) ){
    if( p->flags&MEM_Agg ){
      sqlite3VdbeMemFinalize(p, p->u.pDef);
      assert( (p->flags & MEM_Agg)==0 );
      sqlite3VdbeMemRelease(p);
    }else if( p->flags&MEM_Dyn && p->xDel ){
      assert( (p->flags&MEM_RowSet)==0 );
      p->xDel((void *)p->z);
      p->xDel = 0;
    }else if( p->flags&MEM_RowSet ){
      sqlite3RowSetClear(p->u.pRowSet);
    }else if( p->flags&MEM_RowHash ){
      sqlite3RowhashDestroy(p->u.pRowHash);
      p->u.pRowHash = 0;
    }
  }
}

/*
** Release any memory held by the Mem. This may leave the Mem in an
** inconsistent state, for example with (Mem.z==0) and
** (Mem.type==SQLITE_TEXT).

** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is responsible for
** generating the code that loops through a table looking for applicable
** rows.  Indices are selected and used to speed the search when doing
** so is applicable.  Because this module is responsible for selecting
** indices, you might also think of this module as the "query optimizer".
**
** $Id: where.c,v 1.383 2009/04/21 09:02:47 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** Trace output macros
*/
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)

  sqlite3DebugPrintf("  orderByConsumed=%d\n", p->orderByConsumed);
  sqlite3DebugPrintf("  estimatedCost=%g\n", p->estimatedCost);
}
#else
#define TRACE_IDX_INPUTS(A)
#define TRACE_IDX_OUTPUTS(A)
#endif

/* 
** Required because bestIndex() is called by bestOrClauseIndex() 
*/
static void bestIndex(
    Parse*, WhereClause*, struct SrcList_item*, Bitmask, ExprList*, WhereCost*);

/*
** 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(
  Parse *pParse,              /* The parsing context */
  WhereClause *pWC,           /* The WHERE clause */
  struct SrcList_item *pSrc,  /* The FROM clause term to search */
  Bitmask notReady,           /* Mask of cursors that are not available */
  ExprList *pOrderBy,         /* The ORDER BY clause */
  WhereCost *pCost            /* Lowest cost query plan */
){
#ifndef SQLITE_OMIT_OR_OPTIMIZATION
  const int iCur = pSrc->iCursor;   /* The cursor of the table to be accessed */
  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 */

  /* 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) & 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;

      for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
        WhereCost sTermCost;
        WHERETRACE(("... Multi-index OR testing for term %d of %d....\n", 
          (pOrTerm - pOrWC->a), (pTerm - pWC->a)
        ));
        if( pOrTerm->eOperator==WO_AND ){
          WhereClause *pAndWC = &pOrTerm->u.pAndInfo->wc;
          bestIndex(pParse, pAndWC, pSrc, notReady, 0, &sTermCost);
        }else if( pOrTerm->leftCursor==iCur ){
          WhereClause tempWC;
          tempWC.pParse = pWC->pParse;
          tempWC.pMaskSet = pWC->pMaskSet;
          tempWC.op = TK_AND;
          tempWC.a = pOrTerm;
          tempWC.nTerm = 1;
          bestIndex(pParse, &tempWC, pSrc, notReady, 0, &sTermCost);
        }else{
          continue;
        }
        rTotal += sTermCost.rCost;
        nRow += sTermCost.nRow;
        if( rTotal>=pCost->rCost ) break;
      }

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

      /* 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<pCost->rCost ){
        pCost->rCost = rTotal;
        pCost->nRow = nRow;
        pCost->plan.wsFlags = flags;
        pCost->plan.u.pTerm = pTerm;
      }
    }
  }
#endif /* SQLITE_OMIT_OR_OPTIMIZATION */
}

#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(
  Parse *pParse, 
  WhereClause *pWC,
  struct SrcList_item *pSrc,
  ExprList *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;
  sqlite3_index_info *pIdxInfo;

  WHERETRACE(("Recomputing index info for %s...\n", pSrc->pTab->zName));

  /* Count the number of possible WHERE clause constraints referring
  ** to this virtual table */
  for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
    if( pTerm->leftCursor != pSrc->iCursor ) continue;
    assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
    testcase( pTerm->eOperator==WO_IN );
    testcase( pTerm->eOperator==WO_ISNULL );
    if( pTerm->eOperator & (WO_IN|WO_ISNULL) ) continue;
    nTerm++;
  }

  /* 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 ){
    for(i=0; i<pOrderBy->nExpr; i++){
      Expr *pExpr = pOrderBy->a[i].pExpr;
      if( pExpr->op!=TK_COLUMN || pExpr->iTable!=pSrc->iCursor ) break;
    }
    if( i==pOrderBy->nExpr ){
      nOrderBy = pOrderBy->nExpr;
    }
  }

  /* Allocate the sqlite3_index_info structure
  */
  pIdxInfo = sqlite3DbMallocZero(pParse->db, sizeof(*pIdxInfo)
                           + (sizeof(*pIdxCons) + sizeof(*pUsage))*nTerm
                           + sizeof(*pIdxOrderBy)*nOrderBy );
  if( pIdxInfo==0 ){
    sqlite3ErrorMsg(pParse, "out of memory");
    /* (double)0 In case of SQLITE_OMIT_FLOATING_POINT... */
    return 0;
  }

  /* Initialize the structure.  The sqlite3_index_info structure contains
  ** many fields that are declared "const" to prevent xBestIndex from
  ** changing them.  We have to do some funky casting in order to
  ** initialize those fields.
  */
  pIdxCons = (struct sqlite3_index_constraint*)&pIdxInfo[1];
  pIdxOrderBy = (struct sqlite3_index_orderby*)&pIdxCons[nTerm];
  pUsage = (struct sqlite3_index_constraint_usage*)&pIdxOrderBy[nOrderBy];
  *(int*)&pIdxInfo->nConstraint = nTerm;
  *(int*)&pIdxInfo->nOrderBy = nOrderBy;
  *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint = pIdxCons;
  *(struct sqlite3_index_orderby**)&pIdxInfo->aOrderBy = pIdxOrderBy;
  *(struct sqlite3_index_constraint_usage**)&pIdxInfo->aConstraintUsage =
                                                                   pUsage;

  for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
    if( pTerm->leftCursor != pSrc->iCursor ) continue;
    assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
    testcase( pTerm->eOperator==WO_IN );
    testcase( pTerm->eOperator==WO_ISNULL );
    if( pTerm->eOperator & (WO_IN|WO_ISNULL) ) continue;
    pIdxCons[j].iColumn = pTerm->u.leftColumn;
    pIdxCons[j].iTermOffset = i;
    pIdxCons[j].op = (u8)pTerm->eOperator;
    /* The direct assignment in the previous line is possible only because
    ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical.  The
    ** following asserts verify this fact. */
    assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ );
    assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT );
    assert( WO_LE==SQLITE_INDEX_CONSTRAINT_LE );
    assert( WO_GT==SQLITE_INDEX_CONSTRAINT_GT );
    assert( WO_GE==SQLITE_INDEX_CONSTRAINT_GE );
    assert( WO_MATCH==SQLITE_INDEX_CONSTRAINT_MATCH );
    assert( pTerm->eOperator & (WO_EQ|WO_LT|WO_LE|WO_GT|WO_GE|WO_MATCH) );
    j++;
  }
  for(i=0; i<nOrderBy; i++){
    Expr *pExpr = pOrderBy->a[i].pExpr;
    pIdxOrderBy[i].iColumn = pExpr->iColumn;
    pIdxOrderBy[i].desc = pOrderBy->a[i].sortOrder;
  }

  return pIdxInfo;
}

/*
** The table object reference passed as the second argument to this function
** must represent a virtual table. This function invokes the xBestIndex()
** method of the virtual table with the sqlite3_index_info pointer passed
** as the argument.
**
** If an error occurs, pParse is populated with an error message and a
** non-zero value is returned. Otherwise, 0 is returned and the output
** part of the sqlite3_index_info structure is left populated.
**
** Whether or not an error is returned, it is the responsibility of the
** caller to eventually free p->idxStr if p->needToFreeIdxStr indicates
** that this is required.
*/
static int vtabBestIndex(Parse *pParse, Table *pTab, sqlite3_index_info *p){
  sqlite3_vtab *pVtab = pTab->pVtab;
  int i;
  int rc;

  (void)sqlite3SafetyOff(pParse->db);
  WHERETRACE(("xBestIndex for %s\n", pTab->zName));
  TRACE_IDX_INPUTS(p);
  rc = pVtab->pModule->xBestIndex(pVtab, p);
  TRACE_IDX_OUTPUTS(p);
  (void)sqlite3SafetyOn(pParse->db);

  if( rc!=SQLITE_OK ){
    if( rc==SQLITE_NOMEM ){
      pParse->db->mallocFailed = 1;
    }else if( !pVtab->zErrMsg ){
      sqlite3ErrorMsg(pParse, "%s", sqlite3ErrStr(rc));
    }else{
      sqlite3ErrorMsg(pParse, "%s", pVtab->zErrMsg);
    }
  }
  sqlite3DbFree(pParse->db, pVtab->zErrMsg);
  pVtab->zErrMsg = 0;

  for(i=0; i<p->nConstraint; i++){
    if( !p->aConstraint[i].usable && p->aConstraintUsage[i].argvIndex>0 ){
      sqlite3ErrorMsg(pParse, 
          "table %s: xBestIndex returned an invalid plan", pTab->zName);
    }
  }

  return pParse->nErr;
}


/*
** Compute the best index for a virtual table.
**
** The best index is computed by the xBestIndex method of the virtual
** table module.  This routine is really just a wrapper that sets up
** the sqlite3_index_info structure that is used to communicate with
** xBestIndex.
**
** In a join, this routine might be called multiple times for the
** 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(
  Parse *pParse,                  /* The parsing context */
  WhereClause *pWC,               /* The WHERE clause */
  struct SrcList_item *pSrc,      /* The FROM clause term to search */
  Bitmask notReady,               /* Mask of cursors that are not available */
  ExprList *pOrderBy,             /* The order by clause */
  WhereCost *pCost,               /* Lowest cost query plan */
  sqlite3_index_info **ppIdxInfo  /* Index information passed to xBestIndex */
){
  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;


  /* If the sqlite3_index_info structure has not been previously
  ** allocated and initialized, then allocate and initialize it now.

  */
  pIdxInfo = *ppIdxInfo;
  if( pIdxInfo==0 ){







































    *ppIdxInfo = pIdxInfo = allocateIndexInfo(pParse, pWC, pSrc, pOrderBy);










































  }

  /* At this point, the sqlite3_index_info structure that pIdxInfo points
  ** to will have been initialized, either during the current invocation or
  ** during some prior invocation.  Now we just have to customize the
  ** details of pIdxInfo for the current invocation and pass it to
  ** xBestIndex.
  */

  /* The module name must be defined. Also, by this point there must
  ** be a pointer to an sqlite3_vtab structure. Otherwise
  ** sqlite3ViewGetColumnNames() would have picked up the error. 
  */
  assert( pTab->azModuleArg && pTab->azModuleArg[0] );
  assert( pTab->pVtab );








  /* Set the aConstraint[].usable fields and initialize all 
  ** output variables to zero.
  **
  ** aConstraint[].usable is true for constraints where the right-hand
  ** side contains only references to tables to the left of the current
  ** table.  In other words, if the constraint is of the form:

  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( !pOrderBy ){
    pIdxInfo->nOrderBy = 0;
  }




  if( vtabBestIndex(pParse, pTab, pIdxInfo) ){

    return;
  }

  /* 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))<pIdxInfo->estimatedCost ){
    pCost->rCost = (SQLITE_BIG_DBL/((double)2));
  }else{

    pCost->rCost = pIdxInfo->estimatedCost;
  }



  pCost->plan.wsFlags = WHERE_VIRTUALTABLE;
  pCost->plan.u.pVtabIdx = pIdxInfo;
  if( pIdxInfo && pIdxInfo->orderByConsumed ){




    pCost->plan.wsFlags |= WHERE_ORDERBY;
  }

  pCost->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(pParse, pWC, pSrc, notReady, pOrderBy, pCost);
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

/*
** Find the query plan for accessing a particular table.  Write the
** best query plan and its cost into the WhereCost object supplied as the
** last parameter.

** 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 tables built-in rowid
** index.
*/
static void bestBtreeIndex(
  Parse *pParse,              /* The parsing context */
  WhereClause *pWC,           /* The WHERE clause */
  struct SrcList_item *pSrc,  /* The FROM clause term to search */
  Bitmask notReady,           /* Mask of cursors that are not available */
  ExprList *pOrderBy,         /* The ORDER BY clause */
  WhereCost *pCost            /* Lowest cost query plan */
){
  WhereTerm *pTerm;           /* A single term of the WHERE clause */
  int iCur = pSrc->iCursor;   /* The cursor of the table to be accessed */
  Index *pProbe;              /* An index we are evaluating */
  int rev;                    /* True to scan in reverse order */
  int wsFlags;                /* Flags associated with pProbe */
  int nEq;                    /* Number of == or IN constraints */
  int eqTermMask;             /* Mask of valid equality operators */
  double cost;                /* Cost of using pProbe */
  double nRow;                /* Estimated number of rows in result set */
  int i;                      /* Loop counter */


  WHERETRACE(("bestIndex: tbl=%s notReady=%llx\n", pSrc->pTab->zName,notReady));
  pProbe = pSrc->pTab->pIndex;
  if( pSrc->notIndexed ){
    pProbe = 0;
  }

    if( cost<pCost->rCost ){
      pCost->rCost = cost;
      pCost->nRow = nRow;
      pCost->plan.wsFlags = wsFlags;
    }
  }






















  bestOrClauseIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost);


































  /* 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)!=0 ){

  pCost->plan.wsFlags |= eqTermMask;
  WHERETRACE(("best index is %s, cost=%.9g, nrow=%.9g, wsFlags=%x, nEq=%d\n",
        (pCost->plan.wsFlags & WHERE_INDEXED)!=0 ?
             pCost->plan.u.pIdx->zName : "(none)", pCost->nRow,
        pCost->rCost, pCost->plan.wsFlags, pCost->plan.nEq));
}

/*
** 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.
*/
static void bestIndex(
  Parse *pParse,              /* The parsing context */
  WhereClause *pWC,           /* The WHERE clause */
  struct SrcList_item *pSrc,  /* The FROM clause term to search */
  Bitmask notReady,           /* Mask of cursors that are not available */
  ExprList *pOrderBy,         /* The ORDER BY clause */
  WhereCost *pCost            /* Lowest cost query plan */
){
  if( IsVirtual(pSrc->pTab) ){
    sqlite3_index_info *p = 0;
    bestVirtualIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost, &p);
    if( p->needToFreeIdxStr ){
      sqlite3_free(p->idxStr);
    }
    sqlite3DbFree(pParse->db, p);
  }else{
    bestBtreeIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost);
  }
}

/*
** 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.
**
** Consider the term t2.z='ok' in the following queries:

    if( (pTerm->eOperator & (WO_ISNULL|WO_IN))==0 ){
      sqlite3VdbeAddOp2(v, OP_IsNull, regBase+j, pLevel->addrBrk);
    }
  }
  return regBase;
}




















/*
** Generate code for the start of the iLevel-th loop in the WHERE clause
** implementation described by pWInfo.
*/
static Bitmask codeOneLoopStart(
  WhereInfo *pWInfo,   /* Complete information about the WHERE clause */
  int iLevel,          /* Which level of pWInfo->a[] should be coded */

  Parse *pParse;                  /* Parsing context */
  Vdbe *v;                        /* The prepared stmt under constructions */
  struct SrcList_item *pTabItem;  /* FROM clause term being coded */
  int addrBrk;                    /* Jump here to break out of the loop */
  int addrCont;                   /* Jump here to continue with next cycle */
  int regRowSet;       /* Write rowids to this RowSet if non-negative */
  int codeRowSetEarly; /* True if index fully constrains the search */

  /* Sometimes, this function is required to generate code to do 
  ** something with the rowid of each row scanned. Specifically:
  **
  **   1) If pWInfo->regRowSet is non-zero, then the rowid must be inserted
  **      into the RowSet object stored in register pWInfo->regRowSet.
  **
  **   2) If pWInfo->regRowHash is non-zero, then the rowid must be inserted
  **      into the RowHash object stored in register pWInfo->regRowHash.
  **
  ** Extracting a rowid value from a VDBE cursor is not always a cheap
  ** operation, especially if the rowid is being extracted from an index
  ** cursor. If the rowid value is available as a by-product of the code
  ** generated to create the top of the scan loop, then it can be reused
  ** for either of the two purposes enumerated above without extracting
  ** it from a cursor. The following two variables are used to communicate
  ** the availability of the rowid value to the C-code at the end of this
  ** function that generates the rowid-handling VDBE code.
  */
  int iRowidReg = 0;              /* Rowid is stored in this register */
  int iReleaseReg = 0;            /* Temp register to free before returning */

  pParse = pWInfo->pParse;
  v = pParse->pVdbe;
  pWC = pWInfo->pWC;
  pLevel = &pWInfo->a[iLevel];
  pTabItem = &pWInfo->pTabList->a[pLevel->iFrom];
  iCur = pTabItem->iCursor;
  bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0;
  omitTable = (pLevel->plan.wsFlags & WHERE_IDX_ONLY)!=0 
           && (wctrlFlags & WHERE_FILL_ROWHASH)==0;
  regRowSet = pWInfo->regRowSet;
  codeRowSetEarly = 0;

  /* Create labels for the "break" and "continue" instructions
  ** for the current loop.  Jump to addrBrk to break out of a loop.
  ** Jump to cont to go immediately to the next iteration of the
  ** loop.

        int iTerm = aConstraint[j].iTermOffset;
        disableTerm(pLevel, &pWC->a[iTerm]);
      }
    }
    pLevel->op = OP_VNext;
    pLevel->p1 = iCur;
    pLevel->p2 = sqlite3VdbeCurrentAddr(v);





    sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);
  }else
#endif /* SQLITE_OMIT_VIRTUALTABLE */

  if( pLevel->plan.wsFlags & WHERE_ROWID_EQ ){
    /* Case 1:  We can directly reference a single row using an
    **          equality comparison against the ROWID field.  Or
    **          we reference multiple rows using a "rowid IN (...)"
    **          construct.
    */

    iReleaseReg = sqlite3GetTempReg(pParse);
    pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
    assert( pTerm!=0 );
    assert( pTerm->pExpr!=0 );
    assert( pTerm->leftCursor==iCur );
    assert( omitTable==0 );
    iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, iReleaseReg);
    addrNxt = pLevel->addrNxt;
    sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt);
    sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, iRowidReg);





    VdbeComment((v, "pk"));
    pLevel->op = OP_Noop;
  }else if( pLevel->plan.wsFlags & WHERE_ROWID_RANGE ){
    /* Case 2:  We have an inequality comparison against the ROWID field.
    */
    int testOp = OP_Noop;
    int start;

      disableTerm(pLevel, pEnd);
    }
    start = sqlite3VdbeCurrentAddr(v);
    pLevel->op = bRev ? OP_Prev : OP_Next;
    pLevel->p1 = iCur;
    pLevel->p2 = start;
    pLevel->p5 = (pStart==0 && pEnd==0) ?1:0;

    if( testOp!=OP_Noop ){
      iRowidReg = iReleaseReg = sqlite3GetTempReg(pParse);
      sqlite3VdbeAddOp2(v, OP_Rowid, iCur, iRowidReg);

      sqlite3VdbeAddOp3(v, testOp, memEndValue, addrBrk, iRowidReg);
      sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL);





    }
  }else if( pLevel->plan.wsFlags & (WHERE_COLUMN_RANGE|WHERE_COLUMN_EQ) ){
    /* Case 3: A scan using an index.
    **
    **         The WHERE clause may contain zero or more equality 
    **         terms ("==" or "IN" operators) that refer to the N
    **         left-most columns of the index. It may also contain

    r1 = sqlite3GetTempReg(pParse);
    testcase( pLevel->plan.wsFlags & WHERE_BTM_LIMIT );
    testcase( pLevel->plan.wsFlags & WHERE_TOP_LIMIT );
    if( pLevel->plan.wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT) ){
      sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, nEq, r1);
      sqlite3VdbeAddOp2(v, OP_IsNull, r1, addrCont);
    }
    sqlite3ReleaseTempReg(pParse, r1);

    /* Seek the table cursor, if required */
    disableTerm(pLevel, pRangeStart);
    disableTerm(pLevel, pRangeEnd);

    if( !omitTable ){
      iRowidReg = iReleaseReg = sqlite3GetTempReg(pParse);
      sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, iRowidReg);



      sqlite3VdbeAddOp2(v, OP_Seek, iCur, iRowidReg);  /* Deferred seek */
    }



    /* Record the instruction used to terminate the loop. Disable 
    ** WHERE clause terms made redundant by the index range scan.
    */
    pLevel->op = bRev ? OP_Prev : OP_Next;
    pLevel->p1 = iIdxCur;
  }else

    **   CREATE INDEX i1 ON t1(a);
    **   CREATE INDEX i2 ON t1(b);
    **   CREATE INDEX i3 ON t1(c);
    **
    **   SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
    **
    ** In the example, there are three indexed terms connected by OR.
    ** The top of the loop looks like this:
    **
    **          Null       1                # Zero the row-hash in reg 1
    **
    ** Then, for each indexed term, the following. The arguments to
    ** RowHash are such that the rowid of the current row is inserted
    ** into the row-hash. If it is already present, control skips the
    ** Gosub opcode and jumps straight to the code generated by WhereEnd().
    **
    **        sqlite3WhereBegin(<term>)
    **          RowHash                     # Insert rowid into rowhash
    **          Gosub      2 A
    **        sqlite3WhereEnd()
    **
    ** Following the above, code to terminate the loop. Label A, the target
    ** of the Gosub above, jumps to the instruction right after the Goto.
    **
    **          Null       1                # Zero the row-hash in reg 1
    **          Goto       B                # The loop is finished.
    **

    **       A: <loop body>                 # Return data, whatever.
    **
    **          Return     2                # Jump back to the Gosub
    **
    **       B: <after the loop>
    **
    */
    const int f = WHERE_OMIT_OPEN | WHERE_OMIT_CLOSE | WHERE_FILL_ROWHASH;


    WhereClause *pOrWc;    /* The OR-clause broken out into subterms */
    WhereTerm *pFinal;     /* Final subterm within the OR-clause. */
    SrcList oneTab;        /* Shortened table list */

    int regReturn = ++pParse->nMem;           /* Register used with OP_Gosub */
    int regRowhash = ++pParse->nMem;          /* Register for RowHash object */
    int iLoopBody = sqlite3VdbeMakeLabel(v);  /* Start of loop body */
    int iRetInit;                             /* Address of regReturn init */
    int ii;
   
    pTerm = pLevel->plan.u.pTerm;
    assert( pTerm!=0 );
    assert( pTerm->eOperator==WO_OR );
    assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
    pOrWc = &pTerm->u.pOrInfo->wc;

    pFinal = &pOrWc->a[pOrWc->nTerm-1];






    /* Set up a SrcList containing just the table being scanned by this loop. */
    oneTab.nSrc = 1;
    oneTab.nAlloc = 1;
    oneTab.a[0] = *pTabItem;

    /* Initialize the row-hash register to contain NULL. An SQL NULL is 
    ** equivalent to an empty row-hash. 
    **
    ** Also initialize regReturn to contain the address of the instruction 
    ** immediately following the OP_Return at the bottom of the loop. This
    ** is required in a few obscure LEFT JOIN cases where control jumps
    ** over the top of the loop into the body of it. In this case the 
    ** correct response for the end-of-loop code (the OP_Return) is to 
    ** fall through to the next instruction, just as an OP_Next does if
    ** called on an uninitialized cursor.
    */
    sqlite3VdbeAddOp2(v, OP_Null, 0, regRowhash);
    iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, regReturn);

    /* iReleaseReg = iRowidReg = sqlite3GetTempReg(pParse); */
    for(ii=0; ii<pOrWc->nTerm; ii++){
      WhereTerm *pOrTerm = &pOrWc->a[ii];
      if( pOrTerm->leftCursor==iCur || pOrTerm->eOperator==WO_AND ){
        WhereInfo *pSubWInfo;          /* Info for single OR-term scan */

        /* Loop through table entries that match term pOrTerm. */
        pSubWInfo = sqlite3WhereBegin(


            pParse, &oneTab, pOrTerm->pExpr, 0, f, regRowhash);
        if( pSubWInfo ){
          int iSet = ((ii==pOrWc->nTerm-1)?-1:ii);
          /* The call to sqlite3WhereBegin has coded an OP_RowHash 
          ** at instruction iRowHash. Set P2 (the jump target) of this
          ** instruction to jump past the OP_Gosub coded below. This way,
          ** if the rowid is already in the hash-table, the body of the
          ** loop is not executed.
          */
          int iRowHash = pSubWInfo->iRowidHandler;
          sqlite3VdbeChangeP2(v, iRowHash, sqlite3VdbeCurrentAddr(v) + 1);
          sqlite3VdbeChangeP4(v, iRowHash, (char *)iSet, P4_INT32);
          sqlite3VdbeAddOp2(v, OP_Gosub, regReturn, iLoopBody);

          /* Finish the loop through table entries that match term pOrTerm. */
          sqlite3WhereEnd(pSubWInfo);
        }
      }
    }
    sqlite3VdbeChangeP1(v, iRetInit, sqlite3VdbeCurrentAddr(v));




    sqlite3VdbeAddOp2(v, OP_Null, 0, regRowhash);
    sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrBrk);
    sqlite3VdbeResolveLabel(v, iLoopBody);

    pLevel->op = OP_Return;
    pLevel->p1 = regReturn;



    disableTerm(pLevel, pTerm);
  }else
#endif /* SQLITE_OMIT_OR_OPTIMIZATION */

  {
    /* Case 5:  There is no usable index.  We must do a complete
    **          scan of the entire table.
    */
    static const u8 aStep[] = { OP_Next, OP_Prev };
    static const u8 aStart[] = { OP_Rewind, OP_Last };
    assert( bRev==0 || bRev==1 );
    assert( omitTable==0 );
    pLevel->op = aStep[bRev];
    pLevel->p1 = iCur;
    pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk);
    pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;

  }
  notReady &= ~getMask(pWC->pMaskSet, iCur);

  /* Insert code to test every subexpression that can be completely
  ** computed using the current set of tables.
  */
  k = 0;

      if( (pTerm->prereqAll & notReady)!=0 ) continue;
      assert( pTerm->pExpr );
      sqlite3ExprIfFalse(pParse, pTerm->pExpr, addrCont, SQLITE_JUMPIFNULL);
      pTerm->wtFlags |= TERM_CODED;
    }
  }

  /* Do the special rowid handling now. */
  if( regRowSet ){
    assert( regRowSet>0 );
    if( iRowidReg==0 ){
      /* The rowid was not available as a side-effect of the code 
      ** genenerated above. So extract it from the cursor now.
      */

      assert( iReleaseReg==0 );
      iReleaseReg = iRowidReg = sqlite3GetTempReg(pParse);
#ifndef SQLITE_OMIT_VIRTUALTABLE
      if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
        sqlite3VdbeAddOp2(v, OP_VRowid, iCur, iRowidReg);
      }else
#endif
      {
        sqlite3VdbeAddOp2(v, OP_Rowid, iCur, iRowidReg);
      }
    }
    
    pWInfo->iRowidHandler = sqlite3VdbeCurrentAddr(v);
    if( pWInfo->wctrlFlags&WHERE_FILL_ROWSET ){
      sqlite3VdbeAddOp2(v, OP_RowSetAdd, regRowSet, iRowidReg);
    }else{
      assert( pWInfo->wctrlFlags&WHERE_FILL_ROWHASH );
      sqlite3VdbeAddOp3(v, OP_RowHash, regRowSet, 0, iRowidReg);
    }
  }
  sqlite3ReleaseTempReg(pParse, iReleaseReg);

  return notReady;
}

#if defined(SQLITE_TEST)
/*
** The following variable holds a text description of query plan generated

*/
static void whereInfoFree(sqlite3 *db, WhereInfo *pWInfo){
  if( pWInfo ){
    int i;
    for(i=0; i<pWInfo->nLevel; i++){
      sqlite3_index_info *pInfo = pWInfo->a[i].pIdxInfo;
      if( pInfo ){
        /* assert( pInfo->needToFreeIdxStr==0 || db->mallocFailed ); */
        if( pInfo->needToFreeIdxStr ){
          sqlite3_free(pInfo->idxStr);
        }
        sqlite3DbFree(db, pInfo);
      }
    }
    whereClauseClear(pWInfo->pWC);

  if( db->mallocFailed ){
    goto whereBeginError;
  }
  pWInfo->nLevel = pTabList->nSrc;
  pWInfo->pParse = pParse;
  pWInfo->pTabList = pTabList;
  pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
  pWInfo->regRowSet = regRowSet;
  pWInfo->pWC = pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo];
  pWInfo->wctrlFlags = wctrlFlags;
  pMaskSet = (WhereMaskSet*)&pWC[1];
  assert( regRowSet==0 || (wctrlFlags&(WHERE_FILL_ROWSET|WHERE_FILL_ROWHASH)) );

  /* Split the WHERE clause into separate subexpressions where each
  ** subexpression is separated by an AND operator.
  */
  initMaskSet(pMaskSet);
  whereClauseInit(pWC, pParse, pMaskSet);
  sqlite3ExprCodeConstants(pParse, pWhere);

    int bestJ = 0;              /* The value of j */
    Bitmask m;                  /* Bitmask value for j or bestJ */
    int once = 0;               /* True when first table is seen */

    memset(&bestPlan, 0, sizeof(bestPlan));
    bestPlan.rCost = SQLITE_BIG_DBL;
    for(j=iFrom, pTabItem=&pTabList->a[j]; j<pTabList->nSrc; j++, pTabItem++){
      int doNotReorder;    /* True if this table should not be reordered */
      WhereCost sCost;     /* Cost information from best[Virtual]Index() */
      ExprList *pOrderBy;  /* ORDER BY clause for index to optimize */

      doNotReorder =  (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0;
      if( once && doNotReorder ) break;
      m = getMask(pMaskSet, pTabItem->iCursor);
      if( (m & notReady)==0 ){
        if( j==iFrom ) iFrom++;
        continue;
      }
      pOrderBy = ((i==0 && ppOrderBy )?*ppOrderBy:0);

      assert( pTabItem->pTab );
#ifndef SQLITE_OMIT_VIRTUALTABLE
      if( IsVirtual(pTabItem->pTab) ){

        sqlite3_index_info **pp = &pWInfo->a[j].pIdxInfo;
        bestVirtualIndex(pParse, pWC, pTabItem, notReady, pOrderBy, &sCost, pp);

















      }else 
#endif
      {
        bestBtreeIndex(pParse, pWC, pTabItem, notReady, pOrderBy, &sCost);

      }
      if( once==0 || sCost.rCost<bestPlan.rCost ){
        once = 1;
        bestPlan = sCost;
        bestJ = j;
      }
      if( doNotReorder ) break;

        ** guaranteed to find the index specified in the INDEXED BY clause
        ** if it find an index at all. */
        assert( bestPlan.plan.u.pIdx==pIdx );
      }
    }
  }
  WHERETRACE(("*** Optimizer Finished ***\n"));
  if( pParse->nErr || db->mallocFailed ){
    goto whereBeginError;
  }

  /* If the total query only selects a single row, then the ORDER BY
  ** clause is irrelevant.
  */
  if( (andFlags & WHERE_UNIQUE)!=0 && ppOrderBy ){

  if {[info exists seen($w)]} {
    incr i -1
    continue
  }
  set seen($w) 1
  set result [lsort -int [array names r]]
  puts "do_test where7-2.$i.1 \173"
  puts "  count_steps_sort \173"
  puts "     SELECT a FROM t2"
  set wc [join $w "\n         OR "]
  puts "      WHERE $wc"

  puts "  \175"
  puts "\175 {$result scan 0 sort 0}"
  puts "do_test where7-2.$i.2 \173"
  puts "  count_steps_sort \173"
  puts "     SELECT a FROM t3"
  set wc [join $w "\n         OR "]
  puts "      WHERE $wc"

  puts "  \175"
  puts "\175 {$result scan 0 sort 0}"
}
puts "finish_test"

# 2009 April 17
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# This file implements regression tests for SQLite library.  The
# focus of this file is the code in rowhash.c.
#
# $Id: rowhash.test,v 1.1 2009/04/21 09:02:47 danielk1977 Exp $

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

do_test rowhash-1.1 {
  execsql {
    CREATE TABLE t1(id INTEGER PRIMARY KEY, a, b, c);
    CREATE INDEX i1 ON t1(a);
    CREATE INDEX i2 ON t1(b);
    CREATE INDEX i3 ON t1(c);
  }
} {}

proc do_keyset_test {name lKey} {
  db transaction {
    execsql { DELETE FROM t1 }
    foreach key $lKey {
      execsql { INSERT INTO t1 VALUES($key, 'a', 'b', 'c') }
    }
  }
  do_test $name {
    lsort -integer [execsql {
      SELECT id FROM t1 WHERE a = 'a' OR b = 'b' OR c = 'c';
    }]
  } [lsort -integer $lKey]
}

do_keyset_test rowhash-2.1 {1 2 3}
do_keyset_test rowhash-2.2 {0 1 2 3}
do_keyset_test rowhash-2.3 {62 125 188}
for {set i 4} {$i < 10} {incr i} {
  for {set j 0} {$j < 5000} {incr j} {
    lappend L [expr int(rand()*10000000000)]
  }
  do_keyset_test rowhash-2.$i $L
}

finish_test

# 2009 April 14
#
# 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 creating and dropping virtual tables.
#
# $Id: vtabD.test,v 1.1 2009/04/21 09:02:47 danielk1977 Exp $

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

ifcapable !vtab||!schema_pragmas { finish_test ; return }

# Register the echo module
register_echo_module [sqlite3_connection_pointer db]

do_test vtabD-1.1 {
  execsql {
    CREATE TABLE t1(a, b);
    CREATE INDEX i1 ON t1(a);
    CREATE INDEX i2 ON t1(b);
    CREATE VIRTUAL TABLE tv1 USING echo(t1);
  }
} {}
do_test vtabD-1.2 {
  execsql BEGIN
  for {set i 0} {$i < 100000} {incr i} {
    execsql { INSERT INTO t1 VALUES($i, $i*$i) }
  }
  execsql COMMIT
} {}
do_test vtabD-1.3 {
  execsql { SELECT * FROM tv1 WHERE a = 1 OR b = 4 }
} {1 1 2 4}
do_test vtabD-1.4 {
  execsql { SELECT * FROM tv1 WHERE a = 1 OR b = 1 }
} {1 1}
do_test vtabD-1.5 {
  execsql { SELECT * FROM tv1 WHERE (a > 0 AND a < 5) OR (b > 15 AND b < 65) }
} {1 1 2 4 3 9 4 16 5 25 6 36 7 49 8 64}

do_test vtabD-1.6 {
  execsql { SELECT * FROM tv1 WHERE a < 500 OR b = 810000 }
} [execsql {
  SELECT * FROM t1 WHERE a < 500
    UNION ALL
  SELECT * FROM t1 WHERE b = 810000 AND NOT (a < 500)
}]

do_test vtabD-1.7 {
  execsql { SELECT * FROM tv1 WHERE a < 90000 OR b = 8100000000 }
} [execsql {
  SELECT * FROM t1 WHERE a < 90000
    UNION ALL
  SELECT * FROM t1 WHERE b = 8100000000 AND NOT (a < 90000)
}]

do_test vtabD-1.8 {
  execsql { SELECT * FROM tv1 WHERE a = 90001 OR b = 810000 }
} {90001 8100180001 900 810000}

finish_test

#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library. The focus
# is testing of where.c. More specifically, the focus is the optimization
# of WHERE clauses that feature the OR operator.
#
# $Id: where8.test,v 1.6 2009/04/21 09:02:47 danielk1977 Exp $

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

# Test organization:
#
#   where8-1.*: Tests to demonstrate simple cases work with a single table

do_test where8-1.2 { 
  execsql_status2 { SELECT c FROM t1 WHERE a = 1 OR b = 'nine' }
} {I IX 0 0 6}

do_test where8-1.3 { 
  execsql_status2 { SELECT c FROM t1 WHERE a > 8 OR b = 'two' }
} {IX X II 0 0 6}

do_test where8-1.4 { 
  execsql_status2 { SELECT c FROM t1 WHERE a > 8 OR b GLOB 't*' }
} {IX X III II 0 0 9}

do_test where8-1.5 { 
  execsql_status2 { SELECT c FROM t1 WHERE a > 8 OR b GLOB 'f*' }
} {IX X V IV 0 0 9}

do_test where8-1.6 { 
  execsql_status { SELECT c FROM t1 WHERE a = 1 OR b = 'three' ORDER BY rowid }
} {I III 0 1}

do_test where8-1.7 { 
  execsql_status { SELECT c FROM t1 WHERE a = 1 OR b = 'three' ORDER BY a }
} {I III 0 1}

do_test where8-1.8 {
  # 18 searches. 9 on the index cursor and 9 on the table cursor.
  execsql_status2 { SELECT c FROM t1 WHERE a > 1 AND c LIKE 'I%' }
} {II III IV IX 0 0 18}

do_test where8-1.9 {
  execsql_status2 { SELECT c FROM t1 WHERE a >= 9 OR b <= 'eight' }
} {IX X VIII 0 0 6}

do_test where8-1.10 {
  execsql_status2 { 
    SELECT c FROM t1 WHERE (a >= 9 AND c != 'X') OR b <= 'eight' 
  }
} {IX VIII 0 0 6}

do_test where8-1.11 {
  execsql_status2 { 
    SELECT c FROM t1 WHERE (a >= 4 AND a <= 6) OR b = 'nine' 
  }
} {IV V VI IX 0 0 10}

do_test where8-1.13 {
  execsql_status2 {
    SELECT c FROM t1
    WHERE a = 2 OR b = 'three' OR a = 4 OR b = 'five' OR a = 6
    ORDER BY rowid
  }
} {II III IV V VI 0 1 18}
do_test where8-1.14 {
  execsql_status2 {
    SELECT c FROM t1
    WHERE 
      a = 2 OR b = 'three' OR a = 4 OR b = 'five' OR a = 6 OR
      b = 'seven' OR a = 8 OR b = 'nine' OR a = 10
    ORDER BY rowid
  }
} {II III IV V VI VII VIII IX X 0 1 33}

do_test where8-1.15 {
  execsql_status2 {
    SELECT c FROM t1 WHERE 
      a BETWEEN 2 AND 4 OR b = 'nine'
    ORDER BY rowid
  }
} {II III IV IX 0 1 12}



#--------------------------------------------------------------------------
# Tests where8-2.*: Virtual tables
# 

if 0 {

do_test where8-3.8 {
  execsql_status {
    SELECT a, d 
    FROM t1, t2 
    WHERE (a = 2 OR b = 'three') AND (d = a OR e = 'sixteen')
    ORDER BY t1.rowid
  }
} {2 2 2 4 3 3 3 4 0 1}

do_test where8-3.9 {
  # The "OR c = 'IX'" term forces a linear scan.
  execsql_status {
    SELECT a, d 
    FROM t1, t2 
    WHERE (a = 2 OR b = 'three' OR c = 'IX') AND (d = a OR e = 'sixteen')
    ORDER BY t1.rowid
  }
} {2 2 2 4 3 3 3 4 9 9 9 4 9 0}

do_test where8-3.10 {
  execsql_status {
    SELECT d FROM t2 WHERE e IS NULL OR e = 'four'
  }
} {1 3 5 10 2 0 0}

do_test where8-3.11 {
  execsql_status {
    SELECT a, d FROM t1, t2 WHERE (a=d OR b=e) AND a<5 ORDER BY a
  }
} {1 1 2 2 3 3 4 2 4 4 0 0}
do_test where8-3.12 {

#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library. The focus
# is testing of where.c. More specifically, the focus is the optimization
# of WHERE clauses that feature the OR operator.
#
# $Id: where8m.test,v 1.2 2009/04/21 09:02:47 danielk1977 Exp $

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

source $testdir/malloc_common.tcl

do_malloc_test where8m-1 -sqlprep {

  SELECT c FROM t1 WHERE
    a = 1 OR a = 2 OR a = 3 OR a = 4 OR a = 5 OR a = 6;

  SELECT c FROM t1 WHERE
    a BETWEEN 1 AND 3  AND b < 5 AND b > 2 AND c = 4;
}

do_malloc_test where8m-2 -tclprep {
  db eval {
    BEGIN;
    CREATE TABLE t1(a, b, c);
    CREATE INDEX i1 ON t1(a);
    CREATE INDEX i2 ON t1(b);
  }
  for {set i 0} {$i < 1000} {incr i} {
    set ii [expr $i*$i]
    set iii [expr $i*$i]
    db eval { INSERT INTO t1 VALUES($i, $ii, $iii) }
  }
  db eval COMMIT
} -sqlbody {
  SELECT count(*) FROM t1 WHERE a BETWEEN 5 AND 995 OR b BETWEEN 5 AND 900000;
}

finish_test

# 2008 December 30
#
# 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 the multi-index OR clause optimizer.
#
# $Id: where9.test,v 1.8 2009/04/21 09:02:47 danielk1977 Exp $

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

ifcapable !or_opt {
  finish_test
  return

  count_steps {
    SELECT a FROM t1
     WHERE b IS NULL
        OR c IS NULL
        OR d IS NULL
    ORDER BY a
  }
} {90 91 92 96 97 99 scan 0 sort 1}
do_test where9-1.2.2 {
  count_steps {
    SELECT a FROM t1
     WHERE +b IS NULL
        OR c IS NULL
        OR d IS NULL
    ORDER BY a

  count_steps {
    SELECT a FROM t1
     WHERE (b IS NULL AND c NOT NULL AND d NOT NULL)
        OR (b NOT NULL AND c IS NULL AND d NOT NULL)
        OR (b NOT NULL AND c NOT NULL AND d IS NULL)
    ORDER BY a
  }
} {90 91 92 97 scan 0 sort 1}
do_test where9-1.3.2 {
  count_steps {
    SELECT a FROM t4
     WHERE (b IS NULL AND c NOT NULL AND d NOT NULL)
        OR (b NOT NULL AND c IS NULL AND d NOT NULL)
        OR (b NOT NULL AND c NOT NULL AND d IS NULL)
    ORDER BY a

do_test where9-1.4 {
  count_steps {
    SELECT a FROM t1
     WHERE (b>=950 AND b<=1010) OR (b IS NULL AND c NOT NULL)
    ORDER BY a
  }
} {87 88 89 90 91 scan 0 sort 1}
do_test where9-1.5 {
  # When this test was originally written, SQLite used a rowset object 
  # to optimize the "ORDER BY a" clause. Now that it is using a rowhash,
  # this is not possible. So we have to comment out one term of the OR
  # expression in order to prevent SQLite from deeming a full-table
  # scan to be a better strategy than using multiple indexes, which would
  # defeat the point of the test.
  count_steps {
    SELECT a FROM t1
     WHERE a=83
        OR b=913
        OR c=28028
        OR (d>=82 AND d<83)
/*      OR (e>2802 AND e<2803)  */
        OR f='fghijklmn'
        OR g='hgfedcb'
    ORDER BY a
  }
} {5 31 57 82 83 84 85 86 87 scan 0 sort 1}
do_test where9-1.6 {
  count_steps {
    SELECT a FROM t1
     WHERE b=1012
        OR (d IS NULL AND e IS NOT NULL)
  }
} {92 scan 0 sort 0}

do_test where9-2.5 {
  count_steps {
    SELECT t1.a, coalesce(t2.a,9999)
      FROM t1 LEFT JOIN t2 ON (t1.c=t2.c AND t1.d=t2.d) OR (t1.f)=t2.f
     WHERE t1.a=80 OR t1.b=880 OR (t1.c=27027 AND round(t1.d)==80)
    ORDER BY 1
  }
} {80 80 80 2 80 28 80 54 scan 0 sort 1}
do_test where9-2.6 {
  count_steps {
    SELECT t1.a, coalesce(t2.a,9999)
      FROM t1 LEFT JOIN t2 ON (t1.c+1=t2.c AND t1.d=t2.d) OR (t1.f||'x')=t2.f
     WHERE t1.a=80 OR t1.b=880 OR (t1.c=27027 AND round(t1.d)==80)
    ORDER BY 1
  }
} {80 9999 scan 0 sort 1}
do_test where9-2.7 {
  count_steps {
    SELECT t3.x, t1.a, coalesce(t2.a,9999)
      FROM t3 JOIN
           t1 LEFT JOIN t2 ON (t1.c+1=t2.c AND t1.d=t2.d) OR (t1.f||'x')=t2.f
     WHERE t1.a=t3.y OR t1.b=t3.y*11 OR (t1.c=27027 AND round(t1.d)==80)
    ORDER BY 1, 2
  }
} {1 80 9999 2 80 9999 scan 1 sort 1}
do_test where9-2.8 {
  count_steps {
    SELECT t3.x, t1.a, coalesce(t2.a,9999)
      FROM t3 JOIN
           t1 LEFT JOIN t2 ON (t1.c=t2.c AND t1.d=t2.d) OR (t1.f)=t2.f
     WHERE t1.a=t3.y OR t1.b=t3.y*11 OR (t1.c=27027 AND round(t1.d)==80)
    ORDER BY 1, 2, 3
  }
} {1 80 2 1 80 28 1 80 54 1 80 80 2 80 2 2 80 28 2 80 54 2 80 80 scan 1 sort 1}


ifcapable explain {
  do_test where9-3.1 {
    set r [db eval {

   hash.c
   opcodes.c

   os_os2.c
   os_unix.c
   os_win.c

   rowhash.c
   bitvec.c
   pcache.c
   pcache1.c
   rowset.c
   pager.c

   btmutex.c