monotone

monotone Mtn Source Tree

Root/sqlite/select.c

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

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status