select.c

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.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle SELECT statements in SQLite.
**
** $Id: select.c,v 1.161.2.4 2004/07/20 01:45:49 drh Exp $
*/
#include "sqliteInt.h"


/*
** Allocate a new Select structure and return a pointer to that
** structure.
*/
Select *sqliteSelectNew(
  ExprList *pEList,     /* which columns to include in the result */
  SrcList *pSrc,        /* the FROM clause -- which tables to scan */
  Expr *pWhere,         /* the WHERE clause */
  ExprList *pGroupBy,   /* the GROUP BY clause */
  Expr *pHaving,        /* the HAVING clause */
  ExprList *pOrderBy,   /* the ORDER BY clause */
  int isDistinct,       /* true if the DISTINCT keyword is present */
  int nLimit,           /* LIMIT value.  -1 means not used */
  int nOffset           /* OFFSET value.  0 means no offset */
){
  Select *pNew;
  pNew = sqliteMalloc( sizeof(*pNew) );
  if( pNew==0 ){
    sqliteExprListDelete(pEList);
    sqliteSrcListDelete(pSrc);
    sqliteExprDelete(pWhere);
    sqliteExprListDelete(pGroupBy);
    sqliteExprDelete(pHaving);
    sqliteExprListDelete(pOrderBy);
  }else{
    if( pEList==0 ){
      pEList = sqliteExprListAppend(0, sqliteExpr(TK_ALL,0,0,0), 0);
    }
    pNew->pEList = pEList;
    pNew->pSrc = pSrc;
    pNew->pWhere = pWhere;
    pNew->pGroupBy = pGroupBy;
    pNew->pHaving = pHaving;
    pNew->pOrderBy = pOrderBy;
    pNew->isDistinct = isDistinct;
    pNew->op = TK_SELECT;
    pNew->nLimit = nLimit;
    pNew->nOffset = nOffset;
    pNew->iLimit = -1;
    pNew->iOffset = -1;
  }
  return pNew;
}

/*
** Given 1 to 3 identifiers preceeding the JOIN keyword, determine the
** type of join.  Return an integer constant that expresses that type
** in terms of the following bit values:
**
**     JT_INNER
**     JT_OUTER
**     JT_NATURAL
**     JT_LEFT
**     JT_RIGHT
**
** A full outer join is the combination of JT_LEFT and JT_RIGHT.
**
** If an illegal or unsupported join type is seen, then still return
** a join type, but put an error in the pParse structure.
*/
int sqliteJoinType(Parse *pParse, Token *pA, Token *pB, Token *pC){
  int jointype = 0;
  Token *apAll[3];
  Token *p;
  static struct {
    const char *zKeyword;
    int nChar;
    int code;
  } keywords[] = {
    { "natural", 7, JT_NATURAL },
    { "left",    4, JT_LEFT|JT_OUTER },
    { "right",   5, JT_RIGHT|JT_OUTER },
    { "full",    4, JT_LEFT|JT_RIGHT|JT_OUTER },
    { "outer",   5, JT_OUTER },
    { "inner",   5, JT_INNER },
    { "cross",   5, JT_INNER },
  };
  int i, j;
  apAll[0] = pA;
  apAll[1] = pB;
  apAll[2] = pC;
  for(i=0; i<3 && apAll[i]; i++){
    p = apAll[i];
    for(j=0; j<sizeof(keywords)/sizeof(keywords[0]); j++){
      if( p->n==keywords[j].nChar 
          && sqliteStrNICmp(p->z, keywords[j].zKeyword, p->n)==0 ){
        jointype |= keywords[j].code;
        break;
      }
    }
    if( j>=sizeof(keywords)/sizeof(keywords[0]) ){
      jointype |= JT_ERROR;
      break;
    }
  }
  if(
     (jointype & (JT_INNER|JT_OUTER))==(JT_INNER|JT_OUTER) ||
     (jointype & JT_ERROR)!=0
  ){
    static Token dummy = { 0, 0 };
    char *zSp1 = " ", *zSp2 = " ";
    if( pB==0 ){ pB = &dummy; zSp1 = 0; }
    if( pC==0 ){ pC = &dummy; zSp2 = 0; }
    sqliteSetNString(&pParse->zErrMsg, "unknown or unsupported join type: ", 0,
       pA->z, pA->n, zSp1, 1, pB->z, pB->n, zSp2, 1, pC->z, pC->n, 0);
    pParse->nErr++;
    jointype = JT_INNER;
  }else if( jointype & JT_RIGHT ){
    sqliteErrorMsg(pParse, 
      "RIGHT and FULL OUTER JOINs are not currently supported");
    jointype = JT_INNER;
  }
  return jointype;
}

/*
** Return the index of a column in a table.  Return -1 if the column
** is not contained in the table.
*/
static int columnIndex(Table *pTab, const char *zCol){
  int i;
  for(i=0; i<pTab->nCol; i++){
    if( sqliteStrICmp(pTab->aCol[i].zName, zCol)==0 ) return i;
  }
  return -1;
}

/*
** Add a term to the WHERE expression in *ppExpr that requires the
** zCol column to be equal in the two tables pTab1 and pTab2.
*/
static void addWhereTerm(
  const char *zCol,        /* Name of the column */
  const Table *pTab1,      /* First table */
  const Table *pTab2,      /* Second table */
  Expr **ppExpr            /* Add the equality term to this expression */
){
  Token dummy;
  Expr *pE1a, *pE1b, *pE1c;
  Expr *pE2a, *pE2b, *pE2c;
  Expr *pE;

  dummy.z = zCol;
  dummy.n = strlen(zCol);
  dummy.dyn = 0;
  pE1a = sqliteExpr(TK_ID, 0, 0, &dummy);
  pE2a = sqliteExpr(TK_ID, 0, 0, &dummy);
  dummy.z = pTab1->zName;
  dummy.n = strlen(dummy.z);
  pE1b = sqliteExpr(TK_ID, 0, 0, &dummy);
  dummy.z = pTab2->zName;
  dummy.n = strlen(dummy.z);
  pE2b = sqliteExpr(TK_ID, 0, 0, &dummy);
  pE1c = sqliteExpr(TK_DOT, pE1b, pE1a, 0);
  pE2c = sqliteExpr(TK_DOT, pE2b, pE2a, 0);
  pE = sqliteExpr(TK_EQ, pE1c, pE2c, 0);
  ExprSetProperty(pE, EP_FromJoin);
  if( *ppExpr ){
    *ppExpr = sqliteExpr(TK_AND, *ppExpr, pE, 0);
  }else{
    *ppExpr = pE;
  }
}

/*
** Set the EP_FromJoin property on all terms of the given expression.
**
** The EP_FromJoin property is used on terms of an expression to tell
** the LEFT OUTER JOIN processing logic that this term is part of the
** join restriction specified in the ON or USING clause and not a part
** of the more general WHERE clause.  These terms are moved over to the
** WHERE clause during join processing but we need to remember that they
** originated in the ON or USING clause.
*/
static void setJoinExpr(Expr *p){
  while( p ){
    ExprSetProperty(p, EP_FromJoin);
    setJoinExpr(p->pLeft);
    p = p->pRight;
  } 
}

/*
** This routine processes the join information for a SELECT statement.
** ON and USING clauses are converted into extra terms of the WHERE clause.
** NATURAL joins also create extra WHERE clause terms.
**
** This routine returns the number of errors encountered.
*/
static int sqliteProcessJoin(Parse *pParse, Select *p){
  SrcList *pSrc;
  int i, j;
  pSrc = p->pSrc;
  for(i=0; i<pSrc->nSrc-1; i++){
    struct SrcList_item *pTerm = &pSrc->a[i];
    struct SrcList_item *pOther = &pSrc->a[i+1];

    if( pTerm->pTab==0 || pOther->pTab==0 ) continue;

    /* When the NATURAL keyword is present, add WHERE clause terms for
    ** every column that the two tables have in common.
    */
    if( pTerm->jointype & JT_NATURAL ){
      Table *pTab;
      if( pTerm->pOn || pTerm->pUsing ){
        sqliteErrorMsg(pParse, "a NATURAL join may not have "
           "an ON or USING clause", 0);
        return 1;
      }
      pTab = pTerm->pTab;
      for(j=0; j<pTab->nCol; j++){
        if( columnIndex(pOther->pTab, pTab->aCol[j].zName)>=0 ){
          addWhereTerm(pTab->aCol[j].zName, pTab, pOther->pTab, &p->pWhere);
        }
      }
    }

    /* Disallow both ON and USING clauses in the same join
    */
    if( pTerm->pOn && pTerm->pUsing ){
      sqliteErrorMsg(pParse, "cannot have both ON and USING "
        "clauses in the same join");
      return 1;
    }

    /* Add the ON clause to the end of the WHERE clause, connected by
    ** and AND operator.
    */
    if( pTerm->pOn ){
      setJoinExpr(pTerm->pOn);
      if( p->pWhere==0 ){
        p->pWhere = pTerm->pOn;
      }else{
        p->pWhere = sqliteExpr(TK_AND, p->pWhere, pTerm->pOn, 0);
      }
      pTerm->pOn = 0;
    }

    /* Create extra terms on the WHERE clause for each column named
    ** in the USING clause.  Example: If the two tables to be joined are 
    ** A and B and the USING clause names X, Y, and Z, then add this
    ** to the WHERE clause:    A.X=B.X AND A.Y=B.Y AND A.Z=B.Z
    ** Report an error if any column mentioned in the USING clause is
    ** not contained in both tables to be joined.
    */
    if( pTerm->pUsing ){
      IdList *pList;
      int j;
      assert( i<pSrc->nSrc-1 );
      pList = pTerm->pUsing;
      for(j=0; j<pList->nId; j++){
        if( columnIndex(pTerm->pTab, pList->a[j].zName)<0 ||
            columnIndex(pOther->pTab, pList->a[j].zName)<0 ){
          sqliteErrorMsg(pParse, "cannot join using column %s - column "
            "not present in both tables", pList->a[j].zName);
          return 1;
        }
        addWhereTerm(pList->a[j].zName, pTerm->pTab, pOther->pTab, &p->pWhere);
      }
    }
  }
  return 0;
}

/*
** Delete the given Select structure and all of its substructures.
*/
void sqliteSelectDelete(Select *p){
  if( p==0 ) return;
  sqliteExprListDelete(p->pEList);
  sqliteSrcListDelete(p->pSrc);
  sqliteExprDelete(p->pWhere);
  sqliteExprListDelete(p->pGroupBy);
  sqliteExprDelete(p->pHaving);
  sqliteExprListDelete(p->pOrderBy);
  sqliteSelectDelete(p->pPrior);
  sqliteFree(p->zSelect);
  sqliteFree(p);
}

/*
** Delete the aggregate information from the parse structure.
*/
static void sqliteAggregateInfoReset(Parse *pParse){
  sqliteFree(pParse->aAgg);
  pParse->aAgg = 0;
  pParse->nAgg = 0;
  pParse->useAgg = 0;
}

/*
** Insert code into "v" that will push the record on the top of the
** stack into the sorter.
*/
static void pushOntoSorter(Parse *pParse, Vdbe *v, ExprList *pOrderBy){
  char *zSortOrder;
  int i;
  zSortOrder = sqliteMalloc( pOrderBy->nExpr + 1 );
  if( zSortOrder==0 ) return;
  for(i=0; i<pOrderBy->nExpr; i++){
    int order = pOrderBy->a[i].sortOrder;
    int type;
    int c;
    if( (order & SQLITE_SO_TYPEMASK)==SQLITE_SO_TEXT ){
      type = SQLITE_SO_TEXT;
    }else if( (order & SQLITE_SO_TYPEMASK)==SQLITE_SO_NUM ){
      type = SQLITE_SO_NUM;
    }else if( pParse->db->file_format>=4 ){
      type = sqliteExprType(pOrderBy->a[i].pExpr);
    }else{
      type = SQLITE_SO_NUM;
    }
    if( (order & SQLITE_SO_DIRMASK)==SQLITE_SO_ASC ){
      c = type==SQLITE_SO_TEXT ? 'A' : '+';
    }else{
      c = type==SQLITE_SO_TEXT ? 'D' : '-';
    }
    zSortOrder[i] = c;
    sqliteExprCode(pParse, pOrderBy->a[i].pExpr);
  }
  zSortOrder[pOrderBy->nExpr] = 0;
  sqliteVdbeOp3(v, OP_SortMakeKey, pOrderBy->nExpr, 0, zSortOrder, P3_DYNAMIC);
  sqliteVdbeAddOp(v, OP_SortPut, 0, 0);
}

/*
** This routine adds a P3 argument to the last VDBE opcode that was
** inserted. The P3 argument added is a string suitable for the 
** OP_MakeKey or OP_MakeIdxKey opcodes.  The string consists of
** characters 't' or 'n' depending on whether or not the various
** fields of the key to be generated should be treated as numeric
** or as text.  See the OP_MakeKey and OP_MakeIdxKey opcode
** documentation for additional information about the P3 string.
** See also the sqliteAddIdxKeyType() routine.
*/
void sqliteAddKeyType(Vdbe *v, ExprList *pEList){
  int nColumn = pEList->nExpr;
  char *zType = sqliteMalloc( nColumn+1 );
  int i;
  if( zType==0 ) return;
  for(i=0; i<nColumn; i++){
    zType[i] = sqliteExprType(pEList->a[i].pExpr)==SQLITE_SO_NUM ? 'n' : 't';
  }
  zType[i] = 0;
  sqliteVdbeChangeP3(v, -1, zType, P3_DYNAMIC);
}

/*
** Add code to implement the OFFSET and LIMIT
*/
static void codeLimiter(
  Vdbe *v,          /* Generate code into this VM */
  Select *p,        /* The SELECT statement being coded */
  int iContinue,    /* Jump here to skip the current record */
  int iBreak,       /* Jump here to end the loop */
  int nPop          /* Number of times to pop stack when jumping */
){
  if( p->iOffset>=0 ){
    int addr = sqliteVdbeCurrentAddr(v) + 2;
    if( nPop>0 ) addr++;
    sqliteVdbeAddOp(v, OP_MemIncr, p->iOffset, addr);
    if( nPop>0 ){
      sqliteVdbeAddOp(v, OP_Pop, nPop, 0);
    }
    sqliteVdbeAddOp(v, OP_Goto, 0, iContinue);
  }
  if( p->iLimit>=0 ){
    sqliteVdbeAddOp(v, OP_MemIncr, p->iLimit, iBreak);
  }
}

/*
** This routine generates the code for the inside of the inner loop
** of a SELECT.