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

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

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

Patch Set: Created 3 years, 7 months ago

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

Jump to:

OLD	NEW
	(Empty)
1 /*

2 ** 2001 September 15

3 **

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

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

6 **

7 ** May you do good and not evil.

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

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

10 **

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

12 ** This 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 #include "sqliteInt.h"

20 #include "whereInt.h"

21

22 /* Forward declaration of methods */

23 static int whereLoopResize(sqlite3, WhereLoop, int);

24

25 /* Test variable that can be set to enable WHERE tracing */

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

27 /***/ int sqlite3WhereTrace = 0;

28 #endif

29

30

31 /*

32 ** Return the estimated number of output rows from a WHERE clause

33 */

34 u64 sqlite3WhereOutputRowCount(WhereInfo *pWInfo){

35 return sqlite3LogEstToInt(pWInfo->nRowOut);

36 }

37

38 /*

39 ** Return one of the WHERE_DISTINCT_xxxxx values to indicate how this

40 ** WHERE clause returns outputs for DISTINCT processing.

41 */

42 int sqlite3WhereIsDistinct(WhereInfo *pWInfo){

43 return pWInfo->eDistinct;

44 }

45

46 /*

47 ** Return TRUE if the WHERE clause returns rows in ORDER BY order.

48 ** Return FALSE if the output needs to be sorted.

49 */

50 int sqlite3WhereIsOrdered(WhereInfo *pWInfo){

51 return pWInfo->nOBSat;

52 }

53

54 /*

55 ** Return the VDBE address or label to jump to in order to continue

56 ** immediately with the next row of a WHERE clause.

57 */

58 int sqlite3WhereContinueLabel(WhereInfo *pWInfo){

59 assert( pWInfo->iContinue!=0 );

60 return pWInfo->iContinue;

61 }

62

63 /*

64 ** Return the VDBE address or label to jump to in order to break

65 ** out of a WHERE loop.

66 */

67 int sqlite3WhereBreakLabel(WhereInfo *pWInfo){

68 return pWInfo->iBreak;

69 }

70

71 /*

72 ** Return ONEPASS_OFF (0) if an UPDATE or DELETE statement is unable to

73 ** operate directly on the rowis returned by a WHERE clause. Return

74 ** ONEPASS_SINGLE (1) if the statement can operation directly because only

75 ** a single row is to be changed. Return ONEPASS_MULTI (2) if the one-pass

76 ** optimization can be used on multiple

77 **

78 ** If the ONEPASS optimization is used (if this routine returns true)

79 ** then also write the indices of open cursors used by ONEPASS

80 ** into aiCur[0] and aiCur[1]. iaCur[0] gets the cursor of the data

81 ** table and iaCur[1] gets the cursor used by an auxiliary index.

82 ** Either value may be -1, indicating that cursor is not used.

83 ** Any cursors returned will have been opened for writing.

84 **

85 ** aiCur[0] and aiCur[1] both get -1 if the where-clause logic is

86 ** unable to use the ONEPASS optimization.

87 */

88 int sqlite3WhereOkOnePass(WhereInfo pWInfo, int aiCur){

89 memcpy(aiCur, pWInfo->aiCurOnePass, sizeof(int)*2);

90 #ifdef WHERETRACE_ENABLED

91 if( sqlite3WhereTrace && pWInfo->eOnePass!=ONEPASS_OFF ){

92 sqlite3DebugPrintf("%s cursors: %d %d\n",

93 pWInfo->eOnePass==ONEPASS_SINGLE ? "ONEPASS_SINGLE" : "ONEPASS_MULTI",

94 aiCur[0], aiCur[1]);

95 }

96 #endif

97 return pWInfo->eOnePass;

98 }

99

100 /*

101 ** Move the content of pSrc into pDest

102 */

103 static void whereOrMove(WhereOrSet pDest, WhereOrSet pSrc){

104 pDest->n = pSrc->n;

105 memcpy(pDest->a, pSrc->a, pDest->n*sizeof(pDest->a[0]));

106 }

107

108 /*

109 ** Try to insert a new prerequisite/cost entry into the WhereOrSet pSet.

110 **

111 ** The new entry might overwrite an existing entry, or it might be

112 ** appended, or it might be discarded. Do whatever is the right thing

113 ** so that pSet keeps the N_OR_COST best entries seen so far.

114 */

115 static int whereOrInsert(

116 WhereOrSet pSet, / The WhereOrSet to be updated */

117 Bitmask prereq, /* Prerequisites of the new entry */

118 LogEst rRun, /* Run-cost of the new entry */

119 LogEst nOut /* Number of outputs for the new entry */

120 ){

121 u16 i;

122 WhereOrCost *p;

123 for(i=pSet->n, p=pSet->a; i>0; i--, p++){

124 if( rRun<=p->rRun && (prereq & p->prereq)==prereq ){

125 goto whereOrInsert_done;

126 }

127 if( p->rRun<=rRun && (p->prereq & prereq)==p->prereq ){

128 return 0;

129 }

130 }

131 if( pSet->n<N_OR_COST ){

132 p = &pSet->a[pSet->n++];

133 p->nOut = nOut;

134 }else{

135 p = pSet->a;

136 for(i=1; i<pSet->n; i++){

137 if( p->rRun>pSet->a[i].rRun ) p = pSet->a + i;

138 }

139 if( p->rRun<=rRun ) return 0;

140 }

141 whereOrInsert_done:

142 p->prereq = prereq;

143 p->rRun = rRun;

144 if( p->nOut>nOut ) p->nOut = nOut;

145 return 1;

146 }

147

148 /*

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

150 ** iCursor is not in the set.

151 */

152 Bitmask sqlite3WhereGetMask(WhereMaskSet *pMaskSet, int iCursor){

153 int i;

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

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

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

157 return MASKBIT(i);

158 }

159 }

160 return 0;

161 }

162

163 /*

164 ** Create a new mask for cursor iCursor.

165 **

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

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

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

169 ** array will never overflow.

170 */

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

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

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

174 }

175

176 /*

177 ** Advance to the next WhereTerm that matches according to the criteria

178 ** established when the pScan object was initialized by whereScanInit().

179 ** Return NULL if there are no more matching WhereTerms.

180 */

181 static WhereTerm whereScanNext(WhereScan pScan){

182 int iCur; /* The cursor on the LHS of the term */

183 i16 iColumn; /* The column on the LHS of the term. -1 for IPK */

184 Expr pX; / An expression being tested */

185 WhereClause pWC; / Shorthand for pScan->pWC */

186 WhereTerm pTerm; / The term being tested */

187 int k = pScan->k; /* Where to start scanning */

188

189 while( pScan->iEquiv<=pScan->nEquiv ){

190 iCur = pScan->aiCur[pScan->iEquiv-1];

191 iColumn = pScan->aiColumn[pScan->iEquiv-1];

192 if( iColumn==XN_EXPR && pScan->pIdxExpr==0 ) return 0;

193 while( (pWC = pScan->pWC)!=0 ){

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

195 if( pTerm->leftCursor==iCur

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

197 && (iColumn!=XN_EXPR

198 \|\| sqlite3ExprCompare(pTerm->pExpr->pLeft,pScan->pIdxExpr,iCur)==0)

199 && (pScan->iEquiv<=1 \|\| !ExprHasProperty(pTerm->pExpr, EP_FromJoin))

200 ){

201 if( (pTerm->eOperator & WO_EQUIV)!=0

202 && pScan->nEquiv<ArraySize(pScan->aiCur)

203 && (pX = sqlite3ExprSkipCollate(pTerm->pExpr->pRight))->op==TK_COLUMN

204 ){

205 int j;

206 for(j=0; j<pScan->nEquiv; j++){

207 if( pScan->aiCur[j]==pX->iTable

208 && pScan->aiColumn[j]==pX->iColumn ){

209 break;

210 }

211 }

212 if( j==pScan->nEquiv ){

213 pScan->aiCur[j] = pX->iTable;

214 pScan->aiColumn[j] = pX->iColumn;

215 pScan->nEquiv++;

216 }

217 }

218 if( (pTerm->eOperator & pScan->opMask)!=0 ){

219 /* Verify the affinity and collating sequence match */

220 if( pScan->zCollName && (pTerm->eOperator & WO_ISNULL)==0 ){

221 CollSeq *pColl;

222 Parse *pParse = pWC->pWInfo->pParse;

223 pX = pTerm->pExpr;

224 if( !sqlite3IndexAffinityOk(pX, pScan->idxaff) ){

225 continue;

226 }

227 assert(pX->pLeft);

228 pColl = sqlite3BinaryCompareCollSeq(pParse,

229 pX->pLeft, pX->pRight);

230 if( pColl==0 ) pColl = pParse->db->pDfltColl;

231 if( sqlite3StrICmp(pColl->zName, pScan->zCollName) ){

232 continue;

233 }

234 }

235 if( (pTerm->eOperator & (WO_EQ\|WO_IS))!=0

236 && (pX = pTerm->pExpr->pRight)->op==TK_COLUMN

237 && pX->iTable==pScan->aiCur[0]

238 && pX->iColumn==pScan->aiColumn[0]

239 ){

240 testcase( pTerm->eOperator & WO_IS );

241 continue;

242 }

243 pScan->k = k+1;

244 return pTerm;

245 }

246 }

247 }

248 pScan->pWC = pScan->pWC->pOuter;

249 k = 0;

250 }

251 pScan->pWC = pScan->pOrigWC;

252 k = 0;

253 pScan->iEquiv++;

254 }

255 return 0;

256 }

257

258 /*

259 ** Initialize a WHERE clause scanner object. Return a pointer to the

260 ** first match. Return NULL if there are no matches.

261 **

262 ** The scanner will be searching the WHERE clause pWC. It will look

263 ** for terms of the form "X <op> <expr>" where X is column iColumn of table

264 ** iCur. The <op> must be one of the operators described by opMask.

265 **

266 ** If the search is for X and the WHERE clause contains terms of the

267 ** form X=Y then this routine might also return terms of the form

268 ** "Y <op> <expr>". The number of levels of transitivity is limited,

269 ** but is enough to handle most commonly occurring SQL statements.

270 **

271 ** If X is not the INTEGER PRIMARY KEY then X must be compatible with

272 ** index pIdx.

273 */

274 static WhereTerm *whereScanInit(

275 WhereScan pScan, / The WhereScan object being initialized */

276 WhereClause pWC, / The WHERE clause to be scanned */

277 int iCur, /* Cursor to scan for */

278 int iColumn, /* Column to scan for */

279 u32 opMask, /* Operator(s) to scan for */

280 Index pIdx / Must be compatible with this index */

281 ){

282 int j = 0;

283

284 /* memset(pScan, 0, sizeof(pScan)); /

285 pScan->pOrigWC = pWC;

286 pScan->pWC = pWC;

287 pScan->pIdxExpr = 0;

288 if( pIdx ){

289 j = iColumn;

290 iColumn = pIdx->aiColumn[j];

291 if( iColumn==XN_EXPR ) pScan->pIdxExpr = pIdx->aColExpr->a[j].pExpr;

292 }

293 if( pIdx && iColumn>=0 ){

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

295 pScan->zCollName = pIdx->azColl[j];

296 }else{

297 pScan->idxaff = 0;

298 pScan->zCollName = 0;

299 }

300 pScan->opMask = opMask;

301 pScan->k = 0;

302 pScan->aiCur[0] = iCur;

303 pScan->aiColumn[0] = iColumn;

304 pScan->nEquiv = 1;

305 pScan->iEquiv = 1;

306 return whereScanNext(pScan);

307 }

308

309 /*

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

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

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

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

314 **

315 ** If pIdx!=0 then search for terms matching the iColumn-th column of pIdx

316 ** rather than the iColumn-th column of table iCur.

317 **

318 ** The term returned might by Y=<expr> if there is another constraint in

319 ** the WHERE clause that specifies that X=Y. Any such constraints will be

320 ** identified by the WO_EQUIV bit in the pTerm->eOperator field. The

321 ** aiCur[]/iaColumn[] arrays hold X and all its equivalents. There are 11

322 ** slots in aiCur[]/aiColumn[] so that means we can look for X plus up to 10

323 ** other equivalent values. Hence a search for X will return <expr> if X=A1

324 ** and A1=A2 and A2=A3 and ... and A9=A10 and A10=<expr>.

325 **

326 ** If there are multiple terms in the WHERE clause of the form "X <op> <expr>"

327 ** then try for the one with no dependencies on <expr> - in other words where

328 ** <expr> is a constant expression of some kind. Only return entries of

329 ** the form "X <op> Y" where Y is a column in another table if no terms of

330 ** the form "X <op> <const-expr>" exist. If no terms with a constant RHS

331 ** exist, try to return a term that does not use WO_EQUIV.

332 */

333 WhereTerm *sqlite3WhereFindTerm(

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

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

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

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

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

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

340 ){

341 WhereTerm *pResult = 0;

342 WhereTerm *p;

343 WhereScan scan;

344

345 p = whereScanInit(&scan, pWC, iCur, iColumn, op, pIdx);

346 op &= WO_EQ\|WO_IS;

347 while( p ){

348 if( (p->prereqRight & notReady)==0 ){

349 if( p->prereqRight==0 && (p->eOperator&op)!=0 ){

350 testcase( p->eOperator & WO_IS );

351 return p;

352 }

353 if( pResult==0 ) pResult = p;

354 }

355 p = whereScanNext(&scan);

356 }

357 return pResult;

358 }

359

360 /*

361 ** This function searches pList for an entry that matches the iCol-th column

362 ** of index pIdx.

363 **

364 ** If such an expression is found, its index in pList->a[] is returned. If

365 ** no expression is found, -1 is returned.

366 */

367 static int findIndexCol(

368 Parse pParse, / Parse context */

369 ExprList pList, / Expression list to search */

370 int iBase, /* Cursor for table associated with pIdx */

371 Index pIdx, / Index to match column of */

372 int iCol /* Column of index to match */

373 ){

374 int i;

375 const char *zColl = pIdx->azColl[iCol];

376

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

378 Expr *p = sqlite3ExprSkipCollate(pList->a[i].pExpr);

379 if( p->op==TK_COLUMN

380 && p->iColumn==pIdx->aiColumn[iCol]

381 && p->iTable==iBase

382 ){

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

384 if( pColl && 0==sqlite3StrICmp(pColl->zName, zColl) ){

385 return i;

386 }

387 }

388 }

389

390 return -1;

391 }

392

393 /*

394 ** Return TRUE if the iCol-th column of index pIdx is NOT NULL

395 */

396 static int indexColumnNotNull(Index *pIdx, int iCol){

397 int j;

398 assert( pIdx!=0 );

399 assert( iCol>=0 && iCol<pIdx->nColumn );

400 j = pIdx->aiColumn[iCol];

401 if( j>=0 ){

402 return pIdx->pTable->aCol[j].notNull;

403 }else if( j==(-1) ){

404 return 1;

405 }else{

406 assert( j==(-2) );

407 return 0; /* Assume an indexed expression can always yield a NULL */

408

409 }

410 }

411

412 /*

413 ** Return true if the DISTINCT expression-list passed as the third argument

414 ** is redundant.

415 **

416 ** A DISTINCT list is redundant if any subset of the columns in the

417 ** DISTINCT list are collectively unique and individually non-null.

418 */

419 static int isDistinctRedundant(

420 Parse pParse, / Parsing context */

421 SrcList pTabList, / The FROM clause */

422 WhereClause pWC, / The WHERE clause */

423 ExprList pDistinct / The result set that needs to be DISTINCT */

424 ){

425 Table *pTab;

426 Index *pIdx;

427 int i;

428 int iBase;

429

430 /* If there is more than one table or sub-select in the FROM clause of

431 ** this query, then it will not be possible to show that the DISTINCT

432 ** clause is redundant. */

433 if( pTabList->nSrc!=1 ) return 0;

434 iBase = pTabList->a[0].iCursor;

435 pTab = pTabList->a[0].pTab;

436

437 /* If any of the expressions is an IPK column on table iBase, then return

438 ** true. Note: The (p->iTable==iBase) part of this test may be false if the

439 ** current SELECT is a correlated sub-query.

440 */

441 for(i=0; i<pDistinct->nExpr; i++){

442 Expr *p = sqlite3ExprSkipCollate(pDistinct->a[i].pExpr);

443 if( p->op==TK_COLUMN && p->iTable==iBase && p->iColumn<0 ) return 1;

444 }

445

446 /* Loop through all indices on the table, checking each to see if it makes

447 ** the DISTINCT qualifier redundant. It does so if:

448 **

449 ** 1. The index is itself UNIQUE, and

450 **

451 ** 2. All of the columns in the index are either part of the pDistinct

452 ** list, or else the WHERE clause contains a term of the form "col=X",

453 ** where X is a constant value. The collation sequences of the

454 ** comparison and select-list expressions must match those of the index.

455 **

456 ** 3. All of those index columns for which the WHERE clause does not

457 ** contain a "col=X" term are subject to a NOT NULL constraint.

458 */

459 for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){

460 if( !IsUniqueIndex(pIdx) ) continue;

461 for(i=0; i<pIdx->nKeyCol; i++){

462 if( 0==sqlite3WhereFindTerm(pWC, iBase, i, ~(Bitmask)0, WO_EQ, pIdx) ){

463 if( findIndexCol(pParse, pDistinct, iBase, pIdx, i)<0 ) break;

464 if( indexColumnNotNull(pIdx, i)==0 ) break;

465 }

466 }

467 if( i==pIdx->nKeyCol ){

468 /* This index implies that the DISTINCT qualifier is redundant. */

469 return 1;

470 }

471 }

472

473 return 0;

474 }

475

476

477 /*

478 ** Estimate the logarithm of the input value to base 2.

479 */

480 static LogEst estLog(LogEst N){

481 return N<=10 ? 0 : sqlite3LogEst(N) - 33;

482 }

483

484 /*

485 ** Convert OP_Column opcodes to OP_Copy in previously generated code.

486 **

487 ** This routine runs over generated VDBE code and translates OP_Column

488 ** opcodes into OP_Copy when the table is being accessed via co-routine

489 ** instead of via table lookup.

490 **

491 ** If the bIncrRowid parameter is 0, then any OP_Rowid instructions on

492 ** cursor iTabCur are transformed into OP_Null. Or, if bIncrRowid is non-zero,

493 ** then each OP_Rowid is transformed into an instruction to increment the

494 ** value stored in its output register.

495 */

496 static void translateColumnToCopy(

497 Vdbe v, / The VDBE containing code to translate */

498 int iStart, /* Translate from this opcode to the end */

499 int iTabCur, /* OP_Column/OP_Rowid references to this table */

500 int iRegister, /* The first column is in this register */

501 int bIncrRowid /* If non-zero, transform OP_rowid to OP_AddImm(1) */

502 ){

503 VdbeOp *pOp = sqlite3VdbeGetOp(v, iStart);

504 int iEnd = sqlite3VdbeCurrentAddr(v);

505 for(; iStart<iEnd; iStart++, pOp++){

506 if( pOp->p1!=iTabCur ) continue;

507 if( pOp->opcode==OP_Column ){

508 pOp->opcode = OP_Copy;

509 pOp->p1 = pOp->p2 + iRegister;

510 pOp->p2 = pOp->p3;

511 pOp->p3 = 0;

512 }else if( pOp->opcode==OP_Rowid ){

513 if( bIncrRowid ){

514 /* Increment the value stored in the P2 operand of the OP_Rowid. */

515 pOp->opcode = OP_AddImm;

516 pOp->p1 = pOp->p2;

517 pOp->p2 = 1;

518 }else{

519 pOp->opcode = OP_Null;

520 pOp->p1 = 0;

521 pOp->p3 = 0;

522 }

523 }

524 }

525 }

526

527 /*

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

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

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

531 ** are no-ops.

532 */

533 #if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(WHERETRACE_ENABLED)

534 static void TRACE_IDX_INPUTS(sqlite3_index_info *p){

535 int i;

536 if( !sqlite3WhereTrace ) return;

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

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

539 i,

540 p->aConstraint[i].iColumn,

541 p->aConstraint[i].iTermOffset,

542 p->aConstraint[i].op,

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

544 }

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

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

547 i,

548 p->aOrderBy[i].iColumn,

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

550 }

551 }

552 static void TRACE_IDX_OUTPUTS(sqlite3_index_info *p){

553 int i;

554 if( !sqlite3WhereTrace ) return;

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

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

557 i,

558 p->aConstraintUsage[i].argvIndex,

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

560 }

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

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

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

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

565 sqlite3DebugPrintf(" estimatedRows=%lld\n", p->estimatedRows);

566 }

567 #else

568 #define TRACE_IDX_INPUTS(A)

569 #define TRACE_IDX_OUTPUTS(A)

570 #endif

571

572 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX

573 /*

574 ** Return TRUE if the WHERE clause term pTerm is of a form where it

575 ** could be used with an index to access pSrc, assuming an appropriate

576 ** index existed.

577 */

578 static int termCanDriveIndex(

579 WhereTerm pTerm, / WHERE clause term to check */

580 struct SrcList_item pSrc, / Table we are trying to access */

581 Bitmask notReady /* Tables in outer loops of the join */

582 ){

583 char aff;

584 if( pTerm->leftCursor!=pSrc->iCursor ) return 0;

585 if( (pTerm->eOperator & (WO_EQ\|WO_IS))==0 ) return 0;

586 if( (pTerm->prereqRight & notReady)!=0 ) return 0;

587 if( pTerm->u.leftColumn<0 ) return 0;

588 aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity;

589 if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0;

590 testcase( pTerm->pExpr->op==TK_IS );

591 return 1;

592 }

593 #endif

594

595

596 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX

597 /*

598 ** Generate code to construct the Index object for an automatic index

599 ** and to set up the WhereLevel object pLevel so that the code generator

600 ** makes use of the automatic index.

601 */

602 static void constructAutomaticIndex(

603 Parse pParse, / The parsing context */

604 WhereClause pWC, / The WHERE clause */

605 struct SrcList_item pSrc, / The FROM clause term to get the next index */

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

607 WhereLevel pLevel / Write new index here */

608 ){

609 int nKeyCol; /* Number of columns in the constructed index */

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

611 WhereTerm pWCEnd; / End of pWC->a[] */

612 Index pIdx; / Object describing the transient index */

613 Vdbe v; / Prepared statement under construction */

614 int addrInit; /* Address of the initialization bypass jump */

615 Table pTable; / The table being indexed */

616 int addrTop; /* Top of the index fill loop */

617 int regRecord; /* Register holding an index record */

618 int n; /* Column counter */

619 int i; /* Loop counter */

620 int mxBitCol; /* Maximum column in pSrc->colUsed */

621 CollSeq pColl; / Collating sequence to on a column */

622 WhereLoop pLoop; / The Loop object */

623 char zNotUsed; / Extra space on the end of pIdx */

624 Bitmask idxCols; /* Bitmap of columns used for indexing */

625 Bitmask extraCols; /* Bitmap of additional columns */

626 u8 sentWarning = 0; /* True if a warnning has been issued */

627 Expr pPartial = 0; / Partial Index Expression */

628 int iContinue = 0; /* Jump here to skip excluded rows */

629 struct SrcList_item pTabItem; / FROM clause term being indexed */

630 int addrCounter = 0; /* Address where integer counter is initialized */

631 int regBase; /* Array of registers where record is assembled */

632

633 /* Generate code to skip over the creation and initialization of the

634 ** transient index on 2nd and subsequent iterations of the loop. */

635 v = pParse->pVdbe;

636 assert( v!=0 );

637 addrInit = sqlite3CodeOnce(pParse); VdbeCoverage(v);

638

639 /* Count the number of columns that will be added to the index

640 ** and used to match WHERE clause constraints */

641 nKeyCol = 0;

642 pTable = pSrc->pTab;

643 pWCEnd = &pWC->a[pWC->nTerm];

644 pLoop = pLevel->pWLoop;

645 idxCols = 0;

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

647 Expr *pExpr = pTerm->pExpr;

648 assert( !ExprHasProperty(pExpr, EP_FromJoin) /* prereq always non-zero */

649 \|\| pExpr->iRightJoinTable!=pSrc->iCursor /* for the right-hand */

650 \|\| pLoop->prereq!=0 ); /* table of a LEFT JOIN */

651 if( pLoop->prereq==0

652 && (pTerm->wtFlags & TERM_VIRTUAL)==0

653 && !ExprHasProperty(pExpr, EP_FromJoin)

654 && sqlite3ExprIsTableConstant(pExpr, pSrc->iCursor) ){

655 pPartial = sqlite3ExprAnd(pParse->db, pPartial,

656 sqlite3ExprDup(pParse->db, pExpr, 0));

657 }

658 if( termCanDriveIndex(pTerm, pSrc, notReady) ){

659 int iCol = pTerm->u.leftColumn;

660 Bitmask cMask = iCol>=BMS ? MASKBIT(BMS-1) : MASKBIT(iCol);

661 testcase( iCol==BMS );

662 testcase( iCol==BMS-1 );

663 if( !sentWarning ){

664 sqlite3_log(SQLITE_WARNING_AUTOINDEX,

665 "automatic index on %s(%s)", pTable->zName,

666 pTable->aCol[iCol].zName);

667 sentWarning = 1;

668 }

669 if( (idxCols & cMask)==0 ){

670 if( whereLoopResize(pParse->db, pLoop, nKeyCol+1) ){

671 goto end_auto_index_create;

672 }

673 pLoop->aLTerm[nKeyCol++] = pTerm;

674 idxCols \|= cMask;

675 }

676 }

677 }

678 assert( nKeyCol>0 );

679 pLoop->u.btree.nEq = pLoop->nLTerm = nKeyCol;

680 pLoop->wsFlags = WHERE_COLUMN_EQ \| WHERE_IDX_ONLY \| WHERE_INDEXED

681 \| WHERE_AUTO_INDEX;

682

683 /* Count the number of additional columns needed to create a

684 ** covering index. A "covering index" is an index that contains all

685 ** columns that are needed by the query. With a covering index, the

686 ** original table never needs to be accessed. Automatic indices must

687 ** be a covering index because the index will not be updated if the

688 ** original table changes and the index and table cannot both be used

689 ** if they go out of sync.

690 */

691 extraCols = pSrc->colUsed & (~idxCols \| MASKBIT(BMS-1));

692 mxBitCol = MIN(BMS-1,pTable->nCol);

693 testcase( pTable->nCol==BMS-1 );

694 testcase( pTable->nCol==BMS-2 );

695 for(i=0; i<mxBitCol; i++){

696 if( extraCols & MASKBIT(i) ) nKeyCol++;

697 }

698 if( pSrc->colUsed & MASKBIT(BMS-1) ){

699 nKeyCol += pTable->nCol - BMS + 1;

700 }

701

702 /* Construct the Index object to describe this index */

703 pIdx = sqlite3AllocateIndexObject(pParse->db, nKeyCol+1, 0, &zNotUsed);

704 if( pIdx==0 ) goto end_auto_index_create;

705 pLoop->u.btree.pIndex = pIdx;

706 pIdx->zName = "auto-index";

707 pIdx->pTable = pTable;

708 n = 0;

709 idxCols = 0;

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

711 if( termCanDriveIndex(pTerm, pSrc, notReady) ){

712 int iCol = pTerm->u.leftColumn;

713 Bitmask cMask = iCol>=BMS ? MASKBIT(BMS-1) : MASKBIT(iCol);

714 testcase( iCol==BMS-1 );

715 testcase( iCol==BMS );

716 if( (idxCols & cMask)==0 ){

717 Expr *pX = pTerm->pExpr;

718 idxCols \|= cMask;

719 pIdx->aiColumn[n] = pTerm->u.leftColumn;

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

721 pIdx->azColl[n] = pColl ? pColl->zName : sqlite3StrBINARY;

722 n++;

723 }

724 }

725 }

726 assert( (u32)n==pLoop->u.btree.nEq );

727

728 /* Add additional columns needed to make the automatic index into

729 ** a covering index */

730 for(i=0; i<mxBitCol; i++){

731 if( extraCols & MASKBIT(i) ){

732 pIdx->aiColumn[n] = i;

733 pIdx->azColl[n] = sqlite3StrBINARY;

734 n++;

735 }

736 }

737 if( pSrc->colUsed & MASKBIT(BMS-1) ){

738 for(i=BMS-1; i<pTable->nCol; i++){

739 pIdx->aiColumn[n] = i;

740 pIdx->azColl[n] = sqlite3StrBINARY;

741 n++;

742 }

743 }

744 assert( n==nKeyCol );

745 pIdx->aiColumn[n] = XN_ROWID;

746 pIdx->azColl[n] = sqlite3StrBINARY;

747

748 /* Create the automatic index */

749 assert( pLevel->iIdxCur>=0 );

750 pLevel->iIdxCur = pParse->nTab++;

751 sqlite3VdbeAddOp2(v, OP_OpenAutoindex, pLevel->iIdxCur, nKeyCol+1);

752 sqlite3VdbeSetP4KeyInfo(pParse, pIdx);

753 VdbeComment((v, "for %s", pTable->zName));

754

755 /* Fill the automatic index with content */

756 sqlite3ExprCachePush(pParse);

757 pTabItem = &pWC->pWInfo->pTabList->a[pLevel->iFrom];

758 if( pTabItem->fg.viaCoroutine ){

759 int regYield = pTabItem->regReturn;

760 addrCounter = sqlite3VdbeAddOp2(v, OP_Integer, 0, 0);

761 sqlite3VdbeAddOp3(v, OP_InitCoroutine, regYield, 0, pTabItem->addrFillSub);

762 addrTop = sqlite3VdbeAddOp1(v, OP_Yield, regYield);

763 VdbeCoverage(v);

764 VdbeComment((v, "next row of \"%s\"", pTabItem->pTab->zName));

765 }else{

766 addrTop = sqlite3VdbeAddOp1(v, OP_Rewind, pLevel->iTabCur); VdbeCoverage(v);

767 }

768 if( pPartial ){

769 iContinue = sqlite3VdbeMakeLabel(v);

770 sqlite3ExprIfFalse(pParse, pPartial, iContinue, SQLITE_JUMPIFNULL);

771 pLoop->wsFlags \|= WHERE_PARTIALIDX;

772 }

773 regRecord = sqlite3GetTempReg(pParse);

774 regBase = sqlite3GenerateIndexKey(

775 pParse, pIdx, pLevel->iTabCur, regRecord, 0, 0, 0, 0

776 );

777 sqlite3VdbeAddOp2(v, OP_IdxInsert, pLevel->iIdxCur, regRecord);

778 sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);

779 if( pPartial ) sqlite3VdbeResolveLabel(v, iContinue);

780 if( pTabItem->fg.viaCoroutine ){

781 sqlite3VdbeChangeP2(v, addrCounter, regBase+n);

782 translateColumnToCopy(v, addrTop, pLevel->iTabCur, pTabItem->regResult, 1);

783 sqlite3VdbeGoto(v, addrTop);

784 pTabItem->fg.viaCoroutine = 0;

785 }else{

786 sqlite3VdbeAddOp2(v, OP_Next, pLevel->iTabCur, addrTop+1); VdbeCoverage(v);

787 }

788 sqlite3VdbeChangeP5(v, SQLITE_STMTSTATUS_AUTOINDEX);

789 sqlite3VdbeJumpHere(v, addrTop);

790 sqlite3ReleaseTempReg(pParse, regRecord);

791 sqlite3ExprCachePop(pParse);

792

793 /* Jump here when skipping the initialization */

794 sqlite3VdbeJumpHere(v, addrInit);

795

796 end_auto_index_create:

797 sqlite3ExprDelete(pParse->db, pPartial);

798 }

799 #endif /* SQLITE_OMIT_AUTOMATIC_INDEX */

800

801 #ifndef SQLITE_OMIT_VIRTUALTABLE

802 /*

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

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

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

806 */

807 static sqlite3_index_info *allocateIndexInfo(

808 Parse *pParse,

809 WhereClause *pWC,

810 Bitmask mUnusable, /* Ignore terms with these prereqs */

811 struct SrcList_item *pSrc,

812 ExprList *pOrderBy

813 ){

814 int i, j;

815 int nTerm;

816 struct sqlite3_index_constraint *pIdxCons;

817 struct sqlite3_index_orderby *pIdxOrderBy;

818 struct sqlite3_index_constraint_usage *pUsage;

819 WhereTerm *pTerm;

820 int nOrderBy;

821 sqlite3_index_info *pIdxInfo;

822

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

824 ** to this virtual table */

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

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

827 if( pTerm->prereqRight & mUnusable ) continue;

828 assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) );

829 testcase( pTerm->eOperator & WO_IN );

830 testcase( pTerm->eOperator & WO_ISNULL );

831 testcase( pTerm->eOperator & WO_IS );

832 testcase( pTerm->eOperator & WO_ALL );

833 if( (pTerm->eOperator & ~(WO_ISNULL\|WO_EQUIV\|WO_IS))==0 ) continue;

834 if( pTerm->wtFlags & TERM_VNULL ) continue;

835 assert( pTerm->u.leftColumn>=(-1) );

836 nTerm++;

837 }

838

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

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

841 ** the sqlite3_index_info structure.

842 */

843 nOrderBy = 0;

844 if( pOrderBy ){

845 int n = pOrderBy->nExpr;

846 for(i=0; i<n; i++){

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

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

849 }

850 if( i==n){

851 nOrderBy = n;

852 }

853 }

854

855 /* Allocate the sqlite3_index_info structure

856 */

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

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

859 + sizeof(pIdxOrderBy)nOrderBy );

860 if( pIdxInfo==0 ){

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

862 return 0;

863 }

864

865 /* Initialize the structure. The sqlite3_index_info structure contains

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

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

868 ** initialize those fields.

869 */

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

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

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

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

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

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

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

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

878 pUsage;

879

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

881 u8 op;

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

883 if( pTerm->prereqRight & mUnusable ) continue;

884 assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) );

885 testcase( pTerm->eOperator & WO_IN );

886 testcase( pTerm->eOperator & WO_IS );

887 testcase( pTerm->eOperator & WO_ISNULL );

888 testcase( pTerm->eOperator & WO_ALL );

889 if( (pTerm->eOperator & ~(WO_ISNULL\|WO_EQUIV\|WO_IS))==0 ) continue;

890 if( pTerm->wtFlags & TERM_VNULL ) continue;

891 assert( pTerm->u.leftColumn>=(-1) );

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

893 pIdxCons[j].iTermOffset = i;

894 op = (u8)pTerm->eOperator & WO_ALL;

895 if( op==WO_IN ) op = WO_EQ;

896 if( op==WO_MATCH ){

897 op = pTerm->eMatchOp;

898 }

899 pIdxCons[j].op = op;

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

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

902 ** following asserts verify this fact. */

903 assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ );

904 assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT );

905 assert( WO_LE==SQLITE_INDEX_CONSTRAINT_LE );

906 assert( WO_GT==SQLITE_INDEX_CONSTRAINT_GT );

907 assert( WO_GE==SQLITE_INDEX_CONSTRAINT_GE );

908 assert( WO_MATCH==SQLITE_INDEX_CONSTRAINT_MATCH );

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

910 j++;

911 }

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

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

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

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

916 }

917

918 return pIdxInfo;

919 }

920

921 /*

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

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

924 ** method of the virtual table with the sqlite3_index_info object that

925 ** comes in as the 3rd argument to this function.

926 **

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

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

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

930 **

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

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

933 ** that this is required.

934 */

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

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

937 int i;

938 int rc;

939

940 TRACE_IDX_INPUTS(p);

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

942 TRACE_IDX_OUTPUTS(p);

943

944 if( rc!=SQLITE_OK ){

945 if( rc==SQLITE_NOMEM ){

946 pParse->db->mallocFailed = 1;

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

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

949 }else{

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

951 }

952 }

953 sqlite3_free(pVtab->zErrMsg);

954 pVtab->zErrMsg = 0;

955

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

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

958 sqlite3ErrorMsg(pParse,

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

960 }

961 }

962

963 return pParse->nErr;

964 }

965 #endif /* !defined(SQLITE_OMIT_VIRTUALTABLE) */

966

967 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4

968 /*

969 ** Estimate the location of a particular key among all keys in an

970 ** index. Store the results in aStat as follows:

971 **

972 ** aStat[0] Est. number of rows less than pRec

973 ** aStat[1] Est. number of rows equal to pRec

974 **

975 ** Return the index of the sample that is the smallest sample that

976 ** is greater than or equal to pRec. Note that this index is not an index

977 ** into the aSample[] array - it is an index into a virtual set of samples

978 ** based on the contents of aSample[] and the number of fields in record

979 ** pRec.

980 */

981 static int whereKeyStats(

982 Parse pParse, / Database connection */

983 Index pIdx, / Index to consider domain of */

984 UnpackedRecord pRec, / Vector of values to consider */

985 int roundUp, /* Round up if true. Round down if false */

986 tRowcnt aStat / OUT: stats written here */

987 ){

988 IndexSample *aSample = pIdx->aSample;

989 int iCol; /* Index of required stats in anEq[] etc. */

990 int i; /* Index of first sample >= pRec */

991 int iSample; /* Smallest sample larger than or equal to pRec */

992 int iMin = 0; /* Smallest sample not yet tested */

993 int iTest; /* Next sample to test */

994 int res; /* Result of comparison operation */

995 int nField; /* Number of fields in pRec */

996 tRowcnt iLower = 0; /* anLt[] + anEq[] of largest sample pRec is > */

997

998 #ifndef SQLITE_DEBUG

999 UNUSED_PARAMETER( pParse );

1000 #endif

1001 assert( pRec!=0 );

1002 assert( pIdx->nSample>0 );

1003 assert( pRec->nField>0 && pRec->nField<=pIdx->nSampleCol );

1004

1005 /* Do a binary search to find the first sample greater than or equal

1006 ** to pRec. If pRec contains a single field, the set of samples to search

1007 ** is simply the aSample[] array. If the samples in aSample[] contain more

1008 ** than one fields, all fields following the first are ignored.

1009 **

1010 ** If pRec contains N fields, where N is more than one, then as well as the

1011 ** samples in aSample[] (truncated to N fields), the search also has to

1012 ** consider prefixes of those samples. For example, if the set of samples

1013 ** in aSample is:

1014 **

1015 ** aSample[0] = (a, 5)

1016 ** aSample[1] = (a, 10)

1017 ** aSample[2] = (b, 5)

1018 ** aSample[3] = (c, 100)

1019 ** aSample[4] = (c, 105)

1020 **

1021 ** Then the search space should ideally be the samples above and the

1022 ** unique prefixes [a], [b] and [c]. But since that is hard to organize,

1023 ** the code actually searches this set:

1024 **

1025 ** 0: (a)

1026 ** 1: (a, 5)

1027 ** 2: (a, 10)

1028 ** 3: (a, 10)

1029 ** 4: (b)

1030 ** 5: (b, 5)

1031 ** 6: (c)

1032 ** 7: (c, 100)

1033 ** 8: (c, 105)

1034 ** 9: (c, 105)

1035 **

1036 ** For each sample in the aSample[] array, N samples are present in the

1037 ** effective sample array. In the above, samples 0 and 1 are based on

1038 ** sample aSample[0]. Samples 2 and 3 on aSample[1] etc.

1039 **

1040 ** Often, sample i of each block of N effective samples has (i+1) fields.

1041 ** Except, each sample may be extended to ensure that it is greater than or

1042 ** equal to the previous sample in the array. For example, in the above,

1043 ** sample 2 is the first sample of a block of N samples, so at first it

1044 ** appears that it should be 1 field in size. However, that would make it

1045 ** smaller than sample 1, so the binary search would not work. As a result,

1046 ** it is extended to two fields. The duplicates that this creates do not

1047 ** cause any problems.

1048 */

1049 nField = pRec->nField;

1050 iCol = 0;

1051 iSample = pIdx->nSample * nField;

1052 do{

1053 int iSamp; /* Index in aSample[] of test sample */

1054 int n; /* Number of fields in test sample */

1055

1056 iTest = (iMin+iSample)/2;

1057 iSamp = iTest / nField;

1058 if( iSamp>0 ){

1059 /* The proposed effective sample is a prefix of sample aSample[iSamp].

1060 ** Specifically, the shortest prefix of at least (1 + iTest%nField)

1061 ** fields that is greater than the previous effective sample. */

1062 for(n=(iTest % nField) + 1; n<nField; n++){

1063 if( aSample[iSamp-1].anLt[n-1]!=aSample[iSamp].anLt[n-1] ) break;

1064 }

1065 }else{

1066 n = iTest + 1;

1067 }

1068

1069 pRec->nField = n;

1070 res = sqlite3VdbeRecordCompare(aSample[iSamp].n, aSample[iSamp].p, pRec);

1071 if( res<0 ){

1072 iLower = aSample[iSamp].anLt[n-1] + aSample[iSamp].anEq[n-1];

1073 iMin = iTest+1;

1074 }else if( res==0 && n<nField ){

1075 iLower = aSample[iSamp].anLt[n-1];

1076 iMin = iTest+1;

1077 res = -1;

1078 }else{

1079 iSample = iTest;

1080 iCol = n-1;

1081 }

1082 }while( res && iMin<iSample );

1083 i = iSample / nField;

1084

1085 #ifdef SQLITE_DEBUG

1086 /* The following assert statements check that the binary search code

1087 ** above found the right answer. This block serves no purpose other

1088 ** than to invoke the asserts. */

1089 if( pParse->db->mallocFailed==0 ){

1090 if( res==0 ){

1091 /* If (res==0) is true, then pRec must be equal to sample i. */

1092 assert( i<pIdx->nSample );

1093 assert( iCol==nField-1 );

1094 pRec->nField = nField;

1095 assert( 0==sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec)

1096 \|\| pParse->db->mallocFailed

1097 );

1098 }else{

1099 /* Unless i==pIdx->nSample, indicating that pRec is larger than

1100 ** all samples in the aSample[] array, pRec must be smaller than the

1101 ** (iCol+1) field prefix of sample i. */

1102 assert( i<=pIdx->nSample && i>=0 );

1103 pRec->nField = iCol+1;

1104 assert( i==pIdx->nSample

1105 \|\| sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec)>0

1106 \|\| pParse->db->mallocFailed );

1107

1108 /* if i==0 and iCol==0, then record pRec is smaller than all samples

1109 ** in the aSample[] array. Otherwise, if (iCol>0) then pRec must

1110 ** be greater than or equal to the (iCol) field prefix of sample i.

1111 ** If (i>0), then pRec must also be greater than sample (i-1). */

1112 if( iCol>0 ){

1113 pRec->nField = iCol;

1114 assert( sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec)<=0

1115 \|\| pParse->db->mallocFailed );

1116 }

1117 if( i>0 ){

1118 pRec->nField = nField;

1119 assert( sqlite3VdbeRecordCompare(aSample[i-1].n, aSample[i-1].p, pRec)<0

1120 \|\| pParse->db->mallocFailed );

1121 }

1122 }

1123 }

1124 #endif /* ifdef SQLITE_DEBUG */

1125

1126 if( res==0 ){

1127 /* Record pRec is equal to sample i */

1128 assert( iCol==nField-1 );

1129 aStat[0] = aSample[i].anLt[iCol];

1130 aStat[1] = aSample[i].anEq[iCol];

1131 }else{

1132 /* At this point, the (iCol+1) field prefix of aSample[i] is the first

1133 ** sample that is greater than pRec. Or, if i==pIdx->nSample then pRec

1134 ** is larger than all samples in the array. */

1135 tRowcnt iUpper, iGap;

1136 if( i>=pIdx->nSample ){

1137 iUpper = sqlite3LogEstToInt(pIdx->aiRowLogEst[0]);

1138 }else{

1139 iUpper = aSample[i].anLt[iCol];

1140 }

1141

1142 if( iLower>=iUpper ){

1143 iGap = 0;

1144 }else{

1145 iGap = iUpper - iLower;

1146 }

1147 if( roundUp ){

1148 iGap = (iGap*2)/3;

1149 }else{

1150 iGap = iGap/3;

1151 }

1152 aStat[0] = iLower + iGap;

1153 aStat[1] = pIdx->aAvgEq[iCol];

1154 }

1155

1156 /* Restore the pRec->nField value before returning. */

1157 pRec->nField = nField;

1158 return i;

1159 }

1160 #endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */

1161

1162 /*

1163 ** If it is not NULL, pTerm is a term that provides an upper or lower

1164 ** bound on a range scan. Without considering pTerm, it is estimated

1165 ** that the scan will visit nNew rows. This function returns the number

1166 ** estimated to be visited after taking pTerm into account.

1167 **

1168 ** If the user explicitly specified a likelihood() value for this term,

1169 ** then the return value is the likelihood multiplied by the number of

1170 ** input rows. Otherwise, this function assumes that an "IS NOT NULL" term

1171 ** has a likelihood of 0.50, and any other term a likelihood of 0.25.

1172 */

1173 static LogEst whereRangeAdjust(WhereTerm *pTerm, LogEst nNew){

1174 LogEst nRet = nNew;

1175 if( pTerm ){

1176 if( pTerm->truthProb<=0 ){

1177 nRet += pTerm->truthProb;

1178 }else if( (pTerm->wtFlags & TERM_VNULL)==0 ){

1179 nRet -= 20; assert( 20==sqlite3LogEst(4) );

1180 }

1181 }

1182 return nRet;

1183 }

1184

1185

1186 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4

1187 /*

1188 ** Return the affinity for a single column of an index.

1189 */

1190 static char sqlite3IndexColumnAffinity(sqlite3 db, Index pIdx, int iCol){

1191 assert( iCol>=0 && iCol<pIdx->nColumn );

1192 if( !pIdx->zColAff ){

1193 if( sqlite3IndexAffinityStr(db, pIdx)==0 ) return SQLITE_AFF_BLOB;

1194 }

1195 return pIdx->zColAff[iCol];

1196 }

1197 #endif

1198

1199

1200 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4

1201 /*

1202 ** This function is called to estimate the number of rows visited by a

1203 ** range-scan on a skip-scan index. For example:

1204 **

1205 ** CREATE INDEX i1 ON t1(a, b, c);

1206 ** SELECT * FROM t1 WHERE a=? AND c BETWEEN ? AND ?;

1207 **

1208 ** Value pLoop->nOut is currently set to the estimated number of rows

1209 ** visited for scanning (a=? AND b=?). This function reduces that estimate

1210 ** by some factor to account for the (c BETWEEN ? AND ?) expression based

1211 ** on the stat4 data for the index. this scan will be peformed multiple

1212 ** times (once for each (a,b) combination that matches a=?) is dealt with

1213 ** by the caller.

1214 **

1215 ** It does this by scanning through all stat4 samples, comparing values

1216 ** extracted from pLower and pUpper with the corresponding column in each

1217 ** sample. If L and U are the number of samples found to be less than or

1218 ** equal to the values extracted from pLower and pUpper respectively, and

1219 ** N is the total number of samples, the pLoop->nOut value is adjusted

1220 ** as follows:

1221 **

1222 ** nOut = nOut * ( min(U - L, 1) / N )

1223 **

1224 ** If pLower is NULL, or a value cannot be extracted from the term, L is

1225 ** set to zero. If pUpper is NULL, or a value cannot be extracted from it,

1226 ** U is set to N.

1227 **

1228 ** Normally, this function sets *pbDone to 1 before returning. However,

1229 ** if no value can be extracted from either pLower or pUpper (and so the

1230 ** estimate of the number of rows delivered remains unchanged), *pbDone

1231 ** is left as is.

1232 **

1233 ** If an error occurs, an SQLite error code is returned. Otherwise,

1234 ** SQLITE_OK.

1235 */

1236 static int whereRangeSkipScanEst(

1237 Parse pParse, / Parsing & code generating context */

1238 WhereTerm pLower, / Lower bound on the range. ex: "x>123" Might be NULL */

1239 WhereTerm pUpper, / Upper bound on the range. ex: "x<455" Might be NULL */

1240 WhereLoop pLoop, / Update the .nOut value of this loop */

1241 int pbDone / Set to true if at least one expr. value extracted */

1242 ){

1243 Index *p = pLoop->u.btree.pIndex;

1244 int nEq = pLoop->u.btree.nEq;

1245 sqlite3 *db = pParse->db;

1246 int nLower = -1;

1247 int nUpper = p->nSample+1;

1248 int rc = SQLITE_OK;

1249 u8 aff = sqlite3IndexColumnAffinity(db, p, nEq);

1250 CollSeq *pColl;

1251

1252 sqlite3_value p1 = 0; / Value extracted from pLower */

1253 sqlite3_value p2 = 0; / Value extracted from pUpper */

1254 sqlite3_value pVal = 0; / Value extracted from record */

1255

1256 pColl = sqlite3LocateCollSeq(pParse, p->azColl[nEq]);

1257 if( pLower ){

1258 rc = sqlite3Stat4ValueFromExpr(pParse, pLower->pExpr->pRight, aff, &p1);

1259 nLower = 0;

1260 }

1261 if( pUpper && rc==SQLITE_OK ){

1262 rc = sqlite3Stat4ValueFromExpr(pParse, pUpper->pExpr->pRight, aff, &p2);

1263 nUpper = p2 ? 0 : p->nSample;

1264 }

1265

1266 if( p1 \|\| p2 ){

1267 int i;

1268 int nDiff;

1269 for(i=0; rc==SQLITE_OK && i<p->nSample; i++){

1270 rc = sqlite3Stat4Column(db, p->aSample[i].p, p->aSample[i].n, nEq, &pVal);

1271 if( rc==SQLITE_OK && p1 ){

1272 int res = sqlite3MemCompare(p1, pVal, pColl);

1273 if( res>=0 ) nLower++;

1274 }

1275 if( rc==SQLITE_OK && p2 ){

1276 int res = sqlite3MemCompare(p2, pVal, pColl);

1277 if( res>=0 ) nUpper++;

1278 }

1279 }

1280 nDiff = (nUpper - nLower);

1281 if( nDiff<=0 ) nDiff = 1;

1282

1283 /* If there is both an upper and lower bound specified, and the

1284 ** comparisons indicate that they are close together, use the fallback

1285 ** method (assume that the scan visits 1/64 of the rows) for estimating

1286 ** the number of rows visited. Otherwise, estimate the number of rows

1287 ** using the method described in the header comment for this function. */

1288 if( nDiff!=1 \|\| pUpper==0 \|\| pLower==0 ){

1289 int nAdjust = (sqlite3LogEst(p->nSample) - sqlite3LogEst(nDiff));

1290 pLoop->nOut -= nAdjust;

1291 *pbDone = 1;

1292 WHERETRACE(0x10, ("range skip-scan regions: %u..%u adjust=%d est=%d\n",

1293 nLower, nUpper, nAdjust*-1, pLoop->nOut));

1294 }

1295

1296 }else{

1297 assert( *pbDone==0 );

1298 }

1299

1300 sqlite3ValueFree(p1);

1301 sqlite3ValueFree(p2);

1302 sqlite3ValueFree(pVal);

1303

1304 return rc;

1305 }

1306 #endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */

1307

1308 /*

1309 ** This function is used to estimate the number of rows that will be visited

1310 ** by scanning an index for a range of values. The range may have an upper

1311 ** bound, a lower bound, or both. The WHERE clause terms that set the upper

1312 ** and lower bounds are represented by pLower and pUpper respectively. For

1313 ** example, assuming that index p is on t1(a):

1314 **

1315 ** ... FROM t1 WHERE a > ? AND a < ? ...

1316 ** \|_____\| \|_____\|

1317 ** \| \|

1318 ** pLower pUpper

1319 **

1320 ** If either of the upper or lower bound is not present, then NULL is passed in

1321 ** place of the corresponding WhereTerm.

1322 **

1323 ** The value in (pBuilder->pNew->u.btree.nEq) is the number of the index

1324 ** column subject to the range constraint. Or, equivalently, the number of

1325 ** equality constraints optimized by the proposed index scan. For example,

1326 ** assuming index p is on t1(a, b), and the SQL query is:

1327 **

1328 ** ... FROM t1 WHERE a = ? AND b > ? AND b < ? ...

1329 **

1330 ** then nEq is set to 1 (as the range restricted column, b, is the second

1331 ** left-most column of the index). Or, if the query is:

1332 **

1333 ** ... FROM t1 WHERE a > ? AND a < ? ...

1334 **

1335 ** then nEq is set to 0.

1336 **

1337 ** When this function is called, *pnOut is set to the sqlite3LogEst() of the

1338 ** number of rows that the index scan is expected to visit without

1339 ** considering the range constraints. If nEq is 0, then *pnOut is the number of

1340 ** rows in the index. Assuming no error occurs, *pnOut is adjusted (reduced)

1341 ** to account for the range constraints pLower and pUpper.

1342 **

1343 ** In the absence of sqlite_stat4 ANALYZE data, or if such data cannot be

1344 ** used, a single range inequality reduces the search space by a factor of 4.

1345 ** and a pair of constraints (x>? AND x<?) reduces the expected number of

1346 ** rows visited by a factor of 64.

1347 */

1348 static int whereRangeScanEst(

1349 Parse pParse, / Parsing & code generating context */

1350 WhereLoopBuilder *pBuilder,

1351 WhereTerm pLower, / Lower bound on the range. ex: "x>123" Might be NULL */

1352 WhereTerm pUpper, / Upper bound on the range. ex: "x<455" Might be NULL */

1353 WhereLoop pLoop / Modify the .nOut and maybe .rRun fields */

1354 ){

1355 int rc = SQLITE_OK;

1356 int nOut = pLoop->nOut;

1357 LogEst nNew;

1358

1359 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4

1360 Index *p = pLoop->u.btree.pIndex;

1361 int nEq = pLoop->u.btree.nEq;

1362

1363 if( p->nSample>0 && nEq<p->nSampleCol ){

1364 if( nEq==pBuilder->nRecValid ){

1365 UnpackedRecord *pRec = pBuilder->pRec;

1366 tRowcnt a[2];

1367 u8 aff;

1368

1369 /* Variable iLower will be set to the estimate of the number of rows in

1370 ** the index that are less than the lower bound of the range query. The

1371 ** lower bound being the concatenation of $P and $L, where $P is the

1372 ** key-prefix formed by the nEq values matched against the nEq left-most

1373 ** columns of the index, and $L is the value in pLower.

1374 **

1375 ** Or, if pLower is NULL or $L cannot be extracted from it (because it

1376 ** is not a simple variable or literal value), the lower bound of the

1377 ** range is $P. Due to a quirk in the way whereKeyStats() works, even

1378 ** if $L is available, whereKeyStats() is called for both ($P) and

1379 ** ($P:$L) and the larger of the two returned values is used.

1380 **

1381 ** Similarly, iUpper is to be set to the estimate of the number of rows

1382 ** less than the upper bound of the range query. Where the upper bound

1383 ** is either ($P) or ($P:$U). Again, even if $U is available, both values

1384 ** of iUpper are requested of whereKeyStats() and the smaller used.

1385 **

1386 ** The number of rows between the two bounds is then just iUpper-iLower.

1387 */

1388 tRowcnt iLower; /* Rows less than the lower bound */

1389 tRowcnt iUpper; /* Rows less than the upper bound */

1390 int iLwrIdx = -2; /* aSample[] for the lower bound */

1391 int iUprIdx = -1; /* aSample[] for the upper bound */

1392

1393 if( pRec ){

1394 testcase( pRec->nField!=pBuilder->nRecValid );

1395 pRec->nField = pBuilder->nRecValid;

1396 }

1397 aff = sqlite3IndexColumnAffinity(pParse->db, p, nEq);

1398 assert( nEq!=p->nKeyCol \|\| aff==SQLITE_AFF_INTEGER );

1399 /* Determine iLower and iUpper using ($P) only. */

1400 if( nEq==0 ){

1401 iLower = 0;

1402 iUpper = p->nRowEst0;

1403 }else{

1404 /* Note: this call could be optimized away - since the same values must

1405 ** have been requested when testing key $P in whereEqualScanEst(). */

1406 whereKeyStats(pParse, p, pRec, 0, a);

1407 iLower = a[0];

1408 iUpper = a[0] + a[1];

1409 }

1410

1411 assert( pLower==0 \|\| (pLower->eOperator & (WO_GT\|WO_GE))!=0 );

1412 assert( pUpper==0 \|\| (pUpper->eOperator & (WO_LT\|WO_LE))!=0 );

1413 assert( p->aSortOrder!=0 );

1414 if( p->aSortOrder[nEq] ){

1415 /* The roles of pLower and pUpper are swapped for a DESC index */

1416 SWAP(WhereTerm*, pLower, pUpper);

1417 }

1418

1419 /* If possible, improve on the iLower estimate using ($P:$L). */

1420 if( pLower ){

1421 int bOk; /* True if value is extracted from pExpr */

1422 Expr *pExpr = pLower->pExpr->pRight;

1423 rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, aff, nEq, &bOk);

1424 if( rc==SQLITE_OK && bOk ){

1425 tRowcnt iNew;

1426 iLwrIdx = whereKeyStats(pParse, p, pRec, 0, a);

1427 iNew = a[0] + ((pLower->eOperator & (WO_GT\|WO_LE)) ? a[1] : 0);

1428 if( iNew>iLower ) iLower = iNew;

1429 nOut--;

1430 pLower = 0;

1431 }

1432 }

1433

1434 /* If possible, improve on the iUpper estimate using ($P:$U). */

1435 if( pUpper ){

1436 int bOk; /* True if value is extracted from pExpr */

1437 Expr *pExpr = pUpper->pExpr->pRight;

1438 rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, aff, nEq, &bOk);

1439 if( rc==SQLITE_OK && bOk ){

1440 tRowcnt iNew;

1441 iUprIdx = whereKeyStats(pParse, p, pRec, 1, a);

1442 iNew = a[0] + ((pUpper->eOperator & (WO_GT\|WO_LE)) ? a[1] : 0);

1443 if( iNew<iUpper ) iUpper = iNew;

1444 nOut--;

1445 pUpper = 0;

1446 }

1447 }

1448

1449 pBuilder->pRec = pRec;

1450 if( rc==SQLITE_OK ){

1451 if( iUpper>iLower ){

1452 nNew = sqlite3LogEst(iUpper - iLower);

1453 /* TUNING: If both iUpper and iLower are derived from the same

1454 ** sample, then assume they are 4x more selective. This brings

1455 ** the estimated selectivity more in line with what it would be

1456 ** if estimated without the use of STAT3/4 tables. */

1457 if( iLwrIdx==iUprIdx ) nNew -= 20; assert( 20==sqlite3LogEst(4) );

1458 }else{

1459 nNew = 10; assert( 10==sqlite3LogEst(2) );

1460 }

1461 if( nNew<nOut ){

1462 nOut = nNew;

1463 }

1464 WHERETRACE(0x10, ("STAT4 range scan: %u..%u est=%d\n",

1465 (u32)iLower, (u32)iUpper, nOut));

1466 }

1467 }else{

1468 int bDone = 0;

1469 rc = whereRangeSkipScanEst(pParse, pLower, pUpper, pLoop, &bDone);

1470 if( bDone ) return rc;

1471 }

1472 }

1473 #else

1474 UNUSED_PARAMETER(pParse);

1475 UNUSED_PARAMETER(pBuilder);

1476 assert( pLower \|\| pUpper );

1477 #endif

1478 assert( pUpper==0 \|\| (pUpper->wtFlags & TERM_VNULL)==0 );

1479 nNew = whereRangeAdjust(pLower, nOut);

1480 nNew = whereRangeAdjust(pUpper, nNew);

1481

1482 /* TUNING: If there is both an upper and lower limit and neither limit

1483 ** has an application-defined likelihood(), assume the range is

1484 ** reduced by an additional 75%. This means that, by default, an open-ended

1485 ** range query (e.g. col > ?) is assumed to match 1/4 of the rows in the

1486 ** index. While a closed range (e.g. col BETWEEN ? AND ?) is estimated to

1487 ** match 1/64 of the index. */

1488 if( pLower && pLower->truthProb>0 && pUpper && pUpper->truthProb>0 ){

1489 nNew -= 20;

1490 }

1491

1492 nOut -= (pLower!=0) + (pUpper!=0);

1493 if( nNew<10 ) nNew = 10;

1494 if( nNew<nOut ) nOut = nNew;

1495 #if defined(WHERETRACE_ENABLED)

1496 if( pLoop->nOut>nOut ){

1497 WHERETRACE(0x10,("Range scan lowers nOut from %d to %d\n",

1498 pLoop->nOut, nOut));

1499 }

1500 #endif

1501 pLoop->nOut = (LogEst)nOut;

1502 return rc;

1503 }

1504

1505 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4

1506 /*

1507 ** Estimate the number of rows that will be returned based on

1508 ** an equality constraint x=VALUE and where that VALUE occurs in

1509 ** the histogram data. This only works when x is the left-most

1510 ** column of an index and sqlite_stat3 histogram data is available

1511 ** for that index. When pExpr==NULL that means the constraint is

1512 ** "x IS NULL" instead of "x=VALUE".

1513 **

1514 ** Write the estimated row count into *pnRow and return SQLITE_OK.

1515 ** If unable to make an estimate, leave *pnRow unchanged and return

1516 ** non-zero.

1517 **

1518 ** This routine can fail if it is unable to load a collating sequence

1519 ** required for string comparison, or if unable to allocate memory

1520 ** for a UTF conversion required for comparison. The error is stored

1521 ** in the pParse structure.

1522 */

1523 static int whereEqualScanEst(

1524 Parse pParse, / Parsing & code generating context */

1525 WhereLoopBuilder *pBuilder,

1526 Expr pExpr, / Expression for VALUE in the x=VALUE constraint */

1527 tRowcnt pnRow / Write the revised row estimate here */

1528 ){

1529 Index *p = pBuilder->pNew->u.btree.pIndex;

1530 int nEq = pBuilder->pNew->u.btree.nEq;

1531 UnpackedRecord *pRec = pBuilder->pRec;

1532 u8 aff; /* Column affinity */

1533 int rc; /* Subfunction return code */

1534 tRowcnt a[2]; /* Statistics */

1535 int bOk;

1536

1537 assert( nEq>=1 );

1538 assert( nEq<=p->nColumn );

1539 assert( p->aSample!=0 );

1540 assert( p->nSample>0 );

1541 assert( pBuilder->nRecValid<nEq );

1542

1543 /* If values are not available for all fields of the index to the left

1544 ** of this one, no estimate can be made. Return SQLITE_NOTFOUND. */

1545 if( pBuilder->nRecValid<(nEq-1) ){

1546 return SQLITE_NOTFOUND;

1547 }

1548

1549 /* This is an optimization only. The call to sqlite3Stat4ProbeSetValue()

1550 ** below would return the same value. */

1551 if( nEq>=p->nColumn ){

1552 *pnRow = 1;

1553 return SQLITE_OK;

1554 }

1555

1556 aff = sqlite3IndexColumnAffinity(pParse->db, p, nEq-1);

1557 rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, aff, nEq-1, &bOk);

1558 pBuilder->pRec = pRec;

1559 if( rc!=SQLITE_OK ) return rc;

1560 if( bOk==0 ) return SQLITE_NOTFOUND;

1561 pBuilder->nRecValid = nEq;

1562

1563 whereKeyStats(pParse, p, pRec, 0, a);

1564 WHERETRACE(0x10,("equality scan regions: %d\n", (int)a[1]));

1565 *pnRow = a[1];

1566

1567 return rc;

1568 }

1569 #endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */

1570

1571 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4

1572 /*

1573 ** Estimate the number of rows that will be returned based on

1574 ** an IN constraint where the right-hand side of the IN operator

1575 ** is a list of values. Example:

1576 **

1577 ** WHERE x IN (1,2,3,4)

1578 **

1579 ** Write the estimated row count into *pnRow and return SQLITE_OK.

1580 ** If unable to make an estimate, leave *pnRow unchanged and return

1581 ** non-zero.

1582 **

1583 ** This routine can fail if it is unable to load a collating sequence

1584 ** required for string comparison, or if unable to allocate memory

1585 ** for a UTF conversion required for comparison. The error is stored

1586 ** in the pParse structure.

1587 */

1588 static int whereInScanEst(

1589 Parse pParse, / Parsing & code generating context */

1590 WhereLoopBuilder *pBuilder,

1591 ExprList pList, / The value list on the RHS of "x IN (v1,v2,v3,...)" */

1592 tRowcnt pnRow / Write the revised row estimate here */

1593 ){

1594 Index *p = pBuilder->pNew->u.btree.pIndex;

1595 i64 nRow0 = sqlite3LogEstToInt(p->aiRowLogEst[0]);

1596 int nRecValid = pBuilder->nRecValid;

1597 int rc = SQLITE_OK; /* Subfunction return code */

1598 tRowcnt nEst; /* Number of rows for a single term */

1599 tRowcnt nRowEst = 0; /* New estimate of the number of rows */

1600 int i; /* Loop counter */

1601

1602 assert( p->aSample!=0 );

1603 for(i=0; rc==SQLITE_OK && i<pList->nExpr; i++){

1604 nEst = nRow0;

1605 rc = whereEqualScanEst(pParse, pBuilder, pList->a[i].pExpr, &nEst);

1606 nRowEst += nEst;

1607 pBuilder->nRecValid = nRecValid;

1608 }

1609

1610 if( rc==SQLITE_OK ){

1611 if( nRowEst > nRow0 ) nRowEst = nRow0;

1612 *pnRow = nRowEst;

1613 WHERETRACE(0x10,("IN row estimate: est=%d\n", nRowEst));

1614 }

1615 assert( pBuilder->nRecValid==nRecValid );

1616 return rc;

1617 }

1618 #endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */

1619

1620

1621 #ifdef WHERETRACE_ENABLED

1622 /*

1623 ** Print the content of a WhereTerm object

1624 */

1625 static void whereTermPrint(WhereTerm *pTerm, int iTerm){

1626 if( pTerm==0 ){

1627 sqlite3DebugPrintf("TERM-%-3d NULL\n", iTerm);

1628 }else{

1629 char zType[4];

1630 memcpy(zType, "...", 4);

1631 if( pTerm->wtFlags & TERM_VIRTUAL ) zType[0] = 'V';

1632 if( pTerm->eOperator & WO_EQUIV ) zType[1] = 'E';

1633 if( ExprHasProperty(pTerm->pExpr, EP_FromJoin) ) zType[2] = 'L';

1634 sqlite3DebugPrintf(

1635 "TERM-%-3d %p %s cursor=%-3d prob=%-3d op=0x%03x wtFlags=0x%04x\n",

1636 iTerm, pTerm, zType, pTerm->leftCursor, pTerm->truthProb,

1637 pTerm->eOperator, pTerm->wtFlags);

1638 sqlite3TreeViewExpr(0, pTerm->pExpr, 0);

1639 }

1640 }

1641 #endif

1642

1643 #ifdef WHERETRACE_ENABLED

1644 /*

1645 ** Print a WhereLoop object for debugging purposes

1646 */

1647 static void whereLoopPrint(WhereLoop p, WhereClause pWC){

1648 WhereInfo *pWInfo = pWC->pWInfo;

1649 int nb = 1+(pWInfo->pTabList->nSrc+7)/8;

1650 struct SrcList_item *pItem = pWInfo->pTabList->a + p->iTab;

1651 Table *pTab = pItem->pTab;

1652 sqlite3DebugPrintf("%c%2d.%0llx.%0llx", p->cId,

1653 p->iTab, nb, p->maskSelf, nb, p->prereq);

1654 sqlite3DebugPrintf(" %12s",

1655 pItem->zAlias ? pItem->zAlias : pTab->zName);

1656 if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){

1657 const char *zName;

1658 if( p->u.btree.pIndex && (zName = p->u.btree.pIndex->zName)!=0 ){

1659 if( strncmp(zName, "sqlite_autoindex_", 17)==0 ){

1660 int i = sqlite3Strlen30(zName) - 1;

1661 while( zName[i]!='_' ) i--;

1662 zName += i;

1663 }

1664 sqlite3DebugPrintf(".%-16s %2d", zName, p->u.btree.nEq);

1665 }else{

1666 sqlite3DebugPrintf("%20s","");

1667 }

1668 }else{

1669 char *z;

1670 if( p->u.vtab.idxStr ){

1671 z = sqlite3_mprintf("(%d,\"%s\",%x)",

1672 p->u.vtab.idxNum, p->u.vtab.idxStr, p->u.vtab.omitMask);

1673 }else{

1674 z = sqlite3_mprintf("(%d,%x)", p->u.vtab.idxNum, p->u.vtab.omitMask);

1675 }

1676 sqlite3DebugPrintf(" %-19s", z);

1677 sqlite3_free(z);

1678 }

1679 if( p->wsFlags & WHERE_SKIPSCAN ){

1680 sqlite3DebugPrintf(" f %05x %d-%d", p->wsFlags, p->nLTerm,p->nSkip);

1681 }else{

1682 sqlite3DebugPrintf(" f %05x N %d", p->wsFlags, p->nLTerm);

1683 }

1684 sqlite3DebugPrintf(" cost %d,%d,%d\n", p->rSetup, p->rRun, p->nOut);

1685 if( p->nLTerm && (sqlite3WhereTrace & 0x100)!=0 ){

1686 int i;

1687 for(i=0; i<p->nLTerm; i++){

1688 whereTermPrint(p->aLTerm[i], i);

1689 }

1690 }

1691 }

1692 #endif

1693

1694 /*

1695 ** Convert bulk memory into a valid WhereLoop that can be passed

1696 ** to whereLoopClear harmlessly.

1697 */

1698 static void whereLoopInit(WhereLoop *p){

1699 p->aLTerm = p->aLTermSpace;

1700 p->nLTerm = 0;

1701 p->nLSlot = ArraySize(p->aLTermSpace);

1702 p->wsFlags = 0;

1703 }

1704

1705 /*

1706 ** Clear the WhereLoop.u union. Leave WhereLoop.pLTerm intact.

1707 */

1708 static void whereLoopClearUnion(sqlite3 db, WhereLoop p){

1709 if( p->wsFlags & (WHERE_VIRTUALTABLE\|WHERE_AUTO_INDEX) ){

1710 if( (p->wsFlags & WHERE_VIRTUALTABLE)!=0 && p->u.vtab.needFree ){

1711 sqlite3_free(p->u.vtab.idxStr);

1712 p->u.vtab.needFree = 0;

1713 p->u.vtab.idxStr = 0;

1714 }else if( (p->wsFlags & WHERE_AUTO_INDEX)!=0 && p->u.btree.pIndex!=0 ){

1715 sqlite3DbFree(db, p->u.btree.pIndex->zColAff);

1716 sqlite3DbFree(db, p->u.btree.pIndex);

1717 p->u.btree.pIndex = 0;

1718 }

1719 }

1720 }

1721

1722 /*

1723 ** Deallocate internal memory used by a WhereLoop object

1724 */

1725 static void whereLoopClear(sqlite3 db, WhereLoop p){

1726 if( p->aLTerm!=p->aLTermSpace ) sqlite3DbFree(db, p->aLTerm);

1727 whereLoopClearUnion(db, p);

1728 whereLoopInit(p);

1729 }

1730

1731 /*

1732 ** Increase the memory allocation for pLoop->aLTerm[] to be at least n.

1733 */

1734 static int whereLoopResize(sqlite3 db, WhereLoop p, int n){

1735 WhereTerm **paNew;

1736 if( p->nLSlot>=n ) return SQLITE_OK;

1737 n = (n+7)&~7;

1738 paNew = sqlite3DbMallocRaw(db, sizeof(p->aLTerm[0])*n);

1739 if( paNew==0 ) return SQLITE_NOMEM;

1740 memcpy(paNew, p->aLTerm, sizeof(p->aLTerm[0])*p->nLSlot);

1741 if( p->aLTerm!=p->aLTermSpace ) sqlite3DbFree(db, p->aLTerm);

1742 p->aLTerm = paNew;

1743 p->nLSlot = n;

1744 return SQLITE_OK;

1745 }

1746

1747 /*

1748 ** Transfer content from the second pLoop into the first.

1749 */

1750 static int whereLoopXfer(sqlite3 db, WhereLoop pTo, WhereLoop *pFrom){

1751 whereLoopClearUnion(db, pTo);

1752 if( whereLoopResize(db, pTo, pFrom->nLTerm) ){

1753 memset(&pTo->u, 0, sizeof(pTo->u));

1754 return SQLITE_NOMEM;

1755 }

1756 memcpy(pTo, pFrom, WHERE_LOOP_XFER_SZ);

1757 memcpy(pTo->aLTerm, pFrom->aLTerm, pTo->nLTerm*sizeof(pTo->aLTerm[0]));

1758 if( pFrom->wsFlags & WHERE_VIRTUALTABLE ){

1759 pFrom->u.vtab.needFree = 0;

1760 }else if( (pFrom->wsFlags & WHERE_AUTO_INDEX)!=0 ){

1761 pFrom->u.btree.pIndex = 0;

1762 }

1763 return SQLITE_OK;

1764 }

1765

1766 /*

1767 ** Delete a WhereLoop object

1768 */

1769 static void whereLoopDelete(sqlite3 db, WhereLoop p){

1770 whereLoopClear(db, p);

1771 sqlite3DbFree(db, p);

1772 }

1773

1774 /*

1775 ** Free a WhereInfo structure

1776 */

1777 static void whereInfoFree(sqlite3 db, WhereInfo pWInfo){

1778 if( ALWAYS(pWInfo) ){

1779 int i;

1780 for(i=0; i<pWInfo->nLevel; i++){

1781 WhereLevel *pLevel = &pWInfo->a[i];

1782 if( pLevel->pWLoop && (pLevel->pWLoop->wsFlags & WHERE_IN_ABLE) ){

1783 sqlite3DbFree(db, pLevel->u.in.aInLoop);

1784 }

1785 }

1786 sqlite3WhereClauseClear(&pWInfo->sWC);

1787 while( pWInfo->pLoops ){

1788 WhereLoop *p = pWInfo->pLoops;

1789 pWInfo->pLoops = p->pNextLoop;

1790 whereLoopDelete(db, p);

1791 }

1792 sqlite3DbFree(db, pWInfo);

1793 }

1794 }

1795

1796 /*

1797 ** Return TRUE if all of the following are true:

1798 **

1799 ** (1) X has the same or lower cost that Y

1800 ** (2) X is a proper subset of Y

1801 ** (3) X skips at least as many columns as Y

1802 **

1803 ** By "proper subset" we mean that X uses fewer WHERE clause terms

1804 ** than Y and that every WHERE clause term used by X is also used

1805 ** by Y.

1806 **

1807 ** If X is a proper subset of Y then Y is a better choice and ought

1808 ** to have a lower cost. This routine returns TRUE when that cost

1809 ** relationship is inverted and needs to be adjusted. The third rule

1810 ** was added because if X uses skip-scan less than Y it still might

1811 ** deserve a lower cost even if it is a proper subset of Y.

1812 */

1813 static int whereLoopCheaperProperSubset(

1814 const WhereLoop pX, / First WhereLoop to compare */

1815 const WhereLoop pY / Compare against this WhereLoop */

1816 ){

1817 int i, j;

1818 if( pX->nLTerm-pX->nSkip >= pY->nLTerm-pY->nSkip ){

1819 return 0; /* X is not a subset of Y */

1820 }

1821 if( pY->nSkip > pX->nSkip ) return 0;

1822 if( pX->rRun >= pY->rRun ){

1823 if( pX->rRun > pY->rRun ) return 0; /* X costs more than Y */

1824 if( pX->nOut > pY->nOut ) return 0; /* X costs more than Y */

1825 }

1826 for(i=pX->nLTerm-1; i>=0; i--){

1827 if( pX->aLTerm[i]==0 ) continue;

1828 for(j=pY->nLTerm-1; j>=0; j--){

1829 if( pY->aLTerm[j]==pX->aLTerm[i] ) break;

1830 }

1831 if( j<0 ) return 0; /* X not a subset of Y since term X[i] not used by Y */

1832 }

1833 return 1; /* All conditions meet */

1834 }

1835

1836 /*

1837 ** Try to adjust the cost of WhereLoop pTemplate upwards or downwards so

1838 ** that:

1839 **

1840 ** (1) pTemplate costs less than any other WhereLoops that are a proper

1841 ** subset of pTemplate

1842 **

1843 ** (2) pTemplate costs more than any other WhereLoops for which pTemplate

1844 ** is a proper subset.

1845 **

1846 ** To say "WhereLoop X is a proper subset of Y" means that X uses fewer

1847 ** WHERE clause terms than Y and that every WHERE clause term used by X is

1848 ** also used by Y.

1849 */

1850 static void whereLoopAdjustCost(const WhereLoop p, WhereLoop pTemplate){

1851 if( (pTemplate->wsFlags & WHERE_INDEXED)==0 ) return;

1852 for(; p; p=p->pNextLoop){

1853 if( p->iTab!=pTemplate->iTab ) continue;

1854 if( (p->wsFlags & WHERE_INDEXED)==0 ) continue;

1855 if( whereLoopCheaperProperSubset(p, pTemplate) ){

1856 /* Adjust pTemplate cost downward so that it is cheaper than its

1857 ** subset p. */

1858 WHERETRACE(0x80,("subset cost adjustment %d,%d to %d,%d\n",

1859 pTemplate->rRun, pTemplate->nOut, p->rRun, p->nOut-1));

1860 pTemplate->rRun = p->rRun;

1861 pTemplate->nOut = p->nOut - 1;

1862 }else if( whereLoopCheaperProperSubset(pTemplate, p) ){

1863 /* Adjust pTemplate cost upward so that it is costlier than p since

1864 ** pTemplate is a proper subset of p */

1865 WHERETRACE(0x80,("subset cost adjustment %d,%d to %d,%d\n",

1866 pTemplate->rRun, pTemplate->nOut, p->rRun, p->nOut+1));

1867 pTemplate->rRun = p->rRun;

1868 pTemplate->nOut = p->nOut + 1;

1869 }

1870 }

1871 }

1872

1873 /*

1874 ** Search the list of WhereLoops in *ppPrev looking for one that can be

1875 ** supplanted by pTemplate.

1876 **

1877 ** Return NULL if the WhereLoop list contains an entry that can supplant

1878 ** pTemplate, in other words if pTemplate does not belong on the list.

1879 **

1880 ** If pX is a WhereLoop that pTemplate can supplant, then return the

1881 ** link that points to pX.

1882 **

1883 ** If pTemplate cannot supplant any existing element of the list but needs

1884 ** to be added to the list, then return a pointer to the tail of the list.

1885 */

1886 static WhereLoop **whereLoopFindLesser(

1887 WhereLoop **ppPrev,

1888 const WhereLoop *pTemplate

1889 ){

1890 WhereLoop *p;

1891 for(p=(ppPrev); p; ppPrev=&p->pNextLoop, p=ppPrev){

1892 if( p->iTab!=pTemplate->iTab \|\| p->iSortIdx!=pTemplate->iSortIdx ){

1893 /* If either the iTab or iSortIdx values for two WhereLoop are different

1894 ** then those WhereLoops need to be considered separately. Neither is

1895 ** a candidate to replace the other. */

1896 continue;

1897 }

1898 /* In the current implementation, the rSetup value is either zero

1899 ** or the cost of building an automatic index (NlogN) and the NlogN

1900 ** is the same for compatible WhereLoops. */

1901 assert( p->rSetup==0 \|\| pTemplate->rSetup==0

1902 \|\| p->rSetup==pTemplate->rSetup );

1903

1904 /* whereLoopAddBtree() always generates and inserts the automatic index

1905 ** case first. Hence compatible candidate WhereLoops never have a larger

1906 ** rSetup. Call this SETUP-INVARIANT */

1907 assert( p->rSetup>=pTemplate->rSetup );

1908

1909 /* Any loop using an appliation-defined index (or PRIMARY KEY or

1910 ** UNIQUE constraint) with one or more == constraints is better

1911 ** than an automatic index. Unless it is a skip-scan. */

1912 if( (p->wsFlags & WHERE_AUTO_INDEX)!=0

1913 && (pTemplate->nSkip)==0

1914 && (pTemplate->wsFlags & WHERE_INDEXED)!=0

1915 && (pTemplate->wsFlags & WHERE_COLUMN_EQ)!=0

1916 && (p->prereq & pTemplate->prereq)==pTemplate->prereq

1917 ){

1918 break;

1919 }

1920

1921 /* If existing WhereLoop p is better than pTemplate, pTemplate can be

1922 ** discarded. WhereLoop p is better if:

1923 ** (1) p has no more dependencies than pTemplate, and

1924 ** (2) p has an equal or lower cost than pTemplate

1925 */

1926 if( (p->prereq & pTemplate->prereq)==p->prereq /* (1) */

1927 && p->rSetup<=pTemplate->rSetup /* (2a) */

1928 && p->rRun<=pTemplate->rRun /* (2b) */

1929 && p->nOut<=pTemplate->nOut /* (2c) */

1930 ){

1931 return 0; /* Discard pTemplate */

1932 }

1933

1934 /* If pTemplate is always better than p, then cause p to be overwritten

1935 ** with pTemplate. pTemplate is better than p if:

1936 ** (1) pTemplate has no more dependences than p, and

1937 ** (2) pTemplate has an equal or lower cost than p.

1938 */

1939 if( (p->prereq & pTemplate->prereq)==pTemplate->prereq /* (1) */

1940 && p->rRun>=pTemplate->rRun /* (2a) */

1941 && p->nOut>=pTemplate->nOut /* (2b) */

1942 ){

1943 assert( p->rSetup>=pTemplate->rSetup ); /* SETUP-INVARIANT above */

1944 break; /* Cause p to be overwritten by pTemplate */

1945 }

1946 }

1947 return ppPrev;

1948 }

1949

1950 /*

1951 ** Insert or replace a WhereLoop entry using the template supplied.

1952 **

1953 ** An existing WhereLoop entry might be overwritten if the new template

1954 ** is better and has fewer dependencies. Or the template will be ignored

1955 ** and no insert will occur if an existing WhereLoop is faster and has

1956 ** fewer dependencies than the template. Otherwise a new WhereLoop is

1957 ** added based on the template.

1958 **

1959 ** If pBuilder->pOrSet is not NULL then we care about only the

1960 ** prerequisites and rRun and nOut costs of the N best loops. That

1961 ** information is gathered in the pBuilder->pOrSet object. This special

1962 ** processing mode is used only for OR clause processing.

1963 **

1964 ** When accumulating multiple loops (when pBuilder->pOrSet is NULL) we

1965 ** still might overwrite similar loops with the new template if the

1966 ** new template is better. Loops may be overwritten if the following

1967 ** conditions are met:

1968 **

1969 ** (1) They have the same iTab.

1970 ** (2) They have the same iSortIdx.

1971 ** (3) The template has same or fewer dependencies than the current loop

1972 ** (4) The template has the same or lower cost than the current loop

1973 */

1974 static int whereLoopInsert(WhereLoopBuilder pBuilder, WhereLoop pTemplate){

1975 WhereLoop *ppPrev, p;

1976 WhereInfo *pWInfo = pBuilder->pWInfo;

1977 sqlite3 *db = pWInfo->pParse->db;

1978

1979 /* If pBuilder->pOrSet is defined, then only keep track of the costs

1980 ** and prereqs.

1981 */

1982 if( pBuilder->pOrSet!=0 ){

1983 if( pTemplate->nLTerm ){

1984 #if WHERETRACE_ENABLED

1985 u16 n = pBuilder->pOrSet->n;

1986 int x =

1987 #endif

1988 whereOrInsert(pBuilder->pOrSet, pTemplate->prereq, pTemplate->rRun,

1989 pTemplate->nOut);

1990 #if WHERETRACE_ENABLED /* 0x8 */

1991 if( sqlite3WhereTrace & 0x8 ){

1992 sqlite3DebugPrintf(x?" or-%d: ":" or-X: ", n);

1993 whereLoopPrint(pTemplate, pBuilder->pWC);

1994 }

1995 #endif

1996 }

1997 return SQLITE_OK;

1998 }

1999

2000 /* Look for an existing WhereLoop to replace with pTemplate

2001 */

2002 whereLoopAdjustCost(pWInfo->pLoops, pTemplate);

2003 ppPrev = whereLoopFindLesser(&pWInfo->pLoops, pTemplate);

2004

2005 if( ppPrev==0 ){

2006 /* There already exists a WhereLoop on the list that is better

2007 ** than pTemplate, so just ignore pTemplate */

2008 #if WHERETRACE_ENABLED /* 0x8 */

2009 if( sqlite3WhereTrace & 0x8 ){

2010 sqlite3DebugPrintf(" skip: ");

2011 whereLoopPrint(pTemplate, pBuilder->pWC);

2012 }

2013 #endif

2014 return SQLITE_OK;

2015 }else{

2016 p = *ppPrev;

2017 }

2018

2019 /* If we reach this point it means that either p[] should be overwritten

2020 ** with pTemplate[] if p[] exists, or if p==NULL then allocate a new

2021 ** WhereLoop and insert it.

2022 */

2023 #if WHERETRACE_ENABLED /* 0x8 */

2024 if( sqlite3WhereTrace & 0x8 ){

2025 if( p!=0 ){

2026 sqlite3DebugPrintf("replace: ");

2027 whereLoopPrint(p, pBuilder->pWC);

2028 }

2029 sqlite3DebugPrintf(" add: ");

2030 whereLoopPrint(pTemplate, pBuilder->pWC);

2031 }

2032 #endif

2033 if( p==0 ){

2034 /* Allocate a new WhereLoop to add to the end of the list */

2035 *ppPrev = p = sqlite3DbMallocRaw(db, sizeof(WhereLoop));

2036 if( p==0 ) return SQLITE_NOMEM;

2037 whereLoopInit(p);

2038 p->pNextLoop = 0;

2039 }else{

2040 /* We will be overwriting WhereLoop p[]. But before we do, first

2041 ** go through the rest of the list and delete any other entries besides

2042 ** p[] that are also supplated by pTemplate */

2043 WhereLoop **ppTail = &p->pNextLoop;

2044 WhereLoop *pToDel;

2045 while( *ppTail ){

2046 ppTail = whereLoopFindLesser(ppTail, pTemplate);

2047 if( ppTail==0 ) break;

2048 pToDel = *ppTail;

2049 if( pToDel==0 ) break;

2050 *ppTail = pToDel->pNextLoop;

2051 #if WHERETRACE_ENABLED /* 0x8 */

2052 if( sqlite3WhereTrace & 0x8 ){

2053 sqlite3DebugPrintf(" delete: ");

2054 whereLoopPrint(pToDel, pBuilder->pWC);

2055 }

2056 #endif

2057 whereLoopDelete(db, pToDel);

2058 }

2059 }

2060 whereLoopXfer(db, p, pTemplate);

2061 if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){

2062 Index *pIndex = p->u.btree.pIndex;

2063 if( pIndex && pIndex->tnum==0 ){

2064 p->u.btree.pIndex = 0;

2065 }

2066 }

2067 return SQLITE_OK;

2068 }

2069

2070 /*

2071 ** Adjust the WhereLoop.nOut value downward to account for terms of the

2072 ** WHERE clause that reference the loop but which are not used by an

2073 ** index.

2074 *

2075 ** For every WHERE clause term that is not used by the index

2076 ** and which has a truth probability assigned by one of the likelihood(),

2077 ** likely(), or unlikely() SQL functions, reduce the estimated number

2078 ** of output rows by the probability specified.

2079 **

2080 ** TUNING: For every WHERE clause term that is not used by the index

2081 ** and which does not have an assigned truth probability, heuristics

2082 ** described below are used to try to estimate the truth probability.

2083 ** TODO --> Perhaps this is something that could be improved by better

2084 ** table statistics.

2085 **

2086 ** Heuristic 1: Estimate the truth probability as 93.75%. The 93.75%

2087 ** value corresponds to -1 in LogEst notation, so this means decrement

2088 ** the WhereLoop.nOut field for every such WHERE clause term.

2089 **

2090 ** Heuristic 2: If there exists one or more WHERE clause terms of the

2091 ** form "x==EXPR" and EXPR is not a constant 0 or 1, then make sure the

2092 ** final output row estimate is no greater than 1/4 of the total number

2093 ** of rows in the table. In other words, assume that x==EXPR will filter

2094 ** out at least 3 out of 4 rows. If EXPR is -1 or 0 or 1, then maybe the

2095 ** "x" column is boolean or else -1 or 0 or 1 is a common default value

2096 ** on the "x" column and so in that case only cap the output row estimate

2097 ** at 1/2 instead of 1/4.

2098 */

2099 static void whereLoopOutputAdjust(

2100 WhereClause pWC, / The WHERE clause */

2101 WhereLoop pLoop, / The loop to adjust downward */

2102 LogEst nRow /* Number of rows in the entire table */

2103 ){

2104 WhereTerm pTerm, pX;

2105 Bitmask notAllowed = ~(pLoop->prereq\|pLoop->maskSelf);

2106 int i, j, k;

2107 LogEst iReduce = 0; /* pLoop->nOut should not exceed nRow-iReduce */

2108

2109 assert( (pLoop->wsFlags & WHERE_AUTO_INDEX)==0 );

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

2111 if( (pTerm->wtFlags & TERM_VIRTUAL)!=0 ) break;

2112 if( (pTerm->prereqAll & pLoop->maskSelf)==0 ) continue;

2113 if( (pTerm->prereqAll & notAllowed)!=0 ) continue;

2114 for(j=pLoop->nLTerm-1; j>=0; j--){

2115 pX = pLoop->aLTerm[j];

2116 if( pX==0 ) continue;

2117 if( pX==pTerm ) break;

2118 if( pX->iParent>=0 && (&pWC->a[pX->iParent])==pTerm ) break;

2119 }

2120 if( j<0 ){

2121 if( pTerm->truthProb<=0 ){

2122 /* If a truth probability is specified using the likelihood() hints,

2123 ** then use the probability provided by the application. */

2124 pLoop->nOut += pTerm->truthProb;

2125 }else{

2126 /* In the absence of explicit truth probabilities, use heuristics to

2127 ** guess a reasonable truth probability. */

2128 pLoop->nOut--;

2129 if( pTerm->eOperator&(WO_EQ\|WO_IS) ){

2130 Expr *pRight = pTerm->pExpr->pRight;

2131 testcase( pTerm->pExpr->op==TK_IS );

2132 if( sqlite3ExprIsInteger(pRight, &k) && k>=(-1) && k<=1 ){

2133 k = 10;

2134 }else{

2135 k = 20;

2136 }

2137 if( iReduce<k ) iReduce = k;

2138 }

2139 }

2140 }

2141 }

2142 if( pLoop->nOut > nRow-iReduce ) pLoop->nOut = nRow - iReduce;

2143 }

2144

2145 /*

2146 ** Adjust the cost C by the costMult facter T. This only occurs if

2147 ** compiled with -DSQLITE_ENABLE_COSTMULT

2148 */

2149 #ifdef SQLITE_ENABLE_COSTMULT

2150 # define ApplyCostMultiplier(C,T) C += T

2151 #else

2152 # define ApplyCostMultiplier(C,T)

2153 #endif

2154

2155 /*

2156 ** We have so far matched pBuilder->pNew->u.btree.nEq terms of the

2157 ** index pIndex. Try to match one more.

2158 **

2159 ** When this function is called, pBuilder->pNew->nOut contains the

2160 ** number of rows expected to be visited by filtering using the nEq

2161 ** terms only. If it is modified, this value is restored before this

2162 ** function returns.

2163 **

2164 ** If pProbe->tnum==0, that means pIndex is a fake index used for the

2165 ** INTEGER PRIMARY KEY.

2166 */

2167 static int whereLoopAddBtreeIndex(

2168 WhereLoopBuilder pBuilder, / The WhereLoop factory */

2169 struct SrcList_item pSrc, / FROM clause term being analyzed */

2170 Index pProbe, / An index on pSrc */

2171 LogEst nInMul /* log(Number of iterations due to IN) */

2172 ){

2173 WhereInfo pWInfo = pBuilder->pWInfo; / WHERE analyse context */

2174 Parse pParse = pWInfo->pParse; / Parsing context */

2175 sqlite3 db = pParse->db; / Database connection malloc context */

2176 WhereLoop pNew; / Template WhereLoop under construction */

2177 WhereTerm pTerm; / A WhereTerm under consideration */

2178 int opMask; /* Valid operators for constraints */

2179 WhereScan scan; /* Iterator for WHERE terms */

2180 Bitmask saved_prereq; /* Original value of pNew->prereq */

2181 u16 saved_nLTerm; /* Original value of pNew->nLTerm */

2182 u16 saved_nEq; /* Original value of pNew->u.btree.nEq */

2183 u16 saved_nSkip; /* Original value of pNew->nSkip */

2184 u32 saved_wsFlags; /* Original value of pNew->wsFlags */

2185 LogEst saved_nOut; /* Original value of pNew->nOut */

2186 int rc = SQLITE_OK; /* Return code */

2187 LogEst rSize; /* Number of rows in the table */

2188 LogEst rLogSize; /* Logarithm of table size */

2189 WhereTerm pTop = 0, pBtm = 0; /* Top and bottom range constraints */

2190

2191 pNew = pBuilder->pNew;

2192 if( db->mallocFailed ) return SQLITE_NOMEM;

2193

2194 assert( (pNew->wsFlags & WHERE_VIRTUALTABLE)==0 );

2195 assert( (pNew->wsFlags & WHERE_TOP_LIMIT)==0 );

2196 if( pNew->wsFlags & WHERE_BTM_LIMIT ){

2197 opMask = WO_LT\|WO_LE;

2198 }else if( /pProbe->tnum<=0 \|\|/ (pSrc->fg.jointype & JT_LEFT)!=0 ){

2199 opMask = WO_EQ\|WO_IN\|WO_GT\|WO_GE\|WO_LT\|WO_LE;

2200 }else{

2201 opMask = WO_EQ\|WO_IN\|WO_GT\|WO_GE\|WO_LT\|WO_LE\|WO_ISNULL\|WO_IS;

2202 }

2203 if( pProbe->bUnordered ) opMask &= ~(WO_GT\|WO_GE\|WO_LT\|WO_LE);

2204

2205 assert( pNew->u.btree.nEq<pProbe->nColumn );

2206

2207 saved_nEq = pNew->u.btree.nEq;

2208 saved_nSkip = pNew->nSkip;

2209 saved_nLTerm = pNew->nLTerm;

2210 saved_wsFlags = pNew->wsFlags;

2211 saved_prereq = pNew->prereq;

2212 saved_nOut = pNew->nOut;

2213 pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, saved_nEq,

2214 opMask, pProbe);

2215 pNew->rSetup = 0;

2216 rSize = pProbe->aiRowLogEst[0];

2217 rLogSize = estLog(rSize);

2218 for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){

2219 u16 eOp = pTerm->eOperator; /* Shorthand for pTerm->eOperator */

2220 LogEst rCostIdx;

2221 LogEst nOutUnadjusted; /* nOut before IN() and WHERE adjustments */

2222 int nIn = 0;

2223 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4

2224 int nRecValid = pBuilder->nRecValid;

2225 #endif

2226 if( (eOp==WO_ISNULL \|\| (pTerm->wtFlags&TERM_VNULL)!=0)

2227 && indexColumnNotNull(pProbe, saved_nEq)

2228 ){

2229 continue; /* ignore IS [NOT] NULL constraints on NOT NULL columns */

2230 }

2231 if( pTerm->prereqRight & pNew->maskSelf ) continue;

2232

2233 /* Do not allow the upper bound of a LIKE optimization range constraint

2234 ** to mix with a lower range bound from some other source */

2235 if( pTerm->wtFlags & TERM_LIKEOPT && pTerm->eOperator==WO_LT ) continue;

2236

2237 pNew->wsFlags = saved_wsFlags;

2238 pNew->u.btree.nEq = saved_nEq;

2239 pNew->nLTerm = saved_nLTerm;

2240 if( whereLoopResize(db, pNew, pNew->nLTerm+1) ) break; /* OOM */

2241 pNew->aLTerm[pNew->nLTerm++] = pTerm;

2242 pNew->prereq = (saved_prereq \| pTerm->prereqRight) & ~pNew->maskSelf;

2243

2244 assert( nInMul==0

2245 \|\| (pNew->wsFlags & WHERE_COLUMN_NULL)!=0

2246 \|\| (pNew->wsFlags & WHERE_COLUMN_IN)!=0

2247 \|\| (pNew->wsFlags & WHERE_SKIPSCAN)!=0

2248 );

2249

2250 if( eOp & WO_IN ){

2251 Expr *pExpr = pTerm->pExpr;

2252 pNew->wsFlags \|= WHERE_COLUMN_IN;

2253 if( ExprHasProperty(pExpr, EP_xIsSelect) ){

2254 /* "x IN (SELECT ...)": TUNING: the SELECT returns 25 rows */

2255 nIn = 46; assert( 46==sqlite3LogEst(25) );

2256 }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){

2257 /* "x IN (value, value, ...)" */

2258 nIn = sqlite3LogEst(pExpr->x.pList->nExpr);

2259 }

2260 assert( nIn>0 ); /* RHS always has 2 or more terms... The parser

2261 ** changes "x IN (?)" into "x=?". */

2262

2263 }else if( eOp & (WO_EQ\|WO_IS) ){

2264 int iCol = pProbe->aiColumn[saved_nEq];

2265 pNew->wsFlags \|= WHERE_COLUMN_EQ;

2266 assert( saved_nEq==pNew->u.btree.nEq );

2267 if( iCol==XN_ROWID

2268 \|\| (iCol>0 && nInMul==0 && saved_nEq==pProbe->nKeyCol-1)

2269 ){

2270 if( iCol>=0 && pProbe->uniqNotNull==0 ){

2271 pNew->wsFlags \|= WHERE_UNQ_WANTED;

2272 }else{

2273 pNew->wsFlags \|= WHERE_ONEROW;

2274 }

2275 }

2276 }else if( eOp & WO_ISNULL ){

2277 pNew->wsFlags \|= WHERE_COLUMN_NULL;

2278 }else if( eOp & (WO_GT\|WO_GE) ){

2279 testcase( eOp & WO_GT );

2280 testcase( eOp & WO_GE );

2281 pNew->wsFlags \|= WHERE_COLUMN_RANGE\|WHERE_BTM_LIMIT;

2282 pBtm = pTerm;

2283 pTop = 0;

2284 if( pTerm->wtFlags & TERM_LIKEOPT ){

2285 /* Range contraints that come from the LIKE optimization are

2286 ** always used in pairs. */

2287 pTop = &pTerm[1];

2288 assert( (pTop-(pTerm->pWC->a))<pTerm->pWC->nTerm );

2289 assert( pTop->wtFlags & TERM_LIKEOPT );

2290 assert( pTop->eOperator==WO_LT );

2291 if( whereLoopResize(db, pNew, pNew->nLTerm+1) ) break; /* OOM */

2292 pNew->aLTerm[pNew->nLTerm++] = pTop;

2293 pNew->wsFlags \|= WHERE_TOP_LIMIT;

2294 }

2295 }else{

2296 assert( eOp & (WO_LT\|WO_LE) );

2297 testcase( eOp & WO_LT );

2298 testcase( eOp & WO_LE );

2299 pNew->wsFlags \|= WHERE_COLUMN_RANGE\|WHERE_TOP_LIMIT;

2300 pTop = pTerm;

2301 pBtm = (pNew->wsFlags & WHERE_BTM_LIMIT)!=0 ?

2302 pNew->aLTerm[pNew->nLTerm-2] : 0;

2303 }

2304

2305 /* At this point pNew->nOut is set to the number of rows expected to

2306 ** be visited by the index scan before considering term pTerm, or the

2307 ** values of nIn and nInMul. In other words, assuming that all

2308 ** "x IN(...)" terms are replaced with "x = ?". This block updates

2309 ** the value of pNew->nOut to account for pTerm (but not nIn/nInMul). */

2310 assert( pNew->nOut==saved_nOut );

2311 if( pNew->wsFlags & WHERE_COLUMN_RANGE ){

2312 /* Adjust nOut using stat3/stat4 data. Or, if there is no stat3/stat4

2313 ** data, using some other estimate. */

2314 whereRangeScanEst(pParse, pBuilder, pBtm, pTop, pNew);

2315 }else{

2316 int nEq = ++pNew->u.btree.nEq;

2317 assert( eOp & (WO_ISNULL\|WO_EQ\|WO_IN\|WO_IS) );

2318

2319 assert( pNew->nOut==saved_nOut );

2320 if( pTerm->truthProb<=0 && pProbe->aiColumn[saved_nEq]>=0 ){

2321 assert( (eOp & WO_IN) \|\| nIn==0 );

2322 testcase( eOp & WO_IN );

2323 pNew->nOut += pTerm->truthProb;

2324 pNew->nOut -= nIn;

2325 }else{

2326 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4

2327 tRowcnt nOut = 0;

2328 if( nInMul==0

2329 && pProbe->nSample

2330 && pNew->u.btree.nEq<=pProbe->nSampleCol

2331 && ((eOp & WO_IN)==0 \|\| !ExprHasProperty(pTerm->pExpr, EP_xIsSelect))

2332 ){

2333 Expr *pExpr = pTerm->pExpr;

2334 if( (eOp & (WO_EQ\|WO_ISNULL\|WO_IS))!=0 ){

2335 testcase( eOp & WO_EQ );

2336 testcase( eOp & WO_IS );

2337 testcase( eOp & WO_ISNULL );

2338 rc = whereEqualScanEst(pParse, pBuilder, pExpr->pRight, &nOut);

2339 }else{

2340 rc = whereInScanEst(pParse, pBuilder, pExpr->x.pList, &nOut);

2341 }

2342 if( rc==SQLITE_NOTFOUND ) rc = SQLITE_OK;

2343 if( rc!=SQLITE_OK ) break; /* Jump out of the pTerm loop */

2344 if( nOut ){

2345 pNew->nOut = sqlite3LogEst(nOut);

2346 if( pNew->nOut>saved_nOut ) pNew->nOut = saved_nOut;

2347 pNew->nOut -= nIn;

2348 }

2349 }

2350 if( nOut==0 )

2351 #endif

2352 {

2353 pNew->nOut += (pProbe->aiRowLogEst[nEq] - pProbe->aiRowLogEst[nEq-1]);

2354 if( eOp & WO_ISNULL ){

2355 /* TUNING: If there is no likelihood() value, assume that a

2356 ** "col IS NULL" expression matches twice as many rows

2357 ** as (col=?). */

2358 pNew->nOut += 10;

2359 }

2360 }

2361 }

2362 }

2363

2364 /* Set rCostIdx to the cost of visiting selected rows in index. Add

2365 ** it to pNew->rRun, which is currently set to the cost of the index

2366 ** seek only. Then, if this is a non-covering index, add the cost of

2367 ** visiting the rows in the main table. */

2368 rCostIdx = pNew->nOut + 1 + (15*pProbe->szIdxRow)/pSrc->pTab->szTabRow;

2369 pNew->rRun = sqlite3LogEstAdd(rLogSize, rCostIdx);

2370 if( (pNew->wsFlags & (WHERE_IDX_ONLY\|WHERE_IPK))==0 ){

2371 pNew->rRun = sqlite3LogEstAdd(pNew->rRun, pNew->nOut + 16);

2372 }

2373 ApplyCostMultiplier(pNew->rRun, pProbe->pTable->costMult);

2374

2375 nOutUnadjusted = pNew->nOut;

2376 pNew->rRun += nInMul + nIn;

2377 pNew->nOut += nInMul + nIn;

2378 whereLoopOutputAdjust(pBuilder->pWC, pNew, rSize);

2379 rc = whereLoopInsert(pBuilder, pNew);

2380

2381 if( pNew->wsFlags & WHERE_COLUMN_RANGE ){

2382 pNew->nOut = saved_nOut;

2383 }else{

2384 pNew->nOut = nOutUnadjusted;

2385 }

2386

2387 if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0

2388 && pNew->u.btree.nEq<pProbe->nColumn

2389 ){

2390 whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul+nIn);

2391 }

2392 pNew->nOut = saved_nOut;

2393 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4

2394 pBuilder->nRecValid = nRecValid;

2395 #endif

2396 }

2397 pNew->prereq = saved_prereq;

2398 pNew->u.btree.nEq = saved_nEq;

2399 pNew->nSkip = saved_nSkip;

2400 pNew->wsFlags = saved_wsFlags;

2401 pNew->nOut = saved_nOut;

2402 pNew->nLTerm = saved_nLTerm;

2403

2404 /* Consider using a skip-scan if there are no WHERE clause constraints

2405 ** available for the left-most terms of the index, and if the average

2406 ** number of repeats in the left-most terms is at least 18.

2407 **

2408 ** The magic number 18 is selected on the basis that scanning 17 rows

2409 ** is almost always quicker than an index seek (even though if the index

2410 ** contains fewer than 2^17 rows we assume otherwise in other parts of

2411 ** the code). And, even if it is not, it should not be too much slower.

2412 ** On the other hand, the extra seeks could end up being significantly

2413 ** more expensive. */

2414 assert( 42==sqlite3LogEst(18) );

2415 if( saved_nEq==saved_nSkip

2416 && saved_nEq+1<pProbe->nKeyCol

2417 && pProbe->noSkipScan==0

2418 && pProbe->aiRowLogEst[saved_nEq+1]>=42 /* TUNING: Minimum for skip-scan */

2419 && (rc = whereLoopResize(db, pNew, pNew->nLTerm+1))==SQLITE_OK

2420 ){

2421 LogEst nIter;

2422 pNew->u.btree.nEq++;

2423 pNew->nSkip++;

2424 pNew->aLTerm[pNew->nLTerm++] = 0;

2425 pNew->wsFlags \|= WHERE_SKIPSCAN;

2426 nIter = pProbe->aiRowLogEst[saved_nEq] - pProbe->aiRowLogEst[saved_nEq+1];

2427 pNew->nOut -= nIter;

2428 /* TUNING: Because uncertainties in the estimates for skip-scan queries,

2429 ** add a 1.375 fudge factor to make skip-scan slightly less likely. */

2430 nIter += 5;

2431 whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nIter + nInMul);

2432 pNew->nOut = saved_nOut;

2433 pNew->u.btree.nEq = saved_nEq;

2434 pNew->nSkip = saved_nSkip;

2435 pNew->wsFlags = saved_wsFlags;

2436 }

2437

2438 return rc;

2439 }

2440

2441 /*

2442 ** Return True if it is possible that pIndex might be useful in

2443 ** implementing the ORDER BY clause in pBuilder.

2444 **

2445 ** Return False if pBuilder does not contain an ORDER BY clause or

2446 ** if there is no way for pIndex to be useful in implementing that

2447 ** ORDER BY clause.

2448 */

2449 static int indexMightHelpWithOrderBy(

2450 WhereLoopBuilder *pBuilder,

2451 Index *pIndex,

2452 int iCursor

2453 ){

2454 ExprList *pOB;

2455 ExprList *aColExpr;

2456 int ii, jj;

2457

2458 if( pIndex->bUnordered ) return 0;

2459 if( (pOB = pBuilder->pWInfo->pOrderBy)==0 ) return 0;

2460 for(ii=0; ii<pOB->nExpr; ii++){

2461 Expr *pExpr = sqlite3ExprSkipCollate(pOB->a[ii].pExpr);

2462 if( pExpr->op==TK_COLUMN && pExpr->iTable==iCursor ){

2463 if( pExpr->iColumn<0 ) return 1;

2464 for(jj=0; jj<pIndex->nKeyCol; jj++){

2465 if( pExpr->iColumn==pIndex->aiColumn[jj] ) return 1;

2466 }

2467 }else if( (aColExpr = pIndex->aColExpr)!=0 ){

2468 for(jj=0; jj<pIndex->nKeyCol; jj++){

2469 if( pIndex->aiColumn[jj]!=XN_EXPR ) continue;

2470 if( sqlite3ExprCompare(pExpr,aColExpr->a[jj].pExpr,iCursor)==0 ){

2471 return 1;

2472 }

2473 }

2474 }

2475 }

2476 return 0;

2477 }

2478

2479 /*

2480 ** Return a bitmask where 1s indicate that the corresponding column of

2481 ** the table is used by an index. Only the first 63 columns are considered.

2482 */

2483 static Bitmask columnsInIndex(Index *pIdx){

2484 Bitmask m = 0;

2485 int j;

2486 for(j=pIdx->nColumn-1; j>=0; j--){

2487 int x = pIdx->aiColumn[j];

2488 if( x>=0 ){

2489 testcase( x==BMS-1 );

2490 testcase( x==BMS-2 );

2491 if( x<BMS-1 ) m \|= MASKBIT(x);

2492 }

2493 }

2494 return m;

2495 }

2496

2497 /* Check to see if a partial index with pPartIndexWhere can be used

2498 ** in the current query. Return true if it can be and false if not.

2499 */

2500 static int whereUsablePartialIndex(int iTab, WhereClause pWC, Expr pWhere){

2501 int i;

2502 WhereTerm *pTerm;

2503 while( pWhere->op==TK_AND ){

2504 if( !whereUsablePartialIndex(iTab,pWC,pWhere->pLeft) ) return 0;

2505 pWhere = pWhere->pRight;

2506 }

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

2508 Expr *pExpr = pTerm->pExpr;

2509 if( sqlite3ExprImpliesExpr(pExpr, pWhere, iTab)

2510 && (!ExprHasProperty(pExpr, EP_FromJoin) \|\| pExpr->iRightJoinTable==iTab)

2511 ){

2512 return 1;

2513 }

2514 }

2515 return 0;

2516 }

2517

2518 /*

2519 ** Add all WhereLoop objects for a single table of the join where the table

2520 ** is idenfied by pBuilder->pNew->iTab. That table is guaranteed to be

2521 ** a b-tree table, not a virtual table.

2522 **

2523 ** The costs (WhereLoop.rRun) of the b-tree loops added by this function

2524 ** are calculated as follows:

2525 **

2526 ** For a full scan, assuming the table (or index) contains nRow rows:

2527 **

2528 ** cost = nRow * 3.0 // full-table scan

2529 ** cost = nRow * K // scan of covering index

2530 ** cost = nRow * (K+3.0) // scan of non-covering index

2531 **

2532 ** where K is a value between 1.1 and 3.0 set based on the relative

2533 ** estimated average size of the index and table records.

2534 **

2535 ** For an index scan, where nVisit is the number of index rows visited

2536 ** by the scan, and nSeek is the number of seek operations required on

2537 ** the index b-tree:

2538 **

2539 ** cost = nSeek * (log(nRow) + K * nVisit) // covering index

2540 ** cost = nSeek * (log(nRow) + (K+3.0) * nVisit) // non-covering index

2541 **

2542 ** Normally, nSeek is 1. nSeek values greater than 1 come about if the

2543 ** WHERE clause includes "x IN (....)" terms used in place of "x=?". Or when

2544 ** implicit "x IN (SELECT x FROM tbl)" terms are added for skip-scans.

2545 **

2546 ** The estimated values (nRow, nVisit, nSeek) often contain a large amount

2547 ** of uncertainty. For this reason, scoring is designed to pick plans that

2548 ** "do the least harm" if the estimates are inaccurate. For example, a

2549 ** log(nRow) factor is omitted from a non-covering index scan in order to

2550 ** bias the scoring in favor of using an index, since the worst-case

2551 ** performance of using an index is far better than the worst-case performance

2552 ** of a full table scan.

2553 */

2554 static int whereLoopAddBtree(

2555 WhereLoopBuilder pBuilder, / WHERE clause information */

2556 Bitmask mExtra /* Extra prerequesites for using this table */

2557 ){

2558 WhereInfo pWInfo; / WHERE analysis context */

2559 Index pProbe; / An index we are evaluating */

2560 Index sPk; /* A fake index object for the primary key */

2561 LogEst aiRowEstPk[2]; /* The aiRowLogEst[] value for the sPk index */

2562 i16 aiColumnPk = -1; /* The aColumn[] value for the sPk index */

2563 SrcList pTabList; / The FROM clause */

2564 struct SrcList_item pSrc; / The FROM clause btree term to add */

2565 WhereLoop pNew; / Template WhereLoop object */

2566 int rc = SQLITE_OK; /* Return code */

2567 int iSortIdx = 1; /* Index number */

2568 int b; /* A boolean value */

2569 LogEst rSize; /* number of rows in the table */

2570 LogEst rLogSize; /* Logarithm of the number of rows in the table */

2571 WhereClause pWC; / The parsed WHERE clause */

2572 Table pTab; / Table being queried */

2573

2574 pNew = pBuilder->pNew;

2575 pWInfo = pBuilder->pWInfo;

2576 pTabList = pWInfo->pTabList;

2577 pSrc = pTabList->a + pNew->iTab;

2578 pTab = pSrc->pTab;

2579 pWC = pBuilder->pWC;

2580 assert( !IsVirtual(pSrc->pTab) );

2581

2582 if( pSrc->pIBIndex ){

2583 /* An INDEXED BY clause specifies a particular index to use */

2584 pProbe = pSrc->pIBIndex;

2585 }else if( !HasRowid(pTab) ){

2586 pProbe = pTab->pIndex;

2587 }else{

2588 /* There is no INDEXED BY clause. Create a fake Index object in local

2589 ** variable sPk to represent the rowid primary key index. Make this

2590 ** fake index the first in a chain of Index objects with all of the real

2591 ** indices to follow */

2592 Index pFirst; / First of real indices on the table */

2593 memset(&sPk, 0, sizeof(Index));

2594 sPk.nKeyCol = 1;

2595 sPk.nColumn = 1;

2596 sPk.aiColumn = &aiColumnPk;

2597 sPk.aiRowLogEst = aiRowEstPk;

2598 sPk.onError = OE_Replace;

2599 sPk.pTable = pTab;

2600 sPk.szIdxRow = pTab->szTabRow;

2601 aiRowEstPk[0] = pTab->nRowLogEst;

2602 aiRowEstPk[1] = 0;

2603 pFirst = pSrc->pTab->pIndex;

2604 if( pSrc->fg.notIndexed==0 ){

2605 /* The real indices of the table are only considered if the

2606 ** NOT INDEXED qualifier is omitted from the FROM clause */

2607 sPk.pNext = pFirst;

2608 }

2609 pProbe = &sPk;

2610 }

2611 rSize = pTab->nRowLogEst;

2612 rLogSize = estLog(rSize);

2613

2614 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX

2615 /* Automatic indexes */

2616 if( !pBuilder->pOrSet /* Not part of an OR optimization */

2617 && (pWInfo->wctrlFlags & WHERE_NO_AUTOINDEX)==0

2618 && (pWInfo->pParse->db->flags & SQLITE_AutoIndex)!=0

2619 && pSrc->pIBIndex==0 /* Has no INDEXED BY clause */

2620 && !pSrc->fg.notIndexed /* Has no NOT INDEXED clause */

2621 && HasRowid(pTab) /* Not WITHOUT ROWID table. (FIXME: Why not?) */

2622 && !pSrc->fg.isCorrelated /* Not a correlated subquery */

2623 && !pSrc->fg.isRecursive /* Not a recursive common table expression. */

2624 ){

2625 /* Generate auto-index WhereLoops */

2626 WhereTerm *pTerm;

2627 WhereTerm *pWCEnd = pWC->a + pWC->nTerm;

2628 for(pTerm=pWC->a; rc==SQLITE_OK && pTerm<pWCEnd; pTerm++){

2629 if( pTerm->prereqRight & pNew->maskSelf ) continue;

2630 if( termCanDriveIndex(pTerm, pSrc, 0) ){

2631 pNew->u.btree.nEq = 1;

2632 pNew->nSkip = 0;

2633 pNew->u.btree.pIndex = 0;

2634 pNew->nLTerm = 1;

2635 pNew->aLTerm[0] = pTerm;

2636 /* TUNING: One-time cost for computing the automatic index is

2637 ** estimated to be XNlog2(N) where N is the number of rows in

2638 ** the table being indexed and where X is 7 (LogEst=28) for normal

2639 ** tables or 1.375 (LogEst=4) for views and subqueries. The value

2640 ** of X is smaller for views and subqueries so that the query planner

2641 ** will be more aggressive about generating automatic indexes for

2642 ** those objects, since there is no opportunity to add schema

2643 ** indexes on subqueries and views. */

2644 pNew->rSetup = rLogSize + rSize + 4;

2645 if( pTab->pSelect==0 && (pTab->tabFlags & TF_Ephemeral)==0 ){

2646 pNew->rSetup += 24;

2647 }

2648 ApplyCostMultiplier(pNew->rSetup, pTab->costMult);

2649 /* TUNING: Each index lookup yields 20 rows in the table. This

2650 ** is more than the usual guess of 10 rows, since we have no way

2651 ** of knowing how selective the index will ultimately be. It would

2652 ** not be unreasonable to make this value much larger. */

2653 pNew->nOut = 43; assert( 43==sqlite3LogEst(20) );

2654 pNew->rRun = sqlite3LogEstAdd(rLogSize,pNew->nOut);

2655 pNew->wsFlags = WHERE_AUTO_INDEX;

2656 pNew->prereq = mExtra \| pTerm->prereqRight;

2657 rc = whereLoopInsert(pBuilder, pNew);

2658 }

2659 }

2660 }

2661 #endif /* SQLITE_OMIT_AUTOMATIC_INDEX */

2662

2663 /* Loop over all indices

2664 */

2665 for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext, iSortIdx++){

2666 if( pProbe->pPartIdxWhere!=0

2667 && !whereUsablePartialIndex(pSrc->iCursor, pWC, pProbe->pPartIdxWhere) ){

2668 testcase( pNew->iTab!=pSrc->iCursor ); /* See ticket [98d973b8f5] */

2669 continue; /* Partial index inappropriate for this query */

2670 }

2671 rSize = pProbe->aiRowLogEst[0];

2672 pNew->u.btree.nEq = 0;

2673 pNew->nSkip = 0;

2674 pNew->nLTerm = 0;

2675 pNew->iSortIdx = 0;

2676 pNew->rSetup = 0;

2677 pNew->prereq = mExtra;

2678 pNew->nOut = rSize;

2679 pNew->u.btree.pIndex = pProbe;

2680 b = indexMightHelpWithOrderBy(pBuilder, pProbe, pSrc->iCursor);

2681 /* The ONEPASS_DESIRED flags never occurs together with ORDER BY */

2682 assert( (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 \|\| b==0 );

2683 if( pProbe->tnum<=0 ){

2684 /* Integer primary key index */

2685 pNew->wsFlags = WHERE_IPK;

2686

2687 /* Full table scan */

2688 pNew->iSortIdx = b ? iSortIdx : 0;

2689 /* TUNING: Cost of full table scan is (N3.0). /

2690 pNew->rRun = rSize + 16;

2691 ApplyCostMultiplier(pNew->rRun, pTab->costMult);

2692 whereLoopOutputAdjust(pWC, pNew, rSize);

2693 rc = whereLoopInsert(pBuilder, pNew);

2694 pNew->nOut = rSize;

2695 if( rc ) break;

2696 }else{

2697 Bitmask m;

2698 if( pProbe->isCovering ){

2699 pNew->wsFlags = WHERE_IDX_ONLY \| WHERE_INDEXED;

2700 m = 0;

2701 }else{

2702 m = pSrc->colUsed & ~columnsInIndex(pProbe);

2703 pNew->wsFlags = (m==0) ? (WHERE_IDX_ONLY\|WHERE_INDEXED) : WHERE_INDEXED;

2704 }

2705

2706 /* Full scan via index */

2707 if( b

2708 \|\| !HasRowid(pTab)

2709 \|\| ( m==0

2710 && pProbe->bUnordered==0

2711 && (pProbe->szIdxRow<pTab->szTabRow)

2712 && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0

2713 && sqlite3GlobalConfig.bUseCis

2714 && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)

2715 )

2716 ){

2717 pNew->iSortIdx = b ? iSortIdx : 0;

2718

2719 /* The cost of visiting the index rows is N*K, where K is

2720 ** between 1.1 and 3.0, depending on the relative sizes of the

2721 ** index and table rows. If this is a non-covering index scan,

2722 ** also add the cost of visiting table rows (N3.0). /

2723 pNew->rRun = rSize + 1 + (15*pProbe->szIdxRow)/pTab->szTabRow;

2724 if( m!=0 ){

2725 pNew->rRun = sqlite3LogEstAdd(pNew->rRun, rSize+16);

2726 }

2727 ApplyCostMultiplier(pNew->rRun, pTab->costMult);

2728 whereLoopOutputAdjust(pWC, pNew, rSize);

2729 rc = whereLoopInsert(pBuilder, pNew);

2730 pNew->nOut = rSize;

2731 if( rc ) break;

2732 }

2733 }

2734

2735 rc = whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 0);

2736 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4

2737 sqlite3Stat4ProbeFree(pBuilder->pRec);

2738 pBuilder->nRecValid = 0;

2739 pBuilder->pRec = 0;

2740 #endif

2741

2742 /* If there was an INDEXED BY clause, then only that one index is

2743 ** considered. */

2744 if( pSrc->pIBIndex ) break;

2745 }

2746 return rc;

2747 }

2748

2749 #ifndef SQLITE_OMIT_VIRTUALTABLE

2750 /*

2751 ** Add all WhereLoop objects for a table of the join identified by

2752 ** pBuilder->pNew->iTab. That table is guaranteed to be a virtual table.

2753 **

2754 ** If there are no LEFT or CROSS JOIN joins in the query, both mExtra and

2755 ** mUnusable are set to 0. Otherwise, mExtra is a mask of all FROM clause

2756 ** entries that occur before the virtual table in the FROM clause and are

2757 ** separated from it by at least one LEFT or CROSS JOIN. Similarly, the

2758 ** mUnusable mask contains all FROM clause entries that occur after the

2759 ** virtual table and are separated from it by at least one LEFT or

2760 ** CROSS JOIN.

2761 **

2762 ** For example, if the query were:

2763 **

2764 ** ... FROM t1, t2 LEFT JOIN t3, t4, vt CROSS JOIN t5, t6;

2765 **

2766 ** then mExtra corresponds to (t1, t2) and mUnusable to (t5, t6).

2767 **

2768 ** All the tables in mExtra must be scanned before the current virtual

2769 ** table. So any terms for which all prerequisites are satisfied by

2770 ** mExtra may be specified as "usable" in all calls to xBestIndex.

2771 ** Conversely, all tables in mUnusable must be scanned after the current

2772 ** virtual table, so any terms for which the prerequisites overlap with

2773 ** mUnusable should always be configured as "not-usable" for xBestIndex.

2774 */

2775 static int whereLoopAddVirtual(

2776 WhereLoopBuilder pBuilder, / WHERE clause information */

2777 Bitmask mExtra, /* Tables that must be scanned before this one */

2778 Bitmask mUnusable /* Tables that must be scanned after this one */

2779 ){

2780 WhereInfo pWInfo; / WHERE analysis context */

2781 Parse pParse; / The parsing context */

2782 WhereClause pWC; / The WHERE clause */

2783 struct SrcList_item pSrc; / The FROM clause term to search */

2784 Table *pTab;

2785 sqlite3 *db;

2786 sqlite3_index_info *pIdxInfo;

2787 struct sqlite3_index_constraint *pIdxCons;

2788 struct sqlite3_index_constraint_usage *pUsage;

2789 WhereTerm *pTerm;

2790 int i, j;

2791 int iTerm, mxTerm;

2792 int nConstraint;

2793 int seenIn = 0; /* True if an IN operator is seen */

2794 int seenVar = 0; /* True if a non-constant constraint is seen */

2795 int iPhase; /* 0: const w/o IN, 1: const, 2: no IN, 2: IN */

2796 WhereLoop *pNew;

2797 int rc = SQLITE_OK;

2798

2799 assert( (mExtra & mUnusable)==0 );

2800 pWInfo = pBuilder->pWInfo;

2801 pParse = pWInfo->pParse;

2802 db = pParse->db;

2803 pWC = pBuilder->pWC;

2804 pNew = pBuilder->pNew;

2805 pSrc = &pWInfo->pTabList->a[pNew->iTab];

2806 pTab = pSrc->pTab;

2807 assert( IsVirtual(pTab) );

2808 pIdxInfo = allocateIndexInfo(pParse, pWC, mUnusable, pSrc,pBuilder->pOrderBy);

2809 if( pIdxInfo==0 ) return SQLITE_NOMEM;

2810 pNew->prereq = 0;

2811 pNew->rSetup = 0;

2812 pNew->wsFlags = WHERE_VIRTUALTABLE;

2813 pNew->nLTerm = 0;

2814 pNew->u.vtab.needFree = 0;

2815 pUsage = pIdxInfo->aConstraintUsage;

2816 nConstraint = pIdxInfo->nConstraint;

2817 if( whereLoopResize(db, pNew, nConstraint) ){

2818 sqlite3DbFree(db, pIdxInfo);

2819 return SQLITE_NOMEM;

2820 }

2821

2822 for(iPhase=0; iPhase<=3; iPhase++){

2823 if( !seenIn && (iPhase&1)!=0 ){

2824 iPhase++;

2825 if( iPhase>3 ) break;

2826 }

2827 if( !seenVar && iPhase>1 ) break;

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

2829 for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){

2830 j = pIdxCons->iTermOffset;

2831 pTerm = &pWC->a[j];

2832 switch( iPhase ){

2833 case 0: /* Constants without IN operator */

2834 pIdxCons->usable = 0;

2835 if( (pTerm->eOperator & WO_IN)!=0 ){

2836 seenIn = 1;

2837 }

2838 if( (pTerm->prereqRight & ~mExtra)!=0 ){

2839 seenVar = 1;

2840 }else if( (pTerm->eOperator & WO_IN)==0 ){

2841 pIdxCons->usable = 1;

2842 }

2843 break;

2844 case 1: /* Constants with IN operators */

2845 assert( seenIn );

2846 pIdxCons->usable = (pTerm->prereqRight & ~mExtra)==0;

2847 break;

2848 case 2: /* Variables without IN */

2849 assert( seenVar );

2850 pIdxCons->usable = (pTerm->eOperator & WO_IN)==0;

2851 break;

2852 default: /* Variables with IN */

2853 assert( seenVar && seenIn );

2854 pIdxCons->usable = 1;

2855 break;

2856 }

2857 }

2858 memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);

2859 if( pIdxInfo->needToFreeIdxStr ) sqlite3_free(pIdxInfo->idxStr);

2860 pIdxInfo->idxStr = 0;

2861 pIdxInfo->idxNum = 0;

2862 pIdxInfo->needToFreeIdxStr = 0;

2863 pIdxInfo->orderByConsumed = 0;

2864 pIdxInfo->estimatedCost = SQLITE_BIG_DBL / (double)2;

2865 pIdxInfo->estimatedRows = 25;

2866 pIdxInfo->idxFlags = 0;

2867 pIdxInfo->colUsed = (sqlite3_int64)pSrc->colUsed;

2868 rc = vtabBestIndex(pParse, pTab, pIdxInfo);

2869 if( rc ) goto whereLoopAddVtab_exit;

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

2871 pNew->prereq = mExtra;

2872 mxTerm = -1;

2873 assert( pNew->nLSlot>=nConstraint );

2874 for(i=0; i<nConstraint; i++) pNew->aLTerm[i] = 0;

2875 pNew->u.vtab.omitMask = 0;

2876 for(i=0; i<nConstraint; i++, pIdxCons++){

2877 if( (iTerm = pUsage[i].argvIndex - 1)>=0 ){

2878 j = pIdxCons->iTermOffset;

2879 if( iTerm>=nConstraint

2880 \|\| j<0

2881 \|\| j>=pWC->nTerm

2882 \|\| pNew->aLTerm[iTerm]!=0

2883 ){

2884 rc = SQLITE_ERROR;

2885 sqlite3ErrorMsg(pParse, "%s.xBestIndex() malfunction", pTab->zName);

2886 goto whereLoopAddVtab_exit;

2887 }

2888 testcase( iTerm==nConstraint-1 );

2889 testcase( j==0 );

2890 testcase( j==pWC->nTerm-1 );

2891 pTerm = &pWC->a[j];

2892 pNew->prereq \|= pTerm->prereqRight;

2893 assert( iTerm<pNew->nLSlot );

2894 pNew->aLTerm[iTerm] = pTerm;

2895 if( iTerm>mxTerm ) mxTerm = iTerm;

2896 testcase( iTerm==15 );

2897 testcase( iTerm==16 );

2898 if( iTerm<16 && pUsage[i].omit ) pNew->u.vtab.omitMask \|= 1<<iTerm;

2899 if( (pTerm->eOperator & WO_IN)!=0 ){

2900 if( pUsage[i].omit==0 ){

2901 /* Do not attempt to use an IN constraint if the virtual table

2902 ** says that the equivalent EQ constraint cannot be safely omitted.

2903 ** If we do attempt to use such a constraint, some rows might be

2904 ** repeated in the output. */

2905 break;

2906 }

2907 /* A virtual table that is constrained by an IN clause may not

2908 ** consume the ORDER BY clause because (1) the order of IN terms

2909 ** is not necessarily related to the order of output terms and

2910 ** (2) Multiple outputs from a single IN value will not merge

2911 ** together. */

2912 pIdxInfo->orderByConsumed = 0;

2913 pIdxInfo->idxFlags &= ~SQLITE_INDEX_SCAN_UNIQUE;

2914 }

2915 }

2916 }

2917 if( i>=nConstraint ){

2918 pNew->nLTerm = mxTerm+1;

2919 assert( pNew->nLTerm<=pNew->nLSlot );

2920 pNew->u.vtab.idxNum = pIdxInfo->idxNum;

2921 pNew->u.vtab.needFree = pIdxInfo->needToFreeIdxStr;

2922 pIdxInfo->needToFreeIdxStr = 0;

2923 pNew->u.vtab.idxStr = pIdxInfo->idxStr;

2924 pNew->u.vtab.isOrdered = (i8)(pIdxInfo->orderByConsumed ?

2925 pIdxInfo->nOrderBy : 0);

2926 pNew->rSetup = 0;

2927 pNew->rRun = sqlite3LogEstFromDouble(pIdxInfo->estimatedCost);

2928 pNew->nOut = sqlite3LogEst(pIdxInfo->estimatedRows);

2929

2930 /* Set the WHERE_ONEROW flag if the xBestIndex() method indicated

2931 ** that the scan will visit at most one row. Clear it otherwise. */

2932 if( pIdxInfo->idxFlags & SQLITE_INDEX_SCAN_UNIQUE ){

2933 pNew->wsFlags \|= WHERE_ONEROW;

2934 }else{

2935 pNew->wsFlags &= ~WHERE_ONEROW;

2936 }

2937 whereLoopInsert(pBuilder, pNew);

2938 if( pNew->u.vtab.needFree ){

2939 sqlite3_free(pNew->u.vtab.idxStr);

2940 pNew->u.vtab.needFree = 0;

2941 }

2942 }

2943 }

2944

2945 whereLoopAddVtab_exit:

2946 if( pIdxInfo->needToFreeIdxStr ) sqlite3_free(pIdxInfo->idxStr);

2947 sqlite3DbFree(db, pIdxInfo);

2948 return rc;

2949 }

2950 #endif /* SQLITE_OMIT_VIRTUALTABLE */

2951

2952 /*

2953 ** Add WhereLoop entries to handle OR terms. This works for either

2954 ** btrees or virtual tables.

2955 */

2956 static int whereLoopAddOr(

2957 WhereLoopBuilder *pBuilder,

2958 Bitmask mExtra,

2959 Bitmask mUnusable

2960 ){

2961 WhereInfo *pWInfo = pBuilder->pWInfo;

2962 WhereClause *pWC;

2963 WhereLoop *pNew;

2964 WhereTerm pTerm, pWCEnd;

2965 int rc = SQLITE_OK;

2966 int iCur;

2967 WhereClause tempWC;

2968 WhereLoopBuilder sSubBuild;

2969 WhereOrSet sSum, sCur;

2970 struct SrcList_item *pItem;

2971

2972 pWC = pBuilder->pWC;

2973 pWCEnd = pWC->a + pWC->nTerm;

2974 pNew = pBuilder->pNew;

2975 memset(&sSum, 0, sizeof(sSum));

2976 pItem = pWInfo->pTabList->a + pNew->iTab;

2977 iCur = pItem->iCursor;

2978

2979 for(pTerm=pWC->a; pTerm<pWCEnd && rc==SQLITE_OK; pTerm++){

2980 if( (pTerm->eOperator & WO_OR)!=0

2981 && (pTerm->u.pOrInfo->indexable & pNew->maskSelf)!=0

2982 ){

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

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

2985 WhereTerm *pOrTerm;

2986 int once = 1;

2987 int i, j;

2988

2989 sSubBuild = *pBuilder;

2990 sSubBuild.pOrderBy = 0;

2991 sSubBuild.pOrSet = &sCur;

2992

2993 WHERETRACE(0x200, ("Begin processing OR-clause %p\n", pTerm));

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

2995 if( (pOrTerm->eOperator & WO_AND)!=0 ){

2996 sSubBuild.pWC = &pOrTerm->u.pAndInfo->wc;

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

2998 tempWC.pWInfo = pWC->pWInfo;

2999 tempWC.pOuter = pWC;

3000 tempWC.op = TK_AND;

3001 tempWC.nTerm = 1;

3002 tempWC.a = pOrTerm;

3003 sSubBuild.pWC = &tempWC;

3004 }else{

3005 continue;

3006 }

3007 sCur.n = 0;

3008 #ifdef WHERETRACE_ENABLED

3009 WHERETRACE(0x200, ("OR-term %d of %p has %d subterms:\n",

3010 (int)(pOrTerm-pOrWC->a), pTerm, sSubBuild.pWC->nTerm));

3011 if( sqlite3WhereTrace & 0x400 ){

3012 for(i=0; i<sSubBuild.pWC->nTerm; i++){

3013 whereTermPrint(&sSubBuild.pWC->a[i], i);

3014 }

3015 }

3016 #endif

3017 #ifndef SQLITE_OMIT_VIRTUALTABLE

3018 if( IsVirtual(pItem->pTab) ){

3019 rc = whereLoopAddVirtual(&sSubBuild, mExtra, mUnusable);

3020 }else

3021 #endif

3022 {

3023 rc = whereLoopAddBtree(&sSubBuild, mExtra);

3024 }

3025 if( rc==SQLITE_OK ){

3026 rc = whereLoopAddOr(&sSubBuild, mExtra, mUnusable);

3027 }

3028 assert( rc==SQLITE_OK \|\| sCur.n==0 );

3029 if( sCur.n==0 ){

3030 sSum.n = 0;

3031 break;

3032 }else if( once ){

3033 whereOrMove(&sSum, &sCur);

3034 once = 0;

3035 }else{

3036 WhereOrSet sPrev;

3037 whereOrMove(&sPrev, &sSum);

3038 sSum.n = 0;

3039 for(i=0; i<sPrev.n; i++){

3040 for(j=0; j<sCur.n; j++){

3041 whereOrInsert(&sSum, sPrev.a[i].prereq \| sCur.a[j].prereq,

3042 sqlite3LogEstAdd(sPrev.a[i].rRun, sCur.a[j].rRun),

3043 sqlite3LogEstAdd(sPrev.a[i].nOut, sCur.a[j].nOut));

3044 }

3045 }

3046 }

3047 }

3048 pNew->nLTerm = 1;

3049 pNew->aLTerm[0] = pTerm;

3050 pNew->wsFlags = WHERE_MULTI_OR;

3051 pNew->rSetup = 0;

3052 pNew->iSortIdx = 0;

3053 memset(&pNew->u, 0, sizeof(pNew->u));

3054 for(i=0; rc==SQLITE_OK && i<sSum.n; i++){

3055 /* TUNING: Currently sSum.a[i].rRun is set to the sum of the costs

3056 ** of all sub-scans required by the OR-scan. However, due to rounding

3057 ** errors, it may be that the cost of the OR-scan is equal to its

3058 ** most expensive sub-scan. Add the smallest possible penalty

3059 ** (equivalent to multiplying the cost by 1.07) to ensure that

3060 ** this does not happen. Otherwise, for WHERE clauses such as the

3061 ** following where there is an index on "y":

3062 **

3063 ** WHERE likelihood(x=?, 0.99) OR y=?

3064 **

3065 ** the planner may elect to "OR" together a full-table scan and an

3066 ** index lookup. And other similarly odd results. */

3067 pNew->rRun = sSum.a[i].rRun + 1;

3068 pNew->nOut = sSum.a[i].nOut;

3069 pNew->prereq = sSum.a[i].prereq;

3070 rc = whereLoopInsert(pBuilder, pNew);

3071 }

3072 WHERETRACE(0x200, ("End processing OR-clause %p\n", pTerm));

3073 }

3074 }

3075 return rc;

3076 }

3077

3078 /*

3079 ** Add all WhereLoop objects for all tables

3080 */

3081 static int whereLoopAddAll(WhereLoopBuilder *pBuilder){

3082 WhereInfo *pWInfo = pBuilder->pWInfo;

3083 Bitmask mExtra = 0;

3084 Bitmask mPrior = 0;

3085 int iTab;

3086 SrcList *pTabList = pWInfo->pTabList;

3087 struct SrcList_item *pItem;

3088 struct SrcList_item *pEnd = &pTabList->a[pWInfo->nLevel];

3089 sqlite3 *db = pWInfo->pParse->db;

3090 int rc = SQLITE_OK;

3091 WhereLoop *pNew;

3092 u8 priorJointype = 0;

3093

3094 /* Loop over the tables in the join, from left to right */

3095 pNew = pBuilder->pNew;

3096 whereLoopInit(pNew);

3097 for(iTab=0, pItem=pTabList->a; pItem<pEnd; iTab++, pItem++){

3098 Bitmask mUnusable = 0;

3099 pNew->iTab = iTab;

3100 pNew->maskSelf = sqlite3WhereGetMask(&pWInfo->sMaskSet, pItem->iCursor);

3101 if( ((pItem->fg.jointype\|priorJointype) & (JT_LEFT\|JT_CROSS))!=0 ){

3102 /* This condition is true when pItem is the FROM clause term on the

3103 ** right-hand-side of a LEFT or CROSS JOIN. */

3104 mExtra = mPrior;

3105 }

3106 priorJointype = pItem->fg.jointype;

3107 if( IsVirtual(pItem->pTab) ){

3108 struct SrcList_item *p;

3109 for(p=&pItem[1]; p<pEnd; p++){

3110 if( mUnusable \|\| (p->fg.jointype & (JT_LEFT\|JT_CROSS)) ){

3111 mUnusable \|= sqlite3WhereGetMask(&pWInfo->sMaskSet, p->iCursor);

3112 }

3113 }

3114 rc = whereLoopAddVirtual(pBuilder, mExtra, mUnusable);

3115 }else{

3116 rc = whereLoopAddBtree(pBuilder, mExtra);

3117 }

3118 if( rc==SQLITE_OK ){

3119 rc = whereLoopAddOr(pBuilder, mExtra, mUnusable);

3120 }

3121 mPrior \|= pNew->maskSelf;

3122 if( rc \|\| db->mallocFailed ) break;

3123 }

3124

3125 whereLoopClear(db, pNew);

3126 return rc;

3127 }

3128

3129 /*

3130 ** Examine a WherePath (with the addition of the extra WhereLoop of the 5th

3131 ** parameters) to see if it outputs rows in the requested ORDER BY

3132 ** (or GROUP BY) without requiring a separate sort operation. Return N:

3133 **

3134 ** N>0: N terms of the ORDER BY clause are satisfied

3135 ** N==0: No terms of the ORDER BY clause are satisfied

3136 ** N<0: Unknown yet how many terms of ORDER BY might be satisfied.

3137 **

3138 ** Note that processing for WHERE_GROUPBY and WHERE_DISTINCTBY is not as

3139 ** strict. With GROUP BY and DISTINCT the only requirement is that

3140 ** equivalent rows appear immediately adjacent to one another. GROUP BY

3141 ** and DISTINCT do not require rows to appear in any particular order as long

3142 ** as equivalent rows are grouped together. Thus for GROUP BY and DISTINCT

3143 ** the pOrderBy terms can be matched in any order. With ORDER BY, the

3144 ** pOrderBy terms must be matched in strict left-to-right order.

3145 */

3146 static i8 wherePathSatisfiesOrderBy(

3147 WhereInfo pWInfo, / The WHERE clause */

3148 ExprList pOrderBy, / ORDER BY or GROUP BY or DISTINCT clause to check */

3149 WherePath pPath, / The WherePath to check */

3150 u16 wctrlFlags, /* Might contain WHERE_GROUPBY or WHERE_DISTINCTBY */

3151 u16 nLoop, /* Number of entries in pPath->aLoop[] */

3152 WhereLoop pLast, / Add this WhereLoop to the end of pPath->aLoop[] */

3153 Bitmask pRevMask / OUT: Mask of WhereLoops to run in reverse order */

3154 ){

3155 u8 revSet; /* True if rev is known */

3156 u8 rev; /* Composite sort order */

3157 u8 revIdx; /* Index sort order */

3158 u8 isOrderDistinct; /* All prior WhereLoops are order-distinct */

3159 u8 distinctColumns; /* True if the loop has UNIQUE NOT NULL columns */

3160 u8 isMatch; /* iColumn matches a term of the ORDER BY clause */

3161 u16 nKeyCol; /* Number of key columns in pIndex */

3162 u16 nColumn; /* Total number of ordered columns in the index */

3163 u16 nOrderBy; /* Number terms in the ORDER BY clause */

3164 int iLoop; /* Index of WhereLoop in pPath being processed */

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

3166 int iCur; /* Cursor number for current WhereLoop */

3167 int iColumn; /* A column number within table iCur */

3168 WhereLoop pLoop = 0; / Current WhereLoop being processed. */

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

3170 Expr pOBExpr; / An expression from the ORDER BY clause */

3171 CollSeq pColl; / COLLATE function from an ORDER BY clause term */

3172 Index pIndex; / The index associated with pLoop */

3173 sqlite3 db = pWInfo->pParse->db; / Database connection */

3174 Bitmask obSat = 0; /* Mask of ORDER BY terms satisfied so far */

3175 Bitmask obDone; /* Mask of all ORDER BY terms */

3176 Bitmask orderDistinctMask; /* Mask of all well-ordered loops */

3177 Bitmask ready; /* Mask of inner loops */

3178

3179 /*

3180 ** We say the WhereLoop is "one-row" if it generates no more than one

3181 ** row of output. A WhereLoop is one-row if all of the following are true:

3182 ** (a) All index columns match with WHERE_COLUMN_EQ.

3183 ** (b) The index is unique

3184 ** Any WhereLoop with an WHERE_COLUMN_EQ constraint on the rowid is one-row.

3185 ** Every one-row WhereLoop will have the WHERE_ONEROW bit set in wsFlags.

3186 **

3187 ** We say the WhereLoop is "order-distinct" if the set of columns from

3188 ** that WhereLoop that are in the ORDER BY clause are different for every

3189 ** row of the WhereLoop. Every one-row WhereLoop is automatically

3190 ** order-distinct. A WhereLoop that has no columns in the ORDER BY clause

3191 ** is not order-distinct. To be order-distinct is not quite the same as being

3192 ** UNIQUE since a UNIQUE column or index can have multiple rows that

3193 ** are NULL and NULL values are equivalent for the purpose of order-distinct.

3194 ** To be order-distinct, the columns must be UNIQUE and NOT NULL.

3195 **

3196 ** The rowid for a table is always UNIQUE and NOT NULL so whenever the

3197 ** rowid appears in the ORDER BY clause, the corresponding WhereLoop is

3198 ** automatically order-distinct.

3199 */

3200

3201 assert( pOrderBy!=0 );

3202 if( nLoop && OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return 0;

3203

3204 nOrderBy = pOrderBy->nExpr;

3205 testcase( nOrderBy==BMS-1 );

3206 if( nOrderBy>BMS-1 ) return 0; /* Cannot optimize overly large ORDER BYs */

3207 isOrderDistinct = 1;

3208 obDone = MASKBIT(nOrderBy)-1;

3209 orderDistinctMask = 0;

3210 ready = 0;

3211 for(iLoop=0; isOrderDistinct && obSat<obDone && iLoop<=nLoop; iLoop++){

3212 if( iLoop>0 ) ready \|= pLoop->maskSelf;

3213 pLoop = iLoop<nLoop ? pPath->aLoop[iLoop] : pLast;

3214 if( pLoop->wsFlags & WHERE_VIRTUALTABLE ){

3215 if( pLoop->u.vtab.isOrdered ) obSat = obDone;

3216 break;

3217 }

3218 iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor;

3219

3220 /* Mark off any ORDER BY term X that is a column in the table of

3221 ** the current loop for which there is term in the WHERE

3222 ** clause of the form X IS NULL or X=? that reference only outer

3223 ** loops.

3224 */

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

3226 if( MASKBIT(i) & obSat ) continue;

3227 pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);

3228 if( pOBExpr->op!=TK_COLUMN ) continue;

3229 if( pOBExpr->iTable!=iCur ) continue;

3230 pTerm = sqlite3WhereFindTerm(&pWInfo->sWC, iCur, pOBExpr->iColumn,

3231 ~ready, WO_EQ\|WO_ISNULL\|WO_IS, 0);

3232 if( pTerm==0 ) continue;

3233 if( (pTerm->eOperator&(WO_EQ\|WO_IS))!=0 && pOBExpr->iColumn>=0 ){

3234 const char z1, z2;

3235 pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr);

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

3237 z1 = pColl->zName;

3238 pColl = sqlite3ExprCollSeq(pWInfo->pParse, pTerm->pExpr);

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

3240 z2 = pColl->zName;

3241 if( sqlite3StrICmp(z1, z2)!=0 ) continue;

3242 testcase( pTerm->pExpr->op==TK_IS );

3243 }

3244 obSat \|= MASKBIT(i);

3245 }

3246

3247 if( (pLoop->wsFlags & WHERE_ONEROW)==0 ){

3248 if( pLoop->wsFlags & WHERE_IPK ){

3249 pIndex = 0;

3250 nKeyCol = 0;

3251 nColumn = 1;

3252 }else if( (pIndex = pLoop->u.btree.pIndex)==0 \|\| pIndex->bUnordered ){

3253 return 0;

3254 }else{

3255 nKeyCol = pIndex->nKeyCol;

3256 nColumn = pIndex->nColumn;

3257 assert( nColumn==nKeyCol+1 \|\| !HasRowid(pIndex->pTable) );

3258 assert( pIndex->aiColumn[nColumn-1]==XN_ROWID

3259 \|\| !HasRowid(pIndex->pTable));

3260 isOrderDistinct = IsUniqueIndex(pIndex);

3261 }

3262

3263 /* Loop through all columns of the index and deal with the ones

3264 ** that are not constrained by == or IN.

3265 */

3266 rev = revSet = 0;

3267 distinctColumns = 0;

3268 for(j=0; j<nColumn; j++){

3269 u8 bOnce; /* True to run the ORDER BY search loop */

3270

3271 /* Skip over == and IS NULL terms */

3272 if( j<pLoop->u.btree.nEq

3273 && pLoop->nSkip==0

3274 && ((i = pLoop->aLTerm[j]->eOperator) & (WO_EQ\|WO_ISNULL\|WO_IS))!=0

3275 ){

3276 if( i & WO_ISNULL ){

3277 testcase( isOrderDistinct );

3278 isOrderDistinct = 0;

3279 }

3280 continue;

3281 }

3282

3283 /* Get the column number in the table (iColumn) and sort order

3284 ** (revIdx) for the j-th column of the index.

3285 */

3286 if( pIndex ){

3287 iColumn = pIndex->aiColumn[j];

3288 revIdx = pIndex->aSortOrder[j];

3289 if( iColumn==pIndex->pTable->iPKey ) iColumn = -1;

3290 }else{

3291 iColumn = XN_ROWID;

3292 revIdx = 0;

3293 }

3294

3295 /* An unconstrained column that might be NULL means that this

3296 ** WhereLoop is not well-ordered

3297 */

3298 if( isOrderDistinct

3299 && iColumn>=0

3300 && j>=pLoop->u.btree.nEq

3301 && pIndex->pTable->aCol[iColumn].notNull==0

3302 ){

3303 isOrderDistinct = 0;

3304 }

3305

3306 /* Find the ORDER BY term that corresponds to the j-th column

3307 ** of the index and mark that ORDER BY term off

3308 */

3309 bOnce = 1;

3310 isMatch = 0;

3311 for(i=0; bOnce && i<nOrderBy; i++){

3312 if( MASKBIT(i) & obSat ) continue;

3313 pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);

3314 testcase( wctrlFlags & WHERE_GROUPBY );

3315 testcase( wctrlFlags & WHERE_DISTINCTBY );

3316 if( (wctrlFlags & (WHERE_GROUPBY\|WHERE_DISTINCTBY))==0 ) bOnce = 0;

3317 if( iColumn>=(-1) ){

3318 if( pOBExpr->op!=TK_COLUMN ) continue;

3319 if( pOBExpr->iTable!=iCur ) continue;

3320 if( pOBExpr->iColumn!=iColumn ) continue;

3321 }else{

3322 if( sqlite3ExprCompare(pOBExpr,pIndex->aColExpr->a[j].pExpr,iCur) ){

3323 continue;

3324 }

3325 }

3326 if( iColumn>=0 ){

3327 pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr);

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

3329 if( sqlite3StrICmp(pColl->zName, pIndex->azColl[j])!=0 ) continue;

3330 }

3331 isMatch = 1;

3332 break;

3333 }

3334 if( isMatch && (wctrlFlags & WHERE_GROUPBY)==0 ){

3335 /* Make sure the sort order is compatible in an ORDER BY clause.

3336 ** Sort order is irrelevant for a GROUP BY clause. */

3337 if( revSet ){

3338 if( (rev ^ revIdx)!=pOrderBy->a[i].sortOrder ) isMatch = 0;

3339 }else{

3340 rev = revIdx ^ pOrderBy->a[i].sortOrder;

3341 if( rev ) *pRevMask \|= MASKBIT(iLoop);

3342 revSet = 1;

3343 }

3344 }

3345 if( isMatch ){

3346 if( iColumn<0 ){

3347 testcase( distinctColumns==0 );

3348 distinctColumns = 1;

3349 }

3350 obSat \|= MASKBIT(i);

3351 }else{

3352 /* No match found */

3353 if( j==0 \|\| j<nKeyCol ){

3354 testcase( isOrderDistinct!=0 );

3355 isOrderDistinct = 0;

3356 }

3357 break;

3358 }

3359 } /* end Loop over all index columns */

3360 if( distinctColumns ){

3361 testcase( isOrderDistinct==0 );

3362 isOrderDistinct = 1;

3363 }

3364 } /* end-if not one-row */

3365

3366 /* Mark off any other ORDER BY terms that reference pLoop */

3367 if( isOrderDistinct ){

3368 orderDistinctMask \|= pLoop->maskSelf;

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

3370 Expr *p;

3371 Bitmask mTerm;

3372 if( MASKBIT(i) & obSat ) continue;

3373 p = pOrderBy->a[i].pExpr;

3374 mTerm = sqlite3WhereExprUsage(&pWInfo->sMaskSet,p);

3375 if( mTerm==0 && !sqlite3ExprIsConstant(p) ) continue;

3376 if( (mTerm&~orderDistinctMask)==0 ){

3377 obSat \|= MASKBIT(i);

3378 }

3379 }

3380 }

3381 } /* End the loop over all WhereLoops from outer-most down to inner-most */

3382 if( obSat==obDone ) return (i8)nOrderBy;

3383 if( !isOrderDistinct ){

3384 for(i=nOrderBy-1; i>0; i--){

3385 Bitmask m = MASKBIT(i) - 1;

3386 if( (obSat&m)==m ) return i;

3387 }

3388 return 0;

3389 }

3390 return -1;

3391 }

3392

3393

3394 /*

3395 ** If the WHERE_GROUPBY flag is set in the mask passed to sqlite3WhereBegin(),

3396 ** the planner assumes that the specified pOrderBy list is actually a GROUP

3397 ** BY clause - and so any order that groups rows as required satisfies the

3398 ** request.

3399 **

3400 ** Normally, in this case it is not possible for the caller to determine

3401 ** whether or not the rows are really being delivered in sorted order, or

3402 ** just in some other order that provides the required grouping. However,

3403 ** if the WHERE_SORTBYGROUP flag is also passed to sqlite3WhereBegin(), then

3404 ** this function may be called on the returned WhereInfo object. It returns

3405 ** true if the rows really will be sorted in the specified order, or false

3406 ** otherwise.

3407 **

3408 ** For example, assuming:

3409 **

3410 ** CREATE INDEX i1 ON t1(x, Y);

3411 **

3412 ** then

3413 **

3414 ** SELECT * FROM t1 GROUP BY x,y ORDER BY x,y; -- IsSorted()==1

3415 ** SELECT * FROM t1 GROUP BY y,x ORDER BY y,x; -- IsSorted()==0

3416 */

3417 int sqlite3WhereIsSorted(WhereInfo *pWInfo){

3418 assert( pWInfo->wctrlFlags & WHERE_GROUPBY );

3419 assert( pWInfo->wctrlFlags & WHERE_SORTBYGROUP );

3420 return pWInfo->sorted;

3421 }

3422

3423 #ifdef WHERETRACE_ENABLED

3424 /* For debugging use only: */

3425 static const char wherePathName(WherePath pPath, int nLoop, WhereLoop *pLast){

3426 static char zName[65];

3427 int i;

3428 for(i=0; i<nLoop; i++){ zName[i] = pPath->aLoop[i]->cId; }

3429 if( pLast ) zName[i++] = pLast->cId;

3430 zName[i] = 0;

3431 return zName;

3432 }

3433 #endif

3434

3435 /*

3436 ** Return the cost of sorting nRow rows, assuming that the keys have

3437 ** nOrderby columns and that the first nSorted columns are already in

3438 ** order.

3439 */

3440 static LogEst whereSortingCost(

3441 WhereInfo *pWInfo,

3442 LogEst nRow,

3443 int nOrderBy,

3444 int nSorted

3445 ){

3446 /* TUNING: Estimated cost of a full external sort, where N is

3447 ** the number of rows to sort is:

3448 **

3449 ** cost = (3.0 * N * log(N)).

3450 **

3451 ** Or, if the order-by clause has X terms but only the last Y

3452 ** terms are out of order, then block-sorting will reduce the

3453 ** sorting cost to:

3454 **

3455 ** cost = (3.0 * N * log(N)) * (Y/X)

3456 **

3457 ** The (Y/X) term is implemented using stack variable rScale

3458 ** below. */

3459 LogEst rScale, rSortCost;

3460 assert( nOrderBy>0 && 66==sqlite3LogEst(100) );

3461 rScale = sqlite3LogEst((nOrderBy-nSorted)*100/nOrderBy) - 66;

3462 rSortCost = nRow + estLog(nRow) + rScale + 16;

3463

3464 /* TUNING: The cost of implementing DISTINCT using a B-TREE is

3465 ** similar but with a larger constant of proportionality.

3466 ** Multiply by an additional factor of 3.0. */

3467 if( pWInfo->wctrlFlags & WHERE_WANT_DISTINCT ){

3468 rSortCost += 16;

3469 }

3470

3471 return rSortCost;

3472 }

3473

3474 /*

3475 ** Given the list of WhereLoop objects at pWInfo->pLoops, this routine

3476 ** attempts to find the lowest cost path that visits each WhereLoop

3477 ** once. This path is then loaded into the pWInfo->a[].pWLoop fields.

3478 **

3479 ** Assume that the total number of output rows that will need to be sorted

3480 ** will be nRowEst (in the 10*log2 representation). Or, ignore sorting

3481 ** costs if nRowEst==0.

3482 **

3483 ** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation

3484 ** error occurs.

3485 */

3486 static int wherePathSolver(WhereInfo *pWInfo, LogEst nRowEst){

3487 int mxChoice; /* Maximum number of simultaneous paths tracked */

3488 int nLoop; /* Number of terms in the join */

3489 Parse pParse; / Parsing context */

3490 sqlite3 db; / The database connection */

3491 int iLoop; /* Loop counter over the terms of the join */

3492 int ii, jj; /* Loop counters */

3493 int mxI = 0; /* Index of next entry to replace */

3494 int nOrderBy; /* Number of ORDER BY clause terms */

3495 LogEst mxCost = 0; /* Maximum cost of a set of paths */

3496 LogEst mxUnsorted = 0; /* Maximum unsorted cost of a set of path */

3497 int nTo, nFrom; /* Number of valid entries in aTo[] and aFrom[] */

3498 WherePath aFrom; / All nFrom paths at the previous level */

3499 WherePath aTo; / The nTo best paths at the current level */

3500 WherePath pFrom; / An element of aFrom[] that we are working on */

3501 WherePath pTo; / An element of aTo[] that we are working on */

3502 WhereLoop pWLoop; / One of the WhereLoop objects */

3503 WhereLoop *pX; / Used to divy up the pSpace memory */

3504 LogEst aSortCost = 0; / Sorting and partial sorting costs */

3505 char pSpace; / Temporary memory used by this routine */

3506 int nSpace; /* Bytes of space allocated at pSpace */

3507

3508 pParse = pWInfo->pParse;

3509 db = pParse->db;

3510 nLoop = pWInfo->nLevel;

3511 /* TUNING: For simple queries, only the best path is tracked.

3512 ** For 2-way joins, the 5 best paths are followed.

3513 ** For joins of 3 or more tables, track the 10 best paths */

3514 mxChoice = (nLoop<=1) ? 1 : (nLoop==2 ? 5 : 10);

3515 assert( nLoop<=pWInfo->pTabList->nSrc );

3516 WHERETRACE(0x002, ("---- begin solver. (nRowEst=%d)\n", nRowEst));

3517

3518 /* If nRowEst is zero and there is an ORDER BY clause, ignore it. In this

3519 ** case the purpose of this call is to estimate the number of rows returned

3520 ** by the overall query. Once this estimate has been obtained, the caller

3521 ** will invoke this function a second time, passing the estimate as the

3522 ** nRowEst parameter. */

3523 if( pWInfo->pOrderBy==0 \|\| nRowEst==0 ){

3524 nOrderBy = 0;

3525 }else{

3526 nOrderBy = pWInfo->pOrderBy->nExpr;

3527 }

3528

3529 /* Allocate and initialize space for aTo, aFrom and aSortCost[] */

3530 nSpace = (sizeof(WherePath)+sizeof(WhereLoop)nLoop)mxChoice2;

3531 nSpace += sizeof(LogEst) * nOrderBy;

3532 pSpace = sqlite3DbMallocRaw(db, nSpace);

3533 if( pSpace==0 ) return SQLITE_NOMEM;

3534 aTo = (WherePath*)pSpace;

3535 aFrom = aTo+mxChoice;

3536 memset(aFrom, 0, sizeof(aFrom[0]));

3537 pX = (WhereLoop**)(aFrom+mxChoice);

3538 for(ii=mxChoice*2, pFrom=aTo; ii>0; ii--, pFrom++, pX += nLoop){

3539 pFrom->aLoop = pX;

3540 }

3541 if( nOrderBy ){

3542 /* If there is an ORDER BY clause and it is not being ignored, set up

3543 ** space for the aSortCost[] array. Each element of the aSortCost array

3544 ** is either zero - meaning it has not yet been initialized - or the

3545 ** cost of sorting nRowEst rows of data where the first X terms of

3546 ** the ORDER BY clause are already in order, where X is the array

3547 ** index. */

3548 aSortCost = (LogEst*)pX;

3549 memset(aSortCost, 0, sizeof(LogEst) * nOrderBy);

3550 }

3551 assert( aSortCost==0 \|\| &pSpace[nSpace]==(char*)&aSortCost[nOrderBy] );

3552 assert( aSortCost!=0 \|\| &pSpace[nSpace]==(char*)pX );

3553

3554 /* Seed the search with a single WherePath containing zero WhereLoops.

3555 **

3556 ** TUNING: Do not let the number of iterations go above 28. If the cost

3557 ** of computing an automatic index is not paid back within the first 28

3558 ** rows, then do not use the automatic index. */

3559 aFrom[0].nRow = MIN(pParse->nQueryLoop, 48); assert( 48==sqlite3LogEst(28) );

3560 nFrom = 1;

3561 assert( aFrom[0].isOrdered==0 );

3562 if( nOrderBy ){

3563 /* If nLoop is zero, then there are no FROM terms in the query. Since

3564 ** in this case the query may return a maximum of one row, the results

3565 ** are already in the requested order. Set isOrdered to nOrderBy to

3566 ** indicate this. Or, if nLoop is greater than zero, set isOrdered to

3567 ** -1, indicating that the result set may or may not be ordered,

3568 ** depending on the loops added to the current plan. */

3569 aFrom[0].isOrdered = nLoop>0 ? -1 : nOrderBy;

3570 }

3571

3572 /* Compute successively longer WherePaths using the previous generation

3573 ** of WherePaths as the basis for the next. Keep track of the mxChoice

3574 ** best paths at each generation */

3575 for(iLoop=0; iLoop<nLoop; iLoop++){

3576 nTo = 0;

3577 for(ii=0, pFrom=aFrom; ii<nFrom; ii++, pFrom++){

3578 for(pWLoop=pWInfo->pLoops; pWLoop; pWLoop=pWLoop->pNextLoop){

3579 LogEst nOut; /* Rows visited by (pFrom+pWLoop) */

3580 LogEst rCost; /* Cost of path (pFrom+pWLoop) */

3581 LogEst rUnsorted; /* Unsorted cost of (pFrom+pWLoop) */

3582 i8 isOrdered = pFrom->isOrdered; /* isOrdered for (pFrom+pWLoop) */

3583 Bitmask maskNew; /* Mask of src visited by (..) */

3584 Bitmask revMask = 0; /* Mask of rev-order loops for (..) */

3585

3586 if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue;

3587 if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue;

3588 /* At this point, pWLoop is a candidate to be the next loop.

3589 ** Compute its cost */

3590 rUnsorted = sqlite3LogEstAdd(pWLoop->rSetup,pWLoop->rRun + pFrom->nRow);

3591 rUnsorted = sqlite3LogEstAdd(rUnsorted, pFrom->rUnsorted);

3592 nOut = pFrom->nRow + pWLoop->nOut;

3593 maskNew = pFrom->maskLoop \| pWLoop->maskSelf;

3594 if( isOrdered<0 ){

3595 isOrdered = wherePathSatisfiesOrderBy(pWInfo,

3596 pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags,

3597 iLoop, pWLoop, &revMask);

3598 }else{

3599 revMask = pFrom->revLoop;

3600 }

3601 if( isOrdered>=0 && isOrdered<nOrderBy ){

3602 if( aSortCost[isOrdered]==0 ){

3603 aSortCost[isOrdered] = whereSortingCost(

3604 pWInfo, nRowEst, nOrderBy, isOrdered

3605 );

3606 }

3607 rCost = sqlite3LogEstAdd(rUnsorted, aSortCost[isOrdered]);

3608

3609 WHERETRACE(0x002,

3610 ("---- sort cost=%-3d (%d/%d) increases cost %3d to %-3d\n",

3611 aSortCost[isOrdered], (nOrderBy-isOrdered), nOrderBy,

3612 rUnsorted, rCost));

3613 }else{

3614 rCost = rUnsorted;

3615 }

3616

3617 /* Check to see if pWLoop should be added to the set of

3618 ** mxChoice best-so-far paths.

3619 **

3620 ** First look for an existing path among best-so-far paths

3621 ** that covers the same set of loops and has the same isOrdered

3622 ** setting as the current path candidate.

3623 **

3624 ** The term "((pTo->isOrdered^isOrdered)&0x80)==0" is equivalent

3625 ** to (pTo->isOrdered==(-1))==(isOrdered==(-1))" for the range

3626 ** of legal values for isOrdered, -1..64.

3627 */

3628 for(jj=0, pTo=aTo; jj<nTo; jj++, pTo++){

3629 if( pTo->maskLoop==maskNew

3630 && ((pTo->isOrdered^isOrdered)&0x80)==0

3631 ){

3632 testcase( jj==nTo-1 );

3633 break;

3634 }

3635 }

3636 if( jj>=nTo ){

3637 /* None of the existing best-so-far paths match the candidate. */

3638 if( nTo>=mxChoice

3639 && (rCost>mxCost \|\| (rCost==mxCost && rUnsorted>=mxUnsorted))

3640 ){

3641 /* The current candidate is no better than any of the mxChoice

3642 ** paths currently in the best-so-far buffer. So discard

3643 ** this candidate as not viable. */

3644 #ifdef WHERETRACE_ENABLED /* 0x4 */

3645 if( sqlite3WhereTrace&0x4 ){

3646 sqlite3DebugPrintf("Skip %s cost=%-3d,%3d order=%c\n",

3647 wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,

3648 isOrdered>=0 ? isOrdered+'0' : '?');

3649 }

3650 #endif

3651 continue;

3652 }

3653 /* If we reach this points it means that the new candidate path

3654 ** needs to be added to the set of best-so-far paths. */

3655 if( nTo<mxChoice ){

3656 /* Increase the size of the aTo set by one */

3657 jj = nTo++;

3658 }else{

3659 /* New path replaces the prior worst to keep count below mxChoice */

3660 jj = mxI;

3661 }

3662 pTo = &aTo[jj];

3663 #ifdef WHERETRACE_ENABLED /* 0x4 */

3664 if( sqlite3WhereTrace&0x4 ){

3665 sqlite3DebugPrintf("New %s cost=%-3d,%3d order=%c\n",

3666 wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,

3667 isOrdered>=0 ? isOrdered+'0' : '?');

3668 }

3669 #endif

3670 }else{

3671 /* Control reaches here if best-so-far path pTo=aTo[jj] covers the

3672 ** same set of loops and has the sam isOrdered setting as the

3673 ** candidate path. Check to see if the candidate should replace

3674 ** pTo or if the candidate should be skipped */

3675 if( pTo->rCost<rCost \|\| (pTo->rCost==rCost && pTo->nRow<=nOut) ){

3676 #ifdef WHERETRACE_ENABLED /* 0x4 */

3677 if( sqlite3WhereTrace&0x4 ){

3678 sqlite3DebugPrintf(

3679 "Skip %s cost=%-3d,%3d order=%c",

3680 wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,

3681 isOrdered>=0 ? isOrdered+'0' : '?');

3682 sqlite3DebugPrintf(" vs %s cost=%-3d,%d order=%c\n",

3683 wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow,

3684 pTo->isOrdered>=0 ? pTo->isOrdered+'0' : '?');

3685 }

3686 #endif

3687 /* Discard the candidate path from further consideration */

3688 testcase( pTo->rCost==rCost );

3689 continue;

3690 }

3691 testcase( pTo->rCost==rCost+1 );

3692 /* Control reaches here if the candidate path is better than the

3693 ** pTo path. Replace pTo with the candidate. */

3694 #ifdef WHERETRACE_ENABLED /* 0x4 */

3695 if( sqlite3WhereTrace&0x4 ){

3696 sqlite3DebugPrintf(

3697 "Update %s cost=%-3d,%3d order=%c",

3698 wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,

3699 isOrdered>=0 ? isOrdered+'0' : '?');

3700 sqlite3DebugPrintf(" was %s cost=%-3d,%3d order=%c\n",

3701 wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow,

3702 pTo->isOrdered>=0 ? pTo->isOrdered+'0' : '?');

3703 }

3704 #endif

3705 }

3706 /* pWLoop is a winner. Add it to the set of best so far */

3707 pTo->maskLoop = pFrom->maskLoop \| pWLoop->maskSelf;

3708 pTo->revLoop = revMask;

3709 pTo->nRow = nOut;

3710 pTo->rCost = rCost;

3711 pTo->rUnsorted = rUnsorted;

3712 pTo->isOrdered = isOrdered;

3713 memcpy(pTo->aLoop, pFrom->aLoop, sizeof(WhereLoop)iLoop);

3714 pTo->aLoop[iLoop] = pWLoop;

3715 if( nTo>=mxChoice ){

3716 mxI = 0;

3717 mxCost = aTo[0].rCost;

3718 mxUnsorted = aTo[0].nRow;

3719 for(jj=1, pTo=&aTo[1]; jj<mxChoice; jj++, pTo++){

3720 if( pTo->rCost>mxCost

3721 \|\| (pTo->rCost==mxCost && pTo->rUnsorted>mxUnsorted)

3722 ){

3723 mxCost = pTo->rCost;

3724 mxUnsorted = pTo->rUnsorted;

3725 mxI = jj;

3726 }

3727 }

3728 }

3729 }

3730 }

3731

3732 #ifdef WHERETRACE_ENABLED /* >=2 */

3733 if( sqlite3WhereTrace & 0x02 ){

3734 sqlite3DebugPrintf("---- after round %d ----\n", iLoop);

3735 for(ii=0, pTo=aTo; ii<nTo; ii++, pTo++){

3736 sqlite3DebugPrintf(" %s cost=%-3d nrow=%-3d order=%c",

3737 wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow,

3738 pTo->isOrdered>=0 ? (pTo->isOrdered+'0') : '?');

3739 if( pTo->isOrdered>0 ){

3740 sqlite3DebugPrintf(" rev=0x%llx\n", pTo->revLoop);

3741 }else{

3742 sqlite3DebugPrintf("\n");

3743 }

3744 }

3745 }

3746 #endif

3747

3748 /* Swap the roles of aFrom and aTo for the next generation */

3749 pFrom = aTo;

3750 aTo = aFrom;

3751 aFrom = pFrom;

3752 nFrom = nTo;

3753 }

3754

3755 if( nFrom==0 ){

3756 sqlite3ErrorMsg(pParse, "no query solution");

3757 sqlite3DbFree(db, pSpace);

3758 return SQLITE_ERROR;

3759 }

3760

3761 /* Find the lowest cost path. pFrom will be left pointing to that path */

3762 pFrom = aFrom;

3763 for(ii=1; ii<nFrom; ii++){

3764 if( pFrom->rCost>aFrom[ii].rCost ) pFrom = &aFrom[ii];

3765 }

3766 assert( pWInfo->nLevel==nLoop );

3767 /* Load the lowest cost path into pWInfo */

3768 for(iLoop=0; iLoop<nLoop; iLoop++){

3769 WhereLevel *pLevel = pWInfo->a + iLoop;

3770 pLevel->pWLoop = pWLoop = pFrom->aLoop[iLoop];

3771 pLevel->iFrom = pWLoop->iTab;

3772 pLevel->iTabCur = pWInfo->pTabList->a[pLevel->iFrom].iCursor;

3773 }

3774 if( (pWInfo->wctrlFlags & WHERE_WANT_DISTINCT)!=0

3775 && (pWInfo->wctrlFlags & WHERE_DISTINCTBY)==0

3776 && pWInfo->eDistinct==WHERE_DISTINCT_NOOP

3777 && nRowEst

3778 ){

3779 Bitmask notUsed;

3780 int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pResultSet, pFrom,

3781 WHERE_DISTINCTBY, nLoop-1, pFrom->aLoop[nLoop-1], &notUsed);

3782 if( rc==pWInfo->pResultSet->nExpr ){

3783 pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;

3784 }

3785 }

3786 if( pWInfo->pOrderBy ){

3787 if( pWInfo->wctrlFlags & WHERE_DISTINCTBY ){

3788 if( pFrom->isOrdered==pWInfo->pOrderBy->nExpr ){

3789 pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;

3790 }

3791 }else{

3792 pWInfo->nOBSat = pFrom->isOrdered;

3793 if( pWInfo->nOBSat<0 ) pWInfo->nOBSat = 0;

3794 pWInfo->revMask = pFrom->revLoop;

3795 }

3796 if( (pWInfo->wctrlFlags & WHERE_SORTBYGROUP)

3797 && pWInfo->nOBSat==pWInfo->pOrderBy->nExpr && nLoop>0

3798 ){

3799 Bitmask revMask = 0;

3800 int nOrder = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy,

3801 pFrom, 0, nLoop-1, pFrom->aLoop[nLoop-1], &revMask

3802 );

3803 assert( pWInfo->sorted==0 );

3804 if( nOrder==pWInfo->pOrderBy->nExpr ){

3805 pWInfo->sorted = 1;

3806 pWInfo->revMask = revMask;

3807 }

3808 }

3809 }

3810

3811

3812 pWInfo->nRowOut = pFrom->nRow;

3813

3814 /* Free temporary memory and return success */

3815 sqlite3DbFree(db, pSpace);

3816 return SQLITE_OK;

3817 }

3818

3819 /*

3820 ** Most queries use only a single table (they are not joins) and have

3821 ** simple == constraints against indexed fields. This routine attempts

3822 ** to plan those simple cases using much less ceremony than the

3823 ** general-purpose query planner, and thereby yield faster sqlite3_prepare()

3824 ** times for the common case.

3825 **

3826 ** Return non-zero on success, if this query can be handled by this

3827 ** no-frills query planner. Return zero if this query needs the

3828 ** general-purpose query planner.

3829 */

3830 static int whereShortCut(WhereLoopBuilder *pBuilder){

3831 WhereInfo *pWInfo;

3832 struct SrcList_item *pItem;

3833 WhereClause *pWC;

3834 WhereTerm *pTerm;

3835 WhereLoop *pLoop;

3836 int iCur;

3837 int j;

3838 Table *pTab;

3839 Index *pIdx;

3840

3841 pWInfo = pBuilder->pWInfo;

3842 if( pWInfo->wctrlFlags & WHERE_FORCE_TABLE ) return 0;

3843 assert( pWInfo->pTabList->nSrc>=1 );

3844 pItem = pWInfo->pTabList->a;

3845 pTab = pItem->pTab;

3846 if( IsVirtual(pTab) ) return 0;

3847 if( pItem->fg.isIndexedBy ) return 0;

3848 iCur = pItem->iCursor;

3849 pWC = &pWInfo->sWC;

3850 pLoop = pBuilder->pNew;

3851 pLoop->wsFlags = 0;

3852 pLoop->nSkip = 0;

3853 pTerm = sqlite3WhereFindTerm(pWC, iCur, -1, 0, WO_EQ\|WO_IS, 0);

3854 if( pTerm ){

3855 testcase( pTerm->eOperator & WO_IS );

3856 pLoop->wsFlags = WHERE_COLUMN_EQ\|WHERE_IPK\|WHERE_ONEROW;

3857 pLoop->aLTerm[0] = pTerm;

3858 pLoop->nLTerm = 1;

3859 pLoop->u.btree.nEq = 1;

3860 /* TUNING: Cost of a rowid lookup is 10 */

3861 pLoop->rRun = 33; /* 33==sqlite3LogEst(10) */

3862 }else{

3863 for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){

3864 int opMask;

3865 assert( pLoop->aLTermSpace==pLoop->aLTerm );

3866 if( !IsUniqueIndex(pIdx)

3867 \|\| pIdx->pPartIdxWhere!=0

3868 \|\| pIdx->nKeyCol>ArraySize(pLoop->aLTermSpace)

3869 ) continue;

3870 opMask = pIdx->uniqNotNull ? (WO_EQ\|WO_IS) : WO_EQ;

3871 for(j=0; j<pIdx->nKeyCol; j++){

3872 pTerm = sqlite3WhereFindTerm(pWC, iCur, j, 0, opMask, pIdx);

3873 if( pTerm==0 ) break;

3874 testcase( pTerm->eOperator & WO_IS );

3875 pLoop->aLTerm[j] = pTerm;

3876 }

3877 if( j!=pIdx->nKeyCol ) continue;

3878 pLoop->wsFlags = WHERE_COLUMN_EQ\|WHERE_ONEROW\|WHERE_INDEXED;

3879 if( pIdx->isCovering \|\| (pItem->colUsed & ~columnsInIndex(pIdx))==0 ){

3880 pLoop->wsFlags \|= WHERE_IDX_ONLY;

3881 }

3882 pLoop->nLTerm = j;

3883 pLoop->u.btree.nEq = j;

3884 pLoop->u.btree.pIndex = pIdx;

3885 /* TUNING: Cost of a unique index lookup is 15 */

3886 pLoop->rRun = 39; /* 39==sqlite3LogEst(15) */

3887 break;

3888 }

3889 }

3890 if( pLoop->wsFlags ){

3891 pLoop->nOut = (LogEst)1;

3892 pWInfo->a[0].pWLoop = pLoop;

3893 pLoop->maskSelf = sqlite3WhereGetMask(&pWInfo->sMaskSet, iCur);

3894 pWInfo->a[0].iTabCur = iCur;

3895 pWInfo->nRowOut = 1;

3896 if( pWInfo->pOrderBy ) pWInfo->nOBSat = pWInfo->pOrderBy->nExpr;

3897 if( pWInfo->wctrlFlags & WHERE_WANT_DISTINCT ){

3898 pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;

3899 }

3900 #ifdef SQLITE_DEBUG

3901 pLoop->cId = '0';

3902 #endif

3903 return 1;

3904 }

3905 return 0;

3906 }

3907

3908 /*

3909 ** Generate the beginning of the loop used for WHERE clause processing.

3910 ** The return value is a pointer to an opaque structure that contains

3911 ** information needed to terminate the loop. Later, the calling routine

3912 ** should invoke sqlite3WhereEnd() with the return value of this function

3913 ** in order to complete the WHERE clause processing.

3914 **

3915 ** If an error occurs, this routine returns NULL.

3916 **

3917 ** The basic idea is to do a nested loop, one loop for each table in

3918 ** the FROM clause of a select. (INSERT and UPDATE statements are the

3919 ** same as a SELECT with only a single table in the FROM clause.) For

3920 ** example, if the SQL is this:

3921 **

3922 ** SELECT * FROM t1, t2, t3 WHERE ...;

3923 **

3924 ** Then the code generated is conceptually like the following:

3925 **

3926 ** foreach row1 in t1 do \ Code generated

3927 ** foreach row2 in t2 do \|-- by sqlite3WhereBegin()

3928 ** foreach row3 in t3 do /

3929 ** ...

3930 ** end \ Code generated

3931 ** end \|-- by sqlite3WhereEnd()

3932 ** end /

3933 **

3934 ** Note that the loops might not be nested in the order in which they

3935 ** appear in the FROM clause if a different order is better able to make

3936 ** use of indices. Note also that when the IN operator appears in

3937 ** the WHERE clause, it might result in additional nested loops for

3938 ** scanning through all values on the right-hand side of the IN.

3939 **

3940 ** There are Btree cursors associated with each table. t1 uses cursor

3941 ** number pTabList->a[0].iCursor. t2 uses the cursor pTabList->a[1].iCursor.

3942 ** And so forth. This routine generates code to open those VDBE cursors

3943 ** and sqlite3WhereEnd() generates the code to close them.

3944 **

3945 ** The code that sqlite3WhereBegin() generates leaves the cursors named

3946 ** in pTabList pointing at their appropriate entries. The [...] code

3947 ** can use OP_Column and OP_Rowid opcodes on these cursors to extract

3948 ** data from the various tables of the loop.

3949 **

3950 ** If the WHERE clause is empty, the foreach loops must each scan their

3951 ** entire tables. Thus a three-way join is an O(N^3) operation. But if

3952 ** the tables have indices and there are terms in the WHERE clause that

3953 ** refer to those indices, a complete table scan can be avoided and the

3954 ** code will run much faster. Most of the work of this routine is checking

3955 ** to see if there are indices that can be used to speed up the loop.

3956 **

3957 ** Terms of the WHERE clause are also used to limit which rows actually

3958 ** make it to the "..." in the middle of the loop. After each "foreach",

3959 ** terms of the WHERE clause that use only terms in that loop and outer

3960 ** loops are evaluated and if false a jump is made around all subsequent

3961 ** inner loops (or around the "..." if the test occurs within the inner-

3962 ** most loop)

3963 **

3964 ** OUTER JOINS

3965 **

3966 ** An outer join of tables t1 and t2 is conceptally coded as follows:

3967 **

3968 ** foreach row1 in t1 do

3969 ** flag = 0

3970 ** foreach row2 in t2 do

3971 ** start:

3972 ** ...

3973 ** flag = 1

3974 ** end

3975 ** if flag==0 then

3976 ** move the row2 cursor to a null row

3977 ** goto start

3978 ** fi

3979 ** end

3980 **

3981 ** ORDER BY CLAUSE PROCESSING

3982 **

3983 ** pOrderBy is a pointer to the ORDER BY clause (or the GROUP BY clause

3984 ** if the WHERE_GROUPBY flag is set in wctrlFlags) of a SELECT statement

3985 ** if there is one. If there is no ORDER BY clause or if this routine

3986 ** is called from an UPDATE or DELETE statement, then pOrderBy is NULL.

3987 **

3988 ** The iIdxCur parameter is the cursor number of an index. If

3989 ** WHERE_ONETABLE_ONLY is set, iIdxCur is the cursor number of an index

3990 ** to use for OR clause processing. The WHERE clause should use this

3991 ** specific cursor. If WHERE_ONEPASS_DESIRED is set, then iIdxCur is

3992 ** the first cursor in an array of cursors for all indices. iIdxCur should

3993 ** be used to compute the appropriate cursor depending on which index is

3994 ** used.

3995 */

3996 WhereInfo *sqlite3WhereBegin(

3997 Parse pParse, / The parser context */

3998 SrcList pTabList, / FROM clause: A list of all tables to be scanned */

3999 Expr pWhere, / The WHERE clause */

4000 ExprList pOrderBy, / An ORDER BY (or GROUP BY) clause, or NULL */

4001 ExprList pResultSet, / Result set of the query */

4002 u16 wctrlFlags, /* One of the WHERE_* flags defined in sqliteInt.h */

4003 int iIdxCur /* If WHERE_ONETABLE_ONLY is set, index cursor number */

4004 ){

4005 int nByteWInfo; /* Num. bytes allocated for WhereInfo struct */

4006 int nTabList; /* Number of elements in pTabList */

4007 WhereInfo pWInfo; / Will become the return value of this function */

4008 Vdbe v = pParse->pVdbe; / The virtual database engine */

4009 Bitmask notReady; /* Cursors that are not yet positioned */

4010 WhereLoopBuilder sWLB; /* The WhereLoop builder */

4011 WhereMaskSet pMaskSet; / The expression mask set */

4012 WhereLevel pLevel; / A single level in pWInfo->a[] */

4013 WhereLoop pLoop; / Pointer to a single WhereLoop object */

4014 int ii; /* Loop counter */

4015 sqlite3 db; / Database connection */

4016 int rc; /* Return code */

4017 u8 bFordelete = 0;

4018

4019 assert( (wctrlFlags & WHERE_ONEPASS_MULTIROW)==0 \|\| (

4020 (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0

4021 && (wctrlFlags & WHERE_OMIT_OPEN_CLOSE)==0

4022 ));

4023

4024 /* Variable initialization */

4025 db = pParse->db;

4026 memset(&sWLB, 0, sizeof(sWLB));

4027

4028 /* An ORDER/GROUP BY clause of more than 63 terms cannot be optimized */

4029 testcase( pOrderBy && pOrderBy->nExpr==BMS-1 );

4030 if( pOrderBy && pOrderBy->nExpr>=BMS ) pOrderBy = 0;

4031 sWLB.pOrderBy = pOrderBy;

4032

4033 /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via

4034 ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */

4035 if( OptimizationDisabled(db, SQLITE_DistinctOpt) ){

4036 wctrlFlags &= ~WHERE_WANT_DISTINCT;

4037 }

4038

4039 /* The number of tables in the FROM clause is limited by the number of

4040 ** bits in a Bitmask

4041 */

4042 testcase( pTabList->nSrc==BMS );

4043 if( pTabList->nSrc>BMS ){

4044 sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS);

4045 return 0;

4046 }

4047

4048 /* This function normally generates a nested loop for all tables in

4049 ** pTabList. But if the WHERE_ONETABLE_ONLY flag is set, then we should

4050 ** only generate code for the first table in pTabList and assume that

4051 ** any cursors associated with subsequent tables are uninitialized.

4052 */

4053 nTabList = (wctrlFlags & WHERE_ONETABLE_ONLY) ? 1 : pTabList->nSrc;

4054

4055 /* Allocate and initialize the WhereInfo structure that will become the

4056 ** return value. A single allocation is used to store the WhereInfo

4057 ** struct, the contents of WhereInfo.a[], the WhereClause structure

4058 ** and the WhereMaskSet structure. Since WhereClause contains an 8-byte

4059 ** field (type Bitmask) it must be aligned on an 8-byte boundary on

4060 ** some architectures. Hence the ROUND8() below.

4061 */

4062 nByteWInfo = ROUND8(sizeof(WhereInfo)+(nTabList-1)*sizeof(WhereLevel));

4063 pWInfo = sqlite3DbMallocZero(db, nByteWInfo + sizeof(WhereLoop));

4064 if( db->mallocFailed ){

4065 sqlite3DbFree(db, pWInfo);

4066 pWInfo = 0;

4067 goto whereBeginError;

4068 }

4069 pWInfo->aiCurOnePass[0] = pWInfo->aiCurOnePass[1] = -1;

4070 pWInfo->nLevel = nTabList;

4071 pWInfo->pParse = pParse;

4072 pWInfo->pTabList = pTabList;

4073 pWInfo->pOrderBy = pOrderBy;

4074 pWInfo->pResultSet = pResultSet;

4075 pWInfo->iBreak = pWInfo->iContinue = sqlite3VdbeMakeLabel(v);

4076 pWInfo->wctrlFlags = wctrlFlags;

4077 pWInfo->savedNQueryLoop = pParse->nQueryLoop;

4078 assert( pWInfo->eOnePass==ONEPASS_OFF ); /* ONEPASS defaults to OFF */

4079 pMaskSet = &pWInfo->sMaskSet;

4080 sWLB.pWInfo = pWInfo;

4081 sWLB.pWC = &pWInfo->sWC;

4082 sWLB.pNew = (WhereLoop)(((char)pWInfo)+nByteWInfo);

4083 assert( EIGHT_BYTE_ALIGNMENT(sWLB.pNew) );

4084 whereLoopInit(sWLB.pNew);

4085 #ifdef SQLITE_DEBUG

4086 sWLB.pNew->cId = '*';

4087 #endif

4088

4089 /* Split the WHERE clause into separate subexpressions where each

4090 ** subexpression is separated by an AND operator.

4091 */

4092 initMaskSet(pMaskSet);

4093 sqlite3WhereClauseInit(&pWInfo->sWC, pWInfo);

4094 sqlite3WhereSplit(&pWInfo->sWC, pWhere, TK_AND);

4095

4096 /* Special case: a WHERE clause that is constant. Evaluate the

4097 ** expression and either jump over all of the code or fall thru.

4098 */

4099 for(ii=0; ii<sWLB.pWC->nTerm; ii++){

4100 if( nTabList==0 \|\| sqlite3ExprIsConstantNotJoin(sWLB.pWC->a[ii].pExpr) ){

4101 sqlite3ExprIfFalse(pParse, sWLB.pWC->a[ii].pExpr, pWInfo->iBreak,

4102 SQLITE_JUMPIFNULL);

4103 sWLB.pWC->a[ii].wtFlags \|= TERM_CODED;

4104 }

4105 }

4106

4107 /* Special case: No FROM clause

4108 */

4109 if( nTabList==0 ){

4110 if( pOrderBy ) pWInfo->nOBSat = pOrderBy->nExpr;

4111 if( wctrlFlags & WHERE_WANT_DISTINCT ){

4112 pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;

4113 }

4114 }

4115

4116 /* Assign a bit from the bitmask to every term in the FROM clause.

4117 **

4118 ** The N-th term of the FROM clause is assigned a bitmask of 1<<N.

4119 **

4120 ** The rule of the previous sentence ensures thta if X is the bitmask for

4121 ** a table T, then X-1 is the bitmask for all other tables to the left of T.

4122 ** Knowing the bitmask for all tables to the left of a left join is

4123 ** important. Ticket #3015.

4124 **

4125 ** Note that bitmasks are created for all pTabList->nSrc tables in

4126 ** pTabList, not just the first nTabList tables. nTabList is normally

4127 ** equal to pTabList->nSrc but might be shortened to 1 if the

4128 ** WHERE_ONETABLE_ONLY flag is set.

4129 */

4130 for(ii=0; ii<pTabList->nSrc; ii++){

4131 createMask(pMaskSet, pTabList->a[ii].iCursor);

4132 sqlite3WhereTabFuncArgs(pParse, &pTabList->a[ii], &pWInfo->sWC);

4133 }

4134 #ifdef SQLITE_DEBUG

4135 for(ii=0; ii<pTabList->nSrc; ii++){

4136 Bitmask m = sqlite3WhereGetMask(pMaskSet, pTabList->a[ii].iCursor);

4137 assert( m==MASKBIT(ii) );

4138 }

4139 #endif

4140

4141 /* Analyze all of the subexpressions. */

4142 sqlite3WhereExprAnalyze(pTabList, &pWInfo->sWC);

4143 if( db->mallocFailed ) goto whereBeginError;

4144

4145 if( wctrlFlags & WHERE_WANT_DISTINCT ){

4146 if( isDistinctRedundant(pParse, pTabList, &pWInfo->sWC, pResultSet) ){

4147 /* The DISTINCT marking is pointless. Ignore it. */

4148 pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;

4149 }else if( pOrderBy==0 ){

4150 /* Try to ORDER BY the result set to make distinct processing easier */

4151 pWInfo->wctrlFlags \|= WHERE_DISTINCTBY;

4152 pWInfo->pOrderBy = pResultSet;

4153 }

4154 }

4155

4156 /* Construct the WhereLoop objects */

4157 WHERETRACE(0xffff,("* Optimizer Start * (wctrlFlags: 0x%x)\n",

4158 wctrlFlags));

4159 #if defined(WHERETRACE_ENABLED)

4160 if( sqlite3WhereTrace & 0x100 ){ /* Display all terms of the WHERE clause */

4161 int i;

4162 for(i=0; i<sWLB.pWC->nTerm; i++){

4163 whereTermPrint(&sWLB.pWC->a[i], i);

4164 }

4165 }

4166 #endif

4167

4168 if( nTabList!=1 \|\| whereShortCut(&sWLB)==0 ){

4169 rc = whereLoopAddAll(&sWLB);

4170 if( rc ) goto whereBeginError;

4171

4172 #ifdef WHERETRACE_ENABLED

4173 if( sqlite3WhereTrace ){ /* Display all of the WhereLoop objects */

4174 WhereLoop *p;

4175 int i;

4176 static const char zLabel[] = "0123456789abcdefghijklmnopqrstuvwyxz"

4177 "ABCDEFGHIJKLMNOPQRSTUVWYXZ";

4178 for(p=pWInfo->pLoops, i=0; p; p=p->pNextLoop, i++){

4179 p->cId = zLabel[i%sizeof(zLabel)];

4180 whereLoopPrint(p, sWLB.pWC);

4181 }

4182 }

4183 #endif

4184

4185 wherePathSolver(pWInfo, 0);

4186 if( db->mallocFailed ) goto whereBeginError;

4187 if( pWInfo->pOrderBy ){

4188 wherePathSolver(pWInfo, pWInfo->nRowOut+1);

4189 if( db->mallocFailed ) goto whereBeginError;

4190 }

4191 }

4192 if( pWInfo->pOrderBy==0 && (db->flags & SQLITE_ReverseOrder)!=0 ){

4193 pWInfo->revMask = (Bitmask)(-1);

4194 }

4195 if( pParse->nErr \|\| NEVER(db->mallocFailed) ){

4196 goto whereBeginError;

4197 }

4198 #ifdef WHERETRACE_ENABLED

4199 if( sqlite3WhereTrace ){

4200 sqlite3DebugPrintf("---- Solution nRow=%d", pWInfo->nRowOut);

4201 if( pWInfo->nOBSat>0 ){

4202 sqlite3DebugPrintf(" ORDERBY=%d,0x%llx", pWInfo->nOBSat, pWInfo->revMask);

4203 }

4204 switch( pWInfo->eDistinct ){

4205 case WHERE_DISTINCT_UNIQUE: {

4206 sqlite3DebugPrintf(" DISTINCT=unique");

4207 break;

4208 }

4209 case WHERE_DISTINCT_ORDERED: {

4210 sqlite3DebugPrintf(" DISTINCT=ordered");

4211 break;

4212 }

4213 case WHERE_DISTINCT_UNORDERED: {

4214 sqlite3DebugPrintf(" DISTINCT=unordered");

4215 break;

4216 }

4217 }

4218 sqlite3DebugPrintf("\n");

4219 for(ii=0; ii<pWInfo->nLevel; ii++){

4220 whereLoopPrint(pWInfo->a[ii].pWLoop, sWLB.pWC);

4221 }

4222 }

4223 #endif

4224 /* Attempt to omit tables from the join that do not effect the result */

4225 if( pWInfo->nLevel>=2

4226 && pResultSet!=0

4227 && OptimizationEnabled(db, SQLITE_OmitNoopJoin)

4228 ){

4229 Bitmask tabUsed = sqlite3WhereExprListUsage(pMaskSet, pResultSet);

4230 if( sWLB.pOrderBy ){

4231 tabUsed \|= sqlite3WhereExprListUsage(pMaskSet, sWLB.pOrderBy);

4232 }

4233 while( pWInfo->nLevel>=2 ){

4234 WhereTerm pTerm, pEnd;

4235 pLoop = pWInfo->a[pWInfo->nLevel-1].pWLoop;

4236 if( (pWInfo->pTabList->a[pLoop->iTab].fg.jointype & JT_LEFT)==0 ) break;

4237 if( (wctrlFlags & WHERE_WANT_DISTINCT)==0

4238 && (pLoop->wsFlags & WHERE_ONEROW)==0

4239 ){

4240 break;

4241 }

4242 if( (tabUsed & pLoop->maskSelf)!=0 ) break;

4243 pEnd = sWLB.pWC->a + sWLB.pWC->nTerm;

4244 for(pTerm=sWLB.pWC->a; pTerm<pEnd; pTerm++){

4245 if( (pTerm->prereqAll & pLoop->maskSelf)!=0

4246 && !ExprHasProperty(pTerm->pExpr, EP_FromJoin)

4247 ){

4248 break;

4249 }

4250 }

4251 if( pTerm<pEnd ) break;

4252 WHERETRACE(0xffff, ("-> drop loop %c not used\n", pLoop->cId));

4253 pWInfo->nLevel--;

4254 nTabList--;

4255 }

4256 }

4257 WHERETRACE(0xffff,("* Optimizer Finished *\n"));

4258 pWInfo->pParse->nQueryLoop += pWInfo->nRowOut;

4259

4260 /* If the caller is an UPDATE or DELETE statement that is requesting

4261 ** to use a one-pass algorithm, determine if this is appropriate.

4262 ** The one-pass algorithm only works if the WHERE clause constrains

4263 ** the statement to update or delete a single row.

4264 */

4265 assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 \|\| pWInfo->nLevel==1 );

4266 if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 ){

4267 int wsFlags = pWInfo->a[0].pWLoop->wsFlags;

4268 int bOnerow = (wsFlags & WHERE_ONEROW)!=0;

4269 if( bOnerow \|\| ( (wctrlFlags & WHERE_ONEPASS_MULTIROW)

4270 && 0==(wsFlags & WHERE_VIRTUALTABLE)

4271 )){

4272 pWInfo->eOnePass = bOnerow ? ONEPASS_SINGLE : ONEPASS_MULTI;

4273 if( HasRowid(pTabList->a[0].pTab) && (wsFlags & WHERE_IDX_ONLY) ){

4274 if( wctrlFlags & WHERE_ONEPASS_MULTIROW ){

4275 bFordelete = OPFLAG_FORDELETE;

4276 }

4277 pWInfo->a[0].pWLoop->wsFlags = (wsFlags & ~WHERE_IDX_ONLY);

4278 }

4279 }

4280 }

4281

4282 /* Open all tables in the pTabList and any indices selected for

4283 ** searching those tables.

4284 */

4285 for(ii=0, pLevel=pWInfo->a; ii<nTabList; ii++, pLevel++){

4286 Table pTab; / Table to open */

4287 int iDb; /* Index of database containing table/index */

4288 struct SrcList_item *pTabItem;

4289

4290 pTabItem = &pTabList->a[pLevel->iFrom];

4291 pTab = pTabItem->pTab;

4292 iDb = sqlite3SchemaToIndex(db, pTab->pSchema);

4293 pLoop = pLevel->pWLoop;

4294 if( (pTab->tabFlags & TF_Ephemeral)!=0 \|\| pTab->pSelect ){

4295 /* Do nothing */

4296 }else

4297 #ifndef SQLITE_OMIT_VIRTUALTABLE

4298 if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)!=0 ){

4299 const char pVTab = (const char )sqlite3GetVTable(db, pTab);

4300 int iCur = pTabItem->iCursor;

4301 sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0, pVTab, P4_VTAB);

4302 }else if( IsVirtual(pTab) ){

4303 /* noop */

4304 }else

4305 #endif

4306 if( (pLoop->wsFlags & WHERE_IDX_ONLY)==0

4307 && (wctrlFlags & WHERE_OMIT_OPEN_CLOSE)==0 ){

4308 int op = OP_OpenRead;

4309 if( pWInfo->eOnePass!=ONEPASS_OFF ){

4310 op = OP_OpenWrite;

4311 pWInfo->aiCurOnePass[0] = pTabItem->iCursor;

4312 };

4313 sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, op);

4314 assert( pTabItem->iCursor==pLevel->iTabCur );

4315 testcase( pWInfo->eOnePass==ONEPASS_OFF && pTab->nCol==BMS-1 );

4316 testcase( pWInfo->eOnePass==ONEPASS_OFF && pTab->nCol==BMS );

4317 if( pWInfo->eOnePass==ONEPASS_OFF && pTab->nCol<BMS && HasRowid(pTab) ){

4318 Bitmask b = pTabItem->colUsed;

4319 int n = 0;

4320 for(; b; b=b>>1, n++){}

4321 sqlite3VdbeChangeP4(v, sqlite3VdbeCurrentAddr(v)-1,

4322 SQLITE_INT_TO_PTR(n), P4_INT32);

4323 assert( n<=pTab->nCol );

4324 }

4325 #ifdef SQLITE_ENABLE_CURSOR_HINTS

4326 if( pLoop->u.btree.pIndex!=0 ){

4327 sqlite3VdbeChangeP5(v, OPFLAG_SEEKEQ\|bFordelete);

4328 }else

4329 #endif

4330 {

4331 sqlite3VdbeChangeP5(v, bFordelete);

4332 }

4333 #ifdef SQLITE_ENABLE_COLUMN_USED_MASK

4334 sqlite3VdbeAddOp4Dup8(v, OP_ColumnsUsed, pTabItem->iCursor, 0, 0,

4335 (const u8*)&pTabItem->colUsed, P4_INT64);

4336 #endif

4337 }else{

4338 sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);

4339 }

4340 if( pLoop->wsFlags & WHERE_INDEXED ){

4341 Index *pIx = pLoop->u.btree.pIndex;

4342 int iIndexCur;

4343 int op = OP_OpenRead;

4344 /* iIdxCur is always set if to a positive value if ONEPASS is possible */

4345 assert( iIdxCur!=0 \|\| (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 );

4346 if( !HasRowid(pTab) && IsPrimaryKeyIndex(pIx)

4347 && (wctrlFlags & WHERE_ONETABLE_ONLY)!=0

4348 ){

4349 /* This is one term of an OR-optimization using the PRIMARY KEY of a

4350 ** WITHOUT ROWID table. No need for a separate index */

4351 iIndexCur = pLevel->iTabCur;

4352 op = 0;

4353 }else if( pWInfo->eOnePass!=ONEPASS_OFF ){

4354 Index *pJ = pTabItem->pTab->pIndex;

4355 iIndexCur = iIdxCur;

4356 assert( wctrlFlags & WHERE_ONEPASS_DESIRED );

4357 while( ALWAYS(pJ) && pJ!=pIx ){

4358 iIndexCur++;

4359 pJ = pJ->pNext;

4360 }

4361 op = OP_OpenWrite;

4362 pWInfo->aiCurOnePass[1] = iIndexCur;

4363 }else if( iIdxCur && (wctrlFlags & WHERE_ONETABLE_ONLY)!=0 ){

4364 iIndexCur = iIdxCur;

4365 if( wctrlFlags & WHERE_REOPEN_IDX ) op = OP_ReopenIdx;

4366 }else{

4367 iIndexCur = pParse->nTab++;

4368 }

4369 pLevel->iIdxCur = iIndexCur;

4370 assert( pIx->pSchema==pTab->pSchema );

4371 assert( iIndexCur>=0 );

4372 if( op ){

4373 sqlite3VdbeAddOp3(v, op, iIndexCur, pIx->tnum, iDb);

4374 sqlite3VdbeSetP4KeyInfo(pParse, pIx);

4375 if( (pLoop->wsFlags & WHERE_CONSTRAINT)!=0

4376 && (pLoop->wsFlags & (WHERE_COLUMN_RANGE\|WHERE_SKIPSCAN))==0

4377 && (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)==0

4378 ){

4379 sqlite3VdbeChangeP5(v, OPFLAG_SEEKEQ); /* Hint to COMDB2 */

4380 }

4381 VdbeComment((v, "%s", pIx->zName));

4382 #ifdef SQLITE_ENABLE_COLUMN_USED_MASK

4383 {

4384 u64 colUsed = 0;

4385 int ii, jj;

4386 for(ii=0; ii<pIx->nColumn; ii++){

4387 jj = pIx->aiColumn[ii];

4388 if( jj<0 ) continue;

4389 if( jj>63 ) jj = 63;

4390 if( (pTabItem->colUsed & MASKBIT(jj))==0 ) continue;

4391 colUsed \|= ((u64)1)<<(ii<63 ? ii : 63);

4392 }

4393 sqlite3VdbeAddOp4Dup8(v, OP_ColumnsUsed, iIndexCur, 0, 0,

4394 (u8*)&colUsed, P4_INT64);

4395 }

4396 #endif /* SQLITE_ENABLE_COLUMN_USED_MASK */

4397 }

4398 }

4399 if( iDb>=0 ) sqlite3CodeVerifySchema(pParse, iDb);

4400 }

4401 pWInfo->iTop = sqlite3VdbeCurrentAddr(v);

4402 if( db->mallocFailed ) goto whereBeginError;

4403

4404 /* Generate the code to do the search. Each iteration of the for

4405 ** loop below generates code for a single nested loop of the VM

4406 ** program.

4407 */

4408 notReady = ~(Bitmask)0;

4409 for(ii=0; ii<nTabList; ii++){

4410 int addrExplain;

4411 int wsFlags;

4412 pLevel = &pWInfo->a[ii];

4413 wsFlags = pLevel->pWLoop->wsFlags;

4414 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX

4415 if( (pLevel->pWLoop->wsFlags & WHERE_AUTO_INDEX)!=0 ){

4416 constructAutomaticIndex(pParse, &pWInfo->sWC,

4417 &pTabList->a[pLevel->iFrom], notReady, pLevel);

4418 if( db->mallocFailed ) goto whereBeginError;

4419 }

4420 #endif

4421 addrExplain = sqlite3WhereExplainOneScan(

4422 pParse, pTabList, pLevel, ii, pLevel->iFrom, wctrlFlags

4423 );

4424 pLevel->addrBody = sqlite3VdbeCurrentAddr(v);

4425 notReady = sqlite3WhereCodeOneLoopStart(pWInfo, ii, notReady);

4426 pWInfo->iContinue = pLevel->addrCont;

4427 if( (wsFlags&WHERE_MULTI_OR)==0 && (wctrlFlags&WHERE_ONETABLE_ONLY)==0 ){

4428 sqlite3WhereAddScanStatus(v, pTabList, pLevel, addrExplain);

4429 }

4430 }

4431

4432 /* Done. */

4433 VdbeModuleComment((v, "Begin WHERE-core"));

4434 return pWInfo;

4435

4436 /* Jump here if malloc fails */

4437 whereBeginError:

4438 if( pWInfo ){

4439 pParse->nQueryLoop = pWInfo->savedNQueryLoop;

4440 whereInfoFree(db, pWInfo);

4441 }

4442 return 0;

4443 }

4444

4445 /*

4446 ** Generate the end of the WHERE loop. See comments on

4447 ** sqlite3WhereBegin() for additional information.

4448 */

4449 void sqlite3WhereEnd(WhereInfo *pWInfo){

4450 Parse *pParse = pWInfo->pParse;

4451 Vdbe *v = pParse->pVdbe;

4452 int i;

4453 WhereLevel *pLevel;

4454 WhereLoop *pLoop;

4455 SrcList *pTabList = pWInfo->pTabList;

4456 sqlite3 *db = pParse->db;

4457

4458 /* Generate loop termination code.

4459 */

4460 VdbeModuleComment((v, "End WHERE-core"));

4461 sqlite3ExprCacheClear(pParse);

4462 for(i=pWInfo->nLevel-1; i>=0; i--){

4463 int addr;

4464 pLevel = &pWInfo->a[i];

4465 pLoop = pLevel->pWLoop;

4466 sqlite3VdbeResolveLabel(v, pLevel->addrCont);

4467 if( pLevel->op!=OP_Noop ){

4468 sqlite3VdbeAddOp3(v, pLevel->op, pLevel->p1, pLevel->p2, pLevel->p3);

4469 sqlite3VdbeChangeP5(v, pLevel->p5);

4470 VdbeCoverage(v);

4471 VdbeCoverageIf(v, pLevel->op==OP_Next);

4472 VdbeCoverageIf(v, pLevel->op==OP_Prev);

4473 VdbeCoverageIf(v, pLevel->op==OP_VNext);

4474 }

4475 if( pLoop->wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){

4476 struct InLoop *pIn;

4477 int j;

4478 sqlite3VdbeResolveLabel(v, pLevel->addrNxt);

4479 for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){

4480 sqlite3VdbeJumpHere(v, pIn->addrInTop+1);

4481 sqlite3VdbeAddOp2(v, pIn->eEndLoopOp, pIn->iCur, pIn->addrInTop);

4482 VdbeCoverage(v);

4483 VdbeCoverageIf(v, pIn->eEndLoopOp==OP_PrevIfOpen);

4484 VdbeCoverageIf(v, pIn->eEndLoopOp==OP_NextIfOpen);

4485 sqlite3VdbeJumpHere(v, pIn->addrInTop-1);

4486 }

4487 }

4488 sqlite3VdbeResolveLabel(v, pLevel->addrBrk);

4489 if( pLevel->addrSkip ){

4490 sqlite3VdbeGoto(v, pLevel->addrSkip);

4491 VdbeComment((v, "next skip-scan on %s", pLoop->u.btree.pIndex->zName));

4492 sqlite3VdbeJumpHere(v, pLevel->addrSkip);

4493 sqlite3VdbeJumpHere(v, pLevel->addrSkip-2);

4494 }

4495 #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS

4496 if( pLevel->addrLikeRep ){

4497 int op;

4498 if( sqlite3VdbeGetOp(v, pLevel->addrLikeRep-1)->p1 ){

4499 op = OP_DecrJumpZero;

4500 }else{

4501 op = OP_JumpZeroIncr;

4502 }

4503 sqlite3VdbeAddOp2(v, op, pLevel->iLikeRepCntr, pLevel->addrLikeRep);

4504 VdbeCoverage(v);

4505 }

4506 #endif

4507 if( pLevel->iLeftJoin ){

4508 addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin); VdbeCoverage(v);

4509 assert( (pLoop->wsFlags & WHERE_IDX_ONLY)==0

4510 \|\| (pLoop->wsFlags & WHERE_INDEXED)!=0 );

4511 if( (pLoop->wsFlags & WHERE_IDX_ONLY)==0 ){

4512 sqlite3VdbeAddOp1(v, OP_NullRow, pTabList->a[i].iCursor);

4513 }

4514 if( pLoop->wsFlags & WHERE_INDEXED ){

4515 sqlite3VdbeAddOp1(v, OP_NullRow, pLevel->iIdxCur);

4516 }

4517 if( pLevel->op==OP_Return ){

4518 sqlite3VdbeAddOp2(v, OP_Gosub, pLevel->p1, pLevel->addrFirst);

4519 }else{

4520 sqlite3VdbeGoto(v, pLevel->addrFirst);

4521 }

4522 sqlite3VdbeJumpHere(v, addr);

4523 }

4524 VdbeModuleComment((v, "End WHERE-loop%d: %s", i,

4525 pWInfo->pTabList->a[pLevel->iFrom].pTab->zName));

4526 }

4527

4528 /* The "break" point is here, just past the end of the outer loop.

4529 ** Set it.

4530 */

4531 sqlite3VdbeResolveLabel(v, pWInfo->iBreak);

4532

4533 assert( pWInfo->nLevel<=pTabList->nSrc );

4534 for(i=0, pLevel=pWInfo->a; i<pWInfo->nLevel; i++, pLevel++){

4535 int k, last;

4536 VdbeOp *pOp;

4537 Index *pIdx = 0;

4538 struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];

4539 Table *pTab = pTabItem->pTab;

4540 assert( pTab!=0 );

4541 pLoop = pLevel->pWLoop;

4542

4543 /* For a co-routine, change all OP_Column references to the table of

4544 ** the co-routine into OP_Copy of result contained in a register.

4545 ** OP_Rowid becomes OP_Null.

4546 */

4547 if( pTabItem->fg.viaCoroutine && !db->mallocFailed ){

4548 translateColumnToCopy(v, pLevel->addrBody, pLevel->iTabCur,

4549 pTabItem->regResult, 0);

4550 continue;

4551 }

4552

4553 /* Close all of the cursors that were opened by sqlite3WhereBegin.

4554 ** Except, do not close cursors that will be reused by the OR optimization

4555 ** (WHERE_OMIT_OPEN_CLOSE). And do not close the OP_OpenWrite cursors

4556 ** created for the ONEPASS optimization.

4557 */

4558 if( (pTab->tabFlags & TF_Ephemeral)==0

4559 && pTab->pSelect==0

4560 && (pWInfo->wctrlFlags & WHERE_OMIT_OPEN_CLOSE)==0

4561 ){

4562 int ws = pLoop->wsFlags;

4563 if( pWInfo->eOnePass==ONEPASS_OFF && (ws & WHERE_IDX_ONLY)==0 ){

4564 sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor);

4565 }

4566 if( (ws & WHERE_INDEXED)!=0

4567 && (ws & (WHERE_IPK\|WHERE_AUTO_INDEX))==0

4568 && pLevel->iIdxCur!=pWInfo->aiCurOnePass[1]

4569 ){

4570 sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur);

4571 }

4572 }

4573

4574 /* If this scan uses an index, make VDBE code substitutions to read data

4575 ** from the index instead of from the table where possible. In some cases

4576 ** this optimization prevents the table from ever being read, which can

4577 ** yield a significant performance boost.

4578 **

4579 ** Calls to the code generator in between sqlite3WhereBegin and

4580 ** sqlite3WhereEnd will have created code that references the table

4581 ** directly. This loop scans all that code looking for opcodes

4582 ** that reference the table and converts them into opcodes that

4583 ** reference the index.

4584 */

4585 if( pLoop->wsFlags & (WHERE_INDEXED\|WHERE_IDX_ONLY) ){

4586 pIdx = pLoop->u.btree.pIndex;

4587 }else if( pLoop->wsFlags & WHERE_MULTI_OR ){

4588 pIdx = pLevel->u.pCovidx;

4589 }

4590 if( pIdx

4591 && (pWInfo->eOnePass==ONEPASS_OFF \|\| !HasRowid(pIdx->pTable))

4592 && !db->mallocFailed

4593 ){

4594 last = sqlite3VdbeCurrentAddr(v);

4595 k = pLevel->addrBody;

4596 pOp = sqlite3VdbeGetOp(v, k);

4597 for(; k<last; k++, pOp++){

4598 if( pOp->p1!=pLevel->iTabCur ) continue;

4599 if( pOp->opcode==OP_Column ){

4600 int x = pOp->p2;

4601 assert( pIdx->pTable==pTab );

4602 if( !HasRowid(pTab) ){

4603 Index *pPk = sqlite3PrimaryKeyIndex(pTab);

4604 x = pPk->aiColumn[x];

4605 assert( x>=0 );

4606 }

4607 x = sqlite3ColumnOfIndex(pIdx, x);

4608 if( x>=0 ){

4609 pOp->p2 = x;

4610 pOp->p1 = pLevel->iIdxCur;

4611 }

4612 assert( (pLoop->wsFlags & WHERE_IDX_ONLY)==0 \|\| x>=0 );

4613 }else if( pOp->opcode==OP_Rowid ){

4614 pOp->p1 = pLevel->iIdxCur;

4615 pOp->opcode = OP_IdxRowid;

4616 }

4617 }

4618 }

4619 }

4620

4621 /* Final cleanup

4622 */

4623 pParse->nQueryLoop = pWInfo->savedNQueryLoop;

4624 whereInfoFree(db, pWInfo);

4625 return;

4626 }

OLD	NEW

« no previous file with comments | « third_party/sqlite/sqlite-src-3100200/src/walker.c ('k') | third_party/sqlite/sqlite-src-3100200/src/whereInt.h » ('j') | no next file with comments »