4 ** The author disclaims copyright to this source code. In place of
5 ** a legal notice, here is a blessing:
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.
11 *************************************************************************
12 ** This file contains C code routines that are called by the parser
13 ** to handle SELECT statements in SQLite.
15 #include "sqliteInt.h"
18 ** Trace output macros
20 #if SELECTTRACE_ENABLED
21 /***/ int sqlite3SelectTrace
= 0;
22 # define SELECTTRACE(K,P,S,X) \
23 if(sqlite3SelectTrace&(K)) \
24 sqlite3DebugPrintf("%s/%p: ",(S)->zSelName,(S)),\
27 # define SELECTTRACE(K,P,S,X)
32 ** An instance of the following object is used to record information about
33 ** how to process the DISTINCT keyword, to simplify passing that information
34 ** into the selectInnerLoop() routine.
36 typedef struct DistinctCtx DistinctCtx
;
38 u8 isTnct
; /* True if the DISTINCT keyword is present */
39 u8 eTnctType
; /* One of the WHERE_DISTINCT_* operators */
40 int tabTnct
; /* Ephemeral table used for DISTINCT processing */
41 int addrTnct
; /* Address of OP_OpenEphemeral opcode for tabTnct */
45 ** An instance of the following object is used to record information about
46 ** the ORDER BY (or GROUP BY) clause of query is being coded.
48 typedef struct SortCtx SortCtx
;
50 ExprList
*pOrderBy
; /* The ORDER BY (or GROUP BY clause) */
51 int nOBSat
; /* Number of ORDER BY terms satisfied by indices */
52 int iECursor
; /* Cursor number for the sorter */
53 int regReturn
; /* Register holding block-output return address */
54 int labelBkOut
; /* Start label for the block-output subroutine */
55 int addrSortIndex
; /* Address of the OP_SorterOpen or OP_OpenEphemeral */
56 int labelDone
; /* Jump here when done, ex: LIMIT reached */
57 u8 sortFlags
; /* Zero or more SORTFLAG_* bits */
58 u8 bOrderedInnerLoop
; /* ORDER BY correctly sorts the inner loop */
60 #define SORTFLAG_UseSorter 0x01 /* Use SorterOpen instead of OpenEphemeral */
63 ** Delete all the content of a Select structure. Deallocate the structure
64 ** itself only if bFree is true.
66 static void clearSelect(sqlite3
*db
, Select
*p
, int bFree
){
68 Select
*pPrior
= p
->pPrior
;
69 sqlite3ExprListDelete(db
, p
->pEList
);
70 sqlite3SrcListDelete(db
, p
->pSrc
);
71 sqlite3ExprDelete(db
, p
->pWhere
);
72 sqlite3ExprListDelete(db
, p
->pGroupBy
);
73 sqlite3ExprDelete(db
, p
->pHaving
);
74 sqlite3ExprListDelete(db
, p
->pOrderBy
);
75 sqlite3ExprDelete(db
, p
->pLimit
);
76 if( OK_IF_ALWAYS_TRUE(p
->pWith
) ) sqlite3WithDelete(db
, p
->pWith
);
77 if( bFree
) sqlite3DbFreeNN(db
, p
);
84 ** Initialize a SelectDest structure.
86 void sqlite3SelectDestInit(SelectDest
*pDest
, int eDest
, int iParm
){
87 pDest
->eDest
= (u8
)eDest
;
88 pDest
->iSDParm
= iParm
;
96 ** Allocate a new Select structure and return a pointer to that
99 Select
*sqlite3SelectNew(
100 Parse
*pParse
, /* Parsing context */
101 ExprList
*pEList
, /* which columns to include in the result */
102 SrcList
*pSrc
, /* the FROM clause -- which tables to scan */
103 Expr
*pWhere
, /* the WHERE clause */
104 ExprList
*pGroupBy
, /* the GROUP BY clause */
105 Expr
*pHaving
, /* the HAVING clause */
106 ExprList
*pOrderBy
, /* the ORDER BY clause */
107 u32 selFlags
, /* Flag parameters, such as SF_Distinct */
108 Expr
*pLimit
/* LIMIT value. NULL means not used */
112 pNew
= sqlite3DbMallocRawNN(pParse
->db
, sizeof(*pNew
) );
114 assert( pParse
->db
->mallocFailed
);
118 pEList
= sqlite3ExprListAppend(pParse
, 0,
119 sqlite3Expr(pParse
->db
,TK_ASTERISK
,0));
121 pNew
->pEList
= pEList
;
122 pNew
->op
= TK_SELECT
;
123 pNew
->selFlags
= selFlags
;
126 #if SELECTTRACE_ENABLED
127 pNew
->zSelName
[0] = 0;
129 pNew
->addrOpenEphm
[0] = -1;
130 pNew
->addrOpenEphm
[1] = -1;
131 pNew
->nSelectRow
= 0;
132 if( pSrc
==0 ) pSrc
= sqlite3DbMallocZero(pParse
->db
, sizeof(*pSrc
));
134 pNew
->pWhere
= pWhere
;
135 pNew
->pGroupBy
= pGroupBy
;
136 pNew
->pHaving
= pHaving
;
137 pNew
->pOrderBy
= pOrderBy
;
140 pNew
->pLimit
= pLimit
;
142 if( pParse
->db
->mallocFailed
) {
143 clearSelect(pParse
->db
, pNew
, pNew
!=&standin
);
146 assert( pNew
->pSrc
!=0 || pParse
->nErr
>0 );
148 assert( pNew
!=&standin
);
152 #if SELECTTRACE_ENABLED
154 ** Set the name of a Select object
156 void sqlite3SelectSetName(Select
*p
, const char *zName
){
158 sqlite3_snprintf(sizeof(p
->zSelName
), p
->zSelName
, "%s", zName
);
165 ** Delete the given Select structure and all of its substructures.
167 void sqlite3SelectDelete(sqlite3
*db
, Select
*p
){
168 if( OK_IF_ALWAYS_TRUE(p
) ) clearSelect(db
, p
, 1);
172 ** Return a pointer to the right-most SELECT statement in a compound.
174 static Select
*findRightmost(Select
*p
){
175 while( p
->pNext
) p
= p
->pNext
;
180 ** Given 1 to 3 identifiers preceding the JOIN keyword, determine the
181 ** type of join. Return an integer constant that expresses that type
182 ** in terms of the following bit values:
191 ** A full outer join is the combination of JT_LEFT and JT_RIGHT.
193 ** If an illegal or unsupported join type is seen, then still return
194 ** a join type, but put an error in the pParse structure.
196 int sqlite3JoinType(Parse
*pParse
, Token
*pA
, Token
*pB
, Token
*pC
){
200 /* 0123456789 123456789 123456789 123 */
201 static const char zKeyText
[] = "naturaleftouterightfullinnercross";
202 static const struct {
203 u8 i
; /* Beginning of keyword text in zKeyText[] */
204 u8 nChar
; /* Length of the keyword in characters */
205 u8 code
; /* Join type mask */
207 /* natural */ { 0, 7, JT_NATURAL
},
208 /* left */ { 6, 4, JT_LEFT
|JT_OUTER
},
209 /* outer */ { 10, 5, JT_OUTER
},
210 /* right */ { 14, 5, JT_RIGHT
|JT_OUTER
},
211 /* full */ { 19, 4, JT_LEFT
|JT_RIGHT
|JT_OUTER
},
212 /* inner */ { 23, 5, JT_INNER
},
213 /* cross */ { 28, 5, JT_INNER
|JT_CROSS
},
219 for(i
=0; i
<3 && apAll
[i
]; i
++){
221 for(j
=0; j
<ArraySize(aKeyword
); j
++){
222 if( p
->n
==aKeyword
[j
].nChar
223 && sqlite3StrNICmp((char*)p
->z
, &zKeyText
[aKeyword
[j
].i
], p
->n
)==0 ){
224 jointype
|= aKeyword
[j
].code
;
228 testcase( j
==0 || j
==1 || j
==2 || j
==3 || j
==4 || j
==5 || j
==6 );
229 if( j
>=ArraySize(aKeyword
) ){
230 jointype
|= JT_ERROR
;
235 (jointype
& (JT_INNER
|JT_OUTER
))==(JT_INNER
|JT_OUTER
) ||
236 (jointype
& JT_ERROR
)!=0
238 const char *zSp
= " ";
240 if( pC
==0 ){ zSp
++; }
241 sqlite3ErrorMsg(pParse
, "unknown or unsupported join type: "
242 "%T %T%s%T", pA
, pB
, zSp
, pC
);
244 }else if( (jointype
& JT_OUTER
)!=0
245 && (jointype
& (JT_LEFT
|JT_RIGHT
))!=JT_LEFT
){
246 sqlite3ErrorMsg(pParse
,
247 "RIGHT and FULL OUTER JOINs are not currently supported");
254 ** Return the index of a column in a table. Return -1 if the column
255 ** is not contained in the table.
257 static int columnIndex(Table
*pTab
, const char *zCol
){
259 for(i
=0; i
<pTab
->nCol
; i
++){
260 if( sqlite3StrICmp(pTab
->aCol
[i
].zName
, zCol
)==0 ) return i
;
266 ** Search the first N tables in pSrc, from left to right, looking for a
267 ** table that has a column named zCol.
269 ** When found, set *piTab and *piCol to the table index and column index
270 ** of the matching column and return TRUE.
272 ** If not found, return FALSE.
274 static int tableAndColumnIndex(
275 SrcList
*pSrc
, /* Array of tables to search */
276 int N
, /* Number of tables in pSrc->a[] to search */
277 const char *zCol
, /* Name of the column we are looking for */
278 int *piTab
, /* Write index of pSrc->a[] here */
279 int *piCol
/* Write index of pSrc->a[*piTab].pTab->aCol[] here */
281 int i
; /* For looping over tables in pSrc */
282 int iCol
; /* Index of column matching zCol */
284 assert( (piTab
==0)==(piCol
==0) ); /* Both or neither are NULL */
286 iCol
= columnIndex(pSrc
->a
[i
].pTab
, zCol
);
299 ** This function is used to add terms implied by JOIN syntax to the
300 ** WHERE clause expression of a SELECT statement. The new term, which
301 ** is ANDed with the existing WHERE clause, is of the form:
303 ** (tab1.col1 = tab2.col2)
305 ** where tab1 is the iSrc'th table in SrcList pSrc and tab2 is the
306 ** (iSrc+1)'th. Column col1 is column iColLeft of tab1, and col2 is
307 ** column iColRight of tab2.
309 static void addWhereTerm(
310 Parse
*pParse
, /* Parsing context */
311 SrcList
*pSrc
, /* List of tables in FROM clause */
312 int iLeft
, /* Index of first table to join in pSrc */
313 int iColLeft
, /* Index of column in first table */
314 int iRight
, /* Index of second table in pSrc */
315 int iColRight
, /* Index of column in second table */
316 int isOuterJoin
, /* True if this is an OUTER join */
317 Expr
**ppWhere
/* IN/OUT: The WHERE clause to add to */
319 sqlite3
*db
= pParse
->db
;
324 assert( iLeft
<iRight
);
325 assert( pSrc
->nSrc
>iRight
);
326 assert( pSrc
->a
[iLeft
].pTab
);
327 assert( pSrc
->a
[iRight
].pTab
);
329 pE1
= sqlite3CreateColumnExpr(db
, pSrc
, iLeft
, iColLeft
);
330 pE2
= sqlite3CreateColumnExpr(db
, pSrc
, iRight
, iColRight
);
332 pEq
= sqlite3PExpr(pParse
, TK_EQ
, pE1
, pE2
);
333 if( pEq
&& isOuterJoin
){
334 ExprSetProperty(pEq
, EP_FromJoin
);
335 assert( !ExprHasProperty(pEq
, EP_TokenOnly
|EP_Reduced
) );
336 ExprSetVVAProperty(pEq
, EP_NoReduce
);
337 pEq
->iRightJoinTable
= (i16
)pE2
->iTable
;
339 *ppWhere
= sqlite3ExprAnd(db
, *ppWhere
, pEq
);
343 ** Set the EP_FromJoin property on all terms of the given expression.
344 ** And set the Expr.iRightJoinTable to iTable for every term in the
347 ** The EP_FromJoin property is used on terms of an expression to tell
348 ** the LEFT OUTER JOIN processing logic that this term is part of the
349 ** join restriction specified in the ON or USING clause and not a part
350 ** of the more general WHERE clause. These terms are moved over to the
351 ** WHERE clause during join processing but we need to remember that they
352 ** originated in the ON or USING clause.
354 ** The Expr.iRightJoinTable tells the WHERE clause processing that the
355 ** expression depends on table iRightJoinTable even if that table is not
356 ** explicitly mentioned in the expression. That information is needed
357 ** for cases like this:
359 ** SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.b AND t1.x=5
361 ** The where clause needs to defer the handling of the t1.x=5
362 ** term until after the t2 loop of the join. In that way, a
363 ** NULL t2 row will be inserted whenever t1.x!=5. If we do not
364 ** defer the handling of t1.x=5, it will be processed immediately
365 ** after the t1 loop and rows with t1.x!=5 will never appear in
366 ** the output, which is incorrect.
368 static void setJoinExpr(Expr
*p
, int iTable
){
370 ExprSetProperty(p
, EP_FromJoin
);
371 assert( !ExprHasProperty(p
, EP_TokenOnly
|EP_Reduced
) );
372 ExprSetVVAProperty(p
, EP_NoReduce
);
373 p
->iRightJoinTable
= (i16
)iTable
;
374 if( p
->op
==TK_FUNCTION
&& p
->x
.pList
){
376 for(i
=0; i
<p
->x
.pList
->nExpr
; i
++){
377 setJoinExpr(p
->x
.pList
->a
[i
].pExpr
, iTable
);
380 setJoinExpr(p
->pLeft
, iTable
);
385 /* Undo the work of setJoinExpr(). In the expression tree p, convert every
386 ** term that is marked with EP_FromJoin and iRightJoinTable==iTable into
387 ** an ordinary term that omits the EP_FromJoin mark.
389 ** This happens when a LEFT JOIN is simplified into an ordinary JOIN.
391 static void unsetJoinExpr(Expr
*p
, int iTable
){
393 if( ExprHasProperty(p
, EP_FromJoin
)
394 && (iTable
<0 || p
->iRightJoinTable
==iTable
) ){
395 ExprClearProperty(p
, EP_FromJoin
);
397 if( p
->op
==TK_FUNCTION
&& p
->x
.pList
){
399 for(i
=0; i
<p
->x
.pList
->nExpr
; i
++){
400 unsetJoinExpr(p
->x
.pList
->a
[i
].pExpr
, iTable
);
403 unsetJoinExpr(p
->pLeft
, iTable
);
409 ** This routine processes the join information for a SELECT statement.
410 ** ON and USING clauses are converted into extra terms of the WHERE clause.
411 ** NATURAL joins also create extra WHERE clause terms.
413 ** The terms of a FROM clause are contained in the Select.pSrc structure.
414 ** The left most table is the first entry in Select.pSrc. The right-most
415 ** table is the last entry. The join operator is held in the entry to
416 ** the left. Thus entry 0 contains the join operator for the join between
417 ** entries 0 and 1. Any ON or USING clauses associated with the join are
418 ** also attached to the left entry.
420 ** This routine returns the number of errors encountered.
422 static int sqliteProcessJoin(Parse
*pParse
, Select
*p
){
423 SrcList
*pSrc
; /* All tables in the FROM clause */
424 int i
, j
; /* Loop counters */
425 struct SrcList_item
*pLeft
; /* Left table being joined */
426 struct SrcList_item
*pRight
; /* Right table being joined */
431 for(i
=0; i
<pSrc
->nSrc
-1; i
++, pRight
++, pLeft
++){
432 Table
*pRightTab
= pRight
->pTab
;
435 if( NEVER(pLeft
->pTab
==0 || pRightTab
==0) ) continue;
436 isOuter
= (pRight
->fg
.jointype
& JT_OUTER
)!=0;
438 /* When the NATURAL keyword is present, add WHERE clause terms for
439 ** every column that the two tables have in common.
441 if( pRight
->fg
.jointype
& JT_NATURAL
){
442 if( pRight
->pOn
|| pRight
->pUsing
){
443 sqlite3ErrorMsg(pParse
, "a NATURAL join may not have "
444 "an ON or USING clause", 0);
447 for(j
=0; j
<pRightTab
->nCol
; j
++){
448 char *zName
; /* Name of column in the right table */
449 int iLeft
; /* Matching left table */
450 int iLeftCol
; /* Matching column in the left table */
452 zName
= pRightTab
->aCol
[j
].zName
;
453 if( tableAndColumnIndex(pSrc
, i
+1, zName
, &iLeft
, &iLeftCol
) ){
454 addWhereTerm(pParse
, pSrc
, iLeft
, iLeftCol
, i
+1, j
,
455 isOuter
, &p
->pWhere
);
460 /* Disallow both ON and USING clauses in the same join
462 if( pRight
->pOn
&& pRight
->pUsing
){
463 sqlite3ErrorMsg(pParse
, "cannot have both ON and USING "
464 "clauses in the same join");
468 /* Add the ON clause to the end of the WHERE clause, connected by
472 if( isOuter
) setJoinExpr(pRight
->pOn
, pRight
->iCursor
);
473 p
->pWhere
= sqlite3ExprAnd(pParse
->db
, p
->pWhere
, pRight
->pOn
);
477 /* Create extra terms on the WHERE clause for each column named
478 ** in the USING clause. Example: If the two tables to be joined are
479 ** A and B and the USING clause names X, Y, and Z, then add this
480 ** to the WHERE clause: A.X=B.X AND A.Y=B.Y AND A.Z=B.Z
481 ** Report an error if any column mentioned in the USING clause is
482 ** not contained in both tables to be joined.
484 if( pRight
->pUsing
){
485 IdList
*pList
= pRight
->pUsing
;
486 for(j
=0; j
<pList
->nId
; j
++){
487 char *zName
; /* Name of the term in the USING clause */
488 int iLeft
; /* Table on the left with matching column name */
489 int iLeftCol
; /* Column number of matching column on the left */
490 int iRightCol
; /* Column number of matching column on the right */
492 zName
= pList
->a
[j
].zName
;
493 iRightCol
= columnIndex(pRightTab
, zName
);
495 || !tableAndColumnIndex(pSrc
, i
+1, zName
, &iLeft
, &iLeftCol
)
497 sqlite3ErrorMsg(pParse
, "cannot join using column %s - column "
498 "not present in both tables", zName
);
501 addWhereTerm(pParse
, pSrc
, iLeft
, iLeftCol
, i
+1, iRightCol
,
502 isOuter
, &p
->pWhere
);
509 /* Forward reference */
510 static KeyInfo
*keyInfoFromExprList(
511 Parse
*pParse
, /* Parsing context */
512 ExprList
*pList
, /* Form the KeyInfo object from this ExprList */
513 int iStart
, /* Begin with this column of pList */
514 int nExtra
/* Add this many extra columns to the end */
518 ** Generate code that will push the record in registers regData
519 ** through regData+nData-1 onto the sorter.
521 static void pushOntoSorter(
522 Parse
*pParse
, /* Parser context */
523 SortCtx
*pSort
, /* Information about the ORDER BY clause */
524 Select
*pSelect
, /* The whole SELECT statement */
525 int regData
, /* First register holding data to be sorted */
526 int regOrigData
, /* First register holding data before packing */
527 int nData
, /* Number of elements in the data array */
528 int nPrefixReg
/* No. of reg prior to regData available for use */
530 Vdbe
*v
= pParse
->pVdbe
; /* Stmt under construction */
531 int bSeq
= ((pSort
->sortFlags
& SORTFLAG_UseSorter
)==0);
532 int nExpr
= pSort
->pOrderBy
->nExpr
; /* No. of ORDER BY terms */
533 int nBase
= nExpr
+ bSeq
+ nData
; /* Fields in sorter record */
534 int regBase
; /* Regs for sorter record */
535 int regRecord
= ++pParse
->nMem
; /* Assembled sorter record */
536 int nOBSat
= pSort
->nOBSat
; /* ORDER BY terms to skip */
537 int op
; /* Opcode to add sorter record to sorter */
538 int iLimit
; /* LIMIT counter */
540 assert( bSeq
==0 || bSeq
==1 );
541 assert( nData
==1 || regData
==regOrigData
|| regOrigData
==0 );
543 assert( nPrefixReg
==nExpr
+bSeq
);
544 regBase
= regData
- nExpr
- bSeq
;
546 regBase
= pParse
->nMem
+ 1;
547 pParse
->nMem
+= nBase
;
549 assert( pSelect
->iOffset
==0 || pSelect
->iLimit
!=0 );
550 iLimit
= pSelect
->iOffset
? pSelect
->iOffset
+1 : pSelect
->iLimit
;
551 pSort
->labelDone
= sqlite3VdbeMakeLabel(v
);
552 sqlite3ExprCodeExprList(pParse
, pSort
->pOrderBy
, regBase
, regOrigData
,
553 SQLITE_ECEL_DUP
| (regOrigData
? SQLITE_ECEL_REF
: 0));
555 sqlite3VdbeAddOp2(v
, OP_Sequence
, pSort
->iECursor
, regBase
+nExpr
);
557 if( nPrefixReg
==0 && nData
>0 ){
558 sqlite3ExprCodeMove(pParse
, regData
, regBase
+nExpr
+bSeq
, nData
);
560 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, regBase
+nOBSat
, nBase
-nOBSat
, regRecord
);
562 int regPrevKey
; /* The first nOBSat columns of the previous row */
563 int addrFirst
; /* Address of the OP_IfNot opcode */
564 int addrJmp
; /* Address of the OP_Jump opcode */
565 VdbeOp
*pOp
; /* Opcode that opens the sorter */
566 int nKey
; /* Number of sorting key columns, including OP_Sequence */
567 KeyInfo
*pKI
; /* Original KeyInfo on the sorter table */
569 regPrevKey
= pParse
->nMem
+1;
570 pParse
->nMem
+= pSort
->nOBSat
;
571 nKey
= nExpr
- pSort
->nOBSat
+ bSeq
;
573 addrFirst
= sqlite3VdbeAddOp1(v
, OP_IfNot
, regBase
+nExpr
);
575 addrFirst
= sqlite3VdbeAddOp1(v
, OP_SequenceTest
, pSort
->iECursor
);
578 sqlite3VdbeAddOp3(v
, OP_Compare
, regPrevKey
, regBase
, pSort
->nOBSat
);
579 pOp
= sqlite3VdbeGetOp(v
, pSort
->addrSortIndex
);
580 if( pParse
->db
->mallocFailed
) return;
581 pOp
->p2
= nKey
+ nData
;
582 pKI
= pOp
->p4
.pKeyInfo
;
583 memset(pKI
->aSortOrder
, 0, pKI
->nKeyField
); /* Makes OP_Jump testable */
584 sqlite3VdbeChangeP4(v
, -1, (char*)pKI
, P4_KEYINFO
);
585 testcase( pKI
->nAllField
> pKI
->nKeyField
+2 );
586 pOp
->p4
.pKeyInfo
= keyInfoFromExprList(pParse
, pSort
->pOrderBy
, nOBSat
,
587 pKI
->nAllField
-pKI
->nKeyField
-1);
588 addrJmp
= sqlite3VdbeCurrentAddr(v
);
589 sqlite3VdbeAddOp3(v
, OP_Jump
, addrJmp
+1, 0, addrJmp
+1); VdbeCoverage(v
);
590 pSort
->labelBkOut
= sqlite3VdbeMakeLabel(v
);
591 pSort
->regReturn
= ++pParse
->nMem
;
592 sqlite3VdbeAddOp2(v
, OP_Gosub
, pSort
->regReturn
, pSort
->labelBkOut
);
593 sqlite3VdbeAddOp1(v
, OP_ResetSorter
, pSort
->iECursor
);
595 sqlite3VdbeAddOp2(v
, OP_IfNot
, iLimit
, pSort
->labelDone
);
598 sqlite3VdbeJumpHere(v
, addrFirst
);
599 sqlite3ExprCodeMove(pParse
, regBase
, regPrevKey
, pSort
->nOBSat
);
600 sqlite3VdbeJumpHere(v
, addrJmp
);
602 if( pSort
->sortFlags
& SORTFLAG_UseSorter
){
603 op
= OP_SorterInsert
;
607 sqlite3VdbeAddOp4Int(v
, op
, pSort
->iECursor
, regRecord
,
608 regBase
+nOBSat
, nBase
-nOBSat
);
612 /* Fill the sorter until it contains LIMIT+OFFSET entries. (The iLimit
613 ** register is initialized with value of LIMIT+OFFSET.) After the sorter
614 ** fills up, delete the least entry in the sorter after each insert.
615 ** Thus we never hold more than the LIMIT+OFFSET rows in memory at once */
616 addr
= sqlite3VdbeAddOp1(v
, OP_IfNotZero
, iLimit
); VdbeCoverage(v
);
617 sqlite3VdbeAddOp1(v
, OP_Last
, pSort
->iECursor
);
618 if( pSort
->bOrderedInnerLoop
){
620 sqlite3VdbeAddOp3(v
, OP_Column
, pSort
->iECursor
, nExpr
, r1
);
621 VdbeComment((v
, "seq"));
623 sqlite3VdbeAddOp1(v
, OP_Delete
, pSort
->iECursor
);
624 if( pSort
->bOrderedInnerLoop
){
625 /* If the inner loop is driven by an index such that values from
626 ** the same iteration of the inner loop are in sorted order, then
627 ** immediately jump to the next iteration of an inner loop if the
628 ** entry from the current iteration does not fit into the top
629 ** LIMIT+OFFSET entries of the sorter. */
630 int iBrk
= sqlite3VdbeCurrentAddr(v
) + 2;
631 sqlite3VdbeAddOp3(v
, OP_Eq
, regBase
+nExpr
, iBrk
, r1
);
632 sqlite3VdbeChangeP5(v
, SQLITE_NULLEQ
);
635 sqlite3VdbeJumpHere(v
, addr
);
640 ** Add code to implement the OFFSET
642 static void codeOffset(
643 Vdbe
*v
, /* Generate code into this VM */
644 int iOffset
, /* Register holding the offset counter */
645 int iContinue
/* Jump here to skip the current record */
648 sqlite3VdbeAddOp3(v
, OP_IfPos
, iOffset
, iContinue
, 1); VdbeCoverage(v
);
649 VdbeComment((v
, "OFFSET"));
654 ** Add code that will check to make sure the N registers starting at iMem
655 ** form a distinct entry. iTab is a sorting index that holds previously
656 ** seen combinations of the N values. A new entry is made in iTab
657 ** if the current N values are new.
659 ** A jump to addrRepeat is made and the N+1 values are popped from the
660 ** stack if the top N elements are not distinct.
662 static void codeDistinct(
663 Parse
*pParse
, /* Parsing and code generating context */
664 int iTab
, /* A sorting index used to test for distinctness */
665 int addrRepeat
, /* Jump to here if not distinct */
666 int N
, /* Number of elements */
667 int iMem
/* First element */
673 r1
= sqlite3GetTempReg(pParse
);
674 sqlite3VdbeAddOp4Int(v
, OP_Found
, iTab
, addrRepeat
, iMem
, N
); VdbeCoverage(v
);
675 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, iMem
, N
, r1
);
676 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, iTab
, r1
, iMem
, N
);
677 sqlite3VdbeChangeP5(v
, OPFLAG_USESEEKRESULT
);
678 sqlite3ReleaseTempReg(pParse
, r1
);
682 ** This routine generates the code for the inside of the inner loop
685 ** If srcTab is negative, then the p->pEList expressions
686 ** are evaluated in order to get the data for this row. If srcTab is
687 ** zero or more, then data is pulled from srcTab and p->pEList is used only
688 ** to get the number of columns and the collation sequence for each column.
690 static void selectInnerLoop(
691 Parse
*pParse
, /* The parser context */
692 Select
*p
, /* The complete select statement being coded */
693 int srcTab
, /* Pull data from this table if non-negative */
694 SortCtx
*pSort
, /* If not NULL, info on how to process ORDER BY */
695 DistinctCtx
*pDistinct
, /* If not NULL, info on how to process DISTINCT */
696 SelectDest
*pDest
, /* How to dispose of the results */
697 int iContinue
, /* Jump here to continue with next row */
698 int iBreak
/* Jump here to break out of the inner loop */
700 Vdbe
*v
= pParse
->pVdbe
;
702 int hasDistinct
; /* True if the DISTINCT keyword is present */
703 int eDest
= pDest
->eDest
; /* How to dispose of results */
704 int iParm
= pDest
->iSDParm
; /* First argument to disposal method */
705 int nResultCol
; /* Number of result columns */
706 int nPrefixReg
= 0; /* Number of extra registers before regResult */
708 /* Usually, regResult is the first cell in an array of memory cells
709 ** containing the current result row. In this case regOrig is set to the
710 ** same value. However, if the results are being sent to the sorter, the
711 ** values for any expressions that are also part of the sort-key are omitted
712 ** from this array. In this case regOrig is set to zero. */
713 int regResult
; /* Start of memory holding current results */
714 int regOrig
; /* Start of memory holding full result (or 0) */
717 assert( p
->pEList
!=0 );
718 hasDistinct
= pDistinct
? pDistinct
->eTnctType
: WHERE_DISTINCT_NOOP
;
719 if( pSort
&& pSort
->pOrderBy
==0 ) pSort
= 0;
720 if( pSort
==0 && !hasDistinct
){
721 assert( iContinue
!=0 );
722 codeOffset(v
, p
->iOffset
, iContinue
);
725 /* Pull the requested columns.
727 nResultCol
= p
->pEList
->nExpr
;
729 if( pDest
->iSdst
==0 ){
731 nPrefixReg
= pSort
->pOrderBy
->nExpr
;
732 if( !(pSort
->sortFlags
& SORTFLAG_UseSorter
) ) nPrefixReg
++;
733 pParse
->nMem
+= nPrefixReg
;
735 pDest
->iSdst
= pParse
->nMem
+1;
736 pParse
->nMem
+= nResultCol
;
737 }else if( pDest
->iSdst
+nResultCol
> pParse
->nMem
){
738 /* This is an error condition that can result, for example, when a SELECT
739 ** on the right-hand side of an INSERT contains more result columns than
740 ** there are columns in the table on the left. The error will be caught
741 ** and reported later. But we need to make sure enough memory is allocated
742 ** to avoid other spurious errors in the meantime. */
743 pParse
->nMem
+= nResultCol
;
745 pDest
->nSdst
= nResultCol
;
746 regOrig
= regResult
= pDest
->iSdst
;
748 for(i
=0; i
<nResultCol
; i
++){
749 sqlite3VdbeAddOp3(v
, OP_Column
, srcTab
, i
, regResult
+i
);
750 VdbeComment((v
, "%s", p
->pEList
->a
[i
].zName
));
752 }else if( eDest
!=SRT_Exists
){
753 /* If the destination is an EXISTS(...) expression, the actual
754 ** values returned by the SELECT are not required.
757 if( eDest
==SRT_Mem
|| eDest
==SRT_Output
|| eDest
==SRT_Coroutine
){
758 ecelFlags
= SQLITE_ECEL_DUP
;
762 if( pSort
&& hasDistinct
==0 && eDest
!=SRT_EphemTab
&& eDest
!=SRT_Table
){
763 /* For each expression in p->pEList that is a copy of an expression in
764 ** the ORDER BY clause (pSort->pOrderBy), set the associated
765 ** iOrderByCol value to one more than the index of the ORDER BY
766 ** expression within the sort-key that pushOntoSorter() will generate.
767 ** This allows the p->pEList field to be omitted from the sorted record,
768 ** saving space and CPU cycles. */
769 ecelFlags
|= (SQLITE_ECEL_OMITREF
|SQLITE_ECEL_REF
);
770 for(i
=pSort
->nOBSat
; i
<pSort
->pOrderBy
->nExpr
; i
++){
772 if( (j
= pSort
->pOrderBy
->a
[i
].u
.x
.iOrderByCol
)>0 ){
773 p
->pEList
->a
[j
-1].u
.x
.iOrderByCol
= i
+1-pSort
->nOBSat
;
777 assert( eDest
==SRT_Set
|| eDest
==SRT_Mem
778 || eDest
==SRT_Coroutine
|| eDest
==SRT_Output
);
780 nResultCol
= sqlite3ExprCodeExprList(pParse
,p
->pEList
,regResult
,
784 /* If the DISTINCT keyword was present on the SELECT statement
785 ** and this row has been seen before, then do not make this row
786 ** part of the result.
789 switch( pDistinct
->eTnctType
){
790 case WHERE_DISTINCT_ORDERED
: {
791 VdbeOp
*pOp
; /* No longer required OpenEphemeral instr. */
792 int iJump
; /* Jump destination */
793 int regPrev
; /* Previous row content */
795 /* Allocate space for the previous row */
796 regPrev
= pParse
->nMem
+1;
797 pParse
->nMem
+= nResultCol
;
799 /* Change the OP_OpenEphemeral coded earlier to an OP_Null
800 ** sets the MEM_Cleared bit on the first register of the
801 ** previous value. This will cause the OP_Ne below to always
802 ** fail on the first iteration of the loop even if the first
805 sqlite3VdbeChangeToNoop(v
, pDistinct
->addrTnct
);
806 pOp
= sqlite3VdbeGetOp(v
, pDistinct
->addrTnct
);
807 pOp
->opcode
= OP_Null
;
811 iJump
= sqlite3VdbeCurrentAddr(v
) + nResultCol
;
812 for(i
=0; i
<nResultCol
; i
++){
813 CollSeq
*pColl
= sqlite3ExprCollSeq(pParse
, p
->pEList
->a
[i
].pExpr
);
814 if( i
<nResultCol
-1 ){
815 sqlite3VdbeAddOp3(v
, OP_Ne
, regResult
+i
, iJump
, regPrev
+i
);
818 sqlite3VdbeAddOp3(v
, OP_Eq
, regResult
+i
, iContinue
, regPrev
+i
);
821 sqlite3VdbeChangeP4(v
, -1, (const char *)pColl
, P4_COLLSEQ
);
822 sqlite3VdbeChangeP5(v
, SQLITE_NULLEQ
);
824 assert( sqlite3VdbeCurrentAddr(v
)==iJump
|| pParse
->db
->mallocFailed
);
825 sqlite3VdbeAddOp3(v
, OP_Copy
, regResult
, regPrev
, nResultCol
-1);
829 case WHERE_DISTINCT_UNIQUE
: {
830 sqlite3VdbeChangeToNoop(v
, pDistinct
->addrTnct
);
835 assert( pDistinct
->eTnctType
==WHERE_DISTINCT_UNORDERED
);
836 codeDistinct(pParse
, pDistinct
->tabTnct
, iContinue
, nResultCol
,
842 codeOffset(v
, p
->iOffset
, iContinue
);
847 /* In this mode, write each query result to the key of the temporary
850 #ifndef SQLITE_OMIT_COMPOUND_SELECT
853 r1
= sqlite3GetTempReg(pParse
);
854 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, regResult
, nResultCol
, r1
);
855 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, iParm
, r1
, regResult
, nResultCol
);
856 sqlite3ReleaseTempReg(pParse
, r1
);
860 /* Construct a record from the query result, but instead of
861 ** saving that record, use it as a key to delete elements from
862 ** the temporary table iParm.
865 sqlite3VdbeAddOp3(v
, OP_IdxDelete
, iParm
, regResult
, nResultCol
);
868 #endif /* SQLITE_OMIT_COMPOUND_SELECT */
870 /* Store the result as data using a unique key.
876 int r1
= sqlite3GetTempRange(pParse
, nPrefixReg
+1);
877 testcase( eDest
==SRT_Table
);
878 testcase( eDest
==SRT_EphemTab
);
879 testcase( eDest
==SRT_Fifo
);
880 testcase( eDest
==SRT_DistFifo
);
881 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, regResult
, nResultCol
, r1
+nPrefixReg
);
882 #ifndef SQLITE_OMIT_CTE
883 if( eDest
==SRT_DistFifo
){
884 /* If the destination is DistFifo, then cursor (iParm+1) is open
885 ** on an ephemeral index. If the current row is already present
886 ** in the index, do not write it to the output. If not, add the
887 ** current row to the index and proceed with writing it to the
888 ** output table as well. */
889 int addr
= sqlite3VdbeCurrentAddr(v
) + 4;
890 sqlite3VdbeAddOp4Int(v
, OP_Found
, iParm
+1, addr
, r1
, 0);
892 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, iParm
+1, r1
,regResult
,nResultCol
);
897 pushOntoSorter(pParse
, pSort
, p
, r1
+nPrefixReg
,regResult
,1,nPrefixReg
);
899 int r2
= sqlite3GetTempReg(pParse
);
900 sqlite3VdbeAddOp2(v
, OP_NewRowid
, iParm
, r2
);
901 sqlite3VdbeAddOp3(v
, OP_Insert
, iParm
, r1
, r2
);
902 sqlite3VdbeChangeP5(v
, OPFLAG_APPEND
);
903 sqlite3ReleaseTempReg(pParse
, r2
);
905 sqlite3ReleaseTempRange(pParse
, r1
, nPrefixReg
+1);
909 #ifndef SQLITE_OMIT_SUBQUERY
910 /* If we are creating a set for an "expr IN (SELECT ...)" construct,
911 ** then there should be a single item on the stack. Write this
912 ** item into the set table with bogus data.
916 /* At first glance you would think we could optimize out the
917 ** ORDER BY in this case since the order of entries in the set
918 ** does not matter. But there might be a LIMIT clause, in which
919 ** case the order does matter */
921 pParse
, pSort
, p
, regResult
, regOrig
, nResultCol
, nPrefixReg
);
923 int r1
= sqlite3GetTempReg(pParse
);
924 assert( sqlite3Strlen30(pDest
->zAffSdst
)==nResultCol
);
925 sqlite3VdbeAddOp4(v
, OP_MakeRecord
, regResult
, nResultCol
,
926 r1
, pDest
->zAffSdst
, nResultCol
);
927 sqlite3ExprCacheAffinityChange(pParse
, regResult
, nResultCol
);
928 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, iParm
, r1
, regResult
, nResultCol
);
929 sqlite3ReleaseTempReg(pParse
, r1
);
934 /* If any row exist in the result set, record that fact and abort.
937 sqlite3VdbeAddOp2(v
, OP_Integer
, 1, iParm
);
938 /* The LIMIT clause will terminate the loop for us */
942 /* If this is a scalar select that is part of an expression, then
943 ** store the results in the appropriate memory cell or array of
944 ** memory cells and break out of the scan loop.
948 assert( nResultCol
<=pDest
->nSdst
);
950 pParse
, pSort
, p
, regResult
, regOrig
, nResultCol
, nPrefixReg
);
952 assert( nResultCol
==pDest
->nSdst
);
953 assert( regResult
==iParm
);
954 /* The LIMIT clause will jump out of the loop for us */
958 #endif /* #ifndef SQLITE_OMIT_SUBQUERY */
960 case SRT_Coroutine
: /* Send data to a co-routine */
961 case SRT_Output
: { /* Return the results */
962 testcase( eDest
==SRT_Coroutine
);
963 testcase( eDest
==SRT_Output
);
965 pushOntoSorter(pParse
, pSort
, p
, regResult
, regOrig
, nResultCol
,
967 }else if( eDest
==SRT_Coroutine
){
968 sqlite3VdbeAddOp1(v
, OP_Yield
, pDest
->iSDParm
);
970 sqlite3VdbeAddOp2(v
, OP_ResultRow
, regResult
, nResultCol
);
971 sqlite3ExprCacheAffinityChange(pParse
, regResult
, nResultCol
);
976 #ifndef SQLITE_OMIT_CTE
977 /* Write the results into a priority queue that is order according to
978 ** pDest->pOrderBy (in pSO). pDest->iSDParm (in iParm) is the cursor for an
979 ** index with pSO->nExpr+2 columns. Build a key using pSO for the first
980 ** pSO->nExpr columns, then make sure all keys are unique by adding a
981 ** final OP_Sequence column. The last column is the record as a blob.
989 pSO
= pDest
->pOrderBy
;
992 r1
= sqlite3GetTempReg(pParse
);
993 r2
= sqlite3GetTempRange(pParse
, nKey
+2);
995 if( eDest
==SRT_DistQueue
){
996 /* If the destination is DistQueue, then cursor (iParm+1) is open
997 ** on a second ephemeral index that holds all values every previously
998 ** added to the queue. */
999 addrTest
= sqlite3VdbeAddOp4Int(v
, OP_Found
, iParm
+1, 0,
1000 regResult
, nResultCol
);
1003 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, regResult
, nResultCol
, r3
);
1004 if( eDest
==SRT_DistQueue
){
1005 sqlite3VdbeAddOp2(v
, OP_IdxInsert
, iParm
+1, r3
);
1006 sqlite3VdbeChangeP5(v
, OPFLAG_USESEEKRESULT
);
1008 for(i
=0; i
<nKey
; i
++){
1009 sqlite3VdbeAddOp2(v
, OP_SCopy
,
1010 regResult
+ pSO
->a
[i
].u
.x
.iOrderByCol
- 1,
1013 sqlite3VdbeAddOp2(v
, OP_Sequence
, iParm
, r2
+nKey
);
1014 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, r2
, nKey
+2, r1
);
1015 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, iParm
, r1
, r2
, nKey
+2);
1016 if( addrTest
) sqlite3VdbeJumpHere(v
, addrTest
);
1017 sqlite3ReleaseTempReg(pParse
, r1
);
1018 sqlite3ReleaseTempRange(pParse
, r2
, nKey
+2);
1021 #endif /* SQLITE_OMIT_CTE */
1025 #if !defined(SQLITE_OMIT_TRIGGER)
1026 /* Discard the results. This is used for SELECT statements inside
1027 ** the body of a TRIGGER. The purpose of such selects is to call
1028 ** user-defined functions that have side effects. We do not care
1029 ** about the actual results of the select.
1032 assert( eDest
==SRT_Discard
);
1038 /* Jump to the end of the loop if the LIMIT is reached. Except, if
1039 ** there is a sorter, in which case the sorter has already limited
1040 ** the output for us.
1042 if( pSort
==0 && p
->iLimit
){
1043 sqlite3VdbeAddOp2(v
, OP_DecrJumpZero
, p
->iLimit
, iBreak
); VdbeCoverage(v
);
1048 ** Allocate a KeyInfo object sufficient for an index of N key columns and
1051 KeyInfo
*sqlite3KeyInfoAlloc(sqlite3
*db
, int N
, int X
){
1052 int nExtra
= (N
+X
)*(sizeof(CollSeq
*)+1) - sizeof(CollSeq
*);
1053 KeyInfo
*p
= sqlite3DbMallocRawNN(db
, sizeof(KeyInfo
) + nExtra
);
1055 p
->aSortOrder
= (u8
*)&p
->aColl
[N
+X
];
1056 p
->nKeyField
= (u16
)N
;
1057 p
->nAllField
= (u16
)(N
+X
);
1061 memset(&p
[1], 0, nExtra
);
1063 sqlite3OomFault(db
);
1069 ** Deallocate a KeyInfo object
1071 void sqlite3KeyInfoUnref(KeyInfo
*p
){
1073 assert( p
->nRef
>0 );
1075 if( p
->nRef
==0 ) sqlite3DbFreeNN(p
->db
, p
);
1080 ** Make a new pointer to a KeyInfo object
1082 KeyInfo
*sqlite3KeyInfoRef(KeyInfo
*p
){
1084 assert( p
->nRef
>0 );
1092 ** Return TRUE if a KeyInfo object can be change. The KeyInfo object
1093 ** can only be changed if this is just a single reference to the object.
1095 ** This routine is used only inside of assert() statements.
1097 int sqlite3KeyInfoIsWriteable(KeyInfo
*p
){ return p
->nRef
==1; }
1098 #endif /* SQLITE_DEBUG */
1101 ** Given an expression list, generate a KeyInfo structure that records
1102 ** the collating sequence for each expression in that expression list.
1104 ** If the ExprList is an ORDER BY or GROUP BY clause then the resulting
1105 ** KeyInfo structure is appropriate for initializing a virtual index to
1106 ** implement that clause. If the ExprList is the result set of a SELECT
1107 ** then the KeyInfo structure is appropriate for initializing a virtual
1108 ** index to implement a DISTINCT test.
1110 ** Space to hold the KeyInfo structure is obtained from malloc. The calling
1111 ** function is responsible for seeing that this structure is eventually
1114 static KeyInfo
*keyInfoFromExprList(
1115 Parse
*pParse
, /* Parsing context */
1116 ExprList
*pList
, /* Form the KeyInfo object from this ExprList */
1117 int iStart
, /* Begin with this column of pList */
1118 int nExtra
/* Add this many extra columns to the end */
1122 struct ExprList_item
*pItem
;
1123 sqlite3
*db
= pParse
->db
;
1126 nExpr
= pList
->nExpr
;
1127 pInfo
= sqlite3KeyInfoAlloc(db
, nExpr
-iStart
, nExtra
+1);
1129 assert( sqlite3KeyInfoIsWriteable(pInfo
) );
1130 for(i
=iStart
, pItem
=pList
->a
+iStart
; i
<nExpr
; i
++, pItem
++){
1131 pInfo
->aColl
[i
-iStart
] = sqlite3ExprNNCollSeq(pParse
, pItem
->pExpr
);
1132 pInfo
->aSortOrder
[i
-iStart
] = pItem
->sortOrder
;
1139 ** Name of the connection operator, used for error messages.
1141 static const char *selectOpName(int id
){
1144 case TK_ALL
: z
= "UNION ALL"; break;
1145 case TK_INTERSECT
: z
= "INTERSECT"; break;
1146 case TK_EXCEPT
: z
= "EXCEPT"; break;
1147 default: z
= "UNION"; break;
1152 #ifndef SQLITE_OMIT_EXPLAIN
1154 ** Unless an "EXPLAIN QUERY PLAN" command is being processed, this function
1155 ** is a no-op. Otherwise, it adds a single row of output to the EQP result,
1156 ** where the caption is of the form:
1158 ** "USE TEMP B-TREE FOR xxx"
1160 ** where xxx is one of "DISTINCT", "ORDER BY" or "GROUP BY". Exactly which
1161 ** is determined by the zUsage argument.
1163 static void explainTempTable(Parse
*pParse
, const char *zUsage
){
1164 if( pParse
->explain
==2 ){
1165 Vdbe
*v
= pParse
->pVdbe
;
1166 char *zMsg
= sqlite3MPrintf(pParse
->db
, "USE TEMP B-TREE FOR %s", zUsage
);
1167 sqlite3VdbeAddOp4(v
, OP_Explain
, pParse
->iSelectId
, 0, 0, zMsg
, P4_DYNAMIC
);
1172 ** Assign expression b to lvalue a. A second, no-op, version of this macro
1173 ** is provided when SQLITE_OMIT_EXPLAIN is defined. This allows the code
1174 ** in sqlite3Select() to assign values to structure member variables that
1175 ** only exist if SQLITE_OMIT_EXPLAIN is not defined without polluting the
1176 ** code with #ifndef directives.
1178 # define explainSetInteger(a, b) a = b
1181 /* No-op versions of the explainXXX() functions and macros. */
1182 # define explainTempTable(y,z)
1183 # define explainSetInteger(y,z)
1186 #if !defined(SQLITE_OMIT_EXPLAIN) && !defined(SQLITE_OMIT_COMPOUND_SELECT)
1188 ** Unless an "EXPLAIN QUERY PLAN" command is being processed, this function
1189 ** is a no-op. Otherwise, it adds a single row of output to the EQP result,
1190 ** where the caption is of one of the two forms:
1192 ** "COMPOSITE SUBQUERIES iSub1 and iSub2 (op)"
1193 ** "COMPOSITE SUBQUERIES iSub1 and iSub2 USING TEMP B-TREE (op)"
1195 ** where iSub1 and iSub2 are the integers passed as the corresponding
1196 ** function parameters, and op is the text representation of the parameter
1197 ** of the same name. The parameter "op" must be one of TK_UNION, TK_EXCEPT,
1198 ** TK_INTERSECT or TK_ALL. The first form is used if argument bUseTmp is
1199 ** false, or the second form if it is true.
1201 static void explainComposite(
1202 Parse
*pParse
, /* Parse context */
1203 int op
, /* One of TK_UNION, TK_EXCEPT etc. */
1204 int iSub1
, /* Subquery id 1 */
1205 int iSub2
, /* Subquery id 2 */
1206 int bUseTmp
/* True if a temp table was used */
1208 assert( op
==TK_UNION
|| op
==TK_EXCEPT
|| op
==TK_INTERSECT
|| op
==TK_ALL
);
1209 if( pParse
->explain
==2 ){
1210 Vdbe
*v
= pParse
->pVdbe
;
1211 char *zMsg
= sqlite3MPrintf(
1212 pParse
->db
, "COMPOUND SUBQUERIES %d AND %d %s(%s)", iSub1
, iSub2
,
1213 bUseTmp
?"USING TEMP B-TREE ":"", selectOpName(op
)
1215 sqlite3VdbeAddOp4(v
, OP_Explain
, pParse
->iSelectId
, 0, 0, zMsg
, P4_DYNAMIC
);
1219 /* No-op versions of the explainXXX() functions and macros. */
1220 # define explainComposite(v,w,x,y,z)
1224 ** If the inner loop was generated using a non-null pOrderBy argument,
1225 ** then the results were placed in a sorter. After the loop is terminated
1226 ** we need to run the sorter and output the results. The following
1227 ** routine generates the code needed to do that.
1229 static void generateSortTail(
1230 Parse
*pParse
, /* Parsing context */
1231 Select
*p
, /* The SELECT statement */
1232 SortCtx
*pSort
, /* Information on the ORDER BY clause */
1233 int nColumn
, /* Number of columns of data */
1234 SelectDest
*pDest
/* Write the sorted results here */
1236 Vdbe
*v
= pParse
->pVdbe
; /* The prepared statement */
1237 int addrBreak
= pSort
->labelDone
; /* Jump here to exit loop */
1238 int addrContinue
= sqlite3VdbeMakeLabel(v
); /* Jump here for next cycle */
1242 ExprList
*pOrderBy
= pSort
->pOrderBy
;
1243 int eDest
= pDest
->eDest
;
1244 int iParm
= pDest
->iSDParm
;
1249 int iSortTab
; /* Sorter cursor to read from */
1250 int nSortData
; /* Trailing values to read from sorter */
1252 int bSeq
; /* True if sorter record includes seq. no. */
1253 struct ExprList_item
*aOutEx
= p
->pEList
->a
;
1255 assert( addrBreak
<0 );
1256 if( pSort
->labelBkOut
){
1257 sqlite3VdbeAddOp2(v
, OP_Gosub
, pSort
->regReturn
, pSort
->labelBkOut
);
1258 sqlite3VdbeGoto(v
, addrBreak
);
1259 sqlite3VdbeResolveLabel(v
, pSort
->labelBkOut
);
1261 iTab
= pSort
->iECursor
;
1262 if( eDest
==SRT_Output
|| eDest
==SRT_Coroutine
|| eDest
==SRT_Mem
){
1264 regRow
= pDest
->iSdst
;
1265 nSortData
= nColumn
;
1267 regRowid
= sqlite3GetTempReg(pParse
);
1268 regRow
= sqlite3GetTempRange(pParse
, nColumn
);
1269 nSortData
= nColumn
;
1271 nKey
= pOrderBy
->nExpr
- pSort
->nOBSat
;
1272 if( pSort
->sortFlags
& SORTFLAG_UseSorter
){
1273 int regSortOut
= ++pParse
->nMem
;
1274 iSortTab
= pParse
->nTab
++;
1275 if( pSort
->labelBkOut
){
1276 addrOnce
= sqlite3VdbeAddOp0(v
, OP_Once
); VdbeCoverage(v
);
1278 sqlite3VdbeAddOp3(v
, OP_OpenPseudo
, iSortTab
, regSortOut
, nKey
+1+nSortData
);
1279 if( addrOnce
) sqlite3VdbeJumpHere(v
, addrOnce
);
1280 addr
= 1 + sqlite3VdbeAddOp2(v
, OP_SorterSort
, iTab
, addrBreak
);
1282 codeOffset(v
, p
->iOffset
, addrContinue
);
1283 sqlite3VdbeAddOp3(v
, OP_SorterData
, iTab
, regSortOut
, iSortTab
);
1286 addr
= 1 + sqlite3VdbeAddOp2(v
, OP_Sort
, iTab
, addrBreak
); VdbeCoverage(v
);
1287 codeOffset(v
, p
->iOffset
, addrContinue
);
1291 for(i
=0, iCol
=nKey
+bSeq
-1; i
<nSortData
; i
++){
1292 if( aOutEx
[i
].u
.x
.iOrderByCol
==0 ) iCol
++;
1294 for(i
=nSortData
-1; i
>=0; i
--){
1296 if( aOutEx
[i
].u
.x
.iOrderByCol
){
1297 iRead
= aOutEx
[i
].u
.x
.iOrderByCol
-1;
1301 sqlite3VdbeAddOp3(v
, OP_Column
, iSortTab
, iRead
, regRow
+i
);
1302 VdbeComment((v
, "%s", aOutEx
[i
].zName
? aOutEx
[i
].zName
: aOutEx
[i
].zSpan
));
1306 case SRT_EphemTab
: {
1307 sqlite3VdbeAddOp2(v
, OP_NewRowid
, iParm
, regRowid
);
1308 sqlite3VdbeAddOp3(v
, OP_Insert
, iParm
, regRow
, regRowid
);
1309 sqlite3VdbeChangeP5(v
, OPFLAG_APPEND
);
1312 #ifndef SQLITE_OMIT_SUBQUERY
1314 assert( nColumn
==sqlite3Strlen30(pDest
->zAffSdst
) );
1315 sqlite3VdbeAddOp4(v
, OP_MakeRecord
, regRow
, nColumn
, regRowid
,
1316 pDest
->zAffSdst
, nColumn
);
1317 sqlite3ExprCacheAffinityChange(pParse
, regRow
, nColumn
);
1318 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, iParm
, regRowid
, regRow
, nColumn
);
1322 /* The LIMIT clause will terminate the loop for us */
1327 assert( eDest
==SRT_Output
|| eDest
==SRT_Coroutine
);
1328 testcase( eDest
==SRT_Output
);
1329 testcase( eDest
==SRT_Coroutine
);
1330 if( eDest
==SRT_Output
){
1331 sqlite3VdbeAddOp2(v
, OP_ResultRow
, pDest
->iSdst
, nColumn
);
1332 sqlite3ExprCacheAffinityChange(pParse
, pDest
->iSdst
, nColumn
);
1334 sqlite3VdbeAddOp1(v
, OP_Yield
, pDest
->iSDParm
);
1340 if( eDest
==SRT_Set
){
1341 sqlite3ReleaseTempRange(pParse
, regRow
, nColumn
);
1343 sqlite3ReleaseTempReg(pParse
, regRow
);
1345 sqlite3ReleaseTempReg(pParse
, regRowid
);
1347 /* The bottom of the loop
1349 sqlite3VdbeResolveLabel(v
, addrContinue
);
1350 if( pSort
->sortFlags
& SORTFLAG_UseSorter
){
1351 sqlite3VdbeAddOp2(v
, OP_SorterNext
, iTab
, addr
); VdbeCoverage(v
);
1353 sqlite3VdbeAddOp2(v
, OP_Next
, iTab
, addr
); VdbeCoverage(v
);
1355 if( pSort
->regReturn
) sqlite3VdbeAddOp1(v
, OP_Return
, pSort
->regReturn
);
1356 sqlite3VdbeResolveLabel(v
, addrBreak
);
1360 ** Return a pointer to a string containing the 'declaration type' of the
1361 ** expression pExpr. The string may be treated as static by the caller.
1363 ** Also try to estimate the size of the returned value and return that
1364 ** result in *pEstWidth.
1366 ** The declaration type is the exact datatype definition extracted from the
1367 ** original CREATE TABLE statement if the expression is a column. The
1368 ** declaration type for a ROWID field is INTEGER. Exactly when an expression
1369 ** is considered a column can be complex in the presence of subqueries. The
1370 ** result-set expression in all of the following SELECT statements is
1371 ** considered a column by this function.
1373 ** SELECT col FROM tbl;
1374 ** SELECT (SELECT col FROM tbl;
1375 ** SELECT (SELECT col FROM tbl);
1376 ** SELECT abc FROM (SELECT col AS abc FROM tbl);
1378 ** The declaration type for any expression other than a column is NULL.
1380 ** This routine has either 3 or 6 parameters depending on whether or not
1381 ** the SQLITE_ENABLE_COLUMN_METADATA compile-time option is used.
1383 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1384 # define columnType(A,B,C,D,E) columnTypeImpl(A,B,C,D,E)
1385 #else /* if !defined(SQLITE_ENABLE_COLUMN_METADATA) */
1386 # define columnType(A,B,C,D,E) columnTypeImpl(A,B)
1388 static const char *columnTypeImpl(
1390 #ifndef SQLITE_ENABLE_COLUMN_METADATA
1394 const char **pzOrigDb
,
1395 const char **pzOrigTab
,
1396 const char **pzOrigCol
1399 char const *zType
= 0;
1401 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1402 char const *zOrigDb
= 0;
1403 char const *zOrigTab
= 0;
1404 char const *zOrigCol
= 0;
1408 assert( pNC
->pSrcList
!=0 );
1409 assert( pExpr
->op
!=TK_AGG_COLUMN
); /* This routine runes before aggregates
1411 switch( pExpr
->op
){
1413 /* The expression is a column. Locate the table the column is being
1414 ** extracted from in NameContext.pSrcList. This table may be real
1415 ** database table or a subquery.
1417 Table
*pTab
= 0; /* Table structure column is extracted from */
1418 Select
*pS
= 0; /* Select the column is extracted from */
1419 int iCol
= pExpr
->iColumn
; /* Index of column in pTab */
1420 while( pNC
&& !pTab
){
1421 SrcList
*pTabList
= pNC
->pSrcList
;
1422 for(j
=0;j
<pTabList
->nSrc
&& pTabList
->a
[j
].iCursor
!=pExpr
->iTable
;j
++);
1423 if( j
<pTabList
->nSrc
){
1424 pTab
= pTabList
->a
[j
].pTab
;
1425 pS
= pTabList
->a
[j
].pSelect
;
1432 /* At one time, code such as "SELECT new.x" within a trigger would
1433 ** cause this condition to run. Since then, we have restructured how
1434 ** trigger code is generated and so this condition is no longer
1435 ** possible. However, it can still be true for statements like
1438 ** CREATE TABLE t1(col INTEGER);
1439 ** SELECT (SELECT t1.col) FROM FROM t1;
1441 ** when columnType() is called on the expression "t1.col" in the
1442 ** sub-select. In this case, set the column type to NULL, even
1443 ** though it should really be "INTEGER".
1445 ** This is not a problem, as the column type of "t1.col" is never
1446 ** used. When columnType() is called on the expression
1447 ** "(SELECT t1.col)", the correct type is returned (see the TK_SELECT
1452 assert( pTab
&& pExpr
->pTab
==pTab
);
1454 /* The "table" is actually a sub-select or a view in the FROM clause
1455 ** of the SELECT statement. Return the declaration type and origin
1456 ** data for the result-set column of the sub-select.
1458 if( iCol
>=0 && iCol
<pS
->pEList
->nExpr
){
1459 /* If iCol is less than zero, then the expression requests the
1460 ** rowid of the sub-select or view. This expression is legal (see
1461 ** test case misc2.2.2) - it always evaluates to NULL.
1464 Expr
*p
= pS
->pEList
->a
[iCol
].pExpr
;
1465 sNC
.pSrcList
= pS
->pSrc
;
1467 sNC
.pParse
= pNC
->pParse
;
1468 zType
= columnType(&sNC
, p
,&zOrigDb
,&zOrigTab
,&zOrigCol
);
1471 /* A real table or a CTE table */
1473 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1474 if( iCol
<0 ) iCol
= pTab
->iPKey
;
1475 assert( iCol
==XN_ROWID
|| (iCol
>=0 && iCol
<pTab
->nCol
) );
1480 zOrigCol
= pTab
->aCol
[iCol
].zName
;
1481 zType
= sqlite3ColumnType(&pTab
->aCol
[iCol
],0);
1483 zOrigTab
= pTab
->zName
;
1484 if( pNC
->pParse
&& pTab
->pSchema
){
1485 int iDb
= sqlite3SchemaToIndex(pNC
->pParse
->db
, pTab
->pSchema
);
1486 zOrigDb
= pNC
->pParse
->db
->aDb
[iDb
].zDbSName
;
1489 assert( iCol
==XN_ROWID
|| (iCol
>=0 && iCol
<pTab
->nCol
) );
1493 zType
= sqlite3ColumnType(&pTab
->aCol
[iCol
],0);
1499 #ifndef SQLITE_OMIT_SUBQUERY
1501 /* The expression is a sub-select. Return the declaration type and
1502 ** origin info for the single column in the result set of the SELECT
1506 Select
*pS
= pExpr
->x
.pSelect
;
1507 Expr
*p
= pS
->pEList
->a
[0].pExpr
;
1508 assert( ExprHasProperty(pExpr
, EP_xIsSelect
) );
1509 sNC
.pSrcList
= pS
->pSrc
;
1511 sNC
.pParse
= pNC
->pParse
;
1512 zType
= columnType(&sNC
, p
, &zOrigDb
, &zOrigTab
, &zOrigCol
);
1518 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1520 assert( pzOrigTab
&& pzOrigCol
);
1521 *pzOrigDb
= zOrigDb
;
1522 *pzOrigTab
= zOrigTab
;
1523 *pzOrigCol
= zOrigCol
;
1530 ** Generate code that will tell the VDBE the declaration types of columns
1531 ** in the result set.
1533 static void generateColumnTypes(
1534 Parse
*pParse
, /* Parser context */
1535 SrcList
*pTabList
, /* List of tables */
1536 ExprList
*pEList
/* Expressions defining the result set */
1538 #ifndef SQLITE_OMIT_DECLTYPE
1539 Vdbe
*v
= pParse
->pVdbe
;
1542 sNC
.pSrcList
= pTabList
;
1543 sNC
.pParse
= pParse
;
1545 for(i
=0; i
<pEList
->nExpr
; i
++){
1546 Expr
*p
= pEList
->a
[i
].pExpr
;
1548 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1549 const char *zOrigDb
= 0;
1550 const char *zOrigTab
= 0;
1551 const char *zOrigCol
= 0;
1552 zType
= columnType(&sNC
, p
, &zOrigDb
, &zOrigTab
, &zOrigCol
);
1554 /* The vdbe must make its own copy of the column-type and other
1555 ** column specific strings, in case the schema is reset before this
1556 ** virtual machine is deleted.
1558 sqlite3VdbeSetColName(v
, i
, COLNAME_DATABASE
, zOrigDb
, SQLITE_TRANSIENT
);
1559 sqlite3VdbeSetColName(v
, i
, COLNAME_TABLE
, zOrigTab
, SQLITE_TRANSIENT
);
1560 sqlite3VdbeSetColName(v
, i
, COLNAME_COLUMN
, zOrigCol
, SQLITE_TRANSIENT
);
1562 zType
= columnType(&sNC
, p
, 0, 0, 0);
1564 sqlite3VdbeSetColName(v
, i
, COLNAME_DECLTYPE
, zType
, SQLITE_TRANSIENT
);
1566 #endif /* !defined(SQLITE_OMIT_DECLTYPE) */
1571 ** Compute the column names for a SELECT statement.
1573 ** The only guarantee that SQLite makes about column names is that if the
1574 ** column has an AS clause assigning it a name, that will be the name used.
1575 ** That is the only documented guarantee. However, countless applications
1576 ** developed over the years have made baseless assumptions about column names
1577 ** and will break if those assumptions changes. Hence, use extreme caution
1578 ** when modifying this routine to avoid breaking legacy.
1580 ** See Also: sqlite3ColumnsFromExprList()
1582 ** The PRAGMA short_column_names and PRAGMA full_column_names settings are
1583 ** deprecated. The default setting is short=ON, full=OFF. 99.9% of all
1584 ** applications should operate this way. Nevertheless, we need to support the
1585 ** other modes for legacy:
1587 ** short=OFF, full=OFF: Column name is the text of the expression has it
1588 ** originally appears in the SELECT statement. In
1589 ** other words, the zSpan of the result expression.
1591 ** short=ON, full=OFF: (This is the default setting). If the result
1592 ** refers directly to a table column, then the
1593 ** result column name is just the table column
1594 ** name: COLUMN. Otherwise use zSpan.
1596 ** full=ON, short=ANY: If the result refers directly to a table column,
1597 ** then the result column name with the table name
1598 ** prefix, ex: TABLE.COLUMN. Otherwise use zSpan.
1600 static void generateColumnNames(
1601 Parse
*pParse
, /* Parser context */
1602 Select
*pSelect
/* Generate column names for this SELECT statement */
1604 Vdbe
*v
= pParse
->pVdbe
;
1609 sqlite3
*db
= pParse
->db
;
1610 int fullName
; /* TABLE.COLUMN if no AS clause and is a direct table ref */
1611 int srcName
; /* COLUMN or TABLE.COLUMN if no AS clause and is direct */
1613 #ifndef SQLITE_OMIT_EXPLAIN
1614 /* If this is an EXPLAIN, skip this step */
1615 if( pParse
->explain
){
1620 if( pParse
->colNamesSet
|| db
->mallocFailed
) return;
1621 /* Column names are determined by the left-most term of a compound select */
1622 while( pSelect
->pPrior
) pSelect
= pSelect
->pPrior
;
1623 SELECTTRACE(1,pParse
,pSelect
,("generating column names\n"));
1624 pTabList
= pSelect
->pSrc
;
1625 pEList
= pSelect
->pEList
;
1627 assert( pTabList
!=0 );
1628 pParse
->colNamesSet
= 1;
1629 fullName
= (db
->flags
& SQLITE_FullColNames
)!=0;
1630 srcName
= (db
->flags
& SQLITE_ShortColNames
)!=0 || fullName
;
1631 sqlite3VdbeSetNumCols(v
, pEList
->nExpr
);
1632 for(i
=0; i
<pEList
->nExpr
; i
++){
1633 Expr
*p
= pEList
->a
[i
].pExpr
;
1636 assert( p
->op
!=TK_AGG_COLUMN
); /* Agg processing has not run yet */
1637 assert( p
->op
!=TK_COLUMN
|| p
->pTab
!=0 ); /* Covering idx not yet coded */
1638 if( pEList
->a
[i
].zName
){
1639 /* An AS clause always takes first priority */
1640 char *zName
= pEList
->a
[i
].zName
;
1641 sqlite3VdbeSetColName(v
, i
, COLNAME_NAME
, zName
, SQLITE_TRANSIENT
);
1642 }else if( srcName
&& p
->op
==TK_COLUMN
){
1644 int iCol
= p
->iColumn
;
1647 if( iCol
<0 ) iCol
= pTab
->iPKey
;
1648 assert( iCol
==-1 || (iCol
>=0 && iCol
<pTab
->nCol
) );
1652 zCol
= pTab
->aCol
[iCol
].zName
;
1656 zName
= sqlite3MPrintf(db
, "%s.%s", pTab
->zName
, zCol
);
1657 sqlite3VdbeSetColName(v
, i
, COLNAME_NAME
, zName
, SQLITE_DYNAMIC
);
1659 sqlite3VdbeSetColName(v
, i
, COLNAME_NAME
, zCol
, SQLITE_TRANSIENT
);
1662 const char *z
= pEList
->a
[i
].zSpan
;
1663 z
= z
==0 ? sqlite3MPrintf(db
, "column%d", i
+1) : sqlite3DbStrDup(db
, z
);
1664 sqlite3VdbeSetColName(v
, i
, COLNAME_NAME
, z
, SQLITE_DYNAMIC
);
1667 generateColumnTypes(pParse
, pTabList
, pEList
);
1671 ** Given an expression list (which is really the list of expressions
1672 ** that form the result set of a SELECT statement) compute appropriate
1673 ** column names for a table that would hold the expression list.
1675 ** All column names will be unique.
1677 ** Only the column names are computed. Column.zType, Column.zColl,
1678 ** and other fields of Column are zeroed.
1680 ** Return SQLITE_OK on success. If a memory allocation error occurs,
1681 ** store NULL in *paCol and 0 in *pnCol and return SQLITE_NOMEM.
1683 ** The only guarantee that SQLite makes about column names is that if the
1684 ** column has an AS clause assigning it a name, that will be the name used.
1685 ** That is the only documented guarantee. However, countless applications
1686 ** developed over the years have made baseless assumptions about column names
1687 ** and will break if those assumptions changes. Hence, use extreme caution
1688 ** when modifying this routine to avoid breaking legacy.
1690 ** See Also: generateColumnNames()
1692 int sqlite3ColumnsFromExprList(
1693 Parse
*pParse
, /* Parsing context */
1694 ExprList
*pEList
, /* Expr list from which to derive column names */
1695 i16
*pnCol
, /* Write the number of columns here */
1696 Column
**paCol
/* Write the new column list here */
1698 sqlite3
*db
= pParse
->db
; /* Database connection */
1699 int i
, j
; /* Loop counters */
1700 u32 cnt
; /* Index added to make the name unique */
1701 Column
*aCol
, *pCol
; /* For looping over result columns */
1702 int nCol
; /* Number of columns in the result set */
1703 char *zName
; /* Column name */
1704 int nName
; /* Size of name in zName[] */
1705 Hash ht
; /* Hash table of column names */
1707 sqlite3HashInit(&ht
);
1709 nCol
= pEList
->nExpr
;
1710 aCol
= sqlite3DbMallocZero(db
, sizeof(aCol
[0])*nCol
);
1711 testcase( aCol
==0 );
1712 if( nCol
>32767 ) nCol
= 32767;
1717 assert( nCol
==(i16
)nCol
);
1721 for(i
=0, pCol
=aCol
; i
<nCol
&& !db
->mallocFailed
; i
++, pCol
++){
1722 /* Get an appropriate name for the column
1724 if( (zName
= pEList
->a
[i
].zName
)!=0 ){
1725 /* If the column contains an "AS <name>" phrase, use <name> as the name */
1727 Expr
*pColExpr
= sqlite3ExprSkipCollate(pEList
->a
[i
].pExpr
);
1728 while( pColExpr
->op
==TK_DOT
){
1729 pColExpr
= pColExpr
->pRight
;
1730 assert( pColExpr
!=0 );
1732 assert( pColExpr
->op
!=TK_AGG_COLUMN
);
1733 if( pColExpr
->op
==TK_COLUMN
){
1734 /* For columns use the column name name */
1735 int iCol
= pColExpr
->iColumn
;
1736 Table
*pTab
= pColExpr
->pTab
;
1738 if( iCol
<0 ) iCol
= pTab
->iPKey
;
1739 zName
= iCol
>=0 ? pTab
->aCol
[iCol
].zName
: "rowid";
1740 }else if( pColExpr
->op
==TK_ID
){
1741 assert( !ExprHasProperty(pColExpr
, EP_IntValue
) );
1742 zName
= pColExpr
->u
.zToken
;
1744 /* Use the original text of the column expression as its name */
1745 zName
= pEList
->a
[i
].zSpan
;
1749 zName
= sqlite3DbStrDup(db
, zName
);
1751 zName
= sqlite3MPrintf(db
,"column%d",i
+1);
1754 /* Make sure the column name is unique. If the name is not unique,
1755 ** append an integer to the name so that it becomes unique.
1758 while( zName
&& sqlite3HashFind(&ht
, zName
)!=0 ){
1759 nName
= sqlite3Strlen30(zName
);
1761 for(j
=nName
-1; j
>0 && sqlite3Isdigit(zName
[j
]); j
--){}
1762 if( zName
[j
]==':' ) nName
= j
;
1764 zName
= sqlite3MPrintf(db
, "%.*z:%u", nName
, zName
, ++cnt
);
1765 if( cnt
>3 ) sqlite3_randomness(sizeof(cnt
), &cnt
);
1767 pCol
->zName
= zName
;
1768 sqlite3ColumnPropertiesFromName(0, pCol
);
1769 if( zName
&& sqlite3HashInsert(&ht
, zName
, pCol
)==pCol
){
1770 sqlite3OomFault(db
);
1773 sqlite3HashClear(&ht
);
1774 if( db
->mallocFailed
){
1776 sqlite3DbFree(db
, aCol
[j
].zName
);
1778 sqlite3DbFree(db
, aCol
);
1781 return SQLITE_NOMEM_BKPT
;
1787 ** Add type and collation information to a column list based on
1788 ** a SELECT statement.
1790 ** The column list presumably came from selectColumnNamesFromExprList().
1791 ** The column list has only names, not types or collations. This
1792 ** routine goes through and adds the types and collations.
1794 ** This routine requires that all identifiers in the SELECT
1795 ** statement be resolved.
1797 void sqlite3SelectAddColumnTypeAndCollation(
1798 Parse
*pParse
, /* Parsing contexts */
1799 Table
*pTab
, /* Add column type information to this table */
1800 Select
*pSelect
/* SELECT used to determine types and collations */
1802 sqlite3
*db
= pParse
->db
;
1808 struct ExprList_item
*a
;
1810 assert( pSelect
!=0 );
1811 assert( (pSelect
->selFlags
& SF_Resolved
)!=0 );
1812 assert( pTab
->nCol
==pSelect
->pEList
->nExpr
|| db
->mallocFailed
);
1813 if( db
->mallocFailed
) return;
1814 memset(&sNC
, 0, sizeof(sNC
));
1815 sNC
.pSrcList
= pSelect
->pSrc
;
1816 a
= pSelect
->pEList
->a
;
1817 for(i
=0, pCol
=pTab
->aCol
; i
<pTab
->nCol
; i
++, pCol
++){
1821 zType
= columnType(&sNC
, p
, 0, 0, 0);
1822 /* pCol->szEst = ... // Column size est for SELECT tables never used */
1823 pCol
->affinity
= sqlite3ExprAffinity(p
);
1825 m
= sqlite3Strlen30(zType
);
1826 n
= sqlite3Strlen30(pCol
->zName
);
1827 pCol
->zName
= sqlite3DbReallocOrFree(db
, pCol
->zName
, n
+m
+2);
1829 memcpy(&pCol
->zName
[n
+1], zType
, m
+1);
1830 pCol
->colFlags
|= COLFLAG_HASTYPE
;
1833 if( pCol
->affinity
==0 ) pCol
->affinity
= SQLITE_AFF_BLOB
;
1834 pColl
= sqlite3ExprCollSeq(pParse
, p
);
1835 if( pColl
&& pCol
->zColl
==0 ){
1836 pCol
->zColl
= sqlite3DbStrDup(db
, pColl
->zName
);
1839 pTab
->szTabRow
= 1; /* Any non-zero value works */
1843 ** Given a SELECT statement, generate a Table structure that describes
1844 ** the result set of that SELECT.
1846 Table
*sqlite3ResultSetOfSelect(Parse
*pParse
, Select
*pSelect
){
1848 sqlite3
*db
= pParse
->db
;
1851 savedFlags
= db
->flags
;
1852 db
->flags
&= ~SQLITE_FullColNames
;
1853 db
->flags
|= SQLITE_ShortColNames
;
1854 sqlite3SelectPrep(pParse
, pSelect
, 0);
1855 if( pParse
->nErr
) return 0;
1856 while( pSelect
->pPrior
) pSelect
= pSelect
->pPrior
;
1857 db
->flags
= savedFlags
;
1858 pTab
= sqlite3DbMallocZero(db
, sizeof(Table
) );
1862 /* The sqlite3ResultSetOfSelect() is only used n contexts where lookaside
1864 assert( db
->lookaside
.bDisable
);
1867 pTab
->nRowLogEst
= 200; assert( 200==sqlite3LogEst(1048576) );
1868 sqlite3ColumnsFromExprList(pParse
, pSelect
->pEList
, &pTab
->nCol
, &pTab
->aCol
);
1869 sqlite3SelectAddColumnTypeAndCollation(pParse
, pTab
, pSelect
);
1871 if( db
->mallocFailed
){
1872 sqlite3DeleteTable(db
, pTab
);
1879 ** Get a VDBE for the given parser context. Create a new one if necessary.
1880 ** If an error occurs, return NULL and leave a message in pParse.
1882 Vdbe
*sqlite3GetVdbe(Parse
*pParse
){
1883 if( pParse
->pVdbe
){
1884 return pParse
->pVdbe
;
1886 if( pParse
->pToplevel
==0
1887 && OptimizationEnabled(pParse
->db
,SQLITE_FactorOutConst
)
1889 pParse
->okConstFactor
= 1;
1891 return sqlite3VdbeCreate(pParse
);
1896 ** Compute the iLimit and iOffset fields of the SELECT based on the
1897 ** pLimit expressions. pLimit->pLeft and pLimit->pRight hold the expressions
1898 ** that appear in the original SQL statement after the LIMIT and OFFSET
1899 ** keywords. Or NULL if those keywords are omitted. iLimit and iOffset
1900 ** are the integer memory register numbers for counters used to compute
1901 ** the limit and offset. If there is no limit and/or offset, then
1902 ** iLimit and iOffset are negative.
1904 ** This routine changes the values of iLimit and iOffset only if
1905 ** a limit or offset is defined by pLimit->pLeft and pLimit->pRight. iLimit
1906 ** and iOffset should have been preset to appropriate default values (zero)
1907 ** prior to calling this routine.
1909 ** The iOffset register (if it exists) is initialized to the value
1910 ** of the OFFSET. The iLimit register is initialized to LIMIT. Register
1911 ** iOffset+1 is initialized to LIMIT+OFFSET.
1913 ** Only if pLimit->pLeft!=0 do the limit registers get
1914 ** redefined. The UNION ALL operator uses this property to force
1915 ** the reuse of the same limit and offset registers across multiple
1916 ** SELECT statements.
1918 static void computeLimitRegisters(Parse
*pParse
, Select
*p
, int iBreak
){
1923 Expr
*pLimit
= p
->pLimit
;
1925 if( p
->iLimit
) return;
1928 ** "LIMIT -1" always shows all rows. There is some
1929 ** controversy about what the correct behavior should be.
1930 ** The current implementation interprets "LIMIT 0" to mean
1933 sqlite3ExprCacheClear(pParse
);
1935 assert( pLimit
->op
==TK_LIMIT
);
1936 assert( pLimit
->pLeft
!=0 );
1937 p
->iLimit
= iLimit
= ++pParse
->nMem
;
1938 v
= sqlite3GetVdbe(pParse
);
1940 if( sqlite3ExprIsInteger(pLimit
->pLeft
, &n
) ){
1941 sqlite3VdbeAddOp2(v
, OP_Integer
, n
, iLimit
);
1942 VdbeComment((v
, "LIMIT counter"));
1944 sqlite3VdbeGoto(v
, iBreak
);
1945 }else if( n
>=0 && p
->nSelectRow
>sqlite3LogEst((u64
)n
) ){
1946 p
->nSelectRow
= sqlite3LogEst((u64
)n
);
1947 p
->selFlags
|= SF_FixedLimit
;
1950 sqlite3ExprCode(pParse
, pLimit
->pLeft
, iLimit
);
1951 sqlite3VdbeAddOp1(v
, OP_MustBeInt
, iLimit
); VdbeCoverage(v
);
1952 VdbeComment((v
, "LIMIT counter"));
1953 sqlite3VdbeAddOp2(v
, OP_IfNot
, iLimit
, iBreak
); VdbeCoverage(v
);
1955 if( pLimit
->pRight
){
1956 p
->iOffset
= iOffset
= ++pParse
->nMem
;
1957 pParse
->nMem
++; /* Allocate an extra register for limit+offset */
1958 sqlite3ExprCode(pParse
, pLimit
->pRight
, iOffset
);
1959 sqlite3VdbeAddOp1(v
, OP_MustBeInt
, iOffset
); VdbeCoverage(v
);
1960 VdbeComment((v
, "OFFSET counter"));
1961 sqlite3VdbeAddOp3(v
, OP_OffsetLimit
, iLimit
, iOffset
+1, iOffset
);
1962 VdbeComment((v
, "LIMIT+OFFSET"));
1967 #ifndef SQLITE_OMIT_COMPOUND_SELECT
1969 ** Return the appropriate collating sequence for the iCol-th column of
1970 ** the result set for the compound-select statement "p". Return NULL if
1971 ** the column has no default collating sequence.
1973 ** The collating sequence for the compound select is taken from the
1974 ** left-most term of the select that has a collating sequence.
1976 static CollSeq
*multiSelectCollSeq(Parse
*pParse
, Select
*p
, int iCol
){
1979 pRet
= multiSelectCollSeq(pParse
, p
->pPrior
, iCol
);
1984 /* iCol must be less than p->pEList->nExpr. Otherwise an error would
1985 ** have been thrown during name resolution and we would not have gotten
1987 if( pRet
==0 && ALWAYS(iCol
<p
->pEList
->nExpr
) ){
1988 pRet
= sqlite3ExprCollSeq(pParse
, p
->pEList
->a
[iCol
].pExpr
);
1994 ** The select statement passed as the second parameter is a compound SELECT
1995 ** with an ORDER BY clause. This function allocates and returns a KeyInfo
1996 ** structure suitable for implementing the ORDER BY.
1998 ** Space to hold the KeyInfo structure is obtained from malloc. The calling
1999 ** function is responsible for ensuring that this structure is eventually
2002 static KeyInfo
*multiSelectOrderByKeyInfo(Parse
*pParse
, Select
*p
, int nExtra
){
2003 ExprList
*pOrderBy
= p
->pOrderBy
;
2004 int nOrderBy
= p
->pOrderBy
->nExpr
;
2005 sqlite3
*db
= pParse
->db
;
2006 KeyInfo
*pRet
= sqlite3KeyInfoAlloc(db
, nOrderBy
+nExtra
, 1);
2009 for(i
=0; i
<nOrderBy
; i
++){
2010 struct ExprList_item
*pItem
= &pOrderBy
->a
[i
];
2011 Expr
*pTerm
= pItem
->pExpr
;
2014 if( pTerm
->flags
& EP_Collate
){
2015 pColl
= sqlite3ExprCollSeq(pParse
, pTerm
);
2017 pColl
= multiSelectCollSeq(pParse
, p
, pItem
->u
.x
.iOrderByCol
-1);
2018 if( pColl
==0 ) pColl
= db
->pDfltColl
;
2019 pOrderBy
->a
[i
].pExpr
=
2020 sqlite3ExprAddCollateString(pParse
, pTerm
, pColl
->zName
);
2022 assert( sqlite3KeyInfoIsWriteable(pRet
) );
2023 pRet
->aColl
[i
] = pColl
;
2024 pRet
->aSortOrder
[i
] = pOrderBy
->a
[i
].sortOrder
;
2031 #ifndef SQLITE_OMIT_CTE
2033 ** This routine generates VDBE code to compute the content of a WITH RECURSIVE
2034 ** query of the form:
2036 ** <recursive-table> AS (<setup-query> UNION [ALL] <recursive-query>)
2037 ** \___________/ \_______________/
2041 ** There is exactly one reference to the recursive-table in the FROM clause
2042 ** of recursive-query, marked with the SrcList->a[].fg.isRecursive flag.
2044 ** The setup-query runs once to generate an initial set of rows that go
2045 ** into a Queue table. Rows are extracted from the Queue table one by
2046 ** one. Each row extracted from Queue is output to pDest. Then the single
2047 ** extracted row (now in the iCurrent table) becomes the content of the
2048 ** recursive-table for a recursive-query run. The output of the recursive-query
2049 ** is added back into the Queue table. Then another row is extracted from Queue
2050 ** and the iteration continues until the Queue table is empty.
2052 ** If the compound query operator is UNION then no duplicate rows are ever
2053 ** inserted into the Queue table. The iDistinct table keeps a copy of all rows
2054 ** that have ever been inserted into Queue and causes duplicates to be
2055 ** discarded. If the operator is UNION ALL, then duplicates are allowed.
2057 ** If the query has an ORDER BY, then entries in the Queue table are kept in
2058 ** ORDER BY order and the first entry is extracted for each cycle. Without
2059 ** an ORDER BY, the Queue table is just a FIFO.
2061 ** If a LIMIT clause is provided, then the iteration stops after LIMIT rows
2062 ** have been output to pDest. A LIMIT of zero means to output no rows and a
2063 ** negative LIMIT means to output all rows. If there is also an OFFSET clause
2064 ** with a positive value, then the first OFFSET outputs are discarded rather
2065 ** than being sent to pDest. The LIMIT count does not begin until after OFFSET
2066 ** rows have been skipped.
2068 static void generateWithRecursiveQuery(
2069 Parse
*pParse
, /* Parsing context */
2070 Select
*p
, /* The recursive SELECT to be coded */
2071 SelectDest
*pDest
/* What to do with query results */
2073 SrcList
*pSrc
= p
->pSrc
; /* The FROM clause of the recursive query */
2074 int nCol
= p
->pEList
->nExpr
; /* Number of columns in the recursive table */
2075 Vdbe
*v
= pParse
->pVdbe
; /* The prepared statement under construction */
2076 Select
*pSetup
= p
->pPrior
; /* The setup query */
2077 int addrTop
; /* Top of the loop */
2078 int addrCont
, addrBreak
; /* CONTINUE and BREAK addresses */
2079 int iCurrent
= 0; /* The Current table */
2080 int regCurrent
; /* Register holding Current table */
2081 int iQueue
; /* The Queue table */
2082 int iDistinct
= 0; /* To ensure unique results if UNION */
2083 int eDest
= SRT_Fifo
; /* How to write to Queue */
2084 SelectDest destQueue
; /* SelectDest targetting the Queue table */
2085 int i
; /* Loop counter */
2086 int rc
; /* Result code */
2087 ExprList
*pOrderBy
; /* The ORDER BY clause */
2088 Expr
*pLimit
; /* Saved LIMIT and OFFSET */
2089 int regLimit
, regOffset
; /* Registers used by LIMIT and OFFSET */
2091 /* Obtain authorization to do a recursive query */
2092 if( sqlite3AuthCheck(pParse
, SQLITE_RECURSIVE
, 0, 0, 0) ) return;
2094 /* Process the LIMIT and OFFSET clauses, if they exist */
2095 addrBreak
= sqlite3VdbeMakeLabel(v
);
2096 p
->nSelectRow
= 320; /* 4 billion rows */
2097 computeLimitRegisters(pParse
, p
, addrBreak
);
2099 regLimit
= p
->iLimit
;
2100 regOffset
= p
->iOffset
;
2102 p
->iLimit
= p
->iOffset
= 0;
2103 pOrderBy
= p
->pOrderBy
;
2105 /* Locate the cursor number of the Current table */
2106 for(i
=0; ALWAYS(i
<pSrc
->nSrc
); i
++){
2107 if( pSrc
->a
[i
].fg
.isRecursive
){
2108 iCurrent
= pSrc
->a
[i
].iCursor
;
2113 /* Allocate cursors numbers for Queue and Distinct. The cursor number for
2114 ** the Distinct table must be exactly one greater than Queue in order
2115 ** for the SRT_DistFifo and SRT_DistQueue destinations to work. */
2116 iQueue
= pParse
->nTab
++;
2117 if( p
->op
==TK_UNION
){
2118 eDest
= pOrderBy
? SRT_DistQueue
: SRT_DistFifo
;
2119 iDistinct
= pParse
->nTab
++;
2121 eDest
= pOrderBy
? SRT_Queue
: SRT_Fifo
;
2123 sqlite3SelectDestInit(&destQueue
, eDest
, iQueue
);
2125 /* Allocate cursors for Current, Queue, and Distinct. */
2126 regCurrent
= ++pParse
->nMem
;
2127 sqlite3VdbeAddOp3(v
, OP_OpenPseudo
, iCurrent
, regCurrent
, nCol
);
2129 KeyInfo
*pKeyInfo
= multiSelectOrderByKeyInfo(pParse
, p
, 1);
2130 sqlite3VdbeAddOp4(v
, OP_OpenEphemeral
, iQueue
, pOrderBy
->nExpr
+2, 0,
2131 (char*)pKeyInfo
, P4_KEYINFO
);
2132 destQueue
.pOrderBy
= pOrderBy
;
2134 sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, iQueue
, nCol
);
2136 VdbeComment((v
, "Queue table"));
2138 p
->addrOpenEphm
[0] = sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, iDistinct
, 0);
2139 p
->selFlags
|= SF_UsesEphemeral
;
2142 /* Detach the ORDER BY clause from the compound SELECT */
2145 /* Store the results of the setup-query in Queue. */
2147 rc
= sqlite3Select(pParse
, pSetup
, &destQueue
);
2149 if( rc
) goto end_of_recursive_query
;
2151 /* Find the next row in the Queue and output that row */
2152 addrTop
= sqlite3VdbeAddOp2(v
, OP_Rewind
, iQueue
, addrBreak
); VdbeCoverage(v
);
2154 /* Transfer the next row in Queue over to Current */
2155 sqlite3VdbeAddOp1(v
, OP_NullRow
, iCurrent
); /* To reset column cache */
2157 sqlite3VdbeAddOp3(v
, OP_Column
, iQueue
, pOrderBy
->nExpr
+1, regCurrent
);
2159 sqlite3VdbeAddOp2(v
, OP_RowData
, iQueue
, regCurrent
);
2161 sqlite3VdbeAddOp1(v
, OP_Delete
, iQueue
);
2163 /* Output the single row in Current */
2164 addrCont
= sqlite3VdbeMakeLabel(v
);
2165 codeOffset(v
, regOffset
, addrCont
);
2166 selectInnerLoop(pParse
, p
, iCurrent
,
2167 0, 0, pDest
, addrCont
, addrBreak
);
2169 sqlite3VdbeAddOp2(v
, OP_DecrJumpZero
, regLimit
, addrBreak
);
2172 sqlite3VdbeResolveLabel(v
, addrCont
);
2174 /* Execute the recursive SELECT taking the single row in Current as
2175 ** the value for the recursive-table. Store the results in the Queue.
2177 if( p
->selFlags
& SF_Aggregate
){
2178 sqlite3ErrorMsg(pParse
, "recursive aggregate queries not supported");
2181 sqlite3Select(pParse
, p
, &destQueue
);
2182 assert( p
->pPrior
==0 );
2186 /* Keep running the loop until the Queue is empty */
2187 sqlite3VdbeGoto(v
, addrTop
);
2188 sqlite3VdbeResolveLabel(v
, addrBreak
);
2190 end_of_recursive_query
:
2191 sqlite3ExprListDelete(pParse
->db
, p
->pOrderBy
);
2192 p
->pOrderBy
= pOrderBy
;
2196 #endif /* SQLITE_OMIT_CTE */
2198 /* Forward references */
2199 static int multiSelectOrderBy(
2200 Parse
*pParse
, /* Parsing context */
2201 Select
*p
, /* The right-most of SELECTs to be coded */
2202 SelectDest
*pDest
/* What to do with query results */
2206 ** Handle the special case of a compound-select that originates from a
2207 ** VALUES clause. By handling this as a special case, we avoid deep
2208 ** recursion, and thus do not need to enforce the SQLITE_LIMIT_COMPOUND_SELECT
2209 ** on a VALUES clause.
2211 ** Because the Select object originates from a VALUES clause:
2212 ** (1) There is no LIMIT or OFFSET or else there is a LIMIT of exactly 1
2213 ** (2) All terms are UNION ALL
2214 ** (3) There is no ORDER BY clause
2216 ** The "LIMIT of exactly 1" case of condition (1) comes about when a VALUES
2217 ** clause occurs within scalar expression (ex: "SELECT (VALUES(1),(2),(3))").
2218 ** The sqlite3CodeSubselect will have added the LIMIT 1 clause in tht case.
2219 ** Since the limit is exactly 1, we only need to evalutes the left-most VALUES.
2221 static int multiSelectValues(
2222 Parse
*pParse
, /* Parsing context */
2223 Select
*p
, /* The right-most of SELECTs to be coded */
2224 SelectDest
*pDest
/* What to do with query results */
2227 Select
*pRightmost
= p
;
2230 assert( p
->selFlags
& SF_MultiValue
);
2232 assert( p
->selFlags
& SF_Values
);
2233 assert( p
->op
==TK_ALL
|| (p
->op
==TK_SELECT
&& p
->pPrior
==0) );
2234 assert( p
->pNext
==0 || p
->pEList
->nExpr
==p
->pNext
->pEList
->nExpr
);
2235 if( p
->pPrior
==0 ) break;
2236 assert( p
->pPrior
->pNext
==p
);
2243 rc
= sqlite3Select(pParse
, p
, pDest
);
2245 if( rc
|| pRightmost
->pLimit
) break;
2246 p
->nSelectRow
= nRow
;
2253 ** This routine is called to process a compound query form from
2254 ** two or more separate queries using UNION, UNION ALL, EXCEPT, or
2257 ** "p" points to the right-most of the two queries. the query on the
2258 ** left is p->pPrior. The left query could also be a compound query
2259 ** in which case this routine will be called recursively.
2261 ** The results of the total query are to be written into a destination
2262 ** of type eDest with parameter iParm.
2264 ** Example 1: Consider a three-way compound SQL statement.
2266 ** SELECT a FROM t1 UNION SELECT b FROM t2 UNION SELECT c FROM t3
2268 ** This statement is parsed up as follows:
2272 ** `-----> SELECT b FROM t2
2274 ** `------> SELECT a FROM t1
2276 ** The arrows in the diagram above represent the Select.pPrior pointer.
2277 ** So if this routine is called with p equal to the t3 query, then
2278 ** pPrior will be the t2 query. p->op will be TK_UNION in this case.
2280 ** Notice that because of the way SQLite parses compound SELECTs, the
2281 ** individual selects always group from left to right.
2283 static int multiSelect(
2284 Parse
*pParse
, /* Parsing context */
2285 Select
*p
, /* The right-most of SELECTs to be coded */
2286 SelectDest
*pDest
/* What to do with query results */
2288 int rc
= SQLITE_OK
; /* Success code from a subroutine */
2289 Select
*pPrior
; /* Another SELECT immediately to our left */
2290 Vdbe
*v
; /* Generate code to this VDBE */
2291 SelectDest dest
; /* Alternative data destination */
2292 Select
*pDelete
= 0; /* Chain of simple selects to delete */
2293 sqlite3
*db
; /* Database connection */
2294 #ifndef SQLITE_OMIT_EXPLAIN
2295 int iSub1
= 0; /* EQP id of left-hand query */
2296 int iSub2
= 0; /* EQP id of right-hand query */
2299 /* Make sure there is no ORDER BY or LIMIT clause on prior SELECTs. Only
2300 ** the last (right-most) SELECT in the series may have an ORDER BY or LIMIT.
2302 assert( p
&& p
->pPrior
); /* Calling function guarantees this much */
2303 assert( (p
->selFlags
& SF_Recursive
)==0 || p
->op
==TK_ALL
|| p
->op
==TK_UNION
);
2307 if( pPrior
->pOrderBy
|| pPrior
->pLimit
){
2308 sqlite3ErrorMsg(pParse
,"%s clause should come after %s not before",
2309 pPrior
->pOrderBy
!=0 ? "ORDER BY" : "LIMIT", selectOpName(p
->op
));
2311 goto multi_select_end
;
2314 v
= sqlite3GetVdbe(pParse
);
2315 assert( v
!=0 ); /* The VDBE already created by calling function */
2317 /* Create the destination temporary table if necessary
2319 if( dest
.eDest
==SRT_EphemTab
){
2320 assert( p
->pEList
);
2321 sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, dest
.iSDParm
, p
->pEList
->nExpr
);
2322 dest
.eDest
= SRT_Table
;
2325 /* Special handling for a compound-select that originates as a VALUES clause.
2327 if( p
->selFlags
& SF_MultiValue
){
2328 rc
= multiSelectValues(pParse
, p
, &dest
);
2329 goto multi_select_end
;
2332 /* Make sure all SELECTs in the statement have the same number of elements
2333 ** in their result sets.
2335 assert( p
->pEList
&& pPrior
->pEList
);
2336 assert( p
->pEList
->nExpr
==pPrior
->pEList
->nExpr
);
2338 #ifndef SQLITE_OMIT_CTE
2339 if( p
->selFlags
& SF_Recursive
){
2340 generateWithRecursiveQuery(pParse
, p
, &dest
);
2344 /* Compound SELECTs that have an ORDER BY clause are handled separately.
2347 return multiSelectOrderBy(pParse
, p
, pDest
);
2350 /* Generate code for the left and right SELECT statements.
2356 assert( !pPrior
->pLimit
);
2357 pPrior
->iLimit
= p
->iLimit
;
2358 pPrior
->iOffset
= p
->iOffset
;
2359 pPrior
->pLimit
= p
->pLimit
;
2360 explainSetInteger(iSub1
, pParse
->iNextSelectId
);
2361 rc
= sqlite3Select(pParse
, pPrior
, &dest
);
2364 goto multi_select_end
;
2367 p
->iLimit
= pPrior
->iLimit
;
2368 p
->iOffset
= pPrior
->iOffset
;
2370 addr
= sqlite3VdbeAddOp1(v
, OP_IfNot
, p
->iLimit
); VdbeCoverage(v
);
2371 VdbeComment((v
, "Jump ahead if LIMIT reached"));
2373 sqlite3VdbeAddOp3(v
, OP_OffsetLimit
,
2374 p
->iLimit
, p
->iOffset
+1, p
->iOffset
);
2377 explainSetInteger(iSub2
, pParse
->iNextSelectId
);
2378 rc
= sqlite3Select(pParse
, p
, &dest
);
2379 testcase( rc
!=SQLITE_OK
);
2380 pDelete
= p
->pPrior
;
2382 p
->nSelectRow
= sqlite3LogEstAdd(p
->nSelectRow
, pPrior
->nSelectRow
);
2384 && sqlite3ExprIsInteger(pPrior
->pLimit
->pLeft
, &nLimit
)
2385 && nLimit
>0 && p
->nSelectRow
> sqlite3LogEst((u64
)nLimit
)
2387 p
->nSelectRow
= sqlite3LogEst((u64
)nLimit
);
2390 sqlite3VdbeJumpHere(v
, addr
);
2396 int unionTab
; /* Cursor number of the temporary table holding result */
2397 u8 op
= 0; /* One of the SRT_ operations to apply to self */
2398 int priorOp
; /* The SRT_ operation to apply to prior selects */
2399 Expr
*pLimit
; /* Saved values of p->nLimit */
2401 SelectDest uniondest
;
2403 testcase( p
->op
==TK_EXCEPT
);
2404 testcase( p
->op
==TK_UNION
);
2405 priorOp
= SRT_Union
;
2406 if( dest
.eDest
==priorOp
){
2407 /* We can reuse a temporary table generated by a SELECT to our
2410 assert( p
->pLimit
==0 ); /* Not allowed on leftward elements */
2411 unionTab
= dest
.iSDParm
;
2413 /* We will need to create our own temporary table to hold the
2414 ** intermediate results.
2416 unionTab
= pParse
->nTab
++;
2417 assert( p
->pOrderBy
==0 );
2418 addr
= sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, unionTab
, 0);
2419 assert( p
->addrOpenEphm
[0] == -1 );
2420 p
->addrOpenEphm
[0] = addr
;
2421 findRightmost(p
)->selFlags
|= SF_UsesEphemeral
;
2422 assert( p
->pEList
);
2425 /* Code the SELECT statements to our left
2427 assert( !pPrior
->pOrderBy
);
2428 sqlite3SelectDestInit(&uniondest
, priorOp
, unionTab
);
2429 explainSetInteger(iSub1
, pParse
->iNextSelectId
);
2430 rc
= sqlite3Select(pParse
, pPrior
, &uniondest
);
2432 goto multi_select_end
;
2435 /* Code the current SELECT statement
2437 if( p
->op
==TK_EXCEPT
){
2440 assert( p
->op
==TK_UNION
);
2446 uniondest
.eDest
= op
;
2447 explainSetInteger(iSub2
, pParse
->iNextSelectId
);
2448 rc
= sqlite3Select(pParse
, p
, &uniondest
);
2449 testcase( rc
!=SQLITE_OK
);
2450 /* Query flattening in sqlite3Select() might refill p->pOrderBy.
2451 ** Be sure to delete p->pOrderBy, therefore, to avoid a memory leak. */
2452 sqlite3ExprListDelete(db
, p
->pOrderBy
);
2453 pDelete
= p
->pPrior
;
2456 if( p
->op
==TK_UNION
){
2457 p
->nSelectRow
= sqlite3LogEstAdd(p
->nSelectRow
, pPrior
->nSelectRow
);
2459 sqlite3ExprDelete(db
, p
->pLimit
);
2464 /* Convert the data in the temporary table into whatever form
2465 ** it is that we currently need.
2467 assert( unionTab
==dest
.iSDParm
|| dest
.eDest
!=priorOp
);
2468 if( dest
.eDest
!=priorOp
){
2469 int iCont
, iBreak
, iStart
;
2470 assert( p
->pEList
);
2471 iBreak
= sqlite3VdbeMakeLabel(v
);
2472 iCont
= sqlite3VdbeMakeLabel(v
);
2473 computeLimitRegisters(pParse
, p
, iBreak
);
2474 sqlite3VdbeAddOp2(v
, OP_Rewind
, unionTab
, iBreak
); VdbeCoverage(v
);
2475 iStart
= sqlite3VdbeCurrentAddr(v
);
2476 selectInnerLoop(pParse
, p
, unionTab
,
2477 0, 0, &dest
, iCont
, iBreak
);
2478 sqlite3VdbeResolveLabel(v
, iCont
);
2479 sqlite3VdbeAddOp2(v
, OP_Next
, unionTab
, iStart
); VdbeCoverage(v
);
2480 sqlite3VdbeResolveLabel(v
, iBreak
);
2481 sqlite3VdbeAddOp2(v
, OP_Close
, unionTab
, 0);
2485 default: assert( p
->op
==TK_INTERSECT
); {
2487 int iCont
, iBreak
, iStart
;
2490 SelectDest intersectdest
;
2493 /* INTERSECT is different from the others since it requires
2494 ** two temporary tables. Hence it has its own case. Begin
2495 ** by allocating the tables we will need.
2497 tab1
= pParse
->nTab
++;
2498 tab2
= pParse
->nTab
++;
2499 assert( p
->pOrderBy
==0 );
2501 addr
= sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, tab1
, 0);
2502 assert( p
->addrOpenEphm
[0] == -1 );
2503 p
->addrOpenEphm
[0] = addr
;
2504 findRightmost(p
)->selFlags
|= SF_UsesEphemeral
;
2505 assert( p
->pEList
);
2507 /* Code the SELECTs to our left into temporary table "tab1".
2509 sqlite3SelectDestInit(&intersectdest
, SRT_Union
, tab1
);
2510 explainSetInteger(iSub1
, pParse
->iNextSelectId
);
2511 rc
= sqlite3Select(pParse
, pPrior
, &intersectdest
);
2513 goto multi_select_end
;
2516 /* Code the current SELECT into temporary table "tab2"
2518 addr
= sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, tab2
, 0);
2519 assert( p
->addrOpenEphm
[1] == -1 );
2520 p
->addrOpenEphm
[1] = addr
;
2524 intersectdest
.iSDParm
= tab2
;
2525 explainSetInteger(iSub2
, pParse
->iNextSelectId
);
2526 rc
= sqlite3Select(pParse
, p
, &intersectdest
);
2527 testcase( rc
!=SQLITE_OK
);
2528 pDelete
= p
->pPrior
;
2530 if( p
->nSelectRow
>pPrior
->nSelectRow
) p
->nSelectRow
= pPrior
->nSelectRow
;
2531 sqlite3ExprDelete(db
, p
->pLimit
);
2534 /* Generate code to take the intersection of the two temporary
2537 assert( p
->pEList
);
2538 iBreak
= sqlite3VdbeMakeLabel(v
);
2539 iCont
= sqlite3VdbeMakeLabel(v
);
2540 computeLimitRegisters(pParse
, p
, iBreak
);
2541 sqlite3VdbeAddOp2(v
, OP_Rewind
, tab1
, iBreak
); VdbeCoverage(v
);
2542 r1
= sqlite3GetTempReg(pParse
);
2543 iStart
= sqlite3VdbeAddOp2(v
, OP_RowData
, tab1
, r1
);
2544 sqlite3VdbeAddOp4Int(v
, OP_NotFound
, tab2
, iCont
, r1
, 0); VdbeCoverage(v
);
2545 sqlite3ReleaseTempReg(pParse
, r1
);
2546 selectInnerLoop(pParse
, p
, tab1
,
2547 0, 0, &dest
, iCont
, iBreak
);
2548 sqlite3VdbeResolveLabel(v
, iCont
);
2549 sqlite3VdbeAddOp2(v
, OP_Next
, tab1
, iStart
); VdbeCoverage(v
);
2550 sqlite3VdbeResolveLabel(v
, iBreak
);
2551 sqlite3VdbeAddOp2(v
, OP_Close
, tab2
, 0);
2552 sqlite3VdbeAddOp2(v
, OP_Close
, tab1
, 0);
2557 explainComposite(pParse
, p
->op
, iSub1
, iSub2
, p
->op
!=TK_ALL
);
2559 /* Compute collating sequences used by
2560 ** temporary tables needed to implement the compound select.
2561 ** Attach the KeyInfo structure to all temporary tables.
2563 ** This section is run by the right-most SELECT statement only.
2564 ** SELECT statements to the left always skip this part. The right-most
2565 ** SELECT might also skip this part if it has no ORDER BY clause and
2566 ** no temp tables are required.
2568 if( p
->selFlags
& SF_UsesEphemeral
){
2569 int i
; /* Loop counter */
2570 KeyInfo
*pKeyInfo
; /* Collating sequence for the result set */
2571 Select
*pLoop
; /* For looping through SELECT statements */
2572 CollSeq
**apColl
; /* For looping through pKeyInfo->aColl[] */
2573 int nCol
; /* Number of columns in result set */
2575 assert( p
->pNext
==0 );
2576 nCol
= p
->pEList
->nExpr
;
2577 pKeyInfo
= sqlite3KeyInfoAlloc(db
, nCol
, 1);
2579 rc
= SQLITE_NOMEM_BKPT
;
2580 goto multi_select_end
;
2582 for(i
=0, apColl
=pKeyInfo
->aColl
; i
<nCol
; i
++, apColl
++){
2583 *apColl
= multiSelectCollSeq(pParse
, p
, i
);
2585 *apColl
= db
->pDfltColl
;
2589 for(pLoop
=p
; pLoop
; pLoop
=pLoop
->pPrior
){
2591 int addr
= pLoop
->addrOpenEphm
[i
];
2593 /* If [0] is unused then [1] is also unused. So we can
2594 ** always safely abort as soon as the first unused slot is found */
2595 assert( pLoop
->addrOpenEphm
[1]<0 );
2598 sqlite3VdbeChangeP2(v
, addr
, nCol
);
2599 sqlite3VdbeChangeP4(v
, addr
, (char*)sqlite3KeyInfoRef(pKeyInfo
),
2601 pLoop
->addrOpenEphm
[i
] = -1;
2604 sqlite3KeyInfoUnref(pKeyInfo
);
2608 pDest
->iSdst
= dest
.iSdst
;
2609 pDest
->nSdst
= dest
.nSdst
;
2610 sqlite3SelectDelete(db
, pDelete
);
2613 #endif /* SQLITE_OMIT_COMPOUND_SELECT */
2616 ** Error message for when two or more terms of a compound select have different
2617 ** size result sets.
2619 void sqlite3SelectWrongNumTermsError(Parse
*pParse
, Select
*p
){
2620 if( p
->selFlags
& SF_Values
){
2621 sqlite3ErrorMsg(pParse
, "all VALUES must have the same number of terms");
2623 sqlite3ErrorMsg(pParse
, "SELECTs to the left and right of %s"
2624 " do not have the same number of result columns", selectOpName(p
->op
));
2629 ** Code an output subroutine for a coroutine implementation of a
2632 ** The data to be output is contained in pIn->iSdst. There are
2633 ** pIn->nSdst columns to be output. pDest is where the output should
2636 ** regReturn is the number of the register holding the subroutine
2639 ** If regPrev>0 then it is the first register in a vector that
2640 ** records the previous output. mem[regPrev] is a flag that is false
2641 ** if there has been no previous output. If regPrev>0 then code is
2642 ** generated to suppress duplicates. pKeyInfo is used for comparing
2645 ** If the LIMIT found in p->iLimit is reached, jump immediately to
2648 static int generateOutputSubroutine(
2649 Parse
*pParse
, /* Parsing context */
2650 Select
*p
, /* The SELECT statement */
2651 SelectDest
*pIn
, /* Coroutine supplying data */
2652 SelectDest
*pDest
, /* Where to send the data */
2653 int regReturn
, /* The return address register */
2654 int regPrev
, /* Previous result register. No uniqueness if 0 */
2655 KeyInfo
*pKeyInfo
, /* For comparing with previous entry */
2656 int iBreak
/* Jump here if we hit the LIMIT */
2658 Vdbe
*v
= pParse
->pVdbe
;
2662 addr
= sqlite3VdbeCurrentAddr(v
);
2663 iContinue
= sqlite3VdbeMakeLabel(v
);
2665 /* Suppress duplicates for UNION, EXCEPT, and INTERSECT
2669 addr1
= sqlite3VdbeAddOp1(v
, OP_IfNot
, regPrev
); VdbeCoverage(v
);
2670 addr2
= sqlite3VdbeAddOp4(v
, OP_Compare
, pIn
->iSdst
, regPrev
+1, pIn
->nSdst
,
2671 (char*)sqlite3KeyInfoRef(pKeyInfo
), P4_KEYINFO
);
2672 sqlite3VdbeAddOp3(v
, OP_Jump
, addr2
+2, iContinue
, addr2
+2); VdbeCoverage(v
);
2673 sqlite3VdbeJumpHere(v
, addr1
);
2674 sqlite3VdbeAddOp3(v
, OP_Copy
, pIn
->iSdst
, regPrev
+1, pIn
->nSdst
-1);
2675 sqlite3VdbeAddOp2(v
, OP_Integer
, 1, regPrev
);
2677 if( pParse
->db
->mallocFailed
) return 0;
2679 /* Suppress the first OFFSET entries if there is an OFFSET clause
2681 codeOffset(v
, p
->iOffset
, iContinue
);
2683 assert( pDest
->eDest
!=SRT_Exists
);
2684 assert( pDest
->eDest
!=SRT_Table
);
2685 switch( pDest
->eDest
){
2686 /* Store the result as data using a unique key.
2688 case SRT_EphemTab
: {
2689 int r1
= sqlite3GetTempReg(pParse
);
2690 int r2
= sqlite3GetTempReg(pParse
);
2691 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, pIn
->iSdst
, pIn
->nSdst
, r1
);
2692 sqlite3VdbeAddOp2(v
, OP_NewRowid
, pDest
->iSDParm
, r2
);
2693 sqlite3VdbeAddOp3(v
, OP_Insert
, pDest
->iSDParm
, r1
, r2
);
2694 sqlite3VdbeChangeP5(v
, OPFLAG_APPEND
);
2695 sqlite3ReleaseTempReg(pParse
, r2
);
2696 sqlite3ReleaseTempReg(pParse
, r1
);
2700 #ifndef SQLITE_OMIT_SUBQUERY
2701 /* If we are creating a set for an "expr IN (SELECT ...)".
2705 testcase( pIn
->nSdst
>1 );
2706 r1
= sqlite3GetTempReg(pParse
);
2707 sqlite3VdbeAddOp4(v
, OP_MakeRecord
, pIn
->iSdst
, pIn
->nSdst
,
2708 r1
, pDest
->zAffSdst
, pIn
->nSdst
);
2709 sqlite3ExprCacheAffinityChange(pParse
, pIn
->iSdst
, pIn
->nSdst
);
2710 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, pDest
->iSDParm
, r1
,
2711 pIn
->iSdst
, pIn
->nSdst
);
2712 sqlite3ReleaseTempReg(pParse
, r1
);
2716 /* If this is a scalar select that is part of an expression, then
2717 ** store the results in the appropriate memory cell and break out
2718 ** of the scan loop.
2721 assert( pIn
->nSdst
==1 || pParse
->nErr
>0 ); testcase( pIn
->nSdst
!=1 );
2722 sqlite3ExprCodeMove(pParse
, pIn
->iSdst
, pDest
->iSDParm
, 1);
2723 /* The LIMIT clause will jump out of the loop for us */
2726 #endif /* #ifndef SQLITE_OMIT_SUBQUERY */
2728 /* The results are stored in a sequence of registers
2729 ** starting at pDest->iSdst. Then the co-routine yields.
2731 case SRT_Coroutine
: {
2732 if( pDest
->iSdst
==0 ){
2733 pDest
->iSdst
= sqlite3GetTempRange(pParse
, pIn
->nSdst
);
2734 pDest
->nSdst
= pIn
->nSdst
;
2736 sqlite3ExprCodeMove(pParse
, pIn
->iSdst
, pDest
->iSdst
, pIn
->nSdst
);
2737 sqlite3VdbeAddOp1(v
, OP_Yield
, pDest
->iSDParm
);
2741 /* If none of the above, then the result destination must be
2742 ** SRT_Output. This routine is never called with any other
2743 ** destination other than the ones handled above or SRT_Output.
2745 ** For SRT_Output, results are stored in a sequence of registers.
2746 ** Then the OP_ResultRow opcode is used to cause sqlite3_step() to
2747 ** return the next row of result.
2750 assert( pDest
->eDest
==SRT_Output
);
2751 sqlite3VdbeAddOp2(v
, OP_ResultRow
, pIn
->iSdst
, pIn
->nSdst
);
2752 sqlite3ExprCacheAffinityChange(pParse
, pIn
->iSdst
, pIn
->nSdst
);
2757 /* Jump to the end of the loop if the LIMIT is reached.
2760 sqlite3VdbeAddOp2(v
, OP_DecrJumpZero
, p
->iLimit
, iBreak
); VdbeCoverage(v
);
2763 /* Generate the subroutine return
2765 sqlite3VdbeResolveLabel(v
, iContinue
);
2766 sqlite3VdbeAddOp1(v
, OP_Return
, regReturn
);
2772 ** Alternative compound select code generator for cases when there
2773 ** is an ORDER BY clause.
2775 ** We assume a query of the following form:
2777 ** <selectA> <operator> <selectB> ORDER BY <orderbylist>
2779 ** <operator> is one of UNION ALL, UNION, EXCEPT, or INTERSECT. The idea
2780 ** is to code both <selectA> and <selectB> with the ORDER BY clause as
2781 ** co-routines. Then run the co-routines in parallel and merge the results
2782 ** into the output. In addition to the two coroutines (called selectA and
2783 ** selectB) there are 7 subroutines:
2785 ** outA: Move the output of the selectA coroutine into the output
2786 ** of the compound query.
2788 ** outB: Move the output of the selectB coroutine into the output
2789 ** of the compound query. (Only generated for UNION and
2790 ** UNION ALL. EXCEPT and INSERTSECT never output a row that
2791 ** appears only in B.)
2793 ** AltB: Called when there is data from both coroutines and A<B.
2795 ** AeqB: Called when there is data from both coroutines and A==B.
2797 ** AgtB: Called when there is data from both coroutines and A>B.
2799 ** EofA: Called when data is exhausted from selectA.
2801 ** EofB: Called when data is exhausted from selectB.
2803 ** The implementation of the latter five subroutines depend on which
2804 ** <operator> is used:
2807 ** UNION ALL UNION EXCEPT INTERSECT
2808 ** ------------- ----------------- -------------- -----------------
2809 ** AltB: outA, nextA outA, nextA outA, nextA nextA
2811 ** AeqB: outA, nextA nextA nextA outA, nextA
2813 ** AgtB: outB, nextB outB, nextB nextB nextB
2815 ** EofA: outB, nextB outB, nextB halt halt
2817 ** EofB: outA, nextA outA, nextA outA, nextA halt
2819 ** In the AltB, AeqB, and AgtB subroutines, an EOF on A following nextA
2820 ** causes an immediate jump to EofA and an EOF on B following nextB causes
2821 ** an immediate jump to EofB. Within EofA and EofB, and EOF on entry or
2822 ** following nextX causes a jump to the end of the select processing.
2824 ** Duplicate removal in the UNION, EXCEPT, and INTERSECT cases is handled
2825 ** within the output subroutine. The regPrev register set holds the previously
2826 ** output value. A comparison is made against this value and the output
2827 ** is skipped if the next results would be the same as the previous.
2829 ** The implementation plan is to implement the two coroutines and seven
2830 ** subroutines first, then put the control logic at the bottom. Like this:
2833 ** coA: coroutine for left query (A)
2834 ** coB: coroutine for right query (B)
2835 ** outA: output one row of A
2836 ** outB: output one row of B (UNION and UNION ALL only)
2842 ** Init: initialize coroutine registers
2844 ** if eof(A) goto EofA
2846 ** if eof(B) goto EofB
2847 ** Cmpr: Compare A, B
2848 ** Jump AltB, AeqB, AgtB
2851 ** We call AltB, AeqB, AgtB, EofA, and EofB "subroutines" but they are not
2852 ** actually called using Gosub and they do not Return. EofA and EofB loop
2853 ** until all data is exhausted then jump to the "end" labe. AltB, AeqB,
2854 ** and AgtB jump to either L2 or to one of EofA or EofB.
2856 #ifndef SQLITE_OMIT_COMPOUND_SELECT
2857 static int multiSelectOrderBy(
2858 Parse
*pParse
, /* Parsing context */
2859 Select
*p
, /* The right-most of SELECTs to be coded */
2860 SelectDest
*pDest
/* What to do with query results */
2862 int i
, j
; /* Loop counters */
2863 Select
*pPrior
; /* Another SELECT immediately to our left */
2864 Vdbe
*v
; /* Generate code to this VDBE */
2865 SelectDest destA
; /* Destination for coroutine A */
2866 SelectDest destB
; /* Destination for coroutine B */
2867 int regAddrA
; /* Address register for select-A coroutine */
2868 int regAddrB
; /* Address register for select-B coroutine */
2869 int addrSelectA
; /* Address of the select-A coroutine */
2870 int addrSelectB
; /* Address of the select-B coroutine */
2871 int regOutA
; /* Address register for the output-A subroutine */
2872 int regOutB
; /* Address register for the output-B subroutine */
2873 int addrOutA
; /* Address of the output-A subroutine */
2874 int addrOutB
= 0; /* Address of the output-B subroutine */
2875 int addrEofA
; /* Address of the select-A-exhausted subroutine */
2876 int addrEofA_noB
; /* Alternate addrEofA if B is uninitialized */
2877 int addrEofB
; /* Address of the select-B-exhausted subroutine */
2878 int addrAltB
; /* Address of the A<B subroutine */
2879 int addrAeqB
; /* Address of the A==B subroutine */
2880 int addrAgtB
; /* Address of the A>B subroutine */
2881 int regLimitA
; /* Limit register for select-A */
2882 int regLimitB
; /* Limit register for select-A */
2883 int regPrev
; /* A range of registers to hold previous output */
2884 int savedLimit
; /* Saved value of p->iLimit */
2885 int savedOffset
; /* Saved value of p->iOffset */
2886 int labelCmpr
; /* Label for the start of the merge algorithm */
2887 int labelEnd
; /* Label for the end of the overall SELECT stmt */
2888 int addr1
; /* Jump instructions that get retargetted */
2889 int op
; /* One of TK_ALL, TK_UNION, TK_EXCEPT, TK_INTERSECT */
2890 KeyInfo
*pKeyDup
= 0; /* Comparison information for duplicate removal */
2891 KeyInfo
*pKeyMerge
; /* Comparison information for merging rows */
2892 sqlite3
*db
; /* Database connection */
2893 ExprList
*pOrderBy
; /* The ORDER BY clause */
2894 int nOrderBy
; /* Number of terms in the ORDER BY clause */
2895 int *aPermute
; /* Mapping from ORDER BY terms to result set columns */
2896 #ifndef SQLITE_OMIT_EXPLAIN
2897 int iSub1
; /* EQP id of left-hand query */
2898 int iSub2
; /* EQP id of right-hand query */
2901 assert( p
->pOrderBy
!=0 );
2902 assert( pKeyDup
==0 ); /* "Managed" code needs this. Ticket #3382. */
2905 assert( v
!=0 ); /* Already thrown the error if VDBE alloc failed */
2906 labelEnd
= sqlite3VdbeMakeLabel(v
);
2907 labelCmpr
= sqlite3VdbeMakeLabel(v
);
2910 /* Patch up the ORDER BY clause
2914 assert( pPrior
->pOrderBy
==0 );
2915 pOrderBy
= p
->pOrderBy
;
2917 nOrderBy
= pOrderBy
->nExpr
;
2919 /* For operators other than UNION ALL we have to make sure that
2920 ** the ORDER BY clause covers every term of the result set. Add
2921 ** terms to the ORDER BY clause as necessary.
2924 for(i
=1; db
->mallocFailed
==0 && i
<=p
->pEList
->nExpr
; i
++){
2925 struct ExprList_item
*pItem
;
2926 for(j
=0, pItem
=pOrderBy
->a
; j
<nOrderBy
; j
++, pItem
++){
2927 assert( pItem
->u
.x
.iOrderByCol
>0 );
2928 if( pItem
->u
.x
.iOrderByCol
==i
) break;
2931 Expr
*pNew
= sqlite3Expr(db
, TK_INTEGER
, 0);
2932 if( pNew
==0 ) return SQLITE_NOMEM_BKPT
;
2933 pNew
->flags
|= EP_IntValue
;
2935 p
->pOrderBy
= pOrderBy
= sqlite3ExprListAppend(pParse
, pOrderBy
, pNew
);
2936 if( pOrderBy
) pOrderBy
->a
[nOrderBy
++].u
.x
.iOrderByCol
= (u16
)i
;
2941 /* Compute the comparison permutation and keyinfo that is used with
2942 ** the permutation used to determine if the next
2943 ** row of results comes from selectA or selectB. Also add explicit
2944 ** collations to the ORDER BY clause terms so that when the subqueries
2945 ** to the right and the left are evaluated, they use the correct
2948 aPermute
= sqlite3DbMallocRawNN(db
, sizeof(int)*(nOrderBy
+ 1));
2950 struct ExprList_item
*pItem
;
2951 aPermute
[0] = nOrderBy
;
2952 for(i
=1, pItem
=pOrderBy
->a
; i
<=nOrderBy
; i
++, pItem
++){
2953 assert( pItem
->u
.x
.iOrderByCol
>0 );
2954 assert( pItem
->u
.x
.iOrderByCol
<=p
->pEList
->nExpr
);
2955 aPermute
[i
] = pItem
->u
.x
.iOrderByCol
- 1;
2957 pKeyMerge
= multiSelectOrderByKeyInfo(pParse
, p
, 1);
2962 /* Reattach the ORDER BY clause to the query.
2964 p
->pOrderBy
= pOrderBy
;
2965 pPrior
->pOrderBy
= sqlite3ExprListDup(pParse
->db
, pOrderBy
, 0);
2967 /* Allocate a range of temporary registers and the KeyInfo needed
2968 ** for the logic that removes duplicate result rows when the
2969 ** operator is UNION, EXCEPT, or INTERSECT (but not UNION ALL).
2974 int nExpr
= p
->pEList
->nExpr
;
2975 assert( nOrderBy
>=nExpr
|| db
->mallocFailed
);
2976 regPrev
= pParse
->nMem
+1;
2977 pParse
->nMem
+= nExpr
+1;
2978 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, regPrev
);
2979 pKeyDup
= sqlite3KeyInfoAlloc(db
, nExpr
, 1);
2981 assert( sqlite3KeyInfoIsWriteable(pKeyDup
) );
2982 for(i
=0; i
<nExpr
; i
++){
2983 pKeyDup
->aColl
[i
] = multiSelectCollSeq(pParse
, p
, i
);
2984 pKeyDup
->aSortOrder
[i
] = 0;
2989 /* Separate the left and the right query from one another
2993 sqlite3ResolveOrderGroupBy(pParse
, p
, p
->pOrderBy
, "ORDER");
2994 if( pPrior
->pPrior
==0 ){
2995 sqlite3ResolveOrderGroupBy(pParse
, pPrior
, pPrior
->pOrderBy
, "ORDER");
2998 /* Compute the limit registers */
2999 computeLimitRegisters(pParse
, p
, labelEnd
);
3000 if( p
->iLimit
&& op
==TK_ALL
){
3001 regLimitA
= ++pParse
->nMem
;
3002 regLimitB
= ++pParse
->nMem
;
3003 sqlite3VdbeAddOp2(v
, OP_Copy
, p
->iOffset
? p
->iOffset
+1 : p
->iLimit
,
3005 sqlite3VdbeAddOp2(v
, OP_Copy
, regLimitA
, regLimitB
);
3007 regLimitA
= regLimitB
= 0;
3009 sqlite3ExprDelete(db
, p
->pLimit
);
3012 regAddrA
= ++pParse
->nMem
;
3013 regAddrB
= ++pParse
->nMem
;
3014 regOutA
= ++pParse
->nMem
;
3015 regOutB
= ++pParse
->nMem
;
3016 sqlite3SelectDestInit(&destA
, SRT_Coroutine
, regAddrA
);
3017 sqlite3SelectDestInit(&destB
, SRT_Coroutine
, regAddrB
);
3019 /* Generate a coroutine to evaluate the SELECT statement to the
3020 ** left of the compound operator - the "A" select.
3022 addrSelectA
= sqlite3VdbeCurrentAddr(v
) + 1;
3023 addr1
= sqlite3VdbeAddOp3(v
, OP_InitCoroutine
, regAddrA
, 0, addrSelectA
);
3024 VdbeComment((v
, "left SELECT"));
3025 pPrior
->iLimit
= regLimitA
;
3026 explainSetInteger(iSub1
, pParse
->iNextSelectId
);
3027 sqlite3Select(pParse
, pPrior
, &destA
);
3028 sqlite3VdbeEndCoroutine(v
, regAddrA
);
3029 sqlite3VdbeJumpHere(v
, addr1
);
3031 /* Generate a coroutine to evaluate the SELECT statement on
3032 ** the right - the "B" select
3034 addrSelectB
= sqlite3VdbeCurrentAddr(v
) + 1;
3035 addr1
= sqlite3VdbeAddOp3(v
, OP_InitCoroutine
, regAddrB
, 0, addrSelectB
);
3036 VdbeComment((v
, "right SELECT"));
3037 savedLimit
= p
->iLimit
;
3038 savedOffset
= p
->iOffset
;
3039 p
->iLimit
= regLimitB
;
3041 explainSetInteger(iSub2
, pParse
->iNextSelectId
);
3042 sqlite3Select(pParse
, p
, &destB
);
3043 p
->iLimit
= savedLimit
;
3044 p
->iOffset
= savedOffset
;
3045 sqlite3VdbeEndCoroutine(v
, regAddrB
);
3047 /* Generate a subroutine that outputs the current row of the A
3048 ** select as the next output row of the compound select.
3050 VdbeNoopComment((v
, "Output routine for A"));
3051 addrOutA
= generateOutputSubroutine(pParse
,
3052 p
, &destA
, pDest
, regOutA
,
3053 regPrev
, pKeyDup
, labelEnd
);
3055 /* Generate a subroutine that outputs the current row of the B
3056 ** select as the next output row of the compound select.
3058 if( op
==TK_ALL
|| op
==TK_UNION
){
3059 VdbeNoopComment((v
, "Output routine for B"));
3060 addrOutB
= generateOutputSubroutine(pParse
,
3061 p
, &destB
, pDest
, regOutB
,
3062 regPrev
, pKeyDup
, labelEnd
);
3064 sqlite3KeyInfoUnref(pKeyDup
);
3066 /* Generate a subroutine to run when the results from select A
3067 ** are exhausted and only data in select B remains.
3069 if( op
==TK_EXCEPT
|| op
==TK_INTERSECT
){
3070 addrEofA_noB
= addrEofA
= labelEnd
;
3072 VdbeNoopComment((v
, "eof-A subroutine"));
3073 addrEofA
= sqlite3VdbeAddOp2(v
, OP_Gosub
, regOutB
, addrOutB
);
3074 addrEofA_noB
= sqlite3VdbeAddOp2(v
, OP_Yield
, regAddrB
, labelEnd
);
3076 sqlite3VdbeGoto(v
, addrEofA
);
3077 p
->nSelectRow
= sqlite3LogEstAdd(p
->nSelectRow
, pPrior
->nSelectRow
);
3080 /* Generate a subroutine to run when the results from select B
3081 ** are exhausted and only data in select A remains.
3083 if( op
==TK_INTERSECT
){
3084 addrEofB
= addrEofA
;
3085 if( p
->nSelectRow
> pPrior
->nSelectRow
) p
->nSelectRow
= pPrior
->nSelectRow
;
3087 VdbeNoopComment((v
, "eof-B subroutine"));
3088 addrEofB
= sqlite3VdbeAddOp2(v
, OP_Gosub
, regOutA
, addrOutA
);
3089 sqlite3VdbeAddOp2(v
, OP_Yield
, regAddrA
, labelEnd
); VdbeCoverage(v
);
3090 sqlite3VdbeGoto(v
, addrEofB
);
3093 /* Generate code to handle the case of A<B
3095 VdbeNoopComment((v
, "A-lt-B subroutine"));
3096 addrAltB
= sqlite3VdbeAddOp2(v
, OP_Gosub
, regOutA
, addrOutA
);
3097 sqlite3VdbeAddOp2(v
, OP_Yield
, regAddrA
, addrEofA
); VdbeCoverage(v
);
3098 sqlite3VdbeGoto(v
, labelCmpr
);
3100 /* Generate code to handle the case of A==B
3103 addrAeqB
= addrAltB
;
3104 }else if( op
==TK_INTERSECT
){
3105 addrAeqB
= addrAltB
;
3108 VdbeNoopComment((v
, "A-eq-B subroutine"));
3110 sqlite3VdbeAddOp2(v
, OP_Yield
, regAddrA
, addrEofA
); VdbeCoverage(v
);
3111 sqlite3VdbeGoto(v
, labelCmpr
);
3114 /* Generate code to handle the case of A>B
3116 VdbeNoopComment((v
, "A-gt-B subroutine"));
3117 addrAgtB
= sqlite3VdbeCurrentAddr(v
);
3118 if( op
==TK_ALL
|| op
==TK_UNION
){
3119 sqlite3VdbeAddOp2(v
, OP_Gosub
, regOutB
, addrOutB
);
3121 sqlite3VdbeAddOp2(v
, OP_Yield
, regAddrB
, addrEofB
); VdbeCoverage(v
);
3122 sqlite3VdbeGoto(v
, labelCmpr
);
3124 /* This code runs once to initialize everything.
3126 sqlite3VdbeJumpHere(v
, addr1
);
3127 sqlite3VdbeAddOp2(v
, OP_Yield
, regAddrA
, addrEofA_noB
); VdbeCoverage(v
);
3128 sqlite3VdbeAddOp2(v
, OP_Yield
, regAddrB
, addrEofB
); VdbeCoverage(v
);
3130 /* Implement the main merge loop
3132 sqlite3VdbeResolveLabel(v
, labelCmpr
);
3133 sqlite3VdbeAddOp4(v
, OP_Permutation
, 0, 0, 0, (char*)aPermute
, P4_INTARRAY
);
3134 sqlite3VdbeAddOp4(v
, OP_Compare
, destA
.iSdst
, destB
.iSdst
, nOrderBy
,
3135 (char*)pKeyMerge
, P4_KEYINFO
);
3136 sqlite3VdbeChangeP5(v
, OPFLAG_PERMUTE
);
3137 sqlite3VdbeAddOp3(v
, OP_Jump
, addrAltB
, addrAeqB
, addrAgtB
); VdbeCoverage(v
);
3139 /* Jump to the this point in order to terminate the query.
3141 sqlite3VdbeResolveLabel(v
, labelEnd
);
3143 /* Reassembly the compound query so that it will be freed correctly
3144 ** by the calling function */
3146 sqlite3SelectDelete(db
, p
->pPrior
);
3151 /*** TBD: Insert subroutine calls to close cursors on incomplete
3152 **** subqueries ****/
3153 explainComposite(pParse
, p
->op
, iSub1
, iSub2
, 0);
3154 return pParse
->nErr
!=0;
3158 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3160 /* An instance of the SubstContext object describes an substitution edit
3161 ** to be performed on a parse tree.
3163 ** All references to columns in table iTable are to be replaced by corresponding
3164 ** expressions in pEList.
3166 typedef struct SubstContext
{
3167 Parse
*pParse
; /* The parsing context */
3168 int iTable
; /* Replace references to this table */
3169 int iNewTable
; /* New table number */
3170 int isLeftJoin
; /* Add TK_IF_NULL_ROW opcodes on each replacement */
3171 ExprList
*pEList
; /* Replacement expressions */
3174 /* Forward Declarations */
3175 static void substExprList(SubstContext
*, ExprList
*);
3176 static void substSelect(SubstContext
*, Select
*, int);
3179 ** Scan through the expression pExpr. Replace every reference to
3180 ** a column in table number iTable with a copy of the iColumn-th
3181 ** entry in pEList. (But leave references to the ROWID column
3184 ** This routine is part of the flattening procedure. A subquery
3185 ** whose result set is defined by pEList appears as entry in the
3186 ** FROM clause of a SELECT such that the VDBE cursor assigned to that
3187 ** FORM clause entry is iTable. This routine makes the necessary
3188 ** changes to pExpr so that it refers directly to the source table
3189 ** of the subquery rather the result set of the subquery.
3191 static Expr
*substExpr(
3192 SubstContext
*pSubst
, /* Description of the substitution */
3193 Expr
*pExpr
/* Expr in which substitution occurs */
3195 if( pExpr
==0 ) return 0;
3196 if( ExprHasProperty(pExpr
, EP_FromJoin
)
3197 && pExpr
->iRightJoinTable
==pSubst
->iTable
3199 pExpr
->iRightJoinTable
= pSubst
->iNewTable
;
3201 if( pExpr
->op
==TK_COLUMN
&& pExpr
->iTable
==pSubst
->iTable
){
3202 if( pExpr
->iColumn
<0 ){
3203 pExpr
->op
= TK_NULL
;
3206 Expr
*pCopy
= pSubst
->pEList
->a
[pExpr
->iColumn
].pExpr
;
3208 assert( pSubst
->pEList
!=0 && pExpr
->iColumn
<pSubst
->pEList
->nExpr
);
3209 assert( pExpr
->pLeft
==0 && pExpr
->pRight
==0 );
3210 if( sqlite3ExprIsVector(pCopy
) ){
3211 sqlite3VectorErrorMsg(pSubst
->pParse
, pCopy
);
3213 sqlite3
*db
= pSubst
->pParse
->db
;
3214 if( pSubst
->isLeftJoin
&& pCopy
->op
!=TK_COLUMN
){
3215 memset(&ifNullRow
, 0, sizeof(ifNullRow
));
3216 ifNullRow
.op
= TK_IF_NULL_ROW
;
3217 ifNullRow
.pLeft
= pCopy
;
3218 ifNullRow
.iTable
= pSubst
->iNewTable
;
3221 pNew
= sqlite3ExprDup(db
, pCopy
, 0);
3222 if( pNew
&& pSubst
->isLeftJoin
){
3223 ExprSetProperty(pNew
, EP_CanBeNull
);
3225 if( pNew
&& ExprHasProperty(pExpr
,EP_FromJoin
) ){
3226 pNew
->iRightJoinTable
= pExpr
->iRightJoinTable
;
3227 ExprSetProperty(pNew
, EP_FromJoin
);
3229 sqlite3ExprDelete(db
, pExpr
);
3234 if( pExpr
->op
==TK_IF_NULL_ROW
&& pExpr
->iTable
==pSubst
->iTable
){
3235 pExpr
->iTable
= pSubst
->iNewTable
;
3237 pExpr
->pLeft
= substExpr(pSubst
, pExpr
->pLeft
);
3238 pExpr
->pRight
= substExpr(pSubst
, pExpr
->pRight
);
3239 if( ExprHasProperty(pExpr
, EP_xIsSelect
) ){
3240 substSelect(pSubst
, pExpr
->x
.pSelect
, 1);
3242 substExprList(pSubst
, pExpr
->x
.pList
);
3247 static void substExprList(
3248 SubstContext
*pSubst
, /* Description of the substitution */
3249 ExprList
*pList
/* List to scan and in which to make substitutes */
3252 if( pList
==0 ) return;
3253 for(i
=0; i
<pList
->nExpr
; i
++){
3254 pList
->a
[i
].pExpr
= substExpr(pSubst
, pList
->a
[i
].pExpr
);
3257 static void substSelect(
3258 SubstContext
*pSubst
, /* Description of the substitution */
3259 Select
*p
, /* SELECT statement in which to make substitutions */
3260 int doPrior
/* Do substitutes on p->pPrior too */
3263 struct SrcList_item
*pItem
;
3267 substExprList(pSubst
, p
->pEList
);
3268 substExprList(pSubst
, p
->pGroupBy
);
3269 substExprList(pSubst
, p
->pOrderBy
);
3270 p
->pHaving
= substExpr(pSubst
, p
->pHaving
);
3271 p
->pWhere
= substExpr(pSubst
, p
->pWhere
);
3274 for(i
=pSrc
->nSrc
, pItem
=pSrc
->a
; i
>0; i
--, pItem
++){
3275 substSelect(pSubst
, pItem
->pSelect
, 1);
3276 if( pItem
->fg
.isTabFunc
){
3277 substExprList(pSubst
, pItem
->u1
.pFuncArg
);
3280 }while( doPrior
&& (p
= p
->pPrior
)!=0 );
3282 #endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */
3284 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3286 ** This routine attempts to flatten subqueries as a performance optimization.
3287 ** This routine returns 1 if it makes changes and 0 if no flattening occurs.
3289 ** To understand the concept of flattening, consider the following
3292 ** SELECT a FROM (SELECT x+y AS a FROM t1 WHERE z<100) WHERE a>5
3294 ** The default way of implementing this query is to execute the
3295 ** subquery first and store the results in a temporary table, then
3296 ** run the outer query on that temporary table. This requires two
3297 ** passes over the data. Furthermore, because the temporary table
3298 ** has no indices, the WHERE clause on the outer query cannot be
3301 ** This routine attempts to rewrite queries such as the above into
3302 ** a single flat select, like this:
3304 ** SELECT x+y AS a FROM t1 WHERE z<100 AND a>5
3306 ** The code generated for this simplification gives the same result
3307 ** but only has to scan the data once. And because indices might
3308 ** exist on the table t1, a complete scan of the data might be
3311 ** Flattening is subject to the following constraints:
3313 ** (**) We no longer attempt to flatten aggregate subqueries. Was:
3314 ** The subquery and the outer query cannot both be aggregates.
3316 ** (**) We no longer attempt to flatten aggregate subqueries. Was:
3317 ** (2) If the subquery is an aggregate then
3318 ** (2a) the outer query must not be a join and
3319 ** (2b) the outer query must not use subqueries
3320 ** other than the one FROM-clause subquery that is a candidate
3321 ** for flattening. (This is due to ticket [2f7170d73bf9abf80]
3322 ** from 2015-02-09.)
3324 ** (3) If the subquery is the right operand of a LEFT JOIN then
3325 ** (3a) the subquery may not be a join and
3326 ** (3b) the FROM clause of the subquery may not contain a virtual
3328 ** (3c) the outer query may not be an aggregate.
3330 ** (4) The subquery can not be DISTINCT.
3332 ** (**) At one point restrictions (4) and (5) defined a subset of DISTINCT
3333 ** sub-queries that were excluded from this optimization. Restriction
3334 ** (4) has since been expanded to exclude all DISTINCT subqueries.
3336 ** (**) We no longer attempt to flatten aggregate subqueries. Was:
3337 ** If the subquery is aggregate, the outer query may not be DISTINCT.
3339 ** (7) The subquery must have a FROM clause. TODO: For subqueries without
3340 ** A FROM clause, consider adding a FROM clause with the special
3341 ** table sqlite_once that consists of a single row containing a
3344 ** (8) If the subquery uses LIMIT then the outer query may not be a join.
3346 ** (9) If the subquery uses LIMIT then the outer query may not be aggregate.
3348 ** (**) Restriction (10) was removed from the code on 2005-02-05 but we
3349 ** accidently carried the comment forward until 2014-09-15. Original
3350 ** constraint: "If the subquery is aggregate then the outer query
3351 ** may not use LIMIT."
3353 ** (11) The subquery and the outer query may not both have ORDER BY clauses.
3355 ** (**) Not implemented. Subsumed into restriction (3). Was previously
3356 ** a separate restriction deriving from ticket #350.
3358 ** (13) The subquery and outer query may not both use LIMIT.
3360 ** (14) The subquery may not use OFFSET.
3362 ** (15) If the outer query is part of a compound select, then the
3363 ** subquery may not use LIMIT.
3364 ** (See ticket #2339 and ticket [02a8e81d44]).
3366 ** (16) If the outer query is aggregate, then the subquery may not
3367 ** use ORDER BY. (Ticket #2942) This used to not matter
3368 ** until we introduced the group_concat() function.
3370 ** (17) If the subquery is a compound select, then
3371 ** (17a) all compound operators must be a UNION ALL, and
3372 ** (17b) no terms within the subquery compound may be aggregate
3374 ** (17c) every term within the subquery compound must have a FROM clause
3375 ** (17d) the outer query may not be
3376 ** (17d1) aggregate, or
3377 ** (17d2) DISTINCT, or
3380 ** The parent and sub-query may contain WHERE clauses. Subject to
3381 ** rules (11), (13) and (14), they may also contain ORDER BY,
3382 ** LIMIT and OFFSET clauses. The subquery cannot use any compound
3383 ** operator other than UNION ALL because all the other compound
3384 ** operators have an implied DISTINCT which is disallowed by
3387 ** Also, each component of the sub-query must return the same number
3388 ** of result columns. This is actually a requirement for any compound
3389 ** SELECT statement, but all the code here does is make sure that no
3390 ** such (illegal) sub-query is flattened. The caller will detect the
3391 ** syntax error and return a detailed message.
3393 ** (18) If the sub-query is a compound select, then all terms of the
3394 ** ORDER BY clause of the parent must be simple references to
3395 ** columns of the sub-query.
3397 ** (19) If the subquery uses LIMIT then the outer query may not
3398 ** have a WHERE clause.
3400 ** (20) If the sub-query is a compound select, then it must not use
3401 ** an ORDER BY clause. Ticket #3773. We could relax this constraint
3402 ** somewhat by saying that the terms of the ORDER BY clause must
3403 ** appear as unmodified result columns in the outer query. But we
3404 ** have other optimizations in mind to deal with that case.
3406 ** (21) If the subquery uses LIMIT then the outer query may not be
3407 ** DISTINCT. (See ticket [752e1646fc]).
3409 ** (22) The subquery may not be a recursive CTE.
3411 ** (**) Subsumed into restriction (17d3). Was: If the outer query is
3412 ** a recursive CTE, then the sub-query may not be a compound query.
3413 ** This restriction is because transforming the
3414 ** parent to a compound query confuses the code that handles
3415 ** recursive queries in multiSelect().
3417 ** (**) We no longer attempt to flatten aggregate subqueries. Was:
3418 ** The subquery may not be an aggregate that uses the built-in min() or
3419 ** or max() functions. (Without this restriction, a query like:
3420 ** "SELECT x FROM (SELECT max(y), x FROM t1)" would not necessarily
3421 ** return the value X for which Y was maximal.)
3424 ** In this routine, the "p" parameter is a pointer to the outer query.
3425 ** The subquery is p->pSrc->a[iFrom]. isAgg is true if the outer query
3428 ** If flattening is not attempted, this routine is a no-op and returns 0.
3429 ** If flattening is attempted this routine returns 1.
3431 ** All of the expression analysis must occur on both the outer query and
3432 ** the subquery before this routine runs.
3434 static int flattenSubquery(
3435 Parse
*pParse
, /* Parsing context */
3436 Select
*p
, /* The parent or outer SELECT statement */
3437 int iFrom
, /* Index in p->pSrc->a[] of the inner subquery */
3438 int isAgg
/* True if outer SELECT uses aggregate functions */
3440 const char *zSavedAuthContext
= pParse
->zAuthContext
;
3441 Select
*pParent
; /* Current UNION ALL term of the other query */
3442 Select
*pSub
; /* The inner query or "subquery" */
3443 Select
*pSub1
; /* Pointer to the rightmost select in sub-query */
3444 SrcList
*pSrc
; /* The FROM clause of the outer query */
3445 SrcList
*pSubSrc
; /* The FROM clause of the subquery */
3446 int iParent
; /* VDBE cursor number of the pSub result set temp table */
3447 int iNewParent
= -1;/* Replacement table for iParent */
3448 int isLeftJoin
= 0; /* True if pSub is the right side of a LEFT JOIN */
3449 int i
; /* Loop counter */
3450 Expr
*pWhere
; /* The WHERE clause */
3451 struct SrcList_item
*pSubitem
; /* The subquery */
3452 sqlite3
*db
= pParse
->db
;
3454 /* Check to see if flattening is permitted. Return 0 if not.
3457 assert( p
->pPrior
==0 );
3458 if( OptimizationDisabled(db
, SQLITE_QueryFlattener
) ) return 0;
3460 assert( pSrc
&& iFrom
>=0 && iFrom
<pSrc
->nSrc
);
3461 pSubitem
= &pSrc
->a
[iFrom
];
3462 iParent
= pSubitem
->iCursor
;
3463 pSub
= pSubitem
->pSelect
;
3466 pSubSrc
= pSub
->pSrc
;
3468 /* Prior to version 3.1.2, when LIMIT and OFFSET had to be simple constants,
3469 ** not arbitrary expressions, we allowed some combining of LIMIT and OFFSET
3470 ** because they could be computed at compile-time. But when LIMIT and OFFSET
3471 ** became arbitrary expressions, we were forced to add restrictions (13)
3473 if( pSub
->pLimit
&& p
->pLimit
) return 0; /* Restriction (13) */
3474 if( pSub
->pLimit
&& pSub
->pLimit
->pRight
) return 0; /* Restriction (14) */
3475 if( (p
->selFlags
& SF_Compound
)!=0 && pSub
->pLimit
){
3476 return 0; /* Restriction (15) */
3478 if( pSubSrc
->nSrc
==0 ) return 0; /* Restriction (7) */
3479 if( pSub
->selFlags
& SF_Distinct
) return 0; /* Restriction (4) */
3480 if( pSub
->pLimit
&& (pSrc
->nSrc
>1 || isAgg
) ){
3481 return 0; /* Restrictions (8)(9) */
3483 if( p
->pOrderBy
&& pSub
->pOrderBy
){
3484 return 0; /* Restriction (11) */
3486 if( isAgg
&& pSub
->pOrderBy
) return 0; /* Restriction (16) */
3487 if( pSub
->pLimit
&& p
->pWhere
) return 0; /* Restriction (19) */
3488 if( pSub
->pLimit
&& (p
->selFlags
& SF_Distinct
)!=0 ){
3489 return 0; /* Restriction (21) */
3491 if( pSub
->selFlags
& (SF_Recursive
) ){
3492 return 0; /* Restrictions (22) */
3496 ** If the subquery is the right operand of a LEFT JOIN, then the
3497 ** subquery may not be a join itself (3a). Example of why this is not
3500 ** t1 LEFT OUTER JOIN (t2 JOIN t3)
3502 ** If we flatten the above, we would get
3504 ** (t1 LEFT OUTER JOIN t2) JOIN t3
3506 ** which is not at all the same thing.
3508 ** If the subquery is the right operand of a LEFT JOIN, then the outer
3509 ** query cannot be an aggregate. (3c) This is an artifact of the way
3510 ** aggregates are processed - there is no mechanism to determine if
3511 ** the LEFT JOIN table should be all-NULL.
3513 ** See also tickets #306, #350, and #3300.
3515 if( (pSubitem
->fg
.jointype
& JT_OUTER
)!=0 ){
3517 if( pSubSrc
->nSrc
>1 || isAgg
|| IsVirtual(pSubSrc
->a
[0].pTab
) ){
3518 /* (3a) (3c) (3b) */
3522 #ifdef SQLITE_EXTRA_IFNULLROW
3523 else if( iFrom
>0 && !isAgg
){
3524 /* Setting isLeftJoin to -1 causes OP_IfNullRow opcodes to be generated for
3525 ** every reference to any result column from subquery in a join, even
3526 ** though they are not necessary. This will stress-test the OP_IfNullRow
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
3538 if( pSub
->pOrderBy
){
3539 return 0; /* Restriction (20) */
3541 if( isAgg
|| (p
->selFlags
& SF_Distinct
)!=0 || pSrc
->nSrc
!=1 ){
3542 return 0; /* (17d1), (17d2), or (17d3) */
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 /* (17b) */
3550 || (pSub1
->pPrior
&& pSub1
->op
!=TK_ALL
) /* (17a) */
3551 || pSub1
->pSrc
->nSrc
<1 /* (17c) */
3555 testcase( pSub1
->pSrc
->nSrc
>1 );
3558 /* Restriction (18). */
3561 for(ii
=0; ii
<p
->pOrderBy
->nExpr
; ii
++){
3562 if( p
->pOrderBy
->a
[ii
].u
.x
.iOrderByCol
==0 ) return 0;
3567 /* Ex-restriction (23):
3568 ** The only way that the recursive part of a CTE can contain a compound
3569 ** subquery is for the subquery to be one term of a join. But if the
3570 ** subquery is a join, then the flattening has already been stopped by
3571 ** restriction (17d3)
3573 assert( (p
->selFlags
& SF_Recursive
)==0 || pSub
->pPrior
==0 );
3575 /***** If we reach this point, flattening is permitted. *****/
3576 SELECTTRACE(1,pParse
,p
,("flatten %s.%p from term %d\n",
3577 pSub
->zSelName
, pSub
, iFrom
));
3579 /* Authorize the subquery */
3580 pParse
->zAuthContext
= pSubitem
->zName
;
3581 TESTONLY(i
=) sqlite3AuthCheck(pParse
, SQLITE_SELECT
, 0, 0, 0);
3582 testcase( i
==SQLITE_DENY
);
3583 pParse
->zAuthContext
= zSavedAuthContext
;
3585 /* If the sub-query is a compound SELECT statement, then (by restrictions
3586 ** 17 and 18 above) it must be a UNION ALL and the parent query must
3589 ** SELECT <expr-list> FROM (<sub-query>) <where-clause>
3591 ** followed by any ORDER BY, LIMIT and/or OFFSET clauses. This block
3592 ** creates N-1 copies of the parent query without any ORDER BY, LIMIT or
3593 ** OFFSET clauses and joins them to the left-hand-side of the original
3594 ** using UNION ALL operators. In this case N is the number of simple
3595 ** select statements in the compound sub-query.
3599 ** SELECT a+1 FROM (
3600 ** SELECT x FROM tab
3602 ** SELECT y FROM tab
3604 ** SELECT abs(z*2) FROM tab2
3605 ** ) WHERE a!=5 ORDER BY 1
3607 ** Transformed into:
3609 ** SELECT x+1 FROM tab WHERE x+1!=5
3611 ** SELECT y+1 FROM tab WHERE y+1!=5
3613 ** SELECT abs(z*2)+1 FROM tab2 WHERE abs(z*2)+1!=5
3616 ** We call this the "compound-subquery flattening".
3618 for(pSub
=pSub
->pPrior
; pSub
; pSub
=pSub
->pPrior
){
3620 ExprList
*pOrderBy
= p
->pOrderBy
;
3621 Expr
*pLimit
= p
->pLimit
;
3622 Select
*pPrior
= p
->pPrior
;
3627 pNew
= sqlite3SelectDup(db
, p
, 0);
3628 sqlite3SelectSetName(pNew
, pSub
->zSelName
);
3630 p
->pOrderBy
= pOrderBy
;
3636 pNew
->pPrior
= pPrior
;
3637 if( pPrior
) pPrior
->pNext
= pNew
;
3640 SELECTTRACE(2,pParse
,p
,
3641 ("compound-subquery flattener creates %s.%p as peer\n",
3642 pNew
->zSelName
, pNew
));
3644 if( db
->mallocFailed
) return 1;
3647 /* Begin flattening the iFrom-th entry of the FROM clause
3648 ** in the outer query.
3650 pSub
= pSub1
= pSubitem
->pSelect
;
3652 /* Delete the transient table structure associated with the
3655 sqlite3DbFree(db
, pSubitem
->zDatabase
);
3656 sqlite3DbFree(db
, pSubitem
->zName
);
3657 sqlite3DbFree(db
, pSubitem
->zAlias
);
3658 pSubitem
->zDatabase
= 0;
3659 pSubitem
->zName
= 0;
3660 pSubitem
->zAlias
= 0;
3661 pSubitem
->pSelect
= 0;
3663 /* Defer deleting the Table object associated with the
3664 ** subquery until code generation is
3665 ** complete, since there may still exist Expr.pTab entries that
3666 ** refer to the subquery even after flattening. Ticket #3346.
3668 ** pSubitem->pTab is always non-NULL by test restrictions and tests above.
3670 if( ALWAYS(pSubitem
->pTab
!=0) ){
3671 Table
*pTabToDel
= pSubitem
->pTab
;
3672 if( pTabToDel
->nTabRef
==1 ){
3673 Parse
*pToplevel
= sqlite3ParseToplevel(pParse
);
3674 pTabToDel
->pNextZombie
= pToplevel
->pZombieTab
;
3675 pToplevel
->pZombieTab
= pTabToDel
;
3677 pTabToDel
->nTabRef
--;
3682 /* The following loop runs once for each term in a compound-subquery
3683 ** flattening (as described above). If we are doing a different kind
3684 ** of flattening - a flattening other than a compound-subquery flattening -
3685 ** then this loop only runs once.
3687 ** This loop moves all of the FROM elements of the subquery into the
3688 ** the FROM clause of the outer query. Before doing this, remember
3689 ** the cursor number for the original outer query FROM element in
3690 ** iParent. The iParent cursor will never be used. Subsequent code
3691 ** will scan expressions looking for iParent references and replace
3692 ** those references with expressions that resolve to the subquery FROM
3693 ** elements we are now copying in.
3695 for(pParent
=p
; pParent
; pParent
=pParent
->pPrior
, pSub
=pSub
->pPrior
){
3698 pSubSrc
= pSub
->pSrc
; /* FROM clause of subquery */
3699 nSubSrc
= pSubSrc
->nSrc
; /* Number of terms in subquery FROM clause */
3700 pSrc
= pParent
->pSrc
; /* FROM clause of the outer query */
3703 assert( pParent
==p
); /* First time through the loop */
3704 jointype
= pSubitem
->fg
.jointype
;
3706 assert( pParent
!=p
); /* 2nd and subsequent times through the loop */
3707 pSrc
= pParent
->pSrc
= sqlite3SrcListAppend(db
, 0, 0, 0);
3709 assert( db
->mallocFailed
);
3714 /* The subquery uses a single slot of the FROM clause of the outer
3715 ** query. If the subquery has more than one element in its FROM clause,
3716 ** then expand the outer query to make space for it to hold all elements
3721 ** SELECT * FROM tabA, (SELECT * FROM sub1, sub2), tabB;
3723 ** The outer query has 3 slots in its FROM clause. One slot of the
3724 ** outer query (the middle slot) is used by the subquery. The next
3725 ** block of code will expand the outer query FROM clause to 4 slots.
3726 ** The middle slot is expanded to two slots in order to make space
3727 ** for the two elements in the FROM clause of the subquery.
3730 pParent
->pSrc
= pSrc
= sqlite3SrcListEnlarge(db
, pSrc
, nSubSrc
-1,iFrom
+1);
3731 if( db
->mallocFailed
){
3736 /* Transfer the FROM clause terms from the subquery into the
3739 for(i
=0; i
<nSubSrc
; i
++){
3740 sqlite3IdListDelete(db
, pSrc
->a
[i
+iFrom
].pUsing
);
3741 assert( pSrc
->a
[i
+iFrom
].fg
.isTabFunc
==0 );
3742 pSrc
->a
[i
+iFrom
] = pSubSrc
->a
[i
];
3743 iNewParent
= pSubSrc
->a
[i
].iCursor
;
3744 memset(&pSubSrc
->a
[i
], 0, sizeof(pSubSrc
->a
[i
]));
3746 pSrc
->a
[iFrom
].fg
.jointype
= jointype
;
3748 /* Now begin substituting subquery result set expressions for
3749 ** references to the iParent in the outer query.
3753 ** SELECT a+5, b*10 FROM (SELECT x*3 AS a, y+10 AS b FROM t1) WHERE a>b;
3754 ** \ \_____________ subquery __________/ /
3755 ** \_____________________ outer query ______________________________/
3757 ** We look at every expression in the outer query and every place we see
3758 ** "a" we substitute "x*3" and every place we see "b" we substitute "y+10".
3760 if( pSub
->pOrderBy
){
3761 /* At this point, any non-zero iOrderByCol values indicate that the
3762 ** ORDER BY column expression is identical to the iOrderByCol'th
3763 ** expression returned by SELECT statement pSub. Since these values
3764 ** do not necessarily correspond to columns in SELECT statement pParent,
3765 ** zero them before transfering the ORDER BY clause.
3767 ** Not doing this may cause an error if a subsequent call to this
3768 ** function attempts to flatten a compound sub-query into pParent
3769 ** (the only way this can happen is if the compound sub-query is
3770 ** currently part of pSub->pSrc). See ticket [d11a6e908f]. */
3771 ExprList
*pOrderBy
= pSub
->pOrderBy
;
3772 for(i
=0; i
<pOrderBy
->nExpr
; i
++){
3773 pOrderBy
->a
[i
].u
.x
.iOrderByCol
= 0;
3775 assert( pParent
->pOrderBy
==0 );
3776 assert( pSub
->pPrior
==0 );
3777 pParent
->pOrderBy
= pOrderBy
;
3780 pWhere
= sqlite3ExprDup(db
, pSub
->pWhere
, 0);
3782 setJoinExpr(pWhere
, iNewParent
);
3784 pParent
->pWhere
= sqlite3ExprAnd(db
, pWhere
, pParent
->pWhere
);
3785 if( db
->mallocFailed
==0 ){
3789 x
.iNewTable
= iNewParent
;
3790 x
.isLeftJoin
= isLeftJoin
;
3791 x
.pEList
= pSub
->pEList
;
3792 substSelect(&x
, pParent
, 0);
3795 /* The flattened query is distinct if either the inner or the
3796 ** outer query is distinct.
3798 pParent
->selFlags
|= pSub
->selFlags
& SF_Distinct
;
3801 ** SELECT ... FROM (SELECT ... LIMIT a OFFSET b) LIMIT x OFFSET y;
3803 ** One is tempted to try to add a and b to combine the limits. But this
3804 ** does not work if either limit is negative.
3807 pParent
->pLimit
= pSub
->pLimit
;
3812 /* Finially, delete what is left of the subquery and return
3815 sqlite3SelectDelete(db
, pSub1
);
3817 #if SELECTTRACE_ENABLED
3818 if( sqlite3SelectTrace
& 0x100 ){
3819 SELECTTRACE(0x100,pParse
,p
,("After flattening:\n"));
3820 sqlite3TreeViewSelect(0, p
, 0);
3826 #endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */
3830 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3832 ** Make copies of relevant WHERE clause terms of the outer query into
3833 ** the WHERE clause of subquery. Example:
3835 ** SELECT * FROM (SELECT a AS x, c-d AS y FROM t1) WHERE x=5 AND y=10;
3837 ** Transformed into:
3839 ** SELECT * FROM (SELECT a AS x, c-d AS y FROM t1 WHERE a=5 AND c-d=10)
3840 ** WHERE x=5 AND y=10;
3842 ** The hope is that the terms added to the inner query will make it more
3845 ** Do not attempt this optimization if:
3847 ** (1) (** This restriction was removed on 2017-09-29. We used to
3848 ** disallow this optimization for aggregate subqueries, but now
3849 ** it is allowed by putting the extra terms on the HAVING clause.
3850 ** The added HAVING clause is pointless if the subquery lacks
3851 ** a GROUP BY clause. But such a HAVING clause is also harmless
3852 ** so there does not appear to be any reason to add extra logic
3853 ** to suppress it. **)
3855 ** (2) The inner query is the recursive part of a common table expression.
3857 ** (3) The inner query has a LIMIT clause (since the changes to the WHERE
3858 ** close would change the meaning of the LIMIT).
3860 ** (4) The inner query is the right operand of a LEFT JOIN and the
3861 ** expression to be pushed down does not come from the ON clause
3862 ** on that LEFT JOIN.
3864 ** (5) The WHERE clause expression originates in the ON or USING clause
3865 ** of a LEFT JOIN where iCursor is not the right-hand table of that
3866 ** left join. An example:
3869 ** FROM (SELECT 1 AS a1 UNION ALL SELECT 2) AS aa
3870 ** JOIN (SELECT 1 AS b2 UNION ALL SELECT 2) AS bb ON (a1=b2)
3871 ** LEFT JOIN (SELECT 8 AS c3 UNION ALL SELECT 9) AS cc ON (b2=2);
3873 ** The correct answer is three rows: (1,1,NULL),(2,2,8),(2,2,9).
3874 ** But if the (b2=2) term were to be pushed down into the bb subquery,
3875 ** then the (1,1,NULL) row would be suppressed.
3877 ** Return 0 if no changes are made and non-zero if one or more WHERE clause
3878 ** terms are duplicated into the subquery.
3880 static int pushDownWhereTerms(
3881 Parse
*pParse
, /* Parse context (for malloc() and error reporting) */
3882 Select
*pSubq
, /* The subquery whose WHERE clause is to be augmented */
3883 Expr
*pWhere
, /* The WHERE clause of the outer query */
3884 int iCursor
, /* Cursor number of the subquery */
3885 int isLeftJoin
/* True if pSubq is the right term of a LEFT JOIN */
3889 if( pWhere
==0 ) return 0;
3890 if( pSubq
->selFlags
& SF_Recursive
) return 0; /* restriction (2) */
3893 /* Only the first term of a compound can have a WITH clause. But make
3894 ** sure no other terms are marked SF_Recursive in case something changes
3899 for(pX
=pSubq
; pX
; pX
=pX
->pPrior
){
3900 assert( (pX
->selFlags
& (SF_Recursive
))==0 );
3905 if( pSubq
->pLimit
!=0 ){
3906 return 0; /* restriction (3) */
3908 while( pWhere
->op
==TK_AND
){
3909 nChng
+= pushDownWhereTerms(pParse
, pSubq
, pWhere
->pRight
,
3910 iCursor
, isLeftJoin
);
3911 pWhere
= pWhere
->pLeft
;
3914 && (ExprHasProperty(pWhere
,EP_FromJoin
)==0
3915 || pWhere
->iRightJoinTable
!=iCursor
)
3917 return 0; /* restriction (4) */
3919 if( ExprHasProperty(pWhere
,EP_FromJoin
) && pWhere
->iRightJoinTable
!=iCursor
){
3920 return 0; /* restriction (5) */
3922 if( sqlite3ExprIsTableConstant(pWhere
, iCursor
) ){
3926 pNew
= sqlite3ExprDup(pParse
->db
, pWhere
, 0);
3927 unsetJoinExpr(pNew
, -1);
3930 x
.iNewTable
= iCursor
;
3932 x
.pEList
= pSubq
->pEList
;
3933 pNew
= substExpr(&x
, pNew
);
3934 if( pSubq
->selFlags
& SF_Aggregate
){
3935 pSubq
->pHaving
= sqlite3ExprAnd(pParse
->db
, pSubq
->pHaving
, pNew
);
3937 pSubq
->pWhere
= sqlite3ExprAnd(pParse
->db
, pSubq
->pWhere
, pNew
);
3939 pSubq
= pSubq
->pPrior
;
3944 #endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */
3947 ** The pFunc is the only aggregate function in the query. Check to see
3948 ** if the query is a candidate for the min/max optimization.
3950 ** If the query is a candidate for the min/max optimization, then set
3951 ** *ppMinMax to be an ORDER BY clause to be used for the optimization
3952 ** and return either WHERE_ORDERBY_MIN or WHERE_ORDERBY_MAX depending on
3953 ** whether pFunc is a min() or max() function.
3955 ** If the query is not a candidate for the min/max optimization, return
3956 ** WHERE_ORDERBY_NORMAL (which must be zero).
3958 ** This routine must be called after aggregate functions have been
3959 ** located but before their arguments have been subjected to aggregate
3962 static u8
minMaxQuery(sqlite3
*db
, Expr
*pFunc
, ExprList
**ppMinMax
){
3963 int eRet
= WHERE_ORDERBY_NORMAL
; /* Return value */
3964 ExprList
*pEList
= pFunc
->x
.pList
; /* Arguments to agg function */
3965 const char *zFunc
; /* Name of aggregate function pFunc */
3969 assert( *ppMinMax
==0 );
3970 assert( pFunc
->op
==TK_AGG_FUNCTION
);
3971 if( pEList
==0 || pEList
->nExpr
!=1 ) return eRet
;
3972 zFunc
= pFunc
->u
.zToken
;
3973 if( sqlite3StrICmp(zFunc
, "min")==0 ){
3974 eRet
= WHERE_ORDERBY_MIN
;
3975 sortOrder
= SQLITE_SO_ASC
;
3976 }else if( sqlite3StrICmp(zFunc
, "max")==0 ){
3977 eRet
= WHERE_ORDERBY_MAX
;
3978 sortOrder
= SQLITE_SO_DESC
;
3982 *ppMinMax
= pOrderBy
= sqlite3ExprListDup(db
, pEList
, 0);
3983 assert( pOrderBy
!=0 || db
->mallocFailed
);
3984 if( pOrderBy
) pOrderBy
->a
[0].sortOrder
= sortOrder
;
3989 ** The select statement passed as the first argument is an aggregate query.
3990 ** The second argument is the associated aggregate-info object. This
3991 ** function tests if the SELECT is of the form:
3993 ** SELECT count(*) FROM <tbl>
3995 ** where table is a database table, not a sub-select or view. If the query
3996 ** does match this pattern, then a pointer to the Table object representing
3997 ** <tbl> is returned. Otherwise, 0 is returned.
3999 static Table
*isSimpleCount(Select
*p
, AggInfo
*pAggInfo
){
4003 assert( !p
->pGroupBy
);
4005 if( p
->pWhere
|| p
->pEList
->nExpr
!=1
4006 || p
->pSrc
->nSrc
!=1 || p
->pSrc
->a
[0].pSelect
4010 pTab
= p
->pSrc
->a
[0].pTab
;
4011 pExpr
= p
->pEList
->a
[0].pExpr
;
4012 assert( pTab
&& !pTab
->pSelect
&& pExpr
);
4014 if( IsVirtual(pTab
) ) return 0;
4015 if( pExpr
->op
!=TK_AGG_FUNCTION
) return 0;
4016 if( NEVER(pAggInfo
->nFunc
==0) ) return 0;
4017 if( (pAggInfo
->aFunc
[0].pFunc
->funcFlags
&SQLITE_FUNC_COUNT
)==0 ) return 0;
4018 if( pExpr
->flags
&EP_Distinct
) return 0;
4024 ** If the source-list item passed as an argument was augmented with an
4025 ** INDEXED BY clause, then try to locate the specified index. If there
4026 ** was such a clause and the named index cannot be found, return
4027 ** SQLITE_ERROR and leave an error in pParse. Otherwise, populate
4028 ** pFrom->pIndex and return SQLITE_OK.
4030 int sqlite3IndexedByLookup(Parse
*pParse
, struct SrcList_item
*pFrom
){
4031 if( pFrom
->pTab
&& pFrom
->fg
.isIndexedBy
){
4032 Table
*pTab
= pFrom
->pTab
;
4033 char *zIndexedBy
= pFrom
->u1
.zIndexedBy
;
4035 for(pIdx
=pTab
->pIndex
;
4036 pIdx
&& sqlite3StrICmp(pIdx
->zName
, zIndexedBy
);
4040 sqlite3ErrorMsg(pParse
, "no such index: %s", zIndexedBy
, 0);
4041 pParse
->checkSchema
= 1;
4042 return SQLITE_ERROR
;
4044 pFrom
->pIBIndex
= pIdx
;
4049 ** Detect compound SELECT statements that use an ORDER BY clause with
4050 ** an alternative collating sequence.
4052 ** SELECT ... FROM t1 EXCEPT SELECT ... FROM t2 ORDER BY .. COLLATE ...
4054 ** These are rewritten as a subquery:
4056 ** SELECT * FROM (SELECT ... FROM t1 EXCEPT SELECT ... FROM t2)
4057 ** ORDER BY ... COLLATE ...
4059 ** This transformation is necessary because the multiSelectOrderBy() routine
4060 ** above that generates the code for a compound SELECT with an ORDER BY clause
4061 ** uses a merge algorithm that requires the same collating sequence on the
4062 ** result columns as on the ORDER BY clause. See ticket
4063 ** http://www.sqlite.org/src/info/6709574d2a
4065 ** This transformation is only needed for EXCEPT, INTERSECT, and UNION.
4066 ** The UNION ALL operator works fine with multiSelectOrderBy() even when
4067 ** there are COLLATE terms in the ORDER BY.
4069 static int convertCompoundSelectToSubquery(Walker
*pWalker
, Select
*p
){
4074 struct ExprList_item
*a
;
4079 if( p
->pPrior
==0 ) return WRC_Continue
;
4080 if( p
->pOrderBy
==0 ) return WRC_Continue
;
4081 for(pX
=p
; pX
&& (pX
->op
==TK_ALL
|| pX
->op
==TK_SELECT
); pX
=pX
->pPrior
){}
4082 if( pX
==0 ) return WRC_Continue
;
4084 for(i
=p
->pOrderBy
->nExpr
-1; i
>=0; i
--){
4085 if( a
[i
].pExpr
->flags
& EP_Collate
) break;
4087 if( i
<0 ) return WRC_Continue
;
4089 /* If we reach this point, that means the transformation is required. */
4091 pParse
= pWalker
->pParse
;
4093 pNew
= sqlite3DbMallocZero(db
, sizeof(*pNew
) );
4094 if( pNew
==0 ) return WRC_Abort
;
4095 memset(&dummy
, 0, sizeof(dummy
));
4096 pNewSrc
= sqlite3SrcListAppendFromTerm(pParse
,0,0,0,&dummy
,pNew
,0,0);
4097 if( pNewSrc
==0 ) return WRC_Abort
;
4100 p
->pEList
= sqlite3ExprListAppend(pParse
, 0, sqlite3Expr(db
, TK_ASTERISK
, 0));
4109 p
->selFlags
&= ~SF_Compound
;
4110 assert( (p
->selFlags
& SF_Converted
)==0 );
4111 p
->selFlags
|= SF_Converted
;
4112 assert( pNew
->pPrior
!=0 );
4113 pNew
->pPrior
->pNext
= pNew
;
4115 return WRC_Continue
;
4119 ** Check to see if the FROM clause term pFrom has table-valued function
4120 ** arguments. If it does, leave an error message in pParse and return
4121 ** non-zero, since pFrom is not allowed to be a table-valued function.
4123 static int cannotBeFunction(Parse
*pParse
, struct SrcList_item
*pFrom
){
4124 if( pFrom
->fg
.isTabFunc
){
4125 sqlite3ErrorMsg(pParse
, "'%s' is not a function", pFrom
->zName
);
4131 #ifndef SQLITE_OMIT_CTE
4133 ** Argument pWith (which may be NULL) points to a linked list of nested
4134 ** WITH contexts, from inner to outermost. If the table identified by
4135 ** FROM clause element pItem is really a common-table-expression (CTE)
4136 ** then return a pointer to the CTE definition for that table. Otherwise
4139 ** If a non-NULL value is returned, set *ppContext to point to the With
4140 ** object that the returned CTE belongs to.
4142 static struct Cte
*searchWith(
4143 With
*pWith
, /* Current innermost WITH clause */
4144 struct SrcList_item
*pItem
, /* FROM clause element to resolve */
4145 With
**ppContext
/* OUT: WITH clause return value belongs to */
4148 if( pItem
->zDatabase
==0 && (zName
= pItem
->zName
)!=0 ){
4150 for(p
=pWith
; p
; p
=p
->pOuter
){
4152 for(i
=0; i
<p
->nCte
; i
++){
4153 if( sqlite3StrICmp(zName
, p
->a
[i
].zName
)==0 ){
4163 /* The code generator maintains a stack of active WITH clauses
4164 ** with the inner-most WITH clause being at the top of the stack.
4166 ** This routine pushes the WITH clause passed as the second argument
4167 ** onto the top of the stack. If argument bFree is true, then this
4168 ** WITH clause will never be popped from the stack. In this case it
4169 ** should be freed along with the Parse object. In other cases, when
4170 ** bFree==0, the With object will be freed along with the SELECT
4171 ** statement with which it is associated.
4173 void sqlite3WithPush(Parse
*pParse
, With
*pWith
, u8 bFree
){
4174 assert( bFree
==0 || (pParse
->pWith
==0 && pParse
->pWithToFree
==0) );
4176 assert( pParse
->pWith
!=pWith
);
4177 pWith
->pOuter
= pParse
->pWith
;
4178 pParse
->pWith
= pWith
;
4179 if( bFree
) pParse
->pWithToFree
= pWith
;
4184 ** This function checks if argument pFrom refers to a CTE declared by
4185 ** a WITH clause on the stack currently maintained by the parser. And,
4186 ** if currently processing a CTE expression, if it is a recursive
4187 ** reference to the current CTE.
4189 ** If pFrom falls into either of the two categories above, pFrom->pTab
4190 ** and other fields are populated accordingly. The caller should check
4191 ** (pFrom->pTab!=0) to determine whether or not a successful match
4194 ** Whether or not a match is found, SQLITE_OK is returned if no error
4195 ** occurs. If an error does occur, an error message is stored in the
4196 ** parser and some error code other than SQLITE_OK returned.
4198 static int withExpand(
4200 struct SrcList_item
*pFrom
4202 Parse
*pParse
= pWalker
->pParse
;
4203 sqlite3
*db
= pParse
->db
;
4204 struct Cte
*pCte
; /* Matched CTE (or NULL if no match) */
4205 With
*pWith
; /* WITH clause that pCte belongs to */
4207 assert( pFrom
->pTab
==0 );
4209 pCte
= searchWith(pParse
->pWith
, pFrom
, &pWith
);
4214 Select
*pLeft
; /* Left-most SELECT statement */
4215 int bMayRecursive
; /* True if compound joined by UNION [ALL] */
4216 With
*pSavedWith
; /* Initial value of pParse->pWith */
4218 /* If pCte->zCteErr is non-NULL at this point, then this is an illegal
4219 ** recursive reference to CTE pCte. Leave an error in pParse and return
4220 ** early. If pCte->zCteErr is NULL, then this is not a recursive reference.
4221 ** In this case, proceed. */
4222 if( pCte
->zCteErr
){
4223 sqlite3ErrorMsg(pParse
, pCte
->zCteErr
, pCte
->zName
);
4224 return SQLITE_ERROR
;
4226 if( cannotBeFunction(pParse
, pFrom
) ) return SQLITE_ERROR
;
4228 assert( pFrom
->pTab
==0 );
4229 pFrom
->pTab
= pTab
= sqlite3DbMallocZero(db
, sizeof(Table
));
4230 if( pTab
==0 ) return WRC_Abort
;
4232 pTab
->zName
= sqlite3DbStrDup(db
, pCte
->zName
);
4234 pTab
->nRowLogEst
= 200; assert( 200==sqlite3LogEst(1048576) );
4235 pTab
->tabFlags
|= TF_Ephemeral
| TF_NoVisibleRowid
;
4236 pFrom
->pSelect
= sqlite3SelectDup(db
, pCte
->pSelect
, 0);
4237 if( db
->mallocFailed
) return SQLITE_NOMEM_BKPT
;
4238 assert( pFrom
->pSelect
);
4240 /* Check if this is a recursive CTE. */
4241 pSel
= pFrom
->pSelect
;
4242 bMayRecursive
= ( pSel
->op
==TK_ALL
|| pSel
->op
==TK_UNION
);
4243 if( bMayRecursive
){
4245 SrcList
*pSrc
= pFrom
->pSelect
->pSrc
;
4246 for(i
=0; i
<pSrc
->nSrc
; i
++){
4247 struct SrcList_item
*pItem
= &pSrc
->a
[i
];
4248 if( pItem
->zDatabase
==0
4250 && 0==sqlite3StrICmp(pItem
->zName
, pCte
->zName
)
4253 pItem
->fg
.isRecursive
= 1;
4255 pSel
->selFlags
|= SF_Recursive
;
4260 /* Only one recursive reference is permitted. */
4261 if( pTab
->nTabRef
>2 ){
4263 pParse
, "multiple references to recursive table: %s", pCte
->zName
4265 return SQLITE_ERROR
;
4267 assert( pTab
->nTabRef
==1 ||
4268 ((pSel
->selFlags
&SF_Recursive
) && pTab
->nTabRef
==2 ));
4270 pCte
->zCteErr
= "circular reference: %s";
4271 pSavedWith
= pParse
->pWith
;
4272 pParse
->pWith
= pWith
;
4273 if( bMayRecursive
){
4274 Select
*pPrior
= pSel
->pPrior
;
4275 assert( pPrior
->pWith
==0 );
4276 pPrior
->pWith
= pSel
->pWith
;
4277 sqlite3WalkSelect(pWalker
, pPrior
);
4280 sqlite3WalkSelect(pWalker
, pSel
);
4282 pParse
->pWith
= pWith
;
4284 for(pLeft
=pSel
; pLeft
->pPrior
; pLeft
=pLeft
->pPrior
);
4285 pEList
= pLeft
->pEList
;
4287 if( pEList
&& pEList
->nExpr
!=pCte
->pCols
->nExpr
){
4288 sqlite3ErrorMsg(pParse
, "table %s has %d values for %d columns",
4289 pCte
->zName
, pEList
->nExpr
, pCte
->pCols
->nExpr
4291 pParse
->pWith
= pSavedWith
;
4292 return SQLITE_ERROR
;
4294 pEList
= pCte
->pCols
;
4297 sqlite3ColumnsFromExprList(pParse
, pEList
, &pTab
->nCol
, &pTab
->aCol
);
4298 if( bMayRecursive
){
4299 if( pSel
->selFlags
& SF_Recursive
){
4300 pCte
->zCteErr
= "multiple recursive references: %s";
4302 pCte
->zCteErr
= "recursive reference in a subquery: %s";
4304 sqlite3WalkSelect(pWalker
, pSel
);
4307 pParse
->pWith
= pSavedWith
;
4314 #ifndef SQLITE_OMIT_CTE
4316 ** If the SELECT passed as the second argument has an associated WITH
4317 ** clause, pop it from the stack stored as part of the Parse object.
4319 ** This function is used as the xSelectCallback2() callback by
4320 ** sqlite3SelectExpand() when walking a SELECT tree to resolve table
4321 ** names and other FROM clause elements.
4323 static void selectPopWith(Walker
*pWalker
, Select
*p
){
4324 Parse
*pParse
= pWalker
->pParse
;
4325 if( OK_IF_ALWAYS_TRUE(pParse
->pWith
) && p
->pPrior
==0 ){
4326 With
*pWith
= findRightmost(p
)->pWith
;
4328 assert( pParse
->pWith
==pWith
);
4329 pParse
->pWith
= pWith
->pOuter
;
4334 #define selectPopWith 0
4338 ** This routine is a Walker callback for "expanding" a SELECT statement.
4339 ** "Expanding" means to do the following:
4341 ** (1) Make sure VDBE cursor numbers have been assigned to every
4342 ** element of the FROM clause.
4344 ** (2) Fill in the pTabList->a[].pTab fields in the SrcList that
4345 ** defines FROM clause. When views appear in the FROM clause,
4346 ** fill pTabList->a[].pSelect with a copy of the SELECT statement
4347 ** that implements the view. A copy is made of the view's SELECT
4348 ** statement so that we can freely modify or delete that statement
4349 ** without worrying about messing up the persistent representation
4352 ** (3) Add terms to the WHERE clause to accommodate the NATURAL keyword
4353 ** on joins and the ON and USING clause of joins.
4355 ** (4) Scan the list of columns in the result set (pEList) looking
4356 ** for instances of the "*" operator or the TABLE.* operator.
4357 ** If found, expand each "*" to be every column in every table
4358 ** and TABLE.* to be every column in TABLE.
4361 static int selectExpander(Walker
*pWalker
, Select
*p
){
4362 Parse
*pParse
= pWalker
->pParse
;
4366 struct SrcList_item
*pFrom
;
4367 sqlite3
*db
= pParse
->db
;
4368 Expr
*pE
, *pRight
, *pExpr
;
4369 u16 selFlags
= p
->selFlags
;
4372 p
->selFlags
|= SF_Expanded
;
4373 if( db
->mallocFailed
){
4376 assert( p
->pSrc
!=0 );
4377 if( (selFlags
& SF_Expanded
)!=0 ){
4382 if( OK_IF_ALWAYS_TRUE(p
->pWith
) ){
4383 sqlite3WithPush(pParse
, p
->pWith
, 0);
4386 /* Make sure cursor numbers have been assigned to all entries in
4387 ** the FROM clause of the SELECT statement.
4389 sqlite3SrcListAssignCursors(pParse
, pTabList
);
4391 /* Look up every table named in the FROM clause of the select. If
4392 ** an entry of the FROM clause is a subquery instead of a table or view,
4393 ** then create a transient table structure to describe the subquery.
4395 for(i
=0, pFrom
=pTabList
->a
; i
<pTabList
->nSrc
; i
++, pFrom
++){
4397 assert( pFrom
->fg
.isRecursive
==0 || pFrom
->pTab
!=0 );
4398 if( pFrom
->fg
.isRecursive
) continue;
4399 assert( pFrom
->pTab
==0 );
4400 #ifndef SQLITE_OMIT_CTE
4401 if( withExpand(pWalker
, pFrom
) ) return WRC_Abort
;
4402 if( pFrom
->pTab
) {} else
4404 if( pFrom
->zName
==0 ){
4405 #ifndef SQLITE_OMIT_SUBQUERY
4406 Select
*pSel
= pFrom
->pSelect
;
4407 /* A sub-query in the FROM clause of a SELECT */
4409 assert( pFrom
->pTab
==0 );
4410 if( sqlite3WalkSelect(pWalker
, pSel
) ) return WRC_Abort
;
4411 pFrom
->pTab
= pTab
= sqlite3DbMallocZero(db
, sizeof(Table
));
4412 if( pTab
==0 ) return WRC_Abort
;
4414 if( pFrom
->zAlias
){
4415 pTab
->zName
= sqlite3DbStrDup(db
, pFrom
->zAlias
);
4417 pTab
->zName
= sqlite3MPrintf(db
, "subquery_%p", (void*)pTab
);
4419 while( pSel
->pPrior
){ pSel
= pSel
->pPrior
; }
4420 sqlite3ColumnsFromExprList(pParse
, pSel
->pEList
,&pTab
->nCol
,&pTab
->aCol
);
4422 pTab
->nRowLogEst
= 200; assert( 200==sqlite3LogEst(1048576) );
4423 pTab
->tabFlags
|= TF_Ephemeral
;
4426 /* An ordinary table or view name in the FROM clause */
4427 assert( pFrom
->pTab
==0 );
4428 pFrom
->pTab
= pTab
= sqlite3LocateTableItem(pParse
, 0, pFrom
);
4429 if( pTab
==0 ) return WRC_Abort
;
4430 if( pTab
->nTabRef
>=0xffff ){
4431 sqlite3ErrorMsg(pParse
, "too many references to \"%s\": max 65535",
4437 if( !IsVirtual(pTab
) && cannotBeFunction(pParse
, pFrom
) ){
4440 #if !defined(SQLITE_OMIT_VIEW) || !defined (SQLITE_OMIT_VIRTUALTABLE)
4441 if( IsVirtual(pTab
) || pTab
->pSelect
){
4443 if( sqlite3ViewGetColumnNames(pParse
, pTab
) ) return WRC_Abort
;
4444 assert( pFrom
->pSelect
==0 );
4445 pFrom
->pSelect
= sqlite3SelectDup(db
, pTab
->pSelect
, 0);
4446 sqlite3SelectSetName(pFrom
->pSelect
, pTab
->zName
);
4449 sqlite3WalkSelect(pWalker
, pFrom
->pSelect
);
4455 /* Locate the index named by the INDEXED BY clause, if any. */
4456 if( sqlite3IndexedByLookup(pParse
, pFrom
) ){
4461 /* Process NATURAL keywords, and ON and USING clauses of joins.
4463 if( db
->mallocFailed
|| sqliteProcessJoin(pParse
, p
) ){
4467 /* For every "*" that occurs in the column list, insert the names of
4468 ** all columns in all tables. And for every TABLE.* insert the names
4469 ** of all columns in TABLE. The parser inserted a special expression
4470 ** with the TK_ASTERISK operator for each "*" that it found in the column
4471 ** list. The following code just has to locate the TK_ASTERISK
4472 ** expressions and expand each one to the list of all columns in
4475 ** The first loop just checks to see if there are any "*" operators
4476 ** that need expanding.
4478 for(k
=0; k
<pEList
->nExpr
; k
++){
4479 pE
= pEList
->a
[k
].pExpr
;
4480 if( pE
->op
==TK_ASTERISK
) break;
4481 assert( pE
->op
!=TK_DOT
|| pE
->pRight
!=0 );
4482 assert( pE
->op
!=TK_DOT
|| (pE
->pLeft
!=0 && pE
->pLeft
->op
==TK_ID
) );
4483 if( pE
->op
==TK_DOT
&& pE
->pRight
->op
==TK_ASTERISK
) break;
4484 elistFlags
|= pE
->flags
;
4486 if( k
<pEList
->nExpr
){
4488 ** If we get here it means the result set contains one or more "*"
4489 ** operators that need to be expanded. Loop through each expression
4490 ** in the result set and expand them one by one.
4492 struct ExprList_item
*a
= pEList
->a
;
4494 int flags
= pParse
->db
->flags
;
4495 int longNames
= (flags
& SQLITE_FullColNames
)!=0
4496 && (flags
& SQLITE_ShortColNames
)==0;
4498 for(k
=0; k
<pEList
->nExpr
; k
++){
4500 elistFlags
|= pE
->flags
;
4501 pRight
= pE
->pRight
;
4502 assert( pE
->op
!=TK_DOT
|| pRight
!=0 );
4503 if( pE
->op
!=TK_ASTERISK
4504 && (pE
->op
!=TK_DOT
|| pRight
->op
!=TK_ASTERISK
)
4506 /* This particular expression does not need to be expanded.
4508 pNew
= sqlite3ExprListAppend(pParse
, pNew
, a
[k
].pExpr
);
4510 pNew
->a
[pNew
->nExpr
-1].zName
= a
[k
].zName
;
4511 pNew
->a
[pNew
->nExpr
-1].zSpan
= a
[k
].zSpan
;
4517 /* This expression is a "*" or a "TABLE.*" and needs to be
4519 int tableSeen
= 0; /* Set to 1 when TABLE matches */
4520 char *zTName
= 0; /* text of name of TABLE */
4521 if( pE
->op
==TK_DOT
){
4522 assert( pE
->pLeft
!=0 );
4523 assert( !ExprHasProperty(pE
->pLeft
, EP_IntValue
) );
4524 zTName
= pE
->pLeft
->u
.zToken
;
4526 for(i
=0, pFrom
=pTabList
->a
; i
<pTabList
->nSrc
; i
++, pFrom
++){
4527 Table
*pTab
= pFrom
->pTab
;
4528 Select
*pSub
= pFrom
->pSelect
;
4529 char *zTabName
= pFrom
->zAlias
;
4530 const char *zSchemaName
= 0;
4533 zTabName
= pTab
->zName
;
4535 if( db
->mallocFailed
) break;
4536 if( pSub
==0 || (pSub
->selFlags
& SF_NestedFrom
)==0 ){
4538 if( zTName
&& sqlite3StrICmp(zTName
, zTabName
)!=0 ){
4541 iDb
= sqlite3SchemaToIndex(db
, pTab
->pSchema
);
4542 zSchemaName
= iDb
>=0 ? db
->aDb
[iDb
].zDbSName
: "*";
4544 for(j
=0; j
<pTab
->nCol
; j
++){
4545 char *zName
= pTab
->aCol
[j
].zName
;
4546 char *zColname
; /* The computed column name */
4547 char *zToFree
; /* Malloced string that needs to be freed */
4548 Token sColname
; /* Computed column name as a token */
4552 && sqlite3MatchSpanName(pSub
->pEList
->a
[j
].zSpan
, 0, zTName
, 0)==0
4557 /* If a column is marked as 'hidden', omit it from the expanded
4558 ** result-set list unless the SELECT has the SF_IncludeHidden
4561 if( (p
->selFlags
& SF_IncludeHidden
)==0
4562 && IsHiddenColumn(&pTab
->aCol
[j
])
4568 if( i
>0 && zTName
==0 ){
4569 if( (pFrom
->fg
.jointype
& JT_NATURAL
)!=0
4570 && tableAndColumnIndex(pTabList
, i
, zName
, 0, 0)
4572 /* In a NATURAL join, omit the join columns from the
4573 ** table to the right of the join */
4576 if( sqlite3IdListIndex(pFrom
->pUsing
, zName
)>=0 ){
4577 /* In a join with a USING clause, omit columns in the
4578 ** using clause from the table on the right. */
4582 pRight
= sqlite3Expr(db
, TK_ID
, zName
);
4585 if( longNames
|| pTabList
->nSrc
>1 ){
4587 pLeft
= sqlite3Expr(db
, TK_ID
, zTabName
);
4588 pExpr
= sqlite3PExpr(pParse
, TK_DOT
, pLeft
, pRight
);
4590 pLeft
= sqlite3Expr(db
, TK_ID
, zSchemaName
);
4591 pExpr
= sqlite3PExpr(pParse
, TK_DOT
, pLeft
, pExpr
);
4594 zColname
= sqlite3MPrintf(db
, "%s.%s", zTabName
, zName
);
4600 pNew
= sqlite3ExprListAppend(pParse
, pNew
, pExpr
);
4601 sqlite3TokenInit(&sColname
, zColname
);
4602 sqlite3ExprListSetName(pParse
, pNew
, &sColname
, 0);
4603 if( pNew
&& (p
->selFlags
& SF_NestedFrom
)!=0 ){
4604 struct ExprList_item
*pX
= &pNew
->a
[pNew
->nExpr
-1];
4606 pX
->zSpan
= sqlite3DbStrDup(db
, pSub
->pEList
->a
[j
].zSpan
);
4607 testcase( pX
->zSpan
==0 );
4609 pX
->zSpan
= sqlite3MPrintf(db
, "%s.%s.%s",
4610 zSchemaName
, zTabName
, zColname
);
4611 testcase( pX
->zSpan
==0 );
4615 sqlite3DbFree(db
, zToFree
);
4620 sqlite3ErrorMsg(pParse
, "no such table: %s", zTName
);
4622 sqlite3ErrorMsg(pParse
, "no tables specified");
4627 sqlite3ExprListDelete(db
, pEList
);
4631 if( p
->pEList
->nExpr
>db
->aLimit
[SQLITE_LIMIT_COLUMN
] ){
4632 sqlite3ErrorMsg(pParse
, "too many columns in result set");
4635 if( (elistFlags
& (EP_HasFunc
|EP_Subquery
))!=0 ){
4636 p
->selFlags
|= SF_ComplexResult
;
4639 return WRC_Continue
;
4643 ** No-op routine for the parse-tree walker.
4645 ** When this routine is the Walker.xExprCallback then expression trees
4646 ** are walked without any actions being taken at each node. Presumably,
4647 ** when this routine is used for Walker.xExprCallback then
4648 ** Walker.xSelectCallback is set to do something useful for every
4649 ** subquery in the parser tree.
4651 int sqlite3ExprWalkNoop(Walker
*NotUsed
, Expr
*NotUsed2
){
4652 UNUSED_PARAMETER2(NotUsed
, NotUsed2
);
4653 return WRC_Continue
;
4657 ** No-op routine for the parse-tree walker for SELECT statements.
4658 ** subquery in the parser tree.
4660 int sqlite3SelectWalkNoop(Walker
*NotUsed
, Select
*NotUsed2
){
4661 UNUSED_PARAMETER2(NotUsed
, NotUsed2
);
4662 return WRC_Continue
;
4667 ** Always assert. This xSelectCallback2 implementation proves that the
4668 ** xSelectCallback2 is never invoked.
4670 void sqlite3SelectWalkAssert2(Walker
*NotUsed
, Select
*NotUsed2
){
4671 UNUSED_PARAMETER2(NotUsed
, NotUsed2
);
4676 ** This routine "expands" a SELECT statement and all of its subqueries.
4677 ** For additional information on what it means to "expand" a SELECT
4678 ** statement, see the comment on the selectExpand worker callback above.
4680 ** Expanding a SELECT statement is the first step in processing a
4681 ** SELECT statement. The SELECT statement must be expanded before
4682 ** name resolution is performed.
4684 ** If anything goes wrong, an error message is written into pParse.
4685 ** The calling function can detect the problem by looking at pParse->nErr
4686 ** and/or pParse->db->mallocFailed.
4688 static void sqlite3SelectExpand(Parse
*pParse
, Select
*pSelect
){
4690 w
.xExprCallback
= sqlite3ExprWalkNoop
;
4692 if( OK_IF_ALWAYS_TRUE(pParse
->hasCompound
) ){
4693 w
.xSelectCallback
= convertCompoundSelectToSubquery
;
4694 w
.xSelectCallback2
= 0;
4695 sqlite3WalkSelect(&w
, pSelect
);
4697 w
.xSelectCallback
= selectExpander
;
4698 w
.xSelectCallback2
= selectPopWith
;
4699 sqlite3WalkSelect(&w
, pSelect
);
4703 #ifndef SQLITE_OMIT_SUBQUERY
4705 ** This is a Walker.xSelectCallback callback for the sqlite3SelectTypeInfo()
4708 ** For each FROM-clause subquery, add Column.zType and Column.zColl
4709 ** information to the Table structure that represents the result set
4710 ** of that subquery.
4712 ** The Table structure that represents the result set was constructed
4713 ** by selectExpander() but the type and collation information was omitted
4714 ** at that point because identifiers had not yet been resolved. This
4715 ** routine is called after identifier resolution.
4717 static void selectAddSubqueryTypeInfo(Walker
*pWalker
, Select
*p
){
4721 struct SrcList_item
*pFrom
;
4723 assert( p
->selFlags
& SF_Resolved
);
4724 assert( (p
->selFlags
& SF_HasTypeInfo
)==0 );
4725 p
->selFlags
|= SF_HasTypeInfo
;
4726 pParse
= pWalker
->pParse
;
4728 for(i
=0, pFrom
=pTabList
->a
; i
<pTabList
->nSrc
; i
++, pFrom
++){
4729 Table
*pTab
= pFrom
->pTab
;
4731 if( (pTab
->tabFlags
& TF_Ephemeral
)!=0 ){
4732 /* A sub-query in the FROM clause of a SELECT */
4733 Select
*pSel
= pFrom
->pSelect
;
4735 while( pSel
->pPrior
) pSel
= pSel
->pPrior
;
4736 sqlite3SelectAddColumnTypeAndCollation(pParse
, pTab
, pSel
);
4745 ** This routine adds datatype and collating sequence information to
4746 ** the Table structures of all FROM-clause subqueries in a
4747 ** SELECT statement.
4749 ** Use this routine after name resolution.
4751 static void sqlite3SelectAddTypeInfo(Parse
*pParse
, Select
*pSelect
){
4752 #ifndef SQLITE_OMIT_SUBQUERY
4754 w
.xSelectCallback
= sqlite3SelectWalkNoop
;
4755 w
.xSelectCallback2
= selectAddSubqueryTypeInfo
;
4756 w
.xExprCallback
= sqlite3ExprWalkNoop
;
4758 sqlite3WalkSelect(&w
, pSelect
);
4764 ** This routine sets up a SELECT statement for processing. The
4765 ** following is accomplished:
4767 ** * VDBE Cursor numbers are assigned to all FROM-clause terms.
4768 ** * Ephemeral Table objects are created for all FROM-clause subqueries.
4769 ** * ON and USING clauses are shifted into WHERE statements
4770 ** * Wildcards "*" and "TABLE.*" in result sets are expanded.
4771 ** * Identifiers in expression are matched to tables.
4773 ** This routine acts recursively on all subqueries within the SELECT.
4775 void sqlite3SelectPrep(
4776 Parse
*pParse
, /* The parser context */
4777 Select
*p
, /* The SELECT statement being coded. */
4778 NameContext
*pOuterNC
/* Name context for container */
4780 assert( p
!=0 || pParse
->db
->mallocFailed
);
4781 if( pParse
->db
->mallocFailed
) return;
4782 if( p
->selFlags
& SF_HasTypeInfo
) return;
4783 sqlite3SelectExpand(pParse
, p
);
4784 if( pParse
->nErr
|| pParse
->db
->mallocFailed
) return;
4785 sqlite3ResolveSelectNames(pParse
, p
, pOuterNC
);
4786 if( pParse
->nErr
|| pParse
->db
->mallocFailed
) return;
4787 sqlite3SelectAddTypeInfo(pParse
, p
);
4791 ** Reset the aggregate accumulator.
4793 ** The aggregate accumulator is a set of memory cells that hold
4794 ** intermediate results while calculating an aggregate. This
4795 ** routine generates code that stores NULLs in all of those memory
4798 static void resetAccumulator(Parse
*pParse
, AggInfo
*pAggInfo
){
4799 Vdbe
*v
= pParse
->pVdbe
;
4801 struct AggInfo_func
*pFunc
;
4802 int nReg
= pAggInfo
->nFunc
+ pAggInfo
->nColumn
;
4803 if( nReg
==0 ) return;
4805 /* Verify that all AggInfo registers are within the range specified by
4806 ** AggInfo.mnReg..AggInfo.mxReg */
4807 assert( nReg
==pAggInfo
->mxReg
-pAggInfo
->mnReg
+1 );
4808 for(i
=0; i
<pAggInfo
->nColumn
; i
++){
4809 assert( pAggInfo
->aCol
[i
].iMem
>=pAggInfo
->mnReg
4810 && pAggInfo
->aCol
[i
].iMem
<=pAggInfo
->mxReg
);
4812 for(i
=0; i
<pAggInfo
->nFunc
; i
++){
4813 assert( pAggInfo
->aFunc
[i
].iMem
>=pAggInfo
->mnReg
4814 && pAggInfo
->aFunc
[i
].iMem
<=pAggInfo
->mxReg
);
4817 sqlite3VdbeAddOp3(v
, OP_Null
, 0, pAggInfo
->mnReg
, pAggInfo
->mxReg
);
4818 for(pFunc
=pAggInfo
->aFunc
, i
=0; i
<pAggInfo
->nFunc
; i
++, pFunc
++){
4819 if( pFunc
->iDistinct
>=0 ){
4820 Expr
*pE
= pFunc
->pExpr
;
4821 assert( !ExprHasProperty(pE
, EP_xIsSelect
) );
4822 if( pE
->x
.pList
==0 || pE
->x
.pList
->nExpr
!=1 ){
4823 sqlite3ErrorMsg(pParse
, "DISTINCT aggregates must have exactly one "
4825 pFunc
->iDistinct
= -1;
4827 KeyInfo
*pKeyInfo
= keyInfoFromExprList(pParse
, pE
->x
.pList
, 0, 0);
4828 sqlite3VdbeAddOp4(v
, OP_OpenEphemeral
, pFunc
->iDistinct
, 0, 0,
4829 (char*)pKeyInfo
, P4_KEYINFO
);
4836 ** Invoke the OP_AggFinalize opcode for every aggregate function
4837 ** in the AggInfo structure.
4839 static void finalizeAggFunctions(Parse
*pParse
, AggInfo
*pAggInfo
){
4840 Vdbe
*v
= pParse
->pVdbe
;
4842 struct AggInfo_func
*pF
;
4843 for(i
=0, pF
=pAggInfo
->aFunc
; i
<pAggInfo
->nFunc
; i
++, pF
++){
4844 ExprList
*pList
= pF
->pExpr
->x
.pList
;
4845 assert( !ExprHasProperty(pF
->pExpr
, EP_xIsSelect
) );
4846 sqlite3VdbeAddOp2(v
, OP_AggFinal
, pF
->iMem
, pList
? pList
->nExpr
: 0);
4847 sqlite3VdbeAppendP4(v
, pF
->pFunc
, P4_FUNCDEF
);
4852 ** Update the accumulator memory cells for an aggregate based on
4853 ** the current cursor position.
4855 static void updateAccumulator(Parse
*pParse
, AggInfo
*pAggInfo
){
4856 Vdbe
*v
= pParse
->pVdbe
;
4859 int addrHitTest
= 0;
4860 struct AggInfo_func
*pF
;
4861 struct AggInfo_col
*pC
;
4863 pAggInfo
->directMode
= 1;
4864 for(i
=0, pF
=pAggInfo
->aFunc
; i
<pAggInfo
->nFunc
; i
++, pF
++){
4868 ExprList
*pList
= pF
->pExpr
->x
.pList
;
4869 assert( !ExprHasProperty(pF
->pExpr
, EP_xIsSelect
) );
4871 nArg
= pList
->nExpr
;
4872 regAgg
= sqlite3GetTempRange(pParse
, nArg
);
4873 sqlite3ExprCodeExprList(pParse
, pList
, regAgg
, 0, SQLITE_ECEL_DUP
);
4878 if( pF
->iDistinct
>=0 ){
4879 addrNext
= sqlite3VdbeMakeLabel(v
);
4880 testcase( nArg
==0 ); /* Error condition */
4881 testcase( nArg
>1 ); /* Also an error */
4882 codeDistinct(pParse
, pF
->iDistinct
, addrNext
, 1, regAgg
);
4884 if( pF
->pFunc
->funcFlags
& SQLITE_FUNC_NEEDCOLL
){
4886 struct ExprList_item
*pItem
;
4888 assert( pList
!=0 ); /* pList!=0 if pF->pFunc has NEEDCOLL */
4889 for(j
=0, pItem
=pList
->a
; !pColl
&& j
<nArg
; j
++, pItem
++){
4890 pColl
= sqlite3ExprCollSeq(pParse
, pItem
->pExpr
);
4893 pColl
= pParse
->db
->pDfltColl
;
4895 if( regHit
==0 && pAggInfo
->nAccumulator
) regHit
= ++pParse
->nMem
;
4896 sqlite3VdbeAddOp4(v
, OP_CollSeq
, regHit
, 0, 0, (char *)pColl
, P4_COLLSEQ
);
4898 sqlite3VdbeAddOp3(v
, OP_AggStep0
, 0, regAgg
, pF
->iMem
);
4899 sqlite3VdbeAppendP4(v
, pF
->pFunc
, P4_FUNCDEF
);
4900 sqlite3VdbeChangeP5(v
, (u8
)nArg
);
4901 sqlite3ExprCacheAffinityChange(pParse
, regAgg
, nArg
);
4902 sqlite3ReleaseTempRange(pParse
, regAgg
, nArg
);
4904 sqlite3VdbeResolveLabel(v
, addrNext
);
4905 sqlite3ExprCacheClear(pParse
);
4909 /* Before populating the accumulator registers, clear the column cache.
4910 ** Otherwise, if any of the required column values are already present
4911 ** in registers, sqlite3ExprCode() may use OP_SCopy to copy the value
4912 ** to pC->iMem. But by the time the value is used, the original register
4913 ** may have been used, invalidating the underlying buffer holding the
4914 ** text or blob value. See ticket [883034dcb5].
4916 ** Another solution would be to change the OP_SCopy used to copy cached
4917 ** values to an OP_Copy.
4920 addrHitTest
= sqlite3VdbeAddOp1(v
, OP_If
, regHit
); VdbeCoverage(v
);
4922 sqlite3ExprCacheClear(pParse
);
4923 for(i
=0, pC
=pAggInfo
->aCol
; i
<pAggInfo
->nAccumulator
; i
++, pC
++){
4924 sqlite3ExprCode(pParse
, pC
->pExpr
, pC
->iMem
);
4926 pAggInfo
->directMode
= 0;
4927 sqlite3ExprCacheClear(pParse
);
4929 sqlite3VdbeJumpHere(v
, addrHitTest
);
4934 ** Add a single OP_Explain instruction to the VDBE to explain a simple
4935 ** count(*) query ("SELECT count(*) FROM pTab").
4937 #ifndef SQLITE_OMIT_EXPLAIN
4938 static void explainSimpleCount(
4939 Parse
*pParse
, /* Parse context */
4940 Table
*pTab
, /* Table being queried */
4941 Index
*pIdx
/* Index used to optimize scan, or NULL */
4943 if( pParse
->explain
==2 ){
4944 int bCover
= (pIdx
!=0 && (HasRowid(pTab
) || !IsPrimaryKeyIndex(pIdx
)));
4945 char *zEqp
= sqlite3MPrintf(pParse
->db
, "SCAN TABLE %s%s%s",
4947 bCover
? " USING COVERING INDEX " : "",
4948 bCover
? pIdx
->zName
: ""
4951 pParse
->pVdbe
, OP_Explain
, pParse
->iSelectId
, 0, 0, zEqp
, P4_DYNAMIC
4956 # define explainSimpleCount(a,b,c)
4960 ** sqlite3WalkExpr() callback used by havingToWhere().
4962 ** If the node passed to the callback is a TK_AND node, return
4963 ** WRC_Continue to tell sqlite3WalkExpr() to iterate through child nodes.
4965 ** Otherwise, return WRC_Prune. In this case, also check if the
4966 ** sub-expression matches the criteria for being moved to the WHERE
4967 ** clause. If so, add it to the WHERE clause and replace the sub-expression
4968 ** within the HAVING expression with a constant "1".
4970 static int havingToWhereExprCb(Walker
*pWalker
, Expr
*pExpr
){
4971 if( pExpr
->op
!=TK_AND
){
4972 Select
*pS
= pWalker
->u
.pSelect
;
4973 if( sqlite3ExprIsConstantOrGroupBy(pWalker
->pParse
, pExpr
, pS
->pGroupBy
) ){
4974 sqlite3
*db
= pWalker
->pParse
->db
;
4975 Expr
*pNew
= sqlite3ExprAlloc(db
, TK_INTEGER
, &sqlite3IntTokens
[1], 0);
4977 Expr
*pWhere
= pS
->pWhere
;
4978 SWAP(Expr
, *pNew
, *pExpr
);
4979 pNew
= sqlite3ExprAnd(db
, pWhere
, pNew
);
4986 return WRC_Continue
;
4990 ** Transfer eligible terms from the HAVING clause of a query, which is
4991 ** processed after grouping, to the WHERE clause, which is processed before
4992 ** grouping. For example, the query:
4994 ** SELECT * FROM <tables> WHERE a=? GROUP BY b HAVING b=? AND c=?
4996 ** can be rewritten as:
4998 ** SELECT * FROM <tables> WHERE a=? AND b=? GROUP BY b HAVING c=?
5000 ** A term of the HAVING expression is eligible for transfer if it consists
5001 ** entirely of constants and expressions that are also GROUP BY terms that
5002 ** use the "BINARY" collation sequence.
5004 static void havingToWhere(Parse
*pParse
, Select
*p
){
5006 memset(&sWalker
, 0, sizeof(sWalker
));
5007 sWalker
.pParse
= pParse
;
5008 sWalker
.xExprCallback
= havingToWhereExprCb
;
5009 sWalker
.u
.pSelect
= p
;
5010 sqlite3WalkExpr(&sWalker
, p
->pHaving
);
5011 #if SELECTTRACE_ENABLED
5012 if( sWalker
.eCode
&& (sqlite3SelectTrace
& 0x100)!=0 ){
5013 SELECTTRACE(0x100,pParse
,p
,("Move HAVING terms into WHERE:\n"));
5014 sqlite3TreeViewSelect(0, p
, 0);
5020 ** Check to see if the pThis entry of pTabList is a self-join of a prior view.
5021 ** If it is, then return the SrcList_item for the prior view. If it is not,
5024 static struct SrcList_item
*isSelfJoinView(
5025 SrcList
*pTabList
, /* Search for self-joins in this FROM clause */
5026 struct SrcList_item
*pThis
/* Search for prior reference to this subquery */
5028 struct SrcList_item
*pItem
;
5029 for(pItem
= pTabList
->a
; pItem
<pThis
; pItem
++){
5030 if( pItem
->pSelect
==0 ) continue;
5031 if( pItem
->fg
.viaCoroutine
) continue;
5032 if( pItem
->zName
==0 ) continue;
5033 if( sqlite3_stricmp(pItem
->zDatabase
, pThis
->zDatabase
)!=0 ) continue;
5034 if( sqlite3_stricmp(pItem
->zName
, pThis
->zName
)!=0 ) continue;
5035 if( sqlite3ExprCompare(0,
5036 pThis
->pSelect
->pWhere
, pItem
->pSelect
->pWhere
, -1)
5038 /* The view was modified by some other optimization such as
5039 ** pushDownWhereTerms() */
5047 #ifdef SQLITE_COUNTOFVIEW_OPTIMIZATION
5049 ** Attempt to transform a query of the form
5051 ** SELECT count(*) FROM (SELECT x FROM t1 UNION ALL SELECT y FROM t2)
5055 ** SELECT (SELECT count(*) FROM t1)+(SELECT count(*) FROM t2)
5057 ** The transformation only works if all of the following are true:
5059 ** * The subquery is a UNION ALL of two or more terms
5060 ** * There is no WHERE or GROUP BY or HAVING clauses on the subqueries
5061 ** * The outer query is a simple count(*)
5063 ** Return TRUE if the optimization is undertaken.
5065 static int countOfViewOptimization(Parse
*pParse
, Select
*p
){
5066 Select
*pSub
, *pPrior
;
5070 if( (p
->selFlags
& SF_Aggregate
)==0 ) return 0; /* This is an aggregate */
5071 if( p
->pEList
->nExpr
!=1 ) return 0; /* Single result column */
5072 pExpr
= p
->pEList
->a
[0].pExpr
;
5073 if( pExpr
->op
!=TK_AGG_FUNCTION
) return 0; /* Result is an aggregate */
5074 if( sqlite3_stricmp(pExpr
->u
.zToken
,"count") ) return 0; /* Is count() */
5075 if( pExpr
->x
.pList
!=0 ) return 0; /* Must be count(*) */
5076 if( p
->pSrc
->nSrc
!=1 ) return 0; /* One table in FROM */
5077 pSub
= p
->pSrc
->a
[0].pSelect
;
5078 if( pSub
==0 ) return 0; /* The FROM is a subquery */
5079 if( pSub
->pPrior
==0 ) return 0; /* Must be a compound ry */
5081 if( pSub
->op
!=TK_ALL
&& pSub
->pPrior
) return 0; /* Must be UNION ALL */
5082 if( pSub
->pWhere
) return 0; /* No WHERE clause */
5083 if( pSub
->selFlags
& SF_Aggregate
) return 0; /* Not an aggregate */
5084 pSub
= pSub
->pPrior
; /* Repeat over compound */
5087 /* If we reach this point then it is OK to perform the transformation */
5092 pSub
= p
->pSrc
->a
[0].pSelect
;
5093 p
->pSrc
->a
[0].pSelect
= 0;
5094 sqlite3SrcListDelete(db
, p
->pSrc
);
5095 p
->pSrc
= sqlite3DbMallocZero(pParse
->db
, sizeof(*p
->pSrc
));
5098 pPrior
= pSub
->pPrior
;
5101 pSub
->selFlags
|= SF_Aggregate
;
5102 pSub
->selFlags
&= ~SF_Compound
;
5103 pSub
->nSelectRow
= 0;
5104 sqlite3ExprListDelete(db
, pSub
->pEList
);
5105 pTerm
= pPrior
? sqlite3ExprDup(db
, pCount
, 0) : pCount
;
5106 pSub
->pEList
= sqlite3ExprListAppend(pParse
, 0, pTerm
);
5107 pTerm
= sqlite3PExpr(pParse
, TK_SELECT
, 0, 0);
5108 sqlite3PExprAddSelect(pParse
, pTerm
, pSub
);
5112 pExpr
= sqlite3PExpr(pParse
, TK_PLUS
, pTerm
, pExpr
);
5116 p
->pEList
->a
[0].pExpr
= pExpr
;
5117 p
->selFlags
&= ~SF_Aggregate
;
5119 #if SELECTTRACE_ENABLED
5120 if( sqlite3SelectTrace
& 0x400 ){
5121 SELECTTRACE(0x400,pParse
,p
,("After count-of-view optimization:\n"));
5122 sqlite3TreeViewSelect(0, p
, 0);
5127 #endif /* SQLITE_COUNTOFVIEW_OPTIMIZATION */
5130 ** Generate code for the SELECT statement given in the p argument.
5132 ** The results are returned according to the SelectDest structure.
5133 ** See comments in sqliteInt.h for further information.
5135 ** This routine returns the number of errors. If any errors are
5136 ** encountered, then an appropriate error message is left in
5139 ** This routine does NOT free the Select structure passed in. The
5140 ** calling function needs to do that.
5143 Parse
*pParse
, /* The parser context */
5144 Select
*p
, /* The SELECT statement being coded. */
5145 SelectDest
*pDest
/* What to do with the query results */
5147 int i
, j
; /* Loop counters */
5148 WhereInfo
*pWInfo
; /* Return from sqlite3WhereBegin() */
5149 Vdbe
*v
; /* The virtual machine under construction */
5150 int isAgg
; /* True for select lists like "count(*)" */
5151 ExprList
*pEList
= 0; /* List of columns to extract. */
5152 SrcList
*pTabList
; /* List of tables to select from */
5153 Expr
*pWhere
; /* The WHERE clause. May be NULL */
5154 ExprList
*pGroupBy
; /* The GROUP BY clause. May be NULL */
5155 Expr
*pHaving
; /* The HAVING clause. May be NULL */
5156 int rc
= 1; /* Value to return from this function */
5157 DistinctCtx sDistinct
; /* Info on how to code the DISTINCT keyword */
5158 SortCtx sSort
; /* Info on how to code the ORDER BY clause */
5159 AggInfo sAggInfo
; /* Information used by aggregate queries */
5160 int iEnd
; /* Address of the end of the query */
5161 sqlite3
*db
; /* The database connection */
5162 ExprList
*pMinMaxOrderBy
= 0; /* Added ORDER BY for min/max queries */
5163 u8 minMaxFlag
; /* Flag for min/max queries */
5165 #ifndef SQLITE_OMIT_EXPLAIN
5166 int iRestoreSelectId
= pParse
->iSelectId
;
5167 pParse
->iSelectId
= pParse
->iNextSelectId
++;
5171 if( p
==0 || db
->mallocFailed
|| pParse
->nErr
){
5174 if( sqlite3AuthCheck(pParse
, SQLITE_SELECT
, 0, 0, 0) ) return 1;
5175 memset(&sAggInfo
, 0, sizeof(sAggInfo
));
5176 #if SELECTTRACE_ENABLED
5177 SELECTTRACE(1,pParse
,p
, ("begin processing:\n"));
5178 if( sqlite3SelectTrace
& 0x100 ){
5179 sqlite3TreeViewSelect(0, p
, 0);
5183 assert( p
->pOrderBy
==0 || pDest
->eDest
!=SRT_DistFifo
);
5184 assert( p
->pOrderBy
==0 || pDest
->eDest
!=SRT_Fifo
);
5185 assert( p
->pOrderBy
==0 || pDest
->eDest
!=SRT_DistQueue
);
5186 assert( p
->pOrderBy
==0 || pDest
->eDest
!=SRT_Queue
);
5187 if( IgnorableOrderby(pDest
) ){
5188 assert(pDest
->eDest
==SRT_Exists
|| pDest
->eDest
==SRT_Union
||
5189 pDest
->eDest
==SRT_Except
|| pDest
->eDest
==SRT_Discard
||
5190 pDest
->eDest
==SRT_Queue
|| pDest
->eDest
==SRT_DistFifo
||
5191 pDest
->eDest
==SRT_DistQueue
|| pDest
->eDest
==SRT_Fifo
);
5192 /* If ORDER BY makes no difference in the output then neither does
5193 ** DISTINCT so it can be removed too. */
5194 sqlite3ExprListDelete(db
, p
->pOrderBy
);
5196 p
->selFlags
&= ~SF_Distinct
;
5198 sqlite3SelectPrep(pParse
, p
, 0);
5199 memset(&sSort
, 0, sizeof(sSort
));
5200 sSort
.pOrderBy
= p
->pOrderBy
;
5202 if( pParse
->nErr
|| db
->mallocFailed
){
5205 assert( p
->pEList
!=0 );
5206 isAgg
= (p
->selFlags
& SF_Aggregate
)!=0;
5207 #if SELECTTRACE_ENABLED
5208 if( sqlite3SelectTrace
& 0x100 ){
5209 SELECTTRACE(0x100,pParse
,p
, ("after name resolution:\n"));
5210 sqlite3TreeViewSelect(0, p
, 0);
5214 /* Get a pointer the VDBE under construction, allocating a new VDBE if one
5215 ** does not already exist */
5216 v
= sqlite3GetVdbe(pParse
);
5217 if( v
==0 ) goto select_end
;
5218 if( pDest
->eDest
==SRT_Output
){
5219 generateColumnNames(pParse
, p
);
5222 /* Try to various optimizations (flattening subqueries, and strength
5223 ** reduction of join operators) in the FROM clause up into the main query
5225 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
5226 for(i
=0; !p
->pPrior
&& i
<pTabList
->nSrc
; i
++){
5227 struct SrcList_item
*pItem
= &pTabList
->a
[i
];
5228 Select
*pSub
= pItem
->pSelect
;
5229 Table
*pTab
= pItem
->pTab
;
5231 /* Convert LEFT JOIN into JOIN if there are terms of the right table
5232 ** of the LEFT JOIN used in the WHERE clause.
5234 if( (pItem
->fg
.jointype
& JT_LEFT
)!=0
5235 && sqlite3ExprImpliesNonNullRow(p
->pWhere
, pItem
->iCursor
)
5236 && OptimizationEnabled(db
, SQLITE_SimplifyJoin
)
5238 SELECTTRACE(0x100,pParse
,p
,
5239 ("LEFT-JOIN simplifies to JOIN on term %d\n",i
));
5240 pItem
->fg
.jointype
&= ~(JT_LEFT
|JT_OUTER
);
5241 unsetJoinExpr(p
->pWhere
, pItem
->iCursor
);
5244 /* No futher action if this term of the FROM clause is no a subquery */
5245 if( pSub
==0 ) continue;
5247 /* Catch mismatch in the declared columns of a view and the number of
5248 ** columns in the SELECT on the RHS */
5249 if( pTab
->nCol
!=pSub
->pEList
->nExpr
){
5250 sqlite3ErrorMsg(pParse
, "expected %d columns for '%s' but got %d",
5251 pTab
->nCol
, pTab
->zName
, pSub
->pEList
->nExpr
);
5255 /* Do not try to flatten an aggregate subquery.
5257 ** Flattening an aggregate subquery is only possible if the outer query
5258 ** is not a join. But if the outer query is not a join, then the subquery
5259 ** will be implemented as a co-routine and there is no advantage to
5260 ** flattening in that case.
5262 if( (pSub
->selFlags
& SF_Aggregate
)!=0 ) continue;
5263 assert( pSub
->pGroupBy
==0 );
5265 /* If the outer query contains a "complex" result set (that is,
5266 ** if the result set of the outer query uses functions or subqueries)
5267 ** and if the subquery contains an ORDER BY clause and if
5268 ** it will be implemented as a co-routine, then do not flatten. This
5269 ** restriction allows SQL constructs like this:
5271 ** SELECT expensive_function(x)
5272 ** FROM (SELECT x FROM tab ORDER BY y LIMIT 10);
5274 ** The expensive_function() is only computed on the 10 rows that
5275 ** are output, rather than every row of the table.
5277 ** The requirement that the outer query have a complex result set
5278 ** means that flattening does occur on simpler SQL constraints without
5279 ** the expensive_function() like:
5281 ** SELECT x FROM (SELECT x FROM tab ORDER BY y LIMIT 10);
5283 if( pSub
->pOrderBy
!=0
5285 && (p
->selFlags
& SF_ComplexResult
)!=0
5286 && (pTabList
->nSrc
==1
5287 || (pTabList
->a
[1].fg
.jointype
&(JT_LEFT
|JT_CROSS
))!=0)
5292 if( flattenSubquery(pParse
, p
, i
, isAgg
) ){
5293 /* This subquery can be absorbed into its parent. */
5297 if( db
->mallocFailed
) goto select_end
;
5298 if( !IgnorableOrderby(pDest
) ){
5299 sSort
.pOrderBy
= p
->pOrderBy
;
5304 #ifndef SQLITE_OMIT_COMPOUND_SELECT
5305 /* Handle compound SELECT statements using the separate multiSelect()
5309 rc
= multiSelect(pParse
, p
, pDest
);
5310 explainSetInteger(pParse
->iSelectId
, iRestoreSelectId
);
5311 #if SELECTTRACE_ENABLED
5312 SELECTTRACE(1,pParse
,p
,("end compound-select processing\n"));
5318 /* For each term in the FROM clause, do two things:
5319 ** (1) Authorized unreferenced tables
5320 ** (2) Generate code for all sub-queries
5322 for(i
=0; i
<pTabList
->nSrc
; i
++){
5323 struct SrcList_item
*pItem
= &pTabList
->a
[i
];
5326 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
5327 const char *zSavedAuthContext
;
5330 /* Issue SQLITE_READ authorizations with a fake column name for any
5331 ** tables that are referenced but from which no values are extracted.
5332 ** Examples of where these kinds of null SQLITE_READ authorizations
5335 ** SELECT count(*) FROM t1; -- SQLITE_READ t1.""
5336 ** SELECT t1.* FROM t1, t2; -- SQLITE_READ t2.""
5338 ** The fake column name is an empty string. It is possible for a table to
5339 ** have a column named by the empty string, in which case there is no way to
5340 ** distinguish between an unreferenced table and an actual reference to the
5341 ** "" column. The original design was for the fake column name to be a NULL,
5342 ** which would be unambiguous. But legacy authorization callbacks might
5343 ** assume the column name is non-NULL and segfault. The use of an empty
5344 ** string for the fake column name seems safer.
5346 if( pItem
->colUsed
==0 ){
5347 sqlite3AuthCheck(pParse
, SQLITE_READ
, pItem
->zName
, "", pItem
->zDatabase
);
5350 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
5351 /* Generate code for all sub-queries in the FROM clause
5353 pSub
= pItem
->pSelect
;
5354 if( pSub
==0 ) continue;
5356 /* Sometimes the code for a subquery will be generated more than
5357 ** once, if the subquery is part of the WHERE clause in a LEFT JOIN,
5358 ** for example. In that case, do not regenerate the code to manifest
5359 ** a view or the co-routine to implement a view. The first instance
5360 ** is sufficient, though the subroutine to manifest the view does need
5361 ** to be invoked again. */
5362 if( pItem
->addrFillSub
){
5363 if( pItem
->fg
.viaCoroutine
==0 ){
5364 /* The subroutine that manifests the view might be a one-time routine,
5365 ** or it might need to be rerun on each iteration because it
5366 ** encodes a correlated subquery. */
5367 testcase( sqlite3VdbeGetOp(v
, pItem
->addrFillSub
)->opcode
==OP_Once
);
5368 sqlite3VdbeAddOp2(v
, OP_Gosub
, pItem
->regReturn
, pItem
->addrFillSub
);
5373 /* Increment Parse.nHeight by the height of the largest expression
5374 ** tree referred to by this, the parent select. The child select
5375 ** may contain expression trees of at most
5376 ** (SQLITE_MAX_EXPR_DEPTH-Parse.nHeight) height. This is a bit
5377 ** more conservative than necessary, but much easier than enforcing
5380 pParse
->nHeight
+= sqlite3SelectExprHeight(p
);
5382 /* Make copies of constant WHERE-clause terms in the outer query down
5383 ** inside the subquery. This can help the subquery to run more efficiently.
5385 if( OptimizationEnabled(db
, SQLITE_PushDown
)
5386 && pushDownWhereTerms(pParse
, pSub
, p
->pWhere
, pItem
->iCursor
,
5387 (pItem
->fg
.jointype
& JT_OUTER
)!=0)
5389 #if SELECTTRACE_ENABLED
5390 if( sqlite3SelectTrace
& 0x100 ){
5391 SELECTTRACE(0x100,pParse
,p
,("After WHERE-clause push-down:\n"));
5392 sqlite3TreeViewSelect(0, p
, 0);
5396 SELECTTRACE(0x100,pParse
,p
,("Push-down not possible\n"));
5399 zSavedAuthContext
= pParse
->zAuthContext
;
5400 pParse
->zAuthContext
= pItem
->zName
;
5402 /* Generate code to implement the subquery
5404 ** The subquery is implemented as a co-routine if the subquery is
5405 ** guaranteed to be the outer loop (so that it does not need to be
5406 ** computed more than once)
5408 ** TODO: Are there other reasons beside (1) to use a co-routine
5412 && (pTabList
->nSrc
==1
5413 || (pTabList
->a
[1].fg
.jointype
&(JT_LEFT
|JT_CROSS
))!=0) /* (1) */
5415 /* Implement a co-routine that will return a single row of the result
5416 ** set on each invocation.
5418 int addrTop
= sqlite3VdbeCurrentAddr(v
)+1;
5420 pItem
->regReturn
= ++pParse
->nMem
;
5421 sqlite3VdbeAddOp3(v
, OP_InitCoroutine
, pItem
->regReturn
, 0, addrTop
);
5422 VdbeComment((v
, "%s", pItem
->pTab
->zName
));
5423 pItem
->addrFillSub
= addrTop
;
5424 sqlite3SelectDestInit(&dest
, SRT_Coroutine
, pItem
->regReturn
);
5425 explainSetInteger(pItem
->iSelectId
, (u8
)pParse
->iNextSelectId
);
5426 sqlite3Select(pParse
, pSub
, &dest
);
5427 pItem
->pTab
->nRowLogEst
= pSub
->nSelectRow
;
5428 pItem
->fg
.viaCoroutine
= 1;
5429 pItem
->regResult
= dest
.iSdst
;
5430 sqlite3VdbeEndCoroutine(v
, pItem
->regReturn
);
5431 sqlite3VdbeJumpHere(v
, addrTop
-1);
5432 sqlite3ClearTempRegCache(pParse
);
5434 /* Generate a subroutine that will fill an ephemeral table with
5435 ** the content of this subquery. pItem->addrFillSub will point
5436 ** to the address of the generated subroutine. pItem->regReturn
5437 ** is a register allocated to hold the subroutine return address
5442 struct SrcList_item
*pPrior
;
5444 assert( pItem
->addrFillSub
==0 );
5445 pItem
->regReturn
= ++pParse
->nMem
;
5446 topAddr
= sqlite3VdbeAddOp2(v
, OP_Integer
, 0, pItem
->regReturn
);
5447 pItem
->addrFillSub
= topAddr
+1;
5448 if( pItem
->fg
.isCorrelated
==0 ){
5449 /* If the subquery is not correlated and if we are not inside of
5450 ** a trigger, then we only need to compute the value of the subquery
5452 onceAddr
= sqlite3VdbeAddOp0(v
, OP_Once
); VdbeCoverage(v
);
5453 VdbeComment((v
, "materialize \"%s\"", pItem
->pTab
->zName
));
5455 VdbeNoopComment((v
, "materialize \"%s\"", pItem
->pTab
->zName
));
5457 pPrior
= isSelfJoinView(pTabList
, pItem
);
5459 sqlite3VdbeAddOp2(v
, OP_OpenDup
, pItem
->iCursor
, pPrior
->iCursor
);
5460 explainSetInteger(pItem
->iSelectId
, pPrior
->iSelectId
);
5461 assert( pPrior
->pSelect
!=0 );
5462 pSub
->nSelectRow
= pPrior
->pSelect
->nSelectRow
;
5464 sqlite3SelectDestInit(&dest
, SRT_EphemTab
, pItem
->iCursor
);
5465 explainSetInteger(pItem
->iSelectId
, (u8
)pParse
->iNextSelectId
);
5466 sqlite3Select(pParse
, pSub
, &dest
);
5468 pItem
->pTab
->nRowLogEst
= pSub
->nSelectRow
;
5469 if( onceAddr
) sqlite3VdbeJumpHere(v
, onceAddr
);
5470 retAddr
= sqlite3VdbeAddOp1(v
, OP_Return
, pItem
->regReturn
);
5471 VdbeComment((v
, "end %s", pItem
->pTab
->zName
));
5472 sqlite3VdbeChangeP1(v
, topAddr
, retAddr
);
5473 sqlite3ClearTempRegCache(pParse
);
5475 if( db
->mallocFailed
) goto select_end
;
5476 pParse
->nHeight
-= sqlite3SelectExprHeight(p
);
5477 pParse
->zAuthContext
= zSavedAuthContext
;
5481 /* Various elements of the SELECT copied into local variables for
5485 pGroupBy
= p
->pGroupBy
;
5486 pHaving
= p
->pHaving
;
5487 sDistinct
.isTnct
= (p
->selFlags
& SF_Distinct
)!=0;
5489 #if SELECTTRACE_ENABLED
5490 if( sqlite3SelectTrace
& 0x400 ){
5491 SELECTTRACE(0x400,pParse
,p
,("After all FROM-clause analysis:\n"));
5492 sqlite3TreeViewSelect(0, p
, 0);
5496 #ifdef SQLITE_COUNTOFVIEW_OPTIMIZATION
5497 if( OptimizationEnabled(db
, SQLITE_QueryFlattener
|SQLITE_CountOfView
)
5498 && countOfViewOptimization(pParse
, p
)
5500 if( db
->mallocFailed
) goto select_end
;
5506 /* If the query is DISTINCT with an ORDER BY but is not an aggregate, and
5507 ** if the select-list is the same as the ORDER BY list, then this query
5508 ** can be rewritten as a GROUP BY. In other words, this:
5510 ** SELECT DISTINCT xyz FROM ... ORDER BY xyz
5512 ** is transformed to:
5514 ** SELECT xyz FROM ... GROUP BY xyz ORDER BY xyz
5516 ** The second form is preferred as a single index (or temp-table) may be
5517 ** used for both the ORDER BY and DISTINCT processing. As originally
5518 ** written the query must use a temp-table for at least one of the ORDER
5519 ** BY and DISTINCT, and an index or separate temp-table for the other.
5521 if( (p
->selFlags
& (SF_Distinct
|SF_Aggregate
))==SF_Distinct
5522 && sqlite3ExprListCompare(sSort
.pOrderBy
, pEList
, -1)==0
5524 p
->selFlags
&= ~SF_Distinct
;
5525 pGroupBy
= p
->pGroupBy
= sqlite3ExprListDup(db
, pEList
, 0);
5526 /* Notice that even thought SF_Distinct has been cleared from p->selFlags,
5527 ** the sDistinct.isTnct is still set. Hence, isTnct represents the
5528 ** original setting of the SF_Distinct flag, not the current setting */
5529 assert( sDistinct
.isTnct
);
5531 #if SELECTTRACE_ENABLED
5532 if( sqlite3SelectTrace
& 0x400 ){
5533 SELECTTRACE(0x400,pParse
,p
,("Transform DISTINCT into GROUP BY:\n"));
5534 sqlite3TreeViewSelect(0, p
, 0);
5539 /* If there is an ORDER BY clause, then create an ephemeral index to
5540 ** do the sorting. But this sorting ephemeral index might end up
5541 ** being unused if the data can be extracted in pre-sorted order.
5542 ** If that is the case, then the OP_OpenEphemeral instruction will be
5543 ** changed to an OP_Noop once we figure out that the sorting index is
5544 ** not needed. The sSort.addrSortIndex variable is used to facilitate
5547 if( sSort
.pOrderBy
){
5549 pKeyInfo
= keyInfoFromExprList(pParse
, sSort
.pOrderBy
, 0, pEList
->nExpr
);
5550 sSort
.iECursor
= pParse
->nTab
++;
5551 sSort
.addrSortIndex
=
5552 sqlite3VdbeAddOp4(v
, OP_OpenEphemeral
,
5553 sSort
.iECursor
, sSort
.pOrderBy
->nExpr
+1+pEList
->nExpr
, 0,
5554 (char*)pKeyInfo
, P4_KEYINFO
5557 sSort
.addrSortIndex
= -1;
5560 /* If the output is destined for a temporary table, open that table.
5562 if( pDest
->eDest
==SRT_EphemTab
){
5563 sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, pDest
->iSDParm
, pEList
->nExpr
);
5568 iEnd
= sqlite3VdbeMakeLabel(v
);
5569 if( (p
->selFlags
& SF_FixedLimit
)==0 ){
5570 p
->nSelectRow
= 320; /* 4 billion rows */
5572 computeLimitRegisters(pParse
, p
, iEnd
);
5573 if( p
->iLimit
==0 && sSort
.addrSortIndex
>=0 ){
5574 sqlite3VdbeChangeOpcode(v
, sSort
.addrSortIndex
, OP_SorterOpen
);
5575 sSort
.sortFlags
|= SORTFLAG_UseSorter
;
5578 /* Open an ephemeral index to use for the distinct set.
5580 if( p
->selFlags
& SF_Distinct
){
5581 sDistinct
.tabTnct
= pParse
->nTab
++;
5582 sDistinct
.addrTnct
= sqlite3VdbeAddOp4(v
, OP_OpenEphemeral
,
5583 sDistinct
.tabTnct
, 0, 0,
5584 (char*)keyInfoFromExprList(pParse
, p
->pEList
,0,0),
5586 sqlite3VdbeChangeP5(v
, BTREE_UNORDERED
);
5587 sDistinct
.eTnctType
= WHERE_DISTINCT_UNORDERED
;
5589 sDistinct
.eTnctType
= WHERE_DISTINCT_NOOP
;
5592 if( !isAgg
&& pGroupBy
==0 ){
5593 /* No aggregate functions and no GROUP BY clause */
5594 u16 wctrlFlags
= (sDistinct
.isTnct
? WHERE_WANT_DISTINCT
: 0);
5595 assert( WHERE_USE_LIMIT
==SF_FixedLimit
);
5596 wctrlFlags
|= p
->selFlags
& SF_FixedLimit
;
5598 /* Begin the database scan. */
5599 SELECTTRACE(1,pParse
,p
,("WhereBegin\n"));
5600 pWInfo
= sqlite3WhereBegin(pParse
, pTabList
, pWhere
, sSort
.pOrderBy
,
5601 p
->pEList
, wctrlFlags
, p
->nSelectRow
);
5602 if( pWInfo
==0 ) goto select_end
;
5603 if( sqlite3WhereOutputRowCount(pWInfo
) < p
->nSelectRow
){
5604 p
->nSelectRow
= sqlite3WhereOutputRowCount(pWInfo
);
5606 if( sDistinct
.isTnct
&& sqlite3WhereIsDistinct(pWInfo
) ){
5607 sDistinct
.eTnctType
= sqlite3WhereIsDistinct(pWInfo
);
5609 if( sSort
.pOrderBy
){
5610 sSort
.nOBSat
= sqlite3WhereIsOrdered(pWInfo
);
5611 sSort
.bOrderedInnerLoop
= sqlite3WhereOrderedInnerLoop(pWInfo
);
5612 if( sSort
.nOBSat
==sSort
.pOrderBy
->nExpr
){
5617 /* If sorting index that was created by a prior OP_OpenEphemeral
5618 ** instruction ended up not being needed, then change the OP_OpenEphemeral
5621 if( sSort
.addrSortIndex
>=0 && sSort
.pOrderBy
==0 ){
5622 sqlite3VdbeChangeToNoop(v
, sSort
.addrSortIndex
);
5625 /* Use the standard inner loop. */
5626 assert( p
->pEList
==pEList
);
5627 selectInnerLoop(pParse
, p
, -1, &sSort
, &sDistinct
, pDest
,
5628 sqlite3WhereContinueLabel(pWInfo
),
5629 sqlite3WhereBreakLabel(pWInfo
));
5631 /* End the database scan loop.
5633 sqlite3WhereEnd(pWInfo
);
5635 /* This case when there exist aggregate functions or a GROUP BY clause
5637 NameContext sNC
; /* Name context for processing aggregate information */
5638 int iAMem
; /* First Mem address for storing current GROUP BY */
5639 int iBMem
; /* First Mem address for previous GROUP BY */
5640 int iUseFlag
; /* Mem address holding flag indicating that at least
5641 ** one row of the input to the aggregator has been
5643 int iAbortFlag
; /* Mem address which causes query abort if positive */
5644 int groupBySort
; /* Rows come from source in GROUP BY order */
5645 int addrEnd
; /* End of processing for this SELECT */
5646 int sortPTab
= 0; /* Pseudotable used to decode sorting results */
5647 int sortOut
= 0; /* Output register from the sorter */
5648 int orderByGrp
= 0; /* True if the GROUP BY and ORDER BY are the same */
5650 /* Remove any and all aliases between the result set and the
5654 int k
; /* Loop counter */
5655 struct ExprList_item
*pItem
; /* For looping over expression in a list */
5657 for(k
=p
->pEList
->nExpr
, pItem
=p
->pEList
->a
; k
>0; k
--, pItem
++){
5658 pItem
->u
.x
.iAlias
= 0;
5660 for(k
=pGroupBy
->nExpr
, pItem
=pGroupBy
->a
; k
>0; k
--, pItem
++){
5661 pItem
->u
.x
.iAlias
= 0;
5663 assert( 66==sqlite3LogEst(100) );
5664 if( p
->nSelectRow
>66 ) p
->nSelectRow
= 66;
5666 assert( 0==sqlite3LogEst(1) );
5670 /* If there is both a GROUP BY and an ORDER BY clause and they are
5671 ** identical, then it may be possible to disable the ORDER BY clause
5672 ** on the grounds that the GROUP BY will cause elements to come out
5673 ** in the correct order. It also may not - the GROUP BY might use a
5674 ** database index that causes rows to be grouped together as required
5675 ** but not actually sorted. Either way, record the fact that the
5676 ** ORDER BY and GROUP BY clauses are the same by setting the orderByGrp
5678 if( sqlite3ExprListCompare(pGroupBy
, sSort
.pOrderBy
, -1)==0 ){
5682 /* Create a label to jump to when we want to abort the query */
5683 addrEnd
= sqlite3VdbeMakeLabel(v
);
5685 /* Convert TK_COLUMN nodes into TK_AGG_COLUMN and make entries in
5686 ** sAggInfo for all TK_AGG_FUNCTION nodes in expressions of the
5687 ** SELECT statement.
5689 memset(&sNC
, 0, sizeof(sNC
));
5690 sNC
.pParse
= pParse
;
5691 sNC
.pSrcList
= pTabList
;
5692 sNC
.pAggInfo
= &sAggInfo
;
5693 sAggInfo
.mnReg
= pParse
->nMem
+1;
5694 sAggInfo
.nSortingColumn
= pGroupBy
? pGroupBy
->nExpr
: 0;
5695 sAggInfo
.pGroupBy
= pGroupBy
;
5696 sqlite3ExprAnalyzeAggList(&sNC
, pEList
);
5697 sqlite3ExprAnalyzeAggList(&sNC
, sSort
.pOrderBy
);
5700 assert( pWhere
==p
->pWhere
);
5701 assert( pHaving
==p
->pHaving
);
5702 assert( pGroupBy
==p
->pGroupBy
);
5703 havingToWhere(pParse
, p
);
5706 sqlite3ExprAnalyzeAggregates(&sNC
, pHaving
);
5708 sAggInfo
.nAccumulator
= sAggInfo
.nColumn
;
5709 if( p
->pGroupBy
==0 && p
->pHaving
==0 && sAggInfo
.nFunc
==1 ){
5710 minMaxFlag
= minMaxQuery(db
, sAggInfo
.aFunc
[0].pExpr
, &pMinMaxOrderBy
);
5712 minMaxFlag
= WHERE_ORDERBY_NORMAL
;
5714 for(i
=0; i
<sAggInfo
.nFunc
; i
++){
5715 assert( !ExprHasProperty(sAggInfo
.aFunc
[i
].pExpr
, EP_xIsSelect
) );
5716 sNC
.ncFlags
|= NC_InAggFunc
;
5717 sqlite3ExprAnalyzeAggList(&sNC
, sAggInfo
.aFunc
[i
].pExpr
->x
.pList
);
5718 sNC
.ncFlags
&= ~NC_InAggFunc
;
5720 sAggInfo
.mxReg
= pParse
->nMem
;
5721 if( db
->mallocFailed
) goto select_end
;
5722 #if SELECTTRACE_ENABLED
5723 if( sqlite3SelectTrace
& 0x400 ){
5725 SELECTTRACE(0x400,pParse
,p
,("After aggregate analysis:\n"));
5726 sqlite3TreeViewSelect(0, p
, 0);
5727 for(ii
=0; ii
<sAggInfo
.nColumn
; ii
++){
5728 sqlite3DebugPrintf("agg-column[%d] iMem=%d\n",
5729 ii
, sAggInfo
.aCol
[ii
].iMem
);
5730 sqlite3TreeViewExpr(0, sAggInfo
.aCol
[ii
].pExpr
, 0);
5732 for(ii
=0; ii
<sAggInfo
.nFunc
; ii
++){
5733 sqlite3DebugPrintf("agg-func[%d]: iMem=%d\n",
5734 ii
, sAggInfo
.aFunc
[ii
].iMem
);
5735 sqlite3TreeViewExpr(0, sAggInfo
.aFunc
[ii
].pExpr
, 0);
5741 /* Processing for aggregates with GROUP BY is very different and
5742 ** much more complex than aggregates without a GROUP BY.
5745 KeyInfo
*pKeyInfo
; /* Keying information for the group by clause */
5746 int addr1
; /* A-vs-B comparision jump */
5747 int addrOutputRow
; /* Start of subroutine that outputs a result row */
5748 int regOutputRow
; /* Return address register for output subroutine */
5749 int addrSetAbort
; /* Set the abort flag and return */
5750 int addrTopOfLoop
; /* Top of the input loop */
5751 int addrSortingIdx
; /* The OP_OpenEphemeral for the sorting index */
5752 int addrReset
; /* Subroutine for resetting the accumulator */
5753 int regReset
; /* Return address register for reset subroutine */
5755 /* If there is a GROUP BY clause we might need a sorting index to
5756 ** implement it. Allocate that sorting index now. If it turns out
5757 ** that we do not need it after all, the OP_SorterOpen instruction
5758 ** will be converted into a Noop.
5760 sAggInfo
.sortingIdx
= pParse
->nTab
++;
5761 pKeyInfo
= keyInfoFromExprList(pParse
, pGroupBy
, 0, sAggInfo
.nColumn
);
5762 addrSortingIdx
= sqlite3VdbeAddOp4(v
, OP_SorterOpen
,
5763 sAggInfo
.sortingIdx
, sAggInfo
.nSortingColumn
,
5764 0, (char*)pKeyInfo
, P4_KEYINFO
);
5766 /* Initialize memory locations used by GROUP BY aggregate processing
5768 iUseFlag
= ++pParse
->nMem
;
5769 iAbortFlag
= ++pParse
->nMem
;
5770 regOutputRow
= ++pParse
->nMem
;
5771 addrOutputRow
= sqlite3VdbeMakeLabel(v
);
5772 regReset
= ++pParse
->nMem
;
5773 addrReset
= sqlite3VdbeMakeLabel(v
);
5774 iAMem
= pParse
->nMem
+ 1;
5775 pParse
->nMem
+= pGroupBy
->nExpr
;
5776 iBMem
= pParse
->nMem
+ 1;
5777 pParse
->nMem
+= pGroupBy
->nExpr
;
5778 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, iAbortFlag
);
5779 VdbeComment((v
, "clear abort flag"));
5780 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, iUseFlag
);
5781 VdbeComment((v
, "indicate accumulator empty"));
5782 sqlite3VdbeAddOp3(v
, OP_Null
, 0, iAMem
, iAMem
+pGroupBy
->nExpr
-1);
5784 /* Begin a loop that will extract all source rows in GROUP BY order.
5785 ** This might involve two separate loops with an OP_Sort in between, or
5786 ** it might be a single loop that uses an index to extract information
5787 ** in the right order to begin with.
5789 sqlite3VdbeAddOp2(v
, OP_Gosub
, regReset
, addrReset
);
5790 SELECTTRACE(1,pParse
,p
,("WhereBegin\n"));
5791 pWInfo
= sqlite3WhereBegin(pParse
, pTabList
, pWhere
, pGroupBy
, 0,
5792 WHERE_GROUPBY
| (orderByGrp
? WHERE_SORTBYGROUP
: 0), 0
5794 if( pWInfo
==0 ) goto select_end
;
5795 if( sqlite3WhereIsOrdered(pWInfo
)==pGroupBy
->nExpr
){
5796 /* The optimizer is able to deliver rows in group by order so
5797 ** we do not have to sort. The OP_OpenEphemeral table will be
5798 ** cancelled later because we still need to use the pKeyInfo
5802 /* Rows are coming out in undetermined order. We have to push
5803 ** each row into a sorting index, terminate the first loop,
5804 ** then loop over the sorting index in order to get the output
5812 explainTempTable(pParse
,
5813 (sDistinct
.isTnct
&& (p
->selFlags
&SF_Distinct
)==0) ?
5814 "DISTINCT" : "GROUP BY");
5817 nGroupBy
= pGroupBy
->nExpr
;
5820 for(i
=0; i
<sAggInfo
.nColumn
; i
++){
5821 if( sAggInfo
.aCol
[i
].iSorterColumn
>=j
){
5826 regBase
= sqlite3GetTempRange(pParse
, nCol
);
5827 sqlite3ExprCacheClear(pParse
);
5828 sqlite3ExprCodeExprList(pParse
, pGroupBy
, regBase
, 0, 0);
5830 for(i
=0; i
<sAggInfo
.nColumn
; i
++){
5831 struct AggInfo_col
*pCol
= &sAggInfo
.aCol
[i
];
5832 if( pCol
->iSorterColumn
>=j
){
5833 int r1
= j
+ regBase
;
5834 sqlite3ExprCodeGetColumnToReg(pParse
,
5835 pCol
->pTab
, pCol
->iColumn
, pCol
->iTable
, r1
);
5839 regRecord
= sqlite3GetTempReg(pParse
);
5840 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, regBase
, nCol
, regRecord
);
5841 sqlite3VdbeAddOp2(v
, OP_SorterInsert
, sAggInfo
.sortingIdx
, regRecord
);
5842 sqlite3ReleaseTempReg(pParse
, regRecord
);
5843 sqlite3ReleaseTempRange(pParse
, regBase
, nCol
);
5844 sqlite3WhereEnd(pWInfo
);
5845 sAggInfo
.sortingIdxPTab
= sortPTab
= pParse
->nTab
++;
5846 sortOut
= sqlite3GetTempReg(pParse
);
5847 sqlite3VdbeAddOp3(v
, OP_OpenPseudo
, sortPTab
, sortOut
, nCol
);
5848 sqlite3VdbeAddOp2(v
, OP_SorterSort
, sAggInfo
.sortingIdx
, addrEnd
);
5849 VdbeComment((v
, "GROUP BY sort")); VdbeCoverage(v
);
5850 sAggInfo
.useSortingIdx
= 1;
5851 sqlite3ExprCacheClear(pParse
);
5855 /* If the index or temporary table used by the GROUP BY sort
5856 ** will naturally deliver rows in the order required by the ORDER BY
5857 ** clause, cancel the ephemeral table open coded earlier.
5859 ** This is an optimization - the correct answer should result regardless.
5860 ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER to
5861 ** disable this optimization for testing purposes. */
5862 if( orderByGrp
&& OptimizationEnabled(db
, SQLITE_GroupByOrder
)
5863 && (groupBySort
|| sqlite3WhereIsSorted(pWInfo
))
5866 sqlite3VdbeChangeToNoop(v
, sSort
.addrSortIndex
);
5869 /* Evaluate the current GROUP BY terms and store in b0, b1, b2...
5870 ** (b0 is memory location iBMem+0, b1 is iBMem+1, and so forth)
5871 ** Then compare the current GROUP BY terms against the GROUP BY terms
5872 ** from the previous row currently stored in a0, a1, a2...
5874 addrTopOfLoop
= sqlite3VdbeCurrentAddr(v
);
5875 sqlite3ExprCacheClear(pParse
);
5877 sqlite3VdbeAddOp3(v
, OP_SorterData
, sAggInfo
.sortingIdx
,
5880 for(j
=0; j
<pGroupBy
->nExpr
; j
++){
5882 sqlite3VdbeAddOp3(v
, OP_Column
, sortPTab
, j
, iBMem
+j
);
5884 sAggInfo
.directMode
= 1;
5885 sqlite3ExprCode(pParse
, pGroupBy
->a
[j
].pExpr
, iBMem
+j
);
5888 sqlite3VdbeAddOp4(v
, OP_Compare
, iAMem
, iBMem
, pGroupBy
->nExpr
,
5889 (char*)sqlite3KeyInfoRef(pKeyInfo
), P4_KEYINFO
);
5890 addr1
= sqlite3VdbeCurrentAddr(v
);
5891 sqlite3VdbeAddOp3(v
, OP_Jump
, addr1
+1, 0, addr1
+1); VdbeCoverage(v
);
5893 /* Generate code that runs whenever the GROUP BY changes.
5894 ** Changes in the GROUP BY are detected by the previous code
5895 ** block. If there were no changes, this block is skipped.
5897 ** This code copies current group by terms in b0,b1,b2,...
5898 ** over to a0,a1,a2. It then calls the output subroutine
5899 ** and resets the aggregate accumulator registers in preparation
5900 ** for the next GROUP BY batch.
5902 sqlite3ExprCodeMove(pParse
, iBMem
, iAMem
, pGroupBy
->nExpr
);
5903 sqlite3VdbeAddOp2(v
, OP_Gosub
, regOutputRow
, addrOutputRow
);
5904 VdbeComment((v
, "output one row"));
5905 sqlite3VdbeAddOp2(v
, OP_IfPos
, iAbortFlag
, addrEnd
); VdbeCoverage(v
);
5906 VdbeComment((v
, "check abort flag"));
5907 sqlite3VdbeAddOp2(v
, OP_Gosub
, regReset
, addrReset
);
5908 VdbeComment((v
, "reset accumulator"));
5910 /* Update the aggregate accumulators based on the content of
5913 sqlite3VdbeJumpHere(v
, addr1
);
5914 updateAccumulator(pParse
, &sAggInfo
);
5915 sqlite3VdbeAddOp2(v
, OP_Integer
, 1, iUseFlag
);
5916 VdbeComment((v
, "indicate data in accumulator"));
5921 sqlite3VdbeAddOp2(v
, OP_SorterNext
, sAggInfo
.sortingIdx
, addrTopOfLoop
);
5924 sqlite3WhereEnd(pWInfo
);
5925 sqlite3VdbeChangeToNoop(v
, addrSortingIdx
);
5928 /* Output the final row of result
5930 sqlite3VdbeAddOp2(v
, OP_Gosub
, regOutputRow
, addrOutputRow
);
5931 VdbeComment((v
, "output final row"));
5933 /* Jump over the subroutines
5935 sqlite3VdbeGoto(v
, addrEnd
);
5937 /* Generate a subroutine that outputs a single row of the result
5938 ** set. This subroutine first looks at the iUseFlag. If iUseFlag
5939 ** is less than or equal to zero, the subroutine is a no-op. If
5940 ** the processing calls for the query to abort, this subroutine
5941 ** increments the iAbortFlag memory location before returning in
5942 ** order to signal the caller to abort.
5944 addrSetAbort
= sqlite3VdbeCurrentAddr(v
);
5945 sqlite3VdbeAddOp2(v
, OP_Integer
, 1, iAbortFlag
);
5946 VdbeComment((v
, "set abort flag"));
5947 sqlite3VdbeAddOp1(v
, OP_Return
, regOutputRow
);
5948 sqlite3VdbeResolveLabel(v
, addrOutputRow
);
5949 addrOutputRow
= sqlite3VdbeCurrentAddr(v
);
5950 sqlite3VdbeAddOp2(v
, OP_IfPos
, iUseFlag
, addrOutputRow
+2);
5952 VdbeComment((v
, "Groupby result generator entry point"));
5953 sqlite3VdbeAddOp1(v
, OP_Return
, regOutputRow
);
5954 finalizeAggFunctions(pParse
, &sAggInfo
);
5955 sqlite3ExprIfFalse(pParse
, pHaving
, addrOutputRow
+1, SQLITE_JUMPIFNULL
);
5956 selectInnerLoop(pParse
, p
, -1, &sSort
,
5958 addrOutputRow
+1, addrSetAbort
);
5959 sqlite3VdbeAddOp1(v
, OP_Return
, regOutputRow
);
5960 VdbeComment((v
, "end groupby result generator"));
5962 /* Generate a subroutine that will reset the group-by accumulator
5964 sqlite3VdbeResolveLabel(v
, addrReset
);
5965 resetAccumulator(pParse
, &sAggInfo
);
5966 sqlite3VdbeAddOp1(v
, OP_Return
, regReset
);
5968 } /* endif pGroupBy. Begin aggregate queries without GROUP BY: */
5970 #ifndef SQLITE_OMIT_BTREECOUNT
5972 if( (pTab
= isSimpleCount(p
, &sAggInfo
))!=0 ){
5973 /* If isSimpleCount() returns a pointer to a Table structure, then
5974 ** the SQL statement is of the form:
5976 ** SELECT count(*) FROM <tbl>
5978 ** where the Table structure returned represents table <tbl>.
5980 ** This statement is so common that it is optimized specially. The
5981 ** OP_Count instruction is executed either on the intkey table that
5982 ** contains the data for table <tbl> or on one of its indexes. It
5983 ** is better to execute the op on an index, as indexes are almost
5984 ** always spread across less pages than their corresponding tables.
5986 const int iDb
= sqlite3SchemaToIndex(pParse
->db
, pTab
->pSchema
);
5987 const int iCsr
= pParse
->nTab
++; /* Cursor to scan b-tree */
5988 Index
*pIdx
; /* Iterator variable */
5989 KeyInfo
*pKeyInfo
= 0; /* Keyinfo for scanned index */
5990 Index
*pBest
= 0; /* Best index found so far */
5991 int iRoot
= pTab
->tnum
; /* Root page of scanned b-tree */
5993 sqlite3CodeVerifySchema(pParse
, iDb
);
5994 sqlite3TableLock(pParse
, iDb
, pTab
->tnum
, 0, pTab
->zName
);
5996 /* Search for the index that has the lowest scan cost.
5998 ** (2011-04-15) Do not do a full scan of an unordered index.
6000 ** (2013-10-03) Do not count the entries in a partial index.
6002 ** In practice the KeyInfo structure will not be used. It is only
6003 ** passed to keep OP_OpenRead happy.
6005 if( !HasRowid(pTab
) ) pBest
= sqlite3PrimaryKeyIndex(pTab
);
6006 for(pIdx
=pTab
->pIndex
; pIdx
; pIdx
=pIdx
->pNext
){
6007 if( pIdx
->bUnordered
==0
6008 && pIdx
->szIdxRow
<pTab
->szTabRow
6009 && pIdx
->pPartIdxWhere
==0
6010 && (!pBest
|| pIdx
->szIdxRow
<pBest
->szIdxRow
)
6016 iRoot
= pBest
->tnum
;
6017 pKeyInfo
= sqlite3KeyInfoOfIndex(pParse
, pBest
);
6020 /* Open a read-only cursor, execute the OP_Count, close the cursor. */
6021 sqlite3VdbeAddOp4Int(v
, OP_OpenRead
, iCsr
, iRoot
, iDb
, 1);
6023 sqlite3VdbeChangeP4(v
, -1, (char *)pKeyInfo
, P4_KEYINFO
);
6025 sqlite3VdbeAddOp2(v
, OP_Count
, iCsr
, sAggInfo
.aFunc
[0].iMem
);
6026 sqlite3VdbeAddOp1(v
, OP_Close
, iCsr
);
6027 explainSimpleCount(pParse
, pTab
, pBest
);
6029 #endif /* SQLITE_OMIT_BTREECOUNT */
6031 /* This case runs if the aggregate has no GROUP BY clause. The
6032 ** processing is much simpler since there is only a single row
6035 assert( p
->pGroupBy
==0 );
6036 resetAccumulator(pParse
, &sAggInfo
);
6038 /* If this query is a candidate for the min/max optimization, then
6039 ** minMaxFlag will have been previously set to either
6040 ** WHERE_ORDERBY_MIN or WHERE_ORDERBY_MAX and pMinMaxOrderBy will
6041 ** be an appropriate ORDER BY expression for the optimization.
6043 assert( minMaxFlag
==WHERE_ORDERBY_NORMAL
|| pMinMaxOrderBy
!=0 );
6044 assert( pMinMaxOrderBy
==0 || pMinMaxOrderBy
->nExpr
==1 );
6046 SELECTTRACE(1,pParse
,p
,("WhereBegin\n"));
6047 pWInfo
= sqlite3WhereBegin(pParse
, pTabList
, pWhere
, pMinMaxOrderBy
,
6052 updateAccumulator(pParse
, &sAggInfo
);
6053 if( sqlite3WhereIsOrdered(pWInfo
)>0 ){
6054 sqlite3VdbeGoto(v
, sqlite3WhereBreakLabel(pWInfo
));
6055 VdbeComment((v
, "%s() by index",
6056 (minMaxFlag
==WHERE_ORDERBY_MIN
?"min":"max")));
6058 sqlite3WhereEnd(pWInfo
);
6059 finalizeAggFunctions(pParse
, &sAggInfo
);
6063 sqlite3ExprIfFalse(pParse
, pHaving
, addrEnd
, SQLITE_JUMPIFNULL
);
6064 selectInnerLoop(pParse
, p
, -1, 0, 0,
6065 pDest
, addrEnd
, addrEnd
);
6067 sqlite3VdbeResolveLabel(v
, addrEnd
);
6069 } /* endif aggregate query */
6071 if( sDistinct
.eTnctType
==WHERE_DISTINCT_UNORDERED
){
6072 explainTempTable(pParse
, "DISTINCT");
6075 /* If there is an ORDER BY clause, then we need to sort the results
6076 ** and send them to the callback one by one.
6078 if( sSort
.pOrderBy
){
6079 explainTempTable(pParse
,
6080 sSort
.nOBSat
>0 ? "RIGHT PART OF ORDER BY":"ORDER BY");
6081 generateSortTail(pParse
, p
, &sSort
, pEList
->nExpr
, pDest
);
6084 /* Jump here to skip this query
6086 sqlite3VdbeResolveLabel(v
, iEnd
);
6088 /* The SELECT has been coded. If there is an error in the Parse structure,
6089 ** set the return code to 1. Otherwise 0. */
6090 rc
= (pParse
->nErr
>0);
6092 /* Control jumps to here if an error is encountered above, or upon
6093 ** successful coding of the SELECT.
6096 explainSetInteger(pParse
->iSelectId
, iRestoreSelectId
);
6097 sqlite3ExprListDelete(db
, pMinMaxOrderBy
);
6098 sqlite3DbFree(db
, sAggInfo
.aCol
);
6099 sqlite3DbFree(db
, sAggInfo
.aFunc
);
6100 #if SELECTTRACE_ENABLED
6101 SELECTTRACE(1,pParse
,p
,("end processing\n"));