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/%d/%p: ",(S)->zSelName,(P)->addrExplain,(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 ** The aDefer[] array is used by the sorter-references optimization. For
49 ** example, assuming there is no index that can be used for the ORDER BY,
52 ** SELECT a, bigblob FROM t1 ORDER BY a LIMIT 10;
54 ** it may be more efficient to add just the "a" values to the sorter, and
55 ** retrieve the associated "bigblob" values directly from table t1 as the
56 ** 10 smallest "a" values are extracted from the sorter.
58 ** When the sorter-reference optimization is used, there is one entry in the
59 ** aDefer[] array for each database table that may be read as values are
60 ** extracted from the sorter.
62 typedef struct SortCtx SortCtx
;
64 ExprList
*pOrderBy
; /* The ORDER BY (or GROUP BY clause) */
65 int nOBSat
; /* Number of ORDER BY terms satisfied by indices */
66 int iECursor
; /* Cursor number for the sorter */
67 int regReturn
; /* Register holding block-output return address */
68 int labelBkOut
; /* Start label for the block-output subroutine */
69 int addrSortIndex
; /* Address of the OP_SorterOpen or OP_OpenEphemeral */
70 int labelDone
; /* Jump here when done, ex: LIMIT reached */
71 u8 sortFlags
; /* Zero or more SORTFLAG_* bits */
72 u8 bOrderedInnerLoop
; /* ORDER BY correctly sorts the inner loop */
73 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
74 u8 nDefer
; /* Number of valid entries in aDefer[] */
76 Table
*pTab
; /* Table definition */
77 int iCsr
; /* Cursor number for table */
78 int nKey
; /* Number of PK columns for table pTab (>=1) */
81 struct RowLoadInfo
*pDeferredRowLoad
; /* Deferred row loading info or NULL */
83 #define SORTFLAG_UseSorter 0x01 /* Use SorterOpen instead of OpenEphemeral */
86 ** Delete all the content of a Select structure. Deallocate the structure
87 ** itself only if bFree is true.
89 static void clearSelect(sqlite3
*db
, Select
*p
, int bFree
){
91 Select
*pPrior
= p
->pPrior
;
92 sqlite3ExprListDelete(db
, p
->pEList
);
93 sqlite3SrcListDelete(db
, p
->pSrc
);
94 sqlite3ExprDelete(db
, p
->pWhere
);
95 sqlite3ExprListDelete(db
, p
->pGroupBy
);
96 sqlite3ExprDelete(db
, p
->pHaving
);
97 sqlite3ExprListDelete(db
, p
->pOrderBy
);
98 sqlite3ExprDelete(db
, p
->pLimit
);
99 #ifndef SQLITE_OMIT_WINDOWFUNC
100 if( OK_IF_ALWAYS_TRUE(p
->pWinDefn
) ){
101 sqlite3WindowListDelete(db
, p
->pWinDefn
);
104 if( OK_IF_ALWAYS_TRUE(p
->pWith
) ) sqlite3WithDelete(db
, p
->pWith
);
105 if( bFree
) sqlite3DbFreeNN(db
, p
);
112 ** Initialize a SelectDest structure.
114 void sqlite3SelectDestInit(SelectDest
*pDest
, int eDest
, int iParm
){
115 pDest
->eDest
= (u8
)eDest
;
116 pDest
->iSDParm
= iParm
;
124 ** Allocate a new Select structure and return a pointer to that
127 Select
*sqlite3SelectNew(
128 Parse
*pParse
, /* Parsing context */
129 ExprList
*pEList
, /* which columns to include in the result */
130 SrcList
*pSrc
, /* the FROM clause -- which tables to scan */
131 Expr
*pWhere
, /* the WHERE clause */
132 ExprList
*pGroupBy
, /* the GROUP BY clause */
133 Expr
*pHaving
, /* the HAVING clause */
134 ExprList
*pOrderBy
, /* the ORDER BY clause */
135 u32 selFlags
, /* Flag parameters, such as SF_Distinct */
136 Expr
*pLimit
/* LIMIT value. NULL means not used */
140 pNew
= sqlite3DbMallocRawNN(pParse
->db
, sizeof(*pNew
) );
142 assert( pParse
->db
->mallocFailed
);
146 pEList
= sqlite3ExprListAppend(pParse
, 0,
147 sqlite3Expr(pParse
->db
,TK_ASTERISK
,0));
149 pNew
->pEList
= pEList
;
150 pNew
->op
= TK_SELECT
;
151 pNew
->selFlags
= selFlags
;
154 #if SELECTTRACE_ENABLED
155 pNew
->zSelName
[0] = 0;
157 pNew
->addrOpenEphm
[0] = -1;
158 pNew
->addrOpenEphm
[1] = -1;
159 pNew
->nSelectRow
= 0;
160 if( pSrc
==0 ) pSrc
= sqlite3DbMallocZero(pParse
->db
, sizeof(*pSrc
));
162 pNew
->pWhere
= pWhere
;
163 pNew
->pGroupBy
= pGroupBy
;
164 pNew
->pHaving
= pHaving
;
165 pNew
->pOrderBy
= pOrderBy
;
168 pNew
->pLimit
= pLimit
;
170 #ifndef SQLITE_OMIT_WINDOWFUNC
174 if( pParse
->db
->mallocFailed
) {
175 clearSelect(pParse
->db
, pNew
, pNew
!=&standin
);
178 assert( pNew
->pSrc
!=0 || pParse
->nErr
>0 );
180 assert( pNew
!=&standin
);
184 #if SELECTTRACE_ENABLED
186 ** Set the name of a Select object
188 void sqlite3SelectSetName(Select
*p
, const char *zName
){
190 sqlite3_snprintf(sizeof(p
->zSelName
), p
->zSelName
, "%s", zName
);
197 ** Delete the given Select structure and all of its substructures.
199 void sqlite3SelectDelete(sqlite3
*db
, Select
*p
){
200 if( OK_IF_ALWAYS_TRUE(p
) ) clearSelect(db
, p
, 1);
204 ** Return a pointer to the right-most SELECT statement in a compound.
206 static Select
*findRightmost(Select
*p
){
207 while( p
->pNext
) p
= p
->pNext
;
212 ** Given 1 to 3 identifiers preceding the JOIN keyword, determine the
213 ** type of join. Return an integer constant that expresses that type
214 ** in terms of the following bit values:
223 ** A full outer join is the combination of JT_LEFT and JT_RIGHT.
225 ** If an illegal or unsupported join type is seen, then still return
226 ** a join type, but put an error in the pParse structure.
228 int sqlite3JoinType(Parse
*pParse
, Token
*pA
, Token
*pB
, Token
*pC
){
232 /* 0123456789 123456789 123456789 123 */
233 static const char zKeyText
[] = "naturaleftouterightfullinnercross";
234 static const struct {
235 u8 i
; /* Beginning of keyword text in zKeyText[] */
236 u8 nChar
; /* Length of the keyword in characters */
237 u8 code
; /* Join type mask */
239 /* natural */ { 0, 7, JT_NATURAL
},
240 /* left */ { 6, 4, JT_LEFT
|JT_OUTER
},
241 /* outer */ { 10, 5, JT_OUTER
},
242 /* right */ { 14, 5, JT_RIGHT
|JT_OUTER
},
243 /* full */ { 19, 4, JT_LEFT
|JT_RIGHT
|JT_OUTER
},
244 /* inner */ { 23, 5, JT_INNER
},
245 /* cross */ { 28, 5, JT_INNER
|JT_CROSS
},
251 for(i
=0; i
<3 && apAll
[i
]; i
++){
253 for(j
=0; j
<ArraySize(aKeyword
); j
++){
254 if( p
->n
==aKeyword
[j
].nChar
255 && sqlite3StrNICmp((char*)p
->z
, &zKeyText
[aKeyword
[j
].i
], p
->n
)==0 ){
256 jointype
|= aKeyword
[j
].code
;
260 testcase( j
==0 || j
==1 || j
==2 || j
==3 || j
==4 || j
==5 || j
==6 );
261 if( j
>=ArraySize(aKeyword
) ){
262 jointype
|= JT_ERROR
;
267 (jointype
& (JT_INNER
|JT_OUTER
))==(JT_INNER
|JT_OUTER
) ||
268 (jointype
& JT_ERROR
)!=0
270 const char *zSp
= " ";
272 if( pC
==0 ){ zSp
++; }
273 sqlite3ErrorMsg(pParse
, "unknown or unsupported join type: "
274 "%T %T%s%T", pA
, pB
, zSp
, pC
);
276 }else if( (jointype
& JT_OUTER
)!=0
277 && (jointype
& (JT_LEFT
|JT_RIGHT
))!=JT_LEFT
){
278 sqlite3ErrorMsg(pParse
,
279 "RIGHT and FULL OUTER JOINs are not currently supported");
286 ** Return the index of a column in a table. Return -1 if the column
287 ** is not contained in the table.
289 static int columnIndex(Table
*pTab
, const char *zCol
){
291 for(i
=0; i
<pTab
->nCol
; i
++){
292 if( sqlite3StrICmp(pTab
->aCol
[i
].zName
, zCol
)==0 ) return i
;
298 ** Search the first N tables in pSrc, from left to right, looking for a
299 ** table that has a column named zCol.
301 ** When found, set *piTab and *piCol to the table index and column index
302 ** of the matching column and return TRUE.
304 ** If not found, return FALSE.
306 static int tableAndColumnIndex(
307 SrcList
*pSrc
, /* Array of tables to search */
308 int N
, /* Number of tables in pSrc->a[] to search */
309 const char *zCol
, /* Name of the column we are looking for */
310 int *piTab
, /* Write index of pSrc->a[] here */
311 int *piCol
/* Write index of pSrc->a[*piTab].pTab->aCol[] here */
313 int i
; /* For looping over tables in pSrc */
314 int iCol
; /* Index of column matching zCol */
316 assert( (piTab
==0)==(piCol
==0) ); /* Both or neither are NULL */
318 iCol
= columnIndex(pSrc
->a
[i
].pTab
, zCol
);
331 ** This function is used to add terms implied by JOIN syntax to the
332 ** WHERE clause expression of a SELECT statement. The new term, which
333 ** is ANDed with the existing WHERE clause, is of the form:
335 ** (tab1.col1 = tab2.col2)
337 ** where tab1 is the iSrc'th table in SrcList pSrc and tab2 is the
338 ** (iSrc+1)'th. Column col1 is column iColLeft of tab1, and col2 is
339 ** column iColRight of tab2.
341 static void addWhereTerm(
342 Parse
*pParse
, /* Parsing context */
343 SrcList
*pSrc
, /* List of tables in FROM clause */
344 int iLeft
, /* Index of first table to join in pSrc */
345 int iColLeft
, /* Index of column in first table */
346 int iRight
, /* Index of second table in pSrc */
347 int iColRight
, /* Index of column in second table */
348 int isOuterJoin
, /* True if this is an OUTER join */
349 Expr
**ppWhere
/* IN/OUT: The WHERE clause to add to */
351 sqlite3
*db
= pParse
->db
;
356 assert( iLeft
<iRight
);
357 assert( pSrc
->nSrc
>iRight
);
358 assert( pSrc
->a
[iLeft
].pTab
);
359 assert( pSrc
->a
[iRight
].pTab
);
361 pE1
= sqlite3CreateColumnExpr(db
, pSrc
, iLeft
, iColLeft
);
362 pE2
= sqlite3CreateColumnExpr(db
, pSrc
, iRight
, iColRight
);
364 pEq
= sqlite3PExpr(pParse
, TK_EQ
, pE1
, pE2
);
365 if( pEq
&& isOuterJoin
){
366 ExprSetProperty(pEq
, EP_FromJoin
);
367 assert( !ExprHasProperty(pEq
, EP_TokenOnly
|EP_Reduced
) );
368 ExprSetVVAProperty(pEq
, EP_NoReduce
);
369 pEq
->iRightJoinTable
= (i16
)pE2
->iTable
;
371 *ppWhere
= sqlite3ExprAnd(db
, *ppWhere
, pEq
);
375 ** Set the EP_FromJoin property on all terms of the given expression.
376 ** And set the Expr.iRightJoinTable to iTable for every term in the
379 ** The EP_FromJoin property is used on terms of an expression to tell
380 ** the LEFT OUTER JOIN processing logic that this term is part of the
381 ** join restriction specified in the ON or USING clause and not a part
382 ** of the more general WHERE clause. These terms are moved over to the
383 ** WHERE clause during join processing but we need to remember that they
384 ** originated in the ON or USING clause.
386 ** The Expr.iRightJoinTable tells the WHERE clause processing that the
387 ** expression depends on table iRightJoinTable even if that table is not
388 ** explicitly mentioned in the expression. That information is needed
389 ** for cases like this:
391 ** SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.b AND t1.x=5
393 ** The where clause needs to defer the handling of the t1.x=5
394 ** term until after the t2 loop of the join. In that way, a
395 ** NULL t2 row will be inserted whenever t1.x!=5. If we do not
396 ** defer the handling of t1.x=5, it will be processed immediately
397 ** after the t1 loop and rows with t1.x!=5 will never appear in
398 ** the output, which is incorrect.
400 static void setJoinExpr(Expr
*p
, int iTable
){
402 ExprSetProperty(p
, EP_FromJoin
);
403 assert( !ExprHasProperty(p
, EP_TokenOnly
|EP_Reduced
) );
404 ExprSetVVAProperty(p
, EP_NoReduce
);
405 p
->iRightJoinTable
= (i16
)iTable
;
406 if( p
->op
==TK_FUNCTION
&& p
->x
.pList
){
408 for(i
=0; i
<p
->x
.pList
->nExpr
; i
++){
409 setJoinExpr(p
->x
.pList
->a
[i
].pExpr
, iTable
);
412 setJoinExpr(p
->pLeft
, iTable
);
417 /* Undo the work of setJoinExpr(). In the expression tree p, convert every
418 ** term that is marked with EP_FromJoin and iRightJoinTable==iTable into
419 ** an ordinary term that omits the EP_FromJoin mark.
421 ** This happens when a LEFT JOIN is simplified into an ordinary JOIN.
423 static void unsetJoinExpr(Expr
*p
, int iTable
){
425 if( ExprHasProperty(p
, EP_FromJoin
)
426 && (iTable
<0 || p
->iRightJoinTable
==iTable
) ){
427 ExprClearProperty(p
, EP_FromJoin
);
429 if( p
->op
==TK_FUNCTION
&& p
->x
.pList
){
431 for(i
=0; i
<p
->x
.pList
->nExpr
; i
++){
432 unsetJoinExpr(p
->x
.pList
->a
[i
].pExpr
, iTable
);
435 unsetJoinExpr(p
->pLeft
, iTable
);
441 ** This routine processes the join information for a SELECT statement.
442 ** ON and USING clauses are converted into extra terms of the WHERE clause.
443 ** NATURAL joins also create extra WHERE clause terms.
445 ** The terms of a FROM clause are contained in the Select.pSrc structure.
446 ** The left most table is the first entry in Select.pSrc. The right-most
447 ** table is the last entry. The join operator is held in the entry to
448 ** the left. Thus entry 0 contains the join operator for the join between
449 ** entries 0 and 1. Any ON or USING clauses associated with the join are
450 ** also attached to the left entry.
452 ** This routine returns the number of errors encountered.
454 static int sqliteProcessJoin(Parse
*pParse
, Select
*p
){
455 SrcList
*pSrc
; /* All tables in the FROM clause */
456 int i
, j
; /* Loop counters */
457 struct SrcList_item
*pLeft
; /* Left table being joined */
458 struct SrcList_item
*pRight
; /* Right table being joined */
463 for(i
=0; i
<pSrc
->nSrc
-1; i
++, pRight
++, pLeft
++){
464 Table
*pRightTab
= pRight
->pTab
;
467 if( NEVER(pLeft
->pTab
==0 || pRightTab
==0) ) continue;
468 isOuter
= (pRight
->fg
.jointype
& JT_OUTER
)!=0;
470 /* When the NATURAL keyword is present, add WHERE clause terms for
471 ** every column that the two tables have in common.
473 if( pRight
->fg
.jointype
& JT_NATURAL
){
474 if( pRight
->pOn
|| pRight
->pUsing
){
475 sqlite3ErrorMsg(pParse
, "a NATURAL join may not have "
476 "an ON or USING clause", 0);
479 for(j
=0; j
<pRightTab
->nCol
; j
++){
480 char *zName
; /* Name of column in the right table */
481 int iLeft
; /* Matching left table */
482 int iLeftCol
; /* Matching column in the left table */
484 zName
= pRightTab
->aCol
[j
].zName
;
485 if( tableAndColumnIndex(pSrc
, i
+1, zName
, &iLeft
, &iLeftCol
) ){
486 addWhereTerm(pParse
, pSrc
, iLeft
, iLeftCol
, i
+1, j
,
487 isOuter
, &p
->pWhere
);
492 /* Disallow both ON and USING clauses in the same join
494 if( pRight
->pOn
&& pRight
->pUsing
){
495 sqlite3ErrorMsg(pParse
, "cannot have both ON and USING "
496 "clauses in the same join");
500 /* Add the ON clause to the end of the WHERE clause, connected by
504 if( isOuter
) setJoinExpr(pRight
->pOn
, pRight
->iCursor
);
505 p
->pWhere
= sqlite3ExprAnd(pParse
->db
, p
->pWhere
, pRight
->pOn
);
509 /* Create extra terms on the WHERE clause for each column named
510 ** in the USING clause. Example: If the two tables to be joined are
511 ** A and B and the USING clause names X, Y, and Z, then add this
512 ** to the WHERE clause: A.X=B.X AND A.Y=B.Y AND A.Z=B.Z
513 ** Report an error if any column mentioned in the USING clause is
514 ** not contained in both tables to be joined.
516 if( pRight
->pUsing
){
517 IdList
*pList
= pRight
->pUsing
;
518 for(j
=0; j
<pList
->nId
; j
++){
519 char *zName
; /* Name of the term in the USING clause */
520 int iLeft
; /* Table on the left with matching column name */
521 int iLeftCol
; /* Column number of matching column on the left */
522 int iRightCol
; /* Column number of matching column on the right */
524 zName
= pList
->a
[j
].zName
;
525 iRightCol
= columnIndex(pRightTab
, zName
);
527 || !tableAndColumnIndex(pSrc
, i
+1, zName
, &iLeft
, &iLeftCol
)
529 sqlite3ErrorMsg(pParse
, "cannot join using column %s - column "
530 "not present in both tables", zName
);
533 addWhereTerm(pParse
, pSrc
, iLeft
, iLeftCol
, i
+1, iRightCol
,
534 isOuter
, &p
->pWhere
);
542 ** An instance of this object holds information (beyond pParse and pSelect)
543 ** needed to load the next result row that is to be added to the sorter.
545 typedef struct RowLoadInfo RowLoadInfo
;
547 int regResult
; /* Store results in array of registers here */
548 u8 ecelFlags
; /* Flag argument to ExprCodeExprList() */
549 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
550 ExprList
*pExtra
; /* Extra columns needed by sorter refs */
551 int regExtraResult
; /* Where to load the extra columns */
556 ** This routine does the work of loading query data into an array of
557 ** registers so that it can be added to the sorter.
559 static void innerLoopLoadRow(
560 Parse
*pParse
, /* Statement under construction */
561 Select
*pSelect
, /* The query being coded */
562 RowLoadInfo
*pInfo
/* Info needed to complete the row load */
564 sqlite3ExprCodeExprList(pParse
, pSelect
->pEList
, pInfo
->regResult
,
565 0, pInfo
->ecelFlags
);
566 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
568 sqlite3ExprCodeExprList(pParse
, pInfo
->pExtra
, pInfo
->regExtraResult
, 0, 0);
569 sqlite3ExprListDelete(pParse
->db
, pInfo
->pExtra
);
575 ** Code the OP_MakeRecord instruction that generates the entry to be
576 ** added into the sorter.
578 ** Return the register in which the result is stored.
580 static int makeSorterRecord(
587 int nOBSat
= pSort
->nOBSat
;
588 Vdbe
*v
= pParse
->pVdbe
;
589 int regOut
= ++pParse
->nMem
;
590 if( pSort
->pDeferredRowLoad
){
591 innerLoopLoadRow(pParse
, pSelect
, pSort
->pDeferredRowLoad
);
593 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, regBase
+nOBSat
, nBase
-nOBSat
, regOut
);
598 ** Generate code that will push the record in registers regData
599 ** through regData+nData-1 onto the sorter.
601 static void pushOntoSorter(
602 Parse
*pParse
, /* Parser context */
603 SortCtx
*pSort
, /* Information about the ORDER BY clause */
604 Select
*pSelect
, /* The whole SELECT statement */
605 int regData
, /* First register holding data to be sorted */
606 int regOrigData
, /* First register holding data before packing */
607 int nData
, /* Number of elements in the regData data array */
608 int nPrefixReg
/* No. of reg prior to regData available for use */
610 Vdbe
*v
= pParse
->pVdbe
; /* Stmt under construction */
611 int bSeq
= ((pSort
->sortFlags
& SORTFLAG_UseSorter
)==0);
612 int nExpr
= pSort
->pOrderBy
->nExpr
; /* No. of ORDER BY terms */
613 int nBase
= nExpr
+ bSeq
+ nData
; /* Fields in sorter record */
614 int regBase
; /* Regs for sorter record */
615 int regRecord
= 0; /* Assembled sorter record */
616 int nOBSat
= pSort
->nOBSat
; /* ORDER BY terms to skip */
617 int op
; /* Opcode to add sorter record to sorter */
618 int iLimit
; /* LIMIT counter */
619 int iSkip
= 0; /* End of the sorter insert loop */
621 assert( bSeq
==0 || bSeq
==1 );
624 ** (1) The data to be sorted has already been packed into a Record
625 ** by a prior OP_MakeRecord. In this case nData==1 and regData
626 ** will be completely unrelated to regOrigData.
627 ** (2) All output columns are included in the sort record. In that
628 ** case regData==regOrigData.
629 ** (3) Some output columns are omitted from the sort record due to
630 ** the SQLITE_ENABLE_SORTER_REFERENCE optimization, or due to the
631 ** SQLITE_ECEL_OMITREF optimization, or due to the
632 ** SortCtx.pDeferredRowLoad optimiation. In any of these cases
633 ** regOrigData is 0 to prevent this routine from trying to copy
634 ** values that might not yet exist.
636 assert( nData
==1 || regData
==regOrigData
|| regOrigData
==0 );
639 assert( nPrefixReg
==nExpr
+bSeq
);
640 regBase
= regData
- nPrefixReg
;
642 regBase
= pParse
->nMem
+ 1;
643 pParse
->nMem
+= nBase
;
645 assert( pSelect
->iOffset
==0 || pSelect
->iLimit
!=0 );
646 iLimit
= pSelect
->iOffset
? pSelect
->iOffset
+1 : pSelect
->iLimit
;
647 pSort
->labelDone
= sqlite3VdbeMakeLabel(v
);
648 sqlite3ExprCodeExprList(pParse
, pSort
->pOrderBy
, regBase
, regOrigData
,
649 SQLITE_ECEL_DUP
| (regOrigData
? SQLITE_ECEL_REF
: 0));
651 sqlite3VdbeAddOp2(v
, OP_Sequence
, pSort
->iECursor
, regBase
+nExpr
);
653 if( nPrefixReg
==0 && nData
>0 ){
654 sqlite3ExprCodeMove(pParse
, regData
, regBase
+nExpr
+bSeq
, nData
);
657 int regPrevKey
; /* The first nOBSat columns of the previous row */
658 int addrFirst
; /* Address of the OP_IfNot opcode */
659 int addrJmp
; /* Address of the OP_Jump opcode */
660 VdbeOp
*pOp
; /* Opcode that opens the sorter */
661 int nKey
; /* Number of sorting key columns, including OP_Sequence */
662 KeyInfo
*pKI
; /* Original KeyInfo on the sorter table */
664 regRecord
= makeSorterRecord(pParse
, pSort
, pSelect
, regBase
, nBase
);
665 regPrevKey
= pParse
->nMem
+1;
666 pParse
->nMem
+= pSort
->nOBSat
;
667 nKey
= nExpr
- pSort
->nOBSat
+ bSeq
;
669 addrFirst
= sqlite3VdbeAddOp1(v
, OP_IfNot
, regBase
+nExpr
);
671 addrFirst
= sqlite3VdbeAddOp1(v
, OP_SequenceTest
, pSort
->iECursor
);
674 sqlite3VdbeAddOp3(v
, OP_Compare
, regPrevKey
, regBase
, pSort
->nOBSat
);
675 pOp
= sqlite3VdbeGetOp(v
, pSort
->addrSortIndex
);
676 if( pParse
->db
->mallocFailed
) return;
677 pOp
->p2
= nKey
+ nData
;
678 pKI
= pOp
->p4
.pKeyInfo
;
679 memset(pKI
->aSortOrder
, 0, pKI
->nKeyField
); /* Makes OP_Jump testable */
680 sqlite3VdbeChangeP4(v
, -1, (char*)pKI
, P4_KEYINFO
);
681 testcase( pKI
->nAllField
> pKI
->nKeyField
+2 );
682 pOp
->p4
.pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
,pSort
->pOrderBy
,nOBSat
,
683 pKI
->nAllField
-pKI
->nKeyField
-1);
684 addrJmp
= sqlite3VdbeCurrentAddr(v
);
685 sqlite3VdbeAddOp3(v
, OP_Jump
, addrJmp
+1, 0, addrJmp
+1); VdbeCoverage(v
);
686 pSort
->labelBkOut
= sqlite3VdbeMakeLabel(v
);
687 pSort
->regReturn
= ++pParse
->nMem
;
688 sqlite3VdbeAddOp2(v
, OP_Gosub
, pSort
->regReturn
, pSort
->labelBkOut
);
689 sqlite3VdbeAddOp1(v
, OP_ResetSorter
, pSort
->iECursor
);
691 sqlite3VdbeAddOp2(v
, OP_IfNot
, iLimit
, pSort
->labelDone
);
694 sqlite3VdbeJumpHere(v
, addrFirst
);
695 sqlite3ExprCodeMove(pParse
, regBase
, regPrevKey
, pSort
->nOBSat
);
696 sqlite3VdbeJumpHere(v
, addrJmp
);
699 /* At this point the values for the new sorter entry are stored
700 ** in an array of registers. They need to be composed into a record
701 ** and inserted into the sorter if either (a) there are currently
702 ** less than LIMIT+OFFSET items or (b) the new record is smaller than
703 ** the largest record currently in the sorter. If (b) is true and there
704 ** are already LIMIT+OFFSET items in the sorter, delete the largest
705 ** entry before inserting the new one. This way there are never more
706 ** than LIMIT+OFFSET items in the sorter.
708 ** If the new record does not need to be inserted into the sorter,
709 ** jump to the next iteration of the loop. Or, if the
710 ** pSort->bOrderedInnerLoop flag is set to indicate that the inner
711 ** loop delivers items in sorted order, jump to the next iteration
712 ** of the outer loop.
714 int iCsr
= pSort
->iECursor
;
715 sqlite3VdbeAddOp2(v
, OP_IfNotZero
, iLimit
, sqlite3VdbeCurrentAddr(v
)+4);
717 sqlite3VdbeAddOp2(v
, OP_Last
, iCsr
, 0);
718 iSkip
= sqlite3VdbeAddOp4Int(v
, OP_IdxLE
,
719 iCsr
, 0, regBase
+nOBSat
, nExpr
-nOBSat
);
721 sqlite3VdbeAddOp1(v
, OP_Delete
, iCsr
);
724 regRecord
= makeSorterRecord(pParse
, pSort
, pSelect
, regBase
, nBase
);
726 if( pSort
->sortFlags
& SORTFLAG_UseSorter
){
727 op
= OP_SorterInsert
;
731 sqlite3VdbeAddOp4Int(v
, op
, pSort
->iECursor
, regRecord
,
732 regBase
+nOBSat
, nBase
-nOBSat
);
734 assert( pSort
->bOrderedInnerLoop
==0 || pSort
->bOrderedInnerLoop
==1 );
735 sqlite3VdbeChangeP2(v
, iSkip
,
736 sqlite3VdbeCurrentAddr(v
) + pSort
->bOrderedInnerLoop
);
741 ** Add code to implement the OFFSET
743 static void codeOffset(
744 Vdbe
*v
, /* Generate code into this VM */
745 int iOffset
, /* Register holding the offset counter */
746 int iContinue
/* Jump here to skip the current record */
749 sqlite3VdbeAddOp3(v
, OP_IfPos
, iOffset
, iContinue
, 1); VdbeCoverage(v
);
750 VdbeComment((v
, "OFFSET"));
755 ** Add code that will check to make sure the N registers starting at iMem
756 ** form a distinct entry. iTab is a sorting index that holds previously
757 ** seen combinations of the N values. A new entry is made in iTab
758 ** if the current N values are new.
760 ** A jump to addrRepeat is made and the N+1 values are popped from the
761 ** stack if the top N elements are not distinct.
763 static void codeDistinct(
764 Parse
*pParse
, /* Parsing and code generating context */
765 int iTab
, /* A sorting index used to test for distinctness */
766 int addrRepeat
, /* Jump to here if not distinct */
767 int N
, /* Number of elements */
768 int iMem
/* First element */
774 r1
= sqlite3GetTempReg(pParse
);
775 sqlite3VdbeAddOp4Int(v
, OP_Found
, iTab
, addrRepeat
, iMem
, N
); VdbeCoverage(v
);
776 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, iMem
, N
, r1
);
777 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, iTab
, r1
, iMem
, N
);
778 sqlite3VdbeChangeP5(v
, OPFLAG_USESEEKRESULT
);
779 sqlite3ReleaseTempReg(pParse
, r1
);
782 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
784 ** This function is called as part of inner-loop generation for a SELECT
785 ** statement with an ORDER BY that is not optimized by an index. It
786 ** determines the expressions, if any, that the sorter-reference
787 ** optimization should be used for. The sorter-reference optimization
788 ** is used for SELECT queries like:
790 ** SELECT a, bigblob FROM t1 ORDER BY a LIMIT 10
792 ** If the optimization is used for expression "bigblob", then instead of
793 ** storing values read from that column in the sorter records, the PK of
794 ** the row from table t1 is stored instead. Then, as records are extracted from
795 ** the sorter to return to the user, the required value of bigblob is
796 ** retrieved directly from table t1. If the values are very large, this
797 ** can be more efficient than storing them directly in the sorter records.
799 ** The ExprList_item.bSorterRef flag is set for each expression in pEList
800 ** for which the sorter-reference optimization should be enabled.
801 ** Additionally, the pSort->aDefer[] array is populated with entries
802 ** for all cursors required to evaluate all selected expressions. Finally.
803 ** output variable (*ppExtra) is set to an expression list containing
804 ** expressions for all extra PK values that should be stored in the
807 static void selectExprDefer(
808 Parse
*pParse
, /* Leave any error here */
809 SortCtx
*pSort
, /* Sorter context */
810 ExprList
*pEList
, /* Expressions destined for sorter */
811 ExprList
**ppExtra
/* Expressions to append to sorter record */
815 ExprList
*pExtra
= 0;
816 for(i
=0; i
<pEList
->nExpr
; i
++){
817 struct ExprList_item
*pItem
= &pEList
->a
[i
];
818 if( pItem
->u
.x
.iOrderByCol
==0 ){
819 Expr
*pExpr
= pItem
->pExpr
;
820 Table
*pTab
= pExpr
->pTab
;
821 if( pExpr
->op
==TK_COLUMN
&& pExpr
->iColumn
>=0 && pTab
&& !IsVirtual(pTab
)
822 && (pTab
->aCol
[pExpr
->iColumn
].colFlags
& COLFLAG_SORTERREF
)
825 for(j
=0; j
<nDefer
; j
++){
826 if( pSort
->aDefer
[j
].iCsr
==pExpr
->iTable
) break;
829 if( nDefer
==ArraySize(pSort
->aDefer
) ){
835 if( !HasRowid(pTab
) ){
836 pPk
= sqlite3PrimaryKeyIndex(pTab
);
839 for(k
=0; k
<nKey
; k
++){
840 Expr
*pNew
= sqlite3PExpr(pParse
, TK_COLUMN
, 0, 0);
842 pNew
->iTable
= pExpr
->iTable
;
843 pNew
->pTab
= pExpr
->pTab
;
844 pNew
->iColumn
= pPk
? pPk
->aiColumn
[k
] : -1;
845 pExtra
= sqlite3ExprListAppend(pParse
, pExtra
, pNew
);
848 pSort
->aDefer
[nDefer
].pTab
= pExpr
->pTab
;
849 pSort
->aDefer
[nDefer
].iCsr
= pExpr
->iTable
;
850 pSort
->aDefer
[nDefer
].nKey
= nKey
;
854 pItem
->bSorterRef
= 1;
858 pSort
->nDefer
= (u8
)nDefer
;
864 ** This routine generates the code for the inside of the inner loop
867 ** If srcTab is negative, then the p->pEList expressions
868 ** are evaluated in order to get the data for this row. If srcTab is
869 ** zero or more, then data is pulled from srcTab and p->pEList is used only
870 ** to get the number of columns and the collation sequence for each column.
872 static void selectInnerLoop(
873 Parse
*pParse
, /* The parser context */
874 Select
*p
, /* The complete select statement being coded */
875 int srcTab
, /* Pull data from this table if non-negative */
876 SortCtx
*pSort
, /* If not NULL, info on how to process ORDER BY */
877 DistinctCtx
*pDistinct
, /* If not NULL, info on how to process DISTINCT */
878 SelectDest
*pDest
, /* How to dispose of the results */
879 int iContinue
, /* Jump here to continue with next row */
880 int iBreak
/* Jump here to break out of the inner loop */
882 Vdbe
*v
= pParse
->pVdbe
;
884 int hasDistinct
; /* True if the DISTINCT keyword is present */
885 int eDest
= pDest
->eDest
; /* How to dispose of results */
886 int iParm
= pDest
->iSDParm
; /* First argument to disposal method */
887 int nResultCol
; /* Number of result columns */
888 int nPrefixReg
= 0; /* Number of extra registers before regResult */
889 RowLoadInfo sRowLoadInfo
; /* Info for deferred row loading */
891 /* Usually, regResult is the first cell in an array of memory cells
892 ** containing the current result row. In this case regOrig is set to the
893 ** same value. However, if the results are being sent to the sorter, the
894 ** values for any expressions that are also part of the sort-key are omitted
895 ** from this array. In this case regOrig is set to zero. */
896 int regResult
; /* Start of memory holding current results */
897 int regOrig
; /* Start of memory holding full result (or 0) */
900 assert( p
->pEList
!=0 );
901 hasDistinct
= pDistinct
? pDistinct
->eTnctType
: WHERE_DISTINCT_NOOP
;
902 if( pSort
&& pSort
->pOrderBy
==0 ) pSort
= 0;
903 if( pSort
==0 && !hasDistinct
){
904 assert( iContinue
!=0 );
905 codeOffset(v
, p
->iOffset
, iContinue
);
908 /* Pull the requested columns.
910 nResultCol
= p
->pEList
->nExpr
;
912 if( pDest
->iSdst
==0 ){
914 nPrefixReg
= pSort
->pOrderBy
->nExpr
;
915 if( !(pSort
->sortFlags
& SORTFLAG_UseSorter
) ) nPrefixReg
++;
916 pParse
->nMem
+= nPrefixReg
;
918 pDest
->iSdst
= pParse
->nMem
+1;
919 pParse
->nMem
+= nResultCol
;
920 }else if( pDest
->iSdst
+nResultCol
> pParse
->nMem
){
921 /* This is an error condition that can result, for example, when a SELECT
922 ** on the right-hand side of an INSERT contains more result columns than
923 ** there are columns in the table on the left. The error will be caught
924 ** and reported later. But we need to make sure enough memory is allocated
925 ** to avoid other spurious errors in the meantime. */
926 pParse
->nMem
+= nResultCol
;
928 pDest
->nSdst
= nResultCol
;
929 regOrig
= regResult
= pDest
->iSdst
;
931 for(i
=0; i
<nResultCol
; i
++){
932 sqlite3VdbeAddOp3(v
, OP_Column
, srcTab
, i
, regResult
+i
);
933 VdbeComment((v
, "%s", p
->pEList
->a
[i
].zName
));
935 }else if( eDest
!=SRT_Exists
){
936 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
937 ExprList
*pExtra
= 0;
939 /* If the destination is an EXISTS(...) expression, the actual
940 ** values returned by the SELECT are not required.
942 u8 ecelFlags
; /* "ecel" is an abbreviation of "ExprCodeExprList" */
944 if( eDest
==SRT_Mem
|| eDest
==SRT_Output
|| eDest
==SRT_Coroutine
){
945 ecelFlags
= SQLITE_ECEL_DUP
;
949 if( pSort
&& hasDistinct
==0 && eDest
!=SRT_EphemTab
&& eDest
!=SRT_Table
){
950 /* For each expression in p->pEList that is a copy of an expression in
951 ** the ORDER BY clause (pSort->pOrderBy), set the associated
952 ** iOrderByCol value to one more than the index of the ORDER BY
953 ** expression within the sort-key that pushOntoSorter() will generate.
954 ** This allows the p->pEList field to be omitted from the sorted record,
955 ** saving space and CPU cycles. */
956 ecelFlags
|= (SQLITE_ECEL_OMITREF
|SQLITE_ECEL_REF
);
958 for(i
=pSort
->nOBSat
; i
<pSort
->pOrderBy
->nExpr
; i
++){
960 if( (j
= pSort
->pOrderBy
->a
[i
].u
.x
.iOrderByCol
)>0 ){
961 p
->pEList
->a
[j
-1].u
.x
.iOrderByCol
= i
+1-pSort
->nOBSat
;
964 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
965 selectExprDefer(pParse
, pSort
, p
->pEList
, &pExtra
);
966 if( pExtra
&& pParse
->db
->mallocFailed
==0 ){
967 /* If there are any extra PK columns to add to the sorter records,
968 ** allocate extra memory cells and adjust the OpenEphemeral
969 ** instruction to account for the larger records. This is only
970 ** required if there are one or more WITHOUT ROWID tables with
971 ** composite primary keys in the SortCtx.aDefer[] array. */
972 VdbeOp
*pOp
= sqlite3VdbeGetOp(v
, pSort
->addrSortIndex
);
973 pOp
->p2
+= (pExtra
->nExpr
- pSort
->nDefer
);
974 pOp
->p4
.pKeyInfo
->nAllField
+= (pExtra
->nExpr
- pSort
->nDefer
);
975 pParse
->nMem
+= pExtra
->nExpr
;
979 /* Adjust nResultCol to account for columns that are omitted
980 ** from the sorter by the optimizations in this branch */
982 for(i
=0; i
<pEList
->nExpr
; i
++){
983 if( pEList
->a
[i
].u
.x
.iOrderByCol
>0
984 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
985 || pEList
->a
[i
].bSorterRef
994 testcase( eDest
==SRT_Set
);
995 testcase( eDest
==SRT_Mem
);
996 testcase( eDest
==SRT_Coroutine
);
997 testcase( eDest
==SRT_Output
);
998 assert( eDest
==SRT_Set
|| eDest
==SRT_Mem
999 || eDest
==SRT_Coroutine
|| eDest
==SRT_Output
);
1001 sRowLoadInfo
.regResult
= regResult
;
1002 sRowLoadInfo
.ecelFlags
= ecelFlags
;
1003 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
1004 sRowLoadInfo
.pExtra
= pExtra
;
1005 sRowLoadInfo
.regExtraResult
= regResult
+ nResultCol
;
1006 if( pExtra
) nResultCol
+= pExtra
->nExpr
;
1009 && (ecelFlags
& SQLITE_ECEL_OMITREF
)!=0
1013 assert( hasDistinct
==0 );
1014 pSort
->pDeferredRowLoad
= &sRowLoadInfo
;
1017 innerLoopLoadRow(pParse
, p
, &sRowLoadInfo
);
1021 /* If the DISTINCT keyword was present on the SELECT statement
1022 ** and this row has been seen before, then do not make this row
1023 ** part of the result.
1026 switch( pDistinct
->eTnctType
){
1027 case WHERE_DISTINCT_ORDERED
: {
1028 VdbeOp
*pOp
; /* No longer required OpenEphemeral instr. */
1029 int iJump
; /* Jump destination */
1030 int regPrev
; /* Previous row content */
1032 /* Allocate space for the previous row */
1033 regPrev
= pParse
->nMem
+1;
1034 pParse
->nMem
+= nResultCol
;
1036 /* Change the OP_OpenEphemeral coded earlier to an OP_Null
1037 ** sets the MEM_Cleared bit on the first register of the
1038 ** previous value. This will cause the OP_Ne below to always
1039 ** fail on the first iteration of the loop even if the first
1040 ** row is all NULLs.
1042 sqlite3VdbeChangeToNoop(v
, pDistinct
->addrTnct
);
1043 pOp
= sqlite3VdbeGetOp(v
, pDistinct
->addrTnct
);
1044 pOp
->opcode
= OP_Null
;
1048 iJump
= sqlite3VdbeCurrentAddr(v
) + nResultCol
;
1049 for(i
=0; i
<nResultCol
; i
++){
1050 CollSeq
*pColl
= sqlite3ExprCollSeq(pParse
, p
->pEList
->a
[i
].pExpr
);
1051 if( i
<nResultCol
-1 ){
1052 sqlite3VdbeAddOp3(v
, OP_Ne
, regResult
+i
, iJump
, regPrev
+i
);
1055 sqlite3VdbeAddOp3(v
, OP_Eq
, regResult
+i
, iContinue
, regPrev
+i
);
1058 sqlite3VdbeChangeP4(v
, -1, (const char *)pColl
, P4_COLLSEQ
);
1059 sqlite3VdbeChangeP5(v
, SQLITE_NULLEQ
);
1061 assert( sqlite3VdbeCurrentAddr(v
)==iJump
|| pParse
->db
->mallocFailed
);
1062 sqlite3VdbeAddOp3(v
, OP_Copy
, regResult
, regPrev
, nResultCol
-1);
1066 case WHERE_DISTINCT_UNIQUE
: {
1067 sqlite3VdbeChangeToNoop(v
, pDistinct
->addrTnct
);
1072 assert( pDistinct
->eTnctType
==WHERE_DISTINCT_UNORDERED
);
1073 codeDistinct(pParse
, pDistinct
->tabTnct
, iContinue
, nResultCol
,
1079 codeOffset(v
, p
->iOffset
, iContinue
);
1084 /* In this mode, write each query result to the key of the temporary
1087 #ifndef SQLITE_OMIT_COMPOUND_SELECT
1090 r1
= sqlite3GetTempReg(pParse
);
1091 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, regResult
, nResultCol
, r1
);
1092 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, iParm
, r1
, regResult
, nResultCol
);
1093 sqlite3ReleaseTempReg(pParse
, r1
);
1097 /* Construct a record from the query result, but instead of
1098 ** saving that record, use it as a key to delete elements from
1099 ** the temporary table iParm.
1102 sqlite3VdbeAddOp3(v
, OP_IdxDelete
, iParm
, regResult
, nResultCol
);
1105 #endif /* SQLITE_OMIT_COMPOUND_SELECT */
1107 /* Store the result as data using a unique key.
1112 case SRT_EphemTab
: {
1113 int r1
= sqlite3GetTempRange(pParse
, nPrefixReg
+1);
1114 testcase( eDest
==SRT_Table
);
1115 testcase( eDest
==SRT_EphemTab
);
1116 testcase( eDest
==SRT_Fifo
);
1117 testcase( eDest
==SRT_DistFifo
);
1118 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, regResult
, nResultCol
, r1
+nPrefixReg
);
1119 #ifndef SQLITE_OMIT_CTE
1120 if( eDest
==SRT_DistFifo
){
1121 /* If the destination is DistFifo, then cursor (iParm+1) is open
1122 ** on an ephemeral index. If the current row is already present
1123 ** in the index, do not write it to the output. If not, add the
1124 ** current row to the index and proceed with writing it to the
1125 ** output table as well. */
1126 int addr
= sqlite3VdbeCurrentAddr(v
) + 4;
1127 sqlite3VdbeAddOp4Int(v
, OP_Found
, iParm
+1, addr
, r1
, 0);
1129 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, iParm
+1, r1
,regResult
,nResultCol
);
1134 assert( regResult
==regOrig
);
1135 pushOntoSorter(pParse
, pSort
, p
, r1
+nPrefixReg
, regOrig
, 1, nPrefixReg
);
1137 int r2
= sqlite3GetTempReg(pParse
);
1138 sqlite3VdbeAddOp2(v
, OP_NewRowid
, iParm
, r2
);
1139 sqlite3VdbeAddOp3(v
, OP_Insert
, iParm
, r1
, r2
);
1140 sqlite3VdbeChangeP5(v
, OPFLAG_APPEND
);
1141 sqlite3ReleaseTempReg(pParse
, r2
);
1143 sqlite3ReleaseTempRange(pParse
, r1
, nPrefixReg
+1);
1147 #ifndef SQLITE_OMIT_SUBQUERY
1148 /* If we are creating a set for an "expr IN (SELECT ...)" construct,
1149 ** then there should be a single item on the stack. Write this
1150 ** item into the set table with bogus data.
1154 /* At first glance you would think we could optimize out the
1155 ** ORDER BY in this case since the order of entries in the set
1156 ** does not matter. But there might be a LIMIT clause, in which
1157 ** case the order does matter */
1159 pParse
, pSort
, p
, regResult
, regOrig
, nResultCol
, nPrefixReg
);
1161 int r1
= sqlite3GetTempReg(pParse
);
1162 assert( sqlite3Strlen30(pDest
->zAffSdst
)==nResultCol
);
1163 sqlite3VdbeAddOp4(v
, OP_MakeRecord
, regResult
, nResultCol
,
1164 r1
, pDest
->zAffSdst
, nResultCol
);
1165 sqlite3ExprCacheAffinityChange(pParse
, regResult
, nResultCol
);
1166 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, iParm
, r1
, regResult
, nResultCol
);
1167 sqlite3ReleaseTempReg(pParse
, r1
);
1172 /* If any row exist in the result set, record that fact and abort.
1175 sqlite3VdbeAddOp2(v
, OP_Integer
, 1, iParm
);
1176 /* The LIMIT clause will terminate the loop for us */
1180 /* If this is a scalar select that is part of an expression, then
1181 ** store the results in the appropriate memory cell or array of
1182 ** memory cells and break out of the scan loop.
1186 assert( nResultCol
<=pDest
->nSdst
);
1188 pParse
, pSort
, p
, regResult
, regOrig
, nResultCol
, nPrefixReg
);
1190 assert( nResultCol
==pDest
->nSdst
);
1191 assert( regResult
==iParm
);
1192 /* The LIMIT clause will jump out of the loop for us */
1196 #endif /* #ifndef SQLITE_OMIT_SUBQUERY */
1198 case SRT_Coroutine
: /* Send data to a co-routine */
1199 case SRT_Output
: { /* Return the results */
1200 testcase( eDest
==SRT_Coroutine
);
1201 testcase( eDest
==SRT_Output
);
1203 pushOntoSorter(pParse
, pSort
, p
, regResult
, regOrig
, nResultCol
,
1205 }else if( eDest
==SRT_Coroutine
){
1206 sqlite3VdbeAddOp1(v
, OP_Yield
, pDest
->iSDParm
);
1208 sqlite3VdbeAddOp2(v
, OP_ResultRow
, regResult
, nResultCol
);
1209 sqlite3ExprCacheAffinityChange(pParse
, regResult
, nResultCol
);
1214 #ifndef SQLITE_OMIT_CTE
1215 /* Write the results into a priority queue that is order according to
1216 ** pDest->pOrderBy (in pSO). pDest->iSDParm (in iParm) is the cursor for an
1217 ** index with pSO->nExpr+2 columns. Build a key using pSO for the first
1218 ** pSO->nExpr columns, then make sure all keys are unique by adding a
1219 ** final OP_Sequence column. The last column is the record as a blob.
1227 pSO
= pDest
->pOrderBy
;
1230 r1
= sqlite3GetTempReg(pParse
);
1231 r2
= sqlite3GetTempRange(pParse
, nKey
+2);
1233 if( eDest
==SRT_DistQueue
){
1234 /* If the destination is DistQueue, then cursor (iParm+1) is open
1235 ** on a second ephemeral index that holds all values every previously
1236 ** added to the queue. */
1237 addrTest
= sqlite3VdbeAddOp4Int(v
, OP_Found
, iParm
+1, 0,
1238 regResult
, nResultCol
);
1241 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, regResult
, nResultCol
, r3
);
1242 if( eDest
==SRT_DistQueue
){
1243 sqlite3VdbeAddOp2(v
, OP_IdxInsert
, iParm
+1, r3
);
1244 sqlite3VdbeChangeP5(v
, OPFLAG_USESEEKRESULT
);
1246 for(i
=0; i
<nKey
; i
++){
1247 sqlite3VdbeAddOp2(v
, OP_SCopy
,
1248 regResult
+ pSO
->a
[i
].u
.x
.iOrderByCol
- 1,
1251 sqlite3VdbeAddOp2(v
, OP_Sequence
, iParm
, r2
+nKey
);
1252 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, r2
, nKey
+2, r1
);
1253 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, iParm
, r1
, r2
, nKey
+2);
1254 if( addrTest
) sqlite3VdbeJumpHere(v
, addrTest
);
1255 sqlite3ReleaseTempReg(pParse
, r1
);
1256 sqlite3ReleaseTempRange(pParse
, r2
, nKey
+2);
1259 #endif /* SQLITE_OMIT_CTE */
1263 #if !defined(SQLITE_OMIT_TRIGGER)
1264 /* Discard the results. This is used for SELECT statements inside
1265 ** the body of a TRIGGER. The purpose of such selects is to call
1266 ** user-defined functions that have side effects. We do not care
1267 ** about the actual results of the select.
1270 assert( eDest
==SRT_Discard
);
1276 /* Jump to the end of the loop if the LIMIT is reached. Except, if
1277 ** there is a sorter, in which case the sorter has already limited
1278 ** the output for us.
1280 if( pSort
==0 && p
->iLimit
){
1281 sqlite3VdbeAddOp2(v
, OP_DecrJumpZero
, p
->iLimit
, iBreak
); VdbeCoverage(v
);
1286 ** Allocate a KeyInfo object sufficient for an index of N key columns and
1289 KeyInfo
*sqlite3KeyInfoAlloc(sqlite3
*db
, int N
, int X
){
1290 int nExtra
= (N
+X
)*(sizeof(CollSeq
*)+1) - sizeof(CollSeq
*);
1291 KeyInfo
*p
= sqlite3DbMallocRawNN(db
, sizeof(KeyInfo
) + nExtra
);
1293 p
->aSortOrder
= (u8
*)&p
->aColl
[N
+X
];
1294 p
->nKeyField
= (u16
)N
;
1295 p
->nAllField
= (u16
)(N
+X
);
1299 memset(&p
[1], 0, nExtra
);
1301 sqlite3OomFault(db
);
1307 ** Deallocate a KeyInfo object
1309 void sqlite3KeyInfoUnref(KeyInfo
*p
){
1311 assert( p
->nRef
>0 );
1313 if( p
->nRef
==0 ) sqlite3DbFreeNN(p
->db
, p
);
1318 ** Make a new pointer to a KeyInfo object
1320 KeyInfo
*sqlite3KeyInfoRef(KeyInfo
*p
){
1322 assert( p
->nRef
>0 );
1330 ** Return TRUE if a KeyInfo object can be change. The KeyInfo object
1331 ** can only be changed if this is just a single reference to the object.
1333 ** This routine is used only inside of assert() statements.
1335 int sqlite3KeyInfoIsWriteable(KeyInfo
*p
){ return p
->nRef
==1; }
1336 #endif /* SQLITE_DEBUG */
1339 ** Given an expression list, generate a KeyInfo structure that records
1340 ** the collating sequence for each expression in that expression list.
1342 ** If the ExprList is an ORDER BY or GROUP BY clause then the resulting
1343 ** KeyInfo structure is appropriate for initializing a virtual index to
1344 ** implement that clause. If the ExprList is the result set of a SELECT
1345 ** then the KeyInfo structure is appropriate for initializing a virtual
1346 ** index to implement a DISTINCT test.
1348 ** Space to hold the KeyInfo structure is obtained from malloc. The calling
1349 ** function is responsible for seeing that this structure is eventually
1352 KeyInfo
*sqlite3KeyInfoFromExprList(
1353 Parse
*pParse
, /* Parsing context */
1354 ExprList
*pList
, /* Form the KeyInfo object from this ExprList */
1355 int iStart
, /* Begin with this column of pList */
1356 int nExtra
/* Add this many extra columns to the end */
1360 struct ExprList_item
*pItem
;
1361 sqlite3
*db
= pParse
->db
;
1364 nExpr
= pList
->nExpr
;
1365 pInfo
= sqlite3KeyInfoAlloc(db
, nExpr
-iStart
, nExtra
+1);
1367 assert( sqlite3KeyInfoIsWriteable(pInfo
) );
1368 for(i
=iStart
, pItem
=pList
->a
+iStart
; i
<nExpr
; i
++, pItem
++){
1369 pInfo
->aColl
[i
-iStart
] = sqlite3ExprNNCollSeq(pParse
, pItem
->pExpr
);
1370 pInfo
->aSortOrder
[i
-iStart
] = pItem
->sortOrder
;
1377 ** Name of the connection operator, used for error messages.
1379 static const char *selectOpName(int id
){
1382 case TK_ALL
: z
= "UNION ALL"; break;
1383 case TK_INTERSECT
: z
= "INTERSECT"; break;
1384 case TK_EXCEPT
: z
= "EXCEPT"; break;
1385 default: z
= "UNION"; break;
1390 #ifndef SQLITE_OMIT_EXPLAIN
1392 ** Unless an "EXPLAIN QUERY PLAN" command is being processed, this function
1393 ** is a no-op. Otherwise, it adds a single row of output to the EQP result,
1394 ** where the caption is of the form:
1396 ** "USE TEMP B-TREE FOR xxx"
1398 ** where xxx is one of "DISTINCT", "ORDER BY" or "GROUP BY". Exactly which
1399 ** is determined by the zUsage argument.
1401 static void explainTempTable(Parse
*pParse
, const char *zUsage
){
1402 ExplainQueryPlan((pParse
, 0, "USE TEMP B-TREE FOR %s", zUsage
));
1406 ** Assign expression b to lvalue a. A second, no-op, version of this macro
1407 ** is provided when SQLITE_OMIT_EXPLAIN is defined. This allows the code
1408 ** in sqlite3Select() to assign values to structure member variables that
1409 ** only exist if SQLITE_OMIT_EXPLAIN is not defined without polluting the
1410 ** code with #ifndef directives.
1412 # define explainSetInteger(a, b) a = b
1415 /* No-op versions of the explainXXX() functions and macros. */
1416 # define explainTempTable(y,z)
1417 # define explainSetInteger(y,z)
1422 ** If the inner loop was generated using a non-null pOrderBy argument,
1423 ** then the results were placed in a sorter. After the loop is terminated
1424 ** we need to run the sorter and output the results. The following
1425 ** routine generates the code needed to do that.
1427 static void generateSortTail(
1428 Parse
*pParse
, /* Parsing context */
1429 Select
*p
, /* The SELECT statement */
1430 SortCtx
*pSort
, /* Information on the ORDER BY clause */
1431 int nColumn
, /* Number of columns of data */
1432 SelectDest
*pDest
/* Write the sorted results here */
1434 Vdbe
*v
= pParse
->pVdbe
; /* The prepared statement */
1435 int addrBreak
= pSort
->labelDone
; /* Jump here to exit loop */
1436 int addrContinue
= sqlite3VdbeMakeLabel(v
); /* Jump here for next cycle */
1437 int addr
; /* Top of output loop. Jump for Next. */
1440 ExprList
*pOrderBy
= pSort
->pOrderBy
;
1441 int eDest
= pDest
->eDest
;
1442 int iParm
= pDest
->iSDParm
;
1446 int nKey
; /* Number of key columns in sorter record */
1447 int iSortTab
; /* Sorter cursor to read from */
1449 int bSeq
; /* True if sorter record includes seq. no. */
1451 struct ExprList_item
*aOutEx
= p
->pEList
->a
;
1453 assert( addrBreak
<0 );
1454 if( pSort
->labelBkOut
){
1455 sqlite3VdbeAddOp2(v
, OP_Gosub
, pSort
->regReturn
, pSort
->labelBkOut
);
1456 sqlite3VdbeGoto(v
, addrBreak
);
1457 sqlite3VdbeResolveLabel(v
, pSort
->labelBkOut
);
1460 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
1461 /* Open any cursors needed for sorter-reference expressions */
1462 for(i
=0; i
<pSort
->nDefer
; i
++){
1463 Table
*pTab
= pSort
->aDefer
[i
].pTab
;
1464 int iDb
= sqlite3SchemaToIndex(pParse
->db
, pTab
->pSchema
);
1465 sqlite3OpenTable(pParse
, pSort
->aDefer
[i
].iCsr
, iDb
, pTab
, OP_OpenRead
);
1466 nRefKey
= MAX(nRefKey
, pSort
->aDefer
[i
].nKey
);
1470 iTab
= pSort
->iECursor
;
1471 if( eDest
==SRT_Output
|| eDest
==SRT_Coroutine
|| eDest
==SRT_Mem
){
1473 regRow
= pDest
->iSdst
;
1475 regRowid
= sqlite3GetTempReg(pParse
);
1476 regRow
= sqlite3GetTempRange(pParse
, nColumn
);
1478 nKey
= pOrderBy
->nExpr
- pSort
->nOBSat
;
1479 if( pSort
->sortFlags
& SORTFLAG_UseSorter
){
1480 int regSortOut
= ++pParse
->nMem
;
1481 iSortTab
= pParse
->nTab
++;
1482 if( pSort
->labelBkOut
){
1483 addrOnce
= sqlite3VdbeAddOp0(v
, OP_Once
); VdbeCoverage(v
);
1485 sqlite3VdbeAddOp3(v
, OP_OpenPseudo
, iSortTab
, regSortOut
,
1486 nKey
+1+nColumn
+nRefKey
);
1487 if( addrOnce
) sqlite3VdbeJumpHere(v
, addrOnce
);
1488 addr
= 1 + sqlite3VdbeAddOp2(v
, OP_SorterSort
, iTab
, addrBreak
);
1490 codeOffset(v
, p
->iOffset
, addrContinue
);
1491 sqlite3VdbeAddOp3(v
, OP_SorterData
, iTab
, regSortOut
, iSortTab
);
1494 addr
= 1 + sqlite3VdbeAddOp2(v
, OP_Sort
, iTab
, addrBreak
); VdbeCoverage(v
);
1495 codeOffset(v
, p
->iOffset
, addrContinue
);
1499 for(i
=0, iCol
=nKey
+bSeq
-1; i
<nColumn
; i
++){
1500 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
1501 if( aOutEx
[i
].bSorterRef
) continue;
1503 if( aOutEx
[i
].u
.x
.iOrderByCol
==0 ) iCol
++;
1505 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
1506 if( pSort
->nDefer
){
1508 int regKey
= sqlite3GetTempRange(pParse
, nRefKey
);
1510 for(i
=0; i
<pSort
->nDefer
; i
++){
1511 int iCsr
= pSort
->aDefer
[i
].iCsr
;
1512 Table
*pTab
= pSort
->aDefer
[i
].pTab
;
1513 int nKey
= pSort
->aDefer
[i
].nKey
;
1515 sqlite3VdbeAddOp1(v
, OP_NullRow
, iCsr
);
1516 if( HasRowid(pTab
) ){
1517 sqlite3VdbeAddOp3(v
, OP_Column
, iSortTab
, iKey
++, regKey
);
1518 sqlite3VdbeAddOp3(v
, OP_SeekRowid
, iCsr
,
1519 sqlite3VdbeCurrentAddr(v
)+1, regKey
);
1523 assert( sqlite3PrimaryKeyIndex(pTab
)->nKeyCol
==nKey
);
1524 for(k
=0; k
<nKey
; k
++){
1525 sqlite3VdbeAddOp3(v
, OP_Column
, iSortTab
, iKey
++, regKey
+k
);
1527 iJmp
= sqlite3VdbeCurrentAddr(v
);
1528 sqlite3VdbeAddOp4Int(v
, OP_SeekGE
, iCsr
, iJmp
+2, regKey
, nKey
);
1529 sqlite3VdbeAddOp4Int(v
, OP_IdxLE
, iCsr
, iJmp
+3, regKey
, nKey
);
1530 sqlite3VdbeAddOp1(v
, OP_NullRow
, iCsr
);
1533 sqlite3ReleaseTempRange(pParse
, regKey
, nRefKey
);
1536 for(i
=nColumn
-1; i
>=0; i
--){
1537 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
1538 if( aOutEx
[i
].bSorterRef
){
1539 sqlite3ExprCode(pParse
, aOutEx
[i
].pExpr
, regRow
+i
);
1544 if( aOutEx
[i
].u
.x
.iOrderByCol
){
1545 iRead
= aOutEx
[i
].u
.x
.iOrderByCol
-1;
1549 sqlite3VdbeAddOp3(v
, OP_Column
, iSortTab
, iRead
, regRow
+i
);
1550 VdbeComment((v
, "%s", aOutEx
[i
].zName
?aOutEx
[i
].zName
: aOutEx
[i
].zSpan
));
1555 case SRT_EphemTab
: {
1556 sqlite3VdbeAddOp2(v
, OP_NewRowid
, iParm
, regRowid
);
1557 sqlite3VdbeAddOp3(v
, OP_Insert
, iParm
, regRow
, regRowid
);
1558 sqlite3VdbeChangeP5(v
, OPFLAG_APPEND
);
1561 #ifndef SQLITE_OMIT_SUBQUERY
1563 assert( nColumn
==sqlite3Strlen30(pDest
->zAffSdst
) );
1564 sqlite3VdbeAddOp4(v
, OP_MakeRecord
, regRow
, nColumn
, regRowid
,
1565 pDest
->zAffSdst
, nColumn
);
1566 sqlite3ExprCacheAffinityChange(pParse
, regRow
, nColumn
);
1567 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, iParm
, regRowid
, regRow
, nColumn
);
1571 /* The LIMIT clause will terminate the loop for us */
1576 assert( eDest
==SRT_Output
|| eDest
==SRT_Coroutine
);
1577 testcase( eDest
==SRT_Output
);
1578 testcase( eDest
==SRT_Coroutine
);
1579 if( eDest
==SRT_Output
){
1580 sqlite3VdbeAddOp2(v
, OP_ResultRow
, pDest
->iSdst
, nColumn
);
1581 sqlite3ExprCacheAffinityChange(pParse
, pDest
->iSdst
, nColumn
);
1583 sqlite3VdbeAddOp1(v
, OP_Yield
, pDest
->iSDParm
);
1589 if( eDest
==SRT_Set
){
1590 sqlite3ReleaseTempRange(pParse
, regRow
, nColumn
);
1592 sqlite3ReleaseTempReg(pParse
, regRow
);
1594 sqlite3ReleaseTempReg(pParse
, regRowid
);
1596 /* The bottom of the loop
1598 sqlite3VdbeResolveLabel(v
, addrContinue
);
1599 if( pSort
->sortFlags
& SORTFLAG_UseSorter
){
1600 sqlite3VdbeAddOp2(v
, OP_SorterNext
, iTab
, addr
); VdbeCoverage(v
);
1602 sqlite3VdbeAddOp2(v
, OP_Next
, iTab
, addr
); VdbeCoverage(v
);
1604 if( pSort
->regReturn
) sqlite3VdbeAddOp1(v
, OP_Return
, pSort
->regReturn
);
1605 sqlite3VdbeResolveLabel(v
, addrBreak
);
1609 ** Return a pointer to a string containing the 'declaration type' of the
1610 ** expression pExpr. The string may be treated as static by the caller.
1612 ** Also try to estimate the size of the returned value and return that
1613 ** result in *pEstWidth.
1615 ** The declaration type is the exact datatype definition extracted from the
1616 ** original CREATE TABLE statement if the expression is a column. The
1617 ** declaration type for a ROWID field is INTEGER. Exactly when an expression
1618 ** is considered a column can be complex in the presence of subqueries. The
1619 ** result-set expression in all of the following SELECT statements is
1620 ** considered a column by this function.
1622 ** SELECT col FROM tbl;
1623 ** SELECT (SELECT col FROM tbl;
1624 ** SELECT (SELECT col FROM tbl);
1625 ** SELECT abc FROM (SELECT col AS abc FROM tbl);
1627 ** The declaration type for any expression other than a column is NULL.
1629 ** This routine has either 3 or 6 parameters depending on whether or not
1630 ** the SQLITE_ENABLE_COLUMN_METADATA compile-time option is used.
1632 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1633 # define columnType(A,B,C,D,E) columnTypeImpl(A,B,C,D,E)
1634 #else /* if !defined(SQLITE_ENABLE_COLUMN_METADATA) */
1635 # define columnType(A,B,C,D,E) columnTypeImpl(A,B)
1637 static const char *columnTypeImpl(
1639 #ifndef SQLITE_ENABLE_COLUMN_METADATA
1643 const char **pzOrigDb
,
1644 const char **pzOrigTab
,
1645 const char **pzOrigCol
1648 char const *zType
= 0;
1650 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1651 char const *zOrigDb
= 0;
1652 char const *zOrigTab
= 0;
1653 char const *zOrigCol
= 0;
1657 assert( pNC
->pSrcList
!=0 );
1658 assert( pExpr
->op
!=TK_AGG_COLUMN
); /* This routine runes before aggregates
1660 switch( pExpr
->op
){
1662 /* The expression is a column. Locate the table the column is being
1663 ** extracted from in NameContext.pSrcList. This table may be real
1664 ** database table or a subquery.
1666 Table
*pTab
= 0; /* Table structure column is extracted from */
1667 Select
*pS
= 0; /* Select the column is extracted from */
1668 int iCol
= pExpr
->iColumn
; /* Index of column in pTab */
1669 while( pNC
&& !pTab
){
1670 SrcList
*pTabList
= pNC
->pSrcList
;
1671 for(j
=0;j
<pTabList
->nSrc
&& pTabList
->a
[j
].iCursor
!=pExpr
->iTable
;j
++);
1672 if( j
<pTabList
->nSrc
){
1673 pTab
= pTabList
->a
[j
].pTab
;
1674 pS
= pTabList
->a
[j
].pSelect
;
1681 /* At one time, code such as "SELECT new.x" within a trigger would
1682 ** cause this condition to run. Since then, we have restructured how
1683 ** trigger code is generated and so this condition is no longer
1684 ** possible. However, it can still be true for statements like
1687 ** CREATE TABLE t1(col INTEGER);
1688 ** SELECT (SELECT t1.col) FROM FROM t1;
1690 ** when columnType() is called on the expression "t1.col" in the
1691 ** sub-select. In this case, set the column type to NULL, even
1692 ** though it should really be "INTEGER".
1694 ** This is not a problem, as the column type of "t1.col" is never
1695 ** used. When columnType() is called on the expression
1696 ** "(SELECT t1.col)", the correct type is returned (see the TK_SELECT
1701 assert( pTab
&& pExpr
->pTab
==pTab
);
1703 /* The "table" is actually a sub-select or a view in the FROM clause
1704 ** of the SELECT statement. Return the declaration type and origin
1705 ** data for the result-set column of the sub-select.
1707 if( iCol
>=0 && iCol
<pS
->pEList
->nExpr
){
1708 /* If iCol is less than zero, then the expression requests the
1709 ** rowid of the sub-select or view. This expression is legal (see
1710 ** test case misc2.2.2) - it always evaluates to NULL.
1713 Expr
*p
= pS
->pEList
->a
[iCol
].pExpr
;
1714 sNC
.pSrcList
= pS
->pSrc
;
1716 sNC
.pParse
= pNC
->pParse
;
1717 zType
= columnType(&sNC
, p
,&zOrigDb
,&zOrigTab
,&zOrigCol
);
1720 /* A real table or a CTE table */
1722 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1723 if( iCol
<0 ) iCol
= pTab
->iPKey
;
1724 assert( iCol
==XN_ROWID
|| (iCol
>=0 && iCol
<pTab
->nCol
) );
1729 zOrigCol
= pTab
->aCol
[iCol
].zName
;
1730 zType
= sqlite3ColumnType(&pTab
->aCol
[iCol
],0);
1732 zOrigTab
= pTab
->zName
;
1733 if( pNC
->pParse
&& pTab
->pSchema
){
1734 int iDb
= sqlite3SchemaToIndex(pNC
->pParse
->db
, pTab
->pSchema
);
1735 zOrigDb
= pNC
->pParse
->db
->aDb
[iDb
].zDbSName
;
1738 assert( iCol
==XN_ROWID
|| (iCol
>=0 && iCol
<pTab
->nCol
) );
1742 zType
= sqlite3ColumnType(&pTab
->aCol
[iCol
],0);
1748 #ifndef SQLITE_OMIT_SUBQUERY
1750 /* The expression is a sub-select. Return the declaration type and
1751 ** origin info for the single column in the result set of the SELECT
1755 Select
*pS
= pExpr
->x
.pSelect
;
1756 Expr
*p
= pS
->pEList
->a
[0].pExpr
;
1757 assert( ExprHasProperty(pExpr
, EP_xIsSelect
) );
1758 sNC
.pSrcList
= pS
->pSrc
;
1760 sNC
.pParse
= pNC
->pParse
;
1761 zType
= columnType(&sNC
, p
, &zOrigDb
, &zOrigTab
, &zOrigCol
);
1767 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1769 assert( pzOrigTab
&& pzOrigCol
);
1770 *pzOrigDb
= zOrigDb
;
1771 *pzOrigTab
= zOrigTab
;
1772 *pzOrigCol
= zOrigCol
;
1779 ** Generate code that will tell the VDBE the declaration types of columns
1780 ** in the result set.
1782 static void generateColumnTypes(
1783 Parse
*pParse
, /* Parser context */
1784 SrcList
*pTabList
, /* List of tables */
1785 ExprList
*pEList
/* Expressions defining the result set */
1787 #ifndef SQLITE_OMIT_DECLTYPE
1788 Vdbe
*v
= pParse
->pVdbe
;
1791 sNC
.pSrcList
= pTabList
;
1792 sNC
.pParse
= pParse
;
1794 for(i
=0; i
<pEList
->nExpr
; i
++){
1795 Expr
*p
= pEList
->a
[i
].pExpr
;
1797 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1798 const char *zOrigDb
= 0;
1799 const char *zOrigTab
= 0;
1800 const char *zOrigCol
= 0;
1801 zType
= columnType(&sNC
, p
, &zOrigDb
, &zOrigTab
, &zOrigCol
);
1803 /* The vdbe must make its own copy of the column-type and other
1804 ** column specific strings, in case the schema is reset before this
1805 ** virtual machine is deleted.
1807 sqlite3VdbeSetColName(v
, i
, COLNAME_DATABASE
, zOrigDb
, SQLITE_TRANSIENT
);
1808 sqlite3VdbeSetColName(v
, i
, COLNAME_TABLE
, zOrigTab
, SQLITE_TRANSIENT
);
1809 sqlite3VdbeSetColName(v
, i
, COLNAME_COLUMN
, zOrigCol
, SQLITE_TRANSIENT
);
1811 zType
= columnType(&sNC
, p
, 0, 0, 0);
1813 sqlite3VdbeSetColName(v
, i
, COLNAME_DECLTYPE
, zType
, SQLITE_TRANSIENT
);
1815 #endif /* !defined(SQLITE_OMIT_DECLTYPE) */
1820 ** Compute the column names for a SELECT statement.
1822 ** The only guarantee that SQLite makes about column names is that if the
1823 ** column has an AS clause assigning it a name, that will be the name used.
1824 ** That is the only documented guarantee. However, countless applications
1825 ** developed over the years have made baseless assumptions about column names
1826 ** and will break if those assumptions changes. Hence, use extreme caution
1827 ** when modifying this routine to avoid breaking legacy.
1829 ** See Also: sqlite3ColumnsFromExprList()
1831 ** The PRAGMA short_column_names and PRAGMA full_column_names settings are
1832 ** deprecated. The default setting is short=ON, full=OFF. 99.9% of all
1833 ** applications should operate this way. Nevertheless, we need to support the
1834 ** other modes for legacy:
1836 ** short=OFF, full=OFF: Column name is the text of the expression has it
1837 ** originally appears in the SELECT statement. In
1838 ** other words, the zSpan of the result expression.
1840 ** short=ON, full=OFF: (This is the default setting). If the result
1841 ** refers directly to a table column, then the
1842 ** result column name is just the table column
1843 ** name: COLUMN. Otherwise use zSpan.
1845 ** full=ON, short=ANY: If the result refers directly to a table column,
1846 ** then the result column name with the table name
1847 ** prefix, ex: TABLE.COLUMN. Otherwise use zSpan.
1849 static void generateColumnNames(
1850 Parse
*pParse
, /* Parser context */
1851 Select
*pSelect
/* Generate column names for this SELECT statement */
1853 Vdbe
*v
= pParse
->pVdbe
;
1858 sqlite3
*db
= pParse
->db
;
1859 int fullName
; /* TABLE.COLUMN if no AS clause and is a direct table ref */
1860 int srcName
; /* COLUMN or TABLE.COLUMN if no AS clause and is direct */
1862 #ifndef SQLITE_OMIT_EXPLAIN
1863 /* If this is an EXPLAIN, skip this step */
1864 if( pParse
->explain
){
1869 if( pParse
->colNamesSet
) return;
1870 /* Column names are determined by the left-most term of a compound select */
1871 while( pSelect
->pPrior
) pSelect
= pSelect
->pPrior
;
1872 SELECTTRACE(1,pParse
,pSelect
,("generating column names\n"));
1873 pTabList
= pSelect
->pSrc
;
1874 pEList
= pSelect
->pEList
;
1876 assert( pTabList
!=0 );
1877 pParse
->colNamesSet
= 1;
1878 fullName
= (db
->flags
& SQLITE_FullColNames
)!=0;
1879 srcName
= (db
->flags
& SQLITE_ShortColNames
)!=0 || fullName
;
1880 sqlite3VdbeSetNumCols(v
, pEList
->nExpr
);
1881 for(i
=0; i
<pEList
->nExpr
; i
++){
1882 Expr
*p
= pEList
->a
[i
].pExpr
;
1885 assert( p
->op
!=TK_AGG_COLUMN
); /* Agg processing has not run yet */
1886 assert( p
->op
!=TK_COLUMN
|| p
->pTab
!=0 ); /* Covering idx not yet coded */
1887 if( pEList
->a
[i
].zName
){
1888 /* An AS clause always takes first priority */
1889 char *zName
= pEList
->a
[i
].zName
;
1890 sqlite3VdbeSetColName(v
, i
, COLNAME_NAME
, zName
, SQLITE_TRANSIENT
);
1891 }else if( srcName
&& p
->op
==TK_COLUMN
){
1893 int iCol
= p
->iColumn
;
1896 if( iCol
<0 ) iCol
= pTab
->iPKey
;
1897 assert( iCol
==-1 || (iCol
>=0 && iCol
<pTab
->nCol
) );
1901 zCol
= pTab
->aCol
[iCol
].zName
;
1905 zName
= sqlite3MPrintf(db
, "%s.%s", pTab
->zName
, zCol
);
1906 sqlite3VdbeSetColName(v
, i
, COLNAME_NAME
, zName
, SQLITE_DYNAMIC
);
1908 sqlite3VdbeSetColName(v
, i
, COLNAME_NAME
, zCol
, SQLITE_TRANSIENT
);
1911 const char *z
= pEList
->a
[i
].zSpan
;
1912 z
= z
==0 ? sqlite3MPrintf(db
, "column%d", i
+1) : sqlite3DbStrDup(db
, z
);
1913 sqlite3VdbeSetColName(v
, i
, COLNAME_NAME
, z
, SQLITE_DYNAMIC
);
1916 generateColumnTypes(pParse
, pTabList
, pEList
);
1920 ** Given an expression list (which is really the list of expressions
1921 ** that form the result set of a SELECT statement) compute appropriate
1922 ** column names for a table that would hold the expression list.
1924 ** All column names will be unique.
1926 ** Only the column names are computed. Column.zType, Column.zColl,
1927 ** and other fields of Column are zeroed.
1929 ** Return SQLITE_OK on success. If a memory allocation error occurs,
1930 ** store NULL in *paCol and 0 in *pnCol and return SQLITE_NOMEM.
1932 ** The only guarantee that SQLite makes about column names is that if the
1933 ** column has an AS clause assigning it a name, that will be the name used.
1934 ** That is the only documented guarantee. However, countless applications
1935 ** developed over the years have made baseless assumptions about column names
1936 ** and will break if those assumptions changes. Hence, use extreme caution
1937 ** when modifying this routine to avoid breaking legacy.
1939 ** See Also: generateColumnNames()
1941 int sqlite3ColumnsFromExprList(
1942 Parse
*pParse
, /* Parsing context */
1943 ExprList
*pEList
, /* Expr list from which to derive column names */
1944 i16
*pnCol
, /* Write the number of columns here */
1945 Column
**paCol
/* Write the new column list here */
1947 sqlite3
*db
= pParse
->db
; /* Database connection */
1948 int i
, j
; /* Loop counters */
1949 u32 cnt
; /* Index added to make the name unique */
1950 Column
*aCol
, *pCol
; /* For looping over result columns */
1951 int nCol
; /* Number of columns in the result set */
1952 char *zName
; /* Column name */
1953 int nName
; /* Size of name in zName[] */
1954 Hash ht
; /* Hash table of column names */
1956 sqlite3HashInit(&ht
);
1958 nCol
= pEList
->nExpr
;
1959 aCol
= sqlite3DbMallocZero(db
, sizeof(aCol
[0])*nCol
);
1960 testcase( aCol
==0 );
1961 if( nCol
>32767 ) nCol
= 32767;
1966 assert( nCol
==(i16
)nCol
);
1970 for(i
=0, pCol
=aCol
; i
<nCol
&& !db
->mallocFailed
; i
++, pCol
++){
1971 /* Get an appropriate name for the column
1973 if( (zName
= pEList
->a
[i
].zName
)!=0 ){
1974 /* If the column contains an "AS <name>" phrase, use <name> as the name */
1976 Expr
*pColExpr
= sqlite3ExprSkipCollate(pEList
->a
[i
].pExpr
);
1977 while( pColExpr
->op
==TK_DOT
){
1978 pColExpr
= pColExpr
->pRight
;
1979 assert( pColExpr
!=0 );
1981 assert( pColExpr
->op
!=TK_AGG_COLUMN
);
1982 if( pColExpr
->op
==TK_COLUMN
){
1983 /* For columns use the column name name */
1984 int iCol
= pColExpr
->iColumn
;
1985 Table
*pTab
= pColExpr
->pTab
;
1987 if( iCol
<0 ) iCol
= pTab
->iPKey
;
1988 zName
= iCol
>=0 ? pTab
->aCol
[iCol
].zName
: "rowid";
1989 }else if( pColExpr
->op
==TK_ID
){
1990 assert( !ExprHasProperty(pColExpr
, EP_IntValue
) );
1991 zName
= pColExpr
->u
.zToken
;
1993 /* Use the original text of the column expression as its name */
1994 zName
= pEList
->a
[i
].zSpan
;
1998 zName
= sqlite3DbStrDup(db
, zName
);
2000 zName
= sqlite3MPrintf(db
,"column%d",i
+1);
2003 /* Make sure the column name is unique. If the name is not unique,
2004 ** append an integer to the name so that it becomes unique.
2007 while( zName
&& sqlite3HashFind(&ht
, zName
)!=0 ){
2008 nName
= sqlite3Strlen30(zName
);
2010 for(j
=nName
-1; j
>0 && sqlite3Isdigit(zName
[j
]); j
--){}
2011 if( zName
[j
]==':' ) nName
= j
;
2013 zName
= sqlite3MPrintf(db
, "%.*z:%u", nName
, zName
, ++cnt
);
2014 if( cnt
>3 ) sqlite3_randomness(sizeof(cnt
), &cnt
);
2016 pCol
->zName
= zName
;
2017 sqlite3ColumnPropertiesFromName(0, pCol
);
2018 if( zName
&& sqlite3HashInsert(&ht
, zName
, pCol
)==pCol
){
2019 sqlite3OomFault(db
);
2022 sqlite3HashClear(&ht
);
2023 if( db
->mallocFailed
){
2025 sqlite3DbFree(db
, aCol
[j
].zName
);
2027 sqlite3DbFree(db
, aCol
);
2030 return SQLITE_NOMEM_BKPT
;
2036 ** Add type and collation information to a column list based on
2037 ** a SELECT statement.
2039 ** The column list presumably came from selectColumnNamesFromExprList().
2040 ** The column list has only names, not types or collations. This
2041 ** routine goes through and adds the types and collations.
2043 ** This routine requires that all identifiers in the SELECT
2044 ** statement be resolved.
2046 void sqlite3SelectAddColumnTypeAndCollation(
2047 Parse
*pParse
, /* Parsing contexts */
2048 Table
*pTab
, /* Add column type information to this table */
2049 Select
*pSelect
/* SELECT used to determine types and collations */
2051 sqlite3
*db
= pParse
->db
;
2057 struct ExprList_item
*a
;
2059 assert( pSelect
!=0 );
2060 assert( (pSelect
->selFlags
& SF_Resolved
)!=0 );
2061 assert( pTab
->nCol
==pSelect
->pEList
->nExpr
|| db
->mallocFailed
);
2062 if( db
->mallocFailed
) return;
2063 memset(&sNC
, 0, sizeof(sNC
));
2064 sNC
.pSrcList
= pSelect
->pSrc
;
2065 a
= pSelect
->pEList
->a
;
2066 for(i
=0, pCol
=pTab
->aCol
; i
<pTab
->nCol
; i
++, pCol
++){
2070 zType
= columnType(&sNC
, p
, 0, 0, 0);
2071 /* pCol->szEst = ... // Column size est for SELECT tables never used */
2072 pCol
->affinity
= sqlite3ExprAffinity(p
);
2074 m
= sqlite3Strlen30(zType
);
2075 n
= sqlite3Strlen30(pCol
->zName
);
2076 pCol
->zName
= sqlite3DbReallocOrFree(db
, pCol
->zName
, n
+m
+2);
2078 memcpy(&pCol
->zName
[n
+1], zType
, m
+1);
2079 pCol
->colFlags
|= COLFLAG_HASTYPE
;
2082 if( pCol
->affinity
==0 ) pCol
->affinity
= SQLITE_AFF_BLOB
;
2083 pColl
= sqlite3ExprCollSeq(pParse
, p
);
2084 if( pColl
&& pCol
->zColl
==0 ){
2085 pCol
->zColl
= sqlite3DbStrDup(db
, pColl
->zName
);
2088 pTab
->szTabRow
= 1; /* Any non-zero value works */
2092 ** Given a SELECT statement, generate a Table structure that describes
2093 ** the result set of that SELECT.
2095 Table
*sqlite3ResultSetOfSelect(Parse
*pParse
, Select
*pSelect
){
2097 sqlite3
*db
= pParse
->db
;
2100 savedFlags
= db
->flags
;
2101 db
->flags
&= ~SQLITE_FullColNames
;
2102 db
->flags
|= SQLITE_ShortColNames
;
2103 sqlite3SelectPrep(pParse
, pSelect
, 0);
2104 if( pParse
->nErr
) return 0;
2105 while( pSelect
->pPrior
) pSelect
= pSelect
->pPrior
;
2106 db
->flags
= savedFlags
;
2107 pTab
= sqlite3DbMallocZero(db
, sizeof(Table
) );
2111 /* The sqlite3ResultSetOfSelect() is only used n contexts where lookaside
2113 assert( db
->lookaside
.bDisable
);
2116 pTab
->nRowLogEst
= 200; assert( 200==sqlite3LogEst(1048576) );
2117 sqlite3ColumnsFromExprList(pParse
, pSelect
->pEList
, &pTab
->nCol
, &pTab
->aCol
);
2118 sqlite3SelectAddColumnTypeAndCollation(pParse
, pTab
, pSelect
);
2120 if( db
->mallocFailed
){
2121 sqlite3DeleteTable(db
, pTab
);
2128 ** Get a VDBE for the given parser context. Create a new one if necessary.
2129 ** If an error occurs, return NULL and leave a message in pParse.
2131 Vdbe
*sqlite3GetVdbe(Parse
*pParse
){
2132 if( pParse
->pVdbe
){
2133 return pParse
->pVdbe
;
2135 if( pParse
->pToplevel
==0
2136 && OptimizationEnabled(pParse
->db
,SQLITE_FactorOutConst
)
2138 pParse
->okConstFactor
= 1;
2140 return sqlite3VdbeCreate(pParse
);
2145 ** Compute the iLimit and iOffset fields of the SELECT based on the
2146 ** pLimit expressions. pLimit->pLeft and pLimit->pRight hold the expressions
2147 ** that appear in the original SQL statement after the LIMIT and OFFSET
2148 ** keywords. Or NULL if those keywords are omitted. iLimit and iOffset
2149 ** are the integer memory register numbers for counters used to compute
2150 ** the limit and offset. If there is no limit and/or offset, then
2151 ** iLimit and iOffset are negative.
2153 ** This routine changes the values of iLimit and iOffset only if
2154 ** a limit or offset is defined by pLimit->pLeft and pLimit->pRight. iLimit
2155 ** and iOffset should have been preset to appropriate default values (zero)
2156 ** prior to calling this routine.
2158 ** The iOffset register (if it exists) is initialized to the value
2159 ** of the OFFSET. The iLimit register is initialized to LIMIT. Register
2160 ** iOffset+1 is initialized to LIMIT+OFFSET.
2162 ** Only if pLimit->pLeft!=0 do the limit registers get
2163 ** redefined. The UNION ALL operator uses this property to force
2164 ** the reuse of the same limit and offset registers across multiple
2165 ** SELECT statements.
2167 static void computeLimitRegisters(Parse
*pParse
, Select
*p
, int iBreak
){
2172 Expr
*pLimit
= p
->pLimit
;
2174 if( p
->iLimit
) return;
2177 ** "LIMIT -1" always shows all rows. There is some
2178 ** controversy about what the correct behavior should be.
2179 ** The current implementation interprets "LIMIT 0" to mean
2182 sqlite3ExprCacheClear(pParse
);
2184 assert( pLimit
->op
==TK_LIMIT
);
2185 assert( pLimit
->pLeft
!=0 );
2186 p
->iLimit
= iLimit
= ++pParse
->nMem
;
2187 v
= sqlite3GetVdbe(pParse
);
2189 if( sqlite3ExprIsInteger(pLimit
->pLeft
, &n
) ){
2190 sqlite3VdbeAddOp2(v
, OP_Integer
, n
, iLimit
);
2191 VdbeComment((v
, "LIMIT counter"));
2193 sqlite3VdbeGoto(v
, iBreak
);
2194 }else if( n
>=0 && p
->nSelectRow
>sqlite3LogEst((u64
)n
) ){
2195 p
->nSelectRow
= sqlite3LogEst((u64
)n
);
2196 p
->selFlags
|= SF_FixedLimit
;
2199 sqlite3ExprCode(pParse
, pLimit
->pLeft
, iLimit
);
2200 sqlite3VdbeAddOp1(v
, OP_MustBeInt
, iLimit
); VdbeCoverage(v
);
2201 VdbeComment((v
, "LIMIT counter"));
2202 sqlite3VdbeAddOp2(v
, OP_IfNot
, iLimit
, iBreak
); VdbeCoverage(v
);
2204 if( pLimit
->pRight
){
2205 p
->iOffset
= iOffset
= ++pParse
->nMem
;
2206 pParse
->nMem
++; /* Allocate an extra register for limit+offset */
2207 sqlite3ExprCode(pParse
, pLimit
->pRight
, iOffset
);
2208 sqlite3VdbeAddOp1(v
, OP_MustBeInt
, iOffset
); VdbeCoverage(v
);
2209 VdbeComment((v
, "OFFSET counter"));
2210 sqlite3VdbeAddOp3(v
, OP_OffsetLimit
, iLimit
, iOffset
+1, iOffset
);
2211 VdbeComment((v
, "LIMIT+OFFSET"));
2216 #ifndef SQLITE_OMIT_COMPOUND_SELECT
2218 ** Return the appropriate collating sequence for the iCol-th column of
2219 ** the result set for the compound-select statement "p". Return NULL if
2220 ** the column has no default collating sequence.
2222 ** The collating sequence for the compound select is taken from the
2223 ** left-most term of the select that has a collating sequence.
2225 static CollSeq
*multiSelectCollSeq(Parse
*pParse
, Select
*p
, int iCol
){
2228 pRet
= multiSelectCollSeq(pParse
, p
->pPrior
, iCol
);
2233 /* iCol must be less than p->pEList->nExpr. Otherwise an error would
2234 ** have been thrown during name resolution and we would not have gotten
2236 if( pRet
==0 && ALWAYS(iCol
<p
->pEList
->nExpr
) ){
2237 pRet
= sqlite3ExprCollSeq(pParse
, p
->pEList
->a
[iCol
].pExpr
);
2243 ** The select statement passed as the second parameter is a compound SELECT
2244 ** with an ORDER BY clause. This function allocates and returns a KeyInfo
2245 ** structure suitable for implementing the ORDER BY.
2247 ** Space to hold the KeyInfo structure is obtained from malloc. The calling
2248 ** function is responsible for ensuring that this structure is eventually
2251 static KeyInfo
*multiSelectOrderByKeyInfo(Parse
*pParse
, Select
*p
, int nExtra
){
2252 ExprList
*pOrderBy
= p
->pOrderBy
;
2253 int nOrderBy
= p
->pOrderBy
->nExpr
;
2254 sqlite3
*db
= pParse
->db
;
2255 KeyInfo
*pRet
= sqlite3KeyInfoAlloc(db
, nOrderBy
+nExtra
, 1);
2258 for(i
=0; i
<nOrderBy
; i
++){
2259 struct ExprList_item
*pItem
= &pOrderBy
->a
[i
];
2260 Expr
*pTerm
= pItem
->pExpr
;
2263 if( pTerm
->flags
& EP_Collate
){
2264 pColl
= sqlite3ExprCollSeq(pParse
, pTerm
);
2266 pColl
= multiSelectCollSeq(pParse
, p
, pItem
->u
.x
.iOrderByCol
-1);
2267 if( pColl
==0 ) pColl
= db
->pDfltColl
;
2268 pOrderBy
->a
[i
].pExpr
=
2269 sqlite3ExprAddCollateString(pParse
, pTerm
, pColl
->zName
);
2271 assert( sqlite3KeyInfoIsWriteable(pRet
) );
2272 pRet
->aColl
[i
] = pColl
;
2273 pRet
->aSortOrder
[i
] = pOrderBy
->a
[i
].sortOrder
;
2280 #ifndef SQLITE_OMIT_CTE
2282 ** This routine generates VDBE code to compute the content of a WITH RECURSIVE
2283 ** query of the form:
2285 ** <recursive-table> AS (<setup-query> UNION [ALL] <recursive-query>)
2286 ** \___________/ \_______________/
2290 ** There is exactly one reference to the recursive-table in the FROM clause
2291 ** of recursive-query, marked with the SrcList->a[].fg.isRecursive flag.
2293 ** The setup-query runs once to generate an initial set of rows that go
2294 ** into a Queue table. Rows are extracted from the Queue table one by
2295 ** one. Each row extracted from Queue is output to pDest. Then the single
2296 ** extracted row (now in the iCurrent table) becomes the content of the
2297 ** recursive-table for a recursive-query run. The output of the recursive-query
2298 ** is added back into the Queue table. Then another row is extracted from Queue
2299 ** and the iteration continues until the Queue table is empty.
2301 ** If the compound query operator is UNION then no duplicate rows are ever
2302 ** inserted into the Queue table. The iDistinct table keeps a copy of all rows
2303 ** that have ever been inserted into Queue and causes duplicates to be
2304 ** discarded. If the operator is UNION ALL, then duplicates are allowed.
2306 ** If the query has an ORDER BY, then entries in the Queue table are kept in
2307 ** ORDER BY order and the first entry is extracted for each cycle. Without
2308 ** an ORDER BY, the Queue table is just a FIFO.
2310 ** If a LIMIT clause is provided, then the iteration stops after LIMIT rows
2311 ** have been output to pDest. A LIMIT of zero means to output no rows and a
2312 ** negative LIMIT means to output all rows. If there is also an OFFSET clause
2313 ** with a positive value, then the first OFFSET outputs are discarded rather
2314 ** than being sent to pDest. The LIMIT count does not begin until after OFFSET
2315 ** rows have been skipped.
2317 static void generateWithRecursiveQuery(
2318 Parse
*pParse
, /* Parsing context */
2319 Select
*p
, /* The recursive SELECT to be coded */
2320 SelectDest
*pDest
/* What to do with query results */
2322 SrcList
*pSrc
= p
->pSrc
; /* The FROM clause of the recursive query */
2323 int nCol
= p
->pEList
->nExpr
; /* Number of columns in the recursive table */
2324 Vdbe
*v
= pParse
->pVdbe
; /* The prepared statement under construction */
2325 Select
*pSetup
= p
->pPrior
; /* The setup query */
2326 int addrTop
; /* Top of the loop */
2327 int addrCont
, addrBreak
; /* CONTINUE and BREAK addresses */
2328 int iCurrent
= 0; /* The Current table */
2329 int regCurrent
; /* Register holding Current table */
2330 int iQueue
; /* The Queue table */
2331 int iDistinct
= 0; /* To ensure unique results if UNION */
2332 int eDest
= SRT_Fifo
; /* How to write to Queue */
2333 SelectDest destQueue
; /* SelectDest targetting the Queue table */
2334 int i
; /* Loop counter */
2335 int rc
; /* Result code */
2336 ExprList
*pOrderBy
; /* The ORDER BY clause */
2337 Expr
*pLimit
; /* Saved LIMIT and OFFSET */
2338 int regLimit
, regOffset
; /* Registers used by LIMIT and OFFSET */
2340 /* Obtain authorization to do a recursive query */
2341 if( sqlite3AuthCheck(pParse
, SQLITE_RECURSIVE
, 0, 0, 0) ) return;
2343 /* Process the LIMIT and OFFSET clauses, if they exist */
2344 addrBreak
= sqlite3VdbeMakeLabel(v
);
2345 p
->nSelectRow
= 320; /* 4 billion rows */
2346 computeLimitRegisters(pParse
, p
, addrBreak
);
2348 regLimit
= p
->iLimit
;
2349 regOffset
= p
->iOffset
;
2351 p
->iLimit
= p
->iOffset
= 0;
2352 pOrderBy
= p
->pOrderBy
;
2354 /* Locate the cursor number of the Current table */
2355 for(i
=0; ALWAYS(i
<pSrc
->nSrc
); i
++){
2356 if( pSrc
->a
[i
].fg
.isRecursive
){
2357 iCurrent
= pSrc
->a
[i
].iCursor
;
2362 /* Allocate cursors numbers for Queue and Distinct. The cursor number for
2363 ** the Distinct table must be exactly one greater than Queue in order
2364 ** for the SRT_DistFifo and SRT_DistQueue destinations to work. */
2365 iQueue
= pParse
->nTab
++;
2366 if( p
->op
==TK_UNION
){
2367 eDest
= pOrderBy
? SRT_DistQueue
: SRT_DistFifo
;
2368 iDistinct
= pParse
->nTab
++;
2370 eDest
= pOrderBy
? SRT_Queue
: SRT_Fifo
;
2372 sqlite3SelectDestInit(&destQueue
, eDest
, iQueue
);
2374 /* Allocate cursors for Current, Queue, and Distinct. */
2375 regCurrent
= ++pParse
->nMem
;
2376 sqlite3VdbeAddOp3(v
, OP_OpenPseudo
, iCurrent
, regCurrent
, nCol
);
2378 KeyInfo
*pKeyInfo
= multiSelectOrderByKeyInfo(pParse
, p
, 1);
2379 sqlite3VdbeAddOp4(v
, OP_OpenEphemeral
, iQueue
, pOrderBy
->nExpr
+2, 0,
2380 (char*)pKeyInfo
, P4_KEYINFO
);
2381 destQueue
.pOrderBy
= pOrderBy
;
2383 sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, iQueue
, nCol
);
2385 VdbeComment((v
, "Queue table"));
2387 p
->addrOpenEphm
[0] = sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, iDistinct
, 0);
2388 p
->selFlags
|= SF_UsesEphemeral
;
2391 /* Detach the ORDER BY clause from the compound SELECT */
2394 /* Store the results of the setup-query in Queue. */
2396 ExplainQueryPlan((pParse
, 1, "SETUP"));
2397 rc
= sqlite3Select(pParse
, pSetup
, &destQueue
);
2399 if( rc
) goto end_of_recursive_query
;
2401 /* Find the next row in the Queue and output that row */
2402 addrTop
= sqlite3VdbeAddOp2(v
, OP_Rewind
, iQueue
, addrBreak
); VdbeCoverage(v
);
2404 /* Transfer the next row in Queue over to Current */
2405 sqlite3VdbeAddOp1(v
, OP_NullRow
, iCurrent
); /* To reset column cache */
2407 sqlite3VdbeAddOp3(v
, OP_Column
, iQueue
, pOrderBy
->nExpr
+1, regCurrent
);
2409 sqlite3VdbeAddOp2(v
, OP_RowData
, iQueue
, regCurrent
);
2411 sqlite3VdbeAddOp1(v
, OP_Delete
, iQueue
);
2413 /* Output the single row in Current */
2414 addrCont
= sqlite3VdbeMakeLabel(v
);
2415 codeOffset(v
, regOffset
, addrCont
);
2416 selectInnerLoop(pParse
, p
, iCurrent
,
2417 0, 0, pDest
, addrCont
, addrBreak
);
2419 sqlite3VdbeAddOp2(v
, OP_DecrJumpZero
, regLimit
, addrBreak
);
2422 sqlite3VdbeResolveLabel(v
, addrCont
);
2424 /* Execute the recursive SELECT taking the single row in Current as
2425 ** the value for the recursive-table. Store the results in the Queue.
2427 if( p
->selFlags
& SF_Aggregate
){
2428 sqlite3ErrorMsg(pParse
, "recursive aggregate queries not supported");
2431 ExplainQueryPlan((pParse
, 1, "RECURSIVE STEP"));
2432 sqlite3Select(pParse
, p
, &destQueue
);
2433 assert( p
->pPrior
==0 );
2437 /* Keep running the loop until the Queue is empty */
2438 sqlite3VdbeGoto(v
, addrTop
);
2439 sqlite3VdbeResolveLabel(v
, addrBreak
);
2441 end_of_recursive_query
:
2442 sqlite3ExprListDelete(pParse
->db
, p
->pOrderBy
);
2443 p
->pOrderBy
= pOrderBy
;
2447 #endif /* SQLITE_OMIT_CTE */
2449 /* Forward references */
2450 static int multiSelectOrderBy(
2451 Parse
*pParse
, /* Parsing context */
2452 Select
*p
, /* The right-most of SELECTs to be coded */
2453 SelectDest
*pDest
/* What to do with query results */
2457 ** Handle the special case of a compound-select that originates from a
2458 ** VALUES clause. By handling this as a special case, we avoid deep
2459 ** recursion, and thus do not need to enforce the SQLITE_LIMIT_COMPOUND_SELECT
2460 ** on a VALUES clause.
2462 ** Because the Select object originates from a VALUES clause:
2463 ** (1) There is no LIMIT or OFFSET or else there is a LIMIT of exactly 1
2464 ** (2) All terms are UNION ALL
2465 ** (3) There is no ORDER BY clause
2467 ** The "LIMIT of exactly 1" case of condition (1) comes about when a VALUES
2468 ** clause occurs within scalar expression (ex: "SELECT (VALUES(1),(2),(3))").
2469 ** The sqlite3CodeSubselect will have added the LIMIT 1 clause in tht case.
2470 ** Since the limit is exactly 1, we only need to evalutes the left-most VALUES.
2472 static int multiSelectValues(
2473 Parse
*pParse
, /* Parsing context */
2474 Select
*p
, /* The right-most of SELECTs to be coded */
2475 SelectDest
*pDest
/* What to do with query results */
2479 int bShowAll
= p
->pLimit
==0;
2480 assert( p
->selFlags
& SF_MultiValue
);
2482 assert( p
->selFlags
& SF_Values
);
2483 assert( p
->op
==TK_ALL
|| (p
->op
==TK_SELECT
&& p
->pPrior
==0) );
2484 assert( p
->pNext
==0 || p
->pEList
->nExpr
==p
->pNext
->pEList
->nExpr
);
2485 if( p
->pPrior
==0 ) break;
2486 assert( p
->pPrior
->pNext
==p
);
2490 ExplainQueryPlan((pParse
, 0, "SCAN %d CONSTANT ROW%s", nRow
,
2491 nRow
==1 ? "" : "S"));
2493 selectInnerLoop(pParse
, p
, -1, 0, 0, pDest
, 1, 1);
2494 if( !bShowAll
) break;
2495 p
->nSelectRow
= nRow
;
2502 ** This routine is called to process a compound query form from
2503 ** two or more separate queries using UNION, UNION ALL, EXCEPT, or
2506 ** "p" points to the right-most of the two queries. the query on the
2507 ** left is p->pPrior. The left query could also be a compound query
2508 ** in which case this routine will be called recursively.
2510 ** The results of the total query are to be written into a destination
2511 ** of type eDest with parameter iParm.
2513 ** Example 1: Consider a three-way compound SQL statement.
2515 ** SELECT a FROM t1 UNION SELECT b FROM t2 UNION SELECT c FROM t3
2517 ** This statement is parsed up as follows:
2521 ** `-----> SELECT b FROM t2
2523 ** `------> SELECT a FROM t1
2525 ** The arrows in the diagram above represent the Select.pPrior pointer.
2526 ** So if this routine is called with p equal to the t3 query, then
2527 ** pPrior will be the t2 query. p->op will be TK_UNION in this case.
2529 ** Notice that because of the way SQLite parses compound SELECTs, the
2530 ** individual selects always group from left to right.
2532 static int multiSelect(
2533 Parse
*pParse
, /* Parsing context */
2534 Select
*p
, /* The right-most of SELECTs to be coded */
2535 SelectDest
*pDest
/* What to do with query results */
2537 int rc
= SQLITE_OK
; /* Success code from a subroutine */
2538 Select
*pPrior
; /* Another SELECT immediately to our left */
2539 Vdbe
*v
; /* Generate code to this VDBE */
2540 SelectDest dest
; /* Alternative data destination */
2541 Select
*pDelete
= 0; /* Chain of simple selects to delete */
2542 sqlite3
*db
; /* Database connection */
2544 /* Make sure there is no ORDER BY or LIMIT clause on prior SELECTs. Only
2545 ** the last (right-most) SELECT in the series may have an ORDER BY or LIMIT.
2547 assert( p
&& p
->pPrior
); /* Calling function guarantees this much */
2548 assert( (p
->selFlags
& SF_Recursive
)==0 || p
->op
==TK_ALL
|| p
->op
==TK_UNION
);
2552 if( pPrior
->pOrderBy
|| pPrior
->pLimit
){
2553 sqlite3ErrorMsg(pParse
,"%s clause should come after %s not before",
2554 pPrior
->pOrderBy
!=0 ? "ORDER BY" : "LIMIT", selectOpName(p
->op
));
2556 goto multi_select_end
;
2559 v
= sqlite3GetVdbe(pParse
);
2560 assert( v
!=0 ); /* The VDBE already created by calling function */
2562 /* Create the destination temporary table if necessary
2564 if( dest
.eDest
==SRT_EphemTab
){
2565 assert( p
->pEList
);
2566 sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, dest
.iSDParm
, p
->pEList
->nExpr
);
2567 dest
.eDest
= SRT_Table
;
2570 /* Special handling for a compound-select that originates as a VALUES clause.
2572 if( p
->selFlags
& SF_MultiValue
){
2573 rc
= multiSelectValues(pParse
, p
, &dest
);
2574 goto multi_select_end
;
2577 /* Make sure all SELECTs in the statement have the same number of elements
2578 ** in their result sets.
2580 assert( p
->pEList
&& pPrior
->pEList
);
2581 assert( p
->pEList
->nExpr
==pPrior
->pEList
->nExpr
);
2583 #ifndef SQLITE_OMIT_CTE
2584 if( p
->selFlags
& SF_Recursive
){
2585 generateWithRecursiveQuery(pParse
, p
, &dest
);
2589 /* Compound SELECTs that have an ORDER BY clause are handled separately.
2592 return multiSelectOrderBy(pParse
, p
, pDest
);
2595 #ifndef SQLITE_OMIT_EXPLAIN
2596 if( pPrior
->pPrior
==0 ){
2597 ExplainQueryPlan((pParse
, 1, "COMPOUND QUERY"));
2598 ExplainQueryPlan((pParse
, 1, "LEFT-MOST SUBQUERY"));
2602 /* Generate code for the left and right SELECT statements.
2608 assert( !pPrior
->pLimit
);
2609 pPrior
->iLimit
= p
->iLimit
;
2610 pPrior
->iOffset
= p
->iOffset
;
2611 pPrior
->pLimit
= p
->pLimit
;
2612 rc
= sqlite3Select(pParse
, pPrior
, &dest
);
2615 goto multi_select_end
;
2618 p
->iLimit
= pPrior
->iLimit
;
2619 p
->iOffset
= pPrior
->iOffset
;
2621 addr
= sqlite3VdbeAddOp1(v
, OP_IfNot
, p
->iLimit
); VdbeCoverage(v
);
2622 VdbeComment((v
, "Jump ahead if LIMIT reached"));
2624 sqlite3VdbeAddOp3(v
, OP_OffsetLimit
,
2625 p
->iLimit
, p
->iOffset
+1, p
->iOffset
);
2628 ExplainQueryPlan((pParse
, 1, "UNION ALL"));
2629 rc
= sqlite3Select(pParse
, p
, &dest
);
2630 testcase( rc
!=SQLITE_OK
);
2631 pDelete
= p
->pPrior
;
2633 p
->nSelectRow
= sqlite3LogEstAdd(p
->nSelectRow
, pPrior
->nSelectRow
);
2635 && sqlite3ExprIsInteger(pPrior
->pLimit
->pLeft
, &nLimit
)
2636 && nLimit
>0 && p
->nSelectRow
> sqlite3LogEst((u64
)nLimit
)
2638 p
->nSelectRow
= sqlite3LogEst((u64
)nLimit
);
2641 sqlite3VdbeJumpHere(v
, addr
);
2647 int unionTab
; /* Cursor number of the temp table holding result */
2648 u8 op
= 0; /* One of the SRT_ operations to apply to self */
2649 int priorOp
; /* The SRT_ operation to apply to prior selects */
2650 Expr
*pLimit
; /* Saved values of p->nLimit */
2652 SelectDest uniondest
;
2654 testcase( p
->op
==TK_EXCEPT
);
2655 testcase( p
->op
==TK_UNION
);
2656 priorOp
= SRT_Union
;
2657 if( dest
.eDest
==priorOp
){
2658 /* We can reuse a temporary table generated by a SELECT to our
2661 assert( p
->pLimit
==0 ); /* Not allowed on leftward elements */
2662 unionTab
= dest
.iSDParm
;
2664 /* We will need to create our own temporary table to hold the
2665 ** intermediate results.
2667 unionTab
= pParse
->nTab
++;
2668 assert( p
->pOrderBy
==0 );
2669 addr
= sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, unionTab
, 0);
2670 assert( p
->addrOpenEphm
[0] == -1 );
2671 p
->addrOpenEphm
[0] = addr
;
2672 findRightmost(p
)->selFlags
|= SF_UsesEphemeral
;
2673 assert( p
->pEList
);
2676 /* Code the SELECT statements to our left
2678 assert( !pPrior
->pOrderBy
);
2679 sqlite3SelectDestInit(&uniondest
, priorOp
, unionTab
);
2680 rc
= sqlite3Select(pParse
, pPrior
, &uniondest
);
2682 goto multi_select_end
;
2685 /* Code the current SELECT statement
2687 if( p
->op
==TK_EXCEPT
){
2690 assert( p
->op
==TK_UNION
);
2696 uniondest
.eDest
= op
;
2697 ExplainQueryPlan((pParse
, 1, "%s USING TEMP B-TREE",
2698 selectOpName(p
->op
)));
2699 rc
= sqlite3Select(pParse
, p
, &uniondest
);
2700 testcase( rc
!=SQLITE_OK
);
2701 /* Query flattening in sqlite3Select() might refill p->pOrderBy.
2702 ** Be sure to delete p->pOrderBy, therefore, to avoid a memory leak. */
2703 sqlite3ExprListDelete(db
, p
->pOrderBy
);
2704 pDelete
= p
->pPrior
;
2707 if( p
->op
==TK_UNION
){
2708 p
->nSelectRow
= sqlite3LogEstAdd(p
->nSelectRow
, pPrior
->nSelectRow
);
2710 sqlite3ExprDelete(db
, p
->pLimit
);
2715 /* Convert the data in the temporary table into whatever form
2716 ** it is that we currently need.
2718 assert( unionTab
==dest
.iSDParm
|| dest
.eDest
!=priorOp
);
2719 if( dest
.eDest
!=priorOp
){
2720 int iCont
, iBreak
, iStart
;
2721 assert( p
->pEList
);
2722 iBreak
= sqlite3VdbeMakeLabel(v
);
2723 iCont
= sqlite3VdbeMakeLabel(v
);
2724 computeLimitRegisters(pParse
, p
, iBreak
);
2725 sqlite3VdbeAddOp2(v
, OP_Rewind
, unionTab
, iBreak
); VdbeCoverage(v
);
2726 iStart
= sqlite3VdbeCurrentAddr(v
);
2727 selectInnerLoop(pParse
, p
, unionTab
,
2728 0, 0, &dest
, iCont
, iBreak
);
2729 sqlite3VdbeResolveLabel(v
, iCont
);
2730 sqlite3VdbeAddOp2(v
, OP_Next
, unionTab
, iStart
); VdbeCoverage(v
);
2731 sqlite3VdbeResolveLabel(v
, iBreak
);
2732 sqlite3VdbeAddOp2(v
, OP_Close
, unionTab
, 0);
2736 default: assert( p
->op
==TK_INTERSECT
); {
2738 int iCont
, iBreak
, iStart
;
2741 SelectDest intersectdest
;
2744 /* INTERSECT is different from the others since it requires
2745 ** two temporary tables. Hence it has its own case. Begin
2746 ** by allocating the tables we will need.
2748 tab1
= pParse
->nTab
++;
2749 tab2
= pParse
->nTab
++;
2750 assert( p
->pOrderBy
==0 );
2752 addr
= sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, tab1
, 0);
2753 assert( p
->addrOpenEphm
[0] == -1 );
2754 p
->addrOpenEphm
[0] = addr
;
2755 findRightmost(p
)->selFlags
|= SF_UsesEphemeral
;
2756 assert( p
->pEList
);
2758 /* Code the SELECTs to our left into temporary table "tab1".
2760 sqlite3SelectDestInit(&intersectdest
, SRT_Union
, tab1
);
2761 rc
= sqlite3Select(pParse
, pPrior
, &intersectdest
);
2763 goto multi_select_end
;
2766 /* Code the current SELECT into temporary table "tab2"
2768 addr
= sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, tab2
, 0);
2769 assert( p
->addrOpenEphm
[1] == -1 );
2770 p
->addrOpenEphm
[1] = addr
;
2774 intersectdest
.iSDParm
= tab2
;
2775 ExplainQueryPlan((pParse
, 1, "%s USING TEMP B-TREE",
2776 selectOpName(p
->op
)));
2777 rc
= sqlite3Select(pParse
, p
, &intersectdest
);
2778 testcase( rc
!=SQLITE_OK
);
2779 pDelete
= p
->pPrior
;
2781 if( p
->nSelectRow
>pPrior
->nSelectRow
){
2782 p
->nSelectRow
= pPrior
->nSelectRow
;
2784 sqlite3ExprDelete(db
, p
->pLimit
);
2787 /* Generate code to take the intersection of the two temporary
2790 assert( p
->pEList
);
2791 iBreak
= sqlite3VdbeMakeLabel(v
);
2792 iCont
= sqlite3VdbeMakeLabel(v
);
2793 computeLimitRegisters(pParse
, p
, iBreak
);
2794 sqlite3VdbeAddOp2(v
, OP_Rewind
, tab1
, iBreak
); VdbeCoverage(v
);
2795 r1
= sqlite3GetTempReg(pParse
);
2796 iStart
= sqlite3VdbeAddOp2(v
, OP_RowData
, tab1
, r1
);
2797 sqlite3VdbeAddOp4Int(v
, OP_NotFound
, tab2
, iCont
, r1
, 0);
2799 sqlite3ReleaseTempReg(pParse
, r1
);
2800 selectInnerLoop(pParse
, p
, tab1
,
2801 0, 0, &dest
, iCont
, iBreak
);
2802 sqlite3VdbeResolveLabel(v
, iCont
);
2803 sqlite3VdbeAddOp2(v
, OP_Next
, tab1
, iStart
); VdbeCoverage(v
);
2804 sqlite3VdbeResolveLabel(v
, iBreak
);
2805 sqlite3VdbeAddOp2(v
, OP_Close
, tab2
, 0);
2806 sqlite3VdbeAddOp2(v
, OP_Close
, tab1
, 0);
2811 #ifndef SQLITE_OMIT_EXPLAIN
2813 ExplainQueryPlanPop(pParse
);
2818 /* Compute collating sequences used by
2819 ** temporary tables needed to implement the compound select.
2820 ** Attach the KeyInfo structure to all temporary tables.
2822 ** This section is run by the right-most SELECT statement only.
2823 ** SELECT statements to the left always skip this part. The right-most
2824 ** SELECT might also skip this part if it has no ORDER BY clause and
2825 ** no temp tables are required.
2827 if( p
->selFlags
& SF_UsesEphemeral
){
2828 int i
; /* Loop counter */
2829 KeyInfo
*pKeyInfo
; /* Collating sequence for the result set */
2830 Select
*pLoop
; /* For looping through SELECT statements */
2831 CollSeq
**apColl
; /* For looping through pKeyInfo->aColl[] */
2832 int nCol
; /* Number of columns in result set */
2834 assert( p
->pNext
==0 );
2835 nCol
= p
->pEList
->nExpr
;
2836 pKeyInfo
= sqlite3KeyInfoAlloc(db
, nCol
, 1);
2838 rc
= SQLITE_NOMEM_BKPT
;
2839 goto multi_select_end
;
2841 for(i
=0, apColl
=pKeyInfo
->aColl
; i
<nCol
; i
++, apColl
++){
2842 *apColl
= multiSelectCollSeq(pParse
, p
, i
);
2844 *apColl
= db
->pDfltColl
;
2848 for(pLoop
=p
; pLoop
; pLoop
=pLoop
->pPrior
){
2850 int addr
= pLoop
->addrOpenEphm
[i
];
2852 /* If [0] is unused then [1] is also unused. So we can
2853 ** always safely abort as soon as the first unused slot is found */
2854 assert( pLoop
->addrOpenEphm
[1]<0 );
2857 sqlite3VdbeChangeP2(v
, addr
, nCol
);
2858 sqlite3VdbeChangeP4(v
, addr
, (char*)sqlite3KeyInfoRef(pKeyInfo
),
2860 pLoop
->addrOpenEphm
[i
] = -1;
2863 sqlite3KeyInfoUnref(pKeyInfo
);
2867 pDest
->iSdst
= dest
.iSdst
;
2868 pDest
->nSdst
= dest
.nSdst
;
2869 sqlite3SelectDelete(db
, pDelete
);
2872 #endif /* SQLITE_OMIT_COMPOUND_SELECT */
2875 ** Error message for when two or more terms of a compound select have different
2876 ** size result sets.
2878 void sqlite3SelectWrongNumTermsError(Parse
*pParse
, Select
*p
){
2879 if( p
->selFlags
& SF_Values
){
2880 sqlite3ErrorMsg(pParse
, "all VALUES must have the same number of terms");
2882 sqlite3ErrorMsg(pParse
, "SELECTs to the left and right of %s"
2883 " do not have the same number of result columns", selectOpName(p
->op
));
2888 ** Code an output subroutine for a coroutine implementation of a
2891 ** The data to be output is contained in pIn->iSdst. There are
2892 ** pIn->nSdst columns to be output. pDest is where the output should
2895 ** regReturn is the number of the register holding the subroutine
2898 ** If regPrev>0 then it is the first register in a vector that
2899 ** records the previous output. mem[regPrev] is a flag that is false
2900 ** if there has been no previous output. If regPrev>0 then code is
2901 ** generated to suppress duplicates. pKeyInfo is used for comparing
2904 ** If the LIMIT found in p->iLimit is reached, jump immediately to
2907 static int generateOutputSubroutine(
2908 Parse
*pParse
, /* Parsing context */
2909 Select
*p
, /* The SELECT statement */
2910 SelectDest
*pIn
, /* Coroutine supplying data */
2911 SelectDest
*pDest
, /* Where to send the data */
2912 int regReturn
, /* The return address register */
2913 int regPrev
, /* Previous result register. No uniqueness if 0 */
2914 KeyInfo
*pKeyInfo
, /* For comparing with previous entry */
2915 int iBreak
/* Jump here if we hit the LIMIT */
2917 Vdbe
*v
= pParse
->pVdbe
;
2921 addr
= sqlite3VdbeCurrentAddr(v
);
2922 iContinue
= sqlite3VdbeMakeLabel(v
);
2924 /* Suppress duplicates for UNION, EXCEPT, and INTERSECT
2928 addr1
= sqlite3VdbeAddOp1(v
, OP_IfNot
, regPrev
); VdbeCoverage(v
);
2929 addr2
= sqlite3VdbeAddOp4(v
, OP_Compare
, pIn
->iSdst
, regPrev
+1, pIn
->nSdst
,
2930 (char*)sqlite3KeyInfoRef(pKeyInfo
), P4_KEYINFO
);
2931 sqlite3VdbeAddOp3(v
, OP_Jump
, addr2
+2, iContinue
, addr2
+2); VdbeCoverage(v
);
2932 sqlite3VdbeJumpHere(v
, addr1
);
2933 sqlite3VdbeAddOp3(v
, OP_Copy
, pIn
->iSdst
, regPrev
+1, pIn
->nSdst
-1);
2934 sqlite3VdbeAddOp2(v
, OP_Integer
, 1, regPrev
);
2936 if( pParse
->db
->mallocFailed
) return 0;
2938 /* Suppress the first OFFSET entries if there is an OFFSET clause
2940 codeOffset(v
, p
->iOffset
, iContinue
);
2942 assert( pDest
->eDest
!=SRT_Exists
);
2943 assert( pDest
->eDest
!=SRT_Table
);
2944 switch( pDest
->eDest
){
2945 /* Store the result as data using a unique key.
2947 case SRT_EphemTab
: {
2948 int r1
= sqlite3GetTempReg(pParse
);
2949 int r2
= sqlite3GetTempReg(pParse
);
2950 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, pIn
->iSdst
, pIn
->nSdst
, r1
);
2951 sqlite3VdbeAddOp2(v
, OP_NewRowid
, pDest
->iSDParm
, r2
);
2952 sqlite3VdbeAddOp3(v
, OP_Insert
, pDest
->iSDParm
, r1
, r2
);
2953 sqlite3VdbeChangeP5(v
, OPFLAG_APPEND
);
2954 sqlite3ReleaseTempReg(pParse
, r2
);
2955 sqlite3ReleaseTempReg(pParse
, r1
);
2959 #ifndef SQLITE_OMIT_SUBQUERY
2960 /* If we are creating a set for an "expr IN (SELECT ...)".
2964 testcase( pIn
->nSdst
>1 );
2965 r1
= sqlite3GetTempReg(pParse
);
2966 sqlite3VdbeAddOp4(v
, OP_MakeRecord
, pIn
->iSdst
, pIn
->nSdst
,
2967 r1
, pDest
->zAffSdst
, pIn
->nSdst
);
2968 sqlite3ExprCacheAffinityChange(pParse
, pIn
->iSdst
, pIn
->nSdst
);
2969 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, pDest
->iSDParm
, r1
,
2970 pIn
->iSdst
, pIn
->nSdst
);
2971 sqlite3ReleaseTempReg(pParse
, r1
);
2975 /* If this is a scalar select that is part of an expression, then
2976 ** store the results in the appropriate memory cell and break out
2977 ** of the scan loop.
2980 assert( pIn
->nSdst
==1 || pParse
->nErr
>0 ); testcase( pIn
->nSdst
!=1 );
2981 sqlite3ExprCodeMove(pParse
, pIn
->iSdst
, pDest
->iSDParm
, 1);
2982 /* The LIMIT clause will jump out of the loop for us */
2985 #endif /* #ifndef SQLITE_OMIT_SUBQUERY */
2987 /* The results are stored in a sequence of registers
2988 ** starting at pDest->iSdst. Then the co-routine yields.
2990 case SRT_Coroutine
: {
2991 if( pDest
->iSdst
==0 ){
2992 pDest
->iSdst
= sqlite3GetTempRange(pParse
, pIn
->nSdst
);
2993 pDest
->nSdst
= pIn
->nSdst
;
2995 sqlite3ExprCodeMove(pParse
, pIn
->iSdst
, pDest
->iSdst
, pIn
->nSdst
);
2996 sqlite3VdbeAddOp1(v
, OP_Yield
, pDest
->iSDParm
);
3000 /* If none of the above, then the result destination must be
3001 ** SRT_Output. This routine is never called with any other
3002 ** destination other than the ones handled above or SRT_Output.
3004 ** For SRT_Output, results are stored in a sequence of registers.
3005 ** Then the OP_ResultRow opcode is used to cause sqlite3_step() to
3006 ** return the next row of result.
3009 assert( pDest
->eDest
==SRT_Output
);
3010 sqlite3VdbeAddOp2(v
, OP_ResultRow
, pIn
->iSdst
, pIn
->nSdst
);
3011 sqlite3ExprCacheAffinityChange(pParse
, pIn
->iSdst
, pIn
->nSdst
);
3016 /* Jump to the end of the loop if the LIMIT is reached.
3019 sqlite3VdbeAddOp2(v
, OP_DecrJumpZero
, p
->iLimit
, iBreak
); VdbeCoverage(v
);
3022 /* Generate the subroutine return
3024 sqlite3VdbeResolveLabel(v
, iContinue
);
3025 sqlite3VdbeAddOp1(v
, OP_Return
, regReturn
);
3031 ** Alternative compound select code generator for cases when there
3032 ** is an ORDER BY clause.
3034 ** We assume a query of the following form:
3036 ** <selectA> <operator> <selectB> ORDER BY <orderbylist>
3038 ** <operator> is one of UNION ALL, UNION, EXCEPT, or INTERSECT. The idea
3039 ** is to code both <selectA> and <selectB> with the ORDER BY clause as
3040 ** co-routines. Then run the co-routines in parallel and merge the results
3041 ** into the output. In addition to the two coroutines (called selectA and
3042 ** selectB) there are 7 subroutines:
3044 ** outA: Move the output of the selectA coroutine into the output
3045 ** of the compound query.
3047 ** outB: Move the output of the selectB coroutine into the output
3048 ** of the compound query. (Only generated for UNION and
3049 ** UNION ALL. EXCEPT and INSERTSECT never output a row that
3050 ** appears only in B.)
3052 ** AltB: Called when there is data from both coroutines and A<B.
3054 ** AeqB: Called when there is data from both coroutines and A==B.
3056 ** AgtB: Called when there is data from both coroutines and A>B.
3058 ** EofA: Called when data is exhausted from selectA.
3060 ** EofB: Called when data is exhausted from selectB.
3062 ** The implementation of the latter five subroutines depend on which
3063 ** <operator> is used:
3066 ** UNION ALL UNION EXCEPT INTERSECT
3067 ** ------------- ----------------- -------------- -----------------
3068 ** AltB: outA, nextA outA, nextA outA, nextA nextA
3070 ** AeqB: outA, nextA nextA nextA outA, nextA
3072 ** AgtB: outB, nextB outB, nextB nextB nextB
3074 ** EofA: outB, nextB outB, nextB halt halt
3076 ** EofB: outA, nextA outA, nextA outA, nextA halt
3078 ** In the AltB, AeqB, and AgtB subroutines, an EOF on A following nextA
3079 ** causes an immediate jump to EofA and an EOF on B following nextB causes
3080 ** an immediate jump to EofB. Within EofA and EofB, and EOF on entry or
3081 ** following nextX causes a jump to the end of the select processing.
3083 ** Duplicate removal in the UNION, EXCEPT, and INTERSECT cases is handled
3084 ** within the output subroutine. The regPrev register set holds the previously
3085 ** output value. A comparison is made against this value and the output
3086 ** is skipped if the next results would be the same as the previous.
3088 ** The implementation plan is to implement the two coroutines and seven
3089 ** subroutines first, then put the control logic at the bottom. Like this:
3092 ** coA: coroutine for left query (A)
3093 ** coB: coroutine for right query (B)
3094 ** outA: output one row of A
3095 ** outB: output one row of B (UNION and UNION ALL only)
3101 ** Init: initialize coroutine registers
3103 ** if eof(A) goto EofA
3105 ** if eof(B) goto EofB
3106 ** Cmpr: Compare A, B
3107 ** Jump AltB, AeqB, AgtB
3110 ** We call AltB, AeqB, AgtB, EofA, and EofB "subroutines" but they are not
3111 ** actually called using Gosub and they do not Return. EofA and EofB loop
3112 ** until all data is exhausted then jump to the "end" labe. AltB, AeqB,
3113 ** and AgtB jump to either L2 or to one of EofA or EofB.
3115 #ifndef SQLITE_OMIT_COMPOUND_SELECT
3116 static int multiSelectOrderBy(
3117 Parse
*pParse
, /* Parsing context */
3118 Select
*p
, /* The right-most of SELECTs to be coded */
3119 SelectDest
*pDest
/* What to do with query results */
3121 int i
, j
; /* Loop counters */
3122 Select
*pPrior
; /* Another SELECT immediately to our left */
3123 Vdbe
*v
; /* Generate code to this VDBE */
3124 SelectDest destA
; /* Destination for coroutine A */
3125 SelectDest destB
; /* Destination for coroutine B */
3126 int regAddrA
; /* Address register for select-A coroutine */
3127 int regAddrB
; /* Address register for select-B coroutine */
3128 int addrSelectA
; /* Address of the select-A coroutine */
3129 int addrSelectB
; /* Address of the select-B coroutine */
3130 int regOutA
; /* Address register for the output-A subroutine */
3131 int regOutB
; /* Address register for the output-B subroutine */
3132 int addrOutA
; /* Address of the output-A subroutine */
3133 int addrOutB
= 0; /* Address of the output-B subroutine */
3134 int addrEofA
; /* Address of the select-A-exhausted subroutine */
3135 int addrEofA_noB
; /* Alternate addrEofA if B is uninitialized */
3136 int addrEofB
; /* Address of the select-B-exhausted subroutine */
3137 int addrAltB
; /* Address of the A<B subroutine */
3138 int addrAeqB
; /* Address of the A==B subroutine */
3139 int addrAgtB
; /* Address of the A>B subroutine */
3140 int regLimitA
; /* Limit register for select-A */
3141 int regLimitB
; /* Limit register for select-A */
3142 int regPrev
; /* A range of registers to hold previous output */
3143 int savedLimit
; /* Saved value of p->iLimit */
3144 int savedOffset
; /* Saved value of p->iOffset */
3145 int labelCmpr
; /* Label for the start of the merge algorithm */
3146 int labelEnd
; /* Label for the end of the overall SELECT stmt */
3147 int addr1
; /* Jump instructions that get retargetted */
3148 int op
; /* One of TK_ALL, TK_UNION, TK_EXCEPT, TK_INTERSECT */
3149 KeyInfo
*pKeyDup
= 0; /* Comparison information for duplicate removal */
3150 KeyInfo
*pKeyMerge
; /* Comparison information for merging rows */
3151 sqlite3
*db
; /* Database connection */
3152 ExprList
*pOrderBy
; /* The ORDER BY clause */
3153 int nOrderBy
; /* Number of terms in the ORDER BY clause */
3154 int *aPermute
; /* Mapping from ORDER BY terms to result set columns */
3156 assert( p
->pOrderBy
!=0 );
3157 assert( pKeyDup
==0 ); /* "Managed" code needs this. Ticket #3382. */
3160 assert( v
!=0 ); /* Already thrown the error if VDBE alloc failed */
3161 labelEnd
= sqlite3VdbeMakeLabel(v
);
3162 labelCmpr
= sqlite3VdbeMakeLabel(v
);
3165 /* Patch up the ORDER BY clause
3169 assert( pPrior
->pOrderBy
==0 );
3170 pOrderBy
= p
->pOrderBy
;
3172 nOrderBy
= pOrderBy
->nExpr
;
3174 /* For operators other than UNION ALL we have to make sure that
3175 ** the ORDER BY clause covers every term of the result set. Add
3176 ** terms to the ORDER BY clause as necessary.
3179 for(i
=1; db
->mallocFailed
==0 && i
<=p
->pEList
->nExpr
; i
++){
3180 struct ExprList_item
*pItem
;
3181 for(j
=0, pItem
=pOrderBy
->a
; j
<nOrderBy
; j
++, pItem
++){
3182 assert( pItem
->u
.x
.iOrderByCol
>0 );
3183 if( pItem
->u
.x
.iOrderByCol
==i
) break;
3186 Expr
*pNew
= sqlite3Expr(db
, TK_INTEGER
, 0);
3187 if( pNew
==0 ) return SQLITE_NOMEM_BKPT
;
3188 pNew
->flags
|= EP_IntValue
;
3190 p
->pOrderBy
= pOrderBy
= sqlite3ExprListAppend(pParse
, pOrderBy
, pNew
);
3191 if( pOrderBy
) pOrderBy
->a
[nOrderBy
++].u
.x
.iOrderByCol
= (u16
)i
;
3196 /* Compute the comparison permutation and keyinfo that is used with
3197 ** the permutation used to determine if the next
3198 ** row of results comes from selectA or selectB. Also add explicit
3199 ** collations to the ORDER BY clause terms so that when the subqueries
3200 ** to the right and the left are evaluated, they use the correct
3203 aPermute
= sqlite3DbMallocRawNN(db
, sizeof(int)*(nOrderBy
+ 1));
3205 struct ExprList_item
*pItem
;
3206 aPermute
[0] = nOrderBy
;
3207 for(i
=1, pItem
=pOrderBy
->a
; i
<=nOrderBy
; i
++, pItem
++){
3208 assert( pItem
->u
.x
.iOrderByCol
>0 );
3209 assert( pItem
->u
.x
.iOrderByCol
<=p
->pEList
->nExpr
);
3210 aPermute
[i
] = pItem
->u
.x
.iOrderByCol
- 1;
3212 pKeyMerge
= multiSelectOrderByKeyInfo(pParse
, p
, 1);
3217 /* Reattach the ORDER BY clause to the query.
3219 p
->pOrderBy
= pOrderBy
;
3220 pPrior
->pOrderBy
= sqlite3ExprListDup(pParse
->db
, pOrderBy
, 0);
3222 /* Allocate a range of temporary registers and the KeyInfo needed
3223 ** for the logic that removes duplicate result rows when the
3224 ** operator is UNION, EXCEPT, or INTERSECT (but not UNION ALL).
3229 int nExpr
= p
->pEList
->nExpr
;
3230 assert( nOrderBy
>=nExpr
|| db
->mallocFailed
);
3231 regPrev
= pParse
->nMem
+1;
3232 pParse
->nMem
+= nExpr
+1;
3233 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, regPrev
);
3234 pKeyDup
= sqlite3KeyInfoAlloc(db
, nExpr
, 1);
3236 assert( sqlite3KeyInfoIsWriteable(pKeyDup
) );
3237 for(i
=0; i
<nExpr
; i
++){
3238 pKeyDup
->aColl
[i
] = multiSelectCollSeq(pParse
, p
, i
);
3239 pKeyDup
->aSortOrder
[i
] = 0;
3244 /* Separate the left and the right query from one another
3248 sqlite3ResolveOrderGroupBy(pParse
, p
, p
->pOrderBy
, "ORDER");
3249 if( pPrior
->pPrior
==0 ){
3250 sqlite3ResolveOrderGroupBy(pParse
, pPrior
, pPrior
->pOrderBy
, "ORDER");
3253 /* Compute the limit registers */
3254 computeLimitRegisters(pParse
, p
, labelEnd
);
3255 if( p
->iLimit
&& op
==TK_ALL
){
3256 regLimitA
= ++pParse
->nMem
;
3257 regLimitB
= ++pParse
->nMem
;
3258 sqlite3VdbeAddOp2(v
, OP_Copy
, p
->iOffset
? p
->iOffset
+1 : p
->iLimit
,
3260 sqlite3VdbeAddOp2(v
, OP_Copy
, regLimitA
, regLimitB
);
3262 regLimitA
= regLimitB
= 0;
3264 sqlite3ExprDelete(db
, p
->pLimit
);
3267 regAddrA
= ++pParse
->nMem
;
3268 regAddrB
= ++pParse
->nMem
;
3269 regOutA
= ++pParse
->nMem
;
3270 regOutB
= ++pParse
->nMem
;
3271 sqlite3SelectDestInit(&destA
, SRT_Coroutine
, regAddrA
);
3272 sqlite3SelectDestInit(&destB
, SRT_Coroutine
, regAddrB
);
3274 ExplainQueryPlan((pParse
, 1, "MERGE (%s)", selectOpName(p
->op
)));
3276 /* Generate a coroutine to evaluate the SELECT statement to the
3277 ** left of the compound operator - the "A" select.
3279 addrSelectA
= sqlite3VdbeCurrentAddr(v
) + 1;
3280 addr1
= sqlite3VdbeAddOp3(v
, OP_InitCoroutine
, regAddrA
, 0, addrSelectA
);
3281 VdbeComment((v
, "left SELECT"));
3282 pPrior
->iLimit
= regLimitA
;
3283 ExplainQueryPlan((pParse
, 1, "LEFT"));
3284 sqlite3Select(pParse
, pPrior
, &destA
);
3285 sqlite3VdbeEndCoroutine(v
, regAddrA
);
3286 sqlite3VdbeJumpHere(v
, addr1
);
3288 /* Generate a coroutine to evaluate the SELECT statement on
3289 ** the right - the "B" select
3291 addrSelectB
= sqlite3VdbeCurrentAddr(v
) + 1;
3292 addr1
= sqlite3VdbeAddOp3(v
, OP_InitCoroutine
, regAddrB
, 0, addrSelectB
);
3293 VdbeComment((v
, "right SELECT"));
3294 savedLimit
= p
->iLimit
;
3295 savedOffset
= p
->iOffset
;
3296 p
->iLimit
= regLimitB
;
3298 ExplainQueryPlan((pParse
, 1, "RIGHT"));
3299 sqlite3Select(pParse
, p
, &destB
);
3300 p
->iLimit
= savedLimit
;
3301 p
->iOffset
= savedOffset
;
3302 sqlite3VdbeEndCoroutine(v
, regAddrB
);
3304 /* Generate a subroutine that outputs the current row of the A
3305 ** select as the next output row of the compound select.
3307 VdbeNoopComment((v
, "Output routine for A"));
3308 addrOutA
= generateOutputSubroutine(pParse
,
3309 p
, &destA
, pDest
, regOutA
,
3310 regPrev
, pKeyDup
, labelEnd
);
3312 /* Generate a subroutine that outputs the current row of the B
3313 ** select as the next output row of the compound select.
3315 if( op
==TK_ALL
|| op
==TK_UNION
){
3316 VdbeNoopComment((v
, "Output routine for B"));
3317 addrOutB
= generateOutputSubroutine(pParse
,
3318 p
, &destB
, pDest
, regOutB
,
3319 regPrev
, pKeyDup
, labelEnd
);
3321 sqlite3KeyInfoUnref(pKeyDup
);
3323 /* Generate a subroutine to run when the results from select A
3324 ** are exhausted and only data in select B remains.
3326 if( op
==TK_EXCEPT
|| op
==TK_INTERSECT
){
3327 addrEofA_noB
= addrEofA
= labelEnd
;
3329 VdbeNoopComment((v
, "eof-A subroutine"));
3330 addrEofA
= sqlite3VdbeAddOp2(v
, OP_Gosub
, regOutB
, addrOutB
);
3331 addrEofA_noB
= sqlite3VdbeAddOp2(v
, OP_Yield
, regAddrB
, labelEnd
);
3333 sqlite3VdbeGoto(v
, addrEofA
);
3334 p
->nSelectRow
= sqlite3LogEstAdd(p
->nSelectRow
, pPrior
->nSelectRow
);
3337 /* Generate a subroutine to run when the results from select B
3338 ** are exhausted and only data in select A remains.
3340 if( op
==TK_INTERSECT
){
3341 addrEofB
= addrEofA
;
3342 if( p
->nSelectRow
> pPrior
->nSelectRow
) p
->nSelectRow
= pPrior
->nSelectRow
;
3344 VdbeNoopComment((v
, "eof-B subroutine"));
3345 addrEofB
= sqlite3VdbeAddOp2(v
, OP_Gosub
, regOutA
, addrOutA
);
3346 sqlite3VdbeAddOp2(v
, OP_Yield
, regAddrA
, labelEnd
); VdbeCoverage(v
);
3347 sqlite3VdbeGoto(v
, addrEofB
);
3350 /* Generate code to handle the case of A<B
3352 VdbeNoopComment((v
, "A-lt-B subroutine"));
3353 addrAltB
= sqlite3VdbeAddOp2(v
, OP_Gosub
, regOutA
, addrOutA
);
3354 sqlite3VdbeAddOp2(v
, OP_Yield
, regAddrA
, addrEofA
); VdbeCoverage(v
);
3355 sqlite3VdbeGoto(v
, labelCmpr
);
3357 /* Generate code to handle the case of A==B
3360 addrAeqB
= addrAltB
;
3361 }else if( op
==TK_INTERSECT
){
3362 addrAeqB
= addrAltB
;
3365 VdbeNoopComment((v
, "A-eq-B subroutine"));
3367 sqlite3VdbeAddOp2(v
, OP_Yield
, regAddrA
, addrEofA
); VdbeCoverage(v
);
3368 sqlite3VdbeGoto(v
, labelCmpr
);
3371 /* Generate code to handle the case of A>B
3373 VdbeNoopComment((v
, "A-gt-B subroutine"));
3374 addrAgtB
= sqlite3VdbeCurrentAddr(v
);
3375 if( op
==TK_ALL
|| op
==TK_UNION
){
3376 sqlite3VdbeAddOp2(v
, OP_Gosub
, regOutB
, addrOutB
);
3378 sqlite3VdbeAddOp2(v
, OP_Yield
, regAddrB
, addrEofB
); VdbeCoverage(v
);
3379 sqlite3VdbeGoto(v
, labelCmpr
);
3381 /* This code runs once to initialize everything.
3383 sqlite3VdbeJumpHere(v
, addr1
);
3384 sqlite3VdbeAddOp2(v
, OP_Yield
, regAddrA
, addrEofA_noB
); VdbeCoverage(v
);
3385 sqlite3VdbeAddOp2(v
, OP_Yield
, regAddrB
, addrEofB
); VdbeCoverage(v
);
3387 /* Implement the main merge loop
3389 sqlite3VdbeResolveLabel(v
, labelCmpr
);
3390 sqlite3VdbeAddOp4(v
, OP_Permutation
, 0, 0, 0, (char*)aPermute
, P4_INTARRAY
);
3391 sqlite3VdbeAddOp4(v
, OP_Compare
, destA
.iSdst
, destB
.iSdst
, nOrderBy
,
3392 (char*)pKeyMerge
, P4_KEYINFO
);
3393 sqlite3VdbeChangeP5(v
, OPFLAG_PERMUTE
);
3394 sqlite3VdbeAddOp3(v
, OP_Jump
, addrAltB
, addrAeqB
, addrAgtB
); VdbeCoverage(v
);
3396 /* Jump to the this point in order to terminate the query.
3398 sqlite3VdbeResolveLabel(v
, labelEnd
);
3400 /* Reassembly the compound query so that it will be freed correctly
3401 ** by the calling function */
3403 sqlite3SelectDelete(db
, p
->pPrior
);
3408 /*** TBD: Insert subroutine calls to close cursors on incomplete
3409 **** subqueries ****/
3410 ExplainQueryPlanPop(pParse
);
3411 return pParse
->nErr
!=0;
3415 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3417 /* An instance of the SubstContext object describes an substitution edit
3418 ** to be performed on a parse tree.
3420 ** All references to columns in table iTable are to be replaced by corresponding
3421 ** expressions in pEList.
3423 typedef struct SubstContext
{
3424 Parse
*pParse
; /* The parsing context */
3425 int iTable
; /* Replace references to this table */
3426 int iNewTable
; /* New table number */
3427 int isLeftJoin
; /* Add TK_IF_NULL_ROW opcodes on each replacement */
3428 ExprList
*pEList
; /* Replacement expressions */
3431 /* Forward Declarations */
3432 static void substExprList(SubstContext
*, ExprList
*);
3433 static void substSelect(SubstContext
*, Select
*, int);
3436 ** Scan through the expression pExpr. Replace every reference to
3437 ** a column in table number iTable with a copy of the iColumn-th
3438 ** entry in pEList. (But leave references to the ROWID column
3441 ** This routine is part of the flattening procedure. A subquery
3442 ** whose result set is defined by pEList appears as entry in the
3443 ** FROM clause of a SELECT such that the VDBE cursor assigned to that
3444 ** FORM clause entry is iTable. This routine makes the necessary
3445 ** changes to pExpr so that it refers directly to the source table
3446 ** of the subquery rather the result set of the subquery.
3448 static Expr
*substExpr(
3449 SubstContext
*pSubst
, /* Description of the substitution */
3450 Expr
*pExpr
/* Expr in which substitution occurs */
3452 if( pExpr
==0 ) return 0;
3453 if( ExprHasProperty(pExpr
, EP_FromJoin
)
3454 && pExpr
->iRightJoinTable
==pSubst
->iTable
3456 pExpr
->iRightJoinTable
= pSubst
->iNewTable
;
3458 if( pExpr
->op
==TK_COLUMN
&& pExpr
->iTable
==pSubst
->iTable
){
3459 if( pExpr
->iColumn
<0 ){
3460 pExpr
->op
= TK_NULL
;
3463 Expr
*pCopy
= pSubst
->pEList
->a
[pExpr
->iColumn
].pExpr
;
3465 assert( pSubst
->pEList
!=0 && pExpr
->iColumn
<pSubst
->pEList
->nExpr
);
3466 assert( pExpr
->pLeft
==0 && pExpr
->pRight
==0 );
3467 if( sqlite3ExprIsVector(pCopy
) ){
3468 sqlite3VectorErrorMsg(pSubst
->pParse
, pCopy
);
3470 sqlite3
*db
= pSubst
->pParse
->db
;
3471 if( pSubst
->isLeftJoin
&& pCopy
->op
!=TK_COLUMN
){
3472 memset(&ifNullRow
, 0, sizeof(ifNullRow
));
3473 ifNullRow
.op
= TK_IF_NULL_ROW
;
3474 ifNullRow
.pLeft
= pCopy
;
3475 ifNullRow
.iTable
= pSubst
->iNewTable
;
3478 pNew
= sqlite3ExprDup(db
, pCopy
, 0);
3479 if( pNew
&& pSubst
->isLeftJoin
){
3480 ExprSetProperty(pNew
, EP_CanBeNull
);
3482 if( pNew
&& ExprHasProperty(pExpr
,EP_FromJoin
) ){
3483 pNew
->iRightJoinTable
= pExpr
->iRightJoinTable
;
3484 ExprSetProperty(pNew
, EP_FromJoin
);
3486 sqlite3ExprDelete(db
, pExpr
);
3491 if( pExpr
->op
==TK_IF_NULL_ROW
&& pExpr
->iTable
==pSubst
->iTable
){
3492 pExpr
->iTable
= pSubst
->iNewTable
;
3494 pExpr
->pLeft
= substExpr(pSubst
, pExpr
->pLeft
);
3495 pExpr
->pRight
= substExpr(pSubst
, pExpr
->pRight
);
3496 if( ExprHasProperty(pExpr
, EP_xIsSelect
) ){
3497 substSelect(pSubst
, pExpr
->x
.pSelect
, 1);
3499 substExprList(pSubst
, pExpr
->x
.pList
);
3504 static void substExprList(
3505 SubstContext
*pSubst
, /* Description of the substitution */
3506 ExprList
*pList
/* List to scan and in which to make substitutes */
3509 if( pList
==0 ) return;
3510 for(i
=0; i
<pList
->nExpr
; i
++){
3511 pList
->a
[i
].pExpr
= substExpr(pSubst
, pList
->a
[i
].pExpr
);
3514 static void substSelect(
3515 SubstContext
*pSubst
, /* Description of the substitution */
3516 Select
*p
, /* SELECT statement in which to make substitutions */
3517 int doPrior
/* Do substitutes on p->pPrior too */
3520 struct SrcList_item
*pItem
;
3524 substExprList(pSubst
, p
->pEList
);
3525 substExprList(pSubst
, p
->pGroupBy
);
3526 substExprList(pSubst
, p
->pOrderBy
);
3527 p
->pHaving
= substExpr(pSubst
, p
->pHaving
);
3528 p
->pWhere
= substExpr(pSubst
, p
->pWhere
);
3531 for(i
=pSrc
->nSrc
, pItem
=pSrc
->a
; i
>0; i
--, pItem
++){
3532 substSelect(pSubst
, pItem
->pSelect
, 1);
3533 if( pItem
->fg
.isTabFunc
){
3534 substExprList(pSubst
, pItem
->u1
.pFuncArg
);
3537 }while( doPrior
&& (p
= p
->pPrior
)!=0 );
3539 #endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */
3541 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3543 ** This routine attempts to flatten subqueries as a performance optimization.
3544 ** This routine returns 1 if it makes changes and 0 if no flattening occurs.
3546 ** To understand the concept of flattening, consider the following
3549 ** SELECT a FROM (SELECT x+y AS a FROM t1 WHERE z<100) WHERE a>5
3551 ** The default way of implementing this query is to execute the
3552 ** subquery first and store the results in a temporary table, then
3553 ** run the outer query on that temporary table. This requires two
3554 ** passes over the data. Furthermore, because the temporary table
3555 ** has no indices, the WHERE clause on the outer query cannot be
3558 ** This routine attempts to rewrite queries such as the above into
3559 ** a single flat select, like this:
3561 ** SELECT x+y AS a FROM t1 WHERE z<100 AND a>5
3563 ** The code generated for this simplification gives the same result
3564 ** but only has to scan the data once. And because indices might
3565 ** exist on the table t1, a complete scan of the data might be
3568 ** Flattening is subject to the following constraints:
3570 ** (**) We no longer attempt to flatten aggregate subqueries. Was:
3571 ** The subquery and the outer query cannot both be aggregates.
3573 ** (**) We no longer attempt to flatten aggregate subqueries. Was:
3574 ** (2) If the subquery is an aggregate then
3575 ** (2a) the outer query must not be a join and
3576 ** (2b) the outer query must not use subqueries
3577 ** other than the one FROM-clause subquery that is a candidate
3578 ** for flattening. (This is due to ticket [2f7170d73bf9abf80]
3579 ** from 2015-02-09.)
3581 ** (3) If the subquery is the right operand of a LEFT JOIN then
3582 ** (3a) the subquery may not be a join and
3583 ** (3b) the FROM clause of the subquery may not contain a virtual
3585 ** (3c) the outer query may not be an aggregate.
3587 ** (4) The subquery can not be DISTINCT.
3589 ** (**) At one point restrictions (4) and (5) defined a subset of DISTINCT
3590 ** sub-queries that were excluded from this optimization. Restriction
3591 ** (4) has since been expanded to exclude all DISTINCT subqueries.
3593 ** (**) We no longer attempt to flatten aggregate subqueries. Was:
3594 ** If the subquery is aggregate, the outer query may not be DISTINCT.
3596 ** (7) The subquery must have a FROM clause. TODO: For subqueries without
3597 ** A FROM clause, consider adding a FROM clause with the special
3598 ** table sqlite_once that consists of a single row containing a
3601 ** (8) If the subquery uses LIMIT then the outer query may not be a join.
3603 ** (9) If the subquery uses LIMIT then the outer query may not be aggregate.
3605 ** (**) Restriction (10) was removed from the code on 2005-02-05 but we
3606 ** accidently carried the comment forward until 2014-09-15. Original
3607 ** constraint: "If the subquery is aggregate then the outer query
3608 ** may not use LIMIT."
3610 ** (11) The subquery and the outer query may not both have ORDER BY clauses.
3612 ** (**) Not implemented. Subsumed into restriction (3). Was previously
3613 ** a separate restriction deriving from ticket #350.
3615 ** (13) The subquery and outer query may not both use LIMIT.
3617 ** (14) The subquery may not use OFFSET.
3619 ** (15) If the outer query is part of a compound select, then the
3620 ** subquery may not use LIMIT.
3621 ** (See ticket #2339 and ticket [02a8e81d44]).
3623 ** (16) If the outer query is aggregate, then the subquery may not
3624 ** use ORDER BY. (Ticket #2942) This used to not matter
3625 ** until we introduced the group_concat() function.
3627 ** (17) If the subquery is a compound select, then
3628 ** (17a) all compound operators must be a UNION ALL, and
3629 ** (17b) no terms within the subquery compound may be aggregate
3631 ** (17c) every term within the subquery compound must have a FROM clause
3632 ** (17d) the outer query may not be
3633 ** (17d1) aggregate, or
3634 ** (17d2) DISTINCT, or
3637 ** The parent and sub-query may contain WHERE clauses. Subject to
3638 ** rules (11), (13) and (14), they may also contain ORDER BY,
3639 ** LIMIT and OFFSET clauses. The subquery cannot use any compound
3640 ** operator other than UNION ALL because all the other compound
3641 ** operators have an implied DISTINCT which is disallowed by
3644 ** Also, each component of the sub-query must return the same number
3645 ** of result columns. This is actually a requirement for any compound
3646 ** SELECT statement, but all the code here does is make sure that no
3647 ** such (illegal) sub-query is flattened. The caller will detect the
3648 ** syntax error and return a detailed message.
3650 ** (18) If the sub-query is a compound select, then all terms of the
3651 ** ORDER BY clause of the parent must be simple references to
3652 ** columns of the sub-query.
3654 ** (19) If the subquery uses LIMIT then the outer query may not
3655 ** have a WHERE clause.
3657 ** (20) If the sub-query is a compound select, then it must not use
3658 ** an ORDER BY clause. Ticket #3773. We could relax this constraint
3659 ** somewhat by saying that the terms of the ORDER BY clause must
3660 ** appear as unmodified result columns in the outer query. But we
3661 ** have other optimizations in mind to deal with that case.
3663 ** (21) If the subquery uses LIMIT then the outer query may not be
3664 ** DISTINCT. (See ticket [752e1646fc]).
3666 ** (22) The subquery may not be a recursive CTE.
3668 ** (**) Subsumed into restriction (17d3). Was: If the outer query is
3669 ** a recursive CTE, then the sub-query may not be a compound query.
3670 ** This restriction is because transforming the
3671 ** parent to a compound query confuses the code that handles
3672 ** recursive queries in multiSelect().
3674 ** (**) We no longer attempt to flatten aggregate subqueries. Was:
3675 ** The subquery may not be an aggregate that uses the built-in min() or
3676 ** or max() functions. (Without this restriction, a query like:
3677 ** "SELECT x FROM (SELECT max(y), x FROM t1)" would not necessarily
3678 ** return the value X for which Y was maximal.)
3680 ** (25) If either the subquery or the parent query contains a window
3681 ** function in the select list or ORDER BY clause, flattening
3682 ** is not attempted.
3685 ** In this routine, the "p" parameter is a pointer to the outer query.
3686 ** The subquery is p->pSrc->a[iFrom]. isAgg is true if the outer query
3689 ** If flattening is not attempted, this routine is a no-op and returns 0.
3690 ** If flattening is attempted this routine returns 1.
3692 ** All of the expression analysis must occur on both the outer query and
3693 ** the subquery before this routine runs.
3695 static int flattenSubquery(
3696 Parse
*pParse
, /* Parsing context */
3697 Select
*p
, /* The parent or outer SELECT statement */
3698 int iFrom
, /* Index in p->pSrc->a[] of the inner subquery */
3699 int isAgg
/* True if outer SELECT uses aggregate functions */
3701 const char *zSavedAuthContext
= pParse
->zAuthContext
;
3702 Select
*pParent
; /* Current UNION ALL term of the other query */
3703 Select
*pSub
; /* The inner query or "subquery" */
3704 Select
*pSub1
; /* Pointer to the rightmost select in sub-query */
3705 SrcList
*pSrc
; /* The FROM clause of the outer query */
3706 SrcList
*pSubSrc
; /* The FROM clause of the subquery */
3707 int iParent
; /* VDBE cursor number of the pSub result set temp table */
3708 int iNewParent
= -1;/* Replacement table for iParent */
3709 int isLeftJoin
= 0; /* True if pSub is the right side of a LEFT JOIN */
3710 int i
; /* Loop counter */
3711 Expr
*pWhere
; /* The WHERE clause */
3712 struct SrcList_item
*pSubitem
; /* The subquery */
3713 sqlite3
*db
= pParse
->db
;
3715 /* Check to see if flattening is permitted. Return 0 if not.
3718 assert( p
->pPrior
==0 );
3719 if( OptimizationDisabled(db
, SQLITE_QueryFlattener
) ) return 0;
3721 assert( pSrc
&& iFrom
>=0 && iFrom
<pSrc
->nSrc
);
3722 pSubitem
= &pSrc
->a
[iFrom
];
3723 iParent
= pSubitem
->iCursor
;
3724 pSub
= pSubitem
->pSelect
;
3727 #ifndef SQLITE_OMIT_WINDOWFUNC
3728 if( p
->pWin
|| pSub
->pWin
) return 0; /* Restriction (25) */
3731 pSubSrc
= pSub
->pSrc
;
3733 /* Prior to version 3.1.2, when LIMIT and OFFSET had to be simple constants,
3734 ** not arbitrary expressions, we allowed some combining of LIMIT and OFFSET
3735 ** because they could be computed at compile-time. But when LIMIT and OFFSET
3736 ** became arbitrary expressions, we were forced to add restrictions (13)
3738 if( pSub
->pLimit
&& p
->pLimit
) return 0; /* Restriction (13) */
3739 if( pSub
->pLimit
&& pSub
->pLimit
->pRight
) return 0; /* Restriction (14) */
3740 if( (p
->selFlags
& SF_Compound
)!=0 && pSub
->pLimit
){
3741 return 0; /* Restriction (15) */
3743 if( pSubSrc
->nSrc
==0 ) return 0; /* Restriction (7) */
3744 if( pSub
->selFlags
& SF_Distinct
) return 0; /* Restriction (4) */
3745 if( pSub
->pLimit
&& (pSrc
->nSrc
>1 || isAgg
) ){
3746 return 0; /* Restrictions (8)(9) */
3748 if( p
->pOrderBy
&& pSub
->pOrderBy
){
3749 return 0; /* Restriction (11) */
3751 if( isAgg
&& pSub
->pOrderBy
) return 0; /* Restriction (16) */
3752 if( pSub
->pLimit
&& p
->pWhere
) return 0; /* Restriction (19) */
3753 if( pSub
->pLimit
&& (p
->selFlags
& SF_Distinct
)!=0 ){
3754 return 0; /* Restriction (21) */
3756 if( pSub
->selFlags
& (SF_Recursive
) ){
3757 return 0; /* Restrictions (22) */
3761 ** If the subquery is the right operand of a LEFT JOIN, then the
3762 ** subquery may not be a join itself (3a). Example of why this is not
3765 ** t1 LEFT OUTER JOIN (t2 JOIN t3)
3767 ** If we flatten the above, we would get
3769 ** (t1 LEFT OUTER JOIN t2) JOIN t3
3771 ** which is not at all the same thing.
3773 ** If the subquery is the right operand of a LEFT JOIN, then the outer
3774 ** query cannot be an aggregate. (3c) This is an artifact of the way
3775 ** aggregates are processed - there is no mechanism to determine if
3776 ** the LEFT JOIN table should be all-NULL.
3778 ** See also tickets #306, #350, and #3300.
3780 if( (pSubitem
->fg
.jointype
& JT_OUTER
)!=0 ){
3782 if( pSubSrc
->nSrc
>1 || isAgg
|| IsVirtual(pSubSrc
->a
[0].pTab
) ){
3783 /* (3a) (3c) (3b) */
3787 #ifdef SQLITE_EXTRA_IFNULLROW
3788 else if( iFrom
>0 && !isAgg
){
3789 /* Setting isLeftJoin to -1 causes OP_IfNullRow opcodes to be generated for
3790 ** every reference to any result column from subquery in a join, even
3791 ** though they are not necessary. This will stress-test the OP_IfNullRow
3797 /* Restriction (17): If the sub-query is a compound SELECT, then it must
3798 ** use only the UNION ALL operator. And none of the simple select queries
3799 ** that make up the compound SELECT are allowed to be aggregate or distinct
3803 if( pSub
->pOrderBy
){
3804 return 0; /* Restriction (20) */
3806 if( isAgg
|| (p
->selFlags
& SF_Distinct
)!=0 || pSrc
->nSrc
!=1 ){
3807 return 0; /* (17d1), (17d2), or (17d3) */
3809 for(pSub1
=pSub
; pSub1
; pSub1
=pSub1
->pPrior
){
3810 testcase( (pSub1
->selFlags
& (SF_Distinct
|SF_Aggregate
))==SF_Distinct
);
3811 testcase( (pSub1
->selFlags
& (SF_Distinct
|SF_Aggregate
))==SF_Aggregate
);
3812 assert( pSub
->pSrc
!=0 );
3813 assert( pSub
->pEList
->nExpr
==pSub1
->pEList
->nExpr
);
3814 if( (pSub1
->selFlags
& (SF_Distinct
|SF_Aggregate
))!=0 /* (17b) */
3815 || (pSub1
->pPrior
&& pSub1
->op
!=TK_ALL
) /* (17a) */
3816 || pSub1
->pSrc
->nSrc
<1 /* (17c) */
3820 testcase( pSub1
->pSrc
->nSrc
>1 );
3823 /* Restriction (18). */
3826 for(ii
=0; ii
<p
->pOrderBy
->nExpr
; ii
++){
3827 if( p
->pOrderBy
->a
[ii
].u
.x
.iOrderByCol
==0 ) return 0;
3832 /* Ex-restriction (23):
3833 ** The only way that the recursive part of a CTE can contain a compound
3834 ** subquery is for the subquery to be one term of a join. But if the
3835 ** subquery is a join, then the flattening has already been stopped by
3836 ** restriction (17d3)
3838 assert( (p
->selFlags
& SF_Recursive
)==0 || pSub
->pPrior
==0 );
3840 /***** If we reach this point, flattening is permitted. *****/
3841 SELECTTRACE(1,pParse
,p
,("flatten %s.%p from term %d\n",
3842 pSub
->zSelName
, pSub
, iFrom
));
3844 /* Authorize the subquery */
3845 pParse
->zAuthContext
= pSubitem
->zName
;
3846 TESTONLY(i
=) sqlite3AuthCheck(pParse
, SQLITE_SELECT
, 0, 0, 0);
3847 testcase( i
==SQLITE_DENY
);
3848 pParse
->zAuthContext
= zSavedAuthContext
;
3850 /* If the sub-query is a compound SELECT statement, then (by restrictions
3851 ** 17 and 18 above) it must be a UNION ALL and the parent query must
3854 ** SELECT <expr-list> FROM (<sub-query>) <where-clause>
3856 ** followed by any ORDER BY, LIMIT and/or OFFSET clauses. This block
3857 ** creates N-1 copies of the parent query without any ORDER BY, LIMIT or
3858 ** OFFSET clauses and joins them to the left-hand-side of the original
3859 ** using UNION ALL operators. In this case N is the number of simple
3860 ** select statements in the compound sub-query.
3864 ** SELECT a+1 FROM (
3865 ** SELECT x FROM tab
3867 ** SELECT y FROM tab
3869 ** SELECT abs(z*2) FROM tab2
3870 ** ) WHERE a!=5 ORDER BY 1
3872 ** Transformed into:
3874 ** SELECT x+1 FROM tab WHERE x+1!=5
3876 ** SELECT y+1 FROM tab WHERE y+1!=5
3878 ** SELECT abs(z*2)+1 FROM tab2 WHERE abs(z*2)+1!=5
3881 ** We call this the "compound-subquery flattening".
3883 for(pSub
=pSub
->pPrior
; pSub
; pSub
=pSub
->pPrior
){
3885 ExprList
*pOrderBy
= p
->pOrderBy
;
3886 Expr
*pLimit
= p
->pLimit
;
3887 Select
*pPrior
= p
->pPrior
;
3892 pNew
= sqlite3SelectDup(db
, p
, 0);
3893 sqlite3SelectSetName(pNew
, pSub
->zSelName
);
3895 p
->pOrderBy
= pOrderBy
;
3901 pNew
->pPrior
= pPrior
;
3902 if( pPrior
) pPrior
->pNext
= pNew
;
3905 SELECTTRACE(2,pParse
,p
,("compound-subquery flattener"
3906 " creates %s.%p as peer\n",pNew
->zSelName
, pNew
));
3908 if( db
->mallocFailed
) return 1;
3911 /* Begin flattening the iFrom-th entry of the FROM clause
3912 ** in the outer query.
3914 pSub
= pSub1
= pSubitem
->pSelect
;
3916 /* Delete the transient table structure associated with the
3919 sqlite3DbFree(db
, pSubitem
->zDatabase
);
3920 sqlite3DbFree(db
, pSubitem
->zName
);
3921 sqlite3DbFree(db
, pSubitem
->zAlias
);
3922 pSubitem
->zDatabase
= 0;
3923 pSubitem
->zName
= 0;
3924 pSubitem
->zAlias
= 0;
3925 pSubitem
->pSelect
= 0;
3927 /* Defer deleting the Table object associated with the
3928 ** subquery until code generation is
3929 ** complete, since there may still exist Expr.pTab entries that
3930 ** refer to the subquery even after flattening. Ticket #3346.
3932 ** pSubitem->pTab is always non-NULL by test restrictions and tests above.
3934 if( ALWAYS(pSubitem
->pTab
!=0) ){
3935 Table
*pTabToDel
= pSubitem
->pTab
;
3936 if( pTabToDel
->nTabRef
==1 ){
3937 Parse
*pToplevel
= sqlite3ParseToplevel(pParse
);
3938 pTabToDel
->pNextZombie
= pToplevel
->pZombieTab
;
3939 pToplevel
->pZombieTab
= pTabToDel
;
3941 pTabToDel
->nTabRef
--;
3946 /* The following loop runs once for each term in a compound-subquery
3947 ** flattening (as described above). If we are doing a different kind
3948 ** of flattening - a flattening other than a compound-subquery flattening -
3949 ** then this loop only runs once.
3951 ** This loop moves all of the FROM elements of the subquery into the
3952 ** the FROM clause of the outer query. Before doing this, remember
3953 ** the cursor number for the original outer query FROM element in
3954 ** iParent. The iParent cursor will never be used. Subsequent code
3955 ** will scan expressions looking for iParent references and replace
3956 ** those references with expressions that resolve to the subquery FROM
3957 ** elements we are now copying in.
3959 for(pParent
=p
; pParent
; pParent
=pParent
->pPrior
, pSub
=pSub
->pPrior
){
3962 pSubSrc
= pSub
->pSrc
; /* FROM clause of subquery */
3963 nSubSrc
= pSubSrc
->nSrc
; /* Number of terms in subquery FROM clause */
3964 pSrc
= pParent
->pSrc
; /* FROM clause of the outer query */
3967 assert( pParent
==p
); /* First time through the loop */
3968 jointype
= pSubitem
->fg
.jointype
;
3970 assert( pParent
!=p
); /* 2nd and subsequent times through the loop */
3971 pSrc
= pParent
->pSrc
= sqlite3SrcListAppend(db
, 0, 0, 0);
3973 assert( db
->mallocFailed
);
3978 /* The subquery uses a single slot of the FROM clause of the outer
3979 ** query. If the subquery has more than one element in its FROM clause,
3980 ** then expand the outer query to make space for it to hold all elements
3985 ** SELECT * FROM tabA, (SELECT * FROM sub1, sub2), tabB;
3987 ** The outer query has 3 slots in its FROM clause. One slot of the
3988 ** outer query (the middle slot) is used by the subquery. The next
3989 ** block of code will expand the outer query FROM clause to 4 slots.
3990 ** The middle slot is expanded to two slots in order to make space
3991 ** for the two elements in the FROM clause of the subquery.
3994 pParent
->pSrc
= pSrc
= sqlite3SrcListEnlarge(db
, pSrc
, nSubSrc
-1,iFrom
+1);
3995 if( db
->mallocFailed
){
4000 /* Transfer the FROM clause terms from the subquery into the
4003 for(i
=0; i
<nSubSrc
; i
++){
4004 sqlite3IdListDelete(db
, pSrc
->a
[i
+iFrom
].pUsing
);
4005 assert( pSrc
->a
[i
+iFrom
].fg
.isTabFunc
==0 );
4006 pSrc
->a
[i
+iFrom
] = pSubSrc
->a
[i
];
4007 iNewParent
= pSubSrc
->a
[i
].iCursor
;
4008 memset(&pSubSrc
->a
[i
], 0, sizeof(pSubSrc
->a
[i
]));
4010 pSrc
->a
[iFrom
].fg
.jointype
= jointype
;
4012 /* Now begin substituting subquery result set expressions for
4013 ** references to the iParent in the outer query.
4017 ** SELECT a+5, b*10 FROM (SELECT x*3 AS a, y+10 AS b FROM t1) WHERE a>b;
4018 ** \ \_____________ subquery __________/ /
4019 ** \_____________________ outer query ______________________________/
4021 ** We look at every expression in the outer query and every place we see
4022 ** "a" we substitute "x*3" and every place we see "b" we substitute "y+10".
4024 if( pSub
->pOrderBy
){
4025 /* At this point, any non-zero iOrderByCol values indicate that the
4026 ** ORDER BY column expression is identical to the iOrderByCol'th
4027 ** expression returned by SELECT statement pSub. Since these values
4028 ** do not necessarily correspond to columns in SELECT statement pParent,
4029 ** zero them before transfering the ORDER BY clause.
4031 ** Not doing this may cause an error if a subsequent call to this
4032 ** function attempts to flatten a compound sub-query into pParent
4033 ** (the only way this can happen is if the compound sub-query is
4034 ** currently part of pSub->pSrc). See ticket [d11a6e908f]. */
4035 ExprList
*pOrderBy
= pSub
->pOrderBy
;
4036 for(i
=0; i
<pOrderBy
->nExpr
; i
++){
4037 pOrderBy
->a
[i
].u
.x
.iOrderByCol
= 0;
4039 assert( pParent
->pOrderBy
==0 );
4040 pParent
->pOrderBy
= pOrderBy
;
4043 pWhere
= sqlite3ExprDup(db
, pSub
->pWhere
, 0);
4045 setJoinExpr(pWhere
, iNewParent
);
4047 pParent
->pWhere
= sqlite3ExprAnd(db
, pWhere
, pParent
->pWhere
);
4048 if( db
->mallocFailed
==0 ){
4052 x
.iNewTable
= iNewParent
;
4053 x
.isLeftJoin
= isLeftJoin
;
4054 x
.pEList
= pSub
->pEList
;
4055 substSelect(&x
, pParent
, 0);
4058 /* The flattened query is distinct if either the inner or the
4059 ** outer query is distinct.
4061 pParent
->selFlags
|= pSub
->selFlags
& SF_Distinct
;
4064 ** SELECT ... FROM (SELECT ... LIMIT a OFFSET b) LIMIT x OFFSET y;
4066 ** One is tempted to try to add a and b to combine the limits. But this
4067 ** does not work if either limit is negative.
4070 pParent
->pLimit
= pSub
->pLimit
;
4075 /* Finially, delete what is left of the subquery and return
4078 sqlite3SelectDelete(db
, pSub1
);
4080 #if SELECTTRACE_ENABLED
4081 if( sqlite3SelectTrace
& 0x100 ){
4082 SELECTTRACE(0x100,pParse
,p
,("After flattening:\n"));
4083 sqlite3TreeViewSelect(0, p
, 0);
4089 #endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */
4093 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
4095 ** Make copies of relevant WHERE clause terms of the outer query into
4096 ** the WHERE clause of subquery. Example:
4098 ** SELECT * FROM (SELECT a AS x, c-d AS y FROM t1) WHERE x=5 AND y=10;
4100 ** Transformed into:
4102 ** SELECT * FROM (SELECT a AS x, c-d AS y FROM t1 WHERE a=5 AND c-d=10)
4103 ** WHERE x=5 AND y=10;
4105 ** The hope is that the terms added to the inner query will make it more
4108 ** Do not attempt this optimization if:
4110 ** (1) (** This restriction was removed on 2017-09-29. We used to
4111 ** disallow this optimization for aggregate subqueries, but now
4112 ** it is allowed by putting the extra terms on the HAVING clause.
4113 ** The added HAVING clause is pointless if the subquery lacks
4114 ** a GROUP BY clause. But such a HAVING clause is also harmless
4115 ** so there does not appear to be any reason to add extra logic
4116 ** to suppress it. **)
4118 ** (2) The inner query is the recursive part of a common table expression.
4120 ** (3) The inner query has a LIMIT clause (since the changes to the WHERE
4121 ** clause would change the meaning of the LIMIT).
4123 ** (4) The inner query is the right operand of a LEFT JOIN and the
4124 ** expression to be pushed down does not come from the ON clause
4125 ** on that LEFT JOIN.
4127 ** (5) The WHERE clause expression originates in the ON or USING clause
4128 ** of a LEFT JOIN where iCursor is not the right-hand table of that
4129 ** left join. An example:
4132 ** FROM (SELECT 1 AS a1 UNION ALL SELECT 2) AS aa
4133 ** JOIN (SELECT 1 AS b2 UNION ALL SELECT 2) AS bb ON (a1=b2)
4134 ** LEFT JOIN (SELECT 8 AS c3 UNION ALL SELECT 9) AS cc ON (b2=2);
4136 ** The correct answer is three rows: (1,1,NULL),(2,2,8),(2,2,9).
4137 ** But if the (b2=2) term were to be pushed down into the bb subquery,
4138 ** then the (1,1,NULL) row would be suppressed.
4140 ** (6) The inner query features one or more window-functions (since
4141 ** changes to the WHERE clause of the inner query could change the
4142 ** window over which window functions are calculated).
4144 ** Return 0 if no changes are made and non-zero if one or more WHERE clause
4145 ** terms are duplicated into the subquery.
4147 static int pushDownWhereTerms(
4148 Parse
*pParse
, /* Parse context (for malloc() and error reporting) */
4149 Select
*pSubq
, /* The subquery whose WHERE clause is to be augmented */
4150 Expr
*pWhere
, /* The WHERE clause of the outer query */
4151 int iCursor
, /* Cursor number of the subquery */
4152 int isLeftJoin
/* True if pSubq is the right term of a LEFT JOIN */
4156 if( pWhere
==0 ) return 0;
4157 if( pSubq
->selFlags
& SF_Recursive
) return 0; /* restriction (2) */
4159 #ifndef SQLITE_OMIT_WINDOWFUNC
4160 if( pSubq
->pWin
) return 0;
4164 /* Only the first term of a compound can have a WITH clause. But make
4165 ** sure no other terms are marked SF_Recursive in case something changes
4170 for(pX
=pSubq
; pX
; pX
=pX
->pPrior
){
4171 assert( (pX
->selFlags
& (SF_Recursive
))==0 );
4176 if( pSubq
->pLimit
!=0 ){
4177 return 0; /* restriction (3) */
4179 while( pWhere
->op
==TK_AND
){
4180 nChng
+= pushDownWhereTerms(pParse
, pSubq
, pWhere
->pRight
,
4181 iCursor
, isLeftJoin
);
4182 pWhere
= pWhere
->pLeft
;
4185 && (ExprHasProperty(pWhere
,EP_FromJoin
)==0
4186 || pWhere
->iRightJoinTable
!=iCursor
)
4188 return 0; /* restriction (4) */
4190 if( ExprHasProperty(pWhere
,EP_FromJoin
) && pWhere
->iRightJoinTable
!=iCursor
){
4191 return 0; /* restriction (5) */
4193 if( sqlite3ExprIsTableConstant(pWhere
, iCursor
) ){
4197 pNew
= sqlite3ExprDup(pParse
->db
, pWhere
, 0);
4198 unsetJoinExpr(pNew
, -1);
4201 x
.iNewTable
= iCursor
;
4203 x
.pEList
= pSubq
->pEList
;
4204 pNew
= substExpr(&x
, pNew
);
4205 if( pSubq
->selFlags
& SF_Aggregate
){
4206 pSubq
->pHaving
= sqlite3ExprAnd(pParse
->db
, pSubq
->pHaving
, pNew
);
4208 pSubq
->pWhere
= sqlite3ExprAnd(pParse
->db
, pSubq
->pWhere
, pNew
);
4210 pSubq
= pSubq
->pPrior
;
4215 #endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */
4218 ** The pFunc is the only aggregate function in the query. Check to see
4219 ** if the query is a candidate for the min/max optimization.
4221 ** If the query is a candidate for the min/max optimization, then set
4222 ** *ppMinMax to be an ORDER BY clause to be used for the optimization
4223 ** and return either WHERE_ORDERBY_MIN or WHERE_ORDERBY_MAX depending on
4224 ** whether pFunc is a min() or max() function.
4226 ** If the query is not a candidate for the min/max optimization, return
4227 ** WHERE_ORDERBY_NORMAL (which must be zero).
4229 ** This routine must be called after aggregate functions have been
4230 ** located but before their arguments have been subjected to aggregate
4233 static u8
minMaxQuery(sqlite3
*db
, Expr
*pFunc
, ExprList
**ppMinMax
){
4234 int eRet
= WHERE_ORDERBY_NORMAL
; /* Return value */
4235 ExprList
*pEList
= pFunc
->x
.pList
; /* Arguments to agg function */
4236 const char *zFunc
; /* Name of aggregate function pFunc */
4240 assert( *ppMinMax
==0 );
4241 assert( pFunc
->op
==TK_AGG_FUNCTION
);
4242 if( pEList
==0 || pEList
->nExpr
!=1 ) return eRet
;
4243 zFunc
= pFunc
->u
.zToken
;
4244 if( sqlite3StrICmp(zFunc
, "min")==0 ){
4245 eRet
= WHERE_ORDERBY_MIN
;
4246 sortOrder
= SQLITE_SO_ASC
;
4247 }else if( sqlite3StrICmp(zFunc
, "max")==0 ){
4248 eRet
= WHERE_ORDERBY_MAX
;
4249 sortOrder
= SQLITE_SO_DESC
;
4253 *ppMinMax
= pOrderBy
= sqlite3ExprListDup(db
, pEList
, 0);
4254 assert( pOrderBy
!=0 || db
->mallocFailed
);
4255 if( pOrderBy
) pOrderBy
->a
[0].sortOrder
= sortOrder
;
4260 ** The select statement passed as the first argument is an aggregate query.
4261 ** The second argument is the associated aggregate-info object. This
4262 ** function tests if the SELECT is of the form:
4264 ** SELECT count(*) FROM <tbl>
4266 ** where table is a database table, not a sub-select or view. If the query
4267 ** does match this pattern, then a pointer to the Table object representing
4268 ** <tbl> is returned. Otherwise, 0 is returned.
4270 static Table
*isSimpleCount(Select
*p
, AggInfo
*pAggInfo
){
4274 assert( !p
->pGroupBy
);
4276 if( p
->pWhere
|| p
->pEList
->nExpr
!=1
4277 || p
->pSrc
->nSrc
!=1 || p
->pSrc
->a
[0].pSelect
4281 pTab
= p
->pSrc
->a
[0].pTab
;
4282 pExpr
= p
->pEList
->a
[0].pExpr
;
4283 assert( pTab
&& !pTab
->pSelect
&& pExpr
);
4285 if( IsVirtual(pTab
) ) return 0;
4286 if( pExpr
->op
!=TK_AGG_FUNCTION
) return 0;
4287 if( NEVER(pAggInfo
->nFunc
==0) ) return 0;
4288 if( (pAggInfo
->aFunc
[0].pFunc
->funcFlags
&SQLITE_FUNC_COUNT
)==0 ) return 0;
4289 if( pExpr
->flags
&EP_Distinct
) return 0;
4295 ** If the source-list item passed as an argument was augmented with an
4296 ** INDEXED BY clause, then try to locate the specified index. If there
4297 ** was such a clause and the named index cannot be found, return
4298 ** SQLITE_ERROR and leave an error in pParse. Otherwise, populate
4299 ** pFrom->pIndex and return SQLITE_OK.
4301 int sqlite3IndexedByLookup(Parse
*pParse
, struct SrcList_item
*pFrom
){
4302 if( pFrom
->pTab
&& pFrom
->fg
.isIndexedBy
){
4303 Table
*pTab
= pFrom
->pTab
;
4304 char *zIndexedBy
= pFrom
->u1
.zIndexedBy
;
4306 for(pIdx
=pTab
->pIndex
;
4307 pIdx
&& sqlite3StrICmp(pIdx
->zName
, zIndexedBy
);
4311 sqlite3ErrorMsg(pParse
, "no such index: %s", zIndexedBy
, 0);
4312 pParse
->checkSchema
= 1;
4313 return SQLITE_ERROR
;
4315 pFrom
->pIBIndex
= pIdx
;
4320 ** Detect compound SELECT statements that use an ORDER BY clause with
4321 ** an alternative collating sequence.
4323 ** SELECT ... FROM t1 EXCEPT SELECT ... FROM t2 ORDER BY .. COLLATE ...
4325 ** These are rewritten as a subquery:
4327 ** SELECT * FROM (SELECT ... FROM t1 EXCEPT SELECT ... FROM t2)
4328 ** ORDER BY ... COLLATE ...
4330 ** This transformation is necessary because the multiSelectOrderBy() routine
4331 ** above that generates the code for a compound SELECT with an ORDER BY clause
4332 ** uses a merge algorithm that requires the same collating sequence on the
4333 ** result columns as on the ORDER BY clause. See ticket
4334 ** http://www.sqlite.org/src/info/6709574d2a
4336 ** This transformation is only needed for EXCEPT, INTERSECT, and UNION.
4337 ** The UNION ALL operator works fine with multiSelectOrderBy() even when
4338 ** there are COLLATE terms in the ORDER BY.
4340 static int convertCompoundSelectToSubquery(Walker
*pWalker
, Select
*p
){
4345 struct ExprList_item
*a
;
4350 if( p
->pPrior
==0 ) return WRC_Continue
;
4351 if( p
->pOrderBy
==0 ) return WRC_Continue
;
4352 for(pX
=p
; pX
&& (pX
->op
==TK_ALL
|| pX
->op
==TK_SELECT
); pX
=pX
->pPrior
){}
4353 if( pX
==0 ) return WRC_Continue
;
4355 for(i
=p
->pOrderBy
->nExpr
-1; i
>=0; i
--){
4356 if( a
[i
].pExpr
->flags
& EP_Collate
) break;
4358 if( i
<0 ) return WRC_Continue
;
4360 /* If we reach this point, that means the transformation is required. */
4362 pParse
= pWalker
->pParse
;
4364 pNew
= sqlite3DbMallocZero(db
, sizeof(*pNew
) );
4365 if( pNew
==0 ) return WRC_Abort
;
4366 memset(&dummy
, 0, sizeof(dummy
));
4367 pNewSrc
= sqlite3SrcListAppendFromTerm(pParse
,0,0,0,&dummy
,pNew
,0,0);
4368 if( pNewSrc
==0 ) return WRC_Abort
;
4371 p
->pEList
= sqlite3ExprListAppend(pParse
, 0, sqlite3Expr(db
, TK_ASTERISK
, 0));
4380 p
->selFlags
&= ~SF_Compound
;
4381 assert( (p
->selFlags
& SF_Converted
)==0 );
4382 p
->selFlags
|= SF_Converted
;
4383 assert( pNew
->pPrior
!=0 );
4384 pNew
->pPrior
->pNext
= pNew
;
4386 return WRC_Continue
;
4390 ** Check to see if the FROM clause term pFrom has table-valued function
4391 ** arguments. If it does, leave an error message in pParse and return
4392 ** non-zero, since pFrom is not allowed to be a table-valued function.
4394 static int cannotBeFunction(Parse
*pParse
, struct SrcList_item
*pFrom
){
4395 if( pFrom
->fg
.isTabFunc
){
4396 sqlite3ErrorMsg(pParse
, "'%s' is not a function", pFrom
->zName
);
4402 #ifndef SQLITE_OMIT_CTE
4404 ** Argument pWith (which may be NULL) points to a linked list of nested
4405 ** WITH contexts, from inner to outermost. If the table identified by
4406 ** FROM clause element pItem is really a common-table-expression (CTE)
4407 ** then return a pointer to the CTE definition for that table. Otherwise
4410 ** If a non-NULL value is returned, set *ppContext to point to the With
4411 ** object that the returned CTE belongs to.
4413 static struct Cte
*searchWith(
4414 With
*pWith
, /* Current innermost WITH clause */
4415 struct SrcList_item
*pItem
, /* FROM clause element to resolve */
4416 With
**ppContext
/* OUT: WITH clause return value belongs to */
4419 if( pItem
->zDatabase
==0 && (zName
= pItem
->zName
)!=0 ){
4421 for(p
=pWith
; p
; p
=p
->pOuter
){
4423 for(i
=0; i
<p
->nCte
; i
++){
4424 if( sqlite3StrICmp(zName
, p
->a
[i
].zName
)==0 ){
4434 /* The code generator maintains a stack of active WITH clauses
4435 ** with the inner-most WITH clause being at the top of the stack.
4437 ** This routine pushes the WITH clause passed as the second argument
4438 ** onto the top of the stack. If argument bFree is true, then this
4439 ** WITH clause will never be popped from the stack. In this case it
4440 ** should be freed along with the Parse object. In other cases, when
4441 ** bFree==0, the With object will be freed along with the SELECT
4442 ** statement with which it is associated.
4444 void sqlite3WithPush(Parse
*pParse
, With
*pWith
, u8 bFree
){
4445 assert( bFree
==0 || (pParse
->pWith
==0 && pParse
->pWithToFree
==0) );
4447 assert( pParse
->pWith
!=pWith
);
4448 pWith
->pOuter
= pParse
->pWith
;
4449 pParse
->pWith
= pWith
;
4450 if( bFree
) pParse
->pWithToFree
= pWith
;
4455 ** This function checks if argument pFrom refers to a CTE declared by
4456 ** a WITH clause on the stack currently maintained by the parser. And,
4457 ** if currently processing a CTE expression, if it is a recursive
4458 ** reference to the current CTE.
4460 ** If pFrom falls into either of the two categories above, pFrom->pTab
4461 ** and other fields are populated accordingly. The caller should check
4462 ** (pFrom->pTab!=0) to determine whether or not a successful match
4465 ** Whether or not a match is found, SQLITE_OK is returned if no error
4466 ** occurs. If an error does occur, an error message is stored in the
4467 ** parser and some error code other than SQLITE_OK returned.
4469 static int withExpand(
4471 struct SrcList_item
*pFrom
4473 Parse
*pParse
= pWalker
->pParse
;
4474 sqlite3
*db
= pParse
->db
;
4475 struct Cte
*pCte
; /* Matched CTE (or NULL if no match) */
4476 With
*pWith
; /* WITH clause that pCte belongs to */
4478 assert( pFrom
->pTab
==0 );
4480 pCte
= searchWith(pParse
->pWith
, pFrom
, &pWith
);
4485 Select
*pLeft
; /* Left-most SELECT statement */
4486 int bMayRecursive
; /* True if compound joined by UNION [ALL] */
4487 With
*pSavedWith
; /* Initial value of pParse->pWith */
4489 /* If pCte->zCteErr is non-NULL at this point, then this is an illegal
4490 ** recursive reference to CTE pCte. Leave an error in pParse and return
4491 ** early. If pCte->zCteErr is NULL, then this is not a recursive reference.
4492 ** In this case, proceed. */
4493 if( pCte
->zCteErr
){
4494 sqlite3ErrorMsg(pParse
, pCte
->zCteErr
, pCte
->zName
);
4495 return SQLITE_ERROR
;
4497 if( cannotBeFunction(pParse
, pFrom
) ) return SQLITE_ERROR
;
4499 assert( pFrom
->pTab
==0 );
4500 pFrom
->pTab
= pTab
= sqlite3DbMallocZero(db
, sizeof(Table
));
4501 if( pTab
==0 ) return WRC_Abort
;
4503 pTab
->zName
= sqlite3DbStrDup(db
, pCte
->zName
);
4505 pTab
->nRowLogEst
= 200; assert( 200==sqlite3LogEst(1048576) );
4506 pTab
->tabFlags
|= TF_Ephemeral
| TF_NoVisibleRowid
;
4507 pFrom
->pSelect
= sqlite3SelectDup(db
, pCte
->pSelect
, 0);
4508 if( db
->mallocFailed
) return SQLITE_NOMEM_BKPT
;
4509 assert( pFrom
->pSelect
);
4511 /* Check if this is a recursive CTE. */
4512 pSel
= pFrom
->pSelect
;
4513 bMayRecursive
= ( pSel
->op
==TK_ALL
|| pSel
->op
==TK_UNION
);
4514 if( bMayRecursive
){
4516 SrcList
*pSrc
= pFrom
->pSelect
->pSrc
;
4517 for(i
=0; i
<pSrc
->nSrc
; i
++){
4518 struct SrcList_item
*pItem
= &pSrc
->a
[i
];
4519 if( pItem
->zDatabase
==0
4521 && 0==sqlite3StrICmp(pItem
->zName
, pCte
->zName
)
4524 pItem
->fg
.isRecursive
= 1;
4526 pSel
->selFlags
|= SF_Recursive
;
4531 /* Only one recursive reference is permitted. */
4532 if( pTab
->nTabRef
>2 ){
4534 pParse
, "multiple references to recursive table: %s", pCte
->zName
4536 return SQLITE_ERROR
;
4538 assert( pTab
->nTabRef
==1 ||
4539 ((pSel
->selFlags
&SF_Recursive
) && pTab
->nTabRef
==2 ));
4541 pCte
->zCteErr
= "circular reference: %s";
4542 pSavedWith
= pParse
->pWith
;
4543 pParse
->pWith
= pWith
;
4544 if( bMayRecursive
){
4545 Select
*pPrior
= pSel
->pPrior
;
4546 assert( pPrior
->pWith
==0 );
4547 pPrior
->pWith
= pSel
->pWith
;
4548 sqlite3WalkSelect(pWalker
, pPrior
);
4551 sqlite3WalkSelect(pWalker
, pSel
);
4553 pParse
->pWith
= pWith
;
4555 for(pLeft
=pSel
; pLeft
->pPrior
; pLeft
=pLeft
->pPrior
);
4556 pEList
= pLeft
->pEList
;
4558 if( pEList
&& pEList
->nExpr
!=pCte
->pCols
->nExpr
){
4559 sqlite3ErrorMsg(pParse
, "table %s has %d values for %d columns",
4560 pCte
->zName
, pEList
->nExpr
, pCte
->pCols
->nExpr
4562 pParse
->pWith
= pSavedWith
;
4563 return SQLITE_ERROR
;
4565 pEList
= pCte
->pCols
;
4568 sqlite3ColumnsFromExprList(pParse
, pEList
, &pTab
->nCol
, &pTab
->aCol
);
4569 if( bMayRecursive
){
4570 if( pSel
->selFlags
& SF_Recursive
){
4571 pCte
->zCteErr
= "multiple recursive references: %s";
4573 pCte
->zCteErr
= "recursive reference in a subquery: %s";
4575 sqlite3WalkSelect(pWalker
, pSel
);
4578 pParse
->pWith
= pSavedWith
;
4585 #ifndef SQLITE_OMIT_CTE
4587 ** If the SELECT passed as the second argument has an associated WITH
4588 ** clause, pop it from the stack stored as part of the Parse object.
4590 ** This function is used as the xSelectCallback2() callback by
4591 ** sqlite3SelectExpand() when walking a SELECT tree to resolve table
4592 ** names and other FROM clause elements.
4594 static void selectPopWith(Walker
*pWalker
, Select
*p
){
4595 Parse
*pParse
= pWalker
->pParse
;
4596 if( OK_IF_ALWAYS_TRUE(pParse
->pWith
) && p
->pPrior
==0 ){
4597 With
*pWith
= findRightmost(p
)->pWith
;
4599 assert( pParse
->pWith
==pWith
);
4600 pParse
->pWith
= pWith
->pOuter
;
4605 #define selectPopWith 0
4609 ** The SrcList_item structure passed as the second argument represents a
4610 ** sub-query in the FROM clause of a SELECT statement. This function
4611 ** allocates and populates the SrcList_item.pTab object. If successful,
4612 ** SQLITE_OK is returned. Otherwise, if an OOM error is encountered,
4615 int sqlite3ExpandSubquery(Parse
*pParse
, struct SrcList_item
*pFrom
){
4616 Select
*pSel
= pFrom
->pSelect
;
4620 pFrom
->pTab
= pTab
= sqlite3DbMallocZero(pParse
->db
, sizeof(Table
));
4621 if( pTab
==0 ) return SQLITE_NOMEM
;
4623 if( pFrom
->zAlias
){
4624 pTab
->zName
= sqlite3DbStrDup(pParse
->db
, pFrom
->zAlias
);
4626 pTab
->zName
= sqlite3MPrintf(pParse
->db
, "subquery_%p", (void*)pTab
);
4628 while( pSel
->pPrior
){ pSel
= pSel
->pPrior
; }
4629 sqlite3ColumnsFromExprList(pParse
, pSel
->pEList
,&pTab
->nCol
,&pTab
->aCol
);
4631 pTab
->nRowLogEst
= 200; assert( 200==sqlite3LogEst(1048576) );
4632 pTab
->tabFlags
|= TF_Ephemeral
;
4638 ** This routine is a Walker callback for "expanding" a SELECT statement.
4639 ** "Expanding" means to do the following:
4641 ** (1) Make sure VDBE cursor numbers have been assigned to every
4642 ** element of the FROM clause.
4644 ** (2) Fill in the pTabList->a[].pTab fields in the SrcList that
4645 ** defines FROM clause. When views appear in the FROM clause,
4646 ** fill pTabList->a[].pSelect with a copy of the SELECT statement
4647 ** that implements the view. A copy is made of the view's SELECT
4648 ** statement so that we can freely modify or delete that statement
4649 ** without worrying about messing up the persistent representation
4652 ** (3) Add terms to the WHERE clause to accommodate the NATURAL keyword
4653 ** on joins and the ON and USING clause of joins.
4655 ** (4) Scan the list of columns in the result set (pEList) looking
4656 ** for instances of the "*" operator or the TABLE.* operator.
4657 ** If found, expand each "*" to be every column in every table
4658 ** and TABLE.* to be every column in TABLE.
4661 static int selectExpander(Walker
*pWalker
, Select
*p
){
4662 Parse
*pParse
= pWalker
->pParse
;
4666 struct SrcList_item
*pFrom
;
4667 sqlite3
*db
= pParse
->db
;
4668 Expr
*pE
, *pRight
, *pExpr
;
4669 u16 selFlags
= p
->selFlags
;
4672 p
->selFlags
|= SF_Expanded
;
4673 if( db
->mallocFailed
){
4676 assert( p
->pSrc
!=0 );
4677 if( (selFlags
& SF_Expanded
)!=0 ){
4682 sqlite3WithPush(pParse
, p
->pWith
, 0);
4684 /* Make sure cursor numbers have been assigned to all entries in
4685 ** the FROM clause of the SELECT statement.
4687 sqlite3SrcListAssignCursors(pParse
, pTabList
);
4689 /* Look up every table named in the FROM clause of the select. If
4690 ** an entry of the FROM clause is a subquery instead of a table or view,
4691 ** then create a transient table structure to describe the subquery.
4693 for(i
=0, pFrom
=pTabList
->a
; i
<pTabList
->nSrc
; i
++, pFrom
++){
4695 assert( pFrom
->fg
.isRecursive
==0 || pFrom
->pTab
!=0 );
4696 if( pFrom
->fg
.isRecursive
) continue;
4697 assert( pFrom
->pTab
==0 );
4698 #ifndef SQLITE_OMIT_CTE
4699 if( withExpand(pWalker
, pFrom
) ) return WRC_Abort
;
4700 if( pFrom
->pTab
) {} else
4702 if( pFrom
->zName
==0 ){
4703 #ifndef SQLITE_OMIT_SUBQUERY
4704 Select
*pSel
= pFrom
->pSelect
;
4705 /* A sub-query in the FROM clause of a SELECT */
4707 assert( pFrom
->pTab
==0 );
4708 if( sqlite3WalkSelect(pWalker
, pSel
) ) return WRC_Abort
;
4709 if( sqlite3ExpandSubquery(pParse
, pFrom
) ) return WRC_Abort
;
4712 /* An ordinary table or view name in the FROM clause */
4713 assert( pFrom
->pTab
==0 );
4714 pFrom
->pTab
= pTab
= sqlite3LocateTableItem(pParse
, 0, pFrom
);
4715 if( pTab
==0 ) return WRC_Abort
;
4716 if( pTab
->nTabRef
>=0xffff ){
4717 sqlite3ErrorMsg(pParse
, "too many references to \"%s\": max 65535",
4723 if( !IsVirtual(pTab
) && cannotBeFunction(pParse
, pFrom
) ){
4726 #if !defined(SQLITE_OMIT_VIEW) || !defined (SQLITE_OMIT_VIRTUALTABLE)
4727 if( IsVirtual(pTab
) || pTab
->pSelect
){
4729 if( sqlite3ViewGetColumnNames(pParse
, pTab
) ) return WRC_Abort
;
4730 assert( pFrom
->pSelect
==0 );
4731 pFrom
->pSelect
= sqlite3SelectDup(db
, pTab
->pSelect
, 0);
4732 sqlite3SelectSetName(pFrom
->pSelect
, pTab
->zName
);
4735 sqlite3WalkSelect(pWalker
, pFrom
->pSelect
);
4741 /* Locate the index named by the INDEXED BY clause, if any. */
4742 if( sqlite3IndexedByLookup(pParse
, pFrom
) ){
4747 /* Process NATURAL keywords, and ON and USING clauses of joins.
4749 if( db
->mallocFailed
|| sqliteProcessJoin(pParse
, p
) ){
4753 /* For every "*" that occurs in the column list, insert the names of
4754 ** all columns in all tables. And for every TABLE.* insert the names
4755 ** of all columns in TABLE. The parser inserted a special expression
4756 ** with the TK_ASTERISK operator for each "*" that it found in the column
4757 ** list. The following code just has to locate the TK_ASTERISK
4758 ** expressions and expand each one to the list of all columns in
4761 ** The first loop just checks to see if there are any "*" operators
4762 ** that need expanding.
4764 for(k
=0; k
<pEList
->nExpr
; k
++){
4765 pE
= pEList
->a
[k
].pExpr
;
4766 if( pE
->op
==TK_ASTERISK
) break;
4767 assert( pE
->op
!=TK_DOT
|| pE
->pRight
!=0 );
4768 assert( pE
->op
!=TK_DOT
|| (pE
->pLeft
!=0 && pE
->pLeft
->op
==TK_ID
) );
4769 if( pE
->op
==TK_DOT
&& pE
->pRight
->op
==TK_ASTERISK
) break;
4770 elistFlags
|= pE
->flags
;
4772 if( k
<pEList
->nExpr
){
4774 ** If we get here it means the result set contains one or more "*"
4775 ** operators that need to be expanded. Loop through each expression
4776 ** in the result set and expand them one by one.
4778 struct ExprList_item
*a
= pEList
->a
;
4780 int flags
= pParse
->db
->flags
;
4781 int longNames
= (flags
& SQLITE_FullColNames
)!=0
4782 && (flags
& SQLITE_ShortColNames
)==0;
4784 for(k
=0; k
<pEList
->nExpr
; k
++){
4786 elistFlags
|= pE
->flags
;
4787 pRight
= pE
->pRight
;
4788 assert( pE
->op
!=TK_DOT
|| pRight
!=0 );
4789 if( pE
->op
!=TK_ASTERISK
4790 && (pE
->op
!=TK_DOT
|| pRight
->op
!=TK_ASTERISK
)
4792 /* This particular expression does not need to be expanded.
4794 pNew
= sqlite3ExprListAppend(pParse
, pNew
, a
[k
].pExpr
);
4796 pNew
->a
[pNew
->nExpr
-1].zName
= a
[k
].zName
;
4797 pNew
->a
[pNew
->nExpr
-1].zSpan
= a
[k
].zSpan
;
4803 /* This expression is a "*" or a "TABLE.*" and needs to be
4805 int tableSeen
= 0; /* Set to 1 when TABLE matches */
4806 char *zTName
= 0; /* text of name of TABLE */
4807 if( pE
->op
==TK_DOT
){
4808 assert( pE
->pLeft
!=0 );
4809 assert( !ExprHasProperty(pE
->pLeft
, EP_IntValue
) );
4810 zTName
= pE
->pLeft
->u
.zToken
;
4812 for(i
=0, pFrom
=pTabList
->a
; i
<pTabList
->nSrc
; i
++, pFrom
++){
4813 Table
*pTab
= pFrom
->pTab
;
4814 Select
*pSub
= pFrom
->pSelect
;
4815 char *zTabName
= pFrom
->zAlias
;
4816 const char *zSchemaName
= 0;
4819 zTabName
= pTab
->zName
;
4821 if( db
->mallocFailed
) break;
4822 if( pSub
==0 || (pSub
->selFlags
& SF_NestedFrom
)==0 ){
4824 if( zTName
&& sqlite3StrICmp(zTName
, zTabName
)!=0 ){
4827 iDb
= sqlite3SchemaToIndex(db
, pTab
->pSchema
);
4828 zSchemaName
= iDb
>=0 ? db
->aDb
[iDb
].zDbSName
: "*";
4830 for(j
=0; j
<pTab
->nCol
; j
++){
4831 char *zName
= pTab
->aCol
[j
].zName
;
4832 char *zColname
; /* The computed column name */
4833 char *zToFree
; /* Malloced string that needs to be freed */
4834 Token sColname
; /* Computed column name as a token */
4838 && sqlite3MatchSpanName(pSub
->pEList
->a
[j
].zSpan
, 0, zTName
, 0)==0
4843 /* If a column is marked as 'hidden', omit it from the expanded
4844 ** result-set list unless the SELECT has the SF_IncludeHidden
4847 if( (p
->selFlags
& SF_IncludeHidden
)==0
4848 && IsHiddenColumn(&pTab
->aCol
[j
])
4854 if( i
>0 && zTName
==0 ){
4855 if( (pFrom
->fg
.jointype
& JT_NATURAL
)!=0
4856 && tableAndColumnIndex(pTabList
, i
, zName
, 0, 0)
4858 /* In a NATURAL join, omit the join columns from the
4859 ** table to the right of the join */
4862 if( sqlite3IdListIndex(pFrom
->pUsing
, zName
)>=0 ){
4863 /* In a join with a USING clause, omit columns in the
4864 ** using clause from the table on the right. */
4868 pRight
= sqlite3Expr(db
, TK_ID
, zName
);
4871 if( longNames
|| pTabList
->nSrc
>1 ){
4873 pLeft
= sqlite3Expr(db
, TK_ID
, zTabName
);
4874 pExpr
= sqlite3PExpr(pParse
, TK_DOT
, pLeft
, pRight
);
4876 pLeft
= sqlite3Expr(db
, TK_ID
, zSchemaName
);
4877 pExpr
= sqlite3PExpr(pParse
, TK_DOT
, pLeft
, pExpr
);
4880 zColname
= sqlite3MPrintf(db
, "%s.%s", zTabName
, zName
);
4886 pNew
= sqlite3ExprListAppend(pParse
, pNew
, pExpr
);
4887 sqlite3TokenInit(&sColname
, zColname
);
4888 sqlite3ExprListSetName(pParse
, pNew
, &sColname
, 0);
4889 if( pNew
&& (p
->selFlags
& SF_NestedFrom
)!=0 ){
4890 struct ExprList_item
*pX
= &pNew
->a
[pNew
->nExpr
-1];
4892 pX
->zSpan
= sqlite3DbStrDup(db
, pSub
->pEList
->a
[j
].zSpan
);
4893 testcase( pX
->zSpan
==0 );
4895 pX
->zSpan
= sqlite3MPrintf(db
, "%s.%s.%s",
4896 zSchemaName
, zTabName
, zColname
);
4897 testcase( pX
->zSpan
==0 );
4901 sqlite3DbFree(db
, zToFree
);
4906 sqlite3ErrorMsg(pParse
, "no such table: %s", zTName
);
4908 sqlite3ErrorMsg(pParse
, "no tables specified");
4913 sqlite3ExprListDelete(db
, pEList
);
4917 if( p
->pEList
->nExpr
>db
->aLimit
[SQLITE_LIMIT_COLUMN
] ){
4918 sqlite3ErrorMsg(pParse
, "too many columns in result set");
4921 if( (elistFlags
& (EP_HasFunc
|EP_Subquery
))!=0 ){
4922 p
->selFlags
|= SF_ComplexResult
;
4925 return WRC_Continue
;
4929 ** No-op routine for the parse-tree walker.
4931 ** When this routine is the Walker.xExprCallback then expression trees
4932 ** are walked without any actions being taken at each node. Presumably,
4933 ** when this routine is used for Walker.xExprCallback then
4934 ** Walker.xSelectCallback is set to do something useful for every
4935 ** subquery in the parser tree.
4937 int sqlite3ExprWalkNoop(Walker
*NotUsed
, Expr
*NotUsed2
){
4938 UNUSED_PARAMETER2(NotUsed
, NotUsed2
);
4939 return WRC_Continue
;
4943 ** No-op routine for the parse-tree walker for SELECT statements.
4944 ** subquery in the parser tree.
4946 int sqlite3SelectWalkNoop(Walker
*NotUsed
, Select
*NotUsed2
){
4947 UNUSED_PARAMETER2(NotUsed
, NotUsed2
);
4948 return WRC_Continue
;
4953 ** Always assert. This xSelectCallback2 implementation proves that the
4954 ** xSelectCallback2 is never invoked.
4956 void sqlite3SelectWalkAssert2(Walker
*NotUsed
, Select
*NotUsed2
){
4957 UNUSED_PARAMETER2(NotUsed
, NotUsed2
);
4962 ** This routine "expands" a SELECT statement and all of its subqueries.
4963 ** For additional information on what it means to "expand" a SELECT
4964 ** statement, see the comment on the selectExpand worker callback above.
4966 ** Expanding a SELECT statement is the first step in processing a
4967 ** SELECT statement. The SELECT statement must be expanded before
4968 ** name resolution is performed.
4970 ** If anything goes wrong, an error message is written into pParse.
4971 ** The calling function can detect the problem by looking at pParse->nErr
4972 ** and/or pParse->db->mallocFailed.
4974 static void sqlite3SelectExpand(Parse
*pParse
, Select
*pSelect
){
4976 w
.xExprCallback
= sqlite3ExprWalkNoop
;
4978 if( OK_IF_ALWAYS_TRUE(pParse
->hasCompound
) ){
4979 w
.xSelectCallback
= convertCompoundSelectToSubquery
;
4980 w
.xSelectCallback2
= 0;
4981 sqlite3WalkSelect(&w
, pSelect
);
4983 w
.xSelectCallback
= selectExpander
;
4984 w
.xSelectCallback2
= selectPopWith
;
4985 sqlite3WalkSelect(&w
, pSelect
);
4989 #ifndef SQLITE_OMIT_SUBQUERY
4991 ** This is a Walker.xSelectCallback callback for the sqlite3SelectTypeInfo()
4994 ** For each FROM-clause subquery, add Column.zType and Column.zColl
4995 ** information to the Table structure that represents the result set
4996 ** of that subquery.
4998 ** The Table structure that represents the result set was constructed
4999 ** by selectExpander() but the type and collation information was omitted
5000 ** at that point because identifiers had not yet been resolved. This
5001 ** routine is called after identifier resolution.
5003 static void selectAddSubqueryTypeInfo(Walker
*pWalker
, Select
*p
){
5007 struct SrcList_item
*pFrom
;
5009 assert( p
->selFlags
& SF_Resolved
);
5010 if( p
->selFlags
& SF_HasTypeInfo
) return;
5011 p
->selFlags
|= SF_HasTypeInfo
;
5012 pParse
= pWalker
->pParse
;
5014 for(i
=0, pFrom
=pTabList
->a
; i
<pTabList
->nSrc
; i
++, pFrom
++){
5015 Table
*pTab
= pFrom
->pTab
;
5017 if( (pTab
->tabFlags
& TF_Ephemeral
)!=0 ){
5018 /* A sub-query in the FROM clause of a SELECT */
5019 Select
*pSel
= pFrom
->pSelect
;
5021 while( pSel
->pPrior
) pSel
= pSel
->pPrior
;
5022 sqlite3SelectAddColumnTypeAndCollation(pParse
, pTab
, pSel
);
5031 ** This routine adds datatype and collating sequence information to
5032 ** the Table structures of all FROM-clause subqueries in a
5033 ** SELECT statement.
5035 ** Use this routine after name resolution.
5037 static void sqlite3SelectAddTypeInfo(Parse
*pParse
, Select
*pSelect
){
5038 #ifndef SQLITE_OMIT_SUBQUERY
5040 w
.xSelectCallback
= sqlite3SelectWalkNoop
;
5041 w
.xSelectCallback2
= selectAddSubqueryTypeInfo
;
5042 w
.xExprCallback
= sqlite3ExprWalkNoop
;
5044 sqlite3WalkSelect(&w
, pSelect
);
5050 ** This routine sets up a SELECT statement for processing. The
5051 ** following is accomplished:
5053 ** * VDBE Cursor numbers are assigned to all FROM-clause terms.
5054 ** * Ephemeral Table objects are created for all FROM-clause subqueries.
5055 ** * ON and USING clauses are shifted into WHERE statements
5056 ** * Wildcards "*" and "TABLE.*" in result sets are expanded.
5057 ** * Identifiers in expression are matched to tables.
5059 ** This routine acts recursively on all subqueries within the SELECT.
5061 void sqlite3SelectPrep(
5062 Parse
*pParse
, /* The parser context */
5063 Select
*p
, /* The SELECT statement being coded. */
5064 NameContext
*pOuterNC
/* Name context for container */
5066 assert( p
!=0 || pParse
->db
->mallocFailed
);
5067 if( pParse
->db
->mallocFailed
) return;
5068 if( p
->selFlags
& SF_HasTypeInfo
) return;
5069 sqlite3SelectExpand(pParse
, p
);
5070 if( pParse
->nErr
|| pParse
->db
->mallocFailed
) return;
5071 sqlite3ResolveSelectNames(pParse
, p
, pOuterNC
);
5072 if( pParse
->nErr
|| pParse
->db
->mallocFailed
) return;
5073 sqlite3SelectAddTypeInfo(pParse
, p
);
5077 ** Reset the aggregate accumulator.
5079 ** The aggregate accumulator is a set of memory cells that hold
5080 ** intermediate results while calculating an aggregate. This
5081 ** routine generates code that stores NULLs in all of those memory
5084 static void resetAccumulator(Parse
*pParse
, AggInfo
*pAggInfo
){
5085 Vdbe
*v
= pParse
->pVdbe
;
5087 struct AggInfo_func
*pFunc
;
5088 int nReg
= pAggInfo
->nFunc
+ pAggInfo
->nColumn
;
5089 if( nReg
==0 ) return;
5091 /* Verify that all AggInfo registers are within the range specified by
5092 ** AggInfo.mnReg..AggInfo.mxReg */
5093 assert( nReg
==pAggInfo
->mxReg
-pAggInfo
->mnReg
+1 );
5094 for(i
=0; i
<pAggInfo
->nColumn
; i
++){
5095 assert( pAggInfo
->aCol
[i
].iMem
>=pAggInfo
->mnReg
5096 && pAggInfo
->aCol
[i
].iMem
<=pAggInfo
->mxReg
);
5098 for(i
=0; i
<pAggInfo
->nFunc
; i
++){
5099 assert( pAggInfo
->aFunc
[i
].iMem
>=pAggInfo
->mnReg
5100 && pAggInfo
->aFunc
[i
].iMem
<=pAggInfo
->mxReg
);
5103 sqlite3VdbeAddOp3(v
, OP_Null
, 0, pAggInfo
->mnReg
, pAggInfo
->mxReg
);
5104 for(pFunc
=pAggInfo
->aFunc
, i
=0; i
<pAggInfo
->nFunc
; i
++, pFunc
++){
5105 if( pFunc
->iDistinct
>=0 ){
5106 Expr
*pE
= pFunc
->pExpr
;
5107 assert( !ExprHasProperty(pE
, EP_xIsSelect
) );
5108 if( pE
->x
.pList
==0 || pE
->x
.pList
->nExpr
!=1 ){
5109 sqlite3ErrorMsg(pParse
, "DISTINCT aggregates must have exactly one "
5111 pFunc
->iDistinct
= -1;
5113 KeyInfo
*pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
, pE
->x
.pList
,0,0);
5114 sqlite3VdbeAddOp4(v
, OP_OpenEphemeral
, pFunc
->iDistinct
, 0, 0,
5115 (char*)pKeyInfo
, P4_KEYINFO
);
5122 ** Invoke the OP_AggFinalize opcode for every aggregate function
5123 ** in the AggInfo structure.
5125 static void finalizeAggFunctions(Parse
*pParse
, AggInfo
*pAggInfo
){
5126 Vdbe
*v
= pParse
->pVdbe
;
5128 struct AggInfo_func
*pF
;
5129 for(i
=0, pF
=pAggInfo
->aFunc
; i
<pAggInfo
->nFunc
; i
++, pF
++){
5130 ExprList
*pList
= pF
->pExpr
->x
.pList
;
5131 assert( !ExprHasProperty(pF
->pExpr
, EP_xIsSelect
) );
5132 sqlite3VdbeAddOp2(v
, OP_AggFinal
, pF
->iMem
, pList
? pList
->nExpr
: 0);
5133 sqlite3VdbeAppendP4(v
, pF
->pFunc
, P4_FUNCDEF
);
5139 ** Update the accumulator memory cells for an aggregate based on
5140 ** the current cursor position.
5142 ** If regAcc is non-zero and there are no min() or max() aggregates
5143 ** in pAggInfo, then only populate the pAggInfo->nAccumulator accumulator
5144 ** registers i register regAcc contains 0. The caller will take care
5145 ** of setting and clearing regAcc.
5147 static void updateAccumulator(Parse
*pParse
, int regAcc
, AggInfo
*pAggInfo
){
5148 Vdbe
*v
= pParse
->pVdbe
;
5151 int addrHitTest
= 0;
5152 struct AggInfo_func
*pF
;
5153 struct AggInfo_col
*pC
;
5155 pAggInfo
->directMode
= 1;
5156 for(i
=0, pF
=pAggInfo
->aFunc
; i
<pAggInfo
->nFunc
; i
++, pF
++){
5160 ExprList
*pList
= pF
->pExpr
->x
.pList
;
5161 assert( !ExprHasProperty(pF
->pExpr
, EP_xIsSelect
) );
5163 nArg
= pList
->nExpr
;
5164 regAgg
= sqlite3GetTempRange(pParse
, nArg
);
5165 sqlite3ExprCodeExprList(pParse
, pList
, regAgg
, 0, SQLITE_ECEL_DUP
);
5170 if( pF
->iDistinct
>=0 ){
5171 addrNext
= sqlite3VdbeMakeLabel(v
);
5172 testcase( nArg
==0 ); /* Error condition */
5173 testcase( nArg
>1 ); /* Also an error */
5174 codeDistinct(pParse
, pF
->iDistinct
, addrNext
, 1, regAgg
);
5176 if( pF
->pFunc
->funcFlags
& SQLITE_FUNC_NEEDCOLL
){
5178 struct ExprList_item
*pItem
;
5180 assert( pList
!=0 ); /* pList!=0 if pF->pFunc has NEEDCOLL */
5181 for(j
=0, pItem
=pList
->a
; !pColl
&& j
<nArg
; j
++, pItem
++){
5182 pColl
= sqlite3ExprCollSeq(pParse
, pItem
->pExpr
);
5185 pColl
= pParse
->db
->pDfltColl
;
5187 if( regHit
==0 && pAggInfo
->nAccumulator
) regHit
= ++pParse
->nMem
;
5188 sqlite3VdbeAddOp4(v
, OP_CollSeq
, regHit
, 0, 0, (char *)pColl
, P4_COLLSEQ
);
5190 sqlite3VdbeAddOp3(v
, OP_AggStep0
, 0, regAgg
, pF
->iMem
);
5191 sqlite3VdbeAppendP4(v
, pF
->pFunc
, P4_FUNCDEF
);
5192 sqlite3VdbeChangeP5(v
, (u8
)nArg
);
5193 sqlite3ExprCacheAffinityChange(pParse
, regAgg
, nArg
);
5194 sqlite3ReleaseTempRange(pParse
, regAgg
, nArg
);
5196 sqlite3VdbeResolveLabel(v
, addrNext
);
5197 sqlite3ExprCacheClear(pParse
);
5201 /* Before populating the accumulator registers, clear the column cache.
5202 ** Otherwise, if any of the required column values are already present
5203 ** in registers, sqlite3ExprCode() may use OP_SCopy to copy the value
5204 ** to pC->iMem. But by the time the value is used, the original register
5205 ** may have been used, invalidating the underlying buffer holding the
5206 ** text or blob value. See ticket [883034dcb5].
5208 ** Another solution would be to change the OP_SCopy used to copy cached
5209 ** values to an OP_Copy.
5211 if( regHit
==0 && pAggInfo
->nAccumulator
){
5215 addrHitTest
= sqlite3VdbeAddOp1(v
, OP_If
, regHit
); VdbeCoverage(v
);
5217 sqlite3ExprCacheClear(pParse
);
5218 for(i
=0, pC
=pAggInfo
->aCol
; i
<pAggInfo
->nAccumulator
; i
++, pC
++){
5219 sqlite3ExprCode(pParse
, pC
->pExpr
, pC
->iMem
);
5221 pAggInfo
->directMode
= 0;
5222 sqlite3ExprCacheClear(pParse
);
5224 sqlite3VdbeJumpHere(v
, addrHitTest
);
5229 ** Add a single OP_Explain instruction to the VDBE to explain a simple
5230 ** count(*) query ("SELECT count(*) FROM pTab").
5232 #ifndef SQLITE_OMIT_EXPLAIN
5233 static void explainSimpleCount(
5234 Parse
*pParse
, /* Parse context */
5235 Table
*pTab
, /* Table being queried */
5236 Index
*pIdx
/* Index used to optimize scan, or NULL */
5238 if( pParse
->explain
==2 ){
5239 int bCover
= (pIdx
!=0 && (HasRowid(pTab
) || !IsPrimaryKeyIndex(pIdx
)));
5240 sqlite3VdbeExplain(pParse
, 0, "SCAN TABLE %s%s%s",
5242 bCover
? " USING COVERING INDEX " : "",
5243 bCover
? pIdx
->zName
: ""
5248 # define explainSimpleCount(a,b,c)
5252 ** sqlite3WalkExpr() callback used by havingToWhere().
5254 ** If the node passed to the callback is a TK_AND node, return
5255 ** WRC_Continue to tell sqlite3WalkExpr() to iterate through child nodes.
5257 ** Otherwise, return WRC_Prune. In this case, also check if the
5258 ** sub-expression matches the criteria for being moved to the WHERE
5259 ** clause. If so, add it to the WHERE clause and replace the sub-expression
5260 ** within the HAVING expression with a constant "1".
5262 static int havingToWhereExprCb(Walker
*pWalker
, Expr
*pExpr
){
5263 if( pExpr
->op
!=TK_AND
){
5264 Select
*pS
= pWalker
->u
.pSelect
;
5265 if( sqlite3ExprIsConstantOrGroupBy(pWalker
->pParse
, pExpr
, pS
->pGroupBy
) ){
5266 sqlite3
*db
= pWalker
->pParse
->db
;
5267 Expr
*pNew
= sqlite3ExprAlloc(db
, TK_INTEGER
, &sqlite3IntTokens
[1], 0);
5269 Expr
*pWhere
= pS
->pWhere
;
5270 SWAP(Expr
, *pNew
, *pExpr
);
5271 pNew
= sqlite3ExprAnd(db
, pWhere
, pNew
);
5278 return WRC_Continue
;
5282 ** Transfer eligible terms from the HAVING clause of a query, which is
5283 ** processed after grouping, to the WHERE clause, which is processed before
5284 ** grouping. For example, the query:
5286 ** SELECT * FROM <tables> WHERE a=? GROUP BY b HAVING b=? AND c=?
5288 ** can be rewritten as:
5290 ** SELECT * FROM <tables> WHERE a=? AND b=? GROUP BY b HAVING c=?
5292 ** A term of the HAVING expression is eligible for transfer if it consists
5293 ** entirely of constants and expressions that are also GROUP BY terms that
5294 ** use the "BINARY" collation sequence.
5296 static void havingToWhere(Parse
*pParse
, Select
*p
){
5298 memset(&sWalker
, 0, sizeof(sWalker
));
5299 sWalker
.pParse
= pParse
;
5300 sWalker
.xExprCallback
= havingToWhereExprCb
;
5301 sWalker
.u
.pSelect
= p
;
5302 sqlite3WalkExpr(&sWalker
, p
->pHaving
);
5303 #if SELECTTRACE_ENABLED
5304 if( sWalker
.eCode
&& (sqlite3SelectTrace
& 0x100)!=0 ){
5305 SELECTTRACE(0x100,pParse
,p
,("Move HAVING terms into WHERE:\n"));
5306 sqlite3TreeViewSelect(0, p
, 0);
5312 ** Check to see if the pThis entry of pTabList is a self-join of a prior view.
5313 ** If it is, then return the SrcList_item for the prior view. If it is not,
5316 static struct SrcList_item
*isSelfJoinView(
5317 SrcList
*pTabList
, /* Search for self-joins in this FROM clause */
5318 struct SrcList_item
*pThis
/* Search for prior reference to this subquery */
5320 struct SrcList_item
*pItem
;
5321 for(pItem
= pTabList
->a
; pItem
<pThis
; pItem
++){
5322 if( pItem
->pSelect
==0 ) continue;
5323 if( pItem
->fg
.viaCoroutine
) continue;
5324 if( pItem
->zName
==0 ) continue;
5325 if( sqlite3_stricmp(pItem
->zDatabase
, pThis
->zDatabase
)!=0 ) continue;
5326 if( sqlite3_stricmp(pItem
->zName
, pThis
->zName
)!=0 ) continue;
5327 if( sqlite3ExprCompare(0,
5328 pThis
->pSelect
->pWhere
, pItem
->pSelect
->pWhere
, -1)
5330 /* The view was modified by some other optimization such as
5331 ** pushDownWhereTerms() */
5339 #ifdef SQLITE_COUNTOFVIEW_OPTIMIZATION
5341 ** Attempt to transform a query of the form
5343 ** SELECT count(*) FROM (SELECT x FROM t1 UNION ALL SELECT y FROM t2)
5347 ** SELECT (SELECT count(*) FROM t1)+(SELECT count(*) FROM t2)
5349 ** The transformation only works if all of the following are true:
5351 ** * The subquery is a UNION ALL of two or more terms
5352 ** * There is no WHERE or GROUP BY or HAVING clauses on the subqueries
5353 ** * The outer query is a simple count(*)
5355 ** Return TRUE if the optimization is undertaken.
5357 static int countOfViewOptimization(Parse
*pParse
, Select
*p
){
5358 Select
*pSub
, *pPrior
;
5362 if( (p
->selFlags
& SF_Aggregate
)==0 ) return 0; /* This is an aggregate */
5363 if( p
->pEList
->nExpr
!=1 ) return 0; /* Single result column */
5364 pExpr
= p
->pEList
->a
[0].pExpr
;
5365 if( pExpr
->op
!=TK_AGG_FUNCTION
) return 0; /* Result is an aggregate */
5366 if( sqlite3_stricmp(pExpr
->u
.zToken
,"count") ) return 0; /* Is count() */
5367 if( pExpr
->x
.pList
!=0 ) return 0; /* Must be count(*) */
5368 if( p
->pSrc
->nSrc
!=1 ) return 0; /* One table in FROM */
5369 pSub
= p
->pSrc
->a
[0].pSelect
;
5370 if( pSub
==0 ) return 0; /* The FROM is a subquery */
5371 if( pSub
->pPrior
==0 ) return 0; /* Must be a compound ry */
5373 if( pSub
->op
!=TK_ALL
&& pSub
->pPrior
) return 0; /* Must be UNION ALL */
5374 if( pSub
->pWhere
) return 0; /* No WHERE clause */
5375 if( pSub
->selFlags
& SF_Aggregate
) return 0; /* Not an aggregate */
5376 pSub
= pSub
->pPrior
; /* Repeat over compound */
5379 /* If we reach this point then it is OK to perform the transformation */
5384 pSub
= p
->pSrc
->a
[0].pSelect
;
5385 p
->pSrc
->a
[0].pSelect
= 0;
5386 sqlite3SrcListDelete(db
, p
->pSrc
);
5387 p
->pSrc
= sqlite3DbMallocZero(pParse
->db
, sizeof(*p
->pSrc
));
5390 pPrior
= pSub
->pPrior
;
5393 pSub
->selFlags
|= SF_Aggregate
;
5394 pSub
->selFlags
&= ~SF_Compound
;
5395 pSub
->nSelectRow
= 0;
5396 sqlite3ExprListDelete(db
, pSub
->pEList
);
5397 pTerm
= pPrior
? sqlite3ExprDup(db
, pCount
, 0) : pCount
;
5398 pSub
->pEList
= sqlite3ExprListAppend(pParse
, 0, pTerm
);
5399 pTerm
= sqlite3PExpr(pParse
, TK_SELECT
, 0, 0);
5400 sqlite3PExprAddSelect(pParse
, pTerm
, pSub
);
5404 pExpr
= sqlite3PExpr(pParse
, TK_PLUS
, pTerm
, pExpr
);
5408 p
->pEList
->a
[0].pExpr
= pExpr
;
5409 p
->selFlags
&= ~SF_Aggregate
;
5411 #if SELECTTRACE_ENABLED
5412 if( sqlite3SelectTrace
& 0x400 ){
5413 SELECTTRACE(0x400,pParse
,p
,("After count-of-view optimization:\n"));
5414 sqlite3TreeViewSelect(0, p
, 0);
5419 #endif /* SQLITE_COUNTOFVIEW_OPTIMIZATION */
5422 ** Generate code for the SELECT statement given in the p argument.
5424 ** The results are returned according to the SelectDest structure.
5425 ** See comments in sqliteInt.h for further information.
5427 ** This routine returns the number of errors. If any errors are
5428 ** encountered, then an appropriate error message is left in
5431 ** This routine does NOT free the Select structure passed in. The
5432 ** calling function needs to do that.
5435 Parse
*pParse
, /* The parser context */
5436 Select
*p
, /* The SELECT statement being coded. */
5437 SelectDest
*pDest
/* What to do with the query results */
5439 int i
, j
; /* Loop counters */
5440 WhereInfo
*pWInfo
; /* Return from sqlite3WhereBegin() */
5441 Vdbe
*v
; /* The virtual machine under construction */
5442 int isAgg
; /* True for select lists like "count(*)" */
5443 ExprList
*pEList
= 0; /* List of columns to extract. */
5444 SrcList
*pTabList
; /* List of tables to select from */
5445 Expr
*pWhere
; /* The WHERE clause. May be NULL */
5446 ExprList
*pGroupBy
; /* The GROUP BY clause. May be NULL */
5447 Expr
*pHaving
; /* The HAVING clause. May be NULL */
5448 int rc
= 1; /* Value to return from this function */
5449 DistinctCtx sDistinct
; /* Info on how to code the DISTINCT keyword */
5450 SortCtx sSort
; /* Info on how to code the ORDER BY clause */
5451 AggInfo sAggInfo
; /* Information used by aggregate queries */
5452 int iEnd
; /* Address of the end of the query */
5453 sqlite3
*db
; /* The database connection */
5454 ExprList
*pMinMaxOrderBy
= 0; /* Added ORDER BY for min/max queries */
5455 u8 minMaxFlag
; /* Flag for min/max queries */
5458 v
= sqlite3GetVdbe(pParse
);
5459 if( p
==0 || db
->mallocFailed
|| pParse
->nErr
){
5462 if( sqlite3AuthCheck(pParse
, SQLITE_SELECT
, 0, 0, 0) ) return 1;
5463 memset(&sAggInfo
, 0, sizeof(sAggInfo
));
5464 #if SELECTTRACE_ENABLED
5465 SELECTTRACE(1,pParse
,p
, ("begin processing:\n", pParse
->addrExplain
));
5466 if( sqlite3SelectTrace
& 0x100 ){
5467 sqlite3TreeViewSelect(0, p
, 0);
5471 assert( p
->pOrderBy
==0 || pDest
->eDest
!=SRT_DistFifo
);
5472 assert( p
->pOrderBy
==0 || pDest
->eDest
!=SRT_Fifo
);
5473 assert( p
->pOrderBy
==0 || pDest
->eDest
!=SRT_DistQueue
);
5474 assert( p
->pOrderBy
==0 || pDest
->eDest
!=SRT_Queue
);
5475 if( IgnorableOrderby(pDest
) ){
5476 assert(pDest
->eDest
==SRT_Exists
|| pDest
->eDest
==SRT_Union
||
5477 pDest
->eDest
==SRT_Except
|| pDest
->eDest
==SRT_Discard
||
5478 pDest
->eDest
==SRT_Queue
|| pDest
->eDest
==SRT_DistFifo
||
5479 pDest
->eDest
==SRT_DistQueue
|| pDest
->eDest
==SRT_Fifo
);
5480 /* If ORDER BY makes no difference in the output then neither does
5481 ** DISTINCT so it can be removed too. */
5482 sqlite3ExprListDelete(db
, p
->pOrderBy
);
5484 p
->selFlags
&= ~SF_Distinct
;
5486 sqlite3SelectPrep(pParse
, p
, 0);
5487 memset(&sSort
, 0, sizeof(sSort
));
5488 sSort
.pOrderBy
= p
->pOrderBy
;
5489 if( pParse
->nErr
|| db
->mallocFailed
){
5492 assert( p
->pEList
!=0 );
5493 #if SELECTTRACE_ENABLED
5494 if( sqlite3SelectTrace
& 0x104 ){
5495 SELECTTRACE(0x104,pParse
,p
, ("after name resolution:\n"));
5496 sqlite3TreeViewSelect(0, p
, 0);
5500 if( pDest
->eDest
==SRT_Output
){
5501 generateColumnNames(pParse
, p
);
5504 #ifndef SQLITE_OMIT_WINDOWFUNC
5505 if( sqlite3WindowRewrite(pParse
, p
) ){
5508 #if SELECTTRACE_ENABLED
5509 if( sqlite3SelectTrace
& 0x108 ){
5510 SELECTTRACE(0x104,pParse
,p
, ("after window rewrite:\n"));
5511 sqlite3TreeViewSelect(0, p
, 0);
5514 #endif /* SQLITE_OMIT_WINDOWFUNC */
5516 isAgg
= (p
->selFlags
& SF_Aggregate
)!=0;
5518 /* Try to various optimizations (flattening subqueries, and strength
5519 ** reduction of join operators) in the FROM clause up into the main query
5521 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
5522 for(i
=0; !p
->pPrior
&& i
<pTabList
->nSrc
; i
++){
5523 struct SrcList_item
*pItem
= &pTabList
->a
[i
];
5524 Select
*pSub
= pItem
->pSelect
;
5525 Table
*pTab
= pItem
->pTab
;
5527 /* Convert LEFT JOIN into JOIN if there are terms of the right table
5528 ** of the LEFT JOIN used in the WHERE clause.
5530 if( (pItem
->fg
.jointype
& JT_LEFT
)!=0
5531 && sqlite3ExprImpliesNonNullRow(p
->pWhere
, pItem
->iCursor
)
5532 && OptimizationEnabled(db
, SQLITE_SimplifyJoin
)
5534 SELECTTRACE(0x100,pParse
,p
,
5535 ("LEFT-JOIN simplifies to JOIN on term %d\n",i
));
5536 pItem
->fg
.jointype
&= ~(JT_LEFT
|JT_OUTER
);
5537 unsetJoinExpr(p
->pWhere
, pItem
->iCursor
);
5540 /* No futher action if this term of the FROM clause is no a subquery */
5541 if( pSub
==0 ) continue;
5543 /* Catch mismatch in the declared columns of a view and the number of
5544 ** columns in the SELECT on the RHS */
5545 if( pTab
->nCol
!=pSub
->pEList
->nExpr
){
5546 sqlite3ErrorMsg(pParse
, "expected %d columns for '%s' but got %d",
5547 pTab
->nCol
, pTab
->zName
, pSub
->pEList
->nExpr
);
5551 /* Do not try to flatten an aggregate subquery.
5553 ** Flattening an aggregate subquery is only possible if the outer query
5554 ** is not a join. But if the outer query is not a join, then the subquery
5555 ** will be implemented as a co-routine and there is no advantage to
5556 ** flattening in that case.
5558 if( (pSub
->selFlags
& SF_Aggregate
)!=0 ) continue;
5559 assert( pSub
->pGroupBy
==0 );
5561 /* If the outer query contains a "complex" result set (that is,
5562 ** if the result set of the outer query uses functions or subqueries)
5563 ** and if the subquery contains an ORDER BY clause and if
5564 ** it will be implemented as a co-routine, then do not flatten. This
5565 ** restriction allows SQL constructs like this:
5567 ** SELECT expensive_function(x)
5568 ** FROM (SELECT x FROM tab ORDER BY y LIMIT 10);
5570 ** The expensive_function() is only computed on the 10 rows that
5571 ** are output, rather than every row of the table.
5573 ** The requirement that the outer query have a complex result set
5574 ** means that flattening does occur on simpler SQL constraints without
5575 ** the expensive_function() like:
5577 ** SELECT x FROM (SELECT x FROM tab ORDER BY y LIMIT 10);
5579 if( pSub
->pOrderBy
!=0
5581 && (p
->selFlags
& SF_ComplexResult
)!=0
5582 && (pTabList
->nSrc
==1
5583 || (pTabList
->a
[1].fg
.jointype
&(JT_LEFT
|JT_CROSS
))!=0)
5588 if( flattenSubquery(pParse
, p
, i
, isAgg
) ){
5589 /* This subquery can be absorbed into its parent. */
5593 if( db
->mallocFailed
) goto select_end
;
5594 if( !IgnorableOrderby(pDest
) ){
5595 sSort
.pOrderBy
= p
->pOrderBy
;
5600 #ifndef SQLITE_OMIT_COMPOUND_SELECT
5601 /* Handle compound SELECT statements using the separate multiSelect()
5605 rc
= multiSelect(pParse
, p
, pDest
);
5606 #if SELECTTRACE_ENABLED
5607 SELECTTRACE(0x1,pParse
,p
,("end compound-select processing\n"));
5608 if( (sqlite3SelectTrace
& 0x2000)!=0 && ExplainQueryPlanParent(pParse
)==0 ){
5609 sqlite3TreeViewSelect(0, p
, 0);
5612 if( p
->pNext
==0 ) ExplainQueryPlanPop(pParse
);
5617 /* For each term in the FROM clause, do two things:
5618 ** (1) Authorized unreferenced tables
5619 ** (2) Generate code for all sub-queries
5621 for(i
=0; i
<pTabList
->nSrc
; i
++){
5622 struct SrcList_item
*pItem
= &pTabList
->a
[i
];
5625 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
5626 const char *zSavedAuthContext
;
5629 /* Issue SQLITE_READ authorizations with a fake column name for any
5630 ** tables that are referenced but from which no values are extracted.
5631 ** Examples of where these kinds of null SQLITE_READ authorizations
5634 ** SELECT count(*) FROM t1; -- SQLITE_READ t1.""
5635 ** SELECT t1.* FROM t1, t2; -- SQLITE_READ t2.""
5637 ** The fake column name is an empty string. It is possible for a table to
5638 ** have a column named by the empty string, in which case there is no way to
5639 ** distinguish between an unreferenced table and an actual reference to the
5640 ** "" column. The original design was for the fake column name to be a NULL,
5641 ** which would be unambiguous. But legacy authorization callbacks might
5642 ** assume the column name is non-NULL and segfault. The use of an empty
5643 ** string for the fake column name seems safer.
5645 if( pItem
->colUsed
==0 ){
5646 sqlite3AuthCheck(pParse
, SQLITE_READ
, pItem
->zName
, "", pItem
->zDatabase
);
5649 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
5650 /* Generate code for all sub-queries in the FROM clause
5652 pSub
= pItem
->pSelect
;
5653 if( pSub
==0 ) continue;
5655 /* Sometimes the code for a subquery will be generated more than
5656 ** once, if the subquery is part of the WHERE clause in a LEFT JOIN,
5657 ** for example. In that case, do not regenerate the code to manifest
5658 ** a view or the co-routine to implement a view. The first instance
5659 ** is sufficient, though the subroutine to manifest the view does need
5660 ** to be invoked again. */
5661 if( pItem
->addrFillSub
){
5662 if( pItem
->fg
.viaCoroutine
==0 ){
5663 /* The subroutine that manifests the view might be a one-time routine,
5664 ** or it might need to be rerun on each iteration because it
5665 ** encodes a correlated subquery. */
5666 testcase( sqlite3VdbeGetOp(v
, pItem
->addrFillSub
)->opcode
==OP_Once
);
5667 sqlite3VdbeAddOp2(v
, OP_Gosub
, pItem
->regReturn
, pItem
->addrFillSub
);
5672 /* Increment Parse.nHeight by the height of the largest expression
5673 ** tree referred to by this, the parent select. The child select
5674 ** may contain expression trees of at most
5675 ** (SQLITE_MAX_EXPR_DEPTH-Parse.nHeight) height. This is a bit
5676 ** more conservative than necessary, but much easier than enforcing
5679 pParse
->nHeight
+= sqlite3SelectExprHeight(p
);
5681 /* Make copies of constant WHERE-clause terms in the outer query down
5682 ** inside the subquery. This can help the subquery to run more efficiently.
5684 if( OptimizationEnabled(db
, SQLITE_PushDown
)
5685 && pushDownWhereTerms(pParse
, pSub
, p
->pWhere
, pItem
->iCursor
,
5686 (pItem
->fg
.jointype
& JT_OUTER
)!=0)
5688 #if SELECTTRACE_ENABLED
5689 if( sqlite3SelectTrace
& 0x100 ){
5690 SELECTTRACE(0x100,pParse
,p
,("After WHERE-clause push-down:\n"));
5691 sqlite3TreeViewSelect(0, p
, 0);
5695 SELECTTRACE(0x100,pParse
,p
,("Push-down not possible\n"));
5698 zSavedAuthContext
= pParse
->zAuthContext
;
5699 pParse
->zAuthContext
= pItem
->zName
;
5701 /* Generate code to implement the subquery
5703 ** The subquery is implemented as a co-routine if the subquery is
5704 ** guaranteed to be the outer loop (so that it does not need to be
5705 ** computed more than once)
5707 ** TODO: Are there other reasons beside (1) to use a co-routine
5711 && (pTabList
->nSrc
==1
5712 || (pTabList
->a
[1].fg
.jointype
&(JT_LEFT
|JT_CROSS
))!=0) /* (1) */
5714 /* Implement a co-routine that will return a single row of the result
5715 ** set on each invocation.
5717 int addrTop
= sqlite3VdbeCurrentAddr(v
)+1;
5719 pItem
->regReturn
= ++pParse
->nMem
;
5720 sqlite3VdbeAddOp3(v
, OP_InitCoroutine
, pItem
->regReturn
, 0, addrTop
);
5721 VdbeComment((v
, "%s", pItem
->pTab
->zName
));
5722 pItem
->addrFillSub
= addrTop
;
5723 sqlite3SelectDestInit(&dest
, SRT_Coroutine
, pItem
->regReturn
);
5724 ExplainQueryPlan((pParse
, 1, "CO-ROUTINE 0x%p", pSub
));
5725 sqlite3Select(pParse
, pSub
, &dest
);
5726 pItem
->pTab
->nRowLogEst
= pSub
->nSelectRow
;
5727 pItem
->fg
.viaCoroutine
= 1;
5728 pItem
->regResult
= dest
.iSdst
;
5729 sqlite3VdbeEndCoroutine(v
, pItem
->regReturn
);
5730 sqlite3VdbeJumpHere(v
, addrTop
-1);
5731 sqlite3ClearTempRegCache(pParse
);
5733 /* Generate a subroutine that will fill an ephemeral table with
5734 ** the content of this subquery. pItem->addrFillSub will point
5735 ** to the address of the generated subroutine. pItem->regReturn
5736 ** is a register allocated to hold the subroutine return address
5741 struct SrcList_item
*pPrior
;
5743 assert( pItem
->addrFillSub
==0 );
5744 pItem
->regReturn
= ++pParse
->nMem
;
5745 topAddr
= sqlite3VdbeAddOp2(v
, OP_Integer
, 0, pItem
->regReturn
);
5746 pItem
->addrFillSub
= topAddr
+1;
5747 if( pItem
->fg
.isCorrelated
==0 ){
5748 /* If the subquery is not correlated and if we are not inside of
5749 ** a trigger, then we only need to compute the value of the subquery
5751 onceAddr
= sqlite3VdbeAddOp0(v
, OP_Once
); VdbeCoverage(v
);
5752 VdbeComment((v
, "materialize \"%s\"", pItem
->pTab
->zName
));
5754 VdbeNoopComment((v
, "materialize \"%s\"", pItem
->pTab
->zName
));
5756 pPrior
= isSelfJoinView(pTabList
, pItem
);
5758 sqlite3VdbeAddOp2(v
, OP_OpenDup
, pItem
->iCursor
, pPrior
->iCursor
);
5759 assert( pPrior
->pSelect
!=0 );
5760 pSub
->nSelectRow
= pPrior
->pSelect
->nSelectRow
;
5762 sqlite3SelectDestInit(&dest
, SRT_EphemTab
, pItem
->iCursor
);
5763 ExplainQueryPlan((pParse
, 1, "MATERIALIZE 0x%p", pSub
));
5764 sqlite3Select(pParse
, pSub
, &dest
);
5766 pItem
->pTab
->nRowLogEst
= pSub
->nSelectRow
;
5767 if( onceAddr
) sqlite3VdbeJumpHere(v
, onceAddr
);
5768 retAddr
= sqlite3VdbeAddOp1(v
, OP_Return
, pItem
->regReturn
);
5769 VdbeComment((v
, "end %s", pItem
->pTab
->zName
));
5770 sqlite3VdbeChangeP1(v
, topAddr
, retAddr
);
5771 sqlite3ClearTempRegCache(pParse
);
5773 if( db
->mallocFailed
) goto select_end
;
5774 pParse
->nHeight
-= sqlite3SelectExprHeight(p
);
5775 pParse
->zAuthContext
= zSavedAuthContext
;
5779 /* Various elements of the SELECT copied into local variables for
5783 pGroupBy
= p
->pGroupBy
;
5784 pHaving
= p
->pHaving
;
5785 sDistinct
.isTnct
= (p
->selFlags
& SF_Distinct
)!=0;
5787 #if SELECTTRACE_ENABLED
5788 if( sqlite3SelectTrace
& 0x400 ){
5789 SELECTTRACE(0x400,pParse
,p
,("After all FROM-clause analysis:\n"));
5790 sqlite3TreeViewSelect(0, p
, 0);
5794 #ifdef SQLITE_COUNTOFVIEW_OPTIMIZATION
5795 if( OptimizationEnabled(db
, SQLITE_QueryFlattener
|SQLITE_CountOfView
)
5796 && countOfViewOptimization(pParse
, p
)
5798 if( db
->mallocFailed
) goto select_end
;
5804 /* If the query is DISTINCT with an ORDER BY but is not an aggregate, and
5805 ** if the select-list is the same as the ORDER BY list, then this query
5806 ** can be rewritten as a GROUP BY. In other words, this:
5808 ** SELECT DISTINCT xyz FROM ... ORDER BY xyz
5810 ** is transformed to:
5812 ** SELECT xyz FROM ... GROUP BY xyz ORDER BY xyz
5814 ** The second form is preferred as a single index (or temp-table) may be
5815 ** used for both the ORDER BY and DISTINCT processing. As originally
5816 ** written the query must use a temp-table for at least one of the ORDER
5817 ** BY and DISTINCT, and an index or separate temp-table for the other.
5819 if( (p
->selFlags
& (SF_Distinct
|SF_Aggregate
))==SF_Distinct
5820 && sqlite3ExprListCompare(sSort
.pOrderBy
, pEList
, -1)==0
5822 p
->selFlags
&= ~SF_Distinct
;
5823 pGroupBy
= p
->pGroupBy
= sqlite3ExprListDup(db
, pEList
, 0);
5824 /* Notice that even thought SF_Distinct has been cleared from p->selFlags,
5825 ** the sDistinct.isTnct is still set. Hence, isTnct represents the
5826 ** original setting of the SF_Distinct flag, not the current setting */
5827 assert( sDistinct
.isTnct
);
5829 #if SELECTTRACE_ENABLED
5830 if( sqlite3SelectTrace
& 0x400 ){
5831 SELECTTRACE(0x400,pParse
,p
,("Transform DISTINCT into GROUP BY:\n"));
5832 sqlite3TreeViewSelect(0, p
, 0);
5837 /* If there is an ORDER BY clause, then create an ephemeral index to
5838 ** do the sorting. But this sorting ephemeral index might end up
5839 ** being unused if the data can be extracted in pre-sorted order.
5840 ** If that is the case, then the OP_OpenEphemeral instruction will be
5841 ** changed to an OP_Noop once we figure out that the sorting index is
5842 ** not needed. The sSort.addrSortIndex variable is used to facilitate
5845 if( sSort
.pOrderBy
){
5847 pKeyInfo
= sqlite3KeyInfoFromExprList(
5848 pParse
, sSort
.pOrderBy
, 0, pEList
->nExpr
);
5849 sSort
.iECursor
= pParse
->nTab
++;
5850 sSort
.addrSortIndex
=
5851 sqlite3VdbeAddOp4(v
, OP_OpenEphemeral
,
5852 sSort
.iECursor
, sSort
.pOrderBy
->nExpr
+1+pEList
->nExpr
, 0,
5853 (char*)pKeyInfo
, P4_KEYINFO
5856 sSort
.addrSortIndex
= -1;
5859 /* If the output is destined for a temporary table, open that table.
5861 if( pDest
->eDest
==SRT_EphemTab
){
5862 sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, pDest
->iSDParm
, pEList
->nExpr
);
5867 iEnd
= sqlite3VdbeMakeLabel(v
);
5868 if( (p
->selFlags
& SF_FixedLimit
)==0 ){
5869 p
->nSelectRow
= 320; /* 4 billion rows */
5871 computeLimitRegisters(pParse
, p
, iEnd
);
5872 if( p
->iLimit
==0 && sSort
.addrSortIndex
>=0 ){
5873 sqlite3VdbeChangeOpcode(v
, sSort
.addrSortIndex
, OP_SorterOpen
);
5874 sSort
.sortFlags
|= SORTFLAG_UseSorter
;
5877 /* Open an ephemeral index to use for the distinct set.
5879 if( p
->selFlags
& SF_Distinct
){
5880 sDistinct
.tabTnct
= pParse
->nTab
++;
5881 sDistinct
.addrTnct
= sqlite3VdbeAddOp4(v
, OP_OpenEphemeral
,
5882 sDistinct
.tabTnct
, 0, 0,
5883 (char*)sqlite3KeyInfoFromExprList(pParse
, p
->pEList
,0,0),
5885 sqlite3VdbeChangeP5(v
, BTREE_UNORDERED
);
5886 sDistinct
.eTnctType
= WHERE_DISTINCT_UNORDERED
;
5888 sDistinct
.eTnctType
= WHERE_DISTINCT_NOOP
;
5891 if( !isAgg
&& pGroupBy
==0 ){
5892 /* No aggregate functions and no GROUP BY clause */
5893 u16 wctrlFlags
= (sDistinct
.isTnct
? WHERE_WANT_DISTINCT
: 0)
5894 | (p
->selFlags
& SF_FixedLimit
);
5895 #ifndef SQLITE_OMIT_WINDOWFUNC
5896 Window
*pWin
= p
->pWin
; /* Master window object (or NULL) */
5898 sqlite3WindowCodeInit(pParse
, pWin
);
5901 assert( WHERE_USE_LIMIT
==SF_FixedLimit
);
5904 /* Begin the database scan. */
5905 SELECTTRACE(1,pParse
,p
,("WhereBegin\n"));
5906 pWInfo
= sqlite3WhereBegin(pParse
, pTabList
, pWhere
, sSort
.pOrderBy
,
5907 p
->pEList
, wctrlFlags
, p
->nSelectRow
);
5908 if( pWInfo
==0 ) goto select_end
;
5909 if( sqlite3WhereOutputRowCount(pWInfo
) < p
->nSelectRow
){
5910 p
->nSelectRow
= sqlite3WhereOutputRowCount(pWInfo
);
5912 if( sDistinct
.isTnct
&& sqlite3WhereIsDistinct(pWInfo
) ){
5913 sDistinct
.eTnctType
= sqlite3WhereIsDistinct(pWInfo
);
5915 if( sSort
.pOrderBy
){
5916 sSort
.nOBSat
= sqlite3WhereIsOrdered(pWInfo
);
5917 sSort
.bOrderedInnerLoop
= sqlite3WhereOrderedInnerLoop(pWInfo
);
5918 if( sSort
.nOBSat
==sSort
.pOrderBy
->nExpr
){
5923 /* If sorting index that was created by a prior OP_OpenEphemeral
5924 ** instruction ended up not being needed, then change the OP_OpenEphemeral
5927 if( sSort
.addrSortIndex
>=0 && sSort
.pOrderBy
==0 ){
5928 sqlite3VdbeChangeToNoop(v
, sSort
.addrSortIndex
);
5931 assert( p
->pEList
==pEList
);
5932 #ifndef SQLITE_OMIT_WINDOWFUNC
5934 int addrGosub
= sqlite3VdbeMakeLabel(v
);
5935 int iCont
= sqlite3VdbeMakeLabel(v
);
5936 int regGosub
= ++pParse
->nMem
;
5939 sqlite3WindowCodeStep(pParse
, p
, pWInfo
, regGosub
, addrGosub
);
5941 addr
= sqlite3VdbeAddOp0(v
, OP_Goto
);
5942 sqlite3VdbeResolveLabel(v
, addrGosub
);
5943 selectInnerLoop(pParse
, p
, -1, &sSort
, &sDistinct
, pDest
, iCont
, 0);
5944 sqlite3VdbeResolveLabel(v
, iCont
);
5945 sqlite3VdbeAddOp1(v
, OP_Return
, regGosub
);
5946 sqlite3VdbeJumpHere(v
, addr
);
5949 #endif /* SQLITE_OMIT_WINDOWFUNC */
5951 /* Use the standard inner loop. */
5952 selectInnerLoop(pParse
, p
, -1, &sSort
, &sDistinct
, pDest
,
5953 sqlite3WhereContinueLabel(pWInfo
),
5954 sqlite3WhereBreakLabel(pWInfo
));
5956 /* End the database scan loop.
5958 sqlite3WhereEnd(pWInfo
);
5961 /* This case when there exist aggregate functions or a GROUP BY clause
5963 NameContext sNC
; /* Name context for processing aggregate information */
5964 int iAMem
; /* First Mem address for storing current GROUP BY */
5965 int iBMem
; /* First Mem address for previous GROUP BY */
5966 int iUseFlag
; /* Mem address holding flag indicating that at least
5967 ** one row of the input to the aggregator has been
5969 int iAbortFlag
; /* Mem address which causes query abort if positive */
5970 int groupBySort
; /* Rows come from source in GROUP BY order */
5971 int addrEnd
; /* End of processing for this SELECT */
5972 int sortPTab
= 0; /* Pseudotable used to decode sorting results */
5973 int sortOut
= 0; /* Output register from the sorter */
5974 int orderByGrp
= 0; /* True if the GROUP BY and ORDER BY are the same */
5976 /* Remove any and all aliases between the result set and the
5980 int k
; /* Loop counter */
5981 struct ExprList_item
*pItem
; /* For looping over expression in a list */
5983 for(k
=p
->pEList
->nExpr
, pItem
=p
->pEList
->a
; k
>0; k
--, pItem
++){
5984 pItem
->u
.x
.iAlias
= 0;
5986 for(k
=pGroupBy
->nExpr
, pItem
=pGroupBy
->a
; k
>0; k
--, pItem
++){
5987 pItem
->u
.x
.iAlias
= 0;
5989 assert( 66==sqlite3LogEst(100) );
5990 if( p
->nSelectRow
>66 ) p
->nSelectRow
= 66;
5992 assert( 0==sqlite3LogEst(1) );
5996 /* If there is both a GROUP BY and an ORDER BY clause and they are
5997 ** identical, then it may be possible to disable the ORDER BY clause
5998 ** on the grounds that the GROUP BY will cause elements to come out
5999 ** in the correct order. It also may not - the GROUP BY might use a
6000 ** database index that causes rows to be grouped together as required
6001 ** but not actually sorted. Either way, record the fact that the
6002 ** ORDER BY and GROUP BY clauses are the same by setting the orderByGrp
6004 if( sqlite3ExprListCompare(pGroupBy
, sSort
.pOrderBy
, -1)==0 ){
6008 /* Create a label to jump to when we want to abort the query */
6009 addrEnd
= sqlite3VdbeMakeLabel(v
);
6011 /* Convert TK_COLUMN nodes into TK_AGG_COLUMN and make entries in
6012 ** sAggInfo for all TK_AGG_FUNCTION nodes in expressions of the
6013 ** SELECT statement.
6015 memset(&sNC
, 0, sizeof(sNC
));
6016 sNC
.pParse
= pParse
;
6017 sNC
.pSrcList
= pTabList
;
6018 sNC
.uNC
.pAggInfo
= &sAggInfo
;
6019 VVA_ONLY( sNC
.ncFlags
= NC_UAggInfo
; )
6020 sAggInfo
.mnReg
= pParse
->nMem
+1;
6021 sAggInfo
.nSortingColumn
= pGroupBy
? pGroupBy
->nExpr
: 0;
6022 sAggInfo
.pGroupBy
= pGroupBy
;
6023 sqlite3ExprAnalyzeAggList(&sNC
, pEList
);
6024 sqlite3ExprAnalyzeAggList(&sNC
, sSort
.pOrderBy
);
6027 assert( pWhere
==p
->pWhere
);
6028 assert( pHaving
==p
->pHaving
);
6029 assert( pGroupBy
==p
->pGroupBy
);
6030 havingToWhere(pParse
, p
);
6033 sqlite3ExprAnalyzeAggregates(&sNC
, pHaving
);
6035 sAggInfo
.nAccumulator
= sAggInfo
.nColumn
;
6036 if( p
->pGroupBy
==0 && p
->pHaving
==0 && sAggInfo
.nFunc
==1 ){
6037 minMaxFlag
= minMaxQuery(db
, sAggInfo
.aFunc
[0].pExpr
, &pMinMaxOrderBy
);
6039 minMaxFlag
= WHERE_ORDERBY_NORMAL
;
6041 for(i
=0; i
<sAggInfo
.nFunc
; i
++){
6042 assert( !ExprHasProperty(sAggInfo
.aFunc
[i
].pExpr
, EP_xIsSelect
) );
6043 sNC
.ncFlags
|= NC_InAggFunc
;
6044 sqlite3ExprAnalyzeAggList(&sNC
, sAggInfo
.aFunc
[i
].pExpr
->x
.pList
);
6045 sNC
.ncFlags
&= ~NC_InAggFunc
;
6047 sAggInfo
.mxReg
= pParse
->nMem
;
6048 if( db
->mallocFailed
) goto select_end
;
6049 #if SELECTTRACE_ENABLED
6050 if( sqlite3SelectTrace
& 0x400 ){
6052 SELECTTRACE(0x400,pParse
,p
,("After aggregate analysis:\n"));
6053 sqlite3TreeViewSelect(0, p
, 0);
6054 for(ii
=0; ii
<sAggInfo
.nColumn
; ii
++){
6055 sqlite3DebugPrintf("agg-column[%d] iMem=%d\n",
6056 ii
, sAggInfo
.aCol
[ii
].iMem
);
6057 sqlite3TreeViewExpr(0, sAggInfo
.aCol
[ii
].pExpr
, 0);
6059 for(ii
=0; ii
<sAggInfo
.nFunc
; ii
++){
6060 sqlite3DebugPrintf("agg-func[%d]: iMem=%d\n",
6061 ii
, sAggInfo
.aFunc
[ii
].iMem
);
6062 sqlite3TreeViewExpr(0, sAggInfo
.aFunc
[ii
].pExpr
, 0);
6068 /* Processing for aggregates with GROUP BY is very different and
6069 ** much more complex than aggregates without a GROUP BY.
6072 KeyInfo
*pKeyInfo
; /* Keying information for the group by clause */
6073 int addr1
; /* A-vs-B comparision jump */
6074 int addrOutputRow
; /* Start of subroutine that outputs a result row */
6075 int regOutputRow
; /* Return address register for output subroutine */
6076 int addrSetAbort
; /* Set the abort flag and return */
6077 int addrTopOfLoop
; /* Top of the input loop */
6078 int addrSortingIdx
; /* The OP_OpenEphemeral for the sorting index */
6079 int addrReset
; /* Subroutine for resetting the accumulator */
6080 int regReset
; /* Return address register for reset subroutine */
6082 /* If there is a GROUP BY clause we might need a sorting index to
6083 ** implement it. Allocate that sorting index now. If it turns out
6084 ** that we do not need it after all, the OP_SorterOpen instruction
6085 ** will be converted into a Noop.
6087 sAggInfo
.sortingIdx
= pParse
->nTab
++;
6088 pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
,pGroupBy
,0,sAggInfo
.nColumn
);
6089 addrSortingIdx
= sqlite3VdbeAddOp4(v
, OP_SorterOpen
,
6090 sAggInfo
.sortingIdx
, sAggInfo
.nSortingColumn
,
6091 0, (char*)pKeyInfo
, P4_KEYINFO
);
6093 /* Initialize memory locations used by GROUP BY aggregate processing
6095 iUseFlag
= ++pParse
->nMem
;
6096 iAbortFlag
= ++pParse
->nMem
;
6097 regOutputRow
= ++pParse
->nMem
;
6098 addrOutputRow
= sqlite3VdbeMakeLabel(v
);
6099 regReset
= ++pParse
->nMem
;
6100 addrReset
= sqlite3VdbeMakeLabel(v
);
6101 iAMem
= pParse
->nMem
+ 1;
6102 pParse
->nMem
+= pGroupBy
->nExpr
;
6103 iBMem
= pParse
->nMem
+ 1;
6104 pParse
->nMem
+= pGroupBy
->nExpr
;
6105 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, iAbortFlag
);
6106 VdbeComment((v
, "clear abort flag"));
6107 sqlite3VdbeAddOp3(v
, OP_Null
, 0, iAMem
, iAMem
+pGroupBy
->nExpr
-1);
6109 /* Begin a loop that will extract all source rows in GROUP BY order.
6110 ** This might involve two separate loops with an OP_Sort in between, or
6111 ** it might be a single loop that uses an index to extract information
6112 ** in the right order to begin with.
6114 sqlite3VdbeAddOp2(v
, OP_Gosub
, regReset
, addrReset
);
6115 SELECTTRACE(1,pParse
,p
,("WhereBegin\n"));
6116 pWInfo
= sqlite3WhereBegin(pParse
, pTabList
, pWhere
, pGroupBy
, 0,
6117 WHERE_GROUPBY
| (orderByGrp
? WHERE_SORTBYGROUP
: 0), 0
6119 if( pWInfo
==0 ) goto select_end
;
6120 if( sqlite3WhereIsOrdered(pWInfo
)==pGroupBy
->nExpr
){
6121 /* The optimizer is able to deliver rows in group by order so
6122 ** we do not have to sort. The OP_OpenEphemeral table will be
6123 ** cancelled later because we still need to use the pKeyInfo
6127 /* Rows are coming out in undetermined order. We have to push
6128 ** each row into a sorting index, terminate the first loop,
6129 ** then loop over the sorting index in order to get the output
6137 explainTempTable(pParse
,
6138 (sDistinct
.isTnct
&& (p
->selFlags
&SF_Distinct
)==0) ?
6139 "DISTINCT" : "GROUP BY");
6142 nGroupBy
= pGroupBy
->nExpr
;
6145 for(i
=0; i
<sAggInfo
.nColumn
; i
++){
6146 if( sAggInfo
.aCol
[i
].iSorterColumn
>=j
){
6151 regBase
= sqlite3GetTempRange(pParse
, nCol
);
6152 sqlite3ExprCacheClear(pParse
);
6153 sqlite3ExprCodeExprList(pParse
, pGroupBy
, regBase
, 0, 0);
6155 for(i
=0; i
<sAggInfo
.nColumn
; i
++){
6156 struct AggInfo_col
*pCol
= &sAggInfo
.aCol
[i
];
6157 if( pCol
->iSorterColumn
>=j
){
6158 int r1
= j
+ regBase
;
6159 sqlite3ExprCodeGetColumnToReg(pParse
,
6160 pCol
->pTab
, pCol
->iColumn
, pCol
->iTable
, r1
);
6164 regRecord
= sqlite3GetTempReg(pParse
);
6165 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, regBase
, nCol
, regRecord
);
6166 sqlite3VdbeAddOp2(v
, OP_SorterInsert
, sAggInfo
.sortingIdx
, regRecord
);
6167 sqlite3ReleaseTempReg(pParse
, regRecord
);
6168 sqlite3ReleaseTempRange(pParse
, regBase
, nCol
);
6169 sqlite3WhereEnd(pWInfo
);
6170 sAggInfo
.sortingIdxPTab
= sortPTab
= pParse
->nTab
++;
6171 sortOut
= sqlite3GetTempReg(pParse
);
6172 sqlite3VdbeAddOp3(v
, OP_OpenPseudo
, sortPTab
, sortOut
, nCol
);
6173 sqlite3VdbeAddOp2(v
, OP_SorterSort
, sAggInfo
.sortingIdx
, addrEnd
);
6174 VdbeComment((v
, "GROUP BY sort")); VdbeCoverage(v
);
6175 sAggInfo
.useSortingIdx
= 1;
6176 sqlite3ExprCacheClear(pParse
);
6180 /* If the index or temporary table used by the GROUP BY sort
6181 ** will naturally deliver rows in the order required by the ORDER BY
6182 ** clause, cancel the ephemeral table open coded earlier.
6184 ** This is an optimization - the correct answer should result regardless.
6185 ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER to
6186 ** disable this optimization for testing purposes. */
6187 if( orderByGrp
&& OptimizationEnabled(db
, SQLITE_GroupByOrder
)
6188 && (groupBySort
|| sqlite3WhereIsSorted(pWInfo
))
6191 sqlite3VdbeChangeToNoop(v
, sSort
.addrSortIndex
);
6194 /* Evaluate the current GROUP BY terms and store in b0, b1, b2...
6195 ** (b0 is memory location iBMem+0, b1 is iBMem+1, and so forth)
6196 ** Then compare the current GROUP BY terms against the GROUP BY terms
6197 ** from the previous row currently stored in a0, a1, a2...
6199 addrTopOfLoop
= sqlite3VdbeCurrentAddr(v
);
6200 sqlite3ExprCacheClear(pParse
);
6202 sqlite3VdbeAddOp3(v
, OP_SorterData
, sAggInfo
.sortingIdx
,
6205 for(j
=0; j
<pGroupBy
->nExpr
; j
++){
6207 sqlite3VdbeAddOp3(v
, OP_Column
, sortPTab
, j
, iBMem
+j
);
6209 sAggInfo
.directMode
= 1;
6210 sqlite3ExprCode(pParse
, pGroupBy
->a
[j
].pExpr
, iBMem
+j
);
6213 sqlite3VdbeAddOp4(v
, OP_Compare
, iAMem
, iBMem
, pGroupBy
->nExpr
,
6214 (char*)sqlite3KeyInfoRef(pKeyInfo
), P4_KEYINFO
);
6215 addr1
= sqlite3VdbeCurrentAddr(v
);
6216 sqlite3VdbeAddOp3(v
, OP_Jump
, addr1
+1, 0, addr1
+1); VdbeCoverage(v
);
6218 /* Generate code that runs whenever the GROUP BY changes.
6219 ** Changes in the GROUP BY are detected by the previous code
6220 ** block. If there were no changes, this block is skipped.
6222 ** This code copies current group by terms in b0,b1,b2,...
6223 ** over to a0,a1,a2. It then calls the output subroutine
6224 ** and resets the aggregate accumulator registers in preparation
6225 ** for the next GROUP BY batch.
6227 sqlite3ExprCodeMove(pParse
, iBMem
, iAMem
, pGroupBy
->nExpr
);
6228 sqlite3VdbeAddOp2(v
, OP_Gosub
, regOutputRow
, addrOutputRow
);
6229 VdbeComment((v
, "output one row"));
6230 sqlite3VdbeAddOp2(v
, OP_IfPos
, iAbortFlag
, addrEnd
); VdbeCoverage(v
);
6231 VdbeComment((v
, "check abort flag"));
6232 sqlite3VdbeAddOp2(v
, OP_Gosub
, regReset
, addrReset
);
6233 VdbeComment((v
, "reset accumulator"));
6235 /* Update the aggregate accumulators based on the content of
6238 sqlite3VdbeJumpHere(v
, addr1
);
6239 updateAccumulator(pParse
, iUseFlag
, &sAggInfo
);
6240 sqlite3VdbeAddOp2(v
, OP_Integer
, 1, iUseFlag
);
6241 VdbeComment((v
, "indicate data in accumulator"));
6246 sqlite3VdbeAddOp2(v
, OP_SorterNext
, sAggInfo
.sortingIdx
, addrTopOfLoop
);
6249 sqlite3WhereEnd(pWInfo
);
6250 sqlite3VdbeChangeToNoop(v
, addrSortingIdx
);
6253 /* Output the final row of result
6255 sqlite3VdbeAddOp2(v
, OP_Gosub
, regOutputRow
, addrOutputRow
);
6256 VdbeComment((v
, "output final row"));
6258 /* Jump over the subroutines
6260 sqlite3VdbeGoto(v
, addrEnd
);
6262 /* Generate a subroutine that outputs a single row of the result
6263 ** set. This subroutine first looks at the iUseFlag. If iUseFlag
6264 ** is less than or equal to zero, the subroutine is a no-op. If
6265 ** the processing calls for the query to abort, this subroutine
6266 ** increments the iAbortFlag memory location before returning in
6267 ** order to signal the caller to abort.
6269 addrSetAbort
= sqlite3VdbeCurrentAddr(v
);
6270 sqlite3VdbeAddOp2(v
, OP_Integer
, 1, iAbortFlag
);
6271 VdbeComment((v
, "set abort flag"));
6272 sqlite3VdbeAddOp1(v
, OP_Return
, regOutputRow
);
6273 sqlite3VdbeResolveLabel(v
, addrOutputRow
);
6274 addrOutputRow
= sqlite3VdbeCurrentAddr(v
);
6275 sqlite3VdbeAddOp2(v
, OP_IfPos
, iUseFlag
, addrOutputRow
+2);
6277 VdbeComment((v
, "Groupby result generator entry point"));
6278 sqlite3VdbeAddOp1(v
, OP_Return
, regOutputRow
);
6279 finalizeAggFunctions(pParse
, &sAggInfo
);
6280 sqlite3ExprIfFalse(pParse
, pHaving
, addrOutputRow
+1, SQLITE_JUMPIFNULL
);
6281 selectInnerLoop(pParse
, p
, -1, &sSort
,
6283 addrOutputRow
+1, addrSetAbort
);
6284 sqlite3VdbeAddOp1(v
, OP_Return
, regOutputRow
);
6285 VdbeComment((v
, "end groupby result generator"));
6287 /* Generate a subroutine that will reset the group-by accumulator
6289 sqlite3VdbeResolveLabel(v
, addrReset
);
6290 resetAccumulator(pParse
, &sAggInfo
);
6291 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, iUseFlag
);
6292 VdbeComment((v
, "indicate accumulator empty"));
6293 sqlite3VdbeAddOp1(v
, OP_Return
, regReset
);
6295 } /* endif pGroupBy. Begin aggregate queries without GROUP BY: */
6297 #ifndef SQLITE_OMIT_BTREECOUNT
6299 if( (pTab
= isSimpleCount(p
, &sAggInfo
))!=0 ){
6300 /* If isSimpleCount() returns a pointer to a Table structure, then
6301 ** the SQL statement is of the form:
6303 ** SELECT count(*) FROM <tbl>
6305 ** where the Table structure returned represents table <tbl>.
6307 ** This statement is so common that it is optimized specially. The
6308 ** OP_Count instruction is executed either on the intkey table that
6309 ** contains the data for table <tbl> or on one of its indexes. It
6310 ** is better to execute the op on an index, as indexes are almost
6311 ** always spread across less pages than their corresponding tables.
6313 const int iDb
= sqlite3SchemaToIndex(pParse
->db
, pTab
->pSchema
);
6314 const int iCsr
= pParse
->nTab
++; /* Cursor to scan b-tree */
6315 Index
*pIdx
; /* Iterator variable */
6316 KeyInfo
*pKeyInfo
= 0; /* Keyinfo for scanned index */
6317 Index
*pBest
= 0; /* Best index found so far */
6318 int iRoot
= pTab
->tnum
; /* Root page of scanned b-tree */
6320 sqlite3CodeVerifySchema(pParse
, iDb
);
6321 sqlite3TableLock(pParse
, iDb
, pTab
->tnum
, 0, pTab
->zName
);
6323 /* Search for the index that has the lowest scan cost.
6325 ** (2011-04-15) Do not do a full scan of an unordered index.
6327 ** (2013-10-03) Do not count the entries in a partial index.
6329 ** In practice the KeyInfo structure will not be used. It is only
6330 ** passed to keep OP_OpenRead happy.
6332 if( !HasRowid(pTab
) ) pBest
= sqlite3PrimaryKeyIndex(pTab
);
6333 for(pIdx
=pTab
->pIndex
; pIdx
; pIdx
=pIdx
->pNext
){
6334 if( pIdx
->bUnordered
==0
6335 && pIdx
->szIdxRow
<pTab
->szTabRow
6336 && pIdx
->pPartIdxWhere
==0
6337 && (!pBest
|| pIdx
->szIdxRow
<pBest
->szIdxRow
)
6343 iRoot
= pBest
->tnum
;
6344 pKeyInfo
= sqlite3KeyInfoOfIndex(pParse
, pBest
);
6347 /* Open a read-only cursor, execute the OP_Count, close the cursor. */
6348 sqlite3VdbeAddOp4Int(v
, OP_OpenRead
, iCsr
, iRoot
, iDb
, 1);
6350 sqlite3VdbeChangeP4(v
, -1, (char *)pKeyInfo
, P4_KEYINFO
);
6352 sqlite3VdbeAddOp2(v
, OP_Count
, iCsr
, sAggInfo
.aFunc
[0].iMem
);
6353 sqlite3VdbeAddOp1(v
, OP_Close
, iCsr
);
6354 explainSimpleCount(pParse
, pTab
, pBest
);
6356 #endif /* SQLITE_OMIT_BTREECOUNT */
6358 int regAcc
= 0; /* "populate accumulators" flag */
6360 /* If there are accumulator registers but no min() or max() functions,
6361 ** allocate register regAcc. Register regAcc will contain 0 the first
6362 ** time the inner loop runs, and 1 thereafter. The code generated
6363 ** by updateAccumulator() only updates the accumulator registers if
6364 ** regAcc contains 0. */
6365 if( sAggInfo
.nAccumulator
){
6366 for(i
=0; i
<sAggInfo
.nFunc
; i
++){
6367 if( sAggInfo
.aFunc
[i
].pFunc
->funcFlags
&SQLITE_FUNC_NEEDCOLL
) break;
6369 if( i
==sAggInfo
.nFunc
){
6370 regAcc
= ++pParse
->nMem
;
6371 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, regAcc
);
6375 /* This case runs if the aggregate has no GROUP BY clause. The
6376 ** processing is much simpler since there is only a single row
6379 assert( p
->pGroupBy
==0 );
6380 resetAccumulator(pParse
, &sAggInfo
);
6382 /* If this query is a candidate for the min/max optimization, then
6383 ** minMaxFlag will have been previously set to either
6384 ** WHERE_ORDERBY_MIN or WHERE_ORDERBY_MAX and pMinMaxOrderBy will
6385 ** be an appropriate ORDER BY expression for the optimization.
6387 assert( minMaxFlag
==WHERE_ORDERBY_NORMAL
|| pMinMaxOrderBy
!=0 );
6388 assert( pMinMaxOrderBy
==0 || pMinMaxOrderBy
->nExpr
==1 );
6390 SELECTTRACE(1,pParse
,p
,("WhereBegin\n"));
6391 pWInfo
= sqlite3WhereBegin(pParse
, pTabList
, pWhere
, pMinMaxOrderBy
,
6396 updateAccumulator(pParse
, regAcc
, &sAggInfo
);
6397 if( regAcc
) sqlite3VdbeAddOp2(v
, OP_Integer
, 1, regAcc
);
6398 if( sqlite3WhereIsOrdered(pWInfo
)>0 ){
6399 sqlite3VdbeGoto(v
, sqlite3WhereBreakLabel(pWInfo
));
6400 VdbeComment((v
, "%s() by index",
6401 (minMaxFlag
==WHERE_ORDERBY_MIN
?"min":"max")));
6403 sqlite3WhereEnd(pWInfo
);
6404 finalizeAggFunctions(pParse
, &sAggInfo
);
6408 sqlite3ExprIfFalse(pParse
, pHaving
, addrEnd
, SQLITE_JUMPIFNULL
);
6409 selectInnerLoop(pParse
, p
, -1, 0, 0,
6410 pDest
, addrEnd
, addrEnd
);
6412 sqlite3VdbeResolveLabel(v
, addrEnd
);
6414 } /* endif aggregate query */
6416 if( sDistinct
.eTnctType
==WHERE_DISTINCT_UNORDERED
){
6417 explainTempTable(pParse
, "DISTINCT");
6420 /* If there is an ORDER BY clause, then we need to sort the results
6421 ** and send them to the callback one by one.
6423 if( sSort
.pOrderBy
){
6424 explainTempTable(pParse
,
6425 sSort
.nOBSat
>0 ? "RIGHT PART OF ORDER BY":"ORDER BY");
6426 assert( p
->pEList
==pEList
);
6427 generateSortTail(pParse
, p
, &sSort
, pEList
->nExpr
, pDest
);
6430 /* Jump here to skip this query
6432 sqlite3VdbeResolveLabel(v
, iEnd
);
6434 /* The SELECT has been coded. If there is an error in the Parse structure,
6435 ** set the return code to 1. Otherwise 0. */
6436 rc
= (pParse
->nErr
>0);
6438 /* Control jumps to here if an error is encountered above, or upon
6439 ** successful coding of the SELECT.
6442 sqlite3ExprListDelete(db
, pMinMaxOrderBy
);
6443 sqlite3DbFree(db
, sAggInfo
.aCol
);
6444 sqlite3DbFree(db
, sAggInfo
.aFunc
);
6445 #if SELECTTRACE_ENABLED
6446 SELECTTRACE(0x1,pParse
,p
,("end processing\n"));
6447 if( (sqlite3SelectTrace
& 0x2000)!=0 && ExplainQueryPlanParent(pParse
)==0 ){
6448 sqlite3TreeViewSelect(0, p
, 0);
6451 ExplainQueryPlanPop(pParse
);