SQLite

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains routines used for analyzing expressions and
** for generating VDBE code that evaluates expressions in SQLite.
**
** $Id: expr.c,v 1.176 2004/12/18 18:40:27 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** Return the 'affinity' of the expression pExpr if any.
**

){
  char *zDb = 0;       /* Name of the database.  The "X" in X.Y.Z */
  char *zTab = 0;      /* Name of the table.  The "Y" in X.Y.Z or Y.Z */
  char *zCol = 0;      /* Name of the column.  The "Z" */
  int i, j;            /* Loop counters */
  int cnt = 0;         /* Number of matching column names */
  int cntTab = 0;      /* Number of matching table names */
  sqlite3 *db = pParse->db;         /* The database */
  struct SrcList_item *pItem;       /* Use for looping over pSrcList items */
  struct SrcList_item *pMatch = 0;  /* The matching pSrcList item */

  assert( pColumnToken && pColumnToken->z ); /* The Z in X.Y.Z cannot be NULL */
  zDb = sqlite3NameFromToken(pDbToken);
  zTab = sqlite3NameFromToken(pTableToken);
  zCol = sqlite3NameFromToken(pColumnToken);
  if( sqlite3_malloc_failed ){
    return 1;  /* Leak memory (zDb and zTab) if malloc fails */
  }
  assert( zTab==0 || pEList==0 );

  pExpr->iTable = -1;
  for(i=0, pItem=pSrcList->a; i<pSrcList->nSrc; i++, pItem++){

    Table *pTab = pItem->pTab;
    Column *pCol;

    if( pTab==0 ) continue;
    assert( pTab->nCol>0 );
    if( zTab ){
      if( pItem->zAlias ){
        char *zTabName = pItem->zAlias;
        if( sqlite3StrICmp(zTabName, zTab)!=0 ) continue;
      }else{
        char *zTabName = pTab->zName;
        if( zTabName==0 || sqlite3StrICmp(zTabName, zTab)!=0 ) continue;
        if( zDb!=0 && sqlite3StrICmp(db->aDb[pTab->iDb].zName, zDb)!=0 ){
          continue;
        }
      }
    }
    if( 0==(cntTab++) ){
      pExpr->iTable = pItem->iCursor;
      pExpr->iDb = pTab->iDb;
      pMatch = pItem;
    }
    for(j=0, pCol=pTab->aCol; j<pTab->nCol; j++, pCol++){
      if( sqlite3StrICmp(pCol->zName, zCol)==0 ){
        cnt++;
        pExpr->iTable = pItem->iCursor;
        pMatch = pItem;
        pExpr->iDb = pTab->iDb;
        /* Substitute the rowid (column -1) for the INTEGER PRIMARY KEY */
        pExpr->iColumn = j==pTab->iPKey ? -1 : j;
        pExpr->affinity = pTab->aCol[j].affinity;
        pExpr->pColl = pTab->aCol[j].pColl;
        break;
      }

      sqlite3SetString(&z, zTab, ".", zCol, 0);
    }else{
      z = sqliteStrDup(zCol);
    }
    sqlite3ErrorMsg(pParse, zErr, z);
    sqliteFree(z);
  }

  /* If a column from a table in pSrcList is referenced, then record
  ** this fact in the pSrcList.a[].colUsed bitmask.  Column 0 causes
  ** bit 0 to be set.  Column 1 sets bit 1.  And so forth.  If the
  ** column number is greater than the number of bits in the bitmask
  ** then set the high-order bit of the bitmask.
  */
  if( pExpr->iColumn>=0 && pMatch!=0 ){
    int n = pExpr->iColumn;
    if( n>=sizeof(Bitmask)*8 ){
      n = sizeof(Bitmask)*8-1;
    }
    assert( pMatch->iCursor==pExpr->iTable );
    pMatch->colUsed |= 1<<n;
  }

  /* Clean up and return
  */
  sqliteFree(zDb);
  sqliteFree(zTab);
  sqliteFree(zCol);
  sqlite3ExprDelete(pExpr->pLeft);

/*
** 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.347 2004/12/18 18:40:27 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** These #defines should enable >2GB file support on Posix if the
** underlying operating system supports it.  If the OS lacks

  int nAlloc;      /* Number of entries allocated for a[] below */
  struct IdList_item {
    char *zName;      /* Name of the identifier */
    int idx;          /* Index in some Table.aCol[] of a column named zName */
  } *a;
};

/*
** The bitmask datatype defined below is used for various optimizations.
*/
typedef unsigned int Bitmask;

/*
** The following structure describes the FROM clause of a SELECT statement.
** Each table or subquery in the FROM clause is a separate element of
** the SrcList.a[] array.
**
** With the addition of multiple database support, the following structure
** can also be used to describe a particular table such as the table that

    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 */
    int jointype;     /* Type of join between this table and the next */
    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 */
  } a[1];             /* One entry for each identifier on the list */
};

/*
** Permitted values of the SrcList.a.jointype field
*/
#define JT_INNER     0x0001    /* Any kind of inner or cross join */

/*
** 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.
**
*************************************************************************
** 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.122 2004/12/18 18:40:27 drh Exp $
*/
#include "sqliteInt.h"

/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE
** clause subexpression is separated from the others by an AND operator.
**
** The idxLeft and idxRight fields are the VDBE cursor numbers for the
** table that contains the column that appears on the left-hand and
** right-hand side of ExprInfo.p.  If either side of ExprInfo.p is
** something other than a simple column reference, then idxLeft or
** idxRight are -1.  
**
** It is the VDBE cursor number is the value stored in Expr.iTable
** when Expr.op==TK_COLUMN and the value stored in SrcList.a[].iCursor.
**
** prereqLeft, prereqRight, and prereqAll record sets of cursor numbers,
** but they do so indirectly.  A single ExprMaskSet structure translates
** cursor number into bits and the translated bit is stored in the prereq
** fields.  The translation is used in order to maximize the number of
** bits that will fit in a Bitmask.  The VDBE cursor numbers might be
** spread out over the non-negative integers.  For example, the cursor
** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45.  The ExprMaskSet
** translates these sparse cursor numbers into consecutive integers
** beginning with 0 in order to make the best possible use of the available
** bits in the Bitmask.  So, in the example above, the cursor numbers
** would be mapped into integers 0 through 7.
**
** prereqLeft tells us every VDBE cursor that is referenced on the
** left-hand side of ExprInfo.p.  prereqRight does the same for the
** right-hand side of the expression.  The following identity always
** holds:
**
**       prereqAll = prereqLeft | prereqRight
**
** The ExprInfo.indexable field is true if the ExprInfo.p expression
** is of a form that might control an index.  Indexable expressions
** look like this:
**
**              <column> <op> <expr>
**
** Where <column> is a simple column name and <op> is on of the operators
** that allowedOp() recognizes.  
*/
typedef struct ExprInfo ExprInfo;
struct ExprInfo {
  Expr *p;                /* Pointer to the subexpression */
  u8 indexable;           /* True if this subexprssion is usable by an index */
  short int idxLeft;      /* p->pLeft is a column in this table number. -1 if
                          ** p->pLeft is not the column of any table */
  short int idxRight;     /* p->pRight is a column in this table number. -1 if
                          ** p->pRight is not the column of any table */
  Bitmask prereqLeft;     /* Bitmask of tables referenced by p->pLeft */
  Bitmask prereqRight;    /* Bitmask of tables referenced by p->pRight */
  Bitmask prereqAll;      /* Bitmask of tables referenced by p */
};

/*
** An instance of the following structure keeps track of a mapping
** between VDBE cursor numbers and bits of the bitmasks in ExprInfo.
**
** The VDBE cursor numbers are small integers contained in 
** SrcList_item.iCursor and Expr.iTable fields.  For any given WHERE 

** clause, the cursor numbers might not begin with 0 and they might
** contain gaps in the numbering sequence.  But we want to make maximum
** use of the bits in our bitmasks.  This structure provides a mapping
** from the sparse cursor numbers into consecutive integers beginning
** with 0.
**
** If ExprMaskSet.ix[A]==B it means that The A-th bit of a Bitmask
** corresponds VDBE cursor number B.  The A-th bit of a bitmask is 1<<A.
**
** For example, if the WHERE clause expression used these VDBE
** cursors:  4, 5, 8, 29, 57, 73.  Then the  ExprMaskSet structure
** would map those cursor numbers into bits 0 through 5.
**
** Note that the mapping is not necessarily ordered.  In the example
** above, the mapping might go like this:  4->3, 5->1, 8->2, 29->0,
** 57->5, 73->4.  Or one of 719 other combinations might be used. It
** does not really matter.  What is important is that sparse cursor
** numbers all get mapped into bit numbers that begin with 0 and contain
** no gaps.
*/
typedef struct ExprMaskSet ExprMaskSet;
struct ExprMaskSet {
  int n;                          /* Number of assigned cursor values */
  int ix[sizeof(Bitmask)*8-1];    /* Cursor assigned to each bit */
};

/*
** Determine the number of elements in an array.
*/
#define ARRAYSIZE(X)  (sizeof(X)/sizeof(X[0]))

/*
** This routine identifies subexpressions in the WHERE clause where
** each subexpression is separate by the AND operator.  aSlot is 
** filled with pointers to the subexpressions.  For example:
**
**    WHERE  a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)
**           \________/     \_______________/     \________________/
**            slot[0]            slot[1]               slot[2]
**
** The original WHERE clause in pExpr is unaltered.  All this routine
** does is make aSlot[] entries point to substructure within pExpr.
**
** aSlot[] is an array of subexpressions structures.  There are nSlot
** spaces left in this array.  This routine finds as many AND-separated
** subexpressions as it can and puts pointers to those subexpressions
** into aSlot[] entries.  The return value is the number of slots filled.
*/
static int exprSplit(int nSlot, ExprInfo *aSlot, Expr *pExpr){
  int cnt = 0;
  if( pExpr==0 || nSlot<1 ) return 0;
  if( nSlot==1 || pExpr->op!=TK_AND ){
    aSlot[0].p = pExpr;
    return 1;

/*
** Initialize an expression mask set
*/
#define initMaskSet(P)  memset(P, 0, sizeof(*P))

/*
** Return the bitmask for the given cursor number.  Assign a new bitmask
** if this is the first time the cursor has been seen.
*/
static Bitmask getMask(ExprMaskSet *pMaskSet, int iCursor){
  int i;
  for(i=0; i<pMaskSet->n; i++){
    if( pMaskSet->ix[i]==iCursor ){
      return ((Bitmask)1)<<i;
    }
  }
  if( i==pMaskSet->n && i<ARRAYSIZE(pMaskSet->ix) ){
    pMaskSet->n++;
    pMaskSet->ix[i] = iCursor;
    return ((Bitmask)1)<<i;
  }
  return 0;
}

/*
** Destroy an expression mask set
*/

** In order for this routine to work, the calling function must have
** previously invoked sqlite3ExprResolveIds() on the expression.  See
** the header comment on that routine for additional information.
** The sqlite3ExprResolveIds() routines looks for column names and
** sets their opcodes to TK_COLUMN and their Expr.iTable fields to
** the VDBE cursor number of the table.
*/
static Bitmask exprTableUsage(ExprMaskSet *pMaskSet, Expr *p){
  Bitmask mask = 0;
  if( p==0 ) return 0;
  if( p->op==TK_COLUMN ){
    mask = getMask(pMaskSet, p->iTable);
    if( mask==0 ) mask = -1;
    return mask;
  }
  if( p->pRight ){

    }
  }
  return mask;
}

/*
** Return TRUE if the given operator is one of the operators that is
** allowed for an indexable WHERE clause term.  The allowed operators are
** "=", "<", ">", "<=", ">=", and "IN".
*/
static int allowedOp(int op){
  assert( TK_GT==TK_LE-1 && TK_LE==TK_LT-1 && TK_LT==TK_GE-1 && TK_EQ==TK_GT-1);
  return op==TK_IN || (op>=TK_EQ && op<=TK_GE);
}

/*
** Swap two objects of type T.
*/
#define SWAP(TYPE,A,B) {TYPE t=A; A=B; B=t;}

/*
** Return the index in the SrcList that uses cursor iCur.  If iCur is
** used by the first entry in SrcList return 0.  If iCur is used by
** the second entry return 1.  And so forth.
**
** SrcList is the set of tables in the FROM clause in the order that
** they will be processed.  The value returned here gives us an index
** of which tables will be processed first.
*/
static int tableOrder(SrcList *pList, int iCur){
  int i;
  struct SrcList_item *pItem;
  for(i=0, pItem=pList->a; i<pList->nSrc; i++, pItem++){
    if( pItem->iCursor==iCur ) return i;
  }
  return -1;
}

/*
** The input to this routine is an ExprInfo structure with only the
** "p" field filled in.  The job of this routine is to analyze the

      pMatch = pIdx;
      if( pIdx==pPreferredIdx ) break;
    }
  }
  *pbRev = sortOrder==SQLITE_SO_DESC;
  return pMatch;
}

/*
** This routine decides if pIdx can be used to satisfy the ORDER BY
** clause.  If it can, it returns 1.  If pIdx cannot satisfy the
** ORDER BY clause, this routine returns 0.
**
** pOrderBy is an ORDER BY clause from a SELECT statement.  pTab is the
** left-most table in the FROM clause of that same SELECT statement and
** the table has a cursor number of "base".  pIdx is an index on pTab.
**
** nEqCol is the number of columns of pIdx that are used as equality
** constraints.  Any of these columns may be missing from the ORDER BY
** clause and the match can still be a success.
**
** If the index is UNIQUE, then the ORDER BY clause is allowed to have
** additional terms past the end of the index and the match will still
** be a success.
**
** All terms of the ORDER BY that match against the index must be either
** ASC or DESC.  (Terms of the ORDER BY clause past the end of a UNIQUE
** index do not need to satisfy this constraint.)  The *pbRev value is
** set to 1 if the ORDER BY clause is all DESC and it is set to 0 if
** the ORDER BY clause is all ASC.
*/
static int isSortingIndex(
  Parse *pParse,          /* Parsing context */
  Index *pIdx,            /* The index we are testing */
  Table *pTab,            /* The table to be sorted */
  int base,               /* Cursor number for pTab */
  ExprList *pOrderBy,     /* The ORDER BY clause */
  int nEqCol,             /* Number of index columns with == constraints */
  int *pbRev              /* Set to 1 if ORDER BY is DESC */
){
  int i, j;                    /* Loop counters */
  int sortOrder;               /* Which direction we are sorting */
  int nTerm;                   /* Number of ORDER BY terms */
  struct ExprList_item *pTerm; /* A term of the ORDER BY clause */
  sqlite3 *db = pParse->db;

  assert( pOrderBy!=0 );
  nTerm = pOrderBy->nExpr;
  assert( nTerm>0 );

  /* Match terms of the ORDER BY clause against columns of
  ** the index.
  */
  for(i=j=0, pTerm=pOrderBy->a; j<nTerm && i<pIdx->nColumn; i++){
    Expr *pExpr;       /* The expression of the ORDER BY pTerm */
    CollSeq *pColl;    /* The collating sequence of pExpr */

    pExpr = pTerm->pExpr;
    if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){
      /* Can not use an index sort on anything that is not a column in the
      ** left-most table of the FROM clause */
      return 0;
    }
    pColl = sqlite3ExprCollSeq(pParse, pExpr);
    if( !pColl ) pColl = db->pDfltColl;
    if( pExpr->iColumn!=pIdx->aiColumn[i] && pColl!=pIdx->keyInfo.aColl[i] ){
      if( i<=nEqCol ){
        /* If an index column that is constrained by == fails to match an
        ** ORDER BY term, that is OK.  Just ignore that column of the index
        */
        continue;
      }else{
        /* If an index column fails to match and is not constrained by ==
        ** then the index cannot satisfy the ORDER BY constraint.
        */
        return 0;
      }
    }
    if( i>nEqCol ){
      if( pTerm->sortOrder!=sortOrder ){
        /* Indices can only be used if all ORDER BY terms past the
        ** equality constraints are all either DESC or ASC. */
        return 0;
      }
    }else{
      sortOrder = pTerm->sortOrder;
    }
    j++;
    pTerm++;
  }

  /* The index can be used for sorting if all terms of the ORDER BY clause
  ** or covered or if we ran out of index columns and the it is a UNIQUE
  ** index.
  */
  if( j>=nTerm || (i>=pIdx->nColumn && pIdx->onError!=OE_None) ){
    *pbRev = sortOrder==SQLITE_SO_DESC;
    return 1;
  }
  return 0;
}

/*
** Check table to see if the ORDER BY clause in pOrderBy can be satisfied
** by sorting in order of ROWID.  Return true if so and set *pbRev to be
** true for reverse ROWID and false for forward ROWID order.
*/
static int sortableByRowid(

    pLevel->inP2 = sqlite3VdbeAddOp(v, OP_IdxColumn, iTab, 0);
    pLevel->inOp = OP_Next;
    pLevel->inP1 = iTab;
  }
  disableTerm(pLevel, &pTerm->p);
}

/*
** The number of bits in a Bitmask
*/
#define BMS  (sizeof(Bitmask)*8-1)


/*
** Generate the beginning of the loop used for WHERE clause processing.
** The return value is a pointer to an (opaque) structure that contains
** information needed to terminate the loop.  Later, the calling routine
** should invoke sqlite3WhereEnd() with the return value of this function
** in order to complete the WHERE clause processing.

  Fetch *pFetch         /* Initial location of cursors.  NULL otherwise */
){
  int i;                     /* Loop counter */
  WhereInfo *pWInfo;         /* Will become the return value of this function */
  Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
  int brk, cont = 0;         /* Addresses used during code generation */
  int nExpr;           /* Number of subexpressions in the WHERE clause */
  Bitmask loopMask;    /* One bit set for each outer loop */
  int haveKey = 0;     /* True if KEY is on the stack */
  ExprInfo *pTerm;     /* A single term in the WHERE clause; ptr to aExpr[] */
  ExprMaskSet maskSet; /* The expression mask set */
  int iDirectEq[BMS];  /* Term of the form ROWID==X for the N-th table */
  int iDirectLt[BMS];  /* Term of the form ROWID<X or ROWID<=X */
  int iDirectGt[BMS];  /* Term of the form ROWID>X or ROWID>=X */
  ExprInfo aExpr[101]; /* The WHERE clause is divided into these terms */

  /* pushKey is only allowed if there is a single table (as in an INSERT or
  ** UPDATE statement)
  */
  assert( pushKey==0 || pTabList->nSrc==1 );




  /* Split the WHERE clause into separate subexpressions where each
  ** subexpression is separated by an AND operator.  If the aExpr[]
  ** array fills up, the last entry might point to an expression which
  ** contains additional unfactored AND operators.
  */
  initMaskSet(&maskSet);
  memset(aExpr, 0, sizeof(aExpr));

    /* If we are executing a trigger body, remove all references to
    ** new.* and old.* tables from the prerequisite masks.
    */
    if( (pStack = pParse->trigStack)!=0 ){
      int x;
      if( (x=pStack->newIdx) >= 0 ){
        Bitmask mask = ~getMask(&maskSet, x);
        pTerm->prereqRight &= mask;
        pTerm->prereqLeft &= mask;
        pTerm->prereqAll &= mask;
      }
      if( (x=pStack->oldIdx) >= 0 ){
        Bitmask mask = ~getMask(&maskSet, x);
        pTerm->prereqRight &= mask;
        pTerm->prereqLeft &= mask;
        pTerm->prereqAll &= mask;
      }
    }
  }

  ** first 32 tables are candidates for indices.  This is (again) due
  ** to the limit of 32 bits in an integer bitmask.
  */
  loopMask = 0;
  for(i=0; i<pTabList->nSrc && i<ARRAYSIZE(iDirectEq); i++){
    int j;
    WhereLevel *pLevel = &pWInfo->a[i];
    int iCur = pTabList->a[i].iCursor;       /* The cursor for this table */
    Bitmask mask = getMask(&maskSet, iCur);  /* Cursor mask for this table */
    Table *pTab = pTabList->a[i].pTab;
    Index *pIdx;
    Index *pBestIdx = 0;
    int bestScore = 0;
    int bestRev = 0;

    /* Check to see if there is an expression that uses only the
    ** ROWID field of this table.  For terms of the form ROWID==expr
    ** set iDirectEq[i] to the index of the term.  For terms of the
    ** form ROWID<expr or ROWID<=expr set iDirectLt[i] to the term index.
    ** For terms like ROWID>expr or ROWID>=expr set iDirectGt[i].
    **

    /* Do a search for usable indices.  Leave pBestIdx pointing to
    ** the "best" index.  pBestIdx is left set to NULL if no indices
    ** are usable.
    **
    ** The best index is determined as follows.  For each of the
    ** left-most terms that is fixed by an equality operator, add
    ** 32 to the score.  The right-most term of the index may be
    ** constrained by an inequality.  Add 4 if for an "x<..." constraint
    ** and add 8 for an "x>..." constraint.  If both constraints
    ** are present, add 12.
    **
    ** If the left-most term of the index uses an IN operator
    ** (ex:  "x IN (...)")  then add 16 to the score.
    **
    ** If an index can be used for sorting, add 2 to the score.
    ** If an index contains all the terms of a table that are ever
    ** used by any expression in the SQL statement, then add 1 to
    ** the score.
    **
    ** This scoring system is designed so that the score can later be
    ** used to determine how the index is used.  If the score&0x1c is 0
    ** then all constraints are equalities.  If score&0x4 is not 0 then
    ** there is an inequality used as a termination key.  (ex: "x<...")
    ** If score&0x8 is not 0 then there is an inequality used as the
    ** start key.  (ex: "x>...").  A score or 0x10 is the special case
    ** of an IN operator constraint.  (ex:  "x IN ...").
    **
    ** The IN operator (as in "<expr> IN (...)") is treated the same as
    ** an equality comparison except that it can only be used on the
    ** left-most column of an index and other terms of the WHERE clause
    ** cannot be used in conjunction with the IN operator to help satisfy
    ** other columns of the index.
    */
    for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
      Bitmask eqMask = 0;  /* Index columns covered by an x=... term */
      Bitmask ltMask = 0;  /* Index columns covered by an x<... term */
      Bitmask gtMask = 0;  /* Index columns covered by an x>... term */
      Bitmask inMask = 0;  /* Index columns covered by an x IN .. term */
      Bitmask m;
      int nEq, score, bRev = 0;

      if( pIdx->nColumn>sizeof(eqMask)*8 ){
        continue;  /* Ignore indices with too many columns to analyze */
      }
      for(pTerm=aExpr, j=0; j<nExpr; j++, pTerm++){
        Expr *pX = pTerm->p;
        CollSeq *pColl = sqlite3ExprCollSeq(pParse, pX->pLeft);
        if( !pColl && pX->pRight ){
          pColl = sqlite3ExprCollSeq(pParse, pX->pRight);
        }
        if( !pColl ){

            if( pIdx->aiColumn[k]==iColumn ){
              switch( pX->op ){
                case TK_IN: {
                  if( k==0 ) inMask |= 1;
                  break;
                }
                case TK_EQ: {
                  eqMask |= ((Bitmask)1)<<k;
                  break;
                }
                case TK_LE:
                case TK_LT: {
                  ltMask |= ((Bitmask)1)<<k;
                  break;
                }
                case TK_GE:
                case TK_GT: {
                  gtMask |= ((Bitmask)1)<<k;
                  break;
                }
                default: {
                  /* CANT_HAPPEN */
                  assert( 0 );
                  break;
                }
              }
              break;
            }
          }
        }
      }

      /* The following loop ends with nEq set to the number of columns
      ** on the left of the index with == constraints.
      */
      for(nEq=0; nEq<pIdx->nColumn; nEq++){
        m = (((Bitmask)1)<<(nEq+1))-1;
        if( (m & eqMask)!=m ) break;
      }

      /* Begin assemblying the score
      */
      score = nEq*32;   /* Base score is 32 times number of == constraints */
      m = ((Bitmask)1)<<nEq;
      if( m & ltMask ) score+=4;    /* Increase score for a < constraint */
      if( m & gtMask ) score+=8;    /* Increase score for a > constraint */
      if( score==0 && inMask ) score = 16; /* Default score for IN constraint */

      /* Give bonus points if this index can be used for sorting
      */
      if( i==0 && score>0 && ppOrderBy && *ppOrderBy ){
        int base = pTabList->a[0].iCursor;
        if( isSortingIndex(pParse, pIdx, pTab, base, *ppOrderBy, nEq, &bRev) ){
          score += 2;
        }
      }

      /* If the score for this index is the best we have seen so far, then
      ** save it
      */
      if( score>bestScore ){
        pBestIdx = pIdx;
        bestScore = score;
        bestRev = bRev;
      }
    }
    pLevel->pIdx = pBestIdx;
    pLevel->score = bestScore;
    pLevel->bRev = bestRev;
    loopMask |= mask;
    if( pBestIdx ){
      pLevel->iCur = pParse->nTab++;
    }
  }

  /* Check to see if the ORDER BY clause is or can be satisfied by the

     iCur = pTabList->a[0].iCursor;
     if( pIdx==0 && sortableByRowid(iCur, *ppOrderBy, &bRev) ){
       /* The ORDER BY clause specifies ROWID order, which is what we
       ** were going to be doing anyway...
       */
       *ppOrderBy = 0;
       pLevel0->bRev = bRev;
     }else if( pLevel0->score==16 ){
       /* If there is already an IN index on the left-most table,
       ** it will not give the correct sort order.
       ** So, pretend that no suitable index is found.
       */
     }else if( iDirectEq[0]>=0 || iDirectLt[0]>=0 || iDirectGt[0]>=0 ){
       /* If the left-most column is accessed using its ROWID, then do
       ** not try to sort by index.  But do delete the ORDER BY clause
       ** if it is redundant.
       */
     }else{
       int nEqCol = (pLevel0->score+16)/32;
       pSortIdx = findSortingIndex(pParse, pTab, iCur, 
                                   *ppOrderBy, pIdx, nEqCol, &bRev);
     }
     if( pSortIdx && (pIdx==0 || pIdx==pSortIdx) ){
       if( pIdx==0 ){
         pLevel0->pIdx = pSortIdx;
         pLevel0->iCur = pParse->nTab++;

      brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
      codeEqualityTerm(pParse, pTerm, brk, pLevel);
      cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
      sqlite3VdbeAddOp(v, OP_MustBeInt, 1, brk);
      haveKey = 0;
      sqlite3VdbeAddOp(v, OP_NotExists, iCur, brk);
      pLevel->op = OP_Noop;
    }else if( pIdx!=0 && pLevel->score>0 && (pLevel->score&0x0c)==0 ){
      /* Case 2:  There is an index and all terms of the WHERE clause that
      **          refer to the index using the "==" or "IN" operators.
      */
      int start;
      int nColumn = (pLevel->score+16)/32;
      brk = pLevel->brk = sqlite3VdbeMakeLabel(v);

      /* For each column of the index, find the term of the WHERE clause that
      ** constraints that column.  If the WHERE clause term is X=expr, then
      ** evaluation expr and leave the result on the stack */
      for(j=0; j<nColumn; j++){
        for(pTerm=aExpr, k=0; k<nExpr; k++, pTerm++){

      **         use the "==" operator.
      **
      **         This case is also used when there are no WHERE clause
      **         constraints but an index is selected anyway, in order
      **         to force the output order to conform to an ORDER BY.
      */
      int score = pLevel->score;
      int nEqColumn = score/32;
      int start;
      int leFlag=0, geFlag=0;
      int testOp;

      /* Evaluate the equality constraints
      */
      for(j=0; j<nEqColumn; j++){

      /* Generate the termination key.  This is the key value that
      ** will end the search.  There is no termination key if there
      ** are no equality terms and no "X<..." term.
      **
      ** 2002-Dec-04: On a reverse-order scan, the so-called "termination"
      ** key computed here really ends up being the start key.
      */
      if( (score & 4)!=0 ){
        for(pTerm=aExpr, k=0; k<nExpr; k++, pTerm++){
          Expr *pX = pTerm->p;
          if( pX==0 ) continue;
          if( pTerm->idxLeft==iCur
             && (pX->op==TK_LT || pX->op==TK_LE)
             && (pTerm->prereqRight & loopMask)==pTerm->prereqRight 
             && pX->pLeft->iColumn==pIdx->aiColumn[j]
          ){
            sqlite3ExprCode(pParse, pX->pRight);
            leFlag = pX->op==TK_LE;
            disableTerm(pLevel, &pTerm->p);
            break;
          }
        }
        testOp = OP_IdxGE;
      }else{
        testOp = nEqColumn>0 ? OP_IdxGE : OP_Noop;
        leFlag = 1;
      }
      if( testOp!=OP_Noop ){
        int nCol = nEqColumn + ((score & 4)!=0);
        pLevel->iMem = pParse->nMem++;
        buildIndexProbe(v, nCol, brk, pIdx);
        if( pLevel->bRev ){
          int op = leFlag ? OP_MoveLe : OP_MoveLt;
          sqlite3VdbeAddOp(v, op, pLevel->iCur, brk);
        }else{
          sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);

      ** equality terms and if there is no "X>..." term.  In
      ** that case, generate a "Rewind" instruction in place of the
      ** start key search.
      **
      ** 2002-Dec-04: In the case of a reverse-order search, the so-called
      ** "start" key really ends up being used as the termination key.
      */
      if( (score & 8)!=0 ){
        for(pTerm=aExpr, k=0; k<nExpr; k++, pTerm++){
          Expr *pX = pTerm->p;
          if( pX==0 ) continue;
          if( pTerm->idxLeft==iCur
             && (pX->op==TK_GT || pX->op==TK_GE)
             && (pTerm->prereqRight & loopMask)==pTerm->prereqRight 
             && pX->pLeft->iColumn==pIdx->aiColumn[j]
          ){
            sqlite3ExprCode(pParse, pX->pRight);
            geFlag = pX->op==TK_GE;
            disableTerm(pLevel, &pTerm->p);
            break;
          }
        }
      }else{
        geFlag = 1;
      }
      if( nEqColumn>0 || (score&8)!=0 ){
        int nCol = nEqColumn + ((score&8)!=0);
        buildIndexProbe(v, nCol, brk, pIdx);
        if( pLevel->bRev ){
          pLevel->iMem = pParse->nMem++;
          sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
          testOp = OP_IdxLT;
        }else{
          int op = geFlag ? OP_MoveGe : OP_MoveGt;

        sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0);
        sqlite3VdbeAddOp(v, testOp, pLevel->iCur, brk);
        if( (leFlag && !pLevel->bRev) || (!geFlag && pLevel->bRev) ){
          sqlite3VdbeChangeP3(v, -1, "+", P3_STATIC);
        }
      }
      sqlite3VdbeAddOp(v, OP_RowKey, pLevel->iCur, 0);
      sqlite3VdbeAddOp(v, OP_IdxIsNull, nEqColumn + ((score&4)!=0), cont);
      sqlite3VdbeAddOp(v, OP_IdxRecno, pLevel->iCur, 0);
      if( i==pTabList->nSrc-1 && pushKey ){
        haveKey = 1;
      }else{
        sqlite3VdbeAddOp(v, OP_MoveGe, iCur, 0);
        haveKey = 0;
      }

# 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.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing the use of indices in WHERE clases.
#
# $Id: where.test,v 1.25 2004/12/18 18:40:28 drh Exp $

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

# Build some test data
#
do_test where-1.0 {

    SELECT * FROM t3 WHERE b>0 ORDER BY a LIMIT 3
  }
} {1 100 4 2 99 9 3 98 16 sort}
do_test where-6.8 {
  cksort {
    SELECT * FROM t3 WHERE a IN (3,5,7,1,9,4,2) ORDER BY a LIMIT 3
  }
} {1 100 4 2 99 9 3 98 16 nosort}
do_test where-6.9.1 {
  cksort {
    SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a LIMIT 3
  }
} {1 100 4 nosort}
do_test where-6.9.2 {
  cksort {