third_party/sqlite/sqlite-src-3100200/src/select.c - Issue 2846743003: [sql] Remove SQLite 3.10.2 reference directory.

Side by Side Diff: third_party/sqlite/sqlite-src-3100200/src/select.c

Issue 2846743003: [sql] Remove SQLite 3.10.2 reference directory. (Closed)

Patch Set: Created 3 years, 7 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

OLD	NEW
	(Empty)
1 /*

2 ** 2001 September 15

3 **

4 ** The author disclaims copyright to this source code. In place of

5 ** a legal notice, here is a blessing:

6 **

7 ** May you do good and not evil.

8 ** May you find forgiveness for yourself and forgive others.

9 ** May you share freely, never taking more than you give.

10 **

11 *************************************************************************

12 ** This file contains C code routines that are called by the parser

13 ** to handle SELECT statements in SQLite.

14 */

15 #include "sqliteInt.h"

16

17 /*

18 ** Trace output macros

19 */

20 #if SELECTTRACE_ENABLED

21 /***/ int sqlite3SelectTrace = 0;

22 # define SELECTTRACE(K,P,S,X) \

23 if(sqlite3SelectTrace&(K)) \

24 sqlite3DebugPrintf("%s%s.%p: ",(P)->nSelectIndent2-2,"",\

25 (S)->zSelName,(S)),\

26 sqlite3DebugPrintf X

27 #else

28 # define SELECTTRACE(K,P,S,X)

29 #endif

30

31

32 /*

33 ** An instance of the following object is used to record information about

34 ** how to process the DISTINCT keyword, to simplify passing that information

35 ** into the selectInnerLoop() routine.

36 */

37 typedef struct DistinctCtx DistinctCtx;

38 struct DistinctCtx {

39 u8 isTnct; /* True if the DISTINCT keyword is present */

40 u8 eTnctType; /* One of the WHERE_DISTINCT_* operators */

41 int tabTnct; /* Ephemeral table used for DISTINCT processing */

42 int addrTnct; /* Address of OP_OpenEphemeral opcode for tabTnct */

43 };

44

45 /*

46 ** An instance of the following object is used to record information about

47 ** the ORDER BY (or GROUP BY) clause of query is being coded.

48 */

49 typedef struct SortCtx SortCtx;

50 struct SortCtx {

51 ExprList pOrderBy; / The ORDER BY (or GROUP BY clause) */

52 int nOBSat; /* Number of ORDER BY terms satisfied by indices */

53 int iECursor; /* Cursor number for the sorter */

54 int regReturn; /* Register holding block-output return address */

55 int labelBkOut; /* Start label for the block-output subroutine */

56 int addrSortIndex; /* Address of the OP_SorterOpen or OP_OpenEphemeral */

57 int labelDone; /* Jump here when done, ex: LIMIT reached */

58 u8 sortFlags; /* Zero or more SORTFLAG_* bits */

59 };

60 #define SORTFLAG_UseSorter 0x01 /* Use SorterOpen instead of OpenEphemeral */

61

62 /*

63 ** Delete all the content of a Select structure. Deallocate the structure

64 ** itself only if bFree is true.

65 */

66 static void clearSelect(sqlite3 db, Select p, int bFree){

67 while( p ){

68 Select *pPrior = p->pPrior;

69 sqlite3ExprListDelete(db, p->pEList);

70 sqlite3SrcListDelete(db, p->pSrc);

71 sqlite3ExprDelete(db, p->pWhere);

72 sqlite3ExprListDelete(db, p->pGroupBy);

73 sqlite3ExprDelete(db, p->pHaving);

74 sqlite3ExprListDelete(db, p->pOrderBy);

75 sqlite3ExprDelete(db, p->pLimit);

76 sqlite3ExprDelete(db, p->pOffset);

77 sqlite3WithDelete(db, p->pWith);

78 if( bFree ) sqlite3DbFree(db, p);

79 p = pPrior;

80 bFree = 1;

81 }

82 }

83

84 /*

85 ** Initialize a SelectDest structure.

86 */

87 void sqlite3SelectDestInit(SelectDest *pDest, int eDest, int iParm){

88 pDest->eDest = (u8)eDest;

89 pDest->iSDParm = iParm;

90 pDest->affSdst = 0;

91 pDest->iSdst = 0;

92 pDest->nSdst = 0;

93 }

94

95

96 /*

97 ** Allocate a new Select structure and return a pointer to that

98 ** structure.

99 */

100 Select *sqlite3SelectNew(

101 Parse pParse, / Parsing context */

102 ExprList pEList, / which columns to include in the result */

103 SrcList pSrc, / the FROM clause -- which tables to scan */

104 Expr pWhere, / the WHERE clause */

105 ExprList pGroupBy, / the GROUP BY clause */

106 Expr pHaving, / the HAVING clause */

107 ExprList pOrderBy, / the ORDER BY clause */

108 u16 selFlags, /* Flag parameters, such as SF_Distinct */

109 Expr pLimit, / LIMIT value. NULL means not used */

110 Expr pOffset / OFFSET value. NULL means no offset */

111 ){

112 Select *pNew;

113 Select standin;

114 sqlite3 *db = pParse->db;

115 pNew = sqlite3DbMallocZero(db, sizeof(*pNew) );

116 if( pNew==0 ){

117 assert( db->mallocFailed );

118 pNew = &standin;

119 memset(pNew, 0, sizeof(*pNew));

120 }

121 if( pEList==0 ){

122 pEList = sqlite3ExprListAppend(pParse, 0, sqlite3Expr(db,TK_ASTERISK,0));

123 }

124 pNew->pEList = pEList;

125 if( pSrc==0 ) pSrc = sqlite3DbMallocZero(db, sizeof(*pSrc));

126 pNew->pSrc = pSrc;

127 pNew->pWhere = pWhere;

128 pNew->pGroupBy = pGroupBy;

129 pNew->pHaving = pHaving;

130 pNew->pOrderBy = pOrderBy;

131 pNew->selFlags = selFlags;

132 pNew->op = TK_SELECT;

133 pNew->pLimit = pLimit;

134 pNew->pOffset = pOffset;

135 assert( pOffset==0 \|\| pLimit!=0 \|\| pParse->nErr>0 \|\| db->mallocFailed!=0 );

136 pNew->addrOpenEphm[0] = -1;

137 pNew->addrOpenEphm[1] = -1;

138 if( db->mallocFailed ) {

139 clearSelect(db, pNew, pNew!=&standin);

140 pNew = 0;

141 }else{

142 assert( pNew->pSrc!=0 \|\| pParse->nErr>0 );

143 }

144 assert( pNew!=&standin );

145 return pNew;

146 }

147

148 #if SELECTTRACE_ENABLED

149 /*

150 ** Set the name of a Select object

151 */

152 void sqlite3SelectSetName(Select p, const char zName){

153 if( p && zName ){

154 sqlite3_snprintf(sizeof(p->zSelName), p->zSelName, "%s", zName);

155 }

156 }

157 #endif

158

159

160 /*

161 ** Delete the given Select structure and all of its substructures.

162 */

163 void sqlite3SelectDelete(sqlite3 db, Select p){

164 clearSelect(db, p, 1);

165 }

166

167 /*

168 ** Return a pointer to the right-most SELECT statement in a compound.

169 */

170 static Select findRightmost(Select p){

171 while( p->pNext ) p = p->pNext;

172 return p;

173 }

174

175 /*

176 ** Given 1 to 3 identifiers preceding the JOIN keyword, determine the

177 ** type of join. Return an integer constant that expresses that type

178 ** in terms of the following bit values:

179 **

180 ** JT_INNER

181 ** JT_CROSS

182 ** JT_OUTER

183 ** JT_NATURAL

184 ** JT_LEFT

185 ** JT_RIGHT

186 **

187 ** A full outer join is the combination of JT_LEFT and JT_RIGHT.

188 **

189 ** If an illegal or unsupported join type is seen, then still return

190 ** a join type, but put an error in the pParse structure.

191 */

192 int sqlite3JoinType(Parse pParse, Token pA, Token pB, Token pC){

193 int jointype = 0;

194 Token *apAll[3];

195 Token *p;

196 /* 0123456789 123456789 123456789 123 */

197 static const char zKeyText[] = "naturaleftouterightfullinnercross";

198 static const struct {

199 u8 i; /* Beginning of keyword text in zKeyText[] */

200 u8 nChar; /* Length of the keyword in characters */

201 u8 code; /* Join type mask */

202 } aKeyword[] = {

203 /* natural */ { 0, 7, JT_NATURAL },

204 /* left */ { 6, 4, JT_LEFT\|JT_OUTER },

205 /* outer */ { 10, 5, JT_OUTER },

206 /* right */ { 14, 5, JT_RIGHT\|JT_OUTER },

207 /* full */ { 19, 4, JT_LEFT\|JT_RIGHT\|JT_OUTER },

208 /* inner */ { 23, 5, JT_INNER },

209 /* cross */ { 28, 5, JT_INNER\|JT_CROSS },

210 };

211 int i, j;

212 apAll[0] = pA;

213 apAll[1] = pB;

214 apAll[2] = pC;

215 for(i=0; i<3 && apAll[i]; i++){

216 p = apAll[i];

217 for(j=0; j<ArraySize(aKeyword); j++){

218 if( p->n==aKeyword[j].nChar

219 && sqlite3StrNICmp((char*)p->z, &zKeyText[aKeyword[j].i], p->n)==0 ){

220 jointype \|= aKeyword[j].code;

221 break;

222 }

223 }

224 testcase( j==0 \|\| j==1 \|\| j==2 \|\| j==3 \|\| j==4 \|\| j==5 \|\| j==6 );

225 if( j>=ArraySize(aKeyword) ){

226 jointype \|= JT_ERROR;

227 break;

228 }

229 }

230 if(

231 (jointype & (JT_INNER\|JT_OUTER))==(JT_INNER\|JT_OUTER) \|\|

232 (jointype & JT_ERROR)!=0

233 ){

234 const char *zSp = " ";

235 assert( pB!=0 );

236 if( pC==0 ){ zSp++; }

237 sqlite3ErrorMsg(pParse, "unknown or unsupported join type: "

238 "%T %T%s%T", pA, pB, zSp, pC);

239 jointype = JT_INNER;

240 }else if( (jointype & JT_OUTER)!=0

241 && (jointype & (JT_LEFT\|JT_RIGHT))!=JT_LEFT ){

242 sqlite3ErrorMsg(pParse,

243 "RIGHT and FULL OUTER JOINs are not currently supported");

244 jointype = JT_INNER;

245 }

246 return jointype;

247 }

248

249 /*

250 ** Return the index of a column in a table. Return -1 if the column

251 ** is not contained in the table.

252 */

253 static int columnIndex(Table pTab, const char zCol){

254 int i;

255 for(i=0; i<pTab->nCol; i++){

256 if( sqlite3StrICmp(pTab->aCol[i].zName, zCol)==0 ) return i;

257 }

258 return -1;

259 }

260

261 /*

262 ** Search the first N tables in pSrc, from left to right, looking for a

263 ** table that has a column named zCol.

264 **

265 ** When found, set piTab and piCol to the table index and column index

266 ** of the matching column and return TRUE.

267 **

268 ** If not found, return FALSE.

269 */

270 static int tableAndColumnIndex(

271 SrcList pSrc, / Array of tables to search */

272 int N, /* Number of tables in pSrc->a[] to search */

273 const char zCol, / Name of the column we are looking for */

274 int piTab, / Write index of pSrc->a[] here */

275 int piCol / Write index of pSrc->a[piTab].pTab->aCol[] here /

276 ){

277 int i; /* For looping over tables in pSrc */

278 int iCol; /* Index of column matching zCol */

279

280 assert( (piTab==0)==(piCol==0) ); /* Both or neither are NULL */

281 for(i=0; i<N; i++){

282 iCol = columnIndex(pSrc->a[i].pTab, zCol);

283 if( iCol>=0 ){

284 if( piTab ){

285 *piTab = i;

286 *piCol = iCol;

287 }

288 return 1;

289 }

290 }

291 return 0;

292 }

293

294 /*

295 ** This function is used to add terms implied by JOIN syntax to the

296 ** WHERE clause expression of a SELECT statement. The new term, which

297 ** is ANDed with the existing WHERE clause, is of the form:

298 **

299 ** (tab1.col1 = tab2.col2)

300 **

301 ** where tab1 is the iSrc'th table in SrcList pSrc and tab2 is the

302 ** (iSrc+1)'th. Column col1 is column iColLeft of tab1, and col2 is

303 ** column iColRight of tab2.

304 */

305 static void addWhereTerm(

306 Parse pParse, / Parsing context */

307 SrcList pSrc, / List of tables in FROM clause */

308 int iLeft, /* Index of first table to join in pSrc */

309 int iColLeft, /* Index of column in first table */

310 int iRight, /* Index of second table in pSrc */

311 int iColRight, /* Index of column in second table */

312 int isOuterJoin, /* True if this is an OUTER join */

313 Expr *ppWhere / IN/OUT: The WHERE clause to add to */

314 ){

315 sqlite3 *db = pParse->db;

316 Expr *pE1;

317 Expr *pE2;

318 Expr *pEq;

319

320 assert( iLeft<iRight );

321 assert( pSrc->nSrc>iRight );

322 assert( pSrc->a[iLeft].pTab );

323 assert( pSrc->a[iRight].pTab );

324

325 pE1 = sqlite3CreateColumnExpr(db, pSrc, iLeft, iColLeft);

326 pE2 = sqlite3CreateColumnExpr(db, pSrc, iRight, iColRight);

327

328 pEq = sqlite3PExpr(pParse, TK_EQ, pE1, pE2, 0);

329 if( pEq && isOuterJoin ){

330 ExprSetProperty(pEq, EP_FromJoin);

331 assert( !ExprHasProperty(pEq, EP_TokenOnly\|EP_Reduced) );

332 ExprSetVVAProperty(pEq, EP_NoReduce);

333 pEq->iRightJoinTable = (i16)pE2->iTable;

334 }

335 ppWhere = sqlite3ExprAnd(db, ppWhere, pEq);

336 }

337

338 /*

339 ** Set the EP_FromJoin property on all terms of the given expression.

340 ** And set the Expr.iRightJoinTable to iTable for every term in the

341 ** expression.

342 **

343 ** The EP_FromJoin property is used on terms of an expression to tell

344 ** the LEFT OUTER JOIN processing logic that this term is part of the

345 ** join restriction specified in the ON or USING clause and not a part

346 ** of the more general WHERE clause. These terms are moved over to the

347 ** WHERE clause during join processing but we need to remember that they

348 ** originated in the ON or USING clause.

349 **

350 ** The Expr.iRightJoinTable tells the WHERE clause processing that the

351 ** expression depends on table iRightJoinTable even if that table is not

352 ** explicitly mentioned in the expression. That information is needed

353 ** for cases like this:

354 **

355 ** SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.b AND t1.x=5

356 **

357 ** The where clause needs to defer the handling of the t1.x=5

358 ** term until after the t2 loop of the join. In that way, a

359 ** NULL t2 row will be inserted whenever t1.x!=5. If we do not

360 ** defer the handling of t1.x=5, it will be processed immediately

361 ** after the t1 loop and rows with t1.x!=5 will never appear in

362 ** the output, which is incorrect.

363 */

364 static void setJoinExpr(Expr *p, int iTable){

365 while( p ){

366 ExprSetProperty(p, EP_FromJoin);

367 assert( !ExprHasProperty(p, EP_TokenOnly\|EP_Reduced) );

368 ExprSetVVAProperty(p, EP_NoReduce);

369 p->iRightJoinTable = (i16)iTable;

370 if( p->op==TK_FUNCTION && p->x.pList ){

371 int i;

372 for(i=0; i<p->x.pList->nExpr; i++){

373 setJoinExpr(p->x.pList->a[i].pExpr, iTable);

374 }

375 }

376 setJoinExpr(p->pLeft, iTable);

377 p = p->pRight;

378 }

379 }

380

381 /*

382 ** This routine processes the join information for a SELECT statement.

383 ** ON and USING clauses are converted into extra terms of the WHERE clause.

384 ** NATURAL joins also create extra WHERE clause terms.

385 **

386 ** The terms of a FROM clause are contained in the Select.pSrc structure.

387 ** The left most table is the first entry in Select.pSrc. The right-most

388 ** table is the last entry. The join operator is held in the entry to

389 ** the left. Thus entry 0 contains the join operator for the join between

390 ** entries 0 and 1. Any ON or USING clauses associated with the join are

391 ** also attached to the left entry.

392 **

393 ** This routine returns the number of errors encountered.

394 */

395 static int sqliteProcessJoin(Parse pParse, Select p){

396 SrcList pSrc; / All tables in the FROM clause */

397 int i, j; /* Loop counters */

398 struct SrcList_item pLeft; / Left table being joined */

399 struct SrcList_item pRight; / Right table being joined */

400

401 pSrc = p->pSrc;

402 pLeft = &pSrc->a[0];

403 pRight = &pLeft[1];

404 for(i=0; i<pSrc->nSrc-1; i++, pRight++, pLeft++){

405 Table *pLeftTab = pLeft->pTab;

406 Table *pRightTab = pRight->pTab;

407 int isOuter;

408

409 if( NEVER(pLeftTab==0 \|\| pRightTab==0) ) continue;

410 isOuter = (pRight->fg.jointype & JT_OUTER)!=0;

411

412 /* When the NATURAL keyword is present, add WHERE clause terms for

413 ** every column that the two tables have in common.

414 */

415 if( pRight->fg.jointype & JT_NATURAL ){

416 if( pRight->pOn \|\| pRight->pUsing ){

417 sqlite3ErrorMsg(pParse, "a NATURAL join may not have "

418 "an ON or USING clause", 0);

419 return 1;

420 }

421 for(j=0; j<pRightTab->nCol; j++){

422 char zName; / Name of column in the right table */

423 int iLeft; /* Matching left table */

424 int iLeftCol; /* Matching column in the left table */

425

426 zName = pRightTab->aCol[j].zName;

427 if( tableAndColumnIndex(pSrc, i+1, zName, &iLeft, &iLeftCol) ){

428 addWhereTerm(pParse, pSrc, iLeft, iLeftCol, i+1, j,

429 isOuter, &p->pWhere);

430 }

431 }

432 }

433

434 /* Disallow both ON and USING clauses in the same join

435 */

436 if( pRight->pOn && pRight->pUsing ){

437 sqlite3ErrorMsg(pParse, "cannot have both ON and USING "

438 "clauses in the same join");

439 return 1;

440 }

441

442 /* Add the ON clause to the end of the WHERE clause, connected by

443 ** an AND operator.

444 */

445 if( pRight->pOn ){

446 if( isOuter ) setJoinExpr(pRight->pOn, pRight->iCursor);

447 p->pWhere = sqlite3ExprAnd(pParse->db, p->pWhere, pRight->pOn);

448 pRight->pOn = 0;

449 }

450

451 /* Create extra terms on the WHERE clause for each column named

452 ** in the USING clause. Example: If the two tables to be joined are

453 ** A and B and the USING clause names X, Y, and Z, then add this

454 ** to the WHERE clause: A.X=B.X AND A.Y=B.Y AND A.Z=B.Z

455 ** Report an error if any column mentioned in the USING clause is

456 ** not contained in both tables to be joined.

457 */

458 if( pRight->pUsing ){

459 IdList *pList = pRight->pUsing;

460 for(j=0; j<pList->nId; j++){

461 char zName; / Name of the term in the USING clause */

462 int iLeft; /* Table on the left with matching column name */

463 int iLeftCol; /* Column number of matching column on the left */

464 int iRightCol; /* Column number of matching column on the right */

465

466 zName = pList->a[j].zName;

467 iRightCol = columnIndex(pRightTab, zName);

468 if( iRightCol<0

469 \|\| !tableAndColumnIndex(pSrc, i+1, zName, &iLeft, &iLeftCol)

470 ){

471 sqlite3ErrorMsg(pParse, "cannot join using column %s - column "

472 "not present in both tables", zName);

473 return 1;

474 }

475 addWhereTerm(pParse, pSrc, iLeft, iLeftCol, i+1, iRightCol,

476 isOuter, &p->pWhere);

477 }

478 }

479 }

480 return 0;

481 }

482

483 /* Forward reference */

484 static KeyInfo *keyInfoFromExprList(

485 Parse pParse, / Parsing context */

486 ExprList pList, / Form the KeyInfo object from this ExprList */

487 int iStart, /* Begin with this column of pList */

488 int nExtra /* Add this many extra columns to the end */

489 );

490

491 /*

492 ** Generate code that will push the record in registers regData

493 ** through regData+nData-1 onto the sorter.

494 */

495 static void pushOntoSorter(

496 Parse pParse, / Parser context */

497 SortCtx pSort, / Information about the ORDER BY clause */

498 Select pSelect, / The whole SELECT statement */

499 int regData, /* First register holding data to be sorted */

500 int regOrigData, /* First register holding data before packing */

501 int nData, /* Number of elements in the data array */

502 int nPrefixReg /* No. of reg prior to regData available for use */

503 ){

504 Vdbe v = pParse->pVdbe; / Stmt under construction */

505 int bSeq = ((pSort->sortFlags & SORTFLAG_UseSorter)==0);

506 int nExpr = pSort->pOrderBy->nExpr; /* No. of ORDER BY terms */

507 int nBase = nExpr + bSeq + nData; /* Fields in sorter record */

508 int regBase; /* Regs for sorter record */

509 int regRecord = ++pParse->nMem; /* Assembled sorter record */

510 int nOBSat = pSort->nOBSat; /* ORDER BY terms to skip */

511 int op; /* Opcode to add sorter record to sorter */

512 int iLimit; /* LIMIT counter */

513

514 assert( bSeq==0 \|\| bSeq==1 );

515 assert( nData==1 \|\| regData==regOrigData );

516 if( nPrefixReg ){

517 assert( nPrefixReg==nExpr+bSeq );

518 regBase = regData - nExpr - bSeq;

519 }else{

520 regBase = pParse->nMem + 1;

521 pParse->nMem += nBase;

522 }

523 assert( pSelect->iOffset==0 \|\| pSelect->iLimit!=0 );

524 iLimit = pSelect->iOffset ? pSelect->iOffset+1 : pSelect->iLimit;

525 pSort->labelDone = sqlite3VdbeMakeLabel(v);

526 sqlite3ExprCodeExprList(pParse, pSort->pOrderBy, regBase, regOrigData,

527 SQLITE_ECEL_DUP\|SQLITE_ECEL_REF);

528 if( bSeq ){

529 sqlite3VdbeAddOp2(v, OP_Sequence, pSort->iECursor, regBase+nExpr);

530 }

531 if( nPrefixReg==0 ){

532 sqlite3ExprCodeMove(pParse, regData, regBase+nExpr+bSeq, nData);

533 }

534 sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase+nOBSat, nBase-nOBSat, regRecord);

535 if( nOBSat>0 ){

536 int regPrevKey; /* The first nOBSat columns of the previous row */

537 int addrFirst; /* Address of the OP_IfNot opcode */

538 int addrJmp; /* Address of the OP_Jump opcode */

539 VdbeOp pOp; / Opcode that opens the sorter */

540 int nKey; /* Number of sorting key columns, including OP_Sequence */

541 KeyInfo pKI; / Original KeyInfo on the sorter table */

542

543 regPrevKey = pParse->nMem+1;

544 pParse->nMem += pSort->nOBSat;

545 nKey = nExpr - pSort->nOBSat + bSeq;

546 if( bSeq ){

547 addrFirst = sqlite3VdbeAddOp1(v, OP_IfNot, regBase+nExpr);

548 }else{

549 addrFirst = sqlite3VdbeAddOp1(v, OP_SequenceTest, pSort->iECursor);

550 }

551 VdbeCoverage(v);

552 sqlite3VdbeAddOp3(v, OP_Compare, regPrevKey, regBase, pSort->nOBSat);

553 pOp = sqlite3VdbeGetOp(v, pSort->addrSortIndex);

554 if( pParse->db->mallocFailed ) return;

555 pOp->p2 = nKey + nData;

556 pKI = pOp->p4.pKeyInfo;

557 memset(pKI->aSortOrder, 0, pKI->nField); /* Makes OP_Jump below testable */

558 sqlite3VdbeChangeP4(v, -1, (char*)pKI, P4_KEYINFO);

559 testcase( pKI->nXField>2 );

560 pOp->p4.pKeyInfo = keyInfoFromExprList(pParse, pSort->pOrderBy, nOBSat,

561 pKI->nXField-1);

562 addrJmp = sqlite3VdbeCurrentAddr(v);

563 sqlite3VdbeAddOp3(v, OP_Jump, addrJmp+1, 0, addrJmp+1); VdbeCoverage(v);

564 pSort->labelBkOut = sqlite3VdbeMakeLabel(v);

565 pSort->regReturn = ++pParse->nMem;

566 sqlite3VdbeAddOp2(v, OP_Gosub, pSort->regReturn, pSort->labelBkOut);

567 sqlite3VdbeAddOp1(v, OP_ResetSorter, pSort->iECursor);

568 if( iLimit ){

569 sqlite3VdbeAddOp2(v, OP_IfNot, iLimit, pSort->labelDone);

570 VdbeCoverage(v);

571 }

572 sqlite3VdbeJumpHere(v, addrFirst);

573 sqlite3ExprCodeMove(pParse, regBase, regPrevKey, pSort->nOBSat);

574 sqlite3VdbeJumpHere(v, addrJmp);

575 }

576 if( pSort->sortFlags & SORTFLAG_UseSorter ){

577 op = OP_SorterInsert;

578 }else{

579 op = OP_IdxInsert;

580 }

581 sqlite3VdbeAddOp2(v, op, pSort->iECursor, regRecord);

582 if( iLimit ){

583 int addr;

584 addr = sqlite3VdbeAddOp3(v, OP_IfNotZero, iLimit, 0, 1); VdbeCoverage(v);

585 sqlite3VdbeAddOp1(v, OP_Last, pSort->iECursor);

586 sqlite3VdbeAddOp1(v, OP_Delete, pSort->iECursor);

587 sqlite3VdbeJumpHere(v, addr);

588 }

589 }

590

591 /*

592 ** Add code to implement the OFFSET

593 */

594 static void codeOffset(

595 Vdbe v, / Generate code into this VM */

596 int iOffset, /* Register holding the offset counter */

597 int iContinue /* Jump here to skip the current record */

598 ){

599 if( iOffset>0 ){

600 sqlite3VdbeAddOp3(v, OP_IfPos, iOffset, iContinue, 1); VdbeCoverage(v);

601 VdbeComment((v, "OFFSET"));

602 }

603 }

604

605 /*

606 ** Add code that will check to make sure the N registers starting at iMem

607 ** form a distinct entry. iTab is a sorting index that holds previously

608 ** seen combinations of the N values. A new entry is made in iTab

609 ** if the current N values are new.

610 **

611 ** A jump to addrRepeat is made and the N+1 values are popped from the

612 ** stack if the top N elements are not distinct.

613 */

614 static void codeDistinct(

615 Parse pParse, / Parsing and code generating context */

616 int iTab, /* A sorting index used to test for distinctness */

617 int addrRepeat, /* Jump to here if not distinct */

618 int N, /* Number of elements */

619 int iMem /* First element */

620 ){

621 Vdbe *v;

622 int r1;

623

624 v = pParse->pVdbe;

625 r1 = sqlite3GetTempReg(pParse);

626 sqlite3VdbeAddOp4Int(v, OP_Found, iTab, addrRepeat, iMem, N); VdbeCoverage(v);

627 sqlite3VdbeAddOp3(v, OP_MakeRecord, iMem, N, r1);

628 sqlite3VdbeAddOp2(v, OP_IdxInsert, iTab, r1);

629 sqlite3ReleaseTempReg(pParse, r1);

630 }

631

632 #ifndef SQLITE_OMIT_SUBQUERY

633 /*

634 ** Generate an error message when a SELECT is used within a subexpression

635 ** (example: "a IN (SELECT * FROM table)") but it has more than 1 result

636 ** column. We do this in a subroutine because the error used to occur

637 ** in multiple places. (The error only occurs in one place now, but we

638 ** retain the subroutine to minimize code disruption.)

639 */

640 static int checkForMultiColumnSelectError(

641 Parse pParse, / Parse context. */

642 SelectDest pDest, / Destination of SELECT results */

643 int nExpr /* Number of result columns returned by SELECT */

644 ){

645 int eDest = pDest->eDest;

646 if( nExpr>1 && (eDest==SRT_Mem \|\| eDest==SRT_Set) ){

647 sqlite3ErrorMsg(pParse, "only a single result allowed for "

648 "a SELECT that is part of an expression");

649 return 1;

650 }else{

651 return 0;

652 }

653 }

654 #endif

655

656 /*

657 ** This routine generates the code for the inside of the inner loop

658 ** of a SELECT.

659 **

660 ** If srcTab is negative, then the pEList expressions

661 ** are evaluated in order to get the data for this row. If srcTab is

662 ** zero or more, then data is pulled from srcTab and pEList is used only

663 ** to get number columns and the datatype for each column.

664 */

665 static void selectInnerLoop(

666 Parse pParse, / The parser context */

667 Select p, / The complete select statement being coded */

668 ExprList pEList, / List of values being extracted */

669 int srcTab, /* Pull data from this table */

670 SortCtx pSort, / If not NULL, info on how to process ORDER BY */

671 DistinctCtx pDistinct, / If not NULL, info on how to process DISTINCT */

672 SelectDest pDest, / How to dispose of the results */

673 int iContinue, /* Jump here to continue with next row */

674 int iBreak /* Jump here to break out of the inner loop */

675 ){

676 Vdbe *v = pParse->pVdbe;

677 int i;

678 int hasDistinct; /* True if the DISTINCT keyword is present */

679 int regResult; /* Start of memory holding result set */

680 int eDest = pDest->eDest; /* How to dispose of results */

681 int iParm = pDest->iSDParm; /* First argument to disposal method */

682 int nResultCol; /* Number of result columns */

683 int nPrefixReg = 0; /* Number of extra registers before regResult */

684

685 assert( v );

686 assert( pEList!=0 );

687 hasDistinct = pDistinct ? pDistinct->eTnctType : WHERE_DISTINCT_NOOP;

688 if( pSort && pSort->pOrderBy==0 ) pSort = 0;

689 if( pSort==0 && !hasDistinct ){

690 assert( iContinue!=0 );

691 codeOffset(v, p->iOffset, iContinue);

692 }

693

694 /* Pull the requested columns.

695 */

696 nResultCol = pEList->nExpr;

697

698 if( pDest->iSdst==0 ){

699 if( pSort ){

700 nPrefixReg = pSort->pOrderBy->nExpr;

701 if( !(pSort->sortFlags & SORTFLAG_UseSorter) ) nPrefixReg++;

702 pParse->nMem += nPrefixReg;

703 }

704 pDest->iSdst = pParse->nMem+1;

705 pParse->nMem += nResultCol;

706 }else if( pDest->iSdst+nResultCol > pParse->nMem ){

707 /* This is an error condition that can result, for example, when a SELECT

708 ** on the right-hand side of an INSERT contains more result columns than

709 ** there are columns in the table on the left. The error will be caught

710 ** and reported later. But we need to make sure enough memory is allocated

711 ** to avoid other spurious errors in the meantime. */

712 pParse->nMem += nResultCol;

713 }

714 pDest->nSdst = nResultCol;

715 regResult = pDest->iSdst;

716 if( srcTab>=0 ){

717 for(i=0; i<nResultCol; i++){

718 sqlite3VdbeAddOp3(v, OP_Column, srcTab, i, regResult+i);

719 VdbeComment((v, "%s", pEList->a[i].zName));

720 }

721 }else if( eDest!=SRT_Exists ){

722 /* If the destination is an EXISTS(...) expression, the actual

723 ** values returned by the SELECT are not required.

724 */

725 u8 ecelFlags;

726 if( eDest==SRT_Mem \|\| eDest==SRT_Output \|\| eDest==SRT_Coroutine ){

727 ecelFlags = SQLITE_ECEL_DUP;

728 }else{

729 ecelFlags = 0;

730 }

731 sqlite3ExprCodeExprList(pParse, pEList, regResult, 0, ecelFlags);

732 }

733

734 /* If the DISTINCT keyword was present on the SELECT statement

735 ** and this row has been seen before, then do not make this row

736 ** part of the result.

737 */

738 if( hasDistinct ){

739 switch( pDistinct->eTnctType ){

740 case WHERE_DISTINCT_ORDERED: {

741 VdbeOp pOp; / No longer required OpenEphemeral instr. */

742 int iJump; /* Jump destination */

743 int regPrev; /* Previous row content */

744

745 /* Allocate space for the previous row */

746 regPrev = pParse->nMem+1;

747 pParse->nMem += nResultCol;

748

749 /* Change the OP_OpenEphemeral coded earlier to an OP_Null

750 ** sets the MEM_Cleared bit on the first register of the

751 ** previous value. This will cause the OP_Ne below to always

752 ** fail on the first iteration of the loop even if the first

753 ** row is all NULLs.

754 */

755 sqlite3VdbeChangeToNoop(v, pDistinct->addrTnct);

756 pOp = sqlite3VdbeGetOp(v, pDistinct->addrTnct);

757 pOp->opcode = OP_Null;

758 pOp->p1 = 1;

759 pOp->p2 = regPrev;

760

761 iJump = sqlite3VdbeCurrentAddr(v) + nResultCol;

762 for(i=0; i<nResultCol; i++){

763 CollSeq *pColl = sqlite3ExprCollSeq(pParse, pEList->a[i].pExpr);

764 if( i<nResultCol-1 ){

765 sqlite3VdbeAddOp3(v, OP_Ne, regResult+i, iJump, regPrev+i);

766 VdbeCoverage(v);

767 }else{

768 sqlite3VdbeAddOp3(v, OP_Eq, regResult+i, iContinue, regPrev+i);

769 VdbeCoverage(v);

770 }

771 sqlite3VdbeChangeP4(v, -1, (const char *)pColl, P4_COLLSEQ);

772 sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);

773 }

774 assert( sqlite3VdbeCurrentAddr(v)==iJump \|\| pParse->db->mallocFailed );

775 sqlite3VdbeAddOp3(v, OP_Copy, regResult, regPrev, nResultCol-1);

776 break;

777 }

778

779 case WHERE_DISTINCT_UNIQUE: {

780 sqlite3VdbeChangeToNoop(v, pDistinct->addrTnct);

781 break;

782 }

783

784 default: {

785 assert( pDistinct->eTnctType==WHERE_DISTINCT_UNORDERED );

786 codeDistinct(pParse, pDistinct->tabTnct, iContinue, nResultCol,

787 regResult);

788 break;

789 }

790 }

791 if( pSort==0 ){

792 codeOffset(v, p->iOffset, iContinue);

793 }

794 }

795

796 switch( eDest ){

797 /* In this mode, write each query result to the key of the temporary

798 ** table iParm.

799 */

800 #ifndef SQLITE_OMIT_COMPOUND_SELECT

801 case SRT_Union: {

802 int r1;

803 r1 = sqlite3GetTempReg(pParse);

804 sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r1);

805 sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm, r1);

806 sqlite3ReleaseTempReg(pParse, r1);

807 break;

808 }

809

810 /* Construct a record from the query result, but instead of

811 ** saving that record, use it as a key to delete elements from

812 ** the temporary table iParm.

813 */

814 case SRT_Except: {

815 sqlite3VdbeAddOp3(v, OP_IdxDelete, iParm, regResult, nResultCol);

816 break;

817 }

818 #endif /* SQLITE_OMIT_COMPOUND_SELECT */

819

820 /* Store the result as data using a unique key.

821 */

822 case SRT_Fifo:

823 case SRT_DistFifo:

824 case SRT_Table:

825 case SRT_EphemTab: {

826 int r1 = sqlite3GetTempRange(pParse, nPrefixReg+1);

827 testcase( eDest==SRT_Table );

828 testcase( eDest==SRT_EphemTab );

829 testcase( eDest==SRT_Fifo );

830 testcase( eDest==SRT_DistFifo );

831 sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r1+nPrefixReg);

832 #ifndef SQLITE_OMIT_CTE

833 if( eDest==SRT_DistFifo ){

834 /* If the destination is DistFifo, then cursor (iParm+1) is open

835 ** on an ephemeral index. If the current row is already present

836 ** in the index, do not write it to the output. If not, add the

837 ** current row to the index and proceed with writing it to the

838 ** output table as well. */

839 int addr = sqlite3VdbeCurrentAddr(v) + 4;

840 sqlite3VdbeAddOp4Int(v, OP_Found, iParm+1, addr, r1, 0);

841 VdbeCoverage(v);

842 sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm+1, r1);

843 assert( pSort==0 );

844 }

845 #endif

846 if( pSort ){

847 pushOntoSorter(pParse, pSort, p, r1+nPrefixReg,regResult,1,nPrefixReg);

848 }else{

849 int r2 = sqlite3GetTempReg(pParse);

850 sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, r2);

851 sqlite3VdbeAddOp3(v, OP_Insert, iParm, r1, r2);

852 sqlite3VdbeChangeP5(v, OPFLAG_APPEND);

853 sqlite3ReleaseTempReg(pParse, r2);

854 }

855 sqlite3ReleaseTempRange(pParse, r1, nPrefixReg+1);

856 break;

857 }

858

859 #ifndef SQLITE_OMIT_SUBQUERY

860 /* If we are creating a set for an "expr IN (SELECT ...)" construct,

861 ** then there should be a single item on the stack. Write this

862 ** item into the set table with bogus data.

863 */

864 case SRT_Set: {

865 assert( nResultCol==1 );

866 pDest->affSdst =

867 sqlite3CompareAffinity(pEList->a[0].pExpr, pDest->affSdst);

868 if( pSort ){

869 /* At first glance you would think we could optimize out the

870 ** ORDER BY in this case since the order of entries in the set

871 ** does not matter. But there might be a LIMIT clause, in which

872 ** case the order does matter */

873 pushOntoSorter(pParse, pSort, p, regResult, regResult, 1, nPrefixReg);

874 }else{

875 int r1 = sqlite3GetTempReg(pParse);

876 sqlite3VdbeAddOp4(v, OP_MakeRecord, regResult,1,r1, &pDest->affSdst, 1);

877 sqlite3ExprCacheAffinityChange(pParse, regResult, 1);

878 sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm, r1);

879 sqlite3ReleaseTempReg(pParse, r1);

880 }

881 break;

882 }

883

884 /* If any row exist in the result set, record that fact and abort.

885 */

886 case SRT_Exists: {

887 sqlite3VdbeAddOp2(v, OP_Integer, 1, iParm);

888 /* The LIMIT clause will terminate the loop for us */

889 break;

890 }

891

892 /* If this is a scalar select that is part of an expression, then

893 ** store the results in the appropriate memory cell and break out

894 ** of the scan loop.

895 */

896 case SRT_Mem: {

897 assert( nResultCol==1 );

898 if( pSort ){

899 pushOntoSorter(pParse, pSort, p, regResult, regResult, 1, nPrefixReg);

900 }else{

901 assert( regResult==iParm );

902 /* The LIMIT clause will jump out of the loop for us */

903 }

904 break;

905 }

906 #endif /* #ifndef SQLITE_OMIT_SUBQUERY */

907

908 case SRT_Coroutine: /* Send data to a co-routine */

909 case SRT_Output: { /* Return the results */

910 testcase( eDest==SRT_Coroutine );

911 testcase( eDest==SRT_Output );

912 if( pSort ){

913 pushOntoSorter(pParse, pSort, p, regResult, regResult, nResultCol,

914 nPrefixReg);

915 }else if( eDest==SRT_Coroutine ){

916 sqlite3VdbeAddOp1(v, OP_Yield, pDest->iSDParm);

917 }else{

918 sqlite3VdbeAddOp2(v, OP_ResultRow, regResult, nResultCol);

919 sqlite3ExprCacheAffinityChange(pParse, regResult, nResultCol);

920 }

921 break;

922 }

923

924 #ifndef SQLITE_OMIT_CTE

925 /* Write the results into a priority queue that is order according to

926 ** pDest->pOrderBy (in pSO). pDest->iSDParm (in iParm) is the cursor for an

927 ** index with pSO->nExpr+2 columns. Build a key using pSO for the first

928 ** pSO->nExpr columns, then make sure all keys are unique by adding a

929 ** final OP_Sequence column. The last column is the record as a blob.

930 */

931 case SRT_DistQueue:

932 case SRT_Queue: {

933 int nKey;

934 int r1, r2, r3;

935 int addrTest = 0;

936 ExprList *pSO;

937 pSO = pDest->pOrderBy;

938 assert( pSO );

939 nKey = pSO->nExpr;

940 r1 = sqlite3GetTempReg(pParse);

941 r2 = sqlite3GetTempRange(pParse, nKey+2);

942 r3 = r2+nKey+1;

943 if( eDest==SRT_DistQueue ){

944 /* If the destination is DistQueue, then cursor (iParm+1) is open

945 ** on a second ephemeral index that holds all values every previously

946 ** added to the queue. */

947 addrTest = sqlite3VdbeAddOp4Int(v, OP_Found, iParm+1, 0,

948 regResult, nResultCol);

949 VdbeCoverage(v);

950 }

951 sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r3);

952 if( eDest==SRT_DistQueue ){

953 sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm+1, r3);

954 sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);

955 }

956 for(i=0; i<nKey; i++){

957 sqlite3VdbeAddOp2(v, OP_SCopy,

958 regResult + pSO->a[i].u.x.iOrderByCol - 1,

959 r2+i);

960 }

961 sqlite3VdbeAddOp2(v, OP_Sequence, iParm, r2+nKey);

962 sqlite3VdbeAddOp3(v, OP_MakeRecord, r2, nKey+2, r1);

963 sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm, r1);

964 if( addrTest ) sqlite3VdbeJumpHere(v, addrTest);

965 sqlite3ReleaseTempReg(pParse, r1);

966 sqlite3ReleaseTempRange(pParse, r2, nKey+2);

967 break;

968 }

969 #endif /* SQLITE_OMIT_CTE */

970

971

972

973 #if !defined(SQLITE_OMIT_TRIGGER)

974 /* Discard the results. This is used for SELECT statements inside

975 ** the body of a TRIGGER. The purpose of such selects is to call

976 ** user-defined functions that have side effects. We do not care

977 ** about the actual results of the select.

978 */

979 default: {

980 assert( eDest==SRT_Discard );

981 break;

982 }

983 #endif

984 }

985

986 /* Jump to the end of the loop if the LIMIT is reached. Except, if

987 ** there is a sorter, in which case the sorter has already limited

988 ** the output for us.

989 */

990 if( pSort==0 && p->iLimit ){

991 sqlite3VdbeAddOp2(v, OP_DecrJumpZero, p->iLimit, iBreak); VdbeCoverage(v);

992 }

993 }

994

995 /*

996 ** Allocate a KeyInfo object sufficient for an index of N key columns and

997 ** X extra columns.

998 */

999 KeyInfo sqlite3KeyInfoAlloc(sqlite3 db, int N, int X){

1000 KeyInfo *p = sqlite3DbMallocZero(0,

1001 sizeof(KeyInfo) + (N+X)(sizeof(CollSeq)+1));

1002 if( p ){

1003 p->aSortOrder = (u8*)&p->aColl[N+X];

1004 p->nField = (u16)N;

1005 p->nXField = (u16)X;

1006 p->enc = ENC(db);

1007 p->db = db;

1008 p->nRef = 1;

1009 }else{

1010 db->mallocFailed = 1;

1011 }

1012 return p;

1013 }

1014

1015 /*

1016 ** Deallocate a KeyInfo object

1017 */

1018 void sqlite3KeyInfoUnref(KeyInfo *p){

1019 if( p ){

1020 assert( p->nRef>0 );

1021 p->nRef--;

1022 if( p->nRef==0 ) sqlite3DbFree(0, p);

1023 }

1024 }

1025

1026 /*

1027 ** Make a new pointer to a KeyInfo object

1028 */

1029 KeyInfo sqlite3KeyInfoRef(KeyInfo p){

1030 if( p ){

1031 assert( p->nRef>0 );

1032 p->nRef++;

1033 }

1034 return p;

1035 }

1036

1037 #ifdef SQLITE_DEBUG

1038 /*

1039 ** Return TRUE if a KeyInfo object can be change. The KeyInfo object

1040 ** can only be changed if this is just a single reference to the object.

1041 **

1042 ** This routine is used only inside of assert() statements.

1043 */

1044 int sqlite3KeyInfoIsWriteable(KeyInfo *p){ return p->nRef==1; }

1045 #endif /* SQLITE_DEBUG */

1046

1047 /*

1048 ** Given an expression list, generate a KeyInfo structure that records

1049 ** the collating sequence for each expression in that expression list.

1050 **

1051 ** If the ExprList is an ORDER BY or GROUP BY clause then the resulting

1052 ** KeyInfo structure is appropriate for initializing a virtual index to

1053 ** implement that clause. If the ExprList is the result set of a SELECT

1054 ** then the KeyInfo structure is appropriate for initializing a virtual

1055 ** index to implement a DISTINCT test.

1056 **

1057 ** Space to hold the KeyInfo structure is obtained from malloc. The calling

1058 ** function is responsible for seeing that this structure is eventually

1059 ** freed.

1060 */

1061 static KeyInfo *keyInfoFromExprList(

1062 Parse pParse, / Parsing context */

1063 ExprList pList, / Form the KeyInfo object from this ExprList */

1064 int iStart, /* Begin with this column of pList */

1065 int nExtra /* Add this many extra columns to the end */

1066 ){

1067 int nExpr;

1068 KeyInfo *pInfo;

1069 struct ExprList_item *pItem;

1070 sqlite3 *db = pParse->db;

1071 int i;

1072

1073 nExpr = pList->nExpr;

1074 pInfo = sqlite3KeyInfoAlloc(db, nExpr-iStart, nExtra+1);

1075 if( pInfo ){

1076 assert( sqlite3KeyInfoIsWriteable(pInfo) );

1077 for(i=iStart, pItem=pList->a+iStart; i<nExpr; i++, pItem++){

1078 CollSeq *pColl;

1079 pColl = sqlite3ExprCollSeq(pParse, pItem->pExpr);

1080 if( !pColl ) pColl = db->pDfltColl;

1081 pInfo->aColl[i-iStart] = pColl;

1082 pInfo->aSortOrder[i-iStart] = pItem->sortOrder;

1083 }

1084 }

1085 return pInfo;

1086 }

1087

1088 /*

1089 ** Name of the connection operator, used for error messages.

1090 */

1091 static const char *selectOpName(int id){

1092 char *z;

1093 switch( id ){

1094 case TK_ALL: z = "UNION ALL"; break;

1095 case TK_INTERSECT: z = "INTERSECT"; break;

1096 case TK_EXCEPT: z = "EXCEPT"; break;

1097 default: z = "UNION"; break;

1098 }

1099 return z;

1100 }

1101

1102 #ifndef SQLITE_OMIT_EXPLAIN

1103 /*

1104 ** Unless an "EXPLAIN QUERY PLAN" command is being processed, this function

1105 ** is a no-op. Otherwise, it adds a single row of output to the EQP result,

1106 ** where the caption is of the form:

1107 **

1108 ** "USE TEMP B-TREE FOR xxx"

1109 **

1110 ** where xxx is one of "DISTINCT", "ORDER BY" or "GROUP BY". Exactly which

1111 ** is determined by the zUsage argument.

1112 */

1113 static void explainTempTable(Parse pParse, const char zUsage){

1114 if( pParse->explain==2 ){

1115 Vdbe *v = pParse->pVdbe;

1116 char *zMsg = sqlite3MPrintf(pParse->db, "USE TEMP B-TREE FOR %s", zUsage);

1117 sqlite3VdbeAddOp4(v, OP_Explain, pParse->iSelectId, 0, 0, zMsg, P4_DYNAMIC);

1118 }

1119 }

1120

1121 /*

1122 ** Assign expression b to lvalue a. A second, no-op, version of this macro

1123 ** is provided when SQLITE_OMIT_EXPLAIN is defined. This allows the code

1124 ** in sqlite3Select() to assign values to structure member variables that

1125 ** only exist if SQLITE_OMIT_EXPLAIN is not defined without polluting the

1126 ** code with #ifndef directives.

1127 */

1128 # define explainSetInteger(a, b) a = b

1129

1130 #else

1131 /* No-op versions of the explainXXX() functions and macros. */

1132 # define explainTempTable(y,z)

1133 # define explainSetInteger(y,z)

1134 #endif

1135

1136 #if !defined(SQLITE_OMIT_EXPLAIN) && !defined(SQLITE_OMIT_COMPOUND_SELECT)

1137 /*

1138 ** Unless an "EXPLAIN QUERY PLAN" command is being processed, this function

1139 ** is a no-op. Otherwise, it adds a single row of output to the EQP result,

1140 ** where the caption is of one of the two forms:

1141 **

1142 ** "COMPOSITE SUBQUERIES iSub1 and iSub2 (op)"

1143 ** "COMPOSITE SUBQUERIES iSub1 and iSub2 USING TEMP B-TREE (op)"

1144 **

1145 ** where iSub1 and iSub2 are the integers passed as the corresponding

1146 ** function parameters, and op is the text representation of the parameter

1147 ** of the same name. The parameter "op" must be one of TK_UNION, TK_EXCEPT,

1148 ** TK_INTERSECT or TK_ALL. The first form is used if argument bUseTmp is

1149 ** false, or the second form if it is true.

1150 */

1151 static void explainComposite(

1152 Parse pParse, / Parse context */

1153 int op, /* One of TK_UNION, TK_EXCEPT etc. */

1154 int iSub1, /* Subquery id 1 */

1155 int iSub2, /* Subquery id 2 */

1156 int bUseTmp /* True if a temp table was used */

1157 ){

1158 assert( op==TK_UNION \|\| op==TK_EXCEPT \|\| op==TK_INTERSECT \|\| op==TK_ALL );

1159 if( pParse->explain==2 ){

1160 Vdbe *v = pParse->pVdbe;

1161 char *zMsg = sqlite3MPrintf(

1162 pParse->db, "COMPOUND SUBQUERIES %d AND %d %s(%s)", iSub1, iSub2,

1163 bUseTmp?"USING TEMP B-TREE ":"", selectOpName(op)

1164 );

1165 sqlite3VdbeAddOp4(v, OP_Explain, pParse->iSelectId, 0, 0, zMsg, P4_DYNAMIC);

1166 }

1167 }

1168 #else

1169 /* No-op versions of the explainXXX() functions and macros. */

1170 # define explainComposite(v,w,x,y,z)

1171 #endif

1172

1173 /*

1174 ** If the inner loop was generated using a non-null pOrderBy argument,

1175 ** then the results were placed in a sorter. After the loop is terminated

1176 ** we need to run the sorter and output the results. The following

1177 ** routine generates the code needed to do that.

1178 */

1179 static void generateSortTail(

1180 Parse pParse, / Parsing context */

1181 Select p, / The SELECT statement */

1182 SortCtx pSort, / Information on the ORDER BY clause */

1183 int nColumn, /* Number of columns of data */

1184 SelectDest pDest / Write the sorted results here */

1185 ){

1186 Vdbe v = pParse->pVdbe; / The prepared statement */

1187 int addrBreak = pSort->labelDone; /* Jump here to exit loop */

1188 int addrContinue = sqlite3VdbeMakeLabel(v); /* Jump here for next cycle */

1189 int addr;

1190 int addrOnce = 0;

1191 int iTab;

1192 ExprList *pOrderBy = pSort->pOrderBy;

1193 int eDest = pDest->eDest;

1194 int iParm = pDest->iSDParm;

1195 int regRow;

1196 int regRowid;

1197 int nKey;

1198 int iSortTab; /* Sorter cursor to read from */

1199 int nSortData; /* Trailing values to read from sorter */

1200 int i;

1201 int bSeq; /* True if sorter record includes seq. no. */

1202 #ifdef SQLITE_ENABLE_EXPLAIN_COMMENTS

1203 struct ExprList_item *aOutEx = p->pEList->a;

1204 #endif

1205

1206 assert( addrBreak<0 );

1207 if( pSort->labelBkOut ){

1208 sqlite3VdbeAddOp2(v, OP_Gosub, pSort->regReturn, pSort->labelBkOut);

1209 sqlite3VdbeGoto(v, addrBreak);

1210 sqlite3VdbeResolveLabel(v, pSort->labelBkOut);

1211 }

1212 iTab = pSort->iECursor;

1213 if( eDest==SRT_Output \|\| eDest==SRT_Coroutine ){

1214 regRowid = 0;

1215 regRow = pDest->iSdst;

1216 nSortData = nColumn;

1217 }else{

1218 regRowid = sqlite3GetTempReg(pParse);

1219 regRow = sqlite3GetTempReg(pParse);

1220 nSortData = 1;

1221 }

1222 nKey = pOrderBy->nExpr - pSort->nOBSat;

1223 if( pSort->sortFlags & SORTFLAG_UseSorter ){

1224 int regSortOut = ++pParse->nMem;

1225 iSortTab = pParse->nTab++;

1226 if( pSort->labelBkOut ){

1227 addrOnce = sqlite3CodeOnce(pParse); VdbeCoverage(v);

1228 }

1229 sqlite3VdbeAddOp3(v, OP_OpenPseudo, iSortTab, regSortOut, nKey+1+nSortData);

1230 if( addrOnce ) sqlite3VdbeJumpHere(v, addrOnce);

1231 addr = 1 + sqlite3VdbeAddOp2(v, OP_SorterSort, iTab, addrBreak);

1232 VdbeCoverage(v);

1233 codeOffset(v, p->iOffset, addrContinue);

1234 sqlite3VdbeAddOp3(v, OP_SorterData, iTab, regSortOut, iSortTab);

1235 bSeq = 0;

1236 }else{

1237 addr = 1 + sqlite3VdbeAddOp2(v, OP_Sort, iTab, addrBreak); VdbeCoverage(v);

1238 codeOffset(v, p->iOffset, addrContinue);

1239 iSortTab = iTab;

1240 bSeq = 1;

1241 }

1242 for(i=0; i<nSortData; i++){

1243 sqlite3VdbeAddOp3(v, OP_Column, iSortTab, nKey+bSeq+i, regRow+i);

1244 VdbeComment((v, "%s", aOutEx[i].zName ? aOutEx[i].zName : aOutEx[i].zSpan));

1245 }

1246 switch( eDest ){

1247 case SRT_EphemTab: {

1248 sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, regRowid);

1249 sqlite3VdbeAddOp3(v, OP_Insert, iParm, regRow, regRowid);

1250 sqlite3VdbeChangeP5(v, OPFLAG_APPEND);

1251 break;

1252 }

1253 #ifndef SQLITE_OMIT_SUBQUERY

1254 case SRT_Set: {

1255 assert( nColumn==1 );

1256 sqlite3VdbeAddOp4(v, OP_MakeRecord, regRow, 1, regRowid,

1257 &pDest->affSdst, 1);

1258 sqlite3ExprCacheAffinityChange(pParse, regRow, 1);

1259 sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm, regRowid);

1260 break;

1261 }

1262 case SRT_Mem: {

1263 assert( nColumn==1 );

1264 sqlite3ExprCodeMove(pParse, regRow, iParm, 1);

1265 /* The LIMIT clause will terminate the loop for us */

1266 break;

1267 }

1268 #endif

1269 default: {

1270 assert( eDest==SRT_Output \|\| eDest==SRT_Coroutine );

1271 testcase( eDest==SRT_Output );

1272 testcase( eDest==SRT_Coroutine );

1273 if( eDest==SRT_Output ){

1274 sqlite3VdbeAddOp2(v, OP_ResultRow, pDest->iSdst, nColumn);

1275 sqlite3ExprCacheAffinityChange(pParse, pDest->iSdst, nColumn);

1276 }else{

1277 sqlite3VdbeAddOp1(v, OP_Yield, pDest->iSDParm);

1278 }

1279 break;

1280 }

1281 }

1282 if( regRowid ){

1283 sqlite3ReleaseTempReg(pParse, regRow);

1284 sqlite3ReleaseTempReg(pParse, regRowid);

1285 }

1286 /* The bottom of the loop

1287 */

1288 sqlite3VdbeResolveLabel(v, addrContinue);

1289 if( pSort->sortFlags & SORTFLAG_UseSorter ){

1290 sqlite3VdbeAddOp2(v, OP_SorterNext, iTab, addr); VdbeCoverage(v);

1291 }else{

1292 sqlite3VdbeAddOp2(v, OP_Next, iTab, addr); VdbeCoverage(v);

1293 }

1294 if( pSort->regReturn ) sqlite3VdbeAddOp1(v, OP_Return, pSort->regReturn);

1295 sqlite3VdbeResolveLabel(v, addrBreak);

1296 }

1297

1298 /*

1299 ** Return a pointer to a string containing the 'declaration type' of the

1300 ** expression pExpr. The string may be treated as static by the caller.

1301 **

1302 ** Also try to estimate the size of the returned value and return that

1303 ** result in *pEstWidth.

1304 **

1305 ** The declaration type is the exact datatype definition extracted from the

1306 ** original CREATE TABLE statement if the expression is a column. The

1307 ** declaration type for a ROWID field is INTEGER. Exactly when an expression

1308 ** is considered a column can be complex in the presence of subqueries. The

1309 ** result-set expression in all of the following SELECT statements is

1310 ** considered a column by this function.

1311 **

1312 ** SELECT col FROM tbl;

1313 ** SELECT (SELECT col FROM tbl;

1314 ** SELECT (SELECT col FROM tbl);

1315 ** SELECT abc FROM (SELECT col AS abc FROM tbl);

1316 **

1317 ** The declaration type for any expression other than a column is NULL.

1318 **

1319 ** This routine has either 3 or 6 parameters depending on whether or not

1320 ** the SQLITE_ENABLE_COLUMN_METADATA compile-time option is used.

1321 */

1322 #ifdef SQLITE_ENABLE_COLUMN_METADATA

1323 # define columnType(A,B,C,D,E,F) columnTypeImpl(A,B,C,D,E,F)

1324 #else /* if !defined(SQLITE_ENABLE_COLUMN_METADATA) */

1325 # define columnType(A,B,C,D,E,F) columnTypeImpl(A,B,F)

1326 #endif

1327 static const char *columnTypeImpl(

1328 NameContext *pNC,

1329 Expr *pExpr,

1330 #ifdef SQLITE_ENABLE_COLUMN_METADATA

1331 const char **pzOrigDb,

1332 const char **pzOrigTab,

1333 const char **pzOrigCol,

1334 #endif

1335 u8 *pEstWidth

1336 ){

1337 char const *zType = 0;

1338 int j;

1339 u8 estWidth = 1;

1340 #ifdef SQLITE_ENABLE_COLUMN_METADATA

1341 char const *zOrigDb = 0;

1342 char const *zOrigTab = 0;

1343 char const *zOrigCol = 0;

1344 #endif

1345

1346 assert( pExpr!=0 );

1347 assert( pNC->pSrcList!=0 );

1348 switch( pExpr->op ){

1349 case TK_AGG_COLUMN:

1350 case TK_COLUMN: {

1351 /* The expression is a column. Locate the table the column is being

1352 ** extracted from in NameContext.pSrcList. This table may be real

1353 ** database table or a subquery.

1354 */

1355 Table pTab = 0; / Table structure column is extracted from */

1356 Select pS = 0; / Select the column is extracted from */

1357 int iCol = pExpr->iColumn; /* Index of column in pTab */

1358 testcase( pExpr->op==TK_AGG_COLUMN );

1359 testcase( pExpr->op==TK_COLUMN );

1360 while( pNC && !pTab ){

1361 SrcList *pTabList = pNC->pSrcList;

1362 for(j=0;j<pTabList->nSrc && pTabList->a[j].iCursor!=pExpr->iTable;j++);

1363 if( j<pTabList->nSrc ){

1364 pTab = pTabList->a[j].pTab;

1365 pS = pTabList->a[j].pSelect;

1366 }else{

1367 pNC = pNC->pNext;

1368 }

1369 }

1370

1371 if( pTab==0 ){

1372 /* At one time, code such as "SELECT new.x" within a trigger would

1373 ** cause this condition to run. Since then, we have restructured how

1374 ** trigger code is generated and so this condition is no longer

1375 ** possible. However, it can still be true for statements like

1376 ** the following:

1377 **

1378 ** CREATE TABLE t1(col INTEGER);

1379 ** SELECT (SELECT t1.col) FROM FROM t1;

1380 **

1381 ** when columnType() is called on the expression "t1.col" in the

1382 ** sub-select. In this case, set the column type to NULL, even

1383 ** though it should really be "INTEGER".

1384 **

1385 ** This is not a problem, as the column type of "t1.col" is never

1386 ** used. When columnType() is called on the expression

1387 ** "(SELECT t1.col)", the correct type is returned (see the TK_SELECT

1388 ** branch below. */

1389 break;

1390 }

1391

1392 assert( pTab && pExpr->pTab==pTab );

1393 if( pS ){

1394 /* The "table" is actually a sub-select or a view in the FROM clause

1395 ** of the SELECT statement. Return the declaration type and origin

1396 ** data for the result-set column of the sub-select.

1397 */

1398 if( iCol>=0 && ALWAYS(iCol<pS->pEList->nExpr) ){

1399 /* If iCol is less than zero, then the expression requests the

1400 ** rowid of the sub-select or view. This expression is legal (see

1401 ** test case misc2.2.2) - it always evaluates to NULL.

1402 **

1403 ** The ALWAYS() is because iCol>=pS->pEList->nExpr will have been

1404 ** caught already by name resolution.

1405 */

1406 NameContext sNC;

1407 Expr *p = pS->pEList->a[iCol].pExpr;

1408 sNC.pSrcList = pS->pSrc;

1409 sNC.pNext = pNC;

1410 sNC.pParse = pNC->pParse;

1411 zType = columnType(&sNC, p,&zOrigDb,&zOrigTab,&zOrigCol, &estWidth);

1412 }

1413 }else if( pTab->pSchema ){

1414 /* A real table */

1415 assert( !pS );

1416 if( iCol<0 ) iCol = pTab->iPKey;

1417 assert( iCol==-1 \|\| (iCol>=0 && iCol<pTab->nCol) );

1418 #ifdef SQLITE_ENABLE_COLUMN_METADATA

1419 if( iCol<0 ){

1420 zType = "INTEGER";

1421 zOrigCol = "rowid";

1422 }else{

1423 zType = pTab->aCol[iCol].zType;

1424 zOrigCol = pTab->aCol[iCol].zName;

1425 estWidth = pTab->aCol[iCol].szEst;

1426 }

1427 zOrigTab = pTab->zName;

1428 if( pNC->pParse ){

1429 int iDb = sqlite3SchemaToIndex(pNC->pParse->db, pTab->pSchema);

1430 zOrigDb = pNC->pParse->db->aDb[iDb].zName;

1431 }

1432 #else

1433 if( iCol<0 ){

1434 zType = "INTEGER";

1435 }else{

1436 zType = pTab->aCol[iCol].zType;

1437 estWidth = pTab->aCol[iCol].szEst;

1438 }

1439 #endif

1440 }

1441 break;

1442 }

1443 #ifndef SQLITE_OMIT_SUBQUERY

1444 case TK_SELECT: {

1445 /* The expression is a sub-select. Return the declaration type and

1446 ** origin info for the single column in the result set of the SELECT

1447 ** statement.

1448 */

1449 NameContext sNC;

1450 Select *pS = pExpr->x.pSelect;

1451 Expr *p = pS->pEList->a[0].pExpr;

1452 assert( ExprHasProperty(pExpr, EP_xIsSelect) );

1453 sNC.pSrcList = pS->pSrc;

1454 sNC.pNext = pNC;

1455 sNC.pParse = pNC->pParse;

1456 zType = columnType(&sNC, p, &zOrigDb, &zOrigTab, &zOrigCol, &estWidth);

1457 break;

1458 }

1459 #endif

1460 }

1461

1462 #ifdef SQLITE_ENABLE_COLUMN_METADATA

1463 if( pzOrigDb ){

1464 assert( pzOrigTab && pzOrigCol );

1465 *pzOrigDb = zOrigDb;

1466 *pzOrigTab = zOrigTab;

1467 *pzOrigCol = zOrigCol;

1468 }

1469 #endif

1470 if( pEstWidth ) *pEstWidth = estWidth;

1471 return zType;

1472 }

1473

1474 /*

1475 ** Generate code that will tell the VDBE the declaration types of columns

1476 ** in the result set.

1477 */

1478 static void generateColumnTypes(

1479 Parse pParse, / Parser context */

1480 SrcList pTabList, / List of tables */

1481 ExprList pEList / Expressions defining the result set */

1482 ){

1483 #ifndef SQLITE_OMIT_DECLTYPE

1484 Vdbe *v = pParse->pVdbe;

1485 int i;

1486 NameContext sNC;

1487 sNC.pSrcList = pTabList;

1488 sNC.pParse = pParse;

1489 for(i=0; i<pEList->nExpr; i++){

1490 Expr *p = pEList->a[i].pExpr;

1491 const char *zType;

1492 #ifdef SQLITE_ENABLE_COLUMN_METADATA

1493 const char *zOrigDb = 0;

1494 const char *zOrigTab = 0;

1495 const char *zOrigCol = 0;

1496 zType = columnType(&sNC, p, &zOrigDb, &zOrigTab, &zOrigCol, 0);

1497

1498 /* The vdbe must make its own copy of the column-type and other

1499 ** column specific strings, in case the schema is reset before this

1500 ** virtual machine is deleted.

1501 */

1502 sqlite3VdbeSetColName(v, i, COLNAME_DATABASE, zOrigDb, SQLITE_TRANSIENT);

1503 sqlite3VdbeSetColName(v, i, COLNAME_TABLE, zOrigTab, SQLITE_TRANSIENT);

1504 sqlite3VdbeSetColName(v, i, COLNAME_COLUMN, zOrigCol, SQLITE_TRANSIENT);

1505 #else

1506 zType = columnType(&sNC, p, 0, 0, 0, 0);

1507 #endif

1508 sqlite3VdbeSetColName(v, i, COLNAME_DECLTYPE, zType, SQLITE_TRANSIENT);

1509 }

1510 #endif /* !defined(SQLITE_OMIT_DECLTYPE) */

1511 }

1512

1513 /*

1514 ** Generate code that will tell the VDBE the names of columns

1515 ** in the result set. This information is used to provide the

1516 ** azCol[] values in the callback.

1517 */

1518 static void generateColumnNames(

1519 Parse pParse, / Parser context */

1520 SrcList pTabList, / List of tables */

1521 ExprList pEList / Expressions defining the result set */

1522 ){

1523 Vdbe *v = pParse->pVdbe;

1524 int i, j;

1525 sqlite3 *db = pParse->db;

1526 int fullNames, shortNames;

1527

1528 #ifndef SQLITE_OMIT_EXPLAIN

1529 /* If this is an EXPLAIN, skip this step */

1530 if( pParse->explain ){

1531 return;

1532 }

1533 #endif

1534

1535 if( pParse->colNamesSet \|\| db->mallocFailed ) return;

1536 assert( v!=0 );

1537 assert( pTabList!=0 );

1538 pParse->colNamesSet = 1;

1539 fullNames = (db->flags & SQLITE_FullColNames)!=0;

1540 shortNames = (db->flags & SQLITE_ShortColNames)!=0;

1541 sqlite3VdbeSetNumCols(v, pEList->nExpr);

1542 for(i=0; i<pEList->nExpr; i++){

1543 Expr *p;

1544 p = pEList->a[i].pExpr;

1545 if( NEVER(p==0) ) continue;

1546 if( pEList->a[i].zName ){

1547 char *zName = pEList->a[i].zName;

1548 sqlite3VdbeSetColName(v, i, COLNAME_NAME, zName, SQLITE_TRANSIENT);

1549 }else if( p->op==TK_COLUMN \|\| p->op==TK_AGG_COLUMN ){

1550 Table *pTab;

1551 char *zCol;

1552 int iCol = p->iColumn;

1553 for(j=0; ALWAYS(j<pTabList->nSrc); j++){

1554 if( pTabList->a[j].iCursor==p->iTable ) break;

1555 }

1556 assert( j<pTabList->nSrc );

1557 pTab = pTabList->a[j].pTab;

1558 if( iCol<0 ) iCol = pTab->iPKey;

1559 assert( iCol==-1 \|\| (iCol>=0 && iCol<pTab->nCol) );

1560 if( iCol<0 ){

1561 zCol = "rowid";

1562 }else{

1563 zCol = pTab->aCol[iCol].zName;

1564 }

1565 if( !shortNames && !fullNames ){

1566 sqlite3VdbeSetColName(v, i, COLNAME_NAME,

1567 sqlite3DbStrDup(db, pEList->a[i].zSpan), SQLITE_DYNAMIC);

1568 }else if( fullNames ){

1569 char *zName = 0;

1570 zName = sqlite3MPrintf(db, "%s.%s", pTab->zName, zCol);

1571 sqlite3VdbeSetColName(v, i, COLNAME_NAME, zName, SQLITE_DYNAMIC);

1572 }else{

1573 sqlite3VdbeSetColName(v, i, COLNAME_NAME, zCol, SQLITE_TRANSIENT);

1574 }

1575 }else{

1576 const char *z = pEList->a[i].zSpan;

1577 z = z==0 ? sqlite3MPrintf(db, "column%d", i+1) : sqlite3DbStrDup(db, z);

1578 sqlite3VdbeSetColName(v, i, COLNAME_NAME, z, SQLITE_DYNAMIC);

1579 }

1580 }

1581 generateColumnTypes(pParse, pTabList, pEList);

1582 }

1583

1584 /*

1585 ** Given an expression list (which is really the list of expressions

1586 ** that form the result set of a SELECT statement) compute appropriate

1587 ** column names for a table that would hold the expression list.

1588 **

1589 ** All column names will be unique.

1590 **

1591 ** Only the column names are computed. Column.zType, Column.zColl,

1592 ** and other fields of Column are zeroed.

1593 **

1594 ** Return SQLITE_OK on success. If a memory allocation error occurs,

1595 ** store NULL in paCol and 0 in pnCol and return SQLITE_NOMEM.

1596 */

1597 int sqlite3ColumnsFromExprList(

1598 Parse pParse, / Parsing context */

1599 ExprList pEList, / Expr list from which to derive column names */

1600 i16 pnCol, / Write the number of columns here */

1601 Column *paCol / Write the new column list here */

1602 ){

1603 sqlite3 db = pParse->db; / Database connection */

1604 int i, j; /* Loop counters */

1605 u32 cnt; /* Index added to make the name unique */

1606 Column aCol, pCol; /* For looping over result columns */

1607 int nCol; /* Number of columns in the result set */

1608 Expr p; / Expression for a single result column */

1609 char zName; / Column name */

1610 int nName; /* Size of name in zName[] */

1611 Hash ht; /* Hash table of column names */

1612

1613 sqlite3HashInit(&ht);

1614 if( pEList ){

1615 nCol = pEList->nExpr;

1616 aCol = sqlite3DbMallocZero(db, sizeof(aCol[0])*nCol);

1617 testcase( aCol==0 );

1618 }else{

1619 nCol = 0;

1620 aCol = 0;

1621 }

1622 assert( nCol==(i16)nCol );

1623 *pnCol = nCol;

1624 *paCol = aCol;

1625

1626 for(i=0, pCol=aCol; i<nCol && !db->mallocFailed; i++, pCol++){

1627 /* Get an appropriate name for the column

1628 */

1629 p = sqlite3ExprSkipCollate(pEList->a[i].pExpr);

1630 if( (zName = pEList->a[i].zName)!=0 ){

1631 /* If the column contains an "AS <name>" phrase, use <name> as the name */

1632 }else{

1633 Expr pColExpr = p; / The expression that is the result column name */

1634 Table pTab; / Table associated with this expression */

1635 while( pColExpr->op==TK_DOT ){

1636 pColExpr = pColExpr->pRight;

1637 assert( pColExpr!=0 );

1638 }

1639 if( pColExpr->op==TK_COLUMN && ALWAYS(pColExpr->pTab!=0) ){

1640 /* For columns use the column name name */

1641 int iCol = pColExpr->iColumn;

1642 pTab = pColExpr->pTab;

1643 if( iCol<0 ) iCol = pTab->iPKey;

1644 zName = iCol>=0 ? pTab->aCol[iCol].zName : "rowid";

1645 }else if( pColExpr->op==TK_ID ){

1646 assert( !ExprHasProperty(pColExpr, EP_IntValue) );

1647 zName = pColExpr->u.zToken;

1648 }else{

1649 /* Use the original text of the column expression as its name */

1650 zName = pEList->a[i].zSpan;

1651 }

1652 }

1653 zName = sqlite3MPrintf(db, "%s", zName);

1654

1655 /* Make sure the column name is unique. If the name is not unique,

1656 ** append an integer to the name so that it becomes unique.

1657 */

1658 cnt = 0;

1659 while( zName && sqlite3HashFind(&ht, zName)!=0 ){

1660 nName = sqlite3Strlen30(zName);

1661 if( nName>0 ){

1662 for(j=nName-1; j>0 && sqlite3Isdigit(zName[j]); j--){}

1663 if( zName[j]==':' ) nName = j;

1664 }

1665 zName = sqlite3MPrintf(db, "%.*z:%u", nName, zName, ++cnt);

1666 if( cnt>3 ) sqlite3_randomness(sizeof(cnt), &cnt);

1667 }

1668 pCol->zName = zName;

1669 sqlite3ColumnPropertiesFromName(0, pCol);

1670 if( zName && sqlite3HashInsert(&ht, zName, pCol)==pCol ){

1671 db->mallocFailed = 1;

1672 }

1673 }

1674 sqlite3HashClear(&ht);

1675 if( db->mallocFailed ){

1676 for(j=0; j<i; j++){

1677 sqlite3DbFree(db, aCol[j].zName);

1678 }

1679 sqlite3DbFree(db, aCol);

1680 *paCol = 0;

1681 *pnCol = 0;

1682 return SQLITE_NOMEM;

1683 }

1684 return SQLITE_OK;

1685 }

1686

1687 /*

1688 ** Add type and collation information to a column list based on

1689 ** a SELECT statement.

1690 **

1691 ** The column list presumably came from selectColumnNamesFromExprList().

1692 ** The column list has only names, not types or collations. This

1693 ** routine goes through and adds the types and collations.

1694 **

1695 ** This routine requires that all identifiers in the SELECT

1696 ** statement be resolved.

1697 */

1698 static void selectAddColumnTypeAndCollation(

1699 Parse pParse, / Parsing contexts */

1700 Table pTab, / Add column type information to this table */

1701 Select pSelect / SELECT used to determine types and collations */

1702 ){

1703 sqlite3 *db = pParse->db;

1704 NameContext sNC;

1705 Column *pCol;

1706 CollSeq *pColl;

1707 int i;

1708 Expr *p;

1709 struct ExprList_item *a;

1710 u64 szAll = 0;

1711

1712 assert( pSelect!=0 );

1713 assert( (pSelect->selFlags & SF_Resolved)!=0 );

1714 assert( pTab->nCol==pSelect->pEList->nExpr \|\| db->mallocFailed );

1715 if( db->mallocFailed ) return;

1716 memset(&sNC, 0, sizeof(sNC));

1717 sNC.pSrcList = pSelect->pSrc;

1718 a = pSelect->pEList->a;

1719 for(i=0, pCol=pTab->aCol; i<pTab->nCol; i++, pCol++){

1720 p = a[i].pExpr;

1721 if( pCol->zType==0 ){

1722 pCol->zType = sqlite3DbStrDup(db,

1723 columnType(&sNC, p,0,0,0, &pCol->szEst));

1724 }

1725 szAll += pCol->szEst;

1726 pCol->affinity = sqlite3ExprAffinity(p);

1727 if( pCol->affinity==0 ) pCol->affinity = SQLITE_AFF_BLOB;

1728 pColl = sqlite3ExprCollSeq(pParse, p);

1729 if( pColl && pCol->zColl==0 ){

1730 pCol->zColl = sqlite3DbStrDup(db, pColl->zName);

1731 }

1732 }

1733 pTab->szTabRow = sqlite3LogEst(szAll*4);

1734 }

1735

1736 /*

1737 ** Given a SELECT statement, generate a Table structure that describes

1738 ** the result set of that SELECT.

1739 */

1740 Table sqlite3ResultSetOfSelect(Parse pParse, Select *pSelect){

1741 Table *pTab;

1742 sqlite3 *db = pParse->db;

1743 int savedFlags;

1744

1745 savedFlags = db->flags;

1746 db->flags &= ~SQLITE_FullColNames;

1747 db->flags \|= SQLITE_ShortColNames;

1748 sqlite3SelectPrep(pParse, pSelect, 0);

1749 if( pParse->nErr ) return 0;

1750 while( pSelect->pPrior ) pSelect = pSelect->pPrior;

1751 db->flags = savedFlags;

1752 pTab = sqlite3DbMallocZero(db, sizeof(Table) );

1753 if( pTab==0 ){

1754 return 0;

1755 }

1756 /* The sqlite3ResultSetOfSelect() is only used n contexts where lookaside

1757 ** is disabled */

1758 assert( db->lookaside.bEnabled==0 );

1759 pTab->nRef = 1;

1760 pTab->zName = 0;

1761 pTab->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) );

1762 sqlite3ColumnsFromExprList(pParse, pSelect->pEList, &pTab->nCol, &pTab->aCol);

1763 selectAddColumnTypeAndCollation(pParse, pTab, pSelect);

1764 pTab->iPKey = -1;

1765 if( db->mallocFailed ){

1766 sqlite3DeleteTable(db, pTab);

1767 return 0;

1768 }

1769 return pTab;

1770 }

1771

1772 /*

1773 ** Get a VDBE for the given parser context. Create a new one if necessary.

1774 ** If an error occurs, return NULL and leave a message in pParse.

1775 */

1776 Vdbe sqlite3GetVdbe(Parse pParse){

1777 Vdbe *v = pParse->pVdbe;

1778 if( v==0 ){

1779 v = pParse->pVdbe = sqlite3VdbeCreate(pParse);

1780 if( v ) sqlite3VdbeAddOp0(v, OP_Init);

1781 if( pParse->pToplevel==0

1782 && OptimizationEnabled(pParse->db,SQLITE_FactorOutConst)

1783 ){

1784 pParse->okConstFactor = 1;

1785 }

1786

1787 }

1788 return v;

1789 }

1790

1791

1792 /*

1793 ** Compute the iLimit and iOffset fields of the SELECT based on the

1794 ** pLimit and pOffset expressions. pLimit and pOffset hold the expressions

1795 ** that appear in the original SQL statement after the LIMIT and OFFSET

1796 ** keywords. Or NULL if those keywords are omitted. iLimit and iOffset

1797 ** are the integer memory register numbers for counters used to compute

1798 ** the limit and offset. If there is no limit and/or offset, then

1799 ** iLimit and iOffset are negative.

1800 **

1801 ** This routine changes the values of iLimit and iOffset only if

1802 ** a limit or offset is defined by pLimit and pOffset. iLimit and

1803 ** iOffset should have been preset to appropriate default values (zero)

1804 ** prior to calling this routine.

1805 **

1806 ** The iOffset register (if it exists) is initialized to the value

1807 ** of the OFFSET. The iLimit register is initialized to LIMIT. Register

1808 ** iOffset+1 is initialized to LIMIT+OFFSET.

1809 **

1810 ** Only if pLimit!=0 or pOffset!=0 do the limit registers get

1811 ** redefined. The UNION ALL operator uses this property to force

1812 ** the reuse of the same limit and offset registers across multiple

1813 ** SELECT statements.

1814 */

1815 static void computeLimitRegisters(Parse pParse, Select p, int iBreak){

1816 Vdbe *v = 0;

1817 int iLimit = 0;

1818 int iOffset;

1819 int n;

1820 if( p->iLimit ) return;

1821

1822 /*

1823 ** "LIMIT -1" always shows all rows. There is some

1824 ** controversy about what the correct behavior should be.

1825 ** The current implementation interprets "LIMIT 0" to mean

1826 ** no rows.

1827 */

1828 sqlite3ExprCacheClear(pParse);

1829 assert( p->pOffset==0 \|\| p->pLimit!=0 );

1830 if( p->pLimit ){

1831 p->iLimit = iLimit = ++pParse->nMem;

1832 v = sqlite3GetVdbe(pParse);

1833 assert( v!=0 );

1834 if( sqlite3ExprIsInteger(p->pLimit, &n) ){

1835 sqlite3VdbeAddOp2(v, OP_Integer, n, iLimit);

1836 VdbeComment((v, "LIMIT counter"));

1837 if( n==0 ){

1838 sqlite3VdbeGoto(v, iBreak);

1839 }else if( n>=0 && p->nSelectRow>(u64)n ){

1840 p->nSelectRow = n;

1841 }

1842 }else{

1843 sqlite3ExprCode(pParse, p->pLimit, iLimit);

1844 sqlite3VdbeAddOp1(v, OP_MustBeInt, iLimit); VdbeCoverage(v);

1845 VdbeComment((v, "LIMIT counter"));

1846 sqlite3VdbeAddOp2(v, OP_IfNot, iLimit, iBreak); VdbeCoverage(v);

1847 }

1848 if( p->pOffset ){

1849 p->iOffset = iOffset = ++pParse->nMem;

1850 pParse->nMem++; /* Allocate an extra register for limit+offset */

1851 sqlite3ExprCode(pParse, p->pOffset, iOffset);

1852 sqlite3VdbeAddOp1(v, OP_MustBeInt, iOffset); VdbeCoverage(v);

1853 VdbeComment((v, "OFFSET counter"));

1854 sqlite3VdbeAddOp3(v, OP_SetIfNotPos, iOffset, iOffset, 0);

1855 sqlite3VdbeAddOp3(v, OP_Add, iLimit, iOffset, iOffset+1);

1856 VdbeComment((v, "LIMIT+OFFSET"));

1857 sqlite3VdbeAddOp3(v, OP_SetIfNotPos, iLimit, iOffset+1, -1);

1858 }

1859 }

1860 }

1861

1862 #ifndef SQLITE_OMIT_COMPOUND_SELECT

1863 /*

1864 ** Return the appropriate collating sequence for the iCol-th column of

1865 ** the result set for the compound-select statement "p". Return NULL if

1866 ** the column has no default collating sequence.

1867 **

1868 ** The collating sequence for the compound select is taken from the

1869 ** left-most term of the select that has a collating sequence.

1870 */

1871 static CollSeq multiSelectCollSeq(Parse pParse, Select *p, int iCol){

1872 CollSeq *pRet;

1873 if( p->pPrior ){

1874 pRet = multiSelectCollSeq(pParse, p->pPrior, iCol);

1875 }else{

1876 pRet = 0;

1877 }

1878 assert( iCol>=0 );

1879 /* iCol must be less than p->pEList->nExpr. Otherwise an error would

1880 ** have been thrown during name resolution and we would not have gotten

1881 ** this far */

1882 if( pRet==0 && ALWAYS(iCol<p->pEList->nExpr) ){

1883 pRet = sqlite3ExprCollSeq(pParse, p->pEList->a[iCol].pExpr);

1884 }

1885 return pRet;

1886 }

1887

1888 /*

1889 ** The select statement passed as the second parameter is a compound SELECT

1890 ** with an ORDER BY clause. This function allocates and returns a KeyInfo

1891 ** structure suitable for implementing the ORDER BY.

1892 **

1893 ** Space to hold the KeyInfo structure is obtained from malloc. The calling

1894 ** function is responsible for ensuring that this structure is eventually

1895 ** freed.

1896 */

1897 static KeyInfo multiSelectOrderByKeyInfo(Parse pParse, Select *p, int nExtra){

1898 ExprList *pOrderBy = p->pOrderBy;

1899 int nOrderBy = p->pOrderBy->nExpr;

1900 sqlite3 *db = pParse->db;

1901 KeyInfo *pRet = sqlite3KeyInfoAlloc(db, nOrderBy+nExtra, 1);

1902 if( pRet ){

1903 int i;

1904 for(i=0; i<nOrderBy; i++){

1905 struct ExprList_item *pItem = &pOrderBy->a[i];

1906 Expr *pTerm = pItem->pExpr;

1907 CollSeq *pColl;

1908

1909 if( pTerm->flags & EP_Collate ){

1910 pColl = sqlite3ExprCollSeq(pParse, pTerm);

1911 }else{

1912 pColl = multiSelectCollSeq(pParse, p, pItem->u.x.iOrderByCol-1);

1913 if( pColl==0 ) pColl = db->pDfltColl;

1914 pOrderBy->a[i].pExpr =

1915 sqlite3ExprAddCollateString(pParse, pTerm, pColl->zName);

1916 }

1917 assert( sqlite3KeyInfoIsWriteable(pRet) );

1918 pRet->aColl[i] = pColl;

1919 pRet->aSortOrder[i] = pOrderBy->a[i].sortOrder;

1920 }

1921 }

1922

1923 return pRet;

1924 }

1925

1926 #ifndef SQLITE_OMIT_CTE

1927 /*

1928 ** This routine generates VDBE code to compute the content of a WITH RECURSIVE

1929 ** query of the form:

1930 **

1931 ** <recursive-table> AS (<setup-query> UNION [ALL] <recursive-query>)

1932 ** \___________/ \_______________/

1933 ** p->pPrior p

1934 **

1935 **

1936 ** There is exactly one reference to the recursive-table in the FROM clause

1937 ** of recursive-query, marked with the SrcList->a[].fg.isRecursive flag.

1938 **

1939 ** The setup-query runs once to generate an initial set of rows that go

1940 ** into a Queue table. Rows are extracted from the Queue table one by

1941 ** one. Each row extracted from Queue is output to pDest. Then the single

1942 ** extracted row (now in the iCurrent table) becomes the content of the

1943 ** recursive-table for a recursive-query run. The output of the recursive-query

1944 ** is added back into the Queue table. Then another row is extracted from Queue

1945 ** and the iteration continues until the Queue table is empty.

1946 **

1947 ** If the compound query operator is UNION then no duplicate rows are ever

1948 ** inserted into the Queue table. The iDistinct table keeps a copy of all rows

1949 ** that have ever been inserted into Queue and causes duplicates to be

1950 ** discarded. If the operator is UNION ALL, then duplicates are allowed.

1951 **

1952 ** If the query has an ORDER BY, then entries in the Queue table are kept in

1953 ** ORDER BY order and the first entry is extracted for each cycle. Without

1954 ** an ORDER BY, the Queue table is just a FIFO.

1955 **

1956 ** If a LIMIT clause is provided, then the iteration stops after LIMIT rows

1957 ** have been output to pDest. A LIMIT of zero means to output no rows and a

1958 ** negative LIMIT means to output all rows. If there is also an OFFSET clause

1959 ** with a positive value, then the first OFFSET outputs are discarded rather

1960 ** than being sent to pDest. The LIMIT count does not begin until after OFFSET

1961 ** rows have been skipped.

1962 */

1963 static void generateWithRecursiveQuery(

1964 Parse pParse, / Parsing context */

1965 Select p, / The recursive SELECT to be coded */

1966 SelectDest pDest / What to do with query results */

1967 ){

1968 SrcList pSrc = p->pSrc; / The FROM clause of the recursive query */

1969 int nCol = p->pEList->nExpr; /* Number of columns in the recursive table */

1970 Vdbe v = pParse->pVdbe; / The prepared statement under construction */

1971 Select pSetup = p->pPrior; / The setup query */

1972 int addrTop; /* Top of the loop */

1973 int addrCont, addrBreak; /* CONTINUE and BREAK addresses */

1974 int iCurrent = 0; /* The Current table */

1975 int regCurrent; /* Register holding Current table */

1976 int iQueue; /* The Queue table */

1977 int iDistinct = 0; /* To ensure unique results if UNION */

1978 int eDest = SRT_Fifo; /* How to write to Queue */

1979 SelectDest destQueue; /* SelectDest targetting the Queue table */

1980 int i; /* Loop counter */

1981 int rc; /* Result code */

1982 ExprList pOrderBy; / The ORDER BY clause */

1983 Expr pLimit, pOffset; /* Saved LIMIT and OFFSET */

1984 int regLimit, regOffset; /* Registers used by LIMIT and OFFSET */

1985

1986 /* Obtain authorization to do a recursive query */

1987 if( sqlite3AuthCheck(pParse, SQLITE_RECURSIVE, 0, 0, 0) ) return;

1988

1989 /* Process the LIMIT and OFFSET clauses, if they exist */

1990 addrBreak = sqlite3VdbeMakeLabel(v);

1991 computeLimitRegisters(pParse, p, addrBreak);

1992 pLimit = p->pLimit;

1993 pOffset = p->pOffset;

1994 regLimit = p->iLimit;

1995 regOffset = p->iOffset;

1996 p->pLimit = p->pOffset = 0;

1997 p->iLimit = p->iOffset = 0;

1998 pOrderBy = p->pOrderBy;

1999

2000 /* Locate the cursor number of the Current table */

2001 for(i=0; ALWAYS(i<pSrc->nSrc); i++){

2002 if( pSrc->a[i].fg.isRecursive ){

2003 iCurrent = pSrc->a[i].iCursor;

2004 break;

2005 }

2006 }

2007

2008 /* Allocate cursors numbers for Queue and Distinct. The cursor number for

2009 ** the Distinct table must be exactly one greater than Queue in order

2010 ** for the SRT_DistFifo and SRT_DistQueue destinations to work. */

2011 iQueue = pParse->nTab++;

2012 if( p->op==TK_UNION ){

2013 eDest = pOrderBy ? SRT_DistQueue : SRT_DistFifo;

2014 iDistinct = pParse->nTab++;

2015 }else{

2016 eDest = pOrderBy ? SRT_Queue : SRT_Fifo;

2017 }

2018 sqlite3SelectDestInit(&destQueue, eDest, iQueue);

2019

2020 /* Allocate cursors for Current, Queue, and Distinct. */

2021 regCurrent = ++pParse->nMem;

2022 sqlite3VdbeAddOp3(v, OP_OpenPseudo, iCurrent, regCurrent, nCol);

2023 if( pOrderBy ){

2024 KeyInfo *pKeyInfo = multiSelectOrderByKeyInfo(pParse, p, 1);

2025 sqlite3VdbeAddOp4(v, OP_OpenEphemeral, iQueue, pOrderBy->nExpr+2, 0,

2026 (char*)pKeyInfo, P4_KEYINFO);

2027 destQueue.pOrderBy = pOrderBy;

2028 }else{

2029 sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iQueue, nCol);

2030 }

2031 VdbeComment((v, "Queue table"));

2032 if( iDistinct ){

2033 p->addrOpenEphm[0] = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iDistinct, 0);

2034 p->selFlags \|= SF_UsesEphemeral;

2035 }

2036

2037 /* Detach the ORDER BY clause from the compound SELECT */

2038 p->pOrderBy = 0;

2039

2040 /* Store the results of the setup-query in Queue. */

2041 pSetup->pNext = 0;

2042 rc = sqlite3Select(pParse, pSetup, &destQueue);

2043 pSetup->pNext = p;

2044 if( rc ) goto end_of_recursive_query;

2045

2046 /* Find the next row in the Queue and output that row */

2047 addrTop = sqlite3VdbeAddOp2(v, OP_Rewind, iQueue, addrBreak); VdbeCoverage(v);

2048

2049 /* Transfer the next row in Queue over to Current */

2050 sqlite3VdbeAddOp1(v, OP_NullRow, iCurrent); /* To reset column cache */

2051 if( pOrderBy ){

2052 sqlite3VdbeAddOp3(v, OP_Column, iQueue, pOrderBy->nExpr+1, regCurrent);

2053 }else{

2054 sqlite3VdbeAddOp2(v, OP_RowData, iQueue, regCurrent);

2055 }

2056 sqlite3VdbeAddOp1(v, OP_Delete, iQueue);

2057

2058 /* Output the single row in Current */

2059 addrCont = sqlite3VdbeMakeLabel(v);

2060 codeOffset(v, regOffset, addrCont);

2061 selectInnerLoop(pParse, p, p->pEList, iCurrent,

2062 0, 0, pDest, addrCont, addrBreak);

2063 if( regLimit ){

2064 sqlite3VdbeAddOp2(v, OP_DecrJumpZero, regLimit, addrBreak);

2065 VdbeCoverage(v);

2066 }

2067 sqlite3VdbeResolveLabel(v, addrCont);

2068

2069 /* Execute the recursive SELECT taking the single row in Current as

2070 ** the value for the recursive-table. Store the results in the Queue.

2071 */

2072 if( p->selFlags & SF_Aggregate ){

2073 sqlite3ErrorMsg(pParse, "recursive aggregate queries not supported");

2074 }else{

2075 p->pPrior = 0;

2076 sqlite3Select(pParse, p, &destQueue);

2077 assert( p->pPrior==0 );

2078 p->pPrior = pSetup;

2079 }

2080

2081 /* Keep running the loop until the Queue is empty */

2082 sqlite3VdbeGoto(v, addrTop);

2083 sqlite3VdbeResolveLabel(v, addrBreak);

2084

2085 end_of_recursive_query:

2086 sqlite3ExprListDelete(pParse->db, p->pOrderBy);

2087 p->pOrderBy = pOrderBy;

2088 p->pLimit = pLimit;

2089 p->pOffset = pOffset;

2090 return;

2091 }

2092 #endif /* SQLITE_OMIT_CTE */

2093

2094 /* Forward references */

2095 static int multiSelectOrderBy(

2096 Parse pParse, / Parsing context */

2097 Select p, / The right-most of SELECTs to be coded */

2098 SelectDest pDest / What to do with query results */

2099 );

2100

2101 /*

2102 ** Handle the special case of a compound-select that originates from a

2103 ** VALUES clause. By handling this as a special case, we avoid deep

2104 ** recursion, and thus do not need to enforce the SQLITE_LIMIT_COMPOUND_SELECT

2105 ** on a VALUES clause.

2106 **

2107 ** Because the Select object originates from a VALUES clause:

2108 ** (1) It has no LIMIT or OFFSET

2109 ** (2) All terms are UNION ALL

2110 ** (3) There is no ORDER BY clause

2111 */

2112 static int multiSelectValues(

2113 Parse pParse, / Parsing context */

2114 Select p, / The right-most of SELECTs to be coded */

2115 SelectDest pDest / What to do with query results */

2116 ){

2117 Select *pPrior;

2118 int nRow = 1;

2119 int rc = 0;

2120 assert( p->selFlags & SF_MultiValue );

2121 do{

2122 assert( p->selFlags & SF_Values );

2123 assert( p->op==TK_ALL \|\| (p->op==TK_SELECT && p->pPrior==0) );

2124 assert( p->pLimit==0 );

2125 assert( p->pOffset==0 );

2126 assert( p->pNext==0 \|\| p->pEList->nExpr==p->pNext->pEList->nExpr );

2127 if( p->pPrior==0 ) break;

2128 assert( p->pPrior->pNext==p );

2129 p = p->pPrior;

2130 nRow++;

2131 }while(1);

2132 while( p ){

2133 pPrior = p->pPrior;

2134 p->pPrior = 0;

2135 rc = sqlite3Select(pParse, p, pDest);

2136 p->pPrior = pPrior;

2137 if( rc ) break;

2138 p->nSelectRow = nRow;

2139 p = p->pNext;

2140 }

2141 return rc;

2142 }

2143

2144 /*

2145 ** This routine is called to process a compound query form from

2146 ** two or more separate queries using UNION, UNION ALL, EXCEPT, or

2147 ** INTERSECT

2148 **

2149 ** "p" points to the right-most of the two queries. the query on the

2150 ** left is p->pPrior. The left query could also be a compound query

2151 ** in which case this routine will be called recursively.

2152 **

2153 ** The results of the total query are to be written into a destination

2154 ** of type eDest with parameter iParm.

2155 **

2156 ** Example 1: Consider a three-way compound SQL statement.

2157 **

2158 ** SELECT a FROM t1 UNION SELECT b FROM t2 UNION SELECT c FROM t3

2159 **

2160 ** This statement is parsed up as follows:

2161 **

2162 ** SELECT c FROM t3

2163 ** \|

2164 ** `-----> SELECT b FROM t2

2165 ** \|

2166 ** `------> SELECT a FROM t1

2167 **

2168 ** The arrows in the diagram above represent the Select.pPrior pointer.

2169 ** So if this routine is called with p equal to the t3 query, then

2170 ** pPrior will be the t2 query. p->op will be TK_UNION in this case.

2171 **

2172 ** Notice that because of the way SQLite parses compound SELECTs, the

2173 ** individual selects always group from left to right.

2174 */

2175 static int multiSelect(

2176 Parse pParse, / Parsing context */

2177 Select p, / The right-most of SELECTs to be coded */

2178 SelectDest pDest / What to do with query results */

2179 ){

2180 int rc = SQLITE_OK; /* Success code from a subroutine */

2181 Select pPrior; / Another SELECT immediately to our left */

2182 Vdbe v; / Generate code to this VDBE */

2183 SelectDest dest; /* Alternative data destination */

2184 Select pDelete = 0; / Chain of simple selects to delete */

2185 sqlite3 db; / Database connection */

2186 #ifndef SQLITE_OMIT_EXPLAIN

2187 int iSub1 = 0; /* EQP id of left-hand query */

2188 int iSub2 = 0; /* EQP id of right-hand query */

2189 #endif

2190

2191 /* Make sure there is no ORDER BY or LIMIT clause on prior SELECTs. Only

2192 ** the last (right-most) SELECT in the series may have an ORDER BY or LIMIT.

2193 */

2194 assert( p && p->pPrior ); /* Calling function guarantees this much */

2195 assert( (p->selFlags & SF_Recursive)==0 \|\| p->op==TK_ALL \|\| p->op==TK_UNION );

2196 db = pParse->db;

2197 pPrior = p->pPrior;

2198 dest = *pDest;

2199 if( pPrior->pOrderBy ){

2200 sqlite3ErrorMsg(pParse,"ORDER BY clause should come after %s not before",

2201 selectOpName(p->op));

2202 rc = 1;

2203 goto multi_select_end;

2204 }

2205 if( pPrior->pLimit ){

2206 sqlite3ErrorMsg(pParse,"LIMIT clause should come after %s not before",

2207 selectOpName(p->op));

2208 rc = 1;

2209 goto multi_select_end;

2210 }

2211

2212 v = sqlite3GetVdbe(pParse);

2213 assert( v!=0 ); /* The VDBE already created by calling function */

2214

2215 /* Create the destination temporary table if necessary

2216 */

2217 if( dest.eDest==SRT_EphemTab ){

2218 assert( p->pEList );

2219 sqlite3VdbeAddOp2(v, OP_OpenEphemeral, dest.iSDParm, p->pEList->nExpr);

2220 sqlite3VdbeChangeP5(v, BTREE_UNORDERED);

2221 dest.eDest = SRT_Table;

2222 }

2223

2224 /* Special handling for a compound-select that originates as a VALUES clause.

2225 */

2226 if( p->selFlags & SF_MultiValue ){

2227 rc = multiSelectValues(pParse, p, &dest);

2228 goto multi_select_end;

2229 }

2230

2231 /* Make sure all SELECTs in the statement have the same number of elements

2232 ** in their result sets.

2233 */

2234 assert( p->pEList && pPrior->pEList );

2235 assert( p->pEList->nExpr==pPrior->pEList->nExpr );

2236

2237 #ifndef SQLITE_OMIT_CTE

2238 if( p->selFlags & SF_Recursive ){

2239 generateWithRecursiveQuery(pParse, p, &dest);

2240 }else

2241 #endif

2242

2243 /* Compound SELECTs that have an ORDER BY clause are handled separately.

2244 */

2245 if( p->pOrderBy ){

2246 return multiSelectOrderBy(pParse, p, pDest);

2247 }else

2248

2249 /* Generate code for the left and right SELECT statements.

2250 */

2251 switch( p->op ){

2252 case TK_ALL: {

2253 int addr = 0;

2254 int nLimit;

2255 assert( !pPrior->pLimit );

2256 pPrior->iLimit = p->iLimit;

2257 pPrior->iOffset = p->iOffset;

2258 pPrior->pLimit = p->pLimit;

2259 pPrior->pOffset = p->pOffset;

2260 explainSetInteger(iSub1, pParse->iNextSelectId);

2261 rc = sqlite3Select(pParse, pPrior, &dest);

2262 p->pLimit = 0;

2263 p->pOffset = 0;

2264 if( rc ){

2265 goto multi_select_end;

2266 }

2267 p->pPrior = 0;

2268 p->iLimit = pPrior->iLimit;

2269 p->iOffset = pPrior->iOffset;

2270 if( p->iLimit ){

2271 addr = sqlite3VdbeAddOp1(v, OP_IfNot, p->iLimit); VdbeCoverage(v);

2272 VdbeComment((v, "Jump ahead if LIMIT reached"));

2273 if( p->iOffset ){

2274 sqlite3VdbeAddOp3(v, OP_SetIfNotPos, p->iOffset, p->iOffset, 0);

2275 sqlite3VdbeAddOp3(v, OP_Add, p->iLimit, p->iOffset, p->iOffset+1);

2276 sqlite3VdbeAddOp3(v, OP_SetIfNotPos, p->iLimit, p->iOffset+1, -1);

2277 }

2278 }

2279 explainSetInteger(iSub2, pParse->iNextSelectId);

2280 rc = sqlite3Select(pParse, p, &dest);

2281 testcase( rc!=SQLITE_OK );

2282 pDelete = p->pPrior;

2283 p->pPrior = pPrior;

2284 p->nSelectRow += pPrior->nSelectRow;

2285 if( pPrior->pLimit

2286 && sqlite3ExprIsInteger(pPrior->pLimit, &nLimit)

2287 && nLimit>0 && p->nSelectRow > (u64)nLimit

2288 ){

2289 p->nSelectRow = nLimit;

2290 }

2291 if( addr ){

2292 sqlite3VdbeJumpHere(v, addr);

2293 }

2294 break;

2295 }

2296 case TK_EXCEPT:

2297 case TK_UNION: {

2298 int unionTab; /* Cursor number of the temporary table holding result */

2299 u8 op = 0; /* One of the SRT_ operations to apply to self */

2300 int priorOp; /* The SRT_ operation to apply to prior selects */

2301 Expr pLimit, pOffset; /* Saved values of p->nLimit and p->nOffset */

2302 int addr;

2303 SelectDest uniondest;

2304

2305 testcase( p->op==TK_EXCEPT );

2306 testcase( p->op==TK_UNION );

2307 priorOp = SRT_Union;

2308 if( dest.eDest==priorOp ){

2309 /* We can reuse a temporary table generated by a SELECT to our

2310 ** right.

2311 */

2312 assert( p->pLimit==0 ); /* Not allowed on leftward elements */

2313 assert( p->pOffset==0 ); /* Not allowed on leftward elements */

2314 unionTab = dest.iSDParm;

2315 }else{

2316 /* We will need to create our own temporary table to hold the

2317 ** intermediate results.

2318 */

2319 unionTab = pParse->nTab++;

2320 assert( p->pOrderBy==0 );

2321 addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, unionTab, 0);

2322 assert( p->addrOpenEphm[0] == -1 );

2323 p->addrOpenEphm[0] = addr;

2324 findRightmost(p)->selFlags \|= SF_UsesEphemeral;

2325 assert( p->pEList );

2326 }

2327

2328 /* Code the SELECT statements to our left

2329 */

2330 assert( !pPrior->pOrderBy );

2331 sqlite3SelectDestInit(&uniondest, priorOp, unionTab);

2332 explainSetInteger(iSub1, pParse->iNextSelectId);

2333 rc = sqlite3Select(pParse, pPrior, &uniondest);

2334 if( rc ){

2335 goto multi_select_end;

2336 }

2337

2338 /* Code the current SELECT statement

2339 */

2340 if( p->op==TK_EXCEPT ){

2341 op = SRT_Except;

2342 }else{

2343 assert( p->op==TK_UNION );

2344 op = SRT_Union;

2345 }

2346 p->pPrior = 0;

2347 pLimit = p->pLimit;

2348 p->pLimit = 0;

2349 pOffset = p->pOffset;

2350 p->pOffset = 0;

2351 uniondest.eDest = op;

2352 explainSetInteger(iSub2, pParse->iNextSelectId);

2353 rc = sqlite3Select(pParse, p, &uniondest);

2354 testcase( rc!=SQLITE_OK );

2355 /* Query flattening in sqlite3Select() might refill p->pOrderBy.

2356 ** Be sure to delete p->pOrderBy, therefore, to avoid a memory leak. */

2357 sqlite3ExprListDelete(db, p->pOrderBy);

2358 pDelete = p->pPrior;

2359 p->pPrior = pPrior;

2360 p->pOrderBy = 0;

2361 if( p->op==TK_UNION ) p->nSelectRow += pPrior->nSelectRow;

2362 sqlite3ExprDelete(db, p->pLimit);

2363 p->pLimit = pLimit;

2364 p->pOffset = pOffset;

2365 p->iLimit = 0;

2366 p->iOffset = 0;

2367

2368 /* Convert the data in the temporary table into whatever form

2369 ** it is that we currently need.

2370 */

2371 assert( unionTab==dest.iSDParm \|\| dest.eDest!=priorOp );

2372 if( dest.eDest!=priorOp ){

2373 int iCont, iBreak, iStart;

2374 assert( p->pEList );

2375 if( dest.eDest==SRT_Output ){

2376 Select *pFirst = p;

2377 while( pFirst->pPrior ) pFirst = pFirst->pPrior;

2378 generateColumnNames(pParse, pFirst->pSrc, pFirst->pEList);

2379 }

2380 iBreak = sqlite3VdbeMakeLabel(v);

2381 iCont = sqlite3VdbeMakeLabel(v);

2382 computeLimitRegisters(pParse, p, iBreak);

2383 sqlite3VdbeAddOp2(v, OP_Rewind, unionTab, iBreak); VdbeCoverage(v);

2384 iStart = sqlite3VdbeCurrentAddr(v);

2385 selectInnerLoop(pParse, p, p->pEList, unionTab,

2386 0, 0, &dest, iCont, iBreak);

2387 sqlite3VdbeResolveLabel(v, iCont);

2388 sqlite3VdbeAddOp2(v, OP_Next, unionTab, iStart); VdbeCoverage(v);

2389 sqlite3VdbeResolveLabel(v, iBreak);

2390 sqlite3VdbeAddOp2(v, OP_Close, unionTab, 0);

2391 }

2392 break;

2393 }

2394 default: assert( p->op==TK_INTERSECT ); {

2395 int tab1, tab2;

2396 int iCont, iBreak, iStart;

2397 Expr pLimit, pOffset;

2398 int addr;

2399 SelectDest intersectdest;

2400 int r1;

2401

2402 /* INTERSECT is different from the others since it requires

2403 ** two temporary tables. Hence it has its own case. Begin

2404 ** by allocating the tables we will need.

2405 */

2406 tab1 = pParse->nTab++;

2407 tab2 = pParse->nTab++;

2408 assert( p->pOrderBy==0 );

2409

2410 addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, tab1, 0);

2411 assert( p->addrOpenEphm[0] == -1 );

2412 p->addrOpenEphm[0] = addr;

2413 findRightmost(p)->selFlags \|= SF_UsesEphemeral;

2414 assert( p->pEList );

2415

2416 /* Code the SELECTs to our left into temporary table "tab1".

2417 */

2418 sqlite3SelectDestInit(&intersectdest, SRT_Union, tab1);

2419 explainSetInteger(iSub1, pParse->iNextSelectId);

2420 rc = sqlite3Select(pParse, pPrior, &intersectdest);

2421 if( rc ){

2422 goto multi_select_end;

2423 }

2424

2425 /* Code the current SELECT into temporary table "tab2"

2426 */

2427 addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, tab2, 0);

2428 assert( p->addrOpenEphm[1] == -1 );

2429 p->addrOpenEphm[1] = addr;

2430 p->pPrior = 0;

2431 pLimit = p->pLimit;

2432 p->pLimit = 0;

2433 pOffset = p->pOffset;

2434 p->pOffset = 0;

2435 intersectdest.iSDParm = tab2;

2436 explainSetInteger(iSub2, pParse->iNextSelectId);

2437 rc = sqlite3Select(pParse, p, &intersectdest);

2438 testcase( rc!=SQLITE_OK );

2439 pDelete = p->pPrior;

2440 p->pPrior = pPrior;

2441 if( p->nSelectRow>pPrior->nSelectRow ) p->nSelectRow = pPrior->nSelectRow;

2442 sqlite3ExprDelete(db, p->pLimit);

2443 p->pLimit = pLimit;

2444 p->pOffset = pOffset;

2445

2446 /* Generate code to take the intersection of the two temporary

2447 ** tables.

2448 */

2449 assert( p->pEList );

2450 if( dest.eDest==SRT_Output ){

2451 Select *pFirst = p;

2452 while( pFirst->pPrior ) pFirst = pFirst->pPrior;

2453 generateColumnNames(pParse, pFirst->pSrc, pFirst->pEList);

2454 }

2455 iBreak = sqlite3VdbeMakeLabel(v);

2456 iCont = sqlite3VdbeMakeLabel(v);

2457 computeLimitRegisters(pParse, p, iBreak);

2458 sqlite3VdbeAddOp2(v, OP_Rewind, tab1, iBreak); VdbeCoverage(v);

2459 r1 = sqlite3GetTempReg(pParse);

2460 iStart = sqlite3VdbeAddOp2(v, OP_RowKey, tab1, r1);

2461 sqlite3VdbeAddOp4Int(v, OP_NotFound, tab2, iCont, r1, 0); VdbeCoverage(v);

2462 sqlite3ReleaseTempReg(pParse, r1);

2463 selectInnerLoop(pParse, p, p->pEList, tab1,

2464 0, 0, &dest, iCont, iBreak);

2465 sqlite3VdbeResolveLabel(v, iCont);

2466 sqlite3VdbeAddOp2(v, OP_Next, tab1, iStart); VdbeCoverage(v);

2467 sqlite3VdbeResolveLabel(v, iBreak);

2468 sqlite3VdbeAddOp2(v, OP_Close, tab2, 0);

2469 sqlite3VdbeAddOp2(v, OP_Close, tab1, 0);

2470 break;

2471 }

2472 }

2473

2474 explainComposite(pParse, p->op, iSub1, iSub2, p->op!=TK_ALL);

2475

2476 /* Compute collating sequences used by

2477 ** temporary tables needed to implement the compound select.

2478 ** Attach the KeyInfo structure to all temporary tables.

2479 **

2480 ** This section is run by the right-most SELECT statement only.

2481 ** SELECT statements to the left always skip this part. The right-most

2482 ** SELECT might also skip this part if it has no ORDER BY clause and

2483 ** no temp tables are required.

2484 */

2485 if( p->selFlags & SF_UsesEphemeral ){

2486 int i; /* Loop counter */

2487 KeyInfo pKeyInfo; / Collating sequence for the result set */

2488 Select pLoop; / For looping through SELECT statements */

2489 CollSeq *apColl; / For looping through pKeyInfo->aColl[] */

2490 int nCol; /* Number of columns in result set */

2491

2492 assert( p->pNext==0 );

2493 nCol = p->pEList->nExpr;

2494 pKeyInfo = sqlite3KeyInfoAlloc(db, nCol, 1);

2495 if( !pKeyInfo ){

2496 rc = SQLITE_NOMEM;

2497 goto multi_select_end;

2498 }

2499 for(i=0, apColl=pKeyInfo->aColl; i<nCol; i++, apColl++){

2500 *apColl = multiSelectCollSeq(pParse, p, i);

2501 if( 0==*apColl ){

2502 *apColl = db->pDfltColl;

2503 }

2504 }

2505

2506 for(pLoop=p; pLoop; pLoop=pLoop->pPrior){

2507 for(i=0; i<2; i++){

2508 int addr = pLoop->addrOpenEphm[i];

2509 if( addr<0 ){

2510 /* If [0] is unused then [1] is also unused. So we can

2511 ** always safely abort as soon as the first unused slot is found */

2512 assert( pLoop->addrOpenEphm[1]<0 );

2513 break;

2514 }

2515 sqlite3VdbeChangeP2(v, addr, nCol);

2516 sqlite3VdbeChangeP4(v, addr, (char*)sqlite3KeyInfoRef(pKeyInfo),

2517 P4_KEYINFO);

2518 pLoop->addrOpenEphm[i] = -1;

2519 }

2520 }

2521 sqlite3KeyInfoUnref(pKeyInfo);

2522 }

2523

2524 multi_select_end:

2525 pDest->iSdst = dest.iSdst;

2526 pDest->nSdst = dest.nSdst;

2527 sqlite3SelectDelete(db, pDelete);

2528 return rc;

2529 }

2530 #endif /* SQLITE_OMIT_COMPOUND_SELECT */

2531

2532 /*

2533 ** Error message for when two or more terms of a compound select have different

2534 ** size result sets.

2535 */

2536 void sqlite3SelectWrongNumTermsError(Parse pParse, Select p){

2537 if( p->selFlags & SF_Values ){

2538 sqlite3ErrorMsg(pParse, "all VALUES must have the same number of terms");

2539 }else{

2540 sqlite3ErrorMsg(pParse, "SELECTs to the left and right of %s"

2541 " do not have the same number of result columns", selectOpName(p->op));

2542 }

2543 }

2544

2545 /*

2546 ** Code an output subroutine for a coroutine implementation of a

2547 ** SELECT statment.

2548 **

2549 ** The data to be output is contained in pIn->iSdst. There are

2550 ** pIn->nSdst columns to be output. pDest is where the output should

2551 ** be sent.

2552 **

2553 ** regReturn is the number of the register holding the subroutine

2554 ** return address.

2555 **

2556 ** If regPrev>0 then it is the first register in a vector that

2557 ** records the previous output. mem[regPrev] is a flag that is false

2558 ** if there has been no previous output. If regPrev>0 then code is

2559 ** generated to suppress duplicates. pKeyInfo is used for comparing

2560 ** keys.

2561 **

2562 ** If the LIMIT found in p->iLimit is reached, jump immediately to

2563 ** iBreak.

2564 */

2565 static int generateOutputSubroutine(

2566 Parse pParse, / Parsing context */

2567 Select p, / The SELECT statement */

2568 SelectDest pIn, / Coroutine supplying data */

2569 SelectDest pDest, / Where to send the data */

2570 int regReturn, /* The return address register */

2571 int regPrev, /* Previous result register. No uniqueness if 0 */

2572 KeyInfo pKeyInfo, / For comparing with previous entry */

2573 int iBreak /* Jump here if we hit the LIMIT */

2574 ){

2575 Vdbe *v = pParse->pVdbe;

2576 int iContinue;

2577 int addr;

2578

2579 addr = sqlite3VdbeCurrentAddr(v);

2580 iContinue = sqlite3VdbeMakeLabel(v);

2581

2582 /* Suppress duplicates for UNION, EXCEPT, and INTERSECT

2583 */

2584 if( regPrev ){

2585 int addr1, addr2;

2586 addr1 = sqlite3VdbeAddOp1(v, OP_IfNot, regPrev); VdbeCoverage(v);

2587 addr2 = sqlite3VdbeAddOp4(v, OP_Compare, pIn->iSdst, regPrev+1, pIn->nSdst,

2588 (char*)sqlite3KeyInfoRef(pKeyInfo), P4_KEYINFO);

2589 sqlite3VdbeAddOp3(v, OP_Jump, addr2+2, iContinue, addr2+2); VdbeCoverage(v);

2590 sqlite3VdbeJumpHere(v, addr1);

2591 sqlite3VdbeAddOp3(v, OP_Copy, pIn->iSdst, regPrev+1, pIn->nSdst-1);

2592 sqlite3VdbeAddOp2(v, OP_Integer, 1, regPrev);

2593 }

2594 if( pParse->db->mallocFailed ) return 0;

2595

2596 /* Suppress the first OFFSET entries if there is an OFFSET clause

2597 */

2598 codeOffset(v, p->iOffset, iContinue);

2599

2600 assert( pDest->eDest!=SRT_Exists );

2601 assert( pDest->eDest!=SRT_Table );

2602 switch( pDest->eDest ){

2603 /* Store the result as data using a unique key.

2604 */

2605 case SRT_EphemTab: {

2606 int r1 = sqlite3GetTempReg(pParse);

2607 int r2 = sqlite3GetTempReg(pParse);

2608 sqlite3VdbeAddOp3(v, OP_MakeRecord, pIn->iSdst, pIn->nSdst, r1);

2609 sqlite3VdbeAddOp2(v, OP_NewRowid, pDest->iSDParm, r2);

2610 sqlite3VdbeAddOp3(v, OP_Insert, pDest->iSDParm, r1, r2);

2611 sqlite3VdbeChangeP5(v, OPFLAG_APPEND);

2612 sqlite3ReleaseTempReg(pParse, r2);

2613 sqlite3ReleaseTempReg(pParse, r1);

2614 break;

2615 }

2616

2617 #ifndef SQLITE_OMIT_SUBQUERY

2618 /* If we are creating a set for an "expr IN (SELECT ...)" construct,

2619 ** then there should be a single item on the stack. Write this

2620 ** item into the set table with bogus data.

2621 */

2622 case SRT_Set: {

2623 int r1;

2624 assert( pIn->nSdst==1 \|\| pParse->nErr>0 );

2625 pDest->affSdst =

2626 sqlite3CompareAffinity(p->pEList->a[0].pExpr, pDest->affSdst);

2627 r1 = sqlite3GetTempReg(pParse);

2628 sqlite3VdbeAddOp4(v, OP_MakeRecord, pIn->iSdst, 1, r1, &pDest->affSdst,1);

2629 sqlite3ExprCacheAffinityChange(pParse, pIn->iSdst, 1);

2630 sqlite3VdbeAddOp2(v, OP_IdxInsert, pDest->iSDParm, r1);

2631 sqlite3ReleaseTempReg(pParse, r1);

2632 break;

2633 }

2634

2635 /* If this is a scalar select that is part of an expression, then

2636 ** store the results in the appropriate memory cell and break out

2637 ** of the scan loop.

2638 */

2639 case SRT_Mem: {

2640 assert( pIn->nSdst==1 \|\| pParse->nErr>0 ); testcase( pIn->nSdst!=1 );

2641 sqlite3ExprCodeMove(pParse, pIn->iSdst, pDest->iSDParm, 1);

2642 /* The LIMIT clause will jump out of the loop for us */

2643 break;

2644 }

2645 #endif /* #ifndef SQLITE_OMIT_SUBQUERY */

2646

2647 /* The results are stored in a sequence of registers

2648 ** starting at pDest->iSdst. Then the co-routine yields.

2649 */

2650 case SRT_Coroutine: {

2651 if( pDest->iSdst==0 ){

2652 pDest->iSdst = sqlite3GetTempRange(pParse, pIn->nSdst);

2653 pDest->nSdst = pIn->nSdst;

2654 }

2655 sqlite3ExprCodeMove(pParse, pIn->iSdst, pDest->iSdst, pIn->nSdst);

2656 sqlite3VdbeAddOp1(v, OP_Yield, pDest->iSDParm);

2657 break;

2658 }

2659

2660 /* If none of the above, then the result destination must be

2661 ** SRT_Output. This routine is never called with any other

2662 ** destination other than the ones handled above or SRT_Output.

2663 **

2664 ** For SRT_Output, results are stored in a sequence of registers.

2665 ** Then the OP_ResultRow opcode is used to cause sqlite3_step() to

2666 ** return the next row of result.

2667 */

2668 default: {

2669 assert( pDest->eDest==SRT_Output );

2670 sqlite3VdbeAddOp2(v, OP_ResultRow, pIn->iSdst, pIn->nSdst);

2671 sqlite3ExprCacheAffinityChange(pParse, pIn->iSdst, pIn->nSdst);

2672 break;

2673 }

2674 }

2675

2676 /* Jump to the end of the loop if the LIMIT is reached.

2677 */

2678 if( p->iLimit ){

2679 sqlite3VdbeAddOp2(v, OP_DecrJumpZero, p->iLimit, iBreak); VdbeCoverage(v);

2680 }

2681

2682 /* Generate the subroutine return

2683 */

2684 sqlite3VdbeResolveLabel(v, iContinue);

2685 sqlite3VdbeAddOp1(v, OP_Return, regReturn);

2686

2687 return addr;

2688 }

2689

2690 /*

2691 ** Alternative compound select code generator for cases when there

2692 ** is an ORDER BY clause.

2693 **

2694 ** We assume a query of the following form:

2695 **

2696 ** <selectA> <operator> <selectB> ORDER BY <orderbylist>

2697 **

2698 ** <operator> is one of UNION ALL, UNION, EXCEPT, or INTERSECT. The idea

2699 ** is to code both <selectA> and <selectB> with the ORDER BY clause as

2700 ** co-routines. Then run the co-routines in parallel and merge the results

2701 ** into the output. In addition to the two coroutines (called selectA and

2702 ** selectB) there are 7 subroutines:

2703 **

2704 ** outA: Move the output of the selectA coroutine into the output

2705 ** of the compound query.

2706 **

2707 ** outB: Move the output of the selectB coroutine into the output

2708 ** of the compound query. (Only generated for UNION and

2709 ** UNION ALL. EXCEPT and INSERTSECT never output a row that

2710 ** appears only in B.)

2711 **

2712 ** AltB: Called when there is data from both coroutines and A<B.

2713 **

2714 ** AeqB: Called when there is data from both coroutines and A==B.

2715 **

2716 ** AgtB: Called when there is data from both coroutines and A>B.

2717 **

2718 ** EofA: Called when data is exhausted from selectA.

2719 **

2720 ** EofB: Called when data is exhausted from selectB.

2721 **

2722 ** The implementation of the latter five subroutines depend on which

2723 ** <operator> is used:

2724 **

2725 **

2726 ** UNION ALL UNION EXCEPT INTERSECT

2727 ** ------------- ----------------- -------------- -----------------

2728 ** AltB: outA, nextA outA, nextA outA, nextA nextA

2729 **

2730 ** AeqB: outA, nextA nextA nextA outA, nextA

2731 **

2732 ** AgtB: outB, nextB outB, nextB nextB nextB

2733 **

2734 ** EofA: outB, nextB outB, nextB halt halt

2735 **

2736 ** EofB: outA, nextA outA, nextA outA, nextA halt

2737 **

2738 ** In the AltB, AeqB, and AgtB subroutines, an EOF on A following nextA

2739 ** causes an immediate jump to EofA and an EOF on B following nextB causes

2740 ** an immediate jump to EofB. Within EofA and EofB, and EOF on entry or

2741 ** following nextX causes a jump to the end of the select processing.

2742 **

2743 ** Duplicate removal in the UNION, EXCEPT, and INTERSECT cases is handled

2744 ** within the output subroutine. The regPrev register set holds the previously

2745 ** output value. A comparison is made against this value and the output

2746 ** is skipped if the next results would be the same as the previous.

2747 **

2748 ** The implementation plan is to implement the two coroutines and seven

2749 ** subroutines first, then put the control logic at the bottom. Like this:

2750 **

2751 ** goto Init

2752 ** coA: coroutine for left query (A)

2753 ** coB: coroutine for right query (B)

2754 ** outA: output one row of A

2755 ** outB: output one row of B (UNION and UNION ALL only)

2756 ** EofA: ...

2757 ** EofB: ...

2758 ** AltB: ...

2759 ** AeqB: ...

2760 ** AgtB: ...

2761 ** Init: initialize coroutine registers

2762 ** yield coA

2763 ** if eof(A) goto EofA

2764 ** yield coB

2765 ** if eof(B) goto EofB

2766 ** Cmpr: Compare A, B

2767 ** Jump AltB, AeqB, AgtB

2768 ** End: ...

2769 **

2770 ** We call AltB, AeqB, AgtB, EofA, and EofB "subroutines" but they are not

2771 ** actually called using Gosub and they do not Return. EofA and EofB loop

2772 ** until all data is exhausted then jump to the "end" labe. AltB, AeqB,

2773 ** and AgtB jump to either L2 or to one of EofA or EofB.

2774 */

2775 #ifndef SQLITE_OMIT_COMPOUND_SELECT

2776 static int multiSelectOrderBy(

2777 Parse pParse, / Parsing context */

2778 Select p, / The right-most of SELECTs to be coded */

2779 SelectDest pDest / What to do with query results */

2780 ){

2781 int i, j; /* Loop counters */

2782 Select pPrior; / Another SELECT immediately to our left */

2783 Vdbe v; / Generate code to this VDBE */

2784 SelectDest destA; /* Destination for coroutine A */

2785 SelectDest destB; /* Destination for coroutine B */

2786 int regAddrA; /* Address register for select-A coroutine */

2787 int regAddrB; /* Address register for select-B coroutine */

2788 int addrSelectA; /* Address of the select-A coroutine */

2789 int addrSelectB; /* Address of the select-B coroutine */

2790 int regOutA; /* Address register for the output-A subroutine */

2791 int regOutB; /* Address register for the output-B subroutine */

2792 int addrOutA; /* Address of the output-A subroutine */

2793 int addrOutB = 0; /* Address of the output-B subroutine */

2794 int addrEofA; /* Address of the select-A-exhausted subroutine */

2795 int addrEofA_noB; /* Alternate addrEofA if B is uninitialized */

2796 int addrEofB; /* Address of the select-B-exhausted subroutine */

2797 int addrAltB; /* Address of the A<B subroutine */

2798 int addrAeqB; /* Address of the A==B subroutine */

2799 int addrAgtB; /* Address of the A>B subroutine */

2800 int regLimitA; /* Limit register for select-A */

2801 int regLimitB; /* Limit register for select-A */

2802 int regPrev; /* A range of registers to hold previous output */

2803 int savedLimit; /* Saved value of p->iLimit */

2804 int savedOffset; /* Saved value of p->iOffset */

2805 int labelCmpr; /* Label for the start of the merge algorithm */

2806 int labelEnd; /* Label for the end of the overall SELECT stmt */

2807 int addr1; /* Jump instructions that get retargetted */

2808 int op; /* One of TK_ALL, TK_UNION, TK_EXCEPT, TK_INTERSECT */

2809 KeyInfo pKeyDup = 0; / Comparison information for duplicate removal */

2810 KeyInfo pKeyMerge; / Comparison information for merging rows */

2811 sqlite3 db; / Database connection */

2812 ExprList pOrderBy; / The ORDER BY clause */

2813 int nOrderBy; /* Number of terms in the ORDER BY clause */

2814 int aPermute; / Mapping from ORDER BY terms to result set columns */

2815 #ifndef SQLITE_OMIT_EXPLAIN

2816 int iSub1; /* EQP id of left-hand query */

2817 int iSub2; /* EQP id of right-hand query */

2818 #endif

2819

2820 assert( p->pOrderBy!=0 );

2821 assert( pKeyDup==0 ); /* "Managed" code needs this. Ticket #3382. */

2822 db = pParse->db;

2823 v = pParse->pVdbe;

2824 assert( v!=0 ); /* Already thrown the error if VDBE alloc failed */

2825 labelEnd = sqlite3VdbeMakeLabel(v);

2826 labelCmpr = sqlite3VdbeMakeLabel(v);

2827

2828

2829 /* Patch up the ORDER BY clause

2830 */

2831 op = p->op;

2832 pPrior = p->pPrior;

2833 assert( pPrior->pOrderBy==0 );

2834 pOrderBy = p->pOrderBy;

2835 assert( pOrderBy );

2836 nOrderBy = pOrderBy->nExpr;

2837

2838 /* For operators other than UNION ALL we have to make sure that

2839 ** the ORDER BY clause covers every term of the result set. Add

2840 ** terms to the ORDER BY clause as necessary.

2841 */

2842 if( op!=TK_ALL ){

2843 for(i=1; db->mallocFailed==0 && i<=p->pEList->nExpr; i++){

2844 struct ExprList_item *pItem;

2845 for(j=0, pItem=pOrderBy->a; j<nOrderBy; j++, pItem++){

2846 assert( pItem->u.x.iOrderByCol>0 );

2847 if( pItem->u.x.iOrderByCol==i ) break;

2848 }

2849 if( j==nOrderBy ){

2850 Expr *pNew = sqlite3Expr(db, TK_INTEGER, 0);

2851 if( pNew==0 ) return SQLITE_NOMEM;

2852 pNew->flags \|= EP_IntValue;

2853 pNew->u.iValue = i;

2854 pOrderBy = sqlite3ExprListAppend(pParse, pOrderBy, pNew);

2855 if( pOrderBy ) pOrderBy->a[nOrderBy++].u.x.iOrderByCol = (u16)i;

2856 }

2857 }

2858 }

2859

2860 /* Compute the comparison permutation and keyinfo that is used with

2861 ** the permutation used to determine if the next

2862 ** row of results comes from selectA or selectB. Also add explicit

2863 ** collations to the ORDER BY clause terms so that when the subqueries

2864 ** to the right and the left are evaluated, they use the correct

2865 ** collation.

2866 */

2867 aPermute = sqlite3DbMallocRaw(db, sizeof(int)*nOrderBy);

2868 if( aPermute ){

2869 struct ExprList_item *pItem;

2870 for(i=0, pItem=pOrderBy->a; i<nOrderBy; i++, pItem++){

2871 assert( pItem->u.x.iOrderByCol>0 );

2872 assert( pItem->u.x.iOrderByCol<=p->pEList->nExpr );

2873 aPermute[i] = pItem->u.x.iOrderByCol - 1;

2874 }

2875 pKeyMerge = multiSelectOrderByKeyInfo(pParse, p, 1);

2876 }else{

2877 pKeyMerge = 0;

2878 }

2879

2880 /* Reattach the ORDER BY clause to the query.

2881 */

2882 p->pOrderBy = pOrderBy;

2883 pPrior->pOrderBy = sqlite3ExprListDup(pParse->db, pOrderBy, 0);

2884

2885 /* Allocate a range of temporary registers and the KeyInfo needed

2886 ** for the logic that removes duplicate result rows when the

2887 ** operator is UNION, EXCEPT, or INTERSECT (but not UNION ALL).

2888 */

2889 if( op==TK_ALL ){

2890 regPrev = 0;

2891 }else{

2892 int nExpr = p->pEList->nExpr;

2893 assert( nOrderBy>=nExpr \|\| db->mallocFailed );

2894 regPrev = pParse->nMem+1;

2895 pParse->nMem += nExpr+1;

2896 sqlite3VdbeAddOp2(v, OP_Integer, 0, regPrev);

2897 pKeyDup = sqlite3KeyInfoAlloc(db, nExpr, 1);

2898 if( pKeyDup ){

2899 assert( sqlite3KeyInfoIsWriteable(pKeyDup) );

2900 for(i=0; i<nExpr; i++){

2901 pKeyDup->aColl[i] = multiSelectCollSeq(pParse, p, i);

2902 pKeyDup->aSortOrder[i] = 0;

2903 }

2904 }

2905 }

2906

2907 /* Separate the left and the right query from one another

2908 */

2909 p->pPrior = 0;

2910 pPrior->pNext = 0;

2911 sqlite3ResolveOrderGroupBy(pParse, p, p->pOrderBy, "ORDER");

2912 if( pPrior->pPrior==0 ){

2913 sqlite3ResolveOrderGroupBy(pParse, pPrior, pPrior->pOrderBy, "ORDER");

2914 }

2915

2916 /* Compute the limit registers */

2917 computeLimitRegisters(pParse, p, labelEnd);

2918 if( p->iLimit && op==TK_ALL ){

2919 regLimitA = ++pParse->nMem;

2920 regLimitB = ++pParse->nMem;

2921 sqlite3VdbeAddOp2(v, OP_Copy, p->iOffset ? p->iOffset+1 : p->iLimit,

2922 regLimitA);

2923 sqlite3VdbeAddOp2(v, OP_Copy, regLimitA, regLimitB);

2924 }else{

2925 regLimitA = regLimitB = 0;

2926 }

2927 sqlite3ExprDelete(db, p->pLimit);

2928 p->pLimit = 0;

2929 sqlite3ExprDelete(db, p->pOffset);

2930 p->pOffset = 0;

2931

2932 regAddrA = ++pParse->nMem;

2933 regAddrB = ++pParse->nMem;

2934 regOutA = ++pParse->nMem;

2935 regOutB = ++pParse->nMem;

2936 sqlite3SelectDestInit(&destA, SRT_Coroutine, regAddrA);

2937 sqlite3SelectDestInit(&destB, SRT_Coroutine, regAddrB);

2938

2939 /* Generate a coroutine to evaluate the SELECT statement to the

2940 ** left of the compound operator - the "A" select.

2941 */

2942 addrSelectA = sqlite3VdbeCurrentAddr(v) + 1;

2943 addr1 = sqlite3VdbeAddOp3(v, OP_InitCoroutine, regAddrA, 0, addrSelectA);

2944 VdbeComment((v, "left SELECT"));

2945 pPrior->iLimit = regLimitA;

2946 explainSetInteger(iSub1, pParse->iNextSelectId);

2947 sqlite3Select(pParse, pPrior, &destA);

2948 sqlite3VdbeAddOp1(v, OP_EndCoroutine, regAddrA);

2949 sqlite3VdbeJumpHere(v, addr1);

2950

2951 /* Generate a coroutine to evaluate the SELECT statement on

2952 ** the right - the "B" select

2953 */

2954 addrSelectB = sqlite3VdbeCurrentAddr(v) + 1;

2955 addr1 = sqlite3VdbeAddOp3(v, OP_InitCoroutine, regAddrB, 0, addrSelectB);

2956 VdbeComment((v, "right SELECT"));

2957 savedLimit = p->iLimit;

2958 savedOffset = p->iOffset;

2959 p->iLimit = regLimitB;

2960 p->iOffset = 0;

2961 explainSetInteger(iSub2, pParse->iNextSelectId);

2962 sqlite3Select(pParse, p, &destB);

2963 p->iLimit = savedLimit;

2964 p->iOffset = savedOffset;

2965 sqlite3VdbeAddOp1(v, OP_EndCoroutine, regAddrB);

2966

2967 /* Generate a subroutine that outputs the current row of the A

2968 ** select as the next output row of the compound select.

2969 */

2970 VdbeNoopComment((v, "Output routine for A"));

2971 addrOutA = generateOutputSubroutine(pParse,

2972 p, &destA, pDest, regOutA,

2973 regPrev, pKeyDup, labelEnd);

2974

2975 /* Generate a subroutine that outputs the current row of the B

2976 ** select as the next output row of the compound select.

2977 */

2978 if( op==TK_ALL \|\| op==TK_UNION ){

2979 VdbeNoopComment((v, "Output routine for B"));

2980 addrOutB = generateOutputSubroutine(pParse,

2981 p, &destB, pDest, regOutB,

2982 regPrev, pKeyDup, labelEnd);

2983 }

2984 sqlite3KeyInfoUnref(pKeyDup);

2985

2986 /* Generate a subroutine to run when the results from select A

2987 ** are exhausted and only data in select B remains.

2988 */

2989 if( op==TK_EXCEPT \|\| op==TK_INTERSECT ){

2990 addrEofA_noB = addrEofA = labelEnd;

2991 }else{

2992 VdbeNoopComment((v, "eof-A subroutine"));

2993 addrEofA = sqlite3VdbeAddOp2(v, OP_Gosub, regOutB, addrOutB);

2994 addrEofA_noB = sqlite3VdbeAddOp2(v, OP_Yield, regAddrB, labelEnd);

2995 VdbeCoverage(v);

2996 sqlite3VdbeGoto(v, addrEofA);

2997 p->nSelectRow += pPrior->nSelectRow;

2998 }

2999

3000 /* Generate a subroutine to run when the results from select B

3001 ** are exhausted and only data in select A remains.

3002 */

3003 if( op==TK_INTERSECT ){

3004 addrEofB = addrEofA;

3005 if( p->nSelectRow > pPrior->nSelectRow ) p->nSelectRow = pPrior->nSelectRow;

3006 }else{

3007 VdbeNoopComment((v, "eof-B subroutine"));

3008 addrEofB = sqlite3VdbeAddOp2(v, OP_Gosub, regOutA, addrOutA);

3009 sqlite3VdbeAddOp2(v, OP_Yield, regAddrA, labelEnd); VdbeCoverage(v);

3010 sqlite3VdbeGoto(v, addrEofB);

3011 }

3012

3013 /* Generate code to handle the case of A<B

3014 */

3015 VdbeNoopComment((v, "A-lt-B subroutine"));

3016 addrAltB = sqlite3VdbeAddOp2(v, OP_Gosub, regOutA, addrOutA);

3017 sqlite3VdbeAddOp2(v, OP_Yield, regAddrA, addrEofA); VdbeCoverage(v);

3018 sqlite3VdbeGoto(v, labelCmpr);

3019

3020 /* Generate code to handle the case of A==B

3021 */

3022 if( op==TK_ALL ){

3023 addrAeqB = addrAltB;

3024 }else if( op==TK_INTERSECT ){

3025 addrAeqB = addrAltB;

3026 addrAltB++;

3027 }else{

3028 VdbeNoopComment((v, "A-eq-B subroutine"));

3029 addrAeqB =

3030 sqlite3VdbeAddOp2(v, OP_Yield, regAddrA, addrEofA); VdbeCoverage(v);

3031 sqlite3VdbeGoto(v, labelCmpr);

3032 }

3033

3034 /* Generate code to handle the case of A>B

3035 */

3036 VdbeNoopComment((v, "A-gt-B subroutine"));

3037 addrAgtB = sqlite3VdbeCurrentAddr(v);

3038 if( op==TK_ALL \|\| op==TK_UNION ){

3039 sqlite3VdbeAddOp2(v, OP_Gosub, regOutB, addrOutB);

3040 }

3041 sqlite3VdbeAddOp2(v, OP_Yield, regAddrB, addrEofB); VdbeCoverage(v);

3042 sqlite3VdbeGoto(v, labelCmpr);

3043

3044 /* This code runs once to initialize everything.

3045 */

3046 sqlite3VdbeJumpHere(v, addr1);

3047 sqlite3VdbeAddOp2(v, OP_Yield, regAddrA, addrEofA_noB); VdbeCoverage(v);

3048 sqlite3VdbeAddOp2(v, OP_Yield, regAddrB, addrEofB); VdbeCoverage(v);

3049

3050 /* Implement the main merge loop

3051 */

3052 sqlite3VdbeResolveLabel(v, labelCmpr);

3053 sqlite3VdbeAddOp4(v, OP_Permutation, 0, 0, 0, (char*)aPermute, P4_INTARRAY);

3054 sqlite3VdbeAddOp4(v, OP_Compare, destA.iSdst, destB.iSdst, nOrderBy,

3055 (char*)pKeyMerge, P4_KEYINFO);

3056 sqlite3VdbeChangeP5(v, OPFLAG_PERMUTE);

3057 sqlite3VdbeAddOp3(v, OP_Jump, addrAltB, addrAeqB, addrAgtB); VdbeCoverage(v);

3058

3059 /* Jump to the this point in order to terminate the query.

3060 */

3061 sqlite3VdbeResolveLabel(v, labelEnd);

3062

3063 /* Set the number of output columns

3064 */

3065 if( pDest->eDest==SRT_Output ){

3066 Select *pFirst = pPrior;

3067 while( pFirst->pPrior ) pFirst = pFirst->pPrior;

3068 generateColumnNames(pParse, pFirst->pSrc, pFirst->pEList);

3069 }

3070

3071 /* Reassembly the compound query so that it will be freed correctly

3072 ** by the calling function */

3073 if( p->pPrior ){

3074 sqlite3SelectDelete(db, p->pPrior);

3075 }

3076 p->pPrior = pPrior;

3077 pPrior->pNext = p;

3078

3079 /*** TBD: Insert subroutine calls to close cursors on incomplete

3080 ** subqueries **/

3081 explainComposite(pParse, p->op, iSub1, iSub2, 0);

3082 return pParse->nErr!=0;

3083 }

3084 #endif

3085

3086 #if !defined(SQLITE_OMIT_SUBQUERY) \|\| !defined(SQLITE_OMIT_VIEW)

3087 /* Forward Declarations */

3088 static void substExprList(sqlite3, ExprList, int, ExprList*);

3089 static void substSelect(sqlite3, Select , int, ExprList*, int);

3090

3091 /*

3092 ** Scan through the expression pExpr. Replace every reference to

3093 ** a column in table number iTable with a copy of the iColumn-th

3094 ** entry in pEList. (But leave references to the ROWID column

3095 ** unchanged.)

3096 **

3097 ** This routine is part of the flattening procedure. A subquery

3098 ** whose result set is defined by pEList appears as entry in the

3099 ** FROM clause of a SELECT such that the VDBE cursor assigned to that

3100 ** FORM clause entry is iTable. This routine make the necessary

3101 ** changes to pExpr so that it refers directly to the source table

3102 ** of the subquery rather the result set of the subquery.

3103 */

3104 static Expr *substExpr(

3105 sqlite3 db, / Report malloc errors to this connection */

3106 Expr pExpr, / Expr in which substitution occurs */

3107 int iTable, /* Table to be substituted */

3108 ExprList pEList / Substitute expressions */

3109 ){

3110 if( pExpr==0 ) return 0;

3111 if( pExpr->op==TK_COLUMN && pExpr->iTable==iTable ){

3112 if( pExpr->iColumn<0 ){

3113 pExpr->op = TK_NULL;

3114 }else{

3115 Expr *pNew;

3116 assert( pEList!=0 && pExpr->iColumn<pEList->nExpr );

3117 assert( pExpr->pLeft==0 && pExpr->pRight==0 );

3118 pNew = sqlite3ExprDup(db, pEList->a[pExpr->iColumn].pExpr, 0);

3119 sqlite3ExprDelete(db, pExpr);

3120 pExpr = pNew;

3121 }

3122 }else{

3123 pExpr->pLeft = substExpr(db, pExpr->pLeft, iTable, pEList);

3124 pExpr->pRight = substExpr(db, pExpr->pRight, iTable, pEList);

3125 if( ExprHasProperty(pExpr, EP_xIsSelect) ){

3126 substSelect(db, pExpr->x.pSelect, iTable, pEList, 1);

3127 }else{

3128 substExprList(db, pExpr->x.pList, iTable, pEList);

3129 }

3130 }

3131 return pExpr;

3132 }

3133 static void substExprList(

3134 sqlite3 db, / Report malloc errors here */

3135 ExprList pList, / List to scan and in which to make substitutes */

3136 int iTable, /* Table to be substituted */

3137 ExprList pEList / Substitute values */

3138 ){

3139 int i;

3140 if( pList==0 ) return;

3141 for(i=0; i<pList->nExpr; i++){

3142 pList->a[i].pExpr = substExpr(db, pList->a[i].pExpr, iTable, pEList);

3143 }

3144 }

3145 static void substSelect(

3146 sqlite3 db, / Report malloc errors here */

3147 Select p, / SELECT statement in which to make substitutions */

3148 int iTable, /* Table to be replaced */

3149 ExprList pEList, / Substitute values */

3150 int doPrior /* Do substitutes on p->pPrior too */

3151 ){

3152 SrcList *pSrc;

3153 struct SrcList_item *pItem;

3154 int i;

3155 if( !p ) return;

3156 do{

3157 substExprList(db, p->pEList, iTable, pEList);

3158 substExprList(db, p->pGroupBy, iTable, pEList);

3159 substExprList(db, p->pOrderBy, iTable, pEList);

3160 p->pHaving = substExpr(db, p->pHaving, iTable, pEList);

3161 p->pWhere = substExpr(db, p->pWhere, iTable, pEList);

3162 pSrc = p->pSrc;

3163 assert( pSrc!=0 );

3164 for(i=pSrc->nSrc, pItem=pSrc->a; i>0; i--, pItem++){

3165 substSelect(db, pItem->pSelect, iTable, pEList, 1);

3166 if( pItem->fg.isTabFunc ){

3167 substExprList(db, pItem->u1.pFuncArg, iTable, pEList);

3168 }

3169 }

3170 }while( doPrior && (p = p->pPrior)!=0 );

3171 }

3172 #endif /* !defined(SQLITE_OMIT_SUBQUERY) \|\| !defined(SQLITE_OMIT_VIEW) */

3173

3174 #if !defined(SQLITE_OMIT_SUBQUERY) \|\| !defined(SQLITE_OMIT_VIEW)

3175 /*

3176 ** This routine attempts to flatten subqueries as a performance optimization.

3177 ** This routine returns 1 if it makes changes and 0 if no flattening occurs.

3178 **

3179 ** To understand the concept of flattening, consider the following

3180 ** query:

3181 **

3182 ** SELECT a FROM (SELECT x+y AS a FROM t1 WHERE z<100) WHERE a>5

3183 **

3184 ** The default way of implementing this query is to execute the

3185 ** subquery first and store the results in a temporary table, then

3186 ** run the outer query on that temporary table. This requires two

3187 ** passes over the data. Furthermore, because the temporary table

3188 ** has no indices, the WHERE clause on the outer query cannot be

3189 ** optimized.

3190 **

3191 ** This routine attempts to rewrite queries such as the above into

3192 ** a single flat select, like this:

3193 **

3194 ** SELECT x+y AS a FROM t1 WHERE z<100 AND a>5

3195 **

3196 ** The code generated for this simplification gives the same result

3197 ** but only has to scan the data once. And because indices might

3198 ** exist on the table t1, a complete scan of the data might be

3199 ** avoided.

3200 **

3201 ** Flattening is only attempted if all of the following are true:

3202 **

3203 ** (1) The subquery and the outer query do not both use aggregates.

3204 **

3205 ** (2) The subquery is not an aggregate or (2a) the outer query is not a join

3206 ** and (2b) the outer query does not use subqueries other than the one

3207 ** FROM-clause subquery that is a candidate for flattening. (2b is

3208 ** due to ticket [2f7170d73bf9abf80] from 2015-02-09.)

3209 **

3210 ** (3) The subquery is not the right operand of a left outer join

3211 ** (Originally ticket #306. Strengthened by ticket #3300)

3212 **

3213 ** (4) The subquery is not DISTINCT.

3214 **

3215 () At one point restrictions (4) and (5) defined a subset of DISTINCT

3216 ** sub-queries that were excluded from this optimization. Restriction

3217 ** (4) has since been expanded to exclude all DISTINCT subqueries.

3218 **

3219 ** (6) The subquery does not use aggregates or the outer query is not

3220 ** DISTINCT.

3221 **

3222 ** (7) The subquery has a FROM clause. TODO: For subqueries without

3223 ** A FROM clause, consider adding a FROM close with the special

3224 ** table sqlite_once that consists of a single row containing a

3225 ** single NULL.

3226 **

3227 ** (8) The subquery does not use LIMIT or the outer query is not a join.

3228 **

3229 ** (9) The subquery does not use LIMIT or the outer query does not use

3230 ** aggregates.

3231 **

3232 () Restriction (10) was removed from the code on 2005-02-05 but we

3233 ** accidently carried the comment forward until 2014-09-15. Original

3234 ** text: "The subquery does not use aggregates or the outer query

3235 ** does not use LIMIT."

3236 **

3237 ** (11) The subquery and the outer query do not both have ORDER BY clauses.

3238 **

3239 () Not implemented. Subsumed into restriction (3). Was previously

3240 ** a separate restriction deriving from ticket #350.

3241 **

3242 ** (13) The subquery and outer query do not both use LIMIT.

3243 **

3244 ** (14) The subquery does not use OFFSET.

3245 **

3246 ** (15) The outer query is not part of a compound select or the

3247 ** subquery does not have a LIMIT clause.

3248 ** (See ticket #2339 and ticket [02a8e81d44]).

3249 **

3250 ** (16) The outer query is not an aggregate or the subquery does

3251 ** not contain ORDER BY. (Ticket #2942) This used to not matter

3252 ** until we introduced the group_concat() function.

3253 **

3254 ** (17) The sub-query is not a compound select, or it is a UNION ALL

3255 ** compound clause made up entirely of non-aggregate queries, and

3256 ** the parent query:

3257 **

3258 ** * is not itself part of a compound select,

3259 ** * is not an aggregate or DISTINCT query, and

3260 ** * is not a join

3261 **

3262 ** The parent and sub-query may contain WHERE clauses. Subject to

3263 ** rules (11), (13) and (14), they may also contain ORDER BY,

3264 ** LIMIT and OFFSET clauses. The subquery cannot use any compound

3265 ** operator other than UNION ALL because all the other compound

3266 ** operators have an implied DISTINCT which is disallowed by

3267 ** restriction (4).

3268 **

3269 ** Also, each component of the sub-query must return the same number

3270 ** of result columns. This is actually a requirement for any compound

3271 ** SELECT statement, but all the code here does is make sure that no

3272 ** such (illegal) sub-query is flattened. The caller will detect the

3273 ** syntax error and return a detailed message.

3274 **

3275 ** (18) If the sub-query is a compound select, then all terms of the

3276 ** ORDER by clause of the parent must be simple references to

3277 ** columns of the sub-query.

3278 **

3279 ** (19) The subquery does not use LIMIT or the outer query does not

3280 ** have a WHERE clause.

3281 **

3282 ** (20) If the sub-query is a compound select, then it must not use

3283 ** an ORDER BY clause. Ticket #3773. We could relax this constraint

3284 ** somewhat by saying that the terms of the ORDER BY clause must

3285 ** appear as unmodified result columns in the outer query. But we

3286 ** have other optimizations in mind to deal with that case.

3287 **

3288 ** (21) The subquery does not use LIMIT or the outer query is not

3289 ** DISTINCT. (See ticket [752e1646fc]).

3290 **

3291 ** (22) The subquery is not a recursive CTE.

3292 **

3293 ** (23) The parent is not a recursive CTE, or the sub-query is not a

3294 ** compound query. This restriction is because transforming the

3295 ** parent to a compound query confuses the code that handles

3296 ** recursive queries in multiSelect().

3297 **

3298 ** (24) The subquery is not an aggregate that uses the built-in min() or

3299 ** or max() functions. (Without this restriction, a query like:

3300 ** "SELECT x FROM (SELECT max(y), x FROM t1)" would not necessarily

3301 ** return the value X for which Y was maximal.)

3302 **

3303 **

3304 ** In this routine, the "p" parameter is a pointer to the outer query.

3305 ** The subquery is p->pSrc->a[iFrom]. isAgg is true if the outer query

3306 ** uses aggregates and subqueryIsAgg is true if the subquery uses aggregates.

3307 **

3308 ** If flattening is not attempted, this routine is a no-op and returns 0.

3309 ** If flattening is attempted this routine returns 1.

3310 **

3311 ** All of the expression analysis must occur on both the outer query and

3312 ** the subquery before this routine runs.

3313 */

3314 static int flattenSubquery(

3315 Parse pParse, / Parsing context */

3316 Select p, / The parent or outer SELECT statement */

3317 int iFrom, /* Index in p->pSrc->a[] of the inner subquery */

3318 int isAgg, /* True if outer SELECT uses aggregate functions */

3319 int subqueryIsAgg /* True if the subquery uses aggregate functions */

3320 ){

3321 const char *zSavedAuthContext = pParse->zAuthContext;

3322 Select pParent; / Current UNION ALL term of the other query */

3323 Select pSub; / The inner query or "subquery" */

3324 Select pSub1; / Pointer to the rightmost select in sub-query */

3325 SrcList pSrc; / The FROM clause of the outer query */

3326 SrcList pSubSrc; / The FROM clause of the subquery */

3327 ExprList pList; / The result set of the outer query */

3328 int iParent; /* VDBE cursor number of the pSub result set temp table */

3329 int i; /* Loop counter */

3330 Expr pWhere; / The WHERE clause */

3331 struct SrcList_item pSubitem; / The subquery */

3332 sqlite3 *db = pParse->db;

3333

3334 /* Check to see if flattening is permitted. Return 0 if not.

3335 */

3336 assert( p!=0 );

3337 assert( p->pPrior==0 ); /* Unable to flatten compound queries */

3338 if( OptimizationDisabled(db, SQLITE_QueryFlattener) ) return 0;

3339 pSrc = p->pSrc;

3340 assert( pSrc && iFrom>=0 && iFrom<pSrc->nSrc );

3341 pSubitem = &pSrc->a[iFrom];

3342 iParent = pSubitem->iCursor;

3343 pSub = pSubitem->pSelect;

3344 assert( pSub!=0 );

3345 if( subqueryIsAgg ){

3346 if( isAgg ) return 0; /* Restriction (1) */

3347 if( pSrc->nSrc>1 ) return 0; /* Restriction (2a) */

3348 if( (p->pWhere && ExprHasProperty(p->pWhere,EP_Subquery))

3349 \|\| (sqlite3ExprListFlags(p->pEList) & EP_Subquery)!=0

3350 \|\| (sqlite3ExprListFlags(p->pOrderBy) & EP_Subquery)!=0

3351 ){

3352 return 0; /* Restriction (2b) */

3353 }

3354 }

3355

3356 pSubSrc = pSub->pSrc;

3357 assert( pSubSrc );

3358 /* Prior to version 3.1.2, when LIMIT and OFFSET had to be simple constants,

3359 ** not arbitrary expressions, we allowed some combining of LIMIT and OFFSET

3360 ** because they could be computed at compile-time. But when LIMIT and OFFSET

3361 ** became arbitrary expressions, we were forced to add restrictions (13)

3362 ** and (14). */

3363 if( pSub->pLimit && p->pLimit ) return 0; /* Restriction (13) */

3364 if( pSub->pOffset ) return 0; /* Restriction (14) */

3365 if( (p->selFlags & SF_Compound)!=0 && pSub->pLimit ){

3366 return 0; /* Restriction (15) */

3367 }

3368 if( pSubSrc->nSrc==0 ) return 0; /* Restriction (7) */

3369 if( pSub->selFlags & SF_Distinct ) return 0; /* Restriction (5) */

3370 if( pSub->pLimit && (pSrc->nSrc>1 \|\| isAgg) ){

3371 return 0; /* Restrictions (8)(9) */

3372 }

3373 if( (p->selFlags & SF_Distinct)!=0 && subqueryIsAgg ){

3374 return 0; /* Restriction (6) */

3375 }

3376 if( p->pOrderBy && pSub->pOrderBy ){

3377 return 0; /* Restriction (11) */

3378 }

3379 if( isAgg && pSub->pOrderBy ) return 0; /* Restriction (16) */

3380 if( pSub->pLimit && p->pWhere ) return 0; /* Restriction (19) */

3381 if( pSub->pLimit && (p->selFlags & SF_Distinct)!=0 ){

3382 return 0; /* Restriction (21) */

3383 }

3384 testcase( pSub->selFlags & SF_Recursive );

3385 testcase( pSub->selFlags & SF_MinMaxAgg );

3386 if( pSub->selFlags & (SF_Recursive\|SF_MinMaxAgg) ){

3387 return 0; /* Restrictions (22) and (24) */

3388 }

3389 if( (p->selFlags & SF_Recursive) && pSub->pPrior ){

3390 return 0; /* Restriction (23) */

3391 }

3392

3393 /* OBSOLETE COMMENT 1:

3394 ** Restriction 3: If the subquery is a join, make sure the subquery is

3395 ** not used as the right operand of an outer join. Examples of why this

3396 ** is not allowed:

3397 **

3398 ** t1 LEFT OUTER JOIN (t2 JOIN t3)

3399 **

3400 ** If we flatten the above, we would get

3401 **

3402 ** (t1 LEFT OUTER JOIN t2) JOIN t3

3403 **

3404 ** which is not at all the same thing.

3405 **

3406 ** OBSOLETE COMMENT 2:

3407 ** Restriction 12: If the subquery is the right operand of a left outer

3408 ** join, make sure the subquery has no WHERE clause.

3409 ** An examples of why this is not allowed:

3410 **

3411 ** t1 LEFT OUTER JOIN (SELECT * FROM t2 WHERE t2.x>0)

3412 **

3413 ** If we flatten the above, we would get

3414 **

3415 ** (t1 LEFT OUTER JOIN t2) WHERE t2.x>0

3416 **

3417 ** But the t2.x>0 test will always fail on a NULL row of t2, which

3418 ** effectively converts the OUTER JOIN into an INNER JOIN.

3419 **

3420 ** THIS OVERRIDES OBSOLETE COMMENTS 1 AND 2 ABOVE:

3421 ** Ticket #3300 shows that flattening the right term of a LEFT JOIN

3422 ** is fraught with danger. Best to avoid the whole thing. If the

3423 ** subquery is the right term of a LEFT JOIN, then do not flatten.

3424 */

3425 if( (pSubitem->fg.jointype & JT_OUTER)!=0 ){

3426 return 0;

3427 }

3428

3429 /* Restriction 17: If the sub-query is a compound SELECT, then it must

3430 ** use only the UNION ALL operator. And none of the simple select queries

3431 ** that make up the compound SELECT are allowed to be aggregate or distinct

3432 ** queries.

3433 */

3434 if( pSub->pPrior ){

3435 if( pSub->pOrderBy ){

3436 return 0; /* Restriction 20 */

3437 }

3438 if( isAgg \|\| (p->selFlags & SF_Distinct)!=0 \|\| pSrc->nSrc!=1 ){

3439 return 0;

3440 }

3441 for(pSub1=pSub; pSub1; pSub1=pSub1->pPrior){

3442 testcase( (pSub1->selFlags & (SF_Distinct\|SF_Aggregate))==SF_Distinct );

3443 testcase( (pSub1->selFlags & (SF_Distinct\|SF_Aggregate))==SF_Aggregate );

3444 assert( pSub->pSrc!=0 );

3445 assert( pSub->pEList->nExpr==pSub1->pEList->nExpr );

3446 if( (pSub1->selFlags & (SF_Distinct\|SF_Aggregate))!=0

3447 \|\| (pSub1->pPrior && pSub1->op!=TK_ALL)

3448 \|\| pSub1->pSrc->nSrc<1

3449 ){

3450 return 0;

3451 }

3452 testcase( pSub1->pSrc->nSrc>1 );

3453 }

3454

3455 /* Restriction 18. */

3456 if( p->pOrderBy ){

3457 int ii;

3458 for(ii=0; ii<p->pOrderBy->nExpr; ii++){

3459 if( p->pOrderBy->a[ii].u.x.iOrderByCol==0 ) return 0;

3460 }

3461 }

3462 }

3463

3464 /*** If we reach this point, flattening is permitted. ***/

3465 SELECTTRACE(1,pParse,p,("flatten %s.%p from term %d\n",

3466 pSub->zSelName, pSub, iFrom));

3467

3468 /* Authorize the subquery */

3469 pParse->zAuthContext = pSubitem->zName;

3470 TESTONLY(i =) sqlite3AuthCheck(pParse, SQLITE_SELECT, 0, 0, 0);

3471 testcase( i==SQLITE_DENY );

3472 pParse->zAuthContext = zSavedAuthContext;

3473

3474 /* If the sub-query is a compound SELECT statement, then (by restrictions

3475 ** 17 and 18 above) it must be a UNION ALL and the parent query must

3476 ** be of the form:

3477 **

3478 ** SELECT <expr-list> FROM (<sub-query>) <where-clause>

3479 **

3480 ** followed by any ORDER BY, LIMIT and/or OFFSET clauses. This block

3481 ** creates N-1 copies of the parent query without any ORDER BY, LIMIT or

3482 ** OFFSET clauses and joins them to the left-hand-side of the original

3483 ** using UNION ALL operators. In this case N is the number of simple

3484 ** select statements in the compound sub-query.

3485 **

3486 ** Example:

3487 **

3488 ** SELECT a+1 FROM (

3489 ** SELECT x FROM tab

3490 ** UNION ALL

3491 ** SELECT y FROM tab

3492 ** UNION ALL

3493 ** SELECT abs(z*2) FROM tab2

3494 ** ) WHERE a!=5 ORDER BY 1

3495 **

3496 ** Transformed into:

3497 **

3498 ** SELECT x+1 FROM tab WHERE x+1!=5

3499 ** UNION ALL

3500 ** SELECT y+1 FROM tab WHERE y+1!=5

3501 ** UNION ALL

3502 ** SELECT abs(z2)+1 FROM tab2 WHERE abs(z2)+1!=5

3503 ** ORDER BY 1

3504 **

3505 ** We call this the "compound-subquery flattening".

3506 */

3507 for(pSub=pSub->pPrior; pSub; pSub=pSub->pPrior){

3508 Select *pNew;

3509 ExprList *pOrderBy = p->pOrderBy;

3510 Expr *pLimit = p->pLimit;

3511 Expr *pOffset = p->pOffset;

3512 Select *pPrior = p->pPrior;

3513 p->pOrderBy = 0;

3514 p->pSrc = 0;

3515 p->pPrior = 0;

3516 p->pLimit = 0;

3517 p->pOffset = 0;

3518 pNew = sqlite3SelectDup(db, p, 0);

3519 sqlite3SelectSetName(pNew, pSub->zSelName);

3520 p->pOffset = pOffset;

3521 p->pLimit = pLimit;

3522 p->pOrderBy = pOrderBy;

3523 p->pSrc = pSrc;

3524 p->op = TK_ALL;

3525 if( pNew==0 ){

3526 p->pPrior = pPrior;

3527 }else{

3528 pNew->pPrior = pPrior;

3529 if( pPrior ) pPrior->pNext = pNew;

3530 pNew->pNext = p;

3531 p->pPrior = pNew;

3532 SELECTTRACE(2,pParse,p,

3533 ("compound-subquery flattener creates %s.%p as peer\n",

3534 pNew->zSelName, pNew));

3535 }

3536 if( db->mallocFailed ) return 1;

3537 }

3538

3539 /* Begin flattening the iFrom-th entry of the FROM clause

3540 ** in the outer query.

3541 */

3542 pSub = pSub1 = pSubitem->pSelect;

3543

3544 /* Delete the transient table structure associated with the

3545 ** subquery

3546 */

3547 sqlite3DbFree(db, pSubitem->zDatabase);

3548 sqlite3DbFree(db, pSubitem->zName);

3549 sqlite3DbFree(db, pSubitem->zAlias);

3550 pSubitem->zDatabase = 0;

3551 pSubitem->zName = 0;

3552 pSubitem->zAlias = 0;

3553 pSubitem->pSelect = 0;

3554

3555 /* Defer deleting the Table object associated with the

3556 ** subquery until code generation is

3557 ** complete, since there may still exist Expr.pTab entries that

3558 ** refer to the subquery even after flattening. Ticket #3346.

3559 **

3560 ** pSubitem->pTab is always non-NULL by test restrictions and tests above.

3561 */

3562 if( ALWAYS(pSubitem->pTab!=0) ){

3563 Table *pTabToDel = pSubitem->pTab;

3564 if( pTabToDel->nRef==1 ){

3565 Parse *pToplevel = sqlite3ParseToplevel(pParse);

3566 pTabToDel->pNextZombie = pToplevel->pZombieTab;

3567 pToplevel->pZombieTab = pTabToDel;

3568 }else{

3569 pTabToDel->nRef--;

3570 }

3571 pSubitem->pTab = 0;

3572 }

3573

3574 /* The following loop runs once for each term in a compound-subquery

3575 ** flattening (as described above). If we are doing a different kind

3576 ** of flattening - a flattening other than a compound-subquery flattening -

3577 ** then this loop only runs once.

3578 **

3579 ** This loop moves all of the FROM elements of the subquery into the

3580 ** the FROM clause of the outer query. Before doing this, remember

3581 ** the cursor number for the original outer query FROM element in

3582 ** iParent. The iParent cursor will never be used. Subsequent code

3583 ** will scan expressions looking for iParent references and replace

3584 ** those references with expressions that resolve to the subquery FROM

3585 ** elements we are now copying in.

3586 */

3587 for(pParent=p; pParent; pParent=pParent->pPrior, pSub=pSub->pPrior){

3588 int nSubSrc;

3589 u8 jointype = 0;

3590 pSubSrc = pSub->pSrc; /* FROM clause of subquery */

3591 nSubSrc = pSubSrc->nSrc; /* Number of terms in subquery FROM clause */

3592 pSrc = pParent->pSrc; /* FROM clause of the outer query */

3593

3594 if( pSrc ){

3595 assert( pParent==p ); /* First time through the loop */

3596 jointype = pSubitem->fg.jointype;

3597 }else{

3598 assert( pParent!=p ); /* 2nd and subsequent times through the loop */

3599 pSrc = pParent->pSrc = sqlite3SrcListAppend(db, 0, 0, 0);

3600 if( pSrc==0 ){

3601 assert( db->mallocFailed );

3602 break;

3603 }

3604 }

3605

3606 /* The subquery uses a single slot of the FROM clause of the outer

3607 ** query. If the subquery has more than one element in its FROM clause,

3608 ** then expand the outer query to make space for it to hold all elements

3609 ** of the subquery.

3610 **

3611 ** Example:

3612 **

3613 ** SELECT * FROM tabA, (SELECT * FROM sub1, sub2), tabB;

3614 **

3615 ** The outer query has 3 slots in its FROM clause. One slot of the

3616 ** outer query (the middle slot) is used by the subquery. The next

3617 ** block of code will expand the outer query FROM clause to 4 slots.

3618 ** The middle slot is expanded to two slots in order to make space

3619 ** for the two elements in the FROM clause of the subquery.

3620 */

3621 if( nSubSrc>1 ){

3622 pParent->pSrc = pSrc = sqlite3SrcListEnlarge(db, pSrc, nSubSrc-1,iFrom+1);

3623 if( db->mallocFailed ){

3624 break;

3625 }

3626 }

3627

3628 /* Transfer the FROM clause terms from the subquery into the

3629 ** outer query.

3630 */

3631 for(i=0; i<nSubSrc; i++){

3632 sqlite3IdListDelete(db, pSrc->a[i+iFrom].pUsing);

3633 assert( pSrc->a[i+iFrom].fg.isTabFunc==0 );

3634 pSrc->a[i+iFrom] = pSubSrc->a[i];

3635 memset(&pSubSrc->a[i], 0, sizeof(pSubSrc->a[i]));

3636 }

3637 pSrc->a[iFrom].fg.jointype = jointype;

3638

3639 /* Now begin substituting subquery result set expressions for

3640 ** references to the iParent in the outer query.

3641 **

3642 ** Example:

3643 **

3644 ** SELECT a+5, b10 FROM (SELECT x3 AS a, y+10 AS b FROM t1) WHERE a>b;

3645 ** \ \_____________ subquery __________/ /

3646 ** \_____________________ outer query ______________________________/

3647 **

3648 ** We look at every expression in the outer query and every place we see

3649 ** "a" we substitute "x*3" and every place we see "b" we substitute "y+10".

3650 */

3651 pList = pParent->pEList;

3652 for(i=0; i<pList->nExpr; i++){

3653 if( pList->a[i].zName==0 ){

3654 char *zName = sqlite3DbStrDup(db, pList->a[i].zSpan);

3655 sqlite3Dequote(zName);

3656 pList->a[i].zName = zName;

3657 }

3658 }

3659 if( pSub->pOrderBy ){

3660 /* At this point, any non-zero iOrderByCol values indicate that the

3661 ** ORDER BY column expression is identical to the iOrderByCol'th

3662 ** expression returned by SELECT statement pSub. Since these values

3663 ** do not necessarily correspond to columns in SELECT statement pParent,

3664 ** zero them before transfering the ORDER BY clause.

3665 **

3666 ** Not doing this may cause an error if a subsequent call to this

3667 ** function attempts to flatten a compound sub-query into pParent

3668 ** (the only way this can happen is if the compound sub-query is

3669 ** currently part of pSub->pSrc). See ticket [d11a6e908f]. */

3670 ExprList *pOrderBy = pSub->pOrderBy;

3671 for(i=0; i<pOrderBy->nExpr; i++){

3672 pOrderBy->a[i].u.x.iOrderByCol = 0;

3673 }

3674 assert( pParent->pOrderBy==0 );

3675 assert( pSub->pPrior==0 );

3676 pParent->pOrderBy = pOrderBy;

3677 pSub->pOrderBy = 0;

3678 }

3679 pWhere = sqlite3ExprDup(db, pSub->pWhere, 0);

3680 if( subqueryIsAgg ){

3681 assert( pParent->pHaving==0 );

3682 pParent->pHaving = pParent->pWhere;

3683 pParent->pWhere = pWhere;

3684 pParent->pHaving = sqlite3ExprAnd(db, pParent->pHaving,

3685 sqlite3ExprDup(db, pSub->pHaving, 0));

3686 assert( pParent->pGroupBy==0 );

3687 pParent->pGroupBy = sqlite3ExprListDup(db, pSub->pGroupBy, 0);

3688 }else{

3689 pParent->pWhere = sqlite3ExprAnd(db, pParent->pWhere, pWhere);

3690 }

3691 substSelect(db, pParent, iParent, pSub->pEList, 0);

3692

3693 /* The flattened query is distinct if either the inner or the

3694 ** outer query is distinct.

3695 */

3696 pParent->selFlags \|= pSub->selFlags & SF_Distinct;

3697

3698 /*

3699 ** SELECT ... FROM (SELECT ... LIMIT a OFFSET b) LIMIT x OFFSET y;

3700 **

3701 ** One is tempted to try to add a and b to combine the limits. But this

3702 ** does not work if either limit is negative.

3703 */

3704 if( pSub->pLimit ){

3705 pParent->pLimit = pSub->pLimit;

3706 pSub->pLimit = 0;

3707 }

3708 }

3709

3710 /* Finially, delete what is left of the subquery and return

3711 ** success.

3712 */

3713 sqlite3SelectDelete(db, pSub1);

3714

3715 #if SELECTTRACE_ENABLED

3716 if( sqlite3SelectTrace & 0x100 ){

3717 SELECTTRACE(0x100,pParse,p,("After flattening:\n"));

3718 sqlite3TreeViewSelect(0, p, 0);

3719 }

3720 #endif

3721

3722 return 1;

3723 }

3724 #endif /* !defined(SQLITE_OMIT_SUBQUERY) \|\| !defined(SQLITE_OMIT_VIEW) */

3725

3726

3727

3728 #if !defined(SQLITE_OMIT_SUBQUERY) \|\| !defined(SQLITE_OMIT_VIEW)

3729 /*

3730 ** Make copies of relevant WHERE clause terms of the outer query into

3731 ** the WHERE clause of subquery. Example:

3732 **

3733 ** SELECT * FROM (SELECT a AS x, c-d AS y FROM t1) WHERE x=5 AND y=10;

3734 **

3735 ** Transformed into:

3736 **

3737 ** SELECT * FROM (SELECT a AS x, c-d AS y FROM t1 WHERE a=5 AND c-d=10)

3738 ** WHERE x=5 AND y=10;

3739 **

3740 ** The hope is that the terms added to the inner query will make it more

3741 ** efficient.

3742 **

3743 ** Do not attempt this optimization if:

3744 **

3745 ** (1) The inner query is an aggregate. (In that case, we'd really want

3746 ** to copy the outer WHERE-clause terms onto the HAVING clause of the

3747 ** inner query. But they probably won't help there so do not bother.)

3748 **

3749 ** (2) The inner query is the recursive part of a common table expression.

3750 **

3751 ** (3) The inner query has a LIMIT clause (since the changes to the WHERE

3752 ** close would change the meaning of the LIMIT).

3753 **

3754 ** (4) The inner query is the right operand of a LEFT JOIN. (The caller

3755 ** enforces this restriction since this routine does not have enough

3756 ** information to know.)

3757 **

3758 ** (5) The WHERE clause expression originates in the ON or USING clause

3759 ** of a LEFT JOIN.

3760 **

3761 ** Return 0 if no changes are made and non-zero if one or more WHERE clause

3762 ** terms are duplicated into the subquery.

3763 */

3764 static int pushDownWhereTerms(

3765 sqlite3 db, / The database connection (for malloc()) */

3766 Select pSubq, / The subquery whose WHERE clause is to be augmented */

3767 Expr pWhere, / The WHERE clause of the outer query */

3768 int iCursor /* Cursor number of the subquery */

3769 ){

3770 Expr *pNew;

3771 int nChng = 0;

3772 if( pWhere==0 ) return 0;

3773 if( (pSubq->selFlags & (SF_Aggregate\|SF_Recursive))!=0 ){

3774 return 0; /* restrictions (1) and (2) */

3775 }

3776 if( pSubq->pLimit!=0 ){

3777 return 0; /* restriction (3) */

3778 }

3779 while( pWhere->op==TK_AND ){

3780 nChng += pushDownWhereTerms(db, pSubq, pWhere->pRight, iCursor);

3781 pWhere = pWhere->pLeft;

3782 }

3783 if( ExprHasProperty(pWhere,EP_FromJoin) ) return 0; /* restriction 5 */

3784 if( sqlite3ExprIsTableConstant(pWhere, iCursor) ){

3785 nChng++;

3786 while( pSubq ){

3787 pNew = sqlite3ExprDup(db, pWhere, 0);

3788 pNew = substExpr(db, pNew, iCursor, pSubq->pEList);

3789 pSubq->pWhere = sqlite3ExprAnd(db, pSubq->pWhere, pNew);

3790 pSubq = pSubq->pPrior;

3791 }

3792 }

3793 return nChng;

3794 }

3795 #endif /* !defined(SQLITE_OMIT_SUBQUERY) \|\| !defined(SQLITE_OMIT_VIEW) */

3796

3797 /*

3798 ** Based on the contents of the AggInfo structure indicated by the first

3799 ** argument, this function checks if the following are true:

3800 **

3801 ** * the query contains just a single aggregate function,

3802 ** * the aggregate function is either min() or max(), and

3803 ** * the argument to the aggregate function is a column value.

3804 **

3805 ** If all of the above are true, then WHERE_ORDERBY_MIN or WHERE_ORDERBY_MAX

3806 ** is returned as appropriate. Also, *ppMinMax is set to point to the

3807 ** list of arguments passed to the aggregate before returning.

3808 **

3809 ** Or, if the conditions above are not met, *ppMinMax is set to 0 and

3810 ** WHERE_ORDERBY_NORMAL is returned.

3811 */

3812 static u8 minMaxQuery(AggInfo pAggInfo, ExprList *ppMinMax){

3813 int eRet = WHERE_ORDERBY_NORMAL; /* Return value */

3814

3815 *ppMinMax = 0;

3816 if( pAggInfo->nFunc==1 ){

3817 Expr pExpr = pAggInfo->aFunc[0].pExpr; / Aggregate function */

3818 ExprList pEList = pExpr->x.pList; / Arguments to agg function */

3819

3820 assert( pExpr->op==TK_AGG_FUNCTION );

3821 if( pEList && pEList->nExpr==1 && pEList->a[0].pExpr->op==TK_AGG_COLUMN ){

3822 const char *zFunc = pExpr->u.zToken;

3823 if( sqlite3StrICmp(zFunc, "min")==0 ){

3824 eRet = WHERE_ORDERBY_MIN;

3825 *ppMinMax = pEList;

3826 }else if( sqlite3StrICmp(zFunc, "max")==0 ){

3827 eRet = WHERE_ORDERBY_MAX;

3828 *ppMinMax = pEList;

3829 }

3830 }

3831 }

3832

3833 assert( ppMinMax==0 \|\| (ppMinMax)->nExpr==1 );

3834 return eRet;

3835 }

3836

3837 /*

3838 ** The select statement passed as the first argument is an aggregate query.

3839 ** The second argument is the associated aggregate-info object. This

3840 ** function tests if the SELECT is of the form:

3841 **

3842 ** SELECT count(*) FROM <tbl>

3843 **

3844 ** where table is a database table, not a sub-select or view. If the query

3845 ** does match this pattern, then a pointer to the Table object representing

3846 ** <tbl> is returned. Otherwise, 0 is returned.

3847 */

3848 static Table isSimpleCount(Select p, AggInfo *pAggInfo){

3849 Table *pTab;

3850 Expr *pExpr;

3851

3852 assert( !p->pGroupBy );

3853

3854 if( p->pWhere \|\| p->pEList->nExpr!=1

3855 \|\| p->pSrc->nSrc!=1 \|\| p->pSrc->a[0].pSelect

3856 ){

3857 return 0;

3858 }

3859 pTab = p->pSrc->a[0].pTab;

3860 pExpr = p->pEList->a[0].pExpr;

3861 assert( pTab && !pTab->pSelect && pExpr );

3862

3863 if( IsVirtual(pTab) ) return 0;

3864 if( pExpr->op!=TK_AGG_FUNCTION ) return 0;

3865 if( NEVER(pAggInfo->nFunc==0) ) return 0;

3866 if( (pAggInfo->aFunc[0].pFunc->funcFlags&SQLITE_FUNC_COUNT)==0 ) return 0;

3867 if( pExpr->flags&EP_Distinct ) return 0;

3868

3869 return pTab;

3870 }

3871

3872 /*

3873 ** If the source-list item passed as an argument was augmented with an

3874 ** INDEXED BY clause, then try to locate the specified index. If there

3875 ** was such a clause and the named index cannot be found, return

3876 ** SQLITE_ERROR and leave an error in pParse. Otherwise, populate

3877 ** pFrom->pIndex and return SQLITE_OK.

3878 */

3879 int sqlite3IndexedByLookup(Parse pParse, struct SrcList_item pFrom){

3880 if( pFrom->pTab && pFrom->fg.isIndexedBy ){

3881 Table *pTab = pFrom->pTab;

3882 char *zIndexedBy = pFrom->u1.zIndexedBy;

3883 Index *pIdx;

3884 for(pIdx=pTab->pIndex;

3885 pIdx && sqlite3StrICmp(pIdx->zName, zIndexedBy);

3886 pIdx=pIdx->pNext

3887 );

3888 if( !pIdx ){

3889 sqlite3ErrorMsg(pParse, "no such index: %s", zIndexedBy, 0);

3890 pParse->checkSchema = 1;

3891 return SQLITE_ERROR;

3892 }

3893 pFrom->pIBIndex = pIdx;

3894 }

3895 return SQLITE_OK;

3896 }

3897 /*

3898 ** Detect compound SELECT statements that use an ORDER BY clause with

3899 ** an alternative collating sequence.

3900 **

3901 ** SELECT ... FROM t1 EXCEPT SELECT ... FROM t2 ORDER BY .. COLLATE ...

3902 **

3903 ** These are rewritten as a subquery:

3904 **

3905 ** SELECT * FROM (SELECT ... FROM t1 EXCEPT SELECT ... FROM t2)

3906 ** ORDER BY ... COLLATE ...

3907 **

3908 ** This transformation is necessary because the multiSelectOrderBy() routine

3909 ** above that generates the code for a compound SELECT with an ORDER BY clause

3910 ** uses a merge algorithm that requires the same collating sequence on the

3911 ** result columns as on the ORDER BY clause. See ticket

3912 ** http://www.sqlite.org/src/info/6709574d2a

3913 **

3914 ** This transformation is only needed for EXCEPT, INTERSECT, and UNION.

3915 ** The UNION ALL operator works fine with multiSelectOrderBy() even when

3916 ** there are COLLATE terms in the ORDER BY.

3917 */

3918 static int convertCompoundSelectToSubquery(Walker pWalker, Select p){

3919 int i;

3920 Select *pNew;

3921 Select *pX;

3922 sqlite3 *db;

3923 struct ExprList_item *a;

3924 SrcList *pNewSrc;

3925 Parse *pParse;

3926 Token dummy;

3927

3928 if( p->pPrior==0 ) return WRC_Continue;

3929 if( p->pOrderBy==0 ) return WRC_Continue;

3930 for(pX=p; pX && (pX->op==TK_ALL \|\| pX->op==TK_SELECT); pX=pX->pPrior){}

3931 if( pX==0 ) return WRC_Continue;

3932 a = p->pOrderBy->a;

3933 for(i=p->pOrderBy->nExpr-1; i>=0; i--){

3934 if( a[i].pExpr->flags & EP_Collate ) break;

3935 }

3936 if( i<0 ) return WRC_Continue;

3937

3938 /* If we reach this point, that means the transformation is required. */

3939

3940 pParse = pWalker->pParse;

3941 db = pParse->db;

3942 pNew = sqlite3DbMallocZero(db, sizeof(*pNew) );

3943 if( pNew==0 ) return WRC_Abort;

3944 memset(&dummy, 0, sizeof(dummy));

3945 pNewSrc = sqlite3SrcListAppendFromTerm(pParse,0,0,0,&dummy,pNew,0,0);

3946 if( pNewSrc==0 ) return WRC_Abort;

3947 pNew = p;

3948 p->pSrc = pNewSrc;

3949 p->pEList = sqlite3ExprListAppend(pParse, 0, sqlite3Expr(db, TK_ASTERISK, 0));

3950 p->op = TK_SELECT;

3951 p->pWhere = 0;

3952 pNew->pGroupBy = 0;

3953 pNew->pHaving = 0;

3954 pNew->pOrderBy = 0;

3955 p->pPrior = 0;

3956 p->pNext = 0;

3957 p->pWith = 0;

3958 p->selFlags &= ~SF_Compound;

3959 assert( (p->selFlags & SF_Converted)==0 );

3960 p->selFlags \|= SF_Converted;

3961 assert( pNew->pPrior!=0 );

3962 pNew->pPrior->pNext = pNew;

3963 pNew->pLimit = 0;

3964 pNew->pOffset = 0;

3965 return WRC_Continue;

3966 }

3967

3968 /*

3969 ** Check to see if the FROM clause term pFrom has table-valued function

3970 ** arguments. If it does, leave an error message in pParse and return

3971 ** non-zero, since pFrom is not allowed to be a table-valued function.

3972 */

3973 static int cannotBeFunction(Parse pParse, struct SrcList_item pFrom){

3974 if( pFrom->fg.isTabFunc ){

3975 sqlite3ErrorMsg(pParse, "'%s' is not a function", pFrom->zName);

3976 return 1;

3977 }

3978 return 0;

3979 }

3980

3981 #ifndef SQLITE_OMIT_CTE

3982 /*

3983 ** Argument pWith (which may be NULL) points to a linked list of nested

3984 ** WITH contexts, from inner to outermost. If the table identified by

3985 ** FROM clause element pItem is really a common-table-expression (CTE)

3986 ** then return a pointer to the CTE definition for that table. Otherwise

3987 ** return NULL.

3988 **

3989 ** If a non-NULL value is returned, set *ppContext to point to the With

3990 ** object that the returned CTE belongs to.

3991 */

3992 static struct Cte *searchWith(

3993 With pWith, / Current innermost WITH clause */

3994 struct SrcList_item pItem, / FROM clause element to resolve */

3995 With *ppContext / OUT: WITH clause return value belongs to */

3996 ){

3997 const char *zName;

3998 if( pItem->zDatabase==0 && (zName = pItem->zName)!=0 ){

3999 With *p;

4000 for(p=pWith; p; p=p->pOuter){

4001 int i;

4002 for(i=0; i<p->nCte; i++){

4003 if( sqlite3StrICmp(zName, p->a[i].zName)==0 ){

4004 *ppContext = p;

4005 return &p->a[i];

4006 }

4007 }

4008 }

4009 }

4010 return 0;

4011 }

4012

4013 /* The code generator maintains a stack of active WITH clauses

4014 ** with the inner-most WITH clause being at the top of the stack.

4015 **

4016 ** This routine pushes the WITH clause passed as the second argument

4017 ** onto the top of the stack. If argument bFree is true, then this

4018 ** WITH clause will never be popped from the stack. In this case it

4019 ** should be freed along with the Parse object. In other cases, when

4020 ** bFree==0, the With object will be freed along with the SELECT

4021 ** statement with which it is associated.

4022 */

4023 void sqlite3WithPush(Parse pParse, With pWith, u8 bFree){

4024 assert( bFree==0 \|\| (pParse->pWith==0 && pParse->pWithToFree==0) );

4025 if( pWith ){

4026 assert( pParse->pWith!=pWith );

4027 pWith->pOuter = pParse->pWith;

4028 pParse->pWith = pWith;

4029 if( bFree ) pParse->pWithToFree = pWith;

4030 }

4031 }

4032

4033 /*

4034 ** This function checks if argument pFrom refers to a CTE declared by

4035 ** a WITH clause on the stack currently maintained by the parser. And,

4036 ** if currently processing a CTE expression, if it is a recursive

4037 ** reference to the current CTE.

4038 **

4039 ** If pFrom falls into either of the two categories above, pFrom->pTab

4040 ** and other fields are populated accordingly. The caller should check

4041 ** (pFrom->pTab!=0) to determine whether or not a successful match

4042 ** was found.

4043 **

4044 ** Whether or not a match is found, SQLITE_OK is returned if no error

4045 ** occurs. If an error does occur, an error message is stored in the

4046 ** parser and some error code other than SQLITE_OK returned.

4047 */

4048 static int withExpand(

4049 Walker *pWalker,

4050 struct SrcList_item *pFrom

4051 ){

4052 Parse *pParse = pWalker->pParse;

4053 sqlite3 *db = pParse->db;

4054 struct Cte pCte; / Matched CTE (or NULL if no match) */

4055 With pWith; / WITH clause that pCte belongs to */

4056

4057 assert( pFrom->pTab==0 );

4058

4059 pCte = searchWith(pParse->pWith, pFrom, &pWith);

4060 if( pCte ){

4061 Table *pTab;

4062 ExprList *pEList;

4063 Select *pSel;

4064 Select pLeft; / Left-most SELECT statement */

4065 int bMayRecursive; /* True if compound joined by UNION [ALL] */

4066 With pSavedWith; / Initial value of pParse->pWith */

4067

4068 /* If pCte->zCteErr is non-NULL at this point, then this is an illegal

4069 ** recursive reference to CTE pCte. Leave an error in pParse and return

4070 ** early. If pCte->zCteErr is NULL, then this is not a recursive reference.

4071 ** In this case, proceed. */

4072 if( pCte->zCteErr ){

4073 sqlite3ErrorMsg(pParse, pCte->zCteErr, pCte->zName);

4074 return SQLITE_ERROR;

4075 }

4076 if( cannotBeFunction(pParse, pFrom) ) return SQLITE_ERROR;

4077

4078 assert( pFrom->pTab==0 );

4079 pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table));

4080 if( pTab==0 ) return WRC_Abort;

4081 pTab->nRef = 1;

4082 pTab->zName = sqlite3DbStrDup(db, pCte->zName);

4083 pTab->iPKey = -1;

4084 pTab->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) );

4085 pTab->tabFlags \|= TF_Ephemeral \| TF_NoVisibleRowid;

4086 pFrom->pSelect = sqlite3SelectDup(db, pCte->pSelect, 0);

4087 if( db->mallocFailed ) return SQLITE_NOMEM;

4088 assert( pFrom->pSelect );

4089

4090 /* Check if this is a recursive CTE. */

4091 pSel = pFrom->pSelect;

4092 bMayRecursive = ( pSel->op==TK_ALL \|\| pSel->op==TK_UNION );

4093 if( bMayRecursive ){

4094 int i;

4095 SrcList *pSrc = pFrom->pSelect->pSrc;

4096 for(i=0; i<pSrc->nSrc; i++){

4097 struct SrcList_item *pItem = &pSrc->a[i];

4098 if( pItem->zDatabase==0

4099 && pItem->zName!=0

4100 && 0==sqlite3StrICmp(pItem->zName, pCte->zName)

4101 ){

4102 pItem->pTab = pTab;

4103 pItem->fg.isRecursive = 1;

4104 pTab->nRef++;

4105 pSel->selFlags \|= SF_Recursive;

4106 }

4107 }

4108 }

4109

4110 /* Only one recursive reference is permitted. */

4111 if( pTab->nRef>2 ){

4112 sqlite3ErrorMsg(

4113 pParse, "multiple references to recursive table: %s", pCte->zName

4114 );

4115 return SQLITE_ERROR;

4116 }

4117 assert( pTab->nRef==1 \|\| ((pSel->selFlags&SF_Recursive) && pTab->nRef==2 ));

4118

4119 pCte->zCteErr = "circular reference: %s";

4120 pSavedWith = pParse->pWith;

4121 pParse->pWith = pWith;

4122 sqlite3WalkSelect(pWalker, bMayRecursive ? pSel->pPrior : pSel);

4123 pParse->pWith = pWith;

4124

4125 for(pLeft=pSel; pLeft->pPrior; pLeft=pLeft->pPrior);

4126 pEList = pLeft->pEList;

4127 if( pCte->pCols ){

4128 if( pEList && pEList->nExpr!=pCte->pCols->nExpr ){

4129 sqlite3ErrorMsg(pParse, "table %s has %d values for %d columns",

4130 pCte->zName, pEList->nExpr, pCte->pCols->nExpr

4131 );

4132 pParse->pWith = pSavedWith;

4133 return SQLITE_ERROR;

4134 }

4135 pEList = pCte->pCols;

4136 }

4137

4138 sqlite3ColumnsFromExprList(pParse, pEList, &pTab->nCol, &pTab->aCol);

4139 if( bMayRecursive ){

4140 if( pSel->selFlags & SF_Recursive ){

4141 pCte->zCteErr = "multiple recursive references: %s";

4142 }else{

4143 pCte->zCteErr = "recursive reference in a subquery: %s";

4144 }

4145 sqlite3WalkSelect(pWalker, pSel);

4146 }

4147 pCte->zCteErr = 0;

4148 pParse->pWith = pSavedWith;

4149 }

4150

4151 return SQLITE_OK;

4152 }

4153 #endif

4154

4155 #ifndef SQLITE_OMIT_CTE

4156 /*

4157 ** If the SELECT passed as the second argument has an associated WITH

4158 ** clause, pop it from the stack stored as part of the Parse object.

4159 **

4160 ** This function is used as the xSelectCallback2() callback by

4161 ** sqlite3SelectExpand() when walking a SELECT tree to resolve table

4162 ** names and other FROM clause elements.

4163 */

4164 static void selectPopWith(Walker pWalker, Select p){

4165 Parse *pParse = pWalker->pParse;

4166 With *pWith = findRightmost(p)->pWith;

4167 if( pWith!=0 ){

4168 assert( pParse->pWith==pWith );

4169 pParse->pWith = pWith->pOuter;

4170 }

4171 }

4172 #else

4173 #define selectPopWith 0

4174 #endif

4175

4176 /*

4177 ** This routine is a Walker callback for "expanding" a SELECT statement.

4178 ** "Expanding" means to do the following:

4179 **

4180 ** (1) Make sure VDBE cursor numbers have been assigned to every

4181 ** element of the FROM clause.

4182 **

4183 ** (2) Fill in the pTabList->a[].pTab fields in the SrcList that

4184 ** defines FROM clause. When views appear in the FROM clause,

4185 ** fill pTabList->a[].pSelect with a copy of the SELECT statement

4186 ** that implements the view. A copy is made of the view's SELECT

4187 ** statement so that we can freely modify or delete that statement

4188 ** without worrying about messing up the persistent representation

4189 ** of the view.

4190 **

4191 ** (3) Add terms to the WHERE clause to accommodate the NATURAL keyword

4192 ** on joins and the ON and USING clause of joins.

4193 **

4194 ** (4) Scan the list of columns in the result set (pEList) looking

4195 ** for instances of the "" operator or the TABLE. operator.

4196 ** If found, expand each "*" to be every column in every table

4197 ** and TABLE.* to be every column in TABLE.

4198 **

4199 */

4200 static int selectExpander(Walker pWalker, Select p){

4201 Parse *pParse = pWalker->pParse;

4202 int i, j, k;

4203 SrcList *pTabList;

4204 ExprList *pEList;

4205 struct SrcList_item *pFrom;

4206 sqlite3 *db = pParse->db;

4207 Expr pE, pRight, *pExpr;

4208 u16 selFlags = p->selFlags;

4209

4210 p->selFlags \|= SF_Expanded;

4211 if( db->mallocFailed ){

4212 return WRC_Abort;

4213 }

4214 if( NEVER(p->pSrc==0) \|\| (selFlags & SF_Expanded)!=0 ){

4215 return WRC_Prune;

4216 }

4217 pTabList = p->pSrc;

4218 pEList = p->pEList;

4219 if( pWalker->xSelectCallback2==selectPopWith ){

4220 sqlite3WithPush(pParse, findRightmost(p)->pWith, 0);

4221 }

4222

4223 /* Make sure cursor numbers have been assigned to all entries in

4224 ** the FROM clause of the SELECT statement.

4225 */

4226 sqlite3SrcListAssignCursors(pParse, pTabList);

4227

4228 /* Look up every table named in the FROM clause of the select. If

4229 ** an entry of the FROM clause is a subquery instead of a table or view,

4230 ** then create a transient table structure to describe the subquery.

4231 */

4232 for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){

4233 Table *pTab;

4234 assert( pFrom->fg.isRecursive==0 \|\| pFrom->pTab!=0 );

4235 if( pFrom->fg.isRecursive ) continue;

4236 assert( pFrom->pTab==0 );

4237 #ifndef SQLITE_OMIT_CTE

4238 if( withExpand(pWalker, pFrom) ) return WRC_Abort;

4239 if( pFrom->pTab ) {} else

4240 #endif

4241 if( pFrom->zName==0 ){

4242 #ifndef SQLITE_OMIT_SUBQUERY

4243 Select *pSel = pFrom->pSelect;

4244 /* A sub-query in the FROM clause of a SELECT */

4245 assert( pSel!=0 );

4246 assert( pFrom->pTab==0 );

4247 if( sqlite3WalkSelect(pWalker, pSel) ) return WRC_Abort;

4248 pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table));

4249 if( pTab==0 ) return WRC_Abort;

4250 pTab->nRef = 1;

4251 pTab->zName = sqlite3MPrintf(db, "sqlite_sq_%p", (void*)pTab);

4252 while( pSel->pPrior ){ pSel = pSel->pPrior; }

4253 sqlite3ColumnsFromExprList(pParse, pSel->pEList,&pTab->nCol,&pTab->aCol);

4254 pTab->iPKey = -1;

4255 pTab->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) );

4256 pTab->tabFlags \|= TF_Ephemeral;

4257 #endif

4258 }else{

4259 /* An ordinary table or view name in the FROM clause */

4260 assert( pFrom->pTab==0 );

4261 pFrom->pTab = pTab = sqlite3LocateTableItem(pParse, 0, pFrom);

4262 if( pTab==0 ) return WRC_Abort;

4263 if( pTab->nRef==0xffff ){

4264 sqlite3ErrorMsg(pParse, "too many references to \"%s\": max 65535",

4265 pTab->zName);

4266 pFrom->pTab = 0;

4267 return WRC_Abort;

4268 }

4269 pTab->nRef++;

4270 if( !IsVirtual(pTab) && cannotBeFunction(pParse, pFrom) ){

4271 return WRC_Abort;

4272 }

4273 #if !defined(SQLITE_OMIT_VIEW) \|\| !defined (SQLITE_OMIT_VIRTUALTABLE)

4274 if( IsVirtual(pTab) \|\| pTab->pSelect ){

4275 i16 nCol;

4276 if( sqlite3ViewGetColumnNames(pParse, pTab) ) return WRC_Abort;

4277 assert( pFrom->pSelect==0 );

4278 pFrom->pSelect = sqlite3SelectDup(db, pTab->pSelect, 0);

4279 sqlite3SelectSetName(pFrom->pSelect, pTab->zName);

4280 nCol = pTab->nCol;

4281 pTab->nCol = -1;

4282 sqlite3WalkSelect(pWalker, pFrom->pSelect);

4283 pTab->nCol = nCol;

4284 }

4285 #endif

4286 }

4287

4288 /* Locate the index named by the INDEXED BY clause, if any. */

4289 if( sqlite3IndexedByLookup(pParse, pFrom) ){

4290 return WRC_Abort;

4291 }

4292 }

4293

4294 /* Process NATURAL keywords, and ON and USING clauses of joins.

4295 */

4296 if( db->mallocFailed \|\| sqliteProcessJoin(pParse, p) ){

4297 return WRC_Abort;

4298 }

4299

4300 /* For every "*" that occurs in the column list, insert the names of

4301 ** all columns in all tables. And for every TABLE.* insert the names

4302 ** of all columns in TABLE. The parser inserted a special expression

4303 ** with the TK_ASTERISK operator for each "*" that it found in the column

4304 ** list. The following code just has to locate the TK_ASTERISK

4305 ** expressions and expand each one to the list of all columns in

4306 ** all tables.

4307 **

4308 ** The first loop just checks to see if there are any "*" operators

4309 ** that need expanding.

4310 */

4311 for(k=0; k<pEList->nExpr; k++){

4312 pE = pEList->a[k].pExpr;

4313 if( pE->op==TK_ASTERISK ) break;

4314 assert( pE->op!=TK_DOT \|\| pE->pRight!=0 );

4315 assert( pE->op!=TK_DOT \|\| (pE->pLeft!=0 && pE->pLeft->op==TK_ID) );

4316 if( pE->op==TK_DOT && pE->pRight->op==TK_ASTERISK ) break;

4317 }

4318 if( k<pEList->nExpr ){

4319 /*

4320 ** If we get here it means the result set contains one or more "*"

4321 ** operators that need to be expanded. Loop through each expression

4322 ** in the result set and expand them one by one.

4323 */

4324 struct ExprList_item *a = pEList->a;

4325 ExprList *pNew = 0;

4326 int flags = pParse->db->flags;

4327 int longNames = (flags & SQLITE_FullColNames)!=0

4328 && (flags & SQLITE_ShortColNames)==0;

4329

4330 for(k=0; k<pEList->nExpr; k++){

4331 pE = a[k].pExpr;

4332 pRight = pE->pRight;

4333 assert( pE->op!=TK_DOT \|\| pRight!=0 );

4334 if( pE->op!=TK_ASTERISK

4335 && (pE->op!=TK_DOT \|\| pRight->op!=TK_ASTERISK)

4336 ){

4337 /* This particular expression does not need to be expanded.

4338 */

4339 pNew = sqlite3ExprListAppend(pParse, pNew, a[k].pExpr);

4340 if( pNew ){

4341 pNew->a[pNew->nExpr-1].zName = a[k].zName;

4342 pNew->a[pNew->nExpr-1].zSpan = a[k].zSpan;

4343 a[k].zName = 0;

4344 a[k].zSpan = 0;

4345 }

4346 a[k].pExpr = 0;

4347 }else{

4348 /* This expression is a "" or a "TABLE." and needs to be

4349 ** expanded. */

4350 int tableSeen = 0; /* Set to 1 when TABLE matches */

4351 char zTName = 0; / text of name of TABLE */

4352 if( pE->op==TK_DOT ){

4353 assert( pE->pLeft!=0 );

4354 assert( !ExprHasProperty(pE->pLeft, EP_IntValue) );

4355 zTName = pE->pLeft->u.zToken;

4356 }

4357 for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){

4358 Table *pTab = pFrom->pTab;

4359 Select *pSub = pFrom->pSelect;

4360 char *zTabName = pFrom->zAlias;

4361 const char *zSchemaName = 0;

4362 int iDb;

4363 if( zTabName==0 ){

4364 zTabName = pTab->zName;

4365 }

4366 if( db->mallocFailed ) break;

4367 if( pSub==0 \|\| (pSub->selFlags & SF_NestedFrom)==0 ){

4368 pSub = 0;

4369 if( zTName && sqlite3StrICmp(zTName, zTabName)!=0 ){

4370 continue;

4371 }

4372 iDb = sqlite3SchemaToIndex(db, pTab->pSchema);

4373 zSchemaName = iDb>=0 ? db->aDb[iDb].zName : "*";

4374 }

4375 for(j=0; j<pTab->nCol; j++){

4376 char *zName = pTab->aCol[j].zName;

4377 char zColname; / The computed column name */

4378 char zToFree; / Malloced string that needs to be freed */

4379 Token sColname; /* Computed column name as a token */

4380

4381 assert( zName );

4382 if( zTName && pSub

4383 && sqlite3MatchSpanName(pSub->pEList->a[j].zSpan, 0, zTName, 0)==0

4384 ){

4385 continue;

4386 }

4387

4388 /* If a column is marked as 'hidden', omit it from the expanded

4389 ** result-set list unless the SELECT has the SF_IncludeHidden

4390 ** bit set.

4391 */

4392 if( (p->selFlags & SF_IncludeHidden)==0

4393 && IsHiddenColumn(&pTab->aCol[j])

4394 ){

4395 continue;

4396 }

4397 tableSeen = 1;

4398

4399 if( i>0 && zTName==0 ){

4400 if( (pFrom->fg.jointype & JT_NATURAL)!=0

4401 && tableAndColumnIndex(pTabList, i, zName, 0, 0)

4402 ){

4403 /* In a NATURAL join, omit the join columns from the

4404 ** table to the right of the join */

4405 continue;

4406 }

4407 if( sqlite3IdListIndex(pFrom->pUsing, zName)>=0 ){

4408 /* In a join with a USING clause, omit columns in the

4409 ** using clause from the table on the right. */

4410 continue;

4411 }

4412 }

4413 pRight = sqlite3Expr(db, TK_ID, zName);

4414 zColname = zName;

4415 zToFree = 0;

4416 if( longNames \|\| pTabList->nSrc>1 ){

4417 Expr *pLeft;

4418 pLeft = sqlite3Expr(db, TK_ID, zTabName);

4419 pExpr = sqlite3PExpr(pParse, TK_DOT, pLeft, pRight, 0);

4420 if( zSchemaName ){

4421 pLeft = sqlite3Expr(db, TK_ID, zSchemaName);

4422 pExpr = sqlite3PExpr(pParse, TK_DOT, pLeft, pExpr, 0);

4423 }

4424 if( longNames ){

4425 zColname = sqlite3MPrintf(db, "%s.%s", zTabName, zName);

4426 zToFree = zColname;

4427 }

4428 }else{

4429 pExpr = pRight;

4430 }

4431 pNew = sqlite3ExprListAppend(pParse, pNew, pExpr);

4432 sColname.z = zColname;

4433 sColname.n = sqlite3Strlen30(zColname);

4434 sqlite3ExprListSetName(pParse, pNew, &sColname, 0);

4435 if( pNew && (p->selFlags & SF_NestedFrom)!=0 ){

4436 struct ExprList_item *pX = &pNew->a[pNew->nExpr-1];

4437 if( pSub ){

4438 pX->zSpan = sqlite3DbStrDup(db, pSub->pEList->a[j].zSpan);

4439 testcase( pX->zSpan==0 );

4440 }else{

4441 pX->zSpan = sqlite3MPrintf(db, "%s.%s.%s",

4442 zSchemaName, zTabName, zColname);

4443 testcase( pX->zSpan==0 );

4444 }

4445 pX->bSpanIsTab = 1;

4446 }

4447 sqlite3DbFree(db, zToFree);

4448 }

4449 }

4450 if( !tableSeen ){

4451 if( zTName ){

4452 sqlite3ErrorMsg(pParse, "no such table: %s", zTName);

4453 }else{

4454 sqlite3ErrorMsg(pParse, "no tables specified");

4455 }

4456 }

4457 }

4458 }

4459 sqlite3ExprListDelete(db, pEList);

4460 p->pEList = pNew;

4461 }

4462 #if SQLITE_MAX_COLUMN

4463 if( p->pEList && p->pEList->nExpr>db->aLimit[SQLITE_LIMIT_COLUMN] ){

4464 sqlite3ErrorMsg(pParse, "too many columns in result set");

4465 return WRC_Abort;

4466 }

4467 #endif

4468 return WRC_Continue;

4469 }

4470

4471 /*

4472 ** No-op routine for the parse-tree walker.

4473 **

4474 ** When this routine is the Walker.xExprCallback then expression trees

4475 ** are walked without any actions being taken at each node. Presumably,

4476 ** when this routine is used for Walker.xExprCallback then

4477 ** Walker.xSelectCallback is set to do something useful for every

4478 ** subquery in the parser tree.

4479 */

4480 int sqlite3ExprWalkNoop(Walker NotUsed, Expr NotUsed2){

4481 UNUSED_PARAMETER2(NotUsed, NotUsed2);

4482 return WRC_Continue;

4483 }

4484

4485 /*

4486 ** This routine "expands" a SELECT statement and all of its subqueries.

4487 ** For additional information on what it means to "expand" a SELECT

4488 ** statement, see the comment on the selectExpand worker callback above.

4489 **

4490 ** Expanding a SELECT statement is the first step in processing a

4491 ** SELECT statement. The SELECT statement must be expanded before

4492 ** name resolution is performed.

4493 **

4494 ** If anything goes wrong, an error message is written into pParse.

4495 ** The calling function can detect the problem by looking at pParse->nErr

4496 ** and/or pParse->db->mallocFailed.

4497 */

4498 static void sqlite3SelectExpand(Parse pParse, Select pSelect){

4499 Walker w;

4500 memset(&w, 0, sizeof(w));

4501 w.xExprCallback = sqlite3ExprWalkNoop;

4502 w.pParse = pParse;

4503 if( pParse->hasCompound ){

4504 w.xSelectCallback = convertCompoundSelectToSubquery;

4505 sqlite3WalkSelect(&w, pSelect);

4506 }

4507 w.xSelectCallback = selectExpander;

4508 if( (pSelect->selFlags & SF_MultiValue)==0 ){

4509 w.xSelectCallback2 = selectPopWith;

4510 }

4511 sqlite3WalkSelect(&w, pSelect);

4512 }

4513

4514

4515 #ifndef SQLITE_OMIT_SUBQUERY

4516 /*

4517 ** This is a Walker.xSelectCallback callback for the sqlite3SelectTypeInfo()

4518 ** interface.

4519 **

4520 ** For each FROM-clause subquery, add Column.zType and Column.zColl

4521 ** information to the Table structure that represents the result set

4522 ** of that subquery.

4523 **

4524 ** The Table structure that represents the result set was constructed

4525 ** by selectExpander() but the type and collation information was omitted

4526 ** at that point because identifiers had not yet been resolved. This

4527 ** routine is called after identifier resolution.

4528 */

4529 static void selectAddSubqueryTypeInfo(Walker pWalker, Select p){

4530 Parse *pParse;

4531 int i;

4532 SrcList *pTabList;

4533 struct SrcList_item *pFrom;

4534

4535 assert( p->selFlags & SF_Resolved );

4536 assert( (p->selFlags & SF_HasTypeInfo)==0 );

4537 p->selFlags \|= SF_HasTypeInfo;

4538 pParse = pWalker->pParse;

4539 pTabList = p->pSrc;

4540 for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){

4541 Table *pTab = pFrom->pTab;

4542 assert( pTab!=0 );

4543 if( (pTab->tabFlags & TF_Ephemeral)!=0 ){

4544 /* A sub-query in the FROM clause of a SELECT */

4545 Select *pSel = pFrom->pSelect;

4546 if( pSel ){

4547 while( pSel->pPrior ) pSel = pSel->pPrior;

4548 selectAddColumnTypeAndCollation(pParse, pTab, pSel);

4549 }

4550 }

4551 }

4552 }

4553 #endif

4554

4555

4556 /*

4557 ** This routine adds datatype and collating sequence information to

4558 ** the Table structures of all FROM-clause subqueries in a

4559 ** SELECT statement.

4560 **

4561 ** Use this routine after name resolution.

4562 */

4563 static void sqlite3SelectAddTypeInfo(Parse pParse, Select pSelect){

4564 #ifndef SQLITE_OMIT_SUBQUERY

4565 Walker w;

4566 memset(&w, 0, sizeof(w));

4567 w.xSelectCallback2 = selectAddSubqueryTypeInfo;

4568 w.xExprCallback = sqlite3ExprWalkNoop;

4569 w.pParse = pParse;

4570 sqlite3WalkSelect(&w, pSelect);

4571 #endif

4572 }

4573

4574

4575 /*

4576 ** This routine sets up a SELECT statement for processing. The

4577 ** following is accomplished:

4578 **

4579 ** * VDBE Cursor numbers are assigned to all FROM-clause terms.

4580 ** * Ephemeral Table objects are created for all FROM-clause subqueries.

4581 ** * ON and USING clauses are shifted into WHERE statements

4582 ** * Wildcards "" and "TABLE." in result sets are expanded.

4583 ** * Identifiers in expression are matched to tables.

4584 **

4585 ** This routine acts recursively on all subqueries within the SELECT.

4586 */

4587 void sqlite3SelectPrep(

4588 Parse pParse, / The parser context */

4589 Select p, / The SELECT statement being coded. */

4590 NameContext pOuterNC / Name context for container */

4591 ){

4592 sqlite3 *db;

4593 if( NEVER(p==0) ) return;

4594 db = pParse->db;

4595 if( db->mallocFailed ) return;

4596 if( p->selFlags & SF_HasTypeInfo ) return;

4597 sqlite3SelectExpand(pParse, p);

4598 if( pParse->nErr \|\| db->mallocFailed ) return;

4599 sqlite3ResolveSelectNames(pParse, p, pOuterNC);

4600 if( pParse->nErr \|\| db->mallocFailed ) return;

4601 sqlite3SelectAddTypeInfo(pParse, p);

4602 }

4603

4604 /*

4605 ** Reset the aggregate accumulator.

4606 **

4607 ** The aggregate accumulator is a set of memory cells that hold

4608 ** intermediate results while calculating an aggregate. This

4609 ** routine generates code that stores NULLs in all of those memory

4610 ** cells.

4611 */

4612 static void resetAccumulator(Parse pParse, AggInfo pAggInfo){

4613 Vdbe *v = pParse->pVdbe;

4614 int i;

4615 struct AggInfo_func *pFunc;

4616 int nReg = pAggInfo->nFunc + pAggInfo->nColumn;

4617 if( nReg==0 ) return;

4618 #ifdef SQLITE_DEBUG

4619 /* Verify that all AggInfo registers are within the range specified by

4620 ** AggInfo.mnReg..AggInfo.mxReg */

4621 assert( nReg==pAggInfo->mxReg-pAggInfo->mnReg+1 );

4622 for(i=0; i<pAggInfo->nColumn; i++){

4623 assert( pAggInfo->aCol[i].iMem>=pAggInfo->mnReg

4624 && pAggInfo->aCol[i].iMem<=pAggInfo->mxReg );

4625 }

4626 for(i=0; i<pAggInfo->nFunc; i++){

4627 assert( pAggInfo->aFunc[i].iMem>=pAggInfo->mnReg

4628 && pAggInfo->aFunc[i].iMem<=pAggInfo->mxReg );

4629 }

4630 #endif

4631 sqlite3VdbeAddOp3(v, OP_Null, 0, pAggInfo->mnReg, pAggInfo->mxReg);

4632 for(pFunc=pAggInfo->aFunc, i=0; i<pAggInfo->nFunc; i++, pFunc++){

4633 if( pFunc->iDistinct>=0 ){

4634 Expr *pE = pFunc->pExpr;

4635 assert( !ExprHasProperty(pE, EP_xIsSelect) );

4636 if( pE->x.pList==0 \|\| pE->x.pList->nExpr!=1 ){

4637 sqlite3ErrorMsg(pParse, "DISTINCT aggregates must have exactly one "

4638 "argument");

4639 pFunc->iDistinct = -1;

4640 }else{

4641 KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pE->x.pList, 0, 0);

4642 sqlite3VdbeAddOp4(v, OP_OpenEphemeral, pFunc->iDistinct, 0, 0,

4643 (char*)pKeyInfo, P4_KEYINFO);

4644 }

4645 }

4646 }

4647 }

4648

4649 /*

4650 ** Invoke the OP_AggFinalize opcode for every aggregate function

4651 ** in the AggInfo structure.

4652 */

4653 static void finalizeAggFunctions(Parse pParse, AggInfo pAggInfo){

4654 Vdbe *v = pParse->pVdbe;

4655 int i;

4656 struct AggInfo_func *pF;

4657 for(i=0, pF=pAggInfo->aFunc; i<pAggInfo->nFunc; i++, pF++){

4658 ExprList *pList = pF->pExpr->x.pList;

4659 assert( !ExprHasProperty(pF->pExpr, EP_xIsSelect) );

4660 sqlite3VdbeAddOp4(v, OP_AggFinal, pF->iMem, pList ? pList->nExpr : 0, 0,

4661 (void*)pF->pFunc, P4_FUNCDEF);

4662 }

4663 }

4664

4665 /*

4666 ** Update the accumulator memory cells for an aggregate based on

4667 ** the current cursor position.

4668 */

4669 static void updateAccumulator(Parse pParse, AggInfo pAggInfo){

4670 Vdbe *v = pParse->pVdbe;

4671 int i;

4672 int regHit = 0;

4673 int addrHitTest = 0;

4674 struct AggInfo_func *pF;

4675 struct AggInfo_col *pC;

4676

4677 pAggInfo->directMode = 1;

4678 for(i=0, pF=pAggInfo->aFunc; i<pAggInfo->nFunc; i++, pF++){

4679 int nArg;

4680 int addrNext = 0;

4681 int regAgg;

4682 ExprList *pList = pF->pExpr->x.pList;

4683 assert( !ExprHasProperty(pF->pExpr, EP_xIsSelect) );

4684 if( pList ){

4685 nArg = pList->nExpr;

4686 regAgg = sqlite3GetTempRange(pParse, nArg);

4687 sqlite3ExprCodeExprList(pParse, pList, regAgg, 0, SQLITE_ECEL_DUP);

4688 }else{

4689 nArg = 0;

4690 regAgg = 0;

4691 }

4692 if( pF->iDistinct>=0 ){

4693 addrNext = sqlite3VdbeMakeLabel(v);

4694 testcase( nArg==0 ); /* Error condition */

4695 testcase( nArg>1 ); /* Also an error */

4696 codeDistinct(pParse, pF->iDistinct, addrNext, 1, regAgg);

4697 }

4698 if( pF->pFunc->funcFlags & SQLITE_FUNC_NEEDCOLL ){

4699 CollSeq *pColl = 0;

4700 struct ExprList_item *pItem;

4701 int j;

4702 assert( pList!=0 ); /* pList!=0 if pF->pFunc has NEEDCOLL */

4703 for(j=0, pItem=pList->a; !pColl && j<nArg; j++, pItem++){

4704 pColl = sqlite3ExprCollSeq(pParse, pItem->pExpr);

4705 }

4706 if( !pColl ){

4707 pColl = pParse->db->pDfltColl;

4708 }

4709 if( regHit==0 && pAggInfo->nAccumulator ) regHit = ++pParse->nMem;

4710 sqlite3VdbeAddOp4(v, OP_CollSeq, regHit, 0, 0, (char *)pColl, P4_COLLSEQ);

4711 }

4712 sqlite3VdbeAddOp4(v, OP_AggStep0, 0, regAgg, pF->iMem,

4713 (void*)pF->pFunc, P4_FUNCDEF);

4714 sqlite3VdbeChangeP5(v, (u8)nArg);

4715 sqlite3ExprCacheAffinityChange(pParse, regAgg, nArg);

4716 sqlite3ReleaseTempRange(pParse, regAgg, nArg);

4717 if( addrNext ){

4718 sqlite3VdbeResolveLabel(v, addrNext);

4719 sqlite3ExprCacheClear(pParse);

4720 }

4721 }

4722

4723 /* Before populating the accumulator registers, clear the column cache.

4724 ** Otherwise, if any of the required column values are already present

4725 ** in registers, sqlite3ExprCode() may use OP_SCopy to copy the value

4726 ** to pC->iMem. But by the time the value is used, the original register

4727 ** may have been used, invalidating the underlying buffer holding the

4728 ** text or blob value. See ticket [883034dcb5].

4729 **

4730 ** Another solution would be to change the OP_SCopy used to copy cached

4731 ** values to an OP_Copy.

4732 */

4733 if( regHit ){

4734 addrHitTest = sqlite3VdbeAddOp1(v, OP_If, regHit); VdbeCoverage(v);

4735 }

4736 sqlite3ExprCacheClear(pParse);

4737 for(i=0, pC=pAggInfo->aCol; i<pAggInfo->nAccumulator; i++, pC++){

4738 sqlite3ExprCode(pParse, pC->pExpr, pC->iMem);

4739 }

4740 pAggInfo->directMode = 0;

4741 sqlite3ExprCacheClear(pParse);

4742 if( addrHitTest ){

4743 sqlite3VdbeJumpHere(v, addrHitTest);

4744 }

4745 }

4746

4747 /*

4748 ** Add a single OP_Explain instruction to the VDBE to explain a simple

4749 ** count() query ("SELECT count() FROM pTab").

4750 */

4751 #ifndef SQLITE_OMIT_EXPLAIN

4752 static void explainSimpleCount(

4753 Parse pParse, / Parse context */

4754 Table pTab, / Table being queried */

4755 Index pIdx / Index used to optimize scan, or NULL */

4756 ){

4757 if( pParse->explain==2 ){

4758 int bCover = (pIdx!=0 && (HasRowid(pTab) \|\| !IsPrimaryKeyIndex(pIdx)));

4759 char *zEqp = sqlite3MPrintf(pParse->db, "SCAN TABLE %s%s%s",

4760 pTab->zName,

4761 bCover ? " USING COVERING INDEX " : "",

4762 bCover ? pIdx->zName : ""

4763 );

4764 sqlite3VdbeAddOp4(

4765 pParse->pVdbe, OP_Explain, pParse->iSelectId, 0, 0, zEqp, P4_DYNAMIC

4766 );

4767 }

4768 }

4769 #else

4770 # define explainSimpleCount(a,b,c)

4771 #endif

4772

4773 /*

4774 ** Generate code for the SELECT statement given in the p argument.

4775 **

4776 ** The results are returned according to the SelectDest structure.

4777 ** See comments in sqliteInt.h for further information.

4778 **

4779 ** This routine returns the number of errors. If any errors are

4780 ** encountered, then an appropriate error message is left in

4781 ** pParse->zErrMsg.

4782 **

4783 ** This routine does NOT free the Select structure passed in. The

4784 ** calling function needs to do that.

4785 */

4786 int sqlite3Select(

4787 Parse pParse, / The parser context */

4788 Select p, / The SELECT statement being coded. */

4789 SelectDest pDest / What to do with the query results */

4790 ){

4791 int i, j; /* Loop counters */

4792 WhereInfo pWInfo; / Return from sqlite3WhereBegin() */

4793 Vdbe v; / The virtual machine under construction */

4794 int isAgg; /* True for select lists like "count()" /

4795 ExprList pEList = 0; / List of columns to extract. */

4796 SrcList pTabList; / List of tables to select from */

4797 Expr pWhere; / The WHERE clause. May be NULL */

4798 ExprList pGroupBy; / The GROUP BY clause. May be NULL */

4799 Expr pHaving; / The HAVING clause. May be NULL */

4800 int rc = 1; /* Value to return from this function */

4801 DistinctCtx sDistinct; /* Info on how to code the DISTINCT keyword */

4802 SortCtx sSort; /* Info on how to code the ORDER BY clause */

4803 AggInfo sAggInfo; /* Information used by aggregate queries */

4804 int iEnd; /* Address of the end of the query */

4805 sqlite3 db; / The database connection */

4806

4807 #ifndef SQLITE_OMIT_EXPLAIN

4808 int iRestoreSelectId = pParse->iSelectId;

4809 pParse->iSelectId = pParse->iNextSelectId++;

4810 #endif

4811

4812 db = pParse->db;

4813 if( p==0 \|\| db->mallocFailed \|\| pParse->nErr ){

4814 return 1;

4815 }

4816 if( sqlite3AuthCheck(pParse, SQLITE_SELECT, 0, 0, 0) ) return 1;

4817 memset(&sAggInfo, 0, sizeof(sAggInfo));

4818 #if SELECTTRACE_ENABLED

4819 pParse->nSelectIndent++;

4820 SELECTTRACE(1,pParse,p, ("begin processing:\n"));

4821 if( sqlite3SelectTrace & 0x100 ){

4822 sqlite3TreeViewSelect(0, p, 0);

4823 }

4824 #endif

4825

4826 assert( p->pOrderBy==0 \|\| pDest->eDest!=SRT_DistFifo );

4827 assert( p->pOrderBy==0 \|\| pDest->eDest!=SRT_Fifo );

4828 assert( p->pOrderBy==0 \|\| pDest->eDest!=SRT_DistQueue );

4829 assert( p->pOrderBy==0 \|\| pDest->eDest!=SRT_Queue );

4830 if( IgnorableOrderby(pDest) ){

4831 assert(pDest->eDest==SRT_Exists \|\| pDest->eDest==SRT_Union \|\|

4832 pDest->eDest==SRT_Except \|\| pDest->eDest==SRT_Discard \|\|

4833 pDest->eDest==SRT_Queue \|\| pDest->eDest==SRT_DistFifo \|\|

4834 pDest->eDest==SRT_DistQueue \|\| pDest->eDest==SRT_Fifo);

4835 /* If ORDER BY makes no difference in the output then neither does

4836 ** DISTINCT so it can be removed too. */

4837 sqlite3ExprListDelete(db, p->pOrderBy);

4838 p->pOrderBy = 0;

4839 p->selFlags &= ~SF_Distinct;

4840 }

4841 sqlite3SelectPrep(pParse, p, 0);

4842 memset(&sSort, 0, sizeof(sSort));

4843 sSort.pOrderBy = p->pOrderBy;

4844 pTabList = p->pSrc;

4845 if( pParse->nErr \|\| db->mallocFailed ){

4846 goto select_end;

4847 }

4848 assert( p->pEList!=0 );

4849 isAgg = (p->selFlags & SF_Aggregate)!=0;

4850 #if SELECTTRACE_ENABLED

4851 if( sqlite3SelectTrace & 0x100 ){

4852 SELECTTRACE(0x100,pParse,p, ("after name resolution:\n"));

4853 sqlite3TreeViewSelect(0, p, 0);

4854 }

4855 #endif

4856

4857

4858 /* If writing to memory or generating a set

4859 ** only a single column may be output.

4860 */

4861 #ifndef SQLITE_OMIT_SUBQUERY

4862 if( checkForMultiColumnSelectError(pParse, pDest, p->pEList->nExpr) ){

4863 goto select_end;

4864 }

4865 #endif

4866

4867 /* Try to flatten subqueries in the FROM clause up into the main query

4868 */

4869 #if !defined(SQLITE_OMIT_SUBQUERY) \|\| !defined(SQLITE_OMIT_VIEW)

4870 for(i=0; !p->pPrior && i<pTabList->nSrc; i++){

4871 struct SrcList_item *pItem = &pTabList->a[i];

4872 Select *pSub = pItem->pSelect;

4873 int isAggSub;

4874 Table *pTab = pItem->pTab;

4875 if( pSub==0 ) continue;

4876

4877 /* Catch mismatch in the declared columns of a view and the number of

4878 ** columns in the SELECT on the RHS */

4879 if( pTab->nCol!=pSub->pEList->nExpr ){

4880 sqlite3ErrorMsg(pParse, "expected %d columns for '%s' but got %d",

4881 pTab->nCol, pTab->zName, pSub->pEList->nExpr);

4882 goto select_end;

4883 }

4884

4885 isAggSub = (pSub->selFlags & SF_Aggregate)!=0;

4886 if( flattenSubquery(pParse, p, i, isAgg, isAggSub) ){

4887 /* This subquery can be absorbed into its parent. */

4888 if( isAggSub ){

4889 isAgg = 1;

4890 p->selFlags \|= SF_Aggregate;

4891 }

4892 i = -1;

4893 }

4894 pTabList = p->pSrc;

4895 if( db->mallocFailed ) goto select_end;

4896 if( !IgnorableOrderby(pDest) ){

4897 sSort.pOrderBy = p->pOrderBy;

4898 }

4899 }

4900 #endif

4901

4902 /* Get a pointer the VDBE under construction, allocating a new VDBE if one

4903 ** does not already exist */

4904 v = sqlite3GetVdbe(pParse);

4905 if( v==0 ) goto select_end;

4906

4907 #ifndef SQLITE_OMIT_COMPOUND_SELECT

4908 /* Handle compound SELECT statements using the separate multiSelect()

4909 ** procedure.

4910 */

4911 if( p->pPrior ){

4912 rc = multiSelect(pParse, p, pDest);

4913 explainSetInteger(pParse->iSelectId, iRestoreSelectId);

4914 #if SELECTTRACE_ENABLED

4915 SELECTTRACE(1,pParse,p,("end compound-select processing\n"));

4916 pParse->nSelectIndent--;

4917 #endif

4918 return rc;

4919 }

4920 #endif

4921

4922 /* Generate code for all sub-queries in the FROM clause

4923 */

4924 #if !defined(SQLITE_OMIT_SUBQUERY) \|\| !defined(SQLITE_OMIT_VIEW)

4925 for(i=0; i<pTabList->nSrc; i++){

4926 struct SrcList_item *pItem = &pTabList->a[i];

4927 SelectDest dest;

4928 Select *pSub = pItem->pSelect;

4929 if( pSub==0 ) continue;

4930

4931 /* Sometimes the code for a subquery will be generated more than

4932 ** once, if the subquery is part of the WHERE clause in a LEFT JOIN,

4933 ** for example. In that case, do not regenerate the code to manifest

4934 ** a view or the co-routine to implement a view. The first instance

4935 ** is sufficient, though the subroutine to manifest the view does need

4936 ** to be invoked again. */

4937 if( pItem->addrFillSub ){

4938 if( pItem->fg.viaCoroutine==0 ){

4939 sqlite3VdbeAddOp2(v, OP_Gosub, pItem->regReturn, pItem->addrFillSub);

4940 }

4941 continue;

4942 }

4943

4944 /* Increment Parse.nHeight by the height of the largest expression

4945 ** tree referred to by this, the parent select. The child select

4946 ** may contain expression trees of at most

4947 ** (SQLITE_MAX_EXPR_DEPTH-Parse.nHeight) height. This is a bit

4948 ** more conservative than necessary, but much easier than enforcing

4949 ** an exact limit.

4950 */

4951 pParse->nHeight += sqlite3SelectExprHeight(p);

4952

4953 /* Make copies of constant WHERE-clause terms in the outer query down

4954 ** inside the subquery. This can help the subquery to run more efficiently.

4955 */

4956 if( (pItem->fg.jointype & JT_OUTER)==0

4957 && pushDownWhereTerms(db, pSub, p->pWhere, pItem->iCursor)

4958 ){

4959 #if SELECTTRACE_ENABLED

4960 if( sqlite3SelectTrace & 0x100 ){

4961 SELECTTRACE(0x100,pParse,p,("After WHERE-clause push-down:\n"));

4962 sqlite3TreeViewSelect(0, p, 0);

4963 }

4964 #endif

4965 }

4966

4967 /* Generate code to implement the subquery

4968 */

4969 if( pTabList->nSrc==1

4970 && (p->selFlags & SF_All)==0

4971 && OptimizationEnabled(db, SQLITE_SubqCoroutine)

4972 ){

4973 /* Implement a co-routine that will return a single row of the result

4974 ** set on each invocation.

4975 */

4976 int addrTop = sqlite3VdbeCurrentAddr(v)+1;

4977 pItem->regReturn = ++pParse->nMem;

4978 sqlite3VdbeAddOp3(v, OP_InitCoroutine, pItem->regReturn, 0, addrTop);

4979 VdbeComment((v, "%s", pItem->pTab->zName));

4980 pItem->addrFillSub = addrTop;

4981 sqlite3SelectDestInit(&dest, SRT_Coroutine, pItem->regReturn);

4982 explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId);

4983 sqlite3Select(pParse, pSub, &dest);

4984 pItem->pTab->nRowLogEst = sqlite3LogEst(pSub->nSelectRow);

4985 pItem->fg.viaCoroutine = 1;

4986 pItem->regResult = dest.iSdst;

4987 sqlite3VdbeAddOp1(v, OP_EndCoroutine, pItem->regReturn);

4988 sqlite3VdbeJumpHere(v, addrTop-1);

4989 sqlite3ClearTempRegCache(pParse);

4990 }else{

4991 /* Generate a subroutine that will fill an ephemeral table with

4992 ** the content of this subquery. pItem->addrFillSub will point

4993 ** to the address of the generated subroutine. pItem->regReturn

4994 ** is a register allocated to hold the subroutine return address

4995 */

4996 int topAddr;

4997 int onceAddr = 0;

4998 int retAddr;

4999 assert( pItem->addrFillSub==0 );

5000 pItem->regReturn = ++pParse->nMem;

5001 topAddr = sqlite3VdbeAddOp2(v, OP_Integer, 0, pItem->regReturn);

5002 pItem->addrFillSub = topAddr+1;

5003 if( pItem->fg.isCorrelated==0 ){

5004 /* If the subquery is not correlated and if we are not inside of

5005 ** a trigger, then we only need to compute the value of the subquery

5006 ** once. */

5007 onceAddr = sqlite3CodeOnce(pParse); VdbeCoverage(v);

5008 VdbeComment((v, "materialize \"%s\"", pItem->pTab->zName));

5009 }else{

5010 VdbeNoopComment((v, "materialize \"%s\"", pItem->pTab->zName));

5011 }

5012 sqlite3SelectDestInit(&dest, SRT_EphemTab, pItem->iCursor);

5013 explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId);

5014 sqlite3Select(pParse, pSub, &dest);

5015 pItem->pTab->nRowLogEst = sqlite3LogEst(pSub->nSelectRow);

5016 if( onceAddr ) sqlite3VdbeJumpHere(v, onceAddr);

5017 retAddr = sqlite3VdbeAddOp1(v, OP_Return, pItem->regReturn);

5018 VdbeComment((v, "end %s", pItem->pTab->zName));

5019 sqlite3VdbeChangeP1(v, topAddr, retAddr);

5020 sqlite3ClearTempRegCache(pParse);

5021 }

5022 if( db->mallocFailed ) goto select_end;

5023 pParse->nHeight -= sqlite3SelectExprHeight(p);

5024 }

5025 #endif

5026

5027 /* Various elements of the SELECT copied into local variables for

5028 ** convenience */

5029 pEList = p->pEList;

5030 pWhere = p->pWhere;

5031 pGroupBy = p->pGroupBy;

5032 pHaving = p->pHaving;

5033 sDistinct.isTnct = (p->selFlags & SF_Distinct)!=0;

5034

5035 #if SELECTTRACE_ENABLED

5036 if( sqlite3SelectTrace & 0x400 ){

5037 SELECTTRACE(0x400,pParse,p,("After all FROM-clause analysis:\n"));

5038 sqlite3TreeViewSelect(0, p, 0);

5039 }

5040 #endif

5041

5042 /* If the query is DISTINCT with an ORDER BY but is not an aggregate, and

5043 ** if the select-list is the same as the ORDER BY list, then this query

5044 ** can be rewritten as a GROUP BY. In other words, this:

5045 **

5046 ** SELECT DISTINCT xyz FROM ... ORDER BY xyz

5047 **

5048 ** is transformed to:

5049 **

5050 ** SELECT xyz FROM ... GROUP BY xyz ORDER BY xyz

5051 **

5052 ** The second form is preferred as a single index (or temp-table) may be

5053 ** used for both the ORDER BY and DISTINCT processing. As originally

5054 ** written the query must use a temp-table for at least one of the ORDER

5055 ** BY and DISTINCT, and an index or separate temp-table for the other.

5056 */

5057 if( (p->selFlags & (SF_Distinct\|SF_Aggregate))==SF_Distinct

5058 && sqlite3ExprListCompare(sSort.pOrderBy, pEList, -1)==0

5059 ){

5060 p->selFlags &= ~SF_Distinct;

5061 pGroupBy = p->pGroupBy = sqlite3ExprListDup(db, pEList, 0);

5062 /* Notice that even thought SF_Distinct has been cleared from p->selFlags,

5063 ** the sDistinct.isTnct is still set. Hence, isTnct represents the

5064 ** original setting of the SF_Distinct flag, not the current setting */

5065 assert( sDistinct.isTnct );

5066 }

5067

5068 /* If there is an ORDER BY clause, then create an ephemeral index to

5069 ** do the sorting. But this sorting ephemeral index might end up

5070 ** being unused if the data can be extracted in pre-sorted order.

5071 ** If that is the case, then the OP_OpenEphemeral instruction will be

5072 ** changed to an OP_Noop once we figure out that the sorting index is

5073 ** not needed. The sSort.addrSortIndex variable is used to facilitate

5074 ** that change.

5075 */

5076 if( sSort.pOrderBy ){

5077 KeyInfo *pKeyInfo;

5078 pKeyInfo = keyInfoFromExprList(pParse, sSort.pOrderBy, 0, pEList->nExpr);

5079 sSort.iECursor = pParse->nTab++;

5080 sSort.addrSortIndex =

5081 sqlite3VdbeAddOp4(v, OP_OpenEphemeral,

5082 sSort.iECursor, sSort.pOrderBy->nExpr+1+pEList->nExpr, 0,

5083 (char*)pKeyInfo, P4_KEYINFO

5084 );

5085 }else{

5086 sSort.addrSortIndex = -1;

5087 }

5088

5089 /* If the output is destined for a temporary table, open that table.

5090 */

5091 if( pDest->eDest==SRT_EphemTab ){

5092 sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pDest->iSDParm, pEList->nExpr);

5093 }

5094

5095 /* Set the limiter.

5096 */

5097 iEnd = sqlite3VdbeMakeLabel(v);

5098 p->nSelectRow = LARGEST_INT64;

5099 computeLimitRegisters(pParse, p, iEnd);

5100 if( p->iLimit==0 && sSort.addrSortIndex>=0 ){

5101 sqlite3VdbeChangeOpcode(v, sSort.addrSortIndex, OP_SorterOpen);

5102 sSort.sortFlags \|= SORTFLAG_UseSorter;

5103 }

5104

5105 /* Open an ephemeral index to use for the distinct set.

5106 */

5107 if( p->selFlags & SF_Distinct ){

5108 sDistinct.tabTnct = pParse->nTab++;

5109 sDistinct.addrTnct = sqlite3VdbeAddOp4(v, OP_OpenEphemeral,

5110 sDistinct.tabTnct, 0, 0,

5111 (char*)keyInfoFromExprList(pParse, p->pEList,0,0),

5112 P4_KEYINFO);

5113 sqlite3VdbeChangeP5(v, BTREE_UNORDERED);

5114 sDistinct.eTnctType = WHERE_DISTINCT_UNORDERED;

5115 }else{

5116 sDistinct.eTnctType = WHERE_DISTINCT_NOOP;

5117 }

5118

5119 if( !isAgg && pGroupBy==0 ){

5120 /* No aggregate functions and no GROUP BY clause */

5121 u16 wctrlFlags = (sDistinct.isTnct ? WHERE_WANT_DISTINCT : 0);

5122

5123 /* Begin the database scan. */

5124 pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, sSort.pOrderBy,

5125 p->pEList, wctrlFlags, 0);

5126 if( pWInfo==0 ) goto select_end;

5127 if( sqlite3WhereOutputRowCount(pWInfo) < p->nSelectRow ){

5128 p->nSelectRow = sqlite3WhereOutputRowCount(pWInfo);

5129 }

5130 if( sDistinct.isTnct && sqlite3WhereIsDistinct(pWInfo) ){

5131 sDistinct.eTnctType = sqlite3WhereIsDistinct(pWInfo);

5132 }

5133 if( sSort.pOrderBy ){

5134 sSort.nOBSat = sqlite3WhereIsOrdered(pWInfo);

5135 if( sSort.nOBSat==sSort.pOrderBy->nExpr ){

5136 sSort.pOrderBy = 0;

5137 }

5138 }

5139

5140 /* If sorting index that was created by a prior OP_OpenEphemeral

5141 ** instruction ended up not being needed, then change the OP_OpenEphemeral

5142 ** into an OP_Noop.

5143 */

5144 if( sSort.addrSortIndex>=0 && sSort.pOrderBy==0 ){

5145 sqlite3VdbeChangeToNoop(v, sSort.addrSortIndex);

5146 }

5147

5148 /* Use the standard inner loop. */

5149 selectInnerLoop(pParse, p, pEList, -1, &sSort, &sDistinct, pDest,

5150 sqlite3WhereContinueLabel(pWInfo),

5151 sqlite3WhereBreakLabel(pWInfo));

5152

5153 /* End the database scan loop.

5154 */

5155 sqlite3WhereEnd(pWInfo);

5156 }else{

5157 /* This case when there exist aggregate functions or a GROUP BY clause

5158 ** or both */

5159 NameContext sNC; /* Name context for processing aggregate information */

5160 int iAMem; /* First Mem address for storing current GROUP BY */

5161 int iBMem; /* First Mem address for previous GROUP BY */

5162 int iUseFlag; /* Mem address holding flag indicating that at least

5163 ** one row of the input to the aggregator has been

5164 ** processed */

5165 int iAbortFlag; /* Mem address which causes query abort if positive */

5166 int groupBySort; /* Rows come from source in GROUP BY order */

5167 int addrEnd; /* End of processing for this SELECT */

5168 int sortPTab = 0; /* Pseudotable used to decode sorting results */

5169 int sortOut = 0; /* Output register from the sorter */

5170 int orderByGrp = 0; /* True if the GROUP BY and ORDER BY are the same */

5171

5172 /* Remove any and all aliases between the result set and the

5173 ** GROUP BY clause.

5174 */

5175 if( pGroupBy ){

5176 int k; /* Loop counter */

5177 struct ExprList_item pItem; / For looping over expression in a list */

5178

5179 for(k=p->pEList->nExpr, pItem=p->pEList->a; k>0; k--, pItem++){

5180 pItem->u.x.iAlias = 0;

5181 }

5182 for(k=pGroupBy->nExpr, pItem=pGroupBy->a; k>0; k--, pItem++){

5183 pItem->u.x.iAlias = 0;

5184 }

5185 if( p->nSelectRow>100 ) p->nSelectRow = 100;

5186 }else{

5187 p->nSelectRow = 1;

5188 }

5189

5190 /* If there is both a GROUP BY and an ORDER BY clause and they are

5191 ** identical, then it may be possible to disable the ORDER BY clause

5192 ** on the grounds that the GROUP BY will cause elements to come out

5193 ** in the correct order. It also may not - the GROUP BY might use a

5194 ** database index that causes rows to be grouped together as required

5195 ** but not actually sorted. Either way, record the fact that the

5196 ** ORDER BY and GROUP BY clauses are the same by setting the orderByGrp

5197 ** variable. */

5198 if( sqlite3ExprListCompare(pGroupBy, sSort.pOrderBy, -1)==0 ){

5199 orderByGrp = 1;

5200 }

5201

5202 /* Create a label to jump to when we want to abort the query */

5203 addrEnd = sqlite3VdbeMakeLabel(v);

5204

5205 /* Convert TK_COLUMN nodes into TK_AGG_COLUMN and make entries in

5206 ** sAggInfo for all TK_AGG_FUNCTION nodes in expressions of the

5207 ** SELECT statement.

5208 */

5209 memset(&sNC, 0, sizeof(sNC));

5210 sNC.pParse = pParse;

5211 sNC.pSrcList = pTabList;

5212 sNC.pAggInfo = &sAggInfo;

5213 sAggInfo.mnReg = pParse->nMem+1;

5214 sAggInfo.nSortingColumn = pGroupBy ? pGroupBy->nExpr : 0;

5215 sAggInfo.pGroupBy = pGroupBy;

5216 sqlite3ExprAnalyzeAggList(&sNC, pEList);

5217 sqlite3ExprAnalyzeAggList(&sNC, sSort.pOrderBy);

5218 if( pHaving ){

5219 sqlite3ExprAnalyzeAggregates(&sNC, pHaving);

5220 }

5221 sAggInfo.nAccumulator = sAggInfo.nColumn;

5222 for(i=0; i<sAggInfo.nFunc; i++){

5223 assert( !ExprHasProperty(sAggInfo.aFunc[i].pExpr, EP_xIsSelect) );

5224 sNC.ncFlags \|= NC_InAggFunc;

5225 sqlite3ExprAnalyzeAggList(&sNC, sAggInfo.aFunc[i].pExpr->x.pList);

5226 sNC.ncFlags &= ~NC_InAggFunc;

5227 }

5228 sAggInfo.mxReg = pParse->nMem;

5229 if( db->mallocFailed ) goto select_end;

5230

5231 /* Processing for aggregates with GROUP BY is very different and

5232 ** much more complex than aggregates without a GROUP BY.

5233 */

5234 if( pGroupBy ){

5235 KeyInfo pKeyInfo; / Keying information for the group by clause */

5236 int addr1; /* A-vs-B comparision jump */

5237 int addrOutputRow; /* Start of subroutine that outputs a result row */

5238 int regOutputRow; /* Return address register for output subroutine */

5239 int addrSetAbort; /* Set the abort flag and return */

5240 int addrTopOfLoop; /* Top of the input loop */

5241 int addrSortingIdx; /* The OP_OpenEphemeral for the sorting index */

5242 int addrReset; /* Subroutine for resetting the accumulator */

5243 int regReset; /* Return address register for reset subroutine */

5244

5245 /* If there is a GROUP BY clause we might need a sorting index to

5246 ** implement it. Allocate that sorting index now. If it turns out

5247 ** that we do not need it after all, the OP_SorterOpen instruction

5248 ** will be converted into a Noop.

5249 */

5250 sAggInfo.sortingIdx = pParse->nTab++;

5251 pKeyInfo = keyInfoFromExprList(pParse, pGroupBy, 0, sAggInfo.nColumn);

5252 addrSortingIdx = sqlite3VdbeAddOp4(v, OP_SorterOpen,

5253 sAggInfo.sortingIdx, sAggInfo.nSortingColumn,

5254 0, (char*)pKeyInfo, P4_KEYINFO);

5255

5256 /* Initialize memory locations used by GROUP BY aggregate processing

5257 */

5258 iUseFlag = ++pParse->nMem;

5259 iAbortFlag = ++pParse->nMem;

5260 regOutputRow = ++pParse->nMem;

5261 addrOutputRow = sqlite3VdbeMakeLabel(v);

5262 regReset = ++pParse->nMem;

5263 addrReset = sqlite3VdbeMakeLabel(v);

5264 iAMem = pParse->nMem + 1;

5265 pParse->nMem += pGroupBy->nExpr;

5266 iBMem = pParse->nMem + 1;

5267 pParse->nMem += pGroupBy->nExpr;

5268 sqlite3VdbeAddOp2(v, OP_Integer, 0, iAbortFlag);

5269 VdbeComment((v, "clear abort flag"));

5270 sqlite3VdbeAddOp2(v, OP_Integer, 0, iUseFlag);

5271 VdbeComment((v, "indicate accumulator empty"));

5272 sqlite3VdbeAddOp3(v, OP_Null, 0, iAMem, iAMem+pGroupBy->nExpr-1);

5273

5274 /* Begin a loop that will extract all source rows in GROUP BY order.

5275 ** This might involve two separate loops with an OP_Sort in between, or

5276 ** it might be a single loop that uses an index to extract information

5277 ** in the right order to begin with.

5278 */

5279 sqlite3VdbeAddOp2(v, OP_Gosub, regReset, addrReset);

5280 pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pGroupBy, 0,

5281 WHERE_GROUPBY \| (orderByGrp ? WHERE_SORTBYGROUP : 0), 0

5282 );

5283 if( pWInfo==0 ) goto select_end;

5284 if( sqlite3WhereIsOrdered(pWInfo)==pGroupBy->nExpr ){

5285 /* The optimizer is able to deliver rows in group by order so

5286 ** we do not have to sort. The OP_OpenEphemeral table will be

5287 ** cancelled later because we still need to use the pKeyInfo

5288 */

5289 groupBySort = 0;

5290 }else{

5291 /* Rows are coming out in undetermined order. We have to push

5292 ** each row into a sorting index, terminate the first loop,

5293 ** then loop over the sorting index in order to get the output

5294 ** in sorted order

5295 */

5296 int regBase;

5297 int regRecord;

5298 int nCol;

5299 int nGroupBy;

5300

5301 explainTempTable(pParse,

5302 (sDistinct.isTnct && (p->selFlags&SF_Distinct)==0) ?

5303 "DISTINCT" : "GROUP BY");

5304

5305 groupBySort = 1;

5306 nGroupBy = pGroupBy->nExpr;

5307 nCol = nGroupBy;

5308 j = nGroupBy;

5309 for(i=0; i<sAggInfo.nColumn; i++){

5310 if( sAggInfo.aCol[i].iSorterColumn>=j ){

5311 nCol++;

5312 j++;

5313 }

5314 }

5315 regBase = sqlite3GetTempRange(pParse, nCol);

5316 sqlite3ExprCacheClear(pParse);

5317 sqlite3ExprCodeExprList(pParse, pGroupBy, regBase, 0, 0);

5318 j = nGroupBy;

5319 for(i=0; i<sAggInfo.nColumn; i++){

5320 struct AggInfo_col *pCol = &sAggInfo.aCol[i];

5321 if( pCol->iSorterColumn>=j ){

5322 int r1 = j + regBase;

5323 sqlite3ExprCodeGetColumnToReg(pParse,

5324 pCol->pTab, pCol->iColumn, pCol->iTable, r1);

5325 j++;

5326 }

5327 }

5328 regRecord = sqlite3GetTempReg(pParse);

5329 sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase, nCol, regRecord);

5330 sqlite3VdbeAddOp2(v, OP_SorterInsert, sAggInfo.sortingIdx, regRecord);

5331 sqlite3ReleaseTempReg(pParse, regRecord);

5332 sqlite3ReleaseTempRange(pParse, regBase, nCol);

5333 sqlite3WhereEnd(pWInfo);

5334 sAggInfo.sortingIdxPTab = sortPTab = pParse->nTab++;

5335 sortOut = sqlite3GetTempReg(pParse);

5336 sqlite3VdbeAddOp3(v, OP_OpenPseudo, sortPTab, sortOut, nCol);

5337 sqlite3VdbeAddOp2(v, OP_SorterSort, sAggInfo.sortingIdx, addrEnd);

5338 VdbeComment((v, "GROUP BY sort")); VdbeCoverage(v);

5339 sAggInfo.useSortingIdx = 1;

5340 sqlite3ExprCacheClear(pParse);

5341

5342 }

5343

5344 /* If the index or temporary table used by the GROUP BY sort

5345 ** will naturally deliver rows in the order required by the ORDER BY

5346 ** clause, cancel the ephemeral table open coded earlier.

5347 **

5348 ** This is an optimization - the correct answer should result regardless.

5349 ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER to

5350 ** disable this optimization for testing purposes. */

5351 if( orderByGrp && OptimizationEnabled(db, SQLITE_GroupByOrder)

5352 && (groupBySort \|\| sqlite3WhereIsSorted(pWInfo))

5353 ){

5354 sSort.pOrderBy = 0;

5355 sqlite3VdbeChangeToNoop(v, sSort.addrSortIndex);

5356 }

5357

5358 /* Evaluate the current GROUP BY terms and store in b0, b1, b2...

5359 ** (b0 is memory location iBMem+0, b1 is iBMem+1, and so forth)

5360 ** Then compare the current GROUP BY terms against the GROUP BY terms

5361 ** from the previous row currently stored in a0, a1, a2...

5362 */

5363 addrTopOfLoop = sqlite3VdbeCurrentAddr(v);

5364 sqlite3ExprCacheClear(pParse);

5365 if( groupBySort ){

5366 sqlite3VdbeAddOp3(v, OP_SorterData, sAggInfo.sortingIdx,

5367 sortOut, sortPTab);

5368 }

5369 for(j=0; j<pGroupBy->nExpr; j++){

5370 if( groupBySort ){

5371 sqlite3VdbeAddOp3(v, OP_Column, sortPTab, j, iBMem+j);

5372 }else{

5373 sAggInfo.directMode = 1;

5374 sqlite3ExprCode(pParse, pGroupBy->a[j].pExpr, iBMem+j);

5375 }

5376 }

5377 sqlite3VdbeAddOp4(v, OP_Compare, iAMem, iBMem, pGroupBy->nExpr,

5378 (char*)sqlite3KeyInfoRef(pKeyInfo), P4_KEYINFO);

5379 addr1 = sqlite3VdbeCurrentAddr(v);

5380 sqlite3VdbeAddOp3(v, OP_Jump, addr1+1, 0, addr1+1); VdbeCoverage(v);

5381

5382 /* Generate code that runs whenever the GROUP BY changes.

5383 ** Changes in the GROUP BY are detected by the previous code

5384 ** block. If there were no changes, this block is skipped.

5385 **

5386 ** This code copies current group by terms in b0,b1,b2,...

5387 ** over to a0,a1,a2. It then calls the output subroutine

5388 ** and resets the aggregate accumulator registers in preparation

5389 ** for the next GROUP BY batch.

5390 */

5391 sqlite3ExprCodeMove(pParse, iBMem, iAMem, pGroupBy->nExpr);

5392 sqlite3VdbeAddOp2(v, OP_Gosub, regOutputRow, addrOutputRow);

5393 VdbeComment((v, "output one row"));

5394 sqlite3VdbeAddOp2(v, OP_IfPos, iAbortFlag, addrEnd); VdbeCoverage(v);

5395 VdbeComment((v, "check abort flag"));

5396 sqlite3VdbeAddOp2(v, OP_Gosub, regReset, addrReset);

5397 VdbeComment((v, "reset accumulator"));

5398

5399 /* Update the aggregate accumulators based on the content of

5400 ** the current row

5401 */

5402 sqlite3VdbeJumpHere(v, addr1);

5403 updateAccumulator(pParse, &sAggInfo);

5404 sqlite3VdbeAddOp2(v, OP_Integer, 1, iUseFlag);

5405 VdbeComment((v, "indicate data in accumulator"));

5406

5407 /* End of the loop

5408 */

5409 if( groupBySort ){

5410 sqlite3VdbeAddOp2(v, OP_SorterNext, sAggInfo.sortingIdx, addrTopOfLoop);

5411 VdbeCoverage(v);

5412 }else{

5413 sqlite3WhereEnd(pWInfo);

5414 sqlite3VdbeChangeToNoop(v, addrSortingIdx);

5415 }

5416

5417 /* Output the final row of result

5418 */

5419 sqlite3VdbeAddOp2(v, OP_Gosub, regOutputRow, addrOutputRow);

5420 VdbeComment((v, "output final row"));

5421

5422 /* Jump over the subroutines

5423 */

5424 sqlite3VdbeGoto(v, addrEnd);

5425

5426 /* Generate a subroutine that outputs a single row of the result

5427 ** set. This subroutine first looks at the iUseFlag. If iUseFlag

5428 ** is less than or equal to zero, the subroutine is a no-op. If

5429 ** the processing calls for the query to abort, this subroutine

5430 ** increments the iAbortFlag memory location before returning in

5431 ** order to signal the caller to abort.

5432 */

5433 addrSetAbort = sqlite3VdbeCurrentAddr(v);

5434 sqlite3VdbeAddOp2(v, OP_Integer, 1, iAbortFlag);

5435 VdbeComment((v, "set abort flag"));

5436 sqlite3VdbeAddOp1(v, OP_Return, regOutputRow);

5437 sqlite3VdbeResolveLabel(v, addrOutputRow);

5438 addrOutputRow = sqlite3VdbeCurrentAddr(v);

5439 sqlite3VdbeAddOp2(v, OP_IfPos, iUseFlag, addrOutputRow+2);

5440 VdbeCoverage(v);

5441 VdbeComment((v, "Groupby result generator entry point"));

5442 sqlite3VdbeAddOp1(v, OP_Return, regOutputRow);

5443 finalizeAggFunctions(pParse, &sAggInfo);

5444 sqlite3ExprIfFalse(pParse, pHaving, addrOutputRow+1, SQLITE_JUMPIFNULL);

5445 selectInnerLoop(pParse, p, p->pEList, -1, &sSort,

5446 &sDistinct, pDest,

5447 addrOutputRow+1, addrSetAbort);

5448 sqlite3VdbeAddOp1(v, OP_Return, regOutputRow);

5449 VdbeComment((v, "end groupby result generator"));

5450

5451 /* Generate a subroutine that will reset the group-by accumulator

5452 */

5453 sqlite3VdbeResolveLabel(v, addrReset);

5454 resetAccumulator(pParse, &sAggInfo);

5455 sqlite3VdbeAddOp1(v, OP_Return, regReset);

5456

5457 } /* endif pGroupBy. Begin aggregate queries without GROUP BY: */

5458 else {

5459 ExprList *pDel = 0;

5460 #ifndef SQLITE_OMIT_BTREECOUNT

5461 Table *pTab;

5462 if( (pTab = isSimpleCount(p, &sAggInfo))!=0 ){

5463 /* If isSimpleCount() returns a pointer to a Table structure, then

5464 ** the SQL statement is of the form:

5465 **

5466 ** SELECT count(*) FROM <tbl>

5467 **

5468 ** where the Table structure returned represents table <tbl>.

5469 **

5470 ** This statement is so common that it is optimized specially. The

5471 ** OP_Count instruction is executed either on the intkey table that

5472 ** contains the data for table <tbl> or on one of its indexes. It

5473 ** is better to execute the op on an index, as indexes are almost

5474 ** always spread across less pages than their corresponding tables.

5475 */

5476 const int iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);

5477 const int iCsr = pParse->nTab++; /* Cursor to scan b-tree */

5478 Index pIdx; / Iterator variable */

5479 KeyInfo pKeyInfo = 0; / Keyinfo for scanned index */

5480 Index pBest = 0; / Best index found so far */

5481 int iRoot = pTab->tnum; /* Root page of scanned b-tree */

5482

5483 sqlite3CodeVerifySchema(pParse, iDb);

5484 sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);

5485

5486 /* Search for the index that has the lowest scan cost.

5487 **

5488 ** (2011-04-15) Do not do a full scan of an unordered index.

5489 **

5490 ** (2013-10-03) Do not count the entries in a partial index.

5491 **

5492 ** In practice the KeyInfo structure will not be used. It is only

5493 ** passed to keep OP_OpenRead happy.

5494 */

5495 if( !HasRowid(pTab) ) pBest = sqlite3PrimaryKeyIndex(pTab);

5496 for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){

5497 if( pIdx->bUnordered==0

5498 && pIdx->szIdxRow<pTab->szTabRow

5499 && pIdx->pPartIdxWhere==0

5500 && (!pBest \|\| pIdx->szIdxRow<pBest->szIdxRow)

5501 ){

5502 pBest = pIdx;

5503 }

5504 }

5505 if( pBest ){

5506 iRoot = pBest->tnum;

5507 pKeyInfo = sqlite3KeyInfoOfIndex(pParse, pBest);

5508 }

5509

5510 /* Open a read-only cursor, execute the OP_Count, close the cursor. */

5511 sqlite3VdbeAddOp4Int(v, OP_OpenRead, iCsr, iRoot, iDb, 1);

5512 if( pKeyInfo ){

5513 sqlite3VdbeChangeP4(v, -1, (char *)pKeyInfo, P4_KEYINFO);

5514 }

5515 sqlite3VdbeAddOp2(v, OP_Count, iCsr, sAggInfo.aFunc[0].iMem);

5516 sqlite3VdbeAddOp1(v, OP_Close, iCsr);

5517 explainSimpleCount(pParse, pTab, pBest);

5518 }else

5519 #endif /* SQLITE_OMIT_BTREECOUNT */

5520 {

5521 /* Check if the query is of one of the following forms:

5522 **

5523 ** SELECT min(x) FROM ...

5524 ** SELECT max(x) FROM ...

5525 **

5526 ** If it is, then ask the code in where.c to attempt to sort results

5527 ** as if there was an "ORDER ON x" or "ORDER ON x DESC" clause.

5528 ** If where.c is able to produce results sorted in this order, then

5529 ** add vdbe code to break out of the processing loop after the

5530 ** first iteration (since the first iteration of the loop is

5531 ** guaranteed to operate on the row with the minimum or maximum

5532 ** value of x, the only row required).

5533 **

5534 ** A special flag must be passed to sqlite3WhereBegin() to slightly

5535 ** modify behavior as follows:

5536 **

5537 ** + If the query is a "SELECT min(x)", then the loop coded by

5538 ** where.c should not iterate over any values with a NULL value

5539 ** for x.

5540 **

5541 ** + The optimizer code in where.c (the thing that decides which

5542 ** index or indices to use) should place a different priority on

5543 ** satisfying the 'ORDER BY' clause than it does in other cases.

5544 ** Refer to code and comments in where.c for details.

5545 */

5546 ExprList *pMinMax = 0;

5547 u8 flag = WHERE_ORDERBY_NORMAL;

5548

5549 assert( p->pGroupBy==0 );

5550 assert( flag==0 );

5551 if( p->pHaving==0 ){

5552 flag = minMaxQuery(&sAggInfo, &pMinMax);

5553 }

5554 assert( flag==0 \|\| (pMinMax!=0 && pMinMax->nExpr==1) );

5555

5556 if( flag ){

5557 pMinMax = sqlite3ExprListDup(db, pMinMax, 0);

5558 pDel = pMinMax;

5559 if( pMinMax && !db->mallocFailed ){

5560 pMinMax->a[0].sortOrder = flag!=WHERE_ORDERBY_MIN ?1:0;

5561 pMinMax->a[0].pExpr->op = TK_COLUMN;

5562 }

5563 }

5564

5565 /* This case runs if the aggregate has no GROUP BY clause. The

5566 ** processing is much simpler since there is only a single row

5567 ** of output.

5568 */

5569 resetAccumulator(pParse, &sAggInfo);

5570 pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pMinMax,0,flag,0);

5571 if( pWInfo==0 ){

5572 sqlite3ExprListDelete(db, pDel);

5573 goto select_end;

5574 }

5575 updateAccumulator(pParse, &sAggInfo);

5576 assert( pMinMax==0 \|\| pMinMax->nExpr==1 );

5577 if( sqlite3WhereIsOrdered(pWInfo)>0 ){

5578 sqlite3VdbeGoto(v, sqlite3WhereBreakLabel(pWInfo));

5579 VdbeComment((v, "%s() by index",

5580 (flag==WHERE_ORDERBY_MIN?"min":"max")));

5581 }

5582 sqlite3WhereEnd(pWInfo);

5583 finalizeAggFunctions(pParse, &sAggInfo);

5584 }

5585

5586 sSort.pOrderBy = 0;

5587 sqlite3ExprIfFalse(pParse, pHaving, addrEnd, SQLITE_JUMPIFNULL);

5588 selectInnerLoop(pParse, p, p->pEList, -1, 0, 0,

5589 pDest, addrEnd, addrEnd);

5590 sqlite3ExprListDelete(db, pDel);

5591 }

5592 sqlite3VdbeResolveLabel(v, addrEnd);

5593

5594 } /* endif aggregate query */

5595

5596 if( sDistinct.eTnctType==WHERE_DISTINCT_UNORDERED ){

5597 explainTempTable(pParse, "DISTINCT");

5598 }

5599

5600 /* If there is an ORDER BY clause, then we need to sort the results

5601 ** and send them to the callback one by one.

5602 */

5603 if( sSort.pOrderBy ){

5604 explainTempTable(pParse,

5605 sSort.nOBSat>0 ? "RIGHT PART OF ORDER BY":"ORDER BY");

5606 generateSortTail(pParse, p, &sSort, pEList->nExpr, pDest);

5607 }

5608

5609 /* Jump here to skip this query

5610 */

5611 sqlite3VdbeResolveLabel(v, iEnd);

5612

5613 /* The SELECT has been coded. If there is an error in the Parse structure,

5614 ** set the return code to 1. Otherwise 0. */

5615 rc = (pParse->nErr>0);

5616

5617 /* Control jumps to here if an error is encountered above, or upon

5618 ** successful coding of the SELECT.

5619 */

5620 select_end:

5621 explainSetInteger(pParse->iSelectId, iRestoreSelectId);

5622

5623 /* Identify column names if results of the SELECT are to be output.

5624 */

5625 if( rc==SQLITE_OK && pDest->eDest==SRT_Output ){

5626 generateColumnNames(pParse, pTabList, pEList);

5627 }

5628

5629 sqlite3DbFree(db, sAggInfo.aCol);

5630 sqlite3DbFree(db, sAggInfo.aFunc);

5631 #if SELECTTRACE_ENABLED

5632 SELECTTRACE(1,pParse,p,("end processing\n"));

5633 pParse->nSelectIndent--;

5634 #endif

5635 return rc;

5636 }

OLD	NEW

« no previous file with comments | « third_party/sqlite/sqlite-src-3100200/src/rowset.c ('k') | third_party/sqlite/sqlite-src-3100200/src/shell.c » ('j') | no next file with comments »