select.c

sqlite数据库管理系统开放源码

**
** Examples:
**
**     CREATE TABLE one(a INTEGER, b TEXT);
**     CREATE TABLE two(c VARCHAR(5), d FLOAT);
**
**     SELECT b, b FROM one UNION SELECT d, c FROM two ORDER BY 1, 2;
**
** The primary sort key will use SQLITE_SO_NUM because the "d" in
** the second SELECT is numeric.  The 1st column of the first SELECT
** is text but that does not matter because a numeric always overrides
** a text.
**
** The secondary key will use the SQLITE_SO_TEXT sort order because
** both the (second) "b" in the first SELECT and the "c" in the second
** SELECT have a datatype of text.
*/ 
static void multiSelectSortOrder(Select *p, ExprList *pOrderBy){
  int i;
  ExprList *pEList;
  if( pOrderBy==0 ) return;
  if( p==0 ){
    for(i=0; i<pOrderBy->nExpr; i++){
      pOrderBy->a[i].pExpr->dataType = SQLITE_SO_TEXT;
    }
    return;
  }
  multiSelectSortOrder(p->pPrior, pOrderBy);
  pEList = p->pEList;
  for(i=0; i<pOrderBy->nExpr; i++){
    Expr *pE = pOrderBy->a[i].pExpr;
    if( pE->dataType==SQLITE_SO_NUM ) continue;
    assert( pE->iColumn>=0 );
    if( pEList->nExpr>pE->iColumn ){
      pE->dataType = sqliteExprType(pEList->a[pE->iColumn].pExpr);
    }
  }
}

/*
** Compute the iLimit and iOffset fields of the SELECT based on the
** nLimit and nOffset fields.  nLimit and nOffset hold the integers
** that appear in the original SQL statement after the LIMIT and OFFSET
** keywords.  Or that hold -1 and 0 if those keywords are omitted.
** iLimit and iOffset are the integer memory register numbers for
** counters used to compute the limit and offset.  If there is no
** limit and/or offset, then iLimit and iOffset are negative.
**
** This routine changes the values if iLimit and iOffset only if
** a limit or offset is defined by nLimit and nOffset.  iLimit and
** iOffset should have been preset to appropriate default values
** (usually but not always -1) prior to calling this routine.
** Only if nLimit>=0 or nOffset>0 do the limit registers get
** redefined.  The UNION ALL operator uses this property to force
** the reuse of the same limit and offset registers across multiple
** SELECT statements.
*/
static void computeLimitRegisters(Parse *pParse, Select *p){
  /* 
  ** If the comparison is p->nLimit>0 then "LIMIT 0" shows
  ** all rows.  It is the same as no limit. If the comparision is
  ** p->nLimit>=0 then "LIMIT 0" show no rows at all.
  ** "LIMIT -1" always shows all rows.  There is some
  ** contraversy about what the correct behavior should be.
  ** The current implementation interprets "LIMIT 0" to mean
  ** no rows.
  */
  if( p->nLimit>=0 ){
    int iMem = pParse->nMem++;
    Vdbe *v = sqliteGetVdbe(pParse);
    if( v==0 ) return;
    sqliteVdbeAddOp(v, OP_Integer, -p->nLimit, 0);
    sqliteVdbeAddOp(v, OP_MemStore, iMem, 1);
    p->iLimit = iMem;
  }
  if( p->nOffset>0 ){
    int iMem = pParse->nMem++;
    Vdbe *v = sqliteGetVdbe(pParse);
    if( v==0 ) return;
    sqliteVdbeAddOp(v, OP_Integer, -p->nOffset, 0);
    sqliteVdbeAddOp(v, OP_MemStore, iMem, 1);
    p->iOffset = iMem;
  }
}

/*
** This routine is called to process a query that is really the union
** or intersection of two or more separate queries.
**
** "p" points to the right-most of the two queries.  the query on the
** left is p->pPrior.  The left query could also be a compound query
** in which case this routine will be called recursively. 
**
** The results of the total query are to be written into a destination
** of type eDest with parameter iParm.
**
** Example 1:  Consider a three-way compound SQL statement.
**
**     SELECT a FROM t1 UNION SELECT b FROM t2 UNION SELECT c FROM t3
**
** This statement is parsed up as follows:
**
**     SELECT c FROM t3
**      |
**      `----->  SELECT b FROM t2
**                |
**                `------>  SELECT a FROM t1
**
** The arrows in the diagram above represent the Select.pPrior pointer.
** So if this routine is called with p equal to the t3 query, then
** pPrior will be the t2 query.  p->op will be TK_UNION in this case.
**
** Notice that because of the way SQLite parses compound SELECTs, the
** individual selects always group from left to right.
*/
static int multiSelect(Parse *pParse, Select *p, int eDest, int iParm){
  int rc;             /* Success code from a subroutine */
  Select *pPrior;     /* Another SELECT immediately to our left */
  Vdbe *v;            /* Generate code to this VDBE */

  /* Make sure there is no ORDER BY or LIMIT clause on prior SELECTs.  Only
  ** the last SELECT in the series may have an ORDER BY or LIMIT.
  */
  if( p==0 || p->pPrior==0 ) return 1;
  pPrior = p->pPrior;
  if( pPrior->pOrderBy ){
    sqliteErrorMsg(pParse,"ORDER BY clause should come after %s not before",
      selectOpName(p->op));
    return 1;
  }
  if( pPrior->nLimit>=0 || pPrior->nOffset>0 ){
    sqliteErrorMsg(pParse,"LIMIT clause should come after %s not before",
      selectOpName(p->op));
    return 1;
  }

  /* Make sure we have a valid query engine.  If not, create a new one.
  */
  v = sqliteGetVdbe(pParse);
  if( v==0 ) return 1;

  /* Create the destination temporary table if necessary
  */
  if( eDest==SRT_TempTable ){
    sqliteVdbeAddOp(v, OP_OpenTemp, iParm, 0);
    eDest = SRT_Table;
  }

  /* Generate code for the left and right SELECT statements.
  */
  switch( p->op ){
    case TK_ALL: {
      if( p->pOrderBy==0 ){
        pPrior->nLimit = p->nLimit;
        pPrior->nOffset = p->nOffset;
        rc = sqliteSelect(pParse, pPrior, eDest, iParm, 0, 0, 0);
        if( rc ) return rc;
        p->pPrior = 0;
        p->iLimit = pPrior->iLimit;
        p->iOffset = pPrior->iOffset;
        p->nLimit = -1;
        p->nOffset = 0;
        rc = sqliteSelect(pParse, p, eDest, iParm, 0, 0, 0);
        p->pPrior = pPrior;
        if( rc ) return rc;
        break;
      }
      /* For UNION ALL ... ORDER BY fall through to the next case */
    }
    case TK_EXCEPT:
    case TK_UNION: {
      int unionTab;    /* Cursor number of the temporary table holding result */
      int op;          /* One of the SRT_ operations to apply to self */
      int priorOp;     /* The SRT_ operation to apply to prior selects */
      int nLimit, nOffset; /* Saved values of p->nLimit and p->nOffset */
      ExprList *pOrderBy;  /* The ORDER BY clause for the right SELECT */

      priorOp = p->op==TK_ALL ? SRT_Table : SRT_Union;
      if( eDest==priorOp && p->pOrderBy==0 && p->nLimit<0 && p->nOffset==0 ){
        /* We can reuse a temporary table generated by a SELECT to our
        ** right.
        */
        unionTab = iParm;
      }else{
        /* We will need to create our own temporary table to hold the
        ** intermediate results.
        */
        unionTab = pParse->nTab++;
        if( p->pOrderBy 
        && matchOrderbyToColumn(pParse, p, p->pOrderBy, unionTab, 1) ){
          return 1;
        }
        if( p->op!=TK_ALL ){
          sqliteVdbeAddOp(v, OP_OpenTemp, unionTab, 1);
          sqliteVdbeAddOp(v, OP_KeyAsData, unionTab, 1);
        }else{
          sqliteVdbeAddOp(v, OP_OpenTemp, unionTab, 0);
        }
      }

      /* Code the SELECT statements to our left
      */
      rc = sqliteSelect(pParse, pPrior, priorOp, unionTab, 0, 0, 0);
      if( rc ) return rc;

      /* Code the current SELECT statement
      */
      switch( p->op ){
         case TK_EXCEPT:  op = SRT_Except;   break;
         case TK_UNION:   op = SRT_Union;    break;
         case TK_ALL:     op = SRT_Table;    break;
      }
      p->pPrior = 0;
      pOrderBy = p->pOrderBy;
      p->pOrderBy = 0;
      nLimit = p->nLimit;
      p->nLimit = -1;
      nOffset = p->nOffset;
      p->nOffset = 0;
      rc = sqliteSelect(pParse, p, op, unionTab, 0, 0, 0);
      p->pPrior = pPrior;
      p->pOrderBy = pOrderBy;
      p->nLimit = nLimit;
      p->nOffset = nOffset;
      if( rc ) return rc;

      /* Convert the data in the temporary table into whatever form
      ** it is that we currently need.
      */      
      if( eDest!=priorOp || unionTab!=iParm ){
        int iCont, iBreak, iStart;
        assert( p->pEList );
        if( eDest==SRT_Callback ){
          generateColumnNames(pParse, 0, p->pEList);
          generateColumnTypes(pParse, p->pSrc, p->pEList);
        }
        iBreak = sqliteVdbeMakeLabel(v);
        iCont = sqliteVdbeMakeLabel(v);
        sqliteVdbeAddOp(v, OP_Rewind, unionTab, iBreak);
        computeLimitRegisters(pParse, p);
        iStart = sqliteVdbeCurrentAddr(v);
        multiSelectSortOrder(p, p->pOrderBy);
        rc = selectInnerLoop(pParse, p, p->pEList, unionTab, p->pEList->nExpr,
                             p->pOrderBy, -1, eDest, iParm, 
                             iCont, iBreak);
        if( rc ) return 1;
        sqliteVdbeResolveLabel(v, iCont);
        sqliteVdbeAddOp(v, OP_Next, unionTab, iStart);
        sqliteVdbeResolveLabel(v, iBreak);
        sqliteVdbeAddOp(v, OP_Close, unionTab, 0);
        if( p->pOrderBy ){
          generateSortTail(p, v, p->pEList->nExpr, eDest, iParm);
        }
      }
      break;
    }
    case TK_INTERSECT: {
      int tab1, tab2;
      int iCont, iBreak, iStart;
      int nLimit, nOffset;

      /* INTERSECT is different from the others since it requires
      ** two temporary tables.  Hence it has its own case.  Begin
      ** by allocating the tables we will need.
      */
      tab1 = pParse->nTab++;
      tab2 = pParse->nTab++;
      if( p->pOrderBy && matchOrderbyToColumn(pParse,p,p->pOrderBy,tab1,1) ){
        return 1;
      }
      sqliteVdbeAddOp(v, OP_OpenTemp, tab1, 1);
      sqliteVdbeAddOp(v, OP_KeyAsData, tab1, 1);

      /* Code the SELECTs to our left into temporary table "tab1".
      */
      rc = sqliteSelect(pParse, pPrior, SRT_Union, tab1, 0, 0, 0);
      if( rc ) return rc;

      /* Code the current SELECT into temporary table "tab2"
      */
      sqliteVdbeAddOp(v, OP_OpenTemp, tab2, 1);
      sqliteVdbeAddOp(v, OP_KeyAsData, tab2, 1);
      p->pPrior = 0;
      nLimit = p->nLimit;
      p->nLimit = -1;
      nOffset = p->nOffset;
      p->nOffset = 0;
      rc = sqliteSelect(pParse, p, SRT_Union, tab2, 0, 0, 0);
      p->pPrior = pPrior;
      p->nLimit = nLimit;
      p->nOffset = nOffset;
      if( rc ) return rc;

      /* Generate code to take the intersection of the two temporary
      ** tables.
      */
      assert( p->pEList );
      if( eDest==SRT_Callback ){
        generateColumnNames(pParse, 0, p->pEList);
        generateColumnTypes(pParse, p->pSrc, p->pEList);
      }
      iBreak = sqliteVdbeMakeLabel(v);
      iCont = sqliteVdbeMakeLabel(v);
      sqliteVdbeAddOp(v, OP_Rewind, tab1, iBreak);
      computeLimitRegisters(pParse, p);
      iStart = sqliteVdbeAddOp(v, OP_FullKey, tab1, 0);
      sqliteVdbeAddOp(v, OP_NotFound, tab2, iCont);
      multiSelectSortOrder(p, p->pOrderBy);
      rc = selectInnerLoop(pParse, p, p->pEList, tab1, p->pEList->nExpr,
                             p->pOrderBy, -1, eDest, iParm, 
                             iCont, iBreak);
      if( rc ) return 1;
      sqliteVdbeResolveLabel(v, iCont);
      sqliteVdbeAddOp(v, OP_Next, tab1, iStart);
      sqliteVdbeResolveLabel(v, iBreak);
      sqliteVdbeAddOp(v, OP_Close, tab2, 0);
      sqliteVdbeAddOp(v, OP_Close, tab1, 0);
      if( p->pOrderBy ){
        generateSortTail(p, v, p->pEList->nExpr, eDest, iParm);
      }
      break;
    }
  }
  assert( p->pEList && pPrior->pEList );
  if( p->pEList->nExpr!=pPrior->pEList->nExpr ){
    sqliteErrorMsg(pParse, "SELECTs to the left and right of %s"
      " do not have the same number of result columns", selectOpName(p->op));
    return 1;
  }
  return 0;
}

/*
** Scan through the expression pExpr.  Replace every reference to
** a column in table number iTable with a copy of the iColumn-th
** entry in pEList.  (But leave references to the ROWID column 
** unchanged.)
**
** This routine is part of the flattening procedure.  A subquery
** whose result set is defined by pEList appears as entry in the
** FROM clause of a SELECT such that the VDBE cursor assigned to that
** FORM clause entry is iTable.  This routine make the necessary 
** changes to pExpr so that it refers directly to the source table
** of the subquery rather the result set of the subquery.
*/
static void substExprList(ExprList*,int,ExprList*);  /* Forward Decl */
static void substExpr(Expr *pExpr, int iTable, ExprList *pEList){
  if( pExpr==0 ) return;
  if( pExpr->op==TK_COLUMN && pExpr->iTable==iTable ){
    if( pExpr->iColumn<0 ){
      pExpr->op = TK_NULL;
    }else{
      Expr *pNew;
      assert( pEList!=0 && pExpr->iColumn<pEList->nExpr );
      assert( pExpr->pLeft==0 && pExpr->pRight==0 && pExpr->pList==0 );
      pNew = pEList->a[pExpr->iColumn].pExpr;
      assert( pNew!=0 );
      pExpr->op = pNew->op;
      pExpr->dataType = pNew->dataType;
      assert( pExpr->pLeft==0 );
      pExpr->pLeft = sqliteExprDup(pNew->pLeft);
      assert( pExpr->pRight==0 );
      pExpr->pRight = sqliteExprDup(pNew->pRight);
      assert( pExpr->pList==0 );
      pExpr->pList = sqliteExprListDup(pNew->pList);
      pExpr->iTable = pNew->iTable;
      pExpr->iColumn = pNew->iColumn;
      pExpr->iAgg = pNew->iAgg;
      sqliteTokenCopy(&pExpr->token, &pNew->token);
      sqliteTokenCopy(&pExpr->span, &pNew->span);
    }
  }else{
    substExpr(pExpr->pLeft, iTable, pEList);
    substExpr(pExpr->pRight, iTable, pEList);
    substExprList(pExpr->pList, iTable, pEList);
  }
}
static void 
substExprList(ExprList *pList, int iTable, ExprList *pEList){
  int i;
  if( pList==0 ) return;
  for(i=0; i<pList->nExpr; i++){
    substExpr(pList->a[i].pExpr, iTable, pEList);
  }
}

/*
** This routine attempts to flatten subqueries in order to speed
** execution.  It returns 1 if it makes changes and 0 if no flattening
** occurs.
**
** To understand the concept of flattening, consider the following
** query: