/*** 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.**** $Id: qt/where.c   3.3.4   edited Mar 30 2004 $*/#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.*/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 */  unsigned prereqLeft;    /* Bitmask of tables referenced by p->pLeft */  unsigned prereqRight;   /* Bitmask of tables referenced by p->pRight */  unsigned prereqAll;     /* Bitmask of tables referenced by p */};/*** An instance of the following structure keeps track of a mapping** between VDBE cursor numbers and bitmasks.  The VDBE cursor numbers** are small integers contained in SrcList_item.iCursor and Expr.iTable** fields.  For any given WHERE clause, we want to track which cursors** are being used, so we assign a single bit in a 32-bit word to track** that cursor.  Then a 32-bit integer is able to show the set of all** cursors being used.*/typedef struct ExprMaskSet ExprMaskSet;struct ExprMaskSet {  int n;          /* Number of assigned cursor values */  int ix[32];     /* Cursor assigned to each bit */};/*** Determine the number of elements in an array.*/#define ARRAYSIZE(X)  (sizeof(X)/sizeof(X[0]))/*** This routine is used to divide the WHERE expression into subexpressions** separated by the AND operator.**** aSlot[] is an array of subexpressions structures.** There are nSlot spaces left in this array.  This routine attempts to** split pExpr into subexpressions and fills aSlot[] with those subexpressions.** 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;  }  if( pExpr->pLeft->op!=TK_AND ){    aSlot[0].p = pExpr->pLeft;    cnt = 1 + exprSplit(nSlot-1, &aSlot[1], pExpr->pRight);  }else{    cnt = exprSplit(nSlot, aSlot, pExpr->pLeft);    cnt += exprSplit(nSlot-cnt, &aSlot[cnt], pExpr->pRight);  }  return cnt;}/*** Initialize an expression mask set*/#define initMaskSet(P)  memset(P, 0, sizeof(*P))/*** Return the bitmask for the given cursor.  Assign a new bitmask** if this is the first time the cursor has been seen.*/static int getMask(ExprMaskSet *pMaskSet, int iCursor){  int i;  for(i=0; i<pMaskSet->n; i++){    if( pMaskSet->ix[i]==iCursor ) return 1<<i;  }  if( i==pMaskSet->n && i<ARRAYSIZE(pMaskSet->ix) ){    pMaskSet->n++;    pMaskSet->ix[i] = iCursor;    return 1<<i;  }  return 0;}/*** Destroy an expression mask set*/#define freeMaskSet(P)   /* NO-OP *//*** 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 sqliteExprResolveIds() on the expression.  See** the header comment on that routine for additional information.** The sqliteExprResolveIds() 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 int exprTableUsage(ExprMaskSet *pMaskSet, Expr *p){  unsigned int mask = 0;  if( p==0 ) return 0;  if( p->op==TK_COLUMN ){    return getMask(pMaskSet, p->iTable);  }  if( p->pRight ){    mask = exprTableUsage(pMaskSet, p->pRight);  }  if( p->pLeft ){    mask |= exprTableUsage(pMaskSet, p->pLeft);  }  if( p->pList ){    int i;    for(i=0; i<p->pList->nExpr; i++){      mask |= exprTableUsage(pMaskSet, p->pList->a[i].pExpr);    }  }  return mask;}/*** Return TRUE if the given operator is one of the operators that is** allowed for an indexable WHERE clause.  The allowed operators are** "=", "<", ">", "<=", ">=", and "IN".*/static int allowedOp(int op){  switch( op ){    case TK_LT:    case TK_LE:    case TK_GT:    case TK_GE:    case TK_EQ:    case TK_IN:      return 1;    default:      return 0;  }}/*** 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** subexpression and populate all the other fields of the ExprInfo** structure.*/static void exprAnalyze(ExprMaskSet *pMaskSet, ExprInfo *pInfo){  Expr *pExpr = pInfo->p;  pInfo->prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft);  pInfo->prereqRight = exprTableUsage(pMaskSet, pExpr->pRight);  pInfo->prereqAll = exprTableUsage(pMaskSet, pExpr);  pInfo->indexable = 0;  pInfo->idxLeft = -1;  pInfo->idxRight = -1;  if( allowedOp(pExpr->op) && (pInfo->prereqRight & pInfo->prereqLeft)==0 ){    if( pExpr->pRight && pExpr->pRight->op==TK_COLUMN ){      pInfo->idxRight = pExpr->pRight->iTable;      pInfo->indexable = 1;    }    if( pExpr->pLeft->op==TK_COLUMN ){      pInfo->idxLeft = pExpr->pLeft->iTable;      pInfo->indexable = 1;    }  }}/*** 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".**** This routine attempts to find an index for pTab that generates the** correct record sequence for the given ORDER BY clause.  The return value** is a pointer to an index that does the job.  NULL is returned if the** table has no index that will generate the correct sort order.**** If there are two or more indices that generate the correct sort order** and pPreferredIdx is one of those indices, then return pPreferredIdx.**** nEqCol is the number of columns of pPreferredIdx that are used as** equality constraints.  Any index returned must have exactly this same** set of columns.  The ORDER BY clause only matches index columns beyond the** the first nEqCol columns.**** All terms of the ORDER BY clause must be either ASC or DESC.  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 Index *findSortingIndex(  Table *pTab,            /* The table to be sorted */  int base,               /* Cursor number for pTab */  ExprList *pOrderBy,     /* The ORDER BY clause */  Index *pPreferredIdx,   /* Use this index, if possible and not NULL */  int nEqCol,             /* Number of index columns used with == constraints */  int *pbRev              /* Set to 1 if ORDER BY is DESC */){  int i, j;  Index *pMatch;  Index *pIdx;  int sortOrder;  assert( pOrderBy!=0 );  assert( pOrderBy->nExpr>0 );  sortOrder = pOrderBy->a[0].sortOrder & SQLITE_SO_DIRMASK;  for(i=0; i<pOrderBy->nExpr; i++){    Expr *p;    if( (pOrderBy->a[i].sortOrder & SQLITE_SO_DIRMASK)!=sortOrder ){      /* Indices can only be used if all ORDER BY terms are either      ** DESC or ASC.  Indices cannot be used on a mixture. */      return 0;    }    if( (pOrderBy->a[i].sortOrder & SQLITE_SO_TYPEMASK)!=SQLITE_SO_UNK ){      /* Do not sort by index if there is a COLLATE clause */      return 0;    }    p = pOrderBy->a[i].pExpr;    if( p->op!=TK_COLUMN || p->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;    }  }    /* If we get this far, it means the ORDER BY clause consists only of  ** ascending columns in the left-most table of the FROM clause.  Now  ** check for a matching index.  */  pMatch = 0;  for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){    int nExpr = pOrderBy->nExpr;    if( pIdx->nColumn < nEqCol || pIdx->nColumn < nExpr ) continue;    for(i=j=0; i<nEqCol; i++){      if( pPreferredIdx->aiColumn[i]!=pIdx->aiColumn[i] ) break;      if( j<nExpr && pOrderBy->a[j].pExpr->iColumn==pIdx->aiColumn[i] ){ j++; }    }    if( i<nEqCol ) continue;    for(i=0; i+j<nExpr; i++){      if( pOrderBy->a[i+j].pExpr->iColumn!=pIdx->aiColumn[i+nEqCol] ) break;    }    if( i+j>=nExpr ){      pMatch = pIdx;      if( pIdx==pPreferredIdx ) break;    }  }  if( pMatch && pbRev ){    *pbRev = sortOrder==SQLITE_SO_DESC;  }  return pMatch;}/*** 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 sqliteWhereEnd() with the return value of this function** in order to complete the WHERE clause processing.**** If an error occurs, this routine returns NULL.**** The basic idea is to do a nested loop, one loop for each table in** the FROM clause of a select.  (INSERT and UPDATE statements are the** same as a SELECT with only a single table in the FROM clause.)  For** example, if the SQL is this:****       SELECT * FROM t1, t2, t3 WHERE ...;**** Then the code generated is conceptually like the following:****      foreach row1 in t1 do       \    Code generated**        foreach row2 in t2 do      |-- by sqliteWhereBegin()**          foreach row3 in t3 do   /**            ...**          end                     \    Code generated**        end                        |-- by sqliteWhereEnd()**      end                         /**** There are Btree cursors associated with each table.  t1 uses cursor** number pTabList->a[0].iCursor.  t2 uses the cursor pTabList->a[1].iCursor.** And so forth.  This routine generates code to open those VDBE cursors** and sqliteWhereEnd() generates the code to close them.**** If the WHERE clause is empty, the foreach loops must each scan their** entire tables.  Thus a three-way join is an O(N^3) operation.  But if** the tables have indices and there are terms in the WHERE clause that** refer to those indices, a complete table scan can be avoided and the** code will run much faster.  Most of the work of this routine is checking** to see if there are indices that can be used to speed up the loop.**** Terms of the WHERE clause are also used to limit which rows actually** make it to the "..." in the middle of the loop.  After each "foreach",** terms of the WHERE clause that use only terms in that loop and outer** loops are evaluated and if false a jump is made around all subsequent** inner loops (or around the "..." if the test occurs within the inner-** most loop)**** OUTER JOINS**** An outer join of tables t1 and t2 is conceptally coded as follows:****    foreach row1 in t1 do**      flag = 0**      foreach row2 in t2 do**        start:**          ...**          flag = 1**      end**      if flag==0 then**        move the row2 cursor to a null row**        goto start**      fi**    end**** ORDER BY CLAUSE PROCESSING**** *ppOrderBy is a pointer to the ORDER BY clause of a SELECT statement,** if there is one.  If there is no ORDER BY clause or if this routine** is called from an UPDATE or DELETE statement, then ppOrderBy is NULL.**** If an index can be used so that the natural output order of the table** scan is correct for the ORDER BY clause, then that index is used and** *ppOrderBy is set to NULL.  This is an optimization that prevents an** unnecessary sort of the result set if an index appropriate for the** ORDER BY clause already exists.**** If the where clause loops cannot be arranged to provide the correct** output order, then the *ppOrderBy is unchanged.*/WhereInfo *sqliteWhereBegin(  Parse *pParse,       /* The parser context */  SrcList *pTabList,   /* A list of all tables to be scanned */  Expr *pWhere,        /* The WHERE clause */  int pushKey,         /* If TRUE, leave the table key on the stack */  ExprList **ppOrderBy /* An ORDER BY clause, or NULL */){  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 */  int loopMask;        /* One bit set for each outer loop */  int haveKey;         /* True if KEY is on the stack */  ExprMaskSet maskSet; /* The expression mask set */  int iDirectEq[32];   /* Term of the form ROWID==X for the N-th table */  int iDirectLt[32];   /* Term of the form ROWID<X or ROWID<=X */  int iDirectGt[32];   /* Term of the form ROWID>X or ROWID>=X */  ExprInfo aExpr[101]; /* The WHERE clause is divided into these expressions */  /* 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));  nExpr = exprSplit(ARRAYSIZE(aExpr), aExpr, pWhere);  if( nExpr==ARRAYSIZE(aExpr) ){    sqliteErrorMsg(pParse, "WHERE clause too complex - no more "       "than %d terms allowed", (int)ARRAYSIZE(aExpr)-1);    return 0;  }    /* Allocate and initialize the WhereInfo structure that will become the  ** return value.  */  pWInfo = sqliteMalloc( sizeof(WhereInfo) + pTabList->nSrc*sizeof(WhereLevel));  if( sqlite_malloc_failed ){    sqliteFree(pWInfo);    return 0;  }  pWInfo->pParse = pParse;  pWInfo->pTabList = pTabList;  pWInfo->peakNTab = pWInfo->savedNTab = pParse->nTab;  pWInfo->iBreak = sqliteVdbeMakeLabel(v);  /* Special case: a WHERE clause that is constant.  Evaluate the  ** expression and either jump over all of the code or fall thru.