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 #include "sqliteInt.h"
16
17 /*
18 ** Trace output macros
19 */
20 #if SELECTTRACE_ENABLED
21 /***/ int sqlite3SelectTrace = 0;
22 # define SELECTTRACE(K,P,S,X) \
23 if(sqlite3SelectTrace&(K)) \
24 sqlite3DebugPrintf("%*s%s.%p: ",(P)->nSelectIndent*2-2,"",\
25 (S)->zSelName,(S)),\
26 sqlite3DebugPrintf X
27 #else
28 # define SELECTTRACE(K,P,S,X)
29 #endif
30
31
32 /*
33 ** An instance of the following object is used to record information about
34 ** how to process the DISTINCT keyword, to simplify passing that information
35 ** into the selectInnerLoop() routine.
36 */
37 typedef struct DistinctCtx DistinctCtx;
38 struct DistinctCtx {
39 u8 isTnct; /* True if the DISTINCT keyword is present */
40 u8 eTnctType; /* One of the WHERE_DISTINCT_* operators */
41 int tabTnct; /* Ephemeral table used for DISTINCT processing */
42 int addrTnct; /* Address of OP_OpenEphemeral opcode for tabTnct */
43 };
44
45 /*
46 ** An instance of the following object is used to record information about
47 ** the ORDER BY (or GROUP BY) clause of query is being coded.
48 */
49 typedef struct SortCtx SortCtx;
50 struct SortCtx {
51 ExprList *pOrderBy; /* The ORDER BY (or GROUP BY clause) */
52 int nOBSat; /* Number of ORDER BY terms satisfied by indices */
53 int iECursor; /* Cursor number for the sorter */
54 int regReturn; /* Register holding block-output return address */
55 int labelBkOut; /* Start label for the block-output subroutine */
56 int addrSortIndex; /* Address of the OP_SorterOpen or OP_OpenEphemeral */
57 int labelDone; /* Jump here when done, ex: LIMIT reached */
58 u8 sortFlags; /* Zero or more SORTFLAG_* bits */
59 u8 bOrderedInnerLoop; /* ORDER BY correctly sorts the inner loop */
60 };
61 #define SORTFLAG_UseSorter 0x01 /* Use SorterOpen instead of OpenEphemeral */
62
63 /*
64 ** Delete all the content of a Select structure. Deallocate the structure
65 ** itself only if bFree is true.
66 */
clearSelect(sqlite3 * db,Select * p,int bFree)67 static void clearSelect(sqlite3 *db, Select *p, int bFree){
68 while( p ){
69 Select *pPrior = p->pPrior;
70 sqlite3ExprListDelete(db, p->pEList);
71 sqlite3SrcListDelete(db, p->pSrc);
72 sqlite3ExprDelete(db, p->pWhere);
73 sqlite3ExprListDelete(db, p->pGroupBy);
74 sqlite3ExprDelete(db, p->pHaving);
75 sqlite3ExprListDelete(db, p->pOrderBy);
76 sqlite3ExprDelete(db, p->pLimit);
77 sqlite3ExprDelete(db, p->pOffset);
78 if( p->pWith ) sqlite3WithDelete(db, p->pWith);
79 if( bFree ) sqlite3DbFreeNN(db, p);
80 p = pPrior;
81 bFree = 1;
82 }
83 }
84
85 /*
86 ** Initialize a SelectDest structure.
87 */
sqlite3SelectDestInit(SelectDest * pDest,int eDest,int iParm)88 void sqlite3SelectDestInit(SelectDest *pDest, int eDest, int iParm){
89 pDest->eDest = (u8)eDest;
90 pDest->iSDParm = iParm;
91 pDest->zAffSdst = 0;
92 pDest->iSdst = 0;
93 pDest->nSdst = 0;
94 }
95
96
97 /*
98 ** Allocate a new Select structure and return a pointer to that
99 ** structure.
100 */
sqlite3SelectNew(Parse * pParse,ExprList * pEList,SrcList * pSrc,Expr * pWhere,ExprList * pGroupBy,Expr * pHaving,ExprList * pOrderBy,u32 selFlags,Expr * pLimit,Expr * pOffset)101 Select *sqlite3SelectNew(
102 Parse *pParse, /* Parsing context */
103 ExprList *pEList, /* which columns to include in the result */
104 SrcList *pSrc, /* the FROM clause -- which tables to scan */
105 Expr *pWhere, /* the WHERE clause */
106 ExprList *pGroupBy, /* the GROUP BY clause */
107 Expr *pHaving, /* the HAVING clause */
108 ExprList *pOrderBy, /* the ORDER BY clause */
109 u32 selFlags, /* Flag parameters, such as SF_Distinct */
110 Expr *pLimit, /* LIMIT value. NULL means not used */
111 Expr *pOffset /* OFFSET value. NULL means no offset */
112 ){
113 Select *pNew;
114 Select standin;
115 pNew = sqlite3DbMallocRawNN(pParse->db, sizeof(*pNew) );
116 if( pNew==0 ){
117 assert( pParse->db->mallocFailed );
118 pNew = &standin;
119 }
120 if( pEList==0 ){
121 pEList = sqlite3ExprListAppend(pParse, 0, sqlite3Expr(pParse->db,TK_ASTERISK,0));
122 }
123 pNew->pEList = pEList;
124 pNew->op = TK_SELECT;
125 pNew->selFlags = selFlags;
126 pNew->iLimit = 0;
127 pNew->iOffset = 0;
128 #if SELECTTRACE_ENABLED
129 pNew->zSelName[0] = 0;
130 #endif
131 pNew->addrOpenEphm[0] = -1;
132 pNew->addrOpenEphm[1] = -1;
133 pNew->nSelectRow = 0;
134 if( pSrc==0 ) pSrc = sqlite3DbMallocZero(pParse->db, sizeof(*pSrc));
135 pNew->pSrc = pSrc;
136 pNew->pWhere = pWhere;
137 pNew->pGroupBy = pGroupBy;
138 pNew->pHaving = pHaving;
139 pNew->pOrderBy = pOrderBy;
140 pNew->pPrior = 0;
141 pNew->pNext = 0;
142 pNew->pLimit = pLimit;
143 pNew->pOffset = pOffset;
144 pNew->pWith = 0;
145 assert( pOffset==0 || pLimit!=0 || pParse->nErr>0 || pParse->db->mallocFailed!=0 );
146 if( pParse->db->mallocFailed ) {
147 clearSelect(pParse->db, pNew, pNew!=&standin);
148 pNew = 0;
149 }else{
150 assert( pNew->pSrc!=0 || pParse->nErr>0 );
151 }
152 assert( pNew!=&standin );
153 return pNew;
154 }
155
156 #if SELECTTRACE_ENABLED
157 /*
158 ** Set the name of a Select object
159 */
sqlite3SelectSetName(Select * p,const char * zName)160 void sqlite3SelectSetName(Select *p, const char *zName){
161 if( p && zName ){
162 sqlite3_snprintf(sizeof(p->zSelName), p->zSelName, "%s", zName);
163 }
164 }
165 #endif
166
167
168 /*
169 ** Delete the given Select structure and all of its substructures.
170 */
sqlite3SelectDelete(sqlite3 * db,Select * p)171 void sqlite3SelectDelete(sqlite3 *db, Select *p){
172 if( p ) clearSelect(db, p, 1);
173 }
174
175 /*
176 ** Return a pointer to the right-most SELECT statement in a compound.
177 */
findRightmost(Select * p)178 static Select *findRightmost(Select *p){
179 while( p->pNext ) p = p->pNext;
180 return p;
181 }
182
183 /*
184 ** Given 1 to 3 identifiers preceding the JOIN keyword, determine the
185 ** type of join. Return an integer constant that expresses that type
186 ** in terms of the following bit values:
187 **
188 ** JT_INNER
189 ** JT_CROSS
190 ** JT_OUTER
191 ** JT_NATURAL
192 ** JT_LEFT
193 ** JT_RIGHT
194 **
195 ** A full outer join is the combination of JT_LEFT and JT_RIGHT.
196 **
197 ** If an illegal or unsupported join type is seen, then still return
198 ** a join type, but put an error in the pParse structure.
199 */
sqlite3JoinType(Parse * pParse,Token * pA,Token * pB,Token * pC)200 int sqlite3JoinType(Parse *pParse, Token *pA, Token *pB, Token *pC){
201 int jointype = 0;
202 Token *apAll[3];
203 Token *p;
204 /* 0123456789 123456789 123456789 123 */
205 static const char zKeyText[] = "naturaleftouterightfullinnercross";
206 static const struct {
207 u8 i; /* Beginning of keyword text in zKeyText[] */
208 u8 nChar; /* Length of the keyword in characters */
209 u8 code; /* Join type mask */
210 } aKeyword[] = {
211 /* natural */ { 0, 7, JT_NATURAL },
212 /* left */ { 6, 4, JT_LEFT|JT_OUTER },
213 /* outer */ { 10, 5, JT_OUTER },
214 /* right */ { 14, 5, JT_RIGHT|JT_OUTER },
215 /* full */ { 19, 4, JT_LEFT|JT_RIGHT|JT_OUTER },
216 /* inner */ { 23, 5, JT_INNER },
217 /* cross */ { 28, 5, JT_INNER|JT_CROSS },
218 };
219 int i, j;
220 apAll[0] = pA;
221 apAll[1] = pB;
222 apAll[2] = pC;
223 for(i=0; i<3 && apAll[i]; i++){
224 p = apAll[i];
225 for(j=0; j<ArraySize(aKeyword); j++){
226 if( p->n==aKeyword[j].nChar
227 && sqlite3StrNICmp((char*)p->z, &zKeyText[aKeyword[j].i], p->n)==0 ){
228 jointype |= aKeyword[j].code;
229 break;
230 }
231 }
232 testcase( j==0 || j==1 || j==2 || j==3 || j==4 || j==5 || j==6 );
233 if( j>=ArraySize(aKeyword) ){
234 jointype |= JT_ERROR;
235 break;
236 }
237 }
238 if(
239 (jointype & (JT_INNER|JT_OUTER))==(JT_INNER|JT_OUTER) ||
240 (jointype & JT_ERROR)!=0
241 ){
242 const char *zSp = " ";
243 assert( pB!=0 );
244 if( pC==0 ){ zSp++; }
245 sqlite3ErrorMsg(pParse, "unknown or unsupported join type: "
246 "%T %T%s%T", pA, pB, zSp, pC);
247 jointype = JT_INNER;
248 }else if( (jointype & JT_OUTER)!=0
249 && (jointype & (JT_LEFT|JT_RIGHT))!=JT_LEFT ){
250 sqlite3ErrorMsg(pParse,
251 "RIGHT and FULL OUTER JOINs are not currently supported");
252 jointype = JT_INNER;
253 }
254 return jointype;
255 }
256
257 /*
258 ** Return the index of a column in a table. Return -1 if the column
259 ** is not contained in the table.
260 */
columnIndex(Table * pTab,const char * zCol)261 static int columnIndex(Table *pTab, const char *zCol){
262 int i;
263 for(i=0; i<pTab->nCol; i++){
264 if( sqlite3StrICmp(pTab->aCol[i].zName, zCol)==0 ) return i;
265 }
266 return -1;
267 }
268
269 /*
270 ** Search the first N tables in pSrc, from left to right, looking for a
271 ** table that has a column named zCol.
272 **
273 ** When found, set *piTab and *piCol to the table index and column index
274 ** of the matching column and return TRUE.
275 **
276 ** If not found, return FALSE.
277 */
tableAndColumnIndex(SrcList * pSrc,int N,const char * zCol,int * piTab,int * piCol)278 static int tableAndColumnIndex(
279 SrcList *pSrc, /* Array of tables to search */
280 int N, /* Number of tables in pSrc->a[] to search */
281 const char *zCol, /* Name of the column we are looking for */
282 int *piTab, /* Write index of pSrc->a[] here */
283 int *piCol /* Write index of pSrc->a[*piTab].pTab->aCol[] here */
284 ){
285 int i; /* For looping over tables in pSrc */
286 int iCol; /* Index of column matching zCol */
287
288 assert( (piTab==0)==(piCol==0) ); /* Both or neither are NULL */
289 for(i=0; i<N; i++){
290 iCol = columnIndex(pSrc->a[i].pTab, zCol);
291 if( iCol>=0 ){
292 if( piTab ){
293 *piTab = i;
294 *piCol = iCol;
295 }
296 return 1;
297 }
298 }
299 return 0;
300 }
301
302 /*
303 ** This function is used to add terms implied by JOIN syntax to the
304 ** WHERE clause expression of a SELECT statement. The new term, which
305 ** is ANDed with the existing WHERE clause, is of the form:
306 **
307 ** (tab1.col1 = tab2.col2)
308 **
309 ** where tab1 is the iSrc'th table in SrcList pSrc and tab2 is the
310 ** (iSrc+1)'th. Column col1 is column iColLeft of tab1, and col2 is
311 ** column iColRight of tab2.
312 */
addWhereTerm(Parse * pParse,SrcList * pSrc,int iLeft,int iColLeft,int iRight,int iColRight,int isOuterJoin,Expr ** ppWhere)313 static void addWhereTerm(
314 Parse *pParse, /* Parsing context */
315 SrcList *pSrc, /* List of tables in FROM clause */
316 int iLeft, /* Index of first table to join in pSrc */
317 int iColLeft, /* Index of column in first table */
318 int iRight, /* Index of second table in pSrc */
319 int iColRight, /* Index of column in second table */
320 int isOuterJoin, /* True if this is an OUTER join */
321 Expr **ppWhere /* IN/OUT: The WHERE clause to add to */
322 ){
323 sqlite3 *db = pParse->db;
324 Expr *pE1;
325 Expr *pE2;
326 Expr *pEq;
327
328 assert( iLeft<iRight );
329 assert( pSrc->nSrc>iRight );
330 assert( pSrc->a[iLeft].pTab );
331 assert( pSrc->a[iRight].pTab );
332
333 pE1 = sqlite3CreateColumnExpr(db, pSrc, iLeft, iColLeft);
334 pE2 = sqlite3CreateColumnExpr(db, pSrc, iRight, iColRight);
335
336 pEq = sqlite3PExpr(pParse, TK_EQ, pE1, pE2);
337 if( pEq && isOuterJoin ){
338 ExprSetProperty(pEq, EP_FromJoin);
339 assert( !ExprHasProperty(pEq, EP_TokenOnly|EP_Reduced) );
340 ExprSetVVAProperty(pEq, EP_NoReduce);
341 pEq->iRightJoinTable = (i16)pE2->iTable;
342 }
343 *ppWhere = sqlite3ExprAnd(db, *ppWhere, pEq);
344 }
345
346 /*
347 ** Set the EP_FromJoin property on all terms of the given expression.
348 ** And set the Expr.iRightJoinTable to iTable for every term in the
349 ** expression.
350 **
351 ** The EP_FromJoin property is used on terms of an expression to tell
352 ** the LEFT OUTER JOIN processing logic that this term is part of the
353 ** join restriction specified in the ON or USING clause and not a part
354 ** of the more general WHERE clause. These terms are moved over to the
355 ** WHERE clause during join processing but we need to remember that they
356 ** originated in the ON or USING clause.
357 **
358 ** The Expr.iRightJoinTable tells the WHERE clause processing that the
359 ** expression depends on table iRightJoinTable even if that table is not
360 ** explicitly mentioned in the expression. That information is needed
361 ** for cases like this:
362 **
363 ** SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.b AND t1.x=5
364 **
365 ** The where clause needs to defer the handling of the t1.x=5
366 ** term until after the t2 loop of the join. In that way, a
367 ** NULL t2 row will be inserted whenever t1.x!=5. If we do not
368 ** defer the handling of t1.x=5, it will be processed immediately
369 ** after the t1 loop and rows with t1.x!=5 will never appear in
370 ** the output, which is incorrect.
371 */
setJoinExpr(Expr * p,int iTable)372 static void setJoinExpr(Expr *p, int iTable){
373 while( p ){
374 ExprSetProperty(p, EP_FromJoin);
375 assert( !ExprHasProperty(p, EP_TokenOnly|EP_Reduced) );
376 ExprSetVVAProperty(p, EP_NoReduce);
377 p->iRightJoinTable = (i16)iTable;
378 if( p->op==TK_FUNCTION && p->x.pList ){
379 int i;
380 for(i=0; i<p->x.pList->nExpr; i++){
381 setJoinExpr(p->x.pList->a[i].pExpr, iTable);
382 }
383 }
384 setJoinExpr(p->pLeft, iTable);
385 p = p->pRight;
386 }
387 }
388
389 /*
390 ** This routine processes the join information for a SELECT statement.
391 ** ON and USING clauses are converted into extra terms of the WHERE clause.
392 ** NATURAL joins also create extra WHERE clause terms.
393 **
394 ** The terms of a FROM clause are contained in the Select.pSrc structure.
395 ** The left most table is the first entry in Select.pSrc. The right-most
396 ** table is the last entry. The join operator is held in the entry to
397 ** the left. Thus entry 0 contains the join operator for the join between
398 ** entries 0 and 1. Any ON or USING clauses associated with the join are
399 ** also attached to the left entry.
400 **
401 ** This routine returns the number of errors encountered.
402 */
sqliteProcessJoin(Parse * pParse,Select * p)403 static int sqliteProcessJoin(Parse *pParse, Select *p){
404 SrcList *pSrc; /* All tables in the FROM clause */
405 int i, j; /* Loop counters */
406 struct SrcList_item *pLeft; /* Left table being joined */
407 struct SrcList_item *pRight; /* Right table being joined */
408
409 pSrc = p->pSrc;
410 pLeft = &pSrc->a[0];
411 pRight = &pLeft[1];
412 for(i=0; i<pSrc->nSrc-1; i++, pRight++, pLeft++){
413 Table *pLeftTab = pLeft->pTab;
414 Table *pRightTab = pRight->pTab;
415 int isOuter;
416
417 if( NEVER(pLeftTab==0 || pRightTab==0) ) continue;
418 isOuter = (pRight->fg.jointype & JT_OUTER)!=0;
419
420 /* When the NATURAL keyword is present, add WHERE clause terms for
421 ** every column that the two tables have in common.
422 */
423 if( pRight->fg.jointype & JT_NATURAL ){
424 if( pRight->pOn || pRight->pUsing ){
425 sqlite3ErrorMsg(pParse, "a NATURAL join may not have "
426 "an ON or USING clause", 0);
427 return 1;
428 }
429 for(j=0; j<pRightTab->nCol; j++){
430 char *zName; /* Name of column in the right table */
431 int iLeft; /* Matching left table */
432 int iLeftCol; /* Matching column in the left table */
433
434 zName = pRightTab->aCol[j].zName;
435 if( tableAndColumnIndex(pSrc, i+1, zName, &iLeft, &iLeftCol) ){
436 addWhereTerm(pParse, pSrc, iLeft, iLeftCol, i+1, j,
437 isOuter, &p->pWhere);
438 }
439 }
440 }
441
442 /* Disallow both ON and USING clauses in the same join
443 */
444 if( pRight->pOn && pRight->pUsing ){
445 sqlite3ErrorMsg(pParse, "cannot have both ON and USING "
446 "clauses in the same join");
447 return 1;
448 }
449
450 /* Add the ON clause to the end of the WHERE clause, connected by
451 ** an AND operator.
452 */
453 if( pRight->pOn ){
454 if( isOuter ) setJoinExpr(pRight->pOn, pRight->iCursor);
455 p->pWhere = sqlite3ExprAnd(pParse->db, p->pWhere, pRight->pOn);
456 pRight->pOn = 0;
457 }
458
459 /* Create extra terms on the WHERE clause for each column named
460 ** in the USING clause. Example: If the two tables to be joined are
461 ** A and B and the USING clause names X, Y, and Z, then add this
462 ** to the WHERE clause: A.X=B.X AND A.Y=B.Y AND A.Z=B.Z
463 ** Report an error if any column mentioned in the USING clause is
464 ** not contained in both tables to be joined.
465 */
466 if( pRight->pUsing ){
467 IdList *pList = pRight->pUsing;
468 for(j=0; j<pList->nId; j++){
469 char *zName; /* Name of the term in the USING clause */
470 int iLeft; /* Table on the left with matching column name */
471 int iLeftCol; /* Column number of matching column on the left */
472 int iRightCol; /* Column number of matching column on the right */
473
474 zName = pList->a[j].zName;
475 iRightCol = columnIndex(pRightTab, zName);
476 if( iRightCol<0
477 || !tableAndColumnIndex(pSrc, i+1, zName, &iLeft, &iLeftCol)
478 ){
479 sqlite3ErrorMsg(pParse, "cannot join using column %s - column "
480 "not present in both tables", zName);
481 return 1;
482 }
483 addWhereTerm(pParse, pSrc, iLeft, iLeftCol, i+1, iRightCol,
484 isOuter, &p->pWhere);
485 }
486 }
487 }
488 return 0;
489 }
490
491 /* Forward reference */
492 static KeyInfo *keyInfoFromExprList(
493 Parse *pParse, /* Parsing context */
494 ExprList *pList, /* Form the KeyInfo object from this ExprList */
495 int iStart, /* Begin with this column of pList */
496 int nExtra /* Add this many extra columns to the end */
497 );
498
499 /*
500 ** Generate code that will push the record in registers regData
501 ** through regData+nData-1 onto the sorter.
502 */
pushOntoSorter(Parse * pParse,SortCtx * pSort,Select * pSelect,int regData,int regOrigData,int nData,int nPrefixReg)503 static void pushOntoSorter(
504 Parse *pParse, /* Parser context */
505 SortCtx *pSort, /* Information about the ORDER BY clause */
506 Select *pSelect, /* The whole SELECT statement */
507 int regData, /* First register holding data to be sorted */
508 int regOrigData, /* First register holding data before packing */
509 int nData, /* Number of elements in the data array */
510 int nPrefixReg /* No. of reg prior to regData available for use */
511 ){
512 Vdbe *v = pParse->pVdbe; /* Stmt under construction */
513 int bSeq = ((pSort->sortFlags & SORTFLAG_UseSorter)==0);
514 int nExpr = pSort->pOrderBy->nExpr; /* No. of ORDER BY terms */
515 int nBase = nExpr + bSeq + nData; /* Fields in sorter record */
516 int regBase; /* Regs for sorter record */
517 int regRecord = ++pParse->nMem; /* Assembled sorter record */
518 int nOBSat = pSort->nOBSat; /* ORDER BY terms to skip */
519 int op; /* Opcode to add sorter record to sorter */
520 int iLimit; /* LIMIT counter */
521
522 assert( bSeq==0 || bSeq==1 );
523 assert( nData==1 || regData==regOrigData || regOrigData==0 );
524 if( nPrefixReg ){
525 assert( nPrefixReg==nExpr+bSeq );
526 regBase = regData - nExpr - bSeq;
527 }else{
528 regBase = pParse->nMem + 1;
529 pParse->nMem += nBase;
530 }
531 assert( pSelect->iOffset==0 || pSelect->iLimit!=0 );
532 iLimit = pSelect->iOffset ? pSelect->iOffset+1 : pSelect->iLimit;
533 pSort->labelDone = sqlite3VdbeMakeLabel(v);
534 sqlite3ExprCodeExprList(pParse, pSort->pOrderBy, regBase, regOrigData,
535 SQLITE_ECEL_DUP | (regOrigData? SQLITE_ECEL_REF : 0));
536 if( bSeq ){
537 sqlite3VdbeAddOp2(v, OP_Sequence, pSort->iECursor, regBase+nExpr);
538 }
539 if( nPrefixReg==0 && nData>0 ){
540 sqlite3ExprCodeMove(pParse, regData, regBase+nExpr+bSeq, nData);
541 }
542 sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase+nOBSat, nBase-nOBSat, regRecord);
543 if( nOBSat>0 ){
544 int regPrevKey; /* The first nOBSat columns of the previous row */
545 int addrFirst; /* Address of the OP_IfNot opcode */
546 int addrJmp; /* Address of the OP_Jump opcode */
547 VdbeOp *pOp; /* Opcode that opens the sorter */
548 int nKey; /* Number of sorting key columns, including OP_Sequence */
549 KeyInfo *pKI; /* Original KeyInfo on the sorter table */
550
551 regPrevKey = pParse->nMem+1;
552 pParse->nMem += pSort->nOBSat;
553 nKey = nExpr - pSort->nOBSat + bSeq;
554 if( bSeq ){
555 addrFirst = sqlite3VdbeAddOp1(v, OP_IfNot, regBase+nExpr);
556 }else{
557 addrFirst = sqlite3VdbeAddOp1(v, OP_SequenceTest, pSort->iECursor);
558 }
559 VdbeCoverage(v);
560 sqlite3VdbeAddOp3(v, OP_Compare, regPrevKey, regBase, pSort->nOBSat);
561 pOp = sqlite3VdbeGetOp(v, pSort->addrSortIndex);
562 if( pParse->db->mallocFailed ) return;
563 pOp->p2 = nKey + nData;
564 pKI = pOp->p4.pKeyInfo;
565 memset(pKI->aSortOrder, 0, pKI->nField); /* Makes OP_Jump below testable */
566 sqlite3VdbeChangeP4(v, -1, (char*)pKI, P4_KEYINFO);
567 testcase( pKI->nXField>2 );
568 pOp->p4.pKeyInfo = keyInfoFromExprList(pParse, pSort->pOrderBy, nOBSat,
569 pKI->nXField-1);
570 addrJmp = sqlite3VdbeCurrentAddr(v);
571 sqlite3VdbeAddOp3(v, OP_Jump, addrJmp+1, 0, addrJmp+1); VdbeCoverage(v);
572 pSort->labelBkOut = sqlite3VdbeMakeLabel(v);
573 pSort->regReturn = ++pParse->nMem;
574 sqlite3VdbeAddOp2(v, OP_Gosub, pSort->regReturn, pSort->labelBkOut);
575 sqlite3VdbeAddOp1(v, OP_ResetSorter, pSort->iECursor);
576 if( iLimit ){
577 sqlite3VdbeAddOp2(v, OP_IfNot, iLimit, pSort->labelDone);
578 VdbeCoverage(v);
579 }
580 sqlite3VdbeJumpHere(v, addrFirst);
581 sqlite3ExprCodeMove(pParse, regBase, regPrevKey, pSort->nOBSat);
582 sqlite3VdbeJumpHere(v, addrJmp);
583 }
584 if( pSort->sortFlags & SORTFLAG_UseSorter ){
585 op = OP_SorterInsert;
586 }else{
587 op = OP_IdxInsert;
588 }
589 sqlite3VdbeAddOp4Int(v, op, pSort->iECursor, regRecord,
590 regBase+nOBSat, nBase-nOBSat);
591 if( iLimit ){
592 int addr;
593 int r1 = 0;
594 /* Fill the sorter until it contains LIMIT+OFFSET entries. (The iLimit
595 ** register is initialized with value of LIMIT+OFFSET.) After the sorter
596 ** fills up, delete the least entry in the sorter after each insert.
597 ** Thus we never hold more than the LIMIT+OFFSET rows in memory at once */
598 addr = sqlite3VdbeAddOp1(v, OP_IfNotZero, iLimit); VdbeCoverage(v);
599 sqlite3VdbeAddOp1(v, OP_Last, pSort->iECursor);
600 if( pSort->bOrderedInnerLoop ){
601 r1 = ++pParse->nMem;
602 sqlite3VdbeAddOp3(v, OP_Column, pSort->iECursor, nExpr, r1);
603 VdbeComment((v, "seq"));
604 }
605 sqlite3VdbeAddOp1(v, OP_Delete, pSort->iECursor);
606 if( pSort->bOrderedInnerLoop ){
607 /* If the inner loop is driven by an index such that values from
608 ** the same iteration of the inner loop are in sorted order, then
609 ** immediately jump to the next iteration of an inner loop if the
610 ** entry from the current iteration does not fit into the top
611 ** LIMIT+OFFSET entries of the sorter. */
612 int iBrk = sqlite3VdbeCurrentAddr(v) + 2;
613 sqlite3VdbeAddOp3(v, OP_Eq, regBase+nExpr, iBrk, r1);
614 sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);
615 VdbeCoverage(v);
616 }
617 sqlite3VdbeJumpHere(v, addr);
618 }
619 }
620
621 /*
622 ** Add code to implement the OFFSET
623 */
codeOffset(Vdbe * v,int iOffset,int iContinue)624 static void codeOffset(
625 Vdbe *v, /* Generate code into this VM */
626 int iOffset, /* Register holding the offset counter */
627 int iContinue /* Jump here to skip the current record */
628 ){
629 if( iOffset>0 ){
630 sqlite3VdbeAddOp3(v, OP_IfPos, iOffset, iContinue, 1); VdbeCoverage(v);
631 VdbeComment((v, "OFFSET"));
632 }
633 }
634
635 /*
636 ** Add code that will check to make sure the N registers starting at iMem
637 ** form a distinct entry. iTab is a sorting index that holds previously
638 ** seen combinations of the N values. A new entry is made in iTab
639 ** if the current N values are new.
640 **
641 ** A jump to addrRepeat is made and the N+1 values are popped from the
642 ** stack if the top N elements are not distinct.
643 */
codeDistinct(Parse * pParse,int iTab,int addrRepeat,int N,int iMem)644 static void codeDistinct(
645 Parse *pParse, /* Parsing and code generating context */
646 int iTab, /* A sorting index used to test for distinctness */
647 int addrRepeat, /* Jump to here if not distinct */
648 int N, /* Number of elements */
649 int iMem /* First element */
650 ){
651 Vdbe *v;
652 int r1;
653
654 v = pParse->pVdbe;
655 r1 = sqlite3GetTempReg(pParse);
656 sqlite3VdbeAddOp4Int(v, OP_Found, iTab, addrRepeat, iMem, N); VdbeCoverage(v);
657 sqlite3VdbeAddOp3(v, OP_MakeRecord, iMem, N, r1);
658 sqlite3VdbeAddOp4Int(v, OP_IdxInsert, iTab, r1, iMem, N);
659 sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);
660 sqlite3ReleaseTempReg(pParse, r1);
661 }
662
663 /*
664 ** This routine generates the code for the inside of the inner loop
665 ** of a SELECT.
666 **
667 ** If srcTab is negative, then the pEList expressions
668 ** are evaluated in order to get the data for this row. If srcTab is
669 ** zero or more, then data is pulled from srcTab and pEList is used only
670 ** to get the number of columns and the collation sequence for each column.
671 */
selectInnerLoop(Parse * pParse,Select * p,ExprList * pEList,int srcTab,SortCtx * pSort,DistinctCtx * pDistinct,SelectDest * pDest,int iContinue,int iBreak)672 static void selectInnerLoop(
673 Parse *pParse, /* The parser context */
674 Select *p, /* The complete select statement being coded */
675 ExprList *pEList, /* List of values being extracted */
676 int srcTab, /* Pull data from this table */
677 SortCtx *pSort, /* If not NULL, info on how to process ORDER BY */
678 DistinctCtx *pDistinct, /* If not NULL, info on how to process DISTINCT */
679 SelectDest *pDest, /* How to dispose of the results */
680 int iContinue, /* Jump here to continue with next row */
681 int iBreak /* Jump here to break out of the inner loop */
682 ){
683 Vdbe *v = pParse->pVdbe;
684 int i;
685 int hasDistinct; /* True if the DISTINCT keyword is present */
686 int eDest = pDest->eDest; /* How to dispose of results */
687 int iParm = pDest->iSDParm; /* First argument to disposal method */
688 int nResultCol; /* Number of result columns */
689 int nPrefixReg = 0; /* Number of extra registers before regResult */
690
691 /* Usually, regResult is the first cell in an array of memory cells
692 ** containing the current result row. In this case regOrig is set to the
693 ** same value. However, if the results are being sent to the sorter, the
694 ** values for any expressions that are also part of the sort-key are omitted
695 ** from this array. In this case regOrig is set to zero. */
696 int regResult; /* Start of memory holding current results */
697 int regOrig; /* Start of memory holding full result (or 0) */
698
699 assert( v );
700 assert( pEList!=0 );
701 hasDistinct = pDistinct ? pDistinct->eTnctType : WHERE_DISTINCT_NOOP;
702 if( pSort && pSort->pOrderBy==0 ) pSort = 0;
703 if( pSort==0 && !hasDistinct ){
704 assert( iContinue!=0 );
705 codeOffset(v, p->iOffset, iContinue);
706 }
707
708 /* Pull the requested columns.
709 */
710 nResultCol = pEList->nExpr;
711
712 if( pDest->iSdst==0 ){
713 if( pSort ){
714 nPrefixReg = pSort->pOrderBy->nExpr;
715 if( !(pSort->sortFlags & SORTFLAG_UseSorter) ) nPrefixReg++;
716 pParse->nMem += nPrefixReg;
717 }
718 pDest->iSdst = pParse->nMem+1;
719 pParse->nMem += nResultCol;
720 }else if( pDest->iSdst+nResultCol > pParse->nMem ){
721 /* This is an error condition that can result, for example, when a SELECT
722 ** on the right-hand side of an INSERT contains more result columns than
723 ** there are columns in the table on the left. The error will be caught
724 ** and reported later. But we need to make sure enough memory is allocated
725 ** to avoid other spurious errors in the meantime. */
726 pParse->nMem += nResultCol;
727 }
728 pDest->nSdst = nResultCol;
729 regOrig = regResult = pDest->iSdst;
730 if( srcTab>=0 ){
731 for(i=0; i<nResultCol; i++){
732 sqlite3VdbeAddOp3(v, OP_Column, srcTab, i, regResult+i);
733 VdbeComment((v, "%s", pEList->a[i].zName));
734 }
735 }else if( eDest!=SRT_Exists ){
736 /* If the destination is an EXISTS(...) expression, the actual
737 ** values returned by the SELECT are not required.
738 */
739 u8 ecelFlags;
740 if( eDest==SRT_Mem || eDest==SRT_Output || eDest==SRT_Coroutine ){
741 ecelFlags = SQLITE_ECEL_DUP;
742 }else{
743 ecelFlags = 0;
744 }
745 if( pSort && hasDistinct==0 && eDest!=SRT_EphemTab && eDest!=SRT_Table ){
746 /* For each expression in pEList that is a copy of an expression in
747 ** the ORDER BY clause (pSort->pOrderBy), set the associated
748 ** iOrderByCol value to one more than the index of the ORDER BY
749 ** expression within the sort-key that pushOntoSorter() will generate.
750 ** This allows the pEList field to be omitted from the sorted record,
751 ** saving space and CPU cycles. */
752 ecelFlags |= (SQLITE_ECEL_OMITREF|SQLITE_ECEL_REF);
753 for(i=pSort->nOBSat; i<pSort->pOrderBy->nExpr; i++){
754 int j;
755 if( (j = pSort->pOrderBy->a[i].u.x.iOrderByCol)>0 ){
756 pEList->a[j-1].u.x.iOrderByCol = i+1-pSort->nOBSat;
757 }
758 }
759 regOrig = 0;
760 assert( eDest==SRT_Set || eDest==SRT_Mem
761 || eDest==SRT_Coroutine || eDest==SRT_Output );
762 }
763 nResultCol = sqlite3ExprCodeExprList(pParse,pEList,regResult,0,ecelFlags);
764 }
765
766 /* If the DISTINCT keyword was present on the SELECT statement
767 ** and this row has been seen before, then do not make this row
768 ** part of the result.
769 */
770 if( hasDistinct ){
771 switch( pDistinct->eTnctType ){
772 case WHERE_DISTINCT_ORDERED: {
773 VdbeOp *pOp; /* No longer required OpenEphemeral instr. */
774 int iJump; /* Jump destination */
775 int regPrev; /* Previous row content */
776
777 /* Allocate space for the previous row */
778 regPrev = pParse->nMem+1;
779 pParse->nMem += nResultCol;
780
781 /* Change the OP_OpenEphemeral coded earlier to an OP_Null
782 ** sets the MEM_Cleared bit on the first register of the
783 ** previous value. This will cause the OP_Ne below to always
784 ** fail on the first iteration of the loop even if the first
785 ** row is all NULLs.
786 */
787 sqlite3VdbeChangeToNoop(v, pDistinct->addrTnct);
788 pOp = sqlite3VdbeGetOp(v, pDistinct->addrTnct);
789 pOp->opcode = OP_Null;
790 pOp->p1 = 1;
791 pOp->p2 = regPrev;
792
793 iJump = sqlite3VdbeCurrentAddr(v) + nResultCol;
794 for(i=0; i<nResultCol; i++){
795 CollSeq *pColl = sqlite3ExprCollSeq(pParse, pEList->a[i].pExpr);
796 if( i<nResultCol-1 ){
797 sqlite3VdbeAddOp3(v, OP_Ne, regResult+i, iJump, regPrev+i);
798 VdbeCoverage(v);
799 }else{
800 sqlite3VdbeAddOp3(v, OP_Eq, regResult+i, iContinue, regPrev+i);
801 VdbeCoverage(v);
802 }
803 sqlite3VdbeChangeP4(v, -1, (const char *)pColl, P4_COLLSEQ);
804 sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);
805 }
806 assert( sqlite3VdbeCurrentAddr(v)==iJump || pParse->db->mallocFailed );
807 sqlite3VdbeAddOp3(v, OP_Copy, regResult, regPrev, nResultCol-1);
808 break;
809 }
810
811 case WHERE_DISTINCT_UNIQUE: {
812 sqlite3VdbeChangeToNoop(v, pDistinct->addrTnct);
813 break;
814 }
815
816 default: {
817 assert( pDistinct->eTnctType==WHERE_DISTINCT_UNORDERED );
818 codeDistinct(pParse, pDistinct->tabTnct, iContinue, nResultCol,
819 regResult);
820 break;
821 }
822 }
823 if( pSort==0 ){
824 codeOffset(v, p->iOffset, iContinue);
825 }
826 }
827
828 switch( eDest ){
829 /* In this mode, write each query result to the key of the temporary
830 ** table iParm.
831 */
832 #ifndef SQLITE_OMIT_COMPOUND_SELECT
833 case SRT_Union: {
834 int r1;
835 r1 = sqlite3GetTempReg(pParse);
836 sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r1);
837 sqlite3VdbeAddOp4Int(v, OP_IdxInsert, iParm, r1, regResult, nResultCol);
838 sqlite3ReleaseTempReg(pParse, r1);
839 break;
840 }
841
842 /* Construct a record from the query result, but instead of
843 ** saving that record, use it as a key to delete elements from
844 ** the temporary table iParm.
845 */
846 case SRT_Except: {
847 sqlite3VdbeAddOp3(v, OP_IdxDelete, iParm, regResult, nResultCol);
848 break;
849 }
850 #endif /* SQLITE_OMIT_COMPOUND_SELECT */
851
852 /* Store the result as data using a unique key.
853 */
854 case SRT_Fifo:
855 case SRT_DistFifo:
856 case SRT_Table:
857 case SRT_EphemTab: {
858 int r1 = sqlite3GetTempRange(pParse, nPrefixReg+1);
859 testcase( eDest==SRT_Table );
860 testcase( eDest==SRT_EphemTab );
861 testcase( eDest==SRT_Fifo );
862 testcase( eDest==SRT_DistFifo );
863 sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r1+nPrefixReg);
864 #ifndef SQLITE_OMIT_CTE
865 if( eDest==SRT_DistFifo ){
866 /* If the destination is DistFifo, then cursor (iParm+1) is open
867 ** on an ephemeral index. If the current row is already present
868 ** in the index, do not write it to the output. If not, add the
869 ** current row to the index and proceed with writing it to the
870 ** output table as well. */
871 int addr = sqlite3VdbeCurrentAddr(v) + 4;
872 sqlite3VdbeAddOp4Int(v, OP_Found, iParm+1, addr, r1, 0);
873 VdbeCoverage(v);
874 sqlite3VdbeAddOp4Int(v, OP_IdxInsert, iParm+1, r1,regResult,nResultCol);
875 assert( pSort==0 );
876 }
877 #endif
878 if( pSort ){
879 pushOntoSorter(pParse, pSort, p, r1+nPrefixReg,regResult,1,nPrefixReg);
880 }else{
881 int r2 = sqlite3GetTempReg(pParse);
882 sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, r2);
883 sqlite3VdbeAddOp3(v, OP_Insert, iParm, r1, r2);
884 sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
885 sqlite3ReleaseTempReg(pParse, r2);
886 }
887 sqlite3ReleaseTempRange(pParse, r1, nPrefixReg+1);
888 break;
889 }
890
891 #ifndef SQLITE_OMIT_SUBQUERY
892 /* If we are creating a set for an "expr IN (SELECT ...)" construct,
893 ** then there should be a single item on the stack. Write this
894 ** item into the set table with bogus data.
895 */
896 case SRT_Set: {
897 if( pSort ){
898 /* At first glance you would think we could optimize out the
899 ** ORDER BY in this case since the order of entries in the set
900 ** does not matter. But there might be a LIMIT clause, in which
901 ** case the order does matter */
902 pushOntoSorter(
903 pParse, pSort, p, regResult, regOrig, nResultCol, nPrefixReg);
904 }else{
905 int r1 = sqlite3GetTempReg(pParse);
906 assert( sqlite3Strlen30(pDest->zAffSdst)==nResultCol );
907 sqlite3VdbeAddOp4(v, OP_MakeRecord, regResult, nResultCol,
908 r1, pDest->zAffSdst, nResultCol);
909 sqlite3ExprCacheAffinityChange(pParse, regResult, nResultCol);
910 sqlite3VdbeAddOp4Int(v, OP_IdxInsert, iParm, r1, regResult, nResultCol);
911 sqlite3ReleaseTempReg(pParse, r1);
912 }
913 break;
914 }
915
916 /* If any row exist in the result set, record that fact and abort.
917 */
918 case SRT_Exists: {
919 sqlite3VdbeAddOp2(v, OP_Integer, 1, iParm);
920 /* The LIMIT clause will terminate the loop for us */
921 break;
922 }
923
924 /* If this is a scalar select that is part of an expression, then
925 ** store the results in the appropriate memory cell or array of
926 ** memory cells and break out of the scan loop.
927 */
928 case SRT_Mem: {
929 if( pSort ){
930 assert( nResultCol<=pDest->nSdst );
931 pushOntoSorter(
932 pParse, pSort, p, regResult, regOrig, nResultCol, nPrefixReg);
933 }else{
934 assert( nResultCol==pDest->nSdst );
935 assert( regResult==iParm );
936 /* The LIMIT clause will jump out of the loop for us */
937 }
938 break;
939 }
940 #endif /* #ifndef SQLITE_OMIT_SUBQUERY */
941
942 case SRT_Coroutine: /* Send data to a co-routine */
943 case SRT_Output: { /* Return the results */
944 testcase( eDest==SRT_Coroutine );
945 testcase( eDest==SRT_Output );
946 if( pSort ){
947 pushOntoSorter(pParse, pSort, p, regResult, regOrig, nResultCol,
948 nPrefixReg);
949 }else if( eDest==SRT_Coroutine ){
950 sqlite3VdbeAddOp1(v, OP_Yield, pDest->iSDParm);
951 }else{
952 sqlite3VdbeAddOp2(v, OP_ResultRow, regResult, nResultCol);
953 sqlite3ExprCacheAffinityChange(pParse, regResult, nResultCol);
954 }
955 break;
956 }
957
958 #ifndef SQLITE_OMIT_CTE
959 /* Write the results into a priority queue that is order according to
960 ** pDest->pOrderBy (in pSO). pDest->iSDParm (in iParm) is the cursor for an
961 ** index with pSO->nExpr+2 columns. Build a key using pSO for the first
962 ** pSO->nExpr columns, then make sure all keys are unique by adding a
963 ** final OP_Sequence column. The last column is the record as a blob.
964 */
965 case SRT_DistQueue:
966 case SRT_Queue: {
967 int nKey;
968 int r1, r2, r3;
969 int addrTest = 0;
970 ExprList *pSO;
971 pSO = pDest->pOrderBy;
972 assert( pSO );
973 nKey = pSO->nExpr;
974 r1 = sqlite3GetTempReg(pParse);
975 r2 = sqlite3GetTempRange(pParse, nKey+2);
976 r3 = r2+nKey+1;
977 if( eDest==SRT_DistQueue ){
978 /* If the destination is DistQueue, then cursor (iParm+1) is open
979 ** on a second ephemeral index that holds all values every previously
980 ** added to the queue. */
981 addrTest = sqlite3VdbeAddOp4Int(v, OP_Found, iParm+1, 0,
982 regResult, nResultCol);
983 VdbeCoverage(v);
984 }
985 sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r3);
986 if( eDest==SRT_DistQueue ){
987 sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm+1, r3);
988 sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);
989 }
990 for(i=0; i<nKey; i++){
991 sqlite3VdbeAddOp2(v, OP_SCopy,
992 regResult + pSO->a[i].u.x.iOrderByCol - 1,
993 r2+i);
994 }
995 sqlite3VdbeAddOp2(v, OP_Sequence, iParm, r2+nKey);
996 sqlite3VdbeAddOp3(v, OP_MakeRecord, r2, nKey+2, r1);
997 sqlite3VdbeAddOp4Int(v, OP_IdxInsert, iParm, r1, r2, nKey+2);
998 if( addrTest ) sqlite3VdbeJumpHere(v, addrTest);
999 sqlite3ReleaseTempReg(pParse, r1);
1000 sqlite3ReleaseTempRange(pParse, r2, nKey+2);
1001 break;
1002 }
1003 #endif /* SQLITE_OMIT_CTE */
1004
1005
1006
1007 #if !defined(SQLITE_OMIT_TRIGGER)
1008 /* Discard the results. This is used for SELECT statements inside
1009 ** the body of a TRIGGER. The purpose of such selects is to call
1010 ** user-defined functions that have side effects. We do not care
1011 ** about the actual results of the select.
1012 */
1013 default: {
1014 assert( eDest==SRT_Discard );
1015 break;
1016 }
1017 #endif
1018 }
1019
1020 /* Jump to the end of the loop if the LIMIT is reached. Except, if
1021 ** there is a sorter, in which case the sorter has already limited
1022 ** the output for us.
1023 */
1024 if( pSort==0 && p->iLimit ){
1025 sqlite3VdbeAddOp2(v, OP_DecrJumpZero, p->iLimit, iBreak); VdbeCoverage(v);
1026 }
1027 }
1028
1029 /*
1030 ** Allocate a KeyInfo object sufficient for an index of N key columns and
1031 ** X extra columns.
1032 */
sqlite3KeyInfoAlloc(sqlite3 * db,int N,int X)1033 KeyInfo *sqlite3KeyInfoAlloc(sqlite3 *db, int N, int X){
1034 int nExtra = (N+X)*(sizeof(CollSeq*)+1) - sizeof(CollSeq*);
1035 KeyInfo *p = sqlite3DbMallocRawNN(db, sizeof(KeyInfo) + nExtra);
1036 if( p ){
1037 p->aSortOrder = (u8*)&p->aColl[N+X];
1038 p->nField = (u16)N;
1039 p->nXField = (u16)X;
1040 p->enc = ENC(db);
1041 p->db = db;
1042 p->nRef = 1;
1043 memset(&p[1], 0, nExtra);
1044 }else{
1045 sqlite3OomFault(db);
1046 }
1047 return p;
1048 }
1049
1050 /*
1051 ** Deallocate a KeyInfo object
1052 */
sqlite3KeyInfoUnref(KeyInfo * p)1053 void sqlite3KeyInfoUnref(KeyInfo *p){
1054 if( p ){
1055 assert( p->nRef>0 );
1056 p->nRef--;
1057 if( p->nRef==0 ) sqlite3DbFreeNN(p->db, p);
1058 }
1059 }
1060
1061 /*
1062 ** Make a new pointer to a KeyInfo object
1063 */
sqlite3KeyInfoRef(KeyInfo * p)1064 KeyInfo *sqlite3KeyInfoRef(KeyInfo *p){
1065 if( p ){
1066 assert( p->nRef>0 );
1067 p->nRef++;
1068 }
1069 return p;
1070 }
1071
1072 #ifdef SQLITE_DEBUG
1073 /*
1074 ** Return TRUE if a KeyInfo object can be change. The KeyInfo object
1075 ** can only be changed if this is just a single reference to the object.
1076 **
1077 ** This routine is used only inside of assert() statements.
1078 */
sqlite3KeyInfoIsWriteable(KeyInfo * p)1079 int sqlite3KeyInfoIsWriteable(KeyInfo *p){ return p->nRef==1; }
1080 #endif /* SQLITE_DEBUG */
1081
1082 /*
1083 ** Given an expression list, generate a KeyInfo structure that records
1084 ** the collating sequence for each expression in that expression list.
1085 **
1086 ** If the ExprList is an ORDER BY or GROUP BY clause then the resulting
1087 ** KeyInfo structure is appropriate for initializing a virtual index to
1088 ** implement that clause. If the ExprList is the result set of a SELECT
1089 ** then the KeyInfo structure is appropriate for initializing a virtual
1090 ** index to implement a DISTINCT test.
1091 **
1092 ** Space to hold the KeyInfo structure is obtained from malloc. The calling
1093 ** function is responsible for seeing that this structure is eventually
1094 ** freed.
1095 */
keyInfoFromExprList(Parse * pParse,ExprList * pList,int iStart,int nExtra)1096 static KeyInfo *keyInfoFromExprList(
1097 Parse *pParse, /* Parsing context */
1098 ExprList *pList, /* Form the KeyInfo object from this ExprList */
1099 int iStart, /* Begin with this column of pList */
1100 int nExtra /* Add this many extra columns to the end */
1101 ){
1102 int nExpr;
1103 KeyInfo *pInfo;
1104 struct ExprList_item *pItem;
1105 sqlite3 *db = pParse->db;
1106 int i;
1107
1108 nExpr = pList->nExpr;
1109 pInfo = sqlite3KeyInfoAlloc(db, nExpr-iStart, nExtra+1);
1110 if( pInfo ){
1111 assert( sqlite3KeyInfoIsWriteable(pInfo) );
1112 for(i=iStart, pItem=pList->a+iStart; i<nExpr; i++, pItem++){
1113 CollSeq *pColl;
1114 pColl = sqlite3ExprCollSeq(pParse, pItem->pExpr);
1115 if( !pColl ) pColl = db->pDfltColl;
1116 pInfo->aColl[i-iStart] = pColl;
1117 pInfo->aSortOrder[i-iStart] = pItem->sortOrder;
1118 }
1119 }
1120 return pInfo;
1121 }
1122
1123 /*
1124 ** Name of the connection operator, used for error messages.
1125 */
selectOpName(int id)1126 static const char *selectOpName(int id){
1127 char *z;
1128 switch( id ){
1129 case TK_ALL: z = "UNION ALL"; break;
1130 case TK_INTERSECT: z = "INTERSECT"; break;
1131 case TK_EXCEPT: z = "EXCEPT"; break;
1132 default: z = "UNION"; break;
1133 }
1134 return z;
1135 }
1136
1137 #ifndef SQLITE_OMIT_EXPLAIN
1138 /*
1139 ** Unless an "EXPLAIN QUERY PLAN" command is being processed, this function
1140 ** is a no-op. Otherwise, it adds a single row of output to the EQP result,
1141 ** where the caption is of the form:
1142 **
1143 ** "USE TEMP B-TREE FOR xxx"
1144 **
1145 ** where xxx is one of "DISTINCT", "ORDER BY" or "GROUP BY". Exactly which
1146 ** is determined by the zUsage argument.
1147 */
explainTempTable(Parse * pParse,const char * zUsage)1148 static void explainTempTable(Parse *pParse, const char *zUsage){
1149 if( pParse->explain==2 ){
1150 Vdbe *v = pParse->pVdbe;
1151 char *zMsg = sqlite3MPrintf(pParse->db, "USE TEMP B-TREE FOR %s", zUsage);
1152 sqlite3VdbeAddOp4(v, OP_Explain, pParse->iSelectId, 0, 0, zMsg, P4_DYNAMIC);
1153 }
1154 }
1155
1156 /*
1157 ** Assign expression b to lvalue a. A second, no-op, version of this macro
1158 ** is provided when SQLITE_OMIT_EXPLAIN is defined. This allows the code
1159 ** in sqlite3Select() to assign values to structure member variables that
1160 ** only exist if SQLITE_OMIT_EXPLAIN is not defined without polluting the
1161 ** code with #ifndef directives.
1162 */
1163 # define explainSetInteger(a, b) a = b
1164
1165 #else
1166 /* No-op versions of the explainXXX() functions and macros. */
1167 # define explainTempTable(y,z)
1168 # define explainSetInteger(y,z)
1169 #endif
1170
1171 #if !defined(SQLITE_OMIT_EXPLAIN) && !defined(SQLITE_OMIT_COMPOUND_SELECT)
1172 /*
1173 ** Unless an "EXPLAIN QUERY PLAN" command is being processed, this function
1174 ** is a no-op. Otherwise, it adds a single row of output to the EQP result,
1175 ** where the caption is of one of the two forms:
1176 **
1177 ** "COMPOSITE SUBQUERIES iSub1 and iSub2 (op)"
1178 ** "COMPOSITE SUBQUERIES iSub1 and iSub2 USING TEMP B-TREE (op)"
1179 **
1180 ** where iSub1 and iSub2 are the integers passed as the corresponding
1181 ** function parameters, and op is the text representation of the parameter
1182 ** of the same name. The parameter "op" must be one of TK_UNION, TK_EXCEPT,
1183 ** TK_INTERSECT or TK_ALL. The first form is used if argument bUseTmp is
1184 ** false, or the second form if it is true.
1185 */
explainComposite(Parse * pParse,int op,int iSub1,int iSub2,int bUseTmp)1186 static void explainComposite(
1187 Parse *pParse, /* Parse context */
1188 int op, /* One of TK_UNION, TK_EXCEPT etc. */
1189 int iSub1, /* Subquery id 1 */
1190 int iSub2, /* Subquery id 2 */
1191 int bUseTmp /* True if a temp table was used */
1192 ){
1193 assert( op==TK_UNION || op==TK_EXCEPT || op==TK_INTERSECT || op==TK_ALL );
1194 if( pParse->explain==2 ){
1195 Vdbe *v = pParse->pVdbe;
1196 char *zMsg = sqlite3MPrintf(
1197 pParse->db, "COMPOUND SUBQUERIES %d AND %d %s(%s)", iSub1, iSub2,
1198 bUseTmp?"USING TEMP B-TREE ":"", selectOpName(op)
1199 );
1200 sqlite3VdbeAddOp4(v, OP_Explain, pParse->iSelectId, 0, 0, zMsg, P4_DYNAMIC);
1201 }
1202 }
1203 #else
1204 /* No-op versions of the explainXXX() functions and macros. */
1205 # define explainComposite(v,w,x,y,z)
1206 #endif
1207
1208 /*
1209 ** If the inner loop was generated using a non-null pOrderBy argument,
1210 ** then the results were placed in a sorter. After the loop is terminated
1211 ** we need to run the sorter and output the results. The following
1212 ** routine generates the code needed to do that.
1213 */
generateSortTail(Parse * pParse,Select * p,SortCtx * pSort,int nColumn,SelectDest * pDest)1214 static void generateSortTail(
1215 Parse *pParse, /* Parsing context */
1216 Select *p, /* The SELECT statement */
1217 SortCtx *pSort, /* Information on the ORDER BY clause */
1218 int nColumn, /* Number of columns of data */
1219 SelectDest *pDest /* Write the sorted results here */
1220 ){
1221 Vdbe *v = pParse->pVdbe; /* The prepared statement */
1222 int addrBreak = pSort->labelDone; /* Jump here to exit loop */
1223 int addrContinue = sqlite3VdbeMakeLabel(v); /* Jump here for next cycle */
1224 int addr;
1225 int addrOnce = 0;
1226 int iTab;
1227 ExprList *pOrderBy = pSort->pOrderBy;
1228 int eDest = pDest->eDest;
1229 int iParm = pDest->iSDParm;
1230 int regRow;
1231 int regRowid;
1232 int iCol;
1233 int nKey;
1234 int iSortTab; /* Sorter cursor to read from */
1235 int nSortData; /* Trailing values to read from sorter */
1236 int i;
1237 int bSeq; /* True if sorter record includes seq. no. */
1238 struct ExprList_item *aOutEx = p->pEList->a;
1239
1240 assert( addrBreak<0 );
1241 if( pSort->labelBkOut ){
1242 sqlite3VdbeAddOp2(v, OP_Gosub, pSort->regReturn, pSort->labelBkOut);
1243 sqlite3VdbeGoto(v, addrBreak);
1244 sqlite3VdbeResolveLabel(v, pSort->labelBkOut);
1245 }
1246 iTab = pSort->iECursor;
1247 if( eDest==SRT_Output || eDest==SRT_Coroutine || eDest==SRT_Mem ){
1248 regRowid = 0;
1249 regRow = pDest->iSdst;
1250 nSortData = nColumn;
1251 }else{
1252 regRowid = sqlite3GetTempReg(pParse);
1253 regRow = sqlite3GetTempRange(pParse, nColumn);
1254 nSortData = nColumn;
1255 }
1256 nKey = pOrderBy->nExpr - pSort->nOBSat;
1257 if( pSort->sortFlags & SORTFLAG_UseSorter ){
1258 int regSortOut = ++pParse->nMem;
1259 iSortTab = pParse->nTab++;
1260 if( pSort->labelBkOut ){
1261 addrOnce = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v);
1262 }
1263 sqlite3VdbeAddOp3(v, OP_OpenPseudo, iSortTab, regSortOut, nKey+1+nSortData);
1264 if( addrOnce ) sqlite3VdbeJumpHere(v, addrOnce);
1265 addr = 1 + sqlite3VdbeAddOp2(v, OP_SorterSort, iTab, addrBreak);
1266 VdbeCoverage(v);
1267 codeOffset(v, p->iOffset, addrContinue);
1268 sqlite3VdbeAddOp3(v, OP_SorterData, iTab, regSortOut, iSortTab);
1269 bSeq = 0;
1270 }else{
1271 addr = 1 + sqlite3VdbeAddOp2(v, OP_Sort, iTab, addrBreak); VdbeCoverage(v);
1272 codeOffset(v, p->iOffset, addrContinue);
1273 iSortTab = iTab;
1274 bSeq = 1;
1275 }
1276 for(i=0, iCol=nKey+bSeq; i<nSortData; i++){
1277 int iRead;
1278 if( aOutEx[i].u.x.iOrderByCol ){
1279 iRead = aOutEx[i].u.x.iOrderByCol-1;
1280 }else{
1281 iRead = iCol++;
1282 }
1283 sqlite3VdbeAddOp3(v, OP_Column, iSortTab, iRead, regRow+i);
1284 VdbeComment((v, "%s", aOutEx[i].zName ? aOutEx[i].zName : aOutEx[i].zSpan));
1285 }
1286 switch( eDest ){
1287 case SRT_Table:
1288 case SRT_EphemTab: {
1289 sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, regRowid);
1290 sqlite3VdbeAddOp3(v, OP_Insert, iParm, regRow, regRowid);
1291 sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
1292 break;
1293 }
1294 #ifndef SQLITE_OMIT_SUBQUERY
1295 case SRT_Set: {
1296 assert( nColumn==sqlite3Strlen30(pDest->zAffSdst) );
1297 sqlite3VdbeAddOp4(v, OP_MakeRecord, regRow, nColumn, regRowid,
1298 pDest->zAffSdst, nColumn);
1299 sqlite3ExprCacheAffinityChange(pParse, regRow, nColumn);
1300 sqlite3VdbeAddOp4Int(v, OP_IdxInsert, iParm, regRowid, regRow, nColumn);
1301 break;
1302 }
1303 case SRT_Mem: {
1304 /* The LIMIT clause will terminate the loop for us */
1305 break;
1306 }
1307 #endif
1308 default: {
1309 assert( eDest==SRT_Output || eDest==SRT_Coroutine );
1310 testcase( eDest==SRT_Output );
1311 testcase( eDest==SRT_Coroutine );
1312 if( eDest==SRT_Output ){
1313 sqlite3VdbeAddOp2(v, OP_ResultRow, pDest->iSdst, nColumn);
1314 sqlite3ExprCacheAffinityChange(pParse, pDest->iSdst, nColumn);
1315 }else{
1316 sqlite3VdbeAddOp1(v, OP_Yield, pDest->iSDParm);
1317 }
1318 break;
1319 }
1320 }
1321 if( regRowid ){
1322 if( eDest==SRT_Set ){
1323 sqlite3ReleaseTempRange(pParse, regRow, nColumn);
1324 }else{
1325 sqlite3ReleaseTempReg(pParse, regRow);
1326 }
1327 sqlite3ReleaseTempReg(pParse, regRowid);
1328 }
1329 /* The bottom of the loop
1330 */
1331 sqlite3VdbeResolveLabel(v, addrContinue);
1332 if( pSort->sortFlags & SORTFLAG_UseSorter ){
1333 sqlite3VdbeAddOp2(v, OP_SorterNext, iTab, addr); VdbeCoverage(v);
1334 }else{
1335 sqlite3VdbeAddOp2(v, OP_Next, iTab, addr); VdbeCoverage(v);
1336 }
1337 if( pSort->regReturn ) sqlite3VdbeAddOp1(v, OP_Return, pSort->regReturn);
1338 sqlite3VdbeResolveLabel(v, addrBreak);
1339 }
1340
1341 /*
1342 ** Return a pointer to a string containing the 'declaration type' of the
1343 ** expression pExpr. The string may be treated as static by the caller.
1344 **
1345 ** Also try to estimate the size of the returned value and return that
1346 ** result in *pEstWidth.
1347 **
1348 ** The declaration type is the exact datatype definition extracted from the
1349 ** original CREATE TABLE statement if the expression is a column. The
1350 ** declaration type for a ROWID field is INTEGER. Exactly when an expression
1351 ** is considered a column can be complex in the presence of subqueries. The
1352 ** result-set expression in all of the following SELECT statements is
1353 ** considered a column by this function.
1354 **
1355 ** SELECT col FROM tbl;
1356 ** SELECT (SELECT col FROM tbl;
1357 ** SELECT (SELECT col FROM tbl);
1358 ** SELECT abc FROM (SELECT col AS abc FROM tbl);
1359 **
1360 ** The declaration type for any expression other than a column is NULL.
1361 **
1362 ** This routine has either 3 or 6 parameters depending on whether or not
1363 ** the SQLITE_ENABLE_COLUMN_METADATA compile-time option is used.
1364 */
1365 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1366 # define columnType(A,B,C,D,E,F) columnTypeImpl(A,B,C,D,E,F)
1367 #else /* if !defined(SQLITE_ENABLE_COLUMN_METADATA) */
1368 # define columnType(A,B,C,D,E,F) columnTypeImpl(A,B,F)
1369 #endif
columnTypeImpl(NameContext * pNC,Expr * pExpr,const char ** pzOrigDb,const char ** pzOrigTab,const char ** pzOrigCol,u8 * pEstWidth)1370 static const char *columnTypeImpl(
1371 NameContext *pNC,
1372 Expr *pExpr,
1373 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1374 const char **pzOrigDb,
1375 const char **pzOrigTab,
1376 const char **pzOrigCol,
1377 #endif
1378 u8 *pEstWidth
1379 ){
1380 char const *zType = 0;
1381 int j;
1382 u8 estWidth = 1;
1383 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1384 char const *zOrigDb = 0;
1385 char const *zOrigTab = 0;
1386 char const *zOrigCol = 0;
1387 #endif
1388
1389 assert( pExpr!=0 );
1390 assert( pNC->pSrcList!=0 );
1391 switch( pExpr->op ){
1392 case TK_AGG_COLUMN:
1393 case TK_COLUMN: {
1394 /* The expression is a column. Locate the table the column is being
1395 ** extracted from in NameContext.pSrcList. This table may be real
1396 ** database table or a subquery.
1397 */
1398 Table *pTab = 0; /* Table structure column is extracted from */
1399 Select *pS = 0; /* Select the column is extracted from */
1400 int iCol = pExpr->iColumn; /* Index of column in pTab */
1401 testcase( pExpr->op==TK_AGG_COLUMN );
1402 testcase( pExpr->op==TK_COLUMN );
1403 while( pNC && !pTab ){
1404 SrcList *pTabList = pNC->pSrcList;
1405 for(j=0;j<pTabList->nSrc && pTabList->a[j].iCursor!=pExpr->iTable;j++);
1406 if( j<pTabList->nSrc ){
1407 pTab = pTabList->a[j].pTab;
1408 pS = pTabList->a[j].pSelect;
1409 }else{
1410 pNC = pNC->pNext;
1411 }
1412 }
1413
1414 if( pTab==0 ){
1415 /* At one time, code such as "SELECT new.x" within a trigger would
1416 ** cause this condition to run. Since then, we have restructured how
1417 ** trigger code is generated and so this condition is no longer
1418 ** possible. However, it can still be true for statements like
1419 ** the following:
1420 **
1421 ** CREATE TABLE t1(col INTEGER);
1422 ** SELECT (SELECT t1.col) FROM FROM t1;
1423 **
1424 ** when columnType() is called on the expression "t1.col" in the
1425 ** sub-select. In this case, set the column type to NULL, even
1426 ** though it should really be "INTEGER".
1427 **
1428 ** This is not a problem, as the column type of "t1.col" is never
1429 ** used. When columnType() is called on the expression
1430 ** "(SELECT t1.col)", the correct type is returned (see the TK_SELECT
1431 ** branch below. */
1432 break;
1433 }
1434
1435 assert( pTab && pExpr->pTab==pTab );
1436 if( pS ){
1437 /* The "table" is actually a sub-select or a view in the FROM clause
1438 ** of the SELECT statement. Return the declaration type and origin
1439 ** data for the result-set column of the sub-select.
1440 */
1441 if( iCol>=0 && iCol<pS->pEList->nExpr ){
1442 /* If iCol is less than zero, then the expression requests the
1443 ** rowid of the sub-select or view. This expression is legal (see
1444 ** test case misc2.2.2) - it always evaluates to NULL.
1445 */
1446 NameContext sNC;
1447 Expr *p = pS->pEList->a[iCol].pExpr;
1448 sNC.pSrcList = pS->pSrc;
1449 sNC.pNext = pNC;
1450 sNC.pParse = pNC->pParse;
1451 zType = columnType(&sNC, p,&zOrigDb,&zOrigTab,&zOrigCol, &estWidth);
1452 }
1453 }else if( pTab->pSchema ){
1454 /* A real table */
1455 assert( !pS );
1456 if( iCol<0 ) iCol = pTab->iPKey;
1457 assert( iCol==-1 || (iCol>=0 && iCol<pTab->nCol) );
1458 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1459 if( iCol<0 ){
1460 zType = "INTEGER";
1461 zOrigCol = "rowid";
1462 }else{
1463 zOrigCol = pTab->aCol[iCol].zName;
1464 zType = sqlite3ColumnType(&pTab->aCol[iCol],0);
1465 estWidth = pTab->aCol[iCol].szEst;
1466 }
1467 zOrigTab = pTab->zName;
1468 if( pNC->pParse ){
1469 int iDb = sqlite3SchemaToIndex(pNC->pParse->db, pTab->pSchema);
1470 zOrigDb = pNC->pParse->db->aDb[iDb].zDbSName;
1471 }
1472 #else
1473 if( iCol<0 ){
1474 zType = "INTEGER";
1475 }else{
1476 zType = sqlite3ColumnType(&pTab->aCol[iCol],0);
1477 estWidth = pTab->aCol[iCol].szEst;
1478 }
1479 #endif
1480 }
1481 break;
1482 }
1483 #ifndef SQLITE_OMIT_SUBQUERY
1484 case TK_SELECT: {
1485 /* The expression is a sub-select. Return the declaration type and
1486 ** origin info for the single column in the result set of the SELECT
1487 ** statement.
1488 */
1489 NameContext sNC;
1490 Select *pS = pExpr->x.pSelect;
1491 Expr *p = pS->pEList->a[0].pExpr;
1492 assert( ExprHasProperty(pExpr, EP_xIsSelect) );
1493 sNC.pSrcList = pS->pSrc;
1494 sNC.pNext = pNC;
1495 sNC.pParse = pNC->pParse;
1496 zType = columnType(&sNC, p, &zOrigDb, &zOrigTab, &zOrigCol, &estWidth);
1497 break;
1498 }
1499 #endif
1500 }
1501
1502 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1503 if( pzOrigDb ){
1504 assert( pzOrigTab && pzOrigCol );
1505 *pzOrigDb = zOrigDb;
1506 *pzOrigTab = zOrigTab;
1507 *pzOrigCol = zOrigCol;
1508 }
1509 #endif
1510 if( pEstWidth ) *pEstWidth = estWidth;
1511 return zType;
1512 }
1513
1514 /*
1515 ** Generate code that will tell the VDBE the declaration types of columns
1516 ** in the result set.
1517 */
generateColumnTypes(Parse * pParse,SrcList * pTabList,ExprList * pEList)1518 static void generateColumnTypes(
1519 Parse *pParse, /* Parser context */
1520 SrcList *pTabList, /* List of tables */
1521 ExprList *pEList /* Expressions defining the result set */
1522 ){
1523 #ifndef SQLITE_OMIT_DECLTYPE
1524 Vdbe *v = pParse->pVdbe;
1525 int i;
1526 NameContext sNC;
1527 sNC.pSrcList = pTabList;
1528 sNC.pParse = pParse;
1529 sNC.pNext = 0;
1530 for(i=0; i<pEList->nExpr; i++){
1531 Expr *p = pEList->a[i].pExpr;
1532 const char *zType;
1533 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1534 const char *zOrigDb = 0;
1535 const char *zOrigTab = 0;
1536 const char *zOrigCol = 0;
1537 zType = columnType(&sNC, p, &zOrigDb, &zOrigTab, &zOrigCol, 0);
1538
1539 /* The vdbe must make its own copy of the column-type and other
1540 ** column specific strings, in case the schema is reset before this
1541 ** virtual machine is deleted.
1542 */
1543 sqlite3VdbeSetColName(v, i, COLNAME_DATABASE, zOrigDb, SQLITE_TRANSIENT);
1544 sqlite3VdbeSetColName(v, i, COLNAME_TABLE, zOrigTab, SQLITE_TRANSIENT);
1545 sqlite3VdbeSetColName(v, i, COLNAME_COLUMN, zOrigCol, SQLITE_TRANSIENT);
1546 #else
1547 zType = columnType(&sNC, p, 0, 0, 0, 0);
1548 #endif
1549 sqlite3VdbeSetColName(v, i, COLNAME_DECLTYPE, zType, SQLITE_TRANSIENT);
1550 }
1551 #endif /* !defined(SQLITE_OMIT_DECLTYPE) */
1552 }
1553
1554
1555 /*
1556 ** Compute the column names for a SELECT statement.
1557 **
1558 ** The only guarantee that SQLite makes about column names is that if the
1559 ** column has an AS clause assigning it a name, that will be the name used.
1560 ** That is the only documented guarantee. However, countless applications
1561 ** developed over the years have made baseless assumptions about column names
1562 ** and will break if those assumptions changes. Hence, use extreme caution
1563 ** when modifying this routine to avoid breaking legacy.
1564 **
1565 ** See Also: sqlite3ColumnsFromExprList()
1566 **
1567 ** The PRAGMA short_column_names and PRAGMA full_column_names settings are
1568 ** deprecated. The default setting is short=ON, full=OFF. 99.9% of all
1569 ** applications should operate this way. Nevertheless, we need to support the
1570 ** other modes for legacy:
1571 **
1572 ** short=OFF, full=OFF: Column name is the text of the expression has it
1573 ** originally appears in the SELECT statement. In
1574 ** other words, the zSpan of the result expression.
1575 **
1576 ** short=ON, full=OFF: (This is the default setting). If the result
1577 ** refers directly to a table column, then the result
1578 ** column name is just the table column name: COLUMN.
1579 ** Otherwise use zSpan.
1580 **
1581 ** full=ON, short=ANY: If the result refers directly to a table column,
1582 ** then the result column name with the table name
1583 ** prefix, ex: TABLE.COLUMN. Otherwise use zSpan.
1584 */
generateColumnNames(Parse * pParse,Select * pSelect)1585 static void generateColumnNames(
1586 Parse *pParse, /* Parser context */
1587 Select *pSelect /* Generate column names for this SELECT statement */
1588 ){
1589 Vdbe *v = pParse->pVdbe;
1590 int i;
1591 Table *pTab;
1592 SrcList *pTabList;
1593 ExprList *pEList;
1594 sqlite3 *db = pParse->db;
1595 int fullName; /* TABLE.COLUMN if no AS clause and is a direct table ref */
1596 int srcName; /* COLUMN or TABLE.COLUMN if no AS clause and is direct */
1597
1598 #ifndef SQLITE_OMIT_EXPLAIN
1599 /* If this is an EXPLAIN, skip this step */
1600 if( pParse->explain ){
1601 return;
1602 }
1603 #endif
1604
1605 if( pParse->colNamesSet || db->mallocFailed ) return;
1606 /* Column names are determined by the left-most term of a compound select */
1607 while( pSelect->pPrior ) pSelect = pSelect->pPrior;
1608 pTabList = pSelect->pSrc;
1609 pEList = pSelect->pEList;
1610 assert( v!=0 );
1611 assert( pTabList!=0 );
1612 pParse->colNamesSet = 1;
1613 fullName = (db->flags & SQLITE_FullColNames)!=0;
1614 srcName = (db->flags & SQLITE_ShortColNames)!=0 || fullName;
1615 sqlite3VdbeSetNumCols(v, pEList->nExpr);
1616 for(i=0; i<pEList->nExpr; i++){
1617 Expr *p = pEList->a[i].pExpr;
1618
1619 assert( p!=0 );
1620 if( pEList->a[i].zName ){
1621 /* An AS clause always takes first priority */
1622 char *zName = pEList->a[i].zName;
1623 sqlite3VdbeSetColName(v, i, COLNAME_NAME, zName, SQLITE_TRANSIENT);
1624 }else if( srcName && p->op==TK_COLUMN ){
1625 char *zCol;
1626 int iCol = p->iColumn;
1627 pTab = p->pTab;
1628 assert( pTab!=0 );
1629 if( iCol<0 ) iCol = pTab->iPKey;
1630 assert( iCol==-1 || (iCol>=0 && iCol<pTab->nCol) );
1631 if( iCol<0 ){
1632 zCol = "rowid";
1633 }else{
1634 zCol = pTab->aCol[iCol].zName;
1635 }
1636 if( fullName ){
1637 char *zName = 0;
1638 zName = sqlite3MPrintf(db, "%s.%s", pTab->zName, zCol);
1639 sqlite3VdbeSetColName(v, i, COLNAME_NAME, zName, SQLITE_DYNAMIC);
1640 }else{
1641 sqlite3VdbeSetColName(v, i, COLNAME_NAME, zCol, SQLITE_TRANSIENT);
1642 }
1643 }else{
1644 const char *z = pEList->a[i].zSpan;
1645 z = z==0 ? sqlite3MPrintf(db, "column%d", i+1) : sqlite3DbStrDup(db, z);
1646 sqlite3VdbeSetColName(v, i, COLNAME_NAME, z, SQLITE_DYNAMIC);
1647 }
1648 }
1649 generateColumnTypes(pParse, pTabList, pEList);
1650 }
1651
1652 /*
1653 ** Given an expression list (which is really the list of expressions
1654 ** that form the result set of a SELECT statement) compute appropriate
1655 ** column names for a table that would hold the expression list.
1656 **
1657 ** All column names will be unique.
1658 **
1659 ** Only the column names are computed. Column.zType, Column.zColl,
1660 ** and other fields of Column are zeroed.
1661 **
1662 ** Return SQLITE_OK on success. If a memory allocation error occurs,
1663 ** store NULL in *paCol and 0 in *pnCol and return SQLITE_NOMEM.
1664 **
1665 ** The only guarantee that SQLite makes about column names is that if the
1666 ** column has an AS clause assigning it a name, that will be the name used.
1667 ** That is the only documented guarantee. However, countless applications
1668 ** developed over the years have made baseless assumptions about column names
1669 ** and will break if those assumptions changes. Hence, use extreme caution
1670 ** when modifying this routine to avoid breaking legacy.
1671 **
1672 ** See Also: generateColumnNames()
1673 */
sqlite3ColumnsFromExprList(Parse * pParse,ExprList * pEList,i16 * pnCol,Column ** paCol)1674 int sqlite3ColumnsFromExprList(
1675 Parse *pParse, /* Parsing context */
1676 ExprList *pEList, /* Expr list from which to derive column names */
1677 i16 *pnCol, /* Write the number of columns here */
1678 Column **paCol /* Write the new column list here */
1679 ){
1680 sqlite3 *db = pParse->db; /* Database connection */
1681 int i, j; /* Loop counters */
1682 u32 cnt; /* Index added to make the name unique */
1683 Column *aCol, *pCol; /* For looping over result columns */
1684 int nCol; /* Number of columns in the result set */
1685 char *zName; /* Column name */
1686 int nName; /* Size of name in zName[] */
1687 Hash ht; /* Hash table of column names */
1688
1689 sqlite3HashInit(&ht);
1690 if( pEList ){
1691 nCol = pEList->nExpr;
1692 aCol = sqlite3DbMallocZero(db, sizeof(aCol[0])*nCol);
1693 testcase( aCol==0 );
1694 }else{
1695 nCol = 0;
1696 aCol = 0;
1697 }
1698 assert( nCol==(i16)nCol );
1699 *pnCol = nCol;
1700 *paCol = aCol;
1701
1702 for(i=0, pCol=aCol; i<nCol && !db->mallocFailed; i++, pCol++){
1703 /* Get an appropriate name for the column
1704 */
1705 if( (zName = pEList->a[i].zName)!=0 ){
1706 /* If the column contains an "AS <name>" phrase, use <name> as the name */
1707 }else{
1708 Expr *pColExpr = sqlite3ExprSkipCollate(pEList->a[i].pExpr);
1709 while( pColExpr->op==TK_DOT ){
1710 pColExpr = pColExpr->pRight;
1711 assert( pColExpr!=0 );
1712 }
1713 if( pColExpr->op==TK_COLUMN && pColExpr->pTab!=0 ){
1714 /* For columns use the column name name */
1715 int iCol = pColExpr->iColumn;
1716 Table *pTab = pColExpr->pTab;
1717 if( iCol<0 ) iCol = pTab->iPKey;
1718 zName = iCol>=0 ? pTab->aCol[iCol].zName : "rowid";
1719 }else if( pColExpr->op==TK_ID ){
1720 assert( !ExprHasProperty(pColExpr, EP_IntValue) );
1721 zName = pColExpr->u.zToken;
1722 }else{
1723 /* Use the original text of the column expression as its name */
1724 zName = pEList->a[i].zSpan;
1725 }
1726 }
1727 if( zName ){
1728 zName = sqlite3DbStrDup(db, zName);
1729 }else{
1730 zName = sqlite3MPrintf(db,"column%d",i+1);
1731 }
1732
1733 /* Make sure the column name is unique. If the name is not unique,
1734 ** append an integer to the name so that it becomes unique.
1735 */
1736 cnt = 0;
1737 while( zName && sqlite3HashFind(&ht, zName)!=0 ){
1738 nName = sqlite3Strlen30(zName);
1739 if( nName>0 ){
1740 for(j=nName-1; j>0 && sqlite3Isdigit(zName[j]); j--){}
1741 if( zName[j]==':' ) nName = j;
1742 }
1743 zName = sqlite3MPrintf(db, "%.*z:%u", nName, zName, ++cnt);
1744 if( cnt>3 ) sqlite3_randomness(sizeof(cnt), &cnt);
1745 }
1746 pCol->zName = zName;
1747 sqlite3ColumnPropertiesFromName(0, pCol);
1748 if( zName && sqlite3HashInsert(&ht, zName, pCol)==pCol ){
1749 sqlite3OomFault(db);
1750 }
1751 }
1752 sqlite3HashClear(&ht);
1753 if( db->mallocFailed ){
1754 for(j=0; j<i; j++){
1755 sqlite3DbFree(db, aCol[j].zName);
1756 }
1757 sqlite3DbFree(db, aCol);
1758 *paCol = 0;
1759 *pnCol = 0;
1760 return SQLITE_NOMEM_BKPT;
1761 }
1762 return SQLITE_OK;
1763 }
1764
1765 /*
1766 ** Add type and collation information to a column list based on
1767 ** a SELECT statement.
1768 **
1769 ** The column list presumably came from selectColumnNamesFromExprList().
1770 ** The column list has only names, not types or collations. This
1771 ** routine goes through and adds the types and collations.
1772 **
1773 ** This routine requires that all identifiers in the SELECT
1774 ** statement be resolved.
1775 */
sqlite3SelectAddColumnTypeAndCollation(Parse * pParse,Table * pTab,Select * pSelect)1776 void sqlite3SelectAddColumnTypeAndCollation(
1777 Parse *pParse, /* Parsing contexts */
1778 Table *pTab, /* Add column type information to this table */
1779 Select *pSelect /* SELECT used to determine types and collations */
1780 ){
1781 sqlite3 *db = pParse->db;
1782 NameContext sNC;
1783 Column *pCol;
1784 CollSeq *pColl;
1785 int i;
1786 Expr *p;
1787 struct ExprList_item *a;
1788 u64 szAll = 0;
1789
1790 assert( pSelect!=0 );
1791 assert( (pSelect->selFlags & SF_Resolved)!=0 );
1792 assert( pTab->nCol==pSelect->pEList->nExpr || db->mallocFailed );
1793 if( db->mallocFailed ) return;
1794 memset(&sNC, 0, sizeof(sNC));
1795 sNC.pSrcList = pSelect->pSrc;
1796 a = pSelect->pEList->a;
1797 for(i=0, pCol=pTab->aCol; i<pTab->nCol; i++, pCol++){
1798 const char *zType;
1799 int n, m;
1800 p = a[i].pExpr;
1801 zType = columnType(&sNC, p, 0, 0, 0, &pCol->szEst);
1802 szAll += pCol->szEst;
1803 pCol->affinity = sqlite3ExprAffinity(p);
1804 if( zType && (m = sqlite3Strlen30(zType))>0 ){
1805 n = sqlite3Strlen30(pCol->zName);
1806 pCol->zName = sqlite3DbReallocOrFree(db, pCol->zName, n+m+2);
1807 if( pCol->zName ){
1808 memcpy(&pCol->zName[n+1], zType, m+1);
1809 pCol->colFlags |= COLFLAG_HASTYPE;
1810 }
1811 }
1812 if( pCol->affinity==0 ) pCol->affinity = SQLITE_AFF_BLOB;
1813 pColl = sqlite3ExprCollSeq(pParse, p);
1814 if( pColl && pCol->zColl==0 ){
1815 pCol->zColl = sqlite3DbStrDup(db, pColl->zName);
1816 }
1817 }
1818 pTab->szTabRow = sqlite3LogEst(szAll*4);
1819 }
1820
1821 /*
1822 ** Given a SELECT statement, generate a Table structure that describes
1823 ** the result set of that SELECT.
1824 */
sqlite3ResultSetOfSelect(Parse * pParse,Select * pSelect)1825 Table *sqlite3ResultSetOfSelect(Parse *pParse, Select *pSelect){
1826 Table *pTab;
1827 sqlite3 *db = pParse->db;
1828 int savedFlags;
1829
1830 savedFlags = db->flags;
1831 db->flags &= ~SQLITE_FullColNames;
1832 db->flags |= SQLITE_ShortColNames;
1833 sqlite3SelectPrep(pParse, pSelect, 0);
1834 if( pParse->nErr ) return 0;
1835 while( pSelect->pPrior ) pSelect = pSelect->pPrior;
1836 db->flags = savedFlags;
1837 pTab = sqlite3DbMallocZero(db, sizeof(Table) );
1838 if( pTab==0 ){
1839 return 0;
1840 }
1841 /* The sqlite3ResultSetOfSelect() is only used n contexts where lookaside
1842 ** is disabled */
1843 assert( db->lookaside.bDisable );
1844 pTab->nTabRef = 1;
1845 pTab->zName = 0;
1846 pTab->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) );
1847 sqlite3ColumnsFromExprList(pParse, pSelect->pEList, &pTab->nCol, &pTab->aCol);
1848 sqlite3SelectAddColumnTypeAndCollation(pParse, pTab, pSelect);
1849 pTab->iPKey = -1;
1850 if( db->mallocFailed ){
1851 sqlite3DeleteTable(db, pTab);
1852 return 0;
1853 }
1854 return pTab;
1855 }
1856
1857 /*
1858 ** Get a VDBE for the given parser context. Create a new one if necessary.
1859 ** If an error occurs, return NULL and leave a message in pParse.
1860 */
allocVdbe(Parse * pParse)1861 static SQLITE_NOINLINE Vdbe *allocVdbe(Parse *pParse){
1862 Vdbe *v = pParse->pVdbe = sqlite3VdbeCreate(pParse);
1863 if( v ) sqlite3VdbeAddOp2(v, OP_Init, 0, 1);
1864 if( pParse->pToplevel==0
1865 && OptimizationEnabled(pParse->db,SQLITE_FactorOutConst)
1866 ){
1867 pParse->okConstFactor = 1;
1868 }
1869 return v;
1870 }
sqlite3GetVdbe(Parse * pParse)1871 Vdbe *sqlite3GetVdbe(Parse *pParse){
1872 Vdbe *v = pParse->pVdbe;
1873 return v ? v : allocVdbe(pParse);
1874 }
1875
1876
1877 /*
1878 ** Compute the iLimit and iOffset fields of the SELECT based on the
1879 ** pLimit and pOffset expressions. pLimit and pOffset hold the expressions
1880 ** that appear in the original SQL statement after the LIMIT and OFFSET
1881 ** keywords. Or NULL if those keywords are omitted. iLimit and iOffset
1882 ** are the integer memory register numbers for counters used to compute
1883 ** the limit and offset. If there is no limit and/or offset, then
1884 ** iLimit and iOffset are negative.
1885 **
1886 ** This routine changes the values of iLimit and iOffset only if
1887 ** a limit or offset is defined by pLimit and pOffset. iLimit and
1888 ** iOffset should have been preset to appropriate default values (zero)
1889 ** prior to calling this routine.
1890 **
1891 ** The iOffset register (if it exists) is initialized to the value
1892 ** of the OFFSET. The iLimit register is initialized to LIMIT. Register
1893 ** iOffset+1 is initialized to LIMIT+OFFSET.
1894 **
1895 ** Only if pLimit!=0 or pOffset!=0 do the limit registers get
1896 ** redefined. The UNION ALL operator uses this property to force
1897 ** the reuse of the same limit and offset registers across multiple
1898 ** SELECT statements.
1899 */
computeLimitRegisters(Parse * pParse,Select * p,int iBreak)1900 static void computeLimitRegisters(Parse *pParse, Select *p, int iBreak){
1901 Vdbe *v = 0;
1902 int iLimit = 0;
1903 int iOffset;
1904 int n;
1905 if( p->iLimit ) return;
1906
1907 /*
1908 ** "LIMIT -1" always shows all rows. There is some
1909 ** controversy about what the correct behavior should be.
1910 ** The current implementation interprets "LIMIT 0" to mean
1911 ** no rows.
1912 */
1913 sqlite3ExprCacheClear(pParse);
1914 assert( p->pOffset==0 || p->pLimit!=0 );
1915 if( p->pLimit ){
1916 p->iLimit = iLimit = ++pParse->nMem;
1917 v = sqlite3GetVdbe(pParse);
1918 assert( v!=0 );
1919 if( sqlite3ExprIsInteger(p->pLimit, &n) ){
1920 sqlite3VdbeAddOp2(v, OP_Integer, n, iLimit);
1921 VdbeComment((v, "LIMIT counter"));
1922 if( n==0 ){
1923 sqlite3VdbeGoto(v, iBreak);
1924 }else if( n>=0 && p->nSelectRow>sqlite3LogEst((u64)n) ){
1925 p->nSelectRow = sqlite3LogEst((u64)n);
1926 p->selFlags |= SF_FixedLimit;
1927 }
1928 }else{
1929 sqlite3ExprCode(pParse, p->pLimit, iLimit);
1930 sqlite3VdbeAddOp1(v, OP_MustBeInt, iLimit); VdbeCoverage(v);
1931 VdbeComment((v, "LIMIT counter"));
1932 sqlite3VdbeAddOp2(v, OP_IfNot, iLimit, iBreak); VdbeCoverage(v);
1933 }
1934 if( p->pOffset ){
1935 p->iOffset = iOffset = ++pParse->nMem;
1936 pParse->nMem++; /* Allocate an extra register for limit+offset */
1937 sqlite3ExprCode(pParse, p->pOffset, iOffset);
1938 sqlite3VdbeAddOp1(v, OP_MustBeInt, iOffset); VdbeCoverage(v);
1939 VdbeComment((v, "OFFSET counter"));
1940 sqlite3VdbeAddOp3(v, OP_OffsetLimit, iLimit, iOffset+1, iOffset);
1941 VdbeComment((v, "LIMIT+OFFSET"));
1942 }
1943 }
1944 }
1945
1946 #ifndef SQLITE_OMIT_COMPOUND_SELECT
1947 /*
1948 ** Return the appropriate collating sequence for the iCol-th column of
1949 ** the result set for the compound-select statement "p". Return NULL if
1950 ** the column has no default collating sequence.
1951 **
1952 ** The collating sequence for the compound select is taken from the
1953 ** left-most term of the select that has a collating sequence.
1954 */
multiSelectCollSeq(Parse * pParse,Select * p,int iCol)1955 static CollSeq *multiSelectCollSeq(Parse *pParse, Select *p, int iCol){
1956 CollSeq *pRet;
1957 if( p->pPrior ){
1958 pRet = multiSelectCollSeq(pParse, p->pPrior, iCol);
1959 }else{
1960 pRet = 0;
1961 }
1962 assert( iCol>=0 );
1963 /* iCol must be less than p->pEList->nExpr. Otherwise an error would
1964 ** have been thrown during name resolution and we would not have gotten
1965 ** this far */
1966 if( pRet==0 && ALWAYS(iCol<p->pEList->nExpr) ){
1967 pRet = sqlite3ExprCollSeq(pParse, p->pEList->a[iCol].pExpr);
1968 }
1969 return pRet;
1970 }
1971
1972 /*
1973 ** The select statement passed as the second parameter is a compound SELECT
1974 ** with an ORDER BY clause. This function allocates and returns a KeyInfo
1975 ** structure suitable for implementing the ORDER BY.
1976 **
1977 ** Space to hold the KeyInfo structure is obtained from malloc. The calling
1978 ** function is responsible for ensuring that this structure is eventually
1979 ** freed.
1980 */
multiSelectOrderByKeyInfo(Parse * pParse,Select * p,int nExtra)1981 static KeyInfo *multiSelectOrderByKeyInfo(Parse *pParse, Select *p, int nExtra){
1982 ExprList *pOrderBy = p->pOrderBy;
1983 int nOrderBy = p->pOrderBy->nExpr;
1984 sqlite3 *db = pParse->db;
1985 KeyInfo *pRet = sqlite3KeyInfoAlloc(db, nOrderBy+nExtra, 1);
1986 if( pRet ){
1987 int i;
1988 for(i=0; i<nOrderBy; i++){
1989 struct ExprList_item *pItem = &pOrderBy->a[i];
1990 Expr *pTerm = pItem->pExpr;
1991 CollSeq *pColl;
1992
1993 if( pTerm->flags & EP_Collate ){
1994 pColl = sqlite3ExprCollSeq(pParse, pTerm);
1995 }else{
1996 pColl = multiSelectCollSeq(pParse, p, pItem->u.x.iOrderByCol-1);
1997 if( pColl==0 ) pColl = db->pDfltColl;
1998 pOrderBy->a[i].pExpr =
1999 sqlite3ExprAddCollateString(pParse, pTerm, pColl->zName);
2000 }
2001 assert( sqlite3KeyInfoIsWriteable(pRet) );
2002 pRet->aColl[i] = pColl;
2003 pRet->aSortOrder[i] = pOrderBy->a[i].sortOrder;
2004 }
2005 }
2006
2007 return pRet;
2008 }
2009
2010 #ifndef SQLITE_OMIT_CTE
2011 /*
2012 ** This routine generates VDBE code to compute the content of a WITH RECURSIVE
2013 ** query of the form:
2014 **
2015 ** <recursive-table> AS (<setup-query> UNION [ALL] <recursive-query>)
2016 ** \___________/ \_______________/
2017 ** p->pPrior p
2018 **
2019 **
2020 ** There is exactly one reference to the recursive-table in the FROM clause
2021 ** of recursive-query, marked with the SrcList->a[].fg.isRecursive flag.
2022 **
2023 ** The setup-query runs once to generate an initial set of rows that go
2024 ** into a Queue table. Rows are extracted from the Queue table one by
2025 ** one. Each row extracted from Queue is output to pDest. Then the single
2026 ** extracted row (now in the iCurrent table) becomes the content of the
2027 ** recursive-table for a recursive-query run. The output of the recursive-query
2028 ** is added back into the Queue table. Then another row is extracted from Queue
2029 ** and the iteration continues until the Queue table is empty.
2030 **
2031 ** If the compound query operator is UNION then no duplicate rows are ever
2032 ** inserted into the Queue table. The iDistinct table keeps a copy of all rows
2033 ** that have ever been inserted into Queue and causes duplicates to be
2034 ** discarded. If the operator is UNION ALL, then duplicates are allowed.
2035 **
2036 ** If the query has an ORDER BY, then entries in the Queue table are kept in
2037 ** ORDER BY order and the first entry is extracted for each cycle. Without
2038 ** an ORDER BY, the Queue table is just a FIFO.
2039 **
2040 ** If a LIMIT clause is provided, then the iteration stops after LIMIT rows
2041 ** have been output to pDest. A LIMIT of zero means to output no rows and a
2042 ** negative LIMIT means to output all rows. If there is also an OFFSET clause
2043 ** with a positive value, then the first OFFSET outputs are discarded rather
2044 ** than being sent to pDest. The LIMIT count does not begin until after OFFSET
2045 ** rows have been skipped.
2046 */
generateWithRecursiveQuery(Parse * pParse,Select * p,SelectDest * pDest)2047 static void generateWithRecursiveQuery(
2048 Parse *pParse, /* Parsing context */
2049 Select *p, /* The recursive SELECT to be coded */
2050 SelectDest *pDest /* What to do with query results */
2051 ){
2052 SrcList *pSrc = p->pSrc; /* The FROM clause of the recursive query */
2053 int nCol = p->pEList->nExpr; /* Number of columns in the recursive table */
2054 Vdbe *v = pParse->pVdbe; /* The prepared statement under construction */
2055 Select *pSetup = p->pPrior; /* The setup query */
2056 int addrTop; /* Top of the loop */
2057 int addrCont, addrBreak; /* CONTINUE and BREAK addresses */
2058 int iCurrent = 0; /* The Current table */
2059 int regCurrent; /* Register holding Current table */
2060 int iQueue; /* The Queue table */
2061 int iDistinct = 0; /* To ensure unique results if UNION */
2062 int eDest = SRT_Fifo; /* How to write to Queue */
2063 SelectDest destQueue; /* SelectDest targetting the Queue table */
2064 int i; /* Loop counter */
2065 int rc; /* Result code */
2066 ExprList *pOrderBy; /* The ORDER BY clause */
2067 Expr *pLimit, *pOffset; /* Saved LIMIT and OFFSET */
2068 int regLimit, regOffset; /* Registers used by LIMIT and OFFSET */
2069
2070 /* Obtain authorization to do a recursive query */
2071 if( sqlite3AuthCheck(pParse, SQLITE_RECURSIVE, 0, 0, 0) ) return;
2072
2073 /* Process the LIMIT and OFFSET clauses, if they exist */
2074 addrBreak = sqlite3VdbeMakeLabel(v);
2075 p->nSelectRow = 320; /* 4 billion rows */
2076 computeLimitRegisters(pParse, p, addrBreak);
2077 pLimit = p->pLimit;
2078 pOffset = p->pOffset;
2079 regLimit = p->iLimit;
2080 regOffset = p->iOffset;
2081 p->pLimit = p->pOffset = 0;
2082 p->iLimit = p->iOffset = 0;
2083 pOrderBy = p->pOrderBy;
2084
2085 /* Locate the cursor number of the Current table */
2086 for(i=0; ALWAYS(i<pSrc->nSrc); i++){
2087 if( pSrc->a[i].fg.isRecursive ){
2088 iCurrent = pSrc->a[i].iCursor;
2089 break;
2090 }
2091 }
2092
2093 /* Allocate cursors numbers for Queue and Distinct. The cursor number for
2094 ** the Distinct table must be exactly one greater than Queue in order
2095 ** for the SRT_DistFifo and SRT_DistQueue destinations to work. */
2096 iQueue = pParse->nTab++;
2097 if( p->op==TK_UNION ){
2098 eDest = pOrderBy ? SRT_DistQueue : SRT_DistFifo;
2099 iDistinct = pParse->nTab++;
2100 }else{
2101 eDest = pOrderBy ? SRT_Queue : SRT_Fifo;
2102 }
2103 sqlite3SelectDestInit(&destQueue, eDest, iQueue);
2104
2105 /* Allocate cursors for Current, Queue, and Distinct. */
2106 regCurrent = ++pParse->nMem;
2107 sqlite3VdbeAddOp3(v, OP_OpenPseudo, iCurrent, regCurrent, nCol);
2108 if( pOrderBy ){
2109 KeyInfo *pKeyInfo = multiSelectOrderByKeyInfo(pParse, p, 1);
2110 sqlite3VdbeAddOp4(v, OP_OpenEphemeral, iQueue, pOrderBy->nExpr+2, 0,
2111 (char*)pKeyInfo, P4_KEYINFO);
2112 destQueue.pOrderBy = pOrderBy;
2113 }else{
2114 sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iQueue, nCol);
2115 }
2116 VdbeComment((v, "Queue table"));
2117 if( iDistinct ){
2118 p->addrOpenEphm[0] = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iDistinct, 0);
2119 p->selFlags |= SF_UsesEphemeral;
2120 }
2121
2122 /* Detach the ORDER BY clause from the compound SELECT */
2123 p->pOrderBy = 0;
2124
2125 /* Store the results of the setup-query in Queue. */
2126 pSetup->pNext = 0;
2127 rc = sqlite3Select(pParse, pSetup, &destQueue);
2128 pSetup->pNext = p;
2129 if( rc ) goto end_of_recursive_query;
2130
2131 /* Find the next row in the Queue and output that row */
2132 addrTop = sqlite3VdbeAddOp2(v, OP_Rewind, iQueue, addrBreak); VdbeCoverage(v);
2133
2134 /* Transfer the next row in Queue over to Current */
2135 sqlite3VdbeAddOp1(v, OP_NullRow, iCurrent); /* To reset column cache */
2136 if( pOrderBy ){
2137 sqlite3VdbeAddOp3(v, OP_Column, iQueue, pOrderBy->nExpr+1, regCurrent);
2138 }else{
2139 sqlite3VdbeAddOp2(v, OP_RowData, iQueue, regCurrent);
2140 }
2141 sqlite3VdbeAddOp1(v, OP_Delete, iQueue);
2142
2143 /* Output the single row in Current */
2144 addrCont = sqlite3VdbeMakeLabel(v);
2145 codeOffset(v, regOffset, addrCont);
2146 selectInnerLoop(pParse, p, p->pEList, iCurrent,
2147 0, 0, pDest, addrCont, addrBreak);
2148 if( regLimit ){
2149 sqlite3VdbeAddOp2(v, OP_DecrJumpZero, regLimit, addrBreak);
2150 VdbeCoverage(v);
2151 }
2152 sqlite3VdbeResolveLabel(v, addrCont);
2153
2154 /* Execute the recursive SELECT taking the single row in Current as
2155 ** the value for the recursive-table. Store the results in the Queue.
2156 */
2157 if( p->selFlags & SF_Aggregate ){
2158 sqlite3ErrorMsg(pParse, "recursive aggregate queries not supported");
2159 }else{
2160 p->pPrior = 0;
2161 sqlite3Select(pParse, p, &destQueue);
2162 assert( p->pPrior==0 );
2163 p->pPrior = pSetup;
2164 }
2165
2166 /* Keep running the loop until the Queue is empty */
2167 sqlite3VdbeGoto(v, addrTop);
2168 sqlite3VdbeResolveLabel(v, addrBreak);
2169
2170 end_of_recursive_query:
2171 sqlite3ExprListDelete(pParse->db, p->pOrderBy);
2172 p->pOrderBy = pOrderBy;
2173 p->pLimit = pLimit;
2174 p->pOffset = pOffset;
2175 return;
2176 }
2177 #endif /* SQLITE_OMIT_CTE */
2178
2179 /* Forward references */
2180 static int multiSelectOrderBy(
2181 Parse *pParse, /* Parsing context */
2182 Select *p, /* The right-most of SELECTs to be coded */
2183 SelectDest *pDest /* What to do with query results */
2184 );
2185
2186 /*
2187 ** Handle the special case of a compound-select that originates from a
2188 ** VALUES clause. By handling this as a special case, we avoid deep
2189 ** recursion, and thus do not need to enforce the SQLITE_LIMIT_COMPOUND_SELECT
2190 ** on a VALUES clause.
2191 **
2192 ** Because the Select object originates from a VALUES clause:
2193 ** (1) It has no LIMIT or OFFSET
2194 ** (2) All terms are UNION ALL
2195 ** (3) There is no ORDER BY clause
2196 */
multiSelectValues(Parse * pParse,Select * p,SelectDest * pDest)2197 static int multiSelectValues(
2198 Parse *pParse, /* Parsing context */
2199 Select *p, /* The right-most of SELECTs to be coded */
2200 SelectDest *pDest /* What to do with query results */
2201 ){
2202 Select *pPrior;
2203 int nRow = 1;
2204 int rc = 0;
2205 assert( p->selFlags & SF_MultiValue );
2206 do{
2207 assert( p->selFlags & SF_Values );
2208 assert( p->op==TK_ALL || (p->op==TK_SELECT && p->pPrior==0) );
2209 assert( p->pLimit==0 );
2210 assert( p->pOffset==0 );
2211 assert( p->pNext==0 || p->pEList->nExpr==p->pNext->pEList->nExpr );
2212 if( p->pPrior==0 ) break;
2213 assert( p->pPrior->pNext==p );
2214 p = p->pPrior;
2215 nRow++;
2216 }while(1);
2217 while( p ){
2218 pPrior = p->pPrior;
2219 p->pPrior = 0;
2220 rc = sqlite3Select(pParse, p, pDest);
2221 p->pPrior = pPrior;
2222 if( rc ) break;
2223 p->nSelectRow = nRow;
2224 p = p->pNext;
2225 }
2226 return rc;
2227 }
2228
2229 /*
2230 ** This routine is called to process a compound query form from
2231 ** two or more separate queries using UNION, UNION ALL, EXCEPT, or
2232 ** INTERSECT
2233 **
2234 ** "p" points to the right-most of the two queries. the query on the
2235 ** left is p->pPrior. The left query could also be a compound query
2236 ** in which case this routine will be called recursively.
2237 **
2238 ** The results of the total query are to be written into a destination
2239 ** of type eDest with parameter iParm.
2240 **
2241 ** Example 1: Consider a three-way compound SQL statement.
2242 **
2243 ** SELECT a FROM t1 UNION SELECT b FROM t2 UNION SELECT c FROM t3
2244 **
2245 ** This statement is parsed up as follows:
2246 **
2247 ** SELECT c FROM t3
2248 ** |
2249 ** `-----> SELECT b FROM t2
2250 ** |
2251 ** `------> SELECT a FROM t1
2252 **
2253 ** The arrows in the diagram above represent the Select.pPrior pointer.
2254 ** So if this routine is called with p equal to the t3 query, then
2255 ** pPrior will be the t2 query. p->op will be TK_UNION in this case.
2256 **
2257 ** Notice that because of the way SQLite parses compound SELECTs, the
2258 ** individual selects always group from left to right.
2259 */
multiSelect(Parse * pParse,Select * p,SelectDest * pDest)2260 static int multiSelect(
2261 Parse *pParse, /* Parsing context */
2262 Select *p, /* The right-most of SELECTs to be coded */
2263 SelectDest *pDest /* What to do with query results */
2264 ){
2265 int rc = SQLITE_OK; /* Success code from a subroutine */
2266 Select *pPrior; /* Another SELECT immediately to our left */
2267 Vdbe *v; /* Generate code to this VDBE */
2268 SelectDest dest; /* Alternative data destination */
2269 Select *pDelete = 0; /* Chain of simple selects to delete */
2270 sqlite3 *db; /* Database connection */
2271 #ifndef SQLITE_OMIT_EXPLAIN
2272 int iSub1 = 0; /* EQP id of left-hand query */
2273 int iSub2 = 0; /* EQP id of right-hand query */
2274 #endif
2275
2276 /* Make sure there is no ORDER BY or LIMIT clause on prior SELECTs. Only
2277 ** the last (right-most) SELECT in the series may have an ORDER BY or LIMIT.
2278 */
2279 assert( p && p->pPrior ); /* Calling function guarantees this much */
2280 assert( (p->selFlags & SF_Recursive)==0 || p->op==TK_ALL || p->op==TK_UNION );
2281 db = pParse->db;
2282 pPrior = p->pPrior;
2283 dest = *pDest;
2284 if( pPrior->pOrderBy ){
2285 sqlite3ErrorMsg(pParse,"ORDER BY clause should come after %s not before",
2286 selectOpName(p->op));
2287 rc = 1;
2288 goto multi_select_end;
2289 }
2290 if( pPrior->pLimit ){
2291 sqlite3ErrorMsg(pParse,"LIMIT clause should come after %s not before",
2292 selectOpName(p->op));
2293 rc = 1;
2294 goto multi_select_end;
2295 }
2296
2297 v = sqlite3GetVdbe(pParse);
2298 assert( v!=0 ); /* The VDBE already created by calling function */
2299
2300 /* Create the destination temporary table if necessary
2301 */
2302 if( dest.eDest==SRT_EphemTab ){
2303 assert( p->pEList );
2304 sqlite3VdbeAddOp2(v, OP_OpenEphemeral, dest.iSDParm, p->pEList->nExpr);
2305 dest.eDest = SRT_Table;
2306 }
2307
2308 /* Special handling for a compound-select that originates as a VALUES clause.
2309 */
2310 if( p->selFlags & SF_MultiValue ){
2311 rc = multiSelectValues(pParse, p, &dest);
2312 goto multi_select_end;
2313 }
2314
2315 /* Make sure all SELECTs in the statement have the same number of elements
2316 ** in their result sets.
2317 */
2318 assert( p->pEList && pPrior->pEList );
2319 assert( p->pEList->nExpr==pPrior->pEList->nExpr );
2320
2321 #ifndef SQLITE_OMIT_CTE
2322 if( p->selFlags & SF_Recursive ){
2323 generateWithRecursiveQuery(pParse, p, &dest);
2324 }else
2325 #endif
2326
2327 /* Compound SELECTs that have an ORDER BY clause are handled separately.
2328 */
2329 if( p->pOrderBy ){
2330 return multiSelectOrderBy(pParse, p, pDest);
2331 }else
2332
2333 /* Generate code for the left and right SELECT statements.
2334 */
2335 switch( p->op ){
2336 case TK_ALL: {
2337 int addr = 0;
2338 int nLimit;
2339 assert( !pPrior->pLimit );
2340 pPrior->iLimit = p->iLimit;
2341 pPrior->iOffset = p->iOffset;
2342 pPrior->pLimit = p->pLimit;
2343 pPrior->pOffset = p->pOffset;
2344 explainSetInteger(iSub1, pParse->iNextSelectId);
2345 rc = sqlite3Select(pParse, pPrior, &dest);
2346 p->pLimit = 0;
2347 p->pOffset = 0;
2348 if( rc ){
2349 goto multi_select_end;
2350 }
2351 p->pPrior = 0;
2352 p->iLimit = pPrior->iLimit;
2353 p->iOffset = pPrior->iOffset;
2354 if( p->iLimit ){
2355 addr = sqlite3VdbeAddOp1(v, OP_IfNot, p->iLimit); VdbeCoverage(v);
2356 VdbeComment((v, "Jump ahead if LIMIT reached"));
2357 if( p->iOffset ){
2358 sqlite3VdbeAddOp3(v, OP_OffsetLimit,
2359 p->iLimit, p->iOffset+1, p->iOffset);
2360 }
2361 }
2362 explainSetInteger(iSub2, pParse->iNextSelectId);
2363 rc = sqlite3Select(pParse, p, &dest);
2364 testcase( rc!=SQLITE_OK );
2365 pDelete = p->pPrior;
2366 p->pPrior = pPrior;
2367 p->nSelectRow = sqlite3LogEstAdd(p->nSelectRow, pPrior->nSelectRow);
2368 if( pPrior->pLimit
2369 && sqlite3ExprIsInteger(pPrior->pLimit, &nLimit)
2370 && nLimit>0 && p->nSelectRow > sqlite3LogEst((u64)nLimit)
2371 ){
2372 p->nSelectRow = sqlite3LogEst((u64)nLimit);
2373 }
2374 if( addr ){
2375 sqlite3VdbeJumpHere(v, addr);
2376 }
2377 break;
2378 }
2379 case TK_EXCEPT:
2380 case TK_UNION: {
2381 int unionTab; /* Cursor number of the temporary table holding result */
2382 u8 op = 0; /* One of the SRT_ operations to apply to self */
2383 int priorOp; /* The SRT_ operation to apply to prior selects */
2384 Expr *pLimit, *pOffset; /* Saved values of p->nLimit and p->nOffset */
2385 int addr;
2386 SelectDest uniondest;
2387
2388 testcase( p->op==TK_EXCEPT );
2389 testcase( p->op==TK_UNION );
2390 priorOp = SRT_Union;
2391 if( dest.eDest==priorOp ){
2392 /* We can reuse a temporary table generated by a SELECT to our
2393 ** right.
2394 */
2395 assert( p->pLimit==0 ); /* Not allowed on leftward elements */
2396 assert( p->pOffset==0 ); /* Not allowed on leftward elements */
2397 unionTab = dest.iSDParm;
2398 }else{
2399 /* We will need to create our own temporary table to hold the
2400 ** intermediate results.
2401 */
2402 unionTab = pParse->nTab++;
2403 assert( p->pOrderBy==0 );
2404 addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, unionTab, 0);
2405 assert( p->addrOpenEphm[0] == -1 );
2406 p->addrOpenEphm[0] = addr;
2407 findRightmost(p)->selFlags |= SF_UsesEphemeral;
2408 assert( p->pEList );
2409 }
2410
2411 /* Code the SELECT statements to our left
2412 */
2413 assert( !pPrior->pOrderBy );
2414 sqlite3SelectDestInit(&uniondest, priorOp, unionTab);
2415 explainSetInteger(iSub1, pParse->iNextSelectId);
2416 rc = sqlite3Select(pParse, pPrior, &uniondest);
2417 if( rc ){
2418 goto multi_select_end;
2419 }
2420
2421 /* Code the current SELECT statement
2422 */
2423 if( p->op==TK_EXCEPT ){
2424 op = SRT_Except;
2425 }else{
2426 assert( p->op==TK_UNION );
2427 op = SRT_Union;
2428 }
2429 p->pPrior = 0;
2430 pLimit = p->pLimit;
2431 p->pLimit = 0;
2432 pOffset = p->pOffset;
2433 p->pOffset = 0;
2434 uniondest.eDest = op;
2435 explainSetInteger(iSub2, pParse->iNextSelectId);
2436 rc = sqlite3Select(pParse, p, &uniondest);
2437 testcase( rc!=SQLITE_OK );
2438 /* Query flattening in sqlite3Select() might refill p->pOrderBy.
2439 ** Be sure to delete p->pOrderBy, therefore, to avoid a memory leak. */
2440 sqlite3ExprListDelete(db, p->pOrderBy);
2441 pDelete = p->pPrior;
2442 p->pPrior = pPrior;
2443 p->pOrderBy = 0;
2444 if( p->op==TK_UNION ){
2445 p->nSelectRow = sqlite3LogEstAdd(p->nSelectRow, pPrior->nSelectRow);
2446 }
2447 sqlite3ExprDelete(db, p->pLimit);
2448 p->pLimit = pLimit;
2449 p->pOffset = pOffset;
2450 p->iLimit = 0;
2451 p->iOffset = 0;
2452
2453 /* Convert the data in the temporary table into whatever form
2454 ** it is that we currently need.
2455 */
2456 assert( unionTab==dest.iSDParm || dest.eDest!=priorOp );
2457 if( dest.eDest!=priorOp ){
2458 int iCont, iBreak, iStart;
2459 assert( p->pEList );
2460 iBreak = sqlite3VdbeMakeLabel(v);
2461 iCont = sqlite3VdbeMakeLabel(v);
2462 computeLimitRegisters(pParse, p, iBreak);
2463 sqlite3VdbeAddOp2(v, OP_Rewind, unionTab, iBreak); VdbeCoverage(v);
2464 iStart = sqlite3VdbeCurrentAddr(v);
2465 selectInnerLoop(pParse, p, p->pEList, unionTab,
2466 0, 0, &dest, iCont, iBreak);
2467 sqlite3VdbeResolveLabel(v, iCont);
2468 sqlite3VdbeAddOp2(v, OP_Next, unionTab, iStart); VdbeCoverage(v);
2469 sqlite3VdbeResolveLabel(v, iBreak);
2470 sqlite3VdbeAddOp2(v, OP_Close, unionTab, 0);
2471 }
2472 break;
2473 }
2474 default: assert( p->op==TK_INTERSECT ); {
2475 int tab1, tab2;
2476 int iCont, iBreak, iStart;
2477 Expr *pLimit, *pOffset;
2478 int addr;
2479 SelectDest intersectdest;
2480 int r1;
2481
2482 /* INTERSECT is different from the others since it requires
2483 ** two temporary tables. Hence it has its own case. Begin
2484 ** by allocating the tables we will need.
2485 */
2486 tab1 = pParse->nTab++;
2487 tab2 = pParse->nTab++;
2488 assert( p->pOrderBy==0 );
2489
2490 addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, tab1, 0);
2491 assert( p->addrOpenEphm[0] == -1 );
2492 p->addrOpenEphm[0] = addr;
2493 findRightmost(p)->selFlags |= SF_UsesEphemeral;
2494 assert( p->pEList );
2495
2496 /* Code the SELECTs to our left into temporary table "tab1".
2497 */
2498 sqlite3SelectDestInit(&intersectdest, SRT_Union, tab1);
2499 explainSetInteger(iSub1, pParse->iNextSelectId);
2500 rc = sqlite3Select(pParse, pPrior, &intersectdest);
2501 if( rc ){
2502 goto multi_select_end;
2503 }
2504
2505 /* Code the current SELECT into temporary table "tab2"
2506 */
2507 addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, tab2, 0);
2508 assert( p->addrOpenEphm[1] == -1 );
2509 p->addrOpenEphm[1] = addr;
2510 p->pPrior = 0;
2511 pLimit = p->pLimit;
2512 p->pLimit = 0;
2513 pOffset = p->pOffset;
2514 p->pOffset = 0;
2515 intersectdest.iSDParm = tab2;
2516 explainSetInteger(iSub2, pParse->iNextSelectId);
2517 rc = sqlite3Select(pParse, p, &intersectdest);
2518 testcase( rc!=SQLITE_OK );
2519 pDelete = p->pPrior;
2520 p->pPrior = pPrior;
2521 if( p->nSelectRow>pPrior->nSelectRow ) p->nSelectRow = pPrior->nSelectRow;
2522 sqlite3ExprDelete(db, p->pLimit);
2523 p->pLimit = pLimit;
2524 p->pOffset = pOffset;
2525
2526 /* Generate code to take the intersection of the two temporary
2527 ** tables.
2528 */
2529 assert( p->pEList );
2530 iBreak = sqlite3VdbeMakeLabel(v);
2531 iCont = sqlite3VdbeMakeLabel(v);
2532 computeLimitRegisters(pParse, p, iBreak);
2533 sqlite3VdbeAddOp2(v, OP_Rewind, tab1, iBreak); VdbeCoverage(v);
2534 r1 = sqlite3GetTempReg(pParse);
2535 iStart = sqlite3VdbeAddOp2(v, OP_RowData, tab1, r1);
2536 sqlite3VdbeAddOp4Int(v, OP_NotFound, tab2, iCont, r1, 0); VdbeCoverage(v);
2537 sqlite3ReleaseTempReg(pParse, r1);
2538 selectInnerLoop(pParse, p, p->pEList, tab1,
2539 0, 0, &dest, iCont, iBreak);
2540 sqlite3VdbeResolveLabel(v, iCont);
2541 sqlite3VdbeAddOp2(v, OP_Next, tab1, iStart); VdbeCoverage(v);
2542 sqlite3VdbeResolveLabel(v, iBreak);
2543 sqlite3VdbeAddOp2(v, OP_Close, tab2, 0);
2544 sqlite3VdbeAddOp2(v, OP_Close, tab1, 0);
2545 break;
2546 }
2547 }
2548
2549 explainComposite(pParse, p->op, iSub1, iSub2, p->op!=TK_ALL);
2550
2551 /* Compute collating sequences used by
2552 ** temporary tables needed to implement the compound select.
2553 ** Attach the KeyInfo structure to all temporary tables.
2554 **
2555 ** This section is run by the right-most SELECT statement only.
2556 ** SELECT statements to the left always skip this part. The right-most
2557 ** SELECT might also skip this part if it has no ORDER BY clause and
2558 ** no temp tables are required.
2559 */
2560 if( p->selFlags & SF_UsesEphemeral ){
2561 int i; /* Loop counter */
2562 KeyInfo *pKeyInfo; /* Collating sequence for the result set */
2563 Select *pLoop; /* For looping through SELECT statements */
2564 CollSeq **apColl; /* For looping through pKeyInfo->aColl[] */
2565 int nCol; /* Number of columns in result set */
2566
2567 assert( p->pNext==0 );
2568 nCol = p->pEList->nExpr;
2569 pKeyInfo = sqlite3KeyInfoAlloc(db, nCol, 1);
2570 if( !pKeyInfo ){
2571 rc = SQLITE_NOMEM_BKPT;
2572 goto multi_select_end;
2573 }
2574 for(i=0, apColl=pKeyInfo->aColl; i<nCol; i++, apColl++){
2575 *apColl = multiSelectCollSeq(pParse, p, i);
2576 if( 0==*apColl ){
2577 *apColl = db->pDfltColl;
2578 }
2579 }
2580
2581 for(pLoop=p; pLoop; pLoop=pLoop->pPrior){
2582 for(i=0; i<2; i++){
2583 int addr = pLoop->addrOpenEphm[i];
2584 if( addr<0 ){
2585 /* If [0] is unused then [1] is also unused. So we can
2586 ** always safely abort as soon as the first unused slot is found */
2587 assert( pLoop->addrOpenEphm[1]<0 );
2588 break;
2589 }
2590 sqlite3VdbeChangeP2(v, addr, nCol);
2591 sqlite3VdbeChangeP4(v, addr, (char*)sqlite3KeyInfoRef(pKeyInfo),
2592 P4_KEYINFO);
2593 pLoop->addrOpenEphm[i] = -1;
2594 }
2595 }
2596 sqlite3KeyInfoUnref(pKeyInfo);
2597 }
2598
2599 multi_select_end:
2600 pDest->iSdst = dest.iSdst;
2601 pDest->nSdst = dest.nSdst;
2602 sqlite3SelectDelete(db, pDelete);
2603 return rc;
2604 }
2605 #endif /* SQLITE_OMIT_COMPOUND_SELECT */
2606
2607 /*
2608 ** Error message for when two or more terms of a compound select have different
2609 ** size result sets.
2610 */
sqlite3SelectWrongNumTermsError(Parse * pParse,Select * p)2611 void sqlite3SelectWrongNumTermsError(Parse *pParse, Select *p){
2612 if( p->selFlags & SF_Values ){
2613 sqlite3ErrorMsg(pParse, "all VALUES must have the same number of terms");
2614 }else{
2615 sqlite3ErrorMsg(pParse, "SELECTs to the left and right of %s"
2616 " do not have the same number of result columns", selectOpName(p->op));
2617 }
2618 }
2619
2620 /*
2621 ** Code an output subroutine for a coroutine implementation of a
2622 ** SELECT statment.
2623 **
2624 ** The data to be output is contained in pIn->iSdst. There are
2625 ** pIn->nSdst columns to be output. pDest is where the output should
2626 ** be sent.
2627 **
2628 ** regReturn is the number of the register holding the subroutine
2629 ** return address.
2630 **
2631 ** If regPrev>0 then it is the first register in a vector that
2632 ** records the previous output. mem[regPrev] is a flag that is false
2633 ** if there has been no previous output. If regPrev>0 then code is
2634 ** generated to suppress duplicates. pKeyInfo is used for comparing
2635 ** keys.
2636 **
2637 ** If the LIMIT found in p->iLimit is reached, jump immediately to
2638 ** iBreak.
2639 */
generateOutputSubroutine(Parse * pParse,Select * p,SelectDest * pIn,SelectDest * pDest,int regReturn,int regPrev,KeyInfo * pKeyInfo,int iBreak)2640 static int generateOutputSubroutine(
2641 Parse *pParse, /* Parsing context */
2642 Select *p, /* The SELECT statement */
2643 SelectDest *pIn, /* Coroutine supplying data */
2644 SelectDest *pDest, /* Where to send the data */
2645 int regReturn, /* The return address register */
2646 int regPrev, /* Previous result register. No uniqueness if 0 */
2647 KeyInfo *pKeyInfo, /* For comparing with previous entry */
2648 int iBreak /* Jump here if we hit the LIMIT */
2649 ){
2650 Vdbe *v = pParse->pVdbe;
2651 int iContinue;
2652 int addr;
2653
2654 addr = sqlite3VdbeCurrentAddr(v);
2655 iContinue = sqlite3VdbeMakeLabel(v);
2656
2657 /* Suppress duplicates for UNION, EXCEPT, and INTERSECT
2658 */
2659 if( regPrev ){
2660 int addr1, addr2;
2661 addr1 = sqlite3VdbeAddOp1(v, OP_IfNot, regPrev); VdbeCoverage(v);
2662 addr2 = sqlite3VdbeAddOp4(v, OP_Compare, pIn->iSdst, regPrev+1, pIn->nSdst,
2663 (char*)sqlite3KeyInfoRef(pKeyInfo), P4_KEYINFO);
2664 sqlite3VdbeAddOp3(v, OP_Jump, addr2+2, iContinue, addr2+2); VdbeCoverage(v);
2665 sqlite3VdbeJumpHere(v, addr1);
2666 sqlite3VdbeAddOp3(v, OP_Copy, pIn->iSdst, regPrev+1, pIn->nSdst-1);
2667 sqlite3VdbeAddOp2(v, OP_Integer, 1, regPrev);
2668 }
2669 if( pParse->db->mallocFailed ) return 0;
2670
2671 /* Suppress the first OFFSET entries if there is an OFFSET clause
2672 */
2673 codeOffset(v, p->iOffset, iContinue);
2674
2675 assert( pDest->eDest!=SRT_Exists );
2676 assert( pDest->eDest!=SRT_Table );
2677 switch( pDest->eDest ){
2678 /* Store the result as data using a unique key.
2679 */
2680 case SRT_EphemTab: {
2681 int r1 = sqlite3GetTempReg(pParse);
2682 int r2 = sqlite3GetTempReg(pParse);
2683 sqlite3VdbeAddOp3(v, OP_MakeRecord, pIn->iSdst, pIn->nSdst, r1);
2684 sqlite3VdbeAddOp2(v, OP_NewRowid, pDest->iSDParm, r2);
2685 sqlite3VdbeAddOp3(v, OP_Insert, pDest->iSDParm, r1, r2);
2686 sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
2687 sqlite3ReleaseTempReg(pParse, r2);
2688 sqlite3ReleaseTempReg(pParse, r1);
2689 break;
2690 }
2691
2692 #ifndef SQLITE_OMIT_SUBQUERY
2693 /* If we are creating a set for an "expr IN (SELECT ...)".
2694 */
2695 case SRT_Set: {
2696 int r1;
2697 testcase( pIn->nSdst>1 );
2698 r1 = sqlite3GetTempReg(pParse);
2699 sqlite3VdbeAddOp4(v, OP_MakeRecord, pIn->iSdst, pIn->nSdst,
2700 r1, pDest->zAffSdst, pIn->nSdst);
2701 sqlite3ExprCacheAffinityChange(pParse, pIn->iSdst, pIn->nSdst);
2702 sqlite3VdbeAddOp4Int(v, OP_IdxInsert, pDest->iSDParm, r1,
2703 pIn->iSdst, pIn->nSdst);
2704 sqlite3ReleaseTempReg(pParse, r1);
2705 break;
2706 }
2707
2708 /* If this is a scalar select that is part of an expression, then
2709 ** store the results in the appropriate memory cell and break out
2710 ** of the scan loop.
2711 */
2712 case SRT_Mem: {
2713 assert( pIn->nSdst==1 || pParse->nErr>0 ); testcase( pIn->nSdst!=1 );
2714 sqlite3ExprCodeMove(pParse, pIn->iSdst, pDest->iSDParm, 1);
2715 /* The LIMIT clause will jump out of the loop for us */
2716 break;
2717 }
2718 #endif /* #ifndef SQLITE_OMIT_SUBQUERY */
2719
2720 /* The results are stored in a sequence of registers
2721 ** starting at pDest->iSdst. Then the co-routine yields.
2722 */
2723 case SRT_Coroutine: {
2724 if( pDest->iSdst==0 ){
2725 pDest->iSdst = sqlite3GetTempRange(pParse, pIn->nSdst);
2726 pDest->nSdst = pIn->nSdst;
2727 }
2728 sqlite3ExprCodeMove(pParse, pIn->iSdst, pDest->iSdst, pIn->nSdst);
2729 sqlite3VdbeAddOp1(v, OP_Yield, pDest->iSDParm);
2730 break;
2731 }
2732
2733 /* If none of the above, then the result destination must be
2734 ** SRT_Output. This routine is never called with any other
2735 ** destination other than the ones handled above or SRT_Output.
2736 **
2737 ** For SRT_Output, results are stored in a sequence of registers.
2738 ** Then the OP_ResultRow opcode is used to cause sqlite3_step() to
2739 ** return the next row of result.
2740 */
2741 default: {
2742 assert( pDest->eDest==SRT_Output );
2743 sqlite3VdbeAddOp2(v, OP_ResultRow, pIn->iSdst, pIn->nSdst);
2744 sqlite3ExprCacheAffinityChange(pParse, pIn->iSdst, pIn->nSdst);
2745 break;
2746 }
2747 }
2748
2749 /* Jump to the end of the loop if the LIMIT is reached.
2750 */
2751 if( p->iLimit ){
2752 sqlite3VdbeAddOp2(v, OP_DecrJumpZero, p->iLimit, iBreak); VdbeCoverage(v);
2753 }
2754
2755 /* Generate the subroutine return
2756 */
2757 sqlite3VdbeResolveLabel(v, iContinue);
2758 sqlite3VdbeAddOp1(v, OP_Return, regReturn);
2759
2760 return addr;
2761 }
2762
2763 /*
2764 ** Alternative compound select code generator for cases when there
2765 ** is an ORDER BY clause.
2766 **
2767 ** We assume a query of the following form:
2768 **
2769 ** <selectA> <operator> <selectB> ORDER BY <orderbylist>
2770 **
2771 ** <operator> is one of UNION ALL, UNION, EXCEPT, or INTERSECT. The idea
2772 ** is to code both <selectA> and <selectB> with the ORDER BY clause as
2773 ** co-routines. Then run the co-routines in parallel and merge the results
2774 ** into the output. In addition to the two coroutines (called selectA and
2775 ** selectB) there are 7 subroutines:
2776 **
2777 ** outA: Move the output of the selectA coroutine into the output
2778 ** of the compound query.
2779 **
2780 ** outB: Move the output of the selectB coroutine into the output
2781 ** of the compound query. (Only generated for UNION and
2782 ** UNION ALL. EXCEPT and INSERTSECT never output a row that
2783 ** appears only in B.)
2784 **
2785 ** AltB: Called when there is data from both coroutines and A<B.
2786 **
2787 ** AeqB: Called when there is data from both coroutines and A==B.
2788 **
2789 ** AgtB: Called when there is data from both coroutines and A>B.
2790 **
2791 ** EofA: Called when data is exhausted from selectA.
2792 **
2793 ** EofB: Called when data is exhausted from selectB.
2794 **
2795 ** The implementation of the latter five subroutines depend on which
2796 ** <operator> is used:
2797 **
2798 **
2799 ** UNION ALL UNION EXCEPT INTERSECT
2800 ** ------------- ----------------- -------------- -----------------
2801 ** AltB: outA, nextA outA, nextA outA, nextA nextA
2802 **
2803 ** AeqB: outA, nextA nextA nextA outA, nextA
2804 **
2805 ** AgtB: outB, nextB outB, nextB nextB nextB
2806 **
2807 ** EofA: outB, nextB outB, nextB halt halt
2808 **
2809 ** EofB: outA, nextA outA, nextA outA, nextA halt
2810 **
2811 ** In the AltB, AeqB, and AgtB subroutines, an EOF on A following nextA
2812 ** causes an immediate jump to EofA and an EOF on B following nextB causes
2813 ** an immediate jump to EofB. Within EofA and EofB, and EOF on entry or
2814 ** following nextX causes a jump to the end of the select processing.
2815 **
2816 ** Duplicate removal in the UNION, EXCEPT, and INTERSECT cases is handled
2817 ** within the output subroutine. The regPrev register set holds the previously
2818 ** output value. A comparison is made against this value and the output
2819 ** is skipped if the next results would be the same as the previous.
2820 **
2821 ** The implementation plan is to implement the two coroutines and seven
2822 ** subroutines first, then put the control logic at the bottom. Like this:
2823 **
2824 ** goto Init
2825 ** coA: coroutine for left query (A)
2826 ** coB: coroutine for right query (B)
2827 ** outA: output one row of A
2828 ** outB: output one row of B (UNION and UNION ALL only)
2829 ** EofA: ...
2830 ** EofB: ...
2831 ** AltB: ...
2832 ** AeqB: ...
2833 ** AgtB: ...
2834 ** Init: initialize coroutine registers
2835 ** yield coA
2836 ** if eof(A) goto EofA
2837 ** yield coB
2838 ** if eof(B) goto EofB
2839 ** Cmpr: Compare A, B
2840 ** Jump AltB, AeqB, AgtB
2841 ** End: ...
2842 **
2843 ** We call AltB, AeqB, AgtB, EofA, and EofB "subroutines" but they are not
2844 ** actually called using Gosub and they do not Return. EofA and EofB loop
2845 ** until all data is exhausted then jump to the "end" labe. AltB, AeqB,
2846 ** and AgtB jump to either L2 or to one of EofA or EofB.
2847 */
2848 #ifndef SQLITE_OMIT_COMPOUND_SELECT
multiSelectOrderBy(Parse * pParse,Select * p,SelectDest * pDest)2849 static int multiSelectOrderBy(
2850 Parse *pParse, /* Parsing context */
2851 Select *p, /* The right-most of SELECTs to be coded */
2852 SelectDest *pDest /* What to do with query results */
2853 ){
2854 int i, j; /* Loop counters */
2855 Select *pPrior; /* Another SELECT immediately to our left */
2856 Vdbe *v; /* Generate code to this VDBE */
2857 SelectDest destA; /* Destination for coroutine A */
2858 SelectDest destB; /* Destination for coroutine B */
2859 int regAddrA; /* Address register for select-A coroutine */
2860 int regAddrB; /* Address register for select-B coroutine */
2861 int addrSelectA; /* Address of the select-A coroutine */
2862 int addrSelectB; /* Address of the select-B coroutine */
2863 int regOutA; /* Address register for the output-A subroutine */
2864 int regOutB; /* Address register for the output-B subroutine */
2865 int addrOutA; /* Address of the output-A subroutine */
2866 int addrOutB = 0; /* Address of the output-B subroutine */
2867 int addrEofA; /* Address of the select-A-exhausted subroutine */
2868 int addrEofA_noB; /* Alternate addrEofA if B is uninitialized */
2869 int addrEofB; /* Address of the select-B-exhausted subroutine */
2870 int addrAltB; /* Address of the A<B subroutine */
2871 int addrAeqB; /* Address of the A==B subroutine */
2872 int addrAgtB; /* Address of the A>B subroutine */
2873 int regLimitA; /* Limit register for select-A */
2874 int regLimitB; /* Limit register for select-A */
2875 int regPrev; /* A range of registers to hold previous output */
2876 int savedLimit; /* Saved value of p->iLimit */
2877 int savedOffset; /* Saved value of p->iOffset */
2878 int labelCmpr; /* Label for the start of the merge algorithm */
2879 int labelEnd; /* Label for the end of the overall SELECT stmt */
2880 int addr1; /* Jump instructions that get retargetted */
2881 int op; /* One of TK_ALL, TK_UNION, TK_EXCEPT, TK_INTERSECT */
2882 KeyInfo *pKeyDup = 0; /* Comparison information for duplicate removal */
2883 KeyInfo *pKeyMerge; /* Comparison information for merging rows */
2884 sqlite3 *db; /* Database connection */
2885 ExprList *pOrderBy; /* The ORDER BY clause */
2886 int nOrderBy; /* Number of terms in the ORDER BY clause */
2887 int *aPermute; /* Mapping from ORDER BY terms to result set columns */
2888 #ifndef SQLITE_OMIT_EXPLAIN
2889 int iSub1; /* EQP id of left-hand query */
2890 int iSub2; /* EQP id of right-hand query */
2891 #endif
2892
2893 assert( p->pOrderBy!=0 );
2894 assert( pKeyDup==0 ); /* "Managed" code needs this. Ticket #3382. */
2895 db = pParse->db;
2896 v = pParse->pVdbe;
2897 assert( v!=0 ); /* Already thrown the error if VDBE alloc failed */
2898 labelEnd = sqlite3VdbeMakeLabel(v);
2899 labelCmpr = sqlite3VdbeMakeLabel(v);
2900
2901
2902 /* Patch up the ORDER BY clause
2903 */
2904 op = p->op;
2905 pPrior = p->pPrior;
2906 assert( pPrior->pOrderBy==0 );
2907 pOrderBy = p->pOrderBy;
2908 assert( pOrderBy );
2909 nOrderBy = pOrderBy->nExpr;
2910
2911 /* For operators other than UNION ALL we have to make sure that
2912 ** the ORDER BY clause covers every term of the result set. Add
2913 ** terms to the ORDER BY clause as necessary.
2914 */
2915 if( op!=TK_ALL ){
2916 for(i=1; db->mallocFailed==0 && i<=p->pEList->nExpr; i++){
2917 struct ExprList_item *pItem;
2918 for(j=0, pItem=pOrderBy->a; j<nOrderBy; j++, pItem++){
2919 assert( pItem->u.x.iOrderByCol>0 );
2920 if( pItem->u.x.iOrderByCol==i ) break;
2921 }
2922 if( j==nOrderBy ){
2923 Expr *pNew = sqlite3Expr(db, TK_INTEGER, 0);
2924 if( pNew==0 ) return SQLITE_NOMEM_BKPT;
2925 pNew->flags |= EP_IntValue;
2926 pNew->u.iValue = i;
2927 p->pOrderBy = pOrderBy = sqlite3ExprListAppend(pParse, pOrderBy, pNew);
2928 if( pOrderBy ) pOrderBy->a[nOrderBy++].u.x.iOrderByCol = (u16)i;
2929 }
2930 }
2931 }
2932
2933 /* Compute the comparison permutation and keyinfo that is used with
2934 ** the permutation used to determine if the next
2935 ** row of results comes from selectA or selectB. Also add explicit
2936 ** collations to the ORDER BY clause terms so that when the subqueries
2937 ** to the right and the left are evaluated, they use the correct
2938 ** collation.
2939 */
2940 aPermute = sqlite3DbMallocRawNN(db, sizeof(int)*(nOrderBy + 1));
2941 if( aPermute ){
2942 struct ExprList_item *pItem;
2943 aPermute[0] = nOrderBy;
2944 for(i=1, pItem=pOrderBy->a; i<=nOrderBy; i++, pItem++){
2945 assert( pItem->u.x.iOrderByCol>0 );
2946 assert( pItem->u.x.iOrderByCol<=p->pEList->nExpr );
2947 aPermute[i] = pItem->u.x.iOrderByCol - 1;
2948 }
2949 pKeyMerge = multiSelectOrderByKeyInfo(pParse, p, 1);
2950 }else{
2951 pKeyMerge = 0;
2952 }
2953
2954 /* Reattach the ORDER BY clause to the query.
2955 */
2956 p->pOrderBy = pOrderBy;
2957 pPrior->pOrderBy = sqlite3ExprListDup(pParse->db, pOrderBy, 0);
2958
2959 /* Allocate a range of temporary registers and the KeyInfo needed
2960 ** for the logic that removes duplicate result rows when the
2961 ** operator is UNION, EXCEPT, or INTERSECT (but not UNION ALL).
2962 */
2963 if( op==TK_ALL ){
2964 regPrev = 0;
2965 }else{
2966 int nExpr = p->pEList->nExpr;
2967 assert( nOrderBy>=nExpr || db->mallocFailed );
2968 regPrev = pParse->nMem+1;
2969 pParse->nMem += nExpr+1;
2970 sqlite3VdbeAddOp2(v, OP_Integer, 0, regPrev);
2971 pKeyDup = sqlite3KeyInfoAlloc(db, nExpr, 1);
2972 if( pKeyDup ){
2973 assert( sqlite3KeyInfoIsWriteable(pKeyDup) );
2974 for(i=0; i<nExpr; i++){
2975 pKeyDup->aColl[i] = multiSelectCollSeq(pParse, p, i);
2976 pKeyDup->aSortOrder[i] = 0;
2977 }
2978 }
2979 }
2980
2981 /* Separate the left and the right query from one another
2982 */
2983 p->pPrior = 0;
2984 pPrior->pNext = 0;
2985 sqlite3ResolveOrderGroupBy(pParse, p, p->pOrderBy, "ORDER");
2986 if( pPrior->pPrior==0 ){
2987 sqlite3ResolveOrderGroupBy(pParse, pPrior, pPrior->pOrderBy, "ORDER");
2988 }
2989
2990 /* Compute the limit registers */
2991 computeLimitRegisters(pParse, p, labelEnd);
2992 if( p->iLimit && op==TK_ALL ){
2993 regLimitA = ++pParse->nMem;
2994 regLimitB = ++pParse->nMem;
2995 sqlite3VdbeAddOp2(v, OP_Copy, p->iOffset ? p->iOffset+1 : p->iLimit,
2996 regLimitA);
2997 sqlite3VdbeAddOp2(v, OP_Copy, regLimitA, regLimitB);
2998 }else{
2999 regLimitA = regLimitB = 0;
3000 }
3001 sqlite3ExprDelete(db, p->pLimit);
3002 p->pLimit = 0;
3003 sqlite3ExprDelete(db, p->pOffset);
3004 p->pOffset = 0;
3005
3006 regAddrA = ++pParse->nMem;
3007 regAddrB = ++pParse->nMem;
3008 regOutA = ++pParse->nMem;
3009 regOutB = ++pParse->nMem;
3010 sqlite3SelectDestInit(&destA, SRT_Coroutine, regAddrA);
3011 sqlite3SelectDestInit(&destB, SRT_Coroutine, regAddrB);
3012
3013 /* Generate a coroutine to evaluate the SELECT statement to the
3014 ** left of the compound operator - the "A" select.
3015 */
3016 addrSelectA = sqlite3VdbeCurrentAddr(v) + 1;
3017 addr1 = sqlite3VdbeAddOp3(v, OP_InitCoroutine, regAddrA, 0, addrSelectA);
3018 VdbeComment((v, "left SELECT"));
3019 pPrior->iLimit = regLimitA;
3020 explainSetInteger(iSub1, pParse->iNextSelectId);
3021 sqlite3Select(pParse, pPrior, &destA);
3022 sqlite3VdbeEndCoroutine(v, regAddrA);
3023 sqlite3VdbeJumpHere(v, addr1);
3024
3025 /* Generate a coroutine to evaluate the SELECT statement on
3026 ** the right - the "B" select
3027 */
3028 addrSelectB = sqlite3VdbeCurrentAddr(v) + 1;
3029 addr1 = sqlite3VdbeAddOp3(v, OP_InitCoroutine, regAddrB, 0, addrSelectB);
3030 VdbeComment((v, "right SELECT"));
3031 savedLimit = p->iLimit;
3032 savedOffset = p->iOffset;
3033 p->iLimit = regLimitB;
3034 p->iOffset = 0;
3035 explainSetInteger(iSub2, pParse->iNextSelectId);
3036 sqlite3Select(pParse, p, &destB);
3037 p->iLimit = savedLimit;
3038 p->iOffset = savedOffset;
3039 sqlite3VdbeEndCoroutine(v, regAddrB);
3040
3041 /* Generate a subroutine that outputs the current row of the A
3042 ** select as the next output row of the compound select.
3043 */
3044 VdbeNoopComment((v, "Output routine for A"));
3045 addrOutA = generateOutputSubroutine(pParse,
3046 p, &destA, pDest, regOutA,
3047 regPrev, pKeyDup, labelEnd);
3048
3049 /* Generate a subroutine that outputs the current row of the B
3050 ** select as the next output row of the compound select.
3051 */
3052 if( op==TK_ALL || op==TK_UNION ){
3053 VdbeNoopComment((v, "Output routine for B"));
3054 addrOutB = generateOutputSubroutine(pParse,
3055 p, &destB, pDest, regOutB,
3056 regPrev, pKeyDup, labelEnd);
3057 }
3058 sqlite3KeyInfoUnref(pKeyDup);
3059
3060 /* Generate a subroutine to run when the results from select A
3061 ** are exhausted and only data in select B remains.
3062 */
3063 if( op==TK_EXCEPT || op==TK_INTERSECT ){
3064 addrEofA_noB = addrEofA = labelEnd;
3065 }else{
3066 VdbeNoopComment((v, "eof-A subroutine"));
3067 addrEofA = sqlite3VdbeAddOp2(v, OP_Gosub, regOutB, addrOutB);
3068 addrEofA_noB = sqlite3VdbeAddOp2(v, OP_Yield, regAddrB, labelEnd);
3069 VdbeCoverage(v);
3070 sqlite3VdbeGoto(v, addrEofA);
3071 p->nSelectRow = sqlite3LogEstAdd(p->nSelectRow, pPrior->nSelectRow);
3072 }
3073
3074 /* Generate a subroutine to run when the results from select B
3075 ** are exhausted and only data in select A remains.
3076 */
3077 if( op==TK_INTERSECT ){
3078 addrEofB = addrEofA;
3079 if( p->nSelectRow > pPrior->nSelectRow ) p->nSelectRow = pPrior->nSelectRow;
3080 }else{
3081 VdbeNoopComment((v, "eof-B subroutine"));
3082 addrEofB = sqlite3VdbeAddOp2(v, OP_Gosub, regOutA, addrOutA);
3083 sqlite3VdbeAddOp2(v, OP_Yield, regAddrA, labelEnd); VdbeCoverage(v);
3084 sqlite3VdbeGoto(v, addrEofB);
3085 }
3086
3087 /* Generate code to handle the case of A<B
3088 */
3089 VdbeNoopComment((v, "A-lt-B subroutine"));
3090 addrAltB = sqlite3VdbeAddOp2(v, OP_Gosub, regOutA, addrOutA);
3091 sqlite3VdbeAddOp2(v, OP_Yield, regAddrA, addrEofA); VdbeCoverage(v);
3092 sqlite3VdbeGoto(v, labelCmpr);
3093
3094 /* Generate code to handle the case of A==B
3095 */
3096 if( op==TK_ALL ){
3097 addrAeqB = addrAltB;
3098 }else if( op==TK_INTERSECT ){
3099 addrAeqB = addrAltB;
3100 addrAltB++;
3101 }else{
3102 VdbeNoopComment((v, "A-eq-B subroutine"));
3103 addrAeqB =
3104 sqlite3VdbeAddOp2(v, OP_Yield, regAddrA, addrEofA); VdbeCoverage(v);
3105 sqlite3VdbeGoto(v, labelCmpr);
3106 }
3107
3108 /* Generate code to handle the case of A>B
3109 */
3110 VdbeNoopComment((v, "A-gt-B subroutine"));
3111 addrAgtB = sqlite3VdbeCurrentAddr(v);
3112 if( op==TK_ALL || op==TK_UNION ){
3113 sqlite3VdbeAddOp2(v, OP_Gosub, regOutB, addrOutB);
3114 }
3115 sqlite3VdbeAddOp2(v, OP_Yield, regAddrB, addrEofB); VdbeCoverage(v);
3116 sqlite3VdbeGoto(v, labelCmpr);
3117
3118 /* This code runs once to initialize everything.
3119 */
3120 sqlite3VdbeJumpHere(v, addr1);
3121 sqlite3VdbeAddOp2(v, OP_Yield, regAddrA, addrEofA_noB); VdbeCoverage(v);
3122 sqlite3VdbeAddOp2(v, OP_Yield, regAddrB, addrEofB); VdbeCoverage(v);
3123
3124 /* Implement the main merge loop
3125 */
3126 sqlite3VdbeResolveLabel(v, labelCmpr);
3127 sqlite3VdbeAddOp4(v, OP_Permutation, 0, 0, 0, (char*)aPermute, P4_INTARRAY);
3128 sqlite3VdbeAddOp4(v, OP_Compare, destA.iSdst, destB.iSdst, nOrderBy,
3129 (char*)pKeyMerge, P4_KEYINFO);
3130 sqlite3VdbeChangeP5(v, OPFLAG_PERMUTE);
3131 sqlite3VdbeAddOp3(v, OP_Jump, addrAltB, addrAeqB, addrAgtB); VdbeCoverage(v);
3132
3133 /* Jump to the this point in order to terminate the query.
3134 */
3135 sqlite3VdbeResolveLabel(v, labelEnd);
3136
3137 /* Reassembly the compound query so that it will be freed correctly
3138 ** by the calling function */
3139 if( p->pPrior ){
3140 sqlite3SelectDelete(db, p->pPrior);
3141 }
3142 p->pPrior = pPrior;
3143 pPrior->pNext = p;
3144
3145 /*** TBD: Insert subroutine calls to close cursors on incomplete
3146 **** subqueries ****/
3147 explainComposite(pParse, p->op, iSub1, iSub2, 0);
3148 return pParse->nErr!=0;
3149 }
3150 #endif
3151
3152 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3153
3154 /* An instance of the SubstContext object describes an substitution edit
3155 ** to be performed on a parse tree.
3156 **
3157 ** All references to columns in table iTable are to be replaced by corresponding
3158 ** expressions in pEList.
3159 */
3160 typedef struct SubstContext {
3161 Parse *pParse; /* The parsing context */
3162 int iTable; /* Replace references to this table */
3163 int iNewTable; /* New table number */
3164 int isLeftJoin; /* Add TK_IF_NULL_ROW opcodes on each replacement */
3165 ExprList *pEList; /* Replacement expressions */
3166 } SubstContext;
3167
3168 /* Forward Declarations */
3169 static void substExprList(SubstContext*, ExprList*);
3170 static void substSelect(SubstContext*, Select*, int);
3171
3172 /*
3173 ** Scan through the expression pExpr. Replace every reference to
3174 ** a column in table number iTable with a copy of the iColumn-th
3175 ** entry in pEList. (But leave references to the ROWID column
3176 ** unchanged.)
3177 **
3178 ** This routine is part of the flattening procedure. A subquery
3179 ** whose result set is defined by pEList appears as entry in the
3180 ** FROM clause of a SELECT such that the VDBE cursor assigned to that
3181 ** FORM clause entry is iTable. This routine makes the necessary
3182 ** changes to pExpr so that it refers directly to the source table
3183 ** of the subquery rather the result set of the subquery.
3184 */
substExpr(SubstContext * pSubst,Expr * pExpr)3185 static Expr *substExpr(
3186 SubstContext *pSubst, /* Description of the substitution */
3187 Expr *pExpr /* Expr in which substitution occurs */
3188 ){
3189 if( pExpr==0 ) return 0;
3190 if( ExprHasProperty(pExpr, EP_FromJoin) && pExpr->iRightJoinTable==pSubst->iTable ){
3191 pExpr->iRightJoinTable = pSubst->iNewTable;
3192 }
3193 if( pExpr->op==TK_COLUMN && pExpr->iTable==pSubst->iTable ){
3194 if( pExpr->iColumn<0 ){
3195 pExpr->op = TK_NULL;
3196 }else{
3197 Expr *pNew;
3198 Expr *pCopy = pSubst->pEList->a[pExpr->iColumn].pExpr;
3199 Expr ifNullRow;
3200 assert( pSubst->pEList!=0 && pExpr->iColumn<pSubst->pEList->nExpr );
3201 assert( pExpr->pLeft==0 && pExpr->pRight==0 );
3202 if( sqlite3ExprIsVector(pCopy) ){
3203 sqlite3VectorErrorMsg(pSubst->pParse, pCopy);
3204 }else{
3205 sqlite3 *db = pSubst->pParse->db;
3206 if( pSubst->isLeftJoin && pCopy->op!=TK_COLUMN ){
3207 memset(&ifNullRow, 0, sizeof(ifNullRow));
3208 ifNullRow.op = TK_IF_NULL_ROW;
3209 ifNullRow.pLeft = pCopy;
3210 ifNullRow.iTable = pSubst->iNewTable;
3211 pCopy = &ifNullRow;
3212 }
3213 pNew = sqlite3ExprDup(db, pCopy, 0);
3214 if( pNew && pSubst->isLeftJoin ){
3215 ExprSetProperty(pNew, EP_CanBeNull);
3216 }
3217 if( pNew && ExprHasProperty(pExpr,EP_FromJoin) ){
3218 pNew->iRightJoinTable = pExpr->iRightJoinTable;
3219 ExprSetProperty(pNew, EP_FromJoin);
3220 }
3221 sqlite3ExprDelete(db, pExpr);
3222 pExpr = pNew;
3223 }
3224 }
3225 }else{
3226 if( pExpr->op==TK_IF_NULL_ROW && pExpr->iTable==pSubst->iTable ){
3227 pExpr->iTable = pSubst->iNewTable;
3228 }
3229 pExpr->pLeft = substExpr(pSubst, pExpr->pLeft);
3230 pExpr->pRight = substExpr(pSubst, pExpr->pRight);
3231 if( ExprHasProperty(pExpr, EP_xIsSelect) ){
3232 substSelect(pSubst, pExpr->x.pSelect, 1);
3233 }else{
3234 substExprList(pSubst, pExpr->x.pList);
3235 }
3236 }
3237 return pExpr;
3238 }
substExprList(SubstContext * pSubst,ExprList * pList)3239 static void substExprList(
3240 SubstContext *pSubst, /* Description of the substitution */
3241 ExprList *pList /* List to scan and in which to make substitutes */
3242 ){
3243 int i;
3244 if( pList==0 ) return;
3245 for(i=0; i<pList->nExpr; i++){
3246 pList->a[i].pExpr = substExpr(pSubst, pList->a[i].pExpr);
3247 }
3248 }
substSelect(SubstContext * pSubst,Select * p,int doPrior)3249 static void substSelect(
3250 SubstContext *pSubst, /* Description of the substitution */
3251 Select *p, /* SELECT statement in which to make substitutions */
3252 int doPrior /* Do substitutes on p->pPrior too */
3253 ){
3254 SrcList *pSrc;
3255 struct SrcList_item *pItem;
3256 int i;
3257 if( !p ) return;
3258 do{
3259 substExprList(pSubst, p->pEList);
3260 substExprList(pSubst, p->pGroupBy);
3261 substExprList(pSubst, p->pOrderBy);
3262 p->pHaving = substExpr(pSubst, p->pHaving);
3263 p->pWhere = substExpr(pSubst, p->pWhere);
3264 pSrc = p->pSrc;
3265 assert( pSrc!=0 );
3266 for(i=pSrc->nSrc, pItem=pSrc->a; i>0; i--, pItem++){
3267 substSelect(pSubst, pItem->pSelect, 1);
3268 if( pItem->fg.isTabFunc ){
3269 substExprList(pSubst, pItem->u1.pFuncArg);
3270 }
3271 }
3272 }while( doPrior && (p = p->pPrior)!=0 );
3273 }
3274 #endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */
3275
3276 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3277 /*
3278 ** This routine attempts to flatten subqueries as a performance optimization.
3279 ** This routine returns 1 if it makes changes and 0 if no flattening occurs.
3280 **
3281 ** To understand the concept of flattening, consider the following
3282 ** query:
3283 **
3284 ** SELECT a FROM (SELECT x+y AS a FROM t1 WHERE z<100) WHERE a>5
3285 **
3286 ** The default way of implementing this query is to execute the
3287 ** subquery first and store the results in a temporary table, then
3288 ** run the outer query on that temporary table. This requires two
3289 ** passes over the data. Furthermore, because the temporary table
3290 ** has no indices, the WHERE clause on the outer query cannot be
3291 ** optimized.
3292 **
3293 ** This routine attempts to rewrite queries such as the above into
3294 ** a single flat select, like this:
3295 **
3296 ** SELECT x+y AS a FROM t1 WHERE z<100 AND a>5
3297 **
3298 ** The code generated for this simplification gives the same result
3299 ** but only has to scan the data once. And because indices might
3300 ** exist on the table t1, a complete scan of the data might be
3301 ** avoided.
3302 **
3303 ** Flattening is only attempted if all of the following are true:
3304 **
3305 ** (1) The subquery and the outer query do not both use aggregates.
3306 **
3307 ** (2) The subquery is not an aggregate or (2a) the outer query is not a join
3308 ** and (2b) the outer query does not use subqueries other than the one
3309 ** FROM-clause subquery that is a candidate for flattening. (2b is
3310 ** due to ticket [2f7170d73bf9abf80] from 2015-02-09.)
3311 **
3312 ** (3) The subquery is not the right operand of a LEFT JOIN
3313 ** or (a) the subquery is not itself a join and (b) the FROM clause
3314 ** of the subquery does not contain a virtual table and (c) the
3315 ** outer query is not an aggregate.
3316 **
3317 ** (4) The subquery is not DISTINCT.
3318 **
3319 ** (**) At one point restrictions (4) and (5) defined a subset of DISTINCT
3320 ** sub-queries that were excluded from this optimization. Restriction
3321 ** (4) has since been expanded to exclude all DISTINCT subqueries.
3322 **
3323 ** (6) The subquery does not use aggregates or the outer query is not
3324 ** DISTINCT.
3325 **
3326 ** (7) The subquery has a FROM clause. TODO: For subqueries without
3327 ** A FROM clause, consider adding a FROM clause with the special
3328 ** table sqlite_once that consists of a single row containing a
3329 ** single NULL.
3330 **
3331 ** (8) The subquery does not use LIMIT or the outer query is not a join.
3332 **
3333 ** (9) The subquery does not use LIMIT or the outer query does not use
3334 ** aggregates.
3335 **
3336 ** (**) Restriction (10) was removed from the code on 2005-02-05 but we
3337 ** accidently carried the comment forward until 2014-09-15. Original
3338 ** text: "The subquery does not use aggregates or the outer query
3339 ** does not use LIMIT."
3340 **
3341 ** (11) The subquery and the outer query do not both have ORDER BY clauses.
3342 **
3343 ** (**) Not implemented. Subsumed into restriction (3). Was previously
3344 ** a separate restriction deriving from ticket #350.
3345 **
3346 ** (13) The subquery and outer query do not both use LIMIT.
3347 **
3348 ** (14) The subquery does not use OFFSET.
3349 **
3350 ** (15) The outer query is not part of a compound select or the
3351 ** subquery does not have a LIMIT clause.
3352 ** (See ticket #2339 and ticket [02a8e81d44]).
3353 **
3354 ** (16) The outer query is not an aggregate or the subquery does
3355 ** not contain ORDER BY. (Ticket #2942) This used to not matter
3356 ** until we introduced the group_concat() function.
3357 **
3358 ** (17) The sub-query is not a compound select, or it is a UNION ALL
3359 ** compound clause made up entirely of non-aggregate queries, and
3360 ** the parent query:
3361 **
3362 ** * is not itself part of a compound select,
3363 ** * is not an aggregate or DISTINCT query, and
3364 ** * is not a join
3365 **
3366 ** The parent and sub-query may contain WHERE clauses. Subject to
3367 ** rules (11), (13) and (14), they may also contain ORDER BY,
3368 ** LIMIT and OFFSET clauses. The subquery cannot use any compound
3369 ** operator other than UNION ALL because all the other compound
3370 ** operators have an implied DISTINCT which is disallowed by
3371 ** restriction (4).
3372 **
3373 ** Also, each component of the sub-query must return the same number
3374 ** of result columns. This is actually a requirement for any compound
3375 ** SELECT statement, but all the code here does is make sure that no
3376 ** such (illegal) sub-query is flattened. The caller will detect the
3377 ** syntax error and return a detailed message.
3378 **
3379 ** (18) If the sub-query is a compound select, then all terms of the
3380 ** ORDER by clause of the parent must be simple references to
3381 ** columns of the sub-query.
3382 **
3383 ** (19) The subquery does not use LIMIT or the outer query does not
3384 ** have a WHERE clause.
3385 **
3386 ** (20) If the sub-query is a compound select, then it must not use
3387 ** an ORDER BY clause. Ticket #3773. We could relax this constraint
3388 ** somewhat by saying that the terms of the ORDER BY clause must
3389 ** appear as unmodified result columns in the outer query. But we
3390 ** have other optimizations in mind to deal with that case.
3391 **
3392 ** (21) The subquery does not use LIMIT or the outer query is not
3393 ** DISTINCT. (See ticket [752e1646fc]).
3394 **
3395 ** (22) The subquery is not a recursive CTE.
3396 **
3397 ** (23) The parent is not a recursive CTE, or the sub-query is not a
3398 ** compound query. This restriction is because transforming the
3399 ** parent to a compound query confuses the code that handles
3400 ** recursive queries in multiSelect().
3401 **
3402 ** (24) The subquery is not an aggregate that uses the built-in min() or
3403 ** or max() functions. (Without this restriction, a query like:
3404 ** "SELECT x FROM (SELECT max(y), x FROM t1)" would not necessarily
3405 ** return the value X for which Y was maximal.)
3406 **
3407 **
3408 ** In this routine, the "p" parameter is a pointer to the outer query.
3409 ** The subquery is p->pSrc->a[iFrom]. isAgg is true if the outer query
3410 ** uses aggregates and subqueryIsAgg is true if the subquery uses aggregates.
3411 **
3412 ** If flattening is not attempted, this routine is a no-op and returns 0.
3413 ** If flattening is attempted this routine returns 1.
3414 **
3415 ** All of the expression analysis must occur on both the outer query and
3416 ** the subquery before this routine runs.
3417 */
flattenSubquery(Parse * pParse,Select * p,int iFrom,int isAgg,int subqueryIsAgg)3418 static int flattenSubquery(
3419 Parse *pParse, /* Parsing context */
3420 Select *p, /* The parent or outer SELECT statement */
3421 int iFrom, /* Index in p->pSrc->a[] of the inner subquery */
3422 int isAgg, /* True if outer SELECT uses aggregate functions */
3423 int subqueryIsAgg /* True if the subquery uses aggregate functions */
3424 ){
3425 const char *zSavedAuthContext = pParse->zAuthContext;
3426 Select *pParent; /* Current UNION ALL term of the other query */
3427 Select *pSub; /* The inner query or "subquery" */
3428 Select *pSub1; /* Pointer to the rightmost select in sub-query */
3429 SrcList *pSrc; /* The FROM clause of the outer query */
3430 SrcList *pSubSrc; /* The FROM clause of the subquery */
3431 int iParent; /* VDBE cursor number of the pSub result set temp table */
3432 int iNewParent = -1;/* Replacement table for iParent */
3433 int isLeftJoin = 0; /* True if pSub is the right side of a LEFT JOIN */
3434 int i; /* Loop counter */
3435 Expr *pWhere; /* The WHERE clause */
3436 struct SrcList_item *pSubitem; /* The subquery */
3437 sqlite3 *db = pParse->db;
3438
3439 /* Check to see if flattening is permitted. Return 0 if not.
3440 */
3441 assert( p!=0 );
3442 assert( p->pPrior==0 ); /* Unable to flatten compound queries */
3443 if( OptimizationDisabled(db, SQLITE_QueryFlattener) ) return 0;
3444 pSrc = p->pSrc;
3445 assert( pSrc && iFrom>=0 && iFrom<pSrc->nSrc );
3446 pSubitem = &pSrc->a[iFrom];
3447 iParent = pSubitem->iCursor;
3448 pSub = pSubitem->pSelect;
3449 assert( pSub!=0 );
3450 if( subqueryIsAgg ){
3451 if( isAgg ) return 0; /* Restriction (1) */
3452 if( pSrc->nSrc>1 ) return 0; /* Restriction (2a) */
3453 if( (p->pWhere && ExprHasProperty(p->pWhere,EP_Subquery))
3454 || (sqlite3ExprListFlags(p->pEList) & EP_Subquery)!=0
3455 || (sqlite3ExprListFlags(p->pOrderBy) & EP_Subquery)!=0
3456 ){
3457 return 0; /* Restriction (2b) */
3458 }
3459 }
3460
3461 pSubSrc = pSub->pSrc;
3462 assert( pSubSrc );
3463 /* Prior to version 3.1.2, when LIMIT and OFFSET had to be simple constants,
3464 ** not arbitrary expressions, we allowed some combining of LIMIT and OFFSET
3465 ** because they could be computed at compile-time. But when LIMIT and OFFSET
3466 ** became arbitrary expressions, we were forced to add restrictions (13)
3467 ** and (14). */
3468 if( pSub->pLimit && p->pLimit ) return 0; /* Restriction (13) */
3469 if( pSub->pOffset ) return 0; /* Restriction (14) */
3470 if( (p->selFlags & SF_Compound)!=0 && pSub->pLimit ){
3471 return 0; /* Restriction (15) */
3472 }
3473 if( pSubSrc->nSrc==0 ) return 0; /* Restriction (7) */
3474 if( pSub->selFlags & SF_Distinct ) return 0; /* Restriction (5) */
3475 if( pSub->pLimit && (pSrc->nSrc>1 || isAgg) ){
3476 return 0; /* Restrictions (8)(9) */
3477 }
3478 if( (p->selFlags & SF_Distinct)!=0 && subqueryIsAgg ){
3479 return 0; /* Restriction (6) */
3480 }
3481 if( p->pOrderBy && pSub->pOrderBy ){
3482 return 0; /* Restriction (11) */
3483 }
3484 if( isAgg && pSub->pOrderBy ) return 0; /* Restriction (16) */
3485 if( pSub->pLimit && p->pWhere ) return 0; /* Restriction (19) */
3486 if( pSub->pLimit && (p->selFlags & SF_Distinct)!=0 ){
3487 return 0; /* Restriction (21) */
3488 }
3489 testcase( pSub->selFlags & SF_Recursive );
3490 testcase( pSub->selFlags & SF_MinMaxAgg );
3491 if( pSub->selFlags & (SF_Recursive|SF_MinMaxAgg) ){
3492 return 0; /* Restrictions (22) and (24) */
3493 }
3494 if( (p->selFlags & SF_Recursive) && pSub->pPrior ){
3495 return 0; /* Restriction (23) */
3496 }
3497
3498 /*
3499 ** If the subquery is the right operand of a LEFT JOIN, then the
3500 ** subquery may not be a join itself. Example of why this is not allowed:
3501 **
3502 ** t1 LEFT OUTER JOIN (t2 JOIN t3)
3503 **
3504 ** If we flatten the above, we would get
3505 **
3506 ** (t1 LEFT OUTER JOIN t2) JOIN t3
3507 **
3508 ** which is not at all the same thing.
3509 **
3510 ** If the subquery is the right operand of a LEFT JOIN, then the outer
3511 ** query cannot be an aggregate. This is an artifact of the way aggregates
3512 ** are processed - there is no mechanism to determine if the LEFT JOIN
3513 ** table should be all-NULL.
3514 **
3515 ** See also tickets #306, #350, and #3300.
3516 */
3517 if( (pSubitem->fg.jointype & JT_OUTER)!=0 ){
3518 isLeftJoin = 1;
3519 if( pSubSrc->nSrc>1 || isAgg || IsVirtual(pSubSrc->a[0].pTab) ){
3520 return 0; /* Restriction (3) */
3521 }
3522 }
3523 #ifdef SQLITE_EXTRA_IFNULLROW
3524 else if( iFrom>0 && !isAgg ){
3525 /* Setting isLeftJoin to -1 causes OP_IfNullRow opcodes to be generated for
3526 ** every reference to any result column from subquery in a join, even though
3527 ** they are not necessary. This will stress-test the OP_IfNullRow opcode. */
3528 isLeftJoin = -1;
3529 }
3530 #endif
3531
3532 /* Restriction 17: If the sub-query is a compound SELECT, then it must
3533 ** use only the UNION ALL operator. And none of the simple select queries
3534 ** that make up the compound SELECT are allowed to be aggregate or distinct
3535 ** queries.
3536 */
3537 if( pSub->pPrior ){
3538 if( pSub->pOrderBy ){
3539 return 0; /* Restriction 20 */
3540 }
3541 if( isAgg || (p->selFlags & SF_Distinct)!=0 || pSrc->nSrc!=1 ){
3542 return 0;
3543 }
3544 for(pSub1=pSub; pSub1; pSub1=pSub1->pPrior){
3545 testcase( (pSub1->selFlags & (SF_Distinct|SF_Aggregate))==SF_Distinct );
3546 testcase( (pSub1->selFlags & (SF_Distinct|SF_Aggregate))==SF_Aggregate );
3547 assert( pSub->pSrc!=0 );
3548 assert( pSub->pEList->nExpr==pSub1->pEList->nExpr );
3549 if( (pSub1->selFlags & (SF_Distinct|SF_Aggregate))!=0
3550 || (pSub1->pPrior && pSub1->op!=TK_ALL)
3551 || pSub1->pSrc->nSrc<1
3552 ){
3553 return 0;
3554 }
3555 testcase( pSub1->pSrc->nSrc>1 );
3556 }
3557
3558 /* Restriction 18. */
3559 if( p->pOrderBy ){
3560 int ii;
3561 for(ii=0; ii<p->pOrderBy->nExpr; ii++){
3562 if( p->pOrderBy->a[ii].u.x.iOrderByCol==0 ) return 0;
3563 }
3564 }
3565 }
3566
3567 /***** If we reach this point, flattening is permitted. *****/
3568 SELECTTRACE(1,pParse,p,("flatten %s.%p from term %d\n",
3569 pSub->zSelName, pSub, iFrom));
3570
3571 /* Authorize the subquery */
3572 pParse->zAuthContext = pSubitem->zName;
3573 TESTONLY(i =) sqlite3AuthCheck(pParse, SQLITE_SELECT, 0, 0, 0);
3574 testcase( i==SQLITE_DENY );
3575 pParse->zAuthContext = zSavedAuthContext;
3576
3577 /* If the sub-query is a compound SELECT statement, then (by restrictions
3578 ** 17 and 18 above) it must be a UNION ALL and the parent query must
3579 ** be of the form:
3580 **
3581 ** SELECT <expr-list> FROM (<sub-query>) <where-clause>
3582 **
3583 ** followed by any ORDER BY, LIMIT and/or OFFSET clauses. This block
3584 ** creates N-1 copies of the parent query without any ORDER BY, LIMIT or
3585 ** OFFSET clauses and joins them to the left-hand-side of the original
3586 ** using UNION ALL operators. In this case N is the number of simple
3587 ** select statements in the compound sub-query.
3588 **
3589 ** Example:
3590 **
3591 ** SELECT a+1 FROM (
3592 ** SELECT x FROM tab
3593 ** UNION ALL
3594 ** SELECT y FROM tab
3595 ** UNION ALL
3596 ** SELECT abs(z*2) FROM tab2
3597 ** ) WHERE a!=5 ORDER BY 1
3598 **
3599 ** Transformed into:
3600 **
3601 ** SELECT x+1 FROM tab WHERE x+1!=5
3602 ** UNION ALL
3603 ** SELECT y+1 FROM tab WHERE y+1!=5
3604 ** UNION ALL
3605 ** SELECT abs(z*2)+1 FROM tab2 WHERE abs(z*2)+1!=5
3606 ** ORDER BY 1
3607 **
3608 ** We call this the "compound-subquery flattening".
3609 */
3610 for(pSub=pSub->pPrior; pSub; pSub=pSub->pPrior){
3611 Select *pNew;
3612 ExprList *pOrderBy = p->pOrderBy;
3613 Expr *pLimit = p->pLimit;
3614 Expr *pOffset = p->pOffset;
3615 Select *pPrior = p->pPrior;
3616 p->pOrderBy = 0;
3617 p->pSrc = 0;
3618 p->pPrior = 0;
3619 p->pLimit = 0;
3620 p->pOffset = 0;
3621 pNew = sqlite3SelectDup(db, p, 0);
3622 sqlite3SelectSetName(pNew, pSub->zSelName);
3623 p->pOffset = pOffset;
3624 p->pLimit = pLimit;
3625 p->pOrderBy = pOrderBy;
3626 p->pSrc = pSrc;
3627 p->op = TK_ALL;
3628 if( pNew==0 ){
3629 p->pPrior = pPrior;
3630 }else{
3631 pNew->pPrior = pPrior;
3632 if( pPrior ) pPrior->pNext = pNew;
3633 pNew->pNext = p;
3634 p->pPrior = pNew;
3635 SELECTTRACE(2,pParse,p,
3636 ("compound-subquery flattener creates %s.%p as peer\n",
3637 pNew->zSelName, pNew));
3638 }
3639 if( db->mallocFailed ) return 1;
3640 }
3641
3642 /* Begin flattening the iFrom-th entry of the FROM clause
3643 ** in the outer query.
3644 */
3645 pSub = pSub1 = pSubitem->pSelect;
3646
3647 /* Delete the transient table structure associated with the
3648 ** subquery
3649 */
3650 sqlite3DbFree(db, pSubitem->zDatabase);
3651 sqlite3DbFree(db, pSubitem->zName);
3652 sqlite3DbFree(db, pSubitem->zAlias);
3653 pSubitem->zDatabase = 0;
3654 pSubitem->zName = 0;
3655 pSubitem->zAlias = 0;
3656 pSubitem->pSelect = 0;
3657
3658 /* Defer deleting the Table object associated with the
3659 ** subquery until code generation is
3660 ** complete, since there may still exist Expr.pTab entries that
3661 ** refer to the subquery even after flattening. Ticket #3346.
3662 **
3663 ** pSubitem->pTab is always non-NULL by test restrictions and tests above.
3664 */
3665 if( ALWAYS(pSubitem->pTab!=0) ){
3666 Table *pTabToDel = pSubitem->pTab;
3667 if( pTabToDel->nTabRef==1 ){
3668 Parse *pToplevel = sqlite3ParseToplevel(pParse);
3669 pTabToDel->pNextZombie = pToplevel->pZombieTab;
3670 pToplevel->pZombieTab = pTabToDel;
3671 }else{
3672 pTabToDel->nTabRef--;
3673 }
3674 pSubitem->pTab = 0;
3675 }
3676
3677 /* The following loop runs once for each term in a compound-subquery
3678 ** flattening (as described above). If we are doing a different kind
3679 ** of flattening - a flattening other than a compound-subquery flattening -
3680 ** then this loop only runs once.
3681 **
3682 ** This loop moves all of the FROM elements of the subquery into the
3683 ** the FROM clause of the outer query. Before doing this, remember
3684 ** the cursor number for the original outer query FROM element in
3685 ** iParent. The iParent cursor will never be used. Subsequent code
3686 ** will scan expressions looking for iParent references and replace
3687 ** those references with expressions that resolve to the subquery FROM
3688 ** elements we are now copying in.
3689 */
3690 for(pParent=p; pParent; pParent=pParent->pPrior, pSub=pSub->pPrior){
3691 int nSubSrc;
3692 u8 jointype = 0;
3693 pSubSrc = pSub->pSrc; /* FROM clause of subquery */
3694 nSubSrc = pSubSrc->nSrc; /* Number of terms in subquery FROM clause */
3695 pSrc = pParent->pSrc; /* FROM clause of the outer query */
3696
3697 if( pSrc ){
3698 assert( pParent==p ); /* First time through the loop */
3699 jointype = pSubitem->fg.jointype;
3700 }else{
3701 assert( pParent!=p ); /* 2nd and subsequent times through the loop */
3702 pSrc = pParent->pSrc = sqlite3SrcListAppend(db, 0, 0, 0);
3703 if( pSrc==0 ){
3704 assert( db->mallocFailed );
3705 break;
3706 }
3707 }
3708
3709 /* The subquery uses a single slot of the FROM clause of the outer
3710 ** query. If the subquery has more than one element in its FROM clause,
3711 ** then expand the outer query to make space for it to hold all elements
3712 ** of the subquery.
3713 **
3714 ** Example:
3715 **
3716 ** SELECT * FROM tabA, (SELECT * FROM sub1, sub2), tabB;
3717 **
3718 ** The outer query has 3 slots in its FROM clause. One slot of the
3719 ** outer query (the middle slot) is used by the subquery. The next
3720 ** block of code will expand the outer query FROM clause to 4 slots.
3721 ** The middle slot is expanded to two slots in order to make space
3722 ** for the two elements in the FROM clause of the subquery.
3723 */
3724 if( nSubSrc>1 ){
3725 pParent->pSrc = pSrc = sqlite3SrcListEnlarge(db, pSrc, nSubSrc-1,iFrom+1);
3726 if( db->mallocFailed ){
3727 break;
3728 }
3729 }
3730
3731 /* Transfer the FROM clause terms from the subquery into the
3732 ** outer query.
3733 */
3734 for(i=0; i<nSubSrc; i++){
3735 sqlite3IdListDelete(db, pSrc->a[i+iFrom].pUsing);
3736 assert( pSrc->a[i+iFrom].fg.isTabFunc==0 );
3737 pSrc->a[i+iFrom] = pSubSrc->a[i];
3738 iNewParent = pSubSrc->a[i].iCursor;
3739 memset(&pSubSrc->a[i], 0, sizeof(pSubSrc->a[i]));
3740 }
3741 pSrc->a[iFrom].fg.jointype = jointype;
3742
3743 /* Now begin substituting subquery result set expressions for
3744 ** references to the iParent in the outer query.
3745 **
3746 ** Example:
3747 **
3748 ** SELECT a+5, b*10 FROM (SELECT x*3 AS a, y+10 AS b FROM t1) WHERE a>b;
3749 ** \ \_____________ subquery __________/ /
3750 ** \_____________________ outer query ______________________________/
3751 **
3752 ** We look at every expression in the outer query and every place we see
3753 ** "a" we substitute "x*3" and every place we see "b" we substitute "y+10".
3754 */
3755 if( pSub->pOrderBy ){
3756 /* At this point, any non-zero iOrderByCol values indicate that the
3757 ** ORDER BY column expression is identical to the iOrderByCol'th
3758 ** expression returned by SELECT statement pSub. Since these values
3759 ** do not necessarily correspond to columns in SELECT statement pParent,
3760 ** zero them before transfering the ORDER BY clause.
3761 **
3762 ** Not doing this may cause an error if a subsequent call to this
3763 ** function attempts to flatten a compound sub-query into pParent
3764 ** (the only way this can happen is if the compound sub-query is
3765 ** currently part of pSub->pSrc). See ticket [d11a6e908f]. */
3766 ExprList *pOrderBy = pSub->pOrderBy;
3767 for(i=0; i<pOrderBy->nExpr; i++){
3768 pOrderBy->a[i].u.x.iOrderByCol = 0;
3769 }
3770 assert( pParent->pOrderBy==0 );
3771 assert( pSub->pPrior==0 );
3772 pParent->pOrderBy = pOrderBy;
3773 pSub->pOrderBy = 0;
3774 }
3775 pWhere = sqlite3ExprDup(db, pSub->pWhere, 0);
3776 if( isLeftJoin>0 ){
3777 setJoinExpr(pWhere, iNewParent);
3778 }
3779 if( subqueryIsAgg ){
3780 assert( pParent->pHaving==0 );
3781 pParent->pHaving = pParent->pWhere;
3782 pParent->pWhere = pWhere;
3783 pParent->pHaving = sqlite3ExprAnd(db,
3784 sqlite3ExprDup(db, pSub->pHaving, 0), pParent->pHaving
3785 );
3786 assert( pParent->pGroupBy==0 );
3787 pParent->pGroupBy = sqlite3ExprListDup(db, pSub->pGroupBy, 0);
3788 }else{
3789 pParent->pWhere = sqlite3ExprAnd(db, pWhere, pParent->pWhere);
3790 }
3791 if( db->mallocFailed==0 ){
3792 SubstContext x;
3793 x.pParse = pParse;
3794 x.iTable = iParent;
3795 x.iNewTable = iNewParent;
3796 x.isLeftJoin = isLeftJoin;
3797 x.pEList = pSub->pEList;
3798 substSelect(&x, pParent, 0);
3799 }
3800
3801 /* The flattened query is distinct if either the inner or the
3802 ** outer query is distinct.
3803 */
3804 pParent->selFlags |= pSub->selFlags & SF_Distinct;
3805
3806 /*
3807 ** SELECT ... FROM (SELECT ... LIMIT a OFFSET b) LIMIT x OFFSET y;
3808 **
3809 ** One is tempted to try to add a and b to combine the limits. But this
3810 ** does not work if either limit is negative.
3811 */
3812 if( pSub->pLimit ){
3813 pParent->pLimit = pSub->pLimit;
3814 pSub->pLimit = 0;
3815 }
3816 }
3817
3818 /* Finially, delete what is left of the subquery and return
3819 ** success.
3820 */
3821 sqlite3SelectDelete(db, pSub1);
3822
3823 #if SELECTTRACE_ENABLED
3824 if( sqlite3SelectTrace & 0x100 ){
3825 SELECTTRACE(0x100,pParse,p,("After flattening:\n"));
3826 sqlite3TreeViewSelect(0, p, 0);
3827 }
3828 #endif
3829
3830 return 1;
3831 }
3832 #endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */
3833
3834
3835
3836 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3837 /*
3838 ** Make copies of relevant WHERE clause terms of the outer query into
3839 ** the WHERE clause of subquery. Example:
3840 **
3841 ** SELECT * FROM (SELECT a AS x, c-d AS y FROM t1) WHERE x=5 AND y=10;
3842 **
3843 ** Transformed into:
3844 **
3845 ** SELECT * FROM (SELECT a AS x, c-d AS y FROM t1 WHERE a=5 AND c-d=10)
3846 ** WHERE x=5 AND y=10;
3847 **
3848 ** The hope is that the terms added to the inner query will make it more
3849 ** efficient.
3850 **
3851 ** Do not attempt this optimization if:
3852 **
3853 ** (1) The inner query is an aggregate. (In that case, we'd really want
3854 ** to copy the outer WHERE-clause terms onto the HAVING clause of the
3855 ** inner query. But they probably won't help there so do not bother.)
3856 **
3857 ** (2) The inner query is the recursive part of a common table expression.
3858 **
3859 ** (3) The inner query has a LIMIT clause (since the changes to the WHERE
3860 ** close would change the meaning of the LIMIT).
3861 **
3862 ** (4) The inner query is the right operand of a LEFT JOIN. (The caller
3863 ** enforces this restriction since this routine does not have enough
3864 ** information to know.)
3865 **
3866 ** (5) The WHERE clause expression originates in the ON or USING clause
3867 ** of a LEFT JOIN.
3868 **
3869 ** Return 0 if no changes are made and non-zero if one or more WHERE clause
3870 ** terms are duplicated into the subquery.
3871 */
pushDownWhereTerms(Parse * pParse,Select * pSubq,Expr * pWhere,int iCursor)3872 static int pushDownWhereTerms(
3873 Parse *pParse, /* Parse context (for malloc() and error reporting) */
3874 Select *pSubq, /* The subquery whose WHERE clause is to be augmented */
3875 Expr *pWhere, /* The WHERE clause of the outer query */
3876 int iCursor /* Cursor number of the subquery */
3877 ){
3878 Expr *pNew;
3879 int nChng = 0;
3880 Select *pX; /* For looping over compound SELECTs in pSubq */
3881 if( pWhere==0 ) return 0;
3882 for(pX=pSubq; pX; pX=pX->pPrior){
3883 if( (pX->selFlags & (SF_Aggregate|SF_Recursive))!=0 ){
3884 testcase( pX->selFlags & SF_Aggregate );
3885 testcase( pX->selFlags & SF_Recursive );
3886 testcase( pX!=pSubq );
3887 return 0; /* restrictions (1) and (2) */
3888 }
3889 }
3890 if( pSubq->pLimit!=0 ){
3891 return 0; /* restriction (3) */
3892 }
3893 while( pWhere->op==TK_AND ){
3894 nChng += pushDownWhereTerms(pParse, pSubq, pWhere->pRight, iCursor);
3895 pWhere = pWhere->pLeft;
3896 }
3897 if( ExprHasProperty(pWhere,EP_FromJoin) ) return 0; /* restriction 5 */
3898 if( sqlite3ExprIsTableConstant(pWhere, iCursor) ){
3899 nChng++;
3900 while( pSubq ){
3901 SubstContext x;
3902 pNew = sqlite3ExprDup(pParse->db, pWhere, 0);
3903 x.pParse = pParse;
3904 x.iTable = iCursor;
3905 x.iNewTable = iCursor;
3906 x.isLeftJoin = 0;
3907 x.pEList = pSubq->pEList;
3908 pNew = substExpr(&x, pNew);
3909 pSubq->pWhere = sqlite3ExprAnd(pParse->db, pSubq->pWhere, pNew);
3910 pSubq = pSubq->pPrior;
3911 }
3912 }
3913 return nChng;
3914 }
3915 #endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */
3916
3917 /*
3918 ** Based on the contents of the AggInfo structure indicated by the first
3919 ** argument, this function checks if the following are true:
3920 **
3921 ** * the query contains just a single aggregate function,
3922 ** * the aggregate function is either min() or max(), and
3923 ** * the argument to the aggregate function is a column value.
3924 **
3925 ** If all of the above are true, then WHERE_ORDERBY_MIN or WHERE_ORDERBY_MAX
3926 ** is returned as appropriate. Also, *ppMinMax is set to point to the
3927 ** list of arguments passed to the aggregate before returning.
3928 **
3929 ** Or, if the conditions above are not met, *ppMinMax is set to 0 and
3930 ** WHERE_ORDERBY_NORMAL is returned.
3931 */
minMaxQuery(AggInfo * pAggInfo,ExprList ** ppMinMax)3932 static u8 minMaxQuery(AggInfo *pAggInfo, ExprList **ppMinMax){
3933 int eRet = WHERE_ORDERBY_NORMAL; /* Return value */
3934
3935 *ppMinMax = 0;
3936 if( pAggInfo->nFunc==1 ){
3937 Expr *pExpr = pAggInfo->aFunc[0].pExpr; /* Aggregate function */
3938 ExprList *pEList = pExpr->x.pList; /* Arguments to agg function */
3939
3940 assert( pExpr->op==TK_AGG_FUNCTION );
3941 if( pEList && pEList->nExpr==1 && pEList->a[0].pExpr->op==TK_AGG_COLUMN ){
3942 const char *zFunc = pExpr->u.zToken;
3943 if( sqlite3StrICmp(zFunc, "min")==0 ){
3944 eRet = WHERE_ORDERBY_MIN;
3945 *ppMinMax = pEList;
3946 }else if( sqlite3StrICmp(zFunc, "max")==0 ){
3947 eRet = WHERE_ORDERBY_MAX;
3948 *ppMinMax = pEList;
3949 }
3950 }
3951 }
3952
3953 assert( *ppMinMax==0 || (*ppMinMax)->nExpr==1 );
3954 return eRet;
3955 }
3956
3957 /*
3958 ** The select statement passed as the first argument is an aggregate query.
3959 ** The second argument is the associated aggregate-info object. This
3960 ** function tests if the SELECT is of the form:
3961 **
3962 ** SELECT count(*) FROM <tbl>
3963 **
3964 ** where table is a database table, not a sub-select or view. If the query
3965 ** does match this pattern, then a pointer to the Table object representing
3966 ** <tbl> is returned. Otherwise, 0 is returned.
3967 */
isSimpleCount(Select * p,AggInfo * pAggInfo)3968 static Table *isSimpleCount(Select *p, AggInfo *pAggInfo){
3969 Table *pTab;
3970 Expr *pExpr;
3971
3972 assert( !p->pGroupBy );
3973
3974 if( p->pWhere || p->pEList->nExpr!=1
3975 || p->pSrc->nSrc!=1 || p->pSrc->a[0].pSelect
3976 ){
3977 return 0;
3978 }
3979 pTab = p->pSrc->a[0].pTab;
3980 pExpr = p->pEList->a[0].pExpr;
3981 assert( pTab && !pTab->pSelect && pExpr );
3982
3983 if( IsVirtual(pTab) ) return 0;
3984 if( pExpr->op!=TK_AGG_FUNCTION ) return 0;
3985 if( NEVER(pAggInfo->nFunc==0) ) return 0;
3986 if( (pAggInfo->aFunc[0].pFunc->funcFlags&SQLITE_FUNC_COUNT)==0 ) return 0;
3987 if( pExpr->flags&EP_Distinct ) return 0;
3988
3989 return pTab;
3990 }
3991
3992 /*
3993 ** If the source-list item passed as an argument was augmented with an
3994 ** INDEXED BY clause, then try to locate the specified index. If there
3995 ** was such a clause and the named index cannot be found, return
3996 ** SQLITE_ERROR and leave an error in pParse. Otherwise, populate
3997 ** pFrom->pIndex and return SQLITE_OK.
3998 */
sqlite3IndexedByLookup(Parse * pParse,struct SrcList_item * pFrom)3999 int sqlite3IndexedByLookup(Parse *pParse, struct SrcList_item *pFrom){
4000 if( pFrom->pTab && pFrom->fg.isIndexedBy ){
4001 Table *pTab = pFrom->pTab;
4002 char *zIndexedBy = pFrom->u1.zIndexedBy;
4003 Index *pIdx;
4004 for(pIdx=pTab->pIndex;
4005 pIdx && sqlite3StrICmp(pIdx->zName, zIndexedBy);
4006 pIdx=pIdx->pNext
4007 );
4008 if( !pIdx ){
4009 sqlite3ErrorMsg(pParse, "no such index: %s", zIndexedBy, 0);
4010 pParse->checkSchema = 1;
4011 return SQLITE_ERROR;
4012 }
4013 pFrom->pIBIndex = pIdx;
4014 }
4015 return SQLITE_OK;
4016 }
4017 /*
4018 ** Detect compound SELECT statements that use an ORDER BY clause with
4019 ** an alternative collating sequence.
4020 **
4021 ** SELECT ... FROM t1 EXCEPT SELECT ... FROM t2 ORDER BY .. COLLATE ...
4022 **
4023 ** These are rewritten as a subquery:
4024 **
4025 ** SELECT * FROM (SELECT ... FROM t1 EXCEPT SELECT ... FROM t2)
4026 ** ORDER BY ... COLLATE ...
4027 **
4028 ** This transformation is necessary because the multiSelectOrderBy() routine
4029 ** above that generates the code for a compound SELECT with an ORDER BY clause
4030 ** uses a merge algorithm that requires the same collating sequence on the
4031 ** result columns as on the ORDER BY clause. See ticket
4032 ** http://www.sqlite.org/src/info/6709574d2a
4033 **
4034 ** This transformation is only needed for EXCEPT, INTERSECT, and UNION.
4035 ** The UNION ALL operator works fine with multiSelectOrderBy() even when
4036 ** there are COLLATE terms in the ORDER BY.
4037 */
convertCompoundSelectToSubquery(Walker * pWalker,Select * p)4038 static int convertCompoundSelectToSubquery(Walker *pWalker, Select *p){
4039 int i;
4040 Select *pNew;
4041 Select *pX;
4042 sqlite3 *db;
4043 struct ExprList_item *a;
4044 SrcList *pNewSrc;
4045 Parse *pParse;
4046 Token dummy;
4047
4048 if( p->pPrior==0 ) return WRC_Continue;
4049 if( p->pOrderBy==0 ) return WRC_Continue;
4050 for(pX=p; pX && (pX->op==TK_ALL || pX->op==TK_SELECT); pX=pX->pPrior){}
4051 if( pX==0 ) return WRC_Continue;
4052 a = p->pOrderBy->a;
4053 for(i=p->pOrderBy->nExpr-1; i>=0; i--){
4054 if( a[i].pExpr->flags & EP_Collate ) break;
4055 }
4056 if( i<0 ) return WRC_Continue;
4057
4058 /* If we reach this point, that means the transformation is required. */
4059
4060 pParse = pWalker->pParse;
4061 db = pParse->db;
4062 pNew = sqlite3DbMallocZero(db, sizeof(*pNew) );
4063 if( pNew==0 ) return WRC_Abort;
4064 memset(&dummy, 0, sizeof(dummy));
4065 pNewSrc = sqlite3SrcListAppendFromTerm(pParse,0,0,0,&dummy,pNew,0,0);
4066 if( pNewSrc==0 ) return WRC_Abort;
4067 *pNew = *p;
4068 p->pSrc = pNewSrc;
4069 p->pEList = sqlite3ExprListAppend(pParse, 0, sqlite3Expr(db, TK_ASTERISK, 0));
4070 p->op = TK_SELECT;
4071 p->pWhere = 0;
4072 pNew->pGroupBy = 0;
4073 pNew->pHaving = 0;
4074 pNew->pOrderBy = 0;
4075 p->pPrior = 0;
4076 p->pNext = 0;
4077 p->pWith = 0;
4078 p->selFlags &= ~SF_Compound;
4079 assert( (p->selFlags & SF_Converted)==0 );
4080 p->selFlags |= SF_Converted;
4081 assert( pNew->pPrior!=0 );
4082 pNew->pPrior->pNext = pNew;
4083 pNew->pLimit = 0;
4084 pNew->pOffset = 0;
4085 return WRC_Continue;
4086 }
4087
4088 /*
4089 ** Check to see if the FROM clause term pFrom has table-valued function
4090 ** arguments. If it does, leave an error message in pParse and return
4091 ** non-zero, since pFrom is not allowed to be a table-valued function.
4092 */
cannotBeFunction(Parse * pParse,struct SrcList_item * pFrom)4093 static int cannotBeFunction(Parse *pParse, struct SrcList_item *pFrom){
4094 if( pFrom->fg.isTabFunc ){
4095 sqlite3ErrorMsg(pParse, "'%s' is not a function", pFrom->zName);
4096 return 1;
4097 }
4098 return 0;
4099 }
4100
4101 #ifndef SQLITE_OMIT_CTE
4102 /*
4103 ** Argument pWith (which may be NULL) points to a linked list of nested
4104 ** WITH contexts, from inner to outermost. If the table identified by
4105 ** FROM clause element pItem is really a common-table-expression (CTE)
4106 ** then return a pointer to the CTE definition for that table. Otherwise
4107 ** return NULL.
4108 **
4109 ** If a non-NULL value is returned, set *ppContext to point to the With
4110 ** object that the returned CTE belongs to.
4111 */
searchWith(With * pWith,struct SrcList_item * pItem,With ** ppContext)4112 static struct Cte *searchWith(
4113 With *pWith, /* Current innermost WITH clause */
4114 struct SrcList_item *pItem, /* FROM clause element to resolve */
4115 With **ppContext /* OUT: WITH clause return value belongs to */
4116 ){
4117 const char *zName;
4118 if( pItem->zDatabase==0 && (zName = pItem->zName)!=0 ){
4119 With *p;
4120 for(p=pWith; p; p=p->pOuter){
4121 int i;
4122 for(i=0; i<p->nCte; i++){
4123 if( sqlite3StrICmp(zName, p->a[i].zName)==0 ){
4124 *ppContext = p;
4125 return &p->a[i];
4126 }
4127 }
4128 }
4129 }
4130 return 0;
4131 }
4132
4133 /* The code generator maintains a stack of active WITH clauses
4134 ** with the inner-most WITH clause being at the top of the stack.
4135 **
4136 ** This routine pushes the WITH clause passed as the second argument
4137 ** onto the top of the stack. If argument bFree is true, then this
4138 ** WITH clause will never be popped from the stack. In this case it
4139 ** should be freed along with the Parse object. In other cases, when
4140 ** bFree==0, the With object will be freed along with the SELECT
4141 ** statement with which it is associated.
4142 */
sqlite3WithPush(Parse * pParse,With * pWith,u8 bFree)4143 void sqlite3WithPush(Parse *pParse, With *pWith, u8 bFree){
4144 assert( bFree==0 || (pParse->pWith==0 && pParse->pWithToFree==0) );
4145 if( pWith ){
4146 assert( pParse->pWith!=pWith );
4147 pWith->pOuter = pParse->pWith;
4148 pParse->pWith = pWith;
4149 if( bFree ) pParse->pWithToFree = pWith;
4150 }
4151 }
4152
4153 /*
4154 ** This function checks if argument pFrom refers to a CTE declared by
4155 ** a WITH clause on the stack currently maintained by the parser. And,
4156 ** if currently processing a CTE expression, if it is a recursive
4157 ** reference to the current CTE.
4158 **
4159 ** If pFrom falls into either of the two categories above, pFrom->pTab
4160 ** and other fields are populated accordingly. The caller should check
4161 ** (pFrom->pTab!=0) to determine whether or not a successful match
4162 ** was found.
4163 **
4164 ** Whether or not a match is found, SQLITE_OK is returned if no error
4165 ** occurs. If an error does occur, an error message is stored in the
4166 ** parser and some error code other than SQLITE_OK returned.
4167 */
withExpand(Walker * pWalker,struct SrcList_item * pFrom)4168 static int withExpand(
4169 Walker *pWalker,
4170 struct SrcList_item *pFrom
4171 ){
4172 Parse *pParse = pWalker->pParse;
4173 sqlite3 *db = pParse->db;
4174 struct Cte *pCte; /* Matched CTE (or NULL if no match) */
4175 With *pWith; /* WITH clause that pCte belongs to */
4176
4177 assert( pFrom->pTab==0 );
4178
4179 pCte = searchWith(pParse->pWith, pFrom, &pWith);
4180 if( pCte ){
4181 Table *pTab;
4182 ExprList *pEList;
4183 Select *pSel;
4184 Select *pLeft; /* Left-most SELECT statement */
4185 int bMayRecursive; /* True if compound joined by UNION [ALL] */
4186 With *pSavedWith; /* Initial value of pParse->pWith */
4187
4188 /* If pCte->zCteErr is non-NULL at this point, then this is an illegal
4189 ** recursive reference to CTE pCte. Leave an error in pParse and return
4190 ** early. If pCte->zCteErr is NULL, then this is not a recursive reference.
4191 ** In this case, proceed. */
4192 if( pCte->zCteErr ){
4193 sqlite3ErrorMsg(pParse, pCte->zCteErr, pCte->zName);
4194 return SQLITE_ERROR;
4195 }
4196 if( cannotBeFunction(pParse, pFrom) ) return SQLITE_ERROR;
4197
4198 assert( pFrom->pTab==0 );
4199 pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table));
4200 if( pTab==0 ) return WRC_Abort;
4201 pTab->nTabRef = 1;
4202 pTab->zName = sqlite3DbStrDup(db, pCte->zName);
4203 pTab->iPKey = -1;
4204 pTab->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) );
4205 pTab->tabFlags |= TF_Ephemeral | TF_NoVisibleRowid;
4206 pFrom->pSelect = sqlite3SelectDup(db, pCte->pSelect, 0);
4207 if( db->mallocFailed ) return SQLITE_NOMEM_BKPT;
4208 assert( pFrom->pSelect );
4209
4210 /* Check if this is a recursive CTE. */
4211 pSel = pFrom->pSelect;
4212 bMayRecursive = ( pSel->op==TK_ALL || pSel->op==TK_UNION );
4213 if( bMayRecursive ){
4214 int i;
4215 SrcList *pSrc = pFrom->pSelect->pSrc;
4216 for(i=0; i<pSrc->nSrc; i++){
4217 struct SrcList_item *pItem = &pSrc->a[i];
4218 if( pItem->zDatabase==0
4219 && pItem->zName!=0
4220 && 0==sqlite3StrICmp(pItem->zName, pCte->zName)
4221 ){
4222 pItem->pTab = pTab;
4223 pItem->fg.isRecursive = 1;
4224 pTab->nTabRef++;
4225 pSel->selFlags |= SF_Recursive;
4226 }
4227 }
4228 }
4229
4230 /* Only one recursive reference is permitted. */
4231 if( pTab->nTabRef>2 ){
4232 sqlite3ErrorMsg(
4233 pParse, "multiple references to recursive table: %s", pCte->zName
4234 );
4235 return SQLITE_ERROR;
4236 }
4237 assert( pTab->nTabRef==1 || ((pSel->selFlags&SF_Recursive) && pTab->nTabRef==2 ));
4238
4239 pCte->zCteErr = "circular reference: %s";
4240 pSavedWith = pParse->pWith;
4241 pParse->pWith = pWith;
4242 if( bMayRecursive ){
4243 Select *pPrior = pSel->pPrior;
4244 assert( pPrior->pWith==0 );
4245 pPrior->pWith = pSel->pWith;
4246 sqlite3WalkSelect(pWalker, pPrior);
4247 pPrior->pWith = 0;
4248 }else{
4249 sqlite3WalkSelect(pWalker, pSel);
4250 }
4251 pParse->pWith = pWith;
4252
4253 for(pLeft=pSel; pLeft->pPrior; pLeft=pLeft->pPrior);
4254 pEList = pLeft->pEList;
4255 if( pCte->pCols ){
4256 if( pEList && pEList->nExpr!=pCte->pCols->nExpr ){
4257 sqlite3ErrorMsg(pParse, "table %s has %d values for %d columns",
4258 pCte->zName, pEList->nExpr, pCte->pCols->nExpr
4259 );
4260 pParse->pWith = pSavedWith;
4261 return SQLITE_ERROR;
4262 }
4263 pEList = pCte->pCols;
4264 }
4265
4266 sqlite3ColumnsFromExprList(pParse, pEList, &pTab->nCol, &pTab->aCol);
4267 if( bMayRecursive ){
4268 if( pSel->selFlags & SF_Recursive ){
4269 pCte->zCteErr = "multiple recursive references: %s";
4270 }else{
4271 pCte->zCteErr = "recursive reference in a subquery: %s";
4272 }
4273 sqlite3WalkSelect(pWalker, pSel);
4274 }
4275 pCte->zCteErr = 0;
4276 pParse->pWith = pSavedWith;
4277 }
4278
4279 return SQLITE_OK;
4280 }
4281 #endif
4282
4283 #ifndef SQLITE_OMIT_CTE
4284 /*
4285 ** If the SELECT passed as the second argument has an associated WITH
4286 ** clause, pop it from the stack stored as part of the Parse object.
4287 **
4288 ** This function is used as the xSelectCallback2() callback by
4289 ** sqlite3SelectExpand() when walking a SELECT tree to resolve table
4290 ** names and other FROM clause elements.
4291 */
selectPopWith(Walker * pWalker,Select * p)4292 static void selectPopWith(Walker *pWalker, Select *p){
4293 Parse *pParse = pWalker->pParse;
4294 if( pParse->pWith && p->pPrior==0 ){
4295 With *pWith = findRightmost(p)->pWith;
4296 if( pWith!=0 ){
4297 assert( pParse->pWith==pWith );
4298 pParse->pWith = pWith->pOuter;
4299 }
4300 }
4301 }
4302 #else
4303 #define selectPopWith 0
4304 #endif
4305
4306 /*
4307 ** This routine is a Walker callback for "expanding" a SELECT statement.
4308 ** "Expanding" means to do the following:
4309 **
4310 ** (1) Make sure VDBE cursor numbers have been assigned to every
4311 ** element of the FROM clause.
4312 **
4313 ** (2) Fill in the pTabList->a[].pTab fields in the SrcList that
4314 ** defines FROM clause. When views appear in the FROM clause,
4315 ** fill pTabList->a[].pSelect with a copy of the SELECT statement
4316 ** that implements the view. A copy is made of the view's SELECT
4317 ** statement so that we can freely modify or delete that statement
4318 ** without worrying about messing up the persistent representation
4319 ** of the view.
4320 **
4321 ** (3) Add terms to the WHERE clause to accommodate the NATURAL keyword
4322 ** on joins and the ON and USING clause of joins.
4323 **
4324 ** (4) Scan the list of columns in the result set (pEList) looking
4325 ** for instances of the "*" operator or the TABLE.* operator.
4326 ** If found, expand each "*" to be every column in every table
4327 ** and TABLE.* to be every column in TABLE.
4328 **
4329 */
selectExpander(Walker * pWalker,Select * p)4330 static int selectExpander(Walker *pWalker, Select *p){
4331 Parse *pParse = pWalker->pParse;
4332 int i, j, k;
4333 SrcList *pTabList;
4334 ExprList *pEList;
4335 struct SrcList_item *pFrom;
4336 sqlite3 *db = pParse->db;
4337 Expr *pE, *pRight, *pExpr;
4338 u16 selFlags = p->selFlags;
4339
4340 p->selFlags |= SF_Expanded;
4341 if( db->mallocFailed ){
4342 return WRC_Abort;
4343 }
4344 if( NEVER(p->pSrc==0) || (selFlags & SF_Expanded)!=0 ){
4345 return WRC_Prune;
4346 }
4347 pTabList = p->pSrc;
4348 pEList = p->pEList;
4349 if( p->pWith ){
4350 sqlite3WithPush(pParse, p->pWith, 0);
4351 }
4352
4353 /* Make sure cursor numbers have been assigned to all entries in
4354 ** the FROM clause of the SELECT statement.
4355 */
4356 sqlite3SrcListAssignCursors(pParse, pTabList);
4357
4358 /* Look up every table named in the FROM clause of the select. If
4359 ** an entry of the FROM clause is a subquery instead of a table or view,
4360 ** then create a transient table structure to describe the subquery.
4361 */
4362 for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){
4363 Table *pTab;
4364 assert( pFrom->fg.isRecursive==0 || pFrom->pTab!=0 );
4365 if( pFrom->fg.isRecursive ) continue;
4366 assert( pFrom->pTab==0 );
4367 #ifndef SQLITE_OMIT_CTE
4368 if( withExpand(pWalker, pFrom) ) return WRC_Abort;
4369 if( pFrom->pTab ) {} else
4370 #endif
4371 if( pFrom->zName==0 ){
4372 #ifndef SQLITE_OMIT_SUBQUERY
4373 Select *pSel = pFrom->pSelect;
4374 /* A sub-query in the FROM clause of a SELECT */
4375 assert( pSel!=0 );
4376 assert( pFrom->pTab==0 );
4377 if( sqlite3WalkSelect(pWalker, pSel) ) return WRC_Abort;
4378 pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table));
4379 if( pTab==0 ) return WRC_Abort;
4380 pTab->nTabRef = 1;
4381 pTab->zName = sqlite3MPrintf(db, "sqlite_sq_%p", (void*)pTab);
4382 while( pSel->pPrior ){ pSel = pSel->pPrior; }
4383 sqlite3ColumnsFromExprList(pParse, pSel->pEList,&pTab->nCol,&pTab->aCol);
4384 pTab->iPKey = -1;
4385 pTab->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) );
4386 pTab->tabFlags |= TF_Ephemeral;
4387 #endif
4388 }else{
4389 /* An ordinary table or view name in the FROM clause */
4390 assert( pFrom->pTab==0 );
4391 pFrom->pTab = pTab = sqlite3LocateTableItem(pParse, 0, pFrom);
4392 if( pTab==0 ) return WRC_Abort;
4393 if( pTab->nTabRef>=0xffff ){
4394 sqlite3ErrorMsg(pParse, "too many references to \"%s\": max 65535",
4395 pTab->zName);
4396 pFrom->pTab = 0;
4397 return WRC_Abort;
4398 }
4399 pTab->nTabRef++;
4400 if( !IsVirtual(pTab) && cannotBeFunction(pParse, pFrom) ){
4401 return WRC_Abort;
4402 }
4403 #if !defined(SQLITE_OMIT_VIEW) || !defined (SQLITE_OMIT_VIRTUALTABLE)
4404 if( IsVirtual(pTab) || pTab->pSelect ){
4405 i16 nCol;
4406 if( sqlite3ViewGetColumnNames(pParse, pTab) ) return WRC_Abort;
4407 assert( pFrom->pSelect==0 );
4408 pFrom->pSelect = sqlite3SelectDup(db, pTab->pSelect, 0);
4409 sqlite3SelectSetName(pFrom->pSelect, pTab->zName);
4410 nCol = pTab->nCol;
4411 pTab->nCol = -1;
4412 sqlite3WalkSelect(pWalker, pFrom->pSelect);
4413 pTab->nCol = nCol;
4414 }
4415 #endif
4416 }
4417
4418 /* Locate the index named by the INDEXED BY clause, if any. */
4419 if( sqlite3IndexedByLookup(pParse, pFrom) ){
4420 return WRC_Abort;
4421 }
4422 }
4423
4424 /* Process NATURAL keywords, and ON and USING clauses of joins.
4425 */
4426 if( db->mallocFailed || sqliteProcessJoin(pParse, p) ){
4427 return WRC_Abort;
4428 }
4429
4430 /* For every "*" that occurs in the column list, insert the names of
4431 ** all columns in all tables. And for every TABLE.* insert the names
4432 ** of all columns in TABLE. The parser inserted a special expression
4433 ** with the TK_ASTERISK operator for each "*" that it found in the column
4434 ** list. The following code just has to locate the TK_ASTERISK
4435 ** expressions and expand each one to the list of all columns in
4436 ** all tables.
4437 **
4438 ** The first loop just checks to see if there are any "*" operators
4439 ** that need expanding.
4440 */
4441 for(k=0; k<pEList->nExpr; k++){
4442 pE = pEList->a[k].pExpr;
4443 if( pE->op==TK_ASTERISK ) break;
4444 assert( pE->op!=TK_DOT || pE->pRight!=0 );
4445 assert( pE->op!=TK_DOT || (pE->pLeft!=0 && pE->pLeft->op==TK_ID) );
4446 if( pE->op==TK_DOT && pE->pRight->op==TK_ASTERISK ) break;
4447 }
4448 if( k<pEList->nExpr ){
4449 /*
4450 ** If we get here it means the result set contains one or more "*"
4451 ** operators that need to be expanded. Loop through each expression
4452 ** in the result set and expand them one by one.
4453 */
4454 struct ExprList_item *a = pEList->a;
4455 ExprList *pNew = 0;
4456 int flags = pParse->db->flags;
4457 int longNames = (flags & SQLITE_FullColNames)!=0
4458 && (flags & SQLITE_ShortColNames)==0;
4459
4460 for(k=0; k<pEList->nExpr; k++){
4461 pE = a[k].pExpr;
4462 pRight = pE->pRight;
4463 assert( pE->op!=TK_DOT || pRight!=0 );
4464 if( pE->op!=TK_ASTERISK
4465 && (pE->op!=TK_DOT || pRight->op!=TK_ASTERISK)
4466 ){
4467 /* This particular expression does not need to be expanded.
4468 */
4469 pNew = sqlite3ExprListAppend(pParse, pNew, a[k].pExpr);
4470 if( pNew ){
4471 pNew->a[pNew->nExpr-1].zName = a[k].zName;
4472 pNew->a[pNew->nExpr-1].zSpan = a[k].zSpan;
4473 a[k].zName = 0;
4474 a[k].zSpan = 0;
4475 }
4476 a[k].pExpr = 0;
4477 }else{
4478 /* This expression is a "*" or a "TABLE.*" and needs to be
4479 ** expanded. */
4480 int tableSeen = 0; /* Set to 1 when TABLE matches */
4481 char *zTName = 0; /* text of name of TABLE */
4482 if( pE->op==TK_DOT ){
4483 assert( pE->pLeft!=0 );
4484 assert( !ExprHasProperty(pE->pLeft, EP_IntValue) );
4485 zTName = pE->pLeft->u.zToken;
4486 }
4487 for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){
4488 Table *pTab = pFrom->pTab;
4489 Select *pSub = pFrom->pSelect;
4490 char *zTabName = pFrom->zAlias;
4491 const char *zSchemaName = 0;
4492 int iDb;
4493 if( zTabName==0 ){
4494 zTabName = pTab->zName;
4495 }
4496 if( db->mallocFailed ) break;
4497 if( pSub==0 || (pSub->selFlags & SF_NestedFrom)==0 ){
4498 pSub = 0;
4499 if( zTName && sqlite3StrICmp(zTName, zTabName)!=0 ){
4500 continue;
4501 }
4502 iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
4503 zSchemaName = iDb>=0 ? db->aDb[iDb].zDbSName : "*";
4504 }
4505 for(j=0; j<pTab->nCol; j++){
4506 char *zName = pTab->aCol[j].zName;
4507 char *zColname; /* The computed column name */
4508 char *zToFree; /* Malloced string that needs to be freed */
4509 Token sColname; /* Computed column name as a token */
4510
4511 assert( zName );
4512 if( zTName && pSub
4513 && sqlite3MatchSpanName(pSub->pEList->a[j].zSpan, 0, zTName, 0)==0
4514 ){
4515 continue;
4516 }
4517
4518 /* If a column is marked as 'hidden', omit it from the expanded
4519 ** result-set list unless the SELECT has the SF_IncludeHidden
4520 ** bit set.
4521 */
4522 if( (p->selFlags & SF_IncludeHidden)==0
4523 && IsHiddenColumn(&pTab->aCol[j])
4524 ){
4525 continue;
4526 }
4527 tableSeen = 1;
4528
4529 if( i>0 && zTName==0 ){
4530 if( (pFrom->fg.jointype & JT_NATURAL)!=0
4531 && tableAndColumnIndex(pTabList, i, zName, 0, 0)
4532 ){
4533 /* In a NATURAL join, omit the join columns from the
4534 ** table to the right of the join */
4535 continue;
4536 }
4537 if( sqlite3IdListIndex(pFrom->pUsing, zName)>=0 ){
4538 /* In a join with a USING clause, omit columns in the
4539 ** using clause from the table on the right. */
4540 continue;
4541 }
4542 }
4543 pRight = sqlite3Expr(db, TK_ID, zName);
4544 zColname = zName;
4545 zToFree = 0;
4546 if( longNames || pTabList->nSrc>1 ){
4547 Expr *pLeft;
4548 pLeft = sqlite3Expr(db, TK_ID, zTabName);
4549 pExpr = sqlite3PExpr(pParse, TK_DOT, pLeft, pRight);
4550 if( zSchemaName ){
4551 pLeft = sqlite3Expr(db, TK_ID, zSchemaName);
4552 pExpr = sqlite3PExpr(pParse, TK_DOT, pLeft, pExpr);
4553 }
4554 if( longNames ){
4555 zColname = sqlite3MPrintf(db, "%s.%s", zTabName, zName);
4556 zToFree = zColname;
4557 }
4558 }else{
4559 pExpr = pRight;
4560 }
4561 pNew = sqlite3ExprListAppend(pParse, pNew, pExpr);
4562 sqlite3TokenInit(&sColname, zColname);
4563 sqlite3ExprListSetName(pParse, pNew, &sColname, 0);
4564 if( pNew && (p->selFlags & SF_NestedFrom)!=0 ){
4565 struct ExprList_item *pX = &pNew->a[pNew->nExpr-1];
4566 if( pSub ){
4567 pX->zSpan = sqlite3DbStrDup(db, pSub->pEList->a[j].zSpan);
4568 testcase( pX->zSpan==0 );
4569 }else{
4570 pX->zSpan = sqlite3MPrintf(db, "%s.%s.%s",
4571 zSchemaName, zTabName, zColname);
4572 testcase( pX->zSpan==0 );
4573 }
4574 pX->bSpanIsTab = 1;
4575 }
4576 sqlite3DbFree(db, zToFree);
4577 }
4578 }
4579 if( !tableSeen ){
4580 if( zTName ){
4581 sqlite3ErrorMsg(pParse, "no such table: %s", zTName);
4582 }else{
4583 sqlite3ErrorMsg(pParse, "no tables specified");
4584 }
4585 }
4586 }
4587 }
4588 sqlite3ExprListDelete(db, pEList);
4589 p->pEList = pNew;
4590 }
4591 #if SQLITE_MAX_COLUMN
4592 if( p->pEList && p->pEList->nExpr>db->aLimit[SQLITE_LIMIT_COLUMN] ){
4593 sqlite3ErrorMsg(pParse, "too many columns in result set");
4594 return WRC_Abort;
4595 }
4596 #endif
4597 return WRC_Continue;
4598 }
4599
4600 /*
4601 ** No-op routine for the parse-tree walker.
4602 **
4603 ** When this routine is the Walker.xExprCallback then expression trees
4604 ** are walked without any actions being taken at each node. Presumably,
4605 ** when this routine is used for Walker.xExprCallback then
4606 ** Walker.xSelectCallback is set to do something useful for every
4607 ** subquery in the parser tree.
4608 */
sqlite3ExprWalkNoop(Walker * NotUsed,Expr * NotUsed2)4609 int sqlite3ExprWalkNoop(Walker *NotUsed, Expr *NotUsed2){
4610 UNUSED_PARAMETER2(NotUsed, NotUsed2);
4611 return WRC_Continue;
4612 }
4613
4614 /*
4615 ** No-op routine for the parse-tree walker for SELECT statements.
4616 ** subquery in the parser tree.
4617 */
sqlite3SelectWalkNoop(Walker * NotUsed,Select * NotUsed2)4618 int sqlite3SelectWalkNoop(Walker *NotUsed, Select *NotUsed2){
4619 UNUSED_PARAMETER2(NotUsed, NotUsed2);
4620 return WRC_Continue;
4621 }
4622
4623 #if SQLITE_DEBUG
4624 /*
4625 ** Always assert. This xSelectCallback2 implementation proves that the
4626 ** xSelectCallback2 is never invoked.
4627 */
sqlite3SelectWalkAssert2(Walker * NotUsed,Select * NotUsed2)4628 void sqlite3SelectWalkAssert2(Walker *NotUsed, Select *NotUsed2){
4629 UNUSED_PARAMETER2(NotUsed, NotUsed2);
4630 assert( 0 );
4631 }
4632 #endif
4633 /*
4634 ** This routine "expands" a SELECT statement and all of its subqueries.
4635 ** For additional information on what it means to "expand" a SELECT
4636 ** statement, see the comment on the selectExpand worker callback above.
4637 **
4638 ** Expanding a SELECT statement is the first step in processing a
4639 ** SELECT statement. The SELECT statement must be expanded before
4640 ** name resolution is performed.
4641 **
4642 ** If anything goes wrong, an error message is written into pParse.
4643 ** The calling function can detect the problem by looking at pParse->nErr
4644 ** and/or pParse->db->mallocFailed.
4645 */
sqlite3SelectExpand(Parse * pParse,Select * pSelect)4646 static void sqlite3SelectExpand(Parse *pParse, Select *pSelect){
4647 Walker w;
4648 w.xExprCallback = sqlite3ExprWalkNoop;
4649 w.pParse = pParse;
4650 if( pParse->hasCompound ){
4651 w.xSelectCallback = convertCompoundSelectToSubquery;
4652 w.xSelectCallback2 = 0;
4653 sqlite3WalkSelect(&w, pSelect);
4654 }
4655 w.xSelectCallback = selectExpander;
4656 w.xSelectCallback2 = selectPopWith;
4657 sqlite3WalkSelect(&w, pSelect);
4658 }
4659
4660
4661 #ifndef SQLITE_OMIT_SUBQUERY
4662 /*
4663 ** This is a Walker.xSelectCallback callback for the sqlite3SelectTypeInfo()
4664 ** interface.
4665 **
4666 ** For each FROM-clause subquery, add Column.zType and Column.zColl
4667 ** information to the Table structure that represents the result set
4668 ** of that subquery.
4669 **
4670 ** The Table structure that represents the result set was constructed
4671 ** by selectExpander() but the type and collation information was omitted
4672 ** at that point because identifiers had not yet been resolved. This
4673 ** routine is called after identifier resolution.
4674 */
selectAddSubqueryTypeInfo(Walker * pWalker,Select * p)4675 static void selectAddSubqueryTypeInfo(Walker *pWalker, Select *p){
4676 Parse *pParse;
4677 int i;
4678 SrcList *pTabList;
4679 struct SrcList_item *pFrom;
4680
4681 assert( p->selFlags & SF_Resolved );
4682 assert( (p->selFlags & SF_HasTypeInfo)==0 );
4683 p->selFlags |= SF_HasTypeInfo;
4684 pParse = pWalker->pParse;
4685 pTabList = p->pSrc;
4686 for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){
4687 Table *pTab = pFrom->pTab;
4688 assert( pTab!=0 );
4689 if( (pTab->tabFlags & TF_Ephemeral)!=0 ){
4690 /* A sub-query in the FROM clause of a SELECT */
4691 Select *pSel = pFrom->pSelect;
4692 if( pSel ){
4693 while( pSel->pPrior ) pSel = pSel->pPrior;
4694 sqlite3SelectAddColumnTypeAndCollation(pParse, pTab, pSel);
4695 }
4696 }
4697 }
4698 }
4699 #endif
4700
4701
4702 /*
4703 ** This routine adds datatype and collating sequence information to
4704 ** the Table structures of all FROM-clause subqueries in a
4705 ** SELECT statement.
4706 **
4707 ** Use this routine after name resolution.
4708 */
sqlite3SelectAddTypeInfo(Parse * pParse,Select * pSelect)4709 static void sqlite3SelectAddTypeInfo(Parse *pParse, Select *pSelect){
4710 #ifndef SQLITE_OMIT_SUBQUERY
4711 Walker w;
4712 w.xSelectCallback = sqlite3SelectWalkNoop;
4713 w.xSelectCallback2 = selectAddSubqueryTypeInfo;
4714 w.xExprCallback = sqlite3ExprWalkNoop;
4715 w.pParse = pParse;
4716 sqlite3WalkSelect(&w, pSelect);
4717 #endif
4718 }
4719
4720
4721 /*
4722 ** This routine sets up a SELECT statement for processing. The
4723 ** following is accomplished:
4724 **
4725 ** * VDBE Cursor numbers are assigned to all FROM-clause terms.
4726 ** * Ephemeral Table objects are created for all FROM-clause subqueries.
4727 ** * ON and USING clauses are shifted into WHERE statements
4728 ** * Wildcards "*" and "TABLE.*" in result sets are expanded.
4729 ** * Identifiers in expression are matched to tables.
4730 **
4731 ** This routine acts recursively on all subqueries within the SELECT.
4732 */
sqlite3SelectPrep(Parse * pParse,Select * p,NameContext * pOuterNC)4733 void sqlite3SelectPrep(
4734 Parse *pParse, /* The parser context */
4735 Select *p, /* The SELECT statement being coded. */
4736 NameContext *pOuterNC /* Name context for container */
4737 ){
4738 sqlite3 *db;
4739 if( NEVER(p==0) ) return;
4740 db = pParse->db;
4741 if( db->mallocFailed ) return;
4742 if( p->selFlags & SF_HasTypeInfo ) return;
4743 sqlite3SelectExpand(pParse, p);
4744 if( pParse->nErr || db->mallocFailed ) return;
4745 sqlite3ResolveSelectNames(pParse, p, pOuterNC);
4746 if( pParse->nErr || db->mallocFailed ) return;
4747 sqlite3SelectAddTypeInfo(pParse, p);
4748 }
4749
4750 /*
4751 ** Reset the aggregate accumulator.
4752 **
4753 ** The aggregate accumulator is a set of memory cells that hold
4754 ** intermediate results while calculating an aggregate. This
4755 ** routine generates code that stores NULLs in all of those memory
4756 ** cells.
4757 */
resetAccumulator(Parse * pParse,AggInfo * pAggInfo)4758 static void resetAccumulator(Parse *pParse, AggInfo *pAggInfo){
4759 Vdbe *v = pParse->pVdbe;
4760 int i;
4761 struct AggInfo_func *pFunc;
4762 int nReg = pAggInfo->nFunc + pAggInfo->nColumn;
4763 if( nReg==0 ) return;
4764 #ifdef SQLITE_DEBUG
4765 /* Verify that all AggInfo registers are within the range specified by
4766 ** AggInfo.mnReg..AggInfo.mxReg */
4767 assert( nReg==pAggInfo->mxReg-pAggInfo->mnReg+1 );
4768 for(i=0; i<pAggInfo->nColumn; i++){
4769 assert( pAggInfo->aCol[i].iMem>=pAggInfo->mnReg
4770 && pAggInfo->aCol[i].iMem<=pAggInfo->mxReg );
4771 }
4772 for(i=0; i<pAggInfo->nFunc; i++){
4773 assert( pAggInfo->aFunc[i].iMem>=pAggInfo->mnReg
4774 && pAggInfo->aFunc[i].iMem<=pAggInfo->mxReg );
4775 }
4776 #endif
4777 sqlite3VdbeAddOp3(v, OP_Null, 0, pAggInfo->mnReg, pAggInfo->mxReg);
4778 for(pFunc=pAggInfo->aFunc, i=0; i<pAggInfo->nFunc; i++, pFunc++){
4779 if( pFunc->iDistinct>=0 ){
4780 Expr *pE = pFunc->pExpr;
4781 assert( !ExprHasProperty(pE, EP_xIsSelect) );
4782 if( pE->x.pList==0 || pE->x.pList->nExpr!=1 ){
4783 sqlite3ErrorMsg(pParse, "DISTINCT aggregates must have exactly one "
4784 "argument");
4785 pFunc->iDistinct = -1;
4786 }else{
4787 KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pE->x.pList, 0, 0);
4788 sqlite3VdbeAddOp4(v, OP_OpenEphemeral, pFunc->iDistinct, 0, 0,
4789 (char*)pKeyInfo, P4_KEYINFO);
4790 }
4791 }
4792 }
4793 }
4794
4795 /*
4796 ** Invoke the OP_AggFinalize opcode for every aggregate function
4797 ** in the AggInfo structure.
4798 */
finalizeAggFunctions(Parse * pParse,AggInfo * pAggInfo)4799 static void finalizeAggFunctions(Parse *pParse, AggInfo *pAggInfo){
4800 Vdbe *v = pParse->pVdbe;
4801 int i;
4802 struct AggInfo_func *pF;
4803 for(i=0, pF=pAggInfo->aFunc; i<pAggInfo->nFunc; i++, pF++){
4804 ExprList *pList = pF->pExpr->x.pList;
4805 assert( !ExprHasProperty(pF->pExpr, EP_xIsSelect) );
4806 sqlite3VdbeAddOp2(v, OP_AggFinal, pF->iMem, pList ? pList->nExpr : 0);
4807 sqlite3VdbeAppendP4(v, pF->pFunc, P4_FUNCDEF);
4808 }
4809 }
4810
4811 /*
4812 ** Update the accumulator memory cells for an aggregate based on
4813 ** the current cursor position.
4814 */
updateAccumulator(Parse * pParse,AggInfo * pAggInfo)4815 static void updateAccumulator(Parse *pParse, AggInfo *pAggInfo){
4816 Vdbe *v = pParse->pVdbe;
4817 int i;
4818 int regHit = 0;
4819 int addrHitTest = 0;
4820 struct AggInfo_func *pF;
4821 struct AggInfo_col *pC;
4822
4823 pAggInfo->directMode = 1;
4824 for(i=0, pF=pAggInfo->aFunc; i<pAggInfo->nFunc; i++, pF++){
4825 int nArg;
4826 int addrNext = 0;
4827 int regAgg;
4828 ExprList *pList = pF->pExpr->x.pList;
4829 assert( !ExprHasProperty(pF->pExpr, EP_xIsSelect) );
4830 if( pList ){
4831 nArg = pList->nExpr;
4832 regAgg = sqlite3GetTempRange(pParse, nArg);
4833 sqlite3ExprCodeExprList(pParse, pList, regAgg, 0, SQLITE_ECEL_DUP);
4834 }else{
4835 nArg = 0;
4836 regAgg = 0;
4837 }
4838 if( pF->iDistinct>=0 ){
4839 addrNext = sqlite3VdbeMakeLabel(v);
4840 testcase( nArg==0 ); /* Error condition */
4841 testcase( nArg>1 ); /* Also an error */
4842 codeDistinct(pParse, pF->iDistinct, addrNext, 1, regAgg);
4843 }
4844 if( pF->pFunc->funcFlags & SQLITE_FUNC_NEEDCOLL ){
4845 CollSeq *pColl = 0;
4846 struct ExprList_item *pItem;
4847 int j;
4848 assert( pList!=0 ); /* pList!=0 if pF->pFunc has NEEDCOLL */
4849 for(j=0, pItem=pList->a; !pColl && j<nArg; j++, pItem++){
4850 pColl = sqlite3ExprCollSeq(pParse, pItem->pExpr);
4851 }
4852 if( !pColl ){
4853 pColl = pParse->db->pDfltColl;
4854 }
4855 if( regHit==0 && pAggInfo->nAccumulator ) regHit = ++pParse->nMem;
4856 sqlite3VdbeAddOp4(v, OP_CollSeq, regHit, 0, 0, (char *)pColl, P4_COLLSEQ);
4857 }
4858 sqlite3VdbeAddOp3(v, OP_AggStep0, 0, regAgg, pF->iMem);
4859 sqlite3VdbeAppendP4(v, pF->pFunc, P4_FUNCDEF);
4860 sqlite3VdbeChangeP5(v, (u8)nArg);
4861 sqlite3ExprCacheAffinityChange(pParse, regAgg, nArg);
4862 sqlite3ReleaseTempRange(pParse, regAgg, nArg);
4863 if( addrNext ){
4864 sqlite3VdbeResolveLabel(v, addrNext);
4865 sqlite3ExprCacheClear(pParse);
4866 }
4867 }
4868
4869 /* Before populating the accumulator registers, clear the column cache.
4870 ** Otherwise, if any of the required column values are already present
4871 ** in registers, sqlite3ExprCode() may use OP_SCopy to copy the value
4872 ** to pC->iMem. But by the time the value is used, the original register
4873 ** may have been used, invalidating the underlying buffer holding the
4874 ** text or blob value. See ticket [883034dcb5].
4875 **
4876 ** Another solution would be to change the OP_SCopy used to copy cached
4877 ** values to an OP_Copy.
4878 */
4879 if( regHit ){
4880 addrHitTest = sqlite3VdbeAddOp1(v, OP_If, regHit); VdbeCoverage(v);
4881 }
4882 sqlite3ExprCacheClear(pParse);
4883 for(i=0, pC=pAggInfo->aCol; i<pAggInfo->nAccumulator; i++, pC++){
4884 sqlite3ExprCode(pParse, pC->pExpr, pC->iMem);
4885 }
4886 pAggInfo->directMode = 0;
4887 sqlite3ExprCacheClear(pParse);
4888 if( addrHitTest ){
4889 sqlite3VdbeJumpHere(v, addrHitTest);
4890 }
4891 }
4892
4893 /*
4894 ** Add a single OP_Explain instruction to the VDBE to explain a simple
4895 ** count(*) query ("SELECT count(*) FROM pTab").
4896 */
4897 #ifndef SQLITE_OMIT_EXPLAIN
explainSimpleCount(Parse * pParse,Table * pTab,Index * pIdx)4898 static void explainSimpleCount(
4899 Parse *pParse, /* Parse context */
4900 Table *pTab, /* Table being queried */
4901 Index *pIdx /* Index used to optimize scan, or NULL */
4902 ){
4903 if( pParse->explain==2 ){
4904 int bCover = (pIdx!=0 && (HasRowid(pTab) || !IsPrimaryKeyIndex(pIdx)));
4905 char *zEqp = sqlite3MPrintf(pParse->db, "SCAN TABLE %s%s%s",
4906 pTab->zName,
4907 bCover ? " USING COVERING INDEX " : "",
4908 bCover ? pIdx->zName : ""
4909 );
4910 sqlite3VdbeAddOp4(
4911 pParse->pVdbe, OP_Explain, pParse->iSelectId, 0, 0, zEqp, P4_DYNAMIC
4912 );
4913 }
4914 }
4915 #else
4916 # define explainSimpleCount(a,b,c)
4917 #endif
4918
4919 /*
4920 ** Context object for havingToWhereExprCb().
4921 */
4922 struct HavingToWhereCtx {
4923 Expr **ppWhere;
4924 ExprList *pGroupBy;
4925 };
4926
4927 /*
4928 ** sqlite3WalkExpr() callback used by havingToWhere().
4929 **
4930 ** If the node passed to the callback is a TK_AND node, return
4931 ** WRC_Continue to tell sqlite3WalkExpr() to iterate through child nodes.
4932 **
4933 ** Otherwise, return WRC_Prune. In this case, also check if the
4934 ** sub-expression matches the criteria for being moved to the WHERE
4935 ** clause. If so, add it to the WHERE clause and replace the sub-expression
4936 ** within the HAVING expression with a constant "1".
4937 */
havingToWhereExprCb(Walker * pWalker,Expr * pExpr)4938 static int havingToWhereExprCb(Walker *pWalker, Expr *pExpr){
4939 if( pExpr->op!=TK_AND ){
4940 struct HavingToWhereCtx *p = pWalker->u.pHavingCtx;
4941 if( sqlite3ExprIsConstantOrGroupBy(pWalker->pParse, pExpr, p->pGroupBy) ){
4942 sqlite3 *db = pWalker->pParse->db;
4943 Expr *pNew = sqlite3ExprAlloc(db, TK_INTEGER, &sqlite3IntTokens[1], 0);
4944 if( pNew ){
4945 Expr *pWhere = *(p->ppWhere);
4946 SWAP(Expr, *pNew, *pExpr);
4947 pNew = sqlite3ExprAnd(db, pWhere, pNew);
4948 *(p->ppWhere) = pNew;
4949 }
4950 }
4951 return WRC_Prune;
4952 }
4953 return WRC_Continue;
4954 }
4955
4956 /*
4957 ** Transfer eligible terms from the HAVING clause of a query, which is
4958 ** processed after grouping, to the WHERE clause, which is processed before
4959 ** grouping. For example, the query:
4960 **
4961 ** SELECT * FROM <tables> WHERE a=? GROUP BY b HAVING b=? AND c=?
4962 **
4963 ** can be rewritten as:
4964 **
4965 ** SELECT * FROM <tables> WHERE a=? AND b=? GROUP BY b HAVING c=?
4966 **
4967 ** A term of the HAVING expression is eligible for transfer if it consists
4968 ** entirely of constants and expressions that are also GROUP BY terms that
4969 ** use the "BINARY" collation sequence.
4970 */
havingToWhere(Parse * pParse,ExprList * pGroupBy,Expr * pHaving,Expr ** ppWhere)4971 static void havingToWhere(
4972 Parse *pParse,
4973 ExprList *pGroupBy,
4974 Expr *pHaving,
4975 Expr **ppWhere
4976 ){
4977 struct HavingToWhereCtx sCtx;
4978 Walker sWalker;
4979
4980 sCtx.ppWhere = ppWhere;
4981 sCtx.pGroupBy = pGroupBy;
4982
4983 memset(&sWalker, 0, sizeof(sWalker));
4984 sWalker.pParse = pParse;
4985 sWalker.xExprCallback = havingToWhereExprCb;
4986 sWalker.u.pHavingCtx = &sCtx;
4987 sqlite3WalkExpr(&sWalker, pHaving);
4988 }
4989
4990 /*
4991 ** Check to see if the pThis entry of pTabList is a self-join of a prior view.
4992 ** If it is, then return the SrcList_item for the prior view. If it is not,
4993 ** then return 0.
4994 */
isSelfJoinView(SrcList * pTabList,struct SrcList_item * pThis)4995 static struct SrcList_item *isSelfJoinView(
4996 SrcList *pTabList, /* Search for self-joins in this FROM clause */
4997 struct SrcList_item *pThis /* Search for prior reference to this subquery */
4998 ){
4999 struct SrcList_item *pItem;
5000 for(pItem = pTabList->a; pItem<pThis; pItem++){
5001 if( pItem->pSelect==0 ) continue;
5002 if( pItem->fg.viaCoroutine ) continue;
5003 if( pItem->zName==0 ) continue;
5004 if( sqlite3_stricmp(pItem->zDatabase, pThis->zDatabase)!=0 ) continue;
5005 if( sqlite3_stricmp(pItem->zName, pThis->zName)!=0 ) continue;
5006 if( sqlite3ExprCompare(0,
5007 pThis->pSelect->pWhere, pItem->pSelect->pWhere, -1)
5008 ){
5009 /* The view was modified by some other optimization such as
5010 ** pushDownWhereTerms() */
5011 continue;
5012 }
5013 return pItem;
5014 }
5015 return 0;
5016 }
5017
5018 #ifdef SQLITE_COUNTOFVIEW_OPTIMIZATION
5019 /*
5020 ** Attempt to transform a query of the form
5021 **
5022 ** SELECT count(*) FROM (SELECT x FROM t1 UNION ALL SELECT y FROM t2)
5023 **
5024 ** Into this:
5025 **
5026 ** SELECT (SELECT count(*) FROM t1)+(SELECT count(*) FROM t2)
5027 **
5028 ** The transformation only works if all of the following are true:
5029 **
5030 ** * The subquery is a UNION ALL of two or more terms
5031 ** * There is no WHERE or GROUP BY or HAVING clauses on the subqueries
5032 ** * The outer query is a simple count(*)
5033 **
5034 ** Return TRUE if the optimization is undertaken.
5035 */
countOfViewOptimization(Parse * pParse,Select * p)5036 static int countOfViewOptimization(Parse *pParse, Select *p){
5037 Select *pSub, *pPrior;
5038 Expr *pExpr;
5039 Expr *pCount;
5040 sqlite3 *db;
5041 if( (p->selFlags & SF_Aggregate)==0 ) return 0; /* This is an aggregate query */
5042 if( p->pEList->nExpr!=1 ) return 0; /* Single result column */
5043 pExpr = p->pEList->a[0].pExpr;
5044 if( pExpr->op!=TK_AGG_FUNCTION ) return 0; /* Result is an aggregate */
5045 if( sqlite3_stricmp(pExpr->u.zToken,"count") ) return 0; /* Must be count() */
5046 if( pExpr->x.pList!=0 ) return 0; /* Must be count(*) */
5047 if( p->pSrc->nSrc!=1 ) return 0; /* One table in the FROM clause */
5048 pSub = p->pSrc->a[0].pSelect;
5049 if( pSub==0 ) return 0; /* The FROM is a subquery */
5050 if( pSub->pPrior==0 ) return 0; /* Must be a compound subquery */
5051 do{
5052 if( pSub->op!=TK_ALL && pSub->pPrior ) return 0; /* Must be UNION ALL */
5053 if( pSub->pWhere ) return 0; /* No WHERE clause */
5054 if( pSub->selFlags & SF_Aggregate ) return 0; /* Not an aggregate */
5055 pSub = pSub->pPrior; /* Repeat over compound terms */
5056 }while( pSub );
5057
5058 /* If we reach this point, that means it is OK to perform the transformation */
5059
5060 db = pParse->db;
5061 pCount = pExpr;
5062 pExpr = 0;
5063 pSub = p->pSrc->a[0].pSelect;
5064 p->pSrc->a[0].pSelect = 0;
5065 sqlite3SrcListDelete(db, p->pSrc);
5066 p->pSrc = sqlite3DbMallocZero(pParse->db, sizeof(*p->pSrc));
5067 while( pSub ){
5068 Expr *pTerm;
5069 pPrior = pSub->pPrior;
5070 pSub->pPrior = 0;
5071 pSub->pNext = 0;
5072 pSub->selFlags |= SF_Aggregate;
5073 pSub->selFlags &= ~SF_Compound;
5074 pSub->nSelectRow = 0;
5075 sqlite3ExprListDelete(db, pSub->pEList);
5076 pTerm = pPrior ? sqlite3ExprDup(db, pCount, 0) : pCount;
5077 pSub->pEList = sqlite3ExprListAppend(pParse, 0, pTerm);
5078 pTerm = sqlite3PExpr(pParse, TK_SELECT, 0, 0);
5079 sqlite3PExprAddSelect(pParse, pTerm, pSub);
5080 if( pExpr==0 ){
5081 pExpr = pTerm;
5082 }else{
5083 pExpr = sqlite3PExpr(pParse, TK_PLUS, pTerm, pExpr);
5084 }
5085 pSub = pPrior;
5086 }
5087 p->pEList->a[0].pExpr = pExpr;
5088 p->selFlags &= ~SF_Aggregate;
5089
5090 #if SELECTTRACE_ENABLED
5091 if( sqlite3SelectTrace & 0x400 ){
5092 SELECTTRACE(0x400,pParse,p,("After count-of-view optimization:\n"));
5093 sqlite3TreeViewSelect(0, p, 0);
5094 }
5095 #endif
5096 return 1;
5097 }
5098 #endif /* SQLITE_COUNTOFVIEW_OPTIMIZATION */
5099
5100 /*
5101 ** Generate code for the SELECT statement given in the p argument.
5102 **
5103 ** The results are returned according to the SelectDest structure.
5104 ** See comments in sqliteInt.h for further information.
5105 **
5106 ** This routine returns the number of errors. If any errors are
5107 ** encountered, then an appropriate error message is left in
5108 ** pParse->zErrMsg.
5109 **
5110 ** This routine does NOT free the Select structure passed in. The
5111 ** calling function needs to do that.
5112 */
sqlite3Select(Parse * pParse,Select * p,SelectDest * pDest)5113 int sqlite3Select(
5114 Parse *pParse, /* The parser context */
5115 Select *p, /* The SELECT statement being coded. */
5116 SelectDest *pDest /* What to do with the query results */
5117 ){
5118 int i, j; /* Loop counters */
5119 WhereInfo *pWInfo; /* Return from sqlite3WhereBegin() */
5120 Vdbe *v; /* The virtual machine under construction */
5121 int isAgg; /* True for select lists like "count(*)" */
5122 ExprList *pEList = 0; /* List of columns to extract. */
5123 SrcList *pTabList; /* List of tables to select from */
5124 Expr *pWhere; /* The WHERE clause. May be NULL */
5125 ExprList *pGroupBy; /* The GROUP BY clause. May be NULL */
5126 Expr *pHaving; /* The HAVING clause. May be NULL */
5127 int rc = 1; /* Value to return from this function */
5128 DistinctCtx sDistinct; /* Info on how to code the DISTINCT keyword */
5129 SortCtx sSort; /* Info on how to code the ORDER BY clause */
5130 AggInfo sAggInfo; /* Information used by aggregate queries */
5131 int iEnd; /* Address of the end of the query */
5132 sqlite3 *db; /* The database connection */
5133
5134 #ifndef SQLITE_OMIT_EXPLAIN
5135 int iRestoreSelectId = pParse->iSelectId;
5136 pParse->iSelectId = pParse->iNextSelectId++;
5137 #endif
5138
5139 db = pParse->db;
5140 if( p==0 || db->mallocFailed || pParse->nErr ){
5141 return 1;
5142 }
5143 if( sqlite3AuthCheck(pParse, SQLITE_SELECT, 0, 0, 0) ) return 1;
5144 memset(&sAggInfo, 0, sizeof(sAggInfo));
5145 #if SELECTTRACE_ENABLED
5146 pParse->nSelectIndent++;
5147 SELECTTRACE(1,pParse,p, ("begin processing:\n"));
5148 if( sqlite3SelectTrace & 0x100 ){
5149 sqlite3TreeViewSelect(0, p, 0);
5150 }
5151 #endif
5152
5153 assert( p->pOrderBy==0 || pDest->eDest!=SRT_DistFifo );
5154 assert( p->pOrderBy==0 || pDest->eDest!=SRT_Fifo );
5155 assert( p->pOrderBy==0 || pDest->eDest!=SRT_DistQueue );
5156 assert( p->pOrderBy==0 || pDest->eDest!=SRT_Queue );
5157 if( IgnorableOrderby(pDest) ){
5158 assert(pDest->eDest==SRT_Exists || pDest->eDest==SRT_Union ||
5159 pDest->eDest==SRT_Except || pDest->eDest==SRT_Discard ||
5160 pDest->eDest==SRT_Queue || pDest->eDest==SRT_DistFifo ||
5161 pDest->eDest==SRT_DistQueue || pDest->eDest==SRT_Fifo);
5162 /* If ORDER BY makes no difference in the output then neither does
5163 ** DISTINCT so it can be removed too. */
5164 sqlite3ExprListDelete(db, p->pOrderBy);
5165 p->pOrderBy = 0;
5166 p->selFlags &= ~SF_Distinct;
5167 }
5168 sqlite3SelectPrep(pParse, p, 0);
5169 memset(&sSort, 0, sizeof(sSort));
5170 sSort.pOrderBy = p->pOrderBy;
5171 pTabList = p->pSrc;
5172 if( pParse->nErr || db->mallocFailed ){
5173 goto select_end;
5174 }
5175 assert( p->pEList!=0 );
5176 isAgg = (p->selFlags & SF_Aggregate)!=0;
5177 #if SELECTTRACE_ENABLED
5178 if( sqlite3SelectTrace & 0x100 ){
5179 SELECTTRACE(0x100,pParse,p, ("after name resolution:\n"));
5180 sqlite3TreeViewSelect(0, p, 0);
5181 }
5182 #endif
5183
5184 /* Get a pointer the VDBE under construction, allocating a new VDBE if one
5185 ** does not already exist */
5186 v = sqlite3GetVdbe(pParse);
5187 if( v==0 ) goto select_end;
5188 if( pDest->eDest==SRT_Output ){
5189 generateColumnNames(pParse, p);
5190 }
5191
5192 /* Try to flatten subqueries in the FROM clause up into the main query
5193 */
5194 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
5195 for(i=0; !p->pPrior && i<pTabList->nSrc; i++){
5196 struct SrcList_item *pItem = &pTabList->a[i];
5197 Select *pSub = pItem->pSelect;
5198 int isAggSub;
5199 Table *pTab = pItem->pTab;
5200 if( pSub==0 ) continue;
5201
5202 /* Catch mismatch in the declared columns of a view and the number of
5203 ** columns in the SELECT on the RHS */
5204 if( pTab->nCol!=pSub->pEList->nExpr ){
5205 sqlite3ErrorMsg(pParse, "expected %d columns for '%s' but got %d",
5206 pTab->nCol, pTab->zName, pSub->pEList->nExpr);
5207 goto select_end;
5208 }
5209
5210 isAggSub = (pSub->selFlags & SF_Aggregate)!=0;
5211 if( flattenSubquery(pParse, p, i, isAgg, isAggSub) ){
5212 /* This subquery can be absorbed into its parent. */
5213 if( isAggSub ){
5214 isAgg = 1;
5215 p->selFlags |= SF_Aggregate;
5216 }
5217 i = -1;
5218 }
5219 pTabList = p->pSrc;
5220 if( db->mallocFailed ) goto select_end;
5221 if( !IgnorableOrderby(pDest) ){
5222 sSort.pOrderBy = p->pOrderBy;
5223 }
5224 }
5225 #endif
5226
5227 #ifndef SQLITE_OMIT_COMPOUND_SELECT
5228 /* Handle compound SELECT statements using the separate multiSelect()
5229 ** procedure.
5230 */
5231 if( p->pPrior ){
5232 rc = multiSelect(pParse, p, pDest);
5233 explainSetInteger(pParse->iSelectId, iRestoreSelectId);
5234 #if SELECTTRACE_ENABLED
5235 SELECTTRACE(1,pParse,p,("end compound-select processing\n"));
5236 pParse->nSelectIndent--;
5237 #endif
5238 return rc;
5239 }
5240 #endif
5241
5242 /* For each term in the FROM clause, do two things:
5243 ** (1) Authorized unreferenced tables
5244 ** (2) Generate code for all sub-queries
5245 */
5246 for(i=0; i<pTabList->nSrc; i++){
5247 struct SrcList_item *pItem = &pTabList->a[i];
5248 SelectDest dest;
5249 Select *pSub;
5250
5251 /* Issue SQLITE_READ authorizations with a fake column name for any tables that
5252 ** are referenced but from which no values are extracted. Examples of where these
5253 ** kinds of null SQLITE_READ authorizations would occur:
5254 **
5255 ** SELECT count(*) FROM t1; -- SQLITE_READ t1.""
5256 ** SELECT t1.* FROM t1, t2; -- SQLITE_READ t2.""
5257 **
5258 ** The fake column name is an empty string. It is possible for a table to
5259 ** have a column named by the empty string, in which case there is no way to
5260 ** distinguish between an unreferenced table and an actual reference to the
5261 ** "" column. The original design was for the fake column name to be a NULL,
5262 ** which would be unambiguous. But legacy authorization callbacks might
5263 ** assume the column name is non-NULL and segfault. The use of an empty string
5264 ** for the fake column name seems safer.
5265 */
5266 if( pItem->colUsed==0 ){
5267 sqlite3AuthCheck(pParse, SQLITE_READ, pItem->zName, "", pItem->zDatabase);
5268 }
5269
5270 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
5271 /* Generate code for all sub-queries in the FROM clause
5272 */
5273 pSub = pItem->pSelect;
5274 if( pSub==0 ) continue;
5275
5276 /* Sometimes the code for a subquery will be generated more than
5277 ** once, if the subquery is part of the WHERE clause in a LEFT JOIN,
5278 ** for example. In that case, do not regenerate the code to manifest
5279 ** a view or the co-routine to implement a view. The first instance
5280 ** is sufficient, though the subroutine to manifest the view does need
5281 ** to be invoked again. */
5282 if( pItem->addrFillSub ){
5283 if( pItem->fg.viaCoroutine==0 ){
5284 /* The subroutine that manifests the view might be a one-time routine,
5285 ** or it might need to be rerun on each iteration because it
5286 ** encodes a correlated subquery. */
5287 testcase( sqlite3VdbeGetOp(v, pItem->addrFillSub)->opcode==OP_Once );
5288 sqlite3VdbeAddOp2(v, OP_Gosub, pItem->regReturn, pItem->addrFillSub);
5289 }
5290 continue;
5291 }
5292
5293 /* Increment Parse.nHeight by the height of the largest expression
5294 ** tree referred to by this, the parent select. The child select
5295 ** may contain expression trees of at most
5296 ** (SQLITE_MAX_EXPR_DEPTH-Parse.nHeight) height. This is a bit
5297 ** more conservative than necessary, but much easier than enforcing
5298 ** an exact limit.
5299 */
5300 pParse->nHeight += sqlite3SelectExprHeight(p);
5301
5302 /* Make copies of constant WHERE-clause terms in the outer query down
5303 ** inside the subquery. This can help the subquery to run more efficiently.
5304 */
5305 if( (pItem->fg.jointype & JT_OUTER)==0
5306 && pushDownWhereTerms(pParse, pSub, p->pWhere, pItem->iCursor)
5307 ){
5308 #if SELECTTRACE_ENABLED
5309 if( sqlite3SelectTrace & 0x100 ){
5310 SELECTTRACE(0x100,pParse,p,("After WHERE-clause push-down:\n"));
5311 sqlite3TreeViewSelect(0, p, 0);
5312 }
5313 #endif
5314 }
5315
5316 /* Generate code to implement the subquery
5317 **
5318 ** The subquery is implemented as a co-routine if all of these are true:
5319 ** (1) The subquery is guaranteed to be the outer loop (so that it
5320 ** does not need to be computed more than once)
5321 ** (2) The ALL keyword after SELECT is omitted. (Applications are
5322 ** allowed to say "SELECT ALL" instead of just "SELECT" to disable
5323 ** the use of co-routines.)
5324 ** (3) Co-routines are not disabled using sqlite3_test_control()
5325 ** with SQLITE_TESTCTRL_OPTIMIZATIONS.
5326 **
5327 ** TODO: Are there other reasons beside (1) to use a co-routine
5328 ** implementation?
5329 */
5330 if( i==0
5331 && (pTabList->nSrc==1
5332 || (pTabList->a[1].fg.jointype&(JT_LEFT|JT_CROSS))!=0) /* (1) */
5333 && (p->selFlags & SF_All)==0 /* (2) */
5334 && OptimizationEnabled(db, SQLITE_SubqCoroutine) /* (3) */
5335 ){
5336 /* Implement a co-routine that will return a single row of the result
5337 ** set on each invocation.
5338 */
5339 int addrTop = sqlite3VdbeCurrentAddr(v)+1;
5340 pItem->regReturn = ++pParse->nMem;
5341 sqlite3VdbeAddOp3(v, OP_InitCoroutine, pItem->regReturn, 0, addrTop);
5342 VdbeComment((v, "%s", pItem->pTab->zName));
5343 pItem->addrFillSub = addrTop;
5344 sqlite3SelectDestInit(&dest, SRT_Coroutine, pItem->regReturn);
5345 explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId);
5346 sqlite3Select(pParse, pSub, &dest);
5347 pItem->pTab->nRowLogEst = pSub->nSelectRow;
5348 pItem->fg.viaCoroutine = 1;
5349 pItem->regResult = dest.iSdst;
5350 sqlite3VdbeEndCoroutine(v, pItem->regReturn);
5351 sqlite3VdbeJumpHere(v, addrTop-1);
5352 sqlite3ClearTempRegCache(pParse);
5353 }else{
5354 /* Generate a subroutine that will fill an ephemeral table with
5355 ** the content of this subquery. pItem->addrFillSub will point
5356 ** to the address of the generated subroutine. pItem->regReturn
5357 ** is a register allocated to hold the subroutine return address
5358 */
5359 int topAddr;
5360 int onceAddr = 0;
5361 int retAddr;
5362 struct SrcList_item *pPrior;
5363
5364 assert( pItem->addrFillSub==0 );
5365 pItem->regReturn = ++pParse->nMem;
5366 topAddr = sqlite3VdbeAddOp2(v, OP_Integer, 0, pItem->regReturn);
5367 pItem->addrFillSub = topAddr+1;
5368 if( pItem->fg.isCorrelated==0 ){
5369 /* If the subquery is not correlated and if we are not inside of
5370 ** a trigger, then we only need to compute the value of the subquery
5371 ** once. */
5372 onceAddr = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v);
5373 VdbeComment((v, "materialize \"%s\"", pItem->pTab->zName));
5374 }else{
5375 VdbeNoopComment((v, "materialize \"%s\"", pItem->pTab->zName));
5376 }
5377 pPrior = isSelfJoinView(pTabList, pItem);
5378 if( pPrior ){
5379 sqlite3VdbeAddOp2(v, OP_OpenDup, pItem->iCursor, pPrior->iCursor);
5380 explainSetInteger(pItem->iSelectId, pPrior->iSelectId);
5381 assert( pPrior->pSelect!=0 );
5382 pSub->nSelectRow = pPrior->pSelect->nSelectRow;
5383 }else{
5384 sqlite3SelectDestInit(&dest, SRT_EphemTab, pItem->iCursor);
5385 explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId);
5386 sqlite3Select(pParse, pSub, &dest);
5387 }
5388 pItem->pTab->nRowLogEst = pSub->nSelectRow;
5389 if( onceAddr ) sqlite3VdbeJumpHere(v, onceAddr);
5390 retAddr = sqlite3VdbeAddOp1(v, OP_Return, pItem->regReturn);
5391 VdbeComment((v, "end %s", pItem->pTab->zName));
5392 sqlite3VdbeChangeP1(v, topAddr, retAddr);
5393 sqlite3ClearTempRegCache(pParse);
5394 }
5395 if( db->mallocFailed ) goto select_end;
5396 pParse->nHeight -= sqlite3SelectExprHeight(p);
5397 #endif
5398 }
5399
5400 /* Various elements of the SELECT copied into local variables for
5401 ** convenience */
5402 pEList = p->pEList;
5403 pWhere = p->pWhere;
5404 pGroupBy = p->pGroupBy;
5405 pHaving = p->pHaving;
5406 sDistinct.isTnct = (p->selFlags & SF_Distinct)!=0;
5407
5408 #if SELECTTRACE_ENABLED
5409 if( sqlite3SelectTrace & 0x400 ){
5410 SELECTTRACE(0x400,pParse,p,("After all FROM-clause analysis:\n"));
5411 sqlite3TreeViewSelect(0, p, 0);
5412 }
5413 #endif
5414
5415 #ifdef SQLITE_COUNTOFVIEW_OPTIMIZATION
5416 if( OptimizationEnabled(db, SQLITE_QueryFlattener|SQLITE_CountOfView)
5417 && countOfViewOptimization(pParse, p)
5418 ){
5419 if( db->mallocFailed ) goto select_end;
5420 pEList = p->pEList;
5421 pTabList = p->pSrc;
5422 }
5423 #endif
5424
5425 /* If the query is DISTINCT with an ORDER BY but is not an aggregate, and
5426 ** if the select-list is the same as the ORDER BY list, then this query
5427 ** can be rewritten as a GROUP BY. In other words, this:
5428 **
5429 ** SELECT DISTINCT xyz FROM ... ORDER BY xyz
5430 **
5431 ** is transformed to:
5432 **
5433 ** SELECT xyz FROM ... GROUP BY xyz ORDER BY xyz
5434 **
5435 ** The second form is preferred as a single index (or temp-table) may be
5436 ** used for both the ORDER BY and DISTINCT processing. As originally
5437 ** written the query must use a temp-table for at least one of the ORDER
5438 ** BY and DISTINCT, and an index or separate temp-table for the other.
5439 */
5440 if( (p->selFlags & (SF_Distinct|SF_Aggregate))==SF_Distinct
5441 && sqlite3ExprListCompare(sSort.pOrderBy, pEList, -1)==0
5442 ){
5443 p->selFlags &= ~SF_Distinct;
5444 pGroupBy = p->pGroupBy = sqlite3ExprListDup(db, pEList, 0);
5445 /* Notice that even thought SF_Distinct has been cleared from p->selFlags,
5446 ** the sDistinct.isTnct is still set. Hence, isTnct represents the
5447 ** original setting of the SF_Distinct flag, not the current setting */
5448 assert( sDistinct.isTnct );
5449
5450 #if SELECTTRACE_ENABLED
5451 if( sqlite3SelectTrace & 0x400 ){
5452 SELECTTRACE(0x400,pParse,p,("Transform DISTINCT into GROUP BY:\n"));
5453 sqlite3TreeViewSelect(0, p, 0);
5454 }
5455 #endif
5456 }
5457
5458 /* If there is an ORDER BY clause, then create an ephemeral index to
5459 ** do the sorting. But this sorting ephemeral index might end up
5460 ** being unused if the data can be extracted in pre-sorted order.
5461 ** If that is the case, then the OP_OpenEphemeral instruction will be
5462 ** changed to an OP_Noop once we figure out that the sorting index is
5463 ** not needed. The sSort.addrSortIndex variable is used to facilitate
5464 ** that change.
5465 */
5466 if( sSort.pOrderBy ){
5467 KeyInfo *pKeyInfo;
5468 pKeyInfo = keyInfoFromExprList(pParse, sSort.pOrderBy, 0, pEList->nExpr);
5469 sSort.iECursor = pParse->nTab++;
5470 sSort.addrSortIndex =
5471 sqlite3VdbeAddOp4(v, OP_OpenEphemeral,
5472 sSort.iECursor, sSort.pOrderBy->nExpr+1+pEList->nExpr, 0,
5473 (char*)pKeyInfo, P4_KEYINFO
5474 );
5475 }else{
5476 sSort.addrSortIndex = -1;
5477 }
5478
5479 /* If the output is destined for a temporary table, open that table.
5480 */
5481 if( pDest->eDest==SRT_EphemTab ){
5482 sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pDest->iSDParm, pEList->nExpr);
5483 }
5484
5485 /* Set the limiter.
5486 */
5487 iEnd = sqlite3VdbeMakeLabel(v);
5488 if( (p->selFlags & SF_FixedLimit)==0 ){
5489 p->nSelectRow = 320; /* 4 billion rows */
5490 }
5491 computeLimitRegisters(pParse, p, iEnd);
5492 if( p->iLimit==0 && sSort.addrSortIndex>=0 ){
5493 sqlite3VdbeChangeOpcode(v, sSort.addrSortIndex, OP_SorterOpen);
5494 sSort.sortFlags |= SORTFLAG_UseSorter;
5495 }
5496
5497 /* Open an ephemeral index to use for the distinct set.
5498 */
5499 if( p->selFlags & SF_Distinct ){
5500 sDistinct.tabTnct = pParse->nTab++;
5501 sDistinct.addrTnct = sqlite3VdbeAddOp4(v, OP_OpenEphemeral,
5502 sDistinct.tabTnct, 0, 0,
5503 (char*)keyInfoFromExprList(pParse, p->pEList,0,0),
5504 P4_KEYINFO);
5505 sqlite3VdbeChangeP5(v, BTREE_UNORDERED);
5506 sDistinct.eTnctType = WHERE_DISTINCT_UNORDERED;
5507 }else{
5508 sDistinct.eTnctType = WHERE_DISTINCT_NOOP;
5509 }
5510
5511 if( !isAgg && pGroupBy==0 ){
5512 /* No aggregate functions and no GROUP BY clause */
5513 u16 wctrlFlags = (sDistinct.isTnct ? WHERE_WANT_DISTINCT : 0);
5514 assert( WHERE_USE_LIMIT==SF_FixedLimit );
5515 wctrlFlags |= p->selFlags & SF_FixedLimit;
5516
5517 /* Begin the database scan. */
5518 pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, sSort.pOrderBy,
5519 p->pEList, wctrlFlags, p->nSelectRow);
5520 if( pWInfo==0 ) goto select_end;
5521 if( sqlite3WhereOutputRowCount(pWInfo) < p->nSelectRow ){
5522 p->nSelectRow = sqlite3WhereOutputRowCount(pWInfo);
5523 }
5524 if( sDistinct.isTnct && sqlite3WhereIsDistinct(pWInfo) ){
5525 sDistinct.eTnctType = sqlite3WhereIsDistinct(pWInfo);
5526 }
5527 if( sSort.pOrderBy ){
5528 sSort.nOBSat = sqlite3WhereIsOrdered(pWInfo);
5529 sSort.bOrderedInnerLoop = sqlite3WhereOrderedInnerLoop(pWInfo);
5530 if( sSort.nOBSat==sSort.pOrderBy->nExpr ){
5531 sSort.pOrderBy = 0;
5532 }
5533 }
5534
5535 /* If sorting index that was created by a prior OP_OpenEphemeral
5536 ** instruction ended up not being needed, then change the OP_OpenEphemeral
5537 ** into an OP_Noop.
5538 */
5539 if( sSort.addrSortIndex>=0 && sSort.pOrderBy==0 ){
5540 sqlite3VdbeChangeToNoop(v, sSort.addrSortIndex);
5541 }
5542
5543 /* Use the standard inner loop. */
5544 selectInnerLoop(pParse, p, pEList, -1, &sSort, &sDistinct, pDest,
5545 sqlite3WhereContinueLabel(pWInfo),
5546 sqlite3WhereBreakLabel(pWInfo));
5547
5548 /* End the database scan loop.
5549 */
5550 sqlite3WhereEnd(pWInfo);
5551 }else{
5552 /* This case when there exist aggregate functions or a GROUP BY clause
5553 ** or both */
5554 NameContext sNC; /* Name context for processing aggregate information */
5555 int iAMem; /* First Mem address for storing current GROUP BY */
5556 int iBMem; /* First Mem address for previous GROUP BY */
5557 int iUseFlag; /* Mem address holding flag indicating that at least
5558 ** one row of the input to the aggregator has been
5559 ** processed */
5560 int iAbortFlag; /* Mem address which causes query abort if positive */
5561 int groupBySort; /* Rows come from source in GROUP BY order */
5562 int addrEnd; /* End of processing for this SELECT */
5563 int sortPTab = 0; /* Pseudotable used to decode sorting results */
5564 int sortOut = 0; /* Output register from the sorter */
5565 int orderByGrp = 0; /* True if the GROUP BY and ORDER BY are the same */
5566
5567 /* Remove any and all aliases between the result set and the
5568 ** GROUP BY clause.
5569 */
5570 if( pGroupBy ){
5571 int k; /* Loop counter */
5572 struct ExprList_item *pItem; /* For looping over expression in a list */
5573
5574 for(k=p->pEList->nExpr, pItem=p->pEList->a; k>0; k--, pItem++){
5575 pItem->u.x.iAlias = 0;
5576 }
5577 for(k=pGroupBy->nExpr, pItem=pGroupBy->a; k>0; k--, pItem++){
5578 pItem->u.x.iAlias = 0;
5579 }
5580 assert( 66==sqlite3LogEst(100) );
5581 if( p->nSelectRow>66 ) p->nSelectRow = 66;
5582 }else{
5583 assert( 0==sqlite3LogEst(1) );
5584 p->nSelectRow = 0;
5585 }
5586
5587 /* If there is both a GROUP BY and an ORDER BY clause and they are
5588 ** identical, then it may be possible to disable the ORDER BY clause
5589 ** on the grounds that the GROUP BY will cause elements to come out
5590 ** in the correct order. It also may not - the GROUP BY might use a
5591 ** database index that causes rows to be grouped together as required
5592 ** but not actually sorted. Either way, record the fact that the
5593 ** ORDER BY and GROUP BY clauses are the same by setting the orderByGrp
5594 ** variable. */
5595 if( sqlite3ExprListCompare(pGroupBy, sSort.pOrderBy, -1)==0 ){
5596 orderByGrp = 1;
5597 }
5598
5599 /* Create a label to jump to when we want to abort the query */
5600 addrEnd = sqlite3VdbeMakeLabel(v);
5601
5602 /* Convert TK_COLUMN nodes into TK_AGG_COLUMN and make entries in
5603 ** sAggInfo for all TK_AGG_FUNCTION nodes in expressions of the
5604 ** SELECT statement.
5605 */
5606 memset(&sNC, 0, sizeof(sNC));
5607 sNC.pParse = pParse;
5608 sNC.pSrcList = pTabList;
5609 sNC.pAggInfo = &sAggInfo;
5610 sAggInfo.mnReg = pParse->nMem+1;
5611 sAggInfo.nSortingColumn = pGroupBy ? pGroupBy->nExpr : 0;
5612 sAggInfo.pGroupBy = pGroupBy;
5613 sqlite3ExprAnalyzeAggList(&sNC, pEList);
5614 sqlite3ExprAnalyzeAggList(&sNC, sSort.pOrderBy);
5615 if( pHaving ){
5616 if( pGroupBy ){
5617 assert( pWhere==p->pWhere );
5618 havingToWhere(pParse, pGroupBy, pHaving, &p->pWhere);
5619 pWhere = p->pWhere;
5620 }
5621 sqlite3ExprAnalyzeAggregates(&sNC, pHaving);
5622 }
5623 sAggInfo.nAccumulator = sAggInfo.nColumn;
5624 for(i=0; i<sAggInfo.nFunc; i++){
5625 assert( !ExprHasProperty(sAggInfo.aFunc[i].pExpr, EP_xIsSelect) );
5626 sNC.ncFlags |= NC_InAggFunc;
5627 sqlite3ExprAnalyzeAggList(&sNC, sAggInfo.aFunc[i].pExpr->x.pList);
5628 sNC.ncFlags &= ~NC_InAggFunc;
5629 }
5630 sAggInfo.mxReg = pParse->nMem;
5631 if( db->mallocFailed ) goto select_end;
5632
5633 /* Processing for aggregates with GROUP BY is very different and
5634 ** much more complex than aggregates without a GROUP BY.
5635 */
5636 if( pGroupBy ){
5637 KeyInfo *pKeyInfo; /* Keying information for the group by clause */
5638 int addr1; /* A-vs-B comparision jump */
5639 int addrOutputRow; /* Start of subroutine that outputs a result row */
5640 int regOutputRow; /* Return address register for output subroutine */
5641 int addrSetAbort; /* Set the abort flag and return */
5642 int addrTopOfLoop; /* Top of the input loop */
5643 int addrSortingIdx; /* The OP_OpenEphemeral for the sorting index */
5644 int addrReset; /* Subroutine for resetting the accumulator */
5645 int regReset; /* Return address register for reset subroutine */
5646
5647 /* If there is a GROUP BY clause we might need a sorting index to
5648 ** implement it. Allocate that sorting index now. If it turns out
5649 ** that we do not need it after all, the OP_SorterOpen instruction
5650 ** will be converted into a Noop.
5651 */
5652 sAggInfo.sortingIdx = pParse->nTab++;
5653 pKeyInfo = keyInfoFromExprList(pParse, pGroupBy, 0, sAggInfo.nColumn);
5654 addrSortingIdx = sqlite3VdbeAddOp4(v, OP_SorterOpen,
5655 sAggInfo.sortingIdx, sAggInfo.nSortingColumn,
5656 0, (char*)pKeyInfo, P4_KEYINFO);
5657
5658 /* Initialize memory locations used by GROUP BY aggregate processing
5659 */
5660 iUseFlag = ++pParse->nMem;
5661 iAbortFlag = ++pParse->nMem;
5662 regOutputRow = ++pParse->nMem;
5663 addrOutputRow = sqlite3VdbeMakeLabel(v);
5664 regReset = ++pParse->nMem;
5665 addrReset = sqlite3VdbeMakeLabel(v);
5666 iAMem = pParse->nMem + 1;
5667 pParse->nMem += pGroupBy->nExpr;
5668 iBMem = pParse->nMem + 1;
5669 pParse->nMem += pGroupBy->nExpr;
5670 sqlite3VdbeAddOp2(v, OP_Integer, 0, iAbortFlag);
5671 VdbeComment((v, "clear abort flag"));
5672 sqlite3VdbeAddOp2(v, OP_Integer, 0, iUseFlag);
5673 VdbeComment((v, "indicate accumulator empty"));
5674 sqlite3VdbeAddOp3(v, OP_Null, 0, iAMem, iAMem+pGroupBy->nExpr-1);
5675
5676 /* Begin a loop that will extract all source rows in GROUP BY order.
5677 ** This might involve two separate loops with an OP_Sort in between, or
5678 ** it might be a single loop that uses an index to extract information
5679 ** in the right order to begin with.
5680 */
5681 sqlite3VdbeAddOp2(v, OP_Gosub, regReset, addrReset);
5682 pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pGroupBy, 0,
5683 WHERE_GROUPBY | (orderByGrp ? WHERE_SORTBYGROUP : 0), 0
5684 );
5685 if( pWInfo==0 ) goto select_end;
5686 if( sqlite3WhereIsOrdered(pWInfo)==pGroupBy->nExpr ){
5687 /* The optimizer is able to deliver rows in group by order so
5688 ** we do not have to sort. The OP_OpenEphemeral table will be
5689 ** cancelled later because we still need to use the pKeyInfo
5690 */
5691 groupBySort = 0;
5692 }else{
5693 /* Rows are coming out in undetermined order. We have to push
5694 ** each row into a sorting index, terminate the first loop,
5695 ** then loop over the sorting index in order to get the output
5696 ** in sorted order
5697 */
5698 int regBase;
5699 int regRecord;
5700 int nCol;
5701 int nGroupBy;
5702
5703 explainTempTable(pParse,
5704 (sDistinct.isTnct && (p->selFlags&SF_Distinct)==0) ?
5705 "DISTINCT" : "GROUP BY");
5706
5707 groupBySort = 1;
5708 nGroupBy = pGroupBy->nExpr;
5709 nCol = nGroupBy;
5710 j = nGroupBy;
5711 for(i=0; i<sAggInfo.nColumn; i++){
5712 if( sAggInfo.aCol[i].iSorterColumn>=j ){
5713 nCol++;
5714 j++;
5715 }
5716 }
5717 regBase = sqlite3GetTempRange(pParse, nCol);
5718 sqlite3ExprCacheClear(pParse);
5719 sqlite3ExprCodeExprList(pParse, pGroupBy, regBase, 0, 0);
5720 j = nGroupBy;
5721 for(i=0; i<sAggInfo.nColumn; i++){
5722 struct AggInfo_col *pCol = &sAggInfo.aCol[i];
5723 if( pCol->iSorterColumn>=j ){
5724 int r1 = j + regBase;
5725 sqlite3ExprCodeGetColumnToReg(pParse,
5726 pCol->pTab, pCol->iColumn, pCol->iTable, r1);
5727 j++;
5728 }
5729 }
5730 regRecord = sqlite3GetTempReg(pParse);
5731 sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase, nCol, regRecord);
5732 sqlite3VdbeAddOp2(v, OP_SorterInsert, sAggInfo.sortingIdx, regRecord);
5733 sqlite3ReleaseTempReg(pParse, regRecord);
5734 sqlite3ReleaseTempRange(pParse, regBase, nCol);
5735 sqlite3WhereEnd(pWInfo);
5736 sAggInfo.sortingIdxPTab = sortPTab = pParse->nTab++;
5737 sortOut = sqlite3GetTempReg(pParse);
5738 sqlite3VdbeAddOp3(v, OP_OpenPseudo, sortPTab, sortOut, nCol);
5739 sqlite3VdbeAddOp2(v, OP_SorterSort, sAggInfo.sortingIdx, addrEnd);
5740 VdbeComment((v, "GROUP BY sort")); VdbeCoverage(v);
5741 sAggInfo.useSortingIdx = 1;
5742 sqlite3ExprCacheClear(pParse);
5743
5744 }
5745
5746 /* If the index or temporary table used by the GROUP BY sort
5747 ** will naturally deliver rows in the order required by the ORDER BY
5748 ** clause, cancel the ephemeral table open coded earlier.
5749 **
5750 ** This is an optimization - the correct answer should result regardless.
5751 ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER to
5752 ** disable this optimization for testing purposes. */
5753 if( orderByGrp && OptimizationEnabled(db, SQLITE_GroupByOrder)
5754 && (groupBySort || sqlite3WhereIsSorted(pWInfo))
5755 ){
5756 sSort.pOrderBy = 0;
5757 sqlite3VdbeChangeToNoop(v, sSort.addrSortIndex);
5758 }
5759
5760 /* Evaluate the current GROUP BY terms and store in b0, b1, b2...
5761 ** (b0 is memory location iBMem+0, b1 is iBMem+1, and so forth)
5762 ** Then compare the current GROUP BY terms against the GROUP BY terms
5763 ** from the previous row currently stored in a0, a1, a2...
5764 */
5765 addrTopOfLoop = sqlite3VdbeCurrentAddr(v);
5766 sqlite3ExprCacheClear(pParse);
5767 if( groupBySort ){
5768 sqlite3VdbeAddOp3(v, OP_SorterData, sAggInfo.sortingIdx,
5769 sortOut, sortPTab);
5770 }
5771 for(j=0; j<pGroupBy->nExpr; j++){
5772 if( groupBySort ){
5773 sqlite3VdbeAddOp3(v, OP_Column, sortPTab, j, iBMem+j);
5774 }else{
5775 sAggInfo.directMode = 1;
5776 sqlite3ExprCode(pParse, pGroupBy->a[j].pExpr, iBMem+j);
5777 }
5778 }
5779 sqlite3VdbeAddOp4(v, OP_Compare, iAMem, iBMem, pGroupBy->nExpr,
5780 (char*)sqlite3KeyInfoRef(pKeyInfo), P4_KEYINFO);
5781 addr1 = sqlite3VdbeCurrentAddr(v);
5782 sqlite3VdbeAddOp3(v, OP_Jump, addr1+1, 0, addr1+1); VdbeCoverage(v);
5783
5784 /* Generate code that runs whenever the GROUP BY changes.
5785 ** Changes in the GROUP BY are detected by the previous code
5786 ** block. If there were no changes, this block is skipped.
5787 **
5788 ** This code copies current group by terms in b0,b1,b2,...
5789 ** over to a0,a1,a2. It then calls the output subroutine
5790 ** and resets the aggregate accumulator registers in preparation
5791 ** for the next GROUP BY batch.
5792 */
5793 sqlite3ExprCodeMove(pParse, iBMem, iAMem, pGroupBy->nExpr);
5794 sqlite3VdbeAddOp2(v, OP_Gosub, regOutputRow, addrOutputRow);
5795 VdbeComment((v, "output one row"));
5796 sqlite3VdbeAddOp2(v, OP_IfPos, iAbortFlag, addrEnd); VdbeCoverage(v);
5797 VdbeComment((v, "check abort flag"));
5798 sqlite3VdbeAddOp2(v, OP_Gosub, regReset, addrReset);
5799 VdbeComment((v, "reset accumulator"));
5800
5801 /* Update the aggregate accumulators based on the content of
5802 ** the current row
5803 */
5804 sqlite3VdbeJumpHere(v, addr1);
5805 updateAccumulator(pParse, &sAggInfo);
5806 sqlite3VdbeAddOp2(v, OP_Integer, 1, iUseFlag);
5807 VdbeComment((v, "indicate data in accumulator"));
5808
5809 /* End of the loop
5810 */
5811 if( groupBySort ){
5812 sqlite3VdbeAddOp2(v, OP_SorterNext, sAggInfo.sortingIdx, addrTopOfLoop);
5813 VdbeCoverage(v);
5814 }else{
5815 sqlite3WhereEnd(pWInfo);
5816 sqlite3VdbeChangeToNoop(v, addrSortingIdx);
5817 }
5818
5819 /* Output the final row of result
5820 */
5821 sqlite3VdbeAddOp2(v, OP_Gosub, regOutputRow, addrOutputRow);
5822 VdbeComment((v, "output final row"));
5823
5824 /* Jump over the subroutines
5825 */
5826 sqlite3VdbeGoto(v, addrEnd);
5827
5828 /* Generate a subroutine that outputs a single row of the result
5829 ** set. This subroutine first looks at the iUseFlag. If iUseFlag
5830 ** is less than or equal to zero, the subroutine is a no-op. If
5831 ** the processing calls for the query to abort, this subroutine
5832 ** increments the iAbortFlag memory location before returning in
5833 ** order to signal the caller to abort.
5834 */
5835 addrSetAbort = sqlite3VdbeCurrentAddr(v);
5836 sqlite3VdbeAddOp2(v, OP_Integer, 1, iAbortFlag);
5837 VdbeComment((v, "set abort flag"));
5838 sqlite3VdbeAddOp1(v, OP_Return, regOutputRow);
5839 sqlite3VdbeResolveLabel(v, addrOutputRow);
5840 addrOutputRow = sqlite3VdbeCurrentAddr(v);
5841 sqlite3VdbeAddOp2(v, OP_IfPos, iUseFlag, addrOutputRow+2);
5842 VdbeCoverage(v);
5843 VdbeComment((v, "Groupby result generator entry point"));
5844 sqlite3VdbeAddOp1(v, OP_Return, regOutputRow);
5845 finalizeAggFunctions(pParse, &sAggInfo);
5846 sqlite3ExprIfFalse(pParse, pHaving, addrOutputRow+1, SQLITE_JUMPIFNULL);
5847 selectInnerLoop(pParse, p, p->pEList, -1, &sSort,
5848 &sDistinct, pDest,
5849 addrOutputRow+1, addrSetAbort);
5850 sqlite3VdbeAddOp1(v, OP_Return, regOutputRow);
5851 VdbeComment((v, "end groupby result generator"));
5852
5853 /* Generate a subroutine that will reset the group-by accumulator
5854 */
5855 sqlite3VdbeResolveLabel(v, addrReset);
5856 resetAccumulator(pParse, &sAggInfo);
5857 sqlite3VdbeAddOp1(v, OP_Return, regReset);
5858
5859 } /* endif pGroupBy. Begin aggregate queries without GROUP BY: */
5860 else {
5861 ExprList *pDel = 0;
5862 #ifndef SQLITE_OMIT_BTREECOUNT
5863 Table *pTab;
5864 if( (pTab = isSimpleCount(p, &sAggInfo))!=0 ){
5865 /* If isSimpleCount() returns a pointer to a Table structure, then
5866 ** the SQL statement is of the form:
5867 **
5868 ** SELECT count(*) FROM <tbl>
5869 **
5870 ** where the Table structure returned represents table <tbl>.
5871 **
5872 ** This statement is so common that it is optimized specially. The
5873 ** OP_Count instruction is executed either on the intkey table that
5874 ** contains the data for table <tbl> or on one of its indexes. It
5875 ** is better to execute the op on an index, as indexes are almost
5876 ** always spread across less pages than their corresponding tables.
5877 */
5878 const int iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
5879 const int iCsr = pParse->nTab++; /* Cursor to scan b-tree */
5880 Index *pIdx; /* Iterator variable */
5881 KeyInfo *pKeyInfo = 0; /* Keyinfo for scanned index */
5882 Index *pBest = 0; /* Best index found so far */
5883 int iRoot = pTab->tnum; /* Root page of scanned b-tree */
5884
5885 sqlite3CodeVerifySchema(pParse, iDb);
5886 sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
5887
5888 /* Search for the index that has the lowest scan cost.
5889 **
5890 ** (2011-04-15) Do not do a full scan of an unordered index.
5891 **
5892 ** (2013-10-03) Do not count the entries in a partial index.
5893 **
5894 ** In practice the KeyInfo structure will not be used. It is only
5895 ** passed to keep OP_OpenRead happy.
5896 */
5897 if( !HasRowid(pTab) ) pBest = sqlite3PrimaryKeyIndex(pTab);
5898 for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
5899 if( pIdx->bUnordered==0
5900 && pIdx->szIdxRow<pTab->szTabRow
5901 && pIdx->pPartIdxWhere==0
5902 && (!pBest || pIdx->szIdxRow<pBest->szIdxRow)
5903 ){
5904 pBest = pIdx;
5905 }
5906 }
5907 if( pBest ){
5908 iRoot = pBest->tnum;
5909 pKeyInfo = sqlite3KeyInfoOfIndex(pParse, pBest);
5910 }
5911
5912 /* Open a read-only cursor, execute the OP_Count, close the cursor. */
5913 sqlite3VdbeAddOp4Int(v, OP_OpenRead, iCsr, iRoot, iDb, 1);
5914 if( pKeyInfo ){
5915 sqlite3VdbeChangeP4(v, -1, (char *)pKeyInfo, P4_KEYINFO);
5916 }
5917 sqlite3VdbeAddOp2(v, OP_Count, iCsr, sAggInfo.aFunc[0].iMem);
5918 sqlite3VdbeAddOp1(v, OP_Close, iCsr);
5919 explainSimpleCount(pParse, pTab, pBest);
5920 }else
5921 #endif /* SQLITE_OMIT_BTREECOUNT */
5922 {
5923 /* Check if the query is of one of the following forms:
5924 **
5925 ** SELECT min(x) FROM ...
5926 ** SELECT max(x) FROM ...
5927 **
5928 ** If it is, then ask the code in where.c to attempt to sort results
5929 ** as if there was an "ORDER ON x" or "ORDER ON x DESC" clause.
5930 ** If where.c is able to produce results sorted in this order, then
5931 ** add vdbe code to break out of the processing loop after the
5932 ** first iteration (since the first iteration of the loop is
5933 ** guaranteed to operate on the row with the minimum or maximum
5934 ** value of x, the only row required).
5935 **
5936 ** A special flag must be passed to sqlite3WhereBegin() to slightly
5937 ** modify behavior as follows:
5938 **
5939 ** + If the query is a "SELECT min(x)", then the loop coded by
5940 ** where.c should not iterate over any values with a NULL value
5941 ** for x.
5942 **
5943 ** + The optimizer code in where.c (the thing that decides which
5944 ** index or indices to use) should place a different priority on
5945 ** satisfying the 'ORDER BY' clause than it does in other cases.
5946 ** Refer to code and comments in where.c for details.
5947 */
5948 ExprList *pMinMax = 0;
5949 u8 flag = WHERE_ORDERBY_NORMAL;
5950
5951 assert( p->pGroupBy==0 );
5952 assert( flag==0 );
5953 if( p->pHaving==0 ){
5954 flag = minMaxQuery(&sAggInfo, &pMinMax);
5955 }
5956 assert( flag==0 || (pMinMax!=0 && pMinMax->nExpr==1) );
5957
5958 if( flag ){
5959 pMinMax = sqlite3ExprListDup(db, pMinMax, 0);
5960 pDel = pMinMax;
5961 assert( db->mallocFailed || pMinMax!=0 );
5962 if( !db->mallocFailed ){
5963 pMinMax->a[0].sortOrder = flag!=WHERE_ORDERBY_MIN ?1:0;
5964 pMinMax->a[0].pExpr->op = TK_COLUMN;
5965 }
5966 }
5967
5968 /* This case runs if the aggregate has no GROUP BY clause. The
5969 ** processing is much simpler since there is only a single row
5970 ** of output.
5971 */
5972 resetAccumulator(pParse, &sAggInfo);
5973 pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pMinMax, 0,flag,0);
5974 if( pWInfo==0 ){
5975 sqlite3ExprListDelete(db, pDel);
5976 goto select_end;
5977 }
5978 updateAccumulator(pParse, &sAggInfo);
5979 assert( pMinMax==0 || pMinMax->nExpr==1 );
5980 if( sqlite3WhereIsOrdered(pWInfo)>0 ){
5981 sqlite3VdbeGoto(v, sqlite3WhereBreakLabel(pWInfo));
5982 VdbeComment((v, "%s() by index",
5983 (flag==WHERE_ORDERBY_MIN?"min":"max")));
5984 }
5985 sqlite3WhereEnd(pWInfo);
5986 finalizeAggFunctions(pParse, &sAggInfo);
5987 }
5988
5989 sSort.pOrderBy = 0;
5990 sqlite3ExprIfFalse(pParse, pHaving, addrEnd, SQLITE_JUMPIFNULL);
5991 selectInnerLoop(pParse, p, p->pEList, -1, 0, 0,
5992 pDest, addrEnd, addrEnd);
5993 sqlite3ExprListDelete(db, pDel);
5994 }
5995 sqlite3VdbeResolveLabel(v, addrEnd);
5996
5997 } /* endif aggregate query */
5998
5999 if( sDistinct.eTnctType==WHERE_DISTINCT_UNORDERED ){
6000 explainTempTable(pParse, "DISTINCT");
6001 }
6002
6003 /* If there is an ORDER BY clause, then we need to sort the results
6004 ** and send them to the callback one by one.
6005 */
6006 if( sSort.pOrderBy ){
6007 explainTempTable(pParse,
6008 sSort.nOBSat>0 ? "RIGHT PART OF ORDER BY":"ORDER BY");
6009 generateSortTail(pParse, p, &sSort, pEList->nExpr, pDest);
6010 }
6011
6012 /* Jump here to skip this query
6013 */
6014 sqlite3VdbeResolveLabel(v, iEnd);
6015
6016 /* The SELECT has been coded. If there is an error in the Parse structure,
6017 ** set the return code to 1. Otherwise 0. */
6018 rc = (pParse->nErr>0);
6019
6020 /* Control jumps to here if an error is encountered above, or upon
6021 ** successful coding of the SELECT.
6022 */
6023 select_end:
6024 explainSetInteger(pParse->iSelectId, iRestoreSelectId);
6025
6026 sqlite3DbFree(db, sAggInfo.aCol);
6027 sqlite3DbFree(db, sAggInfo.aFunc);
6028 #if SELECTTRACE_ENABLED
6029 SELECTTRACE(1,pParse,p,("end processing\n"));
6030 pParse->nSelectIndent--;
6031 #endif
6032 return rc;
6033 }
6034