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