/*** 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.206 2006/03/28 23:55:58 drh Exp $*/#include "sqliteInt.h"/*** The number of bits in a Bitmask.  "BMS" means "BitMask Size".*/#define BMS  (sizeof(Bitmask)*8)/*** Determine the number of elements in an array.*/#define ARRAYSIZE(X)  (sizeof(X)/sizeof(X[0]))/*** Trace output macros*/#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)int sqlite3_where_trace = 0;# define TRACE(X)  if(sqlite3_where_trace) sqlite3DebugPrintf X#else# define TRACE(X)#endif/* Forward reference*/typedef struct WhereClause WhereClause;/*** 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.**** All WhereTerms are collected into a single WhereClause structure.  ** The following identity holds:****        WhereTerm.pWC->a[WhereTerm.idx] == WhereTerm**** When a term is of the form:****              X <op> <expr>**** where X is a column name and <op> is one of certain operators,** then WhereTerm.leftCursor and WhereTerm.leftColumn record the** cursor number and column number for X.  WhereTerm.operator records** the <op> using a bitmask encoding defined by WO_xxx below.  The** use of a bitmask encoding for the operator allows us to search** quickly for terms that match any of several different operators.**** 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.*/typedef struct WhereTerm WhereTerm;struct WhereTerm {  Expr *pExpr;            /* Pointer to the subexpression */  i16 iParent;            /* Disable pWC->a[iParent] when this term disabled */  i16 leftCursor;         /* Cursor number of X in "X <op> <expr>" */  i16 leftColumn;         /* Column number of X in "X <op> <expr>" */  u16 eOperator;          /* A WO_xx value describing <op> */  u8 flags;               /* Bit flags.  See below */  u8 nChild;              /* Number of children that must disable us */  WhereClause *pWC;       /* The clause this term is part of */  Bitmask prereqRight;    /* Bitmask of tables used by pRight */  Bitmask prereqAll;      /* Bitmask of tables referenced by p */};/*** Allowed values of WhereTerm.flags*/#define TERM_DYNAMIC    0x01   /* Need to call sqlite3ExprDelete(pExpr) */#define TERM_VIRTUAL    0x02   /* Added by the optimizer.  Do not code */#define TERM_CODED      0x04   /* This term is already coded */#define TERM_COPIED     0x08   /* Has a child */#define TERM_OR_OK      0x10   /* Used during OR-clause processing *//*** An instance of the following structure holds all information about a** WHERE clause.  Mostly this is a container for one or more WhereTerms.*/struct WhereClause {  Parse *pParse;           /* The parser context */  int nTerm;               /* Number of terms */  int nSlot;               /* Number of entries in a[] */  WhereTerm *a;            /* Each a[] describes a term of the WHERE cluase */  WhereTerm aStatic[10];   /* Initial static space for a[] */};/*** An instance of the following structure keeps track of a mapping** between VDBE cursor numbers and bits of the bitmasks in WhereTerm.**** 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];    /* Cursor assigned to each bit */};/*** Bitmasks for the operators that indices are able to exploit.  An** OR-ed combination of these values can be used when searching for** terms in the where clause.*/#define WO_IN     1#define WO_EQ     2#define WO_LT     (WO_EQ<<(TK_LT-TK_EQ))#define WO_LE     (WO_EQ<<(TK_LE-TK_EQ))#define WO_GT     (WO_EQ<<(TK_GT-TK_EQ))#define WO_GE     (WO_EQ<<(TK_GE-TK_EQ))/*** Value for flags returned by bestIndex()*/#define WHERE_ROWID_EQ       0x0001   /* rowid=EXPR or rowid IN (...) */#define WHERE_ROWID_RANGE    0x0002   /* rowid<EXPR and/or rowid>EXPR */#define WHERE_COLUMN_EQ      0x0010   /* x=EXPR or x IN (...) */#define WHERE_COLUMN_RANGE   0x0020   /* x<EXPR and/or x>EXPR */#define WHERE_COLUMN_IN      0x0040   /* x IN (...) */#define WHERE_TOP_LIMIT      0x0100   /* x<EXPR or x<=EXPR constraint */#define WHERE_BTM_LIMIT      0x0200   /* x>EXPR or x>=EXPR constraint */#define WHERE_IDX_ONLY       0x0800   /* Use index only - omit table */#define WHERE_ORDERBY        0x1000   /* Output will appear in correct order */#define WHERE_REVERSE        0x2000   /* Scan in reverse order */#define WHERE_UNIQUE         0x4000   /* Selects no more than one row *//*** Initialize a preallocated WhereClause structure.*/static void whereClauseInit(WhereClause *pWC, Parse *pParse){  pWC->pParse = pParse;  pWC->nTerm = 0;  pWC->nSlot = ARRAYSIZE(pWC->aStatic);  pWC->a = pWC->aStatic;}/*** Deallocate a WhereClause structure.  The WhereClause structure** itself is not freed.  This routine is the inverse of whereClauseInit().*/static void whereClauseClear(WhereClause *pWC){  int i;  WhereTerm *a;  for(i=pWC->nTerm-1, a=pWC->a; i>=0; i--, a++){    if( a->flags & TERM_DYNAMIC ){      sqlite3ExprDelete(a->pExpr);    }  }  if( pWC->a!=pWC->aStatic ){    sqliteFree(pWC->a);  }}/*** Add a new entries to the WhereClause structure.  Increase the allocated** space as necessary.**** WARNING:  This routine might reallocate the space used to store** WhereTerms.  All pointers to WhereTerms should be invalided after** calling this routine.  Such pointers may be reinitialized by referencing** the pWC->a[] array.*/static int whereClauseInsert(WhereClause *pWC, Expr *p, int flags){  WhereTerm *pTerm;  int idx;  if( pWC->nTerm>=pWC->nSlot ){    WhereTerm *pOld = pWC->a;    pWC->a = sqliteMalloc( sizeof(pWC->a[0])*pWC->nSlot*2 );    if( pWC->a==0 ) return 0;    memcpy(pWC->a, pOld, sizeof(pWC->a[0])*pWC->nTerm);    if( pOld!=pWC->aStatic ){      sqliteFree(pOld);    }    pWC->nSlot *= 2;  }  pTerm = &pWC->a[idx = pWC->nTerm];  pWC->nTerm++;  pTerm->pExpr = p;  pTerm->flags = flags;  pTerm->pWC = pWC;  pTerm->iParent = -1;  return idx;}/*** This routine identifies subexpressions in the WHERE clause where** each subexpression is separated by the AND operator or some other** operator specified in the op parameter.  The WhereClause structure** is filled with pointers to 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 slot[] entries point to substructure within pExpr.**** In the previous sentence and in the diagram, "slot[]" refers to** the WhereClause.a[] array.  This array grows as needed to contain** all terms of the WHERE clause.*/static void whereSplit(WhereClause *pWC, Expr *pExpr, int op){  if( pExpr==0 ) return;  if( pExpr->op!=op ){    whereClauseInsert(pWC, pExpr, 0);  }else{    whereSplit(pWC, pExpr->pLeft, op);    whereSplit(pWC, pExpr->pRight, op);  }}/*** Initialize an expression mask set*/#define initMaskSet(P)  memset(P, 0, sizeof(*P))/*** Return the bitmask for the given cursor number.  Return 0 if** iCursor is not in the set.*/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;    }  }  return 0;}/*** Create a new mask for cursor iCursor.**** There is one cursor per table in the FROM clause.  The number of** tables in the FROM clause is limited by a test early in the** sqlite3WhereBegin() routine.  So we know that the pMaskSet->ix[]** array will never overflow.*/static void createMask(ExprMaskSet *pMaskSet, int iCursor){  assert( pMaskSet->n < ARRAYSIZE(pMaskSet->ix) );  pMaskSet->ix[pMaskSet->n++] = iCursor;}/*** This routine walks (recursively) an expression tree and generates** a bitmask indicating which tables are used in that expression** tree.**** In order for this routine to work, the calling function must have** previously invoked sqlite3ExprResolveNames() on the expression.  See** the header comment on that routine for additional information.** The sqlite3ExprResolveNames() 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.  This routine just has to** translate the cursor numbers into bitmask values and OR all** the bitmasks together.*/static Bitmask exprListTableUsage(ExprMaskSet*, ExprList*);static Bitmask exprSelectTableUsage(ExprMaskSet*, Select*);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);    return mask;  }  mask = exprTableUsage(pMaskSet, p->pRight);  mask |= exprTableUsage(pMaskSet, p->pLeft);  mask |= exprListTableUsage(pMaskSet, p->pList);  mask |= exprSelectTableUsage(pMaskSet, p->pSelect);  return mask;}static Bitmask exprListTableUsage(ExprMaskSet *pMaskSet, ExprList *pList){  int i;  Bitmask mask = 0;  if( pList ){    for(i=0; i<pList->nExpr; i++){      mask |= exprTableUsage(pMaskSet, pList->a[i].pExpr);    }  }  return mask;}static Bitmask exprSelectTableUsage(ExprMaskSet *pMaskSet, Select *pS){  Bitmask mask;  if( pS==0 ){    mask = 0;  }else{    mask = exprListTableUsage(pMaskSet, pS->pEList);    mask |= exprListTableUsage(pMaskSet, pS->pGroupBy);    mask |= exprListTableUsage(pMaskSet, pS->pOrderBy);    mask |= exprTableUsage(pMaskSet, pS->pWhere);    mask |= exprTableUsage(pMaskSet, pS->pHaving);  }  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_EQ && TK_GT<TK_GE );  assert( TK_LT>TK_EQ && TK_LT<TK_GE );  assert( TK_LE>TK_EQ && TK_LE<TK_GE );  assert( TK_GE==TK_EQ+4 );  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;}/*** Commute a comparision operator.  Expressions of the form "X op Y"** are converted into "Y op X".*/static void exprCommute(Expr *pExpr){  assert( allowedOp(pExpr->op) && pExpr->op!=TK_IN );