**    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.813 2008/12/21 03:51:16 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Include the configuration header output by 'configure' if we're using the
** autoconf-based build
................................................................................
    char *zDatabase;  /* Name of database holding this table */
    char *zName;      /* Name of the table */
    char *zAlias;     /* The "B" part of a "A AS B" phrase.  zName is the "A" */
    Table *pTab;      /* An SQL table corresponding to zName */
    Select *pSelect;  /* A SELECT statement used in place of a table name */
    u8 isPopulated;   /* Temporary table associated with SELECT is populated */
    u8 jointype;      /* Type of join between this able and the previous */

    int iCursor;      /* The VDBE cursor number used to access this table */
    Expr *pOn;        /* The ON clause of a join */
    IdList *pUsing;   /* The USING clause of a join */
    Bitmask colUsed;  /* Bit N (1<<N) set if column N or pTab is used */
    u8 notIndexed;    /* True if there is a NOT INDEXED clause */
    char *zIndex;     /* Identifier from "INDEXED BY <zIndex>" clause */
    Index *pIndex;    /* Index structure corresponding to zIndex, if any */
  } a[1];             /* One entry for each identifier on the list */
};

/*
** Permitted values of the SrcList.a.jointype field

**    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.814 2008/12/23 13:35:23 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Include the configuration header output by 'configure' if we're using the
** autoconf-based build
................................................................................
    char *zDatabase;  /* Name of database holding this table */
    char *zName;      /* Name of the table */
    char *zAlias;     /* The "B" part of a "A AS B" phrase.  zName is the "A" */
    Table *pTab;      /* An SQL table corresponding to zName */
    Select *pSelect;  /* A SELECT statement used in place of a table name */
    u8 isPopulated;   /* Temporary table associated with SELECT is populated */
    u8 jointype;      /* Type of join between this able and the previous */
    u8 notIndexed;    /* True if there is a NOT INDEXED clause */
    int iCursor;      /* The VDBE cursor number used to access this table */
    Expr *pOn;        /* The ON clause of a join */
    IdList *pUsing;   /* The USING clause of a join */
    Bitmask colUsed;  /* Bit N (1<<N) set if column N or pTab is used */

    char *zIndex;     /* Identifier from "INDEXED BY <zIndex>" clause */
    Index *pIndex;    /* Index structure corresponding to zIndex, if any */
  } a[1];             /* One entry for each identifier on the list */
};

/*
** Permitted values of the SrcList.a.jointype field

**
** 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.805 2008/12/18 18:31:39 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
** The following global variable is incremented every time a cursor
................................................................................
*/
case OP_RowSetRead: {       /* jump, out3 */
  Mem *pIdx;
  i64 val;
  assert( pOp->p1>0 && pOp->p1<=p->nMem );
  CHECK_FOR_INTERRUPT;
  pIdx = &p->aMem[pOp->p1];

  if( (pIdx->flags & MEM_RowSet)==0 
   || sqlite3RowSetNext(pIdx->u.pRowSet, &val)==0
  ){
    /* The boolean index is empty */
    sqlite3VdbeMemSetNull(pIdx);
    pc = pOp->p2 - 1;
  }else{
    /* A value was pulled from the index */
    assert( pOp->p3>0 && pOp->p3<=p->nMem );
    pOut = &p->aMem[pOp->p3];
    sqlite3VdbeMemSetInt64(pOut, val);
  }
  break;
}


#ifndef SQLITE_OMIT_TRIGGER

**
** 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.806 2008/12/23 13:35:23 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
** The following global variable is incremented every time a cursor
................................................................................
*/
case OP_RowSetRead: {       /* jump, out3 */
  Mem *pIdx;
  i64 val;
  assert( pOp->p1>0 && pOp->p1<=p->nMem );
  CHECK_FOR_INTERRUPT;
  pIdx = &p->aMem[pOp->p1];
  pOut = &p->aMem[pOp->p3];
  if( (pIdx->flags & MEM_RowSet)==0 
   || sqlite3RowSetNext(pIdx->u.pRowSet, &val)==0
  ){
    /* The boolean index is empty */
    sqlite3VdbeMemSetNull(pIdx);
    pc = pOp->p2 - 1;
  }else{
    /* A value was pulled from the index */
    assert( pOp->p3>0 && pOp->p3<=p->nMem );

    sqlite3VdbeMemSetInt64(pOut, val);
  }
  break;
}


#ifndef SQLITE_OMIT_TRIGGER

** 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.340 2008/12/21 03:51:16 drh Exp $
*/
#include "sqliteInt.h"

/*
** Trace output macros
*/
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
................................................................................
/*
** A WhereTerm with eOperator==WO_OR has its u.pOrInfo pointer set to
** a dynamically allocated instance of the following structure.
*/
struct WhereOrInfo {
  WhereClause wc;          /* Decomposition into subterms */
  Bitmask indexable;       /* Bitmask of all indexable tables in the clause */
  WherePlan *aPlan;        /* Search plan for each subterm */
};

/*
** A WhereTerm with eOperator==WO_AND has its u.pAndInfo pointer set to
** a dynamically allocated instance of the following structure.
*/
struct WhereAndInfo {
................................................................................

/*
** Deallocate all memory associated with a WhereOrInfo object.
*/
static void whereOrInfoDelete(sqlite3 *db, WhereOrInfo *p){
  if( p ){
    whereClauseClear(&p->wc);
    sqlite3DbFree(db, p->aPlan);
    sqlite3DbFree(db, p);
  }
}

/*
** Deallocate all memory associated with a WhereAndInfo object.
*/
................................................................................
  assert( (pTerm->wtFlags & (TERM_DYNAMIC|TERM_ORINFO|TERM_ANDINFO))==0 );
  assert( pExpr->op==TK_OR );
  pTerm->u.pOrInfo = pOrInfo = sqlite3DbMallocRaw(db, sizeof(*pOrInfo));
  if( pOrInfo==0 ) return;
  pTerm->wtFlags |= TERM_ORINFO;
  pOrWc = &pOrInfo->wc;
  whereClauseInit(pOrWc, pWC->pParse, pMaskSet);
  pOrInfo->aPlan = 0;
  whereSplit(pOrWc, pExpr, TK_OR);
  exprAnalyzeAll(pSrc, pOrWc);
  if( db->mallocFailed ) return;
  assert( pOrWc->nTerm>=2 );

  /*
  ** Compute the set of tables that might satisfy cases 1 or 2.
................................................................................
        pTerm->nChild = 1;
      }else{
        sqlite3ExprListDelete(db, pList);
      }
      pTerm->eOperator = 0;  /* case 1 trumps case 2 */
    }
  }

  /* If case 2 applies, allocate space for pOrInfo->aPlan
  */
  if( pTerm->eOperator==WO_OR ){
    pOrInfo->aPlan = sqlite3DbMallocRaw(db, pOrWc->nTerm*sizeof(WherePlan));
  }
}
#endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */


/*
** The input to this routine is an WhereTerm structure with only the
** "pExpr" field filled in.  The job of this routine is to analyze the
................................................................................
  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 */



  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;
    }
  }







































  /* 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 ){
................................................................................
    /* 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;
    disableTerm(pLevel, pRangeStart);
    disableTerm(pLevel, pRangeEnd);



  }else if( pLevel->plan.wsFlags & WHERE_MULTI_OR ){
    /* Case 4:  Two or more separately indexed terms connected by OR
    **
    ** Example:
    **
    **   CREATE TABLE t1(a,b,c,d);
    **   CREATE INDEX i1 ON t1(a);
    **   CREATE INDEX i2 ON t1(b);
................................................................................
    **     B:
    */
    int regRowset;         /* Register holding the RowSet object */
    int regNextRowid;      /* Register holding next rowid */
    WhereTerm *pTerm;      /* The complete OR-clause */
    WhereClause *pOrWc;    /* The OR-clause broken out into subterms */
    WhereTerm *pOrTerm;    /* A single subterm within the OR-clause */

   
    pTerm = pLevel->plan.u.pTerm;
    assert( pTerm!=0 );
    assert( pTerm->eOperator==WO_OR );
    assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
    pOrWc = &pTerm->u.pOrInfo->wc;
    
    regRowset = sqlite3GetTempReg(pParse);

    sqlite3VdbeAddOp1(v, OP_Null, regRowset);



    for(j=0, pOrTerm=pOrWc->a; j<pOrWc->nTerm; j++, pOrTerm++){

      if( pOrTerm->leftCursor!=iCur ) continue;
      /* fillRowSetFromIdx(pParse, regRowset, pTabItem, pOrTerm); */






    }
    regNextRowid = sqlite3GetTempReg(pParse);

    sqlite3VdbeResolveLabel(v, addrCont);
    addrCont = 
       sqlite3VdbeAddOp3(v, OP_RowSetRead, regRowset, addrBrk, regNextRowid);
    sqlite3VdbeAddOp2(v, OP_Seek, iCur, regNextRowid);
    sqlite3ReleaseTempReg(pParse, regNextRowid);
    pLevel->op = OP_Goto;
    pLevel->p2 = addrCont;
  }else{



    /* Case 5:  There is no usable index.  We must do a complete
    **          scan of the entire table.
    */
    assert( omitTable==0 );
    assert( bRev==0 );
    pLevel->op = OP_Next;
    pLevel->p1 = iCur;

** 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.341 2008/12/23 13:35:23 drh Exp $
*/
#include "sqliteInt.h"

/*
** Trace output macros
*/
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
................................................................................
/*
** A WhereTerm with eOperator==WO_OR has its u.pOrInfo pointer set to
** a dynamically allocated instance of the following structure.
*/
struct WhereOrInfo {
  WhereClause wc;          /* Decomposition into subterms */
  Bitmask indexable;       /* Bitmask of all indexable tables in the clause */

};

/*
** A WhereTerm with eOperator==WO_AND has its u.pAndInfo pointer set to
** a dynamically allocated instance of the following structure.
*/
struct WhereAndInfo {
................................................................................

/*
** Deallocate all memory associated with a WhereOrInfo object.
*/
static void whereOrInfoDelete(sqlite3 *db, WhereOrInfo *p){
  if( p ){
    whereClauseClear(&p->wc);

    sqlite3DbFree(db, p);
  }
}

/*
** Deallocate all memory associated with a WhereAndInfo object.
*/
................................................................................
  assert( (pTerm->wtFlags & (TERM_DYNAMIC|TERM_ORINFO|TERM_ANDINFO))==0 );
  assert( pExpr->op==TK_OR );
  pTerm->u.pOrInfo = pOrInfo = sqlite3DbMallocRaw(db, sizeof(*pOrInfo));
  if( pOrInfo==0 ) return;
  pTerm->wtFlags |= TERM_ORINFO;
  pOrWc = &pOrInfo->wc;
  whereClauseInit(pOrWc, pWC->pParse, pMaskSet);

  whereSplit(pOrWc, pExpr, TK_OR);
  exprAnalyzeAll(pSrc, pOrWc);
  if( db->mallocFailed ) return;
  assert( pOrWc->nTerm>=2 );

  /*
  ** Compute the set of tables that might satisfy cases 1 or 2.
................................................................................
        pTerm->nChild = 1;
      }else{
        sqlite3ExprListDelete(db, pList);
      }
      pTerm->eOperator = 0;  /* case 1 trumps case 2 */
    }
  }






}
#endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */


/*
** The input to this routine is an WhereTerm structure with only the
** "pExpr" field filled in.  The job of this routine is to analyze the
................................................................................
  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 */
  Bitmask maskSrc;            /* Bitmask for the pSrc table */

  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;
    }
  }

#if SQLITE_ENABLE_MULTI_OR
  /* Search for an OR-clause that can be used to look up the table.
  */
  maskSrc = getMask(pWC->pMaskSet, iCur);
  for(i=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
    WhereClause tempWC;
    tempWC = *pWC;
    tempWC.nSlot = 1;
    if( pTerm->eOperator==WO_OR 
        && ((pTerm->prereqAll & ~maskSrc) & notReady)==0
        && (pTerm->u.pOrInfo->indexable & maskSrc)!=0 ){
      WhereClause *pOrWC = &pTerm->u.pOrInfo->wc;
      WhereTerm *pOrTerm;
      int j;
      double rTotal = 0;
      double nRow = 0;
      for(j=0, pOrTerm=pOrWC->a; j<pOrWC->nTerm; j++, pOrTerm++){
        WhereCost sTermCost;
        if( pOrTerm->leftCursor!=iCur ) continue;
        tempWC.a = pOrTerm;
        bestIndex(pParse, &tempWC, pSrc, notReady, 0, &sTermCost);
        if( sTermCost.plan.wsFlags==0 ){
          rTotal = pCost->rCost;
          break;
        }
        rTotal += sTermCost.rCost;
        nRow += sTermCost.nRow;
      }
      if( rTotal<pCost->rCost ){
        pCost->rCost = rTotal;
        pCost->nRow = nRow;
        pCost->plan.wsFlags = WHERE_MULTI_OR;
        pCost->plan.u.pTerm = pTerm;
      }
    }
  }
#endif

  /* 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 ){
................................................................................
    /* 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;
    disableTerm(pLevel, pRangeStart);
    disableTerm(pLevel, pRangeEnd);
  }else

#if SQLITE_ENABLE_MULTI_OR
  if( pLevel->plan.wsFlags & WHERE_MULTI_OR ){
    /* Case 4:  Two or more separately indexed terms connected by OR
    **
    ** Example:
    **
    **   CREATE TABLE t1(a,b,c,d);
    **   CREATE INDEX i1 ON t1(a);
    **   CREATE INDEX i2 ON t1(b);
................................................................................
    **     B:
    */
    int regRowset;         /* Register holding the RowSet object */
    int regNextRowid;      /* Register holding next rowid */
    WhereTerm *pTerm;      /* The complete OR-clause */
    WhereClause *pOrWc;    /* The OR-clause broken out into subterms */
    WhereTerm *pOrTerm;    /* A single subterm within the OR-clause */
    SrcList oneTab;        /* Shortened table list */
   
    pTerm = pLevel->plan.u.pTerm;
    assert( pTerm!=0 );
    assert( pTerm->eOperator==WO_OR );
    assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
    pOrWc = &pTerm->u.pOrInfo->wc;
    
    regRowset = sqlite3GetTempReg(pParse);
    regNextRowid = sqlite3GetTempReg(pParse);
    sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset);
    oneTab.nSrc = 1;
    oneTab.nAlloc = 1;
    oneTab.a[0] = *pTabItem;
    for(j=0, pOrTerm=pOrWc->a; j<pOrWc->nTerm; j++, pOrTerm++){
      WhereInfo *pSubWInfo;
      if( pOrTerm->leftCursor!=iCur ) continue;

      pSubWInfo = sqlite3WhereBegin(pParse, &oneTab, pOrTerm->pExpr, 0, 0);
      if( pSubWInfo ){
        sqlite3VdbeAddOp2(v, OP_Rowid, oneTab.a[0].iCursor, regNextRowid);
        sqlite3VdbeAddOp2(v, OP_RowSetAdd, regRowset, regNextRowid);
        pSubWInfo->a[0].plan.wsFlags |= WHERE_IDX_ONLY;
        sqlite3WhereEnd(pSubWInfo);
      }

    }
    sqlite3VdbeResolveLabel(v, addrCont);
    addrCont = 
       sqlite3VdbeAddOp3(v, OP_RowSetRead, regRowset, addrBrk, regNextRowid);
    sqlite3VdbeAddOp2(v, OP_Seek, iCur, regNextRowid);
    sqlite3ReleaseTempReg(pParse, regNextRowid);
    pLevel->op = OP_Goto;
    pLevel->p2 = addrCont;
  }else
#endif /* SQLITE_ENABLE_MULTI_OR */

  {
    /* Case 5:  There is no usable index.  We must do a complete
    **          scan of the entire table.
    */
    assert( omitTable==0 );
    assert( bRev==0 );
    pLevel->op = OP_Next;
    pLevel->p1 = iCur;