4 ** The author disclaims copyright to this source code. In place of
5 ** a legal notice, here is a blessing:
7 ** May you do good and not evil.
8 ** May you find forgiveness for yourself and forgive others.
9 ** May you share freely, never taking more than you give.
11 *************************************************************************
12 ** This 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".
19 #include "sqliteInt.h"
23 ** Extra information appended to the end of sqlite3_index_info but not
24 ** visible to the xBestIndex function, at least not directly. The
25 ** sqlite3_vtab_collation() interface knows how to reach it, however.
27 ** This object is not an API and can be changed from one release to the
28 ** next. As long as allocateIndexInfo() and sqlite3_vtab_collation()
29 ** agree on the structure, all will be well.
31 typedef struct HiddenIndexInfo HiddenIndexInfo
;
32 struct HiddenIndexInfo
{
33 WhereClause
*pWC
; /* The Where clause being analyzed */
34 Parse
*pParse
; /* The parsing context */
37 /* Forward declaration of methods */
38 static int whereLoopResize(sqlite3
*, WhereLoop
*, int);
41 ** Return the estimated number of output rows from a WHERE clause
43 LogEst
sqlite3WhereOutputRowCount(WhereInfo
*pWInfo
){
44 return pWInfo
->nRowOut
;
48 ** Return one of the WHERE_DISTINCT_xxxxx values to indicate how this
49 ** WHERE clause returns outputs for DISTINCT processing.
51 int sqlite3WhereIsDistinct(WhereInfo
*pWInfo
){
52 return pWInfo
->eDistinct
;
56 ** Return the number of ORDER BY terms that are satisfied by the
57 ** WHERE clause. A return of 0 means that the output must be
58 ** completely sorted. A return equal to the number of ORDER BY
59 ** terms means that no sorting is needed at all. A return that
60 ** is positive but less than the number of ORDER BY terms means that
61 ** block sorting is required.
63 int sqlite3WhereIsOrdered(WhereInfo
*pWInfo
){
64 return pWInfo
->nOBSat
;
68 ** In the ORDER BY LIMIT optimization, if the inner-most loop is known
69 ** to emit rows in increasing order, and if the last row emitted by the
70 ** inner-most loop did not fit within the sorter, then we can skip all
71 ** subsequent rows for the current iteration of the inner loop (because they
72 ** will not fit in the sorter either) and continue with the second inner
73 ** loop - the loop immediately outside the inner-most.
75 ** When a row does not fit in the sorter (because the sorter already
76 ** holds LIMIT+OFFSET rows that are smaller), then a jump is made to the
77 ** label returned by this function.
79 ** If the ORDER BY LIMIT optimization applies, the jump destination should
80 ** be the continuation for the second-inner-most loop. If the ORDER BY
81 ** LIMIT optimization does not apply, then the jump destination should
82 ** be the continuation for the inner-most loop.
84 ** It is always safe for this routine to return the continuation of the
85 ** inner-most loop, in the sense that a correct answer will result.
86 ** Returning the continuation the second inner loop is an optimization
87 ** that might make the code run a little faster, but should not change
90 int sqlite3WhereOrderByLimitOptLabel(WhereInfo
*pWInfo
){
92 if( !pWInfo
->bOrderedInnerLoop
){
93 /* The ORDER BY LIMIT optimization does not apply. Jump to the
94 ** continuation of the inner-most loop. */
95 return pWInfo
->iContinue
;
97 pInner
= &pWInfo
->a
[pWInfo
->nLevel
-1];
98 assert( pInner
->addrNxt
!=0 );
99 return pInner
->addrNxt
;
103 ** While generating code for the min/max optimization, after handling
104 ** the aggregate-step call to min() or max(), check to see if any
105 ** additional looping is required. If the output order is such that
106 ** we are certain that the correct answer has already been found, then
107 ** code an OP_Goto to by pass subsequent processing.
109 ** Any extra OP_Goto that is coded here is an optimization. The
110 ** correct answer should be obtained regardless. This OP_Goto just
111 ** makes the answer appear faster.
113 void sqlite3WhereMinMaxOptEarlyOut(Vdbe
*v
, WhereInfo
*pWInfo
){
116 if( !pWInfo
->bOrderedInnerLoop
) return;
117 if( pWInfo
->nOBSat
==0 ) return;
118 for(i
=pWInfo
->nLevel
-1; i
>=0; i
--){
119 pInner
= &pWInfo
->a
[i
];
120 if( (pInner
->pWLoop
->wsFlags
& WHERE_COLUMN_IN
)!=0 ){
121 sqlite3VdbeGoto(v
, pInner
->addrNxt
);
125 sqlite3VdbeGoto(v
, pWInfo
->iBreak
);
129 ** Return the VDBE address or label to jump to in order to continue
130 ** immediately with the next row of a WHERE clause.
132 int sqlite3WhereContinueLabel(WhereInfo
*pWInfo
){
133 assert( pWInfo
->iContinue
!=0 );
134 return pWInfo
->iContinue
;
138 ** Return the VDBE address or label to jump to in order to break
139 ** out of a WHERE loop.
141 int sqlite3WhereBreakLabel(WhereInfo
*pWInfo
){
142 return pWInfo
->iBreak
;
146 ** Return ONEPASS_OFF (0) if an UPDATE or DELETE statement is unable to
147 ** operate directly on the rowids returned by a WHERE clause. Return
148 ** ONEPASS_SINGLE (1) if the statement can operation directly because only
149 ** a single row is to be changed. Return ONEPASS_MULTI (2) if the one-pass
150 ** optimization can be used on multiple
152 ** If the ONEPASS optimization is used (if this routine returns true)
153 ** then also write the indices of open cursors used by ONEPASS
154 ** into aiCur[0] and aiCur[1]. iaCur[0] gets the cursor of the data
155 ** table and iaCur[1] gets the cursor used by an auxiliary index.
156 ** Either value may be -1, indicating that cursor is not used.
157 ** Any cursors returned will have been opened for writing.
159 ** aiCur[0] and aiCur[1] both get -1 if the where-clause logic is
160 ** unable to use the ONEPASS optimization.
162 int sqlite3WhereOkOnePass(WhereInfo
*pWInfo
, int *aiCur
){
163 memcpy(aiCur
, pWInfo
->aiCurOnePass
, sizeof(int)*2);
164 #ifdef WHERETRACE_ENABLED
165 if( sqlite3WhereTrace
&& pWInfo
->eOnePass
!=ONEPASS_OFF
){
166 sqlite3DebugPrintf("%s cursors: %d %d\n",
167 pWInfo
->eOnePass
==ONEPASS_SINGLE
? "ONEPASS_SINGLE" : "ONEPASS_MULTI",
171 return pWInfo
->eOnePass
;
175 ** Return TRUE if the WHERE loop uses the OP_DeferredSeek opcode to move
176 ** the data cursor to the row selected by the index cursor.
178 int sqlite3WhereUsesDeferredSeek(WhereInfo
*pWInfo
){
179 return pWInfo
->bDeferredSeek
;
183 ** Move the content of pSrc into pDest
185 static void whereOrMove(WhereOrSet
*pDest
, WhereOrSet
*pSrc
){
187 memcpy(pDest
->a
, pSrc
->a
, pDest
->n
*sizeof(pDest
->a
[0]));
191 ** Try to insert a new prerequisite/cost entry into the WhereOrSet pSet.
193 ** The new entry might overwrite an existing entry, or it might be
194 ** appended, or it might be discarded. Do whatever is the right thing
195 ** so that pSet keeps the N_OR_COST best entries seen so far.
197 static int whereOrInsert(
198 WhereOrSet
*pSet
, /* The WhereOrSet to be updated */
199 Bitmask prereq
, /* Prerequisites of the new entry */
200 LogEst rRun
, /* Run-cost of the new entry */
201 LogEst nOut
/* Number of outputs for the new entry */
205 for(i
=pSet
->n
, p
=pSet
->a
; i
>0; i
--, p
++){
206 if( rRun
<=p
->rRun
&& (prereq
& p
->prereq
)==prereq
){
207 goto whereOrInsert_done
;
209 if( p
->rRun
<=rRun
&& (p
->prereq
& prereq
)==p
->prereq
){
213 if( pSet
->n
<N_OR_COST
){
214 p
= &pSet
->a
[pSet
->n
++];
218 for(i
=1; i
<pSet
->n
; i
++){
219 if( p
->rRun
>pSet
->a
[i
].rRun
) p
= pSet
->a
+ i
;
221 if( p
->rRun
<=rRun
) return 0;
226 if( p
->nOut
>nOut
) p
->nOut
= nOut
;
231 ** Return the bitmask for the given cursor number. Return 0 if
232 ** iCursor is not in the set.
234 Bitmask
sqlite3WhereGetMask(WhereMaskSet
*pMaskSet
, int iCursor
){
236 assert( pMaskSet
->n
<=(int)sizeof(Bitmask
)*8 );
237 for(i
=0; i
<pMaskSet
->n
; i
++){
238 if( pMaskSet
->ix
[i
]==iCursor
){
246 ** Create a new mask for cursor iCursor.
248 ** There is one cursor per table in the FROM clause. The number of
249 ** tables in the FROM clause is limited by a test early in the
250 ** sqlite3WhereBegin() routine. So we know that the pMaskSet->ix[]
251 ** array will never overflow.
253 static void createMask(WhereMaskSet
*pMaskSet
, int iCursor
){
254 assert( pMaskSet
->n
< ArraySize(pMaskSet
->ix
) );
255 pMaskSet
->ix
[pMaskSet
->n
++] = iCursor
;
259 ** If the right-hand branch of the expression is a TK_COLUMN, then return
260 ** a pointer to the right-hand branch. Otherwise, return NULL.
262 static Expr
*whereRightSubexprIsColumn(Expr
*p
){
263 p
= sqlite3ExprSkipCollateAndLikely(p
->pRight
);
264 if( ALWAYS(p
!=0) && p
->op
==TK_COLUMN
&& !ExprHasProperty(p
, EP_FixedCol
) ){
271 ** Advance to the next WhereTerm that matches according to the criteria
272 ** established when the pScan object was initialized by whereScanInit().
273 ** Return NULL if there are no more matching WhereTerms.
275 static WhereTerm
*whereScanNext(WhereScan
*pScan
){
276 int iCur
; /* The cursor on the LHS of the term */
277 i16 iColumn
; /* The column on the LHS of the term. -1 for IPK */
278 Expr
*pX
; /* An expression being tested */
279 WhereClause
*pWC
; /* Shorthand for pScan->pWC */
280 WhereTerm
*pTerm
; /* The term being tested */
281 int k
= pScan
->k
; /* Where to start scanning */
283 assert( pScan
->iEquiv
<=pScan
->nEquiv
);
286 iColumn
= pScan
->aiColumn
[pScan
->iEquiv
-1];
287 iCur
= pScan
->aiCur
[pScan
->iEquiv
-1];
291 for(pTerm
=pWC
->a
+k
; k
<pWC
->nTerm
; k
++, pTerm
++){
292 assert( (pTerm
->eOperator
& (WO_OR
|WO_AND
))==0 || pTerm
->leftCursor
<0 );
293 if( pTerm
->leftCursor
==iCur
294 && pTerm
->u
.x
.leftColumn
==iColumn
296 || sqlite3ExprCompareSkip(pTerm
->pExpr
->pLeft
,
297 pScan
->pIdxExpr
,iCur
)==0)
298 && (pScan
->iEquiv
<=1 || !ExprHasProperty(pTerm
->pExpr
, EP_FromJoin
))
300 if( (pTerm
->eOperator
& WO_EQUIV
)!=0
301 && pScan
->nEquiv
<ArraySize(pScan
->aiCur
)
302 && (pX
= whereRightSubexprIsColumn(pTerm
->pExpr
))!=0
305 for(j
=0; j
<pScan
->nEquiv
; j
++){
306 if( pScan
->aiCur
[j
]==pX
->iTable
307 && pScan
->aiColumn
[j
]==pX
->iColumn
){
311 if( j
==pScan
->nEquiv
){
312 pScan
->aiCur
[j
] = pX
->iTable
;
313 pScan
->aiColumn
[j
] = pX
->iColumn
;
317 if( (pTerm
->eOperator
& pScan
->opMask
)!=0 ){
318 /* Verify the affinity and collating sequence match */
319 if( pScan
->zCollName
&& (pTerm
->eOperator
& WO_ISNULL
)==0 ){
321 Parse
*pParse
= pWC
->pWInfo
->pParse
;
323 if( !sqlite3IndexAffinityOk(pX
, pScan
->idxaff
) ){
327 pColl
= sqlite3ExprCompareCollSeq(pParse
, pX
);
328 if( pColl
==0 ) pColl
= pParse
->db
->pDfltColl
;
329 if( sqlite3StrICmp(pColl
->zName
, pScan
->zCollName
) ){
333 if( (pTerm
->eOperator
& (WO_EQ
|WO_IS
))!=0
334 && (pX
= pTerm
->pExpr
->pRight
, ALWAYS(pX
!=0))
336 && pX
->iTable
==pScan
->aiCur
[0]
337 && pX
->iColumn
==pScan
->aiColumn
[0]
339 testcase( pTerm
->eOperator
& WO_IS
);
344 #ifdef WHERETRACE_ENABLED
345 if( sqlite3WhereTrace
& 0x20000 ){
347 sqlite3DebugPrintf("SCAN-TERM %p: nEquiv=%d",
348 pTerm
, pScan
->nEquiv
);
349 for(ii
=0; ii
<pScan
->nEquiv
; ii
++){
350 sqlite3DebugPrintf(" {%d:%d}",
351 pScan
->aiCur
[ii
], pScan
->aiColumn
[ii
]);
353 sqlite3DebugPrintf("\n");
363 if( pScan
->iEquiv
>=pScan
->nEquiv
) break;
364 pWC
= pScan
->pOrigWC
;
372 ** This is whereScanInit() for the case of an index on an expression.
373 ** It is factored out into a separate tail-recursion subroutine so that
374 ** the normal whereScanInit() routine, which is a high-runner, does not
375 ** need to push registers onto the stack as part of its prologue.
377 static SQLITE_NOINLINE WhereTerm
*whereScanInitIndexExpr(WhereScan
*pScan
){
378 pScan
->idxaff
= sqlite3ExprAffinity(pScan
->pIdxExpr
);
379 return whereScanNext(pScan
);
383 ** Initialize a WHERE clause scanner object. Return a pointer to the
384 ** first match. Return NULL if there are no matches.
386 ** The scanner will be searching the WHERE clause pWC. It will look
387 ** for terms of the form "X <op> <expr>" where X is column iColumn of table
388 ** iCur. Or if pIdx!=0 then X is column iColumn of index pIdx. pIdx
389 ** must be one of the indexes of table iCur.
391 ** The <op> must be one of the operators described by opMask.
393 ** If the search is for X and the WHERE clause contains terms of the
394 ** form X=Y then this routine might also return terms of the form
395 ** "Y <op> <expr>". The number of levels of transitivity is limited,
396 ** but is enough to handle most commonly occurring SQL statements.
398 ** If X is not the INTEGER PRIMARY KEY then X must be compatible with
401 static WhereTerm
*whereScanInit(
402 WhereScan
*pScan
, /* The WhereScan object being initialized */
403 WhereClause
*pWC
, /* The WHERE clause to be scanned */
404 int iCur
, /* Cursor to scan for */
405 int iColumn
, /* Column to scan for */
406 u32 opMask
, /* Operator(s) to scan for */
407 Index
*pIdx
/* Must be compatible with this index */
409 pScan
->pOrigWC
= pWC
;
413 pScan
->zCollName
= 0;
414 pScan
->opMask
= opMask
;
416 pScan
->aiCur
[0] = iCur
;
421 iColumn
= pIdx
->aiColumn
[j
];
422 if( iColumn
==XN_EXPR
){
423 pScan
->pIdxExpr
= pIdx
->aColExpr
->a
[j
].pExpr
;
424 pScan
->zCollName
= pIdx
->azColl
[j
];
425 pScan
->aiColumn
[0] = XN_EXPR
;
426 return whereScanInitIndexExpr(pScan
);
427 }else if( iColumn
==pIdx
->pTable
->iPKey
){
429 }else if( iColumn
>=0 ){
430 pScan
->idxaff
= pIdx
->pTable
->aCol
[iColumn
].affinity
;
431 pScan
->zCollName
= pIdx
->azColl
[j
];
433 }else if( iColumn
==XN_EXPR
){
436 pScan
->aiColumn
[0] = iColumn
;
437 return whereScanNext(pScan
);
441 ** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
442 ** where X is a reference to the iColumn of table iCur or of index pIdx
443 ** if pIdx!=0 and <op> is one of the WO_xx operator codes specified by
444 ** the op parameter. Return a pointer to the term. Return 0 if not found.
446 ** If pIdx!=0 then it must be one of the indexes of table iCur.
447 ** Search for terms matching the iColumn-th column of pIdx
448 ** rather than the iColumn-th column of table iCur.
450 ** The term returned might by Y=<expr> if there is another constraint in
451 ** the WHERE clause that specifies that X=Y. Any such constraints will be
452 ** identified by the WO_EQUIV bit in the pTerm->eOperator field. The
453 ** aiCur[]/iaColumn[] arrays hold X and all its equivalents. There are 11
454 ** slots in aiCur[]/aiColumn[] so that means we can look for X plus up to 10
455 ** other equivalent values. Hence a search for X will return <expr> if X=A1
456 ** and A1=A2 and A2=A3 and ... and A9=A10 and A10=<expr>.
458 ** If there are multiple terms in the WHERE clause of the form "X <op> <expr>"
459 ** then try for the one with no dependencies on <expr> - in other words where
460 ** <expr> is a constant expression of some kind. Only return entries of
461 ** the form "X <op> Y" where Y is a column in another table if no terms of
462 ** the form "X <op> <const-expr>" exist. If no terms with a constant RHS
463 ** exist, try to return a term that does not use WO_EQUIV.
465 WhereTerm
*sqlite3WhereFindTerm(
466 WhereClause
*pWC
, /* The WHERE clause to be searched */
467 int iCur
, /* Cursor number of LHS */
468 int iColumn
, /* Column number of LHS */
469 Bitmask notReady
, /* RHS must not overlap with this mask */
470 u32 op
, /* Mask of WO_xx values describing operator */
471 Index
*pIdx
/* Must be compatible with this index, if not NULL */
473 WhereTerm
*pResult
= 0;
477 p
= whereScanInit(&scan
, pWC
, iCur
, iColumn
, op
, pIdx
);
480 if( (p
->prereqRight
& notReady
)==0 ){
481 if( p
->prereqRight
==0 && (p
->eOperator
&op
)!=0 ){
482 testcase( p
->eOperator
& WO_IS
);
485 if( pResult
==0 ) pResult
= p
;
487 p
= whereScanNext(&scan
);
493 ** This function searches pList for an entry that matches the iCol-th column
496 ** If such an expression is found, its index in pList->a[] is returned. If
497 ** no expression is found, -1 is returned.
499 static int findIndexCol(
500 Parse
*pParse
, /* Parse context */
501 ExprList
*pList
, /* Expression list to search */
502 int iBase
, /* Cursor for table associated with pIdx */
503 Index
*pIdx
, /* Index to match column of */
504 int iCol
/* Column of index to match */
507 const char *zColl
= pIdx
->azColl
[iCol
];
509 for(i
=0; i
<pList
->nExpr
; i
++){
510 Expr
*p
= sqlite3ExprSkipCollateAndLikely(pList
->a
[i
].pExpr
);
512 && (p
->op
==TK_COLUMN
|| p
->op
==TK_AGG_COLUMN
)
513 && p
->iColumn
==pIdx
->aiColumn
[iCol
]
516 CollSeq
*pColl
= sqlite3ExprNNCollSeq(pParse
, pList
->a
[i
].pExpr
);
517 if( 0==sqlite3StrICmp(pColl
->zName
, zColl
) ){
527 ** Return TRUE if the iCol-th column of index pIdx is NOT NULL
529 static int indexColumnNotNull(Index
*pIdx
, int iCol
){
532 assert( iCol
>=0 && iCol
<pIdx
->nColumn
);
533 j
= pIdx
->aiColumn
[iCol
];
535 return pIdx
->pTable
->aCol
[j
].notNull
;
540 return 0; /* Assume an indexed expression can always yield a NULL */
546 ** Return true if the DISTINCT expression-list passed as the third argument
549 ** A DISTINCT list is redundant if any subset of the columns in the
550 ** DISTINCT list are collectively unique and individually non-null.
552 static int isDistinctRedundant(
553 Parse
*pParse
, /* Parsing context */
554 SrcList
*pTabList
, /* The FROM clause */
555 WhereClause
*pWC
, /* The WHERE clause */
556 ExprList
*pDistinct
/* The result set that needs to be DISTINCT */
563 /* If there is more than one table or sub-select in the FROM clause of
564 ** this query, then it will not be possible to show that the DISTINCT
565 ** clause is redundant. */
566 if( pTabList
->nSrc
!=1 ) return 0;
567 iBase
= pTabList
->a
[0].iCursor
;
568 pTab
= pTabList
->a
[0].pTab
;
570 /* If any of the expressions is an IPK column on table iBase, then return
571 ** true. Note: The (p->iTable==iBase) part of this test may be false if the
572 ** current SELECT is a correlated sub-query.
574 for(i
=0; i
<pDistinct
->nExpr
; i
++){
575 Expr
*p
= sqlite3ExprSkipCollateAndLikely(pDistinct
->a
[i
].pExpr
);
576 if( NEVER(p
==0) ) continue;
577 if( p
->op
!=TK_COLUMN
&& p
->op
!=TK_AGG_COLUMN
) continue;
578 if( p
->iTable
==iBase
&& p
->iColumn
<0 ) return 1;
581 /* Loop through all indices on the table, checking each to see if it makes
582 ** the DISTINCT qualifier redundant. It does so if:
584 ** 1. The index is itself UNIQUE, and
586 ** 2. All of the columns in the index are either part of the pDistinct
587 ** list, or else the WHERE clause contains a term of the form "col=X",
588 ** where X is a constant value. The collation sequences of the
589 ** comparison and select-list expressions must match those of the index.
591 ** 3. All of those index columns for which the WHERE clause does not
592 ** contain a "col=X" term are subject to a NOT NULL constraint.
594 for(pIdx
=pTab
->pIndex
; pIdx
; pIdx
=pIdx
->pNext
){
595 if( !IsUniqueIndex(pIdx
) ) continue;
596 if( pIdx
->pPartIdxWhere
) continue;
597 for(i
=0; i
<pIdx
->nKeyCol
; i
++){
598 if( 0==sqlite3WhereFindTerm(pWC
, iBase
, i
, ~(Bitmask
)0, WO_EQ
, pIdx
) ){
599 if( findIndexCol(pParse
, pDistinct
, iBase
, pIdx
, i
)<0 ) break;
600 if( indexColumnNotNull(pIdx
, i
)==0 ) break;
603 if( i
==pIdx
->nKeyCol
){
604 /* This index implies that the DISTINCT qualifier is redundant. */
614 ** Estimate the logarithm of the input value to base 2.
616 static LogEst
estLog(LogEst N
){
617 return N
<=10 ? 0 : sqlite3LogEst(N
) - 33;
621 ** Convert OP_Column opcodes to OP_Copy in previously generated code.
623 ** This routine runs over generated VDBE code and translates OP_Column
624 ** opcodes into OP_Copy when the table is being accessed via co-routine
625 ** instead of via table lookup.
627 ** If the iAutoidxCur is not zero, then any OP_Rowid instructions on
628 ** cursor iTabCur are transformed into OP_Sequence opcode for the
629 ** iAutoidxCur cursor, in order to generate unique rowids for the
630 ** automatic index being generated.
632 static void translateColumnToCopy(
633 Parse
*pParse
, /* Parsing context */
634 int iStart
, /* Translate from this opcode to the end */
635 int iTabCur
, /* OP_Column/OP_Rowid references to this table */
636 int iRegister
, /* The first column is in this register */
637 int iAutoidxCur
/* If non-zero, cursor of autoindex being generated */
639 Vdbe
*v
= pParse
->pVdbe
;
640 VdbeOp
*pOp
= sqlite3VdbeGetOp(v
, iStart
);
641 int iEnd
= sqlite3VdbeCurrentAddr(v
);
642 if( pParse
->db
->mallocFailed
) return;
643 for(; iStart
<iEnd
; iStart
++, pOp
++){
644 if( pOp
->p1
!=iTabCur
) continue;
645 if( pOp
->opcode
==OP_Column
){
646 pOp
->opcode
= OP_Copy
;
647 pOp
->p1
= pOp
->p2
+ iRegister
;
650 }else if( pOp
->opcode
==OP_Rowid
){
651 pOp
->opcode
= OP_Sequence
;
652 pOp
->p1
= iAutoidxCur
;
653 #ifdef SQLITE_ALLOW_ROWID_IN_VIEW
654 if( iAutoidxCur
==0 ){
655 pOp
->opcode
= OP_Null
;
664 ** Two routines for printing the content of an sqlite3_index_info
665 ** structure. Used for testing and debugging only. If neither
666 ** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines
669 #if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(WHERETRACE_ENABLED)
670 static void whereTraceIndexInfoInputs(sqlite3_index_info
*p
){
672 if( !sqlite3WhereTrace
) return;
673 for(i
=0; i
<p
->nConstraint
; i
++){
674 sqlite3DebugPrintf(" constraint[%d]: col=%d termid=%d op=%d usabled=%d\n",
676 p
->aConstraint
[i
].iColumn
,
677 p
->aConstraint
[i
].iTermOffset
,
678 p
->aConstraint
[i
].op
,
679 p
->aConstraint
[i
].usable
);
681 for(i
=0; i
<p
->nOrderBy
; i
++){
682 sqlite3DebugPrintf(" orderby[%d]: col=%d desc=%d\n",
684 p
->aOrderBy
[i
].iColumn
,
685 p
->aOrderBy
[i
].desc
);
688 static void whereTraceIndexInfoOutputs(sqlite3_index_info
*p
){
690 if( !sqlite3WhereTrace
) return;
691 for(i
=0; i
<p
->nConstraint
; i
++){
692 sqlite3DebugPrintf(" usage[%d]: argvIdx=%d omit=%d\n",
694 p
->aConstraintUsage
[i
].argvIndex
,
695 p
->aConstraintUsage
[i
].omit
);
697 sqlite3DebugPrintf(" idxNum=%d\n", p
->idxNum
);
698 sqlite3DebugPrintf(" idxStr=%s\n", p
->idxStr
);
699 sqlite3DebugPrintf(" orderByConsumed=%d\n", p
->orderByConsumed
);
700 sqlite3DebugPrintf(" estimatedCost=%g\n", p
->estimatedCost
);
701 sqlite3DebugPrintf(" estimatedRows=%lld\n", p
->estimatedRows
);
704 #define whereTraceIndexInfoInputs(A)
705 #define whereTraceIndexInfoOutputs(A)
708 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
710 ** Return TRUE if the WHERE clause term pTerm is of a form where it
711 ** could be used with an index to access pSrc, assuming an appropriate
714 static int termCanDriveIndex(
715 WhereTerm
*pTerm
, /* WHERE clause term to check */
716 SrcItem
*pSrc
, /* Table we are trying to access */
717 Bitmask notReady
/* Tables in outer loops of the join */
720 if( pTerm
->leftCursor
!=pSrc
->iCursor
) return 0;
721 if( (pTerm
->eOperator
& (WO_EQ
|WO_IS
))==0 ) return 0;
722 if( (pSrc
->fg
.jointype
& JT_LEFT
)
723 && !ExprHasProperty(pTerm
->pExpr
, EP_FromJoin
)
724 && (pTerm
->eOperator
& WO_IS
)
726 /* Cannot use an IS term from the WHERE clause as an index driver for
727 ** the RHS of a LEFT JOIN. Such a term can only be used if it is from
731 if( (pTerm
->prereqRight
& notReady
)!=0 ) return 0;
732 assert( (pTerm
->eOperator
& (WO_OR
|WO_AND
))==0 );
733 if( pTerm
->u
.x
.leftColumn
<0 ) return 0;
734 aff
= pSrc
->pTab
->aCol
[pTerm
->u
.x
.leftColumn
].affinity
;
735 if( !sqlite3IndexAffinityOk(pTerm
->pExpr
, aff
) ) return 0;
736 testcase( pTerm
->pExpr
->op
==TK_IS
);
742 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
744 ** Generate code to construct the Index object for an automatic index
745 ** and to set up the WhereLevel object pLevel so that the code generator
746 ** makes use of the automatic index.
748 static void constructAutomaticIndex(
749 Parse
*pParse
, /* The parsing context */
750 WhereClause
*pWC
, /* The WHERE clause */
751 SrcItem
*pSrc
, /* The FROM clause term to get the next index */
752 Bitmask notReady
, /* Mask of cursors that are not available */
753 WhereLevel
*pLevel
/* Write new index here */
755 int nKeyCol
; /* Number of columns in the constructed index */
756 WhereTerm
*pTerm
; /* A single term of the WHERE clause */
757 WhereTerm
*pWCEnd
; /* End of pWC->a[] */
758 Index
*pIdx
; /* Object describing the transient index */
759 Vdbe
*v
; /* Prepared statement under construction */
760 int addrInit
; /* Address of the initialization bypass jump */
761 Table
*pTable
; /* The table being indexed */
762 int addrTop
; /* Top of the index fill loop */
763 int regRecord
; /* Register holding an index record */
764 int n
; /* Column counter */
765 int i
; /* Loop counter */
766 int mxBitCol
; /* Maximum column in pSrc->colUsed */
767 CollSeq
*pColl
; /* Collating sequence to on a column */
768 WhereLoop
*pLoop
; /* The Loop object */
769 char *zNotUsed
; /* Extra space on the end of pIdx */
770 Bitmask idxCols
; /* Bitmap of columns used for indexing */
771 Bitmask extraCols
; /* Bitmap of additional columns */
772 u8 sentWarning
= 0; /* True if a warnning has been issued */
773 Expr
*pPartial
= 0; /* Partial Index Expression */
774 int iContinue
= 0; /* Jump here to skip excluded rows */
775 SrcItem
*pTabItem
; /* FROM clause term being indexed */
776 int addrCounter
= 0; /* Address where integer counter is initialized */
777 int regBase
; /* Array of registers where record is assembled */
779 /* Generate code to skip over the creation and initialization of the
780 ** transient index on 2nd and subsequent iterations of the loop. */
783 addrInit
= sqlite3VdbeAddOp0(v
, OP_Once
); VdbeCoverage(v
);
785 /* Count the number of columns that will be added to the index
786 ** and used to match WHERE clause constraints */
789 pWCEnd
= &pWC
->a
[pWC
->nTerm
];
790 pLoop
= pLevel
->pWLoop
;
792 for(pTerm
=pWC
->a
; pTerm
<pWCEnd
; pTerm
++){
793 Expr
*pExpr
= pTerm
->pExpr
;
794 assert( !ExprHasProperty(pExpr
, EP_FromJoin
) /* prereq always non-zero */
795 || pExpr
->iRightJoinTable
!=pSrc
->iCursor
/* for the right-hand */
796 || pLoop
->prereq
!=0 ); /* table of a LEFT JOIN */
798 && (pTerm
->wtFlags
& TERM_VIRTUAL
)==0
799 && !ExprHasProperty(pExpr
, EP_FromJoin
)
800 && sqlite3ExprIsTableConstant(pExpr
, pSrc
->iCursor
) ){
801 pPartial
= sqlite3ExprAnd(pParse
, pPartial
,
802 sqlite3ExprDup(pParse
->db
, pExpr
, 0));
804 if( termCanDriveIndex(pTerm
, pSrc
, notReady
) ){
807 assert( (pTerm
->eOperator
& (WO_OR
|WO_AND
))==0 );
808 iCol
= pTerm
->u
.x
.leftColumn
;
809 cMask
= iCol
>=BMS
? MASKBIT(BMS
-1) : MASKBIT(iCol
);
810 testcase( iCol
==BMS
);
811 testcase( iCol
==BMS
-1 );
813 sqlite3_log(SQLITE_WARNING_AUTOINDEX
,
814 "automatic index on %s(%s)", pTable
->zName
,
815 pTable
->aCol
[iCol
].zCnName
);
818 if( (idxCols
& cMask
)==0 ){
819 if( whereLoopResize(pParse
->db
, pLoop
, nKeyCol
+1) ){
820 goto end_auto_index_create
;
822 pLoop
->aLTerm
[nKeyCol
++] = pTerm
;
827 assert( nKeyCol
>0 || pParse
->db
->mallocFailed
);
828 pLoop
->u
.btree
.nEq
= pLoop
->nLTerm
= nKeyCol
;
829 pLoop
->wsFlags
= WHERE_COLUMN_EQ
| WHERE_IDX_ONLY
| WHERE_INDEXED
832 /* Count the number of additional columns needed to create a
833 ** covering index. A "covering index" is an index that contains all
834 ** columns that are needed by the query. With a covering index, the
835 ** original table never needs to be accessed. Automatic indices must
836 ** be a covering index because the index will not be updated if the
837 ** original table changes and the index and table cannot both be used
838 ** if they go out of sync.
840 extraCols
= pSrc
->colUsed
& (~idxCols
| MASKBIT(BMS
-1));
841 mxBitCol
= MIN(BMS
-1,pTable
->nCol
);
842 testcase( pTable
->nCol
==BMS
-1 );
843 testcase( pTable
->nCol
==BMS
-2 );
844 for(i
=0; i
<mxBitCol
; i
++){
845 if( extraCols
& MASKBIT(i
) ) nKeyCol
++;
847 if( pSrc
->colUsed
& MASKBIT(BMS
-1) ){
848 nKeyCol
+= pTable
->nCol
- BMS
+ 1;
851 /* Construct the Index object to describe this index */
852 pIdx
= sqlite3AllocateIndexObject(pParse
->db
, nKeyCol
+1, 0, &zNotUsed
);
853 if( pIdx
==0 ) goto end_auto_index_create
;
854 pLoop
->u
.btree
.pIndex
= pIdx
;
855 pIdx
->zName
= "auto-index";
856 pIdx
->pTable
= pTable
;
859 for(pTerm
=pWC
->a
; pTerm
<pWCEnd
; pTerm
++){
860 if( termCanDriveIndex(pTerm
, pSrc
, notReady
) ){
863 assert( (pTerm
->eOperator
& (WO_OR
|WO_AND
))==0 );
864 iCol
= pTerm
->u
.x
.leftColumn
;
865 cMask
= iCol
>=BMS
? MASKBIT(BMS
-1) : MASKBIT(iCol
);
866 testcase( iCol
==BMS
-1 );
867 testcase( iCol
==BMS
);
868 if( (idxCols
& cMask
)==0 ){
869 Expr
*pX
= pTerm
->pExpr
;
871 pIdx
->aiColumn
[n
] = pTerm
->u
.x
.leftColumn
;
872 pColl
= sqlite3ExprCompareCollSeq(pParse
, pX
);
873 assert( pColl
!=0 || pParse
->nErr
>0 ); /* TH3 collate01.800 */
874 pIdx
->azColl
[n
] = pColl
? pColl
->zName
: sqlite3StrBINARY
;
879 assert( (u32
)n
==pLoop
->u
.btree
.nEq
);
881 /* Add additional columns needed to make the automatic index into
882 ** a covering index */
883 for(i
=0; i
<mxBitCol
; i
++){
884 if( extraCols
& MASKBIT(i
) ){
885 pIdx
->aiColumn
[n
] = i
;
886 pIdx
->azColl
[n
] = sqlite3StrBINARY
;
890 if( pSrc
->colUsed
& MASKBIT(BMS
-1) ){
891 for(i
=BMS
-1; i
<pTable
->nCol
; i
++){
892 pIdx
->aiColumn
[n
] = i
;
893 pIdx
->azColl
[n
] = sqlite3StrBINARY
;
897 assert( n
==nKeyCol
);
898 pIdx
->aiColumn
[n
] = XN_ROWID
;
899 pIdx
->azColl
[n
] = sqlite3StrBINARY
;
901 /* Create the automatic index */
902 assert( pLevel
->iIdxCur
>=0 );
903 pLevel
->iIdxCur
= pParse
->nTab
++;
904 sqlite3VdbeAddOp2(v
, OP_OpenAutoindex
, pLevel
->iIdxCur
, nKeyCol
+1);
905 sqlite3VdbeSetP4KeyInfo(pParse
, pIdx
);
906 VdbeComment((v
, "for %s", pTable
->zName
));
908 /* Fill the automatic index with content */
909 pTabItem
= &pWC
->pWInfo
->pTabList
->a
[pLevel
->iFrom
];
910 if( pTabItem
->fg
.viaCoroutine
){
911 int regYield
= pTabItem
->regReturn
;
912 addrCounter
= sqlite3VdbeAddOp2(v
, OP_Integer
, 0, 0);
913 sqlite3VdbeAddOp3(v
, OP_InitCoroutine
, regYield
, 0, pTabItem
->addrFillSub
);
914 addrTop
= sqlite3VdbeAddOp1(v
, OP_Yield
, regYield
);
916 VdbeComment((v
, "next row of %s", pTabItem
->pTab
->zName
));
918 addrTop
= sqlite3VdbeAddOp1(v
, OP_Rewind
, pLevel
->iTabCur
); VdbeCoverage(v
);
921 iContinue
= sqlite3VdbeMakeLabel(pParse
);
922 sqlite3ExprIfFalse(pParse
, pPartial
, iContinue
, SQLITE_JUMPIFNULL
);
923 pLoop
->wsFlags
|= WHERE_PARTIALIDX
;
925 regRecord
= sqlite3GetTempReg(pParse
);
926 regBase
= sqlite3GenerateIndexKey(
927 pParse
, pIdx
, pLevel
->iTabCur
, regRecord
, 0, 0, 0, 0
929 sqlite3VdbeAddOp2(v
, OP_IdxInsert
, pLevel
->iIdxCur
, regRecord
);
930 sqlite3VdbeChangeP5(v
, OPFLAG_USESEEKRESULT
);
931 if( pPartial
) sqlite3VdbeResolveLabel(v
, iContinue
);
932 if( pTabItem
->fg
.viaCoroutine
){
933 sqlite3VdbeChangeP2(v
, addrCounter
, regBase
+n
);
934 testcase( pParse
->db
->mallocFailed
);
935 assert( pLevel
->iIdxCur
>0 );
936 translateColumnToCopy(pParse
, addrTop
, pLevel
->iTabCur
,
937 pTabItem
->regResult
, pLevel
->iIdxCur
);
938 sqlite3VdbeGoto(v
, addrTop
);
939 pTabItem
->fg
.viaCoroutine
= 0;
941 sqlite3VdbeAddOp2(v
, OP_Next
, pLevel
->iTabCur
, addrTop
+1); VdbeCoverage(v
);
942 sqlite3VdbeChangeP5(v
, SQLITE_STMTSTATUS_AUTOINDEX
);
944 sqlite3VdbeJumpHere(v
, addrTop
);
945 sqlite3ReleaseTempReg(pParse
, regRecord
);
947 /* Jump here when skipping the initialization */
948 sqlite3VdbeJumpHere(v
, addrInit
);
950 end_auto_index_create
:
951 sqlite3ExprDelete(pParse
->db
, pPartial
);
953 #endif /* SQLITE_OMIT_AUTOMATIC_INDEX */
955 #ifndef SQLITE_OMIT_VIRTUALTABLE
957 ** Allocate and populate an sqlite3_index_info structure. It is the
958 ** responsibility of the caller to eventually release the structure
959 ** by passing the pointer returned by this function to sqlite3_free().
961 static sqlite3_index_info
*allocateIndexInfo(
962 Parse
*pParse
, /* The parsing context */
963 WhereClause
*pWC
, /* The WHERE clause being analyzed */
964 Bitmask mUnusable
, /* Ignore terms with these prereqs */
965 SrcItem
*pSrc
, /* The FROM clause term that is the vtab */
966 ExprList
*pOrderBy
, /* The ORDER BY clause */
967 u16
*pmNoOmit
/* Mask of terms not to omit */
971 struct sqlite3_index_constraint
*pIdxCons
;
972 struct sqlite3_index_orderby
*pIdxOrderBy
;
973 struct sqlite3_index_constraint_usage
*pUsage
;
974 struct HiddenIndexInfo
*pHidden
;
977 sqlite3_index_info
*pIdxInfo
;
980 /* Count the number of possible WHERE clause constraints referring
981 ** to this virtual table */
982 for(i
=nTerm
=0, pTerm
=pWC
->a
; i
<pWC
->nTerm
; i
++, pTerm
++){
983 if( pTerm
->leftCursor
!= pSrc
->iCursor
) continue;
984 if( pTerm
->prereqRight
& mUnusable
) continue;
985 assert( IsPowerOfTwo(pTerm
->eOperator
& ~WO_EQUIV
) );
986 testcase( pTerm
->eOperator
& WO_IN
);
987 testcase( pTerm
->eOperator
& WO_ISNULL
);
988 testcase( pTerm
->eOperator
& WO_IS
);
989 testcase( pTerm
->eOperator
& WO_ALL
);
990 if( (pTerm
->eOperator
& ~(WO_EQUIV
))==0 ) continue;
991 if( pTerm
->wtFlags
& TERM_VNULL
) continue;
992 assert( (pTerm
->eOperator
& (WO_OR
|WO_AND
))==0 );
993 assert( pTerm
->u
.x
.leftColumn
>=(-1) );
997 /* If the ORDER BY clause contains only columns in the current
998 ** virtual table then allocate space for the aOrderBy part of
999 ** the sqlite3_index_info structure.
1003 int n
= pOrderBy
->nExpr
;
1005 Expr
*pExpr
= pOrderBy
->a
[i
].pExpr
;
1006 if( pExpr
->op
!=TK_COLUMN
|| pExpr
->iTable
!=pSrc
->iCursor
) break;
1007 if( pOrderBy
->a
[i
].sortFlags
& KEYINFO_ORDER_BIGNULL
) break;
1014 /* Allocate the sqlite3_index_info structure
1016 pIdxInfo
= sqlite3DbMallocZero(pParse
->db
, sizeof(*pIdxInfo
)
1017 + (sizeof(*pIdxCons
) + sizeof(*pUsage
))*nTerm
1018 + sizeof(*pIdxOrderBy
)*nOrderBy
+ sizeof(*pHidden
) );
1020 sqlite3ErrorMsg(pParse
, "out of memory");
1023 pHidden
= (struct HiddenIndexInfo
*)&pIdxInfo
[1];
1024 pIdxCons
= (struct sqlite3_index_constraint
*)&pHidden
[1];
1025 pIdxOrderBy
= (struct sqlite3_index_orderby
*)&pIdxCons
[nTerm
];
1026 pUsage
= (struct sqlite3_index_constraint_usage
*)&pIdxOrderBy
[nOrderBy
];
1027 pIdxInfo
->nOrderBy
= nOrderBy
;
1028 pIdxInfo
->aConstraint
= pIdxCons
;
1029 pIdxInfo
->aOrderBy
= pIdxOrderBy
;
1030 pIdxInfo
->aConstraintUsage
= pUsage
;
1032 pHidden
->pParse
= pParse
;
1033 for(i
=j
=0, pTerm
=pWC
->a
; i
<pWC
->nTerm
; i
++, pTerm
++){
1035 if( pTerm
->leftCursor
!= pSrc
->iCursor
) continue;
1036 if( pTerm
->prereqRight
& mUnusable
) continue;
1037 assert( IsPowerOfTwo(pTerm
->eOperator
& ~WO_EQUIV
) );
1038 testcase( pTerm
->eOperator
& WO_IN
);
1039 testcase( pTerm
->eOperator
& WO_IS
);
1040 testcase( pTerm
->eOperator
& WO_ISNULL
);
1041 testcase( pTerm
->eOperator
& WO_ALL
);
1042 if( (pTerm
->eOperator
& ~(WO_EQUIV
))==0 ) continue;
1043 if( pTerm
->wtFlags
& TERM_VNULL
) continue;
1045 /* tag-20191211-002: WHERE-clause constraints are not useful to the
1046 ** right-hand table of a LEFT JOIN. See tag-20191211-001 for the
1047 ** equivalent restriction for ordinary tables. */
1048 if( (pSrc
->fg
.jointype
& JT_LEFT
)!=0
1049 && !ExprHasProperty(pTerm
->pExpr
, EP_FromJoin
)
1053 assert( (pTerm
->eOperator
& (WO_OR
|WO_AND
))==0 );
1054 assert( pTerm
->u
.x
.leftColumn
>=(-1) );
1055 pIdxCons
[j
].iColumn
= pTerm
->u
.x
.leftColumn
;
1056 pIdxCons
[j
].iTermOffset
= i
;
1057 op
= pTerm
->eOperator
& WO_ALL
;
1058 if( op
==WO_IN
) op
= WO_EQ
;
1060 pIdxCons
[j
].op
= pTerm
->eMatchOp
;
1061 }else if( op
& (WO_ISNULL
|WO_IS
) ){
1062 if( op
==WO_ISNULL
){
1063 pIdxCons
[j
].op
= SQLITE_INDEX_CONSTRAINT_ISNULL
;
1065 pIdxCons
[j
].op
= SQLITE_INDEX_CONSTRAINT_IS
;
1068 pIdxCons
[j
].op
= (u8
)op
;
1069 /* The direct assignment in the previous line is possible only because
1070 ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical. The
1071 ** following asserts verify this fact. */
1072 assert( WO_EQ
==SQLITE_INDEX_CONSTRAINT_EQ
);
1073 assert( WO_LT
==SQLITE_INDEX_CONSTRAINT_LT
);
1074 assert( WO_LE
==SQLITE_INDEX_CONSTRAINT_LE
);
1075 assert( WO_GT
==SQLITE_INDEX_CONSTRAINT_GT
);
1076 assert( WO_GE
==SQLITE_INDEX_CONSTRAINT_GE
);
1077 assert( pTerm
->eOperator
&(WO_IN
|WO_EQ
|WO_LT
|WO_LE
|WO_GT
|WO_GE
|WO_AUX
) );
1079 if( op
& (WO_LT
|WO_LE
|WO_GT
|WO_GE
)
1080 && sqlite3ExprIsVector(pTerm
->pExpr
->pRight
)
1083 if( j
<16 ) mNoOmit
|= (1 << j
);
1084 if( op
==WO_LT
) pIdxCons
[j
].op
= WO_LE
;
1085 if( op
==WO_GT
) pIdxCons
[j
].op
= WO_GE
;
1091 pIdxInfo
->nConstraint
= j
;
1092 for(i
=0; i
<nOrderBy
; i
++){
1093 Expr
*pExpr
= pOrderBy
->a
[i
].pExpr
;
1094 pIdxOrderBy
[i
].iColumn
= pExpr
->iColumn
;
1095 pIdxOrderBy
[i
].desc
= pOrderBy
->a
[i
].sortFlags
& KEYINFO_ORDER_DESC
;
1098 *pmNoOmit
= mNoOmit
;
1103 ** The table object reference passed as the second argument to this function
1104 ** must represent a virtual table. This function invokes the xBestIndex()
1105 ** method of the virtual table with the sqlite3_index_info object that
1106 ** comes in as the 3rd argument to this function.
1108 ** If an error occurs, pParse is populated with an error message and an
1109 ** appropriate error code is returned. A return of SQLITE_CONSTRAINT from
1110 ** xBestIndex is not considered an error. SQLITE_CONSTRAINT indicates that
1111 ** the current configuration of "unusable" flags in sqlite3_index_info can
1112 ** not result in a valid plan.
1114 ** Whether or not an error is returned, it is the responsibility of the
1115 ** caller to eventually free p->idxStr if p->needToFreeIdxStr indicates
1116 ** that this is required.
1118 static int vtabBestIndex(Parse
*pParse
, Table
*pTab
, sqlite3_index_info
*p
){
1119 sqlite3_vtab
*pVtab
= sqlite3GetVTable(pParse
->db
, pTab
)->pVtab
;
1122 whereTraceIndexInfoInputs(p
);
1123 rc
= pVtab
->pModule
->xBestIndex(pVtab
, p
);
1124 whereTraceIndexInfoOutputs(p
);
1126 if( rc
!=SQLITE_OK
&& rc
!=SQLITE_CONSTRAINT
){
1127 if( rc
==SQLITE_NOMEM
){
1128 sqlite3OomFault(pParse
->db
);
1129 }else if( !pVtab
->zErrMsg
){
1130 sqlite3ErrorMsg(pParse
, "%s", sqlite3ErrStr(rc
));
1132 sqlite3ErrorMsg(pParse
, "%s", pVtab
->zErrMsg
);
1135 sqlite3_free(pVtab
->zErrMsg
);
1139 #endif /* !defined(SQLITE_OMIT_VIRTUALTABLE) */
1141 #ifdef SQLITE_ENABLE_STAT4
1143 ** Estimate the location of a particular key among all keys in an
1144 ** index. Store the results in aStat as follows:
1146 ** aStat[0] Est. number of rows less than pRec
1147 ** aStat[1] Est. number of rows equal to pRec
1149 ** Return the index of the sample that is the smallest sample that
1150 ** is greater than or equal to pRec. Note that this index is not an index
1151 ** into the aSample[] array - it is an index into a virtual set of samples
1152 ** based on the contents of aSample[] and the number of fields in record
1155 static int whereKeyStats(
1156 Parse
*pParse
, /* Database connection */
1157 Index
*pIdx
, /* Index to consider domain of */
1158 UnpackedRecord
*pRec
, /* Vector of values to consider */
1159 int roundUp
, /* Round up if true. Round down if false */
1160 tRowcnt
*aStat
/* OUT: stats written here */
1162 IndexSample
*aSample
= pIdx
->aSample
;
1163 int iCol
; /* Index of required stats in anEq[] etc. */
1164 int i
; /* Index of first sample >= pRec */
1165 int iSample
; /* Smallest sample larger than or equal to pRec */
1166 int iMin
= 0; /* Smallest sample not yet tested */
1167 int iTest
; /* Next sample to test */
1168 int res
; /* Result of comparison operation */
1169 int nField
; /* Number of fields in pRec */
1170 tRowcnt iLower
= 0; /* anLt[] + anEq[] of largest sample pRec is > */
1172 #ifndef SQLITE_DEBUG
1173 UNUSED_PARAMETER( pParse
);
1176 assert( pIdx
->nSample
>0 );
1177 assert( pRec
->nField
>0 && pRec
->nField
<=pIdx
->nSampleCol
);
1179 /* Do a binary search to find the first sample greater than or equal
1180 ** to pRec. If pRec contains a single field, the set of samples to search
1181 ** is simply the aSample[] array. If the samples in aSample[] contain more
1182 ** than one fields, all fields following the first are ignored.
1184 ** If pRec contains N fields, where N is more than one, then as well as the
1185 ** samples in aSample[] (truncated to N fields), the search also has to
1186 ** consider prefixes of those samples. For example, if the set of samples
1189 ** aSample[0] = (a, 5)
1190 ** aSample[1] = (a, 10)
1191 ** aSample[2] = (b, 5)
1192 ** aSample[3] = (c, 100)
1193 ** aSample[4] = (c, 105)
1195 ** Then the search space should ideally be the samples above and the
1196 ** unique prefixes [a], [b] and [c]. But since that is hard to organize,
1197 ** the code actually searches this set:
1210 ** For each sample in the aSample[] array, N samples are present in the
1211 ** effective sample array. In the above, samples 0 and 1 are based on
1212 ** sample aSample[0]. Samples 2 and 3 on aSample[1] etc.
1214 ** Often, sample i of each block of N effective samples has (i+1) fields.
1215 ** Except, each sample may be extended to ensure that it is greater than or
1216 ** equal to the previous sample in the array. For example, in the above,
1217 ** sample 2 is the first sample of a block of N samples, so at first it
1218 ** appears that it should be 1 field in size. However, that would make it
1219 ** smaller than sample 1, so the binary search would not work. As a result,
1220 ** it is extended to two fields. The duplicates that this creates do not
1221 ** cause any problems.
1223 nField
= pRec
->nField
;
1225 iSample
= pIdx
->nSample
* nField
;
1227 int iSamp
; /* Index in aSample[] of test sample */
1228 int n
; /* Number of fields in test sample */
1230 iTest
= (iMin
+iSample
)/2;
1231 iSamp
= iTest
/ nField
;
1233 /* The proposed effective sample is a prefix of sample aSample[iSamp].
1234 ** Specifically, the shortest prefix of at least (1 + iTest%nField)
1235 ** fields that is greater than the previous effective sample. */
1236 for(n
=(iTest
% nField
) + 1; n
<nField
; n
++){
1237 if( aSample
[iSamp
-1].anLt
[n
-1]!=aSample
[iSamp
].anLt
[n
-1] ) break;
1244 res
= sqlite3VdbeRecordCompare(aSample
[iSamp
].n
, aSample
[iSamp
].p
, pRec
);
1246 iLower
= aSample
[iSamp
].anLt
[n
-1] + aSample
[iSamp
].anEq
[n
-1];
1248 }else if( res
==0 && n
<nField
){
1249 iLower
= aSample
[iSamp
].anLt
[n
-1];
1256 }while( res
&& iMin
<iSample
);
1257 i
= iSample
/ nField
;
1260 /* The following assert statements check that the binary search code
1261 ** above found the right answer. This block serves no purpose other
1262 ** than to invoke the asserts. */
1263 if( pParse
->db
->mallocFailed
==0 ){
1265 /* If (res==0) is true, then pRec must be equal to sample i. */
1266 assert( i
<pIdx
->nSample
);
1267 assert( iCol
==nField
-1 );
1268 pRec
->nField
= nField
;
1269 assert( 0==sqlite3VdbeRecordCompare(aSample
[i
].n
, aSample
[i
].p
, pRec
)
1270 || pParse
->db
->mallocFailed
1273 /* Unless i==pIdx->nSample, indicating that pRec is larger than
1274 ** all samples in the aSample[] array, pRec must be smaller than the
1275 ** (iCol+1) field prefix of sample i. */
1276 assert( i
<=pIdx
->nSample
&& i
>=0 );
1277 pRec
->nField
= iCol
+1;
1278 assert( i
==pIdx
->nSample
1279 || sqlite3VdbeRecordCompare(aSample
[i
].n
, aSample
[i
].p
, pRec
)>0
1280 || pParse
->db
->mallocFailed
);
1282 /* if i==0 and iCol==0, then record pRec is smaller than all samples
1283 ** in the aSample[] array. Otherwise, if (iCol>0) then pRec must
1284 ** be greater than or equal to the (iCol) field prefix of sample i.
1285 ** If (i>0), then pRec must also be greater than sample (i-1). */
1287 pRec
->nField
= iCol
;
1288 assert( sqlite3VdbeRecordCompare(aSample
[i
].n
, aSample
[i
].p
, pRec
)<=0
1289 || pParse
->db
->mallocFailed
);
1292 pRec
->nField
= nField
;
1293 assert( sqlite3VdbeRecordCompare(aSample
[i
-1].n
, aSample
[i
-1].p
, pRec
)<0
1294 || pParse
->db
->mallocFailed
);
1298 #endif /* ifdef SQLITE_DEBUG */
1301 /* Record pRec is equal to sample i */
1302 assert( iCol
==nField
-1 );
1303 aStat
[0] = aSample
[i
].anLt
[iCol
];
1304 aStat
[1] = aSample
[i
].anEq
[iCol
];
1306 /* At this point, the (iCol+1) field prefix of aSample[i] is the first
1307 ** sample that is greater than pRec. Or, if i==pIdx->nSample then pRec
1308 ** is larger than all samples in the array. */
1309 tRowcnt iUpper
, iGap
;
1310 if( i
>=pIdx
->nSample
){
1311 iUpper
= sqlite3LogEstToInt(pIdx
->aiRowLogEst
[0]);
1313 iUpper
= aSample
[i
].anLt
[iCol
];
1316 if( iLower
>=iUpper
){
1319 iGap
= iUpper
- iLower
;
1326 aStat
[0] = iLower
+ iGap
;
1327 aStat
[1] = pIdx
->aAvgEq
[nField
-1];
1330 /* Restore the pRec->nField value before returning. */
1331 pRec
->nField
= nField
;
1334 #endif /* SQLITE_ENABLE_STAT4 */
1337 ** If it is not NULL, pTerm is a term that provides an upper or lower
1338 ** bound on a range scan. Without considering pTerm, it is estimated
1339 ** that the scan will visit nNew rows. This function returns the number
1340 ** estimated to be visited after taking pTerm into account.
1342 ** If the user explicitly specified a likelihood() value for this term,
1343 ** then the return value is the likelihood multiplied by the number of
1344 ** input rows. Otherwise, this function assumes that an "IS NOT NULL" term
1345 ** has a likelihood of 0.50, and any other term a likelihood of 0.25.
1347 static LogEst
whereRangeAdjust(WhereTerm
*pTerm
, LogEst nNew
){
1350 if( pTerm
->truthProb
<=0 ){
1351 nRet
+= pTerm
->truthProb
;
1352 }else if( (pTerm
->wtFlags
& TERM_VNULL
)==0 ){
1353 nRet
-= 20; assert( 20==sqlite3LogEst(4) );
1360 #ifdef SQLITE_ENABLE_STAT4
1362 ** Return the affinity for a single column of an index.
1364 char sqlite3IndexColumnAffinity(sqlite3
*db
, Index
*pIdx
, int iCol
){
1365 assert( iCol
>=0 && iCol
<pIdx
->nColumn
);
1366 if( !pIdx
->zColAff
){
1367 if( sqlite3IndexAffinityStr(db
, pIdx
)==0 ) return SQLITE_AFF_BLOB
;
1369 assert( pIdx
->zColAff
[iCol
]!=0 );
1370 return pIdx
->zColAff
[iCol
];
1375 #ifdef SQLITE_ENABLE_STAT4
1377 ** This function is called to estimate the number of rows visited by a
1378 ** range-scan on a skip-scan index. For example:
1380 ** CREATE INDEX i1 ON t1(a, b, c);
1381 ** SELECT * FROM t1 WHERE a=? AND c BETWEEN ? AND ?;
1383 ** Value pLoop->nOut is currently set to the estimated number of rows
1384 ** visited for scanning (a=? AND b=?). This function reduces that estimate
1385 ** by some factor to account for the (c BETWEEN ? AND ?) expression based
1386 ** on the stat4 data for the index. this scan will be peformed multiple
1387 ** times (once for each (a,b) combination that matches a=?) is dealt with
1390 ** It does this by scanning through all stat4 samples, comparing values
1391 ** extracted from pLower and pUpper with the corresponding column in each
1392 ** sample. If L and U are the number of samples found to be less than or
1393 ** equal to the values extracted from pLower and pUpper respectively, and
1394 ** N is the total number of samples, the pLoop->nOut value is adjusted
1397 ** nOut = nOut * ( min(U - L, 1) / N )
1399 ** If pLower is NULL, or a value cannot be extracted from the term, L is
1400 ** set to zero. If pUpper is NULL, or a value cannot be extracted from it,
1403 ** Normally, this function sets *pbDone to 1 before returning. However,
1404 ** if no value can be extracted from either pLower or pUpper (and so the
1405 ** estimate of the number of rows delivered remains unchanged), *pbDone
1408 ** If an error occurs, an SQLite error code is returned. Otherwise,
1411 static int whereRangeSkipScanEst(
1412 Parse
*pParse
, /* Parsing & code generating context */
1413 WhereTerm
*pLower
, /* Lower bound on the range. ex: "x>123" Might be NULL */
1414 WhereTerm
*pUpper
, /* Upper bound on the range. ex: "x<455" Might be NULL */
1415 WhereLoop
*pLoop
, /* Update the .nOut value of this loop */
1416 int *pbDone
/* Set to true if at least one expr. value extracted */
1418 Index
*p
= pLoop
->u
.btree
.pIndex
;
1419 int nEq
= pLoop
->u
.btree
.nEq
;
1420 sqlite3
*db
= pParse
->db
;
1422 int nUpper
= p
->nSample
+1;
1424 u8 aff
= sqlite3IndexColumnAffinity(db
, p
, nEq
);
1427 sqlite3_value
*p1
= 0; /* Value extracted from pLower */
1428 sqlite3_value
*p2
= 0; /* Value extracted from pUpper */
1429 sqlite3_value
*pVal
= 0; /* Value extracted from record */
1431 pColl
= sqlite3LocateCollSeq(pParse
, p
->azColl
[nEq
]);
1433 rc
= sqlite3Stat4ValueFromExpr(pParse
, pLower
->pExpr
->pRight
, aff
, &p1
);
1436 if( pUpper
&& rc
==SQLITE_OK
){
1437 rc
= sqlite3Stat4ValueFromExpr(pParse
, pUpper
->pExpr
->pRight
, aff
, &p2
);
1438 nUpper
= p2
? 0 : p
->nSample
;
1444 for(i
=0; rc
==SQLITE_OK
&& i
<p
->nSample
; i
++){
1445 rc
= sqlite3Stat4Column(db
, p
->aSample
[i
].p
, p
->aSample
[i
].n
, nEq
, &pVal
);
1446 if( rc
==SQLITE_OK
&& p1
){
1447 int res
= sqlite3MemCompare(p1
, pVal
, pColl
);
1448 if( res
>=0 ) nLower
++;
1450 if( rc
==SQLITE_OK
&& p2
){
1451 int res
= sqlite3MemCompare(p2
, pVal
, pColl
);
1452 if( res
>=0 ) nUpper
++;
1455 nDiff
= (nUpper
- nLower
);
1456 if( nDiff
<=0 ) nDiff
= 1;
1458 /* If there is both an upper and lower bound specified, and the
1459 ** comparisons indicate that they are close together, use the fallback
1460 ** method (assume that the scan visits 1/64 of the rows) for estimating
1461 ** the number of rows visited. Otherwise, estimate the number of rows
1462 ** using the method described in the header comment for this function. */
1463 if( nDiff
!=1 || pUpper
==0 || pLower
==0 ){
1464 int nAdjust
= (sqlite3LogEst(p
->nSample
) - sqlite3LogEst(nDiff
));
1465 pLoop
->nOut
-= nAdjust
;
1467 WHERETRACE(0x10, ("range skip-scan regions: %u..%u adjust=%d est=%d\n",
1468 nLower
, nUpper
, nAdjust
*-1, pLoop
->nOut
));
1472 assert( *pbDone
==0 );
1475 sqlite3ValueFree(p1
);
1476 sqlite3ValueFree(p2
);
1477 sqlite3ValueFree(pVal
);
1481 #endif /* SQLITE_ENABLE_STAT4 */
1484 ** This function is used to estimate the number of rows that will be visited
1485 ** by scanning an index for a range of values. The range may have an upper
1486 ** bound, a lower bound, or both. The WHERE clause terms that set the upper
1487 ** and lower bounds are represented by pLower and pUpper respectively. For
1488 ** example, assuming that index p is on t1(a):
1490 ** ... FROM t1 WHERE a > ? AND a < ? ...
1495 ** If either of the upper or lower bound is not present, then NULL is passed in
1496 ** place of the corresponding WhereTerm.
1498 ** The value in (pBuilder->pNew->u.btree.nEq) is the number of the index
1499 ** column subject to the range constraint. Or, equivalently, the number of
1500 ** equality constraints optimized by the proposed index scan. For example,
1501 ** assuming index p is on t1(a, b), and the SQL query is:
1503 ** ... FROM t1 WHERE a = ? AND b > ? AND b < ? ...
1505 ** then nEq is set to 1 (as the range restricted column, b, is the second
1506 ** left-most column of the index). Or, if the query is:
1508 ** ... FROM t1 WHERE a > ? AND a < ? ...
1510 ** then nEq is set to 0.
1512 ** When this function is called, *pnOut is set to the sqlite3LogEst() of the
1513 ** number of rows that the index scan is expected to visit without
1514 ** considering the range constraints. If nEq is 0, then *pnOut is the number of
1515 ** rows in the index. Assuming no error occurs, *pnOut is adjusted (reduced)
1516 ** to account for the range constraints pLower and pUpper.
1518 ** In the absence of sqlite_stat4 ANALYZE data, or if such data cannot be
1519 ** used, a single range inequality reduces the search space by a factor of 4.
1520 ** and a pair of constraints (x>? AND x<?) reduces the expected number of
1521 ** rows visited by a factor of 64.
1523 static int whereRangeScanEst(
1524 Parse
*pParse
, /* Parsing & code generating context */
1525 WhereLoopBuilder
*pBuilder
,
1526 WhereTerm
*pLower
, /* Lower bound on the range. ex: "x>123" Might be NULL */
1527 WhereTerm
*pUpper
, /* Upper bound on the range. ex: "x<455" Might be NULL */
1528 WhereLoop
*pLoop
/* Modify the .nOut and maybe .rRun fields */
1531 int nOut
= pLoop
->nOut
;
1534 #ifdef SQLITE_ENABLE_STAT4
1535 Index
*p
= pLoop
->u
.btree
.pIndex
;
1536 int nEq
= pLoop
->u
.btree
.nEq
;
1538 if( p
->nSample
>0 && ALWAYS(nEq
<p
->nSampleCol
)
1539 && OptimizationEnabled(pParse
->db
, SQLITE_Stat4
)
1541 if( nEq
==pBuilder
->nRecValid
){
1542 UnpackedRecord
*pRec
= pBuilder
->pRec
;
1544 int nBtm
= pLoop
->u
.btree
.nBtm
;
1545 int nTop
= pLoop
->u
.btree
.nTop
;
1547 /* Variable iLower will be set to the estimate of the number of rows in
1548 ** the index that are less than the lower bound of the range query. The
1549 ** lower bound being the concatenation of $P and $L, where $P is the
1550 ** key-prefix formed by the nEq values matched against the nEq left-most
1551 ** columns of the index, and $L is the value in pLower.
1553 ** Or, if pLower is NULL or $L cannot be extracted from it (because it
1554 ** is not a simple variable or literal value), the lower bound of the
1555 ** range is $P. Due to a quirk in the way whereKeyStats() works, even
1556 ** if $L is available, whereKeyStats() is called for both ($P) and
1557 ** ($P:$L) and the larger of the two returned values is used.
1559 ** Similarly, iUpper is to be set to the estimate of the number of rows
1560 ** less than the upper bound of the range query. Where the upper bound
1561 ** is either ($P) or ($P:$U). Again, even if $U is available, both values
1562 ** of iUpper are requested of whereKeyStats() and the smaller used.
1564 ** The number of rows between the two bounds is then just iUpper-iLower.
1566 tRowcnt iLower
; /* Rows less than the lower bound */
1567 tRowcnt iUpper
; /* Rows less than the upper bound */
1568 int iLwrIdx
= -2; /* aSample[] for the lower bound */
1569 int iUprIdx
= -1; /* aSample[] for the upper bound */
1572 testcase( pRec
->nField
!=pBuilder
->nRecValid
);
1573 pRec
->nField
= pBuilder
->nRecValid
;
1575 /* Determine iLower and iUpper using ($P) only. */
1578 iUpper
= p
->nRowEst0
;
1580 /* Note: this call could be optimized away - since the same values must
1581 ** have been requested when testing key $P in whereEqualScanEst(). */
1582 whereKeyStats(pParse
, p
, pRec
, 0, a
);
1584 iUpper
= a
[0] + a
[1];
1587 assert( pLower
==0 || (pLower
->eOperator
& (WO_GT
|WO_GE
))!=0 );
1588 assert( pUpper
==0 || (pUpper
->eOperator
& (WO_LT
|WO_LE
))!=0 );
1589 assert( p
->aSortOrder
!=0 );
1590 if( p
->aSortOrder
[nEq
] ){
1591 /* The roles of pLower and pUpper are swapped for a DESC index */
1592 SWAP(WhereTerm
*, pLower
, pUpper
);
1593 SWAP(int, nBtm
, nTop
);
1596 /* If possible, improve on the iLower estimate using ($P:$L). */
1598 int n
; /* Values extracted from pExpr */
1599 Expr
*pExpr
= pLower
->pExpr
->pRight
;
1600 rc
= sqlite3Stat4ProbeSetValue(pParse
, p
, &pRec
, pExpr
, nBtm
, nEq
, &n
);
1601 if( rc
==SQLITE_OK
&& n
){
1603 u16 mask
= WO_GT
|WO_LE
;
1604 if( sqlite3ExprVectorSize(pExpr
)>n
) mask
= (WO_LE
|WO_LT
);
1605 iLwrIdx
= whereKeyStats(pParse
, p
, pRec
, 0, a
);
1606 iNew
= a
[0] + ((pLower
->eOperator
& mask
) ? a
[1] : 0);
1607 if( iNew
>iLower
) iLower
= iNew
;
1613 /* If possible, improve on the iUpper estimate using ($P:$U). */
1615 int n
; /* Values extracted from pExpr */
1616 Expr
*pExpr
= pUpper
->pExpr
->pRight
;
1617 rc
= sqlite3Stat4ProbeSetValue(pParse
, p
, &pRec
, pExpr
, nTop
, nEq
, &n
);
1618 if( rc
==SQLITE_OK
&& n
){
1620 u16 mask
= WO_GT
|WO_LE
;
1621 if( sqlite3ExprVectorSize(pExpr
)>n
) mask
= (WO_LE
|WO_LT
);
1622 iUprIdx
= whereKeyStats(pParse
, p
, pRec
, 1, a
);
1623 iNew
= a
[0] + ((pUpper
->eOperator
& mask
) ? a
[1] : 0);
1624 if( iNew
<iUpper
) iUpper
= iNew
;
1630 pBuilder
->pRec
= pRec
;
1631 if( rc
==SQLITE_OK
){
1632 if( iUpper
>iLower
){
1633 nNew
= sqlite3LogEst(iUpper
- iLower
);
1634 /* TUNING: If both iUpper and iLower are derived from the same
1635 ** sample, then assume they are 4x more selective. This brings
1636 ** the estimated selectivity more in line with what it would be
1637 ** if estimated without the use of STAT4 tables. */
1638 if( iLwrIdx
==iUprIdx
) nNew
-= 20; assert( 20==sqlite3LogEst(4) );
1640 nNew
= 10; assert( 10==sqlite3LogEst(2) );
1645 WHERETRACE(0x10, ("STAT4 range scan: %u..%u est=%d\n",
1646 (u32
)iLower
, (u32
)iUpper
, nOut
));
1650 rc
= whereRangeSkipScanEst(pParse
, pLower
, pUpper
, pLoop
, &bDone
);
1651 if( bDone
) return rc
;
1655 UNUSED_PARAMETER(pParse
);
1656 UNUSED_PARAMETER(pBuilder
);
1657 assert( pLower
|| pUpper
);
1659 assert( pUpper
==0 || (pUpper
->wtFlags
& TERM_VNULL
)==0 );
1660 nNew
= whereRangeAdjust(pLower
, nOut
);
1661 nNew
= whereRangeAdjust(pUpper
, nNew
);
1663 /* TUNING: If there is both an upper and lower limit and neither limit
1664 ** has an application-defined likelihood(), assume the range is
1665 ** reduced by an additional 75%. This means that, by default, an open-ended
1666 ** range query (e.g. col > ?) is assumed to match 1/4 of the rows in the
1667 ** index. While a closed range (e.g. col BETWEEN ? AND ?) is estimated to
1668 ** match 1/64 of the index. */
1669 if( pLower
&& pLower
->truthProb
>0 && pUpper
&& pUpper
->truthProb
>0 ){
1673 nOut
-= (pLower
!=0) + (pUpper
!=0);
1674 if( nNew
<10 ) nNew
= 10;
1675 if( nNew
<nOut
) nOut
= nNew
;
1676 #if defined(WHERETRACE_ENABLED)
1677 if( pLoop
->nOut
>nOut
){
1678 WHERETRACE(0x10,("Range scan lowers nOut from %d to %d\n",
1679 pLoop
->nOut
, nOut
));
1682 pLoop
->nOut
= (LogEst
)nOut
;
1686 #ifdef SQLITE_ENABLE_STAT4
1688 ** Estimate the number of rows that will be returned based on
1689 ** an equality constraint x=VALUE and where that VALUE occurs in
1690 ** the histogram data. This only works when x is the left-most
1691 ** column of an index and sqlite_stat4 histogram data is available
1692 ** for that index. When pExpr==NULL that means the constraint is
1693 ** "x IS NULL" instead of "x=VALUE".
1695 ** Write the estimated row count into *pnRow and return SQLITE_OK.
1696 ** If unable to make an estimate, leave *pnRow unchanged and return
1699 ** This routine can fail if it is unable to load a collating sequence
1700 ** required for string comparison, or if unable to allocate memory
1701 ** for a UTF conversion required for comparison. The error is stored
1702 ** in the pParse structure.
1704 static int whereEqualScanEst(
1705 Parse
*pParse
, /* Parsing & code generating context */
1706 WhereLoopBuilder
*pBuilder
,
1707 Expr
*pExpr
, /* Expression for VALUE in the x=VALUE constraint */
1708 tRowcnt
*pnRow
/* Write the revised row estimate here */
1710 Index
*p
= pBuilder
->pNew
->u
.btree
.pIndex
;
1711 int nEq
= pBuilder
->pNew
->u
.btree
.nEq
;
1712 UnpackedRecord
*pRec
= pBuilder
->pRec
;
1713 int rc
; /* Subfunction return code */
1714 tRowcnt a
[2]; /* Statistics */
1718 assert( nEq
<=p
->nColumn
);
1719 assert( p
->aSample
!=0 );
1720 assert( p
->nSample
>0 );
1721 assert( pBuilder
->nRecValid
<nEq
);
1723 /* If values are not available for all fields of the index to the left
1724 ** of this one, no estimate can be made. Return SQLITE_NOTFOUND. */
1725 if( pBuilder
->nRecValid
<(nEq
-1) ){
1726 return SQLITE_NOTFOUND
;
1729 /* This is an optimization only. The call to sqlite3Stat4ProbeSetValue()
1730 ** below would return the same value. */
1731 if( nEq
>=p
->nColumn
){
1736 rc
= sqlite3Stat4ProbeSetValue(pParse
, p
, &pRec
, pExpr
, 1, nEq
-1, &bOk
);
1737 pBuilder
->pRec
= pRec
;
1738 if( rc
!=SQLITE_OK
) return rc
;
1739 if( bOk
==0 ) return SQLITE_NOTFOUND
;
1740 pBuilder
->nRecValid
= nEq
;
1742 whereKeyStats(pParse
, p
, pRec
, 0, a
);
1743 WHERETRACE(0x10,("equality scan regions %s(%d): %d\n",
1744 p
->zName
, nEq
-1, (int)a
[1]));
1749 #endif /* SQLITE_ENABLE_STAT4 */
1751 #ifdef SQLITE_ENABLE_STAT4
1753 ** Estimate the number of rows that will be returned based on
1754 ** an IN constraint where the right-hand side of the IN operator
1755 ** is a list of values. Example:
1757 ** WHERE x IN (1,2,3,4)
1759 ** Write the estimated row count into *pnRow and return SQLITE_OK.
1760 ** If unable to make an estimate, leave *pnRow unchanged and return
1763 ** This routine can fail if it is unable to load a collating sequence
1764 ** required for string comparison, or if unable to allocate memory
1765 ** for a UTF conversion required for comparison. The error is stored
1766 ** in the pParse structure.
1768 static int whereInScanEst(
1769 Parse
*pParse
, /* Parsing & code generating context */
1770 WhereLoopBuilder
*pBuilder
,
1771 ExprList
*pList
, /* The value list on the RHS of "x IN (v1,v2,v3,...)" */
1772 tRowcnt
*pnRow
/* Write the revised row estimate here */
1774 Index
*p
= pBuilder
->pNew
->u
.btree
.pIndex
;
1775 i64 nRow0
= sqlite3LogEstToInt(p
->aiRowLogEst
[0]);
1776 int nRecValid
= pBuilder
->nRecValid
;
1777 int rc
= SQLITE_OK
; /* Subfunction return code */
1778 tRowcnt nEst
; /* Number of rows for a single term */
1779 tRowcnt nRowEst
= 0; /* New estimate of the number of rows */
1780 int i
; /* Loop counter */
1782 assert( p
->aSample
!=0 );
1783 for(i
=0; rc
==SQLITE_OK
&& i
<pList
->nExpr
; i
++){
1785 rc
= whereEqualScanEst(pParse
, pBuilder
, pList
->a
[i
].pExpr
, &nEst
);
1787 pBuilder
->nRecValid
= nRecValid
;
1790 if( rc
==SQLITE_OK
){
1791 if( nRowEst
> nRow0
) nRowEst
= nRow0
;
1793 WHERETRACE(0x10,("IN row estimate: est=%d\n", nRowEst
));
1795 assert( pBuilder
->nRecValid
==nRecValid
);
1798 #endif /* SQLITE_ENABLE_STAT4 */
1801 #ifdef WHERETRACE_ENABLED
1803 ** Print the content of a WhereTerm object
1805 void sqlite3WhereTermPrint(WhereTerm
*pTerm
, int iTerm
){
1807 sqlite3DebugPrintf("TERM-%-3d NULL\n", iTerm
);
1811 memcpy(zType
, "....", 5);
1812 if( pTerm
->wtFlags
& TERM_VIRTUAL
) zType
[0] = 'V';
1813 if( pTerm
->eOperator
& WO_EQUIV
) zType
[1] = 'E';
1814 if( ExprHasProperty(pTerm
->pExpr
, EP_FromJoin
) ) zType
[2] = 'L';
1815 if( pTerm
->wtFlags
& TERM_CODED
) zType
[3] = 'C';
1816 if( pTerm
->eOperator
& WO_SINGLE
){
1817 assert( (pTerm
->eOperator
& (WO_OR
|WO_AND
))==0 );
1818 sqlite3_snprintf(sizeof(zLeft
),zLeft
,"left={%d:%d}",
1819 pTerm
->leftCursor
, pTerm
->u
.x
.leftColumn
);
1820 }else if( (pTerm
->eOperator
& WO_OR
)!=0 && pTerm
->u
.pOrInfo
!=0 ){
1821 sqlite3_snprintf(sizeof(zLeft
),zLeft
,"indexable=0x%llx",
1822 pTerm
->u
.pOrInfo
->indexable
);
1824 sqlite3_snprintf(sizeof(zLeft
),zLeft
,"left=%d", pTerm
->leftCursor
);
1827 "TERM-%-3d %p %s %-12s op=%03x wtFlags=%04x",
1828 iTerm
, pTerm
, zType
, zLeft
, pTerm
->eOperator
, pTerm
->wtFlags
);
1829 /* The 0x10000 .wheretrace flag causes extra information to be
1830 ** shown about each Term */
1831 if( sqlite3WhereTrace
& 0x10000 ){
1832 sqlite3DebugPrintf(" prob=%-3d prereq=%llx,%llx",
1833 pTerm
->truthProb
, (u64
)pTerm
->prereqAll
, (u64
)pTerm
->prereqRight
);
1835 if( (pTerm
->eOperator
& (WO_OR
|WO_AND
))==0 && pTerm
->u
.x
.iField
){
1836 sqlite3DebugPrintf(" iField=%d", pTerm
->u
.x
.iField
);
1838 if( pTerm
->iParent
>=0 ){
1839 sqlite3DebugPrintf(" iParent=%d", pTerm
->iParent
);
1841 sqlite3DebugPrintf("\n");
1842 sqlite3TreeViewExpr(0, pTerm
->pExpr
, 0);
1847 #ifdef WHERETRACE_ENABLED
1849 ** Show the complete content of a WhereClause
1851 void sqlite3WhereClausePrint(WhereClause
*pWC
){
1853 for(i
=0; i
<pWC
->nTerm
; i
++){
1854 sqlite3WhereTermPrint(&pWC
->a
[i
], i
);
1859 #ifdef WHERETRACE_ENABLED
1861 ** Print a WhereLoop object for debugging purposes
1863 void sqlite3WhereLoopPrint(WhereLoop
*p
, WhereClause
*pWC
){
1864 WhereInfo
*pWInfo
= pWC
->pWInfo
;
1865 int nb
= 1+(pWInfo
->pTabList
->nSrc
+3)/4;
1866 SrcItem
*pItem
= pWInfo
->pTabList
->a
+ p
->iTab
;
1867 Table
*pTab
= pItem
->pTab
;
1868 Bitmask mAll
= (((Bitmask
)1)<<(nb
*4)) - 1;
1869 sqlite3DebugPrintf("%c%2d.%0*llx.%0*llx", p
->cId
,
1870 p
->iTab
, nb
, p
->maskSelf
, nb
, p
->prereq
& mAll
);
1871 sqlite3DebugPrintf(" %12s",
1872 pItem
->zAlias
? pItem
->zAlias
: pTab
->zName
);
1873 if( (p
->wsFlags
& WHERE_VIRTUALTABLE
)==0 ){
1875 if( p
->u
.btree
.pIndex
&& (zName
= p
->u
.btree
.pIndex
->zName
)!=0 ){
1876 if( strncmp(zName
, "sqlite_autoindex_", 17)==0 ){
1877 int i
= sqlite3Strlen30(zName
) - 1;
1878 while( zName
[i
]!='_' ) i
--;
1881 sqlite3DebugPrintf(".%-16s %2d", zName
, p
->u
.btree
.nEq
);
1883 sqlite3DebugPrintf("%20s","");
1887 if( p
->u
.vtab
.idxStr
){
1888 z
= sqlite3_mprintf("(%d,\"%s\",%#x)",
1889 p
->u
.vtab
.idxNum
, p
->u
.vtab
.idxStr
, p
->u
.vtab
.omitMask
);
1891 z
= sqlite3_mprintf("(%d,%x)", p
->u
.vtab
.idxNum
, p
->u
.vtab
.omitMask
);
1893 sqlite3DebugPrintf(" %-19s", z
);
1896 if( p
->wsFlags
& WHERE_SKIPSCAN
){
1897 sqlite3DebugPrintf(" f %05x %d-%d", p
->wsFlags
, p
->nLTerm
,p
->nSkip
);
1899 sqlite3DebugPrintf(" f %05x N %d", p
->wsFlags
, p
->nLTerm
);
1901 sqlite3DebugPrintf(" cost %d,%d,%d\n", p
->rSetup
, p
->rRun
, p
->nOut
);
1902 if( p
->nLTerm
&& (sqlite3WhereTrace
& 0x100)!=0 ){
1904 for(i
=0; i
<p
->nLTerm
; i
++){
1905 sqlite3WhereTermPrint(p
->aLTerm
[i
], i
);
1912 ** Convert bulk memory into a valid WhereLoop that can be passed
1913 ** to whereLoopClear harmlessly.
1915 static void whereLoopInit(WhereLoop
*p
){
1916 p
->aLTerm
= p
->aLTermSpace
;
1918 p
->nLSlot
= ArraySize(p
->aLTermSpace
);
1923 ** Clear the WhereLoop.u union. Leave WhereLoop.pLTerm intact.
1925 static void whereLoopClearUnion(sqlite3
*db
, WhereLoop
*p
){
1926 if( p
->wsFlags
& (WHERE_VIRTUALTABLE
|WHERE_AUTO_INDEX
) ){
1927 if( (p
->wsFlags
& WHERE_VIRTUALTABLE
)!=0 && p
->u
.vtab
.needFree
){
1928 sqlite3_free(p
->u
.vtab
.idxStr
);
1929 p
->u
.vtab
.needFree
= 0;
1930 p
->u
.vtab
.idxStr
= 0;
1931 }else if( (p
->wsFlags
& WHERE_AUTO_INDEX
)!=0 && p
->u
.btree
.pIndex
!=0 ){
1932 sqlite3DbFree(db
, p
->u
.btree
.pIndex
->zColAff
);
1933 sqlite3DbFreeNN(db
, p
->u
.btree
.pIndex
);
1934 p
->u
.btree
.pIndex
= 0;
1940 ** Deallocate internal memory used by a WhereLoop object
1942 static void whereLoopClear(sqlite3
*db
, WhereLoop
*p
){
1943 if( p
->aLTerm
!=p
->aLTermSpace
) sqlite3DbFreeNN(db
, p
->aLTerm
);
1944 whereLoopClearUnion(db
, p
);
1949 ** Increase the memory allocation for pLoop->aLTerm[] to be at least n.
1951 static int whereLoopResize(sqlite3
*db
, WhereLoop
*p
, int n
){
1953 if( p
->nLSlot
>=n
) return SQLITE_OK
;
1955 paNew
= sqlite3DbMallocRawNN(db
, sizeof(p
->aLTerm
[0])*n
);
1956 if( paNew
==0 ) return SQLITE_NOMEM_BKPT
;
1957 memcpy(paNew
, p
->aLTerm
, sizeof(p
->aLTerm
[0])*p
->nLSlot
);
1958 if( p
->aLTerm
!=p
->aLTermSpace
) sqlite3DbFreeNN(db
, p
->aLTerm
);
1965 ** Transfer content from the second pLoop into the first.
1967 static int whereLoopXfer(sqlite3
*db
, WhereLoop
*pTo
, WhereLoop
*pFrom
){
1968 whereLoopClearUnion(db
, pTo
);
1969 if( whereLoopResize(db
, pTo
, pFrom
->nLTerm
) ){
1970 memset(pTo
, 0, WHERE_LOOP_XFER_SZ
);
1971 return SQLITE_NOMEM_BKPT
;
1973 memcpy(pTo
, pFrom
, WHERE_LOOP_XFER_SZ
);
1974 memcpy(pTo
->aLTerm
, pFrom
->aLTerm
, pTo
->nLTerm
*sizeof(pTo
->aLTerm
[0]));
1975 if( pFrom
->wsFlags
& WHERE_VIRTUALTABLE
){
1976 pFrom
->u
.vtab
.needFree
= 0;
1977 }else if( (pFrom
->wsFlags
& WHERE_AUTO_INDEX
)!=0 ){
1978 pFrom
->u
.btree
.pIndex
= 0;
1984 ** Delete a WhereLoop object
1986 static void whereLoopDelete(sqlite3
*db
, WhereLoop
*p
){
1987 whereLoopClear(db
, p
);
1988 sqlite3DbFreeNN(db
, p
);
1992 ** Free a WhereInfo structure
1994 static void whereInfoFree(sqlite3
*db
, WhereInfo
*pWInfo
){
1996 assert( pWInfo
!=0 );
1997 for(i
=0; i
<pWInfo
->nLevel
; i
++){
1998 WhereLevel
*pLevel
= &pWInfo
->a
[i
];
1999 if( pLevel
->pWLoop
&& (pLevel
->pWLoop
->wsFlags
& WHERE_IN_ABLE
)!=0 ){
2000 assert( (pLevel
->pWLoop
->wsFlags
& WHERE_MULTI_OR
)==0 );
2001 sqlite3DbFree(db
, pLevel
->u
.in
.aInLoop
);
2004 sqlite3WhereClauseClear(&pWInfo
->sWC
);
2005 while( pWInfo
->pLoops
){
2006 WhereLoop
*p
= pWInfo
->pLoops
;
2007 pWInfo
->pLoops
= p
->pNextLoop
;
2008 whereLoopDelete(db
, p
);
2010 assert( pWInfo
->pExprMods
==0 );
2011 sqlite3DbFreeNN(db
, pWInfo
);
2014 /* Undo all Expr node modifications
2016 static void whereUndoExprMods(WhereInfo
*pWInfo
){
2017 while( pWInfo
->pExprMods
){
2018 WhereExprMod
*p
= pWInfo
->pExprMods
;
2019 pWInfo
->pExprMods
= p
->pNext
;
2020 memcpy(p
->pExpr
, &p
->orig
, sizeof(p
->orig
));
2021 sqlite3DbFree(pWInfo
->pParse
->db
, p
);
2026 ** Return TRUE if all of the following are true:
2028 ** (1) X has the same or lower cost, or returns the same or fewer rows,
2030 ** (2) X uses fewer WHERE clause terms than Y
2031 ** (3) Every WHERE clause term used by X is also used by Y
2032 ** (4) X skips at least as many columns as Y
2033 ** (5) If X is a covering index, than Y is too
2035 ** Conditions (2) and (3) mean that X is a "proper subset" of Y.
2036 ** If X is a proper subset of Y then Y is a better choice and ought
2037 ** to have a lower cost. This routine returns TRUE when that cost
2038 ** relationship is inverted and needs to be adjusted. Constraint (4)
2039 ** was added because if X uses skip-scan less than Y it still might
2040 ** deserve a lower cost even if it is a proper subset of Y. Constraint (5)
2041 ** was added because a covering index probably deserves to have a lower cost
2042 ** than a non-covering index even if it is a proper subset.
2044 static int whereLoopCheaperProperSubset(
2045 const WhereLoop
*pX
, /* First WhereLoop to compare */
2046 const WhereLoop
*pY
/* Compare against this WhereLoop */
2049 if( pX
->nLTerm
-pX
->nSkip
>= pY
->nLTerm
-pY
->nSkip
){
2050 return 0; /* X is not a subset of Y */
2052 if( pX
->rRun
>pY
->rRun
&& pX
->nOut
>pY
->nOut
) return 0;
2053 if( pY
->nSkip
> pX
->nSkip
) return 0;
2054 for(i
=pX
->nLTerm
-1; i
>=0; i
--){
2055 if( pX
->aLTerm
[i
]==0 ) continue;
2056 for(j
=pY
->nLTerm
-1; j
>=0; j
--){
2057 if( pY
->aLTerm
[j
]==pX
->aLTerm
[i
] ) break;
2059 if( j
<0 ) return 0; /* X not a subset of Y since term X[i] not used by Y */
2061 if( (pX
->wsFlags
&WHERE_IDX_ONLY
)!=0
2062 && (pY
->wsFlags
&WHERE_IDX_ONLY
)==0 ){
2063 return 0; /* Constraint (5) */
2065 return 1; /* All conditions meet */
2069 ** Try to adjust the cost and number of output rows of WhereLoop pTemplate
2070 ** upwards or downwards so that:
2072 ** (1) pTemplate costs less than any other WhereLoops that are a proper
2073 ** subset of pTemplate
2075 ** (2) pTemplate costs more than any other WhereLoops for which pTemplate
2076 ** is a proper subset.
2078 ** To say "WhereLoop X is a proper subset of Y" means that X uses fewer
2079 ** WHERE clause terms than Y and that every WHERE clause term used by X is
2082 static void whereLoopAdjustCost(const WhereLoop
*p
, WhereLoop
*pTemplate
){
2083 if( (pTemplate
->wsFlags
& WHERE_INDEXED
)==0 ) return;
2084 for(; p
; p
=p
->pNextLoop
){
2085 if( p
->iTab
!=pTemplate
->iTab
) continue;
2086 if( (p
->wsFlags
& WHERE_INDEXED
)==0 ) continue;
2087 if( whereLoopCheaperProperSubset(p
, pTemplate
) ){
2088 /* Adjust pTemplate cost downward so that it is cheaper than its
2090 WHERETRACE(0x80,("subset cost adjustment %d,%d to %d,%d\n",
2091 pTemplate
->rRun
, pTemplate
->nOut
,
2092 MIN(p
->rRun
, pTemplate
->rRun
),
2093 MIN(p
->nOut
- 1, pTemplate
->nOut
)));
2094 pTemplate
->rRun
= MIN(p
->rRun
, pTemplate
->rRun
);
2095 pTemplate
->nOut
= MIN(p
->nOut
- 1, pTemplate
->nOut
);
2096 }else if( whereLoopCheaperProperSubset(pTemplate
, p
) ){
2097 /* Adjust pTemplate cost upward so that it is costlier than p since
2098 ** pTemplate is a proper subset of p */
2099 WHERETRACE(0x80,("subset cost adjustment %d,%d to %d,%d\n",
2100 pTemplate
->rRun
, pTemplate
->nOut
,
2101 MAX(p
->rRun
, pTemplate
->rRun
),
2102 MAX(p
->nOut
+ 1, pTemplate
->nOut
)));
2103 pTemplate
->rRun
= MAX(p
->rRun
, pTemplate
->rRun
);
2104 pTemplate
->nOut
= MAX(p
->nOut
+ 1, pTemplate
->nOut
);
2110 ** Search the list of WhereLoops in *ppPrev looking for one that can be
2111 ** replaced by pTemplate.
2113 ** Return NULL if pTemplate does not belong on the WhereLoop list.
2114 ** In other words if pTemplate ought to be dropped from further consideration.
2116 ** If pX is a WhereLoop that pTemplate can replace, then return the
2117 ** link that points to pX.
2119 ** If pTemplate cannot replace any existing element of the list but needs
2120 ** to be added to the list as a new entry, then return a pointer to the
2121 ** tail of the list.
2123 static WhereLoop
**whereLoopFindLesser(
2125 const WhereLoop
*pTemplate
2128 for(p
=(*ppPrev
); p
; ppPrev
=&p
->pNextLoop
, p
=*ppPrev
){
2129 if( p
->iTab
!=pTemplate
->iTab
|| p
->iSortIdx
!=pTemplate
->iSortIdx
){
2130 /* If either the iTab or iSortIdx values for two WhereLoop are different
2131 ** then those WhereLoops need to be considered separately. Neither is
2132 ** a candidate to replace the other. */
2135 /* In the current implementation, the rSetup value is either zero
2136 ** or the cost of building an automatic index (NlogN) and the NlogN
2137 ** is the same for compatible WhereLoops. */
2138 assert( p
->rSetup
==0 || pTemplate
->rSetup
==0
2139 || p
->rSetup
==pTemplate
->rSetup
);
2141 /* whereLoopAddBtree() always generates and inserts the automatic index
2142 ** case first. Hence compatible candidate WhereLoops never have a larger
2143 ** rSetup. Call this SETUP-INVARIANT */
2144 assert( p
->rSetup
>=pTemplate
->rSetup
);
2146 /* Any loop using an appliation-defined index (or PRIMARY KEY or
2147 ** UNIQUE constraint) with one or more == constraints is better
2148 ** than an automatic index. Unless it is a skip-scan. */
2149 if( (p
->wsFlags
& WHERE_AUTO_INDEX
)!=0
2150 && (pTemplate
->nSkip
)==0
2151 && (pTemplate
->wsFlags
& WHERE_INDEXED
)!=0
2152 && (pTemplate
->wsFlags
& WHERE_COLUMN_EQ
)!=0
2153 && (p
->prereq
& pTemplate
->prereq
)==pTemplate
->prereq
2158 /* If existing WhereLoop p is better than pTemplate, pTemplate can be
2159 ** discarded. WhereLoop p is better if:
2160 ** (1) p has no more dependencies than pTemplate, and
2161 ** (2) p has an equal or lower cost than pTemplate
2163 if( (p
->prereq
& pTemplate
->prereq
)==p
->prereq
/* (1) */
2164 && p
->rSetup
<=pTemplate
->rSetup
/* (2a) */
2165 && p
->rRun
<=pTemplate
->rRun
/* (2b) */
2166 && p
->nOut
<=pTemplate
->nOut
/* (2c) */
2168 return 0; /* Discard pTemplate */
2171 /* If pTemplate is always better than p, then cause p to be overwritten
2172 ** with pTemplate. pTemplate is better than p if:
2173 ** (1) pTemplate has no more dependences than p, and
2174 ** (2) pTemplate has an equal or lower cost than p.
2176 if( (p
->prereq
& pTemplate
->prereq
)==pTemplate
->prereq
/* (1) */
2177 && p
->rRun
>=pTemplate
->rRun
/* (2a) */
2178 && p
->nOut
>=pTemplate
->nOut
/* (2b) */
2180 assert( p
->rSetup
>=pTemplate
->rSetup
); /* SETUP-INVARIANT above */
2181 break; /* Cause p to be overwritten by pTemplate */
2188 ** Insert or replace a WhereLoop entry using the template supplied.
2190 ** An existing WhereLoop entry might be overwritten if the new template
2191 ** is better and has fewer dependencies. Or the template will be ignored
2192 ** and no insert will occur if an existing WhereLoop is faster and has
2193 ** fewer dependencies than the template. Otherwise a new WhereLoop is
2194 ** added based on the template.
2196 ** If pBuilder->pOrSet is not NULL then we care about only the
2197 ** prerequisites and rRun and nOut costs of the N best loops. That
2198 ** information is gathered in the pBuilder->pOrSet object. This special
2199 ** processing mode is used only for OR clause processing.
2201 ** When accumulating multiple loops (when pBuilder->pOrSet is NULL) we
2202 ** still might overwrite similar loops with the new template if the
2203 ** new template is better. Loops may be overwritten if the following
2204 ** conditions are met:
2206 ** (1) They have the same iTab.
2207 ** (2) They have the same iSortIdx.
2208 ** (3) The template has same or fewer dependencies than the current loop
2209 ** (4) The template has the same or lower cost than the current loop
2211 static int whereLoopInsert(WhereLoopBuilder
*pBuilder
, WhereLoop
*pTemplate
){
2212 WhereLoop
**ppPrev
, *p
;
2213 WhereInfo
*pWInfo
= pBuilder
->pWInfo
;
2214 sqlite3
*db
= pWInfo
->pParse
->db
;
2217 /* Stop the search once we hit the query planner search limit */
2218 if( pBuilder
->iPlanLimit
==0 ){
2219 WHERETRACE(0xffffffff,("=== query planner search limit reached ===\n"));
2220 if( pBuilder
->pOrSet
) pBuilder
->pOrSet
->n
= 0;
2223 pBuilder
->iPlanLimit
--;
2225 whereLoopAdjustCost(pWInfo
->pLoops
, pTemplate
);
2227 /* If pBuilder->pOrSet is defined, then only keep track of the costs
2230 if( pBuilder
->pOrSet
!=0 ){
2231 if( pTemplate
->nLTerm
){
2232 #if WHERETRACE_ENABLED
2233 u16 n
= pBuilder
->pOrSet
->n
;
2236 whereOrInsert(pBuilder
->pOrSet
, pTemplate
->prereq
, pTemplate
->rRun
,
2238 #if WHERETRACE_ENABLED /* 0x8 */
2239 if( sqlite3WhereTrace
& 0x8 ){
2240 sqlite3DebugPrintf(x
?" or-%d: ":" or-X: ", n
);
2241 sqlite3WhereLoopPrint(pTemplate
, pBuilder
->pWC
);
2248 /* Look for an existing WhereLoop to replace with pTemplate
2250 ppPrev
= whereLoopFindLesser(&pWInfo
->pLoops
, pTemplate
);
2253 /* There already exists a WhereLoop on the list that is better
2254 ** than pTemplate, so just ignore pTemplate */
2255 #if WHERETRACE_ENABLED /* 0x8 */
2256 if( sqlite3WhereTrace
& 0x8 ){
2257 sqlite3DebugPrintf(" skip: ");
2258 sqlite3WhereLoopPrint(pTemplate
, pBuilder
->pWC
);
2266 /* If we reach this point it means that either p[] should be overwritten
2267 ** with pTemplate[] if p[] exists, or if p==NULL then allocate a new
2268 ** WhereLoop and insert it.
2270 #if WHERETRACE_ENABLED /* 0x8 */
2271 if( sqlite3WhereTrace
& 0x8 ){
2273 sqlite3DebugPrintf("replace: ");
2274 sqlite3WhereLoopPrint(p
, pBuilder
->pWC
);
2275 sqlite3DebugPrintf(" with: ");
2277 sqlite3DebugPrintf(" add: ");
2279 sqlite3WhereLoopPrint(pTemplate
, pBuilder
->pWC
);
2283 /* Allocate a new WhereLoop to add to the end of the list */
2284 *ppPrev
= p
= sqlite3DbMallocRawNN(db
, sizeof(WhereLoop
));
2285 if( p
==0 ) return SQLITE_NOMEM_BKPT
;
2289 /* We will be overwriting WhereLoop p[]. But before we do, first
2290 ** go through the rest of the list and delete any other entries besides
2291 ** p[] that are also supplated by pTemplate */
2292 WhereLoop
**ppTail
= &p
->pNextLoop
;
2295 ppTail
= whereLoopFindLesser(ppTail
, pTemplate
);
2296 if( ppTail
==0 ) break;
2298 if( pToDel
==0 ) break;
2299 *ppTail
= pToDel
->pNextLoop
;
2300 #if WHERETRACE_ENABLED /* 0x8 */
2301 if( sqlite3WhereTrace
& 0x8 ){
2302 sqlite3DebugPrintf(" delete: ");
2303 sqlite3WhereLoopPrint(pToDel
, pBuilder
->pWC
);
2306 whereLoopDelete(db
, pToDel
);
2309 rc
= whereLoopXfer(db
, p
, pTemplate
);
2310 if( (p
->wsFlags
& WHERE_VIRTUALTABLE
)==0 ){
2311 Index
*pIndex
= p
->u
.btree
.pIndex
;
2312 if( pIndex
&& pIndex
->idxType
==SQLITE_IDXTYPE_IPK
){
2313 p
->u
.btree
.pIndex
= 0;
2320 ** Adjust the WhereLoop.nOut value downward to account for terms of the
2321 ** WHERE clause that reference the loop but which are not used by an
2324 ** For every WHERE clause term that is not used by the index
2325 ** and which has a truth probability assigned by one of the likelihood(),
2326 ** likely(), or unlikely() SQL functions, reduce the estimated number
2327 ** of output rows by the probability specified.
2329 ** TUNING: For every WHERE clause term that is not used by the index
2330 ** and which does not have an assigned truth probability, heuristics
2331 ** described below are used to try to estimate the truth probability.
2332 ** TODO --> Perhaps this is something that could be improved by better
2333 ** table statistics.
2335 ** Heuristic 1: Estimate the truth probability as 93.75%. The 93.75%
2336 ** value corresponds to -1 in LogEst notation, so this means decrement
2337 ** the WhereLoop.nOut field for every such WHERE clause term.
2339 ** Heuristic 2: If there exists one or more WHERE clause terms of the
2340 ** form "x==EXPR" and EXPR is not a constant 0 or 1, then make sure the
2341 ** final output row estimate is no greater than 1/4 of the total number
2342 ** of rows in the table. In other words, assume that x==EXPR will filter
2343 ** out at least 3 out of 4 rows. If EXPR is -1 or 0 or 1, then maybe the
2344 ** "x" column is boolean or else -1 or 0 or 1 is a common default value
2345 ** on the "x" column and so in that case only cap the output row estimate
2346 ** at 1/2 instead of 1/4.
2348 static void whereLoopOutputAdjust(
2349 WhereClause
*pWC
, /* The WHERE clause */
2350 WhereLoop
*pLoop
, /* The loop to adjust downward */
2351 LogEst nRow
/* Number of rows in the entire table */
2353 WhereTerm
*pTerm
, *pX
;
2354 Bitmask notAllowed
= ~(pLoop
->prereq
|pLoop
->maskSelf
);
2356 LogEst iReduce
= 0; /* pLoop->nOut should not exceed nRow-iReduce */
2358 assert( (pLoop
->wsFlags
& WHERE_AUTO_INDEX
)==0 );
2359 for(i
=pWC
->nTerm
, pTerm
=pWC
->a
; i
>0; i
--, pTerm
++){
2361 if( (pTerm
->wtFlags
& TERM_VIRTUAL
)!=0 ) break;
2362 if( (pTerm
->prereqAll
& pLoop
->maskSelf
)==0 ) continue;
2363 if( (pTerm
->prereqAll
& notAllowed
)!=0 ) continue;
2364 for(j
=pLoop
->nLTerm
-1; j
>=0; j
--){
2365 pX
= pLoop
->aLTerm
[j
];
2366 if( pX
==0 ) continue;
2367 if( pX
==pTerm
) break;
2368 if( pX
->iParent
>=0 && (&pWC
->a
[pX
->iParent
])==pTerm
) break;
2371 if( pTerm
->truthProb
<=0 ){
2372 /* If a truth probability is specified using the likelihood() hints,
2373 ** then use the probability provided by the application. */
2374 pLoop
->nOut
+= pTerm
->truthProb
;
2376 /* In the absence of explicit truth probabilities, use heuristics to
2377 ** guess a reasonable truth probability. */
2379 if( (pTerm
->eOperator
&(WO_EQ
|WO_IS
))!=0
2380 && (pTerm
->wtFlags
& TERM_HIGHTRUTH
)==0 /* tag-20200224-1 */
2382 Expr
*pRight
= pTerm
->pExpr
->pRight
;
2384 testcase( pTerm
->pExpr
->op
==TK_IS
);
2385 if( sqlite3ExprIsInteger(pRight
, &k
) && k
>=(-1) && k
<=1 ){
2391 pTerm
->wtFlags
|= TERM_HEURTRUTH
;
2398 if( pLoop
->nOut
> nRow
-iReduce
) pLoop
->nOut
= nRow
- iReduce
;
2402 ** Term pTerm is a vector range comparison operation. The first comparison
2403 ** in the vector can be optimized using column nEq of the index. This
2404 ** function returns the total number of vector elements that can be used
2405 ** as part of the range comparison.
2407 ** For example, if the query is:
2409 ** WHERE a = ? AND (b, c, d) > (?, ?, ?)
2413 ** CREATE INDEX ... ON (a, b, c, d, e)
2415 ** then this function would be invoked with nEq=1. The value returned in
2418 static int whereRangeVectorLen(
2419 Parse
*pParse
, /* Parsing context */
2420 int iCur
, /* Cursor open on pIdx */
2421 Index
*pIdx
, /* The index to be used for a inequality constraint */
2422 int nEq
, /* Number of prior equality constraints on same index */
2423 WhereTerm
*pTerm
/* The vector inequality constraint */
2425 int nCmp
= sqlite3ExprVectorSize(pTerm
->pExpr
->pLeft
);
2428 nCmp
= MIN(nCmp
, (pIdx
->nColumn
- nEq
));
2429 for(i
=1; i
<nCmp
; i
++){
2430 /* Test if comparison i of pTerm is compatible with column (i+nEq)
2431 ** of the index. If not, exit the loop. */
2432 char aff
; /* Comparison affinity */
2433 char idxaff
= 0; /* Indexed columns affinity */
2434 CollSeq
*pColl
; /* Comparison collation sequence */
2437 assert( ExprUseXList(pTerm
->pExpr
->pLeft
) );
2438 pLhs
= pTerm
->pExpr
->pLeft
->x
.pList
->a
[i
].pExpr
;
2439 pRhs
= pTerm
->pExpr
->pRight
;
2440 if( ExprUseXSelect(pRhs
) ){
2441 pRhs
= pRhs
->x
.pSelect
->pEList
->a
[i
].pExpr
;
2443 pRhs
= pRhs
->x
.pList
->a
[i
].pExpr
;
2446 /* Check that the LHS of the comparison is a column reference to
2447 ** the right column of the right source table. And that the sort
2448 ** order of the index column is the same as the sort order of the
2449 ** leftmost index column. */
2450 if( pLhs
->op
!=TK_COLUMN
2451 || pLhs
->iTable
!=iCur
2452 || pLhs
->iColumn
!=pIdx
->aiColumn
[i
+nEq
]
2453 || pIdx
->aSortOrder
[i
+nEq
]!=pIdx
->aSortOrder
[nEq
]
2458 testcase( pLhs
->iColumn
==XN_ROWID
);
2459 aff
= sqlite3CompareAffinity(pRhs
, sqlite3ExprAffinity(pLhs
));
2460 idxaff
= sqlite3TableColumnAffinity(pIdx
->pTable
, pLhs
->iColumn
);
2461 if( aff
!=idxaff
) break;
2463 pColl
= sqlite3BinaryCompareCollSeq(pParse
, pLhs
, pRhs
);
2464 if( pColl
==0 ) break;
2465 if( sqlite3StrICmp(pColl
->zName
, pIdx
->azColl
[i
+nEq
]) ) break;
2471 ** Adjust the cost C by the costMult facter T. This only occurs if
2472 ** compiled with -DSQLITE_ENABLE_COSTMULT
2474 #ifdef SQLITE_ENABLE_COSTMULT
2475 # define ApplyCostMultiplier(C,T) C += T
2477 # define ApplyCostMultiplier(C,T)
2481 ** We have so far matched pBuilder->pNew->u.btree.nEq terms of the
2482 ** index pIndex. Try to match one more.
2484 ** When this function is called, pBuilder->pNew->nOut contains the
2485 ** number of rows expected to be visited by filtering using the nEq
2486 ** terms only. If it is modified, this value is restored before this
2487 ** function returns.
2489 ** If pProbe->idxType==SQLITE_IDXTYPE_IPK, that means pIndex is
2490 ** a fake index used for the INTEGER PRIMARY KEY.
2492 static int whereLoopAddBtreeIndex(
2493 WhereLoopBuilder
*pBuilder
, /* The WhereLoop factory */
2494 SrcItem
*pSrc
, /* FROM clause term being analyzed */
2495 Index
*pProbe
, /* An index on pSrc */
2496 LogEst nInMul
/* log(Number of iterations due to IN) */
2498 WhereInfo
*pWInfo
= pBuilder
->pWInfo
; /* WHERE analyse context */
2499 Parse
*pParse
= pWInfo
->pParse
; /* Parsing context */
2500 sqlite3
*db
= pParse
->db
; /* Database connection malloc context */
2501 WhereLoop
*pNew
; /* Template WhereLoop under construction */
2502 WhereTerm
*pTerm
; /* A WhereTerm under consideration */
2503 int opMask
; /* Valid operators for constraints */
2504 WhereScan scan
; /* Iterator for WHERE terms */
2505 Bitmask saved_prereq
; /* Original value of pNew->prereq */
2506 u16 saved_nLTerm
; /* Original value of pNew->nLTerm */
2507 u16 saved_nEq
; /* Original value of pNew->u.btree.nEq */
2508 u16 saved_nBtm
; /* Original value of pNew->u.btree.nBtm */
2509 u16 saved_nTop
; /* Original value of pNew->u.btree.nTop */
2510 u16 saved_nSkip
; /* Original value of pNew->nSkip */
2511 u32 saved_wsFlags
; /* Original value of pNew->wsFlags */
2512 LogEst saved_nOut
; /* Original value of pNew->nOut */
2513 int rc
= SQLITE_OK
; /* Return code */
2514 LogEst rSize
; /* Number of rows in the table */
2515 LogEst rLogSize
; /* Logarithm of table size */
2516 WhereTerm
*pTop
= 0, *pBtm
= 0; /* Top and bottom range constraints */
2518 pNew
= pBuilder
->pNew
;
2519 if( db
->mallocFailed
) return SQLITE_NOMEM_BKPT
;
2520 WHERETRACE(0x800, ("BEGIN %s.addBtreeIdx(%s), nEq=%d, nSkip=%d, rRun=%d\n",
2521 pProbe
->pTable
->zName
,pProbe
->zName
,
2522 pNew
->u
.btree
.nEq
, pNew
->nSkip
, pNew
->rRun
));
2524 assert( (pNew
->wsFlags
& WHERE_VIRTUALTABLE
)==0 );
2525 assert( (pNew
->wsFlags
& WHERE_TOP_LIMIT
)==0 );
2526 if( pNew
->wsFlags
& WHERE_BTM_LIMIT
){
2527 opMask
= WO_LT
|WO_LE
;
2529 assert( pNew
->u
.btree
.nBtm
==0 );
2530 opMask
= WO_EQ
|WO_IN
|WO_GT
|WO_GE
|WO_LT
|WO_LE
|WO_ISNULL
|WO_IS
;
2532 if( pProbe
->bUnordered
) opMask
&= ~(WO_GT
|WO_GE
|WO_LT
|WO_LE
);
2534 assert( pNew
->u
.btree
.nEq
<pProbe
->nColumn
);
2535 assert( pNew
->u
.btree
.nEq
<pProbe
->nKeyCol
2536 || pProbe
->idxType
!=SQLITE_IDXTYPE_PRIMARYKEY
);
2538 saved_nEq
= pNew
->u
.btree
.nEq
;
2539 saved_nBtm
= pNew
->u
.btree
.nBtm
;
2540 saved_nTop
= pNew
->u
.btree
.nTop
;
2541 saved_nSkip
= pNew
->nSkip
;
2542 saved_nLTerm
= pNew
->nLTerm
;
2543 saved_wsFlags
= pNew
->wsFlags
;
2544 saved_prereq
= pNew
->prereq
;
2545 saved_nOut
= pNew
->nOut
;
2546 pTerm
= whereScanInit(&scan
, pBuilder
->pWC
, pSrc
->iCursor
, saved_nEq
,
2549 rSize
= pProbe
->aiRowLogEst
[0];
2550 rLogSize
= estLog(rSize
);
2551 for(; rc
==SQLITE_OK
&& pTerm
!=0; pTerm
= whereScanNext(&scan
)){
2552 u16 eOp
= pTerm
->eOperator
; /* Shorthand for pTerm->eOperator */
2554 LogEst nOutUnadjusted
; /* nOut before IN() and WHERE adjustments */
2556 #ifdef SQLITE_ENABLE_STAT4
2557 int nRecValid
= pBuilder
->nRecValid
;
2559 if( (eOp
==WO_ISNULL
|| (pTerm
->wtFlags
&TERM_VNULL
)!=0)
2560 && indexColumnNotNull(pProbe
, saved_nEq
)
2562 continue; /* ignore IS [NOT] NULL constraints on NOT NULL columns */
2564 if( pTerm
->prereqRight
& pNew
->maskSelf
) continue;
2566 /* Do not allow the upper bound of a LIKE optimization range constraint
2567 ** to mix with a lower range bound from some other source */
2568 if( pTerm
->wtFlags
& TERM_LIKEOPT
&& pTerm
->eOperator
==WO_LT
) continue;
2570 /* tag-20191211-001: Do not allow constraints from the WHERE clause to
2571 ** be used by the right table of a LEFT JOIN. Only constraints in the
2572 ** ON clause are allowed. See tag-20191211-002 for the vtab equivalent. */
2573 if( (pSrc
->fg
.jointype
& JT_LEFT
)!=0
2574 && !ExprHasProperty(pTerm
->pExpr
, EP_FromJoin
)
2579 if( IsUniqueIndex(pProbe
) && saved_nEq
==pProbe
->nKeyCol
-1 ){
2580 pBuilder
->bldFlags1
|= SQLITE_BLDF1_UNIQUE
;
2582 pBuilder
->bldFlags1
|= SQLITE_BLDF1_INDEXED
;
2584 pNew
->wsFlags
= saved_wsFlags
;
2585 pNew
->u
.btree
.nEq
= saved_nEq
;
2586 pNew
->u
.btree
.nBtm
= saved_nBtm
;
2587 pNew
->u
.btree
.nTop
= saved_nTop
;
2588 pNew
->nLTerm
= saved_nLTerm
;
2589 if( whereLoopResize(db
, pNew
, pNew
->nLTerm
+1) ) break; /* OOM */
2590 pNew
->aLTerm
[pNew
->nLTerm
++] = pTerm
;
2591 pNew
->prereq
= (saved_prereq
| pTerm
->prereqRight
) & ~pNew
->maskSelf
;
2594 || (pNew
->wsFlags
& WHERE_COLUMN_NULL
)!=0
2595 || (pNew
->wsFlags
& WHERE_COLUMN_IN
)!=0
2596 || (pNew
->wsFlags
& WHERE_SKIPSCAN
)!=0
2600 Expr
*pExpr
= pTerm
->pExpr
;
2601 if( ExprUseXSelect(pExpr
) ){
2602 /* "x IN (SELECT ...)": TUNING: the SELECT returns 25 rows */
2604 nIn
= 46; assert( 46==sqlite3LogEst(25) );
2606 /* The expression may actually be of the form (x, y) IN (SELECT...).
2607 ** In this case there is a separate term for each of (x) and (y).
2608 ** However, the nIn multiplier should only be applied once, not once
2609 ** for each such term. The following loop checks that pTerm is the
2610 ** first such term in use, and sets nIn back to 0 if it is not. */
2611 for(i
=0; i
<pNew
->nLTerm
-1; i
++){
2612 if( pNew
->aLTerm
[i
] && pNew
->aLTerm
[i
]->pExpr
==pExpr
) nIn
= 0;
2614 }else if( ALWAYS(pExpr
->x
.pList
&& pExpr
->x
.pList
->nExpr
) ){
2615 /* "x IN (value, value, ...)" */
2616 nIn
= sqlite3LogEst(pExpr
->x
.pList
->nExpr
);
2618 if( pProbe
->hasStat1
&& rLogSize
>=10 ){
2621 ** N = the total number of rows in the table
2622 ** K = the number of entries on the RHS of the IN operator
2623 ** M = the number of rows in the table that match terms to the
2624 ** to the left in the same index. If the IN operator is on
2625 ** the left-most index column, M==N.
2627 ** Given the definitions above, it is better to omit the IN operator
2628 ** from the index lookup and instead do a scan of the M elements,
2629 ** testing each scanned row against the IN operator separately, if:
2631 ** M*log(K) < K*log(N)
2633 ** Our estimates for M, K, and N might be inaccurate, so we build in
2634 ** a safety margin of 2 (LogEst: 10) that favors using the IN operator
2635 ** with the index, as using an index has better worst-case behavior.
2636 ** If we do not have real sqlite_stat1 data, always prefer to use
2637 ** the index. Do not bother with this optimization on very small
2638 ** tables (less than 2 rows) as it is pointless in that case.
2640 M
= pProbe
->aiRowLogEst
[saved_nEq
];
2642 /* TUNING v----- 10 to bias toward indexed IN */
2643 x
= M
+ logK
+ 10 - (nIn
+ rLogSize
);
2646 ("IN operator (N=%d M=%d logK=%d nIn=%d rLogSize=%d x=%d) "
2647 "prefers indexed lookup\n",
2648 saved_nEq
, M
, logK
, nIn
, rLogSize
, x
));
2649 }else if( nInMul
<2 && OptimizationEnabled(db
, SQLITE_SeekScan
) ){
2651 ("IN operator (N=%d M=%d logK=%d nIn=%d rLogSize=%d x=%d"
2652 " nInMul=%d) prefers skip-scan\n",
2653 saved_nEq
, M
, logK
, nIn
, rLogSize
, x
, nInMul
));
2654 pNew
->wsFlags
|= WHERE_IN_SEEKSCAN
;
2657 ("IN operator (N=%d M=%d logK=%d nIn=%d rLogSize=%d x=%d"
2658 " nInMul=%d) prefers normal scan\n",
2659 saved_nEq
, M
, logK
, nIn
, rLogSize
, x
, nInMul
));
2663 pNew
->wsFlags
|= WHERE_COLUMN_IN
;
2664 }else if( eOp
& (WO_EQ
|WO_IS
) ){
2665 int iCol
= pProbe
->aiColumn
[saved_nEq
];
2666 pNew
->wsFlags
|= WHERE_COLUMN_EQ
;
2667 assert( saved_nEq
==pNew
->u
.btree
.nEq
);
2669 || (iCol
>=0 && nInMul
==0 && saved_nEq
==pProbe
->nKeyCol
-1)
2671 if( iCol
==XN_ROWID
|| pProbe
->uniqNotNull
2672 || (pProbe
->nKeyCol
==1 && pProbe
->onError
&& eOp
==WO_EQ
)
2674 pNew
->wsFlags
|= WHERE_ONEROW
;
2676 pNew
->wsFlags
|= WHERE_UNQ_WANTED
;
2679 if( scan
.iEquiv
>1 ) pNew
->wsFlags
|= WHERE_TRANSCONS
;
2680 }else if( eOp
& WO_ISNULL
){
2681 pNew
->wsFlags
|= WHERE_COLUMN_NULL
;
2682 }else if( eOp
& (WO_GT
|WO_GE
) ){
2683 testcase( eOp
& WO_GT
);
2684 testcase( eOp
& WO_GE
);
2685 pNew
->wsFlags
|= WHERE_COLUMN_RANGE
|WHERE_BTM_LIMIT
;
2686 pNew
->u
.btree
.nBtm
= whereRangeVectorLen(
2687 pParse
, pSrc
->iCursor
, pProbe
, saved_nEq
, pTerm
2691 if( pTerm
->wtFlags
& TERM_LIKEOPT
){
2692 /* Range constraints that come from the LIKE optimization are
2693 ** always used in pairs. */
2695 assert( (pTop
-(pTerm
->pWC
->a
))<pTerm
->pWC
->nTerm
);
2696 assert( pTop
->wtFlags
& TERM_LIKEOPT
);
2697 assert( pTop
->eOperator
==WO_LT
);
2698 if( whereLoopResize(db
, pNew
, pNew
->nLTerm
+1) ) break; /* OOM */
2699 pNew
->aLTerm
[pNew
->nLTerm
++] = pTop
;
2700 pNew
->wsFlags
|= WHERE_TOP_LIMIT
;
2701 pNew
->u
.btree
.nTop
= 1;
2704 assert( eOp
& (WO_LT
|WO_LE
) );
2705 testcase( eOp
& WO_LT
);
2706 testcase( eOp
& WO_LE
);
2707 pNew
->wsFlags
|= WHERE_COLUMN_RANGE
|WHERE_TOP_LIMIT
;
2708 pNew
->u
.btree
.nTop
= whereRangeVectorLen(
2709 pParse
, pSrc
->iCursor
, pProbe
, saved_nEq
, pTerm
2712 pBtm
= (pNew
->wsFlags
& WHERE_BTM_LIMIT
)!=0 ?
2713 pNew
->aLTerm
[pNew
->nLTerm
-2] : 0;
2716 /* At this point pNew->nOut is set to the number of rows expected to
2717 ** be visited by the index scan before considering term pTerm, or the
2718 ** values of nIn and nInMul. In other words, assuming that all
2719 ** "x IN(...)" terms are replaced with "x = ?". This block updates
2720 ** the value of pNew->nOut to account for pTerm (but not nIn/nInMul). */
2721 assert( pNew
->nOut
==saved_nOut
);
2722 if( pNew
->wsFlags
& WHERE_COLUMN_RANGE
){
2723 /* Adjust nOut using stat4 data. Or, if there is no stat4
2724 ** data, using some other estimate. */
2725 whereRangeScanEst(pParse
, pBuilder
, pBtm
, pTop
, pNew
);
2727 int nEq
= ++pNew
->u
.btree
.nEq
;
2728 assert( eOp
& (WO_ISNULL
|WO_EQ
|WO_IN
|WO_IS
) );
2730 assert( pNew
->nOut
==saved_nOut
);
2731 if( pTerm
->truthProb
<=0 && pProbe
->aiColumn
[saved_nEq
]>=0 ){
2732 assert( (eOp
& WO_IN
) || nIn
==0 );
2733 testcase( eOp
& WO_IN
);
2734 pNew
->nOut
+= pTerm
->truthProb
;
2737 #ifdef SQLITE_ENABLE_STAT4
2741 && ALWAYS(pNew
->u
.btree
.nEq
<=pProbe
->nSampleCol
)
2742 && ((eOp
& WO_IN
)==0 || ExprUseXList(pTerm
->pExpr
))
2743 && OptimizationEnabled(db
, SQLITE_Stat4
)
2745 Expr
*pExpr
= pTerm
->pExpr
;
2746 if( (eOp
& (WO_EQ
|WO_ISNULL
|WO_IS
))!=0 ){
2747 testcase( eOp
& WO_EQ
);
2748 testcase( eOp
& WO_IS
);
2749 testcase( eOp
& WO_ISNULL
);
2750 rc
= whereEqualScanEst(pParse
, pBuilder
, pExpr
->pRight
, &nOut
);
2752 rc
= whereInScanEst(pParse
, pBuilder
, pExpr
->x
.pList
, &nOut
);
2754 if( rc
==SQLITE_NOTFOUND
) rc
= SQLITE_OK
;
2755 if( rc
!=SQLITE_OK
) break; /* Jump out of the pTerm loop */
2757 pNew
->nOut
= sqlite3LogEst(nOut
);
2759 /* TUNING: Mark terms as "low selectivity" if they seem likely
2760 ** to be true for half or more of the rows in the table.
2761 ** See tag-202002240-1 */
2762 && pNew
->nOut
+10 > pProbe
->aiRowLogEst
[0]
2764 #if WHERETRACE_ENABLED /* 0x01 */
2765 if( sqlite3WhereTrace
& 0x01 ){
2767 "STAT4 determines term has low selectivity:\n");
2768 sqlite3WhereTermPrint(pTerm
, 999);
2771 pTerm
->wtFlags
|= TERM_HIGHTRUTH
;
2772 if( pTerm
->wtFlags
& TERM_HEURTRUTH
){
2773 /* If the term has previously been used with an assumption of
2774 ** higher selectivity, then set the flag to rerun the
2775 ** loop computations. */
2776 pBuilder
->bldFlags2
|= SQLITE_BLDF2_2NDPASS
;
2779 if( pNew
->nOut
>saved_nOut
) pNew
->nOut
= saved_nOut
;
2786 pNew
->nOut
+= (pProbe
->aiRowLogEst
[nEq
] - pProbe
->aiRowLogEst
[nEq
-1]);
2787 if( eOp
& WO_ISNULL
){
2788 /* TUNING: If there is no likelihood() value, assume that a
2789 ** "col IS NULL" expression matches twice as many rows
2797 /* Set rCostIdx to the cost of visiting selected rows in index. Add
2798 ** it to pNew->rRun, which is currently set to the cost of the index
2799 ** seek only. Then, if this is a non-covering index, add the cost of
2800 ** visiting the rows in the main table. */
2801 assert( pSrc
->pTab
->szTabRow
>0 );
2802 rCostIdx
= pNew
->nOut
+ 1 + (15*pProbe
->szIdxRow
)/pSrc
->pTab
->szTabRow
;
2803 pNew
->rRun
= sqlite3LogEstAdd(rLogSize
, rCostIdx
);
2804 if( (pNew
->wsFlags
& (WHERE_IDX_ONLY
|WHERE_IPK
))==0 ){
2805 pNew
->rRun
= sqlite3LogEstAdd(pNew
->rRun
, pNew
->nOut
+ 16);
2807 ApplyCostMultiplier(pNew
->rRun
, pProbe
->pTable
->costMult
);
2809 nOutUnadjusted
= pNew
->nOut
;
2810 pNew
->rRun
+= nInMul
+ nIn
;
2811 pNew
->nOut
+= nInMul
+ nIn
;
2812 whereLoopOutputAdjust(pBuilder
->pWC
, pNew
, rSize
);
2813 rc
= whereLoopInsert(pBuilder
, pNew
);
2815 if( pNew
->wsFlags
& WHERE_COLUMN_RANGE
){
2816 pNew
->nOut
= saved_nOut
;
2818 pNew
->nOut
= nOutUnadjusted
;
2821 if( (pNew
->wsFlags
& WHERE_TOP_LIMIT
)==0
2822 && pNew
->u
.btree
.nEq
<pProbe
->nColumn
2823 && (pNew
->u
.btree
.nEq
<pProbe
->nKeyCol
||
2824 pProbe
->idxType
!=SQLITE_IDXTYPE_PRIMARYKEY
)
2826 whereLoopAddBtreeIndex(pBuilder
, pSrc
, pProbe
, nInMul
+nIn
);
2828 pNew
->nOut
= saved_nOut
;
2829 #ifdef SQLITE_ENABLE_STAT4
2830 pBuilder
->nRecValid
= nRecValid
;
2833 pNew
->prereq
= saved_prereq
;
2834 pNew
->u
.btree
.nEq
= saved_nEq
;
2835 pNew
->u
.btree
.nBtm
= saved_nBtm
;
2836 pNew
->u
.btree
.nTop
= saved_nTop
;
2837 pNew
->nSkip
= saved_nSkip
;
2838 pNew
->wsFlags
= saved_wsFlags
;
2839 pNew
->nOut
= saved_nOut
;
2840 pNew
->nLTerm
= saved_nLTerm
;
2842 /* Consider using a skip-scan if there are no WHERE clause constraints
2843 ** available for the left-most terms of the index, and if the average
2844 ** number of repeats in the left-most terms is at least 18.
2846 ** The magic number 18 is selected on the basis that scanning 17 rows
2847 ** is almost always quicker than an index seek (even though if the index
2848 ** contains fewer than 2^17 rows we assume otherwise in other parts of
2849 ** the code). And, even if it is not, it should not be too much slower.
2850 ** On the other hand, the extra seeks could end up being significantly
2851 ** more expensive. */
2852 assert( 42==sqlite3LogEst(18) );
2853 if( saved_nEq
==saved_nSkip
2854 && saved_nEq
+1<pProbe
->nKeyCol
2855 && saved_nEq
==pNew
->nLTerm
2856 && pProbe
->noSkipScan
==0
2857 && pProbe
->hasStat1
!=0
2858 && OptimizationEnabled(db
, SQLITE_SkipScan
)
2859 && pProbe
->aiRowLogEst
[saved_nEq
+1]>=42 /* TUNING: Minimum for skip-scan */
2860 && (rc
= whereLoopResize(db
, pNew
, pNew
->nLTerm
+1))==SQLITE_OK
2863 pNew
->u
.btree
.nEq
++;
2865 pNew
->aLTerm
[pNew
->nLTerm
++] = 0;
2866 pNew
->wsFlags
|= WHERE_SKIPSCAN
;
2867 nIter
= pProbe
->aiRowLogEst
[saved_nEq
] - pProbe
->aiRowLogEst
[saved_nEq
+1];
2868 pNew
->nOut
-= nIter
;
2869 /* TUNING: Because uncertainties in the estimates for skip-scan queries,
2870 ** add a 1.375 fudge factor to make skip-scan slightly less likely. */
2872 whereLoopAddBtreeIndex(pBuilder
, pSrc
, pProbe
, nIter
+ nInMul
);
2873 pNew
->nOut
= saved_nOut
;
2874 pNew
->u
.btree
.nEq
= saved_nEq
;
2875 pNew
->nSkip
= saved_nSkip
;
2876 pNew
->wsFlags
= saved_wsFlags
;
2879 WHERETRACE(0x800, ("END %s.addBtreeIdx(%s), nEq=%d, rc=%d\n",
2880 pProbe
->pTable
->zName
, pProbe
->zName
, saved_nEq
, rc
));
2885 ** Return True if it is possible that pIndex might be useful in
2886 ** implementing the ORDER BY clause in pBuilder.
2888 ** Return False if pBuilder does not contain an ORDER BY clause or
2889 ** if there is no way for pIndex to be useful in implementing that
2892 static int indexMightHelpWithOrderBy(
2893 WhereLoopBuilder
*pBuilder
,
2901 if( pIndex
->bUnordered
) return 0;
2902 if( (pOB
= pBuilder
->pWInfo
->pOrderBy
)==0 ) return 0;
2903 for(ii
=0; ii
<pOB
->nExpr
; ii
++){
2904 Expr
*pExpr
= sqlite3ExprSkipCollateAndLikely(pOB
->a
[ii
].pExpr
);
2905 if( NEVER(pExpr
==0) ) continue;
2906 if( pExpr
->op
==TK_COLUMN
&& pExpr
->iTable
==iCursor
){
2907 if( pExpr
->iColumn
<0 ) return 1;
2908 for(jj
=0; jj
<pIndex
->nKeyCol
; jj
++){
2909 if( pExpr
->iColumn
==pIndex
->aiColumn
[jj
] ) return 1;
2911 }else if( (aColExpr
= pIndex
->aColExpr
)!=0 ){
2912 for(jj
=0; jj
<pIndex
->nKeyCol
; jj
++){
2913 if( pIndex
->aiColumn
[jj
]!=XN_EXPR
) continue;
2914 if( sqlite3ExprCompareSkip(pExpr
,aColExpr
->a
[jj
].pExpr
,iCursor
)==0 ){
2923 /* Check to see if a partial index with pPartIndexWhere can be used
2924 ** in the current query. Return true if it can be and false if not.
2926 static int whereUsablePartialIndex(
2927 int iTab
, /* The table for which we want an index */
2928 int isLeft
, /* True if iTab is the right table of a LEFT JOIN */
2929 WhereClause
*pWC
, /* The WHERE clause of the query */
2930 Expr
*pWhere
/* The WHERE clause from the partial index */
2934 Parse
*pParse
= pWC
->pWInfo
->pParse
;
2935 while( pWhere
->op
==TK_AND
){
2936 if( !whereUsablePartialIndex(iTab
,isLeft
,pWC
,pWhere
->pLeft
) ) return 0;
2937 pWhere
= pWhere
->pRight
;
2939 if( pParse
->db
->flags
& SQLITE_EnableQPSG
) pParse
= 0;
2940 for(i
=0, pTerm
=pWC
->a
; i
<pWC
->nTerm
; i
++, pTerm
++){
2942 pExpr
= pTerm
->pExpr
;
2943 if( (!ExprHasProperty(pExpr
, EP_FromJoin
) || pExpr
->iRightJoinTable
==iTab
)
2944 && (isLeft
==0 || ExprHasProperty(pExpr
, EP_FromJoin
))
2945 && sqlite3ExprImpliesExpr(pParse
, pExpr
, pWhere
, iTab
)
2946 && (pTerm
->wtFlags
& TERM_VNULL
)==0
2955 ** Add all WhereLoop objects for a single table of the join where the table
2956 ** is identified by pBuilder->pNew->iTab. That table is guaranteed to be
2957 ** a b-tree table, not a virtual table.
2959 ** The costs (WhereLoop.rRun) of the b-tree loops added by this function
2960 ** are calculated as follows:
2962 ** For a full scan, assuming the table (or index) contains nRow rows:
2964 ** cost = nRow * 3.0 // full-table scan
2965 ** cost = nRow * K // scan of covering index
2966 ** cost = nRow * (K+3.0) // scan of non-covering index
2968 ** where K is a value between 1.1 and 3.0 set based on the relative
2969 ** estimated average size of the index and table records.
2971 ** For an index scan, where nVisit is the number of index rows visited
2972 ** by the scan, and nSeek is the number of seek operations required on
2973 ** the index b-tree:
2975 ** cost = nSeek * (log(nRow) + K * nVisit) // covering index
2976 ** cost = nSeek * (log(nRow) + (K+3.0) * nVisit) // non-covering index
2978 ** Normally, nSeek is 1. nSeek values greater than 1 come about if the
2979 ** WHERE clause includes "x IN (....)" terms used in place of "x=?". Or when
2980 ** implicit "x IN (SELECT x FROM tbl)" terms are added for skip-scans.
2982 ** The estimated values (nRow, nVisit, nSeek) often contain a large amount
2983 ** of uncertainty. For this reason, scoring is designed to pick plans that
2984 ** "do the least harm" if the estimates are inaccurate. For example, a
2985 ** log(nRow) factor is omitted from a non-covering index scan in order to
2986 ** bias the scoring in favor of using an index, since the worst-case
2987 ** performance of using an index is far better than the worst-case performance
2988 ** of a full table scan.
2990 static int whereLoopAddBtree(
2991 WhereLoopBuilder
*pBuilder
, /* WHERE clause information */
2992 Bitmask mPrereq
/* Extra prerequesites for using this table */
2994 WhereInfo
*pWInfo
; /* WHERE analysis context */
2995 Index
*pProbe
; /* An index we are evaluating */
2996 Index sPk
; /* A fake index object for the primary key */
2997 LogEst aiRowEstPk
[2]; /* The aiRowLogEst[] value for the sPk index */
2998 i16 aiColumnPk
= -1; /* The aColumn[] value for the sPk index */
2999 SrcList
*pTabList
; /* The FROM clause */
3000 SrcItem
*pSrc
; /* The FROM clause btree term to add */
3001 WhereLoop
*pNew
; /* Template WhereLoop object */
3002 int rc
= SQLITE_OK
; /* Return code */
3003 int iSortIdx
= 1; /* Index number */
3004 int b
; /* A boolean value */
3005 LogEst rSize
; /* number of rows in the table */
3006 WhereClause
*pWC
; /* The parsed WHERE clause */
3007 Table
*pTab
; /* Table being queried */
3009 pNew
= pBuilder
->pNew
;
3010 pWInfo
= pBuilder
->pWInfo
;
3011 pTabList
= pWInfo
->pTabList
;
3012 pSrc
= pTabList
->a
+ pNew
->iTab
;
3014 pWC
= pBuilder
->pWC
;
3015 assert( !IsVirtual(pSrc
->pTab
) );
3017 if( pSrc
->fg
.isIndexedBy
){
3018 assert( pSrc
->fg
.isCte
==0 );
3019 /* An INDEXED BY clause specifies a particular index to use */
3020 pProbe
= pSrc
->u2
.pIBIndex
;
3021 }else if( !HasRowid(pTab
) ){
3022 pProbe
= pTab
->pIndex
;
3024 /* There is no INDEXED BY clause. Create a fake Index object in local
3025 ** variable sPk to represent the rowid primary key index. Make this
3026 ** fake index the first in a chain of Index objects with all of the real
3027 ** indices to follow */
3028 Index
*pFirst
; /* First of real indices on the table */
3029 memset(&sPk
, 0, sizeof(Index
));
3032 sPk
.aiColumn
= &aiColumnPk
;
3033 sPk
.aiRowLogEst
= aiRowEstPk
;
3034 sPk
.onError
= OE_Replace
;
3036 sPk
.szIdxRow
= pTab
->szTabRow
;
3037 sPk
.idxType
= SQLITE_IDXTYPE_IPK
;
3038 aiRowEstPk
[0] = pTab
->nRowLogEst
;
3040 pFirst
= pSrc
->pTab
->pIndex
;
3041 if( pSrc
->fg
.notIndexed
==0 ){
3042 /* The real indices of the table are only considered if the
3043 ** NOT INDEXED qualifier is omitted from the FROM clause */
3048 rSize
= pTab
->nRowLogEst
;
3050 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
3051 /* Automatic indexes */
3052 if( !pBuilder
->pOrSet
/* Not part of an OR optimization */
3053 && (pWInfo
->wctrlFlags
& WHERE_OR_SUBCLAUSE
)==0
3054 && (pWInfo
->pParse
->db
->flags
& SQLITE_AutoIndex
)!=0
3055 && !pSrc
->fg
.isIndexedBy
/* Has no INDEXED BY clause */
3056 && !pSrc
->fg
.notIndexed
/* Has no NOT INDEXED clause */
3057 && HasRowid(pTab
) /* Not WITHOUT ROWID table. (FIXME: Why not?) */
3058 && !pSrc
->fg
.isCorrelated
/* Not a correlated subquery */
3059 && !pSrc
->fg
.isRecursive
/* Not a recursive common table expression. */
3061 /* Generate auto-index WhereLoops */
3062 LogEst rLogSize
; /* Logarithm of the number of rows in the table */
3064 WhereTerm
*pWCEnd
= pWC
->a
+ pWC
->nTerm
;
3065 rLogSize
= estLog(rSize
);
3066 for(pTerm
=pWC
->a
; rc
==SQLITE_OK
&& pTerm
<pWCEnd
; pTerm
++){
3067 if( pTerm
->prereqRight
& pNew
->maskSelf
) continue;
3068 if( termCanDriveIndex(pTerm
, pSrc
, 0) ){
3069 pNew
->u
.btree
.nEq
= 1;
3071 pNew
->u
.btree
.pIndex
= 0;
3073 pNew
->aLTerm
[0] = pTerm
;
3074 /* TUNING: One-time cost for computing the automatic index is
3075 ** estimated to be X*N*log2(N) where N is the number of rows in
3076 ** the table being indexed and where X is 7 (LogEst=28) for normal
3077 ** tables or 0.5 (LogEst=-10) for views and subqueries. The value
3078 ** of X is smaller for views and subqueries so that the query planner
3079 ** will be more aggressive about generating automatic indexes for
3080 ** those objects, since there is no opportunity to add schema
3081 ** indexes on subqueries and views. */
3082 pNew
->rSetup
= rLogSize
+ rSize
;
3083 if( !IsView(pTab
) && (pTab
->tabFlags
& TF_Ephemeral
)==0 ){
3088 ApplyCostMultiplier(pNew
->rSetup
, pTab
->costMult
);
3089 if( pNew
->rSetup
<0 ) pNew
->rSetup
= 0;
3090 /* TUNING: Each index lookup yields 20 rows in the table. This
3091 ** is more than the usual guess of 10 rows, since we have no way
3092 ** of knowing how selective the index will ultimately be. It would
3093 ** not be unreasonable to make this value much larger. */
3094 pNew
->nOut
= 43; assert( 43==sqlite3LogEst(20) );
3095 pNew
->rRun
= sqlite3LogEstAdd(rLogSize
,pNew
->nOut
);
3096 pNew
->wsFlags
= WHERE_AUTO_INDEX
;
3097 pNew
->prereq
= mPrereq
| pTerm
->prereqRight
;
3098 rc
= whereLoopInsert(pBuilder
, pNew
);
3102 #endif /* SQLITE_OMIT_AUTOMATIC_INDEX */
3104 /* Loop over all indices. If there was an INDEXED BY clause, then only
3105 ** consider index pProbe. */
3106 for(; rc
==SQLITE_OK
&& pProbe
;
3107 pProbe
=(pSrc
->fg
.isIndexedBy
? 0 : pProbe
->pNext
), iSortIdx
++
3109 int isLeft
= (pSrc
->fg
.jointype
& JT_OUTER
)!=0;
3110 if( pProbe
->pPartIdxWhere
!=0
3111 && !whereUsablePartialIndex(pSrc
->iCursor
, isLeft
, pWC
,
3112 pProbe
->pPartIdxWhere
)
3114 testcase( pNew
->iTab
!=pSrc
->iCursor
); /* See ticket [98d973b8f5] */
3115 continue; /* Partial index inappropriate for this query */
3117 if( pProbe
->bNoQuery
) continue;
3118 rSize
= pProbe
->aiRowLogEst
[0];
3119 pNew
->u
.btree
.nEq
= 0;
3120 pNew
->u
.btree
.nBtm
= 0;
3121 pNew
->u
.btree
.nTop
= 0;
3126 pNew
->prereq
= mPrereq
;
3128 pNew
->u
.btree
.pIndex
= pProbe
;
3129 b
= indexMightHelpWithOrderBy(pBuilder
, pProbe
, pSrc
->iCursor
);
3131 /* The ONEPASS_DESIRED flags never occurs together with ORDER BY */
3132 assert( (pWInfo
->wctrlFlags
& WHERE_ONEPASS_DESIRED
)==0 || b
==0 );
3133 if( pProbe
->idxType
==SQLITE_IDXTYPE_IPK
){
3134 /* Integer primary key index */
3135 pNew
->wsFlags
= WHERE_IPK
;
3137 /* Full table scan */
3138 pNew
->iSortIdx
= b
? iSortIdx
: 0;
3139 /* TUNING: Cost of full table scan is 3.0*N. The 3.0 factor is an
3140 ** extra cost designed to discourage the use of full table scans,
3141 ** since index lookups have better worst-case performance if our
3142 ** stat guesses are wrong. Reduce the 3.0 penalty slightly
3143 ** (to 2.75) if we have valid STAT4 information for the table.
3144 ** At 2.75, a full table scan is preferred over using an index on
3145 ** a column with just two distinct values where each value has about
3146 ** an equal number of appearances. Without STAT4 data, we still want
3147 ** to use an index in that case, since the constraint might be for
3148 ** the scarcer of the two values, and in that case an index lookup is
3151 #ifdef SQLITE_ENABLE_STAT4
3152 pNew
->rRun
= rSize
+ 16 - 2*((pTab
->tabFlags
& TF_HasStat4
)!=0);
3154 pNew
->rRun
= rSize
+ 16;
3156 ApplyCostMultiplier(pNew
->rRun
, pTab
->costMult
);
3157 whereLoopOutputAdjust(pWC
, pNew
, rSize
);
3158 rc
= whereLoopInsert(pBuilder
, pNew
);
3163 if( pProbe
->isCovering
){
3164 pNew
->wsFlags
= WHERE_IDX_ONLY
| WHERE_INDEXED
;
3167 m
= pSrc
->colUsed
& pProbe
->colNotIdxed
;
3168 pNew
->wsFlags
= (m
==0) ? (WHERE_IDX_ONLY
|WHERE_INDEXED
) : WHERE_INDEXED
;
3171 /* Full scan via index */
3174 || pProbe
->pPartIdxWhere
!=0
3175 || pSrc
->fg
.isIndexedBy
3177 && pProbe
->bUnordered
==0
3178 && (pProbe
->szIdxRow
<pTab
->szTabRow
)
3179 && (pWInfo
->wctrlFlags
& WHERE_ONEPASS_DESIRED
)==0
3180 && sqlite3GlobalConfig
.bUseCis
3181 && OptimizationEnabled(pWInfo
->pParse
->db
, SQLITE_CoverIdxScan
)
3184 pNew
->iSortIdx
= b
? iSortIdx
: 0;
3186 /* The cost of visiting the index rows is N*K, where K is
3187 ** between 1.1 and 3.0, depending on the relative sizes of the
3188 ** index and table rows. */
3189 pNew
->rRun
= rSize
+ 1 + (15*pProbe
->szIdxRow
)/pTab
->szTabRow
;
3191 /* If this is a non-covering index scan, add in the cost of
3192 ** doing table lookups. The cost will be 3x the number of
3193 ** lookups. Take into account WHERE clause terms that can be
3194 ** satisfied using just the index, and that do not require a
3196 LogEst nLookup
= rSize
+ 16; /* Base cost: N*3 */
3198 int iCur
= pSrc
->iCursor
;
3199 WhereClause
*pWC2
= &pWInfo
->sWC
;
3200 for(ii
=0; ii
<pWC2
->nTerm
; ii
++){
3201 WhereTerm
*pTerm
= &pWC2
->a
[ii
];
3202 if( !sqlite3ExprCoveredByIndex(pTerm
->pExpr
, iCur
, pProbe
) ){
3205 /* pTerm can be evaluated using just the index. So reduce
3206 ** the expected number of table lookups accordingly */
3207 if( pTerm
->truthProb
<=0 ){
3208 nLookup
+= pTerm
->truthProb
;
3211 if( pTerm
->eOperator
& (WO_EQ
|WO_IS
) ) nLookup
-= 19;
3215 pNew
->rRun
= sqlite3LogEstAdd(pNew
->rRun
, nLookup
);
3217 ApplyCostMultiplier(pNew
->rRun
, pTab
->costMult
);
3218 whereLoopOutputAdjust(pWC
, pNew
, rSize
);
3219 rc
= whereLoopInsert(pBuilder
, pNew
);
3225 pBuilder
->bldFlags1
= 0;
3226 rc
= whereLoopAddBtreeIndex(pBuilder
, pSrc
, pProbe
, 0);
3227 if( pBuilder
->bldFlags1
==SQLITE_BLDF1_INDEXED
){
3228 /* If a non-unique index is used, or if a prefix of the key for
3229 ** unique index is used (making the index functionally non-unique)
3230 ** then the sqlite_stat1 data becomes important for scoring the
3232 pTab
->tabFlags
|= TF_StatsUsed
;
3234 #ifdef SQLITE_ENABLE_STAT4
3235 sqlite3Stat4ProbeFree(pBuilder
->pRec
);
3236 pBuilder
->nRecValid
= 0;
3243 #ifndef SQLITE_OMIT_VIRTUALTABLE
3246 ** Argument pIdxInfo is already populated with all constraints that may
3247 ** be used by the virtual table identified by pBuilder->pNew->iTab. This
3248 ** function marks a subset of those constraints usable, invokes the
3249 ** xBestIndex method and adds the returned plan to pBuilder.
3251 ** A constraint is marked usable if:
3253 ** * Argument mUsable indicates that its prerequisites are available, and
3255 ** * It is not one of the operators specified in the mExclude mask passed
3256 ** as the fourth argument (which in practice is either WO_IN or 0).
3258 ** Argument mPrereq is a mask of tables that must be scanned before the
3259 ** virtual table in question. These are added to the plans prerequisites
3260 ** before it is added to pBuilder.
3262 ** Output parameter *pbIn is set to true if the plan added to pBuilder
3263 ** uses one or more WO_IN terms, or false otherwise.
3265 static int whereLoopAddVirtualOne(
3266 WhereLoopBuilder
*pBuilder
,
3267 Bitmask mPrereq
, /* Mask of tables that must be used. */
3268 Bitmask mUsable
, /* Mask of usable tables */
3269 u16 mExclude
, /* Exclude terms using these operators */
3270 sqlite3_index_info
*pIdxInfo
, /* Populated object for xBestIndex */
3271 u16 mNoOmit
, /* Do not omit these constraints */
3272 int *pbIn
/* OUT: True if plan uses an IN(...) op */
3274 WhereClause
*pWC
= pBuilder
->pWC
;
3275 struct sqlite3_index_constraint
*pIdxCons
;
3276 struct sqlite3_index_constraint_usage
*pUsage
= pIdxInfo
->aConstraintUsage
;
3280 WhereLoop
*pNew
= pBuilder
->pNew
;
3281 Parse
*pParse
= pBuilder
->pWInfo
->pParse
;
3282 SrcItem
*pSrc
= &pBuilder
->pWInfo
->pTabList
->a
[pNew
->iTab
];
3283 int nConstraint
= pIdxInfo
->nConstraint
;
3285 assert( (mUsable
& mPrereq
)==mPrereq
);
3287 pNew
->prereq
= mPrereq
;
3289 /* Set the usable flag on the subset of constraints identified by
3290 ** arguments mUsable and mExclude. */
3291 pIdxCons
= *(struct sqlite3_index_constraint
**)&pIdxInfo
->aConstraint
;
3292 for(i
=0; i
<nConstraint
; i
++, pIdxCons
++){
3293 WhereTerm
*pTerm
= &pWC
->a
[pIdxCons
->iTermOffset
];
3294 pIdxCons
->usable
= 0;
3295 if( (pTerm
->prereqRight
& mUsable
)==pTerm
->prereqRight
3296 && (pTerm
->eOperator
& mExclude
)==0
3298 pIdxCons
->usable
= 1;
3302 /* Initialize the output fields of the sqlite3_index_info structure */
3303 memset(pUsage
, 0, sizeof(pUsage
[0])*nConstraint
);
3304 assert( pIdxInfo
->needToFreeIdxStr
==0 );
3305 pIdxInfo
->idxStr
= 0;
3306 pIdxInfo
->idxNum
= 0;
3307 pIdxInfo
->orderByConsumed
= 0;
3308 pIdxInfo
->estimatedCost
= SQLITE_BIG_DBL
/ (double)2;
3309 pIdxInfo
->estimatedRows
= 25;
3310 pIdxInfo
->idxFlags
= 0;
3311 pIdxInfo
->colUsed
= (sqlite3_int64
)pSrc
->colUsed
;
3313 /* Invoke the virtual table xBestIndex() method */
3314 rc
= vtabBestIndex(pParse
, pSrc
->pTab
, pIdxInfo
);
3316 if( rc
==SQLITE_CONSTRAINT
){
3317 /* If the xBestIndex method returns SQLITE_CONSTRAINT, that means
3318 ** that the particular combination of parameters provided is unusable.
3319 ** Make no entries in the loop table.
3321 WHERETRACE(0xffff, (" ^^^^--- non-viable plan rejected!\n"));
3328 assert( pNew
->nLSlot
>=nConstraint
);
3329 for(i
=0; i
<nConstraint
; i
++) pNew
->aLTerm
[i
] = 0;
3330 pNew
->u
.vtab
.omitMask
= 0;
3331 pIdxCons
= *(struct sqlite3_index_constraint
**)&pIdxInfo
->aConstraint
;
3332 for(i
=0; i
<nConstraint
; i
++, pIdxCons
++){
3334 if( (iTerm
= pUsage
[i
].argvIndex
- 1)>=0 ){
3336 int j
= pIdxCons
->iTermOffset
;
3337 if( iTerm
>=nConstraint
3340 || pNew
->aLTerm
[iTerm
]!=0
3341 || pIdxCons
->usable
==0
3343 sqlite3ErrorMsg(pParse
,"%s.xBestIndex malfunction",pSrc
->pTab
->zName
);
3344 testcase( pIdxInfo
->needToFreeIdxStr
);
3345 return SQLITE_ERROR
;
3347 testcase( iTerm
==nConstraint
-1 );
3349 testcase( j
==pWC
->nTerm
-1 );
3351 pNew
->prereq
|= pTerm
->prereqRight
;
3352 assert( iTerm
<pNew
->nLSlot
);
3353 pNew
->aLTerm
[iTerm
] = pTerm
;
3354 if( iTerm
>mxTerm
) mxTerm
= iTerm
;
3355 testcase( iTerm
==15 );
3356 testcase( iTerm
==16 );
3357 if( pUsage
[i
].omit
){
3358 if( i
<16 && ((1<<i
)&mNoOmit
)==0 ){
3359 testcase( i
!=iTerm
);
3360 pNew
->u
.vtab
.omitMask
|= 1<<iTerm
;
3362 testcase( i
!=iTerm
);
3365 if( (pTerm
->eOperator
& WO_IN
)!=0 ){
3366 /* A virtual table that is constrained by an IN clause may not
3367 ** consume the ORDER BY clause because (1) the order of IN terms
3368 ** is not necessarily related to the order of output terms and
3369 ** (2) Multiple outputs from a single IN value will not merge
3371 pIdxInfo
->orderByConsumed
= 0;
3372 pIdxInfo
->idxFlags
&= ~SQLITE_INDEX_SCAN_UNIQUE
;
3373 *pbIn
= 1; assert( (mExclude
& WO_IN
)==0 );
3378 pNew
->nLTerm
= mxTerm
+1;
3379 for(i
=0; i
<=mxTerm
; i
++){
3380 if( pNew
->aLTerm
[i
]==0 ){
3381 /* The non-zero argvIdx values must be contiguous. Raise an
3382 ** error if they are not */
3383 sqlite3ErrorMsg(pParse
,"%s.xBestIndex malfunction",pSrc
->pTab
->zName
);
3384 testcase( pIdxInfo
->needToFreeIdxStr
);
3385 return SQLITE_ERROR
;
3388 assert( pNew
->nLTerm
<=pNew
->nLSlot
);
3389 pNew
->u
.vtab
.idxNum
= pIdxInfo
->idxNum
;
3390 pNew
->u
.vtab
.needFree
= pIdxInfo
->needToFreeIdxStr
;
3391 pIdxInfo
->needToFreeIdxStr
= 0;
3392 pNew
->u
.vtab
.idxStr
= pIdxInfo
->idxStr
;
3393 pNew
->u
.vtab
.isOrdered
= (i8
)(pIdxInfo
->orderByConsumed
?
3394 pIdxInfo
->nOrderBy
: 0);
3396 pNew
->rRun
= sqlite3LogEstFromDouble(pIdxInfo
->estimatedCost
);
3397 pNew
->nOut
= sqlite3LogEst(pIdxInfo
->estimatedRows
);
3399 /* Set the WHERE_ONEROW flag if the xBestIndex() method indicated
3400 ** that the scan will visit at most one row. Clear it otherwise. */
3401 if( pIdxInfo
->idxFlags
& SQLITE_INDEX_SCAN_UNIQUE
){
3402 pNew
->wsFlags
|= WHERE_ONEROW
;
3404 pNew
->wsFlags
&= ~WHERE_ONEROW
;
3406 rc
= whereLoopInsert(pBuilder
, pNew
);
3407 if( pNew
->u
.vtab
.needFree
){
3408 sqlite3_free(pNew
->u
.vtab
.idxStr
);
3409 pNew
->u
.vtab
.needFree
= 0;
3411 WHERETRACE(0xffff, (" bIn=%d prereqIn=%04llx prereqOut=%04llx\n",
3412 *pbIn
, (sqlite3_uint64
)mPrereq
,
3413 (sqlite3_uint64
)(pNew
->prereq
& ~mPrereq
)));
3419 ** If this function is invoked from within an xBestIndex() callback, it
3420 ** returns a pointer to a buffer containing the name of the collation
3421 ** sequence associated with element iCons of the sqlite3_index_info.aConstraint
3422 ** array. Or, if iCons is out of range or there is no active xBestIndex
3423 ** call, return NULL.
3425 const char *sqlite3_vtab_collation(sqlite3_index_info
*pIdxInfo
, int iCons
){
3426 HiddenIndexInfo
*pHidden
= (HiddenIndexInfo
*)&pIdxInfo
[1];
3427 const char *zRet
= 0;
3428 if( iCons
>=0 && iCons
<pIdxInfo
->nConstraint
){
3430 int iTerm
= pIdxInfo
->aConstraint
[iCons
].iTermOffset
;
3431 Expr
*pX
= pHidden
->pWC
->a
[iTerm
].pExpr
;
3433 pC
= sqlite3ExprCompareCollSeq(pHidden
->pParse
, pX
);
3435 zRet
= (pC
? pC
->zName
: sqlite3StrBINARY
);
3441 ** Add all WhereLoop objects for a table of the join identified by
3442 ** pBuilder->pNew->iTab. That table is guaranteed to be a virtual table.
3444 ** If there are no LEFT or CROSS JOIN joins in the query, both mPrereq and
3445 ** mUnusable are set to 0. Otherwise, mPrereq is a mask of all FROM clause
3446 ** entries that occur before the virtual table in the FROM clause and are
3447 ** separated from it by at least one LEFT or CROSS JOIN. Similarly, the
3448 ** mUnusable mask contains all FROM clause entries that occur after the
3449 ** virtual table and are separated from it by at least one LEFT or
3452 ** For example, if the query were:
3454 ** ... FROM t1, t2 LEFT JOIN t3, t4, vt CROSS JOIN t5, t6;
3456 ** then mPrereq corresponds to (t1, t2) and mUnusable to (t5, t6).
3458 ** All the tables in mPrereq must be scanned before the current virtual
3459 ** table. So any terms for which all prerequisites are satisfied by
3460 ** mPrereq may be specified as "usable" in all calls to xBestIndex.
3461 ** Conversely, all tables in mUnusable must be scanned after the current
3462 ** virtual table, so any terms for which the prerequisites overlap with
3463 ** mUnusable should always be configured as "not-usable" for xBestIndex.
3465 static int whereLoopAddVirtual(
3466 WhereLoopBuilder
*pBuilder
, /* WHERE clause information */
3467 Bitmask mPrereq
, /* Tables that must be scanned before this one */
3468 Bitmask mUnusable
/* Tables that must be scanned after this one */
3470 int rc
= SQLITE_OK
; /* Return code */
3471 WhereInfo
*pWInfo
; /* WHERE analysis context */
3472 Parse
*pParse
; /* The parsing context */
3473 WhereClause
*pWC
; /* The WHERE clause */
3474 SrcItem
*pSrc
; /* The FROM clause term to search */
3475 sqlite3_index_info
*p
; /* Object to pass to xBestIndex() */
3476 int nConstraint
; /* Number of constraints in p */
3477 int bIn
; /* True if plan uses IN(...) operator */
3479 Bitmask mBest
; /* Tables used by best possible plan */
3482 assert( (mPrereq
& mUnusable
)==0 );
3483 pWInfo
= pBuilder
->pWInfo
;
3484 pParse
= pWInfo
->pParse
;
3485 pWC
= pBuilder
->pWC
;
3486 pNew
= pBuilder
->pNew
;
3487 pSrc
= &pWInfo
->pTabList
->a
[pNew
->iTab
];
3488 assert( IsVirtual(pSrc
->pTab
) );
3489 p
= allocateIndexInfo(pParse
, pWC
, mUnusable
, pSrc
, pBuilder
->pOrderBy
,
3491 if( p
==0 ) return SQLITE_NOMEM_BKPT
;
3493 pNew
->wsFlags
= WHERE_VIRTUALTABLE
;
3495 pNew
->u
.vtab
.needFree
= 0;
3496 nConstraint
= p
->nConstraint
;
3497 if( whereLoopResize(pParse
->db
, pNew
, nConstraint
) ){
3498 sqlite3DbFree(pParse
->db
, p
);
3499 return SQLITE_NOMEM_BKPT
;
3502 /* First call xBestIndex() with all constraints usable. */
3503 WHERETRACE(0x800, ("BEGIN %s.addVirtual()\n", pSrc
->pTab
->zName
));
3504 WHERETRACE(0x40, (" VirtualOne: all usable\n"));
3505 rc
= whereLoopAddVirtualOne(pBuilder
, mPrereq
, ALLBITS
, 0, p
, mNoOmit
, &bIn
);
3507 /* If the call to xBestIndex() with all terms enabled produced a plan
3508 ** that does not require any source tables (IOW: a plan with mBest==0)
3509 ** and does not use an IN(...) operator, then there is no point in making
3510 ** any further calls to xBestIndex() since they will all return the same
3511 ** result (if the xBestIndex() implementation is sane). */
3512 if( rc
==SQLITE_OK
&& ((mBest
= (pNew
->prereq
& ~mPrereq
))!=0 || bIn
) ){
3513 int seenZero
= 0; /* True if a plan with no prereqs seen */
3514 int seenZeroNoIN
= 0; /* Plan with no prereqs and no IN(...) seen */
3516 Bitmask mBestNoIn
= 0;
3518 /* If the plan produced by the earlier call uses an IN(...) term, call
3519 ** xBestIndex again, this time with IN(...) terms disabled. */
3521 WHERETRACE(0x40, (" VirtualOne: all usable w/o IN\n"));
3522 rc
= whereLoopAddVirtualOne(
3523 pBuilder
, mPrereq
, ALLBITS
, WO_IN
, p
, mNoOmit
, &bIn
);
3525 mBestNoIn
= pNew
->prereq
& ~mPrereq
;
3532 /* Call xBestIndex once for each distinct value of (prereqRight & ~mPrereq)
3533 ** in the set of terms that apply to the current virtual table. */
3534 while( rc
==SQLITE_OK
){
3536 Bitmask mNext
= ALLBITS
;
3538 for(i
=0; i
<nConstraint
; i
++){
3540 pWC
->a
[p
->aConstraint
[i
].iTermOffset
].prereqRight
& ~mPrereq
3542 if( mThis
>mPrev
&& mThis
<mNext
) mNext
= mThis
;
3545 if( mNext
==ALLBITS
) break;
3546 if( mNext
==mBest
|| mNext
==mBestNoIn
) continue;
3547 WHERETRACE(0x40, (" VirtualOne: mPrev=%04llx mNext=%04llx\n",
3548 (sqlite3_uint64
)mPrev
, (sqlite3_uint64
)mNext
));
3549 rc
= whereLoopAddVirtualOne(
3550 pBuilder
, mPrereq
, mNext
|mPrereq
, 0, p
, mNoOmit
, &bIn
);
3551 if( pNew
->prereq
==mPrereq
){
3553 if( bIn
==0 ) seenZeroNoIN
= 1;
3557 /* If the calls to xBestIndex() in the above loop did not find a plan
3558 ** that requires no source tables at all (i.e. one guaranteed to be
3559 ** usable), make a call here with all source tables disabled */
3560 if( rc
==SQLITE_OK
&& seenZero
==0 ){
3561 WHERETRACE(0x40, (" VirtualOne: all disabled\n"));
3562 rc
= whereLoopAddVirtualOne(
3563 pBuilder
, mPrereq
, mPrereq
, 0, p
, mNoOmit
, &bIn
);
3564 if( bIn
==0 ) seenZeroNoIN
= 1;
3567 /* If the calls to xBestIndex() have so far failed to find a plan
3568 ** that requires no source tables at all and does not use an IN(...)
3569 ** operator, make a final call to obtain one here. */
3570 if( rc
==SQLITE_OK
&& seenZeroNoIN
==0 ){
3571 WHERETRACE(0x40, (" VirtualOne: all disabled and w/o IN\n"));
3572 rc
= whereLoopAddVirtualOne(
3573 pBuilder
, mPrereq
, mPrereq
, WO_IN
, p
, mNoOmit
, &bIn
);
3577 if( p
->needToFreeIdxStr
) sqlite3_free(p
->idxStr
);
3578 sqlite3DbFreeNN(pParse
->db
, p
);
3579 WHERETRACE(0x800, ("END %s.addVirtual(), rc=%d\n", pSrc
->pTab
->zName
, rc
));
3582 #endif /* SQLITE_OMIT_VIRTUALTABLE */
3585 ** Add WhereLoop entries to handle OR terms. This works for either
3586 ** btrees or virtual tables.
3588 static int whereLoopAddOr(
3589 WhereLoopBuilder
*pBuilder
,
3593 WhereInfo
*pWInfo
= pBuilder
->pWInfo
;
3596 WhereTerm
*pTerm
, *pWCEnd
;
3600 WhereLoopBuilder sSubBuild
;
3601 WhereOrSet sSum
, sCur
;
3604 pWC
= pBuilder
->pWC
;
3605 pWCEnd
= pWC
->a
+ pWC
->nTerm
;
3606 pNew
= pBuilder
->pNew
;
3607 memset(&sSum
, 0, sizeof(sSum
));
3608 pItem
= pWInfo
->pTabList
->a
+ pNew
->iTab
;
3609 iCur
= pItem
->iCursor
;
3611 for(pTerm
=pWC
->a
; pTerm
<pWCEnd
&& rc
==SQLITE_OK
; pTerm
++){
3612 if( (pTerm
->eOperator
& WO_OR
)!=0
3613 && (pTerm
->u
.pOrInfo
->indexable
& pNew
->maskSelf
)!=0
3615 WhereClause
* const pOrWC
= &pTerm
->u
.pOrInfo
->wc
;
3616 WhereTerm
* const pOrWCEnd
= &pOrWC
->a
[pOrWC
->nTerm
];
3621 sSubBuild
= *pBuilder
;
3622 sSubBuild
.pOrderBy
= 0;
3623 sSubBuild
.pOrSet
= &sCur
;
3625 WHERETRACE(0x200, ("Begin processing OR-clause %p\n", pTerm
));
3626 for(pOrTerm
=pOrWC
->a
; pOrTerm
<pOrWCEnd
; pOrTerm
++){
3627 if( (pOrTerm
->eOperator
& WO_AND
)!=0 ){
3628 sSubBuild
.pWC
= &pOrTerm
->u
.pAndInfo
->wc
;
3629 }else if( pOrTerm
->leftCursor
==iCur
){
3630 tempWC
.pWInfo
= pWC
->pWInfo
;
3631 tempWC
.pOuter
= pWC
;
3635 sSubBuild
.pWC
= &tempWC
;
3640 #ifdef WHERETRACE_ENABLED
3641 WHERETRACE(0x200, ("OR-term %d of %p has %d subterms:\n",
3642 (int)(pOrTerm
-pOrWC
->a
), pTerm
, sSubBuild
.pWC
->nTerm
));
3643 if( sqlite3WhereTrace
& 0x400 ){
3644 sqlite3WhereClausePrint(sSubBuild
.pWC
);
3647 #ifndef SQLITE_OMIT_VIRTUALTABLE
3648 if( IsVirtual(pItem
->pTab
) ){
3649 rc
= whereLoopAddVirtual(&sSubBuild
, mPrereq
, mUnusable
);
3653 rc
= whereLoopAddBtree(&sSubBuild
, mPrereq
);
3655 if( rc
==SQLITE_OK
){
3656 rc
= whereLoopAddOr(&sSubBuild
, mPrereq
, mUnusable
);
3658 assert( rc
==SQLITE_OK
|| rc
==SQLITE_DONE
|| sCur
.n
==0
3659 || rc
==SQLITE_NOMEM
);
3660 testcase( rc
==SQLITE_NOMEM
&& sCur
.n
>0 );
3661 testcase( rc
==SQLITE_DONE
);
3666 whereOrMove(&sSum
, &sCur
);
3670 whereOrMove(&sPrev
, &sSum
);
3672 for(i
=0; i
<sPrev
.n
; i
++){
3673 for(j
=0; j
<sCur
.n
; j
++){
3674 whereOrInsert(&sSum
, sPrev
.a
[i
].prereq
| sCur
.a
[j
].prereq
,
3675 sqlite3LogEstAdd(sPrev
.a
[i
].rRun
, sCur
.a
[j
].rRun
),
3676 sqlite3LogEstAdd(sPrev
.a
[i
].nOut
, sCur
.a
[j
].nOut
));
3682 pNew
->aLTerm
[0] = pTerm
;
3683 pNew
->wsFlags
= WHERE_MULTI_OR
;
3686 memset(&pNew
->u
, 0, sizeof(pNew
->u
));
3687 for(i
=0; rc
==SQLITE_OK
&& i
<sSum
.n
; i
++){
3688 /* TUNING: Currently sSum.a[i].rRun is set to the sum of the costs
3689 ** of all sub-scans required by the OR-scan. However, due to rounding
3690 ** errors, it may be that the cost of the OR-scan is equal to its
3691 ** most expensive sub-scan. Add the smallest possible penalty
3692 ** (equivalent to multiplying the cost by 1.07) to ensure that
3693 ** this does not happen. Otherwise, for WHERE clauses such as the
3694 ** following where there is an index on "y":
3696 ** WHERE likelihood(x=?, 0.99) OR y=?
3698 ** the planner may elect to "OR" together a full-table scan and an
3699 ** index lookup. And other similarly odd results. */
3700 pNew
->rRun
= sSum
.a
[i
].rRun
+ 1;
3701 pNew
->nOut
= sSum
.a
[i
].nOut
;
3702 pNew
->prereq
= sSum
.a
[i
].prereq
;
3703 rc
= whereLoopInsert(pBuilder
, pNew
);
3705 WHERETRACE(0x200, ("End processing OR-clause %p\n", pTerm
));
3712 ** Add all WhereLoop objects for all tables
3714 static int whereLoopAddAll(WhereLoopBuilder
*pBuilder
){
3715 WhereInfo
*pWInfo
= pBuilder
->pWInfo
;
3716 Bitmask mPrereq
= 0;
3719 SrcList
*pTabList
= pWInfo
->pTabList
;
3721 SrcItem
*pEnd
= &pTabList
->a
[pWInfo
->nLevel
];
3722 sqlite3
*db
= pWInfo
->pParse
->db
;
3726 /* Loop over the tables in the join, from left to right */
3727 pNew
= pBuilder
->pNew
;
3728 whereLoopInit(pNew
);
3729 pBuilder
->iPlanLimit
= SQLITE_QUERY_PLANNER_LIMIT
;
3730 for(iTab
=0, pItem
=pTabList
->a
; pItem
<pEnd
; iTab
++, pItem
++){
3731 Bitmask mUnusable
= 0;
3733 pBuilder
->iPlanLimit
+= SQLITE_QUERY_PLANNER_LIMIT_INCR
;
3734 pNew
->maskSelf
= sqlite3WhereGetMask(&pWInfo
->sMaskSet
, pItem
->iCursor
);
3735 if( (pItem
->fg
.jointype
& (JT_LEFT
|JT_CROSS
))!=0 ){
3736 /* This condition is true when pItem is the FROM clause term on the
3737 ** right-hand-side of a LEFT or CROSS JOIN. */
3742 #ifndef SQLITE_OMIT_VIRTUALTABLE
3743 if( IsVirtual(pItem
->pTab
) ){
3745 for(p
=&pItem
[1]; p
<pEnd
; p
++){
3746 if( mUnusable
|| (p
->fg
.jointype
& (JT_LEFT
|JT_CROSS
)) ){
3747 mUnusable
|= sqlite3WhereGetMask(&pWInfo
->sMaskSet
, p
->iCursor
);
3750 rc
= whereLoopAddVirtual(pBuilder
, mPrereq
, mUnusable
);
3752 #endif /* SQLITE_OMIT_VIRTUALTABLE */
3754 rc
= whereLoopAddBtree(pBuilder
, mPrereq
);
3756 if( rc
==SQLITE_OK
&& pBuilder
->pWC
->hasOr
){
3757 rc
= whereLoopAddOr(pBuilder
, mPrereq
, mUnusable
);
3759 mPrior
|= pNew
->maskSelf
;
3760 if( rc
|| db
->mallocFailed
){
3761 if( rc
==SQLITE_DONE
){
3762 /* We hit the query planner search limit set by iPlanLimit */
3763 sqlite3_log(SQLITE_WARNING
, "abbreviated query algorithm search");
3771 whereLoopClear(db
, pNew
);
3776 ** Examine a WherePath (with the addition of the extra WhereLoop of the 6th
3777 ** parameters) to see if it outputs rows in the requested ORDER BY
3778 ** (or GROUP BY) without requiring a separate sort operation. Return N:
3780 ** N>0: N terms of the ORDER BY clause are satisfied
3781 ** N==0: No terms of the ORDER BY clause are satisfied
3782 ** N<0: Unknown yet how many terms of ORDER BY might be satisfied.
3784 ** Note that processing for WHERE_GROUPBY and WHERE_DISTINCTBY is not as
3785 ** strict. With GROUP BY and DISTINCT the only requirement is that
3786 ** equivalent rows appear immediately adjacent to one another. GROUP BY
3787 ** and DISTINCT do not require rows to appear in any particular order as long
3788 ** as equivalent rows are grouped together. Thus for GROUP BY and DISTINCT
3789 ** the pOrderBy terms can be matched in any order. With ORDER BY, the
3790 ** pOrderBy terms must be matched in strict left-to-right order.
3792 static i8
wherePathSatisfiesOrderBy(
3793 WhereInfo
*pWInfo
, /* The WHERE clause */
3794 ExprList
*pOrderBy
, /* ORDER BY or GROUP BY or DISTINCT clause to check */
3795 WherePath
*pPath
, /* The WherePath to check */
3796 u16 wctrlFlags
, /* WHERE_GROUPBY or _DISTINCTBY or _ORDERBY_LIMIT */
3797 u16 nLoop
, /* Number of entries in pPath->aLoop[] */
3798 WhereLoop
*pLast
, /* Add this WhereLoop to the end of pPath->aLoop[] */
3799 Bitmask
*pRevMask
/* OUT: Mask of WhereLoops to run in reverse order */
3801 u8 revSet
; /* True if rev is known */
3802 u8 rev
; /* Composite sort order */
3803 u8 revIdx
; /* Index sort order */
3804 u8 isOrderDistinct
; /* All prior WhereLoops are order-distinct */
3805 u8 distinctColumns
; /* True if the loop has UNIQUE NOT NULL columns */
3806 u8 isMatch
; /* iColumn matches a term of the ORDER BY clause */
3807 u16 eqOpMask
; /* Allowed equality operators */
3808 u16 nKeyCol
; /* Number of key columns in pIndex */
3809 u16 nColumn
; /* Total number of ordered columns in the index */
3810 u16 nOrderBy
; /* Number terms in the ORDER BY clause */
3811 int iLoop
; /* Index of WhereLoop in pPath being processed */
3812 int i
, j
; /* Loop counters */
3813 int iCur
; /* Cursor number for current WhereLoop */
3814 int iColumn
; /* A column number within table iCur */
3815 WhereLoop
*pLoop
= 0; /* Current WhereLoop being processed. */
3816 WhereTerm
*pTerm
; /* A single term of the WHERE clause */
3817 Expr
*pOBExpr
; /* An expression from the ORDER BY clause */
3818 CollSeq
*pColl
; /* COLLATE function from an ORDER BY clause term */
3819 Index
*pIndex
; /* The index associated with pLoop */
3820 sqlite3
*db
= pWInfo
->pParse
->db
; /* Database connection */
3821 Bitmask obSat
= 0; /* Mask of ORDER BY terms satisfied so far */
3822 Bitmask obDone
; /* Mask of all ORDER BY terms */
3823 Bitmask orderDistinctMask
; /* Mask of all well-ordered loops */
3824 Bitmask ready
; /* Mask of inner loops */
3827 ** We say the WhereLoop is "one-row" if it generates no more than one
3828 ** row of output. A WhereLoop is one-row if all of the following are true:
3829 ** (a) All index columns match with WHERE_COLUMN_EQ.
3830 ** (b) The index is unique
3831 ** Any WhereLoop with an WHERE_COLUMN_EQ constraint on the rowid is one-row.
3832 ** Every one-row WhereLoop will have the WHERE_ONEROW bit set in wsFlags.
3834 ** We say the WhereLoop is "order-distinct" if the set of columns from
3835 ** that WhereLoop that are in the ORDER BY clause are different for every
3836 ** row of the WhereLoop. Every one-row WhereLoop is automatically
3837 ** order-distinct. A WhereLoop that has no columns in the ORDER BY clause
3838 ** is not order-distinct. To be order-distinct is not quite the same as being
3839 ** UNIQUE since a UNIQUE column or index can have multiple rows that
3840 ** are NULL and NULL values are equivalent for the purpose of order-distinct.
3841 ** To be order-distinct, the columns must be UNIQUE and NOT NULL.
3843 ** The rowid for a table is always UNIQUE and NOT NULL so whenever the
3844 ** rowid appears in the ORDER BY clause, the corresponding WhereLoop is
3845 ** automatically order-distinct.
3848 assert( pOrderBy
!=0 );
3849 if( nLoop
&& OptimizationDisabled(db
, SQLITE_OrderByIdxJoin
) ) return 0;
3851 nOrderBy
= pOrderBy
->nExpr
;
3852 testcase( nOrderBy
==BMS
-1 );
3853 if( nOrderBy
>BMS
-1 ) return 0; /* Cannot optimize overly large ORDER BYs */
3854 isOrderDistinct
= 1;
3855 obDone
= MASKBIT(nOrderBy
)-1;
3856 orderDistinctMask
= 0;
3858 eqOpMask
= WO_EQ
| WO_IS
| WO_ISNULL
;
3859 if( wctrlFlags
& (WHERE_ORDERBY_LIMIT
|WHERE_ORDERBY_MAX
|WHERE_ORDERBY_MIN
) ){
3862 for(iLoop
=0; isOrderDistinct
&& obSat
<obDone
&& iLoop
<=nLoop
; iLoop
++){
3863 if( iLoop
>0 ) ready
|= pLoop
->maskSelf
;
3865 pLoop
= pPath
->aLoop
[iLoop
];
3866 if( wctrlFlags
& WHERE_ORDERBY_LIMIT
) continue;
3870 if( pLoop
->wsFlags
& WHERE_VIRTUALTABLE
){
3871 if( pLoop
->u
.vtab
.isOrdered
&& (wctrlFlags
& WHERE_DISTINCTBY
)==0 ){
3875 }else if( wctrlFlags
& WHERE_DISTINCTBY
){
3876 pLoop
->u
.btree
.nDistinctCol
= 0;
3878 iCur
= pWInfo
->pTabList
->a
[pLoop
->iTab
].iCursor
;
3880 /* Mark off any ORDER BY term X that is a column in the table of
3881 ** the current loop for which there is term in the WHERE
3882 ** clause of the form X IS NULL or X=? that reference only outer
3885 for(i
=0; i
<nOrderBy
; i
++){
3886 if( MASKBIT(i
) & obSat
) continue;
3887 pOBExpr
= sqlite3ExprSkipCollateAndLikely(pOrderBy
->a
[i
].pExpr
);
3888 if( NEVER(pOBExpr
==0) ) continue;
3889 if( pOBExpr
->op
!=TK_COLUMN
&& pOBExpr
->op
!=TK_AGG_COLUMN
) continue;
3890 if( pOBExpr
->iTable
!=iCur
) continue;
3891 pTerm
= sqlite3WhereFindTerm(&pWInfo
->sWC
, iCur
, pOBExpr
->iColumn
,
3892 ~ready
, eqOpMask
, 0);
3893 if( pTerm
==0 ) continue;
3894 if( pTerm
->eOperator
==WO_IN
){
3895 /* IN terms are only valid for sorting in the ORDER BY LIMIT
3896 ** optimization, and then only if they are actually used
3897 ** by the query plan */
3898 assert( wctrlFlags
&
3899 (WHERE_ORDERBY_LIMIT
|WHERE_ORDERBY_MIN
|WHERE_ORDERBY_MAX
) );
3900 for(j
=0; j
<pLoop
->nLTerm
&& pTerm
!=pLoop
->aLTerm
[j
]; j
++){}
3901 if( j
>=pLoop
->nLTerm
) continue;
3903 if( (pTerm
->eOperator
&(WO_EQ
|WO_IS
))!=0 && pOBExpr
->iColumn
>=0 ){
3904 Parse
*pParse
= pWInfo
->pParse
;
3905 CollSeq
*pColl1
= sqlite3ExprNNCollSeq(pParse
, pOrderBy
->a
[i
].pExpr
);
3906 CollSeq
*pColl2
= sqlite3ExprCompareCollSeq(pParse
, pTerm
->pExpr
);
3908 if( pColl2
==0 || sqlite3StrICmp(pColl1
->zName
, pColl2
->zName
) ){
3911 testcase( pTerm
->pExpr
->op
==TK_IS
);
3913 obSat
|= MASKBIT(i
);
3916 if( (pLoop
->wsFlags
& WHERE_ONEROW
)==0 ){
3917 if( pLoop
->wsFlags
& WHERE_IPK
){
3921 }else if( (pIndex
= pLoop
->u
.btree
.pIndex
)==0 || pIndex
->bUnordered
){
3924 nKeyCol
= pIndex
->nKeyCol
;
3925 nColumn
= pIndex
->nColumn
;
3926 assert( nColumn
==nKeyCol
+1 || !HasRowid(pIndex
->pTable
) );
3927 assert( pIndex
->aiColumn
[nColumn
-1]==XN_ROWID
3928 || !HasRowid(pIndex
->pTable
));
3929 /* All relevant terms of the index must also be non-NULL in order
3930 ** for isOrderDistinct to be true. So the isOrderDistint value
3931 ** computed here might be a false positive. Corrections will be
3932 ** made at tag-20210426-1 below */
3933 isOrderDistinct
= IsUniqueIndex(pIndex
)
3934 && (pLoop
->wsFlags
& WHERE_SKIPSCAN
)==0;
3937 /* Loop through all columns of the index and deal with the ones
3938 ** that are not constrained by == or IN.
3941 distinctColumns
= 0;
3942 for(j
=0; j
<nColumn
; j
++){
3943 u8 bOnce
= 1; /* True to run the ORDER BY search loop */
3945 assert( j
>=pLoop
->u
.btree
.nEq
3946 || (pLoop
->aLTerm
[j
]==0)==(j
<pLoop
->nSkip
)
3948 if( j
<pLoop
->u
.btree
.nEq
&& j
>=pLoop
->nSkip
){
3949 u16 eOp
= pLoop
->aLTerm
[j
]->eOperator
;
3951 /* Skip over == and IS and ISNULL terms. (Also skip IN terms when
3952 ** doing WHERE_ORDERBY_LIMIT processing). Except, IS and ISNULL
3953 ** terms imply that the index is not UNIQUE NOT NULL in which case
3954 ** the loop need to be marked as not order-distinct because it can
3955 ** have repeated NULL rows.
3957 ** If the current term is a column of an ((?,?) IN (SELECT...))
3958 ** expression for which the SELECT returns more than one column,
3959 ** check that it is the only column used by this loop. Otherwise,
3960 ** if it is one of two or more, none of the columns can be
3961 ** considered to match an ORDER BY term.
3963 if( (eOp
& eqOpMask
)!=0 ){
3964 if( eOp
& (WO_ISNULL
|WO_IS
) ){
3965 testcase( eOp
& WO_ISNULL
);
3966 testcase( eOp
& WO_IS
);
3967 testcase( isOrderDistinct
);
3968 isOrderDistinct
= 0;
3971 }else if( ALWAYS(eOp
& WO_IN
) ){
3972 /* ALWAYS() justification: eOp is an equality operator due to the
3973 ** j<pLoop->u.btree.nEq constraint above. Any equality other
3974 ** than WO_IN is captured by the previous "if". So this one
3975 ** always has to be WO_IN. */
3976 Expr
*pX
= pLoop
->aLTerm
[j
]->pExpr
;
3977 for(i
=j
+1; i
<pLoop
->u
.btree
.nEq
; i
++){
3978 if( pLoop
->aLTerm
[i
]->pExpr
==pX
){
3979 assert( (pLoop
->aLTerm
[i
]->eOperator
& WO_IN
) );
3987 /* Get the column number in the table (iColumn) and sort order
3988 ** (revIdx) for the j-th column of the index.
3991 iColumn
= pIndex
->aiColumn
[j
];
3992 revIdx
= pIndex
->aSortOrder
[j
] & KEYINFO_ORDER_DESC
;
3993 if( iColumn
==pIndex
->pTable
->iPKey
) iColumn
= XN_ROWID
;
3999 /* An unconstrained column that might be NULL means that this
4000 ** WhereLoop is not well-ordered. tag-20210426-1
4002 if( isOrderDistinct
){
4004 && j
>=pLoop
->u
.btree
.nEq
4005 && pIndex
->pTable
->aCol
[iColumn
].notNull
==0
4007 isOrderDistinct
= 0;
4009 if( iColumn
==XN_EXPR
){
4010 isOrderDistinct
= 0;
4014 /* Find the ORDER BY term that corresponds to the j-th column
4015 ** of the index and mark that ORDER BY term off
4018 for(i
=0; bOnce
&& i
<nOrderBy
; i
++){
4019 if( MASKBIT(i
) & obSat
) continue;
4020 pOBExpr
= sqlite3ExprSkipCollateAndLikely(pOrderBy
->a
[i
].pExpr
);
4021 testcase( wctrlFlags
& WHERE_GROUPBY
);
4022 testcase( wctrlFlags
& WHERE_DISTINCTBY
);
4023 if( NEVER(pOBExpr
==0) ) continue;
4024 if( (wctrlFlags
& (WHERE_GROUPBY
|WHERE_DISTINCTBY
))==0 ) bOnce
= 0;
4025 if( iColumn
>=XN_ROWID
){
4026 if( pOBExpr
->op
!=TK_COLUMN
&& pOBExpr
->op
!=TK_AGG_COLUMN
) continue;
4027 if( pOBExpr
->iTable
!=iCur
) continue;
4028 if( pOBExpr
->iColumn
!=iColumn
) continue;
4030 Expr
*pIdxExpr
= pIndex
->aColExpr
->a
[j
].pExpr
;
4031 if( sqlite3ExprCompareSkip(pOBExpr
, pIdxExpr
, iCur
) ){
4035 if( iColumn
!=XN_ROWID
){
4036 pColl
= sqlite3ExprNNCollSeq(pWInfo
->pParse
, pOrderBy
->a
[i
].pExpr
);
4037 if( sqlite3StrICmp(pColl
->zName
, pIndex
->azColl
[j
])!=0 ) continue;
4039 if( wctrlFlags
& WHERE_DISTINCTBY
){
4040 pLoop
->u
.btree
.nDistinctCol
= j
+1;
4045 if( isMatch
&& (wctrlFlags
& WHERE_GROUPBY
)==0 ){
4046 /* Make sure the sort order is compatible in an ORDER BY clause.
4047 ** Sort order is irrelevant for a GROUP BY clause. */
4049 if( (rev
^ revIdx
)!=(pOrderBy
->a
[i
].sortFlags
&KEYINFO_ORDER_DESC
) ){
4053 rev
= revIdx
^ (pOrderBy
->a
[i
].sortFlags
& KEYINFO_ORDER_DESC
);
4054 if( rev
) *pRevMask
|= MASKBIT(iLoop
);
4058 if( isMatch
&& (pOrderBy
->a
[i
].sortFlags
& KEYINFO_ORDER_BIGNULL
) ){
4059 if( j
==pLoop
->u
.btree
.nEq
){
4060 pLoop
->wsFlags
|= WHERE_BIGNULL_SORT
;
4066 if( iColumn
==XN_ROWID
){
4067 testcase( distinctColumns
==0 );
4068 distinctColumns
= 1;
4070 obSat
|= MASKBIT(i
);
4072 /* No match found */
4073 if( j
==0 || j
<nKeyCol
){
4074 testcase( isOrderDistinct
!=0 );
4075 isOrderDistinct
= 0;
4079 } /* end Loop over all index columns */
4080 if( distinctColumns
){
4081 testcase( isOrderDistinct
==0 );
4082 isOrderDistinct
= 1;
4084 } /* end-if not one-row */
4086 /* Mark off any other ORDER BY terms that reference pLoop */
4087 if( isOrderDistinct
){
4088 orderDistinctMask
|= pLoop
->maskSelf
;
4089 for(i
=0; i
<nOrderBy
; i
++){
4092 if( MASKBIT(i
) & obSat
) continue;
4093 p
= pOrderBy
->a
[i
].pExpr
;
4094 mTerm
= sqlite3WhereExprUsage(&pWInfo
->sMaskSet
,p
);
4095 if( mTerm
==0 && !sqlite3ExprIsConstant(p
) ) continue;
4096 if( (mTerm
&~orderDistinctMask
)==0 ){
4097 obSat
|= MASKBIT(i
);
4101 } /* End the loop over all WhereLoops from outer-most down to inner-most */
4102 if( obSat
==obDone
) return (i8
)nOrderBy
;
4103 if( !isOrderDistinct
){
4104 for(i
=nOrderBy
-1; i
>0; i
--){
4105 Bitmask m
= ALWAYS(i
<BMS
) ? MASKBIT(i
) - 1 : 0;
4106 if( (obSat
&m
)==m
) return i
;
4115 ** If the WHERE_GROUPBY flag is set in the mask passed to sqlite3WhereBegin(),
4116 ** the planner assumes that the specified pOrderBy list is actually a GROUP
4117 ** BY clause - and so any order that groups rows as required satisfies the
4120 ** Normally, in this case it is not possible for the caller to determine
4121 ** whether or not the rows are really being delivered in sorted order, or
4122 ** just in some other order that provides the required grouping. However,
4123 ** if the WHERE_SORTBYGROUP flag is also passed to sqlite3WhereBegin(), then
4124 ** this function may be called on the returned WhereInfo object. It returns
4125 ** true if the rows really will be sorted in the specified order, or false
4128 ** For example, assuming:
4130 ** CREATE INDEX i1 ON t1(x, Y);
4134 ** SELECT * FROM t1 GROUP BY x,y ORDER BY x,y; -- IsSorted()==1
4135 ** SELECT * FROM t1 GROUP BY y,x ORDER BY y,x; -- IsSorted()==0
4137 int sqlite3WhereIsSorted(WhereInfo
*pWInfo
){
4138 assert( pWInfo
->wctrlFlags
& WHERE_GROUPBY
);
4139 assert( pWInfo
->wctrlFlags
& WHERE_SORTBYGROUP
);
4140 return pWInfo
->sorted
;
4143 #ifdef WHERETRACE_ENABLED
4144 /* For debugging use only: */
4145 static const char *wherePathName(WherePath
*pPath
, int nLoop
, WhereLoop
*pLast
){
4146 static char zName
[65];
4148 for(i
=0; i
<nLoop
; i
++){ zName
[i
] = pPath
->aLoop
[i
]->cId
; }
4149 if( pLast
) zName
[i
++] = pLast
->cId
;
4156 ** Return the cost of sorting nRow rows, assuming that the keys have
4157 ** nOrderby columns and that the first nSorted columns are already in
4160 static LogEst
whereSortingCost(
4166 /* TUNING: Estimated cost of a full external sort, where N is
4167 ** the number of rows to sort is:
4169 ** cost = (3.0 * N * log(N)).
4171 ** Or, if the order-by clause has X terms but only the last Y
4172 ** terms are out of order, then block-sorting will reduce the
4175 ** cost = (3.0 * N * log(N)) * (Y/X)
4177 ** The (Y/X) term is implemented using stack variable rScale
4180 LogEst rScale
, rSortCost
;
4181 assert( nOrderBy
>0 && 66==sqlite3LogEst(100) );
4182 rScale
= sqlite3LogEst((nOrderBy
-nSorted
)*100/nOrderBy
) - 66;
4183 rSortCost
= nRow
+ rScale
+ 16;
4185 /* Multiple by log(M) where M is the number of output rows.
4186 ** Use the LIMIT for M if it is smaller. Or if this sort is for
4187 ** a DISTINCT operator, M will be the number of distinct output
4188 ** rows, so fudge it downwards a bit.
4190 if( (pWInfo
->wctrlFlags
& WHERE_USE_LIMIT
)!=0 && pWInfo
->iLimit
<nRow
){
4191 nRow
= pWInfo
->iLimit
;
4192 }else if( (pWInfo
->wctrlFlags
& WHERE_WANT_DISTINCT
) ){
4193 /* TUNING: In the sort for a DISTINCT operator, assume that the DISTINCT
4194 ** reduces the number of output rows by a factor of 2 */
4195 if( nRow
>10 ){ nRow
-= 10; assert( 10==sqlite3LogEst(2) ); }
4197 rSortCost
+= estLog(nRow
);
4202 ** Given the list of WhereLoop objects at pWInfo->pLoops, this routine
4203 ** attempts to find the lowest cost path that visits each WhereLoop
4204 ** once. This path is then loaded into the pWInfo->a[].pWLoop fields.
4206 ** Assume that the total number of output rows that will need to be sorted
4207 ** will be nRowEst (in the 10*log2 representation). Or, ignore sorting
4208 ** costs if nRowEst==0.
4210 ** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation
4213 static int wherePathSolver(WhereInfo
*pWInfo
, LogEst nRowEst
){
4214 int mxChoice
; /* Maximum number of simultaneous paths tracked */
4215 int nLoop
; /* Number of terms in the join */
4216 Parse
*pParse
; /* Parsing context */
4217 sqlite3
*db
; /* The database connection */
4218 int iLoop
; /* Loop counter over the terms of the join */
4219 int ii
, jj
; /* Loop counters */
4220 int mxI
= 0; /* Index of next entry to replace */
4221 int nOrderBy
; /* Number of ORDER BY clause terms */
4222 LogEst mxCost
= 0; /* Maximum cost of a set of paths */
4223 LogEst mxUnsorted
= 0; /* Maximum unsorted cost of a set of path */
4224 int nTo
, nFrom
; /* Number of valid entries in aTo[] and aFrom[] */
4225 WherePath
*aFrom
; /* All nFrom paths at the previous level */
4226 WherePath
*aTo
; /* The nTo best paths at the current level */
4227 WherePath
*pFrom
; /* An element of aFrom[] that we are working on */
4228 WherePath
*pTo
; /* An element of aTo[] that we are working on */
4229 WhereLoop
*pWLoop
; /* One of the WhereLoop objects */
4230 WhereLoop
**pX
; /* Used to divy up the pSpace memory */
4231 LogEst
*aSortCost
= 0; /* Sorting and partial sorting costs */
4232 char *pSpace
; /* Temporary memory used by this routine */
4233 int nSpace
; /* Bytes of space allocated at pSpace */
4235 pParse
= pWInfo
->pParse
;
4237 nLoop
= pWInfo
->nLevel
;
4238 /* TUNING: For simple queries, only the best path is tracked.
4239 ** For 2-way joins, the 5 best paths are followed.
4240 ** For joins of 3 or more tables, track the 10 best paths */
4241 mxChoice
= (nLoop
<=1) ? 1 : (nLoop
==2 ? 5 : 10);
4242 assert( nLoop
<=pWInfo
->pTabList
->nSrc
);
4243 WHERETRACE(0x002, ("---- begin solver. (nRowEst=%d)\n", nRowEst
));
4245 /* If nRowEst is zero and there is an ORDER BY clause, ignore it. In this
4246 ** case the purpose of this call is to estimate the number of rows returned
4247 ** by the overall query. Once this estimate has been obtained, the caller
4248 ** will invoke this function a second time, passing the estimate as the
4249 ** nRowEst parameter. */
4250 if( pWInfo
->pOrderBy
==0 || nRowEst
==0 ){
4253 nOrderBy
= pWInfo
->pOrderBy
->nExpr
;
4256 /* Allocate and initialize space for aTo, aFrom and aSortCost[] */
4257 nSpace
= (sizeof(WherePath
)+sizeof(WhereLoop
*)*nLoop
)*mxChoice
*2;
4258 nSpace
+= sizeof(LogEst
) * nOrderBy
;
4259 pSpace
= sqlite3DbMallocRawNN(db
, nSpace
);
4260 if( pSpace
==0 ) return SQLITE_NOMEM_BKPT
;
4261 aTo
= (WherePath
*)pSpace
;
4262 aFrom
= aTo
+mxChoice
;
4263 memset(aFrom
, 0, sizeof(aFrom
[0]));
4264 pX
= (WhereLoop
**)(aFrom
+mxChoice
);
4265 for(ii
=mxChoice
*2, pFrom
=aTo
; ii
>0; ii
--, pFrom
++, pX
+= nLoop
){
4269 /* If there is an ORDER BY clause and it is not being ignored, set up
4270 ** space for the aSortCost[] array. Each element of the aSortCost array
4271 ** is either zero - meaning it has not yet been initialized - or the
4272 ** cost of sorting nRowEst rows of data where the first X terms of
4273 ** the ORDER BY clause are already in order, where X is the array
4275 aSortCost
= (LogEst
*)pX
;
4276 memset(aSortCost
, 0, sizeof(LogEst
) * nOrderBy
);
4278 assert( aSortCost
==0 || &pSpace
[nSpace
]==(char*)&aSortCost
[nOrderBy
] );
4279 assert( aSortCost
!=0 || &pSpace
[nSpace
]==(char*)pX
);
4281 /* Seed the search with a single WherePath containing zero WhereLoops.
4283 ** TUNING: Do not let the number of iterations go above 28. If the cost
4284 ** of computing an automatic index is not paid back within the first 28
4285 ** rows, then do not use the automatic index. */
4286 aFrom
[0].nRow
= MIN(pParse
->nQueryLoop
, 48); assert( 48==sqlite3LogEst(28) );
4288 assert( aFrom
[0].isOrdered
==0 );
4290 /* If nLoop is zero, then there are no FROM terms in the query. Since
4291 ** in this case the query may return a maximum of one row, the results
4292 ** are already in the requested order. Set isOrdered to nOrderBy to
4293 ** indicate this. Or, if nLoop is greater than zero, set isOrdered to
4294 ** -1, indicating that the result set may or may not be ordered,
4295 ** depending on the loops added to the current plan. */
4296 aFrom
[0].isOrdered
= nLoop
>0 ? -1 : nOrderBy
;
4299 /* Compute successively longer WherePaths using the previous generation
4300 ** of WherePaths as the basis for the next. Keep track of the mxChoice
4301 ** best paths at each generation */
4302 for(iLoop
=0; iLoop
<nLoop
; iLoop
++){
4304 for(ii
=0, pFrom
=aFrom
; ii
<nFrom
; ii
++, pFrom
++){
4305 for(pWLoop
=pWInfo
->pLoops
; pWLoop
; pWLoop
=pWLoop
->pNextLoop
){
4306 LogEst nOut
; /* Rows visited by (pFrom+pWLoop) */
4307 LogEst rCost
; /* Cost of path (pFrom+pWLoop) */
4308 LogEst rUnsorted
; /* Unsorted cost of (pFrom+pWLoop) */
4309 i8 isOrdered
= pFrom
->isOrdered
; /* isOrdered for (pFrom+pWLoop) */
4310 Bitmask maskNew
; /* Mask of src visited by (..) */
4311 Bitmask revMask
= 0; /* Mask of rev-order loops for (..) */
4313 if( (pWLoop
->prereq
& ~pFrom
->maskLoop
)!=0 ) continue;
4314 if( (pWLoop
->maskSelf
& pFrom
->maskLoop
)!=0 ) continue;
4315 if( (pWLoop
->wsFlags
& WHERE_AUTO_INDEX
)!=0 && pFrom
->nRow
<3 ){
4316 /* Do not use an automatic index if the this loop is expected
4317 ** to run less than 1.25 times. It is tempting to also exclude
4318 ** automatic index usage on an outer loop, but sometimes an automatic
4319 ** index is useful in the outer loop of a correlated subquery. */
4320 assert( 10==sqlite3LogEst(2) );
4324 /* At this point, pWLoop is a candidate to be the next loop.
4325 ** Compute its cost */
4326 rUnsorted
= sqlite3LogEstAdd(pWLoop
->rSetup
,pWLoop
->rRun
+ pFrom
->nRow
);
4327 rUnsorted
= sqlite3LogEstAdd(rUnsorted
, pFrom
->rUnsorted
);
4328 nOut
= pFrom
->nRow
+ pWLoop
->nOut
;
4329 maskNew
= pFrom
->maskLoop
| pWLoop
->maskSelf
;
4331 isOrdered
= wherePathSatisfiesOrderBy(pWInfo
,
4332 pWInfo
->pOrderBy
, pFrom
, pWInfo
->wctrlFlags
,
4333 iLoop
, pWLoop
, &revMask
);
4335 revMask
= pFrom
->revLoop
;
4337 if( isOrdered
>=0 && isOrdered
<nOrderBy
){
4338 if( aSortCost
[isOrdered
]==0 ){
4339 aSortCost
[isOrdered
] = whereSortingCost(
4340 pWInfo
, nRowEst
, nOrderBy
, isOrdered
4343 /* TUNING: Add a small extra penalty (5) to sorting as an
4344 ** extra encouragment to the query planner to select a plan
4345 ** where the rows emerge in the correct order without any sorting
4347 rCost
= sqlite3LogEstAdd(rUnsorted
, aSortCost
[isOrdered
]) + 5;
4350 ("---- sort cost=%-3d (%d/%d) increases cost %3d to %-3d\n",
4351 aSortCost
[isOrdered
], (nOrderBy
-isOrdered
), nOrderBy
,
4355 rUnsorted
-= 2; /* TUNING: Slight bias in favor of no-sort plans */
4358 /* Check to see if pWLoop should be added to the set of
4359 ** mxChoice best-so-far paths.
4361 ** First look for an existing path among best-so-far paths
4362 ** that covers the same set of loops and has the same isOrdered
4363 ** setting as the current path candidate.
4365 ** The term "((pTo->isOrdered^isOrdered)&0x80)==0" is equivalent
4366 ** to (pTo->isOrdered==(-1))==(isOrdered==(-1))" for the range
4367 ** of legal values for isOrdered, -1..64.
4369 for(jj
=0, pTo
=aTo
; jj
<nTo
; jj
++, pTo
++){
4370 if( pTo
->maskLoop
==maskNew
4371 && ((pTo
->isOrdered
^isOrdered
)&0x80)==0
4373 testcase( jj
==nTo
-1 );
4378 /* None of the existing best-so-far paths match the candidate. */
4380 && (rCost
>mxCost
|| (rCost
==mxCost
&& rUnsorted
>=mxUnsorted
))
4382 /* The current candidate is no better than any of the mxChoice
4383 ** paths currently in the best-so-far buffer. So discard
4384 ** this candidate as not viable. */
4385 #ifdef WHERETRACE_ENABLED /* 0x4 */
4386 if( sqlite3WhereTrace
&0x4 ){
4387 sqlite3DebugPrintf("Skip %s cost=%-3d,%3d,%3d order=%c\n",
4388 wherePathName(pFrom
, iLoop
, pWLoop
), rCost
, nOut
, rUnsorted
,
4389 isOrdered
>=0 ? isOrdered
+'0' : '?');
4394 /* If we reach this points it means that the new candidate path
4395 ** needs to be added to the set of best-so-far paths. */
4397 /* Increase the size of the aTo set by one */
4400 /* New path replaces the prior worst to keep count below mxChoice */
4404 #ifdef WHERETRACE_ENABLED /* 0x4 */
4405 if( sqlite3WhereTrace
&0x4 ){
4406 sqlite3DebugPrintf("New %s cost=%-3d,%3d,%3d order=%c\n",
4407 wherePathName(pFrom
, iLoop
, pWLoop
), rCost
, nOut
, rUnsorted
,
4408 isOrdered
>=0 ? isOrdered
+'0' : '?');
4412 /* Control reaches here if best-so-far path pTo=aTo[jj] covers the
4413 ** same set of loops and has the same isOrdered setting as the
4414 ** candidate path. Check to see if the candidate should replace
4415 ** pTo or if the candidate should be skipped.
4417 ** The conditional is an expanded vector comparison equivalent to:
4418 ** (pTo->rCost,pTo->nRow,pTo->rUnsorted) <= (rCost,nOut,rUnsorted)
4420 if( pTo
->rCost
<rCost
4421 || (pTo
->rCost
==rCost
4423 || (pTo
->nRow
==nOut
&& pTo
->rUnsorted
<=rUnsorted
)
4427 #ifdef WHERETRACE_ENABLED /* 0x4 */
4428 if( sqlite3WhereTrace
&0x4 ){
4430 "Skip %s cost=%-3d,%3d,%3d order=%c",
4431 wherePathName(pFrom
, iLoop
, pWLoop
), rCost
, nOut
, rUnsorted
,
4432 isOrdered
>=0 ? isOrdered
+'0' : '?');
4433 sqlite3DebugPrintf(" vs %s cost=%-3d,%3d,%3d order=%c\n",
4434 wherePathName(pTo
, iLoop
+1, 0), pTo
->rCost
, pTo
->nRow
,
4435 pTo
->rUnsorted
, pTo
->isOrdered
>=0 ? pTo
->isOrdered
+'0' : '?');
4438 /* Discard the candidate path from further consideration */
4439 testcase( pTo
->rCost
==rCost
);
4442 testcase( pTo
->rCost
==rCost
+1 );
4443 /* Control reaches here if the candidate path is better than the
4444 ** pTo path. Replace pTo with the candidate. */
4445 #ifdef WHERETRACE_ENABLED /* 0x4 */
4446 if( sqlite3WhereTrace
&0x4 ){
4448 "Update %s cost=%-3d,%3d,%3d order=%c",
4449 wherePathName(pFrom
, iLoop
, pWLoop
), rCost
, nOut
, rUnsorted
,
4450 isOrdered
>=0 ? isOrdered
+'0' : '?');
4451 sqlite3DebugPrintf(" was %s cost=%-3d,%3d,%3d order=%c\n",
4452 wherePathName(pTo
, iLoop
+1, 0), pTo
->rCost
, pTo
->nRow
,
4453 pTo
->rUnsorted
, pTo
->isOrdered
>=0 ? pTo
->isOrdered
+'0' : '?');
4457 /* pWLoop is a winner. Add it to the set of best so far */
4458 pTo
->maskLoop
= pFrom
->maskLoop
| pWLoop
->maskSelf
;
4459 pTo
->revLoop
= revMask
;
4462 pTo
->rUnsorted
= rUnsorted
;
4463 pTo
->isOrdered
= isOrdered
;
4464 memcpy(pTo
->aLoop
, pFrom
->aLoop
, sizeof(WhereLoop
*)*iLoop
);
4465 pTo
->aLoop
[iLoop
] = pWLoop
;
4466 if( nTo
>=mxChoice
){
4468 mxCost
= aTo
[0].rCost
;
4469 mxUnsorted
= aTo
[0].nRow
;
4470 for(jj
=1, pTo
=&aTo
[1]; jj
<mxChoice
; jj
++, pTo
++){
4471 if( pTo
->rCost
>mxCost
4472 || (pTo
->rCost
==mxCost
&& pTo
->rUnsorted
>mxUnsorted
)
4474 mxCost
= pTo
->rCost
;
4475 mxUnsorted
= pTo
->rUnsorted
;
4483 #ifdef WHERETRACE_ENABLED /* >=2 */
4484 if( sqlite3WhereTrace
& 0x02 ){
4485 sqlite3DebugPrintf("---- after round %d ----\n", iLoop
);
4486 for(ii
=0, pTo
=aTo
; ii
<nTo
; ii
++, pTo
++){
4487 sqlite3DebugPrintf(" %s cost=%-3d nrow=%-3d order=%c",
4488 wherePathName(pTo
, iLoop
+1, 0), pTo
->rCost
, pTo
->nRow
,
4489 pTo
->isOrdered
>=0 ? (pTo
->isOrdered
+'0') : '?');
4490 if( pTo
->isOrdered
>0 ){
4491 sqlite3DebugPrintf(" rev=0x%llx\n", pTo
->revLoop
);
4493 sqlite3DebugPrintf("\n");
4499 /* Swap the roles of aFrom and aTo for the next generation */
4507 sqlite3ErrorMsg(pParse
, "no query solution");
4508 sqlite3DbFreeNN(db
, pSpace
);
4509 return SQLITE_ERROR
;
4512 /* Find the lowest cost path. pFrom will be left pointing to that path */
4514 for(ii
=1; ii
<nFrom
; ii
++){
4515 if( pFrom
->rCost
>aFrom
[ii
].rCost
) pFrom
= &aFrom
[ii
];
4517 assert( pWInfo
->nLevel
==nLoop
);
4518 /* Load the lowest cost path into pWInfo */
4519 for(iLoop
=0; iLoop
<nLoop
; iLoop
++){
4520 WhereLevel
*pLevel
= pWInfo
->a
+ iLoop
;
4521 pLevel
->pWLoop
= pWLoop
= pFrom
->aLoop
[iLoop
];
4522 pLevel
->iFrom
= pWLoop
->iTab
;
4523 pLevel
->iTabCur
= pWInfo
->pTabList
->a
[pLevel
->iFrom
].iCursor
;
4525 if( (pWInfo
->wctrlFlags
& WHERE_WANT_DISTINCT
)!=0
4526 && (pWInfo
->wctrlFlags
& WHERE_DISTINCTBY
)==0
4527 && pWInfo
->eDistinct
==WHERE_DISTINCT_NOOP
4531 int rc
= wherePathSatisfiesOrderBy(pWInfo
, pWInfo
->pResultSet
, pFrom
,
4532 WHERE_DISTINCTBY
, nLoop
-1, pFrom
->aLoop
[nLoop
-1], ¬Used
);
4533 if( rc
==pWInfo
->pResultSet
->nExpr
){
4534 pWInfo
->eDistinct
= WHERE_DISTINCT_ORDERED
;
4537 pWInfo
->bOrderedInnerLoop
= 0;
4538 if( pWInfo
->pOrderBy
){
4539 if( pWInfo
->wctrlFlags
& WHERE_DISTINCTBY
){
4540 if( pFrom
->isOrdered
==pWInfo
->pOrderBy
->nExpr
){
4541 pWInfo
->eDistinct
= WHERE_DISTINCT_ORDERED
;
4544 pWInfo
->nOBSat
= pFrom
->isOrdered
;
4545 pWInfo
->revMask
= pFrom
->revLoop
;
4546 if( pWInfo
->nOBSat
<=0 ){
4549 u32 wsFlags
= pFrom
->aLoop
[nLoop
-1]->wsFlags
;
4550 if( (wsFlags
& WHERE_ONEROW
)==0
4551 && (wsFlags
&(WHERE_IPK
|WHERE_COLUMN_IN
))!=(WHERE_IPK
|WHERE_COLUMN_IN
)
4554 int rc
= wherePathSatisfiesOrderBy(pWInfo
, pWInfo
->pOrderBy
, pFrom
,
4555 WHERE_ORDERBY_LIMIT
, nLoop
-1, pFrom
->aLoop
[nLoop
-1], &m
);
4556 testcase( wsFlags
& WHERE_IPK
);
4557 testcase( wsFlags
& WHERE_COLUMN_IN
);
4558 if( rc
==pWInfo
->pOrderBy
->nExpr
){
4559 pWInfo
->bOrderedInnerLoop
= 1;
4560 pWInfo
->revMask
= m
;
4565 && pWInfo
->nOBSat
==1
4566 && (pWInfo
->wctrlFlags
& (WHERE_ORDERBY_MIN
|WHERE_ORDERBY_MAX
))!=0
4568 pWInfo
->bOrderedInnerLoop
= 1;
4571 if( (pWInfo
->wctrlFlags
& WHERE_SORTBYGROUP
)
4572 && pWInfo
->nOBSat
==pWInfo
->pOrderBy
->nExpr
&& nLoop
>0
4574 Bitmask revMask
= 0;
4575 int nOrder
= wherePathSatisfiesOrderBy(pWInfo
, pWInfo
->pOrderBy
,
4576 pFrom
, 0, nLoop
-1, pFrom
->aLoop
[nLoop
-1], &revMask
4578 assert( pWInfo
->sorted
==0 );
4579 if( nOrder
==pWInfo
->pOrderBy
->nExpr
){
4581 pWInfo
->revMask
= revMask
;
4587 pWInfo
->nRowOut
= pFrom
->nRow
;
4589 /* Free temporary memory and return success */
4590 sqlite3DbFreeNN(db
, pSpace
);
4595 ** Most queries use only a single table (they are not joins) and have
4596 ** simple == constraints against indexed fields. This routine attempts
4597 ** to plan those simple cases using much less ceremony than the
4598 ** general-purpose query planner, and thereby yield faster sqlite3_prepare()
4599 ** times for the common case.
4601 ** Return non-zero on success, if this query can be handled by this
4602 ** no-frills query planner. Return zero if this query needs the
4603 ** general-purpose query planner.
4605 static int whereShortCut(WhereLoopBuilder
*pBuilder
){
4617 pWInfo
= pBuilder
->pWInfo
;
4618 if( pWInfo
->wctrlFlags
& WHERE_OR_SUBCLAUSE
) return 0;
4619 assert( pWInfo
->pTabList
->nSrc
>=1 );
4620 pItem
= pWInfo
->pTabList
->a
;
4622 if( IsVirtual(pTab
) ) return 0;
4623 if( pItem
->fg
.isIndexedBy
) return 0;
4624 iCur
= pItem
->iCursor
;
4626 pLoop
= pBuilder
->pNew
;
4629 pTerm
= whereScanInit(&scan
, pWC
, iCur
, -1, WO_EQ
|WO_IS
, 0);
4630 while( pTerm
&& pTerm
->prereqRight
) pTerm
= whereScanNext(&scan
);
4632 testcase( pTerm
->eOperator
& WO_IS
);
4633 pLoop
->wsFlags
= WHERE_COLUMN_EQ
|WHERE_IPK
|WHERE_ONEROW
;
4634 pLoop
->aLTerm
[0] = pTerm
;
4636 pLoop
->u
.btree
.nEq
= 1;
4637 /* TUNING: Cost of a rowid lookup is 10 */
4638 pLoop
->rRun
= 33; /* 33==sqlite3LogEst(10) */
4640 for(pIdx
=pTab
->pIndex
; pIdx
; pIdx
=pIdx
->pNext
){
4642 assert( pLoop
->aLTermSpace
==pLoop
->aLTerm
);
4643 if( !IsUniqueIndex(pIdx
)
4644 || pIdx
->pPartIdxWhere
!=0
4645 || pIdx
->nKeyCol
>ArraySize(pLoop
->aLTermSpace
)
4647 opMask
= pIdx
->uniqNotNull
? (WO_EQ
|WO_IS
) : WO_EQ
;
4648 for(j
=0; j
<pIdx
->nKeyCol
; j
++){
4649 pTerm
= whereScanInit(&scan
, pWC
, iCur
, j
, opMask
, pIdx
);
4650 while( pTerm
&& pTerm
->prereqRight
) pTerm
= whereScanNext(&scan
);
4651 if( pTerm
==0 ) break;
4652 testcase( pTerm
->eOperator
& WO_IS
);
4653 pLoop
->aLTerm
[j
] = pTerm
;
4655 if( j
!=pIdx
->nKeyCol
) continue;
4656 pLoop
->wsFlags
= WHERE_COLUMN_EQ
|WHERE_ONEROW
|WHERE_INDEXED
;
4657 if( pIdx
->isCovering
|| (pItem
->colUsed
& pIdx
->colNotIdxed
)==0 ){
4658 pLoop
->wsFlags
|= WHERE_IDX_ONLY
;
4661 pLoop
->u
.btree
.nEq
= j
;
4662 pLoop
->u
.btree
.pIndex
= pIdx
;
4663 /* TUNING: Cost of a unique index lookup is 15 */
4664 pLoop
->rRun
= 39; /* 39==sqlite3LogEst(15) */
4668 if( pLoop
->wsFlags
){
4669 pLoop
->nOut
= (LogEst
)1;
4670 pWInfo
->a
[0].pWLoop
= pLoop
;
4671 assert( pWInfo
->sMaskSet
.n
==1 && iCur
==pWInfo
->sMaskSet
.ix
[0] );
4672 pLoop
->maskSelf
= 1; /* sqlite3WhereGetMask(&pWInfo->sMaskSet, iCur); */
4673 pWInfo
->a
[0].iTabCur
= iCur
;
4674 pWInfo
->nRowOut
= 1;
4675 if( pWInfo
->pOrderBy
) pWInfo
->nOBSat
= pWInfo
->pOrderBy
->nExpr
;
4676 if( pWInfo
->wctrlFlags
& WHERE_WANT_DISTINCT
){
4677 pWInfo
->eDistinct
= WHERE_DISTINCT_UNIQUE
;
4679 if( scan
.iEquiv
>1 ) pLoop
->wsFlags
|= WHERE_TRANSCONS
;
4683 #ifdef WHERETRACE_ENABLED
4684 if( sqlite3WhereTrace
){
4685 sqlite3DebugPrintf("whereShortCut() used to compute solution\n");
4694 ** Helper function for exprIsDeterministic().
4696 static int exprNodeIsDeterministic(Walker
*pWalker
, Expr
*pExpr
){
4697 if( pExpr
->op
==TK_FUNCTION
&& ExprHasProperty(pExpr
, EP_ConstFunc
)==0 ){
4701 return WRC_Continue
;
4705 ** Return true if the expression contains no non-deterministic SQL
4706 ** functions. Do not consider non-deterministic SQL functions that are
4707 ** part of sub-select statements.
4709 static int exprIsDeterministic(Expr
*p
){
4711 memset(&w
, 0, sizeof(w
));
4713 w
.xExprCallback
= exprNodeIsDeterministic
;
4714 w
.xSelectCallback
= sqlite3SelectWalkFail
;
4715 sqlite3WalkExpr(&w
, p
);
4720 #ifdef WHERETRACE_ENABLED
4722 ** Display all WhereLoops in pWInfo
4724 static void showAllWhereLoops(WhereInfo
*pWInfo
, WhereClause
*pWC
){
4725 if( sqlite3WhereTrace
){ /* Display all of the WhereLoop objects */
4728 static const char zLabel
[] = "0123456789abcdefghijklmnopqrstuvwyxz"
4729 "ABCDEFGHIJKLMNOPQRSTUVWYXZ";
4730 for(p
=pWInfo
->pLoops
, i
=0; p
; p
=p
->pNextLoop
, i
++){
4731 p
->cId
= zLabel
[i
%(sizeof(zLabel
)-1)];
4732 sqlite3WhereLoopPrint(p
, pWC
);
4736 # define WHERETRACE_ALL_LOOPS(W,C) showAllWhereLoops(W,C)
4738 # define WHERETRACE_ALL_LOOPS(W,C)
4742 ** Generate the beginning of the loop used for WHERE clause processing.
4743 ** The return value is a pointer to an opaque structure that contains
4744 ** information needed to terminate the loop. Later, the calling routine
4745 ** should invoke sqlite3WhereEnd() with the return value of this function
4746 ** in order to complete the WHERE clause processing.
4748 ** If an error occurs, this routine returns NULL.
4750 ** The basic idea is to do a nested loop, one loop for each table in
4751 ** the FROM clause of a select. (INSERT and UPDATE statements are the
4752 ** same as a SELECT with only a single table in the FROM clause.) For
4753 ** example, if the SQL is this:
4755 ** SELECT * FROM t1, t2, t3 WHERE ...;
4757 ** Then the code generated is conceptually like the following:
4759 ** foreach row1 in t1 do \ Code generated
4760 ** foreach row2 in t2 do |-- by sqlite3WhereBegin()
4761 ** foreach row3 in t3 do /
4763 ** end \ Code generated
4764 ** end |-- by sqlite3WhereEnd()
4767 ** Note that the loops might not be nested in the order in which they
4768 ** appear in the FROM clause if a different order is better able to make
4769 ** use of indices. Note also that when the IN operator appears in
4770 ** the WHERE clause, it might result in additional nested loops for
4771 ** scanning through all values on the right-hand side of the IN.
4773 ** There are Btree cursors associated with each table. t1 uses cursor
4774 ** number pTabList->a[0].iCursor. t2 uses the cursor pTabList->a[1].iCursor.
4775 ** And so forth. This routine generates code to open those VDBE cursors
4776 ** and sqlite3WhereEnd() generates the code to close them.
4778 ** The code that sqlite3WhereBegin() generates leaves the cursors named
4779 ** in pTabList pointing at their appropriate entries. The [...] code
4780 ** can use OP_Column and OP_Rowid opcodes on these cursors to extract
4781 ** data from the various tables of the loop.
4783 ** If the WHERE clause is empty, the foreach loops must each scan their
4784 ** entire tables. Thus a three-way join is an O(N^3) operation. But if
4785 ** the tables have indices and there are terms in the WHERE clause that
4786 ** refer to those indices, a complete table scan can be avoided and the
4787 ** code will run much faster. Most of the work of this routine is checking
4788 ** to see if there are indices that can be used to speed up the loop.
4790 ** Terms of the WHERE clause are also used to limit which rows actually
4791 ** make it to the "..." in the middle of the loop. After each "foreach",
4792 ** terms of the WHERE clause that use only terms in that loop and outer
4793 ** loops are evaluated and if false a jump is made around all subsequent
4794 ** inner loops (or around the "..." if the test occurs within the inner-
4799 ** An outer join of tables t1 and t2 is conceptally coded as follows:
4801 ** foreach row1 in t1 do
4803 ** foreach row2 in t2 do
4809 ** move the row2 cursor to a null row
4814 ** ORDER BY CLAUSE PROCESSING
4816 ** pOrderBy is a pointer to the ORDER BY clause (or the GROUP BY clause
4817 ** if the WHERE_GROUPBY flag is set in wctrlFlags) of a SELECT statement
4818 ** if there is one. If there is no ORDER BY clause or if this routine
4819 ** is called from an UPDATE or DELETE statement, then pOrderBy is NULL.
4821 ** The iIdxCur parameter is the cursor number of an index. If
4822 ** WHERE_OR_SUBCLAUSE is set, iIdxCur is the cursor number of an index
4823 ** to use for OR clause processing. The WHERE clause should use this
4824 ** specific cursor. If WHERE_ONEPASS_DESIRED is set, then iIdxCur is
4825 ** the first cursor in an array of cursors for all indices. iIdxCur should
4826 ** be used to compute the appropriate cursor depending on which index is
4829 WhereInfo
*sqlite3WhereBegin(
4830 Parse
*pParse
, /* The parser context */
4831 SrcList
*pTabList
, /* FROM clause: A list of all tables to be scanned */
4832 Expr
*pWhere
, /* The WHERE clause */
4833 ExprList
*pOrderBy
, /* An ORDER BY (or GROUP BY) clause, or NULL */
4834 ExprList
*pResultSet
, /* Query result set. Req'd for DISTINCT */
4835 u16 wctrlFlags
, /* The WHERE_* flags defined in sqliteInt.h */
4836 int iAuxArg
/* If WHERE_OR_SUBCLAUSE is set, index cursor number
4837 ** If WHERE_USE_LIMIT, then the limit amount */
4839 int nByteWInfo
; /* Num. bytes allocated for WhereInfo struct */
4840 int nTabList
; /* Number of elements in pTabList */
4841 WhereInfo
*pWInfo
; /* Will become the return value of this function */
4842 Vdbe
*v
= pParse
->pVdbe
; /* The virtual database engine */
4843 Bitmask notReady
; /* Cursors that are not yet positioned */
4844 WhereLoopBuilder sWLB
; /* The WhereLoop builder */
4845 WhereMaskSet
*pMaskSet
; /* The expression mask set */
4846 WhereLevel
*pLevel
; /* A single level in pWInfo->a[] */
4847 WhereLoop
*pLoop
; /* Pointer to a single WhereLoop object */
4848 int ii
; /* Loop counter */
4849 sqlite3
*db
; /* Database connection */
4850 int rc
; /* Return code */
4851 u8 bFordelete
= 0; /* OPFLAG_FORDELETE or zero, as appropriate */
4853 assert( (wctrlFlags
& WHERE_ONEPASS_MULTIROW
)==0 || (
4854 (wctrlFlags
& WHERE_ONEPASS_DESIRED
)!=0
4855 && (wctrlFlags
& WHERE_OR_SUBCLAUSE
)==0
4858 /* Only one of WHERE_OR_SUBCLAUSE or WHERE_USE_LIMIT */
4859 assert( (wctrlFlags
& WHERE_OR_SUBCLAUSE
)==0
4860 || (wctrlFlags
& WHERE_USE_LIMIT
)==0 );
4862 /* Variable initialization */
4864 memset(&sWLB
, 0, sizeof(sWLB
));
4866 /* An ORDER/GROUP BY clause of more than 63 terms cannot be optimized */
4867 testcase( pOrderBy
&& pOrderBy
->nExpr
==BMS
-1 );
4868 if( pOrderBy
&& pOrderBy
->nExpr
>=BMS
) pOrderBy
= 0;
4869 sWLB
.pOrderBy
= pOrderBy
;
4871 /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via
4872 ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */
4873 if( OptimizationDisabled(db
, SQLITE_DistinctOpt
) ){
4874 wctrlFlags
&= ~WHERE_WANT_DISTINCT
;
4877 /* The number of tables in the FROM clause is limited by the number of
4878 ** bits in a Bitmask
4880 testcase( pTabList
->nSrc
==BMS
);
4881 if( pTabList
->nSrc
>BMS
){
4882 sqlite3ErrorMsg(pParse
, "at most %d tables in a join", BMS
);
4886 /* This function normally generates a nested loop for all tables in
4887 ** pTabList. But if the WHERE_OR_SUBCLAUSE flag is set, then we should
4888 ** only generate code for the first table in pTabList and assume that
4889 ** any cursors associated with subsequent tables are uninitialized.
4891 nTabList
= (wctrlFlags
& WHERE_OR_SUBCLAUSE
) ? 1 : pTabList
->nSrc
;
4893 /* Allocate and initialize the WhereInfo structure that will become the
4894 ** return value. A single allocation is used to store the WhereInfo
4895 ** struct, the contents of WhereInfo.a[], the WhereClause structure
4896 ** and the WhereMaskSet structure. Since WhereClause contains an 8-byte
4897 ** field (type Bitmask) it must be aligned on an 8-byte boundary on
4898 ** some architectures. Hence the ROUND8() below.
4900 nByteWInfo
= ROUND8(sizeof(WhereInfo
)+(nTabList
-1)*sizeof(WhereLevel
));
4901 pWInfo
= sqlite3DbMallocRawNN(db
, nByteWInfo
+ sizeof(WhereLoop
));
4902 if( db
->mallocFailed
){
4903 sqlite3DbFree(db
, pWInfo
);
4905 goto whereBeginError
;
4907 pWInfo
->pParse
= pParse
;
4908 pWInfo
->pTabList
= pTabList
;
4909 pWInfo
->pOrderBy
= pOrderBy
;
4910 pWInfo
->pWhere
= pWhere
;
4911 pWInfo
->pResultSet
= pResultSet
;
4912 pWInfo
->aiCurOnePass
[0] = pWInfo
->aiCurOnePass
[1] = -1;
4913 pWInfo
->nLevel
= nTabList
;
4914 pWInfo
->iBreak
= pWInfo
->iContinue
= sqlite3VdbeMakeLabel(pParse
);
4915 pWInfo
->wctrlFlags
= wctrlFlags
;
4916 pWInfo
->iLimit
= iAuxArg
;
4917 pWInfo
->savedNQueryLoop
= pParse
->nQueryLoop
;
4918 memset(&pWInfo
->nOBSat
, 0,
4919 offsetof(WhereInfo
,sWC
) - offsetof(WhereInfo
,nOBSat
));
4920 memset(&pWInfo
->a
[0], 0, sizeof(WhereLoop
)+nTabList
*sizeof(WhereLevel
));
4921 assert( pWInfo
->eOnePass
==ONEPASS_OFF
); /* ONEPASS defaults to OFF */
4922 pMaskSet
= &pWInfo
->sMaskSet
;
4923 sWLB
.pWInfo
= pWInfo
;
4924 sWLB
.pWC
= &pWInfo
->sWC
;
4925 sWLB
.pNew
= (WhereLoop
*)(((char*)pWInfo
)+nByteWInfo
);
4926 assert( EIGHT_BYTE_ALIGNMENT(sWLB
.pNew
) );
4927 whereLoopInit(sWLB
.pNew
);
4929 sWLB
.pNew
->cId
= '*';
4932 /* Split the WHERE clause into separate subexpressions where each
4933 ** subexpression is separated by an AND operator.
4935 initMaskSet(pMaskSet
);
4936 sqlite3WhereClauseInit(&pWInfo
->sWC
, pWInfo
);
4937 sqlite3WhereSplit(&pWInfo
->sWC
, pWhere
, TK_AND
);
4939 /* Special case: No FROM clause
4942 if( pOrderBy
) pWInfo
->nOBSat
= pOrderBy
->nExpr
;
4943 if( wctrlFlags
& WHERE_WANT_DISTINCT
){
4944 pWInfo
->eDistinct
= WHERE_DISTINCT_UNIQUE
;
4946 ExplainQueryPlan((pParse
, 0, "SCAN CONSTANT ROW"));
4948 /* Assign a bit from the bitmask to every term in the FROM clause.
4950 ** The N-th term of the FROM clause is assigned a bitmask of 1<<N.
4952 ** The rule of the previous sentence ensures thta if X is the bitmask for
4953 ** a table T, then X-1 is the bitmask for all other tables to the left of T.
4954 ** Knowing the bitmask for all tables to the left of a left join is
4955 ** important. Ticket #3015.
4957 ** Note that bitmasks are created for all pTabList->nSrc tables in
4958 ** pTabList, not just the first nTabList tables. nTabList is normally
4959 ** equal to pTabList->nSrc but might be shortened to 1 if the
4960 ** WHERE_OR_SUBCLAUSE flag is set.
4964 createMask(pMaskSet
, pTabList
->a
[ii
].iCursor
);
4965 sqlite3WhereTabFuncArgs(pParse
, &pTabList
->a
[ii
], &pWInfo
->sWC
);
4966 }while( (++ii
)<pTabList
->nSrc
);
4970 for(ii
=0; ii
<pTabList
->nSrc
; ii
++){
4971 Bitmask m
= sqlite3WhereGetMask(pMaskSet
, pTabList
->a
[ii
].iCursor
);
4979 /* Analyze all of the subexpressions. */
4980 sqlite3WhereExprAnalyze(pTabList
, &pWInfo
->sWC
);
4981 if( db
->mallocFailed
) goto whereBeginError
;
4983 /* Special case: WHERE terms that do not refer to any tables in the join
4984 ** (constant expressions). Evaluate each such term, and jump over all the
4985 ** generated code if the result is not true.
4987 ** Do not do this if the expression contains non-deterministic functions
4988 ** that are not within a sub-select. This is not strictly required, but
4989 ** preserves SQLite's legacy behaviour in the following two cases:
4991 ** FROM ... WHERE random()>0; -- eval random() once per row
4992 ** FROM ... WHERE (SELECT random())>0; -- eval random() once overall
4994 for(ii
=0; ii
<sWLB
.pWC
->nTerm
; ii
++){
4995 WhereTerm
*pT
= &sWLB
.pWC
->a
[ii
];
4996 if( pT
->wtFlags
& TERM_VIRTUAL
) continue;
4997 if( pT
->prereqAll
==0 && (nTabList
==0 || exprIsDeterministic(pT
->pExpr
)) ){
4998 sqlite3ExprIfFalse(pParse
, pT
->pExpr
, pWInfo
->iBreak
, SQLITE_JUMPIFNULL
);
4999 pT
->wtFlags
|= TERM_CODED
;
5003 if( wctrlFlags
& WHERE_WANT_DISTINCT
){
5004 if( isDistinctRedundant(pParse
, pTabList
, &pWInfo
->sWC
, pResultSet
) ){
5005 /* The DISTINCT marking is pointless. Ignore it. */
5006 pWInfo
->eDistinct
= WHERE_DISTINCT_UNIQUE
;
5007 }else if( pOrderBy
==0 ){
5008 /* Try to ORDER BY the result set to make distinct processing easier */
5009 pWInfo
->wctrlFlags
|= WHERE_DISTINCTBY
;
5010 pWInfo
->pOrderBy
= pResultSet
;
5014 /* Construct the WhereLoop objects */
5015 #if defined(WHERETRACE_ENABLED)
5016 if( sqlite3WhereTrace
& 0xffff ){
5017 sqlite3DebugPrintf("*** Optimizer Start *** (wctrlFlags: 0x%x",wctrlFlags
);
5018 if( wctrlFlags
& WHERE_USE_LIMIT
){
5019 sqlite3DebugPrintf(", limit: %d", iAuxArg
);
5021 sqlite3DebugPrintf(")\n");
5022 if( sqlite3WhereTrace
& 0x100 ){
5024 memset(&sSelect
, 0, sizeof(sSelect
));
5025 sSelect
.selFlags
= SF_WhereBegin
;
5026 sSelect
.pSrc
= pTabList
;
5027 sSelect
.pWhere
= pWhere
;
5028 sSelect
.pOrderBy
= pOrderBy
;
5029 sSelect
.pEList
= pResultSet
;
5030 sqlite3TreeViewSelect(0, &sSelect
, 0);
5033 if( sqlite3WhereTrace
& 0x100 ){ /* Display all terms of the WHERE clause */
5034 sqlite3DebugPrintf("---- WHERE clause at start of analysis:\n");
5035 sqlite3WhereClausePrint(sWLB
.pWC
);
5039 if( nTabList
!=1 || whereShortCut(&sWLB
)==0 ){
5040 rc
= whereLoopAddAll(&sWLB
);
5041 if( rc
) goto whereBeginError
;
5043 #ifdef SQLITE_ENABLE_STAT4
5044 /* If one or more WhereTerm.truthProb values were used in estimating
5045 ** loop parameters, but then those truthProb values were subsequently
5046 ** changed based on STAT4 information while computing subsequent loops,
5047 ** then we need to rerun the whole loop building process so that all
5048 ** loops will be built using the revised truthProb values. */
5049 if( sWLB
.bldFlags2
& SQLITE_BLDF2_2NDPASS
){
5050 WHERETRACE_ALL_LOOPS(pWInfo
, sWLB
.pWC
);
5052 ("**** Redo all loop computations due to"
5053 " TERM_HIGHTRUTH changes ****\n"));
5054 while( pWInfo
->pLoops
){
5055 WhereLoop
*p
= pWInfo
->pLoops
;
5056 pWInfo
->pLoops
= p
->pNextLoop
;
5057 whereLoopDelete(db
, p
);
5059 rc
= whereLoopAddAll(&sWLB
);
5060 if( rc
) goto whereBeginError
;
5063 WHERETRACE_ALL_LOOPS(pWInfo
, sWLB
.pWC
);
5065 wherePathSolver(pWInfo
, 0);
5066 if( db
->mallocFailed
) goto whereBeginError
;
5067 if( pWInfo
->pOrderBy
){
5068 wherePathSolver(pWInfo
, pWInfo
->nRowOut
+1);
5069 if( db
->mallocFailed
) goto whereBeginError
;
5072 if( pWInfo
->pOrderBy
==0 && (db
->flags
& SQLITE_ReverseOrder
)!=0 ){
5073 pWInfo
->revMask
= ALLBITS
;
5075 if( pParse
->nErr
|| db
->mallocFailed
){
5076 goto whereBeginError
;
5078 #ifdef WHERETRACE_ENABLED
5079 if( sqlite3WhereTrace
){
5080 sqlite3DebugPrintf("---- Solution nRow=%d", pWInfo
->nRowOut
);
5081 if( pWInfo
->nOBSat
>0 ){
5082 sqlite3DebugPrintf(" ORDERBY=%d,0x%llx", pWInfo
->nOBSat
, pWInfo
->revMask
);
5084 switch( pWInfo
->eDistinct
){
5085 case WHERE_DISTINCT_UNIQUE
: {
5086 sqlite3DebugPrintf(" DISTINCT=unique");
5089 case WHERE_DISTINCT_ORDERED
: {
5090 sqlite3DebugPrintf(" DISTINCT=ordered");
5093 case WHERE_DISTINCT_UNORDERED
: {
5094 sqlite3DebugPrintf(" DISTINCT=unordered");
5098 sqlite3DebugPrintf("\n");
5099 for(ii
=0; ii
<pWInfo
->nLevel
; ii
++){
5100 sqlite3WhereLoopPrint(pWInfo
->a
[ii
].pWLoop
, sWLB
.pWC
);
5105 /* Attempt to omit tables from the join that do not affect the result.
5106 ** For a table to not affect the result, the following must be true:
5108 ** 1) The query must not be an aggregate.
5109 ** 2) The table must be the RHS of a LEFT JOIN.
5110 ** 3) Either the query must be DISTINCT, or else the ON or USING clause
5111 ** must contain a constraint that limits the scan of the table to
5112 ** at most a single row.
5113 ** 4) The table must not be referenced by any part of the query apart
5114 ** from its own USING or ON clause.
5116 ** For example, given:
5118 ** CREATE TABLE t1(ipk INTEGER PRIMARY KEY, v1);
5119 ** CREATE TABLE t2(ipk INTEGER PRIMARY KEY, v2);
5120 ** CREATE TABLE t3(ipk INTEGER PRIMARY KEY, v3);
5122 ** then table t2 can be omitted from the following:
5124 ** SELECT v1, v3 FROM t1
5125 ** LEFT JOIN t2 ON (t1.ipk=t2.ipk)
5126 ** LEFT JOIN t3 ON (t1.ipk=t3.ipk)
5130 ** SELECT DISTINCT v1, v3 FROM t1
5132 ** LEFT JOIN t3 ON (t1.ipk=t3.ipk)
5134 notReady
= ~(Bitmask
)0;
5135 if( pWInfo
->nLevel
>=2
5136 && pResultSet
!=0 /* these two combine to guarantee */
5137 && 0==(wctrlFlags
& WHERE_AGG_DISTINCT
) /* condition (1) above */
5138 && OptimizationEnabled(db
, SQLITE_OmitNoopJoin
)
5141 Bitmask tabUsed
= sqlite3WhereExprListUsage(pMaskSet
, pResultSet
);
5142 if( sWLB
.pOrderBy
){
5143 tabUsed
|= sqlite3WhereExprListUsage(pMaskSet
, sWLB
.pOrderBy
);
5145 for(i
=pWInfo
->nLevel
-1; i
>=1; i
--){
5146 WhereTerm
*pTerm
, *pEnd
;
5148 pLoop
= pWInfo
->a
[i
].pWLoop
;
5149 pItem
= &pWInfo
->pTabList
->a
[pLoop
->iTab
];
5150 if( (pItem
->fg
.jointype
& JT_LEFT
)==0 ) continue;
5151 if( (wctrlFlags
& WHERE_WANT_DISTINCT
)==0
5152 && (pLoop
->wsFlags
& WHERE_ONEROW
)==0
5156 if( (tabUsed
& pLoop
->maskSelf
)!=0 ) continue;
5157 pEnd
= sWLB
.pWC
->a
+ sWLB
.pWC
->nTerm
;
5158 for(pTerm
=sWLB
.pWC
->a
; pTerm
<pEnd
; pTerm
++){
5159 if( (pTerm
->prereqAll
& pLoop
->maskSelf
)!=0 ){
5160 if( !ExprHasProperty(pTerm
->pExpr
, EP_FromJoin
)
5161 || pTerm
->pExpr
->iRightJoinTable
!=pItem
->iCursor
5167 if( pTerm
<pEnd
) continue;
5168 WHERETRACE(0xffff, ("-> drop loop %c not used\n", pLoop
->cId
));
5169 notReady
&= ~pLoop
->maskSelf
;
5170 for(pTerm
=sWLB
.pWC
->a
; pTerm
<pEnd
; pTerm
++){
5171 if( (pTerm
->prereqAll
& pLoop
->maskSelf
)!=0 ){
5172 pTerm
->wtFlags
|= TERM_CODED
;
5175 if( i
!=pWInfo
->nLevel
-1 ){
5176 int nByte
= (pWInfo
->nLevel
-1-i
) * sizeof(WhereLevel
);
5177 memmove(&pWInfo
->a
[i
], &pWInfo
->a
[i
+1], nByte
);
5183 #if defined(WHERETRACE_ENABLED)
5184 if( sqlite3WhereTrace
& 0x100 ){ /* Display all terms of the WHERE clause */
5185 sqlite3DebugPrintf("---- WHERE clause at end of analysis:\n");
5186 sqlite3WhereClausePrint(sWLB
.pWC
);
5188 WHERETRACE(0xffff,("*** Optimizer Finished ***\n"));
5190 pWInfo
->pParse
->nQueryLoop
+= pWInfo
->nRowOut
;
5192 /* If the caller is an UPDATE or DELETE statement that is requesting
5193 ** to use a one-pass algorithm, determine if this is appropriate.
5195 ** A one-pass approach can be used if the caller has requested one
5196 ** and either (a) the scan visits at most one row or (b) each
5197 ** of the following are true:
5199 ** * the caller has indicated that a one-pass approach can be used
5200 ** with multiple rows (by setting WHERE_ONEPASS_MULTIROW), and
5201 ** * the table is not a virtual table, and
5202 ** * either the scan does not use the OR optimization or the caller
5203 ** is a DELETE operation (WHERE_DUPLICATES_OK is only specified
5206 ** The last qualification is because an UPDATE statement uses
5207 ** WhereInfo.aiCurOnePass[1] to determine whether or not it really can
5208 ** use a one-pass approach, and this is not set accurately for scans
5209 ** that use the OR optimization.
5211 assert( (wctrlFlags
& WHERE_ONEPASS_DESIRED
)==0 || pWInfo
->nLevel
==1 );
5212 if( (wctrlFlags
& WHERE_ONEPASS_DESIRED
)!=0 ){
5213 int wsFlags
= pWInfo
->a
[0].pWLoop
->wsFlags
;
5214 int bOnerow
= (wsFlags
& WHERE_ONEROW
)!=0;
5215 assert( !(wsFlags
& WHERE_VIRTUALTABLE
) || IsVirtual(pTabList
->a
[0].pTab
) );
5217 0!=(wctrlFlags
& WHERE_ONEPASS_MULTIROW
)
5218 && !IsVirtual(pTabList
->a
[0].pTab
)
5219 && (0==(wsFlags
& WHERE_MULTI_OR
) || (wctrlFlags
& WHERE_DUPLICATES_OK
))
5221 pWInfo
->eOnePass
= bOnerow
? ONEPASS_SINGLE
: ONEPASS_MULTI
;
5222 if( HasRowid(pTabList
->a
[0].pTab
) && (wsFlags
& WHERE_IDX_ONLY
) ){
5223 if( wctrlFlags
& WHERE_ONEPASS_MULTIROW
){
5224 bFordelete
= OPFLAG_FORDELETE
;
5226 pWInfo
->a
[0].pWLoop
->wsFlags
= (wsFlags
& ~WHERE_IDX_ONLY
);
5231 /* Open all tables in the pTabList and any indices selected for
5232 ** searching those tables.
5234 for(ii
=0, pLevel
=pWInfo
->a
; ii
<nTabList
; ii
++, pLevel
++){
5235 Table
*pTab
; /* Table to open */
5236 int iDb
; /* Index of database containing table/index */
5239 pTabItem
= &pTabList
->a
[pLevel
->iFrom
];
5240 pTab
= pTabItem
->pTab
;
5241 iDb
= sqlite3SchemaToIndex(db
, pTab
->pSchema
);
5242 pLoop
= pLevel
->pWLoop
;
5243 if( (pTab
->tabFlags
& TF_Ephemeral
)!=0 || IsView(pTab
) ){
5246 #ifndef SQLITE_OMIT_VIRTUALTABLE
5247 if( (pLoop
->wsFlags
& WHERE_VIRTUALTABLE
)!=0 ){
5248 const char *pVTab
= (const char *)sqlite3GetVTable(db
, pTab
);
5249 int iCur
= pTabItem
->iCursor
;
5250 sqlite3VdbeAddOp4(v
, OP_VOpen
, iCur
, 0, 0, pVTab
, P4_VTAB
);
5251 }else if( IsVirtual(pTab
) ){
5255 if( (pLoop
->wsFlags
& WHERE_IDX_ONLY
)==0
5256 && (wctrlFlags
& WHERE_OR_SUBCLAUSE
)==0 ){
5257 int op
= OP_OpenRead
;
5258 if( pWInfo
->eOnePass
!=ONEPASS_OFF
){
5260 pWInfo
->aiCurOnePass
[0] = pTabItem
->iCursor
;
5262 sqlite3OpenTable(pParse
, pTabItem
->iCursor
, iDb
, pTab
, op
);
5263 assert( pTabItem
->iCursor
==pLevel
->iTabCur
);
5264 testcase( pWInfo
->eOnePass
==ONEPASS_OFF
&& pTab
->nCol
==BMS
-1 );
5265 testcase( pWInfo
->eOnePass
==ONEPASS_OFF
&& pTab
->nCol
==BMS
);
5266 if( pWInfo
->eOnePass
==ONEPASS_OFF
5268 && (pTab
->tabFlags
& (TF_HasGenerated
|TF_WithoutRowid
))==0
5270 /* If we know that only a prefix of the record will be used,
5271 ** it is advantageous to reduce the "column count" field in
5272 ** the P4 operand of the OP_OpenRead/Write opcode. */
5273 Bitmask b
= pTabItem
->colUsed
;
5275 for(; b
; b
=b
>>1, n
++){}
5276 sqlite3VdbeChangeP4(v
, -1, SQLITE_INT_TO_PTR(n
), P4_INT32
);
5277 assert( n
<=pTab
->nCol
);
5279 #ifdef SQLITE_ENABLE_CURSOR_HINTS
5280 if( pLoop
->u
.btree
.pIndex
!=0 ){
5281 sqlite3VdbeChangeP5(v
, OPFLAG_SEEKEQ
|bFordelete
);
5285 sqlite3VdbeChangeP5(v
, bFordelete
);
5287 #ifdef SQLITE_ENABLE_COLUMN_USED_MASK
5288 sqlite3VdbeAddOp4Dup8(v
, OP_ColumnsUsed
, pTabItem
->iCursor
, 0, 0,
5289 (const u8
*)&pTabItem
->colUsed
, P4_INT64
);
5292 sqlite3TableLock(pParse
, iDb
, pTab
->tnum
, 0, pTab
->zName
);
5294 if( pLoop
->wsFlags
& WHERE_INDEXED
){
5295 Index
*pIx
= pLoop
->u
.btree
.pIndex
;
5297 int op
= OP_OpenRead
;
5298 /* iAuxArg is always set to a positive value if ONEPASS is possible */
5299 assert( iAuxArg
!=0 || (pWInfo
->wctrlFlags
& WHERE_ONEPASS_DESIRED
)==0 );
5300 if( !HasRowid(pTab
) && IsPrimaryKeyIndex(pIx
)
5301 && (wctrlFlags
& WHERE_OR_SUBCLAUSE
)!=0
5303 /* This is one term of an OR-optimization using the PRIMARY KEY of a
5304 ** WITHOUT ROWID table. No need for a separate index */
5305 iIndexCur
= pLevel
->iTabCur
;
5307 }else if( pWInfo
->eOnePass
!=ONEPASS_OFF
){
5308 Index
*pJ
= pTabItem
->pTab
->pIndex
;
5309 iIndexCur
= iAuxArg
;
5310 assert( wctrlFlags
& WHERE_ONEPASS_DESIRED
);
5311 while( ALWAYS(pJ
) && pJ
!=pIx
){
5316 pWInfo
->aiCurOnePass
[1] = iIndexCur
;
5317 }else if( iAuxArg
&& (wctrlFlags
& WHERE_OR_SUBCLAUSE
)!=0 ){
5318 iIndexCur
= iAuxArg
;
5321 iIndexCur
= pParse
->nTab
++;
5323 pLevel
->iIdxCur
= iIndexCur
;
5324 assert( pIx
->pSchema
==pTab
->pSchema
);
5325 assert( iIndexCur
>=0 );
5327 sqlite3VdbeAddOp3(v
, op
, iIndexCur
, pIx
->tnum
, iDb
);
5328 sqlite3VdbeSetP4KeyInfo(pParse
, pIx
);
5329 if( (pLoop
->wsFlags
& WHERE_CONSTRAINT
)!=0
5330 && (pLoop
->wsFlags
& (WHERE_COLUMN_RANGE
|WHERE_SKIPSCAN
))==0
5331 && (pLoop
->wsFlags
& WHERE_BIGNULL_SORT
)==0
5332 && (pLoop
->wsFlags
& WHERE_IN_SEEKSCAN
)==0
5333 && (pWInfo
->wctrlFlags
&WHERE_ORDERBY_MIN
)==0
5334 && pWInfo
->eDistinct
!=WHERE_DISTINCT_ORDERED
5336 sqlite3VdbeChangeP5(v
, OPFLAG_SEEKEQ
);
5338 VdbeComment((v
, "%s", pIx
->zName
));
5339 #ifdef SQLITE_ENABLE_COLUMN_USED_MASK
5343 for(ii
=0; ii
<pIx
->nColumn
; ii
++){
5344 jj
= pIx
->aiColumn
[ii
];
5345 if( jj
<0 ) continue;
5346 if( jj
>63 ) jj
= 63;
5347 if( (pTabItem
->colUsed
& MASKBIT(jj
))==0 ) continue;
5348 colUsed
|= ((u64
)1)<<(ii
<63 ? ii
: 63);
5350 sqlite3VdbeAddOp4Dup8(v
, OP_ColumnsUsed
, iIndexCur
, 0, 0,
5351 (u8
*)&colUsed
, P4_INT64
);
5353 #endif /* SQLITE_ENABLE_COLUMN_USED_MASK */
5356 if( iDb
>=0 ) sqlite3CodeVerifySchema(pParse
, iDb
);
5358 pWInfo
->iTop
= sqlite3VdbeCurrentAddr(v
);
5359 if( db
->mallocFailed
) goto whereBeginError
;
5361 /* Generate the code to do the search. Each iteration of the for
5362 ** loop below generates code for a single nested loop of the VM
5365 for(ii
=0; ii
<nTabList
; ii
++){
5368 if( pParse
->nErr
) goto whereBeginError
;
5369 pLevel
= &pWInfo
->a
[ii
];
5370 wsFlags
= pLevel
->pWLoop
->wsFlags
;
5371 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
5372 if( (pLevel
->pWLoop
->wsFlags
& WHERE_AUTO_INDEX
)!=0 ){
5373 constructAutomaticIndex(pParse
, &pWInfo
->sWC
,
5374 &pTabList
->a
[pLevel
->iFrom
], notReady
, pLevel
);
5375 if( db
->mallocFailed
) goto whereBeginError
;
5378 addrExplain
= sqlite3WhereExplainOneScan(
5379 pParse
, pTabList
, pLevel
, wctrlFlags
5381 pLevel
->addrBody
= sqlite3VdbeCurrentAddr(v
);
5382 notReady
= sqlite3WhereCodeOneLoopStart(pParse
,v
,pWInfo
,ii
,pLevel
,notReady
);
5383 pWInfo
->iContinue
= pLevel
->addrCont
;
5384 if( (wsFlags
&WHERE_MULTI_OR
)==0 && (wctrlFlags
&WHERE_OR_SUBCLAUSE
)==0 ){
5385 sqlite3WhereAddScanStatus(v
, pTabList
, pLevel
, addrExplain
);
5390 VdbeModuleComment((v
, "Begin WHERE-core"));
5391 pWInfo
->iEndWhere
= sqlite3VdbeCurrentAddr(v
);
5394 /* Jump here if malloc fails */
5397 testcase( pWInfo
->pExprMods
!=0 );
5398 whereUndoExprMods(pWInfo
);
5399 pParse
->nQueryLoop
= pWInfo
->savedNQueryLoop
;
5400 whereInfoFree(db
, pWInfo
);
5406 ** Part of sqlite3WhereEnd() will rewrite opcodes to reference the
5407 ** index rather than the main table. In SQLITE_DEBUG mode, we want
5408 ** to trace those changes if PRAGMA vdbe_addoptrace=on. This routine
5411 #ifndef SQLITE_DEBUG
5412 # define OpcodeRewriteTrace(D,K,P) /* no-op */
5414 # define OpcodeRewriteTrace(D,K,P) sqlite3WhereOpcodeRewriteTrace(D,K,P)
5415 static void sqlite3WhereOpcodeRewriteTrace(
5420 if( (db
->flags
& SQLITE_VdbeAddopTrace
)==0 ) return;
5421 sqlite3VdbePrintOp(0, pc
, pOp
);
5426 ** Generate the end of the WHERE loop. See comments on
5427 ** sqlite3WhereBegin() for additional information.
5429 void sqlite3WhereEnd(WhereInfo
*pWInfo
){
5430 Parse
*pParse
= pWInfo
->pParse
;
5431 Vdbe
*v
= pParse
->pVdbe
;
5435 SrcList
*pTabList
= pWInfo
->pTabList
;
5436 sqlite3
*db
= pParse
->db
;
5437 int iEnd
= sqlite3VdbeCurrentAddr(v
);
5439 /* Generate loop termination code.
5441 VdbeModuleComment((v
, "End WHERE-core"));
5442 for(i
=pWInfo
->nLevel
-1; i
>=0; i
--){
5444 pLevel
= &pWInfo
->a
[i
];
5445 pLoop
= pLevel
->pWLoop
;
5446 if( pLevel
->op
!=OP_Noop
){
5447 #ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT
5451 if( pWInfo
->eDistinct
==WHERE_DISTINCT_ORDERED
5452 && i
==pWInfo
->nLevel
-1 /* Ticket [ef9318757b152e3] 2017-10-21 */
5453 && (pLoop
->wsFlags
& WHERE_INDEXED
)!=0
5454 && (pIdx
= pLoop
->u
.btree
.pIndex
)->hasStat1
5455 && (n
= pLoop
->u
.btree
.nDistinctCol
)>0
5456 && pIdx
->aiRowLogEst
[n
]>=36
5458 int r1
= pParse
->nMem
+1;
5461 sqlite3VdbeAddOp3(v
, OP_Column
, pLevel
->iIdxCur
, j
, r1
+j
);
5463 pParse
->nMem
+= n
+1;
5464 op
= pLevel
->op
==OP_Prev
? OP_SeekLT
: OP_SeekGT
;
5465 addrSeek
= sqlite3VdbeAddOp4Int(v
, op
, pLevel
->iIdxCur
, 0, r1
, n
);
5466 VdbeCoverageIf(v
, op
==OP_SeekLT
);
5467 VdbeCoverageIf(v
, op
==OP_SeekGT
);
5468 sqlite3VdbeAddOp2(v
, OP_Goto
, 1, pLevel
->p2
);
5470 #endif /* SQLITE_DISABLE_SKIPAHEAD_DISTINCT */
5471 /* The common case: Advance to the next row */
5472 sqlite3VdbeResolveLabel(v
, pLevel
->addrCont
);
5473 sqlite3VdbeAddOp3(v
, pLevel
->op
, pLevel
->p1
, pLevel
->p2
, pLevel
->p3
);
5474 sqlite3VdbeChangeP5(v
, pLevel
->p5
);
5476 VdbeCoverageIf(v
, pLevel
->op
==OP_Next
);
5477 VdbeCoverageIf(v
, pLevel
->op
==OP_Prev
);
5478 VdbeCoverageIf(v
, pLevel
->op
==OP_VNext
);
5479 if( pLevel
->regBignull
){
5480 sqlite3VdbeResolveLabel(v
, pLevel
->addrBignull
);
5481 sqlite3VdbeAddOp2(v
, OP_DecrJumpZero
, pLevel
->regBignull
, pLevel
->p2
-1);
5484 #ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT
5485 if( addrSeek
) sqlite3VdbeJumpHere(v
, addrSeek
);
5488 sqlite3VdbeResolveLabel(v
, pLevel
->addrCont
);
5490 if( (pLoop
->wsFlags
& WHERE_IN_ABLE
)!=0 && pLevel
->u
.in
.nIn
>0 ){
5493 sqlite3VdbeResolveLabel(v
, pLevel
->addrNxt
);
5494 for(j
=pLevel
->u
.in
.nIn
, pIn
=&pLevel
->u
.in
.aInLoop
[j
-1]; j
>0; j
--, pIn
--){
5495 assert( sqlite3VdbeGetOp(v
, pIn
->addrInTop
+1)->opcode
==OP_IsNull
5496 || pParse
->db
->mallocFailed
);
5497 sqlite3VdbeJumpHere(v
, pIn
->addrInTop
+1);
5498 if( pIn
->eEndLoopOp
!=OP_Noop
){
5501 (pLoop
->wsFlags
& WHERE_VIRTUALTABLE
)==0
5502 && (pLoop
->wsFlags
& WHERE_IN_EARLYOUT
)!=0;
5503 if( pLevel
->iLeftJoin
){
5504 /* For LEFT JOIN queries, cursor pIn->iCur may not have been
5505 ** opened yet. This occurs for WHERE clauses such as
5506 ** "a = ? AND b IN (...)", where the index is on (a, b). If
5507 ** the RHS of the (a=?) is NULL, then the "b IN (...)" may
5508 ** never have been coded, but the body of the loop run to
5509 ** return the null-row. So, if the cursor is not open yet,
5510 ** jump over the OP_Next or OP_Prev instruction about to
5512 sqlite3VdbeAddOp2(v
, OP_IfNotOpen
, pIn
->iCur
,
5513 sqlite3VdbeCurrentAddr(v
) + 2 + bEarlyOut
);
5517 sqlite3VdbeAddOp4Int(v
, OP_IfNoHope
, pLevel
->iIdxCur
,
5518 sqlite3VdbeCurrentAddr(v
)+2,
5519 pIn
->iBase
, pIn
->nPrefix
);
5521 /* Retarget the OP_IsNull against the left operand of IN so
5522 ** it jumps past the OP_IfNoHope. This is because the
5523 ** OP_IsNull also bypasses the OP_Affinity opcode that is
5524 ** required by OP_IfNoHope. */
5525 sqlite3VdbeJumpHere(v
, pIn
->addrInTop
+1);
5528 sqlite3VdbeAddOp2(v
, pIn
->eEndLoopOp
, pIn
->iCur
, pIn
->addrInTop
);
5530 VdbeCoverageIf(v
, pIn
->eEndLoopOp
==OP_Prev
);
5531 VdbeCoverageIf(v
, pIn
->eEndLoopOp
==OP_Next
);
5533 sqlite3VdbeJumpHere(v
, pIn
->addrInTop
-1);
5536 sqlite3VdbeResolveLabel(v
, pLevel
->addrBrk
);
5537 if( pLevel
->addrSkip
){
5538 sqlite3VdbeGoto(v
, pLevel
->addrSkip
);
5539 VdbeComment((v
, "next skip-scan on %s", pLoop
->u
.btree
.pIndex
->zName
));
5540 sqlite3VdbeJumpHere(v
, pLevel
->addrSkip
);
5541 sqlite3VdbeJumpHere(v
, pLevel
->addrSkip
-2);
5543 #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
5544 if( pLevel
->addrLikeRep
){
5545 sqlite3VdbeAddOp2(v
, OP_DecrJumpZero
, (int)(pLevel
->iLikeRepCntr
>>1),
5546 pLevel
->addrLikeRep
);
5550 if( pLevel
->iLeftJoin
){
5551 int ws
= pLoop
->wsFlags
;
5552 addr
= sqlite3VdbeAddOp1(v
, OP_IfPos
, pLevel
->iLeftJoin
); VdbeCoverage(v
);
5553 assert( (ws
& WHERE_IDX_ONLY
)==0 || (ws
& WHERE_INDEXED
)!=0 );
5554 if( (ws
& WHERE_IDX_ONLY
)==0 ){
5555 assert( pLevel
->iTabCur
==pTabList
->a
[pLevel
->iFrom
].iCursor
);
5556 sqlite3VdbeAddOp1(v
, OP_NullRow
, pLevel
->iTabCur
);
5558 if( (ws
& WHERE_INDEXED
)
5559 || ((ws
& WHERE_MULTI_OR
) && pLevel
->u
.pCoveringIdx
)
5561 if( ws
& WHERE_MULTI_OR
){
5562 Index
*pIx
= pLevel
->u
.pCoveringIdx
;
5563 int iDb
= sqlite3SchemaToIndex(db
, pIx
->pSchema
);
5564 sqlite3VdbeAddOp3(v
, OP_ReopenIdx
, pLevel
->iIdxCur
, pIx
->tnum
, iDb
);
5565 sqlite3VdbeSetP4KeyInfo(pParse
, pIx
);
5567 sqlite3VdbeAddOp1(v
, OP_NullRow
, pLevel
->iIdxCur
);
5569 if( pLevel
->op
==OP_Return
){
5570 sqlite3VdbeAddOp2(v
, OP_Gosub
, pLevel
->p1
, pLevel
->addrFirst
);
5572 sqlite3VdbeGoto(v
, pLevel
->addrFirst
);
5574 sqlite3VdbeJumpHere(v
, addr
);
5576 VdbeModuleComment((v
, "End WHERE-loop%d: %s", i
,
5577 pWInfo
->pTabList
->a
[pLevel
->iFrom
].pTab
->zName
));
5580 /* The "break" point is here, just past the end of the outer loop.
5583 sqlite3VdbeResolveLabel(v
, pWInfo
->iBreak
);
5585 assert( pWInfo
->nLevel
<=pTabList
->nSrc
);
5586 for(i
=0, pLevel
=pWInfo
->a
; i
<pWInfo
->nLevel
; i
++, pLevel
++){
5588 VdbeOp
*pOp
, *pLastOp
;
5590 SrcItem
*pTabItem
= &pTabList
->a
[pLevel
->iFrom
];
5591 Table
*pTab
= pTabItem
->pTab
;
5593 pLoop
= pLevel
->pWLoop
;
5595 /* For a co-routine, change all OP_Column references to the table of
5596 ** the co-routine into OP_Copy of result contained in a register.
5597 ** OP_Rowid becomes OP_Null.
5599 if( pTabItem
->fg
.viaCoroutine
){
5600 testcase( pParse
->db
->mallocFailed
);
5601 translateColumnToCopy(pParse
, pLevel
->addrBody
, pLevel
->iTabCur
,
5602 pTabItem
->regResult
, 0);
5606 #ifdef SQLITE_ENABLE_EARLY_CURSOR_CLOSE
5607 /* Close all of the cursors that were opened by sqlite3WhereBegin.
5608 ** Except, do not close cursors that will be reused by the OR optimization
5609 ** (WHERE_OR_SUBCLAUSE). And do not close the OP_OpenWrite cursors
5610 ** created for the ONEPASS optimization.
5612 if( (pTab
->tabFlags
& TF_Ephemeral
)==0
5614 && (pWInfo
->wctrlFlags
& WHERE_OR_SUBCLAUSE
)==0
5616 int ws
= pLoop
->wsFlags
;
5617 if( pWInfo
->eOnePass
==ONEPASS_OFF
&& (ws
& WHERE_IDX_ONLY
)==0 ){
5618 sqlite3VdbeAddOp1(v
, OP_Close
, pTabItem
->iCursor
);
5620 if( (ws
& WHERE_INDEXED
)!=0
5621 && (ws
& (WHERE_IPK
|WHERE_AUTO_INDEX
))==0
5622 && pLevel
->iIdxCur
!=pWInfo
->aiCurOnePass
[1]
5624 sqlite3VdbeAddOp1(v
, OP_Close
, pLevel
->iIdxCur
);
5629 /* If this scan uses an index, make VDBE code substitutions to read data
5630 ** from the index instead of from the table where possible. In some cases
5631 ** this optimization prevents the table from ever being read, which can
5632 ** yield a significant performance boost.
5634 ** Calls to the code generator in between sqlite3WhereBegin and
5635 ** sqlite3WhereEnd will have created code that references the table
5636 ** directly. This loop scans all that code looking for opcodes
5637 ** that reference the table and converts them into opcodes that
5638 ** reference the index.
5640 if( pLoop
->wsFlags
& (WHERE_INDEXED
|WHERE_IDX_ONLY
) ){
5641 pIdx
= pLoop
->u
.btree
.pIndex
;
5642 }else if( pLoop
->wsFlags
& WHERE_MULTI_OR
){
5643 pIdx
= pLevel
->u
.pCoveringIdx
;
5646 && !db
->mallocFailed
5648 if( pWInfo
->eOnePass
==ONEPASS_OFF
|| !HasRowid(pIdx
->pTable
) ){
5651 last
= pWInfo
->iEndWhere
;
5653 k
= pLevel
->addrBody
+ 1;
5655 if( db
->flags
& SQLITE_VdbeAddopTrace
){
5656 printf("TRANSLATE opcodes in range %d..%d\n", k
, last
-1);
5658 /* Proof that the "+1" on the k value above is safe */
5659 pOp
= sqlite3VdbeGetOp(v
, k
- 1);
5660 assert( pOp
->opcode
!=OP_Column
|| pOp
->p1
!=pLevel
->iTabCur
);
5661 assert( pOp
->opcode
!=OP_Rowid
|| pOp
->p1
!=pLevel
->iTabCur
);
5662 assert( pOp
->opcode
!=OP_IfNullRow
|| pOp
->p1
!=pLevel
->iTabCur
);
5664 pOp
= sqlite3VdbeGetOp(v
, k
);
5665 pLastOp
= pOp
+ (last
- k
);
5666 assert( pOp
<=pLastOp
);
5668 if( pOp
->p1
!=pLevel
->iTabCur
){
5670 }else if( pOp
->opcode
==OP_Column
5671 #ifdef SQLITE_ENABLE_OFFSET_SQL_FUNC
5672 || pOp
->opcode
==OP_Offset
5676 assert( pIdx
->pTable
==pTab
);
5677 if( !HasRowid(pTab
) ){
5678 Index
*pPk
= sqlite3PrimaryKeyIndex(pTab
);
5679 x
= pPk
->aiColumn
[x
];
5682 testcase( x
!=sqlite3StorageColumnToTable(pTab
,x
) );
5683 x
= sqlite3StorageColumnToTable(pTab
,x
);
5685 x
= sqlite3TableColumnToIndex(pIdx
, x
);
5688 pOp
->p1
= pLevel
->iIdxCur
;
5689 OpcodeRewriteTrace(db
, k
, pOp
);
5691 assert( (pLoop
->wsFlags
& WHERE_IDX_ONLY
)==0 || x
>=0
5692 || pWInfo
->eOnePass
);
5693 }else if( pOp
->opcode
==OP_Rowid
){
5694 pOp
->p1
= pLevel
->iIdxCur
;
5695 pOp
->opcode
= OP_IdxRowid
;
5696 OpcodeRewriteTrace(db
, k
, pOp
);
5697 }else if( pOp
->opcode
==OP_IfNullRow
){
5698 pOp
->p1
= pLevel
->iIdxCur
;
5699 OpcodeRewriteTrace(db
, k
, pOp
);
5704 }while( (++pOp
)<pLastOp
);
5706 if( db
->flags
& SQLITE_VdbeAddopTrace
) printf("TRANSLATE complete\n");
5713 if( pWInfo
->pExprMods
) whereUndoExprMods(pWInfo
);
5714 pParse
->nQueryLoop
= pWInfo
->savedNQueryLoop
;
5715 whereInfoFree(db
, pWInfo
);