xref: /illumos-gate/usr/src/lib/libsqlite/src/select.c (revision 55fea89dcaa64928bed4327112404dcb3e07b79f)
1 /*
2 ** 2001 September 15
3 **
4 ** The author disclaims copyright to this source code.  In place of
5 ** a legal notice, here is a blessing:
6 **
7 **    May you do good and not evil.
8 **    May you find forgiveness for yourself and forgive others.
9 **    May you share freely, never taking more than you give.
10 **
11 *************************************************************************
12 ** This file contains C code routines that are called by the parser
13 ** to handle SELECT statements in SQLite.
14 **
15 ** $Id: select.c,v 1.161.2.4 2004/07/20 01:45:49 drh Exp $
16 */
17 #include "sqliteInt.h"
18 
19 /*
20 ** Allocate a new Select structure and return a pointer to that
21 ** structure.
22 */
sqliteSelectNew(ExprList * pEList,SrcList * pSrc,Expr * pWhere,ExprList * pGroupBy,Expr * pHaving,ExprList * pOrderBy,int isDistinct,int nLimit,int nOffset)23 Select *sqliteSelectNew(
24   ExprList *pEList,     /* which columns to include in the result */
25   SrcList *pSrc,        /* the FROM clause -- which tables to scan */
26   Expr *pWhere,         /* the WHERE clause */
27   ExprList *pGroupBy,   /* the GROUP BY clause */
28   Expr *pHaving,        /* the HAVING clause */
29   ExprList *pOrderBy,   /* the ORDER BY clause */
30   int isDistinct,       /* true if the DISTINCT keyword is present */
31   int nLimit,           /* LIMIT value.  -1 means not used */
32   int nOffset           /* OFFSET value.  0 means no offset */
33 ){
34   Select *pNew;
35   pNew = sqliteMalloc( sizeof(*pNew) );
36   if( pNew==0 ){
37     sqliteExprListDelete(pEList);
38     sqliteSrcListDelete(pSrc);
39     sqliteExprDelete(pWhere);
40     sqliteExprListDelete(pGroupBy);
41     sqliteExprDelete(pHaving);
42     sqliteExprListDelete(pOrderBy);
43   }else{
44     if( pEList==0 ){
45       pEList = sqliteExprListAppend(0, sqliteExpr(TK_ALL,0,0,0), 0);
46     }
47     pNew->pEList = pEList;
48     pNew->pSrc = pSrc;
49     pNew->pWhere = pWhere;
50     pNew->pGroupBy = pGroupBy;
51     pNew->pHaving = pHaving;
52     pNew->pOrderBy = pOrderBy;
53     pNew->isDistinct = isDistinct;
54     pNew->op = TK_SELECT;
55     pNew->nLimit = nLimit;
56     pNew->nOffset = nOffset;
57     pNew->iLimit = -1;
58     pNew->iOffset = -1;
59   }
60   return pNew;
61 }
62 
63 /*
64 ** Given 1 to 3 identifiers preceeding the JOIN keyword, determine the
65 ** type of join.  Return an integer constant that expresses that type
66 ** in terms of the following bit values:
67 **
68 **     JT_INNER
69 **     JT_OUTER
70 **     JT_NATURAL
71 **     JT_LEFT
72 **     JT_RIGHT
73 **
74 ** A full outer join is the combination of JT_LEFT and JT_RIGHT.
75 **
76 ** If an illegal or unsupported join type is seen, then still return
77 ** a join type, but put an error in the pParse structure.
78 */
sqliteJoinType(Parse * pParse,Token * pA,Token * pB,Token * pC)79 int sqliteJoinType(Parse *pParse, Token *pA, Token *pB, Token *pC){
80   int jointype = 0;
81   Token *apAll[3];
82   Token *p;
83   static struct {
84     const char *zKeyword;
85     int nChar;
86     int code;
87   } keywords[] = {
88     { "natural", 7, JT_NATURAL },
89     { "left",    4, JT_LEFT|JT_OUTER },
90     { "right",   5, JT_RIGHT|JT_OUTER },
91     { "full",    4, JT_LEFT|JT_RIGHT|JT_OUTER },
92     { "outer",   5, JT_OUTER },
93     { "inner",   5, JT_INNER },
94     { "cross",   5, JT_INNER },
95   };
96   int i, j;
97   apAll[0] = pA;
98   apAll[1] = pB;
99   apAll[2] = pC;
100   for(i=0; i<3 && apAll[i]; i++){
101     p = apAll[i];
102     for(j=0; j<sizeof(keywords)/sizeof(keywords[0]); j++){
103       if( p->n==keywords[j].nChar
104           && sqliteStrNICmp(p->z, keywords[j].zKeyword, p->n)==0 ){
105         jointype |= keywords[j].code;
106         break;
107       }
108     }
109     if( j>=sizeof(keywords)/sizeof(keywords[0]) ){
110       jointype |= JT_ERROR;
111       break;
112     }
113   }
114   if(
115      (jointype & (JT_INNER|JT_OUTER))==(JT_INNER|JT_OUTER) ||
116      (jointype & JT_ERROR)!=0
117   ){
118     static Token dummy = { 0, 0 };
119     char *zSp1 = " ", *zSp2 = " ";
120     if( pB==0 ){ pB = &dummy; zSp1 = 0; }
121     if( pC==0 ){ pC = &dummy; zSp2 = 0; }
122     sqliteSetNString(&pParse->zErrMsg, "unknown or unsupported join type: ", 0,
123        pA->z, pA->n, zSp1, 1, pB->z, pB->n, zSp2, 1, pC->z, pC->n, 0);
124     pParse->nErr++;
125     jointype = JT_INNER;
126   }else if( jointype & JT_RIGHT ){
127     sqliteErrorMsg(pParse,
128       "RIGHT and FULL OUTER JOINs are not currently supported");
129     jointype = JT_INNER;
130   }
131   return jointype;
132 }
133 
134 /*
135 ** Return the index of a column in a table.  Return -1 if the column
136 ** is not contained in the table.
137 */
columnIndex(Table * pTab,const char * zCol)138 static int columnIndex(Table *pTab, const char *zCol){
139   int i;
140   for(i=0; i<pTab->nCol; i++){
141     if( sqliteStrICmp(pTab->aCol[i].zName, zCol)==0 ) return i;
142   }
143   return -1;
144 }
145 
146 /*
147 ** Add a term to the WHERE expression in *ppExpr that requires the
148 ** zCol column to be equal in the two tables pTab1 and pTab2.
149 */
addWhereTerm(const char * zCol,const Table * pTab1,const Table * pTab2,Expr ** ppExpr)150 static void addWhereTerm(
151   const char *zCol,        /* Name of the column */
152   const Table *pTab1,      /* First table */
153   const Table *pTab2,      /* Second table */
154   Expr **ppExpr            /* Add the equality term to this expression */
155 ){
156   Token dummy;
157   Expr *pE1a, *pE1b, *pE1c;
158   Expr *pE2a, *pE2b, *pE2c;
159   Expr *pE;
160 
161   dummy.z = zCol;
162   dummy.n = strlen(zCol);
163   dummy.dyn = 0;
164   pE1a = sqliteExpr(TK_ID, 0, 0, &dummy);
165   pE2a = sqliteExpr(TK_ID, 0, 0, &dummy);
166   dummy.z = pTab1->zName;
167   dummy.n = strlen(dummy.z);
168   pE1b = sqliteExpr(TK_ID, 0, 0, &dummy);
169   dummy.z = pTab2->zName;
170   dummy.n = strlen(dummy.z);
171   pE2b = sqliteExpr(TK_ID, 0, 0, &dummy);
172   pE1c = sqliteExpr(TK_DOT, pE1b, pE1a, 0);
173   pE2c = sqliteExpr(TK_DOT, pE2b, pE2a, 0);
174   pE = sqliteExpr(TK_EQ, pE1c, pE2c, 0);
175   ExprSetProperty(pE, EP_FromJoin);
176   if( *ppExpr ){
177     *ppExpr = sqliteExpr(TK_AND, *ppExpr, pE, 0);
178   }else{
179     *ppExpr = pE;
180   }
181 }
182 
183 /*
184 ** Set the EP_FromJoin property on all terms of the given expression.
185 **
186 ** The EP_FromJoin property is used on terms of an expression to tell
187 ** the LEFT OUTER JOIN processing logic that this term is part of the
188 ** join restriction specified in the ON or USING clause and not a part
189 ** of the more general WHERE clause.  These terms are moved over to the
190 ** WHERE clause during join processing but we need to remember that they
191 ** originated in the ON or USING clause.
192 */
setJoinExpr(Expr * p)193 static void setJoinExpr(Expr *p){
194   while( p ){
195     ExprSetProperty(p, EP_FromJoin);
196     setJoinExpr(p->pLeft);
197     p = p->pRight;
198   }
199 }
200 
201 /*
202 ** This routine processes the join information for a SELECT statement.
203 ** ON and USING clauses are converted into extra terms of the WHERE clause.
204 ** NATURAL joins also create extra WHERE clause terms.
205 **
206 ** This routine returns the number of errors encountered.
207 */
sqliteProcessJoin(Parse * pParse,Select * p)208 static int sqliteProcessJoin(Parse *pParse, Select *p){
209   SrcList *pSrc;
210   int i, j;
211   pSrc = p->pSrc;
212   for(i=0; i<pSrc->nSrc-1; i++){
213     struct SrcList_item *pTerm = &pSrc->a[i];
214     struct SrcList_item *pOther = &pSrc->a[i+1];
215 
216     if( pTerm->pTab==0 || pOther->pTab==0 ) continue;
217 
218     /* When the NATURAL keyword is present, add WHERE clause terms for
219     ** every column that the two tables have in common.
220     */
221     if( pTerm->jointype & JT_NATURAL ){
222       Table *pTab;
223       if( pTerm->pOn || pTerm->pUsing ){
224         sqliteErrorMsg(pParse, "a NATURAL join may not have "
225            "an ON or USING clause", 0);
226         return 1;
227       }
228       pTab = pTerm->pTab;
229       for(j=0; j<pTab->nCol; j++){
230         if( columnIndex(pOther->pTab, pTab->aCol[j].zName)>=0 ){
231           addWhereTerm(pTab->aCol[j].zName, pTab, pOther->pTab, &p->pWhere);
232         }
233       }
234     }
235 
236     /* Disallow both ON and USING clauses in the same join
237     */
238     if( pTerm->pOn && pTerm->pUsing ){
239       sqliteErrorMsg(pParse, "cannot have both ON and USING "
240         "clauses in the same join");
241       return 1;
242     }
243 
244     /* Add the ON clause to the end of the WHERE clause, connected by
245     ** and AND operator.
246     */
247     if( pTerm->pOn ){
248       setJoinExpr(pTerm->pOn);
249       if( p->pWhere==0 ){
250         p->pWhere = pTerm->pOn;
251       }else{
252         p->pWhere = sqliteExpr(TK_AND, p->pWhere, pTerm->pOn, 0);
253       }
254       pTerm->pOn = 0;
255     }
256 
257     /* Create extra terms on the WHERE clause for each column named
258     ** in the USING clause.  Example: If the two tables to be joined are
259     ** A and B and the USING clause names X, Y, and Z, then add this
260     ** to the WHERE clause:    A.X=B.X AND A.Y=B.Y AND A.Z=B.Z
261     ** Report an error if any column mentioned in the USING clause is
262     ** not contained in both tables to be joined.
263     */
264     if( pTerm->pUsing ){
265       IdList *pList;
266       int j;
267       assert( i<pSrc->nSrc-1 );
268       pList = pTerm->pUsing;
269       for(j=0; j<pList->nId; j++){
270         if( columnIndex(pTerm->pTab, pList->a[j].zName)<0 ||
271             columnIndex(pOther->pTab, pList->a[j].zName)<0 ){
272           sqliteErrorMsg(pParse, "cannot join using column %s - column "
273             "not present in both tables", pList->a[j].zName);
274           return 1;
275         }
276         addWhereTerm(pList->a[j].zName, pTerm->pTab, pOther->pTab, &p->pWhere);
277       }
278     }
279   }
280   return 0;
281 }
282 
283 /*
284 ** Delete the given Select structure and all of its substructures.
285 */
sqliteSelectDelete(Select * p)286 void sqliteSelectDelete(Select *p){
287   if( p==0 ) return;
288   sqliteExprListDelete(p->pEList);
289   sqliteSrcListDelete(p->pSrc);
290   sqliteExprDelete(p->pWhere);
291   sqliteExprListDelete(p->pGroupBy);
292   sqliteExprDelete(p->pHaving);
293   sqliteExprListDelete(p->pOrderBy);
294   sqliteSelectDelete(p->pPrior);
295   sqliteFree(p->zSelect);
296   sqliteFree(p);
297 }
298 
299 /*
300 ** Delete the aggregate information from the parse structure.
301 */
sqliteAggregateInfoReset(Parse * pParse)302 static void sqliteAggregateInfoReset(Parse *pParse){
303   sqliteFree(pParse->aAgg);
304   pParse->aAgg = 0;
305   pParse->nAgg = 0;
306   pParse->useAgg = 0;
307 }
308 
309 /*
310 ** Insert code into "v" that will push the record on the top of the
311 ** stack into the sorter.
312 */
pushOntoSorter(Parse * pParse,Vdbe * v,ExprList * pOrderBy)313 static void pushOntoSorter(Parse *pParse, Vdbe *v, ExprList *pOrderBy){
314   char *zSortOrder;
315   int i;
316   zSortOrder = sqliteMalloc( pOrderBy->nExpr + 1 );
317   if( zSortOrder==0 ) return;
318   for(i=0; i<pOrderBy->nExpr; i++){
319     int order = pOrderBy->a[i].sortOrder;
320     int type;
321     int c;
322     if( (order & SQLITE_SO_TYPEMASK)==SQLITE_SO_TEXT ){
323       type = SQLITE_SO_TEXT;
324     }else if( (order & SQLITE_SO_TYPEMASK)==SQLITE_SO_NUM ){
325       type = SQLITE_SO_NUM;
326     }else if( pParse->db->file_format>=4 ){
327       type = sqliteExprType(pOrderBy->a[i].pExpr);
328     }else{
329       type = SQLITE_SO_NUM;
330     }
331     if( (order & SQLITE_SO_DIRMASK)==SQLITE_SO_ASC ){
332       c = type==SQLITE_SO_TEXT ? 'A' : '+';
333     }else{
334       c = type==SQLITE_SO_TEXT ? 'D' : '-';
335     }
336     zSortOrder[i] = c;
337     sqliteExprCode(pParse, pOrderBy->a[i].pExpr);
338   }
339   zSortOrder[pOrderBy->nExpr] = 0;
340   sqliteVdbeOp3(v, OP_SortMakeKey, pOrderBy->nExpr, 0, zSortOrder, P3_DYNAMIC);
341   sqliteVdbeAddOp(v, OP_SortPut, 0, 0);
342 }
343 
344 /*
345 ** This routine adds a P3 argument to the last VDBE opcode that was
346 ** inserted. The P3 argument added is a string suitable for the
347 ** OP_MakeKey or OP_MakeIdxKey opcodes.  The string consists of
348 ** characters 't' or 'n' depending on whether or not the various
349 ** fields of the key to be generated should be treated as numeric
350 ** or as text.  See the OP_MakeKey and OP_MakeIdxKey opcode
351 ** documentation for additional information about the P3 string.
352 ** See also the sqliteAddIdxKeyType() routine.
353 */
sqliteAddKeyType(Vdbe * v,ExprList * pEList)354 void sqliteAddKeyType(Vdbe *v, ExprList *pEList){
355   int nColumn = pEList->nExpr;
356   char *zType = sqliteMalloc( nColumn+1 );
357   int i;
358   if( zType==0 ) return;
359   for(i=0; i<nColumn; i++){
360     zType[i] = sqliteExprType(pEList->a[i].pExpr)==SQLITE_SO_NUM ? 'n' : 't';
361   }
362   zType[i] = 0;
363   sqliteVdbeChangeP3(v, -1, zType, P3_DYNAMIC);
364 }
365 
366 /*
367 ** Add code to implement the OFFSET and LIMIT
368 */
codeLimiter(Vdbe * v,Select * p,int iContinue,int iBreak,int nPop)369 static void codeLimiter(
370   Vdbe *v,          /* Generate code into this VM */
371   Select *p,        /* The SELECT statement being coded */
372   int iContinue,    /* Jump here to skip the current record */
373   int iBreak,       /* Jump here to end the loop */
374   int nPop          /* Number of times to pop stack when jumping */
375 ){
376   if( p->iOffset>=0 ){
377     int addr = sqliteVdbeCurrentAddr(v) + 2;
378     if( nPop>0 ) addr++;
379     sqliteVdbeAddOp(v, OP_MemIncr, p->iOffset, addr);
380     if( nPop>0 ){
381       sqliteVdbeAddOp(v, OP_Pop, nPop, 0);
382     }
383     sqliteVdbeAddOp(v, OP_Goto, 0, iContinue);
384   }
385   if( p->iLimit>=0 ){
386     sqliteVdbeAddOp(v, OP_MemIncr, p->iLimit, iBreak);
387   }
388 }
389 
390 /*
391 ** This routine generates the code for the inside of the inner loop
392 ** of a SELECT.
393 **
394 ** If srcTab and nColumn are both zero, then the pEList expressions
395 ** are evaluated in order to get the data for this row.  If nColumn>0
396 ** then data is pulled from srcTab and pEList is used only to get the
397 ** datatypes for each column.
398 */
selectInnerLoop(Parse * pParse,Select * p,ExprList * pEList,int srcTab,int nColumn,ExprList * pOrderBy,int distinct,int eDest,int iParm,int iContinue,int iBreak)399 static int selectInnerLoop(
400   Parse *pParse,          /* The parser context */
401   Select *p,              /* The complete select statement being coded */
402   ExprList *pEList,       /* List of values being extracted */
403   int srcTab,             /* Pull data from this table */
404   int nColumn,            /* Number of columns in the source table */
405   ExprList *pOrderBy,     /* If not NULL, sort results using this key */
406   int distinct,           /* If >=0, make sure results are distinct */
407   int eDest,              /* How to dispose of the results */
408   int iParm,              /* An argument to the disposal method */
409   int iContinue,          /* Jump here to continue with next row */
410   int iBreak              /* Jump here to break out of the inner loop */
411 ){
412   Vdbe *v = pParse->pVdbe;
413   int i;
414   int hasDistinct;        /* True if the DISTINCT keyword is present */
415 
416   if( v==0 ) return 0;
417   assert( pEList!=0 );
418 
419   /* If there was a LIMIT clause on the SELECT statement, then do the check
420   ** to see if this row should be output.
421   */
422   hasDistinct = distinct>=0 && pEList && pEList->nExpr>0;
423   if( pOrderBy==0 && !hasDistinct ){
424     codeLimiter(v, p, iContinue, iBreak, 0);
425   }
426 
427   /* Pull the requested columns.
428   */
429   if( nColumn>0 ){
430     for(i=0; i<nColumn; i++){
431       sqliteVdbeAddOp(v, OP_Column, srcTab, i);
432     }
433   }else{
434     nColumn = pEList->nExpr;
435     for(i=0; i<pEList->nExpr; i++){
436       sqliteExprCode(pParse, pEList->a[i].pExpr);
437     }
438   }
439 
440   /* If the DISTINCT keyword was present on the SELECT statement
441   ** and this row has been seen before, then do not make this row
442   ** part of the result.
443   */
444   if( hasDistinct ){
445 #if NULL_ALWAYS_DISTINCT
446     sqliteVdbeAddOp(v, OP_IsNull, -pEList->nExpr, sqliteVdbeCurrentAddr(v)+7);
447 #endif
448     sqliteVdbeAddOp(v, OP_MakeKey, pEList->nExpr, 1);
449     if( pParse->db->file_format>=4 ) sqliteAddKeyType(v, pEList);
450     sqliteVdbeAddOp(v, OP_Distinct, distinct, sqliteVdbeCurrentAddr(v)+3);
451     sqliteVdbeAddOp(v, OP_Pop, pEList->nExpr+1, 0);
452     sqliteVdbeAddOp(v, OP_Goto, 0, iContinue);
453     sqliteVdbeAddOp(v, OP_String, 0, 0);
454     sqliteVdbeAddOp(v, OP_PutStrKey, distinct, 0);
455     if( pOrderBy==0 ){
456       codeLimiter(v, p, iContinue, iBreak, nColumn);
457     }
458   }
459 
460   switch( eDest ){
461     /* In this mode, write each query result to the key of the temporary
462     ** table iParm.
463     */
464     case SRT_Union: {
465       sqliteVdbeAddOp(v, OP_MakeRecord, nColumn, NULL_ALWAYS_DISTINCT);
466       sqliteVdbeAddOp(v, OP_String, 0, 0);
467       sqliteVdbeAddOp(v, OP_PutStrKey, iParm, 0);
468       break;
469     }
470 
471     /* Store the result as data using a unique key.
472     */
473     case SRT_Table:
474     case SRT_TempTable: {
475       sqliteVdbeAddOp(v, OP_MakeRecord, nColumn, 0);
476       if( pOrderBy ){
477         pushOntoSorter(pParse, v, pOrderBy);
478       }else{
479         sqliteVdbeAddOp(v, OP_NewRecno, iParm, 0);
480         sqliteVdbeAddOp(v, OP_Pull, 1, 0);
481         sqliteVdbeAddOp(v, OP_PutIntKey, iParm, 0);
482       }
483       break;
484     }
485 
486     /* Construct a record from the query result, but instead of
487     ** saving that record, use it as a key to delete elements from
488     ** the temporary table iParm.
489     */
490     case SRT_Except: {
491       int addr;
492       addr = sqliteVdbeAddOp(v, OP_MakeRecord, nColumn, NULL_ALWAYS_DISTINCT);
493       sqliteVdbeAddOp(v, OP_NotFound, iParm, addr+3);
494       sqliteVdbeAddOp(v, OP_Delete, iParm, 0);
495       break;
496     }
497 
498     /* If we are creating a set for an "expr IN (SELECT ...)" construct,
499     ** then there should be a single item on the stack.  Write this
500     ** item into the set table with bogus data.
501     */
502     case SRT_Set: {
503       int addr1 = sqliteVdbeCurrentAddr(v);
504       int addr2;
505       assert( nColumn==1 );
506       sqliteVdbeAddOp(v, OP_NotNull, -1, addr1+3);
507       sqliteVdbeAddOp(v, OP_Pop, 1, 0);
508       addr2 = sqliteVdbeAddOp(v, OP_Goto, 0, 0);
509       if( pOrderBy ){
510         pushOntoSorter(pParse, v, pOrderBy);
511       }else{
512         sqliteVdbeAddOp(v, OP_String, 0, 0);
513         sqliteVdbeAddOp(v, OP_PutStrKey, iParm, 0);
514       }
515       sqliteVdbeChangeP2(v, addr2, sqliteVdbeCurrentAddr(v));
516       break;
517     }
518 
519     /* If this is a scalar select that is part of an expression, then
520     ** store the results in the appropriate memory cell and break out
521     ** of the scan loop.
522     */
523     case SRT_Mem: {
524       assert( nColumn==1 );
525       if( pOrderBy ){
526         pushOntoSorter(pParse, v, pOrderBy);
527       }else{
528         sqliteVdbeAddOp(v, OP_MemStore, iParm, 1);
529         sqliteVdbeAddOp(v, OP_Goto, 0, iBreak);
530       }
531       break;
532     }
533 
534     /* Send the data to the callback function.
535     */
536     case SRT_Callback:
537     case SRT_Sorter: {
538       if( pOrderBy ){
539         sqliteVdbeAddOp(v, OP_SortMakeRec, nColumn, 0);
540         pushOntoSorter(pParse, v, pOrderBy);
541       }else{
542         assert( eDest==SRT_Callback );
543         sqliteVdbeAddOp(v, OP_Callback, nColumn, 0);
544       }
545       break;
546     }
547 
548     /* Invoke a subroutine to handle the results.  The subroutine itself
549     ** is responsible for popping the results off of the stack.
550     */
551     case SRT_Subroutine: {
552       if( pOrderBy ){
553         sqliteVdbeAddOp(v, OP_MakeRecord, nColumn, 0);
554         pushOntoSorter(pParse, v, pOrderBy);
555       }else{
556         sqliteVdbeAddOp(v, OP_Gosub, 0, iParm);
557       }
558       break;
559     }
560 
561     /* Discard the results.  This is used for SELECT statements inside
562     ** the body of a TRIGGER.  The purpose of such selects is to call
563     ** user-defined functions that have side effects.  We do not care
564     ** about the actual results of the select.
565     */
566     default: {
567       assert( eDest==SRT_Discard );
568       sqliteVdbeAddOp(v, OP_Pop, nColumn, 0);
569       break;
570     }
571   }
572   return 0;
573 }
574 
575 /*
576 ** If the inner loop was generated using a non-null pOrderBy argument,
577 ** then the results were placed in a sorter.  After the loop is terminated
578 ** we need to run the sorter and output the results.  The following
579 ** routine generates the code needed to do that.
580 */
generateSortTail(Select * p,Vdbe * v,int nColumn,int eDest,int iParm)581 static void generateSortTail(
582   Select *p,       /* The SELECT statement */
583   Vdbe *v,         /* Generate code into this VDBE */
584   int nColumn,     /* Number of columns of data */
585   int eDest,       /* Write the sorted results here */
586   int iParm        /* Optional parameter associated with eDest */
587 ){
588   int end1 = sqliteVdbeMakeLabel(v);
589   int end2 = sqliteVdbeMakeLabel(v);
590   int addr;
591   if( eDest==SRT_Sorter ) return;
592   sqliteVdbeAddOp(v, OP_Sort, 0, 0);
593   addr = sqliteVdbeAddOp(v, OP_SortNext, 0, end1);
594   codeLimiter(v, p, addr, end2, 1);
595   switch( eDest ){
596     case SRT_Callback: {
597       sqliteVdbeAddOp(v, OP_SortCallback, nColumn, 0);
598       break;
599     }
600     case SRT_Table:
601     case SRT_TempTable: {
602       sqliteVdbeAddOp(v, OP_NewRecno, iParm, 0);
603       sqliteVdbeAddOp(v, OP_Pull, 1, 0);
604       sqliteVdbeAddOp(v, OP_PutIntKey, iParm, 0);
605       break;
606     }
607     case SRT_Set: {
608       assert( nColumn==1 );
609       sqliteVdbeAddOp(v, OP_NotNull, -1, sqliteVdbeCurrentAddr(v)+3);
610       sqliteVdbeAddOp(v, OP_Pop, 1, 0);
611       sqliteVdbeAddOp(v, OP_Goto, 0, sqliteVdbeCurrentAddr(v)+3);
612       sqliteVdbeAddOp(v, OP_String, 0, 0);
613       sqliteVdbeAddOp(v, OP_PutStrKey, iParm, 0);
614       break;
615     }
616     case SRT_Mem: {
617       assert( nColumn==1 );
618       sqliteVdbeAddOp(v, OP_MemStore, iParm, 1);
619       sqliteVdbeAddOp(v, OP_Goto, 0, end1);
620       break;
621     }
622     case SRT_Subroutine: {
623       int i;
624       for(i=0; i<nColumn; i++){
625         sqliteVdbeAddOp(v, OP_Column, -1-i, i);
626       }
627       sqliteVdbeAddOp(v, OP_Gosub, 0, iParm);
628       sqliteVdbeAddOp(v, OP_Pop, 1, 0);
629       break;
630     }
631     default: {
632       /* Do nothing */
633       break;
634     }
635   }
636   sqliteVdbeAddOp(v, OP_Goto, 0, addr);
637   sqliteVdbeResolveLabel(v, end2);
638   sqliteVdbeAddOp(v, OP_Pop, 1, 0);
639   sqliteVdbeResolveLabel(v, end1);
640   sqliteVdbeAddOp(v, OP_SortReset, 0, 0);
641 }
642 
643 /*
644 ** Generate code that will tell the VDBE the datatypes of
645 ** columns in the result set.
646 **
647 ** This routine only generates code if the "PRAGMA show_datatypes=on"
648 ** has been executed.  The datatypes are reported out in the azCol
649 ** parameter to the callback function.  The first N azCol[] entries
650 ** are the names of the columns, and the second N entries are the
651 ** datatypes for the columns.
652 **
653 ** The "datatype" for a result that is a column of a type is the
654 ** datatype definition extracted from the CREATE TABLE statement.
655 ** The datatype for an expression is either TEXT or NUMERIC.  The
656 ** datatype for a ROWID field is INTEGER.
657 */
generateColumnTypes(Parse * pParse,SrcList * pTabList,ExprList * pEList)658 static void generateColumnTypes(
659   Parse *pParse,      /* Parser context */
660   SrcList *pTabList,  /* List of tables */
661   ExprList *pEList    /* Expressions defining the result set */
662 ){
663   Vdbe *v = pParse->pVdbe;
664   int i, j;
665   for(i=0; i<pEList->nExpr; i++){
666     Expr *p = pEList->a[i].pExpr;
667     char *zType = 0;
668     if( p==0 ) continue;
669     if( p->op==TK_COLUMN && pTabList ){
670       Table *pTab;
671       int iCol = p->iColumn;
672       for(j=0; j<pTabList->nSrc && pTabList->a[j].iCursor!=p->iTable; j++){}
673       assert( j<pTabList->nSrc );
674       pTab = pTabList->a[j].pTab;
675       if( iCol<0 ) iCol = pTab->iPKey;
676       assert( iCol==-1 || (iCol>=0 && iCol<pTab->nCol) );
677       if( iCol<0 ){
678         zType = "INTEGER";
679       }else{
680         zType = pTab->aCol[iCol].zType;
681       }
682     }else{
683       if( sqliteExprType(p)==SQLITE_SO_TEXT ){
684         zType = "TEXT";
685       }else{
686         zType = "NUMERIC";
687       }
688     }
689     sqliteVdbeOp3(v, OP_ColumnName, i + pEList->nExpr, 0, zType, 0);
690   }
691 }
692 
693 /*
694 ** Generate code that will tell the VDBE the names of columns
695 ** in the result set.  This information is used to provide the
696 ** azCol[] values in the callback.
697 */
generateColumnNames(Parse * pParse,SrcList * pTabList,ExprList * pEList)698 static void generateColumnNames(
699   Parse *pParse,      /* Parser context */
700   SrcList *pTabList,  /* List of tables */
701   ExprList *pEList    /* Expressions defining the result set */
702 ){
703   Vdbe *v = pParse->pVdbe;
704   int i, j;
705   sqlite *db = pParse->db;
706   int fullNames, shortNames;
707 
708   assert( v!=0 );
709   if( pParse->colNamesSet || v==0 || sqlite_malloc_failed ) return;
710   pParse->colNamesSet = 1;
711   fullNames = (db->flags & SQLITE_FullColNames)!=0;
712   shortNames = (db->flags & SQLITE_ShortColNames)!=0;
713   for(i=0; i<pEList->nExpr; i++){
714     Expr *p;
715     int p2 = i==pEList->nExpr-1;
716     p = pEList->a[i].pExpr;
717     if( p==0 ) continue;
718     if( pEList->a[i].zName ){
719       char *zName = pEList->a[i].zName;
720       sqliteVdbeOp3(v, OP_ColumnName, i, p2, zName, 0);
721       continue;
722     }
723     if( p->op==TK_COLUMN && pTabList ){
724       Table *pTab;
725       char *zCol;
726       int iCol = p->iColumn;
727       for(j=0; j<pTabList->nSrc && pTabList->a[j].iCursor!=p->iTable; j++){}
728       assert( j<pTabList->nSrc );
729       pTab = pTabList->a[j].pTab;
730       if( iCol<0 ) iCol = pTab->iPKey;
731       assert( iCol==-1 || (iCol>=0 && iCol<pTab->nCol) );
732       if( iCol<0 ){
733         zCol = "_ROWID_";
734       }else{
735         zCol = pTab->aCol[iCol].zName;
736       }
737       if( !shortNames && !fullNames && p->span.z && p->span.z[0] ){
738         int addr = sqliteVdbeOp3(v,OP_ColumnName, i, p2, p->span.z, p->span.n);
739         sqliteVdbeCompressSpace(v, addr);
740       }else if( fullNames || (!shortNames && pTabList->nSrc>1) ){
741         char *zName = 0;
742         char *zTab;
743 
744         zTab = pTabList->a[j].zAlias;
745         if( fullNames || zTab==0 ) zTab = pTab->zName;
746         sqliteSetString(&zName, zTab, ".", zCol, 0);
747         sqliteVdbeOp3(v, OP_ColumnName, i, p2, zName, P3_DYNAMIC);
748       }else{
749         sqliteVdbeOp3(v, OP_ColumnName, i, p2, zCol, 0);
750       }
751     }else if( p->span.z && p->span.z[0] ){
752       int addr = sqliteVdbeOp3(v,OP_ColumnName, i, p2, p->span.z, p->span.n);
753       sqliteVdbeCompressSpace(v, addr);
754     }else{
755       char zName[30];
756       assert( p->op!=TK_COLUMN || pTabList==0 );
757       sprintf(zName, "column%d", i+1);
758       sqliteVdbeOp3(v, OP_ColumnName, i, p2, zName, 0);
759     }
760   }
761 }
762 
763 /*
764 ** Name of the connection operator, used for error messages.
765 */
selectOpName(int id)766 static const char *selectOpName(int id){
767   char *z;
768   switch( id ){
769     case TK_ALL:       z = "UNION ALL";   break;
770     case TK_INTERSECT: z = "INTERSECT";   break;
771     case TK_EXCEPT:    z = "EXCEPT";      break;
772     default:           z = "UNION";       break;
773   }
774   return z;
775 }
776 
777 /*
778 ** Forward declaration
779 */
780 static int fillInColumnList(Parse*, Select*);
781 
782 /*
783 ** Given a SELECT statement, generate a Table structure that describes
784 ** the result set of that SELECT.
785 */
sqliteResultSetOfSelect(Parse * pParse,char * zTabName,Select * pSelect)786 Table *sqliteResultSetOfSelect(Parse *pParse, char *zTabName, Select *pSelect){
787   Table *pTab;
788   int i, j;
789   ExprList *pEList;
790   Column *aCol;
791 
792   if( fillInColumnList(pParse, pSelect) ){
793     return 0;
794   }
795   pTab = sqliteMalloc( sizeof(Table) );
796   if( pTab==0 ){
797     return 0;
798   }
799   pTab->zName = zTabName ? sqliteStrDup(zTabName) : 0;
800   pEList = pSelect->pEList;
801   pTab->nCol = pEList->nExpr;
802   assert( pTab->nCol>0 );
803   pTab->aCol = aCol = sqliteMalloc( sizeof(pTab->aCol[0])*pTab->nCol );
804   for(i=0; i<pTab->nCol; i++){
805     Expr *p, *pR;
806     if( pEList->a[i].zName ){
807       aCol[i].zName = sqliteStrDup(pEList->a[i].zName);
808     }else if( (p=pEList->a[i].pExpr)->op==TK_DOT
809                && (pR=p->pRight)!=0 && pR->token.z && pR->token.z[0] ){
810       int cnt;
811       sqliteSetNString(&aCol[i].zName, pR->token.z, pR->token.n, 0);
812       for(j=cnt=0; j<i; j++){
813         if( sqliteStrICmp(aCol[j].zName, aCol[i].zName)==0 ){
814           int n;
815           char zBuf[30];
816           sprintf(zBuf,"_%d",++cnt);
817           n = strlen(zBuf);
818           sqliteSetNString(&aCol[i].zName, pR->token.z, pR->token.n, zBuf, n,0);
819           j = -1;
820         }
821       }
822     }else if( p->span.z && p->span.z[0] ){
823       sqliteSetNString(&pTab->aCol[i].zName, p->span.z, p->span.n, 0);
824     }else{
825       char zBuf[30];
826       sprintf(zBuf, "column%d", i+1);
827       aCol[i].zName = sqliteStrDup(zBuf);
828     }
829     sqliteDequote(aCol[i].zName);
830   }
831   pTab->iPKey = -1;
832   return pTab;
833 }
834 
835 /*
836 ** For the given SELECT statement, do three things.
837 **
838 **    (1)  Fill in the pTabList->a[].pTab fields in the SrcList that
839 **         defines the set of tables that should be scanned.  For views,
840 **         fill pTabList->a[].pSelect with a copy of the SELECT statement
841 **         that implements the view.  A copy is made of the view's SELECT
842 **         statement so that we can freely modify or delete that statement
843 **         without worrying about messing up the presistent representation
844 **         of the view.
845 **
846 **    (2)  Add terms to the WHERE clause to accomodate the NATURAL keyword
847 **         on joins and the ON and USING clause of joins.
848 **
849 **    (3)  Scan the list of columns in the result set (pEList) looking
850 **         for instances of the "*" operator or the TABLE.* operator.
851 **         If found, expand each "*" to be every column in every table
852 **         and TABLE.* to be every column in TABLE.
853 **
854 ** Return 0 on success.  If there are problems, leave an error message
855 ** in pParse and return non-zero.
856 */
fillInColumnList(Parse * pParse,Select * p)857 static int fillInColumnList(Parse *pParse, Select *p){
858   int i, j, k, rc;
859   SrcList *pTabList;
860   ExprList *pEList;
861   Table *pTab;
862 
863   if( p==0 || p->pSrc==0 ) return 1;
864   pTabList = p->pSrc;
865   pEList = p->pEList;
866 
867   /* Look up every table in the table list.
868   */
869   for(i=0; i<pTabList->nSrc; i++){
870     if( pTabList->a[i].pTab ){
871       /* This routine has run before!  No need to continue */
872       return 0;
873     }
874     if( pTabList->a[i].zName==0 ){
875       /* A sub-query in the FROM clause of a SELECT */
876       assert( pTabList->a[i].pSelect!=0 );
877       if( pTabList->a[i].zAlias==0 ){
878         char zFakeName[60];
879         sprintf(zFakeName, "sqlite_subquery_%p_",
880            (void*)pTabList->a[i].pSelect);
881         sqliteSetString(&pTabList->a[i].zAlias, zFakeName, 0);
882       }
883       pTabList->a[i].pTab = pTab =
884         sqliteResultSetOfSelect(pParse, pTabList->a[i].zAlias,
885                                         pTabList->a[i].pSelect);
886       if( pTab==0 ){
887         return 1;
888       }
889       /* The isTransient flag indicates that the Table structure has been
890       ** dynamically allocated and may be freed at any time.  In other words,
891       ** pTab is not pointing to a persistent table structure that defines
892       ** part of the schema. */
893       pTab->isTransient = 1;
894     }else{
895       /* An ordinary table or view name in the FROM clause */
896       pTabList->a[i].pTab = pTab =
897         sqliteLocateTable(pParse,pTabList->a[i].zName,pTabList->a[i].zDatabase);
898       if( pTab==0 ){
899         return 1;
900       }
901       if( pTab->pSelect ){
902         /* We reach here if the named table is a really a view */
903         if( sqliteViewGetColumnNames(pParse, pTab) ){
904           return 1;
905         }
906         /* If pTabList->a[i].pSelect!=0 it means we are dealing with a
907         ** view within a view.  The SELECT structure has already been
908         ** copied by the outer view so we can skip the copy step here
909         ** in the inner view.
910         */
911         if( pTabList->a[i].pSelect==0 ){
912           pTabList->a[i].pSelect = sqliteSelectDup(pTab->pSelect);
913         }
914       }
915     }
916   }
917 
918   /* Process NATURAL keywords, and ON and USING clauses of joins.
919   */
920   if( sqliteProcessJoin(pParse, p) ) return 1;
921 
922   /* For every "*" that occurs in the column list, insert the names of
923   ** all columns in all tables.  And for every TABLE.* insert the names
924   ** of all columns in TABLE.  The parser inserted a special expression
925   ** with the TK_ALL operator for each "*" that it found in the column list.
926   ** The following code just has to locate the TK_ALL expressions and expand
927   ** each one to the list of all columns in all tables.
928   **
929   ** The first loop just checks to see if there are any "*" operators
930   ** that need expanding.
931   */
932   for(k=0; k<pEList->nExpr; k++){
933     Expr *pE = pEList->a[k].pExpr;
934     if( pE->op==TK_ALL ) break;
935     if( pE->op==TK_DOT && pE->pRight && pE->pRight->op==TK_ALL
936          && pE->pLeft && pE->pLeft->op==TK_ID ) break;
937   }
938   rc = 0;
939   if( k<pEList->nExpr ){
940     /*
941     ** If we get here it means the result set contains one or more "*"
942     ** operators that need to be expanded.  Loop through each expression
943     ** in the result set and expand them one by one.
944     */
945     struct ExprList_item *a = pEList->a;
946     ExprList *pNew = 0;
947     for(k=0; k<pEList->nExpr; k++){
948       Expr *pE = a[k].pExpr;
949       if( pE->op!=TK_ALL &&
950            (pE->op!=TK_DOT || pE->pRight==0 || pE->pRight->op!=TK_ALL) ){
951         /* This particular expression does not need to be expanded.
952         */
953         pNew = sqliteExprListAppend(pNew, a[k].pExpr, 0);
954         pNew->a[pNew->nExpr-1].zName = a[k].zName;
955         a[k].pExpr = 0;
956         a[k].zName = 0;
957       }else{
958         /* This expression is a "*" or a "TABLE.*" and needs to be
959         ** expanded. */
960         int tableSeen = 0;      /* Set to 1 when TABLE matches */
961         char *zTName;           /* text of name of TABLE */
962         if( pE->op==TK_DOT && pE->pLeft ){
963           zTName = sqliteTableNameFromToken(&pE->pLeft->token);
964         }else{
965           zTName = 0;
966         }
967         for(i=0; i<pTabList->nSrc; i++){
968           Table *pTab = pTabList->a[i].pTab;
969           char *zTabName = pTabList->a[i].zAlias;
970           if( zTabName==0 || zTabName[0]==0 ){
971             zTabName = pTab->zName;
972           }
973           if( zTName && (zTabName==0 || zTabName[0]==0 ||
974                  sqliteStrICmp(zTName, zTabName)!=0) ){
975             continue;
976           }
977           tableSeen = 1;
978           for(j=0; j<pTab->nCol; j++){
979             Expr *pExpr, *pLeft, *pRight;
980             char *zName = pTab->aCol[j].zName;
981 
982             if( i>0 && (pTabList->a[i-1].jointype & JT_NATURAL)!=0 &&
983                 columnIndex(pTabList->a[i-1].pTab, zName)>=0 ){
984               /* In a NATURAL join, omit the join columns from the
985               ** table on the right */
986               continue;
987             }
988             if( i>0 && sqliteIdListIndex(pTabList->a[i-1].pUsing, zName)>=0 ){
989               /* In a join with a USING clause, omit columns in the
990               ** using clause from the table on the right. */
991               continue;
992             }
993             pRight = sqliteExpr(TK_ID, 0, 0, 0);
994             if( pRight==0 ) break;
995             pRight->token.z = zName;
996             pRight->token.n = strlen(zName);
997             pRight->token.dyn = 0;
998             if( zTabName && pTabList->nSrc>1 ){
999               pLeft = sqliteExpr(TK_ID, 0, 0, 0);
1000               pExpr = sqliteExpr(TK_DOT, pLeft, pRight, 0);
1001               if( pExpr==0 ) break;
1002               pLeft->token.z = zTabName;
1003               pLeft->token.n = strlen(zTabName);
1004               pLeft->token.dyn = 0;
1005               sqliteSetString((char**)&pExpr->span.z, zTabName, ".", zName, 0);
1006               pExpr->span.n = strlen(pExpr->span.z);
1007               pExpr->span.dyn = 1;
1008               pExpr->token.z = 0;
1009               pExpr->token.n = 0;
1010               pExpr->token.dyn = 0;
1011             }else{
1012               pExpr = pRight;
1013               pExpr->span = pExpr->token;
1014             }
1015             pNew = sqliteExprListAppend(pNew, pExpr, 0);
1016           }
1017         }
1018         if( !tableSeen ){
1019           if( zTName ){
1020             sqliteErrorMsg(pParse, "no such table: %s", zTName);
1021           }else{
1022             sqliteErrorMsg(pParse, "no tables specified");
1023           }
1024           rc = 1;
1025         }
1026         sqliteFree(zTName);
1027       }
1028     }
1029     sqliteExprListDelete(pEList);
1030     p->pEList = pNew;
1031   }
1032   return rc;
1033 }
1034 
1035 /*
1036 ** This routine recursively unlinks the Select.pSrc.a[].pTab pointers
1037 ** in a select structure.  It just sets the pointers to NULL.  This
1038 ** routine is recursive in the sense that if the Select.pSrc.a[].pSelect
1039 ** pointer is not NULL, this routine is called recursively on that pointer.
1040 **
1041 ** This routine is called on the Select structure that defines a
1042 ** VIEW in order to undo any bindings to tables.  This is necessary
1043 ** because those tables might be DROPed by a subsequent SQL command.
1044 ** If the bindings are not removed, then the Select.pSrc->a[].pTab field
1045 ** will be left pointing to a deallocated Table structure after the
1046 ** DROP and a coredump will occur the next time the VIEW is used.
1047 */
sqliteSelectUnbind(Select * p)1048 void sqliteSelectUnbind(Select *p){
1049   int i;
1050   SrcList *pSrc = p->pSrc;
1051   Table *pTab;
1052   if( p==0 ) return;
1053   for(i=0; i<pSrc->nSrc; i++){
1054     if( (pTab = pSrc->a[i].pTab)!=0 ){
1055       if( pTab->isTransient ){
1056         sqliteDeleteTable(0, pTab);
1057       }
1058       pSrc->a[i].pTab = 0;
1059       if( pSrc->a[i].pSelect ){
1060         sqliteSelectUnbind(pSrc->a[i].pSelect);
1061       }
1062     }
1063   }
1064 }
1065 
1066 /*
1067 ** This routine associates entries in an ORDER BY expression list with
1068 ** columns in a result.  For each ORDER BY expression, the opcode of
1069 ** the top-level node is changed to TK_COLUMN and the iColumn value of
1070 ** the top-level node is filled in with column number and the iTable
1071 ** value of the top-level node is filled with iTable parameter.
1072 **
1073 ** If there are prior SELECT clauses, they are processed first.  A match
1074 ** in an earlier SELECT takes precedence over a later SELECT.
1075 **
1076 ** Any entry that does not match is flagged as an error.  The number
1077 ** of errors is returned.
1078 **
1079 ** This routine does NOT correctly initialize the Expr.dataType  field
1080 ** of the ORDER BY expressions.  The multiSelectSortOrder() routine
1081 ** must be called to do that after the individual select statements
1082 ** have all been analyzed.  This routine is unable to compute Expr.dataType
1083 ** because it must be called before the individual select statements
1084 ** have been analyzed.
1085 */
matchOrderbyToColumn(Parse * pParse,Select * pSelect,ExprList * pOrderBy,int iTable,int mustComplete)1086 static int matchOrderbyToColumn(
1087   Parse *pParse,          /* A place to leave error messages */
1088   Select *pSelect,        /* Match to result columns of this SELECT */
1089   ExprList *pOrderBy,     /* The ORDER BY values to match against columns */
1090   int iTable,             /* Insert this value in iTable */
1091   int mustComplete        /* If TRUE all ORDER BYs must match */
1092 ){
1093   int nErr = 0;
1094   int i, j;
1095   ExprList *pEList;
1096 
1097   if( pSelect==0 || pOrderBy==0 ) return 1;
1098   if( mustComplete ){
1099     for(i=0; i<pOrderBy->nExpr; i++){ pOrderBy->a[i].done = 0; }
1100   }
1101   if( fillInColumnList(pParse, pSelect) ){
1102     return 1;
1103   }
1104   if( pSelect->pPrior ){
1105     if( matchOrderbyToColumn(pParse, pSelect->pPrior, pOrderBy, iTable, 0) ){
1106       return 1;
1107     }
1108   }
1109   pEList = pSelect->pEList;
1110   for(i=0; i<pOrderBy->nExpr; i++){
1111     Expr *pE = pOrderBy->a[i].pExpr;
1112     int iCol = -1;
1113     if( pOrderBy->a[i].done ) continue;
1114     if( sqliteExprIsInteger(pE, &iCol) ){
1115       if( iCol<=0 || iCol>pEList->nExpr ){
1116         sqliteErrorMsg(pParse,
1117           "ORDER BY position %d should be between 1 and %d",
1118           iCol, pEList->nExpr);
1119         nErr++;
1120         break;
1121       }
1122       if( !mustComplete ) continue;
1123       iCol--;
1124     }
1125     for(j=0; iCol<0 && j<pEList->nExpr; j++){
1126       if( pEList->a[j].zName && (pE->op==TK_ID || pE->op==TK_STRING) ){
1127         char *zName, *zLabel;
1128         zName = pEList->a[j].zName;
1129         assert( pE->token.z );
1130         zLabel = sqliteStrNDup(pE->token.z, pE->token.n);
1131         sqliteDequote(zLabel);
1132         if( sqliteStrICmp(zName, zLabel)==0 ){
1133           iCol = j;
1134         }
1135         sqliteFree(zLabel);
1136       }
1137       if( iCol<0 && sqliteExprCompare(pE, pEList->a[j].pExpr) ){
1138         iCol = j;
1139       }
1140     }
1141     if( iCol>=0 ){
1142       pE->op = TK_COLUMN;
1143       pE->iColumn = iCol;
1144       pE->iTable = iTable;
1145       pOrderBy->a[i].done = 1;
1146     }
1147     if( iCol<0 && mustComplete ){
1148       sqliteErrorMsg(pParse,
1149         "ORDER BY term number %d does not match any result column", i+1);
1150       nErr++;
1151       break;
1152     }
1153   }
1154   return nErr;
1155 }
1156 
1157 /*
1158 ** Get a VDBE for the given parser context.  Create a new one if necessary.
1159 ** If an error occurs, return NULL and leave a message in pParse.
1160 */
sqliteGetVdbe(Parse * pParse)1161 Vdbe *sqliteGetVdbe(Parse *pParse){
1162   Vdbe *v = pParse->pVdbe;
1163   if( v==0 ){
1164     v = pParse->pVdbe = sqliteVdbeCreate(pParse->db);
1165   }
1166   return v;
1167 }
1168 
1169 /*
1170 ** This routine sets the Expr.dataType field on all elements of
1171 ** the pOrderBy expression list.  The pOrderBy list will have been
1172 ** set up by matchOrderbyToColumn().  Hence each expression has
1173 ** a TK_COLUMN as its root node.  The Expr.iColumn refers to a
1174 ** column in the result set.   The datatype is set to SQLITE_SO_TEXT
1175 ** if the corresponding column in p and every SELECT to the left of
1176 ** p has a datatype of SQLITE_SO_TEXT.  If the cooressponding column
1177 ** in p or any of the left SELECTs is SQLITE_SO_NUM, then the datatype
1178 ** of the order-by expression is set to SQLITE_SO_NUM.
1179 **
1180 ** Examples:
1181 **
1182 **     CREATE TABLE one(a INTEGER, b TEXT);
1183 **     CREATE TABLE two(c VARCHAR(5), d FLOAT);
1184 **
1185 **     SELECT b, b FROM one UNION SELECT d, c FROM two ORDER BY 1, 2;
1186 **
1187 ** The primary sort key will use SQLITE_SO_NUM because the "d" in
1188 ** the second SELECT is numeric.  The 1st column of the first SELECT
1189 ** is text but that does not matter because a numeric always overrides
1190 ** a text.
1191 **
1192 ** The secondary key will use the SQLITE_SO_TEXT sort order because
1193 ** both the (second) "b" in the first SELECT and the "c" in the second
1194 ** SELECT have a datatype of text.
1195 */
multiSelectSortOrder(Select * p,ExprList * pOrderBy)1196 static void multiSelectSortOrder(Select *p, ExprList *pOrderBy){
1197   int i;
1198   ExprList *pEList;
1199   if( pOrderBy==0 ) return;
1200   if( p==0 ){
1201     for(i=0; i<pOrderBy->nExpr; i++){
1202       pOrderBy->a[i].pExpr->dataType = SQLITE_SO_TEXT;
1203     }
1204     return;
1205   }
1206   multiSelectSortOrder(p->pPrior, pOrderBy);
1207   pEList = p->pEList;
1208   for(i=0; i<pOrderBy->nExpr; i++){
1209     Expr *pE = pOrderBy->a[i].pExpr;
1210     if( pE->dataType==SQLITE_SO_NUM ) continue;
1211     assert( pE->iColumn>=0 );
1212     if( pEList->nExpr>pE->iColumn ){
1213       pE->dataType = sqliteExprType(pEList->a[pE->iColumn].pExpr);
1214     }
1215   }
1216 }
1217 
1218 /*
1219 ** Compute the iLimit and iOffset fields of the SELECT based on the
1220 ** nLimit and nOffset fields.  nLimit and nOffset hold the integers
1221 ** that appear in the original SQL statement after the LIMIT and OFFSET
1222 ** keywords.  Or that hold -1 and 0 if those keywords are omitted.
1223 ** iLimit and iOffset are the integer memory register numbers for
1224 ** counters used to compute the limit and offset.  If there is no
1225 ** limit and/or offset, then iLimit and iOffset are negative.
1226 **
1227 ** This routine changes the values if iLimit and iOffset only if
1228 ** a limit or offset is defined by nLimit and nOffset.  iLimit and
1229 ** iOffset should have been preset to appropriate default values
1230 ** (usually but not always -1) prior to calling this routine.
1231 ** Only if nLimit>=0 or nOffset>0 do the limit registers get
1232 ** redefined.  The UNION ALL operator uses this property to force
1233 ** the reuse of the same limit and offset registers across multiple
1234 ** SELECT statements.
1235 */
computeLimitRegisters(Parse * pParse,Select * p)1236 static void computeLimitRegisters(Parse *pParse, Select *p){
1237   /*
1238   ** If the comparison is p->nLimit>0 then "LIMIT 0" shows
1239   ** all rows.  It is the same as no limit. If the comparision is
1240   ** p->nLimit>=0 then "LIMIT 0" show no rows at all.
1241   ** "LIMIT -1" always shows all rows.  There is some
1242   ** contraversy about what the correct behavior should be.
1243   ** The current implementation interprets "LIMIT 0" to mean
1244   ** no rows.
1245   */
1246   if( p->nLimit>=0 ){
1247     int iMem = pParse->nMem++;
1248     Vdbe *v = sqliteGetVdbe(pParse);
1249     if( v==0 ) return;
1250     sqliteVdbeAddOp(v, OP_Integer, -p->nLimit, 0);
1251     sqliteVdbeAddOp(v, OP_MemStore, iMem, 1);
1252     p->iLimit = iMem;
1253   }
1254   if( p->nOffset>0 ){
1255     int iMem = pParse->nMem++;
1256     Vdbe *v = sqliteGetVdbe(pParse);
1257     if( v==0 ) return;
1258     sqliteVdbeAddOp(v, OP_Integer, -p->nOffset, 0);
1259     sqliteVdbeAddOp(v, OP_MemStore, iMem, 1);
1260     p->iOffset = iMem;
1261   }
1262 }
1263 
1264 /*
1265 ** This routine is called to process a query that is really the union
1266 ** or intersection of two or more separate queries.
1267 **
1268 ** "p" points to the right-most of the two queries.  the query on the
1269 ** left is p->pPrior.  The left query could also be a compound query
1270 ** in which case this routine will be called recursively.
1271 **
1272 ** The results of the total query are to be written into a destination
1273 ** of type eDest with parameter iParm.
1274 **
1275 ** Example 1:  Consider a three-way compound SQL statement.
1276 **
1277 **     SELECT a FROM t1 UNION SELECT b FROM t2 UNION SELECT c FROM t3
1278 **
1279 ** This statement is parsed up as follows:
1280 **
1281 **     SELECT c FROM t3
1282 **      |
1283 **      `----->  SELECT b FROM t2
1284 **                |
1285 **                `------>  SELECT a FROM t1
1286 **
1287 ** The arrows in the diagram above represent the Select.pPrior pointer.
1288 ** So if this routine is called with p equal to the t3 query, then
1289 ** pPrior will be the t2 query.  p->op will be TK_UNION in this case.
1290 **
1291 ** Notice that because of the way SQLite parses compound SELECTs, the
1292 ** individual selects always group from left to right.
1293 */
multiSelect(Parse * pParse,Select * p,int eDest,int iParm)1294 static int multiSelect(Parse *pParse, Select *p, int eDest, int iParm){
1295   int rc;             /* Success code from a subroutine */
1296   Select *pPrior;     /* Another SELECT immediately to our left */
1297   Vdbe *v;            /* Generate code to this VDBE */
1298 
1299   /* Make sure there is no ORDER BY or LIMIT clause on prior SELECTs.  Only
1300   ** the last SELECT in the series may have an ORDER BY or LIMIT.
1301   */
1302   if( p==0 || p->pPrior==0 ) return 1;
1303   pPrior = p->pPrior;
1304   if( pPrior->pOrderBy ){
1305     sqliteErrorMsg(pParse,"ORDER BY clause should come after %s not before",
1306       selectOpName(p->op));
1307     return 1;
1308   }
1309   if( pPrior->nLimit>=0 || pPrior->nOffset>0 ){
1310     sqliteErrorMsg(pParse,"LIMIT clause should come after %s not before",
1311       selectOpName(p->op));
1312     return 1;
1313   }
1314 
1315   /* Make sure we have a valid query engine.  If not, create a new one.
1316   */
1317   v = sqliteGetVdbe(pParse);
1318   if( v==0 ) return 1;
1319 
1320   /* Create the destination temporary table if necessary
1321   */
1322   if( eDest==SRT_TempTable ){
1323     sqliteVdbeAddOp(v, OP_OpenTemp, iParm, 0);
1324     eDest = SRT_Table;
1325   }
1326 
1327   /* Generate code for the left and right SELECT statements.
1328   */
1329   switch( p->op ){
1330     case TK_ALL: {
1331       if( p->pOrderBy==0 ){
1332         pPrior->nLimit = p->nLimit;
1333         pPrior->nOffset = p->nOffset;
1334         rc = sqliteSelect(pParse, pPrior, eDest, iParm, 0, 0, 0);
1335         if( rc ) return rc;
1336         p->pPrior = 0;
1337         p->iLimit = pPrior->iLimit;
1338         p->iOffset = pPrior->iOffset;
1339         p->nLimit = -1;
1340         p->nOffset = 0;
1341         rc = sqliteSelect(pParse, p, eDest, iParm, 0, 0, 0);
1342         p->pPrior = pPrior;
1343         if( rc ) return rc;
1344         break;
1345       }
1346     }
1347     /* FALLTHROUGH */
1348     case TK_EXCEPT:
1349     case TK_UNION: {
1350       int unionTab;    /* Cursor number of the temporary table holding result */
1351       int op;          /* One of the SRT_ operations to apply to self */
1352       int priorOp;     /* The SRT_ operation to apply to prior selects */
1353       int nLimit, nOffset; /* Saved values of p->nLimit and p->nOffset */
1354       ExprList *pOrderBy;  /* The ORDER BY clause for the right SELECT */
1355 
1356       priorOp = p->op==TK_ALL ? SRT_Table : SRT_Union;
1357       if( eDest==priorOp && p->pOrderBy==0 && p->nLimit<0 && p->nOffset==0 ){
1358         /* We can reuse a temporary table generated by a SELECT to our
1359         ** right.
1360         */
1361         unionTab = iParm;
1362       }else{
1363         /* We will need to create our own temporary table to hold the
1364         ** intermediate results.
1365         */
1366         unionTab = pParse->nTab++;
1367         if( p->pOrderBy
1368         && matchOrderbyToColumn(pParse, p, p->pOrderBy, unionTab, 1) ){
1369           return 1;
1370         }
1371         if( p->op!=TK_ALL ){
1372           sqliteVdbeAddOp(v, OP_OpenTemp, unionTab, 1);
1373           sqliteVdbeAddOp(v, OP_KeyAsData, unionTab, 1);
1374         }else{
1375           sqliteVdbeAddOp(v, OP_OpenTemp, unionTab, 0);
1376         }
1377       }
1378 
1379       /* Code the SELECT statements to our left
1380       */
1381       rc = sqliteSelect(pParse, pPrior, priorOp, unionTab, 0, 0, 0);
1382       if( rc ) return rc;
1383 
1384       /* Code the current SELECT statement
1385       */
1386       switch( p->op ){
1387          case TK_EXCEPT:  op = SRT_Except;   break;
1388          case TK_UNION:   op = SRT_Union;    break;
1389          case TK_ALL:     op = SRT_Table;    break;
1390       }
1391       p->pPrior = 0;
1392       pOrderBy = p->pOrderBy;
1393       p->pOrderBy = 0;
1394       nLimit = p->nLimit;
1395       p->nLimit = -1;
1396       nOffset = p->nOffset;
1397       p->nOffset = 0;
1398       rc = sqliteSelect(pParse, p, op, unionTab, 0, 0, 0);
1399       p->pPrior = pPrior;
1400       p->pOrderBy = pOrderBy;
1401       p->nLimit = nLimit;
1402       p->nOffset = nOffset;
1403       if( rc ) return rc;
1404 
1405       /* Convert the data in the temporary table into whatever form
1406       ** it is that we currently need.
1407       */
1408       if( eDest!=priorOp || unionTab!=iParm ){
1409         int iCont, iBreak, iStart;
1410         assert( p->pEList );
1411         if( eDest==SRT_Callback ){
1412           generateColumnNames(pParse, 0, p->pEList);
1413           generateColumnTypes(pParse, p->pSrc, p->pEList);
1414         }
1415         iBreak = sqliteVdbeMakeLabel(v);
1416         iCont = sqliteVdbeMakeLabel(v);
1417         sqliteVdbeAddOp(v, OP_Rewind, unionTab, iBreak);
1418         computeLimitRegisters(pParse, p);
1419         iStart = sqliteVdbeCurrentAddr(v);
1420         multiSelectSortOrder(p, p->pOrderBy);
1421         rc = selectInnerLoop(pParse, p, p->pEList, unionTab, p->pEList->nExpr,
1422                              p->pOrderBy, -1, eDest, iParm,
1423                              iCont, iBreak);
1424         if( rc ) return 1;
1425         sqliteVdbeResolveLabel(v, iCont);
1426         sqliteVdbeAddOp(v, OP_Next, unionTab, iStart);
1427         sqliteVdbeResolveLabel(v, iBreak);
1428         sqliteVdbeAddOp(v, OP_Close, unionTab, 0);
1429         if( p->pOrderBy ){
1430           generateSortTail(p, v, p->pEList->nExpr, eDest, iParm);
1431         }
1432       }
1433       break;
1434     }
1435     case TK_INTERSECT: {
1436       int tab1, tab2;
1437       int iCont, iBreak, iStart;
1438       int nLimit, nOffset;
1439 
1440       /* INTERSECT is different from the others since it requires
1441       ** two temporary tables.  Hence it has its own case.  Begin
1442       ** by allocating the tables we will need.
1443       */
1444       tab1 = pParse->nTab++;
1445       tab2 = pParse->nTab++;
1446       if( p->pOrderBy && matchOrderbyToColumn(pParse,p,p->pOrderBy,tab1,1) ){
1447         return 1;
1448       }
1449       sqliteVdbeAddOp(v, OP_OpenTemp, tab1, 1);
1450       sqliteVdbeAddOp(v, OP_KeyAsData, tab1, 1);
1451 
1452       /* Code the SELECTs to our left into temporary table "tab1".
1453       */
1454       rc = sqliteSelect(pParse, pPrior, SRT_Union, tab1, 0, 0, 0);
1455       if( rc ) return rc;
1456 
1457       /* Code the current SELECT into temporary table "tab2"
1458       */
1459       sqliteVdbeAddOp(v, OP_OpenTemp, tab2, 1);
1460       sqliteVdbeAddOp(v, OP_KeyAsData, tab2, 1);
1461       p->pPrior = 0;
1462       nLimit = p->nLimit;
1463       p->nLimit = -1;
1464       nOffset = p->nOffset;
1465       p->nOffset = 0;
1466       rc = sqliteSelect(pParse, p, SRT_Union, tab2, 0, 0, 0);
1467       p->pPrior = pPrior;
1468       p->nLimit = nLimit;
1469       p->nOffset = nOffset;
1470       if( rc ) return rc;
1471 
1472       /* Generate code to take the intersection of the two temporary
1473       ** tables.
1474       */
1475       assert( p->pEList );
1476       if( eDest==SRT_Callback ){
1477         generateColumnNames(pParse, 0, p->pEList);
1478         generateColumnTypes(pParse, p->pSrc, p->pEList);
1479       }
1480       iBreak = sqliteVdbeMakeLabel(v);
1481       iCont = sqliteVdbeMakeLabel(v);
1482       sqliteVdbeAddOp(v, OP_Rewind, tab1, iBreak);
1483       computeLimitRegisters(pParse, p);
1484       iStart = sqliteVdbeAddOp(v, OP_FullKey, tab1, 0);
1485       sqliteVdbeAddOp(v, OP_NotFound, tab2, iCont);
1486       multiSelectSortOrder(p, p->pOrderBy);
1487       rc = selectInnerLoop(pParse, p, p->pEList, tab1, p->pEList->nExpr,
1488                              p->pOrderBy, -1, eDest, iParm,
1489                              iCont, iBreak);
1490       if( rc ) return 1;
1491       sqliteVdbeResolveLabel(v, iCont);
1492       sqliteVdbeAddOp(v, OP_Next, tab1, iStart);
1493       sqliteVdbeResolveLabel(v, iBreak);
1494       sqliteVdbeAddOp(v, OP_Close, tab2, 0);
1495       sqliteVdbeAddOp(v, OP_Close, tab1, 0);
1496       if( p->pOrderBy ){
1497         generateSortTail(p, v, p->pEList->nExpr, eDest, iParm);
1498       }
1499       break;
1500     }
1501   }
1502   assert( p->pEList && pPrior->pEList );
1503   if( p->pEList->nExpr!=pPrior->pEList->nExpr ){
1504     sqliteErrorMsg(pParse, "SELECTs to the left and right of %s"
1505       " do not have the same number of result columns", selectOpName(p->op));
1506     return 1;
1507   }
1508   return 0;
1509 }
1510 
1511 /*
1512 ** Scan through the expression pExpr.  Replace every reference to
1513 ** a column in table number iTable with a copy of the iColumn-th
1514 ** entry in pEList.  (But leave references to the ROWID column
1515 ** unchanged.)
1516 **
1517 ** This routine is part of the flattening procedure.  A subquery
1518 ** whose result set is defined by pEList appears as entry in the
1519 ** FROM clause of a SELECT such that the VDBE cursor assigned to that
1520 ** FORM clause entry is iTable.  This routine make the necessary
1521 ** changes to pExpr so that it refers directly to the source table
1522 ** of the subquery rather the result set of the subquery.
1523 */
1524 static void substExprList(ExprList*,int,ExprList*);  /* Forward Decl */
substExpr(Expr * pExpr,int iTable,ExprList * pEList)1525 static void substExpr(Expr *pExpr, int iTable, ExprList *pEList){
1526   if( pExpr==0 ) return;
1527   if( pExpr->op==TK_COLUMN && pExpr->iTable==iTable ){
1528     if( pExpr->iColumn<0 ){
1529       pExpr->op = TK_NULL;
1530     }else{
1531       Expr *pNew;
1532       assert( pEList!=0 && pExpr->iColumn<pEList->nExpr );
1533       assert( pExpr->pLeft==0 && pExpr->pRight==0 && pExpr->pList==0 );
1534       pNew = pEList->a[pExpr->iColumn].pExpr;
1535       assert( pNew!=0 );
1536       pExpr->op = pNew->op;
1537       pExpr->dataType = pNew->dataType;
1538       assert( pExpr->pLeft==0 );
1539       pExpr->pLeft = sqliteExprDup(pNew->pLeft);
1540       assert( pExpr->pRight==0 );
1541       pExpr->pRight = sqliteExprDup(pNew->pRight);
1542       assert( pExpr->pList==0 );
1543       pExpr->pList = sqliteExprListDup(pNew->pList);
1544       pExpr->iTable = pNew->iTable;
1545       pExpr->iColumn = pNew->iColumn;
1546       pExpr->iAgg = pNew->iAgg;
1547       sqliteTokenCopy(&pExpr->token, &pNew->token);
1548       sqliteTokenCopy(&pExpr->span, &pNew->span);
1549     }
1550   }else{
1551     substExpr(pExpr->pLeft, iTable, pEList);
1552     substExpr(pExpr->pRight, iTable, pEList);
1553     substExprList(pExpr->pList, iTable, pEList);
1554   }
1555 }
1556 static void
substExprList(ExprList * pList,int iTable,ExprList * pEList)1557 substExprList(ExprList *pList, int iTable, ExprList *pEList){
1558   int i;
1559   if( pList==0 ) return;
1560   for(i=0; i<pList->nExpr; i++){
1561     substExpr(pList->a[i].pExpr, iTable, pEList);
1562   }
1563 }
1564 
1565 /*
1566 ** This routine attempts to flatten subqueries in order to speed
1567 ** execution.  It returns 1 if it makes changes and 0 if no flattening
1568 ** occurs.
1569 **
1570 ** To understand the concept of flattening, consider the following
1571 ** query:
1572 **
1573 **     SELECT a FROM (SELECT x+y AS a FROM t1 WHERE z<100) WHERE a>5
1574 **
1575 ** The default way of implementing this query is to execute the
1576 ** subquery first and store the results in a temporary table, then
1577 ** run the outer query on that temporary table.  This requires two
1578 ** passes over the data.  Furthermore, because the temporary table
1579 ** has no indices, the WHERE clause on the outer query cannot be
1580 ** optimized.
1581 **
1582 ** This routine attempts to rewrite queries such as the above into
1583 ** a single flat select, like this:
1584 **
1585 **     SELECT x+y AS a FROM t1 WHERE z<100 AND a>5
1586 **
1587 ** The code generated for this simpification gives the same result
1588 ** but only has to scan the data once.  And because indices might
1589 ** exist on the table t1, a complete scan of the data might be
1590 ** avoided.
1591 **
1592 ** Flattening is only attempted if all of the following are true:
1593 **
1594 **   (1)  The subquery and the outer query do not both use aggregates.
1595 **
1596 **   (2)  The subquery is not an aggregate or the outer query is not a join.
1597 **
1598 **   (3)  The subquery is not the right operand of a left outer join, or
1599 **        the subquery is not itself a join.  (Ticket #306)
1600 **
1601 **   (4)  The subquery is not DISTINCT or the outer query is not a join.
1602 **
1603 **   (5)  The subquery is not DISTINCT or the outer query does not use
1604 **        aggregates.
1605 **
1606 **   (6)  The subquery does not use aggregates or the outer query is not
1607 **        DISTINCT.
1608 **
1609 **   (7)  The subquery has a FROM clause.
1610 **
1611 **   (8)  The subquery does not use LIMIT or the outer query is not a join.
1612 **
1613 **   (9)  The subquery does not use LIMIT or the outer query does not use
1614 **        aggregates.
1615 **
1616 **  (10)  The subquery does not use aggregates or the outer query does not
1617 **        use LIMIT.
1618 **
1619 **  (11)  The subquery and the outer query do not both have ORDER BY clauses.
1620 **
1621 **  (12)  The subquery is not the right term of a LEFT OUTER JOIN or the
1622 **        subquery has no WHERE clause.  (added by ticket #350)
1623 **
1624 ** In this routine, the "p" parameter is a pointer to the outer query.
1625 ** The subquery is p->pSrc->a[iFrom].  isAgg is true if the outer query
1626 ** uses aggregates and subqueryIsAgg is true if the subquery uses aggregates.
1627 **
1628 ** If flattening is not attempted, this routine is a no-op and returns 0.
1629 ** If flattening is attempted this routine returns 1.
1630 **
1631 ** All of the expression analysis must occur on both the outer query and
1632 ** the subquery before this routine runs.
1633 */
flattenSubquery(Parse * pParse,Select * p,int iFrom,int isAgg,int subqueryIsAgg)1634 static int flattenSubquery(
1635   Parse *pParse,       /* The parsing context */
1636   Select *p,           /* The parent or outer SELECT statement */
1637   int iFrom,           /* Index in p->pSrc->a[] of the inner subquery */
1638   int isAgg,           /* True if outer SELECT uses aggregate functions */
1639   int subqueryIsAgg    /* True if the subquery uses aggregate functions */
1640 ){
1641   Select *pSub;       /* The inner query or "subquery" */
1642   SrcList *pSrc;      /* The FROM clause of the outer query */
1643   SrcList *pSubSrc;   /* The FROM clause of the subquery */
1644   ExprList *pList;    /* The result set of the outer query */
1645   int iParent;        /* VDBE cursor number of the pSub result set temp table */
1646   int i;
1647   Expr *pWhere;
1648 
1649   /* Check to see if flattening is permitted.  Return 0 if not.
1650   */
1651   if( p==0 ) return 0;
1652   pSrc = p->pSrc;
1653   assert( pSrc && iFrom>=0 && iFrom<pSrc->nSrc );
1654   pSub = pSrc->a[iFrom].pSelect;
1655   assert( pSub!=0 );
1656   if( isAgg && subqueryIsAgg ) return 0;
1657   if( subqueryIsAgg && pSrc->nSrc>1 ) return 0;
1658   pSubSrc = pSub->pSrc;
1659   assert( pSubSrc );
1660   if( pSubSrc->nSrc==0 ) return 0;
1661   if( (pSub->isDistinct || pSub->nLimit>=0) &&  (pSrc->nSrc>1 || isAgg) ){
1662      return 0;
1663   }
1664   if( (p->isDistinct || p->nLimit>=0) && subqueryIsAgg ) return 0;
1665   if( p->pOrderBy && pSub->pOrderBy ) return 0;
1666 
1667   /* Restriction 3:  If the subquery is a join, make sure the subquery is
1668   ** not used as the right operand of an outer join.  Examples of why this
1669   ** is not allowed:
1670   **
1671   **         t1 LEFT OUTER JOIN (t2 JOIN t3)
1672   **
1673   ** If we flatten the above, we would get
1674   **
1675   **         (t1 LEFT OUTER JOIN t2) JOIN t3
1676   **
1677   ** which is not at all the same thing.
1678   */
1679   if( pSubSrc->nSrc>1 && iFrom>0 && (pSrc->a[iFrom-1].jointype & JT_OUTER)!=0 ){
1680     return 0;
1681   }
1682 
1683   /* Restriction 12:  If the subquery is the right operand of a left outer
1684   ** join, make sure the subquery has no WHERE clause.
1685   ** An examples of why this is not allowed:
1686   **
1687   **         t1 LEFT OUTER JOIN (SELECT * FROM t2 WHERE t2.x>0)
1688   **
1689   ** If we flatten the above, we would get
1690   **
1691   **         (t1 LEFT OUTER JOIN t2) WHERE t2.x>0
1692   **
1693   ** But the t2.x>0 test will always fail on a NULL row of t2, which
1694   ** effectively converts the OUTER JOIN into an INNER JOIN.
1695   */
1696   if( iFrom>0 && (pSrc->a[iFrom-1].jointype & JT_OUTER)!=0
1697       && pSub->pWhere!=0 ){
1698     return 0;
1699   }
1700 
1701   /* If we reach this point, it means flattening is permitted for the
1702   ** iFrom-th entry of the FROM clause in the outer query.
1703   */
1704 
1705   /* Move all of the FROM elements of the subquery into the
1706   ** the FROM clause of the outer query.  Before doing this, remember
1707   ** the cursor number for the original outer query FROM element in
1708   ** iParent.  The iParent cursor will never be used.  Subsequent code
1709   ** will scan expressions looking for iParent references and replace
1710   ** those references with expressions that resolve to the subquery FROM
1711   ** elements we are now copying in.
1712   */
1713   iParent = pSrc->a[iFrom].iCursor;
1714   {
1715     int nSubSrc = pSubSrc->nSrc;
1716     int jointype = pSrc->a[iFrom].jointype;
1717 
1718     if( pSrc->a[iFrom].pTab && pSrc->a[iFrom].pTab->isTransient ){
1719       sqliteDeleteTable(0, pSrc->a[iFrom].pTab);
1720     }
1721     sqliteFree(pSrc->a[iFrom].zDatabase);
1722     sqliteFree(pSrc->a[iFrom].zName);
1723     sqliteFree(pSrc->a[iFrom].zAlias);
1724     if( nSubSrc>1 ){
1725       int extra = nSubSrc - 1;
1726       for(i=1; i<nSubSrc; i++){
1727         pSrc = sqliteSrcListAppend(pSrc, 0, 0);
1728       }
1729       p->pSrc = pSrc;
1730       for(i=pSrc->nSrc-1; i-extra>=iFrom; i--){
1731         pSrc->a[i] = pSrc->a[i-extra];
1732       }
1733     }
1734     for(i=0; i<nSubSrc; i++){
1735       pSrc->a[i+iFrom] = pSubSrc->a[i];
1736       memset(&pSubSrc->a[i], 0, sizeof(pSubSrc->a[i]));
1737     }
1738     pSrc->a[iFrom+nSubSrc-1].jointype = jointype;
1739   }
1740 
1741   /* Now begin substituting subquery result set expressions for
1742   ** references to the iParent in the outer query.
1743   **
1744   ** Example:
1745   **
1746   **   SELECT a+5, b*10 FROM (SELECT x*3 AS a, y+10 AS b FROM t1) WHERE a>b;
1747   **   \                     \_____________ subquery __________/          /
1748   **    \_____________________ outer query ______________________________/
1749   **
1750   ** We look at every expression in the outer query and every place we see
1751   ** "a" we substitute "x*3" and every place we see "b" we substitute "y+10".
1752   */
1753   substExprList(p->pEList, iParent, pSub->pEList);
1754   pList = p->pEList;
1755   for(i=0; i<pList->nExpr; i++){
1756     Expr *pExpr;
1757     if( pList->a[i].zName==0 && (pExpr = pList->a[i].pExpr)->span.z!=0 ){
1758       pList->a[i].zName = sqliteStrNDup(pExpr->span.z, pExpr->span.n);
1759     }
1760   }
1761   if( isAgg ){
1762     substExprList(p->pGroupBy, iParent, pSub->pEList);
1763     substExpr(p->pHaving, iParent, pSub->pEList);
1764   }
1765   if( pSub->pOrderBy ){
1766     assert( p->pOrderBy==0 );
1767     p->pOrderBy = pSub->pOrderBy;
1768     pSub->pOrderBy = 0;
1769   }else if( p->pOrderBy ){
1770     substExprList(p->pOrderBy, iParent, pSub->pEList);
1771   }
1772   if( pSub->pWhere ){
1773     pWhere = sqliteExprDup(pSub->pWhere);
1774   }else{
1775     pWhere = 0;
1776   }
1777   if( subqueryIsAgg ){
1778     assert( p->pHaving==0 );
1779     p->pHaving = p->pWhere;
1780     p->pWhere = pWhere;
1781     substExpr(p->pHaving, iParent, pSub->pEList);
1782     if( pSub->pHaving ){
1783       Expr *pHaving = sqliteExprDup(pSub->pHaving);
1784       if( p->pHaving ){
1785         p->pHaving = sqliteExpr(TK_AND, p->pHaving, pHaving, 0);
1786       }else{
1787         p->pHaving = pHaving;
1788       }
1789     }
1790     assert( p->pGroupBy==0 );
1791     p->pGroupBy = sqliteExprListDup(pSub->pGroupBy);
1792   }else if( p->pWhere==0 ){
1793     p->pWhere = pWhere;
1794   }else{
1795     substExpr(p->pWhere, iParent, pSub->pEList);
1796     if( pWhere ){
1797       p->pWhere = sqliteExpr(TK_AND, p->pWhere, pWhere, 0);
1798     }
1799   }
1800 
1801   /* The flattened query is distinct if either the inner or the
1802   ** outer query is distinct.
1803   */
1804   p->isDistinct = p->isDistinct || pSub->isDistinct;
1805 
1806   /* Transfer the limit expression from the subquery to the outer
1807   ** query.
1808   */
1809   if( pSub->nLimit>=0 ){
1810     if( p->nLimit<0 ){
1811       p->nLimit = pSub->nLimit;
1812     }else if( p->nLimit+p->nOffset > pSub->nLimit+pSub->nOffset ){
1813       p->nLimit = pSub->nLimit + pSub->nOffset - p->nOffset;
1814     }
1815   }
1816   p->nOffset += pSub->nOffset;
1817 
1818   /* Finially, delete what is left of the subquery and return
1819   ** success.
1820   */
1821   sqliteSelectDelete(pSub);
1822   return 1;
1823 }
1824 
1825 /*
1826 ** Analyze the SELECT statement passed in as an argument to see if it
1827 ** is a simple min() or max() query.  If it is and this query can be
1828 ** satisfied using a single seek to the beginning or end of an index,
1829 ** then generate the code for this SELECT and return 1.  If this is not a
1830 ** simple min() or max() query, then return 0;
1831 **
1832 ** A simply min() or max() query looks like this:
1833 **
1834 **    SELECT min(a) FROM table;
1835 **    SELECT max(a) FROM table;
1836 **
1837 ** The query may have only a single table in its FROM argument.  There
1838 ** can be no GROUP BY or HAVING or WHERE clauses.  The result set must
1839 ** be the min() or max() of a single column of the table.  The column
1840 ** in the min() or max() function must be indexed.
1841 **
1842 ** The parameters to this routine are the same as for sqliteSelect().
1843 ** See the header comment on that routine for additional information.
1844 */
simpleMinMaxQuery(Parse * pParse,Select * p,int eDest,int iParm)1845 static int simpleMinMaxQuery(Parse *pParse, Select *p, int eDest, int iParm){
1846   Expr *pExpr;
1847   int iCol;
1848   Table *pTab;
1849   Index *pIdx;
1850   int base;
1851   Vdbe *v;
1852   int seekOp;
1853   int cont;
1854   ExprList *pEList, *pList, eList;
1855   struct ExprList_item eListItem;
1856   SrcList *pSrc;
1857 
1858 
1859   /* Check to see if this query is a simple min() or max() query.  Return
1860   ** zero if it is  not.
1861   */
1862   if( p->pGroupBy || p->pHaving || p->pWhere ) return 0;
1863   pSrc = p->pSrc;
1864   if( pSrc->nSrc!=1 ) return 0;
1865   pEList = p->pEList;
1866   if( pEList->nExpr!=1 ) return 0;
1867   pExpr = pEList->a[0].pExpr;
1868   if( pExpr->op!=TK_AGG_FUNCTION ) return 0;
1869   pList = pExpr->pList;
1870   if( pList==0 || pList->nExpr!=1 ) return 0;
1871   if( pExpr->token.n!=3 ) return 0;
1872   if( sqliteStrNICmp(pExpr->token.z,"min",3)==0 ){
1873     seekOp = OP_Rewind;
1874   }else if( sqliteStrNICmp(pExpr->token.z,"max",3)==0 ){
1875     seekOp = OP_Last;
1876   }else{
1877     return 0;
1878   }
1879   pExpr = pList->a[0].pExpr;
1880   if( pExpr->op!=TK_COLUMN ) return 0;
1881   iCol = pExpr->iColumn;
1882   pTab = pSrc->a[0].pTab;
1883 
1884   /* If we get to here, it means the query is of the correct form.
1885   ** Check to make sure we have an index and make pIdx point to the
1886   ** appropriate index.  If the min() or max() is on an INTEGER PRIMARY
1887   ** key column, no index is necessary so set pIdx to NULL.  If no
1888   ** usable index is found, return 0.
1889   */
1890   if( iCol<0 ){
1891     pIdx = 0;
1892   }else{
1893     for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
1894       assert( pIdx->nColumn>=1 );
1895       if( pIdx->aiColumn[0]==iCol ) break;
1896     }
1897     if( pIdx==0 ) return 0;
1898   }
1899 
1900   /* Identify column types if we will be using the callback.  This
1901   ** step is skipped if the output is going to a table or a memory cell.
1902   ** The column names have already been generated in the calling function.
1903   */
1904   v = sqliteGetVdbe(pParse);
1905   if( v==0 ) return 0;
1906   if( eDest==SRT_Callback ){
1907     generateColumnTypes(pParse, p->pSrc, p->pEList);
1908   }
1909 
1910   /* If the output is destined for a temporary table, open that table.
1911   */
1912   if( eDest==SRT_TempTable ){
1913     sqliteVdbeAddOp(v, OP_OpenTemp, iParm, 0);
1914   }
1915 
1916   /* Generating code to find the min or the max.  Basically all we have
1917   ** to do is find the first or the last entry in the chosen index.  If
1918   ** the min() or max() is on the INTEGER PRIMARY KEY, then find the first
1919   ** or last entry in the main table.
1920   */
1921   sqliteCodeVerifySchema(pParse, pTab->iDb);
1922   base = pSrc->a[0].iCursor;
1923   computeLimitRegisters(pParse, p);
1924   if( pSrc->a[0].pSelect==0 ){
1925     sqliteVdbeAddOp(v, OP_Integer, pTab->iDb, 0);
1926     sqliteVdbeOp3(v, OP_OpenRead, base, pTab->tnum, pTab->zName, 0);
1927   }
1928   cont = sqliteVdbeMakeLabel(v);
1929   if( pIdx==0 ){
1930     sqliteVdbeAddOp(v, seekOp, base, 0);
1931   }else{
1932     sqliteVdbeAddOp(v, OP_Integer, pIdx->iDb, 0);
1933     sqliteVdbeOp3(v, OP_OpenRead, base+1, pIdx->tnum, pIdx->zName, P3_STATIC);
1934     if( seekOp==OP_Rewind ){
1935       sqliteVdbeAddOp(v, OP_String, 0, 0);
1936       sqliteVdbeAddOp(v, OP_MakeKey, 1, 0);
1937       sqliteVdbeAddOp(v, OP_IncrKey, 0, 0);
1938       seekOp = OP_MoveTo;
1939     }
1940     sqliteVdbeAddOp(v, seekOp, base+1, 0);
1941     sqliteVdbeAddOp(v, OP_IdxRecno, base+1, 0);
1942     sqliteVdbeAddOp(v, OP_Close, base+1, 0);
1943     sqliteVdbeAddOp(v, OP_MoveTo, base, 0);
1944   }
1945   eList.nExpr = 1;
1946   memset(&eListItem, 0, sizeof(eListItem));
1947   eList.a = &eListItem;
1948   eList.a[0].pExpr = pExpr;
1949   selectInnerLoop(pParse, p, &eList, 0, 0, 0, -1, eDest, iParm, cont, cont);
1950   sqliteVdbeResolveLabel(v, cont);
1951   sqliteVdbeAddOp(v, OP_Close, base, 0);
1952 
1953   return 1;
1954 }
1955 
1956 /*
1957 ** Generate code for the given SELECT statement.
1958 **
1959 ** The results are distributed in various ways depending on the
1960 ** value of eDest and iParm.
1961 **
1962 **     eDest Value       Result
1963 **     ------------    -------------------------------------------
1964 **     SRT_Callback    Invoke the callback for each row of the result.
1965 **
1966 **     SRT_Mem         Store first result in memory cell iParm
1967 **
1968 **     SRT_Set         Store results as keys of a table with cursor iParm
1969 **
1970 **     SRT_Union       Store results as a key in a temporary table iParm
1971 **
1972 **     SRT_Except      Remove results from the temporary table iParm.
1973 **
1974 **     SRT_Table       Store results in temporary table iParm
1975 **
1976 ** The table above is incomplete.  Additional eDist value have be added
1977 ** since this comment was written.  See the selectInnerLoop() function for
1978 ** a complete listing of the allowed values of eDest and their meanings.
1979 **
1980 ** This routine returns the number of errors.  If any errors are
1981 ** encountered, then an appropriate error message is left in
1982 ** pParse->zErrMsg.
1983 **
1984 ** This routine does NOT free the Select structure passed in.  The
1985 ** calling function needs to do that.
1986 **
1987 ** The pParent, parentTab, and *pParentAgg fields are filled in if this
1988 ** SELECT is a subquery.  This routine may try to combine this SELECT
1989 ** with its parent to form a single flat query.  In so doing, it might
1990 ** change the parent query from a non-aggregate to an aggregate query.
1991 ** For that reason, the pParentAgg flag is passed as a pointer, so it
1992 ** can be changed.
1993 **
1994 ** Example 1:   The meaning of the pParent parameter.
1995 **
1996 **    SELECT * FROM t1 JOIN (SELECT x, count(*) FROM t2) JOIN t3;
1997 **    \                      \_______ subquery _______/        /
1998 **     \                                                      /
1999 **      \____________________ outer query ___________________/
2000 **
2001 ** This routine is called for the outer query first.   For that call,
2002 ** pParent will be NULL.  During the processing of the outer query, this
2003 ** routine is called recursively to handle the subquery.  For the recursive
2004 ** call, pParent will point to the outer query.  Because the subquery is
2005 ** the second element in a three-way join, the parentTab parameter will
2006 ** be 1 (the 2nd value of a 0-indexed array.)
2007 */
sqliteSelect(Parse * pParse,Select * p,int eDest,int iParm,Select * pParent,int parentTab,int * pParentAgg)2008 int sqliteSelect(
2009   Parse *pParse,         /* The parser context */
2010   Select *p,             /* The SELECT statement being coded. */
2011   int eDest,             /* How to dispose of the results */
2012   int iParm,             /* A parameter used by the eDest disposal method */
2013   Select *pParent,       /* Another SELECT for which this is a sub-query */
2014   int parentTab,         /* Index in pParent->pSrc of this query */
2015   int *pParentAgg        /* True if pParent uses aggregate functions */
2016 ){
2017   int i;
2018   WhereInfo *pWInfo;
2019   Vdbe *v;
2020   int isAgg = 0;         /* True for select lists like "count(*)" */
2021   ExprList *pEList;      /* List of columns to extract. */
2022   SrcList *pTabList;     /* List of tables to select from */
2023   Expr *pWhere;          /* The WHERE clause.  May be NULL */
2024   ExprList *pOrderBy;    /* The ORDER BY clause.  May be NULL */
2025   ExprList *pGroupBy;    /* The GROUP BY clause.  May be NULL */
2026   Expr *pHaving;         /* The HAVING clause.  May be NULL */
2027   int isDistinct;        /* True if the DISTINCT keyword is present */
2028   int distinct;          /* Table to use for the distinct set */
2029   int rc = 1;            /* Value to return from this function */
2030 
2031   if( sqlite_malloc_failed || pParse->nErr || p==0 ) return 1;
2032   if( sqliteAuthCheck(pParse, SQLITE_SELECT, 0, 0, 0) ) return 1;
2033 
2034   /* If there is are a sequence of queries, do the earlier ones first.
2035   */
2036   if( p->pPrior ){
2037     return multiSelect(pParse, p, eDest, iParm);
2038   }
2039 
2040   /* Make local copies of the parameters for this query.
2041   */
2042   pTabList = p->pSrc;
2043   pWhere = p->pWhere;
2044   pOrderBy = p->pOrderBy;
2045   pGroupBy = p->pGroupBy;
2046   pHaving = p->pHaving;
2047   isDistinct = p->isDistinct;
2048 
2049   /* Allocate VDBE cursors for each table in the FROM clause
2050   */
2051   sqliteSrcListAssignCursors(pParse, pTabList);
2052 
2053   /*
2054   ** Do not even attempt to generate any code if we have already seen
2055   ** errors before this routine starts.
2056   */
2057   if( pParse->nErr>0 ) goto select_end;
2058 
2059   /* Expand any "*" terms in the result set.  (For example the "*" in
2060   ** "SELECT * FROM t1")  The fillInColumnlist() routine also does some
2061   ** other housekeeping - see the header comment for details.
2062   */
2063   if( fillInColumnList(pParse, p) ){
2064     goto select_end;
2065   }
2066   pWhere = p->pWhere;
2067   pEList = p->pEList;
2068   if( pEList==0 ) goto select_end;
2069 
2070   /* If writing to memory or generating a set
2071   ** only a single column may be output.
2072   */
2073   if( (eDest==SRT_Mem || eDest==SRT_Set) && pEList->nExpr>1 ){
2074     sqliteErrorMsg(pParse, "only a single result allowed for "
2075        "a SELECT that is part of an expression");
2076     goto select_end;
2077   }
2078 
2079   /* ORDER BY is ignored for some destinations.
2080   */
2081   switch( eDest ){
2082     case SRT_Union:
2083     case SRT_Except:
2084     case SRT_Discard:
2085       pOrderBy = 0;
2086       break;
2087     default:
2088       break;
2089   }
2090 
2091   /* At this point, we should have allocated all the cursors that we
2092   ** need to handle subquerys and temporary tables.
2093   **
2094   ** Resolve the column names and do a semantics check on all the expressions.
2095   */
2096   for(i=0; i<pEList->nExpr; i++){
2097     if( sqliteExprResolveIds(pParse, pTabList, 0, pEList->a[i].pExpr) ){
2098       goto select_end;
2099     }
2100     if( sqliteExprCheck(pParse, pEList->a[i].pExpr, 1, &isAgg) ){
2101       goto select_end;
2102     }
2103   }
2104   if( pWhere ){
2105     if( sqliteExprResolveIds(pParse, pTabList, pEList, pWhere) ){
2106       goto select_end;
2107     }
2108     if( sqliteExprCheck(pParse, pWhere, 0, 0) ){
2109       goto select_end;
2110     }
2111   }
2112   if( pHaving ){
2113     if( pGroupBy==0 ){
2114       sqliteErrorMsg(pParse, "a GROUP BY clause is required before HAVING");
2115       goto select_end;
2116     }
2117     if( sqliteExprResolveIds(pParse, pTabList, pEList, pHaving) ){
2118       goto select_end;
2119     }
2120     if( sqliteExprCheck(pParse, pHaving, 1, &isAgg) ){
2121       goto select_end;
2122     }
2123   }
2124   if( pOrderBy ){
2125     for(i=0; i<pOrderBy->nExpr; i++){
2126       int iCol;
2127       Expr *pE = pOrderBy->a[i].pExpr;
2128       if( sqliteExprIsInteger(pE, &iCol) && iCol>0 && iCol<=pEList->nExpr ){
2129         sqliteExprDelete(pE);
2130         pE = pOrderBy->a[i].pExpr = sqliteExprDup(pEList->a[iCol-1].pExpr);
2131       }
2132       if( sqliteExprResolveIds(pParse, pTabList, pEList, pE) ){
2133         goto select_end;
2134       }
2135       if( sqliteExprCheck(pParse, pE, isAgg, 0) ){
2136         goto select_end;
2137       }
2138       if( sqliteExprIsConstant(pE) ){
2139         if( sqliteExprIsInteger(pE, &iCol)==0 ){
2140           sqliteErrorMsg(pParse,
2141              "ORDER BY terms must not be non-integer constants");
2142           goto select_end;
2143         }else if( iCol<=0 || iCol>pEList->nExpr ){
2144           sqliteErrorMsg(pParse,
2145              "ORDER BY column number %d out of range - should be "
2146              "between 1 and %d", iCol, pEList->nExpr);
2147           goto select_end;
2148         }
2149       }
2150     }
2151   }
2152   if( pGroupBy ){
2153     for(i=0; i<pGroupBy->nExpr; i++){
2154       int iCol;
2155       Expr *pE = pGroupBy->a[i].pExpr;
2156       if( sqliteExprIsInteger(pE, &iCol) && iCol>0 && iCol<=pEList->nExpr ){
2157         sqliteExprDelete(pE);
2158         pE = pGroupBy->a[i].pExpr = sqliteExprDup(pEList->a[iCol-1].pExpr);
2159       }
2160       if( sqliteExprResolveIds(pParse, pTabList, pEList, pE) ){
2161         goto select_end;
2162       }
2163       if( sqliteExprCheck(pParse, pE, isAgg, 0) ){
2164         goto select_end;
2165       }
2166       if( sqliteExprIsConstant(pE) ){
2167         if( sqliteExprIsInteger(pE, &iCol)==0 ){
2168           sqliteErrorMsg(pParse,
2169             "GROUP BY terms must not be non-integer constants");
2170           goto select_end;
2171         }else if( iCol<=0 || iCol>pEList->nExpr ){
2172           sqliteErrorMsg(pParse,
2173              "GROUP BY column number %d out of range - should be "
2174              "between 1 and %d", iCol, pEList->nExpr);
2175           goto select_end;
2176         }
2177       }
2178     }
2179   }
2180 
2181   /* Begin generating code.
2182   */
2183   v = sqliteGetVdbe(pParse);
2184   if( v==0 ) goto select_end;
2185 
2186   /* Identify column names if we will be using them in a callback.  This
2187   ** step is skipped if the output is going to some other destination.
2188   */
2189   if( eDest==SRT_Callback ){
2190     generateColumnNames(pParse, pTabList, pEList);
2191   }
2192 
2193   /* Generate code for all sub-queries in the FROM clause
2194   */
2195   for(i=0; i<pTabList->nSrc; i++){
2196     const char *zSavedAuthContext;
2197     int needRestoreContext;
2198 
2199     if( pTabList->a[i].pSelect==0 ) continue;
2200     if( pTabList->a[i].zName!=0 ){
2201       zSavedAuthContext = pParse->zAuthContext;
2202       pParse->zAuthContext = pTabList->a[i].zName;
2203       needRestoreContext = 1;
2204     }else{
2205       needRestoreContext = 0;
2206     }
2207     sqliteSelect(pParse, pTabList->a[i].pSelect, SRT_TempTable,
2208                  pTabList->a[i].iCursor, p, i, &isAgg);
2209     if( needRestoreContext ){
2210       pParse->zAuthContext = zSavedAuthContext;
2211     }
2212     pTabList = p->pSrc;
2213     pWhere = p->pWhere;
2214     if( eDest!=SRT_Union && eDest!=SRT_Except && eDest!=SRT_Discard ){
2215       pOrderBy = p->pOrderBy;
2216     }
2217     pGroupBy = p->pGroupBy;
2218     pHaving = p->pHaving;
2219     isDistinct = p->isDistinct;
2220   }
2221 
2222   /* Check for the special case of a min() or max() function by itself
2223   ** in the result set.
2224   */
2225   if( simpleMinMaxQuery(pParse, p, eDest, iParm) ){
2226     rc = 0;
2227     goto select_end;
2228   }
2229 
2230   /* Check to see if this is a subquery that can be "flattened" into its parent.
2231   ** If flattening is a possiblity, do so and return immediately.
2232   */
2233   if( pParent && pParentAgg &&
2234       flattenSubquery(pParse, pParent, parentTab, *pParentAgg, isAgg) ){
2235     if( isAgg ) *pParentAgg = 1;
2236     return rc;
2237   }
2238 
2239   /* Set the limiter.
2240   */
2241   computeLimitRegisters(pParse, p);
2242 
2243   /* Identify column types if we will be using a callback.  This
2244   ** step is skipped if the output is going to a destination other
2245   ** than a callback.
2246   **
2247   ** We have to do this separately from the creation of column names
2248   ** above because if the pTabList contains views then they will not
2249   ** have been resolved and we will not know the column types until
2250   ** now.
2251   */
2252   if( eDest==SRT_Callback ){
2253     generateColumnTypes(pParse, pTabList, pEList);
2254   }
2255 
2256   /* If the output is destined for a temporary table, open that table.
2257   */
2258   if( eDest==SRT_TempTable ){
2259     sqliteVdbeAddOp(v, OP_OpenTemp, iParm, 0);
2260   }
2261 
2262   /* Do an analysis of aggregate expressions.
2263   */
2264   sqliteAggregateInfoReset(pParse);
2265   if( isAgg || pGroupBy ){
2266     assert( pParse->nAgg==0 );
2267     isAgg = 1;
2268     for(i=0; i<pEList->nExpr; i++){
2269       if( sqliteExprAnalyzeAggregates(pParse, pEList->a[i].pExpr) ){
2270         goto select_end;
2271       }
2272     }
2273     if( pGroupBy ){
2274       for(i=0; i<pGroupBy->nExpr; i++){
2275         if( sqliteExprAnalyzeAggregates(pParse, pGroupBy->a[i].pExpr) ){
2276           goto select_end;
2277         }
2278       }
2279     }
2280     if( pHaving && sqliteExprAnalyzeAggregates(pParse, pHaving) ){
2281       goto select_end;
2282     }
2283     if( pOrderBy ){
2284       for(i=0; i<pOrderBy->nExpr; i++){
2285         if( sqliteExprAnalyzeAggregates(pParse, pOrderBy->a[i].pExpr) ){
2286           goto select_end;
2287         }
2288       }
2289     }
2290   }
2291 
2292   /* Reset the aggregator
2293   */
2294   if( isAgg ){
2295     sqliteVdbeAddOp(v, OP_AggReset, 0, pParse->nAgg);
2296     for(i=0; i<pParse->nAgg; i++){
2297       FuncDef *pFunc;
2298       if( (pFunc = pParse->aAgg[i].pFunc)!=0 && pFunc->xFinalize!=0 ){
2299         sqliteVdbeOp3(v, OP_AggInit, 0, i, (char*)pFunc, P3_POINTER);
2300       }
2301     }
2302     if( pGroupBy==0 ){
2303       sqliteVdbeAddOp(v, OP_String, 0, 0);
2304       sqliteVdbeAddOp(v, OP_AggFocus, 0, 0);
2305     }
2306   }
2307 
2308   /* Initialize the memory cell to NULL
2309   */
2310   if( eDest==SRT_Mem ){
2311     sqliteVdbeAddOp(v, OP_String, 0, 0);
2312     sqliteVdbeAddOp(v, OP_MemStore, iParm, 1);
2313   }
2314 
2315   /* Open a temporary table to use for the distinct set.
2316   */
2317   if( isDistinct ){
2318     distinct = pParse->nTab++;
2319     sqliteVdbeAddOp(v, OP_OpenTemp, distinct, 1);
2320   }else{
2321     distinct = -1;
2322   }
2323 
2324   /* Begin the database scan
2325   */
2326   pWInfo = sqliteWhereBegin(pParse, pTabList, pWhere, 0,
2327                             pGroupBy ? 0 : &pOrderBy);
2328   if( pWInfo==0 ) goto select_end;
2329 
2330   /* Use the standard inner loop if we are not dealing with
2331   ** aggregates
2332   */
2333   if( !isAgg ){
2334     if( selectInnerLoop(pParse, p, pEList, 0, 0, pOrderBy, distinct, eDest,
2335                     iParm, pWInfo->iContinue, pWInfo->iBreak) ){
2336        goto select_end;
2337     }
2338   }
2339 
2340   /* If we are dealing with aggregates, then do the special aggregate
2341   ** processing.
2342   */
2343   else{
2344     AggExpr *pAgg;
2345     if( pGroupBy ){
2346       int lbl1;
2347       for(i=0; i<pGroupBy->nExpr; i++){
2348         sqliteExprCode(pParse, pGroupBy->a[i].pExpr);
2349       }
2350       sqliteVdbeAddOp(v, OP_MakeKey, pGroupBy->nExpr, 0);
2351       if( pParse->db->file_format>=4 ) sqliteAddKeyType(v, pGroupBy);
2352       lbl1 = sqliteVdbeMakeLabel(v);
2353       sqliteVdbeAddOp(v, OP_AggFocus, 0, lbl1);
2354       for(i=0, pAgg=pParse->aAgg; i<pParse->nAgg; i++, pAgg++){
2355         if( pAgg->isAgg ) continue;
2356         sqliteExprCode(pParse, pAgg->pExpr);
2357         sqliteVdbeAddOp(v, OP_AggSet, 0, i);
2358       }
2359       sqliteVdbeResolveLabel(v, lbl1);
2360     }
2361     for(i=0, pAgg=pParse->aAgg; i<pParse->nAgg; i++, pAgg++){
2362       Expr *pE;
2363       int nExpr;
2364       FuncDef *pDef;
2365       if( !pAgg->isAgg ) continue;
2366       assert( pAgg->pFunc!=0 );
2367       assert( pAgg->pFunc->xStep!=0 );
2368       pDef = pAgg->pFunc;
2369       pE = pAgg->pExpr;
2370       assert( pE!=0 );
2371       assert( pE->op==TK_AGG_FUNCTION );
2372       nExpr = sqliteExprCodeExprList(pParse, pE->pList, pDef->includeTypes);
2373       sqliteVdbeAddOp(v, OP_Integer, i, 0);
2374       sqliteVdbeOp3(v, OP_AggFunc, 0, nExpr, (char*)pDef, P3_POINTER);
2375     }
2376   }
2377 
2378   /* End the database scan loop.
2379   */
2380   sqliteWhereEnd(pWInfo);
2381 
2382   /* If we are processing aggregates, we need to set up a second loop
2383   ** over all of the aggregate values and process them.
2384   */
2385   if( isAgg ){
2386     int endagg = sqliteVdbeMakeLabel(v);
2387     int startagg;
2388     startagg = sqliteVdbeAddOp(v, OP_AggNext, 0, endagg);
2389     pParse->useAgg = 1;
2390     if( pHaving ){
2391       sqliteExprIfFalse(pParse, pHaving, startagg, 1);
2392     }
2393     if( selectInnerLoop(pParse, p, pEList, 0, 0, pOrderBy, distinct, eDest,
2394                     iParm, startagg, endagg) ){
2395       goto select_end;
2396     }
2397     sqliteVdbeAddOp(v, OP_Goto, 0, startagg);
2398     sqliteVdbeResolveLabel(v, endagg);
2399     sqliteVdbeAddOp(v, OP_Noop, 0, 0);
2400     pParse->useAgg = 0;
2401   }
2402 
2403   /* If there is an ORDER BY clause, then we need to sort the results
2404   ** and send them to the callback one by one.
2405   */
2406   if( pOrderBy ){
2407     generateSortTail(p, v, pEList->nExpr, eDest, iParm);
2408   }
2409 
2410   /* If this was a subquery, we have now converted the subquery into a
2411   ** temporary table.  So delete the subquery structure from the parent
2412   ** to prevent this subquery from being evaluated again and to force the
2413   ** the use of the temporary table.
2414   */
2415   if( pParent ){
2416     assert( pParent->pSrc->nSrc>parentTab );
2417     assert( pParent->pSrc->a[parentTab].pSelect==p );
2418     sqliteSelectDelete(p);
2419     pParent->pSrc->a[parentTab].pSelect = 0;
2420   }
2421 
2422   /* The SELECT was successfully coded.   Set the return code to 0
2423   ** to indicate no errors.
2424   */
2425   rc = 0;
2426 
2427   /* Control jumps to here if an error is encountered above, or upon
2428   ** successful coding of the SELECT.
2429   */
2430 select_end:
2431   sqliteAggregateInfoReset(pParse);
2432   return rc;
2433 }
2434