third_party/sqlite/src/where.c - Issue 3108030: Move bundled copy of sqlite one level deeper to better separate it...

Side by Side Diff: third_party/sqlite/src/where.c

Issue 3108030: Move bundled copy of sqlite one level deeper to better separate it... (Closed) Base URL: svn://svn.chromium.org/chrome/trunk/src/

Patch Set: Created 10 years, 4 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:

View unified diff | Download patch | Annotate | Revision Log

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 module contains C code that generates VDBE code used to process

13 ** the WHERE clause of SQL statements. This module is responsible for

14 ** generating the code that loops through a table looking for applicable

15 ** rows. Indices are selected and used to speed the search when doing

16 ** so is applicable. Because this module is responsible for selecting

17 ** indices, you might also think of this module as the "query optimizer".

18 **

19 ** $Id: where.c,v 1.411 2009/07/31 06:14:52 danielk1977 Exp $

20 */

21 #include "sqliteInt.h"

22

23 /*

24 ** Trace output macros

25 */

26 #if defined(SQLITE_TEST) \|\| defined(SQLITE_DEBUG)

27 int sqlite3WhereTrace = 0;

28 #endif

29 #if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)

30 # define WHERETRACE(X) if(sqlite3WhereTrace) sqlite3DebugPrintf X

31 #else

32 # define WHERETRACE(X)

33 #endif

34

35 /* Forward reference

36 */

37 typedef struct WhereClause WhereClause;

38 typedef struct WhereMaskSet WhereMaskSet;

39 typedef struct WhereOrInfo WhereOrInfo;

40 typedef struct WhereAndInfo WhereAndInfo;

41 typedef struct WhereCost WhereCost;

42

43 /*

44 ** The query generator uses an array of instances of this structure to

45 ** help it analyze the subexpressions of the WHERE clause. Each WHERE

46 ** clause subexpression is separated from the others by AND operators,

47 ** usually, or sometimes subexpressions separated by OR.

48 **

49 ** All WhereTerms are collected into a single WhereClause structure.

50 ** The following identity holds:

51 **

52 ** WhereTerm.pWC->a[WhereTerm.idx] == WhereTerm

53 **

54 ** When a term is of the form:

55 **

56 ** X <op> <expr>

57 **

58 ** where X is a column name and <op> is one of certain operators,

59 ** then WhereTerm.leftCursor and WhereTerm.u.leftColumn record the

60 ** cursor number and column number for X. WhereTerm.eOperator records

61 ** the <op> using a bitmask encoding defined by WO_xxx below. The

62 ** use of a bitmask encoding for the operator allows us to search

63 ** quickly for terms that match any of several different operators.

64 **

65 ** A WhereTerm might also be two or more subterms connected by OR:

66 **

67 ** (t1.X <op> <expr>) OR (t1.Y <op> <expr>) OR ....

68 **

69 ** In this second case, wtFlag as the TERM_ORINFO set and eOperator==WO_OR

70 ** and the WhereTerm.u.pOrInfo field points to auxiliary information that

71 ** is collected about the

72 **

73 ** If a term in the WHERE clause does not match either of the two previous

74 ** categories, then eOperator==0. The WhereTerm.pExpr field is still set

75 ** to the original subexpression content and wtFlags is set up appropriately

76 ** but no other fields in the WhereTerm object are meaningful.

77 **

78 ** When eOperator!=0, prereqRight and prereqAll record sets of cursor numbers,

79 ** but they do so indirectly. A single WhereMaskSet structure translates

80 ** cursor number into bits and the translated bit is stored in the prereq

81 ** fields. The translation is used in order to maximize the number of

82 ** bits that will fit in a Bitmask. The VDBE cursor numbers might be

83 ** spread out over the non-negative integers. For example, the cursor

84 ** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45. The WhereMaskSet

85 ** translates these sparse cursor numbers into consecutive integers

86 ** beginning with 0 in order to make the best possible use of the available

87 ** bits in the Bitmask. So, in the example above, the cursor numbers

88 ** would be mapped into integers 0 through 7.

89 **

90 ** The number of terms in a join is limited by the number of bits

91 ** in prereqRight and prereqAll. The default is 64 bits, hence SQLite

92 ** is only able to process joins with 64 or fewer tables.

93 */

94 typedef struct WhereTerm WhereTerm;

95 struct WhereTerm {

96 Expr pExpr; / Pointer to the subexpression that is this term */

97 int iParent; /* Disable pWC->a[iParent] when this term disabled */

98 int leftCursor; /* Cursor number of X in "X <op> <expr>" */

99 union {

100 int leftColumn; /* Column number of X in "X <op> <expr>" */

101 WhereOrInfo pOrInfo; / Extra information if eOperator==WO_OR */

102 WhereAndInfo pAndInfo; / Extra information if eOperator==WO_AND */

103 } u;

104 u16 eOperator; /* A WO_xx value describing <op> */

105 u8 wtFlags; /* TERM_xxx bit flags. See below */

106 u8 nChild; /* Number of children that must disable us */

107 WhereClause pWC; / The clause this term is part of */

108 Bitmask prereqRight; /* Bitmask of tables used by pExpr->pRight */

109 Bitmask prereqAll; /* Bitmask of tables referenced by pExpr */

110 };

111

112 /*

113 ** Allowed values of WhereTerm.wtFlags

114 */

115 #define TERM_DYNAMIC 0x01 /* Need to call sqlite3ExprDelete(db, pExpr) */

116 #define TERM_VIRTUAL 0x02 /* Added by the optimizer. Do not code */

117 #define TERM_CODED 0x04 /* This term is already coded */

118 #define TERM_COPIED 0x08 /* Has a child */

119 #define TERM_ORINFO 0x10 /* Need to free the WhereTerm.u.pOrInfo object */

120 #define TERM_ANDINFO 0x20 /* Need to free the WhereTerm.u.pAndInfo obj */

121 #define TERM_OR_OK 0x40 /* Used during OR-clause processing */

122

123 /*

124 ** An instance of the following structure holds all information about a

125 ** WHERE clause. Mostly this is a container for one or more WhereTerms.

126 */

127 struct WhereClause {

128 Parse pParse; / The parser context */

129 WhereMaskSet pMaskSet; / Mapping of table cursor numbers to bitmasks */

130 Bitmask vmask; /* Bitmask identifying virtual table cursors */

131 u8 op; /* Split operator. TK_AND or TK_OR */

132 int nTerm; /* Number of terms */

133 int nSlot; /* Number of entries in a[] */

134 WhereTerm a; / Each a[] describes a term of the WHERE cluase */

135 #if defined(SQLITE_SMALL_STACK)

136 WhereTerm aStatic[1]; /* Initial static space for a[] */

137 #else

138 WhereTerm aStatic[8]; /* Initial static space for a[] */

139 #endif

140 };

141

142 /*

143 ** A WhereTerm with eOperator==WO_OR has its u.pOrInfo pointer set to

144 ** a dynamically allocated instance of the following structure.

145 */

146 struct WhereOrInfo {

147 WhereClause wc; /* Decomposition into subterms */

148 Bitmask indexable; /* Bitmask of all indexable tables in the clause */

149 };

150

151 /*

152 ** A WhereTerm with eOperator==WO_AND has its u.pAndInfo pointer set to

153 ** a dynamically allocated instance of the following structure.

154 */

155 struct WhereAndInfo {

156 WhereClause wc; /* The subexpression broken out */

157 };

158

159 /*

160 ** An instance of the following structure keeps track of a mapping

161 ** between VDBE cursor numbers and bits of the bitmasks in WhereTerm.

162 **

163 ** The VDBE cursor numbers are small integers contained in

164 ** SrcList_item.iCursor and Expr.iTable fields. For any given WHERE

165 ** clause, the cursor numbers might not begin with 0 and they might

166 ** contain gaps in the numbering sequence. But we want to make maximum

167 ** use of the bits in our bitmasks. This structure provides a mapping

168 ** from the sparse cursor numbers into consecutive integers beginning

169 ** with 0.

170 **

171 ** If WhereMaskSet.ix[A]==B it means that The A-th bit of a Bitmask

172 ** corresponds VDBE cursor number B. The A-th bit of a bitmask is 1<<A.

173 **

174 ** For example, if the WHERE clause expression used these VDBE

175 ** cursors: 4, 5, 8, 29, 57, 73. Then the WhereMaskSet structure

176 ** would map those cursor numbers into bits 0 through 5.

177 **

178 ** Note that the mapping is not necessarily ordered. In the example

179 ** above, the mapping might go like this: 4->3, 5->1, 8->2, 29->0,

180 ** 57->5, 73->4. Or one of 719 other combinations might be used. It

181 ** does not really matter. What is important is that sparse cursor

182 ** numbers all get mapped into bit numbers that begin with 0 and contain

183 ** no gaps.

184 */

185 struct WhereMaskSet {

186 int n; /* Number of assigned cursor values */

187 int ix[BMS]; /* Cursor assigned to each bit */

188 };

189

190 /*

191 ** A WhereCost object records a lookup strategy and the estimated

192 ** cost of pursuing that strategy.

193 */

194 struct WhereCost {

195 WherePlan plan; /* The lookup strategy */

196 double rCost; /* Overall cost of pursuing this search strategy */

197 double nRow; /* Estimated number of output rows */

198 Bitmask used; /* Bitmask of cursors used by this plan */

199 };

200

201 /*

202 ** Bitmasks for the operators that indices are able to exploit. An

203 ** OR-ed combination of these values can be used when searching for

204 ** terms in the where clause.

205 */

206 #define WO_IN 0x001

207 #define WO_EQ 0x002

208 #define WO_LT (WO_EQ<<(TK_LT-TK_EQ))

209 #define WO_LE (WO_EQ<<(TK_LE-TK_EQ))

210 #define WO_GT (WO_EQ<<(TK_GT-TK_EQ))

211 #define WO_GE (WO_EQ<<(TK_GE-TK_EQ))

212 #define WO_MATCH 0x040

213 #define WO_ISNULL 0x080

214 #define WO_OR 0x100 /* Two or more OR-connected terms */

215 #define WO_AND 0x200 /* Two or more AND-connected terms */

216

217 #define WO_ALL 0xfff /* Mask of all possible WO_* values */

218 #define WO_SINGLE 0x0ff /* Mask of all non-compound WO_* values */

219

220 /*

221 ** Value for wsFlags returned by bestIndex() and stored in

222 ** WhereLevel.wsFlags. These flags determine which search

223 ** strategies are appropriate.

224 **

225 ** The least significant 12 bits is reserved as a mask for WO_ values above.

226 ** The WhereLevel.wsFlags field is usually set to WO_IN\|WO_EQ\|WO_ISNULL.

227 ** But if the table is the right table of a left join, WhereLevel.wsFlags

228 ** is set to WO_IN\|WO_EQ. The WhereLevel.wsFlags field can then be used as

229 ** the "op" parameter to findTerm when we are resolving equality constraints.

230 ** ISNULL constraints will then not be used on the right table of a left

231 ** join. Tickets #2177 and #2189.

232 */

233 #define WHERE_ROWID_EQ 0x00001000 /* rowid=EXPR or rowid IN (...) */

234 #define WHERE_ROWID_RANGE 0x00002000 /* rowid<EXPR and/or rowid>EXPR */

235 #define WHERE_COLUMN_EQ 0x00010000 /* x=EXPR or x IN (...) or x IS NULL */

236 #define WHERE_COLUMN_RANGE 0x00020000 /* x<EXPR and/or x>EXPR */

237 #define WHERE_COLUMN_IN 0x00040000 /* x IN (...) */

238 #define WHERE_COLUMN_NULL 0x00080000 /* x IS NULL */

239 #define WHERE_INDEXED 0x000f0000 /* Anything that uses an index */

240 #define WHERE_IN_ABLE 0x000f1000 /* Able to support an IN operator */

241 #define WHERE_TOP_LIMIT 0x00100000 /* x<EXPR or x<=EXPR constraint */

242 #define WHERE_BTM_LIMIT 0x00200000 /* x>EXPR or x>=EXPR constraint */

243 #define WHERE_IDX_ONLY 0x00800000 /* Use index only - omit table */

244 #define WHERE_ORDERBY 0x01000000 /* Output will appear in correct order */

245 #define WHERE_REVERSE 0x02000000 /* Scan in reverse order */

246 #define WHERE_UNIQUE 0x04000000 /* Selects no more than one row */

247 #define WHERE_VIRTUALTABLE 0x08000000 /* Use virtual-table processing */

248 #define WHERE_MULTI_OR 0x10000000 /* OR using multiple indices */

249

250 /*

251 ** Initialize a preallocated WhereClause structure.

252 */

253 static void whereClauseInit(

254 WhereClause pWC, / The WhereClause to be initialized */

255 Parse pParse, / The parsing context */

256 WhereMaskSet pMaskSet / Mapping from table cursor numbers to bitmasks */

257 ){

258 pWC->pParse = pParse;

259 pWC->pMaskSet = pMaskSet;

260 pWC->nTerm = 0;

261 pWC->nSlot = ArraySize(pWC->aStatic);

262 pWC->a = pWC->aStatic;

263 pWC->vmask = 0;

264 }

265

266 /* Forward reference */

267 static void whereClauseClear(WhereClause*);

268

269 /*

270 ** Deallocate all memory associated with a WhereOrInfo object.

271 */

272 static void whereOrInfoDelete(sqlite3 db, WhereOrInfo p){

273 whereClauseClear(&p->wc);

274 sqlite3DbFree(db, p);

275 }

276

277 /*

278 ** Deallocate all memory associated with a WhereAndInfo object.

279 */

280 static void whereAndInfoDelete(sqlite3 db, WhereAndInfo p){

281 whereClauseClear(&p->wc);

282 sqlite3DbFree(db, p);

283 }

284

285 /*

286 ** Deallocate a WhereClause structure. The WhereClause structure

287 ** itself is not freed. This routine is the inverse of whereClauseInit().

288 */

289 static void whereClauseClear(WhereClause *pWC){

290 int i;

291 WhereTerm *a;

292 sqlite3 *db = pWC->pParse->db;

293 for(i=pWC->nTerm-1, a=pWC->a; i>=0; i--, a++){

294 if( a->wtFlags & TERM_DYNAMIC ){

295 sqlite3ExprDelete(db, a->pExpr);

296 }

297 if( a->wtFlags & TERM_ORINFO ){

298 whereOrInfoDelete(db, a->u.pOrInfo);

299 }else if( a->wtFlags & TERM_ANDINFO ){

300 whereAndInfoDelete(db, a->u.pAndInfo);

301 }

302 }

303 if( pWC->a!=pWC->aStatic ){

304 sqlite3DbFree(db, pWC->a);

305 }

306 }

307

308 /*

309 ** Add a single new WhereTerm entry to the WhereClause object pWC.

310 ** The new WhereTerm object is constructed from Expr p and with wtFlags.

311 ** The index in pWC->a[] of the new WhereTerm is returned on success.

312 ** 0 is returned if the new WhereTerm could not be added due to a memory

313 ** allocation error. The memory allocation failure will be recorded in

314 ** the db->mallocFailed flag so that higher-level functions can detect it.

315 **

316 ** This routine will increase the size of the pWC->a[] array as necessary.

317 **

318 ** If the wtFlags argument includes TERM_DYNAMIC, then responsibility

319 ** for freeing the expression p is assumed by the WhereClause object pWC.

320 ** This is true even if this routine fails to allocate a new WhereTerm.

321 **

322 ** WARNING: This routine might reallocate the space used to store

323 ** WhereTerms. All pointers to WhereTerms should be invalidated after

324 ** calling this routine. Such pointers may be reinitialized by referencing

325 ** the pWC->a[] array.

326 */

327 static int whereClauseInsert(WhereClause pWC, Expr p, u8 wtFlags){

328 WhereTerm *pTerm;

329 int idx;

330 if( pWC->nTerm>=pWC->nSlot ){

331 WhereTerm *pOld = pWC->a;

332 sqlite3 *db = pWC->pParse->db;

333 pWC->a = sqlite3DbMallocRaw(db, sizeof(pWC->a[0])pWC->nSlot2 );

334 if( pWC->a==0 ){

335 if( wtFlags & TERM_DYNAMIC ){

336 sqlite3ExprDelete(db, p);

337 }

338 pWC->a = pOld;

339 return 0;

340 }

341 memcpy(pWC->a, pOld, sizeof(pWC->a[0])*pWC->nTerm);

342 if( pOld!=pWC->aStatic ){

343 sqlite3DbFree(db, pOld);

344 }

345 pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]);

346 }

347 pTerm = &pWC->a[idx = pWC->nTerm++];

348 pTerm->pExpr = p;

349 pTerm->wtFlags = wtFlags;

350 pTerm->pWC = pWC;

351 pTerm->iParent = -1;

352 return idx;

353 }

354

355 /*

356 ** This routine identifies subexpressions in the WHERE clause where

357 ** each subexpression is separated by the AND operator or some other

358 ** operator specified in the op parameter. The WhereClause structure

359 ** is filled with pointers to subexpressions. For example:

360 **

361 ** WHERE a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)

362 ** \________/ \_______________/ \________________/

363 ** slot[0] slot[1] slot[2]

364 **

365 ** The original WHERE clause in pExpr is unaltered. All this routine

366 ** does is make slot[] entries point to substructure within pExpr.

367 **

368 ** In the previous sentence and in the diagram, "slot[]" refers to

369 ** the WhereClause.a[] array. The slot[] array grows as needed to contain

370 ** all terms of the WHERE clause.

371 */

372 static void whereSplit(WhereClause pWC, Expr pExpr, int op){

373 pWC->op = (u8)op;

374 if( pExpr==0 ) return;

375 if( pExpr->op!=op ){

376 whereClauseInsert(pWC, pExpr, 0);

377 }else{

378 whereSplit(pWC, pExpr->pLeft, op);

379 whereSplit(pWC, pExpr->pRight, op);

380 }

381 }

382

383 /*

384 ** Initialize an expression mask set (a WhereMaskSet object)

385 */

386 #define initMaskSet(P) memset(P, 0, sizeof(*P))

387

388 /*

389 ** Return the bitmask for the given cursor number. Return 0 if

390 ** iCursor is not in the set.

391 */

392 static Bitmask getMask(WhereMaskSet *pMaskSet, int iCursor){

393 int i;

394 assert( pMaskSet->n<=sizeof(Bitmask)*8 );

395 for(i=0; i<pMaskSet->n; i++){

396 if( pMaskSet->ix[i]==iCursor ){

397 return ((Bitmask)1)<<i;

398 }

399 }

400 return 0;

401 }

402

403 /*

404 ** Create a new mask for cursor iCursor.

405 **

406 ** There is one cursor per table in the FROM clause. The number of

407 ** tables in the FROM clause is limited by a test early in the

408 ** sqlite3WhereBegin() routine. So we know that the pMaskSet->ix[]

409 ** array will never overflow.

410 */

411 static void createMask(WhereMaskSet *pMaskSet, int iCursor){

412 assert( pMaskSet->n < ArraySize(pMaskSet->ix) );

413 pMaskSet->ix[pMaskSet->n++] = iCursor;

414 }

415

416 /*

417 ** This routine walks (recursively) an expression tree and generates

418 ** a bitmask indicating which tables are used in that expression

419 ** tree.

420 **

421 ** In order for this routine to work, the calling function must have

422 ** previously invoked sqlite3ResolveExprNames() on the expression. See

423 ** the header comment on that routine for additional information.

424 ** The sqlite3ResolveExprNames() routines looks for column names and

425 ** sets their opcodes to TK_COLUMN and their Expr.iTable fields to

426 ** the VDBE cursor number of the table. This routine just has to

427 ** translate the cursor numbers into bitmask values and OR all

428 ** the bitmasks together.

429 */

430 static Bitmask exprListTableUsage(WhereMaskSet, ExprList);

431 static Bitmask exprSelectTableUsage(WhereMaskSet, Select);

432 static Bitmask exprTableUsage(WhereMaskSet pMaskSet, Expr p){

433 Bitmask mask = 0;

434 if( p==0 ) return 0;

435 if( p->op==TK_COLUMN ){

436 mask = getMask(pMaskSet, p->iTable);

437 return mask;

438 }

439 mask = exprTableUsage(pMaskSet, p->pRight);

440 mask \|= exprTableUsage(pMaskSet, p->pLeft);

441 if( ExprHasProperty(p, EP_xIsSelect) ){

442 mask \|= exprSelectTableUsage(pMaskSet, p->x.pSelect);

443 }else{

444 mask \|= exprListTableUsage(pMaskSet, p->x.pList);

445 }

446 return mask;

447 }

448 static Bitmask exprListTableUsage(WhereMaskSet pMaskSet, ExprList pList){

449 int i;

450 Bitmask mask = 0;

451 if( pList ){

452 for(i=0; i<pList->nExpr; i++){

453 mask \|= exprTableUsage(pMaskSet, pList->a[i].pExpr);

454 }

455 }

456 return mask;

457 }

458 static Bitmask exprSelectTableUsage(WhereMaskSet pMaskSet, Select pS){

459 Bitmask mask = 0;

460 while( pS ){

461 mask \|= exprListTableUsage(pMaskSet, pS->pEList);

462 mask \|= exprListTableUsage(pMaskSet, pS->pGroupBy);

463 mask \|= exprListTableUsage(pMaskSet, pS->pOrderBy);

464 mask \|= exprTableUsage(pMaskSet, pS->pWhere);

465 mask \|= exprTableUsage(pMaskSet, pS->pHaving);

466 pS = pS->pPrior;

467 }

468 return mask;

469 }

470

471 /*

472 ** Return TRUE if the given operator is one of the operators that is

473 ** allowed for an indexable WHERE clause term. The allowed operators are

474 ** "=", "<", ">", "<=", ">=", and "IN".

475 */

476 static int allowedOp(int op){

477 assert( TK_GT>TK_EQ && TK_GT<TK_GE );

478 assert( TK_LT>TK_EQ && TK_LT<TK_GE );

479 assert( TK_LE>TK_EQ && TK_LE<TK_GE );

480 assert( TK_GE==TK_EQ+4 );

481 return op==TK_IN \|\| (op>=TK_EQ && op<=TK_GE) \|\| op==TK_ISNULL;

482 }

483

484 /*

485 ** Swap two objects of type TYPE.

486 */

487 #define SWAP(TYPE,A,B) {TYPE t=A; A=B; B=t;}

488

489 /*

490 ** Commute a comparison operator. Expressions of the form "X op Y"

491 ** are converted into "Y op X".

492 **

493 ** If a collation sequence is associated with either the left or right

494 ** side of the comparison, it remains associated with the same side after

495 ** the commutation. So "Y collate NOCASE op X" becomes

496 ** "X collate NOCASE op Y". This is because any collation sequence on

497 ** the left hand side of a comparison overrides any collation sequence

498 ** attached to the right. For the same reason the EP_ExpCollate flag

499 ** is not commuted.

500 */

501 static void exprCommute(Parse pParse, Expr pExpr){

502 u16 expRight = (pExpr->pRight->flags & EP_ExpCollate);

503 u16 expLeft = (pExpr->pLeft->flags & EP_ExpCollate);

504 assert( allowedOp(pExpr->op) && pExpr->op!=TK_IN );

505 pExpr->pRight->pColl = sqlite3ExprCollSeq(pParse, pExpr->pRight);

506 pExpr->pLeft->pColl = sqlite3ExprCollSeq(pParse, pExpr->pLeft);

507 SWAP(CollSeq*,pExpr->pRight->pColl,pExpr->pLeft->pColl);

508 pExpr->pRight->flags = (pExpr->pRight->flags & ~EP_ExpCollate) \| expLeft;

509 pExpr->pLeft->flags = (pExpr->pLeft->flags & ~EP_ExpCollate) \| expRight;

510 SWAP(Expr*,pExpr->pRight,pExpr->pLeft);

511 if( pExpr->op>=TK_GT ){

512 assert( TK_LT==TK_GT+2 );

513 assert( TK_GE==TK_LE+2 );

514 assert( TK_GT>TK_EQ );

515 assert( TK_GT<TK_LE );

516 assert( pExpr->op>=TK_GT && pExpr->op<=TK_GE );

517 pExpr->op = ((pExpr->op-TK_GT)^2)+TK_GT;

518 }

519 }

520

521 /*

522 ** Translate from TK_xx operator to WO_xx bitmask.

523 */

524 static u16 operatorMask(int op){

525 u16 c;

526 assert( allowedOp(op) );

527 if( op==TK_IN ){

528 c = WO_IN;

529 }else if( op==TK_ISNULL ){

530 c = WO_ISNULL;

531 }else{

532 assert( (WO_EQ<<(op-TK_EQ)) < 0x7fff );

533 c = (u16)(WO_EQ<<(op-TK_EQ));

534 }

535 assert( op!=TK_ISNULL \|\| c==WO_ISNULL );

536 assert( op!=TK_IN \|\| c==WO_IN );

537 assert( op!=TK_EQ \|\| c==WO_EQ );

538 assert( op!=TK_LT \|\| c==WO_LT );

539 assert( op!=TK_LE \|\| c==WO_LE );

540 assert( op!=TK_GT \|\| c==WO_GT );

541 assert( op!=TK_GE \|\| c==WO_GE );

542 return c;

543 }

544

545 /*

546 ** Search for a term in the WHERE clause that is of the form "X <op> <expr>"

547 ** where X is a reference to the iColumn of table iCur and <op> is one of

548 ** the WO_xx operator codes specified by the op parameter.

549 ** Return a pointer to the term. Return 0 if not found.

550 */

551 static WhereTerm *findTerm(

552 WhereClause pWC, / The WHERE clause to be searched */

553 int iCur, /* Cursor number of LHS */

554 int iColumn, /* Column number of LHS */

555 Bitmask notReady, /* RHS must not overlap with this mask */

556 u32 op, /* Mask of WO_xx values describing operator */

557 Index pIdx / Must be compatible with this index, if not NULL */

558 ){

559 WhereTerm *pTerm;

560 int k;

561 assert( iCur>=0 );

562 op &= WO_ALL;

563 for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){

564 if( pTerm->leftCursor==iCur

565 && (pTerm->prereqRight & notReady)==0

566 && pTerm->u.leftColumn==iColumn

567 && (pTerm->eOperator & op)!=0

568 ){

569 if( pIdx && pTerm->eOperator!=WO_ISNULL ){

570 Expr *pX = pTerm->pExpr;

571 CollSeq *pColl;

572 char idxaff;

573 int j;

574 Parse *pParse = pWC->pParse;

575

576 idxaff = pIdx->pTable->aCol[iColumn].affinity;

577 if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;

578

579 /* Figure out the collation sequence required from an index for

580 ** it to be useful for optimising expression pX. Store this

581 ** value in variable pColl.

582 */

583 assert(pX->pLeft);

584 pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);

585 assert(pColl \|\| pParse->nErr);

586

587 for(j=0; pIdx->aiColumn[j]!=iColumn; j++){

588 if( NEVER(j>=pIdx->nColumn) ) return 0;

589 }

590 if( pColl && sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;

591 }

592 return pTerm;

593 }

594 }

595 return 0;

596 }

597

598 /* Forward reference */

599 static void exprAnalyze(SrcList, WhereClause, int);

600

601 /*

602 ** Call exprAnalyze on all terms in a WHERE clause.

603 **

604 **

605 */

606 static void exprAnalyzeAll(

607 SrcList pTabList, / the FROM clause */

608 WhereClause pWC / the WHERE clause to be analyzed */

609 ){

610 int i;

611 for(i=pWC->nTerm-1; i>=0; i--){

612 exprAnalyze(pTabList, pWC, i);

613 }

614 }

615

616 #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION

617 /*

618 ** Check to see if the given expression is a LIKE or GLOB operator that

619 ** can be optimized using inequality constraints. Return TRUE if it is

620 ** so and false if not.

621 **

622 ** In order for the operator to be optimizible, the RHS must be a string

623 ** literal that does not begin with a wildcard.

624 */

625 static int isLikeOrGlob(

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

627 Expr pExpr, / Test this expression */

628 int pnPattern, / Number of non-wildcard prefix characters */

629 int pisComplete, / True if the only wildcard is % in the last character */

630 int pnoCase / True if uppercase is equivalent to lowercase */

631 ){

632 const char z; / String on RHS of LIKE operator */

633 Expr pRight, pLeft; /* Right and left size of LIKE operator */

634 ExprList pList; / List of operands to the LIKE operator */

635 int c; /* One character in z[] */

636 int cnt; /* Number of non-wildcard prefix characters */

637 char wc[3]; /* Wildcard characters */

638 CollSeq pColl; / Collating sequence for LHS */

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

640

641 if( !sqlite3IsLikeFunction(db, pExpr, pnoCase, wc) ){

642 return 0;

643 }

644 #ifdef SQLITE_EBCDIC

645 if( *pnoCase ) return 0;

646 #endif

647 pList = pExpr->x.pList;

648 pRight = pList->a[0].pExpr;

649 if( pRight->op!=TK_STRING ){

650 return 0;

651 }

652 pLeft = pList->a[1].pExpr;

653 if( pLeft->op!=TK_COLUMN ){

654 return 0;

655 }

656 pColl = sqlite3ExprCollSeq(pParse, pLeft);

657 assert( pColl!=0 \|\| pLeft->iColumn==-1 );

658 if( pColl==0 ) return 0;

659 if( (pColl->type!=SQLITE_COLL_BINARY \|\| *pnoCase) &&

660 (pColl->type!=SQLITE_COLL_NOCASE \|\| !*pnoCase) ){

661 return 0;

662 }

663 if( sqlite3ExprAffinity(pLeft)!=SQLITE_AFF_TEXT ) return 0;

664 z = pRight->u.zToken;

665 if( ALWAYS(z) ){

666 cnt = 0;

667 while( (c=z[cnt])!=0 && c!=wc[0] && c!=wc[1] && c!=wc[2] ){

668 cnt++;

669 }

670 if( cnt!=0 && c!=0 && 255!=(u8)z[cnt-1] ){

671 *pisComplete = z[cnt]==wc[0] && z[cnt+1]==0;

672 *pnPattern = cnt;

673 return 1;

674 }

675 }

676 return 0;

677 }

678 #endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */

679

680

681 #ifndef SQLITE_OMIT_VIRTUALTABLE

682 /*

683 ** Check to see if the given expression is of the form

684 **

685 ** column MATCH expr

686 **

687 ** If it is then return TRUE. If not, return FALSE.

688 */

689 static int isMatchOfColumn(

690 Expr pExpr / Test this expression */

691 ){

692 ExprList *pList;

693

694 if( pExpr->op!=TK_FUNCTION ){

695 return 0;

696 }

697 if( sqlite3StrICmp(pExpr->u.zToken,"match")!=0 ){

698 return 0;

699 }

700 pList = pExpr->x.pList;

701 if( pList->nExpr!=2 ){

702 return 0;

703 }

704 if( pList->a[1].pExpr->op != TK_COLUMN ){

705 return 0;

706 }

707 return 1;

708 }

709 #endif /* SQLITE_OMIT_VIRTUALTABLE */

710

711 /*

712 ** If the pBase expression originated in the ON or USING clause of

713 ** a join, then transfer the appropriate markings over to derived.

714 */

715 static void transferJoinMarkings(Expr pDerived, Expr pBase){

716 pDerived->flags \|= pBase->flags & EP_FromJoin;

717 pDerived->iRightJoinTable = pBase->iRightJoinTable;

718 }

719

720 #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)

721 /*

722 ** Analyze a term that consists of two or more OR-connected

723 ** subterms. So in:

724 **

725 ** ... WHERE (a=5) AND (b=7 OR c=9 OR d=13) AND (d=13)

726 ** ^^^^^^^^^^^^^^^^^^^^

727 **

728 ** This routine analyzes terms such as the middle term in the above example.

729 ** A WhereOrTerm object is computed and attached to the term under

730 ** analysis, regardless of the outcome of the analysis. Hence:

731 **

732 ** WhereTerm.wtFlags \|= TERM_ORINFO

733 ** WhereTerm.u.pOrInfo = a dynamically allocated WhereOrTerm object

734 **

735 ** The term being analyzed must have two or more of OR-connected subterms.

736 ** A single subterm might be a set of AND-connected sub-subterms.

737 ** Examples of terms under analysis:

738 **

739 ** (A) t1.x=t2.y OR t1.x=t2.z OR t1.y=15 OR t1.z=t3.a+5

740 ** (B) x=expr1 OR expr2=x OR x=expr3

741 ** (C) t1.x=t2.y OR (t1.x=t2.z AND t1.y=15)

742 ** (D) x=expr1 OR (y>11 AND y<22 AND z LIKE 'hello')

743 ** (E) (p.a=1 AND q.b=2 AND r.c=3) OR (p.x=4 AND q.y=5 AND r.z=6)

744 **

745 ** CASE 1:

746 **

747 ** If all subterms are of the form T.C=expr for some single column of C

748 ** a single table T (as shown in example B above) then create a new virtual

749 ** term that is an equivalent IN expression. In other words, if the term

750 ** being analyzed is:

751 **

752 ** x = expr1 OR expr2 = x OR x = expr3

753 **

754 ** then create a new virtual term like this:

755 **

756 ** x IN (expr1,expr2,expr3)

757 **

758 ** CASE 2:

759 **

760 ** If all subterms are indexable by a single table T, then set

761 **

762 ** WhereTerm.eOperator = WO_OR

763 ** WhereTerm.u.pOrInfo->indexable \|= the cursor number for table T

764 **

765 ** A subterm is "indexable" if it is of the form

766 ** "T.C <op> <expr>" where C is any column of table T and

767 ** <op> is one of "=", "<", "<=", ">", ">=", "IS NULL", or "IN".

768 ** A subterm is also indexable if it is an AND of two or more

769 ** subsubterms at least one of which is indexable. Indexable AND

770 ** subterms have their eOperator set to WO_AND and they have

771 ** u.pAndInfo set to a dynamically allocated WhereAndTerm object.

772 **

773 ** From another point of view, "indexable" means that the subterm could

774 ** potentially be used with an index if an appropriate index exists.

775 ** This analysis does not consider whether or not the index exists; that

776 ** is something the bestIndex() routine will determine. This analysis

777 ** only looks at whether subterms appropriate for indexing exist.

778 **

779 ** All examples A through E above all satisfy case 2. But if a term

780 ** also statisfies case 1 (such as B) we know that the optimizer will

781 ** always prefer case 1, so in that case we pretend that case 2 is not

782 ** satisfied.

783 **

784 ** It might be the case that multiple tables are indexable. For example,

785 ** (E) above is indexable on tables P, Q, and R.

786 **

787 ** Terms that satisfy case 2 are candidates for lookup by using

788 ** separate indices to find rowids for each subterm and composing

789 ** the union of all rowids using a RowSet object. This is similar

790 ** to "bitmap indices" in other database engines.

791 **

792 ** OTHERWISE:

793 **

794 ** If neither case 1 nor case 2 apply, then leave the eOperator set to

795 ** zero. This term is not useful for search.

796 */

797 static void exprAnalyzeOrTerm(

798 SrcList pSrc, / the FROM clause */

799 WhereClause pWC, / the complete WHERE clause */

800 int idxTerm /* Index of the OR-term to be analyzed */

801 ){

802 Parse pParse = pWC->pParse; / Parser context */

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

804 WhereTerm pTerm = &pWC->a[idxTerm]; / The term to be analyzed */

805 Expr pExpr = pTerm->pExpr; / The expression of the term */

806 WhereMaskSet pMaskSet = pWC->pMaskSet; / Table use masks */

807 int i; /* Loop counters */

808 WhereClause pOrWc; / Breakup of pTerm into subterms */

809 WhereTerm pOrTerm; / A Sub-term within the pOrWc */

810 WhereOrInfo pOrInfo; / Additional information associated with pTerm */

811 Bitmask chngToIN; /* Tables that might satisfy case 1 */

812 Bitmask indexable; /* Tables that are indexable, satisfying case 2 */

813

814 /*

815 ** Break the OR clause into its separate subterms. The subterms are

816 ** stored in a WhereClause structure containing within the WhereOrInfo

817 ** object that is attached to the original OR clause term.

818 */

819 assert( (pTerm->wtFlags & (TERM_DYNAMIC\|TERM_ORINFO\|TERM_ANDINFO))==0 );

820 assert( pExpr->op==TK_OR );

821 pTerm->u.pOrInfo = pOrInfo = sqlite3DbMallocZero(db, sizeof(*pOrInfo));

822 if( pOrInfo==0 ) return;

823 pTerm->wtFlags \|= TERM_ORINFO;

824 pOrWc = &pOrInfo->wc;

825 whereClauseInit(pOrWc, pWC->pParse, pMaskSet);

826 whereSplit(pOrWc, pExpr, TK_OR);

827 exprAnalyzeAll(pSrc, pOrWc);

828 if( db->mallocFailed ) return;

829 assert( pOrWc->nTerm>=2 );

830

831 /*

832 ** Compute the set of tables that might satisfy cases 1 or 2.

833 */

834 indexable = ~(Bitmask)0;

835 chngToIN = ~(pWC->vmask);

836 for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0 && indexable; i--, pOrTerm++){

837 if( (pOrTerm->eOperator & WO_SINGLE)==0 ){

838 WhereAndInfo *pAndInfo;

839 assert( pOrTerm->eOperator==0 );

840 assert( (pOrTerm->wtFlags & (TERM_ANDINFO\|TERM_ORINFO))==0 );

841 chngToIN = 0;

842 pAndInfo = sqlite3DbMallocRaw(db, sizeof(*pAndInfo));

843 if( pAndInfo ){

844 WhereClause *pAndWC;

845 WhereTerm *pAndTerm;

846 int j;

847 Bitmask b = 0;

848 pOrTerm->u.pAndInfo = pAndInfo;

849 pOrTerm->wtFlags \|= TERM_ANDINFO;

850 pOrTerm->eOperator = WO_AND;

851 pAndWC = &pAndInfo->wc;

852 whereClauseInit(pAndWC, pWC->pParse, pMaskSet);

853 whereSplit(pAndWC, pOrTerm->pExpr, TK_AND);

854 exprAnalyzeAll(pSrc, pAndWC);

855 testcase( db->mallocFailed );

856 if( !db->mallocFailed ){

857 for(j=0, pAndTerm=pAndWC->a; j<pAndWC->nTerm; j++, pAndTerm++){

858 assert( pAndTerm->pExpr );

859 if( allowedOp(pAndTerm->pExpr->op) ){

860 b \|= getMask(pMaskSet, pAndTerm->leftCursor);

861 }

862 }

863 }

864 indexable &= b;

865 }

866 }else if( pOrTerm->wtFlags & TERM_COPIED ){

867 /* Skip this term for now. We revisit it when we process the

868 ** corresponding TERM_VIRTUAL term */

869 }else{

870 Bitmask b;

871 b = getMask(pMaskSet, pOrTerm->leftCursor);

872 if( pOrTerm->wtFlags & TERM_VIRTUAL ){

873 WhereTerm *pOther = &pOrWc->a[pOrTerm->iParent];

874 b \|= getMask(pMaskSet, pOther->leftCursor);

875 }

876 indexable &= b;

877 if( pOrTerm->eOperator!=WO_EQ ){

878 chngToIN = 0;

879 }else{

880 chngToIN &= b;

881 }

882 }

883 }

884

885 /*

886 ** Record the set of tables that satisfy case 2. The set might be

887 ** empty.

888 */

889 pOrInfo->indexable = indexable;

890 pTerm->eOperator = indexable==0 ? 0 : WO_OR;

891

892 /*

893 ** chngToIN holds a set of tables that might satisfy case 1. But

894 ** we have to do some additional checking to see if case 1 really

895 ** is satisfied.

896 **

897 ** chngToIN will hold either 0, 1, or 2 bits. The 0-bit case means

898 ** that there is no possibility of transforming the OR clause into an

899 ** IN operator because one or more terms in the OR clause contain

900 ** something other than == on a column in the single table. The 1-bit

901 ** case means that every term of the OR clause is of the form

902 ** "table.column=expr" for some single table. The one bit that is set

903 ** will correspond to the common table. We still need to check to make

904 ** sure the same column is used on all terms. The 2-bit case is when

905 ** the all terms are of the form "table1.column=table2.column". It

906 ** might be possible to form an IN operator with either table1.column

907 ** or table2.column as the LHS if either is common to every term of

908 ** the OR clause.

909 **

910 ** Note that terms of the form "table.column1=table.column2" (the

911 ** same table on both sizes of the ==) cannot be optimized.

912 */

913 if( chngToIN ){

914 int okToChngToIN = 0; /* True if the conversion to IN is valid */

915 int iColumn = -1; /* Column index on lhs of IN operator */

916 int iCursor = -1; /* Table cursor common to all terms */

917 int j = 0; /* Loop counter */

918

919 /* Search for a table and column that appears on one side or the

920 ** other of the == operator in every subterm. That table and column

921 ** will be recorded in iCursor and iColumn. There might not be any

922 ** such table and column. Set okToChngToIN if an appropriate table

923 ** and column is found but leave okToChngToIN false if not found.

924 */

925 for(j=0; j<2 && !okToChngToIN; j++){

926 pOrTerm = pOrWc->a;

927 for(i=pOrWc->nTerm-1; i>=0; i--, pOrTerm++){

928 assert( pOrTerm->eOperator==WO_EQ );

929 pOrTerm->wtFlags &= ~TERM_OR_OK;

930 if( pOrTerm->leftCursor==iCursor ){

931 /* This is the 2-bit case and we are on the second iteration and

932 ** current term is from the first iteration. So skip this term. */

933 assert( j==1 );

934 continue;

935 }

936 if( (chngToIN & getMask(pMaskSet, pOrTerm->leftCursor))==0 ){

937 /* This term must be of the form t1.a==t2.b where t2 is in the

938 ** chngToIN set but t1 is not. This term will be either preceeded

939 ** or follwed by an inverted copy (t2.b==t1.a). Skip this term

940 ** and use its inversion. */

941 testcase( pOrTerm->wtFlags & TERM_COPIED );

942 testcase( pOrTerm->wtFlags & TERM_VIRTUAL );

943 assert( pOrTerm->wtFlags & (TERM_COPIED\|TERM_VIRTUAL) );

944 continue;

945 }

946 iColumn = pOrTerm->u.leftColumn;

947 iCursor = pOrTerm->leftCursor;

948 break;

949 }

950 if( i<0 ){

951 /* No candidate table+column was found. This can only occur

952 ** on the second iteration */

953 assert( j==1 );

954 assert( (chngToIN&(chngToIN-1))==0 );

955 assert( chngToIN==getMask(pMaskSet, iCursor) );

956 break;

957 }

958 testcase( j==1 );

959

960 /* We have found a candidate table and column. Check to see if that

961 ** table and column is common to every term in the OR clause */

962 okToChngToIN = 1;

963 for(; i>=0 && okToChngToIN; i--, pOrTerm++){

964 assert( pOrTerm->eOperator==WO_EQ );

965 if( pOrTerm->leftCursor!=iCursor ){

966 pOrTerm->wtFlags &= ~TERM_OR_OK;

967 }else if( pOrTerm->u.leftColumn!=iColumn ){

968 okToChngToIN = 0;

969 }else{

970 int affLeft, affRight;

971 /* If the right-hand side is also a column, then the affinities

972 ** of both right and left sides must be such that no type

973 ** conversions are required on the right. (Ticket #2249)

974 */

975 affRight = sqlite3ExprAffinity(pOrTerm->pExpr->pRight);

976 affLeft = sqlite3ExprAffinity(pOrTerm->pExpr->pLeft);

977 if( affRight!=0 && affRight!=affLeft ){

978 okToChngToIN = 0;

979 }else{

980 pOrTerm->wtFlags \|= TERM_OR_OK;

981 }

982 }

983 }

984 }

985

986 /* At this point, okToChngToIN is true if original pTerm satisfies

987 ** case 1. In that case, construct a new virtual term that is

988 ** pTerm converted into an IN operator.

989 */

990 if( okToChngToIN ){

991 Expr pDup; / A transient duplicate expression */

992 ExprList pList = 0; / The RHS of the IN operator */

993 Expr pLeft = 0; / The LHS of the IN operator */

994 Expr pNew; / The complete IN operator */

995

996 for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0; i--, pOrTerm++){

997 if( (pOrTerm->wtFlags & TERM_OR_OK)==0 ) continue;

998 assert( pOrTerm->eOperator==WO_EQ );

999 assert( pOrTerm->leftCursor==iCursor );

1000 assert( pOrTerm->u.leftColumn==iColumn );

1001 pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight, 0);

1002 pList = sqlite3ExprListAppend(pWC->pParse, pList, pDup);

1003 pLeft = pOrTerm->pExpr->pLeft;

1004 }

1005 assert( pLeft!=0 );

1006 pDup = sqlite3ExprDup(db, pLeft, 0);

1007 pNew = sqlite3PExpr(pParse, TK_IN, pDup, 0, 0);

1008 if( pNew ){

1009 int idxNew;

1010 transferJoinMarkings(pNew, pExpr);

1011 assert( !ExprHasProperty(pNew, EP_xIsSelect) );

1012 pNew->x.pList = pList;

1013 idxNew = whereClauseInsert(pWC, pNew, TERM_VIRTUAL\|TERM_DYNAMIC);

1014 testcase( idxNew==0 );

1015 exprAnalyze(pSrc, pWC, idxNew);

1016 pTerm = &pWC->a[idxTerm];

1017 pWC->a[idxNew].iParent = idxTerm;

1018 pTerm->nChild = 1;

1019 }else{

1020 sqlite3ExprListDelete(db, pList);

1021 }

1022 pTerm->eOperator = 0; /* case 1 trumps case 2 */

1023 }

1024 }

1025 }

1026 #endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */

1027

1028

1029 /*

1030 ** The input to this routine is an WhereTerm structure with only the

1031 ** "pExpr" field filled in. The job of this routine is to analyze the

1032 ** subexpression and populate all the other fields of the WhereTerm

1033 ** structure.

1034 **

1035 ** If the expression is of the form "<expr> <op> X" it gets commuted

1036 ** to the standard form of "X <op> <expr>".

1037 **

1038 ** If the expression is of the form "X <op> Y" where both X and Y are

1039 ** columns, then the original expression is unchanged and a new virtual

1040 ** term of the form "Y <op> X" is added to the WHERE clause and

1041 ** analyzed separately. The original term is marked with TERM_COPIED

1042 ** and the new term is marked with TERM_DYNAMIC (because it's pExpr

1043 ** needs to be freed with the WhereClause) and TERM_VIRTUAL (because it

1044 ** is a commuted copy of a prior term.) The original term has nChild=1

1045 ** and the copy has idxParent set to the index of the original term.

1046 */

1047 static void exprAnalyze(

1048 SrcList pSrc, / the FROM clause */

1049 WhereClause pWC, / the WHERE clause */

1050 int idxTerm /* Index of the term to be analyzed */

1051 ){

1052 WhereTerm pTerm; / The term to be analyzed */

1053 WhereMaskSet pMaskSet; / Set of table index masks */

1054 Expr pExpr; / The expression to be analyzed */

1055 Bitmask prereqLeft; /* Prerequesites of the pExpr->pLeft */

1056 Bitmask prereqAll; /* Prerequesites of pExpr */

1057 Bitmask extraRight = 0;

1058 int nPattern;

1059 int isComplete;

1060 int noCase;

1061 int op; /* Top-level operator. pExpr->op */

1062 Parse pParse = pWC->pParse; / Parsing context */

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

1064

1065 if( db->mallocFailed ){

1066 return;

1067 }

1068 pTerm = &pWC->a[idxTerm];

1069 pMaskSet = pWC->pMaskSet;

1070 pExpr = pTerm->pExpr;

1071 prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft);

1072 op = pExpr->op;

1073 if( op==TK_IN ){

1074 assert( pExpr->pRight==0 );

1075 if( ExprHasProperty(pExpr, EP_xIsSelect) ){

1076 pTerm->prereqRight = exprSelectTableUsage(pMaskSet, pExpr->x.pSelect);

1077 }else{

1078 pTerm->prereqRight = exprListTableUsage(pMaskSet, pExpr->x.pList);

1079 }

1080 }else if( op==TK_ISNULL ){

1081 pTerm->prereqRight = 0;

1082 }else{

1083 pTerm->prereqRight = exprTableUsage(pMaskSet, pExpr->pRight);

1084 }

1085 prereqAll = exprTableUsage(pMaskSet, pExpr);

1086 if( ExprHasProperty(pExpr, EP_FromJoin) ){

1087 Bitmask x = getMask(pMaskSet, pExpr->iRightJoinTable);

1088 prereqAll \|= x;

1089 extraRight = x-1; /* ON clause terms may not be used with an index

1090 ** on left table of a LEFT JOIN. Ticket #3015 */

1091 }

1092 pTerm->prereqAll = prereqAll;

1093 pTerm->leftCursor = -1;

1094 pTerm->iParent = -1;

1095 pTerm->eOperator = 0;

1096 if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){

1097 Expr *pLeft = pExpr->pLeft;

1098 Expr *pRight = pExpr->pRight;

1099 if( pLeft->op==TK_COLUMN ){

1100 pTerm->leftCursor = pLeft->iTable;

1101 pTerm->u.leftColumn = pLeft->iColumn;

1102 pTerm->eOperator = operatorMask(op);

1103 }

1104 if( pRight && pRight->op==TK_COLUMN ){

1105 WhereTerm *pNew;

1106 Expr *pDup;

1107 if( pTerm->leftCursor>=0 ){

1108 int idxNew;

1109 pDup = sqlite3ExprDup(db, pExpr, 0);

1110 if( db->mallocFailed ){

1111 sqlite3ExprDelete(db, pDup);

1112 return;

1113 }

1114 idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL\|TERM_DYNAMIC);

1115 if( idxNew==0 ) return;

1116 pNew = &pWC->a[idxNew];

1117 pNew->iParent = idxTerm;

1118 pTerm = &pWC->a[idxTerm];

1119 pTerm->nChild = 1;

1120 pTerm->wtFlags \|= TERM_COPIED;

1121 }else{

1122 pDup = pExpr;

1123 pNew = pTerm;

1124 }

1125 exprCommute(pParse, pDup);

1126 pLeft = pDup->pLeft;

1127 pNew->leftCursor = pLeft->iTable;

1128 pNew->u.leftColumn = pLeft->iColumn;

1129 pNew->prereqRight = prereqLeft;

1130 pNew->prereqAll = prereqAll;

1131 pNew->eOperator = operatorMask(pDup->op);

1132 }

1133 }

1134

1135 #ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION

1136 /* If a term is the BETWEEN operator, create two new virtual terms

1137 ** that define the range that the BETWEEN implements. For example:

1138 **

1139 ** a BETWEEN b AND c

1140 **

1141 ** is converted into:

1142 **

1143 ** (a BETWEEN b AND c) AND (a>=b) AND (a<=c)

1144 **

1145 ** The two new terms are added onto the end of the WhereClause object.

1146 ** The new terms are "dynamic" and are children of the original BETWEEN

1147 ** term. That means that if the BETWEEN term is coded, the children are

1148 ** skipped. Or, if the children are satisfied by an index, the original

1149 ** BETWEEN term is skipped.

1150 */

1151 else if( pExpr->op==TK_BETWEEN && pWC->op==TK_AND ){

1152 ExprList *pList = pExpr->x.pList;

1153 int i;

1154 static const u8 ops[] = {TK_GE, TK_LE};

1155 assert( pList!=0 );

1156 assert( pList->nExpr==2 );

1157 for(i=0; i<2; i++){

1158 Expr *pNewExpr;

1159 int idxNew;

1160 pNewExpr = sqlite3PExpr(pParse, ops[i],

1161 sqlite3ExprDup(db, pExpr->pLeft, 0),

1162 sqlite3ExprDup(db, pList->a[i].pExpr, 0), 0);

1163 idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL\|TERM_DYNAMIC);

1164 testcase( idxNew==0 );

1165 exprAnalyze(pSrc, pWC, idxNew);

1166 pTerm = &pWC->a[idxTerm];

1167 pWC->a[idxNew].iParent = idxTerm;

1168 }

1169 pTerm->nChild = 2;

1170 }

1171 #endif /* SQLITE_OMIT_BETWEEN_OPTIMIZATION */

1172

1173 #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)

1174 /* Analyze a term that is composed of two or more subterms connected by

1175 ** an OR operator.

1176 */

1177 else if( pExpr->op==TK_OR ){

1178 assert( pWC->op==TK_AND );

1179 exprAnalyzeOrTerm(pSrc, pWC, idxTerm);

1180 pTerm = &pWC->a[idxTerm];

1181 }

1182 #endif /* SQLITE_OMIT_OR_OPTIMIZATION */

1183

1184 #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION

1185 /* Add constraints to reduce the search space on a LIKE or GLOB

1186 ** operator.

1187 **

1188 ** A like pattern of the form "x LIKE 'abc%'" is changed into constraints

1189 **

1190 ** x>='abc' AND x<'abd' AND x LIKE 'abc%'

1191 **

1192 ** The last character of the prefix "abc" is incremented to form the

1193 ** termination condition "abd".

1194 */

1195 if( isLikeOrGlob(pParse, pExpr, &nPattern, &isComplete, &noCase)

1196 && pWC->op==TK_AND ){

1197 Expr pLeft, pRight;

1198 Expr pStr1, pStr2;

1199 Expr pNewExpr1, pNewExpr2;

1200 int idxNew1, idxNew2;

1201

1202 pLeft = pExpr->x.pList->a[1].pExpr;

1203 pRight = pExpr->x.pList->a[0].pExpr;

1204 pStr1 = sqlite3Expr(db, TK_STRING, pRight->u.zToken);

1205 if( pStr1 ) pStr1->u.zToken[nPattern] = 0;

1206 pStr2 = sqlite3ExprDup(db, pStr1, 0);

1207 if( !db->mallocFailed ){

1208 u8 c, pC; / Last character before the first wildcard */

1209 pC = (u8*)&pStr2->u.zToken[nPattern-1];

1210 c = *pC;

1211 if( noCase ){

1212 /* The point is to increment the last character before the first

1213 ** wildcard. But if we increment '@', that will push it into the

1214 ** alphabetic range where case conversions will mess up the

1215 ** inequality. To avoid this, make sure to also run the full

1216 ** LIKE on all candidate expressions by clearing the isComplete flag

1217 */

1218 if( c=='A'-1 ) isComplete = 0;

1219

1220 c = sqlite3UpperToLower[c];

1221 }

1222 *pC = c + 1;

1223 }

1224 pNewExpr1 = sqlite3PExpr(pParse, TK_GE, sqlite3ExprDup(db,pLeft,0),pStr1,0);

1225 idxNew1 = whereClauseInsert(pWC, pNewExpr1, TERM_VIRTUAL\|TERM_DYNAMIC);

1226 testcase( idxNew1==0 );

1227 exprAnalyze(pSrc, pWC, idxNew1);

1228 pNewExpr2 = sqlite3PExpr(pParse, TK_LT, sqlite3ExprDup(db,pLeft,0),pStr2,0);

1229 idxNew2 = whereClauseInsert(pWC, pNewExpr2, TERM_VIRTUAL\|TERM_DYNAMIC);

1230 testcase( idxNew2==0 );

1231 exprAnalyze(pSrc, pWC, idxNew2);

1232 pTerm = &pWC->a[idxTerm];

1233 if( isComplete ){

1234 pWC->a[idxNew1].iParent = idxTerm;

1235 pWC->a[idxNew2].iParent = idxTerm;

1236 pTerm->nChild = 2;

1237 }

1238 }

1239 #endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */

1240

1241 #ifndef SQLITE_OMIT_VIRTUALTABLE

1242 /* Add a WO_MATCH auxiliary term to the constraint set if the

1243 ** current expression is of the form: column MATCH expr.

1244 ** This information is used by the xBestIndex methods of

1245 ** virtual tables. The native query optimizer does not attempt

1246 ** to do anything with MATCH functions.

1247 */

1248 if( isMatchOfColumn(pExpr) ){

1249 int idxNew;

1250 Expr pRight, pLeft;

1251 WhereTerm *pNewTerm;

1252 Bitmask prereqColumn, prereqExpr;

1253

1254 pRight = pExpr->x.pList->a[0].pExpr;

1255 pLeft = pExpr->x.pList->a[1].pExpr;

1256 prereqExpr = exprTableUsage(pMaskSet, pRight);

1257 prereqColumn = exprTableUsage(pMaskSet, pLeft);

1258 if( (prereqExpr & prereqColumn)==0 ){

1259 Expr *pNewExpr;

1260 pNewExpr = sqlite3PExpr(pParse, TK_MATCH,

1261 0, sqlite3ExprDup(db, pRight, 0), 0);

1262 idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL\|TERM_DYNAMIC);

1263 testcase( idxNew==0 );

1264 pNewTerm = &pWC->a[idxNew];

1265 pNewTerm->prereqRight = prereqExpr;

1266 pNewTerm->leftCursor = pLeft->iTable;

1267 pNewTerm->u.leftColumn = pLeft->iColumn;

1268 pNewTerm->eOperator = WO_MATCH;

1269 pNewTerm->iParent = idxTerm;

1270 pTerm = &pWC->a[idxTerm];

1271 pTerm->nChild = 1;

1272 pTerm->wtFlags \|= TERM_COPIED;

1273 pNewTerm->prereqAll = pTerm->prereqAll;

1274 }

1275 }

1276 #endif /* SQLITE_OMIT_VIRTUALTABLE */

1277

1278 /* Prevent ON clause terms of a LEFT JOIN from being used to drive

1279 ** an index for tables to the left of the join.

1280 */

1281 pTerm->prereqRight \|= extraRight;

1282 }

1283

1284 /*

1285 ** Return TRUE if any of the expressions in pList->a[iFirst...] contain

1286 ** a reference to any table other than the iBase table.

1287 */

1288 static int referencesOtherTables(

1289 ExprList pList, / Search expressions in ths list */

1290 WhereMaskSet pMaskSet, / Mapping from tables to bitmaps */

1291 int iFirst, /* Be searching with the iFirst-th expression */

1292 int iBase /* Ignore references to this table */

1293 ){

1294 Bitmask allowed = ~getMask(pMaskSet, iBase);

1295 while( iFirst<pList->nExpr ){

1296 if( (exprTableUsage(pMaskSet, pList->a[iFirst++].pExpr)&allowed)!=0 ){

1297 return 1;

1298 }

1299 }

1300 return 0;

1301 }

1302

1303

1304 /*

1305 ** This routine decides if pIdx can be used to satisfy the ORDER BY

1306 ** clause. If it can, it returns 1. If pIdx cannot satisfy the

1307 ** ORDER BY clause, this routine returns 0.

1308 **

1309 ** pOrderBy is an ORDER BY clause from a SELECT statement. pTab is the

1310 ** left-most table in the FROM clause of that same SELECT statement and

1311 ** the table has a cursor number of "base". pIdx is an index on pTab.

1312 **

1313 ** nEqCol is the number of columns of pIdx that are used as equality

1314 ** constraints. Any of these columns may be missing from the ORDER BY

1315 ** clause and the match can still be a success.

1316 **

1317 ** All terms of the ORDER BY that match against the index must be either

1318 ** ASC or DESC. (Terms of the ORDER BY clause past the end of a UNIQUE

1319 ** index do not need to satisfy this constraint.) The *pbRev value is

1320 ** set to 1 if the ORDER BY clause is all DESC and it is set to 0 if

1321 ** the ORDER BY clause is all ASC.

1322 */

1323 static int isSortingIndex(

1324 Parse pParse, / Parsing context */

1325 WhereMaskSet pMaskSet, / Mapping from table cursor numbers to bitmaps */

1326 Index pIdx, / The index we are testing */

1327 int base, /* Cursor number for the table to be sorted */

1328 ExprList pOrderBy, / The ORDER BY clause */

1329 int nEqCol, /* Number of index columns with == constraints */

1330 int pbRev / Set to 1 if ORDER BY is DESC */

1331 ){

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

1333 int sortOrder = 0; /* XOR of index and ORDER BY sort direction */

1334 int nTerm; /* Number of ORDER BY terms */

1335 struct ExprList_item pTerm; / A term of the ORDER BY clause */

1336 sqlite3 *db = pParse->db;

1337

1338 assert( pOrderBy!=0 );

1339 nTerm = pOrderBy->nExpr;

1340 assert( nTerm>0 );

1341

1342 /* Argument pIdx must either point to a 'real' named index structure,

1343 ** or an index structure allocated on the stack by bestBtreeIndex() to

1344 ** represent the rowid index that is part of every table. */

1345 assert( pIdx->zName \|\| (pIdx->nColumn==1 && pIdx->aiColumn[0]==-1) );

1346

1347 /* Match terms of the ORDER BY clause against columns of

1348 ** the index.

1349 **

1350 ** Note that indices have pIdx->nColumn regular columns plus

1351 ** one additional column containing the rowid. The rowid column

1352 ** of the index is also allowed to match against the ORDER BY

1353 ** clause.

1354 */

1355 for(i=j=0, pTerm=pOrderBy->a; j<nTerm && i<=pIdx->nColumn; i++){

1356 Expr pExpr; / The expression of the ORDER BY pTerm */

1357 CollSeq pColl; / The collating sequence of pExpr */

1358 int termSortOrder; /* Sort order for this term */

1359 int iColumn; /* The i-th column of the index. -1 for rowid */

1360 int iSortOrder; /* 1 for DESC, 0 for ASC on the i-th index term */

1361 const char zColl; / Name of the collating sequence for i-th index term */

1362

1363 pExpr = pTerm->pExpr;

1364 if( pExpr->op!=TK_COLUMN \|\| pExpr->iTable!=base ){

1365 /* Can not use an index sort on anything that is not a column in the

1366 ** left-most table of the FROM clause */

1367 break;

1368 }

1369 pColl = sqlite3ExprCollSeq(pParse, pExpr);

1370 if( !pColl ){

1371 pColl = db->pDfltColl;

1372 }

1373 if( pIdx->zName && i<pIdx->nColumn ){

1374 iColumn = pIdx->aiColumn[i];

1375 if( iColumn==pIdx->pTable->iPKey ){

1376 iColumn = -1;

1377 }

1378 iSortOrder = pIdx->aSortOrder[i];

1379 zColl = pIdx->azColl[i];

1380 }else{

1381 iColumn = -1;

1382 iSortOrder = 0;

1383 zColl = pColl->zName;

1384 }

1385 if( pExpr->iColumn!=iColumn \|\| sqlite3StrICmp(pColl->zName, zColl) ){

1386 /* Term j of the ORDER BY clause does not match column i of the index */

1387 if( i<nEqCol ){

1388 /* If an index column that is constrained by == fails to match an

1389 ** ORDER BY term, that is OK. Just ignore that column of the index

1390 */

1391 continue;

1392 }else if( i==pIdx->nColumn ){

1393 /* Index column i is the rowid. All other terms match. */

1394 break;

1395 }else{

1396 /* If an index column fails to match and is not constrained by ==

1397 ** then the index cannot satisfy the ORDER BY constraint.

1398 */

1399 return 0;

1400 }

1401 }

1402 assert( pIdx->aSortOrder!=0 \|\| iColumn==-1 );

1403 assert( pTerm->sortOrder==0 \|\| pTerm->sortOrder==1 );

1404 assert( iSortOrder==0 \|\| iSortOrder==1 );

1405 termSortOrder = iSortOrder ^ pTerm->sortOrder;

1406 if( i>nEqCol ){

1407 if( termSortOrder!=sortOrder ){

1408 /* Indices can only be used if all ORDER BY terms past the

1409 ** equality constraints are all either DESC or ASC. */

1410 return 0;

1411 }

1412 }else{

1413 sortOrder = termSortOrder;

1414 }

1415 j++;

1416 pTerm++;

1417 if( iColumn<0 && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){

1418 /* If the indexed column is the primary key and everything matches

1419 ** so far and none of the ORDER BY terms to the right reference other

1420 ** tables in the join, then we are assured that the index can be used

1421 ** to sort because the primary key is unique and so none of the other

1422 ** columns will make any difference

1423 */

1424 j = nTerm;

1425 }

1426 }

1427

1428 *pbRev = sortOrder!=0;

1429 if( j>=nTerm ){

1430 /* All terms of the ORDER BY clause are covered by this index so

1431 ** this index can be used for sorting. */

1432 return 1;

1433 }

1434 if( pIdx->onError!=OE_None && i==pIdx->nColumn

1435 && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){

1436 /* All terms of this index match some prefix of the ORDER BY clause

1437 ** and the index is UNIQUE and no terms on the tail of the ORDER BY

1438 ** clause reference other tables in a join. If this is all true then

1439 ** the order by clause is superfluous. */

1440 return 1;

1441 }

1442 return 0;

1443 }

1444

1445 /*

1446 ** Prepare a crude estimate of the logarithm of the input value.

1447 ** The results need not be exact. This is only used for estimating

1448 ** the total cost of performing operations with O(logN) or O(NlogN)

1449 ** complexity. Because N is just a guess, it is no great tragedy if

1450 ** logN is a little off.

1451 */

1452 static double estLog(double N){

1453 double logN = 1;

1454 double x = 10;

1455 while( N>x ){

1456 logN += 1;

1457 x *= 10;

1458 }

1459 return logN;

1460 }

1461

1462 /*

1463 ** Two routines for printing the content of an sqlite3_index_info

1464 ** structure. Used for testing and debugging only. If neither

1465 ** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines

1466 ** are no-ops.

1467 */

1468 #if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(SQLITE_DEBUG)

1469 static void TRACE_IDX_INPUTS(sqlite3_index_info *p){

1470 int i;

1471 if( !sqlite3WhereTrace ) return;

1472 for(i=0; i<p->nConstraint; i++){

1473 sqlite3DebugPrintf(" constraint[%d]: col=%d termid=%d op=%d usabled=%d\n",

1474 i,

1475 p->aConstraint[i].iColumn,

1476 p->aConstraint[i].iTermOffset,

1477 p->aConstraint[i].op,

1478 p->aConstraint[i].usable);

1479 }

1480 for(i=0; i<p->nOrderBy; i++){

1481 sqlite3DebugPrintf(" orderby[%d]: col=%d desc=%d\n",

1482 i,

1483 p->aOrderBy[i].iColumn,

1484 p->aOrderBy[i].desc);

1485 }

1486 }

1487 static void TRACE_IDX_OUTPUTS(sqlite3_index_info *p){

1488 int i;

1489 if( !sqlite3WhereTrace ) return;

1490 for(i=0; i<p->nConstraint; i++){

1491 sqlite3DebugPrintf(" usage[%d]: argvIdx=%d omit=%d\n",

1492 i,

1493 p->aConstraintUsage[i].argvIndex,

1494 p->aConstraintUsage[i].omit);

1495 }

1496 sqlite3DebugPrintf(" idxNum=%d\n", p->idxNum);

1497 sqlite3DebugPrintf(" idxStr=%s\n", p->idxStr);

1498 sqlite3DebugPrintf(" orderByConsumed=%d\n", p->orderByConsumed);

1499 sqlite3DebugPrintf(" estimatedCost=%g\n", p->estimatedCost);

1500 }

1501 #else

1502 #define TRACE_IDX_INPUTS(A)

1503 #define TRACE_IDX_OUTPUTS(A)

1504 #endif

1505

1506 /*

1507 ** Required because bestIndex() is called by bestOrClauseIndex()

1508 */

1509 static void bestIndex(

1510 Parse, WhereClause, struct SrcList_item, Bitmask, ExprList, WhereCost*);

1511

1512 /*

1513 ** This routine attempts to find an scanning strategy that can be used

1514 ** to optimize an 'OR' expression that is part of a WHERE clause.

1515 **

1516 ** The table associated with FROM clause term pSrc may be either a

1517 ** regular B-Tree table or a virtual table.

1518 */

1519 static void bestOrClauseIndex(

1520 Parse pParse, / The parsing context */

1521 WhereClause pWC, / The WHERE clause */

1522 struct SrcList_item pSrc, / The FROM clause term to search */

1523 Bitmask notReady, /* Mask of cursors that are not available */

1524 ExprList pOrderBy, / The ORDER BY clause */

1525 WhereCost pCost / Lowest cost query plan */

1526 ){

1527 #ifndef SQLITE_OMIT_OR_OPTIMIZATION

1528 const int iCur = pSrc->iCursor; /* The cursor of the table to be accessed */

1529 const Bitmask maskSrc = getMask(pWC->pMaskSet, iCur); /* Bitmask for pSrc */

1530 WhereTerm * const pWCEnd = &pWC->a[pWC->nTerm]; /* End of pWC->a[] */

1531 WhereTerm pTerm; / A single term of the WHERE clause */

1532

1533 /* Search the WHERE clause terms for a usable WO_OR term. */

1534 for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){

1535 if( pTerm->eOperator==WO_OR

1536 && ((pTerm->prereqAll & ~maskSrc) & notReady)==0

1537 && (pTerm->u.pOrInfo->indexable & maskSrc)!=0

1538 ){

1539 WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;

1540 WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];

1541 WhereTerm *pOrTerm;

1542 int flags = WHERE_MULTI_OR;

1543 double rTotal = 0;

1544 double nRow = 0;

1545 Bitmask used = 0;

1546

1547 for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){

1548 WhereCost sTermCost;

1549 WHERETRACE(("... Multi-index OR testing for term %d of %d....\n",

1550 (pOrTerm - pOrWC->a), (pTerm - pWC->a)

1551 ));

1552 if( pOrTerm->eOperator==WO_AND ){

1553 WhereClause *pAndWC = &pOrTerm->u.pAndInfo->wc;

1554 bestIndex(pParse, pAndWC, pSrc, notReady, 0, &sTermCost);

1555 }else if( pOrTerm->leftCursor==iCur ){

1556 WhereClause tempWC;

1557 tempWC.pParse = pWC->pParse;

1558 tempWC.pMaskSet = pWC->pMaskSet;

1559 tempWC.op = TK_AND;

1560 tempWC.a = pOrTerm;

1561 tempWC.nTerm = 1;

1562 bestIndex(pParse, &tempWC, pSrc, notReady, 0, &sTermCost);

1563 }else{

1564 continue;

1565 }

1566 rTotal += sTermCost.rCost;

1567 nRow += sTermCost.nRow;

1568 used \|= sTermCost.used;

1569 if( rTotal>=pCost->rCost ) break;

1570 }

1571

1572 /* If there is an ORDER BY clause, increase the scan cost to account

1573 ** for the cost of the sort. */

1574 if( pOrderBy!=0 ){

1575 rTotal += nRow*estLog(nRow);

1576 WHERETRACE(("... sorting increases OR cost to %.9g\n", rTotal));

1577 }

1578

1579 /* If the cost of scanning using this OR term for optimization is

1580 ** less than the current cost stored in pCost, replace the contents

1581 ** of pCost. */

1582 WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n", rTotal, nRow));

1583 if( rTotal<pCost->rCost ){

1584 pCost->rCost = rTotal;

1585 pCost->nRow = nRow;

1586 pCost->used = used;

1587 pCost->plan.wsFlags = flags;

1588 pCost->plan.u.pTerm = pTerm;

1589 }

1590 }

1591 }

1592 #endif /* SQLITE_OMIT_OR_OPTIMIZATION */

1593 }

1594

1595 #ifndef SQLITE_OMIT_VIRTUALTABLE

1596 /*

1597 ** Allocate and populate an sqlite3_index_info structure. It is the

1598 ** responsibility of the caller to eventually release the structure

1599 ** by passing the pointer returned by this function to sqlite3_free().

1600 */

1601 static sqlite3_index_info *allocateIndexInfo(

1602 Parse *pParse,

1603 WhereClause *pWC,

1604 struct SrcList_item *pSrc,

1605 ExprList *pOrderBy

1606 ){

1607 int i, j;

1608 int nTerm;

1609 struct sqlite3_index_constraint *pIdxCons;

1610 struct sqlite3_index_orderby *pIdxOrderBy;

1611 struct sqlite3_index_constraint_usage *pUsage;

1612 WhereTerm *pTerm;

1613 int nOrderBy;

1614 sqlite3_index_info *pIdxInfo;

1615

1616 WHERETRACE(("Recomputing index info for %s...\n", pSrc->pTab->zName));

1617

1618 /* Count the number of possible WHERE clause constraints referring

1619 ** to this virtual table */

1620 for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){

1621 if( pTerm->leftCursor != pSrc->iCursor ) continue;

1622 assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );

1623 testcase( pTerm->eOperator==WO_IN );

1624 testcase( pTerm->eOperator==WO_ISNULL );

1625 if( pTerm->eOperator & (WO_IN\|WO_ISNULL) ) continue;

1626 nTerm++;

1627 }

1628

1629 /* If the ORDER BY clause contains only columns in the current

1630 ** virtual table then allocate space for the aOrderBy part of

1631 ** the sqlite3_index_info structure.

1632 */

1633 nOrderBy = 0;

1634 if( pOrderBy ){

1635 for(i=0; i<pOrderBy->nExpr; i++){

1636 Expr *pExpr = pOrderBy->a[i].pExpr;

1637 if( pExpr->op!=TK_COLUMN \|\| pExpr->iTable!=pSrc->iCursor ) break;

1638 }

1639 if( i==pOrderBy->nExpr ){

1640 nOrderBy = pOrderBy->nExpr;

1641 }

1642 }

1643

1644 /* Allocate the sqlite3_index_info structure

1645 */

1646 pIdxInfo = sqlite3DbMallocZero(pParse->db, sizeof(*pIdxInfo)

1647 + (sizeof(pIdxCons) + sizeof(pUsage))*nTerm

1648 + sizeof(pIdxOrderBy)nOrderBy );

1649 if( pIdxInfo==0 ){

1650 sqlite3ErrorMsg(pParse, "out of memory");

1651 /* (double)0 In case of SQLITE_OMIT_FLOATING_POINT... */

1652 return 0;

1653 }

1654

1655 /* Initialize the structure. The sqlite3_index_info structure contains

1656 ** many fields that are declared "const" to prevent xBestIndex from

1657 ** changing them. We have to do some funky casting in order to

1658 ** initialize those fields.

1659 */

1660 pIdxCons = (struct sqlite3_index_constraint*)&pIdxInfo[1];

1661 pIdxOrderBy = (struct sqlite3_index_orderby*)&pIdxCons[nTerm];

1662 pUsage = (struct sqlite3_index_constraint_usage*)&pIdxOrderBy[nOrderBy];

1663 (int)&pIdxInfo->nConstraint = nTerm;

1664 (int)&pIdxInfo->nOrderBy = nOrderBy;

1665 (struct sqlite3_index_constraint*)&pIdxInfo->aConstraint = pIdxCons;

1666 (struct sqlite3_index_orderby*)&pIdxInfo->aOrderBy = pIdxOrderBy;

1667 (struct sqlite3_index_constraint_usage*)&pIdxInfo->aConstraintUsage =

1668 pUsage;

1669

1670 for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){

1671 if( pTerm->leftCursor != pSrc->iCursor ) continue;

1672 assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );

1673 testcase( pTerm->eOperator==WO_IN );

1674 testcase( pTerm->eOperator==WO_ISNULL );

1675 if( pTerm->eOperator & (WO_IN\|WO_ISNULL) ) continue;

1676 pIdxCons[j].iColumn = pTerm->u.leftColumn;

1677 pIdxCons[j].iTermOffset = i;

1678 pIdxCons[j].op = (u8)pTerm->eOperator;

1679 /* The direct assignment in the previous line is possible only because

1680 ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical. The

1681 ** following asserts verify this fact. */

1682 assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ );

1683 assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT );

1684 assert( WO_LE==SQLITE_INDEX_CONSTRAINT_LE );

1685 assert( WO_GT==SQLITE_INDEX_CONSTRAINT_GT );

1686 assert( WO_GE==SQLITE_INDEX_CONSTRAINT_GE );

1687 assert( WO_MATCH==SQLITE_INDEX_CONSTRAINT_MATCH );

1688 assert( pTerm->eOperator & (WO_EQ\|WO_LT\|WO_LE\|WO_GT\|WO_GE\|WO_MATCH) );

1689 j++;

1690 }

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

1692 Expr *pExpr = pOrderBy->a[i].pExpr;

1693 pIdxOrderBy[i].iColumn = pExpr->iColumn;

1694 pIdxOrderBy[i].desc = pOrderBy->a[i].sortOrder;

1695 }

1696

1697 return pIdxInfo;

1698 }

1699

1700 /*

1701 ** The table object reference passed as the second argument to this function

1702 ** must represent a virtual table. This function invokes the xBestIndex()

1703 ** method of the virtual table with the sqlite3_index_info pointer passed

1704 ** as the argument.

1705 **

1706 ** If an error occurs, pParse is populated with an error message and a

1707 ** non-zero value is returned. Otherwise, 0 is returned and the output

1708 ** part of the sqlite3_index_info structure is left populated.

1709 **

1710 ** Whether or not an error is returned, it is the responsibility of the

1711 ** caller to eventually free p->idxStr if p->needToFreeIdxStr indicates

1712 ** that this is required.

1713 */

1714 static int vtabBestIndex(Parse pParse, Table pTab, sqlite3_index_info *p){

1715 sqlite3_vtab *pVtab = sqlite3GetVTable(pParse->db, pTab)->pVtab;

1716 int i;

1717 int rc;

1718

1719 (void)sqlite3SafetyOff(pParse->db);

1720 WHERETRACE(("xBestIndex for %s\n", pTab->zName));

1721 TRACE_IDX_INPUTS(p);

1722 rc = pVtab->pModule->xBestIndex(pVtab, p);

1723 TRACE_IDX_OUTPUTS(p);

1724 (void)sqlite3SafetyOn(pParse->db);

1725

1726 if( rc!=SQLITE_OK ){

1727 if( rc==SQLITE_NOMEM ){

1728 pParse->db->mallocFailed = 1;

1729 }else if( !pVtab->zErrMsg ){

1730 sqlite3ErrorMsg(pParse, "%s", sqlite3ErrStr(rc));

1731 }else{

1732 sqlite3ErrorMsg(pParse, "%s", pVtab->zErrMsg);

1733 }

1734 }

1735 sqlite3DbFree(pParse->db, pVtab->zErrMsg);

1736 pVtab->zErrMsg = 0;

1737

1738 for(i=0; i<p->nConstraint; i++){

1739 if( !p->aConstraint[i].usable && p->aConstraintUsage[i].argvIndex>0 ){

1740 sqlite3ErrorMsg(pParse,

1741 "table %s: xBestIndex returned an invalid plan", pTab->zName);

1742 }

1743 }

1744

1745 return pParse->nErr;

1746 }

1747

1748

1749 /*

1750 ** Compute the best index for a virtual table.

1751 **

1752 ** The best index is computed by the xBestIndex method of the virtual

1753 ** table module. This routine is really just a wrapper that sets up

1754 ** the sqlite3_index_info structure that is used to communicate with

1755 ** xBestIndex.

1756 **

1757 ** In a join, this routine might be called multiple times for the

1758 ** same virtual table. The sqlite3_index_info structure is created

1759 ** and initialized on the first invocation and reused on all subsequent

1760 ** invocations. The sqlite3_index_info structure is also used when

1761 ** code is generated to access the virtual table. The whereInfoDelete()

1762 ** routine takes care of freeing the sqlite3_index_info structure after

1763 ** everybody has finished with it.

1764 */

1765 static void bestVirtualIndex(

1766 Parse pParse, / The parsing context */

1767 WhereClause pWC, / The WHERE clause */

1768 struct SrcList_item pSrc, / The FROM clause term to search */

1769 Bitmask notReady, /* Mask of cursors that are not available */

1770 ExprList pOrderBy, / The order by clause */

1771 WhereCost pCost, / Lowest cost query plan */

1772 sqlite3_index_info *ppIdxInfo / Index information passed to xBestIndex */

1773 ){

1774 Table *pTab = pSrc->pTab;

1775 sqlite3_index_info *pIdxInfo;

1776 struct sqlite3_index_constraint *pIdxCons;

1777 struct sqlite3_index_constraint_usage *pUsage;

1778 WhereTerm *pTerm;

1779 int i, j;

1780 int nOrderBy;

1781

1782 /* Make sure wsFlags is initialized to some sane value. Otherwise, if the

1783 ** malloc in allocateIndexInfo() fails and this function returns leaving

1784 ** wsFlags in an uninitialized state, the caller may behave unpredictably.

1785 */

1786 memset(pCost, 0, sizeof(*pCost));

1787 pCost->plan.wsFlags = WHERE_VIRTUALTABLE;

1788

1789 /* If the sqlite3_index_info structure has not been previously

1790 ** allocated and initialized, then allocate and initialize it now.

1791 */

1792 pIdxInfo = *ppIdxInfo;

1793 if( pIdxInfo==0 ){

1794 *ppIdxInfo = pIdxInfo = allocateIndexInfo(pParse, pWC, pSrc, pOrderBy);

1795 }

1796 if( pIdxInfo==0 ){

1797 return;

1798 }

1799

1800 /* At this point, the sqlite3_index_info structure that pIdxInfo points

1801 ** to will have been initialized, either during the current invocation or

1802 ** during some prior invocation. Now we just have to customize the

1803 ** details of pIdxInfo for the current invocation and pass it to

1804 ** xBestIndex.

1805 */

1806

1807 /* The module name must be defined. Also, by this point there must

1808 ** be a pointer to an sqlite3_vtab structure. Otherwise

1809 ** sqlite3ViewGetColumnNames() would have picked up the error.

1810 */

1811 assert( pTab->azModuleArg && pTab->azModuleArg[0] );

1812 assert( sqlite3GetVTable(pParse->db, pTab) );

1813

1814 /* Set the aConstraint[].usable fields and initialize all

1815 ** output variables to zero.

1816 **

1817 ** aConstraint[].usable is true for constraints where the right-hand

1818 ** side contains only references to tables to the left of the current

1819 ** table. In other words, if the constraint is of the form:

1820 **

1821 ** column = expr

1822 **

1823 ** and we are evaluating a join, then the constraint on column is

1824 ** only valid if all tables referenced in expr occur to the left

1825 ** of the table containing column.

1826 **

1827 ** The aConstraints[] array contains entries for all constraints

1828 ** on the current table. That way we only have to compute it once

1829 ** even though we might try to pick the best index multiple times.

1830 ** For each attempt at picking an index, the order of tables in the

1831 ** join might be different so we have to recompute the usable flag

1832 ** each time.

1833 */

1834 pIdxCons = (struct sqlite3_index_constraint*)&pIdxInfo->aConstraint;

1835 pUsage = pIdxInfo->aConstraintUsage;

1836 for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){

1837 j = pIdxCons->iTermOffset;

1838 pTerm = &pWC->a[j];

1839 pIdxCons->usable = (pTerm->prereqRight&notReady) ? 0 : 1;

1840 }

1841 memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);

1842 if( pIdxInfo->needToFreeIdxStr ){

1843 sqlite3_free(pIdxInfo->idxStr);

1844 }

1845 pIdxInfo->idxStr = 0;

1846 pIdxInfo->idxNum = 0;

1847 pIdxInfo->needToFreeIdxStr = 0;

1848 pIdxInfo->orderByConsumed = 0;

1849 /* ((double)2) In case of SQLITE_OMIT_FLOATING_POINT... */

1850 pIdxInfo->estimatedCost = SQLITE_BIG_DBL / ((double)2);

1851 nOrderBy = pIdxInfo->nOrderBy;

1852 if( !pOrderBy ){

1853 pIdxInfo->nOrderBy = 0;

1854 }

1855

1856 if( vtabBestIndex(pParse, pTab, pIdxInfo) ){

1857 return;

1858 }

1859

1860 pIdxCons = (struct sqlite3_index_constraint*)&pIdxInfo->aConstraint;

1861 for(i=0; i<pIdxInfo->nConstraint; i++){

1862 if( pUsage[i].argvIndex>0 ){

1863 pCost->used \|= pWC->a[pIdxCons[i].iTermOffset].prereqRight;

1864 }

1865 }

1866

1867 /* The cost is not allowed to be larger than SQLITE_BIG_DBL (the

1868 ** inital value of lowestCost in this loop. If it is, then the

1869 ** (cost<lowestCost) test below will never be true.

1870 **

1871 ** Use "(double)2" instead of "2.0" in case OMIT_FLOATING_POINT

1872 ** is defined.

1873 */

1874 if( (SQLITE_BIG_DBL/((double)2))<pIdxInfo->estimatedCost ){

1875 pCost->rCost = (SQLITE_BIG_DBL/((double)2));

1876 }else{

1877 pCost->rCost = pIdxInfo->estimatedCost;

1878 }

1879 pCost->plan.u.pVtabIdx = pIdxInfo;

1880 if( pIdxInfo->orderByConsumed ){

1881 pCost->plan.wsFlags \|= WHERE_ORDERBY;

1882 }

1883 pCost->plan.nEq = 0;

1884 pIdxInfo->nOrderBy = nOrderBy;

1885

1886 /* Try to find a more efficient access pattern by using multiple indexes

1887 ** to optimize an OR expression within the WHERE clause.

1888 */

1889 bestOrClauseIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost);

1890 }

1891 #endif /* SQLITE_OMIT_VIRTUALTABLE */

1892

1893 /*

1894 ** Argument pIdx is a pointer to an index structure that has an array of

1895 ** SQLITE_INDEX_SAMPLES evenly spaced samples of the first indexed column

1896 ** stored in Index.aSample. The domain of values stored in said column

1897 ** may be thought of as divided into (SQLITE_INDEX_SAMPLES+1) regions.

1898 ** Region 0 contains all values smaller than the first sample value. Region

1899 ** 1 contains values larger than or equal to the value of the first sample,

1900 ** but smaller than the value of the second. And so on.

1901 **

1902 ** If successful, this function determines which of the regions value

1903 ** pVal lies in, sets *piRegion to the region index (a value between 0

1904 ** and SQLITE_INDEX_SAMPLES+1, inclusive) and returns SQLITE_OK.

1905 ** Or, if an OOM occurs while converting text values between encodings,

1906 ** SQLITE_NOMEM is returned and *piRegion is undefined.

1907 */

1908 #ifdef SQLITE_ENABLE_STAT2

1909 static int whereRangeRegion(

1910 Parse pParse, / Database connection */

1911 Index pIdx, / Index to consider domain of */

1912 sqlite3_value pVal, / Value to consider */

1913 int piRegion / OUT: Region of domain in which value lies */

1914 ){

1915 if( ALWAYS(pVal) ){

1916 IndexSample *aSample = pIdx->aSample;

1917 int i = 0;

1918 int eType = sqlite3_value_type(pVal);

1919

1920 if( eType==SQLITE_INTEGER \|\| eType==SQLITE_FLOAT ){

1921 double r = sqlite3_value_double(pVal);

1922 for(i=0; i<SQLITE_INDEX_SAMPLES; i++){

1923 if( aSample[i].eType==SQLITE_NULL ) continue;

1924 if( aSample[i].eType>=SQLITE_TEXT \|\| aSample[i].u.r>r ) break;

1925 }

1926 }else{

1927 sqlite3 *db = pParse->db;

1928 CollSeq *pColl;

1929 const u8 *z;

1930 int n;

1931

1932 /* pVal comes from sqlite3ValueFromExpr() so the type cannot be NULL */

1933 assert( eType==SQLITE_TEXT \|\| eType==SQLITE_BLOB );

1934

1935 if( eType==SQLITE_BLOB ){

1936 z = (const u8 *)sqlite3_value_blob(pVal);

1937 pColl = db->pDfltColl;

1938 assert( pColl->enc==SQLITE_UTF8 );

1939 }else{

1940 pColl = sqlite3GetCollSeq(db, SQLITE_UTF8, 0, *pIdx->azColl);

1941 if( pColl==0 ){

1942 sqlite3ErrorMsg(pParse, "no such collation sequence: %s",

1943 *pIdx->azColl);

1944 return SQLITE_ERROR;

1945 }

1946 z = (const u8 *)sqlite3ValueText(pVal, pColl->enc);

1947 if( !z ){

1948 return SQLITE_NOMEM;

1949 }

1950 assert( z && pColl && pColl->xCmp );

1951 }

1952 n = sqlite3ValueBytes(pVal, pColl->enc);

1953

1954 for(i=0; i<SQLITE_INDEX_SAMPLES; i++){

1955 int r;

1956 int eSampletype = aSample[i].eType;

1957 if( eSampletype==SQLITE_NULL \|\| eSampletype<eType ) continue;

1958 if( (eSampletype!=eType) ) break;

1959 if( pColl->enc==SQLITE_UTF8 ){

1960 r = pColl->xCmp(pColl->pUser, aSample[i].nByte, aSample[i].u.z, n, z);

1961 }else{

1962 int nSample;

1963 char *zSample = sqlite3Utf8to16(

1964 db, pColl->enc, aSample[i].u.z, aSample[i].nByte, &nSample

1965 );

1966 if( !zSample ){

1967 assert( db->mallocFailed );

1968 return SQLITE_NOMEM;

1969 }

1970 r = pColl->xCmp(pColl->pUser, nSample, zSample, n, z);

1971 sqlite3DbFree(db, zSample);

1972 }

1973 if( r>0 ) break;

1974 }

1975 }

1976

1977 assert( i>=0 && i<=SQLITE_INDEX_SAMPLES );

1978 *piRegion = i;

1979 }

1980 return SQLITE_OK;

1981 }

1982 #endif /* #ifdef SQLITE_ENABLE_STAT2 */

1983

1984 /*

1985 ** This function is used to estimate the number of rows that will be visited

1986 ** by scanning an index for a range of values. The range may have an upper

1987 ** bound, a lower bound, or both. The WHERE clause terms that set the upper

1988 ** and lower bounds are represented by pLower and pUpper respectively. For

1989 ** example, assuming that index p is on t1(a):

1990 **

1991 ** ... FROM t1 WHERE a > ? AND a < ? ...

1992 ** \|_____\| \|_____\|

1993 ** \| \|

1994 ** pLower pUpper

1995 **

1996 ** If either of the upper or lower bound is not present, then NULL is passed in

1997 ** place of the corresponding WhereTerm.

1998 **

1999 ** The nEq parameter is passed the index of the index column subject to the

2000 ** range constraint. Or, equivalently, the number of equality constraints

2001 ** optimized by the proposed index scan. For example, assuming index p is

2002 ** on t1(a, b), and the SQL query is:

2003 **

2004 ** ... FROM t1 WHERE a = ? AND b > ? AND b < ? ...

2005 **

2006 ** then nEq should be passed the value 1 (as the range restricted column,

2007 ** b, is the second left-most column of the index). Or, if the query is:

2008 **

2009 ** ... FROM t1 WHERE a > ? AND a < ? ...

2010 **

2011 ** then nEq should be passed 0.

2012 **

2013 ** The returned value is an integer between 1 and 100, inclusive. A return

2014 ** value of 1 indicates that the proposed range scan is expected to visit

2015 ** approximately 1/100th (1%) of the rows selected by the nEq equality

2016 ** constraints (if any). A return value of 100 indicates that it is expected

2017 ** that the range scan will visit every row (100%) selected by the equality

2018 ** constraints.

2019 **

2020 ** In the absence of sqlite_stat2 ANALYZE data, each range inequality

2021 ** reduces the search space by 2/3rds. Hence a single constraint (x>?)

2022 ** results in a return of 33 and a range constraint (x>? AND x<?) results

2023 ** in a return of 11.

2024 */

2025 static int whereRangeScanEst(

2026 Parse pParse, / Parsing & code generating context */

2027 Index p, / The index containing the range-compared column; "x" */

2028 int nEq, /* index into p->aCol[] of the range-compared column */

2029 WhereTerm pLower, / Lower bound on the range. ex: "x>123" Might be NULL */

2030 WhereTerm pUpper, / Upper bound on the range. ex: "x<455" Might be NULL */

2031 int piEst / OUT: Return value */

2032 ){

2033 int rc = SQLITE_OK;

2034

2035 #ifdef SQLITE_ENABLE_STAT2

2036 sqlite3 *db = pParse->db;

2037 sqlite3_value *pLowerVal = 0;

2038 sqlite3_value *pUpperVal = 0;

2039

2040 if( nEq==0 && p->aSample ){

2041 int iEst;

2042 int iLower = 0;

2043 int iUpper = SQLITE_INDEX_SAMPLES;

2044 u8 aff = p->pTable->aCol[0].affinity;

2045

2046 if( pLower ){

2047 Expr *pExpr = pLower->pExpr->pRight;

2048 rc = sqlite3ValueFromExpr(db, pExpr, SQLITE_UTF8, aff, &pLowerVal);

2049 }

2050 if( rc==SQLITE_OK && pUpper ){

2051 Expr *pExpr = pUpper->pExpr->pRight;

2052 rc = sqlite3ValueFromExpr(db, pExpr, SQLITE_UTF8, aff, &pUpperVal);

2053 }

2054

2055 if( rc!=SQLITE_OK \|\| (pLowerVal==0 && pUpperVal==0) ){

2056 sqlite3ValueFree(pLowerVal);

2057 sqlite3ValueFree(pUpperVal);

2058 goto range_est_fallback;

2059 }else if( pLowerVal==0 ){

2060 rc = whereRangeRegion(pParse, p, pUpperVal, &iUpper);

2061 if( pLower ) iLower = iUpper/2;

2062 }else if( pUpperVal==0 ){

2063 rc = whereRangeRegion(pParse, p, pLowerVal, &iLower);

2064 if( pUpper ) iUpper = (iLower + SQLITE_INDEX_SAMPLES + 1)/2;

2065 }else{

2066 rc = whereRangeRegion(pParse, p, pUpperVal, &iUpper);

2067 if( rc==SQLITE_OK ){

2068 rc = whereRangeRegion(pParse, p, pLowerVal, &iLower);

2069 }

2070 }

2071

2072 iEst = iUpper - iLower;

2073 testcase( iEst==SQLITE_INDEX_SAMPLES );

2074 assert( iEst<=SQLITE_INDEX_SAMPLES );

2075 if( iEst<1 ){

2076 iEst = 1;

2077 }

2078

2079 sqlite3ValueFree(pLowerVal);

2080 sqlite3ValueFree(pUpperVal);

2081 piEst = (iEst 100)/SQLITE_INDEX_SAMPLES;

2082 return rc;

2083 }

2084 range_est_fallback:

2085 #else

2086 UNUSED_PARAMETER(pParse);

2087 UNUSED_PARAMETER(p);

2088 UNUSED_PARAMETER(nEq);

2089 #endif

2090 assert( pLower \|\| pUpper );

2091 if( pLower && pUpper ){

2092 *piEst = 11;

2093 }else{

2094 *piEst = 33;

2095 }

2096 return rc;

2097 }

2098

2099

2100 /*

2101 ** Find the query plan for accessing a particular table. Write the

2102 ** best query plan and its cost into the WhereCost object supplied as the

2103 ** last parameter.

2104 **

2105 ** The lowest cost plan wins. The cost is an estimate of the amount of

2106 ** CPU and disk I/O need to process the request using the selected plan.

2107 ** Factors that influence cost include:

2108 **

2109 ** * The estimated number of rows that will be retrieved. (The

2110 ** fewer the better.)

2111 **

2112 ** * Whether or not sorting must occur.

2113 **

2114 ** * Whether or not there must be separate lookups in the

2115 ** index and in the main table.

2116 **

2117 ** If there was an INDEXED BY clause (pSrc->pIndex) attached to the table in

2118 ** the SQL statement, then this function only considers plans using the

2119 ** named index. If no such plan is found, then the returned cost is

2120 ** SQLITE_BIG_DBL. If a plan is found that uses the named index,

2121 ** then the cost is calculated in the usual way.

2122 **

2123 ** If a NOT INDEXED clause (pSrc->notIndexed!=0) was attached to the table

2124 ** in the SELECT statement, then no indexes are considered. However, the

2125 ** selected plan may still take advantage of the tables built-in rowid

2126 ** index.

2127 */

2128 static void bestBtreeIndex(

2129 Parse pParse, / The parsing context */

2130 WhereClause pWC, / The WHERE clause */

2131 struct SrcList_item pSrc, / The FROM clause term to search */

2132 Bitmask notReady, /* Mask of cursors that are not available */

2133 ExprList pOrderBy, / The ORDER BY clause */

2134 WhereCost pCost / Lowest cost query plan */

2135 ){

2136 int iCur = pSrc->iCursor; /* The cursor of the table to be accessed */

2137 Index pProbe; / An index we are evaluating */

2138 Index pIdx; / Copy of pProbe, or zero for IPK index */

2139 int eqTermMask; /* Current mask of valid equality operators */

2140 int idxEqTermMask; /* Index mask of valid equality operators */

2141 Index sPk; /* A fake index object for the primary key */

2142 unsigned int aiRowEstPk[2]; /* The aiRowEst[] value for the sPk index */

2143 int aiColumnPk = -1; /* The aColumn[] value for the sPk index */

2144 int wsFlagMask; /* Allowed flags in pCost->plan.wsFlag */

2145

2146 /* Initialize the cost to a worst-case value */

2147 memset(pCost, 0, sizeof(*pCost));

2148 pCost->rCost = SQLITE_BIG_DBL;

2149

2150 /* If the pSrc table is the right table of a LEFT JOIN then we may not

2151 ** use an index to satisfy IS NULL constraints on that table. This is

2152 ** because columns might end up being NULL if the table does not match -

2153 ** a circumstance which the index cannot help us discover. Ticket #2177.

2154 */

2155 if( pSrc->jointype & JT_LEFT ){

2156 idxEqTermMask = WO_EQ\|WO_IN;

2157 }else{

2158 idxEqTermMask = WO_EQ\|WO_IN\|WO_ISNULL;

2159 }

2160

2161 if( pSrc->pIndex ){

2162 /* An INDEXED BY clause specifies a particular index to use */

2163 pIdx = pProbe = pSrc->pIndex;

2164 wsFlagMask = ~(WHERE_ROWID_EQ\|WHERE_ROWID_RANGE);

2165 eqTermMask = idxEqTermMask;

2166 }else{

2167 /* There is no INDEXED BY clause. Create a fake Index object to

2168 ** represent the primary key */

2169 Index pFirst; / Any other index on the table */

2170 memset(&sPk, 0, sizeof(Index));

2171 sPk.nColumn = 1;

2172 sPk.aiColumn = &aiColumnPk;

2173 sPk.aiRowEst = aiRowEstPk;

2174 aiRowEstPk[1] = 1;

2175 sPk.onError = OE_Replace;

2176 sPk.pTable = pSrc->pTab;

2177 pFirst = pSrc->pTab->pIndex;

2178 if( pSrc->notIndexed==0 ){

2179 sPk.pNext = pFirst;

2180 }

2181 /* The aiRowEstPk[0] is an estimate of the total number of rows in the

2182 ** table. Get this information from the ANALYZE information if it is

2183 ** available. If not available, assume the table 1 million rows in size.

2184 */

2185 if( pFirst ){

2186 assert( pFirst->aiRowEst!=0 ); /* Allocated together with pFirst */

2187 aiRowEstPk[0] = pFirst->aiRowEst[0];

2188 }else{

2189 aiRowEstPk[0] = 1000000;

2190 }

2191 pProbe = &sPk;

2192 wsFlagMask = ~(

2193 WHERE_COLUMN_IN\|WHERE_COLUMN_EQ\|WHERE_COLUMN_NULL\|WHERE_COLUMN_RANGE

2194 );

2195 eqTermMask = WO_EQ\|WO_IN;

2196 pIdx = 0;

2197 }

2198

2199 /* Loop over all indices looking for the best one to use

2200 */

2201 for(; pProbe; pIdx=pProbe=pProbe->pNext){

2202 const unsigned int * const aiRowEst = pProbe->aiRowEst;

2203 double cost; /* Cost of using pProbe */

2204 double nRow; /* Estimated number of rows in result set */

2205 int rev; /* True to scan in reverse order */

2206 int wsFlags = 0;

2207 Bitmask used = 0;

2208

2209 /* The following variables are populated based on the properties of

2210 ** scan being evaluated. They are then used to determine the expected

2211 ** cost and number of rows returned.

2212 **

2213 ** nEq:

2214 ** Number of equality terms that can be implemented using the index.

2215 **

2216 ** nInMul:

2217 ** The "in-multiplier". This is an estimate of how many seek operations

2218 ** SQLite must perform on the index in question. For example, if the

2219 ** WHERE clause is:

2220 **

2221 ** WHERE a IN (1, 2, 3) AND b IN (4, 5, 6)

2222 **

2223 ** SQLite must perform 9 lookups on an index on (a, b), so nInMul is

2224 ** set to 9. Given the same schema and either of the following WHERE

2225 ** clauses:

2226 **

2227 ** WHERE a = 1

2228 ** WHERE a >= 2

2229 **

2230 ** nInMul is set to 1.

2231 **

2232 ** If there exists a WHERE term of the form "x IN (SELECT ...)", then

2233 ** the sub-select is assumed to return 25 rows for the purposes of

2234 ** determining nInMul.

2235 **

2236 ** bInEst:

2237 ** Set to true if there was at least one "x IN (SELECT ...)" term used

2238 ** in determining the value of nInMul.

2239 **

2240 ** nBound:

2241 ** An estimate on the amount of the table that must be searched. A

2242 ** value of 100 means the entire table is searched. Range constraints

2243 ** might reduce this to a value less than 100 to indicate that only

2244 ** a fraction of the table needs searching. In the absence of

2245 ** sqlite_stat2 ANALYZE data, a single inequality reduces the search

2246 ** space to 1/3rd its original size. So an x>? constraint reduces

2247 ** nBound to 33. Two constraints (x>? AND x<?) reduce nBound to 11.

2248 **

2249 ** bSort:

2250 ** Boolean. True if there is an ORDER BY clause that will require an

2251 ** external sort (i.e. scanning the index being evaluated will not

2252 ** correctly order records).

2253 **

2254 ** bLookup:

2255 ** Boolean. True if for each index entry visited a lookup on the

2256 ** corresponding table b-tree is required. This is always false

2257 ** for the rowid index. For other indexes, it is true unless all the

2258 ** columns of the table used by the SELECT statement are present in

2259 ** the index (such an index is sometimes described as a covering index).

2260 ** For example, given the index on (a, b), the second of the following

2261 ** two queries requires table b-tree lookups, but the first does not.

2262 **

2263 ** SELECT a, b FROM tbl WHERE a = 1;

2264 ** SELECT a, b, c FROM tbl WHERE a = 1;

2265 */

2266 int nEq;

2267 int bInEst = 0;

2268 int nInMul = 1;

2269 int nBound = 100;

2270 int bSort = 0;

2271 int bLookup = 0;

2272

2273 /* Determine the values of nEq and nInMul */

2274 for(nEq=0; nEq<pProbe->nColumn; nEq++){

2275 WhereTerm pTerm; / A single term of the WHERE clause */

2276 int j = pProbe->aiColumn[nEq];

2277 pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pIdx);

2278 if( pTerm==0 ) break;

2279 wsFlags \|= (WHERE_COLUMN_EQ\|WHERE_ROWID_EQ);

2280 if( pTerm->eOperator & WO_IN ){

2281 Expr *pExpr = pTerm->pExpr;

2282 wsFlags \|= WHERE_COLUMN_IN;

2283 if( ExprHasProperty(pExpr, EP_xIsSelect) ){

2284 nInMul *= 25;

2285 bInEst = 1;

2286 }else if( pExpr->x.pList ){

2287 nInMul *= pExpr->x.pList->nExpr + 1;

2288 }

2289 }else if( pTerm->eOperator & WO_ISNULL ){

2290 wsFlags \|= WHERE_COLUMN_NULL;

2291 }

2292 used \|= pTerm->prereqRight;

2293 }

2294

2295 /* Determine the value of nBound. */

2296 if( nEq<pProbe->nColumn ){

2297 int j = pProbe->aiColumn[nEq];

2298 if( findTerm(pWC, iCur, j, notReady, WO_LT\|WO_LE\|WO_GT\|WO_GE, pIdx) ){

2299 WhereTerm *pTop = findTerm(pWC, iCur, j, notReady, WO_LT\|WO_LE, pIdx);

2300 WhereTerm *pBtm = findTerm(pWC, iCur, j, notReady, WO_GT\|WO_GE, pIdx);

2301 whereRangeScanEst(pParse, pProbe, nEq, pBtm, pTop, &nBound);

2302 if( pTop ){

2303 wsFlags \|= WHERE_TOP_LIMIT;

2304 used \|= pTop->prereqRight;

2305 }

2306 if( pBtm ){

2307 wsFlags \|= WHERE_BTM_LIMIT;

2308 used \|= pBtm->prereqRight;

2309 }

2310 wsFlags \|= (WHERE_COLUMN_RANGE\|WHERE_ROWID_RANGE);

2311 }

2312 }else if( pProbe->onError!=OE_None ){

2313 testcase( wsFlags & WHERE_COLUMN_IN );

2314 testcase( wsFlags & WHERE_COLUMN_NULL );

2315 if( (wsFlags & (WHERE_COLUMN_IN\|WHERE_COLUMN_NULL))==0 ){

2316 wsFlags \|= WHERE_UNIQUE;

2317 }

2318 }

2319

2320 /* If there is an ORDER BY clause and the index being considered will

2321 ** naturally scan rows in the required order, set the appropriate flags

2322 ** in wsFlags. Otherwise, if there is an ORDER BY clause but the index

2323 ** will scan rows in a different order, set the bSort variable. */

2324 if( pOrderBy ){

2325 if( (wsFlags & (WHERE_COLUMN_IN\|WHERE_COLUMN_NULL))==0

2326 && isSortingIndex(pParse,pWC->pMaskSet,pProbe,iCur,pOrderBy,nEq,&rev)

2327 ){

2328 wsFlags \|= WHERE_ROWID_RANGE\|WHERE_COLUMN_RANGE\|WHERE_ORDERBY;

2329 wsFlags \|= (rev ? WHERE_REVERSE : 0);

2330 }else{

2331 bSort = 1;

2332 }

2333 }

2334

2335 /* If currently calculating the cost of using an index (not the IPK

2336 ** index), determine if all required column data may be obtained without

2337 ** seeking to entries in the main table (i.e. if the index is a covering

2338 ** index for this query). If it is, set the WHERE_IDX_ONLY flag in

2339 ** wsFlags. Otherwise, set the bLookup variable to true. */

2340 if( pIdx && wsFlags ){

2341 Bitmask m = pSrc->colUsed;

2342 int j;

2343 for(j=0; j<pIdx->nColumn; j++){

2344 int x = pIdx->aiColumn[j];

2345 if( x<BMS-1 ){

2346 m &= ~(((Bitmask)1)<<x);

2347 }

2348 }

2349 if( m==0 ){

2350 wsFlags \|= WHERE_IDX_ONLY;

2351 }else{

2352 bLookup = 1;

2353 }

2354 }

2355

2356 /**** Begin adding up the cost of using this index (Needs improvements)

2357 **

2358 ** Estimate the number of rows of output. For an IN operator,

2359 ** do not let the estimate exceed half the rows in the table.

2360 */

2361 nRow = (double)(aiRowEst[nEq] * nInMul);

2362 if( bInEst && nRow*2>aiRowEst[0] ){

2363 nRow = aiRowEst[0]/2;

2364 nInMul = (int)(nRow / aiRowEst[nEq]);

2365 }

2366

2367 /* Assume constant cost to access a row and logarithmic cost to

2368 ** do a binary search. Hence, the initial cost is the number of output

2369 ** rows plus log2(table-size) times the number of binary searches.

2370 */

2371 cost = nRow + nInMul*estLog(aiRowEst[0]);

2372

2373 /* Adjust the number of rows and the cost downward to reflect rows

2374 ** that are excluded by range constraints.

2375 */

2376 nRow = (nRow * (double)nBound) / (double)100;

2377 cost = (cost * (double)nBound) / (double)100;

2378

2379 /* Add in the estimated cost of sorting the result

2380 */

2381 if( bSort ){

2382 cost += cost*estLog(cost);

2383 }

2384

2385 /* If all information can be taken directly from the index, we avoid

2386 ** doing table lookups. This reduces the cost by half. (Not really -

2387 ** this needs to be fixed.)

2388 */

2389 if( pIdx && bLookup==0 ){

2390 cost /= (double)2;

2391 }

2392 /** Cost of using this index has now been computed **/

2393

2394 WHERETRACE((

2395 "tbl=%s idx=%s nEq=%d nInMul=%d nBound=%d bSort=%d bLookup=%d"

2396 " wsFlags=%d (nRow=%.2f cost=%.2f)\n",

2397 pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk"),

2398 nEq, nInMul, nBound, bSort, bLookup, wsFlags, nRow, cost

2399 ));

2400

2401 /* If this index is the best we have seen so far, then record this

2402 ** index and its cost in the pCost structure.

2403 */

2404 if( (!pIdx \|\| wsFlags) && cost<pCost->rCost ){

2405 pCost->rCost = cost;

2406 pCost->nRow = nRow;

2407 pCost->used = used;

2408 pCost->plan.wsFlags = (wsFlags&wsFlagMask);

2409 pCost->plan.nEq = nEq;

2410 pCost->plan.u.pIdx = pIdx;

2411 }

2412

2413 /* If there was an INDEXED BY clause, then only that one index is

2414 ** considered. */

2415 if( pSrc->pIndex ) break;

2416

2417 /* Reset masks for the next index in the loop */

2418 wsFlagMask = ~(WHERE_ROWID_EQ\|WHERE_ROWID_RANGE);

2419 eqTermMask = idxEqTermMask;

2420 }

2421

2422 /* If there is no ORDER BY clause and the SQLITE_ReverseOrder flag

2423 ** is set, then reverse the order that the index will be scanned

2424 ** in. This is used for application testing, to help find cases

2425 ** where application behaviour depends on the (undefined) order that

2426 ** SQLite outputs rows in in the absence of an ORDER BY clause. */

2427 if( !pOrderBy && pParse->db->flags & SQLITE_ReverseOrder ){

2428 pCost->plan.wsFlags \|= WHERE_REVERSE;

2429 }

2430

2431 assert( pOrderBy \|\| (pCost->plan.wsFlags&WHERE_ORDERBY)==0 );

2432 assert( pCost->plan.u.pIdx==0 \|\| (pCost->plan.wsFlags&WHERE_ROWID_EQ)==0 );

2433 assert( pSrc->pIndex==0

2434 \|\| pCost->plan.u.pIdx==0

2435 \|\| pCost->plan.u.pIdx==pSrc->pIndex

2436 );

2437

2438 WHERETRACE(("best index is: %s\n",

2439 (pCost->plan.u.pIdx ? pCost->plan.u.pIdx->zName : "ipk")

2440 ));

2441

2442 bestOrClauseIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost);

2443 pCost->plan.wsFlags \|= eqTermMask;

2444 }

2445

2446 /*

2447 ** Find the query plan for accessing table pSrc->pTab. Write the

2448 ** best query plan and its cost into the WhereCost object supplied

2449 ** as the last parameter. This function may calculate the cost of

2450 ** both real and virtual table scans.

2451 */

2452 static void bestIndex(

2453 Parse pParse, / The parsing context */

2454 WhereClause pWC, / The WHERE clause */

2455 struct SrcList_item pSrc, / The FROM clause term to search */

2456 Bitmask notReady, /* Mask of cursors that are not available */

2457 ExprList pOrderBy, / The ORDER BY clause */

2458 WhereCost pCost / Lowest cost query plan */

2459 ){

2460 #ifndef SQLITE_OMIT_VIRTUALTABLE

2461 if( IsVirtual(pSrc->pTab) ){

2462 sqlite3_index_info *p = 0;

2463 bestVirtualIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost, &p);

2464 if( p->needToFreeIdxStr ){

2465 sqlite3_free(p->idxStr);

2466 }

2467 sqlite3DbFree(pParse->db, p);

2468 }else

2469 #endif

2470 {

2471 bestBtreeIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost);

2472 }

2473 }

2474

2475 /*

2476 ** Disable a term in the WHERE clause. Except, do not disable the term

2477 ** if it controls a LEFT OUTER JOIN and it did not originate in the ON

2478 ** or USING clause of that join.

2479 **

2480 ** Consider the term t2.z='ok' in the following queries:

2481 **

2482 ** (1) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok'

2483 ** (2) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok'

2484 ** (3) SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok'

2485 **

2486 ** The t2.z='ok' is disabled in the in (2) because it originates

2487 ** in the ON clause. The term is disabled in (3) because it is not part

2488 ** of a LEFT OUTER JOIN. In (1), the term is not disabled.

2489 **

2490 ** Disabling a term causes that term to not be tested in the inner loop

2491 ** of the join. Disabling is an optimization. When terms are satisfied

2492 ** by indices, we disable them to prevent redundant tests in the inner

2493 ** loop. We would get the correct results if nothing were ever disabled,

2494 ** but joins might run a little slower. The trick is to disable as much

2495 ** as we can without disabling too much. If we disabled in (1), we'd get

2496 ** the wrong answer. See ticket #813.

2497 */

2498 static void disableTerm(WhereLevel pLevel, WhereTerm pTerm){

2499 if( pTerm

2500 && ALWAYS((pTerm->wtFlags & TERM_CODED)==0)

2501 && (pLevel->iLeftJoin==0 \|\| ExprHasProperty(pTerm->pExpr, EP_FromJoin))

2502 ){

2503 pTerm->wtFlags \|= TERM_CODED;

2504 if( pTerm->iParent>=0 ){

2505 WhereTerm *pOther = &pTerm->pWC->a[pTerm->iParent];

2506 if( (--pOther->nChild)==0 ){

2507 disableTerm(pLevel, pOther);

2508 }

2509 }

2510 }

2511 }

2512

2513 /*

2514 ** Code an OP_Affinity opcode to apply the column affinity string zAff

2515 ** to the n registers starting at base.

2516 **

2517 ** Buffer zAff was allocated using sqlite3DbMalloc(). It is the

2518 ** responsibility of this function to arrange for it to be eventually

2519 ** freed using sqlite3DbFree().

2520 */

2521 static void codeApplyAffinity(Parse pParse, int base, int n, char zAff){

2522 Vdbe *v = pParse->pVdbe;

2523 assert( v!=0 );

2524 sqlite3VdbeAddOp2(v, OP_Affinity, base, n);

2525 sqlite3VdbeChangeP4(v, -1, zAff, P4_DYNAMIC);

2526 sqlite3ExprCacheAffinityChange(pParse, base, n);

2527 }

2528

2529

2530 /*

2531 ** Generate code for a single equality term of the WHERE clause. An equality

2532 ** term can be either X=expr or X IN (...). pTerm is the term to be

2533 ** coded.

2534 **

2535 ** The current value for the constraint is left in register iReg.

2536 **

2537 ** For a constraint of the form X=expr, the expression is evaluated and its

2538 ** result is left on the stack. For constraints of the form X IN (...)

2539 ** this routine sets up a loop that will iterate over all values of X.

2540 */

2541 static int codeEqualityTerm(

2542 Parse pParse, / The parsing context */

2543 WhereTerm pTerm, / The term of the WHERE clause to be coded */

2544 WhereLevel pLevel, / When level of the FROM clause we are working on */

2545 int iTarget /* Attempt to leave results in this register */

2546 ){

2547 Expr *pX = pTerm->pExpr;

2548 Vdbe *v = pParse->pVdbe;

2549 int iReg; /* Register holding results */

2550

2551 assert( iTarget>0 );

2552 if( pX->op==TK_EQ ){

2553 iReg = sqlite3ExprCodeTarget(pParse, pX->pRight, iTarget);

2554 }else if( pX->op==TK_ISNULL ){

2555 iReg = iTarget;

2556 sqlite3VdbeAddOp2(v, OP_Null, 0, iReg);

2557 #ifndef SQLITE_OMIT_SUBQUERY

2558 }else{

2559 int eType;

2560 int iTab;

2561 struct InLoop *pIn;

2562

2563 assert( pX->op==TK_IN );

2564 iReg = iTarget;

2565 eType = sqlite3FindInIndex(pParse, pX, 0);

2566 iTab = pX->iTable;

2567 sqlite3VdbeAddOp2(v, OP_Rewind, iTab, 0);

2568 assert( pLevel->plan.wsFlags & WHERE_IN_ABLE );

2569 if( pLevel->u.in.nIn==0 ){

2570 pLevel->addrNxt = sqlite3VdbeMakeLabel(v);

2571 }

2572 pLevel->u.in.nIn++;

2573 pLevel->u.in.aInLoop =

2574 sqlite3DbReallocOrFree(pParse->db, pLevel->u.in.aInLoop,

2575 sizeof(pLevel->u.in.aInLoop[0])*pLevel->u.in.nIn);

2576 pIn = pLevel->u.in.aInLoop;

2577 if( pIn ){

2578 pIn += pLevel->u.in.nIn - 1;

2579 pIn->iCur = iTab;

2580 if( eType==IN_INDEX_ROWID ){

2581 pIn->addrInTop = sqlite3VdbeAddOp2(v, OP_Rowid, iTab, iReg);

2582 }else{

2583 pIn->addrInTop = sqlite3VdbeAddOp3(v, OP_Column, iTab, 0, iReg);

2584 }

2585 sqlite3VdbeAddOp1(v, OP_IsNull, iReg);

2586 }else{

2587 pLevel->u.in.nIn = 0;

2588 }

2589 #endif

2590 }

2591 disableTerm(pLevel, pTerm);

2592 return iReg;

2593 }

2594

2595 /*

2596 ** Generate code that will evaluate all == and IN constraints for an

2597 ** index. The values for all constraints are left on the stack.

2598 **

2599 ** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c).

2600 ** Suppose the WHERE clause is this: a==5 AND b IN (1,2,3) AND c>5 AND c<10

2601 ** The index has as many as three equality constraints, but in this

2602 ** example, the third "c" value is an inequality. So only two

2603 ** constraints are coded. This routine will generate code to evaluate

2604 ** a==5 and b IN (1,2,3). The current values for a and b will be stored

2605 ** in consecutive registers and the index of the first register is returned.

2606 **

2607 ** In the example above nEq==2. But this subroutine works for any value

2608 ** of nEq including 0. If nEq==0, this routine is nearly a no-op.

2609 ** The only thing it does is allocate the pLevel->iMem memory cell.

2610 **

2611 ** This routine always allocates at least one memory cell and returns

2612 ** the index of that memory cell. The code that

2613 ** calls this routine will use that memory cell to store the termination

2614 ** key value of the loop. If one or more IN operators appear, then

2615 ** this routine allocates an additional nEq memory cells for internal

2616 ** use.

2617 **

2618 ** Before returning, *pzAff is set to point to a buffer containing a

2619 ** copy of the column affinity string of the index allocated using

2620 ** sqlite3DbMalloc(). Except, entries in the copy of the string associated

2621 ** with equality constraints that use NONE affinity are set to

2622 ** SQLITE_AFF_NONE. This is to deal with SQL such as the following:

2623 **

2624 ** CREATE TABLE t1(a TEXT PRIMARY KEY, b);

2625 ** SELECT ... FROM t1 AS t2, t1 WHERE t1.a = t2.b;

2626 **

2627 ** In the example above, the index on t1(a) has TEXT affinity. But since

2628 ** the right hand side of the equality constraint (t2.b) has NONE affinity,

2629 ** no conversion should be attempted before using a t2.b value as part of

2630 ** a key to search the index. Hence the first byte in the returned affinity

2631 ** string in this example would be set to SQLITE_AFF_NONE.

2632 */

2633 static int codeAllEqualityTerms(

2634 Parse pParse, / Parsing context */

2635 WhereLevel pLevel, / Which nested loop of the FROM we are coding */

2636 WhereClause pWC, / The WHERE clause */

2637 Bitmask notReady, /* Which parts of FROM have not yet been coded */

2638 int nExtraReg, /* Number of extra registers to allocate */

2639 char *pzAff / OUT: Set to point to affinity string */

2640 ){

2641 int nEq = pLevel->plan.nEq; /* The number of == or IN constraints to code */

2642 Vdbe v = pParse->pVdbe; / The vm under construction */

2643 Index pIdx; / The index being used for this loop */

2644 int iCur = pLevel->iTabCur; /* The cursor of the table */

2645 WhereTerm pTerm; / A single constraint term */

2646 int j; /* Loop counter */

2647 int regBase; /* Base register */

2648 int nReg; /* Number of registers to allocate */

2649 char zAff; / Affinity string to return */

2650

2651 /* This module is only called on query plans that use an index. */

2652 assert( pLevel->plan.wsFlags & WHERE_INDEXED );

2653 pIdx = pLevel->plan.u.pIdx;

2654

2655 /* Figure out how many memory cells we will need then allocate them.

2656 */

2657 regBase = pParse->nMem + 1;

2658 nReg = pLevel->plan.nEq + nExtraReg;

2659 pParse->nMem += nReg;

2660

2661 zAff = sqlite3DbStrDup(pParse->db, sqlite3IndexAffinityStr(v, pIdx));

2662 if( !zAff ){

2663 pParse->db->mallocFailed = 1;

2664 }

2665

2666 /* Evaluate the equality constraints

2667 */

2668 assert( pIdx->nColumn>=nEq );

2669 for(j=0; j<nEq; j++){

2670 int r1;

2671 int k = pIdx->aiColumn[j];

2672 pTerm = findTerm(pWC, iCur, k, notReady, pLevel->plan.wsFlags, pIdx);

2673 if( NEVER(pTerm==0) ) break;

2674 assert( (pTerm->wtFlags & TERM_CODED)==0 );

2675 r1 = codeEqualityTerm(pParse, pTerm, pLevel, regBase+j);

2676 if( r1!=regBase+j ){

2677 if( nReg==1 ){

2678 sqlite3ReleaseTempReg(pParse, regBase);

2679 regBase = r1;

2680 }else{

2681 sqlite3VdbeAddOp2(v, OP_SCopy, r1, regBase+j);

2682 }

2683 }

2684 testcase( pTerm->eOperator & WO_ISNULL );

2685 testcase( pTerm->eOperator & WO_IN );

2686 if( (pTerm->eOperator & (WO_ISNULL\|WO_IN))==0 ){

2687 sqlite3VdbeAddOp2(v, OP_IsNull, regBase+j, pLevel->addrBrk);

2688 if( zAff

2689 && sqlite3CompareAffinity(pTerm->pExpr->pRight, zAff[j])==SQLITE_AFF_NONE

2690 ){

2691 zAff[j] = SQLITE_AFF_NONE;

2692 }

2693 }

2694 }

2695 *pzAff = zAff;

2696 return regBase;

2697 }

2698

2699 /*

2700 ** Generate code for the start of the iLevel-th loop in the WHERE clause

2701 ** implementation described by pWInfo.

2702 */

2703 static Bitmask codeOneLoopStart(

2704 WhereInfo pWInfo, / Complete information about the WHERE clause */

2705 int iLevel, /* Which level of pWInfo->a[] should be coded */

2706 u16 wctrlFlags, /* One of the WHERE_* flags defined in sqliteInt.h */

2707 Bitmask notReady /* Which tables are currently available */

2708 ){

2709 int j, k; /* Loop counters */

2710 int iCur; /* The VDBE cursor for the table */

2711 int addrNxt; /* Where to jump to continue with the next IN case */

2712 int omitTable; /* True if we use the index only */

2713 int bRev; /* True if we need to scan in reverse order */

2714 WhereLevel pLevel; / The where level to be coded */

2715 WhereClause pWC; / Decomposition of the entire WHERE clause */

2716 WhereTerm pTerm; / A WHERE clause term */

2717 Parse pParse; / Parsing context */

2718 Vdbe v; / The prepared stmt under constructions */

2719 struct SrcList_item pTabItem; / FROM clause term being coded */

2720 int addrBrk; /* Jump here to break out of the loop */

2721 int addrCont; /* Jump here to continue with next cycle */

2722 int iRowidReg = 0; /* Rowid is stored in this register, if not zero */

2723 int iReleaseReg = 0; /* Temp register to free before returning */

2724

2725 pParse = pWInfo->pParse;

2726 v = pParse->pVdbe;

2727 pWC = pWInfo->pWC;

2728 pLevel = &pWInfo->a[iLevel];

2729 pTabItem = &pWInfo->pTabList->a[pLevel->iFrom];

2730 iCur = pTabItem->iCursor;

2731 bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0;

2732 omitTable = (pLevel->plan.wsFlags & WHERE_IDX_ONLY)!=0

2733 && (wctrlFlags & WHERE_FORCE_TABLE)==0;

2734

2735 /* Create labels for the "break" and "continue" instructions

2736 ** for the current loop. Jump to addrBrk to break out of a loop.

2737 ** Jump to cont to go immediately to the next iteration of the

2738 ** loop.

2739 **

2740 ** When there is an IN operator, we also have a "addrNxt" label that

2741 ** means to continue with the next IN value combination. When

2742 ** there are no IN operators in the constraints, the "addrNxt" label

2743 ** is the same as "addrBrk".

2744 */

2745 addrBrk = pLevel->addrBrk = pLevel->addrNxt = sqlite3VdbeMakeLabel(v);

2746 addrCont = pLevel->addrCont = sqlite3VdbeMakeLabel(v);

2747

2748 /* If this is the right table of a LEFT OUTER JOIN, allocate and

2749 ** initialize a memory cell that records if this table matches any

2750 ** row of the left table of the join.

2751 */

2752 if( pLevel->iFrom>0 && (pTabItem[0].jointype & JT_LEFT)!=0 ){

2753 pLevel->iLeftJoin = ++pParse->nMem;

2754 sqlite3VdbeAddOp2(v, OP_Integer, 0, pLevel->iLeftJoin);

2755 VdbeComment((v, "init LEFT JOIN no-match flag"));

2756 }

2757

2758 #ifndef SQLITE_OMIT_VIRTUALTABLE

2759 if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){

2760 /* Case 0: The table is a virtual-table. Use the VFilter and VNext

2761 ** to access the data.

2762 */

2763 int iReg; /* P3 Value for OP_VFilter */

2764 sqlite3_index_info *pVtabIdx = pLevel->plan.u.pVtabIdx;

2765 int nConstraint = pVtabIdx->nConstraint;

2766 struct sqlite3_index_constraint_usage *aUsage =

2767 pVtabIdx->aConstraintUsage;

2768 const struct sqlite3_index_constraint *aConstraint =

2769 pVtabIdx->aConstraint;

2770

2771 iReg = sqlite3GetTempRange(pParse, nConstraint+2);

2772 for(j=1; j<=nConstraint; j++){

2773 for(k=0; k<nConstraint; k++){

2774 if( aUsage[k].argvIndex==j ){

2775 int iTerm = aConstraint[k].iTermOffset;

2776 sqlite3ExprCode(pParse, pWC->a[iTerm].pExpr->pRight, iReg+j+1);

2777 break;

2778 }

2779 }

2780 if( k==nConstraint ) break;

2781 }

2782 sqlite3VdbeAddOp2(v, OP_Integer, pVtabIdx->idxNum, iReg);

2783 sqlite3VdbeAddOp2(v, OP_Integer, j-1, iReg+1);

2784 sqlite3VdbeAddOp4(v, OP_VFilter, iCur, addrBrk, iReg, pVtabIdx->idxStr,

2785 pVtabIdx->needToFreeIdxStr ? P4_MPRINTF : P4_STATIC);

2786 pVtabIdx->needToFreeIdxStr = 0;

2787 for(j=0; j<nConstraint; j++){

2788 if( aUsage[j].omit ){

2789 int iTerm = aConstraint[j].iTermOffset;

2790 disableTerm(pLevel, &pWC->a[iTerm]);

2791 }

2792 }

2793 pLevel->op = OP_VNext;

2794 pLevel->p1 = iCur;

2795 pLevel->p2 = sqlite3VdbeCurrentAddr(v);

2796 sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);

2797 }else

2798 #endif /* SQLITE_OMIT_VIRTUALTABLE */

2799

2800 if( pLevel->plan.wsFlags & WHERE_ROWID_EQ ){

2801 /* Case 1: We can directly reference a single row using an

2802 ** equality comparison against the ROWID field. Or

2803 ** we reference multiple rows using a "rowid IN (...)"

2804 ** construct.

2805 */

2806 iReleaseReg = sqlite3GetTempReg(pParse);

2807 pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ\|WO_IN, 0);

2808 assert( pTerm!=0 );

2809 assert( pTerm->pExpr!=0 );

2810 assert( pTerm->leftCursor==iCur );

2811 assert( omitTable==0 );

2812 iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, iReleaseReg);

2813 addrNxt = pLevel->addrNxt;

2814 sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt);

2815 sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, iRowidReg);

2816 sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);

2817 VdbeComment((v, "pk"));

2818 pLevel->op = OP_Noop;

2819 }else if( pLevel->plan.wsFlags & WHERE_ROWID_RANGE ){

2820 /* Case 2: We have an inequality comparison against the ROWID field.

2821 */

2822 int testOp = OP_Noop;

2823 int start;

2824 int memEndValue = 0;

2825 WhereTerm pStart, pEnd;

2826

2827 assert( omitTable==0 );

2828 pStart = findTerm(pWC, iCur, -1, notReady, WO_GT\|WO_GE, 0);

2829 pEnd = findTerm(pWC, iCur, -1, notReady, WO_LT\|WO_LE, 0);

2830 if( bRev ){

2831 pTerm = pStart;

2832 pStart = pEnd;

2833 pEnd = pTerm;

2834 }

2835 if( pStart ){

2836 Expr pX; / The expression that defines the start bound */

2837 int r1, rTemp; /* Registers for holding the start boundary */

2838

2839 /* The following constant maps TK_xx codes into corresponding

2840 ** seek opcodes. It depends on a particular ordering of TK_xx

2841 */

2842 const u8 aMoveOp[] = {

2843 /* TK_GT */ OP_SeekGt,

2844 /* TK_LE */ OP_SeekLe,

2845 /* TK_LT */ OP_SeekLt,

2846 /* TK_GE */ OP_SeekGe

2847 };

2848 assert( TK_LE==TK_GT+1 ); /* Make sure the ordering.. */

2849 assert( TK_LT==TK_GT+2 ); /* ... of the TK_xx values... */

2850 assert( TK_GE==TK_GT+3 ); /* ... is correcct. */

2851

2852 pX = pStart->pExpr;

2853 assert( pX!=0 );

2854 assert( pStart->leftCursor==iCur );

2855 r1 = sqlite3ExprCodeTemp(pParse, pX->pRight, &rTemp);

2856 sqlite3VdbeAddOp3(v, aMoveOp[pX->op-TK_GT], iCur, addrBrk, r1);

2857 VdbeComment((v, "pk"));

2858 sqlite3ExprCacheAffinityChange(pParse, r1, 1);

2859 sqlite3ReleaseTempReg(pParse, rTemp);

2860 disableTerm(pLevel, pStart);

2861 }else{

2862 sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iCur, addrBrk);

2863 }

2864 if( pEnd ){

2865 Expr *pX;

2866 pX = pEnd->pExpr;

2867 assert( pX!=0 );

2868 assert( pEnd->leftCursor==iCur );

2869 memEndValue = ++pParse->nMem;

2870 sqlite3ExprCode(pParse, pX->pRight, memEndValue);

2871 if( pX->op==TK_LT \|\| pX->op==TK_GT ){

2872 testOp = bRev ? OP_Le : OP_Ge;

2873 }else{

2874 testOp = bRev ? OP_Lt : OP_Gt;

2875 }

2876 disableTerm(pLevel, pEnd);

2877 }

2878 start = sqlite3VdbeCurrentAddr(v);

2879 pLevel->op = bRev ? OP_Prev : OP_Next;

2880 pLevel->p1 = iCur;

2881 pLevel->p2 = start;

2882 pLevel->p5 = (pStart==0 && pEnd==0) ?1:0;

2883 if( testOp!=OP_Noop ){

2884 iRowidReg = iReleaseReg = sqlite3GetTempReg(pParse);

2885 sqlite3VdbeAddOp2(v, OP_Rowid, iCur, iRowidReg);

2886 sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);

2887 sqlite3VdbeAddOp3(v, testOp, memEndValue, addrBrk, iRowidReg);

2888 sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC \| SQLITE_JUMPIFNULL);

2889 }

2890 }else if( pLevel->plan.wsFlags & (WHERE_COLUMN_RANGE\|WHERE_COLUMN_EQ) ){

2891 /* Case 3: A scan using an index.

2892 **

2893 ** The WHERE clause may contain zero or more equality

2894 ** terms ("==" or "IN" operators) that refer to the N

2895 ** left-most columns of the index. It may also contain

2896 ** inequality constraints (>, <, >= or <=) on the indexed

2897 ** column that immediately follows the N equalities. Only

2898 ** the right-most column can be an inequality - the rest must

2899 ** use the "==" and "IN" operators. For example, if the

2900 ** index is on (x,y,z), then the following clauses are all

2901 ** optimized:

2902 **

2903 ** x=5

2904 ** x=5 AND y=10

2905 ** x=5 AND y<10

2906 ** x=5 AND y>5 AND y<10

2907 ** x=5 AND y=5 AND z<=10

2908 **

2909 ** The z<10 term of the following cannot be used, only

2910 ** the x=5 term:

2911 **

2912 ** x=5 AND z<10

2913 **

2914 ** N may be zero if there are inequality constraints.

2915 ** If there are no inequality constraints, then N is at

2916 ** least one.

2917 **

2918 ** This case is also used when there are no WHERE clause

2919 ** constraints but an index is selected anyway, in order

2920 ** to force the output order to conform to an ORDER BY.

2921 */

2922 int aStartOp[] = {

2923 0,

2924 0,

2925 OP_Rewind, /* 2: (!start_constraints && startEq && !bRev) */

2926 OP_Last, /* 3: (!start_constraints && startEq && bRev) */

2927 OP_SeekGt, /* 4: (start_constraints && !startEq && !bRev) */

2928 OP_SeekLt, /* 5: (start_constraints && !startEq && bRev) */

2929 OP_SeekGe, /* 6: (start_constraints && startEq && !bRev) */

2930 OP_SeekLe /* 7: (start_constraints && startEq && bRev) */

2931 };

2932 int aEndOp[] = {

2933 OP_Noop, /* 0: (!end_constraints) */

2934 OP_IdxGE, /* 1: (end_constraints && !bRev) */

2935 OP_IdxLT /* 2: (end_constraints && bRev) */

2936 };

2937 int nEq = pLevel->plan.nEq;

2938 int isMinQuery = 0; /* If this is an optimized SELECT min(x).. */

2939 int regBase; /* Base register holding constraint values */

2940 int r1; /* Temp register */

2941 WhereTerm pRangeStart = 0; / Inequality constraint at range start */

2942 WhereTerm pRangeEnd = 0; / Inequality constraint at range end */

2943 int startEq; /* True if range start uses ==, >= or <= */

2944 int endEq; /* True if range end uses ==, >= or <= */

2945 int start_constraints; /* Start of range is constrained */

2946 int nConstraint; /* Number of constraint terms */

2947 Index pIdx; / The index we will be using */

2948 int iIdxCur; /* The VDBE cursor for the index */

2949 int nExtraReg = 0; /* Number of extra registers needed */

2950 int op; /* Instruction opcode */

2951 char *zAff;

2952

2953 pIdx = pLevel->plan.u.pIdx;

2954 iIdxCur = pLevel->iIdxCur;

2955 k = pIdx->aiColumn[nEq]; /* Column for inequality constraints */

2956

2957 /* If this loop satisfies a sort order (pOrderBy) request that

2958 ** was passed to this function to implement a "SELECT min(x) ..."

2959 ** query, then the caller will only allow the loop to run for

2960 ** a single iteration. This means that the first row returned

2961 ** should not have a NULL value stored in 'x'. If column 'x' is

2962 ** the first one after the nEq equality constraints in the index,

2963 ** this requires some special handling.

2964 */

2965 if( (wctrlFlags&WHERE_ORDERBY_MIN)!=0

2966 && (pLevel->plan.wsFlags&WHERE_ORDERBY)

2967 && (pIdx->nColumn>nEq)

2968 ){

2969 /* assert( pOrderBy->nExpr==1 ); */

2970 /* assert( pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq] ); */

2971 isMinQuery = 1;

2972 nExtraReg = 1;

2973 }

2974

2975 /* Find any inequality constraint terms for the start and end

2976 ** of the range.

2977 */

2978 if( pLevel->plan.wsFlags & WHERE_TOP_LIMIT ){

2979 pRangeEnd = findTerm(pWC, iCur, k, notReady, (WO_LT\|WO_LE), pIdx);

2980 nExtraReg = 1;

2981 }

2982 if( pLevel->plan.wsFlags & WHERE_BTM_LIMIT ){

2983 pRangeStart = findTerm(pWC, iCur, k, notReady, (WO_GT\|WO_GE), pIdx);

2984 nExtraReg = 1;

2985 }

2986

2987 /* Generate code to evaluate all constraint terms using == or IN

2988 ** and store the values of those terms in an array of registers

2989 ** starting at regBase.

2990 */

2991 regBase = codeAllEqualityTerms(

2992 pParse, pLevel, pWC, notReady, nExtraReg, &zAff

2993 );

2994 addrNxt = pLevel->addrNxt;

2995

2996 /* If we are doing a reverse order scan on an ascending index, or

2997 ** a forward order scan on a descending index, interchange the

2998 ** start and end terms (pRangeStart and pRangeEnd).

2999 */

3000 if( bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC) ){

3001 SWAP(WhereTerm *, pRangeEnd, pRangeStart);

3002 }

3003

3004 testcase( pRangeStart && pRangeStart->eOperator & WO_LE );

3005 testcase( pRangeStart && pRangeStart->eOperator & WO_GE );

3006 testcase( pRangeEnd && pRangeEnd->eOperator & WO_LE );

3007 testcase( pRangeEnd && pRangeEnd->eOperator & WO_GE );

3008 startEq = !pRangeStart \|\| pRangeStart->eOperator & (WO_LE\|WO_GE);

3009 endEq = !pRangeEnd \|\| pRangeEnd->eOperator & (WO_LE\|WO_GE);

3010 start_constraints = pRangeStart \|\| nEq>0;

3011

3012 /* Seek the index cursor to the start of the range. */

3013 nConstraint = nEq;

3014 if( pRangeStart ){

3015 Expr *pRight = pRangeStart->pExpr->pRight;

3016 sqlite3ExprCode(pParse, pRight, regBase+nEq);

3017 sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt);

3018 if( zAff

3019 && sqlite3CompareAffinity(pRight, zAff[nConstraint])==SQLITE_AFF_NONE

3020 ){

3021 /* Since the comparison is to be performed with no conversions applied

3022 ** to the operands, set the affinity to apply to pRight to

3023 ** SQLITE_AFF_NONE. */

3024 zAff[nConstraint] = SQLITE_AFF_NONE;

3025 }

3026 nConstraint++;

3027 }else if( isMinQuery ){

3028 sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);

3029 nConstraint++;

3030 startEq = 0;

3031 start_constraints = 1;

3032 }

3033 codeApplyAffinity(pParse, regBase, nConstraint, zAff);

3034 op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev];

3035 assert( op!=0 );

3036 testcase( op==OP_Rewind );

3037 testcase( op==OP_Last );

3038 testcase( op==OP_SeekGt );

3039 testcase( op==OP_SeekGe );

3040 testcase( op==OP_SeekLe );

3041 testcase( op==OP_SeekLt );

3042 sqlite3VdbeAddOp4(v, op, iIdxCur, addrNxt, regBase,

3043 SQLITE_INT_TO_PTR(nConstraint), P4_INT32);

3044

3045 /* Load the value for the inequality constraint at the end of the

3046 ** range (if any).

3047 */

3048 nConstraint = nEq;

3049 if( pRangeEnd ){

3050 Expr *pRight = pRangeEnd->pExpr->pRight;

3051 sqlite3ExprCacheRemove(pParse, regBase+nEq);

3052 sqlite3ExprCode(pParse, pRight, regBase+nEq);

3053 sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt);

3054 zAff = sqlite3DbStrDup(pParse->db, zAff);

3055 if( zAff

3056 && sqlite3CompareAffinity(pRight, zAff[nConstraint])==SQLITE_AFF_NONE

3057 ){

3058 /* Since the comparison is to be performed with no conversions applied

3059 ** to the operands, set the affinity to apply to pRight to

3060 ** SQLITE_AFF_NONE. */

3061 zAff[nConstraint] = SQLITE_AFF_NONE;

3062 }

3063 codeApplyAffinity(pParse, regBase, nEq+1, zAff);

3064 nConstraint++;

3065 }

3066

3067 /* Top of the loop body */

3068 pLevel->p2 = sqlite3VdbeCurrentAddr(v);

3069

3070 /* Check if the index cursor is past the end of the range. */

3071 op = aEndOp[(pRangeEnd \|\| nEq) * (1 + bRev)];

3072 testcase( op==OP_Noop );

3073 testcase( op==OP_IdxGE );

3074 testcase( op==OP_IdxLT );

3075 if( op!=OP_Noop ){

3076 sqlite3VdbeAddOp4(v, op, iIdxCur, addrNxt, regBase,

3077 SQLITE_INT_TO_PTR(nConstraint), P4_INT32);

3078 sqlite3VdbeChangeP5(v, endEq!=bRev ?1:0);

3079 }

3080

3081 /* If there are inequality constraints, check that the value

3082 ** of the table column that the inequality contrains is not NULL.

3083 ** If it is, jump to the next iteration of the loop.

3084 */

3085 r1 = sqlite3GetTempReg(pParse);

3086 testcase( pLevel->plan.wsFlags & WHERE_BTM_LIMIT );

3087 testcase( pLevel->plan.wsFlags & WHERE_TOP_LIMIT );

3088 if( pLevel->plan.wsFlags & (WHERE_BTM_LIMIT\|WHERE_TOP_LIMIT) ){

3089 sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, nEq, r1);

3090 sqlite3VdbeAddOp2(v, OP_IsNull, r1, addrCont);

3091 }

3092 sqlite3ReleaseTempReg(pParse, r1);

3093

3094 /* Seek the table cursor, if required */

3095 disableTerm(pLevel, pRangeStart);

3096 disableTerm(pLevel, pRangeEnd);

3097 if( !omitTable ){

3098 iRowidReg = iReleaseReg = sqlite3GetTempReg(pParse);

3099 sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, iRowidReg);

3100 sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);

3101 sqlite3VdbeAddOp2(v, OP_Seek, iCur, iRowidReg); /* Deferred seek */

3102 }

3103

3104 /* Record the instruction used to terminate the loop. Disable

3105 ** WHERE clause terms made redundant by the index range scan.

3106 */

3107 pLevel->op = bRev ? OP_Prev : OP_Next;

3108 pLevel->p1 = iIdxCur;

3109 }else

3110

3111 #ifndef SQLITE_OMIT_OR_OPTIMIZATION

3112 if( pLevel->plan.wsFlags & WHERE_MULTI_OR ){

3113 /* Case 4: Two or more separately indexed terms connected by OR

3114 **

3115 ** Example:

3116 **

3117 ** CREATE TABLE t1(a,b,c,d);

3118 ** CREATE INDEX i1 ON t1(a);

3119 ** CREATE INDEX i2 ON t1(b);

3120 ** CREATE INDEX i3 ON t1(c);

3121 **

3122 ** SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)

3123 **

3124 ** In the example, there are three indexed terms connected by OR.

3125 ** The top of the loop looks like this:

3126 **

3127 ** Null 1 # Zero the rowset in reg 1

3128 **

3129 ** Then, for each indexed term, the following. The arguments to

3130 ** RowSetTest are such that the rowid of the current row is inserted

3131 ** into the RowSet. If it is already present, control skips the

3132 ** Gosub opcode and jumps straight to the code generated by WhereEnd().

3133 **

3134 ** sqlite3WhereBegin(<term>)

3135 ** RowSetTest # Insert rowid into rowset

3136 ** Gosub 2 A

3137 ** sqlite3WhereEnd()

3138 **

3139 ** Following the above, code to terminate the loop. Label A, the target

3140 ** of the Gosub above, jumps to the instruction right after the Goto.

3141 **

3142 ** Null 1 # Zero the rowset in reg 1

3143 ** Goto B # The loop is finished.

3144 **

3145 ** A: <loop body> # Return data, whatever.

3146 **

3147 ** Return 2 # Jump back to the Gosub

3148 **

3149 ** B: <after the loop>

3150 **

3151 */

3152 WhereClause pOrWc; / The OR-clause broken out into subterms */

3153 WhereTerm pFinal; / Final subterm within the OR-clause. */

3154 SrcList oneTab; /* Shortened table list */

3155

3156 int regReturn = ++pParse->nMem; /* Register used with OP_Gosub */

3157 int regRowset = 0; /* Register for RowSet object */

3158 int regRowid = 0; /* Register holding rowid */

3159 int iLoopBody = sqlite3VdbeMakeLabel(v); /* Start of loop body */

3160 int iRetInit; /* Address of regReturn init */

3161 int ii;

3162

3163 pTerm = pLevel->plan.u.pTerm;

3164 assert( pTerm!=0 );

3165 assert( pTerm->eOperator==WO_OR );

3166 assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );

3167 pOrWc = &pTerm->u.pOrInfo->wc;

3168 pFinal = &pOrWc->a[pOrWc->nTerm-1];

3169

3170 /* Set up a SrcList containing just the table being scanned by this loop. */

3171 oneTab.nSrc = 1;

3172 oneTab.nAlloc = 1;

3173 oneTab.a[0] = *pTabItem;

3174

3175 /* Initialize the rowset register to contain NULL. An SQL NULL is

3176 ** equivalent to an empty rowset.

3177 **

3178 ** Also initialize regReturn to contain the address of the instruction

3179 ** immediately following the OP_Return at the bottom of the loop. This

3180 ** is required in a few obscure LEFT JOIN cases where control jumps

3181 ** over the top of the loop into the body of it. In this case the

3182 ** correct response for the end-of-loop code (the OP_Return) is to

3183 ** fall through to the next instruction, just as an OP_Next does if

3184 ** called on an uninitialized cursor.

3185 */

3186 if( (wctrlFlags & WHERE_DUPLICATES_OK)==0 ){

3187 regRowset = ++pParse->nMem;

3188 regRowid = ++pParse->nMem;

3189 sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset);

3190 }

3191 iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, regReturn);

3192

3193 for(ii=0; ii<pOrWc->nTerm; ii++){

3194 WhereTerm *pOrTerm = &pOrWc->a[ii];

3195 if( pOrTerm->leftCursor==iCur \|\| pOrTerm->eOperator==WO_AND ){

3196 WhereInfo pSubWInfo; / Info for single OR-term scan */

3197 /* Loop through table entries that match term pOrTerm. */

3198 pSubWInfo = sqlite3WhereBegin(pParse, &oneTab, pOrTerm->pExpr, 0,

3199 WHERE_OMIT_OPEN \| WHERE_OMIT_CLOSE \| WHERE_FORCE_TABLE);

3200 if( pSubWInfo ){

3201 if( (wctrlFlags & WHERE_DUPLICATES_OK)==0 ){

3202 int iSet = ((ii==pOrWc->nTerm-1)?-1:ii);

3203 int r;

3204 r = sqlite3ExprCodeGetColumn(pParse, pTabItem->pTab, -1, iCur,

3205 regRowid, 0);

3206 sqlite3VdbeAddOp4(v, OP_RowSetTest, regRowset,

3207 sqlite3VdbeCurrentAddr(v)+2,

3208 r, SQLITE_INT_TO_PTR(iSet), P4_INT32);

3209 }

3210 sqlite3VdbeAddOp2(v, OP_Gosub, regReturn, iLoopBody);

3211

3212 /* Finish the loop through table entries that match term pOrTerm. */

3213 sqlite3WhereEnd(pSubWInfo);

3214 }

3215 }

3216 }

3217 sqlite3VdbeChangeP1(v, iRetInit, sqlite3VdbeCurrentAddr(v));

3218 /* sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset); */

3219 sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrBrk);

3220 sqlite3VdbeResolveLabel(v, iLoopBody);

3221

3222 pLevel->op = OP_Return;

3223 pLevel->p1 = regReturn;

3224 disableTerm(pLevel, pTerm);

3225 }else

3226 #endif /* SQLITE_OMIT_OR_OPTIMIZATION */

3227

3228 {

3229 /* Case 5: There is no usable index. We must do a complete

3230 ** scan of the entire table.

3231 */

3232 static const u8 aStep[] = { OP_Next, OP_Prev };

3233 static const u8 aStart[] = { OP_Rewind, OP_Last };

3234 assert( bRev==0 \|\| bRev==1 );

3235 assert( omitTable==0 );

3236 pLevel->op = aStep[bRev];

3237 pLevel->p1 = iCur;

3238 pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk);

3239 pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;

3240 }

3241 notReady &= ~getMask(pWC->pMaskSet, iCur);

3242

3243 /* Insert code to test every subexpression that can be completely

3244 ** computed using the current set of tables.

3245 */

3246 k = 0;

3247 for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){

3248 Expr *pE;

3249 testcase( pTerm->wtFlags & TERM_VIRTUAL );

3250 testcase( pTerm->wtFlags & TERM_CODED );

3251 if( pTerm->wtFlags & (TERM_VIRTUAL\|TERM_CODED) ) continue;

3252 if( (pTerm->prereqAll & notReady)!=0 ) continue;

3253 pE = pTerm->pExpr;

3254 assert( pE!=0 );

3255 if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){

3256 continue;

3257 }

3258 sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL);

3259 k = 1;

3260 pTerm->wtFlags \|= TERM_CODED;

3261 }

3262

3263 /* For a LEFT OUTER JOIN, generate code that will record the fact that

3264 ** at least one row of the right table has matched the left table.

3265 */

3266 if( pLevel->iLeftJoin ){

3267 pLevel->addrFirst = sqlite3VdbeCurrentAddr(v);

3268 sqlite3VdbeAddOp2(v, OP_Integer, 1, pLevel->iLeftJoin);

3269 VdbeComment((v, "record LEFT JOIN hit"));

3270 sqlite3ExprCacheClear(pParse);

3271 for(pTerm=pWC->a, j=0; j<pWC->nTerm; j++, pTerm++){

3272 testcase( pTerm->wtFlags & TERM_VIRTUAL );

3273 testcase( pTerm->wtFlags & TERM_CODED );

3274 if( pTerm->wtFlags & (TERM_VIRTUAL\|TERM_CODED) ) continue;

3275 if( (pTerm->prereqAll & notReady)!=0 ) continue;

3276 assert( pTerm->pExpr );

3277 sqlite3ExprIfFalse(pParse, pTerm->pExpr, addrCont, SQLITE_JUMPIFNULL);

3278 pTerm->wtFlags \|= TERM_CODED;

3279 }

3280 }

3281 sqlite3ReleaseTempReg(pParse, iReleaseReg);

3282

3283 return notReady;

3284 }

3285

3286 #if defined(SQLITE_TEST)

3287 /*

3288 ** The following variable holds a text description of query plan generated

3289 ** by the most recent call to sqlite3WhereBegin(). Each call to WhereBegin

3290 ** overwrites the previous. This information is used for testing and

3291 ** analysis only.

3292 */

3293 char sqlite3_query_plan[BMS240]; /* Text of the join */

3294 static int nQPlan = 0; /* Next free slow in _query_plan[] */

3295

3296 #endif /* SQLITE_TEST */

3297

3298

3299 /*

3300 ** Free a WhereInfo structure

3301 */

3302 static void whereInfoFree(sqlite3 db, WhereInfo pWInfo){

3303 if( pWInfo ){

3304 int i;

3305 for(i=0; i<pWInfo->nLevel; i++){

3306 sqlite3_index_info *pInfo = pWInfo->a[i].pIdxInfo;

3307 if( pInfo ){

3308 /* assert( pInfo->needToFreeIdxStr==0 \|\| db->mallocFailed ); */

3309 if( pInfo->needToFreeIdxStr ){

3310 sqlite3_free(pInfo->idxStr);

3311 }

3312 sqlite3DbFree(db, pInfo);

3313 }

3314 }

3315 whereClauseClear(pWInfo->pWC);

3316 sqlite3DbFree(db, pWInfo);

3317 }

3318 }

3319

3320

3321 /*

3322 ** Generate the beginning of the loop used for WHERE clause processing.

3323 ** The return value is a pointer to an opaque structure that contains

3324 ** information needed to terminate the loop. Later, the calling routine

3325 ** should invoke sqlite3WhereEnd() with the return value of this function

3326 ** in order to complete the WHERE clause processing.

3327 **

3328 ** If an error occurs, this routine returns NULL.

3329 **

3330 ** The basic idea is to do a nested loop, one loop for each table in

3331 ** the FROM clause of a select. (INSERT and UPDATE statements are the

3332 ** same as a SELECT with only a single table in the FROM clause.) For

3333 ** example, if the SQL is this:

3334 **

3335 ** SELECT * FROM t1, t2, t3 WHERE ...;

3336 **

3337 ** Then the code generated is conceptually like the following:

3338 **

3339 ** foreach row1 in t1 do \ Code generated

3340 ** foreach row2 in t2 do \|-- by sqlite3WhereBegin()

3341 ** foreach row3 in t3 do /

3342 ** ...

3343 ** end \ Code generated

3344 ** end \|-- by sqlite3WhereEnd()

3345 ** end /

3346 **

3347 ** Note that the loops might not be nested in the order in which they

3348 ** appear in the FROM clause if a different order is better able to make

3349 ** use of indices. Note also that when the IN operator appears in

3350 ** the WHERE clause, it might result in additional nested loops for

3351 ** scanning through all values on the right-hand side of the IN.

3352 **

3353 ** There are Btree cursors associated with each table. t1 uses cursor

3354 ** number pTabList->a[0].iCursor. t2 uses the cursor pTabList->a[1].iCursor.

3355 ** And so forth. This routine generates code to open those VDBE cursors

3356 ** and sqlite3WhereEnd() generates the code to close them.

3357 **

3358 ** The code that sqlite3WhereBegin() generates leaves the cursors named

3359 ** in pTabList pointing at their appropriate entries. The [...] code

3360 ** can use OP_Column and OP_Rowid opcodes on these cursors to extract

3361 ** data from the various tables of the loop.

3362 **

3363 ** If the WHERE clause is empty, the foreach loops must each scan their

3364 ** entire tables. Thus a three-way join is an O(N^3) operation. But if

3365 ** the tables have indices and there are terms in the WHERE clause that

3366 ** refer to those indices, a complete table scan can be avoided and the

3367 ** code will run much faster. Most of the work of this routine is checking

3368 ** to see if there are indices that can be used to speed up the loop.

3369 **

3370 ** Terms of the WHERE clause are also used to limit which rows actually

3371 ** make it to the "..." in the middle of the loop. After each "foreach",

3372 ** terms of the WHERE clause that use only terms in that loop and outer

3373 ** loops are evaluated and if false a jump is made around all subsequent

3374 ** inner loops (or around the "..." if the test occurs within the inner-

3375 ** most loop)

3376 **

3377 ** OUTER JOINS

3378 **

3379 ** An outer join of tables t1 and t2 is conceptally coded as follows:

3380 **

3381 ** foreach row1 in t1 do

3382 ** flag = 0

3383 ** foreach row2 in t2 do

3384 ** start:

3385 ** ...

3386 ** flag = 1

3387 ** end

3388 ** if flag==0 then

3389 ** move the row2 cursor to a null row

3390 ** goto start

3391 ** fi

3392 ** end

3393 **

3394 ** ORDER BY CLAUSE PROCESSING

3395 **

3396 ** *ppOrderBy is a pointer to the ORDER BY clause of a SELECT statement,

3397 ** if there is one. If there is no ORDER BY clause or if this routine

3398 ** is called from an UPDATE or DELETE statement, then ppOrderBy is NULL.

3399 **

3400 ** If an index can be used so that the natural output order of the table

3401 ** scan is correct for the ORDER BY clause, then that index is used and

3402 ** *ppOrderBy is set to NULL. This is an optimization that prevents an

3403 ** unnecessary sort of the result set if an index appropriate for the

3404 ** ORDER BY clause already exists.

3405 **

3406 ** If the where clause loops cannot be arranged to provide the correct

3407 ** output order, then the *ppOrderBy is unchanged.

3408 */

3409 WhereInfo *sqlite3WhereBegin(

3410 Parse pParse, / The parser context */

3411 SrcList pTabList, / A list of all tables to be scanned */

3412 Expr pWhere, / The WHERE clause */

3413 ExprList *ppOrderBy, / An ORDER BY clause, or NULL */

3414 u16 wctrlFlags /* One of the WHERE_* flags defined in sqliteInt.h */

3415 ){

3416 int i; /* Loop counter */

3417 int nByteWInfo; /* Num. bytes allocated for WhereInfo struct */

3418 WhereInfo pWInfo; / Will become the return value of this function */

3419 Vdbe v = pParse->pVdbe; / The virtual database engine */

3420 Bitmask notReady; /* Cursors that are not yet positioned */

3421 WhereMaskSet pMaskSet; / The expression mask set */

3422 WhereClause pWC; / Decomposition of the WHERE clause */

3423 struct SrcList_item pTabItem; / A single entry from pTabList */

3424 WhereLevel pLevel; / A single level in the pWInfo list */

3425 int iFrom; /* First unused FROM clause element */

3426 int andFlags; /* AND-ed combination of all pWC->a[].wtFlags */

3427 sqlite3 db; / Database connection */

3428

3429 /* The number of tables in the FROM clause is limited by the number of

3430 ** bits in a Bitmask

3431 */

3432 if( pTabList->nSrc>BMS ){

3433 sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS);

3434 return 0;

3435 }

3436

3437 /* Allocate and initialize the WhereInfo structure that will become the

3438 ** return value. A single allocation is used to store the WhereInfo

3439 ** struct, the contents of WhereInfo.a[], the WhereClause structure

3440 ** and the WhereMaskSet structure. Since WhereClause contains an 8-byte

3441 ** field (type Bitmask) it must be aligned on an 8-byte boundary on

3442 ** some architectures. Hence the ROUND8() below.

3443 */

3444 db = pParse->db;

3445 nByteWInfo = ROUND8(sizeof(WhereInfo)+(pTabList->nSrc-1)*sizeof(WhereLevel));

3446 pWInfo = sqlite3DbMallocZero(db,

3447 nByteWInfo +

3448 sizeof(WhereClause) +

3449 sizeof(WhereMaskSet)

3450 );

3451 if( db->mallocFailed ){

3452 goto whereBeginError;

3453 }

3454 pWInfo->nLevel = pTabList->nSrc;

3455 pWInfo->pParse = pParse;

3456 pWInfo->pTabList = pTabList;

3457 pWInfo->iBreak = sqlite3VdbeMakeLabel(v);

3458 pWInfo->pWC = pWC = (WhereClause )&((u8 )pWInfo)[nByteWInfo];

3459 pWInfo->wctrlFlags = wctrlFlags;

3460 pMaskSet = (WhereMaskSet*)&pWC[1];

3461

3462 /* Split the WHERE clause into separate subexpressions where each

3463 ** subexpression is separated by an AND operator.

3464 */

3465 initMaskSet(pMaskSet);

3466 whereClauseInit(pWC, pParse, pMaskSet);

3467 sqlite3ExprCodeConstants(pParse, pWhere);

3468 whereSplit(pWC, pWhere, TK_AND);

3469

3470 /* Special case: a WHERE clause that is constant. Evaluate the

3471 ** expression and either jump over all of the code or fall thru.

3472 */

3473 if( pWhere && (pTabList->nSrc==0 \|\| sqlite3ExprIsConstantNotJoin(pWhere)) ){

3474 sqlite3ExprIfFalse(pParse, pWhere, pWInfo->iBreak, SQLITE_JUMPIFNULL);

3475 pWhere = 0;

3476 }

3477

3478 /* Assign a bit from the bitmask to every term in the FROM clause.

3479 **

3480 ** When assigning bitmask values to FROM clause cursors, it must be

3481 ** the case that if X is the bitmask for the N-th FROM clause term then

3482 ** the bitmask for all FROM clause terms to the left of the N-th term

3483 ** is (X-1). An expression from the ON clause of a LEFT JOIN can use

3484 ** its Expr.iRightJoinTable value to find the bitmask of the right table

3485 ** of the join. Subtracting one from the right table bitmask gives a

3486 ** bitmask for all tables to the left of the join. Knowing the bitmask

3487 ** for all tables to the left of a left join is important. Ticket #3015.

3488 **

3489 ** Configure the WhereClause.vmask variable so that bits that correspond

3490 ** to virtual table cursors are set. This is used to selectively disable

3491 ** the OR-to-IN transformation in exprAnalyzeOrTerm(). It is not helpful

3492 ** with virtual tables.

3493 */

3494 assert( pWC->vmask==0 && pMaskSet->n==0 );

3495 for(i=0; i<pTabList->nSrc; i++){

3496 createMask(pMaskSet, pTabList->a[i].iCursor);

3497 #ifndef SQLITE_OMIT_VIRTUALTABLE

3498 if( ALWAYS(pTabList->a[i].pTab) && IsVirtual(pTabList->a[i].pTab) ){

3499 pWC->vmask \|= ((Bitmask)1 << i);

3500 }

3501 #endif

3502 }

3503 #ifndef NDEBUG

3504 {

3505 Bitmask toTheLeft = 0;

3506 for(i=0; i<pTabList->nSrc; i++){

3507 Bitmask m = getMask(pMaskSet, pTabList->a[i].iCursor);

3508 assert( (m-1)==toTheLeft );

3509 toTheLeft \|= m;

3510 }

3511 }

3512 #endif

3513

3514 /* Analyze all of the subexpressions. Note that exprAnalyze() might

3515 ** add new virtual terms onto the end of the WHERE clause. We do not

3516 ** want to analyze these virtual terms, so start analyzing at the end

3517 ** and work forward so that the added virtual terms are never processed.

3518 */

3519 exprAnalyzeAll(pTabList, pWC);

3520 if( db->mallocFailed ){

3521 goto whereBeginError;

3522 }

3523

3524 /* Chose the best index to use for each table in the FROM clause.

3525 **

3526 ** This loop fills in the following fields:

3527 **

3528 ** pWInfo->a[].pIdx The index to use for this level of the loop.

3529 ** pWInfo->a[].wsFlags WHERE_xxx flags associated with pIdx

3530 ** pWInfo->a[].nEq The number of == and IN constraints

3531 ** pWInfo->a[].iFrom Which term of the FROM clause is being coded

3532 ** pWInfo->a[].iTabCur The VDBE cursor for the database table

3533 ** pWInfo->a[].iIdxCur The VDBE cursor for the index

3534 ** pWInfo->a[].pTerm When wsFlags==WO_OR, the OR-clause term

3535 **

3536 ** This loop also figures out the nesting order of tables in the FROM

3537 ** clause.

3538 */

3539 notReady = ~(Bitmask)0;

3540 pTabItem = pTabList->a;

3541 pLevel = pWInfo->a;

3542 andFlags = ~0;

3543 WHERETRACE(("* Optimizer Start *\n"));

3544 for(i=iFrom=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){

3545 WhereCost bestPlan; /* Most efficient plan seen so far */

3546 Index pIdx; / Index for FROM table at pTabItem */

3547 int j; /* For looping over FROM tables */

3548 int bestJ = -1; /* The value of j */

3549 Bitmask m; /* Bitmask value for j or bestJ */

3550 int isOptimal; /* Iterator for optimal/non-optimal search */

3551

3552 memset(&bestPlan, 0, sizeof(bestPlan));

3553 bestPlan.rCost = SQLITE_BIG_DBL;

3554

3555 /* Loop through the remaining entries in the FROM clause to find the

3556 ** next nested loop. The FROM clause entries may be iterated through

3557 ** either once or twice.

3558 **

3559 ** The first iteration, which is always performed, searches for the

3560 ** FROM clause entry that permits the lowest-cost, "optimal" scan. In

3561 ** this context an optimal scan is one that uses the same strategy

3562 ** for the given FROM clause entry as would be selected if the entry

3563 ** were used as the innermost nested loop. In other words, a table

3564 ** is chosen such that the cost of running that table cannot be reduced

3565 ** by waiting for other tables to run first.

3566 **

3567 ** The second iteration is only performed if no optimal scan strategies

3568 ** were found by the first. This iteration is used to search for the

3569 ** lowest cost scan overall.

3570 **

3571 ** Previous versions of SQLite performed only the second iteration -

3572 ** the next outermost loop was always that with the lowest overall

3573 ** cost. However, this meant that SQLite could select the wrong plan

3574 ** for scripts such as the following:

3575 **

3576 ** CREATE TABLE t1(a, b);

3577 ** CREATE TABLE t2(c, d);

3578 ** SELECT * FROM t2, t1 WHERE t2.rowid = t1.a;

3579 **

3580 ** The best strategy is to iterate through table t1 first. However it

3581 ** is not possible to determine this with a simple greedy algorithm.

3582 ** However, since the cost of a linear scan through table t2 is the same

3583 ** as the cost of a linear scan through table t1, a simple greedy

3584 ** algorithm may choose to use t2 for the outer loop, which is a much

3585 ** costlier approach.

3586 */

3587 for(isOptimal=1; isOptimal>=0 && bestJ<0; isOptimal--){

3588 Bitmask mask = (isOptimal ? 0 : notReady);

3589 assert( (pTabList->nSrc-iFrom)>1 \|\| isOptimal );

3590 for(j=iFrom, pTabItem=&pTabList->a[j]; j<pTabList->nSrc; j++, pTabItem++){

3591 int doNotReorder; /* True if this table should not be reordered */

3592 WhereCost sCost; /* Cost information from best[Virtual]Index() */

3593 ExprList pOrderBy; / ORDER BY clause for index to optimize */

3594

3595 doNotReorder = (pTabItem->jointype & (JT_LEFT\|JT_CROSS))!=0;

3596 if( j!=iFrom && doNotReorder ) break;

3597 m = getMask(pMaskSet, pTabItem->iCursor);

3598 if( (m & notReady)==0 ){

3599 if( j==iFrom ) iFrom++;

3600 continue;

3601 }

3602 pOrderBy = ((i==0 && ppOrderBy )?*ppOrderBy:0);

3603

3604 assert( pTabItem->pTab );

3605 #ifndef SQLITE_OMIT_VIRTUALTABLE

3606 if( IsVirtual(pTabItem->pTab) ){

3607 sqlite3_index_info **pp = &pWInfo->a[j].pIdxInfo;

3608 bestVirtualIndex(pParse, pWC, pTabItem, mask, pOrderBy, &sCost, pp);

3609 }else

3610 #endif

3611 {

3612 bestBtreeIndex(pParse, pWC, pTabItem, mask, pOrderBy, &sCost);

3613 }

3614 assert( isOptimal \|\| (sCost.used&notReady)==0 );

3615

3616 if( (sCost.used&notReady)==0

3617 && (j==iFrom \|\| sCost.rCost<bestPlan.rCost)

3618 ){

3619 bestPlan = sCost;

3620 bestJ = j;

3621 }

3622 if( doNotReorder ) break;

3623 }

3624 }

3625 assert( bestJ>=0 );

3626 assert( notReady & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );

3627 WHERETRACE(("*** Optimizer selects table %d for loop %d\n", bestJ,

3628 pLevel-pWInfo->a));

3629 if( (bestPlan.plan.wsFlags & WHERE_ORDERBY)!=0 ){

3630 *ppOrderBy = 0;

3631 }

3632 andFlags &= bestPlan.plan.wsFlags;

3633 pLevel->plan = bestPlan.plan;

3634 if( bestPlan.plan.wsFlags & WHERE_INDEXED ){

3635 pLevel->iIdxCur = pParse->nTab++;

3636 }else{

3637 pLevel->iIdxCur = -1;

3638 }

3639 notReady &= ~getMask(pMaskSet, pTabList->a[bestJ].iCursor);

3640 pLevel->iFrom = (u8)bestJ;

3641

3642 /* Check that if the table scanned by this loop iteration had an

3643 ** INDEXED BY clause attached to it, that the named index is being

3644 ** used for the scan. If not, then query compilation has failed.

3645 ** Return an error.

3646 */

3647 pIdx = pTabList->a[bestJ].pIndex;

3648 if( pIdx ){

3649 if( (bestPlan.plan.wsFlags & WHERE_INDEXED)==0 ){

3650 sqlite3ErrorMsg(pParse, "cannot use index: %s", pIdx->zName);

3651 goto whereBeginError;

3652 }else{

3653 /* If an INDEXED BY clause is used, the bestIndex() function is

3654 ** guaranteed to find the index specified in the INDEXED BY clause

3655 ** if it find an index at all. */

3656 assert( bestPlan.plan.u.pIdx==pIdx );

3657 }

3658 }

3659 }

3660 WHERETRACE(("* Optimizer Finished *\n"));

3661 if( pParse->nErr \|\| db->mallocFailed ){

3662 goto whereBeginError;

3663 }

3664

3665 /* If the total query only selects a single row, then the ORDER BY

3666 ** clause is irrelevant.

3667 */

3668 if( (andFlags & WHERE_UNIQUE)!=0 && ppOrderBy ){

3669 *ppOrderBy = 0;

3670 }

3671

3672 /* If the caller is an UPDATE or DELETE statement that is requesting

3673 ** to use a one-pass algorithm, determine if this is appropriate.

3674 ** The one-pass algorithm only works if the WHERE clause constraints

3675 ** the statement to update a single row.

3676 */

3677 assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 \|\| pWInfo->nLevel==1 );

3678 if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_UNIQUE)!=0 ){

3679 pWInfo->okOnePass = 1;

3680 pWInfo->a[0].plan.wsFlags &= ~WHERE_IDX_ONLY;

3681 }

3682

3683 /* Open all tables in the pTabList and any indices selected for

3684 ** searching those tables.

3685 */

3686 sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */

3687 for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){

3688 Table pTab; / Table to open */

3689 int iDb; /* Index of database containing table/index */

3690

3691 #ifndef SQLITE_OMIT_EXPLAIN

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

3693 char *zMsg;

3694 struct SrcList_item *pItem = &pTabList->a[pLevel->iFrom];

3695 zMsg = sqlite3MPrintf(db, "TABLE %s", pItem->zName);

3696 if( pItem->zAlias ){

3697 zMsg = sqlite3MAppendf(db, zMsg, "%s AS %s", zMsg, pItem->zAlias);

3698 }

3699 if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){

3700 zMsg = sqlite3MAppendf(db, zMsg, "%s WITH INDEX %s",

3701 zMsg, pLevel->plan.u.pIdx->zName);

3702 }else if( pLevel->plan.wsFlags & WHERE_MULTI_OR ){

3703 zMsg = sqlite3MAppendf(db, zMsg, "%s VIA MULTI-INDEX UNION", zMsg);

3704 }else if( pLevel->plan.wsFlags & (WHERE_ROWID_EQ\|WHERE_ROWID_RANGE) ){

3705 zMsg = sqlite3MAppendf(db, zMsg, "%s USING PRIMARY KEY", zMsg);

3706 }

3707 #ifndef SQLITE_OMIT_VIRTUALTABLE

3708 else if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){

3709 sqlite3_index_info *pVtabIdx = pLevel->plan.u.pVtabIdx;

3710 zMsg = sqlite3MAppendf(db, zMsg, "%s VIRTUAL TABLE INDEX %d:%s", zMsg,

3711 pVtabIdx->idxNum, pVtabIdx->idxStr);

3712 }

3713 #endif

3714 if( pLevel->plan.wsFlags & WHERE_ORDERBY ){

3715 zMsg = sqlite3MAppendf(db, zMsg, "%s ORDER BY", zMsg);

3716 }

3717 sqlite3VdbeAddOp4(v, OP_Explain, i, pLevel->iFrom, 0, zMsg, P4_DYNAMIC);

3718 }

3719 #endif /* SQLITE_OMIT_EXPLAIN */

3720 pTabItem = &pTabList->a[pLevel->iFrom];

3721 pTab = pTabItem->pTab;

3722 iDb = sqlite3SchemaToIndex(db, pTab->pSchema);

3723 if( (pTab->tabFlags & TF_Ephemeral)!=0 \|\| pTab->pSelect ) continue;

3724 #ifndef SQLITE_OMIT_VIRTUALTABLE

3725 if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){

3726 const char pVTab = (const char )sqlite3GetVTable(db, pTab);

3727 int iCur = pTabItem->iCursor;

3728 sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0, pVTab, P4_VTAB);

3729 }else

3730 #endif

3731 if( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0

3732 && (wctrlFlags & WHERE_OMIT_OPEN)==0 ){

3733 int op = pWInfo->okOnePass ? OP_OpenWrite : OP_OpenRead;

3734 sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, op);

3735 if( !pWInfo->okOnePass && pTab->nCol<BMS ){

3736 Bitmask b = pTabItem->colUsed;

3737 int n = 0;

3738 for(; b; b=b>>1, n++){}

3739 sqlite3VdbeChangeP4(v, sqlite3VdbeCurrentAddr(v)-1, SQLITE_INT_TO_PTR(n) , P4_INT32);

3740 assert( n<=pTab->nCol );

3741 }

3742 }else{

3743 sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);

3744 }

3745 pLevel->iTabCur = pTabItem->iCursor;

3746 if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){

3747 Index *pIx = pLevel->plan.u.pIdx;

3748 KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIx);

3749 int iIdxCur = pLevel->iIdxCur;

3750 assert( pIx->pSchema==pTab->pSchema );

3751 assert( iIdxCur>=0 );

3752 sqlite3VdbeAddOp4(v, OP_OpenRead, iIdxCur, pIx->tnum, iDb,

3753 (char*)pKey, P4_KEYINFO_HANDOFF);

3754 VdbeComment((v, "%s", pIx->zName));

3755 }

3756 sqlite3CodeVerifySchema(pParse, iDb);

3757 }

3758 pWInfo->iTop = sqlite3VdbeCurrentAddr(v);

3759

3760 /* Generate the code to do the search. Each iteration of the for

3761 ** loop below generates code for a single nested loop of the VM

3762 ** program.

3763 */

3764 notReady = ~(Bitmask)0;

3765 for(i=0; i<pTabList->nSrc; i++){

3766 notReady = codeOneLoopStart(pWInfo, i, wctrlFlags, notReady);

3767 pWInfo->iContinue = pWInfo->a[i].addrCont;

3768 }

3769

3770 #ifdef SQLITE_TEST /* For testing and debugging use only */

3771 /* Record in the query plan information about the current table

3772 ** and the index used to access it (if any). If the table itself

3773 ** is not used, its name is just '{}'. If no index is used

3774 ** the index is listed as "{}". If the primary key is used the

3775 ** index name is '*'.

3776 */

3777 for(i=0; i<pTabList->nSrc; i++){

3778 char *z;

3779 int n;

3780 pLevel = &pWInfo->a[i];

3781 pTabItem = &pTabList->a[pLevel->iFrom];

3782 z = pTabItem->zAlias;

3783 if( z==0 ) z = pTabItem->pTab->zName;

3784 n = sqlite3Strlen30(z);

3785 if( n+nQPlan < sizeof(sqlite3_query_plan)-10 ){

3786 if( pLevel->plan.wsFlags & WHERE_IDX_ONLY ){

3787 memcpy(&sqlite3_query_plan[nQPlan], "{}", 2);

3788 nQPlan += 2;

3789 }else{

3790 memcpy(&sqlite3_query_plan[nQPlan], z, n);

3791 nQPlan += n;

3792 }

3793 sqlite3_query_plan[nQPlan++] = ' ';

3794 }

3795 testcase( pLevel->plan.wsFlags & WHERE_ROWID_EQ );

3796 testcase( pLevel->plan.wsFlags & WHERE_ROWID_RANGE );

3797 if( pLevel->plan.wsFlags & (WHERE_ROWID_EQ\|WHERE_ROWID_RANGE) ){

3798 memcpy(&sqlite3_query_plan[nQPlan], "* ", 2);

3799 nQPlan += 2;

3800 }else if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){

3801 n = sqlite3Strlen30(pLevel->plan.u.pIdx->zName);

3802 if( n+nQPlan < sizeof(sqlite3_query_plan)-2 ){

3803 memcpy(&sqlite3_query_plan[nQPlan], pLevel->plan.u.pIdx->zName, n);

3804 nQPlan += n;

3805 sqlite3_query_plan[nQPlan++] = ' ';

3806 }

3807 }else{

3808 memcpy(&sqlite3_query_plan[nQPlan], "{} ", 3);

3809 nQPlan += 3;

3810 }

3811 }

3812 while( nQPlan>0 && sqlite3_query_plan[nQPlan-1]==' ' ){

3813 sqlite3_query_plan[--nQPlan] = 0;

3814 }

3815 sqlite3_query_plan[nQPlan] = 0;

3816 nQPlan = 0;

3817 #endif /* SQLITE_TEST // Testing and debugging use only */

3818

3819 /* Record the continuation address in the WhereInfo structure. Then

3820 ** clean up and return.

3821 */

3822 return pWInfo;

3823

3824 /* Jump here if malloc fails */

3825 whereBeginError:

3826 whereInfoFree(db, pWInfo);

3827 return 0;

3828 }

3829

3830 /*

3831 ** Generate the end of the WHERE loop. See comments on

3832 ** sqlite3WhereBegin() for additional information.

3833 */

3834 void sqlite3WhereEnd(WhereInfo *pWInfo){

3835 Parse *pParse = pWInfo->pParse;

3836 Vdbe *v = pParse->pVdbe;

3837 int i;

3838 WhereLevel *pLevel;

3839 SrcList *pTabList = pWInfo->pTabList;

3840 sqlite3 *db = pParse->db;

3841

3842 /* Generate loop termination code.

3843 */

3844 sqlite3ExprCacheClear(pParse);

3845 for(i=pTabList->nSrc-1; i>=0; i--){

3846 pLevel = &pWInfo->a[i];

3847 sqlite3VdbeResolveLabel(v, pLevel->addrCont);

3848 if( pLevel->op!=OP_Noop ){

3849 sqlite3VdbeAddOp2(v, pLevel->op, pLevel->p1, pLevel->p2);

3850 sqlite3VdbeChangeP5(v, pLevel->p5);

3851 }

3852 if( pLevel->plan.wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){

3853 struct InLoop *pIn;

3854 int j;

3855 sqlite3VdbeResolveLabel(v, pLevel->addrNxt);

3856 for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){

3857 sqlite3VdbeJumpHere(v, pIn->addrInTop+1);

3858 sqlite3VdbeAddOp2(v, OP_Next, pIn->iCur, pIn->addrInTop);

3859 sqlite3VdbeJumpHere(v, pIn->addrInTop-1);

3860 }

3861 sqlite3DbFree(db, pLevel->u.in.aInLoop);

3862 }

3863 sqlite3VdbeResolveLabel(v, pLevel->addrBrk);

3864 if( pLevel->iLeftJoin ){

3865 int addr;

3866 addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin);

3867 sqlite3VdbeAddOp1(v, OP_NullRow, pTabList->a[i].iCursor);

3868 if( pLevel->iIdxCur>=0 ){

3869 sqlite3VdbeAddOp1(v, OP_NullRow, pLevel->iIdxCur);

3870 }

3871 if( pLevel->op==OP_Return ){

3872 sqlite3VdbeAddOp2(v, OP_Gosub, pLevel->p1, pLevel->addrFirst);

3873 }else{

3874 sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrFirst);

3875 }

3876 sqlite3VdbeJumpHere(v, addr);

3877 }

3878 }

3879

3880 /* The "break" point is here, just past the end of the outer loop.

3881 ** Set it.

3882 */

3883 sqlite3VdbeResolveLabel(v, pWInfo->iBreak);

3884

3885 /* Close all of the cursors that were opened by sqlite3WhereBegin.

3886 */

3887 for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){

3888 struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];

3889 Table *pTab = pTabItem->pTab;

3890 assert( pTab!=0 );

3891 if( (pTab->tabFlags & TF_Ephemeral)!=0 \|\| pTab->pSelect ) continue;

3892 if( (pWInfo->wctrlFlags & WHERE_OMIT_CLOSE)==0 ){

3893 if( !pWInfo->okOnePass && (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0 ){

3894 sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor);

3895 }

3896 if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){

3897 sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur);

3898 }

3899 }

3900

3901 /* If this scan uses an index, make code substitutions to read data

3902 ** from the index in preference to the table. Sometimes, this means

3903 ** the table need never be read from. This is a performance boost,

3904 ** as the vdbe level waits until the table is read before actually

3905 ** seeking the table cursor to the record corresponding to the current

3906 ** position in the index.

3907 **

3908 ** Calls to the code generator in between sqlite3WhereBegin and

3909 ** sqlite3WhereEnd will have created code that references the table

3910 ** directly. This loop scans all that code looking for opcodes

3911 ** that reference the table and converts them into opcodes that

3912 ** reference the index.

3913 */

3914 if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 && !db->mallocFailed){

3915 int k, j, last;

3916 VdbeOp *pOp;

3917 Index *pIdx = pLevel->plan.u.pIdx;

3918 int useIndexOnly = pLevel->plan.wsFlags & WHERE_IDX_ONLY;

3919

3920 assert( pIdx!=0 );

3921 pOp = sqlite3VdbeGetOp(v, pWInfo->iTop);

3922 last = sqlite3VdbeCurrentAddr(v);

3923 for(k=pWInfo->iTop; k<last; k++, pOp++){

3924 if( pOp->p1!=pLevel->iTabCur ) continue;

3925 if( pOp->opcode==OP_Column ){

3926 for(j=0; j<pIdx->nColumn; j++){

3927 if( pOp->p2==pIdx->aiColumn[j] ){

3928 pOp->p2 = j;

3929 pOp->p1 = pLevel->iIdxCur;

3930 break;

3931 }

3932 }

3933 assert(!useIndexOnly \|\| j<pIdx->nColumn);

3934 }else if( pOp->opcode==OP_Rowid ){

3935 pOp->p1 = pLevel->iIdxCur;

3936 pOp->opcode = OP_IdxRowid;

3937 }else if( pOp->opcode==OP_NullRow && useIndexOnly ){

3938 pOp->opcode = OP_Noop;

3939 }

3940 }

3941 }

3942 }

3943

3944 /* Final cleanup

3945 */

3946 whereInfoFree(db, pWInfo);

3947 return;

3948 }

OLD	NEW

« no previous file with comments | « third_party/sqlite/src/walker.c ('k') | third_party/sqlite/test/aggerror.test » ('j') | no next file with comments »