SQLite

/*
** 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.514 2006/06/26 21:35:45 drh Exp $
** @(#) $Id: sqliteInt.h,v 1.515 2006/06/27 01:54:26 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Extra interface definitions for those who need them
*/

#define JT_ERROR     0x0040    /* unknown or unsupported join type */

/*
** For each nested loop in a WHERE clause implementation, the WhereInfo
** structure contains a single instance of this structure.  This structure
** is intended to be private the the where.c module and should not be
** access or modified by other modules.
**
** The pIdxInfo and pBestIdx fields are used to help pick the best
** index on a virtual table.  The pIdxInfo pointer contains indexing
** information for the i-th table in the FROM clause before reordering.
** All the pIdxInfo pointers are freed by whereInfoFree() in where.c.
** The pBestIdx pointer is a copy of pIdxInfo for the i-th table after
** FROM clause ordering.  This is a little confusing so I will repeat
** it in different words.  WhereInfo.a[i].pIdxInfo is index information 
** for WhereInfo.pTabList.a[i].  WhereInfo.a[i].pBestInfo is the
** index information for the i-th loop of the join.  pBestInfo is always
** either NULL or a copy of some pIdxInfo.  So for cleanup it is 
** sufficient to free all of the pIdxInfo pointers.
** 
*/
struct WhereLevel {
  int iFrom;            /* Which entry in the FROM clause */
  int flags;            /* Flags associated with this level */
  int iMem;             /* First memory cell used by this level */
  int iLeftJoin;        /* Memory cell used to implement LEFT OUTER JOIN */
  Index *pIdx;          /* Index used.  NULL if no index */
  int iTabCur;          /* The VDBE cursor used to access the table */
  int iIdxCur;          /* The VDBE cursor used to acesss pIdx */
  int brk;              /* Jump here to break out of the loop */
  int cont;             /* Jump here to continue with the next loop cycle */
  int top;              /* First instruction of interior of the loop */
  int op, p1, p2;       /* Opcode used to terminate the loop */
  int nEq;              /* Number of == or IN constraints on this loop */
  int nIn;              /* Number of IN operators constraining this loop */
  int *aInLoop;         /* Loop terminators for IN operators */
  sqlite3_index_info *pBestIdx;  /* Index information for this level */

  /* The following field is really not part of the current level.  But
  ** we need a place to cache index information for each table in the
  ** FROM clause and the WhereLevel structure is a convenient place.
  */
  sqlite3_index_info *pIdxInfo;  /* Index information for virtual tables */
  sqlite3_index_info *pIdxInfo;  /* Index info for n-th source table */
};

/*
** 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;
  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 */
  sqlite3_index_info **apInfo;  /* Array of pointers to index info structures */
  WhereLevel a[1];     /* Information about each nest loop in the WHERE */
};

/*
** A NameContext defines a context in which to resolve table and column
** names.  The context consists of a list of tables (the pSrcList) field and
** a list of named expression (pEList).  The named expression list may

** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is reponsible 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.223 2006/06/24 11:51:35 danielk1977 Exp $
** $Id: where.c,v 1.224 2006/06/27 01:54:26 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)

  while( N>x ){
    logN += 1;
    x *= 10;
  }
  return logN;
}

/*
** Two routines for printing the content of an sqlite3_index_info
** structure.  Used for testing and debugging only.  If neither
** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines
** are no-ops.
*/
#if !defined(SQLITE_OMIT_VIRTUALTABLE) && \
        (defined(SQLITE_TEST) || defined(SQLITE_DEBUG))
static void TRACE_IDX_INPUTS(sqlite3_index_info *p){
  int i;
  if( !sqlite3_where_trace ) return;
  for(i=0; i<p->nConstraint; i++){
    sqlite3DebugPrintf("  constraint[%d]: col=%d termid=%d op=%d usabled=%d\n",
       i,
       p->aConstraint[i].iColumn,
       p->aConstraint[i].iTermOffset,
       p->aConstraint[i].op,
       p->aConstraint[i].usable);
  }
  for(i=0; i<p->nOrderBy; i++){
    sqlite3DebugPrintf("  orderby[%d]: col=%d desc=%d\n",
       i,
       p->aOrderBy[i].iColumn,
       p->aOrderBy[i].desc);
  }
}
static void TRACE_IDX_OUTPUTS(sqlite3_index_info *p){
  int i;
  if( !sqlite3_where_trace ) return;
  for(i=0; i<p->nConstraint; i++){
    sqlite3DebugPrintf("  usage[%d]: argvIdx=%d omit=%d\n",
       i,
       p->aConstraintUsage[i].argvIndex,
       p->aConstraintUsage[i].omit);
  }
  sqlite3DebugPrintf("  idxNum=%d\n", p->idxNum);
  sqlite3DebugPrintf("  idxStr=%s\n", p->idxStr);
  sqlite3DebugPrintf("  orderByConsumed=%d\n", p->orderByConsumed);
  sqlite3DebugPrintf("  estimatedCost=%g\n", p->estimatedCost);
}
#else
#define TRACE_IDX_INPUTS(A)
#define TRACE_IDX_OUTPUTS(A)
#endif

#ifndef SQLITE_OMIT_VIRTUALTABLE
/*
** 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

  ** allocated and initialized for this virtual table, then allocate
  ** and initialize it now
  */
  pIdxInfo = *ppIdxInfo;
  if( pIdxInfo==0 ){
    WhereTerm *pTerm;
    int nTerm;
    TRACE(("Recomputing index info for %s...\n", 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;
      if( pTerm->eOperator==WO_IN ) continue;
      nTerm++;

  pIdxInfo->estimatedCost = SQLITE_BIG_DBL / 2.0;
  nOrderBy = pIdxInfo->nOrderBy;
  if( pIdxInfo->nOrderBy && !orderByUsable ){
    *(int*)&pIdxInfo->nOrderBy = 0;
  }

  sqlite3SafetyOff(pParse->db);
  TRACE(("xBestIndex for %s\n", pTab->zName));
  TRACE_IDX_INPUTS(pIdxInfo);
  rc = pTab->pVtab->pModule->xBestIndex(pTab->pVtab, pIdxInfo);
  TRACE_IDX_OUTPUTS(pIdxInfo);
  if( rc!=SQLITE_OK ){
    if( rc==SQLITE_NOMEM ){
      sqlite3FailedMalloc();
    }else {
      sqlite3ErrorMsg(pParse, "%s", sqlite3ErrStr(rc));
    }
    sqlite3SafetyOn(pParse->db);
  }else{
    rc = sqlite3SafetyOn(pParse->db);
  }

  *(int*)&pIdxInfo->nOrderBy = nOrderBy;
  return pIdxInfo->estimatedCost;
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

/*
** Find the best index for accessing a particular table.  Return a pointer

    Index *pBest = 0;           /* The best index seen so far */
    int bestFlags = 0;          /* Flags associated with pBest */
    int bestNEq = 0;            /* nEq associated with pBest */
    double lowestCost;          /* Cost of the pBest */
    int bestJ = 0;              /* The value of j */
    Bitmask m;                  /* Bitmask value for j or bestJ */
    int once = 0;               /* True when first table is seen */
    sqlite3_index_info *pBestIndex = 0;
    sqlite3_index_info *pIndex = 0;
    sqlite3_index_info *pIndex; /* Current virtual index */

    lowestCost = 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 */

      doNotReorder =  (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0
                   || (j>0 && (pTabItem[-1].jointype & (JT_LEFT|JT_CROSS))!=0);
      if( once && doNotReorder ) break;
      m = getMask(&maskSet, pTabItem->iCursor);
      if( (m & notReady)==0 ){
        if( j==iFrom ) iFrom++;
        continue;
      }
      assert( pTabItem->pTab );
#ifndef SQLITE_OMIT_VIRTUALTABLE
      pIndex = 0;
      if( IsVirtual(pTabItem->pTab) ){
        sqlite3_index_info **ppIdxInfo = &pWInfo->a[j].pIdxInfo;
        cost = bestVirtualIndex(pParse, &wc, pTabItem, notReady,
                                ppOrderBy ? *ppOrderBy : 0, i==0,
                                &pIndex);
                                ppIdxInfo);
        flags = WHERE_VIRTUALTABLE;
        pIndex = *ppIdxInfo;
        if( pIndex && pIndex->orderByConsumed ){
          flags = WHERE_VIRTUALTABLE | WHERE_ORDERBY;
        }
        pIdx = 0;
        nEq = 0;
      }else 
#endif
      {
        cost = bestIndex(pParse, &wc, pTabItem, notReady,
                         (i==0 && ppOrderBy) ? *ppOrderBy : 0,
                         &pIdx, &flags, &nEq);
      }
      if( cost<lowestCost ){
        once = 1;
        lowestCost = cost;
        pBest = pIdx;
        bestFlags = flags;
        bestNEq = nEq;
        bestJ = j;
#ifndef SQLITE_OMIT_VIRTUALTABLE
        sqliteFree(pBestIndex);
        pBestIndex = pIndex;
        pLevel->pBestIdx = pIndex;
        pIndex = 0;
      }else{
        sqliteFree(pIndex);
        pIndex = 0;
#endif
      }
      if( doNotReorder ) break;
    }
    TRACE(("*** Optimizer choose table %d for loop %d\n", bestJ,
           pLevel-pWInfo->a));
    if( (bestFlags & WHERE_ORDERBY)!=0 ){
      *ppOrderBy = 0;
    }
    andFlags &= bestFlags;
    pLevel->flags = bestFlags;
    pLevel->pIdx = pBest;
    pLevel->nEq = bestNEq;
    pLevel->aInLoop = 0;
    pLevel->nIn = 0;
    pLevel->pIdxInfo = pBestIndex;
    if( pBest ){
      pLevel->iIdxCur = pParse->nTab++;
    }else{
      pLevel->iIdxCur = -1;
    }
    notReady &= ~getMask(&maskSet, pTabList->a[bestJ].iCursor);
    pLevel->iFrom = bestJ;

      }
      if( (pIx = pLevel->pIdx)!=0 ){
        zMsg = sqlite3MPrintf("%z WITH INDEX %s", zMsg, pIx->zName);
      }else if( pLevel->flags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
        zMsg = sqlite3MPrintf("%z USING PRIMARY KEY", zMsg);
      }
#ifndef SQLITE_OMIT_VIRTUALTABLE
      else if( pLevel->pIdxInfo ){
        sqlite3_index_info *pIdxInfo = pLevel->pIdxInfo;
      else if( pLevel->pBestIdx ){
        sqlite3_index_info *pBestIdx = pLevel->pBestIdx;
        zMsg = sqlite3MPrintf("%z VIRTUAL TABLE INDEX %d:%s", zMsg,
                    pIdxInfo->idxNum, pIdxInfo->idxStr);
                    pBestIdx->idxNum, pBestIdx->idxStr);
      }
#endif
      if( pLevel->flags & WHERE_ORDERBY ){
        zMsg = sqlite3MPrintf("%z ORDER BY", zMsg);
      }
      sqlite3VdbeOp3(v, OP_Explain, i, pLevel->iFrom, zMsg, P3_DYNAMIC);
    }
#endif /* SQLITE_OMIT_EXPLAIN */
    pTabItem = &pTabList->a[pLevel->iFrom];
    pTab = pTabItem->pTab;
    iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
    if( pTab->isEphem || pTab->pSelect ) continue;
#ifndef SQLITE_OMIT_VIRTUALTABLE
    if( pLevel->pIdxInfo ){
    if( pLevel->pBestIdx ){
      int iCur = pTabItem->iCursor;
      sqlite3VdbeOp3(v, OP_VOpen, iCur, 0, (const char*)pTab->pVtab, P3_VTAB);
    }else
#endif
    if( (pLevel->flags & WHERE_IDX_ONLY)==0 ){
      sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, OP_OpenRead);
      if( pTab->nCol<(sizeof(Bitmask)*8) ){

      if( !pParse->nMem ) pParse->nMem++;
      pLevel->iLeftJoin = pParse->nMem++;
      sqlite3VdbeAddOp(v, OP_MemInt, 0, pLevel->iLeftJoin);
      VdbeComment((v, "# init LEFT JOIN no-match flag"));
    }

#ifndef SQLITE_OMIT_VIRTUALTABLE
    if( pLevel->pIdxInfo ){
    if( pLevel->pBestIdx ){
      /* Case 0:  The table is a virtual-table.  Use the VFilter and VNext
      **          to access the data.
      */
      int ii;
      sqlite3_index_info *pIdxInfo = pLevel->pIdxInfo;
      int nConstraint = pIdxInfo->nConstraint;
      sqlite3_index_info *pBestIdx = pLevel->pBestIdx;
      int nConstraint = pBestIdx->nConstraint;
      struct sqlite3_index_constraint_usage *aUsage =
                                                  pIdxInfo->aConstraintUsage;
                                                  pBestIdx->aConstraintUsage;
      const struct sqlite3_index_constraint *aConstraint =
                                                  pIdxInfo->aConstraint;
                                                  pBestIdx->aConstraint;

      for(ii=1; ii<=nConstraint; ii++){
        int j;
        for(j=0; j<nConstraint; j++){
          if( aUsage[j].argvIndex==ii ){
            int k = aConstraint[j].iTermOffset;
            sqlite3ExprCode(pParse, wc.a[k].pExpr->pRight);
            break;
          }
        }
        if( j==nConstraint ) break;
      }
      sqlite3VdbeAddOp(v, OP_Integer, ii-1, 0);
      sqlite3VdbeAddOp(v, OP_Integer, pIdxInfo->idxNum, 0);
      sqlite3VdbeOp3(v, OP_VFilter, iCur, brk, pIdxInfo->idxStr,
                      pIdxInfo->needToFreeIdxStr ? P3_MPRINTF : P3_STATIC);
      pIdxInfo->needToFreeIdxStr = 0;
      for(ii=0; ii<pIdxInfo->nConstraint; ii++){
        if( pIdxInfo->aConstraintUsage[ii].omit ){
      sqlite3VdbeAddOp(v, OP_Integer, pBestIdx->idxNum, 0);
      sqlite3VdbeOp3(v, OP_VFilter, iCur, brk, pBestIdx->idxStr,
                      pBestIdx->needToFreeIdxStr ? P3_MPRINTF : P3_STATIC);
      pBestIdx->needToFreeIdxStr = 0;
      for(ii=0; ii<pBestIdx->nConstraint; ii++){
        if( pBestIdx->aConstraintUsage[ii].omit ){
          disableTerm(pLevel, &wc.a[ii]);
        }
      }
      pLevel->op = OP_VNext;
      pLevel->p1 = iCur;
      pLevel->p2 = sqlite3VdbeCurrentAddr(v);
    }else