third_party/sqlite/sqlite-src-3080704/src/select.c - Issue 2363173002: [sqlite] Remove obsolete reference version 3.8.7.4.

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

Issue 2363173002: [sqlite] Remove obsolete reference version 3.8.7.4. (Closed)

Patch Set: Created 4 years, 2 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,"",(S)->zSelName,(S)) ,\

25 sqlite3DebugPrintf X

26 #else

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

28 #endif

29

30

31 /*

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

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

34 ** into the selectInnerLoop() routine.

35 */

36 typedef struct DistinctCtx DistinctCtx;

37 struct DistinctCtx {

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

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

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

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

42 };

43

44 /*

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

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

47 */

48 typedef struct SortCtx SortCtx;

49 struct SortCtx {

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

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

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

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

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

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

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

57 };

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

59

60 /*

61 ** Delete all the content of a Select structure but do not deallocate

62 ** the select structure itself.

63 */

64 static void clearSelect(sqlite3 db, Select p){

65 sqlite3ExprListDelete(db, p->pEList);

66 sqlite3SrcListDelete(db, p->pSrc);

67 sqlite3ExprDelete(db, p->pWhere);

68 sqlite3ExprListDelete(db, p->pGroupBy);

69 sqlite3ExprDelete(db, p->pHaving);

70 sqlite3ExprListDelete(db, p->pOrderBy);

71 sqlite3SelectDelete(db, p->pPrior);

72 sqlite3ExprDelete(db, p->pLimit);

73 sqlite3ExprDelete(db, p->pOffset);

74 sqlite3WithDelete(db, p->pWith);

75 }

76

77 /*

78 ** Initialize a SelectDest structure.

79 */

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

81 pDest->eDest = (u8)eDest;

82 pDest->iSDParm = iParm;

83 pDest->affSdst = 0;

84 pDest->iSdst = 0;

85 pDest->nSdst = 0;

86 }

87

88

89 /*

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

91 ** structure.

92 */

93 Select *sqlite3SelectNew(

94 Parse pParse, / Parsing context */

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

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

97 Expr pWhere, / the WHERE clause */

98 ExprList pGroupBy, / the GROUP BY clause */

99 Expr pHaving, / the HAVING clause */

100 ExprList pOrderBy, / the ORDER BY clause */

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

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

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

104 ){

105 Select *pNew;

106 Select standin;

107 sqlite3 *db = pParse->db;

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

109 assert( db->mallocFailed \|\| !pOffset \|\| pLimit ); /* OFFSET implies LIMIT */

110 if( pNew==0 ){

111 assert( db->mallocFailed );

112 pNew = &standin;

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

114 }

115 if( pEList==0 ){

116 pEList = sqlite3ExprListAppend(pParse, 0, sqlite3Expr(db,TK_ALL,0));

117 }

118 pNew->pEList = pEList;

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

120 pNew->pSrc = pSrc;

121 pNew->pWhere = pWhere;

122 pNew->pGroupBy = pGroupBy;

123 pNew->pHaving = pHaving;

124 pNew->pOrderBy = pOrderBy;

125 pNew->selFlags = selFlags;

126 pNew->op = TK_SELECT;

127 pNew->pLimit = pLimit;

128 pNew->pOffset = pOffset;

129 assert( pOffset==0 \|\| pLimit!=0 );

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

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

132 if( db->mallocFailed ) {

133 clearSelect(db, pNew);

134 if( pNew!=&standin ) sqlite3DbFree(db, pNew);

135 pNew = 0;

136 }else{

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

138 }

139 assert( pNew!=&standin );

140 return pNew;

141 }

142

143 #if SELECTTRACE_ENABLED

144 /*

145 ** Set the name of a Select object

146 */

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

148 if( p && zName ){

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

150 }

151 }

152 #endif

153

154

155 /*

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

157 */

158 void sqlite3SelectDelete(sqlite3 db, Select p){

159 if( p ){

160 clearSelect(db, p);

161 sqlite3DbFree(db, p);

162 }

163 }

164

165 /*

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

167 */

168 static Select findRightmost(Select p){

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

170 return p;

171 }

172

173 /*

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

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

176 ** in terms of the following bit values:

177 **

178 ** JT_INNER

179 ** JT_CROSS

180 ** JT_OUTER

181 ** JT_NATURAL

182 ** JT_LEFT

183 ** JT_RIGHT

184 **

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

186 **

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

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

189 */

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

191 int jointype = 0;

192 Token *apAll[3];

193 Token *p;

194 /* 0123456789 123456789 123456789 123 */

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

196 static const struct {

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

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

199 u8 code; /* Join type mask */

200 } aKeyword[] = {

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

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

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

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

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

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

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

208 };

209 int i, j;

210 apAll[0] = pA;

211 apAll[1] = pB;

212 apAll[2] = pC;

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

214 p = apAll[i];

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

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

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

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

219 break;

220 }

221 }

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

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

224 jointype \|= JT_ERROR;

225 break;

226 }

227 }

228 if(

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

230 (jointype & JT_ERROR)!=0

231 ){

232 const char *zSp = " ";

233 assert( pB!=0 );

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

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

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

237 jointype = JT_INNER;

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

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

240 sqlite3ErrorMsg(pParse,

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

242 jointype = JT_INNER;

243 }

244 return jointype;

245 }

246

247 /*

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

249 ** is not contained in the table.

250 */

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

252 int i;

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

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

255 }

256 return -1;

257 }

258

259 /*

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

261 ** table that has a column named zCol.

262 **

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

264 ** of the matching column and return TRUE.

265 **

266 ** If not found, return FALSE.

267 */

268 static int tableAndColumnIndex(

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

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

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

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

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

274 ){

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

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

277

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

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

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

281 if( iCol>=0 ){

282 if( piTab ){

283 *piTab = i;

284 *piCol = iCol;

285 }

286 return 1;

287 }

288 }

289 return 0;

290 }

291

292 /*

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

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

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

296 **

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

298 **

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

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

301 ** column iColRight of tab2.

302 */

303 static void addWhereTerm(

304 Parse pParse, / Parsing context */

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

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

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

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

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

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

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

312 ){

313 sqlite3 *db = pParse->db;

314 Expr *pE1;

315 Expr *pE2;

316 Expr *pEq;

317

318 assert( iLeft<iRight );

319 assert( pSrc->nSrc>iRight );

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

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

322

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

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

325

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

327 if( pEq && isOuterJoin ){

328 ExprSetProperty(pEq, EP_FromJoin);

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

330 ExprSetVVAProperty(pEq, EP_NoReduce);

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

332 }

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

334 }

335

336 /*

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

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

339 ** expression.

340 **

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

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

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

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

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

346 ** originated in the ON or USING clause.

347 **

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

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

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

351 ** for cases like this:

352 **

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

354 **

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

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

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

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

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

360 ** the output, which is incorrect.

361 */

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

363 while( p ){

364 ExprSetProperty(p, EP_FromJoin);

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

366 ExprSetVVAProperty(p, EP_NoReduce);

367 p->iRightJoinTable = (i16)iTable;

368 setJoinExpr(p->pLeft, iTable);

369 p = p->pRight;

370 }

371 }

372

373 /*

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

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

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

377 **

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

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

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

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

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

383 ** also attached to the left entry.

384 **

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

386 */

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

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

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

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

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

392

393 pSrc = p->pSrc;

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

395 pRight = &pLeft[1];

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

397 Table *pLeftTab = pLeft->pTab;

398 Table *pRightTab = pRight->pTab;

399 int isOuter;

400

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

402 isOuter = (pRight->jointype & JT_OUTER)!=0;

403

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

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

406 */

407 if( pRight->jointype & JT_NATURAL ){

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

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

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

411 return 1;

412 }

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

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

415 int iLeft; /* Matching left table */

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

417

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

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

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

421 isOuter, &p->pWhere);

422 }

423 }

424 }

425

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

427 */

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

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

430 "clauses in the same join");

431 return 1;

432 }

433

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

435 ** an AND operator.

436 */

437 if( pRight->pOn ){

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

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

440 pRight->pOn = 0;

441 }

442

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

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

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

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

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

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

449 */

450 if( pRight->pUsing ){

451 IdList *pList = pRight->pUsing;

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

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

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

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

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

457

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

459 iRightCol = columnIndex(pRightTab, zName);

460 if( iRightCol<0

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

462 ){

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

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

465 return 1;

466 }

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

468 isOuter, &p->pWhere);

469 }

470 }

471 }

472 return 0;

473 }

474

475 /* Forward reference */

476 static KeyInfo *keyInfoFromExprList(

477 Parse pParse, / Parsing context */

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

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

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

481 );

482

483 /*

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

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

486 */

487 static void pushOntoSorter(

488 Parse pParse, / Parser context */

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

490 Select pSelect, / The whole SELECT statement */

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

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

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

494 ){

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

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

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

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

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

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

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

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

503

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

505 if( nPrefixReg ){

506 assert( nPrefixReg==nExpr+bSeq );

507 regBase = regData - nExpr - bSeq;

508 }else{

509 regBase = pParse->nMem + 1;

510 pParse->nMem += nBase;

511 }

512 sqlite3ExprCodeExprList(pParse, pSort->pOrderBy, regBase, SQLITE_ECEL_DUP);

513 if( bSeq ){

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

515 }

516 if( nPrefixReg==0 ){

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

518 }

519

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

521 if( nOBSat>0 ){

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

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

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

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

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

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

528

529 regPrevKey = pParse->nMem+1;

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

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

532 if( bSeq ){

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

534 }else{

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

536 }

537 VdbeCoverage(v);

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

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

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

541 pOp->p2 = nKey + nData;

542 pKI = pOp->p4.pKeyInfo;

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

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

545 pOp->p4.pKeyInfo = keyInfoFromExprList(pParse, pSort->pOrderBy, nOBSat, 1);

546 addrJmp = sqlite3VdbeCurrentAddr(v);

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

548 pSort->labelBkOut = sqlite3VdbeMakeLabel(v);

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

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

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

552 sqlite3VdbeJumpHere(v, addrFirst);

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

554 sqlite3VdbeJumpHere(v, addrJmp);

555 }

556 if( pSort->sortFlags & SORTFLAG_UseSorter ){

557 op = OP_SorterInsert;

558 }else{

559 op = OP_IdxInsert;

560 }

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

562 if( pSelect->iLimit ){

563 int addr1, addr2;

564 int iLimit;

565 if( pSelect->iOffset ){

566 iLimit = pSelect->iOffset+1;

567 }else{

568 iLimit = pSelect->iLimit;

569 }

570 addr1 = sqlite3VdbeAddOp1(v, OP_IfZero, iLimit); VdbeCoverage(v);

571 sqlite3VdbeAddOp2(v, OP_AddImm, iLimit, -1);

572 addr2 = sqlite3VdbeAddOp0(v, OP_Goto);

573 sqlite3VdbeJumpHere(v, addr1);

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

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

576 sqlite3VdbeJumpHere(v, addr2);

577 }

578 }

579

580 /*

581 ** Add code to implement the OFFSET

582 */

583 static void codeOffset(

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

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

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

587 ){

588 if( iOffset>0 ){

589 int addr;

590 addr = sqlite3VdbeAddOp3(v, OP_IfNeg, iOffset, 0, -1); VdbeCoverage(v);

591 sqlite3VdbeAddOp2(v, OP_Goto, 0, iContinue);

592 VdbeComment((v, "skip OFFSET records"));

593 sqlite3VdbeJumpHere(v, addr);

594 }

595 }

596

597 /*

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

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

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

601 ** if the current N values are new.

602 **

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

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

605 */

606 static void codeDistinct(

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

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

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

610 int N, /* Number of elements */

611 int iMem /* First element */

612 ){

613 Vdbe *v;

614 int r1;

615

616 v = pParse->pVdbe;

617 r1 = sqlite3GetTempReg(pParse);

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

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

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

621 sqlite3ReleaseTempReg(pParse, r1);

622 }

623

624 #ifndef SQLITE_OMIT_SUBQUERY

625 /*

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

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

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

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

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

631 */

632 static int checkForMultiColumnSelectError(

633 Parse pParse, / Parse context. */

634 SelectDest pDest, / Destination of SELECT results */

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

636 ){

637 int eDest = pDest->eDest;

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

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

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

641 return 1;

642 }else{

643 return 0;

644 }

645 }

646 #endif

647

648 /*

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

650 ** of a SELECT.

651 **

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

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

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

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

656 */

657 static void selectInnerLoop(

658 Parse pParse, / The parser context */

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

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

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

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

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

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

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

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

667 ){

668 Vdbe *v = pParse->pVdbe;

669 int i;

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

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

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

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

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

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

676

677 assert( v );

678 assert( pEList!=0 );

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

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

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

682 assert( iContinue!=0 );

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

684 }

685

686 /* Pull the requested columns.

687 */

688 nResultCol = pEList->nExpr;

689

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

691 if( pSort ){

692 nPrefixReg = pSort->pOrderBy->nExpr;

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

694 pParse->nMem += nPrefixReg;

695 }

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

697 pParse->nMem += nResultCol;

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

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

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

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

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

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

704 pParse->nMem += nResultCol;

705 }

706 pDest->nSdst = nResultCol;

707 regResult = pDest->iSdst;

708 if( srcTab>=0 ){

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

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

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

712 }

713 }else if( eDest!=SRT_Exists ){

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

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

716 */

717 sqlite3ExprCodeExprList(pParse, pEList, regResult,

718 (eDest==SRT_Output\|\|eDest==SRT_Coroutine)?SQLITE_ECEL_DUP:0);

719 }

720

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

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

723 ** part of the result.

724 */

725 if( hasDistinct ){

726 switch( pDistinct->eTnctType ){

727 case WHERE_DISTINCT_ORDERED: {

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

729 int iJump; /* Jump destination */

730 int regPrev; /* Previous row content */

731

732 /* Allocate space for the previous row */

733 regPrev = pParse->nMem+1;

734 pParse->nMem += nResultCol;

735

736 /* Change the OP_OpenEphemeral coded earlier to an OP_Null

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

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

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

740 ** row is all NULLs.

741 */

742 sqlite3VdbeChangeToNoop(v, pDistinct->addrTnct);

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

744 pOp->opcode = OP_Null;

745 pOp->p1 = 1;

746 pOp->p2 = regPrev;

747

748 iJump = sqlite3VdbeCurrentAddr(v) + nResultCol;

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

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

751 if( i<nResultCol-1 ){

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

753 VdbeCoverage(v);

754 }else{

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

756 VdbeCoverage(v);

757 }

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

759 sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);

760 }

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

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

763 break;

764 }

765

766 case WHERE_DISTINCT_UNIQUE: {

767 sqlite3VdbeChangeToNoop(v, pDistinct->addrTnct);

768 break;

769 }

770

771 default: {

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

773 codeDistinct(pParse, pDistinct->tabTnct, iContinue, nResultCol, regResul t);

774 break;

775 }

776 }

777 if( pSort==0 ){

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

779 }

780 }

781

782 switch( eDest ){

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

784 ** table iParm.

785 */

786 #ifndef SQLITE_OMIT_COMPOUND_SELECT

787 case SRT_Union: {

788 int r1;

789 r1 = sqlite3GetTempReg(pParse);

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

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

792 sqlite3ReleaseTempReg(pParse, r1);

793 break;

794 }

795

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

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

798 ** the temporary table iParm.

799 */

800 case SRT_Except: {

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

802 break;

803 }

804 #endif /* SQLITE_OMIT_COMPOUND_SELECT */

805

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

807 */

808 case SRT_Fifo:

809 case SRT_DistFifo:

810 case SRT_Table:

811 case SRT_EphemTab: {

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

813 testcase( eDest==SRT_Table );

814 testcase( eDest==SRT_EphemTab );

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

816 #ifndef SQLITE_OMIT_CTE

817 if( eDest==SRT_DistFifo ){

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

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

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

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

822 ** output table as well. */

823 int addr = sqlite3VdbeCurrentAddr(v) + 4;

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

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

826 assert( pSort==0 );

827 }

828 #endif

829 if( pSort ){

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

831 }else{

832 int r2 = sqlite3GetTempReg(pParse);

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

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

835 sqlite3VdbeChangeP5(v, OPFLAG_APPEND);

836 sqlite3ReleaseTempReg(pParse, r2);

837 }

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

839 break;

840 }

841

842 #ifndef SQLITE_OMIT_SUBQUERY

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

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

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

846 */

847 case SRT_Set: {

848 assert( nResultCol==1 );

849 pDest->affSdst =

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

851 if( pSort ){

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

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

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

855 ** case the order does matter */

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

857 }else{

858 int r1 = sqlite3GetTempReg(pParse);

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

860 sqlite3ExprCacheAffinityChange(pParse, regResult, 1);

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

862 sqlite3ReleaseTempReg(pParse, r1);

863 }

864 break;

865 }

866

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

868 */

869 case SRT_Exists: {

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

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

872 break;

873 }

874

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

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

877 ** of the scan loop.

878 */

879 case SRT_Mem: {

880 assert( nResultCol==1 );

881 if( pSort ){

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

883 }else{

884 assert( regResult==iParm );

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

886 }

887 break;

888 }

889 #endif /* #ifndef SQLITE_OMIT_SUBQUERY */

890

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

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

893 testcase( eDest==SRT_Coroutine );

894 testcase( eDest==SRT_Output );

895 if( pSort ){

896 pushOntoSorter(pParse, pSort, p, regResult, nResultCol, nPrefixReg);

897 }else if( eDest==SRT_Coroutine ){

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

899 }else{

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

901 sqlite3ExprCacheAffinityChange(pParse, regResult, nResultCol);

902 }

903 break;

904 }

905

906 #ifndef SQLITE_OMIT_CTE

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

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

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

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

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

912 */

913 case SRT_DistQueue:

914 case SRT_Queue: {

915 int nKey;

916 int r1, r2, r3;

917 int addrTest = 0;

918 ExprList *pSO;

919 pSO = pDest->pOrderBy;

920 assert( pSO );

921 nKey = pSO->nExpr;

922 r1 = sqlite3GetTempReg(pParse);

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

924 r3 = r2+nKey+1;

925 if( eDest==SRT_DistQueue ){

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

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

928 ** added to the queue. */

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

930 regResult, nResultCol);

931 VdbeCoverage(v);

932 }

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

934 if( eDest==SRT_DistQueue ){

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

936 sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);

937 }

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

939 sqlite3VdbeAddOp2(v, OP_SCopy,

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

941 r2+i);

942 }

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

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

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

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

947 sqlite3ReleaseTempReg(pParse, r1);

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

949 break;

950 }

951 #endif /* SQLITE_OMIT_CTE */

952

953

954

955 #if !defined(SQLITE_OMIT_TRIGGER)

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

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

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

959 ** about the actual results of the select.

960 */

961 default: {

962 assert( eDest==SRT_Discard );

963 break;

964 }

965 #endif

966 }

967

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

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

970 ** the output for us.

971 */

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

973 sqlite3VdbeAddOp3(v, OP_IfZero, p->iLimit, iBreak, -1); VdbeCoverage(v);

974 }

975 }

976

977 /*

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

979 ** X extra columns.

980 */

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

982 KeyInfo *p = sqlite3DbMallocZero(0,

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

984 if( p ){

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

986 p->nField = (u16)N;

987 p->nXField = (u16)X;

988 p->enc = ENC(db);

989 p->db = db;

990 p->nRef = 1;

991 }else{

992 db->mallocFailed = 1;

993 }

994 return p;

995 }

996

997 /*

998 ** Deallocate a KeyInfo object

999 */

1000 void sqlite3KeyInfoUnref(KeyInfo *p){

1001 if( p ){

1002 assert( p->nRef>0 );

1003 p->nRef--;

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

1005 }

1006 }

1007

1008 /*

1009 ** Make a new pointer to a KeyInfo object

1010 */

1011 KeyInfo sqlite3KeyInfoRef(KeyInfo p){

1012 if( p ){

1013 assert( p->nRef>0 );

1014 p->nRef++;

1015 }

1016 return p;

1017 }

1018

1019 #ifdef SQLITE_DEBUG

1020 /*

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

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

1023 **

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

1025 */

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

1027 #endif /* SQLITE_DEBUG */

1028

1029 /*

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

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

1032 **

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

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

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

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

1037 ** index to implement a DISTINCT test.

1038 **

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

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

1041 ** freed.

1042 */

1043 static KeyInfo *keyInfoFromExprList(

1044 Parse pParse, / Parsing context */

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

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

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

1048 ){

1049 int nExpr;

1050 KeyInfo *pInfo;

1051 struct ExprList_item *pItem;

1052 sqlite3 *db = pParse->db;

1053 int i;

1054

1055 nExpr = pList->nExpr;

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

1057 if( pInfo ){

1058 assert( sqlite3KeyInfoIsWriteable(pInfo) );

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

1060 CollSeq *pColl;

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

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

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

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

1065 }

1066 }

1067 return pInfo;

1068 }

1069

1070 #ifndef SQLITE_OMIT_COMPOUND_SELECT

1071 /*

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

1073 */

1074 static const char *selectOpName(int id){

1075 char *z;

1076 switch( id ){

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

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

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

1080 default: z = "UNION"; break;

1081 }

1082 return z;

1083 }

1084 #endif /* SQLITE_OMIT_COMPOUND_SELECT */

1085

1086 #ifndef SQLITE_OMIT_EXPLAIN

1087 /*

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

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

1090 ** where the caption is of the form:

1091 **

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

1093 **

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

1095 ** is determined by the zUsage argument.

1096 */

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

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

1099 Vdbe *v = pParse->pVdbe;

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

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

1102 }

1103 }

1104

1105 /*

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

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

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

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

1110 ** code with #ifndef directives.

1111 */

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

1113

1114 #else

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

1116 # define explainTempTable(y,z)

1117 # define explainSetInteger(y,z)

1118 #endif

1119

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

1121 /*

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

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

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

1125 **

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

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

1128 **

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

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

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

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

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

1134 */

1135 static void explainComposite(

1136 Parse pParse, / Parse context */

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

1138 int iSub1, /* Subquery id 1 */

1139 int iSub2, /* Subquery id 2 */

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

1141 ){

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

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

1144 Vdbe *v = pParse->pVdbe;

1145 char *zMsg = sqlite3MPrintf(

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

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

1148 );

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

1150 }

1151 }

1152 #else

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

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

1155 #endif

1156

1157 /*

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

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

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

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

1162 */

1163 static void generateSortTail(

1164 Parse pParse, / Parsing context */

1165 Select p, / The SELECT statement */

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

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

1168 SelectDest pDest / Write the sorted results here */

1169 ){

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

1171 int addrBreak = sqlite3VdbeMakeLabel(v); /* Jump here to exit loop */

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

1173 int addr;

1174 int addrOnce = 0;

1175 int iTab;

1176 ExprList *pOrderBy = pSort->pOrderBy;

1177 int eDest = pDest->eDest;

1178 int iParm = pDest->iSDParm;

1179 int regRow;

1180 int regRowid;

1181 int nKey;

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

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

1184 int i;

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

1186 #ifdef SQLITE_ENABLE_EXPLAIN_COMMENTS

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

1188 #endif

1189

1190 if( pSort->labelBkOut ){

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

1192 sqlite3VdbeAddOp2(v, OP_Goto, 0, addrBreak);

1193 sqlite3VdbeResolveLabel(v, pSort->labelBkOut);

1194 }

1195 iTab = pSort->iECursor;

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

1197 regRowid = 0;

1198 regRow = pDest->iSdst;

1199 nSortData = nColumn;

1200 }else{

1201 regRowid = sqlite3GetTempReg(pParse);

1202 regRow = sqlite3GetTempReg(pParse);

1203 nSortData = 1;

1204 }

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

1206 if( pSort->sortFlags & SORTFLAG_UseSorter ){

1207 int regSortOut = ++pParse->nMem;

1208 iSortTab = pParse->nTab++;

1209 if( pSort->labelBkOut ){

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

1211 }

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

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

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

1215 VdbeCoverage(v);

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

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

1218 bSeq = 0;

1219 }else{

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

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

1222 iSortTab = iTab;

1223 bSeq = 1;

1224 }

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

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

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

1228 }

1229 switch( eDest ){

1230 case SRT_Table:

1231 case SRT_EphemTab: {

1232 testcase( eDest==SRT_Table );

1233 testcase( eDest==SRT_EphemTab );

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

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

1236 sqlite3VdbeChangeP5(v, OPFLAG_APPEND);

1237 break;

1238 }

1239 #ifndef SQLITE_OMIT_SUBQUERY

1240 case SRT_Set: {

1241 assert( nColumn==1 );

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

1243 &pDest->affSdst, 1);

1244 sqlite3ExprCacheAffinityChange(pParse, regRow, 1);

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

1246 break;

1247 }

1248 case SRT_Mem: {

1249 assert( nColumn==1 );

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

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

1252 break;

1253 }

1254 #endif

1255 default: {

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

1257 testcase( eDest==SRT_Output );

1258 testcase( eDest==SRT_Coroutine );

1259 if( eDest==SRT_Output ){

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

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

1262 }else{

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

1264 }

1265 break;

1266 }

1267 }

1268 if( regRowid ){

1269 sqlite3ReleaseTempReg(pParse, regRow);

1270 sqlite3ReleaseTempReg(pParse, regRowid);

1271 }

1272 /* The bottom of the loop

1273 */

1274 sqlite3VdbeResolveLabel(v, addrContinue);

1275 if( pSort->sortFlags & SORTFLAG_UseSorter ){

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

1277 }else{

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

1279 }

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

1281 sqlite3VdbeResolveLabel(v, addrBreak);

1282 }

1283

1284 /*

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

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

1287 **

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

1289 ** result in *pEstWidth.

1290 **

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

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

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

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

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

1296 ** considered a column by this function.

1297 **

1298 ** SELECT col FROM tbl;

1299 ** SELECT (SELECT col FROM tbl;

1300 ** SELECT (SELECT col FROM tbl);

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

1302 **

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

1304 **

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

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

1307 */

1308 #ifdef SQLITE_ENABLE_COLUMN_METADATA

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

1310 static const char *columnTypeImpl(

1311 NameContext *pNC,

1312 Expr *pExpr,

1313 const char **pzOrigDb,

1314 const char **pzOrigTab,

1315 const char **pzOrigCol,

1316 u8 *pEstWidth

1317 ){

1318 char const *zOrigDb = 0;

1319 char const *zOrigTab = 0;

1320 char const *zOrigCol = 0;

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

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

1323 static const char *columnTypeImpl(

1324 NameContext *pNC,

1325 Expr *pExpr,

1326 u8 *pEstWidth

1327 ){

1328 #endif /* !defined(SQLITE_ENABLE_COLUMN_METADATA) */

1329 char const *zType = 0;

1330 int j;

1331 u8 estWidth = 1;

1332

1333 if( NEVER(pExpr==0) \|\| pNC->pSrcList==0 ) return 0;

1334 switch( pExpr->op ){

1335 case TK_AGG_COLUMN:

1336 case TK_COLUMN: {

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

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

1339 ** database table or a subquery.

1340 */

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

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

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

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

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

1346 while( pNC && !pTab ){

1347 SrcList *pTabList = pNC->pSrcList;

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

1349 if( j<pTabList->nSrc ){

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

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

1352 }else{

1353 pNC = pNC->pNext;

1354 }

1355 }

1356

1357 if( pTab==0 ){

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

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

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

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

1362 ** the following:

1363 **

1364 ** CREATE TABLE t1(col INTEGER);

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

1366 **

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

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

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

1370 **

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

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

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

1374 ** branch below. */

1375 break;

1376 }

1377

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

1379 if( pS ){

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

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

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

1383 */

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

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

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

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

1388 */

1389 NameContext sNC;

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

1391 sNC.pSrcList = pS->pSrc;

1392 sNC.pNext = pNC;

1393 sNC.pParse = pNC->pParse;

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

1395 }

1396 }else if( pTab->pSchema ){

1397 /* A real table */

1398 assert( !pS );

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

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

1401 #ifdef SQLITE_ENABLE_COLUMN_METADATA

1402 if( iCol<0 ){

1403 zType = "INTEGER";

1404 zOrigCol = "rowid";

1405 }else{

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

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

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

1409 }

1410 zOrigTab = pTab->zName;

1411 if( pNC->pParse ){

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

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

1414 }

1415 #else

1416 if( iCol<0 ){

1417 zType = "INTEGER";

1418 }else{

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

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

1421 }

1422 #endif

1423 }

1424 break;

1425 }

1426 #ifndef SQLITE_OMIT_SUBQUERY

1427 case TK_SELECT: {

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

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

1430 ** statement.

1431 */

1432 NameContext sNC;

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

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

1435 assert( ExprHasProperty(pExpr, EP_xIsSelect) );

1436 sNC.pSrcList = pS->pSrc;

1437 sNC.pNext = pNC;

1438 sNC.pParse = pNC->pParse;

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

1440 break;

1441 }

1442 #endif

1443 }

1444

1445 #ifdef SQLITE_ENABLE_COLUMN_METADATA

1446 if( pzOrigDb ){

1447 assert( pzOrigTab && pzOrigCol );

1448 *pzOrigDb = zOrigDb;

1449 *pzOrigTab = zOrigTab;

1450 *pzOrigCol = zOrigCol;

1451 }

1452 #endif

1453 if( pEstWidth ) *pEstWidth = estWidth;

1454 return zType;

1455 }

1456

1457 /*

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

1459 ** in the result set.

1460 */

1461 static void generateColumnTypes(

1462 Parse pParse, / Parser context */

1463 SrcList pTabList, / List of tables */

1464 ExprList pEList / Expressions defining the result set */

1465 ){

1466 #ifndef SQLITE_OMIT_DECLTYPE

1467 Vdbe *v = pParse->pVdbe;

1468 int i;

1469 NameContext sNC;

1470 sNC.pSrcList = pTabList;

1471 sNC.pParse = pParse;

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

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

1474 const char *zType;

1475 #ifdef SQLITE_ENABLE_COLUMN_METADATA

1476 const char *zOrigDb = 0;

1477 const char *zOrigTab = 0;

1478 const char *zOrigCol = 0;

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

1480

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

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

1483 ** virtual machine is deleted.

1484 */

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

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

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

1488 #else

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

1490 #endif

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

1492 }

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

1494 }

1495

1496 /*

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

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

1499 ** azCol[] values in the callback.

1500 */

1501 static void generateColumnNames(

1502 Parse pParse, / Parser context */

1503 SrcList pTabList, / List of tables */

1504 ExprList pEList / Expressions defining the result set */

1505 ){

1506 Vdbe *v = pParse->pVdbe;

1507 int i, j;

1508 sqlite3 *db = pParse->db;

1509 int fullNames, shortNames;

1510

1511 #ifndef SQLITE_OMIT_EXPLAIN

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

1513 if( pParse->explain ){

1514 return;

1515 }

1516 #endif

1517

1518 if( pParse->colNamesSet \|\| NEVER(v==0) \|\| db->mallocFailed ) return;

1519 pParse->colNamesSet = 1;

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

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

1522 sqlite3VdbeSetNumCols(v, pEList->nExpr);

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

1524 Expr *p;

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

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

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

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

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

1530 }else if( (p->op==TK_COLUMN \|\| p->op==TK_AGG_COLUMN) && pTabList ){

1531 Table *pTab;

1532 char *zCol;

1533 int iCol = p->iColumn;

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

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

1536 }

1537 assert( j<pTabList->nSrc );

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

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

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

1541 if( iCol<0 ){

1542 zCol = "rowid";

1543 }else{

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

1545 }

1546 if( !shortNames && !fullNames ){

1547 sqlite3VdbeSetColName(v, i, COLNAME_NAME,

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

1549 }else if( fullNames ){

1550 char *zName = 0;

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

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

1553 }else{

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

1555 }

1556 }else{

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

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

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

1560 }

1561 }

1562 generateColumnTypes(pParse, pTabList, pEList);

1563 }

1564

1565 /*

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

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

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

1569 **

1570 ** All column names will be unique.

1571 **

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

1573 ** and other fields of Column are zeroed.

1574 **

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

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

1577 */

1578 static int selectColumnsFromExprList(

1579 Parse pParse, / Parsing context */

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

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

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

1583 ){

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

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

1586 int cnt; /* Index added to make the name unique */

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

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

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

1590 char zName; / Column name */

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

1592

1593 if( pEList ){

1594 nCol = pEList->nExpr;

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

1596 testcase( aCol==0 );

1597 }else{

1598 nCol = 0;

1599 aCol = 0;

1600 }

1601 *pnCol = nCol;

1602 *paCol = aCol;

1603

1604 for(i=0, pCol=aCol; i<nCol; i++, pCol++){

1605 /* Get an appropriate name for the column

1606 */

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

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

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

1610 zName = sqlite3DbStrDup(db, zName);

1611 }else{

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

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

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

1615 pColExpr = pColExpr->pRight;

1616 assert( pColExpr!=0 );

1617 }

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

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

1620 int iCol = pColExpr->iColumn;

1621 pTab = pColExpr->pTab;

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

1623 zName = sqlite3MPrintf(db, "%s",

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

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

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

1627 zName = sqlite3MPrintf(db, "%s", pColExpr->u.zToken);

1628 }else{

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

1630 zName = sqlite3MPrintf(db, "%s", pEList->a[i].zSpan);

1631 }

1632 }

1633 if( db->mallocFailed ){

1634 sqlite3DbFree(db, zName);

1635 break;

1636 }

1637

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

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

1640 */

1641 nName = sqlite3Strlen30(zName);

1642 for(j=cnt=0; j<i; j++){

1643 if( sqlite3StrICmp(aCol[j].zName, zName)==0 ){

1644 char *zNewName;

1645 int k;

1646 for(k=nName-1; k>1 && sqlite3Isdigit(zName[k]); k--){}

1647 if( k>=0 && zName[k]==':' ) nName = k;

1648 zName[nName] = 0;

1649 zNewName = sqlite3MPrintf(db, "%s:%d", zName, ++cnt);

1650 sqlite3DbFree(db, zName);

1651 zName = zNewName;

1652 j = -1;

1653 if( zName==0 ) break;

1654 }

1655 }

1656 pCol->zName = zName;

1657 }

1658 if( db->mallocFailed ){

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

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

1661 }

1662 sqlite3DbFree(db, aCol);

1663 *paCol = 0;

1664 *pnCol = 0;

1665 return SQLITE_NOMEM;

1666 }

1667 return SQLITE_OK;

1668 }

1669

1670 /*

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

1672 ** a SELECT statement.

1673 **

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

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

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

1677 **

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

1679 ** statement be resolved.

1680 */

1681 static void selectAddColumnTypeAndCollation(

1682 Parse pParse, / Parsing contexts */

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

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

1685 ){

1686 sqlite3 *db = pParse->db;

1687 NameContext sNC;

1688 Column *pCol;

1689 CollSeq *pColl;

1690 int i;

1691 Expr *p;

1692 struct ExprList_item *a;

1693 u64 szAll = 0;

1694

1695 assert( pSelect!=0 );

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

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

1698 if( db->mallocFailed ) return;

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

1700 sNC.pSrcList = pSelect->pSrc;

1701 a = pSelect->pEList->a;

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

1703 p = a[i].pExpr;

1704 pCol->zType = sqlite3DbStrDup(db, columnType(&sNC, p,0,0,0, &pCol->szEst));

1705 szAll += pCol->szEst;

1706 pCol->affinity = sqlite3ExprAffinity(p);

1707 if( pCol->affinity==0 ) pCol->affinity = SQLITE_AFF_NONE;

1708 pColl = sqlite3ExprCollSeq(pParse, p);

1709 if( pColl ){

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

1711 }

1712 }

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

1714 }

1715

1716 /*

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

1718 ** the result set of that SELECT.

1719 */

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

1721 Table *pTab;

1722 sqlite3 *db = pParse->db;

1723 int savedFlags;

1724

1725 savedFlags = db->flags;

1726 db->flags &= ~SQLITE_FullColNames;

1727 db->flags \|= SQLITE_ShortColNames;

1728 sqlite3SelectPrep(pParse, pSelect, 0);

1729 if( pParse->nErr ) return 0;

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

1731 db->flags = savedFlags;

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

1733 if( pTab==0 ){

1734 return 0;

1735 }

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

1737 ** is disabled */

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

1739 pTab->nRef = 1;

1740 pTab->zName = 0;

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

1742 selectColumnsFromExprList(pParse, pSelect->pEList, &pTab->nCol, &pTab->aCol);

1743 selectAddColumnTypeAndCollation(pParse, pTab, pSelect);

1744 pTab->iPKey = -1;

1745 if( db->mallocFailed ){

1746 sqlite3DeleteTable(db, pTab);

1747 return 0;

1748 }

1749 return pTab;

1750 }

1751

1752 /*

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

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

1755 */

1756 Vdbe sqlite3GetVdbe(Parse pParse){

1757 Vdbe *v = pParse->pVdbe;

1758 if( v==0 ){

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

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

1761 if( pParse->pToplevel==0

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

1763 ){

1764 pParse->okConstFactor = 1;

1765 }

1766

1767 }

1768 return v;

1769 }

1770

1771

1772 /*

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

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

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

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

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

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

1779 ** iLimit and iOffset are negative.

1780 **

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

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

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

1784 ** prior to calling this routine.

1785 **

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

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

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

1789 **

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

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

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

1793 ** SELECT statements.

1794 */

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

1796 Vdbe *v = 0;

1797 int iLimit = 0;

1798 int iOffset;

1799 int addr1, n;

1800 if( p->iLimit ) return;

1801

1802 /*

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

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

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

1806 ** no rows.

1807 */

1808 sqlite3ExprCacheClear(pParse);

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

1810 if( p->pLimit ){

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

1812 v = sqlite3GetVdbe(pParse);

1813 assert( v!=0 );

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

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

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

1817 if( n==0 ){

1818 sqlite3VdbeAddOp2(v, OP_Goto, 0, iBreak);

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

1820 p->nSelectRow = n;

1821 }

1822 }else{

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

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

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

1826 sqlite3VdbeAddOp2(v, OP_IfZero, iLimit, iBreak); VdbeCoverage(v);

1827 }

1828 if( p->pOffset ){

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

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

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

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

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

1834 addr1 = sqlite3VdbeAddOp1(v, OP_IfPos, iOffset); VdbeCoverage(v);

1835 sqlite3VdbeAddOp2(v, OP_Integer, 0, iOffset);

1836 sqlite3VdbeJumpHere(v, addr1);

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

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

1839 addr1 = sqlite3VdbeAddOp1(v, OP_IfPos, iLimit); VdbeCoverage(v);

1840 sqlite3VdbeAddOp2(v, OP_Integer, -1, iOffset+1);

1841 sqlite3VdbeJumpHere(v, addr1);

1842 }

1843 }

1844 }

1845

1846 #ifndef SQLITE_OMIT_COMPOUND_SELECT

1847 /*

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

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

1850 ** the column has no default collating sequence.

1851 **

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

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

1854 */

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

1856 CollSeq *pRet;

1857 if( p->pPrior ){

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

1859 }else{

1860 pRet = 0;

1861 }

1862 assert( iCol>=0 );

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

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

1865 }

1866 return pRet;

1867 }

1868

1869 /*

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

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

1872 ** structure suitable for implementing the ORDER BY.

1873 **

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

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

1876 ** freed.

1877 */

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

1879 ExprList *pOrderBy = p->pOrderBy;

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

1881 sqlite3 *db = pParse->db;

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

1883 if( pRet ){

1884 int i;

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

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

1887 Expr *pTerm = pItem->pExpr;

1888 CollSeq *pColl;

1889

1890 if( pTerm->flags & EP_Collate ){

1891 pColl = sqlite3ExprCollSeq(pParse, pTerm);

1892 }else{

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

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

1895 pOrderBy->a[i].pExpr =

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

1897 }

1898 assert( sqlite3KeyInfoIsWriteable(pRet) );

1899 pRet->aColl[i] = pColl;

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

1901 }

1902 }

1903

1904 return pRet;

1905 }

1906

1907 #ifndef SQLITE_OMIT_CTE

1908 /*

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

1910 ** query of the form:

1911 **

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

1913 ** \___________/ \_______________/

1914 ** p->pPrior p

1915 **

1916 **

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

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

1919 **

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

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

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

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

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

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

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

1927 **

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

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

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

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

1932 **

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

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

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

1936 **

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

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

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

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

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

1942 ** rows have been skipped.

1943 */

1944 static void generateWithRecursiveQuery(

1945 Parse pParse, / Parsing context */

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

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

1948 ){

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

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

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

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

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

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

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

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

1957 int iQueue; /* The Queue table */

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

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

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

1961 int i; /* Loop counter */

1962 int rc; /* Result code */

1963 ExprList pOrderBy; / The ORDER BY clause */

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

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

1966

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

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

1969

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

1971 addrBreak = sqlite3VdbeMakeLabel(v);

1972 computeLimitRegisters(pParse, p, addrBreak);

1973 pLimit = p->pLimit;

1974 pOffset = p->pOffset;

1975 regLimit = p->iLimit;

1976 regOffset = p->iOffset;

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

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

1979 pOrderBy = p->pOrderBy;

1980

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

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

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

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

1985 break;

1986 }

1987 }

1988

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

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

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

1992 iQueue = pParse->nTab++;

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

1994 eDest = pOrderBy ? SRT_DistQueue : SRT_DistFifo;

1995 iDistinct = pParse->nTab++;

1996 }else{

1997 eDest = pOrderBy ? SRT_Queue : SRT_Fifo;

1998 }

1999 sqlite3SelectDestInit(&destQueue, eDest, iQueue);

2000

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

2002 regCurrent = ++pParse->nMem;

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

2004 if( pOrderBy ){

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

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

2007 (char*)pKeyInfo, P4_KEYINFO);

2008 destQueue.pOrderBy = pOrderBy;

2009 }else{

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

2011 }

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

2013 if( iDistinct ){

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

2015 p->selFlags \|= SF_UsesEphemeral;

2016 }

2017

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

2019 p->pOrderBy = 0;

2020

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

2022 pSetup->pNext = 0;

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

2024 pSetup->pNext = p;

2025 if( rc ) goto end_of_recursive_query;

2026

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

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

2029

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

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

2032 if( pOrderBy ){

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

2034 }else{

2035 sqlite3VdbeAddOp2(v, OP_RowData, iQueue, regCurrent);

2036 }

2037 sqlite3VdbeAddOp1(v, OP_Delete, iQueue);

2038

2039 /* Output the single row in Current */

2040 addrCont = sqlite3VdbeMakeLabel(v);

2041 codeOffset(v, regOffset, addrCont);

2042 selectInnerLoop(pParse, p, p->pEList, iCurrent,

2043 0, 0, pDest, addrCont, addrBreak);

2044 if( regLimit ){

2045 sqlite3VdbeAddOp3(v, OP_IfZero, regLimit, addrBreak, -1);

2046 VdbeCoverage(v);

2047 }

2048 sqlite3VdbeResolveLabel(v, addrCont);

2049

2050 /* Execute the recursive SELECT taking the single row in Current as

2051 ** the value for the recursive-table. Store the results in the Queue.

2052 */

2053 p->pPrior = 0;

2054 sqlite3Select(pParse, p, &destQueue);

2055 assert( p->pPrior==0 );

2056 p->pPrior = pSetup;

2057

2058 /* Keep running the loop until the Queue is empty */

2059 sqlite3VdbeAddOp2(v, OP_Goto, 0, addrTop);

2060 sqlite3VdbeResolveLabel(v, addrBreak);

2061

2062 end_of_recursive_query:

2063 sqlite3ExprListDelete(pParse->db, p->pOrderBy);

2064 p->pOrderBy = pOrderBy;

2065 p->pLimit = pLimit;

2066 p->pOffset = pOffset;

2067 return;

2068 }

2069 #endif /* SQLITE_OMIT_CTE */

2070

2071 /* Forward references */

2072 static int multiSelectOrderBy(

2073 Parse pParse, / Parsing context */

2074 Select p, / The right-most of SELECTs to be coded */

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

2076 );

2077

2078

2079 /*

2080 ** This routine is called to process a compound query form from

2081 ** two or more separate queries using UNION, UNION ALL, EXCEPT, or

2082 ** INTERSECT

2083 **

2084 ** "p" points to the right-most of the two queries. the query on the

2085 ** left is p->pPrior. The left query could also be a compound query

2086 ** in which case this routine will be called recursively.

2087 **

2088 ** The results of the total query are to be written into a destination

2089 ** of type eDest with parameter iParm.

2090 **

2091 ** Example 1: Consider a three-way compound SQL statement.

2092 **

2093 ** SELECT a FROM t1 UNION SELECT b FROM t2 UNION SELECT c FROM t3

2094 **

2095 ** This statement is parsed up as follows:

2096 **

2097 ** SELECT c FROM t3

2098 ** \|

2099 ** `-----> SELECT b FROM t2

2100 ** \|

2101 ** `------> SELECT a FROM t1

2102 **

2103 ** The arrows in the diagram above represent the Select.pPrior pointer.

2104 ** So if this routine is called with p equal to the t3 query, then

2105 ** pPrior will be the t2 query. p->op will be TK_UNION in this case.

2106 **

2107 ** Notice that because of the way SQLite parses compound SELECTs, the

2108 ** individual selects always group from left to right.

2109 */

2110 static int multiSelect(

2111 Parse pParse, / Parsing context */

2112 Select p, / The right-most of SELECTs to be coded */

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

2114 ){

2115 int rc = SQLITE_OK; /* Success code from a subroutine */

2116 Select pPrior; / Another SELECT immediately to our left */

2117 Vdbe v; / Generate code to this VDBE */

2118 SelectDest dest; /* Alternative data destination */

2119 Select pDelete = 0; / Chain of simple selects to delete */

2120 sqlite3 db; / Database connection */

2121 #ifndef SQLITE_OMIT_EXPLAIN

2122 int iSub1 = 0; /* EQP id of left-hand query */

2123 int iSub2 = 0; /* EQP id of right-hand query */

2124 #endif

2125

2126 /* Make sure there is no ORDER BY or LIMIT clause on prior SELECTs. Only

2127 ** the last (right-most) SELECT in the series may have an ORDER BY or LIMIT.

2128 */

2129 assert( p && p->pPrior ); /* Calling function guarantees this much */

2130 assert( (p->selFlags & SF_Recursive)==0 \|\| p->op==TK_ALL \|\| p->op==TK_UNION );

2131 db = pParse->db;

2132 pPrior = p->pPrior;

2133 dest = *pDest;

2134 if( pPrior->pOrderBy ){

2135 sqlite3ErrorMsg(pParse,"ORDER BY clause should come after %s not before",

2136 selectOpName(p->op));

2137 rc = 1;

2138 goto multi_select_end;

2139 }

2140 if( pPrior->pLimit ){

2141 sqlite3ErrorMsg(pParse,"LIMIT clause should come after %s not before",

2142 selectOpName(p->op));

2143 rc = 1;

2144 goto multi_select_end;

2145 }

2146

2147 v = sqlite3GetVdbe(pParse);

2148 assert( v!=0 ); /* The VDBE already created by calling function */

2149

2150 /* Create the destination temporary table if necessary

2151 */

2152 if( dest.eDest==SRT_EphemTab ){

2153 assert( p->pEList );

2154 sqlite3VdbeAddOp2(v, OP_OpenEphemeral, dest.iSDParm, p->pEList->nExpr);

2155 sqlite3VdbeChangeP5(v, BTREE_UNORDERED);

2156 dest.eDest = SRT_Table;

2157 }

2158

2159 /* Make sure all SELECTs in the statement have the same number of elements

2160 ** in their result sets.

2161 */

2162 assert( p->pEList && pPrior->pEList );

2163 if( p->pEList->nExpr!=pPrior->pEList->nExpr ){

2164 if( p->selFlags & SF_Values ){

2165 sqlite3ErrorMsg(pParse, "all VALUES must have the same number of terms");

2166 }else{

2167 sqlite3ErrorMsg(pParse, "SELECTs to the left and right of %s"

2168 " do not have the same number of result columns", selectOpName(p->op));

2169 }

2170 rc = 1;

2171 goto multi_select_end;

2172 }

2173

2174 #ifndef SQLITE_OMIT_CTE

2175 if( p->selFlags & SF_Recursive ){

2176 generateWithRecursiveQuery(pParse, p, &dest);

2177 }else

2178 #endif

2179

2180 /* Compound SELECTs that have an ORDER BY clause are handled separately.

2181 */

2182 if( p->pOrderBy ){

2183 return multiSelectOrderBy(pParse, p, pDest);

2184 }else

2185

2186 /* Generate code for the left and right SELECT statements.

2187 */

2188 switch( p->op ){

2189 case TK_ALL: {

2190 int addr = 0;

2191 int nLimit;

2192 assert( !pPrior->pLimit );

2193 pPrior->iLimit = p->iLimit;

2194 pPrior->iOffset = p->iOffset;

2195 pPrior->pLimit = p->pLimit;

2196 pPrior->pOffset = p->pOffset;

2197 explainSetInteger(iSub1, pParse->iNextSelectId);

2198 rc = sqlite3Select(pParse, pPrior, &dest);

2199 p->pLimit = 0;

2200 p->pOffset = 0;

2201 if( rc ){

2202 goto multi_select_end;

2203 }

2204 p->pPrior = 0;

2205 p->iLimit = pPrior->iLimit;

2206 p->iOffset = pPrior->iOffset;

2207 if( p->iLimit ){

2208 addr = sqlite3VdbeAddOp1(v, OP_IfZero, p->iLimit); VdbeCoverage(v);

2209 VdbeComment((v, "Jump ahead if LIMIT reached"));

2210 }

2211 explainSetInteger(iSub2, pParse->iNextSelectId);

2212 rc = sqlite3Select(pParse, p, &dest);

2213 testcase( rc!=SQLITE_OK );

2214 pDelete = p->pPrior;

2215 p->pPrior = pPrior;

2216 p->nSelectRow += pPrior->nSelectRow;

2217 if( pPrior->pLimit

2218 && sqlite3ExprIsInteger(pPrior->pLimit, &nLimit)

2219 && nLimit>0 && p->nSelectRow > (u64)nLimit

2220 ){

2221 p->nSelectRow = nLimit;

2222 }

2223 if( addr ){

2224 sqlite3VdbeJumpHere(v, addr);

2225 }

2226 break;

2227 }

2228 case TK_EXCEPT:

2229 case TK_UNION: {

2230 int unionTab; /* Cursor number of the temporary table holding result */

2231 u8 op = 0; /* One of the SRT_ operations to apply to self */

2232 int priorOp; /* The SRT_ operation to apply to prior selects */

2233 Expr pLimit, pOffset; /* Saved values of p->nLimit and p->nOffset */

2234 int addr;

2235 SelectDest uniondest;

2236

2237 testcase( p->op==TK_EXCEPT );

2238 testcase( p->op==TK_UNION );

2239 priorOp = SRT_Union;

2240 if( dest.eDest==priorOp ){

2241 /* We can reuse a temporary table generated by a SELECT to our

2242 ** right.

2243 */

2244 assert( p->pLimit==0 ); /* Not allowed on leftward elements */

2245 assert( p->pOffset==0 ); /* Not allowed on leftward elements */

2246 unionTab = dest.iSDParm;

2247 }else{

2248 /* We will need to create our own temporary table to hold the

2249 ** intermediate results.

2250 */

2251 unionTab = pParse->nTab++;

2252 assert( p->pOrderBy==0 );

2253 addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, unionTab, 0);

2254 assert( p->addrOpenEphm[0] == -1 );

2255 p->addrOpenEphm[0] = addr;

2256 findRightmost(p)->selFlags \|= SF_UsesEphemeral;

2257 assert( p->pEList );

2258 }

2259

2260 /* Code the SELECT statements to our left

2261 */

2262 assert( !pPrior->pOrderBy );

2263 sqlite3SelectDestInit(&uniondest, priorOp, unionTab);

2264 explainSetInteger(iSub1, pParse->iNextSelectId);

2265 rc = sqlite3Select(pParse, pPrior, &uniondest);

2266 if( rc ){

2267 goto multi_select_end;

2268 }

2269

2270 /* Code the current SELECT statement

2271 */

2272 if( p->op==TK_EXCEPT ){

2273 op = SRT_Except;

2274 }else{

2275 assert( p->op==TK_UNION );

2276 op = SRT_Union;

2277 }

2278 p->pPrior = 0;

2279 pLimit = p->pLimit;

2280 p->pLimit = 0;

2281 pOffset = p->pOffset;

2282 p->pOffset = 0;

2283 uniondest.eDest = op;

2284 explainSetInteger(iSub2, pParse->iNextSelectId);

2285 rc = sqlite3Select(pParse, p, &uniondest);

2286 testcase( rc!=SQLITE_OK );

2287 /* Query flattening in sqlite3Select() might refill p->pOrderBy.

2288 ** Be sure to delete p->pOrderBy, therefore, to avoid a memory leak. */

2289 sqlite3ExprListDelete(db, p->pOrderBy);

2290 pDelete = p->pPrior;

2291 p->pPrior = pPrior;

2292 p->pOrderBy = 0;

2293 if( p->op==TK_UNION ) p->nSelectRow += pPrior->nSelectRow;

2294 sqlite3ExprDelete(db, p->pLimit);

2295 p->pLimit = pLimit;

2296 p->pOffset = pOffset;

2297 p->iLimit = 0;

2298 p->iOffset = 0;

2299

2300 /* Convert the data in the temporary table into whatever form

2301 ** it is that we currently need.

2302 */

2303 assert( unionTab==dest.iSDParm \|\| dest.eDest!=priorOp );

2304 if( dest.eDest!=priorOp ){

2305 int iCont, iBreak, iStart;

2306 assert( p->pEList );

2307 if( dest.eDest==SRT_Output ){

2308 Select *pFirst = p;

2309 while( pFirst->pPrior ) pFirst = pFirst->pPrior;

2310 generateColumnNames(pParse, 0, pFirst->pEList);

2311 }

2312 iBreak = sqlite3VdbeMakeLabel(v);

2313 iCont = sqlite3VdbeMakeLabel(v);

2314 computeLimitRegisters(pParse, p, iBreak);

2315 sqlite3VdbeAddOp2(v, OP_Rewind, unionTab, iBreak); VdbeCoverage(v);

2316 iStart = sqlite3VdbeCurrentAddr(v);

2317 selectInnerLoop(pParse, p, p->pEList, unionTab,

2318 0, 0, &dest, iCont, iBreak);

2319 sqlite3VdbeResolveLabel(v, iCont);

2320 sqlite3VdbeAddOp2(v, OP_Next, unionTab, iStart); VdbeCoverage(v);

2321 sqlite3VdbeResolveLabel(v, iBreak);

2322 sqlite3VdbeAddOp2(v, OP_Close, unionTab, 0);

2323 }

2324 break;

2325 }

2326 default: assert( p->op==TK_INTERSECT ); {

2327 int tab1, tab2;

2328 int iCont, iBreak, iStart;

2329 Expr pLimit, pOffset;

2330 int addr;

2331 SelectDest intersectdest;

2332 int r1;

2333

2334 /* INTERSECT is different from the others since it requires

2335 ** two temporary tables. Hence it has its own case. Begin

2336 ** by allocating the tables we will need.

2337 */

2338 tab1 = pParse->nTab++;

2339 tab2 = pParse->nTab++;

2340 assert( p->pOrderBy==0 );

2341

2342 addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, tab1, 0);

2343 assert( p->addrOpenEphm[0] == -1 );

2344 p->addrOpenEphm[0] = addr;

2345 findRightmost(p)->selFlags \|= SF_UsesEphemeral;

2346 assert( p->pEList );

2347

2348 /* Code the SELECTs to our left into temporary table "tab1".

2349 */

2350 sqlite3SelectDestInit(&intersectdest, SRT_Union, tab1);

2351 explainSetInteger(iSub1, pParse->iNextSelectId);

2352 rc = sqlite3Select(pParse, pPrior, &intersectdest);

2353 if( rc ){

2354 goto multi_select_end;

2355 }

2356

2357 /* Code the current SELECT into temporary table "tab2"

2358 */

2359 addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, tab2, 0);

2360 assert( p->addrOpenEphm[1] == -1 );

2361 p->addrOpenEphm[1] = addr;

2362 p->pPrior = 0;

2363 pLimit = p->pLimit;

2364 p->pLimit = 0;

2365 pOffset = p->pOffset;

2366 p->pOffset = 0;

2367 intersectdest.iSDParm = tab2;

2368 explainSetInteger(iSub2, pParse->iNextSelectId);

2369 rc = sqlite3Select(pParse, p, &intersectdest);

2370 testcase( rc!=SQLITE_OK );

2371 pDelete = p->pPrior;

2372 p->pPrior = pPrior;

2373 if( p->nSelectRow>pPrior->nSelectRow ) p->nSelectRow = pPrior->nSelectRow;

2374 sqlite3ExprDelete(db, p->pLimit);

2375 p->pLimit = pLimit;

2376 p->pOffset = pOffset;

2377

2378 /* Generate code to take the intersection of the two temporary

2379 ** tables.

2380 */

2381 assert( p->pEList );

2382 if( dest.eDest==SRT_Output ){

2383 Select *pFirst = p;

2384 while( pFirst->pPrior ) pFirst = pFirst->pPrior;

2385 generateColumnNames(pParse, 0, pFirst->pEList);

2386 }

2387 iBreak = sqlite3VdbeMakeLabel(v);

2388 iCont = sqlite3VdbeMakeLabel(v);

2389 computeLimitRegisters(pParse, p, iBreak);

2390 sqlite3VdbeAddOp2(v, OP_Rewind, tab1, iBreak); VdbeCoverage(v);

2391 r1 = sqlite3GetTempReg(pParse);

2392 iStart = sqlite3VdbeAddOp2(v, OP_RowKey, tab1, r1);

2393 sqlite3VdbeAddOp4Int(v, OP_NotFound, tab2, iCont, r1, 0); VdbeCoverage(v);

2394 sqlite3ReleaseTempReg(pParse, r1);

2395 selectInnerLoop(pParse, p, p->pEList, tab1,

2396 0, 0, &dest, iCont, iBreak);

2397 sqlite3VdbeResolveLabel(v, iCont);

2398 sqlite3VdbeAddOp2(v, OP_Next, tab1, iStart); VdbeCoverage(v);

2399 sqlite3VdbeResolveLabel(v, iBreak);

2400 sqlite3VdbeAddOp2(v, OP_Close, tab2, 0);

2401 sqlite3VdbeAddOp2(v, OP_Close, tab1, 0);

2402 break;

2403 }

2404 }

2405

2406 explainComposite(pParse, p->op, iSub1, iSub2, p->op!=TK_ALL);

2407

2408 /* Compute collating sequences used by

2409 ** temporary tables needed to implement the compound select.

2410 ** Attach the KeyInfo structure to all temporary tables.

2411 **

2412 ** This section is run by the right-most SELECT statement only.

2413 ** SELECT statements to the left always skip this part. The right-most

2414 ** SELECT might also skip this part if it has no ORDER BY clause and

2415 ** no temp tables are required.

2416 */

2417 if( p->selFlags & SF_UsesEphemeral ){

2418 int i; /* Loop counter */

2419 KeyInfo pKeyInfo; / Collating sequence for the result set */

2420 Select pLoop; / For looping through SELECT statements */

2421 CollSeq *apColl; / For looping through pKeyInfo->aColl[] */

2422 int nCol; /* Number of columns in result set */

2423

2424 assert( p->pNext==0 );

2425 nCol = p->pEList->nExpr;

2426 pKeyInfo = sqlite3KeyInfoAlloc(db, nCol, 1);

2427 if( !pKeyInfo ){

2428 rc = SQLITE_NOMEM;

2429 goto multi_select_end;

2430 }

2431 for(i=0, apColl=pKeyInfo->aColl; i<nCol; i++, apColl++){

2432 *apColl = multiSelectCollSeq(pParse, p, i);

2433 if( 0==*apColl ){

2434 *apColl = db->pDfltColl;

2435 }

2436 }

2437

2438 for(pLoop=p; pLoop; pLoop=pLoop->pPrior){

2439 for(i=0; i<2; i++){

2440 int addr = pLoop->addrOpenEphm[i];

2441 if( addr<0 ){

2442 /* If [0] is unused then [1] is also unused. So we can

2443 ** always safely abort as soon as the first unused slot is found */

2444 assert( pLoop->addrOpenEphm[1]<0 );

2445 break;

2446 }

2447 sqlite3VdbeChangeP2(v, addr, nCol);

2448 sqlite3VdbeChangeP4(v, addr, (char*)sqlite3KeyInfoRef(pKeyInfo),

2449 P4_KEYINFO);

2450 pLoop->addrOpenEphm[i] = -1;

2451 }

2452 }

2453 sqlite3KeyInfoUnref(pKeyInfo);

2454 }

2455

2456 multi_select_end:

2457 pDest->iSdst = dest.iSdst;

2458 pDest->nSdst = dest.nSdst;

2459 sqlite3SelectDelete(db, pDelete);

2460 return rc;

2461 }

2462 #endif /* SQLITE_OMIT_COMPOUND_SELECT */

2463

2464 /*

2465 ** Code an output subroutine for a coroutine implementation of a

2466 ** SELECT statment.

2467 **

2468 ** The data to be output is contained in pIn->iSdst. There are

2469 ** pIn->nSdst columns to be output. pDest is where the output should

2470 ** be sent.

2471 **

2472 ** regReturn is the number of the register holding the subroutine

2473 ** return address.

2474 **

2475 ** If regPrev>0 then it is the first register in a vector that

2476 ** records the previous output. mem[regPrev] is a flag that is false

2477 ** if there has been no previous output. If regPrev>0 then code is

2478 ** generated to suppress duplicates. pKeyInfo is used for comparing

2479 ** keys.

2480 **

2481 ** If the LIMIT found in p->iLimit is reached, jump immediately to

2482 ** iBreak.

2483 */

2484 static int generateOutputSubroutine(

2485 Parse pParse, / Parsing context */

2486 Select p, / The SELECT statement */

2487 SelectDest pIn, / Coroutine supplying data */

2488 SelectDest pDest, / Where to send the data */

2489 int regReturn, /* The return address register */

2490 int regPrev, /* Previous result register. No uniqueness if 0 */

2491 KeyInfo pKeyInfo, / For comparing with previous entry */

2492 int iBreak /* Jump here if we hit the LIMIT */

2493 ){

2494 Vdbe *v = pParse->pVdbe;

2495 int iContinue;

2496 int addr;

2497

2498 addr = sqlite3VdbeCurrentAddr(v);

2499 iContinue = sqlite3VdbeMakeLabel(v);

2500

2501 /* Suppress duplicates for UNION, EXCEPT, and INTERSECT

2502 */

2503 if( regPrev ){

2504 int j1, j2;

2505 j1 = sqlite3VdbeAddOp1(v, OP_IfNot, regPrev); VdbeCoverage(v);

2506 j2 = sqlite3VdbeAddOp4(v, OP_Compare, pIn->iSdst, regPrev+1, pIn->nSdst,

2507 (char*)sqlite3KeyInfoRef(pKeyInfo), P4_KEYINFO);

2508 sqlite3VdbeAddOp3(v, OP_Jump, j2+2, iContinue, j2+2); VdbeCoverage(v);

2509 sqlite3VdbeJumpHere(v, j1);

2510 sqlite3VdbeAddOp3(v, OP_Copy, pIn->iSdst, regPrev+1, pIn->nSdst-1);

2511 sqlite3VdbeAddOp2(v, OP_Integer, 1, regPrev);

2512 }

2513 if( pParse->db->mallocFailed ) return 0;

2514

2515 /* Suppress the first OFFSET entries if there is an OFFSET clause

2516 */

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

2518

2519 switch( pDest->eDest ){

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

2521 */

2522 case SRT_Table:

2523 case SRT_EphemTab: {

2524 int r1 = sqlite3GetTempReg(pParse);

2525 int r2 = sqlite3GetTempReg(pParse);

2526 testcase( pDest->eDest==SRT_Table );

2527 testcase( pDest->eDest==SRT_EphemTab );

2528 sqlite3VdbeAddOp3(v, OP_MakeRecord, pIn->iSdst, pIn->nSdst, r1);

2529 sqlite3VdbeAddOp2(v, OP_NewRowid, pDest->iSDParm, r2);

2530 sqlite3VdbeAddOp3(v, OP_Insert, pDest->iSDParm, r1, r2);

2531 sqlite3VdbeChangeP5(v, OPFLAG_APPEND);

2532 sqlite3ReleaseTempReg(pParse, r2);

2533 sqlite3ReleaseTempReg(pParse, r1);

2534 break;

2535 }

2536

2537 #ifndef SQLITE_OMIT_SUBQUERY

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

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

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

2541 */

2542 case SRT_Set: {

2543 int r1;

2544 assert( pIn->nSdst==1 );

2545 pDest->affSdst =

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

2547 r1 = sqlite3GetTempReg(pParse);

2548 sqlite3VdbeAddOp4(v, OP_MakeRecord, pIn->iSdst, 1, r1, &pDest->affSdst,1);

2549 sqlite3ExprCacheAffinityChange(pParse, pIn->iSdst, 1);

2550 sqlite3VdbeAddOp2(v, OP_IdxInsert, pDest->iSDParm, r1);

2551 sqlite3ReleaseTempReg(pParse, r1);

2552 break;

2553 }

2554

2555 #if 0 /* Never occurs on an ORDER BY query */

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

2557 */

2558 case SRT_Exists: {

2559 sqlite3VdbeAddOp2(v, OP_Integer, 1, pDest->iSDParm);

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

2561 break;

2562 }

2563 #endif

2564

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

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

2567 ** of the scan loop.

2568 */

2569 case SRT_Mem: {

2570 assert( pIn->nSdst==1 );

2571 sqlite3ExprCodeMove(pParse, pIn->iSdst, pDest->iSDParm, 1);

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

2573 break;

2574 }

2575 #endif /* #ifndef SQLITE_OMIT_SUBQUERY */

2576

2577 /* The results are stored in a sequence of registers

2578 ** starting at pDest->iSdst. Then the co-routine yields.

2579 */

2580 case SRT_Coroutine: {

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

2582 pDest->iSdst = sqlite3GetTempRange(pParse, pIn->nSdst);

2583 pDest->nSdst = pIn->nSdst;

2584 }

2585 sqlite3ExprCodeMove(pParse, pIn->iSdst, pDest->iSdst, pDest->nSdst);

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

2587 break;

2588 }

2589

2590 /* If none of the above, then the result destination must be

2591 ** SRT_Output. This routine is never called with any other

2592 ** destination other than the ones handled above or SRT_Output.

2593 **

2594 ** For SRT_Output, results are stored in a sequence of registers.

2595 ** Then the OP_ResultRow opcode is used to cause sqlite3_step() to

2596 ** return the next row of result.

2597 */

2598 default: {

2599 assert( pDest->eDest==SRT_Output );

2600 sqlite3VdbeAddOp2(v, OP_ResultRow, pIn->iSdst, pIn->nSdst);

2601 sqlite3ExprCacheAffinityChange(pParse, pIn->iSdst, pIn->nSdst);

2602 break;

2603 }

2604 }

2605

2606 /* Jump to the end of the loop if the LIMIT is reached.

2607 */

2608 if( p->iLimit ){

2609 sqlite3VdbeAddOp3(v, OP_IfZero, p->iLimit, iBreak, -1); VdbeCoverage(v);

2610 }

2611

2612 /* Generate the subroutine return

2613 */

2614 sqlite3VdbeResolveLabel(v, iContinue);

2615 sqlite3VdbeAddOp1(v, OP_Return, regReturn);

2616

2617 return addr;

2618 }

2619

2620 /*

2621 ** Alternative compound select code generator for cases when there

2622 ** is an ORDER BY clause.

2623 **

2624 ** We assume a query of the following form:

2625 **

2626 ** <selectA> <operator> <selectB> ORDER BY <orderbylist>

2627 **

2628 ** <operator> is one of UNION ALL, UNION, EXCEPT, or INTERSECT. The idea

2629 ** is to code both <selectA> and <selectB> with the ORDER BY clause as

2630 ** co-routines. Then run the co-routines in parallel and merge the results

2631 ** into the output. In addition to the two coroutines (called selectA and

2632 ** selectB) there are 7 subroutines:

2633 **

2634 ** outA: Move the output of the selectA coroutine into the output

2635 ** of the compound query.

2636 **

2637 ** outB: Move the output of the selectB coroutine into the output

2638 ** of the compound query. (Only generated for UNION and

2639 ** UNION ALL. EXCEPT and INSERTSECT never output a row that

2640 ** appears only in B.)

2641 **

2642 ** AltB: Called when there is data from both coroutines and A<B.

2643 **

2644 ** AeqB: Called when there is data from both coroutines and A==B.

2645 **

2646 ** AgtB: Called when there is data from both coroutines and A>B.

2647 **

2648 ** EofA: Called when data is exhausted from selectA.

2649 **

2650 ** EofB: Called when data is exhausted from selectB.

2651 **

2652 ** The implementation of the latter five subroutines depend on which

2653 ** <operator> is used:

2654 **

2655 **

2656 ** UNION ALL UNION EXCEPT INTERSECT

2657 ** ------------- ----------------- -------------- -----------------

2658 ** AltB: outA, nextA outA, nextA outA, nextA nextA

2659 **

2660 ** AeqB: outA, nextA nextA nextA outA, nextA

2661 **

2662 ** AgtB: outB, nextB outB, nextB nextB nextB

2663 **

2664 ** EofA: outB, nextB outB, nextB halt halt

2665 **

2666 ** EofB: outA, nextA outA, nextA outA, nextA halt

2667 **

2668 ** In the AltB, AeqB, and AgtB subroutines, an EOF on A following nextA

2669 ** causes an immediate jump to EofA and an EOF on B following nextB causes

2670 ** an immediate jump to EofB. Within EofA and EofB, and EOF on entry or

2671 ** following nextX causes a jump to the end of the select processing.

2672 **

2673 ** Duplicate removal in the UNION, EXCEPT, and INTERSECT cases is handled

2674 ** within the output subroutine. The regPrev register set holds the previously

2675 ** output value. A comparison is made against this value and the output

2676 ** is skipped if the next results would be the same as the previous.

2677 **

2678 ** The implementation plan is to implement the two coroutines and seven

2679 ** subroutines first, then put the control logic at the bottom. Like this:

2680 **

2681 ** goto Init

2682 ** coA: coroutine for left query (A)

2683 ** coB: coroutine for right query (B)

2684 ** outA: output one row of A

2685 ** outB: output one row of B (UNION and UNION ALL only)

2686 ** EofA: ...

2687 ** EofB: ...

2688 ** AltB: ...

2689 ** AeqB: ...

2690 ** AgtB: ...

2691 ** Init: initialize coroutine registers

2692 ** yield coA

2693 ** if eof(A) goto EofA

2694 ** yield coB

2695 ** if eof(B) goto EofB

2696 ** Cmpr: Compare A, B

2697 ** Jump AltB, AeqB, AgtB

2698 ** End: ...

2699 **

2700 ** We call AltB, AeqB, AgtB, EofA, and EofB "subroutines" but they are not

2701 ** actually called using Gosub and they do not Return. EofA and EofB loop

2702 ** until all data is exhausted then jump to the "end" labe. AltB, AeqB,

2703 ** and AgtB jump to either L2 or to one of EofA or EofB.

2704 */

2705 #ifndef SQLITE_OMIT_COMPOUND_SELECT

2706 static int multiSelectOrderBy(

2707 Parse pParse, / Parsing context */

2708 Select p, / The right-most of SELECTs to be coded */

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

2710 ){

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

2712 Select pPrior; / Another SELECT immediately to our left */

2713 Vdbe v; / Generate code to this VDBE */

2714 SelectDest destA; /* Destination for coroutine A */

2715 SelectDest destB; /* Destination for coroutine B */

2716 int regAddrA; /* Address register for select-A coroutine */

2717 int regAddrB; /* Address register for select-B coroutine */

2718 int addrSelectA; /* Address of the select-A coroutine */

2719 int addrSelectB; /* Address of the select-B coroutine */

2720 int regOutA; /* Address register for the output-A subroutine */

2721 int regOutB; /* Address register for the output-B subroutine */

2722 int addrOutA; /* Address of the output-A subroutine */

2723 int addrOutB = 0; /* Address of the output-B subroutine */

2724 int addrEofA; /* Address of the select-A-exhausted subroutine */

2725 int addrEofA_noB; /* Alternate addrEofA if B is uninitialized */

2726 int addrEofB; /* Address of the select-B-exhausted subroutine */

2727 int addrAltB; /* Address of the A<B subroutine */

2728 int addrAeqB; /* Address of the A==B subroutine */

2729 int addrAgtB; /* Address of the A>B subroutine */

2730 int regLimitA; /* Limit register for select-A */

2731 int regLimitB; /* Limit register for select-A */

2732 int regPrev; /* A range of registers to hold previous output */

2733 int savedLimit; /* Saved value of p->iLimit */

2734 int savedOffset; /* Saved value of p->iOffset */

2735 int labelCmpr; /* Label for the start of the merge algorithm */

2736 int labelEnd; /* Label for the end of the overall SELECT stmt */

2737 int j1; /* Jump instructions that get retargetted */

2738 int op; /* One of TK_ALL, TK_UNION, TK_EXCEPT, TK_INTERSECT */

2739 KeyInfo pKeyDup = 0; / Comparison information for duplicate removal */

2740 KeyInfo pKeyMerge; / Comparison information for merging rows */

2741 sqlite3 db; / Database connection */

2742 ExprList pOrderBy; / The ORDER BY clause */

2743 int nOrderBy; /* Number of terms in the ORDER BY clause */

2744 int aPermute; / Mapping from ORDER BY terms to result set columns */

2745 #ifndef SQLITE_OMIT_EXPLAIN

2746 int iSub1; /* EQP id of left-hand query */

2747 int iSub2; /* EQP id of right-hand query */

2748 #endif

2749

2750 assert( p->pOrderBy!=0 );

2751 assert( pKeyDup==0 ); /* "Managed" code needs this. Ticket #3382. */

2752 db = pParse->db;

2753 v = pParse->pVdbe;

2754 assert( v!=0 ); /* Already thrown the error if VDBE alloc failed */

2755 labelEnd = sqlite3VdbeMakeLabel(v);

2756 labelCmpr = sqlite3VdbeMakeLabel(v);

2757

2758

2759 /* Patch up the ORDER BY clause

2760 */

2761 op = p->op;

2762 pPrior = p->pPrior;

2763 assert( pPrior->pOrderBy==0 );

2764 pOrderBy = p->pOrderBy;

2765 assert( pOrderBy );

2766 nOrderBy = pOrderBy->nExpr;

2767

2768 /* For operators other than UNION ALL we have to make sure that

2769 ** the ORDER BY clause covers every term of the result set. Add

2770 ** terms to the ORDER BY clause as necessary.

2771 */

2772 if( op!=TK_ALL ){

2773 for(i=1; db->mallocFailed==0 && i<=p->pEList->nExpr; i++){

2774 struct ExprList_item *pItem;

2775 for(j=0, pItem=pOrderBy->a; j<nOrderBy; j++, pItem++){

2776 assert( pItem->u.x.iOrderByCol>0 );

2777 if( pItem->u.x.iOrderByCol==i ) break;

2778 }

2779 if( j==nOrderBy ){

2780 Expr *pNew = sqlite3Expr(db, TK_INTEGER, 0);

2781 if( pNew==0 ) return SQLITE_NOMEM;

2782 pNew->flags \|= EP_IntValue;

2783 pNew->u.iValue = i;

2784 pOrderBy = sqlite3ExprListAppend(pParse, pOrderBy, pNew);

2785 if( pOrderBy ) pOrderBy->a[nOrderBy++].u.x.iOrderByCol = (u16)i;

2786 }

2787 }

2788 }

2789

2790 /* Compute the comparison permutation and keyinfo that is used with

2791 ** the permutation used to determine if the next

2792 ** row of results comes from selectA or selectB. Also add explicit

2793 ** collations to the ORDER BY clause terms so that when the subqueries

2794 ** to the right and the left are evaluated, they use the correct

2795 ** collation.

2796 */

2797 aPermute = sqlite3DbMallocRaw(db, sizeof(int)*nOrderBy);

2798 if( aPermute ){

2799 struct ExprList_item *pItem;

2800 for(i=0, pItem=pOrderBy->a; i<nOrderBy; i++, pItem++){

2801 assert( pItem->u.x.iOrderByCol>0

2802 && pItem->u.x.iOrderByCol<=p->pEList->nExpr );

2803 aPermute[i] = pItem->u.x.iOrderByCol - 1;

2804 }

2805 pKeyMerge = multiSelectOrderByKeyInfo(pParse, p, 1);

2806 }else{

2807 pKeyMerge = 0;

2808 }

2809

2810 /* Reattach the ORDER BY clause to the query.

2811 */

2812 p->pOrderBy = pOrderBy;

2813 pPrior->pOrderBy = sqlite3ExprListDup(pParse->db, pOrderBy, 0);

2814

2815 /* Allocate a range of temporary registers and the KeyInfo needed

2816 ** for the logic that removes duplicate result rows when the

2817 ** operator is UNION, EXCEPT, or INTERSECT (but not UNION ALL).

2818 */

2819 if( op==TK_ALL ){

2820 regPrev = 0;

2821 }else{

2822 int nExpr = p->pEList->nExpr;

2823 assert( nOrderBy>=nExpr \|\| db->mallocFailed );

2824 regPrev = pParse->nMem+1;

2825 pParse->nMem += nExpr+1;

2826 sqlite3VdbeAddOp2(v, OP_Integer, 0, regPrev);

2827 pKeyDup = sqlite3KeyInfoAlloc(db, nExpr, 1);

2828 if( pKeyDup ){

2829 assert( sqlite3KeyInfoIsWriteable(pKeyDup) );

2830 for(i=0; i<nExpr; i++){

2831 pKeyDup->aColl[i] = multiSelectCollSeq(pParse, p, i);

2832 pKeyDup->aSortOrder[i] = 0;

2833 }

2834 }

2835 }

2836

2837 /* Separate the left and the right query from one another

2838 */

2839 p->pPrior = 0;

2840 pPrior->pNext = 0;

2841 sqlite3ResolveOrderGroupBy(pParse, p, p->pOrderBy, "ORDER");

2842 if( pPrior->pPrior==0 ){

2843 sqlite3ResolveOrderGroupBy(pParse, pPrior, pPrior->pOrderBy, "ORDER");

2844 }

2845

2846 /* Compute the limit registers */

2847 computeLimitRegisters(pParse, p, labelEnd);

2848 if( p->iLimit && op==TK_ALL ){

2849 regLimitA = ++pParse->nMem;

2850 regLimitB = ++pParse->nMem;

2851 sqlite3VdbeAddOp2(v, OP_Copy, p->iOffset ? p->iOffset+1 : p->iLimit,

2852 regLimitA);

2853 sqlite3VdbeAddOp2(v, OP_Copy, regLimitA, regLimitB);

2854 }else{

2855 regLimitA = regLimitB = 0;

2856 }

2857 sqlite3ExprDelete(db, p->pLimit);

2858 p->pLimit = 0;

2859 sqlite3ExprDelete(db, p->pOffset);

2860 p->pOffset = 0;

2861

2862 regAddrA = ++pParse->nMem;

2863 regAddrB = ++pParse->nMem;

2864 regOutA = ++pParse->nMem;

2865 regOutB = ++pParse->nMem;

2866 sqlite3SelectDestInit(&destA, SRT_Coroutine, regAddrA);

2867 sqlite3SelectDestInit(&destB, SRT_Coroutine, regAddrB);

2868

2869 /* Generate a coroutine to evaluate the SELECT statement to the

2870 ** left of the compound operator - the "A" select.

2871 */

2872 addrSelectA = sqlite3VdbeCurrentAddr(v) + 1;

2873 j1 = sqlite3VdbeAddOp3(v, OP_InitCoroutine, regAddrA, 0, addrSelectA);

2874 VdbeComment((v, "left SELECT"));

2875 pPrior->iLimit = regLimitA;

2876 explainSetInteger(iSub1, pParse->iNextSelectId);

2877 sqlite3Select(pParse, pPrior, &destA);

2878 sqlite3VdbeAddOp1(v, OP_EndCoroutine, regAddrA);

2879 sqlite3VdbeJumpHere(v, j1);

2880

2881 /* Generate a coroutine to evaluate the SELECT statement on

2882 ** the right - the "B" select

2883 */

2884 addrSelectB = sqlite3VdbeCurrentAddr(v) + 1;

2885 j1 = sqlite3VdbeAddOp3(v, OP_InitCoroutine, regAddrB, 0, addrSelectB);

2886 VdbeComment((v, "right SELECT"));

2887 savedLimit = p->iLimit;

2888 savedOffset = p->iOffset;

2889 p->iLimit = regLimitB;

2890 p->iOffset = 0;

2891 explainSetInteger(iSub2, pParse->iNextSelectId);

2892 sqlite3Select(pParse, p, &destB);

2893 p->iLimit = savedLimit;

2894 p->iOffset = savedOffset;

2895 sqlite3VdbeAddOp1(v, OP_EndCoroutine, regAddrB);

2896

2897 /* Generate a subroutine that outputs the current row of the A

2898 ** select as the next output row of the compound select.

2899 */

2900 VdbeNoopComment((v, "Output routine for A"));

2901 addrOutA = generateOutputSubroutine(pParse,

2902 p, &destA, pDest, regOutA,

2903 regPrev, pKeyDup, labelEnd);

2904

2905 /* Generate a subroutine that outputs the current row of the B

2906 ** select as the next output row of the compound select.

2907 */

2908 if( op==TK_ALL \|\| op==TK_UNION ){

2909 VdbeNoopComment((v, "Output routine for B"));

2910 addrOutB = generateOutputSubroutine(pParse,

2911 p, &destB, pDest, regOutB,

2912 regPrev, pKeyDup, labelEnd);

2913 }

2914 sqlite3KeyInfoUnref(pKeyDup);

2915

2916 /* Generate a subroutine to run when the results from select A

2917 ** are exhausted and only data in select B remains.

2918 */

2919 if( op==TK_EXCEPT \|\| op==TK_INTERSECT ){

2920 addrEofA_noB = addrEofA = labelEnd;

2921 }else{

2922 VdbeNoopComment((v, "eof-A subroutine"));

2923 addrEofA = sqlite3VdbeAddOp2(v, OP_Gosub, regOutB, addrOutB);

2924 addrEofA_noB = sqlite3VdbeAddOp2(v, OP_Yield, regAddrB, labelEnd);

2925 VdbeCoverage(v);

2926 sqlite3VdbeAddOp2(v, OP_Goto, 0, addrEofA);

2927 p->nSelectRow += pPrior->nSelectRow;

2928 }

2929

2930 /* Generate a subroutine to run when the results from select B

2931 ** are exhausted and only data in select A remains.

2932 */

2933 if( op==TK_INTERSECT ){

2934 addrEofB = addrEofA;

2935 if( p->nSelectRow > pPrior->nSelectRow ) p->nSelectRow = pPrior->nSelectRow;

2936 }else{

2937 VdbeNoopComment((v, "eof-B subroutine"));

2938 addrEofB = sqlite3VdbeAddOp2(v, OP_Gosub, regOutA, addrOutA);

2939 sqlite3VdbeAddOp2(v, OP_Yield, regAddrA, labelEnd); VdbeCoverage(v);

2940 sqlite3VdbeAddOp2(v, OP_Goto, 0, addrEofB);

2941 }

2942

2943 /* Generate code to handle the case of A<B

2944 */

2945 VdbeNoopComment((v, "A-lt-B subroutine"));

2946 addrAltB = sqlite3VdbeAddOp2(v, OP_Gosub, regOutA, addrOutA);

2947 sqlite3VdbeAddOp2(v, OP_Yield, regAddrA, addrEofA); VdbeCoverage(v);

2948 sqlite3VdbeAddOp2(v, OP_Goto, 0, labelCmpr);

2949

2950 /* Generate code to handle the case of A==B

2951 */

2952 if( op==TK_ALL ){

2953 addrAeqB = addrAltB;

2954 }else if( op==TK_INTERSECT ){

2955 addrAeqB = addrAltB;

2956 addrAltB++;

2957 }else{

2958 VdbeNoopComment((v, "A-eq-B subroutine"));

2959 addrAeqB =

2960 sqlite3VdbeAddOp2(v, OP_Yield, regAddrA, addrEofA); VdbeCoverage(v);

2961 sqlite3VdbeAddOp2(v, OP_Goto, 0, labelCmpr);

2962 }

2963

2964 /* Generate code to handle the case of A>B

2965 */

2966 VdbeNoopComment((v, "A-gt-B subroutine"));

2967 addrAgtB = sqlite3VdbeCurrentAddr(v);

2968 if( op==TK_ALL \|\| op==TK_UNION ){

2969 sqlite3VdbeAddOp2(v, OP_Gosub, regOutB, addrOutB);

2970 }

2971 sqlite3VdbeAddOp2(v, OP_Yield, regAddrB, addrEofB); VdbeCoverage(v);

2972 sqlite3VdbeAddOp2(v, OP_Goto, 0, labelCmpr);

2973

2974 /* This code runs once to initialize everything.

2975 */

2976 sqlite3VdbeJumpHere(v, j1);

2977 sqlite3VdbeAddOp2(v, OP_Yield, regAddrA, addrEofA_noB); VdbeCoverage(v);

2978 sqlite3VdbeAddOp2(v, OP_Yield, regAddrB, addrEofB); VdbeCoverage(v);

2979

2980 /* Implement the main merge loop

2981 */

2982 sqlite3VdbeResolveLabel(v, labelCmpr);

2983 sqlite3VdbeAddOp4(v, OP_Permutation, 0, 0, 0, (char*)aPermute, P4_INTARRAY);

2984 sqlite3VdbeAddOp4(v, OP_Compare, destA.iSdst, destB.iSdst, nOrderBy,

2985 (char*)pKeyMerge, P4_KEYINFO);

2986 sqlite3VdbeChangeP5(v, OPFLAG_PERMUTE);

2987 sqlite3VdbeAddOp3(v, OP_Jump, addrAltB, addrAeqB, addrAgtB); VdbeCoverage(v);

2988

2989 /* Jump to the this point in order to terminate the query.

2990 */

2991 sqlite3VdbeResolveLabel(v, labelEnd);

2992

2993 /* Set the number of output columns

2994 */

2995 if( pDest->eDest==SRT_Output ){

2996 Select *pFirst = pPrior;

2997 while( pFirst->pPrior ) pFirst = pFirst->pPrior;

2998 generateColumnNames(pParse, 0, pFirst->pEList);

2999 }

3000

3001 /* Reassembly the compound query so that it will be freed correctly

3002 ** by the calling function */

3003 if( p->pPrior ){

3004 sqlite3SelectDelete(db, p->pPrior);

3005 }

3006 p->pPrior = pPrior;

3007 pPrior->pNext = p;

3008

3009 /*** TBD: Insert subroutine calls to close cursors on incomplete

3010 ** subqueries **/

3011 explainComposite(pParse, p->op, iSub1, iSub2, 0);

3012 return SQLITE_OK;

3013 }

3014 #endif

3015

3016 #if !defined(SQLITE_OMIT_SUBQUERY) \|\| !defined(SQLITE_OMIT_VIEW)

3017 /* Forward Declarations */

3018 static void substExprList(sqlite3, ExprList, int, ExprList*);

3019 static void substSelect(sqlite3, Select , int, ExprList *);

3020

3021 /*

3022 ** Scan through the expression pExpr. Replace every reference to

3023 ** a column in table number iTable with a copy of the iColumn-th

3024 ** entry in pEList. (But leave references to the ROWID column

3025 ** unchanged.)

3026 **

3027 ** This routine is part of the flattening procedure. A subquery

3028 ** whose result set is defined by pEList appears as entry in the

3029 ** FROM clause of a SELECT such that the VDBE cursor assigned to that

3030 ** FORM clause entry is iTable. This routine make the necessary

3031 ** changes to pExpr so that it refers directly to the source table

3032 ** of the subquery rather the result set of the subquery.

3033 */

3034 static Expr *substExpr(

3035 sqlite3 db, / Report malloc errors to this connection */

3036 Expr pExpr, / Expr in which substitution occurs */

3037 int iTable, /* Table to be substituted */

3038 ExprList pEList / Substitute expressions */

3039 ){

3040 if( pExpr==0 ) return 0;

3041 if( pExpr->op==TK_COLUMN && pExpr->iTable==iTable ){

3042 if( pExpr->iColumn<0 ){

3043 pExpr->op = TK_NULL;

3044 }else{

3045 Expr *pNew;

3046 assert( pEList!=0 && pExpr->iColumn<pEList->nExpr );

3047 assert( pExpr->pLeft==0 && pExpr->pRight==0 );

3048 pNew = sqlite3ExprDup(db, pEList->a[pExpr->iColumn].pExpr, 0);

3049 sqlite3ExprDelete(db, pExpr);

3050 pExpr = pNew;

3051 }

3052 }else{

3053 pExpr->pLeft = substExpr(db, pExpr->pLeft, iTable, pEList);

3054 pExpr->pRight = substExpr(db, pExpr->pRight, iTable, pEList);

3055 if( ExprHasProperty(pExpr, EP_xIsSelect) ){

3056 substSelect(db, pExpr->x.pSelect, iTable, pEList);

3057 }else{

3058 substExprList(db, pExpr->x.pList, iTable, pEList);

3059 }

3060 }

3061 return pExpr;

3062 }

3063 static void substExprList(

3064 sqlite3 db, / Report malloc errors here */

3065 ExprList pList, / List to scan and in which to make substitutes */

3066 int iTable, /* Table to be substituted */

3067 ExprList pEList / Substitute values */

3068 ){

3069 int i;

3070 if( pList==0 ) return;

3071 for(i=0; i<pList->nExpr; i++){

3072 pList->a[i].pExpr = substExpr(db, pList->a[i].pExpr, iTable, pEList);

3073 }

3074 }

3075 static void substSelect(

3076 sqlite3 db, / Report malloc errors here */

3077 Select p, / SELECT statement in which to make substitutions */

3078 int iTable, /* Table to be replaced */

3079 ExprList pEList / Substitute values */

3080 ){

3081 SrcList *pSrc;

3082 struct SrcList_item *pItem;

3083 int i;

3084 if( !p ) return;

3085 substExprList(db, p->pEList, iTable, pEList);

3086 substExprList(db, p->pGroupBy, iTable, pEList);

3087 substExprList(db, p->pOrderBy, iTable, pEList);

3088 p->pHaving = substExpr(db, p->pHaving, iTable, pEList);

3089 p->pWhere = substExpr(db, p->pWhere, iTable, pEList);

3090 substSelect(db, p->pPrior, iTable, pEList);

3091 pSrc = p->pSrc;

3092 assert( pSrc ); /* Even for (SELECT 1) we have: pSrc!=0 but pSrc->nSrc==0 */

3093 if( ALWAYS(pSrc) ){

3094 for(i=pSrc->nSrc, pItem=pSrc->a; i>0; i--, pItem++){

3095 substSelect(db, pItem->pSelect, iTable, pEList);

3096 }

3097 }

3098 }

3099 #endif /* !defined(SQLITE_OMIT_SUBQUERY) \|\| !defined(SQLITE_OMIT_VIEW) */

3100

3101 #if !defined(SQLITE_OMIT_SUBQUERY) \|\| !defined(SQLITE_OMIT_VIEW)

3102 /*

3103 ** This routine attempts to flatten subqueries as a performance optimization.

3104 ** This routine returns 1 if it makes changes and 0 if no flattening occurs.

3105 **

3106 ** To understand the concept of flattening, consider the following

3107 ** query:

3108 **

3109 ** SELECT a FROM (SELECT x+y AS a FROM t1 WHERE z<100) WHERE a>5

3110 **

3111 ** The default way of implementing this query is to execute the

3112 ** subquery first and store the results in a temporary table, then

3113 ** run the outer query on that temporary table. This requires two

3114 ** passes over the data. Furthermore, because the temporary table

3115 ** has no indices, the WHERE clause on the outer query cannot be

3116 ** optimized.

3117 **

3118 ** This routine attempts to rewrite queries such as the above into

3119 ** a single flat select, like this:

3120 **

3121 ** SELECT x+y AS a FROM t1 WHERE z<100 AND a>5

3122 **

3123 ** The code generated for this simplification gives the same result

3124 ** but only has to scan the data once. And because indices might

3125 ** exist on the table t1, a complete scan of the data might be

3126 ** avoided.

3127 **

3128 ** Flattening is only attempted if all of the following are true:

3129 **

3130 ** (1) The subquery and the outer query do not both use aggregates.

3131 **

3132 ** (2) The subquery is not an aggregate or the outer query is not a join.

3133 **

3134 ** (3) The subquery is not the right operand of a left outer join

3135 ** (Originally ticket #306. Strengthened by ticket #3300)

3136 **

3137 ** (4) The subquery is not DISTINCT.

3138 **

3139 () At one point restrictions (4) and (5) defined a subset of DISTINCT

3140 ** sub-queries that were excluded from this optimization. Restriction

3141 ** (4) has since been expanded to exclude all DISTINCT subqueries.

3142 **

3143 ** (6) The subquery does not use aggregates or the outer query is not

3144 ** DISTINCT.

3145 **

3146 ** (7) The subquery has a FROM clause. TODO: For subqueries without

3147 ** A FROM clause, consider adding a FROM close with the special

3148 ** table sqlite_once that consists of a single row containing a

3149 ** single NULL.

3150 **

3151 ** (8) The subquery does not use LIMIT or the outer query is not a join.

3152 **

3153 ** (9) The subquery does not use LIMIT or the outer query does not use

3154 ** aggregates.

3155 **

3156 () Restriction (10) was removed from the code on 2005-02-05 but we

3157 ** accidently carried the comment forward until 2014-09-15. Original

3158 ** text: "The subquery does not use aggregates or the outer query does no t

3159 ** use LIMIT."

3160 **

3161 ** (11) The subquery and the outer query do not both have ORDER BY clauses.

3162 **

3163 () Not implemented. Subsumed into restriction (3). Was previously

3164 ** a separate restriction deriving from ticket #350.

3165 **

3166 ** (13) The subquery and outer query do not both use LIMIT.

3167 **

3168 ** (14) The subquery does not use OFFSET.

3169 **

3170 ** (15) The outer query is not part of a compound select or the

3171 ** subquery does not have a LIMIT clause.

3172 ** (See ticket #2339 and ticket [02a8e81d44]).

3173 **

3174 ** (16) The outer query is not an aggregate or the subquery does

3175 ** not contain ORDER BY. (Ticket #2942) This used to not matter

3176 ** until we introduced the group_concat() function.

3177 **

3178 ** (17) The sub-query is not a compound select, or it is a UNION ALL

3179 ** compound clause made up entirely of non-aggregate queries, and

3180 ** the parent query:

3181 **

3182 ** * is not itself part of a compound select,

3183 ** * is not an aggregate or DISTINCT query, and

3184 ** * is not a join

3185 **

3186 ** The parent and sub-query may contain WHERE clauses. Subject to

3187 ** rules (11), (13) and (14), they may also contain ORDER BY,

3188 ** LIMIT and OFFSET clauses. The subquery cannot use any compound

3189 ** operator other than UNION ALL because all the other compound

3190 ** operators have an implied DISTINCT which is disallowed by

3191 ** restriction (4).

3192 **

3193 ** Also, each component of the sub-query must return the same number

3194 ** of result columns. This is actually a requirement for any compound

3195 ** SELECT statement, but all the code here does is make sure that no

3196 ** such (illegal) sub-query is flattened. The caller will detect the

3197 ** syntax error and return a detailed message.

3198 **

3199 ** (18) If the sub-query is a compound select, then all terms of the

3200 ** ORDER by clause of the parent must be simple references to

3201 ** columns of the sub-query.

3202 **

3203 ** (19) The subquery does not use LIMIT or the outer query does not

3204 ** have a WHERE clause.

3205 **

3206 ** (20) If the sub-query is a compound select, then it must not use

3207 ** an ORDER BY clause. Ticket #3773. We could relax this constraint

3208 ** somewhat by saying that the terms of the ORDER BY clause must

3209 ** appear as unmodified result columns in the outer query. But we

3210 ** have other optimizations in mind to deal with that case.

3211 **

3212 ** (21) The subquery does not use LIMIT or the outer query is not

3213 ** DISTINCT. (See ticket [752e1646fc]).

3214 **

3215 ** (22) The subquery is not a recursive CTE.

3216 **

3217 ** (23) The parent is not a recursive CTE, or the sub-query is not a

3218 ** compound query. This restriction is because transforming the

3219 ** parent to a compound query confuses the code that handles

3220 ** recursive queries in multiSelect().

3221 **

3222 ** (24) The subquery is not an aggregate that uses the built-in min() or

3223 ** or max() functions. (Without this restriction, a query like:

3224 ** "SELECT x FROM (SELECT max(y), x FROM t1)" would not necessarily

3225 ** return the value X for which Y was maximal.)

3226 **

3227 **

3228 ** In this routine, the "p" parameter is a pointer to the outer query.

3229 ** The subquery is p->pSrc->a[iFrom]. isAgg is true if the outer query

3230 ** uses aggregates and subqueryIsAgg is true if the subquery uses aggregates.

3231 **

3232 ** If flattening is not attempted, this routine is a no-op and returns 0.

3233 ** If flattening is attempted this routine returns 1.

3234 **

3235 ** All of the expression analysis must occur on both the outer query and

3236 ** the subquery before this routine runs.

3237 */

3238 static int flattenSubquery(

3239 Parse pParse, / Parsing context */

3240 Select p, / The parent or outer SELECT statement */

3241 int iFrom, /* Index in p->pSrc->a[] of the inner subquery */

3242 int isAgg, /* True if outer SELECT uses aggregate functions */

3243 int subqueryIsAgg /* True if the subquery uses aggregate functions */

3244 ){

3245 const char *zSavedAuthContext = pParse->zAuthContext;

3246 Select *pParent;

3247 Select pSub; / The inner query or "subquery" */

3248 Select pSub1; / Pointer to the rightmost select in sub-query */

3249 SrcList pSrc; / The FROM clause of the outer query */

3250 SrcList pSubSrc; / The FROM clause of the subquery */

3251 ExprList pList; / The result set of the outer query */

3252 int iParent; /* VDBE cursor number of the pSub result set temp table */

3253 int i; /* Loop counter */

3254 Expr pWhere; / The WHERE clause */

3255 struct SrcList_item pSubitem; / The subquery */

3256 sqlite3 *db = pParse->db;

3257

3258 /* Check to see if flattening is permitted. Return 0 if not.

3259 */

3260 assert( p!=0 );

3261 assert( p->pPrior==0 ); /* Unable to flatten compound queries */

3262 if( OptimizationDisabled(db, SQLITE_QueryFlattener) ) return 0;

3263 pSrc = p->pSrc;

3264 assert( pSrc && iFrom>=0 && iFrom<pSrc->nSrc );

3265 pSubitem = &pSrc->a[iFrom];

3266 iParent = pSubitem->iCursor;

3267 pSub = pSubitem->pSelect;

3268 assert( pSub!=0 );

3269 if( isAgg && subqueryIsAgg ) return 0; /* Restriction (1) */

3270 if( subqueryIsAgg && pSrc->nSrc>1 ) return 0; /* Restriction (2) */

3271 pSubSrc = pSub->pSrc;

3272 assert( pSubSrc );

3273 /* Prior to version 3.1.2, when LIMIT and OFFSET had to be simple constants,

3274 ** not arbitrary expressions, we allowed some combining of LIMIT and OFFSET

3275 ** because they could be computed at compile-time. But when LIMIT and OFFSET

3276 ** became arbitrary expressions, we were forced to add restrictions (13)

3277 ** and (14). */

3278 if( pSub->pLimit && p->pLimit ) return 0; /* Restriction (13) */

3279 if( pSub->pOffset ) return 0; /* Restriction (14) */

3280 if( (p->selFlags & SF_Compound)!=0 && pSub->pLimit ){

3281 return 0; /* Restriction (15) */

3282 }

3283 if( pSubSrc->nSrc==0 ) return 0; /* Restriction (7) */

3284 if( pSub->selFlags & SF_Distinct ) return 0; /* Restriction (5) */

3285 if( pSub->pLimit && (pSrc->nSrc>1 \|\| isAgg) ){

3286 return 0; /* Restrictions (8)(9) */

3287 }

3288 if( (p->selFlags & SF_Distinct)!=0 && subqueryIsAgg ){

3289 return 0; /* Restriction (6) */

3290 }

3291 if( p->pOrderBy && pSub->pOrderBy ){

3292 return 0; /* Restriction (11) */

3293 }

3294 if( isAgg && pSub->pOrderBy ) return 0; /* Restriction (16) */

3295 if( pSub->pLimit && p->pWhere ) return 0; /* Restriction (19) */

3296 if( pSub->pLimit && (p->selFlags & SF_Distinct)!=0 ){

3297 return 0; /* Restriction (21) */

3298 }

3299 testcase( pSub->selFlags & SF_Recursive );

3300 testcase( pSub->selFlags & SF_MinMaxAgg );

3301 if( pSub->selFlags & (SF_Recursive\|SF_MinMaxAgg) ){

3302 return 0; /* Restrictions (22) and (24) */

3303 }

3304 if( (p->selFlags & SF_Recursive) && pSub->pPrior ){

3305 return 0; /* Restriction (23) */

3306 }

3307

3308 /* OBSOLETE COMMENT 1:

3309 ** Restriction 3: If the subquery is a join, make sure the subquery is

3310 ** not used as the right operand of an outer join. Examples of why this

3311 ** is not allowed:

3312 **

3313 ** t1 LEFT OUTER JOIN (t2 JOIN t3)

3314 **

3315 ** If we flatten the above, we would get

3316 **

3317 ** (t1 LEFT OUTER JOIN t2) JOIN t3

3318 **

3319 ** which is not at all the same thing.

3320 **

3321 ** OBSOLETE COMMENT 2:

3322 ** Restriction 12: If the subquery is the right operand of a left outer

3323 ** join, make sure the subquery has no WHERE clause.

3324 ** An examples of why this is not allowed:

3325 **

3326 ** t1 LEFT OUTER JOIN (SELECT * FROM t2 WHERE t2.x>0)

3327 **

3328 ** If we flatten the above, we would get

3329 **

3330 ** (t1 LEFT OUTER JOIN t2) WHERE t2.x>0

3331 **

3332 ** But the t2.x>0 test will always fail on a NULL row of t2, which

3333 ** effectively converts the OUTER JOIN into an INNER JOIN.

3334 **

3335 ** THIS OVERRIDES OBSOLETE COMMENTS 1 AND 2 ABOVE:

3336 ** Ticket #3300 shows that flattening the right term of a LEFT JOIN

3337 ** is fraught with danger. Best to avoid the whole thing. If the

3338 ** subquery is the right term of a LEFT JOIN, then do not flatten.

3339 */

3340 if( (pSubitem->jointype & JT_OUTER)!=0 ){

3341 return 0;

3342 }

3343

3344 /* Restriction 17: If the sub-query is a compound SELECT, then it must

3345 ** use only the UNION ALL operator. And none of the simple select queries

3346 ** that make up the compound SELECT are allowed to be aggregate or distinct

3347 ** queries.

3348 */

3349 if( pSub->pPrior ){

3350 if( pSub->pOrderBy ){

3351 return 0; /* Restriction 20 */

3352 }

3353 if( isAgg \|\| (p->selFlags & SF_Distinct)!=0 \|\| pSrc->nSrc!=1 ){

3354 return 0;

3355 }

3356 for(pSub1=pSub; pSub1; pSub1=pSub1->pPrior){

3357 testcase( (pSub1->selFlags & (SF_Distinct\|SF_Aggregate))==SF_Distinct );

3358 testcase( (pSub1->selFlags & (SF_Distinct\|SF_Aggregate))==SF_Aggregate );

3359 assert( pSub->pSrc!=0 );

3360 if( (pSub1->selFlags & (SF_Distinct\|SF_Aggregate))!=0

3361 \|\| (pSub1->pPrior && pSub1->op!=TK_ALL)

3362 \|\| pSub1->pSrc->nSrc<1

3363 \|\| pSub->pEList->nExpr!=pSub1->pEList->nExpr

3364 ){

3365 return 0;

3366 }

3367 testcase( pSub1->pSrc->nSrc>1 );

3368 }

3369

3370 /* Restriction 18. */

3371 if( p->pOrderBy ){

3372 int ii;

3373 for(ii=0; ii<p->pOrderBy->nExpr; ii++){

3374 if( p->pOrderBy->a[ii].u.x.iOrderByCol==0 ) return 0;

3375 }

3376 }

3377 }

3378

3379 /*** If we reach this point, flattening is permitted. ***/

3380 SELECTTRACE(1,pParse,p,("flatten %s.%p from term %d\n",

3381 pSub->zSelName, pSub, iFrom));

3382

3383 /* Authorize the subquery */

3384 pParse->zAuthContext = pSubitem->zName;

3385 TESTONLY(i =) sqlite3AuthCheck(pParse, SQLITE_SELECT, 0, 0, 0);

3386 testcase( i==SQLITE_DENY );

3387 pParse->zAuthContext = zSavedAuthContext;

3388

3389 /* If the sub-query is a compound SELECT statement, then (by restrictions

3390 ** 17 and 18 above) it must be a UNION ALL and the parent query must

3391 ** be of the form:

3392 **

3393 ** SELECT <expr-list> FROM (<sub-query>) <where-clause>

3394 **

3395 ** followed by any ORDER BY, LIMIT and/or OFFSET clauses. This block

3396 ** creates N-1 copies of the parent query without any ORDER BY, LIMIT or

3397 ** OFFSET clauses and joins them to the left-hand-side of the original

3398 ** using UNION ALL operators. In this case N is the number of simple

3399 ** select statements in the compound sub-query.

3400 **

3401 ** Example:

3402 **

3403 ** SELECT a+1 FROM (

3404 ** SELECT x FROM tab

3405 ** UNION ALL

3406 ** SELECT y FROM tab

3407 ** UNION ALL

3408 ** SELECT abs(z*2) FROM tab2

3409 ** ) WHERE a!=5 ORDER BY 1

3410 **

3411 ** Transformed into:

3412 **

3413 ** SELECT x+1 FROM tab WHERE x+1!=5

3414 ** UNION ALL

3415 ** SELECT y+1 FROM tab WHERE y+1!=5

3416 ** UNION ALL

3417 ** SELECT abs(z2)+1 FROM tab2 WHERE abs(z2)+1!=5

3418 ** ORDER BY 1

3419 **

3420 ** We call this the "compound-subquery flattening".

3421 */

3422 for(pSub=pSub->pPrior; pSub; pSub=pSub->pPrior){

3423 Select *pNew;

3424 ExprList *pOrderBy = p->pOrderBy;

3425 Expr *pLimit = p->pLimit;

3426 Expr *pOffset = p->pOffset;

3427 Select *pPrior = p->pPrior;

3428 p->pOrderBy = 0;

3429 p->pSrc = 0;

3430 p->pPrior = 0;

3431 p->pLimit = 0;

3432 p->pOffset = 0;

3433 pNew = sqlite3SelectDup(db, p, 0);

3434 sqlite3SelectSetName(pNew, pSub->zSelName);

3435 p->pOffset = pOffset;

3436 p->pLimit = pLimit;

3437 p->pOrderBy = pOrderBy;

3438 p->pSrc = pSrc;

3439 p->op = TK_ALL;

3440 if( pNew==0 ){

3441 p->pPrior = pPrior;

3442 }else{

3443 pNew->pPrior = pPrior;

3444 if( pPrior ) pPrior->pNext = pNew;

3445 pNew->pNext = p;

3446 p->pPrior = pNew;

3447 SELECTTRACE(2,pParse,p,

3448 ("compound-subquery flattener creates %s.%p as peer\n",

3449 pNew->zSelName, pNew));

3450 }

3451 if( db->mallocFailed ) return 1;

3452 }

3453

3454 /* Begin flattening the iFrom-th entry of the FROM clause

3455 ** in the outer query.

3456 */

3457 pSub = pSub1 = pSubitem->pSelect;

3458

3459 /* Delete the transient table structure associated with the

3460 ** subquery

3461 */

3462 sqlite3DbFree(db, pSubitem->zDatabase);

3463 sqlite3DbFree(db, pSubitem->zName);

3464 sqlite3DbFree(db, pSubitem->zAlias);

3465 pSubitem->zDatabase = 0;

3466 pSubitem->zName = 0;

3467 pSubitem->zAlias = 0;

3468 pSubitem->pSelect = 0;

3469

3470 /* Defer deleting the Table object associated with the

3471 ** subquery until code generation is

3472 ** complete, since there may still exist Expr.pTab entries that

3473 ** refer to the subquery even after flattening. Ticket #3346.

3474 **

3475 ** pSubitem->pTab is always non-NULL by test restrictions and tests above.

3476 */

3477 if( ALWAYS(pSubitem->pTab!=0) ){

3478 Table *pTabToDel = pSubitem->pTab;

3479 if( pTabToDel->nRef==1 ){

3480 Parse *pToplevel = sqlite3ParseToplevel(pParse);

3481 pTabToDel->pNextZombie = pToplevel->pZombieTab;

3482 pToplevel->pZombieTab = pTabToDel;

3483 }else{

3484 pTabToDel->nRef--;

3485 }

3486 pSubitem->pTab = 0;

3487 }

3488

3489 /* The following loop runs once for each term in a compound-subquery

3490 ** flattening (as described above). If we are doing a different kind

3491 ** of flattening - a flattening other than a compound-subquery flattening -

3492 ** then this loop only runs once.

3493 **

3494 ** This loop moves all of the FROM elements of the subquery into the

3495 ** the FROM clause of the outer query. Before doing this, remember

3496 ** the cursor number for the original outer query FROM element in

3497 ** iParent. The iParent cursor will never be used. Subsequent code

3498 ** will scan expressions looking for iParent references and replace

3499 ** those references with expressions that resolve to the subquery FROM

3500 ** elements we are now copying in.

3501 */

3502 for(pParent=p; pParent; pParent=pParent->pPrior, pSub=pSub->pPrior){

3503 int nSubSrc;

3504 u8 jointype = 0;

3505 pSubSrc = pSub->pSrc; /* FROM clause of subquery */

3506 nSubSrc = pSubSrc->nSrc; /* Number of terms in subquery FROM clause */

3507 pSrc = pParent->pSrc; /* FROM clause of the outer query */

3508

3509 if( pSrc ){

3510 assert( pParent==p ); /* First time through the loop */

3511 jointype = pSubitem->jointype;

3512 }else{

3513 assert( pParent!=p ); /* 2nd and subsequent times through the loop */

3514 pSrc = pParent->pSrc = sqlite3SrcListAppend(db, 0, 0, 0);

3515 if( pSrc==0 ){

3516 assert( db->mallocFailed );

3517 break;

3518 }

3519 }

3520

3521 /* The subquery uses a single slot of the FROM clause of the outer

3522 ** query. If the subquery has more than one element in its FROM clause,

3523 ** then expand the outer query to make space for it to hold all elements

3524 ** of the subquery.

3525 **

3526 ** Example:

3527 **

3528 ** SELECT * FROM tabA, (SELECT * FROM sub1, sub2), tabB;

3529 **

3530 ** The outer query has 3 slots in its FROM clause. One slot of the

3531 ** outer query (the middle slot) is used by the subquery. The next

3532 ** block of code will expand the out query to 4 slots. The middle

3533 ** slot is expanded to two slots in order to make space for the

3534 ** two elements in the FROM clause of the subquery.

3535 */

3536 if( nSubSrc>1 ){

3537 pParent->pSrc = pSrc = sqlite3SrcListEnlarge(db, pSrc, nSubSrc-1,iFrom+1);

3538 if( db->mallocFailed ){

3539 break;

3540 }

3541 }

3542

3543 /* Transfer the FROM clause terms from the subquery into the

3544 ** outer query.

3545 */

3546 for(i=0; i<nSubSrc; i++){

3547 sqlite3IdListDelete(db, pSrc->a[i+iFrom].pUsing);

3548 pSrc->a[i+iFrom] = pSubSrc->a[i];

3549 memset(&pSubSrc->a[i], 0, sizeof(pSubSrc->a[i]));

3550 }

3551 pSrc->a[iFrom].jointype = jointype;

3552

3553 /* Now begin substituting subquery result set expressions for

3554 ** references to the iParent in the outer query.

3555 **

3556 ** Example:

3557 **

3558 ** SELECT a+5, b10 FROM (SELECT x3 AS a, y+10 AS b FROM t1) WHERE a>b;

3559 ** \ \_____________ subquery __________/ /

3560 ** \_____________________ outer query ______________________________/

3561 **

3562 ** We look at every expression in the outer query and every place we see

3563 ** "a" we substitute "x*3" and every place we see "b" we substitute "y+10".

3564 */

3565 pList = pParent->pEList;

3566 for(i=0; i<pList->nExpr; i++){

3567 if( pList->a[i].zName==0 ){

3568 char *zName = sqlite3DbStrDup(db, pList->a[i].zSpan);

3569 sqlite3Dequote(zName);

3570 pList->a[i].zName = zName;

3571 }

3572 }

3573 substExprList(db, pParent->pEList, iParent, pSub->pEList);

3574 if( isAgg ){

3575 substExprList(db, pParent->pGroupBy, iParent, pSub->pEList);

3576 pParent->pHaving = substExpr(db, pParent->pHaving, iParent, pSub->pEList);

3577 }

3578 if( pSub->pOrderBy ){

3579 /* At this point, any non-zero iOrderByCol values indicate that the

3580 ** ORDER BY column expression is identical to the iOrderByCol'th

3581 ** expression returned by SELECT statement pSub. Since these values

3582 ** do not necessarily correspond to columns in SELECT statement pParent,

3583 ** zero them before transfering the ORDER BY clause.

3584 **

3585 ** Not doing this may cause an error if a subsequent call to this

3586 ** function attempts to flatten a compound sub-query into pParent

3587 ** (the only way this can happen is if the compound sub-query is

3588 ** currently part of pSub->pSrc). See ticket [d11a6e908f]. */

3589 ExprList *pOrderBy = pSub->pOrderBy;

3590 for(i=0; i<pOrderBy->nExpr; i++){

3591 pOrderBy->a[i].u.x.iOrderByCol = 0;

3592 }

3593 assert( pParent->pOrderBy==0 );

3594 assert( pSub->pPrior==0 );

3595 pParent->pOrderBy = pOrderBy;

3596 pSub->pOrderBy = 0;

3597 }else if( pParent->pOrderBy ){

3598 substExprList(db, pParent->pOrderBy, iParent, pSub->pEList);

3599 }

3600 if( pSub->pWhere ){

3601 pWhere = sqlite3ExprDup(db, pSub->pWhere, 0);

3602 }else{

3603 pWhere = 0;

3604 }

3605 if( subqueryIsAgg ){

3606 assert( pParent->pHaving==0 );

3607 pParent->pHaving = pParent->pWhere;

3608 pParent->pWhere = pWhere;

3609 pParent->pHaving = substExpr(db, pParent->pHaving, iParent, pSub->pEList);

3610 pParent->pHaving = sqlite3ExprAnd(db, pParent->pHaving,

3611 sqlite3ExprDup(db, pSub->pHaving, 0));

3612 assert( pParent->pGroupBy==0 );

3613 pParent->pGroupBy = sqlite3ExprListDup(db, pSub->pGroupBy, 0);

3614 }else{

3615 pParent->pWhere = substExpr(db, pParent->pWhere, iParent, pSub->pEList);

3616 pParent->pWhere = sqlite3ExprAnd(db, pParent->pWhere, pWhere);

3617 }

3618

3619 /* The flattened query is distinct if either the inner or the

3620 ** outer query is distinct.

3621 */

3622 pParent->selFlags \|= pSub->selFlags & SF_Distinct;

3623

3624 /*

3625 ** SELECT ... FROM (SELECT ... LIMIT a OFFSET b) LIMIT x OFFSET y;

3626 **

3627 ** One is tempted to try to add a and b to combine the limits. But this

3628 ** does not work if either limit is negative.

3629 */

3630 if( pSub->pLimit ){

3631 pParent->pLimit = pSub->pLimit;

3632 pSub->pLimit = 0;

3633 }

3634 }

3635

3636 /* Finially, delete what is left of the subquery and return

3637 ** success.

3638 */

3639 sqlite3SelectDelete(db, pSub1);

3640

3641 #if SELECTTRACE_ENABLED

3642 if( sqlite3SelectTrace & 0x100 ){

3643 sqlite3DebugPrintf("After flattening:\n");

3644 sqlite3TreeViewSelect(0, p, 0);

3645 }

3646 #endif

3647

3648 return 1;

3649 }

3650 #endif /* !defined(SQLITE_OMIT_SUBQUERY) \|\| !defined(SQLITE_OMIT_VIEW) */

3651

3652 /*

3653 ** Based on the contents of the AggInfo structure indicated by the first

3654 ** argument, this function checks if the following are true:

3655 **

3656 ** * the query contains just a single aggregate function,

3657 ** * the aggregate function is either min() or max(), and

3658 ** * the argument to the aggregate function is a column value.

3659 **

3660 ** If all of the above are true, then WHERE_ORDERBY_MIN or WHERE_ORDERBY_MAX

3661 ** is returned as appropriate. Also, *ppMinMax is set to point to the

3662 ** list of arguments passed to the aggregate before returning.

3663 **

3664 ** Or, if the conditions above are not met, *ppMinMax is set to 0 and

3665 ** WHERE_ORDERBY_NORMAL is returned.

3666 */

3667 static u8 minMaxQuery(AggInfo pAggInfo, ExprList *ppMinMax){

3668 int eRet = WHERE_ORDERBY_NORMAL; /* Return value */

3669

3670 *ppMinMax = 0;

3671 if( pAggInfo->nFunc==1 ){

3672 Expr pExpr = pAggInfo->aFunc[0].pExpr; / Aggregate function */

3673 ExprList pEList = pExpr->x.pList; / Arguments to agg function */

3674

3675 assert( pExpr->op==TK_AGG_FUNCTION );

3676 if( pEList && pEList->nExpr==1 && pEList->a[0].pExpr->op==TK_AGG_COLUMN ){

3677 const char *zFunc = pExpr->u.zToken;

3678 if( sqlite3StrICmp(zFunc, "min")==0 ){

3679 eRet = WHERE_ORDERBY_MIN;

3680 *ppMinMax = pEList;

3681 }else if( sqlite3StrICmp(zFunc, "max")==0 ){

3682 eRet = WHERE_ORDERBY_MAX;

3683 *ppMinMax = pEList;

3684 }

3685 }

3686 }

3687

3688 assert( ppMinMax==0 \|\| (ppMinMax)->nExpr==1 );

3689 return eRet;

3690 }

3691

3692 /*

3693 ** The select statement passed as the first argument is an aggregate query.

3694 ** The second argument is the associated aggregate-info object. This

3695 ** function tests if the SELECT is of the form:

3696 **

3697 ** SELECT count(*) FROM <tbl>

3698 **

3699 ** where table is a database table, not a sub-select or view. If the query

3700 ** does match this pattern, then a pointer to the Table object representing

3701 ** <tbl> is returned. Otherwise, 0 is returned.

3702 */

3703 static Table isSimpleCount(Select p, AggInfo *pAggInfo){

3704 Table *pTab;

3705 Expr *pExpr;

3706

3707 assert( !p->pGroupBy );

3708

3709 if( p->pWhere \|\| p->pEList->nExpr!=1

3710 \|\| p->pSrc->nSrc!=1 \|\| p->pSrc->a[0].pSelect

3711 ){

3712 return 0;

3713 }

3714 pTab = p->pSrc->a[0].pTab;

3715 pExpr = p->pEList->a[0].pExpr;

3716 assert( pTab && !pTab->pSelect && pExpr );

3717

3718 if( IsVirtual(pTab) ) return 0;

3719 if( pExpr->op!=TK_AGG_FUNCTION ) return 0;

3720 if( NEVER(pAggInfo->nFunc==0) ) return 0;

3721 if( (pAggInfo->aFunc[0].pFunc->funcFlags&SQLITE_FUNC_COUNT)==0 ) return 0;

3722 if( pExpr->flags&EP_Distinct ) return 0;

3723

3724 return pTab;

3725 }

3726

3727 /*

3728 ** If the source-list item passed as an argument was augmented with an

3729 ** INDEXED BY clause, then try to locate the specified index. If there

3730 ** was such a clause and the named index cannot be found, return

3731 ** SQLITE_ERROR and leave an error in pParse. Otherwise, populate

3732 ** pFrom->pIndex and return SQLITE_OK.

3733 */

3734 int sqlite3IndexedByLookup(Parse pParse, struct SrcList_item pFrom){

3735 if( pFrom->pTab && pFrom->zIndex ){

3736 Table *pTab = pFrom->pTab;

3737 char *zIndex = pFrom->zIndex;

3738 Index *pIdx;

3739 for(pIdx=pTab->pIndex;

3740 pIdx && sqlite3StrICmp(pIdx->zName, zIndex);

3741 pIdx=pIdx->pNext

3742 );

3743 if( !pIdx ){

3744 sqlite3ErrorMsg(pParse, "no such index: %s", zIndex, 0);

3745 pParse->checkSchema = 1;

3746 return SQLITE_ERROR;

3747 }

3748 pFrom->pIndex = pIdx;

3749 }

3750 return SQLITE_OK;

3751 }

3752 /*

3753 ** Detect compound SELECT statements that use an ORDER BY clause with

3754 ** an alternative collating sequence.

3755 **

3756 ** SELECT ... FROM t1 EXCEPT SELECT ... FROM t2 ORDER BY .. COLLATE ...

3757 **

3758 ** These are rewritten as a subquery:

3759 **

3760 ** SELECT * FROM (SELECT ... FROM t1 EXCEPT SELECT ... FROM t2)

3761 ** ORDER BY ... COLLATE ...

3762 **

3763 ** This transformation is necessary because the multiSelectOrderBy() routine

3764 ** above that generates the code for a compound SELECT with an ORDER BY clause

3765 ** uses a merge algorithm that requires the same collating sequence on the

3766 ** result columns as on the ORDER BY clause. See ticket

3767 ** http://www.sqlite.org/src/info/6709574d2a

3768 **

3769 ** This transformation is only needed for EXCEPT, INTERSECT, and UNION.

3770 ** The UNION ALL operator works fine with multiSelectOrderBy() even when

3771 ** there are COLLATE terms in the ORDER BY.

3772 */

3773 static int convertCompoundSelectToSubquery(Walker pWalker, Select p){

3774 int i;

3775 Select *pNew;

3776 Select *pX;

3777 sqlite3 *db;

3778 struct ExprList_item *a;

3779 SrcList *pNewSrc;

3780 Parse *pParse;

3781 Token dummy;

3782

3783 if( p->pPrior==0 ) return WRC_Continue;

3784 if( p->pOrderBy==0 ) return WRC_Continue;

3785 for(pX=p; pX && (pX->op==TK_ALL \|\| pX->op==TK_SELECT); pX=pX->pPrior){}

3786 if( pX==0 ) return WRC_Continue;

3787 a = p->pOrderBy->a;

3788 for(i=p->pOrderBy->nExpr-1; i>=0; i--){

3789 if( a[i].pExpr->flags & EP_Collate ) break;

3790 }

3791 if( i<0 ) return WRC_Continue;

3792

3793 /* If we reach this point, that means the transformation is required. */

3794

3795 pParse = pWalker->pParse;

3796 db = pParse->db;

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

3798 if( pNew==0 ) return WRC_Abort;

3799 memset(&dummy, 0, sizeof(dummy));

3800 pNewSrc = sqlite3SrcListAppendFromTerm(pParse,0,0,0,&dummy,pNew,0,0);

3801 if( pNewSrc==0 ) return WRC_Abort;

3802 pNew = p;

3803 p->pSrc = pNewSrc;

3804 p->pEList = sqlite3ExprListAppend(pParse, 0, sqlite3Expr(db, TK_ALL, 0));

3805 p->op = TK_SELECT;

3806 p->pWhere = 0;

3807 pNew->pGroupBy = 0;

3808 pNew->pHaving = 0;

3809 pNew->pOrderBy = 0;

3810 p->pPrior = 0;

3811 p->pNext = 0;

3812 p->selFlags &= ~SF_Compound;

3813 assert( pNew->pPrior!=0 );

3814 pNew->pPrior->pNext = pNew;

3815 pNew->pLimit = 0;

3816 pNew->pOffset = 0;

3817 return WRC_Continue;

3818 }

3819

3820 #ifndef SQLITE_OMIT_CTE

3821 /*

3822 ** Argument pWith (which may be NULL) points to a linked list of nested

3823 ** WITH contexts, from inner to outermost. If the table identified by

3824 ** FROM clause element pItem is really a common-table-expression (CTE)

3825 ** then return a pointer to the CTE definition for that table. Otherwise

3826 ** return NULL.

3827 **

3828 ** If a non-NULL value is returned, set *ppContext to point to the With

3829 ** object that the returned CTE belongs to.

3830 */

3831 static struct Cte *searchWith(

3832 With pWith, / Current outermost WITH clause */

3833 struct SrcList_item pItem, / FROM clause element to resolve */

3834 With *ppContext / OUT: WITH clause return value belongs to */

3835 ){

3836 const char *zName;

3837 if( pItem->zDatabase==0 && (zName = pItem->zName)!=0 ){

3838 With *p;

3839 for(p=pWith; p; p=p->pOuter){

3840 int i;

3841 for(i=0; i<p->nCte; i++){

3842 if( sqlite3StrICmp(zName, p->a[i].zName)==0 ){

3843 *ppContext = p;

3844 return &p->a[i];

3845 }

3846 }

3847 }

3848 }

3849 return 0;

3850 }

3851

3852 /* The code generator maintains a stack of active WITH clauses

3853 ** with the inner-most WITH clause being at the top of the stack.

3854 **

3855 ** This routine pushes the WITH clause passed as the second argument

3856 ** onto the top of the stack. If argument bFree is true, then this

3857 ** WITH clause will never be popped from the stack. In this case it

3858 ** should be freed along with the Parse object. In other cases, when

3859 ** bFree==0, the With object will be freed along with the SELECT

3860 ** statement with which it is associated.

3861 */

3862 void sqlite3WithPush(Parse pParse, With pWith, u8 bFree){

3863 assert( bFree==0 \|\| pParse->pWith==0 );

3864 if( pWith ){

3865 pWith->pOuter = pParse->pWith;

3866 pParse->pWith = pWith;

3867 pParse->bFreeWith = bFree;

3868 }

3869 }

3870

3871 /*

3872 ** This function checks if argument pFrom refers to a CTE declared by

3873 ** a WITH clause on the stack currently maintained by the parser. And,

3874 ** if currently processing a CTE expression, if it is a recursive

3875 ** reference to the current CTE.

3876 **

3877 ** If pFrom falls into either of the two categories above, pFrom->pTab

3878 ** and other fields are populated accordingly. The caller should check

3879 ** (pFrom->pTab!=0) to determine whether or not a successful match

3880 ** was found.

3881 **

3882 ** Whether or not a match is found, SQLITE_OK is returned if no error

3883 ** occurs. If an error does occur, an error message is stored in the

3884 ** parser and some error code other than SQLITE_OK returned.

3885 */

3886 static int withExpand(

3887 Walker *pWalker,

3888 struct SrcList_item *pFrom

3889 ){

3890 Parse *pParse = pWalker->pParse;

3891 sqlite3 *db = pParse->db;

3892 struct Cte pCte; / Matched CTE (or NULL if no match) */

3893 With pWith; / WITH clause that pCte belongs to */

3894

3895 assert( pFrom->pTab==0 );

3896

3897 pCte = searchWith(pParse->pWith, pFrom, &pWith);

3898 if( pCte ){

3899 Table *pTab;

3900 ExprList *pEList;

3901 Select *pSel;

3902 Select pLeft; / Left-most SELECT statement */

3903 int bMayRecursive; /* True if compound joined by UNION [ALL] */

3904 With pSavedWith; / Initial value of pParse->pWith */

3905

3906 /* If pCte->zErr is non-NULL at this point, then this is an illegal

3907 ** recursive reference to CTE pCte. Leave an error in pParse and return

3908 ** early. If pCte->zErr is NULL, then this is not a recursive reference.

3909 ** In this case, proceed. */

3910 if( pCte->zErr ){

3911 sqlite3ErrorMsg(pParse, pCte->zErr, pCte->zName);

3912 return SQLITE_ERROR;

3913 }

3914

3915 assert( pFrom->pTab==0 );

3916 pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table));

3917 if( pTab==0 ) return WRC_Abort;

3918 pTab->nRef = 1;

3919 pTab->zName = sqlite3DbStrDup(db, pCte->zName);

3920 pTab->iPKey = -1;

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

3922 pTab->tabFlags \|= TF_Ephemeral;

3923 pFrom->pSelect = sqlite3SelectDup(db, pCte->pSelect, 0);

3924 if( db->mallocFailed ) return SQLITE_NOMEM;

3925 assert( pFrom->pSelect );

3926

3927 /* Check if this is a recursive CTE. */

3928 pSel = pFrom->pSelect;

3929 bMayRecursive = ( pSel->op==TK_ALL \|\| pSel->op==TK_UNION );

3930 if( bMayRecursive ){

3931 int i;

3932 SrcList *pSrc = pFrom->pSelect->pSrc;

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

3934 struct SrcList_item *pItem = &pSrc->a[i];

3935 if( pItem->zDatabase==0

3936 && pItem->zName!=0

3937 && 0==sqlite3StrICmp(pItem->zName, pCte->zName)

3938 ){

3939 pItem->pTab = pTab;

3940 pItem->isRecursive = 1;

3941 pTab->nRef++;

3942 pSel->selFlags \|= SF_Recursive;

3943 }

3944 }

3945 }

3946

3947 /* Only one recursive reference is permitted. */

3948 if( pTab->nRef>2 ){

3949 sqlite3ErrorMsg(

3950 pParse, "multiple references to recursive table: %s", pCte->zName

3951 );

3952 return SQLITE_ERROR;

3953 }

3954 assert( pTab->nRef==1 \|\| ((pSel->selFlags&SF_Recursive) && pTab->nRef==2 ));

3955

3956 pCte->zErr = "circular reference: %s";

3957 pSavedWith = pParse->pWith;

3958 pParse->pWith = pWith;

3959 sqlite3WalkSelect(pWalker, bMayRecursive ? pSel->pPrior : pSel);

3960

3961 for(pLeft=pSel; pLeft->pPrior; pLeft=pLeft->pPrior);

3962 pEList = pLeft->pEList;

3963 if( pCte->pCols ){

3964 if( pEList->nExpr!=pCte->pCols->nExpr ){

3965 sqlite3ErrorMsg(pParse, "table %s has %d values for %d columns",

3966 pCte->zName, pEList->nExpr, pCte->pCols->nExpr

3967 );

3968 pParse->pWith = pSavedWith;

3969 return SQLITE_ERROR;

3970 }

3971 pEList = pCte->pCols;

3972 }

3973

3974 selectColumnsFromExprList(pParse, pEList, &pTab->nCol, &pTab->aCol);

3975 if( bMayRecursive ){

3976 if( pSel->selFlags & SF_Recursive ){

3977 pCte->zErr = "multiple recursive references: %s";

3978 }else{

3979 pCte->zErr = "recursive reference in a subquery: %s";

3980 }

3981 sqlite3WalkSelect(pWalker, pSel);

3982 }

3983 pCte->zErr = 0;

3984 pParse->pWith = pSavedWith;

3985 }

3986

3987 return SQLITE_OK;

3988 }

3989 #endif

3990

3991 #ifndef SQLITE_OMIT_CTE

3992 /*

3993 ** If the SELECT passed as the second argument has an associated WITH

3994 ** clause, pop it from the stack stored as part of the Parse object.

3995 **

3996 ** This function is used as the xSelectCallback2() callback by

3997 ** sqlite3SelectExpand() when walking a SELECT tree to resolve table

3998 ** names and other FROM clause elements.

3999 */

4000 static void selectPopWith(Walker pWalker, Select p){

4001 Parse *pParse = pWalker->pParse;

4002 With *pWith = findRightmost(p)->pWith;

4003 if( pWith!=0 ){

4004 assert( pParse->pWith==pWith );

4005 pParse->pWith = pWith->pOuter;

4006 }

4007 }

4008 #else

4009 #define selectPopWith 0

4010 #endif

4011

4012 /*

4013 ** This routine is a Walker callback for "expanding" a SELECT statement.

4014 ** "Expanding" means to do the following:

4015 **

4016 ** (1) Make sure VDBE cursor numbers have been assigned to every

4017 ** element of the FROM clause.

4018 **

4019 ** (2) Fill in the pTabList->a[].pTab fields in the SrcList that

4020 ** defines FROM clause. When views appear in the FROM clause,

4021 ** fill pTabList->a[].pSelect with a copy of the SELECT statement

4022 ** that implements the view. A copy is made of the view's SELECT

4023 ** statement so that we can freely modify or delete that statement

4024 ** without worrying about messing up the persistent representation

4025 ** of the view.

4026 **

4027 ** (3) Add terms to the WHERE clause to accommodate the NATURAL keyword

4028 ** on joins and the ON and USING clause of joins.

4029 **

4030 ** (4) Scan the list of columns in the result set (pEList) looking

4031 ** for instances of the "" operator or the TABLE. operator.

4032 ** If found, expand each "*" to be every column in every table

4033 ** and TABLE.* to be every column in TABLE.

4034 **

4035 */

4036 static int selectExpander(Walker pWalker, Select p){

4037 Parse *pParse = pWalker->pParse;

4038 int i, j, k;

4039 SrcList *pTabList;

4040 ExprList *pEList;

4041 struct SrcList_item *pFrom;

4042 sqlite3 *db = pParse->db;

4043 Expr pE, pRight, *pExpr;

4044 u16 selFlags = p->selFlags;

4045

4046 p->selFlags \|= SF_Expanded;

4047 if( db->mallocFailed ){

4048 return WRC_Abort;

4049 }

4050 if( NEVER(p->pSrc==0) \|\| (selFlags & SF_Expanded)!=0 ){

4051 return WRC_Prune;

4052 }

4053 pTabList = p->pSrc;

4054 pEList = p->pEList;

4055 sqlite3WithPush(pParse, findRightmost(p)->pWith, 0);

4056

4057 /* Make sure cursor numbers have been assigned to all entries in

4058 ** the FROM clause of the SELECT statement.

4059 */

4060 sqlite3SrcListAssignCursors(pParse, pTabList);

4061

4062 /* Look up every table named in the FROM clause of the select. If

4063 ** an entry of the FROM clause is a subquery instead of a table or view,

4064 ** then create a transient table structure to describe the subquery.

4065 */

4066 for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){

4067 Table *pTab;

4068 assert( pFrom->isRecursive==0 \|\| pFrom->pTab );

4069 if( pFrom->isRecursive ) continue;

4070 if( pFrom->pTab!=0 ){

4071 /* This statement has already been prepared. There is no need

4072 ** to go further. */

4073 assert( i==0 );

4074 #ifndef SQLITE_OMIT_CTE

4075 selectPopWith(pWalker, p);

4076 #endif

4077 return WRC_Prune;

4078 }

4079 #ifndef SQLITE_OMIT_CTE

4080 if( withExpand(pWalker, pFrom) ) return WRC_Abort;

4081 if( pFrom->pTab ) {} else

4082 #endif

4083 if( pFrom->zName==0 ){

4084 #ifndef SQLITE_OMIT_SUBQUERY

4085 Select *pSel = pFrom->pSelect;

4086 /* A sub-query in the FROM clause of a SELECT */

4087 assert( pSel!=0 );

4088 assert( pFrom->pTab==0 );

4089 sqlite3WalkSelect(pWalker, pSel);

4090 pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table));

4091 if( pTab==0 ) return WRC_Abort;

4092 pTab->nRef = 1;

4093 pTab->zName = sqlite3MPrintf(db, "sqlite_sq_%p", (void*)pTab);

4094 while( pSel->pPrior ){ pSel = pSel->pPrior; }

4095 selectColumnsFromExprList(pParse, pSel->pEList, &pTab->nCol, &pTab->aCol);

4096 pTab->iPKey = -1;

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

4098 pTab->tabFlags \|= TF_Ephemeral;

4099 #endif

4100 }else{

4101 /* An ordinary table or view name in the FROM clause */

4102 assert( pFrom->pTab==0 );

4103 pFrom->pTab = pTab = sqlite3LocateTableItem(pParse, 0, pFrom);

4104 if( pTab==0 ) return WRC_Abort;

4105 if( pTab->nRef==0xffff ){

4106 sqlite3ErrorMsg(pParse, "too many references to \"%s\": max 65535",

4107 pTab->zName);

4108 pFrom->pTab = 0;

4109 return WRC_Abort;

4110 }

4111 pTab->nRef++;

4112 #if !defined(SQLITE_OMIT_VIEW) \|\| !defined (SQLITE_OMIT_VIRTUALTABLE)

4113 if( pTab->pSelect \|\| IsVirtual(pTab) ){

4114 /* We reach here if the named table is a really a view */

4115 if( sqlite3ViewGetColumnNames(pParse, pTab) ) return WRC_Abort;

4116 assert( pFrom->pSelect==0 );

4117 pFrom->pSelect = sqlite3SelectDup(db, pTab->pSelect, 0);

4118 sqlite3SelectSetName(pFrom->pSelect, pTab->zName);

4119 sqlite3WalkSelect(pWalker, pFrom->pSelect);

4120 }

4121 #endif

4122 }

4123

4124 /* Locate the index named by the INDEXED BY clause, if any. */

4125 if( sqlite3IndexedByLookup(pParse, pFrom) ){

4126 return WRC_Abort;

4127 }

4128 }

4129

4130 /* Process NATURAL keywords, and ON and USING clauses of joins.

4131 */

4132 if( db->mallocFailed \|\| sqliteProcessJoin(pParse, p) ){

4133 return WRC_Abort;

4134 }

4135

4136 /* For every "*" that occurs in the column list, insert the names of

4137 ** all columns in all tables. And for every TABLE.* insert the names

4138 ** of all columns in TABLE. The parser inserted a special expression

4139 ** with the TK_ALL operator for each "*" that it found in the column list.

4140 ** The following code just has to locate the TK_ALL expressions and expand

4141 ** each one to the list of all columns in all tables.

4142 **

4143 ** The first loop just checks to see if there are any "*" operators

4144 ** that need expanding.

4145 */

4146 for(k=0; k<pEList->nExpr; k++){

4147 pE = pEList->a[k].pExpr;

4148 if( pE->op==TK_ALL ) break;

4149 assert( pE->op!=TK_DOT \|\| pE->pRight!=0 );

4150 assert( pE->op!=TK_DOT \|\| (pE->pLeft!=0 && pE->pLeft->op==TK_ID) );

4151 if( pE->op==TK_DOT && pE->pRight->op==TK_ALL ) break;

4152 }

4153 if( k<pEList->nExpr ){

4154 /*

4155 ** If we get here it means the result set contains one or more "*"

4156 ** operators that need to be expanded. Loop through each expression

4157 ** in the result set and expand them one by one.

4158 */

4159 struct ExprList_item *a = pEList->a;

4160 ExprList *pNew = 0;

4161 int flags = pParse->db->flags;

4162 int longNames = (flags & SQLITE_FullColNames)!=0

4163 && (flags & SQLITE_ShortColNames)==0;

4164

4165 /* When processing FROM-clause subqueries, it is always the case

4166 ** that full_column_names=OFF and short_column_names=ON. The

4167 ** sqlite3ResultSetOfSelect() routine makes it so. */

4168 assert( (p->selFlags & SF_NestedFrom)==0

4169 \|\| ((flags & SQLITE_FullColNames)==0 &&

4170 (flags & SQLITE_ShortColNames)!=0) );

4171

4172 for(k=0; k<pEList->nExpr; k++){

4173 pE = a[k].pExpr;

4174 pRight = pE->pRight;

4175 assert( pE->op!=TK_DOT \|\| pRight!=0 );

4176 if( pE->op!=TK_ALL && (pE->op!=TK_DOT \|\| pRight->op!=TK_ALL) ){

4177 /* This particular expression does not need to be expanded.

4178 */

4179 pNew = sqlite3ExprListAppend(pParse, pNew, a[k].pExpr);

4180 if( pNew ){

4181 pNew->a[pNew->nExpr-1].zName = a[k].zName;

4182 pNew->a[pNew->nExpr-1].zSpan = a[k].zSpan;

4183 a[k].zName = 0;

4184 a[k].zSpan = 0;

4185 }

4186 a[k].pExpr = 0;

4187 }else{

4188 /* This expression is a "" or a "TABLE." and needs to be

4189 ** expanded. */

4190 int tableSeen = 0; /* Set to 1 when TABLE matches */

4191 char zTName = 0; / text of name of TABLE */

4192 if( pE->op==TK_DOT ){

4193 assert( pE->pLeft!=0 );

4194 assert( !ExprHasProperty(pE->pLeft, EP_IntValue) );

4195 zTName = pE->pLeft->u.zToken;

4196 }

4197 for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){

4198 Table *pTab = pFrom->pTab;

4199 Select *pSub = pFrom->pSelect;

4200 char *zTabName = pFrom->zAlias;

4201 const char *zSchemaName = 0;

4202 int iDb;

4203 if( zTabName==0 ){

4204 zTabName = pTab->zName;

4205 }

4206 if( db->mallocFailed ) break;

4207 if( pSub==0 \|\| (pSub->selFlags & SF_NestedFrom)==0 ){

4208 pSub = 0;

4209 if( zTName && sqlite3StrICmp(zTName, zTabName)!=0 ){

4210 continue;

4211 }

4212 iDb = sqlite3SchemaToIndex(db, pTab->pSchema);

4213 zSchemaName = iDb>=0 ? db->aDb[iDb].zName : "*";

4214 }

4215 for(j=0; j<pTab->nCol; j++){

4216 char *zName = pTab->aCol[j].zName;

4217 char zColname; / The computed column name */

4218 char zToFree; / Malloced string that needs to be freed */

4219 Token sColname; /* Computed column name as a token */

4220

4221 assert( zName );

4222 if( zTName && pSub

4223 && sqlite3MatchSpanName(pSub->pEList->a[j].zSpan, 0, zTName, 0)==0

4224 ){

4225 continue;

4226 }

4227

4228 /* If a column is marked as 'hidden' (currently only possible

4229 ** for virtual tables), do not include it in the expanded

4230 ** result-set list.

4231 */

4232 if( IsHiddenColumn(&pTab->aCol[j]) ){

4233 assert(IsVirtual(pTab));

4234 continue;

4235 }

4236 tableSeen = 1;

4237

4238 if( i>0 && zTName==0 ){

4239 if( (pFrom->jointype & JT_NATURAL)!=0

4240 && tableAndColumnIndex(pTabList, i, zName, 0, 0)

4241 ){

4242 /* In a NATURAL join, omit the join columns from the

4243 ** table to the right of the join */

4244 continue;

4245 }

4246 if( sqlite3IdListIndex(pFrom->pUsing, zName)>=0 ){

4247 /* In a join with a USING clause, omit columns in the

4248 ** using clause from the table on the right. */

4249 continue;

4250 }

4251 }

4252 pRight = sqlite3Expr(db, TK_ID, zName);

4253 zColname = zName;

4254 zToFree = 0;

4255 if( longNames \|\| pTabList->nSrc>1 ){

4256 Expr *pLeft;

4257 pLeft = sqlite3Expr(db, TK_ID, zTabName);

4258 pExpr = sqlite3PExpr(pParse, TK_DOT, pLeft, pRight, 0);

4259 if( zSchemaName ){

4260 pLeft = sqlite3Expr(db, TK_ID, zSchemaName);

4261 pExpr = sqlite3PExpr(pParse, TK_DOT, pLeft, pExpr, 0);

4262 }

4263 if( longNames ){

4264 zColname = sqlite3MPrintf(db, "%s.%s", zTabName, zName);

4265 zToFree = zColname;

4266 }

4267 }else{

4268 pExpr = pRight;

4269 }

4270 pNew = sqlite3ExprListAppend(pParse, pNew, pExpr);

4271 sColname.z = zColname;

4272 sColname.n = sqlite3Strlen30(zColname);

4273 sqlite3ExprListSetName(pParse, pNew, &sColname, 0);

4274 if( pNew && (p->selFlags & SF_NestedFrom)!=0 ){

4275 struct ExprList_item *pX = &pNew->a[pNew->nExpr-1];

4276 if( pSub ){

4277 pX->zSpan = sqlite3DbStrDup(db, pSub->pEList->a[j].zSpan);

4278 testcase( pX->zSpan==0 );

4279 }else{

4280 pX->zSpan = sqlite3MPrintf(db, "%s.%s.%s",

4281 zSchemaName, zTabName, zColname);

4282 testcase( pX->zSpan==0 );

4283 }

4284 pX->bSpanIsTab = 1;

4285 }

4286 sqlite3DbFree(db, zToFree);

4287 }

4288 }

4289 if( !tableSeen ){

4290 if( zTName ){

4291 sqlite3ErrorMsg(pParse, "no such table: %s", zTName);

4292 }else{

4293 sqlite3ErrorMsg(pParse, "no tables specified");

4294 }

4295 }

4296 }

4297 }

4298 sqlite3ExprListDelete(db, pEList);

4299 p->pEList = pNew;

4300 }

4301 #if SQLITE_MAX_COLUMN

4302 if( p->pEList && p->pEList->nExpr>db->aLimit[SQLITE_LIMIT_COLUMN] ){

4303 sqlite3ErrorMsg(pParse, "too many columns in result set");

4304 }

4305 #endif

4306 return WRC_Continue;

4307 }

4308

4309 /*

4310 ** No-op routine for the parse-tree walker.

4311 **

4312 ** When this routine is the Walker.xExprCallback then expression trees

4313 ** are walked without any actions being taken at each node. Presumably,

4314 ** when this routine is used for Walker.xExprCallback then

4315 ** Walker.xSelectCallback is set to do something useful for every

4316 ** subquery in the parser tree.

4317 */

4318 static int exprWalkNoop(Walker NotUsed, Expr NotUsed2){

4319 UNUSED_PARAMETER2(NotUsed, NotUsed2);

4320 return WRC_Continue;

4321 }

4322

4323 /*

4324 ** This routine "expands" a SELECT statement and all of its subqueries.

4325 ** For additional information on what it means to "expand" a SELECT

4326 ** statement, see the comment on the selectExpand worker callback above.

4327 **

4328 ** Expanding a SELECT statement is the first step in processing a

4329 ** SELECT statement. The SELECT statement must be expanded before

4330 ** name resolution is performed.

4331 **

4332 ** If anything goes wrong, an error message is written into pParse.

4333 ** The calling function can detect the problem by looking at pParse->nErr

4334 ** and/or pParse->db->mallocFailed.

4335 */

4336 static void sqlite3SelectExpand(Parse pParse, Select pSelect){

4337 Walker w;

4338 memset(&w, 0, sizeof(w));

4339 w.xExprCallback = exprWalkNoop;

4340 w.pParse = pParse;

4341 if( pParse->hasCompound ){

4342 w.xSelectCallback = convertCompoundSelectToSubquery;

4343 sqlite3WalkSelect(&w, pSelect);

4344 }

4345 w.xSelectCallback = selectExpander;

4346 w.xSelectCallback2 = selectPopWith;

4347 sqlite3WalkSelect(&w, pSelect);

4348 }

4349

4350

4351 #ifndef SQLITE_OMIT_SUBQUERY

4352 /*

4353 ** This is a Walker.xSelectCallback callback for the sqlite3SelectTypeInfo()

4354 ** interface.

4355 **

4356 ** For each FROM-clause subquery, add Column.zType and Column.zColl

4357 ** information to the Table structure that represents the result set

4358 ** of that subquery.

4359 **

4360 ** The Table structure that represents the result set was constructed

4361 ** by selectExpander() but the type and collation information was omitted

4362 ** at that point because identifiers had not yet been resolved. This

4363 ** routine is called after identifier resolution.

4364 */

4365 static void selectAddSubqueryTypeInfo(Walker pWalker, Select p){

4366 Parse *pParse;

4367 int i;

4368 SrcList *pTabList;

4369 struct SrcList_item *pFrom;

4370

4371 assert( p->selFlags & SF_Resolved );

4372 if( (p->selFlags & SF_HasTypeInfo)==0 ){

4373 p->selFlags \|= SF_HasTypeInfo;

4374 pParse = pWalker->pParse;

4375 pTabList = p->pSrc;

4376 for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){

4377 Table *pTab = pFrom->pTab;

4378 if( ALWAYS(pTab!=0) && (pTab->tabFlags & TF_Ephemeral)!=0 ){

4379 /* A sub-query in the FROM clause of a SELECT */

4380 Select *pSel = pFrom->pSelect;

4381 if( pSel ){

4382 while( pSel->pPrior ) pSel = pSel->pPrior;

4383 selectAddColumnTypeAndCollation(pParse, pTab, pSel);

4384 }

4385 }

4386 }

4387 }

4388 }

4389 #endif

4390

4391

4392 /*

4393 ** This routine adds datatype and collating sequence information to

4394 ** the Table structures of all FROM-clause subqueries in a

4395 ** SELECT statement.

4396 **

4397 ** Use this routine after name resolution.

4398 */

4399 static void sqlite3SelectAddTypeInfo(Parse pParse, Select pSelect){

4400 #ifndef SQLITE_OMIT_SUBQUERY

4401 Walker w;

4402 memset(&w, 0, sizeof(w));

4403 w.xSelectCallback2 = selectAddSubqueryTypeInfo;

4404 w.xExprCallback = exprWalkNoop;

4405 w.pParse = pParse;

4406 sqlite3WalkSelect(&w, pSelect);

4407 #endif

4408 }

4409

4410

4411 /*

4412 ** This routine sets up a SELECT statement for processing. The

4413 ** following is accomplished:

4414 **

4415 ** * VDBE Cursor numbers are assigned to all FROM-clause terms.

4416 ** * Ephemeral Table objects are created for all FROM-clause subqueries.

4417 ** * ON and USING clauses are shifted into WHERE statements

4418 ** * Wildcards "" and "TABLE." in result sets are expanded.

4419 ** * Identifiers in expression are matched to tables.

4420 **

4421 ** This routine acts recursively on all subqueries within the SELECT.

4422 */

4423 void sqlite3SelectPrep(

4424 Parse pParse, / The parser context */

4425 Select p, / The SELECT statement being coded. */

4426 NameContext pOuterNC / Name context for container */

4427 ){

4428 sqlite3 *db;

4429 if( NEVER(p==0) ) return;

4430 db = pParse->db;

4431 if( db->mallocFailed ) return;

4432 if( p->selFlags & SF_HasTypeInfo ) return;

4433 sqlite3SelectExpand(pParse, p);

4434 if( pParse->nErr \|\| db->mallocFailed ) return;

4435 sqlite3ResolveSelectNames(pParse, p, pOuterNC);

4436 if( pParse->nErr \|\| db->mallocFailed ) return;

4437 sqlite3SelectAddTypeInfo(pParse, p);

4438 }

4439

4440 /*

4441 ** Reset the aggregate accumulator.

4442 **

4443 ** The aggregate accumulator is a set of memory cells that hold

4444 ** intermediate results while calculating an aggregate. This

4445 ** routine generates code that stores NULLs in all of those memory

4446 ** cells.

4447 */

4448 static void resetAccumulator(Parse pParse, AggInfo pAggInfo){

4449 Vdbe *v = pParse->pVdbe;

4450 int i;

4451 struct AggInfo_func *pFunc;

4452 int nReg = pAggInfo->nFunc + pAggInfo->nColumn;

4453 if( nReg==0 ) return;

4454 #ifdef SQLITE_DEBUG

4455 /* Verify that all AggInfo registers are within the range specified by

4456 ** AggInfo.mnReg..AggInfo.mxReg */

4457 assert( nReg==pAggInfo->mxReg-pAggInfo->mnReg+1 );

4458 for(i=0; i<pAggInfo->nColumn; i++){

4459 assert( pAggInfo->aCol[i].iMem>=pAggInfo->mnReg

4460 && pAggInfo->aCol[i].iMem<=pAggInfo->mxReg );

4461 }

4462 for(i=0; i<pAggInfo->nFunc; i++){

4463 assert( pAggInfo->aFunc[i].iMem>=pAggInfo->mnReg

4464 && pAggInfo->aFunc[i].iMem<=pAggInfo->mxReg );

4465 }

4466 #endif

4467 sqlite3VdbeAddOp3(v, OP_Null, 0, pAggInfo->mnReg, pAggInfo->mxReg);

4468 for(pFunc=pAggInfo->aFunc, i=0; i<pAggInfo->nFunc; i++, pFunc++){

4469 if( pFunc->iDistinct>=0 ){

4470 Expr *pE = pFunc->pExpr;

4471 assert( !ExprHasProperty(pE, EP_xIsSelect) );

4472 if( pE->x.pList==0 \|\| pE->x.pList->nExpr!=1 ){

4473 sqlite3ErrorMsg(pParse, "DISTINCT aggregates must have exactly one "

4474 "argument");

4475 pFunc->iDistinct = -1;

4476 }else{

4477 KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pE->x.pList, 0, 0);

4478 sqlite3VdbeAddOp4(v, OP_OpenEphemeral, pFunc->iDistinct, 0, 0,

4479 (char*)pKeyInfo, P4_KEYINFO);

4480 }

4481 }

4482 }

4483 }

4484

4485 /*

4486 ** Invoke the OP_AggFinalize opcode for every aggregate function

4487 ** in the AggInfo structure.

4488 */

4489 static void finalizeAggFunctions(Parse pParse, AggInfo pAggInfo){

4490 Vdbe *v = pParse->pVdbe;

4491 int i;

4492 struct AggInfo_func *pF;

4493 for(i=0, pF=pAggInfo->aFunc; i<pAggInfo->nFunc; i++, pF++){

4494 ExprList *pList = pF->pExpr->x.pList;

4495 assert( !ExprHasProperty(pF->pExpr, EP_xIsSelect) );

4496 sqlite3VdbeAddOp4(v, OP_AggFinal, pF->iMem, pList ? pList->nExpr : 0, 0,

4497 (void*)pF->pFunc, P4_FUNCDEF);

4498 }

4499 }

4500

4501 /*

4502 ** Update the accumulator memory cells for an aggregate based on

4503 ** the current cursor position.

4504 */

4505 static void updateAccumulator(Parse pParse, AggInfo pAggInfo){

4506 Vdbe *v = pParse->pVdbe;

4507 int i;

4508 int regHit = 0;

4509 int addrHitTest = 0;

4510 struct AggInfo_func *pF;

4511 struct AggInfo_col *pC;

4512

4513 pAggInfo->directMode = 1;

4514 for(i=0, pF=pAggInfo->aFunc; i<pAggInfo->nFunc; i++, pF++){

4515 int nArg;

4516 int addrNext = 0;

4517 int regAgg;

4518 ExprList *pList = pF->pExpr->x.pList;

4519 assert( !ExprHasProperty(pF->pExpr, EP_xIsSelect) );

4520 if( pList ){

4521 nArg = pList->nExpr;

4522 regAgg = sqlite3GetTempRange(pParse, nArg);

4523 sqlite3ExprCodeExprList(pParse, pList, regAgg, SQLITE_ECEL_DUP);

4524 }else{

4525 nArg = 0;

4526 regAgg = 0;

4527 }

4528 if( pF->iDistinct>=0 ){

4529 addrNext = sqlite3VdbeMakeLabel(v);

4530 assert( nArg==1 );

4531 codeDistinct(pParse, pF->iDistinct, addrNext, 1, regAgg);

4532 }

4533 if( pF->pFunc->funcFlags & SQLITE_FUNC_NEEDCOLL ){

4534 CollSeq *pColl = 0;

4535 struct ExprList_item *pItem;

4536 int j;

4537 assert( pList!=0 ); /* pList!=0 if pF->pFunc has NEEDCOLL */

4538 for(j=0, pItem=pList->a; !pColl && j<nArg; j++, pItem++){

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

4540 }

4541 if( !pColl ){

4542 pColl = pParse->db->pDfltColl;

4543 }

4544 if( regHit==0 && pAggInfo->nAccumulator ) regHit = ++pParse->nMem;

4545 sqlite3VdbeAddOp4(v, OP_CollSeq, regHit, 0, 0, (char *)pColl, P4_COLLSEQ);

4546 }

4547 sqlite3VdbeAddOp4(v, OP_AggStep, 0, regAgg, pF->iMem,

4548 (void*)pF->pFunc, P4_FUNCDEF);

4549 sqlite3VdbeChangeP5(v, (u8)nArg);

4550 sqlite3ExprCacheAffinityChange(pParse, regAgg, nArg);

4551 sqlite3ReleaseTempRange(pParse, regAgg, nArg);

4552 if( addrNext ){

4553 sqlite3VdbeResolveLabel(v, addrNext);

4554 sqlite3ExprCacheClear(pParse);

4555 }

4556 }

4557

4558 /* Before populating the accumulator registers, clear the column cache.

4559 ** Otherwise, if any of the required column values are already present

4560 ** in registers, sqlite3ExprCode() may use OP_SCopy to copy the value

4561 ** to pC->iMem. But by the time the value is used, the original register

4562 ** may have been used, invalidating the underlying buffer holding the

4563 ** text or blob value. See ticket [883034dcb5].

4564 **

4565 ** Another solution would be to change the OP_SCopy used to copy cached

4566 ** values to an OP_Copy.

4567 */

4568 if( regHit ){

4569 addrHitTest = sqlite3VdbeAddOp1(v, OP_If, regHit); VdbeCoverage(v);

4570 }

4571 sqlite3ExprCacheClear(pParse);

4572 for(i=0, pC=pAggInfo->aCol; i<pAggInfo->nAccumulator; i++, pC++){

4573 sqlite3ExprCode(pParse, pC->pExpr, pC->iMem);

4574 }

4575 pAggInfo->directMode = 0;

4576 sqlite3ExprCacheClear(pParse);

4577 if( addrHitTest ){

4578 sqlite3VdbeJumpHere(v, addrHitTest);

4579 }

4580 }

4581

4582 /*

4583 ** Add a single OP_Explain instruction to the VDBE to explain a simple

4584 ** count() query ("SELECT count() FROM pTab").

4585 */

4586 #ifndef SQLITE_OMIT_EXPLAIN

4587 static void explainSimpleCount(

4588 Parse pParse, / Parse context */

4589 Table pTab, / Table being queried */

4590 Index pIdx / Index used to optimize scan, or NULL */

4591 ){

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

4593 int bCover = (pIdx!=0 && (HasRowid(pTab) \|\| !IsPrimaryKeyIndex(pIdx)));

4594 char *zEqp = sqlite3MPrintf(pParse->db, "SCAN TABLE %s%s%s",

4595 pTab->zName,

4596 bCover ? " USING COVERING INDEX " : "",

4597 bCover ? pIdx->zName : ""

4598 );

4599 sqlite3VdbeAddOp4(

4600 pParse->pVdbe, OP_Explain, pParse->iSelectId, 0, 0, zEqp, P4_DYNAMIC

4601 );

4602 }

4603 }

4604 #else

4605 # define explainSimpleCount(a,b,c)

4606 #endif

4607

4608 /*

4609 ** Generate code for the SELECT statement given in the p argument.

4610 **

4611 ** The results are returned according to the SelectDest structure.

4612 ** See comments in sqliteInt.h for further information.

4613 **

4614 ** This routine returns the number of errors. If any errors are

4615 ** encountered, then an appropriate error message is left in

4616 ** pParse->zErrMsg.

4617 **

4618 ** This routine does NOT free the Select structure passed in. The

4619 ** calling function needs to do that.

4620 */

4621 int sqlite3Select(

4622 Parse pParse, / The parser context */

4623 Select p, / The SELECT statement being coded. */

4624 SelectDest pDest / What to do with the query results */

4625 ){

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

4627 WhereInfo pWInfo; / Return from sqlite3WhereBegin() */

4628 Vdbe v; / The virtual machine under construction */

4629 int isAgg; /* True for select lists like "count()" /

4630 ExprList pEList; / List of columns to extract. */

4631 SrcList pTabList; / List of tables to select from */

4632 Expr pWhere; / The WHERE clause. May be NULL */

4633 ExprList pGroupBy; / The GROUP BY clause. May be NULL */

4634 Expr pHaving; / The HAVING clause. May be NULL */

4635 int rc = 1; /* Value to return from this function */

4636 DistinctCtx sDistinct; /* Info on how to code the DISTINCT keyword */

4637 SortCtx sSort; /* Info on how to code the ORDER BY clause */

4638 AggInfo sAggInfo; /* Information used by aggregate queries */

4639 int iEnd; /* Address of the end of the query */

4640 sqlite3 db; / The database connection */

4641

4642 #ifndef SQLITE_OMIT_EXPLAIN

4643 int iRestoreSelectId = pParse->iSelectId;

4644 pParse->iSelectId = pParse->iNextSelectId++;

4645 #endif

4646

4647 db = pParse->db;

4648 if( p==0 \|\| db->mallocFailed \|\| pParse->nErr ){

4649 return 1;

4650 }

4651 if( sqlite3AuthCheck(pParse, SQLITE_SELECT, 0, 0, 0) ) return 1;

4652 memset(&sAggInfo, 0, sizeof(sAggInfo));

4653 #if SELECTTRACE_ENABLED

4654 pParse->nSelectIndent++;

4655 SELECTTRACE(1,pParse,p, ("begin processing:\n"));

4656 if( sqlite3SelectTrace & 0x100 ){

4657 sqlite3TreeViewSelect(0, p, 0);

4658 }

4659 #endif

4660

4661 assert( p->pOrderBy==0 \|\| pDest->eDest!=SRT_DistFifo );

4662 assert( p->pOrderBy==0 \|\| pDest->eDest!=SRT_Fifo );

4663 assert( p->pOrderBy==0 \|\| pDest->eDest!=SRT_DistQueue );

4664 assert( p->pOrderBy==0 \|\| pDest->eDest!=SRT_Queue );

4665 if( IgnorableOrderby(pDest) ){

4666 assert(pDest->eDest==SRT_Exists \|\| pDest->eDest==SRT_Union \|\|

4667 pDest->eDest==SRT_Except \|\| pDest->eDest==SRT_Discard \|\|

4668 pDest->eDest==SRT_Queue \|\| pDest->eDest==SRT_DistFifo \|\|

4669 pDest->eDest==SRT_DistQueue \|\| pDest->eDest==SRT_Fifo);

4670 /* If ORDER BY makes no difference in the output then neither does

4671 ** DISTINCT so it can be removed too. */

4672 sqlite3ExprListDelete(db, p->pOrderBy);

4673 p->pOrderBy = 0;

4674 p->selFlags &= ~SF_Distinct;

4675 }

4676 sqlite3SelectPrep(pParse, p, 0);

4677 memset(&sSort, 0, sizeof(sSort));

4678 sSort.pOrderBy = p->pOrderBy;

4679 pTabList = p->pSrc;

4680 pEList = p->pEList;

4681 if( pParse->nErr \|\| db->mallocFailed ){

4682 goto select_end;

4683 }

4684 isAgg = (p->selFlags & SF_Aggregate)!=0;

4685 assert( pEList!=0 );

4686

4687 /* Begin generating code.

4688 */

4689 v = sqlite3GetVdbe(pParse);

4690 if( v==0 ) goto select_end;

4691

4692 /* If writing to memory or generating a set

4693 ** only a single column may be output.

4694 */

4695 #ifndef SQLITE_OMIT_SUBQUERY

4696 if( checkForMultiColumnSelectError(pParse, pDest, pEList->nExpr) ){

4697 goto select_end;

4698 }

4699 #endif

4700

4701 /* Generate code for all sub-queries in the FROM clause

4702 */

4703 #if !defined(SQLITE_OMIT_SUBQUERY) \|\| !defined(SQLITE_OMIT_VIEW)

4704 for(i=0; !p->pPrior && i<pTabList->nSrc; i++){

4705 struct SrcList_item *pItem = &pTabList->a[i];

4706 SelectDest dest;

4707 Select *pSub = pItem->pSelect;

4708 int isAggSub;

4709

4710 if( pSub==0 ) continue;

4711

4712 /* Sometimes the code for a subquery will be generated more than

4713 ** once, if the subquery is part of the WHERE clause in a LEFT JOIN,

4714 ** for example. In that case, do not regenerate the code to manifest

4715 ** a view or the co-routine to implement a view. The first instance

4716 ** is sufficient, though the subroutine to manifest the view does need

4717 ** to be invoked again. */

4718 if( pItem->addrFillSub ){

4719 if( pItem->viaCoroutine==0 ){

4720 sqlite3VdbeAddOp2(v, OP_Gosub, pItem->regReturn, pItem->addrFillSub);

4721 }

4722 continue;

4723 }

4724

4725 /* Increment Parse.nHeight by the height of the largest expression

4726 ** tree referred to by this, the parent select. The child select

4727 ** may contain expression trees of at most

4728 ** (SQLITE_MAX_EXPR_DEPTH-Parse.nHeight) height. This is a bit

4729 ** more conservative than necessary, but much easier than enforcing

4730 ** an exact limit.

4731 */

4732 pParse->nHeight += sqlite3SelectExprHeight(p);

4733

4734 isAggSub = (pSub->selFlags & SF_Aggregate)!=0;

4735 if( flattenSubquery(pParse, p, i, isAgg, isAggSub) ){

4736 /* This subquery can be absorbed into its parent. */

4737 if( isAggSub ){

4738 isAgg = 1;

4739 p->selFlags \|= SF_Aggregate;

4740 }

4741 i = -1;

4742 }else if( pTabList->nSrc==1

4743 && OptimizationEnabled(db, SQLITE_SubqCoroutine)

4744 ){

4745 /* Implement a co-routine that will return a single row of the result

4746 ** set on each invocation.

4747 */

4748 int addrTop = sqlite3VdbeCurrentAddr(v)+1;

4749 pItem->regReturn = ++pParse->nMem;

4750 sqlite3VdbeAddOp3(v, OP_InitCoroutine, pItem->regReturn, 0, addrTop);

4751 VdbeComment((v, "%s", pItem->pTab->zName));

4752 pItem->addrFillSub = addrTop;

4753 sqlite3SelectDestInit(&dest, SRT_Coroutine, pItem->regReturn);

4754 explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId);

4755 sqlite3Select(pParse, pSub, &dest);

4756 pItem->pTab->nRowLogEst = sqlite3LogEst(pSub->nSelectRow);

4757 pItem->viaCoroutine = 1;

4758 pItem->regResult = dest.iSdst;

4759 sqlite3VdbeAddOp1(v, OP_EndCoroutine, pItem->regReturn);

4760 sqlite3VdbeJumpHere(v, addrTop-1);

4761 sqlite3ClearTempRegCache(pParse);

4762 }else{

4763 /* Generate a subroutine that will fill an ephemeral table with

4764 ** the content of this subquery. pItem->addrFillSub will point

4765 ** to the address of the generated subroutine. pItem->regReturn

4766 ** is a register allocated to hold the subroutine return address

4767 */

4768 int topAddr;

4769 int onceAddr = 0;

4770 int retAddr;

4771 assert( pItem->addrFillSub==0 );

4772 pItem->regReturn = ++pParse->nMem;

4773 topAddr = sqlite3VdbeAddOp2(v, OP_Integer, 0, pItem->regReturn);

4774 pItem->addrFillSub = topAddr+1;

4775 if( pItem->isCorrelated==0 ){

4776 /* If the subquery is not correlated and if we are not inside of

4777 ** a trigger, then we only need to compute the value of the subquery

4778 ** once. */

4779 onceAddr = sqlite3CodeOnce(pParse); VdbeCoverage(v);

4780 VdbeComment((v, "materialize \"%s\"", pItem->pTab->zName));

4781 }else{

4782 VdbeNoopComment((v, "materialize \"%s\"", pItem->pTab->zName));

4783 }

4784 sqlite3SelectDestInit(&dest, SRT_EphemTab, pItem->iCursor);

4785 explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId);

4786 sqlite3Select(pParse, pSub, &dest);

4787 pItem->pTab->nRowLogEst = sqlite3LogEst(pSub->nSelectRow);

4788 if( onceAddr ) sqlite3VdbeJumpHere(v, onceAddr);

4789 retAddr = sqlite3VdbeAddOp1(v, OP_Return, pItem->regReturn);

4790 VdbeComment((v, "end %s", pItem->pTab->zName));

4791 sqlite3VdbeChangeP1(v, topAddr, retAddr);

4792 sqlite3ClearTempRegCache(pParse);

4793 }

4794 if( /pParse->nErr \|\|/ db->mallocFailed ){

4795 goto select_end;

4796 }

4797 pParse->nHeight -= sqlite3SelectExprHeight(p);

4798 pTabList = p->pSrc;

4799 if( !IgnorableOrderby(pDest) ){

4800 sSort.pOrderBy = p->pOrderBy;

4801 }

4802 }

4803 pEList = p->pEList;

4804 #endif

4805 pWhere = p->pWhere;

4806 pGroupBy = p->pGroupBy;

4807 pHaving = p->pHaving;

4808 sDistinct.isTnct = (p->selFlags & SF_Distinct)!=0;

4809

4810 #ifndef SQLITE_OMIT_COMPOUND_SELECT

4811 /* If there is are a sequence of queries, do the earlier ones first.

4812 */

4813 if( p->pPrior ){

4814 rc = multiSelect(pParse, p, pDest);

4815 explainSetInteger(pParse->iSelectId, iRestoreSelectId);

4816 #if SELECTTRACE_ENABLED

4817 SELECTTRACE(1,pParse,p,("end compound-select processing\n"));

4818 pParse->nSelectIndent--;

4819 #endif

4820 return rc;

4821 }

4822 #endif

4823

4824 /* If the query is DISTINCT with an ORDER BY but is not an aggregate, and

4825 ** if the select-list is the same as the ORDER BY list, then this query

4826 ** can be rewritten as a GROUP BY. In other words, this:

4827 **

4828 ** SELECT DISTINCT xyz FROM ... ORDER BY xyz

4829 **

4830 ** is transformed to:

4831 **

4832 ** SELECT xyz FROM ... GROUP BY xyz

4833 **

4834 ** The second form is preferred as a single index (or temp-table) may be

4835 ** used for both the ORDER BY and DISTINCT processing. As originally

4836 ** written the query must use a temp-table for at least one of the ORDER

4837 ** BY and DISTINCT, and an index or separate temp-table for the other.

4838 */

4839 if( (p->selFlags & (SF_Distinct\|SF_Aggregate))==SF_Distinct

4840 && sqlite3ExprListCompare(sSort.pOrderBy, p->pEList, -1)==0

4841 ){

4842 p->selFlags &= ~SF_Distinct;

4843 p->pGroupBy = sqlite3ExprListDup(db, p->pEList, 0);

4844 pGroupBy = p->pGroupBy;

4845 sSort.pOrderBy = 0;

4846 /* Notice that even thought SF_Distinct has been cleared from p->selFlags,

4847 ** the sDistinct.isTnct is still set. Hence, isTnct represents the

4848 ** original setting of the SF_Distinct flag, not the current setting */

4849 assert( sDistinct.isTnct );

4850 }

4851

4852 /* If there is an ORDER BY clause, then this sorting

4853 ** index might end up being unused if the data can be

4854 ** extracted in pre-sorted order. If that is the case, then the

4855 ** OP_OpenEphemeral instruction will be changed to an OP_Noop once

4856 ** we figure out that the sorting index is not needed. The addrSortIndex

4857 ** variable is used to facilitate that change.

4858 */

4859 if( sSort.pOrderBy ){

4860 KeyInfo *pKeyInfo;

4861 pKeyInfo = keyInfoFromExprList(pParse, sSort.pOrderBy, 0, 0);

4862 sSort.iECursor = pParse->nTab++;

4863 sSort.addrSortIndex =

4864 sqlite3VdbeAddOp4(v, OP_OpenEphemeral,

4865 sSort.iECursor, sSort.pOrderBy->nExpr+1+pEList->nExpr, 0,

4866 (char*)pKeyInfo, P4_KEYINFO

4867 );

4868 }else{

4869 sSort.addrSortIndex = -1;

4870 }

4871

4872 /* If the output is destined for a temporary table, open that table.

4873 */

4874 if( pDest->eDest==SRT_EphemTab ){

4875 sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pDest->iSDParm, pEList->nExpr);

4876 }

4877

4878 /* Set the limiter.

4879 */

4880 iEnd = sqlite3VdbeMakeLabel(v);

4881 p->nSelectRow = LARGEST_INT64;

4882 computeLimitRegisters(pParse, p, iEnd);

4883 if( p->iLimit==0 && sSort.addrSortIndex>=0 ){

4884 sqlite3VdbeGetOp(v, sSort.addrSortIndex)->opcode = OP_SorterOpen;

4885 sSort.sortFlags \|= SORTFLAG_UseSorter;

4886 }

4887

4888 /* Open a virtual index to use for the distinct set.

4889 */

4890 if( p->selFlags & SF_Distinct ){

4891 sDistinct.tabTnct = pParse->nTab++;

4892 sDistinct.addrTnct = sqlite3VdbeAddOp4(v, OP_OpenEphemeral,

4893 sDistinct.tabTnct, 0, 0,

4894 (char*)keyInfoFromExprList(pParse, p->pEList,0,0 ),

4895 P4_KEYINFO);

4896 sqlite3VdbeChangeP5(v, BTREE_UNORDERED);

4897 sDistinct.eTnctType = WHERE_DISTINCT_UNORDERED;

4898 }else{

4899 sDistinct.eTnctType = WHERE_DISTINCT_NOOP;

4900 }

4901

4902 if( !isAgg && pGroupBy==0 ){

4903 /* No aggregate functions and no GROUP BY clause */

4904 u16 wctrlFlags = (sDistinct.isTnct ? WHERE_WANT_DISTINCT : 0);

4905

4906 /* Begin the database scan. */

4907 pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, sSort.pOrderBy,

4908 p->pEList, wctrlFlags, 0);

4909 if( pWInfo==0 ) goto select_end;

4910 if( sqlite3WhereOutputRowCount(pWInfo) < p->nSelectRow ){

4911 p->nSelectRow = sqlite3WhereOutputRowCount(pWInfo);

4912 }

4913 if( sDistinct.isTnct && sqlite3WhereIsDistinct(pWInfo) ){

4914 sDistinct.eTnctType = sqlite3WhereIsDistinct(pWInfo);

4915 }

4916 if( sSort.pOrderBy ){

4917 sSort.nOBSat = sqlite3WhereIsOrdered(pWInfo);

4918 if( sSort.nOBSat==sSort.pOrderBy->nExpr ){

4919 sSort.pOrderBy = 0;

4920 }

4921 }

4922

4923 /* If sorting index that was created by a prior OP_OpenEphemeral

4924 ** instruction ended up not being needed, then change the OP_OpenEphemeral

4925 ** into an OP_Noop.

4926 */

4927 if( sSort.addrSortIndex>=0 && sSort.pOrderBy==0 ){

4928 sqlite3VdbeChangeToNoop(v, sSort.addrSortIndex);

4929 }

4930

4931 /* Use the standard inner loop. */

4932 selectInnerLoop(pParse, p, pEList, -1, &sSort, &sDistinct, pDest,

4933 sqlite3WhereContinueLabel(pWInfo),

4934 sqlite3WhereBreakLabel(pWInfo));

4935

4936 /* End the database scan loop.

4937 */

4938 sqlite3WhereEnd(pWInfo);

4939 }else{

4940 /* This case when there exist aggregate functions or a GROUP BY clause

4941 ** or both */

4942 NameContext sNC; /* Name context for processing aggregate information */

4943 int iAMem; /* First Mem address for storing current GROUP BY */

4944 int iBMem; /* First Mem address for previous GROUP BY */

4945 int iUseFlag; /* Mem address holding flag indicating that at least

4946 ** one row of the input to the aggregator has been

4947 ** processed */

4948 int iAbortFlag; /* Mem address which causes query abort if positive */

4949 int groupBySort; /* Rows come from source in GROUP BY order */

4950 int addrEnd; /* End of processing for this SELECT */

4951 int sortPTab = 0; /* Pseudotable used to decode sorting results */

4952 int sortOut = 0; /* Output register from the sorter */

4953 int orderByGrp = 0; /* True if the GROUP BY and ORDER BY are the same */

4954

4955 /* Remove any and all aliases between the result set and the

4956 ** GROUP BY clause.

4957 */

4958 if( pGroupBy ){

4959 int k; /* Loop counter */

4960 struct ExprList_item pItem; / For looping over expression in a list */

4961

4962 for(k=p->pEList->nExpr, pItem=p->pEList->a; k>0; k--, pItem++){

4963 pItem->u.x.iAlias = 0;

4964 }

4965 for(k=pGroupBy->nExpr, pItem=pGroupBy->a; k>0; k--, pItem++){

4966 pItem->u.x.iAlias = 0;

4967 }

4968 if( p->nSelectRow>100 ) p->nSelectRow = 100;

4969 }else{

4970 p->nSelectRow = 1;

4971 }

4972

4973

4974 /* If there is both a GROUP BY and an ORDER BY clause and they are

4975 ** identical, then it may be possible to disable the ORDER BY clause

4976 ** on the grounds that the GROUP BY will cause elements to come out

4977 ** in the correct order. It also may not - the GROUP BY may use a

4978 ** database index that causes rows to be grouped together as required

4979 ** but not actually sorted. Either way, record the fact that the

4980 ** ORDER BY and GROUP BY clauses are the same by setting the orderByGrp

4981 ** variable. */

4982 if( sqlite3ExprListCompare(pGroupBy, sSort.pOrderBy, -1)==0 ){

4983 orderByGrp = 1;

4984 }

4985

4986 /* Create a label to jump to when we want to abort the query */

4987 addrEnd = sqlite3VdbeMakeLabel(v);

4988

4989 /* Convert TK_COLUMN nodes into TK_AGG_COLUMN and make entries in

4990 ** sAggInfo for all TK_AGG_FUNCTION nodes in expressions of the

4991 ** SELECT statement.

4992 */

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

4994 sNC.pParse = pParse;

4995 sNC.pSrcList = pTabList;

4996 sNC.pAggInfo = &sAggInfo;

4997 sAggInfo.mnReg = pParse->nMem+1;

4998 sAggInfo.nSortingColumn = pGroupBy ? pGroupBy->nExpr : 0;

4999 sAggInfo.pGroupBy = pGroupBy;

5000 sqlite3ExprAnalyzeAggList(&sNC, pEList);

5001 sqlite3ExprAnalyzeAggList(&sNC, sSort.pOrderBy);

5002 if( pHaving ){

5003 sqlite3ExprAnalyzeAggregates(&sNC, pHaving);

5004 }

5005 sAggInfo.nAccumulator = sAggInfo.nColumn;

5006 for(i=0; i<sAggInfo.nFunc; i++){

5007 assert( !ExprHasProperty(sAggInfo.aFunc[i].pExpr, EP_xIsSelect) );

5008 sNC.ncFlags \|= NC_InAggFunc;

5009 sqlite3ExprAnalyzeAggList(&sNC, sAggInfo.aFunc[i].pExpr->x.pList);

5010 sNC.ncFlags &= ~NC_InAggFunc;

5011 }

5012 sAggInfo.mxReg = pParse->nMem;

5013 if( db->mallocFailed ) goto select_end;

5014

5015 /* Processing for aggregates with GROUP BY is very different and

5016 ** much more complex than aggregates without a GROUP BY.

5017 */

5018 if( pGroupBy ){

5019 KeyInfo pKeyInfo; / Keying information for the group by clause */

5020 int j1; /* A-vs-B comparision jump */

5021 int addrOutputRow; /* Start of subroutine that outputs a result row */

5022 int regOutputRow; /* Return address register for output subroutine */

5023 int addrSetAbort; /* Set the abort flag and return */

5024 int addrTopOfLoop; /* Top of the input loop */

5025 int addrSortingIdx; /* The OP_OpenEphemeral for the sorting index */

5026 int addrReset; /* Subroutine for resetting the accumulator */

5027 int regReset; /* Return address register for reset subroutine */

5028

5029 /* If there is a GROUP BY clause we might need a sorting index to

5030 ** implement it. Allocate that sorting index now. If it turns out

5031 ** that we do not need it after all, the OP_SorterOpen instruction

5032 ** will be converted into a Noop.

5033 */

5034 sAggInfo.sortingIdx = pParse->nTab++;

5035 pKeyInfo = keyInfoFromExprList(pParse, pGroupBy, 0, 0);

5036 addrSortingIdx = sqlite3VdbeAddOp4(v, OP_SorterOpen,

5037 sAggInfo.sortingIdx, sAggInfo.nSortingColumn,

5038 0, (char*)pKeyInfo, P4_KEYINFO);

5039

5040 /* Initialize memory locations used by GROUP BY aggregate processing

5041 */

5042 iUseFlag = ++pParse->nMem;

5043 iAbortFlag = ++pParse->nMem;

5044 regOutputRow = ++pParse->nMem;

5045 addrOutputRow = sqlite3VdbeMakeLabel(v);

5046 regReset = ++pParse->nMem;

5047 addrReset = sqlite3VdbeMakeLabel(v);

5048 iAMem = pParse->nMem + 1;

5049 pParse->nMem += pGroupBy->nExpr;

5050 iBMem = pParse->nMem + 1;

5051 pParse->nMem += pGroupBy->nExpr;

5052 sqlite3VdbeAddOp2(v, OP_Integer, 0, iAbortFlag);

5053 VdbeComment((v, "clear abort flag"));

5054 sqlite3VdbeAddOp2(v, OP_Integer, 0, iUseFlag);

5055 VdbeComment((v, "indicate accumulator empty"));

5056 sqlite3VdbeAddOp3(v, OP_Null, 0, iAMem, iAMem+pGroupBy->nExpr-1);

5057

5058 /* Begin a loop that will extract all source rows in GROUP BY order.

5059 ** This might involve two separate loops with an OP_Sort in between, or

5060 ** it might be a single loop that uses an index to extract information

5061 ** in the right order to begin with.

5062 */

5063 sqlite3VdbeAddOp2(v, OP_Gosub, regReset, addrReset);

5064 pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pGroupBy, 0,

5065 WHERE_GROUPBY \| (orderByGrp ? WHERE_SORTBYGROUP : 0), 0

5066 );

5067 if( pWInfo==0 ) goto select_end;

5068 if( sqlite3WhereIsOrdered(pWInfo)==pGroupBy->nExpr ){

5069 /* The optimizer is able to deliver rows in group by order so

5070 ** we do not have to sort. The OP_OpenEphemeral table will be

5071 ** cancelled later because we still need to use the pKeyInfo

5072 */

5073 groupBySort = 0;

5074 }else{

5075 /* Rows are coming out in undetermined order. We have to push

5076 ** each row into a sorting index, terminate the first loop,

5077 ** then loop over the sorting index in order to get the output

5078 ** in sorted order

5079 */

5080 int regBase;

5081 int regRecord;

5082 int nCol;

5083 int nGroupBy;

5084

5085 explainTempTable(pParse,

5086 (sDistinct.isTnct && (p->selFlags&SF_Distinct)==0) ?

5087 "DISTINCT" : "GROUP BY");

5088

5089 groupBySort = 1;

5090 nGroupBy = pGroupBy->nExpr;

5091 nCol = nGroupBy;

5092 j = nGroupBy;

5093 for(i=0; i<sAggInfo.nColumn; i++){

5094 if( sAggInfo.aCol[i].iSorterColumn>=j ){

5095 nCol++;

5096 j++;

5097 }

5098 }

5099 regBase = sqlite3GetTempRange(pParse, nCol);

5100 sqlite3ExprCacheClear(pParse);

5101 sqlite3ExprCodeExprList(pParse, pGroupBy, regBase, 0);

5102 j = nGroupBy;

5103 for(i=0; i<sAggInfo.nColumn; i++){

5104 struct AggInfo_col *pCol = &sAggInfo.aCol[i];

5105 if( pCol->iSorterColumn>=j ){

5106 int r1 = j + regBase;

5107 int r2;

5108

5109 r2 = sqlite3ExprCodeGetColumn(pParse,

5110 pCol->pTab, pCol->iColumn, pCol->iTable, r1, 0);

5111 if( r1!=r2 ){

5112 sqlite3VdbeAddOp2(v, OP_SCopy, r2, r1);

5113 }

5114 j++;

5115 }

5116 }

5117 regRecord = sqlite3GetTempReg(pParse);

5118 sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase, nCol, regRecord);

5119 sqlite3VdbeAddOp2(v, OP_SorterInsert, sAggInfo.sortingIdx, regRecord);

5120 sqlite3ReleaseTempReg(pParse, regRecord);

5121 sqlite3ReleaseTempRange(pParse, regBase, nCol);

5122 sqlite3WhereEnd(pWInfo);

5123 sAggInfo.sortingIdxPTab = sortPTab = pParse->nTab++;

5124 sortOut = sqlite3GetTempReg(pParse);

5125 sqlite3VdbeAddOp3(v, OP_OpenPseudo, sortPTab, sortOut, nCol);

5126 sqlite3VdbeAddOp2(v, OP_SorterSort, sAggInfo.sortingIdx, addrEnd);

5127 VdbeComment((v, "GROUP BY sort")); VdbeCoverage(v);

5128 sAggInfo.useSortingIdx = 1;

5129 sqlite3ExprCacheClear(pParse);

5130

5131 }

5132

5133 /* If the index or temporary table used by the GROUP BY sort

5134 ** will naturally deliver rows in the order required by the ORDER BY

5135 ** clause, cancel the ephemeral table open coded earlier.

5136 **

5137 ** This is an optimization - the correct answer should result regardless.

5138 ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER to

5139 ** disable this optimization for testing purposes. */

5140 if( orderByGrp && OptimizationEnabled(db, SQLITE_GroupByOrder)

5141 && (groupBySort \|\| sqlite3WhereIsSorted(pWInfo))

5142 ){

5143 sSort.pOrderBy = 0;

5144 sqlite3VdbeChangeToNoop(v, sSort.addrSortIndex);

5145 }

5146

5147 /* Evaluate the current GROUP BY terms and store in b0, b1, b2...

5148 ** (b0 is memory location iBMem+0, b1 is iBMem+1, and so forth)

5149 ** Then compare the current GROUP BY terms against the GROUP BY terms

5150 ** from the previous row currently stored in a0, a1, a2...

5151 */

5152 addrTopOfLoop = sqlite3VdbeCurrentAddr(v);

5153 sqlite3ExprCacheClear(pParse);

5154 if( groupBySort ){

5155 sqlite3VdbeAddOp3(v, OP_SorterData, sAggInfo.sortingIdx, sortOut,sortPTa b);

5156 }

5157 for(j=0; j<pGroupBy->nExpr; j++){

5158 if( groupBySort ){

5159 sqlite3VdbeAddOp3(v, OP_Column, sortPTab, j, iBMem+j);

5160 }else{

5161 sAggInfo.directMode = 1;

5162 sqlite3ExprCode(pParse, pGroupBy->a[j].pExpr, iBMem+j);

5163 }

5164 }

5165 sqlite3VdbeAddOp4(v, OP_Compare, iAMem, iBMem, pGroupBy->nExpr,

5166 (char*)sqlite3KeyInfoRef(pKeyInfo), P4_KEYINFO);

5167 j1 = sqlite3VdbeCurrentAddr(v);

5168 sqlite3VdbeAddOp3(v, OP_Jump, j1+1, 0, j1+1); VdbeCoverage(v);

5169

5170 /* Generate code that runs whenever the GROUP BY changes.

5171 ** Changes in the GROUP BY are detected by the previous code

5172 ** block. If there were no changes, this block is skipped.

5173 **

5174 ** This code copies current group by terms in b0,b1,b2,...

5175 ** over to a0,a1,a2. It then calls the output subroutine

5176 ** and resets the aggregate accumulator registers in preparation

5177 ** for the next GROUP BY batch.

5178 */

5179 sqlite3ExprCodeMove(pParse, iBMem, iAMem, pGroupBy->nExpr);

5180 sqlite3VdbeAddOp2(v, OP_Gosub, regOutputRow, addrOutputRow);

5181 VdbeComment((v, "output one row"));

5182 sqlite3VdbeAddOp2(v, OP_IfPos, iAbortFlag, addrEnd); VdbeCoverage(v);

5183 VdbeComment((v, "check abort flag"));

5184 sqlite3VdbeAddOp2(v, OP_Gosub, regReset, addrReset);

5185 VdbeComment((v, "reset accumulator"));

5186

5187 /* Update the aggregate accumulators based on the content of

5188 ** the current row

5189 */

5190 sqlite3VdbeJumpHere(v, j1);

5191 updateAccumulator(pParse, &sAggInfo);

5192 sqlite3VdbeAddOp2(v, OP_Integer, 1, iUseFlag);

5193 VdbeComment((v, "indicate data in accumulator"));

5194

5195 /* End of the loop

5196 */

5197 if( groupBySort ){

5198 sqlite3VdbeAddOp2(v, OP_SorterNext, sAggInfo.sortingIdx, addrTopOfLoop);

5199 VdbeCoverage(v);

5200 }else{

5201 sqlite3WhereEnd(pWInfo);

5202 sqlite3VdbeChangeToNoop(v, addrSortingIdx);

5203 }

5204

5205 /* Output the final row of result

5206 */

5207 sqlite3VdbeAddOp2(v, OP_Gosub, regOutputRow, addrOutputRow);

5208 VdbeComment((v, "output final row"));

5209

5210 /* Jump over the subroutines

5211 */

5212 sqlite3VdbeAddOp2(v, OP_Goto, 0, addrEnd);

5213

5214 /* Generate a subroutine that outputs a single row of the result

5215 ** set. This subroutine first looks at the iUseFlag. If iUseFlag

5216 ** is less than or equal to zero, the subroutine is a no-op. If

5217 ** the processing calls for the query to abort, this subroutine

5218 ** increments the iAbortFlag memory location before returning in

5219 ** order to signal the caller to abort.

5220 */

5221 addrSetAbort = sqlite3VdbeCurrentAddr(v);

5222 sqlite3VdbeAddOp2(v, OP_Integer, 1, iAbortFlag);

5223 VdbeComment((v, "set abort flag"));

5224 sqlite3VdbeAddOp1(v, OP_Return, regOutputRow);

5225 sqlite3VdbeResolveLabel(v, addrOutputRow);

5226 addrOutputRow = sqlite3VdbeCurrentAddr(v);

5227 sqlite3VdbeAddOp2(v, OP_IfPos, iUseFlag, addrOutputRow+2); VdbeCoverage(v) ;

5228 VdbeComment((v, "Groupby result generator entry point"));

5229 sqlite3VdbeAddOp1(v, OP_Return, regOutputRow);

5230 finalizeAggFunctions(pParse, &sAggInfo);

5231 sqlite3ExprIfFalse(pParse, pHaving, addrOutputRow+1, SQLITE_JUMPIFNULL);

5232 selectInnerLoop(pParse, p, p->pEList, -1, &sSort,

5233 &sDistinct, pDest,

5234 addrOutputRow+1, addrSetAbort);

5235 sqlite3VdbeAddOp1(v, OP_Return, regOutputRow);

5236 VdbeComment((v, "end groupby result generator"));

5237

5238 /* Generate a subroutine that will reset the group-by accumulator

5239 */

5240 sqlite3VdbeResolveLabel(v, addrReset);

5241 resetAccumulator(pParse, &sAggInfo);

5242 sqlite3VdbeAddOp1(v, OP_Return, regReset);

5243

5244 } /* endif pGroupBy. Begin aggregate queries without GROUP BY: */

5245 else {

5246 ExprList *pDel = 0;

5247 #ifndef SQLITE_OMIT_BTREECOUNT

5248 Table *pTab;

5249 if( (pTab = isSimpleCount(p, &sAggInfo))!=0 ){

5250 /* If isSimpleCount() returns a pointer to a Table structure, then

5251 ** the SQL statement is of the form:

5252 **

5253 ** SELECT count(*) FROM <tbl>

5254 **

5255 ** where the Table structure returned represents table <tbl>.

5256 **

5257 ** This statement is so common that it is optimized specially. The

5258 ** OP_Count instruction is executed either on the intkey table that

5259 ** contains the data for table <tbl> or on one of its indexes. It

5260 ** is better to execute the op on an index, as indexes are almost

5261 ** always spread across less pages than their corresponding tables.

5262 */

5263 const int iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);

5264 const int iCsr = pParse->nTab++; /* Cursor to scan b-tree */

5265 Index pIdx; / Iterator variable */

5266 KeyInfo pKeyInfo = 0; / Keyinfo for scanned index */

5267 Index pBest = 0; / Best index found so far */

5268 int iRoot = pTab->tnum; /* Root page of scanned b-tree */

5269

5270 sqlite3CodeVerifySchema(pParse, iDb);

5271 sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);

5272

5273 /* Search for the index that has the lowest scan cost.

5274 **

5275 ** (2011-04-15) Do not do a full scan of an unordered index.

5276 **

5277 ** (2013-10-03) Do not count the entries in a partial index.

5278 **

5279 ** In practice the KeyInfo structure will not be used. It is only

5280 ** passed to keep OP_OpenRead happy.

5281 */

5282 if( !HasRowid(pTab) ) pBest = sqlite3PrimaryKeyIndex(pTab);

5283 for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){

5284 if( pIdx->bUnordered==0

5285 && pIdx->szIdxRow<pTab->szTabRow

5286 && pIdx->pPartIdxWhere==0

5287 && (!pBest \|\| pIdx->szIdxRow<pBest->szIdxRow)

5288 ){

5289 pBest = pIdx;

5290 }

5291 }

5292 if( pBest ){

5293 iRoot = pBest->tnum;

5294 pKeyInfo = sqlite3KeyInfoOfIndex(pParse, pBest);

5295 }

5296

5297 /* Open a read-only cursor, execute the OP_Count, close the cursor. */

5298 sqlite3VdbeAddOp4Int(v, OP_OpenRead, iCsr, iRoot, iDb, 1);

5299 if( pKeyInfo ){

5300 sqlite3VdbeChangeP4(v, -1, (char *)pKeyInfo, P4_KEYINFO);

5301 }

5302 sqlite3VdbeAddOp2(v, OP_Count, iCsr, sAggInfo.aFunc[0].iMem);

5303 sqlite3VdbeAddOp1(v, OP_Close, iCsr);

5304 explainSimpleCount(pParse, pTab, pBest);

5305 }else

5306 #endif /* SQLITE_OMIT_BTREECOUNT */

5307 {

5308 /* Check if the query is of one of the following forms:

5309 **

5310 ** SELECT min(x) FROM ...

5311 ** SELECT max(x) FROM ...

5312 **

5313 ** If it is, then ask the code in where.c to attempt to sort results

5314 ** as if there was an "ORDER ON x" or "ORDER ON x DESC" clause.

5315 ** If where.c is able to produce results sorted in this order, then

5316 ** add vdbe code to break out of the processing loop after the

5317 ** first iteration (since the first iteration of the loop is

5318 ** guaranteed to operate on the row with the minimum or maximum

5319 ** value of x, the only row required).

5320 **

5321 ** A special flag must be passed to sqlite3WhereBegin() to slightly

5322 ** modify behavior as follows:

5323 **

5324 ** + If the query is a "SELECT min(x)", then the loop coded by

5325 ** where.c should not iterate over any values with a NULL value

5326 ** for x.

5327 **

5328 ** + The optimizer code in where.c (the thing that decides which

5329 ** index or indices to use) should place a different priority on

5330 ** satisfying the 'ORDER BY' clause than it does in other cases.

5331 ** Refer to code and comments in where.c for details.

5332 */

5333 ExprList *pMinMax = 0;

5334 u8 flag = WHERE_ORDERBY_NORMAL;

5335

5336 assert( p->pGroupBy==0 );

5337 assert( flag==0 );

5338 if( p->pHaving==0 ){

5339 flag = minMaxQuery(&sAggInfo, &pMinMax);

5340 }

5341 assert( flag==0 \|\| (pMinMax!=0 && pMinMax->nExpr==1) );

5342

5343 if( flag ){

5344 pMinMax = sqlite3ExprListDup(db, pMinMax, 0);

5345 pDel = pMinMax;

5346 if( pMinMax && !db->mallocFailed ){

5347 pMinMax->a[0].sortOrder = flag!=WHERE_ORDERBY_MIN ?1:0;

5348 pMinMax->a[0].pExpr->op = TK_COLUMN;

5349 }

5350 }

5351

5352 /* This case runs if the aggregate has no GROUP BY clause. The

5353 ** processing is much simpler since there is only a single row

5354 ** of output.

5355 */

5356 resetAccumulator(pParse, &sAggInfo);

5357 pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pMinMax,0,flag,0);

5358 if( pWInfo==0 ){

5359 sqlite3ExprListDelete(db, pDel);

5360 goto select_end;

5361 }

5362 updateAccumulator(pParse, &sAggInfo);

5363 assert( pMinMax==0 \|\| pMinMax->nExpr==1 );

5364 if( sqlite3WhereIsOrdered(pWInfo)>0 ){

5365 sqlite3VdbeAddOp2(v, OP_Goto, 0, sqlite3WhereBreakLabel(pWInfo));

5366 VdbeComment((v, "%s() by index",

5367 (flag==WHERE_ORDERBY_MIN?"min":"max")));

5368 }

5369 sqlite3WhereEnd(pWInfo);

5370 finalizeAggFunctions(pParse, &sAggInfo);

5371 }

5372

5373 sSort.pOrderBy = 0;

5374 sqlite3ExprIfFalse(pParse, pHaving, addrEnd, SQLITE_JUMPIFNULL);

5375 selectInnerLoop(pParse, p, p->pEList, -1, 0, 0,

5376 pDest, addrEnd, addrEnd);

5377 sqlite3ExprListDelete(db, pDel);

5378 }

5379 sqlite3VdbeResolveLabel(v, addrEnd);

5380

5381 } /* endif aggregate query */

5382

5383 if( sDistinct.eTnctType==WHERE_DISTINCT_UNORDERED ){

5384 explainTempTable(pParse, "DISTINCT");

5385 }

5386

5387 /* If there is an ORDER BY clause, then we need to sort the results

5388 ** and send them to the callback one by one.

5389 */

5390 if( sSort.pOrderBy ){

5391 explainTempTable(pParse, sSort.nOBSat>0 ? "RIGHT PART OF ORDER BY":"ORDER BY ");

5392 generateSortTail(pParse, p, &sSort, pEList->nExpr, pDest);

5393 }

5394

5395 /* Jump here to skip this query

5396 */

5397 sqlite3VdbeResolveLabel(v, iEnd);

5398

5399 /* The SELECT was successfully coded. Set the return code to 0

5400 ** to indicate no errors.

5401 */

5402 rc = 0;

5403

5404 /* Control jumps to here if an error is encountered above, or upon

5405 ** successful coding of the SELECT.

5406 */

5407 select_end:

5408 explainSetInteger(pParse->iSelectId, iRestoreSelectId);

5409

5410 /* Identify column names if results of the SELECT are to be output.

5411 */

5412 if( rc==SQLITE_OK && pDest->eDest==SRT_Output ){

5413 generateColumnNames(pParse, pTabList, pEList);

5414 }

5415

5416 sqlite3DbFree(db, sAggInfo.aCol);

5417 sqlite3DbFree(db, sAggInfo.aFunc);

5418 #if SELECTTRACE_ENABLED

5419 SELECTTRACE(1,pParse,p,("end processing\n"));

5420 pParse->nSelectIndent--;

5421 #endif

5422 return rc;

5423 }

5424

5425 #ifdef SQLITE_DEBUG

5426 /*

5427 ** Generate a human-readable description of a the Select object.

5428 */

5429 void sqlite3TreeViewSelect(TreeView pView, const Select p, u8 moreToFollow){

5430 int n = 0;

5431 pView = sqlite3TreeViewPush(pView, moreToFollow);

5432 sqlite3TreeViewLine(pView, "SELECT%s%s",

5433 ((p->selFlags & SF_Distinct) ? " DISTINCT" : ""),

5434 ((p->selFlags & SF_Aggregate) ? " agg_flag" : "")

5435 );

5436 if( p->pSrc && p->pSrc->nSrc ) n++;

5437 if( p->pWhere ) n++;

5438 if( p->pGroupBy ) n++;

5439 if( p->pHaving ) n++;

5440 if( p->pOrderBy ) n++;

5441 if( p->pLimit ) n++;

5442 if( p->pOffset ) n++;

5443 if( p->pPrior ) n++;

5444 sqlite3TreeViewExprList(pView, p->pEList, (n--)>0, "result-set");

5445 if( p->pSrc && p->pSrc->nSrc ){

5446 int i;

5447 pView = sqlite3TreeViewPush(pView, (n--)>0);

5448 sqlite3TreeViewLine(pView, "FROM");

5449 for(i=0; i<p->pSrc->nSrc; i++){

5450 struct SrcList_item *pItem = &p->pSrc->a[i];

5451 StrAccum x;

5452 char zLine[100];

5453 sqlite3StrAccumInit(&x, zLine, sizeof(zLine), 0);

5454 sqlite3XPrintf(&x, 0, "{%d,*}", pItem->iCursor);

5455 if( pItem->zDatabase ){

5456 sqlite3XPrintf(&x, 0, " %s.%s", pItem->zDatabase, pItem->zName);

5457 }else if( pItem->zName ){

5458 sqlite3XPrintf(&x, 0, " %s", pItem->zName);

5459 }

5460 if( pItem->pTab ){

5461 sqlite3XPrintf(&x, 0, " tabname=%Q", pItem->pTab->zName);

5462 }

5463 if( pItem->zAlias ){

5464 sqlite3XPrintf(&x, 0, " (AS %s)", pItem->zAlias);

5465 }

5466 if( pItem->jointype & JT_LEFT ){

5467 sqlite3XPrintf(&x, 0, " LEFT-JOIN");

5468 }

5469 sqlite3StrAccumFinish(&x);

5470 sqlite3TreeViewItem(pView, zLine, i<p->pSrc->nSrc-1);

5471 if( pItem->pSelect ){

5472 sqlite3TreeViewSelect(pView, pItem->pSelect, 0);

5473 }

5474 sqlite3TreeViewPop(pView);

5475 }

5476 sqlite3TreeViewPop(pView);

5477 }

5478 if( p->pWhere ){

5479 sqlite3TreeViewItem(pView, "WHERE", (n--)>0);

5480 sqlite3TreeViewExpr(pView, p->pWhere, 0);

5481 sqlite3TreeViewPop(pView);

5482 }

5483 if( p->pGroupBy ){

5484 sqlite3TreeViewExprList(pView, p->pGroupBy, (n--)>0, "GROUPBY");

5485 }

5486 if( p->pHaving ){

5487 sqlite3TreeViewItem(pView, "HAVING", (n--)>0);

5488 sqlite3TreeViewExpr(pView, p->pHaving, 0);

5489 sqlite3TreeViewPop(pView);

5490 }

5491 if( p->pOrderBy ){

5492 sqlite3TreeViewExprList(pView, p->pOrderBy, (n--)>0, "ORDERBY");

5493 }

5494 if( p->pLimit ){

5495 sqlite3TreeViewItem(pView, "LIMIT", (n--)>0);

5496 sqlite3TreeViewExpr(pView, p->pLimit, 0);

5497 sqlite3TreeViewPop(pView);

5498 }

5499 if( p->pOffset ){

5500 sqlite3TreeViewItem(pView, "OFFSET", (n--)>0);

5501 sqlite3TreeViewExpr(pView, p->pOffset, 0);

5502 sqlite3TreeViewPop(pView);

5503 }

5504 if( p->pPrior ){

5505 const char *zOp = "UNION";

5506 switch( p->op ){

5507 case TK_ALL: zOp = "UNION ALL"; break;

5508 case TK_INTERSECT: zOp = "INTERSECT"; break;

5509 case TK_EXCEPT: zOp = "EXCEPT"; break;

5510 }

5511 sqlite3TreeViewItem(pView, zOp, (n--)>0);

5512 sqlite3TreeViewSelect(pView, p->pPrior, 0);

5513 sqlite3TreeViewPop(pView);

5514 }

5515 sqlite3TreeViewPop(pView);

5516 }

5517 #endif /* SQLITE_DEBUG */

OLD	NEW

« no previous file with comments | « third_party/sqlite/sqlite-src-3080704/src/rowset.c ('k') | third_party/sqlite/sqlite-src-3080704/src/shell.c » ('j') | no next file with comments »