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("%u/%d/%p: ",(S)->selId,(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 int labelOBLopt
; /* Jump here when sorter is full */
72 u8 sortFlags
; /* Zero or more SORTFLAG_* bits */
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 pNew
->selId
= ++pParse
->nSelect
;
155 pNew
->addrOpenEphm
[0] = -1;
156 pNew
->addrOpenEphm
[1] = -1;
157 pNew
->nSelectRow
= 0;
158 if( pSrc
==0 ) pSrc
= sqlite3DbMallocZero(pParse
->db
, sizeof(*pSrc
));
160 pNew
->pWhere
= pWhere
;
161 pNew
->pGroupBy
= pGroupBy
;
162 pNew
->pHaving
= pHaving
;
163 pNew
->pOrderBy
= pOrderBy
;
166 pNew
->pLimit
= pLimit
;
168 #ifndef SQLITE_OMIT_WINDOWFUNC
172 if( pParse
->db
->mallocFailed
) {
173 clearSelect(pParse
->db
, pNew
, pNew
!=&standin
);
176 assert( pNew
->pSrc
!=0 || pParse
->nErr
>0 );
178 assert( pNew
!=&standin
);
184 ** Delete the given Select structure and all of its substructures.
186 void sqlite3SelectDelete(sqlite3
*db
, Select
*p
){
187 if( OK_IF_ALWAYS_TRUE(p
) ) clearSelect(db
, p
, 1);
191 ** Return a pointer to the right-most SELECT statement in a compound.
193 static Select
*findRightmost(Select
*p
){
194 while( p
->pNext
) p
= p
->pNext
;
199 ** Given 1 to 3 identifiers preceding the JOIN keyword, determine the
200 ** type of join. Return an integer constant that expresses that type
201 ** in terms of the following bit values:
210 ** A full outer join is the combination of JT_LEFT and JT_RIGHT.
212 ** If an illegal or unsupported join type is seen, then still return
213 ** a join type, but put an error in the pParse structure.
215 int sqlite3JoinType(Parse
*pParse
, Token
*pA
, Token
*pB
, Token
*pC
){
219 /* 0123456789 123456789 123456789 123 */
220 static const char zKeyText
[] = "naturaleftouterightfullinnercross";
221 static const struct {
222 u8 i
; /* Beginning of keyword text in zKeyText[] */
223 u8 nChar
; /* Length of the keyword in characters */
224 u8 code
; /* Join type mask */
226 /* natural */ { 0, 7, JT_NATURAL
},
227 /* left */ { 6, 4, JT_LEFT
|JT_OUTER
},
228 /* outer */ { 10, 5, JT_OUTER
},
229 /* right */ { 14, 5, JT_RIGHT
|JT_OUTER
},
230 /* full */ { 19, 4, JT_LEFT
|JT_RIGHT
|JT_OUTER
},
231 /* inner */ { 23, 5, JT_INNER
},
232 /* cross */ { 28, 5, JT_INNER
|JT_CROSS
},
238 for(i
=0; i
<3 && apAll
[i
]; i
++){
240 for(j
=0; j
<ArraySize(aKeyword
); j
++){
241 if( p
->n
==aKeyword
[j
].nChar
242 && sqlite3StrNICmp((char*)p
->z
, &zKeyText
[aKeyword
[j
].i
], p
->n
)==0 ){
243 jointype
|= aKeyword
[j
].code
;
247 testcase( j
==0 || j
==1 || j
==2 || j
==3 || j
==4 || j
==5 || j
==6 );
248 if( j
>=ArraySize(aKeyword
) ){
249 jointype
|= JT_ERROR
;
254 (jointype
& (JT_INNER
|JT_OUTER
))==(JT_INNER
|JT_OUTER
) ||
255 (jointype
& JT_ERROR
)!=0
257 const char *zSp
= " ";
259 if( pC
==0 ){ zSp
++; }
260 sqlite3ErrorMsg(pParse
, "unknown or unsupported join type: "
261 "%T %T%s%T", pA
, pB
, zSp
, pC
);
263 }else if( (jointype
& JT_OUTER
)!=0
264 && (jointype
& (JT_LEFT
|JT_RIGHT
))!=JT_LEFT
){
265 sqlite3ErrorMsg(pParse
,
266 "RIGHT and FULL OUTER JOINs are not currently supported");
273 ** Return the index of a column in a table. Return -1 if the column
274 ** is not contained in the table.
276 static int columnIndex(Table
*pTab
, const char *zCol
){
278 for(i
=0; i
<pTab
->nCol
; i
++){
279 if( sqlite3StrICmp(pTab
->aCol
[i
].zName
, zCol
)==0 ) return i
;
285 ** Search the first N tables in pSrc, from left to right, looking for a
286 ** table that has a column named zCol.
288 ** When found, set *piTab and *piCol to the table index and column index
289 ** of the matching column and return TRUE.
291 ** If not found, return FALSE.
293 static int tableAndColumnIndex(
294 SrcList
*pSrc
, /* Array of tables to search */
295 int N
, /* Number of tables in pSrc->a[] to search */
296 const char *zCol
, /* Name of the column we are looking for */
297 int *piTab
, /* Write index of pSrc->a[] here */
298 int *piCol
/* Write index of pSrc->a[*piTab].pTab->aCol[] here */
300 int i
; /* For looping over tables in pSrc */
301 int iCol
; /* Index of column matching zCol */
303 assert( (piTab
==0)==(piCol
==0) ); /* Both or neither are NULL */
305 iCol
= columnIndex(pSrc
->a
[i
].pTab
, zCol
);
318 ** This function is used to add terms implied by JOIN syntax to the
319 ** WHERE clause expression of a SELECT statement. The new term, which
320 ** is ANDed with the existing WHERE clause, is of the form:
322 ** (tab1.col1 = tab2.col2)
324 ** where tab1 is the iSrc'th table in SrcList pSrc and tab2 is the
325 ** (iSrc+1)'th. Column col1 is column iColLeft of tab1, and col2 is
326 ** column iColRight of tab2.
328 static void addWhereTerm(
329 Parse
*pParse
, /* Parsing context */
330 SrcList
*pSrc
, /* List of tables in FROM clause */
331 int iLeft
, /* Index of first table to join in pSrc */
332 int iColLeft
, /* Index of column in first table */
333 int iRight
, /* Index of second table in pSrc */
334 int iColRight
, /* Index of column in second table */
335 int isOuterJoin
, /* True if this is an OUTER join */
336 Expr
**ppWhere
/* IN/OUT: The WHERE clause to add to */
338 sqlite3
*db
= pParse
->db
;
343 assert( iLeft
<iRight
);
344 assert( pSrc
->nSrc
>iRight
);
345 assert( pSrc
->a
[iLeft
].pTab
);
346 assert( pSrc
->a
[iRight
].pTab
);
348 pE1
= sqlite3CreateColumnExpr(db
, pSrc
, iLeft
, iColLeft
);
349 pE2
= sqlite3CreateColumnExpr(db
, pSrc
, iRight
, iColRight
);
351 pEq
= sqlite3PExpr(pParse
, TK_EQ
, pE1
, pE2
);
352 if( pEq
&& isOuterJoin
){
353 ExprSetProperty(pEq
, EP_FromJoin
);
354 assert( !ExprHasProperty(pEq
, EP_TokenOnly
|EP_Reduced
) );
355 ExprSetVVAProperty(pEq
, EP_NoReduce
);
356 pEq
->iRightJoinTable
= (i16
)pE2
->iTable
;
358 *ppWhere
= sqlite3ExprAnd(db
, *ppWhere
, pEq
);
362 ** Set the EP_FromJoin property on all terms of the given expression.
363 ** And set the Expr.iRightJoinTable to iTable for every term in the
366 ** The EP_FromJoin property is used on terms of an expression to tell
367 ** the LEFT OUTER JOIN processing logic that this term is part of the
368 ** join restriction specified in the ON or USING clause and not a part
369 ** of the more general WHERE clause. These terms are moved over to the
370 ** WHERE clause during join processing but we need to remember that they
371 ** originated in the ON or USING clause.
373 ** The Expr.iRightJoinTable tells the WHERE clause processing that the
374 ** expression depends on table iRightJoinTable even if that table is not
375 ** explicitly mentioned in the expression. That information is needed
376 ** for cases like this:
378 ** SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.b AND t1.x=5
380 ** The where clause needs to defer the handling of the t1.x=5
381 ** term until after the t2 loop of the join. In that way, a
382 ** NULL t2 row will be inserted whenever t1.x!=5. If we do not
383 ** defer the handling of t1.x=5, it will be processed immediately
384 ** after the t1 loop and rows with t1.x!=5 will never appear in
385 ** the output, which is incorrect.
387 static void setJoinExpr(Expr
*p
, int iTable
){
389 ExprSetProperty(p
, EP_FromJoin
);
390 assert( !ExprHasProperty(p
, EP_TokenOnly
|EP_Reduced
) );
391 ExprSetVVAProperty(p
, EP_NoReduce
);
392 p
->iRightJoinTable
= (i16
)iTable
;
393 if( p
->op
==TK_FUNCTION
&& p
->x
.pList
){
395 for(i
=0; i
<p
->x
.pList
->nExpr
; i
++){
396 setJoinExpr(p
->x
.pList
->a
[i
].pExpr
, iTable
);
399 setJoinExpr(p
->pLeft
, iTable
);
404 /* Undo the work of setJoinExpr(). In the expression tree p, convert every
405 ** term that is marked with EP_FromJoin and iRightJoinTable==iTable into
406 ** an ordinary term that omits the EP_FromJoin mark.
408 ** This happens when a LEFT JOIN is simplified into an ordinary JOIN.
410 static void unsetJoinExpr(Expr
*p
, int iTable
){
412 if( ExprHasProperty(p
, EP_FromJoin
)
413 && (iTable
<0 || p
->iRightJoinTable
==iTable
) ){
414 ExprClearProperty(p
, EP_FromJoin
);
416 if( p
->op
==TK_FUNCTION
&& p
->x
.pList
){
418 for(i
=0; i
<p
->x
.pList
->nExpr
; i
++){
419 unsetJoinExpr(p
->x
.pList
->a
[i
].pExpr
, iTable
);
422 unsetJoinExpr(p
->pLeft
, iTable
);
428 ** This routine processes the join information for a SELECT statement.
429 ** ON and USING clauses are converted into extra terms of the WHERE clause.
430 ** NATURAL joins also create extra WHERE clause terms.
432 ** The terms of a FROM clause are contained in the Select.pSrc structure.
433 ** The left most table is the first entry in Select.pSrc. The right-most
434 ** table is the last entry. The join operator is held in the entry to
435 ** the left. Thus entry 0 contains the join operator for the join between
436 ** entries 0 and 1. Any ON or USING clauses associated with the join are
437 ** also attached to the left entry.
439 ** This routine returns the number of errors encountered.
441 static int sqliteProcessJoin(Parse
*pParse
, Select
*p
){
442 SrcList
*pSrc
; /* All tables in the FROM clause */
443 int i
, j
; /* Loop counters */
444 struct SrcList_item
*pLeft
; /* Left table being joined */
445 struct SrcList_item
*pRight
; /* Right table being joined */
450 for(i
=0; i
<pSrc
->nSrc
-1; i
++, pRight
++, pLeft
++){
451 Table
*pRightTab
= pRight
->pTab
;
454 if( NEVER(pLeft
->pTab
==0 || pRightTab
==0) ) continue;
455 isOuter
= (pRight
->fg
.jointype
& JT_OUTER
)!=0;
457 /* When the NATURAL keyword is present, add WHERE clause terms for
458 ** every column that the two tables have in common.
460 if( pRight
->fg
.jointype
& JT_NATURAL
){
461 if( pRight
->pOn
|| pRight
->pUsing
){
462 sqlite3ErrorMsg(pParse
, "a NATURAL join may not have "
463 "an ON or USING clause", 0);
466 for(j
=0; j
<pRightTab
->nCol
; j
++){
467 char *zName
; /* Name of column in the right table */
468 int iLeft
; /* Matching left table */
469 int iLeftCol
; /* Matching column in the left table */
471 zName
= pRightTab
->aCol
[j
].zName
;
472 if( tableAndColumnIndex(pSrc
, i
+1, zName
, &iLeft
, &iLeftCol
) ){
473 addWhereTerm(pParse
, pSrc
, iLeft
, iLeftCol
, i
+1, j
,
474 isOuter
, &p
->pWhere
);
479 /* Disallow both ON and USING clauses in the same join
481 if( pRight
->pOn
&& pRight
->pUsing
){
482 sqlite3ErrorMsg(pParse
, "cannot have both ON and USING "
483 "clauses in the same join");
487 /* Add the ON clause to the end of the WHERE clause, connected by
491 if( isOuter
) setJoinExpr(pRight
->pOn
, pRight
->iCursor
);
492 p
->pWhere
= sqlite3ExprAnd(pParse
->db
, p
->pWhere
, pRight
->pOn
);
496 /* Create extra terms on the WHERE clause for each column named
497 ** in the USING clause. Example: If the two tables to be joined are
498 ** A and B and the USING clause names X, Y, and Z, then add this
499 ** to the WHERE clause: A.X=B.X AND A.Y=B.Y AND A.Z=B.Z
500 ** Report an error if any column mentioned in the USING clause is
501 ** not contained in both tables to be joined.
503 if( pRight
->pUsing
){
504 IdList
*pList
= pRight
->pUsing
;
505 for(j
=0; j
<pList
->nId
; j
++){
506 char *zName
; /* Name of the term in the USING clause */
507 int iLeft
; /* Table on the left with matching column name */
508 int iLeftCol
; /* Column number of matching column on the left */
509 int iRightCol
; /* Column number of matching column on the right */
511 zName
= pList
->a
[j
].zName
;
512 iRightCol
= columnIndex(pRightTab
, zName
);
514 || !tableAndColumnIndex(pSrc
, i
+1, zName
, &iLeft
, &iLeftCol
)
516 sqlite3ErrorMsg(pParse
, "cannot join using column %s - column "
517 "not present in both tables", zName
);
520 addWhereTerm(pParse
, pSrc
, iLeft
, iLeftCol
, i
+1, iRightCol
,
521 isOuter
, &p
->pWhere
);
529 ** An instance of this object holds information (beyond pParse and pSelect)
530 ** needed to load the next result row that is to be added to the sorter.
532 typedef struct RowLoadInfo RowLoadInfo
;
534 int regResult
; /* Store results in array of registers here */
535 u8 ecelFlags
; /* Flag argument to ExprCodeExprList() */
536 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
537 ExprList
*pExtra
; /* Extra columns needed by sorter refs */
538 int regExtraResult
; /* Where to load the extra columns */
543 ** This routine does the work of loading query data into an array of
544 ** registers so that it can be added to the sorter.
546 static void innerLoopLoadRow(
547 Parse
*pParse
, /* Statement under construction */
548 Select
*pSelect
, /* The query being coded */
549 RowLoadInfo
*pInfo
/* Info needed to complete the row load */
551 sqlite3ExprCodeExprList(pParse
, pSelect
->pEList
, pInfo
->regResult
,
552 0, pInfo
->ecelFlags
);
553 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
555 sqlite3ExprCodeExprList(pParse
, pInfo
->pExtra
, pInfo
->regExtraResult
, 0, 0);
556 sqlite3ExprListDelete(pParse
->db
, pInfo
->pExtra
);
562 ** Code the OP_MakeRecord instruction that generates the entry to be
563 ** added into the sorter.
565 ** Return the register in which the result is stored.
567 static int makeSorterRecord(
574 int nOBSat
= pSort
->nOBSat
;
575 Vdbe
*v
= pParse
->pVdbe
;
576 int regOut
= ++pParse
->nMem
;
577 if( pSort
->pDeferredRowLoad
){
578 innerLoopLoadRow(pParse
, pSelect
, pSort
->pDeferredRowLoad
);
580 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, regBase
+nOBSat
, nBase
-nOBSat
, regOut
);
585 ** Generate code that will push the record in registers regData
586 ** through regData+nData-1 onto the sorter.
588 static void pushOntoSorter(
589 Parse
*pParse
, /* Parser context */
590 SortCtx
*pSort
, /* Information about the ORDER BY clause */
591 Select
*pSelect
, /* The whole SELECT statement */
592 int regData
, /* First register holding data to be sorted */
593 int regOrigData
, /* First register holding data before packing */
594 int nData
, /* Number of elements in the regData data array */
595 int nPrefixReg
/* No. of reg prior to regData available for use */
597 Vdbe
*v
= pParse
->pVdbe
; /* Stmt under construction */
598 int bSeq
= ((pSort
->sortFlags
& SORTFLAG_UseSorter
)==0);
599 int nExpr
= pSort
->pOrderBy
->nExpr
; /* No. of ORDER BY terms */
600 int nBase
= nExpr
+ bSeq
+ nData
; /* Fields in sorter record */
601 int regBase
; /* Regs for sorter record */
602 int regRecord
= 0; /* Assembled sorter record */
603 int nOBSat
= pSort
->nOBSat
; /* ORDER BY terms to skip */
604 int op
; /* Opcode to add sorter record to sorter */
605 int iLimit
; /* LIMIT counter */
606 int iSkip
= 0; /* End of the sorter insert loop */
608 assert( bSeq
==0 || bSeq
==1 );
611 ** (1) The data to be sorted has already been packed into a Record
612 ** by a prior OP_MakeRecord. In this case nData==1 and regData
613 ** will be completely unrelated to regOrigData.
614 ** (2) All output columns are included in the sort record. In that
615 ** case regData==regOrigData.
616 ** (3) Some output columns are omitted from the sort record due to
617 ** the SQLITE_ENABLE_SORTER_REFERENCE optimization, or due to the
618 ** SQLITE_ECEL_OMITREF optimization, or due to the
619 ** SortCtx.pDeferredRowLoad optimiation. In any of these cases
620 ** regOrigData is 0 to prevent this routine from trying to copy
621 ** values that might not yet exist.
623 assert( nData
==1 || regData
==regOrigData
|| regOrigData
==0 );
626 assert( nPrefixReg
==nExpr
+bSeq
);
627 regBase
= regData
- nPrefixReg
;
629 regBase
= pParse
->nMem
+ 1;
630 pParse
->nMem
+= nBase
;
632 assert( pSelect
->iOffset
==0 || pSelect
->iLimit
!=0 );
633 iLimit
= pSelect
->iOffset
? pSelect
->iOffset
+1 : pSelect
->iLimit
;
634 pSort
->labelDone
= sqlite3VdbeMakeLabel(pParse
);
635 sqlite3ExprCodeExprList(pParse
, pSort
->pOrderBy
, regBase
, regOrigData
,
636 SQLITE_ECEL_DUP
| (regOrigData
? SQLITE_ECEL_REF
: 0));
638 sqlite3VdbeAddOp2(v
, OP_Sequence
, pSort
->iECursor
, regBase
+nExpr
);
640 if( nPrefixReg
==0 && nData
>0 ){
641 sqlite3ExprCodeMove(pParse
, regData
, regBase
+nExpr
+bSeq
, nData
);
644 int regPrevKey
; /* The first nOBSat columns of the previous row */
645 int addrFirst
; /* Address of the OP_IfNot opcode */
646 int addrJmp
; /* Address of the OP_Jump opcode */
647 VdbeOp
*pOp
; /* Opcode that opens the sorter */
648 int nKey
; /* Number of sorting key columns, including OP_Sequence */
649 KeyInfo
*pKI
; /* Original KeyInfo on the sorter table */
651 regRecord
= makeSorterRecord(pParse
, pSort
, pSelect
, regBase
, nBase
);
652 regPrevKey
= pParse
->nMem
+1;
653 pParse
->nMem
+= pSort
->nOBSat
;
654 nKey
= nExpr
- pSort
->nOBSat
+ bSeq
;
656 addrFirst
= sqlite3VdbeAddOp1(v
, OP_IfNot
, regBase
+nExpr
);
658 addrFirst
= sqlite3VdbeAddOp1(v
, OP_SequenceTest
, pSort
->iECursor
);
661 sqlite3VdbeAddOp3(v
, OP_Compare
, regPrevKey
, regBase
, pSort
->nOBSat
);
662 pOp
= sqlite3VdbeGetOp(v
, pSort
->addrSortIndex
);
663 if( pParse
->db
->mallocFailed
) return;
664 pOp
->p2
= nKey
+ nData
;
665 pKI
= pOp
->p4
.pKeyInfo
;
666 memset(pKI
->aSortOrder
, 0, pKI
->nKeyField
); /* Makes OP_Jump testable */
667 sqlite3VdbeChangeP4(v
, -1, (char*)pKI
, P4_KEYINFO
);
668 testcase( pKI
->nAllField
> pKI
->nKeyField
+2 );
669 pOp
->p4
.pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
,pSort
->pOrderBy
,nOBSat
,
670 pKI
->nAllField
-pKI
->nKeyField
-1);
671 addrJmp
= sqlite3VdbeCurrentAddr(v
);
672 sqlite3VdbeAddOp3(v
, OP_Jump
, addrJmp
+1, 0, addrJmp
+1); VdbeCoverage(v
);
673 pSort
->labelBkOut
= sqlite3VdbeMakeLabel(pParse
);
674 pSort
->regReturn
= ++pParse
->nMem
;
675 sqlite3VdbeAddOp2(v
, OP_Gosub
, pSort
->regReturn
, pSort
->labelBkOut
);
676 sqlite3VdbeAddOp1(v
, OP_ResetSorter
, pSort
->iECursor
);
678 sqlite3VdbeAddOp2(v
, OP_IfNot
, iLimit
, pSort
->labelDone
);
681 sqlite3VdbeJumpHere(v
, addrFirst
);
682 sqlite3ExprCodeMove(pParse
, regBase
, regPrevKey
, pSort
->nOBSat
);
683 sqlite3VdbeJumpHere(v
, addrJmp
);
686 /* At this point the values for the new sorter entry are stored
687 ** in an array of registers. They need to be composed into a record
688 ** and inserted into the sorter if either (a) there are currently
689 ** less than LIMIT+OFFSET items or (b) the new record is smaller than
690 ** the largest record currently in the sorter. If (b) is true and there
691 ** are already LIMIT+OFFSET items in the sorter, delete the largest
692 ** entry before inserting the new one. This way there are never more
693 ** than LIMIT+OFFSET items in the sorter.
695 ** If the new record does not need to be inserted into the sorter,
696 ** jump to the next iteration of the loop. If the pSort->labelOBLopt
697 ** value is not zero, then it is a label of where to jump. Otherwise,
698 ** just bypass the row insert logic. See the header comment on the
699 ** sqlite3WhereOrderByLimitOptLabel() function for additional info.
701 int iCsr
= pSort
->iECursor
;
702 sqlite3VdbeAddOp2(v
, OP_IfNotZero
, iLimit
, sqlite3VdbeCurrentAddr(v
)+4);
704 sqlite3VdbeAddOp2(v
, OP_Last
, iCsr
, 0);
705 iSkip
= sqlite3VdbeAddOp4Int(v
, OP_IdxLE
,
706 iCsr
, 0, regBase
+nOBSat
, nExpr
-nOBSat
);
708 sqlite3VdbeAddOp1(v
, OP_Delete
, iCsr
);
711 regRecord
= makeSorterRecord(pParse
, pSort
, pSelect
, regBase
, nBase
);
713 if( pSort
->sortFlags
& SORTFLAG_UseSorter
){
714 op
= OP_SorterInsert
;
718 sqlite3VdbeAddOp4Int(v
, op
, pSort
->iECursor
, regRecord
,
719 regBase
+nOBSat
, nBase
-nOBSat
);
721 sqlite3VdbeChangeP2(v
, iSkip
,
722 pSort
->labelOBLopt
? pSort
->labelOBLopt
: sqlite3VdbeCurrentAddr(v
));
727 ** Add code to implement the OFFSET
729 static void codeOffset(
730 Vdbe
*v
, /* Generate code into this VM */
731 int iOffset
, /* Register holding the offset counter */
732 int iContinue
/* Jump here to skip the current record */
735 sqlite3VdbeAddOp3(v
, OP_IfPos
, iOffset
, iContinue
, 1); VdbeCoverage(v
);
736 VdbeComment((v
, "OFFSET"));
741 ** Add code that will check to make sure the N registers starting at iMem
742 ** form a distinct entry. iTab is a sorting index that holds previously
743 ** seen combinations of the N values. A new entry is made in iTab
744 ** if the current N values are new.
746 ** A jump to addrRepeat is made and the N+1 values are popped from the
747 ** stack if the top N elements are not distinct.
749 static void codeDistinct(
750 Parse
*pParse
, /* Parsing and code generating context */
751 int iTab
, /* A sorting index used to test for distinctness */
752 int addrRepeat
, /* Jump to here if not distinct */
753 int N
, /* Number of elements */
754 int iMem
/* First element */
760 r1
= sqlite3GetTempReg(pParse
);
761 sqlite3VdbeAddOp4Int(v
, OP_Found
, iTab
, addrRepeat
, iMem
, N
); VdbeCoverage(v
);
762 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, iMem
, N
, r1
);
763 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, iTab
, r1
, iMem
, N
);
764 sqlite3VdbeChangeP5(v
, OPFLAG_USESEEKRESULT
);
765 sqlite3ReleaseTempReg(pParse
, r1
);
768 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
770 ** This function is called as part of inner-loop generation for a SELECT
771 ** statement with an ORDER BY that is not optimized by an index. It
772 ** determines the expressions, if any, that the sorter-reference
773 ** optimization should be used for. The sorter-reference optimization
774 ** is used for SELECT queries like:
776 ** SELECT a, bigblob FROM t1 ORDER BY a LIMIT 10
778 ** If the optimization is used for expression "bigblob", then instead of
779 ** storing values read from that column in the sorter records, the PK of
780 ** the row from table t1 is stored instead. Then, as records are extracted from
781 ** the sorter to return to the user, the required value of bigblob is
782 ** retrieved directly from table t1. If the values are very large, this
783 ** can be more efficient than storing them directly in the sorter records.
785 ** The ExprList_item.bSorterRef flag is set for each expression in pEList
786 ** for which the sorter-reference optimization should be enabled.
787 ** Additionally, the pSort->aDefer[] array is populated with entries
788 ** for all cursors required to evaluate all selected expressions. Finally.
789 ** output variable (*ppExtra) is set to an expression list containing
790 ** expressions for all extra PK values that should be stored in the
793 static void selectExprDefer(
794 Parse
*pParse
, /* Leave any error here */
795 SortCtx
*pSort
, /* Sorter context */
796 ExprList
*pEList
, /* Expressions destined for sorter */
797 ExprList
**ppExtra
/* Expressions to append to sorter record */
801 ExprList
*pExtra
= 0;
802 for(i
=0; i
<pEList
->nExpr
; i
++){
803 struct ExprList_item
*pItem
= &pEList
->a
[i
];
804 if( pItem
->u
.x
.iOrderByCol
==0 ){
805 Expr
*pExpr
= pItem
->pExpr
;
806 Table
*pTab
= pExpr
->y
.pTab
;
807 if( pExpr
->op
==TK_COLUMN
&& pExpr
->iColumn
>=0 && pTab
&& !IsVirtual(pTab
)
808 && (pTab
->aCol
[pExpr
->iColumn
].colFlags
& COLFLAG_SORTERREF
)
811 for(j
=0; j
<nDefer
; j
++){
812 if( pSort
->aDefer
[j
].iCsr
==pExpr
->iTable
) break;
815 if( nDefer
==ArraySize(pSort
->aDefer
) ){
821 if( !HasRowid(pTab
) ){
822 pPk
= sqlite3PrimaryKeyIndex(pTab
);
825 for(k
=0; k
<nKey
; k
++){
826 Expr
*pNew
= sqlite3PExpr(pParse
, TK_COLUMN
, 0, 0);
828 pNew
->iTable
= pExpr
->iTable
;
829 pNew
->y
.pTab
= pExpr
->y
.pTab
;
830 pNew
->iColumn
= pPk
? pPk
->aiColumn
[k
] : -1;
831 pExtra
= sqlite3ExprListAppend(pParse
, pExtra
, pNew
);
834 pSort
->aDefer
[nDefer
].pTab
= pExpr
->y
.pTab
;
835 pSort
->aDefer
[nDefer
].iCsr
= pExpr
->iTable
;
836 pSort
->aDefer
[nDefer
].nKey
= nKey
;
840 pItem
->bSorterRef
= 1;
844 pSort
->nDefer
= (u8
)nDefer
;
850 ** This routine generates the code for the inside of the inner loop
853 ** If srcTab is negative, then the p->pEList expressions
854 ** are evaluated in order to get the data for this row. If srcTab is
855 ** zero or more, then data is pulled from srcTab and p->pEList is used only
856 ** to get the number of columns and the collation sequence for each column.
858 static void selectInnerLoop(
859 Parse
*pParse
, /* The parser context */
860 Select
*p
, /* The complete select statement being coded */
861 int srcTab
, /* Pull data from this table if non-negative */
862 SortCtx
*pSort
, /* If not NULL, info on how to process ORDER BY */
863 DistinctCtx
*pDistinct
, /* If not NULL, info on how to process DISTINCT */
864 SelectDest
*pDest
, /* How to dispose of the results */
865 int iContinue
, /* Jump here to continue with next row */
866 int iBreak
/* Jump here to break out of the inner loop */
868 Vdbe
*v
= pParse
->pVdbe
;
870 int hasDistinct
; /* True if the DISTINCT keyword is present */
871 int eDest
= pDest
->eDest
; /* How to dispose of results */
872 int iParm
= pDest
->iSDParm
; /* First argument to disposal method */
873 int nResultCol
; /* Number of result columns */
874 int nPrefixReg
= 0; /* Number of extra registers before regResult */
875 RowLoadInfo sRowLoadInfo
; /* Info for deferred row loading */
877 /* Usually, regResult is the first cell in an array of memory cells
878 ** containing the current result row. In this case regOrig is set to the
879 ** same value. However, if the results are being sent to the sorter, the
880 ** values for any expressions that are also part of the sort-key are omitted
881 ** from this array. In this case regOrig is set to zero. */
882 int regResult
; /* Start of memory holding current results */
883 int regOrig
; /* Start of memory holding full result (or 0) */
886 assert( p
->pEList
!=0 );
887 hasDistinct
= pDistinct
? pDistinct
->eTnctType
: WHERE_DISTINCT_NOOP
;
888 if( pSort
&& pSort
->pOrderBy
==0 ) pSort
= 0;
889 if( pSort
==0 && !hasDistinct
){
890 assert( iContinue
!=0 );
891 codeOffset(v
, p
->iOffset
, iContinue
);
894 /* Pull the requested columns.
896 nResultCol
= p
->pEList
->nExpr
;
898 if( pDest
->iSdst
==0 ){
900 nPrefixReg
= pSort
->pOrderBy
->nExpr
;
901 if( !(pSort
->sortFlags
& SORTFLAG_UseSorter
) ) nPrefixReg
++;
902 pParse
->nMem
+= nPrefixReg
;
904 pDest
->iSdst
= pParse
->nMem
+1;
905 pParse
->nMem
+= nResultCol
;
906 }else if( pDest
->iSdst
+nResultCol
> pParse
->nMem
){
907 /* This is an error condition that can result, for example, when a SELECT
908 ** on the right-hand side of an INSERT contains more result columns than
909 ** there are columns in the table on the left. The error will be caught
910 ** and reported later. But we need to make sure enough memory is allocated
911 ** to avoid other spurious errors in the meantime. */
912 pParse
->nMem
+= nResultCol
;
914 pDest
->nSdst
= nResultCol
;
915 regOrig
= regResult
= pDest
->iSdst
;
917 for(i
=0; i
<nResultCol
; i
++){
918 sqlite3VdbeAddOp3(v
, OP_Column
, srcTab
, i
, regResult
+i
);
919 VdbeComment((v
, "%s", p
->pEList
->a
[i
].zName
));
921 }else if( eDest
!=SRT_Exists
){
922 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
923 ExprList
*pExtra
= 0;
925 /* If the destination is an EXISTS(...) expression, the actual
926 ** values returned by the SELECT are not required.
928 u8 ecelFlags
; /* "ecel" is an abbreviation of "ExprCodeExprList" */
930 if( eDest
==SRT_Mem
|| eDest
==SRT_Output
|| eDest
==SRT_Coroutine
){
931 ecelFlags
= SQLITE_ECEL_DUP
;
935 if( pSort
&& hasDistinct
==0 && eDest
!=SRT_EphemTab
&& eDest
!=SRT_Table
){
936 /* For each expression in p->pEList that is a copy of an expression in
937 ** the ORDER BY clause (pSort->pOrderBy), set the associated
938 ** iOrderByCol value to one more than the index of the ORDER BY
939 ** expression within the sort-key that pushOntoSorter() will generate.
940 ** This allows the p->pEList field to be omitted from the sorted record,
941 ** saving space and CPU cycles. */
942 ecelFlags
|= (SQLITE_ECEL_OMITREF
|SQLITE_ECEL_REF
);
944 for(i
=pSort
->nOBSat
; i
<pSort
->pOrderBy
->nExpr
; i
++){
946 if( (j
= pSort
->pOrderBy
->a
[i
].u
.x
.iOrderByCol
)>0 ){
947 p
->pEList
->a
[j
-1].u
.x
.iOrderByCol
= i
+1-pSort
->nOBSat
;
950 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
951 selectExprDefer(pParse
, pSort
, p
->pEList
, &pExtra
);
952 if( pExtra
&& pParse
->db
->mallocFailed
==0 ){
953 /* If there are any extra PK columns to add to the sorter records,
954 ** allocate extra memory cells and adjust the OpenEphemeral
955 ** instruction to account for the larger records. This is only
956 ** required if there are one or more WITHOUT ROWID tables with
957 ** composite primary keys in the SortCtx.aDefer[] array. */
958 VdbeOp
*pOp
= sqlite3VdbeGetOp(v
, pSort
->addrSortIndex
);
959 pOp
->p2
+= (pExtra
->nExpr
- pSort
->nDefer
);
960 pOp
->p4
.pKeyInfo
->nAllField
+= (pExtra
->nExpr
- pSort
->nDefer
);
961 pParse
->nMem
+= pExtra
->nExpr
;
965 /* Adjust nResultCol to account for columns that are omitted
966 ** from the sorter by the optimizations in this branch */
968 for(i
=0; i
<pEList
->nExpr
; i
++){
969 if( pEList
->a
[i
].u
.x
.iOrderByCol
>0
970 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
971 || pEList
->a
[i
].bSorterRef
980 testcase( eDest
==SRT_Set
);
981 testcase( eDest
==SRT_Mem
);
982 testcase( eDest
==SRT_Coroutine
);
983 testcase( eDest
==SRT_Output
);
984 assert( eDest
==SRT_Set
|| eDest
==SRT_Mem
985 || eDest
==SRT_Coroutine
|| eDest
==SRT_Output
);
987 sRowLoadInfo
.regResult
= regResult
;
988 sRowLoadInfo
.ecelFlags
= ecelFlags
;
989 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
990 sRowLoadInfo
.pExtra
= pExtra
;
991 sRowLoadInfo
.regExtraResult
= regResult
+ nResultCol
;
992 if( pExtra
) nResultCol
+= pExtra
->nExpr
;
995 && (ecelFlags
& SQLITE_ECEL_OMITREF
)!=0
999 assert( hasDistinct
==0 );
1000 pSort
->pDeferredRowLoad
= &sRowLoadInfo
;
1003 innerLoopLoadRow(pParse
, p
, &sRowLoadInfo
);
1007 /* If the DISTINCT keyword was present on the SELECT statement
1008 ** and this row has been seen before, then do not make this row
1009 ** part of the result.
1012 switch( pDistinct
->eTnctType
){
1013 case WHERE_DISTINCT_ORDERED
: {
1014 VdbeOp
*pOp
; /* No longer required OpenEphemeral instr. */
1015 int iJump
; /* Jump destination */
1016 int regPrev
; /* Previous row content */
1018 /* Allocate space for the previous row */
1019 regPrev
= pParse
->nMem
+1;
1020 pParse
->nMem
+= nResultCol
;
1022 /* Change the OP_OpenEphemeral coded earlier to an OP_Null
1023 ** sets the MEM_Cleared bit on the first register of the
1024 ** previous value. This will cause the OP_Ne below to always
1025 ** fail on the first iteration of the loop even if the first
1026 ** row is all NULLs.
1028 sqlite3VdbeChangeToNoop(v
, pDistinct
->addrTnct
);
1029 pOp
= sqlite3VdbeGetOp(v
, pDistinct
->addrTnct
);
1030 pOp
->opcode
= OP_Null
;
1034 iJump
= sqlite3VdbeCurrentAddr(v
) + nResultCol
;
1035 for(i
=0; i
<nResultCol
; i
++){
1036 CollSeq
*pColl
= sqlite3ExprCollSeq(pParse
, p
->pEList
->a
[i
].pExpr
);
1037 if( i
<nResultCol
-1 ){
1038 sqlite3VdbeAddOp3(v
, OP_Ne
, regResult
+i
, iJump
, regPrev
+i
);
1041 sqlite3VdbeAddOp3(v
, OP_Eq
, regResult
+i
, iContinue
, regPrev
+i
);
1044 sqlite3VdbeChangeP4(v
, -1, (const char *)pColl
, P4_COLLSEQ
);
1045 sqlite3VdbeChangeP5(v
, SQLITE_NULLEQ
);
1047 assert( sqlite3VdbeCurrentAddr(v
)==iJump
|| pParse
->db
->mallocFailed
);
1048 sqlite3VdbeAddOp3(v
, OP_Copy
, regResult
, regPrev
, nResultCol
-1);
1052 case WHERE_DISTINCT_UNIQUE
: {
1053 sqlite3VdbeChangeToNoop(v
, pDistinct
->addrTnct
);
1058 assert( pDistinct
->eTnctType
==WHERE_DISTINCT_UNORDERED
);
1059 codeDistinct(pParse
, pDistinct
->tabTnct
, iContinue
, nResultCol
,
1065 codeOffset(v
, p
->iOffset
, iContinue
);
1070 /* In this mode, write each query result to the key of the temporary
1073 #ifndef SQLITE_OMIT_COMPOUND_SELECT
1076 r1
= sqlite3GetTempReg(pParse
);
1077 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, regResult
, nResultCol
, r1
);
1078 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, iParm
, r1
, regResult
, nResultCol
);
1079 sqlite3ReleaseTempReg(pParse
, r1
);
1083 /* Construct a record from the query result, but instead of
1084 ** saving that record, use it as a key to delete elements from
1085 ** the temporary table iParm.
1088 sqlite3VdbeAddOp3(v
, OP_IdxDelete
, iParm
, regResult
, nResultCol
);
1091 #endif /* SQLITE_OMIT_COMPOUND_SELECT */
1093 /* Store the result as data using a unique key.
1098 case SRT_EphemTab
: {
1099 int r1
= sqlite3GetTempRange(pParse
, nPrefixReg
+1);
1100 testcase( eDest
==SRT_Table
);
1101 testcase( eDest
==SRT_EphemTab
);
1102 testcase( eDest
==SRT_Fifo
);
1103 testcase( eDest
==SRT_DistFifo
);
1104 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, regResult
, nResultCol
, r1
+nPrefixReg
);
1105 #ifndef SQLITE_OMIT_CTE
1106 if( eDest
==SRT_DistFifo
){
1107 /* If the destination is DistFifo, then cursor (iParm+1) is open
1108 ** on an ephemeral index. If the current row is already present
1109 ** in the index, do not write it to the output. If not, add the
1110 ** current row to the index and proceed with writing it to the
1111 ** output table as well. */
1112 int addr
= sqlite3VdbeCurrentAddr(v
) + 4;
1113 sqlite3VdbeAddOp4Int(v
, OP_Found
, iParm
+1, addr
, r1
, 0);
1115 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, iParm
+1, r1
,regResult
,nResultCol
);
1120 assert( regResult
==regOrig
);
1121 pushOntoSorter(pParse
, pSort
, p
, r1
+nPrefixReg
, regOrig
, 1, nPrefixReg
);
1123 int r2
= sqlite3GetTempReg(pParse
);
1124 sqlite3VdbeAddOp2(v
, OP_NewRowid
, iParm
, r2
);
1125 sqlite3VdbeAddOp3(v
, OP_Insert
, iParm
, r1
, r2
);
1126 sqlite3VdbeChangeP5(v
, OPFLAG_APPEND
);
1127 sqlite3ReleaseTempReg(pParse
, r2
);
1129 sqlite3ReleaseTempRange(pParse
, r1
, nPrefixReg
+1);
1133 #ifndef SQLITE_OMIT_SUBQUERY
1134 /* If we are creating a set for an "expr IN (SELECT ...)" construct,
1135 ** then there should be a single item on the stack. Write this
1136 ** item into the set table with bogus data.
1140 /* At first glance you would think we could optimize out the
1141 ** ORDER BY in this case since the order of entries in the set
1142 ** does not matter. But there might be a LIMIT clause, in which
1143 ** case the order does matter */
1145 pParse
, pSort
, p
, regResult
, regOrig
, nResultCol
, nPrefixReg
);
1147 int r1
= sqlite3GetTempReg(pParse
);
1148 assert( sqlite3Strlen30(pDest
->zAffSdst
)==nResultCol
);
1149 sqlite3VdbeAddOp4(v
, OP_MakeRecord
, regResult
, nResultCol
,
1150 r1
, pDest
->zAffSdst
, nResultCol
);
1151 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, iParm
, r1
, regResult
, nResultCol
);
1152 sqlite3ReleaseTempReg(pParse
, r1
);
1157 /* If any row exist in the result set, record that fact and abort.
1160 sqlite3VdbeAddOp2(v
, OP_Integer
, 1, iParm
);
1161 /* The LIMIT clause will terminate the loop for us */
1165 /* If this is a scalar select that is part of an expression, then
1166 ** store the results in the appropriate memory cell or array of
1167 ** memory cells and break out of the scan loop.
1171 assert( nResultCol
<=pDest
->nSdst
);
1173 pParse
, pSort
, p
, regResult
, regOrig
, nResultCol
, nPrefixReg
);
1175 assert( nResultCol
==pDest
->nSdst
);
1176 assert( regResult
==iParm
);
1177 /* The LIMIT clause will jump out of the loop for us */
1181 #endif /* #ifndef SQLITE_OMIT_SUBQUERY */
1183 case SRT_Coroutine
: /* Send data to a co-routine */
1184 case SRT_Output
: { /* Return the results */
1185 testcase( eDest
==SRT_Coroutine
);
1186 testcase( eDest
==SRT_Output
);
1188 pushOntoSorter(pParse
, pSort
, p
, regResult
, regOrig
, nResultCol
,
1190 }else if( eDest
==SRT_Coroutine
){
1191 sqlite3VdbeAddOp1(v
, OP_Yield
, pDest
->iSDParm
);
1193 sqlite3VdbeAddOp2(v
, OP_ResultRow
, regResult
, nResultCol
);
1198 #ifndef SQLITE_OMIT_CTE
1199 /* Write the results into a priority queue that is order according to
1200 ** pDest->pOrderBy (in pSO). pDest->iSDParm (in iParm) is the cursor for an
1201 ** index with pSO->nExpr+2 columns. Build a key using pSO for the first
1202 ** pSO->nExpr columns, then make sure all keys are unique by adding a
1203 ** final OP_Sequence column. The last column is the record as a blob.
1211 pSO
= pDest
->pOrderBy
;
1214 r1
= sqlite3GetTempReg(pParse
);
1215 r2
= sqlite3GetTempRange(pParse
, nKey
+2);
1217 if( eDest
==SRT_DistQueue
){
1218 /* If the destination is DistQueue, then cursor (iParm+1) is open
1219 ** on a second ephemeral index that holds all values every previously
1220 ** added to the queue. */
1221 addrTest
= sqlite3VdbeAddOp4Int(v
, OP_Found
, iParm
+1, 0,
1222 regResult
, nResultCol
);
1225 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, regResult
, nResultCol
, r3
);
1226 if( eDest
==SRT_DistQueue
){
1227 sqlite3VdbeAddOp2(v
, OP_IdxInsert
, iParm
+1, r3
);
1228 sqlite3VdbeChangeP5(v
, OPFLAG_USESEEKRESULT
);
1230 for(i
=0; i
<nKey
; i
++){
1231 sqlite3VdbeAddOp2(v
, OP_SCopy
,
1232 regResult
+ pSO
->a
[i
].u
.x
.iOrderByCol
- 1,
1235 sqlite3VdbeAddOp2(v
, OP_Sequence
, iParm
, r2
+nKey
);
1236 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, r2
, nKey
+2, r1
);
1237 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, iParm
, r1
, r2
, nKey
+2);
1238 if( addrTest
) sqlite3VdbeJumpHere(v
, addrTest
);
1239 sqlite3ReleaseTempReg(pParse
, r1
);
1240 sqlite3ReleaseTempRange(pParse
, r2
, nKey
+2);
1243 #endif /* SQLITE_OMIT_CTE */
1247 #if !defined(SQLITE_OMIT_TRIGGER)
1248 /* Discard the results. This is used for SELECT statements inside
1249 ** the body of a TRIGGER. The purpose of such selects is to call
1250 ** user-defined functions that have side effects. We do not care
1251 ** about the actual results of the select.
1254 assert( eDest
==SRT_Discard
);
1260 /* Jump to the end of the loop if the LIMIT is reached. Except, if
1261 ** there is a sorter, in which case the sorter has already limited
1262 ** the output for us.
1264 if( pSort
==0 && p
->iLimit
){
1265 sqlite3VdbeAddOp2(v
, OP_DecrJumpZero
, p
->iLimit
, iBreak
); VdbeCoverage(v
);
1270 ** Allocate a KeyInfo object sufficient for an index of N key columns and
1273 KeyInfo
*sqlite3KeyInfoAlloc(sqlite3
*db
, int N
, int X
){
1274 int nExtra
= (N
+X
)*(sizeof(CollSeq
*)+1) - sizeof(CollSeq
*);
1275 KeyInfo
*p
= sqlite3DbMallocRawNN(db
, sizeof(KeyInfo
) + nExtra
);
1277 p
->aSortOrder
= (u8
*)&p
->aColl
[N
+X
];
1278 p
->nKeyField
= (u16
)N
;
1279 p
->nAllField
= (u16
)(N
+X
);
1283 memset(&p
[1], 0, nExtra
);
1285 sqlite3OomFault(db
);
1291 ** Deallocate a KeyInfo object
1293 void sqlite3KeyInfoUnref(KeyInfo
*p
){
1295 assert( p
->nRef
>0 );
1297 if( p
->nRef
==0 ) sqlite3DbFreeNN(p
->db
, p
);
1302 ** Make a new pointer to a KeyInfo object
1304 KeyInfo
*sqlite3KeyInfoRef(KeyInfo
*p
){
1306 assert( p
->nRef
>0 );
1314 ** Return TRUE if a KeyInfo object can be change. The KeyInfo object
1315 ** can only be changed if this is just a single reference to the object.
1317 ** This routine is used only inside of assert() statements.
1319 int sqlite3KeyInfoIsWriteable(KeyInfo
*p
){ return p
->nRef
==1; }
1320 #endif /* SQLITE_DEBUG */
1323 ** Given an expression list, generate a KeyInfo structure that records
1324 ** the collating sequence for each expression in that expression list.
1326 ** If the ExprList is an ORDER BY or GROUP BY clause then the resulting
1327 ** KeyInfo structure is appropriate for initializing a virtual index to
1328 ** implement that clause. If the ExprList is the result set of a SELECT
1329 ** then the KeyInfo structure is appropriate for initializing a virtual
1330 ** index to implement a DISTINCT test.
1332 ** Space to hold the KeyInfo structure is obtained from malloc. The calling
1333 ** function is responsible for seeing that this structure is eventually
1336 KeyInfo
*sqlite3KeyInfoFromExprList(
1337 Parse
*pParse
, /* Parsing context */
1338 ExprList
*pList
, /* Form the KeyInfo object from this ExprList */
1339 int iStart
, /* Begin with this column of pList */
1340 int nExtra
/* Add this many extra columns to the end */
1344 struct ExprList_item
*pItem
;
1345 sqlite3
*db
= pParse
->db
;
1348 nExpr
= pList
->nExpr
;
1349 pInfo
= sqlite3KeyInfoAlloc(db
, nExpr
-iStart
, nExtra
+1);
1351 assert( sqlite3KeyInfoIsWriteable(pInfo
) );
1352 for(i
=iStart
, pItem
=pList
->a
+iStart
; i
<nExpr
; i
++, pItem
++){
1353 pInfo
->aColl
[i
-iStart
] = sqlite3ExprNNCollSeq(pParse
, pItem
->pExpr
);
1354 pInfo
->aSortOrder
[i
-iStart
] = pItem
->sortOrder
;
1361 ** Name of the connection operator, used for error messages.
1363 static const char *selectOpName(int id
){
1366 case TK_ALL
: z
= "UNION ALL"; break;
1367 case TK_INTERSECT
: z
= "INTERSECT"; break;
1368 case TK_EXCEPT
: z
= "EXCEPT"; break;
1369 default: z
= "UNION"; break;
1374 #ifndef SQLITE_OMIT_EXPLAIN
1376 ** Unless an "EXPLAIN QUERY PLAN" command is being processed, this function
1377 ** is a no-op. Otherwise, it adds a single row of output to the EQP result,
1378 ** where the caption is of the form:
1380 ** "USE TEMP B-TREE FOR xxx"
1382 ** where xxx is one of "DISTINCT", "ORDER BY" or "GROUP BY". Exactly which
1383 ** is determined by the zUsage argument.
1385 static void explainTempTable(Parse
*pParse
, const char *zUsage
){
1386 ExplainQueryPlan((pParse
, 0, "USE TEMP B-TREE FOR %s", zUsage
));
1390 ** Assign expression b to lvalue a. A second, no-op, version of this macro
1391 ** is provided when SQLITE_OMIT_EXPLAIN is defined. This allows the code
1392 ** in sqlite3Select() to assign values to structure member variables that
1393 ** only exist if SQLITE_OMIT_EXPLAIN is not defined without polluting the
1394 ** code with #ifndef directives.
1396 # define explainSetInteger(a, b) a = b
1399 /* No-op versions of the explainXXX() functions and macros. */
1400 # define explainTempTable(y,z)
1401 # define explainSetInteger(y,z)
1406 ** If the inner loop was generated using a non-null pOrderBy argument,
1407 ** then the results were placed in a sorter. After the loop is terminated
1408 ** we need to run the sorter and output the results. The following
1409 ** routine generates the code needed to do that.
1411 static void generateSortTail(
1412 Parse
*pParse
, /* Parsing context */
1413 Select
*p
, /* The SELECT statement */
1414 SortCtx
*pSort
, /* Information on the ORDER BY clause */
1415 int nColumn
, /* Number of columns of data */
1416 SelectDest
*pDest
/* Write the sorted results here */
1418 Vdbe
*v
= pParse
->pVdbe
; /* The prepared statement */
1419 int addrBreak
= pSort
->labelDone
; /* Jump here to exit loop */
1420 int addrContinue
= sqlite3VdbeMakeLabel(pParse
);/* Jump here for next cycle */
1421 int addr
; /* Top of output loop. Jump for Next. */
1424 ExprList
*pOrderBy
= pSort
->pOrderBy
;
1425 int eDest
= pDest
->eDest
;
1426 int iParm
= pDest
->iSDParm
;
1430 int nKey
; /* Number of key columns in sorter record */
1431 int iSortTab
; /* Sorter cursor to read from */
1433 int bSeq
; /* True if sorter record includes seq. no. */
1435 struct ExprList_item
*aOutEx
= p
->pEList
->a
;
1437 assert( addrBreak
<0 );
1438 if( pSort
->labelBkOut
){
1439 sqlite3VdbeAddOp2(v
, OP_Gosub
, pSort
->regReturn
, pSort
->labelBkOut
);
1440 sqlite3VdbeGoto(v
, addrBreak
);
1441 sqlite3VdbeResolveLabel(v
, pSort
->labelBkOut
);
1444 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
1445 /* Open any cursors needed for sorter-reference expressions */
1446 for(i
=0; i
<pSort
->nDefer
; i
++){
1447 Table
*pTab
= pSort
->aDefer
[i
].pTab
;
1448 int iDb
= sqlite3SchemaToIndex(pParse
->db
, pTab
->pSchema
);
1449 sqlite3OpenTable(pParse
, pSort
->aDefer
[i
].iCsr
, iDb
, pTab
, OP_OpenRead
);
1450 nRefKey
= MAX(nRefKey
, pSort
->aDefer
[i
].nKey
);
1454 iTab
= pSort
->iECursor
;
1455 if( eDest
==SRT_Output
|| eDest
==SRT_Coroutine
|| eDest
==SRT_Mem
){
1457 regRow
= pDest
->iSdst
;
1459 regRowid
= sqlite3GetTempReg(pParse
);
1460 if( eDest
==SRT_EphemTab
|| eDest
==SRT_Table
){
1461 regRow
= sqlite3GetTempReg(pParse
);
1464 regRow
= sqlite3GetTempRange(pParse
, nColumn
);
1467 nKey
= pOrderBy
->nExpr
- pSort
->nOBSat
;
1468 if( pSort
->sortFlags
& SORTFLAG_UseSorter
){
1469 int regSortOut
= ++pParse
->nMem
;
1470 iSortTab
= pParse
->nTab
++;
1471 if( pSort
->labelBkOut
){
1472 addrOnce
= sqlite3VdbeAddOp0(v
, OP_Once
); VdbeCoverage(v
);
1474 sqlite3VdbeAddOp3(v
, OP_OpenPseudo
, iSortTab
, regSortOut
,
1475 nKey
+1+nColumn
+nRefKey
);
1476 if( addrOnce
) sqlite3VdbeJumpHere(v
, addrOnce
);
1477 addr
= 1 + sqlite3VdbeAddOp2(v
, OP_SorterSort
, iTab
, addrBreak
);
1479 codeOffset(v
, p
->iOffset
, addrContinue
);
1480 sqlite3VdbeAddOp3(v
, OP_SorterData
, iTab
, regSortOut
, iSortTab
);
1483 addr
= 1 + sqlite3VdbeAddOp2(v
, OP_Sort
, iTab
, addrBreak
); VdbeCoverage(v
);
1484 codeOffset(v
, p
->iOffset
, addrContinue
);
1488 for(i
=0, iCol
=nKey
+bSeq
-1; i
<nColumn
; i
++){
1489 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
1490 if( aOutEx
[i
].bSorterRef
) continue;
1492 if( aOutEx
[i
].u
.x
.iOrderByCol
==0 ) iCol
++;
1494 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
1495 if( pSort
->nDefer
){
1497 int regKey
= sqlite3GetTempRange(pParse
, nRefKey
);
1499 for(i
=0; i
<pSort
->nDefer
; i
++){
1500 int iCsr
= pSort
->aDefer
[i
].iCsr
;
1501 Table
*pTab
= pSort
->aDefer
[i
].pTab
;
1502 int nKey
= pSort
->aDefer
[i
].nKey
;
1504 sqlite3VdbeAddOp1(v
, OP_NullRow
, iCsr
);
1505 if( HasRowid(pTab
) ){
1506 sqlite3VdbeAddOp3(v
, OP_Column
, iSortTab
, iKey
++, regKey
);
1507 sqlite3VdbeAddOp3(v
, OP_SeekRowid
, iCsr
,
1508 sqlite3VdbeCurrentAddr(v
)+1, regKey
);
1512 assert( sqlite3PrimaryKeyIndex(pTab
)->nKeyCol
==nKey
);
1513 for(k
=0; k
<nKey
; k
++){
1514 sqlite3VdbeAddOp3(v
, OP_Column
, iSortTab
, iKey
++, regKey
+k
);
1516 iJmp
= sqlite3VdbeCurrentAddr(v
);
1517 sqlite3VdbeAddOp4Int(v
, OP_SeekGE
, iCsr
, iJmp
+2, regKey
, nKey
);
1518 sqlite3VdbeAddOp4Int(v
, OP_IdxLE
, iCsr
, iJmp
+3, regKey
, nKey
);
1519 sqlite3VdbeAddOp1(v
, OP_NullRow
, iCsr
);
1522 sqlite3ReleaseTempRange(pParse
, regKey
, nRefKey
);
1525 for(i
=nColumn
-1; i
>=0; i
--){
1526 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
1527 if( aOutEx
[i
].bSorterRef
){
1528 sqlite3ExprCode(pParse
, aOutEx
[i
].pExpr
, regRow
+i
);
1533 if( aOutEx
[i
].u
.x
.iOrderByCol
){
1534 iRead
= aOutEx
[i
].u
.x
.iOrderByCol
-1;
1538 sqlite3VdbeAddOp3(v
, OP_Column
, iSortTab
, iRead
, regRow
+i
);
1539 VdbeComment((v
, "%s", aOutEx
[i
].zName
?aOutEx
[i
].zName
: aOutEx
[i
].zSpan
));
1544 case SRT_EphemTab
: {
1545 sqlite3VdbeAddOp3(v
, OP_Column
, iSortTab
, nKey
+bSeq
, regRow
);
1546 sqlite3VdbeAddOp2(v
, OP_NewRowid
, iParm
, regRowid
);
1547 sqlite3VdbeAddOp3(v
, OP_Insert
, iParm
, regRow
, regRowid
);
1548 sqlite3VdbeChangeP5(v
, OPFLAG_APPEND
);
1551 #ifndef SQLITE_OMIT_SUBQUERY
1553 assert( nColumn
==sqlite3Strlen30(pDest
->zAffSdst
) );
1554 sqlite3VdbeAddOp4(v
, OP_MakeRecord
, regRow
, nColumn
, regRowid
,
1555 pDest
->zAffSdst
, nColumn
);
1556 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, iParm
, regRowid
, regRow
, nColumn
);
1560 /* The LIMIT clause will terminate the loop for us */
1565 assert( eDest
==SRT_Output
|| eDest
==SRT_Coroutine
);
1566 testcase( eDest
==SRT_Output
);
1567 testcase( eDest
==SRT_Coroutine
);
1568 if( eDest
==SRT_Output
){
1569 sqlite3VdbeAddOp2(v
, OP_ResultRow
, pDest
->iSdst
, nColumn
);
1571 sqlite3VdbeAddOp1(v
, OP_Yield
, pDest
->iSDParm
);
1577 if( eDest
==SRT_Set
){
1578 sqlite3ReleaseTempRange(pParse
, regRow
, nColumn
);
1580 sqlite3ReleaseTempReg(pParse
, regRow
);
1582 sqlite3ReleaseTempReg(pParse
, regRowid
);
1584 /* The bottom of the loop
1586 sqlite3VdbeResolveLabel(v
, addrContinue
);
1587 if( pSort
->sortFlags
& SORTFLAG_UseSorter
){
1588 sqlite3VdbeAddOp2(v
, OP_SorterNext
, iTab
, addr
); VdbeCoverage(v
);
1590 sqlite3VdbeAddOp2(v
, OP_Next
, iTab
, addr
); VdbeCoverage(v
);
1592 if( pSort
->regReturn
) sqlite3VdbeAddOp1(v
, OP_Return
, pSort
->regReturn
);
1593 sqlite3VdbeResolveLabel(v
, addrBreak
);
1597 ** Return a pointer to a string containing the 'declaration type' of the
1598 ** expression pExpr. The string may be treated as static by the caller.
1600 ** Also try to estimate the size of the returned value and return that
1601 ** result in *pEstWidth.
1603 ** The declaration type is the exact datatype definition extracted from the
1604 ** original CREATE TABLE statement if the expression is a column. The
1605 ** declaration type for a ROWID field is INTEGER. Exactly when an expression
1606 ** is considered a column can be complex in the presence of subqueries. The
1607 ** result-set expression in all of the following SELECT statements is
1608 ** considered a column by this function.
1610 ** SELECT col FROM tbl;
1611 ** SELECT (SELECT col FROM tbl;
1612 ** SELECT (SELECT col FROM tbl);
1613 ** SELECT abc FROM (SELECT col AS abc FROM tbl);
1615 ** The declaration type for any expression other than a column is NULL.
1617 ** This routine has either 3 or 6 parameters depending on whether or not
1618 ** the SQLITE_ENABLE_COLUMN_METADATA compile-time option is used.
1620 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1621 # define columnType(A,B,C,D,E) columnTypeImpl(A,B,C,D,E)
1622 #else /* if !defined(SQLITE_ENABLE_COLUMN_METADATA) */
1623 # define columnType(A,B,C,D,E) columnTypeImpl(A,B)
1625 static const char *columnTypeImpl(
1627 #ifndef SQLITE_ENABLE_COLUMN_METADATA
1631 const char **pzOrigDb
,
1632 const char **pzOrigTab
,
1633 const char **pzOrigCol
1636 char const *zType
= 0;
1638 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1639 char const *zOrigDb
= 0;
1640 char const *zOrigTab
= 0;
1641 char const *zOrigCol
= 0;
1645 assert( pNC
->pSrcList
!=0 );
1646 assert( pExpr
->op
!=TK_AGG_COLUMN
); /* This routine runes before aggregates
1648 switch( pExpr
->op
){
1650 /* The expression is a column. Locate the table the column is being
1651 ** extracted from in NameContext.pSrcList. This table may be real
1652 ** database table or a subquery.
1654 Table
*pTab
= 0; /* Table structure column is extracted from */
1655 Select
*pS
= 0; /* Select the column is extracted from */
1656 int iCol
= pExpr
->iColumn
; /* Index of column in pTab */
1657 while( pNC
&& !pTab
){
1658 SrcList
*pTabList
= pNC
->pSrcList
;
1659 for(j
=0;j
<pTabList
->nSrc
&& pTabList
->a
[j
].iCursor
!=pExpr
->iTable
;j
++);
1660 if( j
<pTabList
->nSrc
){
1661 pTab
= pTabList
->a
[j
].pTab
;
1662 pS
= pTabList
->a
[j
].pSelect
;
1669 /* At one time, code such as "SELECT new.x" within a trigger would
1670 ** cause this condition to run. Since then, we have restructured how
1671 ** trigger code is generated and so this condition is no longer
1672 ** possible. However, it can still be true for statements like
1675 ** CREATE TABLE t1(col INTEGER);
1676 ** SELECT (SELECT t1.col) FROM FROM t1;
1678 ** when columnType() is called on the expression "t1.col" in the
1679 ** sub-select. In this case, set the column type to NULL, even
1680 ** though it should really be "INTEGER".
1682 ** This is not a problem, as the column type of "t1.col" is never
1683 ** used. When columnType() is called on the expression
1684 ** "(SELECT t1.col)", the correct type is returned (see the TK_SELECT
1689 assert( pTab
&& pExpr
->y
.pTab
==pTab
);
1691 /* The "table" is actually a sub-select or a view in the FROM clause
1692 ** of the SELECT statement. Return the declaration type and origin
1693 ** data for the result-set column of the sub-select.
1695 if( iCol
>=0 && iCol
<pS
->pEList
->nExpr
){
1696 /* If iCol is less than zero, then the expression requests the
1697 ** rowid of the sub-select or view. This expression is legal (see
1698 ** test case misc2.2.2) - it always evaluates to NULL.
1701 Expr
*p
= pS
->pEList
->a
[iCol
].pExpr
;
1702 sNC
.pSrcList
= pS
->pSrc
;
1704 sNC
.pParse
= pNC
->pParse
;
1705 zType
= columnType(&sNC
, p
,&zOrigDb
,&zOrigTab
,&zOrigCol
);
1708 /* A real table or a CTE table */
1710 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1711 if( iCol
<0 ) iCol
= pTab
->iPKey
;
1712 assert( iCol
==XN_ROWID
|| (iCol
>=0 && iCol
<pTab
->nCol
) );
1717 zOrigCol
= pTab
->aCol
[iCol
].zName
;
1718 zType
= sqlite3ColumnType(&pTab
->aCol
[iCol
],0);
1720 zOrigTab
= pTab
->zName
;
1721 if( pNC
->pParse
&& pTab
->pSchema
){
1722 int iDb
= sqlite3SchemaToIndex(pNC
->pParse
->db
, pTab
->pSchema
);
1723 zOrigDb
= pNC
->pParse
->db
->aDb
[iDb
].zDbSName
;
1726 assert( iCol
==XN_ROWID
|| (iCol
>=0 && iCol
<pTab
->nCol
) );
1730 zType
= sqlite3ColumnType(&pTab
->aCol
[iCol
],0);
1736 #ifndef SQLITE_OMIT_SUBQUERY
1738 /* The expression is a sub-select. Return the declaration type and
1739 ** origin info for the single column in the result set of the SELECT
1743 Select
*pS
= pExpr
->x
.pSelect
;
1744 Expr
*p
= pS
->pEList
->a
[0].pExpr
;
1745 assert( ExprHasProperty(pExpr
, EP_xIsSelect
) );
1746 sNC
.pSrcList
= pS
->pSrc
;
1748 sNC
.pParse
= pNC
->pParse
;
1749 zType
= columnType(&sNC
, p
, &zOrigDb
, &zOrigTab
, &zOrigCol
);
1755 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1757 assert( pzOrigTab
&& pzOrigCol
);
1758 *pzOrigDb
= zOrigDb
;
1759 *pzOrigTab
= zOrigTab
;
1760 *pzOrigCol
= zOrigCol
;
1767 ** Generate code that will tell the VDBE the declaration types of columns
1768 ** in the result set.
1770 static void generateColumnTypes(
1771 Parse
*pParse
, /* Parser context */
1772 SrcList
*pTabList
, /* List of tables */
1773 ExprList
*pEList
/* Expressions defining the result set */
1775 #ifndef SQLITE_OMIT_DECLTYPE
1776 Vdbe
*v
= pParse
->pVdbe
;
1779 sNC
.pSrcList
= pTabList
;
1780 sNC
.pParse
= pParse
;
1782 for(i
=0; i
<pEList
->nExpr
; i
++){
1783 Expr
*p
= pEList
->a
[i
].pExpr
;
1785 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1786 const char *zOrigDb
= 0;
1787 const char *zOrigTab
= 0;
1788 const char *zOrigCol
= 0;
1789 zType
= columnType(&sNC
, p
, &zOrigDb
, &zOrigTab
, &zOrigCol
);
1791 /* The vdbe must make its own copy of the column-type and other
1792 ** column specific strings, in case the schema is reset before this
1793 ** virtual machine is deleted.
1795 sqlite3VdbeSetColName(v
, i
, COLNAME_DATABASE
, zOrigDb
, SQLITE_TRANSIENT
);
1796 sqlite3VdbeSetColName(v
, i
, COLNAME_TABLE
, zOrigTab
, SQLITE_TRANSIENT
);
1797 sqlite3VdbeSetColName(v
, i
, COLNAME_COLUMN
, zOrigCol
, SQLITE_TRANSIENT
);
1799 zType
= columnType(&sNC
, p
, 0, 0, 0);
1801 sqlite3VdbeSetColName(v
, i
, COLNAME_DECLTYPE
, zType
, SQLITE_TRANSIENT
);
1803 #endif /* !defined(SQLITE_OMIT_DECLTYPE) */
1808 ** Compute the column names for a SELECT statement.
1810 ** The only guarantee that SQLite makes about column names is that if the
1811 ** column has an AS clause assigning it a name, that will be the name used.
1812 ** That is the only documented guarantee. However, countless applications
1813 ** developed over the years have made baseless assumptions about column names
1814 ** and will break if those assumptions changes. Hence, use extreme caution
1815 ** when modifying this routine to avoid breaking legacy.
1817 ** See Also: sqlite3ColumnsFromExprList()
1819 ** The PRAGMA short_column_names and PRAGMA full_column_names settings are
1820 ** deprecated. The default setting is short=ON, full=OFF. 99.9% of all
1821 ** applications should operate this way. Nevertheless, we need to support the
1822 ** other modes for legacy:
1824 ** short=OFF, full=OFF: Column name is the text of the expression has it
1825 ** originally appears in the SELECT statement. In
1826 ** other words, the zSpan of the result expression.
1828 ** short=ON, full=OFF: (This is the default setting). If the result
1829 ** refers directly to a table column, then the
1830 ** result column name is just the table column
1831 ** name: COLUMN. Otherwise use zSpan.
1833 ** full=ON, short=ANY: If the result refers directly to a table column,
1834 ** then the result column name with the table name
1835 ** prefix, ex: TABLE.COLUMN. Otherwise use zSpan.
1837 static void generateColumnNames(
1838 Parse
*pParse
, /* Parser context */
1839 Select
*pSelect
/* Generate column names for this SELECT statement */
1841 Vdbe
*v
= pParse
->pVdbe
;
1846 sqlite3
*db
= pParse
->db
;
1847 int fullName
; /* TABLE.COLUMN if no AS clause and is a direct table ref */
1848 int srcName
; /* COLUMN or TABLE.COLUMN if no AS clause and is direct */
1850 #ifndef SQLITE_OMIT_EXPLAIN
1851 /* If this is an EXPLAIN, skip this step */
1852 if( pParse
->explain
){
1857 if( pParse
->colNamesSet
) return;
1858 /* Column names are determined by the left-most term of a compound select */
1859 while( pSelect
->pPrior
) pSelect
= pSelect
->pPrior
;
1860 SELECTTRACE(1,pParse
,pSelect
,("generating column names\n"));
1861 pTabList
= pSelect
->pSrc
;
1862 pEList
= pSelect
->pEList
;
1864 assert( pTabList
!=0 );
1865 pParse
->colNamesSet
= 1;
1866 fullName
= (db
->flags
& SQLITE_FullColNames
)!=0;
1867 srcName
= (db
->flags
& SQLITE_ShortColNames
)!=0 || fullName
;
1868 sqlite3VdbeSetNumCols(v
, pEList
->nExpr
);
1869 for(i
=0; i
<pEList
->nExpr
; i
++){
1870 Expr
*p
= pEList
->a
[i
].pExpr
;
1873 assert( p
->op
!=TK_AGG_COLUMN
); /* Agg processing has not run yet */
1874 assert( p
->op
!=TK_COLUMN
|| p
->y
.pTab
!=0 ); /* Covering idx not yet coded */
1875 if( pEList
->a
[i
].zName
){
1876 /* An AS clause always takes first priority */
1877 char *zName
= pEList
->a
[i
].zName
;
1878 sqlite3VdbeSetColName(v
, i
, COLNAME_NAME
, zName
, SQLITE_TRANSIENT
);
1879 }else if( srcName
&& p
->op
==TK_COLUMN
){
1881 int iCol
= p
->iColumn
;
1884 if( iCol
<0 ) iCol
= pTab
->iPKey
;
1885 assert( iCol
==-1 || (iCol
>=0 && iCol
<pTab
->nCol
) );
1889 zCol
= pTab
->aCol
[iCol
].zName
;
1893 zName
= sqlite3MPrintf(db
, "%s.%s", pTab
->zName
, zCol
);
1894 sqlite3VdbeSetColName(v
, i
, COLNAME_NAME
, zName
, SQLITE_DYNAMIC
);
1896 sqlite3VdbeSetColName(v
, i
, COLNAME_NAME
, zCol
, SQLITE_TRANSIENT
);
1899 const char *z
= pEList
->a
[i
].zSpan
;
1900 z
= z
==0 ? sqlite3MPrintf(db
, "column%d", i
+1) : sqlite3DbStrDup(db
, z
);
1901 sqlite3VdbeSetColName(v
, i
, COLNAME_NAME
, z
, SQLITE_DYNAMIC
);
1904 generateColumnTypes(pParse
, pTabList
, pEList
);
1908 ** Given an expression list (which is really the list of expressions
1909 ** that form the result set of a SELECT statement) compute appropriate
1910 ** column names for a table that would hold the expression list.
1912 ** All column names will be unique.
1914 ** Only the column names are computed. Column.zType, Column.zColl,
1915 ** and other fields of Column are zeroed.
1917 ** Return SQLITE_OK on success. If a memory allocation error occurs,
1918 ** store NULL in *paCol and 0 in *pnCol and return SQLITE_NOMEM.
1920 ** The only guarantee that SQLite makes about column names is that if the
1921 ** column has an AS clause assigning it a name, that will be the name used.
1922 ** That is the only documented guarantee. However, countless applications
1923 ** developed over the years have made baseless assumptions about column names
1924 ** and will break if those assumptions changes. Hence, use extreme caution
1925 ** when modifying this routine to avoid breaking legacy.
1927 ** See Also: generateColumnNames()
1929 int sqlite3ColumnsFromExprList(
1930 Parse
*pParse
, /* Parsing context */
1931 ExprList
*pEList
, /* Expr list from which to derive column names */
1932 i16
*pnCol
, /* Write the number of columns here */
1933 Column
**paCol
/* Write the new column list here */
1935 sqlite3
*db
= pParse
->db
; /* Database connection */
1936 int i
, j
; /* Loop counters */
1937 u32 cnt
; /* Index added to make the name unique */
1938 Column
*aCol
, *pCol
; /* For looping over result columns */
1939 int nCol
; /* Number of columns in the result set */
1940 char *zName
; /* Column name */
1941 int nName
; /* Size of name in zName[] */
1942 Hash ht
; /* Hash table of column names */
1944 sqlite3HashInit(&ht
);
1946 nCol
= pEList
->nExpr
;
1947 aCol
= sqlite3DbMallocZero(db
, sizeof(aCol
[0])*nCol
);
1948 testcase( aCol
==0 );
1949 if( nCol
>32767 ) nCol
= 32767;
1954 assert( nCol
==(i16
)nCol
);
1958 for(i
=0, pCol
=aCol
; i
<nCol
&& !db
->mallocFailed
; i
++, pCol
++){
1959 /* Get an appropriate name for the column
1961 if( (zName
= pEList
->a
[i
].zName
)!=0 ){
1962 /* If the column contains an "AS <name>" phrase, use <name> as the name */
1964 Expr
*pColExpr
= sqlite3ExprSkipCollate(pEList
->a
[i
].pExpr
);
1965 while( pColExpr
->op
==TK_DOT
){
1966 pColExpr
= pColExpr
->pRight
;
1967 assert( pColExpr
!=0 );
1969 assert( pColExpr
->op
!=TK_AGG_COLUMN
);
1970 if( pColExpr
->op
==TK_COLUMN
){
1971 /* For columns use the column name name */
1972 int iCol
= pColExpr
->iColumn
;
1973 Table
*pTab
= pColExpr
->y
.pTab
;
1975 if( iCol
<0 ) iCol
= pTab
->iPKey
;
1976 zName
= iCol
>=0 ? pTab
->aCol
[iCol
].zName
: "rowid";
1977 }else if( pColExpr
->op
==TK_ID
){
1978 assert( !ExprHasProperty(pColExpr
, EP_IntValue
) );
1979 zName
= pColExpr
->u
.zToken
;
1981 /* Use the original text of the column expression as its name */
1982 zName
= pEList
->a
[i
].zSpan
;
1986 zName
= sqlite3DbStrDup(db
, zName
);
1988 zName
= sqlite3MPrintf(db
,"column%d",i
+1);
1991 /* Make sure the column name is unique. If the name is not unique,
1992 ** append an integer to the name so that it becomes unique.
1995 while( zName
&& sqlite3HashFind(&ht
, zName
)!=0 ){
1996 nName
= sqlite3Strlen30(zName
);
1998 for(j
=nName
-1; j
>0 && sqlite3Isdigit(zName
[j
]); j
--){}
1999 if( zName
[j
]==':' ) nName
= j
;
2001 zName
= sqlite3MPrintf(db
, "%.*z:%u", nName
, zName
, ++cnt
);
2002 if( cnt
>3 ) sqlite3_randomness(sizeof(cnt
), &cnt
);
2004 pCol
->zName
= zName
;
2005 sqlite3ColumnPropertiesFromName(0, pCol
);
2006 if( zName
&& sqlite3HashInsert(&ht
, zName
, pCol
)==pCol
){
2007 sqlite3OomFault(db
);
2010 sqlite3HashClear(&ht
);
2011 if( db
->mallocFailed
){
2013 sqlite3DbFree(db
, aCol
[j
].zName
);
2015 sqlite3DbFree(db
, aCol
);
2018 return SQLITE_NOMEM_BKPT
;
2024 ** Add type and collation information to a column list based on
2025 ** a SELECT statement.
2027 ** The column list presumably came from selectColumnNamesFromExprList().
2028 ** The column list has only names, not types or collations. This
2029 ** routine goes through and adds the types and collations.
2031 ** This routine requires that all identifiers in the SELECT
2032 ** statement be resolved.
2034 void sqlite3SelectAddColumnTypeAndCollation(
2035 Parse
*pParse
, /* Parsing contexts */
2036 Table
*pTab
, /* Add column type information to this table */
2037 Select
*pSelect
/* SELECT used to determine types and collations */
2039 sqlite3
*db
= pParse
->db
;
2045 struct ExprList_item
*a
;
2047 assert( pSelect
!=0 );
2048 assert( (pSelect
->selFlags
& SF_Resolved
)!=0 );
2049 assert( pTab
->nCol
==pSelect
->pEList
->nExpr
|| db
->mallocFailed
);
2050 if( db
->mallocFailed
) return;
2051 memset(&sNC
, 0, sizeof(sNC
));
2052 sNC
.pSrcList
= pSelect
->pSrc
;
2053 a
= pSelect
->pEList
->a
;
2054 for(i
=0, pCol
=pTab
->aCol
; i
<pTab
->nCol
; i
++, pCol
++){
2058 zType
= columnType(&sNC
, p
, 0, 0, 0);
2059 /* pCol->szEst = ... // Column size est for SELECT tables never used */
2060 pCol
->affinity
= sqlite3ExprAffinity(p
);
2062 m
= sqlite3Strlen30(zType
);
2063 n
= sqlite3Strlen30(pCol
->zName
);
2064 pCol
->zName
= sqlite3DbReallocOrFree(db
, pCol
->zName
, n
+m
+2);
2066 memcpy(&pCol
->zName
[n
+1], zType
, m
+1);
2067 pCol
->colFlags
|= COLFLAG_HASTYPE
;
2070 if( pCol
->affinity
==0 ) pCol
->affinity
= SQLITE_AFF_BLOB
;
2071 pColl
= sqlite3ExprCollSeq(pParse
, p
);
2072 if( pColl
&& pCol
->zColl
==0 ){
2073 pCol
->zColl
= sqlite3DbStrDup(db
, pColl
->zName
);
2076 pTab
->szTabRow
= 1; /* Any non-zero value works */
2080 ** Given a SELECT statement, generate a Table structure that describes
2081 ** the result set of that SELECT.
2083 Table
*sqlite3ResultSetOfSelect(Parse
*pParse
, Select
*pSelect
){
2085 sqlite3
*db
= pParse
->db
;
2088 savedFlags
= db
->flags
;
2089 db
->flags
&= ~(u64
)SQLITE_FullColNames
;
2090 db
->flags
|= SQLITE_ShortColNames
;
2091 sqlite3SelectPrep(pParse
, pSelect
, 0);
2092 db
->flags
= savedFlags
;
2093 if( pParse
->nErr
) return 0;
2094 while( pSelect
->pPrior
) pSelect
= pSelect
->pPrior
;
2095 pTab
= sqlite3DbMallocZero(db
, sizeof(Table
) );
2099 /* The sqlite3ResultSetOfSelect() is only used n contexts where lookaside
2101 assert( db
->lookaside
.bDisable
);
2104 pTab
->nRowLogEst
= 200; assert( 200==sqlite3LogEst(1048576) );
2105 sqlite3ColumnsFromExprList(pParse
, pSelect
->pEList
, &pTab
->nCol
, &pTab
->aCol
);
2106 sqlite3SelectAddColumnTypeAndCollation(pParse
, pTab
, pSelect
);
2108 if( db
->mallocFailed
){
2109 sqlite3DeleteTable(db
, pTab
);
2116 ** Get a VDBE for the given parser context. Create a new one if necessary.
2117 ** If an error occurs, return NULL and leave a message in pParse.
2119 Vdbe
*sqlite3GetVdbe(Parse
*pParse
){
2120 if( pParse
->pVdbe
){
2121 return pParse
->pVdbe
;
2123 if( pParse
->pToplevel
==0
2124 && OptimizationEnabled(pParse
->db
,SQLITE_FactorOutConst
)
2126 pParse
->okConstFactor
= 1;
2128 return sqlite3VdbeCreate(pParse
);
2133 ** Compute the iLimit and iOffset fields of the SELECT based on the
2134 ** pLimit expressions. pLimit->pLeft and pLimit->pRight hold the expressions
2135 ** that appear in the original SQL statement after the LIMIT and OFFSET
2136 ** keywords. Or NULL if those keywords are omitted. iLimit and iOffset
2137 ** are the integer memory register numbers for counters used to compute
2138 ** the limit and offset. If there is no limit and/or offset, then
2139 ** iLimit and iOffset are negative.
2141 ** This routine changes the values of iLimit and iOffset only if
2142 ** a limit or offset is defined by pLimit->pLeft and pLimit->pRight. iLimit
2143 ** and iOffset should have been preset to appropriate default values (zero)
2144 ** prior to calling this routine.
2146 ** The iOffset register (if it exists) is initialized to the value
2147 ** of the OFFSET. The iLimit register is initialized to LIMIT. Register
2148 ** iOffset+1 is initialized to LIMIT+OFFSET.
2150 ** Only if pLimit->pLeft!=0 do the limit registers get
2151 ** redefined. The UNION ALL operator uses this property to force
2152 ** the reuse of the same limit and offset registers across multiple
2153 ** SELECT statements.
2155 static void computeLimitRegisters(Parse
*pParse
, Select
*p
, int iBreak
){
2160 Expr
*pLimit
= p
->pLimit
;
2162 if( p
->iLimit
) return;
2165 ** "LIMIT -1" always shows all rows. There is some
2166 ** controversy about what the correct behavior should be.
2167 ** The current implementation interprets "LIMIT 0" to mean
2171 assert( pLimit
->op
==TK_LIMIT
);
2172 assert( pLimit
->pLeft
!=0 );
2173 p
->iLimit
= iLimit
= ++pParse
->nMem
;
2174 v
= sqlite3GetVdbe(pParse
);
2176 if( sqlite3ExprIsInteger(pLimit
->pLeft
, &n
) ){
2177 sqlite3VdbeAddOp2(v
, OP_Integer
, n
, iLimit
);
2178 VdbeComment((v
, "LIMIT counter"));
2180 sqlite3VdbeGoto(v
, iBreak
);
2181 }else if( n
>=0 && p
->nSelectRow
>sqlite3LogEst((u64
)n
) ){
2182 p
->nSelectRow
= sqlite3LogEst((u64
)n
);
2183 p
->selFlags
|= SF_FixedLimit
;
2186 sqlite3ExprCode(pParse
, pLimit
->pLeft
, iLimit
);
2187 sqlite3VdbeAddOp1(v
, OP_MustBeInt
, iLimit
); VdbeCoverage(v
);
2188 VdbeComment((v
, "LIMIT counter"));
2189 sqlite3VdbeAddOp2(v
, OP_IfNot
, iLimit
, iBreak
); VdbeCoverage(v
);
2191 if( pLimit
->pRight
){
2192 p
->iOffset
= iOffset
= ++pParse
->nMem
;
2193 pParse
->nMem
++; /* Allocate an extra register for limit+offset */
2194 sqlite3ExprCode(pParse
, pLimit
->pRight
, iOffset
);
2195 sqlite3VdbeAddOp1(v
, OP_MustBeInt
, iOffset
); VdbeCoverage(v
);
2196 VdbeComment((v
, "OFFSET counter"));
2197 sqlite3VdbeAddOp3(v
, OP_OffsetLimit
, iLimit
, iOffset
+1, iOffset
);
2198 VdbeComment((v
, "LIMIT+OFFSET"));
2203 #ifndef SQLITE_OMIT_COMPOUND_SELECT
2205 ** Return the appropriate collating sequence for the iCol-th column of
2206 ** the result set for the compound-select statement "p". Return NULL if
2207 ** the column has no default collating sequence.
2209 ** The collating sequence for the compound select is taken from the
2210 ** left-most term of the select that has a collating sequence.
2212 static CollSeq
*multiSelectCollSeq(Parse
*pParse
, Select
*p
, int iCol
){
2215 pRet
= multiSelectCollSeq(pParse
, p
->pPrior
, iCol
);
2220 /* iCol must be less than p->pEList->nExpr. Otherwise an error would
2221 ** have been thrown during name resolution and we would not have gotten
2223 if( pRet
==0 && ALWAYS(iCol
<p
->pEList
->nExpr
) ){
2224 pRet
= sqlite3ExprCollSeq(pParse
, p
->pEList
->a
[iCol
].pExpr
);
2230 ** The select statement passed as the second parameter is a compound SELECT
2231 ** with an ORDER BY clause. This function allocates and returns a KeyInfo
2232 ** structure suitable for implementing the ORDER BY.
2234 ** Space to hold the KeyInfo structure is obtained from malloc. The calling
2235 ** function is responsible for ensuring that this structure is eventually
2238 static KeyInfo
*multiSelectOrderByKeyInfo(Parse
*pParse
, Select
*p
, int nExtra
){
2239 ExprList
*pOrderBy
= p
->pOrderBy
;
2240 int nOrderBy
= p
->pOrderBy
->nExpr
;
2241 sqlite3
*db
= pParse
->db
;
2242 KeyInfo
*pRet
= sqlite3KeyInfoAlloc(db
, nOrderBy
+nExtra
, 1);
2245 for(i
=0; i
<nOrderBy
; i
++){
2246 struct ExprList_item
*pItem
= &pOrderBy
->a
[i
];
2247 Expr
*pTerm
= pItem
->pExpr
;
2250 if( pTerm
->flags
& EP_Collate
){
2251 pColl
= sqlite3ExprCollSeq(pParse
, pTerm
);
2253 pColl
= multiSelectCollSeq(pParse
, p
, pItem
->u
.x
.iOrderByCol
-1);
2254 if( pColl
==0 ) pColl
= db
->pDfltColl
;
2255 pOrderBy
->a
[i
].pExpr
=
2256 sqlite3ExprAddCollateString(pParse
, pTerm
, pColl
->zName
);
2258 assert( sqlite3KeyInfoIsWriteable(pRet
) );
2259 pRet
->aColl
[i
] = pColl
;
2260 pRet
->aSortOrder
[i
] = pOrderBy
->a
[i
].sortOrder
;
2267 #ifndef SQLITE_OMIT_CTE
2269 ** This routine generates VDBE code to compute the content of a WITH RECURSIVE
2270 ** query of the form:
2272 ** <recursive-table> AS (<setup-query> UNION [ALL] <recursive-query>)
2273 ** \___________/ \_______________/
2277 ** There is exactly one reference to the recursive-table in the FROM clause
2278 ** of recursive-query, marked with the SrcList->a[].fg.isRecursive flag.
2280 ** The setup-query runs once to generate an initial set of rows that go
2281 ** into a Queue table. Rows are extracted from the Queue table one by
2282 ** one. Each row extracted from Queue is output to pDest. Then the single
2283 ** extracted row (now in the iCurrent table) becomes the content of the
2284 ** recursive-table for a recursive-query run. The output of the recursive-query
2285 ** is added back into the Queue table. Then another row is extracted from Queue
2286 ** and the iteration continues until the Queue table is empty.
2288 ** If the compound query operator is UNION then no duplicate rows are ever
2289 ** inserted into the Queue table. The iDistinct table keeps a copy of all rows
2290 ** that have ever been inserted into Queue and causes duplicates to be
2291 ** discarded. If the operator is UNION ALL, then duplicates are allowed.
2293 ** If the query has an ORDER BY, then entries in the Queue table are kept in
2294 ** ORDER BY order and the first entry is extracted for each cycle. Without
2295 ** an ORDER BY, the Queue table is just a FIFO.
2297 ** If a LIMIT clause is provided, then the iteration stops after LIMIT rows
2298 ** have been output to pDest. A LIMIT of zero means to output no rows and a
2299 ** negative LIMIT means to output all rows. If there is also an OFFSET clause
2300 ** with a positive value, then the first OFFSET outputs are discarded rather
2301 ** than being sent to pDest. The LIMIT count does not begin until after OFFSET
2302 ** rows have been skipped.
2304 static void generateWithRecursiveQuery(
2305 Parse
*pParse
, /* Parsing context */
2306 Select
*p
, /* The recursive SELECT to be coded */
2307 SelectDest
*pDest
/* What to do with query results */
2309 SrcList
*pSrc
= p
->pSrc
; /* The FROM clause of the recursive query */
2310 int nCol
= p
->pEList
->nExpr
; /* Number of columns in the recursive table */
2311 Vdbe
*v
= pParse
->pVdbe
; /* The prepared statement under construction */
2312 Select
*pSetup
= p
->pPrior
; /* The setup query */
2313 int addrTop
; /* Top of the loop */
2314 int addrCont
, addrBreak
; /* CONTINUE and BREAK addresses */
2315 int iCurrent
= 0; /* The Current table */
2316 int regCurrent
; /* Register holding Current table */
2317 int iQueue
; /* The Queue table */
2318 int iDistinct
= 0; /* To ensure unique results if UNION */
2319 int eDest
= SRT_Fifo
; /* How to write to Queue */
2320 SelectDest destQueue
; /* SelectDest targetting the Queue table */
2321 int i
; /* Loop counter */
2322 int rc
; /* Result code */
2323 ExprList
*pOrderBy
; /* The ORDER BY clause */
2324 Expr
*pLimit
; /* Saved LIMIT and OFFSET */
2325 int regLimit
, regOffset
; /* Registers used by LIMIT and OFFSET */
2327 #ifndef SQLITE_OMIT_WINDOWFUNC
2329 sqlite3ErrorMsg(pParse
, "cannot use window functions in recursive queries");
2334 /* Obtain authorization to do a recursive query */
2335 if( sqlite3AuthCheck(pParse
, SQLITE_RECURSIVE
, 0, 0, 0) ) return;
2337 /* Process the LIMIT and OFFSET clauses, if they exist */
2338 addrBreak
= sqlite3VdbeMakeLabel(pParse
);
2339 p
->nSelectRow
= 320; /* 4 billion rows */
2340 computeLimitRegisters(pParse
, p
, addrBreak
);
2342 regLimit
= p
->iLimit
;
2343 regOffset
= p
->iOffset
;
2345 p
->iLimit
= p
->iOffset
= 0;
2346 pOrderBy
= p
->pOrderBy
;
2348 /* Locate the cursor number of the Current table */
2349 for(i
=0; ALWAYS(i
<pSrc
->nSrc
); i
++){
2350 if( pSrc
->a
[i
].fg
.isRecursive
){
2351 iCurrent
= pSrc
->a
[i
].iCursor
;
2356 /* Allocate cursors numbers for Queue and Distinct. The cursor number for
2357 ** the Distinct table must be exactly one greater than Queue in order
2358 ** for the SRT_DistFifo and SRT_DistQueue destinations to work. */
2359 iQueue
= pParse
->nTab
++;
2360 if( p
->op
==TK_UNION
){
2361 eDest
= pOrderBy
? SRT_DistQueue
: SRT_DistFifo
;
2362 iDistinct
= pParse
->nTab
++;
2364 eDest
= pOrderBy
? SRT_Queue
: SRT_Fifo
;
2366 sqlite3SelectDestInit(&destQueue
, eDest
, iQueue
);
2368 /* Allocate cursors for Current, Queue, and Distinct. */
2369 regCurrent
= ++pParse
->nMem
;
2370 sqlite3VdbeAddOp3(v
, OP_OpenPseudo
, iCurrent
, regCurrent
, nCol
);
2372 KeyInfo
*pKeyInfo
= multiSelectOrderByKeyInfo(pParse
, p
, 1);
2373 sqlite3VdbeAddOp4(v
, OP_OpenEphemeral
, iQueue
, pOrderBy
->nExpr
+2, 0,
2374 (char*)pKeyInfo
, P4_KEYINFO
);
2375 destQueue
.pOrderBy
= pOrderBy
;
2377 sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, iQueue
, nCol
);
2379 VdbeComment((v
, "Queue table"));
2381 p
->addrOpenEphm
[0] = sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, iDistinct
, 0);
2382 p
->selFlags
|= SF_UsesEphemeral
;
2385 /* Detach the ORDER BY clause from the compound SELECT */
2388 /* Store the results of the setup-query in Queue. */
2390 ExplainQueryPlan((pParse
, 1, "SETUP"));
2391 rc
= sqlite3Select(pParse
, pSetup
, &destQueue
);
2393 if( rc
) goto end_of_recursive_query
;
2395 /* Find the next row in the Queue and output that row */
2396 addrTop
= sqlite3VdbeAddOp2(v
, OP_Rewind
, iQueue
, addrBreak
); VdbeCoverage(v
);
2398 /* Transfer the next row in Queue over to Current */
2399 sqlite3VdbeAddOp1(v
, OP_NullRow
, iCurrent
); /* To reset column cache */
2401 sqlite3VdbeAddOp3(v
, OP_Column
, iQueue
, pOrderBy
->nExpr
+1, regCurrent
);
2403 sqlite3VdbeAddOp2(v
, OP_RowData
, iQueue
, regCurrent
);
2405 sqlite3VdbeAddOp1(v
, OP_Delete
, iQueue
);
2407 /* Output the single row in Current */
2408 addrCont
= sqlite3VdbeMakeLabel(pParse
);
2409 codeOffset(v
, regOffset
, addrCont
);
2410 selectInnerLoop(pParse
, p
, iCurrent
,
2411 0, 0, pDest
, addrCont
, addrBreak
);
2413 sqlite3VdbeAddOp2(v
, OP_DecrJumpZero
, regLimit
, addrBreak
);
2416 sqlite3VdbeResolveLabel(v
, addrCont
);
2418 /* Execute the recursive SELECT taking the single row in Current as
2419 ** the value for the recursive-table. Store the results in the Queue.
2421 if( p
->selFlags
& SF_Aggregate
){
2422 sqlite3ErrorMsg(pParse
, "recursive aggregate queries not supported");
2425 ExplainQueryPlan((pParse
, 1, "RECURSIVE STEP"));
2426 sqlite3Select(pParse
, p
, &destQueue
);
2427 assert( p
->pPrior
==0 );
2431 /* Keep running the loop until the Queue is empty */
2432 sqlite3VdbeGoto(v
, addrTop
);
2433 sqlite3VdbeResolveLabel(v
, addrBreak
);
2435 end_of_recursive_query
:
2436 sqlite3ExprListDelete(pParse
->db
, p
->pOrderBy
);
2437 p
->pOrderBy
= pOrderBy
;
2441 #endif /* SQLITE_OMIT_CTE */
2443 /* Forward references */
2444 static int multiSelectOrderBy(
2445 Parse
*pParse
, /* Parsing context */
2446 Select
*p
, /* The right-most of SELECTs to be coded */
2447 SelectDest
*pDest
/* What to do with query results */
2451 ** Handle the special case of a compound-select that originates from a
2452 ** VALUES clause. By handling this as a special case, we avoid deep
2453 ** recursion, and thus do not need to enforce the SQLITE_LIMIT_COMPOUND_SELECT
2454 ** on a VALUES clause.
2456 ** Because the Select object originates from a VALUES clause:
2457 ** (1) There is no LIMIT or OFFSET or else there is a LIMIT of exactly 1
2458 ** (2) All terms are UNION ALL
2459 ** (3) There is no ORDER BY clause
2461 ** The "LIMIT of exactly 1" case of condition (1) comes about when a VALUES
2462 ** clause occurs within scalar expression (ex: "SELECT (VALUES(1),(2),(3))").
2463 ** The sqlite3CodeSubselect will have added the LIMIT 1 clause in tht case.
2464 ** Since the limit is exactly 1, we only need to evalutes the left-most VALUES.
2466 static int multiSelectValues(
2467 Parse
*pParse
, /* Parsing context */
2468 Select
*p
, /* The right-most of SELECTs to be coded */
2469 SelectDest
*pDest
/* What to do with query results */
2473 int bShowAll
= p
->pLimit
==0;
2474 assert( p
->selFlags
& SF_MultiValue
);
2476 assert( p
->selFlags
& SF_Values
);
2477 assert( p
->op
==TK_ALL
|| (p
->op
==TK_SELECT
&& p
->pPrior
==0) );
2478 assert( p
->pNext
==0 || p
->pEList
->nExpr
==p
->pNext
->pEList
->nExpr
);
2479 if( p
->pPrior
==0 ) break;
2480 assert( p
->pPrior
->pNext
==p
);
2484 ExplainQueryPlan((pParse
, 0, "SCAN %d CONSTANT ROW%s", nRow
,
2485 nRow
==1 ? "" : "S"));
2487 selectInnerLoop(pParse
, p
, -1, 0, 0, pDest
, 1, 1);
2488 if( !bShowAll
) break;
2489 p
->nSelectRow
= nRow
;
2496 ** This routine is called to process a compound query form from
2497 ** two or more separate queries using UNION, UNION ALL, EXCEPT, or
2500 ** "p" points to the right-most of the two queries. the query on the
2501 ** left is p->pPrior. The left query could also be a compound query
2502 ** in which case this routine will be called recursively.
2504 ** The results of the total query are to be written into a destination
2505 ** of type eDest with parameter iParm.
2507 ** Example 1: Consider a three-way compound SQL statement.
2509 ** SELECT a FROM t1 UNION SELECT b FROM t2 UNION SELECT c FROM t3
2511 ** This statement is parsed up as follows:
2515 ** `-----> SELECT b FROM t2
2517 ** `------> SELECT a FROM t1
2519 ** The arrows in the diagram above represent the Select.pPrior pointer.
2520 ** So if this routine is called with p equal to the t3 query, then
2521 ** pPrior will be the t2 query. p->op will be TK_UNION in this case.
2523 ** Notice that because of the way SQLite parses compound SELECTs, the
2524 ** individual selects always group from left to right.
2526 static int multiSelect(
2527 Parse
*pParse
, /* Parsing context */
2528 Select
*p
, /* The right-most of SELECTs to be coded */
2529 SelectDest
*pDest
/* What to do with query results */
2531 int rc
= SQLITE_OK
; /* Success code from a subroutine */
2532 Select
*pPrior
; /* Another SELECT immediately to our left */
2533 Vdbe
*v
; /* Generate code to this VDBE */
2534 SelectDest dest
; /* Alternative data destination */
2535 Select
*pDelete
= 0; /* Chain of simple selects to delete */
2536 sqlite3
*db
; /* Database connection */
2538 /* Make sure there is no ORDER BY or LIMIT clause on prior SELECTs. Only
2539 ** the last (right-most) SELECT in the series may have an ORDER BY or LIMIT.
2541 assert( p
&& p
->pPrior
); /* Calling function guarantees this much */
2542 assert( (p
->selFlags
& SF_Recursive
)==0 || p
->op
==TK_ALL
|| p
->op
==TK_UNION
);
2546 if( pPrior
->pOrderBy
|| pPrior
->pLimit
){
2547 sqlite3ErrorMsg(pParse
,"%s clause should come after %s not before",
2548 pPrior
->pOrderBy
!=0 ? "ORDER BY" : "LIMIT", selectOpName(p
->op
));
2550 goto multi_select_end
;
2553 v
= sqlite3GetVdbe(pParse
);
2554 assert( v
!=0 ); /* The VDBE already created by calling function */
2556 /* Create the destination temporary table if necessary
2558 if( dest
.eDest
==SRT_EphemTab
){
2559 assert( p
->pEList
);
2560 sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, dest
.iSDParm
, p
->pEList
->nExpr
);
2561 dest
.eDest
= SRT_Table
;
2564 /* Special handling for a compound-select that originates as a VALUES clause.
2566 if( p
->selFlags
& SF_MultiValue
){
2567 rc
= multiSelectValues(pParse
, p
, &dest
);
2568 goto multi_select_end
;
2571 /* Make sure all SELECTs in the statement have the same number of elements
2572 ** in their result sets.
2574 assert( p
->pEList
&& pPrior
->pEList
);
2575 assert( p
->pEList
->nExpr
==pPrior
->pEList
->nExpr
);
2577 #ifndef SQLITE_OMIT_CTE
2578 if( p
->selFlags
& SF_Recursive
){
2579 generateWithRecursiveQuery(pParse
, p
, &dest
);
2583 /* Compound SELECTs that have an ORDER BY clause are handled separately.
2586 return multiSelectOrderBy(pParse
, p
, pDest
);
2589 #ifndef SQLITE_OMIT_EXPLAIN
2590 if( pPrior
->pPrior
==0 ){
2591 ExplainQueryPlan((pParse
, 1, "COMPOUND QUERY"));
2592 ExplainQueryPlan((pParse
, 1, "LEFT-MOST SUBQUERY"));
2596 /* Generate code for the left and right SELECT statements.
2602 assert( !pPrior
->pLimit
);
2603 pPrior
->iLimit
= p
->iLimit
;
2604 pPrior
->iOffset
= p
->iOffset
;
2605 pPrior
->pLimit
= p
->pLimit
;
2606 rc
= sqlite3Select(pParse
, pPrior
, &dest
);
2609 goto multi_select_end
;
2612 p
->iLimit
= pPrior
->iLimit
;
2613 p
->iOffset
= pPrior
->iOffset
;
2615 addr
= sqlite3VdbeAddOp1(v
, OP_IfNot
, p
->iLimit
); VdbeCoverage(v
);
2616 VdbeComment((v
, "Jump ahead if LIMIT reached"));
2618 sqlite3VdbeAddOp3(v
, OP_OffsetLimit
,
2619 p
->iLimit
, p
->iOffset
+1, p
->iOffset
);
2622 ExplainQueryPlan((pParse
, 1, "UNION ALL"));
2623 rc
= sqlite3Select(pParse
, p
, &dest
);
2624 testcase( rc
!=SQLITE_OK
);
2625 pDelete
= p
->pPrior
;
2627 p
->nSelectRow
= sqlite3LogEstAdd(p
->nSelectRow
, pPrior
->nSelectRow
);
2629 && sqlite3ExprIsInteger(pPrior
->pLimit
->pLeft
, &nLimit
)
2630 && nLimit
>0 && p
->nSelectRow
> sqlite3LogEst((u64
)nLimit
)
2632 p
->nSelectRow
= sqlite3LogEst((u64
)nLimit
);
2635 sqlite3VdbeJumpHere(v
, addr
);
2641 int unionTab
; /* Cursor number of the temp table holding result */
2642 u8 op
= 0; /* One of the SRT_ operations to apply to self */
2643 int priorOp
; /* The SRT_ operation to apply to prior selects */
2644 Expr
*pLimit
; /* Saved values of p->nLimit */
2646 SelectDest uniondest
;
2648 testcase( p
->op
==TK_EXCEPT
);
2649 testcase( p
->op
==TK_UNION
);
2650 priorOp
= SRT_Union
;
2651 if( dest
.eDest
==priorOp
){
2652 /* We can reuse a temporary table generated by a SELECT to our
2655 assert( p
->pLimit
==0 ); /* Not allowed on leftward elements */
2656 unionTab
= dest
.iSDParm
;
2658 /* We will need to create our own temporary table to hold the
2659 ** intermediate results.
2661 unionTab
= pParse
->nTab
++;
2662 assert( p
->pOrderBy
==0 );
2663 addr
= sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, unionTab
, 0);
2664 assert( p
->addrOpenEphm
[0] == -1 );
2665 p
->addrOpenEphm
[0] = addr
;
2666 findRightmost(p
)->selFlags
|= SF_UsesEphemeral
;
2667 assert( p
->pEList
);
2670 /* Code the SELECT statements to our left
2672 assert( !pPrior
->pOrderBy
);
2673 sqlite3SelectDestInit(&uniondest
, priorOp
, unionTab
);
2674 rc
= sqlite3Select(pParse
, pPrior
, &uniondest
);
2676 goto multi_select_end
;
2679 /* Code the current SELECT statement
2681 if( p
->op
==TK_EXCEPT
){
2684 assert( p
->op
==TK_UNION
);
2690 uniondest
.eDest
= op
;
2691 ExplainQueryPlan((pParse
, 1, "%s USING TEMP B-TREE",
2692 selectOpName(p
->op
)));
2693 rc
= sqlite3Select(pParse
, p
, &uniondest
);
2694 testcase( rc
!=SQLITE_OK
);
2695 /* Query flattening in sqlite3Select() might refill p->pOrderBy.
2696 ** Be sure to delete p->pOrderBy, therefore, to avoid a memory leak. */
2697 sqlite3ExprListDelete(db
, p
->pOrderBy
);
2698 pDelete
= p
->pPrior
;
2701 if( p
->op
==TK_UNION
){
2702 p
->nSelectRow
= sqlite3LogEstAdd(p
->nSelectRow
, pPrior
->nSelectRow
);
2704 sqlite3ExprDelete(db
, p
->pLimit
);
2709 /* Convert the data in the temporary table into whatever form
2710 ** it is that we currently need.
2712 assert( unionTab
==dest
.iSDParm
|| dest
.eDest
!=priorOp
);
2713 if( dest
.eDest
!=priorOp
){
2714 int iCont
, iBreak
, iStart
;
2715 assert( p
->pEList
);
2716 iBreak
= sqlite3VdbeMakeLabel(pParse
);
2717 iCont
= sqlite3VdbeMakeLabel(pParse
);
2718 computeLimitRegisters(pParse
, p
, iBreak
);
2719 sqlite3VdbeAddOp2(v
, OP_Rewind
, unionTab
, iBreak
); VdbeCoverage(v
);
2720 iStart
= sqlite3VdbeCurrentAddr(v
);
2721 selectInnerLoop(pParse
, p
, unionTab
,
2722 0, 0, &dest
, iCont
, iBreak
);
2723 sqlite3VdbeResolveLabel(v
, iCont
);
2724 sqlite3VdbeAddOp2(v
, OP_Next
, unionTab
, iStart
); VdbeCoverage(v
);
2725 sqlite3VdbeResolveLabel(v
, iBreak
);
2726 sqlite3VdbeAddOp2(v
, OP_Close
, unionTab
, 0);
2730 default: assert( p
->op
==TK_INTERSECT
); {
2732 int iCont
, iBreak
, iStart
;
2735 SelectDest intersectdest
;
2738 /* INTERSECT is different from the others since it requires
2739 ** two temporary tables. Hence it has its own case. Begin
2740 ** by allocating the tables we will need.
2742 tab1
= pParse
->nTab
++;
2743 tab2
= pParse
->nTab
++;
2744 assert( p
->pOrderBy
==0 );
2746 addr
= sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, tab1
, 0);
2747 assert( p
->addrOpenEphm
[0] == -1 );
2748 p
->addrOpenEphm
[0] = addr
;
2749 findRightmost(p
)->selFlags
|= SF_UsesEphemeral
;
2750 assert( p
->pEList
);
2752 /* Code the SELECTs to our left into temporary table "tab1".
2754 sqlite3SelectDestInit(&intersectdest
, SRT_Union
, tab1
);
2755 rc
= sqlite3Select(pParse
, pPrior
, &intersectdest
);
2757 goto multi_select_end
;
2760 /* Code the current SELECT into temporary table "tab2"
2762 addr
= sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, tab2
, 0);
2763 assert( p
->addrOpenEphm
[1] == -1 );
2764 p
->addrOpenEphm
[1] = addr
;
2768 intersectdest
.iSDParm
= tab2
;
2769 ExplainQueryPlan((pParse
, 1, "%s USING TEMP B-TREE",
2770 selectOpName(p
->op
)));
2771 rc
= sqlite3Select(pParse
, p
, &intersectdest
);
2772 testcase( rc
!=SQLITE_OK
);
2773 pDelete
= p
->pPrior
;
2775 if( p
->nSelectRow
>pPrior
->nSelectRow
){
2776 p
->nSelectRow
= pPrior
->nSelectRow
;
2778 sqlite3ExprDelete(db
, p
->pLimit
);
2781 /* Generate code to take the intersection of the two temporary
2784 assert( p
->pEList
);
2785 iBreak
= sqlite3VdbeMakeLabel(pParse
);
2786 iCont
= sqlite3VdbeMakeLabel(pParse
);
2787 computeLimitRegisters(pParse
, p
, iBreak
);
2788 sqlite3VdbeAddOp2(v
, OP_Rewind
, tab1
, iBreak
); VdbeCoverage(v
);
2789 r1
= sqlite3GetTempReg(pParse
);
2790 iStart
= sqlite3VdbeAddOp2(v
, OP_RowData
, tab1
, r1
);
2791 sqlite3VdbeAddOp4Int(v
, OP_NotFound
, tab2
, iCont
, r1
, 0);
2793 sqlite3ReleaseTempReg(pParse
, r1
);
2794 selectInnerLoop(pParse
, p
, tab1
,
2795 0, 0, &dest
, iCont
, iBreak
);
2796 sqlite3VdbeResolveLabel(v
, iCont
);
2797 sqlite3VdbeAddOp2(v
, OP_Next
, tab1
, iStart
); VdbeCoverage(v
);
2798 sqlite3VdbeResolveLabel(v
, iBreak
);
2799 sqlite3VdbeAddOp2(v
, OP_Close
, tab2
, 0);
2800 sqlite3VdbeAddOp2(v
, OP_Close
, tab1
, 0);
2805 #ifndef SQLITE_OMIT_EXPLAIN
2807 ExplainQueryPlanPop(pParse
);
2812 /* Compute collating sequences used by
2813 ** temporary tables needed to implement the compound select.
2814 ** Attach the KeyInfo structure to all temporary tables.
2816 ** This section is run by the right-most SELECT statement only.
2817 ** SELECT statements to the left always skip this part. The right-most
2818 ** SELECT might also skip this part if it has no ORDER BY clause and
2819 ** no temp tables are required.
2821 if( p
->selFlags
& SF_UsesEphemeral
){
2822 int i
; /* Loop counter */
2823 KeyInfo
*pKeyInfo
; /* Collating sequence for the result set */
2824 Select
*pLoop
; /* For looping through SELECT statements */
2825 CollSeq
**apColl
; /* For looping through pKeyInfo->aColl[] */
2826 int nCol
; /* Number of columns in result set */
2828 assert( p
->pNext
==0 );
2829 nCol
= p
->pEList
->nExpr
;
2830 pKeyInfo
= sqlite3KeyInfoAlloc(db
, nCol
, 1);
2832 rc
= SQLITE_NOMEM_BKPT
;
2833 goto multi_select_end
;
2835 for(i
=0, apColl
=pKeyInfo
->aColl
; i
<nCol
; i
++, apColl
++){
2836 *apColl
= multiSelectCollSeq(pParse
, p
, i
);
2838 *apColl
= db
->pDfltColl
;
2842 for(pLoop
=p
; pLoop
; pLoop
=pLoop
->pPrior
){
2844 int addr
= pLoop
->addrOpenEphm
[i
];
2846 /* If [0] is unused then [1] is also unused. So we can
2847 ** always safely abort as soon as the first unused slot is found */
2848 assert( pLoop
->addrOpenEphm
[1]<0 );
2851 sqlite3VdbeChangeP2(v
, addr
, nCol
);
2852 sqlite3VdbeChangeP4(v
, addr
, (char*)sqlite3KeyInfoRef(pKeyInfo
),
2854 pLoop
->addrOpenEphm
[i
] = -1;
2857 sqlite3KeyInfoUnref(pKeyInfo
);
2861 pDest
->iSdst
= dest
.iSdst
;
2862 pDest
->nSdst
= dest
.nSdst
;
2863 sqlite3SelectDelete(db
, pDelete
);
2866 #endif /* SQLITE_OMIT_COMPOUND_SELECT */
2869 ** Error message for when two or more terms of a compound select have different
2870 ** size result sets.
2872 void sqlite3SelectWrongNumTermsError(Parse
*pParse
, Select
*p
){
2873 if( p
->selFlags
& SF_Values
){
2874 sqlite3ErrorMsg(pParse
, "all VALUES must have the same number of terms");
2876 sqlite3ErrorMsg(pParse
, "SELECTs to the left and right of %s"
2877 " do not have the same number of result columns", selectOpName(p
->op
));
2882 ** Code an output subroutine for a coroutine implementation of a
2885 ** The data to be output is contained in pIn->iSdst. There are
2886 ** pIn->nSdst columns to be output. pDest is where the output should
2889 ** regReturn is the number of the register holding the subroutine
2892 ** If regPrev>0 then it is the first register in a vector that
2893 ** records the previous output. mem[regPrev] is a flag that is false
2894 ** if there has been no previous output. If regPrev>0 then code is
2895 ** generated to suppress duplicates. pKeyInfo is used for comparing
2898 ** If the LIMIT found in p->iLimit is reached, jump immediately to
2901 static int generateOutputSubroutine(
2902 Parse
*pParse
, /* Parsing context */
2903 Select
*p
, /* The SELECT statement */
2904 SelectDest
*pIn
, /* Coroutine supplying data */
2905 SelectDest
*pDest
, /* Where to send the data */
2906 int regReturn
, /* The return address register */
2907 int regPrev
, /* Previous result register. No uniqueness if 0 */
2908 KeyInfo
*pKeyInfo
, /* For comparing with previous entry */
2909 int iBreak
/* Jump here if we hit the LIMIT */
2911 Vdbe
*v
= pParse
->pVdbe
;
2915 addr
= sqlite3VdbeCurrentAddr(v
);
2916 iContinue
= sqlite3VdbeMakeLabel(pParse
);
2918 /* Suppress duplicates for UNION, EXCEPT, and INTERSECT
2922 addr1
= sqlite3VdbeAddOp1(v
, OP_IfNot
, regPrev
); VdbeCoverage(v
);
2923 addr2
= sqlite3VdbeAddOp4(v
, OP_Compare
, pIn
->iSdst
, regPrev
+1, pIn
->nSdst
,
2924 (char*)sqlite3KeyInfoRef(pKeyInfo
), P4_KEYINFO
);
2925 sqlite3VdbeAddOp3(v
, OP_Jump
, addr2
+2, iContinue
, addr2
+2); VdbeCoverage(v
);
2926 sqlite3VdbeJumpHere(v
, addr1
);
2927 sqlite3VdbeAddOp3(v
, OP_Copy
, pIn
->iSdst
, regPrev
+1, pIn
->nSdst
-1);
2928 sqlite3VdbeAddOp2(v
, OP_Integer
, 1, regPrev
);
2930 if( pParse
->db
->mallocFailed
) return 0;
2932 /* Suppress the first OFFSET entries if there is an OFFSET clause
2934 codeOffset(v
, p
->iOffset
, iContinue
);
2936 assert( pDest
->eDest
!=SRT_Exists
);
2937 assert( pDest
->eDest
!=SRT_Table
);
2938 switch( pDest
->eDest
){
2939 /* Store the result as data using a unique key.
2941 case SRT_EphemTab
: {
2942 int r1
= sqlite3GetTempReg(pParse
);
2943 int r2
= sqlite3GetTempReg(pParse
);
2944 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, pIn
->iSdst
, pIn
->nSdst
, r1
);
2945 sqlite3VdbeAddOp2(v
, OP_NewRowid
, pDest
->iSDParm
, r2
);
2946 sqlite3VdbeAddOp3(v
, OP_Insert
, pDest
->iSDParm
, r1
, r2
);
2947 sqlite3VdbeChangeP5(v
, OPFLAG_APPEND
);
2948 sqlite3ReleaseTempReg(pParse
, r2
);
2949 sqlite3ReleaseTempReg(pParse
, r1
);
2953 #ifndef SQLITE_OMIT_SUBQUERY
2954 /* If we are creating a set for an "expr IN (SELECT ...)".
2958 testcase( pIn
->nSdst
>1 );
2959 r1
= sqlite3GetTempReg(pParse
);
2960 sqlite3VdbeAddOp4(v
, OP_MakeRecord
, pIn
->iSdst
, pIn
->nSdst
,
2961 r1
, pDest
->zAffSdst
, pIn
->nSdst
);
2962 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, pDest
->iSDParm
, r1
,
2963 pIn
->iSdst
, pIn
->nSdst
);
2964 sqlite3ReleaseTempReg(pParse
, r1
);
2968 /* If this is a scalar select that is part of an expression, then
2969 ** store the results in the appropriate memory cell and break out
2970 ** of the scan loop.
2973 assert( pIn
->nSdst
==1 || pParse
->nErr
>0 ); testcase( pIn
->nSdst
!=1 );
2974 sqlite3ExprCodeMove(pParse
, pIn
->iSdst
, pDest
->iSDParm
, 1);
2975 /* The LIMIT clause will jump out of the loop for us */
2978 #endif /* #ifndef SQLITE_OMIT_SUBQUERY */
2980 /* The results are stored in a sequence of registers
2981 ** starting at pDest->iSdst. Then the co-routine yields.
2983 case SRT_Coroutine
: {
2984 if( pDest
->iSdst
==0 ){
2985 pDest
->iSdst
= sqlite3GetTempRange(pParse
, pIn
->nSdst
);
2986 pDest
->nSdst
= pIn
->nSdst
;
2988 sqlite3ExprCodeMove(pParse
, pIn
->iSdst
, pDest
->iSdst
, pIn
->nSdst
);
2989 sqlite3VdbeAddOp1(v
, OP_Yield
, pDest
->iSDParm
);
2993 /* If none of the above, then the result destination must be
2994 ** SRT_Output. This routine is never called with any other
2995 ** destination other than the ones handled above or SRT_Output.
2997 ** For SRT_Output, results are stored in a sequence of registers.
2998 ** Then the OP_ResultRow opcode is used to cause sqlite3_step() to
2999 ** return the next row of result.
3002 assert( pDest
->eDest
==SRT_Output
);
3003 sqlite3VdbeAddOp2(v
, OP_ResultRow
, pIn
->iSdst
, pIn
->nSdst
);
3008 /* Jump to the end of the loop if the LIMIT is reached.
3011 sqlite3VdbeAddOp2(v
, OP_DecrJumpZero
, p
->iLimit
, iBreak
); VdbeCoverage(v
);
3014 /* Generate the subroutine return
3016 sqlite3VdbeResolveLabel(v
, iContinue
);
3017 sqlite3VdbeAddOp1(v
, OP_Return
, regReturn
);
3023 ** Alternative compound select code generator for cases when there
3024 ** is an ORDER BY clause.
3026 ** We assume a query of the following form:
3028 ** <selectA> <operator> <selectB> ORDER BY <orderbylist>
3030 ** <operator> is one of UNION ALL, UNION, EXCEPT, or INTERSECT. The idea
3031 ** is to code both <selectA> and <selectB> with the ORDER BY clause as
3032 ** co-routines. Then run the co-routines in parallel and merge the results
3033 ** into the output. In addition to the two coroutines (called selectA and
3034 ** selectB) there are 7 subroutines:
3036 ** outA: Move the output of the selectA coroutine into the output
3037 ** of the compound query.
3039 ** outB: Move the output of the selectB coroutine into the output
3040 ** of the compound query. (Only generated for UNION and
3041 ** UNION ALL. EXCEPT and INSERTSECT never output a row that
3042 ** appears only in B.)
3044 ** AltB: Called when there is data from both coroutines and A<B.
3046 ** AeqB: Called when there is data from both coroutines and A==B.
3048 ** AgtB: Called when there is data from both coroutines and A>B.
3050 ** EofA: Called when data is exhausted from selectA.
3052 ** EofB: Called when data is exhausted from selectB.
3054 ** The implementation of the latter five subroutines depend on which
3055 ** <operator> is used:
3058 ** UNION ALL UNION EXCEPT INTERSECT
3059 ** ------------- ----------------- -------------- -----------------
3060 ** AltB: outA, nextA outA, nextA outA, nextA nextA
3062 ** AeqB: outA, nextA nextA nextA outA, nextA
3064 ** AgtB: outB, nextB outB, nextB nextB nextB
3066 ** EofA: outB, nextB outB, nextB halt halt
3068 ** EofB: outA, nextA outA, nextA outA, nextA halt
3070 ** In the AltB, AeqB, and AgtB subroutines, an EOF on A following nextA
3071 ** causes an immediate jump to EofA and an EOF on B following nextB causes
3072 ** an immediate jump to EofB. Within EofA and EofB, and EOF on entry or
3073 ** following nextX causes a jump to the end of the select processing.
3075 ** Duplicate removal in the UNION, EXCEPT, and INTERSECT cases is handled
3076 ** within the output subroutine. The regPrev register set holds the previously
3077 ** output value. A comparison is made against this value and the output
3078 ** is skipped if the next results would be the same as the previous.
3080 ** The implementation plan is to implement the two coroutines and seven
3081 ** subroutines first, then put the control logic at the bottom. Like this:
3084 ** coA: coroutine for left query (A)
3085 ** coB: coroutine for right query (B)
3086 ** outA: output one row of A
3087 ** outB: output one row of B (UNION and UNION ALL only)
3093 ** Init: initialize coroutine registers
3095 ** if eof(A) goto EofA
3097 ** if eof(B) goto EofB
3098 ** Cmpr: Compare A, B
3099 ** Jump AltB, AeqB, AgtB
3102 ** We call AltB, AeqB, AgtB, EofA, and EofB "subroutines" but they are not
3103 ** actually called using Gosub and they do not Return. EofA and EofB loop
3104 ** until all data is exhausted then jump to the "end" labe. AltB, AeqB,
3105 ** and AgtB jump to either L2 or to one of EofA or EofB.
3107 #ifndef SQLITE_OMIT_COMPOUND_SELECT
3108 static int multiSelectOrderBy(
3109 Parse
*pParse
, /* Parsing context */
3110 Select
*p
, /* The right-most of SELECTs to be coded */
3111 SelectDest
*pDest
/* What to do with query results */
3113 int i
, j
; /* Loop counters */
3114 Select
*pPrior
; /* Another SELECT immediately to our left */
3115 Vdbe
*v
; /* Generate code to this VDBE */
3116 SelectDest destA
; /* Destination for coroutine A */
3117 SelectDest destB
; /* Destination for coroutine B */
3118 int regAddrA
; /* Address register for select-A coroutine */
3119 int regAddrB
; /* Address register for select-B coroutine */
3120 int addrSelectA
; /* Address of the select-A coroutine */
3121 int addrSelectB
; /* Address of the select-B coroutine */
3122 int regOutA
; /* Address register for the output-A subroutine */
3123 int regOutB
; /* Address register for the output-B subroutine */
3124 int addrOutA
; /* Address of the output-A subroutine */
3125 int addrOutB
= 0; /* Address of the output-B subroutine */
3126 int addrEofA
; /* Address of the select-A-exhausted subroutine */
3127 int addrEofA_noB
; /* Alternate addrEofA if B is uninitialized */
3128 int addrEofB
; /* Address of the select-B-exhausted subroutine */
3129 int addrAltB
; /* Address of the A<B subroutine */
3130 int addrAeqB
; /* Address of the A==B subroutine */
3131 int addrAgtB
; /* Address of the A>B subroutine */
3132 int regLimitA
; /* Limit register for select-A */
3133 int regLimitB
; /* Limit register for select-A */
3134 int regPrev
; /* A range of registers to hold previous output */
3135 int savedLimit
; /* Saved value of p->iLimit */
3136 int savedOffset
; /* Saved value of p->iOffset */
3137 int labelCmpr
; /* Label for the start of the merge algorithm */
3138 int labelEnd
; /* Label for the end of the overall SELECT stmt */
3139 int addr1
; /* Jump instructions that get retargetted */
3140 int op
; /* One of TK_ALL, TK_UNION, TK_EXCEPT, TK_INTERSECT */
3141 KeyInfo
*pKeyDup
= 0; /* Comparison information for duplicate removal */
3142 KeyInfo
*pKeyMerge
; /* Comparison information for merging rows */
3143 sqlite3
*db
; /* Database connection */
3144 ExprList
*pOrderBy
; /* The ORDER BY clause */
3145 int nOrderBy
; /* Number of terms in the ORDER BY clause */
3146 int *aPermute
; /* Mapping from ORDER BY terms to result set columns */
3148 assert( p
->pOrderBy
!=0 );
3149 assert( pKeyDup
==0 ); /* "Managed" code needs this. Ticket #3382. */
3152 assert( v
!=0 ); /* Already thrown the error if VDBE alloc failed */
3153 labelEnd
= sqlite3VdbeMakeLabel(pParse
);
3154 labelCmpr
= sqlite3VdbeMakeLabel(pParse
);
3157 /* Patch up the ORDER BY clause
3161 assert( pPrior
->pOrderBy
==0 );
3162 pOrderBy
= p
->pOrderBy
;
3164 nOrderBy
= pOrderBy
->nExpr
;
3166 /* For operators other than UNION ALL we have to make sure that
3167 ** the ORDER BY clause covers every term of the result set. Add
3168 ** terms to the ORDER BY clause as necessary.
3171 for(i
=1; db
->mallocFailed
==0 && i
<=p
->pEList
->nExpr
; i
++){
3172 struct ExprList_item
*pItem
;
3173 for(j
=0, pItem
=pOrderBy
->a
; j
<nOrderBy
; j
++, pItem
++){
3174 assert( pItem
->u
.x
.iOrderByCol
>0 );
3175 if( pItem
->u
.x
.iOrderByCol
==i
) break;
3178 Expr
*pNew
= sqlite3Expr(db
, TK_INTEGER
, 0);
3179 if( pNew
==0 ) return SQLITE_NOMEM_BKPT
;
3180 pNew
->flags
|= EP_IntValue
;
3182 p
->pOrderBy
= pOrderBy
= sqlite3ExprListAppend(pParse
, pOrderBy
, pNew
);
3183 if( pOrderBy
) pOrderBy
->a
[nOrderBy
++].u
.x
.iOrderByCol
= (u16
)i
;
3188 /* Compute the comparison permutation and keyinfo that is used with
3189 ** the permutation used to determine if the next
3190 ** row of results comes from selectA or selectB. Also add explicit
3191 ** collations to the ORDER BY clause terms so that when the subqueries
3192 ** to the right and the left are evaluated, they use the correct
3195 aPermute
= sqlite3DbMallocRawNN(db
, sizeof(int)*(nOrderBy
+ 1));
3197 struct ExprList_item
*pItem
;
3198 aPermute
[0] = nOrderBy
;
3199 for(i
=1, pItem
=pOrderBy
->a
; i
<=nOrderBy
; i
++, pItem
++){
3200 assert( pItem
->u
.x
.iOrderByCol
>0 );
3201 assert( pItem
->u
.x
.iOrderByCol
<=p
->pEList
->nExpr
);
3202 aPermute
[i
] = pItem
->u
.x
.iOrderByCol
- 1;
3204 pKeyMerge
= multiSelectOrderByKeyInfo(pParse
, p
, 1);
3209 /* Reattach the ORDER BY clause to the query.
3211 p
->pOrderBy
= pOrderBy
;
3212 pPrior
->pOrderBy
= sqlite3ExprListDup(pParse
->db
, pOrderBy
, 0);
3214 /* Allocate a range of temporary registers and the KeyInfo needed
3215 ** for the logic that removes duplicate result rows when the
3216 ** operator is UNION, EXCEPT, or INTERSECT (but not UNION ALL).
3221 int nExpr
= p
->pEList
->nExpr
;
3222 assert( nOrderBy
>=nExpr
|| db
->mallocFailed
);
3223 regPrev
= pParse
->nMem
+1;
3224 pParse
->nMem
+= nExpr
+1;
3225 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, regPrev
);
3226 pKeyDup
= sqlite3KeyInfoAlloc(db
, nExpr
, 1);
3228 assert( sqlite3KeyInfoIsWriteable(pKeyDup
) );
3229 for(i
=0; i
<nExpr
; i
++){
3230 pKeyDup
->aColl
[i
] = multiSelectCollSeq(pParse
, p
, i
);
3231 pKeyDup
->aSortOrder
[i
] = 0;
3236 /* Separate the left and the right query from one another
3240 sqlite3ResolveOrderGroupBy(pParse
, p
, p
->pOrderBy
, "ORDER");
3241 if( pPrior
->pPrior
==0 ){
3242 sqlite3ResolveOrderGroupBy(pParse
, pPrior
, pPrior
->pOrderBy
, "ORDER");
3245 /* Compute the limit registers */
3246 computeLimitRegisters(pParse
, p
, labelEnd
);
3247 if( p
->iLimit
&& op
==TK_ALL
){
3248 regLimitA
= ++pParse
->nMem
;
3249 regLimitB
= ++pParse
->nMem
;
3250 sqlite3VdbeAddOp2(v
, OP_Copy
, p
->iOffset
? p
->iOffset
+1 : p
->iLimit
,
3252 sqlite3VdbeAddOp2(v
, OP_Copy
, regLimitA
, regLimitB
);
3254 regLimitA
= regLimitB
= 0;
3256 sqlite3ExprDelete(db
, p
->pLimit
);
3259 regAddrA
= ++pParse
->nMem
;
3260 regAddrB
= ++pParse
->nMem
;
3261 regOutA
= ++pParse
->nMem
;
3262 regOutB
= ++pParse
->nMem
;
3263 sqlite3SelectDestInit(&destA
, SRT_Coroutine
, regAddrA
);
3264 sqlite3SelectDestInit(&destB
, SRT_Coroutine
, regAddrB
);
3266 ExplainQueryPlan((pParse
, 1, "MERGE (%s)", selectOpName(p
->op
)));
3268 /* Generate a coroutine to evaluate the SELECT statement to the
3269 ** left of the compound operator - the "A" select.
3271 addrSelectA
= sqlite3VdbeCurrentAddr(v
) + 1;
3272 addr1
= sqlite3VdbeAddOp3(v
, OP_InitCoroutine
, regAddrA
, 0, addrSelectA
);
3273 VdbeComment((v
, "left SELECT"));
3274 pPrior
->iLimit
= regLimitA
;
3275 ExplainQueryPlan((pParse
, 1, "LEFT"));
3276 sqlite3Select(pParse
, pPrior
, &destA
);
3277 sqlite3VdbeEndCoroutine(v
, regAddrA
);
3278 sqlite3VdbeJumpHere(v
, addr1
);
3280 /* Generate a coroutine to evaluate the SELECT statement on
3281 ** the right - the "B" select
3283 addrSelectB
= sqlite3VdbeCurrentAddr(v
) + 1;
3284 addr1
= sqlite3VdbeAddOp3(v
, OP_InitCoroutine
, regAddrB
, 0, addrSelectB
);
3285 VdbeComment((v
, "right SELECT"));
3286 savedLimit
= p
->iLimit
;
3287 savedOffset
= p
->iOffset
;
3288 p
->iLimit
= regLimitB
;
3290 ExplainQueryPlan((pParse
, 1, "RIGHT"));
3291 sqlite3Select(pParse
, p
, &destB
);
3292 p
->iLimit
= savedLimit
;
3293 p
->iOffset
= savedOffset
;
3294 sqlite3VdbeEndCoroutine(v
, regAddrB
);
3296 /* Generate a subroutine that outputs the current row of the A
3297 ** select as the next output row of the compound select.
3299 VdbeNoopComment((v
, "Output routine for A"));
3300 addrOutA
= generateOutputSubroutine(pParse
,
3301 p
, &destA
, pDest
, regOutA
,
3302 regPrev
, pKeyDup
, labelEnd
);
3304 /* Generate a subroutine that outputs the current row of the B
3305 ** select as the next output row of the compound select.
3307 if( op
==TK_ALL
|| op
==TK_UNION
){
3308 VdbeNoopComment((v
, "Output routine for B"));
3309 addrOutB
= generateOutputSubroutine(pParse
,
3310 p
, &destB
, pDest
, regOutB
,
3311 regPrev
, pKeyDup
, labelEnd
);
3313 sqlite3KeyInfoUnref(pKeyDup
);
3315 /* Generate a subroutine to run when the results from select A
3316 ** are exhausted and only data in select B remains.
3318 if( op
==TK_EXCEPT
|| op
==TK_INTERSECT
){
3319 addrEofA_noB
= addrEofA
= labelEnd
;
3321 VdbeNoopComment((v
, "eof-A subroutine"));
3322 addrEofA
= sqlite3VdbeAddOp2(v
, OP_Gosub
, regOutB
, addrOutB
);
3323 addrEofA_noB
= sqlite3VdbeAddOp2(v
, OP_Yield
, regAddrB
, labelEnd
);
3325 sqlite3VdbeGoto(v
, addrEofA
);
3326 p
->nSelectRow
= sqlite3LogEstAdd(p
->nSelectRow
, pPrior
->nSelectRow
);
3329 /* Generate a subroutine to run when the results from select B
3330 ** are exhausted and only data in select A remains.
3332 if( op
==TK_INTERSECT
){
3333 addrEofB
= addrEofA
;
3334 if( p
->nSelectRow
> pPrior
->nSelectRow
) p
->nSelectRow
= pPrior
->nSelectRow
;
3336 VdbeNoopComment((v
, "eof-B subroutine"));
3337 addrEofB
= sqlite3VdbeAddOp2(v
, OP_Gosub
, regOutA
, addrOutA
);
3338 sqlite3VdbeAddOp2(v
, OP_Yield
, regAddrA
, labelEnd
); VdbeCoverage(v
);
3339 sqlite3VdbeGoto(v
, addrEofB
);
3342 /* Generate code to handle the case of A<B
3344 VdbeNoopComment((v
, "A-lt-B subroutine"));
3345 addrAltB
= sqlite3VdbeAddOp2(v
, OP_Gosub
, regOutA
, addrOutA
);
3346 sqlite3VdbeAddOp2(v
, OP_Yield
, regAddrA
, addrEofA
); VdbeCoverage(v
);
3347 sqlite3VdbeGoto(v
, labelCmpr
);
3349 /* Generate code to handle the case of A==B
3352 addrAeqB
= addrAltB
;
3353 }else if( op
==TK_INTERSECT
){
3354 addrAeqB
= addrAltB
;
3357 VdbeNoopComment((v
, "A-eq-B subroutine"));
3359 sqlite3VdbeAddOp2(v
, OP_Yield
, regAddrA
, addrEofA
); VdbeCoverage(v
);
3360 sqlite3VdbeGoto(v
, labelCmpr
);
3363 /* Generate code to handle the case of A>B
3365 VdbeNoopComment((v
, "A-gt-B subroutine"));
3366 addrAgtB
= sqlite3VdbeCurrentAddr(v
);
3367 if( op
==TK_ALL
|| op
==TK_UNION
){
3368 sqlite3VdbeAddOp2(v
, OP_Gosub
, regOutB
, addrOutB
);
3370 sqlite3VdbeAddOp2(v
, OP_Yield
, regAddrB
, addrEofB
); VdbeCoverage(v
);
3371 sqlite3VdbeGoto(v
, labelCmpr
);
3373 /* This code runs once to initialize everything.
3375 sqlite3VdbeJumpHere(v
, addr1
);
3376 sqlite3VdbeAddOp2(v
, OP_Yield
, regAddrA
, addrEofA_noB
); VdbeCoverage(v
);
3377 sqlite3VdbeAddOp2(v
, OP_Yield
, regAddrB
, addrEofB
); VdbeCoverage(v
);
3379 /* Implement the main merge loop
3381 sqlite3VdbeResolveLabel(v
, labelCmpr
);
3382 sqlite3VdbeAddOp4(v
, OP_Permutation
, 0, 0, 0, (char*)aPermute
, P4_INTARRAY
);
3383 sqlite3VdbeAddOp4(v
, OP_Compare
, destA
.iSdst
, destB
.iSdst
, nOrderBy
,
3384 (char*)pKeyMerge
, P4_KEYINFO
);
3385 sqlite3VdbeChangeP5(v
, OPFLAG_PERMUTE
);
3386 sqlite3VdbeAddOp3(v
, OP_Jump
, addrAltB
, addrAeqB
, addrAgtB
); VdbeCoverage(v
);
3388 /* Jump to the this point in order to terminate the query.
3390 sqlite3VdbeResolveLabel(v
, labelEnd
);
3392 /* Reassembly the compound query so that it will be freed correctly
3393 ** by the calling function */
3395 sqlite3SelectDelete(db
, p
->pPrior
);
3400 /*** TBD: Insert subroutine calls to close cursors on incomplete
3401 **** subqueries ****/
3402 ExplainQueryPlanPop(pParse
);
3403 return pParse
->nErr
!=0;
3407 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3409 /* An instance of the SubstContext object describes an substitution edit
3410 ** to be performed on a parse tree.
3412 ** All references to columns in table iTable are to be replaced by corresponding
3413 ** expressions in pEList.
3415 typedef struct SubstContext
{
3416 Parse
*pParse
; /* The parsing context */
3417 int iTable
; /* Replace references to this table */
3418 int iNewTable
; /* New table number */
3419 int isLeftJoin
; /* Add TK_IF_NULL_ROW opcodes on each replacement */
3420 ExprList
*pEList
; /* Replacement expressions */
3423 /* Forward Declarations */
3424 static void substExprList(SubstContext
*, ExprList
*);
3425 static void substSelect(SubstContext
*, Select
*, int);
3428 ** Scan through the expression pExpr. Replace every reference to
3429 ** a column in table number iTable with a copy of the iColumn-th
3430 ** entry in pEList. (But leave references to the ROWID column
3433 ** This routine is part of the flattening procedure. A subquery
3434 ** whose result set is defined by pEList appears as entry in the
3435 ** FROM clause of a SELECT such that the VDBE cursor assigned to that
3436 ** FORM clause entry is iTable. This routine makes the necessary
3437 ** changes to pExpr so that it refers directly to the source table
3438 ** of the subquery rather the result set of the subquery.
3440 static Expr
*substExpr(
3441 SubstContext
*pSubst
, /* Description of the substitution */
3442 Expr
*pExpr
/* Expr in which substitution occurs */
3444 if( pExpr
==0 ) return 0;
3445 if( ExprHasProperty(pExpr
, EP_FromJoin
)
3446 && pExpr
->iRightJoinTable
==pSubst
->iTable
3448 pExpr
->iRightJoinTable
= pSubst
->iNewTable
;
3450 if( pExpr
->op
==TK_COLUMN
&& pExpr
->iTable
==pSubst
->iTable
){
3451 if( pExpr
->iColumn
<0 ){
3452 pExpr
->op
= TK_NULL
;
3455 Expr
*pCopy
= pSubst
->pEList
->a
[pExpr
->iColumn
].pExpr
;
3457 assert( pSubst
->pEList
!=0 && pExpr
->iColumn
<pSubst
->pEList
->nExpr
);
3458 assert( pExpr
->pRight
==0 );
3459 if( sqlite3ExprIsVector(pCopy
) ){
3460 sqlite3VectorErrorMsg(pSubst
->pParse
, pCopy
);
3462 sqlite3
*db
= pSubst
->pParse
->db
;
3463 if( pSubst
->isLeftJoin
&& pCopy
->op
!=TK_COLUMN
){
3464 memset(&ifNullRow
, 0, sizeof(ifNullRow
));
3465 ifNullRow
.op
= TK_IF_NULL_ROW
;
3466 ifNullRow
.pLeft
= pCopy
;
3467 ifNullRow
.iTable
= pSubst
->iNewTable
;
3470 testcase( ExprHasProperty(pCopy
, EP_Subquery
) );
3471 pNew
= sqlite3ExprDup(db
, pCopy
, 0);
3472 if( pNew
&& pSubst
->isLeftJoin
){
3473 ExprSetProperty(pNew
, EP_CanBeNull
);
3475 if( pNew
&& ExprHasProperty(pExpr
,EP_FromJoin
) ){
3476 pNew
->iRightJoinTable
= pExpr
->iRightJoinTable
;
3477 ExprSetProperty(pNew
, EP_FromJoin
);
3479 sqlite3ExprDelete(db
, pExpr
);
3484 if( pExpr
->op
==TK_IF_NULL_ROW
&& pExpr
->iTable
==pSubst
->iTable
){
3485 pExpr
->iTable
= pSubst
->iNewTable
;
3487 pExpr
->pLeft
= substExpr(pSubst
, pExpr
->pLeft
);
3488 pExpr
->pRight
= substExpr(pSubst
, pExpr
->pRight
);
3489 if( ExprHasProperty(pExpr
, EP_xIsSelect
) ){
3490 substSelect(pSubst
, pExpr
->x
.pSelect
, 1);
3492 substExprList(pSubst
, pExpr
->x
.pList
);
3497 static void substExprList(
3498 SubstContext
*pSubst
, /* Description of the substitution */
3499 ExprList
*pList
/* List to scan and in which to make substitutes */
3502 if( pList
==0 ) return;
3503 for(i
=0; i
<pList
->nExpr
; i
++){
3504 pList
->a
[i
].pExpr
= substExpr(pSubst
, pList
->a
[i
].pExpr
);
3507 static void substSelect(
3508 SubstContext
*pSubst
, /* Description of the substitution */
3509 Select
*p
, /* SELECT statement in which to make substitutions */
3510 int doPrior
/* Do substitutes on p->pPrior too */
3513 struct SrcList_item
*pItem
;
3517 substExprList(pSubst
, p
->pEList
);
3518 substExprList(pSubst
, p
->pGroupBy
);
3519 substExprList(pSubst
, p
->pOrderBy
);
3520 p
->pHaving
= substExpr(pSubst
, p
->pHaving
);
3521 p
->pWhere
= substExpr(pSubst
, p
->pWhere
);
3524 for(i
=pSrc
->nSrc
, pItem
=pSrc
->a
; i
>0; i
--, pItem
++){
3525 substSelect(pSubst
, pItem
->pSelect
, 1);
3526 if( pItem
->fg
.isTabFunc
){
3527 substExprList(pSubst
, pItem
->u1
.pFuncArg
);
3530 }while( doPrior
&& (p
= p
->pPrior
)!=0 );
3532 #endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */
3534 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3536 ** This routine attempts to flatten subqueries as a performance optimization.
3537 ** This routine returns 1 if it makes changes and 0 if no flattening occurs.
3539 ** To understand the concept of flattening, consider the following
3542 ** SELECT a FROM (SELECT x+y AS a FROM t1 WHERE z<100) WHERE a>5
3544 ** The default way of implementing this query is to execute the
3545 ** subquery first and store the results in a temporary table, then
3546 ** run the outer query on that temporary table. This requires two
3547 ** passes over the data. Furthermore, because the temporary table
3548 ** has no indices, the WHERE clause on the outer query cannot be
3551 ** This routine attempts to rewrite queries such as the above into
3552 ** a single flat select, like this:
3554 ** SELECT x+y AS a FROM t1 WHERE z<100 AND a>5
3556 ** The code generated for this simplification gives the same result
3557 ** but only has to scan the data once. And because indices might
3558 ** exist on the table t1, a complete scan of the data might be
3561 ** Flattening is subject to the following constraints:
3563 ** (**) We no longer attempt to flatten aggregate subqueries. Was:
3564 ** The subquery and the outer query cannot both be aggregates.
3566 ** (**) We no longer attempt to flatten aggregate subqueries. Was:
3567 ** (2) If the subquery is an aggregate then
3568 ** (2a) the outer query must not be a join and
3569 ** (2b) the outer query must not use subqueries
3570 ** other than the one FROM-clause subquery that is a candidate
3571 ** for flattening. (This is due to ticket [2f7170d73bf9abf80]
3572 ** from 2015-02-09.)
3574 ** (3) If the subquery is the right operand of a LEFT JOIN then
3575 ** (3a) the subquery may not be a join and
3576 ** (3b) the FROM clause of the subquery may not contain a virtual
3578 ** (3c) the outer query may not be an aggregate.
3580 ** (4) The subquery can not be DISTINCT.
3582 ** (**) At one point restrictions (4) and (5) defined a subset of DISTINCT
3583 ** sub-queries that were excluded from this optimization. Restriction
3584 ** (4) has since been expanded to exclude all DISTINCT subqueries.
3586 ** (**) We no longer attempt to flatten aggregate subqueries. Was:
3587 ** If the subquery is aggregate, the outer query may not be DISTINCT.
3589 ** (7) The subquery must have a FROM clause. TODO: For subqueries without
3590 ** A FROM clause, consider adding a FROM clause with the special
3591 ** table sqlite_once that consists of a single row containing a
3594 ** (8) If the subquery uses LIMIT then the outer query may not be a join.
3596 ** (9) If the subquery uses LIMIT then the outer query may not be aggregate.
3598 ** (**) Restriction (10) was removed from the code on 2005-02-05 but we
3599 ** accidently carried the comment forward until 2014-09-15. Original
3600 ** constraint: "If the subquery is aggregate then the outer query
3601 ** may not use LIMIT."
3603 ** (11) The subquery and the outer query may not both have ORDER BY clauses.
3605 ** (**) Not implemented. Subsumed into restriction (3). Was previously
3606 ** a separate restriction deriving from ticket #350.
3608 ** (13) The subquery and outer query may not both use LIMIT.
3610 ** (14) The subquery may not use OFFSET.
3612 ** (15) If the outer query is part of a compound select, then the
3613 ** subquery may not use LIMIT.
3614 ** (See ticket #2339 and ticket [02a8e81d44]).
3616 ** (16) If the outer query is aggregate, then the subquery may not
3617 ** use ORDER BY. (Ticket #2942) This used to not matter
3618 ** until we introduced the group_concat() function.
3620 ** (17) If the subquery is a compound select, then
3621 ** (17a) all compound operators must be a UNION ALL, and
3622 ** (17b) no terms within the subquery compound may be aggregate
3624 ** (17c) every term within the subquery compound must have a FROM clause
3625 ** (17d) the outer query may not be
3626 ** (17d1) aggregate, or
3627 ** (17d2) DISTINCT, or
3630 ** The parent and sub-query may contain WHERE clauses. Subject to
3631 ** rules (11), (13) and (14), they may also contain ORDER BY,
3632 ** LIMIT and OFFSET clauses. The subquery cannot use any compound
3633 ** operator other than UNION ALL because all the other compound
3634 ** operators have an implied DISTINCT which is disallowed by
3637 ** Also, each component of the sub-query must return the same number
3638 ** of result columns. This is actually a requirement for any compound
3639 ** SELECT statement, but all the code here does is make sure that no
3640 ** such (illegal) sub-query is flattened. The caller will detect the
3641 ** syntax error and return a detailed message.
3643 ** (18) If the sub-query is a compound select, then all terms of the
3644 ** ORDER BY clause of the parent must be simple references to
3645 ** columns of the sub-query.
3647 ** (19) If the subquery uses LIMIT then the outer query may not
3648 ** have a WHERE clause.
3650 ** (20) If the sub-query is a compound select, then it must not use
3651 ** an ORDER BY clause. Ticket #3773. We could relax this constraint
3652 ** somewhat by saying that the terms of the ORDER BY clause must
3653 ** appear as unmodified result columns in the outer query. But we
3654 ** have other optimizations in mind to deal with that case.
3656 ** (21) If the subquery uses LIMIT then the outer query may not be
3657 ** DISTINCT. (See ticket [752e1646fc]).
3659 ** (22) The subquery may not be a recursive CTE.
3661 ** (**) Subsumed into restriction (17d3). Was: If the outer query is
3662 ** a recursive CTE, then the sub-query may not be a compound query.
3663 ** This restriction is because transforming the
3664 ** parent to a compound query confuses the code that handles
3665 ** recursive queries in multiSelect().
3667 ** (**) We no longer attempt to flatten aggregate subqueries. Was:
3668 ** The subquery may not be an aggregate that uses the built-in min() or
3669 ** or max() functions. (Without this restriction, a query like:
3670 ** "SELECT x FROM (SELECT max(y), x FROM t1)" would not necessarily
3671 ** return the value X for which Y was maximal.)
3673 ** (25) If either the subquery or the parent query contains a window
3674 ** function in the select list or ORDER BY clause, flattening
3675 ** is not attempted.
3678 ** In this routine, the "p" parameter is a pointer to the outer query.
3679 ** The subquery is p->pSrc->a[iFrom]. isAgg is true if the outer query
3682 ** If flattening is not attempted, this routine is a no-op and returns 0.
3683 ** If flattening is attempted this routine returns 1.
3685 ** All of the expression analysis must occur on both the outer query and
3686 ** the subquery before this routine runs.
3688 static int flattenSubquery(
3689 Parse
*pParse
, /* Parsing context */
3690 Select
*p
, /* The parent or outer SELECT statement */
3691 int iFrom
, /* Index in p->pSrc->a[] of the inner subquery */
3692 int isAgg
/* True if outer SELECT uses aggregate functions */
3694 const char *zSavedAuthContext
= pParse
->zAuthContext
;
3695 Select
*pParent
; /* Current UNION ALL term of the other query */
3696 Select
*pSub
; /* The inner query or "subquery" */
3697 Select
*pSub1
; /* Pointer to the rightmost select in sub-query */
3698 SrcList
*pSrc
; /* The FROM clause of the outer query */
3699 SrcList
*pSubSrc
; /* The FROM clause of the subquery */
3700 int iParent
; /* VDBE cursor number of the pSub result set temp table */
3701 int iNewParent
= -1;/* Replacement table for iParent */
3702 int isLeftJoin
= 0; /* True if pSub is the right side of a LEFT JOIN */
3703 int i
; /* Loop counter */
3704 Expr
*pWhere
; /* The WHERE clause */
3705 struct SrcList_item
*pSubitem
; /* The subquery */
3706 sqlite3
*db
= pParse
->db
;
3708 /* Check to see if flattening is permitted. Return 0 if not.
3711 assert( p
->pPrior
==0 );
3712 if( OptimizationDisabled(db
, SQLITE_QueryFlattener
) ) return 0;
3714 assert( pSrc
&& iFrom
>=0 && iFrom
<pSrc
->nSrc
);
3715 pSubitem
= &pSrc
->a
[iFrom
];
3716 iParent
= pSubitem
->iCursor
;
3717 pSub
= pSubitem
->pSelect
;
3720 #ifndef SQLITE_OMIT_WINDOWFUNC
3721 if( p
->pWin
|| pSub
->pWin
) return 0; /* Restriction (25) */
3724 pSubSrc
= pSub
->pSrc
;
3726 /* Prior to version 3.1.2, when LIMIT and OFFSET had to be simple constants,
3727 ** not arbitrary expressions, we allowed some combining of LIMIT and OFFSET
3728 ** because they could be computed at compile-time. But when LIMIT and OFFSET
3729 ** became arbitrary expressions, we were forced to add restrictions (13)
3731 if( pSub
->pLimit
&& p
->pLimit
) return 0; /* Restriction (13) */
3732 if( pSub
->pLimit
&& pSub
->pLimit
->pRight
) return 0; /* Restriction (14) */
3733 if( (p
->selFlags
& SF_Compound
)!=0 && pSub
->pLimit
){
3734 return 0; /* Restriction (15) */
3736 if( pSubSrc
->nSrc
==0 ) return 0; /* Restriction (7) */
3737 if( pSub
->selFlags
& SF_Distinct
) return 0; /* Restriction (4) */
3738 if( pSub
->pLimit
&& (pSrc
->nSrc
>1 || isAgg
) ){
3739 return 0; /* Restrictions (8)(9) */
3741 if( p
->pOrderBy
&& pSub
->pOrderBy
){
3742 return 0; /* Restriction (11) */
3744 if( isAgg
&& pSub
->pOrderBy
) return 0; /* Restriction (16) */
3745 if( pSub
->pLimit
&& p
->pWhere
) return 0; /* Restriction (19) */
3746 if( pSub
->pLimit
&& (p
->selFlags
& SF_Distinct
)!=0 ){
3747 return 0; /* Restriction (21) */
3749 if( pSub
->selFlags
& (SF_Recursive
) ){
3750 return 0; /* Restrictions (22) */
3754 ** If the subquery is the right operand of a LEFT JOIN, then the
3755 ** subquery may not be a join itself (3a). Example of why this is not
3758 ** t1 LEFT OUTER JOIN (t2 JOIN t3)
3760 ** If we flatten the above, we would get
3762 ** (t1 LEFT OUTER JOIN t2) JOIN t3
3764 ** which is not at all the same thing.
3766 ** If the subquery is the right operand of a LEFT JOIN, then the outer
3767 ** query cannot be an aggregate. (3c) This is an artifact of the way
3768 ** aggregates are processed - there is no mechanism to determine if
3769 ** the LEFT JOIN table should be all-NULL.
3771 ** See also tickets #306, #350, and #3300.
3773 if( (pSubitem
->fg
.jointype
& JT_OUTER
)!=0 ){
3775 if( pSubSrc
->nSrc
>1 || isAgg
|| IsVirtual(pSubSrc
->a
[0].pTab
) ){
3776 /* (3a) (3c) (3b) */
3780 #ifdef SQLITE_EXTRA_IFNULLROW
3781 else if( iFrom
>0 && !isAgg
){
3782 /* Setting isLeftJoin to -1 causes OP_IfNullRow opcodes to be generated for
3783 ** every reference to any result column from subquery in a join, even
3784 ** though they are not necessary. This will stress-test the OP_IfNullRow
3790 /* Restriction (17): If the sub-query is a compound SELECT, then it must
3791 ** use only the UNION ALL operator. And none of the simple select queries
3792 ** that make up the compound SELECT are allowed to be aggregate or distinct
3796 if( pSub
->pOrderBy
){
3797 return 0; /* Restriction (20) */
3799 if( isAgg
|| (p
->selFlags
& SF_Distinct
)!=0 || pSrc
->nSrc
!=1 ){
3800 return 0; /* (17d1), (17d2), or (17d3) */
3802 for(pSub1
=pSub
; pSub1
; pSub1
=pSub1
->pPrior
){
3803 testcase( (pSub1
->selFlags
& (SF_Distinct
|SF_Aggregate
))==SF_Distinct
);
3804 testcase( (pSub1
->selFlags
& (SF_Distinct
|SF_Aggregate
))==SF_Aggregate
);
3805 assert( pSub
->pSrc
!=0 );
3806 assert( pSub
->pEList
->nExpr
==pSub1
->pEList
->nExpr
);
3807 if( (pSub1
->selFlags
& (SF_Distinct
|SF_Aggregate
))!=0 /* (17b) */
3808 || (pSub1
->pPrior
&& pSub1
->op
!=TK_ALL
) /* (17a) */
3809 || pSub1
->pSrc
->nSrc
<1 /* (17c) */
3813 testcase( pSub1
->pSrc
->nSrc
>1 );
3816 /* Restriction (18). */
3819 for(ii
=0; ii
<p
->pOrderBy
->nExpr
; ii
++){
3820 if( p
->pOrderBy
->a
[ii
].u
.x
.iOrderByCol
==0 ) return 0;
3825 /* Ex-restriction (23):
3826 ** The only way that the recursive part of a CTE can contain a compound
3827 ** subquery is for the subquery to be one term of a join. But if the
3828 ** subquery is a join, then the flattening has already been stopped by
3829 ** restriction (17d3)
3831 assert( (p
->selFlags
& SF_Recursive
)==0 || pSub
->pPrior
==0 );
3833 /***** If we reach this point, flattening is permitted. *****/
3834 SELECTTRACE(1,pParse
,p
,("flatten %u.%p from term %d\n",
3835 pSub
->selId
, pSub
, iFrom
));
3837 /* Authorize the subquery */
3838 pParse
->zAuthContext
= pSubitem
->zName
;
3839 TESTONLY(i
=) sqlite3AuthCheck(pParse
, SQLITE_SELECT
, 0, 0, 0);
3840 testcase( i
==SQLITE_DENY
);
3841 pParse
->zAuthContext
= zSavedAuthContext
;
3843 /* If the sub-query is a compound SELECT statement, then (by restrictions
3844 ** 17 and 18 above) it must be a UNION ALL and the parent query must
3847 ** SELECT <expr-list> FROM (<sub-query>) <where-clause>
3849 ** followed by any ORDER BY, LIMIT and/or OFFSET clauses. This block
3850 ** creates N-1 copies of the parent query without any ORDER BY, LIMIT or
3851 ** OFFSET clauses and joins them to the left-hand-side of the original
3852 ** using UNION ALL operators. In this case N is the number of simple
3853 ** select statements in the compound sub-query.
3857 ** SELECT a+1 FROM (
3858 ** SELECT x FROM tab
3860 ** SELECT y FROM tab
3862 ** SELECT abs(z*2) FROM tab2
3863 ** ) WHERE a!=5 ORDER BY 1
3865 ** Transformed into:
3867 ** SELECT x+1 FROM tab WHERE x+1!=5
3869 ** SELECT y+1 FROM tab WHERE y+1!=5
3871 ** SELECT abs(z*2)+1 FROM tab2 WHERE abs(z*2)+1!=5
3874 ** We call this the "compound-subquery flattening".
3876 for(pSub
=pSub
->pPrior
; pSub
; pSub
=pSub
->pPrior
){
3878 ExprList
*pOrderBy
= p
->pOrderBy
;
3879 Expr
*pLimit
= p
->pLimit
;
3880 Select
*pPrior
= p
->pPrior
;
3885 pNew
= sqlite3SelectDup(db
, p
, 0);
3887 p
->pOrderBy
= pOrderBy
;
3893 pNew
->pPrior
= pPrior
;
3894 if( pPrior
) pPrior
->pNext
= pNew
;
3897 SELECTTRACE(2,pParse
,p
,("compound-subquery flattener"
3898 " creates %u as peer\n",pNew
->selId
));
3900 if( db
->mallocFailed
) return 1;
3903 /* Begin flattening the iFrom-th entry of the FROM clause
3904 ** in the outer query.
3906 pSub
= pSub1
= pSubitem
->pSelect
;
3908 /* Delete the transient table structure associated with the
3911 sqlite3DbFree(db
, pSubitem
->zDatabase
);
3912 sqlite3DbFree(db
, pSubitem
->zName
);
3913 sqlite3DbFree(db
, pSubitem
->zAlias
);
3914 pSubitem
->zDatabase
= 0;
3915 pSubitem
->zName
= 0;
3916 pSubitem
->zAlias
= 0;
3917 pSubitem
->pSelect
= 0;
3919 /* Defer deleting the Table object associated with the
3920 ** subquery until code generation is
3921 ** complete, since there may still exist Expr.pTab entries that
3922 ** refer to the subquery even after flattening. Ticket #3346.
3924 ** pSubitem->pTab is always non-NULL by test restrictions and tests above.
3926 if( ALWAYS(pSubitem
->pTab
!=0) ){
3927 Table
*pTabToDel
= pSubitem
->pTab
;
3928 if( pTabToDel
->nTabRef
==1 ){
3929 Parse
*pToplevel
= sqlite3ParseToplevel(pParse
);
3930 pTabToDel
->pNextZombie
= pToplevel
->pZombieTab
;
3931 pToplevel
->pZombieTab
= pTabToDel
;
3933 pTabToDel
->nTabRef
--;
3938 /* The following loop runs once for each term in a compound-subquery
3939 ** flattening (as described above). If we are doing a different kind
3940 ** of flattening - a flattening other than a compound-subquery flattening -
3941 ** then this loop only runs once.
3943 ** This loop moves all of the FROM elements of the subquery into the
3944 ** the FROM clause of the outer query. Before doing this, remember
3945 ** the cursor number for the original outer query FROM element in
3946 ** iParent. The iParent cursor will never be used. Subsequent code
3947 ** will scan expressions looking for iParent references and replace
3948 ** those references with expressions that resolve to the subquery FROM
3949 ** elements we are now copying in.
3951 for(pParent
=p
; pParent
; pParent
=pParent
->pPrior
, pSub
=pSub
->pPrior
){
3954 pSubSrc
= pSub
->pSrc
; /* FROM clause of subquery */
3955 nSubSrc
= pSubSrc
->nSrc
; /* Number of terms in subquery FROM clause */
3956 pSrc
= pParent
->pSrc
; /* FROM clause of the outer query */
3959 assert( pParent
==p
); /* First time through the loop */
3960 jointype
= pSubitem
->fg
.jointype
;
3962 assert( pParent
!=p
); /* 2nd and subsequent times through the loop */
3963 pSrc
= sqlite3SrcListAppend(pParse
, 0, 0, 0);
3964 if( pSrc
==0 ) break;
3965 pParent
->pSrc
= pSrc
;
3968 /* The subquery uses a single slot of the FROM clause of the outer
3969 ** query. If the subquery has more than one element in its FROM clause,
3970 ** then expand the outer query to make space for it to hold all elements
3975 ** SELECT * FROM tabA, (SELECT * FROM sub1, sub2), tabB;
3977 ** The outer query has 3 slots in its FROM clause. One slot of the
3978 ** outer query (the middle slot) is used by the subquery. The next
3979 ** block of code will expand the outer query FROM clause to 4 slots.
3980 ** The middle slot is expanded to two slots in order to make space
3981 ** for the two elements in the FROM clause of the subquery.
3984 pSrc
= sqlite3SrcListEnlarge(pParse
, pSrc
, nSubSrc
-1,iFrom
+1);
3985 if( pSrc
==0 ) break;
3986 pParent
->pSrc
= pSrc
;
3989 /* Transfer the FROM clause terms from the subquery into the
3992 for(i
=0; i
<nSubSrc
; i
++){
3993 sqlite3IdListDelete(db
, pSrc
->a
[i
+iFrom
].pUsing
);
3994 assert( pSrc
->a
[i
+iFrom
].fg
.isTabFunc
==0 );
3995 pSrc
->a
[i
+iFrom
] = pSubSrc
->a
[i
];
3996 iNewParent
= pSubSrc
->a
[i
].iCursor
;
3997 memset(&pSubSrc
->a
[i
], 0, sizeof(pSubSrc
->a
[i
]));
3999 pSrc
->a
[iFrom
].fg
.jointype
= jointype
;
4001 /* Now begin substituting subquery result set expressions for
4002 ** references to the iParent in the outer query.
4006 ** SELECT a+5, b*10 FROM (SELECT x*3 AS a, y+10 AS b FROM t1) WHERE a>b;
4007 ** \ \_____________ subquery __________/ /
4008 ** \_____________________ outer query ______________________________/
4010 ** We look at every expression in the outer query and every place we see
4011 ** "a" we substitute "x*3" and every place we see "b" we substitute "y+10".
4013 if( pSub
->pOrderBy
){
4014 /* At this point, any non-zero iOrderByCol values indicate that the
4015 ** ORDER BY column expression is identical to the iOrderByCol'th
4016 ** expression returned by SELECT statement pSub. Since these values
4017 ** do not necessarily correspond to columns in SELECT statement pParent,
4018 ** zero them before transfering the ORDER BY clause.
4020 ** Not doing this may cause an error if a subsequent call to this
4021 ** function attempts to flatten a compound sub-query into pParent
4022 ** (the only way this can happen is if the compound sub-query is
4023 ** currently part of pSub->pSrc). See ticket [d11a6e908f]. */
4024 ExprList
*pOrderBy
= pSub
->pOrderBy
;
4025 for(i
=0; i
<pOrderBy
->nExpr
; i
++){
4026 pOrderBy
->a
[i
].u
.x
.iOrderByCol
= 0;
4028 assert( pParent
->pOrderBy
==0 );
4029 pParent
->pOrderBy
= pOrderBy
;
4032 pWhere
= pSub
->pWhere
;
4035 setJoinExpr(pWhere
, iNewParent
);
4037 pParent
->pWhere
= sqlite3ExprAnd(db
, pWhere
, pParent
->pWhere
);
4038 if( db
->mallocFailed
==0 ){
4042 x
.iNewTable
= iNewParent
;
4043 x
.isLeftJoin
= isLeftJoin
;
4044 x
.pEList
= pSub
->pEList
;
4045 substSelect(&x
, pParent
, 0);
4048 /* The flattened query is distinct if either the inner or the
4049 ** outer query is distinct.
4051 pParent
->selFlags
|= pSub
->selFlags
& SF_Distinct
;
4054 ** SELECT ... FROM (SELECT ... LIMIT a OFFSET b) LIMIT x OFFSET y;
4056 ** One is tempted to try to add a and b to combine the limits. But this
4057 ** does not work if either limit is negative.
4060 pParent
->pLimit
= pSub
->pLimit
;
4065 /* Finially, delete what is left of the subquery and return
4068 sqlite3SelectDelete(db
, pSub1
);
4070 #if SELECTTRACE_ENABLED
4071 if( sqlite3SelectTrace
& 0x100 ){
4072 SELECTTRACE(0x100,pParse
,p
,("After flattening:\n"));
4073 sqlite3TreeViewSelect(0, p
, 0);
4079 #endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */
4082 ** A structure to keep track of all of the column values that are fixed to
4083 ** a known value due to WHERE clause constraints of the form COLUMN=VALUE.
4085 typedef struct WhereConst WhereConst
;
4087 Parse
*pParse
; /* Parsing context */
4088 int nConst
; /* Number for COLUMN=CONSTANT terms */
4089 int nChng
; /* Number of times a constant is propagated */
4090 Expr
**apExpr
; /* [i*2] is COLUMN and [i*2+1] is VALUE */
4094 ** Add a new entry to the pConst object. Except, do not add duplicate
4097 static void constInsert(
4098 WhereConst
*pConst
, /* The WhereConst into which we are inserting */
4099 Expr
*pColumn
, /* The COLUMN part of the constraint */
4100 Expr
*pValue
/* The VALUE part of the constraint */
4103 assert( pColumn
->op
==TK_COLUMN
);
4105 /* 2018-10-25 ticket [cf5ed20f]
4106 ** Make sure the same pColumn is not inserted more than once */
4107 for(i
=0; i
<pConst
->nConst
; i
++){
4108 const Expr
*pExpr
= pConst
->apExpr
[i
*2];
4109 assert( pExpr
->op
==TK_COLUMN
);
4110 if( pExpr
->iTable
==pColumn
->iTable
4111 && pExpr
->iColumn
==pColumn
->iColumn
4113 return; /* Already present. Return without doing anything. */
4118 pConst
->apExpr
= sqlite3DbReallocOrFree(pConst
->pParse
->db
, pConst
->apExpr
,
4119 pConst
->nConst
*2*sizeof(Expr
*));
4120 if( pConst
->apExpr
==0 ){
4123 if( ExprHasProperty(pValue
, EP_FixedCol
) ) pValue
= pValue
->pLeft
;
4124 pConst
->apExpr
[pConst
->nConst
*2-2] = pColumn
;
4125 pConst
->apExpr
[pConst
->nConst
*2-1] = pValue
;
4130 ** Find all terms of COLUMN=VALUE or VALUE=COLUMN in pExpr where VALUE
4131 ** is a constant expression and where the term must be true because it
4132 ** is part of the AND-connected terms of the expression. For each term
4133 ** found, add it to the pConst structure.
4135 static void findConstInWhere(WhereConst
*pConst
, Expr
*pExpr
){
4136 Expr
*pRight
, *pLeft
;
4137 if( pExpr
==0 ) return;
4138 if( ExprHasProperty(pExpr
, EP_FromJoin
) ) return;
4139 if( pExpr
->op
==TK_AND
){
4140 findConstInWhere(pConst
, pExpr
->pRight
);
4141 findConstInWhere(pConst
, pExpr
->pLeft
);
4144 if( pExpr
->op
!=TK_EQ
) return;
4145 pRight
= pExpr
->pRight
;
4146 pLeft
= pExpr
->pLeft
;
4147 assert( pRight
!=0 );
4149 if( pRight
->op
==TK_COLUMN
4150 && !ExprHasProperty(pRight
, EP_FixedCol
)
4151 && sqlite3ExprIsConstant(pLeft
)
4152 && sqlite3IsBinary(sqlite3BinaryCompareCollSeq(pConst
->pParse
,pLeft
,pRight
))
4154 constInsert(pConst
, pRight
, pLeft
);
4156 if( pLeft
->op
==TK_COLUMN
4157 && !ExprHasProperty(pLeft
, EP_FixedCol
)
4158 && sqlite3ExprIsConstant(pRight
)
4159 && sqlite3IsBinary(sqlite3BinaryCompareCollSeq(pConst
->pParse
,pLeft
,pRight
))
4161 constInsert(pConst
, pLeft
, pRight
);
4166 ** This is a Walker expression callback. pExpr is a candidate expression
4167 ** to be replaced by a value. If pExpr is equivalent to one of the
4168 ** columns named in pWalker->u.pConst, then overwrite it with its
4169 ** corresponding value.
4171 static int propagateConstantExprRewrite(Walker
*pWalker
, Expr
*pExpr
){
4174 if( pExpr
->op
!=TK_COLUMN
) return WRC_Continue
;
4175 if( ExprHasProperty(pExpr
, EP_FixedCol
) ) return WRC_Continue
;
4176 pConst
= pWalker
->u
.pConst
;
4177 for(i
=0; i
<pConst
->nConst
; i
++){
4178 Expr
*pColumn
= pConst
->apExpr
[i
*2];
4179 if( pColumn
==pExpr
) continue;
4180 if( pColumn
->iTable
!=pExpr
->iTable
) continue;
4181 if( pColumn
->iColumn
!=pExpr
->iColumn
) continue;
4182 /* A match is found. Add the EP_FixedCol property */
4184 ExprClearProperty(pExpr
, EP_Leaf
);
4185 ExprSetProperty(pExpr
, EP_FixedCol
);
4186 assert( pExpr
->pLeft
==0 );
4187 pExpr
->pLeft
= sqlite3ExprDup(pConst
->pParse
->db
, pConst
->apExpr
[i
*2+1], 0);
4194 ** The WHERE-clause constant propagation optimization.
4196 ** If the WHERE clause contains terms of the form COLUMN=CONSTANT or
4197 ** CONSTANT=COLUMN that must be tree (in other words, if the terms top-level
4198 ** AND-connected terms that are not part of a ON clause from a LEFT JOIN)
4199 ** then throughout the query replace all other occurrences of COLUMN
4200 ** with CONSTANT within the WHERE clause.
4202 ** For example, the query:
4204 ** SELECT * FROM t1, t2, t3 WHERE t1.a=39 AND t2.b=t1.a AND t3.c=t2.b
4206 ** Is transformed into
4208 ** SELECT * FROM t1, t2, t3 WHERE t1.a=39 AND t2.b=39 AND t3.c=39
4210 ** Return true if any transformations where made and false if not.
4212 ** Implementation note: Constant propagation is tricky due to affinity
4213 ** and collating sequence interactions. Consider this example:
4215 ** CREATE TABLE t1(a INT,b TEXT);
4216 ** INSERT INTO t1 VALUES(123,'0123');
4217 ** SELECT * FROM t1 WHERE a=123 AND b=a;
4218 ** SELECT * FROM t1 WHERE a=123 AND b=123;
4220 ** The two SELECT statements above should return different answers. b=a
4221 ** is alway true because the comparison uses numeric affinity, but b=123
4222 ** is false because it uses text affinity and '0123' is not the same as '123'.
4223 ** To work around this, the expression tree is not actually changed from
4224 ** "b=a" to "b=123" but rather the "a" in "b=a" is tagged with EP_FixedCol
4225 ** and the "123" value is hung off of the pLeft pointer. Code generator
4226 ** routines know to generate the constant "123" instead of looking up the
4227 ** column value. Also, to avoid collation problems, this optimization is
4228 ** only attempted if the "a=123" term uses the default BINARY collation.
4230 static int propagateConstants(
4231 Parse
*pParse
, /* The parsing context */
4232 Select
*p
/* The query in which to propagate constants */
4242 findConstInWhere(&x
, p
->pWhere
);
4244 memset(&w
, 0, sizeof(w
));
4246 w
.xExprCallback
= propagateConstantExprRewrite
;
4247 w
.xSelectCallback
= sqlite3SelectWalkNoop
;
4248 w
.xSelectCallback2
= 0;
4251 sqlite3WalkExpr(&w
, p
->pWhere
);
4252 sqlite3DbFree(x
.pParse
->db
, x
.apExpr
);
4259 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
4261 ** Make copies of relevant WHERE clause terms of the outer query into
4262 ** the WHERE clause of subquery. Example:
4264 ** SELECT * FROM (SELECT a AS x, c-d AS y FROM t1) WHERE x=5 AND y=10;
4266 ** Transformed into:
4268 ** SELECT * FROM (SELECT a AS x, c-d AS y FROM t1 WHERE a=5 AND c-d=10)
4269 ** WHERE x=5 AND y=10;
4271 ** The hope is that the terms added to the inner query will make it more
4274 ** Do not attempt this optimization if:
4276 ** (1) (** This restriction was removed on 2017-09-29. We used to
4277 ** disallow this optimization for aggregate subqueries, but now
4278 ** it is allowed by putting the extra terms on the HAVING clause.
4279 ** The added HAVING clause is pointless if the subquery lacks
4280 ** a GROUP BY clause. But such a HAVING clause is also harmless
4281 ** so there does not appear to be any reason to add extra logic
4282 ** to suppress it. **)
4284 ** (2) The inner query is the recursive part of a common table expression.
4286 ** (3) The inner query has a LIMIT clause (since the changes to the WHERE
4287 ** clause would change the meaning of the LIMIT).
4289 ** (4) The inner query is the right operand of a LEFT JOIN and the
4290 ** expression to be pushed down does not come from the ON clause
4291 ** on that LEFT JOIN.
4293 ** (5) The WHERE clause expression originates in the ON or USING clause
4294 ** of a LEFT JOIN where iCursor is not the right-hand table of that
4295 ** left join. An example:
4298 ** FROM (SELECT 1 AS a1 UNION ALL SELECT 2) AS aa
4299 ** JOIN (SELECT 1 AS b2 UNION ALL SELECT 2) AS bb ON (a1=b2)
4300 ** LEFT JOIN (SELECT 8 AS c3 UNION ALL SELECT 9) AS cc ON (b2=2);
4302 ** The correct answer is three rows: (1,1,NULL),(2,2,8),(2,2,9).
4303 ** But if the (b2=2) term were to be pushed down into the bb subquery,
4304 ** then the (1,1,NULL) row would be suppressed.
4306 ** (6) The inner query features one or more window-functions (since
4307 ** changes to the WHERE clause of the inner query could change the
4308 ** window over which window functions are calculated).
4310 ** Return 0 if no changes are made and non-zero if one or more WHERE clause
4311 ** terms are duplicated into the subquery.
4313 static int pushDownWhereTerms(
4314 Parse
*pParse
, /* Parse context (for malloc() and error reporting) */
4315 Select
*pSubq
, /* The subquery whose WHERE clause is to be augmented */
4316 Expr
*pWhere
, /* The WHERE clause of the outer query */
4317 int iCursor
, /* Cursor number of the subquery */
4318 int isLeftJoin
/* True if pSubq is the right term of a LEFT JOIN */
4322 if( pWhere
==0 ) return 0;
4323 if( pSubq
->selFlags
& SF_Recursive
) return 0; /* restriction (2) */
4325 #ifndef SQLITE_OMIT_WINDOWFUNC
4326 if( pSubq
->pWin
) return 0; /* restriction (6) */
4330 /* Only the first term of a compound can have a WITH clause. But make
4331 ** sure no other terms are marked SF_Recursive in case something changes
4336 for(pX
=pSubq
; pX
; pX
=pX
->pPrior
){
4337 assert( (pX
->selFlags
& (SF_Recursive
))==0 );
4342 if( pSubq
->pLimit
!=0 ){
4343 return 0; /* restriction (3) */
4345 while( pWhere
->op
==TK_AND
){
4346 nChng
+= pushDownWhereTerms(pParse
, pSubq
, pWhere
->pRight
,
4347 iCursor
, isLeftJoin
);
4348 pWhere
= pWhere
->pLeft
;
4351 && (ExprHasProperty(pWhere
,EP_FromJoin
)==0
4352 || pWhere
->iRightJoinTable
!=iCursor
)
4354 return 0; /* restriction (4) */
4356 if( ExprHasProperty(pWhere
,EP_FromJoin
) && pWhere
->iRightJoinTable
!=iCursor
){
4357 return 0; /* restriction (5) */
4359 if( sqlite3ExprIsTableConstant(pWhere
, iCursor
) ){
4363 pNew
= sqlite3ExprDup(pParse
->db
, pWhere
, 0);
4364 unsetJoinExpr(pNew
, -1);
4367 x
.iNewTable
= iCursor
;
4369 x
.pEList
= pSubq
->pEList
;
4370 pNew
= substExpr(&x
, pNew
);
4371 if( pSubq
->selFlags
& SF_Aggregate
){
4372 pSubq
->pHaving
= sqlite3ExprAnd(pParse
->db
, pSubq
->pHaving
, pNew
);
4374 pSubq
->pWhere
= sqlite3ExprAnd(pParse
->db
, pSubq
->pWhere
, pNew
);
4376 pSubq
= pSubq
->pPrior
;
4381 #endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */
4384 ** The pFunc is the only aggregate function in the query. Check to see
4385 ** if the query is a candidate for the min/max optimization.
4387 ** If the query is a candidate for the min/max optimization, then set
4388 ** *ppMinMax to be an ORDER BY clause to be used for the optimization
4389 ** and return either WHERE_ORDERBY_MIN or WHERE_ORDERBY_MAX depending on
4390 ** whether pFunc is a min() or max() function.
4392 ** If the query is not a candidate for the min/max optimization, return
4393 ** WHERE_ORDERBY_NORMAL (which must be zero).
4395 ** This routine must be called after aggregate functions have been
4396 ** located but before their arguments have been subjected to aggregate
4399 static u8
minMaxQuery(sqlite3
*db
, Expr
*pFunc
, ExprList
**ppMinMax
){
4400 int eRet
= WHERE_ORDERBY_NORMAL
; /* Return value */
4401 ExprList
*pEList
= pFunc
->x
.pList
; /* Arguments to agg function */
4402 const char *zFunc
; /* Name of aggregate function pFunc */
4406 assert( *ppMinMax
==0 );
4407 assert( pFunc
->op
==TK_AGG_FUNCTION
);
4408 if( pEList
==0 || pEList
->nExpr
!=1 ) return eRet
;
4409 zFunc
= pFunc
->u
.zToken
;
4410 if( sqlite3StrICmp(zFunc
, "min")==0 ){
4411 eRet
= WHERE_ORDERBY_MIN
;
4412 sortOrder
= SQLITE_SO_ASC
;
4413 }else if( sqlite3StrICmp(zFunc
, "max")==0 ){
4414 eRet
= WHERE_ORDERBY_MAX
;
4415 sortOrder
= SQLITE_SO_DESC
;
4419 *ppMinMax
= pOrderBy
= sqlite3ExprListDup(db
, pEList
, 0);
4420 assert( pOrderBy
!=0 || db
->mallocFailed
);
4421 if( pOrderBy
) pOrderBy
->a
[0].sortOrder
= sortOrder
;
4426 ** The select statement passed as the first argument is an aggregate query.
4427 ** The second argument is the associated aggregate-info object. This
4428 ** function tests if the SELECT is of the form:
4430 ** SELECT count(*) FROM <tbl>
4432 ** where table is a database table, not a sub-select or view. If the query
4433 ** does match this pattern, then a pointer to the Table object representing
4434 ** <tbl> is returned. Otherwise, 0 is returned.
4436 static Table
*isSimpleCount(Select
*p
, AggInfo
*pAggInfo
){
4440 assert( !p
->pGroupBy
);
4442 if( p
->pWhere
|| p
->pEList
->nExpr
!=1
4443 || p
->pSrc
->nSrc
!=1 || p
->pSrc
->a
[0].pSelect
4447 pTab
= p
->pSrc
->a
[0].pTab
;
4448 pExpr
= p
->pEList
->a
[0].pExpr
;
4449 assert( pTab
&& !pTab
->pSelect
&& pExpr
);
4451 if( IsVirtual(pTab
) ) return 0;
4452 if( pExpr
->op
!=TK_AGG_FUNCTION
) return 0;
4453 if( NEVER(pAggInfo
->nFunc
==0) ) return 0;
4454 if( (pAggInfo
->aFunc
[0].pFunc
->funcFlags
&SQLITE_FUNC_COUNT
)==0 ) return 0;
4455 if( pExpr
->flags
&EP_Distinct
) return 0;
4461 ** If the source-list item passed as an argument was augmented with an
4462 ** INDEXED BY clause, then try to locate the specified index. If there
4463 ** was such a clause and the named index cannot be found, return
4464 ** SQLITE_ERROR and leave an error in pParse. Otherwise, populate
4465 ** pFrom->pIndex and return SQLITE_OK.
4467 int sqlite3IndexedByLookup(Parse
*pParse
, struct SrcList_item
*pFrom
){
4468 if( pFrom
->pTab
&& pFrom
->fg
.isIndexedBy
){
4469 Table
*pTab
= pFrom
->pTab
;
4470 char *zIndexedBy
= pFrom
->u1
.zIndexedBy
;
4472 for(pIdx
=pTab
->pIndex
;
4473 pIdx
&& sqlite3StrICmp(pIdx
->zName
, zIndexedBy
);
4477 sqlite3ErrorMsg(pParse
, "no such index: %s", zIndexedBy
, 0);
4478 pParse
->checkSchema
= 1;
4479 return SQLITE_ERROR
;
4481 pFrom
->pIBIndex
= pIdx
;
4486 ** Detect compound SELECT statements that use an ORDER BY clause with
4487 ** an alternative collating sequence.
4489 ** SELECT ... FROM t1 EXCEPT SELECT ... FROM t2 ORDER BY .. COLLATE ...
4491 ** These are rewritten as a subquery:
4493 ** SELECT * FROM (SELECT ... FROM t1 EXCEPT SELECT ... FROM t2)
4494 ** ORDER BY ... COLLATE ...
4496 ** This transformation is necessary because the multiSelectOrderBy() routine
4497 ** above that generates the code for a compound SELECT with an ORDER BY clause
4498 ** uses a merge algorithm that requires the same collating sequence on the
4499 ** result columns as on the ORDER BY clause. See ticket
4500 ** http://www.sqlite.org/src/info/6709574d2a
4502 ** This transformation is only needed for EXCEPT, INTERSECT, and UNION.
4503 ** The UNION ALL operator works fine with multiSelectOrderBy() even when
4504 ** there are COLLATE terms in the ORDER BY.
4506 static int convertCompoundSelectToSubquery(Walker
*pWalker
, Select
*p
){
4511 struct ExprList_item
*a
;
4516 if( p
->pPrior
==0 ) return WRC_Continue
;
4517 if( p
->pOrderBy
==0 ) return WRC_Continue
;
4518 for(pX
=p
; pX
&& (pX
->op
==TK_ALL
|| pX
->op
==TK_SELECT
); pX
=pX
->pPrior
){}
4519 if( pX
==0 ) return WRC_Continue
;
4521 for(i
=p
->pOrderBy
->nExpr
-1; i
>=0; i
--){
4522 if( a
[i
].pExpr
->flags
& EP_Collate
) break;
4524 if( i
<0 ) return WRC_Continue
;
4526 /* If we reach this point, that means the transformation is required. */
4528 pParse
= pWalker
->pParse
;
4530 pNew
= sqlite3DbMallocZero(db
, sizeof(*pNew
) );
4531 if( pNew
==0 ) return WRC_Abort
;
4532 memset(&dummy
, 0, sizeof(dummy
));
4533 pNewSrc
= sqlite3SrcListAppendFromTerm(pParse
,0,0,0,&dummy
,pNew
,0,0);
4534 if( pNewSrc
==0 ) return WRC_Abort
;
4537 p
->pEList
= sqlite3ExprListAppend(pParse
, 0, sqlite3Expr(db
, TK_ASTERISK
, 0));
4546 p
->selFlags
&= ~SF_Compound
;
4547 assert( (p
->selFlags
& SF_Converted
)==0 );
4548 p
->selFlags
|= SF_Converted
;
4549 assert( pNew
->pPrior
!=0 );
4550 pNew
->pPrior
->pNext
= pNew
;
4552 return WRC_Continue
;
4556 ** Check to see if the FROM clause term pFrom has table-valued function
4557 ** arguments. If it does, leave an error message in pParse and return
4558 ** non-zero, since pFrom is not allowed to be a table-valued function.
4560 static int cannotBeFunction(Parse
*pParse
, struct SrcList_item
*pFrom
){
4561 if( pFrom
->fg
.isTabFunc
){
4562 sqlite3ErrorMsg(pParse
, "'%s' is not a function", pFrom
->zName
);
4568 #ifndef SQLITE_OMIT_CTE
4570 ** Argument pWith (which may be NULL) points to a linked list of nested
4571 ** WITH contexts, from inner to outermost. If the table identified by
4572 ** FROM clause element pItem is really a common-table-expression (CTE)
4573 ** then return a pointer to the CTE definition for that table. Otherwise
4576 ** If a non-NULL value is returned, set *ppContext to point to the With
4577 ** object that the returned CTE belongs to.
4579 static struct Cte
*searchWith(
4580 With
*pWith
, /* Current innermost WITH clause */
4581 struct SrcList_item
*pItem
, /* FROM clause element to resolve */
4582 With
**ppContext
/* OUT: WITH clause return value belongs to */
4585 if( pItem
->zDatabase
==0 && (zName
= pItem
->zName
)!=0 ){
4587 for(p
=pWith
; p
; p
=p
->pOuter
){
4589 for(i
=0; i
<p
->nCte
; i
++){
4590 if( sqlite3StrICmp(zName
, p
->a
[i
].zName
)==0 ){
4600 /* The code generator maintains a stack of active WITH clauses
4601 ** with the inner-most WITH clause being at the top of the stack.
4603 ** This routine pushes the WITH clause passed as the second argument
4604 ** onto the top of the stack. If argument bFree is true, then this
4605 ** WITH clause will never be popped from the stack. In this case it
4606 ** should be freed along with the Parse object. In other cases, when
4607 ** bFree==0, the With object will be freed along with the SELECT
4608 ** statement with which it is associated.
4610 void sqlite3WithPush(Parse
*pParse
, With
*pWith
, u8 bFree
){
4611 assert( bFree
==0 || (pParse
->pWith
==0 && pParse
->pWithToFree
==0) );
4613 assert( pParse
->pWith
!=pWith
);
4614 pWith
->pOuter
= pParse
->pWith
;
4615 pParse
->pWith
= pWith
;
4616 if( bFree
) pParse
->pWithToFree
= pWith
;
4621 ** This function checks if argument pFrom refers to a CTE declared by
4622 ** a WITH clause on the stack currently maintained by the parser. And,
4623 ** if currently processing a CTE expression, if it is a recursive
4624 ** reference to the current CTE.
4626 ** If pFrom falls into either of the two categories above, pFrom->pTab
4627 ** and other fields are populated accordingly. The caller should check
4628 ** (pFrom->pTab!=0) to determine whether or not a successful match
4631 ** Whether or not a match is found, SQLITE_OK is returned if no error
4632 ** occurs. If an error does occur, an error message is stored in the
4633 ** parser and some error code other than SQLITE_OK returned.
4635 static int withExpand(
4637 struct SrcList_item
*pFrom
4639 Parse
*pParse
= pWalker
->pParse
;
4640 sqlite3
*db
= pParse
->db
;
4641 struct Cte
*pCte
; /* Matched CTE (or NULL if no match) */
4642 With
*pWith
; /* WITH clause that pCte belongs to */
4644 assert( pFrom
->pTab
==0 );
4646 pCte
= searchWith(pParse
->pWith
, pFrom
, &pWith
);
4651 Select
*pLeft
; /* Left-most SELECT statement */
4652 int bMayRecursive
; /* True if compound joined by UNION [ALL] */
4653 With
*pSavedWith
; /* Initial value of pParse->pWith */
4655 /* If pCte->zCteErr is non-NULL at this point, then this is an illegal
4656 ** recursive reference to CTE pCte. Leave an error in pParse and return
4657 ** early. If pCte->zCteErr is NULL, then this is not a recursive reference.
4658 ** In this case, proceed. */
4659 if( pCte
->zCteErr
){
4660 sqlite3ErrorMsg(pParse
, pCte
->zCteErr
, pCte
->zName
);
4661 return SQLITE_ERROR
;
4663 if( cannotBeFunction(pParse
, pFrom
) ) return SQLITE_ERROR
;
4665 assert( pFrom
->pTab
==0 );
4666 pFrom
->pTab
= pTab
= sqlite3DbMallocZero(db
, sizeof(Table
));
4667 if( pTab
==0 ) return WRC_Abort
;
4669 pTab
->zName
= sqlite3DbStrDup(db
, pCte
->zName
);
4671 pTab
->nRowLogEst
= 200; assert( 200==sqlite3LogEst(1048576) );
4672 pTab
->tabFlags
|= TF_Ephemeral
| TF_NoVisibleRowid
;
4673 pFrom
->pSelect
= sqlite3SelectDup(db
, pCte
->pSelect
, 0);
4674 if( db
->mallocFailed
) return SQLITE_NOMEM_BKPT
;
4675 assert( pFrom
->pSelect
);
4677 /* Check if this is a recursive CTE. */
4678 pSel
= pFrom
->pSelect
;
4679 bMayRecursive
= ( pSel
->op
==TK_ALL
|| pSel
->op
==TK_UNION
);
4680 if( bMayRecursive
){
4682 SrcList
*pSrc
= pFrom
->pSelect
->pSrc
;
4683 for(i
=0; i
<pSrc
->nSrc
; i
++){
4684 struct SrcList_item
*pItem
= &pSrc
->a
[i
];
4685 if( pItem
->zDatabase
==0
4687 && 0==sqlite3StrICmp(pItem
->zName
, pCte
->zName
)
4690 pItem
->fg
.isRecursive
= 1;
4692 pSel
->selFlags
|= SF_Recursive
;
4697 /* Only one recursive reference is permitted. */
4698 if( pTab
->nTabRef
>2 ){
4700 pParse
, "multiple references to recursive table: %s", pCte
->zName
4702 return SQLITE_ERROR
;
4704 assert( pTab
->nTabRef
==1 ||
4705 ((pSel
->selFlags
&SF_Recursive
) && pTab
->nTabRef
==2 ));
4707 pCte
->zCteErr
= "circular reference: %s";
4708 pSavedWith
= pParse
->pWith
;
4709 pParse
->pWith
= pWith
;
4710 if( bMayRecursive
){
4711 Select
*pPrior
= pSel
->pPrior
;
4712 assert( pPrior
->pWith
==0 );
4713 pPrior
->pWith
= pSel
->pWith
;
4714 sqlite3WalkSelect(pWalker
, pPrior
);
4717 sqlite3WalkSelect(pWalker
, pSel
);
4719 pParse
->pWith
= pWith
;
4721 for(pLeft
=pSel
; pLeft
->pPrior
; pLeft
=pLeft
->pPrior
);
4722 pEList
= pLeft
->pEList
;
4724 if( pEList
&& pEList
->nExpr
!=pCte
->pCols
->nExpr
){
4725 sqlite3ErrorMsg(pParse
, "table %s has %d values for %d columns",
4726 pCte
->zName
, pEList
->nExpr
, pCte
->pCols
->nExpr
4728 pParse
->pWith
= pSavedWith
;
4729 return SQLITE_ERROR
;
4731 pEList
= pCte
->pCols
;
4734 sqlite3ColumnsFromExprList(pParse
, pEList
, &pTab
->nCol
, &pTab
->aCol
);
4735 if( bMayRecursive
){
4736 if( pSel
->selFlags
& SF_Recursive
){
4737 pCte
->zCteErr
= "multiple recursive references: %s";
4739 pCte
->zCteErr
= "recursive reference in a subquery: %s";
4741 sqlite3WalkSelect(pWalker
, pSel
);
4744 pParse
->pWith
= pSavedWith
;
4751 #ifndef SQLITE_OMIT_CTE
4753 ** If the SELECT passed as the second argument has an associated WITH
4754 ** clause, pop it from the stack stored as part of the Parse object.
4756 ** This function is used as the xSelectCallback2() callback by
4757 ** sqlite3SelectExpand() when walking a SELECT tree to resolve table
4758 ** names and other FROM clause elements.
4760 static void selectPopWith(Walker
*pWalker
, Select
*p
){
4761 Parse
*pParse
= pWalker
->pParse
;
4762 if( OK_IF_ALWAYS_TRUE(pParse
->pWith
) && p
->pPrior
==0 ){
4763 With
*pWith
= findRightmost(p
)->pWith
;
4765 assert( pParse
->pWith
==pWith
);
4766 pParse
->pWith
= pWith
->pOuter
;
4771 #define selectPopWith 0
4775 ** The SrcList_item structure passed as the second argument represents a
4776 ** sub-query in the FROM clause of a SELECT statement. This function
4777 ** allocates and populates the SrcList_item.pTab object. If successful,
4778 ** SQLITE_OK is returned. Otherwise, if an OOM error is encountered,
4781 int sqlite3ExpandSubquery(Parse
*pParse
, struct SrcList_item
*pFrom
){
4782 Select
*pSel
= pFrom
->pSelect
;
4786 pFrom
->pTab
= pTab
= sqlite3DbMallocZero(pParse
->db
, sizeof(Table
));
4787 if( pTab
==0 ) return SQLITE_NOMEM
;
4789 if( pFrom
->zAlias
){
4790 pTab
->zName
= sqlite3DbStrDup(pParse
->db
, pFrom
->zAlias
);
4792 pTab
->zName
= sqlite3MPrintf(pParse
->db
, "subquery_%u", pSel
->selId
);
4794 while( pSel
->pPrior
){ pSel
= pSel
->pPrior
; }
4795 sqlite3ColumnsFromExprList(pParse
, pSel
->pEList
,&pTab
->nCol
,&pTab
->aCol
);
4797 pTab
->nRowLogEst
= 200; assert( 200==sqlite3LogEst(1048576) );
4798 pTab
->tabFlags
|= TF_Ephemeral
;
4804 ** This routine is a Walker callback for "expanding" a SELECT statement.
4805 ** "Expanding" means to do the following:
4807 ** (1) Make sure VDBE cursor numbers have been assigned to every
4808 ** element of the FROM clause.
4810 ** (2) Fill in the pTabList->a[].pTab fields in the SrcList that
4811 ** defines FROM clause. When views appear in the FROM clause,
4812 ** fill pTabList->a[].pSelect with a copy of the SELECT statement
4813 ** that implements the view. A copy is made of the view's SELECT
4814 ** statement so that we can freely modify or delete that statement
4815 ** without worrying about messing up the persistent representation
4818 ** (3) Add terms to the WHERE clause to accommodate the NATURAL keyword
4819 ** on joins and the ON and USING clause of joins.
4821 ** (4) Scan the list of columns in the result set (pEList) looking
4822 ** for instances of the "*" operator or the TABLE.* operator.
4823 ** If found, expand each "*" to be every column in every table
4824 ** and TABLE.* to be every column in TABLE.
4827 static int selectExpander(Walker
*pWalker
, Select
*p
){
4828 Parse
*pParse
= pWalker
->pParse
;
4832 struct SrcList_item
*pFrom
;
4833 sqlite3
*db
= pParse
->db
;
4834 Expr
*pE
, *pRight
, *pExpr
;
4835 u16 selFlags
= p
->selFlags
;
4838 p
->selFlags
|= SF_Expanded
;
4839 if( db
->mallocFailed
){
4842 assert( p
->pSrc
!=0 );
4843 if( (selFlags
& SF_Expanded
)!=0 ){
4848 sqlite3WithPush(pParse
, p
->pWith
, 0);
4850 /* Make sure cursor numbers have been assigned to all entries in
4851 ** the FROM clause of the SELECT statement.
4853 sqlite3SrcListAssignCursors(pParse
, pTabList
);
4855 /* Look up every table named in the FROM clause of the select. If
4856 ** an entry of the FROM clause is a subquery instead of a table or view,
4857 ** then create a transient table structure to describe the subquery.
4859 for(i
=0, pFrom
=pTabList
->a
; i
<pTabList
->nSrc
; i
++, pFrom
++){
4861 assert( pFrom
->fg
.isRecursive
==0 || pFrom
->pTab
!=0 );
4862 if( pFrom
->fg
.isRecursive
) continue;
4863 assert( pFrom
->pTab
==0 );
4864 #ifndef SQLITE_OMIT_CTE
4865 if( withExpand(pWalker
, pFrom
) ) return WRC_Abort
;
4866 if( pFrom
->pTab
) {} else
4868 if( pFrom
->zName
==0 ){
4869 #ifndef SQLITE_OMIT_SUBQUERY
4870 Select
*pSel
= pFrom
->pSelect
;
4871 /* A sub-query in the FROM clause of a SELECT */
4873 assert( pFrom
->pTab
==0 );
4874 if( sqlite3WalkSelect(pWalker
, pSel
) ) return WRC_Abort
;
4875 if( sqlite3ExpandSubquery(pParse
, pFrom
) ) return WRC_Abort
;
4878 /* An ordinary table or view name in the FROM clause */
4879 assert( pFrom
->pTab
==0 );
4880 pFrom
->pTab
= pTab
= sqlite3LocateTableItem(pParse
, 0, pFrom
);
4881 if( pTab
==0 ) return WRC_Abort
;
4882 if( pTab
->nTabRef
>=0xffff ){
4883 sqlite3ErrorMsg(pParse
, "too many references to \"%s\": max 65535",
4889 if( !IsVirtual(pTab
) && cannotBeFunction(pParse
, pFrom
) ){
4892 #if !defined(SQLITE_OMIT_VIEW) || !defined (SQLITE_OMIT_VIRTUALTABLE)
4893 if( IsVirtual(pTab
) || pTab
->pSelect
){
4895 if( sqlite3ViewGetColumnNames(pParse
, pTab
) ) return WRC_Abort
;
4896 assert( pFrom
->pSelect
==0 );
4897 pFrom
->pSelect
= sqlite3SelectDup(db
, pTab
->pSelect
, 0);
4900 sqlite3WalkSelect(pWalker
, pFrom
->pSelect
);
4906 /* Locate the index named by the INDEXED BY clause, if any. */
4907 if( sqlite3IndexedByLookup(pParse
, pFrom
) ){
4912 /* Process NATURAL keywords, and ON and USING clauses of joins.
4914 if( db
->mallocFailed
|| sqliteProcessJoin(pParse
, p
) ){
4918 /* For every "*" that occurs in the column list, insert the names of
4919 ** all columns in all tables. And for every TABLE.* insert the names
4920 ** of all columns in TABLE. The parser inserted a special expression
4921 ** with the TK_ASTERISK operator for each "*" that it found in the column
4922 ** list. The following code just has to locate the TK_ASTERISK
4923 ** expressions and expand each one to the list of all columns in
4926 ** The first loop just checks to see if there are any "*" operators
4927 ** that need expanding.
4929 for(k
=0; k
<pEList
->nExpr
; k
++){
4930 pE
= pEList
->a
[k
].pExpr
;
4931 if( pE
->op
==TK_ASTERISK
) break;
4932 assert( pE
->op
!=TK_DOT
|| pE
->pRight
!=0 );
4933 assert( pE
->op
!=TK_DOT
|| (pE
->pLeft
!=0 && pE
->pLeft
->op
==TK_ID
) );
4934 if( pE
->op
==TK_DOT
&& pE
->pRight
->op
==TK_ASTERISK
) break;
4935 elistFlags
|= pE
->flags
;
4937 if( k
<pEList
->nExpr
){
4939 ** If we get here it means the result set contains one or more "*"
4940 ** operators that need to be expanded. Loop through each expression
4941 ** in the result set and expand them one by one.
4943 struct ExprList_item
*a
= pEList
->a
;
4945 int flags
= pParse
->db
->flags
;
4946 int longNames
= (flags
& SQLITE_FullColNames
)!=0
4947 && (flags
& SQLITE_ShortColNames
)==0;
4949 for(k
=0; k
<pEList
->nExpr
; k
++){
4951 elistFlags
|= pE
->flags
;
4952 pRight
= pE
->pRight
;
4953 assert( pE
->op
!=TK_DOT
|| pRight
!=0 );
4954 if( pE
->op
!=TK_ASTERISK
4955 && (pE
->op
!=TK_DOT
|| pRight
->op
!=TK_ASTERISK
)
4957 /* This particular expression does not need to be expanded.
4959 pNew
= sqlite3ExprListAppend(pParse
, pNew
, a
[k
].pExpr
);
4961 pNew
->a
[pNew
->nExpr
-1].zName
= a
[k
].zName
;
4962 pNew
->a
[pNew
->nExpr
-1].zSpan
= a
[k
].zSpan
;
4968 /* This expression is a "*" or a "TABLE.*" and needs to be
4970 int tableSeen
= 0; /* Set to 1 when TABLE matches */
4971 char *zTName
= 0; /* text of name of TABLE */
4972 if( pE
->op
==TK_DOT
){
4973 assert( pE
->pLeft
!=0 );
4974 assert( !ExprHasProperty(pE
->pLeft
, EP_IntValue
) );
4975 zTName
= pE
->pLeft
->u
.zToken
;
4977 for(i
=0, pFrom
=pTabList
->a
; i
<pTabList
->nSrc
; i
++, pFrom
++){
4978 Table
*pTab
= pFrom
->pTab
;
4979 Select
*pSub
= pFrom
->pSelect
;
4980 char *zTabName
= pFrom
->zAlias
;
4981 const char *zSchemaName
= 0;
4984 zTabName
= pTab
->zName
;
4986 if( db
->mallocFailed
) break;
4987 if( pSub
==0 || (pSub
->selFlags
& SF_NestedFrom
)==0 ){
4989 if( zTName
&& sqlite3StrICmp(zTName
, zTabName
)!=0 ){
4992 iDb
= sqlite3SchemaToIndex(db
, pTab
->pSchema
);
4993 zSchemaName
= iDb
>=0 ? db
->aDb
[iDb
].zDbSName
: "*";
4995 for(j
=0; j
<pTab
->nCol
; j
++){
4996 char *zName
= pTab
->aCol
[j
].zName
;
4997 char *zColname
; /* The computed column name */
4998 char *zToFree
; /* Malloced string that needs to be freed */
4999 Token sColname
; /* Computed column name as a token */
5003 && sqlite3MatchSpanName(pSub
->pEList
->a
[j
].zSpan
, 0, zTName
, 0)==0
5008 /* If a column is marked as 'hidden', omit it from the expanded
5009 ** result-set list unless the SELECT has the SF_IncludeHidden
5012 if( (p
->selFlags
& SF_IncludeHidden
)==0
5013 && IsHiddenColumn(&pTab
->aCol
[j
])
5019 if( i
>0 && zTName
==0 ){
5020 if( (pFrom
->fg
.jointype
& JT_NATURAL
)!=0
5021 && tableAndColumnIndex(pTabList
, i
, zName
, 0, 0)
5023 /* In a NATURAL join, omit the join columns from the
5024 ** table to the right of the join */
5027 if( sqlite3IdListIndex(pFrom
->pUsing
, zName
)>=0 ){
5028 /* In a join with a USING clause, omit columns in the
5029 ** using clause from the table on the right. */
5033 pRight
= sqlite3Expr(db
, TK_ID
, zName
);
5036 if( longNames
|| pTabList
->nSrc
>1 ){
5038 pLeft
= sqlite3Expr(db
, TK_ID
, zTabName
);
5039 pExpr
= sqlite3PExpr(pParse
, TK_DOT
, pLeft
, pRight
);
5041 pLeft
= sqlite3Expr(db
, TK_ID
, zSchemaName
);
5042 pExpr
= sqlite3PExpr(pParse
, TK_DOT
, pLeft
, pExpr
);
5045 zColname
= sqlite3MPrintf(db
, "%s.%s", zTabName
, zName
);
5051 pNew
= sqlite3ExprListAppend(pParse
, pNew
, pExpr
);
5052 sqlite3TokenInit(&sColname
, zColname
);
5053 sqlite3ExprListSetName(pParse
, pNew
, &sColname
, 0);
5054 if( pNew
&& (p
->selFlags
& SF_NestedFrom
)!=0 ){
5055 struct ExprList_item
*pX
= &pNew
->a
[pNew
->nExpr
-1];
5057 pX
->zSpan
= sqlite3DbStrDup(db
, pSub
->pEList
->a
[j
].zSpan
);
5058 testcase( pX
->zSpan
==0 );
5060 pX
->zSpan
= sqlite3MPrintf(db
, "%s.%s.%s",
5061 zSchemaName
, zTabName
, zColname
);
5062 testcase( pX
->zSpan
==0 );
5066 sqlite3DbFree(db
, zToFree
);
5071 sqlite3ErrorMsg(pParse
, "no such table: %s", zTName
);
5073 sqlite3ErrorMsg(pParse
, "no tables specified");
5078 sqlite3ExprListDelete(db
, pEList
);
5082 if( p
->pEList
->nExpr
>db
->aLimit
[SQLITE_LIMIT_COLUMN
] ){
5083 sqlite3ErrorMsg(pParse
, "too many columns in result set");
5086 if( (elistFlags
& (EP_HasFunc
|EP_Subquery
))!=0 ){
5087 p
->selFlags
|= SF_ComplexResult
;
5090 return WRC_Continue
;
5094 ** No-op routine for the parse-tree walker.
5096 ** When this routine is the Walker.xExprCallback then expression trees
5097 ** are walked without any actions being taken at each node. Presumably,
5098 ** when this routine is used for Walker.xExprCallback then
5099 ** Walker.xSelectCallback is set to do something useful for every
5100 ** subquery in the parser tree.
5102 int sqlite3ExprWalkNoop(Walker
*NotUsed
, Expr
*NotUsed2
){
5103 UNUSED_PARAMETER2(NotUsed
, NotUsed2
);
5104 return WRC_Continue
;
5108 ** No-op routine for the parse-tree walker for SELECT statements.
5109 ** subquery in the parser tree.
5111 int sqlite3SelectWalkNoop(Walker
*NotUsed
, Select
*NotUsed2
){
5112 UNUSED_PARAMETER2(NotUsed
, NotUsed2
);
5113 return WRC_Continue
;
5118 ** Always assert. This xSelectCallback2 implementation proves that the
5119 ** xSelectCallback2 is never invoked.
5121 void sqlite3SelectWalkAssert2(Walker
*NotUsed
, Select
*NotUsed2
){
5122 UNUSED_PARAMETER2(NotUsed
, NotUsed2
);
5127 ** This routine "expands" a SELECT statement and all of its subqueries.
5128 ** For additional information on what it means to "expand" a SELECT
5129 ** statement, see the comment on the selectExpand worker callback above.
5131 ** Expanding a SELECT statement is the first step in processing a
5132 ** SELECT statement. The SELECT statement must be expanded before
5133 ** name resolution is performed.
5135 ** If anything goes wrong, an error message is written into pParse.
5136 ** The calling function can detect the problem by looking at pParse->nErr
5137 ** and/or pParse->db->mallocFailed.
5139 static void sqlite3SelectExpand(Parse
*pParse
, Select
*pSelect
){
5141 w
.xExprCallback
= sqlite3ExprWalkNoop
;
5143 if( OK_IF_ALWAYS_TRUE(pParse
->hasCompound
) ){
5144 w
.xSelectCallback
= convertCompoundSelectToSubquery
;
5145 w
.xSelectCallback2
= 0;
5146 sqlite3WalkSelect(&w
, pSelect
);
5148 w
.xSelectCallback
= selectExpander
;
5149 w
.xSelectCallback2
= selectPopWith
;
5150 sqlite3WalkSelect(&w
, pSelect
);
5154 #ifndef SQLITE_OMIT_SUBQUERY
5156 ** This is a Walker.xSelectCallback callback for the sqlite3SelectTypeInfo()
5159 ** For each FROM-clause subquery, add Column.zType and Column.zColl
5160 ** information to the Table structure that represents the result set
5161 ** of that subquery.
5163 ** The Table structure that represents the result set was constructed
5164 ** by selectExpander() but the type and collation information was omitted
5165 ** at that point because identifiers had not yet been resolved. This
5166 ** routine is called after identifier resolution.
5168 static void selectAddSubqueryTypeInfo(Walker
*pWalker
, Select
*p
){
5172 struct SrcList_item
*pFrom
;
5174 assert( p
->selFlags
& SF_Resolved
);
5175 if( p
->selFlags
& SF_HasTypeInfo
) return;
5176 p
->selFlags
|= SF_HasTypeInfo
;
5177 pParse
= pWalker
->pParse
;
5179 for(i
=0, pFrom
=pTabList
->a
; i
<pTabList
->nSrc
; i
++, pFrom
++){
5180 Table
*pTab
= pFrom
->pTab
;
5182 if( (pTab
->tabFlags
& TF_Ephemeral
)!=0 ){
5183 /* A sub-query in the FROM clause of a SELECT */
5184 Select
*pSel
= pFrom
->pSelect
;
5186 while( pSel
->pPrior
) pSel
= pSel
->pPrior
;
5187 sqlite3SelectAddColumnTypeAndCollation(pParse
, pTab
, pSel
);
5196 ** This routine adds datatype and collating sequence information to
5197 ** the Table structures of all FROM-clause subqueries in a
5198 ** SELECT statement.
5200 ** Use this routine after name resolution.
5202 static void sqlite3SelectAddTypeInfo(Parse
*pParse
, Select
*pSelect
){
5203 #ifndef SQLITE_OMIT_SUBQUERY
5205 w
.xSelectCallback
= sqlite3SelectWalkNoop
;
5206 w
.xSelectCallback2
= selectAddSubqueryTypeInfo
;
5207 w
.xExprCallback
= sqlite3ExprWalkNoop
;
5209 sqlite3WalkSelect(&w
, pSelect
);
5215 ** This routine sets up a SELECT statement for processing. The
5216 ** following is accomplished:
5218 ** * VDBE Cursor numbers are assigned to all FROM-clause terms.
5219 ** * Ephemeral Table objects are created for all FROM-clause subqueries.
5220 ** * ON and USING clauses are shifted into WHERE statements
5221 ** * Wildcards "*" and "TABLE.*" in result sets are expanded.
5222 ** * Identifiers in expression are matched to tables.
5224 ** This routine acts recursively on all subqueries within the SELECT.
5226 void sqlite3SelectPrep(
5227 Parse
*pParse
, /* The parser context */
5228 Select
*p
, /* The SELECT statement being coded. */
5229 NameContext
*pOuterNC
/* Name context for container */
5231 assert( p
!=0 || pParse
->db
->mallocFailed
);
5232 if( pParse
->db
->mallocFailed
) return;
5233 if( p
->selFlags
& SF_HasTypeInfo
) return;
5234 sqlite3SelectExpand(pParse
, p
);
5235 if( pParse
->nErr
|| pParse
->db
->mallocFailed
) return;
5236 sqlite3ResolveSelectNames(pParse
, p
, pOuterNC
);
5237 if( pParse
->nErr
|| pParse
->db
->mallocFailed
) return;
5238 sqlite3SelectAddTypeInfo(pParse
, p
);
5242 ** Reset the aggregate accumulator.
5244 ** The aggregate accumulator is a set of memory cells that hold
5245 ** intermediate results while calculating an aggregate. This
5246 ** routine generates code that stores NULLs in all of those memory
5249 static void resetAccumulator(Parse
*pParse
, AggInfo
*pAggInfo
){
5250 Vdbe
*v
= pParse
->pVdbe
;
5252 struct AggInfo_func
*pFunc
;
5253 int nReg
= pAggInfo
->nFunc
+ pAggInfo
->nColumn
;
5254 if( nReg
==0 ) return;
5256 /* Verify that all AggInfo registers are within the range specified by
5257 ** AggInfo.mnReg..AggInfo.mxReg */
5258 assert( nReg
==pAggInfo
->mxReg
-pAggInfo
->mnReg
+1 );
5259 for(i
=0; i
<pAggInfo
->nColumn
; i
++){
5260 assert( pAggInfo
->aCol
[i
].iMem
>=pAggInfo
->mnReg
5261 && pAggInfo
->aCol
[i
].iMem
<=pAggInfo
->mxReg
);
5263 for(i
=0; i
<pAggInfo
->nFunc
; i
++){
5264 assert( pAggInfo
->aFunc
[i
].iMem
>=pAggInfo
->mnReg
5265 && pAggInfo
->aFunc
[i
].iMem
<=pAggInfo
->mxReg
);
5268 sqlite3VdbeAddOp3(v
, OP_Null
, 0, pAggInfo
->mnReg
, pAggInfo
->mxReg
);
5269 for(pFunc
=pAggInfo
->aFunc
, i
=0; i
<pAggInfo
->nFunc
; i
++, pFunc
++){
5270 if( pFunc
->iDistinct
>=0 ){
5271 Expr
*pE
= pFunc
->pExpr
;
5272 assert( !ExprHasProperty(pE
, EP_xIsSelect
) );
5273 if( pE
->x
.pList
==0 || pE
->x
.pList
->nExpr
!=1 ){
5274 sqlite3ErrorMsg(pParse
, "DISTINCT aggregates must have exactly one "
5276 pFunc
->iDistinct
= -1;
5278 KeyInfo
*pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
, pE
->x
.pList
,0,0);
5279 sqlite3VdbeAddOp4(v
, OP_OpenEphemeral
, pFunc
->iDistinct
, 0, 0,
5280 (char*)pKeyInfo
, P4_KEYINFO
);
5287 ** Invoke the OP_AggFinalize opcode for every aggregate function
5288 ** in the AggInfo structure.
5290 static void finalizeAggFunctions(Parse
*pParse
, AggInfo
*pAggInfo
){
5291 Vdbe
*v
= pParse
->pVdbe
;
5293 struct AggInfo_func
*pF
;
5294 for(i
=0, pF
=pAggInfo
->aFunc
; i
<pAggInfo
->nFunc
; i
++, pF
++){
5295 ExprList
*pList
= pF
->pExpr
->x
.pList
;
5296 assert( !ExprHasProperty(pF
->pExpr
, EP_xIsSelect
) );
5297 sqlite3VdbeAddOp2(v
, OP_AggFinal
, pF
->iMem
, pList
? pList
->nExpr
: 0);
5298 sqlite3VdbeAppendP4(v
, pF
->pFunc
, P4_FUNCDEF
);
5304 ** Update the accumulator memory cells for an aggregate based on
5305 ** the current cursor position.
5307 ** If regAcc is non-zero and there are no min() or max() aggregates
5308 ** in pAggInfo, then only populate the pAggInfo->nAccumulator accumulator
5309 ** registers i register regAcc contains 0. The caller will take care
5310 ** of setting and clearing regAcc.
5312 static void updateAccumulator(Parse
*pParse
, int regAcc
, AggInfo
*pAggInfo
){
5313 Vdbe
*v
= pParse
->pVdbe
;
5316 int addrHitTest
= 0;
5317 struct AggInfo_func
*pF
;
5318 struct AggInfo_col
*pC
;
5320 pAggInfo
->directMode
= 1;
5321 for(i
=0, pF
=pAggInfo
->aFunc
; i
<pAggInfo
->nFunc
; i
++, pF
++){
5325 ExprList
*pList
= pF
->pExpr
->x
.pList
;
5326 assert( !ExprHasProperty(pF
->pExpr
, EP_xIsSelect
) );
5328 nArg
= pList
->nExpr
;
5329 regAgg
= sqlite3GetTempRange(pParse
, nArg
);
5330 sqlite3ExprCodeExprList(pParse
, pList
, regAgg
, 0, SQLITE_ECEL_DUP
);
5335 if( pF
->iDistinct
>=0 ){
5336 addrNext
= sqlite3VdbeMakeLabel(pParse
);
5337 testcase( nArg
==0 ); /* Error condition */
5338 testcase( nArg
>1 ); /* Also an error */
5339 codeDistinct(pParse
, pF
->iDistinct
, addrNext
, 1, regAgg
);
5341 if( pF
->pFunc
->funcFlags
& SQLITE_FUNC_NEEDCOLL
){
5343 struct ExprList_item
*pItem
;
5345 assert( pList
!=0 ); /* pList!=0 if pF->pFunc has NEEDCOLL */
5346 for(j
=0, pItem
=pList
->a
; !pColl
&& j
<nArg
; j
++, pItem
++){
5347 pColl
= sqlite3ExprCollSeq(pParse
, pItem
->pExpr
);
5350 pColl
= pParse
->db
->pDfltColl
;
5352 if( regHit
==0 && pAggInfo
->nAccumulator
) regHit
= ++pParse
->nMem
;
5353 sqlite3VdbeAddOp4(v
, OP_CollSeq
, regHit
, 0, 0, (char *)pColl
, P4_COLLSEQ
);
5355 sqlite3VdbeAddOp3(v
, OP_AggStep
, 0, regAgg
, pF
->iMem
);
5356 sqlite3VdbeAppendP4(v
, pF
->pFunc
, P4_FUNCDEF
);
5357 sqlite3VdbeChangeP5(v
, (u8
)nArg
);
5358 sqlite3ReleaseTempRange(pParse
, regAgg
, nArg
);
5360 sqlite3VdbeResolveLabel(v
, addrNext
);
5363 if( regHit
==0 && pAggInfo
->nAccumulator
){
5367 addrHitTest
= sqlite3VdbeAddOp1(v
, OP_If
, regHit
); VdbeCoverage(v
);
5369 for(i
=0, pC
=pAggInfo
->aCol
; i
<pAggInfo
->nAccumulator
; i
++, pC
++){
5370 sqlite3ExprCode(pParse
, pC
->pExpr
, pC
->iMem
);
5372 pAggInfo
->directMode
= 0;
5374 sqlite3VdbeJumpHere(v
, addrHitTest
);
5379 ** Add a single OP_Explain instruction to the VDBE to explain a simple
5380 ** count(*) query ("SELECT count(*) FROM pTab").
5382 #ifndef SQLITE_OMIT_EXPLAIN
5383 static void explainSimpleCount(
5384 Parse
*pParse
, /* Parse context */
5385 Table
*pTab
, /* Table being queried */
5386 Index
*pIdx
/* Index used to optimize scan, or NULL */
5388 if( pParse
->explain
==2 ){
5389 int bCover
= (pIdx
!=0 && (HasRowid(pTab
) || !IsPrimaryKeyIndex(pIdx
)));
5390 sqlite3VdbeExplain(pParse
, 0, "SCAN TABLE %s%s%s",
5392 bCover
? " USING COVERING INDEX " : "",
5393 bCover
? pIdx
->zName
: ""
5398 # define explainSimpleCount(a,b,c)
5402 ** sqlite3WalkExpr() callback used by havingToWhere().
5404 ** If the node passed to the callback is a TK_AND node, return
5405 ** WRC_Continue to tell sqlite3WalkExpr() to iterate through child nodes.
5407 ** Otherwise, return WRC_Prune. In this case, also check if the
5408 ** sub-expression matches the criteria for being moved to the WHERE
5409 ** clause. If so, add it to the WHERE clause and replace the sub-expression
5410 ** within the HAVING expression with a constant "1".
5412 static int havingToWhereExprCb(Walker
*pWalker
, Expr
*pExpr
){
5413 if( pExpr
->op
!=TK_AND
){
5414 Select
*pS
= pWalker
->u
.pSelect
;
5415 if( sqlite3ExprIsConstantOrGroupBy(pWalker
->pParse
, pExpr
, pS
->pGroupBy
) ){
5416 sqlite3
*db
= pWalker
->pParse
->db
;
5417 Expr
*pNew
= sqlite3ExprAlloc(db
, TK_INTEGER
, &sqlite3IntTokens
[1], 0);
5419 Expr
*pWhere
= pS
->pWhere
;
5420 SWAP(Expr
, *pNew
, *pExpr
);
5421 pNew
= sqlite3ExprAnd(db
, pWhere
, pNew
);
5428 return WRC_Continue
;
5432 ** Transfer eligible terms from the HAVING clause of a query, which is
5433 ** processed after grouping, to the WHERE clause, which is processed before
5434 ** grouping. For example, the query:
5436 ** SELECT * FROM <tables> WHERE a=? GROUP BY b HAVING b=? AND c=?
5438 ** can be rewritten as:
5440 ** SELECT * FROM <tables> WHERE a=? AND b=? GROUP BY b HAVING c=?
5442 ** A term of the HAVING expression is eligible for transfer if it consists
5443 ** entirely of constants and expressions that are also GROUP BY terms that
5444 ** use the "BINARY" collation sequence.
5446 static void havingToWhere(Parse
*pParse
, Select
*p
){
5448 memset(&sWalker
, 0, sizeof(sWalker
));
5449 sWalker
.pParse
= pParse
;
5450 sWalker
.xExprCallback
= havingToWhereExprCb
;
5451 sWalker
.u
.pSelect
= p
;
5452 sqlite3WalkExpr(&sWalker
, p
->pHaving
);
5453 #if SELECTTRACE_ENABLED
5454 if( sWalker
.eCode
&& (sqlite3SelectTrace
& 0x100)!=0 ){
5455 SELECTTRACE(0x100,pParse
,p
,("Move HAVING terms into WHERE:\n"));
5456 sqlite3TreeViewSelect(0, p
, 0);
5462 ** Check to see if the pThis entry of pTabList is a self-join of a prior view.
5463 ** If it is, then return the SrcList_item for the prior view. If it is not,
5466 static struct SrcList_item
*isSelfJoinView(
5467 SrcList
*pTabList
, /* Search for self-joins in this FROM clause */
5468 struct SrcList_item
*pThis
/* Search for prior reference to this subquery */
5470 struct SrcList_item
*pItem
;
5471 for(pItem
= pTabList
->a
; pItem
<pThis
; pItem
++){
5473 if( pItem
->pSelect
==0 ) continue;
5474 if( pItem
->fg
.viaCoroutine
) continue;
5475 if( pItem
->zName
==0 ) continue;
5476 if( sqlite3_stricmp(pItem
->zDatabase
, pThis
->zDatabase
)!=0 ) continue;
5477 if( sqlite3_stricmp(pItem
->zName
, pThis
->zName
)!=0 ) continue;
5478 pS1
= pItem
->pSelect
;
5479 if( pThis
->pSelect
->selId
!=pS1
->selId
){
5480 /* The query flattener left two different CTE tables with identical
5481 ** names in the same FROM clause. */
5484 if( sqlite3ExprCompare(0, pThis
->pSelect
->pWhere
, pS1
->pWhere
, -1) ){
5485 /* The view was modified by some other optimization such as
5486 ** pushDownWhereTerms() */
5494 #ifdef SQLITE_COUNTOFVIEW_OPTIMIZATION
5496 ** Attempt to transform a query of the form
5498 ** SELECT count(*) FROM (SELECT x FROM t1 UNION ALL SELECT y FROM t2)
5502 ** SELECT (SELECT count(*) FROM t1)+(SELECT count(*) FROM t2)
5504 ** The transformation only works if all of the following are true:
5506 ** * The subquery is a UNION ALL of two or more terms
5507 ** * The subquery does not have a LIMIT clause
5508 ** * There is no WHERE or GROUP BY or HAVING clauses on the subqueries
5509 ** * The outer query is a simple count(*)
5511 ** Return TRUE if the optimization is undertaken.
5513 static int countOfViewOptimization(Parse
*pParse
, Select
*p
){
5514 Select
*pSub
, *pPrior
;
5518 if( (p
->selFlags
& SF_Aggregate
)==0 ) return 0; /* This is an aggregate */
5519 if( p
->pEList
->nExpr
!=1 ) return 0; /* Single result column */
5520 pExpr
= p
->pEList
->a
[0].pExpr
;
5521 if( pExpr
->op
!=TK_AGG_FUNCTION
) return 0; /* Result is an aggregate */
5522 if( sqlite3_stricmp(pExpr
->u
.zToken
,"count") ) return 0; /* Is count() */
5523 if( pExpr
->x
.pList
!=0 ) return 0; /* Must be count(*) */
5524 if( p
->pSrc
->nSrc
!=1 ) return 0; /* One table in FROM */
5525 pSub
= p
->pSrc
->a
[0].pSelect
;
5526 if( pSub
==0 ) return 0; /* The FROM is a subquery */
5527 if( pSub
->pPrior
==0 ) return 0; /* Must be a compound ry */
5529 if( pSub
->op
!=TK_ALL
&& pSub
->pPrior
) return 0; /* Must be UNION ALL */
5530 if( pSub
->pWhere
) return 0; /* No WHERE clause */
5531 if( pSub
->pLimit
) return 0; /* No LIMIT clause */
5532 if( pSub
->selFlags
& SF_Aggregate
) return 0; /* Not an aggregate */
5533 pSub
= pSub
->pPrior
; /* Repeat over compound */
5536 /* If we reach this point then it is OK to perform the transformation */
5541 pSub
= p
->pSrc
->a
[0].pSelect
;
5542 p
->pSrc
->a
[0].pSelect
= 0;
5543 sqlite3SrcListDelete(db
, p
->pSrc
);
5544 p
->pSrc
= sqlite3DbMallocZero(pParse
->db
, sizeof(*p
->pSrc
));
5547 pPrior
= pSub
->pPrior
;
5550 pSub
->selFlags
|= SF_Aggregate
;
5551 pSub
->selFlags
&= ~SF_Compound
;
5552 pSub
->nSelectRow
= 0;
5553 sqlite3ExprListDelete(db
, pSub
->pEList
);
5554 pTerm
= pPrior
? sqlite3ExprDup(db
, pCount
, 0) : pCount
;
5555 pSub
->pEList
= sqlite3ExprListAppend(pParse
, 0, pTerm
);
5556 pTerm
= sqlite3PExpr(pParse
, TK_SELECT
, 0, 0);
5557 sqlite3PExprAddSelect(pParse
, pTerm
, pSub
);
5561 pExpr
= sqlite3PExpr(pParse
, TK_PLUS
, pTerm
, pExpr
);
5565 p
->pEList
->a
[0].pExpr
= pExpr
;
5566 p
->selFlags
&= ~SF_Aggregate
;
5568 #if SELECTTRACE_ENABLED
5569 if( sqlite3SelectTrace
& 0x400 ){
5570 SELECTTRACE(0x400,pParse
,p
,("After count-of-view optimization:\n"));
5571 sqlite3TreeViewSelect(0, p
, 0);
5576 #endif /* SQLITE_COUNTOFVIEW_OPTIMIZATION */
5579 ** Generate code for the SELECT statement given in the p argument.
5581 ** The results are returned according to the SelectDest structure.
5582 ** See comments in sqliteInt.h for further information.
5584 ** This routine returns the number of errors. If any errors are
5585 ** encountered, then an appropriate error message is left in
5588 ** This routine does NOT free the Select structure passed in. The
5589 ** calling function needs to do that.
5592 Parse
*pParse
, /* The parser context */
5593 Select
*p
, /* The SELECT statement being coded. */
5594 SelectDest
*pDest
/* What to do with the query results */
5596 int i
, j
; /* Loop counters */
5597 WhereInfo
*pWInfo
; /* Return from sqlite3WhereBegin() */
5598 Vdbe
*v
; /* The virtual machine under construction */
5599 int isAgg
; /* True for select lists like "count(*)" */
5600 ExprList
*pEList
= 0; /* List of columns to extract. */
5601 SrcList
*pTabList
; /* List of tables to select from */
5602 Expr
*pWhere
; /* The WHERE clause. May be NULL */
5603 ExprList
*pGroupBy
; /* The GROUP BY clause. May be NULL */
5604 Expr
*pHaving
; /* The HAVING clause. May be NULL */
5605 int rc
= 1; /* Value to return from this function */
5606 DistinctCtx sDistinct
; /* Info on how to code the DISTINCT keyword */
5607 SortCtx sSort
; /* Info on how to code the ORDER BY clause */
5608 AggInfo sAggInfo
; /* Information used by aggregate queries */
5609 int iEnd
; /* Address of the end of the query */
5610 sqlite3
*db
; /* The database connection */
5611 ExprList
*pMinMaxOrderBy
= 0; /* Added ORDER BY for min/max queries */
5612 u8 minMaxFlag
; /* Flag for min/max queries */
5615 v
= sqlite3GetVdbe(pParse
);
5616 if( p
==0 || db
->mallocFailed
|| pParse
->nErr
){
5619 if( sqlite3AuthCheck(pParse
, SQLITE_SELECT
, 0, 0, 0) ) return 1;
5620 memset(&sAggInfo
, 0, sizeof(sAggInfo
));
5621 #if SELECTTRACE_ENABLED
5622 SELECTTRACE(1,pParse
,p
, ("begin processing:\n", pParse
->addrExplain
));
5623 if( sqlite3SelectTrace
& 0x100 ){
5624 sqlite3TreeViewSelect(0, p
, 0);
5628 assert( p
->pOrderBy
==0 || pDest
->eDest
!=SRT_DistFifo
);
5629 assert( p
->pOrderBy
==0 || pDest
->eDest
!=SRT_Fifo
);
5630 assert( p
->pOrderBy
==0 || pDest
->eDest
!=SRT_DistQueue
);
5631 assert( p
->pOrderBy
==0 || pDest
->eDest
!=SRT_Queue
);
5632 if( IgnorableOrderby(pDest
) ){
5633 assert(pDest
->eDest
==SRT_Exists
|| pDest
->eDest
==SRT_Union
||
5634 pDest
->eDest
==SRT_Except
|| pDest
->eDest
==SRT_Discard
||
5635 pDest
->eDest
==SRT_Queue
|| pDest
->eDest
==SRT_DistFifo
||
5636 pDest
->eDest
==SRT_DistQueue
|| pDest
->eDest
==SRT_Fifo
);
5637 /* If ORDER BY makes no difference in the output then neither does
5638 ** DISTINCT so it can be removed too. */
5639 sqlite3ExprListDelete(db
, p
->pOrderBy
);
5641 p
->selFlags
&= ~SF_Distinct
;
5643 sqlite3SelectPrep(pParse
, p
, 0);
5644 if( pParse
->nErr
|| db
->mallocFailed
){
5647 assert( p
->pEList
!=0 );
5648 #if SELECTTRACE_ENABLED
5649 if( sqlite3SelectTrace
& 0x104 ){
5650 SELECTTRACE(0x104,pParse
,p
, ("after name resolution:\n"));
5651 sqlite3TreeViewSelect(0, p
, 0);
5655 if( pDest
->eDest
==SRT_Output
){
5656 generateColumnNames(pParse
, p
);
5659 #ifndef SQLITE_OMIT_WINDOWFUNC
5660 if( sqlite3WindowRewrite(pParse
, p
) ){
5663 #if SELECTTRACE_ENABLED
5664 if( sqlite3SelectTrace
& 0x108 ){
5665 SELECTTRACE(0x104,pParse
,p
, ("after window rewrite:\n"));
5666 sqlite3TreeViewSelect(0, p
, 0);
5669 #endif /* SQLITE_OMIT_WINDOWFUNC */
5671 isAgg
= (p
->selFlags
& SF_Aggregate
)!=0;
5672 memset(&sSort
, 0, sizeof(sSort
));
5673 sSort
.pOrderBy
= p
->pOrderBy
;
5675 /* Try to various optimizations (flattening subqueries, and strength
5676 ** reduction of join operators) in the FROM clause up into the main query
5678 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
5679 for(i
=0; !p
->pPrior
&& i
<pTabList
->nSrc
; i
++){
5680 struct SrcList_item
*pItem
= &pTabList
->a
[i
];
5681 Select
*pSub
= pItem
->pSelect
;
5682 Table
*pTab
= pItem
->pTab
;
5684 /* Convert LEFT JOIN into JOIN if there are terms of the right table
5685 ** of the LEFT JOIN used in the WHERE clause.
5687 if( (pItem
->fg
.jointype
& JT_LEFT
)!=0
5688 && sqlite3ExprImpliesNonNullRow(p
->pWhere
, pItem
->iCursor
)
5689 && OptimizationEnabled(db
, SQLITE_SimplifyJoin
)
5691 SELECTTRACE(0x100,pParse
,p
,
5692 ("LEFT-JOIN simplifies to JOIN on term %d\n",i
));
5693 pItem
->fg
.jointype
&= ~(JT_LEFT
|JT_OUTER
);
5694 unsetJoinExpr(p
->pWhere
, pItem
->iCursor
);
5697 /* No futher action if this term of the FROM clause is no a subquery */
5698 if( pSub
==0 ) continue;
5700 /* Catch mismatch in the declared columns of a view and the number of
5701 ** columns in the SELECT on the RHS */
5702 if( pTab
->nCol
!=pSub
->pEList
->nExpr
){
5703 sqlite3ErrorMsg(pParse
, "expected %d columns for '%s' but got %d",
5704 pTab
->nCol
, pTab
->zName
, pSub
->pEList
->nExpr
);
5708 /* Do not try to flatten an aggregate subquery.
5710 ** Flattening an aggregate subquery is only possible if the outer query
5711 ** is not a join. But if the outer query is not a join, then the subquery
5712 ** will be implemented as a co-routine and there is no advantage to
5713 ** flattening in that case.
5715 if( (pSub
->selFlags
& SF_Aggregate
)!=0 ) continue;
5716 assert( pSub
->pGroupBy
==0 );
5718 /* If the outer query contains a "complex" result set (that is,
5719 ** if the result set of the outer query uses functions or subqueries)
5720 ** and if the subquery contains an ORDER BY clause and if
5721 ** it will be implemented as a co-routine, then do not flatten. This
5722 ** restriction allows SQL constructs like this:
5724 ** SELECT expensive_function(x)
5725 ** FROM (SELECT x FROM tab ORDER BY y LIMIT 10);
5727 ** The expensive_function() is only computed on the 10 rows that
5728 ** are output, rather than every row of the table.
5730 ** The requirement that the outer query have a complex result set
5731 ** means that flattening does occur on simpler SQL constraints without
5732 ** the expensive_function() like:
5734 ** SELECT x FROM (SELECT x FROM tab ORDER BY y LIMIT 10);
5736 if( pSub
->pOrderBy
!=0
5738 && (p
->selFlags
& SF_ComplexResult
)!=0
5739 && (pTabList
->nSrc
==1
5740 || (pTabList
->a
[1].fg
.jointype
&(JT_LEFT
|JT_CROSS
))!=0)
5745 if( flattenSubquery(pParse
, p
, i
, isAgg
) ){
5746 if( pParse
->nErr
) goto select_end
;
5747 /* This subquery can be absorbed into its parent. */
5751 if( db
->mallocFailed
) goto select_end
;
5752 if( !IgnorableOrderby(pDest
) ){
5753 sSort
.pOrderBy
= p
->pOrderBy
;
5758 #ifndef SQLITE_OMIT_COMPOUND_SELECT
5759 /* Handle compound SELECT statements using the separate multiSelect()
5763 rc
= multiSelect(pParse
, p
, pDest
);
5764 #if SELECTTRACE_ENABLED
5765 SELECTTRACE(0x1,pParse
,p
,("end compound-select processing\n"));
5766 if( (sqlite3SelectTrace
& 0x2000)!=0 && ExplainQueryPlanParent(pParse
)==0 ){
5767 sqlite3TreeViewSelect(0, p
, 0);
5770 if( p
->pNext
==0 ) ExplainQueryPlanPop(pParse
);
5775 /* Do the WHERE-clause constant propagation optimization if this is
5776 ** a join. No need to speed time on this operation for non-join queries
5777 ** as the equivalent optimization will be handled by query planner in
5778 ** sqlite3WhereBegin().
5780 if( pTabList
->nSrc
>1
5781 && OptimizationEnabled(db
, SQLITE_PropagateConst
)
5782 && propagateConstants(pParse
, p
)
5784 #if SELECTTRACE_ENABLED
5785 if( sqlite3SelectTrace
& 0x100 ){
5786 SELECTTRACE(0x100,pParse
,p
,("After constant propagation:\n"));
5787 sqlite3TreeViewSelect(0, p
, 0);
5791 SELECTTRACE(0x100,pParse
,p
,("Constant propagation not helpful\n"));
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 /* For each term in the FROM clause, do two things:
5805 ** (1) Authorized unreferenced tables
5806 ** (2) Generate code for all sub-queries
5808 for(i
=0; i
<pTabList
->nSrc
; i
++){
5809 struct SrcList_item
*pItem
= &pTabList
->a
[i
];
5812 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
5813 const char *zSavedAuthContext
;
5816 /* Issue SQLITE_READ authorizations with a fake column name for any
5817 ** tables that are referenced but from which no values are extracted.
5818 ** Examples of where these kinds of null SQLITE_READ authorizations
5821 ** SELECT count(*) FROM t1; -- SQLITE_READ t1.""
5822 ** SELECT t1.* FROM t1, t2; -- SQLITE_READ t2.""
5824 ** The fake column name is an empty string. It is possible for a table to
5825 ** have a column named by the empty string, in which case there is no way to
5826 ** distinguish between an unreferenced table and an actual reference to the
5827 ** "" column. The original design was for the fake column name to be a NULL,
5828 ** which would be unambiguous. But legacy authorization callbacks might
5829 ** assume the column name is non-NULL and segfault. The use of an empty
5830 ** string for the fake column name seems safer.
5832 if( pItem
->colUsed
==0 ){
5833 sqlite3AuthCheck(pParse
, SQLITE_READ
, pItem
->zName
, "", pItem
->zDatabase
);
5836 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
5837 /* Generate code for all sub-queries in the FROM clause
5839 pSub
= pItem
->pSelect
;
5840 if( pSub
==0 ) continue;
5842 /* The code for a subquery should only be generated once, though it is
5843 ** technically harmless for it to be generated multiple times. The
5844 ** following assert() will detect if something changes to cause
5845 ** the same subquery to be coded multiple times, as a signal to the
5846 ** developers to try to optimize the situation. */
5847 assert( pItem
->addrFillSub
==0 );
5849 /* Increment Parse.nHeight by the height of the largest expression
5850 ** tree referred to by this, the parent select. The child select
5851 ** may contain expression trees of at most
5852 ** (SQLITE_MAX_EXPR_DEPTH-Parse.nHeight) height. This is a bit
5853 ** more conservative than necessary, but much easier than enforcing
5856 pParse
->nHeight
+= sqlite3SelectExprHeight(p
);
5858 /* Make copies of constant WHERE-clause terms in the outer query down
5859 ** inside the subquery. This can help the subquery to run more efficiently.
5861 if( OptimizationEnabled(db
, SQLITE_PushDown
)
5862 && pushDownWhereTerms(pParse
, pSub
, p
->pWhere
, pItem
->iCursor
,
5863 (pItem
->fg
.jointype
& JT_OUTER
)!=0)
5865 #if SELECTTRACE_ENABLED
5866 if( sqlite3SelectTrace
& 0x100 ){
5867 SELECTTRACE(0x100,pParse
,p
,
5868 ("After WHERE-clause push-down into subquery %d:\n", pSub
->selId
));
5869 sqlite3TreeViewSelect(0, p
, 0);
5873 SELECTTRACE(0x100,pParse
,p
,("Push-down not possible\n"));
5876 zSavedAuthContext
= pParse
->zAuthContext
;
5877 pParse
->zAuthContext
= pItem
->zName
;
5879 /* Generate code to implement the subquery
5881 ** The subquery is implemented as a co-routine if the subquery is
5882 ** guaranteed to be the outer loop (so that it does not need to be
5883 ** computed more than once)
5885 ** TODO: Are there other reasons beside (1) to use a co-routine
5889 && (pTabList
->nSrc
==1
5890 || (pTabList
->a
[1].fg
.jointype
&(JT_LEFT
|JT_CROSS
))!=0) /* (1) */
5892 /* Implement a co-routine that will return a single row of the result
5893 ** set on each invocation.
5895 int addrTop
= sqlite3VdbeCurrentAddr(v
)+1;
5897 pItem
->regReturn
= ++pParse
->nMem
;
5898 sqlite3VdbeAddOp3(v
, OP_InitCoroutine
, pItem
->regReturn
, 0, addrTop
);
5899 VdbeComment((v
, "%s", pItem
->pTab
->zName
));
5900 pItem
->addrFillSub
= addrTop
;
5901 sqlite3SelectDestInit(&dest
, SRT_Coroutine
, pItem
->regReturn
);
5902 ExplainQueryPlan((pParse
, 1, "CO-ROUTINE %u", pSub
->selId
));
5903 sqlite3Select(pParse
, pSub
, &dest
);
5904 pItem
->pTab
->nRowLogEst
= pSub
->nSelectRow
;
5905 pItem
->fg
.viaCoroutine
= 1;
5906 pItem
->regResult
= dest
.iSdst
;
5907 sqlite3VdbeEndCoroutine(v
, pItem
->regReturn
);
5908 sqlite3VdbeJumpHere(v
, addrTop
-1);
5909 sqlite3ClearTempRegCache(pParse
);
5911 /* Generate a subroutine that will fill an ephemeral table with
5912 ** the content of this subquery. pItem->addrFillSub will point
5913 ** to the address of the generated subroutine. pItem->regReturn
5914 ** is a register allocated to hold the subroutine return address
5919 struct SrcList_item
*pPrior
;
5921 assert( pItem
->addrFillSub
==0 );
5922 pItem
->regReturn
= ++pParse
->nMem
;
5923 topAddr
= sqlite3VdbeAddOp2(v
, OP_Integer
, 0, pItem
->regReturn
);
5924 pItem
->addrFillSub
= topAddr
+1;
5925 if( pItem
->fg
.isCorrelated
==0 ){
5926 /* If the subquery is not correlated and if we are not inside of
5927 ** a trigger, then we only need to compute the value of the subquery
5929 onceAddr
= sqlite3VdbeAddOp0(v
, OP_Once
); VdbeCoverage(v
);
5930 VdbeComment((v
, "materialize \"%s\"", pItem
->pTab
->zName
));
5932 VdbeNoopComment((v
, "materialize \"%s\"", pItem
->pTab
->zName
));
5934 pPrior
= isSelfJoinView(pTabList
, pItem
);
5936 sqlite3VdbeAddOp2(v
, OP_OpenDup
, pItem
->iCursor
, pPrior
->iCursor
);
5937 assert( pPrior
->pSelect
!=0 );
5938 pSub
->nSelectRow
= pPrior
->pSelect
->nSelectRow
;
5940 sqlite3SelectDestInit(&dest
, SRT_EphemTab
, pItem
->iCursor
);
5941 ExplainQueryPlan((pParse
, 1, "MATERIALIZE %u", pSub
->selId
));
5942 sqlite3Select(pParse
, pSub
, &dest
);
5944 pItem
->pTab
->nRowLogEst
= pSub
->nSelectRow
;
5945 if( onceAddr
) sqlite3VdbeJumpHere(v
, onceAddr
);
5946 retAddr
= sqlite3VdbeAddOp1(v
, OP_Return
, pItem
->regReturn
);
5947 VdbeComment((v
, "end %s", pItem
->pTab
->zName
));
5948 sqlite3VdbeChangeP1(v
, topAddr
, retAddr
);
5949 sqlite3ClearTempRegCache(pParse
);
5951 if( db
->mallocFailed
) goto select_end
;
5952 pParse
->nHeight
-= sqlite3SelectExprHeight(p
);
5953 pParse
->zAuthContext
= zSavedAuthContext
;
5957 /* Various elements of the SELECT copied into local variables for
5961 pGroupBy
= p
->pGroupBy
;
5962 pHaving
= p
->pHaving
;
5963 sDistinct
.isTnct
= (p
->selFlags
& SF_Distinct
)!=0;
5965 #if SELECTTRACE_ENABLED
5966 if( sqlite3SelectTrace
& 0x400 ){
5967 SELECTTRACE(0x400,pParse
,p
,("After all FROM-clause analysis:\n"));
5968 sqlite3TreeViewSelect(0, p
, 0);
5972 /* If the query is DISTINCT with an ORDER BY but is not an aggregate, and
5973 ** if the select-list is the same as the ORDER BY list, then this query
5974 ** can be rewritten as a GROUP BY. In other words, this:
5976 ** SELECT DISTINCT xyz FROM ... ORDER BY xyz
5978 ** is transformed to:
5980 ** SELECT xyz FROM ... GROUP BY xyz ORDER BY xyz
5982 ** The second form is preferred as a single index (or temp-table) may be
5983 ** used for both the ORDER BY and DISTINCT processing. As originally
5984 ** written the query must use a temp-table for at least one of the ORDER
5985 ** BY and DISTINCT, and an index or separate temp-table for the other.
5987 if( (p
->selFlags
& (SF_Distinct
|SF_Aggregate
))==SF_Distinct
5988 && sqlite3ExprListCompare(sSort
.pOrderBy
, pEList
, -1)==0
5990 p
->selFlags
&= ~SF_Distinct
;
5991 pGroupBy
= p
->pGroupBy
= sqlite3ExprListDup(db
, pEList
, 0);
5992 /* Notice that even thought SF_Distinct has been cleared from p->selFlags,
5993 ** the sDistinct.isTnct is still set. Hence, isTnct represents the
5994 ** original setting of the SF_Distinct flag, not the current setting */
5995 assert( sDistinct
.isTnct
);
5997 #if SELECTTRACE_ENABLED
5998 if( sqlite3SelectTrace
& 0x400 ){
5999 SELECTTRACE(0x400,pParse
,p
,("Transform DISTINCT into GROUP BY:\n"));
6000 sqlite3TreeViewSelect(0, p
, 0);
6005 /* If there is an ORDER BY clause, then create an ephemeral index to
6006 ** do the sorting. But this sorting ephemeral index might end up
6007 ** being unused if the data can be extracted in pre-sorted order.
6008 ** If that is the case, then the OP_OpenEphemeral instruction will be
6009 ** changed to an OP_Noop once we figure out that the sorting index is
6010 ** not needed. The sSort.addrSortIndex variable is used to facilitate
6013 if( sSort
.pOrderBy
){
6015 pKeyInfo
= sqlite3KeyInfoFromExprList(
6016 pParse
, sSort
.pOrderBy
, 0, pEList
->nExpr
);
6017 sSort
.iECursor
= pParse
->nTab
++;
6018 sSort
.addrSortIndex
=
6019 sqlite3VdbeAddOp4(v
, OP_OpenEphemeral
,
6020 sSort
.iECursor
, sSort
.pOrderBy
->nExpr
+1+pEList
->nExpr
, 0,
6021 (char*)pKeyInfo
, P4_KEYINFO
6024 sSort
.addrSortIndex
= -1;
6027 /* If the output is destined for a temporary table, open that table.
6029 if( pDest
->eDest
==SRT_EphemTab
){
6030 sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, pDest
->iSDParm
, pEList
->nExpr
);
6035 iEnd
= sqlite3VdbeMakeLabel(pParse
);
6036 if( (p
->selFlags
& SF_FixedLimit
)==0 ){
6037 p
->nSelectRow
= 320; /* 4 billion rows */
6039 computeLimitRegisters(pParse
, p
, iEnd
);
6040 if( p
->iLimit
==0 && sSort
.addrSortIndex
>=0 ){
6041 sqlite3VdbeChangeOpcode(v
, sSort
.addrSortIndex
, OP_SorterOpen
);
6042 sSort
.sortFlags
|= SORTFLAG_UseSorter
;
6045 /* Open an ephemeral index to use for the distinct set.
6047 if( p
->selFlags
& SF_Distinct
){
6048 sDistinct
.tabTnct
= pParse
->nTab
++;
6049 sDistinct
.addrTnct
= sqlite3VdbeAddOp4(v
, OP_OpenEphemeral
,
6050 sDistinct
.tabTnct
, 0, 0,
6051 (char*)sqlite3KeyInfoFromExprList(pParse
, p
->pEList
,0,0),
6053 sqlite3VdbeChangeP5(v
, BTREE_UNORDERED
);
6054 sDistinct
.eTnctType
= WHERE_DISTINCT_UNORDERED
;
6056 sDistinct
.eTnctType
= WHERE_DISTINCT_NOOP
;
6059 if( !isAgg
&& pGroupBy
==0 ){
6060 /* No aggregate functions and no GROUP BY clause */
6061 u16 wctrlFlags
= (sDistinct
.isTnct
? WHERE_WANT_DISTINCT
: 0)
6062 | (p
->selFlags
& SF_FixedLimit
);
6063 #ifndef SQLITE_OMIT_WINDOWFUNC
6064 Window
*pWin
= p
->pWin
; /* Master window object (or NULL) */
6066 sqlite3WindowCodeInit(pParse
, pWin
);
6069 assert( WHERE_USE_LIMIT
==SF_FixedLimit
);
6072 /* Begin the database scan. */
6073 SELECTTRACE(1,pParse
,p
,("WhereBegin\n"));
6074 pWInfo
= sqlite3WhereBegin(pParse
, pTabList
, pWhere
, sSort
.pOrderBy
,
6075 p
->pEList
, wctrlFlags
, p
->nSelectRow
);
6076 if( pWInfo
==0 ) goto select_end
;
6077 if( sqlite3WhereOutputRowCount(pWInfo
) < p
->nSelectRow
){
6078 p
->nSelectRow
= sqlite3WhereOutputRowCount(pWInfo
);
6080 if( sDistinct
.isTnct
&& sqlite3WhereIsDistinct(pWInfo
) ){
6081 sDistinct
.eTnctType
= sqlite3WhereIsDistinct(pWInfo
);
6083 if( sSort
.pOrderBy
){
6084 sSort
.nOBSat
= sqlite3WhereIsOrdered(pWInfo
);
6085 sSort
.labelOBLopt
= sqlite3WhereOrderByLimitOptLabel(pWInfo
);
6086 if( sSort
.nOBSat
==sSort
.pOrderBy
->nExpr
){
6091 /* If sorting index that was created by a prior OP_OpenEphemeral
6092 ** instruction ended up not being needed, then change the OP_OpenEphemeral
6095 if( sSort
.addrSortIndex
>=0 && sSort
.pOrderBy
==0 ){
6096 sqlite3VdbeChangeToNoop(v
, sSort
.addrSortIndex
);
6099 assert( p
->pEList
==pEList
);
6100 #ifndef SQLITE_OMIT_WINDOWFUNC
6102 int addrGosub
= sqlite3VdbeMakeLabel(pParse
);
6103 int iCont
= sqlite3VdbeMakeLabel(pParse
);
6104 int iBreak
= sqlite3VdbeMakeLabel(pParse
);
6105 int regGosub
= ++pParse
->nMem
;
6107 sqlite3WindowCodeStep(pParse
, p
, pWInfo
, regGosub
, addrGosub
);
6109 sqlite3VdbeAddOp2(v
, OP_Goto
, 0, iBreak
);
6110 sqlite3VdbeResolveLabel(v
, addrGosub
);
6111 VdbeNoopComment((v
, "inner-loop subroutine"));
6112 sSort
.labelOBLopt
= 0;
6113 selectInnerLoop(pParse
, p
, -1, &sSort
, &sDistinct
, pDest
, iCont
, iBreak
);
6114 sqlite3VdbeResolveLabel(v
, iCont
);
6115 sqlite3VdbeAddOp1(v
, OP_Return
, regGosub
);
6116 VdbeComment((v
, "end inner-loop subroutine"));
6117 sqlite3VdbeResolveLabel(v
, iBreak
);
6119 #endif /* SQLITE_OMIT_WINDOWFUNC */
6121 /* Use the standard inner loop. */
6122 selectInnerLoop(pParse
, p
, -1, &sSort
, &sDistinct
, pDest
,
6123 sqlite3WhereContinueLabel(pWInfo
),
6124 sqlite3WhereBreakLabel(pWInfo
));
6126 /* End the database scan loop.
6128 sqlite3WhereEnd(pWInfo
);
6131 /* This case when there exist aggregate functions or a GROUP BY clause
6133 NameContext sNC
; /* Name context for processing aggregate information */
6134 int iAMem
; /* First Mem address for storing current GROUP BY */
6135 int iBMem
; /* First Mem address for previous GROUP BY */
6136 int iUseFlag
; /* Mem address holding flag indicating that at least
6137 ** one row of the input to the aggregator has been
6139 int iAbortFlag
; /* Mem address which causes query abort if positive */
6140 int groupBySort
; /* Rows come from source in GROUP BY order */
6141 int addrEnd
; /* End of processing for this SELECT */
6142 int sortPTab
= 0; /* Pseudotable used to decode sorting results */
6143 int sortOut
= 0; /* Output register from the sorter */
6144 int orderByGrp
= 0; /* True if the GROUP BY and ORDER BY are the same */
6146 /* Remove any and all aliases between the result set and the
6150 int k
; /* Loop counter */
6151 struct ExprList_item
*pItem
; /* For looping over expression in a list */
6153 for(k
=p
->pEList
->nExpr
, pItem
=p
->pEList
->a
; k
>0; k
--, pItem
++){
6154 pItem
->u
.x
.iAlias
= 0;
6156 for(k
=pGroupBy
->nExpr
, pItem
=pGroupBy
->a
; k
>0; k
--, pItem
++){
6157 pItem
->u
.x
.iAlias
= 0;
6159 assert( 66==sqlite3LogEst(100) );
6160 if( p
->nSelectRow
>66 ) p
->nSelectRow
= 66;
6162 assert( 0==sqlite3LogEst(1) );
6166 /* If there is both a GROUP BY and an ORDER BY clause and they are
6167 ** identical, then it may be possible to disable the ORDER BY clause
6168 ** on the grounds that the GROUP BY will cause elements to come out
6169 ** in the correct order. It also may not - the GROUP BY might use a
6170 ** database index that causes rows to be grouped together as required
6171 ** but not actually sorted. Either way, record the fact that the
6172 ** ORDER BY and GROUP BY clauses are the same by setting the orderByGrp
6174 if( sqlite3ExprListCompare(pGroupBy
, sSort
.pOrderBy
, -1)==0 ){
6178 /* Create a label to jump to when we want to abort the query */
6179 addrEnd
= sqlite3VdbeMakeLabel(pParse
);
6181 /* Convert TK_COLUMN nodes into TK_AGG_COLUMN and make entries in
6182 ** sAggInfo for all TK_AGG_FUNCTION nodes in expressions of the
6183 ** SELECT statement.
6185 memset(&sNC
, 0, sizeof(sNC
));
6186 sNC
.pParse
= pParse
;
6187 sNC
.pSrcList
= pTabList
;
6188 sNC
.uNC
.pAggInfo
= &sAggInfo
;
6189 VVA_ONLY( sNC
.ncFlags
= NC_UAggInfo
; )
6190 sAggInfo
.mnReg
= pParse
->nMem
+1;
6191 sAggInfo
.nSortingColumn
= pGroupBy
? pGroupBy
->nExpr
: 0;
6192 sAggInfo
.pGroupBy
= pGroupBy
;
6193 sqlite3ExprAnalyzeAggList(&sNC
, pEList
);
6194 sqlite3ExprAnalyzeAggList(&sNC
, sSort
.pOrderBy
);
6197 assert( pWhere
==p
->pWhere
);
6198 assert( pHaving
==p
->pHaving
);
6199 assert( pGroupBy
==p
->pGroupBy
);
6200 havingToWhere(pParse
, p
);
6203 sqlite3ExprAnalyzeAggregates(&sNC
, pHaving
);
6205 sAggInfo
.nAccumulator
= sAggInfo
.nColumn
;
6206 if( p
->pGroupBy
==0 && p
->pHaving
==0 && sAggInfo
.nFunc
==1 ){
6207 minMaxFlag
= minMaxQuery(db
, sAggInfo
.aFunc
[0].pExpr
, &pMinMaxOrderBy
);
6209 minMaxFlag
= WHERE_ORDERBY_NORMAL
;
6211 for(i
=0; i
<sAggInfo
.nFunc
; i
++){
6212 assert( !ExprHasProperty(sAggInfo
.aFunc
[i
].pExpr
, EP_xIsSelect
) );
6213 sNC
.ncFlags
|= NC_InAggFunc
;
6214 sqlite3ExprAnalyzeAggList(&sNC
, sAggInfo
.aFunc
[i
].pExpr
->x
.pList
);
6215 sNC
.ncFlags
&= ~NC_InAggFunc
;
6217 sAggInfo
.mxReg
= pParse
->nMem
;
6218 if( db
->mallocFailed
) goto select_end
;
6219 #if SELECTTRACE_ENABLED
6220 if( sqlite3SelectTrace
& 0x400 ){
6222 SELECTTRACE(0x400,pParse
,p
,("After aggregate analysis:\n"));
6223 sqlite3TreeViewSelect(0, p
, 0);
6224 for(ii
=0; ii
<sAggInfo
.nColumn
; ii
++){
6225 sqlite3DebugPrintf("agg-column[%d] iMem=%d\n",
6226 ii
, sAggInfo
.aCol
[ii
].iMem
);
6227 sqlite3TreeViewExpr(0, sAggInfo
.aCol
[ii
].pExpr
, 0);
6229 for(ii
=0; ii
<sAggInfo
.nFunc
; ii
++){
6230 sqlite3DebugPrintf("agg-func[%d]: iMem=%d\n",
6231 ii
, sAggInfo
.aFunc
[ii
].iMem
);
6232 sqlite3TreeViewExpr(0, sAggInfo
.aFunc
[ii
].pExpr
, 0);
6238 /* Processing for aggregates with GROUP BY is very different and
6239 ** much more complex than aggregates without a GROUP BY.
6242 KeyInfo
*pKeyInfo
; /* Keying information for the group by clause */
6243 int addr1
; /* A-vs-B comparision jump */
6244 int addrOutputRow
; /* Start of subroutine that outputs a result row */
6245 int regOutputRow
; /* Return address register for output subroutine */
6246 int addrSetAbort
; /* Set the abort flag and return */
6247 int addrTopOfLoop
; /* Top of the input loop */
6248 int addrSortingIdx
; /* The OP_OpenEphemeral for the sorting index */
6249 int addrReset
; /* Subroutine for resetting the accumulator */
6250 int regReset
; /* Return address register for reset subroutine */
6252 /* If there is a GROUP BY clause we might need a sorting index to
6253 ** implement it. Allocate that sorting index now. If it turns out
6254 ** that we do not need it after all, the OP_SorterOpen instruction
6255 ** will be converted into a Noop.
6257 sAggInfo
.sortingIdx
= pParse
->nTab
++;
6258 pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
,pGroupBy
,0,sAggInfo
.nColumn
);
6259 addrSortingIdx
= sqlite3VdbeAddOp4(v
, OP_SorterOpen
,
6260 sAggInfo
.sortingIdx
, sAggInfo
.nSortingColumn
,
6261 0, (char*)pKeyInfo
, P4_KEYINFO
);
6263 /* Initialize memory locations used by GROUP BY aggregate processing
6265 iUseFlag
= ++pParse
->nMem
;
6266 iAbortFlag
= ++pParse
->nMem
;
6267 regOutputRow
= ++pParse
->nMem
;
6268 addrOutputRow
= sqlite3VdbeMakeLabel(pParse
);
6269 regReset
= ++pParse
->nMem
;
6270 addrReset
= sqlite3VdbeMakeLabel(pParse
);
6271 iAMem
= pParse
->nMem
+ 1;
6272 pParse
->nMem
+= pGroupBy
->nExpr
;
6273 iBMem
= pParse
->nMem
+ 1;
6274 pParse
->nMem
+= pGroupBy
->nExpr
;
6275 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, iAbortFlag
);
6276 VdbeComment((v
, "clear abort flag"));
6277 sqlite3VdbeAddOp3(v
, OP_Null
, 0, iAMem
, iAMem
+pGroupBy
->nExpr
-1);
6279 /* Begin a loop that will extract all source rows in GROUP BY order.
6280 ** This might involve two separate loops with an OP_Sort in between, or
6281 ** it might be a single loop that uses an index to extract information
6282 ** in the right order to begin with.
6284 sqlite3VdbeAddOp2(v
, OP_Gosub
, regReset
, addrReset
);
6285 SELECTTRACE(1,pParse
,p
,("WhereBegin\n"));
6286 pWInfo
= sqlite3WhereBegin(pParse
, pTabList
, pWhere
, pGroupBy
, 0,
6287 WHERE_GROUPBY
| (orderByGrp
? WHERE_SORTBYGROUP
: 0), 0
6289 if( pWInfo
==0 ) goto select_end
;
6290 if( sqlite3WhereIsOrdered(pWInfo
)==pGroupBy
->nExpr
){
6291 /* The optimizer is able to deliver rows in group by order so
6292 ** we do not have to sort. The OP_OpenEphemeral table will be
6293 ** cancelled later because we still need to use the pKeyInfo
6297 /* Rows are coming out in undetermined order. We have to push
6298 ** each row into a sorting index, terminate the first loop,
6299 ** then loop over the sorting index in order to get the output
6307 explainTempTable(pParse
,
6308 (sDistinct
.isTnct
&& (p
->selFlags
&SF_Distinct
)==0) ?
6309 "DISTINCT" : "GROUP BY");
6312 nGroupBy
= pGroupBy
->nExpr
;
6315 for(i
=0; i
<sAggInfo
.nColumn
; i
++){
6316 if( sAggInfo
.aCol
[i
].iSorterColumn
>=j
){
6321 regBase
= sqlite3GetTempRange(pParse
, nCol
);
6322 sqlite3ExprCodeExprList(pParse
, pGroupBy
, regBase
, 0, 0);
6324 for(i
=0; i
<sAggInfo
.nColumn
; i
++){
6325 struct AggInfo_col
*pCol
= &sAggInfo
.aCol
[i
];
6326 if( pCol
->iSorterColumn
>=j
){
6327 int r1
= j
+ regBase
;
6328 sqlite3ExprCodeGetColumnOfTable(v
,
6329 pCol
->pTab
, pCol
->iTable
, pCol
->iColumn
, r1
);
6333 regRecord
= sqlite3GetTempReg(pParse
);
6334 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, regBase
, nCol
, regRecord
);
6335 sqlite3VdbeAddOp2(v
, OP_SorterInsert
, sAggInfo
.sortingIdx
, regRecord
);
6336 sqlite3ReleaseTempReg(pParse
, regRecord
);
6337 sqlite3ReleaseTempRange(pParse
, regBase
, nCol
);
6338 sqlite3WhereEnd(pWInfo
);
6339 sAggInfo
.sortingIdxPTab
= sortPTab
= pParse
->nTab
++;
6340 sortOut
= sqlite3GetTempReg(pParse
);
6341 sqlite3VdbeAddOp3(v
, OP_OpenPseudo
, sortPTab
, sortOut
, nCol
);
6342 sqlite3VdbeAddOp2(v
, OP_SorterSort
, sAggInfo
.sortingIdx
, addrEnd
);
6343 VdbeComment((v
, "GROUP BY sort")); VdbeCoverage(v
);
6344 sAggInfo
.useSortingIdx
= 1;
6347 /* If the index or temporary table used by the GROUP BY sort
6348 ** will naturally deliver rows in the order required by the ORDER BY
6349 ** clause, cancel the ephemeral table open coded earlier.
6351 ** This is an optimization - the correct answer should result regardless.
6352 ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER to
6353 ** disable this optimization for testing purposes. */
6354 if( orderByGrp
&& OptimizationEnabled(db
, SQLITE_GroupByOrder
)
6355 && (groupBySort
|| sqlite3WhereIsSorted(pWInfo
))
6358 sqlite3VdbeChangeToNoop(v
, sSort
.addrSortIndex
);
6361 /* Evaluate the current GROUP BY terms and store in b0, b1, b2...
6362 ** (b0 is memory location iBMem+0, b1 is iBMem+1, and so forth)
6363 ** Then compare the current GROUP BY terms against the GROUP BY terms
6364 ** from the previous row currently stored in a0, a1, a2...
6366 addrTopOfLoop
= sqlite3VdbeCurrentAddr(v
);
6368 sqlite3VdbeAddOp3(v
, OP_SorterData
, sAggInfo
.sortingIdx
,
6371 for(j
=0; j
<pGroupBy
->nExpr
; j
++){
6373 sqlite3VdbeAddOp3(v
, OP_Column
, sortPTab
, j
, iBMem
+j
);
6375 sAggInfo
.directMode
= 1;
6376 sqlite3ExprCode(pParse
, pGroupBy
->a
[j
].pExpr
, iBMem
+j
);
6379 sqlite3VdbeAddOp4(v
, OP_Compare
, iAMem
, iBMem
, pGroupBy
->nExpr
,
6380 (char*)sqlite3KeyInfoRef(pKeyInfo
), P4_KEYINFO
);
6381 addr1
= sqlite3VdbeCurrentAddr(v
);
6382 sqlite3VdbeAddOp3(v
, OP_Jump
, addr1
+1, 0, addr1
+1); VdbeCoverage(v
);
6384 /* Generate code that runs whenever the GROUP BY changes.
6385 ** Changes in the GROUP BY are detected by the previous code
6386 ** block. If there were no changes, this block is skipped.
6388 ** This code copies current group by terms in b0,b1,b2,...
6389 ** over to a0,a1,a2. It then calls the output subroutine
6390 ** and resets the aggregate accumulator registers in preparation
6391 ** for the next GROUP BY batch.
6393 sqlite3ExprCodeMove(pParse
, iBMem
, iAMem
, pGroupBy
->nExpr
);
6394 sqlite3VdbeAddOp2(v
, OP_Gosub
, regOutputRow
, addrOutputRow
);
6395 VdbeComment((v
, "output one row"));
6396 sqlite3VdbeAddOp2(v
, OP_IfPos
, iAbortFlag
, addrEnd
); VdbeCoverage(v
);
6397 VdbeComment((v
, "check abort flag"));
6398 sqlite3VdbeAddOp2(v
, OP_Gosub
, regReset
, addrReset
);
6399 VdbeComment((v
, "reset accumulator"));
6401 /* Update the aggregate accumulators based on the content of
6404 sqlite3VdbeJumpHere(v
, addr1
);
6405 updateAccumulator(pParse
, iUseFlag
, &sAggInfo
);
6406 sqlite3VdbeAddOp2(v
, OP_Integer
, 1, iUseFlag
);
6407 VdbeComment((v
, "indicate data in accumulator"));
6412 sqlite3VdbeAddOp2(v
, OP_SorterNext
, sAggInfo
.sortingIdx
, addrTopOfLoop
);
6415 sqlite3WhereEnd(pWInfo
);
6416 sqlite3VdbeChangeToNoop(v
, addrSortingIdx
);
6419 /* Output the final row of result
6421 sqlite3VdbeAddOp2(v
, OP_Gosub
, regOutputRow
, addrOutputRow
);
6422 VdbeComment((v
, "output final row"));
6424 /* Jump over the subroutines
6426 sqlite3VdbeGoto(v
, addrEnd
);
6428 /* Generate a subroutine that outputs a single row of the result
6429 ** set. This subroutine first looks at the iUseFlag. If iUseFlag
6430 ** is less than or equal to zero, the subroutine is a no-op. If
6431 ** the processing calls for the query to abort, this subroutine
6432 ** increments the iAbortFlag memory location before returning in
6433 ** order to signal the caller to abort.
6435 addrSetAbort
= sqlite3VdbeCurrentAddr(v
);
6436 sqlite3VdbeAddOp2(v
, OP_Integer
, 1, iAbortFlag
);
6437 VdbeComment((v
, "set abort flag"));
6438 sqlite3VdbeAddOp1(v
, OP_Return
, regOutputRow
);
6439 sqlite3VdbeResolveLabel(v
, addrOutputRow
);
6440 addrOutputRow
= sqlite3VdbeCurrentAddr(v
);
6441 sqlite3VdbeAddOp2(v
, OP_IfPos
, iUseFlag
, addrOutputRow
+2);
6443 VdbeComment((v
, "Groupby result generator entry point"));
6444 sqlite3VdbeAddOp1(v
, OP_Return
, regOutputRow
);
6445 finalizeAggFunctions(pParse
, &sAggInfo
);
6446 sqlite3ExprIfFalse(pParse
, pHaving
, addrOutputRow
+1, SQLITE_JUMPIFNULL
);
6447 selectInnerLoop(pParse
, p
, -1, &sSort
,
6449 addrOutputRow
+1, addrSetAbort
);
6450 sqlite3VdbeAddOp1(v
, OP_Return
, regOutputRow
);
6451 VdbeComment((v
, "end groupby result generator"));
6453 /* Generate a subroutine that will reset the group-by accumulator
6455 sqlite3VdbeResolveLabel(v
, addrReset
);
6456 resetAccumulator(pParse
, &sAggInfo
);
6457 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, iUseFlag
);
6458 VdbeComment((v
, "indicate accumulator empty"));
6459 sqlite3VdbeAddOp1(v
, OP_Return
, regReset
);
6461 } /* endif pGroupBy. Begin aggregate queries without GROUP BY: */
6463 #ifndef SQLITE_OMIT_BTREECOUNT
6465 if( (pTab
= isSimpleCount(p
, &sAggInfo
))!=0 ){
6466 /* If isSimpleCount() returns a pointer to a Table structure, then
6467 ** the SQL statement is of the form:
6469 ** SELECT count(*) FROM <tbl>
6471 ** where the Table structure returned represents table <tbl>.
6473 ** This statement is so common that it is optimized specially. The
6474 ** OP_Count instruction is executed either on the intkey table that
6475 ** contains the data for table <tbl> or on one of its indexes. It
6476 ** is better to execute the op on an index, as indexes are almost
6477 ** always spread across less pages than their corresponding tables.
6479 const int iDb
= sqlite3SchemaToIndex(pParse
->db
, pTab
->pSchema
);
6480 const int iCsr
= pParse
->nTab
++; /* Cursor to scan b-tree */
6481 Index
*pIdx
; /* Iterator variable */
6482 KeyInfo
*pKeyInfo
= 0; /* Keyinfo for scanned index */
6483 Index
*pBest
= 0; /* Best index found so far */
6484 int iRoot
= pTab
->tnum
; /* Root page of scanned b-tree */
6486 sqlite3CodeVerifySchema(pParse
, iDb
);
6487 sqlite3TableLock(pParse
, iDb
, pTab
->tnum
, 0, pTab
->zName
);
6489 /* Search for the index that has the lowest scan cost.
6491 ** (2011-04-15) Do not do a full scan of an unordered index.
6493 ** (2013-10-03) Do not count the entries in a partial index.
6495 ** In practice the KeyInfo structure will not be used. It is only
6496 ** passed to keep OP_OpenRead happy.
6498 if( !HasRowid(pTab
) ) pBest
= sqlite3PrimaryKeyIndex(pTab
);
6499 for(pIdx
=pTab
->pIndex
; pIdx
; pIdx
=pIdx
->pNext
){
6500 if( pIdx
->bUnordered
==0
6501 && pIdx
->szIdxRow
<pTab
->szTabRow
6502 && pIdx
->pPartIdxWhere
==0
6503 && (!pBest
|| pIdx
->szIdxRow
<pBest
->szIdxRow
)
6509 iRoot
= pBest
->tnum
;
6510 pKeyInfo
= sqlite3KeyInfoOfIndex(pParse
, pBest
);
6513 /* Open a read-only cursor, execute the OP_Count, close the cursor. */
6514 sqlite3VdbeAddOp4Int(v
, OP_OpenRead
, iCsr
, iRoot
, iDb
, 1);
6516 sqlite3VdbeChangeP4(v
, -1, (char *)pKeyInfo
, P4_KEYINFO
);
6518 sqlite3VdbeAddOp2(v
, OP_Count
, iCsr
, sAggInfo
.aFunc
[0].iMem
);
6519 sqlite3VdbeAddOp1(v
, OP_Close
, iCsr
);
6520 explainSimpleCount(pParse
, pTab
, pBest
);
6522 #endif /* SQLITE_OMIT_BTREECOUNT */
6524 int regAcc
= 0; /* "populate accumulators" flag */
6526 /* If there are accumulator registers but no min() or max() functions,
6527 ** allocate register regAcc. Register regAcc will contain 0 the first
6528 ** time the inner loop runs, and 1 thereafter. The code generated
6529 ** by updateAccumulator() only updates the accumulator registers if
6530 ** regAcc contains 0. */
6531 if( sAggInfo
.nAccumulator
){
6532 for(i
=0; i
<sAggInfo
.nFunc
; i
++){
6533 if( sAggInfo
.aFunc
[i
].pFunc
->funcFlags
&SQLITE_FUNC_NEEDCOLL
) break;
6535 if( i
==sAggInfo
.nFunc
){
6536 regAcc
= ++pParse
->nMem
;
6537 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, regAcc
);
6541 /* This case runs if the aggregate has no GROUP BY clause. The
6542 ** processing is much simpler since there is only a single row
6545 assert( p
->pGroupBy
==0 );
6546 resetAccumulator(pParse
, &sAggInfo
);
6548 /* If this query is a candidate for the min/max optimization, then
6549 ** minMaxFlag will have been previously set to either
6550 ** WHERE_ORDERBY_MIN or WHERE_ORDERBY_MAX and pMinMaxOrderBy will
6551 ** be an appropriate ORDER BY expression for the optimization.
6553 assert( minMaxFlag
==WHERE_ORDERBY_NORMAL
|| pMinMaxOrderBy
!=0 );
6554 assert( pMinMaxOrderBy
==0 || pMinMaxOrderBy
->nExpr
==1 );
6556 SELECTTRACE(1,pParse
,p
,("WhereBegin\n"));
6557 pWInfo
= sqlite3WhereBegin(pParse
, pTabList
, pWhere
, pMinMaxOrderBy
,
6562 updateAccumulator(pParse
, regAcc
, &sAggInfo
);
6563 if( regAcc
) sqlite3VdbeAddOp2(v
, OP_Integer
, 1, regAcc
);
6564 if( sqlite3WhereIsOrdered(pWInfo
)>0 ){
6565 sqlite3VdbeGoto(v
, sqlite3WhereBreakLabel(pWInfo
));
6566 VdbeComment((v
, "%s() by index",
6567 (minMaxFlag
==WHERE_ORDERBY_MIN
?"min":"max")));
6569 sqlite3WhereEnd(pWInfo
);
6570 finalizeAggFunctions(pParse
, &sAggInfo
);
6574 sqlite3ExprIfFalse(pParse
, pHaving
, addrEnd
, SQLITE_JUMPIFNULL
);
6575 selectInnerLoop(pParse
, p
, -1, 0, 0,
6576 pDest
, addrEnd
, addrEnd
);
6578 sqlite3VdbeResolveLabel(v
, addrEnd
);
6580 } /* endif aggregate query */
6582 if( sDistinct
.eTnctType
==WHERE_DISTINCT_UNORDERED
){
6583 explainTempTable(pParse
, "DISTINCT");
6586 /* If there is an ORDER BY clause, then we need to sort the results
6587 ** and send them to the callback one by one.
6589 if( sSort
.pOrderBy
){
6590 explainTempTable(pParse
,
6591 sSort
.nOBSat
>0 ? "RIGHT PART OF ORDER BY":"ORDER BY");
6592 assert( p
->pEList
==pEList
);
6593 generateSortTail(pParse
, p
, &sSort
, pEList
->nExpr
, pDest
);
6596 /* Jump here to skip this query
6598 sqlite3VdbeResolveLabel(v
, iEnd
);
6600 /* The SELECT has been coded. If there is an error in the Parse structure,
6601 ** set the return code to 1. Otherwise 0. */
6602 rc
= (pParse
->nErr
>0);
6604 /* Control jumps to here if an error is encountered above, or upon
6605 ** successful coding of the SELECT.
6608 sqlite3ExprListDelete(db
, pMinMaxOrderBy
);
6609 sqlite3DbFree(db
, sAggInfo
.aCol
);
6610 sqlite3DbFree(db
, sAggInfo
.aFunc
);
6611 #if SELECTTRACE_ENABLED
6612 SELECTTRACE(0x1,pParse
,p
,("end processing\n"));
6613 if( (sqlite3SelectTrace
& 0x2000)!=0 && ExplainQueryPlanParent(pParse
)==0 ){
6614 sqlite3TreeViewSelect(0, p
, 0);
6617 ExplainQueryPlanPop(pParse
);