Back to index

php5  5.3.10
select.c
Go to the documentation of this file.
00001 /*
00002 ** 2001 September 15
00003 **
00004 ** The author disclaims copyright to this source code.  In place of
00005 ** a legal notice, here is a blessing:
00006 **
00007 **    May you do good and not evil.
00008 **    May you find forgiveness for yourself and forgive others.
00009 **    May you share freely, never taking more than you give.
00010 **
00011 *************************************************************************
00012 ** This file contains C code routines that are called by the parser
00013 ** to handle SELECT statements in SQLite.
00014 **
00015 ** $Id: select.c 195361 2005-09-07 15:11:33Z iliaa $
00016 */
00017 #include "sqliteInt.h"
00018 
00019 
00020 /*
00021 ** Allocate a new Select structure and return a pointer to that
00022 ** structure.
00023 */
00024 Select *sqliteSelectNew(
00025   ExprList *pEList,     /* which columns to include in the result */
00026   SrcList *pSrc,        /* the FROM clause -- which tables to scan */
00027   Expr *pWhere,         /* the WHERE clause */
00028   ExprList *pGroupBy,   /* the GROUP BY clause */
00029   Expr *pHaving,        /* the HAVING clause */
00030   ExprList *pOrderBy,   /* the ORDER BY clause */
00031   int isDistinct,       /* true if the DISTINCT keyword is present */
00032   int nLimit,           /* LIMIT value.  -1 means not used */
00033   int nOffset           /* OFFSET value.  0 means no offset */
00034 ){
00035   Select *pNew;
00036   pNew = sqliteMalloc( sizeof(*pNew) );
00037   if( pNew==0 ){
00038     sqliteExprListDelete(pEList);
00039     sqliteSrcListDelete(pSrc);
00040     sqliteExprDelete(pWhere);
00041     sqliteExprListDelete(pGroupBy);
00042     sqliteExprDelete(pHaving);
00043     sqliteExprListDelete(pOrderBy);
00044   }else{
00045     if( pEList==0 ){
00046       pEList = sqliteExprListAppend(0, sqliteExpr(TK_ALL,0,0,0), 0);
00047     }
00048     pNew->pEList = pEList;
00049     pNew->pSrc = pSrc;
00050     pNew->pWhere = pWhere;
00051     pNew->pGroupBy = pGroupBy;
00052     pNew->pHaving = pHaving;
00053     pNew->pOrderBy = pOrderBy;
00054     pNew->isDistinct = isDistinct;
00055     pNew->op = TK_SELECT;
00056     pNew->nLimit = nLimit;
00057     pNew->nOffset = nOffset;
00058     pNew->iLimit = -1;
00059     pNew->iOffset = -1;
00060   }
00061   return pNew;
00062 }
00063 
00064 /*
00065 ** Given 1 to 3 identifiers preceeding the JOIN keyword, determine the
00066 ** type of join.  Return an integer constant that expresses that type
00067 ** in terms of the following bit values:
00068 **
00069 **     JT_INNER
00070 **     JT_OUTER
00071 **     JT_NATURAL
00072 **     JT_LEFT
00073 **     JT_RIGHT
00074 **
00075 ** A full outer join is the combination of JT_LEFT and JT_RIGHT.
00076 **
00077 ** If an illegal or unsupported join type is seen, then still return
00078 ** a join type, but put an error in the pParse structure.
00079 */
00080 int sqliteJoinType(Parse *pParse, Token *pA, Token *pB, Token *pC){
00081   int jointype = 0;
00082   Token *apAll[3];
00083   Token *p;
00084   static struct {
00085     const char *zKeyword;
00086     int nChar;
00087     int code;
00088   } keywords[] = {
00089     { "natural", 7, JT_NATURAL },
00090     { "left",    4, JT_LEFT|JT_OUTER },
00091     { "right",   5, JT_RIGHT|JT_OUTER },
00092     { "full",    4, JT_LEFT|JT_RIGHT|JT_OUTER },
00093     { "outer",   5, JT_OUTER },
00094     { "inner",   5, JT_INNER },
00095     { "cross",   5, JT_INNER },
00096   };
00097   int i, j;
00098   apAll[0] = pA;
00099   apAll[1] = pB;
00100   apAll[2] = pC;
00101   for(i=0; i<3 && apAll[i]; i++){
00102     p = apAll[i];
00103     for(j=0; j<sizeof(keywords)/sizeof(keywords[0]); j++){
00104       if( p->n==keywords[j].nChar 
00105           && sqliteStrNICmp(p->z, keywords[j].zKeyword, p->n)==0 ){
00106         jointype |= keywords[j].code;
00107         break;
00108       }
00109     }
00110     if( j>=sizeof(keywords)/sizeof(keywords[0]) ){
00111       jointype |= JT_ERROR;
00112       break;
00113     }
00114   }
00115   if(
00116      (jointype & (JT_INNER|JT_OUTER))==(JT_INNER|JT_OUTER) ||
00117      (jointype & JT_ERROR)!=0
00118   ){
00119     static Token dummy = { 0, 0 };
00120     char *zSp1 = " ", *zSp2 = " ";
00121     if( pB==0 ){ pB = &dummy; zSp1 = 0; }
00122     if( pC==0 ){ pC = &dummy; zSp2 = 0; }
00123     sqliteSetNString(&pParse->zErrMsg, "unknown or unsupported join type: ", 0,
00124        pA->z, pA->n, zSp1, 1, pB->z, pB->n, zSp2, 1, pC->z, pC->n, 0);
00125     pParse->nErr++;
00126     jointype = JT_INNER;
00127   }else if( jointype & JT_RIGHT ){
00128     sqliteErrorMsg(pParse, 
00129       "RIGHT and FULL OUTER JOINs are not currently supported");
00130     jointype = JT_INNER;
00131   }
00132   return jointype;
00133 }
00134 
00135 /*
00136 ** Return the index of a column in a table.  Return -1 if the column
00137 ** is not contained in the table.
00138 */
00139 static int columnIndex(Table *pTab, const char *zCol){
00140   int i;
00141   for(i=0; i<pTab->nCol; i++){
00142     if( sqliteStrICmp(pTab->aCol[i].zName, zCol)==0 ) return i;
00143   }
00144   return -1;
00145 }
00146 
00147 /*
00148 ** Add a term to the WHERE expression in *ppExpr that requires the
00149 ** zCol column to be equal in the two tables pTab1 and pTab2.
00150 */
00151 static void addWhereTerm(
00152   const char *zCol,        /* Name of the column */
00153   const Table *pTab1,      /* First table */
00154   const Table *pTab2,      /* Second table */
00155   Expr **ppExpr            /* Add the equality term to this expression */
00156 ){
00157   Token dummy;
00158   Expr *pE1a, *pE1b, *pE1c;
00159   Expr *pE2a, *pE2b, *pE2c;
00160   Expr *pE;
00161 
00162   dummy.z = zCol;
00163   dummy.n = strlen(zCol);
00164   dummy.dyn = 0;
00165   pE1a = sqliteExpr(TK_ID, 0, 0, &dummy);
00166   pE2a = sqliteExpr(TK_ID, 0, 0, &dummy);
00167   dummy.z = pTab1->zName;
00168   dummy.n = strlen(dummy.z);
00169   pE1b = sqliteExpr(TK_ID, 0, 0, &dummy);
00170   dummy.z = pTab2->zName;
00171   dummy.n = strlen(dummy.z);
00172   pE2b = sqliteExpr(TK_ID, 0, 0, &dummy);
00173   pE1c = sqliteExpr(TK_DOT, pE1b, pE1a, 0);
00174   pE2c = sqliteExpr(TK_DOT, pE2b, pE2a, 0);
00175   pE = sqliteExpr(TK_EQ, pE1c, pE2c, 0);
00176   ExprSetProperty(pE, EP_FromJoin);
00177   if( *ppExpr ){
00178     *ppExpr = sqliteExpr(TK_AND, *ppExpr, pE, 0);
00179   }else{
00180     *ppExpr = pE;
00181   }
00182 }
00183 
00184 /*
00185 ** Set the EP_FromJoin property on all terms of the given expression.
00186 **
00187 ** The EP_FromJoin property is used on terms of an expression to tell
00188 ** the LEFT OUTER JOIN processing logic that this term is part of the
00189 ** join restriction specified in the ON or USING clause and not a part
00190 ** of the more general WHERE clause.  These terms are moved over to the
00191 ** WHERE clause during join processing but we need to remember that they
00192 ** originated in the ON or USING clause.
00193 */
00194 static void setJoinExpr(Expr *p){
00195   while( p ){
00196     ExprSetProperty(p, EP_FromJoin);
00197     setJoinExpr(p->pLeft);
00198     p = p->pRight;
00199   } 
00200 }
00201 
00202 /*
00203 ** This routine processes the join information for a SELECT statement.
00204 ** ON and USING clauses are converted into extra terms of the WHERE clause.
00205 ** NATURAL joins also create extra WHERE clause terms.
00206 **
00207 ** This routine returns the number of errors encountered.
00208 */
00209 static int sqliteProcessJoin(Parse *pParse, Select *p){
00210   SrcList *pSrc;
00211   int i, j;
00212   pSrc = p->pSrc;
00213   for(i=0; i<pSrc->nSrc-1; i++){
00214     struct SrcList_item *pTerm = &pSrc->a[i];
00215     struct SrcList_item *pOther = &pSrc->a[i+1];
00216 
00217     if( pTerm->pTab==0 || pOther->pTab==0 ) continue;
00218 
00219     /* When the NATURAL keyword is present, add WHERE clause terms for
00220     ** every column that the two tables have in common.
00221     */
00222     if( pTerm->jointype & JT_NATURAL ){
00223       Table *pTab;
00224       if( pTerm->pOn || pTerm->pUsing ){
00225         sqliteErrorMsg(pParse, "a NATURAL join may not have "
00226            "an ON or USING clause", 0);
00227         return 1;
00228       }
00229       pTab = pTerm->pTab;
00230       for(j=0; j<pTab->nCol; j++){
00231         if( columnIndex(pOther->pTab, pTab->aCol[j].zName)>=0 ){
00232           addWhereTerm(pTab->aCol[j].zName, pTab, pOther->pTab, &p->pWhere);
00233         }
00234       }
00235     }
00236 
00237     /* Disallow both ON and USING clauses in the same join
00238     */
00239     if( pTerm->pOn && pTerm->pUsing ){
00240       sqliteErrorMsg(pParse, "cannot have both ON and USING "
00241         "clauses in the same join");
00242       return 1;
00243     }
00244 
00245     /* Add the ON clause to the end of the WHERE clause, connected by
00246     ** and AND operator.
00247     */
00248     if( pTerm->pOn ){
00249       setJoinExpr(pTerm->pOn);
00250       if( p->pWhere==0 ){
00251         p->pWhere = pTerm->pOn;
00252       }else{
00253         p->pWhere = sqliteExpr(TK_AND, p->pWhere, pTerm->pOn, 0);
00254       }
00255       pTerm->pOn = 0;
00256     }
00257 
00258     /* Create extra terms on the WHERE clause for each column named
00259     ** in the USING clause.  Example: If the two tables to be joined are 
00260     ** A and B and the USING clause names X, Y, and Z, then add this
00261     ** to the WHERE clause:    A.X=B.X AND A.Y=B.Y AND A.Z=B.Z
00262     ** Report an error if any column mentioned in the USING clause is
00263     ** not contained in both tables to be joined.
00264     */
00265     if( pTerm->pUsing ){
00266       IdList *pList;
00267       int j;
00268       assert( i<pSrc->nSrc-1 );
00269       pList = pTerm->pUsing;
00270       for(j=0; j<pList->nId; j++){
00271         if( columnIndex(pTerm->pTab, pList->a[j].zName)<0 ||
00272             columnIndex(pOther->pTab, pList->a[j].zName)<0 ){
00273           sqliteErrorMsg(pParse, "cannot join using column %s - column "
00274             "not present in both tables", pList->a[j].zName);
00275           return 1;
00276         }
00277         addWhereTerm(pList->a[j].zName, pTerm->pTab, pOther->pTab, &p->pWhere);
00278       }
00279     }
00280   }
00281   return 0;
00282 }
00283 
00284 /*
00285 ** Delete the given Select structure and all of its substructures.
00286 */
00287 void sqliteSelectDelete(Select *p){
00288   if( p==0 ) return;
00289   sqliteExprListDelete(p->pEList);
00290   sqliteSrcListDelete(p->pSrc);
00291   sqliteExprDelete(p->pWhere);
00292   sqliteExprListDelete(p->pGroupBy);
00293   sqliteExprDelete(p->pHaving);
00294   sqliteExprListDelete(p->pOrderBy);
00295   sqliteSelectDelete(p->pPrior);
00296   sqliteFree(p->zSelect);
00297   sqliteFree(p);
00298 }
00299 
00300 /*
00301 ** Delete the aggregate information from the parse structure.
00302 */
00303 static void sqliteAggregateInfoReset(Parse *pParse){
00304   sqliteFree(pParse->aAgg);
00305   pParse->aAgg = 0;
00306   pParse->nAgg = 0;
00307   pParse->useAgg = 0;
00308 }
00309 
00310 /*
00311 ** Insert code into "v" that will push the record on the top of the
00312 ** stack into the sorter.
00313 */
00314 static void pushOntoSorter(Parse *pParse, Vdbe *v, ExprList *pOrderBy){
00315   char *zSortOrder;
00316   int i;
00317   zSortOrder = sqliteMalloc( pOrderBy->nExpr + 1 );
00318   if( zSortOrder==0 ) return;
00319   for(i=0; i<pOrderBy->nExpr; i++){
00320     int order = pOrderBy->a[i].sortOrder;
00321     int type;
00322     int c;
00323     if( (order & SQLITE_SO_TYPEMASK)==SQLITE_SO_TEXT ){
00324       type = SQLITE_SO_TEXT;
00325     }else if( (order & SQLITE_SO_TYPEMASK)==SQLITE_SO_NUM ){
00326       type = SQLITE_SO_NUM;
00327     }else if( pParse->db->file_format>=4 ){
00328       type = sqliteExprType(pOrderBy->a[i].pExpr);
00329     }else{
00330       type = SQLITE_SO_NUM;
00331     }
00332     if( (order & SQLITE_SO_DIRMASK)==SQLITE_SO_ASC ){
00333       c = type==SQLITE_SO_TEXT ? 'A' : '+';
00334     }else{
00335       c = type==SQLITE_SO_TEXT ? 'D' : '-';
00336     }
00337     zSortOrder[i] = c;
00338     sqliteExprCode(pParse, pOrderBy->a[i].pExpr);
00339   }
00340   zSortOrder[pOrderBy->nExpr] = 0;
00341   sqliteVdbeOp3(v, OP_SortMakeKey, pOrderBy->nExpr, 0, zSortOrder, P3_DYNAMIC);
00342   sqliteVdbeAddOp(v, OP_SortPut, 0, 0);
00343 }
00344 
00345 /*
00346 ** This routine adds a P3 argument to the last VDBE opcode that was
00347 ** inserted. The P3 argument added is a string suitable for the 
00348 ** OP_MakeKey or OP_MakeIdxKey opcodes.  The string consists of
00349 ** characters 't' or 'n' depending on whether or not the various
00350 ** fields of the key to be generated should be treated as numeric
00351 ** or as text.  See the OP_MakeKey and OP_MakeIdxKey opcode
00352 ** documentation for additional information about the P3 string.
00353 ** See also the sqliteAddIdxKeyType() routine.
00354 */
00355 void sqliteAddKeyType(Vdbe *v, ExprList *pEList){
00356   int nColumn = pEList->nExpr;
00357   char *zType = sqliteMalloc( nColumn+1 );
00358   int i;
00359   if( zType==0 ) return;
00360   for(i=0; i<nColumn; i++){
00361     zType[i] = sqliteExprType(pEList->a[i].pExpr)==SQLITE_SO_NUM ? 'n' : 't';
00362   }
00363   zType[i] = 0;
00364   sqliteVdbeChangeP3(v, -1, zType, P3_DYNAMIC);
00365 }
00366 
00367 /*
00368 ** Add code to implement the OFFSET and LIMIT
00369 */
00370 static void codeLimiter(
00371   Vdbe *v,          /* Generate code into this VM */
00372   Select *p,        /* The SELECT statement being coded */
00373   int iContinue,    /* Jump here to skip the current record */
00374   int iBreak,       /* Jump here to end the loop */
00375   int nPop          /* Number of times to pop stack when jumping */
00376 ){
00377   if( p->iOffset>=0 ){
00378     int addr = sqliteVdbeCurrentAddr(v) + 2;
00379     if( nPop>0 ) addr++;
00380     sqliteVdbeAddOp(v, OP_MemIncr, p->iOffset, addr);
00381     if( nPop>0 ){
00382       sqliteVdbeAddOp(v, OP_Pop, nPop, 0);
00383     }
00384     sqliteVdbeAddOp(v, OP_Goto, 0, iContinue);
00385   }
00386   if( p->iLimit>=0 ){
00387     sqliteVdbeAddOp(v, OP_MemIncr, p->iLimit, iBreak);
00388   }
00389 }
00390 
00391 /*
00392 ** This routine generates the code for the inside of the inner loop
00393 ** of a SELECT.
00394 **
00395 ** If srcTab and nColumn are both zero, then the pEList expressions
00396 ** are evaluated in order to get the data for this row.  If nColumn>0
00397 ** then data is pulled from srcTab and pEList is used only to get the
00398 ** datatypes for each column.
00399 */
00400 static int selectInnerLoop(
00401   Parse *pParse,          /* The parser context */
00402   Select *p,              /* The complete select statement being coded */
00403   ExprList *pEList,       /* List of values being extracted */
00404   int srcTab,             /* Pull data from this table */
00405   int nColumn,            /* Number of columns in the source table */
00406   ExprList *pOrderBy,     /* If not NULL, sort results using this key */
00407   int distinct,           /* If >=0, make sure results are distinct */
00408   int eDest,              /* How to dispose of the results */
00409   int iParm,              /* An argument to the disposal method */
00410   int iContinue,          /* Jump here to continue with next row */
00411   int iBreak              /* Jump here to break out of the inner loop */
00412 ){
00413   Vdbe *v = pParse->pVdbe;
00414   int i;
00415   int hasDistinct;        /* True if the DISTINCT keyword is present */
00416 
00417   if( v==0 ) return 0;
00418   assert( pEList!=0 );
00419 
00420   /* If there was a LIMIT clause on the SELECT statement, then do the check
00421   ** to see if this row should be output.
00422   */
00423   hasDistinct = distinct>=0 && pEList && pEList->nExpr>0;
00424   if( pOrderBy==0 && !hasDistinct ){
00425     codeLimiter(v, p, iContinue, iBreak, 0);
00426   }
00427 
00428   /* Pull the requested columns.
00429   */
00430   if( nColumn>0 ){
00431     for(i=0; i<nColumn; i++){
00432       sqliteVdbeAddOp(v, OP_Column, srcTab, i);
00433     }
00434   }else{
00435     nColumn = pEList->nExpr;
00436     for(i=0; i<pEList->nExpr; i++){
00437       sqliteExprCode(pParse, pEList->a[i].pExpr);
00438     }
00439   }
00440 
00441   /* If the DISTINCT keyword was present on the SELECT statement
00442   ** and this row has been seen before, then do not make this row
00443   ** part of the result.
00444   */
00445   if( hasDistinct ){
00446 #if NULL_ALWAYS_DISTINCT
00447     sqliteVdbeAddOp(v, OP_IsNull, -pEList->nExpr, sqliteVdbeCurrentAddr(v)+7);
00448 #endif
00449     sqliteVdbeAddOp(v, OP_MakeKey, pEList->nExpr, 1);
00450     if( pParse->db->file_format>=4 ) sqliteAddKeyType(v, pEList);
00451     sqliteVdbeAddOp(v, OP_Distinct, distinct, sqliteVdbeCurrentAddr(v)+3);
00452     sqliteVdbeAddOp(v, OP_Pop, pEList->nExpr+1, 0);
00453     sqliteVdbeAddOp(v, OP_Goto, 0, iContinue);
00454     sqliteVdbeAddOp(v, OP_String, 0, 0);
00455     sqliteVdbeAddOp(v, OP_PutStrKey, distinct, 0);
00456     if( pOrderBy==0 ){
00457       codeLimiter(v, p, iContinue, iBreak, nColumn);
00458     }
00459   }
00460 
00461   switch( eDest ){
00462     /* In this mode, write each query result to the key of the temporary
00463     ** table iParm.
00464     */
00465     case SRT_Union: {
00466       sqliteVdbeAddOp(v, OP_MakeRecord, nColumn, NULL_ALWAYS_DISTINCT);
00467       sqliteVdbeAddOp(v, OP_String, 0, 0);
00468       sqliteVdbeAddOp(v, OP_PutStrKey, iParm, 0);
00469       break;
00470     }
00471 
00472     /* Store the result as data using a unique key.
00473     */
00474     case SRT_Table:
00475     case SRT_TempTable: {
00476       sqliteVdbeAddOp(v, OP_MakeRecord, nColumn, 0);
00477       if( pOrderBy ){
00478         pushOntoSorter(pParse, v, pOrderBy);
00479       }else{
00480         sqliteVdbeAddOp(v, OP_NewRecno, iParm, 0);
00481         sqliteVdbeAddOp(v, OP_Pull, 1, 0);
00482         sqliteVdbeAddOp(v, OP_PutIntKey, iParm, 0);
00483       }
00484       break;
00485     }
00486 
00487     /* Construct a record from the query result, but instead of
00488     ** saving that record, use it as a key to delete elements from
00489     ** the temporary table iParm.
00490     */
00491     case SRT_Except: {
00492       int addr;
00493       addr = sqliteVdbeAddOp(v, OP_MakeRecord, nColumn, NULL_ALWAYS_DISTINCT);
00494       sqliteVdbeAddOp(v, OP_NotFound, iParm, addr+3);
00495       sqliteVdbeAddOp(v, OP_Delete, iParm, 0);
00496       break;
00497     }
00498 
00499     /* If we are creating a set for an "expr IN (SELECT ...)" construct,
00500     ** then there should be a single item on the stack.  Write this
00501     ** item into the set table with bogus data.
00502     */
00503     case SRT_Set: {
00504       int addr1 = sqliteVdbeCurrentAddr(v);
00505       int addr2;
00506       assert( nColumn==1 );
00507       sqliteVdbeAddOp(v, OP_NotNull, -1, addr1+3);
00508       sqliteVdbeAddOp(v, OP_Pop, 1, 0);
00509       addr2 = sqliteVdbeAddOp(v, OP_Goto, 0, 0);
00510       if( pOrderBy ){
00511         pushOntoSorter(pParse, v, pOrderBy);
00512       }else{
00513         sqliteVdbeAddOp(v, OP_String, 0, 0);
00514         sqliteVdbeAddOp(v, OP_PutStrKey, iParm, 0);
00515       }
00516       sqliteVdbeChangeP2(v, addr2, sqliteVdbeCurrentAddr(v));
00517       break;
00518     }
00519 
00520     /* If this is a scalar select that is part of an expression, then
00521     ** store the results in the appropriate memory cell and break out
00522     ** of the scan loop.
00523     */
00524     case SRT_Mem: {
00525       assert( nColumn==1 );
00526       if( pOrderBy ){
00527         pushOntoSorter(pParse, v, pOrderBy);
00528       }else{
00529         sqliteVdbeAddOp(v, OP_MemStore, iParm, 1);
00530         sqliteVdbeAddOp(v, OP_Goto, 0, iBreak);
00531       }
00532       break;
00533     }
00534 
00535     /* Send the data to the callback function.
00536     */
00537     case SRT_Callback:
00538     case SRT_Sorter: {
00539       if( pOrderBy ){
00540         sqliteVdbeAddOp(v, OP_SortMakeRec, nColumn, 0);
00541         pushOntoSorter(pParse, v, pOrderBy);
00542       }else{
00543         assert( eDest==SRT_Callback );
00544         sqliteVdbeAddOp(v, OP_Callback, nColumn, 0);
00545       }
00546       break;
00547     }
00548 
00549     /* Invoke a subroutine to handle the results.  The subroutine itself
00550     ** is responsible for popping the results off of the stack.
00551     */
00552     case SRT_Subroutine: {
00553       if( pOrderBy ){
00554         sqliteVdbeAddOp(v, OP_MakeRecord, nColumn, 0);
00555         pushOntoSorter(pParse, v, pOrderBy);
00556       }else{
00557         sqliteVdbeAddOp(v, OP_Gosub, 0, iParm);
00558       }
00559       break;
00560     }
00561 
00562     /* Discard the results.  This is used for SELECT statements inside
00563     ** the body of a TRIGGER.  The purpose of such selects is to call
00564     ** user-defined functions that have side effects.  We do not care
00565     ** about the actual results of the select.
00566     */
00567     default: {
00568       assert( eDest==SRT_Discard );
00569       sqliteVdbeAddOp(v, OP_Pop, nColumn, 0);
00570       break;
00571     }
00572   }
00573   return 0;
00574 }
00575 
00576 /*
00577 ** If the inner loop was generated using a non-null pOrderBy argument,
00578 ** then the results were placed in a sorter.  After the loop is terminated
00579 ** we need to run the sorter and output the results.  The following
00580 ** routine generates the code needed to do that.
00581 */
00582 static void generateSortTail(
00583   Select *p,       /* The SELECT statement */
00584   Vdbe *v,         /* Generate code into this VDBE */
00585   int nColumn,     /* Number of columns of data */
00586   int eDest,       /* Write the sorted results here */
00587   int iParm        /* Optional parameter associated with eDest */
00588 ){
00589   int end1 = sqliteVdbeMakeLabel(v);
00590   int end2 = sqliteVdbeMakeLabel(v);
00591   int addr;
00592   if( eDest==SRT_Sorter ) return;
00593   sqliteVdbeAddOp(v, OP_Sort, 0, 0);
00594   addr = sqliteVdbeAddOp(v, OP_SortNext, 0, end1);
00595   codeLimiter(v, p, addr, end2, 1);
00596   switch( eDest ){
00597     case SRT_Callback: {
00598       sqliteVdbeAddOp(v, OP_SortCallback, nColumn, 0);
00599       break;
00600     }
00601     case SRT_Table:
00602     case SRT_TempTable: {
00603       sqliteVdbeAddOp(v, OP_NewRecno, iParm, 0);
00604       sqliteVdbeAddOp(v, OP_Pull, 1, 0);
00605       sqliteVdbeAddOp(v, OP_PutIntKey, iParm, 0);
00606       break;
00607     }
00608     case SRT_Set: {
00609       assert( nColumn==1 );
00610       sqliteVdbeAddOp(v, OP_NotNull, -1, sqliteVdbeCurrentAddr(v)+3);
00611       sqliteVdbeAddOp(v, OP_Pop, 1, 0);
00612       sqliteVdbeAddOp(v, OP_Goto, 0, sqliteVdbeCurrentAddr(v)+3);
00613       sqliteVdbeAddOp(v, OP_String, 0, 0);
00614       sqliteVdbeAddOp(v, OP_PutStrKey, iParm, 0);
00615       break;
00616     }
00617     case SRT_Mem: {
00618       assert( nColumn==1 );
00619       sqliteVdbeAddOp(v, OP_MemStore, iParm, 1);
00620       sqliteVdbeAddOp(v, OP_Goto, 0, end1);
00621       break;
00622     }
00623     case SRT_Subroutine: {
00624       int i;
00625       for(i=0; i<nColumn; i++){
00626         sqliteVdbeAddOp(v, OP_Column, -1-i, i);
00627       }
00628       sqliteVdbeAddOp(v, OP_Gosub, 0, iParm);
00629       sqliteVdbeAddOp(v, OP_Pop, 1, 0);
00630       break;
00631     }
00632     default: {
00633       /* Do nothing */
00634       break;
00635     }
00636   }
00637   sqliteVdbeAddOp(v, OP_Goto, 0, addr);
00638   sqliteVdbeResolveLabel(v, end2);
00639   sqliteVdbeAddOp(v, OP_Pop, 1, 0);
00640   sqliteVdbeResolveLabel(v, end1);
00641   sqliteVdbeAddOp(v, OP_SortReset, 0, 0);
00642 }
00643 
00644 /*
00645 ** Generate code that will tell the VDBE the datatypes of
00646 ** columns in the result set.
00647 **
00648 ** This routine only generates code if the "PRAGMA show_datatypes=on"
00649 ** has been executed.  The datatypes are reported out in the azCol
00650 ** parameter to the callback function.  The first N azCol[] entries
00651 ** are the names of the columns, and the second N entries are the
00652 ** datatypes for the columns.
00653 **
00654 ** The "datatype" for a result that is a column of a type is the
00655 ** datatype definition extracted from the CREATE TABLE statement.
00656 ** The datatype for an expression is either TEXT or NUMERIC.  The
00657 ** datatype for a ROWID field is INTEGER.
00658 */
00659 static void generateColumnTypes(
00660   Parse *pParse,      /* Parser context */
00661   SrcList *pTabList,  /* List of tables */
00662   ExprList *pEList    /* Expressions defining the result set */
00663 ){
00664   Vdbe *v = pParse->pVdbe;
00665   int i, j;
00666   for(i=0; i<pEList->nExpr; i++){
00667     Expr *p = pEList->a[i].pExpr;
00668     char *zType = 0;
00669     if( p==0 ) continue;
00670     if( p->op==TK_COLUMN && pTabList ){
00671       Table *pTab;
00672       int iCol = p->iColumn;
00673       for(j=0; j<pTabList->nSrc && pTabList->a[j].iCursor!=p->iTable; j++){}
00674       assert( j<pTabList->nSrc );
00675       pTab = pTabList->a[j].pTab;
00676       if( iCol<0 ) iCol = pTab->iPKey;
00677       assert( iCol==-1 || (iCol>=0 && iCol<pTab->nCol) );
00678       if( iCol<0 ){
00679         zType = "INTEGER";
00680       }else{
00681         zType = pTab->aCol[iCol].zType;
00682       }
00683     }else{
00684       if( sqliteExprType(p)==SQLITE_SO_TEXT ){
00685         zType = "TEXT";
00686       }else{
00687         zType = "NUMERIC";
00688       }
00689     }
00690     sqliteVdbeOp3(v, OP_ColumnName, i + pEList->nExpr, 0, zType, 0);
00691   }
00692 }
00693 
00694 /*
00695 ** Generate code that will tell the VDBE the names of columns
00696 ** in the result set.  This information is used to provide the
00697 ** azCol[] values in the callback.
00698 */
00699 static void generateColumnNames(
00700   Parse *pParse,      /* Parser context */
00701   SrcList *pTabList,  /* List of tables */
00702   ExprList *pEList    /* Expressions defining the result set */
00703 ){
00704   Vdbe *v = pParse->pVdbe;
00705   int i, j;
00706   sqlite *db = pParse->db;
00707   int fullNames, shortNames;
00708 
00709   assert( v!=0 );
00710   if( pParse->colNamesSet || v==0 || sqlite_malloc_failed ) return;
00711   pParse->colNamesSet = 1;
00712   fullNames = (db->flags & SQLITE_FullColNames)!=0;
00713   shortNames = (db->flags & SQLITE_ShortColNames)!=0;
00714   for(i=0; i<pEList->nExpr; i++){
00715     Expr *p;
00716     int p2 = i==pEList->nExpr-1;
00717     p = pEList->a[i].pExpr;
00718     if( p==0 ) continue;
00719     if( pEList->a[i].zName ){
00720       char *zName = pEList->a[i].zName;
00721       sqliteVdbeOp3(v, OP_ColumnName, i, p2, zName, 0);
00722       continue;
00723     }
00724     if( p->op==TK_COLUMN && pTabList ){
00725       Table *pTab;
00726       char *zCol;
00727       int iCol = p->iColumn;
00728       for(j=0; j<pTabList->nSrc && pTabList->a[j].iCursor!=p->iTable; j++){}
00729       assert( j<pTabList->nSrc );
00730       pTab = pTabList->a[j].pTab;
00731       if( iCol<0 ) iCol = pTab->iPKey;
00732       assert( iCol==-1 || (iCol>=0 && iCol<pTab->nCol) );
00733       if( iCol<0 ){
00734         zCol = "_ROWID_";
00735       }else{
00736         zCol = pTab->aCol[iCol].zName;
00737       }
00738       if( !shortNames && !fullNames && p->span.z && p->span.z[0] ){
00739         int addr = sqliteVdbeOp3(v,OP_ColumnName, i, p2, p->span.z, p->span.n);
00740         sqliteVdbeCompressSpace(v, addr);
00741       }else if( fullNames || (!shortNames && pTabList->nSrc>1) ){
00742         char *zName = 0;
00743         char *zTab;
00744  
00745         zTab = pTabList->a[j].zAlias;
00746         if( fullNames || zTab==0 ) zTab = pTab->zName;
00747         sqliteSetString(&zName, zTab, ".", zCol, 0);
00748         sqliteVdbeOp3(v, OP_ColumnName, i, p2, zName, P3_DYNAMIC);
00749       }else{
00750         sqliteVdbeOp3(v, OP_ColumnName, i, p2, zCol, 0);
00751       }
00752     }else if( p->span.z && p->span.z[0] ){
00753       int addr = sqliteVdbeOp3(v,OP_ColumnName, i, p2, p->span.z, p->span.n);
00754       sqliteVdbeCompressSpace(v, addr);
00755     }else{
00756       char zName[30];
00757       assert( p->op!=TK_COLUMN || pTabList==0 );
00758       sprintf(zName, "column%d", i+1);
00759       sqliteVdbeOp3(v, OP_ColumnName, i, p2, zName, 0);
00760     }
00761   }
00762 }
00763 
00764 /*
00765 ** Name of the connection operator, used for error messages.
00766 */
00767 static const char *selectOpName(int id){
00768   char *z;
00769   switch( id ){
00770     case TK_ALL:       z = "UNION ALL";   break;
00771     case TK_INTERSECT: z = "INTERSECT";   break;
00772     case TK_EXCEPT:    z = "EXCEPT";      break;
00773     default:           z = "UNION";       break;
00774   }
00775   return z;
00776 }
00777 
00778 /*
00779 ** Forward declaration
00780 */
00781 static int fillInColumnList(Parse*, Select*);
00782 
00783 /*
00784 ** Given a SELECT statement, generate a Table structure that describes
00785 ** the result set of that SELECT.
00786 */
00787 Table *sqliteResultSetOfSelect(Parse *pParse, char *zTabName, Select *pSelect){
00788   Table *pTab;
00789   int i, j;
00790   ExprList *pEList;
00791   Column *aCol;
00792 
00793   if( fillInColumnList(pParse, pSelect) ){
00794     return 0;
00795   }
00796   pTab = sqliteMalloc( sizeof(Table) );
00797   if( pTab==0 ){
00798     return 0;
00799   }
00800   pTab->zName = zTabName ? sqliteStrDup(zTabName) : 0;
00801   pEList = pSelect->pEList;
00802   pTab->nCol = pEList->nExpr;
00803   assert( pTab->nCol>0 );
00804   pTab->aCol = aCol = sqliteMalloc( sizeof(pTab->aCol[0])*pTab->nCol );
00805   for(i=0; i<pTab->nCol; i++){
00806     Expr *p, *pR;
00807     if( pEList->a[i].zName ){
00808       aCol[i].zName = sqliteStrDup(pEList->a[i].zName);
00809     }else if( (p=pEList->a[i].pExpr)->op==TK_DOT 
00810                && (pR=p->pRight)!=0 && pR->token.z && pR->token.z[0] ){
00811       int cnt;
00812       sqliteSetNString(&aCol[i].zName, pR->token.z, pR->token.n, 0);
00813       for(j=cnt=0; j<i; j++){
00814         if( sqliteStrICmp(aCol[j].zName, aCol[i].zName)==0 ){
00815           int n;
00816           char zBuf[30];
00817           sprintf(zBuf,"_%d",++cnt);
00818           n = strlen(zBuf);
00819           sqliteSetNString(&aCol[i].zName, pR->token.z, pR->token.n, zBuf, n,0);
00820           j = -1;
00821         }
00822       }
00823     }else if( p->span.z && p->span.z[0] ){
00824       sqliteSetNString(&pTab->aCol[i].zName, p->span.z, p->span.n, 0);
00825     }else{
00826       char zBuf[30];
00827       sprintf(zBuf, "column%d", i+1);
00828       aCol[i].zName = sqliteStrDup(zBuf);
00829     }
00830     sqliteDequote(aCol[i].zName);
00831   }
00832   pTab->iPKey = -1;
00833   return pTab;
00834 }
00835 
00836 /*
00837 ** For the given SELECT statement, do three things.
00838 **
00839 **    (1)  Fill in the pTabList->a[].pTab fields in the SrcList that 
00840 **         defines the set of tables that should be scanned.  For views,
00841 **         fill pTabList->a[].pSelect with a copy of the SELECT statement
00842 **         that implements the view.  A copy is made of the view's SELECT
00843 **         statement so that we can freely modify or delete that statement
00844 **         without worrying about messing up the presistent representation
00845 **         of the view.
00846 **
00847 **    (2)  Add terms to the WHERE clause to accomodate the NATURAL keyword
00848 **         on joins and the ON and USING clause of joins.
00849 **
00850 **    (3)  Scan the list of columns in the result set (pEList) looking
00851 **         for instances of the "*" operator or the TABLE.* operator.
00852 **         If found, expand each "*" to be every column in every table
00853 **         and TABLE.* to be every column in TABLE.
00854 **
00855 ** Return 0 on success.  If there are problems, leave an error message
00856 ** in pParse and return non-zero.
00857 */
00858 static int fillInColumnList(Parse *pParse, Select *p){
00859   int i, j, k, rc;
00860   SrcList *pTabList;
00861   ExprList *pEList;
00862   Table *pTab;
00863 
00864   if( p==0 || p->pSrc==0 ) return 1;
00865   pTabList = p->pSrc;
00866   pEList = p->pEList;
00867 
00868   /* Look up every table in the table list.
00869   */
00870   for(i=0; i<pTabList->nSrc; i++){
00871     if( pTabList->a[i].pTab ){
00872       /* This routine has run before!  No need to continue */
00873       return 0;
00874     }
00875     if( pTabList->a[i].zName==0 ){
00876       /* A sub-query in the FROM clause of a SELECT */
00877       assert( pTabList->a[i].pSelect!=0 );
00878       if( pTabList->a[i].zAlias==0 ){
00879         char zFakeName[60];
00880         sprintf(zFakeName, "sqlite_subquery_%p_",
00881            (void*)pTabList->a[i].pSelect);
00882         sqliteSetString(&pTabList->a[i].zAlias, zFakeName, 0);
00883       }
00884       pTabList->a[i].pTab = pTab = 
00885         sqliteResultSetOfSelect(pParse, pTabList->a[i].zAlias,
00886                                         pTabList->a[i].pSelect);
00887       if( pTab==0 ){
00888         return 1;
00889       }
00890       /* The isTransient flag indicates that the Table structure has been
00891       ** dynamically allocated and may be freed at any time.  In other words,
00892       ** pTab is not pointing to a persistent table structure that defines
00893       ** part of the schema. */
00894       pTab->isTransient = 1;
00895     }else{
00896       /* An ordinary table or view name in the FROM clause */
00897       pTabList->a[i].pTab = pTab = 
00898         sqliteLocateTable(pParse,pTabList->a[i].zName,pTabList->a[i].zDatabase);
00899       if( pTab==0 ){
00900         return 1;
00901       }
00902       if( pTab->pSelect ){
00903         /* We reach here if the named table is a really a view */
00904         if( sqliteViewGetColumnNames(pParse, pTab) ){
00905           return 1;
00906         }
00907         /* If pTabList->a[i].pSelect!=0 it means we are dealing with a
00908         ** view within a view.  The SELECT structure has already been
00909         ** copied by the outer view so we can skip the copy step here
00910         ** in the inner view.
00911         */
00912         if( pTabList->a[i].pSelect==0 ){
00913           pTabList->a[i].pSelect = sqliteSelectDup(pTab->pSelect);
00914         }
00915       }
00916     }
00917   }
00918 
00919   /* Process NATURAL keywords, and ON and USING clauses of joins.
00920   */
00921   if( sqliteProcessJoin(pParse, p) ) return 1;
00922 
00923   /* For every "*" that occurs in the column list, insert the names of
00924   ** all columns in all tables.  And for every TABLE.* insert the names
00925   ** of all columns in TABLE.  The parser inserted a special expression
00926   ** with the TK_ALL operator for each "*" that it found in the column list.
00927   ** The following code just has to locate the TK_ALL expressions and expand
00928   ** each one to the list of all columns in all tables.
00929   **
00930   ** The first loop just checks to see if there are any "*" operators
00931   ** that need expanding.
00932   */
00933   for(k=0; k<pEList->nExpr; k++){
00934     Expr *pE = pEList->a[k].pExpr;
00935     if( pE->op==TK_ALL ) break;
00936     if( pE->op==TK_DOT && pE->pRight && pE->pRight->op==TK_ALL
00937          && pE->pLeft && pE->pLeft->op==TK_ID ) break;
00938   }
00939   rc = 0;
00940   if( k<pEList->nExpr ){
00941     /*
00942     ** If we get here it means the result set contains one or more "*"
00943     ** operators that need to be expanded.  Loop through each expression
00944     ** in the result set and expand them one by one.
00945     */
00946     struct ExprList_item *a = pEList->a;
00947     ExprList *pNew = 0;
00948     for(k=0; k<pEList->nExpr; k++){
00949       Expr *pE = a[k].pExpr;
00950       if( pE->op!=TK_ALL &&
00951            (pE->op!=TK_DOT || pE->pRight==0 || pE->pRight->op!=TK_ALL) ){
00952         /* This particular expression does not need to be expanded.
00953         */
00954         pNew = sqliteExprListAppend(pNew, a[k].pExpr, 0);
00955         pNew->a[pNew->nExpr-1].zName = a[k].zName;
00956         a[k].pExpr = 0;
00957         a[k].zName = 0;
00958       }else{
00959         /* This expression is a "*" or a "TABLE.*" and needs to be
00960         ** expanded. */
00961         int tableSeen = 0;      /* Set to 1 when TABLE matches */
00962         char *zTName;           /* text of name of TABLE */
00963         if( pE->op==TK_DOT && pE->pLeft ){
00964           zTName = sqliteTableNameFromToken(&pE->pLeft->token);
00965         }else{
00966           zTName = 0;
00967         }
00968         for(i=0; i<pTabList->nSrc; i++){
00969           Table *pTab = pTabList->a[i].pTab;
00970           char *zTabName = pTabList->a[i].zAlias;
00971           if( zTabName==0 || zTabName[0]==0 ){ 
00972             zTabName = pTab->zName;
00973           }
00974           if( zTName && (zTabName==0 || zTabName[0]==0 || 
00975                  sqliteStrICmp(zTName, zTabName)!=0) ){
00976             continue;
00977           }
00978           tableSeen = 1;
00979           for(j=0; j<pTab->nCol; j++){
00980             Expr *pExpr, *pLeft, *pRight;
00981             char *zName = pTab->aCol[j].zName;
00982 
00983             if( i>0 && (pTabList->a[i-1].jointype & JT_NATURAL)!=0 &&
00984                 columnIndex(pTabList->a[i-1].pTab, zName)>=0 ){
00985               /* In a NATURAL join, omit the join columns from the 
00986               ** table on the right */
00987               continue;
00988             }
00989             if( i>0 && sqliteIdListIndex(pTabList->a[i-1].pUsing, zName)>=0 ){
00990               /* In a join with a USING clause, omit columns in the
00991               ** using clause from the table on the right. */
00992               continue;
00993             }
00994             pRight = sqliteExpr(TK_ID, 0, 0, 0);
00995             if( pRight==0 ) break;
00996             pRight->token.z = zName;
00997             pRight->token.n = strlen(zName);
00998             pRight->token.dyn = 0;
00999             if( zTabName && pTabList->nSrc>1 ){
01000               pLeft = sqliteExpr(TK_ID, 0, 0, 0);
01001               pExpr = sqliteExpr(TK_DOT, pLeft, pRight, 0);
01002               if( pExpr==0 ) break;
01003               pLeft->token.z = zTabName;
01004               pLeft->token.n = strlen(zTabName);
01005               pLeft->token.dyn = 0;
01006               sqliteSetString((char**)&pExpr->span.z, zTabName, ".", zName, 0);
01007               pExpr->span.n = strlen(pExpr->span.z);
01008               pExpr->span.dyn = 1;
01009               pExpr->token.z = 0;
01010               pExpr->token.n = 0;
01011               pExpr->token.dyn = 0;
01012             }else{
01013               pExpr = pRight;
01014               pExpr->span = pExpr->token;
01015             }
01016             pNew = sqliteExprListAppend(pNew, pExpr, 0);
01017           }
01018         }
01019         if( !tableSeen ){
01020           if( zTName ){
01021             sqliteErrorMsg(pParse, "no such table: %s", zTName);
01022           }else{
01023             sqliteErrorMsg(pParse, "no tables specified");
01024           }
01025           rc = 1;
01026         }
01027         sqliteFree(zTName);
01028       }
01029     }
01030     sqliteExprListDelete(pEList);
01031     p->pEList = pNew;
01032   }
01033   return rc;
01034 }
01035 
01036 /*
01037 ** This routine recursively unlinks the Select.pSrc.a[].pTab pointers
01038 ** in a select structure.  It just sets the pointers to NULL.  This
01039 ** routine is recursive in the sense that if the Select.pSrc.a[].pSelect
01040 ** pointer is not NULL, this routine is called recursively on that pointer.
01041 **
01042 ** This routine is called on the Select structure that defines a
01043 ** VIEW in order to undo any bindings to tables.  This is necessary
01044 ** because those tables might be DROPed by a subsequent SQL command.
01045 ** If the bindings are not removed, then the Select.pSrc->a[].pTab field
01046 ** will be left pointing to a deallocated Table structure after the
01047 ** DROP and a coredump will occur the next time the VIEW is used.
01048 */
01049 void sqliteSelectUnbind(Select *p){
01050   int i;
01051   SrcList *pSrc = p->pSrc;
01052   Table *pTab;
01053   if( p==0 ) return;
01054   for(i=0; i<pSrc->nSrc; i++){
01055     if( (pTab = pSrc->a[i].pTab)!=0 ){
01056       if( pTab->isTransient ){
01057         sqliteDeleteTable(0, pTab);
01058       }
01059       pSrc->a[i].pTab = 0;
01060       if( pSrc->a[i].pSelect ){
01061         sqliteSelectUnbind(pSrc->a[i].pSelect);
01062       }
01063     }
01064   }
01065 }
01066 
01067 /*
01068 ** This routine associates entries in an ORDER BY expression list with
01069 ** columns in a result.  For each ORDER BY expression, the opcode of
01070 ** the top-level node is changed to TK_COLUMN and the iColumn value of
01071 ** the top-level node is filled in with column number and the iTable
01072 ** value of the top-level node is filled with iTable parameter.
01073 **
01074 ** If there are prior SELECT clauses, they are processed first.  A match
01075 ** in an earlier SELECT takes precedence over a later SELECT.
01076 **
01077 ** Any entry that does not match is flagged as an error.  The number
01078 ** of errors is returned.
01079 **
01080 ** This routine does NOT correctly initialize the Expr.dataType  field
01081 ** of the ORDER BY expressions.  The multiSelectSortOrder() routine
01082 ** must be called to do that after the individual select statements
01083 ** have all been analyzed.  This routine is unable to compute Expr.dataType
01084 ** because it must be called before the individual select statements
01085 ** have been analyzed.
01086 */
01087 static int matchOrderbyToColumn(
01088   Parse *pParse,          /* A place to leave error messages */
01089   Select *pSelect,        /* Match to result columns of this SELECT */
01090   ExprList *pOrderBy,     /* The ORDER BY values to match against columns */
01091   int iTable,             /* Insert this value in iTable */
01092   int mustComplete        /* If TRUE all ORDER BYs must match */
01093 ){
01094   int nErr = 0;
01095   int i, j;
01096   ExprList *pEList;
01097 
01098   if( pSelect==0 || pOrderBy==0 ) return 1;
01099   if( mustComplete ){
01100     for(i=0; i<pOrderBy->nExpr; i++){ pOrderBy->a[i].done = 0; }
01101   }
01102   if( fillInColumnList(pParse, pSelect) ){
01103     return 1;
01104   }
01105   if( pSelect->pPrior ){
01106     if( matchOrderbyToColumn(pParse, pSelect->pPrior, pOrderBy, iTable, 0) ){
01107       return 1;
01108     }
01109   }
01110   pEList = pSelect->pEList;
01111   for(i=0; i<pOrderBy->nExpr; i++){
01112     Expr *pE = pOrderBy->a[i].pExpr;
01113     int iCol = -1;
01114     if( pOrderBy->a[i].done ) continue;
01115     if( sqliteExprIsInteger(pE, &iCol) ){
01116       if( iCol<=0 || iCol>pEList->nExpr ){
01117         sqliteErrorMsg(pParse,
01118           "ORDER BY position %d should be between 1 and %d",
01119           iCol, pEList->nExpr);
01120         nErr++;
01121         break;
01122       }
01123       if( !mustComplete ) continue;
01124       iCol--;
01125     }
01126     for(j=0; iCol<0 && j<pEList->nExpr; j++){
01127       if( pEList->a[j].zName && (pE->op==TK_ID || pE->op==TK_STRING) ){
01128         char *zName, *zLabel;
01129         zName = pEList->a[j].zName;
01130         assert( pE->token.z );
01131         zLabel = sqliteStrNDup(pE->token.z, pE->token.n);
01132         sqliteDequote(zLabel);
01133         if( sqliteStrICmp(zName, zLabel)==0 ){ 
01134           iCol = j;
01135         }
01136         sqliteFree(zLabel);
01137       }
01138       if( iCol<0 && sqliteExprCompare(pE, pEList->a[j].pExpr) ){
01139         iCol = j;
01140       }
01141     }
01142     if( iCol>=0 ){
01143       pE->op = TK_COLUMN;
01144       pE->iColumn = iCol;
01145       pE->iTable = iTable;
01146       pOrderBy->a[i].done = 1;
01147     }
01148     if( iCol<0 && mustComplete ){
01149       sqliteErrorMsg(pParse,
01150         "ORDER BY term number %d does not match any result column", i+1);
01151       nErr++;
01152       break;
01153     }
01154   }
01155   return nErr;  
01156 }
01157 
01158 /*
01159 ** Get a VDBE for the given parser context.  Create a new one if necessary.
01160 ** If an error occurs, return NULL and leave a message in pParse.
01161 */
01162 Vdbe *sqliteGetVdbe(Parse *pParse){
01163   Vdbe *v = pParse->pVdbe;
01164   if( v==0 ){
01165     v = pParse->pVdbe = sqliteVdbeCreate(pParse->db);
01166   }
01167   return v;
01168 }
01169 
01170 /*
01171 ** This routine sets the Expr.dataType field on all elements of
01172 ** the pOrderBy expression list.  The pOrderBy list will have been
01173 ** set up by matchOrderbyToColumn().  Hence each expression has
01174 ** a TK_COLUMN as its root node.  The Expr.iColumn refers to a 
01175 ** column in the result set.   The datatype is set to SQLITE_SO_TEXT
01176 ** if the corresponding column in p and every SELECT to the left of
01177 ** p has a datatype of SQLITE_SO_TEXT.  If the cooressponding column
01178 ** in p or any of the left SELECTs is SQLITE_SO_NUM, then the datatype
01179 ** of the order-by expression is set to SQLITE_SO_NUM.
01180 **
01181 ** Examples:
01182 **
01183 **     CREATE TABLE one(a INTEGER, b TEXT);
01184 **     CREATE TABLE two(c VARCHAR(5), d FLOAT);
01185 **
01186 **     SELECT b, b FROM one UNION SELECT d, c FROM two ORDER BY 1, 2;
01187 **
01188 ** The primary sort key will use SQLITE_SO_NUM because the "d" in
01189 ** the second SELECT is numeric.  The 1st column of the first SELECT
01190 ** is text but that does not matter because a numeric always overrides
01191 ** a text.
01192 **
01193 ** The secondary key will use the SQLITE_SO_TEXT sort order because
01194 ** both the (second) "b" in the first SELECT and the "c" in the second
01195 ** SELECT have a datatype of text.
01196 */ 
01197 static void multiSelectSortOrder(Select *p, ExprList *pOrderBy){
01198   int i;
01199   ExprList *pEList;
01200   if( pOrderBy==0 ) return;
01201   if( p==0 ){
01202     for(i=0; i<pOrderBy->nExpr; i++){
01203       pOrderBy->a[i].pExpr->dataType = SQLITE_SO_TEXT;
01204     }
01205     return;
01206   }
01207   multiSelectSortOrder(p->pPrior, pOrderBy);
01208   pEList = p->pEList;
01209   for(i=0; i<pOrderBy->nExpr; i++){
01210     Expr *pE = pOrderBy->a[i].pExpr;
01211     if( pE->dataType==SQLITE_SO_NUM ) continue;
01212     assert( pE->iColumn>=0 );
01213     if( pEList->nExpr>pE->iColumn ){
01214       pE->dataType = sqliteExprType(pEList->a[pE->iColumn].pExpr);
01215     }
01216   }
01217 }
01218 
01219 /*
01220 ** Compute the iLimit and iOffset fields of the SELECT based on the
01221 ** nLimit and nOffset fields.  nLimit and nOffset hold the integers
01222 ** that appear in the original SQL statement after the LIMIT and OFFSET
01223 ** keywords.  Or that hold -1 and 0 if those keywords are omitted.
01224 ** iLimit and iOffset are the integer memory register numbers for
01225 ** counters used to compute the limit and offset.  If there is no
01226 ** limit and/or offset, then iLimit and iOffset are negative.
01227 **
01228 ** This routine changes the values if iLimit and iOffset only if
01229 ** a limit or offset is defined by nLimit and nOffset.  iLimit and
01230 ** iOffset should have been preset to appropriate default values
01231 ** (usually but not always -1) prior to calling this routine.
01232 ** Only if nLimit>=0 or nOffset>0 do the limit registers get
01233 ** redefined.  The UNION ALL operator uses this property to force
01234 ** the reuse of the same limit and offset registers across multiple
01235 ** SELECT statements.
01236 */
01237 static void computeLimitRegisters(Parse *pParse, Select *p){
01238   /* 
01239   ** If the comparison is p->nLimit>0 then "LIMIT 0" shows
01240   ** all rows.  It is the same as no limit. If the comparision is
01241   ** p->nLimit>=0 then "LIMIT 0" show no rows at all.
01242   ** "LIMIT -1" always shows all rows.  There is some
01243   ** contraversy about what the correct behavior should be.
01244   ** The current implementation interprets "LIMIT 0" to mean
01245   ** no rows.
01246   */
01247   if( p->nLimit>=0 ){
01248     int iMem = pParse->nMem++;
01249     Vdbe *v = sqliteGetVdbe(pParse);
01250     if( v==0 ) return;
01251     sqliteVdbeAddOp(v, OP_Integer, -p->nLimit, 0);
01252     sqliteVdbeAddOp(v, OP_MemStore, iMem, 1);
01253     p->iLimit = iMem;
01254   }
01255   if( p->nOffset>0 ){
01256     int iMem = pParse->nMem++;
01257     Vdbe *v = sqliteGetVdbe(pParse);
01258     if( v==0 ) return;
01259     sqliteVdbeAddOp(v, OP_Integer, -p->nOffset, 0);
01260     sqliteVdbeAddOp(v, OP_MemStore, iMem, 1);
01261     p->iOffset = iMem;
01262   }
01263 }
01264 
01265 /*
01266 ** This routine is called to process a query that is really the union
01267 ** or intersection of two or more separate queries.
01268 **
01269 ** "p" points to the right-most of the two queries.  the query on the
01270 ** left is p->pPrior.  The left query could also be a compound query
01271 ** in which case this routine will be called recursively. 
01272 **
01273 ** The results of the total query are to be written into a destination
01274 ** of type eDest with parameter iParm.
01275 **
01276 ** Example 1:  Consider a three-way compound SQL statement.
01277 **
01278 **     SELECT a FROM t1 UNION SELECT b FROM t2 UNION SELECT c FROM t3
01279 **
01280 ** This statement is parsed up as follows:
01281 **
01282 **     SELECT c FROM t3
01283 **      |
01284 **      `----->  SELECT b FROM t2
01285 **                |
01286 **                `------>  SELECT a FROM t1
01287 **
01288 ** The arrows in the diagram above represent the Select.pPrior pointer.
01289 ** So if this routine is called with p equal to the t3 query, then
01290 ** pPrior will be the t2 query.  p->op will be TK_UNION in this case.
01291 **
01292 ** Notice that because of the way SQLite parses compound SELECTs, the
01293 ** individual selects always group from left to right.
01294 */
01295 static int multiSelect(Parse *pParse, Select *p, int eDest, int iParm){
01296   int rc;             /* Success code from a subroutine */
01297   Select *pPrior;     /* Another SELECT immediately to our left */
01298   Vdbe *v;            /* Generate code to this VDBE */
01299 
01300   /* Make sure there is no ORDER BY or LIMIT clause on prior SELECTs.  Only
01301   ** the last SELECT in the series may have an ORDER BY or LIMIT.
01302   */
01303   if( p==0 || p->pPrior==0 ) return 1;
01304   pPrior = p->pPrior;
01305   if( pPrior->pOrderBy ){
01306     sqliteErrorMsg(pParse,"ORDER BY clause should come after %s not before",
01307       selectOpName(p->op));
01308     return 1;
01309   }
01310   if( pPrior->nLimit>=0 || pPrior->nOffset>0 ){
01311     sqliteErrorMsg(pParse,"LIMIT clause should come after %s not before",
01312       selectOpName(p->op));
01313     return 1;
01314   }
01315 
01316   /* Make sure we have a valid query engine.  If not, create a new one.
01317   */
01318   v = sqliteGetVdbe(pParse);
01319   if( v==0 ) return 1;
01320 
01321   /* Create the destination temporary table if necessary
01322   */
01323   if( eDest==SRT_TempTable ){
01324     sqliteVdbeAddOp(v, OP_OpenTemp, iParm, 0);
01325     eDest = SRT_Table;
01326   }
01327 
01328   /* Generate code for the left and right SELECT statements.
01329   */
01330   switch( p->op ){
01331     case TK_ALL: {
01332       if( p->pOrderBy==0 ){
01333         pPrior->nLimit = p->nLimit;
01334         pPrior->nOffset = p->nOffset;
01335         rc = sqliteSelect(pParse, pPrior, eDest, iParm, 0, 0, 0);
01336         if( rc ) return rc;
01337         p->pPrior = 0;
01338         p->iLimit = pPrior->iLimit;
01339         p->iOffset = pPrior->iOffset;
01340         p->nLimit = -1;
01341         p->nOffset = 0;
01342         rc = sqliteSelect(pParse, p, eDest, iParm, 0, 0, 0);
01343         p->pPrior = pPrior;
01344         if( rc ) return rc;
01345         break;
01346       }
01347       /* For UNION ALL ... ORDER BY fall through to the next case */
01348     }
01349     case TK_EXCEPT:
01350     case TK_UNION: {
01351       int unionTab;    /* Cursor number of the temporary table holding result */
01352       int op;          /* One of the SRT_ operations to apply to self */
01353       int priorOp;     /* The SRT_ operation to apply to prior selects */
01354       int nLimit, nOffset; /* Saved values of p->nLimit and p->nOffset */
01355       ExprList *pOrderBy;  /* The ORDER BY clause for the right SELECT */
01356 
01357       priorOp = p->op==TK_ALL ? SRT_Table : SRT_Union;
01358       if( eDest==priorOp && p->pOrderBy==0 && p->nLimit<0 && p->nOffset==0 ){
01359         /* We can reuse a temporary table generated by a SELECT to our
01360         ** right.
01361         */
01362         unionTab = iParm;
01363       }else{
01364         /* We will need to create our own temporary table to hold the
01365         ** intermediate results.
01366         */
01367         unionTab = pParse->nTab++;
01368         if( p->pOrderBy 
01369         && matchOrderbyToColumn(pParse, p, p->pOrderBy, unionTab, 1) ){
01370           return 1;
01371         }
01372         if( p->op!=TK_ALL ){
01373           sqliteVdbeAddOp(v, OP_OpenTemp, unionTab, 1);
01374           sqliteVdbeAddOp(v, OP_KeyAsData, unionTab, 1);
01375         }else{
01376           sqliteVdbeAddOp(v, OP_OpenTemp, unionTab, 0);
01377         }
01378       }
01379 
01380       /* Code the SELECT statements to our left
01381       */
01382       rc = sqliteSelect(pParse, pPrior, priorOp, unionTab, 0, 0, 0);
01383       if( rc ) return rc;
01384 
01385       /* Code the current SELECT statement
01386       */
01387       switch( p->op ){
01388          case TK_EXCEPT:  op = SRT_Except;   break;
01389          case TK_UNION:   op = SRT_Union;    break;
01390          case TK_ALL:     op = SRT_Table;    break;
01391       }
01392       p->pPrior = 0;
01393       pOrderBy = p->pOrderBy;
01394       p->pOrderBy = 0;
01395       nLimit = p->nLimit;
01396       p->nLimit = -1;
01397       nOffset = p->nOffset;
01398       p->nOffset = 0;
01399       rc = sqliteSelect(pParse, p, op, unionTab, 0, 0, 0);
01400       p->pPrior = pPrior;
01401       p->pOrderBy = pOrderBy;
01402       p->nLimit = nLimit;
01403       p->nOffset = nOffset;
01404       if( rc ) return rc;
01405 
01406       /* Convert the data in the temporary table into whatever form
01407       ** it is that we currently need.
01408       */      
01409       if( eDest!=priorOp || unionTab!=iParm ){
01410         int iCont, iBreak, iStart;
01411         assert( p->pEList );
01412         if( eDest==SRT_Callback ){
01413           generateColumnNames(pParse, 0, p->pEList);
01414           generateColumnTypes(pParse, p->pSrc, p->pEList);
01415         }
01416         iBreak = sqliteVdbeMakeLabel(v);
01417         iCont = sqliteVdbeMakeLabel(v);
01418         sqliteVdbeAddOp(v, OP_Rewind, unionTab, iBreak);
01419         computeLimitRegisters(pParse, p);
01420         iStart = sqliteVdbeCurrentAddr(v);
01421         multiSelectSortOrder(p, p->pOrderBy);
01422         rc = selectInnerLoop(pParse, p, p->pEList, unionTab, p->pEList->nExpr,
01423                              p->pOrderBy, -1, eDest, iParm, 
01424                              iCont, iBreak);
01425         if( rc ) return 1;
01426         sqliteVdbeResolveLabel(v, iCont);
01427         sqliteVdbeAddOp(v, OP_Next, unionTab, iStart);
01428         sqliteVdbeResolveLabel(v, iBreak);
01429         sqliteVdbeAddOp(v, OP_Close, unionTab, 0);
01430         if( p->pOrderBy ){
01431           generateSortTail(p, v, p->pEList->nExpr, eDest, iParm);
01432         }
01433       }
01434       break;
01435     }
01436     case TK_INTERSECT: {
01437       int tab1, tab2;
01438       int iCont, iBreak, iStart;
01439       int nLimit, nOffset;
01440 
01441       /* INTERSECT is different from the others since it requires
01442       ** two temporary tables.  Hence it has its own case.  Begin
01443       ** by allocating the tables we will need.
01444       */
01445       tab1 = pParse->nTab++;
01446       tab2 = pParse->nTab++;
01447       if( p->pOrderBy && matchOrderbyToColumn(pParse,p,p->pOrderBy,tab1,1) ){
01448         return 1;
01449       }
01450       sqliteVdbeAddOp(v, OP_OpenTemp, tab1, 1);
01451       sqliteVdbeAddOp(v, OP_KeyAsData, tab1, 1);
01452 
01453       /* Code the SELECTs to our left into temporary table "tab1".
01454       */
01455       rc = sqliteSelect(pParse, pPrior, SRT_Union, tab1, 0, 0, 0);
01456       if( rc ) return rc;
01457 
01458       /* Code the current SELECT into temporary table "tab2"
01459       */
01460       sqliteVdbeAddOp(v, OP_OpenTemp, tab2, 1);
01461       sqliteVdbeAddOp(v, OP_KeyAsData, tab2, 1);
01462       p->pPrior = 0;
01463       nLimit = p->nLimit;
01464       p->nLimit = -1;
01465       nOffset = p->nOffset;
01466       p->nOffset = 0;
01467       rc = sqliteSelect(pParse, p, SRT_Union, tab2, 0, 0, 0);
01468       p->pPrior = pPrior;
01469       p->nLimit = nLimit;
01470       p->nOffset = nOffset;
01471       if( rc ) return rc;
01472 
01473       /* Generate code to take the intersection of the two temporary
01474       ** tables.
01475       */
01476       assert( p->pEList );
01477       if( eDest==SRT_Callback ){
01478         generateColumnNames(pParse, 0, p->pEList);
01479         generateColumnTypes(pParse, p->pSrc, p->pEList);
01480       }
01481       iBreak = sqliteVdbeMakeLabel(v);
01482       iCont = sqliteVdbeMakeLabel(v);
01483       sqliteVdbeAddOp(v, OP_Rewind, tab1, iBreak);
01484       computeLimitRegisters(pParse, p);
01485       iStart = sqliteVdbeAddOp(v, OP_FullKey, tab1, 0);
01486       sqliteVdbeAddOp(v, OP_NotFound, tab2, iCont);
01487       multiSelectSortOrder(p, p->pOrderBy);
01488       rc = selectInnerLoop(pParse, p, p->pEList, tab1, p->pEList->nExpr,
01489                              p->pOrderBy, -1, eDest, iParm, 
01490                              iCont, iBreak);
01491       if( rc ) return 1;
01492       sqliteVdbeResolveLabel(v, iCont);
01493       sqliteVdbeAddOp(v, OP_Next, tab1, iStart);
01494       sqliteVdbeResolveLabel(v, iBreak);
01495       sqliteVdbeAddOp(v, OP_Close, tab2, 0);
01496       sqliteVdbeAddOp(v, OP_Close, tab1, 0);
01497       if( p->pOrderBy ){
01498         generateSortTail(p, v, p->pEList->nExpr, eDest, iParm);
01499       }
01500       break;
01501     }
01502   }
01503   assert( p->pEList && pPrior->pEList );
01504   if( p->pEList->nExpr!=pPrior->pEList->nExpr ){
01505     sqliteErrorMsg(pParse, "SELECTs to the left and right of %s"
01506       " do not have the same number of result columns", selectOpName(p->op));
01507     return 1;
01508   }
01509   return 0;
01510 }
01511 
01512 /*
01513 ** Scan through the expression pExpr.  Replace every reference to
01514 ** a column in table number iTable with a copy of the iColumn-th
01515 ** entry in pEList.  (But leave references to the ROWID column 
01516 ** unchanged.)
01517 **
01518 ** This routine is part of the flattening procedure.  A subquery
01519 ** whose result set is defined by pEList appears as entry in the
01520 ** FROM clause of a SELECT such that the VDBE cursor assigned to that
01521 ** FORM clause entry is iTable.  This routine make the necessary 
01522 ** changes to pExpr so that it refers directly to the source table
01523 ** of the subquery rather the result set of the subquery.
01524 */
01525 static void substExprList(ExprList*,int,ExprList*);  /* Forward Decl */
01526 static void substExpr(Expr *pExpr, int iTable, ExprList *pEList){
01527   if( pExpr==0 ) return;
01528   if( pExpr->op==TK_COLUMN && pExpr->iTable==iTable ){
01529     if( pExpr->iColumn<0 ){
01530       pExpr->op = TK_NULL;
01531     }else{
01532       Expr *pNew;
01533       assert( pEList!=0 && pExpr->iColumn<pEList->nExpr );
01534       assert( pExpr->pLeft==0 && pExpr->pRight==0 && pExpr->pList==0 );
01535       pNew = pEList->a[pExpr->iColumn].pExpr;
01536       assert( pNew!=0 );
01537       pExpr->op = pNew->op;
01538       pExpr->dataType = pNew->dataType;
01539       assert( pExpr->pLeft==0 );
01540       pExpr->pLeft = sqliteExprDup(pNew->pLeft);
01541       assert( pExpr->pRight==0 );
01542       pExpr->pRight = sqliteExprDup(pNew->pRight);
01543       assert( pExpr->pList==0 );
01544       pExpr->pList = sqliteExprListDup(pNew->pList);
01545       pExpr->iTable = pNew->iTable;
01546       pExpr->iColumn = pNew->iColumn;
01547       pExpr->iAgg = pNew->iAgg;
01548       sqliteTokenCopy(&pExpr->token, &pNew->token);
01549       sqliteTokenCopy(&pExpr->span, &pNew->span);
01550     }
01551   }else{
01552     substExpr(pExpr->pLeft, iTable, pEList);
01553     substExpr(pExpr->pRight, iTable, pEList);
01554     substExprList(pExpr->pList, iTable, pEList);
01555   }
01556 }
01557 static void 
01558 substExprList(ExprList *pList, int iTable, ExprList *pEList){
01559   int i;
01560   if( pList==0 ) return;
01561   for(i=0; i<pList->nExpr; i++){
01562     substExpr(pList->a[i].pExpr, iTable, pEList);
01563   }
01564 }
01565 
01566 /*
01567 ** This routine attempts to flatten subqueries in order to speed
01568 ** execution.  It returns 1 if it makes changes and 0 if no flattening
01569 ** occurs.
01570 **
01571 ** To understand the concept of flattening, consider the following
01572 ** query:
01573 **
01574 **     SELECT a FROM (SELECT x+y AS a FROM t1 WHERE z<100) WHERE a>5
01575 **
01576 ** The default way of implementing this query is to execute the
01577 ** subquery first and store the results in a temporary table, then
01578 ** run the outer query on that temporary table.  This requires two
01579 ** passes over the data.  Furthermore, because the temporary table
01580 ** has no indices, the WHERE clause on the outer query cannot be
01581 ** optimized.
01582 **
01583 ** This routine attempts to rewrite queries such as the above into
01584 ** a single flat select, like this:
01585 **
01586 **     SELECT x+y AS a FROM t1 WHERE z<100 AND a>5
01587 **
01588 ** The code generated for this simpification gives the same result
01589 ** but only has to scan the data once.  And because indices might 
01590 ** exist on the table t1, a complete scan of the data might be
01591 ** avoided.
01592 **
01593 ** Flattening is only attempted if all of the following are true:
01594 **
01595 **   (1)  The subquery and the outer query do not both use aggregates.
01596 **
01597 **   (2)  The subquery is not an aggregate or the outer query is not a join.
01598 **
01599 **   (3)  The subquery is not the right operand of a left outer join, or
01600 **        the subquery is not itself a join.  (Ticket #306)
01601 **
01602 **   (4)  The subquery is not DISTINCT or the outer query is not a join.
01603 **
01604 **   (5)  The subquery is not DISTINCT or the outer query does not use
01605 **        aggregates.
01606 **
01607 **   (6)  The subquery does not use aggregates or the outer query is not
01608 **        DISTINCT.
01609 **
01610 **   (7)  The subquery has a FROM clause.
01611 **
01612 **   (8)  The subquery does not use LIMIT or the outer query is not a join.
01613 **
01614 **   (9)  The subquery does not use LIMIT or the outer query does not use
01615 **        aggregates.
01616 **
01617 **  (10)  The subquery does not use aggregates or the outer query does not
01618 **        use LIMIT.
01619 **
01620 **  (11)  The subquery and the outer query do not both have ORDER BY clauses.
01621 **
01622 **  (12)  The subquery is not the right term of a LEFT OUTER JOIN or the
01623 **        subquery has no WHERE clause.  (added by ticket #350)
01624 **
01625 ** In this routine, the "p" parameter is a pointer to the outer query.
01626 ** The subquery is p->pSrc->a[iFrom].  isAgg is true if the outer query
01627 ** uses aggregates and subqueryIsAgg is true if the subquery uses aggregates.
01628 **
01629 ** If flattening is not attempted, this routine is a no-op and returns 0.
01630 ** If flattening is attempted this routine returns 1.
01631 **
01632 ** All of the expression analysis must occur on both the outer query and
01633 ** the subquery before this routine runs.
01634 */
01635 static int flattenSubquery(
01636   Parse *pParse,       /* The parsing context */
01637   Select *p,           /* The parent or outer SELECT statement */
01638   int iFrom,           /* Index in p->pSrc->a[] of the inner subquery */
01639   int isAgg,           /* True if outer SELECT uses aggregate functions */
01640   int subqueryIsAgg    /* True if the subquery uses aggregate functions */
01641 ){
01642   Select *pSub;       /* The inner query or "subquery" */
01643   SrcList *pSrc;      /* The FROM clause of the outer query */
01644   SrcList *pSubSrc;   /* The FROM clause of the subquery */
01645   ExprList *pList;    /* The result set of the outer query */
01646   int iParent;        /* VDBE cursor number of the pSub result set temp table */
01647   int i;
01648   Expr *pWhere;
01649 
01650   /* Check to see if flattening is permitted.  Return 0 if not.
01651   */
01652   if( p==0 ) return 0;
01653   pSrc = p->pSrc;
01654   assert( pSrc && iFrom>=0 && iFrom<pSrc->nSrc );
01655   pSub = pSrc->a[iFrom].pSelect;
01656   assert( pSub!=0 );
01657   if( isAgg && subqueryIsAgg ) return 0;
01658   if( subqueryIsAgg && pSrc->nSrc>1 ) return 0;
01659   pSubSrc = pSub->pSrc;
01660   assert( pSubSrc );
01661   if( pSubSrc->nSrc==0 ) return 0;
01662   if( (pSub->isDistinct || pSub->nLimit>=0) &&  (pSrc->nSrc>1 || isAgg) ){
01663      return 0;
01664   }
01665   if( (p->isDistinct || p->nLimit>=0) && subqueryIsAgg ) return 0;
01666   if( p->pOrderBy && pSub->pOrderBy ) return 0;
01667 
01668   /* Restriction 3:  If the subquery is a join, make sure the subquery is 
01669   ** not used as the right operand of an outer join.  Examples of why this
01670   ** is not allowed:
01671   **
01672   **         t1 LEFT OUTER JOIN (t2 JOIN t3)
01673   **
01674   ** If we flatten the above, we would get
01675   **
01676   **         (t1 LEFT OUTER JOIN t2) JOIN t3
01677   **
01678   ** which is not at all the same thing.
01679   */
01680   if( pSubSrc->nSrc>1 && iFrom>0 && (pSrc->a[iFrom-1].jointype & JT_OUTER)!=0 ){
01681     return 0;
01682   }
01683 
01684   /* Restriction 12:  If the subquery is the right operand of a left outer
01685   ** join, make sure the subquery has no WHERE clause.
01686   ** An examples of why this is not allowed:
01687   **
01688   **         t1 LEFT OUTER JOIN (SELECT * FROM t2 WHERE t2.x>0)
01689   **
01690   ** If we flatten the above, we would get
01691   **
01692   **         (t1 LEFT OUTER JOIN t2) WHERE t2.x>0
01693   **
01694   ** But the t2.x>0 test will always fail on a NULL row of t2, which
01695   ** effectively converts the OUTER JOIN into an INNER JOIN.
01696   */
01697   if( iFrom>0 && (pSrc->a[iFrom-1].jointype & JT_OUTER)!=0 
01698       && pSub->pWhere!=0 ){
01699     return 0;
01700   }
01701 
01702   /* If we reach this point, it means flattening is permitted for the
01703   ** iFrom-th entry of the FROM clause in the outer query.
01704   */
01705 
01706   /* Move all of the FROM elements of the subquery into the
01707   ** the FROM clause of the outer query.  Before doing this, remember
01708   ** the cursor number for the original outer query FROM element in
01709   ** iParent.  The iParent cursor will never be used.  Subsequent code
01710   ** will scan expressions looking for iParent references and replace
01711   ** those references with expressions that resolve to the subquery FROM
01712   ** elements we are now copying in.
01713   */
01714   iParent = pSrc->a[iFrom].iCursor;
01715   {
01716     int nSubSrc = pSubSrc->nSrc;
01717     int jointype = pSrc->a[iFrom].jointype;
01718 
01719     if( pSrc->a[iFrom].pTab && pSrc->a[iFrom].pTab->isTransient ){
01720       sqliteDeleteTable(0, pSrc->a[iFrom].pTab);
01721     }
01722     sqliteFree(pSrc->a[iFrom].zDatabase);
01723     sqliteFree(pSrc->a[iFrom].zName);
01724     sqliteFree(pSrc->a[iFrom].zAlias);
01725     if( nSubSrc>1 ){
01726       int extra = nSubSrc - 1;
01727       for(i=1; i<nSubSrc; i++){
01728         pSrc = sqliteSrcListAppend(pSrc, 0, 0);
01729       }
01730       p->pSrc = pSrc;
01731       for(i=pSrc->nSrc-1; i-extra>=iFrom; i--){
01732         pSrc->a[i] = pSrc->a[i-extra];
01733       }
01734     }
01735     for(i=0; i<nSubSrc; i++){
01736       pSrc->a[i+iFrom] = pSubSrc->a[i];
01737       memset(&pSubSrc->a[i], 0, sizeof(pSubSrc->a[i]));
01738     }
01739     pSrc->a[iFrom+nSubSrc-1].jointype = jointype;
01740   }
01741 
01742   /* Now begin substituting subquery result set expressions for 
01743   ** references to the iParent in the outer query.
01744   ** 
01745   ** Example:
01746   **
01747   **   SELECT a+5, b*10 FROM (SELECT x*3 AS a, y+10 AS b FROM t1) WHERE a>b;
01748   **   \                     \_____________ subquery __________/          /
01749   **    \_____________________ outer query ______________________________/
01750   **
01751   ** We look at every expression in the outer query and every place we see
01752   ** "a" we substitute "x*3" and every place we see "b" we substitute "y+10".
01753   */
01754   substExprList(p->pEList, iParent, pSub->pEList);
01755   pList = p->pEList;
01756   for(i=0; i<pList->nExpr; i++){
01757     Expr *pExpr;
01758     if( pList->a[i].zName==0 && (pExpr = pList->a[i].pExpr)->span.z!=0 ){
01759       pList->a[i].zName = sqliteStrNDup(pExpr->span.z, pExpr->span.n);
01760     }
01761   }
01762   if( isAgg ){
01763     substExprList(p->pGroupBy, iParent, pSub->pEList);
01764     substExpr(p->pHaving, iParent, pSub->pEList);
01765   }
01766   if( pSub->pOrderBy ){
01767     assert( p->pOrderBy==0 );
01768     p->pOrderBy = pSub->pOrderBy;
01769     pSub->pOrderBy = 0;
01770   }else if( p->pOrderBy ){
01771     substExprList(p->pOrderBy, iParent, pSub->pEList);
01772   }
01773   if( pSub->pWhere ){
01774     pWhere = sqliteExprDup(pSub->pWhere);
01775   }else{
01776     pWhere = 0;
01777   }
01778   if( subqueryIsAgg ){
01779     assert( p->pHaving==0 );
01780     p->pHaving = p->pWhere;
01781     p->pWhere = pWhere;
01782     substExpr(p->pHaving, iParent, pSub->pEList);
01783     if( pSub->pHaving ){
01784       Expr *pHaving = sqliteExprDup(pSub->pHaving);
01785       if( p->pHaving ){
01786         p->pHaving = sqliteExpr(TK_AND, p->pHaving, pHaving, 0);
01787       }else{
01788         p->pHaving = pHaving;
01789       }
01790     }
01791     assert( p->pGroupBy==0 );
01792     p->pGroupBy = sqliteExprListDup(pSub->pGroupBy);
01793   }else if( p->pWhere==0 ){
01794     p->pWhere = pWhere;
01795   }else{
01796     substExpr(p->pWhere, iParent, pSub->pEList);
01797     if( pWhere ){
01798       p->pWhere = sqliteExpr(TK_AND, p->pWhere, pWhere, 0);
01799     }
01800   }
01801 
01802   /* The flattened query is distinct if either the inner or the
01803   ** outer query is distinct. 
01804   */
01805   p->isDistinct = p->isDistinct || pSub->isDistinct;
01806 
01807   /* Transfer the limit expression from the subquery to the outer
01808   ** query.
01809   */
01810   if( pSub->nLimit>=0 ){
01811     if( p->nLimit<0 ){
01812       p->nLimit = pSub->nLimit;
01813     }else if( p->nLimit+p->nOffset > pSub->nLimit+pSub->nOffset ){
01814       p->nLimit = pSub->nLimit + pSub->nOffset - p->nOffset;
01815     }
01816   }
01817   p->nOffset += pSub->nOffset;
01818 
01819   /* Finially, delete what is left of the subquery and return
01820   ** success.
01821   */
01822   sqliteSelectDelete(pSub);
01823   return 1;
01824 }
01825 
01826 /*
01827 ** Analyze the SELECT statement passed in as an argument to see if it
01828 ** is a simple min() or max() query.  If it is and this query can be
01829 ** satisfied using a single seek to the beginning or end of an index,
01830 ** then generate the code for this SELECT and return 1.  If this is not a 
01831 ** simple min() or max() query, then return 0;
01832 **
01833 ** A simply min() or max() query looks like this:
01834 **
01835 **    SELECT min(a) FROM table;
01836 **    SELECT max(a) FROM table;
01837 **
01838 ** The query may have only a single table in its FROM argument.  There
01839 ** can be no GROUP BY or HAVING or WHERE clauses.  The result set must
01840 ** be the min() or max() of a single column of the table.  The column
01841 ** in the min() or max() function must be indexed.
01842 **
01843 ** The parameters to this routine are the same as for sqliteSelect().
01844 ** See the header comment on that routine for additional information.
01845 */
01846 static int simpleMinMaxQuery(Parse *pParse, Select *p, int eDest, int iParm){
01847   Expr *pExpr;
01848   int iCol;
01849   Table *pTab;
01850   Index *pIdx;
01851   int base;
01852   Vdbe *v;
01853   int seekOp;
01854   int cont;
01855   ExprList *pEList, *pList, eList;
01856   struct ExprList_item eListItem;
01857   SrcList *pSrc;
01858   
01859 
01860   /* Check to see if this query is a simple min() or max() query.  Return
01861   ** zero if it is  not.
01862   */
01863   if( p->pGroupBy || p->pHaving || p->pWhere ) return 0;
01864   pSrc = p->pSrc;
01865   if( pSrc->nSrc!=1 ) return 0;
01866   pEList = p->pEList;
01867   if( pEList->nExpr!=1 ) return 0;
01868   pExpr = pEList->a[0].pExpr;
01869   if( pExpr->op!=TK_AGG_FUNCTION ) return 0;
01870   pList = pExpr->pList;
01871   if( pList==0 || pList->nExpr!=1 ) return 0;
01872   if( pExpr->token.n!=3 ) return 0;
01873   if( sqliteStrNICmp(pExpr->token.z,"min",3)==0 ){
01874     seekOp = OP_Rewind;
01875   }else if( sqliteStrNICmp(pExpr->token.z,"max",3)==0 ){
01876     seekOp = OP_Last;
01877   }else{
01878     return 0;
01879   }
01880   pExpr = pList->a[0].pExpr;
01881   if( pExpr->op!=TK_COLUMN ) return 0;
01882   iCol = pExpr->iColumn;
01883   pTab = pSrc->a[0].pTab;
01884 
01885   /* If we get to here, it means the query is of the correct form.
01886   ** Check to make sure we have an index and make pIdx point to the
01887   ** appropriate index.  If the min() or max() is on an INTEGER PRIMARY
01888   ** key column, no index is necessary so set pIdx to NULL.  If no
01889   ** usable index is found, return 0.
01890   */
01891   if( iCol<0 ){
01892     pIdx = 0;
01893   }else{
01894     for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
01895       assert( pIdx->nColumn>=1 );
01896       if( pIdx->aiColumn[0]==iCol ) break;
01897     }
01898     if( pIdx==0 ) return 0;
01899   }
01900 
01901   /* Identify column types if we will be using the callback.  This
01902   ** step is skipped if the output is going to a table or a memory cell.
01903   ** The column names have already been generated in the calling function.
01904   */
01905   v = sqliteGetVdbe(pParse);
01906   if( v==0 ) return 0;
01907   if( eDest==SRT_Callback ){
01908     generateColumnTypes(pParse, p->pSrc, p->pEList);
01909   }
01910 
01911   /* If the output is destined for a temporary table, open that table.
01912   */
01913   if( eDest==SRT_TempTable ){
01914     sqliteVdbeAddOp(v, OP_OpenTemp, iParm, 0);
01915   }
01916 
01917   /* Generating code to find the min or the max.  Basically all we have
01918   ** to do is find the first or the last entry in the chosen index.  If
01919   ** the min() or max() is on the INTEGER PRIMARY KEY, then find the first
01920   ** or last entry in the main table.
01921   */
01922   sqliteCodeVerifySchema(pParse, pTab->iDb);
01923   base = pSrc->a[0].iCursor;
01924   computeLimitRegisters(pParse, p);
01925   if( pSrc->a[0].pSelect==0 ){
01926     sqliteVdbeAddOp(v, OP_Integer, pTab->iDb, 0);
01927     sqliteVdbeOp3(v, OP_OpenRead, base, pTab->tnum, pTab->zName, 0);
01928   }
01929   cont = sqliteVdbeMakeLabel(v);
01930   if( pIdx==0 ){
01931     sqliteVdbeAddOp(v, seekOp, base, 0);
01932   }else{
01933     sqliteVdbeAddOp(v, OP_Integer, pIdx->iDb, 0);
01934     sqliteVdbeOp3(v, OP_OpenRead, base+1, pIdx->tnum, pIdx->zName, P3_STATIC);
01935     if( seekOp==OP_Rewind ){
01936       sqliteVdbeAddOp(v, OP_String, 0, 0);
01937       sqliteVdbeAddOp(v, OP_MakeKey, 1, 0);
01938       sqliteVdbeAddOp(v, OP_IncrKey, 0, 0);
01939       seekOp = OP_MoveTo;
01940     }
01941     sqliteVdbeAddOp(v, seekOp, base+1, 0);
01942     sqliteVdbeAddOp(v, OP_IdxRecno, base+1, 0);
01943     sqliteVdbeAddOp(v, OP_Close, base+1, 0);
01944     sqliteVdbeAddOp(v, OP_MoveTo, base, 0);
01945   }
01946   eList.nExpr = 1;
01947   memset(&eListItem, 0, sizeof(eListItem));
01948   eList.a = &eListItem;
01949   eList.a[0].pExpr = pExpr;
01950   selectInnerLoop(pParse, p, &eList, 0, 0, 0, -1, eDest, iParm, cont, cont);
01951   sqliteVdbeResolveLabel(v, cont);
01952   sqliteVdbeAddOp(v, OP_Close, base, 0);
01953   
01954   return 1;
01955 }
01956 
01957 /*
01958 ** Generate code for the given SELECT statement.
01959 **
01960 ** The results are distributed in various ways depending on the
01961 ** value of eDest and iParm.
01962 **
01963 **     eDest Value       Result
01964 **     ------------    -------------------------------------------
01965 **     SRT_Callback    Invoke the callback for each row of the result.
01966 **
01967 **     SRT_Mem         Store first result in memory cell iParm
01968 **
01969 **     SRT_Set         Store results as keys of a table with cursor iParm
01970 **
01971 **     SRT_Union       Store results as a key in a temporary table iParm
01972 **
01973 **     SRT_Except      Remove results from the temporary table iParm.
01974 **
01975 **     SRT_Table       Store results in temporary table iParm
01976 **
01977 ** The table above is incomplete.  Additional eDist value have be added
01978 ** since this comment was written.  See the selectInnerLoop() function for
01979 ** a complete listing of the allowed values of eDest and their meanings.
01980 **
01981 ** This routine returns the number of errors.  If any errors are
01982 ** encountered, then an appropriate error message is left in
01983 ** pParse->zErrMsg.
01984 **
01985 ** This routine does NOT free the Select structure passed in.  The
01986 ** calling function needs to do that.
01987 **
01988 ** The pParent, parentTab, and *pParentAgg fields are filled in if this
01989 ** SELECT is a subquery.  This routine may try to combine this SELECT
01990 ** with its parent to form a single flat query.  In so doing, it might
01991 ** change the parent query from a non-aggregate to an aggregate query.
01992 ** For that reason, the pParentAgg flag is passed as a pointer, so it
01993 ** can be changed.
01994 **
01995 ** Example 1:   The meaning of the pParent parameter.
01996 **
01997 **    SELECT * FROM t1 JOIN (SELECT x, count(*) FROM t2) JOIN t3;
01998 **    \                      \_______ subquery _______/        /
01999 **     \                                                      /
02000 **      \____________________ outer query ___________________/
02001 **
02002 ** This routine is called for the outer query first.   For that call,
02003 ** pParent will be NULL.  During the processing of the outer query, this 
02004 ** routine is called recursively to handle the subquery.  For the recursive
02005 ** call, pParent will point to the outer query.  Because the subquery is
02006 ** the second element in a three-way join, the parentTab parameter will
02007 ** be 1 (the 2nd value of a 0-indexed array.)
02008 */
02009 int sqliteSelect(
02010   Parse *pParse,         /* The parser context */
02011   Select *p,             /* The SELECT statement being coded. */
02012   int eDest,             /* How to dispose of the results */
02013   int iParm,             /* A parameter used by the eDest disposal method */
02014   Select *pParent,       /* Another SELECT for which this is a sub-query */
02015   int parentTab,         /* Index in pParent->pSrc of this query */
02016   int *pParentAgg        /* True if pParent uses aggregate functions */
02017 ){
02018   int i;
02019   WhereInfo *pWInfo;
02020   Vdbe *v;
02021   int isAgg = 0;         /* True for select lists like "count(*)" */
02022   ExprList *pEList;      /* List of columns to extract. */
02023   SrcList *pTabList;     /* List of tables to select from */
02024   Expr *pWhere;          /* The WHERE clause.  May be NULL */
02025   ExprList *pOrderBy;    /* The ORDER BY clause.  May be NULL */
02026   ExprList *pGroupBy;    /* The GROUP BY clause.  May be NULL */
02027   Expr *pHaving;         /* The HAVING clause.  May be NULL */
02028   int isDistinct;        /* True if the DISTINCT keyword is present */
02029   int distinct;          /* Table to use for the distinct set */
02030   int rc = 1;            /* Value to return from this function */
02031 
02032   if( sqlite_malloc_failed || pParse->nErr || p==0 ) return 1;
02033   if( sqliteAuthCheck(pParse, SQLITE_SELECT, 0, 0, 0) ) return 1;
02034 
02035   /* If there is are a sequence of queries, do the earlier ones first.
02036   */
02037   if( p->pPrior ){
02038     return multiSelect(pParse, p, eDest, iParm);
02039   }
02040 
02041   /* Make local copies of the parameters for this query.
02042   */
02043   pTabList = p->pSrc;
02044   pWhere = p->pWhere;
02045   pOrderBy = p->pOrderBy;
02046   pGroupBy = p->pGroupBy;
02047   pHaving = p->pHaving;
02048   isDistinct = p->isDistinct;
02049 
02050   /* Allocate VDBE cursors for each table in the FROM clause
02051   */
02052   sqliteSrcListAssignCursors(pParse, pTabList);
02053 
02054   /* 
02055   ** Do not even attempt to generate any code if we have already seen
02056   ** errors before this routine starts.
02057   */
02058   if( pParse->nErr>0 ) goto select_end;
02059 
02060   /* Expand any "*" terms in the result set.  (For example the "*" in
02061   ** "SELECT * FROM t1")  The fillInColumnlist() routine also does some
02062   ** other housekeeping - see the header comment for details.
02063   */
02064   if( fillInColumnList(pParse, p) ){
02065     goto select_end;
02066   }
02067   pWhere = p->pWhere;
02068   pEList = p->pEList;
02069   if( pEList==0 ) goto select_end;
02070 
02071   /* If writing to memory or generating a set
02072   ** only a single column may be output.
02073   */
02074   if( (eDest==SRT_Mem || eDest==SRT_Set) && pEList->nExpr>1 ){
02075     sqliteErrorMsg(pParse, "only a single result allowed for "
02076        "a SELECT that is part of an expression");
02077     goto select_end;
02078   }
02079 
02080   /* ORDER BY is ignored for some destinations.
02081   */
02082   switch( eDest ){
02083     case SRT_Union:
02084     case SRT_Except:
02085     case SRT_Discard:
02086       pOrderBy = 0;
02087       break;
02088     default:
02089       break;
02090   }
02091 
02092   /* At this point, we should have allocated all the cursors that we
02093   ** need to handle subquerys and temporary tables.  
02094   **
02095   ** Resolve the column names and do a semantics check on all the expressions.
02096   */
02097   for(i=0; i<pEList->nExpr; i++){
02098     if( sqliteExprResolveIds(pParse, pTabList, 0, pEList->a[i].pExpr) ){
02099       goto select_end;
02100     }
02101     if( sqliteExprCheck(pParse, pEList->a[i].pExpr, 1, &isAgg) ){
02102       goto select_end;
02103     }
02104   }
02105   if( pWhere ){
02106     if( sqliteExprResolveIds(pParse, pTabList, pEList, pWhere) ){
02107       goto select_end;
02108     }
02109     if( sqliteExprCheck(pParse, pWhere, 0, 0) ){
02110       goto select_end;
02111     }
02112   }
02113   if( pHaving ){
02114     if( pGroupBy==0 ){
02115       sqliteErrorMsg(pParse, "a GROUP BY clause is required before HAVING");
02116       goto select_end;
02117     }
02118     if( sqliteExprResolveIds(pParse, pTabList, pEList, pHaving) ){
02119       goto select_end;
02120     }
02121     if( sqliteExprCheck(pParse, pHaving, 1, &isAgg) ){
02122       goto select_end;
02123     }
02124   }
02125   if( pOrderBy ){
02126     for(i=0; i<pOrderBy->nExpr; i++){
02127       int iCol;
02128       Expr *pE = pOrderBy->a[i].pExpr;
02129       if( sqliteExprIsInteger(pE, &iCol) && iCol>0 && iCol<=pEList->nExpr ){
02130         sqliteExprDelete(pE);
02131         pE = pOrderBy->a[i].pExpr = sqliteExprDup(pEList->a[iCol-1].pExpr);
02132       }
02133       if( sqliteExprResolveIds(pParse, pTabList, pEList, pE) ){
02134         goto select_end;
02135       }
02136       if( sqliteExprCheck(pParse, pE, isAgg, 0) ){
02137         goto select_end;
02138       }
02139       if( sqliteExprIsConstant(pE) ){
02140         if( sqliteExprIsInteger(pE, &iCol)==0 ){
02141           sqliteErrorMsg(pParse,
02142              "ORDER BY terms must not be non-integer constants");
02143           goto select_end;
02144         }else if( iCol<=0 || iCol>pEList->nExpr ){
02145           sqliteErrorMsg(pParse, 
02146              "ORDER BY column number %d out of range - should be "
02147              "between 1 and %d", iCol, pEList->nExpr);
02148           goto select_end;
02149         }
02150       }
02151     }
02152   }
02153   if( pGroupBy ){
02154     for(i=0; i<pGroupBy->nExpr; i++){
02155       int iCol;
02156       Expr *pE = pGroupBy->a[i].pExpr;
02157       if( sqliteExprIsInteger(pE, &iCol) && iCol>0 && iCol<=pEList->nExpr ){
02158         sqliteExprDelete(pE);
02159         pE = pGroupBy->a[i].pExpr = sqliteExprDup(pEList->a[iCol-1].pExpr);
02160       }
02161       if( sqliteExprResolveIds(pParse, pTabList, pEList, pE) ){
02162         goto select_end;
02163       }
02164       if( sqliteExprCheck(pParse, pE, isAgg, 0) ){
02165         goto select_end;
02166       }
02167       if( sqliteExprIsConstant(pE) ){
02168         if( sqliteExprIsInteger(pE, &iCol)==0 ){
02169           sqliteErrorMsg(pParse,
02170             "GROUP BY terms must not be non-integer constants");
02171           goto select_end;
02172         }else if( iCol<=0 || iCol>pEList->nExpr ){
02173           sqliteErrorMsg(pParse,
02174              "GROUP BY column number %d out of range - should be "
02175              "between 1 and %d", iCol, pEList->nExpr);
02176           goto select_end;
02177         }
02178       }
02179     }
02180   }
02181 
02182   /* Begin generating code.
02183   */
02184   v = sqliteGetVdbe(pParse);
02185   if( v==0 ) goto select_end;
02186 
02187   /* Identify column names if we will be using them in a callback.  This
02188   ** step is skipped if the output is going to some other destination.
02189   */
02190   if( eDest==SRT_Callback ){
02191     generateColumnNames(pParse, pTabList, pEList);
02192   }
02193 
02194   /* Generate code for all sub-queries in the FROM clause
02195   */
02196   for(i=0; i<pTabList->nSrc; i++){
02197     const char *zSavedAuthContext;
02198     int needRestoreContext;
02199 
02200     if( pTabList->a[i].pSelect==0 ) continue;
02201     if( pTabList->a[i].zName!=0 ){
02202       zSavedAuthContext = pParse->zAuthContext;
02203       pParse->zAuthContext = pTabList->a[i].zName;
02204       needRestoreContext = 1;
02205     }else{
02206       needRestoreContext = 0;
02207     }
02208     sqliteSelect(pParse, pTabList->a[i].pSelect, SRT_TempTable, 
02209                  pTabList->a[i].iCursor, p, i, &isAgg);
02210     if( needRestoreContext ){
02211       pParse->zAuthContext = zSavedAuthContext;
02212     }
02213     pTabList = p->pSrc;
02214     pWhere = p->pWhere;
02215     if( eDest!=SRT_Union && eDest!=SRT_Except && eDest!=SRT_Discard ){
02216       pOrderBy = p->pOrderBy;
02217     }
02218     pGroupBy = p->pGroupBy;
02219     pHaving = p->pHaving;
02220     isDistinct = p->isDistinct;
02221   }
02222 
02223   /* Check for the special case of a min() or max() function by itself
02224   ** in the result set.
02225   */
02226   if( simpleMinMaxQuery(pParse, p, eDest, iParm) ){
02227     rc = 0;
02228     goto select_end;
02229   }
02230 
02231   /* Check to see if this is a subquery that can be "flattened" into its parent.
02232   ** If flattening is a possiblity, do so and return immediately.  
02233   */
02234   if( pParent && pParentAgg &&
02235       flattenSubquery(pParse, pParent, parentTab, *pParentAgg, isAgg) ){
02236     if( isAgg ) *pParentAgg = 1;
02237     return rc;
02238   }
02239 
02240   /* Set the limiter.
02241   */
02242   computeLimitRegisters(pParse, p);
02243 
02244   /* Identify column types if we will be using a callback.  This
02245   ** step is skipped if the output is going to a destination other
02246   ** than a callback.
02247   **
02248   ** We have to do this separately from the creation of column names
02249   ** above because if the pTabList contains views then they will not
02250   ** have been resolved and we will not know the column types until
02251   ** now.
02252   */
02253   if( eDest==SRT_Callback ){
02254     generateColumnTypes(pParse, pTabList, pEList);
02255   }
02256 
02257   /* If the output is destined for a temporary table, open that table.
02258   */
02259   if( eDest==SRT_TempTable ){
02260     sqliteVdbeAddOp(v, OP_OpenTemp, iParm, 0);
02261   }
02262 
02263   /* Do an analysis of aggregate expressions.
02264   */
02265   sqliteAggregateInfoReset(pParse);
02266   if( isAgg || pGroupBy ){
02267     assert( pParse->nAgg==0 );
02268     isAgg = 1;
02269     for(i=0; i<pEList->nExpr; i++){
02270       if( sqliteExprAnalyzeAggregates(pParse, pEList->a[i].pExpr) ){
02271         goto select_end;
02272       }
02273     }
02274     if( pGroupBy ){
02275       for(i=0; i<pGroupBy->nExpr; i++){
02276         if( sqliteExprAnalyzeAggregates(pParse, pGroupBy->a[i].pExpr) ){
02277           goto select_end;
02278         }
02279       }
02280     }
02281     if( pHaving && sqliteExprAnalyzeAggregates(pParse, pHaving) ){
02282       goto select_end;
02283     }
02284     if( pOrderBy ){
02285       for(i=0; i<pOrderBy->nExpr; i++){
02286         if( sqliteExprAnalyzeAggregates(pParse, pOrderBy->a[i].pExpr) ){
02287           goto select_end;
02288         }
02289       }
02290     }
02291   }
02292 
02293   /* Reset the aggregator
02294   */
02295   if( isAgg ){
02296     sqliteVdbeAddOp(v, OP_AggReset, 0, pParse->nAgg);
02297     for(i=0; i<pParse->nAgg; i++){
02298       FuncDef *pFunc;
02299       if( (pFunc = pParse->aAgg[i].pFunc)!=0 && pFunc->xFinalize!=0 ){
02300         sqliteVdbeOp3(v, OP_AggInit, 0, i, (char*)pFunc, P3_POINTER);
02301       }
02302     }
02303     if( pGroupBy==0 ){
02304       sqliteVdbeAddOp(v, OP_String, 0, 0);
02305       sqliteVdbeAddOp(v, OP_AggFocus, 0, 0);
02306     }
02307   }
02308 
02309   /* Initialize the memory cell to NULL
02310   */
02311   if( eDest==SRT_Mem ){
02312     sqliteVdbeAddOp(v, OP_String, 0, 0);
02313     sqliteVdbeAddOp(v, OP_MemStore, iParm, 1);
02314   }
02315 
02316   /* Open a temporary table to use for the distinct set.
02317   */
02318   if( isDistinct ){
02319     distinct = pParse->nTab++;
02320     sqliteVdbeAddOp(v, OP_OpenTemp, distinct, 1);
02321   }else{
02322     distinct = -1;
02323   }
02324 
02325   /* Begin the database scan
02326   */
02327   pWInfo = sqliteWhereBegin(pParse, pTabList, pWhere, 0, 
02328                             pGroupBy ? 0 : &pOrderBy);
02329   if( pWInfo==0 ) goto select_end;
02330 
02331   /* Use the standard inner loop if we are not dealing with
02332   ** aggregates
02333   */
02334   if( !isAgg ){
02335     if( selectInnerLoop(pParse, p, pEList, 0, 0, pOrderBy, distinct, eDest,
02336                     iParm, pWInfo->iContinue, pWInfo->iBreak) ){
02337        goto select_end;
02338     }
02339   }
02340 
02341   /* If we are dealing with aggregates, then do the special aggregate
02342   ** processing.  
02343   */
02344   else{
02345     AggExpr *pAgg;
02346     if( pGroupBy ){
02347       int lbl1;
02348       for(i=0; i<pGroupBy->nExpr; i++){
02349         sqliteExprCode(pParse, pGroupBy->a[i].pExpr);
02350       }
02351       sqliteVdbeAddOp(v, OP_MakeKey, pGroupBy->nExpr, 0);
02352       if( pParse->db->file_format>=4 ) sqliteAddKeyType(v, pGroupBy);
02353       lbl1 = sqliteVdbeMakeLabel(v);
02354       sqliteVdbeAddOp(v, OP_AggFocus, 0, lbl1);
02355       for(i=0, pAgg=pParse->aAgg; i<pParse->nAgg; i++, pAgg++){
02356         if( pAgg->isAgg ) continue;
02357         sqliteExprCode(pParse, pAgg->pExpr);
02358         sqliteVdbeAddOp(v, OP_AggSet, 0, i);
02359       }
02360       sqliteVdbeResolveLabel(v, lbl1);
02361     }
02362     for(i=0, pAgg=pParse->aAgg; i<pParse->nAgg; i++, pAgg++){
02363       Expr *pE;
02364       int nExpr;
02365       FuncDef *pDef;
02366       if( !pAgg->isAgg ) continue;
02367       assert( pAgg->pFunc!=0 );
02368       assert( pAgg->pFunc->xStep!=0 );
02369       pDef = pAgg->pFunc;
02370       pE = pAgg->pExpr;
02371       assert( pE!=0 );
02372       assert( pE->op==TK_AGG_FUNCTION );
02373       nExpr = sqliteExprCodeExprList(pParse, pE->pList, pDef->includeTypes);
02374       sqliteVdbeAddOp(v, OP_Integer, i, 0);
02375       sqliteVdbeOp3(v, OP_AggFunc, 0, nExpr, (char*)pDef, P3_POINTER);
02376     }
02377   }
02378 
02379   /* End the database scan loop.
02380   */
02381   sqliteWhereEnd(pWInfo);
02382 
02383   /* If we are processing aggregates, we need to set up a second loop
02384   ** over all of the aggregate values and process them.
02385   */
02386   if( isAgg ){
02387     int endagg = sqliteVdbeMakeLabel(v);
02388     int startagg;
02389     startagg = sqliteVdbeAddOp(v, OP_AggNext, 0, endagg);
02390     pParse->useAgg = 1;
02391     if( pHaving ){
02392       sqliteExprIfFalse(pParse, pHaving, startagg, 1);
02393     }
02394     if( selectInnerLoop(pParse, p, pEList, 0, 0, pOrderBy, distinct, eDest,
02395                     iParm, startagg, endagg) ){
02396       goto select_end;
02397     }
02398     sqliteVdbeAddOp(v, OP_Goto, 0, startagg);
02399     sqliteVdbeResolveLabel(v, endagg);
02400     sqliteVdbeAddOp(v, OP_Noop, 0, 0);
02401     pParse->useAgg = 0;
02402   }
02403 
02404   /* If there is an ORDER BY clause, then we need to sort the results
02405   ** and send them to the callback one by one.
02406   */
02407   if( pOrderBy ){
02408     generateSortTail(p, v, pEList->nExpr, eDest, iParm);
02409   }
02410 
02411   /* If this was a subquery, we have now converted the subquery into a
02412   ** temporary table.  So delete the subquery structure from the parent
02413   ** to prevent this subquery from being evaluated again and to force the
02414   ** the use of the temporary table.
02415   */
02416   if( pParent ){
02417     assert( pParent->pSrc->nSrc>parentTab );
02418     assert( pParent->pSrc->a[parentTab].pSelect==p );
02419     sqliteSelectDelete(p);
02420     pParent->pSrc->a[parentTab].pSelect = 0;
02421   }
02422 
02423   /* The SELECT was successfully coded.   Set the return code to 0
02424   ** to indicate no errors.
02425   */
02426   rc = 0;
02427 
02428   /* Control jumps to here if an error is encountered above, or upon
02429   ** successful coding of the SELECT.
02430   */
02431 select_end:
02432   sqliteAggregateInfoReset(pParse);
02433   return rc;
02434 }